基于短文本信息流的回顾式话题识别模型

周 泓，刘金岭，王新功

(1. 淮阴工学院 计算机工程学院，江苏 淮安 223005；2. 沧州师范学院 计算机系，河北 沧州 061000)



基于短文本信息流的回顾式话题识别模型

周 泓1，刘金岭1，王新功2

(1. 淮阴工学院 计算机工程学院，江苏 淮安 223005；2. 沧州师范学院 计算机系，河北 沧州 061000)

近几年来，短文本信息流广泛应用于一些全民媒体，它在公开传递信息同时携带了丰富且具有极大价值的信息资源。该文提出了一种回顾式话题识别模型，改进了权值计算方法，有效提取了具有较强分辨话题能力的关键词，在聚类过程中将BIC值作为话题类别合并依据，提高了聚类的准确率。通过进行时间段分隔和去掉孤立点信息提高了算法的效率。实验结果表明，该方法有效地提高了短文本信息流的话题检测准确率和效率。

短文本；信息流；话题识别；聚类

1 引言

在这个信息技术日新月异的年代，短文本信息流在生活中随处可见，如手机短信、网络即时通信、微博、微信、论坛等。短文本通常指内容较短的文本，多数字数不超过140，其在传递过程中除了显式的字面信息外，还蕴藏着丰富且极具价值的隐式信息资源。在面对海量短文本动态信息时，如何利用计算机高速的计算能力，自动识别、锁定、收集、跟踪、预判信息流中蕴含的热点话题或突发事件等问题，具有较高的学术研究价值及现实意义，可广泛应用于如信息安全、舆情分析及预警等多个领域。话题识别分为在线话题识别和回顾式话题识别两个研究方向，在线话题识别就是在线检测当前所到达的短信文本所属话题，回顾式话题识别就是检测已接收到的短文本信息流中尚未发现的话题，这些检测都是在缺乏话题先验知识的情况下把短文本信息流中内容相似的无标签短文本组织到一块，这就需要将短文本信息流进行聚类。但是短文本信息流的聚类与传统文本聚类有两个不同之处，一是它具有时序性，短文本信息流的短文本是按时间有序的；二是话题具有生存周期： 产生(提出)→发展(热议)→消失(趋冷)，而传统的文本聚类只是把与话题内容相近的文本聚类到一起。本文所研究的是回顾式话题识别。一个话题通常包含与信息相关的若干方面，即由若干子话题构成，因此无法用一个中心向量来概括。以2012年备受关注的“毒胶囊”话题为例，其是围绕着“问题胶囊子话题”、“工业明胶子话题”、“铬超标子话题”、“皮革废料子话题”、“果冻子话题”、“老酸奶子话题”、“黑心药子话题”、“食品药品安全子话题”、“食品药品监管子话题”、“违规生产子话题”等众多子话题展开的。而这些子话题中又富含该话题的一系列关键词，如毒胶囊、黑心药、政府、卫生部、国家食药监局、国家质量总局、明胶、铬、皮革、四川蜀中、修正药业、通化金马等，这些关键词对区分话题无疑是比较重要的，但若是只依赖于关键词来区分话题，其检测性能却是有限的[1]。基于话题的时间特性，本文不断提炼话题的代表性关键词向量，从而提高了话题识别的准确率，并利用BIC(Bayesian information criterion)的值使得多个相近子话题被聚集到了同一个话题类别。

2 相关工作

