基于Spark與詞語相關度的KNN文本分類算法

于蘋蘋，倪建成，韋錦濤，曹 博，姚彬修

(1.曲阜師范大學 信息科學與工程學院，山東 日照 276826；2.曲阜師范大學 軟件學院，山東 曲阜 273100)

0 引 言

隨著Internet技術以及社交媒體的發展，文本信息規模越來越大，如何高效地在海量文本信息中挖掘出有價值的信息成為當前的研究熱點[1]。文本分類技術作為文本處理的關鍵技術，在提高信息檢索、利用等方面應用廣泛。當前，使用較多的分類算法有樸素貝葉斯、支持向量機(support vector machine，SVM)、K-最近鄰(K-nearest neighbor，KNN)等[2]。由于KNN分類算法具有穩定性強、準確率高等優點，在數據挖掘領域得到了廣泛應用[3]。

近年來，國內外學者對KNN分類算法的準確率和分類效率進行了深入研究。在準確率上，文獻[4]在傳統KNN文本分類算法的基礎上提出了一種基于關聯分析的KNN改進算法，能夠較好地確定K值，降低時間復雜度。文獻[5]提出了一種基于KNN文本分類的偽裝入侵檢測方法，使得有區分性的命令權重增大，有利于更準確地表示用戶的行為特征。在時間效率方面，Deng等[6]使用K-means方法對大規模訓練集進行聚類裁剪，從而減少相似度的計算，提高分類效率。同時，有研究者將KNN算法應用于分布式平臺，進一步提高分類效率。如文獻[7]將SVM分類算法與KNN分類算法相結合，利用Hadoop云計算平臺實現算法并行化。Anchalia等[8-9]依托MapReduce框架實現了KNN分類算法的并行化，縮短了分類時間。MapReduce框架[9]利用并行分布式計算模型對數據進行處理，是有效處理大數據集的關鍵所在。但研究人員在實驗中發現MapReduce在Hadoop[10]中具有限制性[11]：MapReduce在執行過程中，每輪作業都需要重新啟動，開銷過大；同時，通過磁盤對數據進行I/O操作，執行效率較低。而Spark框架[12]改善了以上問題，它通過建立彈性分布式數據集，在內存中對數據進行存取操作，加快了數據處理速度。

分類算法中的距離機制直接影響分類效果。傳統KNN的距離機制僅通過詞頻計算兩樣本間的相似度，而在實際分類過程中，文本詞語間具有一定相關性。同時，在大數據環境中，數據集不斷增大，KNN分類算法的計算復雜度不斷增加，導致運行時間增多。

因此，文中在KNN相似度計算過程中引入詞語相關度進行特征項加權，同時在Spark框架下實現KNN文本分類算法的并行化，以提高分類的準確度。

1 相關技術

1.1 KNN文本分類算法

KNN分類算法的核心原理為：通過相應距離機制計算待測樣本與已知樣本的相似度，找出與待測樣本相似度最大的K個最近鄰樣本，利用決策函數判斷K個樣本中大多數屬于哪個類別，則待分類樣本也屬于這個類別，并具有這個類別上樣本的特性。

余弦相似度計算公式如下：

(1)

其中，wik表示Di文本中第k個特征的權重。

通過相似度計算得到K個相似度最大的樣本即K個最近鄰，并利用式(2)計算權重判斷最終歸類。

(2)

1.2 詞語間相關度

一個詞條對于文檔的主題是否具有代表性與該詞條所在一定范圍內其他詞語在文檔中的出現頻率(同現頻率)是相關的[13]，詞語間相關度指兩個詞語同時出現在一定語言范圍內的概率大小。

計算方法如下：

(1)依據文本預處理后特征空間基向量所包含的詞條個數定義一個N×N維的詞語相關度矩陣，其中N為特征空間中的基向量數目，基向量的一個詞條對應矩陣中的一維數據，矩陣內各對應值初始為0。

