Python实现K-Means聚类算法

àì夳堔傛蜴生んèń 2021-09-17 09:34 323阅读 0赞

声明：代码的运行环境为Python3。Python3与Python2在一些细节上会有所不同，希望广大读者注意。本博客以代码为主，代码中会有详细的注释。相关文章将会发布在我的个人博客专栏[《Python从入门到深度学习》][Python]，欢迎大家关注~

--------------------

根据训练样本是否包含标签信息，机器学习可以分为监督学习和无监督学习（这里我们不考虑半监督学习）。聚类算法是典型的无监督学习算法，它是对事务自动归类的一种算法，在聚类算法中利用样本的标签，将具有相似属性的事物聚集到一类中。

**一、常用的相似性度量**

K-Means算法（K-均值算法）是基于相似性的无监督学习算法，即通过比较样本之间的相似性，将较为相似的样本划分到同一个类别中。为了度量两个样本（以样本X和样本Y为例）之间的相似性，通常会定义一个距离函数d(X,Y)，利用这个距离函数来定义样本X和样本Y之间的相似性。

1、闵可夫斯基距离

空间中两个点X，Y的坐标分别为：

![20181220202348823.png][]

那么，点X与点Y之间的闵可夫斯基距离可以定义为：

![201812202025269.png][]

2、曼哈顿距离

同样的两个点X，Y其曼哈顿距离可以表示为：

![20181220202702982.png][]

3、欧氏距离

同样的，点X与点Y的欧氏距离可以表示为：

![2018122020274923.png][]

由上面的定义可知，曼哈顿距离和欧式距离是闵可夫斯基距离的特殊形式。当p=1时，闵可夫斯基距离就是曼哈顿距离；当p=2时，闵可夫斯基距离就是欧式距离。在K-Means算法中，我们使用欧氏距离作为其相似性度量。因为欧氏距离的根号存在与否对其度量性没有影响，简单起见，我们使用欧氏距离的平方作为最终的相似性度量。

首先将需要加载相关的模块：

import numpy as np

欧氏距离的平方实现代码如下：

def distance(vecA, vecB):
        '''
        计算两个向量之间欧氏距离的平方
        :param vecA: 向量A的坐标
        :param vecB: 向量B的坐标
        :return: 返回两个向量之间欧氏距离的平方
        '''
        dist = (vecA - vecB) * (vecA - vecB).T
        return dist[0, 0]

**二、K-Means算法原理**

首先，我们需要人为的指定最终的聚类个数，假设我们最终的聚类个数为k个，即我们需要初始化k个聚类中心，通过计算每个样本与聚类中心的相似度，将样本点划分到距离最近的聚类中心。然后，通过每个类的样本重新计算每个类的聚类中心，重复这个操作直至聚类中心不再改变即为最终的聚类结果。

**三、K-Means算法步骤**

1、随机初始化K个聚类中心，其代码如下：

def randomCenter(data, k):
        '''
        随机初始化聚类中心
        :param data: 训练数据
        :param k: 聚类中心的个数
        :return: 返回初始化的聚类中心
        '''
        n = np.shape(data)[1]  # 特征的个数
        cent = np.mat(np.zeros((k, n)))  # 初始化K个聚类中心
        for j in range(n):  # 初始化聚类中心每一维的坐标
            minJ = np.min(data[:, j])
            rangeJ = np.max(data[:, j]) - minJ
            cent[:, j] = minJ * np.mat(np.ones((k, 1))) + np.random.rand(k, 1) * rangeJ  # 在最大值和最小值之间初始化
        return cent

2、计算每个样本与k个聚类中心的相似度，将样本划分到与之最相似的类中；

3、计算划分到每个类别中所有样本特征的均值，并将该均值作为每个类别新的聚类中心；

4、重复2、3步操作，直至聚类中心不再改变，输出最终的聚类中心。

构建K-Means算法的代码如下：

