二进制可辨矩阵的变换及高效属性约简算法的构造

This paper dose a lot of mathematics transformation to Binary Disernibility Matrix,it is called BDM too.Though these transformations,we may both decrease a lot of memory space of BDM and contribute to make high efficiency attributes reduction algorithms.Based on BDM,we also give three algorithms which are in turn used to reduce BDM,attribute‘‘‘‘s reduction and judge reduction.Finally,ew give three examples to illuminate the feasibility of three algorithms and analyze the complexity of algorithms.     

基于二进制可辨矩阵的决策规则约简算法

决策规则的约简是利用决策逻辑分别消去每一条决策规则中的冗余属性值,是粗糙集理论知识约简的重要内容,一般是在属性约简之后采用启发式信息实现决策规则的约简。基于二进制可辨矩阵给出一个简单的直接求取决策规则核的方法,并提出一种决策规则的约简算法。所给算法简单直观,不但适用于相容决策表,也适用于不相容的决策表。     

基于改进的二进制分辨矩阵属性约简算法

属性约简是粗糙集理论的重要研究内容之一,目前已有许多属性约简算法。但这些算法中主要针对一致决策表,当决策表是不相容的情况下,常用的计算全部属性约简的差别矩阵算法会产生错误的结果。为了解决这个问题,引入了一个改进的二进制分辨矩阵,提出了一种基于改进的二进制分辨矩阵的属性约简算法。并利用上述算法结合实例进行属性约简,证明了算法的正确性和有效性。     

一种基于二进制区分矩阵的属性约简算法

提出一种基于二进制区分矩阵的属性约简算法,将传统的区分矩阵以二进制形式表现出来,并且针对这个区分矩阵的特点,从两个不同的层次考察属性的重要性,引导求解过程趋于最优化．采用多个数据库进行试验,并与其它两种约简算法进行比较．实验结果表明,该算法是正确且高效的．     

基于二进制区分矩阵的增量式属性约简算法

增量式属性约简算法是动态数据挖掘技术的重要研究内容。为降低区分矩阵的存储空间,结合二进制区分矩阵便于计算以及形象直观的优点,给出一种压缩二进制区分矩阵的方法。将二进制区分矩阵的存储空间从|C|+1列简化成3列。通过动态更新二进制区分矩阵实现增量式求核,并以核为出发点,提出一种的增量式属性约简算法。通过实例计算及仿真实验验证了该算法的有效性。     

一种新的基于简化二进制可辨矩阵的相对约简算法

提出一种基于简化二进制可辨矩阵的启发武相对约筒算法,其特点是在扫描数据库的过程中形成规模很小的简化二进制可辨矩阵.基于简化二进制可辩矩阵构造了面向相对约简的矩阵变换方法.通过这种矩阵变换可从二进制可辨矩阵直接高效地导出相对约简.理论分析和实验结果说明和验证了该算法具有相对高效性和强可操作性等优点.     

基于信息熵的二进制差别矩阵属性约简算法

给出一个简化的二进制差别矩阵的属性约简定义,并证明该属性约简的定义与基于信息熵的属性约简的定义是等价的。为求出简化的二进制差别矩阵,设计了一个快速求简化决策表的算法,其时间复杂度为O（|C||U|）。在此基础上,设计了基于信息熵的简化二进制差别矩阵的快速属性约简算法,其时间复杂度和空间复杂度分别为max{O（|C||U|）,O（|C|²|U/C|²）}和max{O（|C||U/C|²）,O（|U|）},最后用一个实例说明了新算法的高效性。     

改进的基于简化二进制分辨矩阵的属性约简方法

在基于二进制分辨矩阵的属性约简方法中,删除法即从属性全集中依次删除冗余属性,直至剩余的属性集是一个最小约简.针对传统的基于二进制分辨矩阵的删除法效率较低且得不到最小约简的问题,提出一种改进的二进制分辨矩阵属性约简方法.首先对决策表进行简化,然后给出一种改进的简化二进制分辨矩阵方法;其次通过一个新的属性约简度量方法一次性删除多个属性,并从理论上分析了该方法的可行性;最后通过实验证明了得到的约简结果是最小约简.     

