周紅標，喬俊飛

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

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

周紅標1,2,3，喬俊飛1,2

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

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

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

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

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

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

1 互信息理論

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

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

根據(jù)信息論的有關理論[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構成的空間中對于給定的N個樣本首先找出它的k個近鄰，再找出其他樣本分別在X和Y方向到當前樣本的距離小于當前樣本到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ù)信息論知識，增加相關特征，能更好表征輸出特征?；诟呔Sk-近鄰互信息特征選擇的基本思想為，首先利用前向累加搜索策略找出由強相關特征和弱相關特征組成的相關特征候選子集，然后采用后向交叉搜索策略剔除候選子集中的冗余特征，最終形成最優(yōu)強相關特征子集。具體的流程如下。

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

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

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

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

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

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

3 仿真實驗

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

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

Friedman由式(13)描述：

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

利用本文方法進行特征選擇，第1步得到的互信息如圖1所示，可見僅依靠一維互信息會誤選x11，誤剔除x3和x5；第2步得到的高維互信息如圖2所示，設定無關變量個數(shù)為5，則剔除x6～x10得到最優(yōu)相關特征子集為x1～x5、x11和x12；第3步得到的互信息如圖3所示，確定x1、x11和x2、x12中存在冗余特征，再結合一維互信息值，可以判定x11和x12為冗余特征，剔除后得到最優(yōu)強相關特征子集為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)絡對Friedman數(shù)據(jù)進行測試，隨機產生240個帶噪聲數(shù)據(jù)作訓練樣本，1 000個不含噪聲數(shù)據(jù)作測試樣本，變量選擇及網(wǎng)絡測試結果如表1所示。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

方法特征選擇結果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ù)預測結果和預測誤差?？梢姡ㄟ^kNN-FABC方法選出的特征能夠很好地表征原始數(shù)據(jù)，建模誤差主要集中在-0.3～0.3 mg/L之間，能夠較好地滿足污水處理廠對總磷檢測精度的要求。

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

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

4 結束語

通過將數(shù)據(jù)驅動型k-近鄰方法擴展用于多維特征之間相關性計算，結合前向累加策略，能夠較為準確地獲得全部特征的最優(yōu)排序，進而剔除無關特征，再結合后向交叉策略，能夠定位并刪除冗余特征，最終得到最優(yōu)強相關特征子集。Friedman、Housing和實際污水處理出水TP預測實驗證實了本文方法的有效性。下一步的研究工作是實現(xià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]韓敏, 劉曉欣. 基于互信息的分步式輸入變量選擇多元序列預測研究[J]. 自動化學報, 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神經網(wǎng)絡的TBM主軸承載荷譜預測[J]. 哈爾濱工程大學學報, 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]喬俊飛, 周紅標. 基于自組織模糊神經網(wǎng)絡的出水總磷預測[J]. 控制理論與應用, 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.

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

喬俊飛，男，1968年生，教授，博士生導師，國家杰出青年基金獲得者，教育部長江學者特聘教授，教育部新世紀優(yōu)秀人才，主要研究方向為污水處理過程智能優(yōu)化控制。獲教育部科技進步獎一等獎和北京市科學進步獎三等獎各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

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

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

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

日期：2017-03-17.

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

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