基于高維k-近鄰互信息的特征選擇方法

周紅標(biāo)，喬俊飛

(1.北京工業(yè)大學(xué) 信息學(xué)部，北京 100124； 2. 計算智能和智能系統(tǒng)北京市重點實驗室，北京 100124； 3.淮陰工學(xué)院 自動化學(xué)院，江蘇 淮安 223003)

基于高維k-近鄰互信息的特征選擇方法

周紅標(biāo)1,2,3，喬俊飛1,2

(1.北京工業(yè)大學(xué) 信息學(xué)部，北京 100124； 2. 計算智能和智能系統(tǒng)北京市重點實驗室，北京 100124； 3.淮陰工學(xué)院 自動化學(xué)院，江蘇 淮安 223003)

針對多元序列預(yù)測建模過程中特征選擇問題，提出了一種基于數(shù)據(jù)驅(qū)動型高維k-近鄰互信息的特征選擇方法。該方法首先將數(shù)據(jù)驅(qū)動型k-近鄰法擴展用于高維特征變量之間互信息的估計，然后采用前向累加策略給出全部特征最優(yōu)排序，根據(jù)預(yù)設(shè)無關(guān)特征個數(shù)剔除無關(guān)特征，再利用后向交叉策略找出并剔除冗余特征，最終得到最優(yōu)強相關(guān)特征子集。以Friedman數(shù)據(jù)、Housing數(shù)據(jù)和實際污水處理出水總磷預(yù)測數(shù)據(jù)為例，采用多層感知器神經(jīng)網(wǎng)絡(luò)預(yù)測模型進行仿真實驗，驗證了所提方法的有效性。

特征選擇；互信息；k-近鄰；高維互信息；多層感知器

通過特征選擇實現(xiàn)數(shù)據(jù)降維，構(gòu)建結(jié)構(gòu)精簡的辨識模型，能夠有效避免輸入特征太多造成“維數(shù)災(zāi)難”以及給學(xué)習(xí)模型帶來“過擬合”等問題[1-3]。目前，特征選擇的方法主要有偏最小二乘回歸(partial least squares regression, PLSR)[4]、灰色關(guān)聯(lián)分析(grey relational analysis, GRA)[5]和互信息(mutual information, MI)[6-7]等。MI對樣本的分布類型無特別要求，可有效捕捉特征間的非線性關(guān)系，特別適合多元序列特征選擇問題。

互信息是一種衡量兩個隨機變量之間相互依賴強弱程度的準(zhǔn)則，其來源于信息論中熵的概念[8]。采用互信息進行特征選擇主要有以下兩個難點:1)特征評價策略；2)互信息的準(zhǔn)確估計。針對評價策略，Battiti等[9]提出了MIFS(mutual information feature selection)方法，通過平衡相關(guān)特征和冗余特征的選擇，取得了較好的效果，此后，Peng等[10]、Fleuret[11]、Yang等[12]、Brown[13]和韓等[14]都分別提出了各自的評價策略。上述方法主要是采用一維互信息來衡量特征好壞，當(dāng)存在冗余特征時，并不能保證得到最優(yōu)特征子集?；バ畔⒌墓烙嬕话阃ㄟ^非參數(shù)方式[15-16]求解概率密度函數(shù)來實現(xiàn)，主要有直方圖法和核函數(shù)法。近幾年發(fā)展的k-近鄰法(k-nearest neighbors, kNN)[17-18]構(gòu)建的數(shù)據(jù)驅(qū)動型特征選擇框架，無需假設(shè)概率密度函數(shù)形式，避免了對概率密度函數(shù)的估計，其基礎(chǔ)理論完備，非常適合具有非線性不規(guī)則分布特點的實際數(shù)據(jù)，但是高維k-近鄰互信息的估計存在一定困難。

