计算机工程 ›› 2013, Vol. 39 ›› Issue (4): 39-43.doi: 10.3969/j.issn.1000-3428.2013.04.010

• 先进计算与数据处理 • 上一篇    下一篇

基于区分矩阵与区分函数的同元转换约简算法

徐 宁1,章 云2,周如旗3   

  1. (1. 上海应用技术学院计算机科学与信息工程学院,上海 201418; 2. 广东工业大学自动化学院,广州 510006;3. 广东第二师范学院计算机科学系,广州 510800)
  • 收稿日期:2012-04-09 出版日期:2013-04-15 发布日期:2013-04-12
  • 作者简介:徐 宁(1966-),女,副教授、博士,主研方向:智能信息处理;章 云,教授、博士;周如旗,副教授、硕士
  • 基金项目:
    国家自然科学基金资助项目(U0735003);上海市教育委员会科研创新基金资助项目(060Z021);上海应用技术学院科研计划基金资助项目(YJ2008-07)

Same Element Conversion Reduction Algorithm Based on Discernibility Matrix and Discernibility Function

XU Ning   1, ZHANG Yun   2, ZHOU Ru-qi   3   

  1. (1. School of Computer Science & Information Engineering, Shanghai Institute of Technology, Shanghai 201418, China; 2. School of Automation, Guangdong University of Technology, Guangzhou 510006, China; 3. Department of Computer Science, Guangdong University of Education, Guangzhou 510800, China)
  • Received:2012-04-09 Online:2013-04-15 Published:2013-04-12

摘要: 针对较大数据集在区分函数范式转换获得约简解集时的困难性,提出一种基于区分矩阵与区分函数的同元转换约简算法。利用区分矩阵保留数据集的全部分类信息,使用区分函数建立分类信息的数学逻辑范式,从低元的合取范式分步转换为析取范式,根据同元转换算法和高元吸收算法,若能够吸收完全则回退,否则再次调用算法进入转换运算。实例演算结果表明,该算法能缩小一次转换规模,灵活地运用递归算法,使得运算简洁有效。

关键词: 约简算法, 广度搜索, 区分矩阵, 区分函数, 范式转换, 粗糙集

Abstract: Aiming at the difficulties of the form transferring on large datasets to get reducts, a same element conversion reduction algorithm based on discernibility matrix and discernibility function is put forward. It uses discernibility matrix to keep all classification information of data set, and discernibility function constructs the mathematical logic form from the classical information. The algorithm begins from lower rank of Conjunctive Normal Form(CNF) into Disjunctive Normal Form(DNF). According to the same element conversion algorithm and high element absorption algorithm, if higher ranks are absorbed, the algorithm can return; else the algorithm can enter itself to next circle. Calculation results show that this algorithm greatly reduces the once scale of transform, neatly uses the mature recursive algorithm and works compactly and effectively.

Key words: reduction algorithm, breadth search, discernibility matrix, discernibility function, normal form conversion, rough set

中图分类号: