基于差别矩阵和动态划分域的属性约简算法

针对多数属性约简算法在构造差别矩阵时会产生大量重复元素,并且在约简过程中需要频繁的对整个论域进行等价划分等弱点,对降低属性约简和规则生成的复杂度作了研究.利用基于等价类的差别矩阵进行属性重要性计算,从规则相容度的角度出发,提出了一种等价划分域动态缩减的属性约简算法.该算法提高了属性约简的效率,同时完成确定规则决策树的构造.最后给出了具体的实例.     

一个新的差别矩阵及其在决策表中的应用

在利用差别矩阵求解决策表的相对核方法中,针对HU方法的错误,人们提出了各种各样新的差别矩阵及求相对核的方法,但计算代价高.把决策属性与条件属性放在一起构造出一个新的差别矩阵,得到了差别矩阵的若干性质和定理.在此基础上提出了求决策表的正区域、相对核、相对约简和最小约简的新算法,分析了该算法的时间复杂性.理论分析和实例表明,与现有的属性约简算法相比,该算法的时间复杂性较低.     

HU的属性约简方法与相对熵约简的等价性

出于不同的应用目的,许多学者提出了各种不同的属性约简概念.给出相对熵保持不变的条件,利用相对熵定义了决策表的相对熵约简,证明相对熵约简与HU的差别矩阵和差别函数的约简方法是等价的.     

差别矩阵属性约简的信息观解释

常见的属性约简定义有三种，即基于代数观的属性约简，基于信息观的属性约简和基于HU差别矩阵的属性约简。已有文献证明这三种属性约简彼此之间不等价。王国胤教授定义了一种新的决策表信息熵计算方法，在此方法基础上给出了粗糙集理论代数观的一种新的信息观解释。最近有学者提出了一种基于新信息熵的属性约简。经深入研究，我们证明了该属性约简与基于HU差别矩阵的属性约简是等价的，从而给出了基于HU差别矩阵的属性约简的信息观解释。     

属性与属性值合一的数据约简算法

提出一种数据约简算法.该算法从决策表中条件属性的等价类族考虑,分析决策值的等价类族,在约简过程中,可同时进行属性约简与属性值约简.与基于分析法或区分矩阵的传统约简等算法相比,本文算法可省略属性值约简中繁琐的比较过程,减少比较次数,提高约简效率.     

差别矩阵约简表示及其快速算法实现

差别矩阵可以拥有不同的信息, 根据差别矩阵描述的区分信息量不同, 给出4 种差别矩阵定义, 并提出相应H-约简、S-约简、B-约简和P-约简的概念; 研究4 种约简之间的关系, 构建通用约简算法模型. 为了提高约简算法的效率, 给出相对分辨能力约简定义(RD-约简), 揭示相对分辨能力约简与4 种差别矩阵约简之间的等价性, 进而设计相对分辨能力快速约简算法. 最后, 通过实例和UCI 数据集验证了所提出约简算法的有效性和时空性能.

     

不一致决策表信息熵约简与代数约简的核计算与转化

对不一致决策表,信息熵约简与代数约简有时会得到不同的属性约简和核属性,当前的方法多为先将不一致决策表转化为一致决策表,再对后者寻求高效算法.本文基于等价差别矩阵具有相同的核属性和属性约简的思想,提出一种以条件属性等价类构造简化的代数约简差别矩阵,从差别矩阵内部进行比较与分析,发现只须将信息熵约简差别矩阵中由同时为矛盾对象所产生的可辩识属性集剔除,即可转化为简化的代数约简差别矩阵,从而得到将信息熵约简核属性转化为代数约简核属性的新方法,理论分析与数值算例都验证了其正确性.     

一种快速计算HU差别矩阵的属性约简算法