(2)計算全部段落范圍內同時出現的詞條對得到段落同現頻率。在同一段落中，如果詞條Ti和詞條Tj同時出現，則詞語相關度矩陣中的對應值加一。

(3)直到所有文檔的所有段落都學習后停止。

在得到對應的同現頻率后，即可計算相應的詞語相關度，詞條Ti和詞條Tj基于段落同時出現頻率的相關度RPij計算為：

(3)

其中，PFi和PFj表示詞條Ti和Tj在文檔dj中所有段落范圍內的出現頻率。

1.3 Spark框架

Spark是由UCBerkeley開發的一種基于內存的計算框架。Spark框架由兩個主要部分組成：彈性分布式數據集和并行運算。RDD是Spark框架計算中重要的概念，是Spark框架的核心和基礎。

RDD是Spark框架的核心，是各個集群節點中數據共享的一種有效抽象。Spark所執行的數據處理是基于RDD進行的。RDD是可并行的數據結構，同時允許用戶將數據存儲在內存中，方便用戶對數據的重復調用，減少了磁盤I/O的負載。RDD是不可變的集合，不能在原有RDD上實現內容的修改，只能創建一個新的RDD：

(1)通過對文件共享系統(HBase、HDFS、Hive)的讀取得到RDD；

(2)通過驅動程序中用作并行計算的Scala集合創建；

(3)通過對已存在的RDD執行轉換操作新建一個RDD；

(4)通過持久化操作進而轉變現有的RDD。

并行運算包括轉換(transform)和動作(action)。轉換操作只依據原有的RDD定義一個新的RDD，而不對它進行直接計算；動作是對某個值立即進行計算，并返回結果給驅動程序[14]。

對RDD的控制還可利用緩存和分區操作。將RDD緩存在內存中，便于下次計算時的重復利用，減少了磁盤開銷。RDD可根據key來指定分區順序，將數據劃分到不同分區中。

2 Spark框架下基于詞語相關度的KNN算法

為了提高文本分類效率，分類算法的并行化處理是當前的一大趨勢，但通過研究發現，在KNN文本分類的一般并行化過程中會降低分類準確率。因此文中在訓練樣本與待測樣本的相似度計算過程中引入詞語相關度，提高分類準確度并在Spark計算框架下實現并行化，降低運算時間。

2.1 基于詞語相關度的相似度計算

通常情況下，傳統KNN相似度計算方法單純使用TF-IDF[15]計算相關度，忽略了文本數據本身詞語間的關系，易導致文本內容表達的不完整，影響文本分類的準確率[16]。因此，定義合適的距離機制是分類準確的前提。文中在KNN分類算法相似度距離計算中引入詞語相關度概念。

基于詞語相關度的權值通過該詞條詞頻與該詞條在一定語言范圍內其他詞的平均相關度的乘積而得到，選用段落范圍內詞語相關度。詞條Ti基于段落同現頻率的詞語相關度的加權值公式如下所示：

(4)

其中，K表示該文檔中除詞條Ti外其他詞條的個數。

式(4)含義為：基于詞語相關度的權重等于原有的TF*IDF乘以平均相關度。通過該方法計算的平均相關度結果較小，不利于區分，所以添加區分系數ρ。則新的相似度計算公式為：

(5)

2.2 Spark框架下基于詞語相關度的KNN算法

對傳統KNN文本分類算法的并行化處理會提高分類的效率，但并行化處理通常會降低分類的準確度。因此，文中在Spark框架下實現KNN算法并行化的同時引入詞語相關度對特征項進行加權處理，提高文本分類的準確度和分類效率。

2.2.1 預處理并行化

首先采用中科院分詞軟件ICTCLAS2015對數據集進行分詞、去除停用詞等預處理。去停詞結果以形式給出，并利用2.1中提出的基于詞語相關度的TF-IDF對向量進行計算，得到相應權重。在文本預處理之前，將訓練集與測試集提交到HDFS中并轉化為RDD對象，分發給每個節點，Map函數通過靜態方法UseDistributedCache()實現對緩存數據的調用。

