基于Spark與詞語(yǔ)相關(guān)度的KNN文本分類算法

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

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

0 引 言

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

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

分類算法中的距離機(jī)制直接影響分類效果。傳統(tǒng)KNN的距離機(jī)制僅通過(guò)詞頻計(jì)算兩樣本間的相似度，而在實(shí)際分類過(guò)程中，文本詞語(yǔ)間具有一定相關(guān)性。同時(shí)，在大數(shù)據(jù)環(huán)境中，數(shù)據(jù)集不斷增大，KNN分類算法的計(jì)算復(fù)雜度不斷增加，導(dǎo)致運(yùn)行時(shí)間增多。

因此，文中在KNN相似度計(jì)算過(guò)程中引入詞語(yǔ)相關(guān)度進(jìn)行特征項(xiàng)加權(quán)，同時(shí)在Spark框架下實(shí)現(xiàn)KNN文本分類算法的并行化，以提高分類的準(zhǔn)確度。

1 相關(guān)技術(shù)

1.1 KNN文本分類算法

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

余弦相似度計(jì)算公式如下：

(1)

其中，wik表示Di文本中第k個(gè)特征的權(quán)重。

通過(guò)相似度計(jì)算得到K個(gè)相似度最大的樣本即K個(gè)最近鄰，并利用式(2)計(jì)算權(quán)重判斷最終歸類。

(2)

1.2 詞語(yǔ)間相關(guān)度

一個(gè)詞條對(duì)于文檔的主題是否具有代表性與該詞條所在一定范圍內(nèi)其他詞語(yǔ)在文檔中的出現(xiàn)頻率(同現(xiàn)頻率)是相關(guān)的[13]，詞語(yǔ)間相關(guān)度指兩個(gè)詞語(yǔ)同時(shí)出現(xiàn)在一定語(yǔ)言范圍內(nèi)的概率大小。

計(jì)算方法如下：

(1)依據(jù)文本預(yù)處理后特征空間基向量所包含的詞條個(gè)數(shù)定義一個(gè)N×N維的詞語(yǔ)相關(guān)度矩陣，其中N為特征空間中的基向量數(shù)目，基向量的一個(gè)詞條對(duì)應(yīng)矩陣中的一維數(shù)據(jù)，矩陣內(nèi)各對(duì)應(yīng)值初始為0。

(2)計(jì)算全部段落范圍內(nèi)同時(shí)出現(xiàn)的詞條對(duì)得到段落同現(xiàn)頻率。在同一段落中，如果詞條Ti和詞條Tj同時(shí)出現(xiàn)，則詞語(yǔ)相關(guān)度矩陣中的對(duì)應(yīng)值加一。

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

在得到對(duì)應(yīng)的同現(xiàn)頻率后，即可計(jì)算相應(yīng)的詞語(yǔ)相關(guān)度，詞條Ti和詞條Tj基于段落同時(shí)出現(xiàn)頻率的相關(guān)度RPij計(jì)算為：

(3)

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

1.3 Spark框架

Spark是由UCBerkeley開發(fā)的一種基于內(nèi)存的計(jì)算框架。Spark框架由兩個(gè)主要部分組成：彈性分布式數(shù)據(jù)集和并行運(yùn)算。RDD是Spark框架計(jì)算中重要的概念，是Spark框架的核心和基礎(chǔ)。

RDD是Spark框架的核心，是各個(gè)集群節(jié)點(diǎn)中數(shù)據(jù)共享的一種有效抽象。Spark所執(zhí)行的數(shù)據(jù)處理是基于RDD進(jìn)行的。RDD是可并行的數(shù)據(jù)結(jié)構(gòu)，同時(shí)允許用戶將數(shù)據(jù)存儲(chǔ)在內(nèi)存中，方便用戶對(duì)數(shù)據(jù)的重復(fù)調(diào)用，減少了磁盤I/O的負(fù)載。RDD是不可變的集合，不能在原有RDD上實(shí)現(xiàn)內(nèi)容的修改，只能創(chuàng)建一個(gè)新的RDD：

(1)通過(guò)對(duì)文件共享系統(tǒng)(HBase、HDFS、Hive)的讀取得到RDD；

(2)通過(guò)驅(qū)動(dòng)程序中用作并行計(jì)算的Scala集合創(chuàng)建；

(3)通過(guò)對(duì)已存在的RDD執(zhí)行轉(zhuǎn)換操作新建一個(gè)RDD；

