scikit-learn 聚類

2023-02-20 13:44 更新

可以使用模塊 sklearn.cluster 對未標(biāo)記的數(shù)據(jù)進(jìn)行 聚類(Clustering) 。

每個聚類算法都有兩個變體:一個是類，它實現(xiàn)了 fit 方法來學(xué)習(xí)訓(xùn)練數(shù)據(jù)上的簇，另一個是函數(shù)，給定訓(xùn)練數(shù)據(jù)，返回對應(yīng)于不同簇的整數(shù)標(biāo)簽數(shù)組。對于類，可以在 labels_ 屬性中找到訓(xùn)練數(shù)據(jù)上的標(biāo)簽。

輸入數(shù)據(jù)

特別需要注意的一點是，本模塊實現(xiàn)的算法可以采用不同類型的矩陣作為輸入。所有算法的調(diào)用接口都接受 shape[n_samples, n_features] 的標(biāo)準(zhǔn)數(shù)據(jù)矩陣。 這些矩陣可以通過使用 sklearn.feature_extraction 模塊中的類獲得。對于 AffinityPropagation, SpectralClustering 和 DBSCAN 也可以輸入 shape [n_samples, n_samples] 的相似矩陣，可以通過 sklearn.metrics.pairwise 模塊中的函數(shù)獲得。

2.3.1. 聚類方法概述


? scikit-learn 中聚類算法的比較

Method name（方法名稱） Parameters（參數(shù)） Scalability（可擴(kuò)展性） Usecase（使用場景） Geometry (metric used)（幾何圖形（公制））
K-Means（K-均值） number of clusters（聚類形成的簇的個數(shù)） 非常大的 n_samples, 中等的 n_clusters 使用 MiniBatch 代碼） 通用, 均勻的 cluster size（簇大?。? flat geometry（平面幾何）, 不是太多的 clusters（簇） Distances between points（點之間的距離）
Affinity propagation damping（阻尼）, sample preference（樣本偏好） Not scalable with n_samples（n_samples 不可擴(kuò)展） Many clusters, uneven cluster size, non-flat geometry（許多簇，不均勻的簇大小，非平面幾何） Graph distance (e.g. nearest-neighbor graph)（圖距離（例如，最近鄰圖））
Mean-shift bandwidth（帶寬） Not scalable with n_samples （n_samples不可擴(kuò)展） Many clusters, uneven cluster size, non-flat geometry（許多簇，不均勻的簇大小，非平面幾何） Distances between points（點之間的距離）
Spectral clustering number of clusters（簇的個數(shù)） 中等的 n_samples, 小的 n_clusters Few clusters, even cluster size, non-flat geometry（幾個簇，均勻的簇大小，非平面幾何） Graph distance (e.g. nearest-neighbor graph)（圖距離（例如最近鄰圖））
Ward hierarchical clustering number of clusters（簇的個數(shù)） 大的 n_samples 和 n_clusters Many clusters, possibly connectivity constraints（很多的簇，可能連接限制） Distances between points（點之間的距離）
Agglomerative clustering number of clusters（簇的個數(shù)）, linkage type（鏈接類型）, distance（距離） 大的 n_samples 和 n_clusters Many clusters, possibly connectivity constraints, non Euclidean distances（很多簇，可能連接限制，非歐氏距離） Any pairwise distance（任意成對距離）
DBSCAN neighborhood size（neighborhood 的大?。?/td> 非常大的 n_samples, 中等的 n_clusters Non-flat geometry, uneven cluster sizes（非平面幾何，不均勻的簇大?。?/td> Distances between nearest points（最近點之間的距離）
Gaussian mixtures（高斯混合） many（很多） Not scalable（不可擴(kuò)展） Flat geometry, good for density estimation（平面幾何，適用于密度估計） Mahalanobis distances to centers（ 與中心的馬氏距離）
Birch branching factor（分支因子）, threshold（閾值）, optional global clusterer（可選全局簇）. 大的 n_clusters 和 n_samples Large dataset, outlier removal, data reduction.（大型數(shù)據(jù)集，異常值去除，數(shù)據(jù)簡化）

當(dāng)簇具有一個特定的形狀，即非平面流體，并且標(biāo)準(zhǔn)歐氏距離不是正確的度量標(biāo)準(zhǔn)時，非平面幾何聚類是非常有用的。這種情況出現(xiàn)在上圖的前兩行中。

用于聚類（clustering）的高斯混合模型，將在文檔的另一章描述混合模型。KMeans可以看作是每個分量協(xié)方差相等的高斯混合模型的一個特例。

2.3.2. K-means

KMeans 算法通過把樣本分離成 n 個具有相同方差的類的方式來對數(shù)據(jù)進(jìn)行聚類，最小化一個稱為慣量或簇內(nèi)平方和的準(zhǔn)則（見下文）。該算法需要指定簇的數(shù)量。它可以很好地擴(kuò)展到大量樣本，并已經(jīng)在許多不同領(lǐng)域的應(yīng)用領(lǐng)域被廣泛使用。

k-means 算法將一組 樣本 劃分成 個不相交的簇 ,每個都用該簇中樣本的均值 描述。 這個均值通常被稱為簇的 “質(zhì)心”; 盡管它們處在同一個空間，但它們通常不是從 中挑選出的點，雖然它們是處在同一個空間。

K-means算法旨在選擇一個質(zhì)心, 能夠最小化慣性或簇內(nèi)平方和的標(biāo)準(zhǔn):

? $$\sum_{i=0}^{n} \min {\mu{j} \in C}\left(\left|x_{i}-\mu_{j}\right|^{2}\right)$$

慣性被認(rèn)為是測量簇內(nèi)聚程度的尺度。它有很多缺點:

  • 慣性假設(shè)簇是凸的，各項同性的，但并不總是這樣。它對細(xì)長的簇或具有不規(guī)則形狀的流形反應(yīng)很差。
  • 慣性不是一個歸一化度量： 我們只知道當(dāng)慣量的值越低越好，零是最優(yōu)的。但是在非常高維的空間中，歐氏距離往往會膨脹（這就是所謂的 “”的一個例子）。在 k-means 聚類算法之前運行主成分分析(PCA)等降維算法可以緩解這個問題并加快計算速度。


K-means 通常被稱為 Lloyd 算法。簡單來說，算法有三個步驟。第一步是選擇初始質(zhì)心，最基本的方法是從數(shù)據(jù)集中選擇個樣本。初始化之后，K-means由其他兩個步驟之間的循環(huán)組成。第一步將每個樣本分配到其最近的質(zhì)心。第二步是通過取分配給前一個質(zhì)心的所有樣本的平均值來創(chuàng)建新的質(zhì)心。計算新舊質(zhì)心之間的差值，算法重復(fù)最后兩個步驟，直到該值小于閾值。換句話說，算法重復(fù)這個步驟，直到質(zhì)心不再明顯移動。


K-means 相當(dāng)于一個具有小的、完全相等的、對角協(xié)方差矩陣的期望最大化算法。

算法也可以通過 Voronoi diagrams（voronoi圖）的概念來理解。首先，使用當(dāng)前質(zhì)心計算點的Voronoi圖。Voronoi圖中的每個段成為一個單獨的簇。其次，將質(zhì)心更新為每個段的平均值。然后算法重復(fù)這個過程，直到滿足停止條件。通常，當(dāng)?shù)g目標(biāo)函數(shù)的相對下降量小于給定的公差值時，算法停止。在此實現(xiàn)中不是這樣的:當(dāng)質(zhì)心移動小于公差時迭代停止。

只要有足夠的時間，K-means 將總是收斂的，但這可能是局部的最小值。這很大程度上取決于質(zhì)心的初始化。 因此，初始化不同質(zhì)心的計算通常會進(jìn)行幾次。幫助解決這個問題的一種方法是 k-means++ 初始化方案，它已經(jīng)在 scikit-learn 中實現(xiàn)（使用 init='k-means++' 參數(shù)）。 這將初始化質(zhì)心（通常）彼此遠(yuǎn)離，相對隨機(jī)初始化得到更好的結(jié)果，如參考文獻(xiàn)所示。

