２００８年第 ９期
计 算 机 与 现 代 化
ＪＩＳＵＡＮＪＩ ＹＵ ＸＩＡＮＤＡＩＨＵＡ 总第 １５７期
文章编号 ：１００６－２４７５（２００８）０９－００５１－０３
一
种 改进 的启发式离散化算法及 应用
彭佳文
（广西工学院信 息网络 中心 ，广西 柳 州 ５４５００６）
摘 要 ：Ｎｇｕｙｅｎ Ｓ．Ｈ提 出的布 尔逻辑和粗糙 集理论相 结合 的离散 化算法是粗糙 集理论 中的 离散化 算法在 思想上 的重 大突
破 。通过定 义分界点 来区分 Ｎｇｕｙｅｎ Ｓ．Ｈ 离散化算法 中定义的断 点对 决策 系统 的分辨 关 系是否有 贡献 ，并仅取 分界点 集
作为初始 断点集 ，使得初始 断点数 目较 大幅度地 降低 ，提 出了一种改进的启发 式离散 化算法并应用 于一 个 实际的决策 系
统的连 续属性 离散化 。应 用实例表 明改进算法较 大程度地减小 了算 法空间复 杂性和 时间复杂性 ，具有正确性和 实用性。
关键词 ：粗糙 集 ；离散化 ；决策 系统 ；分界点
中圈分类号 ：ＴＰ３０１．６ 文献标识码 ：Ａ
Ａｎ Ｉｍｐｒｏｖｅｄ Ｈｅｕｒｉｓｔｉｃ Ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｄｉｓｃｒｅｔｉｚａｔｉｏｎ ａｎｄ Ｉｔｓ Ａｐｐｌｉｃａｔｉｏｎ
ＰＥＮＧ Ｊｉａ．ｗｅｎ
（Ｎｅｔ Ｉｎｆｏｒｍａｔｉｏｎ Ｃｅｎｔｅｒ，Ｇｕａｎｇｘｉ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ，Ｌｉｕｚｈｏｕ ５４５００６，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｔｈｅ ｄｉｓｃｒｅｆｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｏｆ ｒｏｕｓｈ ｓｅｔ ａｎｄ ｂｏｏｌｅａｎ ｒｅａｓｏｎｉｎｇ ａｐｐｒｏａｃｈ ｐｒｅｓｅｎｔｅｄ ｂｙ Ｎｇｕｙｅｎ Ｓ．Ｈ ｉｓ ａ ｍｏｍｅｎｔｏｕｓ
ｂｒｅａｋｔｈｒｏｕｇｈ ｏｆ ｔｈｉｎｋｉｎｇ ｉｎ ｔｈｅ ｄｉｓｅｒｅｔｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｏｆ ｒｏｕｇｈ ｓｅｔ ｔｈｅｏｒｙ．Ｂｙ ｄｅｆｉｎｉｎｇ ｄｉｖｉｄｉｎｇ ｐｏｉｎｔ，ｗｅ ｃａｎ ｄｉｆｆｅｒｅｎｔｉａｔｅ ｅａｃｈ
ｏｆ ｔｈｅ ｂｒｅａｋｉｎｇ ｐｏ ｉｎｔｓ ｄｅｆｉｎｅｄ ｂｙ Ｎｇｕｙｅｎ Ｓ．Ｈ ｄｉｓｅｒｅｔｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｗｈｅｔｈｅｒ ｈａｓ ｃｏｎｔｒｉｂｕｔｉｏｎ ｔＯ ｔｈｅ ｄｉｆｆｅｒｅｎｔｉａｔｉｏｎ ｒｅｌａｔｉｏｎ ｏｆ ｔｈｅ
ｄｅｃｉｓｉｏｎ ｓｙｓｔｅｍ．Ａｎｄ ｂｙ ｃｈｏｏｓｉｎｇ ｔｈｅ ｄｉｖｉｄｉｎｇ ｐｏｉｎｔ ｓｅｔ ａｓ ｔｈｅ ｏｒｉｇｉｎａｌ ｂｒｅａｋｉｎｇ ｐｏ ｉｎｔ ｓｅｔ ｏｎｌｙ，ｗｅ ｃａｎ ｄｅｃｒｅａｓｅ ｔｈｅ ｎｕｍｂｅｒ ｏｆ Ｏ—
ｒｉ￣ｎａｌ ｂｒｅａｋｉｎｇ ｐｏｉｎｔ ｔｏ ａ ｂｉｇｇｉｓｈ ｄｅｇｒｅｅ．Ｔｈ ｉｓ ｐａｐｅｒ ｉｎｔｒｏｄｕｃｅｓ ａＩＩ ｉｍｐｒｏｖｅｄ ｈｅｕｒｉｓｔｉｃ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｄｉｓｃｒｅｔｉｚａｔｉｏｎ ａｎｄ ａｐｐｌｉｅｓ ｉｔ ｔｏ
ｄｉｓｃｒｅｔｉｚａｔｉｏｎ ｏｆ ｃｏｎｔｉｎｕｏｕｓ ａｔｔｒｉｂｕｔｅｓ ｏｆ ａｎ ａｃｔｕａｌ ｄｅｃｉｓｉｏｎ ｓｙｓｔｅｍ．Ｔｈｅ叩 ｐｌｉｃａｔｉｏｎ ｃａｓｅ ｉｎｄｉｃａｔｅｓ ｔｈａｔ ｔｈｅ ｉｍｐｒｏｖｅｄ ａｌｇｏｒｉｔｈｍ Ｃａｌｌ
ｒｅｄｕｃｅ ｐｒｅｆｅｒａｂｌｙ ｔｈｅ ｓｐａｃｅ ｃｏｍｐｌｅｘｉｔｙ ａｎｄ ｔｉｍｅ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ｔｈｅ ｄｉｓｃｒｅｔｉｚａｔｉｏｎ ａｎｄ ｈａｓ ｔｈｅ ｃｏｒｒｅｃｔｎｅｓｓ ａｎｄ ｐｒａｃｔｉｃａｂｉｌｉｔｙ．
Ｋｅｙ ｗｏｒｄｓ：ｒｏｕｇｈ ｓｅｔ；ｄｉｓｃｒｅｔｉｚａｔｉｏｎ；ｄｅｃｉｓｉｏｎ ｓｙｓｔｅｍ ；ｄｉｖｉｄｉｎｇ ｐｏｉｎｔ
０ 引 言
Ｒｏｕｇｈ集理论 已在数据挖掘领域 得到 了广泛 的
应用 ，但因它不能直接处理连续 属性值 ，当用 Ｒｏｕｇｈ
集方 法处理 这 些数 据时 ，须 首先对 数 据进行 离散 化 预
处理¨剖。Ｎｇｕｙｅｎ Ｓ．Ｈ提 出的布尔逻辑 和粗糙集理
论相结合的离散化算法 刮是粗糙集理论 中的离散化
算法在思想上的重大突破。该算法的主要思想是 ：让
其中一个或几个断点去 区分两个 实例 的不 同的不可
分辨关系 ，在保持信息系统的不可分辨关系不变的前
提下 ，尽量以最少数 目的断点集能够把所有实例间的
分辨关系区分开。但该算法 由于把可能存在的一部
分对决策系统 的分辨关 系并无 贡献 的断点选人初始
断点 集 ，所 确定 的初 始断 点 集 较 大 ，这 无 疑 增 加 了算
法 的空间复杂度和时间复杂度。本文通过定义分界
点来对原算法定义 的断 点是否对决策 系统 的分 辨关
系有贡献进行 区分 ，并仅 取分界点集 作为初始 断点
集 ，使 得 初 始 断 点 数 目较 大 幅 度 地 降 低 ，从 而 对
Ｎｇｕｙｅｎ Ｓ．Ｈ离 散化算 法进 行 了改进并 应 用 于一 个 实
际的决策系统的连续属性离散化。
１ 布尔逻辑和粗糙集理论相 结合的离
散化算法
数据离散化过程本质上就是采用一定 的断点集
合对决策系统 的属性空 间进行划分ｌ－５ Ｊ。为了提高 系
统的聚类能力 ，增强系统对数据 噪音 的鲁棒性 ，应该
采用尽可能少 的断点来完成划分过程。从这一角度
来说 ，在保 证 系统 分 辨 关 系 的前提 下 ，用 最 小 的结果
收稿日期：２００７－０８－２９ ·
基金项 目：湖南省科技厅科技计划项 目（０５ｊＴ１０１３）
作者简介 ：彭佳文（１９６７一）。男 ，湖南永 州人 ，广西工学院信息 网络中心工程师 ，硕士 ，研究方 向：数据挖掘，人 工智 能。
