区间值决策系统下的最小属性约简

Minimum Attribute Reduction under Interval-Valued Decision System

摘要: 在给定的属性约简目标函数下，决策表中往往存在多个约简。最后的决策规则集直接依赖于所获得的约简。决策规则集的简洁性、可理解性、通用性和精确性因约简的不同而不同，因此期望得到一些最优结果，即长度最短的最小约简。这样可以尽可能多地去除冗余属性，有效地管理决策表的存储空间，并且决策规则集的性能将变得优异。不幸的是，寻找最小约简已被证明是一个NP-难问题(Wong和Ziarko 1985)。当给定决策表时，启发式算法并不总是能得到最小约简。因此本文在区间值决策系统下提出了基于差别矩阵的0-1规划最短约简算法。

Abstract: With a given attribute reduction objective function, there are often multiple reductions in the deci-sion table. The final decision rule set is directly dependent on the obtained reductions. The con-ciseness, comprehensibility, generality and accuracy of the decision rule set vary from one reduc-tion to another, so it is expected to obtain some optimal result, i.e., the smallest reduction with the shortest length. This will remove as many redundant attributes as possible, manage the storage space of the decision table efficiently, and the performance of the decision rule set will become superior. Unfortunately, finding the minimum reduction has been shown to be an NP-hard problem (Wong and Ziarko, 1985). Heuristic algorithms do not always yield the minimum reduction when given a decision table. Therefore, in this paper, we propose a difference matrix-based shortest reduction algorithm for 0-1 programming under interval-valued decision system.