基于概率密度逼近的無監督特征排序

摘要：依據概率密度逼近提出了一種新的無監督特征排序，應用于特征選擇降維。實驗證明，這種方法與一些現有的方法相比，更為有效。

關鍵詞：特征排序； 特征選擇； Parzen窗口密度估計； 概率密度逼近

中圖分類號：TP3016文獻標志碼：A

文章編號：10013695(2007)04004705

0引言

模式識別和數據分析中，經常需要利用樣本的特征將樣本劃分為不同的模式類別。通常情況下，樣本特征中包含了足夠的類別信息，才能通過分類器實現正確分類。然而，特征中是否包含足夠的類別信息卻很難確定。為了提高識別率，總是最大限度地提取特征信息，但這不僅使特征維數增大，造成人們所說的維數災難(Curse of Dimensionality)[1，2]，而且其中可能存在較大的相關性和冗余，影響識別的準確性。因而選擇合適的特征來描述模式，不僅對模式識別的精度、需要的訓練時間和需要的實例等許多方面影響很大，并且對分類器的構造也起著非常重要的作用^[3]。這樣，降維對于數據的有效分析就顯得非常重要；特征選擇和特征轉換（特征提取）就是降維的兩種主要方法。特征選擇是選出有用的或重要的特征，拋棄其他特征；特征轉換是根據原來的特征空間再建一個新的特征空間。目前已有不少文獻對這樣的問題進行了探討^[4～6]。在特征選擇方面，已有很多提出了有監督學習的特征選擇算法。但針對無監督學習的特征選擇問題卻并不多。無監督學習的特征選擇問題就是依據一定的判斷準則，選擇一個特征子集能夠最好地覆蓋數據的自然分類^[3]。不容置疑，從理論上講，窮舉法是一種能確保找到最優特征子集的最可靠的特征選擇算法，但這種方法計算量很大，在高維數據中是不能進行的。例如從d個原始特征中選出勢為r的最優特征子集，逐一評估所有Crd個不同特征子集，從中挑選出滿足判別函數需求最優的那一個特征子集。當在高維數據中或d很大時，這種方法的操作性顯得很小。

因此，尋找別的可行方法顯得非常重要。目前，有基于遺傳算法的特征選擇方法^[7]、基于模式相似性判斷的特征選擇方法^[8]和信息增益的特征選擇方法^[5]。然而，這幾種方法沒有考慮特征之間的相關性和特征對分類的影響^[3]。Kira和Rendell^[9]提出RELIEF方法。其關鍵思想在于通過估算每一維特征區分與自己一類樣本和另一類樣本的性能來評定這一維的重要性，但它僅能應用于兩類情況。文獻[10]針對RELIEF提出了一種改進的RELIEFF，使RELIEFF能應用于多類情況。文獻[11]利用信息能量的最大化，提出一種叫ESRNG的算法。文獻[4]應用單個特征與類標的互信息來排序特征的重要性，但這些均使用了類標，屬于有監督排序。文獻[5]利用信息增益提出一種SUD方法。文獻[3]依據特征對分類結果的影響和特征之間相關性分析兩個方面，提出了一種基于K均值聚類方法。在文獻[12]中利用計算FS(Feature Saliency)來對特征進行排序。這幾種方法均可以應用于無監督排序中。本文依據概率密度逼近，從另一個角度提出了一種新的對特征進行無監督排序的方法，用于特征選擇問題。本文對原始樣本空間進行變換，然后應用Parzen窗口密度估計對原始樣本數據集和變換后數據集進行概率密度估計，再對兩個概率密度進行逼近，從而對特征的重要性進行排序。這樣，就可以根據需要確定特征選擇維數，選出重要的特征組，從而達到降維的目的。實驗結果表明，這種方法是有效的。

1Parzen窗口密度估計

1.1簡介

