极客时间已完结课程限时免费阅读

36 | 文本聚类：如何过滤冗余的新闻？

36 | 文本聚类：如何过滤冗余的新闻？-极客时间

36 | 文本聚类：如何过滤冗余的新闻？

2019-03-08 黄申 来自北京
《程序员的数学基础课》
课程介绍

讲述：黄申

时长09:55大小9.09M

你好，我是黄申。
前两节，我讲了向量空间模型，以及如何在信息检索领域中运用向量空间模型。向量空间模型提供了衡量向量之间的距离或者相似度的机制，而这种机制可以衡量查询和被查询数据之间的相似程度，而对于文本检索来说，查询和文档之间的相似程度可作为文档的相关性。
实际上，除了文档的相关性，距离或者相似度还可以用在机器学习的算法中。今天，我们就来聊聊如何在聚类算法中使用向量空间模型，并最终实现过滤重复文章。

聚类算法

在概率统计模块中，我们介绍了分类（Classification/Categorization）和回归（Regression）这两种监督式学习（Supervised Learning）。监督式学习通过训练资料学习并建立一个模型，并依此模型对新的实例进行预测。
不过，在实际场景中，我们常常会遇到另一种更为复杂的情况。这时候不存在任何关于样本的先验知识，而是需要机器在没人指导的情形下，去将很多东西进行归类。由于缺乏训练样本，这种学习被称为“非监督学习”（Unsupervised Learning），也就是我们通常所说的聚类（Clustering）。在这种学习体系中，系统必须通过一种有效的方法发现样本的内在相似性，并把数据对象以群组（Cluster）的形式进行划分。
谈到相似性，你可能已经想到了利用特征向量和向量空间模型，这确实是可行的方法。不过，为了让你全面了解在整个非监督式学习中，如何运用向量空间，让我先从一个具体的聚类算法开始。
这个算法的名称是 K 均值（K-Means）聚类算法，它让我们可以在一个任意多的数据上，得到一个事先定好群组数量（K）的聚类结果。这种算法的中心思想是：尽量最大化总的群组内相似度，同时尽量最小化群组之间的相似度。群组内或群组间的相似度，是通过各个成员和群组质心相比较来确定的。想法很简单，但是在样本数量达到一定规模后，希望通过排列组合所有的群组划分，来找到最大总群组内的相似度几乎是不可能的。于是人们提出如下的求近似解的方法。
从 N 个数据对象中随机选取 k 个对象作为质心，这里每个群组的质心定义是，群组内所有成员对象的平均值。因为是第一轮，所以第 i 个群组的质心就是第 i 个对象，而且这时候我们只有这一个组员。
对剩余的对象，测量它和每个质心的相似度，并把它归到最近的质心所属的群组。这里我们可以说距离，也可以说相似度，只是两者呈现反比关系。
重新计算已经得到的各个群组的质心。这里质心的计算是关键，如果使用特征向量来表示的数据对象，那么最基本的方法是取群组内成员的特征向量，将它们的平均值作为质心的向量表示。
迭代上面的第 2 步和第 3 步，直至新的质心与原质心相等或相差之值小于指定阈值，算法结束。
我以二维空间为例子，画张图来展示一下数据对象聚类的过程。
在这张图中，( a )、( b )、( c ) 三步分别展示了质心和群组逐步调整的过程。我们一一来看。(a) 步骤是选择初始质心，质心用不同颜色的 x 表示；( b ) 步骤开始进行聚类，把点分配到最近的质心所在的组；( c ) 步骤重新计算每个群组的质心，你会发现 x 的位置发生了改变。之后就是如此重复，进入下一轮聚类。
总的来说，K 均值算法是通过不断迭代、调整 K 个聚类质心的算法。而质心或者群组的中心点，是通过求群组所包含的成员之平均值来计算的。

使用向量空间进行聚类

