不完备决策系统中规则提取的快速矩阵算法

提出了广义决策的不可分辨关系及其不可分辨类、联合决策相容矩阵等概念以及不完备决策系统中基于联合决策相容矩阵的约简和规则提取的快速矩阵算法.将条件属性相容矩阵和决策属性分配决策矩阵合并到一个矩阵中,大大减少了矩阵生成过程的比较次数,有效的提高了算法的效率.通过一个实例,说明了算法的执行过程;算法复杂度分析以及相应的对比实验,进一步说明了该方法的有效性.     

基于相对分辨能力的属性约简算法

在粗糙集理论中,分辨能力反映拥有知识的多少;为此,给出分辨能力相关概念、性质和计算方法,并提出基于相对分辨能力的约简定义,同时研究该约简定义与Hu差别矩阵约简之间的等价性,指出Hu差别矩阵约简可由相对分辨能力约简获得.为了进一步提高求解效率,通过减少约简过程中基数排序次数来提升效率,设计了相对分辨能力的约简算法,其时间复杂度为O(|C|~2|U|).实例分析和UcI中数据集的实验比较表明所提出的约简算法是有效的、可行的.     

一种基于新的条件信息量的属性约简算法

为了获得决策系统中更好的相对约简,讨论了属性约简与条件信息量的关系,提出了新的条件信息量,由此定义新的属性重要性。统一了一致决策表和不一致决策表属性约简方法,以新的属性重要性为启发信息,给出了计算新的条件信息量的高效算法。理论分析和实验结果表明,与现有的基于条件信息量的约简算法相比,该算法时间复杂度较低,同时约简后的属性数目更少。     

基于信息量的不完备信息系统属性约简

通过引入信息量和条件信息量,对不完备信息系统中属性的重要性进行了定义;针对不完备数据表和不完备决策表提出了一种基于信息量和条件信息量的属性约简启发式算法,该算法的时间复杂度是多项式的.通过实例说明,该算法能得到信息表的约简和决策表的相对约简.     

基于差别矩阵的Rough集属性约简算法

差别矩阵非空元素的个数,直接影响基于差别矩阵的Rough集属性约简算法的效率。分析了几种差别矩阵的不足,基于此,重新定义了一种差别矩阵,该差别矩阵把划分U/C={[x1]C,[x2]C,…,[xn]C}的一个等价类看成一条规则参与区分,从而大大减少了差别矩阵非空元素的个数,提高了Rough集属性约简算法的效率。给出了这几种差别矩阵非空元素的计算公式及其相关定理。提出了一种带启发式知识的约简算法,该算法在很大程度上能找到决策表的最小属性约简。最后给出了对UCI一些数据库的仿真结果。     

基于限制容差关系和集对分析的数据依赖在IIS中的应用

利用限制容差关系和集对分析方法,分别给出了不完备信息系统(IIS)下对象依赖和属性依赖的定义,并将其应用于IIS约简,提出了利用基于限制容差关系的对象依赖进行对象约简和利用基于集对分析的知识依赖进行属性约简的方法以及相应的算法,以这些算法为依据进行约简得到了较好的结果.最后结合两个实例加以分析,验证这种限制容差关系模型和集对分析方法相结合的方法对处理IIS是合理有效的.     

测试代价敏感的粗糙集方法

在粗糙集模型中,α量化不可分辨关系是强与弱不可分辨关系的推广形式.然而值得注意的是,基于这三种不可分辨关系的粗糙集并未考虑数据中属性的测试代价.为解决这一问题,提出了测试代价敏感的α量化粗糙集模型,从二元关系的角度使得粗糙集模型代价敏感,并将新模型与基于强不可分辨、弱不可分辨以及传统α量化不可分辨关系的粗糙集模型进行了对比分析.进一步地,通过分析传统启发式算法在求解约简的过程中未考虑降低代价这一不足之处,提出一种新的属性适应性函数,并将其应用于基于遗传算法的约简求解中.实验结果表明该方法不仅可以降低由边界域所带来的不确定性而且同时降低了约简后的测试代价.     

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

为降低基于修正差别矩阵的属性约简算法的时间复杂度和空间复杂度,首先给出了简化差别矩阵的定义,并证明了该矩阵所包含的信息量与修正差别矩阵的信息量等价.其次设计了一个高效的求U/C的算法,其时间复杂度被降为O∑|C|i=1|ki||U|.然后分析了基于修正差别矩阵的属性约简算法的不足,并使用上述高效求U/C的算法,设计了一个基于简化差别矩阵的属性约简算法,证明了该新算法的时间复杂度和空间复杂度分别被降为maxO(|C|2(|Up′os||U/C|)),O∑|C|i=1|ki||U|和max{O|C|(|Up′os||U/C|)),O(|U|)}.最后用一实例说明了新算法的高效性.     

粗糙集理论中基于依赖空间的分布约简

约简是粗糙集理论中的一个核心问题,常用的约简方法有分辨矩阵和启发式算法两种。为了求得决策系统中的下、上近似和边界域分布约简,以构建在条件属性集合幂集上的等价关系为同余关系,利用同余关系依赖空间,提出了求得下、上近似和边界域分布约简的新方法,并给出了与这些约简对应的判定定理。通过实例分析验证了采用依赖空间方法可以求得保持所有决策类下、上和边界域都不发生变化的最小属性子集,为从决策系统中删除冗余属性提供了新的理论基础与技术手段。     

基于区分矩阵与强等价集的启发式知识约简法

提出了基于区分矩阵与强等价集的启发式知识约简方法。在决策表的相对约简过程中采用区分矩阵来表达知识,并利用区分矩阵中项的长度和每个属性的频率作为启发信息进行属性的选择。同时利用属性加权频率和强等价集概念化简区分矩阵,既减小了计算复杂度又提高了约简效率。现已证明,寻找决策表中最小相对约简问题是典型的问题,采用该算法在大多数情况下能够找到最小约简,即使在未找到最小约简的情况下,也能找到次优解。通过实例分析,证明该算法是求解属性相对约简的快速、有效的方法.