因此，本文在k-近鄰互信息基礎(chǔ)上將其擴展用于高維互信息的估計，然后采用前向累加后向交叉(forward accumulation and backward cross, FABC)的最優(yōu)特征子集選擇策略，構(gòu)建kNN-FABC的特征選擇方法，最后以Friedman數(shù)據(jù)、Housing數(shù)據(jù)和實際污水處理出水總磷預(yù)測數(shù)據(jù)為例進行仿真實驗，并結(jié)合多層感知器(multilayer perceptron, MLP)預(yù)測模型來驗證所提特征選擇方法的有效性。

1 互信息理論

互信息是一種衡量兩個隨機變量之間相互依賴強弱程度的準(zhǔn)則，其來源于信息論中熵的概念。兩個隨機變量之間的互信息越大，則兩者之間的相關(guān)性就越強[17]。

對隨機變量X和Y來說，設(shè)其聯(lián)合概率密度函數(shù)為ρX,Y(x,y)，則其邊緣概率密度函數(shù)為

根據(jù)信息論的有關(guān)理論[17]，隨機變量X和Y之間的互信息定義為

式中S為X和Y的定義域。

根據(jù)Shannon熵的定義[17]，X、Y的熵和聯(lián)合熵分別為

根據(jù)式(4)、(5)和(6)，式(3)還可以表示為

2 高維k-近鄰互信息理論

2.1 高維k-近鄰互信息的估計

Kraskov等[17-18]提出的k-近鄰法通過數(shù)據(jù)直接近似估計特征的互信息，避免了對概率密度分布的近似估計。其基本思想是，在由隨機變量X和Y構(gòu)成的空間中對于給定的N個樣本首先找出它的k個近鄰，再找出其他樣本分別在X和Y方向到當(dāng)前樣本的距離小于當(dāng)前樣本到k個近鄰距離的最大值的數(shù)目，通過統(tǒng)計數(shù)目從而進行互信息的估計。

現(xiàn)將其擴展到高維互信息的估計，高維互信息計算的具體思路如下[18]：

給定N個樣本z(i)=[(x(i))T(y(i))T]T(i=1,2,…,N)，其中x(i)∈d且y(i)∈p。如果z和z′為數(shù)據(jù)集中兩個不同的向量，則

式中‖·‖表示取最大范數(shù)。

若z(i)的k-近鄰為z(k(i))=[(x(k(i)))T(y(k(i)))T]T，則z(i)與z(k(i))之間的Euclidean距離為

ε(i)=‖z(i)-z(k(i))‖=

對于z(i)中的分量x(i)和y(i)有

2.2 高維k-近鄰互信息特征選擇流程

由于輸入特征之間并非互相獨立，存在非線性耦合，同時根據(jù)信息論知識，增加相關(guān)特征，能更好表征輸出特征?；诟呔Sk-近鄰互信息特征選擇的基本思想為，首先利用前向累加搜索策略找出由強相關(guān)特征和弱相關(guān)特征組成的相關(guān)特征候選子集，然后采用后向交叉搜索策略剔除候選子集中的冗余特征，最終形成最優(yōu)強相關(guān)特征子集。具體的流程如下。

1)參數(shù)初始化，設(shè)置k值和無關(guān)特征個數(shù)。

2)根據(jù)式(12)計算輸入特征X的每一維分量與輸出特征Y之間的一維互信息，提取出互信息最大值對應(yīng)的特征，作為第1個相關(guān)特征。

3)在2)得到的特征基礎(chǔ)上，利用式(12)計算其他輸入特征與輸出特征Y之間的高維互信息，找出第2個相關(guān)特征。

4)重復(fù)2)～3)，直至所有特征處理完畢，得到全部特征變量的排序，根據(jù)預(yù)設(shè)無關(guān)特征個數(shù)，剔除無關(guān)特征，得到相關(guān)特征子集。

5)根據(jù)相關(guān)特征子集，計算兩兩之間的互信息，找出互信息最大值對應(yīng)的特征組。

