2.3. 聚類?

可以使用模塊 sklearn.cluster 對未標記的數據進行 聚類(Clustering) 。

每個聚類算法都有兩個變體:一個是類，它實現了 fit 方法來學習訓練數據上的簇，另一個是函數，給定訓練數據，返回對應于不同簇的整數標簽數組。對于類，可以在 labels_ 屬性中找到訓練數據上的標簽。

輸入數據

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

2.3.1. 聚類方法概述

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

Method name（方法名稱） Parameters（參數） Scalability（可擴展性） Usecase（使用場景） Geometry (metric used)（幾何圖形（公制））
K-Means（K-均值） number of clusters（聚類形成的簇的個數） 非常大的 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 不可擴展） 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不可擴展） Many clusters, uneven cluster size, non-flat geometry（許多簇，不均勻的簇大小，非平面幾何） Distances between points（點之間的距離）
Spectral clustering number of clusters（簇的個數） 中等的 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（簇的個數） 大的 n_samples 和 n_clusters Many clusters, possibly connectivity constraints（很多的簇，可能連接限制） Distances between points（點之間的距離）
Agglomerative clustering number of clusters（簇的個數）, linkage type（鏈接類型）, distance（距離） 大的 n_samples 和 n_clusters Many clusters, possibly connectivity constraints, non Euclidean distances（很多簇，可能連接限制，非歐氏距離） Any pairwise distance（任意成對距離）
DBSCAN neighborhood size（neighborhood 的大小） 非常大的 n_samples, 中等的 n_clusters Non-flat geometry, uneven cluster sizes（非平面幾何，不均勻的簇大小） Distances between nearest points（最近點之間的距離）
Gaussian mixtures（高斯混合） many（很多） Not scalable（不可擴展） 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.（大型數據集，異常值去除，數據簡化）

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

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

2.3.2. K-means

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

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

K-means算法旨在選擇一個質心, 能夠最小化慣性或簇內平方和的標準:

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

慣性被認為是測量簇內聚程度的尺度。它有很多缺點:

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

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

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

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

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

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

K-means可用于矢量量化。這是利用 KMeans 訓練模型的變換方法實現的。

2.3.2.1. 低級并行

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

示例:

參考資料:

2.3.2.2. 小批量 K-Means

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

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

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

示例:

參考文獻:

2.3.3. Affinity Propagation

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

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

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

示例：

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

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

?

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

?

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

? ?

其中 是迭代的次數。

2.3.4. Mean Shift

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

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

?

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

?

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

該算法不是高度可擴展的，因為在執行該算法時需要進行多個最近鄰搜索。該算法保證收斂，但是當質心的變化較小時，該算法將停止迭代。

通過找到給定樣本的最近質心來標記新樣本。

示例:

參考文獻:

2.3.5. Spectral clustering（譜聚類）

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

當前版本的SpectralClustering需要預先指定簇的數量。它適用于簇數量少時，簇數量多時不建議使用。

對于兩個簇，SpectralClustering解決了相似性圖形上歸一化切割問題的凸松弛問題：將圖形切割成兩半，以使所切邊緣的權重比每個簇內邊緣的權重小。此標準特別有趣：當處理圖形的頂點為像素，相似圖形的邊緣是圖像的漸變函數。 警告：將距離轉換為行為良好的相似性

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

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

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

2.3.5.1. 不同的標簽分配策略

SpectralClustering對應的assign_labels參數，可以使用不同的標簽分配策略。 "kmeans"可以匹配更詳細的數據信息，但可能不穩定。特別是，除非你可以控制random_state,否則它可能無法復現運行的結果，因為它取決于隨機初始化。使用"discretize"策略是100％可復現的，但往往會創建幾何形狀相當均勻的閉合包。

2.3.5.2. 譜聚類圖表

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

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

參考文獻：

2.3.6. 層次聚類

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

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

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

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

FeatureAgglomeration

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

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

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

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

示例：

2.3.6.2. 聚類分層結構可視化

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

2.3.6.3. 添加連接約束

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

這些約束對于強加特定的局部結構是有用的，而且也使算法更快，特別是當樣本數量很大的時候。

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

示例：

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

single, average and complete linkage的連接約束可以增強聚合聚類中的 ‘rich getting richer’ 現象，尤其是如果他們是用sklearn.neighbors.kneighbors_graph來構建時。在少數簇的限制下，它們傾向于給出一些宏觀上占據的簇，并且幾乎是空的簇。（請參閱帶結構和無結構的凝聚聚類的討論 ）。就此問題而言，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), 或者任何預先計算的關聯矩陣(affinity matrix).

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

