基于改进相似度与类中心向量的半监督短文本聚类算法*

李晓红，冉宏艳，龚继恒，颜 丽，马慧芳

(西北师范大学计算机科学与工程学院，甘肃 兰州 730070)

1 引言

随着社交网络的兴起，产生了海量的短文本数据，如网络评论、新闻标题、微博等，它们携带了丰富的数据信息，成为一种新的具有极大挖掘价值的信息资源，对此类数据的分类需求也日益凸显出来。但是，短文本具有内容短、信息描述能力弱、主题分散等特点，使得已有的文本聚类方法应用于短文本时面临严重的特征稀疏问题[1]，导致短文本聚类效果并不理想；在实际聚类任务及其应用中，有时又能获得一些带有少量监督信息的数据，如何有效地利用这些监督信息进行短文本聚类也成为了研究人员高度关注的问题。而半监督学习(Semi-supervised Clustering)[2,3]可在监督信息较少的情况下完成对大量未标注数据的有效组织，并获得很好的效果。近几年，半监督学习方法以其显著的实用性价值在机器学习、网络信息安全、文本挖掘等领域获得了广泛应用。

目前,聚类方法与半监督学习相结合的算法已有较多研究结果。根据监督信息的类型将半监督聚类分为三类。一类是基于限制的方法，即利用事先提供的数据之间“必连”(Must-link)与“不连”(Cannot-link)的成对约束信息实现聚类，代表性的方法有：Wagstaff等人[4]提出的带约束的K均值聚类算法COP-Kmeans(ConstrainedK-means clustering)算法，要求每一步划分都满足已知的约束对信息，最终得到满足所有约束的聚类结果。另一类是基于样本标记信息的方法，如Wang等人[5]提出将深度表示学习和K-means聚类结合设计聚类目标函数，并利用少量加标数据和大量未加标数据对目标函数进行迭代优化，从而实现短文本半监督聚类；Zhang等人[6]也利用深度学习模型进行短文本聚类，但是该方法是将聚类过程和表示过程分离开来进行的。更多的则是将上述两类方法进行集成完成聚类，典型的有：赵卫中等人[7]提出的一种结合启发式的主动学习策略，获取成对约束集合，改善聚类性能；肖宇等人[8]引入标记数据或成对约束信息对相似度矩阵进行调整，提出了基于近邻传播算法的半监督聚类方法，该方法的不足之处是相似度矩阵元素值的调整比较极端。

本文通过对带标记数据所含信息量的分析与学习，提出一种依据词项类别区分能力的强弱，按类别抽取并构建强类别区分度词项集合的策略，并且将其应用到短文本相似性度量方法中，使短文本之间相似性的度量更加有效和准确。同时，提出利用短文本与类中心向量之间的相似程度来决定它们的类别，从而形成基于改进相似度和类中心向量的半监督短文本聚类算法ISaCV(Improved Similarity and Class-center Vector)，来提高聚类性能，算法结构如图1所示。

Figure 1 Algorithm structure图1 算法结构图

2 背景知识

假设少量带类标的短文本Dl={(d1,y1),…(di,yi),…,(dl,yl)}，di是m维短文本,yi∈{1,2,…,k}为类标签，大量无类标的短文本Du={dl+1,dl+2,…,dl+u}。半监督聚类就是利用Dl中的监督信息将短文本集合D={d1,…,dn}中的短文本划分到k个簇C1,…,Cr,…,Ck中。n是短文本总数量，n=l+u。显而易见，D=Dl∪Du，且C={C1,…,Cr,…,Ck}。

2.1 期望交叉熵

(1)

(2)

其中，P(t)表示特征t在文本中出现的概率，P(Cr)表示属于第Cr类的文本在数据集中出现的概率，P(Cr|t)表示文本在包含特征t的条件下属于类别Cr的概率。如果P(Cr|t)较大，并且相应的P(Cr)又比较小，则说明特征t和类别Cr强相关，对分类的影响大。

综合公式(1)和公式(2)，可推导出更加合理的期望交叉熵的表示形式:

(3)

其中，分子部分衡量了词项t对类别Cr的指示能力，分母部分衡量了词项t对短文本集合剩余部分(即C-Cr)的类别指示性。公式(3)有效地避开了那些对所有类都有较好表征能力的词项的筛选。

2.2 类中心向量

