K-means聚類算法

零. 說在前面：

什么是特征向量？
用來描述樣本點(diǎn)的一組數(shù)據(jù)，要和我們數(shù)學(xué)中的向量區(qū)別一下，本質(zhì)來說就是個(gè)數(shù)組，數(shù)組中的每個(gè)元素代表從不同角度描述樣本點(diǎn)的值。

K-means 是我們最常用的基于歐式距離的聚類算法，其認(rèn)為兩個(gè)目標(biāo)的距離越近，相似度越大。
聚類就是對大量末知標(biāo)注的數(shù)據(jù)集，按照數(shù)據(jù)內(nèi)部存在的數(shù)據(jù)特征將數(shù)據(jù)集劃分為多個(gè)不同的類別，使類別內(nèi)的數(shù)據(jù)比較相似，類別之間的數(shù)據(jù)相似度比較大，屬于無監(jiān)督學(xué)習(xí)。
聚類算法的本質(zhì)就是使得簇類樣本盡可能相似，簇于簇間盡可能不同

和分類算法的區(qū)別：
分類算法是先有分類在來數(shù)據(jù)。
聚類算法是先有數(shù)據(jù)在來分類。

一. 算法步驟

1、首先確定一個(gè)k值，即我們希望將數(shù)據(jù)集經(jīng)過聚類得到k個(gè)集合。

2、從數(shù)據(jù)集中隨機(jī)選擇k個(gè)數(shù)據(jù)點(diǎn)作為質(zhì)心。

3、對數(shù)據(jù)集中每一個(gè)點(diǎn)，計(jì)算其與每一個(gè)質(zhì)心的距離（如歐式距離），離哪個(gè)質(zhì)心近，就劃分到那個(gè)質(zhì)心所屬的集合。

4、把所有數(shù)據(jù)歸好集合后，一共有k個(gè)集合。然后重新計(jì)算每個(gè)集合的質(zhì)心。

5、如果新計(jì)算出來的質(zhì)心和原來的質(zhì)心之間的距離小于某一個(gè)設(shè)置的閾值（表示重新計(jì)算的質(zhì)心的位置變化不大，趨于穩(wěn)定，或者說收斂），我們可以認(rèn)為聚類已經(jīng)達(dá)到期望的結(jié)果，算法終止。

6、如果新質(zhì)心和原質(zhì)心距離變化很大，需要迭代3~5步驟。

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

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

1、原理比較簡單，實(shí)現(xiàn)也是很容易，收斂速度快。

2、當(dāng)結(jié)果簇是密集的，而簇與簇之間區(qū)別明顯時(shí), 它的效果較好。

3、主要需要調(diào)參的參數(shù)僅僅是簇?cái)?shù)k。

缺點(diǎn)：

1、K值需要預(yù)先給定，很多情況下K值的估計(jì)是非常困難的。

2、K-Means算法對初始選取的質(zhì)心點(diǎn)是敏感的，不同的隨機(jī)種子點(diǎn)得到的聚類結(jié)果完全不同 ，對結(jié)果影響很大。

3、采用迭代方法，可能只能得到局部的最優(yōu)解，而無法得到全局的最優(yōu)解。

三. 算法實(shí)現(xiàn)

算法使用sklearn實(shí)現(xiàn)：

step 1 創(chuàng)建數(shù)據(jù)集合：

首先我們創(chuàng)建一個(gè)由500個(gè)樣本構(gòu)成的數(shù)據(jù)集合，我們首先將自定義劃分為四類。

from sklearn.datasets import make_blobs
import matplotlib.pyplot as plt
#自己創(chuàng)建一個(gè)大小為500的數(shù)據(jù)集，由兩維特征構(gòu)成
X, y = make_blobs(n_samples=500,n_features=2,centers=4,random_state=1)

具體長這樣：

color = ["red","pink","orange","gray"]
fig, ax1 = plt.subplots(1)
for i in range(4):
    ax1.scatter(X[y==i, 0], X[y==i, 1]
                ,marker='o' #點(diǎn)的形狀
                ,s=8 #點(diǎn)的大小
                ,c=color[i]
                )
