一種改進的ＫＮＮ Ｗｅｂ文本分類方法
2008-12-31 00:00:00吳春穎王士同
計算機應用研究 2008年11期
(江南大學 信息工程學院， 江蘇 無錫 214122)
摘要：KNN方法存在兩個不足:a)計算量巨大，它要求計算未知文本與所有訓練樣本間的相似度進而得到k個最近鄰樣本；b)當類別間有較多共性，即訓練樣本間有較多特征交叉現象時，KNN分類的精度將下降。針對這兩個問題，提出了一種改進的KNN方法，該方法先通過Rocchio分類快速得到k0個最有可能的候選類別；然后在k0個類別訓練文檔中抽取部分代表樣本采用KNN算法；最后由一種改進的相似度計算方法決定最終的文本所屬類別。實驗表明，改進的KNN方法在Web文本分類中能夠獲得較好的分類效果。
關鍵詞：Web文本分類； K最近鄰； 快速分類
中圖分類號：TP311文獻標志碼：A
文章編號：1001-3695(2008)11-3275-03
Improved KNN Web text classification method
WU Chun-ying， WANG Shi-tong
(School of Information Engineering， Jiangnan University， Wuxi Jiangsu 214122， China)
Abstract:KNN method not only has large computational demands， because it must compute the similarity between unlabeled text and all training texts; but also may decrease the precision of classification because of the commonness of classes. This paper presented an improved KNN method， which solved two problems mentioned above. It firstly got the most k0 classes fast by Rocchio method， and then used KNN arithmetic in some representative training texts of theclasses， at last assigned class by an improved similar arithmetic in KNN. The result of research indicates that the impact of the new method is better.
Key words：Web text classification; KNN(K-nearest neighbor); fast classification
隨著網絡信息技術的高速發展和高速通信基礎設施的建設，Internet上的Web頁面數量呈指數增長。如何有效地組織和處理這些海量信息，如何更好地搜索、過濾和管理這些網絡資源，Web文本分類成了關鍵技術。目前關于這方面的研究已經取了很大的進步，并取得了一系列的分類方法，其中比較著名的文本分類方法有Rocchio、支持向量機（SVM）、K最近鄰（KNN）、神經網絡和貝葉斯（Bayes）算法等[1]。在這些方法中，KNN是一種簡單、有效、非參數的方法，目前應用比較廣泛。
為了使KNN方法更實用，不少學者對KNN方法進行了進一步研究，王煜等人[2]提出了一種快速KNN算法，通過建立索引表來快速找到k個最近鄰，但沒有提高分類精度；李楊等人[3]提出了排類和歸類算法在不影響原有精度下提高分類速度；李榮陸等人[4]針對不均勻訓練樣本，提出了基于密度的裁剪方法，取得了較好的分類效果。本文提出一種改進KNN文本分類方法，目的是為了減少樣本間相似度的計算量，克服KNN分類搜索空間巨大的問題，同時又能一定程度地改善分類效果。
1傳統的KNN文本分類方法
11文本表示方法
向量空間模型（vector space model，VSM）[5]是由Salton于1968 年提出的，是近年來文本表示應用較多且效果較好的方法之一。該模型涉及到以下三個基本概念：
a)文檔(document)。泛指一般的文本或文本中的片斷，一般指一篇文章。
b)項(term)。文本中的內容特征常用切分后的詞來表示，稱為文本的項，即文本可用項集(term list)，表示為D(t1，t2，…，tn)。其中：tk是項。
c)項的權重(term weight)。對于含有N項的文本，不同的項tk，其區分文本的能力不同，故tk常被賦予不同的權重wk(d)，表示它們在文本中的重要程度。常用的有布爾函數、平方根函數、對數函數、TF-IDF 函數[6]等。其中TF-IDF 在文本檢索和機器學習中被頻繁使用。目前存在多種TF-IDF公式，比較普遍的TF-IDF公式如下：
W(t，d)=[tf(t，d)×log(N/nt+0.01)]/{∑∈d[tf(t，d)×log (N/nt+0.01)]2}(1)
其中：w(t，d)為詞t在文本d中的權重；tf(t，d)為詞t在文本d中出現的詞頻（絕對詞頻即使用詞在文本d中出現的頻次；相對詞頻即為歸一化的詞頻)；N為訓練文本的總數；nt為訓練文本集中出現詞t的文本數，分母為歸一化因子。這樣，Web文本d可表示為向量空間模型為
V(d)=(t1，w1(d);t2，w2(d)；…；tn，wn(d))(2)
12KNN分類算法
KNN算法是一種簡單、有效、非參數的文本分類方法；其本質是一種預測性的監督分類算法，不需要額外的數據來描述規則，它的規則本身就是數據樣本；它并不要求數據的一致性，即可以存在噪聲；KNN根據待分類樣本的k個最近鄰樣本來預測未知樣本的類別。因此，KNN算法必須明確兩個基本因素：最近鄰樣本的數目k和測量相似性的距離函數。距離函數是一個非負函數，用來刻畫不同樣本的相似程度。常用的有歐氏距離、曼哈頓距離、余弦夾角等。本文采用余弦夾角公式[7]，如下：
sim(di，dj)=(di·dj)/(｜di｜×｜dj｜)=(∑nk=0wik×wjk)/(∑nk=0wik2×∑nk=0wjk2)(3)
其中：sim(di，dj)表示文本di和文本dj的相似度；wik表示文本di中第k個特征的權重。
在分類時，首先將待分類文本D轉換與訓練樣本一致的向量空間模型；然后計算D與每個樣本的相似度，計算見式（3）；再取相似度最大的K個樣本，根據K個樣本計算屬于每個類別的權重，計算見式（4）[2] ；最后文本D屬于權重最大的那個類別。
p(D，Cj)=∑ki=0sim (di，D)Pd(di，Cj)
(4)
其中:sim(di，D)表示文本D的K個最近文本di與文本D間的相似度。
Pd(di，Cj)=1di屬于類別Cj樣本0di不屬于類別Cj樣本
（5）
2改進的KNN分類算法
在傳統的KNN分類中，要求計算待測文本與所有訓練樣本間的相似度，時間上難以滿足實際分類需求。因此本文提出了一種改進的KNN分類算法。它的主要思想是：先通過Rocchio分類快速得到k0個最有可能的候選類別；然后在k0個類中心區域采用KNN算法；最后結合Rocchio分類結果，由一種改進的相似度計算方法決定最終的文本所屬類別。
21Rocchio方法的使用
Rocchio算法[8]是用于文檔分類的經典向量空間模型，它的基本思想是使用訓練集為每個類構造一個原型向量。構造方法如下：給定一個類，訓練集中所有屬于這個類的文檔對應向量的分量用正數表示，所有不屬于這個類的文檔對應向量的分量用負數表示，把所有的向量加起來，得到的和向量就是這個類的原型向量；定義兩個向量的相似度公式，逐一計算訓練集中所有文檔和原型向量的相似度，從中挑選某個相似度作為邊界。給定一篇未知文檔，如果這篇文檔與原型向量的相似度比邊界大，則這篇文檔屬于這個類；否則這篇文檔就不屬于該類。該方法的突出優點是容易實現，計算（訓練和分類）特別簡單，但在實際分類系統中很少采用這種方法解決具體的分類問題。
本文采用Rocchio方法作為第一階段處理，先將每個類別的所有訓練文檔表示成向量空間模型，然后對該類所有向量進行相加求和再取平均，得到該類的中心向量；同時計算并保存兩個變量：a)訓練文本與該類中心的最小相似度，公式同式（3），該最小相似度作為衡量一個未知文本是否屬于該類的閾值，記為θc；b)求出該類所有訓練文本與該類中心的平均相似度，記為C，作為后面KNN分類選取代表樣本的參考依據。
在分類時，先利用Rocchio分類器計算待分類文本X與每個類別中心向量之間的相似度SCj=sim(X，Cj)，公式同式（3）；如果sim(X，Cj)≥θCj，則把Cj作為下階段處理的候選類別，否則放棄Cj，即后續不再對該類別進行處理。這樣待分類文本X就只能屬于k0(k0≤m，m為所有類別數）個候選類別中一種。這樣處理的目的就是快速排除那些明顯不是文本X的所屬類別的訓練樣本。Rocchio分類過程如圖1所示。其中：X為待測樣本；C1、C2、C3為類別1、2、3的中心向量。從圖1中可以直觀地看出文本X不屬于第三類，因為它到C3的距離要大于類3中所有訓練樣本到C3的距離，所以直接排除第三類別。這樣文本X要么屬于第一類，要么屬于第二類，接下來就在k0個類別中選擇，由下個階段專門處理。
22改進的KNN算法
經過Rocchio的第一階段處理，已經排除了m-k0個類別；接下來就用一種改進的KNN算法來完成k0個類別中的最后文本所屬類別。改進點主要針對兩點：a)在k0個類中，其訓練文本依然很大，要選取其中部分有代表性的樣本；b)在傳統的KNN分類中，文本大多數在類別的邊界處被誤分，因此改進方法要盡量避免這種情況。
定義1類中心區域。當一個樣本di與該類中心Cj的距離dis(di，Cj)=sim(di，Cj)，如果dis(di，Cj)≤ε(ε=λ×C)（其中：C為該類的所有訓練樣本到該類中心的平均距離，λ(0，1]），則稱di為類別中心區域的一個樣本，所有的di稱為該類的中心區域。其二維平面如圖2所示。
在圖2中，k0=2，三個圓圈表示三個類中心區域，兩個橢圓為類別間的邊界區域。從圖中可以看出，如果采用傳統KNN算法，則待分文本X的k個最近鄰樣本必然在第一個橢圓區域，而該區域的所屬類別是最模糊的，也是文本最容易被誤分的；采用改進的KNN方法則避免了該情況，讓文本X與最能代表類別的中心區域樣本進行比較，從而得出的k個最近鄰樣本也必然是類中心區域中的樣本，這樣提高了分類精度。
定義2類間影響因子。在KNN分類中，一個待測文本X，類別Cj，SCj=sim(X，Cj)，則稱SCj是類別間影響因子，它表示該文本X屬于該類Cj的隸屬度。
這樣，改進后的KNN方法具體步驟如下：
a)根據第1.1節將所有訓練文本表示為向量空間模型，并將待分類文本X轉換為與訓練文檔一致的向量空間模型。
b)采用基于Rocchio的多值分類器進行分類，計算文本X與所有類別之間的相似度，并根據第2.1節處理，快速得到文本X的k0個候選類別；其余的類別將不再考慮。
c)選取訓練集中的代表樣本，即k0個類別的中心區域中的樣本；計算未知類別文本X與代表樣本間的相似度sim(X，di)；然后對相似度值進行排序，取前k個作為文本X的k最近鄰樣本；
d)確定文本X的最后類別；引入類間影響因子SCj，對式（5）進行了改進：
Pd(di，Cj)=SCjdi屬于類別Cj樣本0di不屬于類別Cj樣本
(6)
最后根據k個樣本di，由式（4）（6）計算文本X與每類的權重，把X歸于權重最大的類別。
3實驗結果與分析
3．1實驗概況
常用的特征提取方法有文檔頻率（document frequency，DF）、互信息（mutual information，MI）、信息增益（information gain，IG）和CHI統計[9]。文獻中實驗表明IG和CHI較好。本次實驗采用CHI統計，該方法度量詞條t 和文檔類別c之間的相關程度，并假設t 和c 之間符合具有一階自由度的χ2 分布；詞條對于某類的χ2 統計值越高，它與該類之間的相關性越大，攜帶的類別信息也較多。令N 表示訓練語料中的文檔總數，c為某一特定類別， t表示特定的詞條，A表示屬于c類且包含t 的文檔頻數， B表示不屬于c類但是包含t的文檔頻數， C表示屬于c類但是不包含t 的文檔頻數， D是既不屬于c也不包含t 的文檔頻數。則t 對于c的CHI 值計算公式如下：
χ2(t，c)=N×(AD-BC)2/[(A+C)×(B+D)×
(A+B)×(C+D)](7)
文本分類領域比較常用的評價標準有[9]：
召回率： r=categories found and correct/total categories correct
準確率：p=categories found and correct/total categories found
F1值：F(r，p)=2rp/(r+p)
其中:r表示召回率；p表示準確率；本文采用F1值評價標準。
32實驗結果與分析
本次實驗數據分為兩組，實驗針對兩組不同數據集分別采用傳統KNN和改進后的KNN算法進行測試。第一組來自李榮陸收集的10個類別[10]，它們是大類，即各類間共性較少，而且分布比較均勻。具體情況見表1。實驗結果見表2。
第二組數據來自譚松波收集并發布的文本分類語料[11]，12個大類中教育下的7個小類，它們都是教育的分支，類別間具有很多共性，而且文本數量分布不均勻。具體情況見表3。實驗結果見表4。
從表2和4可以看出：a)不論是大類還是小類，分布是均勻還是不均勻，改進后的KNN方法分類效果都要比傳統的KNN效果好（其F1值平均要高出1.3個百分點）。這是因為在改進方法中通過Rocchio方法排除了m-k0個類別，同時利用類別中心區域減少了邊界樣本點的干擾，進而提高了分類精度；b)在實驗一的大類中，使用KNN方法進行分類效果比較好，不論是傳統的還是改進后的F1都達到了90%以上，改進后只提高了1.3個百分點；在實驗二的小類中，兩種方法的F1都不到80%，這是因為小類間存在很多共性，即它們的訓練樣本間存在嚴重的特征交叉現象，而且樣本分布不均勻，給KNN分類帶來了困難，即使這樣改進后的方法F1提高了6.1個百分點，這說明類別間越是復雜，分布越是不均勻，改進后的方法越有效。由于現實世界中類別往往是種類繁多、關系復雜、分布差別大，這也進一步說明了改進的方法具有現實意義。
此外，在實驗過程中發現，除了分類效果改善，同時分類的速度也有了極大提高。眾所周知，傳統KNN的分類效率與訓練樣本集的規模有直接關系，特別是當訓練樣本規模巨大時，對于Web文本要求實時在線分類時，傳統KNN就無法勝任。改進的KNN先利用Rocchio方法快速排除m-k0個類別，減小樣本搜索空間；其次讓未知文本與各類中心區域中的樣本比較，又一次降低其計算量。在相同實驗環境下，改進的KNN運行時間（0.054 4 s/篇）不到傳統KNN運行時間(0.223 4 s/篇)的1/4。
改進的KNN方法也存在不足:a)為了在第一階段中進行Rocchio分類，必須先計算每個類別的閾值和該類的所有訓練樣本到該類中心的平均距離C，需要更多的前期訓練時間；b)在KNN分類中，為了使得在縮小樣本中分類精度最佳，去除類別的邊界噪聲的標準要由實驗來確定。總體來說，改進后的KNN方法還是有一定優勢的。
4結束語
本文詳細介紹一種改進的KNN算法在Web文本分類中的應用。目前對Web文本分類方法的研究日漸增多，但怎樣在效率和效果兩方面同時改進，特別是當類別繁多、分布不均勻、文本數量巨大的情況下達到實用程度等問題還有待于進一步研究。這些問題也是筆者今后努力和研究的方向。
參考文獻：
［1］高潔，吉根林.文本分類技術研究[J].計算機應用研究，2004，21(9):28-34.
[2]王煜，白石，王正歐.用于Web文本分類的快速KNN算法[J].情報學報，2007，26(1):60-64.
[3]李楊，曾海泉，劉慶華，等. 基于KNN的快速Web文檔分類[J].小型微型計算機系統，2004， 25(4):725-729.
[4]李榮陸，胡運發.基于密度的KNN文本分類器訓練樣本裁剪方法[J].計算機研究與發展，2004，41(4):539-544.
[5]龐劍鋒，卜東波，白碩.基于向量空間模型的文本自動分類系統的研究與實現[J].計算機應用研究，2000，17(9):23-26.
[6]貝雨馨，崔榮一.文本分類中特征項權重的計算方法[J].延邊大學學報:自然科學版，2004，30(3):202-204.
[7]宋玲，馬軍，連莉，等.文檔相似度綜合計算研究[J].計算機工程與應用，2006，42(30):160-163.
[8]LEWIS D D， CALLAN J P. Training algorithms for linear text classifiers[C]//Proc of the 19th Annual International Conference on ACM2-SIGIR. Konstanz: Hartung-Gorre Verlag，1996.
[9]YANG Y. A comparative study on feature selection in text categorization[C]//Proc of the 14th International Conference on Machine Learning. 1997.
[10]李榮陸.中文文本分類語料[EB/OL].[2008-01-20].http://www.nlp.org.cn/docs/doclist.php.
[11]譚松波，王月粉.中文文本分類語料庫-TanCorp v1.0[EB/OL].(2007-08-29) [2008-01-20].http://www.searchforum.org.cn/tansongbo/corpus.htm.
