目前創(chuàng)新互聯(lián)已為上千余家的企業(yè)提供了網(wǎng)站建設(shè)、域名、網(wǎng)頁(yè)空間、網(wǎng)站托管、服務(wù)器租用、企業(yè)網(wǎng)站設(shè)計(jì)、金壇網(wǎng)站維護(hù)等服務(wù)，公司將堅(jiān)持客戶導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長(zhǎng)，共同發(fā)展。

目錄

Kmeans

DBSCAN-基于密度的空間聚類算法

譜聚類

ＧＭＭ-高斯混合模型

MeanShift-均值遷移

層次聚類

代碼

Kmeans

聚類原則：以空間中k個(gè)點(diǎn)為中心進(jìn)行聚類，對(duì)最靠近他們的對(duì)象歸類。逐次計(jì)算各簇中心的值為新的中心值，迭代更新，直至簇中心位置不再改變或者達(dá)到大迭代次數(shù)。

Kmeans的目標(biāo)函數(shù)

定義為：各簇成員到其簇首的距離的平方和最小，如下所示

式中，C為簇首(聚類中心)集合，共有K個(gè)簇首。計(jì)算目標(biāo)函數(shù)梯度，令梯度為0，計(jì)算簇首C，

式中l(wèi)(x)表示簇成員個(gè)數(shù)。通過(guò)迭代優(yōu)化目標(biāo)函數(shù)來(lái)計(jì)算最佳參數(shù)C。由上式得，在每次迭代中需更新聚類中心為每個(gè)簇的簇心即簇成員的均值。

算法流程：

1. 適當(dāng)選擇k個(gè)類的初始中心；
2. 在第n次迭代中，對(duì)任意一個(gè)樣本，求其到k個(gè)中心的距離，將該樣本歸到距離最短的中心所在的類/簇；
3. 利用均值等方法更新該類的中心值；

4. 對(duì)于所有的k個(gè)聚類中心，如果利用（2）（3）的迭代法更新后，聚類中心的位置保持不變，則迭代結(jié)束；否則，則繼續(xù)迭代。

優(yōu)點(diǎn)：

速度快，簡(jiǎn)單

缺點(diǎn)：

1. 適合聚類球狀類簇，不能發(fā)現(xiàn)一些混合度較高，非球狀類簇
2. 需指定簇個(gè)數(shù)
3. 算法結(jié)果不穩(wěn)定，最終結(jié)果跟初始點(diǎn)選擇相關(guān)，容易陷入局部最優(yōu)

4. 對(duì)噪聲或離群點(diǎn)比較敏感：無(wú)法區(qū)分出哪些是噪聲或者離群點(diǎn)，只能給每個(gè)數(shù)據(jù)點(diǎn)都判斷出一個(gè)類別來(lái)，這樣會(huì)導(dǎo)致樣本質(zhì)心偏移，導(dǎo)致誤判或者聚類緊密程度降低。

• kmeans算法結(jié)果易受初始點(diǎn)影響
  由于kmeans算法結(jié)果易受初始點(diǎn)影響，得到的結(jié)果是局部最優(yōu)，為次，我們可以運(yùn)行n次kmeans算法，每次運(yùn)行的初始點(diǎn)均為隨機(jī)生成。然后在n次運(yùn)行結(jié)果中，選取目標(biāo)函數(shù)(代價(jià)函數(shù))最小的聚類結(jié)果。
• 聚類數(shù)量k如何確定?
  通常在數(shù)據(jù)集有多少個(gè)聚類是不清楚的。對(duì)于低維的數(shù)據(jù)，對(duì)其可視化，我們可以通過(guò)肉眼觀察到有多少個(gè)聚類，但這樣并不準(zhǔn)確，而且大部分?jǐn)?shù)據(jù)也無(wú)法可視化顯示。方法1：我們可以通過(guò)構(gòu)建一個(gè)代價(jià)函數(shù)與聚類數(shù)量k的關(guān)系圖，如下圖所示，橫坐標(biāo)是聚類數(shù)量，每個(gè)聚類數(shù)量對(duì)應(yīng)的代價(jià)函數(shù)J均是n次運(yùn)行的最優(yōu)結(jié)果。觀察下圖，代價(jià)函數(shù)隨聚類數(shù)量增大而減小，但并不是說(shuō)聚類數(shù)量越多越好，比如：對(duì)于m個(gè)樣本，m個(gè)聚類的代價(jià)函數(shù)自然是0，但這樣根本不合理。觀察下圖，代價(jià)函數(shù)在沒(méi)有到拐點(diǎn)之前下降很快，拐點(diǎn)之后下降變緩，我們就可以考慮選擇這個(gè)拐點(diǎn)對(duì)應(yīng)的數(shù)量作為聚類數(shù)量，這是一種較為合理的方法，但受限于能否得到一個(gè)清晰的拐點(diǎn)，如右下圖所示，
• 
  
  方法2：結(jié)果導(dǎo)向。我們使用kmeans算法的目的是什么？來(lái)確定k值能更好的服務(wù)于后續(xù)的目的。根據(jù)業(yè)務(wù)需求，多少個(gè)類別能夠滿足需求，效果更好來(lái)確定聚類數(shù)量。

DBSCAN-基于密度的空間聚類算法

聚類原則：聚類距離簇邊界最近的點(diǎn)

算法流程：

核心點(diǎn)：核心點(diǎn)的半徑范圍內(nèi)的樣本個(gè)數(shù)≥最少點(diǎn)數(shù)

邊界點(diǎn)：邊界點(diǎn)的半徑范圍內(nèi)的樣本個(gè)數(shù)小于最少點(diǎn)數(shù)大于0

噪聲點(diǎn)：噪聲點(diǎn)的半徑范圍的樣本個(gè)數(shù)為0

1. 根據(jù)半徑、最少點(diǎn)數(shù)區(qū)分核心點(diǎn)、邊界點(diǎn)、噪聲點(diǎn)
2.先對(duì)核心點(diǎn)歸類：
     while:
           隨機(jī)選取一核心點(diǎn)作為當(dāng)前簇
           尋找距離當(dāng)前簇最近的核心點(diǎn):與簇邊緣最近的核心點(diǎn)，，
           if 若該核心點(diǎn)距離當(dāng)前簇的邊界核心點(diǎn)的距離小于半徑:
              則將該核心點(diǎn)歸類到當(dāng)前簇
           if 若剩余的未歸類的核心點(diǎn)距離當(dāng)前簇邊界距離均大于半徑:
              說(shuō)明：距離第numC個(gè)簇最近的核心點(diǎn)不在該簇鄰域內(nèi)，說(shuō)明第numC個(gè)簇已全部分類完畢，可以 
              生成新簇來(lái)歸類核心點(diǎn),則在剩余的未歸類的核心點(diǎn)隨機(jī)選取一核心點(diǎn)歸類到新的簇中
           if 核心點(diǎn)已全部歸類：
              停止迭代
3. 再根據(jù)半徑和已歸類的核心點(diǎn)來(lái)歸類邊界點(diǎn)

優(yōu)點(diǎn)：

能夠識(shí)別任意形狀的樣本. 該算法將具有足夠密度的區(qū)域劃分為簇，并在具有噪聲的空間數(shù)據(jù)庫(kù)中發(fā)現(xiàn)任意形狀的簇，它將簇定義為密度相連的點(diǎn)的大集合。

缺點(diǎn)：

需指定最少點(diǎn)個(gè)數(shù)，半徑(或自動(dòng)計(jì)算半徑)

譜聚類

是從圖論中演化出來(lái)的算法，后來(lái)在聚類中得到了廣泛的應(yīng)用。它的主要思想是把所有的數(shù)據(jù)看做空間中的點(diǎn)，這些點(diǎn)之間可以用邊連接起來(lái)。距離較遠(yuǎn)的兩個(gè)點(diǎn)之間的邊權(quán)重值較低，而距離較近的兩個(gè)點(diǎn)之間的邊權(quán)重值較高。通過(guò)對(duì)所有數(shù)據(jù)點(diǎn)組成的圖進(jìn)行切圖，讓切圖后不同的子圖間邊權(quán)重和盡可能的低，而子圖內(nèi)的邊權(quán)重和盡可能的高，從而達(dá)到聚類的目的。

算法流程：

1. 生成鄰接矩陣(權(quán)重矩陣/相似度矩陣)：W:m*m，用高斯函數(shù)度量樣本之間的距離，距離越遠(yuǎn)，權(quán)重越小

   

