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

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

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

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

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

为降低基于修正差别矩阵的属性约简算法的时间复杂度和空间复杂度,首先给出了简化差别矩阵的定义,并证明了该矩阵所包含的信息量与修正差别矩阵的信息量等价.其次设计了一个高效的求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|)}.最后用一实例说明了新算法的高效性.     

一类对Jenolek属性约简算法的新的改进方法

在分析了Jenolek属性约简算法和已有的对其改进算法的基础上，提出了一类新的改进方法，主要是利用辅助空间保存属性信息，并且利用排序操作、决策表预处理、寻找核属性集、属性扩展等技术，在保持Jenolek算法性能不变的情况下在时间复杂度方面比已有的方法获得了更大的改进。     

基于粗糙逻辑的增量式属性约简算法

知识约简、决策规则的获取是粗糙集理论研究的核心内容。以粗糙逻辑为基础，首先给出了在新实例加入论域后判断约简变化与否以及判断原极小决策算法中决策规则变化与否的判定依据。在此基础上，提出了一种增量式属性约简算法。该算法能有效地减少计算属性约简与极小决策算法的计算量，提高了计算效率。     

一种新的决策表属性约简算法

结合模糊聚类技术与粗糙集中属性重要性思想,对同时含有连续、离散、序数型条件属性的决策表,提出一种属性约简算法,并对算法的时间复杂度进行了分析.该方法首先利用聚类技术将决策表的对象按条件属性进行分类,然后对去掉某属性后的决策表采用同样的方法进行聚类,再结合粗糙集理论进行属性约简.实例说明了该方法的合理性和有效性.     

决策分析中属性约简的择优算法

粗糙集理论在决策分析中具有广泛的应用。基于优势关系的粗糙集理论只给出如何进行属性约简以得到决策规则的方法，本文则进一步研究了如何针对不同的属性约简如何进行选择。在优势关系的基础上引入格序的概念，利用序关系给出属性约简的贴近度，借此比较了不同约简下所得决策规则贴近于原知识库的程度，并通过一个具体例子加以说明。     

变精度粗糙集属性约简的算法

针对变精度粗糙集属性约简问题,在分析变精度粗糙集理论的基础上,分别从属性依赖度增量、互信息的增量、基于覆盖度与准确度相结合的度量以及属性的不确定性量度等角度,对属性重要度进行分析。并分别以这四个属性重要度作为启发式信息,提出变精度粗糙集属性约简的启发式算法,进而得到信息系统的最小约简,并将所给的算法应用MATLAB程序进行实现。最后,通过具体算例说明所给算法的有效性和实用性。     

属性约简中的近似问题研究

现有相对约简实际上只是在保持所关心范畴的下近似不变的前提下对属性进行约简,这对于不协调信息系统来说,可能会使所关心范畴的上近似变大,从而使其近似精度减小,导致有用信息的丢失.为此,针对属性约简中的近似问题进行了研究,引入近似相对约简概念,利用近似相对约简替代现有相对约简来处理不协调信息系统,以克服现有相对约简在不协调信息系统中所带来的缺陷.同时,证明了在协调信息系统下,条件属性集相对决策属性集的近似相对约简和相对约简是等价的,并提出了一种基于近似相对约简的简便属性约简算法.     

基于冲突域渐减的属性约简算法

针对因决策表中存在不一致对象造成的约简求解错误,同时为了进一步提高约简算法求解效率, 首先,给出简化决策表的定义,并证明了简化决策表的核属性和属性约简与原始决策表的核属性和属性约简是等价的. 然后,提出冲突域的概念,分析冲突域的性质,以冲突域中冲突对象个数的变化为度量依据, 研究核属性和属性重要性的性质,同时设计相应的核属性和属性重要性求解算法;在此基础上, 设计基于冲突域渐减式属性约简算法,算法的时间和空间复杂度分别为O(|C|²|U/C|)和O(|U|). 最后的实例和实验结果表明该方法是正确的,高效的.     

Cooperative extended rough attribute reduction algorithm based on improved PSO

