虛點一種減少特征值鴻溝的方法

1、虛點：一種減少特征值鴻溝的方法林游龍1,2，余智華1，程學(xué)旗1，劉悅11中國科學(xué)院計算技術(shù)研究所，北京，100802中國科學(xué)院研究生院，北京，100190E-mail: linyoulong摘 要：基于向量空間模型的分類方法是目前各種分類方法廣泛使用的文檔結(jié)構(gòu)表示方法，在對基于向量空間模型的分類方法的研究發(fā)現(xiàn)，基于向量空間模型的分類方法存在不合理之處，即特征值之間的“鴻溝”，這種鴻溝會導(dǎo)致向量空間模型中兩點之間的距離的計算出現(xiàn)偏差，本文介紹了一種使用虛點的方法，這種方法消除了特征值之間的鴻溝，使得分類的效果得到了提高。該方法是通過重新定義特征權(quán)重，調(diào)整向量空間模型中點的特征值，即相當(dāng)于重新定義

2、向量空間中的點，這樣的點是相對于原來向量空間模型中的點的矯正映射，即就好像是虛擬點一樣，最后問題歸結(jié)為計算向量空間模型中的點與虛擬點的映射函數(shù)。理論分析表明虛點方法能提高基于向量空間模型的分類方法的效果，在SVM中運用虛點方法的實驗結(jié)果表明，運用虛點方法的SVM的精確度得到了提高，這種結(jié)果驗證了本文提出的虛點方法的有效性。關(guān)鍵詞：虛點；分類算法；特征權(quán)重；向量空間模型VPM: A Method to Bridge the Gap between FeaturesYoulong Lin1,2 , Zhihua Yu1, Xueqi Cheng1, Yue Liu11Institute of Co

3、mputing Technology, Chinese Academy of Sciences, Beijing, 100802Graduate University of Chinese Academy of Sciences, Beijing, 100190E-mail: linyoulongAbstract: Vector space model (VSM) is the widely used model in the representation of the document structure in a variety of classification methods. The

4、 research on the vector space model based classification method shows that there is unreasonable point, that is, the gap between the features, this gap will lead to the deviation in the calculation of the distance between the two points in vector space model. This paper proposes a method of the virt

5、ual point to eliminate the gap between two features which improve the performance of the text categorization. The method is to adjust the feature value of point in the vector space model by redefining the weight of feature which is equivalent to the redefinition of the point in the vector space. Com

6、pared with the point in the original vector space model, the point is assumed to be the correctly mapping, that is, like a virtual point. Finally the problem boils down to the calculating of the mapping function between the vector space model and of virtual vector space model. Theoretical analysis s

7、howed that the virtual-point method can improve the performance of text categorization based on the vector space model. The experimental results of the support vector machine categorization method using virtual-point show that the performance has been improved, which verify that the virtual-point me

8、thod is effective.Keywords: Virtual point, text categorization, feature weight, vector space model1 引言隨著信息時代的高速發(fā)展，如何對自然語言文本進行挖掘，特別是對其按照設(shè)定的語義進行正確的歸類，已經(jīng)成為組織大量文本信息的一個關(guān)鍵問題，這就是文本挖掘中很重要的一類任務(wù)一文本分類1。自動文本分類（Automatic Text Categorization）或者簡稱為文本分類，是指計算機將一篇文章歸于預(yù)先給定的某一類或某幾類的過程2。隨著文本信息量的快速增長，文本分類已成為信息檢索、知識挖掘和管理等

9、領(lǐng)域的關(guān)鍵技術(shù)34。文本分類的精確程度取決于特征提取5和分類算法6。人們提出了很多文本分類方法，例如k-最近鄰分類法，貝葉斯分類，決策樹和神經(jīng)網(wǎng)絡(luò)7。最廣泛使用以及效果最好的文本分類方法是支持向量機與knn方法89。支持向量機是由Vapnik等人提出的一種學(xué)習(xí)技術(shù)，是借助于最優(yōu)化方法解決機器學(xué)習(xí)問題的新工具。它集成了最大間隔超平面、Mercer核、凸二次規(guī)劃、稀疏解和松弛變量等多項技術(shù)10。由于其具有全局最優(yōu)、結(jié)構(gòu)簡單、推廣能力強等優(yōu)點，近幾年得到了廣泛地研究并應(yīng)用于文本分類、模式識別等領(lǐng)域11。k-最近鄰居分類（KNN）方法基于類比學(xué)習(xí)12，采用SVM（向量空間模型）13表示文檔，是一種非參

