短文本相似度研究及其在微博话题检测中的应用

黄贤英，陈红阳，刘英涛

（重庆理工大学 计算机科学与工程学院，重庆400054）

0 引 言

微博话题检测是微博短文本处理与学习的一个重要应用领域，话题检测的质量多受微博短文本相似度计算方法的影响。该类型的短文本具有不同的特点，因此，如何利用微博短文本的特点设计高效的短文本相似度算法至关重要［1－3］。

研究者针对短文本相似度展开了一系列研究，并取得初步的成果，这些方法也常用于度量微博短文本之间的相似性：文献 ［4］提出基于关键词重叠的方法，以单个关键词为语义单元度量文本之间的相似性，文本间共有关键词个数与其相似性成正相关，而短文本用语非规范化，特征极度稀疏，隐含信息难以挖掘，仅基于文本间共有的关键词数目度量文本的相似性存在一定的误差；文献 ［5］使用公共词块为语义单元，相较于关键词重叠方法可更好地度量短文本之间的相似性，却未考虑词块间的组合顺序对文本相似性的影响，且公共词块是由连续的词形相同或者词义相同的词项所组成的，公共词块的粒度较小；文献 ［6］以关键词为基本单元，考虑了关键词之间的语义相似性与组合顺序，提出从关键词的词义与词序的角度来计算文本相似度，但文本相似性度量的语义单元是单个的关键词，不具备独立完整的语义信息表达能力。然而，它们均未涉及到微博短文本自身所具备的一些特点，实际上微博文本的发布时间，文本之间的转发与评论等结构化信息［7，8］对文本间相似性度量也具有一定的贡献。针对微博短文本独有的特点，研究者提出了一些考虑微博短文本特点的相似性度量方法。周刚等［9］提出了基于微博短文本之间的转发与评论关系，微博发布者之间的关注与好友关系来衡量微博短文本之间的相似性以实现微博话题检测；骆卫华等［10］认为话题既具有语义特征，也具有时间特征，考虑了时间因素，引入了时间衰减函数，构建基于余弦相似度与时间相似度的文本相似性度量方法。这些方法均独特地从微博短文本的另一角度出发来衡量微博短文本之间的相似性，具有一定的借鉴意义。

本文依据影响微博短文本相似性度量的因素 （文本间内容主题相似性、文本讨论主题相关性），在新的基于公共块序列的短文本语义相似度的基础上，充分利用微博短文本的发布时间、文本间的转发、评论等信息，进而形成一种基于语义关系，时间关系和社交关系的相似度算法，多角度衡量微博短文本之间的相似性，然后将该算法应用于微博话题检测中以进一步提高话题检测的质量。

1 基于多视角的微博短文本相似度算法

微博短文本内容长度短、表达随意、非规范化等特点致使文本向量高维且有效特征稀疏，传统的相似度算法并不能精确地度量微博短文本之间的相似性，本文在基于公共块序列的短文本语义相似度的基础上，利用微博短文本的发布时间、转发评论等信息对该语义相似度模型进行修正，从而形成新的微博短文本相似度算法来度量文本之间的相似性。该算法首先简介公共块的定义以及如何寻找两微博短文本中的公共块；然后，在此基础上构建基于公共块序列的语义相似度；最后，使用微博短文本发布时间、转发与评论等信息来修正基于公共块序列的语义相似度。

1.1 寻找两微博短文本中存在的公共块

定义 公共块是指两个文本中词形与词义相同的连续的几个词项组合在一起的词块，公共块中至少包含一个词形相同或者词义相同的词项，其最大长度 （公共块中所含的最大词项总数）不超过较短的文本长度 （文本中所含词项总数），最小长度 （公共块中所含的最小词项总数）不低于1。

寻找两微博短文本中所存在的公共块的算法如下描述所示。

算法：寻找两微博短文本中存在的公共块的算法。

