一種基于動(dòng)態(tài)步長(zhǎng)的微博搜索排序算法

張妍琰,姚遠(yuǎn),張娜

(河南城建學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院,河南 平頂山 467036)

?

一種基于動(dòng)態(tài)步長(zhǎng)的微博搜索排序算法

張妍琰,姚遠(yuǎn),張娜

(河南城建學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院,河南 平頂山 467036)

摘要：微博搜索主要是計(jì)算文檔與查詢?cè)~之間的相關(guān)性，通過統(tǒng)計(jì)方法確定詞量的權(quán)重，再用向量空間模型計(jì)算相關(guān)度.然而使用詞量搜索方法，搜索精度并不高，檢測(cè)到某條微博的信息含量有限，難以保證用戶查詢的關(guān)注度.針對(duì)這一問題，提出基于動(dòng)態(tài)步長(zhǎng)的微博搜索排序算法.該算法的主要實(shí)現(xiàn)過程:首先對(duì)微博已有的特征進(jìn)行分析，然后用信息熵的方法計(jì)算微博信息含量，不使用詞量為計(jì)算單位，而以詞性為單位計(jì)算微博的相關(guān)度.最后把動(dòng)態(tài)步長(zhǎng)加入到ListNet排序算法中，并用Armijo-Goldstein準(zhǔn)則對(duì)步長(zhǎng)進(jìn)行優(yōu)化.通過仿真實(shí)驗(yàn)表明，本算法排序效果更優(yōu).

關(guān)鍵詞：微博;搜索排序;ListNet算法; Armijo-Goldstein準(zhǔn)則;特征值;動(dòng)態(tài)步長(zhǎng)

0引言

微博(microblogging或microblog;又稱微博客)是一種基于用戶關(guān)系信息分享、傳播以及獲取平臺(tái)，用戶可以通過電腦、手機(jī)文字(通常少于140字)更新信息，并實(shí)現(xiàn)即時(shí)分享.微博允許任何人閱讀或者只能由用戶選擇的群組閱讀，與傳統(tǒng)博客相比，微博具有“短、靈、快”等特點(diǎn).國(guó)外微博典型代表網(wǎng)站是Twitter，巴黎分析公司Semiocast 發(fā)布消息稱截至 2012年7月1日，Twitter 用戶總數(shù)為 5.17 億[1].國(guó)內(nèi)主流的互聯(lián)網(wǎng)公司大都提供微博服務(wù)，例如新浪、騰訊、搜狐等，其中最典型的代表是新浪微博[2].截止2012年12月31日，新浪微博注冊(cè)用戶突破5.03億，增長(zhǎng)73%.2012年12月，日均活躍用戶數(shù)在4 620萬，同比增82%，其中有75%的活躍用戶通過移動(dòng)終端登錄微博.Twitter(非官方稱:推特 )是一家美國(guó)社交網(wǎng)絡(luò)(social network service)及微博客服務(wù)的網(wǎng)站，是全球互聯(lián)網(wǎng)上訪問量最大的十個(gè)網(wǎng)站之一，截至2012年3月，Twitter 共有1.4億活躍用戶，Twitter 被形容為“互聯(lián)網(wǎng)的短信服務(wù)”，與其相比，截止到2012年底Facebook的每月活躍用戶數(shù)為6億.2006年，博客技術(shù)先驅(qū)blogger創(chuàng)始人埃文·威廉姆斯(Evan Williams)創(chuàng)建了新twitter界面興公司Obvious推出了Twitter服務(wù)，支持33種語言版本，截止2014年，其年盈利額超過5億美金.研究表明:在Twitter中有31%的微博為轉(zhuǎn)發(fā)微博[4],而在新浪微博中轉(zhuǎn)發(fā)比例則高達(dá) 47.8%[5].Twitter 用戶輸入關(guān)鍵字進(jìn)行搜索，可以得到按照時(shí)間排序的微博列表[6].