plt.show()

setp 2 基于分布進(jìn)行聚類

首先，我們要猜測一下，這個(gè)數(shù)據(jù)中有幾簇？
先猜測為3簇

from sklearn.cluster import KMeans
n_clusters = 3#首先測試的超參數(shù)
cluster = KMeans(n_clusters=n_clusters, random_state=0).fit(X)
y_pred = cluster.labels_
centroid = cluster.cluster_centers_

其中n_clusters代表我們聚類的簇?cái)?shù)，y_pred代表對應(yīng)元素聚類的類別，centroid代表每個(gè)類別的中心點(diǎn)。
現(xiàn)在我們打印一下聚類結(jié)果：

color = ["red","pink","orange","gray"]
fig, ax1 = plt.subplots(1)
for i in range(n_clusters):
    ax1.scatter(X[y_pred==i, 0], X[y_pred==i, 1]
                ,marker='o'
                ,s=8
                ,c=color[i]
                )#循環(huán)畫小樣本預(yù)測點(diǎn)的位置
    ax1.scatter(centroid[:,0],centroid[:,1]
                ,marker="x"
                ,s=18
                ,c="white")#循環(huán)畫質(zhì)心的位置
plt.show()

發(fā)現(xiàn)效果還不錯(cuò)！
但是我們最開始生成的是四類數(shù)據(jù)，同樣的我們以四類來進(jìn)行聚類試試？
并且我們順便打印一下聚類效果

from sklearn.cluster import KMeans
n_clusters = 4#首先測試的超參數(shù)
cluster = KMeans(n_clusters=n_clusters, random_state=0).fit(X)
y_pred = cluster.labels_
centroid = cluster.cluster_centers_
color = ["red","pink","orange","gray"]
fig, ax1 = plt.subplots(1)
for i in range(n_clusters):
    ax1.scatter(X[y_pred==i, 0], X[y_pred==i, 1]
                ,marker='o'
                ,s=8
                ,c=color[i]
                )#循環(huán)畫小樣本預(yù)測點(diǎn)的位置
    ax1.scatter(centroid[:,0],centroid[:,1]
                ,marker="x"
                ,s=18
                ,c="white")#循環(huán)畫質(zhì)心的位置
plt.show()

和我們的原始數(shù)據(jù)比較一下：

效果不錯(cuò)！
但是這樣問題就來了
我們?nèi)绾稳ズ饬恳粋€(gè)K值得選取是否合適呢？

四. 聚類效果測評(píng)

被分在同一個(gè)簇中的數(shù)據(jù)是有相似性的，而不同簇中的數(shù)據(jù)是不同的，當(dāng)聚類完畢之后，我們就要分別去研究每個(gè)簇中的樣本都有什么樣的性質(zhì)。
根據(jù)聚類效果，我們追求“簇內(nèi)差異小，簇外差異大”。而這個(gè)“差異“，由樣本點(diǎn)到其所在簇的質(zhì)心的距離來衡量。
對于一個(gè)簇來說，所有樣本點(diǎn)到質(zhì)心的距離之和越小，我們就認(rèn)為這個(gè)簇中的樣本越相似，簇內(nèi)差異就越小。而距離的衡量方法有多種，令$x$表示簇中的一個(gè)樣本點(diǎn)，$\mu$表示該簇中的質(zhì)心，$n$表示每個(gè)樣本點(diǎn)中的特征數(shù)目，$i$表示組成點(diǎn)$x$的每個(gè)特征，則該樣本點(diǎn)到質(zhì)心的距離可以由以下距離來度量:

歐幾里得距離

$d(x,\mu )=\sqrt{{\sum }_{i=1}^n(x_i?{\mu }_i{)}^2}$

采用歐幾里得距離，則一個(gè)簇中所有樣本到質(zhì)心的距離平方和為：

$CSS={\sum }_{j=0}^m{\sum }_{i=0}^n(x_i?{\mu }_i{)}^2$

