基于改进向量空间模型的话题识别与跟踪

教育信息化

简介：宋丹(1980 -)，女，辽宁锦州人，硕士研究生，研究方向话题的识别和追踪。基于改进向量空间模型的话题识别与跟踪宋丹1、王卫东2、陈英2

(1)大连理工大学计算机科学与工程系，辽宁大连116024；2 .东北电力大学计算机系，吉林省吉林省132012 )

摘要：话题识别与跟踪发展了一系列基于事件的信息组织技术，旨在通过监控实现新闻媒体信息流中新话题的自动识别不要与已知话题动态跟踪。 文中给出了一种利用改进的向量空间模型进行识别和跟踪的方法。 没有使用传统的向量空间模型不是单一的向量，而是按语义将特征词分为4组(人物、时间、地点、内容)形成4个向量空间。 每个空间都有独立的权限重新计算和相似度计算。 实验证明这些方法是有效的。关键词：话题识别与跟踪向量空间模型； 时间表达

图中分类编号： TP18文献识别码：A文章编号：1673-629x(2006 ) 09 - 0062 - 03topicdetectionandtrackingwithadevelopedvectorspacemodelSON G Dan1

，湾g圩2东2、陈英2

(11 departmentofcomputerscienceandengineering，Dalian University of Technology，Dalian 116024，China；2. Department of Computer Science，Northeast Dianli University，Jilin 132012，China )

abstract 3360 topicdetectionandtrackingisanevent-basedinformationorganizationtaskwhereonlinewstreamsonitoredinordertospotnewunreportedeventsandlinkdocumentswithpreviouslydetectedevents.sopresentanapproachthatformalizestemporalexpres 2sionsandaugmentsspatialtermswithontologicalinformationandusesthisdatainthedictation.in addition，instead using a single termvector as document representation，splitthetermsintofoursemanticclassesandprocess，including character，time，space and contentweightheclassesseparately.theapproachismotivatedbyexperiment。keywords :主题跟踪； vector space模型； 终端快速0领先

话题识别与跟踪(TDT )作为信息检索的新研究研究方向旨在发展和通过基于一系列事件的信息组织技术监控在新闻媒体信息流中实现新话题的自动识别(first )story detection (和已知话题的动态跟踪) topic tracking、群集检测)。 TDT系统的功能和信息业务

的工作大同小异，对新的报道可以做一个检查总结去的话题，或者把这篇报道看作新的话题。 这个知识很难用传统的信息检索方法实现跟踪过程[1 ]。本文给出了基于语义群空间向量模型的TDT方法。 该方法的各语义组由语义相近的词构成，例如例如，地点组：时间组、人物组、内容组。 把一篇新闻报道4个独立的空间向量表示(地点向量、时间向量、人物的方向量和内容的向量)。 大致说明利用了这种复杂的表现方法的事实目前，话题识别和跟踪的过程和利用单一向量的向量空间比较模型。1前人的工作

话题识别和追踪的基本思想源于1996年，当时美国国防高等研究计划委员会(DARPA )自动决定新闻信息流中话题结构的技术[2 ]、该方向的确立与发展受到话题识别追踪(TDT )系列评估会议的推动的双曲正切值。 话题识别和跟踪更强调和关闭新信息的发现能力心与特定话题相关，是比较广泛的主题范畴的信息。 近年来来吧，动态话题的识别和跟踪开始成为热点。话题识别可以看作是逐事件聚类，研究者经常采用的算法是：增量k均值聚类、聚合聚类、单聚类等[3 ]。 话题跟踪使用了几种不同的方法例如，基于Rocchio分类方法、决策树方法、HMM语言模型等等[3 ]。 目前常用的话题/报道模式是：语言模式(LM )和向量空间模型，其中向量空间模型是目前最简便高效的句子.本显示模型之一[4 ]。

2改进的向量空间模型

一篇新闻报道最少应该有：小时吗？ 在哪里？

是什么样的人？ 发生了什么事？ 如何识别和跟踪以前的话题试图将这些方面压缩成一个向量来表现。 然后在文中提到在用于改进的向量空间模型中，上述四个问题中的每一个第十六卷第九期2006年9月计算机技术与发展

computertechnologyanddevelopmentVol. 16 No. 9Sep. 2006

分配一个语义组，进而形成4个向量空间。 如图1所示。图1改进的向量空间模型

改进的向量空间模型的例子“:周四，美国海军的潜水艇在加利福尼亚附近的太平洋海域，挑战世界潜水艇在潜水最深的记录下起火”3相似度计算

