張森， 張晨,， 林培光， 張春云，郭玉超， 任威龍，任可

(1.山東財(cái)經(jīng)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山東 濟(jì)南 250014；2. 香港科技大學(xué) 計(jì)算機(jī)科學(xué)及工程學(xué)系，香港 999077)

基于用戶查詢?nèi)罩镜木W(wǎng)絡(luò)搜索主題分析

張森1， 張晨1,2， 林培光1， 張春云1，郭玉超1， 任威龍1，任可2

(1.山東財(cái)經(jīng)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山東 濟(jì)南 250014；2. 香港科技大學(xué) 計(jì)算機(jī)科學(xué)及工程學(xué)系，香港 999077)

網(wǎng)絡(luò)搜索分析在優(yōu)化搜索引擎方面具有舉足輕重的作用，而且對用戶個(gè)人搜索特性進(jìn)行分析能夠提高搜索引擎的精準(zhǔn)度。目前，大多數(shù)已有模型(比如點(diǎn)擊圖模型及其變體)，注重研究用戶群體的共同特點(diǎn)。然而，關(guān)于如何做到既可以獲取用戶群體共同特點(diǎn)又可以獲取用戶個(gè)人特點(diǎn)方面的研究卻非常少。本文研究了基于個(gè)人用戶網(wǎng)絡(luò)搜索分析新問題，即通過研究用戶搜索的突發(fā)性現(xiàn)象，獲取個(gè)人用戶搜索查詢的主題分布情況。提出了兩個(gè)搜索主題模型，即搜索突發(fā)性模型(SBM)和耦合敏感搜索突發(fā)性模型(CS-SBM)。SBM假設(shè)查詢詞和URL主題是無關(guān)的，CS-SBM假設(shè)查詢詞和URL之間是有主題關(guān)聯(lián)的，得到的主題分布信息存儲在偏Dirichlet先驗(yàn)中，采用Beta分布刻畫用戶搜索的時(shí)間特性。實(shí)驗(yàn)結(jié)果表明，每一個(gè)用戶的網(wǎng)絡(luò)搜索軌跡都有多種基于用戶的獨(dú)有特點(diǎn)。同時(shí)，在使用大量真實(shí)用戶查詢?nèi)罩緮?shù)據(jù)情況下，與LDA、DCMLDA、TOT相比，本文提出的模型具有明顯的泛化性能優(yōu)勢，并且有效地描繪了用戶搜索查詢主題在時(shí)間上的變化過程。

網(wǎng)絡(luò)搜索；搜索引擎；自然語言處理；主題模型；文本挖掘；突發(fā)性；時(shí)間分析；參數(shù)估計(jì)

1931年，Zipf[1]發(fā)現(xiàn)在自然語言中，詞的頻率與它在詞匯表中的排名成反比，服從冪律分布，他把這種現(xiàn)象稱為上下文語言模型中詞的突發(fā)性。后來發(fā)現(xiàn)，在金融、基因表達(dá)、計(jì)算機(jī)視覺等方面的數(shù)據(jù)也存在這種突發(fā)現(xiàn)象。網(wǎng)絡(luò)搜索已成為人們?nèi)粘Ｉ钪斜夭豢缮俚囊徊糠郑脩籼峤坏乃阉鞑樵冊~是人類智慧的結(jié)晶，并在搜索查詢和微博等網(wǎng)絡(luò)信息中顯現(xiàn)出與傳統(tǒng)的自然語言不同的特點(diǎn)，網(wǎng)絡(luò)搜索中每一個(gè)用戶的搜索條目都包括查詢詞和URL兩項(xiàng)。已經(jīng)提出的Dirichlet Compound Multinomial (DCM)模型[2]和Dirichlet Compound Multinomial Latent Dirichlet Allocation (DCMLDA)模型[3]可以對文章中詞的突發(fā)性現(xiàn)象建模，但如果直接應(yīng)用于網(wǎng)絡(luò)搜索建模卻不是很理想。雖然大多數(shù)的點(diǎn)擊圖模型[4]及其變體[5-6]可以對網(wǎng)絡(luò)搜索建模，但都是針對用戶群體進(jìn)行研究而忽略了用戶個(gè)人特點(diǎn)。

本文通過分析用戶查詢?nèi)罩緛慝@取網(wǎng)絡(luò)搜索突發(fā)現(xiàn)象，并提出了兩個(gè)模型：SBM(search burstiness model)和CS-SBM(coupling-sensitive search burstiness model)。SBM是一個(gè)單極模型，假設(shè)查詢詞和URL之間主題獨(dú)立，突發(fā)性的相關(guān)信息存儲在偏Dirichlet先驗(yàn)里。CS-SBM充分考慮查詢詞和URL之間的關(guān)聯(lián)。本文還用Beta分布刻畫了用戶搜索的時(shí)間特性，使前面提出的模型能夠用來捕獲時(shí)間上的突發(fā)性。

1 相關(guān)工作

