基于多元詞組和數據流聚類的熱點話題動態發現

黃貴懿

(重慶文理學院， 重慶　永川　402160)

?

基于多元詞組和數據流聚類的熱點話題動態發現

黃貴懿

(重慶文理學院， 重慶永川402160)

[摘要]本文主要通過改進的TF-IDF算法和多元詞組動態構建來選擇特征關鍵詞，并利用CluStream數據流聚類方法，實現文本主題的動態發現.實驗表明，該方法可以較好地發現海量文本信息中不斷變化的主題信息，從而達到推薦關聯主題、動態監測輿情等目的.

[關鍵詞]多元詞組；數據流聚類；TF-IDF；CluStream；熱點話題

目前，互聯網中的新聞、論壇、博客和微博傳播著大量信息，各類文本數量龐大，產生和傳播速度極快.如何有效、快速地進行熱點話題的挖掘，抽取文本的主題內容，實現對主題內容的動態跟蹤，已成為亟待解決的問題.

1主題抽取現狀

當前主題信息抽取技術主要分為有監督的學習方法和無監督的學習方法.有監督的學習方法需要利用人工標注的文本進行學習和訓練，但在大數據環境下，面對海量文本，人工標注不可能實現，且人工標注的錯誤率較高，訓練結果的識別效果較差.無監督的方法主要有：

1)基于統計的方法.通過計算文本關鍵詞上下文頻次和文本間出現情況來確定權重，通過權重的大小來抽取文本的主題詞.

2)基于規則的方法.通過對文章、句子進行語法或語義分析，抽取主題信息.

3)基于人工智能的方法.通過計算機對訓練語料進行學習，形成抽取模型，再利用學習到的模型開展主題信息抽取[1].

以上幾種方法也有其不足之處.一是性能不理想，模型訓練時間長或識別速度慢.此外，分詞的性能不佳，直接影響識別效果.二是主題抽取不完整.一篇文章往往有幾個中心點，現有方法只能發現其一.三是主題準確性不夠.現有方法容易出現將文章順便提及的內容作為主題詞進行識別.本文基于多元詞組和數據流聚類，來實現對熱點話題動態抽取.基本方法分為兩個步驟：第一個步驟是在不依賴語料庫和訓練庫的基礎上，運用改進后的TF-IDF算法從文本中提取出特征關鍵詞；第二個步驟是運用聚類算法實現主題內容的自動發現.

2特征關鍵詞的提取

文本話題的核心是提取和發現特征關鍵詞，找到最能代表文本內容的詞匯.我們通過文本預處理、抽取關鍵詞和多元詞組組合等步驟，實現對單個文本主題的初步識別.

2.1文本預處理

1)對機器自動采集到的網頁原始文本根據DOM(Document Object Model)文檔對象模型，發現和提取核心內容，然后再進行噪聲過濾，包括去除鏈接、導航、網頁代碼等內容.

2)對文本進行分詞操作，根據中文停用詞表(有1 208個停用詞)和成語詞表過濾掉常用詞和常用成語.

3)去除文本中的介詞和形容詞，保留未識別成分的未登錄詞.

2.2改進TF-IDF方法

文章中詞的重要性往往通過其自身出現的頻率和詞語的代表性來確認.當前國內外處理詞語權重的方法有很多，其中比較有代表性的方法是利用TF-IDF函數來計算詞語在文章中的權重值.TF-IDF函數提取文檔內的高頻詞語，并計算該詞語在整個文檔集合中的低文檔頻率，從而產生出高權重TF-IDF.計算公式如下：

tfTf·idf(wi)=tf·wi·idfwi

(1)

其中：ni是候選關鍵詞Wi出現的次數，termTotal表示分詞表中與候選關鍵詞Wi長度相同的詞的總詞頻，dtfwi表示候選關鍵詞wi在詞表中的詞頻.但傳統的TF-IDF方法存在著一些弊端，一是計算權值時沒有考慮到詞語在文檔中的位置因素，文章標題或摘要的重要性常常大于文本內容；二是對詞本身的長度不敏感，文本中較長詞的重要性往往更大；三是對出現頻率比較高的領域詞無法很好地抽取，對低頻的重要人地名信息不夠敏感，沒有考慮詞語組合關系等[2].為此，本文提出一種改進后的TF-IDF算法.

2.2.1指代詞加值

文章中常常使用指代詞以代表前面的名詞，以避免詞語重復出現，但指代詞的出現極大地影響到對詞頻的統計.為了避免因指代詞影響詞頻的統計結果，本文將同一句中指代詞前序出現的名詞或命名實體tf值作重復加值處理，以避免出現遺漏重要關鍵詞的情況.

2.2.2增加位置加權

根據新聞文本的特點，候選關鍵詞出現在標題中往往比在正文中更重要.為此，將出現在標題中的關鍵詞Local(wi)權值調整為2，摘要中出現的關鍵詞權值調整為1.5，反之為1.

2.2.3增加詞長加權

