陳 友,程學(xué)旗,楊 森

(1.中國(guó)科學(xué)院計(jì)算技術(shù)研究所,北京100190;2.中國(guó)科學(xué)院研究生院,北京100049)

1 引言

網(wǎng)絡(luò)論壇因其含有的大量有用信息已經(jīng)成為Web2.0的典型代表。在網(wǎng)絡(luò)論壇上用戶不僅是信息的享用者,同時(shí)還是信息的創(chuàng)建者。這就使得網(wǎng)絡(luò)論壇上每天都有大量的信息,并且信息更新速度快。國(guó)內(nèi)網(wǎng)絡(luò)論壇的典型代表“水木社區(qū)”[1]在同一時(shí)刻有接近一萬人登錄,每天有十萬的新帖被寫入。大量的新信息使得論壇對(duì)時(shí)事反映靈敏,特別是一些突發(fā)的事件。一般用戶進(jìn)入論壇基本上都是以主帖或者回帖作為瀏覽的對(duì)象,最普遍的形式就是以同主題的方式瀏覽論壇內(nèi)容。如果他想了解一個(gè)事件發(fā)生的全過程以及與事件相關(guān)的一些描述,他可能需要瀏覽大量的主題才能夠找到需要的信息,并且找出的信息可能還不完整。這樣瀏覽的后果是花費(fèi)大量的時(shí)間,且不一定找到滿意的結(jié)果。如何從論壇大量相關(guān)的主題中自動(dòng)化檢測(cè)突發(fā)話題顯得尤為重要。

論壇的開放性使得每一個(gè)注冊(cè)用戶都可以發(fā)表自己的想法,這就使得論壇上發(fā)表的帖子質(zhì)量參差不齊,并且很多帖子都是口語化表示。論壇內(nèi)容的隨意性,用語不規(guī)范,口語化等這些特征使得針對(duì)網(wǎng)絡(luò)論壇的挖掘變得相當(dāng)困難。傳統(tǒng)的話題檢測(cè)與跟蹤模型(Topic Detection and T racking,TDT)[2-3]雖然能夠很好的解決話題發(fā)現(xiàn)問題,但是在論壇這種噪音環(huán)境下處理效果不好,因?yàn)門DT文獻(xiàn)[4-7]中提出的方法處理對(duì)象是新聞?wù)Z料,相比起論壇內(nèi)容,新聞?wù)Z料描述更準(zhǔn)確、嚴(yán)謹(jǐn)、規(guī)范。內(nèi)容噪音一直是論壇挖掘的一個(gè)障礙,針對(duì)論壇的話題發(fā)現(xiàn)也無法回避這個(gè)問題。

本文提出一種基于噪音過濾的話題發(fā)現(xiàn)模型。模型首先利用詞以及用戶參與度的突發(fā)特性進(jìn)行噪音過濾,提取突發(fā)詞以及核心用戶。我們認(rèn)為那些非突發(fā)詞以及參與度低的用戶在突發(fā)話題發(fā)現(xiàn)過程中起到的作用很小,把這些詞作為噪音過濾掉。在發(fā)現(xiàn)后的突發(fā)詞以及核心用戶上我們應(yīng)用話題發(fā)現(xiàn)算法。我們的算法不僅可以發(fā)現(xiàn)一段時(shí)間內(nèi)的突發(fā)話題,同時(shí)還可以發(fā)現(xiàn)與這些話題相關(guān)聯(lián)的用戶社區(qū)。本文的主要貢獻(xiàn)有三方面：

我們利用時(shí)間序列對(duì)每一個(gè)詞以及用戶參與度進(jìn)行描述,然后在時(shí)間序列上利用頻譜劃分技術(shù)進(jìn)行突發(fā)性計(jì)算與檢測(cè)。我們的檢測(cè)方法能夠及早的發(fā)現(xiàn)突發(fā)詞以及核心用戶。

詞的突發(fā)性被用作噪音過濾。網(wǎng)絡(luò)論壇下的突發(fā)話題發(fā)現(xiàn)面臨的關(guān)鍵問題是噪音,本文很好的利用詞的突發(fā)性過濾掉噪音內(nèi)容。那些非突發(fā)詞以及活躍度低的用戶將被視為過濾的對(duì)象。

我們從時(shí)間序列的相似性以及文本內(nèi)容的重疊性兩個(gè)角度設(shè)計(jì)了一個(gè)無監(jiān)督學(xué)習(xí)的突發(fā)話題發(fā)現(xiàn)算法,該算法不僅可以發(fā)現(xiàn)突發(fā)話題,而且可以發(fā)現(xiàn)與這些話題相關(guān)聯(lián)的用戶社區(qū)。并且算法的高效性在實(shí)際論壇中已經(jīng)得到了很好的驗(yàn)證。

