簡介

前面介紹的線性回歸，SVM等模型都是基于數(shù)據(jù)有標(biāo)簽的監(jiān)督學(xué)習(xí)方法，本文介紹的聚類方法是屬于無標(biāo)簽的無監(jiān)督學(xué)習(xí)方法。其他常見的無監(jiān)督學(xué)習(xí)還有密度估計，異常檢測等。

聚類就是對大量未知標(biāo)注的數(shù)據(jù)集，按照數(shù)據(jù)的內(nèi)在相似性將數(shù)據(jù)集劃分為多個類別（在聚類算法中稱為簇），使類別內(nèi)的數(shù)據(jù)相似度高，二類別間的數(shù)據(jù)相似度低。

相似度

在聚類算法中，大多數(shù)算法都是需要計算兩個數(shù)據(jù)點之間的相似度，所以先介紹一下計算相似度的方法。

圖1

其中Minkowski距離是所有范式距離的統(tǒng)稱，當(dāng)p=1時是L1距離也叫曼哈頓距離，當(dāng)p=2時是L2距離也叫歐式距離。而如果兩個數(shù)據(jù)X，Y的均值都為0時，則X和Y的Pearson相關(guān)系數(shù)就是X和Y的余弦相似度。

下面來介紹一下常見的聚類方法：基于原型聚類的K-means聚類算法以及其衍生算法K-means++，基于密度聚類的DBSCAN聚類算法以及譜聚類。

K-Means聚類：

k-means算法的思想是：通過人工指定k的值確定分類簇的類別數(shù)，隨機(jī)選擇k個數(shù)據(jù)點作為各個簇的中心點，然后通過迭代將一類數(shù)據(jù)（相似度高的一類數(shù)據(jù)）劃入各個簇中。k-means的優(yōu)點是容易實現(xiàn)，可以認(rèn)為確定劃分類別的個數(shù)。但是算法可能收斂到局部極小值，并且在大規(guī)模數(shù)據(jù)上收斂速度慢。

算法過程：

1）隨機(jī)選擇k個初始類別中心點，μ1，μ2.....μk。

2）對于每個樣本計算其與各個中心點的距離，將該樣本劃入距離最近的一個類別簇中。

3）將所有數(shù)據(jù)劃分完畢后，取每個簇的均值作為各個簇Ci的新中心點。

圖2

4）重復(fù)2）和3）過程，直到收斂，也就是簇中心點變化小于閾值。

個人代碼實現(xiàn)：

圖3

需要注意的幾個點是：

1）如果簇中包含異常點，在計算簇均值時可能影響結(jié)果，如[1,1,1,2,100] 這個簇的均值為21，但是已經(jīng)距離樣本中大多數(shù)數(shù)據(jù)很遠(yuǎn)了。所以有時在取均值時換一種方法取簇的中位數(shù)，這個算法稱為K-mediod聚類。

2）初始值敏感，K-means算法不穩(wěn)定只要是由于初始值隨機(jī)選擇，同樣的數(shù)據(jù)同樣的參數(shù)不同的初始值的模型訓(xùn)練結(jié)果不同，一種解決方案是：隨機(jī)選取第一個中心點，然后根據(jù)第一個中心點到其他數(shù)據(jù)的距離作為權(quán)重去選取第二個中心點，使距離第一個中心點最遠(yuǎn)的數(shù)據(jù)點有更大的機(jī)率作為第二個中心點，依次類推一個個選擇出簇的中心點初始值，這個方法稱為K-means++聚類算法?；蛘呤褂霉潭ǖ那発個樣本作為中心點的初始值，這樣可以固定結(jié)果，但是收斂速度卻可能變慢。

3）K-means算法適用于近似圓形分布的數(shù)據(jù)集，一些其他特殊的數(shù)據(jù)分布很難有好的聚類效果。

DBSCAN聚類：

基于密度聚類的算法思想是：只要樣本點的密度大于閾值，就將該樣本點加到最近的簇中。

首先介紹幾個概念：

1）ε-鄰域，指的是在數(shù)據(jù)集中，所有到xi數(shù)據(jù)點的距離小于ε的數(shù)據(jù)點的集合。

