基于粗糙集的符号与数值属性的快速约简算法

基于 等价 关系的经 典粗糙集 是在保持知识系统分类能力 不变的条件下 ， 通过求取核 与约简挖掘出信息系统 中潜在 的、 简洁的知识，从而为知识获取提供 了一套 全新 的方法。但对 于实际问题等价关系要求过于严格 ，如要描述一个对象通常 是通 过该对象 的一些属性 ，这些属性 中有 的是单值属性 ，而 有些则为多值属性 。单值属性对应论域 上的一个等价关系 ， 而多值属性则对应论域 上的一个相似关系 （ 满足 自反性和对 称性）。另外 ，在数据收集时可能不知道某属性 的具体值 ， 而只知道 它町能取几个值之 中的一个 ，即 多值粗糙 集 ，这也 是相似关系 ；还有 ，由于数据测最 的误差 、对数据理解或获 取的限制等原 因，使得在知识获取时可能存在对象 的一些属 性值未知 ，即知识 系统有空值或缺省值 ，这时面临 的是不完
ｄ ｓ ｅ ｎ ｂ ｅａ ｄ ｓｍ ｉ ｒｍａ ｒｘ ａ ｅ ｄ ｆｎ ｄ ｉ ｈ ｉ ｌ ｒｉ ｔ ｒ ｔ ｎ ｓ ｔｍ ｓ Ａｎ ａ ｅ ｎ ｉ ｔ ｅ ａ ｇ ｒｔ ｍ ｆａ ｔｉ ｕ ｅｒ ｄｕ ｔｏ ｎ ｏ ｅ ｉ ｉ ｌｒ ｉ ｃ ｒ ｉ ｌ ｎ ｉ ｌ ｔｉ ｒ ｅ ｉ ｅ ｔ ｅ ｓ ｍｉ ｎ ｏ ｍａ ｉ ｙｓｅ ． ｄ ｂ ｓ ｄ ｏ ｔ ｈ ｌ ｏ ｉ ａ ｎ ａ ｏ ， ｈ ｏ ｔ ｂ ｔ ｅ ｃ ｉ ｎ ａ ｄ ｃ ｒ ｎ ｓｍｉａ ｒ
维普资讯
第 ３ 卷 第 １ 期 ２ Ｏ
Ｉ Ｌ３ １ ２ ｏ
・
计
算 机
工
程
Байду номын сангаас
２０ ０ ６年 ５月
Ｍ ａｙ ２０ ６ ０
Ｄ
Ｃｏ ｍｐ ｔ ｒＥｎ ｉ ｅ ｒｎ ｕ ｅ ｇｎ ｅ ｉ ｇ
软件技术与数据库 ・

Ｌｉ Ｋａ Ｌｉ ｓ ｕ Ｗ ａ ｇ Ｌｅ ｎ ｕ Ｙｕ ｈ ｎ ｉ
（ ｅ ａ ｍｅ ｔｏ ｏ ｐ ｔ ｃｅｃ ｎ ｎｉｅｒ ｇ Ｂ ｒｎ ｎｔｕｅ ｏ ｅｈ ｏ ｇ ，ｅｊ ｇ １０ ８ ） Ｄ ｐ ｒ ｎ ｆＣ ｍ ｕ ｒＳ ｉ ｅａ ｄ Ｅ ｇｎ ｅ ｎ ， ｅ ｉｇ Ｉｓ ｔｔ ｆＴ ｃ ｎｌ ｙ Ｂ ｉｎ ０ ０ １ ｔ ｅ ｎ ｉ ｉ ｏ ｉ
ｔｒｕ ｈ ｅ ｎ ｉｏ ａ ｅ ｔ ｐ ．ｈ ｅ ｔａｔｂ ｔ ｒｄ ｃｉｎ ｓ ｔｅ ｅ ｉｈ ａｕ ｉ ｉ ｎｍｕ ｏ ｖ ｒｇ ｏ ｅｅ ａ ｃ ｈｏ ｇ ｏ ｄｔ ｎ ｌ ｎｒ ｙＴ ｅ ｂ ｓ ｔ ｉｕｅ ｅ ｕ ｔ ｉ ｈ ｓｔｗｈｃ ｖ ｌｅ ｓ ｔｅ ｍｉｉ ｍ ｆ ａｅａ ｅ ｆ ｒｌｖ ｎ ｅ ｌ ｏ ｒ ｏ ｌ ｏ ｔ ｂ ｔｓＴ ｅ ｘ ｅｉ ｎ ｓ ｏ ｓ ｈ ｔ ｔ ａ ｇｔ ｅｔｒ ｆ ｃｉｉ ．ｉａｌ ｉ ｅ ｒｄ ｃｉｎ ｅ ｕｔ ｏ Ｕ ｆ ａｌ ｕｅ ｈ ｅ ｐ ｒ ｉ ｆ ｍｅ ｔ ｈ ｗ ｔａ ｉ ｃ ｎ ｅ ｂ ｔ ｅ ｅ ｔ ｔ Ｆｎ ｌ ｔ ｔ ｅ ｕ ｔ ｒｓ ｌ ｆ ＣＩ 山 ｈｂ ８ ｓ ｅ ｖｙ ｙ． ｇ ｏ ｓ Ｌｎｅ
， ．
ｉ ｏ ｔ ｎ ｔｅｒ， ｅ ａｅ ｅ ｔ ｂ ￣ ｒｄ ｃｉ ｅ ｙ ｉ ｍｉｉｂ ａｒ ，ｎ ｏ ｐ ｔ ｒｌ ａｃ ｔ￣ｕｅ ｎ ｒ ｉ ｈｏｙｔ ｐｐｒ ｇｔ ａ ｆ ｕ ｅｕ ｔ ｎ ｓｔｂ ｄ ｆ ｍａ ｏ －ｈ ｓ ｉ ｏ ￣ｅ ｂｌ ＇ｍ ｔｘ ａｄ ｅｍ ｕ￣ ｅ ｖｎｅ ｏ ａ ｃ ｔｓ ｉ ｉ ｅ ｆ ｔ
１ 引言
粗 糙 集 （ ｏ ｇ ｔＳｔ理 论 是 一 种 处理 模 糊 和不 确 定 知 识 的 Ｒ ｕｈ ｅ） 数 学 工 具 ， 早 由波 兰数 学 家 ＺＰ ｗａ 最 ａ１ｋ在 １８ ９ ２年提 出 的『 ” 。它 已经 在 数 据 挖 掘 人 智 能 、 式 识 别 与 分 类 等 领 域 获 得 了较 模 广泛 的应 用叩 ４１ 性 约 简 是 Ｒ ｕ ｈ Ｓｔ 论 研 究 的一 个 核 心 ’ ３ 属 ｏ ｇ ｅ 理 内容 。 们 希 望 找 到 最 佳属 性 约 简 。 而 Ｗｏ ｇ ．． 和 Ｚａｋ ． 人 然 ｎ ＳＫＭ ｌ ｏ ｒ Ｗ 已经 证 明它 是 Ｎ － ａ 问 题Ｈ 因 而 目前 还 没 有高 教 的最 佳 Ｐ ｈ￣ 属 性 约简 算 法 。 过 ． 在实 际 应 用 中 ， 求 得 到 相 对属 性约 简 就 要 可 了 许 多研 究人 员 已提 出 了属性 约 简 算 法 １ ８。 目前许 多研 究人 员在 对 属 性 约 简 的研 究 中 ． 约 简 结 果 的 将 标 准定 为 约 简 后 属 性 数 最 少 ． 者 是 得 到 的 规 则 最 简 ， 约 简 或 或 量 最 大 。但 从 数 据 库 理 论 的 角 度 考虑 ， 性 的冗 余 、 性 间 的 属 属 依 赖 要 尽 可 能 地 小 。正 是 基 于这 些 ， 文 利用 Ｒ ｕ ｈＳ ｔ 论 ， 该 ｏ ｇ 理 ｅ

