翟東昌，陳紅梅

（1.西南交通大學(xué)唐山研究院，河北唐山 063000；2.西南交通大學(xué)計(jì)算機(jī)與人工智能學(xué)院，成都 611756）

0 引言

隨著遙感技術(shù)的發(fā)展，成像光譜儀發(fā)射的數(shù)百個(gè)連續(xù)窄波可以探測(cè)到地物目標(biāo)豐富的光譜和空間信息，這些獲取的信息經(jīng)過成像處理后稱為高光譜圖像。近些年，高光譜圖像廣泛地應(yīng)用到了多個(gè)領(lǐng)域，主要包括地質(zhì)勘探［1］、農(nóng)業(yè)［1-2］，以及醫(yī)療行業(yè)［1-3］等。

高光譜圖像包含了二維的空間信息，以及一維的光譜信息，所以高光譜圖像的數(shù)據(jù)可以通過一個(gè)三維的圖像立方體呈現(xiàn)。然而高精度傳感器可以采集到高分辨率的空間信息，連續(xù)的數(shù)百個(gè)探測(cè)波段也使得圖像中每個(gè)像素點(diǎn)都包含了大量的光譜信息。根據(jù)美國(guó)國(guó)家航空航天局（National Aeronautics and Space Administration，NASA）噴氣推進(jìn)實(shí)驗(yàn)室的數(shù)據(jù)，高光譜紅外成像設(shè)備發(fā)送的平均數(shù)據(jù)量在65 Mb/s［4］。這使得數(shù)據(jù)處理過程中的時(shí)間成本增加，對(duì)硬件的要求也在提升，同時(shí)也會(huì)引發(fā)Hughes 現(xiàn)象［5］和Bellman 維度的詛咒［6］。

此外，高光譜圖像從光譜信息的維度來看，可以將波段作為一個(gè)維度對(duì)空間信息進(jìn)行描述，是不同波段探測(cè)灰度值的疊加。對(duì)于探測(cè)、分類等相關(guān)任務(wù)，要鑒別的物質(zhì)只對(duì)部分波段進(jìn)行吸收和折射，這使得光譜信息中包含了大量冗余、噪聲信息，全波段在實(shí)際應(yīng)用中的性能也較差。因此對(duì)高光譜數(shù)據(jù)集進(jìn)行降維處理，降低數(shù)據(jù)間的冗余度，提高數(shù)據(jù)的可用性，是數(shù)據(jù)預(yù)處理中的重要環(huán)節(jié)。

對(duì)高光譜圖像進(jìn)行降維處理的方式主要包括了波段選擇以及特征提取。特征提取按照算法中的標(biāo)準(zhǔn)將原始數(shù)據(jù)映射到另一個(gè)特征空間［7-8］。大部分特征提取算法將原始波段進(jìn)行了線性組合，如果采用的算法指標(biāo)不合適，可能導(dǎo)致計(jì)算結(jié)果更加復(fù)雜［9］；波段選擇算法，也稱為特征選擇算法，從原始波段中選取波段子集，并保留了光譜通道的原始光譜信息。

基于數(shù)據(jù)提供的不同的先驗(yàn)知識(shí)，研究學(xué)者提出了很多波段選擇算法。根據(jù)是否采用數(shù)據(jù)的類標(biāo)，波段選擇算法通?？梢苑譃槿N：有監(jiān)督的、半監(jiān)督的和無監(jiān)督的方法［10］?？紤]是否采用分類器，波段選擇算法還可以分為：包裹式方法，即采用可預(yù)測(cè)的模型及其泛化性能對(duì)特征進(jìn)行排序［11］；嵌入式方法，在模型構(gòu)建的過程中選取最相關(guān)的特征［12］；過濾式方法，通過引入其他評(píng)判標(biāo)準(zhǔn)來取代分類器準(zhǔn)確率，對(duì)特征進(jìn)行排序及篩選。

相較于包裹式算法，過濾式算法不用考慮分類器對(duì)特征選取的影響，所以通常會(huì)比包裹式算法更為高效，這使得此類算法在高維數(shù)據(jù)集中的性能會(huì)更好。要獲取特征的相關(guān)性程度，常用的評(píng)判標(biāo)準(zhǔn)有基于皮爾森相關(guān)系數(shù)的方法［13］；基于統(tǒng)計(jì)檢驗(yàn)的方法，如t-檢驗(yàn)［14］；基于Fisher 線性判別的方法［15］；基于最近鄰類別的方法［16］；基于互信息（Mutual Information，MI）的方法［17］等。