DARPA支持的话题识别及跟踪项目[2](Topic Detection and Tracking，TDT)是最早开展的话题识别研究。随后，国内外与话题识别相关的研究日渐深入，研究成果也日益丰富起来。文献[3]分析了英文报道的基本特征，并给出了基于内容分析的话题识别算法，将话题按其语义内容表示为标识中心向量与内容中心向量。文献[4]提出了话题检测算法CMU，使用训练语料建立了所有词语的倒排文档频率，并利用分段的GAC方法进行了聚类。文献[5]则利用时域分析法对事件内容进行分析。现有方法中大都具有以下缺陷：一是在基于文本相似度的聚类上进行特征扩展的过程中，没有考虑到上下文的相关性，即文本信息间的交互性；二是有些方法简单地以信息时间顺序对特征向量值进行加权，忽视了会话深层的时序特征。Takeshi等所设计并实现的基于Twitter的实时地震监控系统[6]，是短文本话题识别及处理方面的典型应用。该系统采用了贝叶斯决策来筛选关键字，可成功检测到的地震发生率达80%以上。其时效性远高于相关地震告警机构，且其还可以依据信息中所包含的地理数据，估算出地震发生的大体位置。Sasa和Miles等提出了一种改进的新话题识别算法[7]，能够在不失精度的前提下，快速地处理大于1.6亿条Twitter消息。Zitao Liu等人利用part-of-speech和HowNet扩展单词的语义特征的方法筛选出短文本的关键词，以改进短文本分类和聚类效果[8]。目前，多数话题识别算法是以语法信息为基础计算话题和报道的相似度，很少考虑短文本信息的特征稀疏性、时序性、交互性、奇异性和动态性，难以区分短文本信息的差异程度，另一方面，这些方法也很少考虑话题的时间特性以及一个话题可能包含几个差异较大的子话题，这些都会影响话题识别的质量。

3 关键词的权值

TF-IDF(term frequency-inverse document frequency)概念被公认为信息检索中最重要的发明。它是一种常用的、有效的词汇加权算法，其基本思想是： 在文本集中出现次数越多的关键词或者在文本集中出现越少的关键词区分度越高，因此关键词权值也就越大。但也有如下明显不足： 如果某个关键词在某些文本中出现得较频繁，而在另一些文本中出现得比较少时关键字区分度较低；另一是当包含某个关键词的文本分散到多个话题中，且文本数量不多时关键字区分度也较低。当前专门针对短文本的度量技术研究并不多，且短文本聚类算法多是长文本聚类算法的简单变形，没有突出短文本短小、内容表达随意、语句不完整、语法不规范和关键词稀疏等特点。本文主要依据“短文本聚类过程中，某些核心词汇可能极具判别性”语义特征来刻画关键词权值的影响程度。从关键词在短文本中出现的频率、关键词对短文本信息流分布影响度、短文本信息流分布对于关键词的影响度和关键词关于话题的影响度四个因素考虑关键词的权值。

定义1 关键词wi在短文本Dj中出现的频率定义为式(1)。

其中，tfij表示文本Dj中关键词wi出现的频率，length(Dj)表示文本Dj的长度。

定义1的意义在于关键字出现的频率，考虑到了文档的长度，是因为关键字在较长短文本中出现的次数一般会比相对较短的文本中出现的多。

定义2 关键词wi对于短文本信息流{Dj}分布影响度定义为式(2)。

其中，tfij表示短文本Dj中关键词wi出现的频率，gfi表示在短文本信息流中关键词wi出现的次数，Nt表示短文本信息流中所包含的短文本数量。

定义2的意义是关键词区分短文本的能力，利用熵理论定义了关键词对于短文本的分布情况的影响。

同样可以利用熵理论来计算短文本分布对于关键词权值的贡献，定义3如式(3)所示。

定义3 短文本信息流{Dj}的分布对于关键词权值的影响度定义为：

其中，tfij表示短文本Dj中关键词wi出现的频率，length(Dj)表示短文本Dj的长度，gfi表示在短文本信息流中关键词wi出现的次数，swf表示文档集中所有关键词出现次数的总和。

传统的聚类算法中，没有考虑到关键词与话题本身的联系，本文在初始聚类时就得到与话题相关联的一组关键词，再通过不断的修正和提炼来提高话题识别的精确度。

定义4 关键词wi关于话题Cj(表示话题的类别)的影响度定义如式(4)所示。

其中，dfci表示在短话题类别Cj中包含关键词wi的短文本数，Nc表示话题类别Cj中的短文本总数，dfi表示短文本信息流中包含关键词wi的短文本总数，Nt表示短文本信息流中包含短文本的总数。

