基于概念模型的Web查詢關系分類

1、 基于概念模型的Web查詢關系分類BA07011021 曹歡歡計算機科學技術學院caohuann 引言隨著Web技術的飛速發(fā)展，搜索引擎已成為人們獲取信息的一種重要工具。而記錄用戶查詢詞和點擊頁面的搜索引擎日志既反映了用戶和搜索引擎的交互模式，又在一定程度上真實反映了用戶滿意度。因此，搜索引擎日志的分析與挖掘對建立用戶行為模型、興趣模型、改進搜索引擎為用戶提供個性化搜索服務的能力以及評價搜索引擎性能等很多方面具有重要價值。近年來，由于搜索引擎用戶的快速增長，搜索引擎日志的規(guī)模也與日俱增。目前，主流搜索引擎的用戶日流量都超過千萬量級，搜索引擎日志的信息量呈現(xiàn)爆炸性增長的態(tài)勢。同時，搜索引擎日志所

2、包含的信息種類也大大豐富，不僅包含了用戶提交的Web查詢，還記錄了用戶點擊頁面的詳細信息，如在返回結果中的排序，停留時間等。一些搜索引擎服務商甚至推出了嵌入瀏覽器的搜索引擎工具欄，同傳統(tǒng)的基于網(wǎng)頁的搜索引擎界面相比，這種新工具可以采集更為豐富的信息，如用戶在點擊搜索引擎返回的結果頁面后，通過點擊該頁面上的鏈接發(fā)生的進一步瀏覽行為等。搜索引擎日志信息的日益豐富，也在很大程度上推動了基于搜索引擎日志挖掘方法的研究。隨著這一領域研究的蓬勃發(fā)展，出現(xiàn)了很多基于搜索引擎日志挖掘的應用，如基于用戶點擊信息的Web查詢聚類、通過挖掘相關Web查詢來構造候選擴展集的Web查詢擴展、基于相關Web查詢的查詢推薦

3、、基于點擊行為分布特性的Web查詢分類、基于用戶搜索行為的搜索引擎?zhèn)€性化服務等等。這些新的應用在一定程度上給當前的搜索引擎帶來了生機和活力，但是基于搜索引擎日志數(shù)據(jù)的挖掘能做的絕不僅僅是這些而已，在技術創(chuàng)新和實際應用上都還有很大的發(fā)展空間。n 研究現(xiàn)狀本項目所研究的Web查詢關系分類和Web查詢概念模型屬于Web挖掘領域的熱點研究課題。目前國內外基于搜索引擎日志的Web查詢關系研究主要有兩大類：第一類研究著眼于Web查詢關系的分析和分類。這一類工作主要有：Rieh 分析了搜索引擎日志中的用戶Web查詢，提出一種Web查詢關系的分類方法 10；Bruza，Jansen和Lau等人研究了用戶在We

4、b查詢會話中輸入的若干Web查詢之間的關系及其分布特征2，8，9；這一類工作只關注如何分析Web查詢關系，而不涉及如何得到Web查詢關系。而且這些Web查詢關系的分析和分類也缺乏明確的應用背景，從而制約了該研究方向的進一步發(fā)展。陳紅濤等在14中基于分析結果提出了一種歷史搜索詞對搜索結果的影響因子算法，陳磊等通過分析用戶Web查詢關系分析搜索引擎的廣告效果15。另一類研究著眼于Web查詢關系的挖掘。其中一些工作主要基于“點擊集合“（click-through）信息，其主要思想是通過分析Web查詢點擊結果的相關性找到Web查詢的關系。主要包括：D. Beeferman等人提出一種基于Web查詢-點

