基于LDA與WordNet方法的微博排序

聶丁

湖南商學(xué)院計(jì)算機(jī)與信息工程學(xué)院，湖南長沙410205

?

基于LDA與WordNet方法的微博排序

聶丁

湖南商學(xué)院計(jì)算機(jī)與信息工程學(xué)院，湖南長沙410205

摘要：微博搜索排序是近年來微博研究的熱點(diǎn)之一。對于任意一個(gè)話題，它內(nèi)容的生產(chǎn)者很容易達(dá)到成千上萬個(gè)，甚至更多，產(chǎn)生的微博數(shù)更是不計(jì)其數(shù)，同時(shí)，也給關(guān)鍵字搜索的微博排序提出了更大的挑戰(zhàn)。因此，本文提出了基于話題的用戶權(quán)威值計(jì)算方法、基于WordNet的內(nèi)容語義相似度方法，以及基于LDA的方法將輸入關(guān)鍵詞和所召回微博與其所屬話題相關(guān)聯(lián)，使用LearningToRank監(jiān)督學(xué)習(xí)方法，學(xué)習(xí)一種排序策略。在此基礎(chǔ)上，對提出的方案在實(shí)際數(shù)據(jù)集上分別對用戶話題權(quán)威性、微博內(nèi)容語義相似度、以及綜合排序因素進(jìn)行驗(yàn)證。

關(guān)鍵詞：微博排序；語義相似度；特征擬合

隨著微博、博客、論壇等在線社交網(wǎng)絡(luò)的應(yīng)用出現(xiàn)及迅猛發(fā)展，使得互聯(lián)網(wǎng)的使用方式發(fā)生了深刻變革。在微博等社交媒體中，用戶具有雙重身份，既是數(shù)據(jù)信息的消費(fèi)者也是數(shù)據(jù)內(nèi)容的生產(chǎn)者［1］。鑒于此，微博搜索排序，是近年來微博研究領(lǐng)域的熱點(diǎn)之一。對于如何在海量數(shù)據(jù)中挖掘出和搜索關(guān)鍵詞高相關(guān)、含有信息量大、用戶真正想要看到的微博，是非常具有現(xiàn)實(shí)性意義的，研究微博搜索排序的算法具有實(shí)用性意義［2］。

1　用戶話題權(quán)威值的計(jì)算方案

1.1數(shù)據(jù)集

1.1.1數(shù)據(jù)集評分方法本評分分為3個(gè)等級，分別為3、2、1分，其中，3分為最高等級，2分次之，1分為最低等級。對每一條微博，評分準(zhǔn)則如下：

1）如果包含信息與查詢該微博的關(guān)鍵字非常相關(guān)，且?guī)в泻芎玫男畔⒘浚稍u為3分；

2）如果包含信息與查詢該微博的關(guān)鍵字比較相關(guān)，且附帶有部分的信息量，可評為2分；

3）如果它包含的信息與查詢該微博的關(guān)鍵字相關(guān)，且基本上不包含相關(guān)信息量；或者它基本與查詢該微博的關(guān)鍵字無關(guān)，則評為1分。

1.1.2數(shù)據(jù)集評分情況由于每一個(gè)數(shù)據(jù)集的數(shù)據(jù)量大，且評分會(huì)耗費(fèi)巨大的人力和物力，本文只是對數(shù)據(jù)集名為Google和Healthcare的進(jìn)行評分，評分情況間表1。1.1.3排序評價(jià)指標(biāo)指標(biāo)NDCG是在DCG［3］的基礎(chǔ)上，進(jìn)行的一個(gè)改進(jìn)，NDCG綜合考慮微博的得分和其所處排序后的位置，適用于對不同的Query的排序評價(jià)后進(jìn)行比較。其計(jì)算方法如下：

表1　數(shù)據(jù)集Google和Healthcare的評分情況Table 1 Scores in data sets of Google and Healthcare

其中，n表示經(jīng)過重排序后的前n條微博，Gi是重排序后的微博列表的第i條微博的得分，Zn是歸一化因子，它使得NDCG的理想值為1。

1.2方案概述