Madsen指出，多項(xiàng)分布經(jīng)常用于文本建模。然而，多項(xiàng)分布能獲取到文檔中詞匯的突發(fā)性現(xiàn)象，即一個(gè)詞如果出現(xiàn)過一次，那么它很有可能再次出現(xiàn)[7]。因此Madsen提出了Dirichlet多項(xiàng)分布(DCM)來代替?zhèn)鹘y(tǒng)的多項(xiàng)分布。DCM擁有一級自由度，能獲取到詞的突發(fā)性，但是沒有涉及文檔中詞匯的主題。文獻(xiàn)[2]將DCM模型擴(kuò)展成為了混合DCM分布，該模型能夠訓(xùn)練表示一組文檔，其中每一個(gè)文檔都來自不同的高級主題。但是，該模型還是不能建模一個(gè)文檔包含多個(gè)主題單詞的情景。

上述工作中，之所以不能很好地刻畫文檔主題，其主要原因是DCM更關(guān)注突發(fā)性現(xiàn)象而非獲取文檔主題。2003年Blei[8]提出的Latent Dirichlet Allocation (LDA) 是非監(jiān)督的貝葉斯生成模型，它可以將文檔集中每篇文檔的主題按照概率分布的形式給出。LDA包括詞匯、主題和文檔3層。LDA引入了Dirichlet先驗(yàn)分布，成為了一個(gè)完備的貝葉斯模型。LDA文檔生成過程為，從Dirichlet分布中采樣文檔與主題、主題與詞匯分布，再重復(fù)從文檔-主題多項(xiàng)式分布中采樣主題以及由主題-詞匯多項(xiàng)式分布生成詞匯的過程，逐步生成整個(gè)文檔。LDA已經(jīng)在學(xué)術(shù)和工業(yè)界得到廣泛應(yīng)用。但是，LDA模型并不能預(yù)測詞匯突發(fā)性出現(xiàn)的趨勢。

為了能夠在獲取主題的同時(shí)預(yù)測詞匯突發(fā)性現(xiàn)象，G.Doyle[3]提出了DCMLDA主題模型，該模型結(jié)合了DCM和LDA的優(yōu)勢，直接將DCM擴(kuò)展合并到主題模型里面形成了一個(gè)比LDA更加復(fù)雜的模型。在DCMLDA中對于每個(gè)主題k和每個(gè)文檔d服從新的多項(xiàng)式分布θkd，每個(gè)主題k都有不同的、非均勻的βk向量。對于每一個(gè)文檔d,φkd根據(jù)Dirichlet(βk)的變化而變化，因此每個(gè)主題實(shí)例在文檔之間是相互聯(lián)系的。文檔中的主題實(shí)例允許在同一主題不同文檔中每一個(gè)詞匯的概率不同，這也就是突發(fā)現(xiàn)象。

隨著帶有時(shí)間標(biāo)記的文本集合(例如，數(shù)字化的報(bào)紙、雜志、博客等)數(shù)量和體積的增加，如何有效地搜索這些數(shù)據(jù)變得更加重要。上述模型都難以發(fā)現(xiàn)主題的演化趨勢。在這個(gè)背景下，文獻(xiàn)[9]等提出了Topic Over Time(TOT)模型。TOT將文檔的時(shí)間信息作為服從Beta分布的變量，將每個(gè)主題通過Beta分布與時(shí)間信息相關(guān)聯(lián)。TOT假設(shè)每個(gè)生成的詞匯對應(yīng)的時(shí)間信息也是通過它所屬主題相關(guān)的Beta分布采樣生成，這樣主題與時(shí)間信息也有關(guān)系。TOT不依賴馬爾可夫假說，這樣能夠避免在離散化過程中遇到時(shí)間粒度選取的問題。

另外，文獻(xiàn)[10]系統(tǒng)地總結(jié)了自然語言處理中主題模型的發(fā)展，對LDA模型進(jìn)行了詳細(xì)的分析，并對主題模型的發(fā)展趨勢進(jìn)行了預(yù)測。根據(jù)微博的特殊形式，在LDA的基礎(chǔ)上進(jìn)行了改進(jìn)，分別提出了(MicroBlogs-LDA)MB-LDA模型[11]和(MicroBlogs-HDP)MB-HDP模型[12]，同時(shí)證明了提出模型能夠很好地對微博進(jìn)行主題挖掘。

以前的工作都是集中在對自然語言文本中的同質(zhì)項(xiàng)目進(jìn)行分析，即對一個(gè)文檔中的同質(zhì)詞匯進(jìn)行建模。然而在網(wǎng)絡(luò)搜索分析中，文檔是由查詢詞和URL兩個(gè)異構(gòu)項(xiàng)目組成，并且?guī)в袝r(shí)間信息。因此，本文結(jié)合網(wǎng)絡(luò)搜索查詢的文本特點(diǎn)，提出并研究了將主題模型運(yùn)用到網(wǎng)絡(luò)搜索分析中，對查詢詞和URL這兩個(gè)異構(gòu)項(xiàng)目和它們之間的關(guān)系進(jìn)行建模。

2 以用戶為中心的概率主題模型

本節(jié)主要介紹了SBM和CS-SBM主題模型，以及獲取主題時(shí)間突發(fā)性的策略。

提出的模型應(yīng)具備以下條件：

1)查詢詞和URL的突發(fā)性現(xiàn)象研究要分開建模[13]。

2)建模時(shí)，網(wǎng)絡(luò)搜索特點(diǎn)，包括查詢詞、URL和session 3個(gè)維度都要考慮在內(nèi)[14-15]。

