进化双层自适应局部特征选择

doi:10.11772/j.issn.1001-9081.2023121829

《计算机应用》唯一官方网站 ›› 2024, Vol. 44 ›› Issue (5): 1408-1414.DOI: 10.11772/j.issn.1001-9081.2023121829

所属专题：进化计算专题（2024年第5期“进化计算专题”导读，全文即将上线）

• 进化计算专题 • 上一篇

进化双层自适应局部特征选择

高麟¹, 周宇¹(), 邝得互²

^1.深圳大学计算机与软件学院，广东深圳 518060
^2.岭南大学电脑及决策科学系，香港 999077

收稿日期:2024-01-01 接受日期:2024-01-19 发布日期:2024-04-26 出版日期:2024-05-10
通讯作者: 周宇
作者简介:高麟（1995—），男，湖南常德人，硕士研究生，主要研究方向：特征选择、多目标优化
邝得互（1959—），男，中国香港人，讲席教授，博士，主要研究方向：进化计算、视频编码、机器学习。
第一联系人：周宇（1987—），男，陕西西安人，副教授，博士研究生，CCF会员，主要研究方向：计算智能、多媒体信息处理、智慧教育
基金资助:
国家自然科学基金资助项目(61702336);深圳市科创委基础研究课题(JCYJ20220810112354002)

Evolutionary bi-level adaptive local feature selection

Lin GAO¹, Yu ZHOU¹(), Tak Wu KWONG²

^1.College of Computer Science & Software Engineering，Shenzhen University，Shenzhen Guangdong 518060，China
^2.Department of Computing and Decision Sciences，Lingnan University，Hongkong 999077，China

Received:2024-01-01 Accepted:2024-01-19 Online:2024-04-26 Published:2024-05-10
Contact: Yu ZHOU
About author:GAO Lin， born in 1995， M. S. candidate. His research interests include feature selection， multi-objective optimization.
KWONG Tak Wu， born in 1959， Ph. D.， chair professor. His research interests include evolutionary computing， video coding， machine learning.
Supported by:
National Natural Science Foundation of China(61702336);Basic Research Project of Shenzhen Science and Innovation Commission(JCYJ20220810112354002)

摘要/Abstract

摘要：

局部特征选择（LFS）方法将样本空间划分为多个局部区域，并为每个区域选择最优特征子集以反映局部异质信息。然而，现有的LFS方法以每个样本为中心划分局部区域并找到最优特征子集，导致优化效率低下且适用场景受限。为了解决这个问题，提出一种进化双层自适应局部特征选择（BiLFS）算法。LFS问题被建模为双层优化问题，特征子集和待优化局部区域是该问题的两个决策变量。在问题的上层，使用非支配排序遗传算法-Ⅱ求解被选择的局部区域的最优特征子集，区域纯度和被选择特征比率是目标函数；在问题的下层，根据上层求解的最优特征子集，首先使用局部区域聚类分析得到区域内的中心样本，然后通过局部区域融合消除非必要区域并更新必要区域的种群。在11个UCI数据集上的测试结果表明，相较于基于进化算法的非自适应LFS方法，BiLFS的平均分类准确率达到前者的98.48%，而平均所需计算用时仅为前者的9.51%，运算效率得到大幅提升，且达到基于线性规划的LFS方法的水准。对迭代过程中BiLFS算法选择的用于优化的局部区域进行可视化分析，结果表明，BiLFS选择必要局部区域具有稳定性和可靠性。

关键词: 特征选择, 双层优化, 遗传算法, 多目标优化, 聚类

Abstract:

Local Feature Selection （LFS） methods partition the sample space into multiple local regions and select the optimal feature subset for each region to reflect local heterogeneous information. However， the existing LFS methods partition local regions around each sample and find the optimal feature subset， resulting in low optimization efficiency and limited applicability. To address this issue， a new evolutionary Bi-level adaptive Local Feature Selection （BiLFS） algorithm was proposed. The LFS problem was formulated as a bi-level optimization problem， with feature subsets and locally optimized regions as the decision variables. At the upper level， Non-dominated Sorting Genetic Algorithm Ⅱ was employed to find the optimal feature subsets for the selected local regions， with region purity and selected feature ratio as the objective functions. At the lower level， based on the upper-level solution， local region clustering analysis was used to obtain center samples within each region， followed by local region fusion to eliminate unnecessary regions and update the population of necessary regions. Experimental results on 11 UCI datasets demonstrate that BiLFS achieves an average classification accuracy up to 98.48%， and an average computation time down to 9.51% compare to those of non-adaptive LFS methods based on evolutionary algorithms， significantly improving computational efficiency to the level of linear programming-based LFS methods. Visual analysis of the locally optimized regions selected by the BiLFS algorithm during the iteration process indicates the stability and reliability of selecting necessary local regions.

