【畢業(yè)學(xué)位論文】（Word原稿）一個(gè)借助查詢歷史改善結(jié)果排序的文件檢索系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)-計(jì)算機(jī)網(wǎng)絡(luò)與分布式系統(tǒng)

北京大學(xué)碩士研究生學(xué)位論文 題目：一個(gè)借助查詢歷史改善 結(jié)果 排序的文件檢索 系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn) 姓 名：謝 欣 學(xué) 號(hào)： 10208105 院 系：信息科學(xué)技術(shù)學(xué)院 專 業(yè)：計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 研究方向：計(jì)算機(jī)網(wǎng)絡(luò)與分布式系統(tǒng) 導(dǎo) 師：李曉明 教授 2005 年 5 月 北京大學(xué) 網(wǎng)絡(luò)實(shí)驗(yàn)室碩士學(xué)位論文 1 版權(quán)聲明 任何收存和保管本論文各種版本的單位和個(gè)人，未經(jīng)本論文作者同意，不得將本論文轉(zhuǎn)借他人，亦不得隨意復(fù)制、抄錄、拍照或以任何方式傳播。否則，引起有礙作者著作權(quán)之問題，將可能承擔(dān)法律 責(zé)任。 北京大學(xué) 網(wǎng)絡(luò)實(shí)驗(yàn)室碩士學(xué)位論文 2 摘 要 隨著網(wǎng)絡(luò)的發(fā)展，網(wǎng)絡(luò)上提供文件共享服務(wù)的服務(wù)器越來越多，共享的文件數(shù)量也隨之增加。如何更好的檢索、利用這些共享文件成為一個(gè)重要的問題。 針對(duì)用戶對(duì)文件檢索的需求，本文在文件檢索技術(shù)領(lǐng)域有如下貢獻(xiàn)。 1. 本文首先提出了一個(gè)文件檢索的模型，明確了在文件檢索模型中檢索對(duì)象、查詢串、查詢與檢索對(duì)象的匹配方式三部分的含義。檢索對(duì)象，即文件條目表示為六元組 形式，查詢串表示為以空格分隔的字符串的集合，查詢與檢索對(duì)象的匹配則表示為 查詢串與文件條目的匹配串之間的匹配。 2. 提出了對(duì)文件檢索系統(tǒng)進(jìn)行評(píng)測(cè)的指標(biāo)。將查詢結(jié)果視作集合時(shí)以查全率、查準(zhǔn)率為評(píng)測(cè)指標(biāo)。將查詢結(jié)果視作有序序列時(shí)，分析了查詢結(jié)果的相關(guān)性、連接下載速度以及結(jié)果的可用性等因素對(duì)排序的影響，并提出了對(duì)排序進(jìn)行評(píng)測(cè)的指標(biāo) 排序指數(shù)。作者還提出對(duì)于兩個(gè)排序策略進(jìn)行比較時(shí)，應(yīng)當(dāng)在結(jié)果的每個(gè)頁面內(nèi)部應(yīng)用排序策略，而不是在全體結(jié)果集合上應(yīng)用排序策略，并比較平均用戶選取條目的頁內(nèi)排名。 3. 通過統(tǒng)計(jì)、分析用戶對(duì)文件搜索引擎的檢索和對(duì)檢索結(jié)果中下載地址條目的選取，作者發(fā)現(xiàn)了用戶行為 習(xí)慣中的兩個(gè)重要規(guī)律：一、少數(shù)查詢串占據(jù)了全部查詢請(qǐng)求的大多數(shù)，具體而言，前 20%的熱門查詢串占據(jù)了全部查詢請(qǐng)求的 80%；二、對(duì)全體用戶而言，假設(shè)有 n 次不同的查詢請(qǐng)求使用了同一個(gè)查詢串，并且它們代表 k 類不同的查詢意圖。那么通常 k 3，因而在 n 較大的情況下，則 n/k 的值較大，即大量的來自不同用戶的請(qǐng)求代表了相同的查詢意圖。 4. 基于上文所述，作者設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)真實(shí)的系統(tǒng)。該系統(tǒng)借助查詢歷史改善結(jié)果的排序。與一般基于用戶歷史信息的檢索系統(tǒng)不同的是，本系統(tǒng)借助的歷史信息不局限于當(dāng)前用戶的歷史信息，還包含提交了 相同查詢串的其他用戶的查詢信息。或者說，即使當(dāng)前用戶是第一次使用本系統(tǒng)，本系統(tǒng)也能利用其他用戶的歷史記錄來改進(jìn)結(jié)果的排序和篩選。作者最后還驗(yàn)證了其實(shí)際的效果。應(yīng)用本方法后，平均用戶選取條目的頁內(nèi)排名從原來的 前進(jìn)到了 。試驗(yàn)結(jié)果表明文中所做的分析是正確的。 關(guān)鍵詞： 文件檢索系統(tǒng)，查詢歷史，檢索模型 北京大學(xué) 網(wǎng)絡(luò)實(shí)驗(yàn)室碩士學(xué)位論文 3 of a I of of is So its to of of we 1. We a is of of an of a be is as by is by of 2. We we is a an So we in of of We to of If we to we in y of 3. By of s a we 1). 80% 0% 2) If n of of is k. k be a 應(yīng)的查詢串的個(gè)數(shù) 33 157 81 0 1 0 從上表可見，查詢意圖只有 1 3 個(gè)的查詢串占全部記錄數(shù)據(jù)的絕大部分，超過 5 種不同意圖的查詢串在統(tǒng)計(jì)的日志中根本就沒有出現(xiàn)。 我們?cè)賮砜匆幌?n 和 k 的比例的分布，統(tǒng)計(jì)結(jié)果如下圖。圖中橫坐標(biāo)表示查詢串被查詢的次數(shù) n，綜坐標(biāo)為 n/k 的比值。要說明一點(diǎn)就是為了使圖像中的點(diǎn)線顯示清晰，我們忽略了很少量的查詢次數(shù)非常高的詞（這些點(diǎn)對(duì)應(yīng)的橫坐標(biāo)值非常大），但事后的手工驗(yàn)證仍然證明了它們符合本文的規(guī)律。 北京大學(xué) 網(wǎng)絡(luò)實(shí)驗(yàn)室碩士學(xué)位論文 25 11010010000 100 200 300 400 500 600 700 800 900 1000圖 4其中橫坐標(biāo)為查詢串查詢 次數(shù) n， 綜坐標(biāo)為 n/k 比值（為指數(shù)標(biāo)度） 從圖中可以看到，當(dāng) n100 時(shí)， n/k 的值都在 30 以上。 由上面的分析我們能夠知道，盡管查詢串不同，但一般說來，它們所代表的查詢意圖的數(shù)量并不是太多的，通常在 1，并且在 n 較大的情況下（如 n100），通常 n/k 的比值較大（本例中大于 30）。因此我們得到了第二個(gè)重要的規(guī)律： 規(guī)律二：假設(shè)有 n 次不同的請(qǐng)求查詢了同一個(gè)查詢串，并且它們代表 k 種不同的查詢意圖。在 n 較大的情況下（ n100）， n/k 的值較大（ n/k30）。 戶行為特點(diǎn)的啟發(fā) 利用上面的用戶行為特點(diǎn) 中的兩個(gè)規(guī)律，以及前面關(guān)于相關(guān)反饋方法的思路，可以考慮采用如下思路來實(shí)現(xiàn)一個(gè)借助查詢歷史信息改善結(jié)果排序的文件檢索系統(tǒng)。 從上面的特征我們知道，大多數(shù)的查詢請(qǐng)求不僅其查詢串本身是重復(fù)的，而且其所代表的查詢意圖也是重復(fù)的。這樣我們就可以由“較早的相同的查詢串的結(jié)果選取記錄”作為用戶的反饋信號(hào)。這樣一來，后來提交同樣查詢串的用戶不需要任何主動(dòng)干預(yù)，就可以得到經(jīng)過反饋信號(hào)處理過的重新排序的查詢結(jié)果了。北京大學(xué) 網(wǎng)絡(luò)實(shí)驗(yàn)室碩士學(xué)位論文 26 當(dāng)然，由于用戶意圖并不唯一，我們并不能確定究竟本次查詢的用戶是哪種查詢意圖，但因?yàn)?k 值通常都相當(dāng)?。ㄐ∮诘扔?3）， 因此對(duì)用戶而言，很容易從這為數(shù)極少的查詢意圖中找到滿足自己意圖的結(jié)果。 具體而言，我們可以考慮如下的思路。 首先記錄下每次用戶對(duì)查詢結(jié)果的選取。我們認(rèn)為，用戶在查詢結(jié)果中點(diǎn)擊的下載地址，就是用戶認(rèn)為比較理想的下載地址。通過一段時(shí)間的記錄，我們就得到了對(duì)于大量查詢串的較理想的匹配結(jié)果。對(duì)于一個(gè)查詢串 q，我們有一個(gè)用戶認(rèn)為較好的文件條目的集合 S，我們將其表示為一個(gè)二元組 (q,S)。這樣，我們就得到了大量的這樣的二元組。 依據(jù)規(guī)律 2，我們知道每個(gè)查詢串可能代表幾個(gè)不同的查詢意圖，那么不同的查詢意圖對(duì)應(yīng)的理想下載地 址肯定不同（否則就是相同的查詢意圖了），我們可以采用聚類的方法對(duì)每個(gè) S 中的文件條目進(jìn)行聚類。聚類后，對(duì)于每個(gè) q，我們會(huì)得到 k 種不同的類別，這 k 個(gè)類別就也就反映了不同的查詢意圖，而每個(gè)類別中的文件條目，就可以看作這個(gè)類別的訓(xùn)練集。每個(gè)類別中的條目個(gè)數(shù)，也直接反映了這個(gè)類別的權(quán)重。 當(dāng)再次有用戶查詢同樣的查詢串 q 時(shí)，我們首先采用原始的檢索方法，得到一個(gè)結(jié)果集合，然后用聚類得到的 k 個(gè)類別和訓(xùn)練集對(duì)其進(jìn)行分類處理。一些條目被分到這 k 個(gè)類別中，另外一些可能不屬于任何類別。不屬于任何類別的條目往往也是用戶不太需要的條目 ，可以考慮拋棄或排在結(jié)果的最后輸出。北京大學(xué) 網(wǎng)絡(luò)實(shí)驗(yàn)室碩士學(xué)位論文 27 第 5章 系統(tǒng)體系結(jié)構(gòu)與主要算法 統(tǒng)體系結(jié)構(gòu) 基于以上分析，我們?cè)O(shè)計(jì)了如下的檢索系統(tǒng)來改善文件檢索系統(tǒng)的排序。 Q u e r y S t r i n g ( q )N o r m a l I n d e x S y s t e m ( I )I n d e x R e s u l t ( S 0 )F e e d b a c k d a t a D a t a B a s eS i t e L i s t D a t a B a s eq u e r yC l u s t e r i n gT h e t r a i n i n g s e t f o r q u e r y i t e m qI t e m s n o t b e l o n g t o a n y g r o u pR e s u l t a f t e r C a t e g o r i z a t S )C a t e g o r i z a t i o n , O r d e r i n gF i l e i t e m s t h a t u s e r c l i c k e 5統(tǒng)結(jié)構(gòu)圖 下面我們來詳細(xì)介紹這個(gè)模型。 我們首先查看模型中的各個(gè)組成部分。 q)： 用戶輸入的查詢串； )： 常規(guī)的文件檢索系統(tǒng)； 0)： 初始查詢結(jié)果集； B(F)： 該數(shù)據(jù)庫中記錄了已有的每個(gè)查詢請(qǐng)求和它對(duì)應(yīng)的不同的 k 種查詢意圖，以及每種意圖的作為訓(xùn)練集的文件條目。 B(D)： 該數(shù)據(jù)庫中保存了每次用戶進(jìn)行檢索后對(duì)查詢結(jié)果的選取情況。具體而言，當(dāng)用戶進(jìn)行查詢后，檢索系統(tǒng)返回結(jié)果，當(dāng)用戶在結(jié)果頁面中對(duì)文件條目進(jìn)行點(diǎn)擊并下載時(shí)，本模型會(huì)記錄用戶的點(diǎn)擊選取行為。庫中的每條記錄含有當(dāng)前的查詢串和用戶點(diǎn)擊的這條記錄的具體文件信息：文件名稱、擴(kuò)展名稱、最后修改日期、文件大小、文件所在 站點(diǎn)和文件所在的路徑。 北京大學(xué) 網(wǎng)絡(luò)實(shí)驗(yàn)室碩士學(xué)位論文 28 本檢索系統(tǒng)的工作流程如下： 數(shù)據(jù)庫 F 中需要足夠的數(shù)據(jù)記錄系統(tǒng)才能夠進(jìn)行工作。因此在系統(tǒng)運(yùn)行之初，系統(tǒng)便開始自動(dòng)記錄用戶的點(diǎn)擊，并將記錄填充進(jìn)數(shù)據(jù)庫 D。數(shù)據(jù)庫 D 每隔一段時(shí)間，對(duì)每個(gè)查詢串 q 進(jìn)行一次聚類操作，這樣便得到了每個(gè)查詢串所代表的 現(xiàn)在我們假設(shè) F 中已經(jīng)包含有了足夠的記錄信息。當(dāng)用戶輸入查詢串 q 后，一方面，模型中最上面的流程開始工作，常規(guī)的檢索系統(tǒng)進(jìn)行檢索，得到一個(gè)原始的查詢結(jié)果 一方面，如模型圖示中的中層的流程， q 被送入數(shù)據(jù)庫 F。數(shù)據(jù)庫 F 返回對(duì)應(yīng)的 k 種意圖和其 點(diǎn)擊記錄集合。這些記錄將作為下一步分類工作的訓(xùn)練集。 有了 這 k 種類別，下面將利用這 k 種類別的訓(xùn)練集對(duì) 行分類。分類后我們將 成了 k+1 類，其中新增加的這個(gè)類別是那些不屬于任何類別的文件條目 合。對(duì)于不屬于任何類別的條目，我們認(rèn)為它是用戶不太關(guān)心的結(jié)果，可以把它拋棄或放入輸出結(jié)果的最后。 這里有一點(diǎn)要注意，就是 k 種類別的地位是不同的，類別本身也是有權(quán)重的，權(quán)重可以由聚類時(shí)每個(gè)類別中的條目數(shù)量來決定。這樣在最后輸出時(shí)可以按照權(quán)重本身對(duì)類別進(jìn)行排序。由于 k 的取值通常都比較?。ㄐ∮诘扔?3），用 戶最終看到的結(jié)果往往是接近用戶的真實(shí)查詢意圖的。 然后就可以按照一般的條目列表方式或者聚類的樹型結(jié)構(gòu)將結(jié)果輸出給最終用戶。 要算法 戶點(diǎn)擊日志的表示 用戶點(diǎn)擊日志就是用戶所點(diǎn)擊的文件條目 前面的對(duì)文件檢索的建模，我們知道可以表示為： 我們將其改寫為如下格式： p a t hs i t ed a t es i z a m e 有時(shí)候?yàn)榱撕?jiǎn)便，我們也會(huì)表述為如下形式： 北京大學(xué) 網(wǎng)絡(luò)實(shí)驗(yàn)室碩士學(xué)位論文 29 654321 對(duì)于查詢串 q， 價(jià)格共有 n 個(gè)記錄，因此我們得到如下的矩陣： 1 , 1 1 , 2 1 , 3 1 , 4 1 , 5 1 , 6, 1 , 2 , 3 , 4 , 5 , 6, 1 , 2 , 3 , 4 , 5 , 6. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .i i i i i in n n n n nx x x x x xx x x x x xx x x x x x算文件條目之間的距離 不論是進(jìn)行聚類處理還是進(jìn)行分類處理，都需要進(jìn)行大量的對(duì)兩個(gè)文件條目(間的距離 d 的計(jì)算?；蛘哒f，需要通過上文中的二模矩陣，得到下面的表示條目之間距離的單模矩陣： 0( 2 , 1 ) 0( 3 , 1 ) ( 3 , 2 ) 0( 4 , 1 ) ( 4 , 2 ) ( 4 , 3 ) 0( 5 , 1 ) ( 5 , 2 ) ( 5 , 3 ) ( 5 , 4 ) 0( 6 , 1 ) ( 6 , 2 ) ( 6 , 3 ) ( 6 , 4 ) ( 6 , 5 ) 0( 7 , 1 ) ( 7 , 2 ) ( 7 , 3 ) ( 7 , 4 ) ( 7 , 5 ) ( 7 , 6 ) 0. . . . . . . . . . . . . . . . . . . . . 0( , 1 ) ( , 2 ) ( , 3 ) ( , 4 ) ( , 5 ) ( , 6 ) . . . ( ,d dd d d dd d d d dd d d d d dd n d n d n d n d n d n d n n 1 ) 0圖中我們用 d(i,j)表示項(xiàng) 間的距離，有 d(i,j) 0。 當(dāng) d(i,j)=0 時(shí)表示二者完全相同； 當(dāng) d(i,j)0 時(shí)表示二者不同，并且 d 的值越大表示文件 條目 間的差異越大。 對(duì)于條目 i 和 j 之間距離的 d(i,j)的計(jì)算，我們采用如下加權(quán)公式： 北京大學(xué) 網(wǎng)絡(luò)實(shí)驗(yàn)室碩士學(xué)位論文 30 ( , )11( , )i f j fp x 由前文文件檢索模型可知，此處 p=6。我們分別計(jì)算文件條目 i 和 j 的 6 項(xiàng)對(duì)應(yīng)屬性的距離，再進(jìn)行加權(quán)求和最后再進(jìn)行標(biāo)準(zhǔn)化處理。 由于文件條目的 6 項(xiàng)屬性的數(shù)據(jù)類型和含義不完全相同，因此具體的計(jì)算方法區(qū)別較大，在計(jì)算時(shí)需要分別考慮。 下圖為各個(gè)屬性的數(shù)據(jù)類型和計(jì)算方法。 表格 5件條目各個(gè)屬性數(shù)據(jù)類型 屬性 數(shù)據(jù)類型 距離計(jì)算方法 ： 性距離的計(jì)算方法 示文件的 不包含擴(kuò)展名的主名的名稱，數(shù)據(jù)類型為字符串型。對(duì)于這種字符串類型數(shù)據(jù)的處理，一般情況下可以按照文檔的相似度的方式進(jìn)行。但由于文件名通常都比較短小，命名多數(shù)情況下也不規(guī)范。這里并不建議按照文檔的形式來處理。 我們這里采用的處理方法是按照最小編輯距離的方法來處理。 編輯距離是指兩個(gè)字符串通過插入字符、刪除字符、改寫字符而變?yōu)橄嗤址枰牟僮鞔螖?shù)。 比如： d(“” = 1 d(“” = 1 d(“ “ = 2 d(“” = 4 利用動(dòng)態(tài)規(guī)劃的方法計(jì)算編輯距離，時(shí)間復(fù)雜性可以達(dá)到 O(空間復(fù)雜性北京大學(xué) 網(wǎng)絡(luò)實(shí)驗(yàn)室碩士學(xué)位論文 31 為 O（ 計(jì)算方法為一個(gè)遞歸算法： d(, ) = 0 d(s, ) = d(, s) = |s| （ |s|表示 s 的長(zhǎng)度） d(s1+s2+= d(+ （ if ） , d(s1+ 1, d(s2+ 1 ) 性距離的計(jì) 算方法 文件的擴(kuò)展名，雖然數(shù)據(jù)類型為字符串，但因此常見的文件類型是有限的，因此可以看成是枚舉類型，在聚類算法中則稱為標(biāo)稱變量。在進(jìn)行距離計(jì)算時(shí)可以按照聚類算法中對(duì)于此類數(shù)據(jù)類型的標(biāo)準(zhǔn)處理方法進(jìn)行處理，即其距離只是一個(gè)二值函數(shù)：取值相同則距離為 0；否則距離為 1。但考慮到文件擴(kuò)展名是有實(shí)際含義的，而且很多時(shí)候這些不同的擴(kuò)展名之間還有著豐富的聯(lián)系，因此我們能夠?qū)⑵涮幚淼母泳_。 一般的，我們可以按照文件的擴(kuò)展名對(duì)文件類型進(jìn)行分類。比如可以將文件分成：程序、圖片、音樂、影視、源碼等類別。在每個(gè)類別內(nèi)部，可 能又有更深的層次，比如源碼可能又分為 C/C+源碼， 碼等，而 C/C+源碼又可以進(jìn)一步分為頭文件和實(shí)現(xiàn)文件等這樣就形成了一棵樹。不過要注意的是，這棵樹不是平衡的，某些葉節(jié)點(diǎn)可能比較深，另外一些可能比較淺。 為了形成這棵樹，我們還需要說明如下。 首先，我們假設(shè)每種擴(kuò)展名只對(duì)應(yīng)于樹中的一個(gè)節(jié)點(diǎn)； 其次，我們?cè)O(shè)置一個(gè)根節(jié)點(diǎn)，根節(jié)點(diǎn)本身不包含如何任何文件類型； 再有，對(duì)于沒有擴(kuò)展名的文件，我們?yōu)槠滟x予一個(gè)特殊的值，并且直接位于根節(jié)點(diǎn)之下；對(duì)于不能識(shí)別的擴(kuò)展名我們也做同樣處理。 這樣，最后形成了一棵類似 下圖的樹： 北京大學(xué) 網(wǎng)絡(luò)實(shí)驗(yàn)室碩士學(xué)位論文 32 r o o tp r o g r a m v i d e o m u s i c p i c t u r e s o u r c e o t h e rR e a l f o r m a t. a v i. r m v C + l a n g u a g e. j a v a. hi m p l e m en t a t i o n. c . c p 5件擴(kuò)展名屬性距離計(jì)算 這樣，計(jì)算任意兩個(gè)文件條目類型屬性的距離演變成了計(jì)算樹中任意兩個(gè)葉節(jié)點(diǎn)之間的關(guān)系。對(duì)于樹中任意兩個(gè)葉節(jié)點(diǎn)的距離，則表示為其相似程度的倒數(shù)。而相似程度的計(jì)算，可以按照如下算法。樹中每個(gè)節(jié)點(diǎn)均存在一條從根節(jié)點(diǎn)到達(dá)它所在位置的唯一路徑 P。兩個(gè)節(jié)點(diǎn)的相似程度可以表示為它們各自路徑 P 中公共節(jié)點(diǎn)的個(gè)數(shù)的函數(shù)。 在實(shí)現(xiàn)上，我們選取 如下的函數(shù)： 假設(shè)需要計(jì)算兩個(gè) 分別為 點(diǎn) 此屬性上的距離。設(shè) 應(yīng)的路徑為 公共節(jié)點(diǎn)個(gè)數(shù)為 k（根節(jié)點(diǎn)除外），則我們?nèi)。?2 , 2 , 2 11( , ) 2ij kd x x 北京大學(xué) 網(wǎng)絡(luò)實(shí)驗(yàn)室碩士學(xué)位論文 33 性距離的計(jì)算方法 性表示文件條目的文件大小，以字節(jié)為單位，數(shù)據(jù)類型為整數(shù)。由于文件大小的取值范圍跨度很大，一般能夠從幾十字節(jié)到幾十億字節(jié)，因此不適合按照一般區(qū)間標(biāo)度變量的方法來計(jì)算，可以按照比例標(biāo)度型變量來處理。首先對(duì) ,3 ,3lo g ( )過在實(shí)際應(yīng)用中要注意的是，因?yàn)?取值范圍是非負(fù)整數(shù)，可能取 0，因此不能直接取 以考慮首先將 x 1 再取 , 3 , 3lo g ( 1 )然后將 化為對(duì)應(yīng)的 3 3,3 3s 其中. . . )3 1 , 3 2 , 3 , 31 ( y y 3 1 , 3 3 2 , 3 3 3 31 ( | | | | . . . | | )ns y m y m y 進(jìn)行標(biāo)準(zhǔn)化處理之后，再求二者之差： 3 , 3 , 3 , 3 , 3( , )i j i jd x x z z 性距離的計(jì)算方法 性表示文件的最后修改日期，前面已經(jīng)說過，我們將原來的字符串格式統(tǒng)一轉(zhuǎn)化為整數(shù)，比如按照距離公元元年元旦的日期數(shù)。對(duì)于整數(shù)，屬于區(qū)間標(biāo)度變量。為了更好的計(jì)算各個(gè)項(xiàng)目該屬性之間的距離，我們并不直接計(jì)算各個(gè)條目的差，而是先對(duì)其進(jìn)行標(biāo)準(zhǔn)化處理。將 化為對(duì)應(yīng)的 4 4,4 4s 北京大學(xué) 網(wǎng)絡(luò)實(shí)驗(yàn)室碩士學(xué)位論文 34 其中. . . )4 1 , 4 2 , 4 , 41 ( x x 4 1 , 4 4 2 , 4 4 , 4 41 ( | | | | . . . | | )ns x m x m x 進(jìn)行標(biāo)準(zhǔn)化處理之后，再求二者 之差： 4 4 4 , 4 , 4( , )i j i jd x x z z 性距離的計(jì)算方法 由于在實(shí)際文件共享系統(tǒng)中， 最常見的情況就是 址，而兩個(gè) 址之間的距離的比較是沒有實(shí)際意義的，因此我們忽略兩個(gè) 性的之間的距離，或者可以表示為： 5 , 5 , 5( , ) 0x x 性距離的計(jì)算方法 示文件從根目錄開始到其節(jié)點(diǎn)所經(jīng)過的路徑。其重要特點(diǎn)就是路徑是分段的，是由多個(gè)字符串連接而成的。比如路徑： / 以看成是由分段的子字符串 成的。 在對(duì) 行比較的時(shí)候，我們將每個(gè)路徑拆分成多個(gè)子字符串，然后比較其中公共子字符串的個(gè)數(shù)占全部子字符串的比例。 6 , 6 , 6( , )c o x 公式中 別表示 性的分段的個(gè)數(shù)， 公共子字符串的個(gè)數(shù)。 用戶點(diǎn)擊記錄進(jìn)行聚類 在本體系中需要對(duì)用戶的點(diǎn)擊日志進(jìn)行聚類，以便能夠得到這 k 個(gè)不同的用戶查詢意圖。 聚類常用的方法有 法， 法和 法。根據(jù)我們的具體情況，這里選用自底向上的 法。 北京大學(xué) 網(wǎng)絡(luò)實(shí)驗(yàn)室碩士學(xué)位論文 35 對(duì)本方法的圖示說明如下： bs t e p 0 s t e p 1 s t e p 2 s t e p 3 s t e p 4d , d , b , c , d ,ea g g l o m e r a t i v e( A G N E S )圖 5假設(shè)共有 5 個(gè)對(duì)象 a,b,c,d,e，我們將其根據(jù)彼此的相關(guān)程度進(jìn)行聚類。 首先，將每個(gè)待聚類的元素獨(dú)立劃分為一 個(gè) 自己的類別，如果有 n 個(gè)元素，則開始時(shí)共有 n 類。然后將距離最近的兩個(gè)元素歸為一 類，此時(shí)有 ；此后再將距離次近的歸為一類，類別共 ；如此不斷重復(fù)如果沒有結(jié)束標(biāo)志，則最終將會(huì)把所有類別都?xì)w為一類。所以必須要設(shè)置結(jié)束標(biāo)志。 這其中有幾點(diǎn)要說明： 束標(biāo)志的設(shè)定 結(jié)束標(biāo)志可以從幾個(gè)方面來綜合考慮。首先是距離因素，設(shè)定當(dāng)距離最近的兩個(gè)類的距離大于某個(gè)類別間的距離閥值 D 時(shí)不再進(jìn)行合并操作，設(shè)置距離標(biāo)志D 可以防止最后生成的類別過少。另外由規(guī)律 2 可知相同的查詢串通常只表示很少的查詢意圖，因此可以設(shè)定一個(gè)最大類別數(shù) G，這個(gè)表示可以防止最后生成的類別數(shù)過多。通過這兩個(gè)結(jié)束標(biāo)志的綜合運(yùn)用， 可以使最終的類別數(shù)量控制在較理想的范圍中。 有多個(gè)元素的類別之間距離的計(jì)算 當(dāng)類別包含多個(gè)元素時(shí)，計(jì)算它們之間的距離有三種不同的方法：計(jì)算距離最近的兩點(diǎn)之間的距離、最遠(yuǎn)的兩點(diǎn)之間的距離、或者用中心點(diǎn)來計(jì)算距離。我們這里選用中心點(diǎn)來計(jì)算二者的距離。這個(gè)中心點(diǎn)可能是類別中真實(shí)存在的一個(gè)北京大學(xué) 網(wǎng)絡(luò)實(shí)驗(yàn)室碩士學(xué)位論文 36 元素，但也可能是一個(gè)并不真正包含的虛擬的元素。 立點(diǎn)的處理 事實(shí)上，一些查詢串可能會(huì)對(duì)應(yīng)一兩個(gè)或很少的孤立查詢記錄，這些查詢記錄和其余大量的查詢記錄的相似度很低。通過人工查看的方法，我們發(fā)現(xiàn)很多這些孤立查詢記錄其實(shí)都是看上去不 太正常的記錄，比如對(duì)于一些大小為 0 的文件進(jìn)行下載，或者下載一些快捷方式文件等。我們認(rèn)為這些孤立點(diǎn)是因?yàn)橛脩舨恍⌒幕虿涣私馑?。而這些文件條目實(shí)際上并不應(yīng)該被下載，而應(yīng)該被拋棄。因此我們需要對(duì)這些孤立點(diǎn)進(jìn)行丟棄。 練集的生成 由于在進(jìn)行完聚類后我們會(huì)對(duì)查詢?cè)龠M(jìn)行分類，因此我們考慮利用聚類中的文件條目作為分類時(shí)的訓(xùn)練集。在聚類完成后我們將保留每個(gè)查詢串的每個(gè)類別足夠的文件條目。 查詢結(jié)果集合進(jìn)行分類 常用的分類算法有 k 還有 。我們采用 法。 其具體步驟為： 首先需要有一個(gè)訓(xùn)練集。對(duì)于每個(gè)可能的類別，各自有一些屬于該類別的對(duì)象。給定一個(gè)待分類的對(duì)象，系統(tǒng)在訓(xùn)練集中查找與其最相似的 k 個(gè)對(duì)象 (稱為鄰居 )，并根據(jù)這些鄰居所屬的類別情況來給該對(duì)象的候選類別評(píng)分，最后按照分值來確定待分類對(duì)象的類別。北京大學(xué) 網(wǎng)絡(luò)實(shí)驗(yàn)室碩士學(xué)位論文 37 第 6章 系統(tǒng)實(shí)現(xiàn)與評(píng)測(cè) 統(tǒng)設(shè)計(jì)體系結(jié)構(gòu)圖 實(shí)際系統(tǒng)的體系結(jié)構(gòu)圖如下?？紤]到一些實(shí)現(xiàn)問題，和上一章的系統(tǒng)模型略有區(qū)別。 I n d e x P a r t C l u s t e r i n g P a r t C o l l e c t i o n P a r t C l i c k L o g D a t a B a s e T r a i n i n g S e t D a t a B a s e C l i c k L o g S e r v e r C l u s t e r i n g Q u e r y q N o r m a l I n d e x S y s t e m I t e m s C a t e g o r i z a t i o n F i l t e r C a t e g o r i e s C l i c k l o g I t e m s T r a i n i n g s C l i c k l o g 圖 6下面我們來詳細(xì)介紹此系統(tǒng)設(shè)計(jì)。 戶行為收集部分 分為用戶點(diǎn)擊記錄收集部分，是實(shí)時(shí)運(yùn)行的。 在用戶進(jìn)行查詢后，文件檢索系統(tǒng)返回包含查詢串的結(jié)果。用戶從中選取自己認(rèn)為正確的文件條目。用戶的選取操作就是一次鼠標(biāo)的點(diǎn)擊操作。這個(gè)點(diǎn)擊動(dòng)作自動(dòng)觸發(fā)到我們的后臺(tái) 序，程序先將用戶的下載請(qǐng)求轉(zhuǎn)向到真正的下載地址，后臺(tái)再發(fā)送一個(gè)記錄點(diǎn)擊操作的服務(wù)請(qǐng)求。該服務(wù)請(qǐng)求由 記錄 到 。我們稱用戶的每次點(diǎn)擊對(duì)應(yīng)的文件條目為北京大學(xué) 網(wǎng)絡(luò)實(shí)驗(yàn)室碩士學(xué)位論文 38 過這樣反復(fù)多次后， 記錄了大量的 個(gè) 含一個(gè)查詢串和對(duì)應(yīng)的文件條目 類部分 此部分為聚類操作部分，每隔一段時(shí)間運(yùn)行一次。在實(shí)際系統(tǒng)中可以根據(jù)用戶數(shù)量來設(shè)定為每小時(shí)或每天一次。 這部分首先從 讀取全部的 目，然后對(duì)每個(gè)查詢串依次進(jìn)行處理。取出每個(gè)查詢串對(duì)應(yīng)的 錄，進(jìn)行聚類 ，聚類后得到 k 個(gè)類別。如前文所述，其中可能存在一些孤立點(diǎn)，然后按照標(biāo)準(zhǔn)對(duì)這些孤立點(diǎn)進(jìn)行考察，需要的話要拋棄掉其對(duì)應(yīng)的孤立類別。 聚類操作完成后，將聚類的結(jié)果存入 。 至此，我們就得到了實(shí)現(xiàn)免用戶干預(yù)的、基于反饋信息的檢索系統(tǒng)所需要的反饋數(shù)據(jù)。 引部分 完成了上面兩個(gè)部分的工作，就可以進(jìn)行真正的反饋了。對(duì)于用戶的查詢串 q，首先使用常規(guī)檢索系統(tǒng)進(jìn)行檢索，就可得到一個(gè)文件條目 集合。然后在取出對(duì)應(yīng)于查詢串 q 的 k 個(gè)類別的 訓(xùn)練集。利用這些訓(xùn)練集條目為剛剛通過常規(guī)查詢得到的 合進(jìn)行分類。此處我們限定每個(gè)文件條目至多屬于 1 個(gè)類別。分類后可能得到 k+1 個(gè)類別（某些 能不屬于任何類別），以及每個(gè)條目和其所屬類別的相似程度。利用分類的類別和相似度，系統(tǒng)可以重新根據(jù)此信息進(jìn)行輸出。對(duì)于那些不屬于任何類別的文件條目，通常也是用戶所不太關(guān)心的結(jié)果，可以選擇拋棄或排在結(jié)果頁面的最后。 它實(shí)現(xiàn)中的問題 錄用戶對(duì)查詢結(jié)果的選取 對(duì)于用戶對(duì)查詢結(jié)果的選取的記錄，一般有兩種方法，采用 技術(shù)和技術(shù)。為了方便 用戶的使用，不改變用戶的任何使用習(xí)慣，我們采取 樣用戶在使用時(shí)就不需要絲毫的改變，而我們也能夠得到足夠的記錄信息。 北京大學(xué) 網(wǎng)絡(luò)實(shí)驗(yàn)室碩士學(xué)位論文 39 具體說來，傳統(tǒng)網(wǎng)頁上的鏈接一般如下： 們采用 術(shù)將其進(jìn)行改造，改造后的形式如下： 意其中有 2 處 本。第一處是 息，當(dāng)用戶點(diǎn)擊了該鏈接時(shí)，自動(dòng)重新轉(zhuǎn)向到了我們的服務(wù)器上，服務(wù)器有一個(gè)接收該請(qǐng)求的 序個(gè)程序自動(dòng)轉(zhuǎn)向到實(shí)際的 載地址，然后向 送一個(gè)記錄請(qǐng)求， 記錄下整個(gè)查詢串和文件條目信息。 腳本中的另一處是 個(gè)是為了處理當(dāng)用戶已經(jīng)點(diǎn)擊該鏈接后卻又突然想復(fù)制該鏈接而使用的。 只所以在此處使用了 不是直接改變鏈接地址，是為了便于那些并不希望通過直接點(diǎn)擊，而是希望使用下載工具或想復(fù)制下載地 址的用戶的方便。通過現(xiàn)在這種改造，用戶看到的頁面和鏈接地址都是和原始信息是完全一致的。 文件類型屬性距離計(jì)算方法的實(shí)現(xiàn) 前面談到對(duì)于常見的文件擴(kuò)展名，我們將其各自賦予一個(gè)屬性值，屬性值代表了在文件類別樹中從根結(jié)點(diǎn)到該文件類型所在節(jié)點(diǎn)的所有節(jié)點(diǎn)編號(hào)的集合。節(jié)點(diǎn)的編號(hào)示例如下圖所示，每個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)的編號(hào)都是從 1 開始的，并沒有全局性的編號(hào)。 北京大學(xué) 網(wǎng)絡(luò)實(shí)驗(yàn)室碩士學(xué)位論文 40 r o o 3 4 5 61 21 21 21 21 2圖 6-2 性距離計(jì)算方法的實(shí)現(xiàn) 比如對(duì)應(yīng)圖中左下角的灰色節(jié)點(diǎn)來說，對(duì)應(yīng)的路徑為 下角的灰色節(jié)點(diǎn)對(duì)應(yīng)的路徑則為 這樣，如果比較兩個(gè)節(jié)點(diǎn)的相似度，我們只需計(jì)數(shù)它們的路徑中相同的節(jié)點(diǎn)個(gè)數(shù)即可。比如路徑為 節(jié)點(diǎn)和 節(jié)點(diǎn)，它們的路徑中有一個(gè)相同的節(jié)點(diǎn) 2，或者說相似度為 1 層；路徑為 節(jié)點(diǎn)和 節(jié)點(diǎn)，它們的相似度為2 層；路徑為 節(jié)點(diǎn)和路徑為 7 的節(jié)點(diǎn)相似度則為 0。 具體文件類型分類列表見附錄 1。 配置文件格式，擴(kuò)展名分類文件的配置文件的格式舉例如下： 1 1 1 1 1 2 文件說明： 北京大學(xué) 網(wǎng)絡(luò)實(shí)驗(yàn)室碩士學(xué)位論文 41 作用：通過讀取文件得到每個(gè)擴(kuò)展名對(duì)應(yīng)的路徑。 文件格式：每 3 行為一個(gè)記錄。每個(gè)記錄中第一行是空行；第 2 行是路徑，格式為每層節(jié)點(diǎn)編號(hào)用制表符分割；第 3 行是擴(kuò)展名列表，每個(gè)擴(kuò)展名都以豎線“ |”結(jié)束。 距離計(jì)算方法的實(shí)現(xiàn)： 在系統(tǒng)實(shí)現(xiàn)時(shí)，定義了一個(gè) ，它代表了一個(gè)具體的節(jié)點(diǎn)路徑，承自 里的 標(biāo)準(zhǔn) 且實(shí)現(xiàn)了如下方法來計(jì)算兩個(gè)路徑之間的距離： ( 統(tǒng)的評(píng)測(cè)環(huán)境 我們采用天網(wǎng)千帆文件搜索引擎為測(cè)試系統(tǒng)。天網(wǎng)千帆文件搜索引擎為北京大學(xué)網(wǎng)絡(luò)實(shí)驗(yàn)室開發(fā)的一個(gè) 件搜索引擎，有較大的用戶訪問量。在 2005 年4 月，我們先后運(yùn)行了普通文件搜索引擎和我們?cè)O(shè)計(jì)的新型文件搜索引擎，并記錄了用戶的查詢記錄和用戶對(duì)查詢結(jié)果的選取信息。 為了保證評(píng)測(cè)效果的準(zhǔn)確性，在使用了新系統(tǒng)后，我們沒有通知任何用戶，也沒有改變?nèi)魏斡脩艚缑?，使測(cè)試盡量在用戶不知情的 情況下進(jìn)行。對(duì)于分類后不能歸入任何類別的文件條目，為了保證總體查詢結(jié)果數(shù)量不變，我們也沒有進(jìn)行拋棄，而是放在排序的最后返回給用戶。這里采用的排序方法是在頁內(nèi)按照各個(gè)初始結(jié)果集合 各個(gè)條目距離其類別的距離遠(yuǎn)近進(jìn)行排序，對(duì)不同的類別之間并不進(jìn)行排序。在結(jié)果的表現(xiàn)形式上與普通搜索引擎無異。 比較試驗(yàn)共進(jìn)行了 8 天，其中 4 天為普通文件檢索系統(tǒng)，另外 4 天則為我們的新系統(tǒng)。我們分別比較了用戶對(duì)前 2 頁查詢結(jié)果頁面中點(diǎn)擊的文件條目在該頁面中的排序的情況，共取得了 8 組比較數(shù)據(jù)。 測(cè)結(jié)果 具體比較結(jié)果參見下圖。圖中橫坐標(biāo)表 示 8 組比較數(shù)據(jù)，縱坐標(biāo)為各組試驗(yàn)數(shù)據(jù)的在頁面中點(diǎn)擊的條目的排序的平均值。圖中上部的曲線（虛線）為普通文件檢索系統(tǒng)的結(jié)果，下面的曲線（實(shí)線）為新系統(tǒng)的試驗(yàn)結(jié)果。 北京大學(xué) 網(wǎng)絡(luò)實(shí)驗(yàn)室碩士學(xué)位論文 42 圖 6從圖中可以明顯的看到：在新系統(tǒng)下，用戶所點(diǎn)擊的文件條目在頁面中的排序比普通系統(tǒng)有了較大幅度的提前。 在我們的試驗(yàn)系統(tǒng)中，而使用了新系統(tǒng)后，點(diǎn)擊條目的平均排名為 排名前 。檢索效果有了較大幅度的改進(jìn)。 由此可驗(yàn)證本文所述新型文件檢索系統(tǒng)的正確性。北京大學(xué) 網(wǎng)絡(luò)實(shí)驗(yàn)室碩士學(xué)位論文 43 第 7章 總結(jié)與展望 結(jié) 作者在本文中首先對(duì)文件檢索系統(tǒng)進(jìn)行了一些基礎(chǔ)性的研究工作，提出了文件檢索系統(tǒng)的檢索模型，并提出了評(píng)測(cè)的指標(biāo)。然后在對(duì)用戶使用文件檢索系統(tǒng)的行為和習(xí)慣進(jìn)行記錄的基礎(chǔ)上，發(fā)現(xiàn)了用戶行