聚類演算法第一篇-概覽

02-12

1 聚類分析概述

聚類（Clustering）的本質是對數據進行分類，將相異的數據儘可能地分開，而將相似的數據聚成一個類別（簇），使得同一類別的數據具有儘可能高的同質性（homogeneity），類別之間有儘可能高的異質性（heterogeneity），從而方便從數據中發現隱含的有用信息。聚類演算法的應用包含如下幾方面：

（1）其他數據挖掘任務的關鍵中間環節：用於構建數據概要，用於分類、模式識別、假設生成和測試；用於異常檢測，檢測遠離群簇的點。

（2）數據摘要、數據壓縮、數據降維：例如圖像處理中的矢量量化技術。創建一個包含所有簇原型的表，即每個原型賦予一個整數值，作為它在表中的索引。每個對象用與它所在簇相關聯的原型的索引表示。

（3）協同過濾：用於推薦系統和用戶細分。

（4）動態趨勢檢測：對流數據進行聚類，檢測動態趨勢和模式。

（5）用於多媒體數據、生物數據、社交網路數據的應用。

2 聚類演算法的分類

（1）基於分層的聚類(hierarchical methods)：主要講給定的數據集進行逐層分解，直到滿足某種條件為止。具體可分為「自底向上」和「自頂向下」兩種方案。在「自底向上」方案中，初始時每個數據點組成一個單獨的組，在接下來的迭代中，按一定的距離度量將相互鄰近的組合併成一個組，直至所有的記錄組成一個分組或者滿足某個條件為止。代表演算法有：BIRCH，CURE，CHAMELEON等。自底向上的凝聚層次聚類如下圖所示。

（2）基於劃分的聚類（partitioning methods）：給定包含 $N$ 個點的數據集，劃分法將構造 $K$ 個分組，每個分組代表一個聚類，這裡每個分組至少包含一個數據點，每個數據點屬於且僅屬於一個分組。對於給定的 $K$ 值，演算法先給出一個初始的分組方法，然後通過反覆迭代的方法改變分組，使得每一次改進之後的分組方案較前一次好，這裡好的標準在於同一組中的點越近越好，不同組中的點越遠越好。代表演算法有：K-means，K-medoids，CLARANS。K-means聚類過程圖解如下：

（3）基於密度的聚類（density-based methods）：基於密度的方法的特點是不依賴於距離，而是依賴於密度，從而克服基於距離的演算法只能發現「球形」聚簇的缺點。其核心思想在於只要一個區域中點的密度大於某個閾值，就把它加到與之相近的聚類中去。代表演算法有：DBSCAN，OPTICS，DENCLUE，WaveCluster。DBSCAN的聚簇生成過程的簡單理解如下圖，後續會進行詳述。

（4）基於網格的聚類（gird-based methods）：這種方法通常將數據空間劃分成有限個單元的網格結構，所有的處理都是以單個的單元為對象。這樣做起來處理速度很快，因為這與數據點的個數無關，而只與單元個數有關。代表演算法有：STING，CLIQUE，WaveCluster。基於Clique的聚類過程可直觀如下圖進行理解。

（5）基於模型的聚類（model-based methods）：基於模型的方法給每一個聚類假定一個模型，然後去尋找能很好的擬合模型的數據集。模型可能是數據點在空間中的密度分布函數或者其它。這樣的方法通常包含的潛在假設是：數據集是由一系列的潛在概率分布生成的。通常有兩種嘗試思路：統計學方法和神經網路方法。其中，統計學方法有COBWEB演算法、GMM(Gaussian Mixture Model)，神經網路演算法有SOM(Self Organized Maps)演算法。下圖是GMM過程的一個簡單直觀地理解。

3 聚類分析的要求

不同的聚類演算法有不同的應用背景，有的適合於大數據集，可以發現任意形狀的聚簇；有的演算法思想簡單，適用於小數據集。總的來說，數據挖掘中針對聚類的典型要求包括：

（1）可伸縮性：當數據量從幾百上升到幾百萬時，聚類結果的準確度能一致。

（2）處理不同類型屬性的能力：許多演算法針對的數值類型的數據。但是，實際應用場景中，會遇到二元類型數據，分類/標稱類型數據，序數型數據。

（3）發現任意形狀的類簇：許多聚類演算法基於距離（歐式距離或曼哈頓距離）來量化對象之間的相似度。基於這種方式，我們往往只能發現相似尺寸和密度的球狀類簇或者凸型類簇。但是，實際中類簇的形狀可能是任意的。

（4）初始化參數的需求最小化：很多演算法需要用戶提供一定個數的初始參數，比如期望的類簇個數，類簇初始中心點的設定。聚類的結果對這些參數十分敏感，調參數需要大量的人力負擔，也非常影響聚類結果的準確性。

（5）處理雜訊數據的能力：雜訊數據通常可以理解為影響聚類結果的干擾數據，包含孤立點，錯誤數據等，一些演算法對這些雜訊數據非常敏感，會導致低質量的聚類。

（6）增量聚類和對輸入次序的不敏感：一些演算法不能將新加入的數據快速插入到已有的聚類結果中，還有一些演算法針對不同次序的數據輸入，產生的聚類結果差異很大。

（7）高維性：有些演算法只能處理2到3維的低緯度數據，而處理高維數據的能力很弱，高維空間中的數據分布十分稀疏，且高度傾斜。

（8）可解釋性和可用性：我們希望得到的聚類結果都能用特定的語義、知識進行解釋，和實際的應用場景相聯繫。

PS：本文是聚類演算法的第一篇，後續會在各個類別的分類演算法中挑選一二進行介紹，敬請期待。^_^!!!

參考文章

【1】聚類分析初探（一）引言

【2】【聚類分析】聚類演算法初階引入

【3】用於數據挖掘的聚類演算法有哪些，各有何優勢？ - 數據分析