Web搜索結(jié)果自動(dòng)歸類系統(tǒng)-畢業(yè)論文

Web搜索結(jié)果自動(dòng)歸類系統(tǒng)摘要隨著因特網(wǎng)上信息資源的爆炸性增長(zhǎng)，搜索引擎已經(jīng)成為了目前網(wǎng)絡(luò)上最重要的信息檢索工具。但很顯然，人們對(duì)目前的搜索引擎還有很多不滿之處。對(duì)于用戶提交的檢索要求，現(xiàn)有的搜索引擎（如Google, Yahoo, MSN, 百度）通常計(jì)算網(wǎng)頁(yè)相關(guān)性后返回給用戶一長(zhǎng)串結(jié)果列表。由于搜索結(jié)果中各種檢索主題是混和在一起的，用戶需要在大量的搜索結(jié)果中尋找所需要的信息，而且用戶很難對(duì)搜索結(jié)果進(jìn)行控制。要解決這些問題，一種組織和控制搜索結(jié)果的有效方法是必要的。如果在搜索引擎中采用聚類技術(shù)對(duì)搜索結(jié)果進(jìn)行聚類處理，經(jīng)過聚類處理的搜索結(jié)果以類目的形式呈現(xiàn)，主題相似的搜索結(jié)果被劃分為一個(gè)類目，類目之間同時(shí)又具有包含關(guān)系。這樣，用戶可以快速了解搜索結(jié)果的整體分布情況，并快速定位自己需要的搜索結(jié)果。在研究搜索引擎原理和聚類算法的基礎(chǔ)上，本文對(duì)聚類搜索引擎的體系結(jié)構(gòu)，以及應(yīng)用于網(wǎng)頁(yè)聚類的Lingo聚類算法進(jìn)行了詳細(xì)探討。并基于開源聚類搜索引擎Carrot22的框架，實(shí)現(xiàn)了適用于中文領(lǐng)域的Web搜索結(jié)果自動(dòng)歸類系統(tǒng)。首先，在本系統(tǒng)的框架設(shè)計(jì)上，充分考慮到中文環(huán)境的特殊性，由此在接口設(shè)計(jì)和可擴(kuò)展性設(shè)計(jì)上，做了十分有意義的工作。其次，本文實(shí)現(xiàn)了描述優(yōu)先的聚類算法Lingo，系統(tǒng)聚類結(jié)果的可讀性和可理解性都得到大大提高。最后，通過比較說明，采用描述優(yōu)先的聚類算法對(duì)提高標(biāo)簽可理解性的優(yōu)勢(shì)。關(guān)鍵詞：聚類算法，搜索引擎，Carrot2, Lingo算法IVAn Automatic Categorization System for Clustering Web Search ResultsAbstractWith the exploding expand of the information resources in Internet, search engines have become the most important tools for users when surfing in Internet. However, obviously, web users are not satisfactory with the present search engines.For each retrieval request by users, present search engines (such as Google, Yahoo, MSN and BaiDu) usually return a lot of search results by counting the relevance of web pages and the results are mixed with different subjects. Users have to look for what they actually need in a mass of search results without any direction. As well, its very hard for users to control the display of the search results. To solve these problems, an effective method to organize and control the search results is useful by applying clustering technology. With automatic clustering system, all the results are organized as several clusters, which are gathered by similarity of web pages. So, web users can quickly get to know the entire distribution of all the search results and orient themselves to the object rapidly.With a study on the search engine principle and the clustering algorithms, this thesis discussed the architecture of clustering search engine, and the Lingo(Label INduction Grouping algOrithm) algorithm. Based on the open source framework Carrot22 clustering search engine, we have implemented an automatic clustering system for web pages in Chinese. Firstly，as in the environment of Chinese, We consider a lot to design the system architecture to fit for it. Secondly, the thesis successfully implements the descriptive clustering algorithm which makes the result labels much more readable. Finally, the comparison shows that the priorities of descriptive clustering algorithm to enhance labeling understandability.Key words：Clustering algorithm, Search Engine, Carrot2, Lingo algorithm目 錄 第一章 緒論11.1研究背景11.2聚類搜索引擎的現(xiàn)狀31.3本文主要內(nèi)容41.4本文結(jié)構(gòu)安排5第二章 網(wǎng)頁(yè)自動(dòng)聚類技術(shù)62.1文檔預(yù)處理62.1.1預(yù)處理步驟62.1.2 中文分詞62.2向量空間模型（VSM）72.3描述優(yōu)先的聚類算法82.4 Lingo聚類算法102.4.1后綴數(shù)組（Suffix Arrays）102.4.2潛在語(yǔ)義索引（LSI）112.5小結(jié)12第三章 自動(dòng)歸類系統(tǒng)（ACS）框架設(shè)計(jì)133.1聚類搜索引擎概述133.2 ACS系統(tǒng)體系結(jié)構(gòu)描述133.2.1搜索引擎用戶界面143.2.2調(diào)度中心143.2.3數(shù)據(jù)獲取模塊143.2.4搜索結(jié)果重排序模塊153.2.5聚類分析模塊153.2.6聚類結(jié)果輸出模塊193.3系統(tǒng)開發(fā)工具和運(yùn)行環(huán)境193.4 小結(jié)19第四章 ACS系統(tǒng)開發(fā)與測(cè)試20III4.1 ACS系統(tǒng)設(shè)計(jì)概述204.2系統(tǒng)詳細(xì)設(shè)計(jì)224.2.1系統(tǒng)過程設(shè)計(jì)224.2.2系統(tǒng)流程設(shè)計(jì)224.2.3系統(tǒng)容錯(cuò)設(shè)計(jì)254.3系統(tǒng)的實(shí)現(xiàn)254.3.1本地接口層次274.3.2查詢處理鏈274.3.3系統(tǒng)的主要協(xié)調(diào)類284.3.4添加中文分詞294.4系統(tǒng)聚類結(jié)果評(píng)測(cè)324.5小結(jié)33第五章 總結(jié)與展望34參考文獻(xiàn)36致謝38ContentsChapter 1 Preface11.1 Background11.2 Research Status of Clustering Search Engine31.3Content of Thesis41.4 Outline of Thesis5Chapter 2 Clustering Technology for Web pages62.1 Web pages preprocessing62.1.1 Preprocessing62.1.2 Chinese tokenizer62.2 Vector Space Model72.3 Descriptive Clustering82.4 Lingo Clustering Algorithm102.4.1 Suffix Arrays102.4.2 Latent Semantic Indexing112.5 Conclusion12Chpater 3 System Architecture133.1 Search Results Clustering Engineering133.2 System Architecture133.2.1 Graphical User Interface143.2.2 Schedule Center143.2.3 Data Fetch Module143.2.4 Serch Results Resorting153.2.5 Clustering Module153.2.6 Output Module193.3 Developing Tools and Environment193.4 Conclusion19Chapter 4 Development and Evaluatation204.1 General Design204.2 Design Specification224.2.1 Architecture Design224.2.2 System Flow Design224.2.3 Error Control254.3 Implementation254.3.1 Local Interface274.3.2 Query Process Chain274.3.3 Main Classes284.3.4 Chinese Tokenizer294.4 Evaluatation324.5 Conclusion33Chpater 5 Summary and Envision34Bibliography36Acknowledgement38VI第一章 緒論第一章 緒論2007年1月23日，中國(guó)互聯(lián)網(wǎng)絡(luò)信息中心（CNNIC）發(fā)布了第19次中國(guó)互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告。根據(jù)報(bào)告，用戶經(jīng)常使用的網(wǎng)絡(luò)服務(wù)中搜索引擎占51.5%，名列三甲。網(wǎng)民主要使用互聯(lián)網(wǎng)的工具性功能，搜索信息與使用MSN等網(wǎng)上即時(shí)通訊成為網(wǎng)民花最多時(shí)間的網(wǎng)上活動(dòng)。搜索引擎現(xiàn)在已成為用戶利用因特網(wǎng)信息資源所不可缺少的工具1。但是現(xiàn)有的搜索引擎并不能很好的滿足用戶的需求。 1.1 研究背景對(duì)于用戶提交的檢索要求，現(xiàn)有的搜索引擎（如Google， Yahoo， MSN， 百度）通常是通過計(jì)算網(wǎng)頁(yè)相關(guān)性返回給用戶一長(zhǎng)串的結(jié)果列表。用戶需要在大量的搜索結(jié)果中尋找自己需要的信息，因?yàn)樗阉鹘Y(jié)果中各種檢索主題全部混和在一起。這往往給用戶帶來煩惱。例如：用戶在百度中輸入關(guān)鍵詞“引擎”，想了解汽車引擎方面的知識(shí)。在百度返回的44，600，000篇網(wǎng)頁(yè)信息中(查詢于07-05-17)，排在前列的內(nèi)容基本都是關(guān)于“搜索引擎”方面的知識(shí)。如果用戶足夠耐心，當(dāng)他查看排在第100位的網(wǎng)頁(yè)時(shí)，才會(huì)了解到有關(guān)“汽車引擎”的內(nèi)容。所以，在搜索引擎普遍采用相關(guān)度排序的今天，用戶將不得不在經(jīng)歷一系列無(wú)關(guān)網(wǎng)頁(yè)后才會(huì)獲取到自己想要的內(nèi)容。這種檢索方式顯然是存在缺陷的。圖1-13顯示了用戶對(duì)現(xiàn)有搜索引擎搜索結(jié)果的滿意程度。圖1-1 用戶對(duì)搜索引擎結(jié)果的困惑程度總得來說，傳統(tǒng)的獨(dú)立搜索引擎面臨著以下挑戰(zhàn)：（1） 返回的搜索結(jié)果數(shù)量太多。在很多情況下，用戶總要在紛雜的搜索結(jié)果中仔細(xì)尋找自己想要的搜索結(jié)果。（2） 用戶很難對(duì)搜索結(jié)果進(jìn)行控制，無(wú)法分類查看或限定搜索結(jié)果，只能更換關(guān)鍵詞重新搜索。（3） 所有的搜索結(jié)果都是線性排列，用戶只能逐行地從上往下瀏覽。無(wú)法迅速地獲得搜索結(jié)果之間的類別關(guān)系和重要程度。（4） 搜索結(jié)果是按照搜索引擎自身的相關(guān)性算法進(jìn)行排序。然而同一關(guān)鍵詞可能指代不同的語(yǔ)義，搜索引擎無(wú)法對(duì)這些不同的語(yǔ)義差別性地對(duì)待。 要解決這些問題，一種組織和控制搜索結(jié)果的有效方法是非常必要的，也就是需要在搜索引擎中采用聚類技術(shù)，對(duì)搜索結(jié)果進(jìn)行聚類處理。搜索引擎結(jié)果聚類技術(shù)實(shí)質(zhì)上是為了方便用戶的瀏覽，將聚類技術(shù)用于Web信息檢索結(jié)果的可視化輸出。Web網(wǎng)頁(yè)聚類是指將網(wǎng)頁(yè)集合分成若干個(gè)簇，要求同一簇內(nèi)網(wǎng)頁(yè)所描述的主題內(nèi)容盡可能地相似，而不同簇間的相似度盡可能地小。搜索引擎結(jié)果聚類技術(shù)根據(jù)搜索引擎結(jié)果所提供的信息（如URLs、標(biāo)題、摘要等）來歸納出聚類，使得對(duì)搜索引擎返回的大量的文檔列表的過濾操作變得方便，這些聚類是搜索引擎返回的文檔集合的高層視圖。在搜索引擎中應(yīng)用聚類技術(shù)，可以有效的組織和控制搜索引擎的搜索結(jié)果。經(jīng)過聚類處理的搜索結(jié)果以類目的形式呈現(xiàn)，內(nèi)容相似的搜索結(jié)果被劃分為一個(gè)類目，類目之間同時(shí)具有包含關(guān)系。這樣，搜索結(jié)果就被有效的組織起來，用戶可以快速地了解搜索結(jié)果的整體分布情況，并快速定位自己需要的搜索結(jié)果。例如上述碰到的問題可以通過網(wǎng)頁(yè)內(nèi)容的聚類得到有效的解決或改善。如果把通用搜索引擎返回的搜索結(jié)果進(jìn)行聚類，分成獨(dú)立的語(yǔ)義相關(guān)的主題，如“搜索引擎”，“圖像引擎”，“游戲引擎”，“汽車引擎”等，那么用戶可以快速的了解搜索引擎返回的結(jié)果都包含哪些主題，這樣就可以輕松的獲得自己關(guān)心的話題了。同時(shí)，我們也注意到自動(dòng)歸類等一些特性如今也越來越受到用戶的追捧。 圖1-2 不同年齡段的網(wǎng)絡(luò)用戶愿意網(wǎng)站跟蹤其行為從而獲得個(gè)性化服務(wù)的比例Choice Stream在2006的年度調(diào)查如圖1-2所示，用戶愿意犧牲部分的網(wǎng)絡(luò)隱私，以獲得更個(gè)性化的服務(wù)。根據(jù)報(bào)告8，有79%的用戶很愿意獲取個(gè)性化的信息服務(wù)，有43%的網(wǎng)絡(luò)用戶愿意以個(gè)人隱私作為交換，來得到個(gè)性化信息服務(wù)，對(duì)比2005年這個(gè)比例有顯著的增長(zhǎng)（11%），尤其是在18-34年齡段的人群中，有14%的增幅。在Read/Write Web8今年發(fā)起的一個(gè)搜索引擎用戶調(diào)查如圖1-3所示，個(gè)性化搜索與聚類搜索都獲得了較高的票數(shù)，也證實(shí)了個(gè)性化搜索是獲得用戶好評(píng)的搜索服務(wù)。得票數(shù)圖 1-3 最有前景的搜索引擎特性聚類搜索引擎作為新興的搜索引擎，其市場(chǎng)地位仍處于劣勢(shì)。但可以看到，國(guó)內(nèi)外各個(gè)聚類搜索引擎都在不斷地嘗試各種服務(wù)，為用戶提供有別于傳統(tǒng)搜索引擎的差異性服務(wù)。目前聚類搜索引擎還處于一個(gè)不斷摸索和變化的階段，其營(yíng)利模式和市場(chǎng)競(jìng)爭(zhēng)力還有等進(jìn)一步發(fā)掘。然而，聚類搜索引擎作為整個(gè)搜索市場(chǎng)的一股新生力量，正在漸漸打破傳統(tǒng)單一的獨(dú)立搜索引擎獨(dú)占的市場(chǎng)模式，給用戶帶來更新鮮的搜索體驗(yàn)，也掀開了搜索引擎市場(chǎng)激烈競(jìng)爭(zhēng)的冰山一角。1.2 聚類搜索引擎的現(xiàn)狀關(guān)于聚類搜索引擎的最早研究始于上個(gè)世紀(jì)70年代，由O. Zamir和 O. Etzioni等人在1997年第三屆國(guó)際知識(shí)發(fā)現(xiàn)和數(shù)據(jù)挖掘大會(huì)（3rd International Conference on Knowledge Discovery and Data Mining）上提出的4，此后，Oren Zamir等人又進(jìn)一步論證了將聚類技術(shù)應(yīng)用于搜索引擎的可行性，并開發(fā)了第一個(gè)聚類搜索引擎Grouper5。聚類引擎是近幾年才開始實(shí)際研究的課題，但很快引起了學(xué)術(shù)界的重視。自1999年開始，學(xué)者們開始以網(wǎng)頁(yè)中包含的文字內(nèi)容為聚類對(duì)象，對(duì)搜索引擎的聚類算法展開廣泛的研究。在這個(gè)過程中，研究的層次不斷深入，從對(duì)網(wǎng)頁(yè)中分析出的關(guān)鍵詞的進(jìn)行聚類研究，到綜合網(wǎng)頁(yè)的語(yǔ)法語(yǔ)義信息對(duì)網(wǎng)頁(yè)進(jìn)行實(shí)際意義上的聚類。在針對(duì)網(wǎng)頁(yè)文字內(nèi)容的聚類算法展開研究的同時(shí)，學(xué)者們也嘗試著將搜索引擎在搜索中產(chǎn)生的各種相關(guān)信息作為聚類對(duì)象，對(duì)這些信息的聚類算法進(jìn)行研究。這些相關(guān)信息包括用戶輸入的檢索式，用戶對(duì)檢索結(jié)果的訪問情況，檢索結(jié)果網(wǎng)頁(yè)之間的鏈接關(guān)系等等。國(guó)外關(guān)于聚類技術(shù)在搜索引擎中的應(yīng)用研究，已經(jīng)有了較完整的理論體系，并且已經(jīng)為互聯(lián)網(wǎng)搜索用戶提供聚類搜索服務(wù)，比較成熟的商業(yè)用聚類搜索引擎有Vivisimo6、Clusty、iBoogie、Webclust等。目前，聚類搜索引擎已呈現(xiàn)出多元化的發(fā)展方向，例如Grokker與Quintura將聚類結(jié)果進(jìn)行可視化顯示，Infocious將各種信息進(jìn)行聚類整合，為搜索用戶提供多種搜索服務(wù)。Carrot22是一個(gè)十分成功的開源聚類搜索引擎開發(fā)框架。它提供了基本的底層接口和一些基本的處理鏈，對(duì)一些聚類搜索共用的模塊進(jìn)行了有效的封裝或者改進(jìn)。這樣大大提高了研究人員或者開發(fā)工作者試驗(yàn)新想法、新算法的效率。本系統(tǒng)就是基于Carrot2的開發(fā)框架，成功實(shí)現(xiàn)的適合中文環(huán)境的Web搜索結(jié)果自動(dòng)歸類系統(tǒng)。國(guó)內(nèi)對(duì)聚類搜索引擎的研究還處于起步階段，目前僅有一家商用的聚類搜索引擎BBMAO，但可以看到業(yè)界逐漸對(duì)聚類搜索引擎引起重視，很多學(xué)術(shù)機(jī)構(gòu)都在研究這個(gè)領(lǐng)域，例如北大信息科學(xué)學(xué)院的Hua-Jun Zeng等人的論文Learning-to-Cluster7提出了聚類引擎就是其中一種解決方案。上海交通大學(xué)的APEX實(shí)驗(yàn)室也已發(fā)布一個(gè)簡(jiǎn)單的聚類搜索引擎。1.3 本文主要內(nèi)容在本論文中，我們所做的主要工作如下：1 重點(diǎn)研究Carrot2底層的開發(fā)框架，并且根據(jù)實(shí)際情況作了大量針對(duì)中文語(yǔ)言環(huán)境下有益的改造和改善工作。主要有以下幾個(gè)方面：（1） 構(gòu)建系統(tǒng)底層查詢流程，組織暢通的數(shù)據(jù)流通渠道。特別是在系統(tǒng)的整個(gè)開發(fā)框架中，如何保持接口的可擴(kuò)展性以及高效性，本文作了很大的改進(jìn)。針對(duì)中文應(yīng)用，在本系統(tǒng)的框架設(shè)計(jì)上考慮了中文處理的特殊性，特別設(shè)計(jì)了中文預(yù)處理模塊接口，而且成功的應(yīng)用到了Web搜索結(jié)果自動(dòng)歸類系統(tǒng)中。（2） 添加中文分詞，以適應(yīng)中文查詢的需求。在Carrot2提供的開發(fā)框架中，并沒有提供中文應(yīng)用方面的相關(guān)支持。而中文分詞對(duì)于本系統(tǒng)的成功實(shí)現(xiàn)起到關(guān)鍵性作用。本文在仔細(xì)研究中文分詞的相關(guān)技術(shù)后，成功地實(shí)現(xiàn)了適合中文查詢的Web搜索結(jié)果自動(dòng)歸類系統(tǒng)。2 除了在框架設(shè)計(jì)，中文分詞上所做的工作以外，還建立了一套適合中文領(lǐng)域的查詢處理流程。本系統(tǒng)的實(shí)現(xiàn)流程如圖1-4所示：圖1-4 系統(tǒng)實(shí)現(xiàn)流程圖1.4 本文結(jié)構(gòu)安排論文主要探討了描述優(yōu)先的聚類算法，并在Carrot22的開源框架上，構(gòu)建并實(shí)現(xiàn)了適用于中文的Web搜索結(jié)果自動(dòng)歸類系統(tǒng)（ACS）。本文共分為五個(gè)章節(jié)，各章節(jié)安排如下：第一章：緒論，涉及問題的提出，并介紹了聚類搜索引擎的研究背景，現(xiàn)狀，以及本文的目的。第二章：網(wǎng)頁(yè)自動(dòng)聚類技術(shù)，介紹了研究和開發(fā)網(wǎng)頁(yè)自動(dòng)聚類系統(tǒng)的一些相關(guān)知識(shí)。第三章：自動(dòng)歸類系統(tǒng)（ACS）框架設(shè)計(jì)，討論了Web搜索結(jié)果自動(dòng)歸類系統(tǒng)的體系結(jié)構(gòu)，運(yùn)用的技術(shù)以及系統(tǒng)所涉及的模塊。第四章：ACS系統(tǒng)開發(fā)與測(cè)試，本系統(tǒng)成功高效的開發(fā)，得益于Carrot22高可擴(kuò)展性的框架。第五章：總結(jié)與展望，對(duì)本系統(tǒng)開發(fā)的一些感想，以及對(duì)聚類系統(tǒng)今后發(fā)展趨勢(shì)的一些展望。- 5 -Web搜索結(jié)果自動(dòng)歸類系統(tǒng)第二章 網(wǎng)頁(yè)自動(dòng)聚類技術(shù)Web搜索結(jié)果自動(dòng)歸類系統(tǒng)通常由以下幾個(gè)部分組成：數(shù)據(jù)獲取、數(shù)據(jù)預(yù)處理、特征提取和聚類過程，如圖2-1所示。我們首先對(duì)聚類系統(tǒng)中涉及的一些概念和技術(shù)做一個(gè)闡述。圖2-1 檢索自動(dòng)聚類系統(tǒng)的一般步驟2.1文檔預(yù)處理2.1.1預(yù)處理步驟Web網(wǎng)頁(yè)通常包含有大量的標(biāo)簽信息、腳本元素等噪音內(nèi)容，如何在數(shù)據(jù)進(jìn)行聚類之前把這些數(shù)據(jù)清洗完畢是一個(gè)十分關(guān)鍵的步驟。一般可以分為以下幾個(gè)步驟： （1）去除HTML標(biāo)簽：javascript等一些腳本元素。（2）去除非字字符：如￥#&。（3）標(biāo)記標(biāo)題：在計(jì)算詞項(xiàng)權(quán)重的時(shí)候可以作為參考。（4）頁(yè)面語(yǔ)言識(shí)別：對(duì)采用那一種分詞方法很重要。 下面著重介紹一下中文分詞方法。2.1.2 中文分詞眾所周知，英文是以詞為單位的，詞和詞之間是靠空格隔開，而中文是以漢字為單位，詞與詞之間沒有明顯的形態(tài)界限，要進(jìn)行漢語(yǔ)的計(jì)算機(jī)處理，必須首先將漢語(yǔ)的詞與詞分割開，即分詞。句子中所有的字連起來才能描述一個(gè)意思。例如，英文句子“It is a stone”，用中文則為：“這是一塊石頭”。計(jì)算機(jī)可以很簡(jiǎn)單通過空格知道“stone”是一個(gè)單詞，但是不能很容易明白石、頭兩個(gè)字合起來才表示一個(gè)詞。如果對(duì)“這是一塊石頭”這個(gè)句子進(jìn)行分詞，分詞的結(jié)果是：“這是 一塊 石頭”。中文分詞是其他中文信息處理的基礎(chǔ)，自動(dòng)歸類只是中文分詞的一個(gè)應(yīng)用。目前采用的分詞歸納起來不外乎三大類：基于字符串匹配的分詞方法、基于理解的分詞方法和基于統(tǒng)計(jì)的分詞方法。在本系統(tǒng)的實(shí)現(xiàn)過程中，我們使用了基于字符串匹配方法，其容易理解，實(shí)現(xiàn)也相對(duì)簡(jiǎn)單。下面僅對(duì)該方法做一介紹?；谧址ヅ涞姆椒ɑ谧址ヅ涞姆衷~方法，又叫做機(jī)械分詞方法。它是按照一定的策略將待切分的漢字串與機(jī)器詞典中的詞條進(jìn)行匹配，若在詞典中找到某個(gè)字符串，則匹配成功（識(shí)別）。按照掃描的方向不同，串匹配分詞方法可分為正向匹配分詞方法和逆向匹配分詞方法；按照優(yōu)先匹配的長(zhǎng)度不同，又可分為最大匹配分詞方法和最小匹配分詞方法；按照是否與詞性標(biāo)注過程相結(jié)合，又可分為單純分詞方法和結(jié)合標(biāo)注分詞方法。本系統(tǒng)中，采用正向和逆向結(jié)合的雙向匹配方法來進(jìn)行中文分詞。2.2向量空間模型（VSM）向量空間模型（Vector Space Model, VSM）是目前信息檢索中最常用的文檔表示模型。在萬(wàn)維網(wǎng)信息檢索方面，向量空間模型比布爾模型等傳統(tǒng)模型更適合。這是因?yàn)椴紶柲Ｐ褪亲詈?jiǎn)單的檢索模型，標(biāo)準(zhǔn)的布爾模型是二元邏輯，所檢索的頁(yè)面要么與所鍵入的關(guān)鍵詞組有關(guān)，要么無(wú)關(guān)，檢索結(jié)果一般不進(jìn)行相關(guān)性排序；而向量空間模型不僅可以方便地產(chǎn)生有效的檢索結(jié)果，而且能夠提供相關(guān)頁(yè)面的文摘，并進(jìn)行檢索結(jié)果分類，為用戶提供準(zhǔn)確的所需信息?；谙蛄靠臻g模型的信息檢索一般過程如下21：（1）將各個(gè)文檔和查詢都表示為向量；（2）計(jì)算查詢與各個(gè)文檔之間的相似度；（3）按照查詢與各個(gè)文檔之間的相似度對(duì)相關(guān)的文檔進(jìn)行排序；（4）將排序后的文檔以線性列表的形式返回給用戶 在向量空間模型中，各個(gè)文本和查詢項(xiàng)的內(nèi)容都表示為向量。設(shè)共有個(gè)文檔，對(duì)所有文本進(jìn)行詞語(yǔ)切分、過濾和轉(zhuǎn)換之后，合適的個(gè)詞項(xiàng)（Term）被提取出來，構(gòu)造的詞項(xiàng)/文檔關(guān)系矩陣（Term-Document Matrix），矩陣中的元素表示第- 51 -Web搜索結(jié)果自動(dòng)歸類系統(tǒng)個(gè)詞項(xiàng)在第個(gè)文檔中的權(quán)重（Weight）。這樣，每個(gè)詞項(xiàng)就可以用W中對(duì)應(yīng)的行向量來表示。 應(yīng)用上述方法，文本被表示為一組有代表性的詞項(xiàng)（Term，索引項(xiàng)）的集合。通常需要提取待處理文本集合中含有的所有索引項(xiàng)。設(shè)索引項(xiàng)的集合，其中表示文本集合中含有的索引項(xiàng)的個(gè)數(shù)，實(shí)際使用中都是隨著文本集合的不斷變化而增加的。通常都是在預(yù)處理以后，只保留文檔中最具有明顯標(biāo)志性作用的索引項(xiàng)。對(duì)初始文檔，其中是文檔含有的索引項(xiàng)的數(shù)目，經(jīng)過預(yù)處理以后其中，預(yù)處理可以很好的減小計(jì)算量。向量空間模型通過分配權(quán)重給文檔中的索引項(xiàng)，將文檔表示為權(quán)重的向量，其中表示索引項(xiàng)在文檔中的權(quán)重。的計(jì)算采用TFIDF加權(quán)策略，具體的計(jì)算公式可以表示為： （2-1）其中表示詞在文檔中出現(xiàn)的次數(shù)，表示要處理的文檔的個(gè)數(shù)， 表示含有詞的文檔個(gè)數(shù)。這種權(quán)重計(jì)算方式中的大小與在文檔中出現(xiàn)的次數(shù)成正比，而與在整個(gè)文本集合中出現(xiàn)的次數(shù)成反比。此外，對(duì)的計(jì)算還有許多形式，在此不一一列舉。在檢索時(shí)也需要將查詢表示成權(quán)重的向量以計(jì)算查詢與文檔的相似度。查詢表示為。相似度的計(jì)算公式表示為： （2-2）這種相似度計(jì)算是通過考察特征向量的余弦夾角實(shí)現(xiàn)的。2.3描述優(yōu)先的聚類算法俗語(yǔ)有云：“物以類聚，人以群分?！本垲惥褪抢糜?jì)算機(jī)技術(shù)來實(shí)現(xiàn)這一目的的一種技術(shù)，其輸入是一組未分類的記錄，且事先不知道如何分類，也可能不知道要分成幾類，通過分析數(shù)據(jù)，合理劃分記錄集合，確定每個(gè)記錄所屬的類別，把相似性大的對(duì)象聚集為一個(gè)簇。聚類的標(biāo)準(zhǔn)是使簇內(nèi)相似度盡可能大、簇間相似度盡可能小。聚類屬于無(wú)監(jiān)督學(xué)習(xí)，由于數(shù)據(jù)密度分布、聚類規(guī)則、處理數(shù)據(jù)量等的多樣性，從而產(chǎn)生了許多種聚類算法。聚類算法可以分為劃分聚類、層次聚類、密度型聚類、網(wǎng)格型聚類和其他幾種聚類算法910。而本系統(tǒng)采用的Lingo算法與上述幾種聚類算法有所不同，Lingo算法采取的是描述優(yōu)先的策略來達(dá)到最終標(biāo)簽的可理解性。我們可以通過圖2-2很清晰的看出描述優(yōu)先的聚類算法和傳統(tǒng)聚類算法的區(qū)別。圖2-2 傳統(tǒng)聚類（左）和描述優(yōu)先聚類（右）的比較在本節(jié)中，將介紹在信息檢索領(lǐng)域，傳統(tǒng)的文檔聚類算法和描述優(yōu)先的聚類算法有哪些區(qū)別。下面我們主要從需求和文檔遍歷方式上來進(jìn)行分析。聚類的一般定義如下：11給定一定數(shù)量的對(duì)象或個(gè)體，并且每個(gè)個(gè)體都用一定的數(shù)學(xué)方法來表示，按照一定分類規(guī)則，把這些對(duì)象分入一定的類內(nèi)，使得類內(nèi)的對(duì)象盡可能的相似，類間的對(duì)象差別盡可能的大。類的數(shù)目和各個(gè)類的表示需要自行定義。上面的定義沒有涉及有關(guān)類標(biāo)簽的問題，而其目的只是去發(fā)現(xiàn)擁有相似對(duì)象的類。如果應(yīng)用程序需要把聚類的結(jié)果呈現(xiàn)給用戶，則需要找到合適的文字去描述相應(yīng)的類，而這個(gè)問題在定義中是沒有提到的。一個(gè)好的算法（根據(jù)定義）如果它沒法去解釋類里面包含的內(nèi)容，那么對(duì)用戶來說可能根本沒用。所以最核心的問題是如何從發(fā)現(xiàn)類聚主題的算法轉(zhuǎn)移到更好的類聚描述的方法。比如，在VSM模型中，想從這個(gè)“詞袋”模型中構(gòu)建聚類標(biāo)簽來表示得到的類，似乎不太可能。同時(shí)，用關(guān)鍵詞或者頻繁出現(xiàn)的短語(yǔ)來表示類標(biāo)簽，并不能很好的滿足應(yīng)用程序的需求。 鑒于以上問題，Dweiss在他的博士論文11中提出了一種描述優(yōu)先的算法。其著重類標(biāo)簽的表達(dá)。以下是他的定義：描述優(yōu)先的聚類算法是一種可以用有意義的，可理解的，精簡(jiǎn)的文字標(biāo)簽來表示的語(yǔ)義相關(guān)的不同的類。根據(jù)以上定義，一個(gè)描述優(yōu)先的聚類結(jié)果應(yīng)該有清晰的，可理解的標(biāo)簽描述的類。所以，文檔內(nèi)容聚類是一個(gè)起決定性作用的步驟，但并不是我們的最終目標(biāo)。綜上，我們可以放棄那些沒有辦法用有意義標(biāo)簽來描述的類?？赡芤婚_始還感到疑惑，但是在Dweiss的實(shí)驗(yàn)中11，可以充分印證這個(gè)思想的合理性：（1）如果標(biāo)簽表達(dá)不清晰，用戶不會(huì)花額外的時(shí)間來弄明白一個(gè)標(biāo)簽的意思。（2）如果標(biāo)簽只是一個(gè)單獨(dú)的關(guān)鍵詞，用戶將不會(huì)查看該類里面的文檔。（3）類描述和類內(nèi)的文檔，如果不清晰或者關(guān)系模糊，將使用戶失去信心。在本系統(tǒng)中采用的Lingo算法13就是一個(gè)描述優(yōu)先的算法，最終聚類標(biāo)簽的可理解性是我們一個(gè)十分重要的目標(biāo)。2.4 Lingo聚類算法本系統(tǒng)實(shí)現(xiàn)并使用了Lingo（Label INduction Grouping algOrithm）和STC（Suffix tree clustering）算法。在Lingo算法中應(yīng)用了標(biāo)簽優(yōu)先聚類算法的思想，并在文中詳細(xì)討論了算法的流程和實(shí)現(xiàn)步驟。由于篇幅，這里不介紹STC聚類算法12。本文通過實(shí)現(xiàn)這兩種算法，構(gòu)建Web搜索結(jié)果自動(dòng)歸類系統(tǒng)，進(jìn)一步了解聚類搜索引擎的工作原理，以及采用Lingo算法的優(yōu)勢(shì)。在Lingo中，需要兩個(gè)很重要的步驟。一個(gè)是用后綴數(shù)組提取共現(xiàn)頻繁短語(yǔ)，這是提取候選標(biāo)簽的基礎(chǔ)。另一個(gè)是LSI方法，我們前面介紹了構(gòu)建VSM的方法，而LSI方法就是基于VSM的，并在計(jì)算了TF-IDF權(quán)重之后，用SVD（奇異值分解）進(jìn)行矩陣分解，使矩陣的維數(shù)進(jìn)一步降低，有利于主題的聚類。下面將詳細(xì)介紹后綴數(shù)組和LSI。2.4.1后綴數(shù)組（Suffix Arrays）后綴數(shù)組的概念定義12定義1： 對(duì)于字符串，定義的長(zhǎng)度為，第個(gè)字符為，第個(gè)字符至第個(gè)字符組成的子串為。構(gòu)成字符串的字符集。定義2：的，即的前個(gè)字符組成的字符串，如果，則其。定義3： 按所有后綴字符串的排序的后綴數(shù)組為，相應(yīng)的名次數(shù)組為13 。后綴數(shù)組（suffix array）是字符串處理應(yīng)用中使用的各種數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)。表示在字符集上的一個(gè)字符串，$ 是唯一的終結(jié)符且小于字符集中的任一字符，是在字符串的末尾加上終結(jié)符得到的一個(gè)新字符串，如果表示字符串的長(zhǎng)度，表示S的第個(gè)字符，那么是字符串的第個(gè)后綴數(shù)組。例如：，在其后增加一個(gè)結(jié)束符，得到，那么，是的第2個(gè)后綴數(shù)組。2.4.2潛在語(yǔ)義索引（LSI）在Web上對(duì)某個(gè)特定領(lǐng)域的信息進(jìn)行采集，首先需要讓采集系統(tǒng)了解這個(gè)領(lǐng)域的精確描述。通常是給定一個(gè)樣本文檔集合，采用合適的代數(shù)模型進(jìn)行描述。傳統(tǒng)的檢索模型描述中16，無(wú)論布爾模型，向量空間模型（Vector Space Model，VSM) 還是概率模型，盡管實(shí)現(xiàn)方法上有很多差異，但對(duì)文本的過濾、檢索等操作都是通過文檔之間的詞匹配來實(shí)現(xiàn)的。由于詞具有同義性，多義性和使用上的概念相關(guān)性，僅僅通過字面的匹配不能準(zhǔn)確地進(jìn)行各種功能操作。從1988年開，Dumais等進(jìn)行了一系列的研究，提出了新的信息檢索代數(shù)模型，主要是為克服現(xiàn)有的查詢?cè)~與文檔匹配檢索技術(shù)的缺點(diǎn)而設(shè)計(jì)的。在VSM基礎(chǔ)上，利用線性代數(shù)的知識(shí)，通過矩陣的奇異值分解(Singular Value Decomposition，SVD) 來進(jìn)行潛在語(yǔ)義索引，簡(jiǎn)稱為L(zhǎng)SI(Latent Semantic Indexing)或者LSA(Latent Semantic Analysis)。LSI通過數(shù)學(xué)分析，計(jì)算出文檔集合中潛在內(nèi)涵的概念之間的關(guān)系，通過潛在概念集表示所有的概念空間，減少了概念表示之間的模糊性，避免了VSM中各維之間概念正交的假設(shè)。它把觀測(cè)到詞項(xiàng)/文檔關(guān)聯(lián)數(shù)據(jù)的不可靠性看作是一種統(tǒng)計(jì)問題，認(rèn)為在數(shù)據(jù)中存在一種潛在的語(yǔ)義結(jié)構(gòu)，這種結(jié)構(gòu)由于檢索詞出現(xiàn)的多樣性被干擾。LSI使用統(tǒng)計(jì)技術(shù)去估計(jì)這些潛在的語(yǔ)義結(jié)構(gòu)，去掉這種“噪聲”。針對(duì)一些TREC文檔庫(kù)的實(shí)驗(yàn)結(jié)果及一些初步的理論分析，證實(shí)了LSI的優(yōu)越性24。通過特定領(lǐng)域樣本文檔集LSI矩陣，獲得樣本集潛在語(yǔ)義的矩陣描述，可以很好地計(jì)算文檔之間潛在內(nèi)容的相關(guān)性，是目前在信息檢索領(lǐng)域最具有前景的發(fā)展方向之一。與傳統(tǒng)的信息檢索代數(shù)模型相比，LSI具有如下優(yōu)點(diǎn)15：(1) 表示的不僅僅是所有標(biāo)引詞的簡(jiǎn)單出現(xiàn)頻度和分布關(guān)系，而是所有標(biāo)引詞在樣本文檔集合中的潛在語(yǔ)義關(guān)系，通過對(duì)樣本文檔集合的文檔操作，語(yǔ)義精度得到較大的提高。(2) 采用一個(gè)低秩近似矩陣替代了詞項(xiàng)/文檔矩陣，存儲(chǔ)計(jì)算效率上得到較大的提高。(3) 不僅表示了標(biāo)引詞和文檔之間的關(guān)系，而且包含了不同詞之間的潛在關(guān)系，可以表示標(biāo)引詞之間，文檔之間，標(biāo)引詞與文檔之間，查詢偽文本和文檔之間的各種相似度，使用上更加靈活。LSI模型的主要問題是從高維映射到低維時(shí)如何確定值16，目前還沒有理論上合適的方法。一方面希望足夠大，能夠適合所有的潛在語(yǔ)義結(jié)構(gòu)，但太大會(huì)導(dǎo)致噪聲，對(duì)于LSI使用產(chǎn)生影響;如果太小，則不能適應(yīng)樣本的誤差或其他次要的細(xì)節(jié)，保留下來的結(jié)構(gòu)太少，無(wú)法把握運(yùn)算的結(jié)果。實(shí)際中，往往需要通過多次的試驗(yàn)，以選取針對(duì)具體文檔集合操作效率最好的值。對(duì)于非常大的文檔集，取100300比較適合16。中文文檔集合LSI初步測(cè)試基本吻合英文的取值范圍。2.5小結(jié)本章介紹了一系列網(wǎng)頁(yè)自動(dòng)聚類技術(shù)，其中包含預(yù)處理，中文分詞，向量空間模型。在介紹聚類算法的同時(shí)，著重介紹了描述優(yōu)先的聚類算法。本系統(tǒng)采用的Lingo聚類算法就采用了描述優(yōu)先的聚類思想。為了更加直接、簡(jiǎn)明的了解Lingo聚類算法的運(yùn)作原理，在本章中我們通過簡(jiǎn)化文檔，描述了Lingo聚類處理的整個(gè)流程。下一章，將詳細(xì)介紹ACS系統(tǒng)的體系結(jié)構(gòu)以及開發(fā)該系統(tǒng)所需要的相關(guān)技術(shù)。第三章 自動(dòng)歸類系統(tǒng)（ACS）框架設(shè)計(jì)第三章 自動(dòng)歸類系統(tǒng)（ACS）框架設(shè)計(jì)聚類搜索引擎是搜索引擎的一種，它用關(guān)鍵詞從傳統(tǒng)的獨(dú)立搜索引擎中獲取搜索結(jié)果列表，通過對(duì)搜索結(jié)果進(jìn)行聚類處理后，將二次加工后的搜索結(jié)果和聚類類目呈現(xiàn)給用戶。一般而言，聚類搜索引擎是元搜索引擎，它本身并不對(duì)網(wǎng)絡(luò)文檔進(jìn)行爬行和索引，而只是利用接口向各個(gè)獨(dú)立搜索引擎發(fā)出關(guān)鍵字檢索請(qǐng)求，對(duì)請(qǐng)求得到的搜索結(jié)果進(jìn)行聚類處理。但也有極少數(shù)聚類搜索引擎建立有自己的網(wǎng)頁(yè)索引庫(kù)，例如 Northern Light 聚類搜索引擎，同樣具備有爬行器和網(wǎng)頁(yè)索引數(shù)據(jù)庫(kù)，用戶提交關(guān)鍵字搜索時(shí)只在自己的索引數(shù)據(jù)庫(kù)中進(jìn)行檢索。本系統(tǒng)就是一個(gè)聚類搜索引擎，本章主要講述ACS(Automatic Categorization System)的框架設(shè)計(jì)，應(yīng)用的技術(shù)以及各個(gè)模塊的內(nèi)涵。3.1聚類搜索引擎概述聚類搜索引擎13自動(dòng)將來自各個(gè)搜索引擎的搜索結(jié)果，自動(dòng)組織成各種類(Cluster)，統(tǒng)一呈現(xiàn)給搜索用戶。這種聚類技術(shù)是實(shí)時(shí)進(jìn)行，聚類過程中沒有人工干預(yù)，因而不同于分類(Classification)和標(biāo)引(Tagging)。此外，由于聚類搜索引擎將搜索結(jié)果分為各個(gè)類目，其類名的選取非常重要，它為用戶指示了此類的核心內(nèi)容。類名的選取需要遵循簡(jiǎn)潔、可理解、準(zhǔn)確、唯一性的特點(diǎn)。聚類搜索引擎由于對(duì)海量的搜索結(jié)果進(jìn)行了聚類處理，使得搜索結(jié)果具有目錄式的分類，用戶可以方便快捷地找到自己的目標(biāo)信息，即對(duì)應(yīng)類下的搜索結(jié)果，而免去在無(wú)數(shù)的搜索結(jié)果中進(jìn)行甄別、篩選、過濾等人工辨別。3.2 ACS系統(tǒng)體系結(jié)構(gòu)描述絕大多數(shù)聚類搜索引擎屬于元搜索引擎，圖3-1是聚類搜索引擎的體系結(jié)構(gòu)13，可以看到，其工作原理與元搜索引擎有不少相似之處。聚類結(jié)果輸出調(diào)度中心數(shù)據(jù)獲取模塊GoogleYahoo!MSN百度獨(dú)立搜索引擎搜索結(jié)果重排序聚類分析搜索引擎用戶界面 圖3-1聚類搜索引擎的體系結(jié)構(gòu)3.2.1搜索引擎用戶界面該模塊負(fù)責(zé)與用戶進(jìn)行交互，它接收用戶的查詢請(qǐng)求，以及用戶檢索偏好，例如選擇的獨(dú)立搜索引擎對(duì)象，返回的搜索結(jié)果數(shù)量等。同時(shí)，該模塊還將聚類處理后的最終結(jié)果以統(tǒng)一的格式返回給用戶。3.2.2調(diào)度中心調(diào)度中心是聚類搜索引擎一個(gè)核心的調(diào)度模塊，負(fù)責(zé)接受用戶的檢索請(qǐng)求傳遞到數(shù)據(jù)獲取模塊，并將其返回的數(shù)據(jù)處理后，傳遞給搜索結(jié)果重排序模塊。在本系統(tǒng)中，在原有Carrot22提供的控制接口上，實(shí)現(xiàn)了整個(gè)處理流程的控制，并成功的組織調(diào)用相關(guān)組件，保證數(shù)據(jù)流的通暢。3.2.3數(shù)據(jù)獲取模塊數(shù)據(jù)獲取模塊負(fù)責(zé)與各個(gè)獨(dú)立搜索引擎的交互，包括多個(gè)搜索引擎的接口代理，它們把用戶的查詢轉(zhuǎn)換成對(duì)應(yīng)搜索引擎能夠辨識(shí)的格式分別發(fā)送，并負(fù)責(zé)解析對(duì)應(yīng)搜索引擎返回的搜索結(jié)果，并將解析過的搜索結(jié)果傳遞給調(diào)度中心。數(shù)據(jù)獲取模塊往往采用多線程(Multithreading)的方式作并行地在各個(gè)獨(dú)立搜索引擎中進(jìn)行搜索，并行地調(diào)用多個(gè)搜索引擎。并且對(duì)于每個(gè)獨(dú)立搜索引擎，數(shù)據(jù)獲取模塊通過多個(gè)線程并行地取回其搜索結(jié)果網(wǎng)頁(yè)。只有這樣采用并行線程，才能更快地獲取足夠多的搜索結(jié)果。在本系統(tǒng)中，我們只實(shí)現(xiàn)了從Yahoo搜索引擎獲取數(shù)據(jù)，關(guān)于對(duì)其他搜索引擎數(shù)據(jù)的獲取，將在以后的改進(jìn)階段實(shí)現(xiàn)。3.2.4搜索結(jié)果重排序模塊搜索結(jié)果重排序模塊負(fù)責(zé)對(duì)數(shù)據(jù)獲取模塊傳遞過來的各個(gè)搜索結(jié)果列表，進(jìn)行網(wǎng)頁(yè)去重和搜索結(jié)果重排序。由于本系統(tǒng)如今只實(shí)現(xiàn)了從Yahoo接口獲取數(shù)據(jù)，故并沒有涉及結(jié)果重排序模塊，若以后從多個(gè)搜索引擎獲取結(jié)果，則需在系統(tǒng)中加入此步驟。下面對(duì)重排序做一簡(jiǎn)單介紹：對(duì)于相同的搜索關(guān)鍵字，不同搜索引擎的返回結(jié)果均不相同，并且彼此的搜索結(jié)果中會(huì)有重復(fù)之處。搜索結(jié)果重排序模塊需要把來自各個(gè)搜索引擎的搜索結(jié)果列表綜合起來，去重后，重新排序形成一個(gè)統(tǒng)一的搜索結(jié)果列表。一種簡(jiǎn)單有效的重排序算法是最高位置算法(Highest-Rank Algorithm) 21，下面簡(jiǎn)要描述這一算法。對(duì)各個(gè)獨(dú)立搜索引擎返回的每一項(xiàng)搜索結(jié)果進(jìn)行檢查，以它在各個(gè)搜索引擎返回的搜索結(jié)果列表中出現(xiàn)的最高位置作為它的序號(hào)，并刪除它在其它位置的出現(xiàn)，直到各個(gè)搜索結(jié)果列表都沒有重復(fù)的搜索結(jié)果為止，然后將所有的搜索結(jié)果按照其序號(hào)順序排列成為一個(gè)統(tǒng)一的列表。對(duì)于相同序號(hào)的搜索結(jié)果，可以根據(jù)其最高位置所在的搜索引擎的優(yōu)劣質(zhì)量順序排序18。3.2.5聚類分析模塊在這個(gè)模塊中，聚類搜索引擎要完成數(shù)據(jù)清理和聚類處理處理過程。（1）數(shù)據(jù)清理：各個(gè)搜索引擎的搜索結(jié)果中一般包括相關(guān)頁(yè)面的標(biāo)題、摘要和目標(biāo)URL地址。數(shù)據(jù)清理過程便是將搜索結(jié)果頁(yè)面的各部分內(nèi)容進(jìn)行清理，合并成一個(gè)文檔內(nèi)容，來表示搜索結(jié)果頁(yè)面內(nèi)容。在這個(gè)過程中，聚類處理模塊對(duì)搜索引擎返回的搜索結(jié)果網(wǎng)頁(yè)進(jìn)行解析，去除其中的HTML標(biāo)簽，并以標(biāo)點(diǎn)符號(hào)、空格等為邊界把網(wǎng)頁(yè)切分成多個(gè)較短的字符串。然后用中文分詞處理將之表示成一個(gè)短語(yǔ)序列，為關(guān)鍵詞組提取作好準(zhǔn)備。（2）聚類分析：接下來，對(duì)所有的搜索結(jié)果文檔(短語(yǔ)序列)，使用Lingo聚類算法13進(jìn)行處理。在數(shù)據(jù)預(yù)處理之后，我們先提取網(wǎng)頁(yè)中的候選標(biāo)簽，這需要使用到后綴數(shù)組。然后通過潛在語(yǔ)義索引(LSI)，分解矩陣，確立網(wǎng)頁(yè)的主題分類。最后通過選取合適的標(biāo)簽，并把文檔重新歸類到相應(yīng)的標(biāo)簽底下。這樣就完成了聚類分析過程。對(duì)文檔完成聚類后，再對(duì)生成的聚類類目進(jìn)行排序，一般對(duì)聚類類目的排序采用最大類別優(yōu)先的策略，即按照包含的結(jié)果文檔數(shù)從大到小排序。下面對(duì)ACS系統(tǒng)采用的聚類算法Lingo進(jìn)行詳細(xì)描述：Lingo算法的大致流程如圖3-2所示13。圖3-2 Lingo算法的流程在ACS系統(tǒng)中，Lingo是默認(rèn)的聚類算法。所以這里用一個(gè)小例子來解釋一下Lingo是如何運(yùn)作的。圖3-3 詞項(xiàng)/文檔矩陣文檔矩陣如圖3-3左所示，是一個(gè)以詞項(xiàng)為行向量，文檔為列向量的一個(gè)矩陣。為了建立VSM模型，我們需要建立一個(gè)詞項(xiàng)/文檔矩陣：一個(gè)包含所有出現(xiàn)在輸入文檔中詞項(xiàng)頻度的矩陣。假設(shè)，如果只有2個(gè)詞項(xiàng)，詞項(xiàng)和詞項(xiàng)。這樣就可以方便的把VSM模型可視化為二維平面。平面的每一個(gè)點(diǎn)代表一個(gè)文檔。圖3-4 詞項(xiàng)/文檔矩陣矩陣分解的任務(wù)是通常把一個(gè)矩陣分解為兩個(gè)矩陣，而這兩個(gè)矩陣的叉積盡可能的與原始矩陣相似，并且具有更低的維數(shù)。其中，左矩陣可以看作是低維空間的基向量，而另一個(gè)矩陣可以看作是我們重建原始矩陣的一個(gè)系數(shù)。在圖3-4中，基向量大致刻畫了輸入集合中的主要走勢(shì)。圖3-5 候選標(biāo)簽選取在圖3-5中，請(qǐng)注意，頻繁短語(yǔ)和基向量都表示在同一個(gè)向量空間中（輸入文檔矩陣）。所以這里可以通過余弦值找到適合每個(gè)基向量的最相似的頻繁短語(yǔ)。這樣，每個(gè)基向量都將找到一個(gè)聚簇標(biāo)簽。圖3-6 聚簇標(biāo)簽的選定和內(nèi)容聚類為了形成合適的聚簇，我們可以再次通過利用余弦值相似度方法，把大于一定值的文檔賦給合適的標(biāo)簽即可，如圖3-6所示。到此為止，聚類已經(jīng)成功完成，只要組織輸出即可。3.2.6聚類結(jié)果輸出模塊該模塊將經(jīng)過聚類處理的各搜索結(jié)果網(wǎng)頁(yè)，以聚類搜索引擎本身采用的統(tǒng)一格式進(jìn)行處理。一般獨(dú)立搜索引擎的搜索結(jié)果中，都包括對(duì)目標(biāo)網(wǎng)頁(yè)的標(biāo)題描述、網(wǎng)頁(yè)摘要、URL目標(biāo)地址、網(wǎng)頁(yè)獲取時(shí)間等。這一模塊分析各個(gè)獨(dú)立搜索引擎結(jié)果的格式，對(duì)其內(nèi)容進(jìn)行處理，統(tǒng)一表述成自己的搜索結(jié)果顯示方式。此外，此模塊還可以在格式化后的搜索結(jié)果中，加入有自身特色的數(shù)據(jù)。例如結(jié)果數(shù)據(jù)的搜索引擎來源，在不同搜索引擎中的排列序號(hào)等等。在本系統(tǒng)中，還可以查看每個(gè)網(wǎng)頁(yè)文檔屬于的類。3.3系統(tǒng)開發(fā)工具和運(yùn)行環(huán)境（1）開發(fā)工具：Eclipse + Tomcat（2）版本管理工具： CVS（3）測(cè)試工具： JUnit （4）基于平臺(tái)： Windows（5）相關(guān)資源：Yahoo API,Log4j日志工具，緩存管理工具Ehcache等3.4 小結(jié)本章詳細(xì)介紹了Web搜索結(jié)果自動(dòng)歸類系統(tǒng)的整個(gè)框架設(shè)計(jì)，并把系統(tǒng)分為六大部分，分別是搜索引擎用戶界面，調(diào)度中心，數(shù)據(jù)獲取模塊，搜索結(jié)果重排序模塊，聚類處理模塊和聚類結(jié)果輸出模塊。其中由于現(xiàn)在我們只從單一的搜索引擎抓取數(shù)據(jù)（Yahoo），所以在實(shí)際的開發(fā)過程中，搜索結(jié)果重排序模塊并沒有使用到。Web搜索結(jié)果自動(dòng)歸類系統(tǒng)第四章 ACS系統(tǒng)開發(fā)與測(cè)試ACS(Automatic Categorization System)系統(tǒng)的設(shè)計(jì)目標(biāo)是設(shè)計(jì)在線的，根據(jù)內(nèi)容分類的，更好地滿足用戶需要的中文網(wǎng)頁(yè)自動(dòng)歸類系統(tǒng)。在線是指即時(shí)響應(yīng)用戶的聚類要求，迅速提供最新的聚類結(jié)果。根據(jù)內(nèi)容分類的，指聚類的結(jié)果是經(jīng)過分門別類之后，展現(xiàn)給用戶的。類與類之間應(yīng)該允許重疊，即若信息涉及多個(gè)類的主題則可以屬于多個(gè)類，并且采用樹的組織形式，樹中每個(gè)結(jié)點(diǎn)都對(duì)應(yīng)一個(gè)類。下面通過介紹系統(tǒng)的設(shè)計(jì)、開發(fā)、測(cè)試來了解ACS系統(tǒng)的實(shí)現(xiàn)過程。4.1 ACS系統(tǒng)設(shè)計(jì)概述 圖4-1 ACS系統(tǒng)查詢界面本系統(tǒng)的設(shè)計(jì)本著為用戶著想的目的，為用戶提供一個(gè)輸入查詢?cè)~的界面，如圖4-1所示，并且可以選擇從搜索引擎獲取多少數(shù)據(jù)量(現(xiàn)在備選的有50，100，200，400，默認(rèn)100)，還可以根據(jù)愛好，選擇相應(yīng)的算法(現(xiàn)在實(shí)現(xiàn)的有Lingo和STC，默認(rèn)為L(zhǎng)ingo)。聚類后的結(jié)果用目錄結(jié)構(gòu)展現(xiàn)給用戶，如圖4-2所示，用戶可以方便的選擇相應(yīng)的主題目錄進(jìn)行瀏覽。 圖4-2 聚類結(jié)果輸出界面 下面7點(diǎn)是我們系統(tǒng)開發(fā)的范圍和目標(biāo)：(1) Web搜索引擎返回的頁(yè)面是動(dòng)態(tài)的，其文檔類別是未知的、不固定的。這也是通用搜索引擎的一個(gè)特性，我們針對(duì)這個(gè)情況采取相應(yīng)的辦法，使得文檔最終可以分 類后展現(xiàn)給用戶。(2) 根據(jù)頁(yè)面內(nèi)容自身的差異，使用文檔聚類