劉 威，邵劍飛，張磊磊

(昆明理工大學(xué) 信息工程與自動化學(xué)院，云南 昆明 650500)

摘 要：針對傳統(tǒng)的文本分類方法費(fèi)時且占用大量資源、效率低等問題，提出了結(jié)合大數(shù)據(jù)處理平臺Hadoop和中文文本分類，實(shí)現(xiàn)支持向量機(jī)(SVM)算法的并行化的模型。通過試驗(yàn)數(shù)據(jù)分析表明，對比采用傳統(tǒng)的單機(jī)SVM對樣本數(shù)據(jù)進(jìn)行訓(xùn)練這個方式，基于Hadoop平臺而實(shí)現(xiàn)的SVM并行化算法能夠改善在對大量樣本訓(xùn)練時訓(xùn)練時間長的缺陷，并且分類的準(zhǔn)確率也有所提高，尤其是對大量文本進(jìn)行分類時，Hadoop平臺下的并行SVM算法較單機(jī)SVM算法具有更大的優(yōu)勢。

關(guān)鍵詞：文本分類；Hadoop；支持向量機(jī)；并行化

21世紀(jì)是一個高度信息化的時代，信息技術(shù)的飛速發(fā)展讓我們無時無刻不在產(chǎn)生數(shù)據(jù)。我們每天通過手機(jī)APP推送消息，從應(yīng)用商店下載軟件，在電腦上通過網(wǎng)絡(luò)購物，在博客上發(fā)表文章等行為都將產(chǎn)生大量的數(shù)據(jù)[1]。除此之外，一些企業(yè)維護(hù)著成千上萬的用戶數(shù)據(jù)，如中國移動、淘寶商城等。根據(jù)國際上著名的市場調(diào)查機(jī)構(gòu)調(diào)查顯示，全球的數(shù)據(jù)總量每過兩年就會增加一倍，到2012年全世界產(chǎn)生的信息量大約為1.9 ZB，和全球歷史數(shù)據(jù)總量相當(dāng)[2]。

然而，在這些海量的信息中存在各種形式的數(shù)據(jù)，包括文本、圖片和視頻等，其中文本數(shù)據(jù)是產(chǎn)生的最多、最廣的海量信息，因而對文本數(shù)據(jù)的分析是很重要的。文本分類是文本挖掘基本、有效的方法之一。使用單機(jī)進(jìn)行自動文本分類不僅效率低下，而且在數(shù)據(jù)量很大時需要花費(fèi)大量的時間和資源。為了更好地完成在大數(shù)據(jù)下的文本分類，本文提出結(jié)合當(dāng)前比較成熟的大數(shù)據(jù)平臺Hadoop和支持向量機(jī)(Support Vector Machine，SVM)算法，來提高海量信息下文本分類的效率。

1 文本分類概述

文本分類是指對所給出的文本，給出預(yù)定義的一個或多個類別標(biāo)號，對文本進(jìn)行準(zhǔn)確、高效地分類，它是許多數(shù)據(jù)管理任務(wù)的重要組成部分。形象地說，就像我們隨便選出一篇文章去問計(jì)算機(jī)這篇文章寫的是什么內(nèi)容，然后計(jì)算機(jī)根據(jù)一些文本分類算法，通過計(jì)算后將分類結(jié)果輸出[3]。

文本分類也可以表示為一個映射的過程。文本分類的流程如圖1所示。

圖1 文本分類的流程

2 Hadoop與SVM算法的結(jié)合

Hadoop能夠存儲海量數(shù)據(jù)，并且能夠開發(fā)和運(yùn)行分布式數(shù)據(jù)處理程序?qū)崿F(xiàn)云計(jì)算模式，其2個關(guān)鍵技術(shù)為分布式文件系統(tǒng)(HDFS)和分布式計(jì)算框架(MapReduce)。

HDFS是一個用于存儲海量數(shù)據(jù)的分布式文件系統(tǒng)，它是在對谷歌文件系統(tǒng)(GFS)原理的研究基礎(chǔ)上實(shí)現(xiàn)的開源版本，它擁有很強(qiáng)的容錯性能并且能夠以高吞吐率來進(jìn)行數(shù)據(jù)的訪問，能夠?qū)⒈姸嘈阅艿土挠布掀饋碜鳛榇髷?shù)據(jù)的存儲和處理平臺[4-5]。

MapReduce是一種分布式編程模型。MapReduce作業(yè)的處理被抽象為2個函數(shù)：Mapper 和Reducer。在Map階段，原數(shù)據(jù)通過處理后映射為鍵值對，經(jīng)過一定處理后交給Reduce階段處理；Reduce階段會將Map階段產(chǎn)生的中間結(jié)果做合并，經(jīng)過處理整理為鍵值對的形式作為結(jié)果輸出[6]。

