大家晚上好，我是阿濤。

今天的主題是聚類算法，小結(jié)一下，也算是炒冷飯了，好久不用真忘了。

小目錄：

1.K-means聚類2.Mean-Shift聚類3.Dbscan聚類4.層次聚類5.GMM_EM聚類

【1】.K-means聚類

1.算法介紹

kmeans算法又名k均值算法,K-means算法中的k表示的是聚類為k個(gè)簇，means代表取每一個(gè)聚類中數(shù)據(jù)值的均值作為該簇的中心，或者稱為質(zhì)心(質(zhì)量中心，可以利用球坐標(biāo)進(jìn)行三重積分求解)，即用每一個(gè)的類的質(zhì)心對(duì)該簇進(jìn)行描述。可以看下圖直觀點(diǎn)：

2.算法思想

先從樣本集中隨機(jī)選取 k個(gè)樣本作為簇中心，并計(jì)算所有樣本與這 k個(gè)“簇中心”的距離，對(duì)于每一個(gè)樣本，將其劃分到與其距離最近的“簇中心”所在的簇中，對(duì)于新的簇重新計(jì)算各個(gè)簇的新的“簇中心”，然后再繼續(xù)距離知道簇中心不發(fā)生變化。

?根據(jù)以上描述，我們可以得到實(shí)現(xiàn)kmeans算法的主要四點(diǎn)：

(1)簇個(gè)數(shù) k 的選擇

(2)各個(gè)樣本點(diǎn)到“簇中心”的距離

(3)根據(jù)新劃分的簇，更新“簇中心”

(4)重復(fù)上述2、3過(guò)程，直至"簇中心"沒有移動(dòng)

3.優(yōu)缺點(diǎn)

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

1.容易實(shí)現(xiàn)，計(jì)算速度快

缺點(diǎn)：

1.可能收斂到局部最小值，在大規(guī)模數(shù)據(jù)上收斂較慢；我們必須提前知道數(shù)據(jù)有多少類/組。

2.K值需要預(yù)先給定，屬于預(yù)先知識(shí)，很多情況下K值的估計(jì)是非常困難的，對(duì)于像計(jì)算全部微信用戶的交往圈這樣的場(chǎng)景就完全的沒辦法用K-Means進(jìn)行。對(duì)于可以確定K值不會(huì)太大但不明確精確的K值的場(chǎng)景，可以進(jìn)行迭代運(yùn)算，然后找出Cost Function最小時(shí)所對(duì)應(yīng)的K值，這個(gè)值往往能較好的描述有多少個(gè)簇類。

3.K-Means算法對(duì)初始選取的聚類中心點(diǎn)是敏感的，不同的隨機(jī)種子點(diǎn)得到的聚類結(jié)果完全不同

4.K-Means算法對(duì)離群點(diǎn)的數(shù)據(jù)進(jìn)行聚類時(shí)，K均值也有問(wèn)題，這種情況下，離群點(diǎn)檢測(cè)和刪除有很大的幫助。(異常值對(duì)聚類中心影響很大，需要離群點(diǎn)檢測(cè)和剔除)

4.K-Means算法并不是適用所有的樣本類型。它不能處理非球形簇、不同尺寸和不同密度的簇。如下圖：

4.詳細(xì)步驟

(1)K值的選擇

k 的選擇一般是按照實(shí)際需求進(jìn)行決定，或在實(shí)現(xiàn)算法時(shí)直接給定 k 值。

(2)距離度量

將對(duì)象點(diǎn)分到距離聚類中心最近的那個(gè)簇中需要最近鄰的度量策略，在歐式空間中采用的是歐式距離，在處理文檔中采用的是余弦相似度函數(shù)，有時(shí)候也采用曼哈頓距離作為度量，不同的情況用的度量公式是不同的。

(補(bǔ)充：歐式空間：歐幾里得空間就是在對(duì)現(xiàn)實(shí)空間的規(guī)則抽象和推廣(從n<=3推廣到有限n維空間))

歐式距離公式：

曼哈頓距離公式：

余弦相似度：

(3)新質(zhì)心的計(jì)算

對(duì)于分類后的產(chǎn)生的k個(gè)簇，分別計(jì)算到簇內(nèi)其他點(diǎn)距離均值最小的點(diǎn)作為質(zhì)心(對(duì)于擁有坐標(biāo)的簇可以計(jì)算每個(gè)簇坐標(biāo)的均值作為質(zhì)心)