文獻(xiàn)[7]中證實(shí)信息在微博網(wǎng)絡(luò)傳播過程中兩級(jí)傳播理論的存在.Twitter用戶和新用戶與在對(duì)熱門話題的喜好上有著很大的差別[8].圖片在照片分享網(wǎng)站Flickr中的傳播傳播過程可以分為3個(gè)階段:線性增長(zhǎng)期、激增期和衰亡期[9].Meij等人提出一種基于語義鏈接(semantic linking)的方法[10].Efron研究了基于標(biāo)簽(Hashtag)的微博搜索方法[11].Zhao等人探索了一種加權(quán)多元素的排序算法[12].這些微博排序算法在提取特征上創(chuàng)新度不夠，大多基于傳統(tǒng)Web方法提取特征(如微博長(zhǎng)度、TF值等)，對(duì)于基于列表學(xué)習(xí)的排序應(yīng)用上有限.上述算法最大的不足表現(xiàn)為:對(duì)于多特征微博海量數(shù)據(jù)搜索排序的適應(yīng)性和訓(xùn)練出模型的良好性沒有得到足夠的驗(yàn)證.這些特征在研究中都具有良好的表現(xiàn)[13]，但對(duì)于微博排序發(fā)揮的作用有限，微博具有與Web網(wǎng)頁(yè)不同特性[14]，需要根據(jù)微博自身特征進(jìn)行探索.因?yàn)槲⒉┑暮?jiǎn)短性和隨意性，當(dāng)微博信息含量類似，當(dāng)前的搜索算法返回的是一種列表式的搜索結(jié)果，未對(duì)用戶感興趣的內(nèi)容排序.

直接特征提取是微博特征提取的主要方法，直接特征包括微博的詞項(xiàng)長(zhǎng)度、微博中是否包括標(biāo)簽@、微博中是否包括標(biāo)簽#[15]、用戶發(fā)博文數(shù)量等，用戶權(quán)威度可以作為微博特征之一.Kwak等人研究了Twitter的拓補(bǔ)結(jié)構(gòu)和作為一個(gè)新平臺(tái)的影響力[16].Kwak等[15-16]人為了研究Twitter影響力的決定因素，他們利用PageRank算法[17]以及用戶粉絲的數(shù)量對(duì)用戶進(jìn)行排序，研究結(jié)果表明:粉絲數(shù)量不是用戶影響力的唯一決定因素.Cha等人探索了3 種影響因素:入度(即一個(gè)用戶的粉絲數(shù)量)、轉(zhuǎn)發(fā)數(shù)(即微博被轉(zhuǎn)發(fā)數(shù)量)和提及數(shù)(即提及某人名字次數(shù))[18].研究表明:在信息傳播過程中，用戶影響力與其粉絲數(shù)量呈弱相關(guān).目前的微博搜索是一種基于傳統(tǒng)網(wǎng)頁(yè)的克隆式搜索，最大的不足是沒有深度挖掘微博本身的特征，用以適用于微博的排序.

Chen等人[19]針對(duì)微博文本的海量性和話題發(fā)散性特征，提出了一種基于動(dòng)態(tài)偽相關(guān)反饋思想的微博話題提取方法.Zhang 等人[20]采用 NMF 方法進(jìn)行基于用戶關(guān)系的社區(qū)發(fā)現(xiàn)，并把 AT 模型用于興趣社區(qū)發(fā)現(xiàn)，然后在Tweets和Delicious上進(jìn)行了驗(yàn)證.Fan等人[21]提出了一種影響力擴(kuò)散模型并將其用于在線網(wǎng)絡(luò)論壇中意見領(lǐng)袖的發(fā)現(xiàn).Zhang等人[22]通過對(duì)新浪微博,研究發(fā)現(xiàn)，微博系統(tǒng)具有很強(qiáng)的名人效應(yīng).

針對(duì)上述研究，我們提出基于動(dòng)態(tài)步長(zhǎng)的微博搜索排序算法，深度分析微博中的直接特征，研究直接特征中的詞性信息量，在現(xiàn)有的ListNet排序算法基礎(chǔ)上加入動(dòng)態(tài)步長(zhǎng)，用Armijo-Goldstein準(zhǔn)則優(yōu)化動(dòng)態(tài)步長(zhǎng)，最后把改進(jìn)后的排序算法應(yīng)用于微博搜索排序中.

1微博特征的提取與建模

1.1微博特征分析微博的直接特征只需經(jīng)過簡(jiǎn)單計(jì)算或者直接提取就能夠取得，已有的研究中提取到的大部分特征都是直接特征，對(duì)直接特征進(jìn)行總結(jié)分析，得到了微博的一些直接特征:

1) 用戶權(quán)威度:通過粉絲數(shù)量和好友數(shù)量之間的比率進(jìn)行判斷.

2) 微博轉(zhuǎn)發(fā)次數(shù):轉(zhuǎn)發(fā)次數(shù)越多，說明大家對(duì)于微博內(nèi)容的興趣度越高.

