◆林游龍

（福州數(shù)據(jù)技術(shù)研究院有限公司 福建 350019）

隨著信息時(shí)代的高速發(fā)展，如何對自然語言文本進(jìn)行挖掘，特別是對其按照設(shè)定的語義進(jìn)行正確的歸類，已經(jīng)成為組織大量文本信息的一個(gè)關(guān)鍵問題，這就是文本挖掘中很重要的一類任務(wù)一文本分類[1]。自動(dòng)文本分類（Automatic Text Categorization）或者簡稱為文本分類，是指計(jì)算機(jī)將一篇文章歸于預(yù)先給定的某一類或某幾類的過程[2]。隨著文本信息量的快速增長，文本分類已成為信息檢索、知識挖掘和管理等領(lǐng)域的關(guān)鍵技術(shù)[3-4]。文本分類的精確程度取決于特征提取[5]和分類算法[6]。人們提出了很多文本分類方法，例如k-最近鄰分類法，貝葉斯分類，決策樹和神經(jīng)網(wǎng)絡(luò)[7]。最廣泛使用以及效果最好的文本分類方法是支持向量機(jī)與KNN 方法[8-9]。

支持向量機(jī)是由Vapnik 等人提出的一種學(xué)習(xí)技術(shù)，是借助于最優(yōu)化方法解決機(jī)器學(xué)習(xí)問題的新工具。它集成了最大間隔超平面、Mercer 核、凸二次規(guī)劃、稀疏解和松弛變量等多項(xiàng)技術(shù)[10]。由于其具有全局最優(yōu)、結(jié)構(gòu)簡單、推廣能力強(qiáng)等優(yōu)點(diǎn)，近幾年得到了廣泛研究并應(yīng)用于文本分類、模式識別等領(lǐng)域[11]。

k-最近鄰居分類（KNN）方法基于類比學(xué)習(xí)[12]，采用SVM（向量空間模型）[13]表示文檔，是一種非參數(shù)的分類技術(shù)，在基于統(tǒng)計(jì)的模式識別中非常有效，對于未知和非正態(tài)分布可以取得較高的分類準(zhǔn)確率，具有魯棒性、概念清晰等諸多優(yōu)點(diǎn)[14]。

本文在對基于向量空間模型的分類方法（如SVM[15-16]）的研究發(fā)現(xiàn)，基于向量空間模型的分類方法存在不合理之處，即特征值之間的“鴻溝”，這種鴻溝會導(dǎo)致向量空間模型中兩點(diǎn)之間距離的計(jì)算出現(xiàn)偏差，由于目前基于向量空間模型的分類方法都沒有考慮到這種鴻溝，因此分類效果受到了一定的限制。如果要想進(jìn)一步提高分類效果，就必須解決這種偏差。

本文介紹了一種使用虛點(diǎn)的方法，這種方法消除了特征值之間的鴻溝，使得分類的效果得到了提高。該方法是通過重新定義特征權(quán)重，調(diào)整向量空間模型中點(diǎn)的特征值，即相當(dāng)于重新定義向量空間中的點(diǎn)，這樣的點(diǎn)是相對于原來向量空間模型中的點(diǎn)的矯正映射，即就好像是虛擬點(diǎn)一樣，最后問題歸結(jié)為計(jì)算向量空間模型中的點(diǎn)與虛擬點(diǎn)的映射函數(shù)。理論分析表明虛點(diǎn)方法能提高基于向量空間模型的分類方法的效果，在SVM 中運(yùn)用虛點(diǎn)方法的實(shí)驗(yàn)結(jié)果表明，運(yùn)用虛點(diǎn)方法的SVM 的精確度得到了提高，這種結(jié)果驗(yàn)證了本文提出的虛點(diǎn)方法的有效性。

1 向量空間模型

向量空間模型（Vector Space Model，VSM）[8]是康奈爾大學(xué)Salton 等人上世紀(jì)70 年代提出并倡導(dǎo)的，文檔可以轉(zhuǎn)化為標(biāo)引項(xiàng)（term）及其權(quán)重組成的向量表示，都可以看成空間中的點(diǎn)。向量之間通過距離計(jì)算得到向量的相似度。VSM 中有三個(gè)關(guān)鍵問題：

