基于多元詞組和數(shù)據(jù)流聚類的熱點話題動態(tài)發(fā)現(xiàn)

黃貴懿

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

?

基于多元詞組和數(shù)據(jù)流聚類的熱點話題動態(tài)發(fā)現(xiàn)

黃貴懿

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

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

[關(guān)鍵詞]多元詞組；數(shù)據(jù)流聚類；TF-IDF；CluStream；熱點話題

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

1主題抽取現(xiàn)狀

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

1)基于統(tǒng)計的方法.通過計算文本關(guān)鍵詞上下文頻次和文本間出現(xiàn)情況來確定權(quán)重，通過權(quán)重的大小來抽取文本的主題詞.

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

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

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

2特征關(guān)鍵詞的提取

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

2.1文本預處理

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

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

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

2.2改進TF-IDF方法

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

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

(1)

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

2.2.1指代詞加值

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

2.2.2增加位置加權(quán)

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

2.2.3增加詞長加權(quán)

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

(2)

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

2.2.4增加信息量加權(quán)

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

(3)

2.2.5綜合加權(quán)

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

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

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

(4)

2.3多元詞語組合

2.3.1關(guān)鍵詞組合

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

2.3.2特征關(guān)鍵詞提取

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

3基于數(shù)據(jù)流的聚類

3.1算法選擇

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

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

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

3.2算法描述

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

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

(CF2x,CF1x,CF2t,CF1t,n)

(5)

上式中，CF2x為數(shù)據(jù)值的平方和，CF1x為數(shù)據(jù)值的和，CF2t為時間戳的平方和，CF1t為時間戳的和，n為集內(nèi)數(shù)據(jù)項的數(shù)目.

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

3.3算法實現(xiàn)步驟

3.3.1初始化簇

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

(6)

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

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

3.3.2在線快速處理

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

3.3.3離線處理

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

4實驗結(jié)果

4.1特征關(guān)鍵詞提取實驗

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

表1　測試數(shù)據(jù)加權(quán)前后的TF-IDF值

4．2數(shù)據(jù)流聚類實驗

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

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

表2　測試數(shù)據(jù)前5項聚類結(jié)果

5結(jié)語

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

[參考文獻]

[1]劉知遠.基于文檔主題結(jié)構(gòu)的關(guān)鍵詞抽取方法研究[D].北京：清華大學,2011.

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

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

[4]史成金,程轉(zhuǎn)流.基于混合聚類的中文詞聚類[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—)，男，重慶榮昌人，高級工程師，碩士，主要從事計算機應(yīng)用與教育技術(shù)方面的研究.

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

[收稿日期]2015-10-30