3) 關(guān)鍵詞是否是話題以及關(guān)鍵詞在微博中的位置:Efron M[11]實(shí)驗(yàn)結(jié)果表明:搜索話題關(guān)鍵詞比普通詞性能效果更好.美國(guó)EE.Baxendale 調(diào)查結(jié)果顯示:段落的論題是段落首句的概率為85%，是段落末句的概率為7%[23].

4) 微博的長(zhǎng)度、微博發(fā)布時(shí)間.

5) 用戶相互關(guān)注的數(shù)量、@用戶的數(shù)量.@標(biāo)簽表明博主讓指定的用戶看見微博并評(píng)論.

6) 微博內(nèi)容包含表情的數(shù)量.豐富的表情可以吸引更多大眾的興趣度.

1.2模型的建立現(xiàn)有的微博大多只提供基于關(guān)鍵詞(字)的搜索方式，在應(yīng)用上存在一些不足，該方式的搜索引擎主要依靠全關(guān)鍵詞(字)匹配方式提升微博匹配度，如果關(guān)鍵詞(字)不恰當(dāng)則導(dǎo)致匹配度不高，微博信息返回較少或者返回海量式的微博信息(模糊匹配的結(jié)果).分析其原因可總結(jié)為3個(gè)方面:第一，簡(jiǎn)單建立在網(wǎng)頁(yè)搜索基礎(chǔ)上的克隆，這種簡(jiǎn)單的克隆方式本身缺乏對(duì)微博特征的深度挖掘，導(dǎo)致沒有合適的微博排序算法.第二，匹配方式?jīng)Q定了微博搜索引擎的結(jié)果精度，基于關(guān)鍵詞(字)匹配模式容易導(dǎo)致微博信息返回極少或返回海量微博數(shù)據(jù)(可能含有一些垃圾數(shù)據(jù)).第三，微博本身的特性，主要表現(xiàn)為簡(jiǎn)短性和隨意性，如果不同微博含有的信息內(nèi)容量大致相同，返回的搜索結(jié)果并未把用戶感興趣的內(nèi)容放置靠前，就失去了用戶的關(guān)注度.針對(duì)這3方面的原因，我們用詞性為單位計(jì)算微博的相關(guān)度.

詞性指以詞的特點(diǎn)作為劃分詞類的根據(jù)，現(xiàn)代漢語的詞可以分為實(shí)詞和虛詞兩大類，細(xì)分為12類，其中實(shí)詞包含名詞、動(dòng)詞、形容詞、數(shù)詞、量詞、代詞，虛詞包含副詞、感嘆詞、介詞、連詞、助詞、擬聲詞.在文本標(biāo)識(shí)中虛詞沒有貢獻(xiàn)，在文本分析時(shí)可以剔除沒有用處的虛詞，可采用停用詞的方式來實(shí)現(xiàn)對(duì)虛詞的消除.因此，把實(shí)詞進(jìn)行三級(jí)分類，名詞和動(dòng)詞為一級(jí)，形容詞為二級(jí)，數(shù)詞、量詞和代詞為三級(jí)，并且所占貢獻(xiàn)權(quán)重依次降低，分別用s1,s2,s3表示.

(1)

假設(shè)發(fā)布微博的數(shù)目為M，單位時(shí)間內(nèi)轉(zhuǎn)發(fā)的比例為常數(shù)，記為R，單位時(shí)間內(nèi)微博信息含量為N.在t時(shí)刻累積轉(zhuǎn)發(fā)次數(shù)的函數(shù)為y(t)，于是單位時(shí)間內(nèi)的轉(zhuǎn)發(fā)的微博數(shù)為y′(t),則在t時(shí)刻有:

R=y′(t)/y(t)

(2)

此一階微分方程的通解為:

y(t)=CeRt

(3)

其中C為常數(shù)，單位時(shí)間內(nèi)微博信息含量N是可計(jì)算的，是一個(gè)常數(shù)，于是令C=N.隨著時(shí)間的推移，微博的轉(zhuǎn)發(fā)比例將隨時(shí)間變化，設(shè)為R(t).代入公式(3)中有:y(t)=NeR(t)t

(4)

公式(4)表明:當(dāng)微博信息含量一定時(shí)，微博轉(zhuǎn)發(fā)比例越高，微博累積的數(shù)量也會(huì)增加，公眾關(guān)注度就高.或當(dāng)微博轉(zhuǎn)發(fā)比例一定時(shí)，微博信息含量越高，微博累積的數(shù)量也會(huì)增加，公眾關(guān)注度就高.

2ListNet排序算法的改進(jìn)

