实验目的

了解基本聚类算法的基本原理，并掌握Python语言中实现Kmeans聚类算法的函数方法

实验原理

聚类就是将相似的事物聚集在一起，而将不相似的事物划分到不同的类别的过程，是数据分析之中十分重要的一种手段。在数据分析的术语之中，聚类和分类是两种技术。分类是指我们已经知道了事物的类别，需要从样品中学习分类的规则，是一种监督式学习；而聚类则是由我们来给定简单的规则，从而得到类别，是一种无监督学习。

在K均值算法中，质心是定义聚类原型（也就是机器学习获得的结果）的核心。在介绍算法实施的具体过程中，我们将演示质心的计算方法。而且你将看到除了第一次的质心是被指定的以外，此后的质心都是经由计算均值而获得的。

首先，选择K个初始质心（这K个质心并不要求来自于样本数据集），其中K是用户指定的参数，也就是所期望的簇的个数。每个数据点都被收归到距其最近之质心的分类中，而同一个质心所收归的点集为一个簇。然后，根据本次分类的结果，更新每个簇的质心。重复上述数据点分类与质心变更步骤，直到簇内数据点不再改变，或者等价地说，直到质心不再改变。

KMeans算法的基本思想是初始随机给定K个簇中心，按照最邻近原则把待分类样本点分到各个簇。然后按平均法重新计算各个簇的质心，从而确定新的簇心。一直迭代，直到簇心的移动距离小于某个给定的值。

复杂度分析

• 时间复杂度：O(tKmn)，其中，t为迭代次数，K为簇的数目，m为记录数，n为维数
• 空间复杂度：O((m+K)n)，其中，K为簇的数目，m为记录数，n为维数

实验步骤

K-Means聚类算法主要分为三个步骤：

1，初始化k个聚类中心。

2，计算出每个对象跟这k个中心的距离（相似度计算，这个下面会提到），假如x这个对象跟y这个中心的距离最小（相似度最大），那么x属于y这个中心。这一步就可以得到初步的k个聚类 。

3，在第二步得到的每个聚类分别计算出新的聚类中心，和旧的中心比对，假如不相同，则继续第2步，直到新旧两个中心相同，说明聚类不可变，已经成功 。

本实验采用数据集为scikit -learn所包含的数据集，点击链接查看数据集描述。

machine-learning-databases/iris点击打开链接

可以通过以下命令查看数据。

1. from sklearn import datasets
2. iris=datasets.load_iris()
3. 1. #data对应了样本的4个特征，150行4列
4. print iris.data.shape
5. 1. #显示样本特征的前5行
6. print iris.data[:5]
7. 1. #target对应了样本的类别（目标属性），150行1列
8. print iris.target.shape
9. 1. #显示所有样本的目标属性
10. print iris.target

结果为：

第一步，将文件中的数据读入到dataset列表中，通过len(dataset[0])来获取数据维数，在测试样例中是四维。

第二步，产生聚类的初始位置。首先扫描数据，获取每一维数据分量中的最大值和最小值，然后在这个区间上随机产生一个值，循环k次(k为所分的类别),这样就产生了聚类初始中心（k个）

第三步，按照最短距离（欧式距离）原则将所有样本分配到k个聚类中心中的某一个，这步操作的结果是产生列表assigments，可以通过Python中的zip函数整合成字典。注意到原始聚类中心可能不在样本中，因此可能出现分配的结果出现某一个聚类中心点集合为空，此时需要结束，提示“随机数产生错误，需要重新运行”，以产生合适的初始中心。

第四步，计算各个聚类中心的新向量，更新距离，即每一类中每一维均值向量。然后再进行分配，比较前后两个聚类中心向量是否相等，若不相等则进行循环，否则终止循环，进入下一步。

最后，将结果输出到文件和屏幕中

结果为：

完整代码如下：

