瞎聊機器學習——K-均值聚類（K-means）算法

本文中我們将會聊到一種常用的無監督學習算法——K-means。

1、K-means算法的原理

K-means算法是一種疊代型的聚類算法，在算法中我們首先要随機确定K個初始點作為質心，然後去計算其他樣本距離每一個質心的距離，将該樣本歸類為距離最近的一個質心所屬類别中（一個簇中）。

舉個例子來表述一下：

如圖所示，我們進行反向思考，我設定四個固定的随機點的位置（紅色點），在每一個點的附近都随機生成50個藍色點，對所有的藍色點進行聚類分析，如果設定簇的數量為4個（K=4）,是不是最後的結果越靠近這四個紅色的點越好呢？當然在尋找最優解的過程中圖中的每一個藍色的點都可以當做要選取的質心，我們進行的是一個疊代求解的過程，下面說一下K-means算法的步驟：

（1）随機選取資料中的K個對象作為聚類中心，每個對象都代表一個類（K個類的确定）；

（2）計算每一個樣本到每一個聚類中心的距離（歐氏距離），将該樣本分到距離最近的那個類的簇中；

（3）周遊每一個簇，算出每個簇的中心，将該中心作為新的聚類中心；

（4）重複進行（2）（3），直到聚類中心不再發生變化為止。

2、K-means算法的優缺點

優點：對于聚類算法來說K-means算法原理簡單；計算複雜度是O(NKt)，N為資料對象的數目，K是聚類中心的數目，t是疊代的次數；對于大資料集的處理，K-means算法具有可伸縮性和高效性。

缺點：需要預先設定K值，K值得設定和真實的資料樣本未必是吻合的；求解的結果是局部最優而非全局最優（當資料簇的分布差異較大時表現的不好）；容易受到噪聲點的影響；樣本最後隻能被分到單一的類别中。

3、K-means算法中K值的選擇

K值得選擇是K-means算法中最大的問題之一，也是該算法的主要缺點所在，然而K值的選擇一般都要基于經驗和多次試驗的結果，我們可以将不同K值下的平均距離進行繪圖：

根據圖檔我們可以看出當K=(1~4)時，K值下的平均距離急速下降，當K>4時，曲線趨于平穩，此時我們可以認為K=4就是最佳的K值。

4、K-means算法的代碼實作

import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans

# 先在四個中心點附近産生一堆資料
real_center = [(1, 1), (1, 2), (2, 2), (2, 1)]
point_number = 50

points_x = []
points_y = []
k_x = []
k_y = []
for center in real_center:
    offset_x, offset_y = np.random.randn(point_number) * 0.3, np.random.randn(point_number) * 0.25
    x_val, y_val = center[0] + offset_x, center[1] + offset_y
    k_x.append(center[0])
    k_y.append(center[1])
    points_x.append(x_val)
    points_y.append(y_val)

points_x = np.concatenate(points_x)  # 将二維數組拼接成一個list
points_y = np.concatenate(points_y)


# plt.scatter(k_x,k_y,c='r')
# plt.scatter(points_x, points_y, c='b')
# plt.show()

def k_means(K, p_list, center):
    points_set = {key: [] for key in range(K)}
    for p in p_list:
        # np.argmin傳回（距離）最小值的下标，參數axis=1
        nearest_index = np.argmin(np.sum((centeroid - p) ** 2, axis=1) ** 0.5)
        points_set[nearest_index].append(p)
    # point_set = {0:[([x1,y1]),([x2,y2]),......],1:[],......}
    for k_index, p_set in points_set.items():
        p_xs = [p[0] for p in p_set]
        p_ys = [p[1] for p in p_set]
        center[k_index, 0] = sum(p_xs) / len(p_set)
        center[k_index, 1] = sum(p_ys) / len(p_set)
    return center, points_set


K = 4
# 用np.stack将points_x和points_y拼接，變成（x,y）的坐标形式   p_list.shape(200,2)
p_list = np.stack([points_x, points_y], axis=1)
# 通過choice函數随機選出K個聚類中心
index = np.random.choice(len(p_list), size=K)
centeroid = p_list[index]
print(centeroid)
k_means(K, p_list, centeroid)

for i in range(10):
    center, point_set = k_means(K, p_list, centeroid)
print(center)             # 輸出聚類中心
print(point_set)          # 輸出聚類後的每個簇

# 利用Sklearn中的kmeans繪制出K值及其聚類簇中平均距離的折線圖，取得最佳K值
# loss = []
# for i in range(1, 10):
#     kmeans = KMeans(n_clusters=i, max_iter=100).fit(p_list)
#     loss.append(kmeans.inertia_ / point_number / K)
#
# plt.plot(range(1, 10), loss)
# plt.show()