李 濤 劉 斌

(南京工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 江蘇 南京 210009)

?

Spark平臺(tái)下的高效Web文本分類系統(tǒng)的研究

李 濤 劉 斌

(南京工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 江蘇 南京 210009)

針對(duì)KNN分類算法在面對(duì)海量Web文本處理情況時(shí)在單機(jī)上訓(xùn)練和測(cè)試效率低下的問題，提出基于Hadoop分布式平臺(tái)以及Spark并行計(jì)算模型的無中間結(jié)果輸出的改進(jìn)型Web文本分類系統(tǒng)。同時(shí)為了充分利用Spark的迭代計(jì)算能力，在文本向量化階段，在傳統(tǒng)TFIDF文本特征加權(quán)算法的基礎(chǔ)上充分考慮特征項(xiàng)在類內(nèi)和類間的信息分布，提出一種改進(jìn)的特征加權(quán)算法。實(shí)驗(yàn)結(jié)果表明，該文本分類系統(tǒng)結(jié)合Spark計(jì)算模型在提高文本預(yù)處理、文本向量化以及KNN文本分類算法的性能上有著優(yōu)異的表現(xiàn)。

KNN TFIDF 文本分類 Hadoop Spark

0 引 言

隨著大數(shù)據(jù)浪潮的到來，對(duì)海量信息的處理能力已經(jīng)成為一個(gè)相當(dāng)重要的課題。成熟的文本分類系統(tǒng)通常具有很高準(zhǔn)確率，但Web文本信息的實(shí)時(shí)性特點(diǎn)同時(shí)也要求分類系統(tǒng)具有很高的分類效率。目前使用比較廣泛的文本分類算法包括K臨近算法[1]、樸素貝葉斯[2]、最大熵[3]、支持向量機(jī)(SVM)[4]、人工神經(jīng)網(wǎng)絡(luò)[5]、決策樹[6]、粗糙集[7]等等。對(duì)上述文本分類方法的研究都集在中小規(guī)模的數(shù)據(jù)模型上，當(dāng)面對(duì)大規(guī)模數(shù)據(jù)且對(duì)實(shí)時(shí)性要求較高的場景，傳統(tǒng)分類系統(tǒng)顯得無能為力。本文在Spark平臺(tái)下實(shí)現(xiàn)了一種Web文本分類系統(tǒng), 該系統(tǒng)對(duì)解決大規(guī)模、實(shí)時(shí)條件下的文本分類具有重要的現(xiàn)實(shí)意義。

1 Spark

與MapReduce不同的是，Spark的并行計(jì)算框架是基于內(nèi)存的。Spark其實(shí)就是MapReduce的替代方案，它可以兼容HDFS和Hive等分布式存儲(chǔ)層，可以融入Hadoop生態(tài)系統(tǒng)。Spark相比于MapReduce的優(yōu)勢(shì)有諸多的優(yōu)勢(shì)[8]，特別適用于流式計(jì)算和機(jī)器學(xué)習(xí)，可以在一個(gè)工作流中無縫搭配這些計(jì)算范式，所以本文采用Hadoop和Spark作為海量Web文本分類的實(shí)現(xiàn)平臺(tái)。

2 Web文本分類系統(tǒng)

文本分類系統(tǒng)的工作流程是：首先對(duì)收集到的文本進(jìn)行預(yù)處理，如圖1所示。然后利用VSM模型[9]將文本使用向量來表示。然后可以利用成熟的分類算法進(jìn)行分類，如KNN分類算法。最后一步是結(jié)果評(píng)價(jià)。圖1給出系統(tǒng)整體結(jié)構(gòu)圖。

圖1 Web文本分類系統(tǒng)結(jié)構(gòu)圖

2.1 文本預(yù)處理

要提高文本分類的效果，首先必須對(duì)文本進(jìn)行預(yù)處理, 其中的主要步驟包括: 分詞、去停用詞和低頻詞等。在Spark集群上實(shí)現(xiàn)文本預(yù)處理，RDD中的數(shù)據(jù)項(xiàng)就是Web文本中的每行內(nèi)容。將文本內(nèi)容進(jìn)行分割去、除停用詞，計(jì)算詞頻形成屬性詞典，這些分布式操作都是在Worker節(jié)點(diǎn)上完成的。預(yù)處理在Spark下的執(zhí)行流程如圖2所示。

