|
1.
|
一个基于决策表的快速属性约简算法 被引次数：4
|
|
|
|
|
|
|
徐章艳 杨炳儒《小型微型计算机系统》,2006年第27卷第5期
|
|
|
在目前已出现的基于Rough Set的属性约简算法中，认为以近似质量为启发信息并非十分理想，以快速缩小搜索空间为目的设计了一个新的较为合理的度量属性重要性的计算公式，并给出了该公式的递归计算方法，计算该公式的算法的复杂度被降低到O（｜C-P｜｜U—UP｜），然后给出了一个时间复杂度为max（O｜C｜｜U｜log｜U｜，O（｜C｜^2｜U｜））的快速属性约简算法，最后用一个实例说明了算法的有效性．
|
|
2.
|
一种快速计算HU差别矩阵的属性约简算法 被引次数：7
|
|
|
|
|
|
|
徐章艳 杨炳儒 宋威 侯伟《小型微型计算机系统》,2008年第29卷第10期
|
|
|
在已有的基于HU差别矩阵的属性约简算法中,一般是以差别矩阵中的元素作为启发信息而设计的,其时间复杂度为O(|C|2|U|2).为降低该属性约简算法的时间复杂度, 首先引入简化决策表的定义,并设计了一个求简化决策表的算法,其时间复杂度为O(|C||U|).然后在简化决策表的基础上,定义了差别区域,并给出基于差别区域的属性约简定义,同时证明了基于差别区域的属性约简与基于差别矩阵的属性约简等价.在此基础上,以快速缩小简化决策表的搜索空间为目的,定义了一个新的、较为合理的、度量属性重要性的公式,并给出了它的递归计算方法,其时间复杂度为O(U/C|).最后以属性重要性为启发信息,设计了一个基于差别矩阵的快速属性约简算法,其时间复杂度降为max(O(|C||U|,O(|C|2|U/C|)),并用一个实例说明了新算法的高效性.理论分析与实验表明,新算法具有较好的扩展性.
|
|
3.
|
信息系统属性约简的快速算法
|
|
|
|
|
|
|
廖毅强 桂现才《计算机工程与设计》,2008年第29卷第18期
|
|
|
对目前已有的信息系统属性约简的启发式算法进行了分析,认为它们的时间复杂度不太理想.以快速缩小搜索空间为目的,先利用划分U/A对信息系统进行化简.设计了一个新的度量属性重要性的计算公式,并给出了该公式的递归计算方法.然后给出了一个时间复杂度为max{O(A‖U|),O|A|2|U/A|)}的快速属性约简算法,最后,实例及实验结果表明了该算法的有效性.
|
|
4.
|
基于改进的差别矩阵的快速属性约简算法 被引次数：2
|
|
|
|
|
|
|
钱进 叶飞跃 徐亚平《计算机工程与应用》,2008年第44卷第21期
|
|
|
为了解决基于差别矩阵属性约简的计算效率问题,首先以计数排序的思想设计了一个新的计算U/C的高效算法,其时间复杂度降为O(|C||U|)。其次分析了基于差别矩阵的属性约简算法的不足,提出了改进的差别矩阵的定义,利用快速计算核属性算法生成的核属性和出现频率最多的属性来降低差别矩阵的大小,并设计了基于改进的差别矩阵的快速属性约简算法,证明了该新算法的时间复杂度和空间复杂度分别被降为max(O|C|2Σ0≤i
|
|
5.
|
一个有效的基于信息熵的启发式属性约简算法 被引次数：3
|
|
|
|
|
|
|
徐章艳 侯伟 SONG Wei 宋威 杨炳儒《小型微型计算机系统》,2009年第30卷第9期
|
|
|
基于信息熵的属性约简算法都是以信息熵为启发信息设计的,其时间复杂度并不理想.为降低算法的时间复杂度,引入简化决策表的定义,设计了一个求简化决策表的算法,其时间复杂度为O(|C||U|).以快速缩小简化决策表的搜索空间为目的,定义了一个新的、较为合理的、度量属性的信息量,并给出了它的递归计算方法,其时间复杂度为P(| U/C|).同时证明了简化决策表上基于信息量的属性约简与原决策表上基于信息熵的属性约简是等价的.然后以属性的信息量为启发信息,设计了一个基于信息熵的快速属性约简算法,其时问复杂度降为max(O(|C||U|),O(|C|2|U/C|)),并用一个实例说明算法的有效性,实验结果表明新算法不仅具有高效性,且能处理大型决策表.
|
|
6.
|
一种相容矩阵的启发式属性约简算法
|
|
|
|
|
|
|
王帅 徐章艳 谭宗凤 舒文豪《计算机工程与应用》,2013年第49卷第1期
|
|
|
针对不完备决策表,黄兵给出一种基于容差关系的相容矩阵的属性约算法,但算法比较费时,其时间复杂度为O(|C|3|U|2)。为降低原算法的时间复杂度,以矩阵距离为启发信息,并运用矩阵合取的特性,设计了一个新的属性约简算法,算法时间复杂度降为O(|C|2|U|2)。通过实例验证了该算法。
|
|
7.
|
基于简化的二进制差别矩阵的快速属性约简算法 被引次数：7
|
|
|
|
|
|
|
徐章艳 杨炳儒 宋威《计算机科学》,2006年第33卷第4期
|
|
|
目前，基于二进制差别矩阵的属性约简算法有如下不足：算法的时间和空间复杂度不理想；所得到的属性约简与由基于正区域的属性约简的定义得到的属性约简不一致。本文给出一个简化的二进制差别矩阵和相应的属性约简的定义，证明了该定义与基于正区域的属性约简的定义是一致的。由于在简化的二进制的差别矩阵中，要先求出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｜））}。
|
|
8.
|
一种新的信息系统启发式属性约简算法 被引次数：1
|
|
|
|
|
|
|
崔巍 徐章艳《微电子学与计算机》,2010年第27卷第9期
|
|
|
为降低信息系统属性约简算法的时间复杂度,首先引入简化信息系统的概念,然后定义了简化信息系统中属性集的区分对象数,证明了基于简化信息系统区分对象数的属性约简与原属性约简是等价的.进而定义了简化信息系统的属性重要性,并设计了一个快速求属性重要性的算法.同时,以属性重要性为启发式信息,设计了一个新的属性约简算法.新算法的时间复杂度降为max{O(|C||U|),O(|C|2|U|C|)}.最后用一个实例说明了新算法的有效性.
|
|
9.
|
基于信息熵的二进制差别矩阵属性约简算法 被引次数：3
|
|
|
|
|
|
|
钱文彬 徐章艳 黄丽宇 杨炳儒《计算机工程与应用》,2010年第46卷第6期
|
|
|
给出一个简化的二进制差别矩阵的属性约简定义，并证明该属性约简的定义与基于信息熵的属性约简的定义是等价的。为求出简化的二进制差别矩阵，设计了一个快速求简化决策表的算法，其时间复杂度为O（|C||U|）。在此基础上，设计了基于信息熵的简化二进制差别矩阵的快速属性约简算法，其时间复杂度和空间复杂度分别为max{O（|C||U|），O（|C|2|U/C|2）}和max{O（|C||U/C|2），O（|U|）}，最后用一个实例说明了新算法的高效性。
|
|
10.
|
快速的属性约简算法 被引次数：1
|
|
|
|
|
|
|
胡彧 白琳林《计算机工程与应用》,2009年第45卷第28期
|
|
|
属性约简的效率是粗糙集等软计算理论的核心问题之一。为了提高约简效率,在分析不可分辨关系和基数排序特点的基础上,提出了一种时间复杂度为O(|C||U|)的求核算法。然后,运用改进的属性重要度作为启发信息,得到一种快速的属性约简算法,时间复杂度为O(|C|2|U)|。最后,通过UCI机器学习库中的一些数据集对算法进行测试,证明了算法对大型的数据集进行属性约简的高效性。
|
|
11.
|
一种快速的不完备决策表属性约简算法
|
|
|
|
|
|
|
舒文豪 徐章艳 钱文彬 杨炳儒《小型微型计算机系统》,2011年第32卷第9期
|
|
|
目前,关于不完备决策表的属性约简算法已有不少,其中在很多算法中,其时间复杂度为O( |C|3|U|2).为有效地降低算法的时间复杂度,给出一个差别矩阵的定义和基于差别矩阵属性约简的定义,并证明了该属性约简与基于正区域的属性约简是等价的.生成的差别矩阵无需比较Umeg之间的对象,使差别矩阵得到有效地简化,进一步降低算法的存储空间.在此基础上,利用简化的差别矩阵设计一个快速计算不完备决策表的属性约简的算法,其时间复杂度降为maX{O( |C|2|Upos,||U|),O(K|C||U|)}.(其中K=max{ |Tc(xi)|,xi∈U}).最后用实例仿真说明了新算法的有效性.
|
|
12.
|
一种信息系统的快速属性约简算法 被引次数：2
|
|
|
|
|
|
|
丁军 高学东《计算机工程与应用》,2007年第43卷第14期
|
|
|
在分析目前已有的基于Rough Set的属性约简算法后,认为计算属性的重要性的算法复杂度可以进一步降低,同时给出了一个新的较为合理的度量属性重要性的计算公式,并分析了该计算公式的性质,然后给出了一个时间复杂度为max｛O｜A‖U｜log｜U｜,O(｜A｜2｜U｜)｝的快速属性约简算法,最后用一个实例说明了算法的有效性。
|
|
13.
|
基于简化差别矩阵的完备属性约简算法 被引次数：4
|
|
|
|
|
|
|
徐章艳 杨炳儒 宋威《计算机工程与应用》,2006年第42卷第26期
|
|
|
由于基于老差别矩阵的属性约简的定义与基于正区域的属性约简的定义是不一致的,给出一个简化差别矩阵和相应的属性约简的定义,并证明了该定义与基于正区域的属性约简的定义是一致的。由于在简化差别矩阵中,要先求出IND(C),故设计了一个较好的求IND(C)的算法,其复杂度被降为O(｜C‖U｜)。在此基础上设计了一个完备属性约简算法,其时间复杂度和空间复杂度分别被降为max｛O(｜C｜2(｜U′pos‖U/C｜)),O(｜C‖U｜)｝和max｛O(｜U｜),O(｜C｜(｜U′pos‖U/C｜))｝。
|
|
14.
|
基于顺序表的启发式属性约简算法
|
|
|
|
|
|
|
梁宝华 汪世义 蔡敏《计算机工程》,2012年第38卷第2期
|
|
|
利用顺序表存储数据集对象，并借助基数排序按关键字“分配”思想，求解U/C的时间复杂度为 、空间复杂度为O(U)。在求属性约简集时，为避免存储差别矩阵所需的大量空间，利用差别矩阵的直观性，给出一种计算差别对象个数公式，并以此为启发信息，设计2种动态约简算法，其时间/空间复杂度分别为 、max( )。理论分析与实验结果表明该算法是有效可行的。
|
|
15.
|
改进的快速属性约简算法 被引次数：10
|
|
|
|
|
|
|
葛浩 李龙澍 杨传健《小型微型计算机系统》,2009年第30卷第2期
|
|
|
属性约简是决策表信息系统中一个重要操作.目前最高效的算法是徐章艳给出的RedueBaseSig算法,其时间复杂度为max{O(|C||U|),D(|C|2|U|)},但在某些情况下,该算法求得的并不是约简.文中分析了徐章艳算法的局限性.并提出改进的快速属性约简算法.该算法优化了等价类划分和正区域求解,以核属性为初始约简集,不断将重要性大的属性加入约简集中.在最坏情况下改进后算法的时间复杂度为O(|C|2|U|);而且实验结果表明,该算法是正确的、高效的.
|
|
16.
|
基于冲突域的高效属性约简算法 被引次数：2
|
|
|
|
|
|
|
葛浩 李龙澍 杨传健《计算机学报》,2012年第35卷第2期
|
|
|
引入冲突域的概念,研究冲突域的性质.以冲突域中冲突对象数目的变化为度量标准,给出核属性和属性重要性的计算方法,并设计了快速求解核属性和属性重要性的算法.在此基础上,给出高效属性约简算法,该算法以核属性为初始约简集,以属性重要性为启发式信息.在最坏情况下,算法的时间复杂度为O(|C|2|U|),空间复杂度为O(|U|);实验结果表明,该算法是正确的、高效的.
|
|
17.
|
一种新的信息熵属性约简算法 被引次数：1
|
|
|
|
|
|
|
舒文豪 徐章艳 杨炳儒 钱文彬《计算机工程与应用》,2009年第45卷第32期
|
|
|
给出一个区分对象对的属性约简定义,同时证明该属性约简的定义与基于信息熵的属性约简的定义是等价的。为求出区分对象对集,首先给出了一个快速求简化决策表的算法,其时间复杂度为O(|C||U)|。然后在简化决策表的基础上,设计了基于区分对象对集的信息熵属性约简算法,其时间复杂度和空间复杂度分别为O(|C||U)|+O(|C||U/C|2)和O(|U/C|2)+O(|U|),最后用一个实例说明了新算法的高效性。
|
|
18.
|
一种改进的基于二进制可分辨矩阵属性约简算法 被引次数：1
|
|
|
|
|
|
|
葛浩 杨传健 李龙澍《计算机技术与发展》,2008年第18卷第8期
|
|
|
指出支天云的二进制可分辨矩阵约简算法存在的不足,给出简化的决策表定义和基于二进制可分辨矩阵的属性频率函数的定义.在此基础上,以核属性为初始约简集,以属性频率为启发式信息,提出了一种改进的基于二进制可分辨矩阵的属性约简算法,其最终可以获得一个最优约简,并且算法时间复杂度和空间复杂度分别为max{O(|C||U|),O(|C|2|U'|2)}和O(|C||U'|2).通过实例验证,表明该算法是有效的.
|
|
19.
|
用差别矩阵思想设计的基于正区域的高效属性约简算法
|
|
|
|
|
|
|
韩智东 王志良 高静《小型微型计算机系统》,2011年第32卷第2期
|
|
|
近来一些学者用差别矩阵或差别矩阵的思想设计了基于正区域的属性约简算法.由于计算差别矩阵是一个既消耗时间又消耗空间的过程,故这些算法的效率并不好.为了降低这类属性约简算法的复杂度,文中利用基于区分对象对的属性约简的思想,在简化决策表的基础上,定义了一个函数,该函数能度量简化决策表中条件属性集产生的区分对象对的个数,并用该函数设计了一个启发函数,同时给出了计算该启发函数的快速算法,经分析其时间和空间复杂度均为O(|U/C|).最后用该启发函数设计了一个有效的基于正区域的属性约简算法,该算法的时间复杂度降为O(|C||U|),空间复杂度降为O(|U|).文中还用一个具体实例说明了新算法的有效性.经实验证明,新算法具有较高的效率.
|
|
20.
|
一种改进的基于二进制可分辨矩阵属性约简算法 被引次数：1
|
|
|
|
|
|
|
葛浩 ;杨传健 ;李龙澍《微机发展》,2008年第8期
|
|
|
指出支天云的二进制可分辨矩阵约简算法存在的不足，给出简化的决策表定义和基于二进制可分辨矩阵的属性频率函数的定义。在此基础上，以核属性为初始约简集，以属性频率为启发式信息，提出了一种改进的基于二进制可分辨矩阵的属性约简算法，其最终可以获得一个最优约简，并且算法时间复杂度和空间复杂度分别为max{O（｜C｜ ｜U｜），O（｜C｜^2｜ ｜U｜^2）}和0（｜C｜ ｜U｜^2）。通过实例验证，表明该算法是有效的。
|
|
