【机器学习】无监督学习--（聚类）K-Means

1. K-Means概述

       算法接受参数k；然后将事先输入的n个数据对象划分为k个聚类以便使得所获得的聚类满足：同一个聚类中的对象相似度较高，而不同聚类中的对象相似度较小。

2. 算法思想

       以空间k个点为中心进行聚类，对最靠近它们的对象归类。通过迭代的方法，逐次更新各聚类中心的值，直至得到最好的聚类结果。

3. 算法流程

1）先从没有标签的元素集合A中随机取k个元素，作为k个子集各自的重心。
2）分别计算剩下的元素到k个子集重心的距离（这里的距离也可以使用欧氏距离），根据距离将这些元素分别划归到最近的子集。
3）根据聚类结果，重新计算重心（重心的计算方法是计算子集中所有元素各个维度的算数平均数）。
4）将集合A中全部元素按照新的重心然后再重新聚类。
5）重复第4步，直到聚类结果不再发生变化。

4. 代码实现

注：数据集在文章末尾

（1）K-Means – python实现

import numpy as np
import matplotlib.pyplot as plt  # 载入数据
data = np.genfromtxt("kmeans.txt", delimiter=" ")plt.scatter(data[:,0],data[:,1])
plt.show()

输出：

## 训练模型 # 计算距离 
def euclDistance(vector1, vector2):  return np.sqrt(sum((vector2 - vector1)**2))# 初始化质心
def initCentroids(data, k):  numSamples, dim = data.shape# k个质心，列数跟样本的列数一样centroids = np.zeros((k, dim))  # 随机选出k个质心for i in range(k):  # 随机选取一个样本的索引index = int(np.random.uniform(0, numSamples))  # 作为初始化的质心centroids[i, :] = data[index, :]  return centroids  # 传入数据集和k的值
def kmeans(data, k):  # 计算样本个数numSamples = data.shape[0]   # 样本的属性，第一列保存该样本属于哪个簇，第二列保存该样本跟它所属簇的误差clusterData = np.array(np.zeros((numSamples, 2)))  # 决定质心是否要改变的变量clusterChanged = True  # 初始化质心  centroids = initCentroids(data, k)  while clusterChanged:  clusterChanged = False  # 循环每一个样本 for i in range(numSamples):  # 最小距离minDist  = 100000.0  # 定义样本所属的簇minIndex = 0  # 循环计算每一个质心与该样本的距离for j in range(k):  # 循环每一个质心和样本，计算距离distance = euclDistance(centroids[j, :], data[i, :])  # 如果计算的距离小于最小距离，则更新最小距离if distance < minDist:  minDist  = distance # 更新最小距离clusterData[i, 1] = minDist# 更新样本所属的簇minIndex = j  # 如果样本的所属的簇发生了变化if clusterData[i, 0] != minIndex:  # 质心要重新计算clusterChanged = True# 更新样本的簇clusterData[i, 0] = minIndex# 更新质心for j in range(k):  # 获取第j个簇所有的样本所在的索引cluster_index = np.nonzero(clusterData[:, 0] == j)# 第j个簇所有的样本点pointsInCluster = data[cluster_index]  # 计算质心centroids[j, :] = np.mean(pointsInCluster, axis = 0) 
# showCluster(data, k, centroids, clusterData)return centroids, clusterData  # 显示结果 
def showCluster(data, k, centroids, clusterData):  numSamples, dim = data.shape  if dim != 2:  print("dimension of your data is not 2!")  return 1  # 用不同颜色形状来表示各个类别mark = ['or', 'ob', 'og', 'ok', '^r', '+r', 'sr', 'dr', '<r', 'pr']  if k > len(mark):  print("Your k is too large!")  return 1  # 画样本点  for i in range(numSamples):  markIndex = int(clusterData[i, 0])  plt.plot(data[i, 0], data[i, 1], mark[markIndex])  # 用不同颜色形状来表示各个类别mark = ['*r', '*b', '*g', '*k', '^b', '+b', 'sb', 'db', '<b', 'pb']  # 画质心点 for i in range(k):  plt.plot(centroids[i, 0], centroids[i, 1], mark[i], markersize = 20)  plt.show()# 设置k值
k = 4  
# centroids 簇的中心点 
# cluster Data样本的属性，第一列保存该样本属于哪个簇，第二列保存该样本跟它所属簇的误差
centroids, clusterData = kmeans(data, k)  
if np.isnan(centroids).any():print('Error')
else:print('cluster complete!')   # 显示结果
showCluster(data, k, centroids, clusterData)  

输出：

## 预测# 做预测
x_test = [0,1]
np.tile(x_test,(k,1))
# 误差
np.tile(x_test,(k,1))-centroids
# 误差平方
(np.tile(x_test,(k,1))-centroids)**2
# 误差平方和
((np.tile(x_test,(k,1))-centroids)**2).sum(axis=1)
# 最小值所在的索引号
index = np.argmin(((np.tile(x_test,(k,1))-centroids)**2).sum(axis=1))
print(index)

输出：1

