摘 要： 隨著Internet等技術(shù)的飛速發(fā)展，信息處理已經(jīng)成為人們獲取有用信息不可或缺的工具,，如何在海量信息中高效地獲得有用信息至關(guān)重要,，因此自動文本分類技術(shù)尤為重要。現(xiàn)有的文本分類算法在時間復(fù)雜性和空間復(fù)雜性上遇到瓶頸,，不能滿足人們的需求,，為此提出了基于Hadoop分布式平臺的TFIDF算法,，給出了算法實現(xiàn)的具體流程，通過MapReduce編程實現(xiàn)了該算法,，并在單機(jī)和集群模式下進(jìn)行了對比實驗,，同時與傳統(tǒng)串行算法進(jìn)行了對比。實驗證明,，使用TFIDF文本分類算法可實現(xiàn)對海量數(shù)據(jù)的高速有效分類,。
關(guān)鍵詞： 文本分類；MapReduce,；并行化,；TFIDF算法
當(dāng)今信息時代，數(shù)據(jù)膨脹的速度已遠(yuǎn)遠(yuǎn)超過人工分析它們的能力,，如何在海量數(shù)據(jù)中快速地獲得所需信息至關(guān)重要,，因此自動文本分類技術(shù)尤為重要。文本分類是指依據(jù)文本內(nèi)容由計算機(jī)根據(jù)某種自動分類算法,，把文本判定為預(yù)先定義好的類別[1],。文本分類是數(shù)據(jù)挖掘的關(guān)鍵技術(shù)，為了提高分類質(zhì)量,，首先要實現(xiàn)算法并行化,。
近幾十年來，一系列統(tǒng)計學(xué)習(xí)文本分類方法被提出[2],，國內(nèi)外對文本分類算法的研究很多,，但大都存在一些局限性，特別是缺乏對海量文本數(shù)據(jù)的挖掘,。云計算的出現(xiàn)為算法并行化帶來了新的契機(jī),，很多科研人員和機(jī)構(gòu)都在投入研究云計算。Hadoop平臺發(fā)布以來,，很多專業(yè)人員致力于利用它對海量數(shù)據(jù)進(jìn)行挖掘，目前已經(jīng)實現(xiàn)了一些基于該平臺的算法,。本文研究TFIDF文本分類算法,，并通過MapReduce編程，在單機(jī)和集群模式下研究TFIDF算法的并行化并進(jìn)行實驗驗證,，并與傳統(tǒng)算法進(jìn)行對比實驗,， 實驗表明，改進(jìn)的算法提高了分類速度,，有效地解決了海量數(shù)據(jù)的分類問題,。
1 TFIDF算法的實現(xiàn)
TFIDF是一種用于資訊檢索與資訊探勘的常用加權(quán)技術(shù)。在某一個特定的文檔中,，詞頻(TF)指某一具體給定的詞語在這個文檔中出現(xiàn)的次數(shù),。對于在某一特定文檔里的詞語ti,，其詞頻可以表示為：
TFIDF算法是有監(jiān)督的文本分類算法，它的訓(xùn)練集是已標(biāo)記的文檔,，并且隨著訓(xùn)練集規(guī)模的增大,，分類效率、精度均顯著提高[6],。
2 MapReduce編程模型
分布式文件系統(tǒng)（HDFS）和MapReduce編程模型是Hadoop的主要組成部分,。Hadoop是一個能夠?qū)Υ髷?shù)據(jù)進(jìn)行分布式處理的框架，能夠把應(yīng)用程序分割成許多小的工作單元,，并且把這些單元放到任何集群節(jié)點上執(zhí)行[7],。MapReduce模型的計算流程如圖1所示。
分布式文件系統(tǒng)主要負(fù)責(zé)各節(jié)點上的數(shù)據(jù)的存儲,，并實現(xiàn)高吞吐的數(shù)據(jù)讀寫,。MapReduce計算模型的核心部分是Map和Reduce兩個函數(shù)[8]。Map的輸入是in_key和in_value,，指明了Map需要處理的原始數(shù)據(jù),。Map的輸出結(jié)果是一組<key，value>對,。系統(tǒng)對Map操作的結(jié)果進(jìn)行歸類處理,。Reduce的輸入是(key，[value1… value m]),。Reduce的工作是將相同key的value值進(jìn)行歸并處理最終形成(key,，final_value)的結(jié)果，所有的Reduce結(jié)果并在一起就是最終結(jié)果,。其中HDFS和MapReduce的關(guān)系如圖2所示,。
3 MapReduce編程模型下的TFIDF算法
3.1 TFIDF算法流程
Hadoop分布式計算的核心思想就是任務(wù)的分割及并行運行。從TFIDF 的計算公式可看出,， 它非常適合分布式計算求解,。詞頻（TF）只與它所在文檔的單詞總數(shù)及它在此文檔出現(xiàn)的次數(shù)有關(guān)。因此,可以通過數(shù)據(jù)分割,， 并行統(tǒng)計出文檔中的詞頻TF,加快計算速度,。得到單詞詞頻TF 后,單詞權(quán)重TFIDF 的計算取決于包含此單詞的文檔個數(shù)。因此,只要能確定包含此單詞的文檔個數(shù),，即能以并行計算的方式實現(xiàn)TFIDF的求解,。MapReduce下計算TFIDF 的整個處理流程如圖3所示。主要包括統(tǒng)計每份文檔中單詞的出現(xiàn)次數(shù),、統(tǒng)計TF及計算單詞的TFIDF值三個步驟,。
Hadoop對數(shù)據(jù)進(jìn)行的是分塊處理，并且默認(rèn)數(shù)據(jù)塊大小為64 MB,，所以當(dāng)存在很多小數(shù)據(jù)文件時,，反而降低了運行速度,，因此對小數(shù)據(jù)集Hadoop的優(yōu)越性體現(xiàn)得并不明顯。但是隨著數(shù)據(jù)集增大,，傳統(tǒng)算法所需要的時間急劇增長,，而應(yīng)用了Hadoop框架的TFIDF算法所需要的時間只是呈線性增加，表現(xiàn)出了一定的算法優(yōu)越性,。
(3)不同節(jié)點數(shù)下的對應(yīng)運行時間
圖5(a)和(b)分別顯示了Sogou文本分類語料庫隨著節(jié)點數(shù)目由1增加到4時的訓(xùn)練時間和測試時間曲線,。
本文通過在Hadoop平臺下的MapReduce編程，對傳統(tǒng)TFIDF算法進(jìn)行了性能優(yōu)化,，并通過3組對比實驗,，驗證了改進(jìn)的TFIDF算法可取得更好的分類結(jié)果，可以很好地實現(xiàn)對海量數(shù)據(jù)的高效挖掘,。
參考文獻(xiàn)
[1] SEBASTIANI F.Text categorization[Z].Encyclopedia of Database Techologies and Applications,，2005：683-687.
[2] Yang Yiming.An evaluation of statistical approaches to text categorizationg[J].Journal of Information Retrieval，1999,，1(1/2)：67-68.
[3] 謝鑫軍,， 何志均.一種單一表單工作流系統(tǒng)的設(shè)計和實現(xiàn)[J].計算機(jī)工程，1988,，24(9)：53-55.
[4] 王宇．基于TFIDF的文本分類算法研究[D]．鄭州：鄭州大學(xué),，2006.
[5] 向小軍，高陽,，商琳,，等．基于Hadoop平臺的海量文本分類的并行化[J]．計算機(jī)科學(xué)，2011,，38(10)：190-194.
[6] 搜狐研發(fā)中心.Sogou文本分類語料庫[OL]．(2008-09)[2012-09-30].http：//www.sogou.com/labs/dl/c.html.
[7] 劉鵬.實戰(zhàn)Hadoop-開啟通向云計算的捷徑[M].北京：電子工業(yè)出版社,，2011.
[8] 李彬．基于Hadoop框架的TF- IDF算法改進(jìn)[J]．微型機(jī)與應(yīng)用，2012,，31(7)：14-16.