基于大規(guī)模中文搜索引擎的搜索日志挖掘

摘要：從中英文用戶的搜索習慣差異的角度出發(fā)，引入中文分詞技術對中文搜索引擎的搜索日志進行了分析。重點分析了用戶輸入搜索詞的一些規(guī)律，包括選擇的語言、搜索詞的長度和頻率、高級搜索技巧的使用以及搜索詞的修改情況；還提出了用戶提交搜索詞的模型，給出了歷史搜索詞對搜索結果的影響因子算法。

關鍵詞：搜索引擎； 數(shù)據(jù)挖掘； 搜索日志； 分詞

中圖分類號：TP391文獻標志碼：A

文章編號：1001－3695(2008)06－1663－03

0引言

隨著互聯(lián)網信息的急劇膨脹，搜索引擎已經成為互聯(lián)網用戶必不可少的助手。目前幾大主要的搜索引擎都采用如下的工作原理：用戶輸入搜索關鍵字，搜索引擎將關鍵字與預先存儲的網頁倒排文檔進行匹配；然后按照一定的算法輸出網頁URL集合。這種簡單地采用搜索關鍵字匹配的方法往往無法反映用戶的真實需求。因此，對用戶的搜索行為進行深層次的分析將有助于提高搜索引擎的質量。

國內外有不少對搜索引擎用戶行為分析的研究成果。文獻[1]通過分析用戶點擊的URL類型，對用戶的搜索需求進行分類；文獻[2]對大型英文搜索引擎日志進行分析，總結了一些英文用戶的搜索規(guī)律；文獻[3~5]著重分析了中文搜索引擎用戶的一些搜索規(guī)律。其中，文獻[4，5]還對用戶的查詢串和點擊URL進行擬合，發(fā)現(xiàn)擬合結果符合Heaps定律。但是目前針對中文搜索引擎日志的研究，很少有從中、英文語言的差異以及中、英文搜索引擎用戶的搜索習慣差異的角度進行分析；此外，專門針對用戶查詢詞的數(shù)據(jù)挖掘較少，而查詢詞是用戶搜索意圖最直接的體現(xiàn)；已有的針對搜索引擎日志的研究大多是基于北京大學天網搜索引擎或者某個專用領域的搜索引擎，這些搜索引擎的用戶群規(guī)模有限，不能真正反映目前主流的大規(guī)模商業(yè)搜索引擎的用戶搜索行為規(guī)律。

本文選擇Sogou搜索引擎日志作為研究對象，從中英文語言差異的角度出發(fā)引入中文分詞算法，更深一步地分析中文搜索引擎用戶的搜索規(guī)律。并且，本文還重點分析了用戶的查詢詞，給出了用戶搜索行為模型，通過計算歷史查詢詞對搜索結果的影響改善搜索引擎的結果。

1數(shù)據(jù)對象及相關工具介紹

1．1搜索日志

本文選擇Sogou搜索引擎提供的2006年8月搜索日志進行分析。該日志已經對原始數(shù)據(jù)進行了清理，去除了無效搜索，得到有效搜索記錄為21 362 462條。此外本文在對查詢串進行分詞處理時選擇2006年8月1日的搜索日志。其中，有效搜索記錄為1 030 577條。

Sogou提供的搜索日志為純文本文件，數(shù)據(jù)格式為：用戶ID\[查詢詞]\該URL在返回結果中的排名\用戶點擊的順序號\用戶點擊的URL。本文主要對其中的“查詢詞”進行分析。

1．2分詞工具

本文的中文分詞部分實驗采用中國科學院計算技術研究所開發(fā)的基于多層隱馬爾科夫模型的漢語詞法分析系統(tǒng)ICTCLAS(Institute of Computing Technology，Chinese lexical analysis system)。該系統(tǒng)提供開源分詞模塊，能夠對中文語句進行有效分詞。

分詞采用的詞典包括三部分：a)中國科學院計算技術研究所提供的Dictionary Free Build0705。b)由Sogou提供的基于互聯(lián)網語料環(huán)境的高頻詞庫v1．0，該詞庫涵蓋了中文互聯(lián)網1億頁面以上出現(xiàn)的15萬條高頻詞。c)本文對2006年8月Sogou搜索引擎用戶輸入的查詢詞進行分析，選擇添加了部分高頻的查詢詞。



2搜索日志初步分析

2．1查詢語言的分析

通過對搜索日志的統(tǒng)計，得到2006年8月總計查詢次數(shù)為21 362 462。其中，純英文字符查詢次數(shù)為2 064 155，占總體的9．7% ；中英文混合查詢次數(shù)為1 823 077，占總體的8．5%；少量非常規(guī)字符，如日文、不合法字符，對分析結果的影響可以忽略不計；其余全部為中文查詢，占總體的81．8%。可見，目前中文搜索引擎的用戶主要還是采用中文查詢詞進行搜索。

2．2查詢詞長度的分析

