一、聚類

1、聚類概念

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

2、聚類的目標

使同一類對象的相似度盡可能地大；不同類對象之間的相似度盡可能地小。

3、聚類和分類的區別

聚類技術通常又被稱為無監督學習，因為與監督學習不同，在聚類中那些表示數據類別的分類或者分組信息是沒有的。?
Clustering (聚類)，簡單地說就是把相似的東西分到一組，聚類的時候，我們并不關心某一類是什么，我們需要實現的目標只是把相似的東西聚到一起。因此，一個聚類算法通常只需要知道如何計算相似度就可以開始工作了，因此 clustering 通常并不需要使用訓練數據進行學習，這在Machine Learning中被稱作unsupervised learning (無監督學習)。?
Classification (分類)，對于一個classifier，通常需要你告訴它“這個東西被分為某某類”這樣一些例子，理想情況下，一個 classifier 會從它得到的訓練集中進行“學習”，從而具備對未知數據進行分類的能力，這種提供訓練數據的過程通常叫做supervised learning (監督學習)。

二、聚類算法的分類

1.基于劃分

1.1基本思想

基于劃分的方法：其原理簡單來說就是，想象你有一堆散點需要聚類，想要的聚類效果就是“類內的點都足夠近，類間的點都足夠遠”。首先你要確定這堆散點最后聚成幾類，然后挑選幾個點作為初始中心點，再然后給數據點做迭代重置（iterative relocation），直到最后到達“類內的點都足夠近，類間的點都足夠遠”的目標效果。也正是根據所謂的“啟發式算法”，形成了k-means算法及其變體包括k-medoids、k-modes、k-medians、kernel k-means等算法。

1.2特點

計算量大，很適合發現中小規模的數據庫中小規模的數據庫中的球狀簇。

1.3主要算法

k-means、k-medoids、k-modes、k-medians、kernel k-means等算法。

1.4算法流程

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

1.5算法優缺點

優點：對于大型數據集也是簡單高效、時間復雜度、空間復雜度低。?
缺點：最重要是數據集大時結果容易局部最優；需要預先設定K值，對最先的K個點選取很敏感；對噪聲和離群值非常敏感；只用于numerical類型數據；不能解決非凸（non-convex）數據。

1.6常見的算法及改進

k-means對初始值的設置很敏感，所以有了k-means++、intelligent k-means、genetic k-means。?
k-means對噪聲和離群值非常敏感，所以有了k-medoids和k-medians。?
k-means只用于numerical類型數據，不適用于categorical類型數據，所以k-modes。?
k-means不能解決非凸（non-convex）數據，所以有了kernel k-means。?
另外，很多教程都告訴我們Partition-based methods聚類多適用于中等體量的數據集，但我們也不知道“中等”到底有多“中”，所以不妨理解成，數據集越大，越有可能陷入局部最小。

2.基于層次

2.1基本思想

層次聚類主要有兩種類型：合并的層次聚類和分裂的層次聚類。前者是一種自底向上的層次聚類算法，從最底層開始，每一次通過合并最相似的聚類來形成上一層次中的聚類，整個當全部數據點都合并到一個聚類的時候停止或者達到某個終止條件而結束，大部分層次聚類都是采用這種方法處理。后者是采用自頂向下的方法，從一個包含全部數據點的聚類開始，然后把根節點分裂為一些子聚類，每個子聚類再遞歸地繼續往下分裂，直到出現只包含一個數據點的單節點聚類出現，即每個聚類中僅包含一個數據點。

2.2特點

處理速度很快，通常這是與目標數據庫中記錄的個數無關的，只與把數據空間分為多少個單元有關。

2.3主要算法

BIRCH算法、CURE算法、CHAMELEON算法

2.4算法流程

以下流程以自下向上為例。?
1. 將每個對象看作一類，計算兩兩之間的最小距離；?
2. 將距離最小的兩個類合并成一個新類；?
3. 重新計算新類與所有類之間的距離；?
4. 重復2、3，直到所有類最后合并成一類

2.5算法優缺點

優點：可解釋性好（如當需要創建一種分類法時）；還有些研究表明這些算法能產生高質量的聚類，也會應用在上面說的先取K比較大的K-means后的合并階段；還有對于K-means不能解決的非球形族就可以解決了。?
缺點：時間復雜度高啊，o(m^3)，改進后的算法也有o(m^2lgm)，m為點的個數；貪心算法的缺點，一步錯步步錯；同K-means，difficulty handling different sized clusters and convex shapes。

