面向高维小样本数据的层次子空间ReliefF特征选择算法

doi:10.13232/j.cnki.jnju.2023.06.003

面向高维小样本数据的层次子空间ReliefF特征选择算法

程凤伟¹, 王文剑^,², 张珍珍¹

1.太原学院计算机科学与技术系, 太原, 030032

2.计算智能与中文信息处理教育部重点实验室, 山西大学, 太原, 030006

Hierarchical subspace ReliefF feature selection algorithm for high⁃dimensional small sample data

Cheng Fengwei¹, Wang Wenjian^,², Zhang Zhenzhen¹

1.Department of Computer Science and Technology，Taiyuan University，Taiyuan，030032，China

2.Key Laboratory of Computatoinal Intelligence and Chinese Information Processing of Ministry of Education，Shanxi University，Taiyuan，030006，China

通讯作者: E⁃mail：wjwang@sxu.edu.cn

收稿日期: 2023-08-10

基金资助:

国家自然科学基金.  62076154.  U1805263
中央引导地方科技发展资金.  YDZX20201400001224
山西省自然科学基金.  201901D111030
山西省教育科学“十四五”规划项目.  GH21395

Received: 2023-08-10

摘要

高维小样本数据的特征维数远远高于样本数，因为其通常包含大量的冗余特征，ReliefF算法在处理这类数据时存在以下挑战：传统ReliefF算法无法剔除冗余特征，而现有的改进ReliefF算法大多通过启发式地计算特征与特征之间的互信息来剔除冗余特征，不适用于高维数据；通过截取与标记相关性最大的若干特征来进行分类，可能不是最优选择，因其没有考虑不同特征组合对分类性能的影响.为了解决以上问题，提出一种基于层次子空间的ReliefF特征选择算法，将原始特征集划分为具有层次结构的子空间，并利用邻域粗糙集理论来计算低层子空间的局部依赖度，能在高维小样本数据上高效率地批量剔除冗余特征.此外，为了考量不同特征组合对结果的影响，引入“局部领导力”的概念，保留部分子空间中“带队”能力较强的特征，从局部和全局的角度共同给予特征更加客观的评价.在六个微阵列基因数据集上的实验表明，与现有方法相比，提出的方法更高效，而且能保持良好的分类性能.

关键词： 高维小样本数据 ; 特征选择 ; ReliefF ; 层次子空间 ; 邻域粗糙集

Abstract

High⁃dimensional small sample data has much higher feature dimensions than the number of samples，which usually contains a large number of redundant features. ReliefF algorithm has the following challenges when dealing with such data. Most of the existing improved ReliefF algorithms eliminate redundant features by calculating the mutual information between features，which is not applicable to high⁃dimensional data. Classifying by intercepting a number of features with the highest relevance to the label may not be the optimal choice because it does not consider the impact of different feature combinations on the classification performance. In this paper，we propose a ReliefF feature selection algorithm based on hierarchical subspaces，which divides the original feature set into subspaces with hierarchical structure and calculates the local dependencies of the lower subspaces by using the neighborhood rough set theory，which eliminates redundant features in batch with high efficiency on high⁃dimensional small sample data. In addition，in order to consider the influence of different feature combinations on the results，the concept of “local leadership” is introduced，and the features with stronger “leading” ability in some subspaces are retained to give a more objective evaluation of the features from both local and global perspectives. Experiments on six microarray gene datasets show that the proposed method is more efficient than existing methods and maintains good classification performance.

Keywords： high⁃dimensional small sample data ; feature selection ; ReliefF ; hierarchical subspace ; neighborhood rough set

PDF (839KB) 元数据多维度评价相关文章导出 EndNote| Ris| Bibtex 收藏本文

本文引用格式

程凤伟, 王文剑, 张珍珍. 面向高维小样本数据的层次子空间ReliefF特征选择算法. 南京大学学报（自然科学）[J], 2023, 59(6): 928-936 doi:10.13232/j.cnki.jnju.2023.06.003

Cheng Fengwei, Wang Wenjian, Zhang Zhenzhen. Hierarchical subspace ReliefF feature selection algorithm for high⁃dimensional small sample data. Journal of nanjing University[J], 2023, 59(6): 928-936 doi:10.13232/j.cnki.jnju.2023.06.003

随着互联网技术的飞速发展，信息的多样化及信息的产生速度有质的飞跃，使数据呈爆发式增长，数据挖掘^［1］需要分析的对象也愈加复杂，如自然语言处理领域中的文本文档数据^［2］、计算机视觉领域中的图像数据^［3-4］和生物信息学领域中的基因表达数据等^［5-7］，这些数据具有高维性和小样本的共性，即特征维数远远高于样本数.这类数据通常有成百上千个特征，而且，随着特征维度的急剧增加，冗余特征、噪声特征以及无关的特征都降低了分类模型的性能，因此，降维是机器学习和模式分类中的一项重要任务，特征选择是一种受到广泛关注的降维手段^［8］.

ReliefF算法^［9］是一种成功的特征选择器，因简单有效而被广泛研究，其前身为Relief算法，1992年由Kira and Rendell^［10］提出，根据各个特征和类别的相关性赋予特征不同的权重来处理两类数据的分类问题.ReliefF算法是Relief算法的多类扩展，可以很好地增强对噪声的容忍性.现有工作往往聚焦于对ReliefF算法在近邻表达^［11-12］、样本效率^［13］、标签相关性^［14-15］等方面的改进，或试图克服其在不同类型任务上面临的挑战，包括回归问题^［16］、数据缺失^［17-18］以及数据非平衡^［19-20］等.此外，ReliefF算法已在入侵检测^［21］、医疗诊断^［22-23］以及图像分类^［24］等实际领域中取得了成功应用.传统的ReliefF算法虽然可以很好地对特征进行排序，但无法去除特征冗余，即得到的特征子集中仍存在冗余项，这些冗余特征会影响分类的性能^［25-27］.针对这一问题，陈平华等^［28］将基于互信息特征选择的手段与ReliefF算法结合，利用ReliefF算法得到特征权重，再通过计算特征与特征间的互信息来剔除冗余特征.但当特征维数较高时，启发式地计算特征与特征之间的互信息的代价巨大，这类方法变得不再适用.而高维小样本数据的样本量较少，本文针对数值型的微阵列基因数据，采用邻域粗糙集理论来度量特征子集及特征的依赖度，从而剔除冗余信息，这比计算互信息的方法^［26-29］更高效.

特征维数较高时，在分类任务中构造特征子集通常采用“一刀切”的方式，即截取与标记相关性较高的若干特征来进行分类，但这种方式忽略了特征组合对分类结果的影响.在特征选择中，将权重高的特征组合起来不一定有好的分类性能，因此前m个特征组成的子集不一定是分类性能最好的特征子集^［30］.基于子空间的技术是一种很好的考虑全局信息的手段，刘景华等^［31］提出基于局部子空间的特征选择方法，根据重要性的不同程度在子空间中设定不同的采样比例来进行选择，以提高算法的分类性能.然而，该方法基于互信息来剔除冗余特征，在特征维数较高时代价较高，且该方法按特征权重的大小排序后进行采样来选择特征，没有考虑不同的特征组合对分类性能的影响.

针对以上问题，本文提出基于层次子空间的ReliefF特征选择算法（Hierarchical Subspace⁃Based ReliefF，HS⁃ReliefF），其主要思想是，首先，将原始特征集划分成具有两层层次结构的子空间，其中高层子空间利用随机法划分获得，低层子空间按照ReliefF算法对特征赋权的大小排序后进行升序均匀划分获得；然后，利用邻域粗糙集理论来度量低层子空间的局部依赖度，经阈值筛选后批量地剔除冗余特征；最后，提出“局部领导力”的概念，保留部分无法直接剔除的子空间中“带队”能力较强的特征.重复多次以上过程来求取特征权重的均值，得到最终的特征权重向量，根据实际情况挑选特征子集进行后续的分类任务.

