基于正則互表示的無監督特征選擇方法

汪志遠，降愛蓮，奧斯曼·穆罕默德

（太原理工大學信息與計算機學院，山西晉中 030600）

（*通信作者電子郵箱ailianjiang@126.com）

0 引言

各種智能電子設備和信息系統的廣泛使用產生和收集了大量的高維無標簽數據。利用相應的機器學習算法對這些數據進行處理和分析，可以發掘數據的潛在價值。在模式識別與機器學習研究領域中，對于機器學習算法而言，樣本數據集是訓練模型的重要前提，但是收集到的原始數據通常含有大量的冗余特征，導致其并不適合直接被使用。冗余特征不必要地增加了數據的維數，降低了訓練性能［1］。如果不剔除數據中的冗余特征，將會導致機器學習模型的訓練時間變長，訓練后得到的預測模型泛化能力差，甚至因遭遇維數災難而使訓練無法進行。文獻［2］表明，去除冗余特征可以明顯地提升訓練效率。

特征選擇是一種有效的數據降維方法［3］，它可以選出數據中的重要特征，剔除不重要的冗余特征，從而得到更加低維的數據。數據維數降低，可以減少機器學習模型的訓練時間，提高模型訓練效率［4］。根據學習任務類型的不同，特征選擇方法分為有監督特征選擇方法和無監督特征選擇方法兩大類［5］。有監督特征選擇方法依據特征與標簽之間的相關性來選出重要的特征子集，因為重要特征與標簽之間的相關性更強。然而，并非所有的數據集都帶有類別標簽信息，數據無標簽使得有監督特征選擇方法不再適用，也使得特征選擇變得更加困難［6-7］。

較早提出的無監督特征選擇方法，如最小化方差法［8］和Trace Ratio 方法［9］，這些方法單獨計算每個特征的分數，按分數排名選出特征，此類方法評價標準單一，對數據的解釋能力較差。之后發展出基于譜分析技術［10］的無監督特征選擇方法，此類方法通過對鄰接圖拉普拉斯矩陣進行譜分解，利用關聯矩陣的特征值度量各個特征的重要性，但是該方法在處理高維數據時面臨計算量過大的問題。目前，正則回歸也被應用到特征選擇，Zheng 等［11］提出的自步正則化無監督特征選擇方法（Unsupervised Feature Selection by Self-Paced Learning Regularization，UFS_SP）和劉艷芳等［12］提出的鄰域保持學習特征選擇方法（Neighborhood Preserving Learning Feature Selection，NPLFS）將特征選擇問題建模為損失函數最小化問題，對權重矩陣施加正則約束，表現出較好的魯棒性，但是現有的正則特征選擇方法優化困難，計算復雜度較高。

正則自表示（Regularized Self-Representation，RSR）方法［13］首次提出特征自表示性質，即高維數據的每個特征可由全部特征線性近似表示，該性質考慮了特征間的相關性，具有較強的數據解釋能力，但該理論也存在不足之處，在目標函數優化時，特征權重容易向自身傾斜，導致無法合理地為特征分配權重。其他的基于自表示性質的特征選擇方法均無法避免自表示性質的缺陷。為此，本文提出特征互表示性質，即高維數據中的每個特征可由除該特征之外的其他特征線性近似表示，而不是由全體特征線性近似表示，這克服了特征權重容易向自身傾斜的缺點。然后，基于特征互表示性質，提出一種新的正則化無監督特征選擇方法，該方法能夠有效提升數據聚類準確率，降低數據冗余率，并且計算復雜度較低。

1 特征互表示性質

假定X是數據矩陣，X∈Rm×n，m是樣本數量，n是特征數量，fi代表X的第i個特征，則X可以表示為特征的集合：X={f1，f2，…，fn}。

高維數據中的每個特征可以由數據中的其他特征線性近似表示，特征之間存在相關性，因此可以很好地互相近似表示，把高維數據所滿足的這一數學性質稱為特征互表示性質。利用特征互表示性質，數據矩陣X中的每一個特征fi可形式化表示為：

