新闻类短文本聚类新方法的研究

傅承涛，谢佳璇，牛永洁

(延安大学继续教育学院，陕西延安716000)

随着信息技术的发展和自媒体的迅速普及，各领域迅速积累了大量的文本资源，对这些文本资源的处理、挖掘进而得到感兴趣的知识显得日益重要。文本聚类是根据文本内容对文本进行归类处理，属于非监督学习的一种，文本聚类可以为信息检索[1]、知识图谱[2，3]、自动摘要[4]、人机对话、知识问答等领域提供支持，因此文本聚类已经逐渐成为自然语言处理和文本数据挖掘的研究热点[5]。

对新闻类文本聚类可以对相同类别的新闻展开研究，比如研究同一事件在不同时间、不同地点的处理方式不同，对研究不同国家、不同地区、不同政党、不同时期政策的变化具有重要的参考价值。而且新闻类文本聚类可以出现某些新闻之间内在的关联，为社交网络、知识国谱、知识问答等提供一定的数据支持。文本聚类首先要解决的问题是文本表示，目前对文本表示的方法有基于词频的TF-IDF模型[6]，基于词语关联度的TextRank模型[7]，这些模型词语出现的频率和词语之间关联度的大小对词语进行编码，尽管解决了文本的表示问题，也一定程度上反映了文本的内容，但是它们都基本没有考虑文本的语义信息，而且由于采用词袋的思想，往往会造成数据维度高的问题。

Mikolov等在2013年提出Word2vec模型，利用神经网络模型将词语转换到带有一定语义特性的高维空间，Word2vec模型的词语向量具有一定的语义信息，一定程度上可以进行语义运算，比如：国王+女人=女王，但Word2vec对文本编码的过程中仅限于微观，失去了词序在语义表达方面的作用[8]。2014年Quoc Le等人提出了Doc2vec模型，该模型能从句子、段落或者文本中学习到固定长度的特征表示[9]，然后使用基于密度的聚类算法CFDF对数据进行聚类[10-12]。为了得到最优的参数组合，采用S_Dbw作为评估聚类的指标[13]，对CFDF算法中的两个参数进行了交叉试验，最后使用t-SNE算法对数据进行降维，在二维空间进行可视化，对数据的原始类别与聚类后的类别做了比较。

1 相关技术

1.1 Doc2vec技术

为了对文本进行处理，第一步需要对文本进行矢量化，传统的编码方式为one-hot编码。由于新闻类文本来自不同的领域，并且文本篇幅一般比较短，这就造成词语索引大，对每篇新闻采用one-hot编码势必造成文本矢量维数大，但矢量比较稀疏的问题，对后续算法的处理带来困难，造成后续算法不容易学习文本模式的困难。因此，新闻类短文本不能采用one-hot编码，需要采用词嵌入的方法。为了有效的保留语义和词序关系，词袋模型和词频模型是无法完成的。Doc2vec是Mikolov和Quoc Le在2014年基于Word2vec模型提出的可以保留次序语义的语义模型，该模型在Word2vec模型的基础上增加了一个段落标识[14，15]。其中Word2vec模型有两种类型，它们分别是连续词袋模型(CBOW)和Skip-Gram模型，CBOW模型是以一个词语上下文中的词语作为模型的输入来预测一个词作为输出，而Skip-Gram模型与CBOW模型相反，它以一个词语作为输入，来预测该词上下文的词。

CBOW模型在目标词的周围使用滑动窗口，将滑动窗口内的单词作为模型的输入，将该词作为模型的输出，CBOW模型如图1所示。

Skip-Gram模型如图2所示。

在不同的Word2vec模型上加入段落矢量(Paragraph Vectors)形成两种不同的Doc2vec模型PV-DM和PV-DBOW，CBOW模型训练过程中加入段落向量就是PV-DM模型，段落矢量是词语矢量的扩展，对文本中段落像词语一样用矢量化表示，其长度与词向量相同，同一句中不同的单词在训练过程中，段落矢量是共享的。

1.2 CFDP算法及其改进

本文采用Doc2vec进行词嵌入以后，每个文本被表示成为一个多维的向量，文本样本集就被转换为一个矢量集，可用采用各种聚类算法对其进行聚类。

传统的K均值聚类算法因为需要事先指定聚类个数而且初始中心点的选择直接决定聚类效果，并且类别归属使用距离决定，造成该类别的聚类算法只能对球形数据聚类，对其他形状的数据聚类效果很差。针对传统聚类算法的缺点，对文本聚类采用基于密谋的聚类方法。