1 相关工作

1.1　ReliefF

ReliefF算法^［9］是Relief算法的扩展，其通过选取k个最近邻样本点来应对不完备和噪声数据，使特征选择器更加鲁棒.ReliefF算法从训练集 $D = {\{(x_{n}, y_{n})\}}_{n = 1}^{N}$ 中随机选择一个样本 $R_{i}$ ，然后从和 $R_{i}$ 同类的样本中选取k个最近邻样本 $N H_{t} (t = 1, \dots, k)$ ，同时，从和 $R_{i}$ 不同类的样本中寻找k个最近邻样本 $M_{t} (t = 1, \dots, k)$ .ReliefF更新特征的权重如下：

\begin{array}{l} 𝒲_{j} = 𝒲_{j} - \sum_{t = 1}^{k} \frac{d i f f (j, R_{i}, N H_{t})}{m \times k} + \\ \sum_{C \neq c l a s s (R_{i})} \frac{\frac{P (C)}{1 - P (c l a s s (R_{i}))} \sum_{t = 1}^{k} d i f f (j, R_{i}, N M_{t} (C))}{m \times k} \\ j = 1,2, \dots, I \end{array}

(1)

其中， $N M_{t} (C)$ 为第C个不同类的第t个最近邻点， $P (C)$ 为类C的先验概率，以上过程重复m次.

1.2　邻域粗糙集

粗糙集理论中通常把特征称为属性，本文涉及的邻域粗糙集的相关内容均用属性表示特征.本节主要介绍邻域粗糙集下的正域、依赖以及属性的重要度^［32］.

定义1

给定实数空间上的非空有限集合 $U = \{x_{1}, x_{2}, \dots, x_{n}\}$ ，对于U上的任意样本 $x_{i}$ ，定义 $δ ⁃邻域$ 为：

δ (x_{i}) = \{x |x \in U, d i s t (x, x_{i}) \leq δ\}

(2)

其中， $d i s t (x, x_{i})$ 为距离函数， $δ \geq 0$ .

定义2

给定一邻域决策系统 $N D S = 〈U, A, D〉$ ，决策属性D将论域U划分为N个等价类 $(X_{1}, X_{2}, \dots, X_{N}), \forall B \subseteq A$ ，则决策属性D关于特征子集B的上、下近似分别为：

\bar{N_{B}} D = ⋃_{i = 1}^{N} \bar{N_{B}} X_{i}

(3)

\underset{̲}{N_{B}} D = ⋃_{i = 1}^{N} \underset{̲}{N_{B}} X_{i}

(4)

其中，

\bar{N_{B}} X = \{x_{i} |δ_{B} (x_{i}) ⋂ X \neq \emptyset, x_{i} \in U\}

(5)

\underset{̲}{N_{B}} X = \{x_{i} |δ_{B} (x_{i}) \subseteq X, x_{i} \in U\}

(6)

可得决策系统的正域为：

P O S_{B} (D) = \underset{̲}{N_{B}} D

(7)

定义3

给定一邻域决策系统 $N D S = 〈U, A, D〉, \forall B \subseteq A$ ，决策属性D对条件属性集B的依赖度为：

γ_{B} (D) = \frac{|P O S_{B} (D)|}{|U|}

(8)

若 $γ_{B - a} (D) < γ_{B} (D)$ ，那么a对于B是必不可少的；否则， $γ_{B - a} (D) = γ_{B} (D)$ ，那么a是多余的，D对于子集B中的属性a的依赖度为0.

定义4

给定一邻域决策系统 $N D S = 〈U, A, D〉, B \subseteq A, \forall a \in B,$ 属性a的重要度定义为：

s i g (a, B, D) = γ_{B} (D) - γ_{B - a} (D)

(9)

2 基于层次子空间的ReliefF特征选择算法

