本篇結(jié)構(gòu)

• 簡(jiǎn)介
• 聚類算法的分類
• K-Means聚類算法
• DBSCAN聚類算法

本篇介紹了聚類算法的種類，重點(diǎn)關(guān)注K-Means和DBSCAN兩類聚類算法，并給出具體實(shí)現(xiàn)。

一、簡(jiǎn)介

1.1 什么是聚類

聚類是數(shù)據(jù)挖掘中的概念，就是按照某個(gè)特定標(biāo)準(zhǔn)(如距離)把一個(gè)數(shù)據(jù)集分割成不同的類或簇，使得同一個(gè)簇內(nèi)的數(shù)據(jù)對(duì)象的相似性盡可能大，同時(shí)不在同一個(gè)簇中的數(shù)據(jù)對(duì)象的差異性也盡可能地大。也即聚類后同一類的數(shù)據(jù)盡可能聚集到一起，不同類數(shù)據(jù)盡量分離。

1.2 什么是分類

分類簡(jiǎn)單來(lái)說(shuō)，就是根據(jù)文本的特征或?qū)傩裕瑒澐值揭延械念悇e中。也就是說(shuō)，這些類別是已知的，通過(guò)對(duì)已知分類的數(shù)據(jù)進(jìn)行訓(xùn)練和學(xué)習(xí)，找到這些不同類的特征，再對(duì)未分類的數(shù)據(jù)進(jìn)行分類。

1.3 聚類與分類的區(qū)別

Clustering (聚類)，是把相似的東西分到一組。聚類的時(shí)候，并不關(guān)心某一類是什么，需要實(shí)現(xiàn)的目標(biāo)只是把相似的東西聚到一起。因此，一個(gè)聚類算法通常只需要知道如何計(jì)算相似度就可以開(kāi)始工作了，因此 clustering 通常并不需要使用訓(xùn)練數(shù)據(jù)進(jìn)行學(xué)習(xí)，這在Machine Learning中被稱作unsupervised learning (無(wú)監(jiān)督學(xué)習(xí))。

Classification (分類)，對(duì)于一個(gè)classifier，通常需要告訴它“這個(gè)東西被分為某某類”這樣一些例子，理想情況下，一個(gè) classifier 會(huì)從它得到的訓(xùn)練集中進(jìn)行“學(xué)習(xí)”，從而具備對(duì)未知數(shù)據(jù)進(jìn)行分類的能力，這種提供訓(xùn)練數(shù)據(jù)的過(guò)程通常叫做supervised learning (監(jiān)督學(xué)習(xí))。

1.4 舉例說(shuō)明兩者的區(qū)別

來(lái)自博文：聚類（clustering）與分類（Classification）的區(qū)別。

假設(shè)有一批人的年齡的數(shù)據(jù)，大致知道其中有一堆少年兒童，一堆青年人，一堆老年人。

聚類就是自動(dòng)發(fā)現(xiàn)這三堆數(shù)據(jù)，并把相似的數(shù)據(jù)聚合到同一堆中。所以對(duì)于這個(gè)例子，如果要聚成3堆的話，那么輸入就是一堆年齡數(shù)據(jù)，注意，此時(shí)的年齡數(shù)據(jù)并不帶有類標(biāo)號(hào)，也就是說(shuō)我只知道里面大致有三堆人，至于誰(shuí)是哪一堆，現(xiàn)在是不知道的，而輸出就是每個(gè)數(shù)據(jù)所屬的類標(biāo)號(hào)，聚類完成之后，就知道誰(shuí)和誰(shuí)是一堆了。

而分類就是，事先告訴你，少年兒童、青年人及老年人的年齡是什么樣的，現(xiàn)在新來(lái)了一個(gè)年齡，輸出它的類標(biāo)號(hào)，就是它是屬于少年兒童、青年人、老年人的哪個(gè)類。一般來(lái)說(shuō)，分類器是需要訓(xùn)練的，也就是要告訴你的算法，每個(gè)類的特征是什么樣子，它才能識(shí)別新的數(shù)據(jù)。

