基于獨(dú)立用戶的聚類(lèi)搜索引擎論文

畢業(yè)論文第1.緒論 11.1研究背景 11.2研究概況 21.3本文結(jié)構(gòu) 32.搜索引擎概述 52.1搜索引擎的組成 52.1.1Robot 52.1.2分析器 62.1.3索引器 62.1.4檢索器 62.1.5用戶接口 72.2搜索引擎工作流程 72.3搜索引擎分類(lèi) 82.3.1全文搜索引擎 82.3.2目錄索引搜索引擎 92.3.3垂直搜索引擎 102.3.4元搜索引擎 113.聚類(lèi)研究 133.1文檔自動(dòng)分類(lèi) 133.2聚類(lèi)分析 133.3基本聚類(lèi)方法 143.3.1平面劃分方法 143.3.2層次凝聚方法 163.4網(wǎng)頁(yè)聚類(lèi)算法 193.4.1基于網(wǎng)頁(yè)內(nèi)容的聚類(lèi)算法 193.4.2基于鏈接分析的聚類(lèi)算法 203.4.3基于用戶搜索日志的聚類(lèi)算法 214.聚類(lèi)搜索引擎設(shè)計(jì) 234.1數(shù)據(jù)源預(yù)處理 234.2索引的建立 244.3相似度計(jì)算 284.4聚類(lèi)處理 295.性能分析 355.1理論分析 355.2系統(tǒng)演示 36總結(jié) 39致謝 41參考文獻(xiàn) 431.緒論1.1研究背景萬(wàn)維網(wǎng)(WorldWideWeb,簡(jiǎn)稱(chēng)WWW或Web)是為廣大用戶交換或共享信息而發(fā)展起來(lái)的一種因特網(wǎng)(Internet)應(yīng)用，從1991年出現(xiàn)以來(lái)，經(jīng)過(guò)短短十幾年已經(jīng)發(fā)展成為一個(gè)巨大的全球化信息空間。面對(duì)這一龐大的信息資源，用戶迫切需要一個(gè)強(qiáng)有力的檢索系統(tǒng)快速有效地檢索Web信息，以使從浩如煙海的信息中找到自己所需的信息。搜索引擎是Web信息檢索服務(wù)的一種形式，從1993年年底第一個(gè)搜索引擎WWWW(WorldWideWebWorm)在Colorado大學(xué)開(kāi)發(fā)成功以來(lái)，經(jīng)過(guò)發(fā)展，因特網(wǎng)上的搜索引擎己經(jīng)達(dá)到上千個(gè)，而包括搜索引擎在內(nèi)的信息檢索也已成為僅次于電子郵件的第二大網(wǎng)絡(luò)應(yīng)用。根據(jù)CNNIC最新的統(tǒng)計(jì)報(bào)告數(shù)據(jù)顯示，我國(guó)近70%萬(wàn)的網(wǎng)民經(jīng)常使用搜索引擎。由于搜索引擎本身具有極大的商業(yè)價(jià)值，所以以盈利為目的搜索引擎服務(wù)提供商在這個(gè)領(lǐng)域爭(zhēng)相投入大量的資源進(jìn)行研究。而除了通用搜索引擎之外，細(xì)分搜索公司的增多，也驗(yàn)證了搜索市場(chǎng)生態(tài)的繁榮，并為搜索引擎的進(jìn)一步發(fā)展找到了新出路，比如：大量垂直搜索的涌出。垂直搜索的用戶特定性，可以有針對(duì)各個(gè)行業(yè)的垂直搜索引擎，有很大的發(fā)展空間。首先，因?yàn)榇怪彼阉鲗?duì)數(shù)據(jù)源進(jìn)行了更詳細(xì)的劃分和更人性化、智能化的操作，比如自動(dòng)分類(lèi)、自動(dòng)聚類(lèi)、個(gè)性化專(zhuān)題等，并將其通過(guò)簡(jiǎn)單易用、搜索結(jié)果精確分類(lèi)等方式表現(xiàn)出來(lái)，并可采用按效果付費(fèi)的廣告模式HYPERLINK[1]，這就超越了傳統(tǒng)搜索廣告點(diǎn)擊付費(fèi)的單一廣告方式。其次，垂直搜索能夠提供更為集中的受眾群體，其中大部分是潛在消費(fèi)者或產(chǎn)品使用者，從而提高搜索引擎廣告受眾的精確度，這是一般的通用搜索做不到的。雖然搜索引擎的系統(tǒng)種類(lèi)繁多，功能服務(wù)特點(diǎn)各異，但是在這個(gè)領(lǐng)域仍然有很多的問(wèn)題亟待解決：首先，盡管現(xiàn)有的搜索引擎采用了多種方法來(lái)提高檢索結(jié)果的精度，用戶從搜索引擎搜索到的結(jié)果中仍然存在大量無(wú)效信息。有統(tǒng)計(jì)標(biāo)明，對(duì)現(xiàn)有的20個(gè)流行的搜索引擎的前200個(gè)返回結(jié)果進(jìn)行的2000次檢索測(cè)試和統(tǒng)計(jì)，其搜索結(jié)果中用戶根本無(wú)法連通的鏈接約占30%，重復(fù)內(nèi)容約占12%，與用戶需求不相關(guān)的內(nèi)容約占8%，與用戶需求相關(guān)但不完全符合用戶需求的約占36%，而完全符合用戶需求的僅占14%，搜索引擎雖然經(jīng)過(guò)了相關(guān)度排序，然而相關(guān)文檔和不相關(guān)文檔相互混雜，用戶必須逐個(gè)瀏覽結(jié)果列表以找到相關(guān)文檔，花費(fèi)了大量的精力，當(dāng)返回的結(jié)果數(shù)目眾多時(shí)，這個(gè)問(wèn)題更為突出，即使搜索引擎找到了用戶所期望的結(jié)果，無(wú)法快速地定位自己所需資源，甚至有許多屬于同一類(lèi)型、同一方面的無(wú)效信息返回，這些問(wèn)題致使一些搜索引擎的檢索質(zhì)量大大降低，成為了今天搜索引擎迫切需要解決的問(wèn)題之一。1.2研究概況搜索引擎發(fā)展到今天,無(wú)論從產(chǎn)業(yè)角度還是從產(chǎn)品角度來(lái)看,都成為計(jì)算機(jī)領(lǐng)域的一個(gè)重要研究方向，創(chuàng)造了一個(gè)又一個(gè)互聯(lián)網(wǎng)亮點(diǎn)。眾多搜索引擎有著不同的信息搜集方法和服務(wù)提供方式，如：Baidu、Google所采用的全文檢索搜索引擎；Yahoo、LookSmart所采用的目錄式搜索引擎；以及LookSmart、WebCrawler所采用的元搜索引擎。其中Google以搜索精度高、速度快成為最受歡迎的搜索引擎?；ヂ?lián)網(wǎng)的普及，使用搜索引擎的用戶多樣化，覆蓋各個(gè)行業(yè)領(lǐng)域，各個(gè)年齡階段，其需求也呈現(xiàn)多樣化。大多數(shù)搜索引擎目前仍然采用通用式的搜索方式，即針對(duì)同一關(guān)鍵詞進(jìn)行的查詢(xún)，搜索引擎會(huì)對(duì)不同用戶給出相同結(jié)果。這種模式以網(wǎng)頁(yè)的加權(quán)評(píng)價(jià)為核心，而并非以用戶為核心，并不能滿足不同用戶的不同需求。針對(duì)某一特定行業(yè)的專(zhuān)業(yè)搜索，即垂直搜索的出現(xiàn)在一定程度上填補(bǔ)了這一需求缺口，但其覆蓋范圍有限，搜索信息有限，用戶群體有限?，F(xiàn)在大多數(shù)的搜索引擎以搜索文字信息為主，隨著網(wǎng)絡(luò)帶寬的不斷加大，多媒體信息在網(wǎng)上迅速增加，這就對(duì)多媒體信息的檢索提出了要求。多媒體信息檢索主要是指基于音頻的檢索、基于圖片的靜態(tài)圖像檢索和基于視穎的動(dòng)態(tài)圖像檢索，現(xiàn)在研究得較多的是圖像檢索。然而這些搜索引擎還存在很大局限性，并不能完全解決互聯(lián)網(wǎng)信息檢索的問(wèn)題。搜索引擎不能搜索整個(gè)互聯(lián)網(wǎng)、正確率非常低、召回率(返回的相關(guān)文檔占所有相關(guān)文檔的比率)和準(zhǔn)確率(返回的相關(guān)文檔占返回的所有文檔的比率)都非常低。搜索引擎面對(duì)的挑戰(zhàn)主要表現(xiàn)在以下幾個(gè)方面：1.網(wǎng)絡(luò)資源的發(fā)展，使得搜索引擎能夠檢索的范圍越來(lái)越??；2.互聯(lián)網(wǎng)是一個(gè)動(dòng)態(tài)增長(zhǎng)的信息源，隨時(shí)會(huì)發(fā)生各種變化，搜索引擎不能及時(shí)反映這種變化；3.對(duì)于用戶來(lái)說(shuō)，用戶檢索到的結(jié)果與用戶所需要的信息相比，用戶檢索到的有用信息經(jīng)常淹沒(méi)在眾多的無(wú)用信息當(dāng)中HYPERLINK[2]。為了緩解上述問(wèn)題，各大搜索引擎開(kāi)發(fā)商不斷采用更好的技術(shù)，提高產(chǎn)品性能；其中，Robot(機(jī)器人)技術(shù)是國(guó)內(nèi)外關(guān)于搜索引擎采用的較好技術(shù)之一，即由一種叫“蜘蛛”的計(jì)算機(jī)程序在網(wǎng)絡(luò)中爬行，并發(fā)現(xiàn)、加工、整理信息，為用戶提供檢索服務(wù)；部分中文搜索采用目錄式搜索引擎（DirectorySearchEngine），即通過(guò)人工發(fā)現(xiàn)信息并依靠編目員的知識(shí)進(jìn)行分類(lèi)；前者獲得的信息量較大，耗費(fèi)資源較少，后者精確度較高。而元搜索引擎沒(méi)有自己的數(shù)據(jù)，是將用戶的查詢(xún)請(qǐng)求同時(shí)向多個(gè)搜索引擎遞交，將返回的結(jié)果進(jìn)行重復(fù)排除、重新排序等處理后，作為自己的結(jié)果返回給用戶；其服務(wù)方式為面向網(wǎng)頁(yè)的全文檢索。這類(lèi)搜索引擎的優(yōu)點(diǎn)是返回結(jié)果的信息量更大、更全，缺點(diǎn)是不能夠充分使用所使用搜索引擎的功能，用戶需要做更多的篩選。近年來(lái)，聚類(lèi)技術(shù)也在搜索引擎中逐漸運(yùn)用。在搜索引擎結(jié)果的聚類(lèi)研究中，聚類(lèi)實(shí)現(xiàn)技術(shù)大致可分為兩種：一種是事先聚類(lèi)，檢索前預(yù)先對(duì)文檔集進(jìn)行聚類(lèi)。由于這一聚類(lèi)處理的文檔集巨大，所以對(duì)計(jì)算資源要求較高，多為脫機(jī)處理。另一種是事后聚類(lèi)，對(duì)檢索結(jié)果進(jìn)行聚類(lèi)。由于事后聚類(lèi)處理的文檔集較小，所以可實(shí)現(xiàn)聯(lián)機(jī)處理。Web信息資源是時(shí)刻動(dòng)態(tài)增加變化的，提前將文檔進(jìn)行聚類(lèi)分類(lèi)，不能滿足信息及時(shí)更新的需求，且處理的文檔集巨大對(duì)計(jì)算資源要求較高，代價(jià)較大，所以將檢索結(jié)果進(jìn)行聚類(lèi)的技術(shù)更加能夠滿足Web信息靈活多變的需要。從老牌聚類(lèi)搜索引擎Vivisimo，到2003年剛剛問(wèn)世的，十分被人們看好的聚類(lèi)搜索引擎Mooter，國(guó)外聚類(lèi)搜索引擎正在蓬勃發(fā)展；當(dāng)前國(guó)內(nèi)也出現(xiàn)了比比貓等優(yōu)秀的中文聚類(lèi)搜索引擎，可見(jiàn)將聚類(lèi)技術(shù)應(yīng)用于搜索引擎是大勢(shì)所趨。1.3本文結(jié)構(gòu)本文的研究目標(biāo)是希望通過(guò)有效的聚類(lèi)分析，對(duì)現(xiàn)有的搜索引擎進(jìn)行優(yōu)化，將大規(guī)模中文網(wǎng)頁(yè)集合進(jìn)行層次結(jié)構(gòu)的聚集和管理，便于瀏覽檢索和進(jìn)一步分析，使用戶可以更快定位自己所需結(jié)果集，縮小選擇范圍，提高用戶搜索效率。本文結(jié)構(gòu)如下：第一章緒論簡(jiǎn)單介紹了當(dāng)前搜索引擎的發(fā)展?fàn)顩r及趨勢(shì)；第二章搜索引擎概述對(duì)幾種主要的搜索引擎的工作流程及原理進(jìn)行了介紹；第三章聚類(lèi)研究詳細(xì)闡述了主要的聚類(lèi)算法及設(shè)計(jì)中所用到的思想；第四章聚類(lèi)搜索引擎設(shè)計(jì) 詳細(xì)闡述了本文聚類(lèi)搜索引擎的整體設(shè)計(jì)；第五章性能分析對(duì)本聚類(lèi)搜索引擎的性能展開(kāi)分析；最后總結(jié)全文，概述本文的主要工作及價(jià)值，并分析了相關(guān)不足和以后的研究方向。搜索引擎概述2.1搜索引擎的組成自從第一個(gè)搜索引擎WWWW(WorldWideWebWorm)在Colorado大學(xué)開(kāi)發(fā)成功以來(lái)，Web上的搜索引擎己經(jīng)發(fā)展到上千個(gè)，雖然各個(gè)搜索引擎，包括各全文搜索引擎、目錄索引搜索引擎、垂直搜索引擎在內(nèi)的大部分搜索引擎，具體實(shí)現(xiàn)不盡相同，但一般包含5個(gè)基本部分：Robot、分析器、索引器、檢索器和用戶接口，各部分的相關(guān)技術(shù)介紹如下HYPERLINK[3]。圖2-1搜索引擎的基本組成2.1.1Robot采用一定的搜索策略對(duì)Web進(jìn)行遍歷并下載文檔，系統(tǒng)中維護(hù)一個(gè)超鏈隊(duì)列，或者堆棧，其中包含一些起始URL。Robot從這些URL出發(fā)，下載相應(yīng)的頁(yè)面，并從中抽取出新的超鏈加入到隊(duì)列或者堆棧中，上述過(guò)程不斷重復(fù)隊(duì)列直到堆棧為空。為了提高效率，搜索引擎中可能會(huì)有多個(gè)Robot進(jìn)程同時(shí)遍歷不同的Web子空間；為了便于將來(lái)擴(kuò)展服務(wù)，Robot應(yīng)能改變搜索范圍。Robot一般采用以寬度優(yōu)先搜索策略為主、線性搜索策略為輔的搜索策略HYPERLINK[4]。線性搜索策略：這是最簡(jiǎn)單的搜索方法，它的基本思想是沿著一個(gè)起始的IP地址，按IP地址遞增的方式搜索后續(xù)的每一個(gè)WWW地址中的HTML文件，完全不考慮各站點(diǎn)的HTML文件中指向其他Web站點(diǎn)的超鏈接地址。此策略不適用于大規(guī)模的搜索（主要原因在于IP可能是動(dòng)態(tài)的），但可以用于小范圍的全面搜索，利用此種策略Robot可以發(fā)現(xiàn)被引用較少或者還沒(méi)有被其他HTML文件引用的新HTML文件信息源。深度優(yōu)先搜索：這是在開(kāi)發(fā)Robot的早期使用較多的一種方法，它的目的是要達(dá)到被搜索結(jié)構(gòu)的葉結(jié)點(diǎn)。深度優(yōu)先搜索順著HTML文件上的超鏈接走到不能再深入為止，然后返回到某一個(gè)HTML文件，再繼續(xù)選擇該HTML文件中的其他超鏈接。當(dāng)不再有其他超鏈接可選擇時(shí)，說(shuō)明搜索已經(jīng)結(jié)束。深度優(yōu)先搜索適宜遍歷一個(gè)指定的站點(diǎn)或者深層嵌套的HTML文件集，但對(duì)于大規(guī)模的搜索，由于Web結(jié)構(gòu)相當(dāng)深，也許就再也出不來(lái)了。寬度優(yōu)先搜索策略：該搜索策略執(zhí)行時(shí)先搜索一層中的內(nèi)容，然后再繼續(xù)搜索下一層。如一個(gè)HTML文件中有三個(gè)超鏈接，選擇其中之一并處理相應(yīng)的HTML文件，然后返回并選擇剛才第一個(gè)網(wǎng)頁(yè)的第二個(gè)超鏈接，處理相應(yīng)的HTML文件，再返回。一旦一層上的所有超鏈接都已被選擇過(guò)，就可以開(kāi)始在剛才處理過(guò)的HTML文件中搜索其余的超鏈接。該搜索策略保證了對(duì)淺層的首先處理，當(dāng)遇到一個(gè)無(wú)窮盡的深層分支時(shí)，也就不會(huì)再陷進(jìn)去；且容易實(shí)現(xiàn)，具備大多數(shù)期望的功能，但是需要花費(fèi)比較長(zhǎng)的時(shí)間才能到達(dá)深層的HTML文件。2.1.2分析器對(duì)Robot下載的文檔進(jìn)行分析以用于索引，文檔分析技術(shù)一般包括：分詞、過(guò)濾和轉(zhuǎn)換。這些技術(shù)往往與具體的語(yǔ)言以及系統(tǒng)的索引模型密切相關(guān)。2.1.3索引器將文檔表示為一種便于檢索的方式并存儲(chǔ)在索引數(shù)據(jù)庫(kù)中。索引的質(zhì)量是Web信息檢索系統(tǒng)成功的關(guān)鍵因素之一。一個(gè)好的索引模型應(yīng)該易于實(shí)現(xiàn)和維護(hù)，檢索速度快，空間需求低。搜索引擎普遍借鑒了傳統(tǒng)信息檢索中的索引模型，包括倒排文檔、矢量空間模型、概率模型等。例如在矢量空間索引模型中，每個(gè)文檔d都表示為一個(gè)范化矢量ti為詞條項(xiàng)，wi(d)為ti在d中的權(quán)值，一般被定義為ti在d中出現(xiàn)頻率tfi(d)的函數(shù)。2.1.4檢索器從索引中找出與用戶查詢(xún)請(qǐng)求相關(guān)的文檔，采用與分析索引文檔相識(shí)的方法來(lái)處理用戶查詢(xún)請(qǐng)求。如在矢量空間索引模型中，用戶查詢(xún)q也被表示為一個(gè)范化矢量。然后按照某種方法來(lái)計(jì)算用戶查詢(xún)與索引數(shù)據(jù)庫(kù)中每個(gè)文檔之間的相關(guān)度，例如在矢量空間索引模型中，相關(guān)度可以表示為查詢(xún)矢量與文檔矢量之間的夾角余弦。最后將相關(guān)度大于閥值的所有文檔按照相關(guān)度遞減的順序排列并返還給用戶，當(dāng)然搜索引擎的相關(guān)度判斷并不一定與所有用戶的需求完全吻合HYPERLINK[5]。2.1.5用戶接口該部分為用戶提供可視化的查詢(xún)輸入和結(jié)果輸出界面。在查詢(xún)界面中，用戶按照搜索引擎的查詢(xún)語(yǔ)法制定待檢索詞條及各種簡(jiǎn)單、高級(jí)檢索條件。在輸出界面中，現(xiàn)有大部分搜索引擎將檢索結(jié)果展現(xiàn)為一個(gè)線性的文檔列表，其中包含了文檔的標(biāo)題、摘要和超鏈等信息；檢索結(jié)果中相關(guān)文檔和不相關(guān)文檔相互混雜，用戶需要逐個(gè)瀏覽以找出所需文檔。這也正是本課題所要解決的問(wèn)題。Web信息是動(dòng)態(tài)變化的，因此Robot、分析器和索引器模塊要定期更新數(shù)據(jù)庫(kù)，時(shí)間視具體搜索引擎實(shí)現(xiàn)不同而有所差異，索引數(shù)據(jù)庫(kù)越大，更新也越困難HYPERLINK[6]。2.2搜索引擎工作流程包括全文搜索引擎、目錄索引搜索引擎、垂直搜索引擎在內(nèi)的大部分搜索引擎的工作可以分為如下三步：從互聯(lián)網(wǎng)上抓取網(wǎng)頁(yè)→建立索引數(shù)據(jù)庫(kù)→在索引數(shù)據(jù)庫(kù)中搜索排序。（1）從互聯(lián)網(wǎng)上抓取網(wǎng)頁(yè)：利用能夠從互聯(lián)網(wǎng)上自動(dòng)收集網(wǎng)頁(yè)的Spider系統(tǒng)程序，自動(dòng)訪問(wèn)互聯(lián)網(wǎng)，并沿著任何網(wǎng)頁(yè)中的所有URL爬到其它網(wǎng)頁(yè)，重復(fù)這過(guò)程，并把爬過(guò)的所有網(wǎng)頁(yè)收集回來(lái)。（2）建立索引數(shù)據(jù)庫(kù)：由分析索引系統(tǒng)程序?qū)κ占貋?lái)的網(wǎng)頁(yè)進(jìn)行分析，提取相關(guān)網(wǎng)頁(yè)信息（包括網(wǎng)頁(yè)所在URL、編碼類(lèi)型、頁(yè)面內(nèi)容包含的關(guān)鍵詞、關(guān)鍵詞位置、生成時(shí)間、大小、與其它網(wǎng)頁(yè)的鏈接關(guān)系等），根據(jù)一定的相關(guān)度算法進(jìn)行大量復(fù)雜計(jì)算，得到每一個(gè)網(wǎng)頁(yè)針對(duì)頁(yè)面內(nèi)容及超鏈接中每一個(gè)關(guān)鍵詞的相關(guān)度，然后用這些相關(guān)信息建立網(wǎng)頁(yè)索引數(shù)據(jù)庫(kù)。（3）在索引數(shù)據(jù)庫(kù)中搜索排序：當(dāng)用戶輸入關(guān)鍵詞搜索后，由搜索系統(tǒng)程序從網(wǎng)頁(yè)索引數(shù)據(jù)庫(kù)中找到符合該關(guān)鍵詞的所有相關(guān)網(wǎng)頁(yè)。由于所有相關(guān)網(wǎng)頁(yè)針對(duì)該關(guān)鍵詞的相關(guān)度早已算好，所以只需按照現(xiàn)成的相關(guān)度數(shù)值排序，相關(guān)度越高，排名越靠前。最后，由頁(yè)面生成系統(tǒng)將搜索結(jié)果的鏈接地址和頁(yè)面內(nèi)容摘要等內(nèi)容組織起來(lái)返回給用戶。搜索引擎的Spider一般要定期重新訪問(wèn)所有網(wǎng)頁(yè)（各搜索引擎的周期不同，可能是幾天、幾周或幾月，也可能對(duì)不同重要性的網(wǎng)頁(yè)有不同的更新頻率），更新網(wǎng)頁(yè)索引數(shù)據(jù)庫(kù)，以反映出網(wǎng)頁(yè)內(nèi)容的更新情況，增加新的網(wǎng)頁(yè)信息，去除死鏈接，并根據(jù)網(wǎng)頁(yè)內(nèi)容和鏈接關(guān)系的變化重新排序。這樣，網(wǎng)頁(yè)的具體內(nèi)容和變化情況就會(huì)反映到用戶查詢(xún)的結(jié)果中HYPERLINK[7]。2.3搜索引擎分類(lèi)搜索引擎按其工作方式主要可分為四種，分別是全文搜索引擎(FullTextSearchEngine)、目錄索引類(lèi)搜索引擎(SearchIndex/Directory)、元搜索引擎(MetaSearchEngine)和垂直搜索引擎(VerticalSearchEngine)HYPERLINK[8]。2.3.1全文搜索引擎全文搜索引擎是從網(wǎng)站提取信息并建立網(wǎng)頁(yè)數(shù)據(jù)庫(kù)。搜索引擎的自動(dòng)信息搜集功能分兩種。一種是定期搜索，即每隔一段時(shí)間（比如Google一般是28天），搜索引擎主動(dòng)派出Spider(“蜘蛛”程序)，對(duì)一定IP地址范圍內(nèi)的互聯(lián)網(wǎng)站進(jìn)行搜索，一旦發(fā)現(xiàn)新的網(wǎng)站，它會(huì)自動(dòng)提取網(wǎng)站的信息和網(wǎng)址加入自己的數(shù)據(jù)庫(kù)。另一種是提交網(wǎng)站搜索，即網(wǎng)站擁有者主動(dòng)向搜索引擎提交網(wǎng)址，它在一定時(shí)間內(nèi)（2天到數(shù)月不等）定向向網(wǎng)站派出“蜘蛛”程序，掃描網(wǎng)站并將有關(guān)信息存入數(shù)據(jù)庫(kù)，以備用戶查詢(xún)。由于近年來(lái)搜索引擎索引規(guī)則發(fā)生了很大變化，主動(dòng)提交網(wǎng)址并不保證所提交網(wǎng)站能進(jìn)入搜索引擎數(shù)據(jù)庫(kù)。當(dāng)用戶以關(guān)鍵詞查找信息時(shí)，搜索引擎會(huì)在數(shù)據(jù)庫(kù)中進(jìn)行搜尋，如果找到與用戶要求內(nèi)容相符的網(wǎng)站，便采用特殊的算法（通常根據(jù)網(wǎng)頁(yè)中關(guān)鍵詞的匹配程度，出現(xiàn)的位置／頻次，鏈接質(zhì)量等）計(jì)算出各網(wǎng)頁(yè)的相關(guān)度及排名等級(jí)，然后根據(jù)關(guān)聯(lián)度高低，按順序?qū)⑦@些網(wǎng)頁(yè)鏈接返回給用戶。在全文搜索引擎中，google和百度是當(dāng)前國(guó)內(nèi)用戶數(shù)較多的搜索引擎產(chǎn)品。Google（/）成立于1997年，幾年間迅速發(fā)展成為世界范圍內(nèi)規(guī)模最大的搜索引擎。Google數(shù)據(jù)庫(kù)現(xiàn)存有42.8億個(gè)Web文件，每天處理的搜索請(qǐng)求已達(dá)2億次，而且這一數(shù)字還在不斷增長(zhǎng)HYPERLINK[9]。Google借用Dmoz（/）的分類(lèi)目錄提供“網(wǎng)頁(yè)目錄”查詢(xún)（/dirhp?hl=zh-CN&tab=wd&ie=UTF-8&oe=UTF-8&q=），但默認(rèn)網(wǎng)站排列順序并非按照字母順序，而是根據(jù)網(wǎng)站PageRank的分值高低排列。百度（/）是國(guó)內(nèi)最早的商業(yè)化（早期為其它門(mén)戶網(wǎng)站提供搜索服務(wù)，現(xiàn)在的競(jìng)價(jià)排名更為其帶來(lái)高效回報(bào)）全文搜索引擎，擁有自己的網(wǎng)絡(luò)機(jī)器人和索引數(shù)據(jù)庫(kù)，專(zhuān)注于中文的搜索引擎市場(chǎng)，除有網(wǎng)頁(yè)搜索外，百度還有專(zhuān)門(mén)針對(duì)新聞、MP3、圖片等搜索，并成功推出了“貼吧”、“百科”、“知道”等功能。2.3.2目錄索引搜索引擎與全文搜索引擎相比，目錄索引有許多不同之處。首先，搜索引擎屬于自動(dòng)網(wǎng)站搜索，而目錄索引則更加依賴(lài)手工操作。用戶提交網(wǎng)站后，目錄編輯人員會(huì)親自瀏覽你的網(wǎng)站，然后根據(jù)一套自定的評(píng)判標(biāo)準(zhǔn)甚至編輯人員的主觀印象，決定是否接納你的網(wǎng)站。其次，搜索引擎收錄網(wǎng)站時(shí)，只要網(wǎng)站本身沒(méi)有違反有關(guān)的規(guī)則，一般都能登錄成功。而目錄索引對(duì)網(wǎng)站的要求則高得多，有時(shí)即使登錄多次也不一定成功。尤其象Yahoo！這樣的超級(jí)索引，登錄更是困難。此外，在登錄搜索引擎時(shí)，我們一般不用考慮網(wǎng)站的分類(lèi)問(wèn)題，而登錄目錄索引時(shí)則必須將網(wǎng)站放在一個(gè)最合適的目錄(Directory)。最后，搜索引擎中各網(wǎng)站的有關(guān)信息都是從用戶網(wǎng)頁(yè)中自動(dòng)提取的，所以從用戶的角度看，我們擁有更多的自主權(quán)；而目錄索引則要求必須手工另外填寫(xiě)網(wǎng)站信息，而且還有各種各樣的限制。更有甚者，如果工作人員認(rèn)為你提交網(wǎng)站的目錄、網(wǎng)站信息不合適，他可以隨時(shí)對(duì)其進(jìn)行調(diào)整。目錄索引，顧名思義就是將網(wǎng)站分門(mén)別類(lèi)地存放在相應(yīng)的目錄中，因此用戶在查詢(xún)信息時(shí)，可選擇關(guān)鍵詞搜索，也可按分類(lèi)目錄逐層查找。如以關(guān)鍵詞搜索，返回的結(jié)果跟搜索引擎一樣，也是根據(jù)信息關(guān)聯(lián)程度排列網(wǎng)站，只不過(guò)其中人為因素要多一些。如果按分層目錄查找，某一目錄中網(wǎng)站的排名則是由標(biāo)題字母的先后順序決定(也有例外)。目前，全文搜索引擎與目錄索引有相互融合滲透的趨勢(shì)。原來(lái)一些純粹的全文搜索引擎現(xiàn)在也提供目錄搜索，如Google就借用OpenDirectory目錄提供分類(lèi)查詢(xún)。而象Yahoo！這些老牌目錄索引則通過(guò)與Google等搜索引擎合作擴(kuò)大搜索范圍。在默認(rèn)搜索模式下，一些目錄類(lèi)搜索引擎首先返回的是自己目錄中匹配的網(wǎng)站，如國(guó)內(nèi)搜狐、新浪、網(wǎng)易等；而另外一些則默認(rèn)的是網(wǎng)頁(yè)搜索，如Yahoo！(Yahoo！已于2004年2月正式推出自己的全文搜索引擎，并結(jié)束了與Google的合作)。在當(dāng)前目錄索引搜索引擎中，雅虎、新浪及網(wǎng)易較為公眾所熟知。雅虎中國(guó)分類(lèi)目錄（/）是最早的分類(lèi)目錄，現(xiàn)有14個(gè)主類(lèi)目，包括“商業(yè)與經(jīng)濟(jì)”、“藝術(shù)與人文”等，可以逐層進(jìn)入進(jìn)行檢索，也可以利用關(guān)鍵詞對(duì)“分類(lèi)網(wǎng)站”進(jìn)行搜索（http://m6.search.cnb.yahoo.com/dirsrch/）。此外，雅虎中國(guó)也可以對(duì)“所有網(wǎng)站”進(jìn)行關(guān)鍵詞搜索（http:///websrch/），早期，他的搜索結(jié)果使用Google的數(shù)據(jù)，2004年2月正式推出自己的全文搜索引擎，并結(jié)束了與Google的合作。搜狐分類(lèi)目錄（http://dir.sohu.com/）把網(wǎng)站作為收錄對(duì)象，具體的方法就是將每個(gè)網(wǎng)站首頁(yè)的URL地址提供給搜索用戶，并且將網(wǎng)站的題名和整個(gè)網(wǎng)站的內(nèi)容簡(jiǎn)單描述一下，但是并不揭示網(wǎng)站中每個(gè)網(wǎng)頁(yè)的信息內(nèi)容。除此之外，也可以使用關(guān)鍵詞對(duì)搜狐的“分類(lèi)目錄”或所有網(wǎng)站進(jìn)行搜索。2.3.3垂直搜索引擎垂直搜索引擎是相對(duì)通用搜索引擎信息量大、查詢(xún)不準(zhǔn)確、深度不夠等提出的新的搜索引擎服務(wù)模式。它通過(guò)針對(duì)某一特定領(lǐng)域、某一特定人群或某一特定需求提供的有一定價(jià)值的信息和相關(guān)服務(wù)，是搜索引擎的細(xì)分和延伸，其特點(diǎn)就是“專(zhuān)精深”，且具有行業(yè)色彩，相比較通用搜索引擎的海量信息無(wú)序化，垂直搜索引擎則顯得更加專(zhuān)注、具體和深入。垂直搜索引擎是對(duì)網(wǎng)頁(yè)庫(kù)中的某類(lèi)專(zhuān)門(mén)的信息進(jìn)行一次整合，定向分字段抽取出需要的數(shù)據(jù)進(jìn)行處理后再以某種形式返回給用戶。垂直搜索引擎和普通的網(wǎng)頁(yè)搜索引擎的最大區(qū)別是對(duì)網(wǎng)頁(yè)信息進(jìn)行了結(jié)構(gòu)化信息抽取，也就是將網(wǎng)頁(yè)的非結(jié)構(gòu)化數(shù)據(jù)抽取成特定的結(jié)構(gòu)化信息數(shù)據(jù)，好比網(wǎng)頁(yè)搜索是以網(wǎng)頁(yè)為最小單位，基于視覺(jué)的網(wǎng)頁(yè)塊分析是以網(wǎng)頁(yè)塊為最小單位，而垂直搜索是以結(jié)構(gòu)化數(shù)據(jù)為最小單位，然后將這些數(shù)據(jù)存儲(chǔ)到數(shù)據(jù)庫(kù)，進(jìn)行進(jìn)一步的加工處理，如：去重、分類(lèi)等，最后分詞、索引再以搜索的方式滿足用戶的需求。垂直搜索引擎的三個(gè)特點(diǎn)：（1）垂直搜索引擎抓取的數(shù)據(jù)來(lái)源于垂直搜索引擎關(guān)注的行業(yè)站點(diǎn)；（2）垂直搜索引擎抓取的數(shù)據(jù)傾向于結(jié)構(gòu)化數(shù)據(jù)和元數(shù)據(jù)；（3）垂直搜索引擎的搜索行為是基于結(jié)構(gòu)化數(shù)據(jù)和元數(shù)據(jù)的結(jié)構(gòu)化搜索。垂直搜索引擎的應(yīng)用方向很多，比如企業(yè)庫(kù)搜索、供求信息搜索、購(gòu)物搜索、房產(chǎn)搜索、人才搜索、地圖搜索、mp3搜索、圖片搜索。幾乎各行各業(yè)各類(lèi)信息都可以進(jìn)一步細(xì)化成各類(lèi)的垂直搜索引擎。2.3.4元搜索引擎目前，雖然各個(gè)商家的搜索引擎為了在競(jìng)爭(zhēng)中獲勝而不斷地增加其索引的Web頁(yè)面數(shù)目，但是卻跟不上Web的發(fā)展速度，任何一個(gè)搜索引擎對(duì)Web的覆蓋度都相當(dāng)有限，不超過(guò)30％。因此，用戶經(jīng)常需要檢索多個(gè)系統(tǒng)以提高檢索的召回率(Recall)。但是，每個(gè)搜索引擎的用戶接口是異構(gòu)的，有其特定且復(fù)雜的界面和查詢(xún)語(yǔ)法，這給用戶同時(shí)使用多個(gè)系統(tǒng)帶來(lái)了不便，針對(duì)這些情況，出現(xiàn)了元搜索引擎。元搜索引擎在接受用戶查詢(xún)請(qǐng)求時(shí)，同時(shí)在其他多個(gè)引擎上進(jìn)行搜索，并將結(jié)果返回給用戶。元搜索引擎將多個(gè)獨(dú)立的搜索引擎集成在一起，提供統(tǒng)一的界面，試圖通過(guò)實(shí)現(xiàn)現(xiàn)有數(shù)據(jù)庫(kù)的綜合利用來(lái)提高搜索引擎的性能。元搜索引擎是建立在多個(gè)獨(dú)立搜索引擎之上的一種搜索引擎．它自己并不收集網(wǎng)站或網(wǎng)頁(yè)信息，通常也沒(méi)有自己的資源庫(kù)和Robot，其結(jié)果來(lái)源于它所管理的獨(dú)立搜索引擎。當(dāng)用戶向元搜索引擎發(fā)出查詢(xún)請(qǐng)求時(shí)，元搜索引擎即根據(jù)該請(qǐng)求向多個(gè)獨(dú)立搜索引擎發(fā)出實(shí)際查詢(xún)請(qǐng)求，然后將所有來(lái)自獨(dú)立搜索引擎的查詢(xún)結(jié)果處理后返回給用戶。其結(jié)構(gòu)示意圖如下圖2-2元搜索引擎結(jié)構(gòu)示意圖元搜索引擎的基本設(shè)計(jì)思想及工作流程可以總結(jié)如下：(1)對(duì)用戶查詢(xún)請(qǐng)求進(jìn)行處理，分別將其轉(zhuǎn)換為若干個(gè)底層搜索引擎能處理的格式；(2)向各個(gè)搜索引擎發(fā)送查詢(xún)請(qǐng)求，并等待其返回檢索結(jié)果。例如：MetaCrawler同時(shí)檢索Yahoo、LookSmart、AltaVista等3個(gè)主要的搜索引擎；(3)對(duì)檢索結(jié)果進(jìn)行后處理，包括:組合各個(gè)搜索引擎返回的檢索結(jié)果，消除重復(fù)項(xiàng)，對(duì)結(jié)果進(jìn)行排序等。有些搜索引擎在必要時(shí)還通過(guò)下載Web文檔來(lái)實(shí)現(xiàn)一些搜索引擎不支持的查詢(xún)，或者對(duì)文檔作進(jìn)一步的分析以提高信息檢索的精度；(4)向用戶返回經(jīng)過(guò)組合和處理后的檢索結(jié)果。上述思想雖然簡(jiǎn)單，但是效果卻比較明顯，對(duì)于設(shè)計(jì)人員而言，不需要建立和維護(hù)龐大的索引數(shù)據(jù)庫(kù)，也不需要使用復(fù)雜的檢索機(jī)制，對(duì)于用戶而言，元搜索引擎提供了一個(gè)能夠同時(shí)查詢(xún)多個(gè)搜索引擎的集成界面，它將各個(gè)搜索引擎的位置、接口等細(xì)節(jié)都屏蔽了起來(lái)，與此同時(shí)元搜索引擎還提高了檢索的召回率和精度。著名的元搜索引擎有InfoSpace()、Dogpile(http://www.dogpile.com)、Vivisimo()等。而中文元搜索引擎中具有代表性的有比比貓（http://）等。在搜索結(jié)果排列方面，有的直接按來(lái)源引擎排列搜索結(jié)果，如Dogpile，有的則按自定的規(guī)則將結(jié)果重新排列組合，如Vivisimo。聚類(lèi)研究3.1文檔自動(dòng)分類(lèi)搜索引擎可對(duì)因特網(wǎng)上海量雜亂無(wú)章的信息進(jìn)行索引，幫助人們找到想要的信息。為了快速、準(zhǔn)確地從Web上找到人們所需的信息，對(duì)網(wǎng)頁(yè)文檔進(jìn)行聚類(lèi)分析是非常重要的。在搜索引擎上，聚類(lèi)分析可用于對(duì)搜索引擎中的Robot抓到的網(wǎng)頁(yè)進(jìn)行聚類(lèi)分析，自動(dòng)生成便于用戶查詢(xún)的網(wǎng)頁(yè)聚類(lèi)系統(tǒng)。聚類(lèi)分析還可用于對(duì)用戶查詢(xún)的結(jié)果進(jìn)行處理，以一種超鏈接的層次方式提交給用戶，提高查詢(xún)的查全率和查準(zhǔn)率HYPERLINK[10]。在設(shè)計(jì)搜索引擎時(shí)，聚類(lèi)技術(shù)對(duì)創(chuàng)建索引的結(jié)構(gòu)化和檢索的優(yōu)化，對(duì)大量網(wǎng)頁(yè)有效尋找和自動(dòng)分類(lèi)的組織方法是很重要。目前，多數(shù)搜索引擎對(duì)搜索結(jié)果的組織方法基本一致，即將搜索結(jié)果按照一定規(guī)則(相關(guān)度、Pagerank等)排列，以列表的方式呈現(xiàn)給用戶。這種方式存在一些缺陷，如：搜索結(jié)果動(dòng)輒成千上萬(wàn)，用戶無(wú)法一一查看，而真正符合用戶需要的搜索結(jié)果很有可能因?yàn)榕盼豢亢蠖诲e(cuò)過(guò)了，因?yàn)镻agerank等排序方法只能保證排在前面的搜索結(jié)果是最權(quán)威的，而不一定是最符合用戶需要的；從另一個(gè)方面來(lái)說(shuō)，這也是對(duì)搜索引擎資源的一種浪費(fèi)，因?yàn)榉祷亟Y(jié)果中只有很少的部分得到了用戶的有效利用。因此，在排序的基礎(chǔ)上，進(jìn)一步組織和控制搜索結(jié)果，是提高搜索結(jié)果質(zhì)量的有效途徑之一。在搜索引擎中應(yīng)用聚類(lèi)技術(shù)，可以有效地組織和控制搜索引擎的搜索結(jié)果。經(jīng)過(guò)聚類(lèi)處理的搜索結(jié)果以類(lèi)目的形式呈現(xiàn)，內(nèi)容相似的搜索結(jié)果被劃分為一個(gè)類(lèi)目，類(lèi)目之間又具有包含關(guān)系，這樣，搜索結(jié)果就被有效地組織起來(lái)，用戶可以快速地了解搜索結(jié)果的整體分布情況，并快速定位自己需要的搜索結(jié)果。3.2聚類(lèi)分析聚類(lèi)分析是根據(jù)數(shù)據(jù)項(xiàng)和聚類(lèi)之間的關(guān)聯(lián)計(jì)算來(lái)安排數(shù)據(jù)項(xiàng)自動(dòng)分類(lèi)的多變化分析技巧，用來(lái)產(chǎn)生數(shù)據(jù)集的目錄結(jié)構(gòu)。聚類(lèi)的最終目的是達(dá)到同一個(gè)聚類(lèi)中的成員有較高的關(guān)聯(lián)度，不同聚類(lèi)中的成員有較低的關(guān)聯(lián)度的效果HYPERLINK[11]，其中關(guān)聯(lián)計(jì)算可以用相似度、相異度和歐幾里德距離等進(jìn)行度量。聚類(lèi)分析方法有兩種類(lèi)型：一類(lèi)是非分層聚類(lèi)方法，把N個(gè)數(shù)據(jù)項(xiàng)的數(shù)據(jù)集分成M個(gè)類(lèi)，常用的有單遍方法和重新分配方法；另一類(lèi)是分層聚類(lèi)，在一對(duì)數(shù)據(jù)項(xiàng)里或成功鏈接的類(lèi)里產(chǎn)生一個(gè)嵌套數(shù)據(jù)集，常用的有單鏈路方法、完全鏈路方法、組平均鏈路方法和Ward方法HYPERLINK[12]。聚類(lèi)分析在文檔上的實(shí)現(xiàn)有以下幾種方法：(1)文檔根據(jù)它們所包含的索引詞來(lái)聚類(lèi)。方法的目的是提供有效的和高效率的檢索；(2)索引詞可以根據(jù)聯(lián)合發(fā)生的文檔來(lái)聚類(lèi)。這種方法可以改進(jìn)詞典的結(jié)構(gòu)或者是加強(qiáng)查詢(xún)；(3)文檔也可根據(jù)聯(lián)合發(fā)生的引用來(lái)聚類(lèi)。這個(gè)方法可以提供進(jìn)入某個(gè)信息領(lǐng)域的途徑HYPERLINK[13]。3.3基本聚類(lèi)方法聚類(lèi)法是根據(jù)所生成的簇類(lèi)結(jié)構(gòu)來(lái)分類(lèi)的。大體上，主要的聚類(lèi)法可分為平面劃分方法(Partitioningmethod)、層次凝聚方法(Hierarchicalmethod),基于密度的方法(Density-basedmethod),基于網(wǎng)格的方法(Grid-basedmethod)和基于模型的方法(Model-basedmethod)。由于這些方法有不同的理論和實(shí)踐基礎(chǔ)，每種方法又有多種具體實(shí)現(xiàn)算法，可以產(chǎn)生不同的聚類(lèi)結(jié)構(gòu)，聚類(lèi)方法的選擇將決定查詢(xún)的結(jié)果和效果。聚類(lèi)的方法決定了聚類(lèi)的結(jié)果，而具體的實(shí)現(xiàn)算法決定了聚類(lèi)過(guò)程的有效性。隨著聚類(lèi)技術(shù)的不斷發(fā)展和計(jì)算機(jī)技術(shù)的發(fā)展，處理海量數(shù)據(jù)集的新的聚類(lèi)方法也在不斷出現(xiàn)HYPERLINK[14]。3.3.1平面劃分方法平面劃分法主要應(yīng)用于早期的文檔聚類(lèi)，比如在SMART項(xiàng)目中的聚類(lèi)試驗(yàn)。由于早期計(jì)算資源有限，平面劃分法比起層次凝聚類(lèi)方法在時(shí)間和空間需求上相對(duì)比較低，所以在信息檢索系統(tǒng)中的應(yīng)用重點(diǎn)在于最佳匹配的有效性上。平面劃分法的主要思想是將文檔集分割為若干簇類(lèi)，這類(lèi)算法包括K-Means和Singlepass。Singlepass的方法屬于加入法，其具體過(guò)程如下：首先將文檔集D中的第一個(gè)文檔作為一個(gè)簇類(lèi)，計(jì)算與簇類(lèi)的相似度，如果相似度超過(guò)某一閥值，就將加入到簇類(lèi)中，否則另外建立一個(gè)包含的簇類(lèi)；以此類(lèi)推，將剩余的文檔歸入與它最相近的簇類(lèi)中，或者另建新簇類(lèi)。該方法的優(yōu)點(diǎn)在于遍歷一次各文檔，就可以形成各簇類(lèi)。缺點(diǎn)是它與文檔順序有關(guān)，不同的文檔順序，聚類(lèi)結(jié)果出入很大，而且也容易形成較大的簇類(lèi)，但它仍然是最受歡迎的增量式聚類(lèi)方法。K-Means屬于調(diào)整法，主要思路是:給定要構(gòu)建的劃分?jǐn)?shù)目,先創(chuàng)建一個(gè)初始化分。然后采用一種迭代的重定位技術(shù)，嘗試通過(guò)再劃分移動(dòng)來(lái)改進(jìn)劃分，具體過(guò)程如下：(1)確定要生成的聚類(lèi)的數(shù)目；(2)按照某種原則生成個(gè)聚類(lèi)中心作為聚類(lèi)的種子；(3)對(duì)中的每一個(gè)文檔，依次計(jì)算它與各個(gè)種子的相似度；(4)選取具有最大的相似度的種子,將歸入以為聚類(lèi)中心的中，從而得到一個(gè)聚類(lèi)結(jié)果；(5)然后重新計(jì)算個(gè)聚類(lèi)的中心點(diǎn)或者是平均值，再以中心點(diǎn)或者平均值作為種子，重復(fù)步驟3-4若干次，直到聚類(lèi)結(jié)果不再發(fā)生變化，或者直到準(zhǔn)則函數(shù)收斂。通常，采用平方誤差準(zhǔn)則，其定義如下:這里的E是數(shù)據(jù)集中所有對(duì)象的平方誤差的總和，p是空何中的點(diǎn)，表示給定的數(shù)據(jù)對(duì)象，mi是簇類(lèi)ci平均值(p和mi都是多維的)。這個(gè)準(zhǔn)則試圖使生成的結(jié)果聚類(lèi)盡可能地緊湊和獨(dú)立。這個(gè)算法嘗試找出使平方誤差函數(shù)值最小的個(gè)劃分。當(dāng)結(jié)果簇是密集的，而簇與簇之間區(qū)別明顯時(shí)，它的效果較好。但聚類(lèi)前要求用戶必須給出(要生成的簇類(lèi)的數(shù)目)也算是該算法的一個(gè)缺點(diǎn)，且它不適合于發(fā)現(xiàn)非凸面形狀的簇，或者大小差別很大的簇，另外由于不同的個(gè)種子的選擇會(huì)導(dǎo)致不同的聚類(lèi)結(jié)果，所以這種算法具有很大的不確定性。生成個(gè)簇類(lèi)種子的方法有以下幾種：前元法直接取前個(gè)文檔作為初始凝聚點(diǎn)，或者稱(chēng)做種子點(diǎn)（中心點(diǎn)）；經(jīng)驗(yàn)法憑經(jīng)驗(yàn)確定文檔集合為幾類(lèi)，對(duì)每一類(lèi)指定一個(gè)代表點(diǎn)，其中代表點(diǎn)有多種確定方法；隨機(jī)法首先確定將文檔集合分為幾類(lèi)，然后將每個(gè)文檔隨機(jī)地分配給每一類(lèi)，計(jì)算每一類(lèi)的均值作為初始凝聚點(diǎn)；或者直接隨機(jī)指定幾個(gè)文檔點(diǎn)作為初始凝聚點(diǎn)；密度法先人為給定兩個(gè)數(shù)()，對(duì)每一個(gè)文檔統(tǒng)計(jì)和它相距不超過(guò)的文檔數(shù)目，并稱(chēng)為它的密度。將文檔按照密度由大到小排列，首先將密度最大的文檔加入到凝聚點(diǎn)集中，然后考慮密度次大的文檔，如果該文檔到現(xiàn)有的任一凝聚點(diǎn)的距離都大于，則將該文檔加入到一個(gè)凝聚點(diǎn)集合HYPERLINK[15]。其它平面劃分方法的變形如：CLARA，不考慮整個(gè)數(shù)據(jù)集合，選擇實(shí)際數(shù)據(jù)的一小部分作為數(shù)據(jù)的樣本，然后用PAM(PartitioningaroundMedoid，圍繞中心點(diǎn)劃分)方法從樣本中選擇中心點(diǎn)。CLARA抽取數(shù)據(jù)集合的多個(gè)樣本，對(duì)每個(gè)樣本應(yīng)用PAM算法，返回最好的聚類(lèi)結(jié)果作為輸出。平面劃分方法不需要提前計(jì)算相似性矩陣；但平面劃分法依賴(lài)于輸入文檔的順序，且要求k預(yù)先確定。3.3.2層次凝聚方法隨著計(jì)算資源的發(fā)展與進(jìn)步，以及一些聚類(lèi)分析軟件包的實(shí)現(xiàn)，使得近幾年層次聚類(lèi)方法在信息檢索系統(tǒng)中得到了較為廣泛的應(yīng)用。層次聚類(lèi)的方法是對(duì)給定數(shù)據(jù)對(duì)象集合進(jìn)行層次的分解。根據(jù)層次的分解如何形成，層次的方法可以分為凝聚的和分裂的。凝聚的方法屬于合并法，也稱(chēng)自底向上法，開(kāi)始將每個(gè)對(duì)象作為單獨(dú)的一個(gè)簇類(lèi)，然后相繼地合并相近的對(duì)象或簇類(lèi)，直到所有的組合并為一個(gè)(層次的最上層)，或者達(dá)到一個(gè)終止條件。分裂的方法，也稱(chēng)為自頂向下的方法，一開(kāi)始將所有的對(duì)象置于一個(gè)簇類(lèi)中，在迭代的每一步中，一個(gè)簇類(lèi)被分裂為兩個(gè)或多個(gè)更小的簇類(lèi)，直到最終每個(gè)對(duì)象在單獨(dú)的一個(gè)簇類(lèi)中，或者達(dá)到一個(gè)終止條件。在文檔聚類(lèi)中，由于用于分裂法的實(shí)現(xiàn)算法較少，所以層次法中主要以凝聚法為主，我們這里只討論層次凝聚方法。文檔聚類(lèi)中層次凝聚法主要的實(shí)現(xiàn)思想基本是：(1)計(jì)算n個(gè)文檔兩兩之間的相似性，記為初始相似性矩陣；(2)初始構(gòu)造n個(gè)簇類(lèi)，每個(gè)文檔自成一簇類(lèi)；(3)找出兩個(gè)最相似的文檔或點(diǎn)(這里的點(diǎn)包括文檔和簇類(lèi))，將其合并成一個(gè)新簇類(lèi)；(4)計(jì)算新類(lèi)與當(dāng)前簇類(lèi)的相似性，更新相似性矩陣，若簇類(lèi)數(shù)等于1或者達(dá)到一個(gè)停止準(zhǔn)則，則跳至步驟5，否則跳至步驟3；(5)選定分類(lèi)閥值，決定簇類(lèi)的個(gè)數(shù)和簇類(lèi)。所謂停止準(zhǔn)則是指用戶提前定義的聚類(lèi)數(shù)目，或者聚類(lèi)程度，達(dá)到一定的聚類(lèi)數(shù)目或聚類(lèi)程度，聚類(lèi)自動(dòng)停止。具體過(guò)程如下:（1）將文檔集中的每一個(gè)文檔看作一個(gè)具有單個(gè)成員的簇類(lèi)，這些簇類(lèi)構(gòu)成了的一個(gè)聚類(lèi)；（2）計(jì)算中每對(duì)簇類(lèi)之間的相似度,形成初始相似性矩陣；（3）選取具有最大相似度的簇類(lèi)對(duì)，并將和合并為一個(gè)新的簇類(lèi)，從而構(gòu)成D的一個(gè)新的簇類(lèi),更新相似性矩陣；重復(fù)上述步驟，直到中只剩下一個(gè)類(lèi)或滿足停止規(guī)則為止。聚類(lèi)過(guò)程如圖3-1所示:圖3-1層次凝聚類(lèi)示意圖在層次凝聚法中除了需要定義文檔之間的相似性之外，還需要定義簇類(lèi)間的相似性。設(shè)有文檔集合,,我們需要一種側(cè)度來(lái)衡量?jī)纱仡?lèi)之間的相似性，既需要定義函數(shù)，不同的簇類(lèi)間相似性測(cè)度函數(shù)應(yīng)用到上述過(guò)程中，就會(huì)得到不同的層次凝聚方法。在文檔層次凝聚法中主要有以下四種方法：SingleLinkMethod,CompletelinkMethod，GroupAverageLinkMethod,Ward'sMethodHYPERLINK[16]。SinglelinkMethod(最大相似性法)；使用兩聚類(lèi)間的最近兩點(diǎn)的相似性來(lái)描述兩簇類(lèi)間的相似程度，即兩聚類(lèi)、間的相似度可表示為：CompletelinkMethod(最小相似性法):使用兩簇類(lèi)間最遠(yuǎn)兩點(diǎn)間的距離來(lái)描述兩簇類(lèi)間的相似程度，即兩聚類(lèi)、間的相似度可表示為：GroupaverageMethod(類(lèi)平均值法):類(lèi)平均值法使用聚類(lèi),中兩兩對(duì)象點(diǎn)相似性的平均值來(lái)表示累計(jì)相似程度，即兩聚類(lèi)、間的相似度可表示為：其中，、分別為,中對(duì)象點(diǎn)的個(gè)數(shù)。Ward'sMethod(離差平方和法):Ward從方差分析的觀點(diǎn)出發(fā)，認(rèn)為正確的分類(lèi)應(yīng)當(dāng)使得類(lèi)內(nèi)方差盡量小，而類(lèi)間方差盡量的大。樣本集的類(lèi)內(nèi)方差為:每次選擇類(lèi)間最相似的兩類(lèi)合并，使得增加最小，最終得到一個(gè)的局部極小值。此方法只適用于歐氏距離，并不適用于采用相似函數(shù)作為樣本點(diǎn)間相似性測(cè)度的情形HYPERLINK[17]。文檔與文檔之間、文檔與簇類(lèi)之間、各簇類(lèi)之間的相似度計(jì)算算法會(huì)在很大程度上影響聚類(lèi)的質(zhì)量，不同的計(jì)算相似性算法也造成了不同的聚類(lèi)方法特點(diǎn)。具體來(lái)說(shuō)，SinglelinkMethod的主要實(shí)現(xiàn)算法有：SLINKalgorithm和Minimalspanningtreesalgorithm等；CompleteLinkMethod的主要實(shí)現(xiàn)算法有:Defays'CLINKalgorithm、Voorheesalgorithm等；Groupaveragelink的主要實(shí)現(xiàn)算法有:Voorheesalgorithm等；Ward'smethod的主要實(shí)現(xiàn)算法有:Reciprocalnearestneighbor(相互最近鄰算法)等。在凝聚層次聚類(lèi)方法中，用戶需要定義希望得到的簇類(lèi)數(shù)目作為一個(gè)結(jié)束條件。層次聚類(lèi)方法盡管簡(jiǎn)單，但經(jīng)常會(huì)遇到合并點(diǎn)選擇的困難。這樣的決定是非常關(guān)鍵的，因?yàn)橐坏┮唤M對(duì)象被合并，下一步的處理將在新生成的簇類(lèi)上進(jìn)行。已做的處理不能被撤銷(xiāo)，聚類(lèi)之間也不能被交換對(duì)象。如果在某一步?jīng)]有做好選擇合并的決定，可能會(huì)導(dǎo)致低質(zhì)量的聚類(lèi)結(jié)果。而且，這種聚類(lèi)方法不具有很好的可伸縮性，因?yàn)楹喜⒌臎Q定需要檢查和估算大量的對(duì)象或簇類(lèi)。改進(jìn)層次方法的聚類(lèi)質(zhì)量可以將層次聚類(lèi)和其它的聚類(lèi)技術(shù)進(jìn)行集成，形成多階段聚類(lèi)。例如:BIRCH方法綜合了層次凝聚和迭代的重定位方法，它首先用樹(shù)結(jié)構(gòu)對(duì)對(duì)象進(jìn)行層次劃分，采用自底向上的層次算法，然后用迭代的重定位來(lái)改進(jìn)結(jié)果；Buchshot方法首先將部分對(duì)象用層次凝聚類(lèi)法確定最初幾個(gè)類(lèi)，然后將其它對(duì)象歸入到已有簇類(lèi)中；Fraction方法將聚類(lèi)對(duì)象隨機(jī)地分成幾個(gè)部分，然后在各自的小范圍進(jìn)行層次凝聚類(lèi)，以此確定聚類(lèi)結(jié)果。層次聚類(lèi)方法最終形成一個(gè)樹(shù)狀結(jié)構(gòu)的譜系圖(Dendogram)如圖3-1所示，簇類(lèi)之間存在著包含嵌套關(guān)系，每一個(gè)小子簇都包含在它上一級(jí)的父節(jié)點(diǎn)更大的簇類(lèi)中；相比較平面聚類(lèi)法簇類(lèi)之間沒(méi)有關(guān)系。3.4網(wǎng)頁(yè)聚類(lèi)算法根據(jù)聚類(lèi)的對(duì)象不同，可以將目前較為流行的網(wǎng)頁(yè)聚類(lèi)算法分為3類(lèi)：基于網(wǎng)頁(yè)內(nèi)容的聚類(lèi)算法、基于鏈接分析的聚類(lèi)算法和基于用戶搜索日志的聚類(lèi)算法。3.4.1基于網(wǎng)頁(yè)內(nèi)容的聚類(lèi)算法基于網(wǎng)頁(yè)內(nèi)容的聚類(lèi)算法是通過(guò)分析網(wǎng)頁(yè)中包含的文字對(duì)網(wǎng)頁(yè)進(jìn)行聚類(lèi)的，包括STC(SuSxTreeClustering)算法、模糊聚類(lèi)算法等。傳統(tǒng)的聚類(lèi)算法首先對(duì)網(wǎng)頁(yè)內(nèi)容進(jìn)行處理，去掉標(biāo)點(diǎn)符號(hào)及詞語(yǔ)的前綴后綴，并將復(fù)數(shù)形式轉(zhuǎn)化為單數(shù)形式，去除停用詞，從而獲得若干能夠表示網(wǎng)頁(yè)實(shí)際內(nèi)容的關(guān)鍵詞，并將這些關(guān)鍵詞作為聚類(lèi)的依據(jù)。這是基于單個(gè)詞的聚類(lèi)算法，其缺點(diǎn)是只關(guān)注單個(gè)詞，而忽略了詞間關(guān)系。而詞間關(guān)系對(duì)于體現(xiàn)網(wǎng)頁(yè)內(nèi)容是至關(guān)重要的，傳統(tǒng)算法并沒(méi)有充分利用網(wǎng)頁(yè)內(nèi)容所傳達(dá)的信息。STC是基于詞組的聚類(lèi)算法。STC算法首先對(duì)網(wǎng)頁(yè)內(nèi)容進(jìn)行處理，得到若干詞組；然后，通過(guò)后綴樹(shù)算法，辨別出擁有相同詞組的網(wǎng)頁(yè)，并將它們作為基本類(lèi)；最后將基本類(lèi)不斷合并，形成高層次的類(lèi)。這種算法克服了傳統(tǒng)算法的缺陷，將詞間順序也作為聚類(lèi)的重要依據(jù)，從而充分利用了網(wǎng)頁(yè)所包含的信息。STC算法的優(yōu)勢(shì)在于，它的執(zhí)行時(shí)間與網(wǎng)頁(yè)包含詞組的多少成線性關(guān)系，非常高效。并且它將詞組作為聚類(lèi)依據(jù)，有效地利用了詞間關(guān)系，聚類(lèi)準(zhǔn)確度比基于關(guān)鍵詞的聚類(lèi)算法要高得多。但是，也正因?yàn)镾TC算法是基于詞組進(jìn)行聚類(lèi)的，所以其準(zhǔn)確率低于利用全文信息進(jìn)行聚類(lèi)的算法。3.4.2基于鏈接分析的聚類(lèi)算法基于鏈接分析的聚類(lèi)算法是通過(guò)分析網(wǎng)頁(yè)之間的鏈接關(guān)系對(duì)網(wǎng)頁(yè)進(jìn)行聚類(lèi)的。該算法假設(shè)對(duì)任一網(wǎng)頁(yè)而言，存在兩類(lèi)鏈接，一類(lèi)是包含在中的，指向其他網(wǎng)頁(yè)的鏈接；另一類(lèi)是包含在其他網(wǎng)頁(yè)中，指向的鏈接。若網(wǎng)頁(yè)、都包含指向網(wǎng)頁(yè)的鏈接，則網(wǎng)頁(yè)、具有同引關(guān)系；若網(wǎng)頁(yè)包含指向網(wǎng)頁(yè)、的鏈接，則、因?yàn)楸幌嗤木W(wǎng)頁(yè)鏈接而具有同被引關(guān)系。此種算法認(rèn)為具有同引關(guān)系和同被引關(guān)系的網(wǎng)頁(yè)之間具有較大的相似性，并將這兩種引用關(guān)系作為聚類(lèi)的依據(jù)。假設(shè)是檢索結(jié)果集合中的一個(gè)網(wǎng)頁(yè)，用N維向量POUT和M維向量PIN表示，其中POUT=(Po1,Po2…Poi…Pon)。若網(wǎng)頁(yè)P(yáng)中包含指向檢索結(jié)果集合中第i個(gè)網(wǎng)頁(yè)的鏈接，則Poi為1，否則Poi為O；其中Pin=(Pi1,Pi2…Pij…Pim)。若檢索結(jié)果集合中的第j個(gè)網(wǎng)頁(yè)包含指向網(wǎng)頁(yè)P(yáng)的鏈接，則Pij為1，否則Pij為0。計(jì)算檢索結(jié)果中任意兩個(gè)網(wǎng)頁(yè)P(yáng)，Q之間相似度的方法如下：其中，聚類(lèi)的過(guò)程如下：從檢索結(jié)果集合中去除無(wú)關(guān)網(wǎng)頁(yè)，依據(jù)上述相似度計(jì)算公式對(duì)網(wǎng)頁(yè)之間的相似度進(jìn)行計(jì)算，將相似度大于閾值的網(wǎng)頁(yè)作為一個(gè)聚類(lèi)。3.4.3基于用戶搜索日志的聚類(lèi)算法基于用戶搜索日志的聚類(lèi)算法是通過(guò)用戶對(duì)搜索結(jié)果網(wǎng)頁(yè)的訪問(wèn)情況對(duì)網(wǎng)頁(yè)進(jìn)行聚類(lèi)的。對(duì)用戶日志進(jìn)行聚類(lèi)，以?xún)蓚€(gè)假設(shè)為前提：（1）如果兩個(gè)檢索式包含相同的檢索詞，那么這兩個(gè)檢索式代表了相同或者相似的搜索需求；（2）如果用戶通過(guò)兩個(gè)不同的檢索式訪問(wèn)了相同的網(wǎng)頁(yè)，那么這兩個(gè)檢索式具有一定程度的相似性。兩個(gè)檢索式、的相似度計(jì)算方法如下：其中是檢索式中擁有的關(guān)鍵詞數(shù)目，是檢索式、共有的關(guān)鍵詞數(shù)目。這種算法對(duì)每個(gè)用戶輸入的檢索詞及其對(duì)搜索結(jié)果的訪問(wèn)情況進(jìn)行記錄，并且依據(jù)上述假設(shè)對(duì)搜索結(jié)果進(jìn)行相似度計(jì)算，對(duì)相似度大于閾值的搜索結(jié)果歸于同一個(gè)類(lèi)目下HYPERLINK[18]。上述3種網(wǎng)頁(yè)聚類(lèi)方法各有利弊，一般來(lái)說(shuō)，它們會(huì)在聚類(lèi)搜索引擎中結(jié)合使用。

