聚類分析經(jīng)典算法講解及實(shí)現(xiàn)

常用聚類算法比較分析

K-pototypes算法

K-pototypes算法結(jié)合了K-means方法和根據(jù)K-means方法改進(jìn)的能夠處理符號(hào)屬性的K-modes方法，同K-means方法相比，K-pototypes 算法能夠處理符號(hào)屬性。

CLARANS算法（劃分方法）

CLARANS算法即隨機(jī)搜索聚類算法，是一種分割聚類方法。它首先隨機(jī)選擇一個(gè)點(diǎn)作為當(dāng)前點(diǎn)，然后隨機(jī)檢查它周圍不超過(guò)參數(shù)Maxneighbor 個(gè)的一些鄰接點(diǎn)，假如找到一個(gè)比它更好的鄰接點(diǎn)，則把它移人該鄰接點(diǎn)，否則把該點(diǎn)作為局部最小量。然后再隨機(jī)選擇一個(gè)點(diǎn)來(lái)尋找另一個(gè)局部最小量，直至所找 到的局部最小量數(shù)目達(dá)到用戶要求為止。該算法要求聚類的對(duì)象必須都預(yù)先調(diào)人內(nèi)存，并且需多次掃描數(shù)據(jù)集，這對(duì)大數(shù)據(jù)量而言，無(wú)論時(shí)間復(fù)雜度還是空間復(fù)雜度 都相當(dāng)大。雖通過(guò)引人R-樹結(jié)構(gòu)對(duì)其性能進(jìn)行改善，使之能夠處理基于磁盤的大型數(shù)據(jù)庫(kù)，但R*-樹的構(gòu)造和維護(hù)代價(jià)太大。該算法對(duì)臟數(shù)據(jù)和異常數(shù)據(jù)不敏 感，但對(duì)數(shù)據(jù)物人順序異常敏感，且只能處理凸形或球形邊界聚類。

BIRCH算法（層次方法）

BIRCH算法即平衡迭代削減聚類法，其核心是用一個(gè)聚類特征3元組表示一個(gè)簇的有關(guān)信息，從而使一簇點(diǎn)的表示可用對(duì)應(yīng)的聚類特征，而不必用具體的一 組點(diǎn)來(lái)表示。它通過(guò)構(gòu)造滿足分支因子和簇直徑限制的聚類特征樹來(lái)求聚類。BIRCH算法通過(guò)聚類特征可以方便地進(jìn)行中心、半徑、直徑及類內(nèi)、類間距離的運(yùn) 算。算法的聚類特征樹是一個(gè)具有兩個(gè)參數(shù)分枝因子B和類直徑T的高度平衡樹。分枝因子規(guī)定了樹的每個(gè)節(jié)點(diǎn)子女的最多個(gè)數(shù)，而類直徑體現(xiàn)了對(duì)一類點(diǎn)的直徑大 小的限制即這些點(diǎn)在多大范圍內(nèi)可以聚為一類，非葉子結(jié)點(diǎn)為它的子女的最大關(guān)鍵字，可以根據(jù)這些關(guān)鍵字進(jìn)行插人索引，它總結(jié)了其子女的信息。

聚類特征樹可以動(dòng)態(tài)構(gòu)造，因此不要求所有數(shù)據(jù)讀人內(nèi)存，而可以在外存上逐個(gè)讀人。新的數(shù)據(jù)項(xiàng)總是插人到樹中與該數(shù)據(jù)距離最近的葉子中。如果插人后使得 該葉子的直徑大于類直徑T，則把該葉子節(jié)點(diǎn)分裂。其它葉子結(jié)點(diǎn)也需要檢查是否超過(guò)分枝因子來(lái)判斷其分裂與否，直至該數(shù)據(jù)插入到葉子中，并且滿足不超過(guò)類直 徑，而每個(gè)非葉子節(jié)點(diǎn)的子女個(gè)數(shù)不大于分枝因子。算法還可以通過(guò)改變類直徑修改特征樹大小，控制其占內(nèi)存容量。

BIRCH算法通過(guò)一次掃描就可以進(jìn)行較好的聚類，由此可見(jiàn)，該算法適合于大數(shù)據(jù)量。對(duì)于給定的M兆內(nèi)存空間，其空間復(fù)雜度為O（M），時(shí)間間復(fù)雜度 為O（dNBlnB（M/P））。其中d為維數(shù)，N為節(jié)點(diǎn)數(shù)，P為內(nèi)存頁(yè)的大小，B為由P決定的分枝因子。I/O花費(fèi)與數(shù)據(jù)量成線性關(guān)系。BIRCH算法 只適用于類的分布呈凸形及球形的情況，并且由于BIRCH算法需提供正確的聚類個(gè)數(shù)和簇直徑限制，對(duì)不可視的高維數(shù)據(jù)不可行。

CURE算法（層次方法）

CURE算法即使用代表點(diǎn)的聚類方法。該算法先把每個(gè)數(shù)據(jù)點(diǎn)看成一類，然后合并距離最近的類直至類個(gè)數(shù)為所要求的個(gè)數(shù)為止。CURE算法將傳統(tǒng)對(duì)類的 表示方法進(jìn)行了改進(jìn)，回避了用所有點(diǎn)或用中心和半徑來(lái)表示一個(gè)類，而是從每一個(gè)類中抽取固定數(shù)量、分布較好的點(diǎn)作為描述此類的代表點(diǎn)，并將這些點(diǎn)乘以一個(gè) 適當(dāng)?shù)氖湛s因子，使它們更靠近類的中心點(diǎn)。將一個(gè)類用代表點(diǎn)表示，使得類的外延可以向非球形的形狀擴(kuò)展，從而可調(diào)整類的形狀以表達(dá)那些非球形的類。另外， 收縮因子的使用減小了嗓音對(duì)聚類的影響。CURE算法采用隨機(jī)抽樣與分割相結(jié)合的辦法來(lái)提高算法的空間和時(shí)間效率，并且在算法中用了堆和K-d樹結(jié)構(gòu)來(lái)提 高算法效率。

DBSCAN算法（基于密度的方法）