基于相關(guān)性系數(shù)的方法對(duì)線性特征非常有效，但是對(duì)于非線性特征之間的關(guān)系無法有效度量；基于統(tǒng)計(jì)檢驗(yàn)的方法以及基于Fisher 線性判別的方法需要特征集合的數(shù)據(jù)服從正態(tài)分布；在Guo 等［18］的研究中，基于MI 的方法可以度量任意隨機(jī)變量之間的信息量，所以適用于復(fù)雜分類任務(wù)中特征相關(guān)性的計(jì)算。此外，基于MI 的特征選擇算法不依賴機(jī)器學(xué)習(xí)模型以及特定基準(zhǔn)的選取。研究學(xué)者利用圖像的空間信息［19］，將樣本像素值之間的極差作為權(quán)重方程，與MI 結(jié)合，其中極差之和可以作為另一種相似度的度量?；蛘咴贚iu 等［20］的研究中，將MI 與粗糙集理論相結(jié)合，采用MI 的思想計(jì)算鄰域MI，并通過粗糙集理論的重要度進(jìn)行波段選取工作。

本文引入了一種基于MI 的度量方式，稱為鄰域熵（Neighborhood Entropy，NE），用于度量多個(gè)特征之間的MI，并且克服了傳統(tǒng)MI 方法需要一對(duì)特征變量進(jìn)行計(jì)算的缺陷。此外，高光譜圖像數(shù)據(jù)集的特征值為實(shí)數(shù)，近似搜索算法有效地減少了計(jì)算樣本鄰域集合耗費(fèi)的時(shí)間。本文將兩種算法結(jié)合在一起，提出了一種基于NE 的單次索引特征選擇（Single indexed NE Feature Selection，SINEFS）算法，運(yùn)用到高光譜圖像的波段選擇過程，并與其他常用的基于MI 的特征選擇算法進(jìn)行了對(duì)比分析。

1 MI理論及相關(guān)的特征選擇算法

1.1 MI理論基礎(chǔ)

本節(jié)將對(duì)基于MI 的特征選擇算法進(jìn)行說明，以下是信息熵相關(guān)內(nèi)容的說明。

信息熵：對(duì)于一個(gè)分類任務(wù)，通過Pr（k）表示不同類出現(xiàn)的概率，其中k=1，2，…，N。熵是每種類度量不確定性的方式，計(jì)算公式如式（1）所示：

條件熵：對(duì)于一個(gè)分類任務(wù)，通過Dd來表示一個(gè)集合，元素為第d個(gè)特征所有可能的特征值，其中1≤d≤D；通過Dc來表示一個(gè)集合，元素為不同的類。在知道第d個(gè)特征后的平均不確定性稱為條件熵，定義如式（2）所示：

互信息：類C和一個(gè)特征Fd之間的互信息定義式為：

根據(jù)公式可知，條件熵往往小于或等于信息熵，當(dāng)且僅當(dāng)輸出的類變量和特征是獨(dú)立的隨機(jī)變量時(shí)，條件熵等于信息熵。當(dāng)特征Fd已知時(shí)，MI 相較于信息熵的值會(huì)減少。將式（3）推導(dǎo)后可得：

其中：C和Fd是對(duì)稱的。根據(jù)Fano 不等式［20］，MI 和一個(gè)學(xué)習(xí)系統(tǒng)的精度有相關(guān)性。以下是Fano 不等式的定理。

定理1Fano 不等式［21］794：設(shè)隨機(jī)變量x和y分別代表一個(gè)噪聲通道的輸入和輸出信息。一個(gè)接收器通過方程f（y），將收到的信息y重構(gòu)成原始輸入信息x，其中x*=f（y）。設(shè)E為二進(jìn)制隨機(jī)變量來表示一個(gè)事件是否為錯(cuò)誤，即E=1 時(shí)，給定通道的輸出y的解碼結(jié)果x*和原始輸入x不同，則不等式的表達(dá)式為：

其中：N是不同輸入通道的個(gè)數(shù)。將y等價(jià)于一個(gè)特征Fd，x等價(jià)于類C，接收器中轉(zhuǎn)化用的方程f（·）等價(jià)于一個(gè)用于分類的算法，則Pr（E=1）可以等價(jià)于一個(gè)分類器的誤差率。根據(jù)式（5），Pr（E=1）的下界和條件熵H（C|Fd）成正比。因此，減少該值可以相當(dāng)于在增大MI 的值，是降低誤差率且構(gòu)建有效分類器的必要條件。

1.2 基于MI的特征選擇算法

接下來將對(duì)一些基于MI 進(jìn)行特征選擇的方法進(jìn)行說明?；贛I 的特征選擇算法是最大化相關(guān)性特征選擇（Maximum Relevance-Mutual Information Feature Selection，MR-MIFS）算法，首先計(jì)算類變量和每個(gè)獨(dú)立特征之間的MI值，然后對(duì)MI 值進(jìn)行排序，選擇最高的s個(gè)特征。但是此類算法在特征選擇過程中容易將連續(xù)的特征進(jìn)行選取，為了改進(jìn)上述算法，在算法的評(píng)價(jià)機(jī)制中引入了最小化冗余度，以篩選所選特征之間較小相關(guān)性的特征。此類算法稱為最小化冗余度以及最大化相關(guān)性的特征選擇（minimum Redundancy MR-MIFS，mRMR-MIFS）算法［22］。該算法首先通過計(jì)算類變量之間的MI，將MI 作為相關(guān)性的評(píng)價(jià)標(biāo)準(zhǔn)，并選擇相關(guān)性高的特征。然后在相關(guān)性較高特征集合里再計(jì)算冗余度，篩選冗余度較小的特征集合。在特征集合冗余度的計(jì)算中，也采用MI 進(jìn)行對(duì)比，用于再次篩選。