6)結(jié)合2)的一維互信息值，剔除冗余特征，最終得到最優(yōu)強相關(guān)特征子集。

3 仿真實驗

為了驗證本文特征選擇方法的有效性，本文分別采用標(biāo)準(zhǔn)Friedman函數(shù)數(shù)據(jù)和實際污水處理出水總磷預(yù)測數(shù)據(jù)進行特征選擇的實驗分析，并與PLSR、MRMR和JMI等方法進行比較，最后利用MLP預(yù)測模型[19]進行誤差分析。實驗時，k設(shè)置為5，MLP預(yù)測模型的隱含層節(jié)點取20個，迭代次數(shù)為20 000次，學(xué)習(xí)率η取為0.001。由于神經(jīng)網(wǎng)絡(luò)建模受初值影響具有隨機性，本文實驗結(jié)果為運行30次取平均值和標(biāo)準(zhǔn)差。

3.1 Friedman數(shù)據(jù)

Friedman由式(13)描述：

式中：x1～x10服從[0,1]的均勻分布，x11=0.5x1+ε，x12=0.5x2+ε。隨機產(chǎn)生500個含高斯噪聲數(shù)據(jù)作樣本，且高斯噪聲ε滿足N(0,0.1)。由式(13)可知，Y只與x1～x5有關(guān)，x6～x10是無關(guān)特征，x11和x12屬于冗余特征。

利用本文方法進行特征選擇，第1步得到的互信息如圖1所示，可見僅依靠一維互信息會誤選x11，誤剔除x3和x5；第2步得到的高維互信息如圖2所示，設(shè)定無關(guān)變量個數(shù)為5，則剔除x6～x10得到最優(yōu)相關(guān)特征子集為x1～x5、x11和x12；第3步得到的互信息如圖3所示，確定x1、x11和x2、x12中存在冗余特征，再結(jié)合一維互信息值，可以判定x11和x12為冗余特征，剔除后得到最優(yōu)強相關(guān)特征子集為x1～x5，完全與式(13)特征屬性相吻合。

圖1 一維互信息圖Fig.1 One-dimensional mutual information

注：+x2表示求取I(x4,x2;Y)；+x12表示求取I(x4,x2,x12;Y)；其余類似。圖2 FA策略高維互信息圖Fig.2 High-dimensional mutual information under FA

圖3 BC策略互信息圖Fig.3 Mutual information under BC

利用本文特征選擇方法，并利用MLP網(wǎng)絡(luò)對Friedman數(shù)據(jù)進行測試，隨機產(chǎn)生240個帶噪聲數(shù)據(jù)作訓(xùn)練樣本，1 000個不含噪聲數(shù)據(jù)作測試樣本，變量選擇及網(wǎng)絡(luò)測試結(jié)果如表1所示。

表1 Friedman數(shù)據(jù)特征選擇及測試結(jié)果

注： ALL 表示選取全部特征。

由表1可知， kNN-FABC方法和文獻[17]的STEP方法都成功篩選出全部僅有的5個相關(guān)特征，MRMR、CMIM和MIFS誤剔相關(guān)特征x3、誤選無關(guān)特征x6，JMI和MMI誤剔相關(guān)特征x3、誤選冗余特征x12，PLSR誤選冗余特征x11和x12。同時，kNN-FABC方法的RMSE均值和標(biāo)準(zhǔn)差都要遠小于其他方法，表明其極大地提高了網(wǎng)絡(luò)泛化能力。

3.2 Housing數(shù)據(jù)

Housing數(shù)據(jù)由13個房屋屬性的輸入特征和1個房屋價格的輸出特征組成，共有506組樣本。隨機選擇338組作訓(xùn)練樣本，剩余168組作測試樣本。利用本文方法進行特征選擇，并與其他文獻特征選擇結(jié)果進行了比較，特征選擇及MLP網(wǎng)絡(luò)測試結(jié)果如表2所示。