$TotalCSS={\sum }_{l=1}^{k}CS{S}_l$

其中，$m$為一個(gè)簇中樣本的個(gè)數(shù)，$j$是每個(gè)樣本的編號(hào)。這個(gè)公式被稱為簇內(nèi)平方和(cluster Sum of Square),又叫做$inertia$。而將一個(gè)數(shù)據(jù)集中的所有簇的簇內(nèi)平方和相加，就得到了整體平方和(Total Cluster Sum of Square)，又叫做$Totalinertia$。$TotalInertia$越小，代表著每個(gè)簇內(nèi)樣本越相似，聚類的效果就越好。因此K-Means追求的是，求解能夠讓$Inertia$最小化的質(zhì)心。實(shí)際上，在質(zhì)心不斷變化不斷迭代的過程中，總體平方和是越來越小的。我們可以使用數(shù)學(xué)來證明，當(dāng)整體平方和最小的時(shí)候，質(zhì)心就不再發(fā)生變化了。如此，K-Means的求解過程，就變成了一個(gè)最優(yōu)化問題。

代碼實(shí)現(xiàn)

inertia = cluster.inertia_

對，就這么簡單
然后我們探究一下剛剛數(shù)據(jù)中k大小與這個(gè)$TotalInertia$的關(guān)系

x_i,y_i=[],[]
for i in range(1,11):
    n_clusters = int(i)#首先測試的超參數(shù)\
    cluster = KMeans(n_clusters=n_clusters, random_state=0).fit(X)
    inertia = cluster.inertia_
    x_i.append(i)
    y_i.append(inertia)
plt.plot(y_i)

由圖可知當(dāng)k取值3到4左右的時(shí)候$TotalInertia$是比較小的。

并且我們可以發(fā)現(xiàn)k值越大，$TotalInertia$的值越小，也就是模型越好

而這樣說明，$TotalInertia$最為評(píng)價(jià)K值選取的參數(shù)使用是不好的，不可能將樣本分成任意多的簇

所以使用Inertia用來評(píng)估聚類的效果可以，但沒必要因?yàn)檫@個(gè)指標(biāo)的缺點(diǎn)太大。

并且使用Inertia作為評(píng)估指標(biāo)，會(huì)讓聚類算法在一些細(xì)長簇，環(huán)形簇，或者不規(guī)則形狀的流形時(shí)表現(xiàn)不佳：

所以研究者們往往會(huì)采用其他參數(shù)來對聚類效果進(jìn)行衡量

五. 算法評(píng)估PLUS

一般我們使用聚類算法進(jìn)行評(píng)估時(shí)往往有兩種數(shù)據(jù)情況

1.當(dāng)標(biāo)簽已知的時(shí)候

2.當(dāng)標(biāo)簽未知的時(shí)候

1.當(dāng)標(biāo)簽已知的時(shí)候（不做討論）

2.當(dāng)標(biāo)簽未知的時(shí)候

當(dāng)標(biāo)簽未知的時(shí)候我們往往會(huì)采用輪廓系數(shù)進(jìn)行衡量。

在99%的情況下，我們是對沒有真實(shí)標(biāo)簽的數(shù)據(jù)進(jìn)行探索，也就是對不知道真正答案的數(shù)據(jù)進(jìn)行聚類。這樣的聚類，是完全依賴于評(píng)價(jià)**簇內(nèi)的稠密程度（簇內(nèi)差異?。┖痛亻g的離散程度（簇外差異大）**來評(píng)估聚類的效果。

其中輪廓系數(shù)是最常用的聚類算法的評(píng)價(jià)指標(biāo)

它是對每個(gè)樣本來定義的：

1）樣本與其自身所在的簇中的其他樣本的相似度a，等于樣本與同一簇中所有其他點(diǎn)之間的平均距離

2）樣本與其他簇中的樣本的相似度b，等于樣本與下一個(gè)最近的簇中的所有點(diǎn)之間的平均距離

