MB-SinglePass_基于组合相似度的微博话题检测

第３９卷第１０期２０１２年１０月

计算机科学

Ｃｏｍｐｕｔｅｒ

Ｓｃｉｅｎｃｅ

Ｖ０１．３９Ｎｏ．１０

Ｏｃｔ２０１２

ＭＢ—ＳｉｎｇｌｅＰａｓｓ：基于组合相似度的微博话题检测

周

（软件开发环境国家重点实验室

刚１’２

邹鸿程２熊小兵２黄永忠２

（信息工程大学信息工程学院

郑州４５０００２）２

北京１００１９１）１

摘要话题检测技术在传统媒体的研究中取得了较好的效果。探讨了针对微博类的新型媒体短文本对象话题检测

技术的优化及性能评价。基于微博中联系人存在的关注和粉丝等结构化信息、帖子之间转发评论等内在关联关系，提出了针对微博的Ｍ＆ｓｉｎｇｌｅＰａｓｓ话题检测算法。该算法除了考虑微博上述特点之外，还针对短文本特征稀疏的问题，利用同义词典，引入了微博特征扩展技术，丰富了特征信息。同时，针对单一使用余弦相似度、雅各比相似度争语义相

似度的不足，采用了组合相似度策略。相较传统算法，ＭＩ｝Ｓｉｎ９１ｅＰａｓｓ算法在新浪微博实测数据集上取得了更好的性能。另外，针对相似度策略的对照实验说明采用组合相似度的效果优于单一相似度。关键词微博，Ｓｉｎ９１ｅＰａｓｓ，话题检测，文本相似度，同义词扩展中图法分类号ＴＰ３９１

文献标识码Ａ

Ｍ弘ＳｉｎｇｌｅＰ嬲ｓ：Ｍｉｃｒｏｂ№ＴｏｐｉｃＤｅｔｅｃｔｉ仰Ｂａｓｅｄ

ｚＨ０ｕＧａｎ９１，２

ｚＣｌＵ

ｏｎ

Ｃ蛐ｂｉｎｅｄ

ＨｕＡＮＧ

ＳｉＩＩＩｉｌａｒｉｔｙ

Ｈｏｎｇ＿ｃｈｅｎ酽

ｘ１０ＮＧ

ｘｉａ伊ｂｉｎ矛Ｙｏｎｇ＿ｚｈｏｎ酽

（ＳｔａｔｅＫｅｙＬａｂｏｒａｔｏｒｙｏｆＳ０ｆｔｗａｒｅＤｅｖｅｌｏｐｍｅｎｔＥｎｖｉｒｏｎｍｅｎｔ，Ｂｅ巧ｉｎｇ１００１９１，Ｃｈｉｎａ）１

（Ｉｎｆｏｍａｔｉｏｎ

Ａｂｓｔｒａｃｔａｎｄ

ＥｎｇｉｎｅｅｒｉｎｇＩｎｓｔｉｔｕｔｅ，ＩｎｆｏＨｎａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇＵｎｉｖｅｒｓｉｔｙ，Ｚｈｅｎｇｚｈｏｕ４５０００２，Ｃｈｉｎａ）２

Ｔｏｐｉｃｄｅｔｅｃｔｉｏｎａｃｈｉｅｖｅｓｑｕｉｔｅｇｏｏｄｒｅｓｕｌｔｉｎｔｈｅ

ｔｒａｄｉｔｉｏｍｌｍｅｄｉａ

ｒｅｓｅａｒｃｈＴｈｉｓｐａｐｅｒｄｉｓｃｕｓｓｅｄｔｈｅｒｅｆｉｎｅｓｓ

ｓｕｃｈ

ａｓ

ａｓ

ｐｅｒｆｏ舢ｎｃｅｅｖａｌｕａｔｉｏｎｏｆｔｈｅｔｏｐｉｃｄｅｔｅｃｔｉｏｎｔｅｃｈｎｉｑｕｅｉｎｔｈｅｎｅｗｋｉｎｄｏｆｍｅｄｉａｓ

ｔｏｐｉｃｄｅｔｅｃｔｉｏｎａｌｇｏｒｉｔｈｍ

ｏｎ

ｍｉｃｒｏｂｌｏｇ，ｐｒｏｐ０Ｓｅｄｔｈｅ

ＭＢＳｉｎ９１ｅＰａｓｓ

ｔｈｅｂａｓｉｓｏｆｔｈｅ

ｓｔｒｕｃｔｕｒｅｄ础ｏｍｌａｔｉｏｎ

ａｓ

ｓｕｃｈ

ｔｈｅｒｄａｔｉｏｎＳｈｉｐｓｏｆａｔｔｅｎ－

ｔｉｏｎｓａｎｄｆａｎｓｂｅｔｗｅｅｎｃｏｎｔａｃｔｓ，ｔｈｅｉｎｎｅｒｓｉｄｅｃｏｎｓｉｄｅｒｉｒｌｇｔｈｅａｂｏｖｅｍｉｃｒｏｂｌｏｇｏｒｄｅｒｔｏ

ｔａｇｅ

ｃｏ肌ｅｃｔｉｏｎ

ｒｅｌａｔｉｏｎｓｈｉｐｓｓｕｃｈｆｏｒｗａｒｄｉｎｇａｎｄｃｏＩｎｍｅｎｔｂｅｔｗｅｅｎｐｏｓｔｓ．王ｋ—

ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ，ＭＢＳｉｎｇｌｅＰａｓｓ