def predict(datas):return np.array([np.argmin(((np.tile(data,(k,1))-centroids)**2).sum(axis=1)) for data in datas])、# 获取数据值所在的范围
x_min, x_max = data[:, 0].min() - 1, data[:, 0].max() + 1
y_min, y_max = data[:, 1].min() - 1, data[:, 1].max() + 1# 生成网格矩阵
xx, yy = np.meshgrid(np.arange(x_min, x_max, 0.02),np.arange(y_min, y_max, 0.02))z = predict(np.c_[xx.ravel(), yy.ravel()])# ravel与flatten类似，多维数据转一维。flatten不会改变原始数据，ravel会改变原始数据
z = z.reshape(xx.shape)
# 等高线图
cs = plt.contourf(xx, yy, z)
# 显示结果
showCluster(data, k, centroids, clusterData)  

输出：

（2）K-Means – sklearn实现

from sklearn.cluster import KMeans
import numpy as np
import matplotlib.pyplot as plt# 载入数据
data = np.genfromtxt("kmeans.txt", delimiter=" ")
# 设置k值
k = 4  # 训练模型
model = KMeans(n_clusters=k)
model.fit(data)# 分类中心点坐标
centers = model.cluster_centers_
print(centers)

输出：

# 预测结果
result = model.predict(data)
print(result)

# 画出各个数据点，用不同颜色表示分类
mark = ['or', 'ob', 'og', 'oy']
for i,d in enumerate(data):plt.plot(d[0], d[1], mark[result[i]])# 画出各个分类的中心点
mark = ['*r', '*b', '*g', '*y']
for i,center in enumerate(centers):plt.plot(center[0],center[1], mark[i], markersize=20)plt.show()

输出：

# 获取数据值所在的范围
x_min, x_max = data[:, 0].min() - 1, data[:, 0].max() + 1
y_min, y_max = data[:, 1].min() - 1, data[:, 1].max() + 1# 生成网格矩阵
xx, yy = np.meshgrid(np.arange(x_min, x_max, 0.02),np.arange(y_min, y_max, 0.02))z = model.predict(np.c_[xx.ravel(), yy.ravel()])# ravel与flatten类似，多维数据转一维。flatten不会改变原始数据，ravel会改变原始数据
z = z.reshape(xx.shape)
# 等高线图
cs = plt.contourf(xx, yy, z)
# 显示结果
# 画出各个数据点，用不同颜色表示分类
mark = ['or', 'ob', 'og', 'oy']
for i,d in enumerate(data):plt.plot(d[0], d[1], mark[result[i]])# 画出各个分类的中心点
mark = ['*r', '*b', '*g', '*y']
for i,center in enumerate(centers):plt.plot(center[0],center[1], mark[i], markersize=20)plt.show()

输出：

数据集：“kmeans.txt”：

1.658985 4.285136  
-3.453687 3.424321  
4.838138 -1.151539  
-5.379713 -3.362104  
0.972564 2.924086  
-3.567919 1.531611  
0.450614 -3.302219  
-3.487105 -1.724432  
2.668759 1.594842  
-3.156485 3.191137  
3.165506 -3.999838  
-2.786837 -3.099354  
4.208187 2.984927  
-2.123337 2.943366  
0.704199 -0.479481  
-0.392370 -3.963704  
2.831667 1.574018  
-0.790153 3.343144  
2.943496 -3.357075  
-3.195883 -2.283926  
2.336445 2.875106  
-1.786345 2.554248  
2.190101 -1.906020  
-3.403367 -2.778288  
1.778124 3.880832  
-1.688346 2.230267  
2.592976 -2.054368  
-4.007257 -3.207066  
2.257734 3.387564  
-2.679011 0.785119  
0.939512 -4.023563  
-3.674424 -2.261084  
2.046259 2.735279  
-3.189470 1.780269  
4.372646 -0.822248  
-2.579316 -3.497576  
1.889034 5.190400  
-0.798747 2.185588  
2.836520 -2.658556  
-3.837877 -3.253815  
2.096701 3.886007  
-2.709034 2.923887  
3.367037 -3.184789  
-2.121479 -4.232586  
2.329546 3.179764  
-3.284816 3.273099  
3.091414 -3.815232  
-3.762093 -2.432191  
3.542056 2.778832  
-1.736822 4.241041  
2.127073 -2.983680  
-4.323818 -3.938116  
3.792121 5.135768  
-4.786473 3.358547  
2.624081 -3.260715  
-4.009299 -2.978115  
2.493525 1.963710  
-2.513661 2.642162  
1.864375 -3.176309  
-3.171184 -3.572452  
2.894220 2.489128  
-2.562539 2.884438  
3.491078 -3.947487  
-2.565729 -2.012114  
3.332948 3.983102  
-1.616805 3.573188  
2.280615 -2.559444  
-2.651229 -3.103198  
2.321395 3.154987  
-1.685703 2.939697  
3.031012 -3.620252  
-4.599622 -2.185829  
4.196223 1.126677  
-2.133863 3.093686  
4.668892 -2.562705  
-2.793241 -2.149706  
2.884105 3.043438  
-2.967647 2.848696  
4.479332 -1.764772  
-4.905566 -2.911070