表2 Housing數(shù)據(jù)特征選擇及測試結(jié)果

注：ALL表示選取全部特征。

由表2可知，在歸一化方法、MLP模型參數(shù)選取一致的情況下，kNN-FABC的 RMSE均值和標(biāo)準(zhǔn)差均表明了采用本文方法所選特征建立的預(yù)測模型精度更高。

3.3 污水處理出水總磷預(yù)測數(shù)據(jù)

近年來，總磷(total phosphorus, TP)污染問題開始凸顯。研究表明，水體富營養(yǎng)化程度與總磷等指標(biāo)密切相關(guān)。因此加強對TP的檢測有助于解決水體富營養(yǎng)化問題[20]。目前，污水處理廠普遍采用的生化方法成本高、耗時長，在線檢測儀表對檢測環(huán)境要求高并且維護成本昂貴，而基于數(shù)據(jù)驅(qū)動的軟測量技術(shù)能夠在線、快速、準(zhǔn)確預(yù)測，受到研究者青睞。但是污水處理生化反應(yīng)過程中可測變量較多，在建立TP軟測量模型時，若選取全部可用特征，則會產(chǎn)生冗余，降低網(wǎng)絡(luò)泛化能力，同時也大幅增加檢測成本，故對TP預(yù)測模型進行輸入特征選擇具有重要意義。污水處理生化反應(yīng)過程中可測變量及其意義如表3所示。本文采用kNN-FABC方法實現(xiàn)對TP預(yù)測特征變量的選擇。

從北京市某污水處理廠獲取了2015年6～8月共492組數(shù)據(jù)，首先剔除明顯異常值，然后采用小波包(sym8小波、2層分解、軟閾值方式)進行降噪處理，處理效果見圖4。

從原始數(shù)據(jù)集中每隔3個樣本選取1個樣本共123個組成測試集，其余369個作為訓(xùn)練集。TP數(shù)據(jù)特征選擇及MLP網(wǎng)絡(luò)測試結(jié)果如表4所示。相比PLSR，kNN-FABC獲得了較少的特征、較低的RMSE及其標(biāo)準(zhǔn)差，尋找到了最有效的特征子集，構(gòu)建了更穩(wěn)定的軟測量模型，驗證了kNN-FABC方法在特征選擇上的有效性。

(a)原始TP數(shù)據(jù)

(b)小波包去噪TP數(shù)據(jù)圖4 出水TP數(shù)據(jù)小波包去噪Fig.4 Wavelet packet denoising for TP

方法特征選擇結(jié)果RMSEALLx1～x90．428±0．077ERRx3，x4，x8，x90．519±0．071PLSRx3，x5，x2，x1，x60．464±0．033kNN-FABCx7，x1，x2，x60．159±0．004

注： ERR為隨機選取特征，作對比。

圖5和圖6分別給出了MLP模型對TP數(shù)據(jù)預(yù)測結(jié)果和預(yù)測誤差。可見，通過kNN-FABC方法選出的特征能夠很好地表征原始數(shù)據(jù)，建模誤差主要集中在-0.3～0.3 mg/L之間，能夠較好地滿足污水處理廠對總磷檢測精度的要求。

圖5 TP數(shù)據(jù)MLP預(yù)測結(jié)果Fig.5 Predicted output using MLP for TP

圖6 TP數(shù)據(jù)MLP預(yù)測誤差Fig.6 Predicted error using MLP for TP

4 結(jié)束語

通過將數(shù)據(jù)驅(qū)動型k-近鄰方法擴展用于多維特征之間相關(guān)性計算，結(jié)合前向累加策略，能夠較為準(zhǔn)確地獲得全部特征的最優(yōu)排序，進而剔除無關(guān)特征，再結(jié)合后向交叉策略，能夠定位并刪除冗余特征，最終得到最優(yōu)強相關(guān)特征子集。Friedman、Housing和實際污水處理出水TP預(yù)測實驗證實了本文方法的有效性。下一步的研究工作是實現(xiàn)無關(guān)特征的自動判定，避免人為設(shè)置帶來的無關(guān)特征誤剔的可能。

