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

一、前言

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

一個(gè)粗略但得到廣泛認(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í)包含給定術(shù)語組合的文檔，類似于關(guān)系表上使用的查詢類型。

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

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

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

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

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

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

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

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

二、相關(guān)工作

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

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

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

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

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

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

三、索引

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

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

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

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

四、聚類

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

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

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

五、結(jié)論

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