通過計(jì)算已選特征以及未被選擇特征之間的歸一化互信息的特征選擇算法，稱為歸一化互信息（Normalized Mutual Information，NMI）［23］。首先計(jì)算MI 作為選取特征的指標(biāo)，再計(jì)算所選特征以及被選擇特征之間MI 最小的值，特征之間的MI 值會(huì)被最小MI 值歸一化處理。歸一化后的MI值在0～1，當(dāng)NMI 為0 時(shí)，說明兩個(gè)特征之間完全獨(dú)立；當(dāng)NMI 值為1 時(shí)，說明特征之間的相關(guān)性較高，以此作為冗余度評(píng)價(jià)的標(biāo)準(zhǔn)，對(duì)波段子集進(jìn)行篩選。

以上兩種算法都是按照一對(duì)特征，或者特征和類之間的配對(duì)進(jìn)行互信息值的計(jì)算。上述的相關(guān)性和冗余度需要分別計(jì)算。在文獻(xiàn)［24］中提出的特征選擇算法將MI 泛化到多個(gè)特征上，稱為精準(zhǔn)互信息特征選擇（eXact Mutual Information Feature Selection，X-MIFS）。該算法計(jì)算所選特征的特征子集和類變量之間的MI，未被選取的特征和特征子集具有較高的相關(guān)性，才會(huì)選取該特征。從計(jì)算MI 的角度看，該算法在計(jì)算MI 的過程中不是兩個(gè)一維向量之間的計(jì)算，而是一個(gè)一維向量和多維隨機(jī)變量進(jìn)行MI 的計(jì)算。

對(duì)于無監(jiān)督的特征選擇算法，MI 也是有效的特征評(píng)價(jià)標(biāo)準(zhǔn)。Martínez-Usó 等［25］提出的基于互信息的Ward連鎖策略（Ward’s Linkage strategy using Mutual Information，WaLuMI），采用基于層次聚類結(jié)構(gòu)算法將類似的特征分成不同的特征子集，使子集之內(nèi)的方差最小、子集間的方差最大，通過MI實(shí)現(xiàn)這種度量方式，以減少波段間的數(shù)據(jù)冗余。

相較于上述的策略，本文提出的算法是一種通過最大化MI 的貪婪特征搜索過程。根據(jù)1.1 節(jié)的式（3），最大化MI，即最大化式（3），等價(jià)于最大化式（4）。在式（4）中，方程式的第一項(xiàng)H（C）是常量，在算法中可以忽視，最大化MI 只需要最小化方程式中的第二項(xiàng)條件熵H（C|Fd），其中1≤d≤D。對(duì)于高光譜圖像，分類器應(yīng)該將圖像中某個(gè)光譜通道下像素值接近的點(diǎn)歸為同一類，其中對(duì)于某一個(gè)類來說，在該光譜通道下條件熵的值應(yīng)該是非常小。與之相對(duì)應(yīng)，當(dāng)一個(gè)類的在某個(gè)光譜通道下的條件熵非常高，對(duì)于分類任務(wù)而言該通道的光譜信息是冗余的，甚至是噪聲信息。所以可以將類相較于一個(gè)特征的條件熵作為評(píng)價(jià)特征和類相關(guān)性程度的指標(biāo)，用于選取最富有信息量的波段。

2 本文算法

2.1 鄰域熵

由式（2）可知，計(jì)算類和特征之間的條件熵，需要知道Pr（f）和Pr（c|f）的概率分布。本文采用了基于NE 的計(jì)算方法可以不需要估計(jì)類熵相較于一個(gè)特征的概率分布，只用考慮一個(gè)樣本點(diǎn)的鄰域范圍的類，并給數(shù)據(jù)集中的所有樣本點(diǎn)求平均。NE［26］是信息熵在數(shù)字特征上的泛化，接下來詳細(xì)介紹相關(guān)內(nèi)容。

給定一個(gè)分類任務(wù)，其中S是一個(gè)多維隨機(jī)變量，X是S的一個(gè)實(shí)例。δ（X，k）是X及其k個(gè)最近鄰域樣本（k-Nearest Neighborhoods，k-NN）的集合，則對(duì)于一個(gè)類c∈Dc，其鄰域集合δ（X，k）的相對(duì)頻率為：

其中：|·|為集合的基數(shù)；n為一個(gè)事件發(fā)生的次數(shù)。則類變量C相較于S的NE 可以定義為：

