李勝東，呂學(xué)強(qiáng)，施水才，孫 軍

(1. 廊坊燕京職業(yè)技術(shù)學(xué)院 計(jì)算機(jī)工程系，河北 廊坊 065200；2. 北京信息科技大學(xué) 網(wǎng)絡(luò)文化與數(shù)字傳播北京市重點(diǎn)實(shí)驗(yàn)室，北京 100101；3. 北華航天工業(yè)學(xué)院，河北 廊坊 065000)

1 引言

互聯(lián)網(wǎng)的出現(xiàn)，使信息急劇膨脹。這些信息包含有用的信息、無(wú)用的信息、感興趣的信息、不感興趣的信息等。在這種情況下，人們最關(guān)注的是如何快速而又準(zhǔn)確地得到感興趣的信息。目前，各種信息檢索、信息抽取和信息過(guò)濾技術(shù)也都圍繞這個(gè)目的展開(kāi)[1]。但是，這些技術(shù)返回的信息冗余度過(guò)高，例如，僅僅因?yàn)樾畔⒅泻兄付ǖ年P(guān)鍵詞，許多不相關(guān)的信息就被作為結(jié)果返回了，其中，即使是相關(guān)的信息，也沒(méi)有進(jìn)行有效地組織。在這種背景下，研究者開(kāi)始關(guān)注一種新的技術(shù)，它就是話題檢測(cè)技術(shù)[2]。該技術(shù)就是研究如何檢測(cè)新發(fā)生的事件，并幫助人們把分散的信息有效地組織起來(lái)。

在話題檢測(cè)與跟蹤研究中，話題檢測(cè)[3～4]被定義為將輸入的新聞報(bào)道歸入不同的話題簇，并且在需要的時(shí)候建立新的話題簇。從定義可以看出，話題檢測(cè)研究在本質(zhì)上等價(jià)于一種無(wú)監(jiān)督的聚類研究，即它的關(guān)鍵技術(shù)就是文本聚類算法。文本聚類算法[5]一般可以分為基于層次的聚類算法、基于平面劃分的聚類算法、基于密度的聚類算法等，其中，最常用的是基于層次的聚類算法和基于平面劃分的聚類算法?；趯哟蔚木垲愃惴╗6]可以達(dá)到很高的精確度，但是時(shí)間復(fù)雜度較高；以K-means算法為代表的基于劃分的聚類算法，具有很高的效率，適合處理海量文本數(shù)據(jù)。

2 話題檢測(cè)任務(wù)的特點(diǎn)

話題檢測(cè)任務(wù)[4]的關(guān)鍵技術(shù)是文本聚類算法，這決定了它除了具有文本聚類的相似性，還有一些自己的特點(diǎn)。傳統(tǒng)的文本聚類算法從全局的角度處理靜態(tài)的對(duì)象，而話題檢測(cè)任務(wù)從局部的角度以增量的方式處理動(dòng)態(tài)的對(duì)象。這是話題檢測(cè)任務(wù)的特點(diǎn)，也是話題檢測(cè)與文本聚類算法的本質(zhì)區(qū)別。

3 聚類算法

3.1 傳統(tǒng)的增量聚類算法

傳統(tǒng)的增量聚類算法處理話題檢測(cè)問(wèn)題時(shí)，其基本思想[7]是一次處理一篇報(bào)道。對(duì)于每一篇報(bào)道，先與每個(gè)已知話題進(jìn)行比較，如果相似度大于閾值，則把該報(bào)道歸入相似度最高的話題，如果對(duì)所有話題的相似度都低于閾值，則創(chuàng)建一個(gè)新話題，并更新話題數(shù)。

這種算法非常簡(jiǎn)單且易于實(shí)現(xiàn)，但缺點(diǎn)也很明顯: 一篇報(bào)道只能做一次決策，早期根據(jù)很少信息作出的錯(cuò)誤判斷，累計(jì)到最后的錯(cuò)誤量可能很大。針對(duì)這個(gè)缺點(diǎn)，本文對(duì)比了國(guó)內(nèi)外常用的聚類算法，分析了傳統(tǒng)的K-means算法，發(fā)現(xiàn)傳統(tǒng)的K-means算法和增量聚類算法具有優(yōu)缺點(diǎn)互補(bǔ)的可能性，能夠彌補(bǔ)傳統(tǒng)的增量聚類算法的缺陷。

3.2 傳統(tǒng)的K-means算法

K-means聚類[8]的算法思想簡(jiǎn)單，易于實(shí)現(xiàn)，能夠快速有效地處理大規(guī)模數(shù)據(jù)，已經(jīng)成為數(shù)據(jù)挖掘等領(lǐng)域應(yīng)用最廣泛的聚類算法之一。它的核心思想[9]是通過(guò)迭代過(guò)程把數(shù)據(jù)劃分到不同的聚類中，以使目標(biāo)函數(shù)(1)最小化。

