數(shù)據(jù)分析師筆試題1-常見聚類算法

來源：小紅書筆試-?？途W(wǎng)

一、算法基礎(chǔ)

1 auc與 roc

AUC：分類中一個正例，一個負例。預(yù)測為正的概率值比預(yù)測為負的概率值還要大的可能性就是auc。繪制ROC曲線，ROC曲線下面的面積就是AUC的值。


image.png

image.png

image.png

二、常見的聚類算法

(1) K-means聚類、K-中心點聚類、CLARANS算法,DIANA算法、BIRCH算法、Chameleon算法
(2) EM算法
(3) OPTICS算法、DBSCAN算法
分類
（1）基于質(zhì)心
K-means聚類√、K-中心點聚類、CLARANS算法,DIANA算法、
（2）基于層次
BIRCH算法√、Chameleon算法√
（3）基于概率
EM算法√
（4）基于密度
DBSCAN算法√
OPTICS算法（Ordering points to identify the clustering structure，排序點來識別聚類結(jié)構(gòu)）有效的解決了密度不同導(dǎo)致的聚類效果不好的問題。
（5）基于圖

各算法在sklearn中的調(diào)用


image.png

1 基于質(zhì)心

K-means聚類

目的：最小化平方誤差


image.png

理解：
第一步選擇初始質(zhì)心，最基本的方法是?從數(shù)據(jù)集中選擇樣本 X。
初始化之后，K-means包括在其他兩個步驟之間循環(huán)：

  • 第一步將每個樣品分配到最近的質(zhì)心。
  • 第二步通過獲取分配給每個先前質(zhì)心的所有樣本的平均值來創(chuàng)建新質(zhì)心。計算舊的和新的質(zhì)心之間的差異，并且算法重復(fù)這最后兩個步驟，直到該值小于閾值。換句話說，它重復(fù)直到質(zhì)心不顯著移動。

實現(xiàn)：

sklearn.cluster.KMeans(n_clusters=8,
    init='k-means++', 
    n_init=10, 
    max_iter=300, 
    tol=0.0001, 
    precompute_distances='auto', 
    verbose=0, 
    random_state=None, 
    copy_x=True, 
    n_jobs=1, 
    algorithm='auto'
    )
algorithm: kmeans的實現(xiàn)算法，有：’auto’, ‘full’, ‘elkan’, 其中 ‘full’表示用EM方式實現(xiàn)

優(yōu)缺點：
優(yōu)點：簡單，可解釋，速度快，主要調(diào)參只有k。
缺點：

  • 需要事先確定分類的簇數(shù)，即k值。
  • 采用迭代方法，得到的結(jié)果只是局部最優(yōu)。
  • 對初始值的選取比較敏感。（改進1：k-means++（sklearn已經(jīng)添加該參數(shù)的取值）;改進2：二分K-means）
  • 當數(shù)據(jù)量非常大時，算法的時間開銷是非常大的（改進：Mini Batch K-Means（精確度會降低，在可接受的范圍即可））；
  • 若簇中含有異常點，將導(dǎo)致均值偏離嚴重，對噪聲和孤立點數(shù)據(jù)敏感（改進1：離群點檢測的LOF算法，通過去除離群點后再聚類，可以減少離群點和孤立點對于聚類效果的影響；改進2：改成求點的中位數(shù)，這種聚類方式即K-k-median聚類（K中值））；
  • 對于不是凸的數(shù)據(jù)集比較難收斂(改進：基于密度的聚類算法更加適合，比如DESCAN算法)

2 基于概率

2.1 BIRCH算法

對于CF Tree，一般有3個重要參數(shù):

  • 第一個參數(shù)是每個內(nèi)部節(jié)點的最大CF數(shù)B
  • 第二個參數(shù)是每個葉子節(jié)點的最大CF數(shù)L
  • 第三個參數(shù)是葉節(jié)點每個CF的最大樣本半徑閾值T，也就是說，在這個CF中的所有樣本點一定要在半徑小于T的一個超球體內(nèi)。

步驟：
1.從根節(jié)點向下尋找和新樣本距離最近的葉子節(jié)點和葉子節(jié)點里最近的CF節(jié)點。

  1. 如果新樣本加入后，這個CF節(jié)點對應(yīng)的超球體半徑仍然滿足小于閾值T，則更新路徑上所有的CF三元組，插入結(jié)束。否則轉(zhuǎn)入3.
  2. 如果當前葉子節(jié)點的CF節(jié)點個數(shù)小于閾值L，則創(chuàng)建一個新的CF節(jié)點，放入新樣本，將新的CF節(jié)點放入這個葉子節(jié)點，更新路徑上所有的CF三元組，插入結(jié)束。否則轉(zhuǎn)入4。
    4.將當前葉子節(jié)點劃分為兩個新葉子節(jié)點，選擇舊葉子節(jié)點中所有CF元組里超球體距離最遠的兩個CF元組，分布作為兩個新葉子節(jié)點的第一個CF節(jié)點。將其他元組和新樣本元組按照距離遠近原則放入對應(yīng)的葉子節(jié)點。依次向上檢查父節(jié)點是否也要分裂，如果需要按和葉子節(jié)點分裂方式相同。
    優(yōu)缺點：
    優(yōu)點：節(jié)約內(nèi)存，聚類塊，可識別噪音點，可用于預(yù)分類處理
    缺點：
    1） 由于CF Tree對每個節(jié)點的CF個數(shù)有限制，導(dǎo)致聚類的結(jié)果可能和真實的類別分布不同.
    2） 對高維特征的數(shù)據(jù)聚類效果不好。此時可以選擇Mini Batch K-Means
    3） 如果數(shù)據(jù)集的分布簇不是類似于超球體，或者說不是凸的，則聚類效果不好。

