聚類(lèi)分析是非監(jiān)督學(xué)習(xí)的很重要的領(lǐng)域。所謂非監(jiān)督學(xué)習(xí)，就是數(shù)據(jù)是沒(méi)有類(lèi)別標(biāo)記的，算法要從對(duì)原始數(shù)據(jù)的探索中提取出一定的規(guī)律。而聚類(lèi)分析就是試圖將數(shù)據(jù)集中的樣本劃分為若干個(gè)不相交的子集，每個(gè)子集稱(chēng)為一個(gè)“簇”。下面是sklearn中對(duì)各種聚類(lèi)算法的比較。

KMeans

KMeans算法在給定一個(gè)數(shù)k之后，能夠?qū)?shù)據(jù)集分成k個(gè)“簇”C={C1,C2,?,Ck}C={C1,C2,?,Ck}，不論這種分類(lèi)是否合理，或者是否有意義。算法需要最小化平方誤差：

當(dāng)p==2的時(shí)候，閔可夫斯基距離即為歐氏距離（2范數(shù)）
當(dāng)p==1的時(shí)候，閔可夫斯基距離即為曼哈頓距離（1范數(shù) 或者叫 cityblock distance）

以上是對(duì)于數(shù)值屬性來(lái)說(shuō)的，對(duì)于一些離散屬性也有相關(guān)的距離的定義。最后在現(xiàn)實(shí)中的數(shù)據(jù)如果要確定合適的距離計(jì)算式，可以通過(guò)“距離度量學(xué)習(xí)”來(lái)實(shí)現(xiàn)。

也就是說(shuō)上面的式（1）的目的就是我們要找到k個(gè)簇，使得在每個(gè)簇內(nèi)，所有的樣本點(diǎn)都盡量靠得比較近。

下面介紹KMeans的基本算法流程
輸入：樣本數(shù)據(jù)集DD，聚類(lèi)簇?cái)?shù)k
(1) 從樣本中隨機(jī)選取k個(gè)樣本點(diǎn)作為初始的均值向量{μ1,μ2,?,μk}{μ1,μ2,?,μk}
(2)循環(huán)以下幾步直到達(dá)到停止條件：
（2.1）令Ci=?(1≤i≤k)Ci=?(1≤i≤k)
（2.2）對(duì)所有樣本點(diǎn)計(jì)算他們到k個(gè)均值向量之間的距離，取其中距離最短的距離對(duì)應(yīng)的均值向量的標(biāo)記作為該點(diǎn)的簇標(biāo)記，然后將該點(diǎn)加入相應(yīng)的簇CiCi
（2.3）對(duì)每一個(gè)簇計(jì)算他們新的均值向量μi=1|Ci|∑x∈Cixμi=1|Ci|∑x∈Cix，如果相比之前的向量有變化，就更新，將其作為新的均值向量，如果沒(méi)有變化就不變

可以看出KMeans的基本算法是很容易理解的，算法本身也挺簡(jiǎn)單，運(yùn)行較快，所以KMeans可用于非常大型的數(shù)據(jù)集。但是KMeans也有一些缺點(diǎn)
（1）對(duì)初始值敏感。KMeans可能由于初始值選的不同，導(dǎo)致最終結(jié)果的不同。我的理解是我們要優(yōu)化的其實(shí)是式（1），但是它很難優(yōu)化，所以我們采用的是一種貪心算法，那么這種算法就可能掉進(jìn)局部最優(yōu)的坑里面，所以我們要盡量多選幾個(gè)初始值多計(jì)算幾次。不過(guò)scikit-learn里面KMeans的算法的參數(shù)里面有個(gè)’init’參數(shù)，將其設(shè)置成’init = k-means++’可以在初始化均值向量的時(shí)候讓他們之間盡量分開(kāi)。
（2）對(duì)特殊分布的數(shù)據(jù)集不能夠得出合理的結(jié)果

比如上圖，我們希望的結(jié)果應(yīng)該是左圖，但是KMeans只能得出右圖，不能得出我們想要的結(jié)果，但是這不是KMeans單獨(dú)的缺點(diǎn)，很多聚類(lèi)算法對(duì)這種情況或者數(shù)據(jù)分布是一種長(zhǎng)條形等的一類(lèi)特殊情況效果都不甚理想。這些情況在文章開(kāi)頭的圖中都有所體現(xiàn)。

