融合詞項(xiàng)關(guān)聯(lián)關(guān)系的半監(jiān)督微博聚類算法

馬慧芳,賈美惠子,袁 媛,張志昌

(西北師范大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院,蘭州730070)

融合詞項(xiàng)關(guān)聯(lián)關(guān)系的半監(jiān)督微博聚類算法

馬慧芳,賈美惠子,袁 媛,張志昌

(西北師范大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院,蘭州730070)

針對(duì)微博文本內(nèi)容短、稀疏、高維等特點(diǎn),提出一種改進(jìn)的半監(jiān)督微博聚類算法。該算法利用詞項(xiàng)間的關(guān)系豐富文本特征,通過(guò)定義詞項(xiàng)文檔間關(guān)聯(lián)關(guān)系和詞項(xiàng)文檔內(nèi)關(guān)聯(lián)關(guān)系揭示詞項(xiàng)間語(yǔ)義的關(guān)聯(lián)程度,并由此自動(dòng)生成有標(biāo)記的數(shù)據(jù)來(lái)指導(dǎo)聚類過(guò)程。對(duì)詞項(xiàng)先驗(yàn)信息進(jìn)行成對(duì)約束編碼,構(gòu)建基于詞項(xiàng)間成對(duì)約束的三重非負(fù)矩陣分解模型來(lái)實(shí)現(xiàn)微博的半監(jiān)督聚類。實(shí)驗(yàn)結(jié)果表明,該算法可以減少繁瑣的人工標(biāo)記過(guò)程,并能高效地進(jìn)行微博聚類。

微博;詞項(xiàng)關(guān)聯(lián)關(guān)系;成對(duì)約束;半監(jiān)督聚類;非負(fù)矩陣分解

1 概述

隨著Web2.0技術(shù)、無(wú)線網(wǎng)絡(luò)技術(shù)和移動(dòng)通信4G技術(shù)的發(fā)展,微博社交網(wǎng)絡(luò)平臺(tái)應(yīng)運(yùn)而生。作為一種新型的社交媒體,其海量的數(shù)據(jù)和主題多變的特點(diǎn)使得用戶難以找到感興趣的微博。直觀想法是將微博聚類至不同主題下方便用戶瀏覽與查詢。針對(duì)文本聚類的研究核心內(nèi)容包括文本表示和聚類模型兩部分。長(zhǎng)期以來(lái)文本表示的經(jīng)典模型是向量空間模型(Vector Space Model,VSM)、通過(guò)詞袋模型(Bag of Words,BOW)和信息檢索中的詞權(quán)重經(jīng)典計(jì)算方法 TF-IDF(Term Frequency-Inversed Document Frequency)對(duì)文本進(jìn)行向量化表示［1］。然后基于特征詞項(xiàng)計(jì)算文本間相似度完成聚類。由于詞空間具有高維、稀疏、多變和相關(guān)等特點(diǎn),使得文本聚類存在各種各樣的問(wèn)題和困難。與傳統(tǒng)文本不同,微博信息往往不遵循語(yǔ)法規(guī)則且內(nèi)容過(guò)短,僅包含140個(gè)字,無(wú)法提供足夠的詞語(yǔ)共現(xiàn)與共享語(yǔ)義信息來(lái)進(jìn)行相似度計(jì)算。此外,現(xiàn)實(shí)中很難得到有標(biāo)簽的樣本信息,對(duì)大量微博進(jìn)行手動(dòng)加標(biāo)件費(fèi)時(shí)費(fèi)力。

研究人員已在微博的聚類方面開(kāi)展了相關(guān)工作,并取得了一定進(jìn)展。主流的研究方法多采用面向長(zhǎng)文本的挖掘方法來(lái)分類微博。代表性的工作包括基于主題模型的方法［2-3］,也有一些研究人員探索傳統(tǒng)的監(jiān)督學(xué)習(xí)方法來(lái)實(shí)現(xiàn)為微博聚類［4-5］。然而微博的稀疏性和用詞不規(guī)范嚴(yán)重影響了這些方法的性能。此外,從微博中獲取帶類標(biāo)的數(shù)據(jù)仍需借助于人工,這在現(xiàn)實(shí)應(yīng)用中幾乎不可能。