session是指在短時(shí)間內(nèi)提交的滿足相同信息需求的一系列查詢。為了避免同一會(huì)話中包含不相干的查詢而導(dǎo)致的性能降低，本文優(yōu)先考慮同一會(huì)話中查詢詞之間的語義一致性。通過對比分析，本文采用文獻(xiàn)[16]提出的一系列規(guī)則來劃分搜索session。這些規(guī)則用于評估查詢之間的詞匯相似性，并在檢測相關(guān)搜索查詢時(shí)表現(xiàn)出很高精度。

2.1 查詢詞和URL獨(dú)立的主題模型(SBM)

SBM的生成過程是基于查詢詞和URL相互獨(dú)立的假設(shè)。與LDA和DCMLDA等傳統(tǒng)主題模型不同，SBM中的文檔有查詢詞、被點(diǎn)擊URL和查詢時(shí)間三項(xiàng)。圖1是SBM的搜索主題模型概率圖。首先，從超參數(shù)為α的Dirichlet分布中抽樣生成文檔與主題之間的關(guān)系矩陣θ，θ是一個(gè)D×K的矩陣，其中D代表文檔數(shù)量，K代表主題數(shù)。對于每一個(gè)主題k，從超參為βk和δk的Dirichlet分布中分別取樣生成查詢詞與主題之間的關(guān)系矩陣θ和URL與主題之間的關(guān)系矩陣Ω。θ和Ω是D×K×V的三維矩陣，V代表訓(xùn)練語料庫中出現(xiàn)的所有詞的詞表。對于文檔中的每一個(gè)session，從參數(shù)為θd的多項(xiàng)分布中選擇一個(gè)主題z，從參數(shù)為φzd的查詢詞的多項(xiàng)分布中，采樣生成查詢詞w。然后，生成點(diǎn)擊事件的二項(xiàng)分布，如果URL被點(diǎn)擊了，從參數(shù)為Ωzd的URL的多項(xiàng)分布中，采樣生成URLu。變量θ和δ是基于單個(gè)特定文檔的，因此SBM可以為每一個(gè)用戶查詢詞和URL的突發(fā)性建模。

圖1 SBM網(wǎng)絡(luò)搜索分析主題模型Fig.1 SBM web search analysis topic model

SBM中的Gibbs采樣方法借鑒了LDA和DCMLDA中Gibbs采樣的方法，并進(jìn)行了推導(dǎo)。模型的完全似然函數(shù)為

P(w,u,z|α,β,δ)=P(u|z,δ)P(w|z,β)P(z|α)

展開上式中的多項(xiàng)分布和Dirichlet分布，利用多項(xiàng)分布和Dirichlet分布的共軛性質(zhì)，分別積分掉參數(shù)θ和φ以后，通過借鑒LDA和DCMLDA中Gibbs采樣的方法，在SBM中概率P(z|α)為

式中ndz為第d個(gè)文檔中主題z的數(shù)量。

概率P(w|z,β)為

式中ndkw為第d個(gè)文檔中第k個(gè)主題下查詢詞w的個(gè)數(shù)。

當(dāng)該session中沒有URL被點(diǎn)擊時(shí)的條件概率為

當(dāng)一個(gè)session中有URL被點(diǎn)擊時(shí)的條件概率為

2.2 查詢詞和URL相關(guān)聯(lián)的主題模型(CS-SBM)

查詢詞和URL通過搜索引擎緊密地結(jié)合在一起，這使得本文研究的問題變得更加復(fù)雜。被點(diǎn)擊的URL是由對應(yīng)的查詢詞經(jīng)過搜索得出的。在網(wǎng)絡(luò)搜索的情境中，URL是提交查詢詞給搜索引擎后返回的結(jié)果。因此，URL和查詢詞是相關(guān)的。為了獲取它們兩者之間的關(guān)系，這里引入變量Δqku來代表“查詢詞-URL”的多項(xiàng)分布，其先驗(yàn)由δ表示?！安樵冊~-URL”多項(xiàng)式通過目前已經(jīng)被廣泛采用的點(diǎn)擊圖來獲得，點(diǎn)擊圖由搜索查詢和被點(diǎn)擊的URL兩部分組成。用于表示全局部分的CS-SBM定義為CS-SBM-G。因?yàn)楸疚闹攸c(diǎn)研究以單個(gè)用戶為核心的信息能否增強(qiáng)主題模型的表現(xiàn)，所以基于單個(gè)用戶 “查詢詞-URL”多項(xiàng)分布的CS-SBM定義為CS-SBM-U。

圖2給出了CS-SBM的生成過程。與SBM相比，查詢詞的生成過程不變，兩者最主要的區(qū)別在于，CS-SBM在URL生成的時(shí)候要考慮查詢詞的影響，對于session中每一個(gè)查詢項(xiàng)q，首先生成點(diǎn)擊事件的二項(xiàng)分布，如果URL被點(diǎn)擊了，則從參數(shù)為Ωqz的URL多項(xiàng)分布中采樣生成URLu。

圖2 CS-SBM網(wǎng)絡(luò)搜索分析主題模型Fig.2 CS-SBM web search analysis topic model

模型的完全似然函數(shù)為

P(w,u,z|α,β,δ)=P(u|z,w,δ)P(w|z,β)P(z|α)

