基于概念模型的Web查詢關(guān)系分類

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

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

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

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

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

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

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

8、性和稀疏性兩個(gè)特點(diǎn)，即不同Web查詢的總量非常大，但單個(gè)Web查詢平均出現(xiàn)的次數(shù)又比較少。因此Web查詢關(guān)系的挖掘同時(shí)面臨著挖掘結(jié)果集龐大，難于管理和支持度閾值難以確定兩大難題。前者是因?yàn)榇罅康膯蝹€(gè)Web查詢?cè)斐闪私M合爆炸，而后者是因?yàn)榇蟛糠諻eb查詢關(guān)系支持度有限，較大的支持度閾值很難獲得足夠的Web查詢關(guān)系，較小的支持度閾值又很難將挖掘結(jié)果和背景噪聲區(qū)分開來。但是如果用Web查詢概念表示單個(gè)Web查詢，由于很多Web查詢可以用同一個(gè)概念表示，Web查詢的海量性和稀疏性都得到了解決。因此，本項(xiàng)研究提出建立Web查詢的概念層次，將Web查詢關(guān)系挖掘轉(zhuǎn)化為Web查詢概念關(guān)系的挖掘。其次，由于先前

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

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

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

12、類法。該分類法中的分類應(yīng)具備可分性，并能為Web查詢關(guān)系分類的應(yīng)用提供指導(dǎo)。3） 研究基于概念模型的Web查詢關(guān)系自動(dòng)分類模型：本項(xiàng)研究將分析概念層次上Web查詢關(guān)系自動(dòng)分類的可行性并嘗試用機(jī)器學(xué)習(xí)的方法建立概念層次上Web查詢關(guān)系的自動(dòng)分類模型。該模型可以用于自動(dòng)從大規(guī)模數(shù)據(jù)中按照預(yù)定義的Web查詢分類法自動(dòng)抽取Web查詢關(guān)系。n 參考文獻(xià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