圖2 Spark文本分類預(yù)處理結(jié)構(gòu)圖

2.2 文本向量化

(1) 經(jīng)典的特征項(xiàng)加權(quán)算法TFIDF

目前，在文本分類研究領(lǐng)域中，向量空間模型(VSM)是常用的形式。在該模型中，每篇文檔被表示為一組特征向量，dj={(w1, f1), (w2,f2),…,(wn, fn)},其中wi表示在文檔dj中出現(xiàn)的特征詞, fi是 wi的權(quán)值, 其中i的取值為1,2,…,n。其中特征詞可在文本預(yù)處理階段得到,特征詞權(quán)重的計(jì)算利用經(jīng)典的TFIDF加權(quán)算法。

TFIDF算法由Salton提出[10]，其中的TF (Term Frequency) 表示某個(gè)特征項(xiàng)在某篇文檔中出現(xiàn)的頻率，計(jì)算方式如下：

(1)

逆向文檔頻率 IDF (Inverse document frequency)實(shí)現(xiàn)對(duì)詞語重要性的度量, 其定義如下：

(2)

TFIDFwij=TFwij×IDFwij

(3)

從TFIDF的經(jīng)典公式中，我們可以發(fā)現(xiàn)，TF值越大，即特征詞在特征文本中出現(xiàn)的次數(shù)越多，權(quán)重越大，區(qū)分該文本的能力越強(qiáng)。特征項(xiàng)出現(xiàn)在特征文本中的越多，即IDF的值越小，表明該特征項(xiàng)區(qū)分文本的的能力越弱。IDF權(quán)值部分沒有考慮類內(nèi)特征項(xiàng)的分布規(guī)律，這就可能導(dǎo)致在類內(nèi)分布不均勻的特征項(xiàng)被賦予較高權(quán)重。

(2) 考慮類內(nèi)和類間信息來改進(jìn)TFIDF算法

傳統(tǒng)的TFIDF特征加權(quán)算法單純地把整個(gè)文本集作為一個(gè)整體來考慮，其IDF部分并不能完全體現(xiàn)特征項(xiàng)的類間分布信息。而往往類間的信息又十分重要，因?yàn)轭愰g信息更能代表這個(gè)類的特征，更具有代表性。如果使用類間頻率CIF(Classes Internal Frequency)來描述包含特征項(xiàng)的類別的數(shù)目，那么在大多數(shù)類中出現(xiàn)的特征項(xiàng)對(duì)于類別之間的區(qū)分能力比較弱，其區(qū)分度不大，應(yīng)該給于其較小的權(quán)重。而只在少數(shù)類中出現(xiàn)的特征項(xiàng)對(duì)于類別之間的區(qū)分能力較強(qiáng)，應(yīng)該賦予較高的權(quán)重。為此我們引入逆類間頻率ICIF(Inverse Classes Internal Frequence)來表征特征項(xiàng)對(duì)于類別之前的區(qū)分能力。它的表達(dá)式如下所示：

(4)

其中，Cm所有文本的類別總數(shù)，Cmi表示包含第i個(gè)特征項(xiàng)的類別數(shù)目。當(dāng)特征項(xiàng)只出現(xiàn)在一個(gè)類別中的時(shí)候，即Cmi=1，它的ICIF值達(dá)到最大的lg(Cm+1)。根據(jù)這個(gè)公式的特點(diǎn)，特征項(xiàng)出現(xiàn)的類別數(shù)越多，ICIF的值越小，即該特征項(xiàng)不具有較大的區(qū)分能力。這里需要注意的是，ICIF和IDF并不沖突，因?yàn)镮CIF體現(xiàn)的是特征詞對(duì)類別區(qū)分的貢獻(xiàn)程度，而IDF體現(xiàn)的則是特征項(xiàng)的文本表現(xiàn)能力的熵值這一信息。

