K-means算法

一、K-均值是最普及的聚类算法，它接受一个未标记的数据集，然后将数据聚类成不同的组。其方法为: 1、首先选择K个随机的点，称为聚类中心。 2、簇分配：对于数据集中的每一个数据，计算其距离K个中心点的距离，将其与距离最近的中心点关联起来，与同一个中心点关联的所有点聚成一类。 3、移动聚类中心：计算每一个组的平均值，移动该组所关联的中心点到平均值的位置。 4、重复步骤2、3直至中心点不再变化。 用${\mu }^1$,${\mu }^2$,…,${\mu }^k$表示聚类中心，用$c^{\left(1\right)}$,$c^{\left(2\right)}$,…,$c^{\left(m\right)}$存储与第i个实例最近的聚类中心的索引，K-均值算法的伪代码如下： K-均值最小化问题，是要最小化所有的数据点与其所关联的聚类中心点之间的距离之和。因此代价函数（畸变函数）为：$$J\left(c^{\left(1\right)},...,c^{\left(m\right)},{\mu }_1,...,{\mu }_k\right)=\frac{1}{m}\sum _{i=1}^m{\Vert X^{\left(i\right)}-{\mu }_{c^{\left(i\right)}}\Vert }^2$$其中${\mu }_{c^{\left(i\right)}}$表示样本$x^{\left(i\right)}$所属簇的中心。 运行算法之前随机初始化聚类中心点的法则： 1、K＜m，即聚类中心点的个数要小于所有训练集实例的数量； 2、随机选择K个训练实例，作为一开始的K个聚类中心。 K-均值存在一个问题是，它可能会停留在一个局部最小值处，而这取决于初始化的情况。为了解决这个问题，采用多次随机初始化的方法，每次都重新进行随机初始化，最后比较多次运行K-均值的结果，选择代价函数最小的结果。这种方法在K较小时（2–10）是可行的，但如果K较大，可能也不会明显地改善。 聚类数K通常需要根据不同的问题，人工进行选择。有一个可能用上的方法是“肘部法则”：改变聚类数K，然后进行聚类，计算损失函数，拐点处即为推荐的聚类数。 当损失函数随着K的增大平缓下降，拐点不明显时，肘部法则就不是一个选择K值的有效方法了。 二、以吴恩达机器学习课程练习材料实现，使用k-means聚类算法进行图像压缩，减少图像中出现的颜色数量，只剩下那些在图像中最常见的颜色。代码实现来源参考：吴恩达机器学习作业Python实现(七)：K-means和PCA主成分分析。 K-means算法实现相关函数代码如下：

from scipy.io import loadmat import numpy as np import matplotlib.pyplot as plt from skimage import io #找到离样本最近的簇中心点 def findClosestCentroids(X, centroids): idx = [] #存储最近的簇中心点对应的索引 max_dist = 1000000 #限制最大距离 for i in range(len(X)): dist = np.sum(np.square(X[i,:]-centroids), axis=1) #计算样本与每个簇中心点的距离 if dist.min() < max_dist: ci = np.argmin(dist) #获得距离最近的簇中心点的索引 idx.append(ci) return np.array(idx) #重新分配簇中心点 def computeCentroids(X, idx): centroids = [] #存储新的簇中心点 for i in range(len(np.unique(idx))): #以簇中心点数量进行循环 u_k = X[idx == i].mean(axis=0) #同一簇中心点下的样本按列求均值，得到新的簇中心点 centroids.append(u_k) return np.array(centroids) #实现K-means算法 def runKmeans(X, centroids, max_iters): centroids_all = [] #存储每次簇中心点记录 centroids_all.append(centroids) centroids_i = centroids for i in range(max_iters): idx = findClosestCentroids(X, centroids_i) #找到离样本最近的簇中心点 centroids_i = computeCentroids(X, idx) #重新分配簇中心点 centroids_all.append(centroids_i) return idx, centroids_all #返回最后的分类结果及簇中心点记录 #从训练集中选择随机的样本进行簇中心点初始化 def initCentroids(X, K): m = X.shape[0] #获得样本行数 idx = np.random.choice(m, K) centroids = X[idx] #根据簇中心点数量随机抽取样本初始化 return centroids

处理图像及聚类压缩的代码如下：

A = io.imread('bird_small.png') #读取图片存储为ndarray对象 #print(A.shape) A = A / 255 #设置像素值在0-1之间 X = A.reshape(-1, 3) #ndarray调整为3列 K = 16 centroids = initCentroids(X, K) #随机初始化簇中心点 idx, centroids_all = runKmeans(X, centroids, 10) #运行K-means算法 img = np.zeros(X.shape) centroids = centroids_all[-1] #获得最终的簇中心点 for i in range(len(centroids)): img[idx == i] = centroids[i] #获得压缩后16个簇中心点表示的图像 img = img.reshape((128, 128, 3)) #调整为原来的图像格式 fig, axes = plt.subplots(1, 2, figsize=(12, 6)) #初始化图像为1行2列 axes[0].imshow(A) #显示原来图像和压缩后的图像 axes[1].imshow(img)

将图片压缩为用16种颜色表示，原图像和压缩后的图像分别如下所示：

（结语个人日记：前几天回到了学校，办理完了毕业手续。面对离别，有说不出的感觉，也不太喜欢回忆四年的时光，因为回忆总让自己产生感慨情绪。当时间突然空闲下来，发现自己竟然不习惯了，那就珍惜当下，提升充实自己，为未来做好准备叭。）