Key words: Feature Selection (FS), bi-level optimization, Genetic Algorithm (GA), multi-objective optimization, clustering

中图分类号:

TP181

高麟, 周宇, 邝得互. 进化双层自适应局部特征选择[J]. 计算机应用, 2024, 44(5): 1408-1414.

Lin GAO, Yu ZHOU, Tak Wu KWONG. Evolutionary bi-level adaptive local feature selection[J]. Journal of Computer Applications, 2024, 44(5): 1408-1414.

图/表 7

图1 BiLFS的概览

Fig. 1 Overview of BiLFS

表1 UCI数据集的详情

Tab. 1 Details of UCI datasets

数据集	实例数	特征数	类别数
Iris	150	4	3
Wine	178	13	3
Breast Cancer	699	9	2
Diabetes	768	8	2
Heart Statlog	270	13	2
Vehicle	846	18	4
Ionosphere	351	34	2
Sonar	208	60	2
Musk1	476	166	2
Yale	165	1 024	40
ORL	400	1 024	40

表2 各LFS算法的具体参数设置

Tab. 2 Specific parameter settings of various LFS algorithms

算法

参数设置

LFSDC

α = 1 / 2 特征 数, τ = 2, γ = 0.2

LFS-MOBPSO

$γ = 0.2,$ 种群规模=20，最大迭代次数=70，

网格扩张系数=0.1，网格划分数=30

RP-NSGA，BiLFS

$γ = 0.2,$ 种群规模=20，最大迭代次数=70，

每代交叉次数=20，每代变异次数=20，

变异概率 $μ = 0.1$

表2 各LFS算法的具体参数设置

Tab. 2 Specific parameter settings of various LFS algorithms

算法

参数设置

LFSDC

α = 1 / 2 特征 数, τ = 2, γ = 0.2

LFS-MOBPSO

$γ = 0.2,$ 种群规模=20，最大迭代次数=70，

网格扩张系数=0.1，网格划分数=30

RP-NSGA，BiLFS

$γ = 0.2,$ 种群规模=20，最大迭代次数=70，

每代交叉次数=20，每代变异次数=20，

变异概率 $μ = 0.1$

表3 与基于进化算法的LFS方法的对比结果

Tab. 3 Comparison results with LFS methods based on evolutionary algorithms

数据集	算法	（ACC ± STD）/%	用时/s	数据集	算法	（ACC ± STD）/%	用时/s
Iris	BiLFS	96.67 ± 0.71	17.70	Diabetes	BiLFS	75.66 ± 0.63	2 032.53
	LFS-MOBPSO	97.13 ± 0.38	617.24		LFS-MOBPSO	76.95 ± 0.57	39 642.42
	RP-NSGA	97.27 ± 0.68	706.33		RP-NSGA	75.96 ± 0.69	42 348.12
Wine	BiLFS	97.18 ± 0.38	39.01	Heart Statlog	BiLFS	79.10 ± 0.61	66.03
	LFS-MOBPSO	97.16 ± 0.37	985.33		LFS-MOBPSO	85.19 ± 0.55	2 004.14
	RP-NSGA	97.98 ± 0.31	1 231.01		RP-NSGA	85.11 ± 0.69	2 024.32
Vehicle	BiLFS	71.16 ± 1.36	265.07	Sonar	BiLFS	89.26 ± 0.83	102.66
	LFS-MOBPSO	69.83 ± 1.81	42 081.17		LFS-MOBPSO	88.98 ± 0.65	786.05
	RP-NSGA	70.76 ± 1.67	59 446.89		RP-NSGA	89.39 ± 0.68	875.24
Breast Cancer	BiLFS	95.61 ± 0.66	1 223.01	ORL	BiLFS	97.00 ± 0.56	5 942.10
	LFS-MOBPSO	96.86 ± 0.47	52 143.74		LFS-MOBPSO	96.65 ± 0.51	30 421.14
	RP-NSGA	96.42 ± 0.58	60 845.65		RP-NSGA	96.75 ± 0.42	31 247.68
Ionosphere	BiLFS	87.43 ± 0.34	210.79	Yale	BiLFS	81.83 ± 0.33	952.79
	LFS-MOBPSO	90.84 ± 0.24	4 015.23		LFS-MOBPSO	86.07 ± 0.29	1 984.14
	RP-NSGA	93.91 ± 0.23	4 323.65		RP-NSGA	88.92 ± 0.31	2 158.30
Musk1	BiLFS	91.00 ± 0.87	1 114.36
	LFS-MOBPSO	91.06 ± 0.63	10 125.53
	RP-NSGA	91.11 ± 0.70	12 842.36

表4 与LFSDC算法的对比结果

Tab. 4 Comparison results with LFSDC algorithm

