聚類分析

維基百科,自由的百科全書
前往: 導覽搜尋

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

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

聚類類型[編輯]

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

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

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

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

距離測量[編輯]

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

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

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

結構性聚類[編輯]

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

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

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

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

聚集型層次聚類[編輯]

Raw data

它的層次聚類樹如下圖

Traditional representation

概念聚類[編輯]

分散性聚類[編輯]

K-均值法及衍生算法[編輯]

K-均值法聚類[編輯]

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

例如:數據集合為三維,聚類以兩點:X =(x1, x2, x3),Y =(y1, y2, y3)。中心點Z變為Z =(z1, z2, z3),其中z1 = (x1 + y1)/2,z2 = (x2 + y2)/2,z3 = (x3 + y3)/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.

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.

外部連結[編輯]

相關軟件[編輯]

免費類[編輯]

  • 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

商業類[編輯]