該算法支持樣本權(quán)重功能，樣本權(quán)重可以由參數(shù)sample_weight給出。該功能允許計算簇中心和慣性值時為一些樣本分配更多的權(quán)重。 例如，給某個樣本分配一個權(quán)重值2，相當(dāng)于在數(shù)據(jù)集X中增加一個該樣本的重復(fù)項。

K-means可用于矢量量化。這是利用 KMeans 訓(xùn)練模型的變換方法實現(xiàn)的。

2.3.2.1. 低級并行

KMeans通過Cython從基于OpenMP的并行性中獲益。并行處理小塊數(shù)據(jù)(256個樣本)，這還會產(chǎn)生較低的內(nèi)存占用。有關(guān)如何控制線程數(shù)量的詳細(xì)信息，請參閱我們的Parallelism說明。

示例:

參考資料:

2.3.2.2. 小批量 K-Means

MiniBatchKMeans 是 KMeans 算法的變體，它使用小批量(mini-batches)來減少計算時間，同時仍然試圖優(yōu)化相同的目標(biāo)函數(shù)。小批量是輸入數(shù)據(jù)的子集，在每次訓(xùn)練迭代中隨機(jī)抽樣。這些小批量極大減少了收斂到局部解所需的計算量。 與其他降低 k-means 收斂時間的算法相比，小批量 k-means 產(chǎn)生的結(jié)果一般只比標(biāo)準(zhǔn)算法略差。

算法在兩個主要步驟之間迭代，類似于普通的k-means。在第一步中，從數(shù)據(jù)集中隨機(jī)抽取樣本，以形成一個小批量。然后把它們分配給最近的質(zhì)心。在第二步，質(zhì)心被更新。與k-means相比，這是在每個樣本的基礎(chǔ)上完成的。對于小批量的每個樣本，將通過對樣本和之前分配給該樣本的所有樣本的流平均值更新分配的質(zhì)心。這具有隨時間減少質(zhì)心變化率的效果。這些步驟一直執(zhí)行到收斂或達(dá)到預(yù)定的迭代次數(shù)。

MiniBatchKMeans 收斂速度比 KMeans快 ，但是結(jié)果的質(zhì)量會降低。在實踐中，質(zhì)量差異可能非常小，如示例和引用的參考文獻(xiàn)所示。


示例:

參考文獻(xiàn):

2.3.3. Affinity Propagation

AffinityPropagation AP聚類是通過在樣本對之間發(fā)送消息直到收斂的方式來創(chuàng)建聚類。然后使用少量有代表性的樣本作為聚類中心來描述數(shù)據(jù)集，而這些樣本對可以被認(rèn)為是最能代表數(shù)據(jù)集中其它數(shù)據(jù)的樣本。把樣本對之間發(fā)送的消息作為一個樣本對另一個樣本的模范樣本的適合程度，適合程度值在根據(jù)來自其他對的值不斷更新。這種更新以迭代的方式進(jìn)行，直到收斂為止，此時會選擇最終的范例，從而給出最終的聚類。


Affinity Propagation 算法非常有趣，因為它可以根據(jù)提供的數(shù)據(jù)決定聚類的數(shù)量。 因此有兩個比較重要的參數(shù)是preference（控制使用多少模范樣本 ）和阻尼因子(damping factor) 減少吸引信息和歸屬信息以避免更新信息時的數(shù)據(jù)振蕩。

AP聚類算法主要的缺點是它的復(fù)雜度。Affinity Propagation 聚類算法的時間復(fù)雜度是 ， 其中是樣本的個數(shù) ，是收斂前迭代的次數(shù)。如果使用密集相似矩陣，其空間復(fù)雜度是。但如果使用稀疏相似性矩陣可以降低空間復(fù)雜度。 這使得Affinity Propagation 算法最適合中小型數(shù)據(jù)集。

示例：

Algorithm description(算法描述): 樣本之間傳遞的信息有兩種。 第一種是吸引信息 (responsibility) , 樣本 適合作為樣本 的聚類中心的程度。第二種是歸屬信息(availability) , 的合適程度。 這樣，選取示例樣本作為聚類中心, 如果 (1) 該樣本與其許多樣本相似，并且 (2) 被許多樣本選擇可以代表他們自己，樣本就會被選擇。

樣本對樣本吸引度計算公式為:

?

其中 是樣本 和樣本 之間的相似度。樣本 作為樣本 的示例樣本的合適程度:

?

算法開始時 和 都被置 0,然后開始迭代計算直到收斂。 為了防止更新數(shù)據(jù)時出現(xiàn)數(shù)據(jù)振蕩，在迭代過程中引入阻尼因子 :

? ?

其中 是迭代的次數(shù)。

2.3.4. Mean Shift

MeanShift 算法目的是在一個平滑的樣本密度中返現(xiàn) blobs 。它是一種基于質(zhì)心的算法，其工作原理是將候選質(zhì)心的位置更新為給定區(qū)域內(nèi)點的平均值。然后在后處理階段對這些候選質(zhì)心位置進(jìn)行篩選，以消除近似重復(fù)，形成最終的質(zhì)心集合。

給定第次迭代中的候選質(zhì)心 , 候選質(zhì)心的位置按照如下公式更新:

?

其中 是圍繞 周圍一個給定距離范圍內(nèi)的樣本鄰域, 是均值偏移向量(mean shift vector), 該向量是所有質(zhì)心中指向點密度增加最多的區(qū)域的偏移向量。使用以下等式計算，有效地將質(zhì)心更新為其鄰域內(nèi)樣本的平均值:

?

該算法自動設(shè)置簇的數(shù)量，而不是依賴參數(shù)bandwidth指示要搜索的區(qū)域大小的參數(shù)。該參數(shù)可以手動設(shè)置，但如果未設(shè)置帶寬，可以使用提供的estimate_bandwidth函數(shù)進(jìn)行估算 。

該算法不是高度可擴(kuò)展的，因為在執(zhí)行該算法時需要進(jìn)行多個最近鄰搜索。該算法保證收斂，但是當(dāng)質(zhì)心的變化較小時，該算法將停止迭代。

通過找到給定樣本的最近質(zhì)心來標(biāo)記新樣本。


示例:

參考文獻(xiàn):

2.3.5. Spectral clustering（譜聚類）

SpectralClustering對樣本之間的關(guān)聯(lián)矩陣執(zhí)行低維嵌入，然后在低維空間中對特征向量的分量進(jìn)行聚類（例如，通過K-Means聚類）。amg求解器用于特征值問題，如果關(guān)聯(lián)矩陣是稀疏的，那么在計算效率會很高。（請注意，amg求解器需要安裝pyamg模塊。）

當(dāng)前版本的SpectralClustering需要預(yù)先指定簇的數(shù)量。它適用于簇數(shù)量少時，簇數(shù)量多時不建議使用。

對于兩個簇，SpectralClustering解決了相似性圖形上歸一化切割問題的凸松弛問題：將圖形切割成兩半，以使所切邊緣的權(quán)重比每個簇內(nèi)邊緣的權(quán)重小。此標(biāo)準(zhǔn)特別有趣：當(dāng)處理圖形的頂點為像素，相似圖形的邊緣是圖像的漸變函數(shù)。



  警告：將距離轉(zhuǎn)換為行為良好的相似性

請注意，如果相似性矩陣的值分布不均，例如具有負(fù)值或距離矩陣并不表示相似性，則 spectral problem 問題將變成奇異的，并且無法解決。在這種情況下，建議對矩陣的 entries 進(jìn)行轉(zhuǎn)換。例如，在有向距離矩陣上應(yīng)用heat kernel:

similarity = np.exp(-beta * distance / distance.std())

請參閱此類應(yīng)用程序的示例。

2.3.5.1. 不同的標(biāo)簽分配策略