Ａｔｔｈｅｓａｍｅ

ｉｎｔｒｏｄｕｃｅｓｔｈｅｃｈａｒａｃｔｅｒｉｓｔｉｃｓｅｘｔｅｎｓｉｏｎｔｅｃｈｌｌｉｑｕｅ证

ｕｓｅｄｔｈｅｃｏｍｂｉｎｅｄｓ．ｍ［１ｉｌａｒｉｔｙａｉｌｌｌｉｎｇ

ａｎｄｓｅｍａｎｔｉｃ

ａｔ

ｅ商ｃｈ

ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ

ｉｎｆｏｍａｔｉｏｎ

ｔ．皿ｅ，ｔｈｅｐａｐｅｒ

ｔｈｅｓｈｏｒ＿

ｏｆｓｉｎ９１ｙｕｔｉｌｉｚｉｎｇｔｈｅＪａｃｃａｒｄ

ｓ确ｌａｒｉｔｙ

ｃｏｅｆｆｉｃｉｅｎｔ，ｃｏｓｉｎｅｂａｓｅｄ

ｔｈｅｔｒａｄｉｔｉｏｎａｌ

ａｌｇｏｒｉｔｈｍｓ，ＭＢＳｉｎ９１ｅＰａｓｓ

ｔｏ

ｓｈｏｗｓｂｅｔｔｅｒ

ｓｔｒａｔｅｇｙ

ｐｅｒｆｏ蚴ｃｅ。ｎ

ｓｉｒＩｌｉｌ撕ｔｙ

ｓ砒ｌａｒｉｔｙ．（乃ｍｐａｒｅｄｗｉｔｈ

Ｉｎｊｃｒｏｂｌｏｇ．Ａｄｄｉｔｉｏｍｌ—

ｔｈｅａｃｔｕａｌｄａｔａｓｅｔｏｆｓｉｌｌａ

ｌｙ，ｅｘｐｅｒｉｍｅｎｔａｃｃｏｒｄｉｎｇ１ａｒｉｙ．

ｔｈｅ

ｓ试ｌａｒｉｔｙ

ｒｅｖｅａｌｓｂｅｔｔｅｒｒｅｓｕｌｔｂｙｕｓｉｎｇｃｏｍｂｉｎｅｄｓｉＩｎｉｌａｒｉｔｙｔｈａｎｓｉｎｇｕｌａｒ

ｓｈｉ一

Ｋｅｙｗ删ｓ

１

Ｍｉｃｒｏｂｌｏｇ，ＳｉｎｇｌｅＰａｓｓ，Ｔｏｐｉｃｄｅｔｅｃｔｉｏｎ，ＴｅＸｔｓｉｍｉｌａｒｉｔｙ，岛ｍｏｎｙｍｓｅＸｔｅｎｓｉｏｎ

引言

自微博问世以来，其因实时移动、简短快捷和互动方便等

ｋｉｎｇ）组织的任务划分，话题检测技术属于ＴＤＴ的一项子任

务［１］。话题检测又称主题检测，其目的是对一系列连续的文本流自动检测出不同的话题。它本质是一种无指导的聚类。

向量空间模型（ＶＳＭ）是文本形式化的主要模型之一［１］。通过将文本映射到多维空间，使得对文本相似比较计算有了可

特点迅速风糜全球。例如，国外著名的微博网站ｔ试ｔｔｅｒ用户突破Ｌ７亿，每天锐推数量超过１．３亿条。国内首个微博网站新浪微博也以极快的速度在发展。微博上通过相互关注、转发评论等行为形成了一个庞大的社交网络。微博文本限制

行性。话题检测算法常用的方法有ａｇｇｌｏｍｅｒａｔｉｖｅ算法［２］、增

量聚类算法［３｜、增量Ｋ＿ｎ瑚ｎＳ算法［“、基于主题模型算法［５］

等。相似度计算的方法常采用余弦夹角、雅各比公式、０ＫＡ—ＰＩ公式、Ｃｌａｒｉｔｙ、Ｔａｎｉｒｎｏｔｏ、Ｈｅｌｌｉｎｇｅｒ公式等西，引。随着自然

在１４０个字以内，一般即时发布，因此微博语言呈现出个性

化、符号化、口语化、非规范化的特点，也产生了很多新鲜词汇，比如“神马”、“给力”等，从某种程度上引领了一种社会文化。

根据ＴＤＴ（话题检测与追踪，Ｔｏｐｉｃ

到稿日期：２０１１—１２一０７返修日期：２０１２一０３一０６（８６３）计划（２００９ＡＡ０４３３０３）资助。

Ｅ电ｔｅｃｔｉｏｎａｎｄＴｒａｃ—

语言处理技术的发展，基于语义相似度的相似度模型也开始

流行［８］。这些相似度计算方法各有利弊。

话题检测与追踪技术在传统研究对象如新闻、论坛和博

本文受软件开发环境国家重点实验室开放课题（ｓＫＩｓＤＥ．２０１１ＫＦ＿０６），国家高技术研究发展

