史淼　劉鋒

摘要：隨著文本數(shù)據(jù)的激增，文本分類的高復(fù)雜度是一個(gè)重要的問題。k近鄰（kNN）算法是一個(gè)簡(jiǎn)單、有效，但是計(jì)算復(fù)雜度很高的分類算法。一般，在使用kNN算法時(shí)，使用主成分分析（PCA）進(jìn)行預(yù)處理來減少維數(shù)，但是該算法要求投影空間中的所有向量來執(zhí)行kNN算法。我們提出一個(gè)新的混合算法PCA&kNN，使用一個(gè)小的鄰居集來執(zhí)行kNN算法，而不是投影空間中的完整的數(shù)據(jù)向量，從而減少了計(jì)算的復(fù)雜性。 新的文本被投影到較低維的空間，kNN僅使用每個(gè)軸的鄰居執(zhí)行，基于更接近原始空間和投影空間且沿著投影成分的主向量。為了驗(yàn)證該方法的有效性，針對(duì)Reuters標(biāo)準(zhǔn)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果顯示，新提出的模型顯著優(yōu)于kNN和標(biāo)準(zhǔn)PCA-kNN混合算法，同時(shí)保持了相似的分類精確度。

關(guān)鍵詞：文本分類；降維；PCA；kNN；混合分類器；加權(quán)

中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2015）10-0169-03

隨著網(wǎng)絡(luò)信息技術(shù)的快速發(fā)展和高速通信基礎(chǔ)設(shè)施的建設(shè)，各種電子文檔的數(shù)量不斷增加，使得人們查找信息越來越難，為了收集有用的信息，需要對(duì)文本進(jìn)行正確、有效的分類。因此，分類技術(shù)的發(fā)展越來越受到人們的重視。

文本分類是為每個(gè)文檔找到正確的類，給定一組類和文本文檔集合的過程，也稱為監(jiān)督學(xué)習(xí)，它融合了數(shù)據(jù)挖掘、信息檢索、統(tǒng)計(jì)學(xué)、神經(jīng)網(wǎng)絡(luò)等學(xué)科的知識(shí)，主要應(yīng)用于描述性問答系統(tǒng)、搜索引擎、推薦系統(tǒng)等。目前，常用的文本分類算法[1]有：支持向量機(jī)（SVM）、k近鄰（kNN）、貝葉斯算法（Bayes）、遺傳算法等。其中kNN算法是一種簡(jiǎn)單、有效、非參數(shù)的方法，因而得到了廣泛的應(yīng)用。但它有一個(gè)明顯的缺點(diǎn)：文本的特征向量空間具有很高的維數(shù)。因此，它的計(jì)算成本很高。

現(xiàn)階段，已有將主成分分析（PCA）用作kNN算法的預(yù)處理階段，以減少維數(shù)。然而，kNN算法的計(jì)算成本盡管減少了，但仍然高，這是因?yàn)?，此方法使用了投影空間中每一個(gè)向量[2]。

本文提出了一個(gè)新的混合文本分類方法，利用PCA來減少維數(shù)，同時(shí)僅對(duì)主成分中鄰近的向量應(yīng)用kNN算法，從而降低了kNN分類器的輸入。我們證明了該混合模型能夠以高精度水平分類數(shù)據(jù)，同時(shí)使用更小的主成分?jǐn)?shù)從而顯著減少了計(jì)算時(shí)間。

1 理論背景

1.1 文本表示

文本文檔存儲(chǔ)的是非結(jié)構(gòu)化的信息，所以文本分類需要將文本表示成計(jì)算機(jī)能夠處理的形式。常見的文本表示方法有布爾邏輯型、概率型和向量空間模型（SVM）[3]等。本文采用的是向量空間模型（SVM）來描述文本集。

在向量空間模型，文件被表示為向量，其中，文檔中的每個(gè)條目對(duì)應(yīng)于術(shù)語的權(quán)重。文本分類的一個(gè)普及的無監(jiān)督的加權(quán)方式是TF* IDF（檢索詞頻率*倒排文檔頻率）[4，5]。還有其他的有效監(jiān)督加權(quán)方式，例如TF*RF（檢索詞頻率*相關(guān)性頻率），TF-ICF（檢索詞頻率*逆語料庫(kù)頻率）[6]等。有效的文本分類取決于加權(quán)方式和分類算法兩者的正確選擇。

1.2 主成分分析