SpectralClustering對應(yīng)的assign_labels參數(shù)，可以使用不同的標(biāo)簽分配策略。 "kmeans"可以匹配更詳細(xì)的數(shù)據(jù)信息，但可能不穩(wěn)定。特別是，除非你可以控制random_state,否則它可能無法復(fù)現(xiàn)運行的結(jié)果，因為它取決于隨機(jī)初始化。使用"discretize"策略是100％可復(fù)現(xiàn)的，但往往會創(chuàng)建幾何形狀相當(dāng)均勻的閉合包。


2.3.5.2. 譜聚類圖表

譜聚類還可用于通過其頻譜嵌入對圖形進(jìn)行分區(qū)。在這種情況下，親和度矩陣是圖的鄰接矩陣，并且SpectralClustering可以由affinity='precomputed'進(jìn)行初始化：

>>> from sklearn.cluster import SpectralClustering
>>> sc = SpectralClustering(3, affinity='precomputed', n_init=100,
...                         assign_labels='discretize')
>>> sc.fit_predict(adjacency_matrix)  

參考文獻(xiàn)：

2.3.6. 層次聚類

層次聚類是一種通過連續(xù)合并或拆分內(nèi)置聚類來構(gòu)建最終聚類的聚類算法。聚類的層次結(jié)構(gòu)表示為樹(或樹形圖)。樹的根是所有的樣本中唯一的聚類，葉子是只有一個樣本的集群。有關(guān)更多詳細(xì)信息，請參見Wikipedia頁面。

AgglomerativeClustering使用自下而上的方法執(zhí)行層次聚類：每個觀察都從其自己的聚類開始，并且聚類連續(xù)合并在一起。連接標(biāo)準(zhǔn)確定用于合并策略的度量標(biāo)準(zhǔn)：

  • Ward最小化了所有群集內(nèi)的平方差總和。這是方差最小化的優(yōu)化方法，從這個意義上講，它類似于k均值目標(biāo)函數(shù)的優(yōu)化方法，但采用了凝聚分層的方法。
  • Maximum 或 complete linkage 最小化成對聚類間最遠(yuǎn)樣本的距離。
  • Average linkage 最小化成對聚類間平均樣本的距離值。
  • Single linkage 最小化成對聚類間最近樣本的距離值。

AgglomerativeClustering 在聯(lián)合使用同一個連接矩陣時，也可以擴(kuò)大到大量樣本，但是在樣本之間沒有添加連接約束時，在計算上代價很大:在每一步都要考慮所有可能的合并。

FeatureAgglomeration

FeatureAgglomeration使用凝聚聚類將看上去相似的特征組合在一起，從而減少特征的數(shù)量。它是一個降維工具, 請參閱 無監(jiān)督降維。

2.3.6.1. 不同連接類型: Ward, complete,average and single linkage

AgglomerativeClustering 支持Ward，single, average, 和 complete linkage 策略。


Agglomerative cluster 存在 “rich get richer” 現(xiàn)象，導(dǎo)致聚類大小不均勻。在這方面，Single linkage 是最差的策略，而Ward給出的規(guī)則大小最大。但是， affinity （或聚類中使用的距離）不能隨Ward一起變化，因此對于非歐氏度量，average linkage 是一個很好的選擇。average linkage雖然對嘈雜的數(shù)據(jù)的魯棒性并不強(qiáng)，但是對規(guī)模較大的數(shù)據(jù)集提供了非常有效的層次聚類算法。 Single linkage 同樣對非全局?jǐn)?shù)據(jù)有很好的效果。

示例：

2.3.6.2. 聚類分層結(jié)構(gòu)可視化

可以將表示聚類層次合并的樹可視化為樹狀圖。視覺檢查通常有助于理解數(shù)據(jù)的結(jié)構(gòu)，在小樣本情況下更是如此。


2.3.6.3. 添加連接約束

AgglomerativeClustering的一個有趣的特點是可以通過一個連接矩陣將連接約束添加到該算法中（只能將相鄰的聚類合并在一起），連接矩陣為每個樣本定義了遵循給定數(shù)據(jù)結(jié)構(gòu)的相鄰樣本。例如，在下面的swiss-roll示例中，連接約束禁止合并不相鄰的 swiss roll ，從而避免形成在 roll 上折疊的簇。



這些約束對于強(qiáng)加特定的局部結(jié)構(gòu)是有用的，而且也使算法更快，特別是當(dāng)樣本數(shù)量很大的時候。

連通性約束是通過連通性矩陣施加的：一個稀疏矩陣，其僅在行和列的交點處具有要連接的數(shù)據(jù)集索引。該矩陣可以由先驗信息構(gòu)建：例如，您可能希望僅通過具有指向彼此的鏈接的合并頁面來對web頁面進(jìn)行聚類。也可以從數(shù)據(jù)中得知，例如，sklearn.neighbors.kneighbors_graph，用于限制與最近鄰的合并，如本例所示；或sklearn.feature_extraction.image.grid_to_graph，如coin示例中，用于僅允許合并圖像上的相鄰像素 點。

示例：

警告：single, average and complete linkage的連接約束

single, average and complete linkage的連接約束可以增強(qiáng)聚合聚類中的 ‘rich getting richer’ 現(xiàn)象，尤其是如果他們是用sklearn.neighbors.kneighbors_graph來構(gòu)建時。在少數(shù)簇的限制下，它們傾向于給出一些宏觀上占據(jù)的簇，并且?guī)缀跏强盏拇?。（請參?a rel="external nofollow" target="_blank" rel="external nofollow" target="_blank" rel="external nofollow" target="_blank" rel="external nofollow" target="_blank" style="text-decoration: none; color: #1e6bb8; word-wrap: break-word; font-weight: bold; border-bottom: 1px solid #1e6bb8;">帶結(jié)構(gòu)和無結(jié)構(gòu)的凝聚聚類的討論 ）。就此問題而言，single是最脆弱的linkage選項。





2.3.6.4. Varying the metric

Single, verage and complete linkage 可以使用各種距離 (or affinities), 特別是歐氏距離 (l2), 曼哈頓距離（Manhattan distance）(or Cityblock, or l1), 余弦距離(cosine distance), 或者任何預(yù)先計算的關(guān)聯(lián)矩陣(affinity matrix).

  • l1 距離有利于稀疏特征或者稀疏噪聲: 例如很多特征都是0，就像在文本挖掘中使用出現(xiàn)的稀有單詞一樣。
  • 余弦距離很有趣，因為它對信號的全局縮放是不變的。

選擇度量標(biāo)準(zhǔn)的知道原則是使得不同類樣本之間距離最大化，并且最小化同類樣本之間的距離




示例：

2.3.7. DBSCAN

該DBSCAN算法將簇視為低密度區(qū)域?qū)⒏呙芏葏^(qū)域分隔開。由于這種相當(dāng)通用的觀點，DBSCAN發(fā)現(xiàn)的簇可以是任何形狀，而k-均值假定簇是凸形的。DBSCAN的核心組件是core samples，即高密度區(qū)域中的樣本。因此，一個簇是一組核心樣本，每個樣本彼此接近（通過某種距離度量來衡量），以及一組與核心樣本接近（但本身不是核心樣本）的非核心樣本。該算法有兩個參數(shù)， min_samples和eps，它們正式定義了我們說稠密 （dense）時的含義。更高的min_samples或更低的eps 都表示形成簇所需的更高密度。

更正式地說，我們將核心樣本定義為數(shù)據(jù)集中的一個樣本的 eps 距離范圍內(nèi)的min_samples其他樣本，以便在距離內(nèi)存在其他樣本eps，這些樣本被定義為核心樣本的鄰居。這告訴我們核心樣本位于向量空間的稠密區(qū)域。 簇中還具有一組非核心樣本，它們是簇中核心樣本的鄰居的樣本，但本身并不是核心樣本。 顯然，這些樣本位于簇的邊緣。

根據(jù)定義，任何核心樣本都是簇的一部分，任何不是核心樣本并且和任意一個核心樣本距離都大于eps 的樣本將被視為異常值。