其中：Xi代表了S的第i個(gè)實(shí)例。根據(jù)式（3）和式（4），通過最小化NE，也就是最大化MI，因?yàn)闂l件熵式（2）和NE 可以推導(dǎo)出近似關(guān)系［26］22：

對(duì)于特定波段的NE 以及MI，NE 可以不需要估計(jì)特征的概率分布以最大化MI，并且NE 采用了自適應(yīng)的不確定性計(jì)算方式，只需要計(jì)算一個(gè)樣本點(diǎn)鄰域內(nèi)類變量及相關(guān)頻率。

算法執(zhí)行主要的時(shí)間都消耗在樣本點(diǎn)最近鄰的搜索過程中。如果已經(jīng)選取了i個(gè)波段，在第i+1 次循環(huán)過程中，NE特征選擇（NE Feature Selection，NEFS）算法為尋找s個(gè)波段的CPU 時(shí)間復(fù)雜度為O（CDs）。

在算法執(zhí)行的過程中，考慮到高光譜圖像的樣本點(diǎn)個(gè)數(shù)和其空間分辨率相關(guān)，所以算法構(gòu)建過程中樣本鄰域的搜索是一個(gè)重要的環(huán)節(jié)。本文提出的算法中采取了局部敏感哈希（Local Sensitive Hashing，LSH）算法搜索鄰域集合。LSH算法接受一定程度下近似帶來的誤差，搜索速度會(huì)遠(yuǎn)高于基于度量距離的暴力搜索方法。

2.2 LSH算法

對(duì)于高光譜圖像數(shù)據(jù)集，假設(shè)其包含D個(gè)波段，N個(gè)樣本點(diǎn)，數(shù)據(jù)集往往符合D

在本文中，主要采用的方法是Gionis 等［27］提出的搜索算法。通過索引技術(shù)將樣本點(diǎn)分到不同的組，每個(gè)組的樣本點(diǎn)是近似鄰閾值。在查詢階段，索引可以幫助樣本點(diǎn)到相應(yīng)的組內(nèi)，從而再計(jì)算組內(nèi)樣本點(diǎn)之間的距離。以下是對(duì)LSH 搜索算法的說明。

設(shè)dist 為D個(gè)波段的高光譜數(shù)據(jù)集M中任意兩個(gè)樣本點(diǎn)之間的距離計(jì)算公式。對(duì)于任意樣本點(diǎn)P，通過dist 計(jì)算距離，令B（P；r）表示距離P的范圍r內(nèi)的所有點(diǎn)的集合。

LSH 方程［27］522：對(duì)于一個(gè)哈希方程簇H，方程h（·）對(duì)距離公式dist 具有（r1，r2，p1，p2）敏感性，其中r1

如果P∈B（Q；r1），則PrH（h（Q）=h（P））≥p1；

如果P?B（Q；r2），則PrH（h（Q）=h（P））≤p1。

在NEFS 中，LSH 需要由適用于歐氏空間的局部敏感哈希方程簇來實(shí)現(xiàn)，這些方程定義為：

其中：w是一個(gè)固定的正整數(shù)；b是從［0，w］中隨機(jī)獲取的數(shù)。為了計(jì)算范式l2的距離，從高斯分布中獲取a∈RD。

在NEFS 每次運(yùn)算的過程中，波段和類之間的NE 需要構(gòu)建一個(gè)新的LSH 索引，時(shí)間復(fù)雜度為O（Ds）。L個(gè)新的哈希方程在NEFS 每次循環(huán)中會(huì)構(gòu)建一次，對(duì)于每個(gè)方程，需要生成b以及向量a∈RD，這些相當(dāng)于系數(shù)的生成過程，時(shí)間復(fù)雜度為O（Ls2）。當(dāng)選取的波段子集基數(shù)變化時(shí)，需要用式（9）將數(shù)據(jù)集中的每個(gè)點(diǎn)哈希L次。循環(huán)過程中總共需要構(gòu)建Ds次索引，因此對(duì)于i=0，1，…，s-1，需要哈希的值的個(gè)數(shù)為NL，則時(shí)間復(fù)雜度為O（NLDs2）。構(gòu)建索引后，每個(gè)樣本點(diǎn)的NN 搜索會(huì)計(jì)算樣本點(diǎn)的哈希值，然后在L個(gè)哈希表中找到候選的樣本點(diǎn)，最后從候選的點(diǎn)集合中使用距離度量的方式找到鄰域子集。查詢一個(gè)樣本點(diǎn)的時(shí)間復(fù)雜度為O（DNL（1+ε））。因此計(jì)算NE 過程中所有波段子集的時(shí)間復(fù)雜度為O（DN（2+ε）/（1+ε）s2），令α=（2+ε）/（1+ε），則本文提出的NEFS 算法的時(shí)間復(fù)雜度為：

2.3 SINEFS

