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

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

0 引 言

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

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

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

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

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

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

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

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

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

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

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

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

2 主題的熱度擴(kuò)散

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

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

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

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

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

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

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

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

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

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

3 基于熱度排序的熱門主題檢測(cè)

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

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

熱度比較排序機(jī)制：將動(dòng)態(tài)樹上每層節(jié)點(diǎn)保存為一個(gè)有序鏈，當(dāng)某個(gè)詞語頻率增加時(shí)比較它與它前面評(píng)語的出現(xiàn)頻率，若新頻率大于前面詞語的頻率，則交換它們?cè)谟行蜴溨械奈恢?。利用這樣的比較排序機(jī)制，可以使熱度的排序計(jì)算復(fù)雜度降低到O（N）級(jí)別。

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

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

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

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

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

表1 熱門話題檢測(cè)實(shí)驗(yàn)結(jié)果

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

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

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

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

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

5 結(jié)束語

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

［1］LI Zhongjun.Internal public opinions monitor system based on topic detection and clustering ［J］.Computer Science，2012，39 （12）：237－240 （in Chinese）.［李忠俊.基于主題檢測(cè)與聚類的內(nèi)部輿情監(jiān)測(cè)系統(tǒng) ［J］.計(jì)算機(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）.［趙華，趙鐵軍，趙霞.時(shí)間信息在主題檢測(cè)中的應(yīng)用研究 ［J］.計(jì)算機(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）.［洪宇，張宇，范基禮，等.基于子話題分治匹配的新事件檢測(cè) ［J］.計(jì)算機(jī)學(xué)報(bào)，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)檢測(cè) ［J］.軟件學(xué)報(bào)，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)系識(shí)別方法研究 ［J］.北京大學(xué)學(xué)報(bào)（自然科學(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é)報(bào)，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)和趨勢(shì)分析 ［J］.中文信息學(xué)報(bào)，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）.［張小明，李舟軍，巢文涵.基于增量型聚類的自動(dòng)主題檢測(cè)研究［J］.軟件學(xué)報(bào)，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é)報(bào)，2011，22（8）：1785－1804.］