聚類分析

聚類分析（Cluster analysis）亦稱集群分析，是對於統計資料分析的一門技術，在許多領域受到廣泛應用，包括機器學習，資料探勘，圖型識別，圖像分析以及生物資訊。聚類是把相似的對象通過靜態分類的方法分成不同的組別或者更多的子集（subset），這樣讓在同一個子集中的成員對象都有相似的一些屬性，常見的包括在坐標系中更加短的空間距離等。

一般把資料聚類歸納為一種非監督式學習。

定義

聚類（clustering）的概念不能精確定義，這也是為什麼聚類演算法眾多的原因之一。 聚類問題的共同點就是有一組資料對象。 然而，不同的研究人員採用不同的聚類模型，並且對於這些聚類模型中的每一個，可以再給出不同的演算法。 而且不同演算法發現的「類（簇）」在其屬性上往往會有很大差異。 理解這些「聚類模型」是理解各種演算法之間差異的關鍵。 典型的聚類模型包括以下幾種：

• 連通性模型：例如，層次聚類基於距離連通性構建模型。

• 質心模型：例如，k-means 演算法用單個均值向量表示每個類。

• 分布模型：聚類過程使用統計分布建模，例如期望最大化演算法使用的多元常態分布。

• 密度模型：例如，DBSCAN 和 OPTICS 將聚類別定義為資料空間中相連接的密集區域。

• 子空間模型：在雙聚類（也稱為共聚類或雙模式聚類）中，聚類是用聚類別成員和相關屬性建模的。

• 組模型：這些演算法不為其結果提供改進的模型，只提供分組資訊。

• 基於圖的模型：團(clique)，即圖中節點的子集，子集中的每兩個節點都由一條邊連接，可以被認為是聚類的原型形式。 與 HCS 聚類演算法一樣，放寬完全連通性的要求（一部分邊可能會遺失）被稱為」准團」。

• 符號圖模型：符號圖（signed graph）中的每條路徑都有一個符號，該符號來自邊上符號的乘積。 在平衡理論的假設下，邊可能會改變符號並導致分叉圖。 較弱的「聚類性公理」（沒有迴圈恰好有一個負邊）產生的結果是兩個以上的聚類，或只有正邊的子圖。

• 神經模型：最著名的無監督神經網路是自組織對映，這些模型的特徵通常與上述一個或多個模型相似，並且在神經網路實現主成分分析或獨立分析形式時包括子空間模型 成分分析

「聚類」的本質上是找到一組類, 這些類通常包含資料集中的所有對象。 此外，它可以指定各個類彼此之間的關係，例如，類相互嵌入的階層。 聚類可以大致區分為：

• 硬聚類：每個對象是否屬於一個類

• 軟聚類（又作：模糊聚類）：每個對象在一定程度上屬於每個聚類（例如，屬於該聚類的可能性）

也可能有更細微的區別，例如：

嚴格分割區聚類：每個對象恰好屬於一個類

• 有異常值的嚴格分割區聚類（Strict partitioning clustering with outliers）：對象也可以不屬於任何簇，被認為是異常值

• 重疊聚類（又作：替代聚類、多視圖聚類）：對象可能屬於多個聚類； 通常涉及硬簇

• 層次聚類：屬於子聚類的對象也屬於父聚類

• 子空間聚類：雖然是重疊聚類，但在唯一定義的子空間內，聚類不應重疊

演算法

沒有客觀上「正確」的聚類演算法，但正如人們所指出的，「聚類在觀察者的眼中」。除非你有喜歡一個聚類模型而不是另一個的數學原因，通常需要通過實驗選擇最適合特定問題的聚類演算法。為一種模型設計的演算法通常會在包含完全不同類型模型的資料集上失敗。 例如，k-means 無法找到非凸簇。

連通性聚類

基於連通性的聚類，也稱為層次聚類，其核心思想是對象與附近對象的相關性高於與較遠對象的相關性。 這些演算法根據它們的距離將「對象」連接起來形成「簇」。 叢集可以主要通過連接叢集各部分所需的最大距離來描述。 在不同的距離，會形成不同的聚類，這可以用樹狀圖表示，這解釋了通用名稱「層次聚類」的來源：這些演算法不提供資料集的單一分割區，而是提供廣泛的階層 在一定距離處相互合併的簇。 在樹狀圖中，y 軸標記叢集合併的距離，而對象沿 x 軸放置，這樣叢集就不會混合。