例
对于上表来说，U中有四个对象（概念），而现 在条件集合中只有一个属性，对于U1和U2来说， 它们的p不同所以可以通过p来区分，即u1,u2在p 下可区分；而U2和U3虽然是不同的对象但是在P 下却是相同的，即在p下不可区分，就成为不可 区分
粗糙集：
一个集合若恰好等于基本集的任意并集称为一个清晰 （crisp）集（精确集），否则称为粗糙（rough）集（不 精确集）。 解释：都可区分的是清晰集，有不可区分的对象为粗糙 集 主要特点:以不完全信息或知识去处理一些不分明现象的 能力,或依据观察、度量到的某些不精确的结果而进行分 类数据的能力. 粗糙集体现了集合中元素间的不可区分性. 主要优势:它不需要提供问题所需处理的数据集合之外的 任何先验知识,而且与处理其它不确定性问题的理论有很 强的互补性.
粗糙集理论所处理的问题
•不确定或不精确知识的表达; •经验学习并从经验中获取知识; •不一致信息的分析; •根据不确定,不完整的知识进行推理; •在保留信息的前提下进行数据化简; •近似模式分类; •识别并评估数据之间的依赖关系
三、粗糙集的应用
粗糙集理论在许多领域得到了应用： ①临床医疗诊断；
②电力系统和其他工业过程故障诊断；
3. 如果P中的任何一条属性都是不 可简约的，那么就称P是独立的 解释：P是独立的说明P中的任何一个属性都是必 不可少的，它独立的表达一个系统分类的特征。
属性约简的算法分析：
初始状态：所有数据已存入数据库(以下为模拟数据)
u 1 2 3 4 5 6
a 1 1 0 1 1 2
b 0 0 0 1 1 1
集合O 的下逼近(即正区) 为 I 3 (O ) = PO S (O ) = {刘保,赵 凯} 集合O 的负区为 N EG (O ) = {李得} 集合O 的边界区为 BND (O ) = {王治, 马丽} 集合O 的上逼近为 I 3 (O ) = PO S (O ) + BND (O ) = {刘保,赵凯,王治,马 丽} 根据表1, 可以归纳出下面几条规则, 揭示了教育程度与 是否能找到好工作之间的关 RUL E 1: IF (教育程度= 大学) OR (教育程度= 博士) THEN (可以找到好工作) RUL E 2: IF (教育程度= 小学) THEN (找不到好工作) RUL E 3: IF (教育程度= 高中) THEN (可能找到好工作)

｛） ｄ 表示 。 Ｂ Ｃ Ｙ ，ＥＵ ， ） 若 Ｃ ， ｘＹ ，≠ｙ 称二 元关 系ＩＤ （ ，ｄ ） ＿ Ｎ ＝ Ｂ ｛｝＝
｛ ，） Ｕ Ｕ Ｉ （）ｄ ｙ 或者口 Ｂ，（）Ⅱｙ ｝ （ Ｙ ∈ ｘ ｄ ＝ （ ） ∈ 口 ＝ （）为不可分辨
关系。
１ ． 粗 糙 集 ２
京 ： 子 工 业 出 社 ．０ ８ 电 ２ｏ ． （ 任编 辑 ： 责 王 钊）
［ ］ 杜 芳 芳． 析基 于 Ｗｅ １ 浅 ｂ数 据 挖 掘 的 电子 商务 网站 架构 ［］电子 Ｊ．
商务 ．０ ０ ２ ． ２ １（ ）
［ ］ 苗夺谦 ， 道 国． ２ 李 粗糙 集理 论 、 法 与应 用 ［ ． 算 Ｍ］ 北京 ： 清华 大 学 出
性口∈Ａ的值域
。 一 单 射 ， 论 域 ｕ中的 任一 元 素取 属 为 使
性。 Ｖ 中的某 一 唯一 值 。 在 Ａ由条件 属性 集 合Ｃ 决策 属性 集合 和 Ｄ组 成， 和Ｄ满 足 ＣＬＤ Ａ， Ｃ Ｊ ＝ ＣＮＤ ｄ，则 称Ｓ 决策 系 统 ，用（ ＝？ 为
ＣｕＤ） 示 ； 表 当决 策 属 性 集 合 只 有 一 个 元 素 时 ， 常 用（ 也 ＣＵ
＿
方 法４算术平 均最小 法 ：
负 域 ，ｎ （ ＝ 一 Ｘ成 为 的曰边 界 域 。 ｂ ） Ｂ
＿
公 ）＿宰 式 （ ： ， ＿ Ｌ
隶属 函数 。
Ｉ ＪＮ （） ｌ Ｌ ＩＤＢ
称 元 集 粗 为 素对 合 的 糙
：
１ ｍ
（Ｉ ） ｘ＋ ｋ
ｅ方 法 ５几 何 平 均 最 小 法 ：
若 Ｉ Ｄ（ ＝Ｎ Ｂ ａ ）ａ∈Ｂ，称Ｂ为 中 的 不 必 要 属 性 ， Ｎ Ｂ）Ｉ Ｄ（ 一｛｝ ， 。 反

方法选择非核属性 ，增加反向删除操作。该算法能够充分反映专家经验知识，保证得到一个 Ｐ ｗ ａ ａｌ ｋ约筒，大 幅度提高案例 的检索效率。
运用 Ｍａ ａ 编程实现了该算法 ，通过实例对算法进行分析、对 比，证明了其正确性 和有效性 。 ｄｂ 关健诃 ：粗糙集 ；基于案例推理 ；属性重要度 ；属性约简
［ ｓｒｃ｜Ｔ ｉｐ ｐｒ ｒｐ ｓｓａ ｌｏ ｔｍ ａｅ ｎｉ ｒｖ ｄｒｕｈｓｔ ｎ ｒｔ ａｍｅｔ ｔｏ ｒ ｅｉ ｏ ｂｅ Ｔ ｅａ ｏ ｔｍ ｏｓｈ Ａｂｔａ ｔ ｈｓ ａ ｅ ｏ ｏｅ ｎａｇ ｒｈ ｂ ｓｄｏ ｐ ｉ ｍｐｏｅ ｏ ｇ ｅ ａｄａ ｅｒ ｔ ｎ ｈ ｄｆ ｃ ｉｎｔ ｌ． ｈ ｌ ｒｈ ｄ ｅ ｅ ｐ ｅ ｍｅ ｏｄ ｓ ａ ｇｉ ｔ
Ｓ ＵＮ ａ ．ｉ ｇ ， Ｎ ｈ ． ｕ ＷＡＮＧ ｉ Ｙ ｈ ｑｎ ＹＩ Ｓ ｕ ｈ ａ， Ｊ
（ ． ｐ ｒｍｅ ｔ ｆＧｒ ｄ ａｅＳｕ ｅ ｔ ａ ａ ｅ ｎ， ’ｎＣｏ １ Ｄｅ ａｔ ｎ ｏ ａ ｕ ｔ ｔｄ ｎ Ｍ ｎ ｇ ｍｅ ｔＸｉａ ｍｍｕ ｉａｉｎＩｓｉ ｔ， ’ｎ７１ ０ ； ｎｃｔ ｏ ｎ ｔｔ ｅ Ｘｉａ ０１ ６ ｕ
１ 橇 述
粗糙集理论 自 １ ８ 年提出以来 ，已经在数据分析、数据 ９２ 挖掘、机器 学习等多个领域中得到广泛应用 Ｊ ，属性 约简则 是粗糙集理论研究的核心问题之一 。采用粗糙集方法对基于 案例推理（ａｅＢ ｓｄ Ｒ ａｏ ｉｇ Ｂ ） Ｃ ｓ． ａｅ ｅｓｎｎ，Ｃ Ｒ 系统中的案例进行属
３ Ｓａ ｏ ｍ ｆ ｌ ａｙＯｐ ｃ ｌ ｂ ｒ ｍ ｎｃ ｔ ｎ Ｘｉ ｎＣ ｍｍｕ ｉａｉｎＩｓｉ ｔ， ’ １ ６ Ｍｉ ｔ ｉ Ｆ Ｃ ｉ ａ ｎｃ ｔ ｔｕ ｅ Ｘｉ ７ ０ ０ ） ｏ ｎ ｔ ｎ ａ １

