陳立偉，謝朝陽，唐權(quán)華

（1.西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院，四川 成都610031；2.西南科技大學(xué) 土木工程與建筑學(xué)院，四川 綿陽621010；3.西南科技大學(xué) 計算機學(xué)院，四川 綿陽621010；4.江西師范大學(xué) 軟件學(xué)院，江西 南昌330022）

0 引 言

主題檢測與跟蹤（topic detection and tracking，TDT）需要從文本或語音中檢測出主題，分析主題間的關(guān)聯(lián)，發(fā)現(xiàn)和收集同主題的材料，需要綜合應(yīng)用自然語言處理、數(shù)據(jù)檢測、信息檢索等多學(xué)科的知識完成。TDT可以應(yīng)用到新聞報道追蹤、大規(guī)模網(wǎng)絡(luò)信息自動處理、金融股票市場分析等國民經(jīng)濟的多個領(lǐng)域，引發(fā)大量學(xué)者的研究興趣［1－3］。

主題檢測一般是基于聚類方法實現(xiàn)。為對主題聚類，需要進(jìn)行距離比較，所以首先對主題進(jìn)行量化描述，即構(gòu)建主題模型?，F(xiàn)有主題描述主要有向量空間模型和語言模型。向量空間模型［4，5］將報道分解到特征空間，再根據(jù)各特征在文本中出現(xiàn)的概率估計其權(quán)重，最后利用夾角余弦評價文本的相似性。語言模型［6］分別將2個文本視作一個報道和一個主題，計算報道產(chǎn)生于主題的概率分布，再綜合2個概率分布作為2個文本的相關(guān)性。使用單一結(jié)構(gòu)的特征向量描述主題和報道可能造成子主題間不正確匹配，并形成錯誤語義，誤導(dǎo)新主題的識別，可以將主題和報道劃分為不同子主題，根據(jù)相關(guān)子主題的比例關(guān)系和分布關(guān)系識別新主題，可以改善新事件檢測［5］。直接比較主題相似度并不能全面描述主題關(guān)系，基于主題語義依存線索的關(guān)系識別方法比基于語義相似度的識別方法在性能上有較大提升［7］。全局主題演化能夠獲得較好的模型參數(shù)，而局部主題演化則能產(chǎn)生細(xì)粒度主題，反映新主題的產(chǎn)生和舊主題的消亡［7］。

對主題檢測的另一方面研究是對聚類方法的改進(jìn)。在主題檢測聚類過程中，通常需要設(shè)定閾值，考慮主題的時間集中性，設(shè)置時間信息的動態(tài)閾值模型可以改善主題檢測系統(tǒng)的性能［4］。主題間的邊界通常并不明確，使用潛在狄利特利分布 （latent Dirichlet allocation）［8－10］可以捕獲文本中的潛在主題，在此基礎(chǔ)上構(gòu)建多層次分割模型 （hierarchical segmentation model）則可解決其中主題異構(gòu)和穩(wěn)定性等問題［7］。隨著網(wǎng)絡(luò)信息的日益增長，主題檢測效率成為一個日益突出的問題，基于增量型聚類的主題檢測方法則可以提高主題檢測的效率和準(zhǔn)確率［11］。

綜合來看，現(xiàn)有主題檢測主要針對固有的規(guī)范文本進(jìn)行研究，少有對非正式的、不規(guī)范的文本中主題檢測研究成果。雖然微博信息的出現(xiàn)引起了個別研究的注意，但相關(guān)研究仍然沿用了傳統(tǒng)向量空間模型對標(biāo)準(zhǔn)文本的描述方式，未能從根本解決互聯(lián)網(wǎng)上微博、BBS、新聞回帖［12］等海量不規(guī)范文本的主題檢測精確度和效率問題。

1 主題的詞網(wǎng)表達(dá)

一個主題通常需要由多個關(guān)鍵詞表達(dá)，為在詞網(wǎng)中識別和分類主題，首先需要基于詞網(wǎng)對主題相關(guān)詞匯進(jìn)行索引；互聯(lián)網(wǎng)中經(jīng)常使用同音、形似、諧音等替代詞匯談?wù)撏恢黝}，在表達(dá)主題時需要有相應(yīng)的適應(yīng)機制。

