一種新穎的基于馬氏距離的文本分類方法的研究

張素莉,潘 欣

(長春工程學院電氣與信息工程學院,長春 130012)

0 引言

et al.,1994)、支持向量機SVM 算法[3](Joachims,1998)、遺傳算法[4](Svingen,1998)、KNN 算法 、基自組織映射算法[5](Hyotyniemi,1996)、貝葉斯算法[6](Lam,1997)及其樸素貝葉斯算法(Nigam,1999)等,其中KNN(k最近鄰算法)算法是最成熟最簡單的分類方法之一。而KNN分類器對分類過程中所使用的距離參數十分敏感[3](Jahromia etal.,2009),這一缺點不但降低了對文本分類的精度,而且也限制了KNN分類器在文本分類中的應用。

本文提出了一種新穎的基于馬氏距離的KNN文本分類方法(M ahalanobis distance KNN,MDKNN)。該分類器不需使用距離函數的參數K,而是通過整個訓練集的分布情況來決定分類的種類。實驗表明,與傳統(tǒng)的KNN 和Na?ve Bayes分類算法相比,MDKNN在文本分類的精度和穩(wěn)定性上有所提高。

1 馬氏距離及其分類算法

文本數據挖掘可以廣義地定義為一個知識密集的過程,即用戶通過使用一套分析工具與文檔交互[1](Ronen and James,2007)。文本分類(TC)是文本數據挖掘研究中最常見的研究問題之一。如何從信息源中提取具有準確性和時效性的文本分類知識有賴于分類技術的使用,因此,如何提高文本分類的精度是當前文本數據挖掘研究的熱點問題之一。