本文算法indexed-NEFS 將LSH 算法和NE 計(jì)算的過程結(jié)合在一起，并且在LSH 構(gòu)建流程中進(jìn)行了優(yōu)化。在2.2 節(jié)中提到，LSH 構(gòu)建索引的過程中，需要當(dāng)前用于計(jì)算NE 的波段子集構(gòu)建索引，但是本文在D維數(shù)據(jù)集上只構(gòu)建了一次索引，也就是在全特征下構(gòu)建了一次。當(dāng)NE 子集進(jìn)行計(jì)算時(shí)，第一個(gè)過程就是獲取一個(gè)樣本點(diǎn)的全特征索引，然后在樣本點(diǎn)的哈希表中搜索NN 個(gè)樣本點(diǎn)。這是基于以下兩點(diǎn)考慮的：首先，對(duì)于D維數(shù)據(jù)集，利用數(shù)據(jù)表達(dá)的空間信息，樣本點(diǎn)的鄰域集合在全特征的情況下，也是特征子集s樣本點(diǎn)的鄰域集合，其中s

3 實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)數(shù)據(jù)集

為了評(píng)估提出算法的性能，本節(jié)將詳細(xì)闡述高光譜波段選擇的實(shí)驗(yàn)結(jié)果。首先簡(jiǎn)單說明實(shí)驗(yàn)中采用的兩個(gè)高光譜圖像數(shù)據(jù)集：Indian Pines 和Salinas。

Indian Pines 數(shù)據(jù)集從普渡大學(xué)多光譜圖像數(shù)據(jù)分析小組的站點(diǎn)下載。該數(shù)據(jù)集為NASA 在1992 年6 月12 日采用JPL 的機(jī)載可見/紅外成像光譜儀傳感器采集，它具有每像素20 m 的空間分辨率和10 nm 光譜分辨率，涵蓋光譜0.4 μm～2.5 μm。本文實(shí)驗(yàn)中的數(shù)據(jù)集為此次采集的一張較大圖像的子集，由145×145 個(gè)像素，224 個(gè)光譜反射帶組成，圖1 為Indian Pines 數(shù)據(jù)集的三通道圖像。

圖1 Indian Pines 三通道圖像Fig.1 Three-channel image in Indian Pines

通過移除受水汽影響以及噪聲波段對(duì)應(yīng)的數(shù)據(jù)，實(shí)驗(yàn)中采用的Indian Pines 數(shù)據(jù)集的波段個(gè)數(shù)為200（移除104～108、150～163 以及220 波段）。數(shù)據(jù)集各個(gè)類標(biāo)樣本量的詳細(xì)信息如表1 所示，地物信息主要包括了蔬菜、植被以及公路鐵路。

表1 Indian Pines數(shù)據(jù)集的類標(biāo)以及相應(yīng)的樣本數(shù)Tab.1 Class labels and corresponding numbers of samples in Indian Pines dataset

Salinas 數(shù)據(jù)集從加利福尼亞州Salinas 山谷上空采集，傳感器為AVIRIS，包含了224 個(gè)波段，具有高空間分辨率（每像素3.7 m）的特征以及512×217 個(gè)像素點(diǎn)。和Indian Pines 數(shù)據(jù)集一樣，移除了20 個(gè)吸水的波段以及噪聲波段（移除108～112、154～167 以及224 波段）。圖2 為Salinas 數(shù)據(jù)集的三通道圖像。

圖2 Salinas數(shù)據(jù)集的三通道圖像Fig.2 Three-channel image in Salinas dataset

數(shù)據(jù)集各個(gè)類標(biāo)樣本量的詳細(xì)信息如表2 所示，地物信息主要包括了蔬菜、土壤以及葡萄園。

表2 Salinas數(shù)據(jù)集的類標(biāo)以及相應(yīng)的樣本數(shù)Tab.2 Class labels and corresponding numbers of samples in Salinas dataset

3.2 實(shí)驗(yàn)設(shè)計(jì)

本文提出的算法將與其他基于MI 的特征選擇算法進(jìn)行波段選擇實(shí)驗(yàn)進(jìn)行比對(duì)，其中包括1.2 節(jié)提及的mRMRMIFS、NMI、X-MIFS 以及WaLuMI。

算法執(zhí)行效率將通過時(shí)間復(fù)雜度的分析以及算法CPU時(shí)間進(jìn)行對(duì)比，以評(píng)價(jià)LSH 對(duì)鄰域集合搜索效率帶來的提升。并通過分類實(shí)驗(yàn)體現(xiàn)SINEFS 算法的可靠性以及有效性。

在本文的實(shí)驗(yàn)中，最佳的波段個(gè)數(shù)是不確定的，不同數(shù)據(jù)集上最優(yōu)的波段個(gè)數(shù)也會(huì)存在差異，所以各個(gè)算法選擇的波段個(gè)數(shù)范圍從5 到60，以等步長(zhǎng)5 依次增加。