明白了 K 均值聚类算法的核心思想，再来理解向量空间模型在其中的运用就不难了。我还是以文本聚类为例，讲讲如何使用向量空间模型和聚类算法，去除重复的新闻。
我们在看新闻的时候，一般都希望不断看到新的内容。可是，由于现在的报道渠道非常丰富，经常会出现热点新闻霸占版面的情况。假如我们不想总是看到重复的新闻，应该怎么办呢？有一种做法就是对新闻进行聚类，那么内容非常类似的文章就会被聚到同一个分组，然后对每个分组我们只选择 1 到 2 篇显示就够了。
基本思路确定后，我们可以把整个方法分为三个主要步骤。
第一步，把文档集合都转换成向量的形式。这块我上一节讲过了，你要是不记得了，可以自己回去复习一下。
第二步，使用 K 均值算法对文档集合进行聚类。这个算法的关键是如何确定数据对象和分组质心之间的相似度。针对这点，我们有两个点需要关注。
使用向量空间中的距离或者夹角余弦度量，计算两个向量的相似度。
计算质心的向量。K 均值里，质心是分组里成员的平均值。所以，我们需要求分组里所有文档向量的平均值。求法非常直观，就是分别为每维分量求平均值，我把具体的计算公式列在这里：
其中， 表示向量的第 i 个分量， 表示第 j 个向量的第 个分量，而 表示属于某个分组的所有向量。
第三步，在每个分类中，选出和质心最接近的几篇文章作为代表。而其他的文章作为冗余的内容过滤掉。
下面，我使用 Python 里的 sklearn 库，来展示使用欧氏距离的 K 均值算法。

Python 中的 K 均值算法

在尝试下面的代码之前，你需要看看自己的机器上是不是已经安装了 scikit-learn。Scikit-learn 是 Python 常用的机器学习库，它提供了大量的机器学习算法的实现和相关的文档，甚至还内置了一些公开数据集，是我们实践机器学习算法的好帮手。
首先，我使用 sklearn 库中的 CountVectorizer，对一个测试的文档集合构建特征，也就是词典。这个测试集合有 7 句话，2 句关于篮球，2 句关于电影，还有 3 句关于游戏。具体代码如下：
from sklearn.feature_extraction.text import CountVectorizer
#模拟文档集合
corpus = ['I like great basketball game',
'This video game is the best action game I have ever played',
'I really really like basketball',
'How about this movie? Is the plot great?',
'Do you like RPG game?',
'You can try this FPS game',
'The movie is really great, so great! I enjoy the plot']
#把文本中的词语转换为词典和相应的向量
vectorizer = CountVectorizer()
vectors = vectorizer.fit_transform(corpus)
#输出所有的词条（所有维度的特征）
print('所有的词条（所有维度的特征）')
print(vectorizer.get_feature_names())
print('\n')
#输出(文章ID, 词条ID) 词频
print('(文章ID, 词条ID) 词频')
print(vectors)
print('\n')
从运行的结果中，你可以看到，整个词典里包含了哪些词，以及每个词在每个文档里的词频。
这里，我们希望使用比词频 tf 更好的 tf-idf 机制，TfidfTransformer 可以帮助我们做到这点，代码和注释如下：
from sklearn.feature_extraction.text import TfidfTransformer
#构建tfidf的值
transformer = TfidfTransformer()
tfidf = transformer.fit_transform(vectorizer.fit_transform(corpus))
# 输出每个文档的向量
tfidf_array = tfidf.toarray()
words = vectorizer.get_feature_names()
for i in range(len(tfidf_array)):
print ("*********第", i + 1, "个文档中，所有词语的tf-idf*********")
# 输出向量中每个维度的取值
for j in range(len(words)):
print(words[j], ' ', tfidf_array[i][j])
print('\n')
运行的结果展示了每个文档中，每个词的 tfidf 权重，你可以自己手动验算一下。
最后，我们就可以进行 K 均值聚类了。由于有篮球、电影和游戏 3 个类别，我选择的 K 是 3，并在 KMeans 的构造函数中设置 n_clusters 为 3。
from sklearn.cluster import KMeans
#进行聚类，在我这个版本里默认使用的是欧氏距离
clusters = KMeans(n_clusters=3)
s = clusters.fit(tfidf_array)
#输出所有质心点，可以看到质心点的向量是组内成员向量的平均值
print('所有质心点的向量')
print(clusters.cluster_centers_)
print('\n')
#输出每个文档所属的分组
print('每个文档所属的分组')
print(clusters.labels_)
#输出每个分组内的文档
dict = {}
for i in range(len(clusters.labels_)):
label = clusters.labels_[i]
if label not in dict.keys():
dict[label] = []
dict[label].append(corpus[i])
else:
dict[label].append(corpus[i])
print(dict)
为了帮助你的理解，我输出了每个群组的质心，也就是其中成员向量的平均值。最后，我也输出了 3 个群组中所包含的句子。在我机器上的运行结果显示，系统可以把属于 3 个话题的句子区分开来。如下所示：
{2: ['I like great basketball game', 'I really really like basketball'], 0: ['This video game is the best action game I have ever played', 'Do you like RPG game?', 'You can try this FPS game'], 1: ['How about this movie? Is the plot great?', 'The movie is really great, so great! I enjoy the plot']}
不过，由于 KMeans 具体的实现可能不一样，而且初始质心的选择也有一定随机性，所以你看到的结果可能稍有不同。