但是，此時(shí)對(duì)于該特征詞在類內(nèi)的分布信息仍然是模糊的，雖然某個(gè)特征項(xiàng)的ICIF值較大，但是可能該特征項(xiàng)只集中于類內(nèi)的某篇或者某幾篇文檔中，并不能代表整個(gè)類的特征。TF-IDF將文檔頻率TF作為個(gè)體來考慮, 而單個(gè)文本中的特征項(xiàng)信息并不能完整體現(xiàn)該類別的全部信息。特征項(xiàng)在某類的內(nèi)部是否呈高值分布、分布是否均勻都關(guān)系到該特征項(xiàng)的權(quán)重計(jì)算是否合理。為此我們引入類內(nèi)頻率ICF(Inside Class Frequence)，同時(shí)為了考慮特征項(xiàng)在整個(gè)類內(nèi)的出現(xiàn)頻率，我們也為特征項(xiàng)引入平均類內(nèi)文檔頻率ADFIC(Average Document Frequency Inside Class)的概念，這樣即考慮到了特征項(xiàng)在類內(nèi)部的出現(xiàn)頻率，也考慮了特征項(xiàng)在類內(nèi)的分布特征，公式如下：

(5)

使用IDF作為平衡因子可以保證分布在較多文本中的特征項(xiàng)的權(quán)重較低，即文本表現(xiàn)能力較強(qiáng)，使用ICIF可以確保出現(xiàn)在少數(shù)類中的特征項(xiàng)獲得高權(quán)重，而ADFIC-ICF能較好地反應(yīng)特征項(xiàng)在類別內(nèi)部的分布規(guī)律。下面給出修改后的權(quán)重計(jì)算公式：

(6)

式(6)中的∑dj和式(2)中的M是一個(gè)含義，都代表整個(gè)文檔集。雖然式(6)較傳統(tǒng)的權(quán)重計(jì)算公式復(fù)雜，但得益于Hadoop和Spark下的高效并發(fā)處理模型，式(6)可以得到較高的分類效率和分類準(zhǔn)確率。

(3) 改進(jìn)的特征加權(quán)算法在Spark中的計(jì)算流程

經(jīng)典的TFIDF權(quán)值計(jì)算在海量文本分類的計(jì)算上顯得捉襟見肘，往往需要耗費(fèi)幾十個(gè)小時(shí)，甚至數(shù)天時(shí)間。這對(duì)于實(shí)時(shí)性較高的場合，顯然是無法想象的災(zāi)難。為此引入基于內(nèi)存的分布式計(jì)算模型Spark。式(6)有一個(gè)非常顯著的特點(diǎn)，三部分權(quán)重分值的計(jì)算都是獨(dú)立的，在Spark中可以分為三個(gè)Stage，如圖3所示。

圖3 加權(quán)算法在Spark中的計(jì)算結(jié)構(gòu)圖

2.3 文本分類

文本的向量空間模型建立好之后，就需要使用文本分類算法進(jìn)行分類操作。如前所述，分類算法有很多，K鄰近算法和支持向量機(jī)(SVM)等分類算法被認(rèn)為是分類效果比較好的分類算法[13]。我們這里使用實(shí)現(xiàn)比較簡單的KNN分類算法，在該算法的基礎(chǔ)之上設(shè)計(jì)出基于Spark的KNN并行化算法。

(1) KNN分類算法

KNN算法[14]是一種比較成熟的分類算法，它通過比較測(cè)試文檔與訓(xùn)練樣本集的相似度，找到距離測(cè)試文檔最近的K個(gè)文本。當(dāng)我們計(jì)算出每個(gè)特征詞的權(quán)重之后，如果我們把每個(gè)文檔看成一個(gè)多維向量空間，那么該向量由包含所有特征詞的權(quán)重值組成，該向量的每一維對(duì)應(yīng)一個(gè)特征詞。文檔之間的相似度采用余弦相似度[15]來計(jì)算，其計(jì)算公式如下所示：

(7)