2.2.2 分類并行化

在KNN算法并行化過程中，以MapReduce模型為基礎，采用Spark計算框架來實現算法的并行化。首先將訓練集D與測試集Ti在HDFS中讀取出來并建立RDD對象，然后將訓練集分割到相應分片中，并將數據集進行緩存以備重復利用，通過分區處理每個Map都將對相近數量的訓練集進行處理。

文中并行化算法為了使分類準確，對每個測試樣本指定一個textID作為key值，然后利用RangePartitioner函數將測試集分成不同的子集Ti，進而通過轉換操作filterByRange函數將測試集Ti讀取進每一個Map任務中。算法1描述了此過程。

算法1：Spark框架下基于詞語相關度的KNN算法。

輸入：訓練集D，測試集T，K

輸出：分類結果

(1)將訓練集在HDFS中讀取并作為RDD對象讀取進Map中；

(2)將測試集在HDFS中讀取并作為RDD對象；

(3)對訓練集和測試集進行規范化處理，并緩存；

(4)Map過程：

使用式(5)計算測試樣本與訓練樣本的距離，并得到每個Map中最小的K個近鄰；

將最小的K個近鄰建立成類別-距離組成的CD向量，并將CD定義進value值中；

將結果發布給Reduce。

(5)Reduce過程：

在Map中讀取結果；

更新距離CDnew向量。對于每個測試樣本，從最近的鄰居開始逐一比較每個鄰居的距離值，如果Map任務轉發來的距離小于當前值，則使用該值更新Reduce過程中相應位置的類和距離；否則，繼續與下一個值比較；

通過判定公式計算最后分類；

輸出結果。

步驟(1)、(2)將訓練集與測試集在HDFS中讀取出來并建立為RDD對象，然后對訓練集D進行分片，同時設置K值。為了使分類準確，將測試集作為RDD讀取但是不與訓練集一起分片，而是根據key值讀取進每個map中比較每一個測試樣本和所有的訓練集。

由于使用余弦相似度來計算樣本間的相似度，將兩個數據集在步驟(3)中進行規范化處理。同時，將數據集進行緩存以備重復利用。

在Map過程中，首先利用式(5)計算測試樣本與每個分片中訓練樣本的相似度距離。通過相似度計算，在每個Map任務中都將得到最近的K個鄰居，將這K個鄰居的類別與相應的相似度距離保存為：CD，并將CD定義進value值中，即，同時根據相似度距離進行升序排列，如圖1所示。每進行一次Map任務處理，就啟動一次Reduce任務，并將中間結果轉發到Reduce任務中。

每完成一次Map任務，Reduce就將CDnew中的距離值與來自Map中CD的對應距離值進行比較，直到得到最終K個近鄰。所有的值更新完畢后，CDnew將包含所有待測樣本的K個最近鄰的類和距離。最后，執行KNN算法的判定函數確定測試集的所屬類別，并將結果作為Reduce階段的最終結果輸出。對于每個測試樣本，Reduce過程將采用ReduceByKey根據之前描述的函數聚集value。

圖1給出了KNN分類并行化處理流程。

圖1 Spark框架下KNN算法并行化過程

3 實 驗

3.1 實驗環境與數據集

在Hadoop平臺上部署了Spark計算框架，通過Vcenter創建了6臺虛擬機，其中包含1個Master節點和5個Slave節點。虛擬機中操作系統均為Ubuntu 14.04.3-Server-amd64版本，Hadoop版本為2.6.0，Spark版本為1.4.0，Java開發包版本為jdk1.7.0_79，程序開發工具為Eclipse Mars.1 Release (4.5.1)。其中Master節點擔任NameNode角色，主要負責管理與調用并維護著所有文件的元數據，Slave節點擔任DataNode角色，根據NameNode的調用檢索和處理數據。

