Relief算法由Kira和Rendell于1992年提出, 主要用于解决二值分类的特征降维问题。 针对Relief算法无法处理多分类的问题, Kononenko于1994年对Relief算法进行改进, 提出了ReliefF算法。 ReliefF算法是一种经典的多变量过滤式特征选择方法, 其核心思想是根据特征与类别标签之间的相关性计算特征的权值^{[13, 14]}。 该算法中特征和类别标签的相关性是基于特征对近距离样本的区分能力度量的, 具体计算过程如下: 首先通过随机抽样选择一个样本x_i, 然后分别计算和R_i相同类别中k个最近邻样本的距离 ∑j=1kdiff(fl, Ri, Hj),和$R_i$ 不同类别中k个最近邻样本的距离 ∑j=1kdiff(fl, Ri, Mj(C)),若类间距大于类内距, 则增加其权值, 若类间距小于类内距, 则降低其权值, 通过计算类间距与类内距不断迭代m次更新其权值, 并根据最终权值进行特征选择, 其权值计算公式为

Wi+1(fl)=Wi(fl)-∑j=1kdiff(fl, Ri, Hj)m×k+∑C≠label(Ri)P(C)1-P(label(Ri))×∑j=1kdiff(fl, Ri, Mj(C))m×k(1)

式(1)中: Wⁱ(f_l)为第i个样本中第l个特征f的权值; H_j(j=1, 2, ..., k)为与R_i同类的k个最近邻样本中的第j个样本; P(C)为在训练样本中属于类别C的样本所占比值; P(label(R_i))为与同类的样本占总样本的比值, 其中label(R_i)为R_i的标签; M_j(C)(j=1, 2, ..., k)为与R_i不同类的k个最近邻样本中的第j个样本。 距离计算公式为

Df(i, j)=∑f(if-jf)2/σf(2)

式(2)中: diff(f, R₁, R₂)为样本R₁与R₂在第f个特征上的归一化距离, R_1f和R_2f分别为样本R₁和R₂的第f个特征, max(f)和min(f)分别为所有样本中对应特征f的最大值和最小值。

递归特征消除法是一种贪婪的优化算法, 是封装式算法的代表。 该算法的主要思想是反复创建模型, 逐步剔除最不重要特征。 该方法是一个循环过程, 每个过程都包含以下3个步骤: (1)用当前数据集训练分类器, 获得与分类器特征相关的信息即每个特征的权重; (2)根据事先制定的规则, 计算所有特征的排序准则分数; (3)在当前数据集中移除对应于最小排序准则分数的特征。 该循环过程一直执行到特征集合中剩余最后一个变量时结束, 执行的结果为获得一列按照特征重要性排序的特征序号列表, 这个迭代循环过程实际上是一个序列后向选择的过程, 它在整个循环过程中先是去除了与判别不相关的特征, 保留了对判别相对重要的优化特征子集, 因而可以达到优化特征子集选择, 提高判别精度的目的。 然而, 封装式由于每次与特征子集的评价都要进行分类器的训练和测试, 计算复杂度很高。 因此, 封装式特征选择的计算开销通常比过滤式特征选择要大得多。

过滤式算法运算高效, 但是其并不考虑特征之间的相关性。 然而, 与类相关性强的单个特征组合在一起并不一定有利于分类^[15], 是因为相关特征中包含一些与其他相关特征具有相同分类信息的特征, 即“ 冗余特征” 。 这类特征不仅会增加分类器的计算复杂度, 而且可能导致分类器性能急剧下降。 因此, 需要寻找一种比较高效的特征搜索算法, 从而获得最佳的分类特征子集。 封装式算法的特征选择与具体分类器紧密相关, 因直接使用分类器的识别率来评价特征性能, 并将选择所得特征直接用于构造最终的分类模型, 所以封装模型相对于过滤模型具有更好的分类识别性能。 但是, 由于每一次选择都涉及到分类器的建模计算, 所以封装式算法的运算时间要比过滤式算法慢很多。 综合考虑过滤式算法和封装式算法的优缺点, 在过滤式ReliefF算法基础上, 选取考虑到特征之间相关性的封装式RFE算法, 构建ReliefF-RFE算法。 首先利用ReliefF算法对不同的特征赋予不同的权重, 通过权重阈值有效剔除无关特征并保留有助于分类的特征, 减少后续特征子集搜索范围, 其次, 将ReliefF算法筛选后留下的特征, 利用RFE算法进一步筛选出与特征间相关性最大且相互之间冗余性最小的最佳分类特征子集。

设输入训练集x, 最近邻样本个数k, 步长step, 输出x_k为训练集x与目标类别有最大相关性且相互之间具有最小冗余性的特征子集, 那么, ReliefF-RFE算法具体可分为以下8个主要步骤:

(1)从训练集x中进行随机抽样选择一个样本R_i;