(4)通過(guò)持久化操作進(jìn)而轉(zhuǎn)變現(xiàn)有的RDD。

并行運(yùn)算包括轉(zhuǎn)換(transform)和動(dòng)作(action)。轉(zhuǎn)換操作只依據(jù)原有的RDD定義一個(gè)新的RDD，而不對(duì)它進(jìn)行直接計(jì)算；動(dòng)作是對(duì)某個(gè)值立即進(jìn)行計(jì)算，并返回結(jié)果給驅(qū)動(dòng)程序[14]。

對(duì)RDD的控制還可利用緩存和分區(qū)操作。將RDD緩存在內(nèi)存中，便于下次計(jì)算時(shí)的重復(fù)利用，減少了磁盤開銷。RDD可根據(jù)key來(lái)指定分區(qū)順序，將數(shù)據(jù)劃分到不同分區(qū)中。

2 Spark框架下基于詞語(yǔ)相關(guān)度的KNN算法

為了提高文本分類效率，分類算法的并行化處理是當(dāng)前的一大趨勢(shì)，但通過(guò)研究發(fā)現(xiàn)，在KNN文本分類的一般并行化過(guò)程中會(huì)降低分類準(zhǔn)確率。因此文中在訓(xùn)練樣本與待測(cè)樣本的相似度計(jì)算過(guò)程中引入詞語(yǔ)相關(guān)度，提高分類準(zhǔn)確度并在Spark計(jì)算框架下實(shí)現(xiàn)并行化，降低運(yùn)算時(shí)間。

2.1 基于詞語(yǔ)相關(guān)度的相似度計(jì)算

通常情況下，傳統(tǒng)KNN相似度計(jì)算方法單純使用TF-IDF[15]計(jì)算相關(guān)度，忽略了文本數(shù)據(jù)本身詞語(yǔ)間的關(guān)系，易導(dǎo)致文本內(nèi)容表達(dá)的不完整，影響文本分類的準(zhǔn)確率[16]。因此，定義合適的距離機(jī)制是分類準(zhǔn)確的前提。文中在KNN分類算法相似度距離計(jì)算中引入詞語(yǔ)相關(guān)度概念。

基于詞語(yǔ)相關(guān)度的權(quán)值通過(guò)該詞條詞頻與該詞條在一定語(yǔ)言范圍內(nèi)其他詞的平均相關(guān)度的乘積而得到，選用段落范圍內(nèi)詞語(yǔ)相關(guān)度。詞條Ti基于段落同現(xiàn)頻率的詞語(yǔ)相關(guān)度的加權(quán)值公式如下所示：

(4)

其中，K表示該文檔中除詞條Ti外其他詞條的個(gè)數(shù)。

式(4)含義為：基于詞語(yǔ)相關(guān)度的權(quán)重等于原有的TF*IDF乘以平均相關(guān)度。通過(guò)該方法計(jì)算的平均相關(guān)度結(jié)果較小，不利于區(qū)分，所以添加區(qū)分系數(shù)ρ。則新的相似度計(jì)算公式為：

(5)

2.2 Spark框架下基于詞語(yǔ)相關(guān)度的KNN算法

對(duì)傳統(tǒng)KNN文本分類算法的并行化處理會(huì)提高分類的效率，但并行化處理通常會(huì)降低分類的準(zhǔn)確度。因此，文中在Spark框架下實(shí)現(xiàn)KNN算法并行化的同時(shí)引入詞語(yǔ)相關(guān)度對(duì)特征項(xiàng)進(jìn)行加權(quán)處理，提高文本分類的準(zhǔn)確度和分類效率。

2.2.1 預(yù)處理并行化

首先采用中科院分詞軟件ICTCLAS2015對(duì)數(shù)據(jù)集進(jìn)行分詞、去除停用詞等預(yù)處理。去停詞結(jié)果以形式給出，并利用2.1中提出的基于詞語(yǔ)相關(guān)度的TF-IDF對(duì)向量進(jìn)行計(jì)算，得到相應(yīng)權(quán)重。在文本預(yù)處理之前，將訓(xùn)練集與測(cè)試集提交到HDFS中并轉(zhuǎn)化為RDD對(duì)象，分發(fā)給每個(gè)節(jié)點(diǎn)，Map函數(shù)通過(guò)靜態(tài)方法UseDistributedCache()實(shí)現(xiàn)對(duì)緩存數(shù)據(jù)的調(diào)用。

2.2.2 分類并行化