[1]OSELEDETS I V, TYRTYSHNIKOV E E. Breaking the curse of dimensionality, or how to use SVD in many dimensions[J]. SIAM journal on scientific computing, 2009, 31(5): 3744-3759.

[2]GHAMISI P, BENEDIKTSSON J A. Feature selection based on hybridization of genetic algorithm and particle swarm optimization[J]. IEEE geoscience and remote sensing letters, 2015, 12(2): 309-313.

[3]RAUBER T W, ASSIS BOLDT de F, VAREJO F M. Heterogeneous feature models and feature selection applied to bearing fault diagnosis[J]. IEEE transactions on industrial electronics, 2015, 62(1): 637-646.

[4]WOLD S, SJ?STR?M M, ERIKSSON L. PLS-regression: a basic tool of chemometrics[J]. Chemometrics and intelligent laboratory systems, 2001, 58(2): 109-130.

[5]SONG Q, SHEPPERD M. Predicting software project effort: a grey relational analysis based method[J]. Expert systems with applications, 2011, 38(6): 7302-7316.

[6]FENG J, JIAO L, LIU F, et al. Mutual-information-based semi-supervised hyperspectral band selection with high discrimination, high information, and low redundancy[J]. IEEE transactions on geoscience and remote sensing, 2015, 53(5): 2956-2969.

[7]BENNASAR M, HICKS Y, SETCHI R. Feature selection using joint mutual information maximisation[J]. Expert systems with applications, 2015, 42(22): 8520-8532.

[8]SHANNON C E. A mathematical theory of communication[J]. ACM sigmobile mobile computing and communications review, 2001, 5(1): 3-55.

[9]BATTITI R. Using mutual information for selecting features in supervised neural net learning[J]. IEEE transactions on neural networks, 1994, 5(4): 537-550.

[10]PENG H, LONG F, DING C. Feature selection based on mutual information criteria of max-dependency, max-relevance, and min-redundancy[J]. IEEE transactions on pattern analysis and machine intelligence, 2005, 27(8): 1226-1238.

[11]FLEURET F. Fast binary feature selection with conditional mutual information[J]. Journal of machine learning research, 2004, 5: 1531-1555.

[12]YANG H H, MOODY J E. Data visualization and feature selection: new algorithms for nongaussian data[C]//Advances in Neural Information Processing Systems. Cambridge,Britain, 1999: 687-693.

[13]BROWN G. A new perspective for information theoretic feature selection[C]//Proceedings of the 12th International Conference on Artificial Intelligence and Statistics. Florida, USA, 2009: 49-56.

[14]韓敏, 劉曉欣. 基于互信息的分步式輸入變量選擇多元序列預(yù)測研究[J]. 自動化學(xué)報, 2012, 38(6): 999-1005.

HAN Min, LIU Xiaoxin. Stepwise input variable selection based on mutual information for multivariate forecasting[J]. ACTA automatica sinica, 2012, 38(6): 999-1005.

[15]BEIRLANT J, DUDEWICZ E J, GY?RFI L, et al. Nonparametric entropy estimation: an overview[J]. International journal of mathematical and statistical sciences, 1997, 6(1): 17-39.

[16]MOON Y I, RAJAGOPALAN B, LALL U. Estimation of mutual information using kernel density estimators[J]. Physical review E, 1995, 52(3): 2318-2321.

[17]KRASKOV A, ST?GBAUER H, GRASSBERGER P. Estimating

mutual information[J]. Physical review E, 2004, 69(6): 1-16.

[18]ST?GBAUER H, KRASKOV A, ASTAKHOV S A, et al. Least-pendent-component analysis based on mutual information[J]. Physical review E, 2004, 70(6): 1-17.

