python实现K均值聚类算法

之前做大作业的时候本来想用聚类法给点集分类的，但是太复杂了，于是最后没有采用这个方案。现在把之前做的一些工作整理出来写个小博客。

K-means聚类法原理：

聚类是一个将数据集中在某些方面相似的数据成员进行分类组织的过程，聚类就是一种发现这种内在结构的技术，聚类技术经常被称为无监督学习。

K-Means算法的思想很简单，对于给定的样本集，按照样本之间的距离大小，将样本集划分为K个簇。让簇内的点尽量紧密的连在一起，而让簇间的距离尽量的大。

如何计算？

如果用数据表达式表示，假设簇划分为 ( C 1 , C 2 , . . . C k ) ({C_1},{C_2},...{C_k}) (C1​,C2​,...Ck​)，则我们的目标是最小化平方误差E：
E = ∑ i = 1 k ∑ x ∈ C i ∥ x − μ i ∥ 2 2 E = \sum\limits_{i = 1}^k {\sum\limits_{x \in {C_i}} {\left\| {x - {\mu _i}} \right\|_2^2} } E=i=1∑k​x∈Ci​∑​∥x−μi​∥22​
其中 μ i μ_i μi​是簇 C i C_i Ci​的均值向量，有时也称为质心，表达式为：
μ i = 1 ∣ C i ∣ ∑ x ∈ C i x {\mu _i} = \frac{1}{{\left| {{C_i}} \right|}}\sum\limits_{x \in {C_i}} x μi​=∣Ci​∣1​x∈Ci​∑​x
如果我们想直接求上式的最小值并不容易，这是一个NP难的问题，因此只能采用启发式的迭代方法。
下图是K均值聚类法的一个示意图：

上图a表达了初始的数据集，假设k=2。在图b中，我们随机选择了两个k类所对应的类别质心，即图中的红色质心和蓝色质心，然后分别求样本中所有点到这两个质心的距离，并标记每个样本的类别为和该样本距离最小的质心的类别，如图c所示，经过计算样本和红色质心和蓝色质心的距离，我们得到了所有样本点的第一轮迭代后的类别。此时我们对我们当前标记为红色和蓝色的点分别求其新的质心，如图4所示，新的红色质心和蓝色质心的位置已经发生了变动。图e和图f重复了我们在图c和图d的过程，即将所有点的类别标记为距离最近的质心的类别并求新的质心。最终我们得到的两个类别如图f。

当然在实际K-Mean算法中，我们一般会多次运行图c和图d，才能达到最终的比较优的类别。

我的解决方案是在代码中使用的是循环10次（可调），选择总距离最小的那个方案。

代码部分：

class KMeansClusterer:  # k均值聚类
    def __init__(self, ndarray, cluster_num):
        self.ndarray = ndarray
        self.cluster_num = cluster_num
        self.points = self.__pick_start_point(ndarray, cluster_num)

    def cluster(self):
        result = []
        for i in range(self.cluster_num):
            result.append([])
        for item in self.ndarray:
            distance_min = sys.maxsize
            index = -1
            for i in range(len(self.points)):
                distance = self.__distance(item, self.points[i])
                if distance < distance_min:
                    distance_min = distance
                    index = i
            result[index] = result[index] + [item.tolist()]
        new_center = []
        for item in result:
            new_center.append(self.__center(item).tolist())
        # 中心点未改变，说明达到稳态，结束递归
        if (self.points == new_center).all():
            sum=self.__sumdis(result)
            return result,self.points,sum
        self.points = np.array(new_center)
        return self.cluster()

    def __sumdis(self,result):
        #计算总距离和
        sum=0
        for i in range(len(self.points)):
            for j in range(len(result[i])):
                sum+=self.__distance(result[i][j],self.points[i])
        return sum

    def __center(self, list):
        # 计算每一列的平均值
        return np.array(list).mean(axis=0)

    def __distance(self, p1, p2):
        #计算两点间距
        tmp = 0
        for i in range(len(p1)):
            tmp += pow(p1[i] - p2[i], 2)
        return pow(tmp, 0.5)

    def __pick_start_point(self, ndarray, cluster_num):
        if cluster_num < 0 or cluster_num > ndarray.shape[0]:
            raise Exception("簇数设置有误")
        # 取点的下标
        indexes = random.sample(np.arange(0, ndarray.shape[0], step=1).tolist(), cluster_num)
        points = []
        for index in indexes:
            points.append(ndarray[index].tolist())
        return np.array(points)

运行结果如下：

结果如上图所示，这是之前大作业得到的点集，不同颜色的点分属于不同类型的点集，五角星为每个点集的中心点。

调用函数后得到的是点集以及总距离。代码使用示例我放在资源包里，有需要自取。