常用聚類算法比較分析

K-pototypes算法

K-pototypes算法結合了K-means方法和根據K-means方法改進的能夠處理符號屬性的K-modes方法，同K-means方法相比，K-pototypes 算法能夠處理符號屬性。

CLARANS算法（劃分方法）

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

BIRCH算法（層次方法）

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

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

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

CURE算法（層次方法）

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

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

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

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

CLIQUE算法（綜合了基于密度和基于網格的算法）

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

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

K 均值算法詳解及實現

算法流程

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

隨機的取 k 個點作為 k 個初始質心；

計算其他點到這個 k 個質心的距離；

如果某個點 p 離第 n 個質心的距離更近，則該點屬于 cluster n，并對其打標簽，標注 point p.label=n，其中 n《=k；

計算同一 cluster 中，也就是相同 label 的點向量的平均值，作為新的質心；

迭代至所有質心都不變化為止，即算法結束。

當然算法實現的方法有很多，比如在選擇初始質心時，可以隨機選擇 k 個，也可以隨機選擇 k 個離得最遠的點等等，方法不盡相同。

K 值估計

對于 k 值，必須提前知道，這也是 kmeans 算法的一個缺點。當然對于 k 值，我們可以有很多種方法進行估計。本文中，我們采用平均直徑法來進行 k 的估計。

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

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

圖 1. K 值估計

我們知道 k 均值總是收斂的，也就是說，k 均值算法一定會達到一種穩定狀態，在此狀態下，所有的點都不會從一個簇轉移到另一個簇，因此質心不在發生改變。在此，我們引出一個剪枝優化，即：k 均值最明顯的收斂過程會發生在算法運行的前期階段，故在某些情況下為了增加算法的執行效率，我們可以替換上述算法的第五步，采用“迭代至僅有 1%~3%的點在影響質心”或“迭代至僅有 1%~3%的點在改變簇”。

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

本文主要為算法講解及實現，因此代碼實現暫不考慮面向對象思想，采用面向過程的實現方式，如果數據多維，可能會需要做數據預處理，比如歸一化，并且修改代碼相關方法即可。

算法實現

清單 1. Kmeans 算法代碼實現

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 用來記錄點屬于第幾個 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， // 用來排序任意兩點之間的距離，從大到小排

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;// 計算平均距離

chooseCentroid（FsQueue）;

}

public double getDistance（Node one， Node two） {// 計算兩點間的歐氏距離

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;// 如果接下來的元組，兩節點間距離小于平均距離，則不繼續迭代

if （！flag） {

centroidList.add（nc.nodeOne）;// 先加入所有點中距離最遠的兩個點

centroidList.add（nc.nodeTwo）;

flag = true;

} else {// 之后從之前已加入的最遠的兩個點開始，找離這兩個點最遠的點，

// 如果距離大于所有點的平均距離，則認為找到了新的質心，否則不認定為質心

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） {// 迭代，直到所有的質心都不變化為止

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（“#.###”）;// 保留小數點后三位

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） {// 若所有的質心都不變，則跳出循環

break;

}

}

j++;

}

if （cntEnd == numLabel） {// 若所有的質心都不變，則 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”）;

}

}

測試數據

給出一組簡單的二維測試數據：

清單 2. Kmeans 算法測試數據

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

運行結果

清單 3. Kmeans 算法運行結果

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

層次聚類算法詳解及實現

層次聚類簡介

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

凝聚式層次聚類，就是在初始階段將每一個點都視為一個簇，之后每一次合并兩個最接近的簇，當然對于接近程度的定義則需要指定簇的鄰近準則。

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

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

對于凝聚式層次聚類，指定簇的鄰近準則是非常重要的一個環節，在此我們介紹三種最常用的準則，分別是 MAX， MIN， 組平均。如下圖所示：

圖 2. 層次聚類計算準則

凝聚式層次聚類算法也是一個迭代的過程，算法流程如下：

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

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

