一种完备的最小属性约简方法

基于集合枚举树的最小属性约简算法蒋瑜【摘要】为了寻找一种有效的最小属性约简方法,给出了条件属性集上的属性重要度序关系,基于此序关系构建了属性集上的集合枚举树,提出了一种快速的最小属性约简算法,该算法采用至上而下、层次优先策略搜索集合枚举树寻找属性最小约简.为了提高算法性能,该算法采用核和父集剪枝策略减少搜索空间,采用优化计算来确保同一集合的正域只计算一次.基于UCI数据的实验结果表明,该算法是有效的.【期刊名称】《计算机工程与应用》【年(卷),期】2013(049)011【总页数】4页(P101-104)【关键词】粗糙集;最小约简;集合枚举树;属性重要度;剪枝【作者】蒋瑜【作者单位】成都信息工程学院软件工程学院,成都610225【正文语种】中文【中图分类】TP311粗糙集理论是由波兰学者Pawlak于1982年提出的[1-2]，是一种刻划具有不完整性和不确定性信息的全新数学工具。

其主要思想是在保证知识库的分类能力不变的前提下，通过知识约简导出问题的决策或分类规则。

知识约简问题是粗糙集理论的一个核心问题[3-4]。

所谓知识约简，就是在保证知识库分类能力不变的条件下删除其中不相关或不重要的冗余知识。

一般来讲，一个决策表的属性约简不是唯一的，通常人们往往希望能够找到一个冗余度最小的属性约简，该属性约简被称为最小属性约简。

对任一给定决策表，若属性约简算法能确保找到其最小属性约简，则该算法称为最小属性约简完备算法。

然而，S.K.M Wong和W.Ziarko已经证明了找一个决策表的最小约简是NP-hard问题[3]。

导致NP-hard问题的主要原因是属性的组合爆炸问题。

目前已存在一些属性约简算法能够找到决策表的最小属性约简[4-12]，但它们要么不是完备的最小属性约简算法，要么通过穷举求出问题的所有约简或所有最小约简。

本文重新定义了属性重要度，给出了条件属性集上的序关系，基于该序关系构建集合枚举树，提出了一种基于集合枚举树的最小属性约简算法。

二进制可分辨矩阵的最小属性约简算法
李龙澍;王慧萍;徐怡
【期刊名称】《计算机技术与发展》
【年(卷),期】2010(020)006
【摘要】指出传统分辨矩阵的不足,给出了二进制可分辨矩阵的定义以及二进制可分辨矩阵元素集合的形成算法.精简了分辨矩阵元素.在此基础上,提出了一种基于二进制可分辨矩阵的最小属性约简算法.该约简算法以属性频率为选择条件,按照普通可分辨矩阵生成属性约简的原理,但以不同的形式,更少的存储空间,最终可以获得一个最小属性约简.通过对一个汽车数据库的数据进行属性约简,并将结果与其他算法的结果进行比较,证明该算法是可行有效的.
【总页数】5页(P93-96,100)
【作者】李龙澍;王慧萍;徐怡
【作者单位】安徽大学,计算机科学与技术学院,安徽,合肥,230039;安徽大学,计算机科学与技术学院,安徽,合肥,230039;安徽大学,计算机科学与技术学院,安徽,合肥,230039
【正文语种】中文
【中图分类】TP301.6
【相关文献】
1.改进的基于简化二进制分辨矩阵的属性约简方法 [J], 王亚琦;范年柏
2.基于改进的二进制分辨矩阵属性约简算法 [J], 郭洪涛;黄广君;张孝国
3.二进制分辨矩阵在连续属性约简中的研究 [J], 杨云霞;杨占勇
4.一种新的基于二进制分辨矩阵的属性约简方法 [J], 陈宸;赵军
5.一种改进的基于二进制可分辨矩阵属性约简算法 [J], 葛浩;杨传健;李龙澍
因版权原因，仅展示原文概要，查看原文内容请购买。

属性约简方法概述属性约简又称维规约或特征选择，从数学的角度考虑，就是有p 维数据 x =(x 1,x 2……x p )，通过某种方法，得到新的数据 x’=(x’1,x’2…… x’k ) , k ≤p , 新的数据在某种评判标准下，最大限度地保留原始数据的特征。