10、數(shù)的分類技術(shù)，在基于統(tǒng)計的模式識別中非常有效，對于未知和非正態(tài)分布可以取得較高的分類準(zhǔn)確率，具有魯棒性、概念清晰等諸多優(yōu)點14。本文在對基于向量空間模型的分類方法(如SVM 1516)的研究發(fā)現(xiàn)，基于向量空間模型的分類方法存在不合理之處，即特征值之間的“鴻溝”，這種鴻溝會導(dǎo)致向量空間模型中兩點之間距離的計算出現(xiàn)偏差，由于目前基于向量空間模型的分類方法都沒有考慮到這種鴻溝，因此分類效果受到了一定的限制，因此要想進一步提高分類效果，就必須解決這種偏差。本文介紹了一種使用虛點的方法，這種方法消除了特征值之間的鴻溝，使得分類的效果得到了提高。該方法是通過重新定義特征權(quán)重，調(diào)整向量空間模型中點的特征值，

11、即相當(dāng)于重新定義向量空間中的點，這樣的點是相對于原來向量空間模型中的點的矯正映射，即就好像是虛擬點一樣，最后問題歸結(jié)為計算向量空間模型中的點與虛擬點的映射函數(shù)。理論分析表明虛點方法能提高基于向量空間模型的分類方法的效果，在SVM中運用虛點方法的實驗結(jié)果表明，運用虛點方法的SVM的精確度得到了提高，這種結(jié)果驗證了本文提出的虛點方法的有效性。2 向量空間模型向量空間模型(Vector Space Model, VSM)8是康奈爾大學(xué)Salton等人上世紀(jì)70年代提出并倡導(dǎo)的，文檔可以轉(zhuǎn)化為標(biāo)引項(term)及其權(quán)重組成的向量表示，都可以看成空間中的點。向量之間通過距離計算得到向量的相似度。VSM中