其中，simij表示待測(cè)樣本i和訓(xùn)練樣本j之間的相似度或者說距離。wik表示待測(cè)文檔di中的第k個(gè)特征項(xiàng)wk的權(quán)重。而wjk表示測(cè)試文檔di中的第k個(gè)特征項(xiàng)在訓(xùn)練文檔dj中的權(quán)重值。通過循環(huán)迭代，計(jì)算出待測(cè)文檔di和所有訓(xùn)練集中的文檔的余弦相似度，并找到與待測(cè)文檔相似度最高的K個(gè)訓(xùn)練文檔，并計(jì)算每個(gè)類的權(quán)重。測(cè)試文檔的類別屬于分?jǐn)?shù)最高的哪個(gè)類別。計(jì)算過程如下式所示：

(8)

其中bm表示閾值，只考慮分值超過閾值的類別。加入條件K，使用更通俗的公式來表示：

(9)

其中，sim(ai，dx)表示待測(cè)文本dx的K個(gè)最鄰近樣本ai和dx之間的相似度，pa,c(ai,cj)表示樣本ai和類別cj之間的隸屬關(guān)系，其定義如下所示：

(10)

計(jì)算出每個(gè)類相對(duì)于待測(cè)文本的權(quán)重之后，將待測(cè)文本歸于權(quán)重最大的類中，分類也就完成。

(2) KNN分類算法在Spark下的實(shí)現(xiàn)

從式(7)可以看出，要得到訓(xùn)練文檔di和測(cè)試文檔K個(gè)相似度最高的值，需要使用待測(cè)文本dx和整個(gè)訓(xùn)練文檔集進(jìn)行相似度的迭代計(jì)算。由于整個(gè)計(jì)算過程是獨(dú)立的，所以完全可以使用分布式計(jì)算模型Spark來實(shí)現(xiàn)整個(gè)計(jì)算過程的并行化，如圖4所示。

圖4 KNN分類算法在Spark中的計(jì)算結(jié)構(gòu)圖

(3) KNN分類算法結(jié)果評(píng)價(jià)

本文采用十折交叉驗(yàn)證來劃分訓(xùn)練集與測(cè)試集。對(duì)于每種加權(quán)算法，根據(jù)評(píng)價(jià)指標(biāo)分別進(jìn)行10次十折交叉驗(yàn)證，并取均值。對(duì)于二元分類通常采用的性能評(píng)估指標(biāo)有召回率(Recall，簡計(jì)為R)、正確率(Precision，簡記為P)、F1值以及精確度(Accuracy，簡稱A)。一般使用列聯(lián)表來描述二元分類問題，如表1所示。

表1 二元分類列聯(lián)表

此時(shí)，查全率(R)和查準(zhǔn)率(P)分類定義為：

結(jié)合召回率和準(zhǔn)確率得到F1值：

(11)

由于正確率、召回率和F1值都是針對(duì)某一類別進(jìn)行評(píng)價(jià)，因此，為了評(píng)價(jià)分類算法在整個(gè)文本集上的性能，通常對(duì)單個(gè)分類方法的分類指標(biāo)進(jìn)行宏平均。計(jì)算方法如下所示：

(12)

其中的MacroR表示宏平均召回率 ，MacroP表示宏平均準(zhǔn)確率。宏平均是每一個(gè)類的性能指標(biāo)的算術(shù)平均值，但是容易受到小類的影響。由于本文研究的是海量Web文本的分類，可能每個(gè)類別中的文檔數(shù)目有差別，所以采用精確度作為評(píng)估指標(biāo)，如式(13)所示：

(13)

其中左側(cè)的A表示精確度，等式的分母其實(shí)就是測(cè)試文檔的總和。

3 實(shí)驗(yàn)結(jié)果分析和評(píng)估