属性约简主要是为了解决高维数据计算的复杂性和准确性问题。

目标是消除冗余和不相关属性对计算过程和最终结果造成的影响。

对数据进行属性约简的意义，主要从以下几个方面考虑：a) 从机器学习的角度来看，通过属性约简去除噪音属性是非常有意义的； b) 对一些学习算法来说，训练或分类时间随着数据维数的增加而增加，经过属性约简可以降低计算复杂度，减少计算时间；c) 假如不进行属性约简，噪音或不相关属性和期望属性对分类的作用一样，就会对最终结果产生负面影响；d) 当用较多的特征来描述数据时，数据均值表现得更加相似，难以区分。

为了描述属性约简方法，这里假设数据集合为D ，D ={x 1,x 2….x n }, x i 表示D 中第i 个实例，1≤i≤n ，n 为总的实例个数。

每个实例包含p 个属性{|x i |=p }。

从机器学习的角度来看，属性约简方法可以分为监督的和非监督的两类。

下面是几种常用的方法。

(1) PCA 主成分分析主成分概念是Karl parson 于1901年最先引进。

1933年，Hotelling 把它推广到随机变量。

主成分分析把高维空间的问题转换到低维空间来处理，有效的降低了计算的复杂度。

通过主成分的提取，降低了部分冗余属性的影响，提高了计算的精度。

主成分分析的基本思想为：借助一个正交变换，将分量相关的原随机变量转换成分量不相关的新变量。

从代数角度，即将原变量的协方差阵转换成对角阵；从几何角度，将原变量系统变换成新的正交系统，使之指向样本点散布最开的正交方向，进而对多维变量系统进行降维处理[43]。

定义4-1[44]：设12(,,...,)'p X X X X =为p 维随机向量，它的第i 主成分分量可表示'i i Y u X =，i =1,2,…, p 。

一种完备的最小属性约简方法于海燕;乔晓东【期刊名称】《计算机工程》【年(卷),期】2012(038)004【摘要】为解决粗糙集中的属性约简问题,提出一种完备的最小属性约简方法.将差别矩阵中所有有关属性区分的信息都浓缩进一个差别向量组,计算每个属性在区分2个对象的属性集合中出现的概率,作为属性重要性的启发式信息,建立最小属性约简树,得到属性约简.分析结果表明,该方法可以获得所有的最小属性约简.%Attribute reduction is the basic problem of rough sets theory. A method for minimal attributes reduction in consistent decision table is proposed in this paper. The discernible information in consistent decision tables is described with discernible vector array. A minimal attribute reduction tree is generated based on the probability of the attributes which discern two objects. All minimal attribute reductions are got from minimal attributes reduction tree. The result of the method is proved to be complete and minimal.【总页数】3页(P46-48)【作者】于海燕;乔晓东【作者单位】中国科学技术信息研究所信息技术支持中心,北京100038;中国科学技术信息研究所信息技术支持中心,北京100038【正文语种】中文【中图分类】TP311.12【相关文献】1.一种改进的不完备熵属性约简在装备故障诊断中应用 [J], 苏艳琴;张光轶;徐廷学2.一种基于冲突域的不完备决策表属性约简算法 [J], 周建华;徐章艳;章晨光3.不完备决策表的一种属性约简方法 [J], 周玉华;李景杰4.不完备系统中一种增量式属性约简算法 [J], 王光琼5.不完备邻域决策粗糙集的最小化代价属性约简算法 [J], 姚晟;李初宴;吴照玉因版权原因，仅展示原文概要，查看原文内容请购买。