聚類(lèi)搜索引擎設(shè)計(jì)從總體結(jié)構(gòu)上講，本文所設(shè)計(jì)系統(tǒng)由三層組成：第一層是系統(tǒng)接口層；第二層是信息聚類(lèi)層，負(fù)責(zé)文本聚類(lèi)算法的實(shí)現(xiàn)乃至形成最終結(jié)果的職責(zé)，起著代理與聚類(lèi)處理承上啟下的雙重作用；第三層是數(shù)據(jù)源層，位于服務(wù)器端，負(fù)責(zé)數(shù)據(jù)獲取，是系統(tǒng)與Internet的接口。聚類(lèi)搜索引擎系統(tǒng)的結(jié)構(gòu)如圖4-1所示。圖4-1聚類(lèi)搜索引擎系統(tǒng)的模塊結(jié)構(gòu)4.1數(shù)據(jù)源預(yù)處理考慮硬盤(pán)存儲(chǔ)、服務(wù)器硬件條件等各方面條件限制，本文采用從yahoo獲取數(shù)據(jù)的方式解決處理數(shù)據(jù)源的問(wèn)題。系統(tǒng)通過(guò)元搜索引擎的方式獲取信息，即將用戶提出的查詢(xún)轉(zhuǎn)交給其它搜索引擎（如google或yahoo），調(diào)用Web上現(xiàn)有的搜索引擎，通過(guò)對(duì)結(jié)果的合并和整理來(lái)得到檢索結(jié)果的一種方式。其實(shí)現(xiàn)既不需要網(wǎng)絡(luò)爬蟲(chóng)程序，也不需要使用復(fù)雜的檢索機(jī)制，但元搜索引擎提供了一個(gè)可以同時(shí)查詢(xún)多個(gè)搜索引擎的統(tǒng)一接口，將各個(gè)搜索引擎的位置，接口等細(xì)節(jié)屏蔽起來(lái)。它的特點(diǎn)在于不必對(duì)整個(gè)網(wǎng)絡(luò)進(jìn)行掃描，減小了網(wǎng)絡(luò)的流量和機(jī)器的負(fù)荷，同時(shí)提高了檢索的廣度、召回率和精度。該系統(tǒng)通過(guò)元搜索引擎原理的運(yùn)用滿足“在線”要求，完成了信息獲取的過(guò)程。為了提高信息獲取的速度，系統(tǒng)需要以多線程的方式做并行元搜索，即并行地調(diào)用多個(gè)搜索引擎。因?yàn)樗阉饕嬉话阃ㄟ^(guò)動(dòng)態(tài)生成的網(wǎng)頁(yè)返回搜索結(jié)果，然而搜索結(jié)果往往很多，必須多個(gè)網(wǎng)頁(yè)來(lái)顯示。如果系統(tǒng)串行地從一個(gè)搜索引擎取回其搜索結(jié)果網(wǎng)頁(yè)，就需要較長(zhǎng)的網(wǎng)絡(luò)通信時(shí)間，因此系統(tǒng)就通過(guò)多線程并行調(diào)用多個(gè)搜索引擎來(lái)達(dá)到更高的并行度，提高系統(tǒng)的運(yùn)行效率。由于對(duì)同一個(gè)查詢(xún)來(lái)說(shuō)不同的搜索引擎返回的搜索結(jié)果列表有所不同，一項(xiàng)結(jié)果往往只在某些搜索結(jié)果列表中出現(xiàn)，而且往往出現(xiàn)在不同的位置。對(duì)于這種情況系統(tǒng)需要將來(lái)自各個(gè)搜索引擎的搜索結(jié)果列表綜合起來(lái)，先削除里面的重復(fù)項(xiàng)，再對(duì)其重新排序形成一個(gè)統(tǒng)一的搜索結(jié)果列表，以提高信息檢索的精度(precision)。并將得到的文本數(shù)據(jù)進(jìn)行切詞處理，利用中文分詞算法將這些文本切分為多個(gè)詞語(yǔ)，優(yōu)先選擇長(zhǎng)度較長(zhǎng)的文字進(jìn)行匹配切詞。分析標(biāo)題、摘要，選取最能表現(xiàn)文本特征的詞或詞對(duì)，用以建立對(duì)應(yīng)的索引，其中包括去除表現(xiàn)力不強(qiáng)的詞HYPERLINK[19]。采用的是基于字符串匹配的分詞方法。這種方法又叫做機(jī)械分詞方法它是按照一定的策略將待分析的漢字串與分詞詞典中的詞條進(jìn)行匹配，若在詞典中找到某個(gè)字符串，則匹配成功(識(shí)別出一個(gè)詞)。按照掃描方向的不同，串匹配分詞方法可以分為正向匹配和逆向匹配；按照不同長(zhǎng)度優(yōu)先匹配的情況可以分為最大(最長(zhǎng))匹配和最小(最短)匹配，優(yōu)先選擇長(zhǎng)度較長(zhǎng)的文字進(jìn)行匹配切詞；按照是否與詞性標(biāo)注過(guò)程相結(jié)合，又可以分為單純分詞方法和分詞與標(biāo)注相結(jié)合的一體化方法。采用的最大逆向單純分詞方法，實(shí)驗(yàn)表明:對(duì)于漢語(yǔ)來(lái)說(shuō)，該方法是最有效的。初步分詞包括：1）原子切分；2）找出原子之間所有可能的組詞方案；例如：“他說(shuō)的確實(shí)在理”這句話。（1）原子切分的目的是完成單個(gè)漢字的切分。經(jīng)過(guò)原子切分后變成“始##始/他/說(shuō)/的/確/實(shí)/在/理/末##末”。（2）然后根據(jù)“詞庫(kù)字典”找出所有原子之間所有可能的組詞方案。經(jīng)過(guò)詞庫(kù)檢索后，該句話變?yōu)椤笆?#始/他/說(shuō)/的/的確/確/確實(shí)/實(shí)/實(shí)在/在/在理/末##末”。4.2索引的建立索引的建立對(duì)于搜索的性能影響重大，本系統(tǒng)采用的建立索引模型為倒排文件模型（InvertedFilesList）。倒排文件模型是將文本看成一組單個(gè)字符或者一些詞的有序串聯(lián)HYPERLINK[20]，是面向單個(gè)字符或詞的思想。倒排表方法直觀，創(chuàng)建效率高，維護(hù)相對(duì)容易，所以本系統(tǒng)使用倒排表模型來(lái)抽取關(guān)鍵短語(yǔ)。在一些全文檢索系統(tǒng)中也以倒排表作為索引模型。倒排表是一些二元組的集合，它的第一個(gè)元素是索引項(xiàng)，基于詞的特征表示中，索引項(xiàng)指的是詞，第二個(gè)元素是該索引項(xiàng)在文本集中出現(xiàn)的所有位置，因此從倒排表可以很快得到每個(gè)索引項(xiàng)在文本集中出現(xiàn)的所有位置。倒排表空間開(kāi)銷(xiāo)與索引項(xiàng)和位置的定義密切相關(guān)。由于在全文檢索系統(tǒng)中文本集巨大，倒排表的索引項(xiàng)包括全部漢語(yǔ)詞條。清華版的常用詞表有13萬(wàn)常用詞，專(zhuān)業(yè)詞表采用《中國(guó)分類(lèi)主題詞表》也有6萬(wàn)主題詞，如果包括全部的漢語(yǔ)詞條系統(tǒng)的空間開(kāi)銷(xiāo)很大，但是索引項(xiàng)可以按照既定的順序分配地址，在動(dòng)態(tài)使用中，索引項(xiàng)不用再排序。由于文檔集的大小范圍變化比較大，小到個(gè)數(shù)位，最大可達(dá)到幾十萬(wàn)數(shù)量級(jí)。因?yàn)闄z索結(jié)果和用戶的檢索條件一一對(duì)應(yīng)，不同的檢索條件將可能導(dǎo)致完全不同的檢索結(jié)果集，所以針對(duì)于每一次的檢索聚類(lèi)，都是不同的輸入數(shù)據(jù)集。倒排表既要適應(yīng)數(shù)據(jù)集的變化，節(jié)省空間開(kāi)銷(xiāo)，又要能迅速地創(chuàng)建，盡可能地實(shí)現(xiàn)高效率，還要考慮如何便于抽取關(guān)鍵短語(yǔ)。考慮到以上因素，本系統(tǒng)中的倒排表，索引項(xiàng)為單個(gè)詞匯或相鄰詞組，索引項(xiàng)指向的元素對(duì)象鏈表包括有共同索引項(xiàng)的檢索結(jié)果的類(lèi)對(duì)象中所有內(nèi)容。用于建立索引項(xiàng)的關(guān)鍵字或者關(guān)鍵點(diǎn)短語(yǔ)在計(jì)算相似度時(shí)起決定性作用。文檔的關(guān)鍵短語(yǔ)列表用于倒排索引的索引項(xiàng)，只有當(dāng)文檔之間至少有一個(gè)共有的索引項(xiàng)時(shí)，才計(jì)算它們的相似性，否則對(duì)應(yīng)的文檔之間相似性值為0。下面舉一個(gè)實(shí)例用以說(shuō)明該模型的原理和工作流程：設(shè)有兩篇文章1和2，內(nèi)容分別為：文章1：TomlivesinGuangzhou,IliveinGuangzhoutoo.文章2：HeoncelivedinShanghai.由于是基于關(guān)鍵詞索引和查詢(xún)的，首先我們要取得這兩篇文章的關(guān)鍵詞，通常我們需要如下處理措施：（1）根據(jù)已有的文章內(nèi)容，即一個(gè)字符串，我們先要找出字符串中的所有單詞，即分詞。英文單詞由于用空格分隔，比較好處理。中文單詞間是連在一起的需要特殊的分詞處理。（2）將不代表概念的詞可以過(guò)濾掉。文章中的“in”，“once”，“too”等詞沒(méi)有實(shí)際意義，中文中的“的”、“是”等字通常也無(wú)具體含義，可以將它們過(guò)濾掉。（3）所有單詞統(tǒng)一大小寫(xiě)。因?yàn)橛脩敉ǔＯＭ椤癏e”時(shí)能把含“he”，“HE”的文章也找出來(lái)。（4）將部分詞還原。用戶通常希望查“l(fā)ive”時(shí)能把含“l(fā)ives”，“l(fā)ived”的文章也找出來(lái)，所以需要把“l(fā)ives”，“l(fā)ived”還原成“l(fā)ive”。（5）過(guò)濾標(biāo)點(diǎn)符號(hào)。文章中的標(biāo)點(diǎn)符號(hào)通常不表示某種概念，也可以過(guò)濾掉。經(jīng)過(guò)上面處理后，兩篇文章所對(duì)應(yīng)的關(guān)鍵詞分別為：文章1的所有關(guān)鍵詞：tomliveguangzhouiliveguangzhou文章2的所有關(guān)鍵詞：heliveshanghai有了關(guān)鍵詞后，我們就可以建立倒排索引了。上面的對(duì)應(yīng)關(guān)系是：“文章號(hào)”對(duì)“文章中所有關(guān)鍵詞”。倒排索引把這個(gè)關(guān)系倒過(guò)來(lái)，變成：“關(guān)鍵詞”對(duì)“擁有該關(guān)鍵詞的所有文章號(hào)”。文章1、2經(jīng)過(guò)倒排后如表4-1所示。表4-1文章1和2經(jīng)過(guò)倒排處理后的結(jié)果關(guān)鍵詞文章號(hào)關(guān)鍵詞文章號(hào)guangzhou1he2i1live1,2shanghai2tom1通常僅知道關(guān)鍵詞在哪些文章中出現(xiàn)還不夠，還需要知道關(guān)鍵詞在文章中出現(xiàn)次數(shù)和出現(xiàn)的位置，通常有兩種位置：字符位置和關(guān)鍵詞位置。字符位置，即記錄該詞是文章中第幾個(gè)字符，其作用是關(guān)鍵詞亮顯時(shí)定位快；關(guān)鍵詞位置，即記錄該詞是文章中第幾個(gè)關(guān)鍵詞，其作用是節(jié)約索引空間、詞組查詢(xún)快。加上“出現(xiàn)頻率”和“出現(xiàn)位置”信息后，索引結(jié)構(gòu)如表4-2所示。表4-2文章1和2經(jīng)過(guò)加強(qiáng)處理后的倒排結(jié)果關(guān)鍵詞文章號(hào)[出現(xiàn)頻率]出現(xiàn)位置guangzhou1[2]3，6he2[1]1i1[1]4live1[2],2[1]2，5，2shanghai2[1]3tom1[1]1以live這行為例我們說(shuō)明一下該結(jié)構(gòu)：live在文章1中出現(xiàn)了2次，文章2中出現(xiàn)了一次，它的出現(xiàn)位置為“2，5，2”。結(jié)合文章號(hào)和出現(xiàn)頻率分析，其含義為文章1中出現(xiàn)了2次，那么“2，5”就表示live在文章1中出現(xiàn)的兩個(gè)位置，文章2中出現(xiàn)了一次，剩下的“2”該設(shè)計(jì)實(shí)現(xiàn)的索引接口、索引及結(jié)果封裝如下HYPERLINK[21]：namespaceIndex{publicclassIndexer:IIndex{privatestaticstringdeleteStr=".,。，()（）!！";privateconstdoubleTITLEWEIGHT=1.2;privateconstdoubleCONTENTWEIGHT=1;publicIndexer(){inerindex=newHashtable();urlindex=newHashtable();documentID=-1;}publicIndexTableGetIndex()publicvoidAddWordArray(WordResult[]title,WordResult[]wordArray,stringUrl){documentID++;urlindex.Add(documentID,Url);AddWordArray(title,FieldType.Title);AddWordArray(wordArray,FieldType.Content);}privatevoidAddWordArray(WordResult[]wordArray,FieldTypeft);}}4.3相似度計(jì)算根據(jù)搜索引擎返回的結(jié)果文檔的標(biāo)題、URL和摘要信息進(jìn)行聚類(lèi)，則先需要通過(guò)相似度函數(shù)計(jì)算返回結(jié)果之間的相似性，然后根據(jù)相似性密度評(píng)價(jià)標(biāo)準(zhǔn)來(lái)聚類(lèi)。本方案將檢索結(jié)果之間的相似度關(guān)系映射為無(wú)向圖，然后再根據(jù)節(jié)點(diǎn)之間的距離決定其是否在同一個(gè)簇類(lèi)當(dāng)中。根據(jù)類(lèi)之間依賴(lài)性處理，從而使得相互聯(lián)系比較緊密的對(duì)象能夠放在同一個(gè)簇類(lèi)中。由檢索結(jié)果之間的相似性矩陣，將每個(gè)文本以及它們之間的相似度關(guān)系映射成無(wú)向圖，每個(gè)文本對(duì)應(yīng)圖中的一個(gè)點(diǎn)，兩個(gè)點(diǎn)之間帶有權(quán)值的邊表示文本之間超過(guò)一定閥值的相似度的值，只有兩個(gè)結(jié)果之間的相似度大于一定的閥值，才構(gòu)成一條邊；如圖4-2所示：圖4-2使用相似度為權(quán)重的無(wú)向圖由上一節(jié)所介紹的倒排文檔結(jié)構(gòu)可知:倒排表模型非常有利于相似性矩陣的計(jì)算，通過(guò)掃描遍歷倒排表，我們只計(jì)算有共同索引項(xiàng)的相似度的值，其余沒(méi)有共同索引項(xiàng)相似度值為0，從而節(jié)省了計(jì)算時(shí)間，大大提高了效率。具體的相似度計(jì)算算法過(guò)程如下：（1）初始化相似性矩陣，令Sim[i,j]=0；（2）遍歷倒排表，文本相似度矩陣；（3）計(jì)算Sim值。計(jì)算索引項(xiàng)1在網(wǎng)頁(yè)i文本中的權(quán)重公式為：Tweigh[i]=(索引出現(xiàn)次數(shù)*W0+索引在標(biāo)題文本中出現(xiàn)次*W1)，其中W0和W1分別為索引項(xiàng)出現(xiàn)在文本正文中和出現(xiàn)在標(biāo)題處的權(quán)重。文本相似度矩陣TR[i,j]的計(jì)算公式為：TR[i,j]=TR[i,j]+（TWeigh[i]/TSnip[i].num+Weigh[j]/TSnip[j].num），其中num為出現(xiàn)次數(shù)。URL相似度矩陣計(jì)算采用字符串比較的方式，使用一級(jí)域名掃描。如：http://www./sports/basketball與/sports/football。其URL地址http://www.sina.com相同，則繼續(xù)掃描，/sports相同，但后續(xù)部分不一樣，則掃描到該斷停止，于是有：UR[i,j]=1+1+0。Sim矩陣的具體計(jì)算公式如下：Sim[i,j]=p*TR[i,j]+q*UR[i,j]，其中UR[i,j]為URL相似度矩陣,p、q為調(diào)整系數(shù)。4.4聚類(lèi)處理算法接受輸入量k；然后將n個(gè)數(shù)據(jù)對(duì)象劃分為k個(gè)聚類(lèi)以便使得所獲得的聚類(lèi)滿足：同一聚類(lèi)中的對(duì)象相似度較高，而不同聚類(lèi)中的對(duì)象相似度較小。聚類(lèi)相似度是利用各聚類(lèi)中對(duì)象的均值所獲得一個(gè)“中心對(duì)象”來(lái)進(jìn)行計(jì)算的。采用模糊聚類(lèi)方式，對(duì)于一個(gè)定點(diǎn)，并不一定只屬于某一類(lèi)，而可能屬于某兩個(gè)甚至更多的類(lèi)，這樣也符合聚類(lèi)的目的和需求。（1）從n個(gè)數(shù)據(jù)對(duì)象任意選擇k－1個(gè)對(duì)象作為初始聚類(lèi)中心；（2）根據(jù)每個(gè)聚類(lèi)對(duì)象的質(zhì)心，從剩余對(duì)象中任意選取一個(gè)計(jì)算它與這些中心對(duì)象的距離；通過(guò)比較其相似度與所選取的閥值T判斷對(duì)相應(yīng)對(duì)象進(jìn)行劃分；當(dāng)該對(duì)象與聚類(lèi)中心的相似度大于閥值時(shí)，該對(duì)象屬于這一聚類(lèi)，若某一對(duì)象不屬于前k－1類(lèi)，則將其劃分為第k類(lèi)；（3）重復(fù)步驟（2）直到所有點(diǎn)都處理完為止。其主要算法為：classQueue{public:Queue(intsz){size=sz+1;rear=front=0;listArray=newdouble[size];}~Queue(){ delete[]listArray;}voidclear(){ front=rear;}boolenqueue(constdouble&it){if((rear+1)%size==front) returnfalse;listArray[rear]=it;rear=(rear+1)%size;returntrue;}virtualintlength()constbooldequeue(double&it){if(length()==0) returnfalse;it=listArray[front];front=(front+1)%size;returntrue;}boolfrontValue(double&it)const{if(length()==0) returnfalse;it=listArray[front];returntrue;}};classGraphm{public: Graphm(intnumVert,string*vmark,intk,double**Synphor){ inti=0; intj=0; numVertex=numVert;//對(duì)頂點(diǎn)數(shù)進(jìn)行賦值 numEdge=numVert*(numVert-1)/2;//對(duì)邊數(shù)進(jìn)行賦值 mark=(string*)newint[k];//為標(biāo)記數(shù)組申請(qǐng)空間 for(i=0;i<k;i++) mark[i]=vmark[i];//對(duì)標(biāo)記數(shù)組進(jìn)行賦值 matrix=(double**)newint*[numVert];//為存儲(chǔ)數(shù)組申請(qǐng)空間 for(i=0;i<numVert;i++) matrix[i]=(double*)newint[numVert]; for(i=0;i<numVert;i++) for(j=0;j<numVert;j++) matrix[i][j]=Synphor[i][j];//對(duì)存儲(chǔ)數(shù)組進(jìn)行賦值 }//構(gòu)造函數(shù)完成，且運(yùn)行沒(méi)有錯(cuò)誤 ~Graphm(){ delete[]mark; for(inti=0;i<numVertex;i++) delete[]matrix[i]; delete[]matrix; } doubleweight(intv1,intv2){ returnmatrix[v1][v2]; } stringgetmark(intv){ returnmark[v%numVertex]; } voidsetmark(intv,stringvalue){ mark[v%numVertex]=value; } intfirst(intstart){ inti=0; for(i=0;i<numVertex;i++) if(!matrix[start][i]) returni; returni; } intnext(intstart,intfirst){ inti=0; for(i=first+1;i<numVertex;i++) if(matrix[start][i]) returni; } voidsetEdge(intv1,intv2,doublewgt)//在兩個(gè)搜索結(jié)果之間設(shè)置相似度 voidCreatweiRandomCenterArray(intk){ inti=0; intj=0; for(i=0;i<k;i++) Center[i]=0; srand((unsigned)time(NULL)); for(i=0;i<k;i++){ inta=rand()%numVertex; for(j=0;j<i;j++){ if(Center[j]==a) break;//判重 elseif(j>i&&Dijkstra(a,j)<T[j]) Center[i]=a; else i--; } } }//至此建立了一個(gè)質(zhì)心 doubleDijkstra(intstart,intdestination)//最短路徑算法 voidBFS(intstart,Queue*Q){ doublev=0;intw=0; stringt=""; Q->enqueue(start); setmark(start,mark[start%numVertex]); while(Q->length()){ Q->dequeue(v); for(w=first(start);w<n();w=next(start,w)){ t=getmark(w); if(&t==&mark[0]&&(weight(start,w)>T[start%numVertex])) setmark(w,mark[w%numVertex]); AddToCluster(start,w);//這里進(jìn)行聚類(lèi) } } } voidUpdateCenter(intk) voidAddToCluster(intindex,intadder){ Cluster[index%numVertex][Top[index]++]=matrix[index][adder]; }//聚類(lèi)函數(shù) voidCopyCenter(intk){ for(inti=0;i<k;i++) CenterCopy[i]=Center[i]; }};

