【强基固本】Kmeans 聚类算法

“强基固本，行稳致远”，科学研究离不开理论基础，人工智能学科更是需要数学、物理、神经科学等基础学科提供有力支撑，为了紧扣时代脉搏，我们推出“强基固本”专栏，讲解AI领域的基础知识，为你的科研学习提供助力，夯实理论基础，提升原始创新能力，敬请关注。

来源：知乎—凌晨伴太阳

地址：https://zhuanlan.zhihu.com/p/150515679

01

什么是聚类

聚类可以将相似的样本归到同一簇中，是无监督学习中最常见的问题。聚类的结果是，簇内的对象越相似，聚类的效果就越好。一个簇的意思就是一个类别。

以人学习习题为例，仔细观察习题，就会发现高频出现运算符号的题目是数学题，高频出现英文字母的题目是英语题。如下图，这种将相似样本归到同一簇中的过程，并不依赖标准答案，这就是聚类。

聚类算法中，最经典的就是Kmeans 聚类了，也叫作 K 均值聚类，是最常用的聚类算法。

Kmeans 算法中的 K 表示的是，将样本聚为 K 个簇；Means 代表取每一个聚类中数据值的均值作为该簇的中心，或者称为质心。Kmeans 聚类算法，可以将输入数据聚合成 K 个簇并输出。

02

Kmeans 聚类算法

Kmeans聚类算法输入的内容包括，聚类目标 K 值和样本的集合。

执行算法的第一步是初始化。通常采用的策略是，在特征空间中，随机选 K 个点作为初始的质心。

第二步是归类和更新。具体来说，归类是对数据集中每个点而言，计算其与每个质点之间的距离，并将数据点分配到距离最近的质点所在的簇。更新是对每一个簇而言，计算簇中所有点的均值，并将均值作为新的质心替换掉原来的质心。

之后呢，就需要重复执行归类和更新的操作，直到某些停止条件满足。

Kmeans 算法的停止条件通常有以下 4 个，一般任意满足一点即可停止算法的主流程：

1）预先设置好迭代的轮数，一旦超过了迭代的最大轮数则停止迭代；

2）在某次循环中，没有数据点被重新分配到其他的簇，也就是算法已经收敛，则算法结束迭代；

3）某次循环，质心的位置没有发生改变，也是算法发生了收敛，则算法结束迭代；

4）某次循环，均方误差 SSE 递减的增量，小于预先设置的某个阈值，也就是这一次的迭代对聚类结果影响非常小，算法已经趋近于收敛，则算法结束迭代。SSE 的计算公式如下：

其中，K 表示 K 个簇，Cj 为簇 j 内数据样本的集合，mj 表示 Cj 簇的质心。这个公式的意思是，对每个簇计算每个数据点与其所归属的质心的距离平方和，再将所有簇的结果求和。随着 Kmeans 不断迭代，SSE 的值在不断的缩小，直到某次迭代，这个减小的幅度可被忽略。

接下来我们看一个例题，来实际用一下 Kmeans 聚类算法。

假设样本集合为 (0.1, 0.9)、(0.2, 0.8)、(0.1, 0.8)、(0.9, 0.3)、(0.9, 0.2)、(0.8, 0.1)，设置 K 为 2，采用 Kmeans 聚类算法对样本集合进行聚类。根据算法流程，首先随机初始化两个质心，假设为 (0.5, 0.5) 和 (0.4, 0.3)，此时样本集合（图中蓝色圆点）以及质心（图中红色、绿色方块）如下图：

对每个样本点，计算其与每个质点的距离，并归至距离近的簇中。在这里，我们选取欧式距离作为距离函数。也就是：

结果，(0.8, 0.1) 被归至绿色的簇，其余点被归至红色的簇。利用每个簇数据点的均值，替换上一轮的质心，则有下图：

重复上面的过程，发现红色簇有两个数据点发生了簇跳变，被重新归位绿色簇中，此时两个质心再次发生改变。见下图：

再次重复上面的过程，发现没有数据点的簇标签发生变化，则算法结束计算。最终结果如下图，其中数据点被聚为两个簇中，分别用红色和绿色标记，每个簇的质心用对应颜色的方块表示：

03

Kmeans聚类算法的优缺点

Kmeans 算法的优势在于简单易懂、便于实现。Kmeans 算法非常简单，上面的内容已经将它的核心流程和示例描述得清楚明了。在运用过程中，即使不使用公开的工具包，自行编码开发，也只不过是体力劳动而已。

既然这个算法简单容易，其实也就决定了它的缺陷和不足。根据经验，Kmeans 算法至少存在 4 个明显的缺陷。

首先，K 是输入参数，没有一套自适应的计算方法，需要依赖人工经验。如果 K 给的不好，则结果质量很难保证。

其次，Kmeans 聚类算法对离群点很敏感。质心的更新，依靠的是全部簇内数据点的平均值。如果样本集合中存在某个离群点，可能会导致质心平均值计算偏差很大，而影响结果。

第三，Kmeans 聚类算法对初始质心很敏感。如果初始质心给的不好，很有可能出现意想不到的结果。

最后，如果样本点的分布不是凸的，Kmeans 聚类算法有可能出现错误的结果。这种情况一旦发生，是很难被发现的，如下图：

聚类问题是无监督学习的代表性问题之一，Kmeans 算法是最常见的聚类算法。Kmeans 算法简单易懂、便于实现，在项目初期的数据分析中，能帮助发现数据背后的规律，发挥了巨大作用。但由于其存在至少 4 个明显的缺陷，造成了其结果的不可控，因此通常在实际工程中不会高频使用。

