K-means算法

一、概念说明

K-means算法的主要目的是最小化点与它们各自的簇质心之间的距离之和。

现在让我们举个例子来了解K-means实际上是如何工作的

我们有这8个点，我们想要应用K-means来为这些点划分簇。下面将演示我们是怎样做到的。

第一步：选择簇的数目k

K-means的第一步是选择簇的数目k。

第二步：从数据中选择k个随机点作为质心

接下来，我们为每个簇随机选择质心。假设我们想要有2个簇，所以k在这里等于2。然后我们随机选择质心：

这里，红色和绿色圆圈代表这些簇的质心。

第三步：将所有点分配给到某个质心距离最近的簇

一旦我们初始化了质心，我们就将每个点分配给到某个质心距离最近的簇：

在这里，你可以看到更接近红点的点被分配给红色簇，而更接近绿点的点被分配给绿色簇。

第四步：重新计算新形成的簇的质心

现在，一旦我们将所有点分配到任一簇中，下一步就是计算新形成的簇的质心：

在这里，红色和绿色叉号是新的质心。

第五步：重复第三步和第四步

计算质心并基于它们与质心的距离将所有点分配给簇的步骤是单次迭代。但我们什么时候应该停止这个过程？它不能永远运行下去对吧？

停止K-means聚类的标准

基本上有三种停止标准可用于停止K-means算法：

1、新形成的簇的质心不会改变

2、数据点保留在同一个簇中

3、达到最大迭代次数

如果新形成的簇的质心没有变化，我们就可以停止算法。即使在多次迭代之后，所有簇都还是相同的质心，我们可以说该算法没有学习任何新模式，并且它是停止训练的标志。

另一个明显的迹象表明，在多次迭代训练的之后，如果数据点仍然都在同一簇中，我们应该停止训练过程。

最后，如果达到最大迭代次数，我们可以停止训练。假设我们将迭代次数设置为100。在停止之前，该过程将重复100次迭代。

二、python代码实现

#定义函数：计算二维空间中两点的欧氏距离
def EuclideanDistance(x, y):
    return math.sqrt(math.pow(x[0]-y[0],2)+math.pow(x[1]-y[1],2))

#定义函数：计算一个DataFrame中点集的形心
def Centroid(df):
    Centroid_x = df['属性1'].mean()
    Centroid_y = df['属性2'].sum()/len(df)
    return [Centroid_x,Centroid_y]

#定义函数：以形心点组成的DF——’Centroid_group‘为基准，对于样本点集’df‘中的点进行聚类，并分别得到group_a/b/c三个新的点集，
#此为聚类后的三类
def Clustering(df,Centroid_group):
        group_a = np.zeros(shape = (1,2))
        group_b = np.zeros(shape = (1,2))
        group_c = np.zeros(shape = (1,2))
        for i in range(11):
            a = EuclideanDistance([df.iloc[i,0],df.iloc[i,1]],
                              [Centroid_group.iloc[0,0],Centroid_group.iloc[0,1]])
            b = EuclideanDistance([df.iloc[i,0],df.iloc[i,1]],
                              [Centroid_group.iloc[1,0],Centroid_group.iloc[1,1]])
            c = EuclideanDistance([df.iloc[i,0],df.iloc[i,1]],
                              [Centroid_group.iloc[2,0],Centroid_group.iloc[2,1]])
 
            if a == min(a,b,c):
                group_a = np.append(group_a, [[df.iloc[i,0], df.iloc[i,1]]], axis=0)
            elif b == min(a,b,c):
                group_b = np.append(group_b, [[df.iloc[i,0], df.iloc[i,1]]], axis=0)
            else:
                group_c = np.append(group_c, [[df.iloc[i,0], df.iloc[i,1]]], axis=0)   
        group_a = np.delete(group_a, 0, 0)
        group_b = np.delete(group_b, 0, 0)
        group_c = np.delete(group_c, 0, 0)
 
        a = pd.DataFrame(group_a,columns=['属性1','属性2'],dtype='float64')
        b = pd.DataFrame(group_b,columns=['属性1','属性2'],dtype='float64')
        c = pd.DataFrame(group_c,columns=['属性1','属性2'],dtype='float64')
        print('第一类为：')
        print(a)
        print('第二类为：')
        print(b)
        print('第三类为：')
        print(c)
        return a,b,c

#将初始点存入一个DF中
data = {'属性1':[8,6,1,7,1,4,3,5,7,4,5],
        '属性2':[9,8,5,0,1,7,7,5,2,8,6]}
frame = pd.DataFrame(data,index=['X1','X2','X3','X4','X5','x6','x7','x8','x9','x10','x11'])
print(frame) 

#指定作为第一次分类的初始形心集
Centroid_init = frame.iloc[0:3,:]
type(Centroid_init)
Centroid_init

Centroid_new = Centroid_init
i = 1
while i <= 300:
    print('————————————————————第' + str(i) + '次分类开始——————————————————————————')
    Centroid_new = pd.DataFrame(Centroid_new) #转换格式（由于意外报错）
    l = Clustering(frame,Centroid_new)
    Centroid_new = {'属性1':[Centroid(l[0])[0],Centroid(l[1])[0],Centroid(l[2])[0]],
            '属性2':[Centroid(l[0])[1],Centroid(l[1])[1],Centroid(l[2])[1]]}
    print('————————————————————第' + str(i) + '次分类结束——————————————————————————')
    print('新的形心集为：')
    print(pd.DataFrame(Centroid_new))#输出新的形心集
            #处理计数器
    i += 1
 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

参考文献1

参考文献2