粗糙集理论的使用方法与步骤详解引言：粗糙集理论是一种用来处理不确定性和模糊性问题的数学工具，它在数据分析和决策支持系统中得到了广泛的应用。

本文将详细介绍粗糙集理论的使用方法与步骤，帮助读者更好地理解和应用这一理论。

一、粗糙集理论概述粗糙集理论是由波兰学者Pawlak于1982年提出的，它是一种基于近似和粗糙程度的数学理论。

粗糙集理论的核心思想是通过对属性间的关系进行分析，识别出数据集中的重要特征和规律。

它主要包括近似集、正域、决策表等概念。

二、粗糙集理论的使用方法1. 数据预处理在使用粗糙集理论之前，首先需要对原始数据进行预处理。

这包括数据清洗、数据变换和数据归一化等步骤，以确保数据的准确性和一致性。

2. 构建决策表决策表是粗糙集理论中的重要概念，它由属性和决策构成。

构建决策表时，需要确定属性集和决策集，并将其表示为一个矩阵。

属性集包括原始数据中的各个属性，而决策集则是属性的决策结果。

3. 确定正域正域是指满足某一条件的样本集合，它是粗糙集理论中的关键概念。

通过对决策表进行分析，可以确定正域，即满足给定条件的样本集合。

正域的确定可以通过计算属性的约简度或者使用启发式算法等方法。

4. 近似集的计算近似集是粗糙集理论中的核心概念，它是指属性集在正域中的近似表示。

通过计算属性集在正域中的近似集，可以确定属性之间的关系和重要程度。

近似集的计算可以使用不同的算法，如基于粒计算、基于覆盖算法等。

5. 属性约简属性约简是粗糙集理论中的一个重要问题，它是指从属性集中选择出最小的子集，保持属性集在正域中的近似表示不变。

属性约简的目标是减少属性集的复杂性，提高数据分析和决策的效率。

属性约简可以通过计算属性的重要度、使用启发式算法或者遗传算法等方法实现。

6. 决策规则的提取决策规则是粗糙集理论中的重要结果，它是从决策表中提取出来的一组条件和决策的组合。

决策规则可以帮助我们理解数据集中的规律和特征，从而做出更好的决策。

｛ ：
（ ４ ）
ｆ ， （ 一 Ｆ ） ／ （ Ｐ ｍ 一 ） Ｆ ≥
Ｐ＝ ｛ ［ ｃ ０ ， ｃ １ ） ， ［ ｃ ｌ ， ｃ ２ ） ， …， ［ ｃ ， ｃ ＋ １ 】 ｊ
对于任意的 Ｐ ＝ Ｕ Ｐ 在原有决策系统的基础上 ，
可定 义一个新 的决策表 Ｓ ｅ ＝ （ （ ， ， Ａ， ） 。 对 于 Ｖｘ∈Ｕ，
１ ） 利用式 （ １ ） ， 计 算 知 识 表 达 系 统 ： （ ， Ａ， Ｖ 厂 ） 中， 条件 属性 Ｃ对 决策 属性 Ｄ 的 支持度 ｋ ， ？ （ Ｄ） 。 ２ ） 假设 ｃ ｏ ｒ ｅ （ Ｃ） ＝ ， 对 于每 一个 条件 属 性 Ｃ ∈Ｃ， 利用 式 （ ３ ） 计算 其 对 决 策属 性 Ｄ 的 重要 性 ｓ ｝ ｅ ） 。
识 约 简 问 题 的实 际 要 求 ， 定 义 个 体 的适 应 值 函数
Ｆ （ ｘ ） 为
式中 ： ｃ为 条件 属 性集 Ｃ中 的一 个 元素 ； ｓ 锄 １ ｃ ） 为ｃ 对决 策属 性集 Ｄ 的重 要性 。
１ ． ２ 基 于布 尔逻 辑 的属 性 离散 化算 法
） ＝ （ １ 一 ］ 针）
决 策属 性 Ｄ 的支持 度 ｋ （ Ｄ） 定义 为
耻 （ １ ）
若ｓ
１ （ ｃ ） ≠０ ， 则令 ｃ ｏ ｒ ｅ 。 （ Ｃ） ＝ ｃ ｏ ｒ ｅ 。（ ｃ） Ｕ｛ ｃ｝ ， 最终
．
得 到 Ｃ对 Ｄ 的相 对核 。 当ｋ ｃ ｏ ｒ ｅ （ Ｄ） （ Ｄ） 时， ｃ ｏ ｒ ｅ 。 （ Ｃ） （ ￣） 即为最 小约 简 ； 否则 ｋ ｃ ｏ ｒ ｅ （ ｚ ） ） （ Ｄ） ， 执 行步骤 ３ ） 。 （ Ｃ）

一种高效的粗糙集属性约简算法【摘要】本文将递归和贪心算法的思想融入粗糙集理论的快速属性约简中，提出了一种较为高效的粗糙集属性约简算法。

该算法在保证约简质量的情况下，较大的提高属性约简的效率，实验仿真结果说明了该算法的高效性。

【关键词】粗糙集；属性核；属性约简；递归；贪心算法引言属性约简是粗糙集理论的一个重要研究内容，目前已经提出了许多经典的属性约简算法[1—6]。

得到决策表的最小约简是一个np 难题，现有的算法大多是以属性重要性为启发性知识得到一个相对约简。

文[1，2]给出了基于属性重要性的属性约简算法和归纳属性约简算法。

文[3，4]给出了基于信息熵的约简算法。

文[5]一种基于快速排序的属性约简算法。

文献[6]给出了一种基于蚁群优化的属性约简算法。

文献[7]给出了一种基于克隆选择的属性约简算法。

然而这些算法的时空复杂度都比较高，对于大数据的处理能力还不足。

本章结合递归的思想，将大数据集转化为多个小数据集来计算属性核，然后在利用贪心算法的思想进行属性约简，从而有效的提高了属性约简算法的运行效率。

1 相关概念以下将粗糙集属性约简的相关概念作简单介绍。

2 基于递归和贪心算法思想的快速属性约简算法本文中提出的属性约简算法首先计算属性核，然后在属性核的基础上采用贪心算法的思想进行属性约简。

首先给出递归思想计算属性核的理论基础。

3 仿真实验windows环境下采用vc6.0开发工具在个人计算机（windowsxp，cpu：p4 2.6，内存512）上进行实验仿真。

4 结束语理论证明得到决策表的最小属性约简是np难题。

本文综合利用递归和贪心算法的思想提出了一种较为高效的相对属性约简算法。

如何进一步提高该算法的效率是下一步研究的重点。

【参考文献】[1]王国胤.rough集理论与知识获取[m].西安交通大学出版社，2001.[2]x h hu， n cercone. learning in relational database：a rough set approach[j]. international. journal. of computational intelligence，1995，11（2）：323—338.[3]王国胤，于洪，杨大春.基于条件信息熵的决策表约简[j].计算机学报，2002，25（7）：759—766.[4]沈永红，王发兴.基于信息熵的粗糙集属性离散化方法及应用[j].计算机工程与应用，2008，05（8）：221—224.[5]刘少辉，盛球戬，吴斌，等.rough集理论高效算法的研究[j].计算机学报，2003，5（26）：524—529.[6]孙涛，蒋科艺，等.一种基于蚁群优化的粗糙集属性约简方法[j].海军工程学院学报，2011，11（1）：324—327.[7]梁霖，徐光华.基于克隆选择的粗糙集属性约简方法[j].西安交通大学学报，2005，11（39）：464—469.[责任编辑：王迎迎]。