主成分分析（PCA）是1933年由Hotelling首先提出的，它是通過對(duì)原始變量的相關(guān)矩陣或協(xié)方差矩陣內(nèi)部結(jié)構(gòu)的研究，將多個(gè)變量轉(zhuǎn)換成少數(shù)幾個(gè)綜合變量，即主成分，從而達(dá)到降維[7]的目的的一種常用的降維方法[8，9]。所謂數(shù)據(jù)降維是指通過線性或非線性映射將樣本從高維空間映射到低維空間，從而獲得高維數(shù)據(jù)的一個(gè)有意義的低維表示的過程。主成分的數(shù)量小于或等于原變量的數(shù)量，被用于降低高維數(shù)據(jù)的維數(shù)。

主成分分析的主要思想[10]：是設(shè)法將原來類別特征重新組合成一組新的互相無關(guān)的幾個(gè)綜合類別特征來代替原來類別特征，同時(shí)根據(jù)實(shí)際需要從中可取出幾個(gè)較少的綜合類別特征盡可能多的反應(yīng)原來類別特征的信息。這種將多個(gè)類別特征化為少數(shù)互相無關(guān)的綜合類別特征的統(tǒng)計(jì)方法叫做主成分分析。它也是常見的處理降維的一種方法。

主成分分析[11]的降維步驟如下：

1.3 kNN文本分類算法

kNN是一種分類算法[12，13]，它的基本思想[14]是：根據(jù)向量空間模型，把文本內(nèi)容轉(zhuǎn)化為特征空間中的加權(quán)特征向量。計(jì)算待測(cè)試文本與訓(xùn)練集中每個(gè)樣本的相似度，找出測(cè)試文件的k個(gè)最近的鄰居，并按k個(gè)鄰居的類別分開統(tǒng)計(jì)，把測(cè)試文本劃分到最相近的一類中去。

這種方法表現(xiàn)良好，即使在處理多分類文檔的分類任務(wù)時(shí)也是一樣，但是在使用大量測(cè)試樣例或高維數(shù)據(jù)分類對(duì)象時(shí)，就會(huì)需要很長(zhǎng)的時(shí)間。為了分類新到達(dá)的數(shù)據(jù)，我們需要遍歷所有的測(cè)試樣例來找到它的近鄰。存儲(chǔ)所有的測(cè)試樣例就會(huì)引起更多的存儲(chǔ)需求。

我們的目標(biāo)是利用k近鄰算法的優(yōu)勢(shì)，并降低它的計(jì)算復(fù)雜度。曾經(jīng)提出過這樣一種模式，在執(zhí)行kNN算法前執(zhí)行一些預(yù)處理，像PCA。通過將每個(gè)類別投影到一個(gè)主成分上。在這種情況下，一個(gè)新的向量必須被投影到多個(gè)主成分上，每個(gè)類別都有一個(gè)這樣的新向量，從而增加了計(jì)算時(shí)間。他們分別計(jì)算每個(gè)類別的主成分，然后使用來自每個(gè)PCA結(jié)果中的第一個(gè)主成分。

針對(duì)上述情況，我們對(duì)上述模型[15]進(jìn)行了改進(jìn)，只執(zhí)行一次PCA，類別的主成分?jǐn)?shù)的選擇也是獨(dú)立的，并顯示了在維持精確度的同時(shí)，顯著地減少了分類時(shí)間。

2 系統(tǒng)架構(gòu)

當(dāng)用戶給定一個(gè)文本數(shù)據(jù)作為輸入時(shí)，混合分類算法以一個(gè)有效的方式執(zhí)行分類并預(yù)測(cè)給定數(shù)據(jù)的類別。在我們處理高維數(shù)據(jù)時(shí)，PCA被用作預(yù)處理階段。kNN預(yù)測(cè)新數(shù)據(jù)的標(biāo)簽。

算法A是我們執(zhí)行混合文本分類的主要算法。

A. 算法——PCA分類器（）

輸入：{類的訓(xùn)練數(shù)據(jù)集，測(cè)試數(shù)據(jù)}

輸出：{測(cè)試數(shù)據(jù)的類別}

1） 計(jì)算訓(xùn)練數(shù)據(jù)的主成分；

2） 訓(xùn)練數(shù)據(jù)投影到每個(gè)主成分上；

3）測(cè)試數(shù)據(jù)投影到每個(gè)主成分上；

4）對(duì)每個(gè)投影空間執(zhí)行二進(jìn)制搜索，找出最近鄰L；

5）計(jì)算測(cè)試數(shù)據(jù)和它在投影空間中的近鄰之間的相似度；

6）選出最相似的近鄰k；

7）基于已選出的近鄰預(yù)測(cè)測(cè)試數(shù)據(jù)的類別。

