一種在MapReduce下實(shí)現(xiàn)的KNN改進(jìn)算法

潘俊輝 王 輝 張 強(qiáng) 王浩暢

(東北石油大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院， 黑龍江 大慶 163318)

數(shù)據(jù)挖掘中的文本分類就是按照文本的主題(屬性)對文本進(jìn)行分類，以方便管理與分析海量的文本數(shù)據(jù)。Apache基金會開發(fā)的分布式系統(tǒng)基礎(chǔ)架構(gòu)Hadoop，作為云計(jì)算平臺，提供了分布式文件系統(tǒng)組件HDFS和編程模型MapReduce，利用此組件和模型的特點(diǎn)可實(shí)現(xiàn)對文本分類的并行化處理。有關(guān)研究目前已經(jīng)取得了許多成果[1-4]。本次研究，我們針對最近鄰分類算法(K-Nearest Neighbor，簡稱“KNN”)存在的不足，提出一種在Hadoop平臺MapReduce下進(jìn)行子類劃分的分類算法(簡稱“ZKNN”)，通過在訓(xùn)練階段構(gòu)造初級分類器，減少訓(xùn)練階段的計(jì)算量，從而提高分類效率。

1 文本分類基礎(chǔ)

文本分類是通過使用分類算法將需要分析的若干文本歸入指定的某個(gè)或某幾個(gè)類別的過程。用數(shù)學(xué)公式表示，即f：D→C，D={d1，d2，…，dm}，C={c1，c2，…，cn}，D為語料庫中的文本集合，C為類別集合，m和n分別表示文本個(gè)數(shù)和類別個(gè)數(shù)。

Hadoop平臺的MapReduce，可把并行計(jì)算過程最終抽象到map和reduce函數(shù)上。MapReduce在對大數(shù)據(jù)集進(jìn)行處理時(shí)會首先將其分成很多個(gè)小數(shù)據(jù)集，把具有相同鍵值的數(shù)據(jù)集分到一個(gè)分區(qū)，并按鍵值大小排序；然后由Reduce函數(shù)取出數(shù)據(jù)和計(jì)算數(shù)據(jù)，并將結(jié)果存入HDFS中[5]。

2 對KNN算法的改進(jìn)

按KNN算法進(jìn)行文本分類，首先要對訓(xùn)練集中的文本進(jìn)行預(yù)處理，并用虛擬交換矩陣(VSM)表示。如對新文本d進(jìn)行測試，先要對其進(jìn)行向量化的處理，然后利用距離計(jì)算公式得到d與不同文本類的距離，從中選擇出距離最小的K個(gè)文本，依據(jù)它們的類別對d進(jìn)行歸類[6]。歸類時(shí)，可以按照類別的不同對K個(gè)文本進(jìn)行分組，并按式(1)計(jì)算得到距離和，然后將d歸入最小距離和所對應(yīng)的類別中。

(1)

式中：dis(d，di)表示文本d與di之間的距離。如果文檔di屬于類別ci，則y(di，ci)=1；否則，y(di，ci)=0。

在訓(xùn)練集中，每類文本會按照不同的主題進(jìn)行劃分，同一主題下又可按照側(cè)重點(diǎn)的不同進(jìn)一步進(jìn)行劃分。因此，可將不同的類別均劃分成S個(gè)子類。另一方面，將文本用VSM表示后，可將其看作特征空間的一個(gè)節(jié)點(diǎn)(node)，這樣就可根據(jù)節(jié)點(diǎn)的密集程度劃分子類，同一子類的節(jié)點(diǎn)相對密集，不同子類的節(jié)點(diǎn)間則相對稀疏。由此，我們可以首先在類的特征空間選擇分散的z個(gè)節(jié)點(diǎn)作為初始子類，然后采用類似聚類的方法，將該類中的節(jié)點(diǎn)按照距離最近的原則，把初始的z個(gè)節(jié)點(diǎn)劃分到不同的子類中。與聚類方法不同的是，這樣劃分子類不需進(jìn)行迭代操作，經(jīng)過一次操作即可得到z個(gè)子類。劃分子類的流程如下：

Step 1：按照式(2)計(jì)算類中心，然后從ci中找出距類中心最遠(yuǎn)的一個(gè)node，將其并入S中。

(2)

Step 2：計(jì)算S中所有node距類別ci中剩余node的最小距離值L，從所有最小距離node中選擇出距離最大的node，將其并入S中。

Step 3：當(dāng)S中的node數(shù)量達(dá)到z時(shí)，停止Step 2的執(zhí)行。

Step 4：將S中的z個(gè)node看作子類，按照距離最近原則，將ci中的node歸入z個(gè)不同子類中。

Step 5：計(jì)算z個(gè)子類的類中心向量。

對z的取值，一般是在類別個(gè)數(shù)n和訓(xùn)練集中最小類別的文本個(gè)數(shù)min|ci|之間確定某個(gè)值。

3 在MapReduce下實(shí)現(xiàn)分類

3.1 子類劃分

