基于聚類的網(wǎng)絡(luò)新聞熱點(diǎn)發(fā)現(xiàn)研究

萬曉霞，趙佳

（西華大學(xué)計(jì)算機(jī)與軟件工程學(xué)院，成都　610039）

基于聚類的網(wǎng)絡(luò)新聞熱點(diǎn)發(fā)現(xiàn)研究

萬曉霞，趙佳

（西華大學(xué)計(jì)算機(jī)與軟件工程學(xué)院，成都610039）

0　引言

在互聯(lián)網(wǎng)技術(shù)飛速發(fā)展的今天，人們獲取新聞信息的形式已不再僅限于傳統(tǒng)的單一媒體，如報(bào)紙、電視，網(wǎng)絡(luò)已成為各大媒體發(fā)布信息的主要渠道。但各大新聞門戶網(wǎng)站每天都會(huì)發(fā)布各種報(bào)道，導(dǎo)致網(wǎng)絡(luò)信息繁雜無序，并且不是每一個(gè)事件都是值得網(wǎng)民關(guān)注。因此，如何快速準(zhǔn)確地從浩瀚的網(wǎng)絡(luò)信息中挖掘出熱點(diǎn)事件，讓人們更好地了解和回顧歷史事件，是一個(gè)值得探討的問題。新聞熱點(diǎn)事件的發(fā)現(xiàn)常用聚類的方法實(shí)現(xiàn)，如今，已有許多學(xué)者做出了大量的研究，如提出了基于層次聚類的網(wǎng)絡(luò)新聞熱點(diǎn)發(fā)現(xiàn)［1］和基于二次聚類的新聞推薦方法［2］，但單一的層次聚類方法由于計(jì)算量過大，會(huì)導(dǎo)致網(wǎng)絡(luò)新聞這種大數(shù)據(jù)集的計(jì)算速度較慢，其他方法也需要人為設(shè)定初值，可能導(dǎo)致聚類結(jié)果的不準(zhǔn)確。鑒于以上原因，本文提出了將三種聚類算法相結(jié)合的話題發(fā)現(xiàn)算法，并通過實(shí)驗(yàn)證明此方法能更準(zhǔn)確地發(fā)現(xiàn)一年的網(wǎng)絡(luò)新聞熱點(diǎn)事件。

1　聚類算法研究

聚類是一個(gè)無監(jiān)督的學(xué)習(xí)過程，它可以將數(shù)據(jù)集里相似性較高的對(duì)象劃分為一類，最終使得同組對(duì)象相似，而不同組對(duì)象則相異。聚類算法有劃分聚類、層次聚類以及增量聚類等。劃分聚類首先是要選定初始聚類中心，然后將剩下的數(shù)據(jù)劃分到與之最近的聚類中心中去，使得在同一個(gè)子集中的點(diǎn)盡可能的相似。K-means是劃分聚類算法中比較經(jīng)典的算法。層次聚類算法是將所有的樣本點(diǎn)自底向上合并成一棵樹或者自頂向下分裂成一棵樹的過程，最終達(dá)到預(yù)期的類簇或其他的終止條件，這兩種方法分別稱為凝聚和分裂。而增量聚類的其中一類是利用上一次聚類的結(jié)果，每次將一個(gè)數(shù)據(jù)點(diǎn)劃分到已有簇中，即新增的數(shù)據(jù)點(diǎn)被劃入中心離它最近的簇中并將中心移向新增的數(shù)據(jù)點(diǎn)，也就是說新增的數(shù)據(jù)點(diǎn)不會(huì)影響原有劃分。

網(wǎng)絡(luò)新聞熱點(diǎn)的發(fā)現(xiàn)過程從本質(zhì)上講是一個(gè)聚類的過程，一個(gè)熱點(diǎn)事件通常會(huì)有很多的報(bào)道，并且報(bào)道的時(shí)間可能會(huì)持續(xù)很長。因此，如何選擇高效且能準(zhǔn)確地將大量的新聞報(bào)道中相同的事件聚集在一起，不同的事件區(qū)分出來是本研究的一個(gè)重要任務(wù)。根據(jù)對(duì)多種聚類算法的比較分析，我們將三種聚類算法共同用于本系統(tǒng)的研究，選擇層次聚類對(duì)每天的新聞網(wǎng)頁進(jìn)行聚類得出微類，再選擇K-means聚類算法對(duì)每月的微類進(jìn)行聚類，最后將每個(gè)月的事件通過增量聚類得出一年的熱點(diǎn)新聞事件。

