《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 嵌入式技術(shù) > 設(shè)計(jì)應(yīng)用 > 基于MapReduce編程模型的TFIDF算法研究
基于MapReduce編程模型的TFIDF算法研究
來源:微型機(jī)與應(yīng)用2013年第4期
趙偉燕1,王靜宇2
(1.內(nèi)蒙古科技大學(xué) 信息工程學(xué)院,內(nèi)蒙古 包頭014010; 2.內(nèi)蒙古科技大學(xué) 信息辦與網(wǎng)絡(luò)中心
摘要: 隨著Internet等技術(shù)的飛速發(fā)展,信息處理已經(jīng)成為人們獲取有用信息不可或缺的工具,如何在海量信息中高效地獲得有用信息至關(guān)重要,因此自動(dòng)文本分類技術(shù)尤為重要。現(xiàn)有的文本分類算法在時(shí)間復(fù)雜性和空間復(fù)雜性上遇到瓶頸,不能滿足人們的需求,為此提出了基于Hadoop分布式平臺的TFIDF算法,給出了算法實(shí)現(xiàn)的具體流程,通過MapReduce編程實(shí)現(xiàn)了該算法,并在單機(jī)和集群模式下進(jìn)行了對比實(shí)驗(yàn),同時(shí)與傳統(tǒng)串行算法進(jìn)行了對比。實(shí)驗(yàn)證明,使用TFIDF文本分類算法可實(shí)現(xiàn)對海量數(shù)據(jù)的高速有效分類。
Abstract:
Key words :

摘  要: 隨著Internet等技術(shù)的飛速發(fā)展,信息處理已經(jīng)成為人們獲取有用信息不可或缺的工具,如何在海量信息中高效地獲得有用信息至關(guān)重要,因此自動(dòng)文本分類技術(shù)尤為重要?,F(xiàn)有的文本分類算法在時(shí)間復(fù)雜性和空間復(fù)雜性上遇到瓶頸,不能滿足人們的需求,為此提出了基于Hadoop分布式平臺的TFIDF算法,給出了算法實(shí)現(xiàn)的具體流程,通過MapReduce編程實(shí)現(xiàn)了該算法,并在單機(jī)和集群模式下進(jìn)行了對比實(shí)驗(yàn),同時(shí)與傳統(tǒng)串行算法進(jìn)行了對比。實(shí)驗(yàn)證明,使用TFIDF文本分類算法可實(shí)現(xiàn)對海量數(shù)據(jù)的高速有效分類。
關(guān)鍵詞: 文本分類;MapReduce;并行化;TFIDF算法

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

此內(nèi)容為AET網(wǎng)站原創(chuàng),未經(jīng)授權(quán)禁止轉(zhuǎn)載。