定义4的意义在于如果关键词wi在话题Cj中出现的次数较多，而在其他话题中出现的次数较少，则说明wi对话题Cj的影响度较大，即有较好的话题区分能力。在本文话题聚类过程中利用式(4)对关键词不断地进行调整、筛选和提炼。

定义5 关键词wi对于短文本Dj的权值定义如式(5)所示。

定义5的意义在于关键词的权值既考虑到了TF-IDF模型的影响，同时也考虑到了短文本信息流文本的分布对关键词权值的影响。

4 子话题合并准则

一般来讲，短文本信息流中通常包含若干个话题，而每个话题又包含若干个子话题，表达这些子话题的短文本相互交织在一起，因此首先需要确定哪些子话题是可以合并的。传统聚类算法中大都采用模型选择的方法来确定类别的合并。而文献[9]中的聚类过程，则利用贝叶斯BIC (bayesian information criterion)来实现模型打分，并合并 BIC分值最高的聚类模型。由于该算法对新的聚类模型采取不间断的测试评分，因此需要较大的空间来存储相关统计信息。本文采用文献[10]的方法，通过计算BIC值来确定需要合并的子话题。

定义6 假设{xi|i=1,2,…,n}是d维样本数据集，被聚类为k个数据子集{C1,C2,…,Ck}，记该聚类模型为M，而Pi为聚类模型M中独立参数的个数，则M的BIC值定义如式(6)所示。

由定义6可以看出，BIC准则的基本思想是样本的极大似然减去模型的复杂度，根据文献[10]，可以利用BIC的值来判断聚类过程中两个类别是否应该合并，即假设短文本类别集聚类模型M1的某两个类别合并后得到聚类模型M2，如果BIC(M1)

5 短文本数据流的回顾式话题识别模型

算法的主要思想是利用短文本信息流时序特征和话题所具有的阶段性，先对每个时间段内的短文本集进行聚类，得到各个话题相应的类别及子话题类别。最后再对各个阶段的类别进行合并。在聚类过程中，通过不断提炼能够代表话题的特征来提高聚类的性能。

5．1 时间段的划分及其聚类

短文本信息流的回顾式话题识别是在主题相关性的基础上考虑多个文本集之间的时序关系，如图1所示把短文本信息流S的生存时间T划分为n个时间段[t0,t1],[t1,t2],…,[tn-1,tn]，各个时段包含的文本集分别为STS1, STS2,…,STSn。短文本信息流的话题识别以文本集STS1,STS2,…, STSn中话题聚类的类别为基础，进一步对这些类别进行合并以得到最后话题识别结果。

图1 短文本数据流按时间段分隔

关于短文本集STSi的聚类，目前研究的方法很多，本文在后面实验中取文献[11]中的基于语义密度的文本聚类方法。

5．2 子话题类别合并算法STCC

定义7 设在m维空间中有两个点x =(x1,x2,…,xm)，y=(y1,y2,…,ym)，x和y的距离定义如式(7)所示。

其中, xk和yk分别是x和y的第k个属性值。如果Ci，Cj是两个类别，则定义Ci与Cj的距离如式(8)所示。

定义8 设类别C的中心向量为C.center，x0∈C，如果满足

则称x0为关于类别C的孤立点。其中α是调节参数，0<α<1，|C|是类别C中所含元素的个数。

定义8是利用密度的思想定义了孤立点，即孤立点附近是稀疏的。其意义在于有些与话题不太相关的短文本可以不去考虑。

下面给出两个话题类别合并的算法。为了问题讨论方便，不妨设两个话题为X、Y，它们的子话题类别个数均为s，话题类别X、Y进行合并后为话题类别Z。基本思想是： 每一个短文本作为向量空间的一个结点，先是在类中选择相互之间距离最大的s个分散的结点作为子话题中心结点，然后去掉孤立结点并选择离它们最近的结点作为各自子话题的成员。算法STSCC(Short Text Subtopic Categories Combination)如下所示。

输入 STS中话题类别X,Y及它们子话题类别个数s

输出 合并后的类别Z

STSCC算法：

step1 利用文献[12]，分别计算出X和Y的中心向量X.center和Y.center