數據集采用Sogou實驗室提供的分類語料庫，選擇語料庫中整理過的搜狐新聞網站新聞語料以及對應的分類信息。實驗中采用的文本為教育、互聯網、財經、軍事、旅游、體育、文化、健康、招聘等20大類，每個類別中有2 000篇文本，共40 000篇文檔。逐個在每個類別中隨機選取500篇文本組成訓練集。為了確保實驗的充分性和有效性，將剩余文本劃分為不同大小，組成不同規模的測試集，如表1所示。

表1 測試集

3.2 評價指標

選用分類方法中常用的準確率(Pr)和查全率(Re)。準確率用于表示分類的正確性，即檢測出分類文檔中正確分類的文檔所占的比率；查全率表示分類的完整性，即所有應分類的文檔中被正確分類的文檔所占的比率，公式如下：

(6)

(7)

同時為了綜合評價分類效果，使用F1值：

(8)

選用加速比對Spark并行化框架進行評價：

(9)

3.3 實驗結果與分析

實驗首先基于詞語相關度對KNN算法的影響進行驗證。以準確率、查全率以及F1值為指標，在單一節點上對比基于詞語相關度算法、距離加權KNN算法以及傳統KNN算法的性能，如表2所示。

表2 三種算法性能比較

由表2可知，在串行狀態下，基于詞語相關度的算法較傳統KNN算法在準確率上提高了2.5～4.9個百分點。而與距離加權KNN算法相比，在小數據集上兩者分類準確率基本相似，但在較大數據集上，基于詞語相關度的KNN算法的準確率隨數據集的增大而逐漸提高。在查全率方面，文中算法較傳統KNN算法與距離加權都有所提高，平均查全率提高了1.3和0.34個百分點。在綜合指標F1中，可以看出文中算法分類效果更佳，較傳統KNN算法與加權KNN算法平均值各提高了2.35和0.24個百分點。因此，在串行狀態下，基于詞語相關度算法可以有效提高KNN文本算法的分類效果。

為了驗證文中算法是否能夠有效彌補并行化過程中分區操作帶來的分類準確率下降的缺陷，對傳統KNN算法、基于Spark框架的傳統KNN算法(3個節點)以及Spark框架下基于詞語相關度優化的KNN算法(3個節點)在不同測試集下進行了比較，結果如表3所示。

表3 并行化算法性能比較

由表3可知，在運行時間方面，Spark框架下基于詞語相關度的KNN算法運行時間較傳統KNN算法縮短了5%～26%，與Spark框架下的傳統KNN算法運行時間基本一致。表明Spark框架下的并行化KNN文本分類算法能夠實現大規模文本數據的分類。而在準確率上，Spark框架下的傳統KNN算法的準確度較串行狀態傳統KNN算法平均降低了2.1%，這是由于通常情況下的并行化算法要對數據集進行分區操作，會降低分類的準確度。而Spark框架下基于詞語相關度的KNN文本分類算法較串行狀態下的傳統KNN分類算法準確率平均提高了1.56個百分點，較Spark框架下的傳統KNN算法提高了3.68個百分點。這是由于使用詞語相關度對相似度進行了優化，彌補了由并行化導致的準確度的影響。因此，文中利用詞語相關度建立的距離機制有效改善了通常情況下并行化分區操作對準確度的影響。

在4個節點的情況下，Spark框架與Hadoop平臺中算法在5個不同規模數據集的運行時間如圖2所示。

圖2 兩種架構運行時間比較

由圖2可知，Hadoop在處理小數據集合時，運行時間較長，這是由于Hadoop平臺處理過程中磁盤I/O計算時花費時間較多，在處理小樣本時較為明顯。而Spark框架將數據存儲在內存中不需要磁盤I/O，因此在各規模數據集下運行時間平緩增長并優于Hadoop。

