基于Hadoop框架的TF-IDF算法改進

李彬

（暨南大學 信息科學技術學院計算機科學系，廣東 廣州 510632）

TF-IDF（Term Frequency-Inverse Document Frequency）是一種用于資訊檢索與文本挖掘的常用加權技術[1]，用來評估單詞對于一個文件集或一個語料庫中的其中一份文件的重要程度。單詞的重要性隨著其在文件中出現(xiàn)的次數(shù)成正比增加，但同時會隨著其在語料庫中出現(xiàn)的頻率成反比下降。TF-IDF算法的各種形式常被搜索引擎、Web數(shù)據(jù)挖掘、文本分類及相似度計算等各種應用中，而這些應用往往是以處理海量數(shù)據(jù)的輸入為背景。因此，如何在海量數(shù)據(jù)中快速有效地計算出TF-IDF具有重要意義。

1 TF-IDF算法原理

在一份給定的文件里，詞頻 TF（Term Frequency）指的是某一個給定的詞語在該文件中出現(xiàn)的次數(shù)。對于在某一特定文件里的詞語ti來說，它的重要性可表示為：

式中，ni，j是該詞在文件 dj中的出現(xiàn)次數(shù)，而分母則是在文件dj中所有字詞的出現(xiàn)次數(shù)之和。

逆向文件頻率 IDF（Inverse Document Frequency）是一個詞語普遍重要性的度量。某一特定詞語的IDF，由總文件數(shù)目除以包含該詞語的文件的數(shù)目，再將得到的商取對數(shù)得到：

式中，|D|表示語料庫 中的文件總數(shù)，|{j：ti∈dj}|表 示包 含詞語ti的文件數(shù)目。

在式（1）、式（2）的基礎上，可得單詞的權重計算公式[2]：

某一特定文件內(nèi)的高詞語頻率以及該詞語在整個文件集合中的低文件頻率，可以產(chǎn)生出高權重的TFIDF。因此，TF-IDF傾向于過濾掉常見的詞語，保留重要的詞語。

2 Hadoop簡介

Hadoop是一個開源的可運行于大規(guī)模集群上的分布式并行編程框架，它主要由分布式文件系統(tǒng)HDFS和MapReduce計算模型構成。HDFS實現(xiàn)了文件的分布式存儲，它是MapReduce計算的數(shù)據(jù)載體[3-4]。MapReduce計算模型的核心是Map和Reduce兩個函數(shù)，這兩個函數(shù)由用戶負責實現(xiàn)，功能是按一定的映射規(guī)則將輸入的＜key，value＞對轉換成另一個或一批＜key，value＞對輸出[4-6]。HDFS與 MapReduce的關系如圖 1所示。

圖1 HDFS與MapReduce的關系

3 Hadoop框架下的TF-IDF算法研究與實現(xiàn)

Hadoop分布式計算的核心思想是分割任務，并行運行。從TF-IDF的計算公式可以看出，它非常適合用分布式計算求解。單詞詞頻TF只與它所在文檔的單詞總數(shù)及它在此文檔出現(xiàn)的次數(shù)有關。因此，可以通過分割數(shù)據(jù)，并行統(tǒng)計文檔中的單詞詞頻TF，加快計算速度。得到單詞詞頻TF后，單詞權重TF-IDF的計算取決于包含此單詞的文檔個數(shù)（因為文檔總數(shù)是一個常量）。因此，只要能確定包含此單詞的文檔個數(shù)，即能以并行計算的方式實現(xiàn)TF-IDF的求解。本文通過設計3次Map、Reduce過程實現(xiàn)TF-IDF的計算。

3.1 統(tǒng)計每份文檔中單詞的出現(xiàn)次數(shù)

原始數(shù)據(jù)經(jīng)過分片后傳給Map函數(shù)。在Map中使用正則表達式識別單詞，并以鍵值對＜word#documentName，1＞的形式寫入中間結果，傳入Reduce函數(shù)處理。在Reduce中計算單詞個數(shù)，并將結果輸出到臨時文件tempFile1中以作為下一步MapReduce計算的輸入。輸出結果是以＜word#documentName＞為鍵、＜n＞為值，n表示單詞word在文檔documentName中出現(xiàn)次數(shù)。函數(shù)設計如下：

此步計算得出單詞在文檔中的出現(xiàn)次數(shù)。

3.2 統(tǒng)計文檔單詞詞頻TF