根據(jù)聚類的要求”簇內(nèi)差異小，簇外差異大“，我們希望b永遠(yuǎn)大于a，并且大得越多越好。
輪廓系數(shù)計(jì)算方法如下：

$s=\frac{b?a}{max(a,b)}$

由公式可知輪廓系數(shù)范圍是(-1,1)。

其中值越接近1表示樣本與自己所在的簇中的樣本很相似，并且與其他簇中的樣本不相似。

當(dāng)樣本點(diǎn)與簇外的樣本更相似的時(shí)候，輪廓系數(shù)就為負(fù)。

當(dāng)輪廓系數(shù)為0時(shí)，則代表兩個(gè)簇中的樣本相似度一致，兩個(gè)簇本應(yīng)該是一個(gè)簇。

可以總結(jié)為輪廓系數(shù)越接近于1越好，負(fù)數(shù)則表示聚類效果非常差。越接近1越好；越接近-1越不好。

如果一個(gè)簇中的大多數(shù)樣本具有比較高的輪廓系數(shù)，則簇會(huì)有較高的總輪廓系數(shù)，則整個(gè)數(shù)據(jù)集的平均輪廓系數(shù)越高，則聚類是合適的。如果許多樣本點(diǎn)具有低輪廓系數(shù)甚至負(fù)值，則聚類是不合適的，聚類的超參數(shù)K可能設(shè)定得太大或者太小。

代碼如下：

from sklearn.metrics import silhouette_score
x_i,y_i=[],[]
for n_clusters in range(2,11):
    clusterer = KMeans(n_clusters=n_clusters, random_state=10)
    cluster_labels = clusterer.fit_predict(X)
    silhouette_avg = silhouette_score(X, cluster_labels)
    x_i.append(n_clusters)
    y_i.append(silhouette_avg)
    print("For n_clusters =", n_clusters,
          "The average silhouette_score is :", silhouette_avg)
plt.plot(x_i, y_i)

結(jié)果如圖：

可見我們在k=4左右效果最好，我們數(shù)據(jù)集生成也是4個(gè)類別?？梢娛褂幂喞禂?shù)作為k值選取的參考非常合理。

輪廓系數(shù)有很多優(yōu)點(diǎn)，它在有限空間中取值，使得我們對模型的聚類效果有一個(gè)“參考”。

并且，輪廓系數(shù)對數(shù)據(jù)的分布沒有假設(shè)，因此在很多數(shù)據(jù)集上都表現(xiàn)良好。但它在每個(gè)簇的分割比較清洗時(shí)表現(xiàn)最好。但輪廓系數(shù)也有缺陷，它在凸型的類上表現(xiàn)會(huì)虛高，比如基于密度進(jìn)行的聚類，或通過DBSCAN獲得的聚類結(jié)果，如果使用輪廓系數(shù)來衡量，則會(huì)表現(xiàn)出比真實(shí)聚類效果更高的分?jǐn)?shù)。

除了輪廓系數(shù)是最常用的，我們還有卡林斯基-哈拉巴斯指數(shù)（Calinski-Harabaz Index，簡稱CHI，也被稱為方差比標(biāo)準(zhǔn)），戴維斯-布爾丁指數(shù)（Davies-Bouldin）以及權(quán)變矩陣（Contingency Matrix）可以使用。

六. Referance

[1]Ahmed M, Seraj R, Islam S M S. The k-means algorithm: A comprehensive survey and performance evaluation[J]. Electronics, 2020, 9(8): 1295.
[2]Hartigan J A, Wong M A. Algorithm AS 136: A k-means clustering algorithm[J]. Journal of the royal statistical society. series c (applied statistics), 1979, 28(1): 100-108.
[3]Likas A, Vlassis N, Verbeek J J. The global k-means clustering algorithm[J]. Pattern recognition, 2003, 36(2): 451-461.
[4]Krishna K, Murty M N. Genetic K-means algorithm[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 1999, 29(3): 433-439.文章來源地址http://www.zghlxwxcb.cn/news/detail-574629.html

到了這里，關(guān)于k-means聚類算法詳解的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！