本研究方案的思想是通過獲取用戶搜索關(guān)鍵詞信息，將用戶搜索關(guān)鍵詞劃分到某個(gè)話題，然后對微博搜索引擎按照時(shí)間順序返回來的近幾天最新結(jié)果，再在該話題上對所有的用戶計(jì)算話題權(quán)威值（表征該用戶的話題權(quán)威性），根據(jù)此話題權(quán)威值，再一次對搜索引擎返回的搜索結(jié)果進(jìn)行重排序［4］。計(jì)算步驟如圖1所示。

圖1　用戶話題權(quán)威值計(jì)算步驟圖Fig.1 Calculation steps of user topic authority

圖2　基于用戶話題權(quán)威值的排序步驟Fig.2 Ranking steps based on the user's authority

在此基礎(chǔ)上，提出一種基于用戶話題權(quán)威性的微博重排序方法，具體步驟如圖2所示。

1.3用戶話題權(quán)威之計(jì)算方法

1.3.1特征提取根據(jù)用戶話題權(quán)威性度量，構(gòu)建12個(gè)相應(yīng)的衡量用戶話題權(quán)威性的特征，其中，TS表示作者參與一個(gè)特定話題的程度，SS用來衡量作者微博的原創(chuàng)性程度，同時(shí)也衡量作者的話題性強(qiáng)度［5］。另外，S用來衡量作者在在這個(gè)話題上發(fā)表微博的程度，以及作者從該話題跑題到會(huì)話的程度。則，

這樣，根據(jù)此不等式，有

就求解出λ。根據(jù)經(jīng)驗(yàn)值，取λ滿足90%的用戶，其中λ用于表示用戶傾向于進(jìn)入微博會(huì)話的程度。接下來，特征RI把作者的微博被轉(zhuǎn)發(fā)的次數(shù)以及轉(zhuǎn)發(fā)作者微博用戶的個(gè)數(shù)考慮在內(nèi)，用于衡量作者微博內(nèi)容的影響力［6］。NS綜合考慮了在該話題上活躍的粉絲數(shù)與其關(guān)注的人中在該話題上活躍的數(shù)量，旨在估計(jì)在作者周圍該話題的活躍程度。對于OT21、OT41，是用來計(jì)算超鏈接以及Hashtag在作者原創(chuàng)微博中的出現(xiàn)的比率。OT3用于計(jì)算作者在其所有的n條（包括該話題上以及該話題外）微博中，所使用的單詞的重復(fù)度，其中，對于兩個(gè)單詞的集合，其相似度被定義為：

其中，si，sj是由作者的第i，第j條微博中通過去掉停用詞以及做Stem之后得到的單詞的集合，且在計(jì)算特征OT3之前，所有微博先按照時(shí)間排序，即times（si）＜times（sj）：?i＜j。觀上來講，對于一個(gè)特定的話題領(lǐng)域，在話題上用戶粉絲的比率越大，該用戶在該話題上的影響力就越大［7］。

1.3.2計(jì)算方法使用基于累積概率分布來計(jì)算每一個(gè)用戶在該話題上的權(quán)威值，即CDF_10或 CDF_12方法。對于用戶xi，其話題權(quán)威值計(jì)算公式如下：

其中，其中xi表示第i個(gè)用戶，表示用戶i在第f個(gè)特征上的值（f取值范圍為1～12），F(xiàn)f表示參數(shù)為fθ的第f個(gè)特征的累積概率分布函數(shù)在處的CDF值，m表示所用到的特征的個(gè)數(shù)。為了更好的逼近真實(shí)話題特征值，在以上話題權(quán)威值計(jì)算公式的基礎(chǔ)上又提出了一種基于加權(quán)的計(jì)算公式，即CDF_weighted方法，其話題權(quán)威值計(jì)算公式如下：

根據(jù)微博用戶權(quán)威值對微博重排序的具體流程如下：首先根據(jù)前面計(jì)算出的用戶話題權(quán)威值按照從大到小的順序?qū)τ脩襞判颍黄浯胃鶕?jù)用戶的排名順序?qū)λ阉饕娣祷氐陌凑諘r(shí)間順序排列的微博進(jìn)行重新排序，對于一個(gè)用戶多條微博的情況，微博之間按照時(shí)間先后排序；最后將重新排序的微博結(jié)果返回給用戶。