2 相關(guān)工作

話題檢測(cè)與跟蹤研究較好的解決了話題發(fā)現(xiàn)這個(gè)子任務(wù)。TDT中大部分研究工作集中在新聞?wù)Z料上,相比起論壇內(nèi)容,新聞內(nèi)容更準(zhǔn)確、嚴(yán)謹(jǐn)、規(guī)范。它們基本上針對(duì)新聞?wù)Z料進(jìn)行聚類或者分類以發(fā)現(xiàn)新的句子來構(gòu)成新的話題[8]。論壇與新聞?dòng)泻艽蟮牟町?論壇對(duì)時(shí)事反映靈敏,參與用戶數(shù)量龐大,用語不規(guī)范。這些差異特征使得TDT在解決論壇中的話題發(fā)現(xiàn)任務(wù)時(shí)力不從心,例如用語的不規(guī)范性,使得聚類效果很差。如何利用論壇的時(shí)間敏感特性來協(xié)助完成話題發(fā)現(xiàn)的任務(wù)是本文要解決的主要問題。針對(duì)論壇對(duì)突發(fā)事件以及與此相關(guān)的一些事件反映靈敏這一特性,我們首先提出在網(wǎng)絡(luò)論壇下發(fā)現(xiàn)突發(fā)話題的新任務(wù)。這項(xiàng)任務(wù)區(qū)別于話題發(fā)現(xiàn)任務(wù),它是在網(wǎng)絡(luò)論壇這種特殊的環(huán)境下提出的一項(xiàng)新任務(wù),既符合網(wǎng)絡(luò)論壇及早發(fā)現(xiàn)突發(fā)事件的功用也符合網(wǎng)絡(luò)論壇在時(shí)間維上的靈敏特性。

在解決網(wǎng)絡(luò)論壇上的話題發(fā)現(xiàn)任務(wù)方面有兩類典型的工作。首先,從用戶角度進(jìn)行相關(guān)研究的工作包括：文獻(xiàn)[9]利用用戶參與模型從論壇上發(fā)現(xiàn)話題。它們通過用戶之間的相似度計(jì)算來對(duì)用戶進(jìn)行聚團(tuán),然后從用戶出發(fā)發(fā)現(xiàn)與這些用戶團(tuán)相關(guān)聯(lián)的話題。文獻(xiàn)[10]在用戶參與上建立馬氏邏輯網(wǎng)絡(luò)模型來發(fā)現(xiàn)話題。這些工作的出發(fā)點(diǎn)都認(rèn)為在論壇中,用戶相比起內(nèi)容噪音更小,因此它們都把用戶作為話題發(fā)現(xiàn)依賴的特征。但是這些方法發(fā)現(xiàn)的話題效果很差,描述性不好。其次,從文本內(nèi)容和用戶參與兩個(gè)角度進(jìn)行相關(guān)研究的工作包括：文獻(xiàn)[11]利用TF-IDF以及UF-ITUF模型分別對(duì)詞和用戶參與度進(jìn)行建模。由于大量噪音詞的存在使得該模型的效果不好。并且文獻(xiàn)[11]中只考慮thread中前17個(gè)帖子,這種做法是缺乏根據(jù)的。據(jù)我們研究,很多重要的信息出現(xiàn)在thread的前17個(gè)帖子之后。我們對(duì)每一個(gè)詞和用戶形成相應(yīng)的時(shí)間序列,考察thread中的全部帖子,而不是前17個(gè)帖子,并且我們考察的重點(diǎn)是詞以及用戶在時(shí)間上的變化規(guī)律。我們通過對(duì)論壇時(shí)間特性的分析,從中挖掘出時(shí)間序列,然后在時(shí)間序列上進(jìn)行相應(yīng)的處理來幫助解決我們提出的新任務(wù)。

近年來,很多研究者在進(jìn)行話題發(fā)現(xiàn)工作的同時(shí),把目光轉(zhuǎn)向發(fā)現(xiàn)Web2.0環(huán)境下的網(wǎng)絡(luò)社區(qū)、核心用戶等研究上來[12-13]。如文獻(xiàn)[12]利用突發(fā)特征從Web log圖中發(fā)現(xiàn)突發(fā)社區(qū)。本文采取一種頻譜劃分的方法對(duì)時(shí)間序列進(jìn)行分析來發(fā)現(xiàn)突發(fā)特征,這種方法能夠及早的發(fā)現(xiàn)突發(fā)特征;并且在頻譜劃分后的時(shí)間序列上我們可以進(jìn)行突發(fā)話題發(fā)現(xiàn)以及用戶社區(qū)發(fā)現(xiàn)相關(guān)的工作。

