2017, Vol. 12
2. 浙江师范大学 数理与信息工程学院，浙江 金华 321004;
3. 河北大学 计算机科学与技术学院，河北 保定 071002;
4. 中国气象局 气象干部培训学院河北分院，河北 保定 071000
2. College of Mathematics, Physics and Information Engineering, Zhejiang Normal University, Jinhua 321004, China;
3. College of Computer Science and Technology, Hebei University, Baoding 071002, China;
4. Hebei Branch of Meteorological Cadres Training Institute, China Meteorological Administration, Baoding 071000, China
特征选择[1-2]是数据挖掘的重要预处理步骤，通过删除不必要特征，以达到降低算法复杂度，提高算法的性能。特征子集的评价至关重要，特征子集的评价准则或启发式确定后，特征选择问题从某种意义上来说就是在特征空间中搜索最优特征子集问题。研究人员提出了许多特征选择算法，这些算法有的是从设计特征子集搜索的方法考虑的，有的是从设计评价特征子集重要性的度量考虑的。
特征选择方法主要有筛选法(filter method)、封装法(wrapper method)和嵌入法(embedded method)3种分类。筛选法独立于学习算法，它依据启发式(如依赖度、互信息、不一致性等)搜索整体最优解。因为这类特征选择算法独立于数据挖掘算法，所以通用性好，适应各种数据挖掘任务，研究也最为广泛。实际上，粗糙集领域中的属性约简方法就是这类方法的一种典型代表[3-4]。Swiniarski等[5]针对模式识别问题，系统地研究了特征选择的粗糙集方法; Jensen等[6]提出了基于模糊粗糙集的方法，但是它在某些情况下不收敛; Bhatt等[7]针对文献[6]中的问题，深入研究模糊粗糙集特征选择算法的收敛性，得出了非常有价值的结论; Jensen等[8]研究了模糊粗糙集特征选择算法的可扩展性问题，并提出了相应的方法; 钱宇华等[9]提出了基于粗糙集正域逼近的属性约简(或特征选择)加速方法，该方法具有很高的计算效率，受到了广泛关注; 胡清华等[10]在邻域粗糙集框架下研究了异构特征选择问题，提出的特征选择算法可以处理实数值异构特征选择问题。
除了基于粗糙集知识的算法，其他特征选择问题代表性的工作还包括基于一致性的方法[2, 11-12]、基于互信息的方法[13-15]及基于依赖度的方法等[16-17]。
封装法以算法性能为标准衡量特征子集，由Kohavi等于1997年提出[18]。多年来，一些专家学者沿着封装法的思路做出了大量研究; Sindhwani等将多层感知器和SVM相结合，提出了基于最大输出信息的特征选择算法[19]; Yang等提出了一种随机扰动特征选择方法，具有较好表示能力[20]。封装法过于依赖学习算法，对于全部筛选出的特征子集，必须重复分类器训练的过程，虽然最终得到的特征子集比较理想，但复杂度太高，代价过大。
在嵌入法中，特征选择与分类器的构造同步完成。实际上，著名的ID3算法[21]和CART算法[22]都可以看作嵌入式特征选择方法。基于神经网络剪枝思想，Setiono等[23]提出了一种特征选择算法。该算法通过计算删除某个特征(剪枝)对神经网络性能的影响来选择特征。在此基础上，Shen等提出了基于SVM的敏感度特征选择算法[24]。而后，Perkins等提出了Grafting嵌入式特征选择算法[25]。
粒子群算法由Kennedy提出[26]，逐渐被专家学者广泛接受和应用。但是直到2001年关于粒子群算法的第一部专著Swarm Intelligence[27]出版后，粒子群算法才得到广泛应用。为解决PSO算法在连续空间中的局限性，Kennedy等[28]提出了离散二进制PSO算法。在此基础上，Chuang等[29]提出了一种改进的二进制粒子群算法(IBPSO)，有效简化了特征选择，并在医疗诊断基因表达领域取得了较好的效果; Chuang等[30]基于Catfish机制，提出了一种二进制粒子群特征选择算法，可避免过早收敛的问题; Wang等[31]提出了一种基于粗糙集的粒子群算法，具有较强的搜索能力能更快地寻找到最优解; Cervante等[32]提出了基于信息熵的BPSO方法，测试结果非常理想。Liu等[33]提出了一种集成邻域信息和粒子群算法的特征选择方法，结合粒子加权提高了算法的稳定性; Fong等[34]面向高维和数据流格式的大数据，提出了一种基于粒子群算法的特征选择方法，提高测试精度的同时降低了处理时间[34]。
本文选择相对分类信息熵作为适应度函数，用粒子群算法搜索最优特征子集，并与其他进化算法进行了实验比较，实验结果表明本文所提的方法更为有效。
1 基础知识 1.1 粒子群算法粒子群算法是一种群体搜索行为。群体由若干个粒子pi组成，pi包含位置信息xik和速度信息vik。位置信息xik表示pi在第k次迭代时其位置信息，速度信息vik表示pi在第k次迭代时移动的速度和方向。从一组初始粒子(初始种群)出发，通过一次次迭代，不断更新速度和位置信息，每个粒子不断向gbest和pbest靠近，最终找到整体最优解。方法过程如图 1所示，具体步骤见第2节。
|
图 1 PSO算法流程图 Fig.1 The flowchart of particle swarm optimization algorithm |
粒子群算法应用的关键是问题编码和粒子适应度评价标准。在问题编码上，显然二进制编码是最为合适的。在粒子适应度评价标准上，一个合适的适应度函数对特征子集的选择影响很大，因此适应度函数的设计是尤为关键的。
1.2 粗糙集定义1 设DT=(U, A∪D, V, f)为知识涉及的决策表。其中，U={x1, x2, …, xn}为论域; A={a1, a2, …, am}是描述对象的属性集合; D={d}，即目标概念唯一; V为属性值域; f:U×A→V为信息函数。
定义2 对于任意条件属性子集B⊆A，B的等价关系为
| $ \begin{array}{l} {\rm{IND}}\left( B \right) = \{ \left( {x,y} \right) \in U \times U\left| {\forall b \in B,} \right.{\rm{ }}\\ b\left( x \right) = b\left( y \right)\} \end{array} $ | (1) |
式中b(x)和b(y)分别是对象x和y在属性b上的属性值。
定义3 令X⊆U，B⊆A，X关于B的下近似为
| $ \underline B X = \{ x{\left| {\left[ x \right]} \right._B} \subseteq X\} $ | (2) |
定义4 令X⊆U，B⊆A，X关于B的上近似为
| $ \overline B X = \{ x{\left| {\left[ x \right]} \right._B} \cap X \ne \emptyset \} $ | (3) |
定义5 令X⊆U，B⊆A，X关于B的边界域为
| $ {\rm{BN}}\left( X \right) = \overline B X - \underline B X $ | (4) |
首先定义适用于特征选择问题的适应度函数。
对于形如DT=(U, A∪D, V, f)的决策表，B⊆A，B和D对U的划分表示为
| $ \begin{array}{l} U/B = {X_1} + {X_2} + \ldots + {X_m}\\ U/D = {Y_1} + {Y_2} + \ldots + {Y_k} \end{array} $ |
定义6 划分U/B相对于U/D的概率分布为
| $ {p_{ij}} = {\rm{ }}\frac{{\left| {{X_i} \cap {Y_j}} \right|}}{{\left| {{X_i}} \right|}} $ | (5) |
定义7 划分U/B相对于U/D的相对分类信息熵为
| $ H\left( {U/B} \right) = - \sum\limits_{i = 1}^m {\sum\limits_{j = 1}^k {\frac{{\left| {{X_i}} \right|}}{{\left| U \right|}}{\rm{ }}{p_{ij}}{{\log }_2}{p_{ij}}} } $ | (6) |
相对分类信息熵反映的不一致程度与其值成正比，因此值越小效果越好。本文所选择的适应度函数，即(6) 式定义的相对分类信息熵，可通过定理1的证明来验证其合理性[35]。
定理1 给定决策表DT=(U, A∪D, V, f)，假设A1, A2⊆A且A1⊆A2，则H(U/A2) ≤H(U/A1)。
定理1保证了本文提出的方法的收敛性，即能够以很高概率找到整体最优解。
算法1 基于粒子群算法的特征选择算法。
输入 离散值决策表DT=(U，A∪D，V，f)，群体大小N、惯性系数w、常量系数c1和c2、数据集维数D。
输出 A′⊆A。
1) 随机初始化大小为N的种群;
2) repeat;
3) for(i=1;i≤N; i=i+1);
4) 用式(6) 计算种群中每一个个体的适应度值;
5) 更新历史最佳位置best;
6) end for;
7) 更新全局最佳位置gbest;
8) for(i=1;i≤N; i=i+1);
9) for(d=1;d≤D; d=d+1);
10) 更新速度信息vid;
11) 更新位置信息xid;
12) end for;
13) end for;
14) until(满足终止条件时);
15) 输出A′。
本文选择适用于离散值特征选择的二进制粒子群算法，问题的解可用d维0-1向量表示，其中d是属性个数。向量的第i个分量为0或1表示属性是否被选择。特征选择的过程分为以下几步。
1) 随机产生N0个0-1向量(粒子)作为初始粒子群, 其中N0是种群的大小。
2) 利用式(6) 计算所有粒子的适应度值。
3) 更新粒子历史最优点pbest：将所有粒子的适应度值和其历史最佳点pbest做比对，择优更新pbest。
4) 更新全局最最优点gbest：将所有粒子的适应度值和全局最优点gbest做比对，择优更新gbest。
5) 根据上一步更新得到的pbest和gbest，更新粒子的速度和位置。其中速度是根据上一步得到的pbest和gbest按照公式(7) 进行更新：
| $ \begin{array}{l} v_i^{k + 1} = wv_i^k + {c_1}{\rm{rand}}\left( {{\rm{pbest}} - x_i^k} \right) + \\ {c_2}{\rm{rand}}({\rm{gbest}} - x_i^k) \end{array} $ | (7) |
这里需要注意的是，pi的位置信息xik中的每个xidk只能取0或1，相应的速度信息也发生了改变，用Sigmoid()函数将vidk映射到(0, 1) 区间上，决定xidk在下一代位置分量为1的概率，如公式(8)：
| $ \begin{array}{l} {x_{ij}} = \left\{ \begin{array}{l} 1,{\rm{rand}}\left( {{v_{i{\rm{ }}j}}} \right) < {\rm{Sigmoid}}\left( {{v_{ij}}} \right)\\ 0,{\rm{其他}} \end{array} \right.\\ {\rm{Sigmoid}}\left( {{v_{ij}}} \right) = \frac{1}{{1 + {{\rm{e}}^{ - {v_{ij}}}}}} \end{array} $ | (8) |
6) 若迭代次数已达到设定值，终止并输出当前gbest对应的解; 否则，令k=k+1转入2)。
粒子运动的步骤即全局最优解的求解过程，通过不断计算每个粒子的适应度值，粒子依靠自我认知能力和社会认知能力来搜索最优特征子集，逐渐向全局最佳位置靠拢，并最终得到理想结果。
3 实验结果及统计分析在实验过程中，选择规模大小和属性个数各异的8个离散UCI数据集进行实验。实验采用Win7操作系统PC机(Intel Core i3处理器，内存大小4 GB)。70%的样例用作训练，30%的样例用作测试。实验研究发现，当惯性系数取值在0.9~1.2时，粒子群算法在全局搜索和收敛能力上表现均较好[36]。惯性系数和加速系数在常用范围内多次实验，确定最终取值。惯性系数w取值为1。加速系数c1和c2取1.426 94，种群数目统一设定为20，终止代数设定为50。
首先选择与本文方法背景知识相关、时间复杂度相仿的方法进行比较，即选用粗糙集与粒子群算法相结合的RSPSO算法[31]和改进的二进制粒子群算法[29]。在表 1中给出本文方法与文献[31]和[29]两种方法实验对比结果，主要对比两个方面的差异，其中#Fs代表被选择的特征个数，Ac代表测试精度。更直观的结果见图 2~9所示。
|
表 1 实验结果比较 Tab.1 The comparison of experimental results |
|
图 2 在Kr-vs-Kp数据集上的实验结果 Fig.2 The experimental results of data set Kr-vs-Kp |
|
图 3 在Voting数据集上的实验结果 Fig.3 The experimental results of data set Voting |
|
图 4 在Mushroom数据集上的实验结果 Fig.4 The experimental results of data set Mushroom |
|
图 5 在Nursery数据集上的实验结果 Fig.5 The experimental results of data set Nursery |
|
图 6 在Car数据集上的实验结果 Fig.6 The experimental results of data set Car |
|
图 7 在Soybean数据集上的实验结果 Fig.7 The experimental results of data set Soybean |
|
图 8 在Tic-Tac-Toe数据集上的实验结果 Fig.8 The experimental results of data set Tic-Tac-Toe |
|
图 9 在SPECT数据集上的实验结果 Fig.9 The experimental results of data set SPECT |
通过上述实验，我们可以看出采用相对分类信息熵作适应度函数的粒子群算法与单纯粗糙集知识作为适应度函数的粒子群算法相比，在实验精度和筛选特征个数方面要明显占优。
接下来实验中，比较粒子群算法和遗传算法在处理特征选择上的优劣，对比方法为文献[35]中的采用相同适应度函数的遗传特征选择方法。从#Fs、Ac、σ和Time 4个方面进行了比较，结果列于表 2和表 3中。其中，#Fs表示选出的特征数，Ac表示测试精度，σ表示分类标准差，Time表示运行时间。更直观的实验结果如图 10~17所示。
|
|
表 2 与遗传算法比较的实验结果(1) Tab.2 The experimental results compared with genetic algorithm(1) |
|
|
表 3 与遗传算法比较的实验结果(2) Tab.3 The experimental results compared with genetic algorithm(2) |
|
图 10 在数据集Kr-vs-Kp上的实验结果(PSO与GA对比) Fig.10 The experimental results of data set Kr-vs-Kp (PSO, GA) |
|
图 11 在数据集Voting上的实验结果(PSO与GA对比) Fig.11 The experimental results of data set Voting(PSO, GA) |
|
图 12 在数据集Mushroom上的实验结果(PSO与GA对比) Fig.12 The experimental results of data set Mushroom(PSO, GA) |
|
图 13 在数据集Nursery上的实验结果(PSO与GA对比) Fig.13 The experimental results of data set Nursery(PSO, GA) |
|
图 14 在数据集Car上的实验结果(PSO与GA对比) Fig.14 The experimental results of data set Car(PSO, GA) |
|
图 15 在数据集Soybean上的实验结果(PSO与GA对比) Fig.15 The experimental results of data set Soybean(PSO, GA) |
|
图 16 在数据集Tic-Tac-Toe上的实验结果(PSO与GA对比) Fig.16 The experimental results of data set Tic-Tac-Toe(PSO, GA) |
|
图 17 在数据集SPECT上的实验结果(PSO与GA对比) Fig.17 The experimental results of data set SPECT(PSO, GA) |
从表 2、表 3、图 10~11可以看出，用粒子群算法选出的特征子集在测试精度总体上优于遗传算法，且收敛速度比遗传算法有大幅提升，筛选出的特征个数和运行时间较遗传算法有一定程度的提高，两者分类标准差基本相当。其原因在于，粒子群算法在迭代的过程中具有一定的记忆功能，能够在保持自身优势的同时感知全局走向，且不需要进行较多的参数设置，省去了遗传和变异的过程，实现起来更容易。实验结果说明本文方法是行之有效的。
为进一步验证方法的有效性，由上述两种方法分别对每个数据集随机实验10次，得到的10组测试结果组成两个10维向量，记为X1和X2，对X1和X2进行配对t检验，p值如表 4所示。
|
|
表 4 配对t检验p值 Tab.4 p values of paired t-test |
p值均较小，显著性差异较大，进一步证明了方法的可行。
4 结论本文选择相对分类信息熵作为适应度函数，用粒子群算法寻找最优特征子集，在解决离散值特征选择问题上效果较好，并与其他方法进行了比较。通过实验我们得出以下结论：1) 粒子群算法相比遗传算法过程更简单，省去了复杂的参数设置，容易实现; 2) 粒子群算法拥有较好的测试精度，且在选择的特征个数和运行时间方面都有一定程度的提高; 3) 粒子群算法收敛较快，可以更早得到拥有更好表示能力的特征子集。
| [1] |
GUYON I, GUNN S, NIKRAVESH M, et al. Feature extraction, foundations and applications[M]. Berlin: Springer, 2006.
( 0)
|
| [2] |
DASH M, LIU H. Feature selection for classification[J]. Intelligent data analysis, 1997, 1: 131-151. DOI:10.1016/S1088-467X(97)00008-5 (0)
|
| [3] |
PAWLAK Z. Rough sets[J]. Internationa journal of information and computer sciences, 1982, 11: 341-356. DOI:10.1007/BF01001956 (0)
|
| [4] |
苗夺谦, 李道国. 粗糙集理论、算法与应用[M]. 北京: 清华大学出版社, 2008.
(0)
|
| [5] |
SWINIARSKI R W, SKOWRON A. Rough set methods in feature selection and recognition[J]. Pattern recognition letters, 2003, 24(6): 833-849. DOI:10.1016/S0167-8655(02)00196-4 (0)
|
| [6] |
JENSEN R, SHEN Q. Fuzzy-rough sets for descriptive dimensionality reduction[C]//IEEE International Conference on Fuzzy Systems, 2002. Fuzz-IEEE. 2002:29-34.
(0)
|
| [7] |
BHATT R B, GOPAL M. On fuzzy-rough sets approach to feature selection[J]. Pattern recognition letters, 2005, 26(3): 965-975. DOI:10.1016/j.patrec.2004.09.044 (0)
|
| [8] |
JENSEN R, PARTHALáIN N M. Towards scalable fuzzy rough feature selection[J]. Information sciences, 2015, 323(C): 1-15. (0)
|
| [9] |
QIAN Y H, LIANG J, PEDRYCZ W, et al. Positive approximation: an accelerator for attribute reduction in rough set theory[J]. Artificial intelligence, 2010, 174(9/10): 597-618. (0)
|
| [10] |
HU Q H, YU D R, LIU J F, et al. Neighborhood rough set based heterogeneous feature subset selection[J]. Information sciences, 2008, 178(18): 3577-3594. DOI:10.1016/j.ins.2008.05.024 (0)
|
| [11] |
ALMUALLIM H, DIETTERICH T G. Learning boolean concepts in the presence of many irrelevant features[J]. Artificial intelligence, 1994, 69(1/2): 279-305. (0)
|
| [12] |
DASH M, LIU H. Consistency-based search in feature selection[J]. Artificial intelligence, 2003(151): 155-176. (0)
|
| [13] |
BATTITI R. Using mutual information for selecting features in supervised neural net learning[J]. IEEE transactions on neural networks, 1994, 5(4): 537-549. DOI:10.1109/72.298224 (0)
|
| [14] |
KWAK N, CHOI C H. Input feature selection by mutual information based on parzen window[J]. IEEE transactions on pattern analysis and machine intelligence, 2002, 24(12): 1667-1671. DOI:10.1109/TPAMI.2002.1114861 (0)
|
| [15] |
ESTEVEZ P A, TESMER M, PEREZ C A, et al. Normalized mutual information feature selection[J]. IEEE transactions on neural networks, 2009, 20(2): 189-201. DOI:10.1109/TNN.2008.2005601 (0)
|
| [16] |
SONG L, SMOLA A, GRETTON A, et al. Feature selection via dependence maximization[J]. Journal of machine learning research, 2012, 13: 1393-1434. (0)
|
| [17] |
HU Q H, ZHU Pengfei, LIU Jinfu, et al. Feature selection via maximizing fuzzy dependency[J]. Fundamenta informaticae, 2010, 98: 167-181. (0)
|
| [18] |
KOHAVI R, JOHN G. Wrappers for feature subset selection[J]. Artificial intelligence, 1997, 97(1/2): 273-324. (0)
|
| [19] |
SINDHWANI V, RAKSHIT S, DEODHARE D, et al. Feature selection in MLPs and SVMs based on maximum output information[J]. IEEE transactions on neural networks, 2004, 15(4): 937-947. DOI:10.1109/TNN.2004.828772 (0)
|
| [20] |
YANG Jianbo, SHEN Kaiquan, ONG Chongjin, et al. Feature selection for MLP neural network: the use of random permutation of probabilistic outputs[J]. IEEE transactions on neural networks, 2009, 20(12): 1911-1922. DOI:10.1109/TNN.2009.2032543 (0)
|
| [21] |
QUINLAN J R. Induction of decision trees[J]. Machine learning, 1986, 1: 81-106. (0)
|
| [22] |
BREIMAN L, FRIEDMAN J H, RICHARD A S, et al. Classification and regression trees[M]. Belmont, CA: wadsworth international group, 1984.
(0)
|
| [23] |
SETIONO R, LIU H. Neural-network feature selector[J]. IEEE transactions on neural networks, 1997, 8(3): 654-662. DOI:10.1109/72.572104 (0)
|
| [24] |
SHEN Kaiquan, ONG Chongjin, LI Xiaoping, et al. Feature selection via sensitivity analysis of SVM probabilistic outputs[J]. Machine learning, 2008, 70: 1-20. (0)
|
| [25] |
PERKINS S, LACKER K, THEILER J. Grafting: fast, incremental feature selection by gradient descent in function space[J]. Journal of machine learning research, 2003(3): 1333-1356. (0)
|
| [26] |
KENNEDY J, EBERHART R. Particle swarm optimization [C]. IEEE International Conference on Neural Networks. Perth, Australia, 1995, 4: 1942-1948.
(0)
|
| [27] |
EBERHART R C, SHI Y H, KENNEDY J. Swarm Intelligence[M]. Massachusetts: Morgan Kaufmann, 2001.
(0)
|
| [28] |
EBERHART R C, KENNEDY J. A discrete binary version of the particle swarm algorithm[J]. IEEE conference on systems, 1997, 5: 4104-4109. (0)
|
| [29] |
CHUANG L Y, CHANG H W, TU C J, et al. Improved binary PSO for feature selection using gene expression data[J]. Computational biology & chemistry, 2008, 32(1): 29-37. (0)
|
| [30] |
CHUANG L Y, TSAI S W, YANG C H. Improved binary particle swarm optimization using catfish effect for feature selection[J]. Expert systems with applications, 2011, 38(10): 12699-12707. DOI:10.1016/j.eswa.2011.04.057 (0)
|
| [31] |
WANG Xiangyang, YANG Jie, TENG Xiaolong, et al. Feature selection based on rough sets and particle swarm optimization[J]. Pattern recognition letters, 2007, 28(4): 459-471. DOI:10.1016/j.patrec.2006.09.003 (0)
|
| [32] |
CERVANTE L, XUE B, ZHANG M, et al. Binary particle swarm optimisation for feature selection: a filter based approach[J]. Evolutionary computation, 2012, 41: 1-8. (0)
|
| [33] |
LIU Quanjin, ZHAO Zhimin, LI Yingxin. Ensemble feature selection method based on neighborhood information and PSO algorithm[J]. Acta electronica sinica, 2016, 44(4): 995-1002. (0)
|
| [34] |
FONG S, WONG R, VASILAKOS A. Accelerated PSO swarm search feature selection for data stream mining big data[J]. IEEE transactions on services computing, 2016, 9(1): 33-45. (0)
|
| [35] |
翟俊海, 刘博, 张素芳. 基于相对分类信息熵的进化特征选择算法[J]. 模式识别与人工智能, 2016, 29(8): 682-690. ZHAI Junhai, LIU Bo, ZHANG Sufang. Feature selection via evolutionary computation based on relative classification information entropy[J]. Pattern recognition and artificial intelligence, 2016, 29(8): 682-690. ( 0)
|
| [36] |
SHI B Y, EBERHART R. A modified particle swarm optimizer[J]. IEEE world congress on computational intelligence, 1999, 6: 69-73. (0)
|