樊艳英++张自敏++陈冠萍

摘要：粗糙集理论是建立在等价类的基础上的，等价类划分算法的优劣会直接影响到属性约简和规则提取的效率.针对等价类基数排序算法中存在重复计算和空间开销较大的问题，提出了一种基于数组的等价类划分算法. 算法的时间复杂度为O（|U||C|），空间复杂度为O|U|.最后通过具体案例验证了算法的执行过程。结果表明算法高效且正确可行。

关键词：粗糙集；属性约简；等价类划分；基数排序；规则提取

中图分类号：TP18 文献标志码：A 文章编号：1009-3044（2016）01-0074-03

An Efficient Equivalence Partitioning Algorithm Based on Array

FAN Yan-ying1， ZHANG Zi-min2， CHEN Guan-ping1

（1.College of computer and Information Engineering， HeZhou University， Hezhou 542899， China； 2.Multimedia Technology Center， HeZhou University， Hezhou 542899， China）

Abstract： Rough set theory is based on Equivalence class，The good and bad of equivalence partitioning algorithm will directly affect the efficiency of the attribute reduction and rule extraction.Aiming at the problem of duplicate computing and large space overhead existed in the equivalence class of Radix Sort， propose an equivalence partitioning algorithm based on array.The time complexity of the algorithm is O （|U||C|）， The space complexity is O|U|. Finally， verify the process of algorithm by specific examples. The results show that the algorithm is correct and feasible

Key words： rough set； attribute reduction； equivalence partitioning； radix sort organization

粗糙集是在1982 年由波兰著名学者Pawlak Z提出的，该理论是一种处理不完备、不精确和不确定知识的数学工具[1]。跟其他处理不精确，不完备，不确定的理论相比，粗糙集无需其他先验知识，只需要提供其所处理的数据集，即可对这些数据进行推理，分析，和处理.正是由于粗糙集有这些方面的优势，引起了国内外科学家的关注，并致力于粗糙集的研究和应用推广.目前，粗糙集在社会很多领域的应用都取得了很好的效果.属性约简是粗糙集研究的重要内容之一[2]。属性约简就是在保持数据库分类能力不变的条件下删除其中不重要和不相关的数据[3]。

通常粗糙集进行属性约简要判断数据分类能力是否发生变化是建立在计算等价类的基础上的，因此求等价类的算法的优劣是影响后续属性约简或规则提取算法效率的重要因素之一.因此设计出低空间复杂度和时间复杂度的等价类划分算法是一件值得探索的工作.