2. 生成度量矩陣D：m*m，D=np.diag(np.sum(W,axis=1))、拉普拉斯矩陣L:L=D-W
3. 標(biāo)準(zhǔn)化拉普拉斯矩陣:Ncut切圖:L_norm=D^(-0.5)LD^(-0.5),注意：這里是矩陣叉乘

   

4. 生成標(biāo)準(zhǔn)化拉普拉斯矩陣對(duì)應(yīng)的特征值和特征向量，對(duì)特征值排序(升序)，選取前k個(gè)最小的特征值對(duì)應(yīng)的特征向量，組成m*k矩陣data
5. 對(duì)降維后的矩陣data使用kmeans、GMM或其他聚類方法來(lái)聚類

拉普拉斯映射

簡(jiǎn)單說(shuō)，譜聚類其實(shí)就是使用了一種映射方法，將原有數(shù)據(jù)映射到新的數(shù)據(jù)空間，使得原數(shù)據(jù)中空間位置接近的樣本在映射后更加接近，這種映射稱為拉普拉斯映射。注意：步驟4中是選取最小的k個(gè)特征值對(duì)應(yīng)特征向量，那么問(wèn)題來(lái)了，為什么要選取最小特征值呢？特征值有什么物理意義呢？

對(duì)于一個(gè)方陣(L為對(duì)稱矩陣也是方陣且是半正定矩陣)，可以稱之為變換矩陣，當(dāng)它叉乘某一個(gè)向量時(shí)，其物理意義為對(duì)該向量作旋轉(zhuǎn)和縮放的變換，即將原有向量所在的空間映射到一個(gè)新的空間。那么，縮放尺度如何度量？可以用變換矩陣的特征值來(lái)度量，如下所示A為變換矩陣，向量α為A的特征向量(對(duì)于特征向量，對(duì)其變換時(shí)，只做縮放變換，其向量方向不變，更多詳細(xì)內(nèi)容見看圖就懂：線性代數(shù)之特征值分解與奇異值分解)，λ為特征值，I為單位向量，向量α左乘A等于對(duì)特征向量縮放λ倍。

特征值在物理意義上可以表示為縮放倍數(shù)，特征值越大，對(duì)應(yīng)的特征向量放大倍數(shù)越大，而特征向量越大，對(duì)應(yīng)的樣本點(diǎn)映射后在空間位置上也更分散，而譜聚類或者拉普拉斯特征映射的目標(biāo)就是將原本比較接近的點(diǎn)在映射后更加接近，使得屬于不同簇的樣本的可分離性變強(qiáng)，所以拉普拉斯特征映射自然要選擇小特征值對(duì)應(yīng)的空間，這樣也就實(shí)現(xiàn)了原數(shù)據(jù)中空間位置接近的樣本在映射后更加接近。如下圖是原始特征空間與拉普拉斯特映射后的樣本空間(2d、3d顯示)的聚類結(jié)果

PCA

經(jīng)過(guò)拉普拉斯映射后樣本的可分離性比較好，易于聚類。于此相對(duì)的是，PCA降維選用的降序特征值即選取大的k個(gè)特征值對(duì)應(yīng)的特征向量，因?yàn)镻CA的目的是對(duì)原數(shù)據(jù)作旋轉(zhuǎn)變換，將原數(shù)據(jù)映射到特征基(關(guān)于特征基概念見看圖就懂：線性代數(shù)之特征值分解與奇異值分解)，投影到特征基方向上的樣本相對(duì)比較分散，如下圖所示，二維原數(shù)據(jù)旋轉(zhuǎn)到二維特征基上和降到1維效果圖

總之，特征值越大對(duì)應(yīng)的向量空間方差越大，即向量方向上的數(shù)據(jù)越分散。降維數(shù)據(jù)肯定會(huì)丟失一部分信息，PCA適用于處理高維數(shù)據(jù)，可以在盡可能保留更多信息的同時(shí)對(duì)高維數(shù)據(jù)降維處理，如何保留更多數(shù)據(jù)信息呢？某種意義上，數(shù)據(jù)分布越分散(方差)或者說(shuō)越混亂(熵)，能得到的信息越多，PCA通過(guò)將數(shù)據(jù)映射到特征基上(特征基不止一個(gè))，然后從中選取k個(gè)方差大的特征基(k個(gè)大特征值對(duì)應(yīng)的特征向量)組成新的特征空間，從而實(shí)現(xiàn)降維+保留大部分信息效果。

