動手寫機器學習演算法：K-Means聚類演算法

K-Means演算法是無監督的聚類演算法，它實現起來比較簡單，聚類效果也不錯，因此應用很廣泛。今天小七和你一起用Python實現機K-Means聚類演算法。

全部代碼

https://github.com/lawlite19/MachineLearning_Python/blob/master/K-Means/K-Menas.py

聚類過程

聚類屬於無監督學習，不知道y的標記分為K類

K-Means演算法分為兩個步驟

第一步：簇分配，隨機選K個點作為中心，計算到這K個點的距離，分為K個簇

第二步：移動聚類中心：重新計算每個簇的中心，移動中心，重複以上步驟。

如下圖所示：

隨機分配的聚類中心

重新計算聚類中心，移動一次

最後10步之後的聚類中心

計算每條數據到哪個中心最近實現代碼：

# 找到每條數據距離哪個類中心最近

def findClosestCentroids(X,initial_centroids):

m = X.shape[0] # 數據條數

K = initial_centroids.shape[0] # 類的總數

dis = np.zeros((m,K)) # 存儲計算每個點分別到K個類的距離

idx = np.zeros((m,1)) # 要返回的每條數據屬於哪個類

計算每個點到每個類中心的距離

for i in range(m):

for j in range(K):

dis[i,j] = np.dot((X[i,:]-initial_centroids[j,:]).reshape(1,-1),(X[i,:]-initial_centroids[j,:]).reshape(-1,1))

返回dis每一行的最小值對應的列號，即為對應的類別

- np.min(dis, axis=1)返回每一行的最小值

- np.where(dis == np.min(dis, axis=1).reshape(-1,1)) 返回對應最小值的坐標

- 注意：可能最小值對應的坐標有多個，where都會找出來，所以返回時返回前m個需要的即可（因為對於多個最小值，屬於哪個類別都可以）

dummy,idx = np.where(dis == np.min(dis, axis=1).reshape(-1,1))

return idx[0:dis.shape[0]] # 注意截取一下

計算類中心實現代碼：

# 計算類中心

def computerCentroids(X,idx,K):

n = X.shape[1]

centroids = np.zeros((K,n))

for i in range(K):

centroids[i,:] = np.mean(X[np.ravel(idx==i),:], axis=0).reshape(1,-1) # 索引要是一維的,axis=0為每一列，idx==i一次找出屬於哪一類的，然後計算均值

return centroids

目標函數

也叫做失真代價函數

最後我們想得到：

其中

表示第i條數據距離哪個類中心最近，其中

即為聚類的中心

聚類中心的選擇

隨機初始化，從給定的數據中隨機抽取K個作為聚類中心

隨機一次的結果可能不好，可以隨機多次，最後取使代價函數最小的作為中心

實現代碼：(這裡隨機一次)

# 初始化類中心--隨機取K個點作為聚類中心

def kMeansInitCentroids(X,K):

m = X.shape[0]

m_arr = np.arange(0,m) # 生成0-m-1

centroids = np.zeros((K,X.shape[1]))

np.random.shuffle(m_arr) # 打亂m_arr順序

rand_indices = m_arr[:K] # 取前K個

centroids = X[rand_indices,:]

return centroids

聚類個數K的選擇

聚類是不知道y的label的，所以不知道真正的聚類個數

肘部法則（Elbow method）

作代價函數J和K的圖，若是出現一個拐點，如下圖所示，K就取拐點處的值，下圖此時K=3

若是很平滑就不明確，人為選擇。

第二種就是人為觀察選擇

應用——圖片壓縮

將圖片的像素分為若干類，然後用這個類代替原來的像素值

執行聚類的演算法代碼：

# 聚類演算法

def runKMeans(X,initial_centroids,max_iters,plot_process):

m,n = X.shape # 數據條數和維度

K = initial_centroids.shape[0] # 類數

centroids = initial_centroids # 記錄當前類中心

previous_centroids = centroids # 記錄上一次類中心

idx = np.zeros((m,1)) # 每條數據屬於哪個類

for i in range(max_iters): # 迭代次數

print u迭代計算次數：%d%(i+1)

idx = findClosestCentroids(X, centroids)

if plot_process: # 如果繪製圖像

plt = plotProcessKMeans(X,centroids,previous_centroids) # 畫聚類中心的移動過程

previous_centroids = centroids # 重置

centroids = computerCentroids(X, idx, K) # 重新計算類中心

if plot_process: # 顯示最終的繪製結果

plt.show()

return centroids,idx # 返回聚類中心和數據屬於哪個類

使用scikit-learn庫中的線性模型實現聚類

https://github.com/lawlite19/MachineLearning_Python/blob/master/K-Means/K-Means_scikit-learn.py

導入包

from sklearn.cluster import KMeans

使用模型擬合數據

model = KMeans(n_clusters=3).fit(X) # n_clusters指定3類，擬合數據

聚類中心

centroids = model.cluster_centers_ # 聚類中心

運行結果

二維數據類中心的移動

圖片壓縮