加速比主要用于衡量一個系統的擴展性能。當采用D4數據集時，Spark和Hadoop在不同節點下的加速比比較如圖3所示。

圖3 兩種架構加速比比較

由圖3可知，加速比在Spark框架下隨節點增加呈線性增長趨勢，由此可知隨著節點的增加能更好地提高分類處理效率，這說明Spark框架在處理KNN分類算法上具有較好的加速比。并且由此可知，節點數不斷增加時Spark的加速比優勢將會更為凸顯。因此，Spark優于Hadoop平臺具有較好的加速比，能夠高效地實現大數據集的處理。

4 結束語

針對KNN分類算法在當前大數據環境下的分類問題，結合詞語相關度對常用的KNN分類相似度進行優化，并在Spark框架下實現算法的并行化，提高分類效率。實驗結果表明，文中提出的并行化算法在保證分類準確率的情況下，較傳統KNN算法在時間效率上有明顯提高。但該算法沒有考慮相似度中其他屬性值的影響，分類效果仍有可提高的空間。

[1] 王小林,陸駱勇,邰偉鵬.基于信息熵的新的詞語相似度算法研究[J].計算機技術與發展,2015,25(9):119-122.

[2] 蘇金樹,張博鋒,徐 昕.基于機器學習的文本分類技術研究進展[J].軟件學報,2006,17(9):1848-1859.

[3] 王邦軍,李凡長,張 莉,等.基于改進協方差特征的李-KNN分類算法[J].模式識別與人工智能,2014,27(2):173-178.

[4] 范恒亮,成衛青.一種基于關聯分析的KNN文本分類方法[J].計算機技術與發展,2014,24(6):71-74.

[5] 王秀利.基于K最近鄰文本分類的偽裝入侵檢測[J].小型微型計算機系統,2014,35(12):2650-2654.

[6] ZHANG L,ZHANG C J,XU Q Y,et al.Weigted-KNN and its application on UCI[C]//Proceedings of the 2015 IEEE international conference on information and automation.[s.l.]:IEEE,2015:1748-1750.

[7] 李正杰,黃 剛.基于Hadoop平臺的SVM_KNN分類算法的研究[J].計算機技術與發展,2016,26(3):75-79.

[8] LU S P,TONG W Q,CHEN Z J.Implementation of the KNN algorithm based on Hadoop[C]//2015 international conference on smart and sustainable city and big data.Shanghai,China:IET,2015:123-126.

[9] ANCHALIA P P,ROY K.The k-Nearest neighbor algorithm using MapReduce paradigm[C]//Proceedings of the 2014 5th international conference on ISMS.[s.l.]:IEEE,2014:513-518.

[10] DEAN J,GHEMAWAT S.MapReduce:simplified data processing on large clusters[J].Communications of ACM,2008,51(1):107-113.

[11] GHEMAWAT S.The Google file system[J].ACM SIGOPS Operating Systems Review,2003,37(5):29-43.

[12] GROLINGER K,HAYES M,HIGASHINO W A,et al.Challenges for MapReduce in big data[C]//Proceedings of the IEEE world congress on services.Anchorage,AK:IEEE,2014:182-189.

[13] ZAHARIA M,CHOWDHURY M,DAS T,et al.Resilient distributed datasets: a fault-tolerant abstraction for in-memory cluster computing[C]//Proceedings of the 9th USENIX conference on networked systems design and implementation.Berkeley:USENIX Association,2012:141-146.

[14] 樓華鋒.面向文本聚類的語義加權研究[D].上海:上海交通大學,2010.

[15] ZAHARIA M,CHOWDHURY M,FRANKLIN M J,et al.Spark:cluster computing with working sets[C]//USENIX conference on hot topics in cloud computing.Boston,MA:USENIX Association,2010:1765-1773.

[16] 梁喜濤,顧 磊.中文分詞與詞性標注研究[J].計算機技術與發展,2015,25(2):175-180.