完成波段選擇算法后，將采用分類任務(wù)對(duì)選取波段的有效性進(jìn)行評(píng)價(jià)。主要采用的分類器為支持向量機(jī)（Support Vector Machine，SVM）、徑向基核函數(shù)（Radial Basis Function，RBF）、隨機(jī)森林（Random Forest，RF）分類器進(jìn)行分類，其中RF 樹個(gè)數(shù)設(shè)置為20。通過分類器計(jì)算獲取各個(gè)特征作用下，分類的總體精度（Overall Accuracy，OA）和Kappa 系數(shù)（Kappa Coefficience，KC）。此外，為了使分類結(jié)果的可信度提升，進(jìn)行10 次十折交叉驗(yàn)證，對(duì)于每種特征選擇算法，分類實(shí)驗(yàn)中分別在兩個(gè)數(shù)據(jù)集隨機(jī)劃分樣本集合作為訓(xùn)練集和測(cè)試集，并將OA 和KC 的均值作為結(jié)果進(jìn)行比對(duì)。

所有算法在8 核64 位，CPU 頻率在2.6 GHz，內(nèi)存16 GB的計(jì)算機(jī)上運(yùn)行。算法通過Python3 實(shí)現(xiàn)，所有算法在實(shí)現(xiàn)過程中沒有利用語言特性或者相關(guān)張量計(jì)算庫提升運(yùn)算性能，算法按照偽代碼的實(shí)現(xiàn)步驟進(jìn)行編寫，以保證所有實(shí)驗(yàn)結(jié)果的有效性。實(shí)驗(yàn)中的分類器采用第三方庫sklearn 提供的SVM 和RF，以獲取有效的OA 和KC 進(jìn)行實(shí)驗(yàn)結(jié)果比對(duì)。

3.3 時(shí)間復(fù)雜度分析

為了有效地比對(duì)各個(gè)算法的時(shí)間復(fù)雜度，如3.2 節(jié)說明的，對(duì)選擇特征值的個(gè)數(shù)進(jìn)行設(shè)置。雖然從時(shí)間復(fù)雜度進(jìn)行分析所選波段的個(gè)數(shù)只是部分影響因素，但是算法在實(shí)際運(yùn)行過程中，選擇特征的個(gè)數(shù)對(duì)執(zhí)行效率影響較大。

對(duì)于mRMR-MIFS，算法計(jì)算相關(guān)性的時(shí)間和樣本數(shù)量為線性關(guān)系，且為正相關(guān)。隨著搜索樣本數(shù)量的增加，算法執(zhí)行的時(shí)間也會(huì)增加。算法計(jì)算相關(guān)性最差的情況是O（N）。算法循環(huán)的過程中，需要執(zhí)行O（|S|）次計(jì)算以獲取特征之間的相關(guān)性，并更新特征子集中最大相關(guān)性的值。該算法的時(shí)間復(fù)雜度為CmRMR-MIFS=O（DNs2）。

NMI 算法在執(zhí)行過程中需要對(duì)計(jì)算出來的特征對(duì)進(jìn)行排序，排序算法采用堆排序，時(shí)間復(fù)雜度為O（NlogN），其中N為樣本個(gè)數(shù)?？紤]已選擇的特征個(gè)數(shù)s，NMI 的時(shí)間復(fù)雜度為CNMI=O（DNslogN）。

X-MIFS 算法和NEFS 的貪婪搜索過程一致，不同之處在于評(píng)價(jià)指標(biāo)為MI，NEFS 為NE。在計(jì)算MI 的過程中需要用到修改的式（3），將其中的概率分布函數(shù)用多維直方圖的預(yù)估器進(jìn)行替換。在X-MIFS 實(shí)現(xiàn)的過程中需要對(duì)特征二進(jìn)制化，所以對(duì)于每個(gè)子集，通過對(duì)所有點(diǎn)的線性遍歷來估計(jì)聯(lián)合概率分布和邊際概率分布。因此選擇s個(gè)特征的時(shí)間復(fù)雜度為CX-MIFS=O（DNs2）。

WaLuMI 算法在執(zhí)行過程中主要包括兩個(gè)部分。首先是聚類部分，對(duì)于一個(gè)型為L(zhǎng)×L的距離矩陣，以及特征個(gè)數(shù)為D的數(shù)據(jù)集，聚類部分的時(shí)間復(fù)雜度為O（L2D）。第二部分進(jìn)行離散的子集MI 計(jì)算。該計(jì)算部分和聚類后的特征子集個(gè)數(shù)，以及MI 計(jì)算過程相關(guān)，時(shí)間復(fù)雜度為O（LDN）。所以WaLuMI 的時(shí)間復(fù)雜度為O（LDN+L2D）。表3 顯示了各類算法的時(shí)間復(fù)雜度。

表3 各個(gè)算法的時(shí)間復(fù)雜度Tab.3 Time complexity of each algorithm

為了能夠測(cè)試各類算法運(yùn)行的效率，在表4 中顯示了用CPU 的時(shí)間模型，數(shù)據(jù)集固定在DN，s為10，L為N的1/4，ε=15，各類算法運(yùn)行時(shí)間的最小二乘法線性模型。

