基于特征驅(qū)動(dòng)的微博話題檢測(cè)方法

賀 敏，劉 瑋,，劉 悅，王麗宏，白 碩，程學(xué)旗

(1. 中國(guó)科學(xué)院計(jì)算技術(shù)研究所 中國(guó)科學(xué)院網(wǎng)絡(luò)數(shù)據(jù)科學(xué)與技術(shù)重點(diǎn)實(shí)驗(yàn)室，北京 100190；2. 國(guó)家計(jì)算機(jī)網(wǎng)絡(luò)應(yīng)急技術(shù)處理協(xié)調(diào)中心，北京 100029)

基于特征驅(qū)動(dòng)的微博話題檢測(cè)方法

賀 敏1，劉 瑋1,2，劉 悅1，王麗宏2，白 碩1，程學(xué)旗1

(1. 中國(guó)科學(xué)院計(jì)算技術(shù)研究所 中國(guó)科學(xué)院網(wǎng)絡(luò)數(shù)據(jù)科學(xué)與技術(shù)重點(diǎn)實(shí)驗(yàn)室，北京 100190；2. 國(guó)家計(jì)算機(jī)網(wǎng)絡(luò)應(yīng)急技術(shù)處理協(xié)調(diào)中心，北京 100029)

該文針對(duì)微博數(shù)據(jù)稀疏、內(nèi)容關(guān)系難以計(jì)算的特點(diǎn)，提出了一種基于特征驅(qū)動(dòng)的微博話題檢測(cè)方法。提取有意義串作為微博動(dòng)態(tài)特征，根據(jù)微博的結(jié)構(gòu)關(guān)系計(jì)算特征的作者影響力和文檔影響力，與內(nèi)容統(tǒng)計(jì)特性共同構(gòu)成特征的屬性組，采用邏輯回歸對(duì)特征建模，基于屬性組對(duì)特征二元分類得到話題關(guān)鍵特征，將關(guān)鍵特征之間的互信息作為距離度量，改進(jìn)最近鄰聚類方法對(duì)關(guān)鍵特征聚類產(chǎn)生話題。微博數(shù)據(jù)實(shí)驗(yàn)表明，該方法有效提高了微博話題檢測(cè)的準(zhǔn)確率和召回率。

話題檢測(cè)；微博；關(guān)鍵特征；邏輯回歸；聚類

1 引言

近年來，隨著Web2.0社交網(wǎng)絡(luò)的興起，微博憑借平臺(tái)開放性、終端擴(kuò)展性、內(nèi)容簡(jiǎn)潔性和低門檻等特性，在網(wǎng)民中迅速流行起來。微博用戶數(shù)量大，信息傳播速度快，發(fā)展成為網(wǎng)民獲取新聞時(shí)事、人際交往、自我表達(dá)、社會(huì)分享以及社會(huì)參與的重要媒介。由于大量的網(wǎng)民在微博上參與討論社會(huì)事件，微博不僅是信息產(chǎn)生和傳播的重要平臺(tái)，而且是反映社情民意的輿論陣地。但是，微博也具有信息零碎、內(nèi)容多樣、數(shù)量龐大等特點(diǎn)，為信息獲取和信息組織帶來了嚴(yán)重的信息過載和信息碎片問題。而面向微博的話題檢測(cè)技術(shù)，能夠從話題粒度上重新組織微博數(shù)據(jù)，成為解決上述問題的關(guān)鍵技術(shù)之一。所以，在海量的微博信息中，及時(shí)、準(zhǔn)確的檢測(cè)社會(huì)性話題，能夠輔助發(fā)現(xiàn)網(wǎng)絡(luò)輿情事件和判斷輿論趨勢(shì)，在輿情監(jiān)控、信息安全等領(lǐng)域具有重要的現(xiàn)實(shí)意義。

話題檢測(cè)是TDT一個(gè)傳統(tǒng)的研究方向，但是微博數(shù)據(jù)具有諸多不同于傳統(tǒng)新聞數(shù)據(jù)的顯著特點(diǎn)，這些新特點(diǎn)為面向微博的話題檢測(cè)技術(shù)帶來了新的挑戰(zhàn)。

(1) 微博新詞涌現(xiàn)導(dǎo)致詞空間的動(dòng)態(tài)變化。每個(gè)用戶隨時(shí)都可以發(fā)表微博，信息具有原創(chuàng)性和時(shí)效性的同時(shí)，也表現(xiàn)出草根性和隨意性，用詞口語化、不規(guī)范現(xiàn)象嚴(yán)重，簡(jiǎn)稱、縮略語大量存在，這些碎片信息需要依賴語言上下文來輔助分析。隨著網(wǎng)絡(luò)事件的事態(tài)發(fā)展，微博空間不斷涌現(xiàn)出大量的新詞，用傳統(tǒng)的靜態(tài)詞典中的詞語來表示文本，將會(huì)遺漏部分關(guān)鍵特征。

(2) 數(shù)據(jù)高維稀疏導(dǎo)致內(nèi)容關(guān)系難以準(zhǔn)確計(jì)算。傳統(tǒng)特征向量文本表示方法中，通常以詞作為特征，并使用TF-IDF方法來衡量每個(gè)特征(即向量每一維) 的權(quán)重。 但是對(duì)于微博來說，它的文本內(nèi)容非常短，同一個(gè)詞出現(xiàn)在不同短文本中的概率會(huì)遠(yuǎn)小于長(zhǎng)文本，這種數(shù)據(jù)的稀疏性，使得傳統(tǒng)文本表示方法很難準(zhǔn)確計(jì)算文本間的相似度。

(3) 話題分散多樣，信息噪聲大。微博是一種自媒體，用戶可以隨時(shí)發(fā)表自己的所見所聞所感所想，導(dǎo)致在同一時(shí)間，微博上各種不同類別的話題，如時(shí)政類、民生類、娛樂八卦類、個(gè)人生活瑣事等多種話題摻雜在一起，這些大量的個(gè)人信息類話題對(duì)于發(fā)現(xiàn)社會(huì)性話題構(gòu)成噪聲。而新聞數(shù)據(jù)以公眾關(guān)注的社會(huì)性話題為主，無需考慮個(gè)人生活類的信息噪聲。

本文針對(duì)上述挑戰(zhàn)，提出基于特征驅(qū)動(dòng)的微博話題檢測(cè)方法，首先通過有意義串提取來發(fā)現(xiàn)微博的動(dòng)態(tài)特征，然后根據(jù)微博的作者關(guān)注關(guān)系和轉(zhuǎn)發(fā)評(píng)論關(guān)系計(jì)算特征的非內(nèi)容屬性，與特征的內(nèi)容統(tǒng)計(jì)特性共同構(gòu)成多重屬性組，依據(jù)特征屬性采用邏輯回歸的方法對(duì)特征進(jìn)行二元分類，得到話題相關(guān)的關(guān)鍵特征和話題無關(guān)的噪聲特征，最后將關(guān)鍵特征的互信息作為其距離度量，改進(jìn)最近鄰聚類算法對(duì)其聚類產(chǎn)生話題。

2 相關(guān)工作

傳統(tǒng)的話題檢測(cè)研究主要包括兩類：基于文本聚類的方法和基于概率話題模型的方法。在基于文本聚類的方法中，文本表示通常使用向量空間模型(VSM)，文本相似度計(jì)算多采用歐式距離和余弦夾角距離。Papka等人[1]首先提出SinglePass的聚類思想，是一種效果較好的在線話題檢測(cè)方法；雷震等人[2]提出了一種用于事件檢測(cè)的增量K均值聚類算法，使用密度函數(shù)法進(jìn)行聚類中心初始化；駱衛(wèi)華等人[3]提出了針對(duì)事件特點(diǎn)的單粒度話題識(shí)別方法，采用了自底向上的層次凝聚式聚類方法。在基于概率話題模型方法中，比較典型的是產(chǎn)生式模型LDA[4],由Blei等人在2003年提出，認(rèn)為文檔集合由隱含在文檔集合背后的話題集合生成，而每個(gè)話題都是詞的概率分布，一篇文章的每個(gè)詞都是通過以一定概率選擇了某個(gè)主題，并從這個(gè)主題中以一定概率選擇某個(gè)詞語。后來有學(xué)者提出了LDA模型的各種變形，主要分為層次結(jié)構(gòu)的話題模型和有監(jiān)督的話題模型兩類。 HLDA[5]模型是一種有層次結(jié)構(gòu)話題模型，在LDA的基礎(chǔ)上，試圖建立話題之間的層次關(guān)系，用Chinese restaurant process去自動(dòng)決定每一層的話題數(shù)量。labeled LDA[6]模型是一種有監(jiān)督的話題模型，通過訓(xùn)練得到帶標(biāo)簽的topic，為某個(gè)詞選擇話題時(shí)，只從文檔相關(guān)的label對(duì)應(yīng)的topic中去選擇。上述方法主要針對(duì)長(zhǎng)文本，將詞作為特征，采用TF-IDF來作為權(quán)重，對(duì)于特征高度稀疏的微博文本適用性較差。

近年來，也出現(xiàn)了一些針對(duì)微博話題方面的研究， 一類是通過特征擴(kuò)展來解決特征稀疏的問題，如Sharifi等人[7]將Twitter文本分類到預(yù)定義的話題類別時(shí)，通過抽取作者profile文件和文本記錄中的領(lǐng)域相關(guān)的特征集合，對(duì)Twitter文本的特征進(jìn)行擴(kuò)充。Liu等人[8]試圖借助HowNet實(shí)現(xiàn)特征擴(kuò)展，但也帶來了一些噪聲信息，導(dǎo)致處理效果提高不明顯；另一類是提高關(guān)鍵特征提取準(zhǔn)確率，Lee等人[9]結(jié)合滑動(dòng)窗口技術(shù)提出了一種名為BursT特征權(quán)重算法，該算法能夠在動(dòng)態(tài)環(huán)境抽取重要特征，與遞增TF-IDF進(jìn)行比較，具有明顯的優(yōu)勢(shì)。Du等人[10]提出了另一種新的關(guān)鍵詞權(quán)重計(jì)算方法，詞的權(quán)重計(jì)算主要考慮用戶的權(quán)威性、受眾數(shù)量、回復(fù)數(shù)量及關(guān)鍵詞集等因素。Kasiviswanathan等人[11]提出了通過詞典學(xué)習(xí)的方法來識(shí)別新話題，如果當(dāng)前時(shí)刻的文檔不能用從前一時(shí)刻文檔中提取的詞典線性表示，則將文檔判定為新穎文檔，再將所有新文檔聚類產(chǎn)生新話題。上述方法對(duì)于緩解特征稀疏有幫助，但是又引入了新的特征，增加了特征維度，也會(huì)帶來一些噪聲，不能從根本上解決特征稀疏和特征動(dòng)態(tài)變化的問題。本文從實(shí)時(shí)信息中動(dòng)態(tài)提取特征，以特征為核心來檢測(cè)話題，既能局部降維，又避免了文本相似度的計(jì)算問題。

3 特征驅(qū)動(dòng)的微博話題發(fā)現(xiàn)方法

3.1 基于有意義串發(fā)現(xiàn)的微博特征提取

作者前期提出了有意義串的概念[12-13]，指具有統(tǒng)計(jì)意義、包含具體語義、能夠獨(dú)立靈活使用的語言單元，既包含未登錄的新詞和命名實(shí)體，又包含有意義的詞組和短語，如“禽流感”“輸油管爆燃”“孫楊”“延長(zhǎng)春節(jié)假期”等。有意義串發(fā)現(xiàn)是一種回顧性檢測(cè)，主要發(fā)現(xiàn)表現(xiàn)出重復(fù)特性的有意義的字符串，發(fā)現(xiàn)的一個(gè)重要依據(jù)是字符串的鄰接類別VN(variety of neighbour)，表示字符串的上文或者下文相鄰的不同語言單元的類別數(shù)量，反映了字符串語言環(huán)境的靈活性。具體的提取過程為，首先通過重復(fù)串發(fā)現(xiàn)得到具有統(tǒng)計(jì)意義的候選字符串，然后計(jì)算重復(fù)串的上下文鄰接類別，來衡量候選串是否滿足語用多樣性，最后通過語言模型來判斷字符串的語義完整性，經(jīng)過兩層過濾得到有意義串。

從有意義串的提取過程可看出，有意義串在當(dāng)前時(shí)間的真實(shí)文本中具有一定流通度，能夠在多種不同語言環(huán)境中使用。而且，有意義串的粒度可以比詞語更大，能夠更加具體完整地反映話題的關(guān)鍵信息。隨著網(wǎng)絡(luò)事件的事態(tài)發(fā)展，微博空間不斷涌現(xiàn)出大量的新詞和術(shù)語，用傳統(tǒng)的靜態(tài)詞典中的詞語來表示微博信息，將會(huì)遺漏部分關(guān)鍵特征，而從微博流通文本中提取出來的有意義串，可以涵蓋正在使用的微博新詞和術(shù)語，能夠更加準(zhǔn)確有效的反映微博的實(shí)時(shí)內(nèi)容。所以，與傳統(tǒng)的詞空間相比，有意義串空間更適合表示微博信息。本文將有意義串作為微博信息的基本特征，采用上下文鄰接分析與語言模型相結(jié)合的方法[12]，以天作為時(shí)間窗口，動(dòng)態(tài)檢測(cè)微博信息中的有意義串，構(gòu)成微博信息的動(dòng)態(tài)特征空間。

3.2 基于邏輯回歸的關(guān)鍵特征識(shí)別

由于微博信息內(nèi)容多樣化，既包括時(shí)政、民生等社會(huì)性熱點(diǎn)話題，又包括大量的娛樂八卦、生活瑣事和個(gè)人信息。在3.1節(jié)有意義串的提取過程中，上述兩類信息中表現(xiàn)出重復(fù)特性的短語或新詞均被識(shí)別出來，共同構(gòu)成時(shí)間窗口內(nèi)微博信息的特征。但是，在這些特征中，有些是微博話題相關(guān)的，反映出話題內(nèi)容，如“變速器”“大眾汽車”“安全隱患”，稱為話題的關(guān)鍵特征；有些則與微博話題無關(guān)，如“工作人員”“小伙伴們”“今天下午”，對(duì)于話題發(fā)現(xiàn)稱為噪聲特征。所以，為了準(zhǔn)確有效的發(fā)現(xiàn)話題，需要進(jìn)一步在已經(jīng)提取的微博特征中識(shí)別出話題關(guān)鍵特征。

3.2.1 特征屬性

微博特征非常稀疏，每個(gè)特征在一條微博中出現(xiàn)頻次很低，大部分都是1～2次，采用傳統(tǒng)的TF-IDF計(jì)算方法將無法選擇出關(guān)鍵特征。但是，微博除了內(nèi)容信息之外，包含大量的非內(nèi)容信息，這包括博主之間的關(guān)注關(guān)系，微博信息的動(dòng)態(tài)轉(zhuǎn)發(fā)評(píng)論關(guān)系，這些信息能夠間接反映微博信息的重要程度。下面，將定義特征的非內(nèi)容屬性、作者影響力和文檔影響力。