3 時(shí)間序列分析

首先定義網(wǎng)絡(luò)論壇中幾個(gè)重要的概念：

主題(thread)：thread由論題(title)、入口(entry)、帖子(post)組成,并且 title、entry是唯一的。主題包含有一系列的post。每一個(gè)post唯一屬于一個(gè)thread。

論題(title)：一個(gè) thread中的標(biāo)題,是thread中第一個(gè)作者提出來的,并且在該thread中是唯一的,它代表著這個(gè)thread即將論述的主要內(nèi)容,以后的post都是圍繞這個(gè) title展開論述。一個(gè)thread內(nèi)部的所有帖子共享同一個(gè)論題。

入口(entry)：它是關(guān)于thread中 title的詳細(xì)論述,是由創(chuàng)建title的作者對(duì) title的一個(gè)詳細(xì)解說。每一個(gè)thread中entry也是唯一的。實(shí)際上它是thread中的第一個(gè)post。

帖子(post)：一個(gè)post是指作者就某個(gè)論題進(jìn)行論述的文章。它分為兩類：主貼與回帖。一個(gè)post具有四個(gè)特性：發(fā)表時(shí)間、作者、論題以及論述內(nèi)容。

論壇是由很多的板塊構(gòu)成,如在水木社區(qū)中有板塊“水木特快”、“個(gè)人 show”、“交通信息”等。在每一個(gè)板塊中,文本的組織形式是thread。每一個(gè)板塊含有很多的thread。當(dāng)發(fā)生突發(fā)事件,我們就會(huì)在“水木特快”上找到與該突發(fā)事件相關(guān)的的討論,這些討論可以是關(guān)于該突發(fā)事件發(fā)生的時(shí)間、地點(diǎn)、原因以及相關(guān)的背景知識(shí)。而這些內(nèi)容的組織形式是很多的thread,它們的量很大,很難在短時(shí)間內(nèi)對(duì)它們進(jìn)行人工整理與歸納,此時(shí)在這些thread中自動(dòng)發(fā)現(xiàn)大家討論的話題顯得相當(dāng)重要。

3.1 時(shí)間序列

我們針對(duì)每一個(gè)詞與用戶,應(yīng)用一定的規(guī)則形成相應(yīng)的時(shí)間序列。首先定義幾個(gè)重要的概念如下：

T：考察的post流時(shí)間跨度;F：特征空間集合;

TF f(t)：特征 f在時(shí)間段t-1到 t出現(xiàn)在 post流中的次數(shù);y f(t)=TF f(t);

yf=[yf(1),yf(2),…,yf(i),…yf(T)],特征f在T時(shí)間段內(nèi)的序列;

在網(wǎng)絡(luò)論壇中,詞出現(xiàn)在 thread中不同的位置,其重要性是不一樣的。例如如果一個(gè)詞出現(xiàn)在標(biāo)題中或是entry中,其重要性要比它們出現(xiàn)在回帖中更高。為此我們根據(jù)詞在thread中不同的位置,定義一個(gè)位置權(quán)重策略如下：

該位置權(quán)重策略表示如果一個(gè)詞在時(shí)間段t-1到t出現(xiàn)在title中的次數(shù)是 f_title,出現(xiàn)在entry中次數(shù)是 f_entry,出現(xiàn)在其他post中的次數(shù)是f_other,則 y f(t)=ωt×f_title+ωe×f_entry+ωo×f_other。ωt,ωe,ωo是根據(jù)經(jīng)驗(yàn)來確定的,定義它們的目的就是為了突出那些對(duì)話題發(fā)現(xiàn)有幫助的詞,因?yàn)闃?biāo)題中的詞以及entry中的詞在一個(gè)thread中重要性很高,突出它們符合論壇中th read的固有特性。ωt,ωe,ωo三個(gè)參數(shù)根據(jù)經(jīng)驗(yàn)確定,在我們實(shí)驗(yàn)中確定為5,2,1。

相比起傳統(tǒng)的新聞?wù)Z料,大量用戶參與其中是網(wǎng)絡(luò)論壇的一個(gè)重要特征。在國(guó)家輿情控制方面,我們不僅希望發(fā)現(xiàn)突發(fā)話題,同時(shí)更想發(fā)現(xiàn)這些突發(fā)話題的背后都是哪些用戶在參與。因此發(fā)現(xiàn)一些活躍的核心用戶以及由他們構(gòu)成的網(wǎng)絡(luò)社區(qū)也顯得尤為重要。為了突出那些發(fā)起者,我們?cè)O(shè)計(jì)了一個(gè)角色權(quán)重策略,其定義如下：

