一种不完备决策表的差别矩阵求核算法

计算不完备决策表的核属性是粗糙集理论的重要内容之一。目前关于不完备决策表的求核算法的研究相对较少,而且在一般的求核算法中,其时间复杂度为[O(|C||U|2)]。为了有效地降低算法的时间复杂度,给出了一个不完备决策表的差别矩阵定义和基于差别矩阵的核定义,并证明了该定义与基于不完备决策表的核定义是等价的。在此基础上,利用差别矩阵方法来设计一种计算不完备决策表的求核算法,其时间复杂度降为[O(|C||Upos||U|)]。最后用仿真实例说明了新算法的有效性。     

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

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

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

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

一种基于决策表的核增量式高效更新算法

引入简化决策表,结合简化二进制差别矩阵设计思想,提出一种基于决策表的核增量式高效更新算法.该算法在更新简化的二进制差别矩阵时,只需在原决策表基础上对记录进行相应的更新,不需要重复计算原决策表的二进制差别矩阵.采用边更新简化二进制差别矩阵边计算核,显著地提高了算法的效率和灵活性.新算法的时间复杂度和空间复杂度分别为O(|C||U′|)和O(|C||U′pos||U′|).最后用一个实例说明了新算法的高效性.     

用序关系求信息熵核的高效算法

目前设计基于信息熵的求核算法的主要方法是差别矩阵方法.在该种方法中,是通过搜索差别矩阵的所有差别元素得到核.由于是在所有的差别元素上搜索,故该方法比较耗时.为此,在简化决策表和简化差别矩阵的基础上,得到了核的一个新性质:当把简化决策表的对象按其条件属性值看成一个数时,其对象有序.利用这个序,只需判断简化差别矩阵的少量差别元素就可以找到核属性集.在此基础上,设计了一个高效求核算法,其时间复杂度max{O(|C|2 |U/Cl),O(|C ||U|)},其空间复杂度为O(|U|).由于新算法只判断简化差别矩阵的少量差别元素就可以找到核算属性集,故新算法的效率得到了有效地改善.     

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

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

基于序关系的快速计算正区域核的算法

目前设计基于正区域的求核算法的主要方法是差别矩阵方法.该方法通过搜索差别矩阵的所有差别元素来得到核,故比较耗时.为此,在简化决策表和简化差别矩阵的基础上,若将其对象按条件属性值看成一个数,则对象是有序的.利用这个序,可将具有核属性的差别元素集映射到一个较小的搜索空间上,故只需判断简化差别矩阵的少量差别元素就可以找到核属性集.在此基础上,利用基数排序的思想,设计了一个高效求核算法,其时间复杂度为O(|C|2|U/C|)+O(|C||U|),空间复杂度为O(|U|).由于新算法只需判断简化差别矩阵的少量差别元素就可以找到核算属性集,故算法的效率得到了改善.     

利用序关系求差别矩阵的核的高效算法

目前设计基于差别矩阵的求核算法的主要方法是差别矩阵方法.在该种方法中,是通过搜索差别矩阵的所有差别元素得到核.由于是在所有的差别元素上搜索,故该方法比较耗时.本文在简化决策表和简化差别矩阵的基础上,将具有核属性的差别元素集归纳在某一相对较小的集合上,故新算法只需搜索和检查简化差别矩阵的少量差别元素就可以得到核算属性集.设计了一个高效求核算法,其时间复杂度为max{O(|C|2|U/C|),O(|C||U|)},其空间复杂度为O(|U|).由于新算法只判断简化差别矩阵的少量差别元素就可以找到核算属性集,故新算法的效率得到了有效地改善.     

改进的差别矩阵及其快速求核算法

求核是粗糙集中一个重要的研究内容之一。本文对杨明的基于差别矩阵求核方法进行研究,实例表明其方法还存在一些不完善。为了能够进一步提高求核效率,对差别矩阵进行改进,提出一种简化差别矩阵的定义,并给出求核方法,同时证明了由该方法获得的核与正区域的核是等价的,由此设计求核算法,其时间复杂度为max{O(|C||U|),O(|C||U/C||U′1|)},空间复杂度为O(|C||U/C||U′1|)。实验表明,该算法是有效的、高效的,且能适合大数据集的处理。     

一种快速计算HU差别矩阵的属性约简算法

在已有的基于HU差别矩阵的属性约简算法中,一般是以差别矩阵中的元素作为启发信息而设计的,其时间复杂度为O(|C|2|U|2).为降低该属性约简算法的时间复杂度, 首先引入简化决策表的定义,并设计了一个求简化决策表的算法,其时间复杂度为O(|C||U|).然后在简化决策表的基础上,定义了差别区域,并给出基于差别区域的属性约简定义,同时证明了基于差别区域的属性约简与基于差别矩阵的属性约简等价.在此基础上,以快速缩小简化决策表的搜索空间为目的,定义了一个新的、较为合理的、度量属性重要性的公式,并给出了它的递归计算方法,其时间复杂度为O(U/C|).最后以属性重要性为启发信息,设计了一个基于差别矩阵的快速属性约简算法,其时间复杂度降为max(O(|C||U|,O(|C|2|U/C|)),并用一个实例说明了新算法的高效性.理论分析与实验表明,新算法具有较好的扩展性.     

一种新的信息熵属性约简算法

给出一个区分对象对的属性约简定义,同时证明该属性约简的定义与基于信息熵的属性约简的定义是等价的。为求出区分对象对集,首先给出了一个快速求简化决策表的算法,其时间复杂度为O（|C||U|）。然后在简化决策表的基础上,设计了基于区分对象对集的信息熵属性约简算法,其时间复杂度和空间复杂度分别为O（|C||U|）+O（|C||U/C|²）和O（|U/C|²）+O（|U|）,最后用一个实例说明了新算法的高效性。     

一个计算Skowron差别矩阵核的新算法

为提高基于Skowron差别矩阵的求核算法的效率,引入简化决策表的定义,给出了简化Skowron差别矩阵和相应核的定义,证明了新核与基于Skowron差别矩阵的核是一致的。提出一个基于Skowron差别矩阵的快速求核新算法,其时间复杂度和空间复杂度分别降为[max{O(|C||U/C|2),O(|C||U|)}]和[max{O(|U|),O(|C|)}]。     

区分对象对集的不完备决策表属性约简

通过利用粗糙集中差别矩阵的思想,引入不完备决策表的区分对象对集的概念。并给出不完备决策表基于区分对象对集的属性约简定义。同时,也证明了利用该定义得到的不完备决策表的属性约简与基于正区域的属性约简是等价的。相比较基于正区域的不完备决策表属性约简算法,基于区分对象对集的属性约简算法时间复杂度是降低的。最后,用一个实例说明了该算法的合理性。     

一种改进的基于二进制可分辨矩阵属性约简算法

指出支天云的二进制可分辨矩阵约简算法存在的不足,给出简化的决策表定义和基于二进制可分辨矩阵的属性频率函数的定义。在此基础上,以核属性为初始约简集,以属性频率为启发式信息,提出了一种改进的基于二进制可分辨矩阵的属性约简算法,其最终可以获得一个最优约简,并且算法时间复杂度和空间复杂度分别为max{O（｜C｜ ｜U｜）,O（｜C｜^2｜ ｜U｜^2）}和0（｜C｜ ｜U｜^2）。通过实例验证,表明该算法是有效的。