开篇

在本系列的前面几期中，我们介绍了包含决策树及其相关算法在内的一系列有监督学习算法。本期不妨换换口味，学习一种比较简单的无监督学习算法： k-means.

k-means 算法理论讲解

你可能已经听说过这个算法，没有也不要紧，它的原理并不复杂，让我们来看看~

给你一批样本的数据，就像这样：
Alt text
其中不同的id代表不同样本，共10个样本。x和y是两个特征，每一个样本都有且只有这两个特征。

现在希望你能够对这些样本进行分类。

我们知道，在属于有监督学习的分类问题中，训练数据往往会包含类别标签。而上面这份数据本身是不含标签的，所以这并不是一个分类问题。

既然不知道类别标签，你又让我对这些样本进行分类，那如何聚类？又要聚成几类呢？

其实，在k-means中，最终聚成几类是由我们自己决定的；这里的类别标签通常用数字表示，如0,1,2等；当我们指定好类别总数后，每一个样本被归到哪一类，就需要聚类算法自己去学习了。

k-means算法学习将相似的样本聚在一起，称为一个类别(也称为一个”簇”)，而将不相似的样本划分到不同的类别(“簇”)中。

这里的相似程度，通常是用样本之间的距离来度量的，比如最常用的欧氏距离。

啰嗦了这么多，k-means算法的执行步骤可以总结如下：

(1) 对于给定的一批样本，初始化聚类中心（这里需要手动指定聚成几类），初始化每个样本所属簇；
(2) 对于每一个样本，分别计算该样本与所有聚类中心之间的距离，选择距离该样本最近的聚类中心作为该样本所属簇；
(3) 经过(2)之后，每个样本所属簇就被更新了，现在来更新聚类中心：计算每一个簇内所有样本在所有特征维度上的平均值，将其作为该簇新的聚类中心。
(4) 重复(2)、(3)若干次，便完成了聚类。

接下来，我们将根据以上四步，用Python实现k-means算法。

k-means 算法的Python实现

我们需要手动指定要聚成几类，这里用参数k来表示，比如k=3就代表我们希望聚成3类。

data是训练数据，毫无疑问也是需要手动传入的。

另外，我们还设置了一个是否随机打乱样本顺序的开关：do_shuffle，默认并保持样本原序。

1
2
3
4
5
class MyKmeans:
    def __init__(self,k,data,do_shuffle=False):
        self.k=k#自己指定聚成几类
        self.data=data#训练数据
        self.do_shuffle=do_shuffle#是否随机打乱样本顺序

现在实现(1)，即：初始化聚类中心，初始化每个样本所属簇。

这里，我直接以前k个样本的坐标分别作为k个初始聚类中心，并将每个样本的类别标签(所属簇)初始化为0。

1
2
3
4
5
6
7
def initialize(self):
    if self.do_shuffle:
        np.random.shuffle(self.data)
    #初始化聚类中心
    self.centers=self.data[:self.k]
    #初始化每个样本所属簇
    self.targets=np.zeros(self.data.shape[0])

再看(2)，其中涉及到了求距离，所以先来实现两个样本点之间的距离计算方法，这里采用欧氏距离：

1
2
def cal_dist(self,p1,p2):
    return np.sqrt(np.sum((p1-p2)**2))

然后来实现(2)，即：更新样本所属簇

1
2
3
4
5
6
for i,item in enumerate(self.data):#对于每一个样本点
    c=[]#分别计算该样本点到k个聚类中心的距离，并存入c
    for j in range(len(self.centers)):
        c.append(self.cal_dist(item,self.centers[j]))
    #print(c)
    self.targets[i]=np.argmin(c)#更新targets

现在来实现(3)，即：更新聚类中心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#更新聚类中心
new_centers=[]
for i in range(self.k):#对于每一个类中的全部样本点
    #此时target的取值集合是0到k-1
    
    #挑选出属于簇i的全部样本
    i_data=[]
    for index,item in enumerate(self.data):
        if self.targets[index]==i:
            i_data.append(item)
    if len(i_data)!=0:
        cent=[]#存储新的聚类中心的每一个维度
        for p in range(len(self.data[0])):#对于点的每一个维度
            sums=0

            #计算第i个簇中，每个维度的新值
            for x in i_data:
                sums+=x[p]
            res=sums/len(i_data)
            cent.append(res)
        new_centers.append(cent)
    else:
        new_centers.append(self.centers[i])#若某一个簇中所含样本数为0，则不更新该簇的中心点
self.centers=new_centers

注意这里需要判断某个簇中所含样本个数是否为0，因为当样本数为0时，上述代码求解均值所做的除法会报错。

为了避免这个错误，当出现这种情况时，我们选择本次不更新该簇的聚类中心。

