基于遗传粒子群和粗糙集的最小属性约简算法

J4 ›› 2016, Vol. 38 ›› Issue (05): 1007-1013.

基于遗传粒子群和粗糙集的最小属性约简算法

吴尚智1，罗艺纯2，翟敬鹏1

（1.西北师范大学计算机科学与工程学院,甘肃兰州 730070；
2.中国移动通信集团甘肃有限公司,甘肃兰州 730070）

收稿日期:2015-05-29 修回日期:2015-10-25 出版日期:2016-05-25 发布日期:2016-05-25
基金资助:
甘肃省自然科学基金(1010RJZA011)；国家自然科学基金(61261015)

A minimum attribute reduction algorithm based on
genetic & particle swarm optimization and rough sets

WU Shangzhi1,LUO Yichun2,ZHAI Jingpeng1

（1.College of Computer Science and Engineering,Northwest Normal University,Lanzhou 730070;
2.Gansu Co.Ltd. of China Mobile Communications,Lanzhou 730070,China)

Received:2015-05-29 Revised:2015-10-25 Online:2016-05-25 Published:2016-05-25

摘要/Abstract

摘要：

阐述了粗糙集理论、遗传约简算法和粒子群约简算法。属性约简是知识发现的关键问题之一。传统的属性约简算法都是串行搜索的，算法效率低且收敛速度慢。将计算智能和粗糙集相结合，提出了一种基于遗传粒子群和粗糙集的最小属性约简算法。该算法利用属性依赖度计算属性核，并在种群初始化时引入属性核作为限制条件，动态调整适应度函数，以达到求得最小属性约简的目的。实验表明，对于数据量大、属性维度高的属性约简问题，该算法具有高效的处理能力。

关键词: 属性约简, 粗糙集, 遗传算法, 粒子群优化算法, 属性依赖度

Abstract:

We exploit the basic concepts of the rough sets theory, genetic algorithm and particle swarm optimization algorithm. Attributes reduction is one of the key issues in knowledge discovery. Traditional reduction algorithms feature serial search, low efficiency and slow convergence speed. By combining computational intelligence and rough sets, we propose a minimum attributes reduction algorithm which bases on the rough sets, genetic algorithm and particle swarm optimization algorithm. In order to solve the minimum attribute reduction, this algorithm regulates the function parameters dynamically and calculates attribute core using attribute dependability, thus restricting the initialized population. Experimental results prove the efficiency of the proposed algorithm in attribute reduction for high dimensionality and big data.

Key words: attribute reduction;rough sets;genetic algorithm;particle swarm optimization;dependability of attributes

吴尚智1，罗艺纯2，翟敬鹏1. 基于遗传粒子群和粗糙集的最小属性约简算法[J]. J4, 2016, 38(05): 1007-1013.

WU Shangzhi1,LUO Yichun2,ZHAI Jingpeng1. A minimum attribute reduction algorithm based on
genetic & particle swarm optimization and rough sets [J]. J4, 2016, 38(05): 1007-1013.

参考文献［14］

［1］	Pawlak Z. Rough sets［J］. International Journal of Information and Computer Sciences, 1982, 11(5):431356.
［2］	Zadeh L A. Fuzzy logic, neural networks and soft computing［M］∥Safety Evaluation Based on Identification Approaches Related to TimeVariant and Nonlinear Structures, 1993:320321.
［3］	Wu Shangzhi.An algorithm of attribute value reduction and its application based on rough sets［J］.Computer Applications and Software,2009,26(2):263265.(in Chinese)
［4］	Wu Shangzhi, Gou Pingzhang. Attribute reduction algorithm on rough set and information entropy and its application［J］.Computer Engineering,2011,37(7):5658.(in Chinese)
［5］	Wroblewski J. Finding minimal reducts using genetic algorithms［C］∥Proc of the 2nd Annual Join Conference on Information Sciences,1995:186189.
［6］	Li Weisheng, Yi Zhe. Rough set attribute reduction algorithm based on GA［J］.Microelectronics & Computer,2010,27(3):7174.(in Chinese)
［7］	Xiong Yunhui,Xiao Renyue.Finding minimal reducts using an improved genetic algorithms［J］.Computer Science,29(9):123125.(in Chinese)
［8］	Bae C,Yeh W C, Chung Y Y, et al.Feature selection with intelligent dynamic swarm and rough set ［J］.Expert Systems with Applications,2010,37 (10):70267032.
［9］	Bing Xue,Zhang Mengjie, Browne W N. Particle swarm optimisation for feature selection in classification:Novel initialisation and updating mechanisms ［J］.Applied Soft Computing,2014,18(5):261276.
［10］	Shi Feng,Wang Hui,Yu Lei,et al.MATLAB intelligent algorithm with 30 case analysis［M］.Beijing:Beihang University Press,2011.(in Chinese)
［11］	Ye Dongyi, Liao Jiankun. Minimum attribute reduction algorithm based on particle swarm optimization［C］∥Proc of the 11th Chinese Association for Artificial Intelligence,2005:728732.(in Chinese)
［12］	Qi Xiaoming, Shi Liang. Improved feature selection algorithm based on simulated annealing algorithm and artificial bee colony algorithm［J］.Computer Engineering and Design,2013,34(8):29172921.(in Chinese)
［13］	Huang Danfeng, Qi Yunsong, Xu Shanna.Gene selection method based on rough sets and ant colony algorithm［J］.Computer Technology and Development,2012,22(6):6870.(in Chinese)
［14］	Xu Gang,Yang Yuqun,Liu Binbin.Improved nonlinear adaptive particle swarm optimizer［J］.Journal of Nanchang Univercity(Natural Science),2011,35(4):323326.(in Chinese)
	附中文参考文献:
［3］	吴尚智.基于粗糙集的一种属性值约简算法及其应用［J］.计算机应用与软件,2009,26(2):263265.
［4］	吴尚智，苟平章.粗糙集和信息熵的属性约简算法及其应用［J］.计算机工程,2011,37(7):5658.
［6］	李伟生，易哲.基于遗传算法的粗糙集属性约简算法［J］.微电子学与计算机,2010,27(3):7174.
［7］	熊赟晖，肖人岳．用遗传算法求解粗糙集约简的改进方法［J］.计算机科学,2002,29(9):123125.
［10］	史峰，王辉，郁磊，等.MATLAB智能算法30个案例分析［M］.北京：北京航空航天大学出版社,2011.
［11］	叶东毅，廖建坤.基于粒子群优化的最小属性约简算法［Ｃ］∥第11届中国人工智能大会论文集,2005:728732.
［12］	戚孝铭，施亮.基于模拟退火及蜂群算法的优化特征选择算法［J］.计算机工程与设计,2013,34(8):29172921.
［13］	黄丹凤，齐云嵩，许珊娜.基于粗糙集和蚁群算法的特征基因选择方法［J］.计算机技术与发展,2012,22(6):6870.
［14］	徐刚，杨玉群，刘斌斌.一种非线性自适应粒子群优化算法［J］.南昌大学学报（自然科学版）,2011,35(4):323326.

[1]	王林, 王燕丽, 安泽远. 改进粒子群算法优化回声状态网络的电力需求预测研究[J]. 计算机工程与科学, 2022, 44(08): 1457-1466.
[2]	骆公志, 陈佳馨. 多源覆盖信息系统下的加权广义多粒度粗糙集模型及其应用[J]. 计算机工程与科学, 2021, 43(12): 2231-2237.
[3]	张晶, 魏淼, . 基于Delaunay三角划分策略的WSN区域覆盖优化研究[J]. 计算机工程与科学, 2021, 43(11): 1944-1951.
[4]	李雨晨, 魏巍, 白伟明, 王达. 基于标签共现关系的多标签特征选择[J]. 计算机工程与科学, 2021, 43(11): 2049-2055.
[5]	毛媛媛, 石恩雅, 蒋从锋, 仇烨亮, 贾刚勇, 万健, 闫龙川. 基于遗传算法的数据中心能效仿真[J]. 计算机工程与科学, 2021, 43(08): 1341-1352.
[6]	胡新荣, 刘嘉文, 刘军平, 彭涛, 何儒汉, . 基于改进GA-BP-MC神经网络的人体三维尺寸预测[J]. 计算机工程与科学, 2021, 43(08): 1443-1453.
[7]	李静, 莫思敏 . 基于改进遗传算法的深度神经网络优化研究[J]. 计算机工程与科学, 2021, 43(08): 1503-1511.
[8]	李晶晶, 许少华. 基于组合核函数的径向基过程神经网络及其在示功图诊断中的应用[J]. 计算机工程与科学, 2021, 43(04): 746-752.
[9]	季子豪, 江凌云. 一种基于遗传算法的多站点协同计算卸载算法[J]. 计算机工程与科学, 2021, 43(03): 426-434.
[10]	贾俊杰, 秦海涛. 基于遗传算法的动态轨迹匿名算法[J]. 计算机工程与科学, 2021, 43(01): 142-150.
[11]	姜春茂, 刘安鹏. 三支决策视角下的属性约简加速方法[J]. 计算机工程与科学, 2020, 42(12): 2280-2286.
[12]	李丹莲, 曹倩, 徐菲. 基于改进遗传算法的连锁便利店配送路径优化[J]. 计算机工程与科学, 2020, 42(11): 2096-2102.
[13]	王虹, 李敏赢. 局部广义多粒度粗糙集[J]. 计算机工程与科学, 2020, 42(08): 1463-1471.
[14]	陈旺虎，田真，张礼智，梁小燕，高雅琼. 基于插值的高维稀疏数据离群点检测方法[J]. 计算机工程与科学, 2020, 42(06): 966-972.
[15]	王硕禾1，刘旭1，李苏晨1，张国驹2. 基于多目标遗传算法的LoRa参数匹配优化[J]. 计算机工程与科学, 2020, 42(03): 434-440.