下面再舉一個(gè)實(shí)際的例子。

對(duì)于聚類，比如有些搜索引擎有“查看相似網(wǎng)頁(yè)”的功能，這個(gè)就可以用聚類來(lái)做，把網(wǎng)頁(yè)就行聚類，在聚類的結(jié)果中，每一個(gè)類中的網(wǎng)頁(yè)看成是相似的。

對(duì)于分類，比如手寫(xiě)識(shí)別就可以看到是分類問(wèn)題，比如我寫(xiě)了10個(gè)“我”字，然后對(duì)這10個(gè)“我”字進(jìn)行特征提取，就可以告訴算法，“我”字具有什么樣的特征，于是來(lái)了一個(gè)新的“我”字，雖然筆畫(huà)和之前的10個(gè)“我”字不完全一樣，但是特征高度相似，于是就把這個(gè)手寫(xiě)的字分類到“我”這個(gè)類，就識(shí)別出來(lái)了。

總結(jié)一下，數(shù)據(jù)分類是分析已有的數(shù)據(jù)，尋找其共同的屬性，并根據(jù)分類模型將這些數(shù)據(jù)劃分成不同的類別，這些數(shù)據(jù)賦予類標(biāo)號(hào)。這些類別是事先定義好的，并且類別數(shù)是已知的。相反，數(shù)據(jù)聚類則是將本沒(méi)有類別參考的數(shù)據(jù)進(jìn)行分析并劃分為不同的組，即從這些數(shù)據(jù)導(dǎo)出類標(biāo)號(hào)。聚類分析本身則是根據(jù)數(shù)據(jù)來(lái)發(fā)掘數(shù)據(jù)對(duì)象及其關(guān)系信息，并將這些數(shù)據(jù)分組。每個(gè)組內(nèi)的對(duì)象之間是相似的，而各個(gè)組間的對(duì)象是不相關(guān)的。不難理解，組內(nèi)相似性越高，組間相異性越高，則聚類越好。

二、聚類算法的分類

來(lái)自博文：常用聚類算法有哪些？

主要分為層次化聚類算法，劃分式聚類算法，基于密度的聚類算法，基于網(wǎng)格的聚類算法，基于模型的聚類算法等。

2.1 基于劃分的聚類（partitioning methods）

給定一個(gè)有N個(gè)元組或者記錄的數(shù)據(jù)集，分裂法將構(gòu)造K個(gè)分組，每一個(gè)分組就代表一個(gè)聚類，K《N。而且這K個(gè)分組滿足下列條件：

1. 每一個(gè)分組至少包含一個(gè)數(shù)據(jù)紀(jì)錄；
2. 每一個(gè)數(shù)據(jù)紀(jì)錄屬于且僅屬于一個(gè)分組（注意：這個(gè)要求在某些模糊聚類算法中可以放寬）；

對(duì)于給定的K，算法首先給出一個(gè)初始的分組方法，以后通過(guò)反復(fù)迭代的方法改變分組，使得每一次改進(jìn)之后的分組方案都較前一次好，而所謂好的標(biāo)準(zhǔn)就是：同一分組中的記錄越近越好，而不同分組中的紀(jì)錄越遠(yuǎn)越好。

大部分劃分方法是基于距離的。給定要構(gòu)建的分區(qū)數(shù)k，劃分方法首先創(chuàng)建一個(gè)初始化劃分。然后，它采用一種迭代的重定位技術(shù)，通過(guò)把對(duì)象從一個(gè)組移動(dòng)到另一個(gè)組來(lái)進(jìn)行劃分。一個(gè)好的劃分的一般準(zhǔn)備是：同一個(gè)簇中的對(duì)象盡可能相互接近或相關(guān)，而不同的簇中的對(duì)象盡可能遠(yuǎn)離或不同。

代表算法有：K-means，K-medoids，CLARANS。

2.2 基于分層的聚類(hierarchical methods)