基于二进制可辨矩阵属性重要度的属性约简算法
汪小燕
【期刊名称】《安徽工业大学学报（自然科学版）》
【年(卷),期】2007(024)001
【摘要】粗糙集理论是一个新的数据挖掘方法,是在保持分类能力不变的情况下,利用等价类,通过属性约简和规则约简,达到挖掘知识并简化知识的目的.但属性约简是一个NP难题,需要通过启发式知识实现.文中提出了一种利用二进制可辨矩阵的属性重要度实现属性约简的算法,该算法能快速求最少属性且实现简单,并通过理论和实例证明了其正确性.
【总页数】4页(P76-78,97)
【作者】汪小燕
【作者单位】安徽工业大学,计算机学院,安徽,马鞍山,243002
【正文语种】中文
【中图分类】TP3
【相关文献】
1.基于二进制可辨矩阵的属性约简算法的改进 [J], 周海岩;杨汀
2.二进制可辨矩阵的变换及高效属性约简算法的构造 [J], 支天云;苗夺谦
3.基于核搜索和二进制可辨识矩阵的属性约简算法 [J], 崔建华;褚蕾蕾;常文波
4.一种基于二进制可辨矩阵的属性约简算法 [J], 王希雷;马永军
5.基于可辨识矩阵的属性约简算法及应用 [J], 陈志恩;田彦山;马旭
因版权原因，仅展示原文概要，查看原文内容请购买。

一种增量式约简方法求解最小顶点覆盖问题
Zhan Shanhua;Xie Xiaojun
【期刊名称】《计算机应用研究》
【年(卷),期】2018(035)012
【摘要】最小顶点覆盖问题是一个应用很广泛的NP难题,针对该问题给出一种增量式属性约简方法.首先将最小顶点覆盖问题转换为一个决策表的最小属性约简问题;利用增量式属性约简思想,随着图中边数的增多,提出一种更新最小顶点覆盖的增量式属性约简算法;该算法时间复杂度低于计算整个图的最小顶点覆盖的时间复杂度,同时针对大规模图问题,可随着边的增加动态更新最小顶点覆盖,因此降低了属性约简的方法求解最小顶点覆盖问题的运行时间.实验结果表明了该算法的可行性和有效性.
【总页数】4页(P3685-3688)
【作者】Zhan Shanhua;Xie Xiaojun
【作者单位】
【正文语种】中文
【中图分类】TP391.6
【相关文献】
1.一种求解平面图的最小顶点覆盖算法 [J], 吴春;朱国魂;谢玉忠;林宏
2.一种混合化学反应优化算法求解最小顶点覆盖问题 [J], 郑光勇;徐雨明;李肯立;孙士兵
3.一种基于粗集理论的增量式属性约简算法 [J], 高晓红;李兴奇
4.不完备系统中一种增量式属性约简算法 [J], 王光琼
5.一种高效的复杂信息系统增量式属性约简 [J], 段海玲;王光琼
因版权原因，仅展示原文概要，查看原文内容请购买。

基于量子粒子群优化的最小属性约简算法
王加阳;谢颖
【期刊名称】《计算机工程》
【年(卷),期】2009(035)012
【摘要】属性约简是粗糙集理论中的一个核心问题,为了有效获取属性最小相对约简,提出一种基于量子粒子群优化算法的粗糙集属性约简算法.该算法通过引入自适应参数使得算法在保证取得的是一个约简的情况下尽可能地减少所包含的属性数目,并期望能够获得理想的约简结果.试验结果证明该算法能有效地进行属性约简,并取得良好的约简结果.
【总页数】4页(P148-150,153)
【作者】王加阳;谢颖
【作者单位】中南大学信息科学与工程学院,长沙,410083;中南大学信息科学与工程学院,长沙,410083
【正文语种】中文
【中图分类】TP301.6
【相关文献】
1.基于免疫量子粒子群优化的测试代价敏感属性约简算法 [J], 谢小军;俞春强;王博;何弦;徐章艳
2.基于遗传粒子群和粗糙集的最小属性约简算法 [J], 吴尚智;罗艺纯;翟敬鹏
3.基于量子粒子群优化算法的最小交叉熵多阈值图像分割 [J], 赵勇;方宗德;庞辉;王侃伟
4.基于0-1规划的最小属性约简算法 [J], 詹婉荣;于海
5.基于最小化邻域互信息的邻域熵属性约简算法 [J], 刘正;陈雪勤;张书锋
因版权原因，仅展示原文概要，查看原文内容请购买。