參數(shù)min_samples 主要控制算法對噪聲的容忍度(當(dāng)處理大型噪聲數(shù)據(jù)集時, 需要考慮增加該參數(shù)的值), 如何選擇適當(dāng)?shù)?code style="font-size: 14px; word-wrap: break-word; padding: 2px 4px; border-radius: 4px; margin: 0 2px; color: #1e6bb8; background-color: rgba(27,31,35,.05); font-family: Operator Mono, Consolas, Monaco, Menlo, monospace; word-break: break-all;">eps 對具體地數(shù)據(jù)集和距離函數(shù)非常關(guān)鍵，通常不能使用默認(rèn)值。參數(shù)eps控制了點地領(lǐng)域范圍。如果取值太小,大多數(shù)數(shù)據(jù)并不會被聚類(并將“噪音”標(biāo)記為-1); 如果取值太大，可能會導(dǎo)致相近的多個簇被合并成一個,并最終將整個數(shù)據(jù)集分配到單個簇返回。文獻(xiàn)上已經(jīng)討論過了一些啟發(fā)式（heuristics）參數(shù)選擇方法。例如，在最近鄰距離圖種，基于Knee的參數(shù)選擇方式（如下面的參考文獻(xiàn)中所討論的）。

在下圖中，顏色表示簇成員屬性，大圓圈表示算法找到的核心樣本。較小的圓圈表示仍是簇的一部分的非核心樣本。 此外，下面的黑點表示異常值。


示例:

實現(xiàn)

DBSCAN 算法是確定性的，當(dāng)以相同的順序給出相同的數(shù)據(jù)時總是形成相同的簇。 然而，當(dāng)以不同的順序提供數(shù)據(jù)時,結(jié)果可能不相同。首先，盡管核心樣本總是被分配給相同的簇，但這些簇的標(biāo)簽將取決于數(shù)據(jù)中遇到這些樣本的順序。其次，更重要的是，分配給非核心樣本的簇可能因數(shù)據(jù)順序而有所不同。 當(dāng)一個非核心樣本到兩個不同簇的核心樣本的距離都小于 eps 時，就會發(fā)生這種情況。 根據(jù)三角不等式，這兩個核心樣本距離必須大于 eps ，否則他們將處于同一個簇中。 非核心樣本將被分配給在數(shù)據(jù)傳遞過程中首先生成的任何簇，因此結(jié)果也將取決于數(shù)據(jù)排序。

當(dāng)前版本使用 ball trees 和 kd-trees 來確定點的領(lǐng)域，從而避免了計算完整的距離矩陣 （就像在0.14之前的scikit-learn版本中所做的那樣）。保留使用自定義指標(biāo)(custom metrics)的可能性。更多細(xì)節(jié)請參照 NearestNeighbors。

在大規(guī)模樣本上運行時的內(nèi)存消耗

這個實現(xiàn)在默認(rèn)情況下內(nèi)存效率不高，因為在不能使用 kd-trees 或 ball-trees 的情況下情況下構(gòu)建一個完整的相似度矩陣（例如，使用稀疏矩陣情況下）。這個矩陣會消耗n2個浮點數(shù)。 解決這個問題的幾種機(jī)制:

  • 使用 OPTICS 聚類算法結(jié)合 extract_dbscan 方式。 OPTICS 聚類算法同樣需要計算全結(jié)對矩陣(full pairwise matrix)，但每次僅在內(nèi)存中保持一行(內(nèi)存復(fù)雜度為 n)。
  • 稀疏半徑鄰域圖(A sparse radius neighborhood graph)(其中缺少的樣本被假定為距離超出eps) 可以以高效的方式預(yù)先編譯，并且可以使用 metric='precomputed' 來運行 dbscan。
  • 可以對數(shù)據(jù)集進(jìn)行壓縮，當(dāng)數(shù)據(jù)中存在準(zhǔn)確的重復(fù)時，可以刪除這些重復(fù)的數(shù)據(jù)，或者使用BIRCH。 那么對于大量的點僅需要使用相對少量的樣本。然后在訓(xùn)練DBSCAN時，可以提供一個sample_weight 參數(shù)。

參考文獻(xiàn)：

  • “A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise” Ester, M., H. P. Kriegel, J. Sander, and X. Xu, In Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining, Portland, OR, AAAI Press, pp. 226–231. 1996
  • “DBSCAN revisited, revisited: why and how you should (still) use DBSCAN. Schubert, E., Sander, J., Ester, M., Kriegel, H. P., & Xu, X. (2017). In ACM Transactions on Database Systems (TODS), 42(3), 19.

2.3.8. OPTICS

OPTICS算法與DBSCAN算法有許多相似之處，可以認(rèn)為是DBSCAN算法的推廣，將eps要求從一個值放寬到一個值范圍。OPTICS與DBSCAN的只要區(qū)別在于OPTICS算法建立了一個可達(dá)性圖，它為每個樣本分配了一個reachability_距離(可達(dá)性距離)和一個簇ordering_屬性中的點;擬合模型時會分配這兩個屬性，用于確定簇的成員關(guān)系。如果運行OPTICS時max_eps設(shè)置為默認(rèn)值inf，則可以使用cluster_optics_dbscan方法對任意給定的eps值在線性時間內(nèi)針對任何給定值重復(fù)執(zhí)行DBSCAN樣式的簇提取。將max_eps設(shè)置為較低的值將縮短運行時間，并可以視為從每個點開始尋找其他可能的可到達(dá)點的最大鄰域半徑。


OPTICS生成的可達(dá)性距離允許在單個數(shù)據(jù)集中進(jìn)行可變密度的簇提取。如上圖所示，將可達(dá)性距離和數(shù)據(jù)集ordering_結(jié)合生成可達(dá)性圖，其中點密度在Y軸上表示，并且對點進(jìn)行排序以使附近的點相鄰。在單個值處“切割”可達(dá)性圖會產(chǎn)生類似DBSCAN的結(jié)果; “切割”上方的所有點都會被歸類為噪聲，每次從左到右讀取時都表示新的簇。使用OPTICS進(jìn)行默認(rèn)的簇提取時，會查看圖中的陡峭斜率以查找簇，用戶可以使用參數(shù)xi定義什么算作陡峭斜率。還可以對圖形本身進(jìn)行其他分析，例如通過可達(dá)性圖樹狀圖生成數(shù)據(jù)的層次表示，并且可以通過cluster_hierarchy_參數(shù)訪問算法檢測到的聚類的層次。上面的圖已經(jīng)過顏色編碼，因此平面空間中的簇顏色與可達(dá)性圖的線性段簇匹配。請注意，藍(lán)色和紅色群集在可達(dá)性圖中相鄰，可以分層次地表示為較大父簇的子簇。

示例:

與DBSCAN相比

OPTICS cluster_optics_dbscan方法和DBSCAN的結(jié)果非常相似，但并不總是相同; 具體而言，是在標(biāo)記離群點和噪聲點方面。這部分是因為由OPTICS處理的每個密集區(qū)域的第一個樣本具有大的可達(dá)性值，使得接近其區(qū)域中的其他點，因此有時將被標(biāo)記為噪聲而不是離群點。當(dāng)它們被視為被標(biāo)記為離群點或噪聲的候選點時，這會影響相鄰點的判斷。

請注意，對于任何單個值eps，DBSCAN的運行時間往往比OPTICS短; 但是，對于不同eps 值的重復(fù)運行，單次運行OPTICS可能需要比DBSCAN更少的累積運行時間。同樣重要的是要注意的是OPTICS的輸出接近DBSCAN的只有eps和max_eps接近。

計算復(fù)雜度

采用空間索引樹以避免計算整個距離矩陣，并允許在大量樣本上有效地使用內(nèi)存?？梢酝ㄟ^metric關(guān)鍵字提供不同的距離度量。