針對(duì)微博長(zhǎng)度短、內(nèi)容稀疏的特點(diǎn),本文提出一種融合詞項(xiàng)關(guān)聯(lián)關(guān)系的半監(jiān)督非負(fù)矩陣分解聚類算法。通過(guò)挖掘微博內(nèi)部的詞語(yǔ)信息豐富微博的文本特征,自動(dòng)生成具有特定類別詞項(xiàng)標(biāo)注信息來(lái)輔助預(yù)測(cè)大量未標(biāo)注微博數(shù)據(jù),并從中挖掘出微博潛在主題和語(yǔ)義信息。具體地,以正交三重非負(fù)矩陣分解算法(Orthogonal Nonnegative Matrix Tri-Factoriz-ation, OTri-NMF)［6］為基礎(chǔ),從詞項(xiàng)關(guān)聯(lián)關(guān)系出發(fā),通過(guò)定義文檔內(nèi)關(guān)系與文檔間關(guān)系獲取詞項(xiàng)關(guān)系,并設(shè)計(jì)合理的先驗(yàn)信息編碼表示方法和迭代算法構(gòu)建半監(jiān)督三重非負(fù)矩陣分解算法來(lái)實(shí)現(xiàn)微博聚類。

2 先驗(yàn)信息

短文本應(yīng)用場(chǎng)景下隨著文檔規(guī)模的不斷上升詞項(xiàng)規(guī)模增速緩慢,基本趨于一個(gè)穩(wěn)定值。此外相應(yīng)的詞項(xiàng)中約95%詞在大多數(shù)文檔中的出現(xiàn)次數(shù)都等于1,即絕大數(shù)詞項(xiàng)的tf值與idf值相等［7］?，F(xiàn)有方法大多將文本向量每維視為彼此獨(dú)立不相關(guān)的信息進(jìn)行處理。即將每維特征詞項(xiàng)的距離差值對(duì)文本整體相似度的貢獻(xiàn)簡(jiǎn)單等同,不考慮不同特征分量間可能存在著的關(guān)聯(lián)關(guān)系。事實(shí)上,特征詞項(xiàng)分量間關(guān)聯(lián)性直接影響著文本相似度的計(jì)算結(jié)果。利用詞項(xiàng)間的關(guān)聯(lián)關(guān)系代替詞與文檔間的關(guān)系可以有效地降低短文本表示矩陣的維度并豐富短文本的詞項(xiàng)語(yǔ)義信息。

2.1 詞項(xiàng)關(guān)聯(lián)關(guān)系

先驗(yàn)信息生成的基礎(chǔ)是基于詞項(xiàng)的共現(xiàn)關(guān)系。顯然,同一微博中共現(xiàn)的詞項(xiàng)具有語(yǔ)義上的聯(lián)系,而不同微博中出現(xiàn)的詞項(xiàng)若通過(guò)某個(gè)或某些特定詞項(xiàng)在其他微博中共現(xiàn)也具有一定的語(yǔ)義關(guān)聯(lián)。如圖1所示。其中,d1和d2分別表示2篇微博,黑色圓點(diǎn)表示兩篇文檔中共有的詞項(xiàng),實(shí)線圈內(nèi)表示關(guān)聯(lián)詞關(guān)系的2種模式。左圖表示詞項(xiàng)在同一篇文檔中的關(guān)聯(lián)關(guān)系;右圖則表示詞項(xiàng)文檔間關(guān)聯(lián)關(guān)系。

圖1 關(guān)聯(lián)詞類型

考慮詞項(xiàng)ti的分布情況可由該詞項(xiàng)與上下文中的其它詞項(xiàng)共現(xiàn)向量ti(w11,w12,…,wij)來(lái)表示,wij表示詞ti和tj的互信息(Positive Point Mutual Information,PPMI)。作為信息論知識(shí)在統(tǒng)計(jì)學(xué)中的一種應(yīng)用,互信息可用于度量2個(gè)統(tǒng)計(jì)量之間的相互關(guān)聯(lián)程度。利用詞分布上下文語(yǔ)義相關(guān)性思想來(lái)構(gòu)建詞項(xiàng)關(guān)聯(lián)關(guān)系具體思想如下:

其中,P(ti,tj)和P(ti)的計(jì)算公式如下:

其中,n(ti,ti)表示ti和tj共同出現(xiàn)的次數(shù)。由此,可將數(shù)據(jù)集中的每一個(gè)詞項(xiàng)表示為該詞項(xiàng)的互信息向量。

2.1.1 文檔內(nèi)關(guān)聯(lián)關(guān)系

若2個(gè)詞語(yǔ)在同一篇文檔中的共現(xiàn),則這2個(gè)詞語(yǔ)具有文檔內(nèi)關(guān)聯(lián)關(guān)系。如圖1所示,詞ti和tk在d1中共現(xiàn),tj和tk在d2中共現(xiàn),則詞ti,tk和詞tj,tk分別在文檔d1和d2中具有文檔內(nèi)直接關(guān)聯(lián)關(guān)系。采用經(jīng)典余弦相似度計(jì)算公式如下:

2.1.2 文檔間關(guān)聯(lián)關(guān)系

若2篇文檔d1和d2中的詞與d1和d2共有詞共現(xiàn),則這2個(gè)詞具有文檔間關(guān)聯(lián)關(guān)系,如圖1所示,給定詞ti和tj,至少存在一個(gè)詞tk,使得詞ti與tj共現(xiàn),那么稱ti和tj是具有文檔間關(guān)聯(lián)關(guān)系的。其中詞tk稱為ti和tj的鏈接詞。計(jì)算詞ti和tj通過(guò)詞tk的文檔間關(guān)聯(lián)關(guān)系公式如下:

對(duì)所有與ti和tj共現(xiàn)的鏈接詞求和,并規(guī)范化至［0,1］之間如下:

上述公式表明2個(gè)詞的共有鏈接詞越多,表明這2個(gè)詞關(guān)系越密切,其文檔間關(guān)聯(lián)關(guān)系越大。與文檔內(nèi)關(guān)聯(lián)關(guān)系相比,文檔間關(guān)聯(lián)關(guān)系考慮了所有與其具有相似關(guān)系的鏈接詞出現(xiàn)的文檔,語(yǔ)義覆蓋面更為寬泛。

至此,文檔內(nèi)與文檔間詞語(yǔ)的關(guān)聯(lián)關(guān)系充分挖掘出詞語(yǔ)間全部的關(guān)聯(lián)關(guān)系。利用如下公式計(jì)算詞項(xiàng)間關(guān)聯(lián)詞關(guān)系:

其中,α∈［0,1］,決定了文檔內(nèi)關(guān)聯(lián)關(guān)系和文檔間關(guān)系所占比例。由上述方法得到的關(guān)聯(lián)詞關(guān)系不僅包含了共現(xiàn)詞語(yǔ)的互信息,而且包含了非共現(xiàn)詞語(yǔ)的文檔間關(guān)聯(lián)關(guān)系因此具有更為豐富的的語(yǔ)義信息。

2.2 先驗(yàn)信息的編碼

針對(duì)本文中聚類的具體應(yīng)用,must-1ink約束定義2個(gè)詞項(xiàng)必在同一類;cannot-1ink約束則限定2個(gè)詞項(xiàng)必不在同一聚類中。設(shè)定閾值,當(dāng)計(jì)算得到的詞項(xiàng)關(guān)聯(lián)關(guān)系大于給定閾值則定義其必在同一類中,而小于特定閾值則必不在同一類中?？紤]到must-1ink限制具備典型的傳遞關(guān)系,通過(guò)計(jì)算傳遞閉包將詞項(xiàng)層面上的限制進(jìn)行傳播。詞項(xiàng)的成對(duì)約束需要通過(guò)以下的方式對(duì)約束信息編碼。

假定詞項(xiàng)(wik,wjk)屬于同一類,must-link約束集合As表征所有必須在同一類的詞對(duì),記為:

類似地,cannot-link約束集合Bs記為:

將must-link約束集合As以及cannot-link約束集合Bs集成到優(yōu)化目標(biāo)函數(shù)中的可行方案是將must-link約束集合As編碼為對(duì)角線元素均為1的對(duì)稱矩陣A,類似的,cannot-link約束集合Bs則編碼為矩陣B。

將約束看作在矩陣F上詞項(xiàng)屬于各類的后驗(yàn)概率。那么一個(gè)must-link約束對(duì)(i1;j1)意味著對(duì)某個(gè)類別hi1hj1k＞0,也即需要極大化,將must-link約束表示為:

類似的處理可應(yīng)用于cannot-link約束對(duì)(i2;j2)的處理。對(duì)不同類別k,h21khj2k=0。換言之,需要極小化。因此將cannot-link約束表示為:

3 算法描述

經(jīng)典的非負(fù)矩陣分解算法［8］僅要求所分解的因子矩陣非負(fù)。本文的應(yīng)用背景中對(duì)分解的因子矩陣考慮更多的約束來(lái)得到強(qiáng)化分解的結(jié)果。一是要求分解結(jié)果正交來(lái)獲得唯一的聚類結(jié)果;二是要求增添詞項(xiàng)向量矩陣的成對(duì)約束信息。最終將融合詞項(xiàng)關(guān)聯(lián)關(guān)系的半監(jiān)督微博聚類問(wèn)題可轉(zhuǎn)化為約束優(yōu)化求解問(wèn)題,目標(biāo)函數(shù)定義為:

從優(yōu)化的角度看,式(11)表示了一個(gè)典型的優(yōu)化問(wèn)題,其中β,γ均為正數(shù),用于表示用戶先驗(yàn)信息的強(qiáng)度,參數(shù)值越大則表示先驗(yàn)知識(shí)越重要。A,B表示詞項(xiàng)間成對(duì)約束的先驗(yàn)信息。此處求F,S僅是為了輔助求G,求G是進(jìn)行學(xué)習(xí)的根本目的。

如上所述,NMF的解不具有唯一性,為避免歧義,對(duì)目標(biāo)函數(shù)定義正交約束:

對(duì)式(11)的優(yōu)化可以用以下迭代過(guò)程來(lái)求解［9］:

為計(jì)算S,優(yōu)化方程式(11),相當(dāng)于優(yōu)化:

得到更新F的函數(shù)如下:

為計(jì)算G,優(yōu)化方程式(11),相當(dāng)于優(yōu)化:

文獻(xiàn)［6］已證明了該算法的收斂性和正確性。

半監(jiān)督微博聚類算法:

輸入 詞項(xiàng)類別數(shù)目k1,微博類別數(shù)目k2,詞_微博矩陣X∈RM×N,約束矩陣A,B

輸出 F∈RM×K1,S∈RM×K1,G∈RK2×N

第2步

循環(huán):

固定S,G,應(yīng)用式(16)更新F;

固定F,G,應(yīng)用式(14)更新S;

固定F,S,應(yīng)用式(18)更新G。

4 實(shí)驗(yàn)性能與分析

4.1 數(shù)據(jù)描述

本文實(shí)驗(yàn)數(shù)據(jù)來(lái)源于微博平臺(tái)Twitter［10］與新浪微博。實(shí)驗(yàn)采集了2013年10月15日-2013年12月15日大量的微博數(shù)據(jù),通過(guò)Google趨勢(shì)查找2013年的“熱詞”得到不同的類別。對(duì)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行預(yù)處理,首先去除微博文本中的鏈接、轉(zhuǎn)發(fā)標(biāo)志、@用戶名和表情符號(hào)、簡(jiǎn)繁轉(zhuǎn)換等噪音信息之后,對(duì)其進(jìn)行分詞,去除停用詞、高頻詞和低頻詞,得實(shí)驗(yàn)數(shù)據(jù)集合。其中,分詞采用 python開(kāi)源分詞系統(tǒng)stammer,停用詞表采用新浪提供的1 028個(gè)停用詞。最后去除所有在少于10篇文檔中出現(xiàn)過(guò)的低頻詞項(xiàng),得最終表1所示的實(shí)驗(yàn)數(shù)據(jù)集合。

