第12卷第4期 智能系统学报 Vol.12 No.4 2017年8月 CAAI Transactions on Intelligent Systems Aug.2017 D0I:10.11992/is.201609008 网络出版地址:http://kns.cmki.net/kcms/detail/23.1538.tp.20170407.1758.016.html 基于特征相关的谱特征选择算法 胡敏杰,林耀进,杨红和,郑荔平,傅为 (闽南师范大学计算机学院,福建漳州363000) 摘要:针对传统的谱特征选择算法只考虑单特征的重要性,将特征之间的统计相关性引人到传统谱分析中,构造 了基于特征相关的谱特征选择模型。首先利用Laplacian Score找出最核心的一个特征作为已选特征,然后设计了新 的特征组区分能力目标函数,采用前向贪心搜索策略依次评价候选特征,并选中使目标函数最小的候选特征加入到 已选特征。该算法不仅考虑了特征重要性,而且充分考虑了特征之间的关联性,最后在2个不同分类器和8个UC 数据集上的实验结果表明:该算法不仅提高了特征子集的分类性能,而且获得较高的分类精度下所需特征子集的数 量较少。 关键词:特征选择:谱特征选择;谱图理论:特征关联;区分能力;索搜策略;拉普拉斯;分类精度 中图分类号:TP18文献标志码:A文章编号:1673-4785(2017)04-0519-07 中文引用格式:胡敏杰,林耀进,杨红和,等.基于特征相关的谱特征选择算法[J].智能系统学报,2017,12(4):519-525. 英文引用格式:HU Minjie,LIN Yaojin,YANG Honghe,etal.Spectral feature selection based on feature correlation[J].CAAI transactions on intelligent systems,2017,12(4):519-525. Spectral feature selection based on feature correlation HU Minjie,LIN Yaojin,YANG Honghe,ZHENG Liping,FU Wei (School of Computer Science,Minnan Normal University,Zhangzhou 363000,China) Abstract:In the traditional spectrum feature selection algorithm,only the importance of single features are considered.In this paper,we introduce the statistical correlation between features into traditional spectrum analysis and construct a spectral feature selection model based on feature correlation.First,the proposed model utilizes the Laplacian Score to identify the most central feature as the selected feature,then designs a new feature group discernibility objective function,and applies the forward greedy search strategy to sequentially evaluate the candidate features.Then,the candidate feature with the minimum objective function is added to the selected features.The algorithm considers both the importance of feature as well as the correlations between features.We conducted experiments on two different classifiers and eight UCI datasets,the results of which show that the algorithm effectively improves the classification performance of the feature subset and also obtains a small number of feature subsets with high classification precision. Keywords:feature selection;spectral feature selection;spectral graph theory;feature relevance;discernibility; search strategy;Laplacian score:;classification performance 特征选择是指在原始特征空间中选择能让给 和不显著改变类分布情况下选择一个重要特征子 定任务的评价准则达到最优的特征子集的过程,是 集并且移除不相关或不重要的特征,使留下的特征 模式识别、机器学习等领域中数据预处理的关键步 具有更强的分辨率。其中评价准则是特征选择 骤之一【1]。其主要目标是在不显著降低分类精度 算法中的关键步骤,国内外研究者已设计了多种评 价准则,包括距离度量[)、信息度量[6和谱图理 收稿日期:2016-09-08.网络出版日期:2017-04-07 论[7-剧等方法。由于基于谱图理论的特征选择模型 基金项目:国家自然科学基金项目(61303131,61379021):福建省教 有厅科技项目UA14192). 的可理解性及其完备的数学理论,受到了广泛的 通信作者:胡敏杰.E-mail:zzhuminjie@sina.com, 关注[8-]
1); 第 12 卷第 4 期 智 能 系 统 学 报 Vol.12 №.4 2017 年 8 月 CAAI Transactions on Intelligent Systems Aug. 201 通信作者:胡敏杰.E-mail:zzhuminjie@ sina.com. 7 DOI:10.11992 / tis.201609008 网络出版地址:http: / / kns.cnki.net / kcms/ detail / 23.1538.tp.20170407.1758.016.html 基于特征相关的谱特征选择算法 胡敏杰,林耀进,杨红和,郑荔平,傅为 (闽南师范大学 计算机学院,福建 漳州 363000) 摘 要:针对传统的谱特征选择算法只考虑单特征的重要性,将特征之间的统计相关性引入到传统谱分析中,构造 了基于特征相关的谱特征选择模型。 首先利用 Laplacian Score 找出最核心的一个特征作为已选特征,然后设计了新 的特征组区分能力目标函数,采用前向贪心搜索策略依次评价候选特征,并选中使目标函数最小的候选特征加入到 已选特征。 该算法不仅考虑了特征重要性,而且充分考虑了特征之间的关联性,最后在 2 个不同分类器和 8 个 UCI 数据集上的实验结果表明:该算法不仅提高了特征子集的分类性能,而且获得较高的分类精度下所需特征子集的数 量较少。 关键词:特征选择;谱特征选择;谱图理论;特征关联;区分能力;索搜策略;拉普拉斯;分类精度 中图分类号:TP18 文献标志码:A 文章编号:1673-4785(2017)04-0519-07 中文引用格式:胡敏杰,林耀进,杨红和,等.基于特征相关的谱特征选择算法[J]. 智能系统学报, 2017, 12(4): 519-525. 英文引用格式:HU Minjie, LIN Yaojin, YANG Honghe, et al. Spectral feature selection based on feature correlation[ J]. CAAI transactions on intelligent systems, 2017, 12(4): 519-525. Spectral feature selection based on feature correlation HU Minjie, LIN Yaojin, YANG Honghe, ZHENG Liping, FU Wei (School of Computer Science, Minnan Normal University, Zhangzhou 363000, China) Abstract:In the traditional spectrum feature selection algorithm, only the importance of single features are considered. In this paper, we introduce the statistical correlation between features into traditional spectrum analysis and construct a spectral feature selection model based on feature correlation. First, the proposed model utilizes the Laplacian Score to identify the most central feature as the selected feature, then designs a new feature group discernibility objective function, and applies the forward greedy search strategy to sequentially evaluate the candidate features. Then, the candidate feature with the minimum objective function is added to the selected features. The algorithm considers both the importance of feature as well as the correlations between features. We conducted experiments on two different classifiers and eight UCI datasets, the results of which show that the algorithm effectively improves the classification performance of the feature subset and also obtains a small number of feature subsets with high classification precision. Keywords: feature selection; spectral feature selection; spectral graph theory; feature relevance; discernibility; search strategy; Laplacian score;classification performance 收稿日期:2016-09-08. 网络出版日期:2 4-07. 基金项目:国家自然科学基金项目( 613031 , 37902 - 6 0 1 0 3 1 1 7 特征选择是指在原始特征空间中选择能让给 定任务的评价准则达到最优的特征子集的过程,是 模式识别、机器学习等领域中数据预处理的关键步 骤之一[1-3] 。 其主要目标是在不显著降低分类精度 和不显著改变类分布情况下选择一个重要特征子 集并且移除不相关或不重要的特征,使留下的特征 具有更强的分辨率[4] 。 其中评价准则是特征选择 算法中的关键步骤,国内外研究者已设计了多种评 价准则,包括距离度量[5] 、 信息度量[6] 和谱图理 论[7-8]等方法。 由于基于谱图理论的特征选择模型 的可理解性及其完备的数学理论,受到了广泛的 关注[8-9] 。 育厅科技项目(JA14192). 福建省教
520· 智能系统学报 第12卷 根据数据是否带有标记,基于谱图理论的特征 阵用到类标记信息,那么对于给定的图G,其相似性 选择可分为有监督特征选择和无监督特征选 矩阵S为 择8-2)。无监督特征选择算法在构造相似性矩阵时 1 不考虑类信息,通常对给出的样本值采用核函数构 S,= :=y=k 造相似性矩阵。有监督特征选择算法将类信息引 0,其他 入相似性矩阵中,常根据类别个数来构造对应的相 式中n为类别为k的样本个数。 似性矩阵。利用谱图理论进行特征选择的主要思 令G为一无向有权图,则邻接矩阵W,=S(1≤ 想是对邻接图Laplacian矩阵进行谱分解,其特征向 i,j≤m),且W为对称矩阵。令度矩阵D为 量反映了样本的类属关系[。基于该思想,Zhao 等]设计了一个谱特征选择框架,框架根据相似性 Wi,j=i D= (1) 矩阵是否考虑类标记信息分别应用于有监督和无 0, j≠i 监督算法,而选择特征子集过程与具体学习器无 由式(1)可以看出度矩阵D是一个对角矩阵, 关,利用特征对样本分布的影响对特征进行排序。 对角线上的每个元素是邻接矩阵W每一行或每一 He等[uo]结合谱图理论和特征的局部保持能力提出 列的和。度矩阵可以解释为每个样本周围围绕的 了基于Laplacian得分的特征选择算法。Zhao[]和 其他样本的密集度,度矩阵中的元素越大,意味着 He[o]等基于谱图理论的特征选择均仅考虑每个单 有更多的样本靠近这个元素代表的样本。 独的特征按一定的可分性或统计判据进行排队以 由邻接矩阵和度矩阵得到相应的Laplacian矩 形成特征序列,并取靠前的特征子集进行学习。该 阵L和正则化的Laplacian矩阵 策略仅在各个特征间统计独立且类别正态分布时 较优,但特征间具有这种关系仅仅是极少数),实 罗=D-S,3=D立LD 根据Laplacian矩阵的性质[),给出下面定义: 际上特征空间中特征之间存在较为紧密的关联性。 定义1 Laplacian矩阵的最小特征值为0,对应 针对已有的基于谱图理论有监督特征选择算 特征向量为单位向量 法存在的上述问题,我们提出融合特征相关的谱特 let1=[11…1]I,L*1=0 征选择算法,在原始的整个特征空间中不仅考虑每 定义2对于任意一个n维向量x(数据集中的 一个特征的区分力,还考虑特征组的区分性能,迭 特征列),都满足下式成立: 代地寻找对保持数据的局部结构比上一组特征更 强的特征组合。由此,提出了基于特征相关的谱特 eR=∑g,x-)产 征选择算法(spectral feature selection based on 定义3对于任意一个n维向量x(数据集中的 feature correlation,SPFC)。实验结果表明,该算法不 特征列),任意一个实数,都有(特征列中的每个元 仅提高了特征选择的分类性能,而且获得了较高的 素减去一个相同的值得到的新特征列仍然保持结 分类精度下所需特征子集的数量较少。 果不变): 1 谱特征选择算法 Vx ER",VtE R,(x-t*e)L(x-t*e)=xLx 谱图理论说明,Laplacian矩阵的特征值与特征 谱特征选择算法的主要理论是谱图理论,本文 向量包含着数据集的样本分布结构。谱特征选择 研究的算法是以Laplacian Score特征选择算法为基 在选取有强识别度的特征时,以特征取值的分布是 础,因此本节只介绍图Laplacian矩阵谱分析。 否与样本分布的结构保持一致作为特征选择的评 假设训练样本集X=[x1x2…x]T,类标 价标准。例如在图1中,每个图形(三角和星)表示 记y=[y:y2…yn]T。用标量F(1≤i≤n)记 一个样本,形状不同意味样本在同一特征上的取值 为第i个特征,向量表示有样本在第i个特征上 不同,各圆形分别为类1和类2的区域,即同一区域 的取值,第j个样本可以表示成x=(ff行,…)。 内的样本属于同一类别。在图1左侧中属于同一类 样本分布的结构由邻接图G(V,E)表示,其中V为 的样本在特征F上取值近似相同,而不属于同一类 图的点集,图的第j个结点,∈V对应于训练样本中 的样本在特征F上取值不同,因此特征F对类1 的第j个样本x,E为图的边集,边e∈E的权重W 和类2就有很好的识别能力,此时称特征F的取值 对应第j个样本和第i个样本的相似度S(1≤i,j≤ 分布与样本分布一致。在图1右侧中特征2的取 m)。本文研究有监督谱特征选择,即构建相似性矩 值分布则与样本分布不一致,F2对类1和类2不具
根据数据是否带有标记,基于谱图理论的特征 选择 可 分 为 有 监 督 特 征 选 择 和 无 监 督 特 征 选 择[8-12] 。 无监督特征选择算法在构造相似性矩阵时 不考虑类信息,通常对给出的样本值采用核函数构 造相似性矩阵。 有监督特征选择算法将类信息引 入相似性矩阵中,常根据类别个数来构造对应的相 似性矩阵。 利用谱图理论进行特征选择的主要思 想是对邻接图 Laplacian 矩阵进行谱分解,其特征向 量反映了样本的类属关系[11] 。 基于该思想,Zhao 等[8]设计了一个谱特征选择框架,框架根据相似性 矩阵是否考虑类标记信息分别应用于有监督和无 监督算法,而选择特征子集过程与具体学习器无 关,利用特征对样本分布的影响对特征进行排序。 He 等[10]结合谱图理论和特征的局部保持能力提出 了基于 Laplacian 得分的特征选择算法。 Zhao [8] 和 He [10]等基于谱图理论的特征选择均仅考虑每个单 独的特征按一定的可分性或统计判据进行排队以 形成特征序列,并取靠前的特征子集进行学习。 该 策略仅在各个特征间统计独立且类别正态分布时 较优,但特征间具有这种关系仅仅是极少数[13] ,实 际上特征空间中特征之间存在较为紧密的关联性。 针对已有的基于谱图理论有监督特征选择算 法存在的上述问题,我们提出融合特征相关的谱特 征选择算法,在原始的整个特征空间中不仅考虑每 一个特征的区分力,还考虑特征组的区分性能,迭 代地寻找对保持数据的局部结构比上一组特征更 强的特征组合。 由此,提出了基于特征相关的谱特 征 选 择 算 法 ( spectral feature selection based on feature correlation,SPFC)。 实验结果表明,该算法不 仅提高了特征选择的分类性能,而且获得了较高的 分类精度下所需特征子集的数量较少。 1 谱特征选择算法 谱特征选择算法的主要理论是谱图理论,本文 研究的算法是以 Laplacian Score 特征选择算法为基 础,因此本节只介绍图 Laplacian 矩阵谱分析。 假设训练样本集 X = [x1 x2 … xm ] T ,类标 记y = [y1 y2 … ym ] T 。 用标量 F i (1≤i≤n) 记 为第 i 个特征,向量 f i表示所有样本在第 i 个特征上 的取值,第 j 个样本可以表示成 xj = (f 1 j ,f 2 j ,…,f n j )。 样本分布的结构由邻接图 G(V,E)表示,其中 V 为 图的点集,图的第 j 个结点 vj∈V 对应于训练样本中 的第 j 个样本 xj,E 为图的边集,边 eji∈E 的权重 Wij 对应第 j 个样本和第 i 个样本的相似度 Sij(1≤i,j≤ m)。 本文研究有监督谱特征选择,即构建相似性矩 阵用到类标记信息,那么对于给定的图 G,其相似性 矩阵 S 为 Sij = 1 nk , yi = yj = k 0, 其他 ì î í ï ï ïï 式中 nk 为类别为 k 的样本个数。 令 G 为一无向有权图,则邻接矩阵 Wij = Sij(1≤ i,j≤m),且 W 为对称矩阵。 令度矩阵 D 为 D = ∑ m j = 1 Wji, j = i 0, j ≠ i ì î í ï ï ïï (1) 由式(1)可以看出度矩阵 D 是一个对角矩阵, 对角线上的每个元素是邻接矩阵 W 每一行或每一 列的和。 度矩阵可以解释为每个样本周围围绕的 其他样本的密集度,度矩阵中的元素越大,意味着 有更多的样本靠近这个元素代表的样本。 由邻接矩阵和度矩阵得到相应的 Laplacian 矩 阵 L 和正则化的 Laplacian 矩阵 L L = D - S,L = D - 1 2 LD - 1 2 根据 Laplacian 矩阵的性质[5] ,给出下面定义: 定义 1 Laplacian 矩阵的最小特征值为 0,对应 特征向量为单位向量 let I = [1 1 … 1] T ,L∗I = 0 定义 2 对于任意一个 n 维向量 x(数据集中的 特征列),都满足下式成立: ∀x ∈ R n ,x TLx = 1 2 ∑ wij xi - xj ( ) 2 定义 3 对于任意一个 n 维向量 x(数据集中的 特征列),任意一个实数,都有(特征列中的每个元 素减去一个相同的值得到的新特征列仍然保持结 果不变): ∀x ∈ R n ,∀t ∈ R,(x - t∗e) T L(x - t∗e) = x TLx 谱图理论说明,Laplacian 矩阵的特征值与特征 向量包含着数据集的样本分布结构。 谱特征选择 在选取有强识别度的特征时,以特征取值的分布是 否与样本分布的结构保持一致作为特征选择的评 价标准。 例如在图 1 中,每个图形(三角和星)表示 一个样本,形状不同意味样本在同一特征上的取值 不同,各圆形分别为类 1 和类 2 的区域,即同一区域 内的样本属于同一类别。 在图 1 左侧中属于同一类 的样本在特征 F 1 上取值近似相同,而不属于同一类 的样本在特征 F 1 上取值不同,因此特征 F 1 对类 1 和类 2 就有很好的识别能力,此时称特征 F 1 的取值 分布与样本分布一致。 在图 1 右侧中特征 F 2 的取 值分布则与样本分布不一致,F 2 对类 1 和类 2 不具 ·520· 智 能 系 统 学 报 第 12 卷
第4期 胡敏杰,等:基于特征相关的谱特征选择算法 ·521. 有很好的识别能力。因此在谱特征选择算法中会 互性,因此需要考虑候选特征与已选特征之间的冗 选取F而不选F。 余性和交互性。本文在式(2)的基础上定义了特征 组的重要度公式如式(3)。为了度量每个候选特征 对已选特征的贡献程度,同时定义了式(4)来计算 候选特征的重要度。模型思想是:首先利用传统谱 特征选择算法选出使目标函数式(2)最好的一个特 征,然后以这个特征为核心据点作为已选特征,依 次逐个评价候选特征与已选特征的相关性,即依次 图1特征与样本分布一致性示意图 根据目标函数(式(3))评价特征组合后的图的保持 Fig.1 The characteristics and the sample distribution 能力,然后根据式(4)选出保持能力优于未组合时 consistency schematic diagram 的最强一个特征,并将该特征加人到已选特征中形 而谱特征选择算法将选择那些与样本分布结 成新的组合,接着对余下候选特征进行下一轮的迭 构一致的特征,即选择那些使得式(2)取较小值的 代。该算法不仅考虑了特征间的相关效应,而且通 特征: 过式(4)避免了特征间的冗余。 定义特征组相关的目标函数为 P(F)= s,.- (2) v(f) sqt(∑∑(S,fn-f)) 式中:F表示第r个特征,∫,是第r个特征向量f和 (Fs)= (3) f表示第r个特征上的i,j(1≤i,j≤m)个样本的取 多∑,G-Pn 值,V(f)表示第r个特征∫的方差。 k 一个随机变量x的方差定义为): 式中:F、表示已选出的特征子集,k表示已选出的 V(x)=(x-u)'dP(x) 特征子集中的特征个数,P(F,)表示已选出的特征 式中:M是数据的流行结构,u表示x期望值,dP是 子集对数据的识别能力。sq(∑∑S,,)评 一个概率度量。根据谱图理论[】,dP可以用对角矩 估已选的特征子集对样本空间的局部保持能力,通过 阵D估计出来,因此特征f,的方差V(f,)为 欧式距离计算各特征间的相关性,特征子集对样本局 V)=∑,fa-u,)2D 部保持能力越强,则sq(∑∑S,。-))越 式中u,表示第r个特征∫的期望值,定义为 ∑fD ∑,4-4n 小。 ∑,D 通过各特征的均方差来衡 ∑S,。-,)尸越小表示在样本分布结构图 量各特征对样本数据的区分能力,已选特征子集区 里近邻的样本在该特征上差异很小,即一个识别能 Σ∑.-4,)D。 力强的特征会使得S,大而(fm-f,)小,因而式(2)趋 分能力越强,则 越大。因此式 k 小。∑,f-u,)2D越大表示该特征在各样本上的 (3)越小则说明已选子集能力越强。 取值方差越大,一个区分能力强的特征应该会赋予 在式(3)的基础上通过式(4)评估候选特征中 同类样本近似的值而不同类样本差异大的值,即具 能提升已有特征子集的区分能力的特征,其目标函 有较大方差的特征具有较强的识别能力。因此式 数定义为 (2)通过谱图理论结合特征的局部信息保持能力和 argminRed(f.)1=(Fs UF)-(Fs)(4) 方差来进行特征选择。 式中:F,表示候选特征集合,∫:∈F,通过评估一个 2 基于特征相关的谱特征选择模型 新的特征∫能否使得同类样本距离小而不同类样 本距离大来衡量是否加入已选F,。又在候选特征 传统的谱特征选择算法采用单独最优特征组 集合里可能有多个∫:能提升已选子集的能力,由式 合的启发式搜索策略,用式(2)对每个特征单独度 (3)知新加入的∫:使得P(Fs)越小越好,因此在多 量其重要度,该策略并未考虑特征间的冗余度和交 个具有提升子集能力的候选特征中选择使
有很好的识别能力。 因此在谱特征选择算法中会 选取 F 1 而不选 F 2 。 图 1 特征与样本分布一致性示意图 Fig.1 The characteristics and the sample distribution consistency schematic diagram 而谱特征选择算法将选择那些与样本分布结 构一致的特征,即选择那些使得式(2)取较小值的 特征[7] : φ F r ( ) = ∑i,j Sij(f ri - f rj) 2 V(fr) (2) 式中:F r 表示第 r 个特征,fr 是第 r 个特征向量,f ri和 f rj表示第 r 个特征上的 i,j (1≤i,j≤m) 个样本的取 值,V fr ( ) 表示第 r 个特征 fr 的方差。 一个随机变量 x 的方差定义为[7] : V(x) = ∫ M (x - u) 2 dP(x) 式中:M 是数据的流行结构,u 表示 x 期望值,dP 是 一个概率度量。 根据谱图理论[7] ,dP 可以用对角矩 阵 D 估计出来,因此特征 fr 的方差 V(fr)为 V fr ( ) = ∑i (f ri - ur) 2Dii 式中 ur 表示第 r 个特征 fr 的期望值,定义为 ur = ∑i f ri Dii ∑i Dii æ è ç ç ö ø ÷ ÷ = ∑i f riDii ∑i Dii ∑i,j Sij(f ri - f rj) 2 越小表示在样本分布结构图 里近邻的样本在该特征上差异很小,即一个识别能 力强的特征会使得 Sij大而( f ri -f rj)小,因而式(2)趋 小。 ∑i (f ri - ur) 2Dii 越大表示该特征在各样本上的 取值方差越大,一个区分能力强的特征应该会赋予 同类样本近似的值而不同类样本差异大的值,即具 有较大方差的特征具有较强的识别能力。 因此式 (2)通过谱图理论结合特征的局部信息保持能力和 方差来进行特征选择。 2 基于特征相关的谱特征选择模型 传统的谱特征选择算法采用单独最优特征组 合的启发式搜索策略,用式(2)对每个特征单独度 量其重要度,该策略并未考虑特征间的冗余度和交 互性,因此需要考虑候选特征与已选特征之间的冗 余性和交互性。 本文在式(2)的基础上定义了特征 组的重要度公式如式(3)。 为了度量每个候选特征 对已选特征的贡献程度,同时定义了式(4) 来计算 候选特征的重要度。 模型思想是:首先利用传统谱 特征选择算法选出使目标函数式(2)最好的一个特 征,然后以这个特征为核心据点作为已选特征,依 次逐个评价候选特征与已选特征的相关性,即依次 根据目标函数(式(3))评价特征组合后的图的保持 能力,然后根据式(4)选出保持能力优于未组合时 的最强一个特征,并将该特征加入到已选特征中形 成新的组合,接着对余下候选特征进行下一轮的迭 代。 该算法不仅考虑了特征间的相关效应,而且通 过式(4)避免了特征间的冗余。 定义特征组相关的目标函数为 φ(FS ) = sqrt ∑ k r = 1∑i,j (Sij(f ri - f rj) 2 ( ) ∑ k r = 1∑i (f ri - ur) 2Dii k (3) 式中:FS 表示已选出的特征子集,k 表示已选出的 特征子集中的特征个数,φ Fs ( ) 表示已选出的特征 子集对数据的识别能力。 sqrt(∑ k r = 1 ∑i,j Sij(f ri -f rj) 2 ) 评 估已选的特征子集对样本空间的局部保持能力,通过 欧式距离计算各特征间的相关性,特征子集对样本局 部保持能力越强,则 sqrt(∑ k r = 1 ∑i,j Sij f ri - f rj ( ) 2 ) 越 小。 ∑ k r = 1 ∑i (f ri - ur) 2Dii k 通过各特征的均方差来衡 量各特征对样本数据的区分能力,已选特征子集区 分能力越强,则 ∑ k r = 1∑i (f ri - ur) 2Dii k 越大。 因此式 (3)越小则说明已选子集能力越强。 在式(3)的基础上通过式(4)评估候选特征中 能提升已有特征子集的区分能力的特征,其目标函 数定义为 argminRed fi ( ) f i∈FU = φ FS ∪ Fi ( ) - φ FS ( ) (4) 式中:FU 表示候选特征集合,fi∈FU,通过评估一个 新的特征 fi 能否使得同类样本距离小而不同类样 本距离大来衡量是否加入已选 Fs。 又在候选特征 集合里可能有多个 fi 能提升已选子集的能力,由式 (3)知新加入的 fi 使得 φ FS ( ) 越小越好,因此在多 个具 有 提 升 子 集 能 力 的 候 选 特 征 中 选 择 使 第 4 期 胡敏杰,等:基于特征相关的谱特征选择算法 ·521·
.522. 智能系统学报 第12卷 p(FsUf)-p(F,)最小的一个特征。 表1实验数据描述 根据式(4),可提出基于特征相关的谱特征选 Table 1 Experimental data description 择算法(SPF℃)的伪代码如算法1所示。 数据集 样本数 特征数 类别数 算法1基于特征相关的谱特征选择算法 AC 690 14 (SPFC) erx 690 15 2 heart 270 13 输入样本集X,类标记Y: ICU 200 20 3 输出F、特征相关后的特征序列。 rice 104 5 2 1)Fs=☑,Fu=[FF2.…Fm]; Ve 137 7 2 2)依据X、Y计算每两个样本间的相似度矩阵 wpbc 198 33 2 S(1≤i,j≤m); 200 101 17 3)依据相似度构建Laplacian图G,并计算W、 3.2 实验结果与分析 D、L; 为了验证SPFC算法的性能,实验分为两部分。 4)根据传统谱特征选择算法求出最具有识别 第1组实验与CFS4、ChiSquare)、FCBF16 力的一个特征∫ Laplacian、NRs以及Relief)算法进行比较由 Fs=Fs Uf,Fu=Fu-f; 特征子集诱导出来的分类精度。另一组实验采用 5)while F不为空 Friedman test!9]和Bonferroni-Dunn test2o]在统计上 6)根据式(3)计算p(Fs); 对比SPFC与其他算法在8个数据集上的实验结 7)for i=1 to length(F) 果。由于ChiSquare、Laplacian、FCFS、Relief这4种 if ((FsUf)-(Fs))>0 then 算法得到的是一个特征序列,而CFS、FCBF、NRS3 L(j)=o(FsUf)-o(Fs): 种算法得到的是子集约简,因此,ChiSquare、Fisher、 j=j+1; FCFS、Relief这4种算法得到的特征序列取前k个 end if 特征作特征子集,其中k为CFS、FCBF、NRS算法中 8)end for 得到的3个约简子集数量的最小值。此外,NRS算 9)将L按升序排序 法中的邻域参数值δ为0.10。在实验中,采用十折 Fs=FsUf(1),Fu=Fv-fLO); 交叉验证法进行评价特征子集的优劣,用KNN(K= 10)end while 10)、CART2个不同的基分类器来评价分类精度。 实验1为了比较特征选择后的分类精度,在表2 3 实验设计与对比 ~4中,分别采用KNN(K=10)、CART这2个不同的基 3.1实验数据 分类器进行特征子集分类精度的评价。此外,为了更 为了进一步验证SPFC算法的有效性,本文从 加直观地比较不同方法得到的特征子集的性能,表2,3 UCI(http://www.ics.uci.edu)中选择8个数据集, 中加粗的数值表示最高分类进度,下划线表示精度次 各数据集相应的描述信息见表1,在表1~3中 优,最后一行表示不同算法得到的特征子集的平均分 australian一credit数据集简写为AC, 类精度,最后一行中加下划线的数值表示平均分类精 VeteranLungCancer数据集简写为VE。 度最高的值。另外,括号里面的数值表示数据的标准 差,括号外面的数值表示分类精度。 表2不同特征选择算法在KNN分类器下的分类精度比较 Table 2 Classification accuracies of feature selection with different algorithms based on KNN % 数据集 SPFC Laplacian CFS ChiSquare FCBF NRS Relief AC 86.1(3.0) 84.7(4.4) 84.7(4.4) 86.6(3.1) 84.7(4.4) 85.2(4.8) 84.7(4.1) crx 83.8(1.7) 84.0(1.6) 83.4(1.7) 83.1(1.7) 83.4(1.7) 84.3(1.7) 84.4(1.8) heart 82.6(6.4) 84.0(4.2) 82.5(5.8) 84.0(4.3) 82.5(3.9) 80.0(8.7) 75.9(7.5) ICU 92.1(2.3) 91.5(3.3) 91.5(3.3) 91.5(3.3) 91.5(3.3) 89.9(6.1) 81.3(3.0) rice 82.7(10.0) 76.9(11.0) 76.9(11.0) 76.9(11.0) 76.9(11.0) 81.6(10.3) 78.9(11.4) Ve 75.8(12.4) 75.8(12.4) 75.8(12.4) 75.8(12.4) 75.8(12.4) 72.1(3.7) 70.7(1.6) wpbe 74.6(9.2) 74.6(9.2) 70.5(11.11) 70.5(11.11) 70.5(11.11) 73.6(9.3) 67.4(13.6) Z00 91.4(7.5) 91.4(7.5) 90.5(10.5) 86.1(8.7) 89.6(8.5) 74.3(10.0)】 87.2(10.0) 平均值 83.64 82.86 81.98 81.81 81.86 80.13 78.81
φ FS∪fi ( ) -φ FS ( ) 最小的一个特征。 根据式(4),可提出基于特征相关的谱特征选 择算法(SPFC)的伪代码如算法 1 所示。 算法 1 基于特征相关的谱特征选择算法 (SPFC) 输入 样本集 X,类标记 Y; 输出 FS 特征相关后的特征序列。 1)FS =⌀,FU = F 1 F 2… F n [ ] ; 2)依据 X、Y 计算每两个样本间的相似度矩阵 Sij(1≤i,j≤m); 3)依据相似度构建 Laplacian 图 G,并计算 W、 D、L; 4)根据传统谱特征选择算法求出最具有识别 力的一个特征 fi FS = FS ∪ fi,FU = FU - {fi}; 5)while FU 不为空 6)根据式(3)计算 φ FS ( ) ; 7) for i = 1 to length(FU) if φ FS∪fi ( ) -φ FS ( ( ) ) >0 then L(j)= φ FS∪fi ( ) -φ FS ( ) ; j = j+1; end if 8)end for 9)将 L 按升序排序 FS =FS∪fL(1),FU =FU -{fL(1) }; 10)end while 3 实验设计与对比 3.1 实验数据 为了进一步验证 SPFC 算法的有效性,本文从 UCI (http: / / www.ics. uci. edu) 中选择 8 个数据集, 各数据集相应的描述信息见表 1, 在表 1 ~ 3 中 australian _ credit 数 据 集 简 写 为 AC, VeteranLungCancer 数据集简写为 VE。 表 1 实验数据描述 Table 1 Experimental data description 数据集 样本数 特征数 类别数 AC 690 14 2 crx 690 15 2 heart 270 13 2 ICU 200 20 3 rice 104 5 2 Ve 137 7 2 wpbc 198 33 2 zoo 101 17 7 3.2 实验结果与分析 为了验证 SPFC 算法的性能,实验分为两部分。 第 1 组 实 验 与 CFS [14] 、 ChiSquare [15] 、 FCBF [16] 、 Laplacian [10] 、NRS [17]以及 Relief [18] 算法进行比较由 特征子集诱导出来的分类精度。 另一组实验采用 Friedman test [19]和 Bonferroni⁃Dunn test [20] 在统计上 对比 SPFC 与其他算法在 8 个数据集上的实验结 果。 由于 ChiSquare、Laplacian、FCFS、Relief 这 4 种 算法得到的是一个特征序列,而 CFS、FCBF、NRS 3 种算法得到的是子集约简,因此,ChiSquare、Fisher、 FCFS、Relief 这 4 种算法得到的特征序列取前 k 个 特征作特征子集,其中 k 为 CFS、FCBF、NRS 算法中 得到的 3 个约简子集数量的最小值。 此外,NRS 算 法中的邻域参数值 δ 为 0.10。 在实验中,采用十折 交叉验证法进行评价特征子集的优劣,用 KNN(K = 10)、CART 2 个不同的基分类器来评价分类精度。 实验 1 为了比较特征选择后的分类精度,在表 2 ~4 中,分别采用 KNN(K=10)、CART 这 2 个不同的基 分类器进行特征子集分类精度的评价。 此外,为了更 加直观地比较不同方法得到的特征子集的性能,表 2、3 中加粗的数值表示最高分类进度,下划线表示精度次 优,最后一行表示不同算法得到的特征子集的平均分 类精度,最后一行中加下划线的数值表示平均分类精 度最高的值。 另外,括号里面的数值表示数据的标准 差,括号外面的数值表示分类精度。 表 2 不同特征选择算法在 KNN 分类器下的分类精度比较 Table 2 Classification accuracies of feature selection with different algorithms based on KNN % 数据集 SPFC Laplacian CFS ChiSquare FCBF NRS Relief AC 86.1(3.0) 84.7(4.4) 84.7(4.4) 86.6(3.1) 84.7(4.4) 85.2(4.8) 84.7(4.1) crx 83.8(1.7) 84.0(1.6) 83.4(1.7) 83.1(1.7) 83.4(1.7) 84.3(1.7) 84.4(1.8) heart 82.6(6.4) 84.0(4.2) 82.5(5.8) 84.0(4.3) 82.5(3.9) 80.0(8.7) 75.9(7.5) ICU 92.1(2.3) 91.5(3.3) 91.5(3.3) 91.5(3.3) 91.5(3.3) 89.9(6.1) 81.3(3.0) rice 82.7(10.0) 76.9(11.0) 76.9(11.0) 76.9(11.0) 76.9(11.0) 81.6(10.3) 78.9(11.4) Ve 75.8(12.4) 75.8(12.4) 75.8(12.4) 75.8(12.4) 75.8(12.4) 72.1(3.7) 70.7(1.6) wpbc 74.6(9.2) 74.6(9.2) 70.5(11.11) 70.5(11.11) 70.5(11.11) 73.6(9.3) 67.4(13.6) zoo 91.4(7.5) 91.4(7.5) 90.5(10.5) 86.1(8.7) 89.6(8.5) 74.3(10.0) 87.2(10.0) 平均值 83.64 82.86 81.98 81.81 81.86 80.13 78.81 ·522· 智 能 系 统 学 报 第 12 卷
第4期 胡敏杰,等:基于特征相关的谱特征选择算法 .523. 表3不同特征选择算法在CART分类器下的分类精度比较 Table 3 Classification accuracies of feature selection with different algorithms based on CART 数据集 SPFC Laplacian CFS ChiSquare FCBF NRS Relief AC 84.2(4.5) 83.6(3.3) 82.6(7.3) 81.1(4.5) 82.4(7.5) 83.4(4.7) 80.5(4.0) crx 83.9(16.9) 82.0(13.4) 80.1(14.4) 79.5(13.6) 79.9(14) 82.4(15.4) 80.1(12.8) heart 81.1(7.9) 76.3(6.8) 77.0(6.9) 76.6(7.4) 77.7(7.4) 75.1(9.2) 77.7(7.8) ICU 92.1(2.3) 90.5(7.9) 90.5(7.9) 90.5(7.9) 90.5(7.9) 85.3(17.5) 92.6(2.3) rice 83.9(9.4) 83.9(9.4) 83.0(10.0) 83.0(10.0) 83.0(10.0) 82.0(11.7) 80.8(7.5) Ve 70.6(10.7) 70.6(10.7) 70.6(10.7) 70.6(10.7) 70.6(10.7) 68.7(11.5) 70.7(1.5) wpbe 73.2(8.8) 69.0(12.9) 72.6(9.5) 72.6(9.5) 72.6(9.5) 67.0(8.4) 64.4(20.3) Z00 96.9(9.8) 96.9(9.8) 93.6(10.1) 88.6(10.2) 89.6(8.5) 84.3(6.9) 87.7(10.5) 平均值 83.24 81.6 81.25 80.31 80.79 78.53 79.31 结合表2、3的实验结果可知: 式中:k代表对比算法个数,N表示数据集个数,R 1)从总体上看,SPFC算法相比CFS、ChiSquare、 表示第i个算法在8个数据集上的排序均值(见表 FCBF、Laplacian、NRS以及Relief算法在KNN、 4)。由表4结合式(5)算出KNN分类器下FF的值 CART基分类器下表现稳定,且均获得最高平均分 为2.18,cart分类器下Fe的值为3.05,又当显著性 类精度。相比考虑类信息的传统谱特征选择算法 水平a=0.1时F(6,42)=1.87,因此在两个分类器 Laplacian,SPFC算法优于Laplacian.。 下都拒绝了零假设(所有算法性能相等),这时还需 2)相比ChiSquare、Laplacian、Relief这3种同样 要结合特定的post-hoc test来进一步分析各个算法 获得特征系列的算法,SPF℃算法以相同的前k个特 性能的差异。本文采用显著性水平为0.1的 征在不同的基分类器下获得的平均分精度明显较 Bonferroni--Dunn test。在这里定义两个算法的不同 高,相比子集约简的算法CFS、FCBF、NRS,SPFC取 用下面的临界差: 它们子集约简数量的最小值在两个基分类器下分 类精度明显要高于NRS,在CART基分类器下SPFC k(k+1) CD=4 6/ 的分类精度高于CS、FCBF达两个百分点以上,而 在KNN基分类器下也显著高于CFS、FCBF。 在Bonferroni-Dunn test里显著性水平为0.1且 3)每一种算法均会在某一个分类器上某个数 7个算法对比时9.=2.394,因此CD=2.58(k=7,V= 据集上获得最高分类精度,但只有SPFC能在两个 8)。如果两个算法在所有数据集上的平均排序的 基分类器上多个数据集上获得最高分类精度。 差不低于临界差CD,则认为它们有显著性差异。图 SPF℃算法在数据集ICU、ice、zoo上性能提升更为 2给出了在两个分类器下SPFC算法与其他算法的 明显,在两个分类器上均达到最高。而ICU为混合 比较,其中,每个子图中最上行为临界值,坐标轴画 型数据,rice为连续型数据、zoo为离散型数据。说 出了各种算法的平均排序且最左(右)边的平均排 明SP℉C可以处理多类型数据集,在大部分各类型 序最高(低)。用一根加粗的线连接性能没有显著 数据集上SP℉C均能达到较好的稳定表现。 差异的算法组。 实验2为了进一步研究比较SPFC算法与其 从图2可以直观看出在KNN分类器下,SPEC 他算法在两个分类器下的分类性能是否明显不同, 算法显著优于Relief算法,虽然与其他算法没有显 我们采用Friedman test和Bonferroni-Dunn在统计上 著差别,但可以看出SP℉C算法性能要高于其他算 进行验证。Friedman统计值定义为 法;在CART分类器下SPFC算法性能显著优于算 法NRs、ChiSquare、Relief,而与算法Laplacain、CFS、 4 FCBF性能相当,但性能相当的同一组里SPFC算法 (N-1)x F=Nk-1))-号 (5) 要远远优于算法Laplacain、CFS、FCBF
表 3 不同特征选择算法在 CART 分类器下的分类精度比较 Table 3 Classification accuracies of feature selection with different algorithms based on CART % 数据集 SPFC Laplacian CFS ChiSquare FCBF NRS Relief AC 84.2(4.5) 83.6(3.3) 82.6(7.3) 81.1(4.5) 82.4(7.5) 83.4(4.7) 80.5(4.0) crx 83.9(16.9) 82.0(13.4) 80.1(14.4) 79.5(13.6) 79.9(14) 82.4(15.4) 80.1(12.8) heart 81.1(7.9) 76.3(6.8) 77.0(6.9) 76.6(7.4) 77.7(7.4) 75.1(9.2) 77.7(7.8) ICU 92.1(2.3) 90.5(7.9) 90.5(7.9) 90.5(7.9) 90.5(7.9) 85.3(17.5) 92.6(2.3) rice 83.9(9.4) 83.9(9.4) 83.0(10.0) 83.0(10.0) 83.0(10.0) 82.0(11.7) 80.8(7.5) Ve 70.6(10.7) 70.6(10.7) 70.6(10.7) 70.6(10.7) 70.6(10.7) 68.7(11.5) 70.7(1.5) wpbc 73.2(8.8) 69.0(12.9) 72.6(9.5) 72.6(9.5) 72.6(9.5) 67.0(8.4) 64.4(20.3) zoo 96.9(9.8) 96.9(9.8) 93.6(10.1) 88.6(10.2) 89.6(8.5) 84.3(6.9) 87.7(10.5) 平均值 83.24 81.6 81.25 80.31 80.79 78.53 79.31 结合表 2、3 的实验结果可知: 1)从总体上看,SPFC 算法相比 CFS、ChiSquare、 FCBF、 Laplacian、 NRS 以 及 Relief 算 法 在 KNN、 CART 基分类器下表现稳定,且均获得最高平均分 类精度。 相比考虑类信息的传统谱特征选择算法 Laplacian, SPFC 算法优于 Laplacian。 2)相比 ChiSquare、Laplacian、Relief 这 3 种同样 获得特征系列的算法,SPFC 算法以相同的前 k 个特 征在不同的基分类器下获得的平均分精度明显较 高,相比子集约简的算法 CFS、FCBF、NRS,SPFC 取 它们子集约简数量的最小值在两个基分类器下分 类精度明显要高于 NRS,在 CART 基分类器下 SPFC 的分类精度高于 CFS、FCBF 达两个百分点以上,而 在 KNN 基分类器下也显著高于 CFS、FCBF。 3)每一种算法均会在某一个分类器上某个数 据集上获得最高分类精度,但只有 SPFC 能在两个 基分类 器 上 多 个 数 据 集 上 获 得 最 高 分 类 精 度。 SPFC 算法在数据集 ICU、rice、zoo 上性能提升更为 明显,在两个分类器上均达到最高。 而 ICU 为混合 型数据,rice 为连续型数据、zoo 为离散型数据。 说 明 SPFC 可以处理多类型数据集,在大部分各类型 数据集上 SPFC 均能达到较好的稳定表现。 实验 2 为了进一步研究比较 SPFC 算法与其 他算法在两个分类器下的分类性能是否明显不同, 我们采用 Friedman test 和 Bonferroni⁃Dunn 在统计上 进行验证。 Friedman 统计值定义为 x 2 F = 12N k (k + 1) ∑ k i = 1 R 2 i - k (k + 1) 2 4 é ë ê ê ù û ú ú FF = (N - 1)x 2 F N(k - 1) - x 2 F (5) 式中:k 代表对比算法个数,N 表示数据集个数,Ri 表示第 i 个算法在 8 个数据集上的排序均值(见表 4)。 由表 4 结合式(5)算出 KNN 分类器下 FF 的值 为 2.18,cart 分类器下 FF 的值为 3.05,又当显著性 水平 a = 0.1 时 F(6,42)= 1.87,因此在两个分类器 下都拒绝了零假设(所有算法性能相等),这时还需 要结合特定的 post⁃hoc test 来进一步分析各个算法 性能 的 差 异。 本 文 采 用 显 著 性 水 平 为 0. 1 的 Bonferroni⁃Dunn test。 在这里定义两个算法的不同 用下面的临界差: CDα = qα k(k + 1) 6N 在 Bonferroni⁃Dunn test 里显著性水平为 0.1 且 7 个算法对比时 qα = 2.394,因此 CD= 2.58(k = 7,N= 8)。 如果两个算法在所有数据集上的平均排序的 差不低于临界差 CD,则认为它们有显著性差异。 图 2 给出了在两个分类器下 SPFC 算法与其他算法的 比较,其中,每个子图中最上行为临界值,坐标轴画 出了各种算法的平均排序且最左(右)边的平均排 序最高(低)。 用一根加粗的线连接性能没有显著 差异的算法组。 从图 2 可以直观看出在 KNN 分类器下,SPEC 算法显著优于 Relief 算法,虽然与其他算法没有显 著差别,但可以看出 SPFC 算法性能要高于其他算 法;在 CART 分类器下 SPFC 算法性能显著优于算 法 NRS、ChiSquare、Relief,而与算法 Laplacain、CFS、 FCBF 性能相当,但性能相当的同一组里 SPFC 算法 要远远优于算法 Laplacain、CFS、FCBF。 第 4 期 胡敏杰,等:基于特征相关的谱特征选择算法 ·523·
.524. 智能系统学报 第12卷 表4不同算法在两个分类器下的排序均值表 Table 4 Different algorithms under the two classifiers the mean of sorting table 数据集 SPFC Laplacian CFS ChiSquare FCBF NRS Relief KNN 2.13 3.13 4.44 4.06 4.56 4.38 5.31 CART 1.63 3.44 3.81 4.81 4.13 5.63 4.44 CD [3]ZHANG C,ARUN K,CHRISTOPHER R.Materialization 6 optimizations for feature selection workloads[J].ACM Relief SPEC transactions on database systems,2016,41(1):2. CFSNRSCHISquarplacian [4]曹晋,张莉,李凡长.一种基于支持向量数据描述的特 -FCBF 征选择算法[J].智能系统学报,2015,10(2): (a)KNN分类器 215-220 CD CAO Jin,ZHANG li,LI Fanchang.A feature selection algorithm based on support vector data description J]. Relief_ CAAI transactions on intelligent systems,2015,10(2): NRS- ChiSquare 215-220. [5]MANORANJAN D,LIU Huan.Feature selection for classification (b)CART分类器 [J].Intelligent data analysis,1997,1(3):131-156. 图2在KNN和CART分类器下SPEC与其他算法的比较 [6]SUN Yujing,WANG Fei,WANG Bo,et al.Correlation Fig.2 SPEC compared with other algorithms Under feature selection and mutual information theory based the CART and KNN classifier quantitative research on meteorological impact factors of 4结论 module temperature for solar photovoltaic systems[J]. Energies,2016,10(1):7. 本文针对传统的谱特征选择只考虑特征的单 [7]CVETKOVIC D M,ROWLINSON P.Spectral graph theory 独最优组合问题进行改进,提出基于谱图理论的特 [J].Topics in algebraic graph theory,2004:88-112. 征相关的特征选择算法,本文研究发现:1)引入特 [8 ZHAO Zheng,LIU Huan.Spectral feature selection for 征之间的统计相关性到谱特征选择中,能有效地解 supervised and unsupervised learning[C]//Proceedings of 决有用特征可能是冗余的问题:2)在公开的UCI数 the 24th international conference on Machine learning. ACM.2007:1151-1157. 据集上的实验结果表明,本文算法能够选择较少的 [9]ZHAO Zhou,HE Xiaofei,CAI Deng,et al.Graph 特征,获得较好的分类精度:3)由表2~4中的数据 regularized feature selection with data reconstruction[J]. 亦看出考虑特征间的相关性算法(SPEC)比不考虑 IEEE transactions on knowledge and data engineering, 特征间相关性算法(Laplacian)能显著提高特征子 2016,28(3):689-700. 集的分类性能。但由于本文实验采用欧式距离统 [10]HE Xiaofei,CAI Deng,NIYONGI P.Laplacian score for 计特征间的相关性,而欧式距离对于高维特征的计 feature selection[M].Cambridge:MIT Press,MA,2005, 算差值变化不大,因此对于高维特征间的相关性的 17:507-514. [11]BELABBAS M A,WOLFE P J.Spectral method in machine 设计有待进一步研究。 learning and new strategies for very large datasets [J]. 参考文献: Proceedings of the national academy of sciences,2009, 106(2):369-374. [1]LIN Yaojin,Li Jinjin,LIN Peirong,et al.Feature selection [12]WANG Xiaodong,ZHANG Xu,ZENG Zhigiang,et al. via neighborhood multi-granulation fusion[J].Knowledge- Unsupervised spectral feature selection with I 1-norm graph based systems,2014,67:162-168. J].Neurocomputing,2016,200:47-54. [2]MANORANJAN D,LIU Huan.Consistency-based search in [13]边肇祺,张学工模式识别[M].2版.北京:请华大学 feature selection[]].Artificial intelligence,2003,151(1): 出版社.2000. 155-176. [14]HALL M A.Correlation-based feature selection for discrete
表 4 不同算法在两个分类器下的排序均值表 Table 4 Different algorithms under the two classifiers the mean of sorting table 数据集 SPFC Laplacian CFS ChiSquare FCBF NRS Relief KNN 2.13 3.13 4.44 4.06 4.56 4.38 5.31 CART 1.63 3.44 3.81 4.81 4.13 5.63 4.44 (a) KNN 分类器 (b) CART 分类器 图 2 在 KNN 和 CART 分类器下 SPEC 与其他算法的比较 Fig.2 SPEC compared with other algorithms Under the CART and KNN classifier 4 结论 本文针对传统的谱特征选择只考虑特征的单 独最优组合问题进行改进,提出基于谱图理论的特 征相关的特征选择算法,本文研究发现:1) 引入特 征之间的统计相关性到谱特征选择中,能有效地解 决有用特征可能是冗余的问题;2)在公开的 UCI 数 据集上的实验结果表明,本文算法能够选择较少的 特征,获得较好的分类精度;3)由表 2 ~ 4 中的数据 亦看出考虑特征间的相关性算法( SPEC)比不考虑 特征间相关性算法( Laplacian) 能显著提高特征子 集的分类性能。 但由于本文实验采用欧式距离统 计特征间的相关性,而欧式距离对于高维特征的计 算差值变化不大,因此对于高维特征间的相关性的 设计有待进一步研究。 参考文献: [1]LIN Yaojin, Li Jinjin, LIN Peirong, et al. Feature selection via neighborhood multi⁃granulation fusion [ J]. Knowledge⁃ based systems, 2014, 67: 162-168. [2] MANORANJAN D, LIU Huan. Consistency⁃based search in feature selection[J]. Artificial intelligence, 2003,151(1): 155-176. [3] ZHANG C, ARUN K, CHRISTOPHER R. Materialization optimizations for feature selection workloads[J]. ACM transactions on database systems, 2016, 41(1): 2. [4]曹晋, 张莉, 李凡长. 一种基于支持向量数据描述的特 征选 择 算 法 [ J ]. 智 能 系 统 学 报, 2015, 10 ( 2 ): 215-220. CAO Jin , ZHANG li, LI Fanchang . A feature selection algorithm based on support vector data description [ J ]. CAAI transactions on intelligent systems, 2015, 10 ( 2): 215-220 . [5]MANORANJAN D, LIU Huan. Feature selection for classification [J]. Intelligent data analysis, 1997, 1(3): 131-156. [6] SUN Yujing, WANG Fei, WANG Bo, et al. Correlation feature selection and mutual information theory based quantitative research on meteorological impact factors of module temperature for solar photovoltaic systems [ J ]. Energies, 2016, 10(1): 7. [7]CVETKOVIC D M, ROWLINSON P. Spectral graph theory [J]. Topics in algebraic graph theory, 2004: 88-112. [8 ] ZHAO Zheng, LIU Huan. Spectral feature selection for supervised and unsupervised learning [ C] / / Proceedings of the 24th international conference on Machine learning. ACM, 2007: 1151-1157. [9 ] ZHAO Zhou, HE Xiaofei, CAI Deng, et al. Graph regularized feature selection with data reconstruction [ J]. IEEE transactions on knowledge and data engineering, 2016, 28(3): 689-700. [10]HE Xiaofei, CAI Deng, NIYONGI P. Laplacian score for feature selection[M].Cambridge: MIT Press, MA, 2005, 17: 507-514. [11]BELABBAS M A, WOLFE P J. Spectral method in machine learning and new strategies for very large datasets [ J ]. Proceedings of the national academy of sciences, 2009, 106(2): 369-374. [12] WANG Xiaodong, ZHANG Xu, ZENG Zhiqiang, et al. Unsupervised spectral feature selection with l 1⁃norm graph [J]. Neurocomputing, 2016, 200: 47-54. [13]边肇祺,张学工.模式识别[M]. 2 版. 北京: 清华大学 出版社, 2000. [14]HALL M A. Correlation⁃based feature selection for discrete ·524· 智 能 系 统 学 报 第 12 卷
第4期 胡敏杰,等:基于特征相关的谱特征选择算法 .525. and numeric class machine learning [C]//the 17th 作者简介: International Conference on Machine Learning.San 胡敏杰,女,1979年生,讲师,主要 Francisco:Morgan Kaufmann,2000:359-366. 研究方向为数据挖掘。 [15]ANDREAS W,ANDREAS P.Attacks on stegan ographic systems[M].Heidelberg,Berlin:Springer-Verlag,2000: 61-76. [16]YU Lei,LIU Huan.Efficient feature selection via analysis of relevance and redundancy [J].Journal of machine learning research,2004,5(1):1205-1224. 林耀进,男,1980年生,主要研究方 [17]HU Qinghua,YU Daren,LIU Jinfu,et al.Neighborhood 向为数据挖掘、粒计算。主持国家自然 rough set based heterogeneous feature subset selection[J]. 科学基金2项。发表学术论文60 Information sciences,2008,178 (18):3577-3594. 余篇。 [18]CRAMMER K,GILAD-BACHRACH R,NAVOT A.Margin analysis of the Ivq algorithm C]//Advances in Neural Information Processing Systems.2002,14:462-469. 杨红和,男,1969生,高级实验师 [19]FRIEDMAN M,A comparison of alternative tests of 主要研究方向为数字校园。 significance for the problem of m rankings[J].The annals of mathematical statistics,1940,11(1):86-92. [20]DUNN O J.Multiple comparisons among means[J].Journal of the american statistical association,1961,56(293): 52-64. 2017 Workshop on SAR in Big Data Era:Models, Methods and Applications During the last decade a series of SAR satellites has been launched,including Chinese Gaofen-3,providing great amount of SAR data with varied modes to meet the varieties of applications.It becomes a challenge to retrieve information from these big data.The main objective of this workshop is to share models,methods and applications of SAR data exploration in the big data era. The workshop includes different subjects,such as big SAR data modeling,large-scale intelligent SAR processing, SAR applications in big data frameworks.It will feature keynote presentations by distinguished researchers on this topics, most of them are IEEE GRSS members. Website:http://www.radi.ac.cn/BIGSARDATA2017/
and numeric class machine learning [ C ] / / the 17 th International Conference on Machine Learning. San Francisco: Morgan Kaufmann, 2000: 359-366. [15]ANDREAS W, ANDREAS P. Attacks on stegan ographic systems[M]. Heidelberg, Berlin: Springer⁃Verlag, 2000: 61-76. [16]YU Lei, LIU Huan. Efficient feature selection via analysis of relevance and redundancy [ J ]. Journal of machine learning research, 2004, 5(1): 1205-1224. [17]HU Qinghua, YU Daren, LIU Jinfu, et al. Neighborhood rough set based heterogeneous feature subset selection[ J]. Information sciences, 2008, 178 (18): 3577-3594. [18] CRAMMER K, GILAD⁃BACHRACH R, NAVOT A. Margin analysis of the lvq algorithm [ C] / / Advances in Neural Information Processing Systems. 2002, 14: 462-469. [19 ] FRIEDMAN M, A comparison of alternative tests of significance for the problem of m rankings[J]. The annals of mathematical statistics, 1940, 11(1): 86-92. [20]DUNN O J.Multiple comparisons among means[J]. Journal of the american statistical association, 1961, 56 ( 293): 52-64. 作者简介: 胡敏杰,女,1979 年生,讲师,主要 研究方向为数据挖掘。 林耀进,男,1980 年生,主要研究方 向为数据挖掘、粒计算。 主持国家自然 科学 基 金 2 项。 发 表 学 术 论 文 60 余篇。 杨红和,男,1969 生,高级实验师, 主要研究方向为数字校园。 2017 Workshop on SAR in Big Data Era: Models, Methods and Applications During the last decade a series of SAR satellites has been launched, including Chinese Gaofen⁃3, providing great amount of SAR data with varied modes to meet the varieties of applications. It becomes a challenge to retrieve information from these big data. The main objective of this workshop is to share models, methods and applications of SAR data exploration in the big data era. The workshop includes different subjects, such as big SAR data modeling, large⁃scale intelligent SAR processing, SAR applications in big data frameworks. It will feature keynote presentations by distinguished researchers on this topics, most of them are IEEE GRSS members. Website:http: / / www.radi.ac.cn / BIGSARDATA2017 / 第 4 期 胡敏杰,等:基于特征相关的谱特征选择算法 ·525·