2　網(wǎng)絡(luò)新聞熱點(diǎn)發(fā)現(xiàn)系統(tǒng)

本文的目的主要是對(duì)一年的網(wǎng)絡(luò)新聞報(bào)道進(jìn)行話題發(fā)現(xiàn)的研究，通過聚類得出一年里網(wǎng)絡(luò)上報(bào)道的較受關(guān)注的新聞，最后通過熱點(diǎn)計(jì)算公式得出它們的熱度，進(jìn)而得出一年的熱點(diǎn)事件。因此，如果直接對(duì)一年的新聞報(bào)道數(shù)據(jù)進(jìn)行處理無疑會(huì)增加處理過程的復(fù)雜性，為了提高熱點(diǎn)事件發(fā)現(xiàn)的精確性，降低系統(tǒng)的時(shí)間復(fù)雜度，本文利用分而治之的思想，將一年的新聞報(bào)道分為12個(gè)月分別存儲(chǔ)，每個(gè)月的新聞?dòng)职疵刻斓男侣勥M(jìn)行存儲(chǔ)，先對(duì)每一天的新聞報(bào)道進(jìn)行話題發(fā)現(xiàn)，即進(jìn)行凝聚聚類，找出每天的微類，再將每個(gè)月里的微類進(jìn)行K-means聚類，最后將12個(gè)月里的話題類簇進(jìn)行增量聚類，得出一年的話題新聞，并通過熱點(diǎn)計(jì)算公式篩選和排序，得到一年的熱點(diǎn)事件。系統(tǒng)的整體流程框架如圖1所示。

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

新聞網(wǎng)頁是一種非結(jié)構(gòu)化的數(shù)據(jù)類型，因此我們必須將其轉(zhuǎn)化為結(jié)構(gòu)化的數(shù)據(jù)類型才能被計(jì)算機(jī)所處理。首先將下載的網(wǎng)頁通過分詞軟件進(jìn)行切詞、去除停用詞以及詞性的標(biāo)注，接著我們將采用常用的向量空間模型（VSM）對(duì)新聞文檔進(jìn)行向量表示，這是通過計(jì)算機(jī)編程對(duì)新聞網(wǎng)頁進(jìn)行聚類處理的前提條件。每一個(gè)新聞文本d表示成如下所示的向量形式：

V（d）=

（t1，w1（d）；t2，w2（d）；…ti，wi（d）；tn，wn（d））（1）

其中，ti為新聞文檔的特征項(xiàng)，wi為特征項(xiàng)在文檔d中所占的權(quán)值。

對(duì)于特征項(xiàng)權(quán)值的計(jì)算，本文采用經(jīng)典的TF-IDF算法，計(jì)算公式如下：

對(duì)于每日的網(wǎng)絡(luò)新聞而言，我們無法預(yù)料究竟有多少話題數(shù)量，所以如果用給定聚類數(shù)K值的聚類算法可能會(huì)由于經(jīng)驗(yàn)不足導(dǎo)致聚類結(jié)果偏差較大，因此我們將采用凝聚聚類算法并通過對(duì)閾值的控制來確定算法終止的條件，進(jìn)而得出每日的話題簇。每日話題簇?cái)?shù)量得出之后，通過求出一個(gè)月內(nèi)每日話題簇的平均值，將之作為第二步使用K-means進(jìn)行每月話題聚類的初始聚類數(shù)目，并選擇K個(gè)話題簇中文檔數(shù)較多的類簇作為初始聚類中心，進(jìn)行每月話題簇的聚類發(fā)現(xiàn)。最后用增量聚類的算法得出一年的話題類簇。每日話題聚類和每月話題聚類的具體算法步驟如下所示：

（1）每日話題凝聚聚類算法

輸入：包含n個(gè)數(shù)據(jù)的單日新聞數(shù)據(jù)集D，聚類終止條件閾值M

輸出：K個(gè)聚類后的話題簇

①將每個(gè)對(duì)象作為一類，共n類

②計(jì)算兩兩之間的相似度