ｓ Ｃ ｅｓ ｎ ｈ ｏ ｇ ｅ ｅ ｐ ｉ ｓ ｏ ｅ ｕ ｐ ｒａ ｄ ｌｗ ｒｓ ｌｒｄｓ ｉｕ ｏ ｔ ｘ ｓｆｕ ｄ ｏ ｏ ｄ ｔ ｎ ａｔ ｂ ｔｓａ ｄ ｄ ｃｓ ｎ ａ ｒ ｕｅ ｕ Ｃ ｓｉ ，ｔ ｒｕ ｈ ｄ ｓ ｒ ｔ ｎ ｆｔ ｐ ｎ ｅ ｉ ａ ｉｔ ｂ ｔ ｎ ｍａ ｅ ｎ ｎ ｃ ｎ ｉ ｏ ｔ ｕｅ ｎ ｅ ｉ ｏ ｔ ｉ ｔ ， ｏ ｉ ｏ ｈ ｅ ｏ ｍｉ ｒ ｉ ｉ ｒ ｏ ｉ ｉ ｒ ｉ ｔｂ
ｏｔｎｒ ｓｎｂｅ ｏ ａｔ ｏｓａ ｏｇｏｊ ｔ ｈ ｔ ｉ ｔｎｍｏｅ ｆ ｒ ｈｌ ａｃｕｔｇｉｐｅｅｔ ． ｈｎ ａｅ ｎｔ ｐｅ ｂ ｉ ｅ ｏａｌ ｓｆｐｒ ｎ ｎ ｅｓ ｅｏｉ ｚｉ ｄｌｏ ｔ ｅ ｏ ｃｏｎｎ ｒ ｎｅ Ｔ ｅ，ｂｓｄｏ ｅｕｐｒ ａ ａ ｔ ｉ ｉ ｔ ｍ ｂ ｃ ，ｔ ｐｍ ａｏ ｒｈ ｓ ｄ ｉ ｓ ｓ ｄ ｈ ａｄｌ ｅ ａｐ ｘ ａｏ ｎｅｔｒ ｕｈｓｔ ｅｒ．ｈ ｖｒ ｇｕｐｒａｄｌ ｅ ｍｌ ａｔｏｓａ ｏｇｏｊ ｔ ａ ｏｔｎ ． ｎ ｎ ｗｒ ｐｒ ｉ ｔｎｃ ｃｐ ｆｍ ｒ ｇ ｏ ｔ ｃ ｅｎ ｐｅ ｎ ｗ ｒ ｉｉｒ ｒｔｎ ｍ ｎ ｂ ｃ ｂ ｉｅ Ｉ ｏ ｏ ｍ ｉ ｏ ｏ ｏ ｅｔ ｙ ｅ ｏ ｉ ｈ ｏ ｓ ａｐ ｉ ｉ ｅｓ ａｄ
ｔｅ ｔ ｏ ａｔ ｂ ｔ ｒｄ ｃ ｏ ｓ １ ｆ ｉｅｅ ｔ ｉ ｏ ｎｓｃ ｎ ｂ ｔ ｅ ｅ ｔｉ ｖ ｌ ，ｂ ｓ ｄＯ ｅｎ － ｉｔ ｂ ｔ ｎ ｍａ ｘ ｓ ｉａｌ ，ｔｅ ｈ ｔ ｉｕｅ ｅ ｕ ｔ ｎ ｒ ｕ ｔ ｏ ｄｆ ｒｎ ｅ ｉｔ ａ ｅｒ ｒ ｖ ｉ ｕ ｔ ｅｙ ａ ｅ Ｎ ｔ ｍｘｄ ｓ ／ｕ ｏ ｔ ｅ ．Ｆｎ ｌ ｗ ｒ ｉ ｓ ｖ ｗｐ ｅｉ ｄ ｎ ｉ ｈ ｒ ｉ ｉ ｒ ｙ ｈ ｅ ｐ ｒ ｅ ｒ ｕｔ ｐ ｏ ｅ ｔａ ｉ ａ ｏ ｔｍ ｓｅ ｅ ｔ ｅ ａ ｄ ｆａ ｉｌ ． ｘ ｉ ｍ ｓ ｌ ｒｖ ｈ ｔ ｈｓ ｌ ｒ ｈ ｉ ｆ ｃ ｖ ｓｂｅ ｅ ｍ ｅ ｓ ｔ ｇｉ ｉ ｎ ｅ

一种基于模糊粗糙集的快速特征选择算法张晓;杨燕燕【摘要】模糊粗糙集由于能够处理实数值数据,甚至是混合值数据中的不确定性受到人们的广泛关注,其最重要的应用之一是特征选择,相关的特征选择方法已有不少研究,但其快速的特征选择算法研究很少.实际中的数据一般含有噪声点或信息含量低的样例,如果对数据集先筛选出代表样例,再对筛选的样例集进行数据挖掘便会降低挖掘计算量.本文基于模糊粗糙集,先根据样例的模糊下近似值对样例进行筛选,然后利用筛选样例的模糊粗糙信息熵构造特征选择的评估度量,并给出相应的特征选择算法,从而降低了算法的计算复杂度.数值试验表明该快速算法具有有效性,并且对控制筛选样例个数的参数给出了建议.【期刊名称】《数据采集与处理》【年(卷),期】2019(034)003【总页数】10页(P538-547)【关键词】模糊粗糙集;样例选择;特征选择;信息熵【作者】张晓;杨燕燕【作者单位】西安理工大学应用数学系,西安,710048;清华大学自动化系,北京,100084【正文语种】中文【中图分类】TP18引言经典的粗糙集理论[1]是由波兰数学家Pawlak在1982年提出的,它是一种处理数据中的不确定性的有效工具,然而经典粗糙集只能处理符号值(名义值)的数据。

模糊粗糙集[2]作为经典粗糙集的最重要的推广之一,可以用来处理实数值甚至是混合值的数据。

目前,模糊粗糙集已经成功应用于机器学习和数据挖掘领域[3],其最受人们关注的应用之一就是特征选择(属性约简)。

关于模糊粗糙集特征选择的研究工作已存在不少[4-10],但其快速的特征选择算法的研究还很少,据作者所知,仅文献[11]在特征选择算法迭代步骤提供了加速策略，从而减少了算法的计算时间。

实际中的数据一般包含信息量较低的样例或噪声点,如果对样例进行筛选,利用筛选得到的样例进行挖掘知识将会减少计算的复杂度。

文献[12]提供了3种样例选择的启发式算法,其中之一的算法思想即选择隶属模糊正域的值不小于给定阈值的那些样例。