数据集	算法	（ACC ± STD）/%	用时/s	数据集	算法	（ACC ± STD）/%	用时/s
Iris	BiLFS	96.67 ± 0.71	17.70	Diabetes	BiLFS	75.66 ± 0.63	2 032.53
Iris	LFSDC	94.67 ± 0.42	35.12	Diabetes	LFSDC	75.39 ± 0.56	324.40
Wine	BiLFS	97.18 ± 0.38	39.01	Heart Statlog	BiLFS	79.10 ± 0.61	66.00
Wine	LFSDC	96.84 ± 0.39	59.52	Heart Statlog	LFSDC	83.24 ± 0.60	84.50
Vehicle	BiLFS	71.16 ± 1.36	265.07	Sonar	BiLFS	89.26 ± 0.83	102.66
Vehicle	LFSDC	69.02 ± 0.90	230.04	Sonar	LFSDC	85.30 ± 0.79	51.52
Breast Cancer	BiLFS	95.61 ± 0.66	1 223.01	ORL	BiLFS	97.00 ± 0.56	5 942.10
Breast Cancer	LFSDC	96.28 ± 0.38	980.00	ORL	LFSDC	96.65 ± 0.34	1 423.21
Ionosphere	BiLFS	87.43 ± 0.34	210.79	Yale	BiLFS	81.83 ± 0.33	952.79
Ionosphere	LFSDC	91.79 ± 0.40	170.00	Yale	LFSDC	81.73 ± 0.29	413.65
Musk1	BiLFS	91.00 ± 0.87	1 114.36
Musk1	LFSDC	87.60 ± 0.88	420.00

图2 迭代过程中BiLFS选择的需要被优化的局部区域数量的变化曲线

Fig. 2 Variation curve of number of local regions selected by BiLFS for optimization during iteration process

图3 迭代过程中BiLFS选择的需要被优化的局部区域的变化情况

Fig. 3 Variation of selected local regions for optimization by BiLFS during iteration process

参考文献 16

1	李郅琴，杜建强，聂斌，等.特征选择方法综述［J］.计算机工程与应用，2019，55（24）：10-19. 10.3778/j.issn.1002-8331.1909-0066
	LI Z Q， DU J Q， NIE B， et al. Summary of feature selection methods［J］. Computer Engineering and Applications， 2019， 55（24）： 10-19. 10.3778/j.issn.1002-8331.1909-0066
2	UYSAL A K. An improved global feature selection scheme for text classification［J］. Expert Systems with Applications， 2016， 43： 82-92. 10.1016/j.eswa.2015.08.050
3	DUDEK G. An artificial immune system for classification with local feature selection［J］. IEEE Transactions on Evolutionary Computation， 2012， 16（6）： 847-860. 10.1109/tevc.2011.2173580
4	ARMANFARD N， REILLY J P， KOMEILI M. Local feature selection for data classification［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2015， 38（6）： 1217-1227. 10.1109/tpami.2015.2478471
5	WANG Y， LI T. Local feature selection based on artificial immune system for classification［J］. Applied Soft Computing， 2020， 87： 105989. 10.1016/j.asoc.2019.105989
6	ARMANFARD N， REILLY J P， KOMEILI M. Logistic localized modeling of the sample space for feature selection and classification［J］. IEEE Transactions on Neural Networks and Learning Systems， 2017， 29（5）： 1396-1413. 10.1109/tnnls.2017.2676101
7	ZHOU Y， QIU Y， KWONG S. Region purity-based local feature selection： a multi-objective perspective［J］. IEEE Transactions on Evolutionary Computation， 2023， 27（4）： 787-801. 10.1109/tevc.2022.3222297
8	姬强，孙艳丰，胡永利，等.深度聚类算法研究综述［J］.北京工业大学学报，2021，47（8）：912-924. 10.11936/bjutxb2021010013
	JI Q， SUN Y F， HU Y L， et al. Review of clustering with deep learning［J］. Journal of Beijing University of Technology， 2021， 47（8）： 912-924. 10.11936/bjutxb2021010013
9	孙林，刘梦含，徐久成.基于优化初始聚类中心和轮廓系数的K‑means聚类算法［J］.模糊系统与数学，2022，36（1）：47-65.
	SUN L， LIU M H， XU J C. K-means clustering algorithm using optimal initial clustering center and contour coefficient［J］. Fuzzy Systems and Mathematics， 2013， 36（1）： 47-65.
10	SINHA A， MALO P， DEB K. A review on bilevel optimization： from classical to evolutionary approaches and applications［J］. IEEE Transactions on Evolutionary Computation， 2017， 22（2）： 276-295. 10.1109/tevc.2017.2712906
11	赵波，汪湘晋，张雪松，等.考虑需求侧响应及不确定性的微电网双层优化配置方法［J］.电工技术学报，2018，33（14）：3284-3295. 10.19595/j.cnki.1000-6753.tces.170388
	ZHAO B， WANG X J， ZHANG X S， et al. Two-layer method of microgrid optimal sizing considering demand-side response and uncertainties［J］. Transactions of China Electrotechnical Society， 2018， 33（14）： 3284-3295. 10.19595/j.cnki.1000-6753.tces.170388