5、擊URL二部圖的圖聚類算法來得到相關Web查詢的聚類 1；J.R.Wen 等人提出一種基于點擊網(wǎng)頁的特征向量構造方法來構造Web查詢的特征向量，并以此對Web查詢聚類來發(fā)現(xiàn)Web查詢的相關性 5，11； Yates等人研究了一個大規(guī)模的搜索引擎日志，并分析了基于點擊信息的Web查詢之間的關系13。這些工作主要著眼于從大量用戶的點擊行為判斷Web查詢的相關性，往往只能找到相似的Web查詢，而對于類似“次貸危機”，“金融風暴”這種關聯(lián)的概念很難發(fā)現(xiàn)其內在聯(lián)系。另一些工作主要基于“會話“（session）信息，其主要思想是通過分析用戶的會話發(fā)現(xiàn)Web查詢的關系。用戶的會話信息表示為若干用戶提交的We

6、b查詢，如果一些Web查詢經(jīng)常同時出現(xiàn)在一起，那么它們很有可能是相關的。這些工作主要有：J. Wei 等人提出一種通過在會話日志中挖掘關聯(lián)規(guī)則擴展Web查詢的方法12；Fonseca等人提出在搜索引擎日志中挖掘Web查詢關聯(lián)規(guī)則來發(fā)現(xiàn)Web查詢之間的聯(lián)系6，并依據(jù)Web查詢關系建立Web查詢關系圖，將關系圖中的極大完全圖作為Web查詢概念7。上述分析表明，目前的工作缺乏一種將Web查詢關系的挖掘和Web查詢關系的分析進行有效結合的方法，它們或者只涉及對Web查詢關系的分析而不考慮Web查詢關系的獲取，或者只考慮Web查詢關系的挖掘而缺乏對挖掘結果的分析和分類。相比之下，如何進行Web查詢關系的

7、自動分類是一個新的課題，而在Web查詢關系的分類中引入概念模型更是一種新的嘗試。申請人在Web查詢關系的抽取和Web查詢的概念模型建模方面具備了一定的工作基礎，先后在Web數(shù)據(jù)挖掘方面的國際頂級會議SIGIR、SIGKDD和WWW上發(fā)表了相關論文。在KDD2008論文3，我們研究了基于查詢上下文和查詢概念的查詢詞推薦問題；在WWW2009論文4，我們研究了如何用vlHMM模型對復雜的查詢詞和點擊關系進行建模以及此模型的潛在應用。n 研究思路本項研究旨在通過挖掘搜索引擎日志自動獲取分類的Web查詢關系，這一課題在理論研究和實際應用中都有著重要的意義。首先，在搜索引擎日志中，Web查詢同時具有海量

8、性和稀疏性兩個特點，即不同Web查詢的總量非常大，但單個Web查詢平均出現(xiàn)的次數(shù)又比較少。因此Web查詢關系的挖掘同時面臨著挖掘結果集龐大，難于管理和支持度閾值難以確定兩大難題。前者是因為大量的單個Web查詢造成了組合爆炸，而后者是因為大部分Web查詢關系支持度有限，較大的支持度閾值很難獲得足夠的Web查詢關系，較小的支持度閾值又很難將挖掘結果和背景噪聲區(qū)分開來。但是如果用Web查詢概念表示單個Web查詢，由于很多Web查詢可以用同一個概念表示，Web查詢的海量性和稀疏性都得到了解決。因此，本項研究提出建立Web查詢的概念層次，將Web查詢關系挖掘轉化為Web查詢概念關系的挖掘。其次，由于先前

9、的Web查詢關系挖掘算法沒有細分挖掘得到的Web查詢關系的類型，導致Web查詢關系的利用具有很大的盲目性和局限性。例如，會話日志挖掘得到的Web查詢關系多達七類 10，將這些Web查詢關系全都用于單一的應用有很多不妥之處。或者對于拼寫改正的Web查詢關系，將其用于隱式的Web查詢優(yōu)化要好于在Web查詢推薦上的應用。因此，本課題將研究建立一種面向應用的Web查詢關系分類法，以及Web查詢關系的自動分類模型，以有效的管理挖掘出的Web查詢關系進行。n 研究內容為了實現(xiàn)概念層次上Web查詢關系的自動分類，本課題首先將研究Web查詢的概念模型，將傳統(tǒng)的Web查詢關系挖掘轉化為概念層次上的Web查詢關系

