基于個(gè)性化詞典的搜索引擎查詢擴(kuò)展模型

　　摘要：為了向用戶提供個(gè)性化的web信息檢索服務(wù)，該文對(duì)已有的個(gè)性化服務(wù)模型加以改進(jìn)，介紹了一種基于用戶個(gè)性化詞典的搜索引擎查詢擴(kuò)展模型。該模型采用用戶個(gè)性化詞典替換傳統(tǒng)的全局詞典，并利用查詢擴(kuò)展策略實(shí)現(xiàn)個(gè)性化服務(wù)。用戶個(gè)性化詞典能夠優(yōu)化用戶興趣建模過程，使用戶興趣模型更加準(zhǔn)確，從而優(yōu)化最終生成的擴(kuò)展詞。借助擴(kuò)展詞，用戶可以在搜索引擎上更方便地檢索到更符合自己興趣的網(wǎng)頁。實(shí)驗(yàn)表明該模型能夠通過搜索引擎，向用戶提供有效可行的個(gè)性化服務(wù)。
　　關(guān)鍵詞：用戶個(gè)性化詞典；二級(jí)向量；查詢擴(kuò)展；個(gè)性化服務(wù)；搜索引擎
　　中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2012）28-6764-07
　　網(wǎng)絡(luò)是人們獲取知識(shí)和傳遞信息的橋梁。然而，隨著近年來internet的高速發(fā)展，網(wǎng)絡(luò)上信息的數(shù)量也呈現(xiàn)指數(shù)級(jí)的增長，在這一背景下，互聯(lián)網(wǎng)使用者往往無法輕松找到需要的信息。搜索引擎的出現(xiàn)使我們信息檢索方面的需求在一定程度上得到解決。目前，搜索引擎的概念已經(jīng)深入人心，成為進(jìn)行互聯(lián)網(wǎng)信息檢索必不可少的工具。但它存在如下幾個(gè)方面的局限性。
　　1）搜索結(jié)果集龐大，用戶為找到其真正感興趣的信息，耗費(fèi)大量的時(shí)間和精力。
　　2）不同用戶在不同時(shí)期采用同樣的查詢關(guān)鍵詞請(qǐng)求所得到的搜索結(jié)果幾乎相同，對(duì)用戶來說不能提供個(gè)性化的服務(wù)。
　　3）用戶在使用搜索引擎檢索時(shí)帶有一定的目的性，但往往由于該用戶相關(guān)領(lǐng)域知識(shí)的不足以及搜索引擎查詢接口的局限性，導(dǎo)致用戶不能清楚地表達(dá)其信息需求[2]。
　　針對(duì)傳統(tǒng)搜索引擎不能提供面向用戶的個(gè)性化服務(wù)這一缺陷，大量的專家學(xué)者開始研究查詢擴(kuò)展技術(shù)，并在此領(lǐng)域有所突破。文獻(xiàn)[1]根據(jù)文檔分析，提出局部共現(xiàn)的思想，利用詞項(xiàng)與所有查詢?cè)~在局部文檔集合中的共現(xiàn)程度以及在語料集中的全局統(tǒng)計(jì)信息來評(píng)估擴(kuò)展詞的質(zhì)量，選擇合適的擴(kuò)展詞；文獻(xiàn)[3-5]通過分析用戶瀏覽歷史，主要采用關(guān)聯(lián)規(guī)則進(jìn)行查詢擴(kuò)展；文獻(xiàn)[6]利用HITS和TextRank技術(shù)提取用戶主題，并結(jié)合關(guān)聯(lián)規(guī)則進(jìn)行查詢擴(kuò)展；而文獻(xiàn)[7]提出了一種基于二級(jí)向量的搜索引擎?zhèn)€性化服務(wù)模型SEPMBDVD（Search Engine Personalization Model Based on Double Vector Description），其實(shí)質(zhì)也是利用對(duì)用戶瀏覽的歷史網(wǎng)頁進(jìn)行挖掘而得的用戶興趣模型生成與用戶輸入的查詢關(guān)鍵詞配對(duì)的擴(kuò)展詞。通過擴(kuò)展詞加入，使用戶在利用搜索引擎檢索的時(shí)候能夠得到符合用戶興趣或者興趣偏好的結(jié)果，經(jīng)過實(shí)驗(yàn)驗(yàn)證該模型具有查準(zhǔn)率高，反應(yīng)速度快等優(yōu)點(diǎn)。這種查詢擴(kuò)展模型依賴于用戶興趣模型，文獻(xiàn)[7]采用的是二級(jí)向量模型，即通過一組關(guān)鍵詞向量和擴(kuò)展詞向量描述用戶興趣，這種模型是基于一個(gè)全局詞典對(duì)用戶瀏覽的歷史網(wǎng)頁進(jìn)行描述、聚類挖掘以后生成的。整個(gè)模型結(jié)構(gòu)如圖1所示。
　　全局詞典由于詞匯量過大，詞匯太雜，無法體現(xiàn)用戶的興趣等原因，會(huì)對(duì)用戶興趣模型的生成造成較大的影響，從而影響到詞擴(kuò)展的效果。因此本文使用個(gè)性化詞典替換全局詞典，并采用查詢擴(kuò)展策略實(shí)現(xiàn)個(gè)性化服務(wù)，設(shè)計(jì)出一種基于個(gè)性化詞典的搜索引擎查詢擴(kuò)展模型QEMBUPDSE（Query Expansion Model Based on User Personalization Dictionary for Search Engine）。該模型能夠通過個(gè)性化詞典優(yōu)化用戶興趣模型，從而優(yōu)化查詢擴(kuò)展詞，使得用戶的個(gè)性化搜索更快，更準(zhǔn)確。
　　1 基于個(gè)性化詞典的搜索引擎查詢擴(kuò)展模型
　　基于個(gè)性化詞典的搜索引擎查詢擴(kuò)展模型從用戶瀏覽歷史網(wǎng)頁描述開始就利用個(gè)性化詞典的兩級(jí)詞典，即關(guān)鍵詞詞典和擴(kuò)展詞詞典，形成網(wǎng)頁的二級(jí)向量描述，接著通過數(shù)據(jù)挖掘手段更直接的生成用戶興趣的二級(jí)向量模型，最后根據(jù)用戶輸入的關(guān)鍵詞進(jìn)行查詢擴(kuò)展，如圖2所示。
　　2.1 個(gè)性化詞典的定義與實(shí)現(xiàn)
　　根據(jù)文獻(xiàn)[10]，個(gè)性化詞典UPD（User Personalization Dictionary）由關(guān)鍵詞詞典（KeyDict）和擴(kuò)展詞詞典（ExDict）兩級(jí)構(gòu)成，位于兩級(jí)詞典中的詞分別定義為關(guān)鍵詞和擴(kuò)展詞。每一級(jí)詞典中包含n個(gè)（n由人為設(shè)定）由詞和詞權(quán)構(gòu)成的二元組。關(guān)鍵詞通常表示用戶瀏覽興趣，詞的權(quán)值越大，表示在用戶興趣中的重要性越大。而擴(kuò)展詞用于描述用戶在興趣點(diǎn)上的興趣偏好，從而在查詢擴(kuò)展時(shí)提供符合用戶偏好的擴(kuò)展檢索詞。
　　特定用戶的UPD能夠充分表達(dá)用戶對(duì)信息需求的傾向性，同時(shí)對(duì)基于二級(jí)向量的用戶興趣模型提供支持，是一種符合用戶興趣的私有詞典，在詞典設(shè)計(jì)上主要考慮如下主要原則：
　　1）網(wǎng)頁文檔集合中，某詞出現(xiàn)的頻度越高，該詞對(duì)用戶特征的描述能力越強(qiáng)。
　　2）網(wǎng)頁文檔集合中，包含某詞的網(wǎng)頁數(shù)越多，該詞對(duì)用戶特征的描述能力越強(qiáng)。
　　3）對(duì)于一些網(wǎng)頁中比較常用的，沒有檢索價(jià)值的詞，我們稱之為網(wǎng)頁頻繁詞，如：評(píng)論、版權(quán)、文章等，在詞典中應(yīng)該被過濾掉，以免對(duì)用戶的個(gè)人描述帶來噪音。
　　在公式1中S為網(wǎng)頁集合，T為詞空間，W（t，S）為詞t在S中的權(quán)重，tf（t，S）為詞t在S中的詞頻，N為S包含的網(wǎng)頁總數(shù)，nt為S中的文檔出現(xiàn)t的數(shù)量，分母為歸一化因子。在TF-IDF公式中，㏒（N/nt+0.01）為IDF因子，即“逆文本頻率指數(shù)”，在WTUPD中依然沿用這個(gè)名稱，IDF因子越大，表明該詞在網(wǎng)頁集合中分布越稀疏，那么該詞的重要性越小，權(quán)值越小。反之，該詞的IDF因子越小，表明其在網(wǎng)頁集中分布越密集，越均勻，那么該詞的重要性越大，權(quán)值越大。
　　考慮到詞在網(wǎng)頁集合中分布的均勻程度不同，本文認(rèn)為詞t在整個(gè)網(wǎng)頁集合S中的權(quán)重與其在網(wǎng)頁中的均勻度成正比。因此，本文引入衡量均勻度的因子對(duì)詞t的權(quán)重進(jìn)行修正，公式1中詞t的均勻度由t在網(wǎng)頁集合中的標(biāo)準(zhǔn)差（Standard Deviation）來衡量，如公式2所示：
　　通過WTUPD公式可以看出：詞t在網(wǎng)頁集S中的權(quán)重，與它在該網(wǎng)頁集中的詞頻成正比，與它在該網(wǎng)頁集中分布的稀疏程度和均勻程度成正比。通過WTUPD公式得到用戶瀏覽的網(wǎng)頁文集合中所有詞的權(quán)重并排序，再根據(jù)個(gè)人瀏覽興趣的廣泛度選擇關(guān)鍵詞擴(kuò)展詞，興趣點(diǎn)較集中的用戶選擇前1/3的詞作為關(guān)鍵詞，余下的詞即為擴(kuò)展詞。而興趣點(diǎn)較分散（核心興趣點(diǎn)5個(gè)以上）的用戶選擇前1/2的詞作為關(guān)鍵詞，余下即為擴(kuò)展詞，以此形成關(guān)鍵詞詞典和擴(kuò)展詞詞典。
　　最后還要清除關(guān)鍵詞詞典和擴(kuò)展次詞典中的頻繁詞，頻繁詞的特征是分布在網(wǎng)頁集合中大多數(shù)文檔中，且在單張網(wǎng)頁中出現(xiàn)的次數(shù)往往較少（一般為1-2次）。本文采用如下的方法對(duì)這部分詞進(jìn)行過濾。
　　經(jīng)過以上公式處理，最終可以建立滿足用戶興趣描述要求的個(gè)性化詞典。
　　2.2 基于個(gè)性化詞典的用戶興趣建模
　　最終的詞擴(kuò)展依賴于準(zhǔn)確的用戶興趣模型，而個(gè)性化詞典的建立將有利于用戶興趣模型快速、準(zhǔn)確地建立，因此本文采取的用戶興趣建模方法如下：
　　首先，利用個(gè)性化詞典將用戶瀏覽的網(wǎng)頁轉(zhuǎn)換為特征向量，由于個(gè)性化詞典包含兩級(jí)詞典，因此，生成的網(wǎng)頁特征向量即為二級(jí)向量，例如某網(wǎng)頁的特征向量表示為{[（單反，0.05327385），（攝影，0.04826857），（像素，0.03272436），（市場，0.02713352），（專業(yè)，0.02639451），……]；[（鏡頭，0.01135712），（顯示屏，0.01023895），（環(huán)境，0.09325765），（瀏覽，0.09031257），（效果，0.08736234）……]}，分號(hào)之前是關(guān)鍵詞向量而之后是擴(kuò)展詞向量。
　　接著，利用網(wǎng)頁特征向量進(jìn)行聚類分析，得到用戶的各個(gè)興趣子類。
　　最后，利用各類的網(wǎng)頁特征向量將興趣子類描述成為二級(jí)向量，生成用戶興趣模型。
　　由此可見，個(gè)性化詞典使得整個(gè)用戶興趣建模過程均使用二級(jí)向量，用戶興趣模型的生成更直接和順利，并且由于個(gè)性化詞典規(guī)避了傳統(tǒng)全局詞典中的大量與用戶興趣無關(guān)的詞和頻繁詞，使得網(wǎng)頁特征描述更加準(zhǔn)確，為后續(xù)的聚類分析和興趣模型生成奠定良好的基礎(chǔ)，并通過用戶興趣模型提供符合用戶興趣偏好的擴(kuò)展詞，有利于擴(kuò)展詞的分析比較和選取。
　　2.3 查詢擴(kuò)展策略的實(shí)現(xiàn)
　　其中，分子為向量ci與Qini各分量乘積的和，分母為向量模的乘積。本文選擇與初始查詢相似度最高的興趣點(diǎn)C作為用戶的查詢意圖。即：
　　為了盡可能的向用戶提供查詢擴(kuò)展詞，如果在關(guān)鍵詞向量中無法找到用戶的查詢?cè)~，即Qini與關(guān)鍵詞向量的相似度為0的話，那就將擴(kuò)展詞向量并入關(guān)鍵詞向量中一起參與運(yùn)算。
　　接下來，為了找到與用戶查詢?cè)~最相關(guān)的擴(kuò)展詞，需要計(jì)算詞間關(guān)聯(lián)度。本文參照LSI模型[7]中的方法，將一個(gè)網(wǎng)頁文檔集合表示成“詞—文檔”矩陣TD，如表1所示。
　　表1為“詞—文檔”矩陣TD的截取內(nèi)容，頂部一行表示文檔集合中所有文檔的名稱（編號(hào)），而左邊一列中的“歐洲、足球”為用戶向搜索引擎提交的初始查詢?cè)~Qini，“國家隊(duì)、世界杯、澳大利亞、…”為Qini所匹配興趣類的擴(kuò)展詞向量中的擴(kuò)展詞。中間的矩陣單元TDij為對(duì)應(yīng)的詞Ti在文檔Dj中的權(quán)值（頻度）按行歸一化后的結(jié)果。由于詞和文檔的數(shù)量都很大，而單個(gè)文檔中出現(xiàn)的詞又非常有限。因此，TD一般為高階稀疏矩陣。
　　然后利用TD構(gòu)造詞間關(guān)系矩陣TT，并計(jì)算詞間關(guān)聯(lián)度，構(gòu)造方法如公式（6）：
　　其中TD’是TD的轉(zhuǎn)置。所得矩陣TT中每一個(gè)單元的TTij的值所反映的是在特定環(huán)境下（特定用戶的特定興趣類）詞i與詞j之間的相似度。我們可以看到，每個(gè)詞與它本身的相似程度為1，而在該興趣類的任何文檔中都沒有同現(xiàn)的兩個(gè)詞之間的相似度為0。如表2所示。
　　公式7中x*表示詞間關(guān)系矩陣TT中與初始查詢?cè)~Qini相似度最大的候選擴(kuò)展詞對(duì)應(yīng)的關(guān)聯(lián)度，x表示其他候選擴(kuò)展詞與Qini的關(guān)聯(lián)度。公式8中的參數(shù)[δ]表示x與x*的相對(duì)誤差閾值，表示只要某候選擴(kuò)展詞與Qini的關(guān)聯(lián)度與x*之間的相對(duì)誤差只要小于δ，那么該候選擴(kuò)展詞就可以最終推薦給用戶，在實(shí)際應(yīng)用中δ通常取值10%，可以保留較好的擴(kuò)展詞，同時(shí)也減少運(yùn)算時(shí)間?？梢愿鶕?jù)情況設(shè)置。這樣將篩選出來的詞進(jìn)行按關(guān)聯(lián)度從大到小的順序排序以后，就可以推薦給用戶了。由于過多的擴(kuò)展詞將導(dǎo)致搜索的返回結(jié)果減少，反而會(huì)不利于用戶獲取足夠的信息。通常選擇3個(gè)擴(kuò)展詞為宜，那么最終可以從已經(jīng)排序的擴(kuò)展詞隊(duì)列里面選擇前3個(gè)進(jìn)行推薦。當(dāng)然，根據(jù)用戶需求，擴(kuò)展詞的推薦數(shù)量可以自行設(shè)定。
　　3 實(shí)驗(yàn)與分析
　　3.1 評(píng)價(jià)指標(biāo)SWUI
　　由于用戶個(gè)性化詞典UPD實(shí)際上幾乎包含了用戶所有感興趣的詞，并且從瀏覽歷史網(wǎng)頁里計(jì)算出的詞的權(quán)值也反映了用戶對(duì)這些詞的感興趣程度，因此，本文利用通過查詢擴(kuò)展搜索到的網(wǎng)頁集合與用戶個(gè)性化詞典進(jìn)行比較的方式來進(jìn)行實(shí)驗(yàn)，評(píng)測本文提出的個(gè)性化服務(wù)模型的效果。
　　為了將檢索到的網(wǎng)頁集合與用戶個(gè)性化詞典進(jìn)行比較，本文計(jì)算檢索到的網(wǎng)頁集合特征向量的中心向量，并稱中心向量為用戶向量UV（User Victor），然后計(jì)算UV與UPD之間的相似度（余弦函數(shù)值），通過該相似度反映網(wǎng)頁集合與用戶興趣之間的相關(guān)程度，稱該相似度為SWUI（Similarity between Webpages and User Interests）。
　　3.2 實(shí)驗(yàn)數(shù)據(jù)
　　本文實(shí)驗(yàn)基于三位用戶進(jìn)行，他們分別按照自己的興趣瀏覽網(wǎng)頁，然后將自己感興趣的網(wǎng)頁保存下來，接著對(duì)三位用戶提供的興趣網(wǎng)頁進(jìn)行興趣建模，得到用戶興趣模型表4所示，限于篇幅，每個(gè)興趣類只用部分關(guān)鍵詞表示。
　　3.3 對(duì)比實(shí)驗(yàn)
　　本文在Google和百度兩大主流搜索引擎上，進(jìn)行了以下三組實(shí)驗(yàn)：
　　1）None實(shí)驗(yàn)：不采用查詢擴(kuò)展，只使用用戶查詢關(guān)鍵詞進(jìn)行檢索的實(shí)驗(yàn)。
　　2）Standard實(shí)驗(yàn)：采用文獻(xiàn)[7]提出的SEPMBDVD模型進(jìn)行查詢擴(kuò)展，然后在搜索引擎上進(jìn)行檢索的實(shí)驗(yàn)。
　　3）UPD based實(shí)驗(yàn)：采用本文提出的QEMBUPDSE模型進(jìn)行查詢擴(kuò)展，然后在搜索引擎上進(jìn)行檢索的實(shí)驗(yàn)。
　　對(duì)比實(shí)驗(yàn)由提供用戶興趣模型的三位用戶實(shí)施，每位用戶對(duì)自己的每個(gè)興趣選用適當(dāng)?shù)年P(guān)鍵詞按以上三組實(shí)驗(yàn)要求在Google和百度上進(jìn)行搜索，每組實(shí)驗(yàn)都將每種搜索引擎返回的前100張網(wǎng)頁保存下來。接著針對(duì)每種搜索引擎，計(jì)算每個(gè)關(guān)鍵詞搜索到的網(wǎng)頁集合與UPD之間的SWUI，最后根據(jù)各SWUI計(jì)算各個(gè)興趣類的ASWUIIC（Average Similarity between Webpages and User Interest in each Interest Class），計(jì)算公式如公式9所示：
　　公式9中，n為某興趣類的測試關(guān)鍵詞數(shù)量，因此ASWUIIC表示某興趣類的所有關(guān)鍵詞搜索的網(wǎng)頁集合與UPD之間的SWUI的平均值。最終實(shí)驗(yàn)結(jié)果如表5所示：
　　為了更直觀的反映對(duì)比的效果，本文計(jì)算了UPD based相對(duì)于None以及Standard的實(shí)驗(yàn)結(jié)果的提高百分比，如表6所示：
　　從表6可以看出，首先，使用QEMBUPDSE模型進(jìn)行查詢擴(kuò)展后，搜索到的網(wǎng)頁比不使用查詢擴(kuò)展明顯與用戶的興趣更相關(guān)。其次，與使用SEPMBDVD模型擴(kuò)展相比，使用QEMBUPDSE模型進(jìn)行查詢擴(kuò)展后，搜索到的網(wǎng)頁在與用戶的相關(guān)性上也有一定的提高，反映了網(wǎng)頁更符合用戶的興趣。這主要是由于在用戶建模之前使用了UPD后，可以使整個(gè)用戶建模過程得到一定程度的優(yōu)化，最終的用戶興趣模型更加準(zhǔn)確，使查詢擴(kuò)展發(fā)揮出更好的效果。
　　4 結(jié)束語
　　本文在文獻(xiàn)[7]提出的基于二級(jí)向量的搜索引擎?zhèn)€性化服務(wù)模型基礎(chǔ)上進(jìn)行改進(jìn)，加入了用戶個(gè)性化詞典，用以優(yōu)化用戶興趣建模過程，進(jìn)而改善查詢擴(kuò)展的效果。實(shí)驗(yàn)表明基于個(gè)性化詞典的搜索引擎查詢擴(kuò)展模型能夠更有效的輔助用戶利用搜索引擎搜索到自己感興趣的信息。在下一步的研究中，需要考慮如何更準(zhǔn)確地建立個(gè)性化詞典和用戶興趣模型，提出更好的相似度計(jì)算方法，用以改進(jìn)整個(gè)個(gè)性化搜索模型的性能。
　　參考文獻(xiàn)：
　　[1] 丁國棟，白碩，王斌.一種基于局部共現(xiàn)的查詢擴(kuò)展方法[J].中文信息學(xué)報(bào)，2006， 20（3）：48-53.
　　[2] 袁薇，高淼.搜索引擎系統(tǒng)中個(gè)性化機(jī)制的研究[J].微電子學(xué)與計(jì)算機(jī)，2006（2）：68-75.
　　[3] 黃名選，嚴(yán)小衛(wèi)，張師超.基于關(guān)聯(lián)規(guī)則挖掘的查詢擴(kuò)展模型研究[J].現(xiàn)代圖書情報(bào)技術(shù)， 2007（10）：47-51.
　　[4] 黃名選，嚴(yán)小衛(wèi)，張師超.基于矩陣加權(quán)關(guān)聯(lián)規(guī)則挖掘的偽相關(guān)反饋查詢擴(kuò)展[J].軟件學(xué)報(bào)， 2009，20（7）：1854-1865.
　　[5] 黃名選，嚴(yán)小衛(wèi)，張師超.完全加權(quán)關(guān)聯(lián)規(guī)則挖掘及其在查詢擴(kuò)展中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用研究， 2008，25（6）：1724-1730.
　　[6] 支鳳麟，徐煒民.基于主題的個(gè)性化查詢擴(kuò)展模型[J].計(jì)算機(jī)工程與設(shè)計(jì)，2010，31（20）：4471-4475.
　　[7] 徐靜秋，朱征宇，譚明紅，等.基于二級(jí)向量的搜索引擎?zhèn)€性化服務(wù)模型[J].計(jì)算機(jī)科學(xué)，2007， 34（11）：89-92.
　　[8] Zhengyu ZHU， Yunyan TIAN，Kunfeng YUAN，Yong YANG.An Improved Web Document Clustering Method. Journal of Computational Information Systems，2007，3（3）：1087-1094.
　　[9] Khan M S，Khor S.Enhanced web document retrieval using automatic query expansion[J].Journal of the American Society for Information Science and Technology，2004，55（1）：29-40.
　　[10] 羅穎，朱征宇，李力沛，等.Web檢索模型上個(gè)性化詞典的研究與實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用研究，2009（10