(4)是否停止K-means

?? 質(zhì)心不再改變，或給定loop最大次數(shù)loopLimit

【2】.Mean-Shift聚類

1.算法介紹

Mean Shift算法，又稱為均值漂移算法，Mean Shift的概念最早是由Fukunage在1975年提出的，在后來(lái)由Yizong Cheng對(duì)其進(jìn)行擴(kuò)充，主要提出了兩點(diǎn)的改進(jìn)：

• 定義了核函數(shù)；

• 增加了權(quán)重系數(shù)。

核函數(shù)的定義使得偏移值對(duì)偏移向量的貢獻(xiàn)隨之樣本與被偏移點(diǎn)的距離的不同而不同。權(quán)重系數(shù)使得不同樣本的權(quán)重不同。Mean Shift算法在聚類，圖像平滑、分割以及視頻跟蹤等方面有廣泛的應(yīng)用。

2.算法思想

均值漂移聚類是基于滑動(dòng)窗口的算法，來(lái)找到數(shù)據(jù)點(diǎn)的密集區(qū)域。這是一個(gè)基于質(zhì)心的算法，通過(guò)將中心點(diǎn)的候選點(diǎn)更新為滑動(dòng)窗口內(nèi)點(diǎn)的均值來(lái)完成，來(lái)定位每個(gè)組/類的中心點(diǎn)。然后對(duì)這些候選窗口進(jìn)行相似窗口進(jìn)行去除，最終形成中心點(diǎn)集及相應(yīng)的分組。

3.優(yōu)缺點(diǎn)

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

(1)不同于K-Means算法，均值漂移聚類算法不需要我們知道有多少類/組。

(2)基于密度的算法相比于K-Means受均值影響較小。

缺點(diǎn)：

(1)窗口半徑r的選擇可能是不重要的。

4.詳細(xì)步驟

1. 確定滑動(dòng)窗口半徑r，以隨機(jī)選取的中心點(diǎn)C半徑為r的圓形滑動(dòng)窗口開始滑動(dòng)。均值漂移類似一種爬山算法，在每一次迭代中向密度更高的區(qū)域移動(dòng)，直到收斂。在指定區(qū)域內(nèi)計(jì)算出每個(gè)樣本點(diǎn)漂移均值。

2. 每一次滑動(dòng)到新的區(qū)域，計(jì)算滑動(dòng)窗口內(nèi)的均值來(lái)作為中心點(diǎn)，滑動(dòng)窗口內(nèi)的點(diǎn)的數(shù)量為窗口內(nèi)的密度。在每一次移動(dòng)中，窗口會(huì)像密度更高的區(qū)域移動(dòng)。

3. 移動(dòng)窗口，計(jì)算窗口內(nèi)的中心點(diǎn)以及窗口內(nèi)的密度，知道沒有方向在窗口內(nèi)可以容納更多的點(diǎn)，即一直移動(dòng)到圓內(nèi)密度不再增加為止。

4. 步驟一到三會(huì)產(chǎn)生很多個(gè)滑動(dòng)窗口，當(dāng)多個(gè)滑動(dòng)窗口重疊時(shí)，保留包含最多點(diǎn)的窗口，然后根據(jù)數(shù)據(jù)點(diǎn)所在的滑動(dòng)窗口進(jìn)行聚類。

?

【3】.Dbscan聚類

1.算法介紹

與均值漂移聚類類似，DBSCAN也是基于密度的聚類算法。DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一個(gè)比較有代表性的基于密度的聚類算法，類似于均值轉(zhuǎn)移聚類算法，但它有幾個(gè)顯著的優(yōu)點(diǎn)。

2.算法思想

?DBSCAN的聚類定義很簡(jiǎn)單：由密度可達(dá)關(guān)系導(dǎo)出的最大密度相連的樣本集合，即為我們最終聚類的一個(gè)類別，或者說(shuō)一個(gè)簇。

這個(gè)DBSCAN的簇里面可以有一個(gè)或者多個(gè)核心對(duì)象。如果只有一個(gè)核心對(duì)象，則簇里其他的非核心對(duì)象樣本都在這個(gè)核心對(duì)象的??-鄰域里；如果有多個(gè)核心對(duì)象，則簇里的任意一個(gè)核心對(duì)象的??-鄰域中一定有一個(gè)其他的核心對(duì)象，否則這兩個(gè)核心對(duì)象無(wú)法密度可達(dá)。這些核心對(duì)象的??-鄰域里所有的樣本的集合組成的一個(gè)DBSCAN聚類簇。

