一种基于冲突域的不完备决策表属性约简算法

AN INCOMPLETE DECISION TABLE ATTRIBUTE REDUCTION ALGORITHM BASED ON CONFLICT REGION

以不完备决策表为研究对象,通过对冲突域的概念进行研究,给出在不完备决策表下的基于冲突域的属性约简的定义。证明该属性约简的定义与基于正区域的属性约简定义是等价的,同时设计一个在不完备决策表中的新的属性约简算法。该算法的时间复杂度为O(|K||C|2|U|),其中K=max{|TC(xi)|,xi∈U}。最后用实例说明该算法是有效的。

The incomplete decision table is regarded as an object to study. By studying the notion of conflict region, the definition of attribute reduction is provided based on conflict region within an incomplete decision table. It is also proven that the definition of the proposed attribute reduction is equivalent to that of the attribute reduction based on positive region. Meanwhile a new attribution reduction algorithm within an incomplete decision table is designed, whose time complexity is O（｜K｜｜C｜2｜U｜） （ K=max{｜Tc（xi）｜,xi∈U}）. Finally an example illustrates the efficiency of the new algorithm.