输入：微博 短 文 本D1＝｛a1，a2，...，am｝，D2＝｛b1，b2，...，bn｝

输出：存储微博短文本D1，D2中所存在的公共块的集合CommonBlocksList ＝ ｛terms1，terms2，...，termsr｝，（r＜＝min（m，n））

（1）构建二维相似度矩阵M ：采用基于 《知网》的词汇语义相似度方法［11］分别计算第一个词项集合中的每个词项与第二个词项集合中每个词项之间的语义相似度，以此构建二维相似度矩阵M ，如式 （1）所示

式中：sij——文本D1中第i个词项与文本D2中第j个词项之间的语义相似度值。

（2）构建词对集合WordsPairList：①遍历矩阵M ，寻找第一个最大相似度值 （大于0.5），依据该值在矩阵M中所处的位置 （行与列），记录其在两文本D1，D2中所对应的词对＜ai，bj＞（1≤i≤m，1≤j≤n），同时将该相似度值设置为0；②按照①中所述规则寻找下一个最大相似度值，并对相应的数据信息进行记录与更改，直至矩阵M 变为零矩阵；③找出两文本中存在的全部词对，并构建词对集合WordsPairList＝｛＜p1，q1＞，＜p2，q2＞，...，＜pk，qk＞｝，其中，k∈（0，min（m，n）），p1，p2，...，pk为微博短文本D1中的词项，而q1，q2，...，qk为微博短文本D2中的词项，＜pi，qi＞，（1≤i≤k）则为文本D1与D2中的第i个词项。

（3）构建公共块集合CommonBlocksList：①遍历词对集合WordsPairList，取出每一个词对中的第一个元素放入词项集合WordsList1，第二个元素放入词项集合WordsList2。将WordsList1＝｛p1，p2，...，pk｝中的元素按照其在文本D1中所处的先后顺序进行排序，且从1开始依次顺序编号，构成序列OrderList1＝｛l1，l2，...，lk｝，（li∈瓔，0≤i≤k）；将WordsList2＝｛q1，q2，...，qk｝中的元素按照其在文本D2中所处的先后顺序进行排序，然后根据词对中两个元素的对应关系，对经过排序后的元素，进行相应的数字编号以构成序列OrderList2＝｛t1，t2，...，tk｝，（ti∈瓔，0≤i≤k）；②遍历序列OrderList1，首先取前两个元素，判断其在序列OrderList2中所对应的两个元素是否也递增连续，若否，就从序列OrderList1中删除当前元素之前的元素，并将这些元素所对应的词项取出作为一个公共块，然后转②，直至序列OrderList1中的元素为空，转④，否则，转③；③继续遍历序列OrderList1中的下一个元素，看是否能和前面已知的元素组在一起构成公共块，若能，则继续遍历该序列OrderList1中的下一个元素，直至当前所遍历的元素与前面已知元素组合在一起不能相应地构成公共块，则取出当前元素之前的组合元素作为公共块，并将这些组合元素从序列OrderList1中删除掉，转②；④找出两微博短文本中存在的公共块，存储在公共块集合CommonBlocksList 中，它 可 表 示 为CommonBlocksList ＝｛terms1，terms2，...，termsr｝，（r ＜＝ min（m，n）），termsi（1≤i≤r）则表示该集合中的第i个公共块。

1.2 基于公共块序列的语义相似度

两个微博短文本所含公共块个数、块内部所含词项个数愈多，则它们的相似性就愈大；此外，公共块之间的组合顺序对文本之间的相似性也具有一定的影响。鉴于此，基于公共块所含词项总数与公共块之间的组合顺序共同度量文本之间的相似性如式 （2）与式 （3）所示

例如：微博文本D1－小明乘坐火车从河南郑州到陕西西安去同学家玩。微博文本D2－乘客选取乘坐飞机从陕西西安到河南郑州这条线路。公共块：乘坐，从，河南郑州，到，陕西西安。公共块在文本D1中的顺序向量r1：1，2，3，4，5；公共块在文本D2中的顺序向量r2：1，2，5，4，3。

