一种基于知识粒度的属性约简算法
- 格式：pdf
- 大小：178.99 KB
- 文档页数：3
Ｕ Ｉｄ Ｑ ／ｎ （ ）表 示 ， 简记 为 Ｐ Ｑ 若对 。 粗 糙 ， Ｕ Ｉｄ Ｐ） 用 ／ｎ （
性重要性作 为启 发式信 息 ， 采用 启发式搜 索方 法从信 息系统
中求 出最优或次 最优约简。 本文遵循属性约简的一般 原则 ， 出一种 基于知识 粒度 给 的属性约简算法。其 基本思路是 ： 先利用知识粒度的概念 ， 首 对属性的重要度进行定义 ， 然后 用属性 重要 度作为属 性选择
维普资讯
第２ ６卷
２０ ０ ６年 ６月
文 章 编 号 ：０ １ ０ １ ２ ０ ） ６ ０ ７ ０ １ ０ —９ ８ （ ０ ６ ０ Ｚ一 ０ ６— ２
一
计 算机应 用
Ｃｏ ｕ ｅ ｐ ｉａｉ ｎ ｍｐ ｔｒ Ａｐ ｌｃ ｔ ｓ ｏ
Ｖｏ ＿ ６ ｌ２ 关 源自 ， Ｉｄ Ｐ 且 ｎ （ ）＝ｎ
０ 引 言
属性约简是粗糙集 理论… 中的重要 内容之 一 ， 它刻画 了
信息系统中知识的本质部 分 。通 常情况 下 ， 似空 间中的 属 近
．
，
若 Ｐ Ｑ Ａ， Ｉｄ Ｑ Ｉｄ Ｐ 。 则 ｎ （ ） ｎ （ ）
设 Ｕ Ｉｄ Ｐ ＝ ｛ ］ ｌ ∈ Ｕ ／ （） ｎ ［ ｝表示不 可 区分关 系
启发 式信 息 ， 出一种 基 于知 识粒 度 的属性 约 简启发 式算 法 ， 算 法 的时 间复 杂度是 多项式的 。最后 提 该
通过例 子说 明 了该 算法 的有 效性 。
关 键词 ： 息 系统 ； 识 粒度 ； 信 知 重要 度 ； 属性 约 简 中 图分类号 ： Ｐ １ ． ３ Ｔ ３ １ １ 文献标 识码 ： Ａ
∈Ｕ ，） ∈ 。 ａ
定义４ 设 Ｓ＝（ Ａ ｕ，）是一个 信 息系统 ， ／ｎ （ ） ＝ Ｕ Ｉｄ Ａ ｛ ， ， ， ｝则 Ａ 的 知 识 粒 度 ， 为 Ｇ Ａ ， 义 为 ： … ， 记 Ｋ（ ） 定
Ｇ（ Ｋ） Ａ
／ Ｉ其 ∑ ｉ 中 ， ｉ ｕ
＝
Ｕ Ｉｄ Ｑ）表示 ， ／ｎ （ 简记 为 Ｐ＜ Ｑ 。 定义 ２ 设 Ｓ ＝ （ Ａ ｕ， ）是 一个信 息 系统 ， ∈Ａ， 果 ａ 如
同逐次选择最重要的属性增 加到核 中去 ， 到其粒 度等于 属 直
约简 。
ＩｄＡ一｛｝ ｎ（ ａ ）＝ＩｄＡ ， 。 ｎ （ ）则称 在Ａ中是冗余的 ， ， 口 否则 称 在
究 ］ 。综观各种属性约简算 法 ， 其基本 思想 一般 是利用 属
中［］ ＝｛ Ｙ∈Ｕ （ Ｙ ｌ ）∈ＩｄＰ ｝ ， ｎ （ ） 称为 Ｐ 等价类或 Ｐ 知识
颗粒。
令 Ｐ Ｑ Ａ 若对 Ｖ ， ， Ｘ∈Ｕ ＩｄＰ ， Ｙ∈Ｕ Ｉ （ ） ／ｎ （ ）存在 ／ ｄＱ ， ｎ 使 得 ｙ则称 Ｐ的划分 比 Ｑ更精细 ， ， 或者 Ｑ 的划分 比Ｐ 更
核是所有约 简的交集 。
如果每个属性 ａ ｅ Ａ在 Ａ中是必要 的， 则称 属 性集 Ａ的粒 度为止 ， 这时得到 的属性 子集便 构成 系统 的最 小 Ａ中是必 要的。
１ 信息系统与知识粒度
下面介绍信 息系统 中的几个概 念和有关定理 ［ 。 ７ ＿ 定义 １ 四元组 Ｓ＝（ Ａ， ｕ， 是一个信息系统 ， 中 ｕ 其 表示对 象的非空有 限集合 ， 称为论域 ； Ａ表示 属性 的非空有 限 集合； Ｖ＝ｕ ， 表示属性 。 的值域 ： Ａ ｕ× — 是信息函 数， 它为每个 对象 的每 个属性 赋予 一个信 息值 ， Ｖ。 Ａ， 即
ｎ
是由
．
（ ×置 ）
１
通常 ， Ｓ＝ （ Ａ， ｕ，
记为 Ｓ＝ （ Ａ 。 ｕ，）
也称为知识表达 系统或知识 Ａ， 简
决定 的等价关 系的基 数。
当Ｉ （ ）＝｛ ，） ∈Ｕ 时，／ｎ（ ） Ｉ ∈ｕ ｎＡ ｄ （ ｌ ｝ Ｕ Ｉ Ａ ＝｛ ｄ ｝
对于 Ｖａ ∈ Ａ， 以 定 义 ｕ上 的 一 个 等 价 关 系 ０ ： 可
Ｉｄ Ｐ ｎ （ ）在 ｕ上导 出的划分 ， 也称为 Ｐ的划 分或信息粒 度 ， 其
性并不是 同等重要的 ， 至某 些属 性是冗 余 的。冗余 属性 的 甚 存在 ， 会造成 资源的浪费 ， 不仅 而且也会 干扰人们做 出正确而 简洁的决策 。因此 ， 多学 者致力 于对 属性约 简算法 的研 有许
性集 Ａ是独立 的 ， 否则 ， Ａ是依赖的。 称 Ａ中所 有必要的属性组 成 的集合称为属性集 Ａ的核 ， 记作 Ｃ ｒ（ 。 ｏｅＡ） 定义 ３ 设 Ｓ ＝ （ Ａ ｕ， ）是一个 信 息系统 ， Ａ， 果 Ｐ 如 Ｉｄ Ｐ ｎ （ ）＝Ｉｄ Ａ ， Ｐ是独立的 ， ｎ（）且 则称 Ｐ是 Ａ的一个约简 。
Ｊ ｎ ０ ６ ｕ ｅ２ ０
种 基 于 知 识粒 度 的属 性 约 简 算 法
李 秀红 史开泉 ，
（． １ 山东经济学院 统计与数学学院， 山东 济南 ２０ １ ； ５０４ ２ 山 东大学 数 学与 系统科 学 学院 ， 东 济 南 ２０ ０ ） ． 山 ５ １０
摘
（ ｉｈｎ 一 ２ ＠ ｓｈ ．ｏ ｘｕ ｏ ｇ １７ ｏｕ ｃｍ） 要： 通过 引入 知识 粒度 的概 念 ， 对信 息 系统 中属 性 的 重要 度 进 行 了定 义 ； 以属性 重 要度 为 并
标准 ， 求出属性集 Ａ的核 ， 从核 出发 ， 再 根据 属性重要 度的不
Ｖ ∈ Ｕ Ｉ （ ）存在 Ｙ∈ Ｕ Ｉ （ ）使 得 Ｘ ／ ｄＰ ， ｎ ／ ｄＱ ， ｎ
ｙ且存 在 ，
∈Ｕ ＩｄＰ ， ∈Ｕ Ｉｄ Ｑ ， ／ｎ （ ） ／ｎ （ ）使得 ｃ ， Ｐ 则称 的划 分 比 Ｑ严格精 细 ， 或者 Ｑ的划分 比 Ｐ严格粗糙 ， Ｕ Ｉｄ Ｐ 用 ／ｎ （ ）＜
ｘ ｃ （ ，）＝，Ｙ８ ， 在 【 上产生 的划分为：／ ． Ｏ ￣ ｘ８ ｙｆ （ ，）０ 。 ， Ｕ ｏ＝
性重要性作 为启 发式信 息 ， 采用 启发式搜 索方 法从信 息系统
中求 出最优或次 最优约简。 本文遵循属性约简的一般 原则 ， 出一种 基于知识 粒度 给 的属性约简算法。其 基本思路是 ： 先利用知识粒度的概念 ， 首 对属性的重要度进行定义 ， 然后 用属性 重要 度作为属 性选择
维普资讯
第２ ６卷
２０ ０ ６年 ６月
文 章 编 号 ：０ １ ０ １ ２ ０ ） ６ ０ ７ ０ １ ０ —９ ８ （ ０ ６ ０ Ｚ一 ０ ６— ２
一
计 算机应 用
Ｃｏ ｕ ｅ ｐ ｉａｉ ｎ ｍｐ ｔｒ Ａｐ ｌｃ ｔ ｓ ｏ
Ｖｏ ＿ ６ ｌ２ 关 源自 ， Ｉｄ Ｐ 且 ｎ （ ）＝ｎ
０ 引 言
属性约简是粗糙集 理论… 中的重要 内容之 一 ， 它刻画 了
信息系统中知识的本质部 分 。通 常情况 下 ， 似空 间中的 属 近
．
，
若 Ｐ Ｑ Ａ， Ｉｄ Ｑ Ｉｄ Ｐ 。 则 ｎ （ ） ｎ （ ）
设 Ｕ Ｉｄ Ｐ ＝ ｛ ］ ｌ ∈ Ｕ ／ （） ｎ ［ ｝表示不 可 区分关 系
启发 式信 息 ， 出一种 基 于知 识粒 度 的属性 约 简启发 式算 法 ， 算 法 的时 间复 杂度是 多项式的 。最后 提 该
通过例 子说 明 了该 算法 的有 效性 。
关 键词 ： 息 系统 ； 识 粒度 ； 信 知 重要 度 ； 属性 约 简 中 图分类号 ： Ｐ １ ． ３ Ｔ ３ １ １ 文献标 识码 ： Ａ
∈Ｕ ，） ∈ 。 ａ
定义４ 设 Ｓ＝（ Ａ ｕ，）是一个 信 息系统 ， ／ｎ （ ） ＝ Ｕ Ｉｄ Ａ ｛ ， ， ， ｝则 Ａ 的 知 识 粒 度 ， 为 Ｇ Ａ ， 义 为 ： … ， 记 Ｋ（ ） 定
Ｇ（ Ｋ） Ａ
／ Ｉ其 ∑ ｉ 中 ， ｉ ｕ
＝
Ｕ Ｉｄ Ｑ）表示 ， ／ｎ （ 简记 为 Ｐ＜ Ｑ 。 定义 ２ 设 Ｓ ＝ （ Ａ ｕ， ）是 一个信 息 系统 ， ∈Ａ， 果 ａ 如
同逐次选择最重要的属性增 加到核 中去 ， 到其粒 度等于 属 直
约简 。
ＩｄＡ一｛｝ ｎ（ ａ ）＝ＩｄＡ ， 。 ｎ （ ）则称 在Ａ中是冗余的 ， ， 口 否则 称 在
究 ］ 。综观各种属性约简算 法 ， 其基本 思想 一般 是利用 属
中［］ ＝｛ Ｙ∈Ｕ （ Ｙ ｌ ）∈ＩｄＰ ｝ ， ｎ （ ） 称为 Ｐ 等价类或 Ｐ 知识
颗粒。
令 Ｐ Ｑ Ａ 若对 Ｖ ， ， Ｘ∈Ｕ ＩｄＰ ， Ｙ∈Ｕ Ｉ （ ） ／ｎ （ ）存在 ／ ｄＱ ， ｎ 使 得 ｙ则称 Ｐ的划分 比 Ｑ更精细 ， ， 或者 Ｑ 的划分 比Ｐ 更
核是所有约 简的交集 。
如果每个属性 ａ ｅ Ａ在 Ａ中是必要 的， 则称 属 性集 Ａ的粒 度为止 ， 这时得到 的属性 子集便 构成 系统 的最 小 Ａ中是必 要的。
１ 信息系统与知识粒度
下面介绍信 息系统 中的几个概 念和有关定理 ［ 。 ７ ＿ 定义 １ 四元组 Ｓ＝（ Ａ， ｕ， 是一个信息系统 ， 中 ｕ 其 表示对 象的非空有 限集合 ， 称为论域 ； Ａ表示 属性 的非空有 限 集合； Ｖ＝ｕ ， 表示属性 。 的值域 ： Ａ ｕ× — 是信息函 数， 它为每个 对象 的每 个属性 赋予 一个信 息值 ， Ｖ。 Ａ， 即
ｎ
是由
．
（ ×置 ）
１
通常 ， Ｓ＝ （ Ａ， ｕ，
记为 Ｓ＝ （ Ａ 。 ｕ，）
也称为知识表达 系统或知识 Ａ， 简
决定 的等价关 系的基 数。
当Ｉ （ ）＝｛ ，） ∈Ｕ 时，／ｎ（ ） Ｉ ∈ｕ ｎＡ ｄ （ ｌ ｝ Ｕ Ｉ Ａ ＝｛ ｄ ｝
对于 Ｖａ ∈ Ａ， 以 定 义 ｕ上 的 一 个 等 价 关 系 ０ ： 可
Ｉｄ Ｐ ｎ （ ）在 ｕ上导 出的划分 ， 也称为 Ｐ的划 分或信息粒 度 ， 其
性并不是 同等重要的 ， 至某 些属 性是冗 余 的。冗余 属性 的 甚 存在 ， 会造成 资源的浪费 ， 不仅 而且也会 干扰人们做 出正确而 简洁的决策 。因此 ， 多学 者致力 于对 属性约 简算法 的研 有许
性集 Ａ是独立 的 ， 否则 ， Ａ是依赖的。 称 Ａ中所 有必要的属性组 成 的集合称为属性集 Ａ的核 ， 记作 Ｃ ｒ（ 。 ｏｅＡ） 定义 ３ 设 Ｓ ＝ （ Ａ ｕ， ）是一个 信 息系统 ， Ａ， 果 Ｐ 如 Ｉｄ Ｐ ｎ （ ）＝Ｉｄ Ａ ， Ｐ是独立的 ， ｎ（）且 则称 Ｐ是 Ａ的一个约简 。
Ｊ ｎ ０ ６ ｕ ｅ２ ０
种 基 于 知 识粒 度 的属 性 约 简 算 法
李 秀红 史开泉 ，
（． １ 山东经济学院 统计与数学学院， 山东 济南 ２０ １ ； ５０４ ２ 山 东大学 数 学与 系统科 学 学院 ， 东 济 南 ２０ ０ ） ． 山 ５ １０
摘
（ ｉｈｎ 一 ２ ＠ ｓｈ ．ｏ ｘｕ ｏ ｇ １７ ｏｕ ｃｍ） 要： 通过 引入 知识 粒度 的概 念 ， 对信 息 系统 中属 性 的 重要 度 进 行 了定 义 ； 以属性 重 要度 为 并
标准 ， 求出属性集 Ａ的核 ， 从核 出发 ， 再 根据 属性重要 度的不
Ｖ ∈ Ｕ Ｉ （ ）存在 Ｙ∈ Ｕ Ｉ （ ）使 得 Ｘ ／ ｄＰ ， ｎ ／ ｄＱ ， ｎ
ｙ且存 在 ，
∈Ｕ ＩｄＰ ， ∈Ｕ Ｉｄ Ｑ ， ／ｎ （ ） ／ｎ （ ）使得 ｃ ， Ｐ 则称 的划 分 比 Ｑ严格精 细 ， 或者 Ｑ的划分 比 Ｐ严格粗糙 ， Ｕ Ｉｄ Ｐ 用 ／ｎ （ ）＜
ｘ ｃ （ ，）＝，Ｙ８ ， 在 【 上产生 的划分为：／ ． Ｏ ￣ ｘ８ ｙｆ （ ，）０ 。 ， Ｕ ｏ＝