拉普拉斯映射與PCA區(qū)別

設(shè)有原數(shù)據(jù)X，為m行n列數(shù)據(jù)、m個(gè)樣本n個(gè)特征，k為維度個(gè)數(shù)：

1. 拉普拉斯映射是根據(jù)樣本的相似矩陣作變換得到新的樣本空間，這個(gè)新樣本空間可以直接用來(lái)聚類。
2. PCA是根據(jù)特征(變量)的協(xié)方差矩陣作變換得到一個(gè)變換矩陣，然后使用該變換矩陣映射原數(shù)據(jù)得到：
3. 拉普拉斯映射提取升序特征值對(duì)應(yīng)的特征向量，PCA提取降序特征值對(duì)應(yīng)的特征向量

優(yōu)點(diǎn)：

譜聚類能夠識(shí)別任意形狀的樣本空間且收斂于全局最優(yōu)解，其基本思想是利用樣本數(shù)據(jù)的相似矩陣(拉普拉斯矩陣)進(jìn)行特征分解后得到的特征向量進(jìn)行聚類。

譜聚類只需要數(shù)據(jù)之間的相似度矩陣，因此對(duì)于處理稀疏數(shù)據(jù)的聚類很有效。由于使用了降維，因此在處理高維數(shù)據(jù)聚類時(shí)的復(fù)雜度比傳統(tǒng)聚類算法好

缺點(diǎn)：

如果最終聚類的維度非常高，則由于降維的幅度不夠，算法的運(yùn)行速度和最終聚類效果均不好

聚類效果依賴于相似度矩陣(權(quán)重矩陣/鄰接矩陣)，不同的相似度矩陣得到的最終聚類效果可能差別很大

需指定聚類個(gè)數(shù)，高斯參數(shù)。

ＧＭＭ-高斯混合模型

高斯混合混合模型(GMM)是一種概率生成模型，模型通過(guò)學(xué)習(xí)先驗(yàn)分布后推導(dǎo)后驗(yàn)分布來(lái)實(shí)現(xiàn)聚類。當(dāng)我們做聚類任務(wù)的時(shí)候，可以根據(jù)距離最近原則，將樣本聚類到距離其最近的聚類中心，如k-means算法，或者將樣本聚類到距離某個(gè)簇邊緣最近的簇，如DBSCAN算法，而GMM是假設(shè)樣本每個(gè)類的特征分布遵循高斯分布，即整個(gè)數(shù)據(jù)集可由不同參數(shù)的高斯分布線性組合來(lái)描述，GMM算法可以計(jì)算出每個(gè)樣本屬于各個(gè)簇的概率值并將其聚類到概率值大的簇。

GMM如何實(shí)現(xiàn)？

GMM是以假設(shè)數(shù)據(jù)各個(gè)類別的特征分布是高斯分布為基礎(chǔ)，所以首要步驟就是先得到各個(gè)類別的概率分布密度函數(shù)參數(shù)，對(duì)于一元變量，需要計(jì)算各個(gè)類別的均值和期望，而對(duì)于多元變量，則需要計(jì)算均值和協(xié)方差矩陣。有如下數(shù)據(jù)集X，共有m個(gè)樣本，n項(xiàng)特征，k個(gè)類別

高斯概率分布密度函數(shù)公式如下：

一元變量：n=1

多元變量：n>1

式中，表示協(xié)方差矩陣，n行n列矩陣，表示計(jì)算第k個(gè)類別的協(xié)方差矩陣的行列式。

現(xiàn)有如下數(shù)據(jù)集，如何使用GMM聚類？

在學(xué)習(xí)GMM聚類算法前，先從大學(xué)概率論課本上的一個(gè)例子入手。

例如：投擲一顆骰子，實(shí)驗(yàn)的樣本空間為：S={1,2,3,4,5,6}。

存在以下事件

• 事件X={投擲一個(gè)骰子出現(xiàn)i點(diǎn)}，
• 事件={投擲一個(gè)骰子出現(xiàn)偶數(shù)點(diǎn)}，
• 事件= {投擲一個(gè)骰子出現(xiàn)奇數(shù)點(diǎn)}，

