萬(wàn)曉霞，趙佳

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

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

萬(wàn)曉霞，趙佳

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

0　引言

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

1　聚類(lèi)算法研究

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

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

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

本文的目的主要是對(duì)一年的網(wǎng)絡(luò)新聞報(bào)道進(jìn)行話題發(fā)現(xiàn)的研究，通過(guò)聚類(lèi)得出一年里網(wǎng)絡(luò)上報(bào)道的較受關(guān)注的新聞，最后通過(guò)熱點(diǎn)計(jì)算公式得出它們的熱度，進(jìn)而得出一年的熱點(diǎn)事件。因此，如果直接對(duì)一年的新聞報(bào)道數(shù)據(jù)進(jìn)行處理無(wú)疑會(huì)增加處理過(guò)程的復(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)行凝聚聚類(lèi)，找出每天的微類(lèi)，再將每個(gè)月里的微類(lèi)進(jìn)行K-means聚類(lèi)，最后將12個(gè)月里的話題類(lèi)簇進(jìn)行增量聚類(lèi)，得出一年的話題新聞，并通過(guò)熱點(diǎn)計(jì)算公式篩選和排序，得到一年的熱點(diǎn)事件。系統(tǒng)的整體流程框架如圖1所示。

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

新聞網(wǎng)頁(yè)是一種非結(jié)構(gòu)化的數(shù)據(jù)類(lèi)型，因此我們必須將其轉(zhuǎn)化為結(jié)構(gòu)化的數(shù)據(jù)類(lèi)型才能被計(jì)算機(jī)所處理。首先將下載的網(wǎng)頁(yè)通過(guò)分詞軟件進(jìn)行切詞、去除停用詞以及詞性的標(biāo)注，接著我們將采用常用的向量空間模型（VSM）對(duì)新聞文檔進(jìn)行向量表示，這是通過(guò)計(jì)算機(jī)編程對(duì)新聞網(wǎng)頁(yè)進(jìn)行聚類(lèi)處理的前提條件。每一個(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ò)新聞而言，我們無(wú)法預(yù)料究竟有多少話題數(shù)量，所以如果用給定聚類(lèi)數(shù)K值的聚類(lèi)算法可能會(huì)由于經(jīng)驗(yàn)不足導(dǎo)致聚類(lèi)結(jié)果偏差較大，因此我們將采用凝聚聚類(lèi)算法并通過(guò)對(duì)閾值的控制來(lái)確定算法終止的條件，進(jìn)而得出每日的話題簇。每日話題簇?cái)?shù)量得出之后，通過(guò)求出一個(gè)月內(nèi)每日話題簇的平均值，將之作為第二步使用K-means進(jìn)行每月話題聚類(lèi)的初始聚類(lèi)數(shù)目，并選擇K個(gè)話題簇中文檔數(shù)較多的類(lèi)簇作為初始聚類(lèi)中心，進(jìn)行每月話題簇的聚類(lèi)發(fā)現(xiàn)。最后用增量聚類(lèi)的算法得出一年的話題類(lèi)簇。每日話題聚類(lèi)和每月話題聚類(lèi)的具體算法步驟如下所示：

（1）每日話題凝聚聚類(lèi)算法

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

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

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

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

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

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

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

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

（2）每月話題凝聚聚類(lèi)算法

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

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

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

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

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

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

⑤更新中心對(duì)象

⑥重復(fù)③-⑤

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

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

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

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

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

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

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

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

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

為了驗(yàn)證本文的方法對(duì)新聞熱點(diǎn)事件發(fā)現(xiàn)的可行性與準(zhǔn)確性，將本實(shí)驗(yàn)的結(jié)果通過(guò)與網(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é)果相同，說(shuō)明了本實(shí)驗(yàn)聚類(lèi)算法發(fā)現(xiàn)熱點(diǎn)事件的可行性。之所以選擇用網(wǎng)民評(píng)選的結(jié)果作為對(duì)比，是因?yàn)闊狳c(diǎn)事件必然也是網(wǎng)民比較關(guān)注的事件，而事件報(bào)道時(shí)間較長(zhǎng)，篇數(shù)較多也是網(wǎng)民關(guān)注的條件之一，因此即使少數(shù)網(wǎng)民評(píng)選的結(jié)果不足為據(jù)，但數(shù)億的網(wǎng)民便可讓結(jié)果具有一定的說(shuō)服性。但網(wǎng)民評(píng)選的結(jié)果畢竟還是帶有一定程度的主觀性，所以和本實(shí)驗(yàn)的實(shí)驗(yàn)結(jié)果會(huì)有所偏差，相比而言，本實(shí)驗(yàn)的結(jié)果則更加客觀。

4　結(jié)語(yǔ)

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

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

［2］古萬(wàn)榮，董守斌，何錦潮，曾之肇.基于二次聚類(lèi)的新聞推薦方法［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

萬(wàn)曉霞（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)事件，提出將三種聚類(lèi)算法相結(jié)合的話題發(fā)現(xiàn)算法和熱度計(jì)算公式，并通過(guò)實(shí)驗(yàn)驗(yàn)證利用上述方法進(jìn)行熱點(diǎn)發(fā)現(xiàn)的可行性。

熱點(diǎn)事件；聚類(lèi)算法；熱度計(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.