（1）標(biāo)引項(xiàng)（term）的選擇

（2）權(quán)重的計(jì)算，即計(jì)算每篇文檔中每個(gè)Term 的權(quán)重

（3）空間中文檔之間距離的計(jì)算。

Term 可以是能代表文檔內(nèi)容的特征如：字、詞、短語或者某種語義單元（比如：所有同義詞作為1 維）。對于權(quán)重計(jì)算，目前廣泛使用的方法是TF*IDF 方法，其中TF 代表Term 在文檔中出現(xiàn)的次數(shù)。IDF 代表Term 的文檔頻率DF 的倒數(shù)。兩者相乘然后做線性編號就是此方法。計(jì)算完Term 的特征權(quán)重后就可以在向量空間模型中用特征向量表示一個(gè)文檔，即一個(gè)文檔可以表示為一個(gè)向量空間模型中的一點(diǎn)。文檔之間距離的通常有歐式距離、向量夾角余弦、向量夾角正弦和馬氏距離等[9]。

2 虛點(diǎn)原理

2.1 虛點(diǎn)方法產(chǎn)生的背景-特征值鴻溝（GBF）

如圖1 所示，假設(shè)一個(gè)類的構(gòu)成只有2 個(gè)Term，其中Term 權(quán)重用TF*IDF 表示，則每個(gè)類都可以表示為一個(gè)帶權(quán)重的Term 的特征向量，假設(shè)類別1 的分類中心為（1，1）。類別2 的分類中心為（3，2），可知兩者的對角點(diǎn)為（3，1），對角點(diǎn)相對于其他的點(diǎn)來說，特殊之處在于它對類別1 的分類中心的距離只跟Feature1 相關(guān)，而跟類別2 的分類中心的距離只跟Feature2 相關(guān)。那么問題就歸結(jié)為對角點(diǎn)的分類問題，按照原來的向量空間模型，對角點(diǎn)有兩個(gè)（1，2），（3，1）。其中（3，1）跟分類中心1（1，1）的Feature1 的距離為特征Feature1 的差值2.跟分類中心2（3，2）的Feature2 的距離為特征Feature2 的差值1?？梢灾缿?yīng)該將對角點(diǎn)分到類別2（3，2）那一組，但從理論上可知，屬于同一特征的值，可以用量來表示，但是屬于不同特征的值無法用量來表示，因?yàn)閮烧叩呐卸ǖ臉?biāo)準(zhǔn)不一樣。Feature2 的差值為2 的數(shù)不一定大于Feature1 的差值為1 的數(shù)。因此僅僅從此對角點(diǎn)的分類問題應(yīng)該無法判斷到底屬于哪一類。也就是Feature2 的差值為2 的數(shù)應(yīng)該與Feature1 的差值為1 的數(shù)相等。此時(shí)對角點(diǎn)到兩類的距離相等，符合無法判斷類型的情況。因此原向量空間模型沒考慮到這個(gè)問題，這就是特征值的鴻溝問題（GBF）的產(chǎn)生。如圖1 所示鴻溝為θ＝1。

圖1 虛點(diǎn)原理示意圖

為了消除特征值之間的鴻溝?？梢哉J(rèn)為存在原分類點(diǎn)的虛點(diǎn)，這些點(diǎn)是由調(diào)整特征權(quán)重的分配來得到的。它們必須滿足兩個(gè)條件：

（1）歸一化條件。

（2）調(diào)整后的兩個(gè)類別虛點(diǎn)到虛對角點(diǎn)的距離必須相等。

如圖所示，vp1 和vp2 分別對應(yīng)分類點(diǎn)1 和分類點(diǎn)2 的虛點(diǎn)。現(xiàn)在的問題歸結(jié)為本文提出的特征鴻溝理論到底存不存在，用即特征鴻溝的消除能不能帶來分類效果的提高，從如圖2 所示，就是要證明在虛點(diǎn)空間中用vp1 和vp2 分類比原向量空間中分類的效果更好。