通過對文本分類中的各個步驟的分析提出并行化的實(shí)現(xiàn)思想，結(jié)合MapReduce并行計(jì)算框架，將并行分解到Map階段和Reduce階段中，使用Java編程語言實(shí)現(xiàn)了SVM的并行中文文本分類。

2.1 預(yù)處理的MapReduce實(shí)現(xiàn)

在預(yù)處理階段，先將文件上傳到分布式文件系統(tǒng)中。由于Hadoop的設(shè)計(jì)初衷是為用戶提供大數(shù)據(jù)處理和存儲的平臺，大量的小文件存儲會使得管理維護(hù)文件變得困難，而MapReduce任務(wù)每次通常只處理1個數(shù)據(jù)塊的數(shù)據(jù)，大量小文件會產(chǎn)生大量的MapReduce任務(wù)，消耗系統(tǒng)的計(jì)算資源[7]，所以應(yīng)將小文件進(jìn)行合并。本文選取Sequence File，將小文件歸并為大文件，并以鍵值對的形式存儲。預(yù)處理MapReduce作業(yè)流程圖如圖2所示。

圖2 預(yù)處理MapReduce作業(yè)流程圖

2.2 特征選擇

特征選擇階段由一個MapReduce作業(yè)來實(shí)現(xiàn)。在Map階段，將預(yù)處理模塊中經(jīng)過簡單詞頻統(tǒng)計(jì)的輸出作為輸入鍵值對，在Mapper函數(shù)中，計(jì)算統(tǒng)計(jì)各個統(tǒng)計(jì)量，并計(jì)算出每個詞的卡方統(tǒng)計(jì)量；Reduce階段會匯總各特征子集及各特征的卡方統(tǒng)計(jì)量。借助MapReduce中排序的功能對各特征子集按照卡方統(tǒng)計(jì)量降序排序，排序完成后將保留前K個特征作為特征集[8]。Reduce輸出時會設(shè)置一個計(jì)時器，每輸出1個特征，計(jì)數(shù)器就會加1，直到計(jì)數(shù)器的值為K，保留這K個特征作為特征集。特征選擇的MapReduce作業(yè)流程圖如圖3所示。

圖3 特征選擇的MapReduce作業(yè)流程圖

2.3 并行SVM算法的實(shí)現(xiàn)

SVM是一種建立在統(tǒng)計(jì)學(xué)習(xí)基礎(chǔ)之上的機(jī)器學(xué)習(xí)算法[9]，LibSVM(A Library for Support Vector Machines)是對SVM算法的開源實(shí)現(xiàn)，將SVM算法的整個訓(xùn)練過程都封裝起來，調(diào)用時按照格式輸入數(shù)據(jù)就能得出訓(xùn)練的結(jié)果[10]。要在MapReduce框架下實(shí)現(xiàn)并行化SVM就不能直接調(diào)用LibSVM，因?yàn)椴荒苤苯訉⒏鱾€數(shù)據(jù)節(jié)點(diǎn)的SVM訓(xùn)練結(jié)果直接合并。本文對LibSVM的源代碼進(jìn)行改進(jìn)，將SVM訓(xùn)練的過程離散化，實(shí)現(xiàn)MapReduce框架下的并行SVM算法。

在對LibSVM中的SVM實(shí)現(xiàn)進(jìn)行改進(jìn)時，把整改二次規(guī)劃問題分解為很多較小、易處理的問題，每次優(yōu)化只處理2個樣本的優(yōu)化問題，并用解析的方法進(jìn)行處理。改進(jìn)之后，就能夠在Hadoop的各個節(jié)點(diǎn)上分布式的對問題進(jìn)行優(yōu)化，各個節(jié)點(diǎn)上的每一次優(yōu)化并不能保證其結(jié)果就是所優(yōu)化的拉格朗日乘子的最終結(jié)果，但這會使我們向優(yōu)化目標(biāo)邁進(jìn)一步。

SVM算法在訓(xùn)練時要做大量的計(jì)算，會消耗大量的時間和計(jì)算資源，在MapReduce計(jì)算框架下去實(shí)現(xiàn)SVM的并行化能減少訓(xùn)練的時間。改進(jìn)后的SVM算法能夠在Hadoop的各個子節(jié)點(diǎn)對該節(jié)點(diǎn)上的數(shù)據(jù)子集進(jìn)行求解優(yōu)化，然后將各個節(jié)點(diǎn)的優(yōu)化結(jié)果匯總，再對所有進(jìn)行優(yōu)化過的數(shù)據(jù)優(yōu)化并計(jì)算出SVM模型輸出。改進(jìn)后的SVM算法訓(xùn)練的MapReduce作業(yè)流程圖如圖4所示。

