一文讀懂聚類算法

作者：廖旺堅 2017-05-15 11:10:10

聚類是數據挖掘中的概念，就是按照某個特定標準(如距離)把一個數據集分割成不同的類或簇，使得同一個簇內的數據對象的相似性盡可能大，同時不在同一個簇中的數據對象的差異性也盡可能地大。也即聚類后同一類的數據盡可能聚集到一起，不同類數據盡量分離。

1. 聚類的基本概念

1.1 定義

1.2 聚類與分類的區別

Clustering (聚類)，簡單地說就是把相似的東西分到一組，聚類的時候，我們并不關心某一類是什么，我們需要實現的目標只是把相似的東西聚到一起。因此，一個聚類算法通常只需要知道如何計算相似度就可以開始工作了，因此 clustering 通常并不需要使用訓練數據進行學習，這在Machine Learning中被稱作unsupervised learning (無監督學習)。

Classification (分類)，對于一個classifier，通常需要你告訴它“這個東西被分為某某類”這樣一些例子，理想情況下，一個 classifier 會從它得到的訓練集中進行“學習”，從而具備對未知數據進行分類的能力，這種提供訓練數據的過程通常叫做supervised learning (監督學習)。

1.3 聚類過程

數據準備：包括特征標準化和降維;
特征選擇：從最初的特征中選擇最有效的特征,并將其存儲于向量中;
特征提取：通過對所選擇的特征進行轉換形成新的突出特征;
聚類(或分組)：首先選擇合適特征類型的某種距離函數(或構造新的距離函數)進行接近程度的度量，而后執行聚類或分組;
聚類結果評估：是指對聚類結果進行評估，評估主要有3種：外部有效性評估、內部有效性評估和相關性測試評估。

1.4 衡量聚類算法優劣的標準

處理大的數據集的能力;
處理任意形狀，包括有間隙的嵌套的數據的能力;
算法處理的結果與數據輸入的順序是否相關，也就是說算法是否獨立于數據輸入順序;
處理數據噪聲的能力;
是否需要預先知道聚類個數，是否需要用戶給出領域知識;
算法處理有很多屬性數據的能力，也就是對數據維數是否敏感。

2. 聚類方法的分類

主要分為層次化聚類算法，劃分式聚類算法，基于密度的聚類算法，基于網格的聚類算法，基于模型的聚類算法等。

2.1 層次化聚類算法

又稱樹聚類算法，透過一種層次架構方式，反復將數據進行分裂或聚合。典型的有BIRCH算法，CURE算法，CHAMELEON算法，Sequence data rough clustering算法,Between groups average算法,Furthest neighbor算法,Neares neighbor算法等。

典型凝聚型層次聚類：

先將每個對象作為一個簇，然后合并這些原子簇為越來越大的簇，直到所有對象都在一個簇中，或者某個終結條件被滿足。

算法流程：

將每個對象看作一類，計算兩兩之間的最小距離;
將距離最小的兩個類合并成一個新類;
重新計算新類與所有類之間的距離;
重復2、3，直到所有類最后合并成一類。

2.2 劃分式聚類算法

預先指定聚類數目或聚類中心，反復迭代逐步降低目標函數誤差值直至收斂，得到最終結果。K-means,K-modes-Huang,K-means-CP,MDS_CLUSTER, Feature weighted fuzzy clustering，CLARANS等

經典K-means算法流程：

隨機地選擇k個對象，每個對象初始地代表了一個簇的中心;
對剩余的每個對象，根據其與各簇中心的距離，將它賦給最近的簇;
重新計算每個簇的平均值，更新為新的簇中心;
不斷重復2、3，直到準則函數收斂。

2.3 基于模型的聚類算法

為每簇假定了一個模型，尋找數據對給定模型的最佳擬合，同一”類“的數據屬于同一種概率分布，即假設數據是根據潛在的概率分布生成的。主要有基于統計學模型的方法和基于神經網絡模型的方法，尤其以基于概率模型的方法居多。一個基于模型的算法可能通過構建反應數據點空間分布的密度函數來定位聚類。基于模型的聚類試圖優化給定的數據和某些數據模型之間的適應性。

SOM神經網絡算法：

該算法假設在輸入對象中存在一些拓撲結構或順序，可以實現從輸入空間(n維)到輸出平面(2維)的降維映射，其映射具有拓撲特征保持性質,與實際的大腦處理有很強的理論聯系。

SOM網絡包含輸入層和輸出層。輸入層對應一個高維的輸入向量，輸出層由一系列組織在2維網格上的有序節點構成，輸入節點與輸出節點通過權重向量連接。學習過程中，找到與之距離最短的輸出層單元，即獲勝單元，對其更新。同時，將鄰近區域的權值更新，使輸出節點保持輸入向量的拓撲特征。