式中：wj是第j個特征的權重系數；ei為殘差向量，代表特征fi重構前后的殘差。本文期望重構后的特征可以很好地近似表示原特征，所以殘差應當盡可能小，使用向量的l2-范數的平方度量殘差大小，將損失函數定義為：

2 特征選擇模型及其優化算法

2.1 正則互表示無監督特征選擇模型

通過將X={f1，f2，…，fn}中的每一個特征進行重構，可得如下結果：

式中：Wo為權重矩陣，上標o是指權重矩陣W的對角線元素都為0，這是因為特征不參與自身的線性近似表示，所以權重系數為0；E為殘差矩陣，表示原始數據X重構前后的殘差。

從向量的角度分析，殘差矩陣E由殘差向量的有序集合{e1，e2，e3，…，en}組成，每個特征重構前后的殘差使用度量。將殘差度量標準由向量推廣到矩陣時，可以使用度量原始數據X重構前后的殘差大小。本文期望重構后的數據XWo能夠很好地近似表示原始數據X，因此殘差越小越好，對應的目標函數為：

目標函數式（3）的優化問題屬于無偏估計回歸問題，在無偏估計回歸問題中，當數據矩陣X不是列滿秩的，或者某些列之間線性相關性比較強時，得到的最優解將會不穩定。為了解決這個問題，在目標函數中加入一個正則項對權重矩陣的解空間進行約束，使計算出的最優解更穩定。基于上述分析，改進后的目標函數為：

本文把包含權重矩陣正則項的目標函數式（4）稱為正則互表示（Regularized Mutual Representation，RMR）無監督特征選擇模型。

2.2 分治-嶺回歸優化算法

針對提出的RMR 特征選擇模型，為之設計一種高效的優化算法，該算法結合了分治算法［14］和嶺回歸［15］優化算法，本文稱之為分治-嶺回歸優化算法。本節首先證明以下定理。

定理1給定如下兩個優化問題的目標函數：

其中：fi是X的第i列；是Wo的第i列。則整體優化問題的最優解可通過計算所有嶺回歸子優化問題的最優解得到。

證明 將數據矩陣X按列數分解為特征的有序集合{f1，f2，…，fn}，將權重矩陣按列數分解為權重向量的有序集合{ω1，ω2，…，ωn}，則有：

因為矩陣的Frobenius 范數的平方等于矩陣中所有列向量l2-范數平方的和，因此上式中可繼續變形為：

至此可知，只要使得分解后的每個嶺回歸子優化問題都取得最優解，即可保證整體優化問題取得最優解。

定理1證畢

分治-嶺回歸優化算法首先利用分治算法的思想，將整體優化問題分解為若干個子優化問題；然后針對每個子優化問題利用嶺回歸優化算法計算最優解；最后將各個子優化問題的最優解進行整合，得到整體優化問題的最優解。

分治-嶺回歸優化算法的具體計算步驟如下。

首先，將RMR 模型的整體優化問題按照數據矩陣X的每個特征，分解為如下的n個嶺回歸子優化問題：

式中：i=1，2，…，n。第i個子優化問題的最優解用于重構特征fi，使得重構前后的誤差最小的第i個元素為0，因為特征fi不參與自身的線性近似表示。

式（6）中的Xi是由X去掉特征fi得到，式（6）中的由式（5）中的ωi刪除第i個元素得到。目標函數式（6）的優化問題是嶺回歸優化問題，該優化問題的損失函數以及推導過程如下：

由于嶺回歸優化問題的損失函數是一個光滑的凸函數，因此可以在導數為0 處求得損失函數的最優解，即能夠使殘差L(ei)最小的解析解。最優解的推導過程如下：

令L(ei)對求偏導，得：

式中：I是單位矩陣；λ是正則項參數，且λ＞0。

總結上述分治-嶺回歸優化算法的具體計算步驟，得到RMR特征選擇方法的計算框架1。

