（计算机软件与理论专业论文）基于粗糙集合和信息熵的分类模型研究.pdf

摘要 数据库中的知识发现( k d d ) 是当前涉及统计学、人工智能、数据库等学 科的热门研究领域。数据挖掘( d m ) 是从数据中提取人们感兴趣的、潜在的、可 用的知识，并表示成用户可理解的形式。分类是数据挖掘的一个重要分支，分 类能找出描述数据类或概念的模型( 或函数) ，以便能使用模型预测类标记未知 的对象类。 粗糙集合是波兰数学家p a w l a k 提出的一种对不确定性知识的表示方法，粗 糙集合理论凭借其独特的优势而在k d d 领域中具有越来越重要的地位。信息熵 是信息论的一个概念，目前被广泛用于数据分析领域。 本文提出了一种基于粗糙集合和信息熵的r s e 算法模型，该算法模型包括 两个组成部分分类模型和预测模型。分类模型是以经典的粗糙集合理论和信 息熵理论为基础，依据信息熵理论对属性进行筛选，依据不可区分关系确定等 价类，从而提取决策规则。预测模型是以粗糙集合的扩展模型一容差粗糙集合 模型为基础，依据对象与决策规则容差的定义，给出待测对象的预测类别。 此外，我们设计了基于r s e 算法模型和i d 3 算法模型的原型系统一r d m ，该 系统实现了r s e 算法和i d 3 算法的分类模型和预测模型，在此统一的平台上，我 们通过对u c i 提供的多个标准测试数据集进行测试，对r s e 算法和i d 3 算法进行了 分析比较。实验证明，r s e 算法确实优于 d 3 算法。 关键词：数据挖掘，粗糙集合，容差粗糙集合，信息熵，分类，预测 a b s t r a c t 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 ) i saf l o u r i s hr e s e a r c hf i e l dr e l e v a n t t os t a t i s t i c s ，a r t i f i c i a li n t e l l i g e n c ea n dd a t a b a s es y s t e m d a t am i n i n gi st h ep r o c e s s o fm i n i n gt h ei n t e r e s t i n g ，p o t e n t i a l l yu s e f u l ，v a l i da n du n d e r s t a n d a b l ek n o w l e d g ei n d a t a c l a s s i f i c a t i o ni sa ni m p o r t a n ts u b b r a n c ho fd a t am i n i n g ，w h i c hcanf i n do u t am o d e ld e s c r i b i n gap r e d e t e r m i n e ds e to f d a t ac l a s s e so rc o n c e p t sa su s e dt o p r e d i c tt h ec l a s sl a b e lf o ra t e s ts a m p l e r o u g hs e tt h e o r yw a sp r o p o s e db yp o l i s hm a t h e m a t i c i a np a w l a k ，w h i c hu s e d t or e p r e s e n tt h eu n c e r t a i nk n o w l e d g e r o u g hs e tt h e o r yh a sb e c o m eam a i nm e t h o d f o rk d dd u et oi t su n i q u ea d v a n t a g ei nk n o w l e d g ed i s c o v e r y e n t r o p yi sac o n c e p t o fi n f o r m a t i o nt h e o r y ，w h i c hi sa b r o a d l yu s e di nd a t aa n a l y s i sf i e l d i nt h i st h e s i s ，ar s ea l g o r i t h mm o d e lb a s e donr o u g hs e tt h e o r ya n de n t r o p y t h e o r y i sp r e s e n t e d ，w h i c hc o n t a i n st w oc o m p o n e n t s - - c l a s s i f i c a t i o nm o d e la n d p r e d i c t i o nm o d e l c l a s s i f i c a t i o nm o d e li sb a s e do nt y p i c a lr o u g hs e tt h e o r ya n d e n t r o p yt h e o r y ，s e l e c tt h ea t t r i b u t ea c c o r d i n gt oe n t r o p yt h e o r y ，d e t e r m i n et h e e q u i v a l e n c e c l a s s e s a c c o r d i n gt o i n d i s c e r n i b l e r e l a t i o n ，t h e n e x t r a c tt h e c l a s s i f i c a t i o nr u l e s ，p r e d i c t i o nm o d e li sb a s e do nt h ee x t e n d e dr o u g hs e tm o d e l - t o l e r a n c er o u g hs e tt h e o r y ，p r e d i c tt h ec l a s sl a b e lf o rat e s ts a m p l ea c c o r d i n gt ot h e d e f i n i t i o no ft h et o l e r a n c er e l a t i o nb e t w e e nas a m p l ea n dar u l e i na d d i t i o n ，w ed e s i g n e dap r o t o t y p es y s t e mn a m e dr d m ，w h i c hb a s e don r s e a l g o r i t h mm o d e la n di d 3a l g o r i t h mm o d e l ，w h i c hc o m p l e t e dt h ec l a s s i f i c a t i o n a n dp r e d i c t i o nm o d e lo ft h er s ea l g o r i t h ma n di d 3a l g o r i t h m o nt h i su n i f o r m f l a t f o r m ，w ec o m p a r e dt h er s ea l g o r i t h ma n di d 3a l g o r i t h mb yu s i n gt h es t a n d a r d u c id a t as e t s ，f r o mt h ee x p e r i m e n t ，w ecans e et h er s ea l g o r i t h mi ss u p e r i o rt o i d 3a l g o r i t h mi n d e e d k e y w o r d s ：d a t am i n i n g ，r o u g hs e t ，t o l e r a n c er o u g hs e t ，e n t r o p y ， c l a s s i f i c a t i o n ，p r e d i c t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得合肥工业大学 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究 所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者馘矽 签字叫螂年岁f 日 学位论文版权使用授权书 本学位论文作者完全了解佥壁王、业盔堂有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅 和借阅。本人授权金蟹工些厶堂可以将学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名 嘞研 签字日期：几帅t 卢厂月，炉 学位论文作者毕业后去向 工作单位： 通讯地址： 导师签名 z 毫 一| 签字日划：辨年f 月旷日 电话 邮编 致谢 衷心感谢我的导师王浩教授在整个论文阶段给予的悉心指导和帮助。导师 不断从学业上、生活上关心我，为我创造了良好的工作和学习环境，使我在理 论和实践两个方面都得到了良好的锻炼，没有导师付出的辛勤劳动，本论文是 不可能完成的。在三年的研究生活中，王老师f “谨的治学态度和丰富渊博的知 识给我留下了深刻的印象，特别受到王老师那种手不释卷、 _ i = f 口勤勉的工作作 风的熏陶，使我终身受益。 同时，我也深深地感谢计算机学院人工智能与知识挖掘研究室的胡学钢教 授，他也给了我大量的指导、关怀和帮助，他的真知灼见使我受益很多，在我 内心深处，十分感激胡学钢教授。还要感谢方宝富、姚宏亮，姜卯生、于磊、 王骋等，大家一起对知识挖掘课题进行研讨，集思广益，对于构思我的论文有 很大的启发。 7 感谢计算机学院的王新生老师、徐静老师等为我所付出的辛勤工作 f 肥t 业人学倾卜论文 第章绪论 第一章绪论 本章概述了k d d 和r s 的研究和发展概况，指出了本研究工作的目的和意义。 介绍了k d d 的基本概念、k d d 中数据的特点、k d d 的处理过程模型，并且详细阐 述了k d d 的关键步骤一数据挖掘，对数据挖掘的定义、数据挖掘的对象、数据 挖掘发现的模式、数据挖掘的方法、数据挖掘软件的发展、数据挖掘技术的应 用以及数据挖掘面临的挑战进行了介绍。此外还介绍了本文的课题来源和内容 组织。 1 1引言 十八世纪的法国，在启蒙运动精神的鼓舞下，一些人士提出了一项雄心勃 勃、近乎幻想的规划：将全世界所有的知识汇集在一起，做成一本反映人类全 部文明的百科全书。然而两个世纪之后，当i n t e r n e t 看来就要将这个乌托邦式 的梦想付诸实现的时候，人们又发现了一个更加严峻的问题，那就是：我们如 何来使用这个知识宝库昵? 我们如何来翻阅这本厚厚的百科全书呢? 近半个世纪以来，计算机和信息技术的高速发展给人类社会带来了巨大的 变化与影响，数据成为最重要的战略资源。由于技术的进步，人们能以更快速、 更容易、更廉价的方式获取和储存数据，数据库应用的规模、范围和深度不断 扩大，千千万万个数据库被用于商业管理、政府办公、科学研究和工程开发等， 并且这一势头仍将持续发展下去，使得数据及其信息量以指数形式增长。根据 粗略估计，早在2 0 世纪8 0 年代，全球信息量每隔2 0 个月就要增加一倍。而 进入9 0 年代，全世界所拥有的数据库及其所存储的数据规模增长更快。9 0 年 代互联网的发展与普及，以及随之而来的企业内部网、企业外部网以及虚拟私 有网的产生和应用，使整个世界互联形成一个小小的地球村，人们可以跨越时 空在网上交换信息和协作工作。这样展现在人们面前的己不是局限于本部门、 本单位和本行业的庞大数据库，而是浩瀚无垠的信息海洋。从而形成一个新的 挑战：这就是被j o h nn a i s b e r t 称之为“信息丰富而知识贫乏”的窘境，在这些 大量数据的背后隐藏了很多具有决策意义的信息，那么如何及时得到这些有用 的知识呢? 如何才能不被信息的汪洋大海所淹没，提高信息利用率呢? 数据库 知识发现( k n o w l e d g e d i s c o v e r y i n d a t a b a s e s ， k d d ) 技术应运而生，并得以 台肥_ r _ 、世人学坝卜硷文 第一章绪论 蓬勃发展，越来越显示出其强大的生命力。人们把原始数掘看作是形成知识的 源泉，就像从矿石中采矿一样。原始数据可以是结构化的，如关系数据库中的数 据也可以是半结构化的，如文本、图形、图像数据，甚至是分布在网络上的异构 型数据。发现知识的方法可以是数学的，也可以是非数学的；可以是演绎的，也可 以是归纳的。发现了的知识可以被用于信息管理、查询优化、决策支持、过程 控制等，还可以用于数掘自身的维护。因此，k d d 是门很广义的交叉学科，它汇 聚了不同领域的研究者，尤其是数掘库、人工智能、统计学、可视化、等方面的 学者和工程技术人员。一般将k d d 中进行知识发现的阶段称为数据挖掘( d a t a m i n i n g ，d m ) ，数据挖掘是k d d 最关键的步骤，也是技术难点所在。所以某些 应片j 领域对数据挖掘与k d d 不加区分地使用，某种意义上二者可看作同一个概 念。 k d d 一词是在1 9 8 9 年于美国底特律市召开的第l l 届国际人工智能联合会 议上首次提出的，这届学术会议上举行了以k d d 为主题的学术讨论，在1 9 9 1 年、1 9 9 3 年和1 9 9 4 年相继举行了k d d 专题讨论会。随着对k d d 的深入研究 以及k d d 在许多领域的广泛成功的应用，于1 9 9 5 年，在加拿大召开了第一届 知识发现和数据挖掘国际学术会议，此后每年召开一次。第一本关于k d d 的 国际学术杂志d a t am i n i n ga n dk n o w l e d g ed i s c o v e r y ) ) 也于1 9 9 7 年3 月创刊 发行。亚太地区于1 9 9 7 年在新加坡召丌了首次k d d 国际学术研讨会。 目前，在i j c a i 、a a a i 、v l d b 、a c m s i g m o d ，等代表人工智能与数据 库技术研究最高水平的国际学术会议上，对k d d 的研究都占有较大的比例， k d d 已经成为当今计算机科学与技术研究、应用的热点领域之一。在数据挖掘 方丽还有更多的国际会议，如p a k d d 、p k d d 、s i a m d a t a m i n i n g 、f i e e e ) i c d m 、 d a w a k 、s p i e d m 等等。 目前，国外有许多研究机构、公司和院校从事数据挖掘工具的研究与开发。 这些工具主要采用决策树、神经网络、聚类、遗传算法、贝叶斯信任网络、统 计分析等方法。许多数据挖掘系统已经成功应用于零售业、银行业、市场营销、 电信业、保险业、医疗部门等领域。世界上比较有影响的典型数据挖掘系统有： s a s 公司的e n t e r p r i s em i n e r 、i b m 公司的i n t e l l i g e n tm i n e r 、s g i 公司的 s e t m i n e r 、s p s s 公司的c l e m e n t i n e 、s y b a s e 公司的w a r e h o u s es t u d i o 、r u l e o u e s t r e s e a r c h 公司的s e e 5 、还有c o v e r s t o r y 、e x p l o r a 、k n o w l e d g ed i s c o v e r v w o r k b e n c h 、d b m i n e r 、q u e s t 等。 随着k d d 在国际上的兴起，我国也积极地开展了相应的研究和应用。1 9 9 3 年国家自然科学基金首次支持该领域的研究项目，目前国内许多学术会议，如 数据库学术会议、机器学习会议等，也都将k d d 歹o 为重要的研究方向。国内的 许多科研单位和高等院校竞相开展数据挖掘与知识发现的基础理论及其应用研 究。我校是国内较早进行知识发现的研究单位之一，八十年代末期以来相继在 合肥工业大学硕十论文筘一章绪论 国家自然科学基金资助下开展了“从关系数据库中提取领域知识的自动化获取 研究”，在国家教委博士学科点专项科研基金资助下丌展了“从大规模数据库中 自动提取领域知识的算法与实现研究”，以及在国家自然科学基金项目“基于粗 糙集合理论的概念格模型研究”等。本文正是基于上述背景下的开展的研究。 1 2 数据库中知识发现 1 2 1k d d 的定义 众多的学者根据自己的对k d d 的认识和理解，下了很多的定义，而其中 比较公认比较完整、深刻和全面的一个定义是由f a y y a d ，p i a t e t s k y s h a p i r o 和 s 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 ” 即k d d 指大量数据中获取有效的、新颖的、有潜在作用的和最终可理解 的模式的非平儿过程。还有很多和这一术语相近似的术语，如数据挖掘( d m ) 、 数据分析( 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 n s u p p o r t i n g ) 等。 下面对这个定义作详细的解释： 数据：数据是一系列事实的集合，可以是一个或一组数据库、数据仓库、 电子表格或其他类型的信息库，在数据上进行数据清理、集成和规约后的数据。 这是k d d 处理的最常用的数据形式。 模式：模式是指用语言来表示的一个表达式，它可用来描述数据集的特性， 根据某种兴趣度度量，并于数据挖掘模块中进行交互挖掘，以便识别和表示知 识的真正有趣的模式。 过程：过程是在k d d 中包含的步骤，如数据的预处理、模式搜索、知识 表示及知识评估、过程优化等。 非平凡：是指它已经超越了一般封闭形式的数量计算，包括对结构、模式 和参数的搜索。 有效性：通过k d d 从当前数据所发现的模式必须有一定的正确程度，否 则k d d 就毫无作用。 新颖性：经过k d d 提取出的模式必须是新颖的，至少对系统来说应该如 此。模式是否新颖可以通过两个途径来衡量：其一是在所得到的数据方面，通 过对比当前得到的数据和以前的数据或期望得到的数据之间的比较，来判断该 台肥1 二业大学顺，l 论文第一章绪论 模式的新颖程度；其二是在其内部所包含的知识方面，通过对比，发现的模式 与已有的模式的关系来进行判断。 潜在作用：提取出的模式应该是有意义的，有潜在的应用价值。 可理解：k d d 的一个目标就是将数据库中隐含的模式以容易理解的形式表 现出来，从而帮助人们更好地理解数据库中所包含的信息。 1 2 2 k d d 中数据的特点 由于知识发现系统的基本输入是数据库中的原始数据，因此需要特别关注 数据本身固有的一些性质。 1 数据的规模与冗余性 知识发现所面临的数据库一般是非常庞大的且可能包含冗余的信息。数据 的规模包含两方面的含义，其一是数据对象的多少，其二是描述数据对象的属 性的多少。面向属性的归纳与实值离散化技术等是重要的对象约简方法。属性 约简可以根据属性的重要性来应用某种特征选择技术，比如通过基于粗糙集合 的属性约简方法来实现。冗余信息有时会误导知识的发现过程，如此所发现的 知识可能缺乏足够的兴趣度。 2 数据的动态性 大多数数据库的内容将经常变化。在一个在线系统中，必须采用预警机制 柬保证这些变化不导致错误的发现。一般地认为从数据库发现知识是一种动态 过程。 3 噪声数据和稀疏数据 错误的数据对于现实世界数据库是在所难免的，这主要源于数据采集的各 个环节。数据库中的信息在实例空间中可能是稀疏的，这可能会严重影响发现 的效率。另外，有时候异常数据模式不仅不是噪声数据，反而正是知识发现所 关注的目标。 4 不完整性 由于不完整的数据域和数据域上值的缺少所造成的不完整数据，当然会影 响发现的结果。目前数据库并非是面向知识发现进行设计的，而模式的发现、 评价与解释很可能需要数据库中不存在的信息。 5 不确定性 数据的不确定性是指并非全域中的每个概念都可以通过属性值来充分与精 确地表达，知识发现的模式也只可能在一部分数据上有效。模糊集合理论与粗 糙集合理论等使用了不同的方式来解决这一问题。 1 2 3 k d d 的处理过程模型 人们进行的关于k d d 的研究是为了将知识发现的研究成果应用于实际数 4 台肥t 业人学坝i ：论义第一章绪论 据处理中，为科学的决策提供支持。j f 是因为这样，目前所进行的关于k d d 的研究，大多只着眼于对数据挖掘的研究，而忽视了其他方面研究。事实上， k d d 首先是一个处理过程，如果仅仅着重于数据挖掘，l 叮能就看不到在实际工 作中，数据处理过程中的数据提取、组织和显示方式的难度。数据挖掘所完成 的工作对于整个知识发现的过程来说，只是其中较小的一部分，因此对k d d 中其他阶段及处理过程的研究也是非常重要的。 目前人们对熬个处理过程并没有给出非常清楚的划分，而建立合适的处理 过程模型能将各个处理阶段有机地结合在。起，以便于人们开发及使用k d d 应用系统。比较有代表性的模型有三种： 第一种是u s a m a m f a y y a d 等人给出的多处理阶段模型。 第二种是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 处理过程模型为例进行简要地说明，本文后面有关的讨论也是针对这种模 型进行论述的。 臣敷辱库中妇担发现的处理过程横型 如淑 幽1 1k d d 的处理过程模型 图1 1 是u s a m af a y y a d 等人给出的处理模型。该处理模型把k d d 过程分 为九个处理阶段：数据准备、数据选择、数据预处理、数据转换、k d d 目标确 定、挖掘算法确定、数据挖掘、模式解释及知识评价。 1 数据准备：了解k d d 相关领域的有关情况，包括实际应用中的预备知 识和目标，熟悉有关的背景知识，并弄清楚用户的要求。 2 数据选择： 根据用户要求从数据库中提取与k d d 要求相关的数据， k d d 主要从这些数据中进行知识提取。在此过程中，会使用一些数据库操作对 台肥t 业人学硕1 论文第一章绪论 数据进行处理，建立一个目标数据集。 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 数据挖掘 1 3 1 数据挖掘的定义 数据挖掘( d a t em i n i n g ) 是从大型数据库或数据仓库中提取人们感兴趣的 知识，这些知识是隐含的、事先未知的、潜在的、有用的信息，其广泛观点的 定义是从存放在数据库、数据仓库或其他信息库中的大量数据中挖掘有趣的知 识过程。许多人把数据挖掘视为另一个常用的术语数据库中的知识发现或k d d 的同义词。而另一些人只是把数据挖掘视为数据库中的知识发现过程的一个基 本步骤。在这里，我们认为数据挖掘是k d d 的一个阶段。 合肥t 业大学硕i j 论文第章绪论 1 3 2 数据挖掘的对象 根据信息存储格式，用于挖掘的对象有：关系数据库、面向对象数据库、 空间数据库、时序数据库、文本数据源、多媒体数据、异质数据库、遗产数据 库，以及w e b 数据源。 1 3 3 数据挖掘发现的模式 数据挖掘功能用于指定数据挖掘任务重要的模式类型，数据挖掘任务一般 可以分为两类：描述型与预测型。描述型挖掘任务刻画数据库中数据的一般特 性，预测型挖掘任务在当前数据上进行推断，以进行预测。重要的是数据挖掘 系统要能够挖掘出多种的模式，以适应不同用户的需求或不同的应用，此外， 数据挖掘系统应当能够发现各种粒度( 即不同的抽象层) 的模式，同时允许用 户给出提示，指导或聚焦有趣模式的搜索。常用的模式介绍如下： 概念，类描述模式( c o n c e p td e s c r i p t i o n ) ：特征化和区分 概念或类别描述使用汇总的、简洁的、精确的方式描述每个类和概念，可 通过前面的方法得到：1 ) 数掘特征化，是对目标类数据一般特性或特征的汇总； 2 ) 数据区分，将目标类与一个或多个比较类进行比较；3 ) 数据特征化和比较， 两者的结合。数据特征的输出可以用多种形式输出，包括扇形图、条图、曲线、 多维数据立方体和交叉表在内的多维表。结果描述也可以用概括关系 ( g e n e r a l i z e dr e l a t i o n ) 或关联规则形式来表示。 关联规则模式( a s s o c i a t i o nr u l e s ) 关联规则分析就是发现关联规则，这些关联规则反映了在给定的一组数据 中某些属性值高频率同时出现的一种状态。其表现形式是形如x j y ，即规则 a 1 八八a m - - b 1 八八b n ，其中a i ( i l ，m ) ，b i ( j 1 ，n ) 是属性值，关联规 则x j y 解释为“满足条件x 的数据组也可能同时满足条件y ”，但需满足一 定的支持度和可信度。关联规则有单维和多维规则之分，关联规则广泛用于购 物篮或事务的数据分析。 分类模式( c l a s s i f i c a t i o n ) 分类是找出描述并区分数据类或概念的模型( 或函数) ，以便能使用模型预 测类标记未知的对象类，分类可被用于规则描述和预测。与回归方法不同的是， 分类的输出是离散的类别值，而回归的输出则是连续数值。预测是利用历史数据 找出变化规律，建立模型，并由此模型对未来数据的种类及特征进行预测。要 构造分类器，需要有一个训练样本数掘集作为输入，基于对样本数据的训练生成 分类器，然后把该分类器应用于测试集及将来数据。例如，关于疾病的分类规 则可以从已知病例( 训练集) 提取出来，然后结合新病员的症状，可用于对新 病员进行诊断。 台肥t 业人学坝卜论文第一章绪论 聚类模式( c l u s t e r i n g ) 聚类是把数据按照相似性归纳成若干类别，同一类中的数掘彼此相似，不 同类中的数据相异。与分类不同，一般情况下，训练数据中不提供类标记，聚 类可以用于产生这种标记。对象根据最大化的类内相似性、最小化的类别间相 似性的原则进行聚类或分组。即对象的簇( 聚类) 是使得在一个簇中的对象具 有很高的相似性，而与另外簇中的对象很不相似。所形成的每个簇可以看成一 个对象类，由它导出规则。 异常检测模式( o u t l i e r ) 异常检测是用来发现“小的模式”( 相对于聚类) ， 即数掘集中间显著不同于其它数据的对象。数据库中可能包含一些数据对象， 它与数据的一般行为或模型不一致，这些数据对象是异常( o u t l i e r ) ，大部分数据 挖掘方法将异常视为噪音而抛弃，然而在一些应用中( 如欺骗检测) ，罕见的事 件可能比正常出现的事件更有趣。 序列模式( s e q u e n c e l 序列模式是指通过时间序列搜索出的重复发生概率较高的模式。序列模式 与关联模式相仿，差别在于数据间关联性与时间联系起来。即不仅需知道事件 是否发生，而且需确定事件发生的时间。 1 3 4 数据挖掘的方法 数据挖掘的方法通常可以分为两大类，一类是统计型，常用的技术有概率 分析、相关性分析、聚类分析等，另一类是人工智能中的机器学习型，通过训 练和学习大量的样品集得到需要的模式或参数。大致有以下几种，现分别简要 介绍。 一、概念格 概念格是基于二元关系构造的，它描述了对象和特征之间的联系，表明了 概念之间的泛化和例化关系，其相应的哈斯图实现了对数据的可视化，作为知 识的一种表示形式，它有助于挖掘概念问的各种规则。概念是把所感知的事物 的共同本质特点抽象出来，并加以概括。概念都具有内涵和外延，基于概念的 这种理解，r w i l l e 在1 9 8 2 年首先提出根据二元关系来构造相应概念格( 或 g a l o i s 格) 的思想，也称为形式概念分析，就是以概念格中的每个节点表示一 个形式概念，其中概念的外延代表相应的一组对象，内涵则为这组对象所具有 的公共特征( 属性) ；而概念格所相应的哈斯图则形象地揭示了概念间的泛化和 例化关系，反映出一种概念层次结构( c o n c e p t h i e r a r c h y ) ，实现了对数据的可 视化，非常适用于从数据库中进行知谚 挖掘，从丽成为数据分析和规则提取的 一种有效工具。 给定上下文( c o n t e x t ) 为三元组t = ( o ，d ，r ) ，其中0 是对象集合，d 是性质 集合，r 是o 和d 之间的二元关系，则存在唯一的偏序集合与之对应，并且这 台肥工业大学硕d ：论文第一章绪论 个偏序集合产生一种格结构，这种由上下文所诱导出的格称为概念格。x r x 表 示0 中的一个元素x 与d 中一个元素x 之间有关系r 。格中每个结点是一个序 偶( 即概念) ，记为( a ，b ) ，其中a p ( o ) ，b p ( d ) ，p ( o ) 是o 的幂集，p ( d ) 是d 的幂集，称a 为概念的外延( e x t e n s i o n ) ，称b 为概念的内涵( i n t e n s i o n ) 。概念格 是一种完备的概念层次结构，在信息检索、数字图书馆、软件工程、知识分类、 类的设计、网络管理和k d d 等领域，概念格已经显示出一定的应用价值。 二、粗糙集理论 粗糙集合理论( r o u g hs e t ，也称为r s 理论) 由波兰数学家p a w l a k z 于1 9 8 2 年首先提出。八十年代，许多波兰学者对粗糙集合理论及其应用进行了坚持不 懈的研究，其中主要对粗糙集合理论的数学性质及逻辑系统进行了广泛的分析， 同时，他们也开发出一些应用系统。但由于最初的研究成果大多是以波兰文字 发表在“b u l l e t i no f t h ep o l i s ha c a d e m yo f s c i e n c e s ：m a t h e m a t i c s ”或“b u l l e t i no f t h ep o l i s ha c a d e m yo f s c i e n c e s ：t e c h n i c a ls c i e n c e s ”上，该项研究局限于东欧各 国，当时并未引起国际计算机学界的重视。直到八十年代末粗糙集合理论才逐 渐引起了世界各国学者的注意。1 9 9 1 年p a w l a k 发表了专著，奠定了粗糙集合 的理论基础。同时随着1 9 9 2 年s l o w i n s k ir 主编的关于粗糙集合应用及其与相 关方法比较研究的论文集的出版，推动了国际上对粗糙集合理论与应用的深入 研究，掀起了粗糙集合的研究高潮。近几年来，粗糙集合理论已广泛地应用于 机器学习、数据库知识发现、决策支持与分析、专家系统、智能控制、模式识 别等等领域。关于粗糙集合方面的会议有r s f d g r c 、c r s s c 等。 粗糙集理论是一种研究不精确、不确定性知识的数学工具，这一方法在数 据挖掘中具有重要的作用，通常处理含糊性和不确定的问题，发现不准确数据 或噪音数据内在的结构关系，可用于特征的约简和相关分析中。知识工程研究 中，一直存在着信息的含糊性( v a g u e n e s s ) 等问题。含糊性有三种：1 ) 术语 的模糊性，如高矮；2 ) 数据的不确定性，如噪音引起的：3 ) 知识自身的不确 定性，如规则的前题、结果之间的依赖关系并不是完全可靠的。 人工智能的基础理论之一经典逻辑不足以解决这些不确定性问题。为 此，人们提出了一些解决方法，包括统计方法、模糊集理论以及d e m p s t e r s h a f f e r 证据理论，但这些方法都有一些内在缺陷或限定范围。例如，基于统计的方法 在理论上还难以令人信服；而模糊集方法则存在一个本质问题即如何确定成员 隶属度，相比之下，粗糙集方法则有几个优点：不需要预先知道的额外信息， 如统计中要求的先验概率和模糊集中要求的隶属度，算法简单，易于操作。 粗糙集对不精确概念的描述是通过上近似( u p p e ra p p r o x i m a t i o n ) 和下近似 ( 1 0 w e ra p p r o x i m m i o n ) 这两个精确概念来实现的。一个概念( 或集合) 的下近 似是指其中的元组肯定属于该概念：一个概念( 或集合) 的上近似是指其中的 元组可能属于该概念。 含肥1 ：业大学硕l 。论文第一章绪论 三、决策树 决策树方法的起源是概念学习系统c l s ，然后发展到i d 3 方法，最后演化 为能处理连续属性的c 4 5 ，主要是基于数据的属性值进行归纳分类，常用基于 层次方法有“i f t h e n ”规则。决策树方法的最大优点是可理解性，比较直观。 它与神经网络的最大区别是：决策树可以解释如何得出结果的决策过程，其缺 点是处理复杂的数据时，分支数非常的多，管理起来难度非常大。同时，还存 在数据的空缺值处理问题，其算法有i d 3 、c 4 5 、c 5 0 等。目前出现的两种新 算法s l i q 和s p r i n t ，可在非常大的训练集中进行决策树归纳，可以处理分类 属性和连续性属性。 i d 3 决策树构造的输入是一组带有类别标记的例子，构造的结果是一棵树， 树的内部节点一般表示为一个逻辑判断，如形式为( a i = v i ) 的逻辑判断，其中 a ，是属性，v i 是该属性的某个属性值：树的边是逻辑判断的分支结果。树( i d 3 ) 的内部节点是属性，边是该属性的所有取值，有几个属性值，就有几条边。树 的叶子节点都是类别标记。构造决策树的方法是采用自上而下的递归构造。 以多叉树为例，其的构造思路是，如果训练例子集合中的所有例子是同类 的，则将之作为叶子节点，节点内容是该类别标记。否则，根据某种策略选择 一个属性，按照属性的各个取值，把例子集合划分为若干子集合，使得每个子 集上的所有例子在该属性上具有同样的属性值。然后再依次递归处理各个子集。 这种思路实际上就是“分而治之”( d i v i d ea n dc o n q u e r ) 的道理。 四、遗传算法 遗传算法是一种基于生物进化过程的组合优化方法，它是生物学和计算机 相结合的产物，由美国密西根大学的d jh o l l a n d 教授和他的同事们在1 9 7 5 年 首次提出的。根据适者生存的原则模拟自然界的生命迸化机制，从当前群体中 用概率方法选取适应度最高的个体产生新一代群体，在这些选取的个体中，一 部分保持原样进入下一代群体，其他通过交叉和变异等遗传的方法产生新的个 体作为下一代群体的一部分。基于这些思想，根据遗传算法的最合适的模型， 并进一步对数据模型进行优化。由于遗传算法是一种弱方法，具有高效性和灵 活性的特点，在数据挖掘中也用于评估其他算法的适应度。 该算法擅长于数据聚类，通过事件上的类比和空间上的类比，可以把大量 繁杂的信息数据进行系统化、条理化，从而找出数据之间的内在关系，得出有 用的概念和模式，在建立数据模式时，将遗传算法与神经网络相结合，可以更 好地提高模型的适应性，因此遗传算法广泛应用于自动控制、机器学、模式识 别和组合优化等领域。 五、神经网络 神经网络是最常用的数据挖掘技术之一，最早由心理学家和神经生物学家 共同提出的，旨在寻求开发和测试神经的计算模拟，它类似于人类大脑重复学 合肥工业大学颂士论文 第一章绪论 习的方法，先给出一系列的样本，进行学习和训练，从而产生区别各种样品之 间的不同特征和模式。样本集应该尽量体现代表性，为了精确的拟合各种样本 数据，通过上百次、甚至上千次的训练和学习，系统最后得出潜在的模式。当 它遇到新的样品数据时，系统就会根据训练结果自动进行预测和分类。其最大 的特点是难于理解，即无法解释如何得出结果和使用了什么规则，它需要很长 的训练时间，需要的大量的参数，而且解释性较差。该算法的优点是对复杂问 题能进行很好的预测，对噪音数据的承受力较高。 神经网络可细分为前馈式、反馈式和自组织神经网络，具有优化计算、聚 类和预测等功能，在商业界得到广泛的应用。在金融领域，采用神经网络建立 信用卡和货币交易模型，用于识别信贷客户、股票预测和证券市场等。 六、贝叶斯网络 贝叶斯网络基于后验概念的贝叶斯定理，是建立在数据进行统计处理基础 上的方法，将不确定事件通过网络连接起来，可以对其他相关事件的结果进行 预测，其网络变量可以是可见的，也可隐藏在i ) i i 练样本中。贝叶斯网络具有分 类、聚类、预测和因果关系分析的功能。其优点是易于理解，预测效果较好， 缺点是对发生频率很低的事件预；贝i l 效果不好。贝叶斯网络在医学和制造业等领 域的应用具有较好的效果。 七、统计分析 统计分析的理论基础主要是统计学和概率论的原理，是一种较为精确的数 据挖掘技术，它是一种基于模型的方法，包括回归分析、因子分析和判别分析 等，该方法比较容易理解，对结果描述精确。但是当利用大规模数据集来学习 时，统计分析的评估代价变得很敏感。需要收集关于数据的各种统计量，随着 实例数目的增长这将使得代价变得更大。尽管最近的收集技术可能减少这个收 集活动的代价，但对每个新的我们所要的统计量集合仍然要花费大量的时间， 统计分析在实际应用中较为广泛。 1 3 5 数据挖掘软件的发展 在信息化技术迅猛发展的同时，数据挖掘也主要通过软件来实现。截至目 前，数据挖掘技术经过了四个阶段的发展。第一代数据挖掘软件的特点是支持 一个或少数几个数据挖掘算法，挖掘向量数据，数据一般一次性调迸内存进行 处理，典型的系统如s a l f o r ds y s t e m s 公司早期的c a r t 系统。但是，如果数据 足够大，并且频繁的变化，这就需要利用数据库或者数据仓库技术进行管理， 第一代系统显然不能满足需求。在第一代数据挖掘软件的基础上，经过增加一 定的算法，人们推出了第二代数据挖掘软件。其具有的特点是与数据库管理系 统( d b m s ) 集成，支持数据库和数据仓库，与它们具有高性能的接口，具有 高的可扩展性，能够挖掘大数据集、以及更复杂的数据集，通过支持数据挖 台肥t 业大学l ! l 论文 第一章绪论 掘模式和数据挖掘查询语言增加系统的灵活性，典型的系统如d b m i n e r ，能通 过d m q l 挖掘语言进行挖掘操作。同样，第二代数据挖掘软件仍然有不足之处， 如只注重模型的生成，但正因为研究如何与预言模型系统集成导致了第三代数 据挖掘系统的开发，其具有的特点是与预言模型系统之间能够无缝的集成，使 得由数据挖掘软件产生的模型的变化能够及时反映到预言模型系统中，由数据 挖掘软件产生的预言模型能够自动地被操作型系统吸收，从而提供决策支持的 功能，能够挖掘网络环境下的分布式和高度异质的数据，并且能够有效地和 操作型系统集成，典型的系统如s p s s 的c l e m e n t i n e ，缺陷是不能支持移动环 境。目前移动计算越发显得重要，将数据挖掘和移动计算相结合是当前的一个 研究领域，第四代软件能够挖掘嵌入式系统、移动系统、以及普遍存在的计算 设备产生的各种类型的数据。第四代数据挖掘原型或商业系统尚未见报导， p k d d 2 0 0 1 上k a r g u p t a 发表了一篇在移动环境下挖掘决策树的论文，k a r g u p t a 是马里兰巴尔的摩州立大学( u n i v e r s i