基于話題檢測的自適應(yīng)增量K-means算法

李勝東，呂學強，施水才，孫 軍

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

1 引言

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

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

2 話題檢測任務(wù)的特點

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

3 聚類算法

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

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

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

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

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

(1)

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

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

(2)

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

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

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

(3)

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

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

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

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

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

自適應(yīng)的增量K-means算法把所有中文新聞報道語料劃分為r個增量，每個增量報道的規(guī)模為Ni(i=1,2,…,r)。對于每一個增量，先按傳統(tǒng)增量聚類處理所有報道，得到K個聚類，接著對當前增量按照傳統(tǒng)K-means算法進行迭代操作，每一次迭代都按要求進行適當?shù)母淖?，直到聚類中心不變?yōu)橹?，然后處理下一個增量的報道。詳細算法過程如下:

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

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

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

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

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

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

? Step7 重新計算每個聚類的均值，作為該話題類的新聚類中心；

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

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

5 實驗結(jié)果與分析

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

5.1 實驗結(jié)果

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

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

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

5.2 實驗分析

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

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

6 結(jié)論

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

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

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

[3] 李忠俊.基于話題檢測與聚類的內(nèi)部輿情監(jiān)測系統(tǒng)[J].計算機科學，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]. 計算機工程, 2013, 39(3): 191-196.

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

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

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

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

[10] 李勝東，呂學強，魏震等.基于兩層閾值的話題報道表示模型[J]. 華中科技大學學報(自然科學版)，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] 中科院計算所. 基于多層隱馬模型的漢語詞法分析系統(tǒng)ICTCLAS. http://www.nlp.org.cn/project/project.php?proj_id=6.

[13] 譚松波，王月粉. 中文文本分類語料庫-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.