周刚（１９７４一），男，博士，副教授，ＯｃＦ会员，主要研究方向为海量信息处理、云计算、社会网络分析，Ｅ－ｍａｉｌ：ｇｚｈｏｕｇｚｈｏｕ＠ｇｍ“Ｉ．ｃｏｍ；邹鸿程（１９８５～），男，硕士生，主要研究方向为网络数据挖掘；熊小兵（１９８５一），男，博士生，主要研究方向为网络数据挖掘；黄永忠（１９６８一），男，博士，教授，博士生导师，主要研究方向为分布式系统、云计算、海量信息处理。１９８ 万方数据

客等文本较长的媒体中取得了较好的效果。在微博平台上，由于帖子文本内容较短，使得产生特征稀疏问题，给话题检测与技术追踪技术的应用带来了较大的挑战。但是，微博平台自身具有的特点为话题检测与追踪技术研究带来了新的思路，这也是本文研究的出发点。首先，随着自然语言处理相关技术的发展，同义词扩展技术得到发展［９］，并且取得了较好的效果。本文利用该技术对微博文本进行特征扩展，尝试解决特征稀疏的问题。其次，微博平台具备一些传统媒体不具有的特性，如用户之间关注行为、用户相互转发评论行为等。这些结构化特征为研究话题检测与追踪技术带来了新的机遇。在微博主题检测中可以充分利用这些结构化信息辅助判断，以提高主题检测的性能。再有，如前所述，相似度策略各有优缺点，于是，本文提出了组合相似度的方法。它融合了余弦相似度、雅各比相似度和语义相似度３种策略。这是基于以下

３点考虑：第一，余弦相似度采用的是对特征进行ＴｐＤＦ数

量化后再进行计算的策略；而雅各比相似度仅仅利用特征数量统计结果进行相似度计算；语义相似度则是基于知识库的相似度计算方法。这３种方法角度各异，有着本质的区别。第二，余弦相似度和雅各比相似度在计算特征相互不重合的两个文本时，会直接得出其相似度为ｏ，而实际在微博上这两

条帖子可能讨论一个相关的事件，从而造成误判。如果引入

语义相似度策略，则可以减少其中的误差。第三，由于知网等知识库收录的登录词汇有限，语义相似度存在相似性判断不

够精确的问题。因此，融合３种方法可以从多个角度综合地

刻画文本的相似特征，避免单一方法的不足，从而提高文本相似度计算的准确性。

本文的主要工作如下：

１．提出了组合相似度策略，充分利用不同相似度策略的优点，同时规避其缺点。

２．针对微博特点，提出了ＭＢＳｉｎｇｌｅＰａｓｓ算法，结合帖子

转发回复的信息，对帖子的类别进行判断。同时，针对微博特

征稀疏问题，利用《同义词林》对关键词进行特征扩展，丰富了微博文本的特征。

３．通过在新浪微博实际数据集上测试，ＭＢＳｉｎｇｌｅＰａｓｓ算

法显示出较好的话题检测性能。

２

Ｍ弘ｓｉｎ出ｅＰａＳｓ话题检测算法

２．１基于同义词扩展的帖子特征模型

帖子形式化的一般步骤是对帖子进行分词，去除停用词，

统计并计算词的ＴＦ－口阿权重。经过形式化，每个帖子与一

个多维向量相对应，见式（１）：

加是～（Ⅵ１，Ⅵ２，…，砜，％）

（１）

式中，足表示词空间大小，即向量空间的维度；Ｋ表示帖子ｉ

中词ｊ的ＴＦ＿ＤＦ权重，根据式（２）计算得出［１０］：

＿＜

◇ｑ２ｔ３ｂ’记ｌｌ

九

八ｒ

（２）

ｌ￡厶一最，ｉ玎２ｌｇ（詈＋ｏ．０１）

式中，￡＾ｆ表示词ｊ在帖子ｉ中的词频，ｑ表示词Ｊ在帖子ｉ出

现的次数，Ｍ表示帖子ｉ的总词数，Ｎ表示总的帖子数，以表

示出现词ｉ的帖子数。ｏ．ｏｌ是为了避免出现Ｏ值而设定的一个常量。

由于微博帖子较为简短，特征本身就比较稀疏，为了尽可

万方数据

能地利用特征信息，本文借助《同义词林》对主题的关键词向

量进行特征扩展，使关键词特征数量扩大２倍以上。本文设定各扩展特征的权重与其来源特征的权重相同。２．２主题模型

在基于向量空间模型的主题模型中，主题是由一簇帖子组成的。所以，主题向量的物理意义可以理解为主题里各帖子向量的叠加向量的平均，如图１所示。具体的主题向量生成过程是：

１．对各个主题簇内的帖子进行分词，去除停用词，去重并

计算ＴＦ＿口ＤＦ权重形成初始主题向量。

２．对经过步骤１之后形成的关键词进行特征扩展，形成

更丰富的特征向量。

３．对主题内扩展后的文本向量进行叠加平均，得到的向量即为主题向量。

图１主题向量示意图

２．３组合相似度策略２．３．１知网语义相似度

《知网》是一个以汉语和英语的词语所代表的概念为描述对象，以揭示概念与概念之间以及概念所具有的属性之间的关系为基本内容的常识知识库［１１］。

《知网》中有两个主要的概念：“概念”与“义原”。“概念”

是对词汇语义的一种描述。每一个词可以用一个或多个概念来描述。“概念”在知网里是用“知识表示语言”来描述的。

