摘要: 利用差别矩阵进行求核运算时,矩阵中大量的空元素和重复差别元素会浪费很多存储空间及计算时间。针对上述问题,结合频繁模式树,设计一种新的数据结构——压缩树(C_Tree),在此基础上提出一种快速求核算法。理论与实例分析结果证明,该算法的时空复杂度取决于求简化决策表和构造C_Tree的时空复杂度,因此求核效率得到较大的提高。
关键词:
粗糙集,
差别矩阵,
求核算法,
压缩树
Abstract: In the core computing algorithms based on the discernibility matrix idea, there are lots of empty and repeat elements in the discernibility matrix, and these elements cost a mass of memory space and waste plenty of computing time during computing core. In order to solve the problem, by considering frequent pattern tree, this paper proposes a novel data structure named C_Tree, and a quick and efficient core computing algorithm is designed based on C_tree. Theory Analysis and example results show that time complexity and space complexity of the algorithm depend on simplifying the decision table and constructing time and space complexity of the C_Tree, which improves the efficiency of computing core.
Key words:
rough set,
discernibility matrix,
core computing algorithm,
C_Tree
中图分类号:
曾德胜. 基于压缩树的快速求核算法[J]. 计算机工程, 2011, 37(10): 61-63.
CENG De-Qing. Quick Core Computing Algorithm Based on C_Tree[J]. Computer Engineering, 2011, 37(10): 61-63.