可以使用模塊sklearn.cluster對未標記的數據進行聚類。每個聚類算法都有兩種變體：一個是類(class)實現的?fit方法來學習訓練數據上的聚類；另一個是函數(function)實現，給定訓練數據，返回不同聚類對應的整數標簽數組。對于類，可以在?labels_屬性中找到訓練數據上的標簽。輸入數據需要注意的一點是，該模塊中實現的算法可以將不同類型的矩陣作為輸入。所有方法都接受形狀為?[n_samples, n_features]的標準數據矩陣。這些可以從sklearn.feature_extraction模塊的類中獲取。對于仿射投影(AffinityPropagation),?譜聚類(SpectralClustering)和?DBSCAN，還可以輸入形狀為[n_samples, n_samples]的相似矩陣。這些可以從sklearn.metrics.pairwise模塊中的函數獲得。

1. 聚類方法綜述

當簇具有特定形狀(即非平坦流形)且標準歐氏距離不是正確的度量方法時，非平坦幾何聚類(Non-flat geometry clustering)很有用。這種情況出現在上圖的兩個頂行中。用于聚類的高斯混合模型在文檔的另一章節中專門進行了描述。KMeans可以看作是每一個分量的協方差都相等的高斯混合模型的一個特例。

2. K-means

KMeans算法通過嘗試在n組等方差的樣本中分離樣本來對數據進行聚類，最小化稱為慣量(inertia)或簇內平方和(within-cluster sum-of-squares)的標準(見下文)。此算法要求指定簇的數量。它可以很好地擴展到大量的樣本，已在許多不同領域得到了廣泛應用。k-means算法將一組N個樣本X劃分為k個不相交的簇C，每個簇用該簇中樣本的平均來描述。這些均值(means )通常被稱為簇的“質心”("centroids")，請注意，它們通常不是X的點，盡管它們位于同一空間。K-means算法的目標是選擇質心使慣量(inertia)或簇內平方和(within-cluster sum-of-squares)最小化：慣量(inertia)可以被認為是衡量簇與簇之間相關性的指標。它有各種缺點：

• 慣量(inertia)假設集群是凸(convex )的且各向同性(isotropic)，但并非總是如此。它對細長的簇或形狀不規則的流形簇反應很差。
• 慣量(inertia)不是一個標準化的指標：我們只知道較低的值更好，零是最佳值，但是在非常高維的空間中，歐幾里德距離趨于膨脹(inflated)(這是所謂的“維數災難”的一個例子)。在進行k-means聚類之前運行如主成分分析(PCA)等降維算法可以緩解這一問題，并加快計算速度。

K-means常被稱為Lloyd算法。基本上，該算法有三個步驟。第一步選擇初始質心，最基本的方法是從數據集X中選擇k個樣本作為初始化質心。初始化后，k-means由其余兩個步驟之間的循環組成。第一步將每個樣本分配到其最近的質心。第二步通過取分配給前一個質心的所有樣本的平均值來創建新質心。計算舊質心和新質心之間的差異值，算法重復這兩步，直到該值小于閾值。換句話說，它會重復，直到質心不明顯移動為止。K-means等價于期望最大化算法(expectation-maximization algorithm)，其協方差矩陣較小且均相等。該算法也可以通過 Voronoi 圖的概念來理解。首先利用當前質心計算點的Voronoi 圖。Voronoi圖中的每一段(segment)都成為一個獨立的簇。其次，將質心更新為每段(segment)的平均值。然后，算法重復此操作，直到滿足停止條件。通常，當迭代期間，目標函數的相對減少量小于給定的公差值(tolerance value)時，算法停止。在kmeans中，當質心的移動小于公差(tolerance)時，迭代停止。給定足夠的時間，K-means將最終收斂(converge)，但這可能是一個局部極小值。這在很大程度上取決于質心的初始化。因此，計算通常要進行多次，每次對質心進行不同的初始化。解決這個問題的一種方法是k-means++初始化方案，它已經在scikit-learn中實現(使用?init='k-means++'參數)。如參考文獻中所示，這會將質心初始化為(通常)彼此距離較遠，從而產生比隨機初始化更好的結果。該算法支持樣本加權，樣本權重可以由?sample_weight參數給出。這允許在計算簇中心和慣性值時為一些樣本分配更多的權重。例如，為一個樣本指定2的權重相當于將該樣本的副本添加到數據集X。可以給出一個允許K-means并行運行的參數，稱為n_jobs。給這個參數賦予一個正值，表示使用指定數量的處理器(默認值：1)。值-1表示使用所有可用的處理器，-2表示使用所有可用處理器數量減一個的數量處理器，依此類推。并行化通常以消耗內存為代價加快計算速度(在這種情況下，需要存儲多個質心副本，每個作業(job)一個副本)。**警告：**當numpy使用Accelerate(加速)框架時，K-Means的并行版本在OS X上被破壞。可以在fork之后調用?Accelerate，但您需要使用Python二進制文件執行子進程(在posix下，多進程不執行此操作)。K-means可用于矢量量化(vector quantization)。這是使用KMeans訓練模型的轉換方法(transform method)實現的。示例：

• k-均值假設的演示: 直觀演示k-均值何時執行，何時不執行
• 在手寫數字數據集上進行K-Means聚類的演示: 對手寫數字進行聚類

參考文獻：

• “k-means++: The advantages of careful seeding”?Arthur, David, and Sergei Vassilvitskii,?Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, Society for Industrial and Applied Mathematics (2007)

2.1.小批量 (Mini Batch) K-Means

MiniBatchKMeans是KMeans算法的一個變種，它使用小批量(mini-batches)來減少計算時間，同時仍然試圖優化相同的目標函數。小批量是輸入數據的子集，在每次訓練迭代中隨機抽樣。這些小批量極大地減少了收斂到局部解所需的計算量。與其他減少k-means收斂時間的算法相比，小批量k-means算法的結果通常只比標準算法稍差。該算法在兩個主要步驟之間迭代，類似于vanilla k-means。在第一步中，從數據集中隨機抽取b個樣本，形成一個小批量。然后這些樣本被分配到最近的質心。在第二步中，質心被更新。與k-means不同的是，k-means是在每個樣本(per-sample)的基礎上完成的。對于小批量中的每個樣本，通過獲取該樣本和分配給該質心的所有先前樣本的流平均值來更新指定的質心，這會降低質心隨時間的變化率。執行這些步驟直到收斂或達到預定的迭代次數。MiniBatchKMeans的收斂速度比KMeans快，但結果的質量會降低。在實踐中，這種質量差異可以很小，如示例和引用的參考文獻所示。示例：