通常，同类数据相似度较高，分布紧密。为了计算文本与类别之间的相似性，本文使用已知类别信息的类中心向量来代表该类。假设C_cen(r)表示第r类(Cr)的类中心向量，|Cr|表示Cr类所包含短文本的数目。计算方法如下所示：

(4)

将公式(4)计算所得的所有类的类中心向量进行合并，构成加标数据集上的类中心向量集合，用Cen来表示。

Cen={C_cen(1),…,C_cen(r),…,C_cen(k)}

(5)

2.3 强类别区分度

首先，给出强类别区分度及强类别区分度词项的定义。

定义1(强类别区分度SCD(Strong Category Differentiation))[10]设C_diff(t,Cr)表示特征词t对类别Cr的类别区分度，则有：

C_diff(t,Cr)=tf-idf(t,Cr)*ECE′(t,Cr)

(6)

定义2(强类别区分度词项SCDI(Strong Category Differentiation Item)) 对于任意词项t，如果满足条件C_diff(t,Cr)≥g，其中g为筛查阈值，0

由上述定义可知，一个词项具有强类别区分能力应具备这两个条件[11]：(1)能够准确地表达短文本的主要内容；(2)对特定类别具有较强的指示能力，即有较强的类别倾向性。条件(1)可通过向量空间模型中词的词频-逆文档频率tf-idf(term frequency-inverse document frequency)值来衡量该词对于文本的重要程度,即一个词在某文本中出现频率tf越高，而在其他文本中出现的频率idf越低，则该词越能表达文本的主题，相应的tf-idf值也越大。条件(2)中词的类别指示能力可通过公式(3)所示的特征词的期望交叉熵来度量。ECE′(t,Cr)越大，特征词t与某个类Cr越相关，且与其他类别越疏远，说明该特征词t对类Cr的指示能力越强。

3 改进的相似性度量方案

3.1 抽取强类别区分度词项

通常，在不同类别中词的指示能力不同。根据定义2，在Dl中按类别抽取具有强类别区分能力的特征词，构成强类别区分度词项组成的集合，并将其作为先验知识来指导和训练短文本的分类。抽取算法见算法1。

算法1强类别区分度词项抽取算法(ESCDI)

输入：Dl={(d1,y1),…(di,yi),…,(dl,yl)}，阈值g，类别数k。

输出：强类别区分度词项集合Q={Q1,…,Qr,…,Qk}。

初始化：Q=∅，Q1,…,Qk={∅},r=1；

对每一个词项t，重复执行以下操作

forr=1 tokdo

利用公式(3)计算ECE′(t,Cr)；

按照公式(6)计算C_diff(t,Cr);

ifC_diff(t,Cr)≥g

thenQr=Qr∪{t};break;

forr=1 tokdo

Q=Q∪Qr；

returnQ;

3.2 改进的短文本间的相似性度量方案

相似性度量能否真实有效地反映文本之间的相似程度，对于短文本聚类的质量至关重要，因此有必要设计合理有效的相似性计算方案。

余弦相似度是通过测量两个文本向量夹角的余弦值来度量两个文本之间的相似性的。假设文本di可表示为向量di=(wi1,wi2,…,wim)，则任意两个文本di与dj之间的相似性可用下面的公式计算：

(7)

从强类别区分度词项的定义可推知，两个文档共同包含强类别区分度词集合Qr中的词项越多，则它们在类别Cr上就越相似[12]。下面给出文本di，dj在某个类别上基于强类别区分度词的相似度公式：

(8)

其中，f(di,t)表示强类别区分度词t在文档di中的出现频率，|Qr|为第r类强类别区分度词项集合Qr的大小。则在整个数据集上，基于强类别区分度词项的相似度定义为k个类别上文档di与dj之间相似度的最大值，公式如下:

(9)

由于公式(7)中的余弦相似度基于短文本包含的初始特征，忽略了词与类别之间蕴含的联系，而这种联系却极有可能有利于实现文档的正确划分。而公式(9)中基于带强类别区分度词项的相似性考虑了词的类别倾向性，对类别的指示更加明确，恰好可以作为余弦相似度的有效补充。本文综合考虑以上因素，给出如下所示的更全面有效的相似度计算方法来度量文本之间的相似性：

sim(di,dj)=asimCOS(di,dj)+

(1-a)simSCD(di,dj)

(10)

其中，α是相似度调节因子，取值为α∈[0,1]。

4 算法描述及复杂度分析

4.1 半监督聚类算法流程