圖2 原SVM 分類方法與使用了虛點(diǎn)方法的SVM 分類方法

2.2 虛點(diǎn)方法介紹

變量定義：假設(shè)向量空間模型中的分類點(diǎn)為類別1 的分類中心α和類別2 的分類中心β，必然存在一個(gè)點(diǎn)a，它跟α的距離只跟Feature（1）相關(guān)，即特征距離，假設(shè)其為l（1），跟β的距離只跟Feature（2），設(shè)為l（2）相關(guān)，這個(gè)點(diǎn)稱為α和β的對角點(diǎn)。易知α和β的對角點(diǎn)有兩個(gè)，任選其中的一個(gè)Feature（1）與Feature（2）之間的距離鴻溝d（12）定義為：d（12）=|l（1）-l（2）|。

虛點(diǎn)方法：存在特征權(quán)重λ（1），λ（2）滿足歸一化條件，并且使得分配權(quán)重后的向量空間中的點(diǎn)，即原空間中的α和β在虛點(diǎn)空間中的分別對應(yīng)的點(diǎn)的虛點(diǎn)α’和β’的2 個(gè)特征距離相等，即α’和β’到它們虛點(diǎn)空間中的對角點(diǎn)的離相等：l（1）=l（2）。這樣在虛擬空間中特征之間的距離鴻溝就為零了。

關(guān)于對角點(diǎn)的說明：虛點(diǎn)空間與原空間的對角點(diǎn)不是獨(dú)立存在的，他是針對分類點(diǎn)，以及虛點(diǎn)空間中分類點(diǎn)的虛點(diǎn)而提出的一個(gè)抽象的概念，它在現(xiàn)實(shí)中可能不存在。

到目前為止就只有一個(gè)問題了，即特征值鴻溝的觀點(diǎn)是否存在？

2.3 虛點(diǎn)方法的例子

為了形象說明整個(gè)流程，舉個(gè)例子：比如判斷一列火車屬于快車與慢車的標(biāo)準(zhǔn)為：快車為，平均車廂的數(shù)量為10 節(jié)，速度平均為180公里/小時(shí)；而慢車的為：平均車廂30 節(jié)，速度平均為80 公里/小時(shí)。如果此時(shí)，有一列特殊的列車，車廂為10 節(jié)，速度為80 公里/小時(shí)。那么根據(jù)向量空間模型的公式，可以算出這種列車對快車的差異為速度相差100 公里/小時(shí)，車廂沒差異。對慢車的差異為車廂相差20 節(jié)，速度沒差異，進(jìn)行標(biāo)準(zhǔn)化以后（假設(shè)速度的標(biāo)準(zhǔn)化為原值除以180，車廂的標(biāo)準(zhǔn)化為原值除以30），差異分別為100/180，20/30。從而知道此列車屬于快車。但是理論上可知此列出應(yīng)該不能判斷歸屬，因?yàn)?0 節(jié)車廂跟100 公里/小時(shí)這兩個(gè)數(shù)無法比較。此時(shí)鴻溝為差異值的差值即|100/180-20/30|=0.11。而這列車可能現(xiàn)實(shí)中不存在，它只是針對快車和慢車而提出的一個(gè)概念。

因此本文設(shè)特征權(quán)重λ（1），λ（2）來分別調(diào)整火車車廂跟火車速度的權(quán)重，設(shè)歸一化條件λ（1）×λ（2）＝1。此時(shí)λ（1）×（20/30）=λ（2）×（100/180）?？梢缘贸靓耍?）≈0.9129，λ（2）≈1.0954。此時(shí)虛擬分類點(diǎn)為快車平均節(jié)數(shù)為：9.129 節(jié)，速度為197.172 公里/小時(shí)：慢車平均節(jié)數(shù)為。27.387 節(jié)，速度為：87.632 公里/小時(shí)。此時(shí)就能用虛擬點(diǎn)分類了。可以計(jì)算特殊列車在虛點(diǎn)空間中的映射點(diǎn)為9.129 節(jié)與 87.632 公里/小時(shí)，從而計(jì)算得到鴻溝為0，此值小于＜0.11。說明使用快車，與慢車的虛點(diǎn)用來分類比使用原點(diǎn)分類來得更接近實(shí)際。