• 比較K-Means和MiniBatchKMeans聚類算法: 比較KMeans和MiniBatchKMeans
• 使用k-means對文本文檔進行聚類: 使用稀疏MiniBatchKMeans對文檔進行聚類
• 在線學習面部表情字典

參考文獻：

• “Web Scale K-Means clustering”?D. Sculley,?Proceedings of the 19th international conference on World wide web?(2010)

3. 親和力傳播(Affinity Propagation)

AffinityPropagation通過在樣本對之間發送消息直到收斂來創建簇(clusters)，然后使用少量的示例來描述數據集，這些示例被標識為最具代表性的其他示例。在樣本對之間發送的消息表示一個樣本作為另一個樣本的范例樣本的合適程度，合適程度值根據其他樣本對的值進行迭代更新，直到收斂，完成最終聚類中心的選取，從而給出最終的聚類。親和力傳播(Affinity Propagation)可能很有趣，因為它根據提供的數據選擇簇的數量。為此，兩個重要的參數是preference?(控制使用的示例數量)和?damping factor(阻尼因子，該參數阻尼責任和可用性消息，以避免在更新這些消息時出現數值振蕩(numerical oscillations))。親和傳播的主要缺點是其復雜性。該算法的時間復雜度為，其中N為樣本數，T為收斂前的迭代次數。此外，如果使用稠密相似矩陣，則空間復雜度為，但如果使用稀疏相似矩陣，則空間復雜度可降低。這使得親和力傳播更適合于中小型數據集。示例：

• 親和力傳播聚類算法演示: 3類合成二維數據集上的親和力傳播。
• 在金融時間序列上可視化股市結構?親和力傳播，以發現公司群(groups of companies)。

算法描述：點之間發送的消息屬于兩個類別之一。第一個是責任(responsibility )r(i,k)，是樣本k應該是樣本i的模范樣本(exemplar)的合適程度；第二個是可用性(availability )a(i,k)，是樣本i應該選擇樣本k作為模范樣本的合適程度，并考慮所有其他樣本選取樣本k作為模范樣本的合適程度。這樣，如果樣本(1)與多個樣本足夠相似，并且(2)該樣本被多個樣本選擇以代表它們自己，則此樣本被選為模范樣本。更正式地說，樣本k作為樣本i的模范樣本的responsibility由以下公式進行計算：其中s(i,k)是樣本i和k之間的相似性(similarity)。樣本k作為樣本i的模范樣本的可用性(availability)由下式給出：首先，r和a的所有值都設置為零，并且每次迭代的計算都會一直進行直到收斂。如上所述，為了在更新消息時避免數值振蕩(numerical oscillations)，將阻尼因子(damping factor)λ引入迭代過程：其中t表示迭代次數。

4. 平均位移(Mean Shift)

MeanShift聚類的目的是在光滑的樣本密度中發現斑點(blobs)。這是一種基于質心的算法，其工作原理是將質心的候選值更新為給定區域內點的平均值。然后，在后處理階段對這些候選對象進行過濾，以消除近重復項(near-duplicates)，形成最終的質心集。給定第t次迭代的候選質心，根據下列方程更新候選：其中是附近給定距離內的樣本鄰域，m是針對每個質心計算的“平均移動(mean shift)”矢量，而每個質心都指向點密度最大增加的區域。這是使用以下公式計算的，有效地將質心更新為其鄰域內樣本的平均值：該算法自動設置簇的數量，而不是依賴于參數bandwidth，該參數決定了要搜索的區域的大小。此參數可以手動設置，但可以使用提供的estimate_bandwidth函數進行估計，如果未設置參數bandwidth，則調用此函數。該算法的可擴展性不高，因為在算法執行過程中需要多次近鄰搜索。該算法當質心變化較小時，算法將停止迭代。通過找到給定樣本的最近質心來標記新樣本。示例：

• mean-shift聚類算法演示：3類合成2D數據集上的 Mean Shift 聚類。

參考文獻：

• “Mean shift: A robust approach toward feature space analysis.”?D. Comaniciu and P. Meer,?IEEE Transactions on Pattern Analysis and Machine Intelligence?(2002)

5. 譜聚類(Spectral clustering)

SpectralClustering (譜聚類)在樣本之間執行親和力矩陣(affinity matrix)的低維嵌入，然后在低維空間中對特征向量的分量進行聚類(例如，通過KMeans)。如果親和力矩陣是稀疏的，并且amg求解器用于特征值問題(注意，amg解算器要求安裝pyamg模塊)，那么計算將會非常高效。當前版本的譜聚類要求預先指定簇的數量。它在簇比較少的情況下運行良好，但在簇比較多的情況下不建議使用。對于兩個簇，譜聚類解決了相似圖上歸一化切割的凸松弛問題：將圖一分為二，使得切割的邊緣權重比簇內邊緣權重小。當處理圖像時，這個標準特別有趣，其中圖形頂點是像素，并且使用圖像的梯度函數計算相似度圖的邊權重。警告：?將距離轉化為表現良好的相似性請注意，如果相似度矩陣的值分布不均勻，例如使用負值或使用距離矩陣而不是相似度，則譜問題將(spectral problem)是奇異的(singular)，并且該問題無法解決。在這種情況下，建議對矩陣的條目(entries)進行轉換。例如，在有符號距離矩陣的情況下，應用熱核(heat kernel)：similarity = np.exp(-beta * distance / distance.std())

請參閱此類應用程序的示例。

示例：

• 將譜聚類用于圖像分割：使用譜聚類從噪聲背景中分割對象。
• 分割區域內的希臘硬幣圖像：使用譜聚類分割區域內的硬幣圖像。

5.1. 不同的標簽分配策略(Different label assignment strategies)

可以使用不同的標簽分配策略，相對應SpectralClustering的assign_labels參數。"kmeans"的策略可以匹配更精細的細節，但可能不穩定。特別是，除非您控制random_state，否則它可能無法從一次運行復現到另一次運行，因為它取決于隨機初始化值。另一種"discretize"策略是100%可復現的，但往往會產生相當均勻和幾何形狀的塊(parcels)。

5.2. 譜聚類圖(Spectral Clustering Graphs)