2.6常見的算法及改進

該聚類算法因為計算復雜度比較大適用于小數量級，如對中國省會城市聚類。改進的算法有BIRCH（Balanced Iterative Reducing and Clustering Using Hierarchies）主要是在數據體量很大的時候使用，而且數據類型是numerical。?
Chameleon（A Hierarchical Clustering Algorithm Using Dynamic Modeling）里用到的linkage是kNN（k-nearest-neighbor）算法，并以此構建一個graph，Chameleon的聚類效果被認為非常強大，比BIRCH好用，但運算復雜還是很高，O(n^2)。看個Chameleon的聚類效果圖，其中一個顏色代表一類，可以看出來是可以處理非常復雜的形狀的。?

3.基于密度

3.1基本思想

基于密度的方法：k-means解決不了不規則形狀的聚類。于是就有了Density-based methods來系統解決這個問題。該方法同時也對噪聲數據的處理比較好。其原理簡單說畫圈兒，其中要定義兩個參數，一個是圈兒的最大半徑，一個是一個圈兒里最少應容納幾個點。只要鄰近區域的密度（對象或數據點的數目）超過某個閾值，就繼續聚類,最后在一個圈里的，就是一個類。DBSCAN（Density-Based Spatial Clustering of Applications with Noise）就是其中的典型.

3.2特點

能克服基于距離的算法只能發現“類圓形”的聚類的缺點。

3.3主要算法

DBSCAN算法、OPTICS算法、DENCLUE算法

3.4算法流程

DBSCAN流程：?
1. 從任一對象點p開始；?
2. 尋找并合并核心p對象直接密度可達（eps）的對象；?
3. 如果p是一個核心點，則找到了一個聚類，如果p是一個邊界點（即從p沒有密度可達的點）則尋找下一個對象點；?
4. 重復2、3，直到所有點都被處理

3.5算法優缺點

優點：對噪聲不敏感；能發現任意形狀的聚類。?
缺點：聚類的結果與參數有很大的關系；DBSCAN用固定參數識別聚類，但當聚類的稀疏程度不同時，相同的判定標準可能會破壞聚類的自然結構，即較稀的聚類會被劃分為多個類或密度較大且離得較近的類會被合并成一個聚類。

3.6常見的算法及改進

DBSCAN對這兩個參數的設置非常敏感。DBSCAN的擴展叫OPTICS（Ordering Points To Identify Clustering Structure）通過優先對高密度（high density）進行搜索，然后根據高密度的特點設置參數，改善了DBSCAN的不足。

4.基于網格

4.1基本思想

基于網絡的方法：這類方法的原理就是將數據空間劃分為網格單元，將數據對象集映射到網格單元中，并計算每個單元的密度。根據預設的閾值判斷每個網格單元是否為高密度單元，由鄰近的稠密單元組形成”類“。

4.2特點

處理速度很快，通常這是與目標數據庫中記錄的個數無關的，只與把數據空間分為多少個單元有關。?

4.3主要算法

STING算法、CLIQUE算法、WAVE-CLUSTER算法

4.4算法流程

這些算法用不同的網格劃分方法，將數據空間劃分成為有限個單元（cell）的網格結構,并對網格數據結構進行了不同的處理，但核心步驟是相同的：?
1、 劃分網格?
2、 使用網格單元內數據的統計信息對數據進行壓縮表達?
3、 基于這些統計信息判斷高密度網格單元?
4、 最后將相連的高密度網格單元識別為簇

4.5算法優缺點

優點：速度很快，因為其速度與數據對象的個數無關，而只依賴于數據空間中每個維上單元的個數。?
缺點：參數敏感、無法處理不規則分布的數據、維數災難等；這種算法效率的提高是以聚類結果的精確性為代價的。經常與基于密度的算法結合使用。

4.6常見的算法及改進

STING（STatistical INformation Grid）算法、WAVE-CLUSTER算法和CLIQUE（CLustering In QUEst）是該類方法中的代表性算法。

5、基于模型的方法（Model-based methods）

5.1基本思想

基于模型的方法：為每簇假定了一個模型，尋找數據對給定模型的最佳擬合，這一類方法主要是指基于概率模型的方法和基于神經網絡模型的方法，尤其以基于概率模型的方法居多。這里的概率模型主要指概率生成模型（generative Model），同一”類“的數據屬于同一種概率分布，即假設數據是根據潛在的概率分布生成的。其中最典型、也最常用的方法就是高斯混合模型（GMM，Gaussian Mixture Models）。基于神經網絡模型的方法主要就是指SOM（Self Organized Maps）了，也是我所知的唯一一個非監督學習的神經網絡了。下圖表現的就是GMM的一個demo，里面用到EM算法來做最大似然估計。?