微博博主之間的關(guān)注和被關(guān)注關(guān)系構(gòu)成一個(gè)網(wǎng)絡(luò)，每個(gè)博主的被關(guān)注對(duì)象與數(shù)量，與其發(fā)表信息的質(zhì)量和傳播廣泛程度互相影響。博主發(fā)表信息質(zhì)量越高，則其信息傳播越廣泛，該博主將越受關(guān)注；博主被關(guān)注的數(shù)量越多，其信息傳播越廣泛，說明其發(fā)布的信息越有價(jià)值。所以，博主的關(guān)注關(guān)系反映了博主在微博網(wǎng)絡(luò)中的影響力。因?yàn)椴┲鞯年P(guān)注關(guān)系具有類似網(wǎng)頁鏈接關(guān)系的特性，所以采用類Page Rank的方法來計(jì)算博主的影響力AuthRank，如式(1)所示。

根據(jù)博主影響力AuthRank，定義特征的作者影響力如下。

定義1特征的作者影響力Inf_Auth 指特征出現(xiàn)的所有微博信息的作者影響力之和。

其中，N表示特征Fi的總頻次，Dj表示特征Fi第j次出現(xiàn)的文檔，user(Dj)表示文檔Dj的作者。

從定義1看出，影響力較大的意見領(lǐng)袖往往發(fā)布較多的大眾話題信息和觀點(diǎn)，從這些信息中提取的特征，其作者影響力將較大，成為話題關(guān)鍵特征的可能性大。而草根網(wǎng)民發(fā)布的信息大多是個(gè)人瑣事，在這些信息中提取的特征，其作者影響力將較小，成為話題關(guān)鍵特征的可能性較小。

微博具有評(píng)論、轉(zhuǎn)發(fā)的機(jī)制，一條微博信息的評(píng)論、轉(zhuǎn)發(fā)次數(shù)越大，表示其受關(guān)注程度越高，也反映出該條信息的影響力越大。所以，通過評(píng)論數(shù)、轉(zhuǎn)發(fā)數(shù)來計(jì)算一條微博信息自身的影響力，如式(3)所示。

其中，Ncom、Nrep分別表示一條微博信息的評(píng)論數(shù)和轉(zhuǎn)發(fā)數(shù)，MAX{Ncom(Dj)}、MAX{Nrep(Dj)}分別表示文檔集合中的最大評(píng)論數(shù)和最大轉(zhuǎn)發(fā)數(shù)。γ和δ是調(diào)節(jié)參數(shù)。

定義2特征的文檔影響力Inf_Doc，指特征出現(xiàn)的所有微博信息的影響力之和。

對(duì)此，巴斯夫大中華區(qū)農(nóng)業(yè)解決方案部運(yùn)營(yíng)總監(jiān)王翔指出，數(shù)字化在巴斯夫農(nóng)業(yè)解決方案中占據(jù)重要地位。巴斯夫數(shù)字平臺(tái)在中國(guó)已進(jìn)行大量元素收集，計(jì)劃第一步推出病害識(shí)別系統(tǒng)，這需要大量的一手素材。巴斯夫與大疆合作后，在推廣方面取得了成績(jī)。

其中，N表示特征Fi的總頻次，Dj表示特征Fi第j次出現(xiàn)的文檔。

從定義2看出，廣泛轉(zhuǎn)發(fā)、評(píng)論的微博信息往往是大眾關(guān)心的社會(huì)性話題，從中提取的特征，其文檔影響力較大，成為話題關(guān)鍵特征的可能較大，而從不被轉(zhuǎn)發(fā)、評(píng)論的微博信息基本上是個(gè)人類信息，從中提取的特征，其文檔影響力較小，很可能是個(gè)人信息相關(guān)的噪聲特征。

除了特征的作者影響力和文檔影響力外，計(jì)算特征的頻次、長(zhǎng)度、鄰接類別等內(nèi)容統(tǒng)計(jì)特性，共同構(gòu)成特征的15個(gè)屬性，作為特征分類的依據(jù)，具體如表1所示。

表1 特征屬性

3.2.2 關(guān)鍵特征識(shí)別的邏輯回歸模型

邏輯回歸是一種典型的分類預(yù)測(cè)模型，樣本的各個(gè)屬性之間不需要滿足條件獨(dú)立假設(shè)，但各個(gè)屬性的貢獻(xiàn)是獨(dú)立計(jì)算的，所以，邏輯回歸適用于解決特征的二元分類問題。表1中的15個(gè)屬性構(gòu)成特征的15維屬性向量，記作xi=(xi1,xi2...xi15)，分類結(jié)果用Y表示，Y=1表示關(guān)鍵特征，Y=0表示噪聲特征，則特征的邏輯回歸分類模型如式(5)所示。

采用常用的最大似然估計(jì)來擬合模型中的參數(shù)，假設(shè)對(duì)已知N個(gè)特征及其屬性進(jìn)行了標(biāo)注，包括關(guān)鍵特征和噪聲特征，則N個(gè)特征對(duì)數(shù)似然函數(shù)如式(6)所示。