DBSCAN算法即基于密度的聚類算法。該算法利用類的密度連通性可以快速發(fā)現(xiàn)任意形狀的類。其基本思想是：對(duì)于一個(gè)類中的每個(gè)對(duì)象，在其給定半徑的 領(lǐng)域中包含的對(duì)象不能少于某一給定的最小數(shù)目。在DBSCAN算法中，發(fā)現(xiàn)一個(gè)類的過(guò)程是基于這樣的事實(shí)：一個(gè)類能夠被其中的任意一個(gè)核心對(duì)象所確定。為 了發(fā)現(xiàn)一個(gè)類，DBSCAN先從對(duì)象集D中找到任意一對(duì)象P，并查找D中關(guān)于關(guān)徑Eps和最小對(duì)象數(shù)Minpts的從P密度可達(dá)的所有對(duì)象。如果P是核心 對(duì)象，即半徑為Eps的P的鄰域中包含的對(duì)象不少于Minpts，則根據(jù)算法，可以找到一個(gè)關(guān)于參數(shù)Eps和Minpts的類。如果P是一個(gè)邊界點(diǎn)，則半 徑為Eps的P鄰域包含的對(duì)象少于Minpts，P被暫時(shí)標(biāo)注為噪聲點(diǎn)。然后，DBSCAN處理D中的下一個(gè)對(duì)象。

密度可達(dá)對(duì)象的獲取是通過(guò)不斷執(zhí)行區(qū)域查詢來(lái)實(shí)現(xiàn)的。一個(gè)區(qū)域查詢返回指定區(qū)域中的所有對(duì)象。為了有效地執(zhí)行區(qū)域查詢，DBSCAN算法使用了空間查 詢R-樹結(jié)構(gòu)。在進(jìn)行聚類前，必須建立針對(duì)所有數(shù)據(jù)的R*-樹。另外，DBSCAN要求用戶指定一個(gè)全局參數(shù)Eps（為了減少計(jì)算量，預(yù)先確定參數(shù) Minpts）。為了確定取值，DBSCAN計(jì)算任意對(duì)象與它的第k個(gè)最臨近的對(duì)象之間的距離。然后，根據(jù)求得的距離由小到大排序，并繪出排序后的圖，稱 做k-dist圖。k-dist圖中的橫坐標(biāo)表示數(shù)據(jù)對(duì)象與它的第k個(gè)最近的對(duì)象間的距離；縱坐標(biāo)為對(duì)應(yīng)于某一k-dist距離值的數(shù)據(jù)對(duì)象的個(gè)數(shù)。 R*-樹的建立和k-dist圖的繪制非常消耗時(shí)間。此外，為了得到較好的聚類結(jié)果，用戶必須根據(jù)k-dist圖，通過(guò)試探選定一個(gè)比較合適的Eps值。 DBSCAN算法不進(jìn)行任何的預(yù)處理而直接對(duì)整個(gè)數(shù)據(jù)集進(jìn)行聚類操作。當(dāng)數(shù)據(jù)量非常大時(shí)，就必須有大內(nèi)存量支持，I/O消耗也非常大。其時(shí)間復(fù)雜度為 O（nlogn）（n為數(shù)據(jù)量），聚類過(guò)程的大部分時(shí)間用在區(qū)域查詢操作上。DBSCAN算法對(duì)參數(shù)Eps及Minpts非常敏感，且這兩個(gè)參數(shù)很難確定。

CLIQUE算法（綜合了基于密度和基于網(wǎng)格的算法）

CLIQUE算法即自動(dòng)子空間聚類算法。該算法利用自頂向上方法求出各個(gè)子空間的聚類單元。CLUQUE算法主要用于找出在高維數(shù)據(jù)空間中存在的低維 聚類。為了求出d維空間聚類，必須組合給出所有d-1維子空間的聚類，導(dǎo)致其算法的空間和時(shí)間效率都較低，而且要求用戶輸入兩個(gè)參數(shù)：數(shù)據(jù)取值空間等間隔 距離和密度闊值。這2個(gè)參數(shù)與樣木數(shù)據(jù)緊密相關(guān)，用戶一般難以確定。CLIQUE算法對(duì)數(shù)據(jù)輸人順序不敏感。

基于上述分析，我們得到各聚類算法的比較結(jié)果，結(jié)論如下：

K 均值算法詳解及實(shí)現(xiàn)

算法流程

K 均值算法，應(yīng)該是聚類算法中最為基礎(chǔ)但也最為重要的算法。其算法流程如下：

隨機(jī)的取 k 個(gè)點(diǎn)作為 k 個(gè)初始質(zhì)心；

計(jì)算其他點(diǎn)到這個(gè) k 個(gè)質(zhì)心的距離；

如果某個(gè)點(diǎn) p 離第 n 個(gè)質(zhì)心的距離更近，則該點(diǎn)屬于 cluster n，并對(duì)其打標(biāo)簽，標(biāo)注 point p.label=n，其中 n《=k；

計(jì)算同一 cluster 中，也就是相同 label 的點(diǎn)向量的平均值，作為新的質(zhì)心；

迭代至所有質(zhì)心都不變化為止，即算法結(jié)束。

當(dāng)然算法實(shí)現(xiàn)的方法有很多，比如在選擇初始質(zhì)心時(shí)，可以隨機(jī)選擇 k 個(gè)，也可以隨機(jī)選擇 k 個(gè)離得最遠(yuǎn)的點(diǎn)等等，方法不盡相同。

K 值估計(jì)

對(duì)于 k 值，必須提前知道，這也是 kmeans 算法的一個(gè)缺點(diǎn)。當(dāng)然對(duì)于 k 值，我們可以有很多種方法進(jìn)行估計(jì)。本文中，我們采用平均直徑法來(lái)進(jìn)行 k 的估計(jì)。

也就是說(shuō)，首先視所有的點(diǎn)為一個(gè)大的整體 cluster，計(jì)算所有點(diǎn)之間距離的平均值作為該 cluster 的平均直徑。選擇初始質(zhì)心的時(shí)候，先選擇最遠(yuǎn)的兩個(gè)點(diǎn)，接下來(lái)從這最兩個(gè)點(diǎn)開始，與這最兩個(gè)點(diǎn)距離都很遠(yuǎn)的點(diǎn)（遠(yuǎn)的程度為，該點(diǎn)到之前選擇的最遠(yuǎn)的兩個(gè)點(diǎn)的距離都大于整體 cluster 的平均直徑）可視為新發(fā)現(xiàn)的質(zhì)心，否則不視之為質(zhì)心。設(shè)想一下，如果利用平均半徑或平均直徑這一個(gè)指標(biāo)，若我們猜想的 K 值大于或等于真實(shí)的 K 值，也就是簇的真實(shí)數(shù)目，那么該指標(biāo)的上升趨勢(shì)會(huì)很緩慢，但是如果我們給出的 K 值小于真實(shí)的簇的數(shù)目時(shí)，這個(gè)指標(biāo)一定會(huì)急劇上升。

