一種減少數據特征值鴻溝的方法

◆林游龍

（福州數據技術研究院有限公司 福建 350019）

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

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

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

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

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

1 向量空間模型

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

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

（2）權重的計算，即計算每篇文檔中每個Term 的權重

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

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

2 虛點原理

2.1 虛點方法產生的背景-特征值鴻溝（GBF）

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

圖1 虛點原理示意圖

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

（1）歸一化條件。

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

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

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

2.2 虛點方法介紹

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

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

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

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

2.3 虛點方法的例子

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

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

2.4 虛點方法的另一種解讀

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

其中當aλ1=bλ2，時c有最小值。而aλ1=bλ2是虛點空間中的虛點滿足的條件。因此虛點方法就轉化為求虛點空間中虛點之間最小距離。即2.1 節提出的虛點滿足的兩個條件變為：

（1）歸一化條件。

（2）調整后的兩個類別之間的距離最小。

2.5 虛點方法的求解

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

輸出變量：特征權重λ1，λ2，λn。

求解原理：

限制條件為：

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

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

即式子

解得：

因此第i個特征權重為：

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

3 SVM 與使用虛點原理的SVM

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

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

（1）在訓練集中，根據虛點算法調整特征權重，映射到虛點空間。其中權重應滿足歸一化條件以及虛點空間中虛點之間的距離最小。

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

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

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

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

4 實驗

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

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

表1 交叉測試結果

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

5 結束語

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

本文的主要貢獻是：

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

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

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