简单地说，HS⁃ReliefF算法主要包含两部分：一是结合层次子空间技术与邻域粗糙集理论来批量地剔除冗余特征；二是引入“局部领导力”考量特征对其所处子空间的相对依赖程度，保留部分较为重要的特征.

2.1　批量剔除冗余特征

高维小样本数据的特点之一是特征维数较高.子空间（Subspace）技术是一种有效的特征粒化手段，将原始的高维特征空间降低为多个低维的特征空间，这样可以从局部角度处理数据，或使用契合分布式模型、集成模型等，提高计算效率与性能.刘景华等^［31］提出局部子空间技术，即通过计算特征与标记集合之间的互信息来对特征进行排序，按特征权重的大小将原始特征集均匀地划分为三个子空间，根据不同的重要程度在子空间中设定不同的采样比例，进一步在每个子空间中计算特征与特征之间的互信息来剔除冗余特征.显然，此方法仅适用于特征维数较低的数据，因为在高维数据中启发式地计算特征与特征之间的互信息的代价较大，且度量单个特征的重要度的过程在大部分情况下也是多余的，因此，批量地剔除冗余特征不失为一个较好的选择.本文提出一种层次子空间的手段，将原始特征集划分成具有两层层次结构的子空间，具体操作如下.

（1）利用随机法将原始特征集划分为K个子空间，这一层为两层结构中的高层，记为H level.与刘景华等^［31］按照权重大小划分子空间的方法相比，随机法考虑了不同特征组合对分类性能的影响，且本文采取多次随机划分求取平均的方式来增强模型的鲁棒性.

（2）高层中的每个子空间需要进一步进行划分.在ReliefF算法对特征排序的基础上，按照权重大小对H level的K个子空间依次进行均匀划分，得到 $K \times N$ 个子空间，这一层为两层结构中的低层，记为L level.此过程是为接下来批量剔除冗余特征做准备.

高维小样本数据的另一个特点是样本数量较少.和计算特征与特征之间互信息的方法相比，利用邻域粗糙集来构造数值型数据的特征重要度要简单得多，在划分好的子空间的基础上，依次度量低层子空间的依赖度，直接剔除依赖度小于阈值的子空间，便可以高效地批量剔除冗余特征.

定义5

给定一邻域决策系统 $N D S = 〈U, A, D〉$ ，A为原始特征集， $\forall B \subseteq A, B$ 为其中任意一个H level子空间， $\forall R \subseteq B, R$ 为子空间B下的任意L level子空间，则在高层子空间B下，决策属性D对低层子空间R的依赖度为：

γ_{R} (D) = \frac{|P O S_{R} (D)|}{|U|}

(10)

定义6

给定一邻域决策系统 $N D S = 〈U, A, D〉$ ，A为原始特征集， $\forall B \subseteq A, B$ 为其中任意一个H level子空间， $\forall R \subseteq B, R$ 为子空间B下的任意L level子空间，则在高层子空间B下，低层子空间R的重要度定义为：

s i g (R, B, D) = γ_{B} (D) - γ_{B - R} (D)

(11)

定义5和定义6给出了低层子空间的局部依赖度和局部重要度，通过设置阈值来剔除重要度较小的子空间，达到批量剔除冗余特征的目的.

2.2　考虑局部领导力的特征加权方法

高层子空间使用随机法划分获得，经过多次随机划分求取平均的方式可以增强模型的鲁棒性.随机划分的另一个好处是可以对重要度不同的特征进行随机组合，结合局部与全局的角度给予特征更客观的评价.因为低层子空间中特征的重要度是一个相对的概念，对于依赖度处于阈值边缘的低层子空间，不仅要剔除其中的冗余特征，还要对保留的特征进行进一步的评价.若子空间的整体依赖度很大且其中的冗余特征较多，则被保留的重要的特征“带队”能力越强，应给予更高的权重.对此，本文提出“局部领导力”的概念，即结合特征在子空间中的表现以及其所在子空间的整体表现来共同评价该特征.

