基于简化的二进制差别矩阵的快速属性约简算法

目前，基于二进制差别矩阵的属性约简算法有如下不足：算法的时间和空间复杂度不理想；所得到的属性约简与由基于正区域的属性约简的定义得到的属性约简不一致。本文给出一个简化的二进制差别矩阵和相应的属性约简的定义，证明了该定义与基于正区域的属性约简的定义是一致的。由于在简化的二进制的差别矩阵中，要先求出IND（C），故设计了一个较好的求IND（C）的算法，其复杂度被降低为O（｜U‖U｜）。在此基础上设计了一个快速属性约简算法，其时间复杂度和空间复杂度分别被降为max{O（｜C｜^2（｜U＇pos‖U/C｜））,O（｜C‖U｜）}和max{O｜U｜},O（｜C｜（｜U＇pos‖U/C｜））}。

基于简化的二进制差别矩阵的快速求核算法

目前,基于二进制差别矩阵的求核算法有如下不足:算法的时间和空间复杂度不理想;所得到的核与基于正区域的核不一致.叶东毅教授提出了一个新的二进制差别矩阵并证明了在新的二进制差别矩阵中定义的核与基于正区域的核是一致的,但计算新的二进制差别矩阵除了具有和原方法相同的存储空间外,还增加了额外的计算.本文给出一个简化的二进制差别矩阵和相应的求核算法,并证明了所求的核是基于正区域的核.新算法的时间复杂度和空间复杂度分别被降为m ax{O(C(U’p os‖U/C)),O(C‖U)}和m ax{O(U),O(C(U’p os‖U/C))}.

基于信息熵的二进制差别矩阵属性约简算法

给出一个简化的二进制差别矩阵的属性约简定义,并证明该属性约简的定义与基于信息熵的属性约简的定义是等价的。为求出简化的二进制差别矩阵,设计了一个快速求简化决策表的算法,其时间复杂度为O(|C||U)|。在此基础上,设计了基于信息熵的简化二进制差别矩阵的快速属性约简算法,其时间复杂度和空间复杂度分别为max{O(|C||U)|,O(|C|2|U/C|2)}和max{O(|C||U/C|2),O(|U)|},最后用一个实例说明了新算法的高效性。

简化的二进制差别矩阵属性约简算法的改进

目前,基于二进制差别矩阵的属性约简算法有以下不足:所得到的属性约简与基于正区域的属性约简不一致。文献[7]中给出一种基于简化的二进制差别矩阵的快速属性约简算法,但该算法不完备。分析了算法不完备的原因,在此基础上,提出了一种改进的完备算法,该算法的时间复杂度为max(O(∣C||U∣),O(∣C∣2∣U pos||U/C))。

一种使用二进制差别矩阵的属性约简方法

针对区分矩阵属性约简算法中区分矩阵存在空值元素和重复元素等缺点,提出了一种基于二进制差别矩阵的属性约简算法.该算法不仅保证了属性约简的完整性和正确性,同时也降低了运算所需的时间和空间.

一个基于修正的二进制差别矩阵的快速求核方法

本文研究了二进制差别矩阵中核属性的性质,指出并证明了二进制差别矩阵求核的理论依据,在此基础上给出了一种二进制差别矩阵的修正方法及求核方法。该方法不仅适用于任何决策表信息系统(相容决策表和不相容决策表),而且有效地降低了计算代价。

基于浓缩差别矩阵的规则获取算法

基于HU的差别矩阵方法不仅构造费时且占用空间大,使得执行效率不高。利用元素间两两比较的方法构造浓缩差别矩阵的算法则时间复杂度过高,不适用大数据的处理。而将差别元素压缩存储在一棵FP树上,却无法去除无用的元素。为此,引入二叉树的思想,对短差别集依次建树,长差别集依次进行比较查找,提出一种改进的浓缩差别矩阵算法,在此基础上,给出扩展的二进制差别矩阵,直接从矩阵中提取规则。实验结果证明,该算法不仅降低了时间复杂度,还能够去掉无用元素,减少存储空间。

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

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

一种基于决策表的属性约简增量式快速更新算法

针对实际的决策表中的对象通常是动态变化的情况,首先引入了简化的决策表,然后在动态更新核的基础上,结合简化二进制差别矩阵和位图运算的设计思想,提出了一种快速的属性约简增量式更新算法.当有新对象加入决策表时,新算法只需验证新增的对象和原决策表中的对象是否一致性,然后采用在计算二进制差别矩阵的同时对原属性约简进行动态更新,从而有效地降低算法的时空复杂度,最后用实例说明了新算法的可行性和高效性.

基于知识粒度的不完备决策表求核方法

为降低不完备决策表求核算法的时间复杂度,本文构造了粒度二进制的差别矩阵。然后定义属性重要性及相应的核,由此设计了一个基于不完备决策表的粒度二进制差别矩阵的求核算法,并分析新算法的时间复杂度,其时间复杂度降为max{O(C U Upos),O(K C U)},优于同类算法的时间复杂度,最后用实例说明了该算法的有效性。

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

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

区间值决策系统下最短约简算法的研究

属性约简可以选出保持分类能力不变的属性子集,而最短约简不仅可以选出保持分类能力不变的属性子集,还可以最大程度地删除冗余属性、压缩决策表,选出最优的属性子集。本文在区间值决策系统的数据背景下,分别对针对决策属性的全部决策类和特定决策类构建二进制差别矩阵,结合SRA算法分别提出了基于二进制差别矩阵的最短约简算法和特定类最短约简算法。为了验证算法的有效性,选取8组UCI数据集分别从算法的约简结果长度和约简效率两方面进行对比,实验结果证明了算法的可行性和有效性。