在KNN算法并行化過(guò)程中，以MapReduce模型為基礎(chǔ)，采用Spark計(jì)算框架來(lái)實(shí)現(xiàn)算法的并行化。首先將訓(xùn)練集D與測(cè)試集Ti在HDFS中讀取出來(lái)并建立RDD對(duì)象，然后將訓(xùn)練集分割到相應(yīng)分片中，并將數(shù)據(jù)集進(jìn)行緩存以備重復(fù)利用，通過(guò)分區(qū)處理每個(gè)Map都將對(duì)相近數(shù)量的訓(xùn)練集進(jìn)行處理。

文中并行化算法為了使分類準(zhǔn)確，對(duì)每個(gè)測(cè)試樣本指定一個(gè)textID作為key值，然后利用RangePartitioner函數(shù)將測(cè)試集分成不同的子集Ti，進(jìn)而通過(guò)轉(zhuǎn)換操作filterByRange函數(shù)將測(cè)試集Ti讀取進(jìn)每一個(gè)Map任務(wù)中。算法1描述了此過(guò)程。

算法1：Spark框架下基于詞語(yǔ)相關(guān)度的KNN算法。

輸入：訓(xùn)練集D，測(cè)試集T，K

輸出：分類結(jié)果

(1)將訓(xùn)練集在HDFS中讀取并作為RDD對(duì)象讀取進(jìn)Map中；

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

(3)對(duì)訓(xùn)練集和測(cè)試集進(jìn)行規(guī)范化處理，并緩存；

(4)Map過(guò)程：

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

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

將結(jié)果發(fā)布給Reduce。

(5)Reduce過(guò)程：

在Map中讀取結(jié)果；

更新距離CDnew向量。對(duì)于每個(gè)測(cè)試樣本，從最近的鄰居開始逐一比較每個(gè)鄰居的距離值，如果Map任務(wù)轉(zhuǎn)發(fā)來(lái)的距離小于當(dāng)前值，則使用該值更新Reduce過(guò)程中相應(yīng)位置的類和距離；否則，繼續(xù)與下一個(gè)值比較；

通過(guò)判定公式計(jì)算最后分類；

輸出結(jié)果。

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

由于使用余弦相似度來(lái)計(jì)算樣本間的相似度，將兩個(gè)數(shù)據(jù)集在步驟(3)中進(jìn)行規(guī)范化處理。同時(shí)，將數(shù)據(jù)集進(jìn)行緩存以備重復(fù)利用。

在Map過(guò)程中，首先利用式(5)計(jì)算測(cè)試樣本與每個(gè)分片中訓(xùn)練樣本的相似度距離。通過(guò)相似度計(jì)算，在每個(gè)Map任務(wù)中都將得到最近的K個(gè)鄰居，將這K個(gè)鄰居的類別與相應(yīng)的相似度距離保存為：CD，并將CD定義進(jìn)value值中，即，同時(shí)根據(jù)相似度距離進(jìn)行升序排列，如圖1所示。每進(jìn)行一次Map任務(wù)處理，就啟動(dòng)一次Reduce任務(wù)，并將中間結(jié)果轉(zhuǎn)發(fā)到Reduce任務(wù)中。

每完成一次Map任務(wù)，Reduce就將CDnew中的距離值與來(lái)自Map中CD的對(duì)應(yīng)距離值進(jìn)行比較，直到得到最終K個(gè)近鄰。所有的值更新完畢后，CDnew將包含所有待測(cè)樣本的K個(gè)最近鄰的類和距離。最后，執(zhí)行KNN算法的判定函數(shù)確定測(cè)試集的所屬類別，并將結(jié)果作為Reduce階段的最終結(jié)果輸出。對(duì)于每個(gè)測(cè)試樣本，Reduce過(guò)程將采用ReduceByKey根據(jù)之前描述的函數(shù)聚集value。

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

圖1 Spark框架下KNN算法并行化過(guò)程

3 實(shí) 驗(yàn)

3.1 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)集

在Hadoop平臺(tái)上部署了Spark計(jì)算框架，通過(guò)Vcenter創(chuàng)建了6臺(tái)虛擬機(jī)，其中包含1個(gè)Master節(jié)點(diǎn)和5個(gè)Slave節(jié)點(diǎn)。虛擬機(jī)中操作系統(tǒng)均為Ubuntu 14.04.3-Server-amd64版本，Hadoop版本為2.6.0，Spark版本為1.4.0，Java開發(fā)包版本為jdk1.7.0_79，程序開發(fā)工具為Eclipse Mars.1 Release (4.5.1)。其中Master節(jié)點(diǎn)擔(dān)任NameNode角色，主要負(fù)責(zé)管理與調(diào)用并維護(hù)著所有文件的元數(shù)據(jù)，Slave節(jié)點(diǎn)擔(dān)任DataNode角色，根據(jù)NameNode的調(diào)用檢索和處理數(shù)據(jù)。