“义原”是描述“概念”的最小意义单位，也是“知识表示语言”

所用的“词汇”。与其他语义词典不同，《知网》并不是简单地将所有的“概念”归结到一个树状的概念层次体系中，而是试图用一系列的“义原”来对每一个“概念”进行描述。

本文使用的语义相似度方法参考了刘群、李素建的论

文——基于《知网》的词汇语义相似度计算口”，其中，针对知

网收录词，语义相似度计算包括以下几种情况：

１．实词与虚词相似度为ｏ。

２．虚词概念只有｛句法义原）或者｛关系义原｝两种描述方式，因此，两个虚词概念之间的相似度等于对应句法义原或关

系义原之间的相似度，见式（３）：

ｓｈ（众，Ａ）２南

（３）

式中，ｄ表示义原ｐ，，户。在知网义原层次体系中的路径长度，

口是一个可调节参数。

３．实词概念可以用４种不同义项类型来描述，第一种是第一基本义原描述式，是对实词最重要的一种描述；第二种是

除第一基本义原之外的其他基本义原描述式，是一个义原集合；第三种是关系义原描述；第四种符号义原描述。一般地，

两个实词概念之间的相似度可由式（４）来计算：

４

ｉ

ｓｈ（ｓ－，ｓｚ）一郛盟ｓｉ岫（ｓ ，ｓｚ）

（４）

１９９

式中，ｓ嘶（５，，Ｓｚ）（歹一ｌ，２，３，４）表示Ｓｔ和Ｓ２两个概念对应

上述４种不同义项的两两相似度。届是可调节的参数，且满足：Ｊ臼ｌ＋屈＋届＋庳一１；屉＞屉＞届＞厚。这种参数设置方法的意义是使主要义项的相似度对次要义项的相似度进行制约，维持主要义项相似度对整体相似度的主要贡献地位。例

如，如果次要义项相似度高，主要义项相似度低，那么整体相

似度也不会受到次要义项的太大影响。

针对知网未收录词，本文采用以下方法进行处理：１．对于人名

如果两个人名姓氏部分相同，则认为两者具有高相似度，如潘石屹、老潘和潘总；

如果两个人名除姓氏部分相同，则认为其具有较高相似度，如吴菊萍和菊萍；

对于外籍人名，如果存在部分相同匹配，则认为其具有较

高相似度，这主要考虑了外来词音译带来的误差，如本拉登、拉丹和本拉丹。

２．对于地名

针对知网只收录市一级及以上行政区域地名的限制，手工编制各地区简称及下属县、区地名表。对于市级以下行政级别之间的相似度，通过分别将其提升到对应的知网收录的市级以上行政区域进行相似度计算。如郑州金水区与北京朝阳区相似度，可以用知网收录词郑州与北京的相似度来近似。同时，规定属于同一市的各级行政地名之间相似度为１。如金水区与郑州市。

３．对于机构组织

对于机构组织存在简称的情况，如果两个机构名称通过了部分相同匹配，则不加区别，即相似度为１。如“住建部”与“住房与城乡建设部”相似度为ｌ。

４．其他情况

除以上情况之外，如果两个知网未收录词相同，则相似度为ｌ，否则为ｏ。２．３．２组合相似度

常用的相似度计算方法有余弦相似度、雅各比相似度ｍ］、语义相似度吲等。具体地：

余弦相似度的定义为：

ｓｉｒｎ。（加毋，加町）一—芋Ｌ—］广∑‰×Ｖｈ

（５）

（∑垤）（∑瞧）

ｎ—ｌ

Ｈ＝ｌ

雅各比相似度的定义为：

她ｃ搬，溉，一摆君剁

㈣

式中，１加ｓｎ加墨Ｉ表示帖子ｉ和帖子Ｊ的公共特征数量，

ＩｐｏｓｉＵ加ｓｌ表示帖子ｉ和帖子Ｊ的不同特征数量。借鉴信息融合中的顺序加权思想，语义相似度的定义如下：

设帖子ｉ含有优个关键词，对应的权重为让，，让。，…，

‰，见式（７）：

夕ｏＲ～［瑚，矗｛１／让１，ｔ￡舫，ｄ挖／诎２，…，ｔ￡耵ｒ矗拥／‰］

（７）

帖子ｊ含有咒个关键词，对应的权重为ｑ。，ｑｚ，…，％，见式（８）：

户。昌～［ｕｏｒ谚１／功１，伽，磅２／功２，…，ｔｃＤ，矗＿／芑铀］

（８）

则帖子ｉ与帖子Ｊ的语义相似度归一化表示见式（９）（由于对

称性，不妨假设ｍ≥竹，反之亦然）：

万方数据

２００

ｆｓｍ‰晡（多Ｄ嚣，户ｏＳ）２

ｌ竺！！堕呈垒！！塑型盟！之箜ｆ２±：：：±！垒！鱼坠曼！里！！塑型丝！堂皇墨２

１

墨％

Ｌｓｉｍｓｅｎｌ（御刑≥，声Ｄ５ｆ）一ｍａｘ｛ｓｉ芏工ｌｓｅｎ２（氆移托乙，豇船，矗露）（９）

式中，Ｚ一１，２，…，竹；ｒ＝１，２，…，ｍ；ｓｉｍｓｅｎ２（伽磁，伽以ｊ）表示词ｉ和词歹的相似度；ｓｂｓｅｎｌ（咖 磁，ｐｏ彤）表示词ｉ和帖子