為更全面分析主題間的潛在關(guān)聯(lián)，將詞語記錄為詞意、詞形、發(fā)音、詞性等多個分量組成的向量，詞語間的關(guān)系通過向量的各分量 （pi）比較及分量間的關(guān)系產(chǎn)生，詞語間的關(guān)系強度記錄為

式中：compi——第i個分量的比較方法，λi——第i個分量的權(quán)重，N——分量的總數(shù)。

主題在詞網(wǎng)中表現(xiàn)為一組被討論的詞語，對與這些詞相關(guān)的討論也可以視作對主題的討論，因此無法準(zhǔn)確地劃分出主題邊界。同一主題詞語間有固定的屬性關(guān)聯(lián)，具有穩(wěn)定性，也有臨時的事件關(guān)聯(lián)，具有時效性。為客觀反映一個詞語 （w）與主題 （Topic）的相關(guān)程度，定義詞語對主題的從屬度 （Mw，Topic）如下

式中：tw，i——詞語w 第i 次出現(xiàn)的時間，t0——主題參照時間。

主題的熱度應(yīng)反映主題包含詞匯被提及的頻率，詞匯的出現(xiàn)頻率fw可以簡單地認(rèn)為是單位時間出現(xiàn)次數(shù)即

式中：T——統(tǒng)計時間周期，Kw，T——周期內(nèi)詞匯w 出現(xiàn)的次數(shù)。

2 主題的熱度擴散

主題的熱度指一段時期內(nèi)參與討論者的數(shù)量和次數(shù)，根據(jù)觀察到的主題出現(xiàn)次數(shù)更新主題的熱度有利于熱門主題的及時發(fā)現(xiàn)。主題具有相關(guān)性，一條互聯(lián)網(wǎng)消息往往涉及多個主題，如何根據(jù)一條互聯(lián)網(wǎng)消息查找相關(guān)主題并更新其熱度是發(fā)現(xiàn)熱門主題的關(guān)鍵技術(shù)之一。詞匯出現(xiàn)頻率越大，詞對主題的從屬度越高，則主題熱度越高，因此可將主題的熱度HTopic定義為

按以上方式定義主題熱度后，則可以按熱度增長方向劃分主題即

當(dāng)一個詞語被提及時，其所屬的主題熱度應(yīng)該相應(yīng)增加，與其關(guān)聯(lián)的詞語熱度也應(yīng)該直接，即應(yīng)該增加其相關(guān)聯(lián)詞語的出現(xiàn)頻率，然而這種增加可能引起主題的邊界無限擴散。為解決這一矛盾，引入各向異性擴散 （anisotropic diffusion）方程作為擴散標(biāo)準(zhǔn)，各向異性擴散方程原型如下

式中：——梯度算子，Δ——拉普拉斯算子，c——擴散函數(shù)，為方便計算，選用c的形式為

式中：C——常數(shù)。

各向異性擴散方程在產(chǎn)生多尺度圖像時有效地保護(hù)了圖像邊緣，借鑒些經(jīng)驗，本課題將之引入用于保護(hù)主題邊緣，其中擴散變量u為詞語的出現(xiàn)頻率fw，常數(shù)C 由詞語間的關(guān)系強度代替，則當(dāng)某詞匯w 受到刺激 （被提及）時，與之相關(guān)的詞匯v也獲得相應(yīng)的刺激擴散，即

主題在詞網(wǎng)中表現(xiàn)為一組被討論的詞語，對與這些詞相關(guān)的討論也可以視作對主題的討論，因此無法準(zhǔn)確地劃分出主題邊界。同一主題詞語間有固定的屬性關(guān)聯(lián)，具有穩(wěn)定性，也有臨時的事件關(guān)聯(lián)，具有時效性。為客觀反映一個詞語 （w）與主題 （Topic）的相關(guān)程度，定義詞語對主題的從屬度 （Mw，Topic）如下

式中：tw，i——詞語w 第i 次出現(xiàn)的時間，t0——主題參照時間。

主題的熱度應(yīng)反映主題包含詞匯被提及的頻率，詞匯的出現(xiàn)頻率fw可以簡單地認(rèn)為是單位時間出現(xiàn)次數(shù)即