基于公共块序列的语义相似度算法具体描述过程如下所示。

算法：基于公共块序列的短文本语义相似度算法。

输入：微博短文本D1，D2

输出：微博短文本D1，D2之间的相似度值SimCB

（1）微博短文本表示：将微博短文本D1，D2以词项集合的 形 式 进 行 表 示。D1＝｛a1，a2，...，am｝，D2＝｛b1，b2，...，bn｝，其中ai（1≤i≤m）表示微博短文本D1中的第i个词项，m 表示该文本的长度；bj（1≤j≤n）表示微博短文本D2中的第j个词项，n表示该文本的长度。

（2）寻找两微博短文本中存在的公共块：根据上述所描述的公共块寻找算法将两微博短文本中存在的公共块找出 并 以 集 合CommonBlocksList ＝ ｛terms1，terms2，...，termsr｝，（r＜＝min（m，n））的形式进行表示。

（3）基于公共块所含词项总数与公共块之间的组合顺序度量微博短文本之间的语义相似性按照式 （4）计算两微博短文本中的语义相似度值SimCB。

1.3 利用微博短文本的发布时间、转发与评论等信息修正基于公共块序列的语义相似度

（1）微博短文本之间的转发、评论等结构化信息蕴含着文本之间的相似性关系。从微博文本之间的社会化关系角度度量文本之间的相似性，避免了单一语义相似度的片面性。如果文本间存在转发与评论关系，则认为它们的相似度值为1，否则，基于微博短文本内容的角度分析、度量文本之间的相似性。

（2）微博话题具有时间聚集特性，通常，一定时间段内微博文本发布时间间隔距离越短，则它们归属于同一个话题的可能性就越大，相似性也越大。因此，从文本发布时间的角度衡量微博短文本之间的相似性，如式 （5）所示

式中：Simtime（D1，D2）——两微博短文本D1，D2之间的 时间相似度，而time1，time2——两文本所对应的发布时间。

综上所述，则基于微博短文本的发布时间对语义相似度进行修正：融合时间相似度与语义相似度来度量微博短文本在内容主题上的相似性，如式 （6）所示

α，β，γ分别表示为计算两个微博短文本之间语义相似度和时间相似度时各自所对应的加权系数，彼此间的关系为（α＋β＋γ＝1，α＞β＞γ），α，β见式 （4）。

利用微博短文本的发布时间、转发与评论等信息修正短文本语义相似度，以度量文本之间的相似性，具体描述过程如图1所示。

2 实 验

本文将新的基于多视角的微博短文本相似度算法应用在微博话题检测中，即融入该相似性度量方法于Single－Pass聚类算法［12］中实现微博话题的检测功能。它的具体流程如图2所示。

2.1 实验数据

图1 基于多视角的微博短文本相似度算法流程

图2 新的微博短文本相似度算法应用于微博话题检测中的流程

本实验所使用的数据主要来源于新浪微博中2013年08月04日至2013年08月19日所产生的数据，具体包括微博文本内容、发布时间、发布作者、回复数及转发数等，共计16个话题，4257条微博文本数据，其中16个话题分别为 “北京楼顶别墅主人”、“全国各地持续高温”、“斯诺登棱镜事件”等。

2.2 实验的评价指标

采用话题检测与跟踪的性能评价指标中的漏检率、误检率和归一化错误识别代价作为微博话题检测的性能评测指标［13］，此3个指标的计算方法如式 （7）所示

式中：Cmiss与Cfa——漏检率和误检率的代价系数，Ptarget与Pnon－target——先验目标出现的概率和先验目标不出现的概率，二者的和为1。通常，Cmiss与Cfa取值为1.0 和0.1；Ptarget为0.02。

本实验通过将16个微博话题对应指标取平均值来测试观察新的微博短文本相似度算法应用在微博话题检测中时各个性能指标。