2014年Alex Rodriguez和Alessandro Laio在Science上发表了文献[16]，文中提出了一个基于数据密度的新算法，简称为CFDF，该算法因为其观点的新颖性和简单性，理解引起研究者的关注[17，18]。CFDF算法建立在两个基本的假设上：

a)聚类中心周围都是密度比其低的点

b)聚类中心周围的点距离该聚类中心的距离相比于其他聚类中心来说是最近的。

对于需要聚类的每一个数据点，要计算两个量：点的局部密度和该点到具有更高局部密度的点的距离，而这两个值都取决于数据点间的距离。

现有需要聚类的数据集合X={x1，x2，x3，…，xN}，Is={1，2，3，…，N}，其中共有N个数据点，假设该数据集合有K个类别，分别为{c1，c2，…，ck}，其中K≤N，算法的步骤如下：

1)计算数据集合中任意两个数据点之间的距离。将距离数据存储到矩阵dist中，矩阵dist是一个对称矩阵，其中dist[i][J]=dist[J][i]，dist[i][i]=∞。

2)计算每一个数据点的局部密度ρi，局部密度的计算有两种方法，分别是截距局部密度和高斯局部密度。截距局部密度的计算公式如公式(1)所示。

(1)

其中函数x(z)如公式2所示

(2)

由公式(1)可知，一个数据点的局部密度就是距离小于dc的所有点的个数，dc称为截断距离，由用户设定。很明显截距局部密度是个离散值。因此可能会出现若干个数据点的截距局部密度相同的情况。

高斯局部密度由公式(3)计算。

(3)

高斯局部密度是一个连续值，同时满足距离数据点xi小于dc的点越多，ρi值越大。

3)按照局部密度的大小降序排列，得到数据点的下标序列qi。其中ρq1≥ρq2≥ρq3≥…≥ρqN，每个数据点的距离局部密度比它大的最小距离由公式(4)计算。

(4)

公式(4)没有采用原来的计算公式是因为原来的计算公式有将一个大的聚类分裂为两个小的聚类的缺陷，这是对原算法的一个改进和创新。现假设有28个数据点，根据上面的步骤计算得到每个数据点的(ρi,δi)，那么数据中心就应该是都比较大的点，如果ρi比较大，而δi比较小，说明该点周围的点比较多，但是距离比它局部密度大的点的距离比较小，说明这两个数据点边界不明显，有可能属于同一个类别。如果ρi比较小，而δi比较大，说明该点周围的点比较稀疏，而且距离另一个聚类中心的距离比较近。该点可能是一个孤立点，最好的点是ρi和δi都比较大，这样的点应该就是聚类中心。ρi和δi的意义如图3所示。图3中有28个数据点，横坐标是每个点的局部密度，纵坐标是每个点距离局部密度比它大的其他点的最小值。从图中可以看出，数据点1和数据点10应该是数据中心。数据点28应该是孤立点。

4)聚类中心的选择[19]。聚类中心的选择应该由ρi和δi共同决定，不同的文献资料采用的方法不同，本文采用对ρi和δi加权的形式进行调整，为了消除ρi和δi数量上的影响，首先对ρi和δi采用公式(5)归一化，然后使用公式6进行综合参数的计算。对数据集中的每个数据点都采用公式(6)进行计算，当Y值大于一定的阈值的时候，才能被认定为聚类中心。

(5)

Y=a*ρ+b*δ，其中a，b∈[0，1]

(6)

该算法采用a,b对局部密度和最小距离进行平衡，摒弃原算法使用硬阈值的做法，使得算法可以动态调整二者之间的关系，是算法的另一个创新点。

5)确定聚类中心后，其余数据点类别的指定。剩余数据点的类别标签的指定遵循当前点的类别标签和高于当前点局部密度的最近点的标签一致。所以剩余数据点类标签的指定按照局部密度值的降序顺序指定，如果当前点xi是聚类中心，跳过，否则寻找比xi局部密度大的离它最近的数据点的类别标签，如果找到的点的类别标签已经指定，那么xi的类别就与找到的点类别标签一致，如果找到的数据点的类别标签还没有指定，那么递归寻找该点的类别标签。直到所有的数据点的类别标签都被指定。

6)类别间边界确定。首先为每个类簇定义一个边界区域，即分配到该类簇但与其它类簇的点的距离小于dc(截断距离)的点的集合。然后为每个类簇找到其边界区域中局部密度最高的点，并以该点的密度作为阀值来筛选类簇。将边界中小于阈值的点排除该类别作为孤立点对待。

1.3 聚类效果评价

为了评估聚类效果的好坏，需要寻找一个评价指标，文献[20]对聚类常用的11种评价指标进行了测试，发现聚类评价指标S_Dbw在不同类型的数据集(例如有噪声，密度不均，聚类边界模糊等问题)上都有比较好的鲁棒性，能够比较全面的对聚类算法进行评价。

S_Dbw由公式(7)计算。

S_Dbw=Scat(NC)+Dens_bw(NC)

(7)

Scat(NC)由公式(8)计算。

(8)

Dens_bw(NC)由公式(9)计算。

(9)

其中D表示数据集，n表示类中数据集中数据点的个数，NC表示数据集中簇的个数，ci表示数据集中的第i个簇，ci表示簇Ci的中心，σ(ci)表示方差，‖σ(D)‖表示L2范数。f(x,ci)表示簇Ci聚类中心的局部密度，阶段距离使用该簇的平均标准偏差。

从公式(7)可以看出S_Dbw使用Scat(NC)衡量簇内的紧凑度，用Dens_bw(NC)衡量簇间的离散度。

2 实验仿真与结果

实验的整个流程如图4所示。

采用的数据来自搜狗新闻数据集，数据集的名称是corpus_6_4000[21]，在该数据集中共包含6大类新闻，每类新闻4000篇，每篇新闻长度在几百到几千字不等，平均长度为961。6类新闻分别是‘汽车’，‘文化’，‘经济’，‘医疗’，‘军事’，‘体育’，分词工具采用NLPIR汉语分词系统，Doc2vec由gensim工具包提供，参数min_count=5，epochs=15，window=8，dm=0，workers=4，sample=1e-5，seed=100，negative=5，文本矢量的维度分别采用了200和300以及平均长度960，点与点的距离采用余弦距离，截断距离dc采用平均每个点的邻居局部密度为数据总数的2%，从实验结果看，文本矢量的维度对聚类的效果有一定的影响，呈现当文本矢量长度在平均长度以下时，随着矢量维度越大，聚类效果越好，但是计算量也越大，综合运算时间和聚类效果，本实验的文本矢量长度取200。

实验过程中，对公式(6)中的参数a,b采用先粗调后微调的交叉验证方法。让参数a,b从0开始以步长0.1步进到1，记录每一对参数组合的S_Dbw值，对S_Dbw排序，选取其中最小的10个S_Dbw时的参数a,b的范围，在此范围内再以步长0.01对参数进行交叉验证。选取第二轮交叉验证的S_Dbw的最小值时a,b的组合为最终参数。

在实验过程中，发现公式(6)中的参数a，b及阈值的指定非常关键，图5是文本矢量维数为200，参数a为0.52，参数b为0.27时的局部密度和最小距离图。图中的平行于坐标轴的虚线是参数a，b物理意义的直观表示。

表1列出了文本不同维数一些参数及结果。

表1不同维数的参数及结果

虽然S_Dbw描述了聚类算法对数据点的聚类效果良好，但是聚类后的数据与真实数据的类别之间的差距如何？算法最后采用准确率P、召回率R以及宏平均F值作为该聚类算法正确性的评判标准，令KA表示数据集中文章本身所提供的真实类别，KB表示算法聚类后数据指定的类别，则P、R和F值的计算方法如公式(10)所示

(10)

当文本维数为200，a=5.20，b=0.27，F值达到最大值89.24。

3 结论

经过大量的试验，可以得出结论:对短文本聚类，影响因素比较多，首先是文本的矢量化，不同的矢量化方法对文本内容进行了不同的表达，本文采用Doc2vec的方法，但该算法的参数众多，不同的参数对聚类结果的影响还是比较大，CFDP算法聚类思想新颖，简单，但是算法中截断距离，参数a，b对该算法来说选取十分关键，目前为止还没有自动确定这些参数的良好办法，需要通过大量的交叉实验来选取，这也是将来的一个研究方向。

聚类效果评价指标S_Dbw的大小并不能绝对衡量聚类效果的好坏，通过表1可以看出，在数据维数发生变化的情况下，200维的S_Dbw就比900维的S_Dbw数值要大，因此只有在其他参数固定的情况下，S_Dbw越小才能说明聚类效果越好，聚类效果好与聚类结果是否正确基本呈现正比例相关。

从实验过程可以看出，文本聚类的核心问题是文本矢量化。文本矢量化要求能够从语义上体现文本的定义，目前Doc2vec方法能体现一定的文本语义，但文本中的其他属性(性别属性、地域属性等)还不能全面覆盖，而且一个良好的聚类算法也是必需的，但距离度量、阈值设定等对算法都有一定的影响，这些问题将是以后研究的重点。