以上便完成了(2)和(3)，注意到(4)中需要重复(2)和(3)这两个步骤，因此，我们可以将(2)和(3)封装到一个方法里面，就像这样：

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
def one_step(self):
    for i,item in enumerate(self.data):#对于每一个样本点
        c=[]#分别计算该样本点到k个聚类中心的距离，并存入c
        for j in range(len(self.centers)):
            c.append(self.cal_dist(item,self.centers[j]))
        #print(c)
        self.targets[i]=np.argmin(c)#更新targets

    #更新聚类中心
    new_centers=[]
    for i in range(self.k):#对于每一个类中的全部样本点
        #此时target的取值集合是0到k-1
        
        #挑选出属于簇i的全部样本
        i_data=[]
        for index,item in enumerate(self.data):
            if self.targets[index]==i:
                i_data.append(item)
        if len(i_data)!=0:
            cent=[]#存储新的聚类中心的每一个维度
            for p in range(len(self.data[0])):#对于点的每一个维度
                sums=0

                #计算第i个簇中，每个维度的新值
                for x in i_data:
                    sums+=x[p]
                res=sums/len(i_data)
                cent.append(res)
            new_centers.append(cent)
        else:
            new_centers.append(self.centers[i])#若某一个簇中所含样本数为0，则不更新该簇的中心点
    self.centers=new_centers

有了上面实现的这些方法，第(4)步的实现就很简单啦，直接来个for循环即可

1
2
3
4
5
6
7
def run(self,iterations):
    self.initialize()#初始化聚类中心和各样本所属类别
    #经过iterations次迭代，基本就完成了聚类
    for it in range(iterations):
        #print('iterations',it)
        self.one_step()
    return self.centers,self.targets

到这里，我们就完成了整个k-means算法，是时候测试一下效果了。

我们的训练数据是随机生成的，共100个样本，每个样本含2个特征。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import matplotlib.pyplot as plt
import numpy as np
if __name__ == '__main__':
    datasets=np.random.randint(0,100,size=(100,2))
    k=4#聚类数
    iterations=100#总迭代次数
    mykmeans=MyKmeans(k,datasets,True)#实例化
    centers,targets=mykmeans.run(iterations)#迭代求解
    
    #可视化聚类结果
    plt.scatter(datasets[:,0],datasets[:,1],c=targets)
    for center in centers:
        plt.scatter(center[0],center[1],marker='*',s=300)
        plt.text(center[0], center[1], (round(center[0],2),round(center[1],2)), fontsize=10, color = "r")
    plt.show()

聚类结果如下图所示
Alt text

现将完整的k-means实现代码汇总如下：

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
import numpy as np

class MyKmeans:
    def __init__(self,k,data,do_shuffle=False):
        self.k=k
        self.data=data
        self.do_shuffle=do_shuffle
    
    #计算欧氏距离
    def cal_dist(self,p1,p2):
        return np.sqrt(np.sum((p1-p2)**2))
    
    #初始化聚类中心和每个样本所属类别
    def initialize(self):
        if self.do_shuffle:
            np.random.shuffle(self.data)
        #初始化聚类中心
        self.centers=self.data[:self.k]
        #初始化每个样本所属簇
        self.targets=np.zeros(self.data.shape[0])
        
    def one_step(self):
        for i,item in enumerate(self.data):#对于每一个样本点
            c=[]#分别计算该样本点到k个聚类中心的距离，并存入c
            for j in range(len(self.centers)):
                c.append(self.cal_dist(item,self.centers[j]))
            #print(c)
            self.targets[i]=np.argmin(c)#更新targets

        #更新聚类中心
        new_centers=[]
        for i in range(self.k):#对于每一个类中的全部样本点
            #此时target的取值集合是0到k-1
            
            #挑选出属于簇i的全部样本
            i_data=[]
            for index,item in enumerate(self.data):
                if self.targets[index]==i:
                    i_data.append(item)
            if len(i_data)!=0:
                cent=[]#存储新的聚类中心的每一个维度
                for p in range(len(self.data[0])):#对于点的每一个维度
                    sums=0

                    #计算第i个簇中，每个维度的新值
                    for x in i_data:
                        sums+=x[p]
                    res=sums/len(i_data)
                    cent.append(res)
                new_centers.append(cent)
            else:
                new_centers.append(self.centers[i])#若某一个簇中所含样本数为0，则不更新该簇的中心点
        self.centers=new_centers
        
                   
    def run(self,iterations):
        self.initialize()#初始化聚类中心和各样本所属类别
        #经过iterations次迭代，基本就完成了聚类
        for it in range(iterations):
            #print('iterations',it)
            self.one_step()
        return self.centers,self.targets