def kmeans(data, k, cent):
        '''
        kmeans算法求解聚类中心
        :param data: 训练数据
        :param k: 聚类中心的个数
        :param cent: 随机初始化的聚类中心
        :return: 返回训练完成的聚类中心和每个样本所属的类别
        '''
        m, n = np.shape(data)  # m：样本的个数；n：特征的维度
        subCenter = np.mat(np.zeros((m, 2)))  # 初始化每个样本所属的类别
        change = True  # 判断是否需要重新计算聚类中心
        while change == True:
            change = False  # 重置
            for i in range(m):
                minDist = np.inf  # 设置样本与聚类中心的最小距离，初始值为正无穷
                minIndex = 0  # 所属的类别
                for j in range(k):
                    # 计算i和每个聚类中心的距离
                    dist = distance(data[i, ], cent[j, ])
                    if dist < minDist:
                        minDist = dist
                        minIndex = j
                # 判断是否需要改变
                if subCenter[i, 0] != minIndex:  # 需要改变
                    change = True
                    subCenter[i, ] = np.mat([minIndex, minDist])
            # 重新计算聚类中心
            for j in range(k):
                sum_all = np.mat(np.zeros((1, n)))
                r = 0  # 每个类别中样本的个数
                for i in range(m):
                    if subCenter[i, 0] == j:  # 计算第j个类别
                        sum_all += data[i, ]
                        r += 1
                for z in range(n):
                    try:
                        cent[j, z] = sum_all[0, z] / r
                    except:
                        print("ZeroDivisionError: division by zero")
        return subCenter, cent

**四、K-Means算法举例**

1、数据集：数据集含有两个特征，如下图所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dka3l4eTIwMTM_size_16_color_FFFFFF_t_70][]

2、加载数据集

我们此处使用如下方法加载数据集，也可使用其他的方式进行加载，此处可以参考我的另外一篇文章[《Python两种方式加载文件内容》][Python 1]。加载文件内容代码如下：

def load_data(file_path):
        '''
        导入数据
        :param file_path: 文件路径
        :return: 以矩阵的形式返回导入的数据
        '''
        f = open(file_path)
        data = []
        for words in f.readlines():
            row = []  # 记录每一行
            word = words.strip().split("\t")
            for x in word:
                row.append(float(x))  # 将文本中的特征转换成浮点数
            data.append(row)
        f.close()
        return np.mat(data)  # 以矩阵的形式返回

3、保存聚类结果

通过K-Means聚类之后，我们可以使用如下方法保存聚类结果：

def save_result(file_name, data):
        '''
        保存source中的结果到file_name文件中
        :param file_name: 保存的文件名
        :param data: 需要保存的数据
        :return:
        '''
        m, n = np.shape(data)
        f = open(file_name, "w")
        for i in range(m):
            tmp = []
            for j in range(n):
                tmp.append(str(data[i, j]))
            f.write("\t".join(tmp) + "\n")
        f.close()

4、调用K-Means算法

调用K-Means算法：

if __name__ == "__main__":
        k = 4  # 聚类中心的个数
        file_path = "tfidf.txt"
        subCenter, center = kmeans(load_data(file_path), k, randomCenter(load_data(file_path), k))
        save_result("result/kmeans_sub", subCenter)
        save_result("result/kmeans_center", center)

5、结果展示

得到的聚类结果如图所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dka3l4eTIwMTM_size_16_color_FFFFFF_t_70 1][]

你们在此过程中遇到了什么问题，欢迎留言，让我看看你们都遇到了哪些问题。

[Python]: https://blog.csdn.net/gdkyxy2013/column/info/22367
[20181220202348823.png]: /images/20210726/871673d03b7c40fe99817698d15d82bf.png
[201812202025269.png]: /images/20210726/edf173046f4e4ce2a9a2d180dbe7f9a7.png
[20181220202702982.png]: /images/20210726/dab70f59727c4a52a3e0e184d2e1651b.png
[2018122020274923.png]: /images/20210726/5a37e623051c4c07acbc7c81931f666d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dka3l4eTIwMTM_size_16_color_FFFFFF_t_70]: /images/20210726/684f8485f44c46d8a18ee06fe73272d9.png
[Python 1]: https://blog.csdn.net/gdkyxy2013/article/details/81979214
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dka3l4eTIwMTM_size_16_color_FFFFFF_t_70 1]: /images/20210726/81ba3f18cb0a4db89e0d3eaa48b945d7.png