是樣本空間S的一個(gè)劃分，每做一次實(shí)驗(yàn)時(shí)，事件必有一個(gè)且僅有一個(gè)發(fā)生。則有

證明過(guò)程如下：

則事件X={投擲一個(gè)骰子出現(xiàn)i點(diǎn)}的概率p(X)為

式中的稱為先驗(yàn)概率，進(jìn)一步得到以下公式：貝葉斯公式

綜上我們可以得到，投擲一顆骰子后，發(fā)生事件的概率為

回到聚類任務(wù)中，上述 事件X={投擲一個(gè)骰子出現(xiàn)i點(diǎn)}其實(shí)就是我們的訓(xùn)練集對(duì)應(yīng)X，事件

就是類別，對(duì)應(yīng)y。如下所示：

p(X)是訓(xùn)練集樣本出現(xiàn)的概率，公式如下：

GMM代價(jià)函數(shù)

GMM首先需要計(jì)算每個(gè)類別的分布函數(shù)的參數(shù)，如何估計(jì)參數(shù)呢？可以采用極大似然估計(jì)方法。

極大似然估計(jì)，就是利用已知的樣本信息，反推最具有可能(大概率)導(dǎo)致這些樣本出現(xiàn)的模型參數(shù)值。換句話說(shuō)，極大似然估計(jì)提供了一種通過(guò)給定觀察數(shù)據(jù)來(lái)估計(jì)模型參數(shù)的方法，即：模型已定，參數(shù)未知?？梢赃@樣理解，既然事情(樣本)已經(jīng)發(fā)生了，為什么不讓這個(gè)結(jié)果出現(xiàn)的可能性大呢？這也就是極大似然估計(jì)核心。

通過(guò)極大似然估計(jì)方法來(lái)使樣本出現(xiàn)的概率p(X)大從而得到分布函數(shù)參數(shù)，這樣我們可以得到代價(jià)函數(shù)

由于連乘可能會(huì)導(dǎo)致下溢，所以需要取對(duì)數(shù)。對(duì)數(shù)函數(shù)是一個(gè)嚴(yán)格遞增的函數(shù)，取對(duì)數(shù)后不會(huì)改變數(shù)據(jù)的相對(duì)關(guān)系，即對(duì)數(shù)化后，我們?nèi)匀豢梢垣@得具有相同臨界點(diǎn)的最優(yōu)化函數(shù)，代價(jià)函數(shù)如下所示

已知多元變量的高斯分布公式如下

可以得到

注意，式中，這里直接用概率分布密度函數(shù)表示概率分布可能有一定誤導(dǎo)性。為什么這樣表達(dá)呢？如下

是每個(gè)類的一個(gè)常量乘法因子，在之后的對(duì)后驗(yàn)概率進(jìn)行規(guī)范化的時(shí)候就抵消掉了。因此可以直接使用來(lái)估計(jì)類條件概率。

綜上，GMM代價(jià)函數(shù)的最終公式如下

通過(guò)求解代價(jià)函數(shù)，就可以得到各個(gè)類別的高斯分布函數(shù)參數(shù)，進(jìn)而能計(jì)算樣本屬于某個(gè)類別的概率，從而實(shí)現(xiàn)聚類，公式如下

以上過(guò)程其實(shí)就是一個(gè)建模過(guò)程，建模過(guò)程包括如下

1. 分析業(yè)務(wù)類型(聚類問(wèn)題)，√
2. 確定模型類型(非參數(shù)+概率+生成模型)，√
3. 確定代價(jià)函數(shù)，√
4. 目標(biāo)函數(shù)：超參數(shù)
5. 優(yōu)化模型：調(diào)參

在得到代價(jià)函數(shù)后，我們還要確定這個(gè)代價(jià)函數(shù)是否具有凸性，因?yàn)橥购瘮?shù)有一個(gè)好性質(zhì)，若代價(jià)函數(shù)是凸函數(shù)，則其局部最優(yōu)解也是全局最優(yōu)解。若無(wú)法得到凸代價(jià)函數(shù)，則嘗試更換模型或者使用迭代算法來(lái)逼近全局最優(yōu)解。

