藏文WEB文檔分類算法

劉昕，安見才讓

藏文WEB文檔分類算法

劉昕，安見才讓

針對藏文WEB文檔分類中KNN算法計算復(fù)雜度高的缺點(diǎn)，不同于以往從減少訓(xùn)練樣本集大小和采用快速算法角度來降低KNN算法的計算復(fù)雜度，從并行的角度出發(fā)，提出了一種基于Java Bean模式的并行算法，其關(guān)鍵部分的時間計算復(fù)雜度從O(n2)降為O(log(n))，該算法與經(jīng)典的串行算法相比，能顯著地提高分類速度。

文檔分類；K近鄰；并行策略；藏文WEB文檔

0 引言

隨著Intemet的迅速發(fā)展，文本分類已經(jīng)成為大規(guī)模數(shù)據(jù)處理的熱點(diǎn)之一。它是從一組已知的訓(xùn)練集樣本中創(chuàng)建分類模型，并且使用這個文本分類模型識別待分類樣本。目前比較常用的分類方法有：樸素貝葉斯（NativeBes，NB）、支持向量機(jī)（Support veetor Maehine，SVM）、K近鄰（K Nearest Neighbour，KNN）等等，其中KNN算法以其實(shí)現(xiàn)的簡單性及較高的分類準(zhǔn)確性在中文文本自動分類等領(lǐng)域得到了廣泛的應(yīng)用。KNN算法的基本思想是在訓(xùn)練樣本中找到測試樣本的K個最近鄰，然后根據(jù)這K個最近鄰的類別來決定測試樣本的類別。但是，該方法對屬性較多的訓(xùn)練樣本進(jìn)行分類時，由于計算量大而使其效率大大降低，效果不很理想。為了在更廣泛的應(yīng)用領(lǐng)域使用KNN算法，如何提高該算法在處理屬性較多的訓(xùn)練樣本時的效率，受到了數(shù)據(jù)挖掘工作者極大的關(guān)注。為了從訓(xùn)練樣本中找到K個近鄰，不得不計算與所有樣本間的距離，而藏文WEB文檔又具有高維的特點(diǎn)，龐大的計算量影響了KNN法的實(shí)時性應(yīng)用。為了提高KNN法的運(yùn)行效率，有很多文獻(xiàn)資料提出減少計算負(fù)擔(dān)的算法[1-4]。這些算法大致可分為兩類：第一類是在保持或近似保持分類性能不變的條件下，減少訓(xùn)練樣本集的大小[2]；第二類是在保持分類性能不變的情況下，采用快速算法。本文不同于以上兩種思路，提出了一種用于網(wǎng)頁文檔分類的基于Java Bean的分布式并行KNN算法，并分析了本文算法的時間復(fù)雜度，分析表明本文算法能極大的提高KNN算法的運(yùn)行效率。

1 經(jīng)典KNN算法

1.1 文本分類的傳統(tǒng)KNN算法

目前在信息處理方面，文本的表示主要采用向量空間模型。向量空間模型的基本思想是以向量表示文本：W1，W2，…Wn，其中Wi為第i個特征項的權(quán)重。KNN是一種有監(jiān)督學(xué)習(xí)的分類算法[6]，它的規(guī)則本身就是數(shù)據(jù)，不需要產(chǎn)生額外的數(shù)據(jù)來描述規(guī)則，不要求數(shù)據(jù)的一致性，即可以存在噪聲。

KNN分類算法的主要思想是：先計算待分類樣本與已知類別的訓(xùn)練樣本之間的距離或相似度，找到距離或相似度與待分類樣本數(shù)據(jù)最近的K個鄰居；再根據(jù)這些鄰居所屬的類別來判斷待分類樣本數(shù)據(jù)的類別。如果待分類樣本數(shù)據(jù)的K個鄰居都屬于一個類別，那么待分類樣本也屬于這個類別。否則，對每一個候選類別進(jìn)行評分，按照某種規(guī)則來確定待分類樣本數(shù)據(jù)的類別。因此，KNN算法必須明確兩個基本的因素：最近鄰樣本的數(shù)目K和相似性函數(shù)。相似度函數(shù)對應(yīng)一個非負(fù)的函數(shù)，用來刻畫不同樣本的相似程度。常用的有夾角余弦相似度函數(shù)、歐氏距離等。歐氏距離函數(shù)如公式（1）：

其中X=(x1,x2,…xn)和Y=(y1,y2,…yn)代表兩個樣本數(shù)據(jù)，

Tibetan WEB Document Classification Algorithm

Liu Xin, Anjian Cairang
(Computer Science Qinghai University for Nationalities, Xining 810007, China)

To optimize the high computation complexity of KNN algorithm in Tibetan web document classification, a parallel algorithm, based on Java Bean mode, is proposed. It means that the time-critical portions of computation complexity can be shortened from O(n2) to O(log(n)). What’s more， it’s different from the traditional way by reducing the training sample size and using high-speed algorithm. All in all, comparing with the typical serial algorithm, it can dramatically increase classification speed.

Document Classification; KNN; Parallel Algorithm; Tibetan Web Document

TP301

A

1007-757X(2016)08-0001-02

青海2014年度教育部“春暉計劃”合作科研項目（Z2015054）

劉 昕（1981-），女，青海，青海民族大學(xué)，計算機(jī)學(xué)院，講師，碩士，研究方向：計算機(jī)網(wǎng)絡(luò)，計算機(jī)應(yīng)用技術(shù)教學(xué)和研究工作，西寧，810007

安見才讓（1969-），男，青海，青海民族大學(xué)，計算機(jī)學(xué)院，教授，碩士，研究方向：藏文信息處理，計算機(jī)應(yīng)用技術(shù)教學(xué)和研究工作，西寧，810007