本文提出的半监督短文本聚类算法就是通过对已知的少量加标数据的学习，获得对应类别的类中心向量。通过改进的相似度公式计算短文本与类中心向量的相似程度，再将每个未加标数据对象划分到与其最相似的类中心向量所代表的类中，由此达到对所有未加标数据聚类的目的。算法伪代码如算法2所示。

算法2基于改进相似度与类中心向量的半监督短文本聚类算法(ISaCV)

输入：Dl={d1,d2,…,dl}，Du={dl+1,dl+2,…,dl+u}，C={C1,…Cr,…,Ck}，阈值g，类别数k。

输出：簇矩阵C。

初始化：Cen=∅；

for eachdi∈Du,i=l+1,l+2,…,ndo{

调用算法1抽取并构建强类别区分度词项集合：Q=ESCDI(Dl,g,k);

根据公式(4)和公式(5)构造类中心集合：Cen={C_cen(1),…,C_cen(r),…,C_cen(k)}；

Max=0;label=0;

for eachC_cen(r)∈Cen,r=1,…,kdo{/*C_cen(r)为第r类的类中心向量*/

根据公式(10)计算sim(di,C_cen(r));

ifsim(di,C_cen(r))>Max

then {Max=sim(di,C_cen(r));label=r};}

将文档di划分到簇Clabel中,同时将di加入到加标文档集Dl;

Clabel=Clabel+{di},Dl=Dl+{di};

Du=Du-{di};//将di从未加标文档集中删除

}

returnC;

4.2 时间复杂度分析

5 实验结果与分析

为了验证本文所提短文本分类算法的有效性，精心设计了三个实验对算法进行验证，并提出相应的评价指标对实验结果进行评价。三个实验分别是：(1)阈值g和参数α的变化对算法性能的影响；(2)不同的相似度计算方法对聚类结果的影响；(3)比较不同聚类算法之间的性能差别。另外，本文采用F1值和纯度(Purity)[13]来客观评价算法的聚类效果，其中，F1值是综合查全率与查准率的评估指标，对聚类结果优劣的整体区分能力非常强；纯度简单计算所有簇中被正确聚类的文本数与总文本数的比值，值在0～1之间，值越大表示聚类结果越好。

5.1 实验数据

本文以新浪网站中各类新闻标题为实验数据，利用爬虫软件爬取了有代表性的8个类别。实验数据如表1所示。在本实验中，将每个类别中10%的数据加标以便提供监督信息，其余90%用来评价聚类性能，同时，将这8类数据混合在一起形成了待聚类的短文本集合D，共8 442条新闻标题。

Table 1 Dataset information of the experiment表1 实验数据集信息

5.2 实验结果与分析

5.2.1 阈值g和参数α对算法性能的影响

图2给出了强类别区分度词项的数目(注：图中用|SCDI|表示)的变化趋势，从实验结果来看，随着g的增大，筛选出来的强类别区分度词越来越少，符合强类别区分度词项的定义，而且g的变化对强类别区分度词项数目的影响极大。

为了进一步测试阈值g与相似度调节参数α对聚类结果的影响，表2和表3展示了g=0.551和g=0.561，α∈{0.3,0.35,0.4,0.45,0.5,0.55,0.6,0.65,0.7}时，聚类的各个F1值。可以发现在两张表中，调节因子α=0.35的聚类效果均是最好的；而且，当确定α=0.35时，g=0.551对应的F1值比g=0.561的F1值高，所以g=0.551，α=0.35时本文算法的聚类效果最佳。当α<0.35时，相似度计算公式中余弦相似度所占比重过小，忽略了文本原始特征对分类结果的重要作用。反

之，当α过大时，基于强类别区分度词项的相似度所占比重越小，强类别区分度词项的类别指示性越弱，导致强类别区分度词对分类结果的影响越小。

图3给出了强类别区分度词项数目(用|SCDI|表示)对聚类结果的影响，可以看出，在(253，1142]，算法的F1值随着强类别区分度词项数目的增大而逐渐增大，强类别区分度词项数目|SCDI|=253时，F1值达到最大值；但是当强类别区分度词项数目|SCDI|>253时，算法的F1值反而逐渐减小。并且|SCDI|=253时，g=0.551，恰好与表2和表3的结果相吻合。

综合图2、表2、表3和图3，强类别区分度词项的数目随g的变化波动较大，而且也影响到参数α的取值，因此对聚类的性能影响较大。为显示算法的效率与精确性，在后续实验中，取g=0.551，α=0.35，强类别区分度词项数目为|SCDI|=253。

