[Python数据挖掘] KMeans聚类算法原理底层实现

比眉伴天荒 2022-01-21 06:37 375阅读 0赞

**\[问题背景\]**

关于KMeans聚类原理的动画演示，我在B站的投稿《[Kmeans聚类原理 动画演示][Kmeans_]》中已作了介绍，有兴趣的朋友可以先看一下链接中的1分钟动画演示。

在[\[Python数据挖掘\] sklearn-KMeans聚类][Python_ sklearn-KMeans]一文中，我们调用sklearn库的KMeans聚类方法，成功对以下ANSI编码的grade.txt文本文档数据集进行了聚类：

YZN,133,108,76
    ZHY,96,145,101
    WYZ,132,107,60
    DHY,100,102,120
    CYH,139,99,93
    LHY,73,149,81
    ZHY,85,148,93
    TQP,39,138,85
    ZZL,145,112,71
    HJC,101,116,118
    XZY,99,98,117

**\[问题分析\]**

下面从底层实现的角度，只使用外部的random.sample和math.sqrt，无需使用numpy，逐步实现KMeans聚类算法。

完整代码如下：

针对grade.txt文本文档进行数据预处理并聚类的实例代码：

（grade.txt需要与代码的.py文件位于同一目录下）

from random import sample
    from math import sqrt
    
    # 函数名：means
    # 函数接口：大列表data
    # 函数功能：返回data大列表内所有点的平均点，是一个小列表
    def means(data):
        len_data = len(data)
        len_item = len(data[0])
        ret = []
        for j in range(len_item):
            ret_item = 0
            for i in range(len_data):
                ret_item += data[i][j]
            ret_item /= len_data
            ret.append(ret_item)
        return ret
    
    # 函数名：distance
    # 函数接口：两个数据点列表data1和data2
    # 函数功能：返回两个数据点的距离
    def distance(data1, data2):
        ret = 0
        for i in range(len(data1)):
            dif = data1[i] - data2[i]
            dif *= dif
            ret += dif
            # sqrt来自math
        ret = sqrt(ret)
        return ret
        
    # 函数名：kmeans
    # 函数接口：簇的数量n_clusters 数据列表data
    # 函数功能：返回标签labels列表
    def kmeans(n_clusters, data):
        # 簇中心列表
        centers = []
        labels = []
        len_data = len(data)
        for i in range(len_data):
            labels.append([])
    
        # 随机选择n_clusters个数据点作为初始簇中心
        # 其中sample来自random
        indexes = sample(range(0,len(data)),n_clusters)
        for i in range(n_clusters):
            centers.append(data[indexes[i]])
        len_centers = len(centers)
    
        flag = 1 # 标记簇中心是否发生变化，是为1，否为0
    
        while(flag == 1): # 如果簇中心发生变化，就继续迭代
    
            flag = 0 # 重置flag
            
            # 标签值 就是 最近簇中心标号
            # 将每个数据点与其最近的簇中心连接，将连接到同一簇中心的数据点聚为同一类（簇）
            for data_index in range(len_data):
                mindistance = float("inf") # 最近距离 初始值设置为无限大
                for center_index in range(len_centers):
                    dis = distance(data[data_index], centers[center_index])
                    if (dis < mindistance):
                        mindistance = dis
                        labels[data_index] = center_index
                    else:
                        pass
            
            # 每个簇的平均点作为新的簇中心
            for center_index in range(len_centers):
                same_label_data_list = []
                for data_index in range(len_data):
                    if (labels[data_index] == center_index):
                        same_label_data_list.append(data[data_index])
                if (centers[center_index] != means(same_label_data_list)):
                    centers[center_index] = means(same_label_data_list)
                    flag = 1
                else:
                    pass
        return labels
                
    # 数据预处理
    def loadData(filePath):
        fr = open(filePath, 'r+')
        lines = fr.readlines()
        retName = []
        retData = []
        for line in lines:
            items = line.strip().split(',')
            retName.append(items[0])
            retData.append([float(items[i]) for i in range(1,len(items))])
        return retName, retData
     
    if __name__ == '__main__':
        Name, Data = loadData('grade.txt')
        
        clusters_cnt = 3
        label = kmeans(clusters_cnt, Data)
        # print(label)
     
        outputName = []
        for i in range(clusters_cnt):
            outputName.append([])
        for i in range(len(Name)):
            outputName[label[i]].append(Name[i])
        print(outputName)

运行结果为：

[['ZHY', 'LHY', 'ZHY', 'TQP'], ['YZN', 'WYZ', 'CYH', 'ZZL'], ['DHY', 'HJC', 'XZY']]

可以看到，这一聚类结果与我们用sklearn的KMeans得到的聚类结果是一致的。本文代码的缺点是聚类结果不够稳定(即使增加轮数使标签取众数也不稳定)，但上述聚类结果占多数。如果读者知道如何像sklearn那样稳定聚类结果，还请读者不吝赐教。

Kmeans聚类函数的实现部分：

[Kmeans_]: https://b23.tv/av54650064
[Python_ sklearn-KMeans]: https://blog.csdn.net/swordtraveller/article/details/90726633