(1)

在公式(1)中，Ci是語(yǔ)料中的第i類話題；x是話題Ci中的數(shù)據(jù)對(duì)象；xi是話題中Ci的均值；K為初始化的聚類數(shù)，也是算法認(rèn)定的話題數(shù)。

定義1根據(jù)兩層閾值的話題/報(bào)道表示模型[10]，報(bào)道i和報(bào)道j之間的余弦相似度函數(shù)Sim(di,dj)的定義為[11]式(2)。

(2)

在公式(2)中，di表示報(bào)道i的特征向量；dj表示報(bào)道j中的特征向量；參數(shù)M是基于兩層閾值的話題/報(bào)道表示模型的特征空間維數(shù)。

定義2報(bào)道向量間的余弦距離Dis(di,dj)被定義為式(3)。

Dis(di,dj)=1-Sim(di,dj)

(3)

從定義1和定義2可知，報(bào)道i與報(bào)道j之間的余弦相似度越大，它們?cè)较嗨?，因此，這兩個(gè)報(bào)道之間的余弦距離越小，傳統(tǒng)的K-means算法越有可能把它們作為同一個(gè)話題。

傳統(tǒng)的K-means算法通過(guò)迭代過(guò)程能夠得到全局最優(yōu)解，但初始化K值影響它的性能。

4 自適應(yīng)的增量K-means算法

傳統(tǒng)的K-means聚類算法可以通過(guò)迭代過(guò)程得到全局最優(yōu)解，但初始化聚類數(shù)K制約著該算法的性能；而傳統(tǒng)的增量聚類算法對(duì)一篇報(bào)道只做一次決策，能夠得到局部最優(yōu)解，很難得到全局最優(yōu)解，但該算法不需要初始化聚類數(shù)K。

通過(guò)分析傳統(tǒng)增量聚類算法和K-means聚類算法的優(yōu)缺點(diǎn)，發(fā)現(xiàn)它們的優(yōu)缺點(diǎn)有互補(bǔ)的可能性；在此基礎(chǔ)上，用傳統(tǒng)的增量聚類得到初始聚類中心，產(chǎn)生自適應(yīng)的K值，解決K-means算法對(duì)K值初始化敏感的問(wèn)題；然后用傳統(tǒng)K-means算法的迭代過(guò)程得到全局最優(yōu)解，解決傳統(tǒng)增量聚類中的局部最優(yōu)問(wèn)題，提出了自適應(yīng)的增量K-means算法作為話題檢測(cè)算法。

自適應(yīng)的增量K-means算法把所有中文新聞報(bào)道語(yǔ)料劃分為r個(gè)增量，每個(gè)增量報(bào)道的規(guī)模為Ni(i=1,2,…,r)。對(duì)于每一個(gè)增量，先按傳統(tǒng)增量聚類處理所有報(bào)道，得到K個(gè)聚類，接著對(duì)當(dāng)前增量按照傳統(tǒng)K-means算法進(jìn)行迭代操作，每一次迭代都按要求進(jìn)行適當(dāng)?shù)母淖?，直到聚類中心不變?yōu)橹梗缓筇幚硐乱粋€(gè)增量的報(bào)道。詳細(xì)算法過(guò)程如下:

? Step1 對(duì)于每一個(gè)增量，設(shè)它的報(bào)道規(guī)模為Ni(i=1,2,…，r)，判定報(bào)道S是否是第一篇報(bào)道，如果是，使用報(bào)道S建立第一個(gè)話題，如果不是，計(jì)算報(bào)道S與其他話題中心的相似度；

? Step2 根據(jù)S與各個(gè)話題的相似度，找到與S相似度最高的話題T1；

? Step3 判定報(bào)道S與話題T1的相似度是否大于閾值θ。如果相似度大于閾值θ，就把報(bào)道S歸入話題T1，否則，使用S建立一個(gè)新話題，并更新話題數(shù)K；

? Step4 判定報(bào)道規(guī)模Ni是否為0。如果Ni為0，則輸出話題數(shù)K和聚類結(jié)果，并轉(zhuǎn)到Step5；否則，轉(zhuǎn)到Step1，處理下一篇報(bào)道；

? Step5 根據(jù)傳統(tǒng)增量聚類的結(jié)果，計(jì)算K個(gè)話題的均值，作為傳統(tǒng)K-means算法的初始聚類中心；

? Step6 根據(jù)式(2)和式(3)，計(jì)算每個(gè)聚類中心與其余所有新聞報(bào)道之間的余弦距離。根據(jù)余弦距離的大小，把每個(gè)報(bào)道分配到余弦距離最小的聚類中心，也就是把每個(gè)報(bào)道分配到最近的聚類中心；