③找出相似度最大的兩類并合并，并對(duì)它們重新進(jìn)行表示

④重新計(jì)算新類與其它類之間的相似度

⑤重復(fù)③和④，UNTIL達(dá)到聚類終止條件

⑥輸出K個(gè)話題簇

（2）每月話題凝聚聚類算法

輸入：第一次聚類后一個(gè)月的話題簇?cái)?shù)據(jù)集D1

輸出：K個(gè)聚類后的話題簇

①計(jì)算出一個(gè)月內(nèi)每日的話題數(shù)均值K

②從D1中選取出K個(gè)文檔數(shù)最多的話題簇作為初始的聚類中心

③分別計(jì)算D1中其他樣本點(diǎn)與各中心的距離

④將樣本點(diǎn)劃入與之距離最小的聚類中心簇中

⑤更新中心對(duì)象

⑥重復(fù)③-⑤

⑦UNTIL聚類中心不再發(fā)生變化且所有的類均被劃分完

⑧輸出一個(gè)月的K個(gè)話題簇

一個(gè)事件要成為熱點(diǎn)事件，則還需對(duì)它們進(jìn)行熱度的度量。熱點(diǎn)事件必然也是新聞媒體報(bào)道的比較多，而且受關(guān)注度也較高的事件，根據(jù)這個(gè)思路，本文首先找出能度量熱點(diǎn)事件的特征量，然后總結(jié)出公式對(duì)熱點(diǎn)事件進(jìn)行熱度的計(jì)算。

由于我們要得出的是一年的熱點(diǎn)事件，那么事件在一年內(nèi)的報(bào)道數(shù)量越多或者其報(bào)道的天數(shù)越多，其熱度便會(huì)越高。我們將一年的天數(shù)定義為D，一年中的事件報(bào)道總數(shù)為N，而該事件的報(bào)道總天數(shù)定義為d，報(bào)道篇數(shù)為n。其熱度R的計(jì)算公式如下：

3　實(shí)驗(yàn)與分析

本實(shí)驗(yàn)使用網(wǎng)絡(luò)爬蟲從騰訊、新浪、網(wǎng)易三個(gè)門戶網(wǎng)站上下載了從2014年1月1日到2014年12月31日的國內(nèi)國際社會(huì)新聞網(wǎng)頁，總計(jì)162 510篇。由于網(wǎng)頁數(shù)目龐大，并且具有時(shí)序的特點(diǎn)，故將這一年的新聞按月份存儲(chǔ)在12個(gè)文件夾里，每個(gè)文件夾里再將每天的網(wǎng)頁分別存儲(chǔ)。

根據(jù)系統(tǒng)的整體框架流程圖，我們進(jìn)行實(shí)驗(yàn)的步驟如下：

①對(duì)每天的網(wǎng)頁數(shù)據(jù)用分詞軟件進(jìn)行分詞、去除停用詞和詞性標(biāo)記等的處理；

②對(duì)文檔的特征項(xiàng)進(jìn)行權(quán)值的計(jì)算，并進(jìn)行向量表示；

③對(duì)每天的網(wǎng)頁數(shù)據(jù)進(jìn)行自底向上的凝聚聚類，通過相似度閾值確定聚類終止條件，并選取類簇中文檔數(shù)大于某一閾值的話題類參與下一層的聚類；

④求出每天的平均話題類數(shù)K，并選取K個(gè)文檔數(shù)較多的類，將之作為K-means聚類的初始中心，對(duì)每月的話題類進(jìn)行二次聚類；

⑤將每月的話題類用增量聚類的方法再次聚類得出一年的事件列表；

⑥根據(jù)熱點(diǎn)計(jì)算公式求得熱點(diǎn)事件排序。

為了驗(yàn)證本文的方法對(duì)新聞熱點(diǎn)事件發(fā)現(xiàn)的可行性與準(zhǔn)確性，將本實(shí)驗(yàn)的結(jié)果通過與網(wǎng)上發(fā)布的由數(shù)億網(wǎng)民評(píng)選的十大社會(huì)熱點(diǎn)事件進(jìn)行對(duì)比，對(duì)比結(jié)果如表1所示：

表1　實(shí)驗(yàn)對(duì)比結(jié)果