Particle swarm optimization (PSO) is a new heuristic algorithm which has been applied to many optimization problems successfully. Attribute reduction is a key studying point of the rough set theory, and it has been proven that computing minimal reduction of decision tables is a non-derterministic polynomial (NP)-hard problem. A new cooperative extended attribute reduction algorithm named Co-PSAR based on improved PSO is proposed, in which the cooperative evolutionary strategy with suitable fitness functions is involved to learn a good hypothesis for accelerating the optimization of searching minimal attribute reduction. Experiments on Benchmark functions and University of California, Irvine (UCI) data sets, compared with other algorithms, verify the superiority of the Co-PSAR algorithm in terms of the convergence speed, efficiency and accuracy for the attribute reduction.     

一种基于分明矩阵的启发式知识约简方法

提出了基于分明矩阵的启发式知识约简方法。在决策表的相对约简过程中采用分明矩阵来表达知识,并利用分明矩阵中项的长度和每个属性的频率作为启发信息进行属性的选择。现已证明,寻找决策表中最小相对约简问题是典型的NP hard问题。所提供的算法在大多数情况下能够找到最小约简,即使在没找到最小约简的情况下,也能找到次优解。通过实例分析,证明该算法是求解属性相对约简的快速有效的方法     

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

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

Enhanced minimum attribute reduction based on quantum-inspired shuffled frog leaping algorithm

Attribute reduction in the rough set theory is an important feature selection method,but finding a minimum attribute reduction has been proven to be a non-deterministic polynomial(NP)-hard problem.Therefore,it is necessary to investigate some fast and effective approximate algorithms.A novel and enhanced quantum-inspired shuffled frog leaping based minimum attribute reduction algorithm(QSFLAR) is proposed.Evolutionary frogs are represented by multi-state quantum bits,and both quantum rotation gate and quantum mutation operators are used to exploit the mechanisms of frog population diversity and convergence to the global optimum.The decomposed attribute subsets are co-evolved by the elitist frogs with a quantum-inspired shuffled frog leaping algorithm.The experimental results validate the better feasibility and effectiveness of QSFLAR,comparing with some representative algorithms.Therefore,QSFLAR can be considered as a more competitive algorithm on the efficiency and accuracy for minimum attribute reduction.     

一种基于条件熵的增量核求解方法

分析了增加新对象后,决策表的决策属性关于条件属性的条件熵变化原理. 并在此基础上提出了一种新的增量核求解算法. 该算法只需找到与新对象属性值相等的条件类和决策类就可以得到新的条件熵,进而求得决策表在信息观下的增量属性核. 实例证明了该算法的有效性.     

粗等价类双边递减下多次Hash的渐增式求核与约简算法

为设计高效约简算法,首先以全局等价类为最小计算单位提出粗等价类概念,证明粗等价类下约简与原信息系统等价;然后深入剖析1,0,-1三类粗等价类的性质,把求正区域等价转化为0-粗等价类双边递减下的渐增式计算,结合1和-1-粗等价类的传递性,设计双边横向删减实体和纵向删减属性的优化规则,可在每一轮增量计算中缩减计算域,基于此设计多次Hash的属性增量划分方法;最后给出新的渐增式快速求核与约简算法,其中求核基于纵向优化规则,可在一次计算中求得多个非核属性,无需遍历全部属性.基于UCI、海量和超高维3类数据集进行多个实验,实验结果证明本文求核与约简算法是高效完备的,在海量数据与超高维数据集下有较大优势.     

模糊信息系统知识约简的分辨函数法

知识约简是粗糙集理论的重要研究内容.针对不同的粗糙集模型和约简定义,给出相应的知识约简方法一直是知识约简的主要任务.以分辩函数法为代表的各种符号值信息系统知识约简方法已得到深入研究.将分辨函数引入模糊信息系统,得到相应的知识约简分辨函数法,并通过实例分析说明了该方法的具体计算步骤.这为从模糊信息系统中获取知识提供了一种有效的粗糙集方法.     

基于区分对象对集的快速求核算法

为降低基于正区域求核算法的时间复杂度,首先给出了简化决策表和简化差别矩阵及其核的定义。然后给出了简化决策表中条件属性的区分对象对集的定义,并得出区分对象对集与决策表核属性的关系,证明了求决策表的核可以转化到求条件属性的区分对象对集上。再结合简化差别矩阵的核的性质,设计了一个基于区分对象对集的快速求核算法。该算法的时间复杂度优于同类算法的时间复杂度。最后用实例说明了新算法的有效性。