一种完备的最小属性约简方法
- 格式：pdf
- 大小：220.97 KB
- 文档页数：3
下载文档原格式
合集下载
基于量子云模型演化的最小属性约简增强算法
制属 性约 简空 间搜 索范 围 ， 并采 用量 子云 变异和 云 纠缠操 作 算 子较 好 地避 免 了在 属 性 演 化 约简 中易陷入 局部 最优和 早 熟收敛 等 问题 ， 使 算法 快速 搜 索到全 局 最 优属 性 约 简 集． 仿 真 实验 表 明，
提 出的最 小属 性约 简增 强算法具 有 收敛速度 快 、 约简 精度 高和稳 定性 强等优 点．
摘 要 ：为提 高决 策表 中最 小属 性约简 的效 率 、 稳定 性 和鲁 棒 性 ， 基 于云 模 型在 非 规 范知 识定 性 、
定 量 表 示及 其相 互 转换 过 程 中的优 良特 征 对量 子进 化算 法进 行 算 子设 计 ， 提 出 了一种 基 于量 子
云模 型演 化 的最 小属 性约 简增 强算法 （ ＱＣ ＭＥ ＡＲ Ｅ ） ． 该 算法 采 用量 子 基 因云 对进 化 种 群进 行 编 码， 基 于 约简属 性熵权 逆 向云进 行量 子旋 转 ｆ － ｊ 自适 应调 整 ， 使 其在 定 性知识指 导 下能够 自适 应控
ｗ ｅ ｉ ｇ ｈ ｔ ｉ ｓ ｄ ｅ ｓ ｉ ｇ ｎ ｅ ｄ ｔ ｏ ａ ｄ ａ ｐ ｉ ｔ ｖ ｅ ｌ ｙ ａ ｄ ｊ ｕ ｓ ｔ ｈｅ ｔ ｑ ｕ ａ ｎ ｔ ｕ ｍ ｒ ｅ ｖ ｏ ｌ ｖ ｉ ｎ ｇ ｇ ａ ｔ ｅ ， Ｓ Ｏ ｈｅ ｔ ｓ ｃ ｏ ｐ ｅ ｏ ｆ ｔ ｈ ｅ ｓ ｅ ａ ｒ ｃ ｈ ｓ ｐ ａ ｃ ｅ
第 ２期
丁卫 平 ， 等： 基 于量子 云模 型 演化 的最 小属性 约 简增 强算 法
２ ９ １
属 性 约 简 是 粗 糙 集 理 论 中 一 个 重 要 的 研 究 内容 ， 其 主 要任 务 是 在 保 证 知 识 库 分 类 和决 策
基于集合枚举树的最小属性约简算法
基于集合枚举树的最小属性约简算法蒋瑜【摘要】为了寻找一种有效的最小属性约简方法,给出了条件属性集上的属性重要度序关系,基于此序关系构建了属性集上的集合枚举树,提出了一种快速的最小属性约简算法,该算法采用至上而下、层次优先策略搜索集合枚举树寻找属性最小约简.为了提高算法性能,该算法采用核和父集剪枝策略减少搜索空间,采用优化计算来确保同一集合的正域只计算一次.基于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], 段海玲;王光琼
因版权原因，仅展示原文概要，查看原文内容请购买。
一种改进的最小属性约简算法
其 中一个 核属 性 ， 必会漏 选其 他 的核属性 ， 所得 的 结 果就 不是正 确 的 了． 另外 ， 文献 ［ ］ ４ 中的 方法 是 对 整个 论域元 素 依 次 进行 计 算 ， 就 会 出现 重 复 这 计 算 的现象 ， 增加 了算 法 的复杂 度 ， 降低 了效率 ．
定 义 ６ 如果 有 相 同条 件属 性 的数 据 同时 其 决 策属性 的 值 也 相 等 ， 称 该 决 策表 为相 容 决 策 则
定 义 １ 设 Ｓ一 （ Ｒ， ， ， 于 每 个 属 性 Ｕ， Ｆ） 对
基于 正区域 的求解 算法 ， 时在求解 的过程 中会 结 有 合属性 的重要性 、 信息等 ；２ 基于 差别矩 阵 的求 互 （）
解算法 ；３ （ ）基 于智 能 计算 的求 解 方法 ， 基 于 遗 如 传算法 和神经 网络 ． 着 问题 规模 的增 大 ， 于 差 随 基 别矩 阵求 解算法 的缺陷会愈 加凸显． 有时在 利用 正 区域或差别 矩 阵求解 时 ， 结合 属 性 的重 要性 、 常 Ｊ
第 ３ ６卷 第 ３期 ２１ ０ ２年 ６月
武 汉理 工大 学学 报 （ 交通 科学 与工 程版 ）
Ｊ ｕ ｎ ｌｏ ｕ ａ ｉ ｅ ｓｔ ｆＴｅ ｈ ｏ ｏ ｙ ｏ ｒ ａ ｆＷ ｈ ｎ Ｕｎ ｖ ｒ ｉｙ ｏ ｃ ｎ ｌ ｇ
（ ａ ｓ ｏ ｔｔ ｎＳ ｉｎ ｅ＆ Ｅｎ ｉｅ ｒ ｇ Ｔｒ ｎ ｐ ｒａｉ ｃｅ ｃ ｏ ｇｎ ｅｉ ） ｎ
子 集 Ｐ Ｒ， 义 属 性 Ｐ 的 不 可 区 分 关 系 定
Ｉ ＮＤ（ 一｛ ． ） Ｐ） （ ， ∈Ｕ。 Ｖｒ ２ ２ ｛ ∈Ｐ， （ ｒ 一ｆ（ 厂 ，） Ｙ，
ｒ ）如 果 （ ） Ｉ ）， ｚ， ∈ ＮＤ（ ， 称 ｚ 与 ． 是 Ｐ 不 Ｐ） 则 ｙ
定 义 ６ 如果 有 相 同条 件属 性 的数 据 同时 其 决 策属性 的 值 也 相 等 ， 称 该 决 策表 为相 容 决 策 则
定 义 １ 设 Ｓ一 （ Ｒ， ， ， 于 每 个 属 性 Ｕ， Ｆ） 对
基于 正区域 的求解 算法 ， 时在求解 的过程 中会 结 有 合属性 的重要性 、 信息等 ；２ 基于 差别矩 阵 的求 互 （）
解算法 ；３ （ ）基 于智 能 计算 的求 解 方法 ， 基 于 遗 如 传算法 和神经 网络 ． 着 问题 规模 的增 大 ， 于 差 随 基 别矩 阵求 解算法 的缺陷会愈 加凸显． 有时在 利用 正 区域或差别 矩 阵求解 时 ， 结合 属 性 的重 要性 、 常 Ｊ
第 ３ ６卷 第 ３期 ２１ ０ ２年 ６月
武 汉理 工大 学学 报 （ 交通 科学 与工 程版 ）
Ｊ ｕ ｎ ｌｏ ｕ ａ ｉ ｅ ｓｔ ｆＴｅ ｈ ｏ ｏ ｙ ｏ ｒ ａ ｆＷ ｈ ｎ Ｕｎ ｖ ｒ ｉｙ ｏ ｃ ｎ ｌ ｇ
（ ａ ｓ ｏ ｔｔ ｎＳ ｉｎ ｅ＆ Ｅｎ ｉｅ ｒ ｇ Ｔｒ ｎ ｐ ｒａｉ ｃｅ ｃ ｏ ｇｎ ｅｉ ） ｎ
子 集 Ｐ Ｒ， 义 属 性 Ｐ 的 不 可 区 分 关 系 定
Ｉ ＮＤ（ 一｛ ． ） Ｐ） （ ， ∈Ｕ。 Ｖｒ ２ ２ ｛ ∈Ｐ， （ ｒ 一ｆ（ 厂 ，） Ｙ，
ｒ ）如 果 （ ） Ｉ ）， ｚ， ∈ ＮＤ（ ， 称 ｚ 与 ． 是 Ｐ 不 Ｐ） 则 ｙ
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
ｒｄ ｃｉｎ ｅｕ ｔ ｏ
Ｄｏｈ １．９ ９ ．ｓ ０ ０３ ２ ． １ ． ．１ Ｏ３ ６ ／ｉ ｎ１０ —４ ８ Ｏ ２ ４０ ５ ｊｓ ２ ０
１ 概 述
粗糙集理论是一种新型的处理模 糊和 不确 定知识 的数学
。
工具 ，属性约简是它的核心内容 之一 ，目前国内外 已经提 出
了许多属性约简方法。 基于差别矩 阵 的属性约简是属性约简 的方法之一 ，该
ｒｄ ｃｉｎｔ ｅｉｇ ｎｒｔ ａｅ ｎｔｅｐｏ ａ ｉｔ ｆｈ ｔｉｕｅ ｉ ｉ ｅｎｔ ｂｅｔ． ｌ ｎｍａ ｔｉｕｅｒｄ ｃｉｎ ｒ ｇ ｔｒｍ ｍｉｉ ｌ ｅ ｕｔ ｅ ｅ ｅａｅ ｂ ｓｄｏ ｒｂ ｂｌｙｏ ｅａｔｂ ｔｓ ｃ ｄｓ ｒ ｏｊｃｓＡｌｍｉｉ ｌ ｔｂ ｔ ｅ ｕ ｔ ｓ ｅ ｏ ｏ ｎｍａ ｏ ｒ ｓ ｄ ｈ ｉ ｔ ｒ ｗｈ ｈ ｃ ｗｏ ａｒ ｏ ａ ｆ
的，也就是说这 ２ 种属性约简是不等价的 ，文献 ［】 ８进一步研
究指 出产 生这个 问题 的根本原 因：由于决策表 信息系统的不 相容 性导致 了 Ｈ 的方法出错 ，因此对于一致决策表基于差 ｕ 别矩阵的属性约筒与基于正 区域的属性 约简是等价 的。 对一 个信 息系统 ，一般而言求 出所有约简与求最小约筒 都是 Ｎ Ｐ难 问题 ，因此 ，常借助于某种启 发式信息来求近优 解 ，但很多方法都 是不完备 的。本文根据差别矩阵 的求核原
ａｔ ｉ ｕ ｅ ｅ ｕ ｔｏ ｒ ｅ Ｔ ｅ ｒ ｓ ｌ ｆｔ ｅｍｅ ｈ ｄ ｉ ｏ ｅ ｏ ｂ ｏ ｔｒｂ ｔ ｓｒ ｄ ｃ ｉ ｎ ｔｅ ． ｈ ｅ ｕ ｔ ｔ ｏ ｓ ｏ ｈ ｐｒ ｖ ｄ ｔ ｅｃ ｍｐ ｅｅ ａ ｄ ｍｉ ｉ ｌ ｌ ｔ ｎ ｎ ｍａ
第３ ８卷 第 ４期
Ｖ０ ＿８ １３
・
计
算
机
工
程
２１ ０ ２年 ２月
Ｆｅ ｕａ ｙ ０１ ｂｒ ｒ ２ ２
ＮＯ４ ．
Ｃｏ ｐ ｔ ｒＥｎ ｉ ｅ ｒｎ ｍ ｕｅ ｇｎ ｅｉｇ
软 件 技术 与数 据库 ・
一
文章编号：１ ０－２（ １）— ０６＿ 文献标识码： ０ —３ ８ ０２４ ４—０ ０ ４ ２ ０ ３ Ａ
决策属性集 。对于 每个属性 ａ Ｒ， 为 它的值域 。每个属
性有一个决策函数 ｆ： Ｒ＿ 。 Ｕｘ ÷
约简。
定义 ２把 一个给定 的决策表 的属性 区分 的信 息用一个 差别 向量组来表示 ，即 Ｅ ＝（ 日 Ｅ …， ）， 的任一项 Ｅ ， ， Ｅ 它 元素 Ｅ ＝（ｉ Ｏ， ， １ ， ｎ ， Ｇ ）（ ， …，） 其中 ， ２ ０为可 区分对象对 ；
定义 ３在一个决策表 Ｓ＝ Ｕ， ，， ＜ ＲＶ ｆ＞中， Ｒ＝ ＣｕＤ ， 设 Ｍ ＝（ 为差别矩阵 ，Ｖ ｍ） ＰｃＣ，若 Ｐ满足 ：
（） ≠ｍ ∈Ｍ ，有 Ｐ ， ； １Ｖ ｎｍ， ≠
（） ａ ２ Ｖ ∈Ｐ， Ｐ ＝Ｐ一 Ⅱ 均 不 满 足（） ｛｝ １。
方法将信息系统中所有有关属性 的区分信 息都浓缩进一个矩
阵中， 目前很 多属性约简算法都是基于区分矩阵或在 此基础 上进行改进 的 。文献［】 ７指出 由 Ｈ ｕ提 出的基于差别矩阵的 求核 方法 求 出的核与基 于正 区域 的属 性约 简的核 是不等价
则称 Ｐ是 Ｃ关于 Ｄ 的一个属性约简。
定理 在一个概 率向量中 ， 如果其 中的某一项元素取值为 １ ，则该元素所对应 的属性为原信息表 的核属性 。
［ ｓｒｃ］Ａｔ ｂ ｔｒｄ ｃｉｎｉ ｔｅｂｓｃ ｒｂｅ ｏ ｕ ｈｓｔｔｅｒ． ｔｏ ｒ ｎｍａ ａｔｂ ｔｓ ｅｕ ｔ ｎｉ ｃ ｎｉｅ ｔ ｅ ｉｏ ｂｅｉ Ａｂｔａ ｔ ｔｉｕｅ ｅ ｕｔ ｓｈ ａｉ ｏ ｌｍ ｆ ｏ ｇ ｓ ｈｏｙ Ａｍｅ ｄｆ ｉ ｌｔ ｉｕｅ ｄ ｃｉ ｏ ｓ ｔｎ ｃｓ ｎｔ ｌ ｒ ｏ ｐ ｒ ｅ ｈ ｏ ｍｉ ｒ ｒ ｏ ｎ ｓ ｄ ｉ ａ ｓ
向量组 ，计算每个属性在 区分 ２ 个对象 的属性集合 中出现 的概率 ，作为属性重要性 的启发式信息 ，建立最小属性约简树 ，得到属性约筒 。
分析结果表 明，该方法可 以获得 所有 的最小属性约筒 。 关健词 ：粗糙集 ；决策表 ；差 别属性集 ；差 别向量组 ；最小属性 约简树 ；最小属性约 筒
２ 相关概念
定义 １决策表定义为 Ｓ＝ ＲＶ ｆ＞， Ｒ＝ＣｕＤ为属 ＜Ｕ，， ，
性集合 ，其中 ，Ｕ是对 象的有限集 ；Ｃ是条件属性集 ；Ｄ是
所 以，一个属性约筒即能将 所有对象 区分开 的属性 的集合 ，
一
个最小属性约简即能将对象 区分 开的属性个数最少 的属性
本文讨论的方法是根据差 别矩 阵的求核原理 ，所 以，只
第３ 卷 ８
第 ４期
于海燕 ，乔晓东 ：一种 完备 的最 小属 性约简方法
４ ７
１０ ０ ％地 覆盖整个 训练集 ，且对象之 间都能 区分开 。
（） ， １Ｃ 只能将 Ｃ对应 的对 象区分，则新属性集合为一个约 ｉ 简 ，且 属 性个 数 与 ｛ Ｃ ｝ 等 ，原 约 简为 最 小属 性 Ｃ ｃ， ｎ 相 ， …， 约简。 （） ， ２ Ｃ 不能将 Ｃ对应 的对象 区分 ， ｉ 则新属性集合不是一个
约简 ，需要另外选择属性 区分 ，这 时属性约简 中的属性个 数大于约 筒 ｛ Ｃ ｝ ｃ ｃ， 中的属性 个数 ，所 以原属性 约简仍 ， …，
为最小 属性 约简。
根据这个思路 ，首先将核属性加入约简 ，将包含核属性 的元素删除 ，在剩余 的元素 中继续寻找能 区分其余对象 的属 性 。在 剩余的元素 中，每个元素包含 的属性 中至少要有一个
证 明： 令概率 向量 中的任意一项 ｆａ） ，， ，， ｍ， （ ＝１ ＝Ｉ …， ２
因 为 Ｆ ＝（ （ ，（： …， （，） ｆａ） ｌｌ ，，所 以 Ｉ ， ）ｆａ） ． ａ ） ， （，＝ ／Ｃ ｌ ． ， ｆ Ｃｌ ＝ １ 也 就 是 在 相 应 的 区 分 对 象 的差 别 属 性 集 只 有 该 概 率 向 量 ，
［ ｙｗｏ ｄ ｒｕ ｈｓｔ ｄ ｃｓ ｎｔｂｅ ｄｓｅｎｂｅａｔｂ ｔ ｓｔ ｉ ｅｎｂｅ ｖｃｏ ｒ ｙ ｍｉｉ ｌ ｔｉｕｅｒｄ ｃｉｎｔ ｅ ｍｉｉ ｌ ｔｉｕｅ Ｋｅ ｒ ｓ ｏ ｇ ｅ； ｅｉｉ ａｌ； ｉ ｒｉｌ ｔ ｉｕｅ ｅ；ｄｓ ｒｉｌ ｅ ｔｒａｒ ； ｎｍａ ａｔｂ ｔ ｅ ｕｔ ｒ ； ｎｍａ ａｔｂ ｔ Ｉ ｏ ｃ ｒ ｃ ａ ｒ ｏ ｅ ｒ
属性来区分其对应 的 ２个对 象 ，即属 性约简中至少 要包含其 中的一个属性 ，属性个数越少 ，被选 中的概率越大 ，以此概
（） ３ Ｃ不仅能 区分 Ｃ，且能 区分其他对象 ，设被 区分 的对 ，
象对 为 Ｏ ，则 Ｃ 必属于能将 区分开 的属性子 集 ，且 Ｃ 在 ｋ ， ， 这里的对应概率为 Ｐ ，即 Ｐ ＝Ｐ ，因为 Ｐ ≥Ｐ ≥Ｐ ， ， ，对于 概 率大于 等于 Ｐ 的属性 都在 最小属性 约简树 中处理过 ， 所以 不属于新 的约简情况 。
织 ，数据挖掘 ，粒 度计算；乔晓东，研究员、硕士
量 ，Ｆ＝（ （． ．ａ） ｆ ａ ） ，它的每一项表示该属性出现 ， “）ｆ ， （ ） ， （ …，
的概率 ， ｍ为属性个数 ，令 ／ ，， ｍ： ＝１ …， ２
收稿 日 ：２ １ ０—６ 期 ０１ ８２ —
Ｅｍａ ：ｙｈ ａ６ ＠１３ ｏ ・ ｉ ｕｙｎቤተ መጻሕፍቲ ባይዱ ６ ． ｍ ｌ ｃ
中图分类号：Ｔ３１２ Ｐ１１ ．
种 完备 的 最 小属 性 约 简 方 法
于海燕 ，乔 晓东
（ 中国科 学技术信 息研究所信息技 术支持 中心，北京 １０ ３） ００ ８
摘
要 ：为解决粗糙集 中的属性 约简问题 ， 出一种 完备 的最小属性约简 方法 。将差别矩阵中所有有关属性 区分的信息都浓缩进一个差别 提
率作为属性的重要性 ，每个属性被选 中的概率为该元素包含 的属 性个数分之一 ，选择重要性大 的属性加入约简 ，然后删 除包含该属性的元素 ，重复这个过程 ，直到所有对象都被 区
分开 。
综上所述 ，该方法得到的属性 约简是属性个数最少的 ，
即为最 小属性约筒 。 ４２ 完备性证 明 ． 证明： 根据 Ｐ ｗｌ ａ ａ ｋ的定义 ，若属性集 Ｐ亡Ｃ是给定决策
在差别矩 阵中， 属性组合数为 １的元素表 明除该属性外 ， 其余条件属性无法将该元素对应 ２条 决策属性 不同的对 象区
分开 ，即该属性必须保 留，与决策表 中核属性 的概念一致 ， 所以 ，矩阵中所有属性组合 数为 １的属性 均为决策 表的核属 性 ，所有包含核属性 的元素所对应 的对象都可 以由核属性 与 其他对象 区分开 。
Ｃｏ ｐ ｅ ｅＭ ｉ ｉ ａ ｔ ｉ ｕ ｅＲｅ ｕ ｔｏ ｅ ｈ ｄ ｍ ｌ ｔ ｎ ｍ ｌ Ａｔｒ ｂ ｔ ｄ ｃ ｉ ｎ Ｍ ｔ ｏ
ＹＵ Ｈ ｉ ａ ． ＡＯ ａ － ｏ ｇ ａ － ｎ ＱＩ Ｘｉｏｄ ｎ ｙ
（ｎｏｍａｉｎＴ ｃｎ ｌｇ ｕ ｐ ｒＣ ｎｅ，ｎｔｕｅｏ ｃｅｔ ｉａ ｄＴ ｃ ｎ ａ Ｉｆｒ ｔ ｎｏ ｈｎ ， ｅ ｉｇ１０ ３ ， ｉａ Ｉｆｒ ｔ ｅｈ ｏｏ ｙＳ ｐ ｏｔ ｅ ｔ Ｉｓｔｔ ｆ ｉｎｉｃ ｎ ｅｈ ｉ ｌｎｏｍａｉ ｆ ｉａ Ｂ ｉｎ ０ ０ ８ Ｃｈｎ ） ｏ ｒ ｉ Ｓ ｆ ｃ ｏ Ｃ ｊ
最小 属性约简 ，并证明该方法是完备 的，且用该方法能得到 所有最小属性约简 。
（） ２对任意 的 ∈Ｐ， Ｐ Ｓ－ ｝ ≠Ｐ Ｓ （ 。 Ｏ ｅ ａＤ） Ｏ Ｄ） ｌ（ 如果一 个属性 约简 算法求得 的属性 集 同时满足条 件（） １
最小属性约简算法的具体步骤如下 ： 输入 训练数据
ｐ ｏ ｏｓ ｄ ｉ ｈ ｓ ｐ ｐ ｒ ｒ ｐ ｅ ｎ ｔ ｉ ａ ｅ Ｔｈ ｉｃ ｒ ｉ ｌ ｎ ｏ ｍａ ｉ ｎ ｉ ｏ ｉｔ ｎ ｅ ｉ ｉ ｎ ｔ ｂ ｅ ｓ ｄ ｓ ｒｂ ｄ ｗｉ ｉｃ ｒ ｉ ｌ ｅ ｔ ｒ ａ ｒ ｙ ｅ ｄ ｓ ｅ ｎ ｂ ｅ ｉ ｆ ｒ ｔ ｎ ｃ ｎｓｓｅ ｔｄ ｃ ｓ ｏ ａ ｌ ｓ ｉ ｅ ｃ ｉ ｅ ｔ ｄ ｓ ｅ ｎ ｂ ｅ ｖ ｃ ｏ ｒａ ．Ａ ｎｉ ｌａ ｔｉ ｕ ｅ ｏ ｈ ｍｉ ｍａ ｔｒｂ ｔ
Ｄｏｈ １．９ ９ ．ｓ ０ ０３ ２ ． １ ． ．１ Ｏ３ ６ ／ｉ ｎ１０ —４ ８ Ｏ ２ ４０ ５ ｊｓ ２ ０
１ 概 述
粗糙集理论是一种新型的处理模 糊和 不确 定知识 的数学
。
工具 ，属性约简是它的核心内容 之一 ，目前国内外 已经提 出
了许多属性约简方法。 基于差别矩 阵 的属性约简是属性约简 的方法之一 ，该
ｒｄ ｃｉｎｔ ｅｉｇ ｎｒｔ ａｅ ｎｔｅｐｏ ａ ｉｔ ｆｈ ｔｉｕｅ ｉ ｉ ｅｎｔ ｂｅｔ． ｌ ｎｍａ ｔｉｕｅｒｄ ｃｉｎ ｒ ｇ ｔｒｍ ｍｉｉ ｌ ｅ ｕｔ ｅ ｅ ｅａｅ ｂ ｓｄｏ ｒｂ ｂｌｙｏ ｅａｔｂ ｔｓ ｃ ｄｓ ｒ ｏｊｃｓＡｌｍｉｉ ｌ ｔｂ ｔ ｅ ｕ ｔ ｓ ｅ ｏ ｏ ｎｍａ ｏ ｒ ｓ ｄ ｈ ｉ ｔ ｒ ｗｈ ｈ ｃ ｗｏ ａｒ ｏ ａ ｆ
的，也就是说这 ２ 种属性约简是不等价的 ，文献 ［】 ８进一步研
究指 出产 生这个 问题 的根本原 因：由于决策表 信息系统的不 相容 性导致 了 Ｈ 的方法出错 ，因此对于一致决策表基于差 ｕ 别矩阵的属性约筒与基于正 区域的属性 约简是等价 的。 对一 个信 息系统 ，一般而言求 出所有约简与求最小约筒 都是 Ｎ Ｐ难 问题 ，因此 ，常借助于某种启 发式信息来求近优 解 ，但很多方法都 是不完备 的。本文根据差别矩阵 的求核原
ａｔ ｉ ｕ ｅ ｅ ｕ ｔｏ ｒ ｅ Ｔ ｅ ｒ ｓ ｌ ｆｔ ｅｍｅ ｈ ｄ ｉ ｏ ｅ ｏ ｂ ｏ ｔｒｂ ｔ ｓｒ ｄ ｃ ｉ ｎ ｔｅ ． ｈ ｅ ｕ ｔ ｔ ｏ ｓ ｏ ｈ ｐｒ ｖ ｄ ｔ ｅｃ ｍｐ ｅｅ ａ ｄ ｍｉ ｉ ｌ ｌ ｔ ｎ ｎ ｍａ
第３ ８卷 第 ４期
Ｖ０ ＿８ １３
・
计
算
机
工
程
２１ ０ ２年 ２月
Ｆｅ ｕａ ｙ ０１ ｂｒ ｒ ２ ２
ＮＯ４ ．
Ｃｏ ｐ ｔ ｒＥｎ ｉ ｅ ｒｎ ｍ ｕｅ ｇｎ ｅｉｇ
软 件 技术 与数 据库 ・
一
文章编号：１ ０－２（ １）— ０６＿ 文献标识码： ０ —３ ８ ０２４ ４—０ ０ ４ ２ ０ ３ Ａ
决策属性集 。对于 每个属性 ａ Ｒ， 为 它的值域 。每个属
性有一个决策函数 ｆ： Ｒ＿ 。 Ｕｘ ÷
约简。
定义 ２把 一个给定 的决策表 的属性 区分 的信 息用一个 差别 向量组来表示 ，即 Ｅ ＝（ 日 Ｅ …， ）， 的任一项 Ｅ ， ， Ｅ 它 元素 Ｅ ＝（ｉ Ｏ， ， １ ， ｎ ， Ｇ ）（ ， …，） 其中 ， ２ ０为可 区分对象对 ；
定义 ３在一个决策表 Ｓ＝ Ｕ， ，， ＜ ＲＶ ｆ＞中， Ｒ＝ ＣｕＤ ， 设 Ｍ ＝（ 为差别矩阵 ，Ｖ ｍ） ＰｃＣ，若 Ｐ满足 ：
（） ≠ｍ ∈Ｍ ，有 Ｐ ， ； １Ｖ ｎｍ， ≠
（） ａ ２ Ｖ ∈Ｐ， Ｐ ＝Ｐ一 Ⅱ 均 不 满 足（） ｛｝ １。
方法将信息系统中所有有关属性 的区分信 息都浓缩进一个矩
阵中， 目前很 多属性约简算法都是基于区分矩阵或在 此基础 上进行改进 的 。文献［】 ７指出 由 Ｈ ｕ提 出的基于差别矩阵的 求核 方法 求 出的核与基 于正 区域 的属 性约 简的核 是不等价
则称 Ｐ是 Ｃ关于 Ｄ 的一个属性约简。
定理 在一个概 率向量中 ， 如果其 中的某一项元素取值为 １ ，则该元素所对应 的属性为原信息表 的核属性 。
［ ｓｒｃ］Ａｔ ｂ ｔｒｄ ｃｉｎｉ ｔｅｂｓｃ ｒｂｅ ｏ ｕ ｈｓｔｔｅｒ． ｔｏ ｒ ｎｍａ ａｔｂ ｔｓ ｅｕ ｔ ｎｉ ｃ ｎｉｅ ｔ ｅ ｉｏ ｂｅｉ Ａｂｔａ ｔ ｔｉｕｅ ｅ ｕｔ ｓｈ ａｉ ｏ ｌｍ ｆ ｏ ｇ ｓ ｈｏｙ Ａｍｅ ｄｆ ｉ ｌｔ ｉｕｅ ｄ ｃｉ ｏ ｓ ｔｎ ｃｓ ｎｔ ｌ ｒ ｏ ｐ ｒ ｅ ｈ ｏ ｍｉ ｒ ｒ ｏ ｎ ｓ ｄ ｉ ａ ｓ
向量组 ，计算每个属性在 区分 ２ 个对象 的属性集合 中出现 的概率 ，作为属性重要性 的启发式信息 ，建立最小属性约简树 ，得到属性约筒 。
分析结果表 明，该方法可 以获得 所有 的最小属性约筒 。 关健词 ：粗糙集 ；决策表 ；差 别属性集 ；差 别向量组 ；最小属性 约简树 ；最小属性约 筒
２ 相关概念
定义 １决策表定义为 Ｓ＝ ＲＶ ｆ＞， Ｒ＝ＣｕＤ为属 ＜Ｕ，， ，
性集合 ，其中 ，Ｕ是对 象的有限集 ；Ｃ是条件属性集 ；Ｄ是
所 以，一个属性约筒即能将 所有对象 区分开 的属性 的集合 ，
一
个最小属性约简即能将对象 区分 开的属性个数最少 的属性
本文讨论的方法是根据差 别矩 阵的求核原理 ，所 以，只
第３ 卷 ８
第 ４期
于海燕 ，乔晓东 ：一种 完备 的最 小属 性约简方法
４ ７
１０ ０ ％地 覆盖整个 训练集 ，且对象之 间都能 区分开 。
（） ， １Ｃ 只能将 Ｃ对应 的对 象区分，则新属性集合为一个约 ｉ 简 ，且 属 性个 数 与 ｛ Ｃ ｝ 等 ，原 约 简为 最 小属 性 Ｃ ｃ， ｎ 相 ， …， 约简。 （） ， ２ Ｃ 不能将 Ｃ对应 的对象 区分 ， ｉ 则新属性集合不是一个
约简 ，需要另外选择属性 区分 ，这 时属性约简 中的属性个 数大于约 筒 ｛ Ｃ ｝ ｃ ｃ， 中的属性 个数 ，所 以原属性 约简仍 ， …，
为最小 属性 约简。
根据这个思路 ，首先将核属性加入约简 ，将包含核属性 的元素删除 ，在剩余 的元素 中继续寻找能 区分其余对象 的属 性 。在 剩余的元素 中，每个元素包含 的属性 中至少要有一个
证 明： 令概率 向量 中的任意一项 ｆａ） ，， ，， ｍ， （ ＝１ ＝Ｉ …， ２
因 为 Ｆ ＝（ （ ，（： …， （，） ｆａ） ｌｌ ，，所 以 Ｉ ， ）ｆａ） ． ａ ） ， （，＝ ／Ｃ ｌ ． ， ｆ Ｃｌ ＝ １ 也 就 是 在 相 应 的 区 分 对 象 的差 别 属 性 集 只 有 该 概 率 向 量 ，
［ ｙｗｏ ｄ ｒｕ ｈｓｔ ｄ ｃｓ ｎｔｂｅ ｄｓｅｎｂｅａｔｂ ｔ ｓｔ ｉ ｅｎｂｅ ｖｃｏ ｒ ｙ ｍｉｉ ｌ ｔｉｕｅｒｄ ｃｉｎｔ ｅ ｍｉｉ ｌ ｔｉｕｅ Ｋｅ ｒ ｓ ｏ ｇ ｅ； ｅｉｉ ａｌ； ｉ ｒｉｌ ｔ ｉｕｅ ｅ；ｄｓ ｒｉｌ ｅ ｔｒａｒ ； ｎｍａ ａｔｂ ｔ ｅ ｕｔ ｒ ； ｎｍａ ａｔｂ ｔ Ｉ ｏ ｃ ｒ ｃ ａ ｒ ｏ ｅ ｒ
属性来区分其对应 的 ２个对 象 ，即属 性约简中至少 要包含其 中的一个属性 ，属性个数越少 ，被选 中的概率越大 ，以此概
（） ３ Ｃ不仅能 区分 Ｃ，且能 区分其他对象 ，设被 区分 的对 ，
象对 为 Ｏ ，则 Ｃ 必属于能将 区分开 的属性子 集 ，且 Ｃ 在 ｋ ， ， 这里的对应概率为 Ｐ ，即 Ｐ ＝Ｐ ，因为 Ｐ ≥Ｐ ≥Ｐ ， ， ，对于 概 率大于 等于 Ｐ 的属性 都在 最小属性 约简树 中处理过 ， 所以 不属于新 的约简情况 。
织 ，数据挖掘 ，粒 度计算；乔晓东，研究员、硕士
量 ，Ｆ＝（ （． ．ａ） ｆ ａ ） ，它的每一项表示该属性出现 ， “）ｆ ， （ ） ， （ …，
的概率 ， ｍ为属性个数 ，令 ／ ，， ｍ： ＝１ …， ２
收稿 日 ：２ １ ０—６ 期 ０１ ８２ —
Ｅｍａ ：ｙｈ ａ６ ＠１３ ｏ ・ ｉ ｕｙｎቤተ መጻሕፍቲ ባይዱ ６ ． ｍ ｌ ｃ
中图分类号：Ｔ３１２ Ｐ１１ ．
种 完备 的 最 小属 性 约 简 方 法
于海燕 ，乔 晓东
（ 中国科 学技术信 息研究所信息技 术支持 中心，北京 １０ ３） ００ ８
摘
要 ：为解决粗糙集 中的属性 约简问题 ， 出一种 完备 的最小属性约简 方法 。将差别矩阵中所有有关属性 区分的信息都浓缩进一个差别 提
率作为属性的重要性 ，每个属性被选 中的概率为该元素包含 的属 性个数分之一 ，选择重要性大 的属性加入约简 ，然后删 除包含该属性的元素 ，重复这个过程 ，直到所有对象都被 区
分开 。
综上所述 ，该方法得到的属性 约简是属性个数最少的 ，
即为最 小属性约筒 。 ４２ 完备性证 明 ． 证明： 根据 Ｐ ｗｌ ａ ａ ｋ的定义 ，若属性集 Ｐ亡Ｃ是给定决策
在差别矩 阵中， 属性组合数为 １的元素表 明除该属性外 ， 其余条件属性无法将该元素对应 ２条 决策属性 不同的对 象区
分开 ，即该属性必须保 留，与决策表 中核属性 的概念一致 ， 所以 ，矩阵中所有属性组合 数为 １的属性 均为决策 表的核属 性 ，所有包含核属性 的元素所对应 的对象都可 以由核属性 与 其他对象 区分开 。
Ｃｏ ｐ ｅ ｅＭ ｉ ｉ ａ ｔ ｉ ｕ ｅＲｅ ｕ ｔｏ ｅ ｈ ｄ ｍ ｌ ｔ ｎ ｍ ｌ Ａｔｒ ｂ ｔ ｄ ｃ ｉ ｎ Ｍ ｔ ｏ
ＹＵ Ｈ ｉ ａ ． ＡＯ ａ － ｏ ｇ ａ － ｎ ＱＩ Ｘｉｏｄ ｎ ｙ
（ｎｏｍａｉｎＴ ｃｎ ｌｇ ｕ ｐ ｒＣ ｎｅ，ｎｔｕｅｏ ｃｅｔ ｉａ ｄＴ ｃ ｎ ａ Ｉｆｒ ｔ ｎｏ ｈｎ ， ｅ ｉｇ１０ ３ ， ｉａ Ｉｆｒ ｔ ｅｈ ｏｏ ｙＳ ｐ ｏｔ ｅ ｔ Ｉｓｔｔ ｆ ｉｎｉｃ ｎ ｅｈ ｉ ｌｎｏｍａｉ ｆ ｉａ Ｂ ｉｎ ０ ０ ８ Ｃｈｎ ） ｏ ｒ ｉ Ｓ ｆ ｃ ｏ Ｃ ｊ
最小 属性约简 ，并证明该方法是完备 的，且用该方法能得到 所有最小属性约简 。
（） ２对任意 的 ∈Ｐ， Ｐ Ｓ－ ｝ ≠Ｐ Ｓ （ 。 Ｏ ｅ ａＤ） Ｏ Ｄ） ｌ（ 如果一 个属性 约简 算法求得 的属性 集 同时满足条 件（） １
最小属性约简算法的具体步骤如下 ： 输入 训练数据
ｐ ｏ ｏｓ ｄ ｉ ｈ ｓ ｐ ｐ ｒ ｒ ｐ ｅ ｎ ｔ ｉ ａ ｅ Ｔｈ ｉｃ ｒ ｉ ｌ ｎ ｏ ｍａ ｉ ｎ ｉ ｏ ｉｔ ｎ ｅ ｉ ｉ ｎ ｔ ｂ ｅ ｓ ｄ ｓ ｒｂ ｄ ｗｉ ｉｃ ｒ ｉ ｌ ｅ ｔ ｒ ａ ｒ ｙ ｅ ｄ ｓ ｅ ｎ ｂ ｅ ｉ ｆ ｒ ｔ ｎ ｃ ｎｓｓｅ ｔｄ ｃ ｓ ｏ ａ ｌ ｓ ｉ ｅ ｃ ｉ ｅ ｔ ｄ ｓ ｅ ｎ ｂ ｅ ｖ ｃ ｏ ｒａ ．Ａ ｎｉ ｌａ ｔｉ ｕ ｅ ｏ ｈ ｍｉ ｍａ ｔｒｂ ｔ