表1 實(shí)驗(yàn)數(shù)據(jù)統(tǒng)計(jì)信息

此外,實(shí)驗(yàn)中的詞項(xiàng)和微博的主題數(shù)目取值是按照實(shí)驗(yàn)者經(jīng)驗(yàn)來(lái)進(jìn)行主觀選取的經(jīng)驗(yàn)值,實(shí)驗(yàn)中將主題數(shù)目多次設(shè)定為不同值,得到在不同主題數(shù)目的情況下實(shí)驗(yàn)結(jié)果的對(duì)比。

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

為了驗(yàn)證本文方法的有效性,設(shè)計(jì)了2個(gè)實(shí)驗(yàn): (1)將本文方法與其他經(jīng)典算法進(jìn)行比較;(2)分析成對(duì)約束對(duì)算法的影響。比較算法選擇K-means、IT-Co-clustering、TNMF-E以及 TNMF-I為基線方法。其中,K-means算法是最經(jīng)典的聚類算法之一; IT-Co-clustering［11］是經(jīng)典的聯(lián)合聚類算法TNMF-E以及TNMF-I分別代表采用歐式距離和KL散度的三重非負(fù)矩陣分解算法。

4.2.1 聚類整體性能和比較

采用純度(Purity)、歸一化互信息(Normalized Mutual Information,NMI)和可調(diào)節(jié)約當(dāng)指數(shù) ARI (Adjusted Rand Index)［12］作為評(píng)價(jià)聚類結(jié)果的指標(biāo)。其中,純度用來(lái)刻畫整個(gè)聚類結(jié)果相對(duì)于手工分類結(jié)果的準(zhǔn)確程度。NMI是外部評(píng)價(jià)標(biāo)準(zhǔn),用來(lái)評(píng)價(jià)在一個(gè)數(shù)據(jù)集上的聚類結(jié)果與該數(shù)據(jù)集的真實(shí)劃分的相似程度。ARI則是用來(lái)刻畫一對(duì)方法的準(zhǔn)確度。

本文方法與K-means,IT-Co-clustering,TNMF-E以及TNMF-I方法分別進(jìn)行對(duì)比,結(jié)果如圖2所示。

圖2 不同算法在2個(gè)數(shù)據(jù)集上的聚類性能比較

由圖2可以看出,本文方法在純度、NMI和ARI指標(biāo)上均優(yōu)于其他4種方法。K-means僅從字面信息考慮,忽略了詞項(xiàng)間隱含的關(guān)系,導(dǎo)致所得到的詞微博矩陣非常稀疏,文檔向量并不能很好地刻畫所屬的原始文檔信息,所以算法性能最差。TNMF-E以及TNMF-I算法中三重非負(fù)矩陣分解的機(jī)制允許設(shè)置不同個(gè)數(shù)的特征詞項(xiàng)與微博類別,這與現(xiàn)實(shí)中實(shí)際應(yīng)用一致。IT-Co-clustering應(yīng)用了聯(lián)合聚類的思想算法性能好于其他3種。但是仍然沒(méi)有考慮詞項(xiàng)間的關(guān)系。本文方法不僅加入了詞語(yǔ)的互信息,而且從詞語(yǔ)的文檔間關(guān)系入手,生成的約束充分挖掘了詞項(xiàng)之間的關(guān)聯(lián)關(guān)系,克服了文本表示中沒(méi)有考慮詞項(xiàng)與上下文關(guān)系而導(dǎo)致的聚類結(jié)果不準(zhǔn)確的問(wèn)題,還大大降低了原始數(shù)據(jù)高維稀疏及傳統(tǒng)詞頻與逆文檔頻率對(duì)這類短文本區(qū)別能力差的難題。因而本文提出的算法總是優(yōu)于其他的幾種無(wú)監(jiān)督聚類方法。

4.2.2 先驗(yàn)信息對(duì)聚類的影響

