所謂聚類,就是按照某個特定的標準將一個數據集劃分成不同的多個類或者簇,使得同一個簇內的數據對象的相似性儘可能大,同時不再一個簇內的數據對象的差異性也儘可能大,聚類算法屬於無監督學習算法的一種.
引言
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所示.
K值選擇
通過上述描述,我們基本理解了k-means算法工作的原理,但是遺留給我們的問題是這個k值要如何確定呢?由於這個值是算法的輸入,需要用戶自行指定,當然不可以隨便拍腦袋想了.這裡介紹一種常用的WCSS方法來進行k值的選擇.
WCSS算法是Within-Cluster-Sum-of-Squares的簡稱,中文翻譯為最小簇內節點平方偏差之和.我們希望聚類後的效果是對每個樣本距離其簇內中心點的距離最小.
使用WCSS選擇k值的步驟如下:
step1 選擇不同的k值(比如1-14),對數據樣本執行k-means算法
step2 對於每個k值,計算相應的WCSS值
step3 畫出WCSS值隨著k值變化的曲線
step4一般來說WCSS值應該隨著K的增加而減小，然後趨於平緩，選擇當WCSS開始趨於平衡時的K的取值.上圖中可以選擇6-10之間的值作為k值.
03
代碼實現
樣例數據生成
我們使用python生成我們的數據代碼如下:
from clustering__utils import *x1, y1, x2, y2 = synthData()X1 = np.array([x1, y1]).TX2 = np.array([x2, y2]).T結果如下:
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): 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): 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): 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個樣本所屬中心點以及中心點的位置.
K值確定
我們使用以下代碼,計算不同k值下的WCSS的值Cs = 12V1 = 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,示例如上圖紅色圓圈所示.
最終效果:
我們根據上述選定的k值,可視化兩組數據迭代過程,代碼如下:iters = 20; seed = 6K1 = 3kmeans1 = kMeans(K1, iters, seed)fnc1, C1 = kmeans1.pred(X1)K2 = 6kmeans2 = kMeans(K2, iters, seed)fnc2, C2 = kmeans2.pred(X2)04
總結
本文介紹了機器學習領域中k-means進行聚類的原理以及相應的代碼實現,並給出了完整的代碼示例.
您學廢了嗎?註：完整代碼，關注公眾號，後臺回復 kMeans , 即可獲取。