在已有的基于HU差别矩阵的属性约简算法中,一般是以差别矩阵中的元素作为启发信息而设计的,其时间复杂度为O(|C|2|U|2).为降低该属性约简算法的时间复杂度, 首先引入简化决策表的定义,并设计了一个求简化决策表的算法,其时间复杂度为O(|C||U|).然后在简化决策表的基础上,定义了差别区域,并给出基于差别区域的属性约简定义,同时证明了基于差别区域的属性约简与基于差别矩阵的属性约简等价.在此基础上,以快速缩小简化决策表的搜索空间为目的,定义了一个新的、较为合理的、度量属性重要性的公式,并给出了它的递归计算方法,其时间复杂度为O(U/C|).最后以属性重要性为启发信息,设计了一个基于差别矩阵的快速属性约简算法,其时间复杂度降为max(O(|C||U|,O(|C|2|U/C|)),并用一个实例说明了新算法的高效性.理论分析与实验表明,新算法具有较好的扩展性.     

基于二进制区分矩阵的约简算法研究

给出了一种基于二进制区分矩阵的约简方法.首先基于粗糙集理论定义了二进制区分矩阵及运算规则、基于二进制区分矩阵的最小约简的判别及属性重要性的计算方法.在定义的基础上,给出了基于二进制区分矩阵的求核算法、相对属性约简算法及值约简算法.该约简方法以位操作为主与传统的约简方法比较不包括复杂的逻辑化简和集合运算,在一定程度上简化了计算,提高了约简效率.将该算法应用于数字电路设计的开关电路综合中,得到最简数字电路的逻辑表达,从而说明了算法的有效性.     

基于粗糙属性向量树的属性约简新方法

在对区分能力大小研究的基础上建立了一个用于指导信息表的绝对属性约简的粗糙集模型, 同时在对区分能力和分类能力二者关系深入研究的基础上提出了决策依赖区分精度新概念,该概念是用于指导决策表的、相对属性约简的一个新的判据.借助粗糙属性向量树提出了新的求全部属性约简的算法, 通过理论分析说明了新算法的最坏时间复杂度低于经典的"基于差别矩阵求全部属性约简算法"以及它的改进算法.对比实验结果验证了该算法在运算效率上明显高于"基于差别矩阵求全部属性约简算法"的改进算法.     

基于局部条件区分能力的高效属性约简算法

基于区分矩阵的传统属性约简方法具有直观易理解的优点,但时间和空间复杂度都很高,当数据规模较大或条件属性较多时,会无法快速得到约简结果.为解决该问题,在区分关系的基础上构造了条件区分能力来进行属性选择,提出一种基于条件区分能力的属性约简算法.而为了进一步加快属性重要性的计算、提高约简效率,依据大数定律中频率的稳定性,通过...     

基于决策表的区分矩阵增量属性约简算法

对于决策表中存在对象动态变化的现象,当利用静态的属性约简算法处理这类决策表时算法效率并不理想,为了有效提高增量属性约简算法的效率,对决策表进行了简化,并证明了基于简化区分矩阵的属性约简与基于区分矩阵的属性约简是一致的,在利用原的属性约简的基础上,提出了一种基于决策表的区分矩阵增量属性约简算法,通过实例分析说明算法的有效性和可行性。     

区分对象对集的不完备决策表属性约简

通过利用粗糙集中差别矩阵的思想,引入不完备决策表的区分对象对集的概念。并给出不完备决策表基于区分对象对集的属性约简定义。同时,也证明了利用该定义得到的不完备决策表的属性约简与基于正区域的属性约简是等价的。相比较基于正区域的不完备决策表属性约简算法,基于区分对象对集的属性约简算法时间复杂度是降低的。最后,用一个实例说明了该算法的合理性。     

基于分辨矩阵和约简树的增量式属性约简算法

为了对动态变化的决策表进行高效属性约简处理,在改进的分辨矩阵的基础上提出一种基于约简树的增量式属性约简算法IRART,该算法首先根据序贯属性约简算法对原决策表构造约简树,然后求出新增对象的分辨向量,并利用此向量对约简树进行修整,从而快速得到新决策表的所有约简,最后通过示例证明了这种算法的有效性。与传统增量式属性约简算法相比,该算法避免了复杂的逻辑演算,提高了属性约简的更新效率,理论分析表明该算法是有效可行的。     

差别矩阵HU属性约简的几种等价表示

对于一致决策表,现有基于相对粒度、相对划分粒度、知识量和同可区分度的属性约简与分别代数约简是等价的,但对于不一致决策表,它们与代数约简并不等价.为此,针对不一致决策表,建立相对粒度与新条件信息熵、知识量和同可区分度之间的线性关系,从而得出结论:现有基于相对粒度、相对划分粒度、知识量和同可区分度的属性约简本质上仅与基于差...     

基于差别矩阵的属性约简完备算法

分析了传统属性频率函数作为属性重要度的不足,重新定义了属性重要度,提出了一种基于差别矩阵属性重要度的属性约简完备算法,即CRABSA（Complete Reduction Algorithm Based on the Significance of Attribute）。该算法采用迭代思想,在每次迭代过程中根据属性重要度SGF（a）选择必要的条件属性加入约简R中。由SGF（a）的定义可知,算法能确保在大多数情况下能得到决策表的最小约简。分析了算法在最坏情况下的时间复杂度,给出了该算法相对Pawlak约简的完备性的证明。     

不相容决策表的属性约简算法

对Skowron可辨识矩阵方法进行分析,并应用反例说明基于Skowron可辨识矩阵的属性约简算法对不相容决策表的属性约简,可能会导致错误的结果。针对这一问题,提出了一种基于改进可辨识矩阵的属性频率约简算法。该算法以改进的可辨识矩阵为基础,以属性频率作为启发信息,同时在算法中加入消除冗余属性二次约简过程。提供了实例分析,验证了该算法能够有效地对相容与不相容的决策表进行属性约简。     

关于基于分明矩阵的属性约简算法的探讨

该文讨论了基于分明矩阵和近似度的属性约简算法之间的关系。在更为充分的挖掘分明矩阵的信息的条件下,提出一种新的基于分明矩阵的属性约简算法,对某些数据库可以取得更好的效果。     

决策表属性约简集的增量式更新算法

针对动态变化的决策表,研究了属性约简集的动态更新问题。在详细分析新增对象的所有可能情况的基础上,提出一种基于分辨矩阵元素集的属性约简集增量式更新算法。该算法根据新增对象的不同情况快速更新分辨矩阵元素集,依据分辨矩阵元素集中增加和减少的元素有效地更新原属性约简集,快速得到新的最小属性约简。最后,通过5个UCI的数据集验证了算法的有效性。