注：这篇技术文章是9月我就职于W公司时在完成新闻聚类后整理的技术文档，因数据管控严格，文档中的聚类结果无法从公司电脑上复制，也无法发送邮件到自己邮箱中。2017.10.27

文本聚类

目  录

1 聚类概述 

2 不同文本间相似性的度量 

  2.1 杰卡德系数(JACCARD COEFFICIENT) 

3 文本分词 

4 文本聚类算法 

  4.1 DBSCAN算法的基本定义 

  4.2 DBSCAN算法 

5 文本聚类实现 

  5.1 聚类结果 

6 参考文献 

1 聚类概述

作为一种数据挖掘技术，聚类可将被聚类对象从无序状态实现聚集。被聚类的对象包括物理或抽象对象，按照特定或非特定的属性分为一组，根据对象间在属性上的相似性完成分类。分为同一组的对象有相似性，不同组间的对象有很大相异性。与分类不同，聚类所要划分的类是事先未知的。

2 不同文本间相似性的度量

常见的相似性的测量方式包括欧式距离、马氏距离、曼哈顿距离、夹角余弦、杰卡德相似系数/距离等。新闻和报告的文本特点是不同题材文本之间含有大量不同的词汇。这个特点决定了文本相似性适合由杰卡德相似系数/距离来度量。

2.1 杰卡德系数(Jaccard coefficient)

给定了两个集合A, B，杰卡德系数定义为A与B交集的大小与A与B并集的大小的比值，定义表达式如下

当集合A, B都为空时，J(A, B)定义为1.

与杰卡德系数相关的指标叫做杰卡德距离，用于描述集合间的不相似度

其中 .

在文本聚类中应用杰卡德系数测量距离时，首先将文本转化成n维布尔向量，即所有维度的取值为0或1，比如某文本A的布尔向量是(0,1,0,1,0,……1)，某文本B的布尔向量是(0,0,1,0,0,……0).向量的每个维度对应了一个词，1表示集合中包含该词，即向量中1对应位置的词出现在文本中，0表示集合不包含该元素。

定义如下指标：

p: 文本A和B相对应的位置都是1的维度的个数；

q: 在文本A的值是1，文本B的值是0的维度个数；

r: 文本A的值是0，文本B的值是1的维度个数；

s: 文本A和B相对应的位置都是0的维度的个数。

p, q, r, s表示的是由向量代表的词是否在文本中出现及各自出现次数。仅考虑向量对应的词库，在两篇文章中均出现的词的数目为p,只在A中出现不在B中出现的数目是q，只在B中出现不在A中出现的数目是r，不在两篇文章中出现的数目是s。

3 文本分词

进行文本聚类前需要对中文文本进行分词操作。分词操作后得到每个文本的分词向量，删除重复词，并与另一文本分词向量计算杰卡德系数。实例如下：

A：美国国家经济顾问科恩：特朗普总统100%承诺将在今年完成税改。

B: 美国白宫发言人：总统特朗普感谢俄罗斯总统普京驱离美国外交官时是在“挖苦”俄罗斯。