信息檢索常用的排序模型有BM25[24],語言模型(language model,簡(jiǎn)稱LM)[25]和PageRank[17]等.這些模型在預(yù)測(cè)未知查詢時(shí)可能會(huì)導(dǎo)致過度擬合，排序?qū)W習(xí)最顯著的特點(diǎn)能集合大量特征和判別訓(xùn)練.因此可以利用機(jī)器學(xué)習(xí)技術(shù)自動(dòng)地建立有效的排序模型[26].現(xiàn)有的排序方法主要可分為3大類:列表排序法、對(duì)排序法、點(diǎn)排序法.點(diǎn)排序法采用一對(duì)一的訓(xùn)練模型，即一個(gè)查詢對(duì)應(yīng)一個(gè)文檔進(jìn)行訓(xùn)練.對(duì)排序法是在點(diǎn)排序法的基礎(chǔ)上提出來的，它以查詢對(duì)應(yīng)的文檔作為訓(xùn)練模型，其目的是準(zhǔn)確找到輸入實(shí)體對(duì)等級(jí)的差異，這導(dǎo)致訓(xùn)練時(shí)間可能較長(zhǎng)，訓(xùn)練模型變得比較復(fù)雜.在對(duì)排序法的基礎(chǔ)上又提出了列表排序法，它以查詢對(duì)應(yīng)文檔的序列作為訓(xùn)練模型，此方法的排序性能更優(yōu).因此，我們把列表排序方法應(yīng)用到微博搜索排序中，根據(jù)微博的特征，對(duì)微博搜索進(jìn)行更好地排序.

2.1ListNet排序算法ListNet排序算法是一種典型的基于列表排序的學(xué)習(xí)方法，它定義了一種Listwise的損失函數(shù)，該損失函數(shù)用構(gòu)造模型計(jì)算得到的文檔排序和真正文檔排序之間的差異表示，ListNet排序通過最小化損失函數(shù)實(shí)現(xiàn).文獻(xiàn)[27]實(shí)驗(yàn)結(jié)果表明:ListNet 算法比基于對(duì)排序方法的 RankNet、Ranking SVM 和 RankBoost 算法具有更好的效果.ListNet算法排序主要包含以下過程:

1) 把文檔排序列表轉(zhuǎn)換成概率分布.

2) 利用梯度下降原理來構(gòu)造模型.

3) 選取交叉熵來衡量由模型訓(xùn)練出的文檔排序和真正文檔排序之間的差異.

4) 最小化這個(gè)差異值來完成排序.

ListNet算法主要使用兩個(gè)概率模型來計(jì)算損失函數(shù)組合概率[27]和Top-K概率[27].

2.1.1組合概率假設(shè)待排序的文檔數(shù)為n，用n=<π(1),π(2),…,π(n)，>表示一種排列組合，其中，π(i)表示排在第i個(gè)位置的文檔，φ(·)是一個(gè)嚴(yán)格的遞增且恒為正的單調(diào)函數(shù).則排序組合n的概率為[27]:

(5)

其中，Sπ(i)表示文檔在第i個(gè)位置的得分.組合概率的計(jì)算復(fù)雜度為O(n!)，當(dāng)文檔的數(shù)量較多時(shí)，計(jì)算量明顯變太大，所以ListNet選用了另一種概率:Top-K概率.

2.1.2Top-K概率樣本序列(j1,j2,…,jk) (k

(6)

n個(gè)文檔中排在前k個(gè)文檔(j1,j2,…,jk)的Top-K概率計(jì)算方法為[27]:

(7)

Ωk中的不同組合共有n!/(n-k)!種，這遠(yuǎn)遠(yuǎn)低于組合概率(n!種).

(8)

(9)

ListNet算法采用神經(jīng)網(wǎng)絡(luò)計(jì)算文檔的得分，選取φ(x)=exp(x)，利用梯度下降的方法實(shí)現(xiàn)最小化損失函數(shù)和更新神經(jīng)網(wǎng)絡(luò)的參數(shù)ω.ω的迭代公式如下[27]:

(10)

2.2ListNet算法的不足ListNet算法采用的是梯度下降算法，最大的不足就是收斂速度慢，因?yàn)長(zhǎng)istNet算法每迭代一次都要遍歷一次全部的樣本集，并且每次迭代過程中都需要使用復(fù)雜的梯度公式，這導(dǎo)致ListNet算法訓(xùn)練需要花費(fèi)較長(zhǎng)的時(shí)間.ListNet算法偽代碼見算法1.

算法1.ListNet算法

輸入:訓(xùn)練集{(x(1),y(1)),…,(x(n),y(n))}