(2)计算与样本$R_i$ 相同类别的k个猜中近邻的距离 ∑j=1kdiff(fl, Ri, Hj)和其他不同类的k个猜错近邻的距离 ∑j=1kdiff(fl, Ri, Mj(C));

(3)根据与R_i不同类样本所占比值, 最终计算出特征的权重Wⁱ(f_l);

(4)筛选出权重系数总和达95%的特征子集, 通过权重阈值剔除无关特征, 得到ReliefF算法筛选后的特征子集x_j;

(5)将特征子集x_j作为RFE算法的输入, 同时设置最优特征子集x_k为空, max=0;

(6)在特征子集x_j构建随机森林分类器, 并通过随机森林的feature_importances_属性获得每个特征的重要性;

(7)将特征子集x_j中每个特征的重要性进行排序, 根据步长step从当前的这组特征集合中修剪最不重要的特征, 计算修剪后集合的Accuracy值。 若Accuracy≥ max, 则max=Accuracy, 且取当前集合为最优特征子集, 否则max和最优特征子集不变;

(8)在修剪的集合上递归地重复该过程, 逐次进行迭代, 直到找到Accuracy值最高的一组特征子集x_k。

为验证算法的适用性, 采用高光谱图像分类领域所公认的Indian pines, Salinas-A及KSC等3个标准数据集, 数据集中包含了许多地物类别(图1和图2)。 Indian pines数据集与Salinas-A数据集的地物类别分别为16类和6类, 地物的分布比较规则, 每类地物的分布整体性好; 而KSC数据集的地物类别共13类, 分布较为分散。 各数据集描述如表1所示。

图1

Fig.1

	Figure Option ViewDownloadNew Window
	图1 各标准数据集的高光谱图像 (a): Indian pines; (b): Salinas-A; (c): KSCFig.1 Hyperspectral images of each standard dataset (a): Indian pines; (b): Salinas-A; (c): KSC

图2

Fig.2

	Figure Option ViewDownloadNew Window
	图2 各标准数据集的真实地物参考图 (a): Indian pines; (b): Salinas-A; (c): KSCFig.2 References of real features for each standard dataset (a): Indian pines; (b): Salinas-A; (c): KSC

表1

Table 1

表1(Table 1)

表1 高光谱数据集描述 Table 1 Hyperspectral dataset description 数据集 Indian pines Salinas-A KSC 特征维数 200 204 176 样本数 10 249 5 348 5 211 影像尺寸 145× 145 86× 83 512× 614 分辨率/m 20 3.7 18 地物类别 16 6 13

表1 高光谱数据集描述 Table 1 Hyperspectral dataset description

(1)Indian pines数据集是使用AVIRIS成像光谱仪获取的美国印第安纳州西北部地区的试验区域图像, 地表覆盖类型混合了林地、 农田、 道路、 房屋建筑等。 标记样本分布不均衡, 部分类别样本较少。 各种农作物基本都处于生长初期, 对地表的林冠覆盖程度只有5%, 裸地和作物残渣对植被像元分类影响明显。 以上原因导致数据集类间相似度非常高, 分类难度大大增加。 Indian pines图像大小145× 145像素, 波长范围0.4~2.5 μ m, 220个波段, 空间分辨率20 m, 去除坏波段和水体吸收后剩余200个波段。

(2)Salinas-A数据集也是用AVIRIS成像光谱仪拍摄的, 同Indian pines图像相似, 是对美国Salinas山谷进行成像。 它区别于Indian pines的是, Salinas-A数据集能够达到3.7 m的空间分辨率。 图像原本包含的波段有224个, 对没有水反射的108~112, 154~167以及第224波段都需要剔除, 剩余波段图像有204个。

(3)KSC数据集由佛罗里达肯尼迪航天中心的AVIRIS传感器收集, 包含224个波段。 该数据集由512× 614个像素组成, 其中每个像素具有8 m的空间分辨率。 同时, 光谱覆盖范围为0.4~2.5 μ m, 去除48个噪声比较高的波段后, 共使用了176个波段。

为验证本算法的可靠性, 将ReliefF-RFE算法及单一的ReliefF、 RFE算法分别应用于前述3个高光谱数据集, 分析并比较3种算法的分类效果, 分类器统一采用随机森林分类器。 在进行实验比较之前, 先设置不同算法的参数。 ReliefF算法通过随机抽样选择样本计算某个特征的权值, 为了有效处理权重偏差, 避免最终运算结果的权重不同, 对某一特征的不同权值, 通过10次运算求取平均值作为该特征的权值, 设定最邻近样本数k为10, 对大多数分类任务最为可靠有效; 随机森林的最佳参数通过网格搜索交叉验证工具(GridSearchCV)进行参数寻优。 随机选取70%的样本作为训练样本, 30%样本作为验证样本, 统计十折交叉验证下最佳特征子集的总体精度(overall accuracy, OA)、 F-measure、 Kappa系数和筛选的最小特征维数以及特征选择算法的运算时间, 各指标的值越大, 特征维数和运算时间越少, 说明对应特征选择算法的性能越好, 具体公式如式(3)— 式(7)