為區(qū)分分詞前后用戶查詢詞的表示方式，本文定義用戶原始輸入的搜索關鍵字為“查詢串”，一個查詢串可以由多個短語組成，相鄰兩個短語之間由空格隔開。短語經過分詞后形成詞組，一個短語可以分詞成一個或多個詞。

由于中英文天然的差異，導致對中英文搜索引擎搜索日志的分析產生不同的結果。英文的句子由多個單詞組成，兩個單詞之間由空格隔開。因此，英文查詢串必然由多個獨立的單詞組成。中文的句法與英文完全不同，單詞之間沒有空格；并且，雖然中文搜索引擎用戶可以在輸入查詢詞的時候用空格隔開，但是對查詢日志的分析顯示，很少有用戶愿意將一個短語徹底分解成詞組后輸入。從表1左側數(shù)據(jù)可以看出，約90%的用戶只輸入一個短語進行查詢，很少有人輸入四個以上的短語。用戶的平均查詢短語數(shù)為1．14。這顯然與文獻[2]中的平均值2．35相差較大。

考慮到中文和英文的句子成分（如主語、謂語等）以及詞性（名詞、動詞等）存在著共同點，因此筆者猜測對中文查詢短語進行分詞，然后再進行分析所得的結果可能更接近英文搜索引擎日志的分析結果。于是本文采用詞典以及分詞算法對2006年8月1日的查詢串進行分詞處理，得到表1右側數(shù)據(jù)。用戶的平均查詢詞數(shù)為2．27，與文獻[2]中的值基本相符。

2．3查詢詞頻分析

本文對用戶輸入的查詢短語出現(xiàn)的頻率進行分析，得到圖1所示的結果。其中，橫軸表示查詢詞被搜索的頻率；縱軸表示不同頻率的查詢詞占全部查詢詞的比例。在對查詢短語進行分詞之前，超過40%的短語搜索數(shù)僅為1，超過90%的短語被搜索的次數(shù)小于10。可見用戶的輸入內容比較分散。由于8月1日查詢短語的頻率分布曲線與當月的分布曲線基本吻合，筆者選擇當日的搜索日志進行分詞處理。分詞之后，曲線相對平緩一些，有相當一部分比例的詞被搜索的次數(shù)超過100。

此外還將每個查詢短語被搜索的次數(shù)進行降序排列，分析y=∑nx=1px的曲線。其中：x為查詢短語的離散序列；px為查詢短語x被搜索的次數(shù)占總搜索數(shù)的比例。圖2表明在分詞之前，約20%的短語占了80%的搜索量，這與文獻[5]中的數(shù)據(jù)基本相符。但是當筆者對查詢短語進行分詞后，發(fā)現(xiàn)用戶的搜索熱點比預期的還要集中，10%的詞約占了85%的搜索量。于是筆者專門分析了8月1日及當月十大熱門查詢詞。表2顯示，8月1日十大熱門查詢占當日全部查詢的28．25%，這相對于當月十大查詢詞所占的4．9%的比例偏高。又如“張玉鳳”這個查詢詞，8月1日的搜索量占該詞當月搜索量的一半以上。出現(xiàn)這種現(xiàn)象的原因可能是由于一些突發(fā)事件的存在，如某個重要紀念日、八卦新聞等，會導致某些詞的搜索量急劇增加。這對于設計查詢cache的時候具有很大的參考價值。除了采用文獻[5]中建議的LLU替代算法，一些熱門查詢詞可以考慮設置較高的優(yōu)先級，以減少由于算法的缺陷帶來的消耗。此外8月1日的十大查詢詞有一半出現(xiàn)在當月的十大查詢詞中，可見熱門的查詢存在一定的連續(xù)性。

2．4高級搜索方式分析

Sogou提供了以下幾種高級搜索方式：雙引號（“”）用于精確查詢；“site：”允許在指定網站內搜索；“http://”可以直接搜索類似的網頁地址；減號（-）用于剔除無關資料；“filetype：”用于制定搜索文檔類型。表3顯示了用戶使用高級搜索技巧的情況。只有1．5%的用戶采用了Sogou提供的高級搜索技巧，其中幾乎沒有人使用減號，很少用戶使用“filetype：”。出現(xiàn)這種情況的原因可能有兩點：a)用戶并不知道有哪些高級搜索技巧；b)使用高級搜索技巧比較麻煩。

2．5查詢詞的修改情況

用戶對查詢詞的修改主要包括以下幾種情況：增加、減少、部分替換以及完全更換查詢詞。為使分析結果更準確，本文首先對原始查詢串進行分詞，然后分析查詢詞的修改情況。分析結果如表4所示。其中增加、減少以及部分替換查詢詞這三種方式比較具有參考意義，部分替換方式的比例在這三者中最高，很少有用戶通過減少查詢詞進一步搜索，這比較符合用戶的搜索習慣。完全更換查詢詞的比例約占2/3，其原因可能是用戶發(fā)現(xiàn)最初的搜索詞不能表達其搜索目的。此外，除了增加查詢詞這種修改方式，其余的方式都舍棄了部分或全部的上一次查詢詞。但是，這些被舍棄的查詢詞都在某種程度上反映了用戶的搜索意圖，因此這些詞不應當被忽視。