通过利用语义组的表达方法，可以对每个组分别进行相似度的计算。 这种文章相似度的比较方法与传统的比较方法基于各个空间向量的相似度比较方法不同。 在这个时间中，首先给出了全部适用于4个向量的共同权重的计算方法。接着分别给出时间和地点相似度的计算方法，最后给出笔作者提出的TDT算法。3. 1通用权重及相似度计算方法

典型的新闻报道与侦探小说不同，新闻报道一般都是叙述了前面几句话所报道的事件。 因此，利用特征语的出现等用级(也就是说，该特征词所在句子的顺序)来衡量该特征词有其重要性。 如果一个特征词t在报道中出现m次，则t的等级分数的计算公式是：RS(t )=m

k=112

ln tK

(1) ) ) )。

t k是特征语t的第k次出现的等级。 按等级评分那么，一篇文章第一句中所有词的得分是：12

ln 1=11

=1。

为了确定两个文档之间交点的权重，计算了两个文章交叉部分的权重与两个文档的权重之和之比。 时光流逝但是，各个特征词本身的价值性不同，所以遵循传统IR的方法是将等级得分乘以倒置文档频率IDF(inversed )document frequency )[5 ]。

中国教育信息化

)3IDF(TK ) )。| X|j=1RS(TJ| Y|

L=1RS(TL）(2) ) ) )。

因此，如果两篇文章完全相同，则RWS(x，y )=1。如果x和y没有相似之处，则RWS(x，y )=0。 利使用式(2)计算人物向量和内容向量的相似度。3. 2时间相似性计算方法

如果两篇文章都有“上星期一”，就无法解释它们。很像。 “上星期一”是相对的概念，是说话的时候了根据差异而变化。 为了表示时间，我做了自动转换器将无意义的时间表示映射到日历上并标准化。 做标记标准化的时间信息由全球时间轴上的点表示。两篇报道的时间相似度通过时间对点的匹配来均衡在量上，考察与时间段相对应的起点和终点。 如图2所示，对角线上的点表示时间轴上的两个同步点，阴影区域的世代表重叠的间隔，重叠越多相似度越高。图2示出a和b两个时间段集合的坐标

用ut 3: T T IR计算两个时间段的相似度3360ut([ ti

，tj ]，[ t k，tl ]

2) (ti，TJ ) ) TK，TL ) )(ti、tj

(tk，tl ) )。(3) ) )。

实际上，使用“覆盖矩阵”计算函数ut的值。 Ti，j表示Ti的第j个时间段。 Ti，j的“复盖”是求I行或j列中u的最大值(用vi，j表示)。 整体的“覆盖”是vi，j之和用与时间间隔数之比表示。 例如，两个间隔T1和T2、T1如果n个间隔，T2包含m个间隔，则计算公式为：盖子(T1，T2 )=n

i=1

v1，i mj=1

v2，j纳米

(4) ) )。

也考虑时间特征词的类得分的相似性(

)2)，因此，两篇报道的时间相似度的最终计算公式为：simt(x，y )=Covert ) ) XT、Yt)3rws’(XT、Yt

(五) )。

Xt和Yt是文章x和y各自的时间向量，rws’(XT，Yt）不乘坐IDF的rws(XT，Yt请参阅。

3. 3地点相似度计算

利用地理知识计算地点相似性，比单纯

纯粹比较两个地理名词一直是正确的。 如：报道安徽洪水的情况下，特征语：安徽，长江和芜湖市，表面上没有它们虽然有共同点，但在地理上是相邻的，基于地理知识我知道有关联。 一个简单的例子：扩大了大连市被分配到辽宁省大连市。图3显示了一个简单的地理树。 树中的每个节点都是要比较一个地点、两个地点的相似度，只需了解它们即可的公共路径和总路径的长度之比，因此地点l1和l2的相似度美国是：美国

(l1，l2 )=

(level L1L2 ) ) ) ) ) ) ) ) ) ll2 ) ) ) ) ) ll2 ) ) ) ll2 ) ) ll2 ) )(级别(L1 )级别(L2 ) )(6) ) )。

如果两个地方完全相同，us

(l1，l2 )=1。 从现在开始

与法国和德国相比，结果是1/2(=1/4)，因为有共同的路径长度为1，每个路径为2。 同样，中国和法国的结果为0/(2 3 )=0。 巴黎和法国的相似度为2/(2)3) )。=2/5。第九期宋丹等：基于改进向量空间模型的话题识别与跟踪63图3简单的地理树