step3 TSet=Φ,k=1

step4 do while k<=s

step4-1 maxD=0

step4-2 对于X和Y的子话题中任意点p

step4-3 if (k=1) then

step4-4 d=dist(p,Z.center)

step4-5 else

step4-6 d=dist(p,Z) //点p到类别Z的距离

step4-7 if (d>maxD) then

step4-8 maxD=d

step4-9 maxP=p

step4-10 endif //找到类别Z中与点p最大距离的点和距离值

step4-11 endif

step4-12 k=k+1

step4-13 TSet=TSet∪{maxP}

//TSet中存储了X、Y类别中与Z距离最大的s个点

step4-14 enddo

step6 对于话题Z中的每一个点q

step7 for (每一个点p∈TSet) do

//把TSet的点作为Z子话题的中心向量进行子话题划分

step7-1 对于话题Z中的每一个点q

step7-2 if (q是孤立点) then

step7-3 Z=Z-{q}

step7-4 endif

step7-5 if (q离p所在类Cp的中心向量最近) then

step7-6 Cp=Cp∪{q}

step7-7 endif

step7-8 endfor

step8 输出Z

5．3 短文本数据流的回顾式话题识别算法

在短文本集STSi聚类结果中，总假设每个话题类别具有s个子话题，如果不足s个子话题时补充空子话题，如图2所示。

图2 话题的子话题生成

短文本集STSi的回顾式话题识别算法STRTD(Short Text Review Topic Detection)如下：

输入 短文本信息流S，子话题数s，短文本向量维数m，距离阈值μ

输出 话题类别集CT_S

STRTD算法

step1 对任意短文本ST∈S，按(5)式计算出ST每个关键词权值，并将权值由大到小选出m个关键词构成ST的一个向量，最后得到S的短文本向量集，记为TST_V

step2 按4.1分成n个时间段，将每一个时间段中的短文本向量按文献[11]的方法聚类，初始状态是将S的各类别存储在类别集合CT_S中，并假设每一个类别都有s个子类别

step3 建立存储类别对的堆栈Stack

step4 repeat

step4-1 将CT_S中的类别按两两距离最近构成若干个类别对，并按距离由小到大压入堆栈Stack

step4-2 出栈存入Nd

step4-3 do while (Nd!=Φ)

step4-4 将Nd中的类别对分别赋值给X,Y

step4-5 将值X,Y,s传给算法STSCC算法，合并后的类别为Z

step4-6 if (BIC(Z)>BIC(X,Y)) then

step4-7 退出该循环，重新定义关键词并修改CT_S，执行step4-1

step4-8 endif

step4-9 enddo

step4-10 until (step4-6中条件不满足)

step5 输出CT_S

短文本集STS的回顾式话题识别算法STRTD的结果给出了具体的话题、子话题内容及话题个数，并且还可能检测出S中尚未发现的话题。

6 实验及结果分析

为了评价算法性能，该实验将话题检测算法STRTD、文献[9]的X-means聚类算法及文献[4]中给出的CMU关于话题聚类算法进行比较。

6．1 实验数据及评价标准

为了验证相关结论，我们从江苏某短信运营商截取2012年2月1日0点整到4月30日24点0分时间段的近9.4万条手机短信文本集合进行了人工标注。抽取出了如载有化学品的船在江阴段沉船、江苏沿江部分城市出现市民抢购矿泉水、元宵节祝福等78个话题，假设每个话题中有8个子话题。为了问题的简化，实验前已将样本集S通过分词、特征提取和降维等预处理为短信文本向量集STS[13]。

假设类别i中包含ni条短信文本，聚类j中包含nj条短信文本，聚类j中隶属于类别i的短信文本条数记为nij，则召回率R(i,j) 和正确率P(i,j)的定义如下[14]：

F值F(i,j)为：

F值的全局聚类为：

在这里，|STS|=n，并且有，F值越大，标志着聚类效果越好。

如果系统漏检率用PMiss表示，由文献[15]有：

6．2 小类别数量实验