該策略表示如果用戶是發(fā)起者,即是title與entry的作者,其權(quán)重為 ωs,如果為跟隨者其權(quán)重為ωr。例如如果一個(gè)用戶在時(shí)間段t-1到t內(nèi)其發(fā)表了3篇標(biāo)題(title)和2篇帖子,則其在該時(shí)間段內(nèi)的yf(t)=ωs×3+ωr×2。ωs和 ωr也是根據(jù)經(jīng)驗(yàn)來確定的,在實(shí)驗(yàn)中它們被賦值為5和1。

3.2 頻譜劃分

當(dāng)前有很多方法[14-15]可以用來判斷一個(gè)時(shí)間序列中是否含有突發(fā)(burst)。在這些方法中最典型的就是K leinberg提出的自動(dòng)機(jī)模型。這個(gè)模型在很多應(yīng)用中[16-17]得到了驗(yàn)證。這些典型的burst檢測(cè)方法效果很好,但是它們的復(fù)雜度高,實(shí)現(xiàn)困難,特別是在對(duì)實(shí)時(shí)要求很高的系統(tǒng)中很難應(yīng)用。突發(fā)話題的發(fā)現(xiàn)對(duì)實(shí)時(shí)性要求很高,這就使得這些方法很難在突發(fā)話題發(fā)現(xiàn)上應(yīng)用。為了快速及早的檢測(cè)burst,我們采取頻譜劃分的技術(shù)對(duì)時(shí)間序列進(jìn)行分析。

對(duì)時(shí)間序列進(jìn)行分段劃分的方法很多,最典型的就是等時(shí)間窗口劃分。在這些方法中最困難的就是時(shí)間窗口大小的確定,如果選擇不合適的時(shí)間窗口,burst很可能被分解成很多的非burst,這樣就會(huì)漏報(bào)很多的burst序列。我們采取一種新的方法來分割頻譜。這種分割技術(shù)帶來的 burst檢測(cè)效率高,性能好,易實(shí)現(xiàn)。能夠滿足實(shí)時(shí)性的需求。

給定一個(gè)特征的時(shí)間序列y f=[y f(1),yf(2),…,y f(i),…yf(T)],我們把它分成k塊X1,X2,…,Xi,…,Xk。每一塊內(nèi)部的每一個(gè)時(shí)間段的頻率都大于0。每一塊的值Xi為該塊內(nèi)所有時(shí)間段內(nèi)頻率值之和。例如時(shí)間序列(2 1 2 3 0 2 6 5 4 7 3),我們把它分成兩塊(2 1 2 3)和(2 6 5 4 7 3)。分塊后兩塊的值X1,X2為X 1=8=2+1+2+3;X2=27=2+6+5+4+7+3。該例子的轉(zhuǎn)換過程如圖1所示。

圖1 時(shí)間序列以及相應(yīng)的頻譜劃分片段

圖1中可以看出,頻譜劃分片段相比原始時(shí)間序列,其在早期就能夠發(fā)現(xiàn)burst,并且它把burst的值擴(kuò)大化,更強(qiáng)調(diào)頻率的變化。這些都是感性上的認(rèn)識(shí),為了快速的進(jìn)行burst檢測(cè),需要對(duì)頻譜劃分片段進(jìn)行量化。首先定義幾個(gè)基本概念：

Sumseg[i]=Xi,i=1,2,…,k,表示第i塊的頻率值X i;

用一個(gè)二維向量Vf=[(s1,d1),(s2,d2),…,(si,di),…,(sk,dk)]來表示時(shí)間序列劃分后的頻譜片段。其中si=Sumseg[i],di=Devseg[i]。利用這種表示方法,圖 1中的實(shí)例可以表示為：[(8,-0.72),(27,0.72)]。在二維向量空間中可以看出si表示第i塊頻率的絕對(duì)值,而di則表示第i塊頻率的相對(duì)值。當(dāng)序列中含有burst時(shí),其塊與塊之間的絕對(duì)值以及相對(duì)值差距大。

4 話題發(fā)現(xiàn)模型