設(shè)p(xi;θ)=Pr(Y=1|x=xi;θ),yi表示標(biāo)注的分類結(jié)果，則對(duì)數(shù)似然可以表示為式(7)。

為極大化對(duì)數(shù)似然，令式(7)的導(dǎo)數(shù)為0，得到16個(gè)β上的非線性方程組，如式(8)所示。

為求解式(8)，使用牛頓-拉夫森(Newton-raphson)迭代算法，計(jì)算二階導(dǎo)數(shù)，得到式(9)。

以βold開始，單個(gè)牛頓-拉夫森更新是：

經(jīng)過數(shù)次更新迭代，βnew收斂，得到邏輯回歸模型的參數(shù)。

產(chǎn)生邏輯回歸模型后，還需要在標(biāo)注特征集合中訓(xùn)練閾值PT，當(dāng)Pr(Y=1|X=x)大于PT時(shí)為關(guān)鍵特征，否則為噪聲特征。

3.2.3 改進(jìn)的最近鄰特征聚類

一個(gè)話題通常由若干個(gè)關(guān)鍵特征來描述，在3.2節(jié)識(shí)別出話題關(guān)鍵特征后，需要通過特征聚類來產(chǎn)生話題。采用互信息作為特征之間的距離度量，改進(jìn)最近鄰聚類算法對(duì)特征聚類。

特征之間的互信息指特征在相同微博信息中的共現(xiàn)情況，體現(xiàn)了兩個(gè)特征的依賴程度，互信息越高，特征的相關(guān)度越高，描述同一話題的可能性越大。特征X和特征Y的互信息計(jì)算公式如式(11)所示。

其中，P(X)表示特征X在時(shí)間窗口文檔中出現(xiàn)的概率,P(X)=N(X)/NDOC，N(X)是包含特征X的文檔數(shù)，NDOC是觀察窗口的總文檔數(shù)。P(X,Y)表示特征X和Y同時(shí)出現(xiàn)的概率，P(X,Y)=N(X,Y)/NDOC,N(X,Y)是同時(shí)包含特征X和Y出現(xiàn)的文檔數(shù)。

特征是聚類的樣本點(diǎn)，互信息表示特征之間的距離，聚類產(chǎn)生的簇是話題。由于每天的話題數(shù)量不確定，聚類的中心數(shù)無法事先確定，K-means、K-Medoids等經(jīng)典聚類方法不太適用。一個(gè)話題相關(guān)的特征之間互信息較大，不同話題的特征之間互信息較小，所以聚出的話題類內(nèi)距離小，類間距離大，最近鄰聚類方法比較適合。對(duì)最近鄰聚類方法的初始聚類樣本選取、距離計(jì)算及聚類過程進(jìn)行改進(jìn)，進(jìn)行有監(jiān)督的不完全聚類產(chǎn)生話題。

受分類性能的限制，3.2節(jié)關(guān)鍵特征的識(shí)別準(zhǔn)確率難以做到100%，在產(chǎn)生的關(guān)鍵特征中仍然包含少量噪聲特征，如果初始聚類樣本選擇了噪聲特征，則會(huì)干擾聚類結(jié)果，產(chǎn)生噪聲類。所以，改進(jìn)對(duì)初始聚類樣本的選取，從所有樣本點(diǎn)中選擇距離最近，且距離小于閾值D的一對(duì)樣本的其中之一作為初始聚類樣本。這樣選擇能夠避免選到噪聲特征，因?yàn)橐话憔嚯x很近的兩個(gè)特征應(yīng)該屬于同一話題，都是話題關(guān)鍵特征。

微博內(nèi)容短小，一個(gè)話題一般比較集中明確，話題的所有關(guān)鍵特征之間距離都比較近，所以對(duì)聚類的距離計(jì)算方法改進(jìn)，設(shè)置更嚴(yán)格的聚類條件。產(chǎn)生一個(gè)簇后，用新樣本點(diǎn)與該簇已有樣本點(diǎn)之間的平均距離來表示新樣本點(diǎn)與簇之間的距離，選擇新樣本點(diǎn)聚入該簇需滿足兩個(gè)條件，一個(gè)是與該類別距離最近，另一個(gè)是與該簇已有樣本點(diǎn)的距離都大于閾值D。聚類過程也與最近鄰聚類不同，最近鄰聚類是一個(gè)樣本點(diǎn)與所有簇比較距離，選擇最近的聚入，而本方法中初始聚類樣本確定后，即確定了一個(gè)簇，由所有樣本點(diǎn)與簇比較距離，選擇新的樣本點(diǎn)聚入，如無新樣本點(diǎn)，該簇聚類完畢，選擇下一個(gè)初始樣本點(diǎn)產(chǎn)生新簇。算法如圖1所示。