在CS-SBM中，同樣采用了與LDA類似的Gibbs采樣方法。P(z|α)和P(w|z,β)都與SBM中的相同。兩者主要的區(qū)別就是給定的主題中的w和u不再相互獨(dú)立。u的生成過程可能受到主題z和相關(guān)搜索查詢q的影響。

P(u|z,w,δ)=

式中，nqzu是第z個(gè)主題的第q個(gè)查詢中的URLu的數(shù)量。

當(dāng)session中沒有URL被點(diǎn)擊時(shí)的條件概率為

P(zi=k|Xi=0,z-i,w,u,α,β,δ,Ψ)∝

當(dāng)session中有URL被點(diǎn)擊時(shí)的條件概率為

P(zi=k|Xi=1,z-i,w,t,u,α,β,δ,Ψ)∝

2.3 主題在時(shí)間上的突發(fā)性

網(wǎng)絡(luò)搜索中另一個(gè)常見現(xiàn)象就是時(shí)間上的突發(fā)性。一個(gè)用戶更傾向于在一個(gè)很短的時(shí)間內(nèi)集中查詢一些內(nèi)容。因此，本文假設(shè)每一個(gè)用戶的查詢軌跡都有一個(gè)時(shí)間上的突發(fā)性，這種突發(fā)性由與查詢相關(guān)的時(shí)間戳來體現(xiàn)。因?yàn)闀r(shí)間粒度是很難設(shè)定的，所以本文采用TOT中提出的方法，使用連續(xù)的Beta分布來捕獲主題時(shí)間上的突發(fā)性。通過引入Beta分布，使一個(gè)主題能夠更容易在一個(gè)短的時(shí)間周期內(nèi)出現(xiàn)。在這種情況下，本文從整個(gè)語料庫級別(定義為X-TG)和基于單一用戶級別(定義為X-TU)出發(fā)，刻畫一個(gè)主題在時(shí)間上的變化趨勢。

因?yàn)橹黝}-周期的多項(xiàng)分布是固定的(對每一個(gè)用戶而言)，所以主題中存在的時(shí)間周期將會(huì)證明突發(fā)性。每天或者每小時(shí)都可以觀察到突發(fā)性現(xiàn)象，這表明去離散化是更合適的。

下面是SBM和CS-SBM在添加了時(shí)間信息以后的模型算法。

the same as the original model

for each sessionsinddo

choose a topicz：Multinomial(θd);

generate timestampst～Beta(τz)(X-TG) or

t：Beta(τzd) (X-TU);

the same as the original model

end for

它主要的變化在于，對文檔中的每一個(gè)session，從參數(shù)為θd的多項(xiàng)分布中采樣一個(gè)主題z，然后根據(jù)數(shù)據(jù)集的不同，從Beta分布Beta(τz)和Beta(τzd)分別生成基于全局的時(shí)間戳和基于特定用戶的時(shí)間戳。

TS-SBM的Gibbs采樣與LDA方法類似。本文給出了一些簡單的推導(dǎo)。首先，模型的完全似然函數(shù)為

P(w,u,t,z|α,β,δ,τ)=P(t|z,τ)P(u|z,δ)·

P(w|z,β)P(z|α)

如果session中沒有URL被點(diǎn)擊，那么此時(shí)的條件概率是：

P(zi=k|Xi=0,z-i,w,u,α,β,δ,τ)∝

式中：τdk1和τdk2是Beta分布的超參數(shù)。

對于SBM模型，如果session中有URL被點(diǎn)擊，此時(shí)的條件概率為

P(zi=k|Xi=1,z-i,w,u,α,β,δ)∝

對于CS-SBM模型，當(dāng)session中有URL被點(diǎn)擊時(shí)的條件概率為

P(zi=k|Xi=1,z-i,w,t,u,α,β,δ,Ψ)∝

時(shí)間的參數(shù)按照如下方法更新:

3 參數(shù)估計(jì)

關(guān)于超參數(shù)α和β設(shè)置問題，一些LDA應(yīng)用采用默認(rèn)相同值的方法獲得了成功，例如由Griffiths和Steyers[17]提出的α=50/k，β=0.01，K是主題的數(shù)量。因此，在LDA中沒有必要去研究超參數(shù)。然而，在本文提出的模型中，超參數(shù)的設(shè)置是至關(guān)重要的。因?yàn)長DA中的φ和Ω值，也被包括在SBM和CS-SBM的β和δ中。

SBM完全似然P(w,u,z|α,β,δ)的計(jì)算如下所示：

P(w,u,z|α,β,δ)=

CS-SBM完全似然P(w,u,z|α,β,δ)的計(jì)算如下所示：

P(w,u,z|α,β,δ)=

SBM-T完全似然P(w,u,z|α,β,δ)的計(jì)算如下所示：

P(w,u,z|α,β,δ)=

CS-SBM-T完全似然P(w,u,z|α,β,δ,τ)的計(jì)算如下所示：

P(w,u,z|α,β,δ,τ)=

進(jìn)行對數(shù)似然轉(zhuǎn)換:

對于SBM：

對于CS-SBM：

上面的每一個(gè)公式無論α.′、β.k′還是δ.k′、δ.q′都定義了一個(gè)向量。本文采用文獻(xiàn)[18]中提出的有限空間的BFGS方法使它最大化。運(yùn)行Gibbs采樣，然后選擇α、β和δ使P(w,u,z|α,β,δ,τ)完全似然最大化，直到達(dá)到穩(wěn)定狀態(tài)。重復(fù)上述過程，直到α、β和δ收斂。

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

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