話題發(fā)現(xiàn)的過程主要有原數(shù)據(jù)預(yù)處理,時(shí)間序列形成,頻譜劃分,突發(fā)詞與核心用戶檢測(cè),突發(fā)話題與用戶社區(qū)發(fā)現(xiàn)五個(gè)階段。原數(shù)據(jù)預(yù)處理是從post流中發(fā)現(xiàn)每一個(gè)post的五個(gè)基本特性：post所屬的標(biāo)題、post作者、發(fā)表時(shí)間、內(nèi)容以及post標(biāo)志號(hào)。post內(nèi)容已經(jīng)被分成詞流的形式,并且一些諸如“的”“re”等停用詞被移除。原數(shù)據(jù)預(yù)處理之后,針對(duì)每一個(gè)詞與用戶按照時(shí)間序列的形成規(guī)則形成對(duì)應(yīng)的時(shí)間序列。在時(shí)間序列的基礎(chǔ)上采用頻譜劃分技術(shù),然后利用二維向量Vf來表示時(shí)間序列。在向量空間Vf上發(fā)現(xiàn)突發(fā)詞和核心用戶,然后在這些突發(fā)詞以及核心用戶上應(yīng)用話題發(fā)現(xiàn)算法,發(fā)現(xiàn)突發(fā)話題以及與這些話題相關(guān)聯(lián)的用戶社區(qū)。

4.1 突發(fā)特征提取

通過觀察每一個(gè)詞的二維向量空間V f,我們發(fā)現(xiàn)有兩種典型的詞：普通詞與突發(fā)詞。普通詞在向量空間上的表現(xiàn)形式為其偏差均為0,這種詞大部分只有一個(gè)元素(s1,d1),在物理上表明這些詞出現(xiàn)頻繁,幾乎時(shí)時(shí)出現(xiàn);而突發(fā)詞在向量空間上的表現(xiàn)形式為其向量中某些偏差與Sumseg[i]均很大,物理上表明該詞在極短的時(shí)間內(nèi)存在爆發(fā)性。普通詞中那些Sumseg[i]值很大的詞對(duì)突發(fā)話題的形成也是有作用的。我們從詞集合中尋找這兩類詞,把它們作為突發(fā)特征。我們根據(jù)經(jīng)驗(yàn)在普通詞中選擇那些Sumseg[i]值大于2 000的詞作為突發(fā)特征,因?yàn)镾umseg[i]值小于2 000的詞沒有突發(fā)性。當(dāng)然不同的數(shù)據(jù)集閾值是不同的。針對(duì)突發(fā)詞的選擇,max(Sumseg[i])>110,max(Devseg[i])>0.3作為閾值來選擇。其中m ax(Sumseg[i])表示k個(gè)片段中的最大sumseg值,m ax(Devseg[i])表示k個(gè)片段中最大偏差值。

對(duì)閾值選擇后的突發(fā)特征我們利用下面的公式對(duì)其進(jìn)行排序：

α在實(shí)驗(yàn)中被設(shè)置成0.16。

在核心用戶的選擇上,m ax(Sumseg[i])>20,m ax(Devseg[i])>0.35被作為閾值進(jìn)行選擇。

4.2 相似度測(cè)量

突發(fā)詞被發(fā)現(xiàn)之后,如何根據(jù)這些突發(fā)詞來發(fā)現(xiàn)突發(fā)話題是本小節(jié)研究重點(diǎn)。我們從詞的相似性與post的重疊性兩個(gè)方面來衡量詞與詞之間的相似度。兩個(gè)詞與詞之間的相似性可以計(jì)算如下：

其中,D fj=[d1,…,di,…,dk]是詞序列的偏差向量。通過偏差之間的相似性度量,可以發(fā)現(xiàn)相關(guān)的詞集合。mean(D fj)是D fj的平均值,表示X與Y的內(nèi)積,‖X‖是X的1范式。

詞的集合R的相似度計(jì)算為：

即集合R的相似性是由其內(nèi)部相似性最小的兩個(gè)詞決定。

兩個(gè)詞所屬的post的重疊度也是衡量詞相似性的一個(gè)重要指標(biāo)。假設(shè)Mi是含有詞 f i的所有post集合,則既含有詞 fi同時(shí)也含有詞 f j的所有post集合為 Mi∩Mj。通常 Mi∩Mj的數(shù)目|Mi∩M j|越大,詞 fi和f j越相關(guān)。我們定義兩個(gè)詞 fi與 f j的post重疊度如下：

集合R的post重疊度定義如下：

同L(R)一樣,p(R)也是由集合中最小post重疊度的兩個(gè)詞決定。

對(duì)于用戶相似度計(jì)算也是從用戶時(shí)間序列的相似性與用戶所屬thread的重疊度兩個(gè)方面來度量。用戶時(shí)間序列之間的相似性同詞時(shí)間序列相似性計(jì)算一樣。用戶ui與uj所屬thread的重疊度計(jì)算如下：