定义7

给定一邻域决策系统 $N D S = 〈U, A, D〉$ ，A为原始特征集， $\forall B \subseteq A, B$ 为其中任意一个H level子空间， $\forall R \subseteq B, R$ 为子空间B下的任意L level子空间. $\forall a \subseteq R$ ，低层子空间R中属性a的重要度为：

s i g (a, R, D) = γ_{R} (D) - γ_{R - a} (D)

(12)

则该属性a的“局部领导力”（Local Leadership，LLs）定义为：

L L s (a, R, D) = γ_{R} (D) ∙ S o f t m a x (s i g (a, R, D))

(13)

其中，Softmax函数为：

S o f t m a x (z_{i}) = \frac{e^{z_{i}}}{\sum_{c}^{C} e^{z_{c}}}

(14)

其中，z_i 表示第i个属性的重要度，C为子空间R中的属性个数.Softmax函数能体现子空间中每个属性与其他属性的“差距悬殊”程度，这种差距的悬殊即反映了属性的“带队”能力；同时，结合当前子空间R的整体依赖度，构造属性a的“局部领导力”，在高层子空间多次随机划分的前提下，同时从局部和全局的角度为属性a额外增加更客观的评价来更新属性a的权重.更新公式为：

𝒲_{a} = 𝒲_{a} ∙ L L s (a, R, D)

(15)

2.3　基于局部子空间的ReliefF特征选择方法

前文介绍了层次子空间法以及考虑局部领导力的特征加权法.层次子空间法将原始特征集划分为具有层次结构的子空间，这样可以批量地剔除冗余信息；考虑局部领导力的特征加权法构造了“局部领导力”的评价标准，在保留部分重要特征的同时，可以给予特征更客观的评价.HS⁃ReliefF算法的详细步骤如下，示意图如图1所示.由于无法确定数据集中实际存在的冗余特征个数，设定输入参数T，表示在每个高层子空间中预设的剔除子空间的数量.

图1

新窗口打开| 下载原图ZIP| 生成PPT

图1 本文算法的示意图

Fig.1 The schematic diagram of our algorithm

算法1

HS⁃ReliefF算法

输入：数值型高维小样本数据的邻域决策系统 $N D S = 〈U, A, D〉$ ，构造层次子空间次数M，高层子空间个数K，低层子空间个数N，批量剔除冗余子空间的个数T以及重要度阈值θ，低层子空间保留重要特征的阈值δ.

输出：特征质量估计的向量 $𝒲$ .

Step 1.利用RliefF算法得到初始的特征权重向量 $𝒲$ ；

Step 2.对A进行随机划分，得到K个高层子空间 $\{B_{1},$

$B_{2}, \dots, B_{K}\}$ 及对应的特征权重向量 $𝒲_{j}, j = 1,2, \dots, K$ ；

Step 3.对 $𝒲_{j}$ 排序，按排序结果升序对当前子空间 $B_{j}$ 进行均匀划分，得到N个低层子空间 $\{R_{1}, R_{2}, \dots, R_{N}\}$ ；

Step 4.用式（11）依次计算前T个低层子空间的重要度，若重要度小于阈值θ，则直接剔除该子空间；否则，用式（13）依次计算该子空间中每个特征的局部领导力，并用式（15）更新特征的权重；

Step 5.重复M次步骤Step 2~4，求取平均值，返回最终的权重向量 $𝒲$ .

3 实验设计与结果

3.1　数据集及实验设置

为了测试提出的算法的有效性，选取六个微阵列基因数据集进行实验，表1为所有数据集的详细信息，所有数据均经过归一化处理.

表1 实验使用的数据集描述

Table 1 Description of datasets used in experiments

数据集	样本数	条件特征数	类别数
alon	62	2001	2
gravier	168	2906	2
shipp	77	7130	2
subramanian	50	10101	2
tian	173	12626	2
yeoh	248	12626	6