圖4 改進(jìn)后的SVM算法訓(xùn)練的MapReduce作業(yè)流程圖

在設(shè)計(jì)MapReduce程序時，可以先將樣本集分配到多個數(shù)據(jù)節(jié)點(diǎn)上，然后每個分樣本集為其分配一個Map任務(wù)，對樣本進(jìn)行訓(xùn)練，根據(jù)SVM訓(xùn)練的要求，在各個節(jié)點(diǎn)上求解樣本子集的最優(yōu)化問題，將非邊界樣本點(diǎn)都過濾，保留邊界樣本，在Map任務(wù)完成后得到各個節(jié)點(diǎn)的支持向量樣本集，在Reduce任務(wù)中將會匯總支持向量樣本集，并對計(jì)算出SVM模型輸出到指定目錄。

3 試驗(yàn)

3.1 試驗(yàn)環(huán)境

本次試驗(yàn)利用5臺計(jì)算機(jī)搭建了1個Master和4個Salve，Master機(jī)器主要承擔(dān)NameNode和JobTracker的角色，負(fù)責(zé)分布式文件系統(tǒng)的管理和任務(wù)的分配與調(diào)度，4個Salve主要承擔(dān)DataNode和TaskTracker的角色，負(fù)責(zé)分布式數(shù)據(jù)的存儲以及任務(wù)的執(zhí)行。節(jié)點(diǎn)之間通過交換機(jī)組成一個小型的局域網(wǎng)，安裝和配置完Hadoop環(huán)境。

3.2 試驗(yàn)數(shù)據(jù)

由文本的分類流程可知，在對未知樣本進(jìn)行文本分類測試時，需要有訓(xùn)練得出的分類器，而分類器是通過收集樣本對支持向量機(jī)進(jìn)行訓(xùn)練得到的。本次試驗(yàn)樣本來自搜狗語料庫中的一部分，該庫包括政治、經(jīng)濟(jì)、軍事、教育、體育、環(huán)境、計(jì)算機(jī)、醫(yī)藥、藝術(shù)和交通等10個類別的文章。

3.3 試驗(yàn)方案

本次試驗(yàn)分為5組，每組試驗(yàn)在樣本數(shù)量相同的情況下分別對單機(jī)SVM和并行SVM進(jìn)行試驗(yàn)，統(tǒng)計(jì)訓(xùn)練時間。訓(xùn)練得到分類器之后，分別對各個分類器進(jìn)行分類測試，測試時使用相同測試樣本進(jìn)行測試，并記錄每組的測試數(shù)據(jù)，計(jì)算測試的準(zhǔn)確率。

3.4 試驗(yàn)步驟

試驗(yàn)平臺的搭建和樣本數(shù)據(jù)準(zhǔn)備好后，就可以按照設(shè)計(jì)進(jìn)行試驗(yàn)了。試驗(yàn)流程圖如圖5所示。

圖5 試驗(yàn)流程圖

將樣本數(shù)據(jù)和測試數(shù)據(jù)上傳到指定的目錄之下，然后從客戶端向Hadoop發(fā)出作業(yè)請求，Hadoop受理作業(yè)請求之后，會到指定目錄下讀取樣本數(shù)據(jù)。在接下來的訓(xùn)練過程中，用戶可查看作業(yè)執(zhí)行的狀態(tài)，訓(xùn)練結(jié)束后分類器會被存儲在指定目錄，客戶端發(fā)起文本分類作業(yè)請求，Hadoop會去讀取測試樣本進(jìn)行分類。分類結(jié)束后，結(jié)果保存到指定目錄，用戶可以從目錄中將結(jié)果取出查看。

3.5 試驗(yàn)結(jié)果與分析

根據(jù)設(shè)計(jì)的試驗(yàn)方案，得到5組試驗(yàn)結(jié)果的統(tǒng)計(jì)數(shù)據(jù)(見表1)。試驗(yàn)數(shù)據(jù)分析如圖6～圖8所示。

表1 5組試驗(yàn)結(jié)果的統(tǒng)計(jì)

參數(shù)試驗(yàn)1試驗(yàn)2試驗(yàn)3試驗(yàn)4試驗(yàn)5訓(xùn)練樣本行數(shù)200500100020003000測試樣本行數(shù)327511734323642單機(jī)訓(xùn)練時間/s1646137293568并行訓(xùn)練時間/s184492163258單機(jī)準(zhǔn)確率/%82 583 385 987 587 6并行準(zhǔn)確率/%85 185 486 888 189 7