2.3 结果与分析

为确定式 （6）中各个加权组合系数的取值，分别取（α，β，γ）的23种取值组合情况 （精度为0.5），观测在不同的组合情况下，将基于多视角 （时间、语义以及社会化关系）的微博短文本相似度算法应用于话题检测时的指标－错误归一化识别代价 （平均值），实验结果表明，只有当（α，β，γ）＝（0.45，0.35，0.2）时，该指标取得最小值0.1036。因此，将（α，β，γ）的取值确定为（0.45，0.35，0.2）。

在加权组合系数确定的情况下，进行实验一与实验二。

（1）实验一，将新的微博短文本相似性度量方法与文献［5］中的相似度方法、文献 ［6］中的相似度方法、基于公共块序列的语义相似度和时间相似度作对比，分别与Single－Pass聚类算法相结合来实现微博话题的检测功能，然后观察在各种不同相似性度量方法下，微博话题检测的平均漏检率、误检率与Norm（CDet）指标，具体的实验结果见表1。

表1 各相似性度量方法下的微博话题检测性能对比

从表1中可观测出，与Single－Pass聚类算法结合实现微博话题检测的功能时，基于公共块序列的语义相似度比时间相似度、文献 ［5，6］中的相似度方法相比，微博话题检测的各项指标均有所降低；且本文所提出的微博短文本相似性度量方法，相较于其它几种方法，各项指标也得到了较大程度的降低。这主要是因为，在对文本中词项之间词义与词序等语义关联信息加以考虑的情况下，基于公共块序列的短文本语义相似度相较于文献 ［5，6］中的相似性度量方法可以更准确地度量文本之间的相似性；此外，在该短文本语义相似度的基础上，充分利用微博短文本所具有的特点，基于微博短文本的发布时间、转发与评论等信息修正该语义相似度模型，从多个角度全面地刻画文本之间的相似性。因此，新的微博短文本相似度算法比传统的单一相似度算法能更好地测量出微博短文本之间的相似性，进一步降低了微博话题发现的漏检率、误检率与归一化错误识别代价等指标。新的文本相似性度量方法能够有效地提高微博短文本之间相似度计算的准确性。

（2）实验二，将基于Single－Pass聚类算法的微博话题检测方法与基于新的相似度算法＋Single－Pass聚类算法的微博话题检测方法作比较，实验结果见表2。

表2 各微博话题检测方法的性能对比

从表2中所显示出的数据，可以较为明显地观察出新的相似度算法与Single－Pass聚类算法结合使用时可以更好地降低话题发现的漏检率与误检率等指标。其原因在于本文的话题检测方法融入了新的基于多视角的微博短文本相似度计算方法，从微博文本的发布时间、社会化关系以及语义的角度来估量文本在内容上的相似性，社会化关系上的相关性，从而多角度地，更为准确地衡量了文本之间的相似性，在融入Single－Pass聚类算法中实现微博话题检测的功能时，有效地将讨论同一个话题的微博文本归入一类，从而更好地降低了微博话题检测的漏检率与误检率等指标。

3 结束语

本文在对词项之间的词义与词序等语义关联信息考虑的基础上，设计一种基于公共块序列的短文本语义相似度，为使其可以较好地衡量微博短文本之间的相似性，又对微博文本的转发与评论等结构化信息与时间信息加以充分利用，融合时间相似度与社交相似度以形成基于多视角的微博短文本相似性度量算法，从多个角度，更为全面、准确地衡量微博文本之间的相似性，最后结合Single－Pass聚类算法以检测微博话题，实验结果表明，微博话题检测的性能判断指标有一定幅度地降低，说明该微博短文本相似度算法准确地度量了微博文本之间的相似性，有效地提高了微博话题检测的性能指标。

［1］SHI Rui.Internet public opinion analysis for short text ［D］.Xi’an：Xidian University，2011 （in Chinese）.［时睿.面向短文本的网络舆情分析［D］.西安：西安电子科技大学，2011.］

