共查询到16条相似文献,搜索用时 187 毫秒
1.
基于信息熵的核属性增量式高效更新算法 总被引:1,自引:0,他引:1
针对基于信息熵求核算法效率不理想的情况,给出信息观下的二进制差别矩阵定义,理论上证明基于信息熵的核属性与基于二进制差别矩阵的核属性等价;并将决策表划分为相容的对象集和不相容的对象集,缩小求核算法的搜索空间;然后针对动态的决策表,研究核属性的增量更新机制,由此构造一种基于信息熵的核属性增量式高效更新算法。实例分析与实验结果验证文中算法优于同类求解算法。 相似文献
2.
3.
核属性求解是粗糙集理论的主要研究内容之一。针对现有差别矩阵求核算法的不足,给出决策差别矩阵定义和水平划分决策表方法。提出在子决策表上创建子决策差别矩阵,进行核属性求解的方法;并证明了由该方法获得核与正区域核是等价的,同时设计相应的串行和并行求核算法。实例分析和实验比较表明所提出的求核算法是正确的、高效的。 相似文献
4.
计算不完备决策表的核属性是粗糙集理论的重要内容之一。目前关于不完备决策表的求核算法的研究相对较少,而且在一般的求核算法中,其时间复杂度为[O(|C||U|2)]。为了有效地降低算法的时间复杂度,给出了一个不完备决策表的差别矩阵定义和基于差别矩阵的核定义,并证明了该定义与基于不完备决策表的核定义是等价的。在此基础上,利用差别矩阵方法来设计一种计算不完备决策表的求核算法,其时间复杂度降为[O(|C||Upos||U|)]。最后用仿真实例说明了新算法的有效性。 相似文献
5.
6.
7.
一种高效的增量式属性约简算法 总被引:2,自引:0,他引:2
针对粗糙集中求属性核和属性约简存在的问题,首先给出了改进的差别矩阵定义,进而提出一种基于改进差别矩阵的核增量式更新算法,用于解决对象动态增加情况下核的更新问题;同时,为了降低现有增量式属性约简算法的时间、空间复杂度,提出一种不存储差别矩阵的高效属性约简算法,用于处理对象动态增加情况下属性约简的更新问题.理论分析及实验结果均表明了所提出算法的有效性和可行性. 相似文献
8.
目前设计基于差别矩阵的求核算法的主要方法是差别矩阵方法.在该种方法中,是通过搜索差别矩阵的所有差别元素得到核.由于是在所有的差别元素上搜索,故该方法比较耗时.本文在简化决策表和简化差别矩阵的基础上,将具有核属性的差别元素集归纳在某一相对较小的集合上,故新算法只需搜索和检查简化差别矩阵的少量差别元素就可以得到核算属性集.设计了一个高效求核算法,其时间复杂度为max{O(|C|2|U/C|),O(|C||U|)},其空间复杂度为O(|U|).由于新算法只判断简化差别矩阵的少量差别元素就可以找到核算属性集,故新算法的效率得到了有效地改善. 相似文献
9.
10.
基于信息熵的快速求核算法 总被引:4,自引:0,他引:4
基于信息熵的求核算法的最好时间复杂度为O(C||2|U|log|U|).为降低算法的时间复杂度,本文首先给出了基于信息熵的简化差别矩阵及相应核的定义,并证明了该核与基于信息熵的属性约简的核是等价的.然后以基数排序的思想设计了一个新的求U/C的算法,其时间复杂度为O(|C||U|).在此基础上,设计了一个新求核算法,其时间复杂度被降为max{O(|C||U/C|2),O(|C||U|)}.最后用一个实例说明了新求核算法的高效性. 相似文献
11.
差别矩阵浓缩及其属性约简求解方法 总被引:4,自引:0,他引:4
属性约简是粗糙集理论的重要研究内容之一,已出现大量的属性约简算法,其中基于差别矩阵的属性约简算法是高效属性约简算法之一,但这些算法主要针对一致决策表,而对于不一致决策表,某些情况下不能得到属性约简。为此,本文提出改进的差别矩阵及其属性约简求解方法,统一考虑决策表一致和不一致情况两种情况下的属性约简,有效改进经典的基于差别矩阵求解属性约简的不足。同时,为适应大数据集属性约简需要,提出一种新的差别矩阵浓缩策略,以此提高属性约简的效率。 相似文献
12.
基于序关系的快速计算正区域核的算法 总被引:1,自引:0,他引:1
目前设计基于正区域的求核算法的主要方法是差别矩阵方法.该方法通过搜索差别矩阵的所有差别元素来得到核,故比较耗时.为此,在简化决策表和简化差别矩阵的基础上,若将其对象按条件属性值看成一个数,则对象是有序的.利用这个序,可将具有核属性的差别元素集映射到一个较小的搜索空间上,故只需判断简化差别矩阵的少量差别元素就可以找到核属性集.在此基础上,利用基数排序的思想,设计了一个高效求核算法,其时间复杂度为O(|C|2|U/C|)+O(|C||U|),空间复杂度为O(|U|).由于新算法只需判断简化差别矩阵的少量差别元素就可以找到核算属性集,故算法的效率得到了改善. 相似文献
13.
在利用差别矩阵求解决策表的相对核方法中,针对HU方法的错误,人们提出了各种各样新的差别矩阵及求相对核的方法,但计算代价高.把决策属性与条件属性放在一起构造出一个新的差别矩阵,得到了差别矩阵的若干性质和定理.在此基础上提出了求决策表的正区域、相对核、相对约简和最小约简的新算法,分析了该算法的时间复杂性.理论分析和实例表明,与现有的属性约简算法相比,该算法的时间复杂性较低. 相似文献
14.
15.
求核算法主要存在以下不足:对不相容决策表无法获得与正区域一致的核,求核算法的效率不够理想。针对上述问题,首先给出决策表的新定义和求核性质,并证明由该性质获得的核与正区域的核是一致的。然后,设计快速求核算法,其时间复杂度和空间复杂度分别降低为O(|C|2|U|)和O(|U|)。最后,实验验证该算法的有效性和高效性。 相似文献
16.
正区域是粗糙集理论中的核心概念之一,计算正区域的算法复杂度直接影响到其他算法的实现。借助于正区域的一种等价定义,提出了一种基于对角矩阵的计算正区域的方法。该方法把每次搜索到的相容对象集存放在对角矩阵的对角线上,并把已经搜索的对象进行归零处理,从而减少计算量。实例表明该方法计算方便,简单直观,能提高计算正区域的效率。 相似文献