輸出:神經(jīng)網(wǎng)絡(luò)模型

Begin:

初始化參數(shù)ω

fori=1 tondo{

輸入查詢q(i)的x(i)到神經(jīng)網(wǎng)絡(luò);

用當(dāng)前ω值計(jì)算得分列表z(i)(f(ω));

使用公式(10)計(jì)算梯度Δω;

更新ωk+1=ωk-α×Δω;

}//End- For

End

算法1在迭代過程中從首查詢到末查詢都需要進(jìn)行嚴(yán)格的遍歷，該算法的執(zhí)行時(shí)間直接取決于訓(xùn)練集的規(guī)模，如果訓(xùn)練集過大，這種遍歷方式就不太實(shí)用了.基于以上不足，對(duì)算法中的梯度做了改進(jìn)以降低遍歷的時(shí)間復(fù)雜度.

2.3改進(jìn)后的ListNet算法對(duì)ListNet算法的改進(jìn)主要針對(duì)梯度下降的步長(zhǎng)優(yōu)化，因此采用Armijo-Goldstein準(zhǔn)則[28]來計(jì)算.

(11)

(12)

在ListNet算法的基礎(chǔ)上，構(gòu)建一個(gè)近似的目標(biāo)函數(shù)，該目標(biāo)函數(shù)為:

f(ω)=ρω2+L(y(i),z(i))

(13)

對(duì)目標(biāo)函數(shù)求導(dǎo)得到它的梯度為:

(14)

(15)

算法2.I-LN算法

輸入:查詢和對(duì)應(yīng)的文檔集合n

輸出:神經(jīng)網(wǎng)絡(luò)模型

參數(shù):迭代次數(shù)MAX,β∈(0,1),ρ∈(0,0.5)

Begin:

初始化參數(shù)ω

formax=1ToMAXdo{

forj=1Tondo{

輸入查詢;

計(jì)算z(x(j),y(j));

用Armijo-Goldstein準(zhǔn)則計(jì)算αk;/*對(duì)步長(zhǎng)進(jìn)行優(yōu)化*/

更新ωk+1=ωk-αk×ωk;

}//End-For

}//End-For

End

3評(píng)價(jià)指標(biāo)

(16)

對(duì)于類似ListNet排序算法的搜索結(jié)果評(píng)價(jià)指標(biāo)比較很多，如常見的有ERR[29](expected reciprocal rank)、NDCG(normalized discount cumulative gain) 、 P@n (Precision at Position)和MAP (mean average precison)[30-31]等等.本仿真實(shí)驗(yàn)采用ERR作為評(píng)價(jià)指標(biāo)，因?yàn)镋RR適合計(jì)算多相關(guān)度問題[29].ERR 在計(jì)算用戶對(duì)當(dāng)前文檔的滿意度時(shí),則需要考慮之前文檔的相關(guān)性以及用戶找到該相關(guān)文檔的努力[32].ERR的計(jì)算公式如公式(16)[29]所示，其中，y∈{0,…,ymax}.當(dāng)n值增大時(shí)，ERR的值開始變小.

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

4.1驗(yàn)證性測(cè)試為了驗(yàn)證改進(jìn)后的ListNet算法準(zhǔn)確度，采用不同的樣本集進(jìn)行訓(xùn)練和測(cè)試.LETOR數(shù)據(jù)集是微軟亞洲研究院(MSRA)為了訓(xùn)練排序算法性能而設(shè)計(jì)的.本實(shí)驗(yàn)采用的數(shù)據(jù)集是LETOR4.0數(shù)據(jù)集，包含MQ2007和MQ2008.MQ2007和MQ2008以Gov2的網(wǎng)頁(yè)集作為原始數(shù)據(jù)集，每個(gè)都含有46個(gè)特征值，其中MQ2007有1 700個(gè)查詢，MQ2008有800個(gè)查詢.表1是MQ2007和MQ2008數(shù)據(jù)體的具體數(shù)據(jù)[33].

表1　MQ2007和MQ2008

在實(shí)驗(yàn)中用樣本集MQ2007和MQ2008進(jìn)行訓(xùn)練學(xué)習(xí)，用最小化損失函數(shù)使得模型的參數(shù)最優(yōu).改進(jìn)后的ListNet算法用到的參數(shù)有迭代次數(shù)MAX、β、ρ.用T1、T2分別表示MQ2007數(shù)據(jù)集和MQ2008數(shù)據(jù)集，采用組合交叉驗(yàn)證的方式求解最優(yōu)參數(shù)，驗(yàn)證方式具體為:T1為訓(xùn)練樣本集，T2為驗(yàn)證樣本集；T2為訓(xùn)練樣本集，T1為驗(yàn)證樣本集；T1和T2同時(shí)為訓(xùn)練樣本集，T1為驗(yàn)證樣本集；T1和T2同時(shí)為訓(xùn)練樣本

