高效的决策表求核算法——子类比较法

Comparing Subclasses Method-an Efficient Algorithm for Computing the Core of Decision Table

目前,基于正区域的启发式决策表求核算法有较高的效率,但需要完全求出U/C。为此,证明了pos(R-{a})(D)≠posR(D)与同父两子类的等价关系,基于最高位基数排序思想,应用正整数有序分拆特性设计了一个决策表求核新算法。在算法中,只需对同父两子类元素的决策属性值进行比较就能判断一个属性是否必要,大大提高了求核效率。

At present, the heuristic algorithm for computing the core of decision table based on positive region is more efficient than others,but U/C must be calculated completely. For improving, the equivalence relation between pos（R-{a}）（D）≠ posR（D） and two subclasses subdivided by the same equivalence class is discovered.Then basing on principle of most significant ditital radix sorting ,and applying property of positive integer ordered partition,a novel algorithm for calculating the core of decision table is designed.In the algorithm,an attribute can be judged whether it is essential or not if only comparing decision attribute values of elements of two subclasses divided by the same equivalence class, and efficiency is improved obviously. The time complexity of the new algorithm is O 0CI21UI） and the important contribution it made is that the way to get the core is transformed into comparing two subclasses during the course of generating equivalence classes. Both it＇s correctness and it＇s high efficiency are verified by the example.