物以類(lèi)聚，人以群分。
聚類(lèi)(cluster)是最常見(jiàn)的無(wú)監督機器學(xué)習算法，通過(guò)樣本屬性間的某種距離度量，將數據集分成相似結構的子集。

模型分類(lèi)

1. 劃分聚類(lèi)(Partitioning Clustering)
   假設數據本身有確定的類(lèi)別(簇)個(gè)數，某條數據確定地屬于某簇，學(xué)習的目的就是劃分每個(gè)簇的具體樣本子集，比如K-Means、K-Means++、Mini Batch K-Means，是最常見(jiàn)的聚類(lèi)方法。
2. 基于模型的聚類(lèi)(Model-Based Clustering)
   假設數據由隱藏分布生成，通過(guò)模型學(xué)習這個(gè)隱藏的分布，比如高斯混合模型GMM(Gaussian Mixture Models)。
3. 層次聚類(lèi)(Hierarchical Clustering)
   完整的聚類(lèi)結果是一棵樹(shù)，葉子節點(diǎn)為單個(gè)樣本，根節點(diǎn)為所有樣本。每個(gè)節點(diǎn)代表一個(gè)簇。
   可以根據實(shí)際需求，從上而下或從下而上，選擇聚成若干簇。
4. 基于密度的聚類(lèi)(Density-Based Clustering)
   假設聚類(lèi)結構能通過(guò)樣本分布的緊密程度確定。通常情況下，密度聚類(lèi)算法從樣本密度的角度來(lái)考察樣本之間的可連接性，并基于可連接樣本不斷擴展聚類(lèi)簇以達到最終的聚類(lèi)結果。 (摘自周志華《機器學(xué)習》)，比如DBSCAN、OPTICS等。
5. 譜聚類(lèi)(Spectral Clustering)等

各模型大致效果及時(shí)間復雜度總覽圖如下，注意觀(guān)察樣本簇的形狀：

scikit-learn Clustering文檔

K-Means

K-Means是聚類(lèi)的代名詞，非常簡(jiǎn)單、常見(jiàn)和重要。

1. 選擇聚類(lèi)簇的個(gè)數k
2. 隨機生成k個(gè)簇的質(zhì)心
3. 為每個(gè)樣本選擇歐拉距離最近的質(zhì)心
4. 為每個(gè)簇，平均樣本，更新質(zhì)心
5. 重復3、4，直至收斂(樣本對應簇及簇的質(zhì)心不再變)，一般根據迭代次數或質(zhì)心位置變化來(lái)控制迭代次數
6. K-Means采用歐拉距離作為相似度度量，所以K-Means適合簇是凸集，不適合不規則的圖形。

Andrew Ng CS229

Andrew Ng CS229 K-Means學(xué)習過(guò)程示意圖

K-Means++

K-Means初始質(zhì)心是隨機的，初始的質(zhì)心有可能使最終的聚類(lèi)結果局部最優(yōu)。
K-Means++在K-Means的基礎上，優(yōu)化了初始質(zhì)心的位置，盡量保證各個(gè)簇的質(zhì)心，保持較遠的距離。

1. 均勻隨機選擇一個(gè)樣本作為質(zhì)心
2. 以樣本離所有質(zhì)心最近的距離作為度量，距離越近，抽樣概率越低，盡可能選擇距離已確定質(zhì)心的簇較遠的樣本作為新增簇的質(zhì)心
3. 重復2，直至k個(gè)質(zhì)心全部選擇完成

David Arthur and Sergei Vassilvitskii

Mini-batch K-Means

1. 每輪隨機mini-batch個(gè)樣本更新質(zhì)心
2. 以單個(gè)樣本為單位，采用梯度的形式，更新質(zhì)心的位置；其中每個(gè)樣本的貢獻除了取決于與質(zhì)心的距離，還與曾經(jīng)隨機到該簇的樣本總數有關(guān)，數量越多，更新越謹慎，變化越穩定。
3. mini-batch K-Means是K-Means的一個(gè)工程簡(jiǎn)化版本，試驗表明，mini-batch K-Means性能稍微差一些，但該算法速度更快，尤其數據海量時(shí)，還是很有必要的。

