基于KL散度的無監(jiān)督特征選擇方法

魏碧劍

(溫州大學數(shù)學與信息科學學院，浙江溫州 325035)

基于KL散度的無監(jiān)督特征選擇方法

魏碧劍

(溫州大學數(shù)學與信息科學學院，浙江溫州 325035)

提出一種新的無監(jiān)督的特征選擇方法，該方法首先通過計算數(shù)據(jù)樣本在圖上的測地距離來定義兩個樣本點之間的聯(lián)合概率密度，該聯(lián)合概率可用于描述這兩樣本之間的相似程度，然后把特征基于相關(guān)性矩陣進行預(yù)分組，使得在投影到低維空間中時能盡量滿足組內(nèi)特征稀疏，最后通過極小化KL散度、投影矩陣的L2,1范數(shù)以及最后的特征優(yōu)化式子來優(yōu)化目標，從而達到維數(shù)降低的目的．

測地距離；特征分組；KL散度；投影矩陣

隨著科技的進步，特征選擇在近幾年得到了很好的發(fā)展．日常生活中我們經(jīng)常會遇到各種不同的數(shù)據(jù)，并且需要對這些數(shù)據(jù)進行分類．大多數(shù)情況下，碰到的數(shù)據(jù)都是高維的，隨著數(shù)據(jù)維數(shù)的增長，對數(shù)據(jù)的認識和判別難度也會增加，這樣就促進了特征選擇方法的發(fā)展．現(xiàn)存的特征選擇方法大體可以分為三類：有監(jiān)督、半監(jiān)督、無監(jiān)督的特征選擇方法．進行計算時把所有樣本的類別標簽都考慮在內(nèi)，則稱這種方法是有監(jiān)督的特征選擇[1]；若在計算時只是運用了原始數(shù)據(jù)中一部分樣本的類別標簽，而對于其它的樣本不考慮其類別信息，則稱這種為半監(jiān)督的特征選擇方法；若進行特征選擇時沒有考慮任何一個樣本的類別標簽，則稱這種特征選擇方法為無監(jiān)督的特征選擇[2]．根據(jù)經(jīng)驗可知，在做數(shù)據(jù)處理時如果需要考慮樣本的類別信息，那么就要在收集數(shù)據(jù)的同時收集相對應(yīng)的類別信息．我們知道如果只是收集樣本數(shù)據(jù)是比較容易的，但是如果還要收集樣本相對應(yīng)的類別信息，就要花費更多的時間和精力，并且在對原始數(shù)據(jù)進行儲存時需要更多的空間．所以說，雖然我們知道有監(jiān)督的或者半監(jiān)督的特征選擇方法也許能夠更好地對原始數(shù)據(jù)進行特征選擇，但是在前期數(shù)據(jù)收集過程中往往需要花費更多的精力和時間．因此，我們希望運用無監(jiān)督的特征選擇方法也能夠得到很好的特征選擇結(jié)果，這樣無疑就促進了無監(jiān)督特征選擇方法的發(fā)展．

無論是有監(jiān)督、半監(jiān)督還是無監(jiān)督的特征選擇方法，都是在這樣一個假設(shè)下進行的，即在高維空間中距離比較近的樣本應(yīng)該具有相同的類別標簽[3]．所以無論是運用何種方法進行特征選擇，都希望能夠很好地把在高維數(shù)據(jù)中的特性保留到低維數(shù)據(jù)中去．但在進行特征選擇時，一般都是通過歐式距離來表示原始數(shù)據(jù)中樣本之間距離的，而歐式距離在評價兩個樣本之間的距離時會出現(xiàn)不可預(yù)計的誤差，本文算法將緩解這種誤差．

此外，在進行特征選擇時，都是通過約束投影矩陣的L2,1范數(shù)的大小來實現(xiàn)特征選擇稀疏性的．由于在進行特征選擇時往往只對一些特別重要的特征及其相關(guān)特征進行了保留，對于那些比主要特征相對較不重要的特征卻沒有很好保留，所以我們保留的原始數(shù)據(jù)中特征不完善．在進行特征選擇時，所用的訓練數(shù)據(jù)是比較有限的，也許通過這種特征選擇方法能夠很好地和訓練數(shù)據(jù)中的樣本區(qū)別開來，但是當數(shù)據(jù)集進行擴充，添加新樣本時，對新樣本的類別標簽的評判就會出現(xiàn)誤差，同樣，本文算法也會對這個誤差進行緩解．

1 本文算法描述

1.1 測地距離

