连续型特征的特征选取方法

王宏威^{1, 2}，李国和¹，李雪³，吴卫江¹，李洪奇¹

(1. 中国石油大学(北京) 地球物理与信息工程学院 油气资源与探测国家重点实验室，北京，102249；

2. 渤海大学 信息科学与技术学院，辽宁 锦州，121013；

3. School of Information Technology and Electrical Engineering, the University of Queensland,

Brisbane, 4072, Australia)

摘要：根据对象在特征空间中的分布，划分连续特征空间为类别单一、边界清晰的多个子空间；把各个子空间分别投影到所有特征上，获取所有不同类别子空间对当前子空间特征分类能力的评估；通过构造分类能力评估矩阵，实现特征分类能力的特征排序。以特征排序为依据，选取特征子集，实现特征选取。实验结果表明，这种特征选取具有有效性和高效性。

关键词：数据约简；特征选取；连续型特征；决策表

中图分类号：TP18          文献标志码：A         文章编号：1672-7207(2011)S1-0651-05

Method of feature selection for continuous features

WANG Hong-wei^{1, 2}, LI Guo-he¹, LI Xue³, WU Wei-jiang¹, LI Hong-qi¹

(1. State Key Laboratory of Petroleum Resource and Prospecting, College of Geophysics and Information Engineering,

China University of Petroleum, Beijing 102249, China;

2. College of Information Science and Technology, Bohai University, Jinzhou 121013, China;

3. School of Information Technology and Electrical Engineering, the University of Queensland,

Brisbane, 4072, Australia)

Abstract: In terms of the distribution of objects and their classification labels, the continuous feature space was partitioned into a variety of subspaces, each one with clear edge and unique classification label. After the projection of all the subspaces to each feature, the quality of each feature was estimated for a subspace opposite to all the other subspaces with different classification labels by means of statistical significance. Through construction of a matrix by all the estimate qualities of all features of all the subspaces, all the features was ranked from the highest classifying power to the lowset on the matrix for the feature space. According to the ranked-feature set, the feature selection was completed. The experimental results illustrate that the feature selection is efficient and effective.

Key words: data reduction; feature selection; continuous attributes; decision table

特征选取在知识建模、自动控制参数优化等得到广泛应用^[1]。目前，特征选取主要是面向“离散型”特征，以“有监督”决策信息为约束，基于等价关系理论，采用与学习算法无关的“过滤”方法。而面向连续型特征的特征选取有如下2种方法：(1)对连续型特征进行离散化，再采用面向离散型特征的特征选取，但在离散化特征过程中容易导致特征的失真，从而影响到后续的特征选取精确性；(2)直接采用连续特征分类能力的“相关性”评估进行特征选取，如Relief系列^[2-4]特征选取。Relief系列包括Relief，ReliefF，RReliefF(回归)及其各种改进方法。ReliefF把Relief针对两分类扩展到多分类，并把kNN方法结合到每个特征分类能力的评估上，提高了特征评估的鲁棒性。但采用给定抽样数m的随机抽样方法，在一定程度上忽视了对象的分布全局性。针对这样的问题，Liu等^[5]根据每个类别的分布概率p，对其进行m×p抽样，使得特征分类能力评估更加合理。Huang等^[6]根据对象类别进行NN聚类，确保每个聚类中对象数最大，并把聚类数作为抽样数m，解决m的自动确定问题，最后以聚类中心为抽样样本进行特征分类能力的评估。Guo等^[7]采用kNN进行聚类，使得每一聚类包含同类别的对象尽量多，但最多可含有e个其他类别的对象，并以聚类中心为抽样样本，对每个聚类内部同类和异类的对象进行特征分类能力的评估外，还兼顾其他聚类参与特征的评估。不仅解决抽样数m的自动确定，且进一步考虑对象分布对特征分类能力评估的影响。当e=0时，该方法就变为Huang等的方法。这些方法除了采用对象在特征上投影距离作为对象分类能力评估外，主要存在的问题如下：(1)只考虑对象及其局部分布特性(临近方法)，但略显缺乏全局性；(2)只强调对象(点)的距离远近对特征分类能力的评估作用，但在分类问题上，只要能够区分对象的不同类别，距离长短是等效的。针对这些问题，本文作者提出一种基于对象分布的特征选取方法。