根据Power Laws和Pareto分布特征原理，小类别的中文短信文本信息的数量往往远远大于大类别[16]。本文对海量中文短信文本信息进行研究，对于小类别的中文短信文本尽量减少其聚类时间，或者将其清除掉，对于大类别的中文短信文本尽量增加其聚类机会，以提高大类别中文短信文本信息的聚类效率。本文从江苏某短信运营商的文本短信样本库中随机抽取了18 000条短信，在经过人工标注后，使用K-means算法对其进行聚类，实验中规定每个样本为一个类别，故类别个数k取18 000，该实验中对于短信文本个数超过20的类别定义为大类别，短信文本小于5的为小类别，孤立点指包含短信文本个数为1的类别。实验结果如表1所示。

从表1可以看出，在18 000条短信文本中，孤立点的短信文本条数占样本总数的61.76%，而大类别数目仅占67个，大类别包含的短信文本的个数仅占样本数的14.38%。

表1 大、小类别和孤立点数目实验结果

6．3 召回率、正确率及F值比较

该实验中，将X-means、CMU和 STRTD的召回率R、正确率P、漏检率PMiss及F值进行比较，实验结果如图3所示。

从图3可以看出， STRTD话题检测方法性能明显优于其他 两 种算法， 这是由于算法STRTD采用了分段聚类，而后进行类别合并，并且引入了子话题的思想，提取具有高辨别能力的关键词，这样就会减少X-means和CMU中依赖类中心向量对话题检测性能的影响，提高了话题检测的召回率和准确率，同时也减少了话题检测的漏检率。

图3 3种算法的4种性能指标比较

6．4 算法运行时间比较

该实验中，在近94 000条手机短信文本集合中随机抽取了18 000条短信文本进行实验，为了问题简单，先使用中科院计算所开发的ICTCLAS 作为中文分词工具将这18 000条短信文本进行了分词，构造出了多维向量空间，然后对算法X-means、CMU和STRTD运行的时间进行比较，结果如图4所示。

图4 3种算法的运行时间比较

在3种算法的运行时间比较试验中，由图4可以看出，当对11 340条短信文本进行试验时，CMU算法和STRTD算法的运行时间基本上相同，当在大于这个数的短信文本集上验证时，STRTD算法比其它两种算法所需时间都少，而且随着样本量的增大，效果越来越好。这是因为在少量短信文本集的实验中，STRTD算法需要对短信文本信息流进行时间段的划分，在子话题类别合并过程中需要去点孤立点，占用了一些时间开销，但随着短文本数据量的增大，使得短信文本信息流的话题检测的运行效率大大提高。

6．5 检测话题数量实验

对6.2实验中得到的67个大类别短信文本作为准确的话题数目，该实验利用3种算法检测出话题数量与真实话题数量进行比较。实验结果如图5所示。

图5 3种算法检测的话题数比较实验

由实验结果可以看出，STRTD算法优于其它两种算法，在超过3 000条短信文本的试验中，STRTD算法检测出的话题数量与真实话题数量的差异在10%以内，而且随着实验样本数量的增多，更接近于真实话题数量。

7 结束语

在短文本信息流中检测话题的中心问题是如何把短文本归类到相应话题中，目前大多话题检测方法都是利用传统的聚类方法，没有体现出话题的本身特点，性能也较低下。本文利用了短文本信息流的时序特征进行分段、聚类、类别合并，并去掉话题识别过程中孤立点信息，提高了话题检测的效率。在检测过程中又不断提取具有辨别能力的短文本关键词，利用TF-IDF的改进算法赋予权值，引入了子话题提高话题检测的准确率。实验表明，该算法具有较好的话题检测质量和效率。

[1] Wang ZM,Zhou XS. A topic detection method based on bicharacteristic vectors[C]//Proceedings of the Int’l Conf. on Networks Security,Wireless Communications and Trusted Computing. Vol. 2. Washington: IEEE Computer Society, 2009. 683-687.

[2] Allan J, Papka R.On-line new event detection and tracking[C]//Proceedings of the 21 st Annual International ACM SIGIR Conference on Research and Devel-opment in Information Retrieval. Melbourne:ACM Press,1998.37-45.