該算法的輸入是類的訓(xùn)練數(shù)據(jù)和測(cè)試數(shù)據(jù)。采用主成分分析（PCA）可以對(duì)高維數(shù)據(jù)降維。在投影空間中維數(shù)降低的數(shù)據(jù)被用于分類。通過在維度減少的特征空間中沿著每個(gè)主成分找到最近鄰L，從而限制了kNN空間。在原始空間中聚集的數(shù)據(jù)在投影空間中也會(huì)更近，且沿著每個(gè)主成分軸。沿著主成分會(huì)有附加的近鄰，但是它們不是新數(shù)據(jù)的近鄰，kNN算法會(huì)丟棄它們。

圖1描繪了混合算法的訓(xùn)練階段。輸入集包含訓(xùn)練數(shù)據(jù)連同它的類信息和測(cè)試數(shù)據(jù)。PCA在這里用來減少的訓(xùn)練數(shù)據(jù)集的特征數(shù)量。

沿著各主成分和與其對(duì)應(yīng)的索引的投影的值被存儲(chǔ)在一個(gè)二維數(shù)組中。索引稍后用于檢索原始數(shù)據(jù)和投影數(shù)據(jù)，并沿著軸查找近鄰。隨著數(shù)組被分類，二進(jìn)制搜索找到一個(gè)復(fù)雜度為O （log n）的最近鄰，其中n是數(shù)組的大小。

我們的模型不僅使用PCA減少了向量的維度，而且減少了搜索空間，通過限制沿著軸線的鄰居對(duì)應(yīng)的數(shù)據(jù)，同時(shí)使用二進(jìn)制搜索減少了發(fā)現(xiàn)鄰居的時(shí)間。

圖2顯示了我們提出模型的測(cè)試階段。當(dāng)新數(shù)據(jù)到達(dá)時(shí)，我們沿著主成分投影新到達(dá)的數(shù)據(jù)。傳統(tǒng)的kNN計(jì)算整個(gè)訓(xùn)練集的相似度。為了減少kNN分類的時(shí)間，我們提出了沿著各成分投影向量，并沿著主成分選擇L最近鄰居。這些鄰居是kNN的輸入數(shù)據(jù)集。而不是搜索整個(gè)訓(xùn)練數(shù)據(jù)和原始特征空間，因此搜索空間減小了。

一旦我們發(fā)現(xiàn)沿主成分最近的鄰居集，kNN就會(huì)用這個(gè)有限的向量集執(zhí)行，同時(shí)選出k個(gè)最近鄰?；谒x子集中最相似的k個(gè)近鄰預(yù)測(cè)新到達(dá)數(shù)據(jù)的類別。

我們可以基于原始向量或基于投影向量執(zhí)行kNN。kNN在原始空間代價(jià)稍大，因?yàn)橄蛄扛?，但是它有更高的精確度。

3實(shí)驗(yàn)評(píng)估

1） 數(shù)據(jù)集

我們使用綜合的且真實(shí)的數(shù)據(jù)集，Reuters 數(shù)據(jù)集，一共有6532個(gè)文檔，5741個(gè)特征集，這些特征集屬于52個(gè)類別。

2） 通過在綜合數(shù)據(jù)集上改變樣例數(shù)來進(jìn)行分析

我們通過改變樣例的數(shù)量，同時(shí)保持特征的數(shù)量為1000個(gè)，L為7，K為5，來測(cè)試混合分類器的執(zhí)行時(shí)間。

接下來，我們比較了分類精確度，通過改變k值，分別使用投影數(shù)據(jù)和原始數(shù)據(jù)來執(zhí)行我們的混合分類器的最后一步，如表1所示。正如預(yù)期的那樣，使用原始數(shù)據(jù)比使用投影數(shù)據(jù)計(jì)算的相似度相對(duì)較高。對(duì)于投影數(shù)據(jù)和原始數(shù)據(jù)，k值越小分類精確度越高。

使用Reuters 數(shù)據(jù)，對(duì)傳統(tǒng)的kNN算法，PCA預(yù)處理的kNN算法和我們提出的混合kNN算法所需時(shí)間的比較，如表1所示。我們的混合分類器表現(xiàn)要優(yōu)于PCA+kNN方法。在用PCA預(yù)處理的kNN方法中，PCA僅用于降維。