本文選擇的實(shí)驗(yàn)數(shù)據(jù)是搜狗搜索發(fā)布的匿名查詢?nèi)罩?。它是搜狗在網(wǎng)上公開發(fā)布的用戶查詢?nèi)罩?。該日志包括了用?008年6月整月的網(wǎng)絡(luò)查詢記錄。日志主要包括5部分，即用戶匿名ID、查詢詞、查詢時(shí)間、點(diǎn)擊的URL的排名、點(diǎn)擊的URL。這些數(shù)據(jù)是按照匿名用戶的ID順序依次排列的。本文選取了在一個(gè)月內(nèi)查詢?nèi)罩緱l目大于500條的用戶進(jìn)行建模。首先，將同一用戶的搜索查詢?nèi)罩痉诺揭粋€(gè)文檔中。然后，用文獻(xiàn)[16]提出的方法將搜索查詢?nèi)罩厩蟹殖闪?47 164個(gè)session，用于下一步搜索主題的發(fā)現(xiàn)。接下來，根據(jù)文獻(xiàn)[16]提出的停用詞列表過濾掉那些沒有意義的查詢詞。同時(shí)，例如www.sougou.com、www.baidu.com等主要的搜索引擎和門戶網(wǎng)站也要過濾掉[19]，因?yàn)樗鼈儧]有提供有用信息。每一個(gè)文檔的時(shí)間戳是由搜索日志上提供的查詢時(shí)間決定的，并且根據(jù)文獻(xiàn)[20]提出的SSTM模型中用到的方法，將時(shí)間按照先后順序歸一化到(0,1)。實(shí)驗(yàn)數(shù)據(jù)中，每一個(gè)文檔都包括了一些session，每一個(gè)session都包括一些查詢詞、URL(如果有點(diǎn)擊事件)和時(shí)間戳。

本文選用了兩個(gè)衡量標(biāo)準(zhǔn)。第1個(gè)衡量標(biāo)準(zhǔn)是用部分Held-Out數(shù)據(jù)評估模型預(yù)測未知數(shù)據(jù)的能力。第2個(gè)衡量標(biāo)準(zhǔn)，本文參照了文獻(xiàn)[21]提出的方法，即在觀察部分用戶搜索記錄以后，預(yù)測剩余查詢項(xiàng)的能力。兩個(gè)衡量標(biāo)準(zhǔn)都選擇了困惑度作為評估模型泛化能力的衡量指標(biāo)。一般而言，模型的困惑度越低，表明泛化能力越強(qiáng)，對模型的擬合程度越高。由于很少有概率模型做有關(guān)獲取網(wǎng)絡(luò)搜索查詢突發(fā)性和時(shí)間上的主題突發(fā)性研究，很難找到提出模型的直接競爭對手。所以本文選取了3個(gè)常用的主題模型作為比較基線，即LDA、DCMLDA和TOT。

4.2 模型困惑度分析

對于第一個(gè)衡量標(biāo)準(zhǔn)，困惑度義如下：

式中，M是模型通過訓(xùn)練過程學(xué)習(xí)到的，Nd是指第d個(gè)文檔中詞匯數(shù)量。圖3展示了困惑度的比較結(jié)果，從中可以發(fā)現(xiàn)這兩個(gè)提出的模型與3個(gè)基線模型相比表現(xiàn)出了更好的預(yù)測未知數(shù)據(jù)的能力。因此，把搜索主題數(shù)設(shè)置為1 000時(shí)，SBM、CS-SBM、LDA、DCMLDA、TOT的困惑度分別為430.347、400.16、1 080.41、995.76、830.23。SBM和CS-SBM自身的困惑度低，并且隨著主題數(shù)增加困惑度還會(huì)進(jìn)一步降低。實(shí)驗(yàn)結(jié)果表明，SBM和CS-SBM更適合于從給予的用戶搜索歷史中預(yù)測用戶未來網(wǎng)絡(luò)搜索查詢。

圖3 Held-out 數(shù)據(jù)的困惑度Fig.3 Perplexity of held-out data

第2種衡量標(biāo)準(zhǔn)的困惑度為

Perplexityportion(M)=

第2種衡量標(biāo)準(zhǔn)可以評估提出的模型在觀察一部分用戶搜索歷史記錄以后，預(yù)測剩余查詢項(xiàng)的能力。例如，從用戶的查詢?nèi)罩局械玫揭呀?jīng)觀察的查詢詞w1:P，那么剩余查詢項(xiàng)的預(yù)測分布為P(w|W1:P)。測試數(shù)據(jù)的困惑度是根據(jù)上面的困惑度公式進(jìn)行計(jì)算。舉例來說，選擇數(shù)據(jù)集中前80%的搜索查詢詞作為觀察訓(xùn)練數(shù)據(jù)，剩余的20%作為測試數(shù)據(jù)。圖4呈現(xiàn)了部分觀察數(shù)據(jù)的預(yù)測困惑度，LDA、DCMLDA、TOT的困惑度分別是684.83、671.09、561.26。本文中提出的模型再次取得了顯著的優(yōu)勢，其中SBM的困惑度是206.76，而CS-SBM達(dá)到了204.87。實(shí)驗(yàn)結(jié)果表明，SBM和CS-SBM有著更好的預(yù)測剩余查詢項(xiàng)的能力。