表4 CPU時(shí)間線性模型Tab.4 CPU time linear model

結(jié)合3.2 節(jié)NEFS 的時(shí)間復(fù)雜度分析結(jié)果可知，NEFS 在各類算法的比對(duì)中較慢，因?yàn)闀?huì)消耗大量時(shí)間進(jìn)行索引構(gòu)建以及NNs 的搜索。SINEFS 在引入單次構(gòu)建LSH 索引后，α≈1，即執(zhí)行效率會(huì)接近NMI，相較于NEFS 效率有顯著的提升；mRMR-MIFS、WaLuMI 和X-MIFS 是速度較快的算法，其中X-MIFS 運(yùn)用了二進(jìn)制特征，使得其執(zhí)行效率較高。當(dāng)WaLuMI 設(shè)置距離矩陣L較大，以及數(shù)據(jù)集特征數(shù)量多時(shí)，執(zhí)行消耗會(huì)增加。

3.4 分類實(shí)驗(yàn)結(jié)果與分析

3.4.1 Indian Pines數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

本節(jié)分析并比對(duì)各類算法在Indian Pines 數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果。圖3 顯示了各個(gè)算法選取的波段子集，以及全波段集合，采用SVM 以及RF 進(jìn)行分類的OA 值。

當(dāng)分類器選取SVM 時(shí)，由圖3（a）可知，全波段OA 為77.56%，選取波段個(gè)數(shù)小于20 時(shí)，除了SINEFS，其他算法選取的波段OA 低于全波段OA；當(dāng)波段子集數(shù)為40 時(shí)，WaLuMI 選取的波段子集OA 超過了其他算法選取的波段子集，且OA 超過了SINEFS；當(dāng)選取波段個(gè)數(shù)超過50 時(shí)，X-MIFS 的OA 超過了全波段OA；mRMR-MIFS 和NMI 的性能較差，選擇的波段子集均未超過全波段OA。WaLuMI 在60個(gè)波段子集時(shí)OA 達(dá)到了最優(yōu)，為83.90%。根據(jù)實(shí)驗(yàn)結(jié)果，SINEFS 選取的波段子集，能夠較快地超過全波段OA。

當(dāng)分類器選取RF 時(shí)，根據(jù)圖3（b），除了NMI 在5 個(gè)選取波段的OA 值，其他算法OA 的整體結(jié)果優(yōu)于SVM。其中全波段OA 為79.80%。當(dāng)波段子集數(shù)為30 時(shí)，SINEFS、WaLuMI 以及X-MIFS 的OA 值優(yōu)于全波段OA。在波段子集數(shù)為35 和40 時(shí)，SINEFS 的OA 值分別為84.45%和84.85%，WaLuMI 的OA 值分別為84.62%和84.71%。雖然SINEFS 在波段子集數(shù)為40 時(shí)OA 最高，但是在這個(gè)區(qū)間的OA 結(jié)果兩種算法差別不明顯。

圖3 Indian Pines數(shù)據(jù)集上采用SVM以及RF進(jìn)行分類實(shí)驗(yàn)的OA值Fig.3 OA values of classification experiments using SVM and RF on Indian Pines dataset

圖4 顯示了各個(gè)算法選取不同波段子集，以及全波段集合，采用SVM 和RF 進(jìn)行分類的KC 值。

圖4 Indian Pines數(shù)據(jù)集上采用SVM以及RF進(jìn)行分類實(shí)驗(yàn)的KC值Fig.4 KC values of classification experiments using SVM and RF on Indian Pines dataset

從圖4（a）的KC 值來看，當(dāng)選取波段子集為15 時(shí)，SINEFS 的KC 為0.736 6，優(yōu)于全波段以及其他算法的KC值；WaLuMI 和X-MIFS 在40 個(gè)波段子集時(shí)超過了全波段KC。當(dāng)SINEFS 選取波段子集為55 時(shí)，KC 為最高的0.797 6。其他算法在RF 分類器的分類結(jié)果相較于SVM 呈現(xiàn)上升趨勢(shì)，在高于55 個(gè)波段子集時(shí)，除了WaLuMI，KC 值有一定的回落。

從圖4（b）的KC 值分析，全波段KC 值為0.754 6，SINEFS 在30 個(gè)波段子集超過了全波段KC 值，為0.772 4，同樣為所有算法中最快超過全波段的算法。SINEFS 和X-MIFS隨著波段子集的增加，KC 值也在增加，在波段個(gè)數(shù)為55 時(shí)，達(dá)到最優(yōu)0.837 5。在波段個(gè)數(shù)為60 時(shí)，SINEFS 的KC 值有回落，但是依然高于其他算法以及全波段KC 值。

3.4.2 Salinas數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

