论文部分内容阅读
目前,关于不完备决策表的属性约简算法已有不少,其中在很多算法中,其时间复杂度为O(|C|3|U|2).为有效地降低算法的时间复杂度,给出一个差别矩阵的定义和基于差别矩阵属性约简的定义,并证明了该属性约简与基于正区域的属性约简是等价的.生成的差别矩阵无需比较Uneg之间的对象,使差别矩阵得到有效地简化,进一步降低算法的存储空间.在此基础上,利用简化的差别矩阵设计一个快速计算不完备决策表的属性约简的算法,其时间复杂度降为max{O(|C|2|Upos||U|),O(K|C||U|)}.(其中K=max{|TC(xi)|,xi∈U}).最后用实例仿真说明了新算法的有效性.
At present, there are many attribute reduction algorithms for incomplete decision tables, among which the time complexity is O (| C | 3 | U | 2) in many algorithms. To effectively reduce the time complexity of the algorithm, A definition of differential matrix and a definition based on attribute reduction of differential matrix are given and it is proved that this attribute reduction is equivalent to attribute reduction based on positive region.The generated differential matrix does not need to compare Uneg objects, The discernibility matrix can be effectively simplified to further reduce the storage space of the algorithm.On the basis of this, a simplified algorithm for the attribute reduction of an incompletely defined decision table is designed using a simplified discernibility matrix, whose time complexity decreases to max {O (| (K | C || U |)} (where K = max {| TC (xi) |, xi∈U}). Finally, an example is given to illustrate the new algorithm Effectiveness.