萬曉霞，趙佳

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

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

萬曉霞，趙佳

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

0　引言

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

1　聚類算法研究

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

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

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

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

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

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

V（d）=

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

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

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

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

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

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

輸出：K個聚類后的話題簇

①將每個對象作為一類，共n類

②計算兩兩之間的相似度

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

④重新計算新類與其它類之間的相似度

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

⑥輸出K個話題簇

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

輸入：第一次聚類后一個月的話題簇數(shù)據(jù)集D1

輸出：K個聚類后的話題簇

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

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

③分別計算D1中其他樣本點與各中心的距離

④將樣本點劃入與之距離最小的聚類中心簇中

⑤更新中心對象

⑥重復(fù)③-⑤

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

⑧輸出一個月的K個話題簇

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

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

3　實驗與分析

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

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

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

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

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

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

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

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

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

表1　實驗對比結(jié)果

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

4　結(jié)語

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

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

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

［3］劉星星，何婷婷，龔海軍，陳龍.網(wǎng)絡(luò)熱點事件發(fā)現(xiàn)系統(tǒng)的設(shè)計［J］.中文信息學(xué)報，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-），女，四川瀘州人，碩士研究生，研究方向為計算機網(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)注的熱點。為了快速準(zhǔn)確地獲得用戶關(guān)注的熱點事件，提出將三種聚類算法相結(jié)合的話題發(fā)現(xiàn)算法和熱度計算公式，并通過實驗驗證利用上述方法進(jìn)行熱點發(fā)現(xiàn)的可行性。

熱點事件；聚類算法；熱度計算；可行性

趙佳（1992-），女，四川成都人，碩士研究生，研究方向為計算機網(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.