（计算机软件与理论专业论文）连续属性离散化方法研究.pdf

连续属性离散化方法研究 摘要 实际数据库中存在较多的连续型数值属性，而现有的很多数据挖掘方法只 能处理离散型的属性，因而需要对连续属性进行离散化，因此，连续属性离散 化方法成为数据挖掘领域重要的基础性工作，直接影响到数据挖掘的质量。已 经出现了多种连续属性离散化算法，且各有特色和优劣。本文结合粗糙集合和 信息熵的相关概念，开展连续属性离散化研究，并提出一种新的离散化方法。 论文的主要工作如下： ( 1 ) 综述了数据挖掘、信息系统和信息熵的基本理论，介绍了粗糙集合的 重要表示形式一一决策表，简述信息论的历史和发展，阐述了信息熵的基本概 念。 ( 2 ) 系统分析了连续属性离散化的相关研究成果，并做了必要的比较。 ( 3 ) 提出了区间类信息熵的概念 续属性的离散化算法一一d i c e 算法， 结合粗集的有关理论，提出一种处理连 并从理论上对d i c e 算法进行了分析。 ( 4 ) 实现了本文提出的d i c e 算法，并以实际数据对d i c e 离散化算法与 c 4 5 自带的离散化方法进行比较，给出了实验分析结果并加以说明。 关键词：数据预处理，信息熵，粗糙集合，离散化。 s t u d y 0 1 1 1t h ed i s c r t i z a t i o no fc o n t i n u o u sa t t r i b u t e s a b s t r a c t i nt h er e a ld a t a b a s e s ，t h ed a t ar e c o r d sa r ec o m p o s e do fm a n ya t t r i b u t e sw i t h c o n t i n u o u sv a l u e ，s i n c em o s to ft h ee x i s t i n gm e t h o do fd a t am i n i n ga r ec a p a b l eo f d e a l i n gw i t ht h ed i s c r e t ea t t r i b u t e so n l y , i ti sn e c e s s a r yt od i s c r e t i z et h ec o n t i n u o u s a t t r i b u t e sf i r s t l y d u et ot h ea b o v e m e n t i o n e df a c t ，t h es t u d yo ft h em e t h o df o r c o n t i n u o u sa t t r i b u t ed i s c r e t i z a t i o nb e c o m e sa ni m p o r t a n tf u n d a m e n t a lw o r kt ot h e r e s e a r c ha r e ao fd a t am i n i n g ，w h i c hc a ng i v ead e e pi n f l u e n c eo nt h er e s u l to fd a t a m i n i n gp r o c e s s m a n yk i n d so fm e t h o df o rt h ec o n t i n u o u sa t t r i b u t ed i s c r e t i z a t i o n h a v eb e e np r o p o s e d ，e v e r yo n eh a si t sp r o p e r t i e sa n dp r i o r i t i e s i nt h i st h e s i s ，s o m e c o n c e p t s o fr o u g hs e t sa n di n f o r m a t i o ne n t r o p ya r ec o m b i n e dt o s t u d yt h e d i s c r e t i z a t i o no fc o n t i n u o u sa t t r i b u t e s ，a n dan e we f f i c i e n td i s c r e t i z a t i o nm e t h o di s f i r s t l yp r o p o s e d t h em a i nc o n t e n t so f t h i st h e s i sa r el i s ta sf o l l o w ： ( 1 ) t h eb a s i ct h e o r yo fd a t am i n i n g ，i n f o r m a t i o ns y s t e ma n di n f o r m a t i o ne n t r o p yi s r e v i e w e di nd e t a i l af u l li n t r o d u c t i o ni sg i v e nt ot h ed e c i s i o nt a b l e ，av e r yi m p o r t a n t c o n c e p tt od e s c r i b et h er o u g hs e t s a l s o ，s o m ed e s c r i p t i o n sa r eb r i e f l yr e v e a l e do nt h e h i s t o r ya n dd e v e l o p m e n to f t h ei n f o r m a t i o nt h e o r y , a n dt h ei n f o r m a t i o ne n t r o p y ( 2 ) t h er e l a t i v er e s u l t sf r o mt h er e s e a r c ho fc o n t i n u o u sa t t r i b u t ed i s c r e t i z a t i o na r e s y s t e m a t i c a l l ya n a l y z e da n df u l l yc o m p a r e de a c ho t h e r | ( 3 ) au s e f u lc o n c e p t ，i n t e r v a lc l a s si n f o r m a t i o ne n t r o p y , i sp r o p o s e di nt h ep r e s e n t t h e s i s c o m b i n e dw i t ht h er e l a t i v et h e o r yo fr o u g hs e t s ，a ne f f i c i e n tm e t h o df o rc o n t i n u o u s a t t r i b u t ed i s c r e t i z a t i o nb a s e do ni n t e r v a lc l a s si n f o r m a t i o ne n t r o p y ( d i c e ) i sd r a w no u t t h e n ，t h e o r e t i c a la n a l y s i si sp e r f o r m e do nt h ed i c em e t h o d ( 4 ) t h ed i c em e t h o d ，p r o p o s e di n t h ep r e s e n tt h e s i s ，i s s u c c e s s f u l l ya p p l i e dt o d i s c r e t i z e dt h er e a la v a i l a b l ed a t a b a s e s b a s e do nt h ea p p l i c a t i o n st od e a lw i t ht h er e a l d a t a b a s e s s o m ec o m p a r i s o n sa r em a d eb e t w e e nt h ed i c em e t h o da n dt h es e l f - s u s t a i n e d d i s c r e t i z a t i o nm e t h o do ft h ec 4 5a l g o r i t h m ，t h e nc o r r e s p o n d i n ga n a l y s i sa n de x p l a i na r e p r e s e n t e do nt h ee x p e r i m e n t a lr e s u l t s k e y w o r d s ：d a t ap r e p r o c e s s i n g ，i n f o r m a t i o ne n t r o p y ，r o u g hs e t s ，d i s c r t i z a t i o n 插图清单 图1 1k d d 的处理过程模型 图5 1d i c e 系统的组成图 图5 。2d i c e 系统基本的调用格式 图5 3t e s t n a m 具体格式 图5 - 4t e s t d a t 具体格式 图5 5t e s t t e s 具体格式 图5 - 6d i c e 处理结果 图5 7c 4 5 处理结果 图5 8 记录的响应时间比较曲线图 图5 9 记录的决策树分支数比较图 图5 - 1 0 记录的决策树误分率比较图 一弱弘粥曲蚰舛拍镉 表4 1 表4 2 表4 3 袭4 4 表4 5 表4 6 表4 7 表4 - 8 表5 - 1 表5 - 2 表5 - 3 表格清单 决策表的一般形式 离散化前的样本数据决策表 区间类信息熵取值与区间内类的比重关系 用d i c i e 算法离散化后的决策表 用c 4 5 算法离散化后的决策表 d i c i e 算法与c 4 5 算法离散化后的断点区间数比较 d i c i e 算法与c 4 5 算法离散化后的区间类信息熵比较 d i c i e 算法与c 4 5 算法离散化前后决策表一致性比较 区间类信息熵取值与区间内类的比重关系 记录的响应时间 记录的决策树分支数和误分率斟舶刀船凹凹如”蚪郇 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所 知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得 盒魍些太堂 或其他教育机构的学位或证书而使t f j 过的材料。与我一同工 作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 一躲闷复6 小舯 学位论文版权使用授权书 本学位论文作者完全了解金魍王些盍鲎有关保留、使用学位论文的规定，有权保留并向国 家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权金目b 王些太堂可 以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手 段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名 签字日期：年月日 学位论文作者毕业后去向 工作单位： 通讯地址： 舀04， 臃、明 椰咖 致谢 首先，衷心感谢我的导师胡学钢教授在整个论文阶段给予的悉心指导和帮 助。导师不断从学业上、生活上关心我，为我创造了良好的工作和学习环境， 使我在理论和实践两个方面都得到了良好的锻炼。没有导师付出的辛勤劳动， 本论文是不可能完成的。在这几年的学习生活中，胡老师严谨的治学态度、丰 富渊博的知识和豁达的人格给我留下了深刻的印象，特别是受到胡老师那种手 不释卷、日日勤勉的工作作风的熏陶，将使我终身受益。 同时，我也深深地感谢计算机学院人工智能与知识挖掘研究室的王浩教授。 他也给了我大量的指导、关怀和帮助，他的真知灼见使我受益很多。还要感谢 张晶、张玉红、吴共庆、王德兴、周红鹃、杨静、李培培等。大家一起对知识 挖掘课题进行研讨，集思广益，对于构思我的论文有很大的启发。此外，我还 要感谢计算机学院的王新生老师、徐静老师等为我所付出的辛勤工作! 我还要感谢我的家人对我的关心和鼓励。 最后，还有许多老师、同学和朋友曾经给过我很大的帮助，他们的名字不 能一一尽述，在此表示衷心的感谢! 作者：阙夏 2 0 0 6 年5 月 第一章绪论 本章概述了k d d 的研究和发展概况，指出了本研究工作的目的和意义。首 先介绍了k d d 的基本概念和k d d 的处理过程模型，并且详细阐述了k d d 的关 键步骤数据挖掘。然后对数据挖掘的定义、数据挖掘的对象和数据挖掘的方 法进行了介绍。此外还介绍了本文的课题来源和内容组织。 1 1 引言 近半个世纪以来，计算机和信息技术的高速发展给人类社会带来了巨大的 变化与影响，数据成为最重要的战略资源。近年来，条形码的推广、o r c 等技 术的出现、企业和政府事务管理以及高速数据采集工具的发明，都提供了大规 模的数据库。数据库应用的规模、范围和深度不断扩大，已经从点( 单台机器) 、 线( 局域网) 发展到面( 网络) ，甚至到全球的i n t e r n e t 全球信息系统。千千万 万个数据库被用于商业管理、政府办公、科学研究和工程开发等，并且这一势 头仍将持续发展下去，使得数据及其信息量以指数形式增长。根据粗略估计， 早在2 0 世纪8 0 年代，全球信息量每隔2 0 个月就要增加一倍。而进入9 0 年代， 全世界所拥有的数据库及其所存储的数据规模增长更快。9 0 年代互联网的发展 与普及，以及随之而来的企业内部网、企业外部网以及虚拟私有网的产生和应 用，使整个世界互联形成一个小小的地球村，人们可以跨越时空，在网上交换 信息和协作工作。这样展现在人们面前的已不是局限于本部门、本单位和本行 业的庞大数据库，而是浩瀚无垠的信息海洋。这对人类形成一个新的挑战。在 这些大量数据的背后隐藏了很多具有决策意义的信息。那么如何及时得到这些 有用的知识呢? 如何才能不被信息的汪洋大海所淹没并提高信息利用率昵? 数据库知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e s ，简称k d d ) 技术应运 而生j 12 i ，并得以蓬勃发展，越来越显示出其强大的生命力。k d d 是一门很广义 的交叉学科，汇聚了不同领域的研究者，尤其是数据库、人工智能、统计学、 可视化等方面的学者和工程技术人员。一般将k d d 中进行知识发现的阶段称为 数据挖掘( d a t am i n i n g ，d m ) ，数据挖掘是k d d 最关键的步骤，也是技术难点 所在。所以某些应用领域对数据挖掘与k d d 不加区分地使用，某种意义上二者 可看作同一个概念。 随着k d d 在国际上的兴起，我国也积极地开展了相应的研究和应用。1 9 9 3 年国家自然科学基金首次支持该领域的研究项目。目前国内许多学术会议，如 数据库学术会议、机器学习会议等，也都将k d d 列为重要的研究方向。国内的 许多科研单位和高等院校竟相开展数据挖掘与知识发现的基础理论及其应用研 究。我校是国内较早进行知识发现的研究单位之一，八十年代术期以来相继在 国家自然科学基金资助下开展了“从关系数据库中提取领域知识的自动化获取 研究”，在国家教委博士学科点专项科研基金资助下开展了“从大规模数据库中 自动提取领域知识的算法与实现研究”，以及在国家自然科学基金项目“基于粗 糙集合理论的概念格模型研究”等。本文正是基于上述背景下的开展的研究。 1 2数据库中知识发现k d d 的定义 1 2 1k d d 的定义 众多的学者根据自己的对k d d 的认识和理解，下了很多的定义，而其中公 认比较完整、深刻和全面的一个定义是由u m f a y y a d ，gp i a t e t s k y s h a p i r o 和 ps m y t h 等人在k d d 9 6 国际会议的会议论文( ( f r o md a t am i n i n gt ok n o w l e d g e d i s c o v e r y ) ) 一文中将k d d 定义为： “t h en o n t r i v i a lp r o c e s so fi d e n t i f y i n gv a l i d ，n o v e l ，p o t e n t i a l l yu s e f u l ， a n du l t i m a t e l yu n d e r s t a n d a b l ep a t t e r n si nd a t a 1 3 j 即k d d 指大量数据中获取有效的、新颖的、有潜在作用的和最终可理解的 模式的非平凡过程。还有很多和这一术语相近似的术语，如数据挖掘( d a t a m i n i n g ) 、数据分析( d a t aa n a l y s i s ) 、数据融合( d a t af u s i o n ) 以及决策支持 ( d e c i s i o ns u p p o r t i n g ) 等。 上述k d d 的定义刻画了知识发现的基本过程，下面我们来对这个定义进行 详细的解释： 数据：数据是一系列事实的集合f ，可以是个或一组数据库、数据仓库、 电子表格或其他类型的信息库，也可以是在数据上进行数据清理、集成和规约 后得到的数据这是k d d 处理的最常用的数据形式； 有效性：通过k d d 从当前数据所发现的模式对于新的数据仍保持有一定的 可信度，否则k d d 就毫无作用； 新颖性：经过k d d 提取出的模式必须是新颖的，至少对系统来说应该如此。 模式是否新颖可以通过两个途径来衡量：其一是在所得到的数据方面，通过对 比当前得到的数据和以前的数据或期望得到的数据之间的比较，来判断该模式 的新颖程度；其二是在其内部所包含的知识方面，通过对比发现的模式与已有 的模式的关系来进行判断； 潜在作用：提取出的模式应该是有意义的，有潜在的应用价值； 可理解：k d d 的一个目标就是将数据库中隐含的模式以容易理解的形式表 现出来，从而帮助人们更好地理解数据库中所包含的信息。目前它主要体现在 简洁性上； 模式：模式是指用语言l 来表示的一个表达式e ，它可用来描述数据集f 的某个子集f e ，e 作为一个模式要求它比对数据子集f e 的枚举要简单( 所用的 描述信息量要少) ；它可用来描述数据集的特性，根据某种兴趣度度量，并于数 据挖掘模块中进行交互挖掘，阻便识别和表示知识的真正有趣的模式； 非平凡：是指它已经超越了一般封闭形式的数量计算，包括对结构、模式 和参数的搜索，它具有一定程度的智能性和自动性； 过程：过程是在k d d 中包含的步骤，如数据的预处理、模式搜索、知识表 示及知识评估、过程优化等。 目前，k d d 的研究涵盖了多个领域的多种知识发现的方法，已经可以发现 关联规则、分类规则和聚类规则等多种规则类型。此外，随着数据仓库技术的 发展和应用，联机分析处理( o n - l i n e a n a l y t i c a lp r o c e s s i n g ，简称o l a p ) 也发 展到了一个新的高度 4 , 5 1 。将o l a p 与k d d 结合用于数据分析和知识发现是一个 新的研究方向。 1 2 2k d d 的处理过程 人们进行的关于k d d 的研究是为了将知识发现的研究成果应用于实际数据 处理中，为科学的决策提供支持。然而，目前所进行的关于k d d 的研究，大多 只着眼于对数据挖掘阶段的研究，而忽视了其他方面的研究。事实上，k d d 首 先是一个处理过程，如果仅仅着重于数据挖掘，可能就看不到在数据处理过程 中的数据提取、组织和显示方式的难度。数据挖掘所完成的工作对于整个知识 发现的过程来说，只是其中的一部分，因此对k d d 中其它阶段及处理过程的研 究也是非常重要的。 目前人们对整个处理过程并没有给出非常清楚的划分，而建立合适的处理 过程模型能将各个处理阶段有机地结合在一起，以便于人们丌发及使用k d d 应 用系统。比较有代表性的模型有三种l j j ： 第一种是u s a m a m f a y y a d 等人给出的面向多处理阶段模型i ”。 第二种是g e o r g eh j o h n 给出的多处理阶段模型。 第三种是b r a c h m a n & a n a n d 提出的以用户为中心的处理模型。 为了使k d d 能更好地应用于实践，下面以第一种面向多阶段处理过程的 k d d 处理过程模型为例进行简要地说明。本文后面有关的讨论也是针对这种模 型进行论述的。 图l _ 1k d d 的处理过程模型 图1 1 是u s a m am f a y y a d 等人给出的处理模型。该处理模型把k d d 过程 分为九个处理阶段：数据准备、数据选择、数据预处理、数据规约、k d d 目标 确定、挖掘算法确定、数据挖掘、模式解释评价及知识表示合并。 1 数据准备：了解k d d 相关领域的有关情况，包括实际应用中的预备知 识和目标，熟悉有关的背景知识，并弄清楚用户的要求。 2 数据选择：根据用户要求从任务相关数据库中提取与k d d 要求相关的 数据，k d d 主要从这些数据中进行知识提取。在此过程中，会使用一些数据库 操作对数据进行处理，建立一个目标数据集。 3 ，数据预处理：主要是对阶段2 产生的数据进行再加工，检查数据的完整 性和一致性，利用统计方法等对丢失的数据进行填补，去除噪音数据和空白数 据域，考虑时间顺序和数据变化等。 4 数据转换：对经过预处理的数据，根据知识发现的任务对数据进行再处 理，主要通过投影或数据库中的其他操作减少数据量或找到数据的不变模式。 5 确定k d d 目标：根据用户要求，确定k d d 发现的知识类型。因为对 k d d 的不同要求，会在具体的知识发现过程中采用不同的知识发现算法。 6 确定知识发现算法：根据阶段5 所确定的任务，选择合适的数据挖掘算 法，包括选取合适的模型和参数，并使得挖掘算法与整个k d d 的评判标准相 致。 7 数据挖掘：运用选定的挖掘算法，搜索或产生一个特定的感兴趣的模式 或数据集，从数掘中提取出用户所需要的知识，这些知识可以用某种特定的方 式表示或使用一些常用的表示方式，如产生式规则等。 8 模式解释，评价：对发现的模式进行解释，去掉多余的不切题意的模式， 转换成某个有用的模式，以便于用户理解。在此过程中，为了耿得更为有效的 知识，可能会返回前面处理中的某些步骤，以便反复提取，从而提取出更有效 的知识。 9 知识表示台并：将发现的知识以用户可理解的方式呈现给用户或合并到 系统中，也包含对知识的一致性检查。 在上述的每个处理阶段，k d d 系统提供处理工具完成相应的工作。在对挖 掘的知识进行评测后，根据结果可以决定是否重新进行某些处理过程，在处理 的任意阶段都可以返回到前面的某个阶段进行再处理。 1 3知识发现的核心一一数据挖掘 数据挖掘( d a t am i n i n g ) 是从大型数据库或数据仓库中提取人们感兴趣的 知识，这些知识是隐含的、事先未知的、潜在的、有用的信息。其广义的定义 是从存放在数据库、数据仓库或其他信息库中的大量数据中挖掘有趣的知识过 程。 许多人把数据挖掘视为数据库知识发现( k d d ) 同义词。而另一些人则是 把数据挖掘视为k d d 过程的一个基本步骤。数据挖掘步骤可以与用户或知识库 交互，把有趣的模式提供给用户，或作为新知识存放在知识库中。根据这个观 点，数据挖掘只是整个知识发现过程中的一步，并且是最重要的一步，因为它 能发现隐藏的模式。本文采用这一观点。 1 3 1 数据挖掘的对象 根据信息存储格式，用于挖掘的对象有：关系数据库、面向对象数据库、 空间数据库、时序数据库、文本数据源、多媒体数据、异质数据库、遗产数据 库，以及w e b 数据源等等。 1 3 2 数据挖掘的方法 数据挖掘的方法通常可以分为两大类：一类是统计型，常用的技术有概率 分析、相关性分析、聚类分析等；另一类是人工智能中的机器学习型，通过训 练和学习大量的样品集得到需要的模式或参数。数据挖掘的方法大致有：概念 格、粗糙集合理论、决策树、遗传算法、神经网络、贝叶斯网络、以及统计分 析等等。 1 4 本文研究背景和内容组织 1 4 1 本文课题来源 本课题来源于安徽省自然科学基金课题( 项目编号0 5 0 4 2 0 2 0 7 ) 一一“基于 概念格的分布式知识发现的关键问题研究”和合肥工业大学科研发展基金课题 ( 项目编号0 5 0 5 0 4 f ) 一一“基于概念格的半结构化数据中知识发现的关键问题 研究”。 1 4 2 本文的内容组织 本文由六章组成： 第一章：主要简述数据库知识发现产生的原因以及发展前景，概述知识发 现和其它相关技术的异同，展望知识发现的最新发展情况，并详细阐述了知识 发现的核心技术数据挖掘及其挖掘的对象、挖掘的方法等。 第二章：本章主要介绍粗糙集合有效的知识表达方式信息表。首先对知 识利用分类的概念进行描述，然后对信息表描述的知识表达进行介绍，并加以 形式化的描述，再对决策表这种特殊的信息表进行描述。此外，对信息熵理论 的起源和发展进行了阐述。这一章是我们算法的基础。 第三章：本章首先介绍了连续属性离散化的必要性，离散化算法的任务与 目标，明确了一个成功的离散化算法应该具备的几大特性：然后，介绍离散化 的发展历程，介绍了几种经典的离散化算法；最后，根据离散化算法的几种不 同的分类标准，分别介绍了离散化算法在这些标准下的分类情况。 第四章：本章介绍了基于粗糙集的有关理论提出的一种新的连续属性离散 化方法( d i s c r e t i z a t i o nb a s e do ni n t e r v a lc l a s si n f o r m a t i o ne n t r o p y ) 。首先介绍度 量属性断点区间离散化效果的区间类熵的概念，然后根据已有数据的取值构成 候选断点区间集，在控制区间类熵小于给定的某个值( 的前提下对相邻的区间进 行合并。最后通过实际的数据分析，说明该算法与经典的离散化算法相比，离 散化效果更好，更有利于下一步的分析工作。 第五章：本章主要介绍d i c e 算法原型系统的实现和实验分析的结果比较。 首先，介绍了系统的分析和设计；然后是介绍使用d i c e 算法系统的用户手册， 包括系统调用的方式、调用的参数说明等等；最后，通过处理实际的大学生成 绩数据和四个u c i 数据集，将d i c e 离散化算法与c 4 5 自带的离散化方法进行 6 比较，给出了实验处理结果并加以说明。 第六章：全文的总结。对本文的主要研究工作进行简要的阐述和说明，并 对基于粗集和区间类信息熵的d i c e 算法模型的研究工作中需要进一步解决的 问题进行了探讨和展望。 第二章信息系统和信息熵 本章主要介绍粗糙集合有效的知识表达方式信息表。首先对知识利用分 类的概念进行描述，然后对信息表描述的知识表达进行介绍，并加以形式化的 描述，再对决策表这种特殊的信息表进行描述。此外，对信息熵理论的起源和 发展进行了阐述。这一章是我们算法的基础。 2 1 信息系统 2 1 1 知识的分类概念 知识就是人类和其他物种所固有的分类能力；分类是推理、学习与决策中 的关键问题i 。因此，粗糙集合理论假定知识是一种将对象进行分类的能力。这 里的“对象”指我们所能言及的任何事物，比如实物、状态、抽象概念、过程和时 刻等等。即知识必须与具体或抽象世界的特定部分相关的各种分类模式联系在 一起，这种特定部分称之为所讨论的全域或论域矾u n i v e r s e ) 。对于全域及知识 的特性并没有任何特别假设。事实上，知识构成了某一感兴趣领域中各种分类 模式的一个族集( f a m i l y ) ，这个族集提供了关于现实的显事实，以及能够从这些 显事实中推导出隐事实的推理能力。 为数学处理方便起见，在下面的定义中用等价关系来代替分类 9 1 。 定义2 1 一个近似空间( a p p r o x i m a t es p a c e ) ( 或知识库) 定义为一个关系系统 ( 或二元组) 胙( 以胄) ，其中u s a 是一个称为全域或论域( u n i v e r s e ) 的有限集合， 月是u 之上等价关系的一个族集。 定义2 2设p c r 且p r o ，p 中的所有等价关系的交集称为p 之上的一种不可 区分关n ( i n d i s e r n i b i l i t yr e l a t i o n ) ，记作i n d ( p ) ， x i n d ( p ) 2n x r r p 在本文一般用大写字母p ，q ，r 等表示一个关系，用大写黑体字母p ，q ，r 等表示关系的族集； x r 或r ) 表示关系r 中包含元素z u 的概念或等价类。 定义2 3给定近似空间肛( u 曰) ，子集x c u 称为u 上的一个概念( c o n c e p t ) ， 形式上，空集0 也视为一个概念；非空子族集p c _ r 所产生的不可区分关系i n d ( p ) 的所有等价类的集合即u t n d ( p ) ，称为基本知识( b a s i ck n o w l e d g e ) ，相应的等价 类称为基本概念( b a s i cc o n c e p t ) ；特别地，若关系q e r ，则关系q 就称为初等知 识( e l e m e n t a r yk n o w l e d g e ) ，相应的等价类就称为初等概念( e l e m e n t a r yc o n c e p t ) 。 根据上述定义可知，概念即对象的集合，概念的族集( 分类) 就是u 上的 知识，u 上分类的族集可以认为是u 上的一个知识库，或说知识库即是分类方 法的集合。 2 1 2 信息系统 近年来，知识表示的研究引起了广泛的注意。目前，常用的知识表示方法 有逻辑模式、框架、语意网络、产生式规则、状态空间、剧本等，这些是知识 工程需要研究的内容。本节我们将介绍一种基于信息表的知识表达形式，它是 r o u g hs e t s 理论中对知识进行表达和处理的基本工具 1 0 1 。 在人工智能研究中，一个实例( 现实世界中的一个对象或个体) 经常使用 属性值对的集合来表示，实例集就是这样的实例集合，记为u 。u 可以被划分 为有限个类蜀，局，蜀，使得 墨u ，蜀o ，置n x i = o ( j 考) ，( f ，产1 ，2 ，n 且u 2 。 信息表知识表达系统的基本成分是研究对象的集合，关于这些对象的知识 是通过指定对象的属性( 特征) 和它们的属性值( 特征值) 来描述的。一般的， 一个信息表知识表达系统s 可以表示为： 。产 玑r ，e p 。 这里，u 是对象的集合，也称为论域，r = c u d 是属性集合，子集c 和d 分别称为条件属性集和结果属性集，其中条件属性集c = c ，c 2 ，c 。) ，c k ( k = l ， 2 ，m ) 均为连续属性，结果属性集d a ；肛u 是属性值的集合，其中以 表示属性r e r 的属性值范围；再u r 一矿表示一爷信息函数，指定u 中每一对 象的属性值。 为了直观方便，u 也可以写出一个表，纵轴表示实例标记，横轴表示实例 属性，实例标记与属性交汇点就是这个实例在这个属性的值。这个表称为信息 袁，是表达描述知识的数据表格。 对于每个属性子集b r ，我们定义一个不可区分关系( 不可分辨二元关系) i n d ( b ) ，即 i n d ( b ) = ( x ，少) 1 ( x ，y ) e 泸，vb 召( 6 ( x ) 。b ( y ) ) 。 显然，i n d ( b ) 是一个等价关系，且 i n d ( b ) = n 删d ( 6 ) 。 口 每个子集b g r 也可称为一个属性，当b 是单元素集时，称b 为原始的，否 则称b 是复合的。属性b 也可以认为是用等价关系( 在该属性上的取值相等) 表示知识的一个名称，称为标识属性。一个表可以看作是定义的一个等价关系 簇，即知识库。 实际上，信息表这种数据表格知识表达系统是对客观对象的描述和罗列， 表达的是属于说明性的知识。当信息表包含的数据足以反映论域的时候，通过 属性所对应的等价关系就可以体现论域中的过程知识，即概念之间的逻辑关系 或规则知识。事实上，从信息表所表达的浣明性知识中发现过程性知识( 规则 知识) 就是知识发现的研究内容。 用信息表来表示知识，我们对系统的实际语意、表中的取值的具体含义内 容并不感兴趣。实际上，表中的属性都是从现实问题中采集到的，是对客观对 象属性的抽象描述。我们以后将把信息表中的属性值仅当作数据来研究。下面， 我们再对决策表这种数据表格知识表达系统作形式化的讨论。 2 1 3 决策表 决策表i lo 是一类特殊且重要的知识表示系统，也是一种特殊的信息表，它 表示当满足某些条件时，决策( 行为、操作、控制) 应当如何进行。决策表可 以定义如下： 定义2 4一个决策表是一个信息表知识表达系统s = 阢r ，以户，r = c u d 是属 性集合，子集c 和d 分别称为条件属性集和结果属性集，d o 。 条件属性c 和结果属性d 的等价关系i n d ( c ) 和i n d ( d ) 的等价类分别被称 为条件类和决策类。 一个决策表中的结果属性有时是唯一的，称为单一决策；有时是不唯一的， 称为多决策。对于具有多个结果属性的多决策表，在处理时，往往需要将之变 换为单一决策的决策表。我们可以通过如下两种方法将多决策的决策表变换为 单一决策的决策表： 方法一如果决策表s = 阢r ，k 户，r = c u d 是属性集合，子集c 和d 分别称为条件属性集和结果属性集，且d = d b 出，矗) ，则可以将决策表分解 为行个不同决策的单一决策表 s - ，& ， ，其中s = ，u 是论域， r ，= c u 4 ) 是属性集合，子集c 和f 凶) 分别称为条件属性集和结果属性集， k = u k 是属性值的集合，其中n 表示属性r e r z 的属性值范围，即属性r 的值 r 6 r 域；：u x r ，一虬表示一个信息函数。 显然，这种方法得到的每个单一决策表是通过将原来决策表中其余决策( 属 性结果) 所对应的列去掉而得到的新的决策表。通常情况下，这样得到的单一 决策表中会包含条件属性和决策属性权值完全相同的重复记录，还需要将这些 重复记录进一步合并为一个汜录。 方法二如果决策表s = ，r = c u d 是属性集合，子集c 和d 分别称为条件属性集和结果属性集，且d = d ，兄，巩 ，则可以构造一个新的 决策表s = ，u 是论域，r kc u d ) 是属性集合，子集c 和 d ) 分 别称为条件属性集和结果属性集， v 。u 是属性值的集合，其中巧表示属性 ，e 。 ，r ；的属性值范围，即属性，的值域；f ：u x r 一以表示一个信息函数。这里， 结果属性d 的取值要满足如下要求： v x v y ( d ( x ) 2 矾y ) ) ( d l ) 2 d f ( y ) 八函0 ) 2 而c y ) 八八比 ) = 如( y ) ) 可以看出，这种方法是通过综合多决策表中所得结果属性的取值来形成一 个综合决策( 结果属性值) ，从而将多决策问题转化为单一决策问题的。 许多决策问题都可以用决策表来表达，这个工具在决策应用中起着相当重 要的作用。 2 2信息熵 熵( e n t r o p y ) 起初是纯粹的物理概念，最早由德国物理学家r c l a u s i u s 于 1 8 6 5 年在热力学中引入，表示物质热状态的概率，在数学中表示情况或问题的 不确定性，而在信息论中则表示信息系统中描述信息的能力。 2 2 i 信息熵历史与发展 信息熵仍在不断完善之中，它不仅被广泛应用于几乎所有学科，而且提出 了将信息的量与质统一量度的理论，以及将概率熵概念移植到模糊集合上而定 义非概率的模糊熵。 在信息论的带动下，熵概念首先进入了概率论、通信和计算机等领域。2 0 世纪后期，以电子计算机为代表的信息革命方兴未艾，推进了与信息密切相关 的熵概念的史无前例的大发展。纵观熵的1 4 0 年的历史，可以说，熵是对系统“不 确定性”的最佳测度。 2 0 世纪4 0 年代末首次提出的s h a n n o n 熵，就是以对不确定性的数学度量的 身份出现的。它是现代动力系统和遍历理论的重要概念，并在自然科学和社会 科学中应用也日趋广泛【、”1 。以下是关于s h a n n o n 熵的一些定义和性质。 2 2 2 信息论介绍 信息论是c e s h a n n o n 为解决信息传递( 通信) 过程问题建立的系列理论， 也称为通信理论。一个传递信息的系统是由发送端( 信源) 和接受端( 信宿) 以及连 接两者的通道( 信道) 三部分组成。信息论把通信过程看成是随机干扰的环境中传 递信息的过程，在这个通信模型中，信息源和干扰( 噪声) 都被理解为某种随机过 程或随机序列。因此，在进行实际的通信之前，收信者( 信宿) 不可能确切了解信 源究竟会发出什么样的具体信息，不可能判断信源会处于什么样的状态，这种 情形就称为信宿对于信源状态具有不定性，而且这种不定性是存在于通信之前 的，因而又叫做先验不确定性。 在进行了通信之后，信宿收到了信源发出的信息，这种先验不定性才会被 消除或者被减少。如果干扰很小，不会对传递的信息产生任何可察觉的影响， 信源发出的信息能够被信宿全部收到。在这种情况下，信宿的先验不确定性就 会被完全消除。但是，在一般情况下，干扰总会对信源发出的信息造成某种破 坏，使信宿受到的信息不完全。因此，先验不确定性不能全部被消除，只能部 分被消除。换句话说，通信结束之后，信宿还仍然具有一定程度的不确定性， 这就是后验不确定性。显然，后验不确定性总要小于先验不确定性，不可能大 于先验不确定性。如果后验不确定性的大小正好等于先验不确定性的大小，这 就表示信宿根本没有收到。如果后验不确定性的大小等于零，这就表示信宿收 到了全部信息。 c e s h a n n o n 于1 9 4 8 年在通信的数学理论一文中指出，信息是用来消除 ( 随机) 不定性的东西；信息的大小，由所消除的不定性的大小来计量。 2 , 2 3 信息熵的定义和性质 c e s h a n n o n 提出的信息论中有几个比较重要的概念i 1 定义2 s 自信息量：设x 代表一组随机事件x i ，x 2 ，z 。，其中p ( x i ) = p i ( o p i _ 1 ) 分别是它们出现的概率，且 p l + p 2 + ，印n = 1 则定义事件x 。的自信息量为i ( x ) ，i ( 扎) = 一l 0 9 2 p i 。由此可见，小概率事件包 含的自信息量大，大概率事件包含的自信息量小。 自信息量公式i ( x ) 的导出，使信息的度量成为可能。但i ( x i ) 只能表示随机 事件集中与某一特定事件x 。的自信息量，不同的事件有不同的自信息量。因此， 它并不能作为整个事件总体信息的测度，所以需要寻找一个量来度量整个事件 总体信息。 定义2 6 信息熵：设x 代表一组随机事件x i ，x 2 ，x 。，其r 扣p ( x i ) = p i ( 0 o ) ，它对于集合熵值的贡献也就趋进于零了，这体现了熵的 总体平均性。 2 3 本章小结 本章主要介绍粗糙集合有效的知识表达方式信息表。首先对知识利用分 类的概念进行描述，然后对信息表描述的知识表达进行介绍，并加以形式化的 描述，再对决策表这种特殊的信息表进行描述。此外，对信息熵理论的起源和 发展进行了阐述，然后介绍了信息熵函数的基本概念和基本性质。这一章是我 们算法的基础。 第三章数据离散化介绍 数据开采中经常遇到的技术难点有两点：一是数据的不完整性，即数据库 中某些个别记录在某些属性上可能存在空值现象，给发现、评估和解释一些重 要的模式带来了困难：另外一个难点是数据库中的某些属性上的属性值是连续 的，如果不对这些数据进行处理，那么给规则的提取带来了很大的困难，必须 对这些连续的数据进行离散化处理。 3 1 数据离散化 一般来说，数据中的属性可以为两种类型：一种是连续( 定量) 属性，表 示了