對于大型數(shù)據(jù)集，可以通過HDBSCAN獲得類似（但不相同）的結(jié)果 。HDBSCAN實現(xiàn)是多線程的，并且具有比OPTICS更好的算法運行時間復(fù)雜性，代價是更高的內(nèi)存代價。對于使用HDBSCAN將耗盡系統(tǒng)內(nèi)存的極大數(shù)據(jù)集，OPTICS將維持n（而不是n^2）內(nèi)存縮放; 然而，可能需要使用max_eps參數(shù)的調(diào)優(yōu)來在合理的時間內(nèi)給出解。

參考文獻(xiàn)：

  • “OPTICS: ordering points to identify the clustering structure.” Ankerst, Mihael, Markus M. Breunig, Hans-Peter Kriegel, and J?rg Sander. In ACM Sigmod Record, vol. 28, no. 2, pp. 49-60. ACM, 1999.

2.3.9. Birch

該Birch為給定數(shù)據(jù)構(gòu)建了一個稱為聚類特征樹 (CFT)的樹。數(shù)據(jù)本質(zhì)上是被有損壓縮到一組“聚類特征”節(jié)點（CF Nodes）上。CF Nodes 具有許多稱為聚類特征的子簇（CF Subclusters），并且位于非終端位置的 CF 子簇可以將 CF 節(jié)點作為子節(jié)點。

CF Subclusters 保存了用于簇的必要信息，從而避免了將整個輸入數(shù)據(jù)保存在內(nèi)存中。這些信息包括：

  • 子簇中的樣本數(shù)。
  • Linear Sum - 包含所有樣本和的n維向量
  • Squared Sum - 所有樣本的L2范數(shù)的平方和。
  • Centroids - 為避免重復(fù)計算 linear sum / n_samples。
  • 質(zhì)心的 Squared norm。

Birch 算法有兩個參數(shù)，閾值和分支因子。分支因子限制了節(jié)點中子簇的數(shù)量，而閾值則限制了新輸入樣本與現(xiàn)有子簇之間的距離。

該算法可以視為一種實例或?qū)?shù)據(jù)簡化的方法，因為它將輸入數(shù)據(jù)簡化為一組直接從CFT葉子結(jié)點中獲取的一組子簇。被簡化的數(shù)據(jù)可以通過將其集合到全局簇 (global clusterer) 來進(jìn)一步處理?？梢酝ㄟ^n_clusters來設(shè)置global clusterer)。如果n_clusters設(shè)置為 “none”，則直接讀取葉子節(jié)點中的子簇，否則全局聚類步驟會將這些子簇標(biāo)記為全局簇（標(biāo)簽），然后將樣本映射到最近的子簇的全局簇的標(biāo)簽。

算法描述:

  • 一個新的樣本被插入到CF樹的根也就是CF節(jié)點中。然后與根的子簇合并，合并后的子簇半徑最小，受閾值和分支因子的約束。如果子簇有任何子節(jié)點，則重復(fù)執(zhí)行此操作直到到達(dá)葉子節(jié)點。在葉子節(jié)點中找到最近的子簇之后，將遞歸地更新這個子簇和父簇的屬性。
  • 如果通過合并新樣本和最近的子簇得到的子簇的半徑大于閾值的平方，并且子簇的數(shù)量大于分支因子，那么將臨時為這個新樣本分配一個空間。取兩個最遠(yuǎn)的子簇，根據(jù)子簇之間的距離將子簇分為兩組。
  • 如果拆分的節(jié)點有一個父子簇(parent subcluster)，并且還有空間足夠容納一個新的子簇，那么父簇會拆分成兩個。如果沒有空間容納一個新的簇，那么這個節(jié)點將被再次一分為二，然后遞歸進(jìn)行這個過程，直到到達(dá)根節(jié)點。

Birch or MiniBatchKMeans?

  • Birch 不能很好的擴(kuò)展到高維數(shù)據(jù)。根據(jù)經(jīng)驗，如果 n_features 大于20，通常使用 MiniBatchKMeans 更好。
  • 如果需要減少數(shù)據(jù)樣本的數(shù)量，或者如果需要大量的子聚類作為預(yù)處理步驟或者其他， 那么Birch 比 MiniBatchKMeans 更有用。

How to use partial_fit?

為了避免對 global clustering 的計算，每次調(diào)用 partial_fit，建議進(jìn)行如下操作:

  1. 初始化 n_clusters=None 。
  2. 通過多次調(diào)用 partial_fit 訓(xùn)練所有數(shù)據(jù)。
  3. 通過使用 brc.set_params(n_clusters=n_clusters) ,設(shè)置 n_clusters 為必需值。
  4. 最后調(diào)用無參的 partial_fit , 即 brc.partial_fit() 執(zhí)行全局聚類。

參考資料：

  • Tian Zhang, Raghu Ramakrishnan, Maron Livny BIRCH: An efficient data clustering method for large databases. https://www.cs.sfu.ca/CourseCentral/459/han/papers/zhang96.pdf
  • Roberto Perdisci JBirch - Java implementation of BIRCH clustering algorithm https://code.google.com/archive/p/jbirch

2.3.10. 聚類性能度量

評估聚類算法的性能并不像統(tǒng)計錯誤數(shù)量或計算監(jiān)督分類算法的準(zhǔn)確率和召回率那么簡單。特別是任何度量指標(biāo)不應(yīng)考慮簇標(biāo)簽的絕對值，而是如果這個聚類方式分離的數(shù)據(jù)類似與一些真實類或滿足某些假設(shè),這樣在同于一個相似性度量下,屬于同一個類內(nèi)的成員比不同類的成員更加類似。

2.3.10.1. 調(diào)整后的蘭德指數(shù)

已知真實簇標(biāo)簽分配 labels_true 和我們的聚類算法是基于相同樣本所得到的 labels_pred，**調(diào)整后的蘭德指數(shù)是一個函數(shù)，它測量兩個簇標(biāo)簽分配的值的 **相似度 ，忽略排列(permutations)和 機(jī)會歸一化（chance normalization）:

>>> from sklearn import metrics
>>> labels_true = [0, 0, 0, 1, 1, 1]
>>> labels_pred = [0, 0, 1, 1, 2, 2]

>>> metrics.adjusted_rand_score(labels_true, labels_pred)
0.24...

在預(yù)測的標(biāo)簽列表中重新排列 0 和 1, 把 2 重命名為 3, 得到相同的得分:

>>> labels_pred = [1, 1, 0, 0, 3, 3]
>>> metrics.adjusted_rand_score(labels_true, labels_pred)
0.24...

此外， adjusted_rand_score 是 對稱的(symmetric) : 交換參數(shù)不會改變得分。它可以作為一種 共識度量(consensus measure):

>>> metrics.adjusted_rand_score(labels_pred, labels_true)
0.24...

完美標(biāo)簽的得分為1.0：

>>> labels_pred = labels_true[:]
>>> metrics.adjusted_rand_score(labels_true, labels_pred)
1.0

不良標(biāo)簽 (e.g. 獨立標(biāo)簽（independent labelings）) 的得分是負(fù)數(shù)或接近于0.0：

>>> labels_true = [0, 1, 2, 0, 3, 4, 5, 1]
>>> labels_pred = [1, 1, 0, 0, 2, 2, 2, 2]
>>> metrics.adjusted_rand_score(labels_true, labels_pred)
-0.12...

2.3.10.1.1. 優(yōu)點

  • 對于 n_clusters 和 n_samples 的任何值，（隨機(jī)（統(tǒng)一）標(biāo)簽分配的 ARI 得分接近于 0.0）（這并不適用于原始的 Rand index 或者 V-measure 的情況）。
  • Bounded range（有界范圍） [-1, 1]: 負(fù)值是不良標(biāo)簽的得分, 類似的聚類結(jié)果有一個正的 ARI 值， 1.0 是完美的匹配得分。
  • 沒有對簇的結(jié)構(gòu)作任何假設(shè)（No assumption is made on the cluster structure）: 可以用于比較聚類算法，如: k-means 的簇是 isotropic blob shapes, 譜聚類算法的簇是 folded shapes。

