基于容差计算的非完备信息系统属性约简算法
- 格式：pdf
- 大小：994.87 KB
- 文档页数：6
下载文档原格式
合集下载
基于包含度的不完备序信息系统属性约简的一种算法
基于包含度的不完备序信息系统属性约简的一种算法郭永平【期刊名称】《佳木斯大学学报（自然科学版）》【年(卷),期】2012(030)002【摘要】In this paper,by introducing the concept of inclusion degree to incomplete ordered information system,the significance of attribute was defined.Then,an inclusion degree-based algorithm for attribute reduction under incomplete ordered information system was proposed.The experimental results show that this algorithm can find the reduction of an incomplete ordered information system.%在不完备序信息系统中,通过引入包含度的概念,对属性重要度进行了定义;在此基础上,提出了一种基于包含度的属性约简算法;最后,通过实例分析表明,该算法能得到不完备序信息系统的一个约简.【总页数】4页(P270-272,277)【作者】郭永平【作者单位】中国人民银行嘉峪关市中心支行,甘肃嘉峪关735100【正文语种】中文【中图分类】O159【相关文献】1.一种不完备模糊目标信息系统的精度属性约简算法 [J], 于晓辉;张强2.一种基于知识粒度的不完备信息系统的属性约简算法 [J], 李秀红;史开泉3.基于全序优势关系的不完备模糊信息系统及其属性约简 [J], 曾雪兰;孙兴星;于莹莹4.不完备信息系统下基于分辨度的属性约简算法 [J], 李长清;张燕兰5.一种基于变精度区分矩阵的不完备信息系统属性约简 [J], 蔡正琦;林和;孔令旺;李永礼因版权原因，仅展示原文概要，查看原文内容请购买。
不完备信息系统的属性约简算法-计算机工程
决策属性集；V = ∪ Vr 是属性值集合，Vr 表示属性 R 的值域； r∈R f :U × R → V 是一个映射函数。若 D 为空，则称信息系统为
数据表，否则称之为决策表。对于具有遗漏属性值的属性子
集 B ⊆ C ，记遗漏值为“*”，则含有未知属性值的信息系统
称为不完备信息系统。Kryszkiewicz M.定义了容差关系 T。
定义 1 容差关系 T 为
( ) ∀x,
y∈U
,
⎛ ⎜ ⎜⎝
TB ( x,
∀Cj∈B
y)
C
⇔
j (x
)
=
C
jபைடு நூலகம்
(
y
)
∨
C
j
(
y
)
=
∗
∨
C
j
(
x
)
=∗
⎞ ⎟ ⎟⎠
其中， TB ( x, y) 表示在属性集合 B 上满足关系个体对象 y 和
对象 x 的容差类关系。本文沿用完备信息系统中的一些相关
定义，对不完备信息系统做相同定义。
若 POSB ( D) = POS(B−{r}) ( D) ，则称 r 为 B 中相对于 D 可省略
的属性，否则称 r 为 B 中相对于 D 不可省略的属性。若对 C
中的独立子集 B ⊆ C ，有 POSB ( D) = POSC ( D) ，则称 B 为 C
的相对约简。
2.2 集合近似关系下的属性约简算法 集合近似关系下的属性约简算法描述如下：
扩展后的信息表进行属性约简。
本文考虑扩展粗糙集理论的适应范围，通过实例比较了
3 种属性约简方法的处理效果。
2 基于集合近似关系的不完备决策属性约简
基于粗糙集的属性约简算法
中 的对 象组 成 的集合 ＋ Ｘ） ＝ ｛ ∈ ＵＩ ） （ Ｂ（
｝ 。
…
３
的上 近似 集 Ｂ ） 根据 知识 判定 可 能属 （ ， 于 的 中的对象 组成 的集合 Ｂ Ｘ）＝ ｛ ∈ Ｕｌ （ Ｘ Ｂ（ ＂ Ｘ ≠ ｝ Ｘ）Ｉ １ 。
定义 ３ 正域
收 稿 日期 ：０ ｌ ３ １ ２ １ － —ｌ ０ 基 金项 目 ： 国家 自然 科 学 基 金 资 助 项 目（ ０７ ０ ９ ６５４３ ）
Ｄ ｃ ｕ Ｄ ＝Ｑ， ＝ ） （ Ｃｎ Ｄ 两个不同的集合。 概念 ２ 完备信息系统与不完备信息系统 在决 策信息系统 Ｄ Ｓ＝＜ ， ｕＤ， ， ＵＣ ＶＰ＞中， 中每个对
１ ２ 基本 定义 ．
Ｌ ）＝ ｛ （ Ｙ∈ ＵＩ（ Ｙ ，）∈ Ｌ ， ｝ Ｌ ＝ ｛ ∈ ＵＩ （ Ｘ Ｌ ） ｝ ， Ｌ ＝ ｛ ∈ ＵＪ （ Ｘ ）ｎ ≠ ｝ 。
（） ２ （） ３ （） ４
定义 １ 不可 分辨 关 系
限制容 差关 系具 有 自反 性 和对 称性 ， 是不 具 但 有 传递 性 。
步骤 有的约简属性集都包含的不可省略属性 的集合 ， 记 为 Ｃ Ｒ Ｐ）＝ｎ Ｒ Ｄ（ Ｏ Ｅ（ Ｅ Ｐ）。
步骤 ７ 将 Ｒ ｄ ｅ 集里的属性与 ｃ集合里剩余的
属性 分别结 合 。 步骤 ８ 采 用组合 属性 ， 复步骤 ２ ～６ 重 。 步骤 ９ 从 Ｒ ｄ的尾部 开 始 ， 后 往前 对 每 个 ｅ 从
２ ２ 知 识约 简算法 ．
ｑ ｝Ｉ Ｄ Ｂ 是一个等价关系。 ）。 （ ） Ｎ 由这种等价关 系导
出 的对 的划 分记 为 Ｕ ＩＤ（ ， 中包 含样本 的 ／Ｎ Ｂ）其 等价类 记 为 ［ ］ 。
｝ 。
…
３
的上 近似 集 Ｂ ） 根据 知识 判定 可 能属 （ ， 于 的 中的对象 组成 的集合 Ｂ Ｘ）＝ ｛ ∈ Ｕｌ （ Ｘ Ｂ（ ＂ Ｘ ≠ ｝ Ｘ）Ｉ １ 。
定义 ３ 正域
收 稿 日期 ：０ ｌ ３ １ ２ １ － —ｌ ０ 基 金项 目 ： 国家 自然 科 学 基 金 资 助 项 目（ ０７ ０ ９ ６５４３ ）
Ｄ ｃ ｕ Ｄ ＝Ｑ， ＝ ） （ Ｃｎ Ｄ 两个不同的集合。 概念 ２ 完备信息系统与不完备信息系统 在决 策信息系统 Ｄ Ｓ＝＜ ， ｕＤ， ， ＵＣ ＶＰ＞中， 中每个对
１ ２ 基本 定义 ．
Ｌ ）＝ ｛ （ Ｙ∈ ＵＩ（ Ｙ ，）∈ Ｌ ， ｝ Ｌ ＝ ｛ ∈ ＵＩ （ Ｘ Ｌ ） ｝ ， Ｌ ＝ ｛ ∈ ＵＪ （ Ｘ ）ｎ ≠ ｝ 。
（） ２ （） ３ （） ４
定义 １ 不可 分辨 关 系
限制容 差关 系具 有 自反 性 和对 称性 ， 是不 具 但 有 传递 性 。
步骤 有的约简属性集都包含的不可省略属性 的集合 ， 记 为 Ｃ Ｒ Ｐ）＝ｎ Ｒ Ｄ（ Ｏ Ｅ（ Ｅ Ｐ）。
步骤 ７ 将 Ｒ ｄ ｅ 集里的属性与 ｃ集合里剩余的
属性 分别结 合 。 步骤 ８ 采 用组合 属性 ， 复步骤 ２ ～６ 重 。 步骤 ９ 从 Ｒ ｄ的尾部 开 始 ， 后 往前 对 每 个 ｅ 从
２ ２ 知 识约 简算法 ．
ｑ ｝Ｉ Ｄ Ｂ 是一个等价关系。 ）。 （ ） Ｎ 由这种等价关 系导
出 的对 的划 分记 为 Ｕ ＩＤ（ ， 中包 含样本 的 ／Ｎ Ｂ）其 等价类 记 为 ［ ］ 。
基于容差计算的非完备信息系统属性约简算法
基于容差计算的非完备信息系统属性约简算法梁宝华【摘要】对于有缺损值的非完备信息系统约简,多数算法利用容差关系求信息量,但此类算法需消耗大量时间计算容差,导致属性约简质量、消耗的时间及空间复杂度均不理想.为了有效提高求容差类计算效率,引入一个与相容类信息量等价的计算公式.以此为基础,提出一种属性约简算法,使时间复杂度降为O(|C|2|U|),空间降为O(|C||U|).最后,通过实例和实验分析并验证了算法的有效性和可行性.%For incomplete information system reduction with defective values, most algorithms use the tolerance relation to compute the amount of information, but this kind of algorithm consumes a large amount of time computing tolerance, which leads to the quality of attribute reduction and the time and space complexity are not ideal.In order to improve the computation efficiency of the tolerance class effectively, a formula for calculating the equivalent information of the compatible class is introduced.Based on it, an attribute reduction algorithm is proposed, which reduces the time complexity to O(|C|2|U|) and reduces the space to O(|C||U|).Finally, the examples and experimental analysis show that the proposed algorithm is efficient and feasible.【期刊名称】《计算机应用与软件》【年(卷),期】2017(034)004【总页数】6页(P299-304)【关键词】粗糙集;属性约简;非完备信息系统;相容类【作者】梁宝华【作者单位】巢湖学院信息工程学院安徽合肥 238000【正文语种】中文【中图分类】TP181粗糙集理论[1-2]是由波兰数学家Pawlak教授于1982年提出的，是一种处理不完全、不精确和模糊性数据的数学工具。
不完备信息系统的属性约简算法研究
（ｅｔ ｆ Ｃｍ ｕｅ ／ ｈｕ Ｔａ ｅ ｎ ｅ ｉ ，Ｘ ｚｏ，ｈｎ ／ ３ ０ ０ Ｃｚ） Ｄｐ ，ｏ ｏｐ ｔ ，Ｘ ｚ ｅｃ ｒ Ｕｉ ｒ ｔ ｒ ｈｏ ｈ ｓ ｖ ｓｙ ／ ｈｕ Ｓ ｘ ０ ４ ０ ， ｈｅ ｈ ａ ｈ
Ａｂ ｔａ ｔ Ｉ ｈｓ ａ ｅ ， ａ ｔｉｕｅ ｅｕ ｔｏ ｂ ｓｄ ｎ ｏｅａ ｃ ｒｌｔ ｎ ｓｒ ｃ ： ｎ ｉ ｐ ｒ ｔ ｐ ｔｒ ｔ ｒｄ ｃｉｎ ａ ｅ ｏ ｔｌｒｎ ｅ ｅａ ｉ ｗａ ｓｕ ｉｄ ａ ｄ ｎ ｌｏｉｈ ｆｒ ｔｒ ｕｅ ｅ ｕｔｏ ｂ ｓｄ ｎ ％ｌｒｎ ｅ ｂ ｏ ｓ ｔｄｅ ， ｎ ａ ａｇ ｒ ｍ ０ ａ ｔｉ ｔ ｒｄ ｃ ｉ ｔ ｂ ｎ ａｅ ｏ ｏｅａ ｃ
备 信息 系统 的研 究却 没 有涉 及 。因此 ，研 究 属性 次
序下 不完 备信息 系统 的属性 约简 算法很 有必 要 。
Ｄ ＝｛ ｌ ｘ∈Ｕ八 （） ＤＩ ｘ 。
定义 ３ 设 Ｕ为 一 个 论域 ，Ｐ、Ｑ是 定 义 在 Ｕ 上
值 的集合 ，Ｖ 表 示属 性 ｒ 的值 域 ，ｆ Ｕ Ｖ是 ： Ａ
一
个信 息 函数 ，它指 定 Ｕ 中每 一个 对象 ｘ的 属性值 ，
方 法 是 先将 不 完 备 信 息 系统 进 行 补 全 ，然 后 再 用
Ｒｏ ｇ ｕ ｈ集 的方法 来进行 处理 。这 样导致 了原 始系统 信 息的变 化 ，得到 的 结果也 不 一定 反映 原 始 系统 的
真 实情 况 。 因此 ，对 属 性次 序 的研 究对 于面 向领 域 的数据 挖掘具 有重 要意义 。
属 性值 “ ”表示 未知 属性值 。 定 义 ２ 容 差 关 系 。 设 不 完 备 信 息 系 统 Ｓ＝ ｃｕＤ ＿ 及 Ｕ 上定义 的二 元关 系 Ｔ（ ＜Ｕ Ａ＝ 厂＞
Ａｂ ｔａ ｔ Ｉ ｈｓ ａ ｅ ， ａ ｔｉｕｅ ｅｕ ｔｏ ｂ ｓｄ ｎ ｏｅａ ｃ ｒｌｔ ｎ ｓｒ ｃ ： ｎ ｉ ｐ ｒ ｔ ｐ ｔｒ ｔ ｒｄ ｃｉｎ ａ ｅ ｏ ｔｌｒｎ ｅ ｅａ ｉ ｗａ ｓｕ ｉｄ ａ ｄ ｎ ｌｏｉｈ ｆｒ ｔｒ ｕｅ ｅ ｕｔｏ ｂ ｓｄ ｎ ％ｌｒｎ ｅ ｂ ｏ ｓ ｔｄｅ ， ｎ ａ ａｇ ｒ ｍ ０ ａ ｔｉ ｔ ｒｄ ｃ ｉ ｔ ｂ ｎ ａｅ ｏ ｏｅａ ｃ
备 信息 系统 的研 究却 没 有涉 及 。因此 ，研 究 属性 次
序下 不完 备信息 系统 的属性 约简 算法很 有必 要 。
Ｄ ＝｛ ｌ ｘ∈Ｕ八 （） ＤＩ ｘ 。
定义 ３ 设 Ｕ为 一 个 论域 ，Ｐ、Ｑ是 定 义 在 Ｕ 上
值 的集合 ，Ｖ 表 示属 性 ｒ 的值 域 ，ｆ Ｕ Ｖ是 ： Ａ
一
个信 息 函数 ，它指 定 Ｕ 中每 一个 对象 ｘ的 属性值 ，
方 法 是 先将 不 完 备 信 息 系统 进 行 补 全 ，然 后 再 用
Ｒｏ ｇ ｕ ｈ集 的方法 来进行 处理 。这 样导致 了原 始系统 信 息的变 化 ，得到 的 结果也 不 一定 反映 原 始 系统 的
真 实情 况 。 因此 ，对 属 性次 序 的研 究对 于面 向领 域 的数据 挖掘具 有重 要意义 。
属 性值 “ ”表示 未知 属性值 。 定 义 ２ 容 差 关 系 。 设 不 完 备 信 息 系 统 Ｓ＝ ｃｕＤ ＿ 及 Ｕ 上定义 的二 元关 系 Ｔ（ ＜Ｕ Ａ＝ 厂＞
不完备信息系统属性约简算法研究
不完备信息系统属性约简算法研究作者：***来源：《计算机时代》2020年第07期摘要：基于经典粗糙集，从不完备信息系统和相容类的相关概念出发，给出了不完备信息系统中相容类的算法和属性约简算法。
此算法将继续被研究以期降低其时间复杂度。
关键词：不完备信息系统;粗糙集;属性约简;相容类中图分类号：TP18 文献标识码：A 文章编号：1006-8228（2020）07-83-030引言自学者Pawlak于1982年提出粗糙集以来，粗糙集理论在机器学习、规则提取、决策支持等领域得到了广泛应用。
经典的粗糙集理论以完备的信息系统为研究对象，在处理数据时基于严格的等价关系来进行划分。
然而，在实际生产、生活和科学实践中，由于数据获取、数据保存技术等方面的限制，很多信息系统都会存在属性的缺省值，即遇到的绝大多数信息系统都是不完备的。
在文献（7）中作者为了能利用粗糙集来处理不完备的信息系统，提出以相容关系来分类，但遇到数据量比较大时，人为计算相容类耗时耗力，求属性约简更是耗时。
所以设计计算机算法来处理是十分关键的。
本文的安排如下：第一部分简要阐述不完备信息系统、完备信息系统及其约简集的相关概念;第二部分设计了计算不完备信息系统中相容类的算法;第三部分设计了计算不完备信息系统中属性约简集的算法;最后，给出了全文总结。
4结束语本文在相关定义和相容类的分类方法下，设計了处理不完备信息系统中分类和属性约简的计算机算法，极大地简化了计算量，在一定程度上能够有效地节省计算时间和研究者的精力。
本文只是在相容类情况下进行分类和属性约简算法的一个初步探索。
基于本文的结果，还可以深入研究分类和属性约简的算法，以进一步降低算法的时间复杂度。
基于近似度的不完备信息系统属性约简
［ ｙｗｏｄ Ｉａｐｏ ｉ ｔ ｄｇｅ；ｎ ｏ ｌｔ ｉｆｒ ｔ ｎｓｓ ｍ； ｔｉｕｅｒｄ ｃ ｏ Ｋｅ ｒ ｓ ｐ ｒｘｍａｅ ｅ ｒｅ ｉｃ ｍｐｅｅ ｎｏｍａｏ ｙｔ ａ ｒ ｔ ｕ ｔ ｎ ｉ ｅ ｔｂ ｅ ｉ
ＤＯＩ １ ． ６ ０ｉ ｎ１０ —４ ８２ １．３０７ ： ０３ ９ ．ｓ ． ０３ ２ ．０ ０ ．１ ９ ｓ ０ １
Ａｎ ｕ Ｕｎｖ ｒｔ， ｆｉ ３ ０ ９ Ｃ ｉａ ２ Ｓａｅ ｙＬ ｂ ｒｔｒ ｒ ｖ ｌ ｏｔ ｒ ｅｈ ｏｏ ｙ Ｎａｊ ｇＵ ｉｅｓｙ Ｎ ｎｉｇ２ ０ ９ ， ｈｎ ） ｈ ｉ ｉｅｓ ｙＨｅｅ ２ ０ ３ ， ｈｎ ；． ｔｔ ａ ｏａ ｙ ｆ ｅ ｆ ｅＴ ｃｎ ｌｇ ， ｎｉ ｎｖｒｉ ， ａｊ １０ ３ Ｃ ｉａ ｉ Ｋｅ ｏ ｏ Ｎｏ Ｓ ｗａ ｎ ｔ ｎ
较 高 的约 简 效 率 。
关健词 ：近似度 ；不完备信息系统 ；属性约简
Ｉ ｃ ｍ ｐ ｅ ｅＩ ｆ ｒ ａ ｉ ｎ Ｓ ｓｅ ｔ ｉ ｕ ｅＲｅ ｕ ｔ０ ｎ ｏ ｌｔ ｎ ｏ ｍ ｔ０ ｙ ｔ ｍ Ａｔｒｂ ｔ ｄ ｃ ｉ ｎ
Ｂａ ｅ ｎ Ａ ｐｐ ｏ ｉ ａ ｅＤ ｅ ｒ ｅ ｓｄ０ ｒ ｘ ｍ ｔ ｇ ｅ
ｓｔ ｆ ｅ ｏ
） ｎ ｏ ｓｎ ｔ ｅｏ ｇ ｔ ａ ｄｄ ｅ ｏ ｌｎ ｂ ｏ
） Ｏ ｉ ｂ ｓｓ ａ ｔ ｉｕ ｅｒｄ ｃ ｏ ｌ ｏｉ ｍ ａ ｅ ｎ ａ ｐ ｏ ｉ ｔ ｄ ｇｅ ｏ ｃ ｍｐｅｅｉｆ ｒ ｔ ｎ ． ｎ ｔ ｓ ａ ｉ， ｎａｔ ｂ ｔ ｕ ｔ ｎ ａ ｒ ｈ ｂ ｄ ｏ ｐ ｒ ｘｍａｅ ｅ ｒｅｆ ｒ ｎ ｏ ｌｔ ｎ ｏ ｍａ ｏ ｈ ｒ ｅ ｉ ｇ ｔ ｓ ｉ ｉ
［ ｂ ｔａ ｔ ｈｓ ａｅ ｏ ｓ ｅｓｔｅｄｆ ｒｎｅ ｆ ｅｉｄｖｄ ａ ｃｎｒ ｕｉｎｂｓｄｏ ｔｉｕｅｓｔ ｌ ｓ ｃｔ ｎｉ ｅｔｌ ａｃ ｅａ ｏ ， Ａ ｓｒｃ！Ｔ ｉ ｐ ｐ ｒ ｎｉ ｒ ｈ ｉｅｅ ｃｓｏ ｉｉｕｌ ｏ ｔｂ ｔ ａｅ ｎ ａｒ ｔ ｅ ｃａ ｉ ａ ｏ ｎｔ ｅ ｎｅｒｌ ｎ ｃ ｄ ｆ ｈ ｔ ｎ ｉ ｏ ｔｂ Ｐ ｓｆ ｉ ｉ ｈ ｏｒ ｉ ｔ
不完备信息系统的一种属性相对约简算法
维普资讯
第３ ３卷 第 ９期
Ｖ ．３ ｏ１ ３
・
计
算
机
工
程
２０ ０ ７年 ５月
Ｍａ ｏ ｕ ｅ ｇ ｎ ｅ ｉ ｇ ｍｐ ｔ ｒＥｎ ｉ ｅ ｒｎ
人工 智能及 识别技 术 ・
文章编号：１ ３２（０） ＿ １４ ２ 文献标 ０ ＿ ４８ ０ ０ ＿ ８一ｌ ０ ２ ７ ０ 识码： Ａ
ＺＨＡＮＧ ｅ ｇｅ， ＡＮＧ ｈ ａ。 ＡＯ ｉｎ ｅ Ｔ ｎ ｆｉＷ Ｘｉｕ ｉＸＩ Ｊａ ｍ ｉ
（ ｐ ｒ ｎ ｏ Ｅ ｅ ｔ ｃ ｌ ｎ ｔ ｍａ ｉｎ Ｓ ａ ｇ ａ Ｍａ ｉｍｅＵｎｖ ｒｉ ， ｈ ｎ ｈ ｉ ０ １ ５ Ｄｅ ａｔ ｔ ｆ ｌｃｒ ａ ａ ｄＡｕ ｏ ｔ ， ｈ ｎ ｈ ｉ ｒｔ ｉ ｅｓ ｙ Ｓ ａ ｇ ａ ２ ０ ３ ） ｍｅ ｉ ｏ ｉ ｔ
规则 ，若存在 ｆ ｘ， ） （ ． ） （，ｃ ＝ｆｘ， ，但 ｆｘ， ≠ｆｘ， ）， ｃ （． Ｄ） （．Ｄ
则称该决策表是不相容的。 由于不 完备信息系统含 有一 定数量的空值 ，相似关系的
信息系统决策表 的求核与属性相对约简一直是粗糙集理
论和应用研究的焦点 问题 ，且决策表核属性的确定往往是属
定义很可能会导致一些规则不相容 。考虑决策表可能存在的
［ ｙｗ ￣ｓ ｏ ｇ ｅ ｔｅｒ；ｎｏ ｌｅｉｆｒ ａｉｎｓｓ ｍ； ｅａ ｖ ｄ ｃｉｎ Ｇｅ ｅａｉ ｄｄｃｓ ｎｔｂｅ Ｋｅ ｏ ］Ｒ ｕ ｈｓｔｈｏｙ Ｉｃｍｐｅ ｏ ｔ ｙｔ Ｒ ｌｉｅｒ ｕ ｔ ； ｎｒｌ ｅ ｅｉｏ ｌ ｔ ｎ ｍ ｏ ｅ ｔ ｅ ｏ ｚ ｉ ａ
统是完备的 ，每 个样本对象的所有属性值都是 已知 的。而在 现实生活中不完备 的信息系统随处可见。为了使粗糙集理论 能适应于对 不完备信息系统 的处理 ，目前主要有 ２种方法： （） 处理方法 ，即通过数据预处理把不 完备信息表转化为 １间接 完备信息表 ；（） ２直接处理方法 ，即对 经典粗糙集理论中的相 关概念在不完备信息系统下进行 扩充 。
第３ ３卷 第 ９期
Ｖ ．３ ｏ１ ３
・
计
算
机
工
程
２０ ０ ７年 ５月
Ｍａ ｏ ｕ ｅ ｇ ｎ ｅ ｉ ｇ ｍｐ ｔ ｒＥｎ ｉ ｅ ｒｎ
人工 智能及 识别技 术 ・
文章编号：１ ３２（０） ＿ １４ ２ 文献标 ０ ＿ ４８ ０ ０ ＿ ８一ｌ ０ ２ ７ ０ 识码： Ａ
ＺＨＡＮＧ ｅ ｇｅ， ＡＮＧ ｈ ａ。 ＡＯ ｉｎ ｅ Ｔ ｎ ｆｉＷ Ｘｉｕ ｉＸＩ Ｊａ ｍ ｉ
（ ｐ ｒ ｎ ｏ Ｅ ｅ ｔ ｃ ｌ ｎ ｔ ｍａ ｉｎ Ｓ ａ ｇ ａ Ｍａ ｉｍｅＵｎｖ ｒｉ ， ｈ ｎ ｈ ｉ ０ １ ５ Ｄｅ ａｔ ｔ ｆ ｌｃｒ ａ ａ ｄＡｕ ｏ ｔ ， ｈ ｎ ｈ ｉ ｒｔ ｉ ｅｓ ｙ Ｓ ａ ｇ ａ ２ ０ ３ ） ｍｅ ｉ ｏ ｉ ｔ
规则 ，若存在 ｆ ｘ， ） （ ． ） （，ｃ ＝ｆｘ， ，但 ｆｘ， ≠ｆｘ， ）， ｃ （． Ｄ） （．Ｄ
则称该决策表是不相容的。 由于不 完备信息系统含 有一 定数量的空值 ，相似关系的
信息系统决策表 的求核与属性相对约简一直是粗糙集理
论和应用研究的焦点 问题 ，且决策表核属性的确定往往是属
定义很可能会导致一些规则不相容 。考虑决策表可能存在的
［ ｙｗ ￣ｓ ｏ ｇ ｅ ｔｅｒ；ｎｏ ｌｅｉｆｒ ａｉｎｓｓ ｍ； ｅａ ｖ ｄ ｃｉｎ Ｇｅ ｅａｉ ｄｄｃｓ ｎｔｂｅ Ｋｅ ｏ ］Ｒ ｕ ｈｓｔｈｏｙ Ｉｃｍｐｅ ｏ ｔ ｙｔ Ｒ ｌｉｅｒ ｕ ｔ ； ｎｒｌ ｅ ｅｉｏ ｌ ｔ ｎ ｍ ｏ ｅ ｔ ｅ ｏ ｚ ｉ ａ
统是完备的 ，每 个样本对象的所有属性值都是 已知 的。而在 现实生活中不完备 的信息系统随处可见。为了使粗糙集理论 能适应于对 不完备信息系统 的处理 ，目前主要有 ２种方法： （） 处理方法 ，即通过数据预处理把不 完备信息表转化为 １间接 完备信息表 ；（） ２直接处理方法 ，即对 经典粗糙集理论中的相 关概念在不完备信息系统下进行 扩充 。
基于信息熵的不完备模糊信息系统属性约简
合， ｛
， … ｝ 是信 息 函数集 。 对每个 ｃ∈Ｃ都 有
ｃ ， ｃ为 Ｃ的值 域 ， 且至 少有一个 属
厂 芒Ｆ使得 ｆ ：
性 Ｃ ∈Ｃ使 得 ｃ有 空值 ，用 六表 示
二元关 系 ：
［ Ｄ ， ］ ， 其中 ∈
定 义 ６ ］ 设 不完 备 信 息 系统 Ｊ ｓ ＝ （ Ｕ， Ｃ ， Ｖ， Ｆ） 上 有
模 糊 集 的粗 糙 集 理 论 在 １ ９ ９ ０年 由 Ｄ ｕ ｂ ｏ ｉ ｓ 等 人 提 出后得 到 了迅 速发展 。 近几年 来 不完 备和 模糊 信息 系统 的属性 约简成 为研 究 热点 之 一 ， 对于 不 完备信 息 系统 ， 有 Ｋ ｒ ｙ ｓ ｚ ｋ ｉ ｅ ｗ ｉ ｃ ￣２ ］ 提 出 的基 于 容 差 关 系 的粗 糙
ｆ
ｌ
１
Ｊ
（ Ｘ ） ＝ ｛ ∈ Ｕ Ｉ （ ） ｎ ≠ ｝ ＝ ｖ ／ （ ） Ｉ ∈ ｝
与 （ ） ＝ｆ ∈Ｕ Ｊ （ ） Ｘ ｌ ＿ ｛ ∈ Ｘ』 （ ） ｘ｝
由定义 显然 得 出 ： （ ） （ ） 。同时 ， 由定义可 知， 上 近 似 集表 示 的是 可 能属 于 ｘ的对 象集 合 ， 下近
Ｂ） ＝ ｆ ∈Ｕ Ｉ ｂ∈ Ｂ， ６ （ ） ＝ ６ （ Ｙ ） Ｖｂ （ ） ＝ ★Ｖ ｂ （ Ｙ ） ＝ 六ｌ ，
其中 Ｂ 口ｃ ，则称 （ 口） 为相 容 关系。 由定 义 可知 ， 相容 类 中空值 与其 他任 意属性值 是 相等的， 相 容 关系 产生 相容 类 （ ） ， 其分类 Ｕ ／ Ｔ （ Ｂ） ＝
要 的意义 。
定义 １ ｃ ｌ 设 Ｓ ＝ （ ， Ｃ， Ｄ， ， Ｆ） 是 不完 备模 糊 目标
不完备信息系统中属性的重要度及约简方法
２ Ｘｉｙ ｎ ｃ ｔ ｎ ｌ ａ ｄ Ｔ ｃ ｎ ｃ ｌ Ｃ ｌ ｇ ， ｎ ａ ｇ Ｈｅ ａ ６ ０ ０， ｈ ｎ ． ｎ ａ ｇ Ｖｏ ａｉ ａ ｎ ｅ ｈ ｉａ ｏｌ ｅ Ｘｉ ｙ ｎ ， ｎ ｎ ４ ４ ０ Ｃ ｉａ ｏ ｅ
Ｅ ｍａ ： １２ ＠１ ３ ｏ － ｉ ￣ ５４ ６ ． ｒ ｌ ｃｎ Ｙ Ｇ ｊ —ｉ ， Ｈ － ｕ 。 Ｉ Ｋｅ ｙ ｎＩ ｏ ｔｎ ｅ ｒｅ ｏ ｔ ｉｕ ｅ ａ ｄ ａｔｉｕ ｅ ｒｄ ｃｉｎ ｉ ｎ ｏ ｌ ｅ ｉｆｒ － ＡＮ ｉ ｌ Ｚ ＯＵ Ｙｕ ｈ ａ Ｑ Ｎ － ｕ ． ｎ ｍｐ ｒ ｔｄ ｇ ｅ ｆ ａｔ ｂ ｔ ｎ ｔ ｂ ｔ ｅ ｕ ｔ ｎ ｉｃ ｍｐｅ ｎ ｏ ｍａ ａ ｒ ｒ ｏ ｔ
Ｃ ｍ ｕ ｒＥ ｇｎｅｉｇａ ｄＡ ｐｉ ｔ ｎ 计算机工程与应用 ｏ ｐ ｔ ｎ ｉ ｒ ｎ ｐ ｌａｉ ｓ ｅ ｅ 、 数 信号 与信 息处 理◎
不完备信息系统 中属性 的重要 度及 约简 方法
杨 霁琳 ， 周玉 华 ２秦 克云 １ ，
关键词 ： 不完备信 息系统 ； 相似 关系； 粗糙 集； 属性约 简； ＷＡ算子 Ｏ Ｄ ：０３ ７／ｉ ｎ１０ — ３ １ ０ ０Ｏ ． １ 文 章 编号 ：０ ２ ８ ３ （ ０ ０ ０ — ０ ９ ０ 文 献 标 识码 ： 中 图 分 类 ￣ ： Ｐ ８ ＯＩ１ ． ８ ．ｓ．０２ ８ ３ ． １ ．１ ３ ７ ｊｓ ２ ０ １０ — ３ １ ２ １ ） １０ ９ —４ Ａ ＇Ｔ １
Ｙ Ｎ ｉｌ １Ｚ Ｏ ｕ ｈ ａ． Ｉ ｅ ｙ ｎ Ａ Ｇ Ｊ—ｉ ， Ｈ Ｕ Ｙ － ｕ Ｑ Ｎ Ｋ － ｕ ｎ
１ ． 西南交通大学 数学学院 ， 成都 ６ ０３ １０ １ ２信阳职业技术学院 ， ． 河南 信 阳 ４ ４ ０ ６００
Ｅ ｍａ ： １２ ＠１ ３ ｏ － ｉ ￣ ５４ ６ ． ｒ ｌ ｃｎ Ｙ Ｇ ｊ —ｉ ， Ｈ － ｕ 。 Ｉ Ｋｅ ｙ ｎＩ ｏ ｔｎ ｅ ｒｅ ｏ ｔ ｉｕ ｅ ａ ｄ ａｔｉｕ ｅ ｒｄ ｃｉｎ ｉ ｎ ｏ ｌ ｅ ｉｆｒ － ＡＮ ｉ ｌ Ｚ ＯＵ Ｙｕ ｈ ａ Ｑ Ｎ － ｕ ． ｎ ｍｐ ｒ ｔｄ ｇ ｅ ｆ ａｔ ｂ ｔ ｎ ｔ ｂ ｔ ｅ ｕ ｔ ｎ ｉｃ ｍｐｅ ｎ ｏ ｍａ ａ ｒ ｒ ｏ ｔ
Ｃ ｍ ｕ ｒＥ ｇｎｅｉｇａ ｄＡ ｐｉ ｔ ｎ 计算机工程与应用 ｏ ｐ ｔ ｎ ｉ ｒ ｎ ｐ ｌａｉ ｓ ｅ ｅ 、 数 信号 与信 息处 理◎
不完备信息系统 中属性 的重要 度及 约简 方法
杨 霁琳 ， 周玉 华 ２秦 克云 １ ，
关键词 ： 不完备信 息系统 ； 相似 关系； 粗糙 集； 属性约 简； ＷＡ算子 Ｏ Ｄ ：０３ ７／ｉ ｎ１０ — ３ １ ０ ０Ｏ ． １ 文 章 编号 ：０ ２ ８ ３ （ ０ ０ ０ — ０ ９ ０ 文 献 标 识码 ： 中 图 分 类 ￣ ： Ｐ ８ ＯＩ１ ． ８ ．ｓ．０２ ８ ３ ． １ ．１ ３ ７ ｊｓ ２ ０ １０ — ３ １ ２ １ ） １０ ９ —４ Ａ ＇Ｔ １
Ｙ Ｎ ｉｌ １Ｚ Ｏ ｕ ｈ ａ． Ｉ ｅ ｙ ｎ Ａ Ｇ Ｊ—ｉ ， Ｈ Ｕ Ｙ － ｕ Ｑ Ｎ Ｋ － ｕ ｎ
１ ． 西南交通大学 数学学院 ， 成都 ６ ０３ １０ １ ２信阳职业技术学院 ， ． 河南 信 阳 ４ ４ ０ ６００
基于容差关系的不完备决策系统属性约简算法
似 关 系 ， 至 是一般 关系 。 甚
以对数据的分类能力为基础 ， 对模糊和不确定数据进行分
析和处 理 ， 因此 ， 目前该 理 沦已被广 泛应 用于 数据挖 掘 、 模 式识别 和人工智 能等 领域 ｌ３ ２ｊ ．。 属 性约简 是 Ｒ ｕｈ集 理 论 的核 心 问题 之 一 ， 可 以 ｏｇ 它
２ Ｄｅｔ ｏ ｔｅ ｔ ｆ ｘ Ｕｎ ． ｈ ｎ ｙ ３ ０ ０ Ｃ ｉａ ． ｐ． ｆ ｈｍａｉ ｏ ｉ ｉ ，Ｚ ａ ｇｅ７ ４０ ， ｈｎ） Ｍａ ｓ ｃ Ｈｅ ｖ
Ａｂ ｔａ ｔＧｉｅｄ ｆ ｉｉｎｏｆ ｔｒｂ ｔ ｅａｉｅｒｄ ｃｉｎｏ ｈ ｎ ｏ ｌｔ ｅ ｉｉｎ ｓｓｅ ｉ ｈ ｏｅａ ｔｒｌｔ ｎ．Ａｎ ａｇ ｒｔｍ ｏ ｉｄｎ ｓｒｃ ： ｖ ｅｉ ｔ ｔｉｕ ｅｒｌｔ ｅ ｕ ｔ ｆ ｅｉｃ ｍｐｅｅｄ ｃｓｏ ｙｔｍ ｎｔ ｅｔｌｒｎ ｅａｉ ｎ ｏ ａ ｖ ｏ ｔ ｏ ｌｏ ｉ ｈ ｆｒｆｎ ｉｇ ａｔ ｂ ｔ ｅ ｕ ｔ ｎｂ ｓ ｄｏ ｏ ｉｉｅｒｇｏ ｆｄ ｃｓｏ ｔｒｂ ｔ ｅａ ｉｅｔ ｎ ｔ ｎ ａｔｉｕ ｅｉ ｒｓ ｎｅ ．Ｗ ｉｈａｌ ｎ ｉｉｎ ａｔｉｕ ｅ ｓ ｔｒ ｕ ｅｒ ｃｉ ａ ｅ ｎ ｐ ｓｔ ｅ ｉｎｏ ｅ ｉｉｎａｔｉｕ ｅｒｌｔ ｏ ｃ ｄｉｏ ｔｒｂ ｔ ｐ ｅｅ ｔ ｉ ｄ ｏ ｖ ｖ ｏ ｉ ｓ ｄ ｔ ｌｃ ｄｔｏ ｔｒｂ ｔｓａ ｏ ｔｅｉｉａ ｅ ｕ ｔｏ ｈ ｎｔ ｌ ｄ ｃｉｎ，ｔｉ ｇ ｒｔ ａ ｅ ｅａｉｅｐ ｓｔ ｅ— ｒｇｏ ｓｔｅｉｅａｉｅｃｉｅｉｎ ｔ ｓｕ ｅｔ ａ ｌｓｉｉａｉｎａ ｉｔ ｆｔｅｒｓ ｌ ｄ ｉ ｒ ｈｓａ ｏｉｈ ｔｋ ｓｒｌｔｖ ｏ ｉｖ ｌ ｍ ｉ ｅ ｉｎａ ｈ ｒｔｖ ｒｔｒｏ ｏａｓ ｒ ｈ ｔｃａｓｆ ｔ ｂｌｙｏ ｈ ｅ ｕｔ ｔ ｃ ｏ ｉ ｅ ｒ ｕ ｔ ｎ ｄ ｅ ｏ ｅ ｌ ｅ ｎｔ ｅｓｌｅｔｍｅ ｈ ｉ ｏ ｌｘｔ ｆｔｉ ｌｏｉｈ ｎ ｌｚｄ，ａ ｄｔ ｅｅｆｃｉｅ ｅｓａ ｄｐ ａ ｔ ａ ｉｔ ｆ ｄ ｅ ｃｉ ｏ ｓｎ ｔｄ ｃｉ ．Ｉ ｈ ａｎ ｉ ，ｔｅｔｍｅｃ ｍｐｅ ｉｙｏ ｈｓａｇ ｒｔ ｏ ｎ ｍ ｉ ａ ａｙ ｅ ｓ ｎ ｈ ｆｅｔｖ ｎ ｓ ｎ ｒｃ ｉ ｂｌｙｏ ｃ ｉ ｔ ｉ ｌｏ ｉ ｒ ｅ ｉｅ ｙｔ ｅｅ ａ ｌ． ｈｓａｇ ｒ ｈ ａ ｅｖ ｒｆ ｄ ｂ ｈ ｘ ｍｐｅ ｔ ｍ ｉ Ｋｅ ｒ ： ｓｔｖ ｙｗｏｄｓ ｐ ｉｉｅ— ｒｇｉｎ；ａｔｉｕｅｒ ｄ ｃｉｎ；ｒ ｕ ｈ ｓｔ ｎ ｍｐｅｅｄ ｃｓ ｎｓ ｓｅ ｏ ｅ ｏ ｔｒｂ ｔ ｅ ｕ ｔ ｏ ｏ ｇ ｅ ；ｉｃ ｏ ｌｔ ｅ ｉｏ ｙｔｍ ｉ
以对数据的分类能力为基础 ， 对模糊和不确定数据进行分
析和处 理 ， 因此 ， 目前该 理 沦已被广 泛应 用于 数据挖 掘 、 模 式识别 和人工智 能等 领域 ｌ３ ２ｊ ．。 属 性约简 是 Ｒ ｕｈ集 理 论 的核 心 问题 之 一 ， 可 以 ｏｇ 它
２ Ｄｅｔ ｏ ｔｅ ｔ ｆ ｘ Ｕｎ ． ｈ ｎ ｙ ３ ０ ０ Ｃ ｉａ ． ｐ． ｆ ｈｍａｉ ｏ ｉ ｉ ，Ｚ ａ ｇｅ７ ４０ ， ｈｎ） Ｍａ ｓ ｃ Ｈｅ ｖ
Ａｂ ｔａ ｔＧｉｅｄ ｆ ｉｉｎｏｆ ｔｒｂ ｔ ｅａｉｅｒｄ ｃｉｎｏ ｈ ｎ ｏ ｌｔ ｅ ｉｉｎ ｓｓｅ ｉ ｈ ｏｅａ ｔｒｌｔ ｎ．Ａｎ ａｇ ｒｔｍ ｏ ｉｄｎ ｓｒｃ ： ｖ ｅｉ ｔ ｔｉｕ ｅｒｌｔ ｅ ｕ ｔ ｆ ｅｉｃ ｍｐｅｅｄ ｃｓｏ ｙｔｍ ｎｔ ｅｔｌｒｎ ｅａｉ ｎ ｏ ａ ｖ ｏ ｔ ｏ ｌｏ ｉ ｈ ｆｒｆｎ ｉｇ ａｔ ｂ ｔ ｅ ｕ ｔ ｎｂ ｓ ｄｏ ｏ ｉｉｅｒｇｏ ｆｄ ｃｓｏ ｔｒｂ ｔ ｅａ ｉｅｔ ｎ ｔ ｎ ａｔｉｕ ｅｉ ｒｓ ｎｅ ．Ｗ ｉｈａｌ ｎ ｉｉｎ ａｔｉｕ ｅ ｓ ｔｒ ｕ ｅｒ ｃｉ ａ ｅ ｎ ｐ ｓｔ ｅ ｉｎｏ ｅ ｉｉｎａｔｉｕ ｅｒｌｔ ｏ ｃ ｄｉｏ ｔｒｂ ｔ ｐ ｅｅ ｔ ｉ ｄ ｏ ｖ ｖ ｏ ｉ ｓ ｄ ｔ ｌｃ ｄｔｏ ｔｒｂ ｔｓａ ｏ ｔｅｉｉａ ｅ ｕ ｔｏ ｈ ｎｔ ｌ ｄ ｃｉｎ，ｔｉ ｇ ｒｔ ａ ｅ ｅａｉｅｐ ｓｔ ｅ— ｒｇｏ ｓｔｅｉｅａｉｅｃｉｅｉｎ ｔ ｓｕ ｅｔ ａ ｌｓｉｉａｉｎａ ｉｔ ｆｔｅｒｓ ｌ ｄ ｉ ｒ ｈｓａ ｏｉｈ ｔｋ ｓｒｌｔｖ ｏ ｉｖ ｌ ｍ ｉ ｅ ｉｎａ ｈ ｒｔｖ ｒｔｒｏ ｏａｓ ｒ ｈ ｔｃａｓｆ ｔ ｂｌｙｏ ｈ ｅ ｕｔ ｔ ｃ ｏ ｉ ｅ ｒ ｕ ｔ ｎ ｄ ｅ ｏ ｅ ｌ ｅ ｎｔ ｅｓｌｅｔｍｅ ｈ ｉ ｏ ｌｘｔ ｆｔｉ ｌｏｉｈ ｎ ｌｚｄ，ａ ｄｔ ｅｅｆｃｉｅ ｅｓａ ｄｐ ａ ｔ ａ ｉｔ ｆ ｄ ｅ ｃｉ ｏ ｓｎ ｔｄ ｃｉ ．Ｉ ｈ ａｎ ｉ ，ｔｅｔｍｅｃ ｍｐｅ ｉｙｏ ｈｓａｇ ｒｔ ｏ ｎ ｍ ｉ ａ ａｙ ｅ ｓ ｎ ｈ ｆｅｔｖ ｎ ｓ ｎ ｒｃ ｉ ｂｌｙｏ ｃ ｉ ｔ ｉ ｌｏ ｉ ｒ ｅ ｉｅ ｙｔ ｅｅ ａ ｌ． ｈｓａｇ ｒ ｈ ａ ｅｖ ｒｆ ｄ ｂ ｈ ｘ ｍｐｅ ｔ ｍ ｉ Ｋｅ ｒ ： ｓｔｖ ｙｗｏｄｓ ｐ ｉｉｅ— ｒｇｉｎ；ａｔｉｕｅｒ ｄ ｃｉｎ；ｒ ｕ ｈ ｓｔ ｎ ｍｐｅｅｄ ｃｓ ｎｓ ｓｅ ｏ ｅ ｏ ｔｒｂ ｔ ｅ ｕ ｔ ｏ ｏ ｇ ｅ ；ｉｃ ｏ ｌｔ ｅ ｉｏ ｙｔｍ ｉ
基于容差关系的不完备信息系统的属性约简
第２ ４卷
Hale Waihona Puke ２ ０ １ ４年 １月 第１ 期
计 算 机 技 术 与 发 展
ＣＯＭＰ ＵＴＥ Ｒ Ｔ ＥＣＨＮＯＬ ＯＧＹ ＡＮＤ Ｄ ＥＶＥ ＬＯＰ ＭＥＮＴ
Ｖ ｏ １ ． ２ ４ Ｎｏ ． １
Ｊ ａ ｎ ． ２ ０ １ ４
基 于容 差关 系的不 完 备信 息 系统 的属 性 约简
ＹＡＮ Ｊ ｉ ａ －ｋ ａ ｉ ， Ｆ ＡＮ Ｍｉ ｎ， ＬＩ Ｕ Ｗｅ ｎ－ｑ ｉ ， ＹＥ Ｒｏ ｎ ｇ－ ｒ ｏ ｎ ｇ
（ Ｓ ｃ ｈ ｏ ｏ ｌ ｏ ｆ Ｓ ｃ ｉ ｅ ｎ ｃ ｅ ， Ｋ ｕ ｎ ｍｉ ｎ ｇ Ｕ ｎ ｉ ｖ ｅ ｒ ｓ ｉ ｔ ｙ ｏ ｆ Ｓ ｃ ｉ ｅ ｎ ｃ ｅ ａ ｎ ｄ Ｔ ｅ ｃ ｈ ｎ ｏ ｌ ｏ ｇ ｙ ， Ｋ ｕ ｎ ｍｉ ｎ ｇ ６ ５ ０ ５ ０ ０ ， Ｃ ｈ ｉ ｎ ａ ）
Ａｂｓ ｔ ｒ ａ ｃ ｔ ： Ｒｏ ｕ ｇ ｈ ｓ ｅ ｔ ｔ ｈ ｅ ｏ ｒ ｙ ｉ ｓ ａ ｋ ｉ ｎ ｄ ｏ ｆ ｅ ｆ ｆ ｅ ｃ ｔ ｉ ｖ ｅ ｔ ｏ ｏ ｌ ｆ ｏ ｒ ｄ ｅ ａ ｌ ｉ ｎ ｇ ｗｉ ｈ ｔ ｕ ｎ ｃ ｅ ｒ ｔ ａ ｉ ｎ ｔ ｙ ｋ ｎ ｏ ｗｌ ｅ ｄ ｇ ｅ ． Ａｔ ｔ ｒ ｉ ｂ ｕ ｔ ｅ ｒ ｅ ｄｕ ｃ ｉ ｔ ｏ ｎ ｉ ｓ ｏ ｎ ｅ ｏ ｆ ｈｅ ｔ ｍｏ ｓ ｔ ｉ ｍ— ｐ ｏ ｒ ｔ ａ ｎ ｔ ｃ ｏ ｎ ｔ ｅ ｎ ｔ ． Ｎｅ ｖ ｅ ｒ ｔ ｈ ｅ ｌ ｅ ｓ ｓ ， ｈｅ ｔ ｃ ｌ ａ ｓ ｓ ｉ ｃ ｌ ａ ｒ ｏ ｕ ｇ ｈ ｓ ｅ ｔ ｈｅ ｔ ｏ ｙ ｒ ｂ ａ ｓ ｅ ｄ ｏ ｎ ｅ ｑ ｕ ｉ ｖ ａ ｌ ｅ ｎ ｃ ｅ ｍｌ ａ ｉｏ ｔ ｎ ｈａ ｓ ｎ ｏ ｔ ｂｅ ｅ ｎ ａ ｐ ｐ ｌ ｉ ｅ ｄ ｆ ｏ ｒ ｔ ｈ ｅ ｉ ｎ ｃ ｏ ｍｐ ｌ ｅ ｔ ｅ ｉ ｎ ｏｒ ｆ ｍａ － ｔ ｉ ｏ ｎ ｓ ｙ ｓ ｔ ｅ ｍ ｗｈ ｉ ｃ ｈ ｓ ｏ ｍｅ ａ ｔ ｔ ｒ ｉ ｂｕ ｔ ｅ ｉ ｓ ｈｅ ｔ ｄ ｅ ｆ ａ ｕ ｌ ｔ ｖ ａ ｌ ｕ ｅ ． Ｔｈ ｅ ｄ ｅ ｉｎ ｆ ｉ ｉ ｔ ｏ ｎ ｈａ ｔ ｔ ｔｔ ａ ｒ ｉ ｂ ｕ ｔ ｅ ｓ ｒ ｅ ｄｕ ｃ ｔ ｉ ｏ ｎ ｏ ｆ ｉ ｎ ｃ ｏ ｍｐ ｌ ｅ ｅ ｔ ｉ ｎ ｆ ｏ ｒ ｍａ ｔ ｉ ｏ ｎ ｓ ｙ ｓ ｔ ｅ ｍ ｉ ｓ ｓ ｉ ｍｉ ｌ ａ ｒ ｔ ｏ ｈｅ ｔ ｃ ｌ ａ ｓ ｓ ｉ ｃ ｌ ａ ｒ ｏ ｕ ｇ ｈ ｓ ｅ ｔ ｂ ｃａ ｅ ｕｓ ｅ ｏ ｆ ｈｅ ｔ ｔ ｏ ｌ ｅ ｒ ａ ｎ ｃ ｅ ｒ ｅ ｌ ａ ｉ ｔ ｏ ｎ． Ｃａ ｎ ｅ ｘ ｐ ｎｄ ａ ｈｅ ｔ ｃ ｌ ａ ｓ ｓ ｉ ｃ ｌ ａ ｒ ｏ ｕ ｇ ｈ ｓ ｅ ｔ ｈｅ ｔ ｏ ｙ ｒ ｗｉ ｈ ｔ ｏｌ ｔ ｅ ｒ ｎｃ ａ ｅ ｅｌ ｒ ａ ｉ ｔ ｏ ｎ ． Ｉ ｎ ｈｉ ｔ ｓ ｐ ａ ｐｅ ｒ ， ｂ ｙ
Hale Waihona Puke ２ ０ １ ４年 １月 第１ 期
计 算 机 技 术 与 发 展
ＣＯＭＰ ＵＴＥ Ｒ Ｔ ＥＣＨＮＯＬ ＯＧＹ ＡＮＤ Ｄ ＥＶＥ ＬＯＰ ＭＥＮＴ
Ｖ ｏ １ ． ２ ４ Ｎｏ ． １
Ｊ ａ ｎ ． ２ ０ １ ４
基 于容 差关 系的不 完 备信 息 系统 的属 性 约简
ＹＡＮ Ｊ ｉ ａ －ｋ ａ ｉ ， Ｆ ＡＮ Ｍｉ ｎ， ＬＩ Ｕ Ｗｅ ｎ－ｑ ｉ ， ＹＥ Ｒｏ ｎ ｇ－ ｒ ｏ ｎ ｇ
（ Ｓ ｃ ｈ ｏ ｏ ｌ ｏ ｆ Ｓ ｃ ｉ ｅ ｎ ｃ ｅ ， Ｋ ｕ ｎ ｍｉ ｎ ｇ Ｕ ｎ ｉ ｖ ｅ ｒ ｓ ｉ ｔ ｙ ｏ ｆ Ｓ ｃ ｉ ｅ ｎ ｃ ｅ ａ ｎ ｄ Ｔ ｅ ｃ ｈ ｎ ｏ ｌ ｏ ｇ ｙ ， Ｋ ｕ ｎ ｍｉ ｎ ｇ ６ ５ ０ ５ ０ ０ ， Ｃ ｈ ｉ ｎ ａ ）
Ａｂｓ ｔ ｒ ａ ｃ ｔ ： Ｒｏ ｕ ｇ ｈ ｓ ｅ ｔ ｔ ｈ ｅ ｏ ｒ ｙ ｉ ｓ ａ ｋ ｉ ｎ ｄ ｏ ｆ ｅ ｆ ｆ ｅ ｃ ｔ ｉ ｖ ｅ ｔ ｏ ｏ ｌ ｆ ｏ ｒ ｄ ｅ ａ ｌ ｉ ｎ ｇ ｗｉ ｈ ｔ ｕ ｎ ｃ ｅ ｒ ｔ ａ ｉ ｎ ｔ ｙ ｋ ｎ ｏ ｗｌ ｅ ｄ ｇ ｅ ． Ａｔ ｔ ｒ ｉ ｂ ｕ ｔ ｅ ｒ ｅ ｄｕ ｃ ｉ ｔ ｏ ｎ ｉ ｓ ｏ ｎ ｅ ｏ ｆ ｈｅ ｔ ｍｏ ｓ ｔ ｉ ｍ— ｐ ｏ ｒ ｔ ａ ｎ ｔ ｃ ｏ ｎ ｔ ｅ ｎ ｔ ． Ｎｅ ｖ ｅ ｒ ｔ ｈ ｅ ｌ ｅ ｓ ｓ ， ｈｅ ｔ ｃ ｌ ａ ｓ ｓ ｉ ｃ ｌ ａ ｒ ｏ ｕ ｇ ｈ ｓ ｅ ｔ ｈｅ ｔ ｏ ｙ ｒ ｂ ａ ｓ ｅ ｄ ｏ ｎ ｅ ｑ ｕ ｉ ｖ ａ ｌ ｅ ｎ ｃ ｅ ｍｌ ａ ｉｏ ｔ ｎ ｈａ ｓ ｎ ｏ ｔ ｂｅ ｅ ｎ ａ ｐ ｐ ｌ ｉ ｅ ｄ ｆ ｏ ｒ ｔ ｈ ｅ ｉ ｎ ｃ ｏ ｍｐ ｌ ｅ ｔ ｅ ｉ ｎ ｏｒ ｆ ｍａ － ｔ ｉ ｏ ｎ ｓ ｙ ｓ ｔ ｅ ｍ ｗｈ ｉ ｃ ｈ ｓ ｏ ｍｅ ａ ｔ ｔ ｒ ｉ ｂｕ ｔ ｅ ｉ ｓ ｈｅ ｔ ｄ ｅ ｆ ａ ｕ ｌ ｔ ｖ ａ ｌ ｕ ｅ ． Ｔｈ ｅ ｄ ｅ ｉｎ ｆ ｉ ｉ ｔ ｏ ｎ ｈａ ｔ ｔ ｔｔ ａ ｒ ｉ ｂ ｕ ｔ ｅ ｓ ｒ ｅ ｄｕ ｃ ｔ ｉ ｏ ｎ ｏ ｆ ｉ ｎ ｃ ｏ ｍｐ ｌ ｅ ｅ ｔ ｉ ｎ ｆ ｏ ｒ ｍａ ｔ ｉ ｏ ｎ ｓ ｙ ｓ ｔ ｅ ｍ ｉ ｓ ｓ ｉ ｍｉ ｌ ａ ｒ ｔ ｏ ｈｅ ｔ ｃ ｌ ａ ｓ ｓ ｉ ｃ ｌ ａ ｒ ｏ ｕ ｇ ｈ ｓ ｅ ｔ ｂ ｃａ ｅ ｕｓ ｅ ｏ ｆ ｈｅ ｔ ｔ ｏ ｌ ｅ ｒ ａ ｎ ｃ ｅ ｒ ｅ ｌ ａ ｉ ｔ ｏ ｎ． Ｃａ ｎ ｅ ｘ ｐ ｎｄ ａ ｈｅ ｔ ｃ ｌ ａ ｓ ｓ ｉ ｃ ｌ ａ ｒ ｏ ｕ ｇ ｈ ｓ ｅ ｔ ｈｅ ｔ ｏ ｙ ｒ ｗｉ ｈ ｔ ｏｌ ｔ ｅ ｒ ｎｃ ａ ｅ ｅｌ ｒ ａ ｉ ｔ ｏ ｎ ． Ｉ ｎ ｈｉ ｔ ｓ ｐ ａ ｐｅ ｒ ， ｂ ｙ
信息量的不完备信息系统属性约简方法
信息量的不完备信息系统属性约简方法信息量的不完备信息系统属性约简方法不完备信息系统是指存在一些未知或不可知的属性的系统。
约简是在保留系统重要特征的前提下，去除一些冗余的特征以降低系统的复杂性。
在不完备信息系统中，属性约简是一种重要的方法。
下面介绍一种基于信息量的不完备信息系统属性约简方法。
信息量是指某一事件的不确定性程度，用信息熵来表示。
对于一个不完备信息系统来说，我们可以通过已知的属性信息和属性取值进行估算和推测，然后计算出每个未知属性的信息熵。
如果一个属性在已知属性的条件下其信息熵较小，那这个属性就有更大的概率是有用的属性。
用这种方法求解属性约简，可以使得约简结果更具有实际意义和解释性。
具体步骤如下：1. 将不完备信息系统分为两类：已知属性集和未知属性集。
其中已知属性集包含在一些实例中已知的属性，未知属性集包含在这些实例中未知或不可知的属性。
2. 对于每个未知属性，计算在已知属性的条件下的信息熵。
假设一个未知属性 Ai，对于系统中任意的实例 X，已知属性集为 K，未知属性集为 U，该未知属性的取值为 Vi，那么该未知属性在已知属性集 K 的条件下的信息熵为：H(Ai|K) = -∑ (P(X|K) * log2 P(X|K))其中，P(X|K) 是在已知属性集 K 的条件下，未知属性 Ai 的取值为 Vi 的概率，根据贝叶斯定理可得P(X|K) = P(V1|K) * P(V2|K) * … * P(Vn|K)V1, V2, …, Vn 分别为未知属性集 U 中的属性取值。
3. 对于每个未知属性，计算其信息增益。
信息增益表示该属性对系统的分类能力，加入该属性后能够使得不完备信息系统的熵减少的程度。
信息增益的计算公式为：Gain(Ai|K) = H(U|K) - H(Ai|K)其中，H(U|K) 是在已知属性集 K 的条件下未知属性集 U 的信息熵。
4. 对于所有未知属性，按照信息增益从大到小排序，选择信息增益最大的属性加入已知属性集 K。
基于包含度的不完备序信息系统属性约简的一种算法
ｌ
Ｄ（ （ ）Ａ Ｂ ）＝八Ｄ ］ ／ ｘ］ ） ＡＡ ／（ ） （ Ａ Ｉ 一
定 理 ２ １ 设 Ｌ ＝（ ， 是一个 不完 备序信 ． Ａ） 息 系 统 ，Ｂ Ａ，则 ＝ 当 且 仅 当 ， 于是
Ｄ（ Ａ） Ａ Ｂ） Ａ（ ／ （ ）＝ １ ．
证 明 （ ）当
文献标 识码 ： Ａ
０ 引 言
粗 糙集 理 论 是波 兰数 学 家 Ｚ Ｐｗａ ． ａ ｌｋ于 １８ ９２ 年提 出 的一 种处理 和分 析不精 确 、 不协 调 、 完备 、 不
不完备信息系统的信息熵 、 粗糙熵及知识粒度等不
确定 度量 ； 夺谦 等人 从信 息论 的角 度 ， 于互 信 苗 基
Ｃ Ｏ等人在 优势关 系下 定 义 了基 于分类 质量 的属 性
上 ， 出了一 种基于包含度 的属性约简算法 ； 提 最 后 ， 过实 例分 析表 明 ， 算法 能 得 到不完 备序 信 通 该
息 系统 的一个 约简 ．
１ 不 完 备 序 信 息 系统
定 义 １１ 形 式上 ，四元 组 Ｌ＝（ Ａ， ． Ｕ，
一
是
个信息系统 ， 中 表示对象 的非空有限集合， 其
＝ｕ。 是属性 口的值域 表示 Ｕ× ＋ 的一 Ａ．
称 为 论 域 ； 表 示 属 性 的 非 空 有 限 集 合 ； Ａ Ｖ 个信息函数 ， 它为每个对象的每个属性赋予一个信 息值 ， 即任意 的 口∈Ａ， ￡Ｕ ，）∈ ． 常也 口 通 用 Ｌ＝（ ，） ｕ Ａ 代替 Ｌ＝（ ， ， ＵＡ Ｖ Ｊ ． 在一个信息系统 中， 如果在某个属性值域上 建立了偏序关系 ， 则称这个属性为一个标准．当所 有的属性都为标准时 ， 该信息系统称为序信息系统
Ｄ（ （ ）Ａ Ｂ ）＝八Ｄ ］ ／ ｘ］ ） ＡＡ ／（ ） （ Ａ Ｉ 一
定 理 ２ １ 设 Ｌ ＝（ ， 是一个 不完 备序信 ． Ａ） 息 系 统 ，Ｂ Ａ，则 ＝ 当 且 仅 当 ， 于是
Ｄ（ Ａ） Ａ Ｂ） Ａ（ ／ （ ）＝ １ ．
证 明 （ ）当
文献标 识码 ： Ａ
０ 引 言
粗 糙集 理 论 是波 兰数 学 家 Ｚ Ｐｗａ ． ａ ｌｋ于 １８ ９２ 年提 出 的一 种处理 和分 析不精 确 、 不协 调 、 完备 、 不
不完备信息系统的信息熵 、 粗糙熵及知识粒度等不
确定 度量 ； 夺谦 等人 从信 息论 的角 度 ， 于互 信 苗 基
Ｃ Ｏ等人在 优势关 系下 定 义 了基 于分类 质量 的属 性
上 ， 出了一 种基于包含度 的属性约简算法 ； 提 最 后 ， 过实 例分 析表 明 ， 算法 能 得 到不完 备序 信 通 该
息 系统 的一个 约简 ．
１ 不 完 备 序 信 息 系统
定 义 １１ 形 式上 ，四元 组 Ｌ＝（ Ａ， ． Ｕ，
一
是
个信息系统 ， 中 表示对象 的非空有限集合， 其
＝ｕ。 是属性 口的值域 表示 Ｕ× ＋ 的一 Ａ．
称 为 论 域 ； 表 示 属 性 的 非 空 有 限 集 合 ； Ａ Ｖ 个信息函数 ， 它为每个对象的每个属性赋予一个信 息值 ， 即任意 的 口∈Ａ， ￡Ｕ ，）∈ ． 常也 口 通 用 Ｌ＝（ ，） ｕ Ａ 代替 Ｌ＝（ ， ， ＵＡ Ｖ Ｊ ． 在一个信息系统 中， 如果在某个属性值域上 建立了偏序关系 ， 则称这个属性为一个标准．当所 有的属性都为标准时 ， 该信息系统称为序信息系统
基于容差关系知识依赖的属性约简算法研究
Ａｂｓｔｒａｃｔ：Ｉｎｏｒｄｅｒｔｏｉｍｐｒｏｖｅｔｈｅａｂｉｌｉｔｙｏｆａｔｔｒｉｂｕｔｅｒｅｄｕｃｔｉｏｎｉｎｉｎｃｏｍｐｌｅｔｅｉｎｆｏｒｍａｔｉｏｎｓｙｓｔｅｍｓ，ｗｅｓｔｕｄｙｔｈｅ ｃｏｎｃｅｐｔｓｏｆｋｎｏｗｌｅｄｇｅｇｒａｎｕｌａｒｉｔｙａｎｄｋｎｏｗｌｅｄｇｅｄｅｐｅｎｄｅｎｃｅｂａｓｅｄｏｎｔｏｌｅｒａｎｃｅｒｅｌａｔｉｏｎ，ａｎｄｇｉｖｅａｎｅｗｄｅｆｉｎｉ ｔｉｏｎｏｆｋｎｏｗｌｅｄｇｅｇｒａｎｕｌａｒｉｔｙ．Ｔｈｅｎｔｈｅｐｒｏｐｅｒｔｉｅｓｏｆｔｗｏｋｉｎｄｓｏｆｄｅｐｅｎｄｅｎｃｉｅｓａｒｅｓｔｕｄｉｅｄａｎｄｖｅｒｉｆｉｅｄｂｙｅｘａｍ ｐｌｅｓ．Ｂｙｉｎｔｒｏｄｕｃｉｎｇｔｈｅｃｏｎｃｅｐｔｏｆｋｎｏｗｌｅｄｇｅｇｒａｎｕｌａｒｉｔｙ，ｔｈｅｉｍｐｏｒｔａｎｃｅｏｆａｔｔｒｉｂｕｔｅｓｉｎｔｈｅｉｎｆｏｒｍａｔｉｏｎｓｙｓｔｅｍ ｉｓｄｅｆｉｎｅｄ，ａｎｄｔｗｏａｌｇｏｒｉｔｈｍｓｏｆａｔｔｒｉｂｕｔｅｒｅｄｕｃｔｉｏｎａｒｅｐｒｏｐｏｓｅｄｂｙｕｓｉｎｇａｔｔｒｉｂｕｔｅｉｍｐｏｒｔａｎｃｅａｓｈｅｕｒｉｓｔｉｃｉｎｆｏｒ ｍａｔｉｏｎ．Ｏｎｅｓｔａｒｔｓｆｒｏｍｔｈｅｃｏｒｅａｔｔｒｉｂｕｔｅｓｅｔｕｓｉｎｇｔｈｅｂｏｔｔｏｍｕｐｍｅｔｈｏｄ，ａｎｄｔｈｅｏｔｈｅｒｆｒｏｍｔｈｅｗｈｏｌｅａｔｔｒｉｂｕｔｅ ｓｅｔｕｓｉｎｇｔｈｅｔｏｐｄｏｗｎｍｅｔｈｏｄ．Ｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｏｎ５ｓｅｔｓｏｆＵＣＩｄａｔａｓｅｔｓｓｈｏｗｔｈａｔ，ｆｒｏｍ ｔｈｅｒｅｄｕｃｔｉｏｎｏｆ ｎｕｍｂｅｒ，ｔｈｅａｌｇｏｒｉｔｈｍ ｉｓｌｅｓｓｔｈａｎｏｒｅｑｕａｌｔｏｔｈｅｒｅｓｕｌｔｏｆｔｈｅｎｕｍｂｅｒｏｆａｔｔｒｉｂｕｔｅｓｃｏｍｐａｒｅｄｗｉｔｈｏｔｈｅｒａｌｇｏ ｒｉｔｈｍｓ，ｆｒｏｍ ｔｈｅｐｅｒｓｐｅｃｔｉｖｅｏｆｃｌａｓｓｉｆｉｃａｔｉｏｎａｃｃｕｒａｃｙ，ｔｈｅａｌｇｏｒｉｔｈｍ ｆｒｏｍ ｔｈｅｋｅｒｎｅｌａｔｔｒｉｂｕｔｅｓｅｔｉｓｂｅｔｔｅｒ．Ｔｈｅ ｃｏｒｒｅｃｔｎｅｓｓａｎｄｆｅａｓｉｂｉｌｉｔｙｏｆｔｈｅａｌｇｏｒｉｔｈｍ ａｒｅｖｅｒｉｆｉｅｄｂｙｅｘｐｅｒｉｍｅｎｔｓ． Ｋｅｙｗｏｒｄｓ：ｉｎｃｏｍｐｌｅｔｅｉｎｆｏｒｍａｔｉｏｎｓｙｓｔｅｍ，ｔｏｌｅｒａｎｃｅｒｅｌａｔｉｏｎ，ｆｕｎｃｔｉｏｎａｌｄｅｐｅｎｄｅｎｃｙ，ａｔｔｒｉｂｕｔｅｒｅｄｕｃｔｉｏｎ
不完备信息系统中基于限制容差关系的属性约简方法
不完备信息系统中基于限制容差关系的属性约简方法王超;罗可【摘要】决策表核属性的确定往往是信息约简的基础,然而以往的核属性约简方法大多是针对完备信息系统的.将完备信息系统中的属性核与属性序约简算法延伸至不完备系统,提出一种不完备信息系统中基于限制容差关系的属性约简方法.该方法通过构造限制容差关系下决策表的改进分辨矩阵来求得核属性,并将非核属性按直观影响分类质量的能力排序,能够保证得到的约简结果是相对最小约简.通过实验比较证明该方法可行、有效.%The confirmation of core attribute of a decision table is always the basis of information reduction. However, most of the previous reduction methods in core attribute are for complete information system. Extending the reduction algorithm in core attribute and attribute order to incomplete information system, which was used in complete information system, this paper presented an attribute reduction algorithm based on limited tolerance relation in incomplete information system. This method obtained core attribute by constructing an improved discemable matrix of decision table in incomplete information system, and sorted the attributes which did not belong to core attribute by ability of affecting classification quality intuitively. Thus, the reduction result was ensured to be a relatively minimized reduction. This method is proved to be feasible and more effective through comparison.【期刊名称】《计算机应用》【年(卷),期】2011(031)012【总页数】4页(P3236-3239)【关键词】不完备信息系统;属性约简;限制容差关系;核属性【作者】王超;罗可【作者单位】长沙理工大学计算机与通信工程学院,长沙 410114;长沙理工大学计算机与通信工程学院,长沙 410114【正文语种】中文【中图分类】TP18;TP311.130 引言属性约简一直是Rough集理论研究的核心内容之一[1－2]。
基于可调节多粒度粗糙集的不完备信息系统属性约简
基于可调节多粒度粗糙集的不完备信息系统属性约简
在数据处理过程中,数据集有时是带噪声的或者是缺省的,因此需要能处理不精确,不确定型数据的理论和方法.粗糙集理论正是满足这种要求的数学工具.目前粗糙集理论被广泛地应用在粒计算,机器学习,人工智能和数据挖掘等领域.属性约简问题是粗糙集理论中最核心的内容之一,现有的信息系统的约简算法主要有基于属性重要度的属性约简算法;基于差别矩阵的属性约简算法;基于信息熵的属性约简算法.然而,随着计算机和数据采集技术的进步,数据的积累无论是在数据对象个数上还是在数据维度上都在迅速增长.由此而导致算法的复杂度会随着数据规模的增大而越来越高,因此研究更有效的属性约简方法具有一定的现实意义.本文的主要工作如下:基于全局的可调节多粒度粗糙集模型在属性约简中因计算复杂度过高而导致其应用性不强.本文以不完备信息系统的多粒度粗糙集模型为基础,给出了基于信息水平的局部可调节多粒度粗糙集模型,并进一步给出了下近似质量,属性内、外重要度的定义.最后,本文研究了基于不完备信息系统的多粒度粗糙集的局部属性约简和全局约简的区别和联系,并给出了相关的启发式算法.。
不完备信息系统的属性约简算法的开题报告
不完备信息系统的属性约简算法的开题报告一、选题背景信息系统是指事物进行解释和研究的任何对象或内容，它是现代计算机技术所应用的重点之一，通过对信息系统进行分析和规划，可以帮助人们更好的实现信息的有效管理和利用。
在信息系统的分析过程中，属性约简一般涉及到的是属性约简问题。
在信息系统中，属性数量可能是非常庞大的，而这些属性中很多都是冗余或者不必要的。
属性约简算法的作用就是通过选择最重要的属性，将系统中不必要和冗余的属性进行消除，从而降低算法的时间和空间复杂度，提高算法的准确性和可用性。
在很多实际问题中，由于缺乏足够的信息或者现有的信息不能完全描述系统本身的特点，因此导致信息系统不完备的情况，这时候需要使用不完备信息系统的属性约简算法来对系统进行优化。
二、选题意义随着现代社会的不断发展，信息化已经成为当今社会的主要发展趋势。
信息系统的优化和管理对于保持信息的可靠性和安全性起到了至关重要的作用，因此信息系统的属性约简算法有着广泛的应用领域，比如在分类和预测、数据挖掘和聚类等方面都有着重要的应用。
而对于不完备信息系统的属性约简算法的研究，在解决实际问题中有着很大的作用。
为了更好的实现信息的分析和规划，需要选择合适的属性约简算法，对信息系统进行优化和管理，从而提高信息系统的效率和准确性。
因此，对于不完备信息系统的属性约简算法的研究和开发，有着非常重要的意义。
三、研究方法本篇论文主要通过文献综述和实例分析两种方法来研究不完备信息系统的属性约简算法。
文献综述方法通过对相关文献的检索和归纳，来获取关于属性约简算法的知识和研究成果，从而对不完备信息系统的属性约简算法进行深入的研究和分析。
实例分析方法通过选择实际的数据集来进行分析和研究，通过自主编程实现不完备信息系统的属性约简算法，并对算法进行实验验证和对比分析，从而对算法的性能和效果进行评估和改进。
四、预期结果通过本次研究，可以预期达到以下的结果：1. 对不完备信息系统的属性约简算法进行深入研究，掌握其原理和特点，为信息系统的优化和管理提供理论支持。
不完备信息系统中基于限制容差关系的属性约简方法
Ｗ ＡＮＧ Ｃｈａ ． ＬＵＯ ｏ Ｋｅ
（ｎｔｕｅｏ ｏ ｐ ｔ ｎ ｏ ｍｕ ｉ ｔ ｎＥ ｇｎｅｉ ，Ｃ ａｇｈ ｎｖｒｔ ｏ Ｓｉ ｃｓ ｎ ｅｈｏｏｙ ｈ ｎｓａＨ ｎ ｎ４０ １，Ｃ ｉ ） Ｉ．ｉ ｔ ｆＣ ｍ ｕｅ ａ ｄＣ ｍ ｎｃ ｉ ｎｉｅｒ ｇ ｈ ｎｓａＵ ｉ ｓｙｆ ｃ ｎｅ ａ ｄＴｃｎｌ ，Ｃ ａｇｈ ｕａ １０ ４ ｈｎ ￣ｔ ｒ ａｏ ｎ ｅ ｉ ｅ ｇ ａ
Ａｂ ｔ ａ ｔ ｈ ｏ ｆ ｍａｉｎ ｏ ｏ ｅ ａ ｔ ｂ ｔ ｆａ ｄ ｃ ｓｏ ａ ｌ ｓ ａｗａ ｓ ｔｅ ｂ ｓｓ ｏ ｎ ｏ ｍａｉｎ ｒ ｄ ｃｉｎ Ｈｏ ｖ ｒ ｓｒ ｃ ：Ｔ ｅ ｃ ｎ ｒ ｔ ｆｃ ｒ ｔ ｉ ｕｅ ｏ ｅ ｉｉｎ ｔ ｂ ｅ ｉ ｌ ｙ ｈ ａ ｉ ｆ ｉｆ ｒ ｔ ｅ ｕ ｔ ． ｉ ｏ ｒ ｏ ｏ ｗｅ ｅ ， ｍｏ ｔ ｆ ｈ ｒ ｖｏ ｓ ｒｄ ｃｉ ｎ ｍｅｈ ｄ ｎ ｃ ｒ ｔ ｉｕ ｅ ａ ｅｆ ｒｃ ｍｐｅ ｅｉ ｆｒ ｔ ｎ ｓ ｓ ｍ．Ｅ ｔｎ ｉ ｇｔ ｅ ｒ ｄ ｃ ｉｎ ａｇ ｒ ｈ ｓ ｅ ｐ ｅ ｉｕ ｅ ｕ ｔ ｔ ｏ ｓｉ ｏ ｅａｔ ｂ ｔ ｒ ｏ ｏ ｌｔ ｎ ｏｍａｉ ｙ ｔ ｏｔ ｏ ｒ ｏ ｅ ｘｅ ｄｎ ｈ ｅ ｕ ｔ ｌｏ ｉ ｍ ｏ ｔ ｉ ｏ ｅ ａｔｉｕ ｅ ａ ｄ ａｔ ｂ ｔ ｒ ｅ ｏ ｉ ｃ ｍｐ ｅｅ ｉｆ ｒ ｔ ｎ ｓ ｓｅ ｎ ｃ ｒ ｔ ｂ ｔ ｎ ｔ ｉ ｕｅ ｏ ｄ ｒ ｔ ｎ ｏ ｌ ｔ ｎ ｏ ｍａｉ ｙ ｔ ｍ， ｗｈｃ ｓ ｕ ｅ ｎ ｃ ｍｐ ｅｅ ｉｆ ｒ ｔ ｎ ｓ ｓｅ ｒ ｒ ｏ ｉｈ ｗａ ｓ ｄ ｉ ｏ ｌ ｔ ｎ ｏ ｍａｉ ｙ ｔ ｍ， ｔ ｉ ｏ ｈｓ ｐ ｐ ｒｐ ｅ ｅ ｔ ｄ ａ ｔ ｂ ｔ ｅ ｕ ｔ ｎ ａｇ ｒ ｈ ｂ ｓ ｄ ｏ ｉ ｔｄ ｔｌｒ ｎ ｅ ｒ ｌｔ ｎ ｉ ｎ ｏ ｌｔ ｎ ｏ ｍａｉ ｎ ｓ ｓｅ ａ ｅ ｒ ｓ ｎ ｅ ｎ ａｔ ｕ ｅ ｒｄ ｃｉ ｌｏ ｉ ｍ ａ ｅ ｎ ｌ ｅ ｏ ｅａ ｃ ｅａ ｉ ｎ ｉ ｃ ｍｐ ｅｅ ｉｆ ｒ ｔ ｙ ｔ ｍ．Ｔ ｉ ｉ ｒ ｏ ｔ ｍｉ ｏ ｏ ｈｓ ｍｅ ｈ ｄ ｏ ｔｉ ｅ ｏ ｅ ａｔ ｂ ｔ ｙ ｃ ｎ ｔｕ ｔ ｇ ａ ｍｐ ｏ ｅ ｉ ｅ ｎ ｂ ｅ ｍａｒ ｆ ｄ ｃ ｓ ｎ ｔｂ ｅ ｉ ｎ ｏ ｌ ｔ ｎｏ ｍａｉｎ ｔ ｏ ｂ ａ ｎ ｄ ｃ ｒ ｔ ｉ ｕ ｅ ｂ ｏ ｓｒ ｃｉ ｎ ｉ ｒ ｖ ｄ ｄ ｓ ｒ ａ ｌ ｒ ｎ ｃ ｔ ｘ ｏ ｅ ｉｉ ａ ｌ ｎ ｉ ｃ ｍｐ ｅｅ ｉｆ ｒ ｔ ｉ ｏ ｏ ｓ ｓ ｍ，ａ ｄ ｓ ｒ ｄ ｔ ｅ ａｔ ｂ ｔ ｓｗｈｃ ｉ ｏ ｂ ｌ ｎ ｏ ｃ ｒ ｔ ｉ ｕｅ ｂ ｂｌ ｙ ｏ ｆ ｃｉ ｇｃ ａ ｓｆ ａｉｎ ｑ ａ ｉ ｎｕ ｔ ｅｙ ｙｔ ｅ ｎ ｏ ｔ ｈ ｔ ｉ ｕ ｅ ｉｈ ｄ ｄ ｎ ｔ ｅｏ ｇ ｔ ｏ ｅ ａｔ ｂ ｔ ｙ ａ ｉ ｔ ｆａｆ ｔ ｌ ｓ ｉ ｃ ｔ ｕ ｌ ｙ ｉｔ ｉ ｖ ｌ ． ｅ ｒ ｒ ｉ ｅ ｎ ｉ ｏ ｔ ｉ Ｔ ｕ ， ｔ ｅ ｒ ｄ ｃ ｉｎ ｒ ｓ ｌ ｗ ｓ ｅ ｓ ｒ ｄ ｔ ｅ ａ ｒ ｌｔ ｅｙ ｍｉｉ ｚ ｄ ｒ ｄ ｃｉｎ ｈ ｓ ｈ ｅ ｕ ｔ ｅ ｕ ｔ ａ ｎ ｕ ｅ ｏ ｂ ｅａ ｉ ｌ ｎ ｍｉｅ ｅ ｕ ｔ ．Ｔ ｉ ｍｅｈ ｄ ｉ ｐ ｏ ｅ ｏ ｂ ｅ ｓ ｌ ａ ｄ ｍｏ ｅ ｏ ｖ ｏ ｈ ｓ ｔ ｏ ｓ ｒ ｖ ｄ ｔ ｅ ｆ ａ ｉ ｅ ｎ ｒ ｂ
（ｎｔｕｅｏ ｏ ｐ ｔ ｎ ｏ ｍｕ ｉ ｔ ｎＥ ｇｎｅｉ ，Ｃ ａｇｈ ｎｖｒｔ ｏ Ｓｉ ｃｓ ｎ ｅｈｏｏｙ ｈ ｎｓａＨ ｎ ｎ４０ １，Ｃ ｉ ） Ｉ．ｉ ｔ ｆＣ ｍ ｕｅ ａ ｄＣ ｍ ｎｃ ｉ ｎｉｅｒ ｇ ｈ ｎｓａＵ ｉ ｓｙｆ ｃ ｎｅ ａ ｄＴｃｎｌ ，Ｃ ａｇｈ ｕａ １０ ４ ｈｎ ￣ｔ ｒ ａｏ ｎ ｅ ｉ ｅ ｇ ａ
Ａｂ ｔ ａ ｔ ｈ ｏ ｆ ｍａｉｎ ｏ ｏ ｅ ａ ｔ ｂ ｔ ｆａ ｄ ｃ ｓｏ ａ ｌ ｓ ａｗａ ｓ ｔｅ ｂ ｓｓ ｏ ｎ ｏ ｍａｉｎ ｒ ｄ ｃｉｎ Ｈｏ ｖ ｒ ｓｒ ｃ ：Ｔ ｅ ｃ ｎ ｒ ｔ ｆｃ ｒ ｔ ｉ ｕｅ ｏ ｅ ｉｉｎ ｔ ｂ ｅ ｉ ｌ ｙ ｈ ａ ｉ ｆ ｉｆ ｒ ｔ ｅ ｕ ｔ ． ｉ ｏ ｒ ｏ ｏ ｗｅ ｅ ， ｍｏ ｔ ｆ ｈ ｒ ｖｏ ｓ ｒｄ ｃｉ ｎ ｍｅｈ ｄ ｎ ｃ ｒ ｔ ｉｕ ｅ ａ ｅｆ ｒｃ ｍｐｅ ｅｉ ｆｒ ｔ ｎ ｓ ｓ ｍ．Ｅ ｔｎ ｉ ｇｔ ｅ ｒ ｄ ｃ ｉｎ ａｇ ｒ ｈ ｓ ｅ ｐ ｅ ｉｕ ｅ ｕ ｔ ｔ ｏ ｓｉ ｏ ｅａｔ ｂ ｔ ｒ ｏ ｏ ｌｔ ｎ ｏｍａｉ ｙ ｔ ｏｔ ｏ ｒ ｏ ｅ ｘｅ ｄｎ ｈ ｅ ｕ ｔ ｌｏ ｉ ｍ ｏ ｔ ｉ ｏ ｅ ａｔｉｕ ｅ ａ ｄ ａｔ ｂ ｔ ｒ ｅ ｏ ｉ ｃ ｍｐ ｅｅ ｉｆ ｒ ｔ ｎ ｓ ｓｅ ｎ ｃ ｒ ｔ ｂ ｔ ｎ ｔ ｉ ｕｅ ｏ ｄ ｒ ｔ ｎ ｏ ｌ ｔ ｎ ｏ ｍａｉ ｙ ｔ ｍ， ｗｈｃ ｓ ｕ ｅ ｎ ｃ ｍｐ ｅｅ ｉｆ ｒ ｔ ｎ ｓ ｓｅ ｒ ｒ ｏ ｉｈ ｗａ ｓ ｄ ｉ ｏ ｌ ｔ ｎ ｏ ｍａｉ ｙ ｔ ｍ， ｔ ｉ ｏ ｈｓ ｐ ｐ ｒｐ ｅ ｅ ｔ ｄ ａ ｔ ｂ ｔ ｅ ｕ ｔ ｎ ａｇ ｒ ｈ ｂ ｓ ｄ ｏ ｉ ｔｄ ｔｌｒ ｎ ｅ ｒ ｌｔ ｎ ｉ ｎ ｏ ｌｔ ｎ ｏ ｍａｉ ｎ ｓ ｓｅ ａ ｅ ｒ ｓ ｎ ｅ ｎ ａｔ ｕ ｅ ｒｄ ｃｉ ｌｏ ｉ ｍ ａ ｅ ｎ ｌ ｅ ｏ ｅａ ｃ ｅａ ｉ ｎ ｉ ｃ ｍｐ ｅｅ ｉｆ ｒ ｔ ｙ ｔ ｍ．Ｔ ｉ ｉ ｒ ｏ ｔ ｍｉ ｏ ｏ ｈｓ ｍｅ ｈ ｄ ｏ ｔｉ ｅ ｏ ｅ ａｔ ｂ ｔ ｙ ｃ ｎ ｔｕ ｔ ｇ ａ ｍｐ ｏ ｅ ｉ ｅ ｎ ｂ ｅ ｍａｒ ｆ ｄ ｃ ｓ ｎ ｔｂ ｅ ｉ ｎ ｏ ｌ ｔ ｎｏ ｍａｉｎ ｔ ｏ ｂ ａ ｎ ｄ ｃ ｒ ｔ ｉ ｕ ｅ ｂ ｏ ｓｒ ｃｉ ｎ ｉ ｒ ｖ ｄ ｄ ｓ ｒ ａ ｌ ｒ ｎ ｃ ｔ ｘ ｏ ｅ ｉｉ ａ ｌ ｎ ｉ ｃ ｍｐ ｅｅ ｉｆ ｒ ｔ ｉ ｏ ｏ ｓ ｓ ｍ，ａ ｄ ｓ ｒ ｄ ｔ ｅ ａｔ ｂ ｔ ｓｗｈｃ ｉ ｏ ｂ ｌ ｎ ｏ ｃ ｒ ｔ ｉ ｕｅ ｂ ｂｌ ｙ ｏ ｆ ｃｉ ｇｃ ａ ｓｆ ａｉｎ ｑ ａ ｉ ｎｕ ｔ ｅｙ ｙｔ ｅ ｎ ｏ ｔ ｈ ｔ ｉ ｕ ｅ ｉｈ ｄ ｄ ｎ ｔ ｅｏ ｇ ｔ ｏ ｅ ａｔ ｂ ｔ ｙ ａ ｉ ｔ ｆａｆ ｔ ｌ ｓ ｉ ｃ ｔ ｕ ｌ ｙ ｉｔ ｉ ｖ ｌ ． ｅ ｒ ｒ ｉ ｅ ｎ ｉ ｏ ｔ ｉ Ｔ ｕ ， ｔ ｅ ｒ ｄ ｃ ｉｎ ｒ ｓ ｌ ｗ ｓ ｅ ｓ ｒ ｄ ｔ ｅ ａ ｒ ｌｔ ｅｙ ｍｉｉ ｚ ｄ ｒ ｄ ｃｉｎ ｈ ｓ ｈ ｅ ｕ ｔ ｅ ｕ ｔ ａ ｎ ｕ ｅ ｏ ｂ ｅａ ｉ ｌ ｎ ｍｉｅ ｅ ｕ ｔ ．Ｔ ｉ ｍｅｈ ｄ ｉ ｐ ｏ ｅ ｏ ｂ ｅ ｓ ｌ ａ ｄ ｍｏ ｅ ｏ ｖ ｏ ｈ ｓ ｔ ｏ ｓ ｒ ｖ ｄ ｔ ｅ ｆ ａ ｉ ｅ ｎ ｒ ｂ
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
Keywords
〇 引 言
R o u g h set
Attribute reduction
Incomplete information system
Compatible class
象属性值是未知的。这种数据缺失会影响粗糙集理论 向实用化方向推广。 为了解决不完备信息系统对粗糙集理论应用化的 粗糖集理论[14]是 由 波 兰 数 学 家 P a w l a k 教授于
第 3 4 卷第4 期
2017年4 月
计算机应用与软件
C o m p u t e r Applications an d Software
VoL34
No. 4
Apr. 2 0 1 7
基于容差计算的非完备信息系统属性约简算法
梁宝华
( 巢 湖 学 院 信 息 工 程 学 院 安 徽 合 肥 238000)
数据的数学工具。属性约简是粗糖集理论研究的重要 内容之一， 指在不影响原知识表达能力的情况下， 通过 消除冗余属性的方法， 从而获得较简洁的知识表达。 经典的粗糙集理论在完备信息系统中已有大量的研 究， 提出了基于正区域、 基于差别矩阵、 基于信息熵及 启发式属性约简算法[3_5’ 14_19]。然 而 在 现 实 生 活 中 ， 由于对数据的理解、 获取方法的限制等不可控因素， 使 得实际处理的数据是一个不完备信息完全、 不精确和模糊性
影响， 研究者们利用相容关系[6]、 相似 关 系 等 ， 给出一 系列有效的属性约简算法， 如 文 献 [7 ]给出了差别矩 阵的二进制形式， 文 献 [8 - 1 0 ] 提出相容关系相似矩 阵并给出一种不完备决策表的属性约简算法。不完备 决策表的属性约简算法多数以“ 信息量” [ 1 °]为启发式 信息， 张等在文献[11 ] 中提出 一 些 改 进 方 法 ， 经研究 发现， 文 献 [11 ]存 在 大 量 重 复 扫 描 数 据 对 象 的 不 足 。 为了减少扫描数据的次数， 无需大量空间存储相容类 信息， 本文根据相容类元素间的对称性、 自反性特征， 提出一种快速计算相容信息量的方法， 有效提高属性
收稿日期 :2016 - 03 - 3 0 。安徽省省级质量工程项目（ 2013tSZy31) ;安徽省高等学校省级自然科学研究项目（ KJ2013Z231) 。 梁 宝 华 ,副 教 授 ， 主研领域 :粗 糖 集 ， 数据 挖掘。
300
计算机应用与软件
2017 年
约简效率。最后通过实例及实验验证算法的有效性和 正确性。
U I ) and
reduces the space to 0 ( I
C II U I)
. Finally, the examples an d experimental analysis
s h o w that the proposed algorithm is efficient a n d feasible.
表 1 不完备决策
U
1 2 3 4 5 6 7 8 r al(l)
a\
1 1 2
a2
1 1
a3
1 1
a4
1 2 1 2 2 1 1 1 =|1,2,4,7|
D
1 1 2 1 1 3 1 2
1
相关概念
设信息系统 S = ( f /， 4， F， /)， 其 中 f/为 论 域 =
氺
1 1
氺
2
氺
C l I f/l )
。
最后， 通过实例和实验分析并验证了算法的有效性和可行性。
关键词
中图分类号
粗糙集属性约简非完备信息系统相容类
TP181
文献标识码
A
DOI ： 10. 3969/j. issn. 1000-386x. 2017. 0 4 . 0 5 1
ATTRIBUTE REDUCTION ALGORITHM FOR INCOMPLETE INFORMATION SYSTEM BASED ON TOLERANCE COMPUTATION
relation to c o m p u t e the a m o u n t of information, but this kind of algorithm co ns u m e s a large a m o u n t of time computing tolerance, which leads to the quality of attribute reduction a n d the time an d space complexity are not ideal. In order to improve the computation efficiency of the tolerance class effectively, a formula for calculating the equivalent information of the compatible class is introduced. Based on it, an attribute reduction algorithm is propos ed, which reduces the time complexity to 0 ( I C I 2 I
摘要
对于有缺损值的非完备信息系统约简， 多数算法利用容差关系求信息量， 但此类算法需消耗大量时间
计算容差， 导致属性约简质量、 消耗的时间及空间复杂度均不理想。为了有效提高求容差类计算效率， 引入一个 与相容类信息量等价的计算公式。以此为基础， 提出一种属性约简算法， 使时间复杂度降为 〇(l C I 2 I f / l ) , 空间 降 为 0(1
Liang B a o h u a
{Information Engineering Institute ,Chaohu University,Hefei 238000, Anhui, China)
Abstract
For incomplete information system reduction with defective values, most algorithms use the tolerance