本文來講講K平均聚類算法(K-Means Clustering),K Means算法是所有聚類算法中最經(jīng)典的一種，因?yàn)樗粩嘣谥庇X上容易理解，而且它的計(jì)算效率也是非常的高。

原理

在講K-Means算法前我們先看看，這個(gè)算法能做什么。下面有一組數(shù)據(jù)，我們想要把數(shù)據(jù)分成若干個(gè)類，在某一類當(dāng)中，這些數(shù)據(jù)的彼此之間的距離比較近。對(duì)于這個(gè)大問題，我們有兩個(gè)小問題。第一個(gè)是，我們?nèi)绾未_定分的類的個(gè)數(shù)；第二個(gè)問題是，如何在確定類的個(gè)數(shù)的情況下，如何確定每個(gè)類中包含的元素。那么K-Means算法就可以自動(dòng)幫助我們找到最佳的聚類的方式。如圖所示，K-Means算法講這些數(shù)據(jù)分成了紅藍(lán)綠三組。

image

那么我們就來看看K-Means算法的工作流程。

1. 選擇我們想要的類的個(gè)數(shù)K；
2. 在平面上隨機(jī)選擇K個(gè)點(diǎn)，作為初始化類的中心點(diǎn)，不一定在原先數(shù)據(jù)當(dāng)中；
3. 對(duì)于數(shù)據(jù)集中的每個(gè)點(diǎn)，要判斷它屬于我們之前K個(gè)中心點(diǎn)的哪一類。依據(jù)數(shù)據(jù)中的每個(gè)點(diǎn)對(duì)這K個(gè)點(diǎn)的距離的大小，找到最短的距離，那么就是每個(gè)數(shù)據(jù)點(diǎn)對(duì)應(yīng)的類別，這一步可以稱作是分配；
4. 重新計(jì)算一些新的中心點(diǎn)，就是應(yīng)用之前分配的結(jié)果重新計(jì)算分配好的每個(gè)類當(dāng)中的中心點(diǎn)；
5. 重新分配，如果重新分配的結(jié)果和之前分配的結(jié)果相同，則說明找到最佳的K-Means算法的結(jié)果，如果不同，那繼續(xù)去第四步進(jìn)行分配計(jì)算，直到找到最佳算法結(jié)果

image

下面從具體的例子來講述這個(gè)步驟。假設(shè)有一組數(shù)據(jù)，我們要分配成兩類，即K=2；然后隨機(jī)選擇兩個(gè)點(diǎn)，分別計(jì)算每個(gè)點(diǎn)距離這兩個(gè)點(diǎn)的距離。這里可以有個(gè)比較簡(jiǎn)單的計(jì)算方式，我們作出這兩個(gè)點(diǎn)的垂直平分線，那么這個(gè)綠線上方的點(diǎn)都是離藍(lán)色點(diǎn)比較近，下面的離紅色比較近。

image

那么我們就把上面的點(diǎn)分作藍(lán)組，下面的分為紅組。目前的步驟相當(dāng)于已經(jīng)進(jìn)行到第三步。接下來第四步，更新每組數(shù)據(jù)的中心點(diǎn)，那么我們就找到了新的中心點(diǎn)可以進(jìn)行第五步，依據(jù)新的中心點(diǎn)，重新進(jìn)行分配。

image

image

不斷重復(fù)45步驟，直到分配的結(jié)果和前一步分配的結(jié)果是一致的。

image

K-Means算法可以以一種算法的方式告訴我們最佳的聚類的方式，這里就得到了左下方紅組，右上方藍(lán)組的這樣一個(gè)結(jié)論。

隨機(jī)初始化陷阱

現(xiàn)在看看初始點(diǎn)的選擇對(duì)最終K-Meas聚類結(jié)果的影響。下面有一個(gè)例子，我們需要用K-Means算法對(duì)這組數(shù)據(jù)進(jìn)行聚類，選擇K=3。這里很明顯有三類，我們這里就直接選擇最佳的中心點(diǎn)并標(biāo)記出這三類數(shù)據(jù)。