2.3.10.1.2. 缺點

  • 與慣性相反，**ARI需要了解真實簇信息，**而在實踐中幾乎是不可用的，或者需要人工標(biāo)注者手動分配（如在監(jiān)督學(xué)習(xí)環(huán)境中）。

    但是，

示例：

2.3.10.1.3. 數(shù)學(xué)表達(dá)

如果 C 是一個真實簇的標(biāo)簽分配， K 是簇的個數(shù)，定義 和 為:

  • ，在 C 中的相同集合與 K 中的相同集合中的元素對數(shù)
  • ，在 C 中的不同集合與 K 中的不同集合中的元素對數(shù)

原始（未排序）的 蘭德指數(shù) 由下式給出:

其中 是數(shù)據(jù)集中可能的數(shù)據(jù)對總數(shù)（未排序）。

然而，RI評分并不能保證隨機(jī)標(biāo)簽分配會得到接近于零的值(特別是，如果簇的數(shù)量與樣本數(shù)量具有相同的數(shù)量級)。

為了抵消這種影響，我們可以通過定義 adjusted Rand index 來低估(discount)隨機(jī)標(biāo)簽的預(yù)期 RI

,如下所示:

參考資料：

2.3.10.2. 基于互信息(mutual information)的得分

已知真實簇的標(biāo)簽分配 labels_true 和我們的聚類算法基于相同樣本所得到的 labels_pred， 互信息 是度量兩個標(biāo)簽分配的 一致性的函數(shù)，忽略排列。這種度量方案有兩個不同的歸一化版本，Normalized Mutual Information(NMI) 和 Adjusted Mutual Information(AMI)。NMI 經(jīng)常在文獻(xiàn)中使用，而 AMI 最近才提出的，并且 隨偶然性而歸一化（normalized against chance） :

>>> from sklearn import metrics
>>> labels_true = [0, 0, 0, 1, 1, 1]
>>> labels_pred = [0, 0, 1, 1, 2, 2]

>>> metrics.adjusted_mutual_info_score(labels_true, labels_pred)  
0.22504...

在預(yù)測的標(biāo)簽列表中重新排列 0 和 1, 把 2 重命名為 3, 得到相同的得分:

>>> labels_pred = [1, 1, 0, 0, 3, 3]
>>> metrics.adjusted_mutual_info_score(labels_true, labels_pred)  
0.22504...

全部的， mutual_info_score, adjusted_mutual_info_score 和 normalized_mutual_info_score 是對稱的: 交換參數(shù)不會更改得分。因此，它們可以用作共識度量（consensus measure）：

>>> metrics.adjusted_mutual_info_score(labels_pred, labels_true)  
0.22504...

完美標(biāo)簽得分是 1.0:

>>> labels_pred = labels_true[:]
>>> metrics.adjusted_mutual_info_score(labels_true, labels_pred)  
1.0

>>> metrics.normalized_mutual_info_score(labels_true, labels_pred)  
1.0

而 mutual_info_score不是這樣，因為它更難判斷：

>>> metrics.mutual_info_score(labels_true, labels_pred)  
0.69...

不良標(biāo)簽 (例如（無相關(guān)標(biāo)簽）independent labelings) 具有非正分?jǐn)?shù)：

>>> labels_true = [0, 1, 2, 0, 3, 4, 5, 1]
>>> labels_pred = [1, 1, 0, 0, 2, 2, 2, 2]
>>> metrics.adjusted_mutual_info_score(labels_true, labels_pred)  
-0.10526...

2.3.10.2.1. 優(yōu)點

  • Random (uniform) label assignments have a AMI score close to 0.0（隨機(jī)（統(tǒng)一）標(biāo)簽分配的AMI評分接近0.0） 適用于 n_clusters 和 n_samples 取任何值（這不適用于原始 Rand index 或 V-measure 的情況）。
  • Upper Bound of 1（上界1） 數(shù)值趨近 0 說明兩個標(biāo)簽分配之間是獨立的；而數(shù)值趨近于 1 時, 表示兩者顯著一致。 此外，如果AMI的取值恰好是 1 時, 說明兩個標(biāo)簽分配是完全相等的(無論是否排列過)。

2.3.10.2.2. 缺點

  • 與慣量相反，MI-based measures 需要先得知 ground truth classes ，而在實踐中幾乎從來沒有使用過，或者需要人工標(biāo)注者手動分配（如在監(jiān)督學(xué)習(xí)環(huán)境中）。

    然而，基于 MI 的測量方式(MI-based measures)也可在完全無監(jiān)督的情況下作為聚類模型選擇過程中共識索引的一個構(gòu)建模塊。

  • NMI 和 MI 不能進(jìn)行使得隨機(jī)標(biāo)簽度量的得分為0的調(diào)整。

示例：

2.3.10.2.3. 數(shù)學(xué)公式

假設(shè)兩個標(biāo)簽分配（在相同的 N 個對象中進(jìn)行）, 和 。 它們的熵是一個分區(qū)集合的不確定性量，被定義為:

其中： 是從 中選取的對象，選取對象落入類 的概率。同樣對于:

采用 ， 和 之間的mutual information (MI) 由下式計算:

其中 是隨機(jī)選擇的對象同時落入兩個類的概率 和

也可以用設(shè)定的基數(shù)表達(dá)式表示:

normalized mutual可以定義為：

mutual information 的值以及歸一化變量的值都不會隨著隨機(jī)標(biāo)簽度量進(jìn)行調(diào)整，但是會隨著不同的簇標(biāo)簽數(shù)量的增加而增加，不管標(biāo)簽分配之間的 “mutual information” 的實際數(shù)量是多少。

可以用以下公式[VEB2009]來計算 mutual information 的期望值。在這個方程式中 ， 中元素的數(shù)量) 和 (中元素的數(shù)量).

使用期望值，然后可以使用與調(diào)整后的蘭德指數(shù)相似的形式來計算調(diào)整后的mutual information:

對于歸一化互信息和調(diào)整互信息，歸一化值通常是每個聚類熵的某個廣義均值。存在在各種廣義的手段，并且不存在一種確定的規(guī)則確定某種方法優(yōu)于其他方法。這個決定很大程度上根據(jù)不同領(lǐng)域有不同方法;例如，在社區(qū)檢測算法（Community Detection）中，算術(shù)平均是最為常見。每一種歸一化方法都提供了定性相似行為（qualitatively similar behaviours）[YAT2016]。在我們的實現(xiàn)中，這由average_method參數(shù)控制的。

Vinh等(2010)用平均法命名NMI和AMI的變體[VEB2010]。它們的“ sqrt”和“ sum”平均值是幾何和算術(shù)平均值;我們使用這些更廣泛的通用名稱。

參考文獻(xiàn)：

2.3.10.3. 同質(zhì)性，完整性和 V-measure

已知真實簇的標(biāo)簽分配，可以使用條件熵(conditional entropy)分析定義一些直觀的度量（intuitive metric）。

特別是 Rosenberg 和 Hirschberg (2007) 為任何簇的分配定義了以下兩個理想的目標(biāo):

  • 同質(zhì)性(homogeneity): 每個簇只包含一個類的成員
  • 完整性(completeness): 給定類的所有成員都分配給同一個簇。

我們可以把這些概念轉(zhuǎn)化為得分 homogeneity_score 和 completeness_score 。兩者均在 0.0 以下 和 1.0 以上（越高越好）:

>>> from sklearn import metrics
>>> labels_true = [0, 0, 0, 1, 1, 1]
>>> labels_pred = [0, 0, 1, 1, 2, 2]

>>> metrics.homogeneity_score(labels_true, labels_pred)
0.66...
>>> metrics.completeness_score(labels_true, labels_pred)
0.42...

稱為 V-measure 的調(diào)和平均數(shù)由 v_measure_score計算得出：

>>> metrics.v_measure_score(labels_true, labels_pred)
0.51...

該函數(shù)的公式如下：

beta 默認(rèn)為1.0，但對于beta小于1時，為：

