Python機器學習之k-means聚類算法

1 引言

所謂聚類,就是按照某個特定的标準将一個資料集劃分成不同的多個類或者簇,使得同一個簇内的資料對象的相似性盡可能大,同時不再一個簇内的資料對象的差異性也盡可能大,聚類算法屬于無監督學習算法的一種.

k-均值聚類的目的是：把 n個點（可以是樣本的一次觀察或一個執行個體)劃分到k個聚類中，使得每個點都屬于離他最近的均值（此即聚類中心）對應的聚類，以之作為聚類的标準。

2 K-Means

k-均值聚類算法屬于最基礎的聚類算法,該算法是一種疊代的算法,将規模為n的資料集基于資料間的相似性以及距離簇内中心點的距離劃分成k簇.這裡的k通常是由使用者自己指定的簇的個數,也就是我們聚類的類别個數.

該算法的一般步驟如下:

• step1 選擇k,來指定我們需要聚類的類别數目.參考上圖a,這裡k=2.
• step2 從資料集中随機選擇k個樣本作為我們不同類别的類内的中心點.參考圖b中紅色和藍色x字
• step3 對資料集中的每一個樣本,計算該樣本到k個中心點的距離,選擇距離該樣本最近的中心點的類别作為該樣本的類别.參考上圖c.
• step4 根據上一步重新指定的樣本的類别,計算每個類别的類内中心點.圖d所示,重新計算的類内中心點為紅色和藍色x字.
• step5 重複步驟3,為資料集中的每個樣本重新配置設定距離其最近的中心點的類别.圖e所示.
• step6 如果給每個樣本配置設定的類别發生改變,則進入step4,否則進入step7
• step7 算法結束.圖f所示.

3 K值确定

通過上述描述,我們基本了解了k-means算法工作的原理,但是遺留給我們的問題是這個k值要如何确定呢?由于這個值是算法的輸入,需要使用者自行指定,當然不可以随便拍腦袋想了.這裡介紹一種常用的WCSS方法來進行k值的選擇.

WCSS算法是Within-Cluster-Sum-of-Squares的簡稱,中文翻譯為最小簇内節點平方偏差之和.白話就是我們每選擇一個k,進行k-means後就可以計算每個樣本到簇内中心點的距離偏差之和, 我們希望聚類後的效果是對每個樣本距離其簇内中心點的距離最小,基于此我們選擇k值的步驟如下:

• step1 選擇不同的k值(比如1-14),對資料樣本執行k-means算法
• step2 對于每個k值,計算相應的WCSS值
• step3 畫出WCSS值随着k值變化的曲線
• step4 一般來說WCSS值應該随着K的增加而減小，然後趨于平緩，選擇當WCSS開始趨于平衡時的K的取值.上圖中可以選擇6-10之間的值作為k值.

4 代碼實作

4.1 樣例資料分布

我們使用python生成我們的資料代碼如下:

from clustering__utils import *
x1, y1, x2, y2 = synthData()
X1 = np.array([x1, y1]).T
X2 = np.array([x2, y2]).T
           

結果如下:

4.2 實作K-means

參考上述原理,我們來實作kMeans,我們将其封裝成類,代碼如下:

class kMeans(Distance):
    def __init__(self, K=2, iters=16, seed=1):
        super(kMeans, self).__init__()
        self._K = K
        self._iters = iters
        self._seed = seed
        self._C = None
    
    def _FNC(self, x, c, n):
        # for each point,
        # find the nearest center
        cmp = np.ndarray(n, dtype=int)
        for i, p in enumerate(x):
            d = self.distance(p, self._C)
            cmp[i] = np.argmin(d)
        return cmp
    
    def pred(self, X):
        # prediction
        n, dim = X.shape
        np.random.seed(self._seed)
        sel = np.random.randint(0, n, self._K)
        self._C = X[sel]
        cmp = self._FNC(X, self._C, n)
        for _ in range(self._iters):
            # adjust position of centroids
            # to the mean value
            for i in range(sel.size):
                P = X[cmp == i]
                self._C[i] = np.mean(P, axis=0)
            cmp = self._FNC(X, self._C, n)
        return cmp, self._C
           

上述代碼中:

• FNC函數中x為輸入樣本,c為聚類中心點,n為樣本數目,該函數為每個樣本計算其最近的中心點
• pred函數首先重新計算樣本中心點,然後基于此給樣本資料重新配置設定所屬類别.傳回值為n個樣本所屬中心點以及中心點的位置.

4.3 确定k

我們使用以下代碼,計算不同k值下的WCSS的值

# elbow method
Cs = 12
V1 = np.zeros(Cs)
V2 = np.zeros(Cs)
D = Distance()
for k in range(Cs):
    kmeans = kMeans(K=k + 1, seed=6)
    fnc1, C1 = kmeans.pred(X1)
    fnc2, C2 = kmeans.pred(X2)
    for i, [c1, c2] in enumerate(zip(C1, C2)):
        d1 = D.distance(c1, X1[fnc1 == i])**2
        d2 = D.distance(c2, X2[fnc2 == i])**2
        V1[k] += np.sum(d1)
        V2[k] += np.sum(d2)
           

結果如下:

這裡我們對第一組資料,選擇k=3,針對第二組資料選擇k=6,示例如上圖紅色圓圈所示.

4.4 最終效果

我們根據上述標明的k值,可視化兩組資料疊代過程,代碼如下:

iters = 20; seed = 6
K1 = 3
kmeans1 = kMeans(K1, iters, seed)
fnc1, C1 = kmeans1.pred(X1)
K2 = 6
kmeans2 = kMeans(K2, iters, seed)
fnc2, C2 = kmeans2.pred(X2)
           

運作結果如下:

5 總結

本文介紹了機器學習領域中k-means進行聚類的原理以及相應的代碼實作,并給出了完整的代碼示例.

您學廢了嗎?

6 參考

參考

連結一

連結二

關注公衆号《AI算法之道》，擷取更多AI算法資訊。

注： 完整代碼，關注公衆号，背景回複 kMeans , 即可擷取。