总结

这一节，我介绍了如何在机器学习的聚类算法中，使用向量空间模型。在聚类中，数据对象之间的相似度是很关键的。如果我们把样本转换为向量，然后使用向量空间中的距离或者夹角余弦，就很自然的能获得这种相似度，所以向量空间模型和聚类算法可以很容易的结合在一起。
为了给你加深印象，我介绍了一个具体的 K 均值算法，以及向量空间模型在其中所起到的作用，并通过 Python 的 sklearn 代码演示了几个关键的步骤。
向量空间模型和 K 均值算法的结合，虽然简单易懂，但是一开始怎样选择这个群组的数量，是个关键问题。我今天演示的测试数据很小，而且主题划分的也非常明显。所以我选择聚类的数量为 3。
可是在实际项目中，对于一个新的数据集合，选择多少比较合适呢？如果这个 K 值取得太大，群组可能切分太细，每个之间区别不大。如果 K 值取得太小，群组的粒度又太粗，造成群组内差异比较明显。对非监督式的学习来说，这个参数确实难以得到准确预估。我们可以事先在一个较小的数据集合上进行尝试，然后根据结果和应用场景确定一个经验值。

思考题

今天我使用的是 sklearn 里的 KMeans 包，它使用了向量间的欧氏距离来进行聚类。你可以尝试实现自己的 K 均值聚类，并使用向量间的夹角余弦作为相似度的度量。
欢迎留言和我分享，也欢迎你在留言区写下今天的学习笔记。你可以点击“请朋友读”，把今天的内容分享给你的好友，和他一起精进。
分享给需要的人，Ta购买本课程，你将得20元
生成海报并分享

赞 3

提建议

© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
上一篇
35 | 文本检索：如何让计算机处理自然语言？
下一篇
37 | 矩阵（上）：如何使用矩阵操作进行PageRank计算？
unpreview
 写留言