算法流程：

網絡初始化，對輸出層每個節點權重賦初值;
將輸入樣本中隨機選取輸入向量，找到與輸入向量距離最小的權重向量;
定義獲勝單元，在獲勝單元的鄰近區域調整權重使其向輸入向量靠攏;
提供新樣本、進行訓練;
收縮鄰域半徑、減小學習率、重復，直到小于允許值，輸出聚類結果。

2.4 基于密度聚類算法

主要思想：

只要鄰近區域的密度(對象或數據點的數目)超過某個閾值，就繼續聚類

擅于解決不規則形狀的聚類問題，廣泛應用于空間信息處理,SGC,GCHL，DBSCAN算法、OPTICS算法、DENCLUE算法。

DBSCAN：

對于集中區域效果較好，為了發現任意形狀的簇，這類方法將簇看做是數據空間中被低密度區域分割開的稠密對象區域;一種基于高密度連通區域的基于密度的聚類方法，該算法將具有足夠高密度的區域劃分為簇，并在具有噪聲的空間數據中發現任意形狀的簇。

2.5 基于網格的聚類算法

基于網格的方法把對象空間量化為有限數目的單元，形成一個網格結構。所有的聚類操作都在這個網格結構(即量化空間)上進行。這種方法的主要優點是它的處理速度很快，其處理速度獨立于數據對象的數目，只與量化空間中每一維的單元數目有關。但這種算法效率的提高是以聚類結果的精確性為代價的。經常與基于密度的算法結合使用。

代表算法有STING算法、CLIQUE算法、WAVE-CLUSTER算法等。

2.6 新發展的方法

基于約束的方法：

真實世界中的聚類問題往往是具備多種約束條件的 , 然而由于在處理過程中不能準確表達相應的約束條件、不能很好地利用約束知識進行推理以及不能有效利用動態的約束條件 , 使得這一方法無法得到廣泛的推廣和應用。這里的約束可以是對個體對象的約束 , 也可以是對聚類參數的約束 , 它們均來自相關領域的經驗知識。該方法的一個重要應用在于對存在障礙數據的二維空間數據進行聚類。 COD (Clustering with Ob2structed Distance) 就是處理這類問題的典型算法 , 其主要思想是用兩點之間的障礙距離取代了一般的歐氏距離來計算其間的最小距離。

基于模糊的聚類方法：

基于模糊集理論的聚類方法，樣本以一定的概率屬于某個類。比較典型的有基于目標函數的模糊聚類方法、基于相似性關系和模糊關系的方法、基于模糊等價關系的傳遞閉包方法、基于模糊圖論的最小支撐樹方法，以及基于數據集的凸分解、動態規劃和難以辨別關系等方法。

FCM模糊聚類算法流程：

標準化數據矩陣;
建立模糊相似矩陣，初始化隸屬矩陣;
算法開始迭代，直到目標函數收斂到極小值;
根據迭代結果，由最后的隸屬矩陣確定數據所屬的類，顯示最后的聚類結果。

基于粒度的聚類方法：

基于粒度原理，研究還不完善。

量子聚類：

受物理學中量子機理和特性啟發，可以用量子理論解決聚類記過依賴于初值和需要指定類別數的問題。一個很好的例子就是基于相關點的 Pott 自旋和統計機理提出的量子聚類模型。它把聚類問題看做一個物理系統。并且許多算例表明，對于傳統聚類算法無能為力的幾種聚類問題，該算法都得到了比較滿意的結果。

核聚類：

核聚類方法增加了對樣本特征的優化過程，利用 Mercer 核把輸入空間的樣本映射到高維特征空間，并在特征空間中進行聚類。核聚類方法是普適的，并在性能上優于經典的聚類算法，它通過非線性映射能夠較好地分辨、提取并放大有用的特征，從而實現更為準確的聚類;同時，算法的收斂速度也較快。在經典聚類算法失效的情況下，核聚類算法仍能夠得到正確的聚類。代表算法有SVDD算法，SVC算法。

譜聚類：

首先根據給定的樣本數據集定義一個描述成對數據點相似度的親合矩陣,并計算矩陣的特征值和特征向量,然后選擇合適的特征向量聚類不同的數據點。譜聚類算法最初用于計算機視覺、VLSI設計等領域,最近才開始用于機器學習中,并迅速成為國際上機器學習領域的研究熱點。

譜聚類算法建立在圖論中的譜圖理論基礎上,其本質是將聚類問題轉化為圖的最優劃分問題,是一種點對聚類算法。