基于区分对象对的不完备决策表求核

在差别矩阵的基础上,针对不完备决策表提出了基于差别矩阵的区分对象对集定义,并证明求不完备决策表的核可以转化到求基于差别矩阵的区分对象对集上。在此基础上,提出了一种基于区分对象对的不完备决策表求核算法,该算法的时间复杂度为：[max{O(|C||U||Upos|),O(K|C||U|)}],优于同类算法的时间复杂度;用实例说明了新算法的有效性。     

基于区分对象对集的不完备决策表求核算法

在不完备决策表中对求核算法的研究较少,且时间复杂度都相对较高.为此,根据不完备决策表中差别矩阵及其核的定义,给出条件属性的区分对象对集的定义,并得出其与决策表核属性的关系,从理论上证明求解不完备决策表的核可以转化到求条件属性的区分对象对集上.结合不完备决策表差别矩阵核的性质,提出一种基于区分对象对集的不完备决策表求核算法.实验结果表明,该算法的时间复杂度优于同类算法的时间复杂度.     

一种基于不完备决策表的求核方法

求核是粗糙集理论的重要研究内容之一,现有的求核算法大部分都是基于完备决策表的,对基于不完备决策表的求核研究很少。提出了不完备决策表二进制差别矩阵的构造方法,在此基础上,利用二进制差别矩阵设计了一种不完备决策表的求核算法。从理论上证明了基于二进制差别矩阵的求核与基于正区域的求核是相等的。新算法的时间复杂度是[O(|C||U|2)],用实例分析说明了新算法的正确性。     

一种不完备决策表的属性约简算法

对于不完备决策表,给出了区分对象对集和基于区分对象对集约简的定义,并证明出基于区分对象对集的属性约简定义等价于基于广义决策的属性约简定义。在此基础上,提出一种基于区分对象对集的新算法。新算法以区分度[K(ci)]和完备度[P(ci)]为启发信息,结合基数排序,使得算法最终时间复杂度为[O(|C||U|2)],相比传统的算法时间复杂度[O(|C|3|U|2)]和[O(|C|2|U|2)],时间复杂度有效降低。通过实例说明了新算法的正确性和有效性。