重復步驟 1 和步驟 2，合并至只剩下一個簇。

算法過程舉例

下面我們看一個例子：

下圖是一個有五個點的而為坐標系：

圖 3. 層次聚類舉例

下表為這五個點的歐式距離矩陣：

表 1. 歐式距離原始矩陣

根據算法流程，我們先找出距離最近的兩個簇，P3， P4。

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

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

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

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

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

接著繼續找出距離最近的兩個簇，{P3， P4}， P5。

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

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

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

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

接著繼續找出距離最近的兩個簇，P1， P2。

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

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

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

最終合并剩下的這兩個簇即可獲得最終結果，如下圖：

圖 4. 層次聚類舉例結果

MAX，組平均算法流程同理，只是在更新矩陣時將上述計算簇間距離變為簇間兩點最大歐式距離，和簇間所有點平均歐式距離即可。

算法實現

清單 4. 層次聚類算法代碼實現

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;// 數據維度

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） {// 計算兩點間的歐氏距離

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（） {// 將輸入數據轉化為矩陣

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） {// 找出矩陣中距離最近的兩個簇

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） {// 當找不出距離最近的兩個簇時，迭代結束

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） {// 如果合并了點 p1 與 p2，則只保留 p1，p2 其中之一與其他點的距離，取較小值

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”）;

}

}

測試數據

給出一組簡單的二維測試數據

清單 5. 層次聚類算法測試數據

0.7，1.2

0.8，2

2，1

2.6，0.8

2.5，1.5

運行結果

清單 6. 層次聚類算法運行結果

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 算法詳解及實現

考慮一種情況，點的分布不均勻，形狀不規則時，Kmeans 算法及層次聚類算法將面臨失效的風險。

如下坐標系：

圖 5. DBSCAN 算法舉例

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

算法流程

設定掃描半徑 Eps， 并規定掃描半徑內的密度值。若當前點的半徑范圍內密度大于等于設定密度值，則設置當前點為核心點；若某點剛好在某核心點的半徑邊緣上，則設定此點為邊界點；若某點既不是核心點又不是邊界點，則此點為噪聲點。

刪除噪聲點。

將距離在掃描半徑內的所有核心點賦予邊進行連通。

每組連通的核心點標記為一個簇。

將所有邊界點指定到與之對應的核心點的簇總。

算法過程舉例

如上圖坐標系所示，我們設定掃描半徑 Eps 為 1.5，密度閾值 threshold 為 3，則通過上述算法過程，我們可以得到下圖：

圖 6. DBSCAN 算法舉例結果示例

通過計算各個點之間的歐式距離及其所在掃描半徑內的密度值來判斷這些點屬于核心點，邊界點或是噪聲點。因為我們設定了掃描半徑為 1.5，密度閾值為 3，所以：

P0 點為邊界點，因為在以其為中心的掃描半徑內只有兩個點 P0 和 P1；

P1 點為核心點，因為在以其為中心的掃描半徑內有四個點 P0，P1，P2，P4 ；

P8 為噪聲點，因為其既非核心點，也非邊界點；

其他點依次類推。

算法實現

清單 7. DBSCAN 算法代碼實現

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;// 數據維度

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;// 標記邊緣點

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） {// 計算兩點間的歐氏距離

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（） {// 給所有在掃描半徑內的核心點之間加邊，標記邊界點并且自動忽略噪聲點

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;// 每一個點一開始都是核心點

}

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） {// 兩點間距離小于掃描半徑

countPoint［i］++;

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

flags［i］ = j;// 記錄邊界點

}

if （countPoint［i］ 》= threshold） {// 如果記錄當前點的掃描半徑內密度值大于或等于給定閾值

flags［i］ = 0;

if （！keyPointList.contains（i）） {

keyPointList.add（i）;

}

}

countPoint［j］++;

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

flags［j］ = i;// 記錄邊界點

}

if （countPoint［j］ 》= threshold） {// 如果記錄當前點的掃描半徑內密度值大于或等于給定閾值

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）） {// 為后期使用并查集求連通分量做準備

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（“核心點為： ” + keyPointList）;

out.println（）;

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

out.println（“核心點 （” + 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）;// 利用并查集將點集變為連通分量

}

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

while （it.hasNext（）） {

int key = it.next（）;

if （id.get（key） == key） {// 利用并查集得到強連通分量個數

++countClusters;

}

}

out.println（）;

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

if （flags［i］ ！= 0） {

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

}

}

out.println（）;

out.println（“由核心點連通分量數量得知共有： ” + countClusters + “個簇”）;

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”）;

}

}

測試數據

清單 8. DBSCAN 算法測試數據

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

運行結果

清單 9. DBSCAN 算法運行結果

核心點為： ［1， 2， 3， 6， 7， 9， 10， 12， 13， 14］

核心點 （1 2） 之間的距離為： 1.0

核心點 （1 3） 之間的距離為： 1.4142135623730951

核心點 （2 3） 之間的距離為： 1.0

核心點 （3 6） 之間的距離為： 1.4142135623730951

核心點 （3 7） 之間的距離為： 1.0

核心點 （6 7） 之間的距離為： 1.0

核心點 （9 10） 之間的距離為： 1.0

核心點 （9 12） 之間的距離為： 1.0

核心點 （10 12） 之間的距離為： 1.4142135623730951

核心點 （12 13） 之間的距離為： 1.0

核心點 （12 14） 之間的距離為： 1.4142135623730951

核心點 （13 14） 之間的距離為： 1.0

連通點 1 和點 2

連通點 1 和點 3

連通點 3 和點 6

連通點 3 和點 7

連通點 9 和點 10

連通點 9 和點 12

連通點 12 和點 13

連通點 12 和點 14

點 1、點 2、點 3、點 6、點 7 同屬于簇 1

點 9、點 10、點 12、點 13、點 14 同屬于簇 2

點 0 屬于點 1 所在的簇

點 4 屬于點 3 所在的簇

點 5 屬于點 6 所在的簇

點 11 屬于點 10 所在的簇

點 15 屬于點 14 所在的簇

由核心點連通分量數量得知共有： 2 個簇

其他聚類算法簡介

BIRCH 算法

Birch 是一種能夠高效處理大數據聚類的基于樹的層次聚類算法。設想這樣一種情況，一個擁有大規模數據的數據庫，當這些數據被放入主存進行聚類處理時，一般的聚類算法則沒有對應的高效處理能力，這時 Birch 算法是最佳的選擇。

Birth 不僅能夠高效地處理大數據聚類，并且能最小化 IO 花銷。它不需要掃描全局數據已經現有的簇。

算法流程

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

葉子節點最多只能包含 L 個實體條目，并且它們具有前向后向指針，這樣可以彼此鏈接起來。

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

從根節點開始，遞歸查找與要插入的數據點距離最近的葉子節點中的實體條目，遞歸過程選擇最短路徑。

比較上述計算出的數據點與葉子節點中實體條目間的最近距離是否小葉簇半徑閾值 T，小于則吸收該數據點。否則執行下一步。

判斷當前條目所在的葉節點個數是否小于 L，若小于則直接將該數據點插入當前點。否則分裂葉子節點，分裂過程是將葉子節點中距離最遠的兩個實體條目變為新的兩個葉子節點，其他條目則根據距離最近原則重新分配到這兩個新的葉子節點中。刪除原來的葉子節點并更新 CF 樹。

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

CURE 算法

算法流程

在數據集中選擇樣本數據。

將上述樣本數據劃分為 P 個同樣大小的劃分。

將每個劃分中的點聚成 m/pq 個簇，共得到 m/q 個簇。過程中需刪除噪聲點。

對上述 m/q 個簇進行聚類直至剩下 k 個簇。

繼續刪除離群點。

將剩下的點指派到最近的簇完成聚類過程。

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