因为一个地方的特征词会和另一篇文章的所有地方特殊化因为征词进行相似度的比较，所以使用3. 2节的“复盖矩阵”，每一行或每一列只取最大的。 如果两篇报道的地点一致间视盖性的计算公式类似，为以下：覆盖

(L 1，L 2 )=ni=1

v1，i mj=1

v2，j纳米

(7) ) )。

如公式(5)所示，使用附带IDF的RWS时，将报道x和y的位置相似度的计算公式为：sims

(x，y )=Covers(xsYs)3RWS(xsYs

(8) )。

国家教学资源库

c3simc(VC，ec ) ) (9) ) ) ) ) ) ) ) ) ) ) )。另外，在某个向量的相似度为0的情况下，也可以考虑与其相对应减分。 像：不能因为时间、地点、人物有很高的相似性要确定报道的相似度，是因为内容向量的相似度为0加权加法后减分。本文采用的这种启发式聚类算法如图4所示。1福特()；

2 for each new document d3vbuild-vector(d )；4 max 0； 事件()；

5 for each found e6 dist，()；

7 for each semantic class c8add(sim(VC，Ec )，dist )；9结束；10if(summax )11 then max sum；12 envent e；13 f1；14结束；

15if (最大)16 then

17elseadd(v，found )；18 f1；19结束；

图4 TDT算法的流程图4实验及其结果笔者从网上2004年4月1日至2004年12月

在1天的10000篇以上的新闻报道中，手工挑选了5807篇。 训练套装包括1918起79起事件的报道，测试集包括3909起85起事件的报道。 利用连接器4名称实体分类器被提取

地点和人物。 正确率、传唤话题识别和追踪系统的性能

概率和它们两者的联合F 1 - measure表示。 评价的方法遵循以下公式：准确率P=

系统识别的相关文章数系统找到的所有文章的总数召回率R=系统识别的相关文章数所有相关文章的总数F1 - measure=F1=2 PR公关

使用本文提供的启发式阈值聚类方法进行实验。 然后呢为了进行比较，用余弦系数[ 5，6 ]的方法已经做了两次实验分别采用了单向量和文中提供的四矢量模型。 中选择另一种天花板类型前提是相同的阈值。 实验结果如表1所示。表1识别和跟踪结果

方法识别p识别r识别Fd跟踪p跟踪r跟踪ft(FDft )/2余弦系数0.5620.3460.4280.3150.7040.4350.431余弦系数(四向量)0. 6720.4010.5140.3840.6720.4890.502启发式0.6840.8930.7750.6920.5430.6090.692从表1可以明显看出，本文提供的这种启发式方法的效果很明显比起其他两个理想。结束语5

话题识别与跟踪(TDT )作为信息检索的新研究追求方向，迄今为止，话题识别和跟踪领域的大部分研究都在进行只需借用信息检索的几种方法，调整一些参数

使这些方法适合处理话题(事件)。 但是，为了识别话题跟踪研究的一些特殊性，以及决定只利用现有的信息检索方法很难进一步提高TDT系统的性能，必须加以研究破必须用更多的自然语言来理解技术。本文提供了利用自然语言理解技术输入特征词行语义分组形成了具有四个独立向量空间的改进的向量空建立间模型，利用该模型采用启发式聚类方法进行识别和跟踪。参照文献：

[1 ] Yang Y C，Donddington J，Peerce R，et al. X Learning ap2proachesfordetectingandtrackingnewsevents [ j ].IEEE in 2telligentsystemsspecialissueonapplicationsofintelligent信息保留，1999(14 ) :32 - 43。[2 ] Carbonell A J，Doddington J，Yamron G，et al. Topic detectionandtrackingpilotstudyfinalreport [ a ].in : proc DARPAbroadcastnewstranscriptionandunderstandingworkshop[ C]. San Francisco，ca : morgankanfmannpublishersinc，1998 : 194 - 218(第67页向下) )。

64 计算机技术与发展第16卷

确切的诊断。 文中的前因也就是知识抽象模型中的现象，前条件的模糊量表示现象的发生程度，其等级划分固定为：

可能性极高，可能性强，有可能，普通，弱普通，极弱，无。 一个一个等都对应于取1个[ 0，1 ]内的值的区间，如表1所示。表1模糊系数的量词表模糊量词的取值区间