圖4 Observed 數(shù)據(jù)的困惑度Fig.4 Perplexity of observed data

4.3 搜索主題發(fā)現(xiàn)及分析

發(fā)現(xiàn)搜索主題的合理性是判斷模型是否成功的一個(gè)重要指標(biāo)。本文中的實(shí)驗(yàn)結(jié)果證明了提出的模型在發(fā)現(xiàn)搜索主題方面表現(xiàn)突出，同時(shí)還準(zhǔn)確地預(yù)測了查詢主題在時(shí)間上的演化趨勢。

實(shí)驗(yàn)中設(shè)置主題的數(shù)目為K=50。搜索主題是從Gibbs采樣的1000次迭代中單次采樣提取的。在表1～4中，展示了4個(gè)由SBM和CS-SBM分別在語料庫級上和單個(gè)用戶級上發(fā)現(xiàn)的搜索主題，并列出了各主題概率值最大的前5個(gè)詞匯及其概率。主題名稱是根據(jù)該主題下詞匯具體的語義信息定義的。圖5～8中，直方圖顯示了主題在時(shí)間軸上的概率分布，光滑曲線為擬合Beta分布的概率密度函數(shù)曲線。下面將選取圖中的兩個(gè)搜索主題進(jìn)行具體分析。

表1～2 中的第一個(gè)主題是“地震”，通過圖5～6可以發(fā)現(xiàn)，本文提出的SBM模型在語料庫級上和單個(gè)用戶級上都成功獲取了主題時(shí)間上的突發(fā)性。根據(jù)其時(shí)間分布來看，由于剛剛發(fā)生過汶川地震，因此在6月份的前半個(gè)月，人們對地震的搜索比較頻繁，但隨著時(shí)間的推移，搜索數(shù)量逐漸減少。從語料庫級的分析結(jié)果看，“汶川、地震、救災(zāi)”等高頻詞匯都與地震相關(guān)。對于單個(gè)用戶，本文從實(shí)驗(yàn)結(jié)果中選擇了一位有大量查詢?nèi)罩静⑶矣械卣鹬黝}的用戶做具體分析描述。結(jié)果發(fā)現(xiàn)，在這個(gè)主題下的詞，例如地震、汶川、唐山、四川等詞匯出現(xiàn)的概率較高。總體來看，汶川地震引起了人們廣泛的關(guān)注，對于全局來說，用戶更關(guān)注地震救援工作；對于表2中的個(gè)人用戶來說，他們只是關(guān)注地震本身，而沒有救援相關(guān)的查詢。

表3～4中，最后一個(gè)主題是“歐洲杯”，圖7～8中，CS-SBM的實(shí)驗(yàn)結(jié)果顯示關(guān)于“歐洲杯”這個(gè)話題的查詢從第十天到第三十天越來越多，這也符合隨著歐洲杯的進(jìn)行人們關(guān)注的熱情越來越高的現(xiàn)象。從整個(gè)語料庫得到的結(jié)果來看，搜索主題“歐洲杯”主要包括歐洲杯、瑞士、奧地利等詞。其中“瑞士”和“奧地利”是本屆歐洲杯的舉辦地，這些詞匯都與歐洲杯的主題緊密相關(guān)。而對于表4中的個(gè)人用戶，我們?nèi)匀粡膶?shí)驗(yàn)結(jié)果中選取了與“歐洲杯”主題相關(guān)的用戶進(jìn)行分析說明。它包括歐洲杯、西班牙、冠軍等關(guān)鍵詞，這證明了該用戶更關(guān)注于歐洲杯的冠軍歸屬問題。

總體而言，發(fā)現(xiàn)的搜索主題與實(shí)際的情況大體相吻合，而且能較好地反應(yīng)主題變化的趨勢。

(a) 主題“地震”隨著時(shí)間 (b) 主題“NBA”隨著時(shí)間 的變化趨勢 的變化趨勢圖5 CS-SBM網(wǎng)絡(luò)搜索分析主題模型Fig.5 Latent evolutions of SBM-TG discovered search topics

(a) 主題“地震”隨著時(shí)間 (b) 主題“NBA”隨著時(shí)間 的變化趨勢 的變化趨勢圖6 SBM-TU發(fā)現(xiàn)的搜索主題在時(shí)間上的演化趨勢Fig.6 Latent evolutions of SBM-TU discovered search topics

(a) 主題“電子產(chǎn)品”隨著 (b) 主題“歐洲杯”隨著 時(shí)間的變化趨勢 時(shí)間的變化趨勢圖7 CS-SBM-TG發(fā)現(xiàn)的搜索主題在時(shí)間上的演化趨勢Fig.7 Latent evolutions of CS-SBM-TG discovered search topics

(a) 主題“電子產(chǎn)品”隨著 (b) 主題“歐洲杯”隨著 時(shí)間的變化趨勢 時(shí)間的變化趨勢圖8 CS-SBM-TU發(fā)現(xiàn)的搜索主題在時(shí)間上的演化趨勢Fig.8 Latent evolutions of CS-SBM-TU discovered search topics

主題1地震主題2NBA搜索詞概率搜索詞概率汶川0．03628NBA0．03128地震0．03342季后賽0．02883救災(zāi)0．03217西部0．02832武警0．02774湖人0．02336哄搶0．02774冠軍0．02092

表2 SBM-TU發(fā)現(xiàn)的搜索主題分布情況

表3 CS-SBM-TG發(fā)現(xiàn)的搜索主題分布情況

表4 CS-SBM-TG發(fā)現(xiàn)的搜索主題分布情況

5 結(jié)束語

本文提出了兩個(gè)主題模型SBM和CS-SBM，從全局和基于特定用戶來建模網(wǎng)絡(luò)搜索分析。SBM主要是用于獲取網(wǎng)絡(luò)查詢的突發(fā)現(xiàn)象。CS-SBM主要添加了查詢詞和URL之間的關(guān)系，獲取了主題突發(fā)性。為了使SBM和CS-SBM可以獲取時(shí)間上的突發(fā)性，本文采用Beta分布擬合主題在時(shí)間上的變化的策略。本文還設(shè)計(jì)了一系列的實(shí)驗(yàn)驗(yàn)證了提出模型擁有較好的泛化能力、主題發(fā)現(xiàn)能力和反應(yīng)主題時(shí)間上突發(fā)性的能力。本文的貢獻(xiàn)主要有三個(gè)方面：第一，研究了搜索引擎用戶行為分析中突發(fā)性現(xiàn)象；第二，提出了兩種新型的模型用來捕獲網(wǎng)絡(luò)搜索中各個(gè)方面的突發(fā)性；第三，通過大量的實(shí)驗(yàn)驗(yàn)證了模型的有效性。下一步工作中，將把這些模型運(yùn)用到團(tuán)購廣告投放。通過發(fā)現(xiàn)用戶的搜索主題，然后將同一主題下的用戶按照社團(tuán)發(fā)現(xiàn)的規(guī)則進(jìn)行分類，并進(jìn)行廣告投放。

[1]SUNEHAG P. Using two-stage conditional word frequency models to model word burstiness and motivating TF-IDF[J]. Journal of machine learning reasearch, 2017, 2: 8.

[2]ELKAN C. Clustering documents with an exponential-family approximation of the Dirichlet compound multinomial distribution[C]//Proceedings of the 23rd International Conference on Machine Learning, Pittsburgh. Pennsylvania, USA, 2006: 289-296.

[3]DOYLE G， ELKAN C. Accounting for burstiness in topic models[C]//Proceedings of the 26th Annual International Conference on Machine Learning Montreal. QC, Canada, 2009: 281-288.

[4]XUE G R, ZENG H J, CHEN Z, et al. Optimizing web search using web click-through data[C]//Proceedings of the thirteenth ACM international conference on Information and Knowledge Management. Washington, USA, 2004: 118-126.

[5]GUO F, LIU C, WANG Y M. Efficient multiple-click models in web search[C]//Proceedings of the Second ACM International Conference on Web Search and Data Mining. Barcelona, Spain, 2009: 124-131.

[6]張宇, 宋巍, 劉挺, 等. 基于 URL 主題的查詢分類方法[J]. 計(jì)算機(jī)研究與發(fā)展, 2012, 49(6): 1298-1305.

ZHANG Yu, SONG Wei, LIU Ting, et al. Query classification based on url topic[J]. Journal of computer research and development, 2012, 49(6): 1298-1305.

[7]MADSEN R E, KAUCHAK D, ELKAN C. Modeling word burstiness using the dirichlet distribution[C]//Proceedings of the 22nd international conference on Machine iearning. Bonn, Germany, 2005: 545-552.

[8]BLEI D M, NG A Y, JORDAN M I. Latent dirichlet allocation[J]. Journal of machine learning research, 2003, 3(1): 993-1022.

[9]WANG X, MCCALLUM A. Topics over time: a non-Markov continuous-time model of topical trends[C]//Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining. Philadelphia, USA, 2006: 424-433.

[10]徐戈, 王厚峰. 自然語言處理中主題模型的發(fā)展[J]. 計(jì)算機(jī)學(xué)報(bào), 2011, 34(8): 1423-1436.

XU Ge， WANG Houfeng. The development of topic model in natural language processing[J]. Chinese journal of computers, 2011, 34(8): 1423-1436.

[11]張晨逸, 孫建伶, 丁軼群. 基于 MB-LDA 模型的微博主題挖掘[J]. 計(jì)算機(jī)研究與發(fā)展, 2011, 48(10): 1795-1802.

ZHANG Chenyi, SUN Jianling， DING Yiqun. Topic mining for microblog based on mb-lda model[J]. Journal of computer research and development, 2011, 48(10): 1795-1802.

[12]劉少鵬, 印鑒, 歐陽佳, 等. 基于 MB-HDP 模型的微博主題挖掘[J]. 計(jì)算機(jī)學(xué)報(bào), 2015, 38(7): 1408-1419.

LIU Shaopeng, YIN Jian, OUYANG Jia, et al. Topic mining from microblogs based on MB-HDP model[J]. Chinese Journal of Computers, 2015, 38(7): 1408-1419.

[13]JIANG D, TONG Y, SONG Y. Cross-lingual topic discovery from multilingual search engine query log[J]. ACM transactions on information systems (TOIS), 2016, 35(2): 9.