詞越長往往包含更多的特指信息，比短詞或一些特定的命名實體重要性更強，但也并不意味著以簡單的詞長定權值.為此，改進后的Length(wi)詞長加權函數為：

(2)

上式中的min(Len(w1),Len(w2),…,Len(wn))為候選詞中長度最小的詞長.

2.2.4增加信息量加權

從文本話題分析中發現，人名、地名、機構名等命名實體能夠為文本話題提供區分信息，為此，對此類專有名詞加大權重值.動詞的重要性常常低于名詞，對此類詞降低權重值.具體計算方法見公式(3)：

(3)

2.2.5綜合加權

根據公式(1)、公式(2)和公式(3)，設計一個綜合加權公式，對TF-IDF加以改進和完善.wights(wi)為提取詞的權值，提取出的詞和權值存入候選關鍵詞表中.改進后的TF-IDF表示為：

weights(wi)=tf·wi·idfwi·(Local(wi)+

Length(wi)+Info(wi))/3

(4)

2.3多元詞語組合

2.3.1關鍵詞組合

中文命名實體常常由多個詞組合而成，然而普通文本經過分詞處理后，可能將大量的關鍵詞“碎片化”，從而無法獲得較長的命名實體.根據2010年CSSCI關鍵詞庫統計，中文關鍵詞中，二元和三元關鍵詞達到83﹪.為此，適當加大初始TF-IDF選取范圍，根據關鍵詞的距離Y(Y<2詞位)閾值，運用二元的Bi-Gram和三元的Tri-Gram方法，使用改進后的TF-IDF方法重新計算命名實體的權值，并將組合詞及權值存入候選關鍵詞表中.

2.3.2特征關鍵詞提取

對候選關鍵詞表中具有包含關系的子關鍵詞進行刪除，按詞的權值從高到低進行排序，并提取前V個詞作為特征關鍵詞(V的值可以根據實際情況調節).

3基于數據流的聚類

3.1算法選擇

縱觀當前國內外中文熱點話題發現的相關研究，有的采用混合聚類的主題詞聚類方法識別主題[3]；有的采用匹配和統計相結合利用余弦距離的方法聚類主題；有的通過構建共詞矩陣，測算主題詞之間的距離來進行聚類[4].本文采取基于關鍵詞的余弦相似度計算來測定文本主題的相似度.

現實中，由于網絡信息數據海量出現，產生的數量大且速度極快，使用普通靜態聚類方法不僅資源耗費多而且時間很長.為此，我們選擇數據流聚類算法，在有限的內存和時間內，經過單遍掃描實現數據的高效聚類，以適應大數據時代的信息分析要求.

當前主要的數據流聚類算法有：1)基于密度的方法(DBSCAN、DENCLUE等)，一般根據距離以相鄰的高密度區域形成聚類；2)基于劃分的方法，基于傳統的劃分聚類法加以適當的改進，以適合數據流所要求的單遍掃描和增量聚類；3)基于層次的方法(BIRCH、CURE等)，由聚類特征組成一種樹形結構來實現聚類.該方法能在數據單遍掃描下增量地維護、更新聚類特征.4)CluStream算法[5]，是一個典型的層次算法，能夠有效保持增量效率.本文綜合考慮到需要處理的文本來源于互聯網，具備大數據的相應特征，所以采用CluStream算法，以微簇(Micro-clusters)的形式維護統計信息，并在簇特征向量中增加時間變量，以實現對海量信息的聚類.

3.2算法描述

CluStream算法將數據流聚類過程分為在線(on-line)(微聚類)和離線(off-line)(宏聚類)兩個部分.在線部分負責實時處理每個新到達的數據記錄，并按設定的時間周期保存聚類結果等信息；離線部分主要是利用這些聚類結果，按用戶的具體要求分析已保存的聚類信息，并輸出最終結果.

我們將數據流視為在t1,t2，…，ti…連續到達的數據點X1,X2，…，Xi，每個xi都是d維的向量(j=1,2,…,d).在t時刻到達的數據點記作xtc，在上述數據流情況下，將微簇看作為2d+3(d是數據維度)的元組，表示為：

(CF2x,CF1x,CF2t,CF1t,n)

(5)

上式中，CF2x為數據值的平方和，CF1x為數據值的和，CF2t為時間戳的平方和，CF1t為時間戳的和，n為集內數據項的數目.

微簇需要按一定的周期存儲到磁盤文件中，以便離線查詢時使用.但數據流產生的數據量一般很大，不可能將每個時刻產生的微簇記錄都保存到磁盤中，所以引入了時間幀結構(Pyramidal Time Frame)，并將時間軸分為不同粒度的時間段，離當前越近，則相應的時間粒度越細.

3.3算法實現步驟

3.3.1初始化簇

首先存儲最初始的N個文本，對其特征關鍵詞使用Rocchio方法，計算文本間特征向量值.基于余弦文本相似度計算公式為：

(6)

上式中，di為文本的特征向量，dj為第j類文本的中心向量，wik為文本向量第k維的權重值，wjk為第j類文本向量的第k維的權重值，M為特征向量的維數.