根據(jù)表1可以得出，本文的實(shí)驗(yàn)結(jié)果中有5個(gè)與網(wǎng)民評(píng)選結(jié)果相同，說明了本實(shí)驗(yàn)聚類算法發(fā)現(xiàn)熱點(diǎn)事件的可行性。之所以選擇用網(wǎng)民評(píng)選的結(jié)果作為對(duì)比，是因?yàn)闊狳c(diǎn)事件必然也是網(wǎng)民比較關(guān)注的事件，而事件報(bào)道時(shí)間較長，篇數(shù)較多也是網(wǎng)民關(guān)注的條件之一，因此即使少數(shù)網(wǎng)民評(píng)選的結(jié)果不足為據(jù)，但數(shù)億的網(wǎng)民便可讓結(jié)果具有一定的說服性。但網(wǎng)民評(píng)選的結(jié)果畢竟還是帶有一定程度的主觀性，所以和本實(shí)驗(yàn)的實(shí)驗(yàn)結(jié)果會(huì)有所偏差，相比而言，本實(shí)驗(yàn)的結(jié)果則更加客觀。

4　結(jié)語

本文提出了將凝聚聚類算法、K-means聚類算法和增量聚類算法相結(jié)合的話題發(fā)現(xiàn)方法，并根據(jù)熱點(diǎn)事件的特征提出了事件的熱度計(jì)算公式，最后通過進(jìn)行實(shí)驗(yàn)和結(jié)果對(duì)比驗(yàn)證了本研究方法的可行性與準(zhǔn)確性。本文的不足之處是熱點(diǎn)計(jì)算公式提的較為簡單，計(jì)算中未加入用戶的評(píng)論數(shù)，因此在以后的研究中可考慮加入這個(gè)因素，以提高熱點(diǎn)事件排名的精確度。

［1］彭楠赟，王厚峰，凌晨添.基于層次聚類的網(wǎng)絡(luò)新聞熱點(diǎn)發(fā)現(xiàn).中國計(jì)算語言學(xué)研究前沿進(jìn)展（2009-2011），2011.

［2］古萬榮，董守斌，何錦潮，曾之肇.基于二次聚類的新聞推薦方法［J］.華南理工大學(xué)學(xué)報(bào)（自然科學(xué)版），2014，7.

［3］劉星星，何婷婷，龔海軍，陳龍.網(wǎng)絡(luò)熱點(diǎn)事件發(fā)現(xiàn)系統(tǒng)的設(shè)計(jì)［J］.中文信息學(xué)報(bào)，2008，11.

Hot Event；Clustering Algorithms；Heat Calculation；Feasibility

Research on Network News Hot Discovery Based on the Clustering

WAN Xiao-xia，ZHAO Jia

（School of Computer and Software Engineering，Xihua University，Chengdu 610039）

1007-1423（2015）26-0036-04

10.3969/j.issn.1007-1423.2015.26.009

萬曉霞（1989-），女，四川瀘州人，碩士研究生，研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)與信息安全系統(tǒng)

2015-07-16

2015-08-15

隨著互聯(lián)網(wǎng)的迅速發(fā)展，網(wǎng)絡(luò)已成為各大媒體發(fā)布新聞和人們獲取信息的主要渠道。而網(wǎng)絡(luò)新聞復(fù)雜多樣，并不是每一條新聞都是人們關(guān)注的熱點(diǎn)。為了快速準(zhǔn)確地獲得用戶關(guān)注的熱點(diǎn)事件，提出將三種聚類算法相結(jié)合的話題發(fā)現(xiàn)算法和熱度計(jì)算公式，并通過實(shí)驗(yàn)驗(yàn)證利用上述方法進(jìn)行熱點(diǎn)發(fā)現(xiàn)的可行性。

熱點(diǎn)事件；聚類算法；熱度計(jì)算；可行性

趙佳（1992-），女，四川成都人，碩士研究生，研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)與信息安全系統(tǒng)

With the rapid development of the Internet，the network has become the main channel for media to release news and the people to obtain information.However，the network news is complex and diverse，not every piece of news is the focus of attention.In order to quickly and accurately obtain hot events that users concerned，presents a topic detection algorithm which combines three kinds of clustering algorithms and a heat calculation formula.And through the experiment，we verify the feasibility of using the above methods for hot found.