基于文本聚類的新聞采集分析系統(tǒng)設計與應用

高兆遠++程珂++張燕平++段震

摘要：隨著互聯(lián)網(wǎng)的飛速發(fā)展，網(wǎng)絡上新聞信息越來越繁雜，采集有用數(shù)據(jù)過濾冗余數(shù)據(jù)變得十分重要，但目前市面上流行軟件并不能過濾冗余新聞。采用網(wǎng)絡爬蟲、中文分詞、向量空間模型、文本聚類等技術可設計一個能自動采集新聞并能將所得信息自動聚類的系統(tǒng)，并且通過真實新聞數(shù)據(jù)驗證了該系統(tǒng)的有效性，證明其能幫助用戶發(fā)現(xiàn)、過濾重復新聞、相似新聞，并能提取熱點新聞，提高用戶閱讀新聞的效率。

關鍵詞：文本聚類；向量空間模型；網(wǎng)絡爬蟲；文本相似度；層次凝聚法

中圖分類號：TP319 文獻標識碼：A 文章編號：1009-3044（2015）11-0005-03

Design and Application of a News Gathering and Analysis System Based on Text Clustering

GAO Zhao-yuan， CHENG Ke， ZHANG Yan-ping， DUAN Zhen

（School of Computer Science and Technology， Anhui University， Hefei 230601， China）

Abstract： With the rapid development of Internet， the news information resources on network are increasingly complicated. So it becomes very important to collect useful data and to filter redundant data， but the popular software can not do that. A system can automatically gather news and cluster obtained information by using technologies such as web crawler， Chinese segmentation， vector space model and text clustering， which is proved to be an effective system through based on the real news data. And it can help users to find and filter overlapping news， extract the hot news as well as improve the efficiency to read the news.

Key words： text clustering； vector space model； web crawler； text similarity； hierarchical agglomerative method

隨著互聯(lián)網(wǎng)的飛速發(fā)展，人們獲取信息的方式發(fā)生了翻天覆地的變化，越來越多的信息涌入人們眼前。面對網(wǎng)絡上繁雜的新聞信息，采集有用數(shù)據(jù)過濾冗余數(shù)據(jù)對于我們來說是十分重要的。建立專門的新聞采集分析系統(tǒng)，從相關網(wǎng)站采集有效的新聞信息并過濾重復新聞、相似新聞，可以減少很多工作量。但目前市面上流行的新聞采集分析系統(tǒng)并沒有有效地做到分析新聞的效果，對新聞的過濾僅僅停留在正則匹配、關鍵字檢索等層面，本文設計的系統(tǒng)旨在完善以往的新聞采集分析系統(tǒng)，通過文本聚類技術有效地對所采集到的海量新聞數(shù)據(jù)進行聚類，從而過濾重復或相似新聞，并提取出熱點新聞，提高閱讀新聞效率。

1 相關工作

1.1 網(wǎng)絡爬蟲技術

網(wǎng)絡爬蟲，又被稱為網(wǎng)頁蜘蛛，是一種按照一定的規(guī)則，自動的抓取網(wǎng)絡信息的程序或者腳本[1]。網(wǎng)絡爬蟲技術在大量自動獲取網(wǎng)絡信息中使用廣泛，通常由頁面源碼獲取、URL提取、URL重復檢測、頁面信息提取等模塊組成。其中，頁面源碼獲取模塊的性能直接影響網(wǎng)絡爬蟲的工作性能，因此該模塊常采用多線程、異步以及超時設置等技術；URL提取和URL重復檢測模塊決定了網(wǎng)絡爬蟲的覆蓋率和效率；頁面信息提取模塊的方法從頁面中提取出新聞正文等信息，其決定了所采集數(shù)據(jù)的準確性。

1.2 中文自動分詞

分詞的目的是將新聞中的句子分割成詞語，為計算文本相似度做準備。中文自動分詞有多種方法，大致可歸為三類：基于詞典的分詞方法、基于統(tǒng)計的分詞方法和基于理解的分詞方法[2]。其中基于詞典的分詞方法使用最為廣泛，其常用的分詞方法有最大匹配法和逆向最大匹配法。目前，中文自動分詞技術已很成熟，常用的開源分詞工具盤古分詞、哈工大語言云（LTP-cloud）、Stanford漢語分詞工具等都能準確高效的將文本分割成詞語。

