Abstract: The prerequisite for reduction is to guarantee the classification capacity of the knowledge base invariant. Thus, the weak reduction is defined. Taking advantage of discernable matrixes which can calculate the weak reduction easily and genetic algorithms in global optimization, this paper regards the chromosome coverage of the discrimination function as the fitness function parameters, and an attribute reduction algorithm based on genetic algorithms and discernable matrixes is proposed. In the algorithm, rough set decision tables based on partition and covering is researched by measuring granularity again. The weak reduction effectiveness is evaluated through k-nearest neighbor accuracy. The validity of the algorithm is proved by a UCI data set. The time complexity of the algorithm is polynomial.

Key words: rough sets, genetic algorithm, discernable matrix, attribute reduction, k-nearest neighbor

摘要： 对于约简来说，其前提是保证知识库分类能力不变，由此引入弱约简的定义。利用区分矩阵能很容易计算出弱约简和遗传算法可以在全局寻优的优势，将染色体对区分函数的覆盖度作为适应度函数的参数，提出了一种基于遗传算法和区分矩阵的属性约简算法。算法中从粒计算的角度，重新度量粒度，对基于划分和覆盖的粗糙集决策表进行了研究。用k近邻算法通过准确率对弱约简效果进行评估。通过UCI数据集证明了该算法的有效性。该算法的时间复杂度是多项式的。

关键词: 粗糙集, 遗传算法, 区分矩阵, 属性约简, k近邻算法