選擇度量標準的知道原則是使得不同類樣本之間距離最大化，并且最小化同類樣本之間的距離

示例：

2.3.7. DBSCAN

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

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

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

參數min_samples 主要控制算法對噪聲的容忍度(當處理大型噪聲數據集時, 需要考慮增加該參數的值), 如何選擇適當的eps 對具體地數據集和距離函數非常關鍵，通常不能使用默認值。參數eps控制了點地領域范圍。如果取值太小,大多數數據并不會被聚類(并將“噪音”標記為-1); 如果取值太大，可能會導致相近的多個簇被合并成一個,并最終將整個數據集分配到單個簇返回。文獻上已經討論過了一些啟發式（heuristics）參數選擇方法。例如，在最近鄰距離圖種，基于Knee的參數選擇方式（如下面的參考文獻中所討論的）。

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

示例:

實現

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

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

在大規模樣本上運行時的內存消耗

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

  • 使用 OPTICS 聚類算法結合 extract_dbscan 方式。 OPTICS 聚類算法同樣需要計算全結對矩陣(full pairwise matrix)，但每次僅在內存中保持一行(內存復雜度為 n)。
  • 稀疏半徑鄰域圖(A sparse radius neighborhood graph)(其中缺少的樣本被假定為距離超出eps) 可以以高效的方式預先編譯，并且可以使用 metric='precomputed' 來運行 dbscan。
  • 可以對數據集進行壓縮，當數據中存在準確的重復時，可以刪除這些重復的數據，或者使用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.

2.3.8. OPTICS

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

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

示例:

與DBSCAN相比

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

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

計算復雜度

采用空間索引樹以避免計算整個距離矩陣，并允許在大量樣本上有效地使用內存。可以通過metric關鍵字提供不同的距離度量。

對于大型數據集，可以通過HDBSCAN獲得類似（但不相同）的結果 。HDBSCAN實現是多線程的，并且具有比OPTICS更好的算法運行時間復雜性，代價是更高的內存代價。對于使用HDBSCAN將耗盡系統內存的極大數據集，OPTICS將維持n（而不是n^2）內存縮放; 然而，可能需要使用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.

2.3.9. Birch

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

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

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

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

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

算法描述:

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

Birch or MiniBatchKMeans?

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

How to use partial_fit?

為了避免對 global clustering 的計算，每次調用 partial_fit，建議進行如下操作:

  1. 初始化 n_clusters=None 。
  2. 通過多次調用 partial_fit 訓練所有數據。
  3. 通過使用 brc.set_params(n_clusters=n_clusters) ,設置 n_clusters 為必需值。
  4. 最后調用無參的 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

2.3.10. 聚類性能度量

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

2.3.10.1. 調整后的蘭德指數

已知真實簇標簽分配 labels_true 和我們的聚類算法是基于相同樣本所得到的 labels_pred，**調整后的蘭德指數是一個函數，它測量兩個簇標簽分配的值的 **相似度 ，忽略排列(permutations)和 機會歸一化（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...