圖6 訓(xùn)練耗時對比圖

圖7 分類準(zhǔn)確率對比圖

圖8 訓(xùn)練樣本對準(zhǔn)確率的影響

從圖6～圖8可以得出如下結(jié)論。

1)從訓(xùn)練時間來看，訓(xùn)練時間隨訓(xùn)練樣本數(shù)量的遞增呈增長的趨勢，訓(xùn)練樣本數(shù)量越大耗時越長。

2)在訓(xùn)練樣本比較少時，單機(jī)模式和并行模式耗時差不多，甚至?xí)l(fā)生單機(jī)模式耗時更短的情況。原因是Hadoop平臺并不擅長處理小數(shù)據(jù)，在處理時會增加HDFS的尋址時間。

3)不管是單機(jī)模式還是并行模式，得到的準(zhǔn)確率的數(shù)值變化不大，能夠表現(xiàn)在一個穩(wěn)定的范圍內(nèi)。這說明了SVM是一個比較穩(wěn)定的文本分類算法，且并行模式下得到的準(zhǔn)確率比單機(jī)模式下略高。

4)文本分類的準(zhǔn)確率與訓(xùn)練樣本的數(shù)量成正比，但是當(dāng)追求高準(zhǔn)確率時，同樣會增加訓(xùn)練大量樣本時的訓(xùn)練時間；因此在訓(xùn)練時間與分類準(zhǔn)確率之間的取舍應(yīng)根據(jù)實(shí)際情況考慮各種因素決定。

4 結(jié)語

本文通過文本分類的理論和SVM算法的原理，并結(jié)合目前比較流行的Hadoop平臺，嘗試通過該平臺實(shí)現(xiàn)SVM的并行文本分類。試驗(yàn)結(jié)果表明，采用該方式降低了單機(jī)SVM在做大量文本分類時的訓(xùn)練時間，減少了占用的資源。

參考文獻(xiàn)：

[1] 洪格.云計(jì)算中的“大數(shù)據(jù)”,帶來新的市場機(jī)遇[J]. 信息與電腦，2013(3)：55-57.

[2] 黃荷.大數(shù)據(jù)時代降臨[J]．黨政論壇：干部文摘，2012(11)：52-53．

[3] 何鐘莉.中文文本分類關(guān)鍵技術(shù)研究與實(shí)現(xiàn)[D]. 西安：西安電子科技大學(xué),2009.

[4] 陸嘉恒.Hadoop實(shí)戰(zhàn)[M].北京：機(jī)械工業(yè)出版社,2012.

[5] 任修仕,邵劍飛.一種基于Hadoop的數(shù)據(jù)展示研究[J]. 新技術(shù)新工藝, 2016(1):83-85.

[6] 劉智慧，張泉靈.大數(shù)據(jù)技術(shù)研究綜述[J].浙江大學(xué)學(xué)報(bào)，2014(6):957-972.

[7] Kruijf M D, Sankaralingam K. MapReduce for the cell B.E. architecture[J]. Ibm Journal of Research & Development, 2007, 53(4):328-330.

[8] 陸江,李云.基于MapReduce的特征選擇并行化研究[J].計(jì)算機(jī)與科學(xué)，2015(8):44-47.

[9] 鄧乃楊,田英杰.支持向量機(jī):理論、算法與拓展[M].北京:科學(xué)出版社,2009.

[10] 周惠勇.基于小波分析的心電信號分類研究[D]. 長沙：中南大學(xué)，2014.

責(zé)任編輯 鄭練

Research and Optimization of Text Categorization under the Mass of Information

LIU Wei, SHAO Jianfei, ZHANG Leilei

(College of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, China)

Abstract：As the traditional text categorization methods not only being time-consuming, but also take up a lot of resources, and in the low efficiency, propose the combining large data processing platform Hadoop and Chinese text classification to achieve the parallelism model of SVM algorithm. By analyzing the experimental data, compared to the traditional single SVM for sample data for training is in this way, Hadoop platform achieving SVM parallel algorithm can get a large number of training samples in long training time defects, and the text categorization accuracy rate is also increased. The parallel SVM algorithm on Hadoop platform has more advantage than the single SVM algorithm, especially with a large number of text classifications.

Key words：text categorization, Hadoop, SVM, parallelization

中圖分類號：TP 391.1

文獻(xiàn)標(biāo)志碼：A

作者簡介：劉威(1988-)，男，碩士研究生，主要從事信號與信息處理、數(shù)據(jù)挖掘等方面的研究。

收稿日期：2016-09-28