新窗口打开| 下载CSV

由于数据样本量较小，采取3折交叉验证，用KNN分类器对特征选择结果进行测试.对比算法为：特征选择结果采用全部特征的ReliefF算法（ReliefF）、特征选择结果截取前I个特征（Cut I）的ReliefF算法（ReliefF⁃CI）以及MFSLS算法^［31］.为公平起见，将MFSLS算法利用计算特征与标记集合的互信息得到的初始化特征权重改为利用ReliefF算法得到的特征权重，且该算法的采样比例直接选择最好的结果 $[0.6,0.3,0.1]$ ，即MFSLS⁃631.所有实验在3.6 GHz Intel Core和16 G内存的电脑上完成，Windows 10，Matlab R2014a.

3.2　参数选择

实验中的一个主要参数为最终挑选出来用于分类任务的特征子集的特征数I.由于MFSLS⁃631算法在构造子空间时的特殊性，其最终挑选的特征子集的大小固定为数据集全部特征维数的1/3，对此，本文在高维的微阵列基因数据上也保持MFSLS⁃631算法的参数设定.对于HS⁃ReliefF，ReliefF以及ReliefF⁃CI算法，设置I的大小占全部特征维数的比重的取值为 $[0.1,0.2,0.3,0.4,0.5]$ ，这样设置的目的是I较小时，可以体现特征选择结果的好坏，I较大时可以体现冗余特征剔除结果的好坏.下文中I的取值直接用比重代替特征数.

本文提出的HS⁃ReliefF算法中，影响冗余剔除的参数主要是预设的剔除子空间的数量T、剔除子空间时的重要度阈值θ以及低层子空间保留重要特征的阈值δ.其中，与参数I直接相关的是T和δ.根据HS⁃ReliefF算法中Step 4所述，参数T决定了需要进行筛选的特征的数量，即可能被剔除的特征的范围.T越大，说明需要筛选的特征越多，得到的结果越准确客观.最终挑选的特征子集的特征数由I决定，因此将参数T设定为：

T = ⌊\frac{S_{B} \cdot (1 - I)}{S_{R}}⌋

(16)

由于HS⁃ReliefF算法采用多次随机求取平均的方法，高层子空间及低层子空间的个数的设定对结果的影响不大，因此，实验中统一设定每个高层子空间包含100个左右的特征 $(S_{B} = 100)$ ，低层子空间包含10个左右的特征 $(S_{R} = 10)$ ，相应地，设置参数 $K = A / S_{B}, N = S_{B} / S_{R}$ .此外，子空间保留重要特征的阈值δ直接决定低层子空间中需要被剔除的冗余特征的数量，但由于无法准确获知冗余特征的具体数量，只能人为指定阈值δ，本文设定 $δ \in [0.1,0.4]$ ，并在3.3对阈值δ进行实验分析，选取最佳结果.最后，对于剔除子空间时的重要度阈值θ，Praveena et al^［22］指出θ应设置为一个非常贴近0的正数，本文设置 $θ = 0.01$ ，这样可以保守地批量剔除冗余特征，尽可能避免误删有用的特征.

3.3　实验结果及分析

为了保证实验对比的公平性，分别在挑选的特征子集维数相同和不同的情况下进行对比，实验结果如表2和表3所示，表中黑体字表示在各数据集上最好的结果.

表2 特征子集维数相同时各算法平均精度对比 $(I = 0.33)$

Table 2 The average accuracy of each algorithm with the same dimension of feature subset $(I = 0.33)$

数据集	ReliefF	MFSLS⁃631	ReliefF⁃CI	HS⁃ReliefF
alon	0.7318	0.7872	0.7993	0.8211
gravier	0.6667	0.6674	0.6682	0.6726
shipp	0.9190	0.8911	0.9431	0.9528
subramanian	0.6969	0.6662	0.6959	0.6959
tian	0.7725	0.7761	0.7782	0.7797
yeoh	0.8957	0.9254	0.9501	0.9501