12	米阳，李战强，吴彦伟，等.基于两级需求响应的并网微电网双层优化调度［J］.电网技术，2018，42（6）：1899-1906. 10.13335/j.1000-3673.pst.2017.2435
	MI Y， LI Z Q， WU Y W， et al. Bi-layer optimal dispatch of grid-connected microgrid based on two-stage demand response［J］. Power System Technology， 2018，42（6）：1899-1906. 10.13335/j.1000-3673.pst.2017.2435
13	林晓明，张勇军，陈伯达，等.计及多评价指标的园区能源互联网双层优化配置［J］.电力系统自动化，2019，43（20）：8-15. 10.7500/AEPS20180811006
	LIN X M， ZHANG Y J， CHEN B D， et al. Bi-level optimal configuration of park energy internet considering multiple evaluation indicators［J］. Automation of Electric Power Systems，2019，43（20）：8-15. 10.7500/AEPS20180811006
14	DEB K， PRATAP A， AGARWAL S， et al. A fast and elitist multiobjective genetic algorithm： NSGA‑Ⅱ［J］. IEEE Transactions on Evolutionary Computation， 2002， 6（2）： 182-197. 10.1109/4235.996017
15	ZHOU Y， GAO L， WANG D， et al. Imbalanced multi-fault diagnosis via improved localized feature selection［J］. IEEE Transactions on Instrumentation and Measurement， 2023， 72： 3531611. 10.1109/tim.2023.3317923
16	KOHAVI R. A study of cross-validation and bootstrap for accuracy estimation and model selection［C］// Proceedings of the 14th International Joint Conference on Artificial Intelligence： Volume 2. San Francisco， CA： Morgan Kaufmann Publishers Inc.， 1995： 1137-1145.

[1]	刘晓芳, 张军. 概率驱动的动态多目标多智能体协同调度进化优化[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1372-1377.
[2]	田野, 陈津津, 张兴义. 面向约束多目标优化的进化计算与梯度下降联合优化算法[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1386-1392.
[3]	李炫锋, 刘晟材, 唐珂. 机会约束的多选择背包问题的遗传算法求解[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1378-1385.
[4]	姜涛, 梁振宇, 程然, 金耀初. GPU加速的演化算法求解多目标流水车间调度问题[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1364-1371.
[5]	李建强, 何舟. 面向多行程取送货车辆路径问题的混合NSGA-Ⅱ[J]. 《计算机应用》唯一官方网站, 2024, 44(4): 1187-1194.
[6]	丁雨, 张瀚霖, 罗荣, 孟华. 基于信念子簇切割的模糊聚类算法[J]. 《计算机应用》唯一官方网站, 2024, 44(4): 1128-1138.
[7]	徐大鹏, 侯新民. 基于网络结构设计的图神经网络特征选择方法[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 663-670.
[8]	孟圣洁, 于万钧, 陈颖. 最大相关和最大差异的高维数据特征选择算法[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 767-771.
[9]	佘维, 李阳, 钟李红, 孔德锋, 田钊. 基于改进实数编码遗传算法的神经网络超参数优化[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 671-676.
[10]	孙林, 刘梦含. 基于自适应布谷鸟优化特征选择的K-means聚类[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 831-841.
[11]	张卓, 陈花竹. 基于一致性和多样性的多尺度自表示学习的深度子空间聚类[J]. 《计算机应用》唯一官方网站, 2024, 44(2): 353-359.
[12]	徐雪冉, 杨庚, 黄喻先. 横向联邦学习中差分隐私聚类算法[J]. 《计算机应用》唯一官方网站, 2024, 44(1): 217-222.
[13]	马勇健, 史旭华, 王佩瑶. 基于两阶段搜索与动态资源分配的约束多目标进化算法[J]. 《计算机应用》唯一官方网站, 2024, 44(1): 269-277.
[14]	何添, 沈宗鑫, 黄倩倩, 黄雁勇. 基于自适应学习的多视图无监督特征选择方法[J]. 《计算机应用》唯一官方网站, 2023, 43(9): 2657-2664.
[15]	甘舰文, 陈艳, 周芃, 杜亮. 基于高阶一致性学习的聚类集成算法[J]. 《计算机应用》唯一官方网站, 2023, 43(9): 2665-2672.

进化双层自适应局部特征选择

Evolutionary bi-level adaptive local feature selection

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 16

相关文章 15

编辑推荐

Metrics