這種方法對(duì)給定的數(shù)據(jù)集進(jìn)行層次似的分解，直到某種條件滿足為止。具體又可分為“自底向上”和“自頂向下”兩種方案。

例如：在“自底向上”方案中，初始時(shí)每個(gè)數(shù)據(jù)點(diǎn)組成一個(gè)單獨(dú)的組，在接下來(lái)的迭代中，按一定的距離度量將相互鄰近的組合并成一個(gè)組，直至所有的記錄組成一個(gè)分組或者滿足某個(gè)條件為止。代表算法有：BIRCH，CURE，CHAMELEON等。

2.3 基于密度的聚類（density-based methods）

基于密度的方法的特點(diǎn)是不依賴于距離，而是依賴于密度，從而克服基于距離的算法只能發(fā)現(xiàn)“球形”聚簇的缺點(diǎn)。其核心思想在于只要一個(gè)區(qū)域中點(diǎn)的密度大于某個(gè)閾值，就把它加到與之相近的聚類中去。代表算法有：DBSCAN，OPTICS，DENCLUE，WaveCluster。

2.4 基于網(wǎng)格的聚類（gird-based methods）

這種方法通常將數(shù)據(jù)空間劃分成有限個(gè)單元的網(wǎng)格結(jié)構(gòu)，所有的處理都是以單個(gè)的單元為對(duì)象。這樣做起來(lái)處理速度很快，因?yàn)檫@與數(shù)據(jù)點(diǎn)的個(gè)數(shù)無(wú)關(guān)，而只與單元個(gè)數(shù)有關(guān)。代表算法有：STING，CLIQUE，WaveCluster。

2.5 基于模型的聚類（model-based methods）

基于模型的方法給每一個(gè)聚類假定一個(gè)模型，然后去尋找能很好的擬合模型的數(shù)據(jù)集。模型可能是數(shù)據(jù)點(diǎn)在空間中的密度分布函數(shù)或者其它。這樣的方法通常包含的潛在假設(shè)是：數(shù)據(jù)集是由一系列的潛在概率分布生成的。通常有兩種嘗試思路：統(tǒng)計(jì)學(xué)方法和神經(jīng)網(wǎng)絡(luò)方法。其中，統(tǒng)計(jì)學(xué)方法有COBWEB算法、GMM(Gaussian Mixture Model)，神經(jīng)網(wǎng)絡(luò)算法有SOM(Self Organized Maps)算法。

三、K-Means聚類算法

3.1 定義

k-means算法中的k代表類簇個(gè)數(shù)，means代表類簇內(nèi)數(shù)據(jù)對(duì)象的均值（這種均值是一種對(duì)類簇中心的描述），因此，k-means算法又稱為k-均值算法。k-means算法是一種基于劃分的聚類算法，以距離作為數(shù)據(jù)對(duì)象間相似性度量的標(biāo)準(zhǔn)，即數(shù)據(jù)對(duì)象間的距離越小，則它們的相似性越高，則它們?cè)接锌赡茉谕粋€(gè)類簇。

數(shù)據(jù)對(duì)象間距離的計(jì)算有很多種，k-means算法通常采用歐氏距離來(lái)計(jì)算數(shù)據(jù)對(duì)象間的距離，計(jì)算公式如下（如果是多維也可以進(jìn)行擴(kuò)展）：

k-means算法聚類過(guò)程中，每次迭代，對(duì)應(yīng)的類簇中心需要重新計(jì)算（更新）：對(duì)應(yīng)類簇中所有數(shù)據(jù)對(duì)象的均值，即為更新后該類簇的類簇中心。

k-means算法需要不斷地迭代來(lái)重新劃分類簇，并更新類簇中心，那么迭代終止的條件是什么呢？一般情況，有兩種方法來(lái)終止迭代：一種方法是設(shè)定迭代次數(shù)T，當(dāng)?shù)竭_(dá)第T次迭代，則終止迭代，此時(shí)所得類簇即為最終聚類結(jié)果；另一種方法是采用誤差平方和準(zhǔn)則函數(shù)。

3.2 算法思路

k-means算法思想可描述為：

1. 首先初始化K個(gè)類簇中心；
2. 然后計(jì)算各個(gè)數(shù)據(jù)對(duì)象到聚類中心的距離，把數(shù)據(jù)對(duì)象劃分至距離其最近的聚類中心所在類簇中；
3. 接著根據(jù)所得類簇，更新類簇中心；
4. 繼續(xù)計(jì)算各個(gè)數(shù)據(jù)對(duì)象到聚類中心的距離，把數(shù)據(jù)對(duì)象劃分至距離其最近的聚類中心所在類簇中；
5. 根據(jù)所得類簇，繼續(xù)更新類簇中心；
6. 一直迭代，直到達(dá)到最大迭代次數(shù)T，或者兩次迭代J的差值小于某一閾值時(shí)，迭代終止，得到最終聚類結(jié)果。

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

網(wǎng)上有很多實(shí)現(xiàn)，可以參考一下下面的博文：

C#下實(shí)現(xiàn)的基礎(chǔ)K-MEANS多維聚類
k-means聚類算法

也可以參考我的github：

https://github.com/w1992wishes/daily-summary/blob/master/algorithm/cluster/src/main/java/me/w1992wishes/algorithm/cluster/kmeans/KMeans.java

3.4 優(yōu)缺點(diǎn)

k-means算法優(yōu)缺點(diǎn)分析

• 優(yōu)點(diǎn)
  ??原理比較簡(jiǎn)單，實(shí)現(xiàn)也是很容易，收斂速度快
  ??聚類效果較優(yōu)
  ??算法的可解釋度比較強(qiáng)
• 缺點(diǎn)
  ??K值的選取不好把握
  ??聚類結(jié)果對(duì)初始類簇中心的選取較為敏感
  ??對(duì)噪音和異常點(diǎn)比較的敏感
  ??可能收斂到局部最小值，在大規(guī)模數(shù)據(jù)集上收斂較慢
  ??只能發(fā)現(xiàn)球型類簇

四、DBSCAN聚類算法

4.1 定義

來(lái)自博文：從DBSCAN算法談?wù)劸垲愃惴?/a>

DBSCAN（Density-Based Spatial Clustering of Applications with Noise，具有噪聲的基于密度的聚類方法）是一種基于密度的空間聚類算法。該算法將具有足夠密度的區(qū)域劃分為簇，并在具有噪聲的空間數(shù)據(jù)庫(kù)中發(fā)現(xiàn)任意形狀的簇，它將簇定義為密度相連的點(diǎn)的最大集合。

DBSCAN一些關(guān)鍵概念的定義：

1. ?鄰域：給定對(duì)象半徑?內(nèi)的區(qū)域稱為該對(duì)象的?鄰域。
2. 核心對(duì)象（core points）：如果給定對(duì)象?鄰域內(nèi)的樣本點(diǎn)數(shù)大于等于MinPts，則稱該對(duì)象為核心對(duì)象。
3. 直接密度可達(dá)（directly density-reachable）：給定一個(gè)對(duì)象集合D，如果p在q的?的鄰域內(nèi)，且q是一個(gè)核心對(duì)象，則我們說(shuō)對(duì)象p從對(duì)象q出發(fā)是直接密度可達(dá)的。
4. 密度可達(dá)（density-reachable）：對(duì)于樣本集合D，如果存在一個(gè)對(duì)象鏈P1,P2,...,Pn,P1=q,Pn=p，對(duì)于Pi∈D,1≤i≤n，Pi+1是從Pi關(guān)于?和MinPts直接密度可達(dá)，則對(duì)象p是從對(duì)象q關(guān)于?和MinPts密度可達(dá)的。
5. 密度相連（density-connected）：如果存在對(duì)象o∈D，使對(duì)象p和q都是從o關(guān)于?和MinPts密度可達(dá)的，那么對(duì)象p到q是關(guān)于?和MinPts密度相連的。