12、有三個關(guān)鍵問題：(1)標(biāo)引項(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。3 虛點原理3.1

13、虛點方法產(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.跟分

14、類中心2(3,2)的Feature2的距離為特征Feature2的差值1。可以知道應(yīng)該將對角點分到類別2(3,2)那一組，但從理論上可知，屬于同一特征的值，可以用量來表示，但是屬于不同特征的值無法用量來表示，因為兩者的判定的標(biāo)準(zhǔn)不一樣。Feature2的差值為2的數(shù)不一定大于Feature1的差值為1的數(shù)。因此僅僅從此對角點的分類問題應(yīng)該無法判斷到底屬于哪一類。也就是Feature2的差值為2的數(shù)應(yīng)該與Feature1的差值為1的數(shù)相等。此時對角點到兩類的距離相等，符合無法判斷類型的情況。因此原向量空間模型沒考慮到這個問題，這就是特征值的鴻溝問題(GBF)的產(chǎn)生。如圖1所示鴻溝為q1。圖1.虛

15、點原理示意圖Fig. 1. Theory of Virtual Point Method為了消除特征值之間的鴻溝?？梢哉J(rèn)為存在原分類點的虛點，這些點是由調(diào)整特征權(quán)重的分配來得到的。它們必須滿足兩個條件：1、歸一化條件。2、調(diào)整后的兩個類別虛點到虛對角點的距離必須相等。 如圖所示，vp1和vp2分別對應(yīng)分類點1和分類點2的虛點?，F(xiàn)在的問題歸結(jié)為本文提出的特征鴻溝理論到底存不存在，用即特征鴻溝的的消除能不能帶來分類效果的提高，從如圖2所示，就是要證明在虛點空間中用vp1和vp2分類比原向量空間中分類的效果更好。3.2虛點方法介紹變量定義：假設(shè)向量空間模型中的分類點為類別1的分類中心a和類別2的分類

16、中心b，必然存在一個點a，它跟a的距離只跟Feature(1)相關(guān)，即特征距離，假設(shè)其為l(1),跟b的距離只跟Feature(2),設(shè)為l(2)相關(guān)，這個點稱為a和b的對角點。易知a和b的對角點有兩個，任選其中的一個Feature(1)與Feature(2)之間的距離鴻溝d(12)定義為：d(12)=|l(1)l(2)|。虛點方法：存在特征權(quán)重l(1),l(2)滿足歸一化條件，并且使得分配權(quán)重后的向量空間中的點，即原空間中的a和b在虛點空間中的分別對應(yīng)的點的虛點a和b的2個特征距離相等，即a和b到它們虛點空間中的對角點的離相等：l(1) = l(2)。這樣在虛擬空間中特征之間的距離鴻溝就為零

17、了。關(guān)于對角點的說明：虛點空間與原空間的對角點不是獨立存在的，他是針對分類點，以及虛點空間中分類點的虛點而提出的一個抽象的概念，它在現(xiàn)實中可能不存在。 到目前為止就只有一個問題了，即特征值鴻溝的觀點是否存在？3.3 虛點方法的例子為了形象的說明整個流程，舉個例子：比如判斷一列火車屬于快車與慢車的標(biāo)準(zhǔn)為：快車為，平均車廂的數(shù)量為10節(jié)，速度平均為180公里/小時。而慢車的為：平均車廂30節(jié)，速度平均為80公里/小時。如果此時，有一列特殊的列車，車廂為10節(jié)，速度為80公里/小時。那么根據(jù)向量空間模型的公式，可以算出這種列車對快車的差異為速度相差100公里/小時，車廂沒差異。對慢車的差異為車廂相差

18、20節(jié)，速度沒差異，進行標(biāo)準(zhǔn)化以后(假設(shè)速度的標(biāo)準(zhǔn)化為原值除以180，車廂的標(biāo)準(zhǔn)化為原值除以30)，差異分別為100/180,20/30。從而知道此列車屬于快車。但是理論上可知此列出應(yīng)該不能判斷歸屬，因為20節(jié)車廂跟100公里/小時這兩個數(shù)無法比較。此時鴻溝為差異值的差值即|100/180-20/30|=0.11。而這列車可能現(xiàn)實中不存在，它只是針對快車和慢車而提出的一個概念。因此本文設(shè)特征權(quán)重l(1),l(2)來分別調(diào)整火車車廂跟火車速度的權(quán)重，設(shè)歸一化條件l(1)×l(2)1。此時l(1)×(20/30) = l(2)×(100/180)?？梢缘贸鰈(1)&#

19、187;0.9129，l(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。說明使用快車，與慢車的虛點用來分類比使用原點分類來得更接近實際。3.4 虛點方法的另一種解讀假設(shè)原空間中存在分類點a(0,0)點和b(a,b)點。根據(jù)虛點方法可知，它們在虛點空間中分別對應(yīng)虛點a(0,0)和b(al1,bl2)，其中，l1l2=1設(shè)a和

20、b的距離為c，則根據(jù)直角三角形公式，已及直角三角形不等式可知： （1）其中當(dāng)al1=bl2，時c有最小值。而al1=bl2是虛點空間中的虛點滿足的條件。因此虛點方法就轉(zhuǎn)化為求虛點空間中虛點之間最小距離。即3.1節(jié)提出的虛點滿足的兩個條件變?yōu)椋?、歸一化條件。2、調(diào)整后的兩個類別之間的距離最小。35虛點方法的求解輸入變量定義：假設(shè)向量空間模型由n維特征向量構(gòu)成，類別1的分類中心為a(a1,a2,.an)，類別2的分類中心為b(b1,b2,.bn)。輸出變量：特征權(quán)重l1，l2，ln。求解原理： （2）限制條件為: （2）根據(jù)以上可知，這是最優(yōu)化問題，因此本文使用拉格朗日乘數(shù)來解決此問題。得到如下

21、函數(shù)： （3）其中l(wèi)為拉格朗日乘數(shù)。為了求l1, l2, ln。將函數(shù)(3)分別對l1, l2, ln求偏微分得： （4）即式子 （5）解得： （6）因此第i個特征權(quán)重為： （7）從以上式子可以看出，跟a和b的第i個特征的差值成反比。此結(jié)果證實了給人的感覺，即為了縮小特征鴻溝，特征值差異越大的，應(yīng)該將它們分配的權(quán)重越低。4 SVM與使用虛點原理的SVM支持向量機方法是建立在統(tǒng)計學(xué)習(xí)理論的VC維理論和結(jié)構(gòu)風(fēng)險最小原理基礎(chǔ)上的17，根據(jù)有限的樣本信息在模型的復(fù)雜性(即對特定訓(xùn)練樣本的學(xué)習(xí)精度，Accuracy)和學(xué)習(xí)能力(即無錯誤地識別任意樣本的能力)之間尋求最佳折衷，以期獲得最好的推廣能力(Ge

22、neralizatin Ability)。支持向量機方法的幾個主要優(yōu)點是1、可以解決小樣本情況下的機器學(xué)習(xí)問題2、可以提高泛化性能3、可以解決高維問題4、可以解決非線性問題5、可以避免神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)選擇和局部極小點問題18。根據(jù)虛點方法可知，在SVM中使用虛點方法的步驟如下：1、在訓(xùn)練集中，根據(jù)虛點算法調(diào)整特征權(quán)重，映射到虛點空間。其中權(quán)重應(yīng)滿足歸一化條件以及虛點空間中虛點之間的距離最小。2、在虛點空間運用SVM方法，即找出最優(yōu)分類超平面，此時的最優(yōu)超平面是虛點空間的最優(yōu)分類超平面。3、用虛點空間的最優(yōu)分類超平面來分類,即使用虛點空間建立的模型。圖2.原SVM分類方法與使用了虛點方法的SVM分類

23、方法Fig. 2. SVM and Virtual Point Method based SVM如圖所示2對于步驟1，首先分別求訓(xùn)練集中類別1和類別2的分類中心，可以用分別求類別1和類別2中向量的平均值的方法。然后使用3.6節(jié)中介紹的求解虛點的方法，求出特征權(quán)重。根據(jù)特征權(quán)重重新計算特征向量，相當(dāng)于將原點映射到虛點空間，此時產(chǎn)生的新的訓(xùn)練集即虛點空間中的訓(xùn)練集。對于步驟2，跟運用SVM方法的差別僅僅是訓(xùn)練集的不同，即虛點空間運用的是步驟1產(chǎn)生的訓(xùn)練集。對于步驟3，跟運用SVM方法的差別僅僅是模型的不同，即，虛點空間用于的是步驟2產(chǎn)生的模型來分類。5 實驗LIBSVM 是臺灣大學(xué)林智仁(Chih

24、-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份合并為一個訓(xùn)練集。核函數(shù)選取徑向基函數(shù)19。因為其對應(yīng)的特征空間是無窮維Hilber

25、t空間。而Hilbert空間推廣了高斯空間的概念，這點跟虛點方法(VPM)很相似。數(shù)據(jù)集都是經(jīng)過了歸一化的了。虛點方法參數(shù)l=2, 測試的是分類精度。實驗結(jié)果如表1所示：表1 交叉測試結(jié)果Tab.1 Result of Cross TestNo.12345SVM56.92%54.35%58.25%47.04%43.43%SVM using VPM61.81%58.35%62.30%52.37%46.74%No.678910SVM50.64%55.19%50.15%59.14%43.19%SVM using VPM55.48%60.47%56.08%64.33%48.27%由實驗結(jié)果可知，使用了

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

27、提出了特征值之間存在鴻溝的問題，2、介紹了一種使用虛點的方法來降低特征值之間的鴻溝。本文介紹的使用虛點的方法，證明了分類中存在特征鴻溝的問題，提高分類的效果，本文使用的是用平均值求特征值鴻溝的方法，這種方法具有一定的局限性，因此研究求特征值鴻溝的方法以及使用訓(xùn)練集的啟發(fā)式知識來定義特征值鴻溝與權(quán)重分配將是下一步要做的工作。參 考 文 獻1 Ruch P. Query translation by text categorizationA. Proceedings of the 20th international conference on Computational Linguistics.

28、 2004.2 Bose I, Mahapatra RK. Business data mining-a machine learning perspectiveJ. J. Information & Management. 2001, 39(3):211-225.3 Núñez H, Angulo C, Català A. Rule-Based Learning Systems for Support Vector MachinesJ. J. Neural Process. Lett. 2006, 24(1):1-18.4 Liu Y, Loh HT,

29、Kama YT, et.al. A hierarchical text classification system for manufacturing knowledge management and retrievalJ. J. Int. Knowledge Management Studies. 2008, 2(4):406-425.5 Pechenizkiy M, Puuronen S, Tsymbal A. Feature Extraction for Classification in Knowledge Discovery SystemsJ. J. Knowledge-B

30、ased Intelligent Information and Engineering Systems . 2003, 2773: 526-5326 Antonie ML, Zaiane OR, Holte RC. Learning to Use a Learned Model: A Two-Stage Approach to ClassificationA. Proc. Int. Conf. Data Mining. 2006, 33-427 Yang Y, Pedersen JO. A Comparative Study on Feature Selection in Text Cate

31、gorizationA. Proc. Int. Conf. Machine Learning. 1997, 412-420.8 Salton G, Wong A, Yang CS. A vector space model for automatic indexingJ. J. Commun. ACM, 1975, 18(11):613-6209 Qu S, Wang S, Zou Y. Improvement of Text Feature Selection Method Based on TFIDFA. Proc. Int. Seminar on Future Information T

32、echnology and Management Engineering. 2008, 79-8110 Yang Y, Liu X, A re-examination of text categorization methodsA. Proc. Int. ACM SIGIR Conf. Research and Development in information Retrieval. 1999, 42-4911 Vapnik VN, The Nature of Statistical Learning TheoryM. Berlin: Springer-Verlag, 1995.12 Has

33、tie T, Tibshirani R. Discriminant Adaptive Nearest Neighbor ClassificationJ. IEEE Trans. Pattern Analysis and Machine Intelligence. 1996, 8(6):607-61613 Shakhnarovich G, Darrell T, Indyk P. Nearest-Neighbor Methods in Learning and Vision: Theory and Practice (Neural Information Processing)M. The MIT Press, 2006.14 Dasarathy BV. Nearest neighbor (NN) norms: NN pattern classification techniqueM. Los Alamitos:IEEE Computer Society Press, 199015 Cristianini N, Taylor JS. An Introduction to Support Vector Machin