輸入：關(guān)鍵特征集合及特征之間的互信息；輸出：話題．Step1：選擇特征樣本中距離最近，且距離小于D的兩個(gè)樣本點(diǎn)之一作為新簇；Step2：計(jì)算每個(gè)樣本點(diǎn)與簇之間的距離；Step3：選擇與簇距離最近，且與簇中每個(gè)樣本距離小于D的新樣本聚入該簇；Step4：重復(fù)step3，如果沒有滿足條件的樣本，該簇聚類結(jié)束，產(chǎn)生一個(gè)話題；Step5：重復(fù)step1，直到?jīng)]有滿足條件的樣本，聚類結(jié)束．圖1 改進(jìn)的最近鄰聚類算法

距離閾值D由已標(biāo)注的話題與聚類結(jié)果訓(xùn)練產(chǎn)生。

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

4.1 實(shí)驗(yàn)數(shù)據(jù)及評(píng)價(jià)標(biāo)準(zhǔn)

本文通過互聯(lián)網(wǎng)采集新浪微博1 000個(gè)加V活躍博主從2013年8月～11月發(fā)表的78萬余條微博信息作為實(shí)驗(yàn)數(shù)據(jù)。實(shí)驗(yàn)將8月～10月這三個(gè)月的數(shù)據(jù)作為訓(xùn)練語料，將11月的數(shù)據(jù)作為微博信息流檢測(cè)每天的話題。由兩名輿情分析領(lǐng)域的專業(yè)人員分別對(duì)每天的數(shù)據(jù)進(jìn)行標(biāo)注，分別產(chǎn)生1 863和 1 915個(gè)話題，取兩人標(biāo)注的交集共1 849個(gè)突發(fā)話題作為訓(xùn)練和評(píng)價(jià)實(shí)驗(yàn)結(jié)果的標(biāo)準(zhǔn)。根據(jù)標(biāo)注結(jié)果計(jì)算話題檢測(cè)的準(zhǔn)確率P、召回率R和綜合指標(biāo)F值，以此評(píng)價(jià)算法。在特征分類實(shí)驗(yàn)中,也由兩名輿情分析領(lǐng)域的專業(yè)人員對(duì)計(jì)算的有意義串進(jìn)行標(biāo)注,產(chǎn)生9 368個(gè)關(guān)鍵特征和12 852個(gè)噪聲特征,作為特征分類的標(biāo)準(zhǔn)。

4.2 實(shí)驗(yàn)結(jié)果

4.2.1 特征分類結(jié)果

采用邏輯回歸對(duì)特征進(jìn)行分類，參數(shù)PT對(duì)分類結(jié)果的影響如圖2所示。從圖2中看出，隨著參數(shù)PT的增大，關(guān)鍵特征的準(zhǔn)確率逐漸上升，但是召回率逐漸下降，而且召回率影響大于準(zhǔn)確率，F(xiàn)值也逐漸下降。因?yàn)镻T增大，關(guān)鍵特征篩選條件更加嚴(yán)格，在將絕大多數(shù)噪聲特征過濾的同時(shí)也過濾了部分關(guān)鍵特征，導(dǎo)致召回率下降比較多。PT取值為0.45時(shí)，F(xiàn)值最大，實(shí)驗(yàn)中取該值作為關(guān)鍵特征和噪聲特征的區(qū)分。

圖2 參數(shù)PT對(duì)邏輯回歸結(jié)果的影響

3.2.1節(jié)中選取了特征的15個(gè)屬性，為了觀察這些屬性對(duì)于分類的貢獻(xiàn)，將屬性按表2分組，逐漸增加屬性，對(duì)分類結(jié)果的影響如圖3所示。從圖3看出，隨著屬性組的增加，分類準(zhǔn)確率逐漸提高，召回率有一定下降，F(xiàn)值基本保持穩(wěn)定，略有提高。這表明各屬性組對(duì)于提高關(guān)鍵特征識(shí)別的準(zhǔn)確率均有貢獻(xiàn)。

表2 屬性分組

本實(shí)驗(yàn)將貝葉斯分類和SVM分類方法對(duì)特征進(jìn)行分類，并與邏輯回歸分類方法的結(jié)果對(duì)比，如表3所示。從表中看出，邏輯回歸的準(zhǔn)確率和F值明顯高于貝葉斯分類和SVM分類方法。因?yàn)樘卣鞯?5個(gè)屬性之間并非相互獨(dú)立，有些屬性相關(guān)性較高，但是針對(duì)每個(gè)屬性的貢獻(xiàn)是獨(dú)立計(jì)算的，邏輯回歸更適用于這種場(chǎng)景。

圖3 屬性對(duì)邏輯回歸分類結(jié)果的影響

表3 特征分類結(jié)果對(duì)比

4.2.2 特征聚類結(jié)果

實(shí)驗(yàn)采用了最近鄰聚類方法，將15個(gè)屬性邏輯回歸的分類結(jié)果作為輸入，與改進(jìn)的最近鄰聚類方法聚類結(jié)果對(duì)比，如表4所示。從表中看出，改進(jìn)的最近鄰聚類方法比最近鄰聚類方法在準(zhǔn)確率、召回率和F值方面均有大幅提升。在對(duì)算法改進(jìn)中，限制更加嚴(yán)格的條件選取初始樣本點(diǎn)和合并樣本點(diǎn)，能夠進(jìn)一步過濾噪聲特征，避免了噪聲特征對(duì)聚類簇的干擾，從而提高了準(zhǔn)確率和召回率。