根據(jù)這樣的估算思想，我們就能估計(jì)出正確的 k 值，并且得到 k 個(gè)初始質(zhì)心，接著，我們便根據(jù)上述算法流程繼續(xù)進(jìn)行迭代，直到所有質(zhì)心都不變化，從而成功實(shí)現(xiàn)算法。如下圖所示：

圖 1. K 值估計(jì)

我們知道 k 均值總是收斂的，也就是說(shuō)，k 均值算法一定會(huì)達(dá)到一種穩(wěn)定狀態(tài)，在此狀態(tài)下，所有的點(diǎn)都不會(huì)從一個(gè)簇轉(zhuǎn)移到另一個(gè)簇，因此質(zhì)心不在發(fā)生改變。在此，我們引出一個(gè)剪枝優(yōu)化，即：k 均值最明顯的收斂過(guò)程會(huì)發(fā)生在算法運(yùn)行的前期階段，故在某些情況下為了增加算法的執(zhí)行效率，我們可以替換上述算法的第五步，采用“迭代至僅有 1%~3%的點(diǎn)在影響質(zhì)心”或“迭代至僅有 1%~3%的點(diǎn)在改變簇”。

k 均值適用于絕大多數(shù)的數(shù)據(jù)類型，并且簡(jiǎn)單有效。但其缺點(diǎn)就是需要知道準(zhǔn)確的 k 值，并且不能處理異形簇，比如球形簇，不同尺寸及密度的簇，環(huán)形簇等等。

本文主要為算法講解及實(shí)現(xiàn)，因此代碼實(shí)現(xiàn)暫不考慮面向?qū)ο笏枷?，采用面向過(guò)程的實(shí)現(xiàn)方式，如果數(shù)據(jù)多維，可能會(huì)需要做數(shù)據(jù)預(yù)處理，比如歸一化，并且修改代碼相關(guān)方法即可。

算法實(shí)現(xiàn)

清單 1. Kmeans 算法代碼實(shí)現(xiàn)

import java.io.BufferedReader;

import java.io.FileReader;

import java.io.IOException;

import java.io.PrintStream;

import java.text.DecimalFormat;

import java.util.ArrayList;

import java.util.Comparator;

import java.util.PriorityQueue;

import java.util.Queue;