Parzen窗口密度估計是一種非參數的概率密度估計法。起源于統計的基本理論，可以在不知道樣本的總體分布形式或分布不能寫成某些參數的函數的情況下，直接利用樣本值來估計總體概率密度。這種方法是把樣本集中各樣本點的窗口函數進行疊加，作為總體密度函數的估計。Parzen窗口密度估計的基本表達形式為^[13]

p^N(x)=1/N∑Ni=11/VN[（x-xi）/hN](1)

其中，樣本xi∈X，N為樣本數目；(#8226;)表示一個窗口函數；hN是超立方體窗口的寬度；VN是寬度為hN的超立方體窗口的體積。

12Gaussian窗口函數的Parzen密度估計

在Parzen窗口密度估計中，(#8226;)窗口函數可以有不同的選擇，只要它滿足一定的條件^[13]。當(#8226;)取Gaussian函數時，d維空間的x∈Xd Gaussian窗口函數為^[14]

其中，Σ為協方差矩陣，h是超立方體窗口的寬度。由于式(2)可以重新表示為

這樣，根據式(1)和(3)，應用Parzen窗口密度估計并選取Gaussian窗口函數的d維空間的N個樣本x∈Xd密度函數可以表示為p(x)=1/N∑Ni=1G(x-xi，Σ)(4)

其中，Σ=KΣ′(K=h2，h是超立方體窗口的寬度，Σ′是協方差矩陣)。本文根據樣本數據集不同的特征，取不同的σ，這樣更能體現數據樣本的特性。

對于d維空間的Gaussian窗口函數，有如下結論^[4]：

式(4)、(5)構成了本文方法和計算公式推導的基礎。

2基于概率密度逼近的特征排序

2.1概率密度逼近的特征排序

假定數據樣本x={x1，x2，…，xd}T，x∈Xd，數據樣本空間Xd共有N個樣本，為d維。作加權變換y=φ(x)={w1x1，w2x2，…，wdxd}T，w={w1，w2，…，wd}T。其中y∈Yd，權重wi＞1，∑di=1wi=M(M為定值)。假定f(x)為原樣本空間Xd的密度估計，g(y)為變換后的樣本空間Yd的密度估計。

本文依據的基本思想是：假設x={x1，x2，…，xd}T按特征重要性進行降序排列后，特征序列號表示{k1，k2，…，kd}。如果權重w={w1，w2，…，wd}T(wi＞1，∑di=1wi=M，M為定值)按從小到大排序序列號也是{k1，k2，…，kd}，則兩個密度函數f(x)和g(y)應最靠近，即兩者間距離最小。也就是說，在權重wi＞1，∑di=1wi=M(M為定值)的前提下，對原來的樣本數據作加權變換y=φ(x)={w1x1，w2x2，…，wdxd}T。當越重要的那一維特征變化(即wi)越小時，則變換前后的兩個密度函數應該越靠近。

于是作下面的度量：

則D(f，g)是關于w的函數。可以根據D(f，g)最小時的w，按照w的各個元素從小到大來降序排列x的特征的重要性序列。

由于 (x)dx與w無關，保持不變，當w=argw min(D(f，g))時其中其中，wi＞1，∑di=1wi=M(M為定值)。

這樣，可以依據當J(f，g)達到最小時w的各分量從小到大排序的序號，來降序排列x各個特征的重要性;然后根據需要確定要選擇的維數，從中選出重要的特征。

2.2概率密度逼近度量計算

假定數據樣本x={x1，x2，…，xd}T，x∈Xd，數據樣本空間Xd共有N個樣本;假定f(x)為原樣本空間的總體概率密度估計，則應用Gaussian窗口函數的Parzen密度估計，根據式(4)可以得到

f(x)=1/N∑Ni=1G(x-xi，∑x)(8)

這里，對數據樣本的不同維特征采用不同的σ，即

其中，K=h2為調節參數；h為原來數據樣本的窗口寬度;σ′2k為數據樣本第k維特征的方差，其估計采取:

其中，xik為數據樣本第i樣本變量的第k特征值；xk為第k特征均值。在很多應用Gaussian窗口函數的Parzen密度估計文章中^[4，14]，均采用了Σ=σ2I(其中I為d維單位矩陣)，即對每一維特征采用了相同的σ2。這種方法主要對Σ=σ2I的σ進行調節。對于高維數據，由于特征在每一維上的散度不同，其相應的σ應體現這一點。根據樣本數據集不同的特征，取不同的σ更能體現數據樣本的特性，從而在密度估計上更為準確。

對x∈Xd，作加權變換y=φ(x)={w1x1，w2x2，…，wdxd}T，w={w1，w2，…，wd}T。其中y∈Yd，權重wi＞1，∑di=1wi=M(M為定值)。假設g(y)為變換后樣本空間的密度估計，則同樣根據Parzen窗口密度估計，選擇Gaussian窗口函數，由式(4)和上面的推導可得

g(y)=1/N∑Ni=1G(y-yi，Σy)(11)

其中，Σy=K×σ′2y1σ′2yd。

σ′2yk變換后的y∈Yd空間的數據樣本的第k維特征方差，其估計采取:σ′2yk=1/（N-1)∑Ni=1(yik-yk)2=w2kσ′2k其中，yik為變換后的y∈Yd空間數據樣本的第i樣本變量的第k特征值；yk為第k特征均值。根據式（10）、(11)，可得

由此，根據式(5)、(8)、(11)可得

這樣，根據式(6)、(13)和(14)有(15)

其中，Σx根據式(9)來計算;Σy根據式(12)來計算。

2.3求解方法和步驟

本文的目標是要選出特征重要性高的特征組。所以應首先求出式（7）；再根據w的各個元素從小到大來降序排列特征的重要性，從而根據需要選出需要的特征組。在求解過程中，需要調節式(9)或(10)中的參數K和設定M。為了求出w=argwmin(J(f，g))，可以用梯度下降法求解。其中求梯度的方法為

所以，由式(15)～(17)，有

其中，σ2k根據式(10)來計算。這構成了基于梯度下降法的關于w的迭代公式:

其中，α為學習速率，實驗中α＝01。

這樣，根據以上推導，形成求解步驟：

（1）初始化w(本文中采用了wk=M/d);

(2)根據式(15)，求出J(f，g)，假如其不再減小，或達到循環次數時，退出循環，轉到（4）；

（3）根據式(18)，求出梯度J/w，調整w，轉到（2）；

(4)按從小到大排序w，從而降序排序特征的重要性。

根據需要確定特征的維數并選擇出需要的特征組，從而達到降維的目的。

3實驗及結果

為了驗證本文方法的有效性，選取了八個數據集（Pipeline取自http://www.ncrg.aston.ac.uk/GTM/3phaseData.html;其他取自http://www.ics.uci.edu/%7Emlearn/MLRepository.html）來進行實驗，實驗分為兩組：在第一組中，共有五個數據集。先用本文的方法對它們進行特征排序，然后應用LIBSVM進行交叉驗證(CrossValidation)，并與現有的一些方法進行比較。第二組實驗沒有與別的方法進行比較，去掉數據集所帶的類標，把本文的方法應用到了這些數據集上。對于有訓練和測試數據集的數據集(Pipeline、Landsat)，采用了LIBSVM^[15，16]來進行先訓練后分類測試的實驗;而對沒有測試數據集的數據集(Wisconsin Diagnostic Breast Cancer，WBC)，進行的是交叉驗證實驗。實驗中，預先對數據進行了處理，每一維處理成均值為0，方差為1。

3.1實驗組一

（1）數據描述

這一組實驗中，選擇了五個數據集。在特征排序時，去掉了樣本數據的類標。在對數據進行預處理中，由于在實驗中要計算協方差矩陣的行列式，而Ionosphere數據的第二維方差為0，將其作為最不重要的一維，并將本文的算法用到剩下的維數上。五個數據集如表1所示。

表1數據描述表

（2）特征排序

①對于NewThyroid、BreastCancer和Ionosphere數據，用本文的算法對它們進行了特征重要性排序(實驗參數是NewThyroid:K=006，M=6;BreastCancer:K=01，M=11;Ionosphere:K=02，M=36)。在文獻[5]中，用SUD^[5]、RELIEFF^[5，10]也對它們進行了特征重要性排序。排序結果如表2所示。

表2特征排序表

數據本文算法SUDRELIEFF

②對于PimaDiabetes數據，用本文的算法對它進行了特征重要性排序(實驗參數是PimaDiabetes:K=02，M=10)。在文獻[5]中，用SUD、RELIEFF也對它進行了特征重要性排序。在文獻[3]中，采用了K均值聚類方法同樣對它進行特征重要性排序。排序結果如表3所示。表3特征排序表

本文算法SUDRELIEFFK均值聚類方法

8，4，2，1，7，5，6，38，5，1，3，6，4，7，28，1，2，5，6，4，7，38，4，3，1，2，6，7，5

③對于Wine數據，用本文的算法對它進行了特征重要性排序(實驗參數是Wine:K=002，M=16)。在文獻[5]中用SUD和RELIEFF、文獻[3]中采用了K均值聚類方法、文獻[12]中采用FSM(Feature Saliency Method)均對這個數據進行了特征重要性排序。排序結果如表4所示。

表4特征排序表

（3）實驗結果

①對于NewThyroid、PimaDiabetes、BreastCancer、Wine和Ionosphere數據，采用LIBSVM對它們的各種排序結果和特征選擇數進行5Fold CrossValidation。其CrossValidtion Accuracy變化和對比情況如圖1～5所示。

②對Wine數據，分別取各種算法排列的前兩位特征進行可視化，其對比效果如圖6～9所示。③對Wine數據，由于樣本數據的類別已知，在特征排序中去掉了類標，采用FCM來對各種算法排列的各特征選擇數進行聚類，這樣可以計算出聚類出錯率。其對比效果如圖10所示(分別是20次FCM的平均錯誤率)。

在這一組實驗中， RELIEFF使用了類標，屬于有監督;SUD、FSM、K均值聚類方法和本文算法沒有使用類標，屬于無監督。從以上實驗結果可以看出，本文的方法在大多數情況下均優于沒有使用類標的方法;在與使用類標的RELIEFF相比時，有時更好，有時稍遜。

3.2實驗組二

（1）數據描述

在這一組實驗中，選擇了三個數據。在特征排序時，去掉了樣本數據的類標。這里沒有與別的方法進行比較。三個數據集如表5所示。

表5數據描述表

數據維數樣本個數類別數

（2）特征排序

采用本文的算法對它們進行了特征重要性的排序(實驗參數是Pipeline:K=01，M=14;Landsat:K=01，M=40;WBC:K=01，M=33)。排序結果如表6所示。

表6特征排序表

（3）實驗結果

采用LIBSVM對Pipeline數據集和Landsat數據集的各特征選擇數進行訓練后分類測試;對WBC數據集的各特征選擇數進行5Fold CrossValidation。實驗結果如圖11～13所示。

在這一組實驗中，沒有與其他方法進行比較。但是，從實驗結果來看，其表現出了良好的性能。對這三個具有較高特征維數的數據集選擇較小的特征維數時，就能取得較好的實驗效果，這對于應用特征選擇來降維有著重要意義。

4結束語

樣本維數的降低是模式識別和數據分析的重點又是難點之一。本文從樣本變換前和后的概率密度，在一定條件下應該最逼近出發，提出了一個新的無監督特征排序算法。其中，在應用Gaussian窗口函數的Parzen密度估計進行密度估計時，本文用有別于常用的計算Σ的方法，其更能體現數據的特征。通過實驗證明，本文的方法是有效的，而且與一些現有方法相比具有更好的實驗效果，甚至比監督方法取得更好的效果。但是，作為一種新的方法，還有待進一步的改進和完善，這也是今后的工作所在。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。