無監督特征選擇算法的分析與總結

郭雙樂 張建光 趙鑫 耿玉菊 石龍

摘要??? 高維無標記數據的出現不僅使數據處理的時間和空間復雜度增加，同時還會使訓練模型出現過擬合，因此對高維無標記數據降維變得越來越必要。特征選擇是數據降維的有效方法，本文給出了幾種具有代表性的無監督特征選擇方法，并指出了這些算法的優缺點，為進一步研究基于無監督的特征選擇提供了理論基礎。

【關鍵詞】降維 特征選擇 無監督

1 引言

在計算機視覺、多媒體分析等領域需要處理的數據往往具有很高的維數，對高維數據的處理增加了運算的時間和空間復雜度，同時也會導致學習模型的過擬合現象。流形學習的觀點認為由于數據內部特征的限制，一些高維數據會產生維度上的冗余，實際上這些數據只要使用比較低的維度就能唯一的表示。另外，并不是所有的特征都和學習任務相關。以上兩點說明對這些高維數據的降維成為必要和可能。

特征選擇是常用的一種降維方法，它通過一定的算法從特征集合中選擇出一組與分類有關的特征，使用選擇的特征來進行模型學習。該方法不改變數據的原始表示，并且當所選擇特征決定后，只要直接在原始特征集合里面對特征進行簡單的提取即可。

特征選擇方法按照訓練數據中是否存在分類信息可分為監督特征選擇方法和無監督特征選擇方法。在現實世界中存在大量的非標記數據，并且對數據進行標記需要付出昂貴的代價，所以對無監督特征選擇方法的研究具有很大的現實意義。本文主要針對無監督特征選擇方法進行探討。

2 無監督特征選擇

無監督特征選擇按照和學習算法的關系可分為有過濾式（Filter）、嵌入式（Embeded）和包裹式（wrapped）三大類，由于包裹式特征選擇方法的時間復雜度一般較高，所以我們只對其他兩種方法進行介紹。

2.1 過濾式

過濾式特征選擇方法獨立于具體的學習算法，它主要按照統計特性對特征的重要性進行排序，把重要性小的特征過濾掉，選擇重要性大的特征作為原始數據的表示。由于該方法獨立于具體的學習算法，所以其具有運算效率高的優點。

PCA得分法（PCAScore）和拉普拉斯得分法（LapScore）是常見的無監督的過濾式特征選擇方法。下面分別對這兩類算法給出簡單介紹。

PCA得分法對原始數據的每一維特征的方差進行排序，特征的方差越大對原始數據的表示能力越強，從而就被選擇出來。PCA得分法只用了數據的統計特性，而沒有考慮到數據的流形特性，在將所選特征應用到具體的學習算法時效果受到影響。

拉普拉斯得分法選擇最能夠保持原始數據流形的特征。該方法首先根據訓練數據建立關聯矩陣S，在S的基礎上建立對角矩陣D，其中D的對角元素Dii為S的第i行元素的和，根據S和D生成拉普拉斯矩陣L=D-S，每個特征的拉普拉斯得分計算如下：

基于流形的特征提取方法，首先都要計算關聯矩陣S。關聯矩陣的計算通常有如下三方法：

2.1.1 0-1權重

如果當第i個結點在第j個結點的p近鄰內則Sij=1，否則Sij=0。這種方法最簡單并且計算容易。

2.1.2 熱核權重

當第i個結點在第j個結點的p近鄰內則

基于流形的特征選擇方法很好的保持了數據的流形特性，所選特征應用到具體學習算法時，取得了較好的效果，但是存在如下問題，

（1）對某些特征來說，它們單獨和任務的相關性不是很大，但是它們的組合可能和任務的相關性很大，應用該方法進行特征選擇，可能會出現對這些類特征的遺漏;

（2）該方法沒考慮特征之間的相關性，從而造成了特征的冗余。

2.2 嵌入式

嵌入式特征選擇方法把一個具體的分類器看做是一個白盒子，把特征選擇融入分類模型，所以其分類效果通常要好，同時該類方法可以實現對多個特征的選擇。MCFS和TRACK等都屬于這類選擇算法。

MCFS首先計算出數據在嵌入空間中的表示，之后通過線性回歸的系數來確定各維特征的重要性。數據在嵌入空間中的表示是通過求解廣義特征問題Ly=λDy獲得的。令Y=[y1，...yk]，yk是最小的特征值對應的特征向量，K是嵌入空間的維數。

線性回歸的系數通過求解以下問題來得到：

對每一個特征通過MCFS得分來確定其重要性，MCFS得分由以下公式獲得：

該算法能夠有效的對多簇數據進行特征選擇。文獻[9]提出的TRACK算法是基于無監督跡比值和k均值來實現嵌入式特征選擇。TRACK算法的目標函數是：

其中，G是類指示矩陣，W為投影矩陣，X為樣本矩陣，St為總體散布矩陣。該目標函數使把跡比值和k均值有機統一在一起，選擇的特征具有很強的判別能力。

3 結論

在當今數據大爆發時代，大量高維無標記數據的出現，使數據處理面臨著極大的挑戰，所以非監督的特征選擇十分必要。本文對幾類非監督特征選擇做了介紹，并比較詳細的給出了過濾式和嵌入式兩類特征選擇方法中具有代表性的算法，同時指出了每種算法的優缺點，為進一步研究基于無監督的特征選擇提供了理論基礎。

參考文獻

[1]Li J， Cheng K， Wang S， et al. Feature selection： A data perspective[J]. ACM Computing Surveys （CSUR）， 2018， 50（6）： 94.

[2]Roweis S T， Saul L K. Nonlinear dimensionality reduction by locally linear embedding[J]. science， 2000， 290（5500）： 2323-2326.

[3]Li Z， Yang Y， Liu J， et al. Unsupervised feature selection using nonnegative spectral analysis[C]// Twenty-Sixth AAAI Conference on Artificial Intelligence. 2012.

[4]Hou C， Nie F， Li X， et al. Joint embedding learning and sparse regression： A framework for unsupervised feature selection[J]. IEEE Transactions on Cybernetics， 2014， 44（6）： 793-804.

[5]Qian M， Zhai C. Robust unsupervised feature selection[C]//Twenty-Third International Joint Conference on Artificial Intelligence. 2013.

[6]Cohen I， Xiang Q T， Sean Zhou X S， et al. Feature selection using principal feature analysis[J]. 2002.

[7]He X， Cai D， Niyogi P. Laplacian score for feature selection[C]// Advances in neural information processing systems. 2006： 507-514.

[8]Cai D， Zhang C， He X. Unsupervised feature selection for multi-cluster data[C]//Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM， 2010： 333-342.

[9]Wang D， Nie F， Huang H. Unsupervised feature selection via unified trace ratio formulation and k-means clustering （track）[C]//Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer， Berlin， Heidelberg， 2014： 306-321.