總體上KMeans以及它很多聚類(lèi)算法對(duì)于每一簇?cái)?shù)據(jù)分布都是凸的情況效果都很好。
除了KMeans之外，我們還有一些它的變體的算法比如 Mini Batch K-means 或者Learning Vector Quantization (LVQ)等，在這里就不再贅述。

密度聚類(lèi)（DBSCAN）

密度聚類(lèi)的思想是不同于KMeans的，但是更符合我們?nèi)祟?lèi)的思維，基本的思想是通過(guò)是否緊密相連來(lái)判斷樣本點(diǎn)是否屬于一個(gè)簇。代表性的算法就是DBSCAN，它基于一組鄰域參數(shù)(?,MinPts)(?,MinPts)來(lái)表征某處樣本是否是緊密的。在介紹算法之前先介紹一些概念。
??-鄰域：即對(duì)于樣本點(diǎn)xixi，和它的距離在??之內(nèi)的屬于樣本集DD中的點(diǎn)的集合，即N?(xj)={si∈D|dist(xi,xj)≤?}N?(xj)={si∈D|dist(xi,xj)≤?}

核心對(duì)象:若xjxj的??-鄰域至少包含MinPtsMinPts個(gè)樣本，即|N?(xj)|≥MinPts|N?(xj)|≥MinPts，那么xjxj是一個(gè)核心對(duì)象。其實(shí)也就是在核心對(duì)象周?chē)狞c(diǎn)相對(duì)鄰域參數(shù)來(lái)說(shuō)是致密的。

密度直達(dá)與可達(dá)：直達(dá)的意思是點(diǎn)xjxj位于點(diǎn)xixi的??-鄰域中?？蛇_(dá)的意思是存在這么一個(gè)樣本序列p1,p2,?,pnp1,p2,?,pn，xjxj到p1p1是直達(dá)的，p1p1到p2p2是直達(dá)的，就這樣不斷地借著這些樣本作為“跳板”，xjxj可以間接地“跳到”xixi。

密度相連：對(duì)于樣本點(diǎn)xjxj和xixi若存在點(diǎn)xkxk使得xjxj和xixi均可由xkxk密度可達(dá)，則稱(chēng)xjxj和xixi密度相連。

最后由DBSCAN所定義的簇的概念為：由密度可達(dá)關(guān)系導(dǎo)出的最大的密度相連樣本集合。
下圖為DBSCAN的一個(gè)結(jié)果示意圖

如圖算法自動(dòng)將數(shù)據(jù)集分成了3簇，用三種顏色代表。每一簇內(nèi)較大的點(diǎn)代表核心對(duì)象，較小的點(diǎn)代表邊界點(diǎn)（與簇內(nèi)其他點(diǎn)密度相連，但是自身不是核心對(duì)象）。黑色的點(diǎn)代表離群點(diǎn)或者叫噪聲點(diǎn)。
另外從最上面的圖也能夠看出DBSCAN的表現(xiàn)還是很不錯(cuò)的。

下面是DBSCAN的基本算法步驟：

其實(shí)周志華老師的書(shū)《機(jī)器學(xué)習(xí)》上對(duì)算法的描述更清晰，感興趣的可以去看看。

這里提一個(gè)我的想法，我在看算法的時(shí)候就覺(jué)得這個(gè)算法有點(diǎn)眼熟，后來(lái)想起來(lái)發(fā)現(xiàn)跟廣度優(yōu)先搜索有點(diǎn)像，再想想發(fā)現(xiàn)DBSCAN的思路就是和廣度優(yōu)先很想。比如密度直連的兩個(gè)點(diǎn)之間可以看作這兩個(gè)點(diǎn)相連，密度可達(dá)可以看作兩個(gè)點(diǎn)之間存在一條路徑，找出所有的簇就可以看作找出整個(gè)圖中的連通分量。另外在數(shù)據(jù)結(jié)構(gòu)上DBSCAN和廣度優(yōu)先都使用了隊(duì)列來(lái)儲(chǔ)存訪(fǎng)問(wèn)到的點(diǎn)。只是由(?,MinPts)(?,MinPts)來(lái)確定兩個(gè)點(diǎn)是否相連。以上提供一個(gè)視角以供參考。