譜聚類(Spectral Clustering)也可以通過譜嵌入來劃分圖。在這種情況下，親和矩陣(affinity matrix)是圖的鄰接矩陣(adjacency matrix)，譜聚類(SpectralClustering )使用affinity='precomputed'進行初始化：>>> from sklearn.cluster import SpectralClustering>>> sc = SpectralClustering(3, affinity='precomputed', n_init=100,... assign_labels='discretize')>>> sc.fit_predict(adjacency_matrix)參考文獻：

• “A Tutorial on Spectral Clustering”?Ulrike von Luxburg, 2007
• “Normalized cuts and image segmentation”?Jianbo Shi, Jitendra Malik, 2000
• “A Random Walks View of Spectral Segmentation”?Marina Meila, Jianbo Shi, 2001
• “On Spectral Clustering: Analysis and an algorithm”?Andrew Y. Ng, Michael I. Jordan, Yair Weiss, 2001
• “Preconditioned Spectral Clustering for Stochastic Block Partition Streaming Graph Challenge”?David Zhuzhunashvili, Andrew Knyazev

6. 層次聚類(Hierarchical clustering)

層次聚類(Hierarchical clustering)是一類常用的聚類算法，它通過連續合并或拆分嵌套聚類(nested clusters)來構建嵌套聚類。簇的層次結構表示為樹(或樹狀圖(dendrogram))。樹根是收集所有樣本的唯一簇，葉子是只有一個樣本的簇。請參閱維基百科頁面了解更多詳細信息。AgglomerativeClustering(凝聚聚類)對象使用自底向上的方法執行分層聚類：每個觀察值是一個聚類，簇被連續地合并在一起。鏈接標準(linkage criteria)確定用于合并策略的度量：

• Ward最小化所有簇內的平方差之和。這是一種方差最小化(variance-minimizing)方法，在這個意義上類似于k-means目標函數，但使用聚集層次法(agglomerative hierarchical approach)進行處理。
• Maximum或complete linkage最小化成對簇中樣本間的最大距離。
• Average linkage最小化成對簇中所有樣本之間的平均距離。
• Single linkage最小化成對簇中最近樣本之間的距離。

當它與連通矩陣(connectivity matrix)一起使用時，AgglomerativeClustering(凝聚聚類)也可以擴展到大規模的樣本中，但是當樣本之間不添加連通約束時，計算代價很高：它在每一步都考慮所有可能的合并。FeatureAgglomeration(特征聚集)FeatureAgglomeration(特征聚集)使用凝聚聚類方法(agglomerative clustering )將看起來非常相似的特征組合在一起，從而減少特征的數量。它是一個降維工具，參見無監督降維。

6.1. Different linkage type: Ward, complete, average, and single linkage

AgglomerativeClustering(凝聚聚類)支持Ward, single, average, 和 complete linkage 策略。凝聚凝聚聚集聚類具有“富變更富(rich get richer)”的行為，導致簇大小不均勻。在這方面，single linkage 是最差的策略，而 Ward 給出了最規則的尺寸。然而，親和力(affinity)(或聚類中使用的距離)不能隨Ward而變化，因此對于非歐氏度量， average linkage是一個很好的選擇。Single linkage雖然對噪聲數據不魯棒，但可以非常有效地計算，因此可以用于提供更大數據集的層次聚類。Single linkage也可以在非球形(non-globular)數據上表現良好。示例：

• 二維數字嵌入上的各種凝聚聚類算法：在真實數據集中探索不同的 linkage 策略。

6.2. 集群層次結構的可視化(Visualization of cluster hierarchy)

可以將表示簇層次合并(hierarchical merging of clusters)的樹可視化為樹狀圖(dendrogram)。可視化通常有助于理解數據的結構，在小樣本情況下更是如此。

6.3. 添加連接約束(Adding connectivity constraints)

AgglomerativeClustering(凝聚聚類)的一個有趣的方面是，連接約束(connectivity constraints)可以通過一個連接矩陣(connectivity matrix)添加到該算法中(只有相鄰的簇可以合并在一起)，該連接矩陣為每個樣本定義了遵循給定數據結構的相鄰樣本。例如，在下面的swiss-roll示例中，連接約束禁止合并不在swiss roll上相鄰的點，從而避免形成跨越 roll 的重復折疊的簇。這些約束有助于施加一定的局部結構，同時也使算法更快，特別是在樣本數較多的情況下。連接性約束(connectivity constraints)是通過一個連接性矩陣(connectivity matrix)施加的：一個scipy稀疏矩陣，它只在一行和一列的交集處有元素，而這些行和列記錄著應該被連接的數據集索引。這個矩陣可以由先驗信息(a-priori information)構造：例如，您可能希望只合并從一個指向另一個的鏈接網頁來對網頁進行聚類。它也可以從數據中學習，例如使用sklearn.neighbors.kneighbors_graph將合并限制為最近的鄰居(如本例)，或使用?sklearn.feature_extraction.image.grid_to_graph啟用圖像上相鄰像素的合并(如?硬幣?示例)。示例：

• 在硬幣圖像上結構化Ward分層聚類的演示：Ward聚類用于在區域中分割硬幣圖像。
• 層次聚類：結構化與非結構化ward：swiss roll上的ward算法示例，結構化方法與非結構化方法的比較。
• 特征聚集與單變量選擇：基于Ward層次聚類的特征聚集降維實例。
• 有無結構的聚集聚類

警告：single, average and complete linkage的連通性約束連接性約束和單一、完全或平均的連接可以增強凝聚聚類的 ‘rich getting richer’現象，特別是在它們用?sklearn.neighbors.kneighbors_graph構建時。在少數簇的限制下，它們傾向于給出一些宏觀上占據的簇(occupied clusters)和幾乎為空的簇(empty clusters)。(見有無結構的凝聚聚類中的討論)。在這個問題上，Single linkage是最脆弱的 linkage 選擇。

6.4. 改變度量(Varying the metric)

Single, average 和 complete linkage可以與各種距離(或仿射(affinities))一起使用，特別是歐幾里德距離(l2)、曼哈頓距離(或Cityblock或 l1)、余弦距離或任何預先計算的仿射矩陣(affinity matrix)。

• l1?距離通常有利于稀疏特征或稀疏噪聲：即許多特征為零，就如在文本挖掘中使用稀有詞(rare words)一樣。
• 余弦?距離很有趣，因為它對信號的全局標度不變。

選擇度量的準則是使用一個最大化不同類中樣本之間的距離，并最小化每個類中樣本之間的距離。示例：

• 使用不同指標的聚集聚類