基於連通性的聚類是一整套方法，它們因計算距離的方式不同而不同。 除了通常選擇的距離函式外，使用者還需要決定要使用的連接標準（因為一個類/簇由多個對象組成，所以有多個候選來計算距離）。 流行的選擇被稱為單連結聚類（對象距離的最小值）、完全連結聚類（對象距離的最大值）和 UPGMA 或 WPGMA（「具有算術平均值的未加權或加權對組方法」，也稱為平均連結 聚類）。 此外，層次聚類可以是凝聚的（從單個元素開始並將它們聚合成簇）或分裂的（從完整的資料集開始並將其分成多個分割區）。

這些方法不會產生資料集的唯一分割區，而是產生一個階層，使用者仍然需要從中選擇合適的叢集。 它們對異常值不是很穩健，異常值要麼顯示為額外的叢集，要麼甚至導致其他叢集合併（稱為「連結現象」，特別是單連結叢集）。 在一般情況下，複雜度是 O(n)³) 對於凝聚聚類和 O(2^n-1) 用於分裂聚類，[7] 這使得它們對於大型資料集來說太慢了。 對於某些特殊情況，已知最佳有效方法（複雜度 O(n)²) ：SLINK 用於單連結和 CLINK 用於完全連結聚類。

質心聚類

在基於質心的聚類演算法中，每個聚類由一個中心向量表示，它不一定是資料集的成員。 當簇數固定為 k 時，k-means 聚類給出了最佳化問題的形式化定義：找到 k 個簇中心並將對象分配到最近的簇中心，使得與簇的平方距離最小。

已知最佳化問題本身是 NP問題（NP困 難），因此常用的方法是只搜尋近似解。 一個特別著名的近似方法是 Lloyd 演算法， 通常簡稱為「k-means 演算法」（儘管另一個演算法引入了這個名稱）。 然而，它確實只能找到局部最佳值，並且通常會使用不同的隨機初始化執行多次。 k-means 的變體通常包括這樣的最佳化，例如選擇多次執行中的最佳者，但也將質心限制為資料集的成員（k-medoids），選擇中位數（k-medians 聚類），不太隨機地選擇初始中心（ k-means++) 或允許模糊聚類分配 (fuzzy c-means)。

大多數 k-means 類型的演算法都需要預先指定聚類的數量 - k，這被認為是這些演算法的最大缺點之一。 此外，演算法更喜歡大小大致相似的簇，因為它們總是會將對象分配給最近的質心。 這通常會導致錯誤地切割叢集邊界（這並不奇怪，因為該演算法最佳化的是叢集中心，而不是叢集邊界）。

K-means 有許多有趣的理論特性。 首先，它將資料空間劃分為一種稱為 Voronoi 圖的結構。 其次，它在概念上接近最近鄰分類，因此在機器學習中很受歡迎。 第三，它可以看作是基於模型的聚類的變體，Lloyd 演算法可以看作是下面討論的該模型的期望最大化演算法的變體。

基於質心的聚類問題（如 k-means 和 k-medoids）是無容量、度量設施位置問題的特例，是運籌學和計算幾何社群中的典型問題。 在一個基本的設施位置問題（其中有許多變體可以類比更複雜的設定）中，任務是找到最佳倉庫位置以最佳地服務一組給定的消費者。 人們可以將「倉庫」視為聚類質心，將「消費者位置」視為要聚類的資料。 這使得將設施位置文獻中完善的演算法解決方案應用於目前考慮的基於質心的聚類問題成為可能。

分布模型聚類

與統計學關係最密切的聚類模型是基於分布模型的。 然後可以很容易地將聚類別定義為最有可能屬於同一分布的對象。 這種方法的一個方便的特性是它非常類似於生成人工資料集的方式：通過從分布中抽取隨機對象。

儘管這些方法的理論基礎非常出色，但它們都存在一個稱為過度擬合的關鍵問題，除非對模型的複雜性施加約束。 更複雜的模型通常能夠更好地解釋資料，這使得選擇合適的模型複雜性本身就很困難。

一種著名的方法被稱為高斯混合模型（使用期望最大化演算法）。 在這裡，資料集通常使用固定數量（以避免過度擬合）的高斯分布建模，這些高斯分布隨機初始化並且其參數經過迭代最佳化以更好地擬合資料集。 這將收斂到局部最佳，因此多次執行可能會產生不同的結果。 為了獲得硬聚類，通常會將對象分配給它們最有可能屬於的高斯分布； 對於軟聚類，這不是必需的。

基於分布的聚類為聚類生成複雜模型，可以擷取屬性之間的相關性和依賴性。 然而，這些演算法給使用者帶來了額外的負擔：對於許多真實資料集，可能沒有簡明定義的數學模型（例如，假設高斯分布是對資料的相當強的假設）。

