11.4 从零实现Kmeans聚类算法#
通过11.3节内容的介绍，我们已经知道了Kmeans聚类算法中两个关键未知变量的计算公式，接下来需要完成的就是对其进行编码实现。在11.2.3节中我们介绍过，聚类算法的步骤主要分为4个步骤，其中其中第4个步骤为循环迭代过程，因此整个聚类过程的关键在于前3步。接下来开始分别进行编码实现，完整示例代码可参见 AllBooKCode/Chapter11/C04_kmeans.py 文件。
11.4.1 随机初始化簇中心#
Kmeans聚类算法的K个初始簇中心由随机初始化得到，因此这里可以借助Python中的random.sample()方法实现，示例代码如下：
1 import random
2 def InitCentroids(X, K):
3 n = X.shape[0]
4 rands_index = np.array(random.sample(range(1, n), K))
5 centriod = X[rands_index, :]
6 return centriod在上述代码中，第3行用来得到数据集X中一共有多少个样本点。第4行用来在数值$[0,n)$中随机取K个不重复的值。第5行则是以第4行得到的K个值为下标，在数据集中取对应的K个样本点，即簇中心。
11.4.2 簇分配矩阵实现#
对于簇分配矩阵的实现，根据式(11-5)可知，只需先遍历每个样本点，然后计算其到每个簇中心的距离并选择最近簇中心即可，示例代码如下：
1 def findClostestCentroids(X, centroid):
2 n = X.shape[0]
3 idx = np.zeros(n, dtype=int)
4 for i in range(n):
5 subs = centroid - X[i, :]
6 dimension2 = np.power(subs, 2)
7 dimension_s = np.sum(dimension2, axis=1)
8 idx[i] = np.where(dimension_s == dimension_s.min())[0][0]
9 return idx在上述代码中，第3行用来初始化1个全0的n维向量，用于后续保存每个样本的簇索引。第4~8行用来分别遍历每个样本点，然后计算其到所有簇中心的距离，最后选择与之距离最近的簇中心。同时，需要注意的是，在实际的编码过程中其实并不需要通过一个形状为$n\times k$的分配矩阵来存储每个样本的分配信息，只需将每个簇进行编号，然后对每个样本点赋予一个对应的编号，因此，在上述代码中返回的idx就是每个样本点距离其最近簇的簇编号。例如idx=[0,1,2]表示这3个样本点分别属于第0个簇、第1个簇和第2个簇。
11.4.3 簇中心矩阵实现#
对于簇中心矩阵的计算，根据式(11-4)可知，只需先遍历K个簇，然后分别计算每个簇中所有样本点的平均中心即可，示例代码如下：
1 def computeCentroids(X, idx, K):
2 n, m = X.shape
3 centriod = np.zeros((K, m), dtype=float)
4 for k in range(K):
5 index = np.where(idx == k)[0] # 一个簇一个簇的分开计算
6 temp = X[index, :] # ? by m # 每次先取出一个簇中的所有样本
7 s = np.sum(temp, axis=0)# 计算一个簇中，每个特征维度的累加和
8 centriod[k, :] = s / index.shape[0]# 计算得到每个特征维度的均值
9 return centriod在上述代码中，第3行用来初始化一个全0的簇中心矩阵。第4~8行分别用来遍历每个簇，然后计算每个簇的簇中心并将其保存到簇中心矩阵中。