本文使用搜狗實(shí)驗(yàn)室提供的新聞?wù)Z料集作為中文語料實(shí)驗(yàn)數(shù)據(jù)集, 其中包含財(cái)經(jīng)、互聯(lián)網(wǎng)、健康、軍事、教育、旅游、體育、文化、環(huán)境等10大類共80 000多篇新聞文本,共計(jì)約108 MB。本文采用的硬件環(huán)境是: 4臺(tái)安裝有Linux系統(tǒng)的PC機(jī)，內(nèi)存大小是2 GB，四臺(tái)主機(jī)通過路由器相連。本文使用的Hadoop版本是2.6.0，使用的spark版本是1.4.0。4臺(tái)主機(jī)，其中一臺(tái)作為Master節(jié)點(diǎn)，另外四臺(tái)作為Slave節(jié)點(diǎn)。Master 運(yùn)行 NameNode節(jié)點(diǎn)和Master進(jìn)程, Slave 運(yùn)行 DataNode和Worker進(jìn)程。對(duì)于Spark計(jì)算模型來說Master作為整個(gè)集群中的控制器，負(fù)責(zé)整個(gè)集群的正常運(yùn)行。Worker相當(dāng)于計(jì)算節(jié)點(diǎn)，接收主節(jié)點(diǎn)的命令與進(jìn)行狀態(tài)匯報(bào)。

3.1 分布式節(jié)點(diǎn)數(shù)和分類時(shí)間的關(guān)系

本文為了體現(xiàn)計(jì)算節(jié)點(diǎn)數(shù)對(duì)分類過程的影響，實(shí)驗(yàn)將計(jì)算節(jié)點(diǎn)數(shù)從1個(gè)逐步增加到4個(gè)節(jié)點(diǎn)，實(shí)驗(yàn)結(jié)果如表2所示。

表2 Spark下不同計(jì)算節(jié)點(diǎn)的訓(xùn)練和測(cè)試時(shí)間

由表2可見:當(dāng)計(jì)算節(jié)點(diǎn)只有一個(gè)的時(shí)候，由于資源(如CPU、內(nèi)存)等限制，Spark的效率還不及本地模式下的計(jì)算效率，那是由于Spark本身的資源調(diào)度需要占用一部分資源和時(shí)間，但是隨著節(jié)點(diǎn)數(shù)的增加, 實(shí)驗(yàn)所需要的訓(xùn)練時(shí)間和測(cè)試時(shí)間均呈明顯下降趨勢(shì)。Web 文本分類系統(tǒng)能快速地完成分類任務(wù)。由于實(shí)驗(yàn)資源實(shí)在有限，計(jì)算節(jié)點(diǎn)Worker的內(nèi)存只有2 GB大小，可以預(yù)見的是，當(dāng)集群的內(nèi)存總量提升時(shí)，該文本分類系統(tǒng)的性能還將進(jìn)一步提升。

3.2 經(jīng)典TFIDF加權(quán)算法與改進(jìn)的加權(quán)算法在Spark平臺(tái)下的分類結(jié)果

我們?cè)赟park計(jì)算模型中統(tǒng)計(jì)出每次實(shí)驗(yàn)的結(jié)果，繪制10次交叉實(shí)驗(yàn)所得的分類正確率曲線圖如圖5所示。

圖5 Spark平臺(tái)下KNN分類算法的結(jié)果

實(shí)驗(yàn)證明，通過改進(jìn)IDF算法，充分考慮特征項(xiàng)在類內(nèi)和類間的的分布規(guī)律后，有效地改善了KNN分類算法的分類效果。

4 結(jié) 語

針對(duì)傳統(tǒng)的分類方法無法解決大規(guī)模分類和實(shí)時(shí)性分類的不足之處，提出基于Hadoop和Spark的高效Web文本分類系統(tǒng)。該系統(tǒng)充分利用Spark計(jì)算模型在迭代計(jì)算上的優(yōu)勢(shì)，對(duì)經(jīng)典的TFIDF加權(quán)算法進(jìn)行了優(yōu)化，充分考慮特征項(xiàng)在整個(gè)文本集、語料類的內(nèi)部以及語料的類別之間的信息，使得整個(gè)分類過程高效且無中間結(jié)果輸出，大大提高了分類的效率。

然而，本文的重點(diǎn)不是研究Spark，而是為海量信息以及實(shí)時(shí)性要求很高的文本分類系統(tǒng)提供一種解決方案。本文中的預(yù)處理、文本向量化以及KNN分類算法在Spark上的實(shí)現(xiàn)流程還有不完美之處，還有很多值得優(yōu)化的地方。

