1.k-means算法步骤详解

使用2维的样本进行讲解，用x-y坐标系表示就是sample=(x, y)，比如sample=(1,3)。其他n维度样本的k-means算法步骤也是一样，不影响理解，都是一样的道理。

1.1算法步骤

Step1.给定初始质心：首先选取初始质心集合centroids

说明：

A.质心数量由用户给出，记为k，k-means最终得到的簇数量也是k

B.每个质心的数值由初始质心的计算算法计算得到，初始质心计算算法由用户给出

C.k-means最后聚类的簇个数和用户指定的质心个数相等，一个质心对应一个簇，每个样本只聚类到一个簇里面

D.初始簇为空

Step2.样本聚类：计算每个样本和每个质心的距离，将样本聚类到距离最近的质心的簇里面

说明：

A.样本和质心的距离可以使用欧氏距离（欧几里得距离）

用python表示就是np.sqrt(sum(np.power(p1-p2,2)))，p1=np.array([x1,y1]), p2=np.array([x2, y2])

B.如果得到某一个样本和每个质心的距离为：distances=[5, 6, 2, 1,3,9]，则可知此样本将被分到第4个质心所在的簇

第4个簇的簇号是3，用python表示簇号就是np.argmin(distances) = 3

C.经过step2，得到k个新的簇，每个样本都被分到k个簇中的某一个簇

D.得到k个新的簇后，当前的质心就会失效，需要计算每个新簇的自己的新质心

Step3.重新计算质心：每个簇的新质心的属性值等于此簇中所有样本的属性值得平均值

说明：

A.比如一个新簇有3个样本：[[1,4], [2,5], [3,6]]，得到此簇的新质心=[(1+2+3)/3,   (4+5+6)/3]

B.经过step3，会得到k个新的质心，作为step2中使用的质心

Step4.是否停止K-means：给定loop最大次数loopLimit 以及 所有质心变化距离的最大值maxDistance

A.当loop次数超过looLimit时，停止k-means

B.当所有质心变化的距离组成的序列中的最大值，小于maxDistance时，停止k-means

旧的质心集合=[[1,1], [2,2], [3,3]]

新的质心集合=[[1.5,1.5],[4,4],[6,6]]

所有质心的变化距离序列=[np.sqrt(0.5), np.sqrt(8), np.sqrt(18)] = [0.71, 2.83, 4.24]

所有质心的变化距离的最大值=max([0.71, 2.83, 4.24]) = 4.24

如果maxDistance=5, 由于4.24 < maxDistance，则停止k-means

如果maxDistance=1, 由于4.24 > maxDistance，则继续k-means

C.只需要满足loopLimit和maxDistance其中的一个条件，就可以停止k-means

Step5.

           如果step4没有结束k-means，就再执行step2-step3-step4-step5

           如果step4结束了k-means，则就打印(或绘制)簇以及质心

1.2样本和质心之间距离的度量方法

在上面step2样本聚类步骤中我们使用欧氏距离作为样本和质心之间距离的度量方法。

也可以使用其他的距离度量方法，下面是常用的距离度量方法有：

1.2.1 欧氏距离

1.2.2 曼哈顿距离：

1.2.3 余弦相似度：

2.用样本数据集实例详解k-means算法过程

2.1样本数据集

    samples = np.array([[1,1], #sample 1
                       [2,2],  #sample 2
                       [3,1],  #sample 3
                       [6,4],
                       [7,5],
                       [8,4]])

即6个样本：(1, 1), (2, 2), (3, 1), (6, 4), (7, 5), (8, 4)

绘制结果如下：

2.2给k-means算法结束的条件

    给定loopLimit = 100, maxDistance=1

2.3给定初始质心

由于是样本数据集讲解k-means算法，这里初始质心是看着绘制结果图给定的，可以知道理想结果是k=2

就选取样本集的前k个样本数据作为初始质心 (1,1), (2,2)

结论：k = 2,  centroids = [[1,1], [2,2]]

2.4样本聚类+重新计算质心直到停止k-means算法

=====================第一次k-means算法=======================

第一次样本聚类：

用字典dict存储簇，重置簇clusters={}

样本	质心(1,1)的距离	质心(2,2)的距离	目标簇号
[1 1]	0.0	1.41421356237	0
[2 2]	1.41421356237	0.0	1
[3 1]	2.0	1.41421356237	1
[6 4]	5.83095189485	4.472135955	1
[7 5]	7.21110255093	5.83095189485	1
[8 4]	7.61577310586	6.32455532034	1

new clusters = {0: [[1, 1]], 1: [[2, 2], [3, 1], [6, 4], [7, 5], [8, 4]]}

计算新的质心

centroid_1 = [1, 1] = [1/1, 1/1]

centroid_2 = [5.20, 3.20] = [(2 + 3 + 6 + 7 + 8)/5,  (2 + 1 + 4 + 5 + 4)/5]

centroids = [[1,1], [5.20, 3.20]]

第一次k-means的结果

old centroids	[[1,1], [2,2]]
clusters	{0: [[1, 1]], 1: [[2, 2], [3, 1], [6, 4], [7, 5], [8, 4]]}
new centroids	[[1, 1], [5.20, 3.20]]

判断是否结束k-means算法

loop	1
old centroids	[[1,1], [2,2]]
new centroids	[[1, 1], [5.20, 3.20]]
质心的变化距离序列	[0, 3.42]
质心的变化距离序列中的最大值	3.42
maxDistance	1
loopLimit	100
loop < loopLimit ?	True，继续k-means
3.42 > maxDistance ?	True，继续k-means

结论：需要继续K-means算法，下面开始第二次K-means算法

==================第二次k-means算法======================