2　基于微博內(nèi)容的語義相似度計(jì)算方案

2.1方案概述

本研究方案的特點(diǎn)是，考慮微博的語義信息，并通過使用WordNet詞典來計(jì)算兩個(gè)單詞之間基于語義的相似度，并在此基礎(chǔ)上考慮單詞的重要程度，即計(jì)算TFIDF值。基于語義的內(nèi)容相似度計(jì)算方法示意圖為：

圖3　基于語義內(nèi)容相似度計(jì)算方法示意圖Fig.3 Calculation method based on semantic content similarity

2.2語義相似度計(jì)算方案

基于語義相似度的計(jì)算方法主要分為兩個(gè)步驟，即首先計(jì)算出每一對微博的語義相似度，然后每一條微博與其他所有微博的相似度由它與其他微博相似度和來表示。對于vi和vj兩條微博，即對于微博vi中的每一個(gè)單詞w：

1）在微博vj中找出一個(gè)單詞的集合Set，該集合中的每一個(gè)單詞u都滿足，它與單詞w的語義相似度大于給定閾值，即使得sim（w，u）＞?，且w∈vi，u∈vj；

2）取步驟1）中集合Set中的一個(gè)使得sim（w，u）取最大值的u；

3）在步驟2）的基礎(chǔ)上，使用TFIDF值做權(quán)重，來計(jì)算兩個(gè)單詞之間的相似度v（w，vi）*v（u，vj）*sim（w，u）；

4）將得到的兩個(gè)單詞之間的相似度相加，得到SIM（vi，vj）。

由于以上得到的這個(gè)度量不具有自反性，即SIM（vi，vj）≠SIM（vj，vi），采取以下操作：

2.3結(jié)果分析

實(shí)驗(yàn)結(jié)果表明，在沒有考慮單詞重要性的前提下，僅僅考慮語義信息，總體上來講排序性能是不理想的。同時(shí)，可以得出一個(gè)結(jié)論，基于內(nèi)容相似度的且不考慮語義信息的排序方法性能都不理想。綜上所述，本研究課題提出的基于微博主題重要性的語義相似度計(jì)算方案在排序性能上總體優(yōu)于僅僅考慮一方面即只考慮單詞的重要性即基于TFIDF的方法，或者只考慮語義信息的排序方案。

3　對話題敏感的排序方案實(shí)現(xiàn)及分析

3.1話題區(qū)分方法

本話題區(qū)分方法使用LDA文檔主題模型實(shí)現(xiàn)，實(shí)現(xiàn)思想是首先判定微博搜索詞所屬話題，然后再根據(jù)微博搜索詞所屬話題將搜索引擎召回的微博在該話題上的分布情況進(jìn)行判定，其實(shí)現(xiàn)主要步驟為：

1）隨機(jī)選取數(shù)據(jù)集中3/4的數(shù)據(jù)作為訓(xùn)練集用于訓(xùn)練LDA模型；

2）使用LDA訓(xùn)練模型對搜索關(guān)鍵詞和其余1/4的數(shù)據(jù)集進(jìn)行推斷（即Inference）操作，得到搜索關(guān)鍵詞及測試集中每一條微博在所有話題上的概率分布；

3）求搜索關(guān)鍵詞在所有話題上分布的最大值，并將其話題編號求出；

4）根據(jù)步驟3）所求得的話題編號，對所有被搜索引擎召回的微博取其在該話題上的分布概率值，并進(jìn)行歸一化。

將上述步驟最終得到的向量作為微博排序的一個(gè)特征，將其稱為話題關(guān)聯(lián)特征，作為微博排序的一個(gè)因素。

3.2排序方案

本文采用基于統(tǒng)計(jì)的Learning To Rank即排序?qū)W習(xí)方法對微博進(jìn)行排序，其中使用9個(gè)特征，即＜用戶話題權(quán)威值，微博內(nèi)容相似度，時(shí)間相近性，轉(zhuǎn)發(fā)次數(shù)，微博長度，超鏈接數(shù)量，標(biāo)簽數(shù)量，@數(shù)量，關(guān)鍵詞與微博的話題關(guān)聯(lián)性＞。這些特征主要可以分為三個(gè)維度，即用戶維度、微博內(nèi)容維度以及微博自身維度，如圖4所示。