表2　交叉驗(yàn)證樣本集的劃分

集，T2為驗(yàn)證樣本集.總共訓(xùn)練4次，對(duì)4次訓(xùn)練的結(jié)果取平均值，以保證求解參數(shù)的可信度.樣本交叉驗(yàn)證的劃分見表2.

文獻(xiàn)[34]對(duì)β和ρ兩個(gè)參數(shù)的取值進(jìn)行了實(shí)驗(yàn)測(cè)試，當(dāng)ρ∈(0.2,0.5)和ρ∈(0.1,0.5)時(shí)實(shí)驗(yàn)結(jié)果較為理想.我們?cè)隍?yàn)證性測(cè)試過程中對(duì)ρ和ρ取值范圍和文獻(xiàn)[34]一樣，經(jīng)過反復(fù)測(cè)試對(duì)參數(shù)β和ρ取平均值實(shí)驗(yàn)效果較為理想，ListNet算

表3　算法參數(shù)設(shè)置

法和I-LN算法訓(xùn)練結(jié)果參數(shù)見表3.

4.2對(duì)比實(shí)驗(yàn)分析1) ERR值的比較

本實(shí)驗(yàn)平臺(tái)為IBM臺(tái)式機(jī)，配置為:Intel Core i7 CPU，主頻3.5 GHz，內(nèi)存4 G，操作系統(tǒng)WIN 7.首先用新浪(sina)微博進(jìn)行關(guān)鍵詞搜索，然后利用新浪提供的API工具爬取了前100條返回結(jié)果，最后分別計(jì)算他們的ERR值，結(jié)果如圖1所示.在取前10個(gè)微博的ERR值作對(duì)比分析，結(jié)果如圖2所示.由圖1和圖2可以看出，ListNet算法和I-LN算法取得的排序結(jié)果都優(yōu)于新浪搜索算法，I-LN算法明顯優(yōu)于這兩種算法.

2) 微博詞性的分析

對(duì)前10個(gè)微博中的取8個(gè)詞性進(jìn)行分析，具體有:名詞為ng、動(dòng)詞為vg、數(shù)詞為mg、形容詞為adj、量詞為qg、代詞為cg、字符串為sg、網(wǎng)址為url.分別對(duì)這8個(gè)詞性出現(xiàn)的次數(shù)統(tǒng)計(jì)，結(jié)果如圖3所示.從圖3可以看出，名詞、動(dòng)詞和數(shù)詞占有很高的比例，其他的詞性占有比例相對(duì)較少.

圖1　訓(xùn)練算法的ERR值對(duì)

圖2　前10個(gè)微博的ERR值對(duì)

圖3　微博詞性的統(tǒng)

圖4　微博詞性的權(quán)

為了進(jìn)一步檢驗(yàn)相關(guān)度，用文檔逆頻率計(jì)算微博中詞性的權(quán)重，在通過詞性的權(quán)重來計(jì)算信息熵，最后通過求解信息熵可以得到微博中的詞性信息量，信息熵的計(jì)算見公式(8)所示.從圖4可以看出，簡(jiǎn)單的名詞累積并沒含有充分的信息量，信息量不是依靠簡(jiǎn)單的詞頻累加.詞性的權(quán)重越大，信息含量也越大，微博排序越靠前，剛好驗(yàn)證了本文中的排序思想.

5總結(jié)

微博搜索一般采用詞量的搜索方法，導(dǎo)致其搜索精度并不高.我們采用了一種基于詞性權(quán)重計(jì)算微博信息量的方法，先對(duì)微博已有的特征進(jìn)行分析，把動(dòng)態(tài)步長(zhǎng)加入到基本的ListNet算法中，再用Armijo-Goldstein準(zhǔn)則對(duì)步長(zhǎng)進(jìn)行優(yōu)化.雖然本文中微博搜索排序算法具有更好地表現(xiàn)，但也存在一些不足，未對(duì)用戶的關(guān)注度進(jìn)行預(yù)測(cè)分析，這將是我們未來研究的重點(diǎn).

6參考文獻(xiàn)

[1] Sina Tech.The numbers of registered users of twitter is over 500 million:rank only second to Facebook[EB/OL].http://tech.sina.com.cn/i/m/2012-07-31/00387445367.shtml.