D. Sculley Web-Scale K-Means Clustering

Gaussian mixture models

假設每個(gè)樣本都由某個(gè)高斯分布產(chǎn)生，高斯分布的個(gè)數代表聚類(lèi)簇的大小。

1. 選定簇的個(gè)數k
2. 初始化每個(gè)簇的高斯分布參數
3. E-step：估計樣本屬于某個(gè)簇的期望
4. 根據每個(gè)簇最新的樣本，更新其分布參數
5. 重復3、4，直至收斂

Andrew Ng CS229

根據高斯模型的形式，可以知道，K-Means方法優(yōu)化的距離和高斯模型本身差個(gè)協(xié)方差Σ；
可以理解成K-Means是GMM的特例，K-Means假設的是每個(gè)高斯分布的協(xié)方差相等，可以通過(guò)下圖感受下：

Hierarchical clustering

以自下而上聚類(lèi)為例：

1. 每一個(gè)單獨是一個(gè)簇
2. 合并距離最近相似度最高的兩個(gè)簇為新簇，并刪除舊的子簇
3. 重復2，直至滿(mǎn)足聚類(lèi)簇的個(gè)數k

示意圖如下：

scikit-learn Hierarchical Clustering文檔

重點(diǎn)在于，兩個(gè)簇之間的距離度量方式，屬于多對多的相似度估計。
常見(jiàn)的分為四種：

1. Ward：兩簇合并之后的方差。
2. 全鏈接(complete linkage)：兩簇之間所有樣本間的最大距離。
3. 均鏈接(Average linkage)：兩簇之間所有樣本間的平均距離。
4. 單鏈接(Single linkage)：兩簇之間所有樣本間的最小距離。

Ward類(lèi)似于K-Means，適合歐拉距離，后面三種的距離可以任意定義。

DBSCAN

在給定半徑的鄰域范圍和領(lǐng)域節點(diǎn)數約束下，尋找核心樣本，核心樣本間并可以進(jìn)行同簇傳遞，直至找到非核心樣本。
如圖：點(diǎn)B、點(diǎn)C可通過(guò)中間密度傳遞連接，而點(diǎn)位于整個(gè)密度環(huán)外，密度不可到達，不屬于該簇。

ERICH SCHUBERT DBSCAN Revisited, Revisited

學(xué)習過(guò)程如下，：

周志華 機器學(xué)習

黑點(diǎn)為非核心樣本，大圓圈為核心樣本。

scikit-learn DBSCAN文檔

評價(jià)

聚類(lèi)算法最大的問(wèn)題就是很難統一評價(jià)，有兩個(gè)大的方向：

1. 簇間距離越大越好，不同簇盡量分離。
2. 簇內距離越小越好，簇內盡量聚合。

周志華 機器學(xué)習

總結

聚類(lèi)最終的效果是根據現有數據屬性，為數據增加一個(gè)簇類(lèi)別的標簽，本質(zhì)是一個(gè)學(xué)習新特征的過(guò)程。
這種數據的內在結構信息，可以用于分類(lèi)本身；也可以當作特征工程，為監督學(xué)習下游任務(wù)提供更多特征；或者應用于數據預處理，篩選有用數據，降低后續模型訓練復雜度。

聚類(lèi)過(guò)程相對比較簡(jiǎn)單，結果相對比較寬泛，但這是一種很接近人類(lèi)的學(xué)習方式，對數據集無(wú)標簽的要求，意味著(zhù)其更大的普適性。

不同模型側重點(diǎn)不同，實(shí)際使用中，需要根據數據量及數據本身分布，在性能和時(shí)間之間折中。