為了進(jìn)一步分析先驗(yàn)信息對(duì)聚類效果的影響,本節(jié)展示調(diào)節(jié)文檔內(nèi)和文檔間詞項(xiàng)關(guān)系的因子變化對(duì)于聚類性能影響。該因子決定了文檔內(nèi)關(guān)聯(lián)關(guān)系和文檔間關(guān)系在先驗(yàn)信息生成中所占比例。取值越大表示關(guān)聯(lián)詞關(guān)系的共現(xiàn)詞語(yǔ)的互信息更為重要,反之則表示非共現(xiàn)詞語(yǔ)的文檔間關(guān)聯(lián)關(guān)系更加重要。圖3給出了在Twitter數(shù)據(jù)集上相應(yīng)的實(shí)驗(yàn)結(jié)果。

圖3 關(guān)聯(lián)關(guān)系比重α對(duì)聚類算法性能的影響

從圖3中可以看出,當(dāng)α的值從0～1逐漸增大時(shí),本文算法的在純度、NMI和ARI指標(biāo)上呈現(xiàn)出先增后減再增的變化,通常參數(shù)值在中間值時(shí)算法的性能達(dá)到最好,即詞語(yǔ)間互信息和詞語(yǔ)的文檔間關(guān)系的地位同等重要,此時(shí)既包含了同一篇文檔中詞語(yǔ)間的關(guān)系,又包含了不同文檔中詞語(yǔ)間的關(guān)系。

當(dāng)α=1,即只考慮詞語(yǔ)的文檔間關(guān)系時(shí)算法的性能優(yōu)于α=0,即只考慮詞語(yǔ)間互信息,這是因?yàn)槲⒉┑脑~匯量有限,如果僅從詞語(yǔ)在同一篇微博中的關(guān)系出發(fā)挖掘信息無(wú)法充分挖掘詞語(yǔ)間蘊(yùn)含的信息,反之在詞語(yǔ)通過(guò)關(guān)聯(lián)詞產(chǎn)生的文檔間關(guān)系中,由于可能發(fā)生的關(guān)聯(lián)詞數(shù)量較多,使得產(chǎn)生的詞語(yǔ)的微博間關(guān)系數(shù)量超過(guò)了詞語(yǔ)的互信息,因此詞語(yǔ)的微博間關(guān)系更加能夠挖掘出詞語(yǔ)間的關(guān)系,所以僅考慮文檔間關(guān)系時(shí)算法的性能略優(yōu)于僅考慮詞語(yǔ)互信息。

5 結(jié)束語(yǔ)

對(duì)海量用戶感興趣的微博進(jìn)行聚類是值得研究的問(wèn)題。針對(duì)現(xiàn)實(shí)應(yīng)用中往往存在大量無(wú)標(biāo)記數(shù)據(jù)和少量有標(biāo)記數(shù)據(jù),本文提出一種結(jié)合詞項(xiàng)上下位詞的信息詞項(xiàng)關(guān)聯(lián)關(guān)系的半監(jiān)督非負(fù)矩陣分解的聚類算法。該算法克服了微博短文本的高維稀疏問(wèn)題,通過(guò)自動(dòng)獲得微博特征詞級(jí)的約束信息來(lái)有效支持微博聚類。然而本文特征項(xiàng)的提取僅從微博內(nèi)容出發(fā),下一步研究將考慮微博用戶間關(guān)系、標(biāo)簽信息等來(lái)進(jìn)一步改進(jìn)微博聚類算法。

［1］Salton G,Wong A,Yang C S.A Vector Space Model for Automatic Indexing［J］.Communications of the ACM, 1975,18(11):613-620.

［2］Zhao W X,Jiang J,Wen J,et al.Comparing Twitter and Traditional Media Using Topic Models［C］//Proceedings of European Conference on Information Retrieval Research.Berlin,Germany:Springer,2011:545-556.

［3］Yan X H,Guo J F,Liu S H,et al.Clustering Short Text Using Ncut-weighted Non-negative Matrix Factorization［C］//Proceedings of the 21st ACM International Conference on Information and Knowledge Management.Maui,USA:ACM Press,2012:216-222.