歹的相似度。

如引言所述，这３种相似度的思想和角度不同，而且仅单

一使用一种相似度都存在一些不足。本文基于以上认识，提

出了组合相似度策略，见式（１０）：

ｓｈ．。ｂ（ｐｏ毋，户ｏＳ）＝ｓｉ如Ｉｃ。。（户。甄，户。町）×ａ＋ｓｉｎｌ豇（户。矗，

ｐｏ唧）×ｆ件ｓｉｒＩｌ掣撕（户。瞬，户。町）×７

（１０）

式中，口，口，ｙ表示加权系数，反映了３种不同相似度对总体相

似度的贡献大小。

２．４主题模型的更新策略

随着帖子依次流人，帖子数量发生变化的对应主题的向量也相应地得到更新。但是，新帖子的加入可能是正确的一

种划分，即相关帖子；也可能是不正确的划分，即伪相关帖子。如果仅仅使用新帖子集合的叠加向量作为来更新主题向量，会存在较大的误差。因此，本文在算法过程中，保留各主题的

历史向量，并将历史向量加入主题更新模型。各历史向量对

最新主题模型的贡献随着时间的推移和更新次数的增加逐渐

衰减。基于以上思想，给出主题更新模型如下：不妨假定当前

是第他次更新主题模型，当有新帖子划分到话题时，该主题模型按式（１１）更新；若没有新帖子加入话题，主题向量与前一次

的主题向量相同。

‘ｎ

Ｌ＝ＥＬ—了—一

∑∞ｔ＋％—刎

＂

（１１）

、１ｌ，

∑豳

式中，ｍ表示主题向量的加权系数，它是一个与更新次数有关

的参数，定义为式（１２）：

啦：士

啦。茅千雨

（１２）（１ｚ）

Ｅ表示第ｉ次更新的主题向量，Ｌ。表示第挖次主题临

时向量，它是由新帖向量与Ｌ一，叠加而成。即

ＴＩ。。＝Ｖ＋Ｌ一１

（１３）

式中，Ｖ是第’２次新来的帖子向量。

２．５

ＭｍＳｉｎ—ｅｎ啜算法流程

基于向量空间模型的话题检测常采用的方法是双阈值算

法，又称ＳｉｎｇｌｅＰａｓｓ算法［１］，其主要思想是通过设立聚类阈值％和创新阈值砂。两个门限来判别将帖子归入某个类别或创

建一个新类。由于微博的特殊性，本文将微博帖子的转发评

论关系、联系人的相互关注关系等辅助信息加入算法辅助考虑，提出了ＭＢＳｉｎ９１ｅＰａｓｓ算法。ＭＢＳｉｎｇｌｅＰａｓｓ算法过程如

图２所示，具体描述如下：

ｓｔｅｐｌ初始化处理。主要包括对帖子进行分词、去除停

用词、去重、计算ＴＦ－ⅢＦ权重等处理。

Ｓｔｅｐ２特征扩展。采用《同义词林》词典对帖子特征进行扩展。扩展特征的权重与原特征的权重相同。

Ｓｔｅｐ３依次读取到来的帖子向量，若是第一条帖子，则创建新话题。如果不是，转Ｓｔｅｐ４。

Ｓｔｅｐ４判断新帖子与当前已判断的帖子是否存在转发评论关系，如果有，则直接归人相应话题，并更新保存话题向量；如果没有，则计算新帖子与各话题向量的最大相似度。如果最大相似度大于聚类阈值让，则归入相应话题，并更新保存话题向量，转Ｓｔｅｐ６；否则，转入ｓｔｅｐ５。

ｓｔｅｐ５判断最大相似度与创新阈值％之间的关系，如果其值小于创新阈值％，则创建新话题，转Ｓｔｅｐ６；否则，判断

新贴子与对应最大相似度话题内帖子的发贴人是否存在关注

和好友关系，如果存在，则归人相应话题类，并更新保存话题向量，转Ｓｔｅｐ６；如果不存在，帖子归入相应话题类，但不更新

话题向量，以上一次话题向量当作本次话题向量，同样保存当

前的主题向量记录，以便用于下一次更新话题向量。转

ｓｔｅｐ６。

Ｓｔｅｐ６判断是否为最后一条帖子，若不是，转入Ｓｔ印３；若是，结束算法。

输入：按发帖时间顺序依次读入帖子ｐｏｓｌ，ｐｏｓ２，…，ｐｏｓ。输出：各个帖子话题簇Ｃ１，Ｃ２，…

１．｛预处理：分词、去停用词、去重、赋权、同义词扩展）

２．ｃｏｕｎｔ一１；

３．Ｃ１＋ｐ０８】；

４．ｓａｖｅ

Ｔ［１］１；

５．ｒｅｐｅａｔ６．ｃｏｕｎｔ＋＋；７．ｉｆ（ｐｏｓ。。与已判断帖子ｔ存在转发评论关系）ｔｈｅｎ

８．ｐｏｓ—。归人帖子ｔ所在话题簇ａ；

９．ｕｐｄａｔｅａｎｄｓａｖｅ

Ｔ［ａ］ｃ０呲；

１０．ｕｐｄａｔｅ

ａｎｄ

ｓａｖｅ

Ｔ［ｏｔｈｅｒ］∞岫ｔ；

