文本檢索的聚類分布式索引

劉宇松 江蘇經(jīng)貿(mào)職業(yè)技術(shù)學(xué)院

一、前言

隨著信息技術(shù)的發(fā)展，各種數(shù)據(jù)的可用性呈爆炸性增長。它帶來了一個前所未有的機(jī)會，可以開發(fā)自動數(shù)據(jù)驅(qū)動的技術(shù)來提取有用的知識，這就產(chǎn)生了數(shù)據(jù)挖掘的概念。數(shù)據(jù)挖掘是知識發(fā)現(xiàn)過程中的一個重要步驟，它由發(fā)現(xiàn)知識的方法組成隱藏在數(shù)據(jù)中的有趣、非平凡和有用的模式。大量的非結(jié)構(gòu)化文檔在許多領(lǐng)域都是可用的，當(dāng)我們使用網(wǎng)絡(luò)時，可以從世界各地檢索文檔。為了檢索到對用戶有用的信息，必須移動大量文本。快速有效的聚類是無監(jiān)督學(xué)習(xí)的基本工具?，F(xiàn)在已經(jīng)開發(fā)出了各種方法來支持對文本文檔集合的高效搜索和檢索，包括后綴數(shù)組、倒排文件或倒排索引和簽名文件等。

一個粗略但得到廣泛認(rèn)可的框架是，根據(jù)生成的聚類的屬性，將聚類技術(shù)分為層次聚類和分區(qū)聚類。距離度量必須根據(jù)數(shù)據(jù)的基本形狀進(jìn)行適當(dāng)選擇，無論是球形數(shù)據(jù)還是橢球數(shù)據(jù)。查詢可以是布爾查詢，也可以是排序查詢。布爾查詢由邏輯運(yùn)算符AND、OR和NOT連接的術(shù)語組成，可用于標(biāo)識包含給定術(shù)語組合的文檔，類似于關(guān)系表上使用的查詢類型。

另一方面，排名是一個將非正式查詢與文檔相匹配的過程，并根據(jù)文檔與查詢的相似程度為文檔分配分?jǐn)?shù)。主要問題是組織和存儲大量數(shù)據(jù)。當(dāng)對這些數(shù)據(jù)進(jìn)行搜索時，搜索的質(zhì)量應(yīng)該非常好。搜索還應(yīng)具有成本效益和時間效益，非常重要的是，搜索查詢得到的結(jié)果應(yīng)該與我們實(shí)際搜索的結(jié)果相同。

有相關(guān)學(xué)者開發(fā)出了用于多臺計算機(jī)上數(shù)據(jù)挖掘的可伸縮并行聚類模型。他們在并行機(jī)上設(shè)計并實(shí)現(xiàn)了自動分類，這是一個基于貝葉斯方法的自動分類系統(tǒng)的并行版本，用于確定大型數(shù)據(jù)集中的最佳類。特別是順序自動分類系統(tǒng)的效率和可擴(kuò)展性也通過它們進(jìn)行了評估和比較。

文本搜索和信息檢索在現(xiàn)代計算中起著非常重要的作用。這可以通過谷歌、雅虎、瑞迪夫等高效搜索引擎實(shí)現(xiàn)。搜索引擎是在集合中查找與用戶查詢匹配良好的文檔的工具。典型的文件收集類型包括網(wǎng)頁、報紙文章、學(xué)術(shù)出版物、公司報告、研究資助申請、手冊頁、百科全書、議會議事錄、參考書目、歷史記錄、電子郵件和法庭記錄等。

一位研究人員在十年內(nèi)撰寫的一整套論文的純文本可能會占用10兆字節(jié)，而同一位研究人員的（純文本、非垃圾郵件）10年電子郵件存檔可能會占用100兆字節(jié)。隨著時間的推移，收藏的變化方式也有所不同。一個新聞專線檔案館或數(shù)字圖書館可能會增長緩慢，也許每天會增長幾千份文檔；刪除很少。

相反，Web集合可以是高度動態(tài)的。許多相同的搜索和存儲技術(shù)對這些集合很有用。文本并不是存儲在文檔集合中的唯一一種內(nèi)容。研究論文和報紙文章包括圖片，電子郵件包括附件，網(wǎng)絡(luò)收藏包括音頻和視頻格式。

為了解決這個問題，許多研究人員在他們的論文中提出了幾種方法。其中一種方法是排名。排名是將查詢與文檔匹配，并根據(jù)文檔的相似度為文檔分配分?jǐn)?shù)的過程。另一種方法是聚類過程。聚類是將對象組織成組的過程，這些組的成員在某種程度上是相似的。