流形上的測地距離，能夠很好地反應(yīng)出原始數(shù)據(jù)中深層的整體結(jié)構(gòu)，并且已經(jīng)在一些非線性降維的算法中得到了很好運用[4]．運用時，首先通過原始輸入數(shù)據(jù)得到一個圖，然后基于這個圖去尋找兩個樣本之間的最短距離，以此來預(yù)計兩點間的測地距離．這種方法能很好地估計出輸入數(shù)據(jù)中樣本之間的測地距離．但在運用k-NN算法對輸入數(shù)據(jù)生成圖時會有一定的限制性[5]．在這種算法中k是個參數(shù)，通過它去控制樣本的鄰居個數(shù)．一般來說，如果鄰居的個數(shù)比較少時，得到的圖就是幾個分塊的圖，這種情況下是很難去估計輸入數(shù)據(jù)中樣本之間的測地距離的．此外，如果給出的鄰居個數(shù)比較多，則在計算樣本間的測地距離時可能會出現(xiàn)“回路”情況，這樣就會使通過計算圖上的流形距離來估計測地距離的算法失效．

基于這種圖的計算方法已有很多，例如基于圖論的計算方法[6]，或者是基于凸優(yōu)化問題的計算方法[7]．這些算法都能很好地緩解上述提到的關(guān)于計算測地距離所存在的問題．

本文將運用一種簡單且高效的方法來得到輸入數(shù)據(jù)的k-Edge-Connected圖（k-EG）．在輸入數(shù)據(jù)中，每個樣本與它距離最近的k個樣本構(gòu)成一個小的圖，通過計算每個輸入樣本的k個最近距離樣本，最終得到輸入數(shù)據(jù)的k-EG圖．這種圖的最大優(yōu)點是可以在輸入時不考慮k的大小，而且也可以避免因k太大而造成在尋找最短路徑時出現(xiàn)“短路”的危險．

輸入數(shù)據(jù)構(gòu)成圖以后，通過Dijkstra’s算法[8]在圖中尋找兩個樣本之間的最短路徑，這樣就可以得到輸入數(shù)據(jù)中兩個樣本基于流形的測地距離．用來表示樣本xi和xj之間的測地距離．在考慮兩個樣本之間的相似程度時，運用測地距離優(yōu)于直接用兩點之間的歐式距離，因為運用歐式距離往往會出現(xiàn)不可避免的誤差．例如在三維空間中的Swiss roll數(shù)據(jù)如圖1．

圖1 瑞士卷數(shù)據(jù)流形分布示意圖

在考慮樣本之間的相似程度時運用歐式距離會使類別標簽不相同的樣本有很高的相似性，這樣在對原始數(shù)據(jù)進行降維時就會出現(xiàn)不可避免的誤差．在算法中運用樣本之間的流形距離，可以很好地降低由于歐式距離估計帶來的誤差．本文算法中用樣本之間的測地距離代替歐式距離，得到一個很好的輸入數(shù)據(jù)樣本之間的相似概率，以此來描述輸入樣本之間的相似程度．

1.2 輸入數(shù)據(jù)的特征分組

一般在做線性特征選擇時，都會給投影矩陣W一個稀疏性的要求，這個稀疏條件都是通過約束投影矩陣的L2,1范數(shù)的大小來實現(xiàn)的．采用這種方法進行特征選擇時，不僅可以挑選出原始數(shù)據(jù)中有用的特征，而且還能保證特征之間足夠稀疏．通過大量實驗發(fā)現(xiàn)，在實現(xiàn)低維空間中特征的稀疏表示時，總是盡量去運用比較少的特征來表示原始數(shù)據(jù)中全部的特征．但是卻忽略了這樣的問題：選出來的特征可能會有很高的線性相關(guān)性，這樣就使得在進行特征選擇時，相關(guān)性較大的特征都保留了下來，而那些同樣有一定的區(qū)別性的特征卻沒有得到很好的保留．由此我們考慮采用原始數(shù)據(jù)特征分組的方法去緩解這種問題，這樣不僅可以保證低維空間中所保留數(shù)據(jù)特征的稀疏性，并且還能使得這些特征在組內(nèi)稀疏，組間稠密．

首先需要把原始數(shù)據(jù)的特征進行分組，通過計算特征之間的相關(guān)性，得到原始數(shù)據(jù)中特征之間的相關(guān)性矩陣，其中Rst表示原始數(shù)據(jù)中第s個特征和第t個特征之間的相似程度，并且對Rst的定義如下：

運用這個特征的相關(guān)性矩陣對特征進行分組．分組時由計算機隨機給出一個閾值θ，當兩個特征的相關(guān)性大于θ時，就定義這兩個特征構(gòu)成一組.通過該方法把原始數(shù)據(jù)中的特征分成k組.在對算法中特征相似性較大的兩個特征進行挑選時，最好是選擇其中一個而不選擇另一個，這樣就可以實現(xiàn)特征在組內(nèi)是盡量稀疏的．本文將運用投影矩陣W來實現(xiàn)這種選擇，其中，投影矩陣的每一列都與輸入數(shù)據(jù)中的一個特征相對應(yīng)．挑選組內(nèi)特征可以通過投影矩陣列向量的二范數(shù)來實現(xiàn)．需要極小化如下公式：