在預測的標簽列表中重新排列 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) : 交換參數不會改變得分。它可以作為一種 共識度量(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

不良標簽 (e.g. 獨立標簽（independent labelings）) 的得分是負數或接近于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. 優點

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

2.3.10.1.2. 缺點

  • 與慣性相反，**ARI需要了解真實簇信息，**而在實踐中幾乎是不可用的，或者需要人工標注者手動分配（如在監督學習環境中）。

    但是，

示例：

2.3.10.1.3. 數學表達

如果 C 是一個真實簇的標簽分配， K 是簇的個數，定義 和 為:

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

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

其中 是數據集中可能的數據對總數（未排序）。

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

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

,如下所示:

參考資料：

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

已知真實簇的標簽分配 labels_true 和我們的聚類算法基于相同樣本所得到的 labels_pred， 互信息 是度量兩個標簽分配的 一致性的函數，忽略排列。這種度量方案有兩個不同的歸一化版本，Normalized Mutual Information(NMI) 和 Adjusted Mutual Information(AMI)。NMI 經常在文獻中使用，而 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...

在預測的標簽列表中重新排列 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...

完美標簽得分是 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...

不良標簽 (例如（無相關標簽）independent labelings) 具有非正分數：

>>> 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. 優點

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

2.3.10.2.2. 缺點

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

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

  • NMI 和 MI 不能進行使得隨機標簽度量的得分為0的調整。

示例：

2.3.10.2.3. 數學公式

假設兩個標簽分配（在相同的 N 個對象中進行）, 和 。 它們的熵是一個分區集合的不確定性量，被定義為:

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

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

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

也可以用設定的基數表達式表示:

normalized mutual可以定義為：

mutual information 的值以及歸一化變量的值都不會隨著隨機標簽度量進行調整，但是會隨著不同的簇標簽數量的增加而增加，不管標簽分配之間的 “mutual information” 的實際數量是多少。

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

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

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

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

參考文獻：

2.3.10.3. 同質性，完整性和 V-measure

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

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

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

我們可以把這些概念轉化為得分 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 的調和平均數由 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的beta值時:

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

更大的beta權重將提高完整性。

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

同質性, 完整性 和 V-measure 可以使用 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是對稱的：可用于評估同一數據集上兩個獨立的標簽分配。

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

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

2.3.10.3.1. 優點

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

2.3.10.3.2. 缺點

  • 先前引入的度量標準并不針對隨機標記進行標準化: 這意味著，根據樣本數量，簇數量和標定過的真實數據類數量，完全隨機的標注方式并不總是產生同質性，完整性 和 v-measure 的相同值。特別是特別是當簇數量很大時，隨機標記不會產生零分。

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

這，而實踐中卻幾乎不可用，或者需要或需要人工標注者人工分配（如在受監督的學習環境中）。

示例：
聚類表現評估中的機會調: 分析數據集大小對隨機分配聚類度量值的影響。

2.3.10.3.3. 數學表達

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

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

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

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

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

Rosenberg 和 Hirschberg 進一步定義 V-measure 作為 同質性和完整性的調和均值:

參考資料

2.3.10.4. Fowlkes-Mallows 得分

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

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

得分范圍為 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

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

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

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

完美的標簽得分是 1.0:

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

不良標簽（例如,無相關標簽）的得分為 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. 優點

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

2.3.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

2.3.10.5. Silhouette 系數

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

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

給出單個樣本的 Silhouette 系數 s :

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

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

在正常使用情況下，將 Silhouette 系數應用于聚類結果的分析。

>>> 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. 優點

  • 不正確的聚類得分為 -1 ，高密度聚類得分為 +1 。0 附近的分數表示重疊的聚類。
  • 當簇密集且分離良好時，得分較高，這與簇的標準概念有關。

2.3.10.5.2. 缺點

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

示例:

2.3.10.6. Calinski-Harabaz 指數

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

該指數是通過簇間色散平均值(between-clusters dispersion mean)與簇內色散之間(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 指數應用于聚類分析的結果：

>>> 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. 優點

  • 當群集密集且分隔良好時，分數會更高，這與群集的標準概念有關。
  • 分數計算迅速。

2.3.10.6.2. 缺點

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

2.3.10.6.3. 數學公式

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

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

為簇 中的點集， 為簇 的中心， 為 的中心， 為簇 中的點數。

參考文獻

2.3.10.7. Davies-Bouldin Index

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

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

零是最低的分數。值越接近零表示更好的分割。

在正常使用中，將Davies-Bouldin索引應用于簇分析的結果，如下所示：

>>> 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. 優點

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

2.3.10.7.2. 缺點

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

2.3.10.7.3. 數學公式

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

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

  • , 簇質心 和 之間的距離。

    以下是一個簡單構建 的方法，使得它具有非負性和對稱性:

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

參考文獻

2.3.10.8. Contingency Matrix

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

這是一個例子：

>>> 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''。其中兩個的預測簇是 0，一個是 1， 沒有一個是 2。而第二行表示有三個樣本的真實簇是‘’b‘’ 。 其中，沒有一個樣本的預測簇是 0, 一個是 1, 兩個是 2。

用于分類的混淆矩陣(confusion matrix) 是平方列矩陣，其中行和列的順序對應于類別列表。

2.3.10.8.1. 優點

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

2.3.10.8.2. 缺點

  • 列聯矩陣很容易解釋小數量的簇，但對于數量較大的簇則很難解釋。

  • 沒有給出一個單一的指標來做聚類優化。

  • 參考文獻