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

KMeans

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

其中μi=1|Ci|∑x∈Cix${\mu }_i=\frac{1}{|C_i|}\sum _{x\in C_i}x$是簇Ci$C_i$的均值向量，或者說是質(zhì)心。其中∥x?μi∥2$\Vert x?{\mu }_i{\Vert }^2$代表每個(gè)樣本點(diǎn)到均值點(diǎn)的距離（其實(shí)也是范數(shù)）。這里就稍微提一下距離度量。
距離度量最常用的就是閔可夫斯基距離（亦即p范數(shù)），即

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

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

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

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

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

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

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

密度聚類（DBSCAN）

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

核心對象:若xj$x_j$的?$?$-鄰域至少包含MinPts$MinPts$個(gè)樣本，即|N?(xj)|≥MinPts$|N_{?}(x_j)|\ge MinPts$，那么xj$x_j$是一個(gè)核心對象。其實(shí)也就是在核心對象周圍的點(diǎn)相對鄰域參數(shù)來說是致密的。

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

密度相連：對于樣本點(diǎn)xj$x_j$和xi$x_i$若存在點(diǎn)xk$x_k$使得xj$x_j$和xi$x_i$均可由xk$x_k$密度可達(dá)，則稱xj$x_j$和xi$x_i$密度相連。

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

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

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

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

這里提一個(gè)我的想法，我在看算法的時(shí)候就覺得這個(gè)算法有點(diǎn)眼熟，后來想起來發(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ì)列來儲存訪問到的點(diǎn)。只是由(?,MinPts)$(?,MinPts)$來確定兩個(gè)點(diǎn)是否相連。以上提供一個(gè)視角以供參考。

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

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

層次聚類（hierarchical clustering）

層次聚類是一類算法的總稱，是通過從下往上不斷合并簇，或者從上往下不斷分離簇形成嵌套的簇。這種層次的類通過“樹狀圖”來表示。AgglomerativeClustering算法是一種層次聚類的算法。
下面大致講一下 AgglomerativeClustering算法。

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

可以看到，一個(gè)很關(guān)鍵的地方就是判斷簇之間的距離。判斷的準(zhǔn)則叫做鏈接準(zhǔn)則。對于AgglomerativeClustering算法，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)則有所不同，在后面的文章中再來探討他們的區(qū)別
AgglomerativeClustering也是適用于較大的數(shù)據(jù)集的，尤其是在有connectivity constraint的時(shí)候，什么是connectivity constraint？下面有一個(gè)圖

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

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

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

參考：
DBSCAN聚類原理
DBSCAN密度聚類算法