其中，Wj表示投影矩陣W的第j個列向量，表示原始數(shù)據(jù)中第j個特征在Gg這個組內(nèi)（其中，i,j分別表示原始數(shù)據(jù)中第i或j個特征，g表示第g組）．這樣在進行特征挑選時就不會把特征相似度很高的特征全部挑選進去，同時也能夠很好地保留有區(qū)別性的特征．

1.3 無監(jiān)督特征選擇的KL散度

高斯函數(shù)中的參數(shù)iσ隨xi變化，本文根據(jù)文獻[9]中提到的算法來確定不同的xi所對應(yīng)的iσ．首先使用者給定一個復(fù)雜度的值，然后通過二分法的算法去計算出iσ的一個估計值．本文對復(fù)雜度進行如下定義：

通過公式（4）可以反解出iσ．

在高維空間中可以運用概率來表示樣本之間的相似程度，在低維空間中也用同樣的方法來考慮投影以后點與點之間的關(guān)系，但不再運用高斯分布來表示，而是用 student t-distribution（這種分布與常見的柯西分布相似）來代替．運用student t-distribution可以得到低維空間中的聯(lián)合概率：

student t-distribution是一個單自由度的分布，性能好，且當?shù)途S空間中兩點之間的距離正好反比于這個距離．因此，通過這樣的概率描述出來的圖像與應(yīng)該得到圖像的差距是比較小的，并且這樣還能夠把類別標簽比較多的數(shù)據(jù)很好地分離開來．通過上面兩個定義就得到了目標函數(shù)中的KL散度：

因為最關(guān)心的是它與附近點的相關(guān)程度，所以限定

1.4 本文的目標函數(shù)以及目標函數(shù)的梯度

在把高維數(shù)據(jù)降到低維空間時希望去找到一個投影矩陣W，這樣就得到了需要極小化的目標函數(shù)：

目標函數(shù)中的第一項為KL散度項，使高維數(shù)據(jù)中相關(guān)性比較大的樣本投影到低維空間；第二項，通過極小化投影矩陣的L2,1范數(shù)來限定選擇的特征是足夠稀疏的；最后一項，通過選擇盡量少的特征相關(guān)度比較大的特征來有區(qū)別性地選擇特征．本文運用梯度下降的方法來優(yōu)化目標函數(shù)．目標函數(shù)中第三項的梯度不方便求解，本文采用文[10]提到的算法將其進行轉(zhuǎn)化，然后再進行梯度求解，得到：

通過以上轉(zhuǎn)化就可以對目標函數(shù)進行梯度求解運算了．求解得到目標函數(shù)的梯度為：

這里的Wi表示的是投影矩陣W的第i個行向量．

對第三個梯度進行求解：

根據(jù)以上求解得到目標函數(shù)的梯度為：

通過MATLAB程序優(yōu)化目標函數(shù)．算法流程如下：

1）通過方程（15）提供的梯度迭代出 Wt；

1）通過方程（9）迭代出 Ft．

2 實 驗

2.1 數(shù)據(jù)集

哥倫比亞大學圖像數(shù)據(jù)庫中數(shù)據(jù)集COIL-20[Nene et al.,1996]中包括了20個不同物品的1 440張灰色照片，每張灰色照片由32 × 32個像素構(gòu)成．

哥倫比亞大學圖像數(shù)據(jù)庫中數(shù)據(jù)集COIL-100[Nene et al.,1996]中包含了100個不同物品的7 200張灰色圖片，每張灰色照片由32 × 32個像素構(gòu)成．

CBCL3000數(shù)據(jù)集由兩個不同人的人臉照片構(gòu)成，照片有3 000張，每張照片由19×19個像素組成．

USPSclassifyAll數(shù)據(jù)集由手寫數(shù)字圖片構(gòu)成，有11 000張灰色照片，每個照片由19×19個像素構(gòu)成．

2.2 本文算法與其它算法的比較

Fisher score（FS），Efficient and Robust Feature Selection via Joint L21-Norms Minimization（ERFS）[2]，unsupervised local discriminative analysis（UDFS），MCFS，都是無監(jiān)督的特征選擇方法，將本文算法（UtSNFFS）與它們進行比較．此之，把1-NN算法作為一個基本線進行考慮，

因為這個算法是沒有參數(shù)輸入的．實驗結(jié)果見圖2、圖3、圖4、圖5．

圖2 不同算法在COIL100數(shù)據(jù)集上的實驗效果

圖3 不同算法在COIL20數(shù)據(jù)集上的實驗效果