精选留言(12)

  • Joe
    2019-03-15
    def customKmeans(vec_array, n_clusters=3, epochs=50): ''' @description: 手动实现kmeans，以向量间的夹角余弦作为相似度 根据上述tf-idf得到的7条文本向量tfidf_array，进行聚类算法 @param {type} vec_array- 向量组, n_clusters-聚类数目, epochs- 训练次数 @return: cluster_labels- 分类标签 ''' # 初始化质心的位置 cluster_centers = [] cluster_centers_indx = [] while (len(cluster_centers_indx) < n_clusters): indx = random.randint(0, len(vec_array)-1) if indx not in cluster_centers_indx: cluster_centers_indx.append(indx) cluster_centers.append(vec_array[indx]) # 初始化向量类别 cluster_labels = [0] * len(vec_array) max_similarity = [-1] * len(vec_array) epoch = 0 while(epoch < epochs): # 计算每个向量与质心的相似性，并将其归纳到最近的质心集群中 for i in range(0, len(vec_array)): max_similarity[i] = computeCosine(vec_array[i], cluster_centers[0]) for j in range(1, n_clusters): temp = computeCosine(vec_array[i], cluster_centers[j]) if (temp > max_similarity[i]): max_similarity[i] = temp cluster_labels[i] = j # 更新质心位置 for i in range(0, n_clusters): # 找到集群对应原向量的下标 indxs = [indx for indx, cluster in enumerate( cluster_labels) if cluster == i] # 根据集群向量的平均值更新质点位置 cluster_centers[i] = np.average( [vec_array[indx] for indx in indxs], axis=0) # 当满足迭代次数或平均最大相似性时退出算法 epoch += 1 if (np.average(max_similarity) > 0.9): break return cluster_labels def computeCosine(vec1, vec2): # 计算向量间的余弦值 vecCosine = np.dot(vec1, vec2) / \ (np.linalg.norm(vec1) * np.linalg.norm(vec2)) return vecCosine # 应用customkmeans labels = customKmeans(tfidf_array, n_clusters=3, epochs=1000) print(labels) 输出结果： [0 2 0 1 2 2 1]
    展开
    6
  • mickey
    2019-03-08
    # encoding=utf-8 from sklearn.feature_extraction.text import CountVectorizer #模拟文档集合 corpus = ['I like great basketball game', 'This video game is the best action game I have ever played', 'I really really like basketball', 'How about this movie? Is the plot great?', 'Do you like RPG game?', 'You can try this FPS game', 'The movie is really great, so great! I enjoy the plot'] #把文本中的词语转换为词典和相应的向量 vectorizer = CountVectorizer() vectors = vectorizer.fit_transform(corpus) from sklearn.feature_extraction.text import TfidfTransformer #构建tfidf的值 transformer = TfidfTransformer() tfidf = transformer.fit_transform(vectorizer.fit_transform(corpus)) # 输出每个文档的向量 tfidf_array = tfidf.toarray() words = vectorizer.get_feature_names() from Bio.Cluster import kcluster #进行聚类，使用向量间的夹角余弦作为相似度的度量 clusterid, error, nfound = kcluster(tfidf_array, nclusters=3, dist='u') print(clusterid) ''' Kmeans 的欧式距离:[0 2 0 1 2 2 1] Bio 的夹角余弦:[2 0 0 2 0 2 1] '''
    展开

    作者回复: 尝试了不同的方法👍

    共 2 条评论
    6
  • 余泽锋
    2019-04-09
    请问一下老师，余弦夹角本质上可以说是归一化的欧式距离么？

    作者回复: 可以这么认为

    共 2 条评论
    5
  • 罗耀龙@坐忘
    2020-04-28
    茶艺师学编程 K—Means算法，给我的感觉，就像是在铺满铁屑的纸上放几个磁铁，附近的铁屑会吸过来。 向量空间模型则是换上更强力的“磁铁”。 …… “什么还有没有吸过来的铁屑，那就不用管了”
    展开
    共 2 条评论
    2
  • Joe
    2019-03-14
    老师，现在很多机器学习的算法都有现成的库了，如sklearn等。但是直接调库，总觉得停留在表面。请问有没有必要自己手动去实现一些经典的机器学习算法呢？

    作者回复: 这是一个好问题，可以参照专栏中的一些介绍，尝试实现某些算法，加强印象，甚至于将来可以根据具体的应用，对算法实现进行优化。

    共 2 条评论
    2
  • zhengfan
    2020-06-02
    黄老师您好。 您在k均值算法介绍后附的图示，似乎呈现出“恰巧把初选质心点选在了不同群组中”的效果。而作为k均值算法的第一步，最初质心的选择是完全随机的。也就是很有可能这些初选质心是在同一个群组中。请问这种情况如何处理？

    作者回复: 很好的问题，作为非监督式学习，这是个很大的缺陷，实际运用中通常试验不同的初始值，或者采用层次化聚类，先细分很多小的类，然后根据相似度进行聚集

    1
  • Paul Shan
    2019-09-26
    kmeans方法用的是利用几何信息将空间点归类的方法，最终的结果是归好类的点集质心之间的距离远，但是集合内点之间距离近的效果，可以类比于软件开发中的高内聚低耦合原则来记忆。

    作者回复: 嗯，这个比喻好👍

    1
  • Bindy🌲
    2019-04-10
    老师，这里如果是中文，是不是要做分词呢

    作者回复: 是的，如果是中文，肯定要做分词的。

    1
  • 013923
    2022-09-14 来自上海
    Keep fit；Study well，and Work hard！
  • 建强
    2020-09-23
    我自己写了一个用向量夹角的余弦做聚类的算法，但不论怎么调整，聚类结果和欧氏距离算法都不一样，是不是和初始质心选择有关，还是程序中的算法有问题，需要请教老师，篇幅有限，部分程序代码如下： # 用样本拟合聚类算法模型 def fit(self, sample_matrix): #检查分类个数是否大于待分类的样本数 if self.n_clusters > len(sample_matrix): raise ValueError('cluster numbers must less than or equal to sample numbers') # 初始化质心，取前n个样本的向量作为质心 self.cluster_centers_ = np.array([sample_matrix[0]]) for j in range(1, self.n_clusters): self.cluster_centers_ = np.r_[self.cluster_centers_, [sample_matrix[j]]] # 迭代计算各样本与质心的夹角，并更新分组，直到新质心与旧质心之间的差距小于指定精度 k = 0 cluster = {} while True: cluster.clear() for i in range(len(sample_matrix)): max_cos = 0 nearest_label = None for j in range(self.n_clusters): cos = self.__cos(sample_matrix[i],self.cluster_centers_[j]) if max_cos < cos: max_cos = cos nearest_label = j cluster.setdefault(nearest_label,[]) cluster[nearest_label].append(i) #保存老的质心，计算新的质心 old_cluster_centers = self.cluster_centers_.copy() for j in range(self.n_clusters): self.cluster_centers_[j] = 0 for i in cluster[j]: self.cluster_centers_[j] += sample_matrix[i] self.cluster_centers_[j] = self.cluster_centers_[j] / len(cluster[j]) # 用方差比较新老质心之间的差距 if self.__variance(self.cluster_centers_, old_cluster_centers) <= self.precision: break; k+=1 # 根据计算结果给样本归类 self.labels_ = list('0' * len(sample_matrix)) for j in range(self.n_clusters): for i in cluster[j]: self.labels_[i] = j self.labels_ = np.array(self.labels_) =================聚类结果========== 每个文档所属的分组 [0 1 2 1 0 1 0]
    展开

    作者回复: 从程序片段看，逻辑上没有什么问题，可能是和初始质心的选取有关，另外欧氏距离和余弦夹角也可能导致结果的不同，因为余弦夹角相当于做了归一化

    共 2 条评论
  • Eleven
    2020-06-28
    看到这里就有点吃力了，工作中没有涉及到这块东西...

    作者回复: 坚持就会有收获

    共 2 条评论
  • 骑行的掌柜J
    2020-06-19
    我这里向量间使用欧式距离得到的是：[1 0 1 2 1 0 2] 而向量间用夹角余弦得到的是：[2 1 2 1 0 0 1] scikit-learn没有相应的夹角余弦包，所以要用后面这个Biopython。 建议大家可以去Biopython官网看看相关用法，用anaconda安装Biopython的指令是 ： conda install -c conda-forge biopython 这是中文文档地址：https://biopython-cn.readthedocs.io/zh_CN/latest/cn/chr15.html 这是英文的：https://biopython.org/wiki/Download
    展开

    作者回复: 感谢提供这么多信息给大家