在本節(jié)，分析并比對(duì)各類算法在Salinas 數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果。圖5 顯示了各個(gè)算法選取的波段子集，以及全波段集合，采用SVM 以及RF 進(jìn)行分類的OA 值。對(duì)比圖3 和圖5 可以看出，在Salinas 數(shù)據(jù)集上，兩種分類器獲取的OA 值均高于Indian Pines 數(shù)據(jù)。

圖5 在Salinas數(shù)據(jù)集上采用SVM以及RF進(jìn)行分類實(shí)驗(yàn)的OA值Fig.5 OA values of classification experiments using SVM and RF on Salinas dataset

當(dāng)分類器選取SVM 時(shí)，根據(jù)圖5（a），全波段OA 值為77.56%。SINEFS 和WaLuMI 在10 個(gè)波段子集時(shí)OA 值分別為77.32%和77.88%，OA 值較為接近，WaLuMI 先超過了全波段OA 值。在波段子集數(shù)為15 時(shí)，SINEFS 的OA 值超過全波段OA 值，為79.71%。其他算法OA 值均隨著波段子集的個(gè)數(shù)增加，逐漸超過全波段OA 值。在選取40 個(gè)波段子集時(shí)，SINEFS 超過WaLuMI 達(dá)到最高OA 值，為92.99%。波段子集數(shù)范圍在25～55 時(shí)，SINEFS 的OA 值優(yōu)于WaLuMI 及其他算法，在60 個(gè)波段子集，SINEFS 的OA 值回落，WaLuMI 有小幅度增加。

當(dāng)分類器選取RF 時(shí)，根據(jù)圖5（b），SINEFS 為OA 值增加最快的算法，當(dāng)選取10 個(gè)波段時(shí)，OA 值為80.70%，高于全波段的79.80%。波段子集區(qū)間10～40 時(shí)，SINEFS 高于其他算法。但是在45 個(gè)波段時(shí)，WaLuMI 達(dá)到了最佳OA，值為93.43%，SINEFS 的OA 值開始小幅度下降。其他算法在波段數(shù)位25 時(shí)均超過全波段OA，并在后面的特征集合中呈上升趨勢(shì)。

圖6 顯示了各類算法在Salinas 數(shù)據(jù)集上KC 值的實(shí)驗(yàn)結(jié)果。相較于圖4 中顯示的結(jié)果，在Salinas 數(shù)據(jù)集上KC 值整體優(yōu)于Indian Pines 數(shù)據(jù)集。

圖6 Salinas數(shù)據(jù)集上采用SVM以及RF進(jìn)行分類實(shí)驗(yàn)的KC值Fig.6 KC values of classification experiments using SVM and RF on Salinas dataset

根據(jù)圖6（a），SINEFS 在20 個(gè)波段子集時(shí)超過全波段KC 值，其中SINEFS 為0.755 3，全波段KC 為0.734。波段子集數(shù)范圍在30～40 時(shí)，WaLuMI 的KC 值優(yōu)于SINEFS 及其他算法，但是SINEFS 在所有波段區(qū)間都保持了增長(zhǎng)的趨勢(shì)，而WaluMI 出現(xiàn)了回落。mRMR-NEFS、NMI、X-MIFS 在整個(gè)效果上優(yōu)于Indian Pines 數(shù)據(jù)集，且在波段子集數(shù)為35 時(shí)，均超過了全波段的KC 值。

根據(jù)圖6（b），SINEFS 在10 個(gè)波段的KC 值超過了全波段KC 值，分別為0.775 5 和0.754 6。波段數(shù)在5～40 時(shí)，SINEFS 的KC 值均優(yōu)于其他算法，在波段數(shù)為30 時(shí)，SINEFS的KC 達(dá)到最大值0.860 8。WaLuMI 的KC 值在波段數(shù)為45時(shí)達(dá)到實(shí)驗(yàn)最佳，為0.872 2。其他算法KC 值均優(yōu)于Indian Pines 數(shù)據(jù)集，且在波段數(shù)為30 及以上，均超過了全波段的KC 值。

4 結(jié)語

本文根據(jù)MI 理論，提出了一種基于MI 波段選擇算法，該算法通過最小化NE，同時(shí)最大化特征和輸出變量之間的MI。該算法采取了貪婪的搜索策略，以及LSH 優(yōu)化NNs 的搜索過程，以獲取最優(yōu)的波段子集。本文通過實(shí)驗(yàn)比對(duì)其他基于MI 的特征選擇算法，實(shí)驗(yàn)結(jié)果顯示，相較于其他比對(duì)算法，本文提出的SINEFS 可以更快地達(dá)到較優(yōu)的波段子集，能在較小的波段集合的區(qū)間獲取較優(yōu)的分類效果；但是本文的鄰域搜索過程中LSH 的參數(shù)設(shè)定為人為設(shè)定，隨著數(shù)據(jù)集的變化，需要預(yù)先計(jì)算以獲取最優(yōu)參數(shù)，后續(xù)需要采用其他技術(shù)進(jìn)行優(yōu)化，以適用于更多的工作場(chǎng)景。