性 ， 形成精 简 的规则 库 以帮助人 们做 出正 确且简 洁 的决策 ． 并 属性 约简 是粗糙 集 理论 （ ｏ ｇ ｅ ｅ ｒ ） Ｒ ｕ ｈＳ ｔ Ｔｈ ｏｙ 研究 的核 心 内容之一 ．Ｓ ｏ ｏ ｋ ｗｒ ｎ教 授 等人 提 出 的可辨 识
矩 阵方法 是计 算决 策 表 属 性 约 简 的一 个 代 表 性 方 法 ］ ，许 多 关 于 属 性 约 简 及 其 拓 展 的研 究 工 作 都 是 以
关 键 词 ：互 信 息 ；属性 约 简 ；不 相 容 决 策 表 ；核 文 献 标 识 码 ：Ａ
中 图分 类号 ：Ｔ １ Ｐ８
在 海量 信息 系统 中的属性 和 实例数 量非 常 巨大 ，有 的属性 并 不重 要 ，有 的属 性 甚至 是冗 余 的 ，这就 使 属 性约 简变 的非常 必要 ．属 性约 简可 以在保 持信 息系统 分类 和决 策 能力 不 变 的前提 下 ， 好 地剔 除 冗余 属 较
１ 粗 糙 集 相 关 理 论
在决策 表 中 ， 们关 心 的是哪些 条件 属性对 于决 策更 重要 ．本 文 以互 信 息 的大 小作 为 属性 重要 性 的度 人
量 ， 节给 出它们 的基本 概念 ， 判断冗 余属 性 的判定定 理． 本 及 定 义 １ 信 息系统 （Ｓ 可 由四元组 Ｓ Ｕ， ， ） Ｉ） 一（ Ｑ， ， 表示 ， 中 ： 其 Ｕ是对 象集 合 ， 即论域 ； Ｑ是 属性集 合 ； —Ｕ Ｖ Ｖ。 属性 ｑ的值域 ； Ｖ ， 是 ｆ是一个 信息 函数 ，即对 Ｖ Ｅ Ｕ， 有 ｆ ｘ， ）Ｅ Ｖ ．决策信 ｑＥ Ｑ， （ ｑ
设 Ｐ， Ｑ在 Ｕ上 导 出的划 分分别 为 Ｘ 一 ｛ Ｘ ， ６ 代 数 上定义 的概率 分 布为 ： 一 …Ｘ ） Ｙ一｛ Ｙ …Ｙ ） 则 Ｐ， ， Ｙ ， ， Ｑ在 Ｕ 的子集组 成 的

粗糙集是根据研究对象的条件属性与决策属性
之间的关系建立分类规则，以识别新观测对象所属类 别。粗糙集优良性评估注重粗糙集的分类能力，主要 对粗糙集的分类性能进行评价，如 Ｄüｎｔｓｃｈ等人利用 随机化统计方法考查粗糙集的分类规则是否仅基于 少数随 机 观 测 得 到，试 图 分 析 粗 糙 集 分 类 的 可 信 度［９］。很多文献也以分类误判率或分类正确率来评 价粗糙集分类的正确性，如 Ｈｕ等人构建了基于数据 库系统的新粗糙集，并进行了粗糙集属性约简［１０］，而 采用分类正确率考量新方法具有更高的计算效率； Ｊａｗｏｒｓｋｉ给出了衡量粗糙集分类规则准确性和覆盖 度的估计指标，并基于这些指标对粗糙集属性进行约 简和粗糙集优良性评价［１１］；Ｃｏｒｎｅｌｉｓ等人总结了使用 模糊容差关系进行粗糙集属性约简的方法，给出的实 际分析案例具有高正确率［８］；邓维斌等人建立了基于 优势关系粗糙集的自主式学习模型，并用正确率和平 均绝对误差评价粗糙集分类性能［１２］；翟育明等人构 造了基于（α，β）集对限制优势关系的粗糙集［１３］，而新 模型分类具有更低整体误判率。
收稿日期：２０１７－０３－０１；修复日期：２０１７－１１－０５ 基金项目：国家自然科学基金项目《劣者淘汰两阶段自适应临床试验的设计和分析》（１１４７１２３９）；２０１６年度重庆市社会科
学规划重大委托项目《人口普查质量评估前沿理论研究》（２０１６ＷＴ０３）；全国统计科学研究重点项目《大数据背 景下住户调查理论与应用研究》（２０１７ＬＺ２５）；天津财经大学研究生科研资助计划项目《粗糙集优化方法及在经 济中的应用研究》（２０１６ＴＣＢ０３） 作者简介：杨贵军，男，黑龙江哈尔滨人，理学博士，教授，研究方向：应用统计； 于 洋，女，天津人，博士生，研究方向：应用统计。
糙集择优和属性约简方法，先利用粗糙集的分类规 类别记为１－犮类。基于最大概率的粗糙集方法先计

维普资讯
蕉全融管堡干部学院学报
２０ ０ ２年第 ５期 （ ７ 期 总 Ｏ
基于 粗糙 集属性 约简的 数据挖 掘技 术
叶 东毅
（ 福州大学 计算机系 福建 福州 ３ ００ ） ５ ０ ２
摘
要： 粗糙 集理论 （ ｏ ｇ ｅ） Ｒ ｕ ｈＳｔ是波 兰学者 Ｚ Ｐ ＷＬ Ｋ提 出的一种 新的软计 算方法 ， ．Ａ Ａ 它在处理 含噪 声 、 完整、 不 不精
了良好的社会和经 济效 益。数据 挖掘技术涉及多
个学科领 域 ， 包含 了许 多 的核 心技 术 和方 法 ， 其 识关 系 记 为 Ｉ Ｄ（ ） 在 不 至 于 混 淆 情 况 下 ， 以 Ｎ Ｐ． 可
中 ， 糙 集 理论 是 一个 典 型 的 、 效 的方 法 。该 理 用 Ｐ代 替 Ｉ Ｄ（ ） 粗 有 Ｎ Ｐ． 论 （ ｏｇ ｅ，Ｓ 是 波 兰 学者 Ｚ Ｐ ＷＬ Ｋ 提 出 的 Ｒ ｕｈＳｔＲ ） ．Ａ Ａ
Ｌ＝（ Ｑ， ， ｑ ， ∈Ｑ Ｕ， Ｆ ） ｑ
（ ）｝ Ｐ Ｙ 。定义集合 ｙ的 下 逼近 ： ｙ＝｛ ∈ＵＩ ］ ｙ Ｐ ［ ｝
上 逼 近 ：ｙ＝｛ Ｐ ∈Ｕ１ ］ ≠ ｝ ［ ｎｙ 下 逼 近Ｐ ｙ定 义 了论 域 中一 定 属 于集 合 ｌ ，
其中 是论域 ， Ｑ是属性集合 ， 为属性取值
确 的信 息方 面具 有独特 的能 力， 已成为数据挖掘技 术 的一 个主要 方 法 ， 在许 多科 学与 工程领 域 中得 到 了广泛 的应 用。本
文着重介 绍粗糙 集的基 本思想 ， 以一 个具 体的属性 约简算 法和 实例 介 绍 它在 数 据挖掘 ， 别是在 数据 浓 缩和规 则提 取 并 特 中的应用 。 关键字 ： 糙集 粗 约简算法 数据挖掘