public class Kmeans {

private class Node {

int label;// label 用來(lái)記錄點(diǎn)屬于第幾個(gè) cluster

double［］ attributes;

public Node（） {

attributes = new double［100］;

}

}

private class NodeComparator {

Node nodeOne;

Node nodeTwo;

double distance;

public void compute（） {

double val = 0;

for （int i = 0; i 《 dimension; ++i） {

val += （this.nodeOne.attributes［i］ - this.nodeTwo.attributes［i］） *

（this.nodeOne.attributes［i］ - this.nodeTwo.attributes［i］）;

}

this.distance = val;

}

}

private ArrayList《Node》 arraylist;

private ArrayList《Node》 centroidList;

private double averageDis;

private int dimension;

private Queue《NodeComparator》 FsQueue =

new PriorityQueue《NodeComparator》（150， // 用來(lái)排序任意兩點(diǎn)之間的距離，從大到小排

new Comparator《NodeComparator》（） {

public int compare（NodeComparator one， NodeComparator two） {

if （one.distance 《 two.distance）

return 1;

else if （one.distance 》 two.distance）

return -1;

else

return 0;

}

}）;

public void setKmeansInput（String path） {

try {

BufferedReader br = new BufferedReader（new FileReader（path））;

String str;

String［］ strArray;

arraylist = new ArrayList《Node》（）;

while （（str = br.readLine（）） ！= null） {

strArray = str.split（“，”）;

dimension = strArray.length;

Node node = new Node（）;

for （int i = 0; i 《 dimension; ++i） {

node.attributes［i］ = Double.parseDouble（strArray［i］）;

}

arraylist.add（node）;

}

br.close（）;

} catch （IOException e） {

e.printStackTrace（）;

}

}

public void computeTheK（） {

int cntTuple = 0;

for （int i = 0; i 《 arraylist.size（） - 1; ++i） {

for （int j = i + 1; j 《 arraylist.size（）; ++j） {

NodeComparator nodecomp = new NodeComparator（）;

nodecomp.nodeOne = new Node（）;

nodecomp.nodeTwo = new Node（）;

for （int k = 0; k 《 dimension; ++k） {

nodecomp.nodeOne.attributes［k］ = arraylist.get（i）.attributes［k］;

nodecomp.nodeTwo.attributes［k］ = arraylist.get（j）.attributes［k］;

}

nodecomp.compute（）;

averageDis += nodecomp.distance;

FsQueue.add（nodecomp）;

cntTuple++;

}

}

averageDis /= cntTuple;// 計(jì)算平均距離

chooseCentroid（FsQueue）;

}

public double getDistance（Node one， Node two） {// 計(jì)算兩點(diǎn)間的歐氏距離

double val = 0;

for （int i = 0; i 《 dimension; ++i） {

val += （one.attributes［i］ - two.attributes［i］） * （one.attributes［i］ - two.attributes［i］）;

}

return val;

}

public void chooseCentroid（Queue《NodeComparator》 queue） {

centroidList = new ArrayList《Node》（）;

boolean flag = false;

while （！queue.isEmpty（）） {

boolean judgeOne = false;

boolean judgeTwo = false;

NodeComparator nc = FsQueue.poll（）;

if （nc.distance 《 averageDis）

break;// 如果接下來(lái)的元組，兩節(jié)點(diǎn)間距離小于平均距離，則不繼續(xù)迭代

if （！flag） {

centroidList.add（nc.nodeOne）;// 先加入所有點(diǎn)中距離最遠(yuǎn)的兩個(gè)點(diǎn)

centroidList.add（nc.nodeTwo）;

flag = true;

} else {// 之后從之前已加入的最遠(yuǎn)的兩個(gè)點(diǎn)開始，找離這兩個(gè)點(diǎn)最遠(yuǎn)的點(diǎn)，

// 如果距離大于所有點(diǎn)的平均距離，則認(rèn)為找到了新的質(zhì)心，否則不認(rèn)定為質(zhì)心

for （int i = 0; i 《 centroidList.size（）; ++i） {

Node testnode = centroidList.get（i）;

if （centroidList.contains（nc.nodeOne） || getDistance（testnode， nc.nodeOne） 《 averageDis） {

judgeOne = true;

}

if （centroidList.contains（nc.nodeTwo） || getDistance（testnode， nc.nodeTwo） 《 averageDis） {

judgeTwo = true;

}

}

if （！judgeOne） {

centroidList.add（nc.nodeOne）;

}

if （！judgeTwo） {

centroidList.add（nc.nodeTwo）;

}

}

}

}

public void doIteration（ArrayList《Node》 centroid） {

int cnt = 1;

int cntEnd = 0;

int numLabel = centroid.size（）;

while （true） {// 迭代，直到所有的質(zhì)心都不變化為止

boolean flag = false;

for （int i = 0; i 《 arraylist.size（）; ++i） {

double dis = 0x7fffffff;

cnt = 1;

for （int j = 0; j 《 centroid.size（）; ++j） {

Node node = centroid.get（j）;

if （getDistance（arraylist.get（i）， node） 《 dis） {

dis = getDistance（arraylist.get（i）， node）;

arraylist.get（i）.label = cnt;

}

cnt++;

}

}

int j = 0;

numLabel -= 1;

while （j 《 numLabel） {

int c = 0;

Node node = new Node（）;

for （int i = 0; i 《 arraylist.size（）; ++i） {

if （arraylist.get（i）.label == j + 1） {

for （int k = 0; k 《 dimension; ++k） {

node.attributes［k］ += arraylist.get（i）.attributes［k］;

}

c++;

}

}

DecimalFormat df = new DecimalFormat（“#.###”）;// 保留小數(shù)點(diǎn)后三位

double［］ attributelist = new double［100］;

for （int i = 0; i 《 dimension; ++i） {

attributelist［i］ = Double.parseDouble（df.format（node.attributes［i］ / c））;

if （attributelist［i］ ！= centroid.get（j）.attributes［i］） {

centroid.get（j）.attributes［i］ = attributelist［i］;

flag = true;

}

}

if （！flag） {

cntEnd++;

if （cntEnd == numLabel） {// 若所有的質(zhì)心都不變，則跳出循環(huán)

break;

}

}

j++;

}

if （cntEnd == numLabel） {// 若所有的質(zhì)心都不變，則 success

System.out.println（“run kmeans successfully.”）;

break;

}

}

}

public void printKmeansResults（String path） {

try {

PrintStream out = new PrintStream（path）;

computeTheK（）;

doIteration（centroidList）;

out.println（“There are ” + centroidList.size（） + “ clusters！”）;

for （int i = 0; i 《 arraylist.size（）; ++i） {

out.print（“（”）;

for （int j = 0; j 《 dimension - 1; ++j） {

out.print（arraylist.get（i）.attributes［j］ + “， ”）;

}

out.print（arraylist.get（i）.attributes［dimension - 1］ + “） ”）;

out.println（“belongs to cluster ” + arraylist.get（i）.label）;

}

out.close（）;

System.out.println（“Please check results in： ” + path）;

} catch （IOException e） {

e.printStackTrace（）;

}

}

public static void main（String［］ args） {

Kmeans kmeans = new Kmeans（）;

kmeans.setKmeansInput（“c:/kmeans.txt”）;

kmeans.printKmeansResults（“c:/kmeansResults.txt”）;

}

}

測(cè)試數(shù)據(jù)

給出一組簡(jiǎn)單的二維測(cè)試數(shù)據(jù)：

清單 2. Kmeans 算法測(cè)試數(shù)據(jù)

1，1

2，1

1，2

2，2

6，1

6，2

7，1

7，2

1，5

1，6

2，5

2，6

6，5

6，6

7，5

7，6

運(yùn)行結(jié)果

清單 3. Kmeans 算法運(yùn)行結(jié)果

There are 4 clusters！

（1.0， 1.0） belongs to cluster 1

（2.0， 1.0） belongs to cluster 1

（1.0， 2.0） belongs to cluster 1

（2.0， 2.0） belongs to cluster 1

（6.0， 1.0） belongs to cluster 3

（6.0， 2.0） belongs to cluster 3

（7.0， 1.0） belongs to cluster 3

（7.0， 2.0） belongs to cluster 3

（1.0， 5.0） belongs to cluster 4

（1.0， 6.0） belongs to cluster 4

（2.0， 5.0） belongs to cluster 4

（2.0， 6.0） belongs to cluster 4

（6.0， 5.0） belongs to cluster 2

（6.0， 6.0） belongs to cluster 2

（7.0， 5.0） belongs to cluster 2

（7.0， 6.0） belongs to cluster 2

層次聚類算法詳解及實(shí)現(xiàn)

層次聚類簡(jiǎn)介

層次聚類分為凝聚式層次聚類和分裂式層次聚類。

凝聚式層次聚類，就是在初始階段將每一個(gè)點(diǎn)都視為一個(gè)簇，之后每一次合并兩個(gè)最接近的簇，當(dāng)然對(duì)于接近程度的定義則需要指定簇的鄰近準(zhǔn)則。

分裂式層次聚類，就是在初始階段將所有的點(diǎn)視為一個(gè)簇，之后每次分裂出一個(gè)簇，直到最后剩下單個(gè)點(diǎn)的簇為止。

本文中我們將詳細(xì)介紹凝聚式層次聚類算法。

對(duì)于凝聚式層次聚類，指定簇的鄰近準(zhǔn)則是非常重要的一個(gè)環(huán)節(jié)，在此我們介紹三種最常用的準(zhǔn)則，分別是 MAX， MIN， 組平均。如下圖所示：

圖 2. 層次聚類計(jì)算準(zhǔn)則