2）核心對象，如果樣本點xi的ε-鄰域中包含的樣本個數(shù)大于等于指定值m，則該點xi稱為核心點。

3）密度直達(dá)，樣本點xi與它的ε-鄰域中的樣本點之間稱為密度直達(dá)。

4）密度可達(dá)，樣本點xi與它的ε-鄰域中樣本的ε-鄰域中的樣本點稱為密度可達(dá)。

DBSCAN就是將數(shù)據(jù)集中的密度可達(dá)的所有樣本點劃分為一個簇，某些樣本密度可達(dá)形成一個簇，另外一些樣本點又可以密度可達(dá)就又形成另外一個簇。簇內(nèi)樣本點均密度可達(dá)，但是簇內(nèi)的樣本點與其他簇的樣本點無法可達(dá)，最后形成了多個簇類。

算法過程：

1）如果一個點p的ε-鄰域包含多于m個樣本，則創(chuàng)建一個以p為核心對象的新簇。

2）尋找并合并核心對象直接密度可達(dá)的樣本點。

3）沒有新點可以更新簇時，算法結(jié)束。

個人代碼實現(xiàn)：

圖4

DBSCAN算法不需要指定簇類的個數(shù)，它是通過數(shù)據(jù)分布內(nèi)在聯(lián)系形成的簇類，所以樣本分布近的樣本團(tuán)就容易分為一個簇。而其他不和任何樣本點密度可達(dá)的樣本點就劃分為異常點或者叫做噪音點的類別中。

層次聚類

1）凝聚的層次聚類：AGNES算法

自底向上的策略，將每個樣本數(shù)據(jù)作為一簇，然后合并這些原子簇為越來越大的簇，直到符合要求為止。

2）分裂的層次聚類：DIANA算法

自頂向下的策略，將所有對象作為一個大簇，然后逐步細(xì)分為越來越小的簇，有些像決策樹。

譜聚類（SC）

方陣作為線性算子，它的所有特征值的全體統(tǒng)稱為方陣的譜，其中最大的特征值成為譜半徑。

算法過程：

1）計算得到鄰接距離矩陣W：將各個樣本與各個樣本做距離計算，求任意兩個樣本的距離，這里使用的是高斯距離公式，形成一個N*N的對稱陣，其中對角線上的元素全為0（自己與自己的距離），N為樣本個數(shù)。

2）求對角矩陣D：將各個樣本點xi與其他樣本點的距離加和，得到該樣本點的度（參考圖），形成一個對角線上是各個樣本點的度，其他元素是0的N階對角矩陣。

3）求拉普拉斯矩陣L：L = D - W，這是一個對稱陣，且L>=0，所以為半正定。

4）對L求特征分解，取前k個特征向量，組成一個N*k的矩陣A，m為樣本個數(shù)，k為簇個數(shù)。

5）使用K-means聚類算法對A矩陣做聚類，得到的聚類結(jié)果就是對原數(shù)據(jù)集的聚類結(jié)果。

譜聚類的思想（個人理解）：就是對原數(shù)據(jù)做降維處理，得到一個N*k的矩陣，并且其中的數(shù)據(jù)值也經(jīng)過計算變成0/1形式，再對該矩陣進(jìn)行K-means聚類時，能夠很容易并快速得到較為準(zhǔn)確的結(jié)果。沒有深入了解學(xué)習(xí)譜聚類，以后有時間敲一下譜聚類的代碼，深入了解后再來更新。

總結(jié)

各個聚類方法有自己的適用場景，根據(jù)數(shù)據(jù)分布的不同選擇合適的聚類方法可以得到良好的結(jié)果，下圖是我用自己寫的代碼與sklearn庫中的聚類方法做了一個對比：

圖5

可以看出DBSCAN很容易將一團(tuán)數(shù)據(jù)劃為一簇。有興趣的朋友可以自己寫一下代碼，做更多的對比實驗（個人比較懶），本文如有寫錯的地方請幫忙指出，共同進(jìn)步，謝謝!

待更新。。

詳細(xì)代碼可參考GitHub:代碼鏈接

參考書籍:

《機(jī)器學(xué)習(xí)》 周志華? 著