目录
1. K-Means 定义
2. K-Means 步骤
3. K-Means 和 KNN 对比
4. 小练习
4.1 第一题
4.2 第二题
4.3 第三题
最后
1. K-Means 定义
K-means聚类算法首先是随机选取K个对象作为初始的聚类中心，然后计算每个样本与各个聚类中心之间的距离，把每个样本分配给距离它最近的聚类中心。
聚类中心以及分配给它们的对象就代表一个聚类。每分配一次样本，聚类的聚类中心会根据聚类中现有的对象被重新计算。这个过程将不断重复直到满足某个终止条件。
终止条件可以是没有（或最小数目）样本被重新分配给不同的聚类，没有（或最小数目）聚类中心再发生变化，误差平方和局部最小。
2. K-Means 步骤
理论：
1 . 随机生成K个聚类中心。
2 .计算每个样本与每一个聚类中心的距离(欧式距离)，离哪个聚类中心近，就划分到哪个聚类中心所属的集合当中。
3 .重新计算每个集合的聚类中心。
4 .重复2，3步直到收敛。
5 .返回所有的聚类标签。
图解K-Means：
数据集采用的是make_blobs，
① 设置K=2，第一次随机划分了两个聚类，可以看出是非常不平衡的！还没有收敛~
② 计算每个样本与这两个聚类中心的距离(欧式距离)，离哪个聚类中心近，就划分到哪个聚类中心所属的集合当中。
如果这个样本点到两个聚类中的距离都是相等的话，就会随机分配到其中一类。
那么当这次聚类结束后，两个聚类会重新进行聚类中心点的计算，聚类中心就会改变。
那么下一次进行样本点和聚类中心点聚类计算的时候，这个样本点该划分到哪一类就会是哪一类。
也就是说这个随机是不影响最终的聚类结果的。
可以换个参考系想想，这两个聚类中心点不断在找自己的样本，就算中间过程中找错了，也不会影响最终的结果，他该有哪些样本点还是哪些样本点
③ 当划分完这一次所有样本点到各个聚类中心之后（即哪个样本点离哪个聚类中心近，就分到哪个聚类中心的集合），重新计算聚类中心的位置，即是黑色点的位置。
下图，红色点是没有计算的，就是上一次的聚类中心点，所以紫色的样本点都是距离右边的红点近的，黄色的样本点都是距离左边的红点近的，黑色点是重新计算后的
然后就通过这个重新计算后的黑色点，继续计算各个样本点到这个黑色点的距离，离左边的聚类中心近的就是黄色区域，离右边聚类中心点近的就是属于右边的一类。
可以看一下这一次聚类的过程： 一共迭代了15次才收敛
3. K-Means 和 KNN 对比
下面两张图来自B站Up五分钟机器学习
Sklearn中的make_circles方法生成数据，用K-Means聚类并可视化。
""" Sklearn中的make_circles方法生成数据，用K-Means聚类并可视化。 """ from sklearn.cluster import KMeans from sklearn.datasets import make_circles import matplotlib.pyplot as plt from ex1.clustering_performance import clusteringMetrics # 导入的老师写的库 fig = plt.figure(1, figsize=(10, 5)) X1, y1 = make_circles(n_samples=400, factor=0.5, noise=0.1) plt.subplot(121) plt.title('original') plt.scatter(X1[:, 0], X1[:, 1], c=y1) plt.subplot(122) plt.title('K-means') kms = KMeans(n_clusters=2, max_iter=400) # n_cluster聚类中心数 max_iter迭代次数 y1_sample = kms.fit_predict(X1, y1) # 计算并预测样本类别 centroids = kms.cluster_centers_ plt.scatter(X1[:, 0], X1[:, 1], c=y1_sample) plt.scatter(centroids[:, 0], centroids[:, 1], s=30, marker='*', c='b') print(clusteringMetrics(y1, y1_sample)) plt.show()
4.2 第二题
Sklearn中的make_moons方法生成数据，用K-Means聚类并可视化。
""" Sklearn中的make_moons方法生成数据，用K-Means聚类并可视化。 """ import numpy as np import matplotlib.pyplot as plt import sklearn.datasets as datasets def create_data(): X, y = datasets.make_moons(n_samples=400, noise=0.1) return X, y def init_centers(data, k): m, n = data.shape # m 样本个数，n特征个数 center_ids = np.random.choice(m, k) centers = data[center_ids] return centers def cal_dist(ptA, ptB): return np.linalg.norm(ptA - ptB) def kmeans_process(data, k): centers = init_centers(data, k) m, n = data.shape keep_changing = True pred_y = np.zeros((m,)) iteration = 0 while keep_changing: keep_changing = False # 计算剩余样本所属类别 for i in range(m): min_distance = np.inf for center in range(k): distance = cal_dist(data[i, :], centers[center, :]) if distance < min_distance: # 判断离哪个更近 min_distance = distance idx = center # 类别换下 if pred_y[i] != idx: # 判断是否发生了改变 keep_changing = True pred_y[i] = idx # 更新类别中心点坐标 for center in range(k): cluster_data = data[pred_y == center] centers[center, :] = np.mean(cluster_data, axis=0) # 求相同类别数据点的质心点 print(centers) plt.clf() plt.title(f'iteration: {iteration}') plt.scatter(X[:, 0], X[:, 1], s=30, c=pred_y) plt.scatter(centers[:, 0], centers[:, 1], s=100, c='k') plt.pause(1) iteration += 1 return centers, pred_y if __name__ == '__main__': X, y = create_data() plt.ion() centers, pred_y = kmeans_process(data=X, k=2) plt.ioff() plt.show()
4.3 第三题
给定的图像，对其像素进行聚类并可视化
from scipy.cluster.vq import * from pylab import * from PIL import Image def clusterpixels(infile, k, steps): im = array(Image.open(infile)) dx = im.shape[0] / steps dy = im.shape[1] / steps features = [] for x in range(steps): # RGB三色通道 for y in range(steps): R = mean(im[int(x * dx):int((x + 1) * dx), int(y * dy):int((y + 1) * dy), 0]) G = mean(im[int(x * dx):int((x + 1) * dx), int(y * dy):int((y + 1) * dy), 1]) B = mean(im[int(x * dx):int((x + 1) * dx), int(y * dy):int((y + 1) * dy), 2]) features.append([R, G, B]) features = array(features, 'f') # make into array # 聚类， k是聚类数目 centroids, variance = kmeans(features, k) code, distance = vq(features, centroids) codeim = code.reshape(steps, steps) codeim = np.array(Image.fromarray(codeim).resize((im.shape[1], im.shape[0]))) return codeim # k = 5 infile_Stones = 'stones.jpg' im_Stones = array(Image.open(infile_Stones)) steps = (50, 100) # image is divided in steps*steps region # 显示原图 figure() subplot(231) title('original') axis('off') imshow(im_Stones) for k in range(2, 7): codeim = clusterpixels(infile_Stones, k, steps[-1]) subplot(2, 3, k) title('K=' + str(k)) axis('off') imshow(codeim) show()