7. DBSCAN

DBSCAN算法將簇視為被低密度區域分隔的高密度區域。由于這個相當普遍的觀點，DBSCAN發現的集群可以是任何形狀，而k-means假設集群是凸形的(convex shaped)。DBSCAN的核心部分是核心樣本?的概念，核心樣本位于高密度區域。因此，一個簇是一組核心樣本，每個樣本彼此靠近(通過某種距離度量方法進行測量)和一組靠近核心樣本(但本身不是核心樣本)的非核心樣本。該算法有兩個參數，min_samples和?eps，它們正式定義了稠密?的含義。較大的?min_samples或較小的?eps表示形成簇所需的較高密度。更正式地說，我們將核心樣本定義為數據集中的一個樣本，使得在eps的一段距離范圍內存在min_samples個其他樣本，這些樣本被定義為核心樣本的鄰居。這告訴我們核心樣本在向量空間的密集區域。一個簇是一組核心樣本，可以通過遞歸地獲取核心樣本、查找鄰居中的所有核心樣本、查找新獲取的核心樣本的所有鄰居中的所有核心樣本等方式來構建。一個簇還會有一組非核心樣本，這些樣本是簇中核心樣本的鄰居，但它們本身不是核心樣本。直觀地說，這些樣本位于一個簇的邊緣。根據定義，任何核心樣本都是簇的一部分。該算法將非核心樣本，且與核心樣本的距離至少為?eps的樣本視為離群值(outlier)。雖然參數min_samples主要控制算法對噪聲的容忍程度(在有噪聲和較大數據集上，可能需要增加此參數)，但參數min_samples對于數據集和距離函數的適當選擇至關重要，并且通常不能保留默認值。它控制點的局部鄰域。當選擇的值太小時，大多數數據根本不會被聚類(并標記為-1表示“噪聲”)。當選擇的值太大時，它會導致相近的聚類合并到一個簇中，并最終將整個數據集作為單個簇返回。文獻中已經討論了一些選擇該參數的啟發式(heuristics)方法，例如基于最近鄰距離圖中的knee(如下面的參考文獻中所討論)。在下圖中，顏色表示簇成員屬性，大圓圈表示算法找到的核心樣本。較小的圓是簇的一部分的非核心樣本。此外，離群值(outliers)用下面的黑點表示。示例：

• DBSCAN聚類算法演示

實現DBSCAN算法是確定性的，當以相同的順序給定相同的數據時，總是生成相同的集群。但是，當以不同的順序提供數據時，結果可能會有所不同。首先，即使核心樣本始終分配給同一個簇，這些簇的標簽將取決于在數據中遇到這些樣本的順序。第二，更重要的是，非核心樣本被分配到的集群可以根據數據順序而不同。當非核心樣本與不同簇中的兩個核心樣本之間的距離小于eps時，就會發生這種情況。根據三角不等式，這兩個核樣本之間的距離必須大于eps，否則它們將在同一個簇中。非核心樣本被分配給在數據傳遞過程中首先生成的集群，因此結果將取決于數據順序。This implementation is by default not memory efficient because it constructs a full pairwise similarity matrix in the case where kd-trees or ball-trees cannot be used (e.g., with sparse matrices). This matrix will consume n^2 floats. A couple of mechanisms for getting around this are:當前的實現使用 ball-trees 和 kd-trees 來確定點的鄰域，這避免了計算全距離矩陣(full distance matrix)(如0.14之前的scikit-learn版本中所實現的)。保留使用自定義度量(custom metrics)的可能性；有關詳細信息，請參閱NearestNeighbors。大樣本的內存消耗默認情況下，此實現是在無法使用 ball-trees 或 kd-trees (例如，使用稀疏矩陣)的情況下構造完整的成對相似矩陣(full pairwise similarity matrix)，因此，該實現內存利用率低。這個矩陣將消耗n^2個浮點數。解決這一問題的兩種機制是：

• 將?OPTICS?聚類與?extract_dbscan?方法結合使用。OPTICS聚類計算完整的成對矩陣(pairwise matrix)，但一次只在內存中保留一行(內存復雜性n)。
• 稀疏半徑鄰域圖(其中丟失的條目被認為是eps之外的)可以以節省內存的方式進行預編譯(precomputed)，可以使用metric='precomputed'運行dbscan。請參見sklearn.neighbors.NearestNeighbors.radius_neighbors_graph。
• 數據集可以壓縮和刪除數據中出現的完全重復的數據，或者使用BIRCH。之后你可以只用相對少量的樣本代表大量的點。您可以在擬合 DBSCAN 時提供?sample_weight參數。

參考文獻：

• “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.

8. OPTICS

OPTICS算法與?DBSCAN算法有許多相似之處，可以認為是DBSCAN的一個推廣，DBSCAN 將eps需求從單個值放寬到一個值范圍。DBSCAN與OPTICS的關鍵區別在于，OPTICS算法建立了一個*可達(reachability)*圖，該圖為每個樣本分配了一個reachability_距離和一個簇-?ordering_屬性內的點；這兩個屬性是在模型擬合時分配的，用于確定簇成員。如果OPTICS運行時的?inf?默認值設置為max_eps，則可以使用cluster_optics_dbscan方法在線性時間內對任何給定的?eps值重復執行DBSCAN類型的簇提取。將?max_eps設置為較低的值將導致較短的運行時間，并且可以認為是從每個點距離其他潛在可達點的最大鄰域半徑(maximum neighborhood radius)。OPTICS 產生的可達(reachability)距離允許在單個數據集中對簇進行可變密度提取。如上圖所示，結合可達距離和數據集ordering_屬性，生成可達性圖，其中點密度表示在Y軸上，并按順序排列點，以使附近的點相鄰。在單個值上“切割”可達圖會產生類似DBSCAN的結果；“切割”上方的所有點都被歸類為噪聲，每次從左到右讀取時出現中斷都表示新的簇。默認使用OPTICS的簇提取會查看圖中的陡坡(steep slopes)來查找簇，用戶可以使用參數xi定義什么是陡坡。對圖本身的分析也有其他的可能性，例如通過可達圖的樹狀圖來生成數據的層次表示，并且該算法檢測到的簇的層次可以通過?cluster_hierarchy_參數來訪問。上面的圖已經進行了顏色編碼(color-coded)，使得平面空間中(planar space)的簇顏色與可達圖的線性段簇(linear segment clusters)相匹配。請注意，藍色和紅色簇在可達圖中相鄰，并且可以分層表示為較大父簇的子簇。示例：

