基于改进区分表的核属性约简算法

知识约简是一个NP难问题,在众多知识约简方法中,核属性基本上作为属性约简的初始解,这样就能有效地减小约简算法在属性空间中的搜索范围,在一定程度上加速了知识约简的进行.然而,核属性解基本上是利用Hu的分辨矩阵法求得的.结合Hu的分辨矩阵算法,讨论了Hu以及Wroblewaski区分表算法中存在的问题,改进了区分表的定义并结合Ye方法提出了基于区分表核属性约简算法,既克服了分辨矩阵方法的缺陷,又避免了区分表算法中存在的问题.实验结果表明该算法能有效求出决策系统的属性核.     

基于优势关系的粗糙集中的一种求核算法

随着粗糙集理论[1]的广泛应用,它得到了不断的发展与扩充.Greco等提出的基于优势关系的粗糙集方法[2]就是该理论的一种扩展模型,它用优势关系代替原来的不可区分关系,在多准则决策分析中得到了广泛的重视[5].由于优势关系是一种不同于不可区分关系的非对称关系,这使得该模型无法利用差别矩阵[3]来求核和约简.文[4]中提出了利用类区分矩阵来求约简,本文将用反例指出用这个方法求核和约简时存在错误,然后在该类区分矩阵的基础上,给出一个新的优势区分矩阵的定义和求核方法,并证明了该方法的正确性.     

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

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

     

基于信息Granule属性约简的求解

在传统基于分辨矩阵的约简方法中，用属性构成的集合表达对象间可区分性质；给出了信息Granule的二进制数构造方法，将对象间的可区分性质通过可区分函数的定义实现，并给出约简和核的求解算法。不难发现，后者比施行分辨矩阵更有利于在计算机上实现。     

基于优势区分矩阵的求核方法

在提出基于优势关系粗糙集方法下的类区分矩阵概念后,为解决不一致数据问题,新的优势区分矩阵定义及其求核方法被提出,但是该方法计算代价高。为了能够快速求出存在不一致数据的信息系统的核,该文给出改进的优势区分矩阵定义和求核算法,其空间和时间复杂度都优于现有的算法。实验证明,该算法适用于处理大数据集。     

一种基于分辨矩阵的新的属性约简算法

属性约简是粗糙集理论中的重要研究内容之一,但属性约简是一个NP难题,需要通过启发式知识实现.文中提出利用分辨矩阵求不同的条件属性组合相对于决策属性的正域的方法,并给出新的求核属性的方法.在此基础上,提出了一种利用分辨矩阵实现属性约简的新算法,该算法能快速求最少属性且实现简单,并实现了属性约简与规则提取的同步,最后通过实例证明了其正确性.     

改进的优势区分矩阵及其求核方法

研究了优势关系下不协调决策表的优势区分矩阵及其求核方法。用反例指出利用文献[6]中的优势区分矩阵来求核的方法是错误的,给出一个改进的优势区分矩阵的定义和求核方法,其空间和时间复杂度都优于现有的算法。     

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

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

基于新特征优势关系的知识约简模型

针对同时具有缺席和遗漏型未知属性值的广义不完备序信息系统,给出一种基于新特征优势关系的知识约简方法.首先,利用属性值的偏序特点提出了两种不同形式的新特征优势关系.新特征优势关系既保留了已有特征优势关系的优点,又在一定程度上克服了已有特征优势关系的局限性,是已有特征优势关系的进一步推广.然后,针对这两种新特征优势关系,分别给出了广义不完备序信息系统下知识约简的判定定理,定义了基于区分矩阵的区分函数,并利用布尔推理得到了这两种新特征优势关系下知识约简的具体操作方法,同时给出实例对结论和方法加以说明和演示.     

优势关系下广义决策约简和上近似约简

论文定义了决策表的优势关系下广义决策约简和上近似约简,给出了优势关系下广义决策约简和上近似约简的判定定理和辨识矩阵。同计算优势关系下上近似约简的辨识矩阵相比,计算优势关系下广义决策约简的辨识矩阵的时间复杂度低,由于论文已证明优势关系下广义决策约简和上近似约简是等价的,因此,可以利用优势关系下广义决策约简的辨识矩阵计算优势关系下广义决策约简和上近似约简。     

基于水平划分决策表的核属性求解算法

核属性求解是粗糙集理论的主要研究内容之一。针对现有差别矩阵求核算法的不足,给出决策差别矩阵定义和水平划分决策表方法。提出在子决策表上创建子决策差别矩阵,进行核属性求解的方法;并证明了由该方法获得核与正区域核是等价的,同时设计相应的串行和并行求核算法。实例分析和实验比较表明所提出的求核算法是正确的、高效的。     