粗糙集属性约简的方法ComputerEngineeringandApplica~ons计算机工程与应用◎数据库,信号与信息处理@粗糙集属性约简的方法王培吉,赵玉琳27吕剑峰W ANGPeiii,ZHAOYulin,LVJianfeng1内蒙古科技大学数理与生物工程学院,内蒙古包头0140102内蒙古第一机械集团公司二分公司,内蒙古包头0140321.SchoolofMath.,Physics&BiologicalEng.,InnerMongoliaUniversityofSciencean dTechnology,Baotou,NeiMongol014010,China2.Branch2,InnerMongoliaFirstMachineryGroupCorporation,Baotou,NeiMongol01403 2,ChinaW ANGPeiji,ZHAOYulin,LVJianfeng.Newmethodofattributereductionbasedonroughse puterEngineeringandAp—plications,2012,48(2):113—115.Abstract:Objectsclassificationisstrictexcessivelyandtoosensitiveonnoise.Aimingatdeci sionsystemwithuncertainfactor.anal? gorithmofattributereductionbasedondependabilityisestablished.Theattributesinthesyste mwithuncertaininformationandnoisedataarereduced,wherebyfindingareducibleimpliedpatternofthedata,anddeletingthosere dundantrulesinthesystem.Anditcan keeptheoriginalpropertiesandfunctionsofthesystem.Theimplementationofalgorithmisd escribedbyintroducinganexample.Keywords:roughset;dependability;attributereduction;implementation摘要:传统粗糙集分类方法过于严格,对噪音过分敏感.针对带不确定因子决策系统,提出一种基于属性依赖度的约简算法,使含不确定信息及数据噪音的系统中的属性得以简化,找到一种具有广泛表达能力的数据隐含格式,删去冗余的规则,并保持系统的原有用途和性能.通过一个例子实现了该算法.关键词:粗糙集;依赖度;属性约简DOI:10.3778/j.issn.1002—8331.2012.02.032文章编号:1002.8331(2012)02.0113.03文献标识码:A中图分类号:TP311基于粗糙集理论】的知识获取的核心问题之一是属性约简,有很多学者作了这方面的工作,其中应用较多的是基于辨识矩阵以及在此基础上的一些改进算法1.一般说来,知识库中的知识(属性)并不是同等重要的,还存在冗余,这不利于做出正确而简洁的决策.属性约简要求在保持知识库的分类和决策能力不变的条件下,删除不相关或不重要的属性.一般而言,较优的属性约简有如下指标:约简后属性个数较少;约简后规则数目较少;最终范化规则数目较少等.已证明求决策表所有约简和最小约简是一个典型的NP嘲问题,不过,在实际应用中,往往只要求出某种次优的属性约简就可以了.传统粗糙集分类方法过于严格,以及数据中存在噪音,造成知识的遗漏.如:条件属性下的两个等价类.,,分别有100个元素,对决策属性等价类,,只有一个元素属于,而,只有一个元素不属于,基于传统的粗糙集模式,,,同属于的边界区,对都不能作出肯定的判断,然而A,中只有一个元素不属于,也许是由噪音导致的,说明传统粗糙集对噪音是非常敏感的,而在机器学习,专家系统等实际应用中,获得的数据含有噪音是不可避免的,因此传统粗糙集模式在一定程度上限制了它更有效的应用,本文提出的针对带不确定因子决策系统的分类方法可将原来由于噪音的影响,被划到边界的等价类划回到正区(如上面的,)或负区(如上面的),克服了粗糙集对噪音过分敏感的缺点,使在有噪音的环境下获得的知识更可靠.1带不确定因子决策系统定义1称=fU,CUD,{},,imp}为带不确定因子的决策系统,记为S,D=},d是带不确定因子(0<-I.t1)的结论属性,=1表示该元素对结论有完全肯定的判断,即该元素所在等价类属于结论属性的正区POSB(D),=0表示该元素对结论有完全否定的判断,即该元素所在等价类属于结论属性的负区NEG09);imp是中元素在中的重要度,体现元素在中的重要性./1,imp由领域知识及数据库操作得到.如表1为一带不确定因子的决策系统.表1带不确定因子的决策系统075O.67O-350750.670_35表1中U={1,2,3,4,5,6),条件属性集C={日1,口2),1={1,2),2={1,2,3),决策属性D={,={1,2,3),每一元素的重要度imp={4,3,4,4,3,4},及不确定因子={O.75,0.67,0.35,0.75,0.67,0.35}.基金项目:国家自然科学基金(No.81060238).作者简介:王培吉(1968一),男,副教授,主要研究领域为数据库,数据挖掘;赵玉琳(1968一),男,高级工程师;吕剑峰(1984_),男,助教.E-mail:*************收稿日期:2011-01.24;修回日期:2011-04.26;CNKI出版:2011-07—25;/kcms/detail/11.2127.TP.20110725.1624.020.html ComputerEngineeringandApplications计算机工程与应用2属性依赖度与属性约筒2.1属性依赖度定义2在S中,BcC,,YcU/B且处于边界,划POSB(D):rflJY;~IJ)kNEG口(D)的误差p()和,l(】,)分别定义为: ):—Z—(impi_x(1一-,ui))厶l州,,?(y):—~.,(im_Pixiai)乙Ilnl划入正区和y划入负区的误差水平分别记为,.即:p()P时,XcPOSB(D);n(】,)≤Ⅳ时,YcNEG口(D●.定义3对,在误差水平为和下,结论屙陛d对条件属性集合C依赖度Dep(C,D,,)是U/C被划入正区POSc(D)和Y划入负区NEG(D)中元素重要度的和与所有元素重要度之比.2.2属性约简定义4在中,误差水平为P和,BC,a∈B,Dep(B,D,,Ⅳ)=Dep(B-{a},D,,aN),称a为B中可省略的,否则a为当中不可省略的;当所有a∈B在中不可省略的,且Dep(B,D,,Ⅳ)=Dep(C,D,,Ⅳ),即D对B,C有相同的依赖度,则是c的一个约简u.定义5在S中U/C={,,…,},称)为的辨识矩阵,其中,"一C:a(X)~a(Xj),D()≠D()}1,其他'其中l≤f,j<t.m包含使得,具有不同结论属性值的所有属性.称/=,vm为S的分辨函数,其中V表示m中所有属性的析取运算,^表示合取运算.如果一个属性在信息系统中是可省略的,删除此属性并不影响信息系统的依赖关系,且能与c一样分辨所有元素的属性子集,但这样的约简不是唯一的,co~(c1表示C的所有约简的交集.核.表1表示的带不确定因子信息系统中P=0.3,=0.6条件属性C的等价类:={l}={2}={3}={4}={5}={6}由P()={{4×(1.0—0.75)j=0.25P()={{3x(1.0—0.67)}=0.33P()={4×(1.0～o.75)}:0.25P()={{3×(i.0一o.67)}:0.33Ⅳ()={4×0_35))=0.35Ⅳ(x6):{4×0_35)}=0.35及P=0.3,Ⅳ=0.6得P(D):{,(D):{,}BND(D)={,}DEP(C,D,P,Ⅳ)=I-(4+4+4+4)=0.73等价类,划回到正区,等价类,划回到负区;而用传统粗糙集进行分类,它们却都属于边界类,造成了知识的遗漏和偏差.3基于属性依赖度的属性约简算法步骤1根据挖掘目标,选取一屙l生为结论屙陛,其余为条件属性;对数据进行归纳,形成宜于实施挖掘的数据形式,同时,结合统计结果及领域知识为每一对象赋一重要度imp及不确定因子,形成带不确定因子的决策系统=(￡,,CUD, {},imp).步骤2由及不可分辨关系形成条件属性等价类和结论属性等价类,对处于边界的等价类,根据,imp及和划入正区和负区,由新的等价类形成可辨识矩阵.步骤3由可辨识矩阵找出该不可分辨关系的核B=COl~(C).步骤4C=C—B.步骤5对每一属性a∈C,计算Dep(BU{a},D,,,)一Dep(B,D,P,Ⅳ)并按降序排列C.步骤6DoJl[~序取a∈C,B=BU{a},C=C一{a}计算Dep(B,D,p,Ⅳ)UntilDep(B,D,P,Ⅳ)=Dep(C,D,dP,Ⅳ)步骤7For/=1to1B1Do如果a诺co~(c),则B:-{a}若Dep(B,D,,ON)~:Dep(C,D,P,Ⅳ)则B=BU{a.1.步骤8得条件属性c的约简为子集B.步骤9由约简简化带不确定因子的决策系统,形成由约简属性集为条件属性的决策系统S=,BU{d}).步骤10合并相同和相近元素(若结论相同,条件中仅有一项不同,则该项对该结论无关紧要).步骤11知识表示.4实例分析决策系统=,CU{d}),按结论属性d排序,为每一对象赋一重要度imp及不确定因子(如可将条件属性下每一等价类元素个数作为该对象的重要度imp),得到带不确定凶子的决策系统=(,CUD,{}c,,imp),见表2.由表2得条件属性C的等价类为={1),:{2}1={3},={4},={5,12},:{6j,={7,9},={8},=flo},Xl.:{1l},={13},:={14,15}.合并等价类得表3,进而得辨识矩阵(见表4).由可辨识矩阵得COl~(C)={a3}.:CORE(C)={a3),C={Ⅱ1,a2,a4,a5}.对每一属性a∈C,计算Dep(BU{aD,,).王培吉,赵玉琳,吕剑峰:粗糙集属性约简的方法2012,48(2)115 表2带不确定因子的决策系统表3=U,CUD,{)Ⅲ,,帅)表4辨识矩阵910l1a2a4a2a3a5ala2a3a5a2a4a2a3a5ala2a3a5a2a4a2a3a4a5dla2a3a4a5a2a4a2a3a4a5ala2a3a4a5ala4a5ala3a4a5a3a4a5a1a2a4ala2a3a4a5a1a2a3a4a5a2a4a5a2a3a4ala2a3a4a2a3a4a2a3a4a5ala2a3a4a5a3a4a2a3a4a3a2a3ala2a3a5ala3a3a5由条件属性co~(c)U{al}的等价类为={1,5,6,7,8,9,12,13},={2},={3),:{4,10},={14,15}及)=(1×(1—0.6)×2+2×(1—0.9)×4+1×(1—0.8)+l×(1—0.9))/12=0.158,z()=(1×0.6×2+2×0.9×4+1×0.8+1×0.9)/12=0.842 p(x2)p(X3)1×(1—0.9)/1=0.1n()n(X3)1x0.9/1=0.9P(X4)=(1×(1—0.9)+1×(1—0.8))/2=0.15H()=(1×0.9+1×0.8)/2=O.85)(2×(1—1)+2×(1—1))/4=0n(Xs)=f2×1+2x1)/4=l得正区等价类为={2)={3)x4={4,10}={14,15};边界等价类为={1,5,6,7,8,9,12,13).这样Dep(CORE(C)U1}, D,P,Ⅳ)=9/21.同理可得:Dep(CORE(C)U{a2},D,P,Ⅳ)=21/21Dep(CORE(C)[J{a4},D,,Ⅳ)=19/21Dep(CORE(COU{a5},D,P,Ⅳ):9/21按依赖度降序排列C={a2,a4,al,a5}B=cD衄(c)U{a2}:{a2,a3}Dep(B,D,P,Ⅳ)=21/21B=曰U{a4)={a2,a3,a4}可求得:Dep(B,D,,Ⅳ)=19/21a2硭CORE(C),贝0B=B-{a2)={a3,a4)又Del~B,D, P,Ⅳ)=19/21DIC,D,P,aN).这样,求得条件属性c的约简为子集B={a3,a4,.由约简B={口3,a4},表3简化为表5.=3对应的五:a3=3,a4=2及五:a3=3,a4=3中仅有口4的值不同,将对应的a4值去掉合并墨,化为表6.表5决策系统"=",BU{d})表6决策系统=,BU{d})知识表示:{(口3=3)^(a4=1)}v{(a3=2)^(a4=2)}(=2)(a3=3)=3)(a3=4)^(a4=3)=4)5结束语本文针对带不确定因子决策系统,提出了一种基于属性依赖度的属性约简算法,本算法能从属性集合中有效去除冗余属性,使属性选择的结果更合理,数据噪音的影响更小,获得的知识更可靠.在大部分情况下本算法都能快速有效地找到属性子集的最优解或令人满意的次优解.(下转129页)m56789m¨刘兴阳,毛力:基于f分布变异的自适应差分进化算法2o12,48(2)129进化代数进化代数进化代数进化代数图1sphere函数寻优曲线对比图2R0senbr0ck函数寻优曲线对比图3Griewallk函数寻优曲线对比图4Ackley函数寻优曲线对比表1三种算法寻优结果比较5结论本文提出一种基于f分布变异算子的自适应差分进化算法:其一在变异过程中使用f分布变异算子有效地将高斯变异和柯西变异进行结合;其二根据进化的不同阶段,提出新的自适应方式来调节进化策略及交叉概率.通过采用四个典型测试函数对新算法进行测试,实验结果表明本文提出的改进算法具有较好的全局探索能力和局部开发能力.参考文献:[1】StornR,PriceK.Differentialevolution-asimpleandefficient heuristicforglobaloptimizationovercontinuousspaces[J].Jour- nalofGlobalOptimization,1997,11(4):341—359.【2]ZhangM,LuoW,WangXF.Differentialevolutionwithdynamic stochasticselectionforconstrainedoptimization[J].Information Sciences,2008,178(15):3043.3074.【3]3唐德翠,朱学峰.改进差分进化PID参数优化及在凝絮中的应用[j]. 计算机工程与应用,2009,45(24):204.206.[4】MaulikU,SahaI.Modifieddifferentialevolutionbasedfuzzy clusteringforpixelclassificationinremotesensingimagery[J]. PaaemRecognition,2009,42(9):2135-2149.【5】RahnamayanS,TizhooshHR,SalamaMMA.Opposition-based differentialevolution[J].IEEEComputationalIntelligenceSociety,2008,12(1):64—79.[6】潭跃,谭冠政,伍雪冬.基于交叉变异策略的双种群差分进化算法[J]. 计算机工程与应用,2010,46(18):9-12.[7】DasS,AbrahamA,ChakrabortyUK.Differentialevolutionusing aneighborhood—basedmutationoperator[J].IEEETransactions onEvolutionaryComputation,2009,13(3):526.553.【8】LanKuo-Tong,LanChun-Hsitmg.NotesonthedislinctionofGaussian andCauchymutations[C]//EighthInternationalConferenceonIn. telligentSystemsDesignandApplications,2008:272-277.[9】Y aoX,LiuY,LinG.Evolutinaryprogrammingmadefaster[J].IEEE TransactionsonEvolutionaryComputation,1999,3(2):82—102.【1O】周方俊,王向军,张民.基于t分布变异的进化规划【J].电子, 2008,36(4):667.671.(da接l15页)参考文献:【1】PawlakZ.Roughset[J].InterofComputerandInformationSci- ences,1982,11.【2】刘清,刘少辉,郑非.Rough逻辑及其在数据挖掘中的应用【J】.软件,2001,12(3):415—419.【3】刘银山,吴孟达,王丹.粗糙集中求取所有最小约简快速算法【J].计算机工程与科学,2007,29(I):97—100.[4】苗夺谦,胡桂荣.知识约简的一种启发式算法[J】.计算机研究与发展,1999,36(6):681.684.【51HuXiaohua,CerconeN.Learninginrelationaldatabases:a roughsetapproach[J].ComputationalIntelligence,1995,11(2):323.337.[6]胡或,李智玲,李春伟.一种基于区分矩阵的属性约简算法[J].计算机工程与应用,2007,43(9):178.181.[7】黄治国,王端.基于粗糙集的数据约简方法研究[J】.计算机工程与设计,2009,30(18).【8】WongSK,ZiarkoW.Onoptimaldecisionrulesindecisionta-bles[J].BulletinofPolishAcademyofScience,1985,33:693-696.(上接123页)【7】ZhuZhengyu,XuJingqiu,RenXiang,eta1.QueryExpansionBased onaPersonalizedWebsearchmodel[C]//ThirdInternationalCon- ferenceonSemantics,KnowledgeandGrid,2007:128—133.【8】ZhuZhengyu,ZhouZhi,YuChunlei.Aquantizedanalyzingmethod forfindingauser'sinterestedwebpagesbasedontheuser's browsingactionsandquerywords[C]//InternationalConference onWebInformationSystemsandMining,2009.【9】ZhuZhengyu,TianYunyan,YuanKunfeng,eta1.Animproved Webdocumentsclausteringmethord[J].JournalofComputational InformationSystems,2007,3(3):1087—1094.[10】蒋萍.基于用户兴趣挖掘的个性化模型研究与设计[D].苏州大学, 2005:39-40.[11】张敏,宋睿华,马少平.基于语义关系查询扩展的文档重构方法[J].计算机,2004(10).【l2】瞿瑞彩,谢伟松.数值分析【M】.天津:天津大学出版社,2001:2-3. [13】LovicS,LuMeiliu,ZhangDu.Enhancingsearchengineperfor- manceusingexpertsystems,informationreuseandintegration[C]g IEEEIntema~IonalConferenceonSept2006:567.572.^趔卿籁闺。