1.3 文本相似度計算

計算文本相似度是文本聚類的基礎，其有兩種常用算法，一是基于語義場，利用同義詞詞林等計算詞語相似度，再通過詞語相似度得出文本相似度。二是被稱為向量空間模型（VSM）的一種算法，其基于大規(guī)模語料庫等統(tǒng)計信息，通過選取特征詞，建立特征向量，利用向量夾角的余弦值來計算相似度，其余弦值越大說明文檔越相似。其中，后者算法計算速度較快，因此在涉及大量文本時，通常采用后者算法進行文本相似度計算。

1.4 文本自動聚類

文本自動聚類是本文最重要的工作之一，其聚類效果決定了過濾重復新聞、相似新聞的能力。目前，文本聚類方法主要有層次凝聚法、平面劃分法、簡單貝葉斯聚類法、K-最近鄰參照聚類法、分級聚類法以及基于概念的文本聚類法等[3]。其中，層次凝聚法（以G-HAC算法為代表）因?qū)崿F(xiàn)簡單且聚類效果較好而被廣泛使用。

2 系統(tǒng)實現(xiàn)

本文針對上述工作，建立了如下系統(tǒng)流程圖，其中新聞采集流程使用的是網(wǎng)絡爬蟲技術。

圖1 系統(tǒng)流程圖

2.1 基于網(wǎng)絡爬蟲技術的新聞采集

本文所提出的網(wǎng)絡爬蟲是從網(wǎng)易新聞列表頁和搜狐新聞列表頁URL開始，循環(huán)執(zhí)行以下的流程：從待抓取URL隊列中取出一個URL，把相對應的源碼下載下來，對下載回來的源碼進行解析處理得到新的URL。驗證得到的URL在數(shù)據(jù)庫中是否存在，如果不存在則代表沒有被爬取過，將其加入到待爬取URL隊列中，爬取流程如圖2所示。

圖2 爬蟲流程圖

下面，本文以網(wǎng)易新聞網(wǎng)為例，詳細說明網(wǎng)絡爬蟲運行的過程。

圖3 網(wǎng)易新聞網(wǎng)頁面示例

如圖3所示，它給出了網(wǎng)易新聞網(wǎng)的頁面版式，從上面可以看出，該版面上包含的有用信息主要是新聞標題和新聞URL。分析該頁面網(wǎng)頁源代碼得出圖4。

圖4 網(wǎng)頁源碼中有關新聞URL的部分

如圖4所示，它給出了網(wǎng)易新聞網(wǎng)的網(wǎng)頁源代碼中有關新聞URL的部分，通過觀察可以得出結(jié)論，“”和“”都是描述新聞列表中有關新聞URL的部分，標簽“”、“”之間則是新聞標題。根據(jù)這一結(jié)論，使用正則表達式可輕松提取新聞的URL和標題，新聞發(fā)表時間、正文等信息也可通過類似過程得到，這里不再贅述。

2.2 中文自動分詞

為節(jié)省項目時間，本文并未實現(xiàn)分詞算法，而是直接使用了成熟的盤古分詞算法來處理新聞文本。盤古分詞是一個中英文分詞組件，作者針對比較復雜的多元分詞提出了多元分詞的冗余度（Redundancy）和多元分詞結(jié)果的權重級別（Rank）兩個概念[4]。多元分詞中一句話會有很多種分詞組合，而冗余度可以控制這個組合的數(shù)量，權重級別可以控制分詞結(jié)果的選擇，因此盤古分詞可以有效解決復雜的多元分詞問題。

盤古分詞分詞速度快且效果很好，滿足了本文要求。比如上文圖3紅框選擇新聞“中國空軍加強中緬邊境針對性空中巡邏警示”中句子“申進科上校指出，中國空軍將采取措施加強中緬邊境空中應對行動，嚴密關注空情動態(tài)，維護國家領空主權。”，系統(tǒng)中分詞模塊將其分割成“申進科”、“指出”、“中國空軍”、“采取”、“領空主權”等詞。另外，盤古分詞可通過設置參數(shù)將待分詞句子中虛詞“的”、“地”、“嘛”等詞過濾，只保留有意義的實詞，從而提高文本相似度計算效率。本文查看了100篇網(wǎng)絡新聞的分詞結(jié)果，證明盤古分詞能將新聞有效分割。

