一個借助查詢歷史改善結(jié)果排序的文件檢索系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)碩士畢業(yè)論文

北京大學(xué)碩士研究生學(xué)位論文題目：一個借助查詢歷史改善結(jié)果排序的文件檢索系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)姓 名： 學(xué) 號： 院 系：信息科學(xué)技術(shù)學(xué)院專 業(yè)：計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)研究方向：計(jì)算機(jī)網(wǎng)絡(luò)與分布式系統(tǒng)導(dǎo) 師： 1版權(quán)聲明版權(quán)聲明任何收存和保管本論文各種版本的單位和個人，未經(jīng)本論文作者同意，不得將本論文轉(zhuǎn)借他人，亦不得隨意復(fù)制、抄錄、拍照或以任何方式傳播。否則，引起有礙作者著作權(quán)之問題，將可能承擔(dān)法律責(zé)任。 2摘摘 要要隨著網(wǎng)絡(luò)的發(fā)展，網(wǎng)絡(luò)上提供文件共享服務(wù)的服務(wù)器越來越多，共享的文件數(shù)量也隨之增加。如何更好的檢索、利用這些共享文件成為一個重要的問題。針對用戶對文件檢索的需求，本文在文件檢索技術(shù)領(lǐng)域有如下貢獻(xiàn)。1. 本文首先提出了一個文件檢索的模型，明確了在文件檢索模型中檢索對象、查詢串、查詢與檢索對象的匹配方式三部分的含義。檢索對象，即文件條目表示為六元組name, ext, size, date, site, path的形式，查詢串表示為以空格分隔的字符串的集合，查詢與檢索對象的匹配則表示為查詢串與文件條目的匹配串之間的匹配。2. 提出了對文件檢索系統(tǒng)進(jìn)行評測的指標(biāo)。將查詢結(jié)果視作集合時以查全率、查準(zhǔn)率為評測指標(biāo)。將查詢結(jié)果視作有序序列時，分析了查詢結(jié)果的相關(guān)性、連接下載速度以及結(jié)果的可用性等因素對排序的影響，并提出了對排序進(jìn)行評測的指標(biāo)排序指數(shù)。作者還提出對于兩個排序策略進(jìn)行比較時，應(yīng)當(dāng)在結(jié)果的每個頁面內(nèi)部應(yīng)用排序策略，而不是在全體結(jié)果集合上應(yīng)用排序策略，并比較平均用戶選取條目的頁內(nèi)排名。3. 通過統(tǒng)計(jì)、分析用戶對文件搜索引擎的檢索和對檢索結(jié)果中下載地址條目的選取，作者發(fā)現(xiàn)了用戶行為習(xí)慣中的兩個重要規(guī)律：一、少數(shù)查詢串占據(jù)了全部查詢請求的大多數(shù)，具體而言，前 20%的熱門查詢串占據(jù)了全部查詢請求的80%；二、對全體用戶而言，假設(shè)有 n 次不同的查詢請求使用了同一個查詢串，并且它們代表 k 類不同的查詢意圖。那么通常 k3，因而在 n 較大的情況下，則 n/k 的值較大，即大量的來自不同用戶的請求代表了相同的查詢意圖。4. 基于上文所述，作者設(shè)計(jì)并實(shí)現(xiàn)了一個真實(shí)的系統(tǒng)。該系統(tǒng)借助查詢歷史改善結(jié)果的排序。與一般基于用戶歷史信息的檢索系統(tǒng)不同的是，本系統(tǒng)借助的歷史信息不局限于當(dāng)前用戶的歷史信息，還包含提交了相同查詢串的其他用戶的查詢信息?；蛘哒f，即使當(dāng)前用戶是第一次使用本系統(tǒng)，本系統(tǒng)也能利用其他用戶的歷史記錄來改進(jìn)結(jié)果的排序和篩選。作者最后還驗(yàn)證了其實(shí)際的效果。應(yīng)用本方法后，平均用戶選取條目的頁內(nèi)排名從原來的13.70 名前進(jìn)到了 8.93 名。試驗(yàn)結(jié)果表明文中所做的分析是正確的。關(guān)鍵詞：文件檢索系統(tǒng)，查詢歷史，檢索模型 3The Design and Implementation of a File Index System which Improve the Order by Query History AbstractWith the rapid expansion of the Internet, there are more sharing file servers. And the number of sharing files is increasing rapidly too. So its more important to retrieve these files easily.For the requirement of file retrieving of the users, we did the following jobs:1. We proposed a file index model. The model is composed of the expression of an index object, the expression of a query, and how the query word matches the index object. The index object can be expressed as name, ext, size, date, site, path, the query string is expressed as strings separated by space, and the matching between query and index object is realized by matching the query string and the matching strings of the file item.2. We also proposed the evaluation indicator for the file index evaluation. The precision and recall are useful when we evaluate the query result. But the result is not a set, but an ordered list. So we indicated the factors in order: the relativity of the item, the connecting and download speed and the availability of the site. We proposed how to evaluate the order: average rank of chosen items. If we just want to compare two ranking strategy, we should not reorder all items in the result set but only reorder the items within each page and compare the average rank of chosen items within page.3. By analyzing the records of users queries and the file items that users chosen from a real file search engine, we discovered two lows. 1). Most query strings are repeating hot query strings. 80% query words are the top 20% hot query strings. 2) If there are n times of queries using the same query strings, and the total number of different intensions is k. Then k should be a very small number (usually, k5對應(yīng)的查詢串的個數(shù)3315781010從上表可見，查詢意圖只有 13 個的查詢串占全部記錄數(shù)據(jù)的絕大部分，超過 5 種不同意圖的查詢串在統(tǒng)計(jì)的日志中根本就沒有出現(xiàn)。我們再來看一下 n 和 k 的比例的分布，統(tǒng)計(jì)結(jié)果如下圖。圖中橫坐標(biāo)表示查詢串被查詢的次數(shù) n，綜坐標(biāo)為 n/k 的比值。要說明一點(diǎn)就是為了使圖像中的點(diǎn)線顯示清晰，我們忽略了很少量的查詢次數(shù)非常高的詞（這些點(diǎn)對應(yīng)的橫坐標(biāo)值非常大），但事后的手工驗(yàn)證仍然證明了它們符合本文的規(guī)律。 26110100100001002003004005006007008009001000圖 4-3 查詢串與查詢意圖種類比值分析其中橫坐標(biāo)為查詢串查詢次數(shù) n，綜坐標(biāo)為 n/k 比值（為指數(shù)標(biāo)度）從圖中可以看到，當(dāng) n100 時，n/k 的值都在 30 以上。由上面的分析我們能夠知道，盡管查詢串不同，但一般說來，它們所代表的查詢意圖的數(shù)量并不是太多的，通常在1-3 種，并且在 n 較大的情況下（如n100），通常 n/k 的比值較大（本例中大于 30）。因此我們得到了第二個重要的規(guī)律：規(guī)規(guī)律律二二：假假設(shè)設(shè)有有 n 次次不不同同的的請請求求查查詢詢了了同同一一個個查查詢詢串串，并并且且它它們們代代表表k 種種不不同同的的查查詢詢意意圖圖。在在 n 較較大大的的情情況況下下（ n100），n/k 的的值值較較大大（ n/k30）。4.3用戶行為特點(diǎn)的啟發(fā)利用上面的用戶行為特點(diǎn)中的兩個規(guī)律，以及前面關(guān)于相關(guān)反饋方法的思路，可以考慮采用如下思路來實(shí)現(xiàn)一個借助查詢歷史信息改善結(jié)果排序的文件檢索系統(tǒng)。從上面的特征我們知道，大多數(shù)的查詢請求不僅其查詢串本身是重復(fù)的，而且其所代表的查詢意圖也是重復(fù)的。這樣我們就可以由“較早的相同的查詢串的結(jié)果選取記錄”作為用戶的反饋信號。這樣一來，后來提交同樣查詢串的用戶不需要 27任何主動干預(yù)，就可以得到經(jīng)過反饋信號處理過的重新排序的查詢結(jié)果了。當(dāng)然，由于用戶意圖并不唯一，我們并不能確定究竟本次查詢的用戶是哪種查詢意圖，但因?yàn)?k 值通常都相當(dāng)?。ㄐ∮诘扔?3），因此對用戶而言，很容易從這為數(shù)極少的查詢意圖中找到滿足自己意圖的結(jié)果。具體而言，我們可以考慮如下的思路。首先記錄下每次用戶對查詢結(jié)果的選取。我們認(rèn)為，用戶在查詢結(jié)果中點(diǎn)擊的下載地址，就是用戶認(rèn)為比較理想的下載地址。通過一段時間的記錄，我們就得到了對于大量查詢串的較理想的匹配結(jié)果。對于一個查詢串q，我們有一個用戶認(rèn)為較好的文件條目的集合 S，我們將其表示為一個二元組 (q,S)。這樣，我們就得到了大量的這樣的二元組。依據(jù)規(guī)律 2，我們知道每個查詢串可能代表幾個不同的查詢意圖，那么不同的查詢意圖對應(yīng)的理想下載地址肯定不同（否則就是相同的查詢意圖了），我們可以采用聚類的方法對每個 S 中的文件條目進(jìn)行聚類。聚類后，對于每個q，我們會得到 k 種不同的類別，這 k 個類別就也就反映了不同的查詢意圖，而每個類別中的文件條目，就可以看作這個類別的訓(xùn)練集。每個類別中的條目個數(shù)，也直接反映了這個類別的權(quán)重。當(dāng)再次有用戶查詢同樣的查詢串 q 時，我們首先采用原始的檢索方法，得到一個結(jié)果集合，然后用聚類得到的 k 個類別和訓(xùn)練集對其進(jìn)行分類處理。一些條目被分到這 k 個類別中，另外一些可能不屬于任何類別。不屬于任何類別的條目往往也是用戶不太需要的條目，可以考慮拋棄或排在結(jié)果的最后輸出。 28第5章 系統(tǒng)體系結(jié)構(gòu)與主要算法5.1系統(tǒng)體系結(jié)構(gòu)基于以上分析，我們設(shè)計(jì)了如下的檢索系統(tǒng)來改善文件檢索系統(tǒng)的排序。Query String (q)Normal Index System (I)Index Result (S0)Feedback data DataBaseSite List DataBasequeryClusteringThe training set for query item qItems not belong to any groupResult after Categorization (S)Categorization, OrderingFileitems that user clicked圖 5-1 系統(tǒng)結(jié)構(gòu)圖下面我們來詳細(xì)介紹這個模型。我們首先查看模型中的各個組成部分。Query String (q)：用戶輸入的查詢串；Normal Index System(I)：常規(guī)的文件檢索系統(tǒng)；Index Result(S0)：初始查詢結(jié)果集；Feedback Data DB(F)：該數(shù)據(jù)庫中記錄了已有的每個查詢請求和它對應(yīng)的不同的 k 種查詢意圖，以及每種意圖的作為訓(xùn)練集的文件條目。Fileitem DB(D)：該數(shù)據(jù)庫中保存了每次用戶進(jìn)行檢索后對查詢結(jié)果的選取情況。具體而言，當(dāng)用戶進(jìn)行查詢后，檢索系統(tǒng)返回結(jié)果，當(dāng)用戶在結(jié)果頁面中對文件條目進(jìn)行點(diǎn)擊并下載時，本模型會記錄用戶的點(diǎn)擊選取行為。庫中的每條記錄含有當(dāng)前的查詢串和用戶點(diǎn)擊的這條記錄的具體文件信息：文件名稱、擴(kuò)展名稱、最后修改日期、文件大小、文件所在站點(diǎn)和文件所在的路徑。 29本檢索系統(tǒng)的工作流程如下：數(shù)據(jù)庫 F 中需要足夠的數(shù)據(jù)記錄系統(tǒng)才能夠進(jìn)行工作。因此在系統(tǒng)運(yùn)行之初，系統(tǒng)便開始自動記錄用戶的點(diǎn)擊，并將記錄填充進(jìn)數(shù)據(jù)庫D。數(shù)據(jù)庫 D 每隔一段時間，對每個查詢串 q 進(jìn)行一次聚類操作，這樣便得到了每個查詢串所代表的k種查詢意圖?，F(xiàn)在我們假設(shè) F 中已經(jīng)包含有了足夠的記錄信息。當(dāng)用戶輸入查詢串q 后，一方面，模型中最上面的流程開始工作，常規(guī)的檢索系統(tǒng)進(jìn)行檢索，得到一個原始的查詢結(jié)果 S0。另一方面，如模型圖示中的中層的流程， q 被送入數(shù)據(jù)庫 F。數(shù)據(jù)庫 F 返回對應(yīng)的 k 種意圖和其點(diǎn)擊記錄集合。這些記錄將作為下一步分類工作的訓(xùn)練集。有了 S0和這 k 種類別，下面將利用這 k 種類別的訓(xùn)練集對 S0進(jìn)行分類。分類后我們將 S0分成了 k+1 類，其中新增加的這個類別是那些不屬于任何類別的文件條目 item 集合。對于不屬于任何類別的條目，我們認(rèn)為它是用戶不太關(guān)心的結(jié)果，可以把它拋棄或放入輸出結(jié)果的最后。這里有一點(diǎn)要注意，就是 k 種類別的地位是不同的，類別本身也是有權(quán)重的，權(quán)重可以由聚類時每個類別中的條目數(shù)量來決定。這樣在最后輸出時可以按照權(quán)重本身對類別進(jìn)行排序。由于 k 的取值通常都比較?。ㄐ∮诘扔?3），用戶最終看到的結(jié)果往往是接近用戶的真實(shí)查詢意圖的。然后就可以按照一般的條目列表方式或者聚類的樹型結(jié)構(gòu)將結(jié)果輸出給最終用戶。5.2主要算法5.2.1 用戶點(diǎn)擊日志的表示用戶點(diǎn)擊日志就是用戶所點(diǎn)擊的文件條目item。由前面的對文件檢索的建模，我們知道可以表示為：item = name, ext, size, date, site, path我們將其改寫為如下格式：pathsitedatesizeextnamexxxxxx有時候?yàn)榱撕啽?，我們也會表述為如下形式?30654321xxxxxx對于查詢串 q，價格共有 n 個記錄，因此我們得到如下的矩陣：1,11,21,31,41,51,6,1,2,3,4,5,6,1,2,3,4,5,6.iiiiiinnnnnnxxxxxxxxxxxxxxxxxx5.2.2 計(jì)算文件條目之間的距離不論是進(jìn)行聚類處理還是進(jìn)行分類處理，都需要進(jìn)行大量的對兩個文件條目(item)之間的距離 d 的計(jì)算。或者說，需要通過上文中的二模矩陣，得到下面的表示條目之間距離的單模矩陣：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).( ,dddddddddddddddddddddd nd nd nd nd nd nd n n1)0圖中我們用 d(i,j)表示項(xiàng) xi和 xj之間的距離，有 d(i,j)0。當(dāng) d(i,j)=0 時表示二者完全相同；當(dāng) d(i,j)0 時表示二者不同，并且 d 的值越大表示文件條目 xi和 xj之間的差異越大。對于條目 i 和 j 之間距離的 d(i,j)的計(jì)算，我們采用如下加權(quán)公式： 31(,)11( ,)ifjfpxxffpfdfd x xijf由前文文件檢索模型可知，此處 p=6。我們分別計(jì)算文件條目 i 和 j 的 6 項(xiàng)對應(yīng)屬性的距離，再進(jìn)行加權(quán)求和最后再進(jìn)行標(biāo)準(zhǔn)化處理。由于文件條目的 6 項(xiàng)屬性的數(shù)據(jù)類型和含義不完全相同，因此具體的計(jì)算方法區(qū)別較大，在計(jì)算時需要分別考慮。下圖為各個屬性的數(shù)據(jù)類型和計(jì)算方法。表格 5-1 文件條目各個屬性數(shù)據(jù)類型屬屬性性數(shù)數(shù)據(jù)據(jù)類類型型距距離離計(jì)計(jì)算算方方法法nameStringMinimal edit distanceextStringNominal VariablessizeIntegerInterval-scaled variablesdateIntegerInterval-scaled variablessiteStringN/ApathStringSubsection string具體方法為：5.2.2.1name 屬性距離的計(jì)算方法name 表示文件的不包含擴(kuò)展名的主名的名稱，數(shù)據(jù)類型為字符串型。對于這種字符串類型數(shù)據(jù)的處理，一般情況下可以按照文檔的相似度的方式進(jìn)行。但由于文件名通常都比較短小，命名多數(shù)情況下也不規(guī)范。這里并不建議按照文檔的形式來處理。我們這里采用的處理方法是按照最小編輯距離的方法來處理。編輯距離是指兩個字符串通過插入字符、刪除字符、改寫字符而變?yōu)橄嗤址枰牟僮鞔螖?shù)。比如：d(“abc”,”abd”) = 1d(“abc”,”ab”) = 1d(“abc”, “abcdf”) = 2d(“serverU”,” ser-u”) = 4利用動態(tài)規(guī)劃的方法計(jì)算編輯距離，時間復(fù)雜性可以達(dá)到O(n2)，空間復(fù)雜性 32為 O（n2）。計(jì)算方法為一個遞歸算法：d(, ) = 0d(s, ) = d(, s) = |s| （|s|表示 s 的長度）d(s1+ch1, s2+ch2) = min( d(s1, s2) + （if ch1=ch2 then 0 else 1）, d(s1+ch1, s2) + 1, d(s1, s2+ch2) + 1 )5.2.2.2ext 屬性距離的計(jì)算方法ext 指文件的擴(kuò)展名，雖然數(shù)據(jù)類型為字符串，但因此常見的文件類型是有限的，因此可以看成是枚舉類型，在聚類算法中則稱為標(biāo)稱變量。在進(jìn)行距離計(jì)算時可以按照聚類算法中對于此類數(shù)據(jù)類型的標(biāo)準(zhǔn)處理方法進(jìn)行處理，即其距離只是一個二值函數(shù)：取值相同則距離為 0；否則距離為 1。但考慮到文件擴(kuò)展名是有實(shí)際含義的，而且很多時候這些不同的擴(kuò)展名之間還有著豐富的聯(lián)系，因此我們能夠?qū)⑵涮幚淼母泳_。一般的，我們可以按照文件的擴(kuò)展名對文件類型進(jìn)行分類。比如可以將文件分成：程序、圖片、音樂、影視、源碼等類別。在每個類別內(nèi)部，可能又有更深的層次，比如源碼可能又分為 C/C+源碼，JAVA 源碼等，而 C/C+源碼又可以進(jìn)一步分為頭文件和實(shí)現(xiàn)文件等 這樣就形成了一棵樹。不過要注意的是，這棵樹不是平衡的，某些葉節(jié)點(diǎn)可能比較深，另外一些可能比較淺。為了形成這棵樹，我們還需要說明如下。首先，我們假設(shè)每種擴(kuò)展名只對應(yīng)于樹中的一個節(jié)點(diǎn)；其次，我們設(shè)置一個根節(jié)點(diǎn)，根節(jié)點(diǎn)本身不包含如何任何文件類型；再有，對于沒有擴(kuò)展名的文件，我們?yōu)槠滟x予一個特殊的值，并且直接位于根節(jié)點(diǎn)之下；對于不能識別的擴(kuò)展名我們也做同樣處理。這樣，最后形成了一棵類似下圖的樹： 33rootprogramvideomusicpicturesourceotherReal format.avi.rm.rmvbC/C+ language.java.himplementation.c.cpp圖 5-2 文件擴(kuò)展名屬性距離計(jì)算這樣，計(jì)算任意兩個文件條目類型屬性的距離演變成了計(jì)算樹中任意兩個葉節(jié)點(diǎn)之間的關(guān)系。對于樹中任意兩個葉節(jié)點(diǎn)的距離，則表示為其相似程度的倒數(shù)。而相似程度的計(jì)算，可以按照如下算法。樹中每個節(jié)點(diǎn)均存在一條從根節(jié)點(diǎn)到達(dá)它所在位置的唯一路徑 P。兩個節(jié)點(diǎn)的相似程度可以表示為它們各自路徑P 中公共節(jié)點(diǎn)的個數(shù)的函數(shù)。在實(shí)現(xiàn)上，我們選取如下的函數(shù)：假設(shè)需要計(jì)算兩個 ext 值分別為 e1 和 e2 的點(diǎn) xi、xj在此屬性上的距離。設(shè)e1 對應(yīng)的路徑為 p1，e2 對應(yīng)的路徑為 p2。p1 和 p2 的公共節(jié)點(diǎn)個數(shù)為 k（根節(jié)點(diǎn)除外），則我們?nèi)。?,2,211(,)2ijkdxx 345.2.2.3size 屬性距離的計(jì)算方法size 屬性表示文件條目的文件大小，以字節(jié)為單位，數(shù)據(jù)類型為整數(shù)。由于文件大小的取值范圍跨度很大，一般能夠從幾十字節(jié)到幾十億字節(jié)，因此不適合按照一般區(qū)間標(biāo)度變量的方法來計(jì)算，可以按照比例標(biāo)度型變量來處理。首先對size的值取對數(shù)：,3,3log()iiyx不過在實(shí)際應(yīng)用中要注意的是，因?yàn)閟ize 的取值范圍是非負(fù)整數(shù)，可能取0，因此不能直接取 log，可以考慮首先將 x1 再取 log。,3,3log(1)iiyx然后將 yi3轉(zhuǎn)化為對應(yīng)的 z-score 值 Zi3,33,33iiymz s其中.)31,32,3,31nm (yyyn31,332,33331(| | . |)nsymymymn 進(jìn)行標(biāo)準(zhǔn)化處理之后，再求二者之差： 3,3,3,3,3(,)ijijdxxzz5.2.2.4date 屬性距離的計(jì)算方法date 屬性表示文件的最后修改日期，前面已經(jīng)說過，我們將原來的字符串格式統(tǒng)一轉(zhuǎn)化為整數(shù)，比如按照距離公元元年元旦的日期數(shù)。對于整數(shù)，屬于區(qū)間標(biāo)度變量。為了更好的計(jì)算各個項(xiàng)目該屬性之間的距離，我們并不直接計(jì)算各個條目的差，而是先對其進(jìn)行標(biāo)準(zhǔn)化處理。將Xi4轉(zhuǎn)化為對應(yīng)的 z-score 值 Zi4,44,44iixmz s 35其中.)41,42,4,41nm (xxxn41,442,44,441(| | . |)nsxmxmxmn 進(jìn)行標(biāo)準(zhǔn)化處理之后，再求二者之差：444,4,4(,)ijijdxxzz5.2.2.5site 屬性距離的計(jì)算方法由于在實(shí)際文件共享系統(tǒng)中， site 值最常見的情況就是 IP 地址，而兩個 IP 地址之間的距離的比較是沒有實(shí)際意義的，因此我們忽略兩個site 屬性的之間的距離，或者可以表示為：5,5,5(,)0ijdxx5.2.2.6path 屬性距離的計(jì)算方法path 表示文件從根目錄開始到其節(jié)點(diǎn)所經(jīng)過的路徑。其重要特點(diǎn)就是路徑是分段的，是由多個字符串連接而成的。比如路徑： /Resource/Software/Tools/network/可以看成是由分段的子字符串 Resource，Software，Tools 和 network 構(gòu)成的。在對 path 進(jìn)行比較的時候，我們將每個路徑拆分成多個子字符串，然后比較其中公共子字符串的個數(shù)占全部子字符串的比例。6,6,6(,)comijijsdxxss公式中 si和 sj分別表示 xi和 xj的 path 屬性的分段的個數(shù)， Scom為公共子字符串的個數(shù)。5.2.3 對用戶點(diǎn)擊記錄進(jìn)行聚類在本體系中需要對用戶的點(diǎn)擊日志進(jìn)行聚類，以便能夠得到這k 個不同的用戶查詢意圖。聚類常用的方法有 Partitioning 方法，Hierarchical 方法和 Density-based 方法。根據(jù)我們的具體情況，這里選用自底向上的Hierarchical 方法。 36對本方法的圖示說明如下： abcdea,bstep 0 step 1 step 2 step 3 step 4d,ec,d,ea,b,c,d,eagglomerative(AGNES)圖 5-3 聚類示意圖假設(shè)共有 5 個對象 a,b,c,d,e，我們將其根據(jù)彼此的相關(guān)程度進(jìn)行聚類。首先，將每個待聚類的元素獨(dú)立劃分為一 個自己的類別，如果有 n 個元素，則開始時共有 n 類。然后將距離最近的兩個元素歸為一類，此時有n-1 類；此后再將距離次近的歸為一類，類別共 n-2 類；如此不斷重復(fù) 如果沒有結(jié)束標(biāo)志，則最終將會把所有類別都?xì)w為一類。所以必須要設(shè)置結(jié)束標(biāo)志。這其中有幾點(diǎn)要說明：5.2.3.1結(jié)束標(biāo)志的設(shè)定結(jié)束標(biāo)志可以從幾個方面來綜合考慮。首先是距離因素，設(shè)定當(dāng)距離最近的兩個類的距離大于某個類別間的距離閥值D 時不再進(jìn)行合并操作，設(shè)置距離標(biāo)志D可以防止最后生成的類別過少。另外由規(guī)律2 可知相同的查詢串通常只表示很少的查詢意圖，因此可以設(shè)定一個最大類別數(shù)G，這個表示可以防止最后生成的類別數(shù)過多。通過這兩個結(jié)束標(biāo)志的綜合運(yùn)用，可以使最終的類別數(shù)量控制在較理想的范圍中。5.2.3.2具有多個元素的類別之間距離的計(jì)算當(dāng)類別包含多個元素時，計(jì)算它們之間的距離有三種不同的方法：計(jì)算距離最近的兩點(diǎn)之間的距離、最遠(yuǎn)的兩點(diǎn)之間的距離、或者用中心點(diǎn)來計(jì)算距離。我們這里選用中心點(diǎn)來計(jì)算二者的距離。這個中心點(diǎn)可能是類別中真實(shí)存在的一個元素， 37但也可能是一個并不真正包含的虛擬的元素。5.2.3.3孤立點(diǎn)的處理事實(shí)上，一些查詢串可能會對應(yīng)一兩個或很少的孤立查詢記錄，這些查詢記錄和其余大量的查詢記錄的相似度很低。通過人工查看的方法，我們發(fā)現(xiàn)很多這些孤立查詢記錄其實(shí)都是看上去不太正常的記錄，比如對于一些大小為0 的文件進(jìn)行下載，或者下載一些快捷方式文件等。我們認(rèn)為這些孤立點(diǎn)是因?yàn)橛脩舨恍⌒幕虿涣私馑?。而這些文件條目實(shí)際上并不應(yīng)該被下載，而應(yīng)該被拋棄。因此我們需要對這些孤立點(diǎn)進(jìn)行丟棄。5.2.3.4訓(xùn)練集的生成由于在進(jìn)行完聚類后我們會對查詢再進(jìn)行分類，因此我們考慮利用聚類中的文件條目作為分類時的訓(xùn)練集。在聚類完成后我們將保留每個查詢串的每個類別足夠的文件條目。5.2.4 對查詢結(jié)果集合進(jìn)行分類常用的分類算法有 k nearest neighbor(kNN), Nave Bayes, 還有 support vector machines 等。我們采用 kNN 算法。其具體步驟為：首先需要有一個訓(xùn)練集。對于每個可能的類別，各自有一些屬于該類別的對象。給定一個待分類的對象，系統(tǒng)在訓(xùn)練集中查找與其最相似的k 個對象(稱為鄰居)，并根據(jù)這些鄰居所屬的類別情況來給該對象的候選類別評分，最后按照分值來確定待分類對象的類別。 38第6章 系統(tǒng)實(shí)現(xiàn)與評測6.1系統(tǒng)設(shè)計(jì)體系結(jié)構(gòu)圖實(shí)際系統(tǒng)的體系結(jié)構(gòu)圖如下。考慮到一些實(shí)現(xiàn)問題，和上一章的系統(tǒng)模型略有區(qū)別。 Index Part Clustering Part Collection Part ClickLog DataBase Training Set DataBase ClickLog Server Clustering Query q Normal Index System Items Categorization Filter Categories Click log Items Training set Click log 圖 6-1 體系結(jié)構(gòu)圖下面我們來詳細(xì)介紹此系統(tǒng)設(shè)計(jì)。6.1.1 用戶行為收集部分Collection Part 部分為用戶點(diǎn)擊記錄收集部分，是實(shí)時運(yùn)行的。在用戶進(jìn)行查詢后，文件檢索系統(tǒng)返回包含查詢串的結(jié)果。用戶從中選取自己認(rèn)為正確的文件條目。用戶的選取操作就是一次鼠標(biāo)的點(diǎn)擊操作。這個點(diǎn)擊動作自動觸發(fā)到我們的后臺 CGI 程序，程序先將用戶的下載請求轉(zhuǎn)向到真正的下載地址，后臺再發(fā)送一個記錄點(diǎn)擊操作的服務(wù)請求。該服務(wù)請求由ClickLog Server 接收，并記錄到 ClickLog Database 中。我們稱用戶的每次點(diǎn)擊對應(yīng)的文件條目為 39ClickLog。經(jīng)過這樣反復(fù)多次后， ClickLog Database 中記錄了大量的 ClickLog，每個 ClickLog 包含一個查詢串和對應(yīng)的文件條目item。6.1.2 聚類部分此部分為聚類操作部分，每隔一段時間運(yùn)行一次。在實(shí)際系統(tǒng)中可以根據(jù)用戶數(shù)量來設(shè)定為每小時或每天一次。這部分首先從 ClickLog Database 中讀取全部的 ClickLog 條目，然后對每個查詢串依次進(jìn)行處理。取出每個查詢串對應(yīng)的ClickLog 記錄，進(jìn)行聚類，聚類后得到 k 個類別。如前文所述，其中可能存在一些孤立點(diǎn)，然后按照標(biāo)準(zhǔn)對這些孤立點(diǎn)進(jìn)行考察，需要的話要拋棄掉其對應(yīng)的孤立類別。聚類操作完成后，將聚類的結(jié)果存入Training Set Database 中。至此，我們就得到了實(shí)現(xiàn)免用戶干預(yù)的、基于反饋信息的檢索系統(tǒng)所需要的反饋數(shù)據(jù)。6.1.3 索引部分完成了上面兩個部分的工作，就可以進(jìn)行真正的反饋了。對于用戶的查詢串q，首先使用常規(guī)檢索系統(tǒng)進(jìn)行檢索，就可得到一個文件條目Item 的集合。然后在 Training Set Database 中取出對應(yīng)于查詢串 q 的 k 個類別的訓(xùn)練集。利用這些訓(xùn)練集條目為剛剛通過常規(guī)查詢得到的Item 集合進(jìn)行分類。此處我們限定每個文件條目至多屬于 1 個類別。分類后可能得到 k+1 個類別（某些 Item 可能不屬于任何類別），以及每個條目和其所屬類別的相似程度。利用分類的類別和相似度，系統(tǒng)可以重新根據(jù)此信息進(jìn)行輸出。對于那些不屬于任何類別的文件條目，通常也是用戶所不太關(guān)心的結(jié)果，可以選擇拋棄或排在結(jié)果頁面的最后。6.2其它實(shí)現(xiàn)中的問題6.2.1 記錄用戶對查詢結(jié)果的選取對于用戶對查詢結(jié)果的選取的記錄，一般有兩種方法，采用client 端技術(shù)和server 端技術(shù)。為了方便用戶的使用，不改變用戶的任何使用習(xí)慣，我們采取server 端技術(shù)來記錄用戶的選擇，這樣用戶在使用時就不需要絲毫的改變，而我們也能夠得到足夠的記錄信息。 40具體說來，傳統(tǒng)網(wǎng)頁上的鏈接一般如下：qqtail.sln我們采用 javascript 技術(shù)將其進(jìn)行改造，改造后的形式如下：QQTail.sln注意其中有 2 處 javascript 腳本。第一處是 onClick 信息，當(dāng)用戶點(diǎn)擊了該鏈接時，自動重新轉(zhuǎn)向到了我們的服務(wù)器上，服務(wù)器有一個接收該請求的CGI 程序clicklog，這個程序自動轉(zhuǎn)向到實(shí)際的 FTP 下載地址，然后向 ClickLog Server 發(fā)送一個記錄請求， ClickLog Server 就記錄下整個查詢串和文件條目信息。腳本中的另一處是 onMouseOver，這個是為了處理當(dāng)用戶已經(jīng)點(diǎn)擊該鏈接后卻又突然想復(fù)制該鏈接而使用的。只所以在此處使用了 javascript 而不是直接改變鏈接地址，是為了便于那些并不希望通過直接點(diǎn)擊，而是希望使用下載工具或想復(fù)制下載地址的用戶的方便。通過現(xiàn)在這種改造，用戶看到的頁面和鏈接地址都是和原始信息是完全一致的。6.2.2 文件類型屬性距離計(jì)算方法的實(shí)現(xiàn)前面談到對于常見的文件擴(kuò)展名，我們將其各自賦予一個屬性值，屬性值代表了在文件類別樹中從根結(jié)點(diǎn)到該文件類型所在節(jié)點(diǎn)的所有節(jié)點(diǎn)編號的集合。節(jié)點(diǎn)的編號示例如下圖所示，每個節(jié)點(diǎn)的子節(jié)點(diǎn)的編號都是從1 開始的，并沒有全局性的編號。 41root1234561212121212圖 6-2 ext 屬性距離計(jì)算方法的實(shí)現(xiàn)比如對應(yīng)圖中左下角的灰色節(jié)點(diǎn)來說，對應(yīng)的路徑為2.1.1；右下角的灰色節(jié)點(diǎn)對應(yīng)的路徑則為 5.1.2.2。這樣，如果比較兩個節(jié)點(diǎn)的相似度，我們只需計(jì)數(shù)它們的路徑中相同的節(jié)點(diǎn)個數(shù)即可。比如路徑為 2.1.1 的節(jié)點(diǎn)和 2.2 的節(jié)點(diǎn)，它們的路徑中有一個相同的節(jié)點(diǎn)2，或者說相似度為 1 層；路徑為 2.1.1 的節(jié)點(diǎn)和 2.1.2 的節(jié)點(diǎn)，它們的相似度為2 層；路徑為 5.3 的節(jié)點(diǎn)和路徑為 7 的節(jié)點(diǎn)相似度則為 0。具體文件類型分類列表見附錄 1。配置文件格式，擴(kuò)展名分類文件的配置文件的格式舉例如下：111mp3|wav|wma|112midi|mid|文件說明： 42作用：通過讀取文件得到每個擴(kuò)展名對應(yīng)的路徑。文件格式：每 3 行為一個記錄。每個記錄中第一行是空行；第2 行是路徑，格式為每層節(jié)點(diǎn)編號用制表符分割；第3 行是擴(kuò)展名列表，每個擴(kuò)展名都以豎線“|”結(jié)束。距離計(jì)算方法的實(shí)現(xiàn)：在系統(tǒng)實(shí)現(xiàn)時，定義了一個 ExtVector 類，它代表了一個具體的節(jié)點(diǎn)路徑，ExtVector 繼承自 vector，這里的 vector 是標(biāo)準(zhǔn) STL 的 vector，并且實(shí)現(xiàn)了如下方法來計(jì)算兩個路徑之間的距離：double operator (const ExtVector& e1, const ExtVector& e2); 6.3系統(tǒng)的評測環(huán)境我們采用天網(wǎng)千帆文件搜索引擎為測試系統(tǒng)。天網(wǎng)千帆文件搜索引擎為北京大學(xué)網(wǎng)絡(luò)實(shí)驗(yàn)室開發(fā)的一個 FTP 文件搜索引擎，有較大的用戶訪問量。在2005 年4 月，我們先后運(yùn)行了普通文件搜索引擎和我們設(shè)計(jì)的新型文件搜索引擎，并記錄了用戶的查詢記錄和用戶對查詢結(jié)果的選取信息。為了保證評測效果的準(zhǔn)確性，在使用了新系統(tǒng)后，我們沒有通知任何用戶，也沒有改變?nèi)魏斡脩艚缑?，使測試盡量在用戶不知情的情況下進(jìn)行。對于分類后不能歸入任何類別的文件條目，為了保證總體查詢結(jié)果數(shù)量不變，我們也沒有進(jìn)行拋棄，而是放在排序的最后返回給用戶。這里采用的排序方法是在頁內(nèi)按照各個初始結(jié)果集合 S0中各個條目距離其類別的距離遠(yuǎn)近進(jìn)行排序，對不同的類別之間并不進(jìn)行排序。在結(jié)果的表現(xiàn)形式上與普通搜索引擎無異。比較試驗(yàn)共進(jìn)行了 8 天，其中 4 天為普通文件檢索系統(tǒng)，另外 4 天則為我們的新系統(tǒng)。我們分別比較了用戶對前2 頁查詢結(jié)果頁面中點(diǎn)擊的文件條目在該頁面中的排序的情況，共取得了 8 組比較數(shù)據(jù)。6.4評測結(jié)果具體比較結(jié)果參見下圖。圖中橫坐標(biāo)表示8 組比較數(shù)據(jù)，縱坐標(biāo)為各組試驗(yàn)數(shù)據(jù)的在頁面中點(diǎn)擊的條目的排序的平均值。圖中上部的曲線（虛線）為普通文件檢索系統(tǒng)的結(jié)果，下面的曲線（實(shí)線）為新系統(tǒng)的試驗(yàn)結(jié)果。 43圖 6-3 系統(tǒng)試驗(yàn)效果比較從圖中可以明顯的看到：在新系統(tǒng)下，用戶所點(diǎn)擊的文件條目在頁面中的排序比普通系統(tǒng)有了較大幅度的提前。在我們的試驗(yàn)系統(tǒng)中，普通文件檢索系統(tǒng)用戶點(diǎn)擊的條目在頁面中的排名為13.70，而使用了新系統(tǒng)后，點(diǎn)擊條目的平均排名為8.93。排名前進(jìn)了 13.70-8.93=4.77 名。檢索效果有了較大幅度的改進(jìn)。由此可驗(yàn)證本文所述新型文件檢索系統(tǒng)的正確性。 44第7章 總結(jié)與展望7.1總結(jié)作者在本文中首先對文件檢索系統(tǒng)進(jìn)行了一些基礎(chǔ)性的研究工作，提出了文件檢索系統(tǒng)的檢索模型，并提出了評測的指標(biāo)。然后在對用戶使用文件檢索系統(tǒng)的行為和習(xí)慣進(jìn)行記錄的基礎(chǔ)上，發(fā)現(xiàn)了用戶行為習(xí)慣中的兩個重要規(guī)律。利用這兩個規(guī)律，作者提出了一個免用戶干預(yù)的、基于用戶查詢記錄的新型文件檢索模型，該模型可以有效的提高文件檢索系統(tǒng)的精度。最后作者實(shí)現(xiàn)了一個真實(shí)的系統(tǒng)并利用該系統(tǒng)對本模型的有效性進(jìn)行了驗(yàn)證。7.2展望由于研發(fā)時間倉促，系統(tǒng)的有些功能還沒有來得急加入，有的地方還有待加強(qiáng)，特別如下文所述的幾處。7.2.1 目錄本文的全部算法都沒有考慮目錄的特殊性，而在實(shí)際的FTP 系統(tǒng)中是存在目錄共享的。在本文提到的試驗(yàn)系統(tǒng)中，對目錄是不加區(qū)分的看成文件來處理，這樣在處理效果上就不是很理想了。目錄和文件的區(qū)別主要表現(xiàn)在這幾個方面：首先，目錄不存在擴(kuò)展名屬性 ext，這樣造成了無法利用這個屬性來進(jìn)行判斷，而 ext 屬性在距離計(jì)算中又是非常重要的一個因素。其次，目錄的大小 filesize 往往比較大。因?yàn)槟夸浭怯脕砣菁{文件的，因此目錄的大小必然比其內(nèi)部的任何文件都要大。這樣，就不能直接將目錄和文件的大小進(jìn)行相似度計(jì)算。7.2.2 壓縮文件類型壓縮文件，比如我們通常見到的 zip 文件，rar 文件等。是一種特殊形式的文件。如文中我們所言，文件的擴(kuò)展名常常表示文件的類型，比如是圖片文件、音樂 45文件、視頻文件等。而壓縮文件本身是為了節(jié)省存儲空間而通過對其它文件進(jìn)行壓縮而生成的。此類文件的意義在于其所壓縮的文件，而本身的文件類型是沒有意義的。這樣就造成了文件類型屬性 ext 判斷的失效。在另一個屬性上，文件大小，對于壓縮文件也是意義不明顯的。因?yàn)閴嚎s方式的區(qū)別，造成壓縮比例的差異，同樣大小的原始文件，可能壓縮為不同大小的壓縮文件；壓縮后同樣大小的文件，其原始文件可能也是不同的。因此直接用文件大小這個屬性來比較壓縮文件也是不準(zhǔn)確的。如上這些特性，造成了壓縮文件不適于按照一般的文件類型來進(jìn)行比較，應(yīng)該進(jìn)行專門的處理。 46參考資料Ruthven, et al., 2003 I. Ruthven and M. Lalmas, A survey on the use of relevance feedback for information access, Knowledge Engineering Review. Vol 18. Issue 2. pp 95-145. 2003.Chang, et al., 1996 Chen-Chuan K. Chang, Hctor Garca-Molina, and Andreas Paepcke. Boolean Query Mapping Across Heterogeneous Information Sources. IEEE Transactions on Knowledge and Data Engineering, 8(4): 515-521, Aug, 1996.Zhang and Dong, 2002 Dell Zhang, Yisheng Dong. A novel Web usage mining approach for search engines, computer networks, 2002, vol.39: 303-310.Allison, 1999 Allison, L. Dynamic programming algorithm (DPA) for edit distance, In Algorithms and Data Structures Research & Reference Material. School of Computer Science and Software Engineering, Monash University, Australia 3168. 1999Beeferman, et al., 2000 D. Beeferman, A. Berger, Agglomerative clustering of a search engine query log, in: Proceedings of ACM KDD, 2000, Boston, MA, USA.Salton, et al, 1983 G. Salton, M. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, New York, 1983.Lewis, 1995 D. D. Lewis. Evaluating and optimizing autonomous text classification systems. In Proceedings of SIGIR-95, 18th ACM International Conference on Research and Development in Information Retrieval, pages 246254, Seattle, US, 1995.Ripeanu, 2001 M. Ripeanu, peer-to-peer Architecture Case Study: Gnutella, Network, University of Chicago Technical Report TR-2001-26.RFC 959 RFC 959, File Transfer Protocol (FTP)陳華等，2003 陳華，李曉明，高級文件搜索引擎核心功能的實(shí)現(xiàn)技術(shù)，全國搜索引 47擎與 Web 挖掘進(jìn)展會議，2003.3 15-27天網(wǎng) 天網(wǎng)千帆文件搜索引擎 http:/天網(wǎng) maze 天網(wǎng) maze 文件共享系統(tǒng) http:/王建勇等, 2001 王建勇、單松巍、雷鳴、謝正茂、李曉明，海量 web 搜索引擎系統(tǒng)中用戶行為的分布特征及其啟示， 中國科學(xué)E 輯，2001 年 8 月，第 31 卷，第四期，372-384 頁陳華等,2004 陳華，王繼民，韓近強(qiáng)，謝欣，互聯(lián)網(wǎng)上 FTP 文件的分布特征及啟示，計(jì)算機(jī)工程與應(yīng)用 ， 2004 年第 40 卷，129-133 48附錄：文件類型列表 音頻文件： 1常用：1.1 聲音記錄 1.1.1mp3|wav| wma| 音階 1.1.2midi| mid|cda| mp1|m3u|mjf|voc|xm|s3m|stm|mod|dsm|far|ult|mtm|mp2|mpa|669|aac|mp4|vqf|pls|xpl|lrc|rmi|snd|aif|wax|rms|aiff|aifc|mpga| 視頻文件 2電影常用格式 2.1 real 格式 2.1.1rmvb| rm| 高清晰 2.1.2avi|短篇格式 2.2 mpg| mpeg| asf| wmv| mpe| dat| asx|mkv|字幕 2.3 vob|ram|rmm|rmj|wvx|m1v|wmp|ivf|smi|mpv|ssm|mpv2|mp2v|smil|rv|rp|rf|rt| 49wm|ra|kbk|la1|lar|lavs|lmsff| 圖形文件 3web 常用格式 3.1 jpg|bmp|gif| png| jpe|矢量 3.2 wmf|pcx|tif|psd|tga|pic|pcd|dib|rle|iff|lbm|jif|dcx|ico|tiff|ilbm| 代碼文件 4C/C+ 4.1 c|h| cpp|hpp|JAVA 4.2 java|class|PASIC 4.3 pas|BASIC 4.4 bas|匯編 4.5 asm|perl 4.6 perl|js|inc|cxx|tli|tlh|hxx|inl|def|odl|idl|py| 壓縮文件 5常用格式 5.1 rar|zip|linux 壓縮格式 5.2 gz|tar|tgz|b64| gz| z|arj|cab| arc| bhx|hqx|lzh|mim|taz|uue|xxe|tz|uu| 網(wǎng)頁文件 6靜態(tài) 6.1 htm|html|shtml|動態(tài) 6.2 50 php|asp| php3|jsp|web 程序 6.3 htw|htx|css|url| 程序相關(guān)文件 7可執(zhí)行文件 7.1 windows 程序 7.1.1exe|msi| Dos 文件 7.1.2com|bat| unix 程序 7.1.3out|系統(tǒng)文件 7.2 ocx|dll|drv| 文本文件 8txt|asa|wri|log|scp| 系統(tǒng)配置文件 9配置文件 9.1 ini|inf|conf|注冊表文件 9.2 reg| office 文檔 10Word 文擋 10.1 doc|rtf|wbk|Excel 文檔 10.2 xls|xlb|xlc|PowerPoint 文檔 10.3 ppt| 幫助文檔 11hlp| Flash 文檔 12swf|fla| Acrobat 文檔 13pdf|pdx|apf|fdf|rmf|xfdf| Caj 文檔 14caj|kdh|其它不可識別格式 51致謝首先要向我的導(dǎo)師 表示衷心的感謝，感謝他在我三年的碩士生階段和本論文的完成工作中對我的精心指導(dǎo)和諄諄教誨，他踏實(shí)的治學(xué)態(tài)度和嚴(yán)謹(jǐn)?shù)墓ぷ髯黠L(fēng)使我受益匪淺，他淵博的知識和對事業(yè)無止境的追求使我感受至深，他對我的嚴(yán)格要求將對我以后的工作學(xué)習(xí)產(chǎn)生巨大的影響，使我終生受益，我以作為他的學(xué)生而自豪。感謝我的父母，他們在我的成長過程中傾注了極大的心血，他們對我的言傳身教和嚴(yán)格要求，將是我這一生中最寶貴的財(cái)富。要感謝我的同學(xué)，他們對我的論文寫作起了非常大的幫助作用，曾經(jīng)多次幫助過我。 還要感謝我的女友，在我的生活和工作中，給予了我莫大的支持和鼓勵。最后，深深感謝每一位關(guān)心我的朋友和老師，感謝你們在我成長道路上對我的幫助。 52北京大學(xué)學(xué)位論文原創(chuàng)性聲明和使用授權(quán)說明北京大學(xué)學(xué)位論文原創(chuàng)性聲明和使用授權(quán)說明原創(chuàng)性聲明原創(chuàng)性聲明本人鄭重聲明： 所呈交的學(xué)位論文，是本人在導(dǎo)師的指導(dǎo)下，獨(dú)立進(jìn)行研究工作所取得的成果。除文中已經(jīng)注明引用的內(nèi)容外，本論文不含任何其他個人或集體已經(jīng)發(fā)表或撰寫過的作品或成果。對本文的研究做出重要貢獻(xiàn)的個人和集體，均已在文中以明確方式標(biāo)明。本聲明的法律結(jié)果由本人承擔(dān)。論文作者簽名： 日期： 年 月 日學(xué)位論文使用授權(quán)說明學(xué)位論文使用授權(quán)說明本人完全了解北京大學(xué)關(guān)于收集、保存、使用學(xué)位論文的規(guī)定，即：按照學(xué)校要求提交學(xué)位論文的印刷本和電子版本；學(xué)校有權(quán)保存學(xué)位論文的印刷本和電子版，并提供目錄檢索與閱覽服務(wù)；學(xué)?？梢圆捎糜坝　⒖s印、數(shù)字化或其它復(fù)制手段保存論文；在不以贏利為目的的前提下，學(xué)?？梢怨颊撐牡牟糠只蛉績?nèi)容。（保密論文在解密后遵守此規(guī)定）論文作者簽名： 導(dǎo)師簽名： 日期： 年 月 日