粗糙集理论及其应用发展一、粗糙集的产生与发展粗糙集(Roughsets)理论是由波兰数学家Z. Pawlak在1982年提出的，该理论是一种刻画不完整性和不确定性的数学工具，能有效地分析和处理不精确、不一致、不完整等各种不完备信息，并从中发现隐含的知识，揭示潜在的规律。

1992年至今，每年都召开以RS为主题的国际会议，推动了RS理论的拓展和应用。

国际上成立了粗糙集学术研究会，参加的成员来自波兰、美国、加拿大、日本、挪威、俄罗斯、乌克兰和印度等国家。

目前，粗糙集这一新的数学理论已经成为信息科学领域的研究热点之一，它在机器学习、知识获取、决策分析、过程控制等许多领域得到了广泛的应用。

粗糙集首先从新的视角对知识进行了定义。

把知识看作是关于论域的划分，从而认为知识是具有粒度〔granularity〕的。

认为知识的不精确性是由知识粒度太大引起的。

为处理数据〔特别是带噪声、不精确或不完全数据〕分类问题提供了一套严密的数学工具，使得对知识能够进行严密的分析和操作。

又由于数据挖掘的深入研究和一些成功的商业运作，使得粗糙集理论和数据挖掘有了天然的联系，粗糙集在知识上的定义、属性约简、规则提取等理论，使得数据库上的数据挖掘有了深刻理论基础，从而为数据挖掘提供了一种崭新的工具。