DBSCAN的優(yōu)點(diǎn)：
（1）可以解決數(shù)據(jù)分布特殊（非凸， 互相包絡(luò)，長(zhǎng)條形等）的情況
（2）對(duì)于噪聲不敏感
（3）速度較快，可適用于較大的數(shù)據(jù)集
（4）在鄰域參數(shù)(?,MinPts)(?,MinPts)給定的情況下，結(jié)果是確定的，只要數(shù)據(jù)進(jìn)入算法的順序不變，與初始值無(wú)關(guān)，這里就和KMeans不同
（5）不需要指定簇的個(gè)數(shù)

缺點(diǎn)：
（1）簇之間密度差距過(guò)大時(shí)效果不好，因?yàn)閷?duì)整個(gè)數(shù)據(jù)集我們使用的是一組鄰域參數(shù)
（2）數(shù)據(jù)集較大的時(shí)候很消耗內(nèi)存，目前在scikit-learn中已經(jīng)可以使用ball-trees 和 kd-trees來(lái)確定鄰居點(diǎn)（可以看出找出點(diǎn)的鄰域內(nèi)有幾個(gè)點(diǎn)是DBSCAN最基本，最多的操作）,但是在默認(rèn)情況下是不使用他們的，而是使用很消耗內(nèi)存的距離矩陣。
（3）對(duì)于高維數(shù)據(jù)距離的計(jì)算會(huì)比較麻煩，造成“維數(shù)災(zāi)難”

層次聚類(lèi)（hierarchical clustering）

層次聚類(lèi)是一類(lèi)算法的總稱(chēng)，是通過(guò)從下往上不斷合并簇，或者從上往下不斷分離簇形成嵌套的簇。這種層次的類(lèi)通過(guò)“樹(shù)狀圖”來(lái)表示。AgglomerativeClustering算法是一種層次聚類(lèi)的算法。
下面大致講一下 AgglomerativeClustering算法。

算法的原理很簡(jiǎn)單，最開(kāi)始的時(shí)候?qū)⑺袛?shù)據(jù)點(diǎn)本身作為簇，然后找出距離最近的兩個(gè)簇將它們合為一個(gè)，不斷重復(fù)以上步驟直到達(dá)到預(yù)設(shè)的簇的個(gè)數(shù)。

可以看到，一個(gè)很關(guān)鍵的地方就是判斷簇之間的距離。判斷的準(zhǔn)則叫做鏈接準(zhǔn)則。對(duì)于A(yíng)gglomerativeClustering算法，scikit-learn有三種準(zhǔn)則

· Ward minimizes the sum of squared differences within all clusters. It is a variance-minimizing approach and in
this sense is similar to the k-means objective function but tackled with an agglomerative hierarchical approach.
· Maximum or complete linkage minimizes the maximum distance between observations of pairs of clusters.
· Average linkage minimizes the average of the distances between all observations of pairs of clusters.

三種準(zhǔn)則有所不同，在后面的文章中再來(lái)探討他們的區(qū)別
AgglomerativeClustering也是適用于較大的數(shù)據(jù)集的，尤其是在有connectivity constraint的時(shí)候，什么是connectivity constraint？下面有一個(gè)圖

左邊是沒(méi)有connectivity constraint的，可以看到有些藍(lán)色的簇橫跨了兩片（只能這么表述了），右邊有connectivity constraint的情況下，簇可以看到基本就是沿著彎曲的平面分布的，這種結(jié)果可能更合理，并且是可以加快計(jì)算速度的，尤其是在數(shù)據(jù)量很大的情況下。因?yàn)閷?duì)于每個(gè)點(diǎn)只需要考慮和它相鄰的點(diǎn)，而不是考慮所有的點(diǎn)。但是connectivity constraint需要一個(gè)叫做connectivity matrix的東西，這個(gè)矩陣我也不清楚具體形式，寫(xiě)這些只是提醒有connectivity constraint這么個(gè)東西存在。

還有，從最上方的圖中也能夠看出AgglomerativeClustering算法對(duì)于形狀比較怪異的分布也有較好的效果

綜上就是我挑出的三個(gè)主要的聚類(lèi)算法進(jìn)行了大致的介紹，另外還有一個(gè)算法：高斯混合模型，我準(zhǔn)備把它和EM算法一起單獨(dú)寫(xiě)篇文章。聚類(lèi)算法可以作為一些監(jiān)督算法的前驅(qū)過(guò)程，又是非監(jiān)督學(xué)習(xí)的重要部分，還是很重要的。

參考：
DBSCAN聚類(lèi)原理
DBSCAN密度聚類(lèi)算法