一种关系积和遗传算法相结合的属性约简算法

A hybrid reduct algorithm based on attribute union and GA

属性约简是粗糙集(rough set,RS)理论进行规则提取中的重要步骤之一。决策表的最小属性约简是NP-hard问题,遗传算法(genetic algorithm,GA)是求解此类问题的有效方法之一,但在利用遗传算法求解属性约简过程中,需要计算各个个体的适应度,每计算一个个体的适应度,需要根据该个体代表的属性组,组织决策表,对组织后的决策表进行扫描,这样,算法就需要多次对决策表进行操作,影响到算法的执行效率。我们基于集合理论,提出了关系积概念,把决策表的属性约简过程转化为关系积的运算,利用关系积计算遗传算法各个体的适应度,不需要扫描决策表,避免了对决策表的操作,提高了遗传算法求解属性约简的效率,通过实例对这一算法进行了详细的描述。

Attribute Reduction in Rough Set is the key procedures to extract rules from decision table.It is a NP-hard problem to get the minimal Attribute Sets.Genetic algorithm(GA) is a effective methods to solve such problem.But it was necessary to calculate every individual s fitness in the GA.The decision table must be reorganized according the attribute sets of the individual.The GA scanned that reorganized decision table to calculate the individual s fitness and chose the best individual.Thus the GA needed to o...