凝聚式層次聚類算法也是一個(gè)迭代的過(guò)程，算法流程如下：

每次選最近的兩個(gè)簇合并，我們將這兩個(gè)合并后的簇稱之為合并簇。

若采用 MAX 準(zhǔn)則，選擇其他簇與合并簇中離得最遠(yuǎn)的兩個(gè)點(diǎn)之間的距離作為簇之間的鄰近度。若采用 MIN 準(zhǔn)則，取其他簇與合并簇中離得最近的兩個(gè)點(diǎn)之間的距離作為簇之間的鄰近度。若組平均準(zhǔn)則，取其他簇與合并簇所有點(diǎn)之間距離的平均值作為簇之間的鄰近度。

重復(fù)步驟 1 和步驟 2，合并至只剩下一個(gè)簇。

算法過(guò)程舉例

下面我們看一個(gè)例子：

下圖是一個(gè)有五個(gè)點(diǎn)的而為坐標(biāo)系：

圖 3. 層次聚類舉例

下表為這五個(gè)點(diǎn)的歐式距離矩陣：

表 1. 歐式距離原始矩陣

根據(jù)算法流程，我們先找出距離最近的兩個(gè)簇，P3， P4。

合并 P3， P4 為 {P3， P4}，根據(jù) MIN 原則更新矩陣如下：

MIN.distance（{P3， P4}， P1） = 1.32;

MIN.distance（{P3， P4}， P2） = 1.56;

MIN.distance（{P3， P4}， P5） = 0.70;

表 2. 歐式距離更新矩陣 1

接著繼續(xù)找出距離最近的兩個(gè)簇，{P3， P4}， P5。

合并 {P3， P4}， P5 為 {P3， P4， P5}，根據(jù) MIN 原則繼續(xù)更新矩陣：

MIN.distance（P1， {P3， P4， P5}） = 1.32;

MIN.distance（P2， {P3， P4， P5}） = 1.56;

表 3. 歐式距離更新矩陣 2

接著繼續(xù)找出距離最近的兩個(gè)簇，P1， P2。

合并 P1， P2 為 {P1， P2}，根據(jù) MIN 原則繼續(xù)更新矩陣：

MIN.distance（{P1，P2}， {P3， P4， P5}） = 1.32

表 4. 歐式距離更新矩陣 3

最終合并剩下的這兩個(gè)簇即可獲得最終結(jié)果，如下圖：

圖 4. 層次聚類舉例結(jié)果

MAX，組平均算法流程同理，只是在更新矩陣時(shí)將上述計(jì)算簇間距離變?yōu)榇亻g兩點(diǎn)最大歐式距離，和簇間所有點(diǎn)平均歐式距離即可。

算法實(shí)現(xiàn)

清單 4. 層次聚類算法代碼實(shí)現(xiàn)

import java.io.BufferedReader;

import java.io.FileReader;

import java.io.IOException;

import java.io.PrintStream;

import java.text.DecimalFormat;

import java.util.ArrayList;

public class Hierarchical {

private double［］［］ matrix;

private int dimension;// 數(shù)據(jù)維度

private class Node {

double［］ attributes;

public Node（） {

attributes = new double［100］;

}

}

private ArrayList《Node》 arraylist;

private class Model {

int x = 0;

int y = 0;

double value = 0;

}

private Model minModel = new Model（）;

private double getDistance（Node one， Node two） {// 計(jì)算兩點(diǎn)間的歐氏距離

double val = 0;

for （int i = 0; i 《 dimension; ++i） {

val += （one.attributes［i］ - two.attributes［i］） * （one.attributes［i］ - two.attributes［i］）;

}

return Math.sqrt（val）;

}

private void loadMatrix（） {// 將輸入數(shù)據(jù)轉(zhuǎn)化為矩陣

for （int i = 0; i 《 matrix.length; ++i） {

for （int j = i + 1; j 《 matrix.length; ++j） {

double distance = getDistance（arraylist.get（i）， arraylist.get（j））;

matrix［i］［j］ = distance;

}

}

}

private Model findMinValueOfMatrix（double［］［］ matrix） {// 找出矩陣中距離最近的兩個(gè)簇

Model model = new Model（）;

double min = 0x7fffffff;

for （int i = 0; i 《 matrix.length; ++i） {

for （int j = i + 1; j 《 matrix.length; ++j） {

if （min 》 matrix［i］［j］ && matrix［i］［j］ ！= 0） {

min = matrix［i］［j］;

model.x = i;

model.y = j;

model.value = matrix［i］［j］;

}

}

}

return model;

}

private void processHierarchical（String path） {

try {

PrintStream out = new PrintStream（path）;

while （true） {// 凝聚層次聚類迭代

out.println（“Matrix update as below： ”）;

for （int i = 0; i 《 matrix.length; ++i） {// 輸出每次迭代更新的矩陣

for （int j = 0; j 《 matrix.length - 1; ++j） {

out.print（new DecimalFormat（“#.00”）.format（matrix［i］［j］） + “ ”）;

}

out.println（new DecimalFormat（“#.00”）.format（matrix［i］［matrix.length - 1］））;

}

out.println（）;

minModel = findMinValueOfMatrix（matrix）;

if （minModel.value == 0） {// 當(dāng)找不出距離最近的兩個(gè)簇時(shí)，迭代結(jié)束

break;

}

out.println（“Combine ” + （minModel.x + 1） + “ ” + （minModel.y + 1））;

out.println（“The distance is： ” + minModel.value）;

matrix［minModel.x］［minModel.y］ = 0;// 更新矩陣

for （int i = 0; i 《 matrix.length; ++i） {// 如果合并了點(diǎn) p1 與 p2，則只保留 p1，p2 其中之一與其他點(diǎn)的距離，取較小值

if （matrix［i］［minModel.x］ 《= matrix［i］［minModel.y］） {

matrix［i］［minModel.y］ = 0;

} else {

matrix［i］［minModel.x］ = 0;

}

if （matrix［minModel.x］［i］ 《= matrix［minModel.y］［i］） {

matrix［minModel.y］［i］ = 0;

} else {

matrix［minModel.x］［i］ = 0;

}

}

}

out.close（）;

System.out.println（“Please check results in： ” + path）;

} catch （Exception e） {

e.printStackTrace（）;

}

}

public void setInput（String path） {

try {

BufferedReader br = new BufferedReader（new FileReader（path））;

String str;

String［］ strArray;

arraylist = new ArrayList《Node》（）;

while （（str = br.readLine（）） ！= null） {

strArray = str.split（“，”）;

dimension = strArray.length;

Node node = new Node（）;

for （int i = 0; i 《 dimension; ++i） {

node.attributes［i］ = Double.parseDouble（strArray［i］）;

}

arraylist.add（node）;

}

matrix = new double［arraylist.size（）］［arraylist.size（）］;

loadMatrix（）;

br.close（）;

} catch （IOException e） {

e.printStackTrace（）;

}

}

public void printOutput（String path） {

processHierarchical（path）;

}

public static void main（String［］ args） {

Hierarchical hi = new Hierarchical（）;

hi.setInput（“c:/hierarchical.txt”）;

hi.printOutput（“c:/hierarchical_results.txt”）;

}

}