表4 特征聚類結(jié)果對(duì)比

為了觀察特征分類的準(zhǔn)確率、召回率對(duì)聚類結(jié)果的影響，針對(duì)4.2.2節(jié)中的參數(shù)PT調(diào)整和屬性分組情況下不同的分類結(jié)果，對(duì)特征聚類的結(jié)果進(jìn)行分析，如圖4和圖5所示。從圖4中看出，參數(shù)PT取值為0.45時(shí)，聚類結(jié)果的準(zhǔn)確率、召回率和F值都最大，隨著PT的增大或減小，準(zhǔn)確率、召回率和F值都逐漸下降。這與圖2的分類結(jié)果中，F(xiàn)值在參數(shù)PT取值為0.45時(shí)最大，PT增大或減小時(shí)F值逐漸下降時(shí)一致的，但是與分類結(jié)果的準(zhǔn)確率和召回率的變化趨勢(shì)不一致。這表明，分類結(jié)果的綜合指標(biāo)F值對(duì)特征聚類影響比較敏感，應(yīng)該選擇F值最大的分類結(jié)果進(jìn)行聚類。從圖5中看出，隨著屬性組的增加，聚類結(jié)果的準(zhǔn)確率、召回率和F值均不斷上升，而在圖2的分類結(jié)果中，隨著屬性組的增加，F(xiàn)值趨于穩(wěn)定，準(zhǔn)確率提升較大，召回率有所下降。這表明在F值相同的情況下，聚類結(jié)果對(duì)分類結(jié)果的準(zhǔn)確率更敏感，分類結(jié)果的準(zhǔn)確率對(duì)于聚類質(zhì)量影響較大，而召回率影響不大。

圖4 邏輯回歸參數(shù)調(diào)整對(duì)聚類結(jié)果的影響

4.2.3 話題檢測(cè)結(jié)果

與本文方法對(duì)比，實(shí)驗(yàn)也采用了將詞作為特征表示文檔， 采用K-means方法的傳統(tǒng)話題檢測(cè)方法[14]。結(jié)果如表5。

圖5 針對(duì)不同屬性分類的聚類結(jié)果

表5 突發(fā)話題檢測(cè)結(jié)果

從表5中明顯看出，本文方法在微博話題檢測(cè)方面效果優(yōu)于K-means方法。傳統(tǒng)方法由于特征稀疏，發(fā)現(xiàn)的話題質(zhì)量不高；本文方法符合微博數(shù)據(jù)的特點(diǎn)，采用有意義串作為特征來表示文本，較好地緩解了特征稀疏的問題，通過特征分類準(zhǔn)確地提取了話題的關(guān)鍵信息，關(guān)鍵特征與話題存在對(duì)應(yīng)關(guān)系，通過特征聚類產(chǎn)生表征話題的特征簇，直觀地反映了話題內(nèi)容。因此以特征為驅(qū)動(dòng)，通過發(fā)現(xiàn)關(guān)鍵特征進(jìn)而檢測(cè)話題的方法適用于大規(guī)模的微博數(shù)據(jù)。兩種方法產(chǎn)生的部分話題結(jié)果樣例如表6。從表中看出，本文方法檢測(cè)發(fā)現(xiàn)的話題更加直觀，有意義串關(guān)鍵特征比詞語表達(dá)更強(qiáng)的語義概念。

表6 話題檢測(cè)結(jié)果樣例

續(xù)表

5 結(jié)束語

本文針對(duì)微博文本數(shù)據(jù)稀疏、關(guān)系難以計(jì)算、微博內(nèi)容繁雜、信息噪聲大的特點(diǎn)，提出了一種以特征驅(qū)動(dòng)的微博話題檢測(cè)方法。通過有意義串發(fā)現(xiàn)來提取微博特征，通過微博作者之間的關(guān)注關(guān)系計(jì)算特征的作者影響力，通過微博的評(píng)論、轉(zhuǎn)發(fā)數(shù)量計(jì)算特征的文檔影響力，影響力特性與特征的頻次等內(nèi)容統(tǒng)計(jì)特性共同構(gòu)成特征的屬性組，采用邏輯回歸對(duì)特征建模，依據(jù)特征屬性進(jìn)行二分類，產(chǎn)生話題關(guān)鍵特征和噪聲特征，將特征之間的互信息作為距離度量，對(duì)最近鄰聚類方法進(jìn)行改進(jìn)，針對(duì)關(guān)鍵特征聚類產(chǎn)生話題。從實(shí)驗(yàn)結(jié)果看出，以特征為驅(qū)動(dòng)，通過發(fā)現(xiàn)關(guān)鍵特征來檢測(cè)話題的方法適用于微博話題檢測(cè)，關(guān)鍵特征的識(shí)別準(zhǔn)確與否直接決定了話題檢測(cè)的質(zhì)量。 與傳統(tǒng)方法相比，該方法有效提高了微博話題檢測(cè)的準(zhǔn)確率和召回率。

