【畢業(yè)學位論文】（Word原稿）基于用戶反饋的個性化檢索技術研究-網(wǎng)絡與分布式系統(tǒng)博士論文

博士研究生學位論文 題目： 基基于用戶反饋的個性化 檢索技術研究 姓 名： 學 號： 院 系： 信息科學技術學院 專 業(yè)： 計算機系統(tǒng)結構 研究方向： 網(wǎng)絡與分布式系統(tǒng) 導師姓名： 李曉明教授 二零 年 五 月 in of ( i 2007 版權聲明 任何收存和保管本論文各種版本的單位和個人，未經(jīng)本論文作者同意，不得將本論文轉借他人，亦不得隨意復制、抄錄、拍照或以任何方式傳播。否則，引起有礙作者著作權之問題，將可能承擔法律責任。 i 摘 要 隨著互聯(lián)網(wǎng)的飛速發(fā)展，搜索引擎日漸成為人們必不可少的一項工具。然而一方面由于搜索引擎的用戶大多是普通用戶，很難將自己復雜的檢索目的組織成搜索引擎所需要的簡單的查詢詞表示；因此為用戶提供更多的交互式接口，提供啟發(fā)式檢索手段就顯得特別重要。另一方面在通用搜索引擎中，當不同的用戶輸入同一個檢索詞時，搜索引擎將 不做區(qū)分的返回同樣的檢索結果。然而實踐證明，用戶的檢索目的是多種多樣的。即使是同樣的檢索詞，不同用戶所期待的檢索結果也是各不相同的。此時需要一些更加貼近用戶的手段來改變這種檢索方式，使得用戶能夠得到真正自己關心的信息。這也就是“個性化檢索”所試圖解決的問題。 個性化檢索系統(tǒng)是指那些針對不同用戶背景返回不同檢索結果的信息檢索系統(tǒng)。在這些系統(tǒng)中，文檔的相關性是基于不同用戶的背景和興趣而單獨計算的。而用戶的興趣和背景通常是通過顯式或隱式的用戶反饋來獲得。通過對基于用戶反饋的個性化檢索技術的深入研究和探討，本文得到 了如下研究成果和結論： (1) 一種無須人工干預的、用于衡量搜索引擎排序結果質量的方法和指標 of a 該指標能夠用于衡量一個文檔排序結果的質量；在實際的檢索過程中，該指標不需人工干預即可計算得到，而以往的指標都需要有人工標注的結果集才可計算。實驗結果表明了 標與 成正比，也就是說 標確實反映了一個排序結果的真實質量。 (2) 一種基于 標的個性化重排序算法。在有了 標的基礎上，就可以通過當前排序結果的質量來衡量用戶不同反饋文檔的相關度高低，這正是 權 排序算法的思想。通過這種方法，相關度較高的反饋文檔將對重排序過程起著更重要的作用，從而有效的改進了個性化排序的結果質量。 (3) 一種 利用分類輔助的 摘要比較算法 摘要比較算法是個性化重排序算法過程中必 不可少的一個子模塊。 法的主要思想是 根據(jù) 搜索引擎返回 摘要的特點，利用分類技術來擴展短摘要的信息，以改進摘要比較算法。 該方法有效的克服了摘要文本短，內容少，無法直接比較的特點；從而改進了摘要比較的結果，進而提高了排序算法的質量。最終的 實驗結果驗證了該方法的有效性。 (4) 一種無損的基于聚類的層次 類算法。 法是一種經(jīng)典的分類算法，然而其在處理大規(guī)模訓練文檔時效率上存在缺陷。本文利用層次聚類算法對訓練文檔進行有效的組織，實現(xiàn)了在提高分類效率的同時，分類質量不下降。 (5) 在深入研究并探討了訓練數(shù)據(jù)集對分類結果的影響之后，本文提出了一種穩(wěn)定的分類評測指標 評測指標具有如下優(yōu)點：（ a） 在不同的訓練數(shù)據(jù)集上， 1 表現(xiàn)較穩(wěn)定；（ b） 使用新的評測指標，不同的研究工作在不同訓練數(shù)據(jù)集上的性能可以直接 進行比較；（ c） 在給定一個分類器在某個訓練數(shù)據(jù)集上的 1 值時，可以推導得到該分類器在另一個訓練數(shù)據(jù)集上的分類結果（即真實的分類精度、召回率以及 ）。 (6) 一 個 個 性 化 檢 索 系 統(tǒng) 原 型 。它是一種基于顯式用戶反饋的個性化檢索系統(tǒng)，該系統(tǒng)通過一個客戶端來完成用戶信息的搜集以及檢索結果的重排序工作。用這種方式可以對不同的用戶產(chǎn)生不同的排序效果，滿足用戶不同的檢索目的，從而達到個性化檢索的目的。 關鍵詞 ：搜索引擎，信息檢索，個性化， 相關反饋，分類 do a in to s a do do a in It is an to by of as In is to by 1) A of a is to of a R be of a R is in to CG R be to of a 2) of is to of is In an in of is of is 3) An to A is a in as is to of by CG of 4) An is in a to a of do in to to of 0 as NN ) A of is to of of on on of an on as on be of 6) A is to v of in is a to 目 錄 第 1 章 引言 . 1 究工作的背景和意義 . 1 戶反饋技術的 線裝概述 . 2 何獲得用戶反饋信息 . 4 何使用用戶反饋信息 . 9 何評價反饋技術 . 14 文的主要工作 . 18 文的主要研究內容 . 18 文的創(chuàng)新之處 . 20 文的組織結構 . 21 第 2 章 對重排序算法的研究 . 22 紹 . 22 關工作 . 24 一個排序結果質量的評估 . 25 量一個排序質量的現(xiàn)有指標 . 25 個特征以及 標 . 26 于新指標 實驗 . 30 用 標改進的重排序算法及實驗結果 . 34 章小結 . 36 第 3 章 利用分類改進的摘要比較算法 . 37 言 . 37 用分類技術改進的摘要比較算法 . 37 言 . 37 關工作 . 39 要比較算法 . 40 驗設置和實驗結果 . 44 結 . 47 分類算法效率的改進 . 47 言 . 47 關工作 . 49 于聚類的無損層次 類算法 . 49 驗結果和算法分析 . 53 結 . 55 章小結 . 55 第 4 章 對中文分類評測方法的研究 . 57 言 . 57 關研究 . 59 個因素 . 60 素 1 訓練集中的文檔比例 . 60 素 2：類半徑 . 62 素 3：類間距 . 64 評測指標以及實驗 . 66 評測指標 . 66 驗 1:同一個分類器在不同數(shù)據(jù)集上的表現(xiàn) . 67 驗 2:12 個不同分類器在 2 個不同數(shù)據(jù)集上的表現(xiàn) . 68 評測指標的優(yōu)點 . 69 章小結 . 70 第 5 章 一個應用實例及應用前景 . 72 性化檢索技術應用現(xiàn)狀 . 72 個應用實例 . 74 他應用場景及實例 . 76 戶端 服務器 . 76 反饋 顯式用戶反饋 . 77 用搜索引擎 個性化搜索引擎 . 78 關工作及系統(tǒng) . 78 章小結 . 79 第 6 章 總結和展望 . 81 文的總結 . 81 一步的研究工作 . 83 參考文獻 . 85 博士期間錄用和提交的論文 . 93 博士期間的主要科研項目與所獲獎勵 . 94 致謝 . 96 圖示 圖 1擬評測 . 18 圖 2果序列的特征 . 29 圖 2詢樣例 . 31 圖 2計相關文檔個數(shù) . 32 圖 2征 2：半徑 . 33 圖 2征 3：可能的相關文檔比例 . 33 圖 2R 指標與 的關系 . 34 圖 2排序算法 流程 . 34 圖 2. 36 圖 3要實例 A . 39 圖 3要實例 B . 39 圖 3要實例 C . 39 圖 3網(wǎng)搜索引擎返回摘要 . 41 圖 3文網(wǎng)頁分類器的工作流程 . 43 圖 3要比較算法 . 46 圖 3 關系圖 . 47 圖 3個反例 . 50 圖 3定規(guī)則說明 . 51 圖 3例：二維空間 . 54 圖 42 個不同分類器在 2 個不同數(shù)據(jù)集上的宏平均精度 . 59 圖 4檔比例對分類結果的影響 . 62 圖 4素 2：類半徑的含義 . 63 圖 4半徑對分類結果的影響 . 64 圖 4素 3：類間距的含義 . 65 圖 4間距對分類結果的影響 . 65 圖 . 68 圖 5性化檢索系統(tǒng) . 73 圖 5于用戶反饋的個性化檢索原型 . 75 x 圖 5使用過程 . 76 圖 5統(tǒng)說明 . 78 表格 表 1種用戶行為的分類 . 6 表 3本集中類別及實例數(shù)量的分布情況 . 42 表 3文網(wǎng)頁分類器 . 43 表 3詢集合說明 . 45 表 3次 法效 率 . 54 表 3法效率 . 54 表 4息檢索系統(tǒng)的評價標準 . 57 表 . 67 表 4據(jù)集 . 68 表 4據(jù)集 . 69 表 42 個不同的分類器在 2 個數(shù)據(jù)集 上性能評價 . 69 表 5性化檢索系統(tǒng)的劃分 . 73 第 1 章 引言 1 第 1章 引言 究工作的背景和意義 隨著 模的迅速增長和內容的不斷豐富，用戶越發(fā)的需要搜索引擎這一信息服務形式以幫助 用戶 快速、準確的在信息的海洋中找到自己需要的內容。 一個典型的使用場景是：用戶將自己的檢索目的組織成若干個查詢詞作為輸入送給搜索引擎；搜索引擎根據(jù)查詢詞 進行檢索，將檢索結果返回給用戶；用戶瀏覽這些結果并點擊查看自己想要的結果頁面。然而一個突出的問題是：一個查詢結果集中往往包含了成千上萬參差不齊、內容各異的結果。這些結果有些是符合用戶檢索目的的，但是大部分都是不相關文檔，也就是說查詢結果集的精度低。從 年的評測結果中也說明了通用搜索引擎的這一問題，而“查詢詞的內容含糊”是導致這種情況的主要原因之一。 由于檢索目的不明確或是對檢索環(huán)境的不熟悉 et 1998等因素，許多事實表明用戶無法將自己的檢索意圖組織成高質量的查詢詞。 經(jīng)驗豐富的用戶，能夠構造出“好”的查詢詞；所謂“好”的查詢詞是指查詢中包含大量區(qū)分度高的詞（即在少量文檔中大量出現(xiàn)的詞）。但是大多數(shù)用戶并不能清楚的描述他的需求，最終得到的檢索結果也往往難以令人滿意。 因此搜索引擎需要一些額外的技術來輔助挖掘用戶的查詢意圖，改進檢索結果。 另一方面，在通用搜索引擎中，當不同的用戶輸入同一個檢索詞時，搜索引擎將不做區(qū)分的返回同樣的檢索結果。然而實踐證明，用戶的檢索目的是多種多樣的。即使是同樣的檢索詞，不同用戶所期 待的檢索結果也是各不相同的。此時需要一些更加貼近用戶的手段來改變這種檢索方式，使得用戶能夠得到真正自己關心的信息。這也就是“個性化檢索”所試圖解決的問題。 相關反饋技術（ 在個性化檢索方面最重要的方法之一（ 傳統(tǒng)的相關反饋技術主要是用于查詢擴展，然而近些年相關反饋技術已經(jīng)廣泛的應用在了各種個性化檢索系統(tǒng)中。這一點將會在后面的章節(jié)中說明） 。經(jīng)典的信息檢索模型通常由 4個要素組成 ),(,ji 中： （ 1） D 是對一個大文檔集合的邏輯表示； （ 2） Q 是對用戶信息需求的邏輯表示； （ 3） 第 1 章 引言 2 （ 4） R(qi,一個排序算法。對任意一個用戶信息需求 （即用戶檢索詞），該算法計算得到每個文檔 的相關度權值 983。 而相關反饋技術最主要的作用是提供一個新的排序算法 ),(，在增加了一個已知條件 用戶的反饋信息集合）的情況下，重新計算對于查詢 ,文檔 相關度權值；從而改變原來的排序結果，進而改進檢索質量。需要注意的是，對于d ， （即 在一個相關反饋系統(tǒng)中，實際的操作流程如下： 用戶對檢索出的文檔顯式或隱式的進行相關性判定，系統(tǒng)根據(jù)這些判定生成新的查詢，對檢索結果進行重排序。這一過程可以不斷的迭代進行，直到用戶找到滿意的相關文檔集合。許多實驗結果都證明了這一方法能夠有效的改進查詢結果的質量，這種改進主要得益于查詢擴展以及對查詢詞權重的重新計算。 根據(jù)所記錄的用戶反饋歷史長短，相關反饋技術可以分為長期及短期兩種：長期（ 關反饋即長期記錄用戶 的行為，建立并維護用戶模型（ 根據(jù)用戶模型對用戶的行為進行預測；短期（ 關反饋只處理一個會話（ 的用戶行為（通常指一次信息檢索查詢中對查詢結果集的優(yōu)化），因此也就不涉及用戶長期歷史以及用戶模型的變遷維護。本文中主要討論的是短期用戶反饋所使用的各種相關技術。 相關反饋相對于其他查詢處理方法而言，具有如下優(yōu)點： （ 1）用戶只需對文檔做出相關性判斷，而不需要了解查詢處理的技術細節(jié)； （ 2）用戶反饋技術將整個檢索過程分割成 3 個用戶容易理解的部分：提交查詢，進 行相關性判斷，對查詢結果的重排序； （ 3）它提供了一種可控制的方法來突出某些查詢詞或是削弱某些查詢詞。 由此可見，相關反饋技術是理解用戶檢索意圖、實現(xiàn)個性化排序、改進搜索引擎排序結果，提高用戶對搜索引擎結果滿意度的重要工具。因此本文將對基于用戶反饋的個性化檢索技術 這一具有重要理論意義和廣闊應用前景的課題進行研究和探索。 戶反饋技術的現(xiàn)狀概述 第 1 章 引言 3 傳統(tǒng)的用戶相關反饋技術主要包括 2 個方面的研究內容：查詢擴展（ 及權值調整（ 隨著技術的進步，相關 反饋的研究內容逐漸發(fā)生了變化。目前的相關反饋技術主要可以劃分為以下 3 個方面的研究工作：如何獲得用戶反饋信息（即上文所提到的 ；如何使用用戶反饋信息來改進檢索系統(tǒng)的質量（即如何構造新的排序算法),( ） ；如何評價用戶反饋技術。 如何獲得用戶反饋信息？在傳統(tǒng)相關反饋技術中，主要是通過用戶顯式的對文檔進行相關性標記來獲得。要求用戶顯式的相關反饋會導致用戶不堪負荷，這也是傳統(tǒng)的相關反饋技術不能廣泛應用的最大限制。目前，有許多新的反饋 獲得方法，隱反饋（ 偽反饋（ 其中最突出的兩種技術。隱反饋技術是指從用戶的行為（例如點擊、瀏覽、打印 .1997; Le et 2001; 004中，通過種種數(shù)據(jù)挖掘技術來發(fā)現(xiàn)用戶隱含的興趣及愛好，并將這些隱含的信息作為反饋信息來輔助檢索。偽反饋技術 et 2005是指將檢索結果中的若干個文檔假設為“相關文檔”作為反饋信息來輔助檢索。 如何使用用戶反饋信息來改進檢索系統(tǒng)的質量？根據(jù)所使用的信息檢索模型的不同，可以將對這一問題的研究分成三個方向。這三個信息檢索模型為：向量空間模型、概率模型和語言模型。不論使 用哪一種信息檢索模型，其中心思想都是盡可能的將查詢貼近用戶的檢索興趣即用戶的反饋信息。 如何評價用戶反饋技術？這里涉及到評價所使用的數(shù)據(jù)集、評價指標、評測方式以及評測環(huán)境的構建。不同的評測環(huán)境會帶來不同的評測結果。 本小節(jié)的主要貢獻是對相關反饋領域當前的研究進展，做了全面的介紹；同時將用戶反饋問題劃分成 3 個基本的技術問題（如何獲得反饋信息、如何使用反饋信息以及如何評價反饋技術）；并對目前這 3 個基本問題的常用解決方法以及研究進展進行了介紹。以前也曾經(jīng)有過一些綜述性的工作，例如 003; 003; 004。但是其中 004只是對相關反饋技術做了很簡略的說明； 003的工作完成的比較早，遺漏了一些重要的部分（比如隱反饋以及語言模型），而這兩個部分都是目前研究工作較集中的方面。文獻 003只是對隱反饋中的主要文章做了說明，主要內容是側重于介紹如何取得反饋，關于第 1 章 引言 4 性能評價以及如何使用反饋信息以改進檢索系統(tǒng)的質量并沒有做出很好的說明。 本文的以下部分是這樣組織的：第 說明了如何獲得用戶反饋信息，介紹了當前主要的 3 種用戶反饋信息取得手段以及對應的典型系統(tǒng)及優(yōu)缺點。第 說明了如何使用用戶反饋信息來改進檢索系統(tǒng)的排序質量，同時介紹了在 3 種模型下各 種不同的反饋算法。第 說明了如何評價用戶反饋技術。 何獲得用戶反饋信息 獲得用戶反饋信息主要有 3 種手段：顯式用戶反饋（ 隱式用戶反饋（ 及偽反饋（ 顯式用戶反饋是一種經(jīng)典的方法；許多研究人員還在考慮如何從用戶的交互行為中隱式的發(fā)現(xiàn)信息作為用戶反饋，也就是隱反饋；偽反饋的思想是從返回結果中選擇一些文檔作為用戶反饋。 顯式用戶反饋 早期的用戶反饋技術主要是用于文本信息檢索領域，當時主要是采用顯式用戶反饋來獲取用戶的反饋信息。 統(tǒng) 990就是顯式用戶反饋方面的一個經(jīng)典系統(tǒng)。該系統(tǒng)要求用戶對檢索結果顯式的做出標記行為，給出反饋信息。例如指定關鍵詞、對文檔進行選擇或是標注、給出自己的興趣范圍等等，這些方式都稱為顯式用戶反饋。這種方式有一個前提是：用戶在檢索期間是有一個明確的檢索目的，而這一目的不會變更。當把所有檢索結果文檔呈現(xiàn)在用戶面前時，用戶能夠從中挑選出符合自己檢索意圖的相關文檔或是不相關文檔做出標記。這一過程是可以迭代進行的：用戶給出一次顯式反饋，檢索系統(tǒng)根據(jù)用戶標記的反饋文檔，使用反饋算法來改進檢索結果的質量；在新的 結果集上，用戶還可以繼續(xù)給出反饋。這一過程可以不斷進行直到用戶滿意為止。 如何顯式的獲得用戶反饋信息，通常的做法是把檢索結果按照其與查詢詞之間的相關度大小排序之后返回給用戶，以供用戶瀏覽；并在界面上提供接口，允許用戶在瀏覽時，對其中的某些文檔進行標注，例如標注為“相關文檔”或是“不相關文檔”。如何提供更方便實用的接口來顯式的與用戶進行互動，這一問題更多的是依賴于人機交互領域的技術，在本文中將第 1 章 引言 5 不詳細進行討論。 在顯式獲得用戶反饋技術方面，有 2 個值得說明的問題：一是主動學習（ 在顯式用戶反饋中的研究；二是關于負反饋信息的處理。 主動反饋“ et 2000; 001; 003; 005是指在用戶對檢索結果進行反饋之前，先對結果集進行一些預處理，并選擇其中的部分文檔集展示給用戶。主動反饋的目的是保證所得到的反饋文檔能帶來最大的信息增益，加快反饋迭代過程，從而盡可能快的達到用戶的檢索目標。 主動反饋的算法有很多，列舉