[14]JIANG D, LEUNG K W T, NG W. Query intent mining with multiple dimensions of web search data[J]. World wide web, 2016, 19(3): 475.

[15]JIANG D, YANG L. Query intent inference via search engine log[J]. Knowledge and information systems, 2016, 49(2): 661-685.

[16]HUANG J, EFTHIMIADIS E N. Analyzing and evaluating query reformulation strategies in web search logs[C]//Proceedings of the 18th ACM Conference on Information and Knowledge Management. Hong Kong, China, 2009: 77-86.

[17]GRIFFITHS T L, STEYVERS M. Finding scientific topics[J]. Proceedings of the national academy of sciences, 2004, 101(1): 5228-5235.

[18]ZHU C, BYRD R H, LU P, et al. Algorithm 778: L-BFGS-B: Fortran subroutines for large-scale bound-constrained optimization[J]. ACM transactions on mathematical software (TOMS), 1997, 23(4): 550-560.

[19]MANNING C D, RAGHAVAN P, SCHüTZE H. Introduction to information retrieval[M]. Cambridge: Cambridge University Press, 2008: 1-16.

[20]JIANG D, NG W. Mining web search topics with diverse spatiotemporal patterns[C]//Proceedings of the 36th International ACM SIGIR Conference on Research and Development in Information Retrieval. Dublin, Ireland, 2013: 881-884.

[21]LI W, MCCALLUM A. Pachinko allocation: DAG-structured mixture models of topic correlations[C]//Proceedings of the 23rd International Conference on Machine Learning. Pittsburgh, USA, 2006: 577-584.

張森，男，1992年生，碩士研究生，主要研究方向?yàn)樾畔z索、自然語言處理。

張晨，男，1988年生，副教授，博士，主要研究方向?yàn)楸姲?、?shù)據(jù)分析與數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)。在TKD、 VLDB、 SIGMOD、 ICDE等國內(nèi)外重要期刊和頂級學(xué)術(shù)會(huì)議上發(fā)表論文10余篇。

林培光，男，1978年生，副教授，博士，主要研究方向?yàn)樾畔z索、海量數(shù)據(jù)處理和集成。主持教育部課題2項(xiàng)、山東省自然科學(xué)基金項(xiàng)目1項(xiàng)、濟(jì)南市科技局自主創(chuàng)新計(jì)劃 1 項(xiàng)和青年科技明星計(jì)劃 1 項(xiàng)，另外參與國家自然科學(xué)基金以及省部級課題多項(xiàng)。發(fā)表學(xué)術(shù)論文30余篇，被SCI檢索3篇，EI檢索30余篇。

Websearchtopicanalysisbasedonusersearchquerylogs

ZHANG Sen1， ZHANG Chen1,2， LIN Peiguang1， ZHANG Chunyun1， GUO Yuchao1， REN Weilong1， REN Ke2

(1. School of Computer Science amp; Technology, Shandong University of Finance amp; Economics, Jinan 250014, China; 2.Department of Computer Science amp; Engineering, Hong Kong University of Science and Technology, Hong Kong 999077, China)

Web search analysis plays a critical role in improving the performance of contemporary search engines. In addition, search engine accuracy can be improved by analyzing the individual search properties of users. Most existing models, such as the click graph and its variants, focus on the common characteristics of the group. However, as yet, there has been little investigation of a model that would obtain both the collective group characteristics and the unique characteristics of individual users. In this paper, we investigate user-specific web search analysis, whereby we obtain the topic distributions of the search queries of individual users by determining the burstiness of user searches. We propose two topic models, i.e., the search burstiness model (SBM) and the coupling-sensitive search burstiness model (CS-SBM). The SBM adopts the assumption that the query words and URL are topically independent, The CS-SBM supposes that the query words and URL are topically relevant. The obtained topic distribution information is stored in skewed Dirichlet priors and a beta distribution is used to capture the temporal properties of the user searches. Our experimental results show that each user’s web search trail has unique characteristics, and that in the case of there being a large amount of real query log data, in comparison to the latent Dirichlet allocation (LDA) and topic over time (TOT) models, our proposed models have advantages with respect to generalized performance and effectively describes the temporal change process of user search queries.

web search; search engine; natural language processing; topic model; data mining; burstiness; temporal analysis; parameter estimate

10.11992/tis.201706096

http://kns.cnki.net/kcms/detail/23.1538.TP.20171021.1349.004.html

TP391

A

1673-4785(2017)05-0668-10

中文引用格式：張森，張晨，林培光，等.基于用戶查詢?nèi)罩镜木W(wǎng)絡(luò)搜索主題分析J.智能系統(tǒng)學(xué)報(bào)， 2017, 12(5): 668-677.

英文引用格式：ZHANGSen，ZHANGChen，LINPeiguang，etal.WebsearchtopicanalysisbasedonusersearchquerylogsJ.CAAItransactionsonintelligentsystems, 2017, 12(5): 668-677.

2017-07-01. < class="emphasis_bold">網(wǎng)絡(luò)出版日期

日期：2017-10-21.

國家自然科學(xué)基金重點(diǎn)項(xiàng)目(U1201258);山東省自然科學(xué)杰出青年基金項(xiàng)目(JQ201316);教育部人文社會(huì)科學(xué)研究項(xiàng)目(15YJAZH042).

張晨. E-mail: zhangchen.sdufe@gmail.com.