共查询到18条相似文献,搜索用时 734 毫秒
1.
基于信息表的求核算法存在如下不足:需要完整求出U/R后方可求核.为此,先寻求理论依据,说明U/R与U/(R-{a})的内在关系,得出了[x]R-{a}/{a}细分[x]R-{a}的结论,证明了U/(R-{a})≠U/R与"U/R元素有兄弟"的等价性.然后基于二叉树设计思想,用兄弟存储结构设计了一个新的信息表求核算法,仅需生成较小的二叉树就能求核,时间复杂度和空间复杂度分别为O(|C|2|U|)和O(|U|).算法的主要贡献是将求核问题转化为等价类生成过程中兄弟的有无判断问题.通过实例验证了算法的有效性. 相似文献
2.
对于基于数据库系统的属性约简模型,给出相应的简化差别矩阵和相应核的定义,并证明该核与基于数据库系统的属性约简模型的核是等价的。在此基础上设计了一个新的求核算法,其时间复杂度和空间复杂度分别为max{O(|C||U/C|2),O(|C||U|)}和O(|U|)。 相似文献
3.
基于可分辨矩阵的快速求核算法 总被引:3,自引:0,他引:3
目前求核算法存在以下不足:求得的核与基于正区域的核不一致,算法的时间和空间复杂度不理想.针对上述问题,提出一种简化的可分辨矩阵的定义和求核方法,并证明了由该方法获得的核与基于正区域的核是等价的.为了提高算法效率,采用分布计数的基数排序思想设计等价类U/C划分算法,其时间复杂度为O(|C||U|).在此基础上,给出快速求核算法,其时间和空间复杂度分别降为max{O(|C||U/C|2),O(|C||U|)}和O(|C||U/C|2).最后,实例说明了算法的有效性. 相似文献
4.
给出一个简化的二进制差别矩阵的属性约简定义,并证明该属性约简的定义与基于信息熵的属性约简的定义是等价的。为求出简化的二进制差别矩阵,设计了一个快速求简化决策表的算法,其时间复杂度为O(|C||U|)。在此基础上,设计了基于信息熵的简化二进制差别矩阵的快速属性约简算法,其时间复杂度和空间复杂度分别为max{O(|C||U|),O(|C|2|U/C|2)}和max{O(|C||U/C|2),O(|U|)},最后用一个实例说明了新算法的高效性。 相似文献
5.
基于简化的二进制差别矩阵的快速求核算法 总被引:8,自引:0,他引:8
目前,基于二进制差别矩阵的求核算法有如下不足:算法的时间和空间复杂度不理想;所得到的核与基于正区域的核不一致.叶东毅教授提出了一个新的二进制差别矩阵并证明了在新的二进制差别矩阵中定义的核与基于正区域的核是一致的,但计算新的二进制差别矩阵除了具有和原方法相同的存储空间外,还增加了额外的计算.本文给出一个简化的二进制差别矩阵和相应的求核算法,并证明了所求的核是基于正区域的核.新算法的时间复杂度和空间复杂度分别被降为max{O(|C|(|U′pos‖U/C|)),O(|C‖U |)}和max{O(|U|),O(|C|(|U′pos‖ U/C|))}。 相似文献
6.
7.
基于信息熵的快速求核算法 总被引:4,自引:0,他引:4
基于信息熵的求核算法的最好时间复杂度为O(C||2|U|log|U|).为降低算法的时间复杂度,本文首先给出了基于信息熵的简化差别矩阵及相应核的定义,并证明了该核与基于信息熵的属性约简的核是等价的.然后以基数排序的思想设计了一个新的求U/C的算法,其时间复杂度为O(|C||U|).在此基础上,设计了一个新求核算法,其时间复杂度被降为max{O(|C||U/C|2),O(|C||U|)}.最后用一个实例说明了新求核算法的高效性. 相似文献
8.
目前,求核算法存在以下不足:求得的核与正区域的核不一致,求核算法的时间复杂度和空间复杂度不理想。针对上述问题,给出一种二进制可分辨矩阵的定义及其求核性质,并证明了由该性质获得的核与正区域的核是等价的,然后设计求核算法,该算法的时间复杂度为max{O(|C||U/C|2),O(|C||U|)},空间复杂度为O(|C||U/C|2)。最后实例说明该方法的可行性和有效性。 相似文献
9.
关于求核的算法有很多,本研究利用选择排序的思想设计了求解等价类的算法,其时间复杂度为O(|C||U|)。在此基础上,设计的求核算法,算法时间复杂度为O(|C|^(2)|U|)。通过实验,证明了算法的正确性和高效性。 相似文献
10.
在Rough Set理论中,计算属性核是最重要的计算之一。以桶排序的思想设计了一个新的求解U/C的算法,其时间复杂度被降为O(|C||U|)。基于此,提出了一个新的求核算法,其时间复杂度被降为[O(|C|2|U|)]。通过实验证明了求核算法的高效性。 相似文献
11.
12.
基于序关系的快速计算正区域核的算法 总被引:1,自引:0,他引:1
目前设计基于正区域的求核算法的主要方法是差别矩阵方法.该方法通过搜索差别矩阵的所有差别元素来得到核,故比较耗时.为此,在简化决策表和简化差别矩阵的基础上,若将其对象按条件属性值看成一个数,则对象是有序的.利用这个序,可将具有核属性的差别元素集映射到一个较小的搜索空间上,故只需判断简化差别矩阵的少量差别元素就可以找到核属性集.在此基础上,利用基数排序的思想,设计了一个高效求核算法,其时间复杂度为O(|C|2|U/C|)+O(|C||U|),空间复杂度为O(|U|).由于新算法只需判断简化差别矩阵的少量差别元素就可以找到核算属性集,故算法的效率得到了改善. 相似文献
13.
给出一个区分对象对的属性约简定义,同时证明该属性约简的定义与基于信息熵的属性约简的定义是等价的。为求出区分对象对集,首先给出了一个快速求简化决策表的算法,其时间复杂度为O(|C||U|)。然后在简化决策表的基础上,设计了基于区分对象对集的信息熵属性约简算法,其时间复杂度和空间复杂度分别为O(|C||U|)+O(|C||U/C|2)和O(|U/C|2)+O(|U|),最后用一个实例说明了新算法的高效性。 相似文献
14.
目前设计基于差别矩阵的求核算法的主要方法是差别矩阵方法.在该种方法中,是通过搜索差别矩阵的所有差别元素得到核.由于是在所有的差别元素上搜索,故该方法比较耗时.本文在简化决策表和简化差别矩阵的基础上,将具有核属性的差别元素集归纳在某一相对较小的集合上,故新算法只需搜索和检查简化差别矩阵的少量差别元素就可以得到核算属性集.设计了一个高效求核算法,其时间复杂度为max{O(|C|2|U/C|),O(|C||U|)},其空间复杂度为O(|U|).由于新算法只判断简化差别矩阵的少量差别元素就可以找到核算属性集,故新算法的效率得到了有效地改善. 相似文献
15.
在差别矩阵的基础上,针对不完备决策表提出了基于差别矩阵的区分对象对集定义,并证明求不完备决策表的核可以转化到求基于差别矩阵的区分对象对集上。在此基础上,提出了一种基于区分对象对的不完备决策表求核算法,该算法的时间复杂度为:[max{O(|C||U||Upos|),O(K|C||U|)}],优于同类算法的时间复杂度;用实例说明了新算法的有效性。 相似文献
16.
一种快速计算HU差别矩阵的属性约简算法 总被引:7,自引:0,他引:7
在已有的基于HU差别矩阵的属性约简算法中,一般是以差别矩阵中的元素作为启发信息而设计的,其时间复杂度为O(|C|2|U|2).为降低该属性约简算法的时间复杂度, 首先引入简化决策表的定义,并设计了一个求简化决策表的算法,其时间复杂度为O(|C||U|).然后在简化决策表的基础上,定义了差别区域,并给出基于差别区域的属性约简定义,同时证明了基于差别区域的属性约简与基于差别矩阵的属性约简等价.在此基础上,以快速缩小简化决策表的搜索空间为目的,定义了一个新的、较为合理的、度量属性重要性的公式,并给出了它的递归计算方法,其时间复杂度为O(U/C|).最后以属性重要性为启发信息,设计了一个基于差别矩阵的快速属性约简算法,其时间复杂度降为max(O(|C||U|,O(|C|2|U/C|)),并用一个实例说明了新算法的高效性.理论分析与实验表明,新算法具有较好的扩展性. 相似文献
17.
18.
针对不完备决策表,黄兵给出一种基于容差关系的相容矩阵的属性约算法,但算法比较费时,其时间复杂度为[O(|C|3|U|2)]。为降低原算法的时间复杂度,以矩阵距离为启发信息,并运用矩阵合取的特性,设计了一个新的属性约简算法,算法时间复杂度降为[O(|C|2|U|2)]。通过实例验证了该算法。 相似文献