OA=TN+TPTP+TN+FP+FN×100%(3)

Precision=TPTP+FP×100%(4)

Recall=TPTP+FN×100%(5)

F-measure=2×Precision×RecallPrecision+Recall×100%(6)

Kappa=p0-pc1-pc=N∑i=1Rxii-∑i=1R(xi+x+i)N2-∑i=1R(xi+x+i)(7)

式中: Precision表示精确度; Recall表示召回率; TP(true positive)表示被模型预测为正的正样本; TN(true negative)表示被模型预测为负的负样本; FP(false positive)表示被模型预测为正的负样本; FN(false negative)表示被模型预测为负的正样本; R为类别数; x_ii为第i行第i列上的数目; x_i+为第i行的总数目; x_+i为第i列的总数目; N为数据集总数目。

分别将3种特征选择算法与随机森林分类器相结合, 对Indian pines数据集进行分类, 由此获得该数据集的最佳特征子集。 利用验证样本计算混淆矩阵评价分类精度, 统计3种特征选择算法的OA, F-measure和Kappa系数以及特征维数和运算时间(表2)。 结果表明, ReliefF算法的分类精度最低且筛选出的特征维数最高, 其原因可能与ReliefF算法筛选出来的特征仍存在冗余, 增加了模型复杂度和过拟合的风险, 不利于提高模型可解释性, 使用的特征维数越多, 并不意味分类预测效果越好; RFE算法取得了较高的分类精度, 同时大幅降低了建模所需的特征数量, 增强了模型的泛化能力, 但是单独采用RFE算法进行特征选择所需要的运算时间较长, 当数据集规模足够大时, 搜索最佳特征子集的运算时间将不能够被接受; 较之于ReliefF算法, 采用过滤式和封装式相结合的ReliefF-RFE算法, 其OA提高了0.75%, F-measure提高了0.85%, Kappa系数提高了0.008 2; 在特征维数方面, ReliefF-RFE算法能够去除ReliefF算法的冗余特征, 其特征维数是ReliefF算法的29%; 在运算时间方面, ReliefF-RFE算法是RFE算法的85%, 说明ReliefF-RFE算法降低了封装式算法的运算时间, 提升了模型的整体运算效率。

表2

Table 2

表2(Table 2)

表2 Indian pines数据集最佳特征子集下的各评价指标 Table 2 Classification results based on the best feature subset of the Indian pines dataset 算法 OA /% F-measure /% Kappa 系数 特征 维数 t /h ReliefF 85.53 85.15 0.834 0 157 58.56 RFE 86.41 86.10 0.844 2 36 107.33 ReliefF-RFE 86.28 86.00 0.842 2 45 91.58

表2 Indian pines数据集最佳特征子集下的各评价指标 Table 2 Classification results based on the best feature subset of the Indian pines dataset

从3种特征选择算法的分类结果图可知(图3), 部分地物存在一定的错分误分现象, 但总体上, 各算法的分类效果与真实地物参考图基本接近。

图3

Fig.3

	Figure Option ViewDownloadNew Window
	图3 Indian pines数据集高光谱图像3种特征选择算法的分类结果Fig.3 Classification results of three feature selection algorithms for hyperspectral images of Indian pines dataset

利用随机森林分类器结合3种特征选择算法得到Salinas-A数据集的最佳特征子集, 可以发现, 3种算法都取得了较好的预测效果(表3)。 ReliefF算法的特征维数最高, RFE算法以较长的运算时间为代价, 用最少的特征数实现了和ReliefF算法相同的预测效果, 这也说明RFE算法能够进一步剔除冗余特征, 减少数据集处理的复杂度。 在分类精度方面, ReliefF-RFE算法首先通过ReliefF算法初步筛选掉一批无相关特征, 再利用RFE算法进一步去除冗余特征, 用较少规模的特征子集取得比单一ReliefF算法和RFE算法更好的分类精度, 其OA提高了0.07%, F-measure提高了0.06%, Kappa系数提高了0.000 8; 在特征维数方面, ReliefF-RFE算法是ReliefF算法的39%, 有效降低了特征维数; 在运算时间方面, ReliefF-RFE算法的运算时间是RFE算法的76%。

表3

Table 3

表3(Table 3)

表3 Salinas-A数据集最佳特征子集下的各评价指标 Table 3 Classification results based on the best feature subset of the Salinas-A dataset 算法 OA /% F-measure /% Kappa 系数 特征 维数 t /h ReliefF 99.31 99.32 0.991 4 180 6.34 RFE 99.31 99.32 0.991 4 35 11.35 ReliefF-RFE 99.38 99.38 0.992 2 71 8.63