數(shù)據(jù)集采用Sogou實(shí)驗(yàn)室提供的分類語(yǔ)料庫(kù)，選擇語(yǔ)料庫(kù)中整理過(guò)的搜狐新聞網(wǎng)站新聞?wù)Z料以及對(duì)應(yīng)的分類信息。實(shí)驗(yàn)中采用的文本為教育、互聯(lián)網(wǎng)、財(cái)經(jīng)、軍事、旅游、體育、文化、健康、招聘等20大類，每個(gè)類別中有2 000篇文本，共40 000篇文檔。逐個(gè)在每個(gè)類別中隨機(jī)選取500篇文本組成訓(xùn)練集。為了確保實(shí)驗(yàn)的充分性和有效性，將剩余文本劃分為不同大小，組成不同規(guī)模的測(cè)試集，如表1所示。

表1 測(cè)試集

3.2 評(píng)價(jià)指標(biāo)

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

(6)

(7)

同時(shí)為了綜合評(píng)價(jià)分類效果，使用F1值：

(8)

選用加速比對(duì)Spark并行化框架進(jìn)行評(píng)價(jià)：

(9)

3.3 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)首先基于詞語(yǔ)相關(guān)度對(duì)KNN算法的影響進(jìn)行驗(yàn)證。以準(zhǔn)確率、查全率以及F1值為指標(biāo)，在單一節(jié)點(diǎn)上對(duì)比基于詞語(yǔ)相關(guān)度算法、距離加權(quán)KNN算法以及傳統(tǒng)KNN算法的性能，如表2所示。

表2 三種算法性能比較

由表2可知，在串行狀態(tài)下，基于詞語(yǔ)相關(guān)度的算法較傳統(tǒng)KNN算法在準(zhǔn)確率上提高了2.5～4.9個(gè)百分點(diǎn)。而與距離加權(quán)KNN算法相比，在小數(shù)據(jù)集上兩者分類準(zhǔn)確率基本相似，但在較大數(shù)據(jù)集上，基于詞語(yǔ)相關(guān)度的KNN算法的準(zhǔn)確率隨數(shù)據(jù)集的增大而逐漸提高。在查全率方面，文中算法較傳統(tǒng)KNN算法與距離加權(quán)都有所提高，平均查全率提高了1.3和0.34個(gè)百分點(diǎn)。在綜合指標(biāo)F1中，可以看出文中算法分類效果更佳，較傳統(tǒng)KNN算法與加權(quán)KNN算法平均值各提高了2.35和0.24個(gè)百分點(diǎn)。因此，在串行狀態(tài)下，基于詞語(yǔ)相關(guān)度算法可以有效提高KNN文本算法的分類效果。

為了驗(yàn)證文中算法是否能夠有效彌補(bǔ)并行化過(guò)程中分區(qū)操作帶來(lái)的分類準(zhǔn)確率下降的缺陷，對(duì)傳統(tǒng)KNN算法、基于Spark框架的傳統(tǒng)KNN算法(3個(gè)節(jié)點(diǎn))以及Spark框架下基于詞語(yǔ)相關(guān)度優(yōu)化的KNN算法(3個(gè)節(jié)點(diǎn))在不同測(cè)試集下進(jìn)行了比較，結(jié)果如表3所示。

表3 并行化算法性能比較