［2］Rafeeque PC，Sendhilkumar S.A survey on short text analysis in web ［C］／／Third International Conference on Advanced Computing，2011：365－371.

［3］JIANG Shengyi，MAI Zhikai，PANG Guansong，et al.A survey of Micro－blog data mining ［J］.Library and Information Service，2012，56 （17）：136－142 （in Chinese）. ［蒋盛益，麦志凯，庞观松，等.微博信息挖掘技术研究综述 ［J］.图书情报工作，2012，56 （17）：136－142.］

［4］WU Quan’e，XIONG Hailing.Method of sentence similarity computation by integrating multi－features［J］.Computer Systems and Applications，2010，19 （11）：110－114 （in Chinese）.［吴全娥，熊海灵.一种综合多特征的句子相似度计算方法 ［J］.计算机系统应用，2010，19 （11）：110－114.］

［5］WANG Dong，XIONG Shihuan.Sentence similarity computing with different semantic unit measure ［J］.Journal of Xinyang Normal University，2014，27 （1）：145－148 （in Chinese）.［王东，熊世桓.用不同语义单元度量的句子相似度计算 ［J］.信阳师范学院学报，2014，27 （1）：145－148.］

［6］JIANG Chao.A Micro－blog recommendation system based on user clustering and semantic dictionary ［D］.Zhejiang：Zhejiang University，2013 （in Chinese）.［蒋超.基于用户聚类和语义词典的微博推荐系统 ［D］.浙江：浙江大学，2013.］

［7］FANG Yixiang.Research on multi－view topic detection method in twitter ［D］.Harbin：Harbin Institute of Technology，2012 （in Chinese）.［方一向.多视图微博话题检测方法研究［D］.哈尔滨：哈尔滨工业大学，2012.］

［8］YANG Wu，LI Yang，LU Ling.Micro－blog hot topics detection method based on user role orientation ［J］.Journal of Computer Applications，2013，33 （11）：3076－3079 （in Chinese）.［杨武，李阳，卢玲.基于用户角色定位的微博热点话题检测方法 ［J］.计算机应用，2013，33 （11）：3076－3079.］

［9］ZHOU Gang，ZHOU Hongcheng，XIONG Xiaobing，et al.MB－SinglePass：Micro－blog topic detection based on combined similarity ［J］.Computer Science，2012，39 （10）：198－202（in Chinese）.［周刚，周鸿程，熊小兵，等.MB－SinglePass：基于组合相似度的微博话题检测 ［J］.计算机科学，2012，39（10）：198－202.］

［10］LUO Weihua，YU Manquan，XU Hongbo，et al.The study of topic detection based on algorithm of division and multi－level clustering with multi－strategy optimization ［J］.Journal of Chinese Information Processing，2006，20 （1）：29－35 （in Chinese）.［骆卫华，于满泉，许洪波，等.基于多策略优化的分治多层聚类算法的话题发现研究 ［J］.中文信息学报，2006，20 （1）：29－35.］

［11］LIU Qun，LI Sujian.Word’s semantic computation method based on Hownet［J］.Computational Linguistics and Chinese Information Processing，2007，31 （7）：59－76 （in Chinese）.［刘群，李素建.基于 《知网》的词汇语义相似度计算 ［J］.计算机语言学及中文信息处理，2007，31 （7）：59－76.］

［12］LIU Gongshen，MENG Kui，XIE Jing.An improved topic detection method for Chinese Micro－blog based on incremental clustering ［J］.Journal of Software，2013，8 （9）：2313－2320.

［13］SUN Shengping.Research on Chinese Micro－blog hot topic detection and tracking ［D］.Beijing：Beijing Jiaotong University，2011 （in Chinese）.［孙胜平.中文微博客热点话题检测与跟踪技术研究 ［D］.北京：北京交通大学，2011.］