A的分词向量是['美国', '国家', '经济', '顾问', '科恩', '特朗普', '总统', '100%', 承诺', '将', '在', '今年', '完成', '税改']，B的分词向量是['美国白宫', '发言人', '总统','特朗普', '感谢', '俄罗斯', '普京', '驱离', '美国', '外交官', '时', '是', '在', '挖苦']。分词的实现过程中删除经常出现的标点符号如逗号（，）句号（。）引号（“”）感叹号（：），并适当选取停止词(stopwords)，在分词后滤出，以清理分词结果，用于计算相似性。

仍然以上文为例，A和B中共有的词共3个（'美国'，'总统'，'特朗普'），p = 3，A中有而B中没有的词共11个（'国家', '经济', '顾问', '科恩', '100%', 承诺', '将', '在', '今年', '完成', '税改'），q = 11，A中没有而B中有的词共11个（'美国白宫', '发言人', '感谢', '俄罗斯', '普京', '驱离', '外交官', '时', '是', '在', '挖苦'），r = 11。由此计算出两个文本的杰卡德系数为

4 文本聚类算法

常见的聚类算法分为以下若干类别，划分法、层次法、基于密度的方法、基于网格的方法和基于模型的方法。被数据科学家广泛采用的无监督的K-means方法(划分法)的劣势在于在对未知数据进行聚类时需要指定所分成簇的个数K，应用于文本聚类中会导致聚类错误。本项目采用的聚类方法是基于密度的DBSCAN(Density-based spatial clustering of application with noise)。该方法是一种基于密度的聚类算法，假定类别可以通过样本分布的紧密程度决定，同一类别的样本之间紧密相连，即在该类任意样本周围不远处一定有同类别的样本存在。通过紧密项相连的样本被划为一类，就得到了一个聚类的类别，通过将各组紧密相连的样本划到不同的类别，即实现了最终聚类的效果。下面介绍DBSCAN算法的细节。

4.1 DBSCAN算法的基本定义

核心点：一个点p是个核心点，如果距离它ε范围之内的其他点个数不低于minPts个。

可到达点：在核心点p的ε范围内的点被称作由核心点直接抵达，或可到达点。可到达点可通过与其相邻的核心点，到达距离超过ε的核心点。

异类点(outliers)：不能达到核心点的点即为异类点。

簇(cluster)：簇由核心点形成，以核心点为中心，每个簇至少包含一个核心点，相连的核心点形成簇，非核心点可以成为簇的一部分。

如图所示，红色点即为核心点，黑色点中处在红点ε范围内的为可到达点，其他黑色点为异类点。彼此距离不大于ε的核心点构成一个簇，图示中含有两个簇。

图1 核心点、可到达点、异类点和簇的示意图

4.2 DBSCAN算法

DBSCAN算法中有两个重要参数：距离ε和形成簇的最小点数minPts。

聚类从随机节点开始，保证每个节点被访问一次且仅访问一次。对每个节点，计算其范围ε内节点的个数。如果节点个数超过预定的点数minPts，则该节点被标记为核心点，否则被标记为噪音点。

核心点和其范围ε内的点形成簇。查找簇的过程在访问所有点一遍之后完成。

DBSCAN算法描述如下：

While 数据库中存在未被处理的点

{从数据库中抽取一个未被处理的点

If 抽出的点周围ε范围内的点个数>= minPts

抽出的点 = 核心点

Else

抽出的点 = 噪音点

If 抽出的点 = = 核心点

找出所有密度可达的周边的点，形成一个簇

Else

抽出的点 = 边缘点

continue

}

5 文本聚类实现

本项目中的文本聚类算法用Python语言实现(IDE: Spyder)，分词使用jieba分词包。前期试验从大数据平台选用了过往任意七天的带有摘要的新闻数据，共4769条，在经过数据预处理之后根据新闻摘要进行聚类。

在分词过程中中文常见标点符号不在结果中保留。一些常见的停止词(stopwords)也被排除在结果中，比如“的”，“月”，“日”，“了”。

在实现过程中对所有新闻任意两两计算杰卡德系数，并保存于杰卡德系数矩阵中(4769*4769)。比较每条新闻的杰卡德系数与范围ε的大小并计算拥有系数大于ε的周围节点数目minPts，即可判断该条新闻是否能够成为核心点，是否有簇形成。

本测试中ε=0.14，minPts = 15。

5.1 聚类结果

下图2(略)是没有经过聚类的新闻事件，图3(略)是经过DBSCAN算法聚类得到的若干结果。这里只给出算法结果的示意图。更多测试和准确性度量将在后续工作中完成。

图略。

调整参数后可得到不同的聚类结果。调整ε，增大ε则聚类结果中新闻的相关性增高；调整minPts，增大minPts则聚类结果只保留新闻多的类。

6 参考文献

[1] DBSCAN on Wikipedia, https://en.wikipedia.org/wiki/Dbscan

[2] 数据挖掘导论(英文版)，Pang-Ning Tan/Michael Steinbach/Vipin Kumar，机械工业出版社，2010

[3] 百度百科: DBSCAN, https://baike.baidu.com/item/DBSCAN/4864716?fr=aladdin