圖3顯示了通過改變L值，在原始和投影數(shù)據(jù)的子集上執(zhí)行kNN算法的時(shí)間的比較。投影數(shù)據(jù)花費(fèi)的時(shí)間少于原始數(shù)據(jù)。隨著L的增加，kNN搜索的子空間增加，我們看到時(shí)間也增加了。因?yàn)樵伎臻g的維度較大，kNN在原始數(shù)據(jù)上執(zhí)行的時(shí)間以一個(gè)很快的速度增長(zhǎng)。

使用 PCA+kNN和我們提出的混合算法進(jìn)行分類，分類的精確度和所需時(shí)間如表4所示。在 PCA+kNN方法中，PCA僅僅只用于預(yù)處理步驟進(jìn)行降維，然后在投影空間中執(zhí)行傳統(tǒng)的kNN算法進(jìn)行分類。我們將使用Reuters 數(shù)據(jù)集的一個(gè)子集與測(cè)試數(shù)據(jù)集大小為100，訓(xùn)練數(shù)據(jù)集大小為6532的情況進(jìn)行比較。我們的結(jié)果顯示我們的混合算法在時(shí)間上有顯著減少，在分類精確度上也有一些提升。

4 結(jié)束語

kNN分類器是一個(gè)很常用的高效的分類器。kNN的一個(gè)主要局限性是，當(dāng)處理高維和大數(shù)據(jù)時(shí)它的分類時(shí)間問題。在這篇論文中，我們提出了一個(gè)有效的混合算法，它是基于PCA降維，和以一個(gè)新穎的方式沿著各主成分找到近鄰，以便限制kNN空間并增加有效性。我們?cè)诜诸悤r(shí)，使用了原始數(shù)據(jù)的投影空間，并表明，在使用標(biāo)準(zhǔn)的Reuters 數(shù)據(jù)集的情況下，我們的混合模型能夠以很高的精確度分類數(shù)據(jù)，對(duì)kNN使用小量的主成分和更小的投影數(shù)據(jù)集。從而顯著減少了計(jì)算時(shí)間。未來的工作將包括，對(duì)各種屬于加權(quán)方案和傳統(tǒng)數(shù)據(jù)集的數(shù)據(jù)分析，來了解我們混合算法的有效性。

參考文獻(xiàn)：

[1] Han Jiawei， Kamber M， Pei Jian.數(shù)據(jù)挖掘概念與技術(shù)[M]. 范明， 孟小峰， 譯. 北京： 機(jī)械工業(yè)出版社， 2012.

[2] 郭新辰， 李成龍， 樊秀玲. 基于主成分分析和KNN混合方法的文本分類研究[J]. 東北電力大學(xué)學(xué)報(bào)， 2013， 33（6）： 60-63.

[3] Christoper D M， Prabhakar R， Hinrich S.信息檢索導(dǎo)論[M]. 王斌， 譯. 北京： 人民郵電出版社， 2012.

[4] Chrles Elkan. Deriving TF-IDF as a Fisher Kernel[J]. String Processing and Information Retrieval， 2005， 3772： 295-300.

[5] Lan Man， Tan Chew Lim， Su Jian， et al. Supervised and Traditional Term Weighting Methods for Automatic Text Categorization[J]. IEEE transactions on pattern analysis and machine intelligence， 2009， 31（4）： 721-735.

[6] Reed J W， Jiao Yu. TF-ICF： A new term weighting scheme for clustering dynamic data streams[C]. 2006： 258-263.

[7] 胡煜. 基于K-緊鄰法的兩種降維方法應(yīng)用研究[J]. 廣東技術(shù)師范學(xué)院學(xué)報(bào)， 2008（6）： 35， 36-39.

[8] Jollife I T. Principal Component Analysis[M]. 2nd ed. Springer， 2002.

[9] Smith L I. Atutorial on Principal Components Analysis[R]. 2002.

[11] 張錦， 李光， 曹伍， 等.基于主成分分析的自動(dòng)文本分類模型[J]. 北京郵電大學(xué)學(xué)報(bào)， 2006， 29（22）： 136-138， 143.

[12] Pawar P Y， Gawande S H. A Comparative Study on Different Types of Approaches to Text Categorization[J]. 2012， 2（4）.

[13] Aggarwal C C， Zhai ChengXiang. A Survey of Text Classification Algorithms[M]. Springer， 2012.

[14] 艾英山， 張德賢.基于文本和類別信息的KNN文本分類算法[J]. 計(jì)算機(jī)與數(shù)字工程， 2009， 37（11）： 10-12， 39.

[15] Du Min， Chen Xingshu. Accelerated k-nearest neighbours algorithm based on principal component analys[J]. Journal of Zhejiang University SCIENCE C， 2013， 14（7）： 407-416.