? Step7 重新計(jì)算每個(gè)聚類的均值，作為該話題類的新聚類中心；

? Step8 如果所有的聚類中心不發(fā)生變化，這說(shuō)明目標(biāo)函數(shù)收斂到最小值，轉(zhuǎn)向Step9；否則，修改聚類中心，按照Step6和Step7迭代；

? Step9 判斷增量數(shù)i是否為0。如果i為0，算法終止，并輸出話題數(shù)K和聚類結(jié)果；否則，轉(zhuǎn)到Step1，處理下一個(gè)增量的報(bào)道。

5 實(shí)驗(yàn)結(jié)果與分析

根據(jù)傳統(tǒng)增量聚類算法、傳統(tǒng)K-means算法和基于話題檢測(cè)的自適應(yīng)的增量K-means算法的算法思想，分別把它們作為話題檢測(cè)算法設(shè)計(jì)話題檢測(cè)實(shí)驗(yàn)，得到相應(yīng)的話題檢測(cè)與跟蹤評(píng)測(cè)結(jié)果，對(duì)比評(píng)測(cè)結(jié)果評(píng)估基于話題檢測(cè)的自適應(yīng)的增量K-means算法作為話題檢測(cè)關(guān)鍵技術(shù)的性能。

5.1 實(shí)驗(yàn)結(jié)果

在實(shí)驗(yàn)中，分詞程序是中科院計(jì)算所軟件室提供的ICTCLAS[12]；語(yǔ)料是中科院計(jì)算所譚松波博士提供14 150篇中文新聞報(bào)道[13-14]，第一層是12個(gè)主題，第二層是60個(gè)話題。對(duì)每個(gè)話題檢測(cè)算法，在實(shí)驗(yàn)參數(shù)和實(shí)驗(yàn)環(huán)境相同的條件下，分別用60個(gè)話題進(jìn)行測(cè)試，得到60個(gè)測(cè)試結(jié)果，對(duì)這60個(gè)結(jié)果進(jìn)行歸一化后，得到能夠反映話題檢測(cè)性能的話題檢測(cè)與跟蹤評(píng)測(cè)結(jié)果，即: 歸一化檢測(cè)開(kāi)銷(xiāo)(CDet)Norm[15-16]。最后，根據(jù)實(shí)驗(yàn)的話題檢測(cè)與跟蹤評(píng)測(cè)結(jié)果分別評(píng)估傳統(tǒng)的增量聚類、傳統(tǒng)的K-means算法和自適應(yīng)的增量K-means算法的性能。實(shí)驗(yàn)的評(píng)測(cè)結(jié)果如表1所示。

為了便于分析這個(gè)新算法對(duì)話題檢測(cè)性能的影響，用Excel 2003中的圖表向?qū)Чぞ甙驯?中的數(shù)據(jù)映射成圖1。

圖1 話題檢測(cè)關(guān)鍵技術(shù)與話題檢測(cè)性能之間的變化趨勢(shì)圖

5.2 實(shí)驗(yàn)分析

在實(shí)驗(yàn)中，根據(jù)評(píng)測(cè)結(jié)果評(píng)測(cè)話題檢測(cè)性能，然后根據(jù)話題檢測(cè)性能評(píng)估聚類算法作為話題檢測(cè)關(guān)鍵技術(shù)的性能。在同等條件下，評(píng)測(cè)結(jié)果越小，說(shuō)明話題檢測(cè)性能越好，也表明該聚類算法作為話題檢測(cè)關(guān)鍵技術(shù)的性能越好。

根據(jù)表1和圖1，傳統(tǒng)的增量聚類作為話題檢測(cè)關(guān)鍵技術(shù)時(shí)，TDT評(píng)測(cè)結(jié)果為0.425 7；傳統(tǒng)的K-means算法作為話題檢測(cè)關(guān)鍵技術(shù)時(shí)，TDT評(píng)測(cè)結(jié)果為0.397 2；自適應(yīng)的增量K-means算法作為話題檢測(cè)關(guān)鍵技術(shù)時(shí)，TDT評(píng)測(cè)結(jié)果為0.378 9。因此，在同等條件下，基于自適應(yīng)的增量K-means算法的評(píng)測(cè)結(jié)果比基于傳統(tǒng)的增量聚類的評(píng)測(cè)結(jié)果減少了10.994%，即自適應(yīng)的增量K-means算法的性能比傳統(tǒng)的增量聚類提高了10.994%；基于自適應(yīng)的增量K-means算法的評(píng)測(cè)結(jié)果比基于傳統(tǒng)的K-means算法的評(píng)測(cè)結(jié)果減少了4.607%，即自適應(yīng)的增量K-means算法的性能比傳統(tǒng)的K-means算法提高了4.607%。除此之外，傳統(tǒng)的K-means算法需要對(duì)K值初始化，而且K的初始化值對(duì)該算法性能的影響很大，而自適應(yīng)的增量K-means算法用傳統(tǒng)增量聚類的思想自適應(yīng)地調(diào)節(jié)K值，在很大程度上減少了K初始化值對(duì)該算法性能的影響；傳統(tǒng)的增量聚類能夠得到局部最優(yōu)解，但很難得到全局最優(yōu)解，而自適應(yīng)的K-means算法通過(guò)迭代過(guò)程能夠得到全局最優(yōu)解，很好地解決了傳統(tǒng)的增量聚類所面臨的問(wèn)題。

6 結(jié)論

本文分析了話題檢測(cè)任務(wù)的定義和特點(diǎn)，對(duì)比了傳統(tǒng)的增量聚類和K-means算法的優(yōu)缺點(diǎn)，然后通過(guò)傳統(tǒng)的K-means算法改進(jìn)了傳統(tǒng)的增量聚類，提出了基于話題跟蹤的自適應(yīng)增量K-means算法。在同等條件下，經(jīng)過(guò)廣泛而深入地研究和分析可知，新算法作為話題檢測(cè)關(guān)鍵技術(shù)具有良好的性能。

[1] 鄭斐然,苗奪謙,張志飛,等.一種中文微博新聞話題檢測(cè)的方法[J].計(jì)算機(jī)科學(xué)，2012，39(1): 138-141

[2] 張闊，李涓子，吳剛,等. 基于關(guān)鍵詞元的話題內(nèi)事件檢測(cè) [J]. 計(jì)算機(jī)研究與發(fā)展，2009，46(02): 245-251.

[3] 李忠俊.基于話題檢測(cè)與聚類的內(nèi)部輿情監(jiān)測(cè)系統(tǒng)[J].計(jì)算機(jī)科學(xué)，2012，39(12): 241-244.

[4] Nist. The 2004 Topic Detection and Tracking (TDT2004) Task Definition and Evaluation Plan. http://www.itl.nist.gov/iad/mig/tests/tdt/2004/TDT04.Eval.Plan.v1.2.pdf.

[5] 馬慧芳,王博. 基于增量主題模型的微博在線事件分析[J]. 計(jì)算機(jī)工程, 2013, 39(3): 191-196.

[6] 駱衛(wèi)華，于滿泉，許洪波,等. 基于多策略優(yōu)化的分治多層聚類算法的話題發(fā)現(xiàn)研究[J]. 中文信息學(xué)報(bào)，2006，20(1): 29-36.

[7] 洪宇，張宇，劉挺,等. 話題檢測(cè)與跟蹤的評(píng)測(cè)及研究綜述[J]. 中文信息學(xué)報(bào)，2007，21(6)： 71-87.

[8] 呂明磊，劉冬梅，曾智勇.一種改進(jìn)的K-means聚類算法的圖像檢索方法[J]. 計(jì)算機(jī)科學(xué)，2013，40(8): 285-288.

[9] 毛嘉莉. 基于K-means的文本聚類算法[J]. 計(jì)算機(jī)系統(tǒng)應(yīng)用，2009，(10): 85-87.

[10] 李勝東，呂學(xué)強(qiáng)，魏震等.基于兩層閾值的話題報(bào)道表示模型[J]. 華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版)，2013，41(S2)： 117-120.

[11] Li Xinwu. Research on Text Clustering Algorithm Based on K_means and SOM[C]//Proceedings of ShangHai: International Symposium on Intelligent Information Technology Application Workshops, 2008: 341-344.

[12] 中科院計(jì)算所. 基于多層隱馬模型的漢語(yǔ)詞法分析系統(tǒng)ICTCLAS. http://www.nlp.org.cn/project/project.php?proj_id=6.

[13] 譚松波，王月粉. 中文文本分類語(yǔ)料庫(kù)-TanCorpV1.0. http://www.searchforum.org.cn/tansongbo/corpus.htm.

[14] Tan S B, et al. A Novel Refinement Approach for Text Categorization[C]//Proceedings of ACM CIKM, 2005.

[15] Tim Leek, Richard Schwartz, Srinivasa Sista. Probabilistic Approaches to Topic Detection and Tracking [J]. Data Mining and Knowledge Discovery. 2003, 7(3): 67-83.

[16] Yiming Yang, Jaime Carbonell, Ralf Brown, et al. Multi-Strategy Learning for Topic Detection and Tracking: a joint report of CMU approaches to multilingual TDT[C]//Proceedings of TDT 2002 Workshop. 2002: 85-114.