測(cè)試數(shù)據(jù)

給出一組簡(jiǎn)單的二維測(cè)試數(shù)據(jù)

清單 5. 層次聚類算法測(cè)試數(shù)據(jù)

0.7，1.2

0.8，2

2，1

2.6，0.8

2.5，1.5

運(yùn)行結(jié)果

清單 6. 層次聚類算法運(yùn)行結(jié)果

Matrix update as below：

.00 .81 1.32 1.94 1.82

.00 .00 1.56 2.16 1.77

.00 .00 .00 .63 .71

.00 .00 .00 .00 .71

.00 .00 .00 .00 .00

Combine 3 4

The distance is： 0.6324555320336759

Matrix update as below：

.00 .81 1.32 .00 1.82

.00 .00 1.56 .00 1.77

.00 .00 .00 .00 .00

.00 .00 .00 .00 .71

.00 .00 .00 .00 .00

Combine 4 5

The distance is： 0.7071067811865475

Matrix update as below：

.00 .81 1.32 .00 .00

.00 .00 1.56 .00 .00

.00 .00 .00 .00 .00

.00 .00 .00 .00 .00

.00 .00 .00 .00 .00

Combine 1 2

The distance is： 0.806225774829855

Matrix update as below：

.00 .00 1.32 .00 .00

.00 .00 .00 .00 .00

.00 .00 .00 .00 .00

.00 .00 .00 .00 .00

.00 .00 .00 .00 .00

Combine 1 3

The distance is： 1.3152946437965907

Matrix update as below：

.00 .00 .00 .00 .00

.00 .00 .00 .00 .00

.00 .00 .00 .00 .00

.00 .00 .00 .00 .00

.00 .00 .00 .00 .00

DBSCAN 算法詳解及實(shí)現(xiàn)

考慮一種情況，點(diǎn)的分布不均勻，形狀不規(guī)則時(shí)，Kmeans 算法及層次聚類算法將面臨失效的風(fēng)險(xiǎn)。

如下坐標(biāo)系：

圖 5. DBSCAN 算法舉例

我們可以看到上面的點(diǎn)密度不均勻，這時(shí)我們考慮采用基于密度的聚類算法：DBSCAN。

算法流程

設(shè)定掃描半徑 Eps， 并規(guī)定掃描半徑內(nèi)的密度值。若當(dāng)前點(diǎn)的半徑范圍內(nèi)密度大于等于設(shè)定密度值，則設(shè)置當(dāng)前點(diǎn)為核心點(diǎn)；若某點(diǎn)剛好在某核心點(diǎn)的半徑邊緣上，則設(shè)定此點(diǎn)為邊界點(diǎn)；若某點(diǎn)既不是核心點(diǎn)又不是邊界點(diǎn)，則此點(diǎn)為噪聲點(diǎn)。

刪除噪聲點(diǎn)。

將距離在掃描半徑內(nèi)的所有核心點(diǎn)賦予邊進(jìn)行連通。

每組連通的核心點(diǎn)標(biāo)記為一個(gè)簇。

將所有邊界點(diǎn)指定到與之對(duì)應(yīng)的核心點(diǎn)的簇總。

算法過(guò)程舉例

如上圖坐標(biāo)系所示，我們?cè)O(shè)定掃描半徑 Eps 為 1.5，密度閾值 threshold 為 3，則通過(guò)上述算法過(guò)程，我們可以得到下圖：

圖 6. DBSCAN 算法舉例結(jié)果示例

通過(guò)計(jì)算各個(gè)點(diǎn)之間的歐式距離及其所在掃描半徑內(nèi)的密度值來(lái)判斷這些點(diǎn)屬于核心點(diǎn)，邊界點(diǎn)或是噪聲點(diǎn)。因?yàn)槲覀冊(cè)O(shè)定了掃描半徑為 1.5，密度閾值為 3，所以：

P0 點(diǎn)為邊界點(diǎn)，因?yàn)樵谝云錇橹行牡膾呙璋霃絻?nèi)只有兩個(gè)點(diǎn) P0 和 P1；

P1 點(diǎn)為核心點(diǎn)，因?yàn)樵谝云錇橹行牡膾呙璋霃絻?nèi)有四個(gè)點(diǎn) P0，P1，P2，P4 ；

P8 為噪聲點(diǎn)，因?yàn)槠浼确呛诵狞c(diǎn)，也非邊界點(diǎn)；

其他點(diǎn)依次類推。

算法實(shí)現(xiàn)

清單 7. DBSCAN 算法代碼實(shí)現(xiàn)

import java.io.BufferedReader;

import java.io.FileReader;

import java.io.IOException;

import java.io.PrintStream;

import java.util.ArrayList;

import java.util.HashMap;

import java.util.Iterator;

import java.util.Map;

