基于圖的聚類分析研究—張濤
【磐創(chuàng)AI導(dǎo)讀】：本文介紹了常用的聚類算法及聚類算法評價指標(biāo)。想要獲取更多的機器學(xué)習(xí)、深度學(xué)習(xí)資源，歡迎大家的公眾號：磐創(chuàng)AI。

1. 典型聚類算法

1.1 基于劃分的方法

代表：kmeans算法

·指定k個聚類中心
·（計算數(shù)據(jù)點與初始聚類中心的距離）
·（對于數(shù)據(jù)點，找到最近的{i}ci(聚類中心)，將分配到{i}ci中）
·(更新聚類中心點，是新類別數(shù)值的均值點)
·（計算每一類的偏差）
·返回
返回第二步

1.2 基于層次的方法

代表：CURE算法

·每個樣本作為單獨的一個類別
·
·合并,為
·遍歷完本次樣本，合并成新的類別后，若存在多個類別，則返回第二步
·遍歷完本次樣本，合并成新的類別后，若所有樣本為同一類別，跳出循環(huán)，輸出每層類別

1.3 基于網(wǎng)格的方法

代表：STING算法

·將數(shù)據(jù)集合X劃分多層網(wǎng)格結(jié)構(gòu)，從某一層開始計算
·查詢該層網(wǎng)格間的屬性值，計算屬性值與閾值的關(guān)系，判定網(wǎng)格間的相關(guān)情況，不相關(guān)的網(wǎng)格不作考慮
·如果網(wǎng)格相關(guān)，則進入下一層的相關(guān)區(qū)域繼續(xù)第二步，直到下一層為最底層
·返回相關(guān)網(wǎng)格結(jié)果

1.4 基于密度的方法

代表：DBSCAN算法

·輸入數(shù)據(jù)集合X，隨機選取一點，并找出這個點的所有高密度可達點
·遍歷此點的所有鄰域內(nèi)的點，并尋找這些密度可達點，判定某點鄰域內(nèi)的點，并尋找這些點密度可達點，判定某點的鄰域內(nèi)的點數(shù)是否超過閾值點數(shù)，超過則構(gòu)成核心點
·掃描數(shù)據(jù)集，尋找沒有被聚類的數(shù)據(jù)點，重復(fù)第二步
·輸出劃分的類，并輸出異常值點（不和其他密度相連）

1.5 神經(jīng)網(wǎng)絡(luò)的方法

代表：SOM算法

·數(shù)據(jù)集合，權(quán)重向量為，，歸一化處理
·尋找獲勝的神經(jīng)元，找到最小距離，對于每一個輸入數(shù)據(jù)，找到與之最相匹配的節(jié)點
令為為的距離，更新權(quán)重：
·更新臨近節(jié)點，，其中代表學(xué)習(xí)率

1.6 基于圖的聚類方法

代表：譜聚類算法

·計算鄰接矩陣，度矩陣，
·計算拉普拉及矩陣
·計算歸一化拉普拉斯矩陣
·計算的特征值和特征向量
·對Q矩陣進行聚類，得到聚類結(jié)果

2. 聚類算法的評價指標(biāo)

一個好的聚類方法可以產(chǎn)生高品質(zhì)簇，是的簇內(nèi)相似度高，簇間相似度低。一般來說，評估聚類質(zhì)量有兩個標(biāo)準，內(nèi)部質(zhì)量評價指標(biāo)和外部評價指標(biāo)。

2.1 內(nèi)部質(zhì)量評價標(biāo)準

內(nèi)部評價指標(biāo)是利用數(shù)據(jù)集的屬性特征來評價聚類算法的優(yōu)劣。通過計算總體的相似度，簇間平均相似度或簇內(nèi)平均相似度來評價聚類質(zhì)量。評價聚類效果的高低通常使用聚類的有效性指標(biāo)，所以目前的檢驗聚類的有效性指標(biāo)主要是通過簇間距離和簇內(nèi)距離來衡量。這類指標(biāo)常用的有CH（Calinski-Harabasz）指標(biāo)等

CH指標(biāo)

CH指標(biāo)定義為：

其中表示類間距離差矩陣的跡，表示類內(nèi)離差矩陣的跡，是整個數(shù)據(jù)集的均值，是第個簇的均值，代表聚類個數(shù)，代表當(dāng)前的類。值越大，聚類效果越好，主要計算簇間距離與簇內(nèi)距離的比值

簇的凝聚度

簇內(nèi)點對的平均距離反映了簇的凝聚度，一般使用組內(nèi)誤差平方（SSE）表示：

簇的鄰近度

簇的鄰近度用組間平方和（SSB）表示，即簇的質(zhì)心到簇內(nèi)所有數(shù)據(jù)點的總平均值的距離的平方和

2.2 外部質(zhì)量評價標(biāo)準

外部質(zhì)量評價指標(biāo)是基于已知分類標(biāo)簽數(shù)據(jù)集進行評價的，這樣可以將原有標(biāo)簽數(shù)據(jù)與聚類輸出結(jié)果進行對比。外部質(zhì)量評價指標(biāo)的理想聚類結(jié)果是：具有不同類標(biāo)簽的數(shù)據(jù)聚合到不同的簇中，具有相同類標(biāo)簽的數(shù)據(jù)聚合相同的簇中。外部質(zhì)量評價準則通常使用熵，純度等指標(biāo)進行度量。

熵：

簇內(nèi)包含單個類對象的一種度量。對于每一個簇，首先計算數(shù)據(jù)的類分布，即對于簇，計算簇的成員屬于類的概率

其中表示簇中所有對象的個數(shù)，而是簇中類的對象個數(shù)。使用類分布，用標(biāo)準公式：

計算每個簇的熵，其中K是類個數(shù)。簇集合的總熵用每個簇的熵的加權(quán)和計算即：

其中是簇的個數(shù)，而是簇內(nèi)數(shù)據(jù)點的總和

純度：

簇內(nèi)包含單個類對象的另外一種度量。簇的純度為，而聚類總純度為：