那么怎么才能找到這樣的簇樣本集合呢？DBSCAN使用的方法很簡(jiǎn)單，它任意選擇一個(gè)沒有類別的核心對(duì)象作為種子，然后找到所有這個(gè)核心對(duì)象能夠密度可達(dá)的樣本集合，即為一個(gè)聚類簇。接著繼續(xù)選擇另一個(gè)沒有類別的核心對(duì)象去尋找密度可達(dá)的樣本集合，這樣就得到另一個(gè)聚類簇。一直運(yùn)行到所有核心對(duì)象都有類別為止。

3.優(yōu)缺點(diǎn)

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

(1)不需要知道簇的數(shù)量

(2) 可以對(duì)任意形狀的稠密數(shù)據(jù)集進(jìn)行聚類，相對(duì)的，K-Means之類的聚類算法一般只適用于凸數(shù)據(jù)集。

(3) 可以在聚類的同時(shí)發(fā)現(xiàn)異常點(diǎn)，對(duì)數(shù)據(jù)集中的異常點(diǎn)不敏感。

(4) 聚類結(jié)果沒有偏倚，相對(duì)的，K-Means之類的聚類算法初始值對(duì)聚類結(jié)果有很大影響。

缺點(diǎn)：

(1)如果樣本集的密度不均勻、聚類間距差相差很大時(shí)，聚類質(zhì)量較差，這時(shí)用DBSCAN聚類一般不適合。

(2) 如果樣本集較大時(shí)，聚類收斂時(shí)間較長(zhǎng)，此時(shí)可以對(duì)搜索最近鄰時(shí)建立的KD樹或者球樹進(jìn)行規(guī)模限制來(lái)改進(jìn)。

(3) 調(diào)參相對(duì)于傳統(tǒng)的K-Means之類的聚類算法稍復(fù)雜，主要需要對(duì)距離閾值??，鄰域樣本數(shù)閾值MinPts聯(lián)合調(diào)參，不同的參數(shù)組合對(duì)最后的聚類效果有較大影響。

4.詳細(xì)步驟

1. 首先確定半徑r和minPoints. 從一個(gè)沒有被訪問(wèn)過(guò)的任意數(shù)據(jù)點(diǎn)開始，以這個(gè)點(diǎn)為中心，r為半徑的圓內(nèi)包含的點(diǎn)的數(shù)量是否大于或等于minPoints，如果大于或等于minPoints則改點(diǎn)被標(biāo)記為central point,反之則會(huì)被標(biāo)記為noise point。

2. 重復(fù)1的步驟，如果一個(gè)noise point存在于某個(gè)central point為半徑的圓內(nèi)，則這個(gè)點(diǎn)被標(biāo)記為邊緣點(diǎn)，反之仍為noise point。重復(fù)步驟1，直到所有的點(diǎn)都被訪問(wèn)過(guò)。

【4】.GMM_EM聚類

1.算法介紹

K-Means的缺點(diǎn)在于對(duì)聚類中心均值的簡(jiǎn)單使用。下面的圖中的兩個(gè)圓如果使用K-Means則不能作出正確的類的判斷。同樣的，如果數(shù)據(jù)集中的點(diǎn)類似下圖中曲線的情況也是不能正確分類的。

2.算法思想

使用高斯混合模型(GMM)做聚類首先假設(shè)數(shù)據(jù)點(diǎn)是呈高斯分布的，相對(duì)應(yīng)K-Means假設(shè)數(shù)據(jù)點(diǎn)是圓形的，高斯分布(橢圓形)給出了更多的可能性。我們有兩個(gè)參數(shù)來(lái)描述簇的形狀：均值和標(biāo)準(zhǔn)差。所以這些簇可以采取任何形狀的橢圓形，因?yàn)樵趚，y方向上都有標(biāo)準(zhǔn)差。因此，每個(gè)高斯分布被分配給單個(gè)簇。
所以要做聚類首先應(yīng)該找到數(shù)據(jù)集的均值和標(biāo)準(zhǔn)差，我們將采用一個(gè)叫做最大期望(EM)的優(yōu)化算法。

3.優(yōu)缺點(diǎn)

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

