共查询到16条相似文献,搜索用时 46 毫秒
1.
基于简化的二进制差别矩阵的快速求核算法 总被引:8,自引:0,他引:8
目前,基于二进制差别矩阵的求核算法有如下不足:算法的时间和空间复杂度不理想;所得到的核与基于正区域的核不一致.叶东毅教授提出了一个新的二进制差别矩阵并证明了在新的二进制差别矩阵中定义的核与基于正区域的核是一致的,但计算新的二进制差别矩阵除了具有和原方法相同的存储空间外,还增加了额外的计算.本文给出一个简化的二进制差别矩阵和相应的求核算法,并证明了所求的核是基于正区域的核.新算法的时间复杂度和空间复杂度分别被降为max{O(|C|(|U′pos‖U/C|)),O(|C‖U |)}和max{O(|U|),O(|C|(|U′pos‖ U/C|))}。 相似文献
2.
一个基于差别矩阵思想的高效求核算法 总被引:2,自引:1,他引:2
徐章艳 《计算机工程与应用》2004,40(17):74-75,79
目前,关于属性约简已有不少算法,其中在很多算法中,都要求先求出核属性集,但利用差别矩阵求核属性这一算法中,生成差别矩阵时,有许多不必要的元素被生成,这些无用的元素在求核时又要进行比较,因而效率不高。利用差别矩阵的思想设计一种不必生成那些不必要的元素的求核算法,从而使算法的效率得到提高。最后,给出了一个实例说明新算法的高效性。 相似文献
3.
基于信息熵的快速求核算法 总被引:4,自引:0,他引:4
基于信息熵的求核算法的最好时间复杂度为O(C||2|U|log|U|).为降低算法的时间复杂度,本文首先给出了基于信息熵的简化差别矩阵及相应核的定义,并证明了该核与基于信息熵的属性约简的核是等价的.然后以基数排序的思想设计了一个新的求U/C的算法,其时间复杂度为O(|C||U|).在此基础上,设计了一个新求核算法,其时间复杂度被降为max{O(|C||U/C|2),O(|C||U|)}.最后用一个实例说明了新求核算法的高效性. 相似文献
4.
求核是粗糙集中一个重要的研究内容之一。本文对杨明的基于差别矩阵求核方法进行研究,实例表明其方法还存在一些不完善。为了能够进一步提高求核效率,对差别矩阵进行改进,提出一种简化差别矩阵的定义,并给出求核方法,同时证明了由该方法获得的核与正区域的核是等价的,由此设计求核算法,其时间复杂度为max{O(|C||U|),O(|C||U/C||U′1|)},空间复杂度为O(|C||U/C||U′1|)。实验表明,该算法是有效的、高效的,且能适合大数据集的处理。 相似文献
5.
6.
7.
对于基于数据库系统的属性约简模型,给出相应的简化差别矩阵和相应核的定义,并证明该核与基于数据库系统的属性约简模型的核是等价的。在此基础上设计了一个新的求核算法,其时间复杂度和空间复杂度分别为max{O(|C||U/C|2),O(|C||U|)}和O(|U|)。 相似文献
8.
基于简化的二进制差别矩阵的快速属性约简算法 总被引:8,自引:0,他引:8
目前,基于二进制差别矩阵的属性约简算法有如下不足:算法的时间和空间复杂度不理想;所得到的属性约简与由基于正区域的属性约简的定义得到的属性约简不一致。本文给出一个简化的二进制差别矩阵和相应的属性约简的定义,证明了该定义与基于正区域的属性约简的定义是一致的。由于在简化的二进制的差别矩阵中,要先求出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|))}。 相似文献
9.
为提高基于Skowron差别矩阵的求核算法的效率,引入简化决策表的定义,给出了简化Skowron差别矩阵和相应核的定义,证明了新核与基于Skowron差别矩阵的核是一致的。提出一个基于Skowron差别矩阵的快速求核新算法,其时间复杂度和空间复杂度分别降为[max{O(|C||U/C|2),O(|C||U|)}]和[max{O(|U|),O(|C|)}]。 相似文献
10.
求核是粗糙集理论的主要研究内容之一.针对现有基于差别矩阵求核算法的不足,首先提出决策表简化的方法;然后,给出属性布尔差别矩阵的定义和基于属性布尔差别矩阵的核属性定义,并证明了该定义与基于正区域求核定义是等价的,同时设计相应求核算法;为了进一步提高求核效率和适应大数据集的处理,给出两个改进的求核算法.通过实例分析和实验比较,表明了本文所提出的求核算法是正确的高效的. 相似文献
11.
本文研究了二进制差别矩阵中核属性的性质,指出并证明了二进制差别矩阵求核的理论依据,在此基础上给出了一种二进制差别矩阵的修正方法及求核方法。该方法不仅适用于任何决策表信息系统(相容决策表和不相容决策表),而且有效地降低了计算代价。 相似文献
12.
利用差别矩阵进行求核运算时,矩阵中大量的空元素和重复差别元素会浪费很多存储空间及计算时间。针对上述问题,结合频繁模式树,设计一种新的数据结构——压缩树(C_Tree),在此基础上提出一种快速求核算法。理论与实例分析结果证明,该算法的时空复杂度取决于求简化决策表和构造C_Tree的时空复杂度,因此求核效率得到较大的提高。 相似文献
13.
14.
15.
一种快速计算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|)),并用一个实例说明了新算法的高效性.理论分析与实验表明,新算法具有较好的扩展性. 相似文献