3查詢詞的影響因子分析

用戶進行搜索的過程可以看做是一個查詢詞取舍的過程。在不改變搜索意圖的前提下，用戶首先輸入一個查詢詞集合（雖然中文搜索引擎用戶可能會輸入一個句子，也可以通過分詞把它看做是一個查詢詞集合），搜索引擎將根據(jù)這個查詢詞集合返回一個URL集合。用戶根據(jù)得到的URL集合修改查詢詞，可能是增加、減少或替代部分查詢詞，得到新的查詢詞集合；搜索引擎則又會根據(jù)新的查詢詞集合返回新的URL集合。如此反復，直到用戶認為搜索引擎返回的URL集合中包含了用戶需要的信息，或用戶放棄搜索。

假設用戶在某個搜索session周期內第i次輸入的查詢?yōu)閝i=(w1，w2，…，wn)。其中：wj為查詢qi的第j個查詢詞。另設一個搜索session的歷史查詢詞集合為T。用戶的搜索行為模型如下。

定義1用戶搜索行為模型

a）初始化T，并令T=q1。q1為一個搜索session的初始查詢。

b）如果qi=qi-1，本次查詢保持不變。用戶沒有修改查詢詞，而是點擊了搜索結果中的另一個URL。此時，T保持不變，但是T中查詢詞的重要性可能會發(fā)生變化。

c）如果qi≠qi-1并且qi∩T≠0，表示用戶修改了查詢詞，但是搜索意圖沒有發(fā)生變化。此時，T=T∪qi。

d）如果qi∩T=0，表示用戶更換了搜索意圖。此時T=qi。

從定義1可以發(fā)現(xiàn)，不管用戶是否改變了搜索意圖，最終集合T中的單詞集合為反映用戶當前搜索意圖的查詢詞集合。因此，只需要計算T中各查詢詞的影響因子即可。為了降低計算復雜度，本文假設每次用戶輸入的查詢中，各查詢詞的重要性是相等的，即對于每一個qi=(w1，w2，…，wn)，qi中的每一個查詢詞wj在qi中的影響因子都為1/n。事實上，也很難判斷用戶每次輸入的查詢詞中哪一個更為重要一些。

顯然，對于定義1中的條件a）和d），T中查詢詞的影響因子可以直接由qi傳遞獲得，且所有查詢詞的影響因子都為1/n。條件a）和d）都可以看做是一個初始查詢，初始查詢中各查詢詞的影響因子均為1/n。本文著重分析條件b）和c）中各歷史查詢詞的影響因子。

很明顯，這個時候T中所有的查詢詞中，對搜索結果有影響的只有最后一次輸入的查詢qi中的查詢詞，且其影響因子均為1/n，等同于qi中各查詢詞的初始影響因子。這就是目前大多數(shù)搜索引擎采用的搜索方式。

4結束語

本文從中、英文語言及用戶搜索習慣差異的角度出發(fā)，首次引入中文分詞技術對大型中文搜索引擎的搜索日志進行了分析，并重點分析了用戶查詢詞的特征，從中發(fā)現(xiàn)了一些中文用戶使用搜索引擎的行為規(guī)律。本文還考慮到用戶的歷史查詢詞在一定程度上反映了用戶的搜索意圖，因此認為在進行搜索的時候不應當忽略歷史查詢詞對搜索結果的影響。本文給出了一個搜索行為模型定義，并計算出歷史查詢詞的影響因子，該影響因子將有助于提高搜索結果的準確性。

后續(xù)的研究將結合用戶點擊的網頁，量化分析歷史查詢詞所反映的用戶搜索意圖，通過計算調整歷史查詢詞的衰減因子d并將歷史查詢詞的影響因子應用到搜索引擎中，分析該方法對搜索結果的影響大小。

參考文獻：

［1］LIU Yi－qun，ZHANG Min，RU Li－yun，et al．Automatic query type identification based on click through information[C]//Proc of Asia Information Retrieval Symposium.2006:593－600．

[2]SILVERSTAIN C，MARAIS H， HENZINGER M，et al． Analysis of a very large Web search engine query log[J].ACM SIGIR Forum，1999，33(1):6－12.

[3]YU Hui－jia， LIU Yi－qun， ZHANG Min， et al．Research in search engine user behavior based on log analysis[J]．Journal of Chinese Information Proceeding，2007，21(1):109－114.

[4]WANG Ji－min， CHEN Chong， PENG Bo． Analysis of the user log for a large－scale Chinese search engine[J]．Journal of South China University of Technology:Natural Science Edition，2004，32(suppl):1－5.

[5]WANG Jian－yong， LI Xiao－ming， SHAN Song－wei，et al．Web search engine: characteristics of user behaviors and their implication[J].Science in China:Series E，2001，31(4): 372－384.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文