［4］Ramage D,Dumais S T,Liebling D J.Charaterizing Microblog with Topic Models［C］//Proceedings of International AAAI Conference on Weblogs and Social Media.Washington D.C.,USA:IEEE Press,2010:234-245.

［5］Chen Y,Li Z J,Nie L Q,et al.A Semi-supervised Bayesian Network Model for Microblog Topic Classification［C］//Proceedings of 24th International Conference on Computational Linguistic.Washington D.C.,USA: IEEE Press,2012:561-576.

［6］馬慧芳,王 博.基于非負(fù)矩陣分解的雙重約束文本聚類算法［J］.計(jì)算機(jī)工程,2011,37(24):161-163.

［7］Yan X H,Guo J F,Liu S H,et al.Learning Topics in Short Texts by Non-negative Matrix Factorization on Term Correlation Matrix［C］//Proceedings of the SIAM InternationalConference on Data Mining.Austin, USA:［s.n.］,2013:145-154.

［8］Lee D D,Seung H S.Learning the Parts of Objects by Non-negative Matrix Factorization［J］.Nature,1999, 401(6755):788-791.

［9］Li T,Ding C,Zhang Y.Knowledge Transformation from Word Space to Document Space［C］//Proceedings of the 31stACM SIGIR Conf.on Research and Development in Information Retrieval.New York,USA: ACM Press,2008:187-194.

［10］馬慧芳,王 博.基于增量主題模型的微博在線事件分析［J］.計(jì)算機(jī)工程,2013,39(24):161-163.

［11］Zhao Y,Karypis G.Criterion Functions for Document Clustering,CSD:01-40［R］.University of Minnesota,2001.

［12］Dhillon I S,Mallela S,Modha D S.Information-theoretic Co-clustering［C］//Proceedings of the 9th International ACM SIGKDD Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2003:89-98.

編輯 索書志

Semi-supervised Microblog Clustering Algorithm Fused with Term Correlation Relationship

MA Huifang,JIA Meihuizi,YUAN Yuan,ZHANG Zhichang
(College of Computer Science and Engineering,Northwest Normal University,Lanzhou 730070,China)

A novel semi-supervised learning algorithm fully exploring the inner semantic information to compensate for the limited message length is presented.The key idea is to explore term correlation data,which well captures the semantic information for term weighting and provides greater context for short texts.Direct and indirect dependency weights between terms are defined to reveal the semantic correlation between terms.Must-link and cannot-link are encoded as constraints for terms.This paper formulates microblog clustering problem as a semi-supervised non-negative matrix factorization co-clustering framework,which takes advantage of knowledge of features as pair-wise constraints.Extensive experiments are conducted on two real-world microblog datasets.Experimental results show that the effectiveness of the proposed algorithm.It not only greatly reduces the labor-intensive labeling process,but also deeply exploits the hidden information from microblog itself.

microblog;term correlation relationship;pair-wise constraints;semi-supervised clustering;non-negative matrix factorization

1000-3428(2015)05-0202-05

A

TP18

10.3969/j.issn.1000-3428.2015.05.037

國(guó)家自然科學(xué)基金資助項(xiàng)目(61163039,61363058);甘肅省教育廳基金資助項(xiàng)目(2013A-016)。

馬慧芳(1981-),女,副教授、博士,主研方向:人工智能,數(shù)據(jù)挖掘,機(jī)器學(xué)習(xí);賈美惠子、袁 媛,碩士研究生;張志昌,副教授、博士。

2014-06-03

2014-07-06E-mail:mahuifang@yeah.net

中文引用格式:馬慧芳,賈美惠子,袁 媛,等.融合詞項(xiàng)關(guān)聯(lián)關(guān)系的半監(jiān)督微博聚類算法［J］.計(jì)算機(jī)工程,2015, 41(5):202-206,212.

英文引用格式:Ma Huifang,Jia Meihuizi,Yuan Yuan,et al.Semi-supervised Microblog Clustering Algorithm Fused with Term Correlation Relationship［J］.Computer Engineering,2015,41(5):202-206,212.