计算机工程与应用 ›› 2014, Vol. 50 ›› Issue (2): 120-123.

• 数据库、数据挖掘、机器学习 • 上一篇    下一篇

遗传算法与区分矩阵的属性约简算法

吴正江,张静敏,高  岩   

  1. 河南理工大学 计算机科学与技术学院,河南 焦作 454000
  • 出版日期:2014-01-15 发布日期:2014-01-26

Attribute reduction algorithm based on genetic algorithms and discernable matrixes

WU Zhengjiang, ZHANG Jingmin, GAO Yan   

  1. School of Computer Science and Technology, Henan Polytechnic University, Jiaozuo, Henan 454000, China
  • Online:2014-01-15 Published:2014-01-26

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

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

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