[2] Liu X H,Wei F R,Duan Y J,et al.Semantic search of microblogs[J].Journal of Shandong University (Natural Science),2012,47(5):39-42.

[3] PhoenixNet.The numbers of registered users of sina microblog is nearly 500 million,75% of active users login in with mobile terminals[EB/OL].http://tech.sina.com.cn/i/2012-02-06/ 15246687778.shtml.

[4] Asur S,Huberman BA,Szabó G,et al.Trends in social media:Persistence and decay[C].Adamic LA,Baeza-Yates RA,Counts S.Proc of the 5th Int’l AAAI Conf.on Weblogs and Social Media.Menlo Park:The AAAI Press,2011：434-437.

[5] Wang C X,Guan X H,Qin T,et al.Who are active? An in-depth measurement on user activity characteristics in sina microblogging[J].Proc of the GLOBECOM Piscataway:IEEE,2012:2083-2088.

[6] Nagmoti R,Teredesai A,De Cock M.Ranking approaches for microblog search[C].Proc of the 2010 IEEE/ACM Int’l Conf on Web Intelligence-Intelligent Agent Technology (WI-IAT),New York:IEEE Press,2010:153-157.

[7] Wu S,Hofman J M,Mason W A,et al.Who says what to whom on Twitter[C].Srinivasan S,Ramamritham K,Kumar A,Ravindra MP,Bertino E,Kumar R.Proc of the 20th Int’l Conf on World Wide Web,New York:ACM Press,2011:705-714.

[8] Yu L,Asur S,Huberman B A.What trends in Chinese social media[C].Proc of the 5th SNA-KDD Workshop’11 (SNA-KDD 2011),New York:ACM Press,2011:81-87.

[9] Cha M,Mislove A,Gummadi KP.A measurement-driven analysis of information propagation in the flickr social network[C].Proc of the 18th Int’l Conf on World Wide Web,New York:ACM Press,2009:721-730.

[10] Meij E,Weerkamp W,Rijke M D.Adding semantics to microblog posts[C].Adar E,Teevan J,Agichtein E,Maarek Y.Proc ofthe 5th ACM Int’l Conf on Web Search and Data Mining,New York:ACM Press,2012:563-572.

[11] Efron M.Hashtag retrieval in a microblogging environment[C].Crestani F,Maillet S M,Chen H H,Efthimiadis E N,Savoy J.Proc of the 5th ACM Int’l Conf on Web Search and Data Mining,New York:ACM Press,2012:563-572.

[12] Zhao L L,Zeng Y,Zhong N.A weighted multi-factor algorithm for microblog search[C].Zhong N,Callaghan V,Ghorbani A A,Hu B.Proc of the 7th Int’l Conf of AMT 2011,BerlSpringer-Verlag,2011:153-161.

[13] Nagmoti R,Teredesai A,De Cock M.Ranking approaches for microblog search[C].Proc of the 2010 IEEE/ACM Int’l Conf on Web Intelligence-Intelligent Agent Technology (WI-IAT),New York:IEEE Press,2010:153-157.

[14] Teevan J,Ramage D,Morris MR.#TwitterSearch:A comparison of microblog search and Web search[C].King I,Nejdl W,Li H.Proc of the 4th ACM Int’l Conf on Web Search and Data Mining,New York:ACM Press,2011:35-44.

[15] Efron M.Information search and retrieval in microblogs[J].Journal of the American Society for Information Science and Technology,2011,62(6):996-1008.

[16] Kwak H,Lee C,Park H,et al.What is Twitter,a social network or a news media[C].New York:ACM Press,2010:591-600.

[17] Lawrence P,Sergey B,Rajeev M,et al.The PageRank citation ranking:Bringing order to the web[R].Technical Report,StanfordUniversity,1999.

[18] Cha M,Haddadi H,Benevenuto F,et al.Measuring user influence in Twitter:The million follower fallacy[C].Proc of the 4th Int’l AAAI Conf on Weblogs and Social Media,Menlo Park:AAAI Press,2010:10-17.

[19] Chen Lin,Chun Lin,Lin Z Y,et al.Hybrid pseudo relevance feedback for microblog retrieval[J].Journal of Information Science,2013,39(6):773-788.

[20] Zhang Z F,Li Q D,Zeng D,et al.User community discovery from multi-relational networks[J].Decision Support Systems,2013,54(2):870-879.

[21] 樊興華,趙靜,方濱興,等.影響力擴(kuò)散概率模型及其用于意見領(lǐng)袖發(fā)現(xiàn)研究[J].計(jì)算機(jī)學(xué)報(bào),2013,36(2):360-367.