基于标识矩阵的粗糙集属性约简改进算法

属性约简是粗糙集理论研究中的核心内容之一,传统的由区分矩阵获得析取矩阵的方法多为全局搜索方法,该方法因重复计算会增加更多的运算时间并占用较大的存储空间;对此以引入标识矩阵构造方法,在标识矩阵中对属性的表示采用计算机更易处理的数字表示方法,仅对原始合取矩阵（OCM）中属性存在（即标识矩阵中为表示为1）的项作合取运算并删除标记属性全部存在（即全为1）的行,显著缩短了搜索空间,节省了计算时间。     

基于二进制可辨矩阵的肝功能检测数据约简方法

基于二进制可辨矩阵的数据约简方法具有直观性和可操作性的特点,因而在实际应用中受到开发人员的青睐。但已有的此类方法通常是在扫描数据集的过程中不加“削减”地直接产生大规模的二进制可辨矩阵,这导致较大的时间和空间开销。为此,利用对行的吸收律和逻辑和实现了对二进制可辨矩阵的规模进行有效缩减,构造一种新的基于二进制可辨矩阵的数据约简算法。它具有更好的可操作性,易于编程实现,其时间和空间复杂度都得到了较大的改善。在与某医院合作开发的项目中,该算法的应用已经进入测试阶段,可以较好完成了对肝功能检测数据（定性的数据）的约简,结果令人满意。     

简化的二进制差别矩阵属性约简算法的改进

目前,基于二进制差别矩阵的属性约简算法有以下不足:所得到的属性约简与基于正区域的属性约简不一致.文献[7]中给出一种基于简化的二进制差别矩阵的快速属性约简算法,但该算法不完备.分析了算法不完备的原因,在此基础上,提出了一种改进的完备算法,该算法的时间复杂度为max(O(|C||U|),O(|C|2|U'pos||U/C|)).     

基于遗传算法的粗糙集属性约简算法

针对粗糙集理论核心内容之一的知识约简问题,提出了一种基于遗传算法的粗糙集属性约简算法。利用条件熵计算属性间的相关性,并将其引入到适值函数中,可以保证所求约简含有较少的属性而且属性间的相关性较小。实验证明,它可以得到比较理想的结果,对UCI机器学习数据集的测试结果也验证了算法的有效性。     

一种基于粗集理论的属性约简改进算法

利用粗集理论中属性的依赖度和重要度性质,提出一种对数据属性进行约简的改进算法,对该算法进行分析,并运用一个简单的例子对该算法的有效性进行验证。     

属性约简矩阵特征结构及分层约简快速算法

已有的属性约简算法往往只能提供一个可行解,并且不能保证是最小约简解.因此,详细分析属性约简特征并获得最小约简解具有重要意义.本文针对信息系统数据集提出属性约简矩阵,通过矩阵的结构特征分析得到属性的约简特征,因此采用矩阵代数的方法求解属性约简问题,并得到分层约简快速算法.经实例运算可见,矩阵代数的处理和算法大大降低了最小约简解获取的计算量.     

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

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

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

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

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

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

基于可辨识矩阵的快速粗糙集属性约简算法

Karno Bozi提出的Core Searching算法在向约简中插入候选属性的时候,根据属性出现次数需要循环查找可辨识矩阵中的所有剩余项,直至矩阵为空,导致计算量较大和结果中冗余属性存在的可能.基于Core Searching算法提出通过给属性设立计数器的基于可辨识矩阵的快速属性约简算法,实例分析表明,该算法与Core Searching算法相比,在计算量减少和循环次数减少的同时能得到更简约的结果,是一种快速、高效的属性约简算法.