1. # coding=gbk
2. #python edition: Python3.4.1,2014,9,24
3. from collections import defaultdict
4. from random import uniform
5. from math import sqrt
6. from sklearn.datasets import load_iris
7. 1. 1. def read_points():
8. dataset=[]
9. with open('Iris.txt','r') as file:
10. for line in file:
11. if line =='\n':
12. continue
13. dataset.append(list(map(float,line.split(' '))))
14. file.close()
15. return dataset
16. 1. def write_results(listResult,dataset,k):
17. with open('result.txt','a') as file:
18. for kind in range(k):
19. file.write( "CLASSINFO:%d\n"%(kind+1) )
20. for j in listResult[kind]:
21. file.write('%d\n'%j)
22. file.write('\n')
23. file.write('\n\n')
24. file.close()
25. 1. def point_avg(points):
26. dimensions=len(points[0])
27. new_center=[]
28. for dimension in range(dimensions):
29. sum=0
30. for p in points:
31. sum+=p[dimension]
32. new_center.append(float("%.8f"%(sum/float(len(points)))))
33. return new_center
34. 1. def update_centers(data_set ,assignments,k):
35. new_means = defaultdict(list)
36. centers = []
37. for assignment ,point in zip(assignments , data_set):
38. new_means[assignment].append(point)
39. for i in range(k):
40. points=new_means[i]
41. centers.append(point_avg(points))
42. return centers
43. 1. def assign_points(data_points,centers):
44. assignments=[]
45. for point in data_points:
46. shortest=float('inf')
47. shortest_index = 0
48. for i in range(len(centers)):
49. value=distance(point,centers[i])
50. if value<shortest:
51. shortest=value
52. shortest_index=i
53. assignments.append(shortest_index)
54. if len(set(assignments))<len(centers) :
55. print("\n--!!!产生随机数错误，请重新运行程序！!!!--\n")
56. exit()
57. return assignments
58. 1. def distance(a,b):
59. dimention=len(a)
60. sum=0
61. for i in range(dimention):
62. sq=(a[i]-b[i])**2
63. sum+=sq
64. return sqrt(sum)
65. 1. def generate_k(data_set,k):
66. centers=[]
67. dimentions=len(data_set[0])
68. min_max=defaultdict(int)
69. for point in data_set:
70. for i in range(dimentions):
71. value=point[i]
72. min_key='min_%d'%i
73. max_key='max_%d'%i
74. if min_key not in min_max or value<min_max[min_key]:
75. min_max[min_key]=value
76. if max_key not in min_max or value>min_max[max_key]:
77. min_max[max_key]=value
78. for j in range(k):
79. rand_point=[]
80. for i in range(dimentions):
81. min_val=min_max['min_%d'%i]
82. max_val=min_max['max_%d'%i]
83. tmp=float("%.8f"%(uniform(min_val,max_val)))
84. rand_point.append(tmp)
85. centers.append(rand_point)
86. return centers
87. 1. def k_means(dataset,k):
88. k_points=generate_k(dataset,k)
89. assignments=assign_points(dataset,k_points)
90. old_assignments=None
91. while assignments !=old_assignments:
92. new_centers=update_centers(dataset,assignments,k)
93. old_assignments=assignments
94. assignments=assign_points(dataset,new_centers)
95. result=list(zip(assignments,dataset))
96. print('\n\n---------------------------------分类结果---------------------------------------\n\n')
97. for out in result :
98. print(out,end='\n')
99. print('\n\n---------------------------------标号简记---------------------------------------\n\n')
100. listResult=[[] for i in range(k)]
101. count=0
102. for i in assignments:
103. listResult[i].append(count)
104. count=count+1
105. write_results(listResult,dataset,k)
106. for kind in range(k):
107. print("第%d类数据有:"%(kind+1))
108. count=0
109. for j in listResult[kind]:
110. print(j,end=' ')
111. count=count+1
112. if count%25==0:
113. print('\n')
114. print('\n')
115. print('\n\n--------------------------------------------------------------------------------\n\n')
116. 1. def main():
117. dataset=read_points()
118. k_means(dataset,3)
119. 1. if __name__ == "__main__":
120. main()