無監(jiān)督特征選擇算法的分析與總結(jié)

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

摘要??? 高維無標(biāo)記數(shù)據(jù)的出現(xiàn)不僅使數(shù)據(jù)處理的時(shí)間和空間復(fù)雜度增加，同時(shí)還會(huì)使訓(xùn)練模型出現(xiàn)過擬合，因此對高維無標(biāo)記數(shù)據(jù)降維變得越來越必要。特征選擇是數(shù)據(jù)降維的有效方法，本文給出了幾種具有代表性的無監(jiān)督特征選擇方法，并指出了這些算法的優(yōu)缺點(diǎn)，為進(jìn)一步研究基于無監(jiān)督的特征選擇提供了理論基礎(chǔ)。

【關(guān)鍵詞】降維 特征選擇 無監(jiān)督

1 引言

在計(jì)算機(jī)視覺、多媒體分析等領(lǐng)域需要處理的數(shù)據(jù)往往具有很高的維數(shù)，對高維數(shù)據(jù)的處理增加了運(yùn)算的時(shí)間和空間復(fù)雜度，同時(shí)也會(huì)導(dǎo)致學(xué)習(xí)模型的過擬合現(xiàn)象。流形學(xué)習(xí)的觀點(diǎn)認(rèn)為由于數(shù)據(jù)內(nèi)部特征的限制，一些高維數(shù)據(jù)會(huì)產(chǎn)生維度上的冗余，實(shí)際上這些數(shù)據(jù)只要使用比較低的維度就能唯一的表示。另外，并不是所有的特征都和學(xué)習(xí)任務(wù)相關(guān)。以上兩點(diǎn)說明對這些高維數(shù)據(jù)的降維成為必要和可能。

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

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

2 無監(jiān)督特征選擇

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

2.1 過濾式

過濾式特征選擇方法獨(dú)立于具體的學(xué)習(xí)算法，它主要按照統(tǒng)計(jì)特性對特征的重要性進(jìn)行排序，把重要性小的特征過濾掉，選擇重要性大的特征作為原始數(shù)據(jù)的表示。由于該方法獨(dú)立于具體的學(xué)習(xí)算法，所以其具有運(yùn)算效率高的優(yōu)點(diǎn)。

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

PCA得分法對原始數(shù)據(jù)的每一維特征的方差進(jìn)行排序，特征的方差越大對原始數(shù)據(jù)的表示能力越強(qiáng)，從而就被選擇出來。PCA得分法只用了數(shù)據(jù)的統(tǒng)計(jì)特性，而沒有考慮到數(shù)據(jù)的流形特性，在將所選特征應(yīng)用到具體的學(xué)習(xí)算法時(shí)效果受到影響。

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

基于流形的特征提取方法，首先都要計(jì)算關(guān)聯(lián)矩陣S。關(guān)聯(lián)矩陣的計(jì)算通常有如下三方法：

2.1.1 0-1權(quán)重

如果當(dāng)?shù)趇個(gè)結(jié)點(diǎn)在第j個(gè)結(jié)點(diǎn)的p近鄰內(nèi)則Sij=1，否則Sij=0。這種方法最簡單并且計(jì)算容易。

2.1.2 熱核權(quán)重

當(dāng)?shù)趇個(gè)結(jié)點(diǎn)在第j個(gè)結(jié)點(diǎn)的p近鄰內(nèi)則

基于流形的特征選擇方法很好的保持了數(shù)據(jù)的流形特性，所選特征應(yīng)用到具體學(xué)習(xí)算法時(shí)，取得了較好的效果，但是存在如下問題，

（1）對某些特征來說，它們單獨(dú)和任務(wù)的相關(guān)性不是很大，但是它們的組合可能和任務(wù)的相關(guān)性很大，應(yīng)用該方法進(jìn)行特征選擇，可能會(huì)出現(xiàn)對這些類特征的遺漏;

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

2.2 嵌入式

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

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

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

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

該算法能夠有效的對多簇?cái)?shù)據(jù)進(jìn)行特征選擇。文獻(xiàn)[9]提出的TRACK算法是基于無監(jiān)督跡比值和k均值來實(shí)現(xiàn)嵌入式特征選擇。TRACK算法的目標(biāo)函數(shù)是：

其中，G是類指示矩陣，W為投影矩陣，X為樣本矩陣，St為總體散布矩陣。該目標(biāo)函數(shù)使把跡比值和k均值有機(jī)統(tǒng)一在一起，選擇的特征具有很強(qiáng)的判別能力。

3 結(jié)論

在當(dāng)今數(shù)據(jù)大爆發(fā)時(shí)代，大量高維無標(biāo)記數(shù)據(jù)的出現(xiàn)，使數(shù)據(jù)處理面臨著極大的挑戰(zhàn)，所以非監(jiān)督的特征選擇十分必要。本文對幾類非監(jiān)督特征選擇做了介紹，并比較詳細(xì)的給出了過濾式和嵌入式兩類特征選擇方法中具有代表性的算法，同時(shí)指出了每種算法的優(yōu)缺點(diǎn)，為進(jìn)一步研究基于無監(jiān)督的特征選擇提供了理論基礎(chǔ)。

參考文獻(xiàn)

[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.