恒定[ 1.00，1.00 ]极有可能[ 0.95，0.99 ]很强的可能性[ 0.80，0.94 ][ 0.65，0.79 ]一般[0. 45，0.64 ]弱一般[ 0.30，0.44 ]极弱[ 0.10，0.29 ][ 0.00，0.00 ]权重系数。

在某个规则中，前因是关于pi的集合，对pi在此集合的尺度用wi的大小表示，也表示在规则中的贡献献度。 因此，可以根据wi的大小判断前因集合中前因的重要程度同时要求这些wi之和为整数1 )因此，根据经验和实际情况可以分为以下几类级：极其重要、重要、重要、普通、不重要，可有可无。 一等一的度量可以根据系统的需要取值，也可以动态地位于不同的类中模型的故障规则指派值，同时这些值可以是基于未来系统的机器学习的运行状况，调整它们的尺度。 默认情况下，的度量如表2所示。表2默认权重系数测量表等级加权值度量

极其重要6很重要5重要4一般3不重要2不可能的1

4故障知识表达示例

电脑故障中有一个典型的例子。 ———死机。 作为结果死机的原因有硬件原因和软件原因两种。 例如硬件资源冲突、设备不匹配、病毒感染、系统文件丢失等时间但是，这些原因不仅导致恐慌，还导致其他故障。这里，根据这里描述的方法，遵循这样的规则(例如)不起作用。

表2表示电脑死机时的知识表示规则(没有列出规则)中详细结论()，根据当前模糊量词和权重测量电脑死亡机器很可能是显卡故障造成的，例如显卡松动、显卡时间比较等沾满灰尘、卡片上的金手指部分脏了或脱落了等。 当然，如果表中模糊量词和权重的测量值不同时，有可能得到其他的元引起的恐慌。 所以，这样做的话，你会发现很合理表达故障知识，将模糊量词和权重尺度转化为相应的数值，也就是说可以用推理机进行诊断。表3计算机死机量表IF模糊量词权重量表病毒感染极弱并不重要指示有无系统文件丢失接通电源可能很重要花屏强可能很重要颜色奇怪可能很重要画面上有乱码可能很重要没有超频

CPU风扇转速不良即使非常弱也不重要飞机内发出“哔声”一般不重要Then软件故障导致的死机(详细信息)。

CPU故障导致的恐慌(详细信息) ) ) ) ) ) ) ) ) ) )处理器故障图形故障导致的死机(详细信息内存故障导致的死机(详细信息) )结束语5

本文分析了计算机故障的分类和特点，提出了计算机故障的抽象知识模型，从而基于模糊产生式规则

知识表达方法在表达该领域知识的同时，也讨论了其知识规则的不确定性，给出了具体的表达例子，并基于下一步模糊匹配与语义距离相结合推理的计算机故障诊断系统奠定基础，这也是笔者正在研究的工作。参照文献：[ 1 ]吕家国，李桂玲.计算机与网络故障诊断与维护[ M] .北京：科学出版社，2004年

[ 2 ]新时代工作室.计算机故障诊断1000例[ M] .北京：机械工业出版社，2005年[ 3 ]蔡自兴，徐光.人工智能及其应用[ 3 ] .北京：清中华大学出版社，2003年

[4 ] Luca C，robertor.diagnosisofmultiplefaultswithflow -basedfunctionalmodels 3360 thefunctionaldiagnosiswitheffortsandflowsapproach [ j ].reliabilityengineeringsystemSafty，1999，64 (2) :137 - 150。[ 5 ]刘铭、时昕、姚燕南。 基于数据库的电力设备故障诊断模糊专家系统的设计与实现[J ] .计算机工程，2001(3) :75- 77。

[ 6 ]刘旭.诊断性专家系统的设计与实现[J ] .计算机工程师(程，2001 (2)2) :90 - 92(接第64页)

[ 3 ]李保利，俞士汶.话题识别与跟踪研究[J ] .计算机工程与应对用，2003，39 (17 ) :6 - 10。

[4 ]林鸿飞，高天，姚天顺.中文文本可视化表示[J ] .东北大学学报，2000，21 (5) :501 - 503[ 5 ]李晓明，阎宏飞，王继民.搜索引擎[ M] .北京：科学出版社2005.[6 ]基于金珠、林鸿飞. HowNet的话题追踪与倾向性分析[J ] .信息学报，2005，24 (5) :10 - 22。第9期程树林等：计算机故障分类及其领域知识表达67