基于遗传粒子群和粗糙集的最小属性约简算法
吴尚智;罗艺纯;翟敬鹏
【期刊名称】《计算机工程与科学》
【年(卷),期】2016(38)5
【摘要】阐述了粗糙集理论、遗传约简算法和粒子群约简算法.属性约简是知识发现的关键问题之一.传统的属性约简算法都是串行搜索的,算法效率低且收敛速度慢.将计算智能和粗糙集相结合,提出了一种基于遗传粒子群和粗糙集的最小属性约简算法.该算法利用属性依赖度计算属性核,并在种群初始化时引入属性核作为限制条件,动态调整适应度函数,以达到求得最小属性约简的目的.实验表明,对于数据量大、属性维度高的属性约简问题,该算法具有高效的处理能力.
【总页数】7页(P1007-1013)
【作者】吴尚智;罗艺纯;翟敬鹏
【作者单位】西北师范大学计算机科学与工程学院,甘肃兰州 730070;中国移动通信集团甘肃有限公司,甘肃兰州 730070;西北师范大学计算机科学与工程学院,甘肃兰州 730070
【正文语种】中文
【中图分类】O159
【相关文献】
1.基于离散粒子群算法的粗糙集属性约简 [J], 李志豪
2.一种基于改进遗传算法的粗糙集属性约简算法磁 [J], 李玉龙;张亚光;毕聪聪
3.基于免疫遗传算法的粗糙集属性约简算法 [J], 时光;智军;陈军;
4.高斯核模糊粗糙集中基于粒子群算法的属性约简 [J], 刘东君;陈红梅
5.基于混沌离散粒子群的粗糙集属性约简算法 [J], 栾雨雨;王锡淮;肖健梅
因版权原因，仅展示原文概要，查看原文内容请购买。

一种改进的最小属性约简算法
薛胜军;郭强
【期刊名称】《武汉理工大学学报（交通科学与工程版）》
【年(卷),期】2012(036)003
【摘要】最小属性约简是粗糙集理论中的一个重要内容,通过对属性约简算法的研究,指出基于U/{a}划分的最小属性约简算法中的不足,并提出了一种改进的最小属性约简算法.该算法以基于等价类的方法对论域进行压缩,有效地降低了算法的空间复杂度,用基于核的方法求解最小约简,从而保证可获得最小约简.实验结果表明,该算法具有复杂性低、存储空间小和效率高的特点,是一种有效的最小属性约简算法.【总页数】4页(P515-518)
【作者】薛胜军;郭强
【作者单位】武汉理工大学计算机科学与技术学院武汉430063;南京信息工程大学计算机与软件学院南京210044;武汉理工大学计算机科学与技术学院武汉430063
【正文语种】中文
【中图分类】TP18
【相关文献】
1.基于改进关系积的最小属性约简算法 [J], 叶明全;伍长荣
2.最小相关性最大依赖度属性约简的改进算法 [J], 毛华;赵书峰
3.一种新的决策粗糙集最小化决策代价属性约简算法 [J], 徐道磊;陈培林;唐轶轩;
吴尚;路宇;卞显福
4.一种求粗糙集中最小属性约简的新算法 [J], 刘文军;王加银;冯艳宾;谷云东;李洪兴
5.一种有效的基于风险最小化的属性约简算法 [J], 于洪;姚园;赵军
因版权原因，仅展示原文概要，查看原文内容请购买。

一种增量式属性最小约简的粗糙集算法刘德银;刘文奇【摘要】当信息系统的对象和决策属性不变而不断增加条件属性时,为了获得该系统的最小约简属性,一般方法是对决策表的所有数据进行重新计算,很显然这种方法不可取.在粗糙集理论的基础上,给出了过渡相对差异比较表的定义,提出一种新的增加条件属性的最小约简算法.实例说明:该算法节省了大量的时间和空间的资源,并且结论与传统的算法得到的属性最小约简的结论是一致的,所以该算法具有一定的适用价值.%In order to obtain minimum attribute reduction of the information system when its condition attributes are added continually while its object and decision attributes are invariant, general method is to recalculate all the data in the decision table. Clearly it is not applicable. In this paper, the definition of transitive relative difference comparative tables is given based on rough set theory and a new minimum attributes reduction algorithm of condition attributes increment is proposed as well. From the specific examples, we can know that the algorithm saves a lot of time and space resources, and this conclusion accords with the condition of minimum attribute reduction obtained from traditional algorithm. Therefore, the new algorithm is of certain application value.【期刊名称】《计算机应用与软件》【年(卷),期】2011(028)008【总页数】3页(P257-259)【关键词】粗糙集;属性约简;过渡相对差异比较表【作者】刘德银;刘文奇【作者单位】昆明理工大学理学院,云南,昆明,650093;昆明理工大学理学院,云南,昆明,650093【正文语种】中文【中图分类】TP180 引言粗糙集理论是波兰华沙理工大学Z.Pawlak教授等一批科学家提出的，它是一种处理不确定信息的新型数学工具。

