高兆遠(yuǎn)++程珂++張燕平++段震

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

關(guān)鍵詞：文本聚類(lèi)；向量空間模型；網(wǎng)絡(luò)爬蟲(chóng)；文本相似度；層次凝聚法

中圖分類(lèi)號(hào)：TP319 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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ā)生了翻天覆地的變化，越來(lái)越多的信息涌入人們眼前。面對(duì)網(wǎng)絡(luò)上繁雜的新聞信息，采集有用數(shù)據(jù)過(guò)濾冗余數(shù)據(jù)對(duì)于我們來(lái)說(shuō)是十分重要的。建立專(zhuān)門(mén)的新聞采集分析系統(tǒng)，從相關(guān)網(wǎng)站采集有效的新聞信息并過(guò)濾重復(fù)新聞、相似新聞，可以減少很多工作量。但目前市面上流行的新聞采集分析系統(tǒng)并沒(méi)有有效地做到分析新聞的效果，對(duì)新聞的過(guò)濾僅僅停留在正則匹配、關(guān)鍵字檢索等層面，本文設(shè)計(jì)的系統(tǒng)旨在完善以往的新聞采集分析系統(tǒng)，通過(guò)文本聚類(lèi)技術(shù)有效地對(duì)所采集到的海量新聞數(shù)據(jù)進(jìn)行聚類(lèi)，從而過(guò)濾重復(fù)或相似新聞，并提取出熱點(diǎn)新聞，提高閱讀新聞效率。

1 相關(guān)工作

1.1 網(wǎng)絡(luò)爬蟲(chóng)技術(shù)

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

1.2 中文自動(dòng)分詞

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

1.3 文本相似度計(jì)算

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

1.4 文本自動(dòng)聚類(lèi)

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

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

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

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

2.1 基于網(wǎng)絡(luò)爬蟲(chóng)技術(shù)的新聞采集

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

圖2 爬蟲(chóng)流程圖

下面，本文以網(wǎng)易新聞網(wǎng)為例，詳細(xì)說(shuō)明網(wǎng)絡(luò)爬蟲(chóng)運(yùn)行的過(guò)程。

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

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

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

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

2.2 中文自動(dòng)分詞

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

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

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

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

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

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

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

圖5 兩篇新聞的標(biāo)題和正文

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

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

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

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

2.4 基于層次凝聚法的新聞文本自動(dòng)聚類(lèi)

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

其基本流程如下：

a） 將待聚類(lèi)的每個(gè)文本di都作為一個(gè)獨(dú)立類(lèi)別ci，即ci = {di}。

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

重復(fù)步驟b）直到只有一個(gè)類(lèi)別[6]，或當(dāng)最相似的兩個(gè)類(lèi)別間相似度值小于設(shè)定閾值。

層次凝聚法雖然簡(jiǎn)單，但該方法需人工設(shè)定閾值，閾值的選取通常依靠一些人工分析出的先驗(yàn)知識(shí)[7]，效率較低，因此文獻(xiàn)7提出了一種可自動(dòng)搜素閾值的層次聚類(lèi)方法。

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

3 實(shí)驗(yàn)及結(jié)果分析

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

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

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

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

表1 測(cè)試集和聚類(lèi)結(jié)果

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

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

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

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

圖6 聚類(lèi)結(jié)果相對(duì)誤差柱狀圖

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

4 結(jié)束語(yǔ)

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

參考文獻(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] 譚穎. 文本挖掘中的聚類(lèi)算法研究[D]. 吉林大學(xué)， 2009.

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

（上接第7頁(yè)）

[3] 徐海霞. 聚類(lèi)分析在Web文本挖掘中的應(yīng)用[J]. 情報(bào)雜志， 2004， 23（12）：99-101.

[4] EAGLET. 盤(pán)古分詞#多元分詞[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] 王偉. 文本自動(dòng)聚類(lèi)技術(shù)研究[J]. 情報(bào)雜志， 2009， 28（2）：94-97.

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

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

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

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