目前,常用的文本分類技術主要有:基于神經網絡(NN)的文本分類算法[2](Liet al.,1991;Farkas

1.1 馬氏距離

M ahalanobis距離(馬氏距離)是由印度統(tǒng)計學家馬哈拉諾比斯[7](P.C.Mahalanobis)于1936年提出的,表示數據的協(xié)方差距離。它是一種有效的計算2個未知樣本集的相似度的方法。與歐式距離不同的是它考慮到各種特性之間的聯系,并且是尺度無關的,即獨立于測量尺度。如果列向量 x=(x1,x2,…,xN)T的每一項均是隨機變量,且均是有限方差,則協(xié)方差矩陣S的每一項(i,j)都是協(xié)方差向量,可以用式(1)來表示:

Sij=cov(Xi,Xj)=E[(Xi-μi)(X j-μj)](1)

其中用μi=E(Xi)表示每一個向量X的期望值,則我們可以用式(2)表示協(xié)方差矩陣S:

因此,多變量向量x=(x1,x2,…,xN)T的馬氏距離可以通過一組均值數據 μ=(μ1,μ2,…,μN)T和協(xié)方差矩陣S表示,如式(3)所示:

我們可以使用式(3)來分析簡單情況下的馬氏距離,并將其與歐氏距離進行對比。馬氏距離充分考慮了N維歐式空間的測試點屬于該集合的可能性問題,在這里我們給出了一些明確屬于馬氏距離集合的樣本,其中離大多數樣本中心越近的點,屬于這個集合的可能性越大?？梢酝ㄟ^一組二維數據X(在圖中標記為圓圈)來比較馬氏距離和歐式距離,共有100個的樣本訓練集,其均值為 μ=[0;0],并且θ=[1 0.9;0.9 1];,有4個樣本數據Y(用星號標記),分別是[1 1;1-1;-1 1;-1-1]。

圖1 訓練集Y和X

從圖1中,我們可以看出,Y 1和Y 3在 X樣本集附近,而Y 2和Y 4點遠離X樣本集。歐式距離僅僅能夠比較2個樣本的距離,即能得到X的均值是[0;0]和Y與X的均值是D=sqrt(2),不能展示Y和X之間的關系。當我們使用馬氏距離的時候,它不僅能夠描述一個樣本和所有樣本X之間的距離D=[1.34;17.22;18.66;1.05],也能通過馬氏距離真正地反應Y和X之間的關系。

1.2 分類算法

根據式(2)和式(3),我們構建了基于KNN分類器的馬氏距離(MDKNN),該算法的訓練和分類過程如下:

(1)訓練階段:

輸入:多維向量的訓練集合 T=(X1,X2,…,XN),訓練集合中的每一個XN一定屬于某一個分類集,其中N表示分類號。

根據式(2)可以計算出每一個分類的協(xié)方差矩陣S=(S1,S2,…,SN)。其中 SN對應第N個分類。

輸出:每一個分類的協(xié)方差矩陣。

(2)分類階段:

輸入:多維向量Y;

a.根據式(3)和訓練階段得到的協(xié)方差矩陣,計算每一個分類和Y的馬氏距離;

b.找到離Y最近的最小距離;

輸出:決定具有最小馬氏距離的分類。

根據這個算法,分類器不需要提前計算參數K,就可以根據分散的訓練樣本集計算出樣本的種類。

2 文本表示

文本表示是文檔分析和處理中的關鍵問題。文本表示也是文本分類、信息過濾、信息檢索、知識發(fā)現等領域的基礎。對于中文語料集中的文本,計算機不能夠直接進行處理,因此在進行中文文本分類

之前,必須要對中文語料集中的文本進行一些處理。采取合理的方式將中文文本轉化成計算機能夠處理的形式,這個過程就是文本表示。因此,作為文本分類的一個預處理步驟,文檔可以用特征向量來表示。Combarro在2005年指出,特征加權方法 TF-IDF方法在絕大多數情況下都是最有效最簡單的文本特征化的方法。

TFI-DF方法是通過特征詞的詞頻(TF)和反文檔頻率(IDF)來計算特征詞的權重。特征詞頻率TF(t,d)表示特征詞t在文檔d中出現的頻率(出現的次數)。文檔頻率DF(t)是在所有文本中特征詞t出現的頻率,反文檔頻率IDF(t)可以通過如下的公式計算:

式中:D——文檔的個數;

IDF(t)——特征詞 t在整個文檔中的離散度。

在文檔的d中特征詞t的權重可以通過如下的式(5)計算:

在上述公式中,W(t,d)的值越大,表示特征詞t在文檔d中出現的頻率越高。

3 文本分類的處理步驟

文本分類的處理步驟可以如圖2所示:

圖2 獲得分類模型的過程

首先,從訓練樣本集中去除所有的停詞,利用TF-IDF方法的式(4)和式(5)構建權重表;然后,將所有文檔向量化;訓練分類器并獲得分類模型。用該模型可以表示文本向量的分類。

4 實驗和結論

本研究選取Internet網上的熱點新聞作為分類目標,其基本分類類別包括:IT、健康、運動、教育和軍事。本次實驗共獲取1 000個文本樣本,其中的500個樣本作為訓練集,剩余的500個作為測試集。為更好地驗證分類算法和樣本數量之間的關系,將500個訓練樣本集進一步細分為100,150,200,250,300,350,400,450,500,樣本數量是隨機的。我們將MDKNN算法與傳統(tǒng)KNN分類器(N=5 to 20,并且選擇最佳的N作為分類精度)及其Na?ve Bayes分類器進行比較。3種分類算法的分類精度比較如下圖3所示:

從圖3中可以看出,在文本數量較多的情況下,MDKNN分類器獲得了比 KNN分類器和Na?ve Bayes分類器更高的分類景區(qū)。在樣本數 350到500之間,MDKNN分類器達到了分類精度的90%,遠高于其他兩類分類器。Na?ve Bayes分類器隨著樣本數的持續(xù)增加呈現了不穩(wěn)定性;KNN分類器必須選擇最佳的 N進行測試和改錯。由此可見,MDKNN分類器在文本分類中具有較好的穩(wěn)定性和較高的分類精度。

圖3 3種分類算法的分類精度比較

[1]Ronen Feldman,James Sanger.THE TEXT M INING HANDBOOK:Advanced Approaches in Analyzing Unstructured Data[M].CAMBRIDGE:CAMBRIDGE UN IVERSITY PRESS,2007:401-402.

[2]LiW ei,Lee Bob,K rausz,etc.Text Classification by a Neural Netw ork[A].Dale P.Proceedings of the 1991 Summer Computer Simulation Con ference[C].Tw enty-Third Annual Summer Computer Simulation Conference,1991:313-318.

[3]Joachim s,Thorsten.Tex t Categorization with Support Vector M achines:Learning w ith Many Relevant Features[A].Claire N,Celine R.Machine Learning:ECM L-98.10th European Conference on Machine Learning[C].California:Springer,1998:137.

[4]Svingen,B.Using genetic programm ing for document classification[A].Diane JC.FLAIRS-98.Proceedings o f the Eleventh International Florida A rtificial Intelligence Research[C].Florida:AAA IPress,1998:63-67.[5]Hyotyniemi,H.Text document classification with self-organizingmaps[A].JarmoA,Timo H,Matti J.STeP＇96-Genes,Nets and Symbols.Finnish A rtificial Intelligence Con ference[C].Vaasa:Finnish A rtificial Inteel-igence society,1996:64-72.

[6]N igam K,Maccallum,A K,etc.Text Classification from Labeled and Unlabeled Documents using EM[A].To appear in the Machine Learning Journal[C].Boston:K luwer A cadem ic Publishers,1999:1-34.

[7]M ahalanobis,PC.On the generalised distance in statistics[J].Proceedings of the National Institute of Sciences of India,1936,12(1):49-55.