• OPTICS 聚類算法演示

與DBSCAN比較：OPTICS的?cluster_optics_dbscan方法和DBSCAN 的結果非常相似，但并不總是完全相同，具體地說，是在標記離群點和噪聲點(periphery and noise points)方面。這部分是因為OPTICS 處理的每個密集區域的第一個樣本在接近其區域中的其他點時具有很大的可達值，因此有時會標記為噪聲點而不是離群點(periphery)。當相鄰點被視為可標記為離群點(periphery)或噪聲點的候選點時，這會影響相鄰點。注意，對于eps的任何單個值，DBSCAN 的運行時間往往比 OPTICS 短，但是在不同eps值下重復運行，單個OPTICS運行所需的累計運行時間可能比DBSCAN少。還需要注意的是，只有當?eps和?max_eps接近時，OPTICS的輸出才接近DBSCAN。計算復雜度：空間索引樹(Spatial indexing trees)用于避免計算全距離矩陣(full distance matrix)，并允許在大樣本集上高效使用內存。可以通過metric關鍵字提供不同的距離度量。對于大型數據集，可以通過HDBSCAN獲得相似(但不完全相同)的結果。HDBSCAN實現是多線程的，與OPTICS相比具有更好的算法運行復雜度，但代價是內存擴展性較差。對于使用HDBSCAN耗盡系統內存的超大數據集，OPTICS 將保持n(而不是)的內存縮放，但是可能需要調整?max_eps參數，以便在合理的時間內給出解決方案。參考文獻：

• “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.

9. Birch

Birch為給定的數據構建了一種名為聚類特征樹(Clustering Feature Tree，簡稱CFT)的樹。數據本質上是有損壓縮到一組聚類特征節點(Clustering Feature nodes，即CF Nodes)。CF Nodes 有許聚類特征子簇(Clustering Feature subclusters，即CF subclusters)，這些位于非終端CF Nodes中的CF subclusters可以將CF Nodes作為子結點。CF子簇保存簇的必要信息，從而避免將整個輸入數據保存在內存中。這些信息包括：

• 子簇中的樣本數。
• 線性和-包含所有樣本總和的n維向量
• 平方和-所有樣本的L2范數的平方和。
• 質心-避免重新計算線性和(或n_samples)。
• 質心的平方范數。

Birch算法有兩個參數：閾值(threshold )和分支因子(branching factor)。分支因子限制節點中的子簇數量，閾值限制輸入樣本與現有子簇之間的距離。該算法可以看作是一種實例或數據簡化方法，因為它將輸入數據簡化為一組直接從CFT的葉子中獲得的子簇。這樣減少的數據可以通過將其輸入全局聚類簇(global clusterer)來進一步處理。這個全局聚類器可以通過n_clusters參數來設置。如果將n_clusters設置為None，則直接讀取葉中的子簇，否則全局聚類步驟會將這些子簇標記為全局簇(標簽)，并將樣本映射到最近子簇的全局標簽。算法描述:

• 一個新的樣本被插入到作為CF節點(CF Node)的CF樹(CF Tree)根中，然后將其與根的子簇合并，該子簇在合并后具有最小的半徑，并受閾值和分支因子(hreshold and branching factor)條件的約束。如果子集群有任何子節點，則重復此操作，直到它到達葉。在葉中找到最近的子簇后，遞歸更新此子簇和父子簇的屬性。
• 如果通過合并新樣本和最近的子簇而獲得的子簇半徑大于閾值的平方，并且如果子簇的數量大于分支因子，則臨時為該新樣本分配空間。取兩個最遠的子簇，根據這些子簇之間的距離將子簇分為兩組。
• 如果此分割節點有父子簇(parent subcluster)，并且有空間容納新的子簇，則父簇被分割為兩個。如果沒有空間，則該節點再次被分成兩個，并遞歸地繼續該過程，直到到達根節點。

Birch 還是 MiniBatchKMeans?

• Birch不能很好地適應高維數據。根據經驗，如果?n_features?大于20，通常最好使用MiniBatchKMeans。
• 如果需要減少數據實例的數量，或者需要大量子簇作為預處理步驟或其他步驟，那么Birch比MiniBatchKMeans更有用。

如何使用 partial_fit?為了避免全局聚類(global clustering)的計算，建議用戶每次調用partial_fit

初始設置n_clusters=None。

通過多次調用 partial_fit 來訓練所有數據。

使用brc.set_params(n_clusters=n_clusters)將?n_clusters設置為所需值。

最后調用不帶參數的partial_fit，即brc.partial_fit()，它執行全局聚類。

參考文獻：

• 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

10. 聚類算法性能評估

評估聚類算法的性能并不像計算錯誤數或監督分類算法的精確度和召回率那樣簡單。特別是，任何評估指標都不應該考慮聚類標簽的絕對值，而應考慮到該聚類定義的數據分離類似于某些類的真實標簽或滿足某些假設(例如，根據某些相似性指標來看，屬于同一類的成員應該比屬于不同類的成員要更相似)。

10.1. Adjusted Rand index

真實類分配(ground truth class assignments)：labels_true和我們的聚類算法對同樣的樣本集預測出的類分配：labels_pred，adjusted Rand index是一個用來度量上述兩種分配的相似度(similarity)的函數，而忽略排列和歸一化：>>> 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...可以在預測的標簽中排列(permute)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是對稱的：交換參數不會更改得分。因此，它可以作為共識度量(consensus measure)：>>> metrics.adjusted_rand_score(labels_pred, labels_true)0.24...完美標簽得分為1.0：>>> labels_pred = labels_true[:]>>> metrics.adjusted_rand_score(labels_true, labels_pred)1.0壞的標簽(例如獨立標簽)具有負值或接近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...

10.1.1. 優點

• 隨機(均勻)標簽分配的 ARI 得分接近于0.0對于n_clusters和n_samples的任何值(這不是未經過調整的Rand index或者V-measure的情況)。
• 得分被界定在[-1, 1]的區間內：負值是壞的(獨立性標簽)，相似的聚類有一個正的 ARI，1.0是完美的匹配得分。
• 沒有對聚類的結構做任何假定：可以用于比較聚類算法，比如假定了各向同性的“blob”形狀的k-means方法的結果和尋找具有“folded”形狀的譜聚類方法的結果進行比較。

10.1.2. 缺點