輸入 數據集X，正則項參數λ，特征選擇數量k；

輸出 特征子集S。

3 實驗驗證與結果分析

3.1 實驗數據集

實驗中使用的數據集來源于UCI 標準數據集，共5 個數據集，關于這些數據集的詳細描述信息請參考表1。

表1 實驗數據集Tab.1 Experimental Datasets

表1中的Iris20 數據集為合成數據集，它是由UCI 標準數據集Iris 擴展而成，前4 列是Iris 數據集初始數據，后16 列數據是由前4 列進行隨機線性組合得到，線性組合系數和為1，并在后16列數據中加入高斯白噪聲。

3.2 評價指標

3.2.1 聚類準確率

使用K-Means 算法［16］對數據進行聚類，并計算數據樣本聚類之后的準確率，聚類準確率（ACCuracy of clustering，ACC）的值越大說明聚類結果越好。ACC計算公式如下：

式中：m是樣本個數；li是第i個樣本的實際標簽；map(ri)是第i個樣本的聚簇標簽，該函數使用Kuhn-Munkres 算法計算樣本的聚簇標簽；函數f(a，b)用于判斷標簽a和標簽b的值是否相等，若相等則函數值為1，不相等則函數值為0。

3.2.2 歸一化互信息

歸一化互信息（Normalized Mutual Information，NMI）是評價聚類結果好壞的常用指標之一，用于度量聚簇標簽向量與實際標簽向量的一致程度，NMI 值越大說明聚類結果越好。NMI計算公式如下：

式中：p是聚簇標簽向量；q是實際標簽向量；I(p，q)是向量p與q之間的互信息；H(p)和H(q)分別是p和q的信息熵。

3.2.3 冗余率

冗余率（Redundancy rate，Rr）用于度量數據的特征之間是否具有較強的相關性，相關性越強說明數據冗余程度越高，因此冗余率越小越好。Rr計算公式如下：

式中：S是特征子集；n是特征子集的特征數量；βi，j是特征fi和特征fj的皮爾遜相關系數。

3.3 實驗設置

為了驗證所提出的RMR 無監督特征選擇方法的有效性和高效性，實驗中使用另外四種無監督特征選擇方法用于對比，對比方法分別為經典的Laplacian 特征選擇方法［17］、使用了譜分析技術的非負判別特征選擇（Nonnegative Discriminative Feature Selection，NDFS）方法［18］、引入了正則約束的RSR 方法和自表示特征選擇（Self-Representation Feature Selection，SR_FS）方法［19］。

每種特征選擇方法從每個數據集中選出9 個不同維數的特征子集，選出特征數量依次是特征總數量的1/10，2/10，…，9/10，然后取這9 個不同維數的特征子集的聚類準確率平均值、歸一化互信息平均值以及冗余率平均值，作為評價該特征選擇方法效果優劣的三項指標。對于目標函數中有正則項的特征選擇方法，將正則項參數的值域設置為｛0.01，0.1，1，10，100｝，對每個正則項參數均進行實驗并選取最佳結果。

另外，針對聚類準確率這一評價指標，由于K-Means 聚類算法得出的聚類準確率會受初始質心選取的影響，為減少隨機誤差的影響，提升結果準確度，對每個特征子集進行100 次聚類，然后取100 次聚類準確率的平均值作為該特征子集的聚類準確率。

3.4 結果分析

首先，將本文提出的RMR 方法應用在Iris20 合成數據集上，因為Iris20 數據集的后16 列數據是由前4 列數據組合得到，且加入了一定的噪聲，因此后16 列數據是應當剔除的冗余特征，而前4 列數據為特征選擇方法應當識別出的重要特征。