5.2算法流程

【以SOM為例】SOM神經網絡是由芬蘭神經網絡專家Kohonen教授提出的，該算法假設在輸入對象中存在一些拓撲結構或順序，可以實現從輸入空間(n維)到輸出平面(2維)的降維映射，其映射具有拓撲特征保持性質,與實際的大腦處理有很強的理論聯系。?
SOM網絡包含輸入層和輸出層。輸入層對應一個高維的輸入向量，輸出層由一系列組織在2維網格上的有序節點構成，輸入節點與輸出節點通過權重向量連接。學習過程中，找到與之距離最短的輸出層單元，即獲勝單元，對其更新。同時，將鄰近區域的權值更新，使輸出節點保持輸入向量的拓撲特征。?
算法流程：?
1、 網絡初始化，對輸出層每個節點權重賦初值；?
2、 將輸入樣本中隨機選取輸入向量，找到與輸入向量距離最小的權重向量；?
3、定義獲勝單元，在獲勝單元的鄰近區域調整權重使其向輸入向量靠攏；?
4、 提供新樣本、進行訓練；?
5、收縮鄰域半徑、減小學習率、重復，直到小于允許值，輸出聚類結果。

5.3算法優缺點

優點：對”類“的劃分不那么”堅硬“，而是以概率形式表現，每一類的特征也可以用參數來表達。?
缺點：執行效率不高，特別是分布數量很多并且數據量很少的時候。

5.4常見的算法及改進

基于概率模型的最典型、也最常用的方法就是高斯混合模型（GMM，Gaussian Mixture Models）。基于神經網絡模型的方法主要就是指SOM（Self Organized Maps）了.

6、基于模糊的聚類（FCM模糊聚類）

6.1基本思想

1965年美國加州大學柏克萊分校的扎德教授第一次提出了‘集合’的概念。經過十多年的發展，模糊集合理論漸漸被應用到各個實際應用方面。為克服非此即彼的分類缺點，出現了以模糊集合論為數學基礎的聚類分析。用模糊數學的方法進行聚類分析，就是模糊聚類分析。?
基于模糊集理論的聚類方法，樣本以一定的概率屬于某個類。比較典型的有基于目標函數的模糊聚類方法、基于相似性關系和模糊關系的方法、基于模糊等價關系的傳遞閉包方法、基于模 糊圖論的最小支撐樹方法，以及基于數據集的凸分解、動態規劃和難以辨別關系等方法。FCM算法是一種以隸屬度來確定每個數據點屬于某個聚類程度的算法。該聚類算法是傳統硬聚類算法的一種改進。

6.2算法流程

FCM模糊聚類算法流程：?
1、 標準化數據矩陣；?
2、 建立模糊相似矩陣，初始化隸屬矩陣；?
3、 算法開始迭代，直到目標函數收斂到極小值；?
4、 根據迭代結果，由最后的隸屬矩陣確定數據所屬的類，顯示最后的聚類結果。?
FCM算法需要兩個參數一個是聚類數目C，另一個是參數m。一般來講C要遠遠小于聚類樣本的總個數，同時要保證C>1。對于m，它是一個控制算法的柔性的參數，如果m過大，則聚類效果會很次，而如果m過小則算法會接近HCM聚類算法。?
算法的輸出是C個聚類中心點向量和C*N的一個模糊劃分矩陣，這個矩陣表示的是每個樣本點屬于每個類的隸屬度。根據這個劃分矩陣按照模糊集合中的最大隸屬原則就能夠確定每個樣本點歸為哪個類。聚類中心表示的是每個類的平均特征，可以認為是這個類的代表點。

6.3算法優缺點

優點：從算法的推導過程中我們不難看出，算法對于滿足正態分布的數據聚類效果會很好，另外，算法對孤立點是敏感的。?
缺點：由于不能確保FCM收斂于一個最優解。算法的性能依賴于初始聚類中心。因此，我們要么用另外的快速算法確定初始聚類中心，要么每次用不同的初始聚類中心啟動該算法，多次運行FCM。

6.4常見的算法及改進

模糊C均值（簡稱FCM）聚類算法是HCM聚類算法的改進。

總結

以上是生活随笔為你收集整理的聚类及聚类算法的分类的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。