式中：T——統(tǒng)計時間周期，Kw，T——周期內(nèi)詞匯w 出現(xiàn)的次數(shù)。

3 基于熱度排序的熱門主題檢測

由于主題在詞網(wǎng)中表現(xiàn)為一個節(jié)點，主題的熱度對應(yīng)于相關(guān)詞匯熱度的綜合，要獲得熱門的主題，需要對每個主題計算熱度并排序，當(dāng)數(shù)據(jù)量較大時，這是一個巨大的計算任務(wù)。所幸的是，主題和詞網(wǎng)的數(shù)據(jù)是逐漸累和變化的，是一個漸變的過程，因此，可以保留一個現(xiàn)有的排序列表，僅在添加新數(shù)據(jù)時將新數(shù)據(jù)與原數(shù)據(jù)進(jìn)行比較排序?；谶@些思路，為快速檢測熱門主題，在動態(tài)詞網(wǎng)索引樹上引入熱度比較排序機制和被動冷卻機制。

基于動態(tài)樹的有限存儲詞網(wǎng)索引：為詞網(wǎng)建立索引不僅有助于高效地更新主題熱度，也有利于快速發(fā)現(xiàn)熱門主題，但由于詞網(wǎng)的詞庫較大，如果全部索引不僅降低檢索效率，而且會給存儲空間帶來巨大負(fù)擔(dān)。為解決這個問題，本課題擬采用動態(tài)樹的方法對熱門詞語進(jìn)行索引基本思路如下：首先選擇少量歷史使用頻率最高的詞語作為索引樹根，然后對現(xiàn)有索引樹的每個節(jié)點依次查找其相關(guān)詞匯，將其中使用頻率最大的加入索引樹的子節(jié)點，直到索引存儲空間占滿；更新詞匯頻率時比較索引樹的使用頻率，若某詞語使用頻率大于索引樹的最小頻率，則去除索引樹的最小頻率節(jié)點，并將該詞語作為與其最近的索引書節(jié)點的子節(jié)點；若更新了索引樹節(jié)點的使用頻率，則比較它與其父節(jié)點的使用頻率，若子節(jié)點頻率大于父節(jié)點，則將二者的父子關(guān)系對換。

熱度比較排序機制：將動態(tài)樹上每層節(jié)點保存為一個有序鏈，當(dāng)某個詞語頻率增加時比較它與它前面評語的出現(xiàn)頻率，若新頻率大于前面詞語的頻率，則交換它們在有序鏈中的位置。利用這樣的比較排序機制，可以使熱度的排序計算復(fù)雜度降低到O（N）級別。

被動冷卻機制：一個熱門主題隨時間推移可能被人們遺忘，主題不再被人提及可稱為冷卻過程，冷卻通常需要過程結(jié)束才能準(zhǔn)確判斷。每個主題由普通話題變成熱門主題的過程實際上是大量對話題有相同興趣的發(fā)言者的發(fā)言過程，每個發(fā)言者對話題討論的決策過程相似，服從相同的概率分布，根據(jù)大數(shù)定律，主題的熱門過程必然為正態(tài)隨機過程，可以認(rèn)為熱門主題的關(guān)鍵詞w 在t 時刻出現(xiàn)概率Pw服從高斯分布

式中：tw0——w 最近出現(xiàn)的高峰時刻。

基于參照詞的有限聚類熱門主題發(fā)現(xiàn)：在索引樹更新過程中，如果一個詞語出現(xiàn)位置向前或向上變化，則觀察與之交換的詞是否屬于熱門主題，如果屬于，則對當(dāng)前詞語進(jìn)行熱度增長聚類，若聚類過程發(fā)現(xiàn)已知熱門主題詞語，則停止，否則增加新的熱門主題。

4 實驗結(jié)果

對某大型網(wǎng)站的微博信息進(jìn)行自動采集，截取1000份當(dāng)日最新發(fā)表的微博信息，通過人工標(biāo)注提取出前50個熱門主題并進(jìn)行排序，然后應(yīng)用本文方法對所有信息進(jìn)行分析，自動檢測微博信息中的主題，對主題的熱度進(jìn)行對比排序，結(jié)果見表1。

表1 熱門話題檢測實驗結(jié)果