圖1 是RMR 方法計算出的Iris20 特征權重直方圖，橫軸代表Iris20 數據集的20 個特征，縱軸代表計算出的各個特征的權重。權重越大，特征越重要，越具有代表性。從圖1 可以直觀地看出，前4個特征的權重明顯大于后16個特征的權重，這說明RMR 方法可以有效地識別出數據集中具有代表性的特征。從表2 的實驗結果數據可以得知，RMR 特征選擇方法與其他四種特征選擇方法相比，其在5 個標準數據集上選出的特征子集的平均聚類準確率最大，說明RMR 方法對聚類準確率的提升能力更強。從表3 的實驗結果數據可以看出，RMR 方法選出的特征子集的歸一化互信息NMI 值最大，說明RMR 方法選出的特征子集的聚類效果更好。無論是聚類準確率還是歸一化互信息，都是度量聚類結果好壞的常用指標，值越大越好。因此從表2 和表3 可以得出相同的結論，使用RMR 方法對原始數據集進行特征選擇，可以選出數據中的具有代表性的特征，有效地改善數據在聚類時的表現，并且同其他四種對比方法相比效果更好。

圖1 Iris20特征權重直方圖Fig.1 Histogram of feature weights of Iris20

表2 聚類準確率對比 單位：%Tab.2 Comparison of clustering accuracy unit：%

表3 歸一化互信息對比 單位：%Tab.3 Comparison of normalized mutual information unit：%

從表4中的實驗結果可知，RMR 方法與另外四種特征選擇方法相比，其所選出的特征子集的冗余率最低，說明RMR方法從原始數據中選出的特征相關性較弱，數據冗余程度更低。

表4 冗余率對比 單位：%Tab.4 Comparison of redundancy rate unit：%

RMR 方法選出的特征子集之所以具有較好的聚類表現和較低的冗余程度，是因為RMR 模型是基于正則互表示性質，利用了特征間的相關性，同時克服了特征權重容易向自身傾斜的缺點。RSR方法和SR_FS方法雖然利用了特征間的相關性，但是忽視了特征權重容易向自身傾斜的問題。NDFS方法結合譜聚類技術進行特征選擇，該方法的效果依賴于樣本相似性矩陣，容易受其影響。Laplacian 方法沒有考慮特征間的相關性，因此無法有效識別冗余特征。

在計算復雜度方面，RMR 數學模型中的誤差項和正則項都是使用矩陣Frobenius 范數進行約束，使用分治算法將矩陣優化問題轉換為若干個向量優化問題，如式（5）所示。此時的向量優化問題是嶺回歸優化問題，目標函數中的誤差項和正則項均由向量l2-范數約束，l2-正則是凸形正則，可以在導數為0處直接取得使殘差最小的解析解，如式（7）所示，式中：的計算復雜度是O(mn2)；求逆運算的復雜度是O(n3)；的復雜度是O(mn)；矩 陣與向量相乘的復雜度是O(n2)。考慮到樣本數量大于特征數量（即m＞n），所以單個嶺回歸優化的總體漸進復雜度為O(mn2)。因為整體優化問題被分解為n個嶺回歸子優化問題，所以RMR 方法的整體優化問題的漸進計算復雜度為O(mn3)。RMR 方法計算特征選擇模型最優解的過程僅相當于一次矩陣迭代運算，而非多次迭代，而NDFS 方法、RSR 方法以及SR_FS 方法都是采用矩陣多次迭代的方式逼近最優解，每一次迭代都會涉及大量的矩陣運算，計算復雜度與迭代次數成正比。因此，RMR 方法具有更低的計算復雜度，在計算性能上更具優勢。

4 結語

本文研究利用高維無標簽數據特征之間的相關性進行特征選擇，通過在特征選擇時對特征權重施加正則約束，提升了特征選擇結果的魯棒性，解決了特征權重分配不合理導致無法有效識別冗余特征的問題。實驗結果表明，RMR 方法能夠選出重要特征，減少數據冗余，提升聚類精度。算法理論復雜度分析表明，所提方法因使用分治-嶺回歸優化而具有較低的計算復雜度。RMR 方法也存在不足之處，其未考慮數據集的樣本數量少于特征數量的情況，未來研究可考慮高維小樣本數據情況下如何改進。