其中H i是含有用戶ui的所有thread的集合,Hi∩Hj是既含有用戶ui也含有用戶uj的所有threads集合。用戶集合U的重疊性度量為：

對(duì)詞集合以及用戶集合的相似度進(jìn)行度量之后,我們可以設(shè)計(jì)算法來挖掘突發(fā)話題與用戶社區(qū)。

4.3 無監(jiān)督學(xué)習(xí)的突發(fā)話題發(fā)現(xiàn)算法

突發(fā)特征提取以后,對(duì)于任意給定的突發(fā)特征fi∈F′,尋找一組和 fi相關(guān)的特征子集來表示突發(fā)話題。其中F′是突發(fā)特征集合。從突發(fā)特征集合F′中尋找特征子集Ri?F′來表示突發(fā)話題是發(fā)現(xiàn)算法需要解決的問題。發(fā)現(xiàn)算法的目的是在找到Ri時(shí),所花費(fèi)的代價(jià)最小。代價(jià)函數(shù)表述如下：

假設(shè) δL是 L(R)最小值 ,δp是p(R)最小值,則在話題發(fā)現(xiàn)過程中發(fā)現(xiàn)一組相關(guān)特征的所需要的代價(jià)C(Ri)不能大于C max(R)=1/(δL×δp)。在突發(fā)特征集合上F′上同一突發(fā)特征可以在不同的突發(fā)話題中。應(yīng)用該算法可以發(fā)現(xiàn)與這些突發(fā)話題相關(guān)聯(lián)的用戶社區(qū)。

無監(jiān)督學(xué)習(xí)的突發(fā)話題發(fā)現(xiàn)算法如下：

5 實(shí)驗(yàn)

5.1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)數(shù)據(jù)采用“水木社區(qū)”的“水木特快”十天的數(shù)據(jù)?！八咎乜臁笔恰八旧鐓^(qū)”里面最具典型性的一個(gè)板塊,對(duì)突發(fā)事件的反映靈敏,并且參與的用戶數(shù)量大。我們實(shí)驗(yàn)的數(shù)據(jù)是“水木特快”從2008年3月1日到2008年3月10日的數(shù)據(jù)。數(shù)據(jù)的詳細(xì)描述在表 1中,并且這個(gè)數(shù)據(jù)集已經(jīng)被人工標(biāo)注[11]。

表1 實(shí)驗(yàn)數(shù)據(jù)集描述

我們實(shí)驗(yàn)的數(shù)據(jù)集有7 263個(gè) thread,這些thread總計(jì)包含67 967個(gè)post。這相當(dāng)于每天平均有6 796.7個(gè)post和 726.3個(gè)thread被加入到板塊中。在數(shù)據(jù)集中,文獻(xiàn)[16]的研究者們標(biāo)注了2 980個(gè)話題,我們?cè)诖嘶A(chǔ)上標(biāo)注了246個(gè)突發(fā)話題.在2 980個(gè)話題中,幾乎有超過2 000個(gè)話題僅僅含有單個(gè) thread。突發(fā)話題往往含有多個(gè)thread,在標(biāo)注的246個(gè)突發(fā)話題中有接近62%的post被包含。這說明在網(wǎng)絡(luò)論壇中突發(fā)話題需要進(jìn)行歸納與總結(jié),這樣用戶就能夠及時(shí)全面的了解發(fā)生的突發(fā)事件以及與這些事件相關(guān)的一些事件,從而幫助用戶節(jié)約大量的瀏覽時(shí)間,同時(shí)提高他們的瀏覽質(zhì)量。

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

我們利用兩個(gè)閾值Sumseg>110,Devseg>0.3來發(fā)現(xiàn)突發(fā)詞,發(fā)現(xiàn)的結(jié)果見圖2,其中在兩條虛線構(gòu)成的四個(gè)區(qū)間中,右上角的區(qū)間就是我們需要的突發(fā)詞。通過閾值選擇的突發(fā)詞數(shù)目有2 591。這就表明通過突發(fā)詞發(fā)現(xiàn)之后,原本需要處理的45 961個(gè)詞,現(xiàn)在只需要處理2 591個(gè)詞。這種對(duì)噪音詞的過濾方法不僅減小了模型的復(fù)雜度,同時(shí)也提高了發(fā)現(xiàn)算法的準(zhǔn)確率。

在發(fā)現(xiàn)的2 591個(gè)突發(fā)詞上,應(yīng)用score(fi)對(duì)它們進(jìn)行排序。

相比起文獻(xiàn)[16]中的TF-IDF,UF-ITUF模型在所有詞上的話題發(fā)現(xiàn),我們的算法在排序好的突發(fā)詞上性能更好,效率更高。