由表3可知，在運(yùn)行時(shí)間方面，Spark框架下基于詞語(yǔ)相關(guān)度的KNN算法運(yùn)行時(shí)間較傳統(tǒng)KNN算法縮短了5%～26%，與Spark框架下的傳統(tǒng)KNN算法運(yùn)行時(shí)間基本一致。表明Spark框架下的并行化KNN文本分類算法能夠?qū)崿F(xiàn)大規(guī)模文本數(shù)據(jù)的分類。而在準(zhǔn)確率上，Spark框架下的傳統(tǒng)KNN算法的準(zhǔn)確度較串行狀態(tài)傳統(tǒng)KNN算法平均降低了2.1%，這是由于通常情況下的并行化算法要對(duì)數(shù)據(jù)集進(jìn)行分區(qū)操作，會(huì)降低分類的準(zhǔn)確度。而Spark框架下基于詞語(yǔ)相關(guān)度的KNN文本分類算法較串行狀態(tài)下的傳統(tǒng)KNN分類算法準(zhǔn)確率平均提高了1.56個(gè)百分點(diǎn)，較Spark框架下的傳統(tǒng)KNN算法提高了3.68個(gè)百分點(diǎn)。這是由于使用詞語(yǔ)相關(guān)度對(duì)相似度進(jìn)行了優(yōu)化，彌補(bǔ)了由并行化導(dǎo)致的準(zhǔn)確度的影響。因此，文中利用詞語(yǔ)相關(guān)度建立的距離機(jī)制有效改善了通常情況下并行化分區(qū)操作對(duì)準(zhǔn)確度的影響。

在4個(gè)節(jié)點(diǎn)的情況下，Spark框架與Hadoop平臺(tái)中算法在5個(gè)不同規(guī)模數(shù)據(jù)集的運(yùn)行時(shí)間如圖2所示。

圖2 兩種架構(gòu)運(yùn)行時(shí)間比較

由圖2可知，Hadoop在處理小數(shù)據(jù)集合時(shí)，運(yùn)行時(shí)間較長(zhǎng)，這是由于Hadoop平臺(tái)處理過(guò)程中磁盤I/O計(jì)算時(shí)花費(fèi)時(shí)間較多，在處理小樣本時(shí)較為明顯。而Spark框架將數(shù)據(jù)存儲(chǔ)在內(nèi)存中不需要磁盤I/O，因此在各規(guī)模數(shù)據(jù)集下運(yùn)行時(shí)間平緩增長(zhǎng)并優(yōu)于Hadoop。

加速比主要用于衡量一個(gè)系統(tǒng)的擴(kuò)展性能。當(dāng)采用D4數(shù)據(jù)集時(shí)，Spark和Hadoop在不同節(jié)點(diǎn)下的加速比比較如圖3所示。

圖3 兩種架構(gòu)加速比比較

由圖3可知，加速比在Spark框架下隨節(jié)點(diǎn)增加呈線性增長(zhǎng)趨勢(shì)，由此可知隨著節(jié)點(diǎn)的增加能更好地提高分類處理效率，這說(shuō)明Spark框架在處理KNN分類算法上具有較好的加速比。并且由此可知，節(jié)點(diǎn)數(shù)不斷增加時(shí)Spark的加速比優(yōu)勢(shì)將會(huì)更為凸顯。因此，Spark優(yōu)于Hadoop平臺(tái)具有較好的加速比，能夠高效地實(shí)現(xiàn)大數(shù)據(jù)集的處理。

4 結(jié)束語(yǔ)

針對(duì)KNN分類算法在當(dāng)前大數(shù)據(jù)環(huán)境下的分類問(wèn)題，結(jié)合詞語(yǔ)相關(guān)度對(duì)常用的KNN分類相似度進(jìn)行優(yōu)化，并在Spark框架下實(shí)現(xiàn)算法的并行化，提高分類效率。實(shí)驗(yàn)結(jié)果表明，文中提出的并行化算法在保證分類準(zhǔn)確率的情況下，較傳統(tǒng)KNN算法在時(shí)間效率上有明顯提高。但該算法沒(méi)有考慮相似度中其他屬性值的影響，分類效果仍有可提高的空間。

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

[2] 蘇金樹,張博鋒,徐 昕.基于機(jī)器學(xué)習(xí)的文本分類技術(shù)研究進(jìn)展[J].軟件學(xué)報(bào),2006,17(9):1848-1859.

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

[4] 范恒亮,成衛(wèi)青.一種基于關(guān)聯(lián)分析的KNN文本分類方法[J].計(jì)算機(jī)技術(shù)與發(fā)展,2014,24(6):71-74.

[5] 王秀利.基于K最近鄰文本分類的偽裝入侵檢測(cè)[J].小型微型計(jì)算機(jī)系統(tǒng),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平臺(tái)的SVM_KNN分類算法的研究[J].計(jì)算機(jī)技術(shù)與發(fā)展,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] 樓華鋒.面向文本聚類的語(yǔ)義加權(quán)研究[D].上海:上海交通大學(xué),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] 梁喜濤,顧 磊.中文分詞與詞性標(biāo)注研究[J].計(jì)算機(jī)技術(shù)與發(fā)展,2015,25(2):175-180.