表3 Salinas-A数据集最佳特征子集下的各评价指标 Table 3 Classification results based on the best feature subset of the Salinas-A dataset

从3种特征选择算法的分类细节上来看(图4), 各地物的边缘区域会存在错分情况, ReliefF-RFE算法在总体上的错分情况较少。

图4

Fig.4

	Figure Option ViewDownloadNew Window
	图4 Salinas-A数据集高光谱图像3种特征选择算法的分类结果Fig.4 Classification results of three feature selection algorithms for hyperspectral images of Salinas-A dataset

参照Indian pines与Salinas-A数据集的步骤, 利用KSC数据集, 对3种算法进行分析。 结果发现, ReliefF算法筛选的特征维数依然较大, 冗余特征的存在在一定程度上影响了模型性能; RFE算法以特征递归消除的方式搜索最优特征子集, 具有更好的预测效果; ReliefF-RFE算法的降维效果最好, 分别是ReliefF算法和RFE算法特征维数的44%和89%, 并且在运算时间上具有显著的优势, 是RFE算法运算时间的63%, 在损失小部分分类精度情况下, 大幅降低了特征选择算法的时间复杂度。

在KSC数据集中, 相较于前两者算法, ReliefF-RFE算法的分类精度最低(图5), 其原因可能在于: KSC数据集地物类别精细、 数量高达13类, 如湿地地物类别多达6种, 然而其光谱曲线的可分性有限, 同种地物类别会有不同的群体状况表现, 增加了分类难度。

图5

Fig.5

	Figure Option ViewDownloadNew Window
	图5 KSC数据集高光谱图像3种特征选择算法的分类结果Fig.5 Classification results of three feature selection algorithms for hyperspectral images of KSC dataset

表4

Table 4

表4(Table 4)

表4 KSC数据集最佳特征子集下的各评价指标 Table 4 Classification results with the best feature subset of the KSC dataset 算法 OA /% F-measure /% Kappa 系数 特征 维数 t /h ReliefF 93.22 93.14 0.924 0 145 8.22 RFE 93.41 93.31 0.936 2 72 14.98 ReliefF-RFE 93.16 93.06 0.923 8 64 9.58

表4 KSC数据集最佳特征子集下的各评价指标 Table 4 Classification results with the best feature subset of the KSC dataset

对比ReliefF-RFE算法与ReliefF, RFE算法对3个高光谱数据集分类应用结果可以发现: 其一, 在分类精度方面[图6(a)], 从总体分类精度可以发现, RFE算法最佳, 其平均OA为93.04%、 F-measure为92.91%, Kappa系数为92.06%; 其次为ReliefF-RFE算法, 其平均OA为92.94%、 F-measure为92.81%, Kappa系数为91.94%; ReliefF算法最低, 其平均OA为92.69%、 F-measure为92.54%, Kappa系数为91.65%; 从各数据集中可以发现, ReliefF-RFE算法在Indian pines数据集上比ReliefF算法拥有更好的预测性能, 其OA提高了0.75%, F-measure提高了0.85%, Kappa系数提高了0.008 2, 在Salinas-A数据集上, 其OA分别较其他两种算法提高0.07%, F-measure提高0.06%, Kappa系数提高0.000 8。 其二, 在特征维数和运算时间角度方面 [图6(b)], ReliefF算法在3个数据集上的特征维数均最高; ReliefF-RFE算法在3个高光谱数据集中筛选的特征维数远低于ReliefF算法, 平均特征维数是ReliefF算法的37%, 由此可以证明, 高维数据集中含有与地物类别无关的特征及互相关性较高的冗余特征, 结合封装式算法的特征选择能够去除过滤式算法中的冗余特征; RFE算法在3个数据集上拥有最高的时间复杂度, ReliefF-RFE算法在3个高光谱数据集中的运算时间均远低于单一的RFE算法, 平均运算时间是RFE算法的75%, 这是由于RFE算法每次都要结合分类器进行迭代, 造成耗时过多, ReliefF-RFE算法则在ReliefF算法筛选结果的基础上降低了数据集的特征数, 减小了特征子集的搜索范围, 从而大幅降低了时间复杂度。 总体而言, ReliefF-RFE算法能够克服过滤式ReliefF算法无法有效减小特征之间冗余以及封装式RFE算法时间复杂度较高的缺陷, 在分类精度、 特征维数、 运算时间共3个方面拥有均衡的综合性能。

图6

Fig.6

	Figure Option ViewDownloadNew Window
	图6 3种特征选择算法的综合对比 (a): 分类精度; (b): 特征维数和运算时间Fig.6 Comprehensive comparison of three feature selection algorithms (a): Classification accuracy; (b): Feature dimension and runtime