本文***計2680字，預計閱讀時長七分鐘
聚類算法
?
壹 、 本質
將數據劃分到不同的類裏，使相似的數據在同壹類裏，不相似的數據在不同類裏
?
二 、 分類算法用來解決什麽問題
文本聚類、圖像聚類和商品聚類，便於發現規律，以解決數據稀疏問題
三 、 聚類算法基礎知識
1. 層次聚類?vs?非層次聚類
– 不同類之間有無包含關系
2. 硬聚類?vs?軟聚類
– 硬聚類：每個對象只屬於壹個類
– 軟聚類：每個對象以某個概率屬於每個類
3. 用向量表示對象
– 每個對象用壹個向量表示，可以視為高維空間的壹個點
– 所有對象形成數據空間（矩陣）
– 相似度計算：Cosine、點積、質心距離
4. 用矩陣列出對象之間的距離、相似度
5. 用字典保存上述矩陣（節省空間）
D={(1,1):0,(1,2):2,(1,3):6...(5,5):0}
6. 評價方法
– 內部評價法（Internal Evalution）：
? 沒有外部標準，非監督式
? 同類是否相似，跨類是否相異
DB值越小聚類效果越好，反之，越不好
– 外部評價法（External Evalution）：
?準確度（accuracy）: (C11+C22) / (C11 + C12 + C21 + C22)
?精度（Precision）: C11 / (C11 + C21 )
?召回（Recall）: C11 / (C11 + C12 )
?F值（F-measure）：
β表示對精度P的重視程度，越大越重視，默認設置為1，即變成了F值，F較高時則能說明聚類效果較好。
四 、 有哪些聚類算法
主要分為 層次化聚類算法 ， 劃分式聚類算法 ， 基於密度的聚類算法 ， 基於網格的聚類算法 ， 基於模型的聚類算法等 。
4.1 層次化聚類算法
又稱樹聚類算法，透過壹種層次架構方式，反復將數據進行分裂或聚合。典型的有BIRCH算法，CURE算法，CHAMELEON算法，Sequence data rough clustering算法,Between groups average算法,Furthest neighbor算法,Neares neighbor算法等。
凝聚型層次聚類 ：
先將每個對象作為壹個簇，然後合並這些原子簇為越來越大的簇，直到所有對象都在壹個簇中，或者某個終結條件被滿足。
算法流程：
1. 將每個對象看作壹類，計算兩兩之間的最小距離；
2. 將距離最小的兩個類合並成壹個新類；
3. 重新計算新類與所有類之間的距離；
4. 重復2、3，直到所有類最後合並成壹類。
特點：
1. 算法簡單
2. 層次用於概念聚類（生成概念、文檔層次樹）
3. 聚類對象的兩種表示法都適用
4. 處理大小不同的簇
5. 簇選取步驟在樹狀圖生成之後
4.2 劃分式聚類算法
預先指定聚類數目或聚類中心，反復叠代逐步降低目標函數誤差值直至收斂，得到最終結果。K-means,K-modes-Huang,K-means-CP,MDS_CLUSTER, Feature weighted fuzzy clustering，CLARANS等
經典K-means：
算法流程：
1. 隨機地選擇k個對象，每個對象初始地代表了壹個簇的中心；
2. 對剩余的每個對象，根據其與各簇中心的距離，將它賦給最近的簇；
3. 重新計算每個簇的平均值，更新為新的簇中心；
4. 不斷重復2、3，直到準則函數收斂。
特點：
1.K的選擇
2.中心點的選擇
– 隨機
– 多輪隨機：選擇最小的WCSS
3.優點
– 算法簡單、有效
– 時間復雜度：O(nkt)
4.缺點
– 不適於處理球面數據
– 密度、大小不同的聚類，受K的限制，難於發現自然的聚類
4.3 基於模型的聚類算法
為每簇假定了壹個模型，尋找數據對給定模型的最佳擬合，同壹”類“的數據屬於同壹種概率分布，即假設數據是根據潛在的概率分布生成的。主要有基於統計學模型的方法和基於神經網絡模型的方法，尤其以基於概率模型的方法居多。壹個基於模型的算法可能通過構建反應數據點空間分布的密度函數來定位聚類。基於模型的聚類試圖優化給定的數據和某些數據模型之間的適應性。
SOM 神經網絡算法 ：
該算法假設在輸入對象中存在壹些拓撲結構或順序，可以實現從輸入空間(n維)到輸出平面(2維)的降維映射，其映射具有拓撲特征保持性質,與實際的大腦處理有很強的理論聯系。
SOM網絡包含輸入層和輸出層。輸入層對應壹個高維的輸入向量，輸出層由壹系列組織在2維網格上的有序節點構成，輸入節點與輸出節點通過權重向量連接。學習過程中，找到與之距離最短的輸出層單元，即獲勝單元，對其更新。同時，將鄰近區域的權值更新，使輸出節點保持輸入向量的拓撲特征。
算法流程：
1. 網絡初始化，對輸出層每個節點權重賦初值；
2. 將輸入樣本中隨機選取輸入向量，找到與輸入向量距離最小的權重向量；
3. 定義獲勝單元，在獲勝單元的鄰近區域調整權重使其向輸入向量靠攏；
4. 提供新樣本、進行訓練；
5. 收縮鄰域半徑、減小學習率、重復，直到小於允許值，輸出聚類結果。
4.4 基於密度聚類算法
只要鄰近區域的密度（對象或數據點的數目）超過某個閾值，就繼續聚類，擅於解決不規則形狀的聚類問題，廣泛應用於空間信息處理,SGC,GCHL，DBSCAN算法、OPTICS算法、DENCLUE算法。
DBSCAN：
對於集中區域效果較好，為了發現任意形狀的簇，這類方法將簇看做是數據空間中被低密度區域分割開的稠密對象區域；壹種基於高密度連通區域的基於密度的聚類方法，該算法將具有足夠高密度的區域劃分為簇，並在具有噪聲的空間數據中發現任意形狀的簇。
4.5 基於網格的聚類算法
基於網格的方法把對象空間量化為有限數目的單元，形成壹個網格結構。所有的聚類操作都在這個網格結構（即量化空間）上進行。這種方法的主要優點是它的處理?速度很快，其處理速度獨立於數據對象的數目，只與量化空間中每壹維的單元數目有關。但這種算法效率的提高是以聚類結果的精確性為代價的。經常與基於密度的算法結合使用。代表算法有STING算法、CLIQUE算法、WAVE-CLUSTER算法等。?