新窗口打开| 下载CSV

表3 特征子集维数不同时各算法平均最大精度的对比 $(I \in [0.1,0.2,0.3,0.4,0.5])$

Table 3 The average maximum accuracy of each algorithm with different dimension of feature subset $(I \in [0.1,0.2,0.3,0.4,0.5])$

数据集	ReliefF	I=0.1		I=0.2		I=0.3		I=0.4		I=0.5
数据集	ReliefF	ReliefF⁃CI	HS⁃ReliefF	ReliefF⁃CI	HS⁃ReliefF	ReliefF⁃CI	HS⁃ReliefF	ReliefF⁃CI	HS⁃ReliefF	ReliefF⁃CI	HS⁃ReliefF
alon	0.7318	0.8224	0.8224	0.8135	0.8194	0.7973	0.8172	0.7809	0.7902	0.7810	0.7823
gravier	0.6667	0.6793	0.6830	0.6704	0.6764	0.6711	0.6734	0.6711	0.6748	0.6682	0.6696
shipp	0.9190	0.9443	0.9460	0.9591	0.9624	0.9479	0.9465	0.9431	0.9415	0.9251	0.9447
subramanian	0.6969	0.7252	0.7252	0.7031	0.7031	0.6984	0.6984	0.6935	0.7065	0.7378	0.7378
tian	0.7725	0.7776	0.7776	0.7796	0.7796	0.7811	0.7811	0.7811	0.7811	0.7812	0.7833
yeoh	0.8957	0.9562	0.9562	0.9567	0.9567	0.9516	0.9516	0.9380	0.9385	0.9300	0.9300

新窗口打开| 下载CSV

表2展示了在特征子集维数相同的情况下各算法用于分类任务的平均最大精度，其中特征子集的大小固定为数据集全部特征维数的1/3，即 $I = 0.33$ .由表可知，在统一特征维数的情况下，本文的HS⁃ReliefF算法能更有效地剔除冗余特征，提升分类性能；MFSLS⁃631算法在这些高维数据上表现欠佳，因为该算法在采样时舍弃了部分特征，这些特征在高维数据中可能同样是重要的，也正因如此，其性能表现不如“一刀切”的方法（ReliefF⁃CI）.

鉴于此，单独分析ReliefF⁃CI和HS⁃ReliefF算法在特征子集维数不同时表现出的性能差异，验证本文提出的方法在考虑特征组合方面的有效性，实验结果如表3所示.表3展示了在特征子集维数不同时ReliefF⁃CI和HS⁃ReliefF算法用于分类任务的平均最大精度对比，其中，ReliefF算法为基准算法，ReliefF⁃CI和HS⁃ReliefF算法在截取特征子集时保持相同的特征数.由表可知，本文的HS⁃ReliefF算法在大多数情况下都有最优或相当的性能.值得注意的是，当I=0.1，0.2和0.3时，ReliefF⁃CI和HS⁃ReliefF算法在subramanian，tian和yeoh数据集上表现的性能相当，而且都显著优于基准算法.这是因为上述三个数据集的特征维数都较高，I较小时选择的特征质量相当，几乎不受冗余特征的影响，因此，在增大I以后（I=0.4和0.5时），HS⁃ReliefF算法在剔除冗余特征方面的优势得到了部分体现.

此外，由于子空间保留重要特征的阈值δ决定了被剔除的冗余特征的数量，进而影响不同特征子集维数下的分类性能，本文在三个代表数据集alon，subramanian和tian上分析了HS⁃ReliefF算法在选择不同的δ时对分类性能的影响，实验结果如图2所示，图中不同的I对应的最高柱点与表3的结果互相对照，颜色越浅，性能越好.由图可见，当I很小（I=0.1，0.2和0.3）时，该算法在三个数据集上的分类性能几乎不受δ的影响，这是由于此时包含冗余特征的概率很小.I增大（I=0.4和0.5）时，阈值δ的选择会影响挑选特征子集的分类性能.在alon数据集上，整体性能随着I的增大呈下降趋势，因此，δ较小时，算法可以保留有价值的特征，表现更好；在subramanian和tian数据集上，算法的整体性能却呈上升趋势，因为δ较大时，算法更能剔除所选特征子集中的冗余特征，表现更好.