根據(jù)上圖，分別解釋這五條定義。

1. 以某個(gè)數(shù)據(jù)樣本點(diǎn)作為圓心，以?為半徑畫(huà)圓，每個(gè)圓所圈的區(qū)域就是?鄰域。直觀上來(lái)說(shuō)，有多少個(gè)數(shù)據(jù)樣本點(diǎn)，就有多少個(gè)鄰域。
2. 核心對(duì)象數(shù)學(xué)形式的定義如下：N?(p)={q∈D|dist(p,q)≤?}，且p∈N?(p),|N?(p)|≥MinPts，滿足上述兩個(gè)條件的p為核心對(duì)象。從同圖中來(lái)說(shuō)，假設(shè)MinPts是3，紅色的點(diǎn)都屬于核心對(duì)象。
3. 如A點(diǎn)所畫(huà)出的圈圈內(nèi)的其他任何紅色點(diǎn)都屬于直接密度可達(dá)。
4. 密度可達(dá)的關(guān)系相對(duì)弱一點(diǎn)，除A點(diǎn)鄰域內(nèi)的其他紅色點(diǎn)與A的關(guān)系均屬于密度可達(dá)。
5. 從A出發(fā)，能夠密度可達(dá)的任意兩個(gè)點(diǎn)都屬于密度相連。

由以上概念，DBSCAN算法中將數(shù)據(jù)點(diǎn)分為一下三類：

• 核心點(diǎn)--在半徑Eps內(nèi)含有超過(guò)MinPts數(shù)目的點(diǎn)
• 邊界點(diǎn)--在半徑Eps內(nèi)點(diǎn)的數(shù)量小于MinPts，但是落在核心點(diǎn)的鄰域內(nèi)
• 噪音點(diǎn)--既不是核心點(diǎn)也不是邊界點(diǎn)的點(diǎn)

4.2 算法思路

DBSCAN算法描述:

1. DBSCAN算法從一個(gè)未被訪問(wèn)的任意的數(shù)據(jù)點(diǎn)開(kāi)始。這個(gè)點(diǎn)的鄰域是用距離epsilon來(lái)定義（即該點(diǎn)ε距離范圍內(nèi)的所有點(diǎn)都是鄰域點(diǎn)）。
2. 如果在該鄰域內(nèi)有足夠數(shù)量的點(diǎn)（根據(jù)minPoints的值），則聚類過(guò)程開(kāi)始，并且當(dāng)前數(shù)據(jù)點(diǎn)成為新簇中的第一個(gè)點(diǎn)。否則，該點(diǎn)將被標(biāo)記為噪聲（稍后，這個(gè)噪聲點(diǎn)可能成為聚類中的一部分）。在這兩種情況下，該點(diǎn)都會(huì)被標(biāo)記為“已訪問(wèn)”。
3. 對(duì)于新簇中的第一個(gè)點(diǎn)，它的ε距離鄰域內(nèi)的點(diǎn)也會(huì)成為同簇的一部分。這個(gè)過(guò)程使ε鄰域內(nèi)的所有點(diǎn)都屬于同一個(gè)簇，然后對(duì)才添加到簇中的所有新點(diǎn)重復(fù)上述過(guò)程。
4. 重復(fù)步驟2和3兩個(gè)過(guò)程直到確定了聚類中的所有點(diǎn)才停止，即訪問(wèn)和標(biāo)記了聚類的ε鄰域內(nèi)的所有點(diǎn)。
5. 一旦我們完成了當(dāng)前的聚類，就檢索和處理新的未訪問(wèn)的點(diǎn)，就能進(jìn)一步發(fā)現(xiàn)新的簇或者是噪聲。重復(fù)上述過(guò)程，直到所有點(diǎn)被標(biāo)記為已訪問(wèn)才停止。由于所有點(diǎn)已經(jīng)被訪問(wèn)完畢，每個(gè)點(diǎn)都被標(biāo)記為屬于一個(gè)簇或是噪聲。

具體算法描述如下：