１１＿ｅｎｄ１２．ｅｌｓｅ

１３．

［ｍａｘｓｉｍ，ＣｌｕｓｔｅｒＮｏ］一ＣａｌＭａｘｓｈ（ｐｏｓ。。ｔ，Ｔ口）；／／计算最大相似度ｍａｘｓｉｍ及对应簇号ＣｌｕｓｔｅｒＮｏ

１４．ｉｆ（ｍｓｉｍｘ＞ｖｃ）ｔｈｅｎ

１５．ｐｏｓｏｏ眦ｃ归入ａｕｓｔｅｒＮｏ簇１６．ｕｐｄａｔｅａｎｄｓａｖｅ

Ｔ［ｃｌｕｓｔｅｒＮｏ］∞呲ｔ；１７．ｕｐｄａｔｅ

ａｎｄ

ｓａｖｅ

Ｔ［ｏｔｈｅｒ］∞∞ｔ；

１８．ｅｎｄ

１９．ｅｌｓｅｉｆ（ｍａｘｓｉｍ＜ｖｎ）ｔｈｅｎ

２０．ｃｒｅａｔｅ

ｃｌｕｓｔｅｒｎｅｗａｎｄ

ｓａｖｅ

Ｔ［ｎｅｗ］；

２１．ｕｐｄａｔｅ

ａＩｌｄ

ｓａｖｅ

Ｔ［ｏｔｈｅｒ］∞帅ｔ；

２２．ｅｎｄ２３．

ｅｌｓｅ

ｉｆ（ｐｏｓ—。与ａｕｓｔｅｒＮｏ簇内已判断帖子发贴人存在关

注或粉丝关系）ｔｈｅｎ

２４．ｐｏｓ。岫ｔ归入Ｃ１ｕｓｔｅｒＮｏ簇；

２５．ｕｐｄａｔｅａｎｄ

ｓａｖｅ

Ｔ［ｃｌｕｓｔｅｒＮｏ］；

２６．ｕｐｄａｔｅａｎｄ

ｓａｖｅ

Ｔ［ｏｔｈｅｒ］咖ＩＩ；

２７．ｅｎｄ２８．ｅｌｓｅ

２９．ｐｏｓ∞ｔ归入ＣＩｕｓｔｅｒＮｏ簇；

３０．Ｔ［Ｃ１ｕｓｔｅｒＮｏ］㈣一Ｔ［ｃｌｕｓｔｅｒＮｏ］。咖ｔ一１；

３１．ｓａｖｅ

Ｔ［ａｕｓｔｅｒＮ０］∞岫ｔ；

３２．

ｕｐｄａｔｅａｎｄ

ｓａｖｅ

Ｔ［ｏｔｈｅｒ］。眦；

３３．ｄｌｄ３４．ｅｎｄ３５．ｅｎｄ３６。

ｅｎｄ

３７．ｕｎｔｉｌ（ｃｏｕｎｔ＞ｎ）

图２

Ｍ艮Ｓｉｎ９１ｅＰａｓｓ算法

万方数据

为了更加清晰直观地表示各步骤之间的关系，图３给出了ＭＢ－ｓｉｎｇｌｅＰａｓｓ算法流程图。

图３

Ｍ＆ＳｉＴｌｇｌｅＰａｓｓ算法流程图

２．６评价方法

本文评价方法采用ＮＩＳＴ建立的话题检测与追踪的评价方法，主要的性能指标包括准确率、召回率、漏检率、误检率、

准确率和召回率的综合指标Ｆ１侧ｓ“化以及模型指标

ＮＤｒｍ（ＣＤ。）。各指标计算公式如下［１］：

准确率Ｐ一≠ｂ（１４）召回率Ｒ５丢乞

（１５）漏检率‰２南

（１６）误检率ＰＦＡ一崩与

（１７）

Ｎｏ瑚ｃ％，一坠意《鼍曼者争

Ｆ１＿一…＝；黑

（１８）

（１９）

式中，口为检测到的帖子数，６为检测到的不相关帖子数，ｃ为检测到的相关帖子，ｄ为检测到的不相关帖子。一般地，Ｇ幽

取为１，ＣＦＡ取ｏ．１，Ｐ越恻取０．０２，只一啊取Ｏ．９８。

３实验及结果分析

３．１数据采集及预处理

本文以新浪微博为实验平台，采集了清华百年校庆、房地产调控、个税起征点上调、盈江地震、药家鑫事件、杭州最美妈妈、北京地铁事故、本拉登遇袭身亡、日本核辐射、威廉王子大婚等１０个热点话题共１０８９８１条帖子数据，以及发贴时间、相

应的发贴人及其帖子之间是否存在转发评论等信息。为了更好地测试算法，从每个话题中人工地挑选了１００条帖子质量好的数据共计１０００条帖子进行测试。转发评论关系主要根

据新浪微博里的转发标志“／／＠”来进行识别，即标志前的帖

２０】

子是对标志后帖子的转发评论。为ｒ获得发贴人之间的关注和粉丝关系，选定实验帖子后，通过正则表达式析取出发贴人ｍ号，进一步获得并建立所有发贴人的关注和粉丝列表，以便在算法过程中匹配发贴人关系。