搜索引擎在結(jié)構(gòu)上類似于數(shù)據(jù)庫系統(tǒng)。文檔存儲在存儲庫中，并維護(hù)索引。通過處理索引來評估查詢，以識別匹配項，然后將匹配項返回給用戶。然而也有許多不同之處。數(shù)據(jù)庫系統(tǒng)必須處理任意復(fù)雜的查詢，而對搜索引擎的查詢是術(shù)語和短語的列表。在數(shù)據(jù)庫系統(tǒng)中，匹配是滿足指定邏輯條件的記錄；在搜索引擎中，匹配是根據(jù)統(tǒng)計啟發(fā)法適合查詢的文檔，甚至可能不包含所有查詢詞。

數(shù)據(jù)庫系統(tǒng)返回所有匹配的記錄；搜索引擎返回固定數(shù)量的匹配項，這些匹配項按其統(tǒng)計相似性排序。數(shù)據(jù)庫系統(tǒng)為每個記錄分配一個唯一的訪問密鑰，并允許對該密鑰進(jìn)行搜索；對于在web集合上進(jìn)行查詢，可能會有數(shù)百萬個與查詢具有非零相似性的文檔。因此，當(dāng)搜索引擎如果沒有關(guān)系連接等操作的相關(guān)成本，快速響應(yīng)會有很大的障礙，也就是說，查詢術(shù)語可能出現(xiàn)在大量文檔中，并且每個文檔通常包含大量術(shù)語。文本搜索帶來的挑戰(zhàn)導(dǎo)致了一系列算法和數(shù)據(jù)結(jié)構(gòu)的發(fā)展。這些包括文本索引表示、索引構(gòu)造技術(shù)和文本查詢評估算法。

二、相關(guān)工作

索引對于搜索引擎提供快速響應(yīng)至關(guān)重要。通過使用壓縮和仔細(xì)的組織，索引所需的空間以及查詢評估期間所需的時間和磁盤流量減少到以前需求的一小部分。因此，考慮到上述所有參數(shù)，我們嘗試開發(fā)一種新的方法，通過使用C語言開發(fā)代碼來改進(jìn)聚集分布索引，這是本文的重點(diǎn)。

我們使用Leader算法對我們獲得的海量數(shù)據(jù)進(jìn)行聚類。在搜索時，我們不必搜索整個數(shù)據(jù)，而只需搜索集群。這是使用集群的最大優(yōu)勢。通過聚類，搜索變得既經(jīng)濟(jì)又省時。因此，我們在搜索技術(shù)中使用了聚類。我們搜索引擎的輸入是從幾本書中收集的數(shù)據(jù)。我們收集了不同地區(qū)幾本書的目錄。我們首先壓縮通過使用詞干和停止等方法獲得的原始數(shù)據(jù)。

停止將各種內(nèi)容表作為輸入，對其進(jìn)行處理，并給出不包含停止字的輸出。停止詞包括重復(fù)詞或功能詞，在數(shù)據(jù)庫中存儲時不太重要，但可能只會占用內(nèi)存。因此，在進(jìn)一步處理這些單詞以供后續(xù)階段使用之前，這些單詞將被刪除或清除。

將輸入語句送入停止模塊，我們獲得的輸出沒有標(biāo)點(diǎn)符號，并且刪除了常見的單詞。下一個階段采用無停止詞列表作為輸入?；締卧~被存儲，該單詞的其他形式被清除，從而節(jié)省了內(nèi)存空間，同時也提高了搜索技術(shù)的效率。這些停止、阻塞和案例折疊的步驟都是預(yù)處理階段的一部分，在預(yù)處理階段中，初始數(shù)據(jù)在實(shí)際處理之前被清理。

為了有效處理高流量的用戶查詢，我們使用分布式反向索引。倒排文件由一個詞匯表和一組發(fā)布列表組成。詞匯表包含測試集合中的一組相關(guān)術(shù)語，這些術(shù)語按字母順序排列。這些術(shù)語中的每一個都與包含文檔標(biāo)識符以及用于排名目的的附加數(shù)據(jù)的發(fā)布列表相關(guān)聯(lián)。要解決查詢，需要獲取與查詢條件相關(guān)聯(lián)的文檔集，然后對這些文檔進(jìn)行排序，以便選擇排名前“K”的文檔作為查詢答案。