public class DBSCAN {

private int dimension;// 數(shù)據(jù)維度

private double eps = 1.5;

private int threshold = 3;

private double distance［］［］;

private Map《Integer， Integer》 id = new HashMap《Integer， Integer》（）;

private int countClusters = 0;

private ArrayList《Integer》 keyPointList = new ArrayList《Integer》（）;//

private int［］ flags;// 標(biāo)記邊緣點(diǎn)

private class Edge {

int p， q;

double weight;

}

private class Node {

double［］ attributes;

public Node（） {

attributes = new double［100］;

}

}

private ArrayList《Node》 nodeList;

private ArrayList《Edge》 edgeList;

private double getDistance（Node one， Node two） {// 計(jì)算兩點(diǎn)間的歐氏距離

double val = 0;

for （int i = 0; i 《 dimension; ++i） {

val += （one.attributes［i］ - two.attributes［i］） * （one.attributes［i］ - two.attributes［i］）;

}

return Math.sqrt（val）;

}

public void loadEdges（） {// 給所有在掃描半徑內(nèi)的核心點(diǎn)之間加邊，標(biāo)記邊界點(diǎn)并且自動(dòng)忽略噪聲點(diǎn)

edgeList = new ArrayList《Edge》（）;

flags = new int［nodeList.size（）］;

int［］ countPoint = new int［nodeList.size（）］;

for （int i = 0; i 《 countPoint.length; ++i） {

countPoint［i］ = 1;// 每一個(gè)點(diǎn)一開始都是核心點(diǎn)

}

for （int i = 0; i 《 nodeList.size（）; ++i） {

for （int j = i + 1; j 《 nodeList.size（）; ++j） {

distance［i］［j］ = getDistance（nodeList.get（i）， nodeList.get（j））;

if （distance［i］［j］ 《= eps） {// 兩點(diǎn)間距離小于掃描半徑

countPoint［i］++;

if （countPoint［i］ 》 0 && countPoint［i］ 《 threshold） {

flags［i］ = j;// 記錄邊界點(diǎn)

}

if （countPoint［i］ 》= threshold） {// 如果記錄當(dāng)前點(diǎn)的掃描半徑內(nèi)密度值大于或等于給定閾值

flags［i］ = 0;

if （！keyPointList.contains（i）） {

keyPointList.add（i）;

}

}

countPoint［j］++;

if （countPoint［j］ 》 0 && countPoint［j］ 《 threshold） {

flags［j］ = i;// 記錄邊界點(diǎn)

}

if （countPoint［j］ 》= threshold） {// 如果記錄當(dāng)前點(diǎn)的掃描半徑內(nèi)密度值大于或等于給定閾值

flags［j］ = 0;

if （！keyPointList.contains（j）） {

keyPointList.add（j）;

}

}

}

}

}

for （int i = 0; i 《 keyPointList.size（）; ++i） {

for （int j = i + 1; j 《 keyPointList.size（）; ++j） {

Edge edge = new Edge（）;

edge.p = keyPointList.get（i）;

edge.q = keyPointList.get（j）;

edge.weight = distance［edge.p］［edge.q］;

if （edge.weight 《= eps） {

if （！id.containsKey（edge.p）） {// 為后期使用并查集求連通分量做準(zhǔn)備

id.put（edge.p， edge.p）;

}

if （！id.containsKey（edge.q）） {

id.put（edge.q， edge.q）;

}

edgeList.add（edge）;

}

}

}

}

public void setInput（String path） {

try {

BufferedReader br = new BufferedReader（new FileReader（path））;

String str;

String［］ strArray;

nodeList = new ArrayList《Node》（）;

while （（str = br.readLine（）） ！= null） {

strArray = str.split（“，”）;

dimension = strArray.length;

Node node = new Node（）;

for （int i = 0; i 《 dimension; ++i） {

node.attributes［i］ = Double.parseDouble（strArray［i］）;

}

nodeList.add（node）;

}

distance = new double［nodeList.size（）］［nodeList.size（）］;

loadEdges（）;

br.close（）;

} catch （IOException e） {

e.printStackTrace（）;

}

}

public void union（int p， int q） {// 并操作

int a = find（p）;

int b = find（q）;

if （a ！= b） {

id.put（a， b）;

}

}

public int find（int p） {// 查操作

if （p ！= id.get（p）） {

id.put（p， find（id.get（p）））;

}

return id.get（p）;

}

public void processDBSCAN（String path） {

try {

PrintStream out = new PrintStream（path）;

out.println（“核心點(diǎn)為： ” + keyPointList）;

out.println（）;

for （int i = 0; i 《 edgeList.size（）; ++i） {

out.println（“核心點(diǎn) （” + edgeList.get（i）.p + “ ” +

edgeList.get（i）.q + “） 之間的距離為： ” + edgeList.get（i）.weight）;

}

for （int i = 0; i 《 edgeList.size（）; ++i） {

union（edgeList.get（i）.p， edgeList.get（i）.q）;// 利用并查集將點(diǎn)集變?yōu)檫B通分量

}

Iterator《Integer》 it = id.keySet（）.iterator（）;

while （it.hasNext（）） {

int key = it.next（）;

if （id.get（key） == key） {// 利用并查集得到強(qiáng)連通分量個(gè)數(shù)

++countClusters;

}

}

out.println（）;

for （int i = 0; i 《 flags.length; ++i） {

if （flags［i］ ！= 0） {

out.println（“點(diǎn)” + i + “屬于點(diǎn)” + flags［i］ + “所在的簇”）;

}

}

out.println（）;

out.println（“由核心點(diǎn)連通分量數(shù)量得知共有： ” + countClusters + “個(gè)簇”）;

out.close（）;

System.out.println（“Please check results in： ” + path）;

} catch （Exception e） {

e.printStackTrace（）;

}

}

public void printOutput（String path） {

processDBSCAN（path）;

}

public static void main（String［］ args） {

DBSCAN dbscan = new DBSCAN（）;

dbscan.setInput（“c:/dbscan.txt”）;

dbscan.printOutput（“c:/dbscan_results.txt”）;

}

}

測(cè)試數(shù)據(jù)

清單 8. DBSCAN 算法測(cè)試數(shù)據(jù)

2，1

2，2

2，3

3，3

3，4.5

4，1

4，2

4，3

6，2

8，1

8，2

8，3

9，1

10，1

10，2

10，3

運(yùn)行結(jié)果

清單 9. DBSCAN 算法運(yùn)行結(jié)果

核心點(diǎn)為： ［1， 2， 3， 6， 7， 9， 10， 12， 13， 14］

核心點(diǎn) （1 2） 之間的距離為： 1.0

核心點(diǎn) （1 3） 之間的距離為： 1.4142135623730951

核心點(diǎn) （2 3） 之間的距離為： 1.0