圖4 不同算法在CBCL3000數(shù)據(jù)集上的實驗效果

圖5 不同算法在USPSclassifyAll數(shù)據(jù)集上的實驗效果

從圖2、圖3、圖4可以看出，本文提出的無監(jiān)督特征提取方法，能夠利用較少的特征數(shù)量得到很高的正確率，這就意味著在把原始數(shù)據(jù)中的樣本投影到低維空間時能夠用很少的特征去表示原始數(shù)據(jù)中樣本之間的聯(lián)系程度，說明本文提出的算法，在COIL100、COIL20、CBCL3000數(shù)據(jù)集上的應(yīng)用效果很好，尤其是在數(shù)據(jù)集COIL100上，明顯優(yōu)于其它算法．從圖5可以發(fā)現(xiàn)，當特征選取的個數(shù)在30 - 80時，與上文提出的所有無監(jiān)督特征選擇方法相比，本文算法的正確率更高．實驗結(jié)果表明，本文算法對高維數(shù)據(jù)的降維效果比其它算法的更好．所以本文提出的算法是有效可行的．

3 結(jié) 語

本文提出一種新的無監(jiān)督的特征選擇方法（UtSNEFS），把流形上的測地距離很好地運用到聯(lián)合概率上，并用聯(lián)合概率描述了兩個樣本之間的相似程度，在保留點與點之間相似程度的情況下，利用KL散度把高維空間中的點投影到了低維空間．同時很好地考慮了相似特征之間的互斥性，從而在相似程度較大的特征之間能夠有選擇性地去挑選特征．此之，在把高維空間中的數(shù)據(jù)投影到低維空間中時，盡量保證了其特征的稀疏性，從而使選出來的特征是足夠稀疏的．實驗結(jié)果表明，本文所提出的算法在無監(jiān)督算法中有較好的性質(zhì)．

[1] Duda R O,Hart P E,Stork D G. Pattern classification [M]. 李宏東，譯. 2版. 北京：機械工業(yè)出版社，2003：96-99.

[2] He X,Cai D,Niyogi P. Laplacian score for feature selection [J]. Advances in Neural Information Processing Systems,2005,18: 507-514.

[3] Zhou D,Bousquet O,Lal T N,et al. Learning with local and global consistency [J]. Advances in Neural Information Processing Systems,2004,16(16): 321-328.

[4] Mingyu F,Xiaoqin Z,Zhouchen L,et al. A regularized approach for geodesic-based semisupervised multimanifold learning [J]. IEEE Transactions on Image Processing A Publication of the IEEE Signal Processing Society,2014,23(5): 2133-2147.

[5] Balasubramanian M,Schwartz E L. The isomap algorithm and topological stability [J]. Science,2002,295(5552): 7.

[6] Li Y. Building k edge-disjoint spanning trees of minimum total length for isometric data embedding [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2005,27(10): 1680-1683.

[7] Jebara T,Wang J,Chang S F. Graph construction and b-matching for semi-supervised learning [C] // Danyluk A,Bottou L,Littman M. Proceedings of the 26th Annual International Conference on Machine Learning. Montréal: ACM,2009: 441-448.

[8] Dijkstra E W. A note on two problems in connexion with graphs [J]. Numerische mathematik,1959,1(1): 269-271.

[9] Maaten L V D,Hinton G. Visualizing data using t-SNE [J]. Journal of Machine Learning Research,2008,9: 2579-2605.

[10] Kong D,Fujimaki R,Liu J,et al. Exclusive feature learning on arbitrary structures via l1,2-norm [J]. Advances in Neural Information Processing Systems,2014,2:1655-1663.

Introduction to Unsupervised Feature Selection Approach Based on KL Divergence

WEI Bijian
(College of Mathematics and Information Science,Wenzhou University,Wenzhou,China 325035)

This paper presents a new unsupervised feature selection method. The joint probability density through calculating the data sample in figure on the geodesic distance is firstly defined between the two sample points. The joint probability is used to describe the level of the similarity between these two samples. Then the characteristics of group based on the correlation matrix is foreordained so as to meet the need of sparse characteristics within the group when the projection lies in the low-dimensional space. At last,the objective is optimized by minimizing the KL divergence,projection matrix of L2,1 norm,and finally the characteristics of the optimized formula so as to achieve the purpose to lower the dimension numbers.

Geodesic Distance; Feature Grouping; KL Divergence; Projection Matrix

TP391

：A

：1674-3563(2017)01-0012-08

10.3875/j.issn.1674-3563.2017.01.002 本文的PDF文件可以從xuebao.wzu.edu.cn獲得

(編輯：王一芳)

2015-10-01

魏碧劍(1989- )，男，河南安陽人，碩士研究生，研究方向：計算機數(shù)學與復(fù)雜系統(tǒng)控制