圖4　排序方案圖解Fig.4 Ranking steps

4　結(jié)論

針對現(xiàn)有微博搜索排序的不足，本文針對用戶權(quán)威值的計(jì)算方面，提出基于話題的用戶權(quán)威值計(jì)算方法。綜合考慮用戶話題權(quán)威性以及傳統(tǒng)的權(quán)威度量，提出了最終的話題權(quán)威值計(jì)算公式。針對現(xiàn)有微博內(nèi)容相似度計(jì)算方案的不足，本文提出了基于單詞重要性的語義相似度計(jì)算方案。該語義相似度計(jì)算方案首先考慮單詞之間的語義相似性，在此基礎(chǔ)上再考慮單詞的重要性。對于提出的以上兩個(gè)研究方案，本文對它們分別從理論可行性和現(xiàn)實(shí)可行性兩方面進(jìn)行了分析，并與已有的研究方案進(jìn)行比較，從實(shí)驗(yàn)的角度證明了所提方案的排序性能的高效性。最后，考慮到搜索關(guān)鍵詞和所召回微博之間的話題相關(guān)性，提出基于LDA的話題區(qū)分方法，將搜索關(guān)鍵詞及微博關(guān)聯(lián)起來，并作為一個(gè)排序特征，應(yīng)用到基于排序?qū)W習(xí)的框架中，通過與基準(zhǔn)的排序方案相比較，從實(shí)驗(yàn)的角度證實(shí)了所提特征的有效性。

參考文獻(xiàn)

［1］Blei DM，Ng AY，Jordan MI. Latent dirichlet allocation［J］. Journal of machine Learning research，2003（3）：993-1022

［2］Griffiths TL，Steyvers M. Finding scientific topics［J］. Proceedings of the National academy of Sciences of the United States of America，2004，101（S1）：5228-5235

［3］王晟，王子琪，張銘.個(gè)性化微博推薦算法［J］.計(jì)算機(jī)科學(xué)與探索，2012，6（10）：895-902

［4］Friedman JH. Stochastic gradient boosting［J］. Computational Statistics & Data Analysis，2002，38（4）：367-378

［5］Mahinthan V，Rutagemwa H，Mark JW，et al. Cross-layer performance study of cooperative diversity system with ARQ［J］. IEEE Transactions on Vehicular Technology，2009，58（2）：705-719

［6］Resnik P. Semantic similarity in a taxonomy：An information-based measure and its application to problems of ambiguity in natural language［J］. Sensor Fusion & Decentralized Control in Robotic Systems Ш，2011，11（1）：95-130

［7］時(shí)曉飛.從最小省力原則來看微博［J］.才智，2014（1）：309

Ranking Sensitive Topics in a Micro-blog Based on LDAand WordNet Method

NIE Ding
School of Computer and Information Engineering/Hunan University of Commerce，Changsha 410205，China

Abstract：Microblog ranking is one of the hot research area in recent years. For any one topic，it is easy to reach thousands of producers or even more，the number of micro-blogs is countless，but also it comes with a greater challenge during searching keywords in micro-blog. In view of this，we proposed to incorporate topical authority of user，content similarity based on WordNet and topical relevance based on LDA algorithm between search keywords and microblogs that recalled to enhance the performance of microblog ranking with learning to rank related algorithm. On this basis，the user's topic authority，micro-blog content semantic similarity as well as the integrated ranking factors in a proposed project were verified on the actual data set.

Keywords：Microblog ranking；semantic similarity；feature fitting

中圖法分類號：TP391.3

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號：1000-2324（2016）03-0469-04

收稿日期：2016-03-12修回日期：2016-04-28

作者簡介：聶丁（1975-），男，湖南長沙人，本科，工程師，主要研究方向?yàn)橛?jì)算機(jī)應(yīng)用、計(jì)算機(jī)網(wǎng)絡(luò).E-mail：diablo@hnuc.edu.cn