python实现K-means算法（步骤详细）

左手的ㄟ右手 2023-03-14 05:59 1阅读 0赞

### 文章目录 ###

*  K-means 聚类算法
 *  代码实现
 *   *  实验目的
     *  实验步骤
     *   *   *  1. 数据准备
             *  2. KMeans算法实现
             *  3. 设置参数，调用函数，得到结果
     *  实验结果

# K-means 聚类算法 #

*  **特点**
    
     *  对初始化敏感。初始点选择的不同，可能会产生不同的聚类结果
     *  最终会收敛。不管初始点如何选择，最终都会收敛
 *  **算法思想**

选择K个点作为初始质心  
    repeat  
        将每个点指派到最近的质心，形成K个簇  
        重新计算每个簇的质心  
    until 簇不发生变化或达到最大迭代次数

# 代码实现 #

## 实验目的 ##

*  根据下列成绩单，将5名同学成绩归为A类、B类、C类。
 *  限制：使用Kmeans算法实现，但不直接调用sklearn第三方库的KMeans函数。

## 实验步骤 ##

#### 1. 数据准备 ####

*  将数据储存为csv文件，格式如下
    
        学生姓名,小测1,小测2,小测3,期末成绩,项目答辩
        张三,12,15,13,28,24
        李四,7,11,10,19,21
        王五,12,14,11,27,23
        赵六,6,7,4,13,20
        刘七,13,14,13,27,25
 *  在从csv文件中读取数据，并选取可用的数据（排除姓名列）
    
        data = pd.read_csv('grade.csv')
        new_data = data.iloc[:, 1:].values

#### 2. KMeans算法实现 ####

*  KMeans算法涉及两点之间距离的计算，我们提前写好一个函数：输入两个点的坐标，返回两点之间的欧氏距离
    
        def eucliDist(A, B):
            return math.sqrt(sum([(a - b) ** 2 for (a, b) in zip(A, B)]))
 *  函数`k_means(c,data,max,label)`实现KMeans算法：
    
    a. 输入：质心列表`c`，待聚类数据`data`，最大迭代次数`max`，标签列表`label`
    
    b. 计算data中的每个点分别到3个质心的欧式距离，得到一个矩阵`metrix`
    
        metrix = [[eucliDist(a, b) for a in data] for b in c]
    
    c. 比较矩阵`metrix`同一列的数值大小，将对应的学生划归距离较短的质心所属的类，将标签存储为列表.
    
        classifier = []
            for (d, e, f) in zip(metrix[0], metrix[1], metrix[2]):
                m = min(d, e, f)
                if d == m:
                    classifier.append(label[0])
                elif e == m:
                    classifier.append(label[1])
                else:
                    classifier.append(label[2])
    
    d. 重新计算质心的坐标，新质心的坐标=被划归同一类点的坐标的平均值
    
        n1, n2 = 0, 0
        c1 = [0, 0, 0, 0, 0]
        c2 = c1
        c3 = c1
            for i in range(0, num):
        
                if classifier[i] == label[0]:
                    c1 = [a + b for (a, b) in zip(c1, data[i])]
                    n1 = n1 + 1
                elif classifier[i] == label[1]:
                    c2 = [a + b for (a, b) in zip(c2, data[i])]
                    n2 = n2 + 1
                else:
                    c3 = [a + b for (a, b) in zip(c3, data[i])]
        
            c1 = [a / n1 for a in c1]
            c2 = [a / n2 for a in c2]
            c3 = [a / (num - n1 - n2) for a in c3]
    
    e. 重复b~d，直到质心坐标不再变化或达到最大迭代次数
    
    f. 返回标签列表
    
     *  完整函数如下
    
        def k_means(c, data, max,label):
            # a. 输入质心列表c，待聚类数据`data`，最大迭代次数max
            max = max - 1
            num = len(data)
            # b. 计算data中的每个点分到k个质心的距离，得到一个矩阵，如
            metrix = [[eucliDist(a, b) for a in data] for b in c]
            print(metrix)
            # c. 比较矩阵同一列的数值大小，将对应的学生划归距离较短的质心所属的类，将标签存储为列表
            classifier = []
            for (d, e, f) in zip(metrix[0], metrix[1], metrix[2]):
                m = min(d, e, f)
                if d == m:
                    classifier.append(label[0])
                elif e == m:
                    classifier.append(label[1])
                else:
                    classifier.append(label[2])
        
            print(classifier)
        
            # d. 重新计算质心的坐标，新质心的坐标=被划归同一类点的坐标的平均值
            n1, n2 = 0, 0
            c1 = [0, 0, 0, 0, 0]
            c2 = c1
            c3 = c1
            for i in range(0, num):
        
                if classifier[i] == label[0]:
                    c1 = [a + b for (a, b) in zip(c1, data[i])]
                    n1 = n1 + 1
                elif classifier[i] == label[1]:
                    c2 = [a + b for (a, b) in zip(c2, data[i])]
                    n2 = n2 + 1
                else:
                    c3 = [a + b for (a, b) in zip(c3, data[i])]
        
            c1 = [a / n1 for a in c1]
            c2 = [a / n2 for a in c2]
            c3 = [a / (num - n1 - n2) for a in c3]
        
            print(max)
            print([c1,c2,c3])
            # e. 重复b~d，直到质心坐标不再变化,或达到最大迭代次数
            if c != [c1, c2, c3] and max > 0:
        
                c = [c1, c2, c3]
                print(c)
                k_means(c, data, max, label)
            return classifier

#### 3. 设置参数，调用函数，得到结果 ####

*  设置初始质心、标签列表、最大迭代次数
    
        # 选择K个点作为初始质心
        c = [[12, 15, 13, 28, 24], [ 7, 11, 10, 19, 21],[12, 14, 11, 27, 23]]
        label = ['A', 'B', 'C']
        max = 20
 *  调用函数，整理结果
    
        grade = k_means(c, new_data, max, label)
        grade = pd.Series(grade, index=data['学生姓名'])
        print(grade)

## 实验结果 ##

*  初始质心为\[12, 15, 13, 28, 24\], \[ 7, 11, 10, 19, 21\],\[12, 14, 11, 27, 23\]时，迭代2次即收敛，结果如下