2.3 基于向量空間模型（VSM：vector space model）的新聞文本相似度計算

在VSM中，一個特征向量表示一篇文本，每個特征向量由其特征項及權值構(gòu)成。權值定義方法中使用較多的是TF-IDF（term frequency–inverse document frequency）方法，它綜合考慮了特征項的詞頻（TF）和逆文本頻率指數(shù)（IDF）。TF指特征項在某一文本中出現(xiàn)的頻率，TF=d/D，其中d表示特征項在文本中出現(xiàn)的次數(shù)，D表示該文本的總字數(shù)；IDF=log（N/n），其中N為全部文本數(shù)，n為全部文本中包含特征項的文本數(shù)[5]。IDF反映特征項在全部文本中的分布情況，IDF值越大特征項區(qū)分度越大，特征項也越重要。在TF-IDF方法中，權值W=TF·IDF，這種權值定義方法，降低了高頻卻低區(qū)分度特征項的權重，使權值的定義更加準確。在數(shù)學中，兩個向量間的夾角越小，夾角的余弦值越大，這兩個向量越接近平行，也越相似。因此可用向量間夾角的余弦值來代替新聞間的相似度，即

[Sim=cosθ=a?b] （1）

其中為Sim新聞間相似度，θ為新聞間夾角，a和b分別為兩篇新聞對應的特征向量，為向量a和向量b的內(nèi)積，|a|為向量a的模。得到新聞間相似度后，給予閾值即可定性判斷出新聞是否相似。

同樣使用上文圖3紅框選擇新聞1“中國空軍加強中緬邊境針對性空中巡邏警示”作為例子來說明向量空間模型，并從搜狐新聞網(wǎng)上選取新聞2“中緬邊境數(shù)架殲-7戰(zhàn)機掛實彈 哨兵荷槍實彈警戒”用于計算與新聞1間的相似度。兩篇新聞的標題和正文內(nèi)容如圖5所示。

圖5 兩篇新聞的標題和正文

首先，我們對新聞1的標題和內(nèi)容進行分詞并統(tǒng)計各個詞語的詞頻（TF），得到向量如下：

[????????14??????????...0.02620.01570.01570.01050.01570.00520.0052...]

然后，計算各個詞語的逆文本頻率指數(shù)（IDF），并求出各個詞語的TF-IDF值，因為在1000篇隨機新聞中有5篇新聞出現(xiàn)“中國空軍”一詞，因此“中國空軍”的IDF值為7.6439，其TF-IDF值為0.2001，求出各個詞語的TF-IDF值后得到新聞1的特征向量：

使用相同方法，我們也可以求出新聞2的特征向量，在此不再重復。最后，我們使用公式1計算出這兩篇新聞間相似度為60.34%。

2.4 基于層次凝聚法的新聞文本自動聚類

層次凝聚法是目前常用的文本聚類算法之一，它是一種自底向上的算法。該方法復雜度高，但效果較好，聚類過程中只需掃描聚類樣本一次[6]。

其基本流程如下：

a） 將待聚類的每個文本di都作為一個獨立類別ci，即ci = {di}。

b） 根據(jù)類別間相似度Sim（cj，ck）的大小將最相似的兩個類別[cj，ck=argmaxSimcj，ckj≠k]合并為一個新類別cn。

重復步驟b）直到只有一個類別[6]，或當最相似的兩個類別間相似度值小于設定閾值。

層次凝聚法雖然簡單，但該方法需人工設定閾值，閾值的選取通常依靠一些人工分析出的先驗知識[7]，效率較低，因此文獻7提出了一種可自動搜素閾值的層次聚類方法。

另外隨著采集的新聞越來越多，聚類速度將越來越慢，此時使用分治思想，將每天采集的新聞分別聚類，再將每天聚好的類統(tǒng)一聚類，可減少聚類時間。新聞聚類后統(tǒng)計每日或每周出現(xiàn)次數(shù)最多的主題便能得到每日熱點或每周熱點新聞。

3 實驗及結(jié)果分析

本節(jié)通過實驗證明該系統(tǒng)對新聞聚類的效果，首先我們采用擬合優(yōu)度（Goodness of Fit）方法來評估聚類結(jié)果的準確性。擬合優(yōu)度的度量統(tǒng)計量是確定系數(shù)R2，R2的取值范圍是[0，1]。R2的值越接近1，說明聚類結(jié)果越好；反之，R2的值越接近0，說明聚類結(jié)果越差。R2的計算公式如下：

