羅 成,劉奕群,張 敏,馬少平,茹立云,張 闊
(智能技術(shù)與系統(tǒng)國(guó)家重點(diǎn)實(shí)驗(yàn)室;清華信息科學(xué)與技術(shù)國(guó)家實(shí)驗(yàn)室(籌);清華大學(xué) 計(jì)算機(jī)系,北京,100084)
過去的20年中,World Wide Web(以下簡(jiǎn)稱Web)在全球化范圍內(nèi)獲得了長(zhǎng)足的發(fā)展。Web上的信息以傳統(tǒng)網(wǎng)頁、媒體文件(圖片、音頻、視頻)、社區(qū)論壇、郵件列表、微博和博客等多種形式呈現(xiàn),從數(shù)量上呈現(xiàn)了爆炸的趨勢(shì)。面對(duì)如此規(guī)模龐大的Web信息,傳統(tǒng)的檢索方法已經(jīng)無法滿足人們的信息需求,給人們的生活和工作帶來了無法想象的困難。
搜索引擎是指自動(dòng)從Web上搜集信息,經(jīng)過一定的整理以后,提供給用戶進(jìn)行查詢的系統(tǒng)[1]。它的出現(xiàn)在一定程度上解決了針對(duì)海量信息檢索和瀏覽的問題。在短短的20年里,搜索引擎相關(guān)的技術(shù)進(jìn)步顯著,同時(shí)極大地改變了人們獲取信息的方式。
現(xiàn)有的用戶和搜索引擎的交互過程一般如下:
? 用戶分析自身的信息需求,概括查詢意圖。
? 用戶進(jìn)一步試圖用一些關(guān)鍵字描述查詢意圖,并提交給搜索引擎。這一過程受限于用戶自身的水平,可能發(fā)生信息丟失。
? 搜索引擎將根據(jù)用戶提交的關(guān)鍵詞查找索引,將查找結(jié)果按照相關(guān)性排序后返回給用戶。
在依賴關(guān)鍵詞進(jìn)行檢索的搜索引擎框架中,經(jīng)常無法返回滿足用戶意圖的相關(guān)結(jié)果。這一方面是因?yàn)閃eb上的信息量非常巨大,另外一方面是用戶提交的查詢意圖通常非常短,所包含的信息量很少。有研究者對(duì)某中文搜索引擎大量的查詢?nèi)罩具M(jìn)行了統(tǒng)計(jì),發(fā)現(xiàn)長(zhǎng)度不超過3個(gè)詞的查詢數(shù)量占總查詢數(shù)量的93.15%,平均長(zhǎng)度僅為1.85個(gè)詞[2]。這就使得搜索引擎很難準(zhǔn)確地識(shí)別用戶的具體查詢意圖,進(jìn)而提供讓用戶滿意的結(jié)果。如何幫助用戶更準(zhǔn)確地描述自己的信息需求,或者幫助搜索引擎更充分地理解用戶的查詢意圖,成為搜索引擎重要且關(guān)鍵的技術(shù)之一。
在近年來的相關(guān)研究中,查詢推薦相關(guān)技術(shù)成為解決這一問題的有效手段之一。在用戶提交查詢后,搜索引擎除了返回相關(guān)結(jié)果之外,還返回一個(gè)相關(guān)查詢列表供用戶選擇,可以幫助用戶更準(zhǔn)確、更快捷地描述自己的查詢意圖,增加用戶和搜索引擎再次交互的可能。目前幾乎所有的商用搜索引擎都會(huì)在搜索結(jié)果頁為用戶提供查詢推薦,并且這一方式也被用戶所認(rèn)同,據(jù)統(tǒng)計(jì),有15.36%的用戶查詢會(huì)話中都包含對(duì)查詢推薦結(jié)果的點(diǎn)擊[3]。
由此可見,查詢推薦相關(guān)的技術(shù)的研究,具有重要的研究?jī)r(jià)值和應(yīng)用前景,吸引了當(dāng)前學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注。然而,現(xiàn)有的商業(yè)搜索引擎中,大多從查詢文本本身出發(fā),對(duì)其進(jìn)行同義改寫和替換,或是選擇和原查詢文本類似的熱門查詢作為推薦,并沒有關(guān)注原查詢中潛在的用戶意圖。如果給出的查詢推薦可以更準(zhǔn)確地描述用戶意圖,搜索引擎就有可能有針對(duì)地調(diào)整自己的檢索策略,把質(zhì)量更高的頁面放在相對(duì)靠前的位置。作者從用戶意圖識(shí)別的角度,就如何給出更加切合用戶信息需求的查詢推薦進(jìn)行了一些研究,構(gòu)建了一個(gè)完整的查詢推薦流程。
查詢推薦方法吸引工業(yè)界和學(xué)術(shù)界關(guān)注已經(jīng)有超過10年的時(shí)間,形成了一系列的研究成果,可以將其分為查詢層次和詞項(xiàng)層次的查詢推薦方法。
查詢層次的查詢推薦方法通常將查詢看成一個(gè)整體,和其他查詢進(jìn)行某種意義下的相似性度量,將最相似的結(jié)果作為查詢推薦。其優(yōu)點(diǎn)在于綜合考慮了原查詢的全部信息,給出的推薦更加可靠。經(jīng)常用到的方法有查詢流圖(Query-Flow Graph)[4],二部圖上的隨機(jī)漫步(Random Walk)[5]等。Zhang等人提出了一種將查詢流圖上的轉(zhuǎn)移和文本相關(guān)性結(jié)合的一種查詢推薦方法[6]。在查詢流圖上作者認(rèn)為從一個(gè)節(jié)點(diǎn)到另外一個(gè)節(jié)點(diǎn)的轉(zhuǎn)移可能以一個(gè)固定的比例衰減。兩個(gè)查詢間的相似性以所有會(huì)話中一個(gè)節(jié)點(diǎn)到另外一個(gè)節(jié)點(diǎn)的所有道路的權(quán)重加和來表示。Mei等人在2008年提出的一種在大規(guī)模的“查詢-鏈接”二部圖上基于Hitting Time進(jìn)行查詢推薦的方法[7]。Hitting Time可以直觀理解為二部圖上從一個(gè)查詢頂點(diǎn)跳轉(zhuǎn)到另外一個(gè)查詢頂點(diǎn)的點(diǎn)擊時(shí)間。如果將和用戶查詢相關(guān)的個(gè)性化信息一起放入二部圖中,還可以做個(gè)性化的推薦。查詢層次的方法缺陷是通常要求原查詢和給出的推薦必須在之前的用戶日志中出現(xiàn)過,很難對(duì)所有的查詢都給出推薦。
詞項(xiàng)層次的查詢推薦通常把查詢視為一個(gè)詞的序列,然后對(duì)其中的元素進(jìn)行替換、改寫或者重組織等操作。經(jīng)常用到的模型有詞項(xiàng)轉(zhuǎn)移圖[8]、概念模式[9]等。詞項(xiàng)層次的查詢推薦優(yōu)點(diǎn)在于幾乎可以為任何查詢給出推薦。Song等人提出了一種在不同的話題分類下基于詞項(xiàng)轉(zhuǎn)移圖的查詢推薦方法[8]。作者挖掘了用戶查詢行為中對(duì)查詢中的詞項(xiàng)進(jìn)行修改的行為,在不同的分類話題下建立詞項(xiàng)轉(zhuǎn)移圖,迭代計(jì)算每一個(gè)頂點(diǎn)的PageRank值。對(duì)于一個(gè)給定的查詢,首先對(duì)其進(jìn)行話題分類,根據(jù)其類別標(biāo)簽在相應(yīng)的短語圖上計(jì)算每一個(gè)詞的最佳推薦,經(jīng)過排序和過濾給出最終的推薦查詢。概念模式是將用戶給出的查詢轉(zhuǎn)換成一個(gè)概念模板,所謂概念,可以理解為一個(gè)類別。Cao等人提出了一種將查詢概念模式和概念后綴樹結(jié)合的內(nèi)容敏感查詢推薦框架[9]。概念模式樹的每一個(gè)節(jié)點(diǎn)是一個(gè)概念,葉子節(jié)點(diǎn)對(duì)應(yīng)著一個(gè)按照熱門程度排序的后綴短語列表。當(dāng)用戶提交查詢時(shí),找到和其查詢對(duì)應(yīng)的概念模式,在概念后綴樹上從根節(jié)點(diǎn)出發(fā),找到葉子節(jié)點(diǎn)上最熱門的詞附在原查詢后作為最終的查詢推薦。詞項(xiàng)層次的方法不足之處在于某一個(gè)詞項(xiàng)可能只代表原查詢含義的一部分,添加或者替換的詞項(xiàng)可能和原查詢無關(guān)。
從用戶意圖識(shí)別的角度出發(fā),也有一些相關(guān)的工作。Liu等人在2011年提出了基于摘要點(diǎn)擊模型進(jìn)行用戶意圖挖掘的方法[3],基于摘要點(diǎn)擊信息對(duì)商業(yè)搜索引擎給出的查詢推薦進(jìn)行重新排序,從體現(xiàn)用戶意圖的角度取得了提高。Liu等人的嘗試僅從摘要點(diǎn)擊的角度挖掘優(yōu)化商業(yè)搜索引擎提供的查詢推薦結(jié)果,并沒有構(gòu)建完整的查詢推薦流程。Sadikov 等人提出了一種結(jié)合文檔點(diǎn)擊和session共現(xiàn)特征,根據(jù)用戶意圖進(jìn)行查詢修改行為的聚類方法[10]。這樣的聚類可以側(cè)面描述用戶的潛在意圖,但是通常用戶在搜索過程中遇到不滿意的結(jié)果大多放棄搜索,因此用戶修改查詢的數(shù)據(jù)相對(duì)稀疏,該方法很難對(duì)大量的查詢給出查詢推薦。Mei等人利用Hitting Time進(jìn)行查詢推薦的方法[7],可以加入用戶的個(gè)人信息,在一定程度上可以進(jìn)行用戶信息需求的細(xì)化,也是一種間接的利用用戶意圖進(jìn)行查詢推薦的技術(shù)。
在已有的工作中,研究者大多關(guān)注查詢之間的相似程度、利用文本、用戶點(diǎn)擊等特征進(jìn)行推薦,并沒有充分理解用戶的真實(shí)查詢意圖,往往無法給出更加清晰表述信息需求的推薦結(jié)果。
論文工作的創(chuàng)新之處在于利用二部圖上隨機(jī)漫步方法產(chǎn)生規(guī)模較大的候選集合,結(jié)合摘要點(diǎn)擊信息充分地考慮用戶意圖,并采用機(jī)器學(xué)習(xí)方法對(duì)其中可能的噪聲進(jìn)行識(shí)別,從而提升查詢推薦的性能,協(xié)助用戶更好地完成信息獲取任務(wù)。
為了實(shí)現(xiàn)對(duì)大規(guī)模用戶行為進(jìn)行分析,給出查詢推薦,我們?cè)谀成虡I(yè)搜索引擎公司的協(xié)助下收集了2012年的部分用戶搜索引擎點(diǎn)擊數(shù)據(jù),總的規(guī)模為19.39億條,選取的時(shí)間跨度在1個(gè)月之內(nèi)。
測(cè)試查詢集合選取NTCIR的INTENT-1 和INTENT-2測(cè)試集,合并去重后共包含198個(gè)互不相同的查詢。
針對(duì)查詢意圖的分類,Broder等人提出了導(dǎo)航類、信息類和事務(wù)類的分類標(biāo)準(zhǔn)[11]。我們將本文選取的測(cè)試查詢集合和Broder等人抽樣統(tǒng)計(jì)的結(jié)果進(jìn)行了比較。
圖1 本文查詢數(shù)據(jù)集合分布
由圖1,我們選取的查詢集合與Broder等人的統(tǒng)計(jì)結(jié)果趨勢(shì)基本一致,其中的比例差異可能是由于中英文用戶使用搜索引擎的習(xí)慣差異導(dǎo)致,總體而言,可以認(rèn)為是實(shí)際網(wǎng)絡(luò)環(huán)境的可靠近似。
生成候選的查詢推薦有多種方法。在真實(shí)的搜索引擎中,可以從文本特征、語義特征等多個(gè)角度生成推薦候選。與基于文本相似度給出的推薦候選相比,語義層面上給出的候選推薦與用戶意圖相關(guān)的可能性更大。從語義的角度出發(fā),結(jié)合我們擁有的海量用戶行為記錄,建立查詢流圖[4]或者查詢鏈接二部圖[5]等都是常用的查詢推薦的挖掘技術(shù)。這里我們采用二部圖上的隨機(jī)漫步方法進(jìn)行候選查詢的挖掘。基本假設(shè)是點(diǎn)擊了相同或相似鏈接的查詢具有一定的語義層次相關(guān)性。二部圖上的隨機(jī)漫步方法可以利用大量的真實(shí)的用戶查詢作為候選,為大量查詢高效的生成候選推薦。同時(shí),這樣生成的查詢推薦比較接近用戶的意圖;候選列表按照二部圖上的轉(zhuǎn)移概率排序,本身具有一定的參考意義;同時(shí)得到候選集合的規(guī)模大,之后結(jié)合用戶意圖信息進(jìn)行重排序的空間較大。缺點(diǎn)是隨機(jī)漫步方法可能無法為全部的查詢給出推薦,我們可以通過擴(kuò)大數(shù)據(jù)規(guī)模進(jìn)行改善;可能帶來一些噪音,但之后的重排序過程、機(jī)器學(xué)習(xí)方法噪音識(shí)別過程都可以對(duì)噪音進(jìn)行有效地過濾和篩選,對(duì)整個(gè)查詢推薦流程的影響不大。
“查詢-鏈接”二部圖的頂點(diǎn)由兩個(gè)互不相交的子集構(gòu)成,一個(gè)子集為查詢集合,包含用戶提交的相關(guān)查詢,另外一個(gè)集合為鏈接集合,為用戶點(diǎn)擊的所有鏈接。從查詢q到鏈接u這條邊的權(quán)重表明在用戶行為數(shù)據(jù)集合中提交查詢q,點(diǎn)擊鏈接u的次數(shù)。
基于隨機(jī)漫步的查詢推薦過程,需要定義不同的查詢節(jié)點(diǎn)間的轉(zhuǎn)移概率。然后在“查詢-鏈接”二部圖上進(jìn)行隨機(jī)游走,選取到達(dá)概率最大的前若干個(gè)查詢作為推薦的查詢返回。
在二部圖G=({V1,V2},E)上,首先定義從頂點(diǎn)i到相鄰的頂點(diǎn)j的轉(zhuǎn)移概率如式(1)所示。
其中,
其中wi,j為二部圖上有向邊(i,j)的權(quán)重;di是所有與頂點(diǎn)i相連的邊的權(quán)重加和。
在此基礎(chǔ)上,可以定義一個(gè)該二部圖上的一個(gè)2步長(zhǎng)的隨機(jī)漫步過程:
這樣,我們就對(duì)查詢間的相似度給出了度量。
通過“查詢-鏈接”二部圖上隨機(jī)漫步的方法,對(duì)于198個(gè)查詢,我們對(duì)其中的176個(gè)查詢給出了推薦結(jié)果,其中161個(gè)查詢的推薦結(jié)果數(shù)量多于10個(gè)。22個(gè)查詢沒有得到查詢推薦結(jié)果,主要是這些查詢比較冷門,在“查詢-鏈接”二部圖上沒有相應(yīng)的聯(lián)通分支,這是二部圖上隨機(jī)漫步方法的一個(gè)局限。
表1 隨機(jī)漫步方法查詢推薦結(jié)果示例
分析表中的數(shù)據(jù)可以得出,對(duì)于“巨人”和“E話通”這兩個(gè)查詢,隨機(jī)漫步方法可以給出相關(guān)的查詢推薦,并且根據(jù)轉(zhuǎn)移概率進(jìn)行排序。但是這種方法給出的查詢推薦也存在一些問題: 1)很多推薦的查詢是對(duì)原查詢的簡(jiǎn)單重復(fù),比如“E話通”的推薦結(jié)果“e話通”,對(duì)于用戶細(xì)化對(duì)查詢意圖的描述沒有太大的幫助;2)查詢的質(zhì)量不穩(wěn)定,例如,“巨人”查詢推薦“juren”,和“E話通”的查詢推薦“doshow”,都可以認(rèn)為是一些表達(dá)模糊的低質(zhì)量查詢,隨機(jī)漫步方法本身不能判斷這種查詢的質(zhì)量。
針對(duì)上面的問題,一方面可以結(jié)合用戶意圖,對(duì)推薦列表進(jìn)行重新排序,讓高質(zhì)量的推薦排在比較前的位置,從而提升推薦查詢的質(zhì)量;另外一方面可以利用機(jī)器學(xué)習(xí)的方法,訓(xùn)練模型,對(duì)低質(zhì)量的推薦結(jié)果進(jìn)行過濾。
在用戶和搜索引擎的單次交互中,搜索引擎很難把握用戶的準(zhǔn)確意圖。通過對(duì)過去提交相同或者相似查詢的用戶行為進(jìn)行分析,可以盡可能地接近當(dāng)前用戶的意圖。搜索結(jié)果頁上的摘要是用戶進(jìn)行相關(guān)性判斷的依據(jù),也隱含著迎合了用戶意圖的信息。
現(xiàn)有的通用搜索引擎,通常接受用戶提供的一個(gè)查詢?cè)~序列,返回一系列搜索結(jié)果,以標(biāo)題和摘要作為主要的展現(xiàn)內(nèi)容。
我們不難看出,在用戶點(diǎn)擊某條結(jié)果之前,并不能看到這條結(jié)果所鏈接到的頁面的具體內(nèi)容,只能看到結(jié)果的標(biāo)題、摘要、鏈接地址和時(shí)間。
圖2 搜索結(jié)果呈現(xiàn)方式示例
Liu等人在相關(guān)工作中提出以下兩個(gè)假設(shè)[3]:
相關(guān)性的間接判定假設(shè): 認(rèn)為搜索引擎用戶在點(diǎn)擊結(jié)果之前,標(biāo)題和摘要是用戶判斷相關(guān)性的最主要依據(jù)。
用戶的群體智慧假設(shè): 雖然單個(gè)用戶的點(diǎn)擊行為不足以判斷查詢和結(jié)果間的相關(guān)性,但是大量用戶的點(diǎn)擊行為為相關(guān)關(guān)系提供了可靠反饋。
在此基礎(chǔ)上我們可以進(jìn)一步假定,在某個(gè)查詢的結(jié)果中,被較多用戶點(diǎn)擊的結(jié)果,其標(biāo)題和摘要反映用戶意圖的可能性較大;在同一條結(jié)果的標(biāo)題和摘要中,出現(xiàn)較多的詞對(duì)用戶的相關(guān)性判定發(fā)揮更重要的作用。將標(biāo)題和摘要切分成詞,不同的詞在標(biāo)題和摘要中對(duì)用戶的吸引程度不同,可如果可以將其量化成一個(gè)權(quán)重,就可以對(duì)推薦的查詢從滿足用戶意圖的角度進(jìn)行評(píng)價(jià),對(duì)候選查詢推薦重新排序。
結(jié)合上述的兩點(diǎn)假定,我們提出了一種利用詞頻和點(diǎn)擊分布計(jì)算詞得分的方法,同時(shí)考慮到了摘要和標(biāo)題的重要性差異,假定標(biāo)題在用戶進(jìn)行相關(guān)性判定時(shí)更重要一些。
對(duì)于一個(gè)查詢Q,摘要中每一個(gè)詞t的權(quán)重按照式(4)算出:
其中N表示從結(jié)果頁上解析出的查詢結(jié)果的數(shù)量。TF表示該詞在標(biāo)題和摘要總的詞頻,CDi表示第i條摘要在用戶行為數(shù)據(jù)中的點(diǎn)擊分布,既考慮到了單個(gè)搜索結(jié)果中,不同詞的詞頻和權(quán)重不同,又考慮到了用戶的點(diǎn)擊偏好。為了解決詞項(xiàng)出現(xiàn)的邊際效應(yīng),對(duì)詞頻取對(duì)數(shù),這也是文本檢索中的常見的做法。
進(jìn)一步的,需要考慮用戶在瀏覽搜索結(jié)果中,對(duì)標(biāo)題與摘要的信任程度可能不同,對(duì)摘要和標(biāo)題的信息進(jìn)行區(qū)分和整合:
實(shí)驗(yàn)中經(jīng)過多次嘗試,當(dāng)λ=1.2時(shí)效果較好。
利用上面的產(chǎn)生式,我們?yōu)槊恳粋€(gè)查詢都計(jì)算出了一個(gè)詞權(quán)重列表,隨機(jī)抽取了50個(gè)查詢進(jìn)行統(tǒng)計(jì),平均每一個(gè)查詢得到的有效詞項(xiàng)個(gè)數(shù)為47.2個(gè)。
得到詞權(quán)重列表以后,我們可以對(duì)隨機(jī)漫步方法給出的查詢推薦列表進(jìn)行重新排序。
對(duì)于一個(gè)查詢Q,可以得到一個(gè)與其相關(guān)的詞權(quán)重列表D,對(duì)于一個(gè)查詢推薦QR,我們可以計(jì)算其得分,這里采用了線性加和的方法:
即查詢推薦QR的得分等于所有在QR中出現(xiàn)且不在Q中出現(xiàn)的詞權(quán)重之和,得分越高,意味著QR包含了越多權(quán)重不為0的詞,或者包含了權(quán)重越高的詞。按照查詢推薦命中的詞項(xiàng)得分進(jìn)行重排序。
在表2的結(jié)果示例中,存在一些噪聲,例如,查詢“坐上火車去拉薩”中的“傷感唯美歌曲”、“拉薩歌曲”、“坐上火車+去拉薩歌曲”,和查詢“貔貅”中的“開光方法”、“開光”、“pixiujiage”和“淘寶網(wǎng)”等。出現(xiàn)這種噪聲的可能是:
1. 用戶的點(diǎn)擊較為稀疏,計(jì)算出的詞項(xiàng)得分偶然性較大;
2. 查詢?yōu)槠匆艋蜴溄?,可讀性較差,并不能描述用戶的信息需求;
表2 基于用戶意圖重排序推薦結(jié)果示例
3. 查詢中包含錯(cuò)別字,不能很好的獲得結(jié)果。
綜合以上,如果可以采用機(jī)器學(xué)習(xí)的方法對(duì)候選列表進(jìn)行過濾和篩選,可以進(jìn)一步提高其質(zhì)量。
對(duì)于一個(gè)給定的查詢,利用“查詢-鏈接”二部圖上的隨機(jī)漫步方法挖掘出的查詢推薦中,很有可能包含一些低質(zhì)量的結(jié)果,利用摘要點(diǎn)擊信息依然無法對(duì)查詢的質(zhì)量進(jìn)行甄別。如果可以構(gòu)建一個(gè)分類器,對(duì)查詢推薦的質(zhì)量進(jìn)行分類,結(jié)合前面的候選查詢生成算法,就可以自動(dòng)生成查詢推薦。
對(duì)于樣本中的每一個(gè)查詢,我們抽取了10個(gè)特征:
特征1: 提交過該查詢的獨(dú)立用戶數(shù);
特征2: 查詢結(jié)果中,被用戶點(diǎn)擊過的獨(dú)立目標(biāo)地址數(shù);
特征3: 總共被查詢的次數(shù);
特征4: 推薦查詢對(duì)原查詢的覆蓋率,即原查詢中的字符在推薦查詢中出現(xiàn)的比例;
特征5: 推薦查詢和原查詢的長(zhǎng)度比值;
特征6: 推薦查詢比原查詢多出字母數(shù);
特征7: 推薦查詢比原查詢多出數(shù)字?jǐn)?shù);
特征8: 推薦查詢相當(dāng)于原查詢的轉(zhuǎn)移概率;
特征9: 推薦查詢命中的原查詢摘要詞項(xiàng)數(shù)目;
特征10: 推薦查詢基于原查詢的摘要詞權(quán)重表的得分。
上面提取的10個(gè)特征來源于三點(diǎn)考慮:
? 推薦查詢相關(guān)的真實(shí)用戶行為(特征1、特征2和特征3): 針對(duì)推薦候選中的一些冷門查詢、包含錯(cuò)別字的查詢等。
? 推薦查詢于原查詢的文本特征(特征4、特征5、特征6、特征7和特征8): 針對(duì)候選推薦中的超鏈接、長(zhǎng)串?dāng)?shù)字等不可讀的情況,以及和原查詢文本無關(guān)等情況。
? 推薦查詢?cè)谠樵兊恼~權(quán)重表上的表現(xiàn)(特征9和特征10): 針對(duì)查詢對(duì)用戶意圖的滿足情況。
實(shí)際構(gòu)建數(shù)據(jù)集合時(shí),設(shè)計(jì)了一些對(duì)照實(shí)驗(yàn),具體如下:
? 不使用摘要詞特征的數(shù)據(jù)集,即在上面的10個(gè)特征中,只使用特征1~特征8,不包含特征9和特征10,這樣的設(shè)計(jì)是想考察有摘要詞特征和無摘要特征帶來的性能差異;
? 使用摘要詞權(quán)重表中的前k條結(jié)果,這樣設(shè)計(jì)的考慮主要是,一些查詢的摘要詞權(quán)重表可能非常的長(zhǎng),得分越低的詞說明其出現(xiàn)頻度越少,和查詢?cè)~之間的相關(guān)度越低,設(shè)置這一組實(shí)驗(yàn)可以分析出大概用多少特征是合適的。
綜合以上,我們總共構(gòu)造了下面17個(gè)數(shù)據(jù)集:
? 不使用摘要詞特征;
? 使用摘要詞特征,其中k=1,2,3,4,5,6,7,8,9,10,20,30,40,50,100和使用所有的摘要詞權(quán)重。
支持向量機(jī)(Support Vector Machine)[12]是一種廣泛使用的監(jiān)督式的學(xué)習(xí)方法,廣泛應(yīng)用于解決小樣本、非線性和高維模式識(shí)別問題。論文工作中選取支持向量機(jī)構(gòu)建分類器。
評(píng)價(jià)指標(biāo)借鑒了信息檢索相關(guān)的評(píng)價(jià)指標(biāo)中MAP(Mean Average Precison)和NDCG(Normalized Discounted Cumulative Gain)[13]兩項(xiàng)指標(biāo)。
MAP的計(jì)算公式如式(6)所示:
NDCG的計(jì)算公式如式(7)所示:
隨機(jī)選取了176個(gè)查詢中的50個(gè),對(duì)其重排序前后的前10條結(jié)果和某商業(yè)搜索引擎結(jié)果頁上呈現(xiàn)的查詢推薦采用Pooling[14]方法進(jìn)行三級(jí)手工標(biāo)注,將標(biāo)注為“2”的視為“好的查詢標(biāo)注”,將標(biāo)注為“1”和“0”的視為“不好的查詢標(biāo)注”。在上述兩個(gè)指標(biāo)上進(jìn)行評(píng)價(jià),結(jié)果如圖3所示。
圖3 查詢推薦結(jié)果比較
可以看到,加入摘要點(diǎn)擊特征挖掘用戶行為進(jìn)行重排序后,在隨機(jī)漫步結(jié)果與搜索引擎呈現(xiàn)結(jié)果兩組數(shù)據(jù)上都取得了不同程度的提高。在某商業(yè)搜索引擎呈現(xiàn)的查詢推薦數(shù)據(jù)上提高有限,主要是搜索引擎呈現(xiàn)數(shù)據(jù)只有9個(gè)結(jié)果,重排序的提升空間不大。
另外,我們對(duì)某搜索引擎2012年1月至3月中用戶點(diǎn)擊查詢推薦的情況進(jìn)行了統(tǒng)計(jì),并與隨機(jī)漫步和重排序后的結(jié)果列表進(jìn)行了匹配,選取了匹配率50%及以上,單個(gè)查詢匹配點(diǎn)擊數(shù)20以上的62個(gè)查詢,共涵蓋用戶點(diǎn)擊54 424次。經(jīng)過統(tǒng)計(jì),用戶在不同排序位置上的平均點(diǎn)擊分布如圖4所示。
圖4 優(yōu)化前后用戶點(diǎn)擊分布的比較
由上圖可以看出,經(jīng)過重排序后的列表,用戶點(diǎn)擊的分布更加集中在整個(gè)列表靠前的位置。這說明利用摘要點(diǎn)擊的信息可以有效地挖掘用戶的潛在意圖。
實(shí)驗(yàn)中選取了198個(gè)查詢中的70個(gè)查詢,將他們的候選推薦作為樣例。如果某一個(gè)查詢的候選推薦超過30個(gè),只取前30個(gè)作為樣例,總共獲得 2 030個(gè)樣例。
對(duì)于其中的每一個(gè)查詢推薦,采取和之前一致的Pooling方法進(jìn)行手工三級(jí)標(biāo)注。最終得到兩種樣例的比例為1 107∶923,基本平衡。
支持向量機(jī)選取臺(tái)灣大學(xué)林智仁(Lin Chih-Jen)開發(fā)的LIBSVM[15]。
在交叉驗(yàn)證比為3的前提下,不加摘要點(diǎn)擊特征得到的分類結(jié)果為Precision 0.789,Recall 0.686,F(xiàn)-Measure 0.640。在同樣的實(shí)驗(yàn)設(shè)置下,加入點(diǎn)擊特征后分類的結(jié)果如圖5所示。
圖5 加入點(diǎn)擊特征前后分類性能比較
對(duì)比結(jié)果我們可以看到,加入摘要點(diǎn)擊特征后,分類器的性能在Recall和F-Measure上獲得較顯著的提升,分析具體結(jié)果,主要原因是對(duì)于負(fù)例(不好的推薦查詢)分類Recall提升明顯。
在加入摘要點(diǎn)擊特征后,在k =9時(shí)分類器Precision最好,之后受到影響,這主要是因?yàn)檎藱?quán)重表中越靠后的詞可靠性越差,k=50之后分類器Precision獲得了一定的提升,這主要是因?yàn)闄?quán)重詞表中靠后的詞權(quán)重值非常小,此時(shí)對(duì)特征9的影響比較小,反而對(duì)特征10的影響顯著,對(duì)分類器的性能造成了較大的影響。
論文工作采用大規(guī)?!安樵?鏈接”二部圖上隨機(jī)漫步的方法生成了查詢推薦候選列表。在此基礎(chǔ)上充分考慮用戶的查詢意圖,結(jié)合用戶點(diǎn)擊摘要的信息,為每一個(gè)查詢構(gòu)建一個(gè)詞項(xiàng)得分表,以此為依據(jù)進(jìn)行候選列表重排序。實(shí)驗(yàn)證明該方法可以從迎合用戶意圖的角度提供更高質(zhì)量的查詢推薦。針對(duì)推薦列表中的噪聲,進(jìn)一步從用戶行為、文本特征和用戶意圖三個(gè)角度提取特征,利用支持向量機(jī)構(gòu)造分類器,對(duì)噪聲進(jìn)行識(shí)別和過濾,精度較高。從查詢推薦候選生成、根據(jù)用戶意圖進(jìn)行優(yōu)化到利用分類器進(jìn)行噪聲識(shí)別,形成了一個(gè)完整的查詢推薦流程。
回顧整個(gè)流程中的一些不足之處,還有很多進(jìn)一步工作可以繼續(xù)。
首先,可以考慮到結(jié)果頁位置的偏執(zhí),采用點(diǎn)擊模型(Click Model)優(yōu)化用戶意圖識(shí)別過程。
其次,可以采取一些規(guī)則,對(duì)二部圖上隨機(jī)漫步得到的集合進(jìn)行篩選和過濾,得到質(zhì)量更高的候選集合。
最后,可以利用網(wǎng)絡(luò)百科等知識(shí),對(duì)查詢推薦進(jìn)行多樣化處理,使得查詢推薦覆蓋盡量多的相關(guān)子話題。
[1] 維基百科.Web search engine[EB/OL]. [2012年6月5日]. http://en.wikipedia.org/wiki/Web_search_engine.
[2] 余慧佳, 劉奕群, 張敏, 等. 基于大規(guī)模日志分析的網(wǎng)絡(luò)搜索引擎用戶行為研究[C].第三屆學(xué)生計(jì)算語言學(xué)研討會(huì), 中國(guó)遼寧沈陽, 2006.
[3] Liu Y, Miao J, Zhang M, et al. How do users describe their information need: Query recommendation based on snippet click model. Expert Systems with Applications, 2011,38(11):13847-13856.
[4] Boldi P, Bonchi F, Castillo C, et al. The query-flow graph: model and applications[C]//Proceedings of CIKM ’08, New York, NY, USA, 2008.
[5] Craswell N, Szummer M. Random walks on the click graph[C]//Proceedings of SIGIR ’07, New York, NY, USA, 2007.
[6] Zhang Z, Nasraoui O. Mining search engine query logs for social filtering-based query recommendation[J]. Applied Soft Computing, 2008,8(4):1326-1334.
[7] Mei Q, Zhou D, Church K. Query suggestion using hitting time[C]//Proceedings of CIKM ’08, New York, NY, USA, 2008.
[8] Song Y, Zhou D, He L. Query suggestion by constructing term-transition graphs[C]//Proceedings of WSDM ’12, New York, NY, USA, 2012.
[9] Cao H, Jiang D, Pei J, et al. Context-aware query suggestion by mining click-through and session data[C]//Proceedings of KDD ’08, New York, NY, USA, 2008.
[10] Sadikov E, Madhavan J, Wang L, et al. Clustering query refinements by user intent[C]//Proceedings of the 19th international conference on World wide web. ACM, 2010: 841-850.
[11] Broder A. A taxonomy of web search[C], 2002.
[12] Boser B E, Guyon I M, Vapnik V N. A training algorithm for optimal margin classifiers[C]//Proceedings of COLT ’92, New York, NY, USA, 1992.
[13] Rvelin K J A, Kek A L A, Inen J. Cumulated gain-based evaluation of IR techniques[J]. ACM Transactions on Information Systems (TOIS), 2002,20(4):422-446.
[14] Jones K S, van Rijsbergen C J. Information retrieval test collections[J]. Journal of documentation, 1976,32(1):59-75.
[15] Chang C C, Lin C J. LIBSVM: a library for support vector machines[J]. ACM Transactions on Intelligent Systems and Technology (TIST), 2011,2(3):27.