2.4 虛點(diǎn)方法的另一種解讀

假設(shè)原空間中存在分類點(diǎn)α（0，0）點(diǎn)和β（a，b）點(diǎn)。根據(jù)虛點(diǎn)方法可知，它們在虛點(diǎn)空間中分別對應(yīng)虛點(diǎn)α’（0，0）和β’（aλ1，bλ2），其中，λ1λ2=1 設(shè)α’和β’的距離為c，則根據(jù)直角三角形公式以及直角三角形不等式可知：

其中當(dāng)aλ1=bλ2，時(shí)c有最小值。而aλ1=bλ2是虛點(diǎn)空間中的虛點(diǎn)滿足的條件。因此虛點(diǎn)方法就轉(zhuǎn)化為求虛點(diǎn)空間中虛點(diǎn)之間最小距離。即2.1 節(jié)提出的虛點(diǎn)滿足的兩個(gè)條件變?yōu)椋?/p>

（1）歸一化條件。

（2）調(diào)整后的兩個(gè)類別之間的距離最小。

2.5 虛點(diǎn)方法的求解

輸入變量定義：假設(shè)向量空間模型由n維特征向量構(gòu)成，類別1的分類中心為α（a1，a2，...an），類別2 的分類中心為β（b1，b2，...bn）。

輸出變量：特征權(quán)重λ1，λ2，λn。

求解原理：

限制條件為：

根據(jù)以上可知，這是最優(yōu)化問題，因此本文使用拉格朗日乘數(shù)來解決此問題。得到如下函數(shù)：

其中λ為拉格朗日乘數(shù)。為了求λ1，λ2，…λn。將函數(shù)分別對λ1，λ2，…λn求偏微分得：

即式子

解得：

因此第i個(gè)特征權(quán)重為：

從以上式子可以看出，iλ跟α’和β’的第i個(gè)特征的差值成反比。此結(jié)果證實(shí)了給人的感覺，即為了縮小特征鴻溝，特征值差異越大的，應(yīng)該將它們分配的權(quán)重越低。

3 SVM 與使用虛點(diǎn)原理的SVM

支持向量機(jī)方法是建立在統(tǒng)計(jì)學(xué)習(xí)理論的VC 維理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小原理基礎(chǔ)上的[17]，根據(jù)有限的樣本信息在模型的復(fù)雜性（即對特定訓(xùn)練樣本的學(xué)習(xí)精度，Accuracy）和學(xué)習(xí)能力（即無錯(cuò)誤地識別任意樣本的能力）之間尋求最佳折中，以期獲得最好的推廣能力（Generalizatin Ability）。支持向量機(jī)方法的幾個(gè)主要優(yōu)點(diǎn)是：1、可以解決小樣本情況下的機(jī)器學(xué)習(xí)問題；2、可以提高泛化性能；3、可以解決高維問題；4、可以解決非線性問題；5、可以避免神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)選擇和局部極小點(diǎn)問題[18]。

根據(jù)虛點(diǎn)方法可知，在SVM 中使用虛點(diǎn)方法的步驟如下：

（1）在訓(xùn)練集中，根據(jù)虛點(diǎn)算法調(diào)整特征權(quán)重，映射到虛點(diǎn)空間。其中權(quán)重應(yīng)滿足歸一化條件以及虛點(diǎn)空間中虛點(diǎn)之間的距離最小。

（2）在虛點(diǎn)空間運(yùn)用SVM 方法，即找出最優(yōu)分類超平面，此時(shí)的最優(yōu)超平面是虛點(diǎn)空間的最優(yōu)分類超平面。

（3）用虛點(diǎn)空間的最優(yōu)分類超平面來分類，即使用虛點(diǎn)空間建立的模型。

