聚類演算法整理
- 介紹
- 相似性度量
- 常見的相似性度量演算法
- 聚類演算法的分類
- 傳統聚類
- 劃分聚類
- K-Means:
- 混合密度聚類：
- 圖聚類：
- 模糊聚類：
- 基于密度的劃分聚類：
- 層次聚類
- 智能聚類
- 人工神經網路聚類
- 核聚類
介紹
由于課題研究需要聚類演算法，故將看過的論文整理后發布在博客中，方便后續查看，
聚類的目的：達到類內的相似性與類間的排他性，也就是說具有相似特性的物件放到一起，
一般而言，聚類指將沒有分類標簽的資料集，分為若干個簇的程序，是一種無監督的分類方法，實際上，很難對聚類下一個明確的定義，因為聚類分析本身是一種建立在主觀判斷基礎上的相對行之有效的方法，
相似性度量
聚類分析是將資料集的相似性樣本歸為若干類的方法，因此，如何度量樣本之間的相似性是聚類演算法的關鍵問題
常見的相似性度量演算法
（1）歐氏距離
（2）馬氏距離
（3）相關系數
（4）余弦相似度
聚類演算法的分類
劃分聚類的里又包含傳統的基于劃分、基于密度、基于網路的聚類演算法
大小資料劃分是依據有效資料量1012位元組為閾值劃分體量
傳統聚類
劃分聚類
針對一個包含n 個樣本的資料集，先創建一個初始劃分; 然后采用一種迭代的重定位技術，通過樣本在類別間移動來改進聚類簇，
其代表演算法是K-Means、混合密度聚類、圖聚類、模糊聚類等
K-Means:
對于給定的樣本集，按照樣本之間的距離大小，將樣本集劃分為K個簇，讓簇內的點盡量緊密的連在一起，而讓簇間的距離盡量的大，
(由上圖的演算法流程，簡單來說，這個演算法就是隨機聚類中心，然后計算各個樣本與聚類中心的相似度進行分類，接著按照分類結果計算簇中心，再次計算所有樣本與簇中心的相似度，按此方法不斷迭代最后形成穩定的聚類結果)
聚類結果的好壞依賴于初始聚類中心的選擇;
對例外樣本點較為敏感
出現了很多改進，如：
用于處理例外資料的K-MEDOIDS
加速迭代程序的X-Means
克服只能處理數值型資料缺陷的K-MODES
混合密度聚類：
混合密度聚類演算法從概率分布的角度，假設樣本集有若干個內在的概率分布，然后利用不同的概率分布來劃分聚類簇，這樣，聚類程序變成了尋找幾個概率分布引數的程序，這些概率分布一般為常用的分布，如高斯分布、t 分布等，
圖聚類：
圖就是：頂點+邊構成的圖
頂點：樣本點
邊：樣本點的相似度
聚類：頂點的劃分
如下圖所示：
其中最具有代表的圖聚類演算法是譜聚類
譜聚類：是一種基于圖論的聚類方法，通過對樣本資料的拉普拉斯矩陣的特征向量進行分析來完成聚類，能夠識別任意形狀的聚類簇并可以收斂于全域最優解在影像分析領域有著廣泛的應用，
具體詳情可見劉老師的博客： 譜聚類.
模糊聚類：
大名鼎鼎的FCM，該演算法使用隸屬度來確定樣本點的相似性，通過隸屬度值大小來將樣本歸類，是一種基于目標函式的模糊聚類方法，目標函式如下：
FCM詳解（python）.
基于密度的劃分聚類：
將資料集看作低密度區域隔開的若干個高密度簇的集合，該方法的主要特點是可以識別任何形狀的簇，
如：DBSCAN
*除了傳統的劃分聚類演算法之外，還出現了一些新的劃分聚類演算法，如同步聚類、近鄰傳播（AP）聚類、密度峰值快速聚類DPC與大規模資料集聚類等，
層次聚類
按照構建樹形結構的方式不同，可以將聚類分為自頂向下和自底向上兩種構建方式，分別稱為聚合型層次聚類與分裂型層次聚類，下圖為層次聚類構建示意圖：
應用領域包括基因表達譜分析、文本聚類、并行工程組結構等
**聚合型層次聚類：**首先將每一個樣本都稱為一個聚類簇，然后計算簇間的相似度，分層合并，直到最后只有一個簇為止或滿足一定的終止條件，
**分裂型層次聚類：**首先將所有的樣本都看作是一個聚類簇，然后在每一步中，上層聚類簇被分裂為下層更小的聚類簇，直到每個簇只包含一個樣本，或者滿足終止條件為止，如：
- 使用具有代表性的一些點來代替聚類簇中的一個中心樣本的CURE演算法
- 對CURE演算法的改進，使之具有識別類別屬性功能的ROCK演算法
- 將原始資料轉化為二進制位資料，樣本點之間的相似性度量只在正位元位上進行的正二進制演算法
智能聚類
人工神經網路聚類
自組織映射（SOM）就是一種利用人工神經網路進行聚類的演算法，該方法將所有的樣本點逐一進行處理，并將聚類中心映射到二維空間，從而實作可視化，
與傳統的模式聚類方法相比，它所形成的聚類中心能映射到一個曲面或平面上，而保持拓撲結構不變，對于未知聚類中心的判別問題可以用自組織映射來實作，
核聚類
核聚類方法是將樣本點從輸入空間通過核函式映射到高維空間，這種非線性映射，將不能線性可分的資料集在高維特征空間中變得線性可分，從而在高維空間中利用線性方法完成聚類，這樣極大地提高了非線性聚類的性能和可伸縮性
**支持向量聚類演算法：**首先將輸入映射到高維空間，結合高維空間的點在輸入空間的位置特性，進行聚類劃分，下圖為高維空間的映射示意圖：
[說明]：由于大資料聚類演算法目前暫時用不到，所以只歸納到這里，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/232106.html
標籤：其他