image

那么這里是我們?nèi)庋劭闯鰜淼娜齻€(gè)中心點(diǎn)，但如果我們選擇的不是這最佳的中心點(diǎn)，則需要重復(fù)上述的45步，比如選的是下面這三個(gè)中心點(diǎn)。

image

那么這時(shí)就需要對(duì)中心點(diǎn)進(jìn)行位移，但由于這個(gè)位移是非常小的，所以新的分類結(jié)果和之前并不會(huì)有什么改變，所以算法就這樣結(jié)束了。

image

這樣得到的分類結(jié)果和之前那個(gè)顯然是不同的。但這樣就發(fā)生了同一組數(shù)據(jù)，卻產(chǎn)生了兩個(gè)不同的分類結(jié)果。區(qū)別就在于選擇了不同的初始中心點(diǎn)。我們不好直接說哪一個(gè)分類算法更好，需要有一個(gè)方法來判斷如何選擇初始中心點(diǎn)。也就是說初始中心點(diǎn)不能隨機(jī)進(jìn)行選擇了?，F(xiàn)在有一個(gè)K-Means算法的更新版本，叫做K-Means++，它完美的解決了初始化中心點(diǎn)的陷阱，數(shù)學(xué)上來講叫做局部最小值的一個(gè)陷阱。無論在R還是Python中，這個(gè)K-Means++都已經(jīng)加入了算法當(dāng)中，因此不用擔(dān)心之后的代碼實(shí)現(xiàn)會(huì)不會(huì)掉入這個(gè)陷阱。

選擇類的個(gè)數(shù)

上文講到的是選擇中心點(diǎn)的陷阱，那么現(xiàn)在在談?wù)勅绾芜x擇類的個(gè)數(shù)。從直觀上，上文中的圖像大部分人應(yīng)該很容易想到分為3組，也有的人可能想分為2組，但怎樣選擇才是最佳的分組方式是個(gè)需要好好研究的問題。首先來定義一個(gè)數(shù)學(xué)的量，組內(nèi)平方和(WCSS)。

WCSS

來看這個(gè)表達(dá)式，一共有3項(xiàng)，每一項(xiàng)代表對(duì)于每一組的平方和。比如第一項(xiàng)，就是對(duì)所有數(shù)據(jù)點(diǎn)對(duì)這一組中心點(diǎn)距離的平方。很顯然，如果每一組的數(shù)據(jù)蜷縮的越緊，那么這個(gè)平方和就越小。

那么如果將這組數(shù)據(jù)分為1組，那么這個(gè)組內(nèi)平方和只有一項(xiàng)，那么這個(gè)結(jié)果很顯然會(huì)很大。如果分為2組，那么結(jié)果比1組的肯定要小，當(dāng)分為3組時(shí)，得到的結(jié)果會(huì)更小。也就是說，隨著分組的個(gè)數(shù)增加，這個(gè)組內(nèi)平方和會(huì)逐漸變小。那么現(xiàn)在的問題來了，如何選擇最合適的分組的個(gè)數(shù)？

這里要介紹一個(gè)法則，叫做手肘法則(The Elbow Method)。我們把隨著分組個(gè)數(shù)的增加，WCSS的結(jié)果的圖像畫出來。

手肘法則

找到最像手肘的這個(gè)點(diǎn)，這里就是3，那么這個(gè)點(diǎn)，就是最佳的分組的個(gè)數(shù)。這個(gè)曲線上可以看到，從1到2，和2到3時(shí)，下降的速率都是比較快的，但從3往后，下降的速率都是非常小的，那么我們要找的就是這樣一個(gè)點(diǎn)，在到達(dá)這個(gè)點(diǎn)之前和從這個(gè)點(diǎn)開始的下降，速率的變化時(shí)最大的。

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