目標(biāo)函數(shù)一般是代價(jià)函數(shù)+正則項(xiàng)，用來(lái)確定超參數(shù)，防止過(guò)擬合，來(lái)提高模型泛化能力。本文這里先跳過(guò)這一步，直接講如何計(jì)算參數(shù)。

使用EM算法計(jì)算GMM參數(shù)

EM(期望大)算法是一個(gè)迭代算法，其思想就是多次迭代來(lái)估計(jì)參數(shù)，直到算法收斂。EM算法就是一個(gè)迭代逼近過(guò)程，若目標(biāo)函數(shù)為非凸函數(shù)，則EM算法不能保證收斂至全局最優(yōu)解，且EM算法的求解結(jié)果與初值的選擇有較大關(guān)系，該算法對(duì)初值敏感。

EM算法求解參數(shù)思路可以將其理解為對(duì)兩個(gè)未知變量的方程求解。首先固定其中一個(gè)未知數(shù)，求另一個(gè)未知數(shù)的偏導(dǎo)數(shù)，之后再反過(guò)來(lái)固定后者，求前者的偏導(dǎo)數(shù)，反復(fù)迭代直到目標(biāo)函數(shù)值不變、收斂。EM算法就是相互迭代，求出一個(gè)穩(wěn)定值，用于在無(wú)法直接找到參數(shù)的情況下尋找模型的大似然估計(jì)(MLE)。它包括兩個(gè)步驟:期望步驟和大化步驟。在聚類問(wèn)題中，步驟如下

1. 初始化參數(shù)：混合高斯分布函數(shù)參數(shù)
2. 根據(jù)估計(jì)的參數(shù)計(jì)算簇成員后驗(yàn)概率：
3. 大化步驟：代價(jià)函數(shù)代入，求參數(shù)偏導(dǎo)，更新每一個(gè)參數(shù)
   (分別可以只用一個(gè)未知量來(lái)表達(dá))
4. 重復(fù)1、2步驟直到對(duì)數(shù)似然值收斂。

具體步驟如下

1、初始化參數(shù)，根據(jù)估計(jì)參數(shù)計(jì)算給定數(shù)據(jù)點(diǎn)屬于類別的概率(后驗(yàn)概率)：

2、大化步驟：對(duì)代價(jià)函數(shù)求偏導(dǎo)， 根據(jù)第一步得到的來(lái)更新每一個(gè)參數(shù),

3、重復(fù)1、2步驟，直到算法收斂。

參數(shù)推導(dǎo)過(guò)程

可通過(guò)對(duì)代價(jià)函數(shù)求偏導(dǎo)得到，過(guò)程比較復(fù)雜，所以本文從另一個(gè)角度來(lái)解釋參數(shù)的計(jì)算過(guò)程。

關(guān)于均值μ：

關(guān)于協(xié)方差矩陣如何計(jì)算：給定如下訓(xùn)練集X:m*2，假設(shè)有k個(gè)類別，則

GMM的代價(jià)函數(shù)是大化數(shù)據(jù)X出現(xiàn)的概率p(X)。若多次迭代后的p(X)保持不變，則說(shuō)明程序已收斂。在得到參數(shù)，即得到數(shù)據(jù)集每個(gè)類別的概率分布函數(shù)，就可以計(jì)算每個(gè)樣本屬于各個(gè)類別的概率，樣本選擇大的概率值對(duì)應(yīng)的聚類中心，從而實(shí)現(xiàn)聚類。

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

優(yōu)點(diǎn)：

GMM假設(shè)生成數(shù)據(jù)的是一種混合的高斯分布，為模型找到大似然估計(jì)。與將數(shù)據(jù)點(diǎn)硬分配到聚類的K-means方法（假設(shè)圍繞質(zhì)心的數(shù)據(jù)呈圓形分布）相比，它使用了將數(shù)據(jù)點(diǎn)軟分配到聚類的方法（即概率性，因此更好）。速度：它是混合模型學(xué)習(xí)算法中的最快算法;無(wú)偏差性：由于此算法僅大化可能性，因此不會(huì)使均值趨于零，也不會(huì)使聚類大小具有可能適用或不適用的特定結(jié)構(gòu)。
（A）通過(guò)使用軟分配捕獲屬于不同聚類的數(shù)據(jù)點(diǎn)的不確定性，（B）對(duì)圓形聚類沒(méi)有偏見。即使是非線性數(shù)據(jù)分布，它也能很好地工作，具有較強(qiáng)的魯棒性