基于优化可辨识矩阵和改进差别信息树的属性约简算法

运用可辨识矩阵表示信息系统中所有对象的区分信息,为研究属性约简提供了新方向。然而,传统的可辨识矩阵在构造结束后才利用核属性消除冗余元素项,忽略了核属性在矩阵构建过程中的作用。针对这一问题,文中做了以下研究:1)优化可辨识矩阵的构造方式,在计算任意两个对象的区分信息之前,先判断核属性上的取值是否相等,如果不相等,则直接将对应元素项记为Φ,忽略对其他条件属性的判断;2)提出属性加权重要度的概念,综合考虑每个条件属性占可辨识矩阵中非空元素项的比率(称为宏观重要度)与每个属性对区分对象的贡献程度(称为微观重要度),并通过例子说明了该度量方法的合理性;3)针对优化后的矩阵仍然存在大量冗余元素和空集这一缺陷,结合差别信息树的概念提出基于优化可辨识矩阵和属性加权重要度的差别信息树。按照属性加权重要度对优化可辨识矩阵中所有非空元素项进行排序,使得重要度高的属性被更多的节点共享;且在构建过程中将不包含核属性的元素项映射到树中的一条路径上,而包含核属性的元素项则被直接忽略。最后,提出基于优化可辨识矩阵和改进差别信息树的约简算法HSDI-tree。在UCI的5个数据集上分别比较了HSDI-tree算法与CDI-tree,DI-tree和IDI-tree算法的约简结果和节点个数,实验结果表明HSDI-tree算法能有效找到最小属性约简且空间压缩能力更好。     

基于属性分辨度的最大相容块规则提取算法

提出一种基于属性分辨度的不完备决策表规则提取算法, 它是一种例化方向的方法. 首先从空集开始, 逐步 选择当前最重要的条件属性对对象集分类, 从广义决策值唯一的相容块提取确定规则, 从其他的相容块提取不确定 规则; 然后设计属性必要性判断步骤去除每条规则的冗余属性; 最后通过规则约简过程来简化所获得的规则, 增强规 则的泛化能力. 实验结果表明, 所提出的算法效率更高, 并且所获得的规则简洁有效.

     

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

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

决策表化简及其属性约简方法

给出一种求不一致决策表的核和所有属性约简的新方法,首先利用U/C对决策表进行化简,然后在简化的决策表上定义新的差别矩阵,最后利用差别函数求出所有属性约简.该方法可有效降低生成差别矩阵时所需的存储空间和时间,理论分析和例子表明,该属性约简方法在效率上比现有的基于差别矩阵和差别函数的方法有显著提高.     

新的可分辨矩阵及其约简方法

为了解决因决策表存在不相容性造成求核和属性约简的错误,首先通过增加一个属性列,将原始决策表相容化;然后创建可分辨矩阵,并给出核属性和属性约简的性质,同时证明了由该性质获得的核和属性约简与正区域的核和属性约简是等价的;最后设计属性约简算法及其改进算法,并通过实例验证了该方法的正确性.     

一种分布式的决策表核属性计算方法

针对决策表核属性的计算问题,首先对前人的一些结论观点进行了讨论,在认识这些理论观点缺陷的基础上,给出了分明矩阵的一个新的表示定义,并由此提出了一种新的核属性计算方法。然后依据论域中各对象在某个条件属性上的不同取值把决策表信息系统划分为多个子决策表信息系统,给出了几条相关性质以及子决策表与原决策表核属性的关系定理。最后提出了一种决策表核属性的分布式计算方法,实例分析表明该算法是有效的。     

基于系统熵的属性约简的简化差别矩阵方法*

基于系统熵的属性约简是一种新型的属性约简。该模型由于同时考虑了条件属性集和决策属性集对决策表的分类能力,它是一种考虑较周全的属性约简模型。为设计高效的属性约简算法,首先引入简化差别矩阵, 同时给出了基于该简化差别矩阵的属性约简定义,并证明该定义与基于系统熵的属性约简定义等价;然后用简化差别矩阵设计了一个基于系统熵的完备属性约简算法;最后用实例说明了新算法。     

同可区分度属性约简的研究

通过具体算例指出基于同可区分度属性约简不是王国胤等提出的条件信息熵约简。理论上证明了基于同可区分度属性约简仅是基于差别矩阵的HU属性约简,它是一种基于梁吉业等提出的新条件信息熵属性约简。证明了同可区分度约简协调集一定是代数协调集和信息熵协调集,从而代数约简核属性和信息熵核属性一定是同可区分度约简核属性的子集。