聚類分析

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

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

聚類類型

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

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

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

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

距離測量

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

一個更為常見的測量是歐氏空間距離，他的演算法是找到一個空間，來計算每個空間中點到原點的距離，然後對所有距離進行換算。

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

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

結構性聚類

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

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

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

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

聚集型層次聚類

它的層次聚類樹如下圖：

分散性聚類

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個中心。
對每個點確定其聚類中心點。
再計算其聚類新中心。
重複以上步驟直到滿足收斂要求。（通常就是確定的中心點不再改變。）

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

QT聚類演算法

延伸閱讀

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.