针对待测试的帖子，采用分词工具对其进行分词、对分词结果去除停用词、去重，并计算每个词的ＴＦ－ｍＦ权重，最后采用同义词典对帖子特征进行扩展，并赋予权重。中文分词工具采用的是中科院ＩＣＴＣＬＡｓ２０１ｌ提供的ＪＮＩ接口，同义词典采用的是哈工大信息检索研究室的同义词词林扩展版。去除停用词是在构建一个停用词典的基础上进行的，该词典还包括微博常用表情符号等，共有４８７个词。基于此词典，匹配并过滤帖子中存在的停用词。

为了确定组合相似度的加权系数，分别对Ｄ＋口＋），＝１且口，风７＞０的３６种取值可能情况（精度为Ｏ．１）测试Ｍ侈Ｓｉｎ—

麟舣～舱一枞删，触¨＂．ｄ７

６

：ｉ

ｏｏｏ

＿！Ｊ１＿－Ｉ斛黧｛ｌ曩腓¨㈣

ｍｉ

●宰一”姑珏～

Ｉ议且ｎ

ｏ

．幢¨∞姑一串啡ｓ盯

．，¨㈨ｈ吖㈣撼

图５不同相似度策略下ＭＢｓｉ嘲ｅＰａｓｓ算法的性能比较

在同一实验参数和检测算法情况下，通过测试比较，可以

看到使用组合相似度策略结果性能指标明显优于余弦相似度

和语义相似度，最多性能可以提高１０％。实验充分说明了组

合相似度可以更好地刻画相似度特征。此外，单一使用语义

相似度比单一使用余弦相似度性能更好，性能提高５％以上。

ｇｌｅＰａｓｓ算法的Ｆｌ一舢ｓ“僧值。实验表明，当（ａ，ｐ，ｙ）＝

（０．３，Ｏ．３，ｏ．４）时，Ｆ１一打搬ｎｓＨ＂取得最大值０．８４３２。因此，本文组合相似度的参数口，口，７取值分别取为ｏ．３、ｏ．３、ｏ．４。在实际应用中，根据实际问题的不同，最佳的加权系数可能是不

同的。

这主要是因为余弦相似度没有考虑到语义信息，而语义信息

在短文本相似度比较中是很重要的因素。

结束语本文针对微博短文本提出了ＭＢＳｉｎｇｌｅＰａｓｓ算法。与基于传统媒体对象的话题检测算法相比，ＭＢＳｉｎｇｌｅ—Ｐａｓｓ算法考虑了微博平台本身的特点，即微博结构化信息，包括发贴人之间存在的关注关系、帖子的转发评论关系等。同时Ｍｌ｝ＳｉｎｇｌｅＰａｓｓ算法采用了组合相似度和同义词扩展技术，更准确地刻画了相似性和丰富了帖子的特征信息。通过

３．２实验１

为了测试ＭＢｓｉｌｌｇｌｅＰａｓｓ算法的性能，本文设计了一组对比试验。对照算法也是话题检测常用的增量聚类和增量Ｋ＿ｍｅａＩｌｓ算法。增量聚类算法只采用单一阈值策略，算法实

际类似于二值分类问题；增量Ｋ．ｍｅａ璐算法按帖子数量设置

窗口长度，值设为５０，共两个窗口。实验采用１０个话题的平均性能作为相应算法的性能指标。实验结果如图４所示。

与传统话题检测算法增量Ｋ＿ｎ煳ｓ、增量聚类的比较显示，

Ｍ眵ＳｉｎｇｌｅＰａＳｓ算法在性能上有较大的提高。下一步的研究可以在其他微博平台上进一步测试，同时对其他算法进行测试，甚至可以在话题模型上进一步探讨，以使微博的话题检测性能得到进一步的提高。

参考文献

［１］洪字，张宇，等．话题检测与跟踪的评测及研究综述［Ｊ］．中文信

息学报，２００７，２１（６）

［２］闪四清，陈茵，程雁．数据挖掘一概念、模型、方法和算法［Ｍ］．北

京：清华大学出版社，２００３：１１４—１１６

ＩＩＩ～■¨

［３］

ＡｌｌａｎＪ，ＣａｒｂｏｎｅｌｌＪ，Ｉ）。ｄｄｉｎｇｔｏｎ

ｏ●一■■■■■‘一

准确半

●增量鬟妻

科同半０础９７Ｉ】而捕

嗣捡串“Ｊ？∽

（Ｉ＝．４ｉ？

ＩＺ捡宰

０．０７１３

Ｇ．Ｔｏｐｉｃ使ｔｅｃｔｉｏｎａｎｄＴ陆

ｏ．６ｊ椰

¨Ｉ郇ｌ

７

７＿ｌ簟曼Ｋ＿舢Ｈｎｓ

亿㈣’Ｈ

＿熙一蛳ｇ∽ｎｓ５．ｏ

８５蛳

㈧＝¨【…晡＊｛Ｊ㈦？

■■，¨㈨㈣

ｃｋｉｎｇＰｉｌｏｔｓｔｕｄｙ：ＦｉｎａｌＲｅｐｏｒｔ［ｃ］∥ＰｒｏｃｅｅｄｉｎｇＤｆｔｈｅＤＡＲＰＡ

”≈∽

仉ｍ仉

的町Ⅲ

ＢｍａｄｃａｓｔＮｅｗｓＴｒａｎｓｃｒｉｐｔｉｏｎａｎｄＵｎｄｅｒｓｔａｎｄｉｎｇＷｏｒｋｓｈｏｐ．