10、挖掘。其次，本課題將研究合理的Web查詢關系分類法，從而細化所發(fā)現(xiàn)的Web查詢關系以方便進一步的應用。最后研究如何用機器學習方法建立一個Web查詢關系的自動分類模型。根據(jù)該模型，可以推廣挖掘出的Web查詢關系，當遇到新的搜索引擎日志時，Web查詢關系的發(fā)現(xiàn)和分類都將大大簡化。這種增量式的挖掘方式，對于處理頻繁更新的搜索引擎日志具有十分重要的意義。本項研究成果對于綜合利用搜索引擎日志信息,解決用戶搜索行為建模、搜索引擎?zhèn)€性化服等關鍵問題的解決有著重要意義。本項研究還將結合理論研究提出的方法，開發(fā)一個面向搜索引擎日志的Web查詢關系挖掘原型系統(tǒng)。結合系統(tǒng)的實際性能，對Web查詢關系自動分類模型進行

11、有效性檢驗，并根據(jù)系統(tǒng)在處理大規(guī)模真實數(shù)據(jù)中存在的問題，對我們的方法作進一步完善。本項目擬從下列三個方面開展研究：1） 研究基于概念模型的Web查詢關系挖掘方法：本項目將研究一種基于Web查詢聚類的自動生成Web查詢概念層次的方法。Web查詢概念層次的建立可以支持概念層次上的Web查詢關系挖掘，更好地抽象挖掘出的知識，以解決搜索引擎日志數(shù)據(jù)的稀疏性和背景噪聲等問題。2） 研究面向應用的可分性Web查詢關系分類法：本項研究將針對現(xiàn)有Web查詢分類法的不足，面向Web查詢推薦、Web查詢擴展及Web用戶興趣跟蹤等應用，在深入分析Web查詢關系實際應用背景的基礎上，提出一種面向應用的Web查詢關系分

12、類法。該分類法中的分類應具備可分性，并能為Web查詢關系分類的應用提供指導。3） 研究基于概念模型的Web查詢關系自動分類模型：本項研究將分析概念層次上Web查詢關系自動分類的可行性并嘗試用機器學習的方法建立概念層次上Web查詢關系的自動分類模型。該模型可以用于自動從大規(guī)模數(shù)據(jù)中按照預定義的Web查詢分類法自動抽取Web查詢關系。n 參考文獻1 D Beeferman, A Berger. Agglomerative clustering of a search engine query log. In SIGKDD00. 2000.2 PD Bruza, S Dennis. Query re

13、formulation on the Internet: Empirical data and the Hyperindex search engine. In RIAO97. 1997.3 Huanhuan Cao, Daxin Jiang, Jian Pei, Enhong Chen and Hang Li. Towards context-aware search by learning a large variable length Hidden Markov Model from search logs. To appear in WWW09 as Full Paper.4 Huan

14、huan Cao, Daxin Jiang, Jian Pei, Qi He, Zhen Liao, Enhong Chen and Hang Li. Context-aware query suggestion by mining click-through and session data. In KDD08, pages 875-883, 2008. 5 H Cui, JR Wen, JY Nie, WY Ma. Probabilistic query expansion using query logs. In WWW02. 2002.6 BM Fonseca, PB Golgher,

15、 ES de Moura, N Ziviani. Using association rules to discover search engine related queries. Web Congress, 2003.7 BM Fonseca, P Golgher, B Pssas, B Ribeiro-Neto. Concept-based interactive query expansion. In CIKM05. 2005.8 BJ Jansen, A Spink, T Saracevic. Real life, real users, and real needs: a stud

16、y and analysis of user queries on the web. Information Processing and Management, 2000.9 T Lau, E Horvitz. Patterns of search:analyzing and modeling Web query refinement. In 7th international conference on User modeling, 1999.10 SY Rieh. Patterns and sequences of multiple query reformulation in web search: a preliminary study. In ASIST01. 2001.11 JR Wen, JY Nie, HJ Zhang. Query clustering using query logs. ACM Transactions on Information Systems, 2002.12 J Wei, S Bressan, BC Ooi. Mining term association rules for automatic global query expansion：methodolo