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