[3] 赵华,赵铁军,张姝,等.基于内容分析的话题识别研究[J].哈尔滨工业大学学报,2006,38(10) : 1740-1743.

[4] Seo YW,Sycara K.Text clustering for topic detection[C]//Proceedings of the Pittsburgh: Robotics Institute, Carnegie Mellon University, 2004. 1-11.

[5] 骆卫华,于满泉,许洪波,等.基于多策略优化的分治多层聚类算法的话题发现研究[J].中文信息学报,2006,20(1):29-36.

[6] Sakaki Ti,Okazzki M,Matsuo Y.Earthquake Shakes Twitter User:Real-time Event Detection Detection by Social Sensors[C]//Proceedings of the 19th International Conference on World Wide Web,2010. Raleigh,North Carolina:ACM Press,2010:851-861.

[7] Petrovi S,Osborne M,Lavrenko V.Streaming First Story Detection with application to Twitter[C]//Proceedings of HLTNAACL,2010. stroudsburg,PA,USA:Association for Computational Linguistics,2010:181-189.

[8] Liu Zitao,Yu Wenchao,Chen Wei,et al.Short Text Feature Selection for Micro-blog Mining[C]//Computational Intelligence and Softeare Engineering,2010. Wuhan, China:Wuhan Unive- sity, 2010:1-4.

[9] Pelleg D, Moore A. X-means: Extending K-means with Efficient Estimation of the Number of Clusters[C]//Proceedings 17th ICML. Stanford University.2000.727-734.

[10] 张小明,李舟军,巢文涵.基于增量型聚类的自动话题识别研究[J].软件学报,2012,23(6): 1578-1587.

[11] 刘金岭. 基于语义密度的文本聚类研究[J].计算机工程,2010,36(5):81-83.

[12] 王强,关毅,王晓龙.基于标题类别语义识别的文本分类算法研究[J].电子与信息学报,2007,29(12):2886-2890.

[13] 刘金岭.基于降维的短信文本语义分类及主题提取[J].计算机工程与应用,2010,46(23): 159-161.

[14] 黄九鸣,吴泉源,刘春阳,等.短信文本信息流的无监督会话抽取技术[J].软件学报,2012,23(4):735-747.

[15] NIST.The 2004 Topic Detection and Tracking(TDT2004) Task Definition and Evaluation Plan version1.1c[EB/OL]. http://www.nist.gov.

[16] M. E. J. Newman. Powerlaws, Pareto distributions and Zipf’s law[J]. Contemporary Physics, 2005,46(5):323-351.

Retrospective Topic Identification Model for Short Text Information Flow

ZHOU Hong1, LIU Jinling1, WANG Xingong2

(1. Computer Engineering Faculty, Huaiyin Institute of Technology, Huaian, Jiangsu 223005, China;2. Department of Computer, Cangzhou Teachers College, Cangzhou, Hebei 061001, China)

In recent years, the short text information flow has occured in some public media. For this kind of data, a retrospective topic identification model is presented with an improved weight estimation. It employes the value of BIC for clustering to improve the clustering accuracy. By dividing the time segments and removing isolated information point, the efficiency of the algorithm is further improved. The experimental results show that this method achieves good accuracy and efficiency in the topic detection of the short text information flow.

short text; information flow; topic identification; clustering

周泓(1980—)，硕士，讲师，主要研究领域为数据挖掘、计算机应用。E⁃mail：hong＿zhou@126．com刘金岭(1958—)，学士，教授，主要研究领域为数据挖掘、数据库应用。E⁃mail：liujinlingg@126．com王新功(1978—)，学士，讲师，主要研究领域为文本数据挖掘。E⁃mail：flash⁃mx2004@163．com

1003-0077(2015)01-0111-07

2013-02-28 定稿日期： 2013-07-28

河北省科技支撑计划项目(10213581)；淮安市社会发展项目(HASZ2012046)；淮安市科技支撑计划(工业)项目(HAG2012086)

TP391

A