以特征為驅(qū)動(dòng)的微博話題檢測(cè)方法對(duì)于微博數(shù)據(jù)較為有效，在此框架下，仍然可以通過提取微博信息中的其他結(jié)構(gòu)化信息與非內(nèi)容信息，優(yōu)化特征屬性計(jì)算和分類方法，來提高關(guān)鍵特征識(shí)別準(zhǔn)確率，進(jìn)而提高話題檢測(cè)性能。

[1] Papka R, Allan J. On-line new event detection using single pass clustering[R]. USA: University of Massachusetts, 1998.

[2] 雷震，吳玲達(dá)，雷蕾，等. 初始化類中心的增量K軍執(zhí)法及其在新聞事件探測(cè)的應(yīng)用[J]. 情報(bào)學(xué)報(bào)，2006，25(3): 289-295.

[3] 駱衛(wèi)華，于滿泉，許洪波，等. 基于多策略優(yōu)化的分治多層聚類算法的話題發(fā)現(xiàn)研究[J].中文信息學(xué)報(bào)，2006, 20(1): 29-36.

[4] BleiD, Ng A, Jordan M. Latent dirichlet allocation[J]. Journal of Machine Learning Research: 2003, 3(2003): 993-1022.

[5] Blei D, Griffiths T, Jordan M, et al. Hierarchical topic models and the nested Chinese restaurant process[C]//Proceedings of NIPS 04’. Denver, USA： NIPS, 2004.

[6] RamageD, Hall D, Nallapati R，et al. Labeled LDA: a supervised topic model for credit attribution in multi-labeled corpora[C]//Proceedings of EMNLP 09’. Stroudsburg, PA: ACL, 2004.

[7] Sharifi B, Hutton M, Kalita J.Summarizing microblogs with topic models[C]//Proceedings of 11th Annual Conference of the North American Chapter of the Association for Computational Linguistics. Los Angeles, USA: NAACL, 2010: 685-688.

[8] Liu Z, Yu W, Chen W. Short Text Feature Selection and Classification for MicroBlog Mining[C]//Proceedings of International Conference on Computational Intelligence and Software Engineering. Piscataway, NJ: IEEE, 2010: 1-4.

[9] Lee C, Wu C, Chien T. BursT: A Dynamic Term Weighting Scheme for Mining Microblogging Messages[C]//Proceedings of 8th International Symposium on Neural Networks. Piscataway, NJ: IEEE , 2011.

[10] Du Yanyan,He Yanxiang,Tian Ye. Microblog bursty topic detection based on userrelationship[C]//Proceedings of 6th IEEE Information Technology and Artificial Intelligence Conference. Piscataway, NJ： IEEE, 2011: 260-263.

[11] Kasiviswanathan S, Melville P, Banerjee A. Emerging topic detection using dictionary learning[C]//Proceedings of conference on CIKM’11. New York: ACM , 2011: 745-754.

[12] 賀敏.面向互聯(lián)網(wǎng)的中文有意義串挖掘[D]. 中國(guó)科學(xué)院計(jì)算技術(shù)研究所碩士學(xué)位論文，2007.

[13] 賀敏，王麗宏，杜攀，等．基于有意義串聚類的微博熱點(diǎn)話題發(fā)現(xiàn)方法[J]．通信學(xué)報(bào)，2013, 34(Z1): 256-262.

[14] Yang S, Cheng X, Chen Y. Detect events on noisy textual datasets[C]//Proceedings of the 12th International Asia-Pacific Web Conference. Busan, Korea: IEEE, 2010.

FeatureDrivenMicroblogTopicDetection

HE Min1, LIU Wei1，2, LIU Yue1, WANG Lihong2, BAI Shuo1, CHENG Xueqi1

(1. CAS Key Laboratory of Newtwork Data Science and Technology, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China; 2. National Computer network Emergency Response technical Team/Coordination Center of China, Beijing 100029, China)

With the microblog properties of sparse data and difficult decision on relation of content, a feature-driven microblog topic detection method is proposed. The meaningful strings are extracted as dynamic microblog features. The author-influence and document-influence of features are defined according to the structure relation of microblogs, which form the attribute sets together with the statistics on content. The logic regression model is used to classify features into key features and noise features. The nearest neighbor clustering method is modified to derive the topics from clustering the key feartures, in which the mutual information of key features is applied as the distance measure. The microblog data experiment shows that the accuracy and recall are remarkably improved by the proposed method.

topic detection; microblog; key feature; logic regression; clustering

賀敏(1982—)，博士，高級(jí)工程師，主要研究領(lǐng)域社交網(wǎng)絡(luò)挖掘、輿情分析、自然語言處理等。

劉瑋(1984—)，博士，高級(jí)工程師，主要研究領(lǐng)域社交網(wǎng)絡(luò)挖掘、網(wǎng)絡(luò)信息安全等。

劉悅(1971—)，博士，副研究員，主要研究領(lǐng)域?yàn)樾畔z索、互聯(lián)網(wǎng)挖掘等。

1003-0077(2017)03-0101-08

2014-12-27定稿日期： 2015-02-24

國(guó)家科技支撐基金(2012BAH46B01)；國(guó)家自然科學(xué)基金(61170230)

TP391

：A