K-Means原理分析與手動實現

K-Means將所給數據進行分類（聚類，clustering），演算法是無監督學習（unsupervised），步驟如下：

首先要給個分類的類別數目，最開始的分類中心。

一（1）：

計算其中一個點到所有分類中心的距離，將這個點與最近的中心劃分為一類

一（2）：

將所有的點重複一（1）

二：

每個分類中，所有點的平均值作為新的分類中心

三：

重複迭代一、二兩步

手動實現代碼如下：

# -*- coding: utf-8 -*-"""Created on Wed Dec 6 17:05:34 2017@author: Administrator"""import numpy as npimport matplotlib.pyplot as pltimport pandas as pdfrom sklearn.cluster import KMeansfrom sklearn.datasets import make_blobsif __name__ == "__main__": n_samples = 1500 random_state = 170 X, y = make_blobs(n_samples=n_samples, random_state=random_state)# center = [X[10], X[365], X[666]] center = [X[100], X[365], X[666]] distance = list(np.zeros(3)) temp_data = pd.DataFrame(X) times = 4 for j in range(times): temp_y = [] for i in range(len(X)): distance[0] = np.square(center[0][0]-X[i][0]) + np.square(center[0][1]-X[i][1]) distance[1] = np.square(center[1][0]-X[i][0]) + np.square(center[1][1]-X[i][1]) distance[2] = np.square(center[2][0]-X[i][0]) + np.square(center[2][1]-X[i][1]) max_loc = distance.index(min(distance)) temp_y.append(max_loc) temp_data[y] = temp_y #update center temp = temp_data[temp_data[y] == 0] center[0] = [temp[0].mean(), temp[1].mean()] temp = temp_data[temp_data[y] == 1] center[1] = [temp[0].mean(), temp[1].mean()] temp = temp_data[temp_data[y] == 2] center[2] = [temp[0].mean(), temp[1].mean()] #plot the data plt.figure(figsize=(12, 12)) plt.subplot(221) plt.scatter(X[:, 0], X[:, 1], c=temp_y) plt.title("clustering data") plt.subplot(222) plt.scatter(X[:, 0], X[:, 1], c=y) plt.title("original data")

結果如下：

代碼解釋：

X, y = make_blobs(n_samples=n_samples, random_state=random_state)

生成用於聚類實驗的數據，數據是高斯分布，樣本點是n_samples個。

times：樣本迭代次數

distance[0] = np.square(center[0][0]-X[i][0]) + np.square(center[0][1]-X[i][1]) distance[1] = np.square(center[1][0]-X[i][0]) + np.square(center[1][1]-X[i][1]) distance[2] = np.square(center[2][0]-X[i][0]) + np.square(center[2][1]-X[i][1])

計算樣本點到聚類中心的距離

#update center temp = temp_data[temp_data[y] == 0] center[0] = [temp[0].mean(), temp[1].mean()] temp = temp_data[temp_data[y] == 1] center[1] = [temp[0].mean(), temp[1].mean()] temp = temp_data[temp_data[y] == 2] center[2] = [temp[0].mean(), temp[1].mean()]

更新聚類中心

迭代一次的結果：

迭代四次的結果：

數學原理分析：

1.步驟一的目的是：使得聚類中所有點到聚類中心的距離只和最小

迭代的最終目的是使J()最小化：

2.為何每次都是設置平均值為新的聚類中心呢？

我們的最終目的是使得J()函數最小，但是每一步怎麼走？

我們的每一步更新類似使用梯度下降演算法，這樣使得最快取得J()最小。可以認為，其本身是使用梯度下降法解目的函數。

3.這樣是不是全局最優解？

不是！這樣的只是局部最優解，與初始值的設置有極大關係，所以K-Means++應運而生。

4.補充

（1）手動實現的代碼是迭代times次，在實際中可以以中心點變得幅度，或整體方差作為是否停止的限制條件

（2）在數據量較大時，在

#update center temp = temp_data[temp_data[y] == 0] center[0] = [temp[0].mean(), temp[1].mean()]

在部分，可以使用隨機梯度下降(SGD)或批量梯度下降（MBGD）最為修改中心點或停止的條件，在數據量較大時可以提升速度。

在劃分樣本間差異，或者作為分類的依據，我們使用的是歐式距離：計算點與點間的距離。在實際用也可使用其他劃分標準，如：相關係數等。