信息熵最小约简问题的若干随机优化算法

现有的启发式属性约简算法一般无法得到信息熵意义下的最小属性约简.为此,文中探讨应用随机优化算法计算信息熵意义下最小属性约简的问题.首先通过定义适当的适应值函数,将信息熵意义下的最小属性约简问题转化为不含约束的适应值优化问题,证明问题转化的等价性.研究基于遗传算法、粒子群优化算法、禁忌搜索以及蚁群算法等若干随机优化算法的求解效率和求解质量,并用一批UCI数据集来加以测试.实验结果表明,文中设计的带增强策略的基于全息粒子群的属性约简算法,具有较高的获得信息熵意义下最小属性约简的概率和较优的算法性能.

Research on Computing Minimum Entropy Based Attribute Reduction via Stochastic Optimization Algorithms

Existing heuristic attribute reduction algorithms generally fail to get a minimum entropy-based attribute reduction of a decision table.Some stochastic optimization algorithms are discussed to solve the problem of entropy-based attribute reduction.Firstly,a proper fitness function is defined to transform the minimum attribute reduction problem into a fitness optimization problem without additional constraints and the equivalence of transformation is proved.Then,the solving efficiency and the solution quality of some stochastic optimization algorithms are studied such as Genetic Algorithm,Particle Swarm Optimization,Tabu search and Ant Colony Optimization.Some UCI datasets are applied to test those performances.The experimental results show that the fully informed PSO based attribute reduction algorithm with refine scheme has a higher probability to find a minimum entropy-based attribute reduction and good performance.