(1)GMMs使用均值和標(biāo)準(zhǔn)差，簇可以呈現(xiàn)出橢圓形而不是僅僅限制于圓形。K-Means是GMMs的一個(gè)特殊情況，是方差在所有維度上都接近于0時(shí)簇就會(huì)呈現(xiàn)出圓形。

(2)GMMs是使用概率，所有一個(gè)數(shù)據(jù)點(diǎn)可以屬于多個(gè)簇。例如數(shù)據(jù)點(diǎn)X可以有百分之20的概率屬于A簇，百分之80的概率屬于B簇。也就是說(shuō)GMMs可以支持混合資格。

?缺點(diǎn)：

(1)計(jì)算復(fù)雜，是一種軟聚類，給出樣本的類別概率

補(bǔ)充：

當(dāng)引入一些額外條件，GMM就退化成了K-means：

4.詳細(xì)步驟

1. 選擇簇的數(shù)量(與K-Means類似)并隨機(jī)初始化每個(gè)簇的高斯分布參數(shù)(均值和方差)。也可以先觀察數(shù)據(jù)給出一個(gè)相對(duì)精確的均值和方差。

2. 給定每個(gè)簇的高斯分布，計(jì)算每個(gè)數(shù)據(jù)點(diǎn)屬于每個(gè)簇的概率。一個(gè)點(diǎn)越靠近高斯分布的中心就越可能屬于該簇。

3. 基于這些概率我們計(jì)算高斯分布參數(shù)使得數(shù)據(jù)點(diǎn)的概率最大化，可以使用數(shù)據(jù)點(diǎn)概率的加權(quán)來(lái)計(jì)算這些新的參數(shù)，權(quán)重就是數(shù)據(jù)點(diǎn)屬于該簇的概率。

4. 重復(fù)迭代2和3直到在迭代中的變化不大。

【5】.層次聚類

1.算法介紹

層次聚類算法分為兩類：自上而下和自下而上。

凝聚層級(jí)聚類(HAC)是自下而上的一種聚類算法。HAC首先將每個(gè)數(shù)據(jù)點(diǎn)視為一個(gè)單一的簇，然后計(jì)算所有簇之間的距離來(lái)合并簇，知道所有的簇聚合成為一個(gè)簇為止。

分裂(divisive)層次聚類：分裂的層次聚類與凝聚的層次聚類相反，采用自頂向下的策略，它首先將所有對(duì)象置于同一個(gè)簇中，然后逐漸細(xì)分為越來(lái)越小的簇，直到每個(gè)對(duì)象自成一簇，或者達(dá)到了某個(gè)終止條件。該種方法一般較少使用。

2.優(yōu)缺點(diǎn)

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

(1)不需要知道有多少個(gè)簇

(2)對(duì)于距離度量標(biāo)準(zhǔn)的選擇并不敏感

缺點(diǎn)：

(1)效率低

3.詳細(xì)步驟

1. 首先我們將每個(gè)數(shù)據(jù)點(diǎn)視為一個(gè)單一的簇，然后選擇一個(gè)測(cè)量?jī)蓚€(gè)簇之間距離的度量標(biāo)準(zhǔn)。例如我們使用average linkage作為標(biāo)準(zhǔn)，它將兩個(gè)簇之間的距離定義為第一個(gè)簇中的數(shù)據(jù)點(diǎn)與第二個(gè)簇中的數(shù)據(jù)點(diǎn)之間的平均距離。

2. 在每次迭代中，我們將兩個(gè)具有最小averagelinkage的簇合并成為一個(gè)簇。

3. 重復(fù)步驟2知道所有的數(shù)據(jù)點(diǎn)合并成一個(gè)簇，然后選擇我們需要多少個(gè)簇。

后記：附上一個(gè)總結(jié)的聚類算法對(duì)比表

對(duì)了也附上代碼把：

1.kmeans

結(jié)果：

2.Mean-shift

結(jié)果：

3.Dbscan聚類

結(jié)果：

4.GMM_EM

結(jié)果：

5.層次聚類

結(jié)果：

往期推薦閱讀▽白話MCMC爬蟲之scrapy框架不要再被這些圖騙了我被詐騙了？極速可視化BI——Tableau

End

作者：濤網(wǎng)站：http://atshare.top/

半壺水全棧工程師，好讀書，甚喜之

總結(jié)

以上是生活随笔為你收集整理的a*算法的优缺点_五种聚类算法一览与python实现的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。