1  相关基本概念

1.1  信息系统与特征选取

信息系统是数据集的抽象表达^[8-11]，可由K=(U，A，V)表示，其中U={u₁，u₂，…，u_|U|}为对象集合(|U|为对象集合中元素的个数)；A={a_i|i=1，2，…，k}为对象的特征集；V={|i=1，2，…，k}，对象特征a_i的值域，表示对象u∈U在a_i上的投影，即a_i：U? ，a_i(u)?Va_i。当特征a_i为实型时，特征a_i为连续型特征，其值域Va_i为连续数据区间。当A=C∪D，且C≠Φ, D≠Φ，C∩D=Φ，称K为决策表DT，其中C为条件特征集，D为决策特征集。求解条件特征子集F_s?C，并使其具有不低于C的分类能力，称求解F_s过程称为特征选取。本文针对条件特征为连续型，决策特征为离散型的特征选取。

1.2  集合中心和半径

给定特征集A′?A，对任意集合S?U，相对特征集A′的中心和半径定义如下：

 (1)

 (2)

其中：dist为距离函数(如欧氏距离等)。

2  基于对象分布的特征选取

为了实现基于对象分布的特征选取(Feature selection for continuous features, FSCF)，引入以下一些概念。

2.1  同类子集及其优化

给定决策表DT=(U, CD, V)，根据条件特征C进行的最近邻(Nearest neighbour, NN)聚类，得到聚类簇Clus(U, C)，且满足：(1)对于"S_i?Clus(U, C)，|S_i|≥2，"u,v?S_i，D(u)=D(v)，并(2)如果"w?U，半径Radius(S_i {w}, C)>Radius(S_i, C)，则至少$x, y?U，D(x)≠D(y)，称以Radius(S_i, C)为半径的超球体为DT的一个同类子集(Same-label subclass set, SLSS)。一个决策表可以生成一个同类子集的集合SLSS_Set(DT)。SLSS_Set(DT)是连续特征空间的组成部分。对于决策表，具有相对稳定的SLSS_Set(DT)。显然，| SLSS_Set(DT)|≤|U|，有利于进行高效特征选取。如果|S_i|=1，那么认为S_i为噪声，应予删除。

2.2  特征分类能力评估及其评估矩阵

在决策表DT中，每个条件特征的分类能力是不同的，可以通过SLSS_Set(DT)进行评估。首先，确定同类子集"C_o?SLSS_Set(DT)在特征"c?C投影区间：

               (3)

其中：Z_a/2为在概率a下标准正态分布双百侧值，即：

        (4)

且Z_a/2?[0, 3.09]，对应概率a?[0, 1]。

对于同类子集，?SLSS_Set(DT)，且D()≠D()，同类子集和在特征c上相互分类能力如下：

    (5)

显然，DP_c(,, a)?[0, 1]，其含义：在特征c上，同类子集包含的对象越多越集中，而同类子集间相距越远，那么可分类不同类别同类子集的能力越强。DP_c(,, a)=1时，表示在统计概率a意义上，不同类别的,完全可由c进行识别。在等价关系中，同类子集为等价类。

在式(5)基础上，定义所有同类子集的特征分类能力评估矩阵FIM(Feature importance matrix)：

     (6)

其中：

        (7)

式中：特征c区别同类子集C_o与其他不同类别同类子集的区别能力评估。显然，[0, 1]。可以看出，FIM中每一行对应一个同类子集，每一列对应一个条件特征。

2.3  特征全集的特征排序