相似度的范圍在[-1,1]之間，值越接近于1，說明兩個向量的方向更加趨向一致，兩個文本間的相似度也越高.然后采用標準的K-means算法對相似度值進行計算，形成q個微簇：M1，M2，…，Mq.

3.3.2在線快速處理

對達到的每一個文本Xik，通過特征關鍵詞先測算Xik與k個微簇中每一個的余弦相似度值，并將其放到相似度值最大的微簇Mk中.如果相似度值低于閾值Z，則另外生成一個帶有標志信息的新簇，同時刪除一個最早的簇或者合并兩個最早的簇，以保持微簇總數量的平衡，并按金字塔式的時間結構將對應時刻的微簇保存到數據表中.

3.3.3離線處理

按查詢時間點提取不同時段的聚類情況，生成最終可供顯現的聚類結果.

4實驗結果

4.1特征關鍵詞提取實驗

使用網絡爬蟲采集2013年4月至5月間3 400余條新浪、騰訊等國內新聞網頁作為實驗語料，去除網頁中的鏈接，導航等信息，處理成純文本形式，只包含新聞標題和正文，因為它在反映網絡真實環境的同時又具有一定的系統性.對所采集的語料經過PanGuSegment分詞系統進行分詞，之后我們對分詞進行預處理，對相關詞進行加權計算后，再利用改進后的TF-IDF算法提取特征關鍵詞.本實驗以《鳳凰古城商業化的是是非非》這篇2 500字的文章為例，經過分詞預處理和關鍵詞提取，選取權值靠前的60個詞如表1所示.然后，對詞進行二元和三元組合嘗試，產生“鳳凰古城、收費新政”等新二元詞組，列入候選關鍵詞列表中并重新計算權值，最后，按詞語在文本中出現的先后順序排序后，提取20個詞作為最終關鍵詞表.

表1　測試數據加權前后的TF-IDF值

4．2數據流聚類實驗

對所有候選文章，先讀取200篇的特征關鍵詞表，根據文本相似度函數計算距離值，再根據距離值大小，用K-means算法形成10個初始微簇，再依時間順序逐個讀入剩余文本.新聞主題離散性高，在算法中設定了相似度參考閾值，根據相似度值變化情況靈活調整了微簇變化的數量，根據距離值將微簇量控制在10~30間變化，設定存儲周期為20 ms，整個測試文本執行完成時間為10 s，基本能夠滿足快速動態提取主題的要求.

對提取離線結果，選取了最大的5個聚類結果列出，如表2所示.最后，選取每組聚類前兩個關鍵詞組組合后，構成熱點話題，如表2最后“話題”列所示.測試所提取結果基本與人工提取的文章話題相關度在70﹪以上.

表2　測試數據前5項聚類結果

5結語

本文首先把新聞語料通過PanGuSegment進行自動分詞，對分詞后的語料進行停用詞過濾，根據改進后的TF-IDF關鍵字提取的方法提取新聞語料庫的關鍵詞，對關鍵詞按順序進行組合和重新計算權值，通過CluStream算法對文本特征詞的相似度進行動態聚類.實驗結果證明了該方法的準確性、可行性和快速性.在下一步工作中，我們將結合語義的相似度和文本的情感特征繼續開展深入研究.

[參考文獻]

[1]劉知遠.基于文檔主題結構的關鍵詞抽取方法研究[D].北京：清華大學,2011.

[2]錢愛兵.中文新聞網頁處理與輿情分析[M].南京：南京大學出版社，2012.

[3]王小華,徐寧,諶志群.基于共詞分析的文本主題詞聚類與主題發現[J].情報科學,2011(11):1621-1625.

[4]史成金,程轉流.基于混合聚類的中文詞聚類[J].微計算機信息,2010，26(5-3)：222-223.

[5]AGGARWAL C C, HAN J, WANG J , et al.A framework for projected clustering of high dimensional data streams[C]．Proceedings 2004 VLDB ConferenceInProc of Vldb Dong,2004(30)：852-863．

(責任編輯穆剛)

Discovering of text’s hottopic based on the dynamic phrases and stream data mining

HUANG Guiyi

(Chongqing University of Arts and Sciences, Yongchuan Chongqing 402160, China)

Abstract：This paper rapidly find text’s hot topic by the improved TF-IDF algorithm and dynamic phrases that can choose the key words for text.The second, we uses clustering evolving datastreams to get hot topic for the candidate text. Discovering of text topic can detect the most important aspects of the vast information, so as to achieve the monitoring of public opinionrapidly.

Key words：dynamic phrases; data stream clustering; TF-IDF; Clustream; hot topic

[中圖分類號]TP391

[文獻標志碼]A

[文章編號]1673-8004(2016)02-0126-04

[作者簡介]黃貴懿(1979—)，男，重慶榮昌人，高級工程師，碩士，主要從事計算機應用與教育技術方面的研究.

[基金項目]全國教育信息技術研究“十二五”規劃2014年度青年課題(146242121)；重慶市永川區自然科學基金項目(YCSTC,2014NC2001).

[收稿日期]2015-10-30