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

Web搜索結果自動歸類系統(tǒng)摘要隨著因特網上信息資源的爆炸性增長，搜索引擎已經成為了目前網絡上最重要的信息檢索工具。但很顯然，人們對目前的搜索引擎還有很多不滿之處。對于用戶提交的檢索要求，現(xiàn)有的搜索引擎（如Google, Yahoo, MSN, 百度）通常計算網頁相關性后返回給用戶一長串結果列表。由于搜索結果中各種檢索主題是混和在一起的，用戶需要在大量的搜索結果中尋找所需要的信息，而且用戶很難對搜索結果進行控制。要解決這些問題，一種組織和控制搜索結果的有效方法是必要的。如果在搜索引擎中采用聚類技術對搜索結果進行聚類處理，經過聚類處理的搜索結果以類目的形式呈現(xiàn)，主題相似的搜索結果被劃分為一個類目，類目之間同時又具有包含關系。這樣，用戶可以快速了解搜索結果的整體分布情況，并快速定位自己需要的搜索結果。在研究搜索引擎原理和聚類算法的基礎上，本文對聚類搜索引擎的體系結構，以及應用于網頁聚類的Lingo聚類算法進行了詳細探討。并基于開源聚類搜索引擎Carrot22的框架，實現(xiàn)了適用于中文領域的Web搜索結果自動歸類系統(tǒng)。首先，在本系統(tǒng)的框架設計上，充分考慮到中文環(huán)境的特殊性，由此在接口設計和可擴展性設計上，做了十分有意義的工作。其次，本文實現(xiàn)了描述優(yōu)先的聚類算法Lingo，系統(tǒng)聚類結果的可讀性和可理解性都得到大大提高。最后，通過比較說明，采用描述優(yōu)先的聚類算法對提高標簽可理解性的優(yōu)勢。關鍵詞：聚類算法，搜索引擎，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本文主要內容41.4本文結構安排5第二章 網頁自動聚類技術62.1文檔預處理62.1.1預處理步驟62.1.2 中文分詞62.2向量空間模型（VSM）72.3描述優(yōu)先的聚類算法82.4 Lingo聚類算法102.4.1后綴數(shù)組（Suffix Arrays）102.4.2潛在語義索引（LSI）112.5小結12第三章 自動歸類系統(tǒng)（ACS）框架設計133.1聚類搜索引擎概述133.2 ACS系統(tǒng)體系結構描述133.2.1搜索引擎用戶界面143.2.2調度中心143.2.3數(shù)據(jù)獲取模塊143.2.4搜索結果重排序模塊153.2.5聚類分析模塊153.2.6聚類結果輸出模塊193.3系統(tǒng)開發(fā)工具和運行環(huán)境193.4 小結19第四章 ACS系統(tǒng)開發(fā)與測試20III4.1 ACS系統(tǒng)設計概述204.2系統(tǒng)詳細設計224.2.1系統(tǒng)過程設計224.2.2系統(tǒng)流程設計224.2.3系統(tǒng)容錯設計254.3系統(tǒng)的實現(xiàn)254.3.1本地接口層次274.3.2查詢處理鏈274.3.3系統(tǒng)的主要協(xié)調類284.3.4添加中文分詞294.4系統(tǒng)聚類結果評測324.5小結33第五章 總結與展望34參考文獻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日，中國互聯(lián)網絡信息中心（CNNIC）發(fā)布了第19次中國互聯(lián)網絡發(fā)展狀況統(tǒng)計報告。根據(jù)報告，用戶經常使用的網絡服務中搜索引擎占51.5%，名列三甲。網民主要使用互聯(lián)網的工具性功能，搜索信息與使用MSN等網上即時通訊成為網民花最多時間的網上活動。搜索引擎現(xiàn)在已成為用戶利用因特網信息資源所不可缺少的工具1。但是現(xiàn)有的搜索引擎并不能很好的滿足用戶的需求。 1.1 研究背景對于用戶提交的檢索要求，現(xiàn)有的搜索引擎（如Google， Yahoo， MSN， 百度）通常是通過計算網頁相關性返回給用戶一長串的結果列表。用戶需要在大量的搜索結果中尋找自己需要的信息，因為搜索結果中各種檢索主題全部混和在一起。這往往給用戶帶來煩惱。例如：用戶在百度中輸入關鍵詞“引擎”，想了解汽車引擎方面的知識。在百度返回的44，600，000篇網頁信息中(查詢于07-05-17)，排在前列的內容基本都是關于“搜索引擎”方面的知識。如果用戶足夠耐心，當他查看排在第100位的網頁時，才會了解到有關“汽車引擎”的內容。所以，在搜索引擎普遍采用相關度排序的今天，用戶將不得不在經歷一系列無關網頁后才會獲取到自己想要的內容。這種檢索方式顯然是存在缺陷的。圖1-13顯示了用戶對現(xiàn)有搜索引擎搜索結果的滿意程度。圖1-1 用戶對搜索引擎結果的困惑程度總得來說，傳統(tǒng)的獨立搜索引擎面臨著以下挑戰(zhàn)：（1） 返回的搜索結果數(shù)量太多。在很多情況下，用戶總要在紛雜的搜索結果中仔細尋找自己想要的搜索結果。（2） 用戶很難對搜索結果進行控制，無法分類查看或限定搜索結果，只能更換關鍵詞重新搜索。（3） 所有的搜索結果都是線性排列，用戶只能逐行地從上往下瀏覽。無法迅速地獲得搜索結果之間的類別關系和重要程度。（4） 搜索結果是按照搜索引擎自身的相關性算法進行排序。然而同一關鍵詞可能指代不同的語義，搜索引擎無法對這些不同的語義差別性地對待。 要解決這些問題，一種組織和控制搜索結果的有效方法是非常必要的，也就是需要在搜索引擎中采用聚類技術，對搜索結果進行聚類處理。搜索引擎結果聚類技術實質上是為了方便用戶的瀏覽，將聚類技術用于Web信息檢索結果的可視化輸出。Web網頁聚類是指將網頁集合分成若干個簇，要求同一簇內網頁所描述的主題內容盡可能地相似，而不同簇間的相似度盡可能地小。搜索引擎結果聚類技術根據(jù)搜索引擎結果所提供的信息（如URLs、標題、摘要等）來歸納出聚類，使得對搜索引擎返回的大量的文檔列表的過濾操作變得方便，這些聚類是搜索引擎返回的文檔集合的高層視圖。在搜索引擎中應用聚類技術，可以有效的組織和控制搜索引擎的搜索結果。經過聚類處理的搜索結果以類目的形式呈現(xiàn)，內容相似的搜索結果被劃分為一個類目，類目之間同時具有包含關系。這樣，搜索結果就被有效的組織起來，用戶可以快速地了解搜索結果的整體分布情況，并快速定位自己需要的搜索結果。例如上述碰到的問題可以通過網頁內容的聚類得到有效的解決或改善。如果把通用搜索引擎返回的搜索結果進行聚類，分成獨立的語義相關的主題，如“搜索引擎”，“圖像引擎”，“游戲引擎”，“汽車引擎”等，那么用戶可以快速的了解搜索引擎返回的結果都包含哪些主題，這樣就可以輕松的獲得自己關心的話題了。同時，我們也注意到自動歸類等一些特性如今也越來越受到用戶的追捧。 圖1-2 不同年齡段的網絡用戶愿意網站跟蹤其行為從而獲得個性化服務的比例Choice Stream在2006的年度調查如圖1-2所示，用戶愿意犧牲部分的網絡隱私，以獲得更個性化的服務。根據(jù)報告8，有79%的用戶很愿意獲取個性化的信息服務，有43%的網絡用戶愿意以個人隱私作為交換，來得到個性化信息服務，對比2005年這個比例有顯著的增長（11%），尤其是在18-34年齡段的人群中，有14%的增幅。在Read/Write Web8今年發(fā)起的一個搜索引擎用戶調查如圖1-3所示，個性化搜索與聚類搜索都獲得了較高的票數(shù)，也證實了個性化搜索是獲得用戶好評的搜索服務。得票數(shù)圖 1-3 最有前景的搜索引擎特性聚類搜索引擎作為新興的搜索引擎，其市場地位仍處于劣勢。但可以看到，國內外各個聚類搜索引擎都在不斷地嘗試各種服務，為用戶提供有別于傳統(tǒng)搜索引擎的差異性服務。目前聚類搜索引擎還處于一個不斷摸索和變化的階段，其營利模式和市場競爭力還有等進一步發(fā)掘。然而，聚類搜索引擎作為整個搜索市場的一股新生力量，正在漸漸打破傳統(tǒng)單一的獨立搜索引擎獨占的市場模式，給用戶帶來更新鮮的搜索體驗，也掀開了搜索引擎市場激烈競爭的冰山一角。1.2 聚類搜索引擎的現(xiàn)狀關于聚類搜索引擎的最早研究始于上個世紀70年代，由O. Zamir和 O. Etzioni等人在1997年第三屆國際知識發(fā)現(xiàn)和數(shù)據(jù)挖掘大會（3rd International Conference on Knowledge Discovery and Data Mining）上提出的4，此后，Oren Zamir等人又進一步論證了將聚類技術應用于搜索引擎的可行性，并開發(fā)了第一個聚類搜索引擎Grouper5。聚類引擎是近幾年才開始實際研究的課題，但很快引起了學術界的重視。自1999年開始，學者們開始以網頁中包含的文字內容為聚類對象，對搜索引擎的聚類算法展開廣泛的研究。在這個過程中，研究的層次不斷深入，從對網頁中分析出的關鍵詞的進行聚類研究，到綜合網頁的語法語義信息對網頁進行實際意義上的聚類。在針對網頁文字內容的聚類算法展開研究的同時，學者們也嘗試著將搜索引擎在搜索中產生的各種相關信息作為聚類對象，對這些信息的聚類算法進行研究。這些相關信息包括用戶輸入的檢索式，用戶對檢索結果的訪問情況，檢索結果網頁之間的鏈接關系等等。國外關于聚類技術在搜索引擎中的應用研究，已經有了較完整的理論體系，并且已經為互聯(lián)網搜索用戶提供聚類搜索服務，比較成熟的商業(yè)用聚類搜索引擎有Vivisimo6、Clusty、iBoogie、Webclust等。目前，聚類搜索引擎已呈現(xiàn)出多元化的發(fā)展方向，例如Grokker與Quintura將聚類結果進行可視化顯示，Infocious將各種信息進行聚類整合，為搜索用戶提供多種搜索服務。Carrot22是一個十分成功的開源聚類搜索引擎開發(fā)框架。它提供了基本的底層接口和一些基本的處理鏈，對一些聚類搜索共用的模塊進行了有效的封裝或者改進。這樣大大提高了研究人員或者開發(fā)工作者試驗新想法、新算法的效率。本系統(tǒng)就是基于Carrot2的開發(fā)框架，成功實現(xiàn)的適合中文環(huán)境的Web搜索結果自動歸類系統(tǒng)。國內對聚類搜索引擎的研究還處于起步階段，目前僅有一家商用的聚類搜索引擎BBMAO，但可以看到業(yè)界逐漸對聚類搜索引擎引起重視，很多學術機構都在研究這個領域，例如北大信息科學學院的Hua-Jun Zeng等人的論文Learning-to-Cluster7提出了聚類引擎就是其中一種解決方案。上海交通大學的APEX實驗室也已發(fā)布一個簡單的聚類搜索引擎。1.3 本文主要內容在本論文中，我們所做的主要工作如下：1 重點研究Carrot2底層的開發(fā)框架，并且根據(jù)實際情況作了大量針對中文語言環(huán)境下有益的改造和改善工作。主要有以下幾個方面：（1） 構建系統(tǒng)底層查詢流程，組織暢通的數(shù)據(jù)流通渠道。特別是在系統(tǒng)的整個開發(fā)框架中，如何保持接口的可擴展性以及高效性，本文作了很大的改進。針對中文應用，在本系統(tǒng)的框架設計上考慮了中文處理的特殊性，特別設計了中文預處理模塊接口，而且成功的應用到了Web搜索結果自動歸類系統(tǒng)中。（2） 添加中文分詞，以適應中文查詢的需求。在Carrot2提供的開發(fā)框架中，并沒有提供中文應用方面的相關支持。而中文分詞對于本系統(tǒng)的成功實現(xiàn)起到關鍵性作用。本文在仔細研究中文分詞的相關技術后，成功地實現(xiàn)了適合中文查詢的Web搜索結果自動歸類系統(tǒng)。2 除了在框架設計，中文分詞上所做的工作以外，還建立了一套適合中文領域的查詢處理流程。本系統(tǒng)的實現(xiàn)流程如圖1-4所示：圖1-4 系統(tǒng)實現(xiàn)流程圖1.4 本文結構安排論文主要探討了描述優(yōu)先的聚類算法，并在Carrot22的開源框架上，構建并實現(xiàn)了適用于中文的Web搜索結果自動歸類系統(tǒng)（ACS）。本文共分為五個章節(jié)，各章節(jié)安排如下：第一章：緒論，涉及問題的提出，并介紹了聚類搜索引擎的研究背景，現(xiàn)狀，以及本文的目的。第二章：網頁自動聚類技術，介紹了研究和開發(fā)網頁自動聚類系統(tǒng)的一些相關知識。第三章：自動歸類系統(tǒng)（ACS）框架設計，討論了Web搜索結果自動歸類系統(tǒng)的體系結構，運用的技術以及系統(tǒng)所涉及的模塊。第四章：ACS系統(tǒng)開發(fā)與測試，本系統(tǒng)成功高效的開發(fā)，得益于Carrot22高可擴展性的框架。第五章：總結與展望，對本系統(tǒng)開發(fā)的一些感想，以及對聚類系統(tǒng)今后發(fā)展趨勢的一些展望。- 5 -Web搜索結果自動歸類系統(tǒng)第二章 網頁自動聚類技術Web搜索結果自動歸類系統(tǒng)通常由以下幾個部分組成：數(shù)據(jù)獲取、數(shù)據(jù)預處理、特征提取和聚類過程，如圖2-1所示。我們首先對聚類系統(tǒng)中涉及的一些概念和技術做一個闡述。圖2-1 檢索自動聚類系統(tǒng)的一般步驟2.1文檔預處理2.1.1預處理步驟Web網頁通常包含有大量的標簽信息、腳本元素等噪音內容，如何在數(shù)據(jù)進行聚類之前把這些數(shù)據(jù)清洗完畢是一個十分關鍵的步驟。一般可以分為以下幾個步驟： （1）去除HTML標簽：javascript等一些腳本元素。（2）去除非字字符：如￥#&。（3）標記標題：在計算詞項權重的時候可以作為參考。（4）頁面語言識別：對采用那一種分詞方法很重要。 下面著重介紹一下中文分詞方法。2.1.2 中文分詞眾所周知，英文是以詞為單位的，詞和詞之間是靠空格隔開，而中文是以漢字為單位，詞與詞之間沒有明顯的形態(tài)界限，要進行漢語的計算機處理，必須首先將漢語的詞與詞分割開，即分詞。句子中所有的字連起來才能描述一個意思。例如，英文句子“It is a stone”，用中文則為：“這是一塊石頭”。計算機可以很簡單通過空格知道“stone”是一個單詞，但是不能很容易明白石、頭兩個字合起來才表示一個詞。如果對“這是一塊石頭”這個句子進行分詞，分詞的結果是：“這是 一塊 石頭”。中文分詞是其他中文信息處理的基礎，自動歸類只是中文分詞的一個應用。目前采用的分詞歸納起來不外乎三大類：基于字符串匹配的分詞方法、基于理解的分詞方法和基于統(tǒng)計的分詞方法。在本系統(tǒng)的實現(xiàn)過程中，我們使用了基于字符串匹配方法，其容易理解，實現(xiàn)也相對簡單。下面僅對該方法做一介紹?；谧址ヅ涞姆椒ɑ谧址ヅ涞姆衷~方法，又叫做機械分詞方法。它是按照一定的策略將待切分的漢字串與機器詞典中的詞條進行匹配，若在詞典中找到某個字符串，則匹配成功（識別）。按照掃描的方向不同，串匹配分詞方法可分為正向匹配分詞方法和逆向匹配分詞方法；按照優(yōu)先匹配的長度不同，又可分為最大匹配分詞方法和最小匹配分詞方法；按照是否與詞性標注過程相結合，又可分為單純分詞方法和結合標注分詞方法。本系統(tǒng)中，采用正向和逆向結合的雙向匹配方法來進行中文分詞。2.2向量空間模型（VSM）向量空間模型（Vector Space Model, VSM）是目前信息檢索中最常用的文檔表示模型。在萬維網信息檢索方面，向量空間模型比布爾模型等傳統(tǒng)模型更適合。這是因為布爾模型是最簡單的檢索模型，標準的布爾模型是二元邏輯，所檢索的頁面要么與所鍵入的關鍵詞組有關，要么無關，檢索結果一般不進行相關性排序；而向量空間模型不僅可以方便地產生有效的檢索結果，而且能夠提供相關頁面的文摘，并進行檢索結果分類，為用戶提供準確的所需信息?；谙蛄靠臻g模型的信息檢索一般過程如下21：（1）將各個文檔和查詢都表示為向量；（2）計算查詢與各個文檔之間的相似度；（3）按照查詢與各個文檔之間的相似度對相關的文檔進行排序；（4）將排序后的文檔以線性列表的形式返回給用戶 在向量空間模型中，各個文本和查詢項的內容都表示為向量。設共有個文檔，對所有文本進行詞語切分、過濾和轉換之后，合適的個詞項（Term）被提取出來，構造的詞項/文檔關系矩陣（Term-Document Matrix），矩陣中的元素表示第- 51 -Web搜索結果自動歸類系統(tǒng)個詞項在第個文檔中的權重（Weight）。這樣，每個詞項就可以用W中對應的行向量來表示。 應用上述方法，文本被表示為一組有代表性的詞項（Term，索引項）的集合。通常需要提取待處理文本集合中含有的所有索引項。設索引項的集合，其中表示文本集合中含有的索引項的個數(shù)，實際使用中都是隨著文本集合的不斷變化而增加的。通常都是在預處理以后，只保留文檔中最具有明顯標志性作用的索引項。對初始文檔，其中是文檔含有的索引項的數(shù)目，經過預處理以后其中，預處理可以很好的減小計算量。向量空間模型通過分配權重給文檔中的索引項，將文檔表示為權重的向量，其中表示索引項在文檔中的權重。的計算采用TFIDF加權策略，具體的計算公式可以表示為： （2-1）其中表示詞在文檔中出現(xiàn)的次數(shù)，表示要處理的文檔的個數(shù)， 表示含有詞的文檔個數(shù)。這種權重計算方式中的大小與在文檔中出現(xiàn)的次數(shù)成正比，而與在整個文本集合中出現(xiàn)的次數(shù)成反比。此外，對的計算還有許多形式，在此不一一列舉。在檢索時也需要將查詢表示成權重的向量以計算查詢與文檔的相似度。查詢表示為。相似度的計算公式表示為： （2-2）這種相似度計算是通過考察特征向量的余弦夾角實現(xiàn)的。2.3描述優(yōu)先的聚類算法俗語有云：“物以類聚，人以群分。”聚類就是利用計算機技術來實現(xiàn)這一目的的一種技術，其輸入是一組未分類的記錄，且事先不知道如何分類，也可能不知道要分成幾類，通過分析數(shù)據(jù)，合理劃分記錄集合，確定每個記錄所屬的類別，把相似性大的對象聚集為一個簇。聚類的標準是使簇內相似度盡可能大、簇間相似度盡可能小。聚類屬于無監(jiān)督學習，由于數(shù)據(jù)密度分布、聚類規(guī)則、處理數(shù)據(jù)量等的多樣性，從而產生了許多種聚類算法。聚類算法可以分為劃分聚類、層次聚類、密度型聚類、網格型聚類和其他幾種聚類算法910。而本系統(tǒng)采用的Lingo算法與上述幾種聚類算法有所不同，Lingo算法采取的是描述優(yōu)先的策略來達到最終標簽的可理解性。我們可以通過圖2-2很清晰的看出描述優(yōu)先的聚類算法和傳統(tǒng)聚類算法的區(qū)別。圖2-2 傳統(tǒng)聚類（左）和描述優(yōu)先聚類（右）的比較在本節(jié)中，將介紹在信息檢索領域，傳統(tǒng)的文檔聚類算法和描述優(yōu)先的聚類算法有哪些區(qū)別。下面我們主要從需求和文檔遍歷方式上來進行分析。聚類的一般定義如下：11給定一定數(shù)量的對象或個體，并且每個個體都用一定的數(shù)學方法來表示，按照一定分類規(guī)則，把這些對象分入一定的類內，使得類內的對象盡可能的相似，類間的對象差別盡可能的大。類的數(shù)目和各個類的表示需要自行定義。上面的定義沒有涉及有關類標簽的問題，而其目的只是去發(fā)現(xiàn)擁有相似對象的類。如果應用程序需要把聚類的結果呈現(xiàn)給用戶，則需要找到合適的文字去描述相應的類，而這個問題在定義中是沒有提到的。一個好的算法（根據(jù)定義）如果它沒法去解釋類里面包含的內容，那么對用戶來說可能根本沒用。所以最核心的問題是如何從發(fā)現(xiàn)類聚主題的算法轉移到更好的類聚描述的方法。比如，在VSM模型中，想從這個“詞袋”模型中構建聚類標簽來表示得到的類，似乎不太可能。同時，用關鍵詞或者頻繁出現(xiàn)的短語來表示類標簽，并不能很好的滿足應用程序的需求。 鑒于以上問題，Dweiss在他的博士論文11中提出了一種描述優(yōu)先的算法。其著重類標簽的表達。以下是他的定義：描述優(yōu)先的聚類算法是一種可以用有意義的，可理解的，精簡的文字標簽來表示的語義相關的不同的類。根據(jù)以上定義，一個描述優(yōu)先的聚類結果應該有清晰的，可理解的標簽描述的類。所以，文檔內容聚類是一個起決定性作用的步驟，但并不是我們的最終目標。綜上，我們可以放棄那些沒有辦法用有意義標簽來描述的類。可能一開始還感到疑惑，但是在Dweiss的實驗中11，可以充分印證這個思想的合理性：（1）如果標簽表達不清晰，用戶不會花額外的時間來弄明白一個標簽的意思。（2）如果標簽只是一個單獨的關鍵詞，用戶將不會查看該類里面的文檔。（3）類描述和類內的文檔，如果不清晰或者關系模糊，將使用戶失去信心。在本系統(tǒng)中采用的Lingo算法13就是一個描述優(yōu)先的算法，最終聚類標簽的可理解性是我們一個十分重要的目標。2.4 Lingo聚類算法本系統(tǒng)實現(xiàn)并使用了Lingo（Label INduction Grouping algOrithm）和STC（Suffix tree clustering）算法。在Lingo算法中應用了標簽優(yōu)先聚類算法的思想，并在文中詳細討論了算法的流程和實現(xiàn)步驟。由于篇幅，這里不介紹STC聚類算法12。本文通過實現(xiàn)這兩種算法，構建Web搜索結果自動歸類系統(tǒng)，進一步了解聚類搜索引擎的工作原理，以及采用Lingo算法的優(yōu)勢。在Lingo中，需要兩個很重要的步驟。一個是用后綴數(shù)組提取共現(xiàn)頻繁短語，這是提取候選標簽的基礎。另一個是LSI方法，我們前面介紹了構建VSM的方法，而LSI方法就是基于VSM的，并在計算了TF-IDF權重之后，用SVD（奇異值分解）進行矩陣分解，使矩陣的維數(shù)進一步降低，有利于主題的聚類。下面將詳細介紹后綴數(shù)組和LSI。2.4.1后綴數(shù)組（Suffix Arrays）后綴數(shù)組的概念定義12定義1： 對于字符串，定義的長度為，第個字符為，第個字符至第個字符組成的子串為。構成字符串的字符集。定義2：的，即的前個字符組成的字符串，如果，則其。定義3： 按所有后綴字符串的排序的后綴數(shù)組為，相應的名次數(shù)組為13 。后綴數(shù)組（suffix array）是字符串處理應用中使用的各種數(shù)據(jù)結構的基礎。表示在字符集上的一個字符串，$ 是唯一的終結符且小于字符集中的任一字符，是在字符串的末尾加上終結符得到的一個新字符串，如果表示字符串的長度，表示S的第個字符，那么是字符串的第個后綴數(shù)組。例如：，在其后增加一個結束符，得到，那么，是的第2個后綴數(shù)組。2.4.2潛在語義索引（LSI）在Web上對某個特定領域的信息進行采集，首先需要讓采集系統(tǒng)了解這個領域的精確描述。通常是給定一個樣本文檔集合，采用合適的代數(shù)模型進行描述。傳統(tǒng)的檢索模型描述中16，無論布爾模型，向量空間模型（Vector Space Model，VSM) 還是概率模型，盡管實現(xiàn)方法上有很多差異，但對文本的過濾、檢索等操作都是通過文檔之間的詞匹配來實現(xiàn)的。由于詞具有同義性，多義性和使用上的概念相關性，僅僅通過字面的匹配不能準確地進行各種功能操作。從1988年開，Dumais等進行了一系列的研究，提出了新的信息檢索代數(shù)模型，主要是為克服現(xiàn)有的查詢詞與文檔匹配檢索技術的缺點而設計的。在VSM基礎上，利用線性代數(shù)的知識，通過矩陣的奇異值分解(Singular Value Decomposition，SVD) 來進行潛在語義索引，簡稱為LSI(Latent Semantic Indexing)或者LSA(Latent Semantic Analysis)。LSI通過數(shù)學分析，計算出文檔集合中潛在內涵的概念之間的關系，通過潛在概念集表示所有的概念空間，減少了概念表示之間的模糊性，避免了VSM中各維之間概念正交的假設。它把觀測到詞項/文檔關聯(lián)數(shù)據(jù)的不可靠性看作是一種統(tǒng)計問題，認為在數(shù)據(jù)中存在一種潛在的語義結構，這種結構由于檢索詞出現(xiàn)的多樣性被干擾。LSI使用統(tǒng)計技術去估計這些潛在的語義結構，去掉這種“噪聲”。針對一些TREC文檔庫的實驗結果及一些初步的理論分析，證實了LSI的優(yōu)越性24。通過特定領域樣本文檔集LSI矩陣，獲得樣本集潛在語義的矩陣描述，可以很好地計算文檔之間潛在內容的相關性，是目前在信息檢索領域最具有前景的發(fā)展方向之一。與傳統(tǒng)的信息檢索代數(shù)模型相比，LSI具有如下優(yōu)點15：(1) 表示的不僅僅是所有標引詞的簡單出現(xiàn)頻度和分布關系，而是所有標引詞在樣本文檔集合中的潛在語義關系，通過對樣本文檔集合的文檔操作，語義精度得到較大的提高。(2) 采用一個低秩近似矩陣替代了詞項/文檔矩陣，存儲計算效率上得到較大的提高。(3) 不僅表示了標引詞和文檔之間的關系，而且包含了不同詞之間的潛在關系，可以表示標引詞之間，文檔之間，標引詞與文檔之間，查詢偽文本和文檔之間的各種相似度，使用上更加靈活。LSI模型的主要問題是從高維映射到低維時如何確定值16，目前還沒有理論上合適的方法。一方面希望足夠大，能夠適合所有的潛在語義結構，但太大會導致噪聲，對于LSI使用產生影響;如果太小，則不能適應樣本的誤差或其他次要的細節(jié)，保留下來的結構太少，無法把握運算的結果。實際中，往往需要通過多次的試驗，以選取針對具體文檔集合操作效率最好的值。對于非常大的文檔集，取100300比較適合16。中文文檔集合LSI初步測試基本吻合英文的取值范圍。2.5小結本章介紹了一系列網頁自動聚類技術，其中包含預處理，中文分詞，向量空間模型。在介紹聚類算法的同時，著重介紹了描述優(yōu)先的聚類算法。本系統(tǒng)采用的Lingo聚類算法就采用了描述優(yōu)先的聚類思想。為了更加直接、簡明的了解Lingo聚類算法的運作原理，在本章中我們通過簡化文檔，描述了Lingo聚類處理的整個流程。下一章，將詳細介紹ACS系統(tǒng)的體系結構以及開發(fā)該系統(tǒng)所需要的相關技術。第三章 自動歸類系統(tǒng)（ACS）框架設計第三章 自動歸類系統(tǒng)（ACS）框架設計聚類搜索引擎是搜索引擎的一種，它用關鍵詞從傳統(tǒng)的獨立搜索引擎中獲取搜索結果列表，通過對搜索結果進行聚類處理后，將二次加工后的搜索結果和聚類類目呈現(xiàn)給用戶。一般而言，聚類搜索引擎是元搜索引擎，它本身并不對網絡文檔進行爬行和索引，而只是利用接口向各個獨立搜索引擎發(fā)出關鍵字檢索請求，對請求得到的搜索結果進行聚類處理。但也有極少數(shù)聚類搜索引擎建立有自己的網頁索引庫，例如 Northern Light 聚類搜索引擎，同樣具備有爬行器和網頁索引數(shù)據(jù)庫，用戶提交關鍵字搜索時只在自己的索引數(shù)據(jù)庫中進行檢索。本系統(tǒng)就是一個聚類搜索引擎，本章主要講述ACS(Automatic Categorization System)的框架設計，應用的技術以及各個模塊的內涵。3.1聚類搜索引擎概述聚類搜索引擎13自動將來自各個搜索引擎的搜索結果，自動組織成各種類(Cluster)，統(tǒng)一呈現(xiàn)給搜索用戶。這種聚類技術是實時進行，聚類過程中沒有人工干預，因而不同于分類(Classification)和標引(Tagging)。此外，由于聚類搜索引擎將搜索結果分為各個類目，其類名的選取非常重要，它為用戶指示了此類的核心內容。類名的選取需要遵循簡潔、可理解、準確、唯一性的特點。聚類搜索引擎由于對海量的搜索結果進行了聚類處理，使得搜索結果具有目錄式的分類，用戶可以方便快捷地找到自己的目標信息，即對應類下的搜索結果，而免去在無數(shù)的搜索結果中進行甄別、篩選、過濾等人工辨別。3.2 ACS系統(tǒng)體系結構描述絕大多數(shù)聚類搜索引擎屬于元搜索引擎，圖3-1是聚類搜索引擎的體系結構13，可以看到，其工作原理與元搜索引擎有不少相似之處。聚類結果輸出調度中心數(shù)據(jù)獲取模塊GoogleYahoo!MSN百度獨立搜索引擎搜索結果重排序聚類分析搜索引擎用戶界面 圖3-1聚類搜索引擎的體系結構3.2.1搜索引擎用戶界面該模塊負責與用戶進行交互，它接收用戶的查詢請求，以及用戶檢索偏好，例如選擇的獨立搜索引擎對象，返回的搜索結果數(shù)量等。同時，該模塊還將聚類處理后的最終結果以統(tǒng)一的格式返回給用戶。3.2.2調度中心調度中心是聚類搜索引擎一個核心的調度模塊，負責接受用戶的檢索請求傳遞到數(shù)據(jù)獲取模塊，并將其返回的數(shù)據(jù)處理后，傳遞給搜索結果重排序模塊。在本系統(tǒng)中，在原有Carrot22提供的控制接口上，實現(xiàn)了整個處理流程的控制，并成功的組織調用相關組件，保證數(shù)據(jù)流的通暢。3.2.3數(shù)據(jù)獲取模塊數(shù)據(jù)獲取模塊負責與各個獨立搜索引擎的交互，包括多個搜索引擎的接口代理，它們把用戶的查詢轉換成對應搜索引擎能夠辨識的格式分別發(fā)送，并負責解析對應搜索引擎返回的搜索結果，并將解析過的搜索結果傳遞給調度中心。數(shù)據(jù)獲取模塊往往采用多線程(Multithreading)的方式作并行地在各個獨立搜索引擎中進行搜索，并行地調用多個搜索引擎。并且對于每個獨立搜索引擎，數(shù)據(jù)獲取模塊通過多個線程并行地取回其搜索結果網頁。只有這樣采用并行線程，才能更快地獲取足夠多的搜索結果。在本系統(tǒng)中，我們只實現(xiàn)了從Yahoo搜索引擎獲取數(shù)據(jù)，關于對其他搜索引擎數(shù)據(jù)的獲取，將在以后的改進階段實現(xiàn)。3.2.4搜索結果重排序模塊搜索結果重排序模塊負責對數(shù)據(jù)獲取模塊傳遞過來的各個搜索結果列表，進行網頁去重和搜索結果重排序。由于本系統(tǒng)如今只實現(xiàn)了從Yahoo接口獲取數(shù)據(jù)，故并沒有涉及結果重排序模塊，若以后從多個搜索引擎獲取結果，則需在系統(tǒng)中加入此步驟。下面對重排序做一簡單介紹：對于相同的搜索關鍵字，不同搜索引擎的返回結果均不相同，并且彼此的搜索結果中會有重復之處。搜索結果重排序模塊需要把來自各個搜索引擎的搜索結果列表綜合起來，去重后，重新排序形成一個統(tǒng)一的搜索結果列表。一種簡單有效的重排序算法是最高位置算法(Highest-Rank Algorithm) 21，下面簡要描述這一算法。對各個獨立搜索引擎返回的每一項搜索結果進行檢查，以它在各個搜索引擎返回的搜索結果列表中出現(xiàn)的最高位置作為它的序號，并刪除它在其它位置的出現(xiàn)，直到各個搜索結果列表都沒有重復的搜索結果為止，然后將所有的搜索結果按照其序號順序排列成為一個統(tǒng)一的列表。對于相同序號的搜索結果，可以根據(jù)其最高位置所在的搜索引擎的優(yōu)劣質量順序排序18。3.2.5聚類分析模塊在這個模塊中，聚類搜索引擎要完成數(shù)據(jù)清理和聚類處理處理過程。（1）數(shù)據(jù)清理：各個搜索引擎的搜索結果中一般包括相關頁面的標題、摘要和目標URL地址。數(shù)據(jù)清理過程便是將搜索結果頁面的各部分內容進行清理，合并成一個文檔內容，來表示搜索結果頁面內容。在這個過程中，聚類處理模塊對搜索引擎返回的搜索結果網頁進行解析，去除其中的HTML標簽，并以標點符號、空格等為邊界把網頁切分成多個較短的字符串。然后用中文分詞處理將之表示成一個短語序列，為關鍵詞組提取作好準備。（2）聚類分析：接下來，對所有的搜索結果文檔(短語序列)，使用Lingo聚類算法13進行處理。在數(shù)據(jù)預處理之后，我們先提取網頁中的候選標簽，這需要使用到后綴數(shù)組。然后通過潛在語義索引(LSI)，分解矩陣，確立網頁的主題分類。最后通過選取合適的標簽，并把文檔重新歸類到相應的標簽底下。這樣就完成了聚類分析過程。對文檔完成聚類后，再對生成的聚類類目進行排序，一般對聚類類目的排序采用最大類別優(yōu)先的策略，即按照包含的結果文檔數(shù)從大到小排序。下面對ACS系統(tǒng)采用的聚類算法Lingo進行詳細描述：Lingo算法的大致流程如圖3-2所示13。圖3-2 Lingo算法的流程在ACS系統(tǒng)中，Lingo是默認的聚類算法。所以這里用一個小例子來解釋一下Lingo是如何運作的。圖3-3 詞項/文檔矩陣文檔矩陣如圖3-3左所示，是一個以詞項為行向量，文檔為列向量的一個矩陣。為了建立VSM模型，我們需要建立一個詞項/文檔矩陣：一個包含所有出現(xiàn)在輸入文檔中詞項頻度的矩陣。假設，如果只有2個詞項，詞項和詞項。這樣就可以方便的把VSM模型可視化為二維平面。平面的每一個點代表一個文檔。圖3-4 詞項/文檔矩陣矩陣分解的任務是通常把一個矩陣分解為兩個矩陣，而這兩個矩陣的叉積盡可能的與原始矩陣相似，并且具有更低的維數(shù)。其中，左矩陣可以看作是低維空間的基向量，而另一個矩陣可以看作是我們重建原始矩陣的一個系數(shù)。在圖3-4中，基向量大致刻畫了輸入集合中的主要走勢。圖3-5 候選標簽選取在圖3-5中，請注意，頻繁短語和基向量都表示在同一個向量空間中（輸入文檔矩陣）。所以這里可以通過余弦值找到適合每個基向量的最相似的頻繁短語。這樣，每個基向量都將找到一個聚簇標簽。圖3-6 聚簇標簽的選定和內容聚類為了形成合適的聚簇，我們可以再次通過利用余弦值相似度方法，把大于一定值的文檔賦給合適的標簽即可，如圖3-6所示。到此為止，聚類已經成功完成，只要組織輸出即可。3.2.6聚類結果輸出模塊該模塊將經過聚類處理的各搜索結果網頁，以聚類搜索引擎本身采用的統(tǒng)一格式進行處理。一般獨立搜索引擎的搜索結果中，都包括對目標網頁的標題描述、網頁摘要、URL目標地址、網頁獲取時間等。這一模塊分析各個獨立搜索引擎結果的格式，對其內容進行處理，統(tǒng)一表述成自己的搜索結果顯示方式。此外，此模塊還可以在格式化后的搜索結果中，加入有自身特色的數(shù)據(jù)。例如結果數(shù)據(jù)的搜索引擎來源，在不同搜索引擎中的排列序號等等。在本系統(tǒng)中，還可以查看每個網頁文檔屬于的類。3.3系統(tǒng)開發(fā)工具和運行環(huán)境（1）開發(fā)工具：Eclipse + Tomcat（2）版本管理工具： CVS（3）測試工具： JUnit （4）基于平臺： Windows（5）相關資源：Yahoo API,Log4j日志工具，緩存管理工具Ehcache等3.4 小結本章詳細介紹了Web搜索結果自動歸類系統(tǒng)的整個框架設計，并把系統(tǒng)分為六大部分，分別是搜索引擎用戶界面，調度中心，數(shù)據(jù)獲取模塊，搜索結果重排序模塊，聚類處理模塊和聚類結果輸出模塊。其中由于現(xiàn)在我們只從單一的搜索引擎抓取數(shù)據(jù)（Yahoo），所以在實際的開發(fā)過程中，搜索結果重排序模塊并沒有使用到。Web搜索結果自動歸類系統(tǒng)第四章 ACS系統(tǒng)開發(fā)與測試ACS(Automatic Categorization System)系統(tǒng)的設計目標是設計在線的，根據(jù)內容分類的，更好地滿足用戶需要的中文網頁自動歸類系統(tǒng)。在線是指即時響應用戶的聚類要求，迅速提供最新的聚類結果。根據(jù)內容分類的，指聚類的結果是經過分門別類之后，展現(xiàn)給用戶的。類與類之間應該允許重疊，即若信息涉及多個類的主題則可以屬于多個類，并且采用樹的組織形式，樹中每個結點都對應一個類。下面通過介紹系統(tǒng)的設計、開發(fā)、測試來了解ACS系統(tǒng)的實現(xiàn)過程。4.1 ACS系統(tǒng)設計概述 圖4-1 ACS系統(tǒng)查詢界面本系統(tǒng)的設計本著為用戶著想的目的，為用戶提供一個輸入查詢詞的界面，如圖4-1所示，并且可以選擇從搜索引擎獲取多少數(shù)據(jù)量(現(xiàn)在備選的有50，100，200，400，默認100)，還可以根據(jù)愛好，選擇相應的算法(現(xiàn)在實現(xiàn)的有Lingo和STC，默認為Lingo)。聚類后的結果用目錄結構展現(xiàn)給用戶，如圖4-2所示，用戶可以方便的選擇相應的主題目錄進行瀏覽。 圖4-2 聚類結果輸出界面 下面7點是我們系統(tǒng)開發(fā)的范圍和目標：(1) Web搜索引擎返回的頁面是動態(tài)的，其文檔類別是未知的、不固定的。這也是通用搜索引擎的一個特性，我們針對這個情況采取相應的辦法，使得文檔最終可以分 類后展現(xiàn)給用戶。(2) 根據(jù)頁面內容自身的差異，使用文檔聚類