根據(jù)詞匯表中單詞之間的距離，相似的單詞會聚集在一起。根據(jù)詞匯表的大小和文檔的類型，存在幾個集群。線程（輕量級進(jìn)程）應(yīng)用于單個集群。令人驚訝的是，我們的結(jié)果顯示，通過使用集群和并行的概念，搜索變得更具成本效益、時間效益，并且搜索質(zhì)量變得更準(zhǔn)確。我們的結(jié)果表明，該策略能夠在大規(guī)模和小型搜索引擎中產(chǎn)生有效的性能。

三、索引

為了避免每次查詢對文本語料庫進(jìn)行線性掃描，我們提前對文檔進(jìn)行索引。為了獲得索引的速度優(yōu)勢，我們還需要提前執(zhí)行文檔索引。進(jìn)行此操作所需的主要步驟如下：收集要編制索引的文檔；將文本標(biāo)記化，將文檔拆分為標(biāo)記；生成索引術(shù)語的列表；創(chuàng)建由列表和詞匯表組成的倒排索引。

矩陣表示法：這是術(shù)語相對于各種文檔的表示法。我們可以使用一些距離度量來計算兩個單詞之間的距離，如歐幾里德距離。

術(shù)語文檔關(guān)聯(lián)矩陣：索引總是從術(shù)語映射回文檔中出現(xiàn)術(shù)語的部分。我們有一本術(shù)語詞典，通常按字母順序排序。對于每個術(shù)語，我們都有一個列表，記錄該術(shù)語出現(xiàn)的文檔。列表中的每一項都記錄了文檔中出現(xiàn)的術(shù)語稱為“郵件列表”，該列表稱為“發(fā)布列表”。

字典通常保存在內(nèi)存中，而發(fā)帖列表通常保存在磁盤上。對于內(nèi)存中的發(fā)布列表，我們使用了單鏈接列表。郵件列表包含以下字段：第一個字段表示該術(shù)語在文檔中出現(xiàn)的頻率。第二個字段表示文檔標(biāo)識（文檔id），第三個字段指向下一個列表。

四、聚類

聚類是將對象組織成員在某種程度上相似的組的過程。簇是相互“相似”且與屬于其他簇的對象“不同”的對象的集合。一個粗略但得到廣泛認(rèn)可的框架是根據(jù)生成的聚類的屬性將聚類技術(shù)分為層次聚類和分區(qū)聚類。

該技術(shù)使用了4種不同的方法，即搜索、聚類、反向索引和預(yù)處理（停止和詞干分析）。聚類算法將數(shù)據(jù)項分為若干組，以便相似的項歸入同一組。這是在沒有任何外部主管建議的情況下完成的，課程和培訓(xùn)示例不適用先驗的。大多數(shù)早期的聚類分析算法來自統(tǒng)計領(lǐng)域，最初是為相對較小的數(shù)據(jù)集設(shè)計的。

近年來，聚類算法得到了擴(kuò)展，能夠有效地在大型數(shù)據(jù)庫中進(jìn)行知識發(fā)現(xiàn)，其中一些算法能夠處理高維特征項。當(dāng)用于對大型數(shù)據(jù)集進(jìn)行分類時，聚類算法的計算要求很高，需要高性能的機(jī)器在合理的時間內(nèi)得到結(jié)果。

五、結(jié)論

本文提出了一種利用線程獲取聚類分布式索引的新方法。使用集群上的線程進(jìn)行搜索比順序搜索更快。此外，這是有道理的結(jié)果表明，與順序搜索或線程搜索相比，使用集群進(jìn)行搜索所需的時間更少。當(dāng)然，線程有助于提高文本檢索的性能，因為搜索查詢所需的時間更少。但是，使用線程的基于集群的搜索進(jìn)一步改進(jìn)了搜索結(jié)果，因為相關(guān)的術(shù)語可以一起找到。我們的結(jié)果還表明，提出的聚類和并行搜索的概念更具成本效益、時間效益和搜索質(zhì)量的準(zhǔn)確性。用于確定搜索索引的leader算法的優(yōu)點(diǎn)是，一次數(shù)據(jù)庫掃描，效率高和訪問時間非?？?。對于數(shù)據(jù)大小，使用基于群集的搜索這種方法對于不同的單詞大小產(chǎn)生了很好的索引結(jié)果，從而減少了搜索時間。在實(shí)際場景中，萬維網(wǎng)（www）正在使用非常大的數(shù)據(jù)集。因此，我們可以推斷，基于聚類的線程搜索花費(fèi)的時間最少，效率最高。