上一步所得的臨時文件tmpFile1作為本次Map函數(shù)的輸入。在Map函數(shù)中，重新組織鍵值對 （以documentName為鍵、＜word=n＞為值）以便于下一步的Reduce計算。Reduce中，為計算每份文檔單詞總數(shù)，只需累加每份文檔的單詞數(shù)即可。輸出結果存入臨時文件tempFile2中以作為下一步MapReduce計算TF-IDF的輸入。函數(shù)設計如下：

此步計算得出每份文檔單詞詞頻TF。

3.3 計算TF-IDF

以上一步所得的臨時文件tmpFile2作為Map函數(shù)的輸入。在Map函數(shù)中，重新組織鍵值對（以單詞word為鍵、＜documentName=n/N＞為值）以便于計算單詞word在整個文檔集中出現(xiàn)的次數(shù)。Reduce函數(shù)中，統(tǒng)計出單詞word在文檔集中出現(xiàn)個數(shù)d、整個文檔集個數(shù)D，然后按公式 TF-IDF=n/N×log（D/d）計算單詞的 TF-IDF值。函數(shù)設計如下：

此步計算得出文檔集中每份文檔的單詞TF-IDF值。

計算TF-IDF的整個處理流程如圖2所示。

圖2 計算TF-IDF的整個處理流程

4 實驗與分析

（1）實 驗 數(shù) 據(jù) 獲 取 ：從 （http：//www.sogou.com/labs/）提供的文本分類語料庫中選取了20萬篇文檔作為實驗語料庫。

（2）數(shù)據(jù) 預 處 理 ：使 用開源中文分詞工具IKAnalyzer對文本進行分詞處理，同時去掉停用詞。維護過多的小文件會降低Hadoop效率，因此需將數(shù)據(jù)集歸檔處理。整理后的測試數(shù)據(jù)如表1所示。

（3）Hadoop群集的搭建：使用了 5臺電腦構建了一個群集，其中一臺作為主節(jié)點，以負責作業(yè)調度及文件空間的管理；其余的作為從節(jié)點用作TF-IDFSS的計算以及文件的存儲。

（4）實驗結果：將使用了Map/Reducer框架的TD_IDF算法與傳統(tǒng)的TF-IDF計算算法進行對比結果如圖3所示。傳統(tǒng)的TF-IDF計算算法只在一臺機上運行，且不能以并行和分布式的方式運行。

從圖中可以看出，當數(shù)據(jù)量不大時（＜200 MB），傳統(tǒng)算法與新算法的差距并不明顯。這是因為Hadoop本身的維護與網(wǎng)絡傳輸需要一定的開銷。隨著數(shù)據(jù)量的增大，傳統(tǒng)方法計算TF-IDF的時間急劇增長，而應用了Hadoop框架的TF-IDF計算方法所需時間只是線性增長，新算法的效率明顯高于傳統(tǒng)算法。

表1 測試數(shù)據(jù)

本文使用了Hadoop框架提供的服務改進了計算TF-IDF算法的效率。如果仍需要進一步提高算法效率，可以使用序列化文件SequenceFile對輸入數(shù)據(jù)做預處理[7]；對Mapper、Reducer的輸出做壓縮；減少中間文件的生成。此外，還可以通過擴展群集規(guī)模、改變?nèi)杭瘏?shù)等方式來提高效率。

[1]SALTON G，BUCKLEY C.Term-weighting approaches in automatic text retrieval [J]. Information Processing and Management， 1988， 24（5）：513-523.

[2]SALTON G， CLEMENT T Y.On theconstruction of effective vocabularies for information retrieval[C].Proceedings ofthe 1973 Meeting on Programming Languages and Information Retrieval.New York：ACM，1973.

[3]The apache softwar foundation HDFS architecture guide[EB/OL].（2011-11-16）[2011-11-30].Hadoop， http：//hadoop.apache.org/hdfs/.do cs/current/index html.

[4]LAMMEL R.Data programmability Team.Google’s MapReduce Programming Model-Revisited[R].Redmond， WA， USA：Microsoft Corp.2007.

[5]Owen O’Malley.Programming with Hadoop’s Map/Reduce[R].ApacheCon EU，2008.

[6]DEAN J， GHEMAWATS.MapReduce： simplifieddata processing on large ousters[C].OSDI’04： Sixth Symposium on Operating System Design and Implementation， San Francisco， CA， December， 2004.

[7]WHITE T.Hadoop： The definitive guide[M].O’Reilly，2010.