>>> metrics.v_measure_score(labels_true, labels_pred, beta=0.6)
0.54...

更大的beta權(quán)重將提高同質(zhì)性，當(dāng)使用大于1的beta值時:

>>> metrics.v_measure_score(labels_true, labels_pred, beta=1.8)
0.48...

更大的beta權(quán)重將提高完整性。

V-measure 實際上等價于上面討論的 mutual information (NMI) , 僅聚合函數(shù)（aggregation function）是算術(shù)均值[B2011]。

同質(zhì)性, 完整性 和 V-measure 可以使用 homogeneity_completeness_v_measure進(jìn)行計算，計算方法如下:

>>> metrics.homogeneity_completeness_v_measure(labels_true, labels_pred)
...                                                      
(0.66..., 0.42..., 0.51...)

以下聚類分配稍微好一些，因為它是同質(zhì)但并不完整:

>>> labels_pred = [0, 0, 0, 1, 2, 2]
>>> metrics.homogeneity_completeness_v_measure(labels_true, labels_pred)
(1.0, 0.68..., 0.81...)

注意：

v_measure_score是對稱的：可用于評估同一數(shù)據(jù)集上兩個獨立的標(biāo)簽分配。

completeness_score和homogeneity_score 的情況并非如此：兩者都受以下關(guān)系約束：

homogeneity_score(a, b) == completeness_score(b, a)

2.3.10.3.1. 優(yōu)點

  • Bounded scores（有界分?jǐn)?shù)）: 0.0 是最壞的, 1.0 是一個完美的分?jǐn)?shù).
  • 直觀解釋: 具有不良 V-measure 的聚類可以用 在同質(zhì)性和完整性方面進(jìn)行定性分析 ，以更好地感知到標(biāo)簽分配所造成的“錯誤”類型。
  • No assumption is made on the cluster structure（對簇的結(jié)構(gòu)沒有作出任何假設(shè)）: 可以用于比較不同類的聚類算法，例如: k-means 和 spectral clustering algorithms（譜聚類算法）間的比較。雖然，前者的簇是isotropic blob shapes, 后者的簇是 folded shapes。

2.3.10.3.2. 缺點

  • 先前引入的度量標(biāo)準(zhǔn)并不針對隨機(jī)標(biāo)記進(jìn)行標(biāo)準(zhǔn)化: 這意味著，根據(jù)樣本數(shù)量，簇數(shù)量和標(biāo)定過的真實數(shù)據(jù)類數(shù)量，完全隨機(jī)的標(biāo)注方式并不總是產(chǎn)生同質(zhì)性，完整性 和 v-measure 的相同值。特別是特別是當(dāng)簇數(shù)量很大時，隨機(jī)標(biāo)記不會產(chǎn)生零分。

    當(dāng)樣本數(shù)量超過 1000且簇的數(shù)量小于 10 時，可以安全地忽略此問題。對于較小的樣本數(shù)量或者較大數(shù)量的簇，使用 adjusted index （例如 Adjusted Rand Index (ARI)）。


這，而實踐中卻幾乎不可用，或者需要或需要人工標(biāo)注者人工分配（如在受監(jiān)督的學(xué)習(xí)環(huán)境中）。

示例：
聚類表現(xiàn)評估中的機(jī)會調(diào): 分析數(shù)據(jù)集大小對隨機(jī)分配聚類度量值的影響。

2.3.10.3.3. 數(shù)學(xué)表達(dá)

同質(zhì)性和完整性的得分由下面公式給出:

其中是給定簇分配的類的條件熵 ，由下式給出:

是 已聚合的類的熵 (entropy of the classes)，并且由下式給出:

個樣本總數(shù)， 和 分別屬于 類 和 簇 的樣本數(shù)，最后 分配給 簇 的類， 的樣本數(shù)。

給定類分配的簇的條件熵（conditional entropy of clusters given class） 和 簇的熵 以對稱的形式 義。

Rosenberg 和 Hirschberg 進(jìn)一步定義 V-measure 作為 同質(zhì)性和完整性的調(diào)和均值:

參考資料

2.3.10.4. Fowlkes-Mallows 得分

當(dāng)已標(biāo)定樣本的真實類分配已知時，可以使用 Fowlkes-Mallows 指數(shù) (sklearn.metrics.fowlkes_mallows_score) 。Fowlkes-Mallows 得分 FMI 被定義為 成對的準(zhǔn)確率和召回率的幾何平均值:

其中 TP 是 真正例(True Positive) 的數(shù)量（即真標(biāo)簽組和預(yù)測標(biāo)簽組中屬于相同簇的點對數(shù)），FP 是 假正例(False Positive) （即不在預(yù)測標(biāo)簽組，僅在真標(biāo)簽組中屬于同一簇的點對數(shù)），FN 是 假負(fù)例(False Negative) 的數(shù)量（即不在真實標(biāo)簽組中，僅在預(yù)測標(biāo)簽組中屬于同一簇的點對數(shù)）。

得分范圍為 0 到 1。較高的值表示兩個簇之間的良好相似性。

>>> from sklearn import metrics
>>> labels_true = [0, 0, 0, 1, 1, 1]
>>> labels_pred = [0, 0, 1, 1, 2, 2]Copy
>>> metrics.fowlkes_mallows_score(labels_true, labels_pred)  
0.47140...Copy

在預(yù)測的標(biāo)簽列表中重新排列 0 和 1, 把 2 重命名為 3, 得到相同的得分:

>>> labels_pred = [1, 1, 0, 0, 3, 3]

>>> metrics.fowlkes_mallows_score(labels_true, labels_pred)  
0.47140...Copy

完美的標(biāo)簽得分是 1.0:

>>> labels_pred = labels_true[:]
>>> metrics.fowlkes_mallows_score(labels_true, labels_pred)  
1.0Copy

不良標(biāo)簽（例如,無相關(guān)標(biāo)簽）的得分為 0:

>>> labels_true = [0, 1, 2, 0, 3, 4, 5, 1]
>>> labels_pred = [1, 1, 0, 0, 2, 2, 2, 2]
>>> metrics.fowlkes_mallows_score(labels_true, labels_pred)  
0.0

2.3.10.4.1. 優(yōu)點

  • 隨機(jī)（統(tǒng)一）標(biāo)簽分配的FMI評分接近0.0） 適用于 n_clusters 和 n_samples 取任何值（但并不適用于原始的Rand index 或 V-measure ）。
  • Upper Bound of 1: 數(shù)值趨近于0 ，是說明兩個標(biāo)簽分配在很大程度上是獨立的；而數(shù)值趨近于 1 時, 表示兩者之間有著極高的相似度。 甚至，當(dāng)FMI的取值正好是 1 時, 表示兩個標(biāo)簽分配是完全相等的(無論是否排列)。
  • 沒有對簇的結(jié)構(gòu)作出任何假設(shè)）: 可以用于比較不同類的聚類算法，例如: k-means 和 spectral clustering algorithms（譜聚類算法）間的比較。k-means的簇是isotropic blob shapes, 譜聚類算法的簇是 folded shapes。

2.3.10.4.2. 缺點

  • 與慣量相反，基于 FMI 的測量方案需要已標(biāo)注的真數(shù)據(jù)類 ，而在實踐中幾乎不可用，或者需要人工標(biāo)注者手動分配（在監(jiān)督學(xué)習(xí)學(xué)習(xí)環(huán)境中）。

參考資料

  • E. B. Fowkles and C. L. Mallows, 1983. “A method for comparing two hierarchical clusterings”. Journal of the American Statistical Association. http://wildfire.stat.ucla.edu/pdflibrary/fowlkes.pdf
  • Wikipedia entry for the Fowlkes-Mallows Index

2.3.10.5. Silhouette 系數(shù)

如果真實簇標(biāo)簽不知道，則必須使用模型本身進(jìn)行度量。Silhouette 系數(shù) (sklearn.metrics.silhouette_score) 這種度量的一個示例，其中較高的 Silhouette 系數(shù)得分和具有更好定義的聚類的模型有關(guān)。Silhouette 系數(shù)根據(jù)每個樣本進(jìn)行定義，由兩個得分組成:

  • a: 樣本與同一類別中所有其他點之間的平均距離。
  • b: 樣本與 下一個距離最近的簇中的所有其他點之間的平均距離。

