一種減少數(shù)據(jù)特征值鴻溝的方法

◆林游龍

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

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

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

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

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

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

1 向量空間模型

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

（1）標引項（term）的選擇

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

（3）空間中文檔之間距離的計算。

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

2 虛點原理

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

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

圖1 虛點原理示意圖

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

（1）歸一化條件。

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

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

圖2 原SVM 分類方法與使用了虛點方法的SVM 分類方法

2.2 虛點方法介紹

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

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

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

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

2.3 虛點方法的例子

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

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

2.4 虛點方法的另一種解讀

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

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

（1）歸一化條件。

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

2.5 虛點方法的求解

輸入變量定義：假設(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個特征權(quán)重為：

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

3 SVM 與使用虛點原理的SVM

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

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

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

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

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

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

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

4 實驗

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

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

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

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

5 結(jié)束語

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

本文的主要貢獻是：

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

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

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