李 濤 劉 斌

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

?

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

李 濤 劉 斌

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

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

KNN TFIDF 文本分類 Hadoop Spark

0 引 言

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

1 Spark

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

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

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

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

2.1 文本預(yù)處理

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

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

2.2 文本向量化

(1) 經(jī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īng)典的TFIDF加權(quán)算法。

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

(1)

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

(2)

TFIDFwij=TFwij×IDFwij

(3)

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

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

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

(4)

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

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

(5)

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

(6)

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

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

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

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

2.3 文本分類

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

(1) KNN分類算法

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

(7)

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

(8)

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

(9)

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

(10)

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

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

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

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

(3) KNN分類算法結(jié)果評價

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

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

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

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

(11)

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

(12)

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

(13)

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

3 實驗結(jié)果分析和評估

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

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

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

表2 Spark下不同計算節(jié)點的訓(xùn)練和測試時間

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

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

我們在Spark計算模型中統(tǒng)計出每次實驗的結(jié)果，繪制10次交叉實驗所得的分類正確率曲線圖如圖5所示。

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

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

4 結(jié) 語

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

然而，本文的重點不是研究Spark，而是為海量信息以及實時性要求很高的文本分類系統(tǒng)提供一種解決方案。本文中的預(yù)處理、文本向量化以及KNN分類算法在Spark上的實現(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].計算機仿真,2006,23(10):92-94.

[3] 李榮陸,王建會,陳曉云,等.使用最大熵模型進(jìn)行中文文本分類[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].計算機應(yīng)用研究,2008,25(6):1640-1641.

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

[7] 劉文軍,鄭國義,張小瓊.基于粗糙集與統(tǒng)計學(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].計算機工程,2012,38(8):37-40.

[12] 張玉芳,彭時名,呂佳.基于文本分類TFIDF方法的改進(jìn)與應(yīng)用[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].計算機工程與設(shè)計,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