[19]霍軍周, 王亞杰, 歐陽湘宇, 等. 基于BP神經(jīng)網(wǎng)絡(luò)的TBM主軸承載荷譜預(yù)測[J]. 哈爾濱工程大學(xué)學(xué)報, 2015, 36(7): 965-969.

HUO Junzhou, WANG Yajie, OUYANG Xiangyu, et al.Load spectrum prediction of the main drive bearing of a tunnel boring machine based on BP neural networks[J]. Journal of Harbin Engineering University, 2015, 36(7): 965-969.

[20]喬俊飛, 周紅標(biāo). 基于自組織模糊神經(jīng)網(wǎng)絡(luò)的出水總磷預(yù)測[J]. 控制理論與應(yīng)用, 2017, 34(2): 224-232.

QIAO Junfei, ZHOU Hongbiao. Prediction of effluent total phosphorus based on self-organizing fuzzy neural network[J]. Control theory and applications, 2017, 34(2): 224-232.

周紅標(biāo)，男，1980年生，講師，博士研究生，主要研究方向為神經(jīng)網(wǎng)絡(luò)分析與設(shè)計。發(fā)表論文十余篇，其中被EI檢索6篇。

喬俊飛，男，1968年生，教授，博士生導(dǎo)師，國家杰出青年基金獲得者，教育部長江學(xué)者特聘教授，教育部新世紀(jì)優(yōu)秀人才，主要研究方向為污水處理過程智能優(yōu)化控制。獲教育部科技進步獎一等獎和北京市科學(xué)進步獎三等獎各1項，發(fā)表論文近100篇，其中被SCI收錄18篇，EI收錄60篇，獲發(fā)明專利20項。

Featureselectionmethodbasedonhighdimensionalk-nearestneighborsmutualinformation

ZHOU Hongbiao1,2,3， QIAO Junfei1,2

(1.Faculty of Information Technology, Beijing University of Technology, Beijing 100124, China;2. Beijing Key Laboratory of Computational Intelligence and Intelligent System, Beijing 100124, China;3. Faculty of Automation, Huaiyin Institute of Technology, Huai’an 223003, China)

Feature selection plays an important role in the modeling and forecast of multivariate series. In this paper, we propose a feature selection method based on data-driven high-dimensionalk-nearest neighbor mutual information. First, this method extends thek-nearest neighbor method to estimate the amount of mutual information among high-dimensional feature variables. Next, optimal sorting of all these features is achieved by adopting a forward accumulation strategy in which irrelevant features are eliminated according to a preset number. Then, redundant features are located and removed using a backward cross strategy. Lastly, this method obtains optimal subsets that feature a strong correlation. Using Friedman data, housing data, and actual effluent total-phosphorus forecast data from wastewater treatment plant as examples, we performed a simulation experiment by adopting a neural network forecast model with multilayer perception. The simulation results demonstrate the feasibility of the proposed method.

feature selection; mutual information;k-nearest neighbor; high-dimensional mutual information; multilayer perceptron

10.11992/tis.201609020

http://kns.cnki.net/kcms/detail/23.1538.TP.20170317.1937.006.html

TP183

A

1673-4785(2017)05-0595-06

中文引用格式：周紅標(biāo)，喬俊飛.基于高維k-近鄰互信息的特征選擇方法J.智能系統(tǒng)學(xué)報， 2017, 12(5): 595-600.

英文引用格式：ZHOUHongbiao，QIAOJunfei.Featureselectionmethodbasedonhighdimensionalk-nearestneighborsmutualinformationJ.CAAItransactionsonintelligentsystems, 2017, 12(5): 595-600.

2016-09-21. < class="emphasis_bold">網(wǎng)絡(luò)出版日期

日期：2017-03-17.

國家自然科學(xué)基金重點項目(61533002)；國家杰出青年科學(xué)基金項目(61225016).

喬俊飛. E-mail:hyitzhb@163.com.