为了综合所有同类子集，对所有特征进行分类能力的综合评估，并给出特征分类能力从大到小对应的特征排序。首先在评估矩阵中增加一列Selected属性。当Selected取值为True或False时，表示该行(同类子集)是否不再参与特征排序。特征排序具体算法如下：

FSCF(FIM(DT, a), C)    ‘输入决策表的特征分类能力矩阵及条件特征集

If C≠Φ, then

‘分类能力最强的列(特征)

For "r?[1..|SLSS_Set(DT)|]  

‘每一行(同类子集)

For "c?C-RankedFeatureSet  ‘所有列(特征)

If c(r)≤c_max(r) then Selected(r)=True   

 ‘更新标记

If "r?[1..|SLSS_Set(DT)|]

   ‘所有行(同类子集)

and Selected(r)=True then Selected(r)=False  

 ‘所有行已均标记，则清除标记

RankedFeatureSet={c_max}RankingFeature(FIM(DT, a),C-{c_max})    ‘递归追加特征

Else

Return RankedFeatureSet

      ‘以分类能力从大到小得到排序特征集

Endif

从上述算法可以看出，首先确定一个同类子集最大分类能力的特征。如果该特征也是其他同类子集最大分类能力的特征，那么这些同类子集不再参与特征排序。从而得到根据分类能力、全局性的特征排序。

2.4  特征选取

根据特征排序结果RankedFeatureSet=1, f₂, …, f_n>，其中f_i∈A。根据特征子集1, f₂, …, f_k>(其中k≤n)，选定一个分类器，对数据集D进行分类精度的测试，直至k=n，最后选取分类精度最高和选取时间最小的特征子集为特征选取。

3  实验结果

本实验在联想昭阳E255 和Windows XP上， Visual Basic 6.0为开发平台，利用Access 2003为数据环境，实现SLSS_Set(DT)及FSCF。

3.1  SLSS_Set(DT)分类器

SLSS_Set(DT)是一个分类器。对于任意对象obj，具体分类规则：

  (13)

实验数据均来自UCI数据集，所有数据集进行10-Fold Cross Validation数据随机分组，a =78%，b = 100%(即Z_a/2=1，Z_b/2=3.09)，dist为欧氏距离，并进行10次实验(即共进行100次的求解)，再求识别精度的平均值。其他分类器的识别精度均来自相关文献报道(见表1)。可以看出，除了对Iris数据集的识别精度略微降低外，SLSS_Set(DT)对其他数据集识别精度都有所提高，说明SLSS_Set(DT)具有较好的分类功能。下面有关分类精度均采用SLSS_Set(DT)分类器进行验证。

表1  分类器识别精度对比

Table1 Comparison of classification accuracy

3.2  特征排序效果

Parkingson数据集有22个连续型条件特征，1个决策特征(共2类)，195个记录。实验参数a=78%，b=100%，e=0(即Z_a/2=1，Z_b/2=3.09)。为了说明FSCF的有效性，对数据集进行10次的10-Fold Cross Validation实验(共100次)，并从学习、识别时间开销和识别精度作为评价。实验结果如图1所示，其中“最先特征集”、“最后特征集”和“随机特征集”的含义是根据每一特征的分类能力，从大到小对所有特征进行排序后，“最先”、“最后”和“随机”选取若干特征构成的特征子集。从图1可以看出，(1)从统计意义上，“最先特征集”的分类能力最强，“最后特征集”分类能力最弱，而“随机特征集”的分类能力介于两者之间；(2)随着特征数的增加，识别精度在逐渐增加，但是多次出现局部最高值，说明特征子集可以提高识别精度，而且在识别精度高的位置，往往具有较低的时间开销。

采用其他UCI数据集进行实验，具有类似的实验结果。这些实验结果说明，通过同类子集确定特征的分类能力对特征进行排序是有效的。

3.3  特征选取效果