密度聚類

在基於密度的聚類中， 聚類被定義為密度高於資料集其餘部分的區域。 稀疏區域中的對象——需要分離叢集——通常被認為是噪聲和邊界點。

最流行的基於密度的聚類別方法是 DBSCAN,。與許多較新的方法相比，它具有一個定義明確的叢集模型，稱為「密度可達性」。 類似於基於連結的聚類，它基於一定距離閾值內的連接點。 然而，它只連接滿足密度標準的點，在原始變體中定義為該半徑內其他對象的最小數量。 簇由所有密度連接的對象（與許多其他方法相反，它可以形成任意形狀的簇）加上這些對象範圍內的所有對象組成。 DBSCAN 的另一個有趣的特性是它的複雜性相當低——它需要對資料庫進行線性數量的範圍查詢——並且它會發現基本相同的結果（它對核心點和噪聲點是確定性的，但對邊界點不是） 在每次執行中，因此無需多次執行。 OPTICS是 DBSCAN 的推廣，無需為範圍參數 ε 選擇合適的值，並產生與連鎖聚類相關的分層結果。 DeLi-Clu， Density-Link-Clustering 結合了單連結聚類和 OPTICS 的思想，完全消除了 ε 參數，並通過使用 R 樹索引提供了優於 OPTICS 的效能改進。

DBSCAN 和 OPTICS 的主要缺點是它們期望某種密度下降來檢測簇邊界。 例如，在具有重疊高斯分布（人工資料中的常見用例）的資料集上，這些演算法生成的聚類邊界通常看起來很隨意，因為聚類密度不斷降低。 在由高斯混合組成的資料集上，這些演算法幾乎總是優於能夠精確建模此類資料的 EM 聚類等方法。

均值漂移(mean-shift)是一種聚類別方法，其中基於核密度估計將每個對象移動到其附近最密集的區域。 最終，對象會聚到密度的局部最大值。 與 k-means 聚類類似，這些「密度吸引子」可以作為資料集的代表，但 mean-shift 可以檢測類似於 DBSCAN 的任意形狀的聚類。 由於昂貴的迭代過程和密度估計，均值漂移通常比 DBSCAN 或 k-Means 慢。 除此之外，均值漂移演算法對多維資料的適用性受到核密度估計的不平滑行為的阻礙，這會導致聚類尾部過度碎片化。

網格聚類

基於網格的技術用於多維資料集。 在此技術中，我們建立一個網格結構，並在網格（也稱為儲存格）上執行比較。 基於網格的技術速度快，計算複雜度低。 有兩種類型的基於網格的聚類別方法：STING 和 CLIQUE。

聚類類型

資料聚類演算法可以分為結構性或者分散性。結構性演算法利用以前成功使用過的聚類器進行分類，而分散型演算法則是一次確定所有分類。結構性演算法可以從上至下或者從下至上雙向進行計算。從下至上演算法從每個對象作為單獨分類開始，不斷融合其中相近的對象。而從上至下演算法則是把所有對象作為一個整體分類，然後逐漸分小。

分散式聚類演算法，是一次性確定要產生的類別，這種演算法也已應用於從下至上聚類演算法。

基於密度的聚類演算法，是為了挖掘有任意形狀特性的類別而發明的。此演算法把一個類別視為資料集中大於某閾值的一個區域。DBSCAN和OPTICS是兩個典型的演算法。

許多聚類演算法在執行之前，需要指定從輸入資料集中產生的分類個數。除非事先準備好一個合適的值，否則必須決定一個大概值，關於這個問題已經有一些現成的技術。

距離測量

資料對象間的相似度度量一般是通過資料之間的相互關係來確定。 在結構性聚類中，關鍵性的一步就是要選擇測量的距離。一個簡單的測量就是使用曼哈頓距離，它相當於每個變數的絕對差值之和。該名字的由來起源於在紐約市區測量街道之間的距離就是由人步行的步數來確定的。

一個更為常見的測量方法是利用歐氏空間距離，可以認為資料分布一個多維空間中，並且計算每個空間中每個點到原點的距離，然後對所有距離進行換算。

常用的幾個距離計算方法：

• 歐氏距離（2-norm距離）
• 曼哈頓距離（Manhattan distance, 1-norm距離）
• infinity norm
• 馬氏距離
• 餘弦相似性
• 漢明距離

結構性聚類

在已經得到距離值之後，元素間可以被聯絡起來。通過分離和融合可以構建一個結構。傳統上，表示的方法是樹形資料結構， 然後對該結構進行修剪。樹的根節點表示一個包含所有專案的類別，樹葉表示與個別的專案相關的類別。