粗糙集不仅自己可以独特的挖掘知识，而且可以和其他的数据挖掘算法结合起来，从而产生了学多混合数据挖掘算法，大大开拓了数据挖掘的算法和技术，丰富了数据挖掘的工具。

除了研究，人们也在积极寻找粗糙集在数据挖掘中的应用，如RSES系统，该系统是基于粗糙集理论上研制的数据挖掘系统，里面提供了粗糙集的属性约简算法和规则提取，可以找到最佳约简集和近似约简集，并可以提出规则。

另外，还有，Regina大学开发的KDD-R系统，被广泛用于医疗诊断、电信业等领域。

还有美国Kansas大学开发的LERS(Learningfrom Examples based on RS)系统，在医疗诊断、社区规划、全球气象研究等方面都有应用。

ＨＵ ｉｈ ａ ， ＤＩ Ｌ—ｕ ＮＧ ｈ —ｅ ， ＤＩ Ｇ ｏ Ｓ ｉｆ ｉ Ｎ Ｈａ
（．Ｓ ｈ ｏ ｆ ｏ ｕｅ ｃｅ ｃ ｎ ｅ ｈ ｏｏ ｙ Ｉ ｃ ｏ ｌ ｍｐ ｔｒ ｉｎ ｅａ ｄＴ ｃ ｎ ｌｇ ，Ｃｈｎ ｎｖ ｒｉ ｆ ｎｎ ｎ ｅ ｈ ｏｏ ｙ Ｘｕ ｈ ｕ２ ，Ｃｈｎ ； ｏＣ Ｓ ｉａＵ ｉｅｓ ｙｏ ｉｇａ ｄＴ ｃ ｎ ｌｇ ， ｚ ｏ ２ １ ｔ Ｍｉ Ｉ １６ ｉａ
进算 法，减 少算法在计 算时 所需的 时间和 空间复杂度 ， 求取 最 小约简 。将 改进后 的约 简算法 系统地应 用到 学生考试 成绩分 析 中， 对得 到 的规 则进行 科学地评 价 ， 出影响 学生成绩 的潜在 因素 ， 找 并提 出学 习建议 。通过 实际应 用表 明 了改进 算法的有
２ Ｋ ｅ ｂ ｒ ｔｒ ｆ ｎ ｅｌ ｅ ｔｎｆ ｒ ａｉ ｎＰｒ ｃ ｓ ｉｇ， ｎ ｔｔｔ ｆＣｏ ｐ ｔ ｇＴ ｃ ｎ ｌ ｇ Ｃｈｎ ｓ ａ ｅ ｙｏ Ｓ ｉｎ ｅ ， ． ｙＬａ ｏ ａ ｏ ｙｏ Ｉ ｔｌｉ ｎ ｏ ｍ ｔｏ ｏ ｅ ｓｎ Ｉ ｓｉ ｅｏ ｇ Ｉ ｕ ｍ ｕ ｉ ｅ ｈ ｏ ｏ Ｎ ｉｅ ｅＡｃ ｄ ｍ ｆ ｃｅ ｃ ｓ ｎ
（．中国矿 业大 学 计 算机科 学与 技 术学 院 ，江 苏 徐 州 ２ １１ ； １ ２ １６ ２ ．中国科 学院 计 算技 术研 究 所智 能信 息处理 重 点 实验 室，北 京 ｌ０ ８） ００ ０
摘 要 ：对 目前 常 见 的 粗 糙 集 属 性 约 简 算 法 进 行 了研 究 和 总 结 ，在 此 基 础 上 ，针 对 差 别 矩 阵 以 及 启 发 式 约 简 算 法 提 出 了 改
Ｂ ｉｎ ０ ０ ０ Ｃ ｉａ ｅ ｉ １０ ８ ， ｈｎ） ｊｇ

图 2 信息系统实例 粗糙集理论研究的对象一般是如图 2 所示的表格（信息表或决策表）。用形式语言表示 为一个四元有序组 S=<U,V,f,A>。其中 U 是对象（事例）的有限集合，U＝{x1,x2,...,xn}；A
是属性的有限集合，A＝{A1,A2,...Am}；V 是属性的值域集，V＝{V1,V2,...,Vm}，其中 Vi 是属性 Ai 的值域。f 是信息函数（information function），ｆ：Ｕ×Ａ→Ｖ，f(xi,Aj)∈Vj。
粗糙集理论中，一个对象是否隶属于某一集合（概念），不是该元素的客观性质，而 是取决于我们对它的了解程度，即知识 R 的分类能力。
粗糙集中的粗糙包含关系，粗糙相等关系。主要是比较集合的拓扑结构而不是集合元素。 在给定的知识库中，基于不同的知识，两个集合可能是精确相等，也可能是粗糙（近似） 相等，或许是粗糙不相等。相等是相对的概念。 1.6 信息论的度量
减弱知识的分类能力。 参数重要度强的属性对知识的分类能力越强，但将参数重要度强的知识结合在一起，
分类能力不一定强。 如果所有 P 中的知识对于论域 U 中的对象正确地划分到知识 Q 的基本范畴
（IND（Q）等价类）都是必不可少的，那么知识 P 就是 Q 独立的。知识 P 的 Q 核是知识 P 最基本的特征部分。
图 1 集合的上下近似 如图 1 所示，折线相连构成的闭合区域表示不确定的概念 X，灰色外边界和黑色外边 界表示人们使用能够确定表达的概念，也就是概念 X 的外延和内涵。人们无法直接表达概 念 X，但可以通过 X 的外延和内涵间接表达。同时概念 X 的外延和内涵可以用来反映 X 的 不确定性即概念的不精确性。图中灰色区域越大，表示概念 X 的精确性越低。 由图 1 可以看出，概念 X 的表达只依赖于人们所了解的关于 X 的外延知识和内涵知识， 不需要预先知道额外信息。粗糙集理论对事物的不精确性表达不 需 要 任 何 假 定 的 先 验 知 识 ， 只依赖于所给定的知识表达系统，通过上下近似算子直接计算得到，这一点与概率论和模 糊集合理论完全不同，这也是粗糙集理论受到广泛关注的原因之一。 1.2 知识是一种分类能力 粗糙集理论受到广泛关注的另一个原因是它对知识的观点。在粗糙集理论中，知识（人 的智能）是一种对对象进行分类的能力。这里的“对象”包括：实物，状态，抽象概念，过 程和时间等。我们通常用等价关系或关系来表示分类和知识。 粗糙集理论把知识定义为关于论域的划分模式，从而使知识具有了颗粒性，我们称其 为信息粒度或知识粒度，简称粒度。 1.3 信息系统