5.性能分析為了對(duì)聚類(lèi)算法的性能進(jìn)行評(píng)價(jià)，很多研究都是利用多種聚類(lèi)方法對(duì)同一個(gè)數(shù)據(jù)集進(jìn)行聚類(lèi)，根據(jù)最終的結(jié)果比較其優(yōu)劣。如：把聚類(lèi)結(jié)果同經(jīng)過(guò)專(zhuān)家人工分類(lèi)的結(jié)果對(duì)照，然而（即使是在實(shí)驗(yàn)條件下，也很難評(píng)估一個(gè)聚類(lèi)算法）對(duì)聚類(lèi)算法性能的評(píng)價(jià)是一個(gè)相當(dāng)困難的問(wèn)題，因?yàn)槊總€(gè)方法算法都有不同的屬性和著重點(diǎn)，實(shí)驗(yàn)研究很難給對(duì)不同的聚類(lèi)算法給出一個(gè)綜合的評(píng)價(jià)HYPERLINK[22]。5.1理論分析本文從如下幾個(gè)方面考慮所設(shè)計(jì)系統(tǒng)的性能：（1）時(shí)間和空間需求 在處理大型數(shù)據(jù)集時(shí)，必須考慮聚類(lèi)分析中的需求資源。該系統(tǒng)在空間占有上主要是文檔的存儲(chǔ)和文檔之間相似性矩陣的存儲(chǔ)。時(shí)間上主要是計(jì)算需求集中在求相似性矩陣，而倒排文檔索引結(jié)構(gòu)大大簡(jiǎn)化了計(jì)算量，它只需計(jì)算有共同索引特征項(xiàng)的檢索結(jié)果之間的相似性就可以了，所以相似性的計(jì)算既依賴(lài)于文檔集特征項(xiàng)的選取范圍，還依賴(lài)于有共同特征項(xiàng)的結(jié)果。針對(duì)于特征項(xiàng)的選取范圍，我們分別對(duì)40條和80條“湖南大學(xué)”的檢索結(jié)果以及40條“軟件工程”的檢索結(jié)果進(jìn)行了關(guān)鍵短語(yǔ)與簡(jiǎn)單分詞之間的對(duì)比試驗(yàn)，以關(guān)鍵詞作為特征項(xiàng)是指只對(duì)檢索結(jié)果進(jìn)行分詞、過(guò)濾、去除無(wú)用詞和高頻詞低頻詞，不進(jìn)行聯(lián)合詞組的組合的單個(gè)詞匯最為特征項(xiàng)，試驗(yàn)結(jié)果如下表6-1所示:表5-1單個(gè)詞匯與關(guān)鍵短語(yǔ)特征項(xiàng)對(duì)比表測(cè)試對(duì)象類(lèi)別40條“湖南大學(xué)”80條“湖南大學(xué)”40條“軟件工程”關(guān)鍵詞180417193關(guān)鍵短語(yǔ)161349239通過(guò)試驗(yàn)可以看出，采用關(guān)鍵短語(yǔ)的方法不但沒(méi)有增加特征項(xiàng)數(shù)目，反倒比簡(jiǎn)單分詞的特征項(xiàng)數(shù)目稍微少一些，可見(jiàn)采用關(guān)鍵短語(yǔ)的方法并沒(méi)有增加計(jì)算量。并且隨著檢索結(jié)果數(shù)目的增加，特征項(xiàng)由于受到整體詞匯量的限制，增加到一定程度后將不再隨檢索結(jié)果的增加而大幅增加，這對(duì)提高檢索性能有著很大的積極作用。（2）網(wǎng)頁(yè)多主題特性 一般而言一個(gè)網(wǎng)頁(yè)的內(nèi)容可能同時(shí)涉及幾方面的主題，聚類(lèi)算法應(yīng)該能適當(dāng)?shù)目紤]這種屬性。本文提出的聚類(lèi)算法允許簇類(lèi)中元素有重疊，屬于模糊聚類(lèi)，實(shí)驗(yàn)表明這種結(jié)果符合檢索結(jié)果可能分屬不同主題的實(shí)際情況。與之相反，在文獻(xiàn)xx中提到的xxx聚類(lèi)算法則沒(méi)有考慮文檔的多主題特性。（3）孤立點(diǎn)處理 在數(shù)據(jù)集中，常常存在一些數(shù)據(jù)對(duì)象，它們不符合數(shù)據(jù)的一般模型，即與數(shù)據(jù)的其他部分(往往是大部分)不同或不一致，我們稱(chēng)這樣的數(shù)據(jù)對(duì)象為孤立點(diǎn)。搜索引擎返回的網(wǎng)頁(yè)中存在相當(dāng)多的孤立點(diǎn)的情況，一種好的聚類(lèi)算法應(yīng)該能夠有效地處理孤立點(diǎn)的情況。本系統(tǒng)中將相似度不滿足閥值要求的孤立點(diǎn)做為一類(lèi)整體簇類(lèi)處理，避免其影響整體聚類(lèi)結(jié)果。但該系統(tǒng)在選詞特征項(xiàng)的選取和聚類(lèi)名稱(chēng)的有效性方面，該系統(tǒng)還需要改進(jìn)。5.2系統(tǒng)演示本文設(shè)計(jì)實(shí)現(xiàn)了一個(gè)基于聚類(lèi)的搜索引擎原型系統(tǒng)，利用該系統(tǒng)進(jìn)行信息檢索的過(guò)程可以演示如下。實(shí)際使用時(shí)，只需要在輸入框中輸入要檢索的關(guān)鍵詞即可返回分類(lèi)后的結(jié)果。用戶登陸系統(tǒng)網(wǎng)站，會(huì)顯示如下登陸界面：圖5-1用戶登陸界面本系統(tǒng)默認(rèn)顯示第一簇類(lèi)的網(wǎng)頁(yè)信息，輸入關(guān)鍵字“軟件工程”后返回的結(jié)果顯示如下圖5-2所示：圖5-2用戶搜索關(guān)鍵字顯示頁(yè)面在頁(yè)面最左邊既是本系統(tǒng)經(jīng)過(guò)聚類(lèi)后顯示的結(jié)果，系統(tǒng)默認(rèn)聚為六類(lèi)，每類(lèi)的類(lèi)名由系統(tǒng)根據(jù)文本片斷中出現(xiàn)頻率最高的關(guān)鍵詞自動(dòng)指定。點(diǎn)擊左邊“示范性”一欄顯示結(jié)果如下圖5-3所示，從中我們可以看出，所指定的類(lèi)名和聚類(lèi)后返回的顯示網(wǎng)頁(yè)內(nèi)容邏輯關(guān)聯(lián)較為緊密。圖5-3點(diǎn)擊某一聚類(lèi)欄顯示信息總結(jié)本文提出并設(shè)計(jì)了一種聚類(lèi)搜索引擎的方案，幫助Web用戶從搜索引擎所返回的大