缺點(diǎn)：

• 奇異性：當(dāng)每個(gè)混合模型的點(diǎn)數(shù)不足時(shí)，估計(jì)協(xié)方差矩陣將變得困難，并且除非對(duì)協(xié)方差進(jìn)行人為正則化，否則該算法會(huì)發(fā)散并尋找無(wú)窮大似然函數(shù)值的解。GMM:需要求逆

• 分量數(shù)量：該算法將始終使用它可以使用的所有分量，所以在沒(méi)有外部提示的情況下，需要留存數(shù)據(jù)或者信息理論標(biāo)準(zhǔn)來(lái)決定用多少個(gè)分量。

• 適合聚類球狀類簇，不能發(fā)現(xiàn)一些混合度較高，非球狀類簇

• 需要指定簇個(gè)數(shù)

MeanShift-均值遷移

該算法也叫做均值漂移，在目標(biāo)追蹤中應(yīng)用廣泛。本身其實(shí)是一種基于密度的聚類算法。

1、算法思路：

主要思路是：計(jì)算某一點(diǎn)A與其周圍半徑R內(nèi)的向量距離的平均值M即遷移向量，更新該點(diǎn)下一步的遷移位置（A=M+A）。當(dāng)該點(diǎn)不再移動(dòng)時(shí)(norm(Mnew-Mold)

2、如何計(jì)算遷移向量M

step1:隨機(jī)選擇一點(diǎn)為初始簇心點(diǎn)（不完全隨機(jī)：不能把噪聲點(diǎn)/離群點(diǎn)作為初始簇心，以防乒乓效應(yīng)）

step2: 根據(jù)初始半徑R，選擇以R為半徑的圓的范圍內(nèi)的點(diǎn)分別與簇心點(diǎn)的向量的平均值作為遷移向量M

表示：屬于當(dāng)前簇c內(nèi)的點(diǎn)集合，簇c：半徑為R，簇心為xc,簇內(nèi)樣本點(diǎn)數(shù)量為k。

3、如何遷移

根據(jù)遷移向量M，更新簇心

4、如何收斂

遷移向量M前后變化量小于閾值且樣本點(diǎn)(除了離群點(diǎn))均已歸類，則停止運(yùn)行

5、如何成簇

norm(Mnew-Mold)>TH時(shí):
    判斷norm(M)TH:說(shuō)明 當(dāng)前簇未成形，需要繼續(xù)遷移
norm(Mnew-Mold)
6、如何調(diào)整簇半徑大小？
當(dāng)遷移向量長(zhǎng)度接近0時(shí)，需要擴(kuò)大簇半徑即擴(kuò)大搜索范圍，看看擴(kuò)大范圍后，簇內(nèi)點(diǎn)是否增加，即遷移向量增量是否大于閾值Th，若小于閾值，則沒(méi)必要繼續(xù)遷移(當(dāng)前簇已穩(wěn)定)，反之繼續(xù)進(jìn)行遷移計(jì)算。
關(guān)于調(diào)整簇半徑策略：根據(jù)當(dāng)前簇成員調(diào)整簇半徑
Rold-->當(dāng)前半斤 Rold范圍內(nèi)簇成員集合： 
 
這里max()表示：如a=[[3,5],[9,2]],max(a)=[9,5]
7、擴(kuò)展
計(jì)算均值的遷移向量-->計(jì)算核函數(shù)形式的遷移向量
 
優(yōu)點(diǎn)：
與kmeans相比，均值遷移無(wú)需指定簇個(gè)數(shù)，自動(dòng)發(fā)現(xiàn)簇個(gè)數(shù)，需指定初始半徑(帶寬)(或者算法自動(dòng)計(jì)算)。算法相對(duì)k-means分類結(jié)果比較穩(wěn)定
缺點(diǎn)：
算法分類結(jié)果易受噪聲點(diǎn)(離群點(diǎn))干擾，若初始簇心點(diǎn)為離群點(diǎn)，可能會(huì)發(fā)生乒乓效應(yīng)，算法無(wú)限循環(huán)，需數(shù)據(jù)預(yù)處理(過(guò)濾噪聲點(diǎn))或者改變距離計(jì)算方法。
適合聚類球狀類簇，不能發(fā)現(xiàn)一些混合度較高，非球狀類簇
計(jì)算復(fù)雜度高
R半徑非自適應(yīng)的menshift聚類算法聚類結(jié)果取決于半徑(帶寬)的設(shè)置，半徑太小，收斂太慢，簇類個(gè)數(shù)過(guò)多；半徑太大，一些簇類可能會(huì)丟失。
層次聚類
訓(xùn)練數(shù)據(jù)X，
 
例如有下數(shù)據(jù)
 
各個(gè)樣本點(diǎn)之間的距離：
 
 
算法流程：
 
1、每個(gè)樣本都視為一個(gè)簇
2、計(jì)算各個(gè)樣本點(diǎn)之間的距離(相似度)，生成m*m的距離矩陣dis
3、尋找最近的兩個(gè)簇(尋找矩陣dis中的非0元素中的最小值對(duì)應(yīng)的索引，i1，i2)，將它們歸為一類(計(jì)算兩個(gè)點(diǎn)/簇的均值means，如何歸為同一類？-->X[[i1,i2],:]=menas)，本算法中衡量距離方法：計(jì)算樣本點(diǎn)到簇心的距離->average
a=copy.deepcopy(X)
i,j = np.unravel_index(np.argmin(dis), dis.shape)#獲取多維矩陣xx值對(duì)應(yīng)的索引
listIJ = findRow(a,i1,i2)#在X中尋找與a[i1,:],a[i2,:]樣本點(diǎn)相同的所有樣本點(diǎn)對(duì)應(yīng)的索引
means = np.mean(X[listIJ,:],axis=0)#計(jì)算最近的樣本點(diǎn)/簇的均值
a[listIJ,:] = means#賦予相同的均值即視為歸為同一類
Tree[iter] = copy.deepcopy(a)#生成聚類樹

def findRow(inX,i,j):
    listI,listJ= [],[]
    for m in range(inX.shape[0]):
        if sum(abs(inX[m,:]-inX[i,:]))<1e-10: listI.append(m) elif sum(abs(inX[m, :] - inX[j,:]))<1e-10: listJ.append(m) listI.extend(listJ) return listI
4、重復(fù)步驟2、3，直到所有樣本歸為一類，或者歸為指定類別個(gè)數(shù)k
a=copy.deepcopy(X)
while len(set(a[:,0]))>1：#while len(set(a[:,0]))>k
    i,j = np.unravel_index(np.argmin(dis), dis.shape)#獲取多維矩陣xx值對(duì)應(yīng)的索引
    listIJ = findRow(a,i1,i2)#在X中尋找與a[i1,:],a[i2,:]樣本點(diǎn)相同的所有樣本點(diǎn)對(duì)應(yīng)的索引
    means = np.mean(X[listIJ,:],axis=0)#計(jì)算最近的樣本點(diǎn)/簇的均值
    a[listIJ,:] = means#賦予相同的均值即視為歸為同一類
    Tree[iter] = copy.deepcopy(a)#生成聚類樹
#聚類樹：每一層都是一個(gè)分類結(jié)果，簇?cái)?shù)量由多到少。
優(yōu)點(diǎn)：
一次性得到聚類樹，每一層均為分類結(jié)果。算法相對(duì)k-means分類結(jié)果比較穩(wěn)定。
相似度規(guī)則(距離衡量)容易定義
可以發(fā)現(xiàn)類別的層次關(guān)系
缺點(diǎn)：
計(jì)算復(fù)雜度高，不適合數(shù)據(jù)量大的
由于類聚類之間的距離(相似度)衡量方法不同，算法分類結(jié)果易受噪聲點(diǎn)(離群點(diǎn))干擾，需數(shù)據(jù)預(yù)處理(過(guò)濾噪聲點(diǎn))或者改變距離計(jì)算方法。
適合聚類球狀類簇，不能發(fā)現(xiàn)一些混合度較高，非球狀類簇
 
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

本文名稱：六種常見聚類算法-創(chuàng)新互聯(lián)
文章鏈接：http://weahome.cn/article/ddcssd.html