2.2 chameleon 變色龍算法

是一種兩階段聚類法


image.png

步驟：

  • 第一階段把點分成很多小的簇；第一個是形成小簇集的過程就是從Data Set 到k最近鄰圖到分裂成小聚簇

  • 第二階段根據(jù)相近程度合并這些小的簇。第二階段計算任意兩個簇的互連性RI和緊密性RC，當兩個指標都比較大時才合并這兩個簇,合并這些小聚簇形成最終的結(jié)果聚簇


    image.png

優(yōu)缺點：
優(yōu)點：算法考慮了互連性和近似性，能發(fā)現(xiàn)高質(zhì)量的任意形狀的簇
缺點：參數(shù)復(fù)雜，時間復(fù)雜度高

3 基于密度

DESCAN算法

DBSCAN是基于一組鄰域來描述樣本集的緊密程度的，參數(shù)(?, MinPts)用來描述鄰域的樣本分布緊密程度。其中，?描述了某一樣本的鄰域距離閾值，MinPts描述了某一樣本的距離為?的鄰域中樣本個數(shù)的閾值。
理解：給定一個半徑長度r和一個最小點的數(shù)目m，然后以某個點為圓心，r為半徑，如果在該圓內(nèi)的點的數(shù)目大于m值，則把該點標記為中心點，如果數(shù)目小于m值，則被標記為噪聲點。重復(fù)該步驟，如果一個噪聲點存在于某個中心點的圓內(nèi)，則標記該點為邊緣點。直到所有點都被標記了，然后連接在一個圓內(nèi)中心點以及每個中心點的邊緣點組成一個簇。
實現(xiàn)：

class sklearn.cluster.DBSCAN(eps=0.5, 
        min_samples=5, 
        metric=’euclidean’, 
        metric_params=None, 
        algorithm=’auto’, 
        leaf_size=30, 
        p=None, 
        n_jobs=1)

eps:兩個樣本之間的最大距離，以便將它們視為在同一鄰域中。
min_samples:對于要被視為核心點的點，鄰域中的樣本數(shù)（或總權(quán)重）。這包括點本身。
metric：最近鄰距離度量參數(shù)?？梢允褂玫木嚯x度量較多，一般來說DBSCAN使用默認的歐式距離
algorithm：最近鄰搜索算法參數(shù)(暴力實現(xiàn)，kd數(shù)，球樹實現(xiàn))

DBSCAN小結(jié)

和傳統(tǒng)的K-Means算法相比，DBSCAN最大的不同就是不需要輸入類別數(shù)k，當然它最大的優(yōu)勢是可以發(fā)現(xiàn)任意形狀的聚類簇，而不是像K-Means，一般僅僅使用于凸的樣本集聚類。同時它在聚類的同時還可以找出異常點，這點和BIRCH算法類似。

那么我們什么時候需要用DBSCAN來聚類呢？一般來說，如果數(shù)據(jù)集是稠密的，并且數(shù)據(jù)集不是凸的，那么用DBSCAN會比K-Means聚類效果好很多。如果數(shù)據(jù)集不是稠密的，則不推薦用DBSCAN來聚類。

4、EM算法

最大期望（EM）算法是在概率（probabilistic）模型中尋找參數(shù)最大似然估計或者最大后驗估計的算法，其中概率模型依賴于無法觀測的隱藏變量（Latent Variable）。
步驟：
最大期望算法經(jīng)過兩個步驟交替進行計算：

  • 第一步是計算期望（E），利用對隱藏變量的現(xiàn)有估計值，計算其最大似然估計值；

  • 第二步是最大化（M），最大化在 E 步上求得的最大似然值來計算參數(shù)的值。M 步上找到的參數(shù)估計值被用于下一個 E 步計算中，這個過程不斷交替進行。


    image.png
參考來源：

3 判別模型與生成式模型

判別式模型是直接對條件概率p(y|x;θ)建模。生成式模型則會對x和y的聯(lián)合分布p(x,y)建模，然后通過貝葉斯公式來求得p(yi|x)，然后選取使得p(yi|x)最大的yi。

image.png

生成式模型有：
AODE（平均單依賴估計）
樸素貝葉斯Native Bayes
混合高斯型Gaussians
隱馬爾科夫模型HMM
貝葉斯網(wǎng)絡(luò)
信念網(wǎng)絡(luò)sigmoid belief networks
馬爾科夫隨機場Markov random fields
深度信念網(wǎng)絡(luò)DBN
隱含狄利克雷分布簡稱LDA(Latent Dirichlet allocation)
多專家模型（the mixture of experts model）
Restricted Boltzmann Machine（限制波茲曼機）

判別式模型有：
感知機(Perceptron):二分類 +1 / -1
決策樹
邏輯回歸logic regression
K近鄰 KNN
最大熵模型
支持向量機SVM
提升方法/集成學習Boosting
神經(jīng)網(wǎng)絡(luò)NN
高斯過程Gaussian process
條件隨機場CRF
CART決策樹(Classification and regression tree)
Linear Regression（線性回歸）
Linear Discriminant Analysis（線性判別分析）

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

友情鏈接更多精彩內(nèi)容