基于属性核的遗传约简算法

An Genetic_Enhanced Core Attributes Based Reduct Method

属性最小约简是NP完全问题,该问题的研究一直被关注。如,以不可分辨矩阵为基础的传统约简方法,基于属性重要性的约简方法等等,这些方法对于大数据集都是不实用的。文[8]提出了以遗传算法全局搜寻能力为基础的属性约简方法,文[3]通过引进属性依赖启发信息改进了文[8]中的方法。本文中,先给出了一个时间复杂度为O(k×n×log n),空间复杂度为O(n)的核属性判别方法。然后,以此为基础给出了较文[3]和文[8]中更有效的遗传粗糙约简算法。

The problem of finding minimal reduct belongs to the class of NP-complete Problems. Some articles solved the problem in different ways. The traditional reduct methods such as the method based on discernability matrix, the induction method based on the importance of the attributes and so on, are all impractical for large database. Paper [8] brings out a minimal reduct methods which take advantage of the global search ability of Genetic Algorithm. Paper [3] improves the methos in Paper [8] mentioned by inducing the heuristic information: the dependency of Attributes. In this paper, firstly we improve the method of finding core attributes, and only O(k×X×n×log n) time complexity and O(n) memory space required in our method. Then we combine the method with methods advised in [3,8], and bring out a genetic-enhanced Attribute reduct Method which shows good qualities in some aspects.