一种新颖的最小属性约简模型
杨明;倪魏伟;孙志挥
【期刊名称】《东南大学学报（自然科学版）》
【年(卷),期】2004(034)005
【摘要】传统的基于粗集的属性约简须计算差别矩阵并生成大量的条件属性类,效率低,且很多算法还不完备.为此,本文引入分类关联规则和相容分类关联规则的概念,给出基于分类关联规则的求解下近似和正区域的等价方法,从而提出基于分类关联规则的属性约简模型和算法,该模型将属性约简问题转化为求解一类特殊的分类关联规则集的问题,因而使得相应的算法可有效地改进属性约简挖掘效率, 克服传统算法依赖于主存的限制,为属性约简提供了一种新的框架.理论分析表明该算法是有效且可行的.
【总页数】5页(P604-608)
【作者】杨明;倪魏伟;孙志挥
【作者单位】安徽工程科技学院计算机科学与工程系,芜湖,241000;东南大学计算机科学与工程系,南京,210096;东南大学计算机科学与工程系,南京,210096;东南大学计算机科学与工程系,南京,210096
【正文语种】中文
【中图分类】TP311
【相关文献】
1.一种改进的最小属性约简算法 [J], 薛胜军;郭强
2.一种完备的最小属性约简方法 [J], 于海燕;乔晓东
3.一种新颖的概念格属性约简算法 [J], 李金海;吕跃进
4.一种新的决策粗糙集最小化决策代价属性约简算法 [J], 徐道磊;陈培林;唐轶轩;吴尚;路宇;卞显福
5.一种有效的基于风险最小化的属性约简算法 [J], 于洪;姚园;赵军
因版权原因，仅展示原文概要，查看原文内容请购买。

高可信度最小约简属性启发策略尹林子;李勇刚;阳春华;桂卫华【期刊名称】《自动化学报》【年(卷),期】2012(038)011【摘要】为提高启发式算法计算最小约简的可信度,基于可辨识矩阵,研究了属性之间存在的吸收、排斥以及互斥等特征,分析其与最小约简的关联,提出了对应的最小约简属性启发策略,建立了各个特征下属性启发策略的可信度计算模型.在此基础上,按照可信度排序,形成了一种综合的高可信度最小约简属性启发策略,并给出了具体的约简算法.理论和实验分析表明,本文策略具有可信度高且可信度可以估计等优点,能有效提升最小约简算法的性能.%In order to improve the confidence of minimal reducts calculated by heuristic methods, some important characters of attributes, such as absorption, repulsion, and mutex etc., are presented based on the discernibility matrix. Then the related heuristic strategies are proposed by analyzing the relation between these characters and the minimal reducts. Some confidence models of these strategies are established to order these strategies. On the basis, an integrated strategy and a related reduction algorithm are proposed to calculate a minimal redcut. Theoretic and experimental analyses show that the proposed strategies are of high confidence and effectiveness.【总页数】6页(P1751-1756)【作者】尹林子;李勇刚;阳春华;桂卫华【作者单位】中南大学信息科学与工程学院长沙410083;中南大学物理与电子学院长沙410083;中南大学信息科学与工程学院长沙410083;中南大学信息科学与工程学院长沙410083;中南大学信息科学与工程学院长沙410083【正文语种】中文【相关文献】1.基于联合属性重要度的决策风险最小化属性约简 [J], 徐菲菲;毕忠勤;雷景生2.变精度粗糙集的属性核和最小属性约简算法 [J], 陈昊;杨俊安;庄镇泉3.属性重要性的启发式属性约简算法 [J], 何英;何丹4.基于启发式二分策略的属性约简方法 [J], 黄治国; 杨清琳5.一种基于属性重要性的属性约简启发式算法 [J], 叶明全;胡学钢因版权原因，仅展示原文概要，查看原文内容请购买。