第二次样本聚类：

用字典dict存储簇，重置簇clusters={}

样本	质心(1,1)的距离	质心(5.20, 3.20)的距离	目标簇号
[1 1]	0.0	4.74	0
[2 2]	1.41	3.42	0
[3 1]	2.0	3.11	0
[6 4]	5.83	1.13	1
[7 5]	7.21	2.55	1
[8 4]	7.62	2.91	1

clusters = {0: [[1, 1], [2, 2], [3, 1]], 1: [[6, 4], [7, 5], [8, 4]]}

第二次计算新的质心

centroid_1 = [2.0, 1.33] = [(1+2+3)/3,  (1+2+1)/3]

centroid_2 = [7.0, 4.33] = [(6 + 7 + 8)/3,  (4 + 5 + 4)/3]

centroids = [[2.0, 1.33], [7.0, 4.33]]

第二次k-means的结果

old centroids	[[1, 1], [5.20, 3.20]]
clusters	{0: [[1, 1], [2, 2], [3, 1]], 1: [[6, 4], [7, 5], [8, 4]]}
new centroids	[[2.0, 1.33], [7.0, 4.33]]

判断是否结束k-means算法

loop	1
old centroids	[[1,1], [5.20,3.20]]
new centroids	[[2.0, 1.33], [7.0, 4.33]]
质心的变化距离序列	[1.05, 2.13]
质心的变化距离序列中的最大值	2.13
maxDistance	1
loopLimit	100
loop < loopLimit(100) ?	True，继续k-means
2.13 > maxDistance(1) ?	True，继续k-means

结论：需要继续K-means算法，下面开始第三次K-means算法

==================第三次k-means算法======================

第三次样本聚类：

用字典dict存储簇，重置簇clusters={}

样本	质心(2.0,1.33)的距离	质心(7.0, 4.33)的距离	目标簇号
[1 1]	1.05	6.86	0
[2 2]	0.67	5.52	0
[3 1]	1.05	5.21	0
[6 4]	4.81	1.05	1
[7 5]	6.20	0.67	1
[8 4]	6.57	1.05	1

clusters ={0: [[1, 1], [2, 2], [3, 1]], 1: [[6, 4], [7, 5], [8, 4]]}

第三次计算新的质心

centroid_1 = [2.0, 1.33] = [(1+2+3)/3,  (1+2+1)/3]

centroid_2 = [7.0, 4.33] = [(6 + 7 + 8)/3,  (4 + 5 + 4)/3]

centroids = [[2.0, 1.33], [7.0, 4.33]]

第三次k-means的结果

old centroids	[[1, 1], [5.20, 3.20]]
clusters	{0: [[1, 1], [2, 2], [3, 1]], 1: [[6, 4], [7, 5], [8, 4]]}
new centroids	[[2.0, 1.33], [7.0, 4.33]]

判断是否结束k-means算法

loop	1
old centroids	[[1,1], [5.20,3.20]]
new centroids	[[2.0, 1.33], [7.0, 4.33]]
质心的变化距离序列	[1.05, 2.13]
质心的变化距离序列中的最大值	2.13
maxDistance	1
loopLimit	100
loop < loopLimit(100) ?	True，继续k-means
2.13 > maxDistance(1) ?	True，继续k-means

结论：需要继续K-means算法，下面开始第四次K-means算法

==================第四次k-means算法======================

第四次样本聚类：

用字典dict存储簇，重置簇clusters={}

样本	质心(2.0,1.33)的距离	质心(7.0, 4.33)的距离	目标簇号
[1 1]	1.05	6.86	0
[2 2]	0.67	5.52	0
[3 1]	1.05	5.21	0
[6 4]	4.81	1.05	1
[7 5]	6.20	0.67	1
[8 4]	6.57	1.05	1

clusters ={0: [[1, 1], [2, 2], [3, 1]], 1: [[6, 4], [7, 5], [8, 4]]}

第四次计算新的质心

centroid_1 = [2.0, 1.33] = [(1+2+3)/3,  (1+2+1)/3]

centroid_2 = [7.0, 4.33] = [(6 + 7 + 8)/3,  (4 + 5 + 4)/3]

centroids = [[2.0, 1.33], [7.0, 4.33]]

第四次k-means的结果

old centroids	[[2.0, 1.33], [7.0, 4.33]]
clusters	{0: [[1, 1], [2, 2], [3, 1]], 1: [[6, 4], [7, 5], [8, 4]]}
new centroids	[[2.0, 1.33], [7.0, 4.33]]

判断是否结束k-means算法

loop	1
old centroids	[[2.0, 1.33], [7.0, 4.33]]
new centroids	[[2.0, 1.33], [7.0, 4.33]]
质心的变化距离序列	[0, 0]
质心的变化距离序列中的最大值	0
maxDistance	1
loopLimit	100
loop < loopLimit(100) ?	True，继续k-means
0 > maxDistance(1) ?	False，结束k-means

结论：结束k-means算法，最终的簇和质心为：

clusters ={0: [[1, 1], [2, 2], [3, 1]], 1: [[6, 4], [7, 5], [8, 4]]}

centroids = [ [2.0, 1.33],  [7.0, 4.33]]

2.5k-means结果打印

k-means origin samples: [[1 1]
 [2 2]
 [3 1]
 [6 4]
 [7 5]
 [8 4]]
k-means loopLimit: 100
k-means maxDistance: 1
k-means target clusters: {0: [[1, 1], [2, 2], [3, 1]], 1: [[6, 4], [7, 5], [8, 4]]}
k-means target centroids: [[2.0, 1.33], [7.0, 4.33]]

2.6结果绘制图形

(end)

如果还不懂，请板儿砖扔过来。