聶丁

湖南商學院計算機與信息工程學院，湖南長沙410205

?

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

聶丁

湖南商學院計算機與信息工程學院，湖南長沙410205

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

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

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

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

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

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

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

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

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

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

表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)鍵詞劃分到某個話題，然后對微博搜索引擎按照時間順序返回來的近幾天最新結(jié)果，再在該話題上對所有的用戶計算話題權(quán)威值（表征該用戶的話題權(quán)威性），根據(jù)此話題權(quán)威值，再一次對搜索引擎返回的搜索結(jié)果進行重排序［4］。計算步驟如圖1所示。

圖1　用戶話題權(quán)威值計算步驟圖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)威之計算方法

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

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

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

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

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

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

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

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

2.1方案概述

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

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

2.2語義相似度計算方案

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

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

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

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

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

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

2.3結(jié)果分析

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

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

3.1話題區(qū)分方法

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

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

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

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

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

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

3.2排序方案

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

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

4　結(jié)論

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

參考文獻

［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］王晟，王子琪，張銘.個性化微博推薦算法［J］.計算機科學與探索，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］時曉飛.從最小省力原則來看微博［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

文獻標識碼：A

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

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

作者簡介：聶?。?975-），男，湖南長沙人，本科，工程師，主要研究方向為計算機應用、計算機網(wǎng)絡.E-mail：diablo@hnuc.edu.cn