图2

新窗口打开| 下载原图ZIP| 生成PPT

图2 在不同维数的特征子集上HS⁃ReliefF算法阈值δ的选择对其分类性能的影响

Fig.2 Classification performance of HS⁃ReliefF with different threshold δ on different dimensional feature subsets

额外地，图3展示了各算法在六个数据集上的分类性能受特征子集维数的影响情况，其中，ReliefF和MFSLS⁃631算法始终保持固定的特征子集维数，在图中用实心点和实心块表示.根据分析，不同的数据集中包含的冗余特征数不同，当特征子集维数较小时，分类性能受到特征对于标记的分类信息影响，当特征子集维数较大时，分类性能受到特征子集中冗余特征的数量影响.由图可知，本文提出的算法无论在特征子集维数较小或较大时，都有不错的表现.

图3

新窗口打开| 下载原图ZIP| 生成PPT

图3 不同维数的特征子集下各算法分类性能对比

Fig.3 Accuracy of each algorithm on different dimension feature subsets

最后，对比MFSLS⁃631和HS⁃ReliefF算法处理数据的时间消耗，实验结果如表4所示，表中黑体字表示耗时较少.由表可见，高维数据中，计算特征与特征之间互信息的代价十分大.对于给定的邻域决策系统 $N D S = 〈U, A, D〉$ ，其时间复杂度为 $O (|U| ∙ {|A|}^{2})$ ，而利用邻域粗糙集理论处理数据的复杂度为 $O (|A| ∙ {|U|}^{2})$ ，由于高维小样本数据的样本数普遍很小，即 $|U| ≪ |A|$ ，因此，本文提出的HS⁃ReliefF算法在处理数据的时间消耗方面有很大优势.此外，HS⁃ReliefF算法始终在RliefF算法得到的初始特征权重向量上进行权重调整，没有增加额外的空间复杂度.

表4 各数据集上MFSLS⁃631和HS⁃ReliefF算法处理数据过程的平均时间(单位：s)对比

Table 4 Average dealing time (unit：s) of MFSLS⁃631 and HS⁃ReliefF on each dataset

数据集	MFSLS⁃631	HS⁃ReliefF
alon	57.37	3.44
gravier	157.01	25.63
shipp	857.29	25.81
subramanian	1774.95	18.69
tian	2780.76	186.54
yeoh	3173.63	309.65

新窗口打开| 下载CSV

4 结论

现有的改进ReliefF算法在高维小样本数据上通过计算特征与特征之间的互信息剔除冗余特征，代价较高，而且没有考虑特征之间的组合对分类性能的影响.因此，本文提出基于层次子空间的ReliefF特征选择算法HS⁃ReliefF，将原始特征集划分为具有层次结构的子空间，利用邻域粗糙集理论批量地剔除冗余特征，大大提高了算法的运行效率；同时，引入“局部领导力”的概念，考虑不同特征组合对算法性能的影响，从局部和全局的角度共同给予特征更客观的评价.

在六个微阵列基因数据集上的实验表明，与现有算法相比，HS⁃ReliefF更高效，且能保持良好的分类性能.值得说明的是，HS⁃ReliefF算法同时也是一种处理高维小样本数据的框架，可以很好地契合分布式、集成式等系统，更高效地完成任务.

算法的不足之处在于控制剔除冗余特征的阈值仍须人为指定，不能确定最佳特征子集.如何自适应地确定相关参数是下一步研究的重点.

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

Han

J W

， Kamber

Data mining：Concepts and techniques

The 2^nd Edition. San Francisco：Morgan Kaufmann Publisher，2007：1-18.