• 與慣性(inertia)方法不同，ARI 需要真實類(ground truth classes)的相關前提，而在實踐中幾乎不可得到，或者需要人工手動分配(如在監督學習環境中)。然而，ARI還可以在純粹無監督的設置中作為可用于聚類模型選擇的共識索引的構建模塊。

示例：

• 聚類算法性能評估中的機會調整：分析數據集大小對隨機分配的聚類度量值的影響。

10.1.3. 數學公式

如果C是真實類分配，而K是聚類，讓我們定a和b如下：1.a，在C中相同集合和在K中相同集合的元素對的數量2.b，在C中不同集合和在K中不同集合的元素對的數量原始(未調整的)Rand index如下：其中是在(未排序的)數據集中所有可能的元素對的總數量。然而，RI評分不能保證隨機標簽分配將獲得接近零的值(特別是如果聚類的數量與樣本數量有相同的數量級)。為了抵消這種影響，我們可以通過定義調整后的Rand index(adjusted Rand index，即ARI)來對隨機標簽分配的期望RIE[RI]進行削減(discount)，如下所示：參考文獻

• Comparing Partitions?L. Hubert and P. Arabie, Journal of Classification 1985
• Wikipedia entry for the adjusted Rand index

10.2. 基于互信息的得分

給定真實類的分配：labels_true和我們的聚類算法對同樣的樣本集預測出的類分配：labels_pred，互信息(Mutual Information)是一個函數，用于度量兩個分配集合的一致性，忽略了排列組合。目前可以用這種度量方法的兩個不同的歸一化版本：規范化互信息(Normalized Mutual Information)(NMI)和調整后的互信息(Adjusted Mutual Information)(AMI)。NMI在文獻中可以經常看到，并且針對偶然性進行了標準化：>>> 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...可以在預測出的標簽中排列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都是對稱的：交換函數的參數不會改變得分。因此，它們可以用作共識度量(consensus measure)：>>> metrics.adjusted_mutual_info_score(labels_pred, labels_true) 0.22504...完美標簽分配(Perfect labeling)的得分是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...壞的標簽分配(例如，獨立標簽)具有負的得分：>>> 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...

10.2.1. 優點

• 隨機(均勻)標簽分配有一個接近于0的AMI得分。對于n_clusters和n_samples的任何值(這不是未經過調整的 互信息(Mutual Information)或者V-measure的情況)。
• 上界為1：得分值接近于0表明兩個標簽分配集合很大程度上是獨立的，而得分值接近于1表明兩個標簽分配集合具有很大的一致性。更進一步，正好是1的AMI表示兩個標簽分配相等。(帶有或不帶有排列)。

10.2.2. 缺點

• 與慣性(inertia)方法不同,?基于互信息的度量(MI-based measures)需要真實類的相關知識?而在實踐中幾乎不可得到，或者需要人工手動分配(如在監督學習環境中)。

  然而，基于互信息的度量還可以在純粹無監督的設置中作為可用于聚類模型選擇的共識索引的構建模塊。

• NMI和MI不會機會調整。

示例：

• 聚類算法性能評估中的機會調整：分析數據集大小對隨機分配的聚類度量值的影響。此示例還包括Adjusted Rand Index。

10.2.3. 數學公式

假定我們有兩個標簽分配集合(具有相同N個對象)，U和V。它們的熵是劃分集的不確定性量，定義如下：

其中是從U集合中隨機挑選的一個對象落到集合中的概率。對于V集合也是一樣的：

其中。U和V之間的互信息的計算公式如下：

其中是隨機選擇的對象落到這兩類集合和中的概率。

互信息還可以用集合基數(set cardinality)的形式來表示：

歸一化的互信息定義為

不管兩個標簽分配集合之間的互信息實際量有多大，互信息的值包括歸一化互信息的值沒有針對偶然性進行調整，而且傾向于隨著不同標簽(聚類)數量的增加而增加。

互信息的期望值可以用等式[VEB2009]。在這個等式中，(集合中的元素數量)和(集合中的元素數量)。

使用了互信息期望值后，經過調整的互信息的計算將使用與ARI(adjusted Rand index)類似的形式進行 :

對于歸一化互信息和調整后的互信息，歸一化值通常是每個聚類的熵的某個廣義均值。有各種廣義均值存在，并沒有明確的規則說某一個優先于其他的。這個決定很大程度上是取決于各個領域的基礎；例如，在社區檢測中，算術平均值是最常見的。每一種歸一化方法提供“定性相似的行為(qualitatively similar behaviours)”?[YAT2016]。在我們的實現中，由?average_method參數控制。

Vinh et al. (2010)對各種NMI和AMI的變體用它們使用的平均方法進行了命名[VEB2010]。他們在論文里說的‘sqrt’和‘sum’ 平均分別是幾何和算數平均；我們使用這些更廣泛的通用名稱。

參考文獻

• Strehl, Alexander, and Joydeep Ghosh (2002). “Cluster ensembles – a knowledge reuse framework for combining multiple partitions”. Journal of Machine Learning Research 3: 583–617.?doi:10.1162/153244303321897735.

• Wikipedia entry for the (normalized) Mutual Information

• Wikipedia entry for the Adjusted Mutual Information

• [VEB2009]?Vinh, Epps, and Bailey, (2009). “Information theoretic measures for clusterings comparison”. Proceedings of the 26th Annual International Conference on Machine Learning - ICML ‘09.?doi:10.1145/1553374.1553511. ISBN 9781605585161.

• [VEB2010]?Vinh, Epps, and Bailey, (2010). “Information Theoretic Measures for Clusterings Comparison: Variants, Properties, Normalization and Correction for Chance”. JMLR?http://jmlr.csail.mit.edu/papers/volume11/vinh10a/vinh10a.pdf

• [YAT2016]?Yang, Algesheimer, and Tessone, (2016). “A comparative analysis of community detection algorithms on artificial networks”. Scientific Reports 6: 30750.?doi:10.1038/srep30750.

10.3. 同質性(Homogeneity)，完整性(completeness)和 V-度量(V-measure)

給定樣本的真實類分配的相關知識, 則使用條件熵分析來定義某個直觀的指標(metric)是可能的。特別地，Rosenberg和Hirschberg(2007)為任意聚類分配定義了以下兩個理想的評估指標：

• 同質性(Homogeneity)：每個聚類里面只包含單個類的樣本。
• 完整性(completeness)：一個給定類的所有樣本都被分到了同一個聚類中。

