第5卷第2期 智能系统学报 Vol.5 No.2 2010年4月 CAAI Transactions on Intelligent Systems Apr.2010 doi:10.3969/j.issn.16734785.2010.02.005 命名实体的网络话题K-means动态检测方法 刘素芹1，柴松1,2 (1.中国石油大学计算机与通信工程学院，山东青岛266555：2.山东省军区自动化工作站，山东济南250013) 摘要：针对传统的网络话题检测方法在文本特征表示方面的不足及K-means聚类算法面临的问题，提出了一种基 于命名实体的网络话题K-meas动态检测方法.该方法对传统话题检测的特征表示方法进行了改进，用命名实体和 文本特征词相结合表示文本特征，用命名实体对文本表示的贡献大小表示命名实体的权重；另外，利用自适应技术 对K-means聚类算法中的K值进行自收敛，对K-means聚类算法进行了优化，利用K值的动态选取来实现网络话题 的动态检测.实验结果表明，该方法较好地区分了相似话题，有救提高了话题检测的性能. 关键词：命名实体；网络话题；动态检测；K-means聚类；自相似度；话题向量 中图分类号：TP18文献标识码：A文章编号：16734785(2010)02012205 K-means dynamic web topic detection method based on named entities LIU Su-qin',CHAI Song'2 (1.College of Computer&Communication Engineering,China University of Petroleum,Qingdao 266555,China;2.Automation Work- station,Military District,Shandong Province,Ji'nan 250013,China) Abstract:Current text representation models are not suitable for web topic detection,and the traditional K-means clustering algorithm has some drawbacks.The authors developed a dynamic K-means detection algorithm for web topics on the basis of named entities.In the new method,the representation model of the traditional topic detection method was modified.The text was represented by a combination of named entities and text features.The weight of the named entity was described by its contribution to the representation.The number of clusters K in the K-means algorithm self-converged by the use of an adaptive technique.The K-means algorithm was optimized,achieving a dynamic detection of web topics by using dynamic selection of K values.Experimental results indicated that the new method detects and distinguishes between similar topics effectively,thus significantly improving the performance of topic detection. Keywords:named entity;web topics;dynamic detection;K-means clustering method;self-similarity;topic vector 网络话题检测与追踪fl(topic detection and 仅仅依靠命名实体而放弃描述话题内容的大量其他 tracking,TDT)旨在开发出一种能在没有人工干预 关键词，必然造成对话题框架概括不全面，从而影响 的情况下自动判断新闻数据流话题的新技术[21.话 话题检测的性能4」 题检测主要研究将新闻报道、新闻专线等来源的数 本文将文本中的命名实体及除命名实体之外的 据流中的报道归入不同的话题并在必要时建立新话 特征词进行分别提取，并赋予不同的权重，将新闻文 题.相似话题的报道中有大量的相同词汇，容易造成 档表示成基于命名实体及特征词的双特征向量；然 话题误判，传统增量聚类方法很难解决这一问 后在此基础上对K-means聚类方法5进行研究，结 题3]，Kumaran利用命名实体来解决此问题.详细分 合自相似度策略来确定K值，解决了聚类算法中K 析可以得知，利用命名实体虽然能在一定程度上区 值自收敛的问题，最终实现利用K值的动态选取来 分相似话题，但新闻报道中的命名实体的数目有限， 实现网络话题的动态检测.试验结果表明，与传统的 话题检测方法相比较，该方法能够很好地解决海量 收稿日期：2009-1204. 网络数据环境下相似话题难以区分的问题，有效实 通信作者：刘素芹.E-mail:liusq@upc.edu.cm. 现对网络话题的动态检测，该话题检测方法优于传
第2期 刘素芹，等：命名实体的网络话题的K-means动态检测方法 ·123· 统话题检测方法 抽取特定数目的词作为该文档的特征词，形成最优 词表. 1基于命名实体的话题向量构造 4)拆分特征词表.对特征词表进行扫描，加入 基于命名实体的话题向量构造主要包括对网络 修正规则，实现对其中命名实体的有效提取，将所提 文本中的命名实体提取以及对命名实体赋予一定权 取的命名实体构造成命名实体词表，余下的特征词 重，并将其与关键词合并构成网络话题向量 形成关键词表。 1.1命名实体提取 5)构造话题向量.将所拆分后的词表分别处 命名实体首次作为一个专门术语出现是在消息 理，对命名实体词表和关键词表分别赋予不同的权 理解会议MUC6上[，根据消息理解会议的定义， 重，最终形成话题向量.权重的赋予根据经验值，将 命名实体分为七大类：人名、地名、机构名、日期、时 命名实体词表的权重加大，经过实验验证，命名实体 间、百分数和货币.这些短语都是文本中最基本的信 词表与关键词表的权重比例在3.5：1时效果最佳. 息元素，往往指示了文章的主要内容，在对文本的理 解上，命名实体的作用较之普通文本特征词来说是 2网络话题K-means聚类动态检测方法 非常重要的.因此，对文本中的命名实体进行专门提 在构造的网络话题向量的基础上，检测方法采 取，并予以与普通特征词不同的权重，将命名实体与 用K-means聚类算法，来完成网络话题的动态检测. 普通特征词结合来表示文本，可以有效提高传统特 本部分首先分析K-means聚类算法及其存在的问 征词向量对文本向量的表示，常用的命名实体主要 题，然后针对K-means聚类中K值的确定问题，引人 包括人名、地名、机构名和时间实体 了基于自相似度的最大最小原则？$]，利用自相似 在真实文本中，中文句子不是以词为单位的，而 度的自收敛策略来确定K值的选取，解决了K- 是以字为单位.为了降低中文命名实体提取的复杂 means聚类话题检测中预先设定话题个数的问题， 度，常常把分词信息用在中文命名实体提取中，但是 实现了话题的动态检测 分词的错误在命名实体提取过程中如果无法得到纠 2.1 K-means聚类算法 正，会导致错误蔓延.为此，制定了4种规则，以此来 给定d维数据集X={x|x:∈R,i=1,2,…, 修正中文分词导致的命名实体提取时的错误， N},将其聚成K个类别o1,2,…,0x,质心为c1,C2, 第1种规则为合并规则，主要修正长实体在分词 …,cx,其中c=(1/n)∑x,n:是类0：中数据点 时被作为几个连续的实体切分错误以及本属于支配 的个数.聚类目标函数为：J=∑11d(,c), 关系的连续实体切分错误；第2种规则为同指人名规 其中d:(,C)是与c:之间的欧氏距离 则，旨在找到指代同一人名的词，并统一进行提取：第 K-means聚类步骤如下： 3种规则为边界修正规则，主要用于实体切分时丢失 1)从X中随机选择K个初始参照点c1,c2,…,cx; 了自身一部分的错误，此类错误主要为地名提取时， 2)以c1,c2,…,cx为参照点，对X进行划分.满 经常会发现丢失后缀的现象；第4种规则为类型修正 规侧，这种规侧主要用于修正命名实体提取时的类型 足若d(9)=吧(，6），其中=1,2， …,K,i=1,2,…,N,则将x:划分到类①中； 判断错误，地名提取时此类错误经常发生 1.2话题向量构造 3)根据式c:=（1/n:)∑xex,重新计算类的质 利用以上这4种规则对中文词语切分之后的命 心c1,c2,…,cx; 名实体作具体的修正，然后提取新闻文档中的命名 4)若对于任意ie{1,2,…,K},c=c:都成立， 实体，并结合特征词分别赋予不同的权重，以此来完 则算法结束，当前的c,c2,…,c代表最终的聚类 成话题向量的构造.具体构造步骤如下： 结果；否则，令c:=c,重新执行2) 1)预处理.扫描文档，对文档进行分词，进行停 为了防止4)中出现无限循环的情况，通常设置 用词去除处理.经过预处理所得到的词表为文档初 一个固定的阈值h,当对于所有的℃：，都有 始词表。 Ic-c:<h时，算法结束， 2)词频统计.对所提取的每一个特征词进行词 利用K-means聚类实现话题检测需要解决以下 频统计，将词所对应的词频作为该词所对应的权重； 问题： 并根据词频统计结果对初始词表进行排序。 1)聚类类别数K的确定.事先不知道所检测话 3)特征提取.对排序后的词表采取截断处理， 题的个数，所以需要确定K的值
·124: 智能系统学报 第5卷 2)初始质心的选择.K-means是以质心为参照 相似度，如果ie%,且jeo,则sh=,三im 点进行聚类的，质心的选取决定最终所聚话题的核 为类0k和®，的互相似度， 心内容，因此，如何选取聚类初始质心在动态话题检 定义全局平均自相似度门限： 测中尤为重要. sch=max(s,Smin max）. (6) 2.2自相似度收敛策略 假设选取了K个质心，各类的平均自相似度分别 假设文本中一个事件为一个文本单元，任意2 为：511,52，…，3x,增加一个质心后，各类的平均自 个文本单元间的距离用余弦相似度来计算.比如文 相似度为：Ⅱ，2，…，5,5(K+1)(K+1) 本单元i的特征向量为x:=(a1,a2,…,an),j的特 定义局部自适应的平均自相似度门限5仙： 征向量为x=(b1,b2,…,bn),则2个文本单元的相 5h=(!+2+…+u+1+ 似度： s'2+…+sx)/2K, (7) sim(,)=(∑a.b)/[sq(∑c2)× 该门限值随每次聚类动态变化， 如果出现 gr(公2)1. (1) (③u+3n+…+3x) 式中：am、bn(1≤m≤n)为文本单元的第m个特征 3n-+州32-+…+3-≥ 对应的权值，n为2个文本单元的特征并集总数. (s1+22+…+5) (Is11-5h1+l52-5h|+…+|5x-5h1) 设聚类样本集合为：X={1,x2,…,xw},N为样 且 本个数.计算所有样本间的相似度simg=sim(x:, x）,当i=j,则sim与=1. 5(K+10(K+)≥SGh, (8) 则继续选取下一个质心聚类 定义全局平均相似度： = S∑sim/N(N-1)/2. 3基于命名实体的话题动态检测方法 (2) +1 定义最大最小平均相似度： 基于命名实体的网络话题动态检测的主要思想 3min max =max(simg)+min(sim;)2.(3) 是在文档特征提取上面进行突破，将文本中的命名 式中：i=1,2,…,N-1,=i+1,i+2,…,N 实体和关键词进行分别处理，予以不同的权重，然后 定义平均自相似度，类别®4的平均自相似度： 将二者结合构造话题向量，从话题的向量表示上加 大了命名实体对文档表示的力度，丰富了词对文档 S= n(n4-1)/2,nk=|wkl. (4) 表示的内容.然后在K-means聚类方法中加入了基 式中： 于最大最小的自相似度收敛策略，实现了K-means 聚类方法中的K值的自动选取，从而实现了基于命 Sk=】 ∑simg (5) 名实体的话题动态检测.新方法流程图如下： i与j同为类0s中的样本，因此称sk为类0s自 规则修正 白适应相似度 网页 网页文本 巾文分词 命名实体 话题 集合 内容提取 K-means 动态 聚类 检测 关键词 话题向量构造 绮米反馈 图1基于命名实体的网络话题动态检测流程图 Fig.1 Flow chart of Web topic dynamic detection based on named entities 基于命名实体的话题动态检测的具体步骤如下： 内容，去除包括网页链接、广告、版权信息等网页噪 1)网页文本内容提取，主要完成对半结构化的 声，完成文本内容提取.本文采用实验室已有的基于 网页数据进行结构化处理，从新闻网页中抽取文本 网页树的文本内容提取方法进行
第2期 刘素芹，等：命名实体的网络话题的K-means动态检测方法 ·125· 2)中文分词，主要完成对中文网页文本内容进 4实验结果及分析 行词语的自动切分.本模块采用中科院开源ICT CLAS进行处理. 实验数据来自TDT2005标准语料中的中文语 3)命名实体提取，主要在中文分词的基础上完 料，包括27142篇新闻报道.评测标准同样采用TDT 成文本中命名实体的提取.在本部分处理中采用本 标准评测，主要包括漏报率P和错报率Pa以及 文第1.1节的规则修正策略，修正中文分词对命名 将漏报率与错报率合并成一个检测开销C及其规 实体的切分错误，从而实现文本中命名实体的完整 范式Nom(Ct)I9].其计算公式为 而准确的提取 CDe=CPmi PCFAPFAP (9) 4)话题向量构造.中文分词之后对停用词进行 式中：P为系统的漏报率，PA为系统的错报率， 有效去除，对其中的常用字等多频字也进行去除，并 Cmin、Puwt、CFA、Pntge为事先设定值，具体如下： 对所得词按照词频进行排序，截取预先设定好的词 Cmise =1.0,Ptrget =0.02,CFA =0.1;Pnontarget =1- 的个数，形成初始词表；从中提取的命名实体及其词 Pagt=0.98. 频信息形成命名实体词表，余下的词形成关键词词 为了使得到的性能指标落在更有意义的范围 表，并按照本文第1.2节的策略予以加权处理，最终 内，因此将Cpt规范化得到Nom(Coa): 构造话题向量。 Norm(Cpa)=Cpa/min(CPCrAP). 5)自相似度K-means聚类.首先选择初始聚类 (10) 质心：将上述所构造的话题向量进行相似度计算，将 可以看出，Nom(C)值越小系统的性能越好本 计算结果进行排序，选择相似度最小的2个样本s1 文实验结果均采用Micro Averageo计算各项指标 与$2作为初始质心，其他样本再按照与初始质心的 实验将本文话题检测结果与传统基于增量聚类 相似度分别划分到s1与$2所在的类别中，然后分别 的话题检测方法[31（增量聚类法）、基于命名实体话 计算311与s22,此时聚类类别数K=2.如果出现具 题检测方法[4（命名实体法）、基于K-means聚类话 有同样最小相似度的其他样本对，则同样重新计算 题检测方法(K-means聚类法)话题检测结果相比 出以此对样本为质心后各类的平均自相似度'、 较，对比结果如表1和图2所示 '2·具体方法二者选其一： 表1不同方法话题检测结果对比 ①计算不同样本对作质心后，各类之间的互相 Table 1 Contrast of topic detection results with differ- 似度和s'·比较s,与s'2,取值小的那对样 ent methods % 本作为初始质心 增量聚命名实 K-means ②不计算互相似度，仅利用平均自相似度进行 检测项目 本文方法 类法 体法 聚类法 初始质心的选取 漏报率 27.8125.63 23.74 20.88 比较(51+52)/(1s1-56m1+182-86h1)与 错报率 1.26 1.15 1.10 0.93 (s'1+'2)/(s'1-shI+Is2-saI),选取比值 召回率 72.19 74.37 76.26 80.44 较大的那对样本作为初始质心：如果比值相等，则选 准确率 72.97 75.17 75.99 81.02 择|s11-82|与1'1-'2|较小的那对样本 F1-Measure 74.33 75.17 77.56 80.73 Norm(CDet) 30.82 29.04 27.83 23.86 这种样本对选择策略有2个好处：既可以尽量 0.35 保证聚类后各类的平均自相似度不能太小，同时也 0.30 避免了选取的样本聚类后2个类的平均自相似度相 Γ0.25 0.20 差太大的情况 0.15 0.10 同样的方法选取下一个质心.聚类后计算每个 0.05 类别的平均自相似度，直到不满足式(8)，停止聚 0 增量、命名K-neans本文方法 类，并确定类别数K 聚类法实体法聚类法 6)结果反馈.自相似度K-menas聚类的结果作 图24种方法的检测开销对比 为话题检测的输出，根据输出结果人工来调整话题 Fig.2 Comparison of four methods of detection of over- 向量构造及自相似度K-menas聚类算法中的参数， head 具体调整包括话题向量构造中的命名实体与关键词 从表1和图2的检测结果对比中可以看出，基 权重的比例大小及K-means聚类中参数的选释等， 于命名实体的网络话题动态检测方法比文献[3]中
·126 智能系统学报 第5卷 基于命名实体的话题检测方法检测准确率提高了6 [4]KUMARAN G,ALLAN J.Text classification and named 个百分点，召回率提高了6个百分点，主要原因在于 entities for new event detection C]//Proceedings of the 文献[3]在话题向量表示中仅采用命名实体，忽略 27th Annual International ACM SIGIR Conference on Re- 了命名实体之外的关键词对文本表达的作用，而新 search and Development in Information Retrieval.Sheffield 2004:297-304。 方法将命名实体和关键词结合起来构造话题向量， [5]YIU M C.K-means:a new generalized K-means clustering 并且根据实际情况，针对命名实体与关键词对文本 algorithm[J].Patter Recognition Letters,2003(24): 的贡献程度不同分别赋予不同的权重，使得在文档 2883-2893. 向量表示上对话题描述更充分、全面而准确，因此可 [6]SUNDHEIM B M.Named entity task definition[C]//Proc 以很好地区分相似话题.新方法与基于增量聚类及 of the Sixth Message Understanding Conf.Columbia,Mary- K-means聚类话题检测方法相比较，无论是从检测 land,1995:319-332. 准确率、召回率都有一定提高，并且本文在K值选 [7]DING C,HE Xiaofeng.Cluster merging and splitting in hi- 取上实现了动态自收敛.与传统方法相比较，本文方 erarchical clustering algorithms[C]//Proceedings of the 法无论是从检测性能，还是检测开销上都优于传统 2002 IEEE International Conference on Data Mining.Mae- 方法，是一种高性能且实用的网络话题检测方法. bashi City,Japan,2002:139-146. [8]DING C,HE X,ZHA H,et al.A min-max cut algorithm 5结束语 for graph partitioning and data clustering[C]//Proceedings of the IEEE Interationl Conference.San Jose,Califoria, 本文在传统网络话题检测的基础上做了改进： USA,2001:107-114. 一是在话题特征表示上，将命名实体及关键词进行 [9]骆卫华，于满泉。基于多策略优化的分治多层聚类算法 分别处理，赋予不同的权重来构造话题向量，丰富了 的话题发现研究[J].中文信息学报，2006,20(1)：29- 词对文档的表达，使得机器处理更能贴近人的理解； 36. 二是利用自相似度对K-means聚类中的K值进行自 LUO Weihua,YU Manquan.The study of topic detection 收敛，解决了K-means聚类中的问题，从而实现了利 based on algorithm of division and multi-level clustering with 用K-means聚类对网络话题的动态检测. multi-strategy[J].Journal Chinese Information Processing, 2006,20(1):29-36. 参考文献： 作者简介： 刘素芹，女，1968年生，副教授，博 [1]ALLAN J,CARBONELL J,DODDINGTON G.Topic de- 士，主要研究方向为计算机网络、高性 tection and tracking pilot study:final report[C]//Proceed- 能计算，近3年发表学术论文20余篇， ing of the DARPA Broadcast News Transcription and Under- 编写教材2部. standing Workshop.San Francisco,1998:194-218. [2]洪宇，张宇，刘挺.话题检测与跟踪的评测及研 究综述[J].中文信息学报，2007,21(6)：71-87. HONG Yu,ZHANG Yu,LIU Ting.Topic detection and 柴松，男，1981年生，主要研究方 tracking review[J].Joumal Chinese Information Processing, 向为计算机网络、高性能计算及应用。 2007,21(6):71-87. [3]YAMRON J P,KNECHT S,Van MULBREGT P.Dragon's tracking and detection systems for the TDT2000 evaluation [C]//Proceedings of Topic Detection and Tracking Work- shop.Washington,USA,2000:75-80