郭雙樂 張建光 趙鑫 耿玉菊 石龍
摘要??? 高維無標(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.