一种基于重构相容决策表的属性约简算法

基于正区域的属性约简是目前最常用的一类约简算法。现实中的决策表有可能存在不一致的对象。另外,在约简过程中随着属性个数的减少,也有可能产生新的不一致对象。对于基于正区域的约简算法来说,不一致的对象并没有提供任何有用的信息,删除不一致的对象不会改变正区域的计算结果以及最终的约简结果,而且可以显著提高算法的效率。然而现有的基于正区域的约简算法并没有考虑到这个问题,它们采用论域中的所有对象来计算正区域并得出约简结果。针对这一问题,定义了重构相容决策表和重构相容决策子表的概念。引入这两个概念的目的是在约简过程中删除初始决策表中的不一致对象,从而获得一个相容决策表。借助于这两个概念,提出了一种新的基于正区域的属性约简算法。在真实数据集上的实验表明,与传统的算法相比,该算法能够获得较小的约简结果和较高的分类精度,并且具有相对较低的时间复杂度。

New Attribute Reduction Algorithm Based on Reconstructed Consistent Decision Table

By now, the positivcbased attribute reduction is one of the most popular algorithms for attribute reduction.Some inconsistent objects may be present in the real world decision tables. And with the decrease of the number of attributes during the process of reduction, some new inconsistent objects may also occur in the decision tables. For a positivcbased attribute reduction algorithm, the inconsistent objects can not provide any useful information. I}herefore, dcleting those objects from the decision table will not change the results of positive regions, and the final result of reduction. Moreover, this operation may improve the efficiency of the algorithm obviously. However, most of the current positivcbased attribute reduction algorithms have not concerned this problem. I}hcy use all objects in the domain to calculate the positive regions and obtain the results of reduction. To solve this problem, we defined the notions of reconstructing consistent decision table and reconstructing consistent decision sulrtable. The aim for introducing the two notions is to delete the inconsistent objects in the original decision table and obtain a consistent decision table during the process of reduction. By virtue of the two notions, we proposed a novel positivcbased attribute reduction algorithm. I}he experimental results on real datasets demonstrate that our algorithm can obtain smaller reducts and higher classification accuracks than the traditional algorithms. And the time complexity of our algorithm is relatively low.