Figure 2 Effect of g on |SCDI|图2 g对强类别区分度词项数目|SCDI|的影响

类别F1α=0.3α=0.35α=0.4α=0.45α=0.5α=0.55α=0.6α=0.65α=0.7环境63.6970.8270.0268.3467.6067.2367.7465.1764.81计算机81.6684.5383.8882.8583.2182.2782.5281.3180.69交通55.5663.5162.0560.5060.1159.8358.4957.6257.14教育55.8563.8363.1060.9660.4859.5257.4458.3557.14经济59.5965.4264.6664.3063.6763.0460.9061.5261.31军事56.3964.2463.3662.2360.3460.6157.7659.8759.74医药60.6869.4768.7867.9065.2667.5563.1665.9765.97艺术65.1171.4670.3768.9670.0768.6767.2868.6766.67

Table 3 Effect of α on F1 when g=0.561表3 g=0.561时，α对F1值的影响

Figure 3 Effect of |SCDI| on F1图3 强类别区分度词项数目|SCDI|对聚类F1值的影响

5.2.2 相似度对算法性能的影响

图4是本文ISaCV算法分别利用三种不同的相似度计算公式得到的聚类结果。从图4中可以看出，使用改进的相似度计算公式(对应图4中的(COS+SCD)后在各个类别上都取得了最优效果，基于强类别区分度词项(SCD)的相似度余弦相似度的效果最差，基于余弦夹角(COS)的相似度效果居中。说明本文提出的将基于强类别区分度词项的相似度和基于余弦夹角的相似度进行整合是正确的，能较好地处理特征稀疏的短文本之间的相似性的度量。

Figure 4 Comparison of F1 among different similarity calculation methods图4 不同相似度计算公式下聚类的F1值

5.2.3 不同聚类算法的性能对比

针对本实验所提供的数据集，分别选择PCS(Pairwise Constrained Semi-supervised text clustering)[14]、K-means与ISaCV算法进行了聚类性能对比。

首先，算法时间复杂度主要体现为聚类算法收敛所需的时间消耗。实验所用计算机配置：CPU为Corei72.60 GHz，内存8 GB，硬盘600 GB，编程语言为Java。在数据集规模不同的情况下，三种聚类算法的时间消耗如图5所示，PCS算法复杂度远高于ISaCV算法，K-means算法的时间复杂度略高，ISaCV算法收敛时间最短，时间复杂度最低。

Figure 5 Comparison of time complexity among the three algorithms图5 不同聚类算法的时间复杂度对比

其次，聚类准确性方面，从图6和图7可以看出，不论是F1值还是纯度，K-means算法的聚类效果最差，说明短文本特征稀疏及高维的问题对传统空间向量方法影响很大，而且只采用欧氏距离来判断相似性，计算结果不准确，从而造成误分。PCS算法效果稍好一点，但是此方法不能充分利用有价值的监督信息，聚类效果无法达到最好。ISaCV算法的聚类效果最好，因ISaCV算法逐步扩展加标数据，并及时更新类别信息，随着监督信息量的增加，使得聚类准确率逐步提升，得到了较好的聚类效果。尤其是“计算机”类的聚类效果突出，主要原因在于该类别的词汇与其他类别词汇混淆较少，强类别区分度词项抽取准确，词项的类别指示能力较强，使得聚类效果提升明显。综合两个指标的评价结果，ISaCV算法都有着较好的聚类结果，同时也表明了监督信息对聚类性能的影响。

Figure 6 Comparison of F1 among the three clustering algorithms图6 不同聚类算法的F1值

Figure 7 Comparison of purity among the three clustering algorithms图7 不同聚类算法的纯度

6 结束语

本文利用少量带类标的数据提取具有强类别区分能力的特征词并构成集合，计算得到基于强类别区分度词的相似度，并进一步将其与基于余弦夹角的相似度进行融合，设计了更有效合理的相似度度量公式，从而达到短文本之间相似性的准确计算。再通过计算已知类别类中心向量与未加标数据之间相似度的策略，来实现对未加标文本划分类别的目的。实验结果显示，本文方法能有效地根据短文本数据的特点利用半监督信息提高聚类效果。未来工作的重点是考虑从语义层面对短文本进行合理有效的扩展，同时考虑能否将类别信息转化为约束信息，从而将聚类问题转化为优化问题，最后是对参数的合理择优等问题进行进一步尝试来提高算法性能。