給出單個樣本的 Silhouette 系數(shù) s :

其中每個樣本的 Silhouette 系數(shù)的平均值可以使用一組樣本的 Silhouette 系數(shù)。

>>> from sklearn import metrics
>>> from sklearn.metrics import pairwise_distances
>>> from sklearn import datasets
>>> X, y = datasets.load_iris(return_X_y=True)

在正常使用情況下，將 Silhouette 系數(shù)應(yīng)用于聚類結(jié)果的分析。

>>> import numpy as np
>>> from sklearn.cluster import KMeans
>>> kmeans_model = KMeans(n_clusters=3, random_state=1).fit(X)
>>> labels = kmeans_model.labels_
>>> metrics.silhouette_score(X, labels, metric='euclidean')
0.55...

參考資料：

  • Peter J. Rousseeuw (1987). “Silhouettes: a Graphical Aid to the Interpretation and Validation of Cluster Analysis”. Computational and Applied Mathematics 20: 53–65. doi:10.1016/0377-0427(87)90125-7.

2.3.10.5.1. 優(yōu)點

  • 不正確的聚類得分為 -1 ，高密度聚類得分為 +1 。0 附近的分?jǐn)?shù)表示重疊的聚類。
  • 當(dāng)簇密集且分離良好時，得分較高，這與簇的標(biāo)準(zhǔn)概念有關(guān)。

2.3.10.5.2. 缺點

  • 凸簇的 Silhouette 系數(shù)通常比其他類型的簇更高，如使用DBSCAN 獲得的基于密度的簇。

示例:

2.3.10.6. Calinski-Harabaz 指數(shù)

當(dāng)不知道真實簇標(biāo)簽時，可使用 Calinski-Harabaz 指數(shù) (sklearn.metrics.calinski_harabaz_score)（也稱為方差比準(zhǔn)則）來評估模型，其中較高的 Calinski-Harabaz 得分和能夠更好定義的聚類模型有關(guān)。

該指數(shù)是通過簇間色散平均值(between-clusters dispersion mean)與簇內(nèi)色散之間(within-cluster dispersion)的比值給出的（其中，離散度定義為距離平方的總和）：

>>> from sklearn import metrics
>>> from sklearn.metrics import pairwise_distances
>>> from sklearn import datasets
>>> X, y = datasets.load_iris(return_X_y=True)

在正常使用中，將 Calinski-Harabasz 指數(shù)應(yīng)用于聚類分析的結(jié)果：

>>> import numpy as np
>>> from sklearn.cluster import KMeans
>>> kmeans_model = KMeans(n_clusters=3, random_state=1).fit(X)
>>> labels = kmeans_model.labels_
>>> metrics.calinski_harabasz_score(X, labels)
561.62...

2.3.10.6.1. 優(yōu)點

  • 當(dāng)群集密集且分隔良好時，分?jǐn)?shù)會更高，這與群集的標(biāo)準(zhǔn)概念有關(guān)。
  • 分?jǐn)?shù)計算迅速。

2.3.10.6.2. 缺點

  • 凸形群集的Calinski-Harabasz索引通常比其他群集概念更高，例如通過DBSCAN獲得的基于密度的群集。

2.3.10.6.3. 數(shù)學(xué)公式

對于 簇，Calinski-Harabaz 得分 是通過簇間色散平均值(between-clusters dispersion mean)與 簇內(nèi)色散之間(within-cluster dispersion)的比值給出的:

其中 是組間色散矩陣(between group dispersion matrix)， 是簇內(nèi)色散矩陣(within-cluster dispersion matrix):

為簇 中的點集， 為簇 的中心， 為 的中心， 為簇 中的點數(shù)。

參考文獻(xiàn)

2.3.10.7. Davies-Bouldin Index

如果不知道真實簇標(biāo)簽，則可以使用Davies-Bouldin指數(shù)sklearn.metrics.davies_bouldin_score度量模型，其中較低的Davies-Bouldin指數(shù)與具有更好簇間分割表現(xiàn)的模型。

該指數(shù)表示簇之間的平均“相似度”，其中相似度是將簇之間的距離與簇本身的大小進(jìn)行比較的度量。

零是最低的分?jǐn)?shù)。值越接近零表示更好的分割。

在正常使用中，將Davies-Bouldin索引應(yīng)用于簇分析的結(jié)果，如下所示：

>>> from sklearn import datasets
>>> iris = datasets.load_iris()
>>> X = iris.data
>>> from sklearn.cluster import KMeans
>>> from sklearn.metrics import davies_bouldin_score
>>> kmeans = KMeans(n_clusters=3, random_state=1).fit(X)
>>> labels = kmeans.labels_
>>> davies_bouldin_score(X, labels)
0.6619...

2.3.10.7.1. 優(yōu)點

  • BDI 的計算比 Silhouette scores 要簡單。
  • 該索引只計算數(shù)據(jù)集固有的數(shù)量和特征。

2.3.10.7.2. 缺點

  • 凸簇(convex clusters)的 DBI 通常比其他類型的簇更高，例如通過 DBSCAN 獲得的基于密度的簇。
  • 在一般情況下, 質(zhì)心距離只能使用歐氏空間內(nèi)的距離度量來衡量。

2.3.10.7.3. 數(shù)學(xué)公式

該指數(shù)被定義為每個簇 ()和它的最大相似度 之間的平均相似度，在該指數(shù)的上下文里，：

  • , 簇 內(nèi)每個點和簇心的平均距離 -- 也稱簇直徑。

  • , 簇質(zhì)心 和 之間的距離。

    以下是一個簡單構(gòu)建 的方法，使得它具有非負(fù)性和對稱性:

    然后將Davies-Bouldin索引定義為：

參考文獻(xiàn)

2.3.10.8. Contingency Matrix

列聯(lián)矩陣（Contingency Matrix）(sklearn.metrics.cluster.contingency_matrix) 記錄了每個真實/預(yù)測簇對之間的交叉基數(shù)。 列聯(lián)矩陣為所有的聚類度量提供了足夠的統(tǒng)計數(shù)據(jù)，在這些度量中樣本都是獨立和均勻分布的，不需要考慮某些未聚類的樣本。

這是一個例子：

>>> from sklearn.metrics.cluster import contingency_matrix
>>> x = ["a", "a", "a", "b", "b", "b"]
>>> y = [0, 0, 1, 1, 2, 2]
>>> contingency_matrix(x, y)
array([[2, 1, 0],
       [0, 1, 2]])

輸出數(shù)組的第一行指示存在三個樣本的真實簇是''a''。其中兩個的預(yù)測簇是 0，一個是 1， 沒有一個是 2。而第二行表示有三個樣本的真實簇是‘’b‘’ 。 其中，沒有一個樣本的預(yù)測簇是 0, 一個是 1, 兩個是 2。

用于分類的混淆矩陣(confusion matrix) 是平方列矩陣，其中行和列的順序?qū)?yīng)于類別列表。

2.3.10.8.1. 優(yōu)點

  • 允許檢查每個真實簇在預(yù)測簇中的分布，反之亦然。
  • 計算列聯(lián)矩陣通常利用了兩個聚類之間的相似性統(tǒng)計數(shù)據(jù)（如本文檔中列出的其他相似性統(tǒng)計信息）。

2.3.10.8.2. 缺點

  • 列聯(lián)矩陣很容易解釋小數(shù)量的簇，但對于數(shù)量較大的簇則很難解釋。

  • 沒有給出一個單一的指標(biāo)來做聚類優(yōu)化。

  • 參考文獻(xiàn)


以上內(nèi)容是否對您有幫助：
在線筆記
App下載
App下載

掃描二維碼

下載編程獅App

公眾號
微信公眾號

編程獅公眾號