注：这篇技术文章是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)：簇由核心点形成，以核心点为中心，每个簇至少包含一个核心点，相连的核心点形成簇，非核心点可以成为簇的一部分。
如图所示，红色点即为核心点，黑色点中处在红点ε范围内的为可到达点，其他黑色点为异类点。彼此距离不大于ε的核心点构成一个簇，图示中含有两个簇。
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