如圖所示2 對于步驟1，首先分別求訓(xùn)練集中類別1 和類別2 的分類中心，可以用分別求類別1 和類別2 中向量的平均值的方法。然后使用介紹的求解虛點(diǎn)的方法，求出特征權(quán)重。根據(jù)特征權(quán)重重新計(jì)算特征向量，相當(dāng)于將原點(diǎn)映射到虛點(diǎn)空間，此時(shí)產(chǎn)生的新的訓(xùn)練集即虛點(diǎn)空間中的訓(xùn)練集。

對于步驟2，跟運(yùn)用SVM 方法的差別僅僅是訓(xùn)練集的不同，即虛點(diǎn)空間運(yùn)用的是步驟1 產(chǎn)生的訓(xùn)練集。

4 實(shí)驗(yàn)

LIBSVM 是臺灣大學(xué)林智仁（Chih-Jen Lin）博士等開發(fā)設(shè)計(jì)的一個(gè)操作簡單、易于使用、快速有效的通用SVM 軟件包，可以解決分類問題、回歸問題以及分布估計(jì)等問題，提供了線性、多項(xiàng)式、徑向基和S 形函數(shù)四種常用的核函數(shù)供選擇，可以有效地解決多類問題、交叉驗(yàn)證選擇參數(shù)、對不平衡樣本加權(quán)、多類問題的概率估計(jì)等。

本文使用 libsvm 附帶的包含 47，236 個(gè)特征值的數(shù)據(jù)集rcv1.binary，其中數(shù)據(jù)量為20，242，本文將此數(shù)據(jù)集分為10 份做交叉測試即，每份2，024 個(gè)數(shù)據(jù)，最后一份是2，206 個(gè)數(shù)據(jù)。然后依次選取10 份中的一份做測試集，其他9 份合并為一個(gè)訓(xùn)練集。核函數(shù)選取徑向基函數(shù)[19]。因?yàn)槠鋵?yīng)的特征空間是無窮維Hilbert 空間。而Hilbert 空間推廣了高斯空間的概念，這點(diǎn)跟虛點(diǎn)方法（VPM）很相似。數(shù)據(jù)集都是經(jīng)過了歸一化的了。虛點(diǎn)方法參數(shù)λ=2，測試的是分類精度。實(shí)驗(yàn)結(jié)果如表1 所示：

表1 交叉測試結(jié)果

由實(shí)驗(yàn)結(jié)果可知，使用了虛點(diǎn)方法調(diào)整的權(quán)重后分類的精度得到了一定的提高，這種結(jié)果驗(yàn)證了本文提出的虛點(diǎn)方法的有效性。

5 結(jié)束語

本文提出了特征值之間存在鴻溝的問題，并介紹了一種使用虛點(diǎn)的方法，這種方法降低了特征值之間的鴻溝，使得分類的效果得到了進(jìn)一步的提高。該方法是通過重新定義特征權(quán)重，調(diào)整向量空間模型中點(diǎn)的特征值，即相當(dāng)于重新定義向量空間中的點(diǎn)，這樣的點(diǎn)是相對于原來向量空間模型中的點(diǎn)的矯正映射，即就好像是虛擬點(diǎn)一樣，最后問題歸結(jié)為計(jì)算向量空間模型中的點(diǎn)與虛擬點(diǎn)的映射函數(shù)。理論分析和實(shí)驗(yàn)結(jié)果表明運(yùn)用了虛點(diǎn)方法的基于向量空間模型的SVM 的分類方法的精確度都得到了提高，這種結(jié)果驗(yàn)證了虛點(diǎn)方法的合理性。

本文的主要貢獻(xiàn)是：

（1）本文提出了特征值之間存在鴻溝的問題，

（2）介紹了一種使用虛點(diǎn)的方法來降低特征值之間的鴻溝。

本文介紹的虛點(diǎn)方法，證明了分類中存在特征鴻溝的問題，提高分類的效果，本文使用的是用平均值求特征值鴻溝的方法，這種方法具有一定的局限性，因此研究求特征值鴻溝的方法以及使用訓(xùn)練集的啟發(fā)式知識來定義特征值鴻溝與權(quán)重分配將是下一步要做的工作。