層次聚類演算法，要麼是由下而上聚集型的，即從葉子節點開始，最終匯聚到根節點；要麼是自頂向下分裂型的，即從根節點開始，遞迴的向下分裂。

任意非負值的函式都可以用于衡量一對觀測值之間的相似度。決定一個類別是否分裂或者合併的是一個連動的標準，它是兩兩觀測值之間距離的函式。

在一個指定高度上切割此樹，可以得到一個相應精度的分類。

聚集型層次聚類

Raw data

它的層次聚類樹如下圖

Traditional representation

分散性聚類

K-均值法及衍生演算法

K-均值法聚類

K-均值演算法表示以空間中k個點為中心進行聚類，對最靠近他們的對象歸類。

例如：資料集合為三維，聚類以兩點：X =(x₁, x₂, x₃),Y =(y₁, y₂, y₃)。中心點Z變為Z =(z₁, z₂, z₃)，其中z₁ = (x₁ + y₁)/2，z₂ = (x₂ + y₂)/2，z₃ = (x₃ + y₃)/2。

演算法歸納為（J. MacQueen, 1967）：

• 選擇聚類的個數k.
• 任意產生k個聚類，然後確定聚類中心，或者直接生成k個中心。
• 對每個點確定其聚類中心點。
• 再計算其聚類新中心。
• 重複以上步驟直到滿足收斂要求。（通常就是確定的中心點不再改變。）

該演算法的最大優勢在於簡潔和快速。劣勢在於對於一些結果並不能夠滿足需要，因為結果往往需要隨機點的選擇非常巧合。

譜聚類

主條目：譜聚類

在多元變數統計中，譜聚類（英語：spectral clustering）技術利用資料相似矩陣的譜（特徵值），在對資料進行降維後，以較少的維度進行聚類。相似矩陣作為輸入，提供了對資料集中每一對點相對相似性的定量評估。

在圖像分割中，譜聚類被稱為基於分割的物體分類。

評估和驗證

聚類結果的評估（或「驗證」）與聚類本身一樣困難 。 流行的方法包括「內部」評估，其中聚類被總結為一個單一的品質分數，「外部」評估，其中聚類與現有的「基準真相(ground truth)」分類進行比較，由人類專家進行「手動」評估，以及「間接」通過評估聚類在其預期應用中的效用來進行評估。

內部評估措施存在一個問題，即它們代表的功能本身可以被視為聚類目標。 例如，可以通過 Silhouette 係數對資料集進行聚類； 除了沒有已知的有效演算法之外。 通過使用這種內部衡量指標進行評估，人們更願意比較最佳化問題的相似性, 而不一定是聚類的有用程度 。

外部評估也有類似的問題：如果我們有這樣的「ground truth」標籤，那麼我們就不需要聚類了； 而在實際應用中我們通常沒有這樣的標籤。 另一方面，標籤僅反映了資料集的一種可能分割區，這並不意味著不存在不同的甚至更好的聚類。

因此，這兩種方法都不能最終判斷聚類的實際品質，但這需要人工評估， 這是非常主觀的。 儘管如此，這樣的統計資料在辨識不良聚類方面可能非常有用， 但不應忽視主觀的人為評估。

參考文獻

• Abdi, H. (1994). Additive-tree representations (with an application to face processing) Lecture Notes in Biomathematics, 84, 43-59.. 1990. 
• Clatworthy, J., Buick, D., Hankins, M., Weinman, J., & Horne, R. (2005). The use and reporting of cluster analysis in health psychology: A review. British Journal of Health Psychology 10: 329-358.
• Cole, A. J. & Wishart, D. (1970). An improved algorithm for the Jardine-Sibson method of generating overlapping clusters. The Computer Journal 13(2):156-163.

• Ester, M., Kriegel, H.P., Sander, J., and Xu, X. 1996. A density-based algorithm for discovering clusters in large spatial databases with noise. Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining, Portland, Oregon, USA: AAAI Press, pp. 226–231.

• Heyer, L.J., Kruglyak, S. and Yooseph, S., Exploring Expression Data: Identification and Analysis of Coexpressed Genes, Genome Research 9:1106-1115.