圖2 所有偏差不小于0的詞在Sumseg-Devseg上的分布

圖3 所有偏差不小于0的用戶在Sumseg-Devseg上的分布

在核心用戶發(fā)現(xiàn)上,我們利用閾值Sumseg>20和Devseg>0.35。首先我們給出了所有偏差不小于0的用戶在Sumseg-Devseg上的分布圖,然后把兩條虛線構(gòu)成的右上角區(qū)間作為核心用戶區(qū)間。詳細(xì)的分布圖見圖3。在5 394個(gè)用戶中我們選擇了390個(gè)用戶作為核心用戶。圖3從某種程度上說明更多的用戶只是在跟從主要用戶,因此對(duì)核心用戶的考察意義非凡。我們同樣利用score(fi)函數(shù)對(duì)用戶進(jìn)行排序,對(duì)這些排名靠前的用戶進(jìn)行觀察,他們中的大部分是突發(fā)話題的發(fā)起者,在突發(fā)話題發(fā)展過程中起到主導(dǎo)作用,并且有很多的追隨者?？梢姾诵挠脩羰峭话l(fā)話題發(fā)現(xiàn)過程中一個(gè)重要的特征。在突發(fā)詞發(fā)現(xiàn)之后,為了驗(yàn)證話題發(fā)現(xiàn)算法的性能,我們根據(jù)不同的閾值Cmax(R)進(jìn)行了7組實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如圖4所示。

從圖4中可以看出,當(dāng) C max(R)在2.4時(shí),其準(zhǔn)確率、召回率以及F1值表現(xiàn)都不錯(cuò),它們的值分別為0.86,0.82和0.84。根據(jù)實(shí)驗(yàn)結(jié)果可以得出兩個(gè)結(jié)論：

圖4 話題發(fā)現(xiàn)算法在不同的C max(R)值上的準(zhǔn)確率、召回率以及F1

(1)我們的模型能夠發(fā)現(xiàn)80%以上的突發(fā)話題。

(2)突發(fā)詞是突發(fā)話題發(fā)現(xiàn)的一個(gè)重要特征。不用從整個(gè)詞空間,而只需要從少量的突發(fā)詞中我們的模型就能以很高的F1值來發(fā)現(xiàn)話題。這樣不僅節(jié)省了模型開銷,同時(shí)也提高了話題發(fā)現(xiàn)的性能。

網(wǎng)絡(luò)論壇的突發(fā)話題發(fā)現(xiàn)是一項(xiàng)新任務(wù),前人的相關(guān)工作較少,最相關(guān)的就是網(wǎng)絡(luò)論壇的話題發(fā)現(xiàn)?；诰W(wǎng)絡(luò)論壇的話題發(fā)現(xiàn)最具代表性的模型就是TF-IDF和UF-ITUF模型,文獻(xiàn)[16]中的研究者們把兩個(gè)模型結(jié)合起來作為話題發(fā)現(xiàn)的模型。這種綜合模型不僅考察了內(nèi)容特征,而且對(duì)用戶參與度也進(jìn)行了考察,具有一定的效果。本文把這種綜合模型用來進(jìn)行突發(fā)話題發(fā)現(xiàn),同時(shí)與我們的模型進(jìn)行了對(duì)比,對(duì)比結(jié)果如表2所示。

表2 我們的模型與TF-IDF-UF-ITUF模型在準(zhǔn)確率、召回率以及F1值上的對(duì)比

從表2可以看出,我們提出的話題發(fā)現(xiàn)模型擁有更好的性能,當(dāng)C max(R)=2.4時(shí),F1值為0.84,相對(duì)于TF-IDF-UF-ITUF模型有將近 30%的提高。這是因?yàn)?TF-IDF-UF-ITUF模型是在噪音環(huán)境中操作的,它針對(duì)所有的詞以及用戶,并且在內(nèi)容方面只考慮thread中的前17個(gè)post。這在一定程度上會(huì)丟失大量的信息。我們的模型通過burst特性過濾掉噪音詞,并且 burst詞的提取是在整個(gè)post空間,而不僅僅是考慮thread的前17個(gè)post。

6 結(jié)論