我們這次要用到的數(shù)據(jù)集部分如下，反映的是一個(gè)購(gòu)物商場(chǎng)的購(gòu)物信息。最后一列Spending Score是購(gòu)物商場(chǎng)根據(jù)客戶的信息打出的客戶的評(píng)分，分?jǐn)?shù)越低意味著客戶花的錢越少，越高以為著客戶花的越多。商場(chǎng)希望通過對(duì)客戶的年收入和購(gòu)物指數(shù)來進(jìn)行分群。

那么這個(gè)問題的自變量就是第三四列，年收入和購(gòu)物指數(shù)。但它是個(gè)無監(jiān)督學(xué)習(xí)，因此沒有因變量。這里我們要用到的工具是sklearn.cluster中的KMeans類。

首先要計(jì)算各個(gè)分組的WCSS。這里我們計(jì)算組數(shù)從1到10的情況。

wcss = []
for i in range(1, 11):
    kmeans = KMeans(n_clusters=i, max_iter=300, n_init=10, init='k-means++', random_state=0)
    kmeans.fit(X)
    wcss.append(kmeans.inertia_)
plt.plot(range(1, 11), wcss)
plt.title('The Elbow Method')
plt.xlabel('Number of Clusters')
plt.ylabel('WCSS')
plt.show()

這里的KMeans中的參數(shù)也解釋下，n_clusters指的是分組數(shù)，max_iter指的是每一次計(jì)算時(shí)最大的循環(huán)個(gè)數(shù)，這里使用默認(rèn)值300，n_init代表每一個(gè)做K平均算法時(shí)，會(huì)對(duì)多少組不同的中心值進(jìn)行計(jì)算。init這個(gè)參數(shù)非常重要，指的是我們?nèi)绾芜x擇初始值，最簡(jiǎn)單的是random，即隨機(jī)，但為了避免掉入隨機(jī)初始值陷阱，這里使用k-means++。

擬合好后得到組間距離就是kmeans.inertia_。這樣我們就可以畫出對(duì)于不同的分組數(shù)，wcss的圖像。

image

那么通過手肘法則，可以得到最佳的分組個(gè)數(shù)是5組，則可以開始擬合數(shù)據(jù)。

# Applying the k-means to the mall dataset
kmeans = KMeans(n_clusters=5, max_iter=300, n_init=10, init='k-means++', random_state=0)
y_kmeans = kmeans.fit_predict(X)

擬合好數(shù)據(jù)后，得到的y_means實(shí)際上就是0-4五個(gè)分組。我們來將分組后的圖像畫出來看看。

# Visualizing the clusters
plt.scatter(X[y_kmeans == 0, 0], X[y_kmeans == 0, 1], s=100, c='red', label='Careful')
plt.scatter(X[y_kmeans == 1, 0], X[y_kmeans == 1, 1], s=100, c='blue', label='Standard')
plt.scatter(X[y_kmeans == 2, 0], X[y_kmeans == 2, 1], s=100, c='green', label='Target')
plt.scatter(X[y_kmeans == 3, 0], X[y_kmeans == 3, 1], s=100, c='cyan', label='Careless')
plt.scatter(X[y_kmeans == 4, 0], X[y_kmeans == 4, 1], s=100, c='magenta', label='Sensible')
plt.scatter(kmeans.cluster_centers_[:, 0], kmeans.cluster_centers_[:, 1], s=300, c='yellow', label='Centroids')
plt.title('Clusters of clients')
plt.xlabel('Annual Income (k$)')
plt.ylabel('Spending Score (1-100)')
plt.legend()
plt.show()

得到的圖像如下，我們就可以根據(jù)圖像來進(jìn)行分析，給予不同的標(biāo)簽。

分類結(jié)果

以上，就是K-Means聚類算法的相關(guān)基礎(chǔ)知識(shí)點(diǎn)。