核心點(diǎn) （3 6） 之間的距離為： 1.4142135623730951

核心點(diǎn) （3 7） 之間的距離為： 1.0

核心點(diǎn) （6 7） 之間的距離為： 1.0

核心點(diǎn) （9 10） 之間的距離為： 1.0

核心點(diǎn) （9 12） 之間的距離為： 1.0

核心點(diǎn) （10 12） 之間的距離為： 1.4142135623730951

核心點(diǎn) （12 13） 之間的距離為： 1.0

核心點(diǎn) （12 14） 之間的距離為： 1.4142135623730951

核心點(diǎn) （13 14） 之間的距離為： 1.0

連通點(diǎn) 1 和點(diǎn) 2

連通點(diǎn) 1 和點(diǎn) 3

連通點(diǎn) 3 和點(diǎn) 6

連通點(diǎn) 3 和點(diǎn) 7

連通點(diǎn) 9 和點(diǎn) 10

連通點(diǎn) 9 和點(diǎn) 12

連通點(diǎn) 12 和點(diǎn) 13

連通點(diǎn) 12 和點(diǎn) 14

點(diǎn) 1、點(diǎn) 2、點(diǎn) 3、點(diǎn) 6、點(diǎn) 7 同屬于簇 1

點(diǎn) 9、點(diǎn) 10、點(diǎn) 12、點(diǎn) 13、點(diǎn) 14 同屬于簇 2

點(diǎn) 0 屬于點(diǎn) 1 所在的簇

點(diǎn) 4 屬于點(diǎn) 3 所在的簇

點(diǎn) 5 屬于點(diǎn) 6 所在的簇

點(diǎn) 11 屬于點(diǎn) 10 所在的簇

點(diǎn) 15 屬于點(diǎn) 14 所在的簇

由核心點(diǎn)連通分量數(shù)量得知共有： 2 個(gè)簇

其他聚類算法簡(jiǎn)介

BIRCH 算法

Birch 是一種能夠高效處理大數(shù)據(jù)聚類的基于樹的層次聚類算法。設(shè)想這樣一種情況，一個(gè)擁有大規(guī)模數(shù)據(jù)的數(shù)據(jù)庫(kù)，當(dāng)這些數(shù)據(jù)被放入主存進(jìn)行聚類處理時(shí)，一般的聚類算法則沒(méi)有對(duì)應(yīng)的高效處理能力，這時(shí) Birch 算法是最佳的選擇。

Birth 不僅能夠高效地處理大數(shù)據(jù)聚類，并且能最小化 IO 花銷。它不需要掃描全局?jǐn)?shù)據(jù)已經(jīng)現(xiàn)有的簇。

算法流程

聚類特征 CF=（N，LS，SS），其中 N 代表簇中點(diǎn)的個(gè)數(shù)，LS 代表簇中代表簇中各點(diǎn)線性和，SS 代表簇中各點(diǎn)的平方和距離。聚類特征被應(yīng)用于 CF 樹中，CF 樹是一種高度平衡樹，它具有兩個(gè)參數(shù)：平衡因子 B 和簇半徑閾值 T。其中平衡因子 B 代表每一個(gè)非葉子節(jié)點(diǎn)最多能夠引入 B 個(gè)實(shí)體條目。

葉子節(jié)點(diǎn)最多只能包含 L 個(gè)實(shí)體條目，并且它們具有前向后向指針，這樣可以彼此鏈接起來(lái)。

樹的大小取決于簇半徑閾值 T 的大小。

從根節(jié)點(diǎn)開始，遞歸查找與要插入的數(shù)據(jù)點(diǎn)距離最近的葉子節(jié)點(diǎn)中的實(shí)體條目，遞歸過(guò)程選擇最短路徑。

比較上述計(jì)算出的數(shù)據(jù)點(diǎn)與葉子節(jié)點(diǎn)中實(shí)體條目間的最近距離是否小葉簇半徑閾值 T，小于則吸收該數(shù)據(jù)點(diǎn)。否則執(zhí)行下一步。

判斷當(dāng)前條目所在的葉節(jié)點(diǎn)個(gè)數(shù)是否小于 L，若小于則直接將該數(shù)據(jù)點(diǎn)插入當(dāng)前點(diǎn)。否則分裂葉子節(jié)點(diǎn)，分裂過(guò)程是將葉子節(jié)點(diǎn)中距離最遠(yuǎn)的兩個(gè)實(shí)體條目變?yōu)樾碌膬蓚€(gè)葉子節(jié)點(diǎn)，其他條目則根據(jù)距離最近原則重新分配到這兩個(gè)新的葉子節(jié)點(diǎn)中。刪除原來(lái)的葉子節(jié)點(diǎn)并更新 CF 樹。

若不能將所有數(shù)據(jù)點(diǎn)加入 CF 樹中，則考慮增加簇半徑閾值 T，并重新更新 CF 樹直至所有的數(shù)據(jù)點(diǎn)被加入 CF 樹為止。

CURE 算法

算法流程

在數(shù)據(jù)集中選擇樣本數(shù)據(jù)。

將上述樣本數(shù)據(jù)劃分為 P 個(gè)同樣大小的劃分。

將每個(gè)劃分中的點(diǎn)聚成 m/pq 個(gè)簇，共得到 m/q 個(gè)簇。過(guò)程中需刪除噪聲點(diǎn)。

對(duì)上述 m/q 個(gè)簇進(jìn)行聚類直至剩下 k 個(gè)簇。

繼續(xù)刪除離群點(diǎn)。

將剩下的點(diǎn)指派到最近的簇完成聚類過(guò)程。

聚類算法是數(shù)據(jù)挖掘算法中最為重要的部分之一，算法種類繁多，應(yīng)用場(chǎng)景也各有不同，本文章提到的聚類算法為常見(jiàn)常用的一些較為基本的算法，對(duì)于其他的聚類算法，如最小生成樹聚類，CLIQUE，DENCLUE，SOM 等等如有興趣，讀者可以自行查找相關(guān)資料進(jìn)行學(xué)習(xí)。本文旨在提高讀者對(duì)算法本身的理解，代碼實(shí)現(xiàn)過(guò)程及結(jié)果打印能夠更好的幫助讀者剖析算法，使讀者能夠更快的入門并掌握基本的聚類算法。