我們可以將上述概念轉化為homogeneity_score和completeness_score函數。這兩個函數的返回值都是介于0到1之間(返回值越高越好)：>>>?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-度量(V-measure)，通過函數v_measure_score來計算：>>>?metrics.v_measure_score(labels_true,?labels_pred)0.51...該函數的公式如下：beta默認值為1.0，但可以給beta傳入小于1的值：>>>?metrics.v_measure_score(labels_true,?labels_pred,?beta=0.6)0.54...更多權重將歸因于同質性，并且給beta傳入大于1的值：>>>?metrics.v_measure_score(labels_true,?labels_pred,?beta=1.8)0.48...更多權重將歸因于完整性。如果使用聚合函數是算術平均值[B2011]，V-度量實際上等效于上面討論的互信息(NMI)。同質性，完備性和V-度量可使用以下方法homogeneity_completeness_v_measure一次性計算出來 ：>>>?metrics.homogeneity_completeness_v_measure(labels_true,?labels_pred)
(0.66...,?0.42...,?0.51...)下面的聚類分配稍微好一點，因為它是同質的，但卻不是完整的:>>>?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是對稱的：可用于評估同一數據集上兩個獨立分配(independent assignments)的一致性。completeness_score和homogeneity_score的情況并非如此：兩者都受以下關系約束：homogeneity_score(a,?b)?==?completeness_score(b,?a)

10.3.1. 優點

• 有界得分：0.0代表最壞的情況，1.0是最完美的得分。
• 直觀可解釋性：具有壞的V-度量值的聚類可以**從同質性和完整性角度進行定性分析(qualitatively analyzed in terms of homogeneity and completeness)**來更好的感受聚類算法預測標簽分配時犯了哪種錯誤。
• 對聚類結構沒有做任何假定：可以用于比較聚類算法，比如假定了各向同性的blob 形狀的k-means方法的結果和尋找具有“folded”形狀的譜聚類方法的結果進行比較。

10.3.2. 缺點

• 以前引入的度量指標并沒有對隨機標記進行標準化?：這意味著，依賴于樣本數量、聚類的數量和真實類的數量，一個完全的隨機標記對于同質性、完備性和v-度量來說并不總是產生相同的值。特別是，隨機標記不會產生零得分，尤其是當簇數很大時。當樣本數大于1000個，聚類的數量小于10個時，可以安全地忽略這個問題。對于較小的樣本大小或較多的聚類數量，使用調整后的索引比如Adjusted Rand Index(ARI)更安全。