• Huang, Z. (1998). Extensions to the K-means Algorithm for Clustering Large Datasets with ategorical Values. Data Mining and Knowledge Discovery, 2, p. 283-304.
• Jardine, N. & Sibson, R. (1968). The construction of hierarchic and non-hierarchic classifications. The Computer Journal 11:177.
• The on-line textbook: Information Theory, Inference, and Learning Algorithms （頁面存檔備份，存於網際網路檔案館）, by David J.C. MacKay includes chapters on k-means clustering, soft k-means clustering, and derivations including the E-M algorithm and the variational view of the E-M algorithm.
• Ng, R.T. and Han, J. 1994. Efficient and effective clustering methods for spatial data mining. Proceedings of the 20th VLDB Conference, Santiago, Chile, pp. 144–155.
• Prinzie A., D. Van den Poel (2006), Incorporating sequential information into traditional classification models by using an element/position-sensitive SAM （頁面存檔備份，存於網際網路檔案館）. Decision Support Systems 42 (2): 508-526.
• Romesburg, H. Clarles, Cluster Analysis for Researchers, 2004, 340 pp. ISBN 1-4116-0617-5 or publisher （頁面存檔備份，存於網際網路檔案館）, reprint of 1990 edition published by Krieger Pub. Co... A Japanese language translation is available from Uchida Rokakuho Publishing Co., Ltd., Tokyo, Japan.
• Zhang, T., Ramakrishnan, R., and Livny, M. 1996. BIRCH: An efficient data clustering method for very large databases. Proceedings of ACM SIGMOD Conference, Montreal, Canada, pp. 103–114.

For spectral clustering :

• Jianbo Shi and Jitendra Malik, "Normalized Cuts and Image Segmentation", IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8), 888-905, August 2000. Available on Jitendra Malik's homepage （頁面存檔備份，存於網際網路檔案館）
• Marina Meila and Jianbo Shi, "Learning Segmentation with Random Walk", Neural Information Processing Systems, NIPS, 2001. Available from Jianbo Shi's homepage （頁面存檔備份，存於網際網路檔案館）

For estimating number of clusters:

• Can, F., Ozkarahan, E. A. (1990) "Concepts and effectiveness of the cover coefficient-based clustering methodology for text databases." ACM Transactions on Database Systems. 15 (4) 483-517.

For discussion of the elbow criterion:

• Aldenderfer, M.S., Blashfield, R.K, Cluster Analysis, (1984), Newbury Park (CA): Sage.

外部連結

• P. Berkhin, Survey of Clustering Data Mining Techniques （頁面存檔備份，存於網際網路檔案館）, Accrue Software, 2002.
• Jain, Murty and Flynn: Data Clustering: A Review （頁面存檔備份，存於網際網路檔案館）, ACM Comp. Surv., 1999.
• for another presentation of hierarchical, k-means and fuzzy c-means see this introduction to clustering （頁面存檔備份，存於網際網路檔案館）. Also has an explanation on mixture of Gaussians.
• David Dowe, Mixture Modelling page （頁面存檔備份，存於網際網路檔案館） - other clustering and mixture model links.
• a tutorial on clustering [1]
• The on-line textbook: Information Theory, Inference, and Learning Algorithms （頁面存檔備份，存於網際網路檔案館）, by David J.C. MacKay includes chapters on k-means clustering, soft k-means clustering, and derivations including the E-M algorithm and the variational view of the E-M algorithm.

相關軟體

免費類

• The flexclust package for R
• COMPACT - Comparative Package for Clustering Assessment （頁面存檔備份，存於網際網路檔案館）（in Matlab）
• YALE (Yet Another Learning Environment): freely available open-source software for data pre-processing, knowledge discovery, data mining, machine learning, visualization, etc. also including a plugin for clustering, fully integrating Weka, easily extendible, and featuring a graphical user interface as well as a XML-based scripting language for data mining;
• mixmod （頁面存檔備份，存於網際網路檔案館） : Model Based Cluster And Discriminant Analysis. Code in C++, interface with Matlab and Scilab
• LingPipe Clustering Tutorial （頁面存檔備份，存於網際網路檔案館） Tutorial for doing complete- and single-link clustering using LingPipe, a Java text data mining package distributed with source.
• Weka : Weka contains tools for data pre-processing, classification, regression, clustering, association rules, and visualization. It is also well-suited for developing new machine learning schemes.
• Tanagra （頁面存檔備份，存於網際網路檔案館） : a free data mining software including several clustering algorithms such as K-MEANS, SOM, Clustering Tree, HAC and more.
• Cluster : Open source clustering software. The routines are available in the form of a C clustering library, an extension module to Python, a module to Perl.
• python-cluster （頁面存檔備份，存於網際網路檔案館） Pure python implementation

商業類

• Clustan （頁面存檔備份，存於網際網路檔案館）
• Peltarion Synapse（using self-organizing maps）[2] （頁面存檔備份，存於網際網路檔案館）