表1中，熱門主題發(fā)現(xiàn)率指人工指定的熱門主題在自動檢測出的主題中出現(xiàn)比例；主題排序匹配度指被檢測出的人工指定的主題與人工排序的匹配比例；人工主題發(fā)現(xiàn)率指人工指定的主題在自動發(fā)現(xiàn)主題中出現(xiàn)的比例；自動檢測主題正確率為人工對自動檢測出的主題進(jìn)行評價，其中正確的比例；自動檢測熱門主題正確率為人工對自動檢測出的前50個主題進(jìn)行評價，其中正確的比例。

從實驗結(jié)果來看，自動檢測和排序熱門主題與人工提取的熱門主題會有一定的誤差，這個誤差主要來源于2個方面的原因：一是機器分析的信息數(shù)量較少，對主題的認(rèn)知度不夠高；二是人的主觀意思決定一些常見主題被忽略掉，而機器檢測過程并未考慮這一因素。

跟一般的信息查詢與檢索不同，話題檢測的速度與資源消耗也是需要考慮的重要因素。由于話題的參與者數(shù)量巨大，話題的種類繁多，話題討論具有一定歷史性和適時性，話題檢測過程中需要處理海量的信息，是一個典型的大數(shù)據(jù)問題，現(xiàn)有的信息檢測和數(shù)據(jù)挖掘方法一般是基于數(shù)據(jù)庫或數(shù)據(jù)倉庫，這種方式需要很大的存儲空間。本文采用詞網(wǎng)記錄和檢測話題，一方面對話題的記錄是通過關(guān)聯(lián)關(guān)系表達(dá)，對數(shù)據(jù)進(jìn)行了自然的壓縮，另一方面對信息的檢測過程僅限于對詞網(wǎng)的修改，而不需要存儲信息本身，因此理論上可以節(jié)省大量空間。為驗證這一做法對時間和空間上的節(jié)省，實驗統(tǒng)計了本文方法處理從1 M 到50G 文本數(shù)據(jù)所耗費的存儲空間和處理時間，部分統(tǒng)計結(jié)果見表2。

表2 處理數(shù)據(jù)量與時間空間統(tǒng)計

表2中，存儲空間的耗費在數(shù)據(jù)量較小時大于數(shù)據(jù)量，但當(dāng)數(shù)據(jù)量超過500 M 時，就基本不隨數(shù)據(jù)量增長，顯示出較大的空間優(yōu)勢；處理時間在2G 以下時基本隨數(shù)據(jù)量增長而線性增加，但數(shù)據(jù)量超過2G 后快速增長，這主要是由于實驗中使用了32位普通PC，實際支持內(nèi)存僅2G，本系統(tǒng)占用內(nèi)存超過500 M 時就開始使用虛擬內(nèi)存代替物理內(nèi)存，致使計算性能迅速下降。

5 結(jié)束語

本文通過將各向異性擴散技術(shù)引入詞網(wǎng)，在詞網(wǎng)中體現(xiàn)相關(guān)詞語的影響，同時保護(hù)主題間的邊界，提出有限記憶和被動冷卻機制，利用有限的存儲空間對詞網(wǎng)進(jìn)行部分索引，不掃描和處理不活動詞語，實現(xiàn)熱門主題及其詞語的快速訪問。利用有限的存儲資源記錄互聯(lián)網(wǎng)文字信息中包含的主題，對于未知主題可以自動識別和記錄，對相關(guān)主題能自動聯(lián)想。準(zhǔn)確描述主題的熱度，主題熱度要反應(yīng)互聯(lián)網(wǎng)言論對該主題及相關(guān)主題的關(guān)心程度。能根據(jù)主題熱度記憶和遺忘主題，對于熱門新主題能的產(chǎn)生記憶，對非熱門主題能迅速清除記錄。根據(jù)主題熱度的統(tǒng)計，及時發(fā)現(xiàn)熱門主題，熱門主題發(fā)現(xiàn)過程要通過局部比較實現(xiàn)，避免主題庫的全局排序或掃描。實驗數(shù)據(jù)表明，基于熱度擴散的主題檢測出的結(jié)果符合人的理解，檢測速度較快，無需要占用大量的存儲空間，是一個可行的方法。但由于時間與計算資源的限制，本文方法尚未對大規(guī)模數(shù)據(jù)進(jìn)行實踐，這將是作者下一步工作努力的方向。