基于MapReduce進(jìn)行并行分類時(shí)，采用ZKNN算法實(shí)現(xiàn)子類的劃分。為提高執(zhí)行效率，我們可以通過2個(gè)job來實(shí)現(xiàn)：job A負(fù)責(zé)劃分子類；job B用于進(jìn)行中心向量的計(jì)算。具體實(shí)現(xiàn)過程如圖1所示。

圖1 劃分子類的MapReduce過程

(1) 將 作為job A中map函數(shù)的輸入，得到相應(yīng)的class類別。利用分區(qū)函數(shù)將同一class歸入到一個(gè)reduce中去執(zhí)行，reduce函數(shù)的輸入為 。這樣，同類別的文本被歸入到reduce中。接著劃分子類，為reduce函數(shù)的輸出。job A的map階段和reduce階段的偽代碼分別為：

map(key，value)

{ class=GetClass (key);

Write(class，file+TFIDF);

}

reduce(key，values)

{ subSet=Huafensub(values);

for sub in subSet

for docID in sub

Write(sub+file，TFIDF);

}

(2) 將 作為job B中map函數(shù)的輸入，其工作為去掉key中的file。然后，進(jìn)入reduce執(zhí)行。reduce會根據(jù)輸入值sub計(jì)算得到InVec類中心向量，即 。job B的map和reduce的偽代碼分別為：

map(key，value)

{ sub=getSub (key);

Write(sub，value);

}

reduce(key，values)

{ InVec=Compute(values)

Write(key，InVec);

}

3.2 文本分類

劃分子類之后，利用ZKNN實(shí)現(xiàn)文本分類，由一個(gè)MapReduce完成。其中， 為map的輸入，這個(gè)階段的工作是找出距離最近的K個(gè)子類，并得到最鄰近的K個(gè)文本。map的輸出為 ，其中distance指文本間的距離。將map的輸出作為reduce的輸入，計(jì)算得到testfile的類別newcategory。因此， 為reduce的輸出。下面給出該MapReduce的偽代碼，實(shí)現(xiàn)文本分類的MapReduce過程如圖2所示。

map(key，value)

{ adjacentFiles=ZKNN(key);

for file in adjacentFiles

Write(testfile，file+distance);

}

reduce(key，values)

{ newcategory=gainNew(values);

Write(key，newcategory);

}

圖2 實(shí)現(xiàn)分類的MapReduce過程

4 實(shí)驗(yàn)及分類結(jié)果比較

實(shí)驗(yàn)使用的語料庫來自復(fù)旦大學(xué)的分類語料庫。選取其訓(xùn)練語料庫中的C31-Environment(環(huán)境)、C32-Agriculture(農(nóng)業(yè))、C19-Computer(計(jì)算機(jī))、C3-Art(藝術(shù))、C34-Economy(經(jīng)濟(jì))等5個(gè)類別，作為訓(xùn)練語料庫。測試語料庫同樣選取相同的5個(gè)類別，每個(gè)類別選取700個(gè)測試文本。

采用3臺同構(gòu)的計(jì)算機(jī)搭建Hadoop集群。其中，使用1臺機(jī)器作為集群中的主節(jié)點(diǎn)，剩下的2臺機(jī)器用作從節(jié)點(diǎn)。分別采用ZKNN和經(jīng)典KNN算法，比較其分類精度和所用時(shí)間。實(shí)驗(yàn)分別在節(jié)點(diǎn)個(gè)數(shù)為1、2、3的情況下進(jìn)行。

在數(shù)據(jù)集和特征值個(gè)數(shù)均相同的情況下，ZKNN算法在查準(zhǔn)率、召回率2項(xiàng)指標(biāo)上和經(jīng)典KNN算法差不多，只有少數(shù)類別的指標(biāo)值會有輕微波動(dòng)(見表1)。由此可見，ZKNN算法在對文本進(jìn)行分類時(shí)不會影響到文本的分類性能。同時(shí)，在不影響分類精度的情況下，與經(jīng)典KNN算法相比，基于MapReduce的ZKNN算法則能夠有效減少文本分類所需時(shí)間(見表2)。

表1 分類性能對比

表2 完成分類所需的執(zhí)行時(shí)間

5 結(jié) 語

經(jīng)典的分類算法KNN具有實(shí)現(xiàn)簡單、穩(wěn)定等優(yōu)點(diǎn)，但在處理海量數(shù)據(jù)時(shí)分類速度較慢，需要花費(fèi)較多的時(shí)間。另外，KNN算法在文本預(yù)處理后就不作處理，缺少訓(xùn)練階段，這也會導(dǎo)致計(jì)算的復(fù)雜度增加，從而影響分類效率。為了提升文本分類效率，對KNN算法進(jìn)行改進(jìn)，主要是通過在訓(xùn)練階段構(gòu)造初級分類器以減少訓(xùn)練階段的計(jì)算量，并在MapReduce下予以實(shí)現(xiàn)。實(shí)驗(yàn)結(jié)果表明，面對大數(shù)據(jù)進(jìn)行文本分類，改進(jìn)后的算法可以在保證分類精度的情況下節(jié)省運(yùn)行時(shí)間，比經(jīng)典KNN算法所需的運(yùn)行時(shí)間少很多。