潘俊輝 王 輝 張 強 王浩暢

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

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

1 文本分類基礎(chǔ)

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

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

2 對KNN算法的改進

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

(1)

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

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

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

(2)

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

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

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

Step 5：計算z個子類的類中心向量。

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

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

3.1 子類劃分

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

圖1 劃分子類的MapReduce過程

(1) 將 作為job A中map函數(shù)的輸入，得到相應(yīng)的class類別。利用分區(qū)函數(shù)將同一class歸入到一個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。然后，進入reduce執(zhí)行。reduce會根據(jù)輸入值sub計算得到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實現(xiàn)文本分類，由一個MapReduce完成。其中， 為map的輸入，這個階段的工作是找出距離最近的K個子類，并得到最鄰近的K個文本。map的輸出為 ，其中distance指文本間的距離。將map的輸出作為reduce的輸入，計算得到testfile的類別newcategory。因此， 為reduce的輸出。下面給出該MapReduce的偽代碼，實現(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 實現(xiàn)分類的MapReduce過程

4 實驗及分類結(jié)果比較

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

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

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

表1 分類性能對比

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

5 結(jié) 語

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