基于不完备决策表的容差类高效求解算法

Efficient Algorithm for Computing Tolerance Classes of Incomplete Decision Table

容差关系作为粗糙集扩展模型中常用的二元关系之一.许多其他扩展模型都是在容差关系基础上构建的,它使得不完备决策表中对象的划分更具有一般性,如何有效降低求解容差类的计算复杂性具有重要的意义.针对目前以容差关系为基础的不完备决策表的属性约简和知识获取算法时间复杂度不理想的问题,其主要原因是由于在求解不完备决策表的容差类时需消耗大量的计算时间,为了有效提高求解容差类的计算效率,引入基数排序和标记技术的设计思想,在此基础上提出一种高效的求解容差类算法,从而有效地降低了算法的时空复杂度,最后,通过实例分析和实验结果验证了新算法的有效性和可行性.

Tolerance relation is one of the most common binary relations in extended rough set models, many other extensions are built on the basis of tolerance relation. It makes the objects into more general in incomplete decision table, how to effectively reduce the computational complexity of tolerance class is of great significance. At present, the algorithms of attribute reduction and rule extrac- tion based on tolerance relations for incomplete decision table are designed, whose time and space complexity are not good. Aiming at the problem, the main reason is that computing the tolerance classes of incomplete decision table consumes a large amount of time. In order to improve the efficiency of computing tolerance classes, radix sorting and label technology are introduced in this paper, on this foundation, the quick algorithm for computing the tolerance classes is presented, which remarkably reduces the time and space com- plexity of the algorithm. At last, an example and experimental results illustrate the efficiency and feasibility of the algorithm.