［1］LI Zhongjun.Internal public opinions monitor system based on topic detection and clustering ［J］.Computer Science，2012，39 （12）：237－240 （in Chinese）.［李忠俊.基于主題檢測與聚類的內(nèi)部輿情監(jiān)測系統(tǒng) ［J］.計算機科學(xué)，2012，39 （12）：237－240.］

［2］Chen Berlin，Chen Kuan－Yu，Chen Pei－Ning，et al.Spoken document retrieval with unsupervised query modeling techniques［J］.IEEE Trans Audio，Speech and Language Processing，2012，20 （9）：2602－2612.

［3］Lappas，T，Arai B，Platakis M，et al.On burstiness－aware search for document sequences ［C］／／ACM Int Conf Knowledge Discovery and Data Mining，2009：477－486.

［4］ZHAO Hua，ZHAO Tiejun，ZHAO Xia.Using temporal information in topic detection ［J］.Computer Science，2008，35（1）：221－223 （in Chinese）.［趙華，趙鐵軍，趙霞.時間信息在主題檢測中的應(yīng)用研究 ［J］.計算機科學(xué)，2008，35 （1）：221－223.］

［5］HONG Yu，ZHANG Yu，F(xiàn)AN Jili，et al.New event detection based on division comparison of subtopic ［J］.Chinese Journal of Computers，2008，31 （4）：687－695 （in Chinese）.［洪宇，張宇，范基禮，等.基于子話題分治匹配的新事件檢測 ［J］.計算機學(xué)報，2008，31 （4）：687－695.］

［6］HONG Yu，ZHANG Yu，F(xiàn)AN Jili，et al.Chinese topic link detection based on semantic domain language model［J］.Journal of Software，2008，19 （9）：2265－2275 （in Chinese）.［洪宇，張宇，范基禮，等.基于語義域語言模型的中文主題關(guān)聯(lián)檢測 ［J］.軟件學(xué)報，2008，19 （9）：2265－2275.］

［7］MA Bin，HONG Yu，YANG Xuerong，et al.Using event dependency cue inference to recognize event relation ［J］.Acta Scientiarum Naturalium Universitatis Pekinensis，2013，49（1）：109－116 （in Chinese）.［馬彬，洪宇，楊雪蓉，等.基于語義依存線索的事件關(guān)系識別方法研究 ［J］.北京大學(xué)學(xué)報（自然科學(xué)版），2013，49 （1）：109－116.］

［8］Chien Jen－Tzung，Chueh Chuang－Hua.Topic－based hierarchical segmentation ［J］.IEEE Trans Audio，Speech and Language Processing，2012，20 （1）：55－66.

［9］ZHANG Jian，LI Fang.LDA topic evolution based on global and local modeling ［J］.Journal of Shanghai Jiaotong University，2012，46 （11）：1754－1758 （in Chinese）. ［章建，李芳.基于局部和全局的LDA 主題演化分析 ［J］.上海交通大學(xué)學(xué)報，2012，46 （11）：1754－1758.］

［10］HE Liang，LI Fang.Topic discovery and trend analysis in scientific literature based on topic model［J］.Journal of Chinese Information Processing，2012，26 （2）：109－115 （in Chinese）.［賀亮，李芳.基于主題模型的科技文獻(xiàn)主題發(fā)現(xiàn)和趨勢分析 ［J］.中文信息學(xué)報，2012，26 （2）：109－115.］

［11］ZHANG Xiaoming，LI Zhoujun，CHAO Wenhan.Research of automatic topic detection based on incremental clustering ［J］.Journal of Software，2012，23 （6）：1578－1587 （in Chinese）.［張小明，李舟軍，巢文涵.基于增量型聚類的自動主題檢測研究［J］.軟件學(xué)報，2012，23 （6）：1578－1587.］

［12］CHEN You，CHENG Xueqi，YANG Sen.Finding high quality threads in web forums ［J］.Journal of Software，2011，22 （8）：1785－1804 （in Chinese）. ［陳友，程學(xué)旗，楊森.面向網(wǎng)絡(luò)論壇的高質(zhì)量主題發(fā)現(xiàn) ［J］.軟件學(xué)報，2011，22（8）：1785－1804.］