WKNN Feature Selection Method Based on Self-Tuning Adaptive Genetic Algorithm

doi:10.3778/j.issn.1002-8331.2012-0021

Abstract

Abstract:

In view of the fact that most of the existing feature selection methods based on [K]-nearest neighbor and genetic algorithm do not take into account the different importance of each feature and are prone to premature convergence, especially the local optimal solution problem, a weighted [K]-nearest neighbor feature selection method based on self-tuning adaptive genetic algorithm is proposed in this paper. The method uses the weighted [K]-nearest neighbor algorithm to predict the category of samples and assigns a weight for each feature to measure the feature’s classification ability, then it uses self-tuning adaptive genetic algorithm to adjust the mutation rate, population size and convergence threshold, and searches for the optimal feature weight vector in the process of iterative evolution. In order to evaluate the effectiveness of this method, it is compared with the existing seven feature selection methods on five standard data sets. Experimental results show that this method is effective and has high classification performances.

Key words: feature selection, weighted [K]-nearest neighbor, self-tuning adaptive genetic algorithm, parameter tuning, real coding

摘要：

针对大多已有基于[K]近邻和遗传算法的特征选择方法中没有考虑各个特征的重要度不同，并且容易出现过早收敛，特别是局部最优解问题，提出了一种基于自调优自适应遗传算法的WKNN特征选择方法。该方法使用WKNN算法预测样本的类别，为每个特征分配一个权重来衡量特征的分类能力，然后采用自调优自适应遗传算法，对变异率、种群规模和收敛阈值进行参数调整，在迭代进化过程中搜索最优特征权重向量。为了评价该方法的有效性，与已有7种特征选择方法在5个标准数据集上进行了比较。实验结果表明，该方法是有效的，且具有较高的分类性能。

关键词: 特征选择, 加权[K]近邻, 自调优自适应遗传算法, 参数调优, 实数编码

CHEN Qianru, LI Yali, XU Kequan, LIU Yilong, WANG Shuqin. WKNN Feature Selection Method Based on Self-Tuning Adaptive Genetic Algorithm[J]. Computer Engineering and Applications, 2021, 57(20): 164-171.

陈倩茹，李雅丽，许科全，刘铱龙，王淑琴. 自调优自适应遗传算法的WKNN特征选择方法[J]. 计算机工程与应用, 2021, 57(20): 164-171.

References

[1] GHEYAS I A，SMITH L S.Feature subset selection in large dimensionality domains[J].Pattern Recognition，2009，43（1）：5-13.
[2] XUE B，ZHANG M J，BROWNE W N，et al.A survey on evolutionary computation approaches to feature selection[J].IEEE Transactions on Evolutionary Computation，2016，20（4）：606-626.
[3] YANG H Q，LYU M R，KING I.Efficient online learning for multitask feature selection[J].ACM Transactions on Knowledge Discovery from Data，2013，7（2）：1-27.
[4] SAEYS Y，INZA I，LARRANAGA P.A review of feature selection techniques in bioinformatics[J].Bioinformatics，2007，23（19）：2507-2517.
[5] JAIN A K，DUIN R P W，MAO J C.Statistical pattern recognition：a review[J].IEEE Transaction on Pattern Analysis and Machine Intelligence，2000，22（1）：4-37.
[6] PARK C H，KIM S B.Sequential random k-nearest neighbor feature selection for high-dimensional data[J].Expert Systems with Applications，2015，42（5）：2336-2342.
[7] WANG A G，AN N，CHEN G L，et al.Accelerating wrapper-based feature selection with K-nearrest-neighbor[J].Knowledge-Based Systems，2015：81-91.
[8] 宋宝燕，孟彦伟，丁琳琳.基于Voronoi划分的位置数据KNN查询处理方法[J].计算机科学与探索，2019，13（12）：2015-2028.
SONG B Y，MENG Y W，DING L L.KNN query method for location data based on Voronoi partition[J].Journal of Frontiers Computer Science and Technology，2019，13（12）：2015-2028.
[9] FU G F，WANG G，DAI X T.An adaptive threshold determination method of feature screening for genomic selection[J].BMC Bioinformatics，2017，18（1）：212.
[10] KOROMYSLOVA A，SEMENKINA M，SERGIENKO R.Feature selection for natural language call routing based on self-adaptive genetic algorithm[J].IOP Conference Series：Materials Science and Engineering，2017，173：012008.
[11] WULANDHARI L A，WIBOWO A，DESA M.Improvement of adaptive GAs and back propagation ANNs performance in condition diagnosis of multiple bearing system using grey relational analysis[J].Computational Intelligence and Neuroscience，2014，2014：419743.
[12] 马永杰，云文霞.遗传算法研究进展[J].计算机应用研究，2012，29（4）：1201-1206.
MA Y J，YUN W X.Research progress of genetic algorithm[J].Application Research of Computers，2012，29（4）：201-1206.
[13] 郭银景，孟庆良，孔芳，等.AUV路径规划算法研究现状与展望[J].计算机科学与探索，2020，14（12）：1981-1994.
GUO Y J，MENG Q L，KONG F，et al.Research status and prospect of AUV path planning algorithms[J].Journal of Frontiers Computer Science and Technology，2020，14（12）：1981-1994.
[14] 张晓缋，戴冠中，徐乃平.遗传算法种群多样性的分析研究[J].控制理论与应用，1998（1）：17-23.
ZHANG X H，DAI G Z，XU N P.Analysis and research on population diversity of genetic algorithm[J].Control Theory & Applications，1998（1）：17-23.
[15] 李欣.自适应遗传算法的改进与研究[D].南京：南京信息工程大学，2008.
LI X.The improvement of the adaptive genetic algorithm and its application[D].Nanjing：Nanjing University of Information Science & Technology，2008.
[16] GOLDBERG D E.Genetic algorithm in search optimization and machine learning[M].[S.l.]：Addison-Wesley，1989.
[17] BACHE K，LICHMAN M.UCI Machine learning repository[EB/OL].[2020-10-11].http：//archive.ics.uci.edu/ml.
[18] LEI Y，HUAN L.Efficient feature selection via analysis of relevance and redundancy[J].Journal of Machine Learning Research，2004，5（1）：1205-1224.
[19] 李安，江加和.基于自适应遗传算法的入侵检测特征选择方法[J].应用科技，2016，43（3）：49-53.
LI A，JIANG J H.A feature selection method for intrusion detection using the adaptive genetic algorithm[J].Applied Science and Technology，2016，43（3）：49-53.
[20] BATTITI R.Using mutual information for selecting features in supervised neural net learning[J].IEEE Trans on Neural Networks，1994，5（4）：537-550.
[21] PENG H C，LONG F L，DING C H Q.Feature selection based on mutual information：criteria of max-dependency，max-relevance，and min-redundancy[J].IEEE Trans on Pattern Analysis and Machine Intelligence，2005，27（8）：1226-1238.
[22] 李双杰，张开翔，王士栋，等.基于加权K近邻的特征选择方法[J].天津师范大学学报（自然科学版），2020，40（2）：63-67.
LI S J，ZHANG K X，WANG S D，et al.Feature selection based on weighted k-nearest neighbors[J].Journal of Tianjin Normal University（Natural Science Edition），2020，40（2）：63-67.
[23] 计智伟，吴耿锋，胡珉.基于自适应遗传算法和SVM的特征选择[J].计算机工程，2009，35（14）：200-202.
JI Z W，WU G F，HU M.Feature selection based on adaptive genetic algorithm and SVM[J].Computer Engineering，2009，35（14）：200-202.