本文提出一種基于噪音過濾的話題發(fā)現(xiàn)模型,用來發(fā)現(xiàn)網(wǎng)絡(luò)論壇中的突發(fā)話題。針對(duì)論壇中的詞與用戶分別設(shè)計(jì)了一套基于位置的權(quán)重策略和基于角色的權(quán)重策略。在兩大權(quán)重策略的基礎(chǔ)上,首先對(duì)詞與用戶建立相應(yīng)的時(shí)間序列;然后采用頻譜劃分技術(shù)來分割時(shí)間序列;最后利用二維向量空間Vf來表示劃分后的時(shí)間序列?；诙S向量空間,模型可以過濾掉噪音詞,提取burst詞與核心用戶。在burst詞與核心用戶上應(yīng)用無監(jiān)督學(xué)習(xí)的話題發(fā)現(xiàn)模型來發(fā)現(xiàn)突發(fā)話題與用戶社區(qū)。

我們?cè)凇八旧鐓^(qū)”數(shù)據(jù)集上進(jìn)行了大量的實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果表明,提出的模型在少量的burst詞上就能夠檢測(cè)到80%以上的突發(fā)話題。Burst詞不僅幫助發(fā)現(xiàn)算法節(jié)約了開支,同時(shí)對(duì)噪音詞的過濾也提高了突發(fā)話題的發(fā)現(xiàn)精度。輿情控制的目的不僅是找到突發(fā)話題,更重要的是能夠找到與這些突發(fā)話題相關(guān)聯(lián)的一些核心用戶以及由這些用戶所構(gòu)成的網(wǎng)絡(luò)社區(qū)。本文提出的模型就能夠很好的滿足這點(diǎn)。

未來的研究集中在突發(fā)話題的演變與衰老上,我們計(jì)劃從核心用戶以及他們構(gòu)成的網(wǎng)絡(luò)社區(qū)來研究話題的演變與衰老。無論如何,我們相信本文提出的模型對(duì)網(wǎng)絡(luò)論壇post流的基礎(chǔ)性研究將會(huì)有很大的幫助。

[1] http：//www.new sm th.net/[EB/OL].

[2] J.A llan,R.Papka,and V.Lav renko.On-linenew event detection and tracking[C]//Proceedings of the 21st Annual International ACM SIGIR Conference,1998：37-45.

[3] K.Zhang,J.Li and G.W u.New Event Detection Based on Indexing-tree and Named Entity[C]//Proc.of ACM SIGIR'07,2007：215-222.

[4] J.Allan,V.Lav renko,and H.Jin.First story detection in tdt is hard[C]//CIKM,2000：374-381.

[5] N.Stokes and J.Carthy.Combining semantic and syntactic document classifiers to imp rove first story detection[C]//SIGIR,2001：424-425.

[6] Y.Yang,J.Zhang,J.Carbonell,and C.Jin.Topicconditioned novelty detection[C]//SIGKDD,2002：688-693.

[7] G.Kumaran and J.A llan.Text classification and named entities for new event detection[C]//SIGIR,2004：297-304.

[8] J.Allan,C.W ade,and A.Bolivar.Retrieval and novelty detection at the sentence level[C]//SIGIR,2003：314-321.

[9] Zhi-LiW u,and Chun-hung Li.Topic Detection in Online Discussion using Non-Negative M atrix Factorization[C]//IEEE/WIC/ACM International Conferences on Web Intelligence and Intelligent Agent Technology,2007.

[10] V ictor Cheng,and C.H.Li.Topic Detection Via Participation using M arkov Logic Netw ork[C]//Third International IEEE Conference on Signal-Image Technologies and Internet-Based System,2007.

[11] M ing liang Zhu,W eim ing H u,and Qu Wu.Topic Detection and Tracking for Threaded Discussion Communities[C]//IEEE/WIC/ACM International Conferences onWeb Intelligenceand Intelligent Agent Technology,2008.

[12] J.K leinberg.Bursty and hierarchical structure in streams[C]//SIGKDD,2002：91-101.

[13] R.Kumar,J.Novak,P.Raghavan,and A.Tomkins[C]//On the bursty evolution of blogspace.In WWW,2005：159-178.

[14] Qi He,Kuiyu Chang,and Ee-Peng Lim.Analyzing feature Trajectories for event detection[C]//Proceedings of the 30th Annual International ACM SIGIR Conference,2007：207-214.

[15] Gabriel Pui Cheong Fung,Jeffrey Xu Yu,Philip S.Yu,and Hong jun Lu.Parameter free bursty events detection in textstreams[C]//Proceedings of the31st international conference on Very large data base,2005：181-192.

[16] R.C.Sw an and J.A llan.Ex trac ting significant time varying features from text[C]//Proceedings of the 8th international conference on Information and know ledgemanagement,1999.

[17] Nish Parikh and Neel Sundaresan.Scalable and near real-time burst detection from eCommerce queries[C]//Proceedings of the 14th ACM SIGKDD international conference on Know ledge discovery and data m ining,2008：972-980.