ＳａｎＦｌａｎｃｉｓｃｏ，１９９８：１９４．２】８

图４算法性能比较结果

［４］

ＹａｍｒｏｎＪＰ，ＫｎｅｃｈｔＳ，ｖａｎＭｕｌｂｒｅｇｔＰ．Ｄｒａｇｏｎ’ｓＴｒａｃｋｉｎｇ蛳ｄＤｅｔｅｃｔｉｏｎＳｙｓｔｅｒｒＩｓｆｏｒｔｈｅＴＩ），ｒ２０００Ｅｖａｌｕａｔｉｏｎ［ｃ］∥Ｐｒｏｃ盱ｄｉｎｇｏｆＴｏｐｉｃ

从以上实验数据可以得到以下结论：首先，相较其他两个算法，ＭＢＳｉＴｌｇｌｅＰａｓｓ算法在各项指标上都有较大的提高，性能提高将近３０％。这主要是由于Ｍ降ＳｉｎｇｌｅＰａｓｓ算法考虑了

Ｄｅｔｅｎｂｎ狮ｄ

ｎａｃｋ吣Ⅵｂｒｋｓｈｏｐ．Ｗａｓｈｊｎｇｔｏｎ，

ＵＳＡ，２０００：７５—８０

［５］贾自艳，何清，等．一种基于动态进化模型的事件探测和追踪算

微博的结构化信息，而且采用了特征扩展技术，丰富了特征信

息，同时组合相似度策略充分吸取了不同相似度策略的优点也是一个重要原因。其次，引入微博的相关信息，可以较大地提高检测算法的性能。在增量聚类和增量Ｋ＿ｒｎｅａｎＳ算法中，由于没有引人微博的各种结构化信息，加上微博的特征稀疏性，使得算法无法得到满意的性能。因此，在微博话题检测算

法口］．计算机研究与发展，２００４，４１（７）：１２７３－１２８０

［６］

Ｂｒａｎｔｓ

Ｔ．ｃｈｅｎＦ，Ｆａｒａｈａｔ八Ａ

ｓｙＳｔ咖ｆｏｒ

ｎｅｗｅｖｅｎｔ

ｏｎ

ｄｅｔｅｃｔｉｏｎＲｅｓｅａｒｃｈ

［ｃ］∥Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ２６ｔｈｓＩＧ取Ｃ０ｎｆｅｒｅｎｃｅ

ａｎｄＤｅｖｅｌｏｐｍｅｎｔｉｎＩｎｆｏｒｍａｔｉｏｎ

Ｒｅｔｒｉｅ砌．２００３

［７］张晓艳，王挺．话题检测与追踪技术研究［Ｊ］．计算机研究与探

索，２００９，３（４）：３４７—３５７［８］席耀一，林琛，李弼程，等．基于语义相似度的论坛话题追踪方法

［Ｊ］．计算机应用，２０１１，３１（１）：９３—９６

［９］徐建民，唐万生．基于查询术语同义词的扩展信念网络检索模型

口］．计算机工程，２００７，３３（１０）：２８—３０

［１０］孙胜平．中文徽博客热点话题检测与追踪技术研究［Ｄ］．北京：

北京交通大学，２０１１

［１１］刘群．李素建．基于《知网》的词汇语义相似度计算［Ｃ］∥第三届

汉语词汇语义学研讨会．台北，２００２：５９—７６

法中引入结构化信息虽然增加了复杂度，但却是必要的。

３．３实验２

为了测试采用组合相似度策略的效果。基于同一实验数

据，本文采用Ｍ睁ＳｉｌｌｇｌｅＰａｓｓ算法，对余弦相似度、语义相似度和组合相似度３种不同相似度策略进行了对照比较。单一使用雅各比相似度效果较为一般，本文未进行探讨。实验的

数据及参数与实验１相同。实验结果如图５所示。

２０２ 万方数据

［１２］Ｒａｎｇｒｅｊ

２０１１

Ａ，ｅｔ

ａ１．（ｂｍｐａｒａｔｉｖｅＳｔｕｄｙｏｆＣｌｕｓｔｅｆｉｎｇ

ｋｈｎｉｑｕｅｓ

ｆｏｒＳｈｏｒｔＴｅｘｔ

Ｄｏｃｕｍｅｎｔｓ［ｃ］∥ｗｗｗ２０１１．Ｈｙｄｅｒａｂａｄ，Ｉｎｄｉａ，

MB-SinglePass:基于组合相似度的微博话题检测

作者：作者单位：

周刚， 邹鸿程， 熊小兵， 黄永忠， ZHOU Gang， ZOU Hong-cheng， XIONG Xiao-bing， HUANG Yong-zhong

周刚,ZHOU Gang(软件开发环境国家重点实验室 北京100191 ; 信息工程大学信息工程学院 郑州450002)， 邹鸿程,熊小兵,黄永忠,ZOU Hong-cheng,XIONG Xiao-bing,HUANG Yong-zhong(信息工程大学信息工程学院 郑州450002)计算机科学

Computer Science2012,39(10)

刊名：英文刊名：年，卷(期)：

本文链接：http://www.77cn.com.cn/Periodical_jsjkx201210044.aspx

本文来源：https://www.bwwdw.com/article/gn3i.html