[1] Rong Lu L I,Yun Fa H U.A Density-Based Method for Reducing the Amount of Training Data in kNN Text Classification[J].Journal of Computer Research & Development,2004,41(4):539-545.

[2] 程克非,張聰.基于特征加權(quán)的樸素貝葉斯分類器[J].計(jì)算機(jī)仿真,2006,23(10):92-94.

[3] 李榮陸,王建會(huì),陳曉云,等.使用最大熵模型進(jìn)行中文文本分類[J].計(jì)算機(jī)研究與發(fā)展,2005,42(1):94-101.

[4] Yuan R,Li Z,Guan X,et al.An SVM-based machine learning method for accurate internet traffic classification[J].Information Systems Frontiers,2010,12(2):149-156.

[5] 丁振國,黎靖,張卓.一種改進(jìn)的基于神經(jīng)網(wǎng)絡(luò)的文本分類算法[J].計(jì)算機(jī)應(yīng)用研究,2008,25(6):1640-1641.

[6] 王熤,王正歐.基于模糊決策樹的文本分類規(guī)則抽取[J].計(jì)算機(jī)應(yīng)用,2005,25(7):1634-1637.

[7] 劉文軍,鄭國義,張小瓊.基于粗糙集與統(tǒng)計(jì)學(xué)習(xí)理論的樣本分類算法[J].模糊系統(tǒng)與數(shù)學(xué),2015,29(1):184-189.

[8] Gao Yanjie.Data Processing with Spark[M].Beijing:China Machine Press,2015.

[9] Salton G,Wong A,Yang C S.A vector space model for automatic indexing[J].Communications of the ACM,1975,18(11):613-620.

[10] Salton G,Buckley C.Term-Weighting Approaches in Automatic Text Retrieval[J].Information Processing & Management,1988,24(88):513-523.

[11] 李學(xué)明,李海瑞,薛亮,等.基于信息增益與信息熵的TFIDF算法[J].計(jì)算機(jī)工程,2012,38(8):37-40.

[12] 張玉芳,彭時(shí)名,呂佳.基于文本分類TFIDF方法的改進(jìn)與應(yīng)用[J].計(jì)算機(jī)工程,2006,32(19):76-78.

[13] Li Rong,Ye Shiwei,Shi Zhongzhi.SVM-KNN Classifier—A New Method of Improving the Accuracy of SVM Classifier[J].Acta Electronica sinica,2002,30(5):745-748.

[14] Lihua Sun,Jidong Zhang,Jingmei Li.An improved KNN method and its application to Text classification[J].Applied Science and Technology,2003,29(2):25-27.

[15] 彭鎧,汪偉,楊熤普.基于余弦距離度量學(xué)習(xí)的偽鄰近文本分類算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2013,34(6):2201-2203.

RESEARCH ON EFFICIENT WEB TEXT CLASSIFICATION SYSTEM BASED ON SPARK

Li Tao Liu Bin

(CollegeofComputerScienceandTechnology,NanjingTechnologyUniversity,Nanjing210009,Jiangsu,China)

In order to solve the problem of low efficiency of KNN classification algorithm in training and test on a single computer when facing the situation of processing massive Web texts, we proposed an improved Web text classification system without intermediate result output, which is based on Hadoop distributed platform and Spark parallel computing model. Meanwhile, in order to take full advantage of the computing power of Spark in iterative computation, at the stage of text vectorisation and on the basis of the traditional text feature weighting algorithm of TFIDF, we made the full consideration on the information distribution of the feature items within class and between class and proposed an improved feature weighting algorithm. Experimental results showed that this Web text classification system, in combination with Spark computing model, has excellent performance in improving text preprocessing, text vectorisation and the performance of KNN text classification algorithm.

KNN TFIDF Text classification Hadoop Spark

2015-09-13。李濤，碩士生，主研領(lǐng)域：數(shù)據(jù)挖掘，文本分類。劉斌，博士。

TP391.1

A

10.3969/j.issn.1000-386x.2016.11.008