[22] 張賽,徐恪,李海濤.微博類社交網(wǎng)絡(luò)中信息傳播的測(cè)量與分析[J].西安：西安交通大學(xué)學(xué)報(bào),2013,47(4):124-130.

[23] 楊樂.基于同義詞詞林的自動(dòng)文摘系統(tǒng)的研究[D].天津：天津大學(xué),2007.

[24] Stephen R,Hugo Z,Michael T.Simple BM25extension to multiple weighted fields[C].Grossman D,Gravano L,Zhai C X,Herzog O,Evans D A.Proc of the 13th ACM Int’l Conf on Information and Knowledge Management,New York:ACM Press,2004:42-49.

[25] Gao J F,Nie J Y,Wu G Y,et al.Dependence language model for information retrieval[C].Sanderson M,Jarvelin K,Allan J,Bruza P.Proc of the 27th Int’l ACM SIGIR Conf on Research and Development in Information Retrieval,New York:ACMPress,2004:170-177.

[26] Qin T,Liu T Y,Xu J,et al.LETOR:A benchmark collection for research on learning to rank for information retrieval[J].Information Retrieval,2010,13(4):346-374.

[27] Cao Z,Qin T,Liu T Y,et al.Learning to rank:From pairwise approach to listwise approach[C].Ghahramani Z.Proc of the 24th Int’l Conf on Machine Learning,New York:ACM Press,2007:129-136.

[28] Armijo L.Minimization of functions having Lipschitz continuous first partial derivatives[J].Pacific Journal of Mathematics,1966,16(1):1-3.

[29] Chapelle O,Metzler D,Zhang Y,et al.Expected reciprocal rank for graded relevance[C].Cheung D,Song I Y,Chu W,Hu X H,Lin J.Proc of the 18th ACM Conf on Information and Knowledge.

[30] Jarvelin K,Kekalainen J.IR evaluation methods for retrieving highly relevant documents[C].management,New York:ACM Press,2009:621-630.

[31] Jarvelin K,Kekalainen J.Cumulated gain-based evaluation of IR techniques[J].Jounal of ACM Trans on Information Systems,2002,20(4):422-446.

[32] Niu S Z,Guo J F,Lan Y Y,et al.Top-k learning to rank:Labeling,ranking and evaluation[C].Hersh W,Callan J,Maarek Y,Sanderson M.Proc of the 35th Int’l ACM SIGIR Conf on Research and Development in Information Retrieval,New York:ACM Press,2012:751-760.

[33]Tie-Yan Liu,Jun Xu,Tao Qin,et al.LETOR:Benchmark Dataset for Research on Learning to Rank for Informaiton Retrival[DB/OL].LR4IR，2007.

[34] 鄭悅潔.一種基于隨機(jī)梯度下降的ListNet排序算法[D].廣州：中山大學(xué),2011.

(責(zé)任編輯趙燕)

A microblog search sort algorithm based on dynamic stepsize

ZHANG Yanyan,YAO Yuan,ZHANG Na

(Institute of Computer Science and Engineering,Henan University of Urban Construction,Pingdingshan 467036,China)

Abstract:Microblog search is mainly calculation the relevance between the document and query,these weight of words are determined by the statistical method,and the relevance degree is calculated by vector space model.However,searching by words is not enough accuracy,the information content of microblog unit detection through this method is limited,thus inadequate to show the true attention paid by users in their query.Aiming to this problem,we proposed a sort algorithm for microblog search based on dynamic stepsize.The main process of algorithm:firstly,the existing features of microblog were analyzed.Secondly,the information content of microblog were calculated by using information entropy method,words were not as the calculating unit,but calculation the relevance of microblog based on part of speech.Finally,the dynamic stepsize was introduced to the ListNet sort algorithm,and it was optimized by Armijo-Goldstein principle.The simulation experiment results show that the algorithm sort effect is better.

Key words:microblog;search sort;ListNet algorithm;Armijo-Goldstein principle; eigenvalue; dynamic stepsize

中圖分類號(hào):TP391.6

文獻(xiàn)標(biāo)志碼:A

DOI:10.3969/j.issn.1000-2375.2016.03.016

文章編號(hào):1000-2375(2016)03-0258-09

作者簡(jiǎn)介：張妍琰(1981-)，女，碩士，講師，E-mail:yanyanschool@163.com

基金項(xiàng)目：國(guó)家自然科學(xué)基金(61202248)資助

收稿日期:2015-11-18