对Spectf数据集的实验是根据UCI给定的训练数据和测试数据进行的，并根据训练数据集进行特征选取和测试。对数据集进行10次的10-Fold Cross Validation实验(即进行100次的求解)，统计特征全集和特征选取的特征子集的识别精度和学习、识别时间的平均值，结果如表2所列。数据集中，前、后行分别为特征全集和特征选取的实验结果。除了Sonar数据集外，其他数据集采用特征子集的识别精度与采用特征全集的识别精度相比均有较明显提高，时间开销却有明显减少。尽管Sonar数据集的识别精度提高不明显，但特征数和时间开销却明显减少。特别说明的是：Iris数据集中，特征选取后得到的识别精度大于采用C4.5和特征全集的识别精度(见表1)。这些实验结果表明，这些特征子集优于特征全集的分类能力。

图1  10次实验平均值

Fig.1  Average values of 10 experiments

表2  识别精度的对比

Table 2  Comparison of classification accuracy with feature subset to original features

4  结束语

FSCF的特点如下：(1)不同类别子空间在同一特征轴上投影，只要投影不重叠，具有等同的分类能力，而不是以距离作为分类能力的评估；(2)只考虑特征分类不同类别的能力，凸显特征的分类能力，减少分类能力评估计算量；(3)通过分类能力评估矩阵，强调能有效分类类别的特征优先排序，使得特征排序更加客观；(4)采用“特征分类能力”为启发信息，实现分类能力强的特征优先结合，得到较优的一个特征选取。

参考文献：

[1] Liu H, Motoda H. Feature selection for knowledge discovery & data mining[M]. Boston: Kluwer Academic Publishers, 1998.

[2] Kira K, Rendell L A. A practical approach to feature selection[C]//Sleeman D, Edwards P. Proc Intern Conf on Machine Learning. Aberdeen: Morgan Kaufman, 1992: 249-256.

[3] Kira K, Rendell L A. The feature selection problem: Traditional methods and a new algorithm[C]//Proceedings of the Tenth National Conference on Artificial Intelligence. Menlo Park: AAAI Press/The MIT Press, 1992: 129-134.

[4] Robnik-Sikonja M, Kononenko I. Theoretical and empirical analysis of relief and relief[J]. Machine Learning Journal, 2003, 53: 23-69.

[5] Huang Y, McCullagh P J, Black N D. Feature selection via supervised model construction[C]//Proc of the Fourth IEEE International Conference on Data Mining, 2004: 411-414.

[6] Liu H, Yu L, Dash M, et al. Active feature selection using classes[C]//Proc of PAKDD, 2003: 474-485.

[7] GUO Gong-de, Neagu D, Mark T D. Cronin: Using kNN model for automatic feature selection[J]. Pattern Recognition and Data Mining, 2005, 3686: 410-419.

[8] LIU Huan, Rudy S. Feature selection via discretization[J]. IEEE Transaction on Knowledge and Data Engineering, 1997, 9(4): 642-645.

[9] Blake C L, Merz C J. http://www.ics.uci.edu/~mlearn/ MLRepository.html. 1998

[10] Richeldi M, Lanzi P L. ADHOC: A tool for performing feature selection[C]//Proceedings of 8th International Conference on Tools with Artificial Intelligence, 1996: 102-105.

[11] 李国和. 基于类扩张矩阵的信息系统特征选取[J]. 计算机工程，2006, 32(17): 52-54.
LI Guo-he. Feature subset selection of information system based on similar extension matrix[J]. Computer Engineering, 2006, 32(17): 52-54.

(编辑 龙怀中)

收稿日期：2011-04-15；修回日期：2011-06-15

基金项目：国家高新技术研究发展计划资助项目(2009AA062802)；国家自然科学基金资助项目(60473125); 中国石油科技中青年创新基金资助项目(05E7013); 国家重大专项子课题资助项目(G5800-08-ZS-WX)

通信作者：王宏威(1980-)，男，吉林永吉人，博士研究生，讲师，从事人工智能，知识发现等研究；电话：15501083193，E-mail: bhu_whw@163.com