非完备信息系统的启发式特征选择遗传算法
|
摘要
为了获取非完备信息系统的相对最小特征子集,提出一种基于非完备信息系统的启发式特征选择遗传算法.本文首先构造了适应度函数,并以特征重要度为启发式信息融入特征选择;同时利用特征的相对核对种群初始化,引导染色体的进化,缩小了算法的搜索空间;且在染色体的交叉和变异过程中,对满足条件的染色体及时删除,加快算法的收敛性;实验结果验证了算法的有效性.
In this paper,in order to get the minimal relative reduction of features set,heuristic genetic algorithm for feature selection in incomplete decision table is proposed.At first,the fitness function of genetic algorithm is presented.Meanwhile,regarding feature significance as heuristic information in feature selection,and relative core feature serves as initial population to optimize chromosome,which can reduce the exploration space,what's more,the corresponding condition chromosomes are deleted in the crossover and mutation processes,this method can accelerate the convergence.At last,the better effect of the proposed algorithm can be tested by the experiment.
In this paper,in order to get the minimal relative reduction of features set,heuristic genetic algorithm for feature selection in incomplete decision table is proposed.At first,the fitness function of genetic algorithm is presented.Meanwhile,regarding feature significance as heuristic information in feature selection,and relative core feature serves as initial population to optimize chromosome,which can reduce the exploration space,what's more,the corresponding condition chromosomes are deleted in the crossover and mutation processes,this method can accelerate the convergence.At last,the better effect of the proposed algorithm can be tested by the experiment.
引文
[1]Pawlak Z.Rough set theory and its application to data analysis[J].Cybernetics and System,1998,29(27):661-688.
[2]PawlakZ,Skowron A.Rudiments ofrough sets[J].InformationSciences,2007,117(1):3-37.
[3]刘少辉,盛秋戬,吴斌,等.Rough集高效算法的研究[J].计算机学报,2003,26(5):524-529.Liu Shao－hui,Sheng Qiu－jian,Wu Bin,et al.Research on eff－icient algorithms for rough set methods[J].Chinese Journal ofComputers,2003,26(5):524-529.(in Chinese)
[4]徐章艳,刘作鹏,杨炳儒,等.一个复杂度为max(O(|C||U|,O|C|2|U/C|))的快速属性约简算法[J].计算机学报,2006,29(3):391-399.Xu Zhang－Yan,Liu Zuo－peng,Yang Bing－ru,et al.A quick at－tribution reduction algorithm with complexity ofmax{O(|U||C|),O(|C|2|U/C|)}[J].Chinese Journal of Computer,2006,29(3):391-399.(in Chinese)
[5]刘勇,熊蓉,褚健.Hash快速属性约简算法[J].计算机学报,2009,32(8):1493-1499.Liu Yong,Xiong Rong,Chu Jian.Quick attribute reduction a－lgorithmwith hash[J].Chinese Journal of Computer,2009,32(8):1493-1499.(in Chinese)
[6]钱进,苗夺谦,张泽华.云计算环境下知识约简算法[J].计算机学报,2011,34(12):2332-2343.Qian Jin,Miao Duo－qian,Zhang Ze－hua.Knowledge reductionalgorithms in cloud computing[J].Chinese Journal of Comput－er,2011,34(12):2332-2343.(in Chinese)
[7]苗夺谦,陈玉明,王睿智,等.图表示下的知识约简[J].电子学报,2010,38(8):1952-1957.Miao Duo－qian,Chen Yu－ming,Wangru－i zhi,et al.Knowledgereduction algorithm under graph view[J].Acta ElectronicaSinica,2010,38(8):1952-1957.(in Chinese)
[8]杜卫锋,秦克云.不协调决策表几种约简标准及其关系分析[J].电子学报,2011,39(6):1336-1340.Du We－i feng,Qin Ke－yun.Analysis of several reduction stan－dards and their relationship for inconsistent decision table[J].Acta Electronica Sinica,2011,39(6):1336-1340.(in Ch－inese)
[9]Kryszkiewicz M.Rough set approach to incomplete informationsystems[J].Information Sciences,1998,112(1):39-49.
[10]Kryszkiewicz M.Rules in incomplete information systems[J].Information Sciences,1999,113(2):271-292.
[11]Wroblewski J.Finding minimal reduces using genetic algo－rithms[A].Proc of 2nd Annual Joint Conf on InformationSciences[C].Wrightsville Beach:JC1S,1995.186-189.
[12]Ke Liangjun,Feng Zuren,Ren Zhigang.An efficient antcolony optimization approach to attribute reduction in roughset[J].Pattern Recognition Letters,2008,29(9):1351-1357.
[13]Wang Xiangyang,Yang Jie,Teng Xiaolong.Feature selectionbased on rough sets and particle swarm optimization[J].Pat－tern Recognition Letters,2007,28(4):459-471.
[14]Riyaz Sikora,Selwyn Piramuthu.Framework for efficient fea－ture selection in genetic algorithm based data mining[J].Eu－ropean Journal of Operational Research,2007,180(2):723-737.
[15]李订芳,章文,李贵斌,等.基于可行域的遗传约简算法[J].小型微型计算机系统,2006,27(2):312-315.Li Ding－fang,Zhang Wen,Li Gu－i bin,et al.Genetic reductionalgorithm based on feasible region[J].Journal of ChineseComputer Systems,2006,27(2):312-315.(in Chinese)
[16]Mingyuan Zhao,ChongFu,et al.Feature selection and param－eter optimization for support vector machines:A new approachbased on genetic algorithm with feature chromosomes[J].Ex－pert Systems with Applications,2011,38:5197-5204.
[17]M E EIAImi.A filter model for feature subset selection basedon genetic algorithm[J].Knowledge－Based Systems,2009,22:356-362.
[2]PawlakZ,Skowron A.Rudiments ofrough sets[J].InformationSciences,2007,117(1):3-37.
[3]刘少辉,盛秋戬,吴斌,等.Rough集高效算法的研究[J].计算机学报,2003,26(5):524-529.Liu Shao－hui,Sheng Qiu－jian,Wu Bin,et al.Research on eff－icient algorithms for rough set methods[J].Chinese Journal ofComputers,2003,26(5):524-529.(in Chinese)
[4]徐章艳,刘作鹏,杨炳儒,等.一个复杂度为max(O(|C||U|,O|C|2|U/C|))的快速属性约简算法[J].计算机学报,2006,29(3):391-399.Xu Zhang－Yan,Liu Zuo－peng,Yang Bing－ru,et al.A quick at－tribution reduction algorithm with complexity ofmax{O(|U||C|),O(|C|2|U/C|)}[J].Chinese Journal of Computer,2006,29(3):391-399.(in Chinese)
[5]刘勇,熊蓉,褚健.Hash快速属性约简算法[J].计算机学报,2009,32(8):1493-1499.Liu Yong,Xiong Rong,Chu Jian.Quick attribute reduction a－lgorithmwith hash[J].Chinese Journal of Computer,2009,32(8):1493-1499.(in Chinese)
[6]钱进,苗夺谦,张泽华.云计算环境下知识约简算法[J].计算机学报,2011,34(12):2332-2343.Qian Jin,Miao Duo－qian,Zhang Ze－hua.Knowledge reductionalgorithms in cloud computing[J].Chinese Journal of Comput－er,2011,34(12):2332-2343.(in Chinese)
[7]苗夺谦,陈玉明,王睿智,等.图表示下的知识约简[J].电子学报,2010,38(8):1952-1957.Miao Duo－qian,Chen Yu－ming,Wangru－i zhi,et al.Knowledgereduction algorithm under graph view[J].Acta ElectronicaSinica,2010,38(8):1952-1957.(in Chinese)
[8]杜卫锋,秦克云.不协调决策表几种约简标准及其关系分析[J].电子学报,2011,39(6):1336-1340.Du We－i feng,Qin Ke－yun.Analysis of several reduction stan－dards and their relationship for inconsistent decision table[J].Acta Electronica Sinica,2011,39(6):1336-1340.(in Ch－inese)
[9]Kryszkiewicz M.Rough set approach to incomplete informationsystems[J].Information Sciences,1998,112(1):39-49.
[10]Kryszkiewicz M.Rules in incomplete information systems[J].Information Sciences,1999,113(2):271-292.
[11]Wroblewski J.Finding minimal reduces using genetic algo－rithms[A].Proc of 2nd Annual Joint Conf on InformationSciences[C].Wrightsville Beach:JC1S,1995.186-189.
[12]Ke Liangjun,Feng Zuren,Ren Zhigang.An efficient antcolony optimization approach to attribute reduction in roughset[J].Pattern Recognition Letters,2008,29(9):1351-1357.
[13]Wang Xiangyang,Yang Jie,Teng Xiaolong.Feature selectionbased on rough sets and particle swarm optimization[J].Pat－tern Recognition Letters,2007,28(4):459-471.
[14]Riyaz Sikora,Selwyn Piramuthu.Framework for efficient fea－ture selection in genetic algorithm based data mining[J].Eu－ropean Journal of Operational Research,2007,180(2):723-737.
[15]李订芳,章文,李贵斌,等.基于可行域的遗传约简算法[J].小型微型计算机系统,2006,27(2):312-315.Li Ding－fang,Zhang Wen,Li Gu－i bin,et al.Genetic reductionalgorithm based on feasible region[J].Journal of ChineseComputer Systems,2006,27(2):312-315.(in Chinese)
[16]Mingyuan Zhao,ChongFu,et al.Feature selection and param－eter optimization for support vector machines:A new approachbased on genetic algorithm with feature chromosomes[J].Ex－pert Systems with Applications,2011,38:5197-5204.
[17]M E EIAImi.A filter model for feature subset selection basedon genetic algorithm[J].Knowledge－Based Systems,2009,22:356-362.