[R2=1-y′-y2y-y2] （2）

其中y'是預測值，即該系統(tǒng)對新聞聚類后得出的類別數(shù)，y是實際值，即測試數(shù)據(jù)的真實類別數(shù)，[y]是的y均值。

本文使用數(shù)據(jù)全部是從網(wǎng)易新聞、搜狐新聞上爬取的真實新聞，該數(shù)據(jù)包括來自于83個專題的共3046篇新聞，我們從數(shù)據(jù)中分別隨機選取15個，30個，45個，60個和75個專題的新聞構(gòu)成5個測試集，然后我們使用所設計系統(tǒng)對測試集聚類，測試集屬性和聚類結(jié)果如表1所示。

表1 測試集和聚類結(jié)果

根據(jù)表1我們計算出確定系數(shù)[R2=90.49%]，說明聚類結(jié)果較好。同時，我們根據(jù)表1還可以計算出每個測試集聚類結(jié)果的相對誤差Er。，其值越小說明聚類結(jié)果越好。Er計算公式如下：

[Er=c′-cc×100%] （3）

其中c'是聚類得出類別數(shù)，c是真實類別數(shù)，|c' - c|表示c' - c的絕對值。

我們將每個測試集的聚類相對誤差繪成如圖6所示的柱狀圖，其中相對誤差最大為20.00%，最小為6.67%，平均相對誤差為12.71%。

圖6 聚類結(jié)果相對誤差柱狀圖

通過得出的確定系數(shù)R2和相對誤差Er，我們得知該系統(tǒng)可以較好的完成聚類工作，即該系統(tǒng)可以有效的過濾冗余新聞。將該系統(tǒng)應用于過濾冗余新聞一方面可有效提取出熱點新聞，另一方面可減輕用戶閱讀量從而提高新聞閱讀效率。

4 結(jié)束語

面對互聯(lián)網(wǎng)上愈發(fā)繁雜的新聞信息，有效的過濾重復新聞、相似新聞對我們來說越來越重要。網(wǎng)絡爬蟲、文本聚類等技術為我們提供了極大的幫助。本文正是通過這些技術，設計并實現(xiàn)了基于文本自動聚類的新聞采集分析系統(tǒng)。通過實驗及結(jié)果分析，證明其對冗余新聞的過濾率高，能幫助用戶自動發(fā)現(xiàn)、過濾重復新聞、相似新聞，提高用戶閱讀新聞的效率。

參考文獻：

[1]Chao Z， Hong-yin Y. Design and Implementation of Multi-threads Web Crawler[J]. Computer Development & Applications， 2012，25（6）：65-67.

[2] 譚穎. 文本挖掘中的聚類算法研究[D]. 吉林大學， 2009.

（下轉(zhuǎn)第9頁）

（上接第7頁）

[3] 徐海霞. 聚類分析在Web文本挖掘中的應用[J]. 情報雜志， 2004， 23（12）：99-101.

[4] EAGLET. 盤古分詞#多元分詞[EB/OL]（.2008- 10- 02）[2012-07-20]. http：//www.cnblogs.cn.

[5]Wu H C， Luk R W P， Wong K F， et al. Interpreting TF-IDF term weights as making relevance decisions[J]. ACM TRANSACTIONS ON INFORMATION SYSTEMS， 2008， 26（3）：55-59.

[6] 王偉. 文本自動聚類技術研究[J]. 情報雜志， 2009， 28（2）：94-97.

[7] 向繼， 荊繼武， 高能. 一種自動搜索閾值的中文文本層次聚類方法[C]//全國網(wǎng)絡與信息安全 技術研討會， 2007.

[8] 肖毅，張林，聶笑一. 基于WEB挖掘的網(wǎng)絡爬蟲設計與實現(xiàn)[J]. 計算機系統(tǒng)應用，2013，22（9）： 60-63.

[9] 修馳. 適應于不同領域的中文分詞方法研究與實現(xiàn)[D]. 北京工業(yè)大學， 2013.

[10] 張彰，樊孝忠.一種改進的基于VSM的文本分類算法[J]. 計算機工程與設計，2006，27（21）： 4078-4080.