04

最优k值的选取：（手肘法）

手肘法的核心指标是SSE(sum of the squared errors，误差平方和)

其中，Ci是第i个簇，p是Ci中的样本点，mi是Ci的质心（Ci中所有样本的均值），SSE是所有样本的聚类误差，代表了聚类效果的好坏。

手肘法的核心思想是：随着聚类数k的增大，样本划分会更加精细，每个簇的聚合程度会逐渐提高，那么误差平方和SSE自然会逐渐变小。并且，当k小于真实聚类数时，由于k的增大会大幅增加每个簇的聚合程度，故SSE的下降幅度会很大，而当k到达真实聚类数时，再增加k所得到的聚合程度回报会迅速变小，所以SSE的下降幅度会骤减，然后随着k值的继续增大而趋于平缓，也就是说SSE和k的关系图是一个手肘的形状，而这个肘部对应的k值就是数据的真实聚类数。当然，这也是该方法被称为手肘法的原因。

05

代码示例

import jieba
from sklearn.feature_extraction.text import CountVectorizer
from sklearn.feature_extraction.text import TfidfTransformer
from sklearn.cluster import KMeans
import matplotlib.pyplot as plt
from sklearn.decomposition import PCA


class KmeansClustering():
    def __init__(self, stopwords_path=None):
        self.stopwords = self.load_stopwords(stopwords_path)
        self.vectorizer = CountVectorizer()
        self.transformer = TfidfTransformer()

    def load_stopwords(self, stopwords=None):
        """
        加载停用词
        :param stopwords:
        :return:
        """
        if stopwords:
            with open(stopwords, 'r', encoding='utf-8') as f:
                return [line.strip() for line in f]
        else:
            return []

    def preprocess_data(self, corpus_path):
        """
        文本预处理，每行一个文本
        :param corpus_path:
        :return:
        """
        corpus = []
        with open(corpus_path, 'r', encoding='utf-8') as f:
            for line in f:
                corpus.append(' '.join([word for word in jieba.lcut(line.strip()) if word not in self.stopwords]))
        return corpus

    def get_text_tfidf_matrix(self, corpus):
        """
        获取tfidf矩阵
        :param corpus:
        :return:
        """
        tfidf = self.transformer.fit_transform(self.vectorizer.fit_transform(corpus))

        # 获取词袋中所有词语
        # words = self.vectorizer.get_feature_names()

        # 获取tfidf矩阵中权重
        weights = tfidf.toarray()
        return weights

    def pca(self, weights, n_components=2):
        """
        PCA对数据进行降维
        :param weights:
        :param n_components:
        :return:
        """
        pca = PCA(n_components=n_components)
        return pca.fit_transform(weights)

    def kmeans(self, corpus_path, n_clusters=5, fig=True):
        """
        KMeans文本聚类
        :param corpus_path: 语料路径（每行一篇）,文章id从0开始
        :param n_clusters: ：聚类类别数目
        :return: {cluster_id1:[text_id1, text_id2]}
        """
        corpus = self.preprocess_data(corpus_path)
        weights = self.get_text_tfidf_matrix(corpus)
        pca_weights = self.pca(weights)
        clf = KMeans(n_clusters=n_clusters)

        # clf.fit(weights)

        y = clf.fit_predict(weights)
        if fig:
            plt.scatter(pca_weights[:, 0], pca_weights[:, 1], c=y)
            plt.show()

        # 中心点
        centers = clf.cluster_centers_
        print('中心点', centers)
        # 用来评估簇的个数是否合适,距离约小说明簇分得越好,选取临界点的簇的个数
        score = clf.inertia_
        print("评估簇的个数是否合适", score)
        # 每个样本所属的簇
        result = {}
        for text_idx, label_idx in enumerate(y):
            if label_idx not in result:
                result[label_idx] = [text_idx]
            else:
                result[label_idx].append(text_idx)
        return result

    def elbow_algorithm(self, corpus_path, n_clusters_iterations=12):
        """
        肘部算法  确定最优聚类类别数目
        :param n_clusters_iterations: 聚类类别数目
        :param corpus_path: 语料路径（每行一篇）,文章id从0开始
        :return:
        """
        corpus = self.preprocess_data(corpus_path)
        weights = self.get_text_tfidf_matrix(corpus)
        SSE = []  # 存放每次结果的误差平方和
        for k in range(1, n_clusters_iterations):
            clf = KMeans(n_clusters=k)  # 构造聚类器
            clf.fit(weights)
            SSE.append(clf.inertia_)  # clf.inertia_获取聚类准则的总和（用来评估簇的个数是否合适,距离约小说明簇分得越好,选取临界点的簇的个数）
        X = range(1, n_clusters_iterations)
        plt.xlabel('k')
        plt.ylabel('SSE')
        plt.plot(X, SSE, 'o-')
        plt.show()

if __name__ == '__main__':
     Kmeans = KmeansClustering(stopwords_path='./data/stop_words.txt')
     # 肘部算法  确定 簇的最优
     Kmeans.elbow_algorithm('./data/test_data.txt',24)
     
     result = Kmeans.kmeans('./data/test_data.txt', n_clusters=18)

本文目的在于学术交流，并不代表本公众号赞同其观点或对其内容真实性负责，版权归原作者所有，如有侵权请告知删除。

“强基固本”历史文章

更多强基固本专栏文章，

请点击文章底部“阅读原文”查看

分享、点赞、在看，给个三连击呗！