（计算机软件与理论专业论文）基于粗糙集理论的数据挖掘方法的研究.pdf

山东师范大学硕士学位论文 基于粗糙集理论的数据挖掘方法的研究 摘要 随着计算机技术的不断发展，人们在信息时代面临着越来越多的数据，如何 发现隐藏在众多数据中的内部信息成为人们研究的热点问题。传统的数据库管理 系统已经不能满足人们从数据库中抽取隐藏信息的需要，因此提出了知识发现和 数据挖掘的概念。知识发现是从数据集中识别出有效的、新颖的、潜在有用的， 以及最终可理解的模式的非平凡过程。数据挖掘是从数据库的大量数据中提取隐 含的、未知的并有潜在价值的信息和知识的过程。数据挖掘是知识发现中最关键 的步骤，也是知识发现技术难点，是目前相当活跃的研究领域。 粗糙集理论是波兰数学家p a w l a kz 于1 9 8 2 年提出的一种分析模糊和不确定 知识的强有力的数学工具。粗糙集理论作为人工智能领域的一个新的研究热点， 能有效地分析和处理不精确、不一致、不完整等各种不完备信息，并从中绂现隐 含的知识，揭示潜在的规律。这个特点使得粗糙集理论非常适合应用于数据挖掘。 研究基于粗糙集理论的数据挖掘方法具有极大的理论价值和现实意义。 。 本课题对基于粗糙集理论的数据挖掘方法进行了系统的研究，主要包括以下 内容： l 、介绍了数据挖掘和粗糙集的相关理论。分析了数据挖掘和粗糙集的研究 现状，对其技术的热点、研究领域以及未来发展趋势进行了探讨，为本课题的全 面开展奠定了基础。 2 、对粗糙集理论的约简算法进行了比较深入的研究。约简算法包括属性约 简和属性值约简，其中属性约简是基于粗糙集理论的数据挖掘模型中的关键步 骤，求取高效、快捷的属性约简算法是该理论研究的主要课题之_ 。论文介绍了 基本的属性约简和属性值约简算法，并归纳总结了启发式属性约简算法。 3 、在目前属性约简算法的基础上提出了一种基于属性频率的改进的属性约 简算法。该算法基于h o r a f a 算法，是一种启发式算法，在计算区分矩阵的基 础上，最终能够找到决策信息系统的一个较优约简。 4 、针对传统的基于粗糙集理论的数据挖掘模型存在着不实用的特点，在其 山东师范大学硕士学位论文 基础上提出了一种改进的模型。该模型包括数据预处理、属性约简和规则生成三 个模块，最后利用算例验证该模型的可行性。 论文的不足在于构造数据挖掘模型时只是利用了经典的粗糙理论模型， 并没有考虑粗糙集的扩展模型，如变精度粗糙集模型或加权粗糙集模型，使得最 终模型的应用范围不够广泛。基于粗糙集理论的数据挖掘方法研究正处于起步阶 段，数据挖掘本身及粗糙集理论研究还有许多问题值得讨论，论文将二者结合起 来研究肯定还有许多不完善的地方，相关工作还有待进一步研究。 关键词：知识发现：数据挖掘；粗糙集：约简 分类号：t p 3 1 1 山东师范大学硕士学位论文 t h er e s e a r c ho fd a t am i n i n gm e t h o db a s e do nr o u g hs e tt h e o r y a b s t r a c t w i t ht h ed e v e l o p m e n to fc o m p u t e rt e c h n o l o g y , p e o p l ea r ec o n f r o n t e dw i t hm o r e a n dm o r ed a t ai ni n f o r m a t i o na g e h o wt of i n dt h ei n t e r n a li n f o r m a t i o ni nd a t ai sa h o tp o i n tw i t hw h i c hp e o p l ea r ec o n c e r n e d a st r a d i t i o n a ld b m sc a l l ta f f o r dt h e r e q u i r e m e n tw h i c hp e o p l ew a n tt oe x t r a c th i d d e ni n f o r m a t i o n ，t h ec o n c e p t i o n so f k d da n dd a t am i n ga r ee x p o u n d e d k n o w l e d g ed i s c o v e yi nd a t a b a s e si st h e n 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 la n d u l t i m a t e l y u n d e r s t a n d a b l ep a t t e r n si nd a t a b a s e s d a t am i n i n gi st h ec o r es t e pd u r i n gt h ec o u r s e o f 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 a tp r e s e n t ，i ti saq u i t ea c t i v er e s e a r c hf i e l d ， t h et h e o r yo fr o u g hs e t s ，p r e s e n t e di n1 9 8 2b yp o l i s hm a t h e m a t i c i a np a w l a kz ， i sap o w e r f u lm a t h e m a t i c a lt o o lf o ra n a l y z i n gu n c e r t a i n ，f u z z yk n o w l e d g e r o u g h s e t s ， a san e wh o t s p o ti nt h ef i e l do fa r t i f i c a li n t e l l i g e n c e ，c a r le f f e c t i v e l yd e a lw i t ht h e e x p r e s s i o na n dd e d u c t i o no fi n c o m p l e t e ，u n c e r t a i nk n o w l e d g e t h et h e o r yo fr o u g h s e t si ss p e c i a l l yf i tf o rt h ea p p l i c a t i o nt od a t a - m i n i n gb e c a u s eo fi tf e a t u r e s n o wt h e m e t h o do fd a t am i n i n gb a s e do nr o u g hs e t sh a sb e c o m eo n eo ft h em a i nm e t h o d so f d a t am i n i n g t h es t u d y0 1 1d a t am i n i n gb a s e dr o u g hs e t sh a sg r e a t l yt h e o r e t i c a la n d r e n i s t i cm e a n i n g t h i st h e s i sr e s e a r c h e st h em e t h o do fd a t am i n i n gb a s e do i l r o u g hs e t s s y s t e m a t i c a l l ya n dd e e p l y t h em a i nc o n t e n t sa r el i s t e da sf o l l o w s ： 1 t h ec o r r e c l a t i v et h e o r yo fr o u g hs e t sa n dd a t am i n i n gw a sd e l i v e r e di nt h i s d i s s e r t a t i o n t h et h e s i ss u m m a r i z e sa n dd i s c u s s e st h e i rd e v e l o p m e n t a lt r e n d sa n dh o t r e s e a r c hf i e l d s a l lo f t h ea b o v eb e c o m et h eb a s i sf o rt h i st h e s i s 2 t h e p a p e rr e s e a r c h e st h e r e d u c t i o na l g o r i t h md e e p l y ，w h i c hc o n s i s t so f a t t r i b u t er e d u c t i o na n da t t r i b u t ev a l u er e d u c t i o n a t t r i b u t er e d u c t i o na l g o r i t h mi st h e k e yf o rt h em o d e lo fd a t am i n i n gb a s e do nt h er o u g h s e t s 3 o nt h eb a s i so fk n o w nr e d u c t i o na l g o r i t h m s ，a ni m p r o v e da t t r i b u t er e d u c t i o n 3 山东师范大学硕士学位论文 a l g o r i t h mi sp r e s e n t e di nt h i sp a p e r t h i sh e u r i s t i c ，i m p r o v e da t t r i b u t er e d u c t i o n a l g o r i t h m ，b a s e d o nt h eh o r a f aa l g o r i t h m ，c a ng u a r a n t e ear e d u c t i o no ft h e i n f o r m a t i o ns y s t e m 4 a ni m p r o v e dm o d e lo fd a t am i n i n gb a s e do i lt h er o u g hs e t si sp r e s e n t e da f t e r l u c u b r m i n gt h ed e f i c i e n c i e s o ft h et h e o r yo ft r a d i t i o n a lr o u g hs e t s t h em o d e l c o n s i s t so fp r e v i o u sm a n a g e m e n tm o d u l e ，a t t r i b u t er e d u c t i o nm o d u l ea n dr u l e s g e n e r a t i o nm o d u l e a ni n s t a n c ei sg i v e nt op r o v et h ef e a s i b i l i t yo ft h em o d e l t h ed r a w b a c ko ft h i sp a p e ri st h a ti to n l yu s e sc l a s s i c a lr o u g hs e tc o n c e p t i o ni n m a k i n gt h ed a t am i n i n gm o d e l t h ea p p l i c a t i o nr a n g ei sn o tw i d ew i t h o u tu s i n go t h e r e x t e n d e dm o d e l d a t am i n i n gi si nab o o m i n gs t a g ea n dt h e r ea r em a n yp r o b l e m s w o r t hs t u d y i n go nt h ea p p l i c a t i o no f r o u g hs e tt h e o r yi nt h i sf i e l d o u rw o r ki s j u s ta b e g i n n i n g ，a n dr e l a t e dw o r kn e e dt ob ef u r t h e rd e v e l o p e d k e y w o r d s ：k n o w l e d g ed i s c o v e r y i nd a t a b a s e ；d a t am i n i n g ；r o u g hs e t s ；r e d u c t i o n c l a s s i f i c a t i o n ：t p3 】 4 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得( 注：如 没有其他需要特别声明的，本栏可空) 或其他教育机构的学位或证书使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示谢意。 学位论文作者签名：茹叉5 - - 导师签字 学位论文版权使用授权书 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。 本人授权堂撞可以将学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在 解密后适用本授权书) 学位论文作者签名：威二， 导师签字 签字r 期：2 0 0 年r 月f 7 同 签字r 期：2 0 06 年期7 r 山东师范大学硕士学位论文 1 1 引言 第一章绪论 随着人类社会的不断发展与进步，在后工业时代向信息时代过渡的过程中， 人类面临着越来越多的数据。在数据与日俱增、信息瞬息万变的现实中及时做出 正确有效的决策来指导生产生活，就显得日益重要。要做到这一点，人们就必须 洞察深藏于庞大数据中的有益知识。所以知识发现( k n o w l e d g ed i s c o v e r yi n d a t a b a s e ，k d d ) 或数据挖掘( d a t am i n i n g ，d m ) 得到了广泛重视和迅猛发展【1 】【2 】【3 】。 数据挖掘技术从一开始就是面向应用的，它要对数据进行微观、中观乃至宏 观的统计、分析、综合和推理，以指导实际问题的求解，发现事件间的相互关联， 甚至利用已有的数据对未来的活动进行预测。如数据挖掘在零售业中的应用，能 够识别顾客的购买行为，发现顾客的购买模式和趋势，改进服务质量，取得更好 的顾客保持力和满意程度，提高货品销量，减少商业成本。数据挖掘在电信业中 的应用有助于理解商业行为，确定电信模式，捕捉盗用行为，更好地利用资源和 提高服务质量。此外，数据挖掘在金融系统和生物医学等方面的研究与应用也获 得了大成功，并促进了这些行业的发展。 进行数据挖掘的方法有很多，粗糙集方法是主要方法之一。粗糙集理论是上 世纪8 0 年代初由波兰数学家z p a w l a k 教授提出的，用于研究不完整数据和不精 确知识的表达、学习、归纳的数学分析理论【”。其特点是算法简单，无需提供数 据之外的任何先验信息，可直接从给定问题的描述集合出发，通过不可分辨关系 和等价类确定给定问题的近似域，从而找出该问题的规律。随着数据挖掘的兴起， 粗糙集理论受到越来越多研究人员的重视，因为它具有以下几个特点： 1 ) 粗糙集是一个强大的数据分析工具。它能表达和处理不完备信息；能在 保留关键信息的前提下对数据进行化简并求得知识的最小表达式；能识别并评估 数据之闯的依赖关系，揭示出概念简单的模式；能从经验数据中获取易于证实的 规则知识，适用于智能控制。 2 ) 粗糙集方法不需要先验知识。模糊集和概率统计方法是处理不确定信息 的常用方法，但是这些方法需要些数据的附加信息或先验信息，如模糊隶属函 山东师范大学硕士学位论文 数和概率分布等，这些信息有时并不容易得到。粗糙集方法仅利用数据本身所提 供的信息，无须任何先验知识。 3 ) 粗糙集与模糊集分别刻画了不完备信息的两个方面【5 】：粗糙集以不可分 辨关系为基础，侧重分类，模糊集基于元素对集合隶属程度的不同，强调集合本 身的含混性。虽然粗糙集和模糊集特点不同，但它们之间有着密切的关系，有很 强的互补性【6 j 。 1 2 国内外研究现状 数据库中的知识发现技术( k d d ) 是随着数据库和人工智能技术的发展而产 生的。它首次出现于1 9 8 9 年在美国举行的第十一届国际人工智能联合学术会议 上，随后k d d 及其核心技术数据挖掘得到了广泛的发展。1 9 9 5 年，数据挖掘 界召开了第一届知识发现与数据挖掘国际学术会议。随着参与人员的不断增多， k d d 国际会议发展成为年会。1 9 9 8 年，在美国纽约举行的第四届知识发现与数 据挖掘国际学术会议上不仅进行了学术讨论，而且有3 0 多家软件公司展示了他 们的数据挖掘软件产品，其中的一些软件产品己在北美、欧洲等国得到应用。其 它内容的专题会议也把数据挖掘和知识发现列为重要议题之一，数据挖掘和知识 发现己成为当前计算机科学界的一大研究热点。 八十年代初，z p a w l a k 教授提出了用粗糙集理论来研究不完整数据、不精确 知识的表达、学习、归纳等方法! 把那些无法确认的个体都归于边界线区域，这 个区域被定义为上近似集和下近似集之差集，由于上近似集和下近似集都可以通 过等价关系给出确定的数学描述，所以含糊元素数目可以被计算出来，从而真假 二值之间的含糊程度可以计算。这套方法与统计方法处理不确定问题不同，它不 是采用概率方法描述数据的不确定性；与这一领域传统的模糊集合论处理不精确 数据的方法也不相同。最初关于粗糙集理论的研究主要集中在波兰，当时并没有 引起国际计算机界和数学界的重视。直到1 9 9 0 年前后，由于该理论在数据的决 策与分析、模式识别、机器学习与知识发现等方面的成功应用，才逐渐引起了世 界各国学者的广泛关注。1 9 9 1 年，z p a w l a k 的专著粗糙集关于数据推理 的理论【4 】问世标志着粗糙集理论及其应用的研究进入了活跃时期。1 9 9 2 年，在 波兰召开了关于粗糙集理论的第一届国际学术会议。1 9 9 5 年，a c m 山东师范大学硕士学位论文 c o m m u n i c a t i o n 将粗糙集列为新浮现的计算机科学研究课题。1 9 9 8 ，2 0 0 0 和 2 0 0 2 年，分别召开了三届r s c t c ( r o u g hs e t sa n d c u r r e n tt r e n d si nc o m p u t i n g ) 国际会议，表明粗糙集的研究已步入发展期。目前粗糙集理论已成为计算机科学 最为活跃的研究领域之一，在许多应用领域已得到发展，如医疗数据分析、水泥 窑生产控制算法、地理学、振动分析、飞行员技能评定、开关电路综合、语言识 别、近似分类、故障诊断、成本预测等【7 1 。 国内对粗糙集理论的研究始于9 0 年代中期，许多科研单位和高等院校竞相 开展相关领域的基础理论及应用研究，取得了令人鼓舞的成果。2 0 0 1 年5 月， 在重庆邮电学院举办了首届中国粗糙集和软计算学术研讨会( c r s s c 2 0 0 1 ) ， 2 0 0 2 年1 0 月在苏州大学举办了第二届中国粗糙集和软计算学术研讨会，2 0 0 3 年 5 月，在重庆邮电学院同时举办第三届中国粗糙集和软计算学术研讨会和第九届 粗糙集、模糊集、数据挖掘与粒度计算国际学术会议( r s f d g r c 2 0 0 3 ) ，这些会 议的举办表明我国粗糙集理论和数据挖掘研究的队伍正在不断壮大，已经得到国 际同行的重视和认可。粗糙集理论逐渐应用于数据挖掘领域中，并在对大型数据 主 库中不完整数据进行分析和学习方面取得了显著的成果，使得粗糙集理论及数据 挖掘的研究成为热点领域。 1 3 本文的研究内容 本文主要围绕着数据挖掘和粗糙集理论进行了以下几方面的工作： 1 、介绍了数据挖掘和粗糙集理论的基本概念，深入研究了传统的属性约简 算法。 2 、针对现有的属性约简算法的缺点，在h o r a f a 算法的基础上给出了一种 改进算法叫3 h o r a f a 算法，能够得到较优的约简。 3 、一提出了一种新的基于粗糙集理论的数据挖掘模型，在模型的约简模块应 用上面提出的g h o r a f a 算法。 1 4 本文的组织结构 本文的组织如下： 第一章为引言部分，对选题意义、研究目标以及国内外研究动态进行了综合 山东师范大学硕士学位论文 论述。 第二章归纳了数据挖掘技术的总体研究情况，包括数据挖掘的定义、挖掘的 主要过程、分类和主要技术手段。 第三章介绍了粗糙集的基本概念和理论，分析了粗糙集理论的几个扩展模 型，并简要介绍了基于粗糙集理论的数据挖掘方法。 第四章详细介绍了粗糙集理论的约简算法，包括属性约简和属性值约简。针 对传统属性约简算法的缺点，提出了一种改进的属性约简算法g h o r a f a 。 第五章提出了一种新的基于粗糙集理论的数据挖掘模型框架，利用该模型对 已有的信息系统进行规则提取，取得了较好的结果。 山东师范大学硕士学位论文 第二章数据挖掘概述 数据挖掘是2 0 世纪9 0 年代兴起的一项新技术，国内外学术界和企业晃都非 常重视对数据挖掘技术和软件的研究和开发。数据挖掘是多门学科和多门技术相 结合的产物，也是一个非常年轻而又活跃的研究领域。本章概要介绍数据挖掘的 定义、挖掘过程以及分类等。 2 1 数据挖掘与知识发现的概述 随着计算机、网络和通讯等信息技术的高速发展，信息处理在整个社会规模 上迅速产业化，而这种产业化在技术上就表现为大规模数据操作的产业化。近些 年来，商务贸易电子化、企业和政府事务电子化的迅速普及都产生了大规模的数 据，目益增长的科学计算和大规模的工业生产过程也提供了海量数据，而日益成 熟的数据库系统和数据管理系统都为这些海量数据的存储和管理提供了技术上 的保证。另一方面，计算机网络技术的长足进步和规模的爆炸性增长，则为数据 的传输和远程交互提供了技术手段，国际互联网更是将全球的信息源纳入了一个 共同的数据库系统中。 毫无疑问，这些庞大的数据库及其中的海量数据是极其丰富的信息源，但是 仅依靠传统的数据检索机制和统计分析方法已远远不能满足需要。随着数据库技 术的迅速发展和数据库管理系统的广泛应用，人们积累的数据越来越多。激增的 数据背后隐藏着许多重要的信息，人们希望能够对其进行更高层次的分析，以便 更好的利用这些数据。目前的数据库系统可以高效地实现数据的查询、统计等功 能，但无法发现数据中存在的关系和规则，无法根据现有的数据预测未来的发展 趋势，缺乏挖掘数据背后隐藏的知识的手段，因此就出现了“数据爆炸但知识贫 乏”的现象。 传统的数据库管理系统已不能满足人们对大量数据进行知识抽取、发现数据 间隐藏的依赖关系，从而为决策提供科学支持的需要。在这种状况下，用数据库 管理系统来存储数据，用机器学习的方法来分析数据，挖掘大量数据背后的知识， 这两者的结合促成了数据库中的知识发现的产生。因此，- - 1 7 新兴的自动信息提 山东师范大学硕士学位论文 取技术：知识发现和数据挖掘，应运而生并得到迅速发展。它的出现为自动和智 能地把海量的数据转化成有用的信息和知识提供了有效的手段。 “知识发现”( 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 ，k d d ) 于1 9 9 5 年在加拿大 召开的第一届知识发现和数据挖掘国际学术会议上被赋予了确切的定义。f a y y a 定义k d d i 列为“k n o w l e 电ed i s c o v e r yi nd a t a b a s e si s t h en o n t r i v i a lp r o c e s so f i 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 柚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 【e m si n d a t a ”即“k d d 是从数据集中识别出有效的、新颖的、潜在有用的以及最终可 理解的模式的非平凡过程”。 数据挖掘( d a mm i n i n g ，d m ) 有多种术语【8 ，如“知识抽取”( i n f o r m m i o n e x t r a c t i o n ) ，“信息发现”( i n f o r m a t i o nd i s c o v e r y ) 等，是指从数据库的大量数据 中提取隐含的、先前的、未知的并有潜在价值的信息和知识的过程。在这个定义 中，要求数据源应该是大量的、真实的、含有噪声的；所发现的信息和知识是潜 在的并隐藏在大量数据背后的，是用户感兴趣的、可理解的、可运用的知识。 可见这两个术语的内涵大致相同，但知识发现是从数据库中发现知识的全部 过程，而数据挖掘是此过程中的一个特定的、关键的步骤。数据挖掘是知识发现 最关键的步骤，也是知识发现技术难点，所以在通常情况下可以不加区分的使用 二者 1 i ，12 1 。 2 2 数据挖掘的定义 数据挖掘的定义有很多，表达方式虽然不同，但本质都是一样的。这里主要 从技术角度和商业角度给数据挖掘的定义。 从技术角度看“，数据挖掘是从大量的、不完全的、有噪声的、模糊的、随 机的实际数据中，提取隐含在其中的、人们不知道的、但又是潜在有用的信息和 知识的过程。 原始数据可以是结构化的，如关系数据库中的数据：也可以是半结构化的， 如文本、图形和图像数据；甚至是分布在网络上的异构数据。发现知识的方法可 以是数学的，也可以是非数学的；可以是演绎的，也可以是归纳的。发现的知识 可以用于信息管理，查询优化，决策支持和过程控制等。因此，数据挖掘是- f 3 交叉学科，它把人们对数据的应用从低层次的简单查询提升到从数据库中挖掘知 6 山东师范大学硕士学位论文 识，提供决策支持。在这种需求的推动下不同领域的研究者，尤其是数据库技术、 人工智能技术、数理统计、可视化技术、并行计算等方面的学者和工程技术人员， 投身到数据挖掘这一新兴的研究领域，形成新的技术研究和开发热点。 从商业应用角度看j ，数据挖掘是一种崭新的商业信息处理技术。其主要特 点是对商业数据库中大量业务数据进行抽取、转化、分析和模式化处理，从中提 取辅助商业决策的关键知识，即从一个数据库中自动发现相关商业模式。 在这种定义下，数据挖掘利用统计学和机器学习的技术，探求那些符合市场、 客户行为的模式。目前，数据挖掘已经可使挖掘技术自动化，将数据挖掘和商业 数据仓库 5 7 1 5 8 】相结合，以适当的形式将挖掘结果展示给企业经营管理人员。数 据挖掘的应用不仅要依靠良好的算法建立模型，更重要的是如何将数据挖掘技术 集成到当今复杂的信息技术应用环境中。因为数据挖掘技术不具备人所特有的经 验和直觉，不能区分哪些挖掘出的模式在现实中有意义的，哪些没有意义，因此 数据挖掘分析人员的参与是必不可少的。 2 3 数据挖掘的过程 数据挖掘的过程一般可以分为三个步骤：数据准备、挖掘、表述和评价。 ( 1 ) 数据准备：该阶段可以进一步划分成数据集成、数据选择和预分析两步。 其中数据集成的目的和使用的技术与建立数据仓库是相同的，虽然数据挖掘不一 定建立在数据仓库的基础上，但是与之协同工作必将大大提高数据挖掘的效率。 数据选择和预分析可以缩小数据范围，提高数据挖掘的质量。 ( 2 ) 挖掘：在该阶段使用数据挖掘技术对数据库中的数据进行分析。 ( 3 ) 表述和评价：可以利用可视化工具将获取的信息以用户可以理解和观察 的方式反映给用户，也可以将分析结果存储在知识库中，供日后进步分析和比 较。如果分析人员对结果不满意，可重复以上三个过程，直到满意为止。 2 4 数据挖掘的分类 从不同酌视角看，数据挖掘技术主要有以下两种分类方法： ( 1 ) 根据挖掘知识的种类分类：( 2 ) 根据采用的技术分类。 山东师范大学硕士学位论文 2 4 1 根据挖掘知识的种类分类 著名的d a t am i n i n g 专家j i a w e ih a r t 在参考文献 1 0 中认为数据挖掘得到的 知识可以分为六大类，因此根据挖掘知识的种类可将数据挖掘分为以下几类： 特征( c h a r a c t e r i s t i c ) 挖掘：对数据集概括总体特征，即对共性的描述。例如， 袋装鲜牛奶的保质期一般为十天。 关联规则( a s s o c i 撕o n ) 挖掘6 2 ：相关数据在不同属性之间或同一属性的不同 值之间的关联关系。例如，购买牛奶一购买面包。 分类( c l a s s i f i c a t i o n ) ：利用已知训练数据集的预定义类建立模型，并用模型 对数据库中的数据进行分类。例如，按每公里的油耗把汽车分类。 聚类( c l u s t e r i n g ) ：按一定距离或相似性测试度把数据分成一系列相互区分的 组，组之间的差别尽可能大，组内的差别尽可能小，与分类模式不同，进行聚类 前并不知道将要划分成几个组和什么样的组，也不知道根据哪些数据项来定义 组。例如，帮助市场分析人员从客户数据库中发现不同的客户群。 趋势分析( t r e n da n dd e r i v a t i o na n a l y s i s ) ：构造和使用模型以评估给定样本可 能具有的属性值或值区间。例如，股票走势分析。 直接模式分析( p a t t e r n d i r e c t e da n a l y s i s ) ：在数据中发现用户指定的模式，并 标识其特征。 2 4 2 根据挖掘采用的技术分类 数据挖掘中采用的方法综合了数据库、人工智能、统计学、模式识别、机器 学习、数据分析等领域的研究成果。现有的数据挖掘方法主要有以下几种： 1 决策树方法 利用信息论中的信息增益寻找出数据集中具有最大信息的字段，建立决策树 中的每一个结点，再根据字段的不同取值建立树的分支的过程，就是建立决策树 过程。国际上最有影响的决策方法是q u i n l a n 研究的i d 3 方法。 2 神经网络方法 它模拟人脑神经元结构，以m p 模型和h e b b 学习规则为基础，建立了三大 类神经网络模型。 1 ) 前馈式网络，以反向传播模型，函数型网络为代表，用于预测、模式识 山东师范大学硕士学位论文 别等方面。 2 ) 反馈式网络，以h o p f i e l d 离散模型和连续模型为代表，分别用于联想记 忆和优化计算。 3 ) 自组织网络，以a p t 模型，k o h o l o n 模型为代表，用于聚类。 3 模糊论方法 利用模糊集合理论对实际问题进行模糊评判、模糊决策，模糊模式识别和模 糊聚类分析。模糊性是客观存在的，系统的复杂性越高，模糊性越强，这是z a d e h 总结出的互克性原理。 4 遗传算法 这是模拟生物进化过程的算法，由三个基本算子组成： 1 ) 选择，是指从一个旧种群( 父代) 中选出生命力强的个体，产生新种群 ( 后代) 的过程。 2 ) 杂交，是选择两个不同个体的部分进行交换，形成新的个体。 3 ) 变异，对某些个体的某些基因进行变异。 遗传算法己在优化计算和分类机器学习等方面发挥了显著的作用。 二 5 统计分析方法 在数据库字段项之间存在两种关系：第一，函数关系( 能用函数公式表示的 确定性关系) ：第二，相关关系( 不能用函数公式表示，但仍是相关确定关系) 。 对它们的分析采用如下方法：回归分析、相关分析、主成分分析等。 6 贝叶斯网络。 贝叶斯网络基于后验概率的贝叶斯定理，是建立在对数据进行统计处理基础 上的方法。将不确定事件通过网络连接起来，可以对与其他事件相关的事件结果 进行预测，其网络变量可以是可见的，也可以隐藏在训练样本中。贝叶斯网络具 有分类、聚类、预测和因果关系分析的功能。其优点是易于理解，预测效果好， 缺点是对发生频率很低的事件预测效果不好。在医学和制造业等领域的应用具有 较好的效果。 7 粗糙集方法 粗糙集理论是上世纪8 0 处z p a w l a k 针对g f i r e g e 的边界域思想提出的，基 于给定训练数据内部的等价类的建立，用一对上下近似集合来逼近数据库中的不 9 山东师范大学硕士学位论文 精确概念。用于分类，可以发现不准确数据或噪声数据内在的结构联系；用于特 征归约，可以识别和删除无助于给定训练数据分类的属性：用于相关分析，可以 根据分类任务评估每个属性的贡献或意义。其主要思想是在保持分类能力不变的 前提下，通过知识约简，导出问题的决策或分类规则。 l o 山东师范大学硕士学位论文 第三章粗糙集理论的基础知识 粗糙集( r o u g hs e t ) 理论是一种刻划不完整性和不确定性的数学工具，其主要 思想是在保持分类能力不变的前提下，通过知识约简导出问题的决策或分类规 则。它能有效地分析和处理不精确、不一致、不完整等各种不完备信息，并从中 发现隐含的知识，揭示潜在的规律。粗糙集理论已广泛应用于近似推理【、医疗 诊断【2 9 1 、过程控制【3 0 】、图像处理【2 7 、粗糙控制 5 9 6 0 l i 6 “、晶体结构分析 2 6 1 、预测 建模f 2 4 1 1 25 1 、结构建模1 2 3 1 、投票分析1 、电力系统吲f 2 2 】、冲突分析1 5 0 】 5 2 等领 域。本章主要介绍粗糙集的基本模型、扩展模型，并简要说明了基于粗糙集理论 的数据挖掘方法。 3 1 粗糙集理论的基本概念 3 1 1 信息系统 信息系统( i n f o r m a t i o ns y s t e m ) 是粗糙集理论所研究的对象。若要应用粗糙集 理论，必须事先将所研究的对象表示为信息系统。信息系统是一个数据集，经常 表示为一张数据表。该数据表的每一行代表一个对象，这些对象可以是事例、事 件等。而数据表的每一列是对象的属性，这些属性可以是对象的特征、度量等。 信息系统s 可形式化地表示为s = ，其中： ( 1 ) u 是有限非空的对象集合，通常称为域； ( 2 ) 一是有限非空的属性集合，对每个属性口e a ，都有映射a j u 一圪，其中 圯是属性a 的值域。 如果信息系统s 的属性集合爿可分为条件属性集合c 与决策属性集合d 两 部分，即a = c u d 且c n d = - f g ，这种信息系统也可称为决策表( 或决策系统) 。 例3 1 下面的表3 1 就是一个信息系统，其中属性集合一= b 6 ，c , d ) ，域，_ x x 2 , x 3 , x 4 , x s , x 6 。如果令c = e 6 ，c ) ，d = d ，那么弘 就是一个决策表。 山东师范大学硕士学位论文 bd x l lil l 局 l 001 l 0 0 1 五 ol1 0 焉 1 l10 托 0ol 0 3 1 2 不可辨识关系 表3 1 信息系统s 不可辨识关系( i n d i s c e r n i b i l i t yr e l m i o n ) 也译作不分明关系。p a w l a k 教授所提 出的经典粗糙集理论中的不可辨识关系总是指等价关系，即该关系是自反，对称 和可传递的“1 。令s = 表示信息系统，那么任意属性子集b 野所对应的不 可辨识关系n d 国可定义为： i n d ( b ) = ( x ，y ) u 2j v a b 【日( x ) = 口( y ) 】) 不可辨识关系，d 髟也称为b 不可辨识关系，它与属性子集曰一一对应， 所以经常可以简单记为口。如果f 兑纠矽，那么通过属性子集曰，对象x , y 将是不可辨识的，即它们在属性集合b 上是不可区分的。根据不可辨识关系 i n d r 矽可导出一个等价划分u i n d f 矽，可简记为u b 。等价划分u b 中包含对 象x 的等价类一般记作m 口。由于等价类嘲b 内的所有对象在属性集合b 上都是 不可辨识，因此x 可代表等价类所有对象在b 上的取值情况，而其它对象都是冗 余的。 例3 2 以表3 ，1 的信息系统s 为例，令条件属性集合c = 珥6 ，c ) ，那么c 对应的不 可辨识关系i n d ( c ) 可以导出等价划分： u c = “工7 ，曲 ， x 2 ，x 3 ， 柳) ， x d 同样，令决策属性集合d = 田，那么d 所对应的不可辨识关系1 n d 倒也可 以导出等价划分： u d = x l ，x 2 ，z 3 ) ， x 4 ，x 5 ，柳) 在p a w l a k 教授提出粗糙集理论以后，也出现了许多扩展的和变种的粗糙集 理论旧1 4 1 ，其中一部分工作就体现在不可辨识关系的重定义上。比如，将上述的 不可辨识关系去除可传递性，就得到相似关系( 或相容关系) ，再以相似关系重定 山东师范大学硕士学位论文 义粗糙集理论中的其它基本概念，就可以得到一些与经典粗糙集理论不同的性质 和命题。 3 1 3 集合的近似 令信息系统s = 。根据对应属性集合b 4 的不可辨识关系1 n d 砂， 可以导出域u 的一个等价划分u b 。划分u b 中的等价类构成信息系统基本集 的集合。通过这些基本集合，可以构造集合的近似。 对任意对象集合x u ，根据属性集合b ，z 的b 下近似星( j ) 定义为： 笪( x ) = xj x 】。x ) 或者旦( ) = i x 。： 工】。z ) 工的b 上近似百( z ) 定义为： 百( ) = x l b k n x o ) 或者百( x ) = u x 8 ： z b n a 曰下近似的两个定义是等价的。集合盖的b 下近似有所有包含于它的等价类 合并得到。占上近似的两个定义也是等价的。集合x 的b 上近似由所有与它交集 不为空的等价类合并得到。集合互的b 下近似内的所有对象是根据b 上的知识 必然属于x 的对象，而集合z 的上近似内的对象是根据曰上的知识可能璃于x 的对象。 集合x 的边界域b ( 矽定义为： 删。( z ) = 曰( x ) 一旦( z ) z 的口边界域b n e 0 0 内的对象就是b 上近似无法确定属于z 的对象。另外， 对象集合 ，一百( x ) 常称为爿的b 外部域，它是由所有根据b 上的知识必定不属 于x 的对象所组成。 如果宦p 9 = o ，那么称z 是b 可定义的，否则就称z 是粗糙的。显然，一 个集合x 是否粗糙与具体的属性集合b 上的知识相关。集合z 可视为一个概念， 如果x 在属性集合b 上是粗糙的，那么说明口不足以完全描述x 所对应的概念。 粗糙集理论给出了四种类型的粗糙集： ( 1 ) 若垦( x ) a 且b ( x ) u ，则称x 为曰粗糙可定义的。 山东师范大学硕士学位论文 ( 2 ) 若星( z ) = 9 且百0 z ) 则称z 为b 内不可定义的。 ( 3 ) 若星( x ) a 且面( ) = u ，则称x 为b 外不可定义的。 ( 4 ) 若曼( x ) = a 且百( ) = u ，则称z 为b 完全不可定义的。 如果为b 粗糙可定义的，那么说明u 中韵某些对象是可以确定是属于z 或“二如果x 为b 内不可定义的，那么说明虽然不能确定u 中的任一对象是属 于z 的，但是可以确定【，中的某些对象是否属于以。如果x 为b 外不可定义的， 那么说明可以确定u 中的某些对象是否属于x ，但是不能确定u 中的任一对象 是否属于以r o 如果x 为曰完全不可定义的，那么说明无法确定u 中的任一对象 是否属于j 或础二 例3 3 以表3 1 的信息系统s 为例，令x l = x x ax 3 ) ，托= ( x 4x s , ) 。令c 碍6 ，c ) 。 由前面的例3 2 可知，不可辨识关系1 n d 习导出4 个等价类，分别是： 缸，奶) ， x 2 ，x s ， 和) ， x 6 ) 那么x i 的c 下近似( 五) ，c 上近似百( 五) ，以及c 边界域引忆1 ) 分别是： c ( x ) = l 扛k ：口 c 蜀) = 即，x 3 ) ， e ( 五) = u m c ： x c n x l 0 ) = x ，却，x 3 ，x 5 ， b n c ( x i ) 2c ( 五) 一( x i ) 2 x i ，x s 坦的c 下近似( 五) ，c 上近似e ( 五) ，以及c 边界域日d 恐) 分别是： ( 五) 2 u i x c ：i x c o _ 恐) 2 却， ， c ( 五) 2 u i x c ： x c n x 2 ：g 2 x j ，却，