1. 檢測(cè)數(shù)據(jù)庫(kù)中尚未檢查過(guò)的對(duì)象p，如果p未被處理(歸為某個(gè)簇或者標(biāo)記為噪聲)，則檢查其鄰域，若包含的對(duì)象數(shù)不小于MinPts ，建立新簇C，將其中的所有點(diǎn)加入候選集N；
2. 對(duì)候選集N 中所有尚未被處理的對(duì)象q，檢查其鄰域，若至少包含MinPts個(gè)對(duì)象，則將這些對(duì)象加入N；如果q 未歸入任何一個(gè)簇，則將q 加入C；
3. 重復(fù)步驟2)，繼續(xù)檢查N 中未處理的對(duì)象，當(dāng)前候選集N為空；
4. 重復(fù)步驟1)~3)，直到所有對(duì)象都?xì)w入了某個(gè)簇或標(biāo)記為噪聲。

其偽代碼描述如下：
輸入：數(shù)據(jù)對(duì)象集合D，半徑Eps，密度閾值MinPts
輸出：聚類C

**DBSCAN（D, Eps, MinPts）
Begin
    init C=0; //初始化簇的個(gè)數(shù)為0
    for each unvisited point p in D
        mark p as visited; //將p標(biāo)記為已訪問(wèn)
        N = getNeighbours (p, Eps);
        //如果滿足sizeOf(N) < MinPts，則將p標(biāo)記為噪聲
        if sizeOf(N) < MinPts then
            mark p as Noise; 
                    else
            C= next cluster; //建立新簇C
            ExpandCluster (p, N, C, Eps, MinPts);
        end if
    end for
End**

ExpandCluster(p, N, C, Eps, MinPts)
    add p to cluster C; //首先將核心點(diǎn)加入C
    for each point p’ in N
        mark p' as visited;
        N’ = getNeighbours (p’, Eps); //對(duì)N鄰域內(nèi)的所有點(diǎn)在進(jìn)行半徑檢查
        if sizeOf(N’) >= MinPts then
            N = N+N’; //如果大于MinPts，就擴(kuò)展N的數(shù)目
        end if
        if p’ is not member of any cluster
            add p’ to cluster C; //將p' 加入簇C
        end if
    end for
End ExpandCluster

如果沒(méi)有講清楚，可以參考下面的博文：

聚類分析常用算法原理：KMeans,DBSCAN
DBSCAN 算法介紹以及C++實(shí)現(xiàn)

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

可以參考博文：

聚類算法——python實(shí)現(xiàn)密度聚類（DBSCAN）

也可以訪問(wèn)我的github：

https://github.com/w1992wishes/daily-summary/blob/master/algorithm/cluster/src/main/java/me/w1992wishes/algorithm/cluster/dbscan/DBSCAN.java

4.4 優(yōu)缺點(diǎn)

DBSCAN算法優(yōu)缺點(diǎn)：

• 優(yōu)點(diǎn)
  ??可以對(duì)任意形狀的稠密數(shù)據(jù)集進(jìn)行聚類，相對(duì)的，K-Means之類的聚類算法一般只適用于凸數(shù)據(jù)集
  ??可以在聚類的同時(shí)發(fā)現(xiàn)異常點(diǎn)，對(duì)數(shù)據(jù)集中的異常點(diǎn)不敏感
  ??聚類結(jié)果沒(méi)有偏倚，相對(duì)的，K-Means之類的聚類算法初始值對(duì)聚類結(jié)果有很大影響
• 缺點(diǎn)
  ??如果樣本集的密度不均勻、聚類間距差相差很大時(shí)，聚類質(zhì)量較差，這時(shí)用DBSCAN聚類一般不適合
  ??調(diào)參相對(duì)于傳統(tǒng)的K-Means之類的聚類算法稍復(fù)雜，主要需要對(duì)距離閾值?，鄰域樣本數(shù)閾值MinPts聯(lián)合調(diào)參，不同的參數(shù)組合對(duì)最后的聚類效果有較大影響