v=(1+β)×homogeneity×completeness(β×homogeneity+completeness

• 這些度量指標需要真實類的相關知識，而這些相關知識在實踐中幾乎不可得到，或者需要人工手動分配(如在監督學習環境中)。

示例：

• 聚類性能評估中的機會調整：分析數據集大小對隨機分配的聚類度量值的影響。

10.3.3. 數學公式

同質性和完整性由以下形式正式給出：其中是給定聚類標簽分配以后各個類的條件熵，并且由下式給出：并且H(C)是各個類的熵，并且由下式給出：公式中的n是樣本總量，和分別是屬于類別c和聚類k的樣本的數量，最后是從類別c被分配到聚類k的樣本數量。給定某個類以后簇的條件熵H(K|C)和各個簇的熵H(K)以對稱方式定義。Rosenberg和Hirschberg進一步定義了V-度量作為同質性和完備性的調和均值：參考文獻

• V-Measure: A conditional entropy-based external cluster evaluation measure?Andrew Rosenberg and Julia Hirschberg, 2007
• [B2011]?Identication and Characterization of Events in Social Media, Hila Becker, PhD Thesis.

10.4. Fowlkes-Mallows 得分

當已知樣本的真實類分配時，可以使用Fowlkes-Mallows索引(sklearn.metrics.fowlkes_mallows_score)。Fowlkes-Mallows得分FMI，定義為成對精度(pairwise precision)和成對召回率(pairwise recall)的幾何平均值：其中TP是True Positive的數量(例如，在真實標簽集中和預測標簽集中屬于相同聚類的點對的數量)，FP是False Positive的數量(例如，在真實標簽集中但不在預測標簽集中屬于相同聚類的點對的數量)，FN是False Negative的數量(例如，不在真實標簽集中但在預測標簽集中屬于相同簇的點對的數量)。FMI得分取值范圍在0到1之間。取值越高表明兩個聚類之間的相似性越好。>>>?from?sklearn?import?metrics>>>?labels_true?=?[0,?0,?0,?1,?1,?1]>>>?labels_pred?=?[0,?0,?1,?1,?2,?2]>>>?metrics.fowlkes_mallows_score(labels_true,?labels_pred)0.47140...可以在預測出的標簽中重新排列0和1，將2改為3，并得到相同的得分：>>>?labels_pred?=?[1,?1,?0,?0,?3,?3]>>>?metrics.fowlkes_mallows_score(labels_true,?labels_pred)0.47140...完美標記的得分是1.0：>>>?labels_pred?=?labels_true[:]
>>>?metrics.fowlkes_mallows_score(labels_true,?labels_pred)
1.0壞的標記(例如，獨立標簽)的得分是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

10.4.1. 優點

• 隨機(均勻)標簽分配有一個接近于0的FMI得分。對于n_clusters?和?n_samples?的任何值(這不是未處理的互信息(raw Mutual Information)或者V-度量的情況)。
  • 上界為1：得分值接近于0，表明兩個標簽分配集合很大程度上是獨立的，而得分值接近于1，表明兩個標簽分配集合 具有很大的一致性。更進一步，正好是0的FMI表示兩個標簽分配純粹獨立，正好是1的FMI表示兩個標簽分配相等。(帶有或不帶有排列)。
• 對聚類結構沒有做任何限制：可以用于比較聚類算法，比如假定了各向同性的blob形狀的k-means方法的結果和尋找具有“folded”形狀的譜聚類方法的結果進行比較。

10.4.2. 缺點

• 與慣性方法不同，基于FMI度量需要真實類的相關知識，而這些知識在實踐中幾乎不可得到，或者需要人工手動分配(如在監督學習環境中)。

參考文獻

• 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

10.5. 輪廓系數(Silhouette Coefficient)

如果不知道真實標簽，則必須使用模型本身進行評估。輪廓系數(sklearn.metrics.silhouette_score)就是這樣一種評估的指標，其中較高的輪廓系數得分對應于具有更好的聚類能力的模型。輪廓系數定義在每個樣本上，并且由兩個得分組成：

• a: 在同一個類中一個樣本到所有其他樣本的平均距離。
• b: 在下一個最近的聚類中，一個樣本到所有其他樣本點的平均距離。

對單個樣本來說，輪廓系數s由下式給出：對于一個樣本集合，輪廓系數是集合中每個樣本的輪廓系數的均值。>>> from sklearn import metrics>>> from sklearn.metrics import pairwise_distances>>> from sklearn import datasets>>> X, y = datasets.load_iris(return_X_y=True)在正常使用中，輪廓系數將應用于聚類結果的分析中。>>> 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.

10.5.1. 優點

• 對于高度稠密的聚類，得分被限制在-1和+1之間。得分在0附近表明是有重疊的聚類。
• 當聚類(cluster)密集且分離良好時，得分較高，這與聚類(cluster)的標準概念有關。

10.5.2. 缺點

• 凸形聚類(cluster)的輪廓系數通常比其他聚類(cluster)高，例如，通過DBSCAN獲得的基于密度的聚類(cluster)。

示例：

• 在KMeans聚類上使用輪廓分析選擇聚類數目：在本示例中，輪廓分析用于為n_clusters選擇最佳值。

10.6. Calinski-Harabasz 指數

如果不知道基本真值標簽，則可以使用Calinski-Harabasz指數(sklearn.metrics.calinski_harabasz_score)來評估模型，其中較高的Calinski-Harabasz分數與具有更好定義的簇的模型相關。此指數(index)是所有簇的簇間色散(between-clusters dispersion)和簇內色散(inter-cluster dispersion)之和的比率(其中色散(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指數應用于聚類分析的結果：>>> 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...

10.6.1. 優點

• 當集群密集且分離較好時，得分更高，這與簇的標準概念有關。
• 計算速度快。

10.6.2. 缺點

• 凸簇(convex clusters)的Calinski-Harabasz指數通常高于其它類型的簇，例如通過DBSCAN獲得的基于密度的簇。

10.6.3. 數學公式

對于大小為的數據集E聚類成k個簇，Calinski-Harabasz得分s被定義為簇間色散平均值(between-clusters dispersion mean)與簇內分散( within-cluster dispersion)的比率：其中是簇間色散矩陣的跡線，是簇內色散矩陣的跡線，定義如下：其中，是簇q中的一組點，是簇q的中心，是E的中心，是簇q中點的數量。參考文獻：

• Caliński, T., & Harabasz, J. (1974).?“A Dendrite Method for Cluster Analysis”. Communications in Statistics-theory and Methods 3: 1-27.?doi:10.1080/03610927408827101.

10.7. Davies-Bouldin 指數

如果不知道真值標簽，可以使用Davies-Bouldin 指數(sklearn.metrics.davies_bouldin_score) 來評估模型，其中較低的Davies-Bouldin index與聚類之間分離較好的模型相關。此指數(index)表示集群之間的平均“相似性”，其中相似性是比較集群之間的距離和集群本身大小的度量。零是可能的最低分。接近零的值表示更好的分區。在正常使用中，Davies-Bouldin index應用于聚類分析的結果，如下所示：>>> 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...

10.7.1. 優點

• Davies Bouldin的計算比輪廓分數(Silhouette scores)的計算簡單。
• index 僅計算數據集內的數量和特征。

10.7.2. 缺點

• 對于凸簇(convex clusters)，Davies-Boulding 指數通常高于其他類型的簇，例如從DBSCAN獲得的基于密度的簇。
• 質心距離只能使用歐幾里德空間的距離度量。

10.7.3. 數學公式

index 定義為每個聚類與其最相似的一個聚類之間的平均相似性(average similarity)，其中i=1,...,k。在這個index定義下，相似性(similarity)被定義為一種衡量，它權衡：，簇i的每個點與簇的質心之間的平均距離，也稱為簇直徑(cluster diameter)。，簇質心i和j之間的距離。構造使其非負且對稱的一個簡單選擇是：然后，Davies-Bouldin index定義為：參考文獻：

• Davies, David L.; Bouldin, Donald W. (1979). “A Cluster Separation Measure” IEEE Transactions on Pattern Analysis and Machine Intelligence. PAMI-1 (2): 224-227.?doi:10.1109/TPAMI.1979.4766909.
• Halkidi, Maria; Batistakis, Yannis; Vazirgiannis, Michalis (2001). “On Clustering Validation Techniques” Journal of Intelligent Information Systems, 17(2-3), 107-145.?doi:10.1023/A:1012801612483.
• Wikipedia entry for Davies-Bouldin index.

10.8. 列聯矩陣(Contingency Matrix)

列聯矩陣(sklearn.metrics.cluster.contingency_matrix)報告每個真實/預測的簇對的交集基數(intersection cardinality)。列聯矩陣為所有的聚類度量(clustering metrics)提供了足夠的統計信息，其中樣本是獨立的、相同分布的，并且不需要考慮一些沒有被聚類的實例。下面是一個例子：>>> 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]])輸出數組的第一行表示有三個樣本的真實簇是“a”。其中，兩個在預測簇(predicted cluster) 0中，一個在1中，沒有一個在2中。第二行表示有三個樣本的真實簇為“b”。其中，沒有一個在預測的集群0中，一個在1中，兩個在2中。分類的混淆矩陣(confusion matrix)是一個平方列聯矩陣，其中行和列的順序對應于類的列表。10.8.1. 優點

• 允許檢查每個真實簇在預測簇之間的傳播，反之亦然。
• 計算出的列聯表通常用于計算兩個簇之間的相似性統計(如本文檔中列出的其他統計方式)

10.8.2. 缺點

• 列聯矩陣對于小數量的簇易于解釋，但對于大數量的簇則變得非常難以解釋。
• 它沒有給出一個指標作為聚類優化的目標。

參考文獻：

• Wikipedia entry for contingency matrix

文壹由“伴編輯器”提供技術支持

☆☆☆為方便大家查閱，小編已將scikit-learn學習路線專欄文章統一整理到公眾號底部菜單欄，同步更新中，關注公眾號，點擊左下方“系列文章”，如圖：

歡迎大家和我一起沿著scikit-learn文檔這條路線，一起鞏固機器學習算法基礎。(添加微信：mthler，備注：sklearn學習，一起進【sklearn機器學習進步群】開啟打怪升級的學習之旅。)

總結

以上是生活随笔為你收集整理的matlab对手写数字聚类的方法_scikitlearn — 聚类的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。