(计算机应用技术专业论文)基于粗集求核和属性约简算法研究与应用.pdf_第1页
(计算机应用技术专业论文)基于粗集求核和属性约简算法研究与应用.pdf_第2页
(计算机应用技术专业论文)基于粗集求核和属性约简算法研究与应用.pdf_第3页
(计算机应用技术专业论文)基于粗集求核和属性约简算法研究与应用.pdf_第4页
(计算机应用技术专业论文)基于粗集求核和属性约简算法研究与应用.pdf_第5页
已阅读5页,还剩46页未读, 继续免费阅读

(计算机应用技术专业论文)基于粗集求核和属性约简算法研究与应用.pdf.pdf 免费下载

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

基于粗集求核和属性约简算法研究与应用 摘要 粗集理论是一种处理不精确、不一致、不完整信息的数据分析工具,不需 要提供问题所需处理的数据集合之外的任何先验信息,可直接对数据进行分析 和推理,从中发现隐含的知识,揭示潜在的规律。粗集理论己广泛地应用于机 器学习、数据库知识发现、决策分析、模式识别、医疗诊断和专家系统等领域。 在粗集理论中,约简与核是两个最重要的基本概念。约简是指在保持分类 能力不变的前提下,删除冗余的属性。核是所有约简的交集,其核属性的计算 往往是决策信息约简过程的出发点和关键。寻求快速的求核和属性约简算法是 粗集理论研究的重要内容之一。 本论文针对粗集求核和属性约简算法进行了研究,主要工作如下: 首先,本文研究了求取决策表核属性的经典算法,分析了时间复杂度和空 间复杂度,提出一种效率更高的计算核属性的算法,通过例子说明算法的具体 过程并验证了算法的正确性。 其次,本文研究了基于差别矩阵的属性约简算法及其局限性,提出了一种 基于依赖度的决策表属性约简算法,该算法不需求核运算,节省了时间和空间, 简化了求解过程。 最后,本文分析了中医数据的特点,介绍基于粗集理论的中医数据预处理 方法,并给出了一个中医诊断应用实例。 关键词:粗集;决策表;核;差别矩阵;属性约简;依赖度 i v t h es t u d ya n da p p l i c a t i o no fc o r ea n 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 mo nt h eb a s i so fr o u g h s e t a b s t r a c t t h er o u g hs e tt h e o r yi sat o o lo fs t a t i s t i c a la n a l y s i so ni n a c c u r a t e ,i n c o n s i s t e n t a n di n c o m p l e t ei n f o r m a t i o mb yd i r e c t l ya n a l y z i n ga n dd e d u c i n gt h ed a t aw i t h o u ta n y p r i o ri n f o r m a t i o me x c e p tt h ed a t as e t t o f i n du n d e r l y i n gk n o w l e d g ea n dp o t e n t i a l r u l e s i t sb e e nw i d e l yu s e di nt h ef i e l d so fm a c h i n el e a r n i n g ,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 e c i s i o na n a l y s i s ,p a t t e r nr e c o g n i t i o n ,m e d i c a ld i a g n o s i sa n de x p e r t s y s t e m ,e t c , t h ea t t r i b u t er e d u c t i o na n dc o r ea r et w oi m p o r t a n tc o n c e p t so ft h er o u g hs e t t h e o r y t h ef o r m e rd e l e t e st h er e d u n d a n ta t t r i b u t e s w i t hc l a s s i f i c a t i o nc a p a b i l i t y r e m a i n i n gu n c h a n g e d c o r ei st h ei n t e r s e c t i o no fa l lr e d u c t i o n s t h ea t t r i b u t ec o r eo f ad e c i s i o nt a b l ei so f t e nt h es t a r t i n gp o i n ta n dk e yt ot h er e d u c t i o np r o c e s so f d e c i s i o ni n f o r m a t i o n t h ef a s ta l g o r i t h mo fc o r ea n da t t r i b u t er e d u c t i o ni so n eo ft h e m o s ti m p o r t a n tc o n t e n t so ft h er o u g hs e tt h e o r yr e s e a r c h t h i sd i s s e r t a t i o ns t u d i e st h ea l g o r i t h mo fc o r ea n da t t r i b u t er e d u c t i o n t h em a i n w o r ki n c l u d e s : f i r s to fa l l ,i tr e v i e w st y p i c a la l g o r i t h mf o rc o u n t i n gc o r eo fd e c i s i o nt a b l e , a n a l y z e st h ec o m p l e x i t yo ft i m e & s p a c ea n dp u t sf o r w a r dan e wa l g o r i t h mo fh i g h e r e f f i c i e n c yt h r o u g he x e m p l i f i c a t i o nt ov e r i f yi t sv a l i d i t y s e c o n d l y ,t h ea t t r i b u t er e d u c t i o na l g o r i t h mb a s e do nd i s c e r n i b i l i t ym a t r i xa n d i t sl i m i t a t i o n sa r ee x p l o r e dt op r e s e n tan e wa t t r i b u t er e d u c t i o na l g o r i t h mb a s e do n d e p e n d e n c ed e g r e e ,w h i c hd o e sn o tn e e dc o r ec a l c u l a t i n g ,s a v i n gt i m e & s p a c ea n d s i m p l i f y i n gt h es l o v i n g p r o c e s sa sw e l l f i n a l l y ,t h ed a t ac h a r a c t e r i s t i c so fc h i n e s et r a d i t i o n a lm e d i c i n ea r ea n a l y z e d , i n t r o d u c i n gm e t h o d sf o rp r e t r e a t i n gc h i n e s et r a d i t i o n a lm e d i c i n ed a t ab a s e do nr o u g h s e tt h e o r ya r ea n da na p p l i c a t i o no fc h i n e s et r a d i t i o n a lm e d i c a ld i a g n o s i si sg i v e n k e y w o r d s :r o u g hs e t ;d e c i s i o nt a b l e ;c o r e ;d i s c e r n i b i l i t ym a t r i x ;a t t r i b u t e r e d u c t i o n ;d e p e n d e n c ed e g r e e v 图表清单 图1 1 数据挖掘主要步骤2 表2 1 决策表信息系统s l 1 2 表2 2 决策表信息系统s 2 1 2 表3 1 决策表信息系统s 3 1 8 表3 2s 3 的差别矩阵1 8 表3 3 两种算法的时阃性能比较。2 2 表3 4 决策表信息系统s 4 2 3 表3 5 规范格式决策表信息系统s 5 2 3 表3 6s 5 的差别矩阵2 3 表3 7 区分表t 2 4 表4 1 决策表信息系统s 6 2 6 表4 2s 6 的差别矩阵2 6 表4 3 决策表信息系统s 7 2 6 表4 4s 7 的差别矩阵2 7 表4 5 两种算法的时间性能比较3 0 表4 6 两种算法约简后的属性个数比较3 0 表4 7 决策表信息系统s 8 3 1 表4 8 约简后的s 8 3 l 表5 1 部分原始样本数据3 7 表5 2 决策表信息系统s 9 3 9 表5 3 约简后的s 9 3 9 表5 4 粗糙集方法的诊断结果4 0 i x 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果。据我所知,除了文中特别加以标志和致谢的地方外,论文中不包含其他人已 经发表或撰写过的研究成果,也不包含为获得 合孵工业大学或其他教育杌构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示谢意。 学位论文作者签字:善螽 签字日期: 罗年歹月7 日 学位论文版权使用授权书 本学位论文作者完全了解合肥工业大学有关保留、使用学位论文的规定, 有权保留并向国家有关部门或机构送交论文的复印件和磁盘,允许论文被查阅或借 阅。本人授权 合肥工业大学可以将学位论文的全部或部分论文内容编入有关数 据库进行检索,可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文者签名:蒡百 签字日期: 口7 年j 月7 日 f 7 日 学位论文作者毕业后去向: 工作单位: 通讯地址: 导师签名: 签字日期 电话: 邮编: 月7 致谢 感谢我的导师胡学钢教授。在本论文的撰写过程中,从理论知识的系统学 习到论文的选题,胡老师自始至终的言传身教,并给了我悉心的关怀和指导。 胡老师渊博的知识、严谨的治学态度、诲人不倦的师长风范以及不断进取、精 益求精的精神,都将对我今后的学习、工作产生深远的影响,是我一生学习的 榜样。在此谨向胡老师表示最崇高的敬意和最诚挚的感谢! 感谢合肥工业大学所有给我授课的老师,他们严谨的教学态度和高尚的品 德给我留下了深刻的印象,是我学习的楷模。 感谢答辩委员会的各位专家在百忙中抽时间评阅本文,并提出了宝贵的修 改建议。 感谢安徽中医学院医药信息工程学院的领导和同事对我工作和学习的支持 和帮助。 感谢我的家人和朋友,没有他们的关心、鼓励、支持和奉献,也就没有我 今天取得的成绩。 衷心的感谢所有关心和帮助过我的人们。 v i 作者:蔡莉 2 0 0 9 年5 月 第一章引言 本章首先对数据挖掘进行简单概述,包括数据挖掘的提出背景、定义及主 要步骤、数据挖掘系统的分类、数据挖掘的方法、应用及面临的问题。然后介 绍了本文的结构。 1 1 数据挖掘概述 1 1 1 数据挖掘技术产生的背景 近年来,数据挖掘引起了信息产业界的极大关注,其主要原因是随着数据 库技术和信息产业的迅速发展,快速增长的海量数据收集、存放在大型和大量 数据库中,没有强有力的数据分析工具,理解它们已经远远超出了人的能力。 人们迫切需要将这些数据转换成有用的信息和知识。获取的信息和知识可以广 泛应用于商务管理、生产控制、市场分析、工程设计、科学探索和医学研究等 领域。 数据挖掘是信息技术自然演化的结果【l 】。自从2 0 世纪6 0 年代以来,数据 库技术和信息技术已经系统地从原始的文件处理演化到复杂的、功能强大的数 据库系统。7 0 年代以来,数据库系统的研究和开发已经从层次数据库和网状数 据库系统发展到开发关系数据库系统、数据建模工具、索引和数据组织技术。 此外,用户通过查询语言、用户界面、优化的查询处理和事物管理,可以方便、 灵活地访问数据。进入8 0 年代中期,数据库技术的特点是广泛接受关系技术, 研究和开发新型的、功能强大的数据库系统。 在过去的几十年中,计算机硬件稳定的、令人吃惊的进步导致了功能强大 的计算机、数据收集设备和存储介质的大量供应。这些技术大大推动了数据库 技术和信息产业的发展,使得大量数据库和信息存储用于事物管理、信息检索 和数据分析。 大量的数据被描述为“数据丰富,但信息贫乏”。收集在大型数据库中的数 据变成了“数据坟墓”难得再访问的数据档案。这样,重要的决定常常不是 基于数据库中信息丰富的数据,而是基于决策者的直觉,因为决策者缺乏从海 量数据中提取有价值知识的工具。此外,当前的专家系统技术通常依赖用户或 领域专家人工地将知识输入知识库,这一过程不仅常常存在偏差和错误,而且 耗时、费用高。数据的丰富带来了对强有力的数据分析工具的需要,利用数据 挖掘工具进行数据分析,可以发现重要的数据模式,对商务决策、知识库、科 学和医学研究作出了巨大贡献。数据和信息之间的鸿沟要求系统地开发数据挖 掘工具,将数据坟墓转换成知识“金块”。 1 1 2 数据挖掘的定义及主要步骤 数据挖掘( d a t am i n i n g ,d m ) 就是从大量的、不完全的、有噪声的、模 糊的、随机的数据中,提取隐含在其中的、人们事先不知道的、但又是潜在有 用的信息和知识的过程。 这个定义包括以下四个层次的含义: ( 1 ) 数据源必须是真实的、大量的、含噪声的: ( 2 ) 发现的是用户感兴趣的知识; ( 3 ) 发现的知识要可接受、可理解、可运用; ( 4 ) 所有发现的知识都是相对的,是有特定前提和约束条件、面向特定领域 的。 数据挖掘与传统的数据分析工具的主要区别在于它们探索数据关系时所 使用的方法。传统的数据分析工具使用基于验证的方法,即用户首先对特定的 数据关系作出假设,然后使用分析工具去确认或否认这些假设。这种方法的有 效性受到许多因素的限制,如提出的问题和预先假设是否合适等。与分析工具 相反,数据挖掘使用基于发现的方法,是在没有明确假设的前提下去挖掘信息、 发现知识。 数据挖掘的主要步骤包括问题定义、数据选择、数据预处理、选定数据挖 掘算法、模式解释、知识评价、知识表示等阶段。如图1 1 。 图1 1数据挖掘主要步骤 ( 1 ) i 右- j 题定义 数据挖掘的主要目标是从大型数据集中进行知识发现,在大量数据中发现 有用的令人感兴趣的信息,因此发现何种知识就成为整个过程中第一个也是最 重要的一个阶段。它驱动了整个数据挖掘过程,在很大程度上决定着数据挖掘 2 的结果。在问题定义过程中,数据挖掘人员必须和领域专家以及最终用户紧密 协作,一方面明确实际工作对数据挖掘的要求,另一方面通过对各种学习算法 的对比而确定可用的学习算法。 ( 2 ) 数据选择 根据定义的问题和用户的要求从原始数据库中选取一组适用于数据挖掘的 数据,将其存入目标数据库。选取的数据必须考虑到以下三个方面:第一,通 常特定的挖掘算法只能使用特定的数据格式,因此数据必须进行相应的格式转 换。第二,选取的数据要具有代表性,各个类别的数据在概率分布上要符合实 际情况。第三,只需选择与特定挖掘任务相关的属性。 ( 3 ) 数据预处理和转换 数据预处理主要是对阶段( 2 ) 产生的数据进行再加工,通过相关性分析去除 冗余属性,消除噪声数据,补足缺值数据,进行数据的完整性、一致性检验, 以及数据的归一化、离散化处理等,将数据转换成一个分析模型,这个分析模 型是针对挖掘算法建立的,建立一个真正适合挖掘算法的分析模型是数据挖掘 成功的关键。 ( 4 ) 选定数据挖掘算法 确定了挖掘任务后,就要选定数据挖掘算法,如粗集、神经网络、决策树、 统计方法、遗传算法等,从数据中提取感兴趣的知识。选择算法有两个考虑因 素:一是不同的数据有不同的特点,因此需要用与之相应的算法来挖掘;二是 根据用户或实际运行系统的要求选择与之相应的算法来挖掘。 ( 5 ) 模式解释 对发现的模式进行解释,在这个过程中,为了取得更为有效的知识,可能 会返回前面处理步骤中的某些步以反复提取,从而提取出更有效的知识。 ( 6 ) 知识评价 将用户理解的、并被认为是符合实际和有价值的模式模型形成了知识。这 期间也包含对知识的一致性的检查,以确信本次发现的知识不与以前发现的知 识相抵触,是否存入基础知识库。 数据挖掘质量的好坏有两个影响因素:一是所采用的数据挖掘技术的有效 性;二是用于挖掘的数据的质量和数量。整个挖掘过程是一个不断反馈的过程。 在对挖掘的知识进行评测后,根据结果可以决定是否返回到某个步骤,重新进 行某些处理过程,在处理的任意阶段都可以返回以前的步骤进行再处理。 1 1 3 数据挖掘系统的分类 数据挖掘是一个交叉学科领域,受多个学科影响,如数据库系统、统计学、 机器学习、可视化和信息科学等。此外,依赖于所用的数据挖掘方法,以及可 以使用的其他学科的技术,如神经网络、粗糙集理论、知识表示、归纳逻辑程 序设计或高性能计算。依赖于所挖掘的数据类型或给定的数据挖掘应用,数据 挖掘系统也可能集成空间数据分析、信息检索、模式识别、图象分析、信号处 理、计算机图形学、w e b 技术、经济、医药学或心理学领域的技术。 由于数据挖掘源于多个学科,因此数据挖掘研究就产生了大量的、各种不 同类型数据挖掘系统。这样,就需要对数据挖掘系统给出一个清楚的分类。这 种分类可以帮助用户区分数据挖掘系统,确定最适合其需要的数据挖掘系统。 根据不同的标准,数据挖掘系统可以分类如下川: ( 1 ) 根据挖掘的数据库类型分类 数据库系统本身可以根据不同的标准分类,每一类可能需要自己的数据挖 掘技术。这样,数据挖掘系统就可以相应的分类。例如,若根据数据模型分类, 可以有关系的、事务的、面向对象的、对象一关系的和数据仓库的数据挖掘系统。 若根据所处理的数据的特定类型分类,则有空间的、时间序列的、文本的、多 媒体的和w w w 数据挖掘系统。 ( 2 ) 根据挖掘的知识类型分类 根据挖掘的知识类型即挖掘的功能分类,如特征化、区分、关联、分类、 聚类、孤立点分析、演变分析、偏差分析、类似性分析等。一个全面的数据挖 掘系统应当提供多种或集成的数据挖掘功能。 ( 3 ) 根据所用的数据挖掘技术分类 数据挖掘技术可以根据用户交互程度或所用的数据分析方法描述。复杂的 数据挖掘系统通常采用多种数据挖掘技术,或采用有效的、集成的技术,结合 多种方法的优点。 ( 4 ) 根据应用分类 不同的应用领域通常需要集成对于该应用特别有效的方法。如适合金融、 电信、股市、医药等应用领域数据挖掘系统。 1 1 4 数据挖掘的方法 数据挖掘的研究融合了多个不同学科领域的技术与成果,使得目前的数据 挖掘方法表现出多种多样的形式 2 , 3 1 。 ( 1 ) 统计方法 传统的统计学为数据挖掘提供了许多判别和回归分析方法,常用的有贝叶斯推 理、回归分析、方差分析等技术。贝叶斯推理是在已知新的信息后修正数据集 概率分布的基本工具,处理数据挖掘中的分类问题;回归分析用来找到一个输 入变量和输出变量关系的最佳模型;方差分析一般用于分析估计回归直线的性 能和自变量对最终回归的影响,是挖掘应用中有力的工具之一。 ( 2 ) 关联规则 关联规则是一种简单、实用的分析规则,它描述了一个事物中某些属性同时出现 4 的规律和模式,是数据挖掘中最成熟的技术之一。它是由r a g r a w a l 等人于1 9 9 3 年首 先提出的,最经典的关联规则的挖掘算法是a p r i o r i ,该算法先挖掘出所有的频繁项集, 然后由频繁项集产生关联规则,许多关联规则频繁项集的挖掘算法都是由它演变而来 的。关联规则适合于在大型数据集中发现数据之间的有意义关系,但是,并不是所有 通过关联得到的属性之间的关系都有实际应用价值,对这些关联规则进行有效的评 价,筛选出用户真正感兴趣的、有意义的关联规则尤为重要。 ( 3 ) 聚类分析 聚类分析时要根据所选样本间关联的标准将其划分成几个组,同组间的样本具有 较高的相似度,不同组的样本则相异。常用的技术有分裂算法、凝聚算法、划分聚类 和增加聚类。聚类方法适合于探讨样本间的内部关系,从而对样本结构做出合理的评 价,此外,聚类分析还用于对孤立点的检测。有时进行聚类不是为了将对象相聚在一 起,而是为了更容易地使某个对象从其它对象中分离出来。聚类分析已被广泛应用于 经济分析、模式识别、图像处理等多种领域。 ( 4 ) 决策树方法 决策树学习是一种通过逼近离散值目标函数的方法,通过把实例从根结点排列到 某个叶子结点来分类实例,叶子结点即为实例所属的分类。树上的每个结点说明了对 实例的某个属性的测试,该结点的每一个后继分支对应于该属性的一个可能值,分类 实例的方法是从这棵树的根结点开始,测试这个结点指定的属性,然后按照给定实例 的该属性值对应的树枝向下移动。决策树方法主要应用于数据挖掘的分类方面。 ( 5 ) 神经网络 神经网络建立在自学习的数学模型基础之上,能够对大量复杂的数据进行分析, 并可以完成对人脑或其他计算机来说极为复杂的模式抽取及趋势分析,神经网络既可 以表现为有指导的学习,也可以是无指导聚类。无论哪一种,输入到神经网络中的值 都是数值型的。典型的神经网络模型主要分三大类:以感知器、b p 反向传播模 型、函数型网络为代表的,用于分类、预测和模式识别的前馈式神经网络模型; 以h o p f i e l d 的离散模型和连续模型为代表的,分别用于联想记忆和优化计算的 反馈式神经网络模型;以a r t 模型、k o h o l o n 模型为代表的,用于聚类的自组织 映射方法。 ( 6 ) 支持向量机 支持向量机是在统计学习理论的基础上发展起来的一种新的机器学习方 法。它是基于结构风险最小化原则上的,尽量提高学习机的泛化能力,具有良 好的推广性能和较高的分类精确性,能有效地解决学习问题。另外,支持向量 机算法是一个凸优化问题,局部最优解一定是全局最优解,这些特点都是包含 神经网络在内的其它算法所不能及的。支持向量机可以应用于数据挖掘的分类、 回归、对未知事物的探索等。 ( 7 ) 遗传算法 5 遗传算法是一种受生物进化启发的学习方法,通过变异和重组当前已知的最好假 设来生成后续的假设。每一步通过使用目前适应性最高的假设的后代代替群体的某个 部分,来更新当前群体的一组假设,从而实现各个个体的适应性的提高。遗传算法由 三个基本过程组成:繁殖是从一个旧种群选出生命力强的个体,产生新种群的过程; 交叉是选择两个不同个体的部分进行交换,形成新个体的过程;变异是对某些个体的 某些基因进行变异的过程。在数据挖掘中,遗传算法被用作评估其它算法的适合度。 ( 8 ) 粗糙集 粗糙集能够在缺少关于数据先验知识的情况下,只以考察数据的分类能力 为基础,解决模糊或不确定数据的分析和处理问题。粗糙集用于从数据库中发 现分类规则的基本思想是将数据库中的属性分为条件属性和决策属性,将数据 库中的元组根据各个属性不同的属性值分成相应的子集,再对条件属性划分的 子集与决策属性划分的子集之间上下近似关系生成判定规则。所有相似对象的 集合称为初等集合,形成知识的基本成分。任何初等集合的并集称为精确集, 否则,一个集合就是粗糙的。每个粗糙集都具有边界元素,即那些既不能确定 为集合元素,也不能确定为集合补集元素的元素。粗糙集理论可以应用于数据 挖掘中的分类、发现不准确数据或噪声数据内在的结构联系等方面。 1 1 5 数据挖掘的应用 目前,数据挖掘已被广泛地应用于社会各行各业,其中典型的应用有以下 几个领域【2 ,4 】: ( 1 ) 科学研究 在天文、气象、生物技术等科学研究领域中,所获得的庞大实验和观察数 据推动了数据挖掘技术应用发展。目前己获得了一些重要的研究成果,如天空 图像分析、金星上的火山定位和地震的侦测、基因工程的研究。 ( 2 ) 商业 在商业领域特别是零售业,积累了大量的销售数据,利用数据挖掘可以进 行销售、顾客、产品、时间和地区的多维分析;促销活动的有效性分析;顾客 忠诚度的分析;购买推荐分析等,为经营管理人员提供正确的决策手段。 ( 3 ) 金融业 在金融领域,如银行、证券公司等交易数据量和存储量都是非常巨大的。 因此,可以利用数据挖掘对金融数据仓库进行多维分析,查看负债和收入的变 化情况;对贷款偿付预测和客户信誉政策进行分析;利用分类和聚集的方法对 用户群体进行识别和目标市场分析;对金融犯罪进行预防和侦破等。 ( 4 ) 电信业 电信业已经从单纯地提供市话和长话服务演变成提供语音、传真、寻呼、 移动电话、图像和w e b 数据传输等综合电信服务。在激烈的电信市场竞争中, 6 可以利用数据挖掘技术来理解商业行为、确定电信模式、捕捉盗用行为、更好 地利用资源和提高服务质量。 ( 5 ) 医学 数据挖掘在医学上的应用十分广泛,从新药研发到医疗诊断,都可以利用 数据挖掘技术来提高效率和效益。采用数据挖掘技术建立的药物开发系统,可 以确定药效基团,指导新药的研究与开发,从而缩短新药的研究开发周期。将 数据挖掘技术应用到医学信息数据库中,可以发现其中的医学诊断规则和模式, 辅助医生进行疾病诊断,从而使人类疾病的诊断、预防和治疗达到了一个新的 水平。利用数据挖掘技术可以预测未来某段时间内哪些药品使用的频率最高或 最低,哪些疾病的发病率最高等问题。 ( 6 ) 网络 数据挖掘在网络中的应用也正在成为一个热点。网络信息挖掘的应用涉及 到电子商务、网站设计和搜索引擎服务等众多方面。 1 1 6 数据挖掘面临的问题 数据挖掘是一个新兴的研究领域,许多问题还有待于研究,随着这些问题 的解决,将为数据挖掘的未来的发展提供了更大的空间。目前面临的问题主要 包括下列几个方面1 3 , 5 - 7 】。 ( 1 ) 算法效率和可伸缩性 数据挖掘通常是直接面向海量数据库,数据结构也显得非常复杂。海量的 数据一方面提供了挖掘的基础和前提,但同时维数的增加也会给数据挖掘的实 现带来难度。许多针对较小规模数据的技术在超大规模数据情况并不适用。因此, 数据挖掘系统必须能有效地处理海量数据,其算法必须是高效率的、可伸缩的。 ( 2 ) 处理不同类型的数据和数据源 目前数据挖掘系统处理的数据库大多是关系数据库。随着计算机网络的发 展和成熟,将许多不同类型、不同用途、不同存储地点的数据源联接起来,形 成巨大的分布式异构数据库。不同来源数据的格式和语义可能不统一,数据挖 掘系统应当能帮助用户揭示异构数据库中的高级数据规律。因此,保证数据挖 掘系统能有效地处理此类数据库中的数据是至关重要的。 ( 3 ) 寻求数据挖掘过程中更优秀的可视化方法 数据挖掘中操作者的适当参与能加速数据挖掘过程。实现在知识发现的过 程中进行人机交互图文数并茂便于知识发现的过程能够很容易的被用户理 解。因此,准确而直观地描述挖掘结果和友好而高效的用户界面一直是研究的 重要课题。 ( 4 ) 研究w 曲数据挖掘 由于w e b 上存在大量信息,并且w e b 在当今社会扮演越来越重要的角色,因 7 此,实现w e b 挖掘将成为数据挖掘中一个非常重要的领域。 ( 5 ) 数据挖掘中的隐私保护与信息安全 数据挖掘能从不同的角度和不同的抽象层上看待数据,这将潜在地影响数 据的私有性和安全性。因此,数据挖掘要特别注意隐私权的保护。 ( 6 ) 探索新的应用领域 随着数据挖掘的日益普及,它的应用领域也在不断扩大。由于通用数据挖 掘系统在处理特定应用问题时有其局限性,因此,开发针对特定应用的数据挖 掘系统是必然趋势。 ( 7 ) 数据挖掘语言的标准化 研究专门用于知识发现的数据挖掘语言,使其走向形式化和标准化,有利 于用户学习和实用数据挖掘系统。 ( 8 ) 建立有效的评估体系 不同的人对同样的数据进行挖掘,可能产生不同的结果甚至差异很大,要 和专业知识相结合才能对其做出判断,这就需要建立有效的评估体系来评价。 1 2 本文结构 本文共分六个章节,整体结构安排如下: 第一章主要对数据挖掘进行简单概述,提到粗集理论可以应用于数据挖掘 中的分类、发现不准确数据或噪声数据内在的结构联系等方面。 第二章主要介绍粗集理论知识和基本概念,其中约简与核是两个最重要的基 本概念。 第三章分析了求决策表核属性经典算法的时间复杂度和空间复杂度,提出一 种效率更高的计算核属性的算法,通过例子说明算法的具体过程并验证了算法的 正确性。 第四章研究了基于差别矩阵的属性约简算法及其局限性,提出了一种基于依 赖度的决策表属性约简算法,该算法不需求核运算,简化了求解过程。 第五章介绍了中医数据的特点,介绍基于粗糙集理论的中医数据预处理方 法,并给出了一个中医诊断应用实例。 第六章总结全文。对本文所作工作进行了总结,并提出今后工作的方向。 1 3 本章小结 随着数据库和信息产业的发展,大量的数据被描述为“数据丰富,但信息贫 乏”,数据和信息之间的鸿沟要求系统地开发数据挖掘工具,将数据坟墓转换成 知识“金块”。数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的 数据中,提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识 的过程。目前,数据挖掘已被广泛地应用于社会的各行各业。 8 第二章粗集理论 本章首先介绍基本粗集理论的研究概况、基本思想、特点、目前具有代表 性的粗集知识发现系统以及粗集理论的研究方向,接着给出粗集理论的基本概 念。 2 1 粗集理论概述 2 1 1 粗集理论研究概况 粗集( r o u g hs e t ) 理论是1 9 8 2 年由波兰科学家z p a w l a k 提出的瞵j 。但由 于最初的研究成果多以波兰文字发表,该项研究局限于东欧各国,当时并未引 起国际计算机学界的重视。直到八十年代未,粗集理论才逐渐引起世界各国学 者的注意。 1 9 9 1 年p a w l a k 发表了第一本关于粗集专著【9 】,奠定了粗集理论基础。随 着1 9 9 2 年r s l o w i n s k i 主编的关于粗集应用与相关方法比较的论文集【lo j 的出 版,推动了国际上对粗集理论与应用的深入研究,掀起了研究粗集理论的高潮。 19 9 2 年在波兰k i e k r z 召开了第一届国际粗集学术讨论会,着重讨论了集合 近似定义的基本思想及其应用。此后每年都召开以粗集为主题的国际会议,包 括“粗糙集进展与计算国际会议”和“粗糙集、模糊集、数据挖掘与粒度一软计算 国际会议”等。2 0 0 4 年国际粗糙集学会主办了第一本粗糙集国际期刊( a d v a n c e s i nr o u g hs e t ) ) 。 国内对粗集的研究起步比较晚,但发展很快,现在国内的糙集研究已经成 为国际粗集研究不可忽视的重要力量。从2 0 0 1 年起每年召开一次“中国粗集与 软计算学术研讨会”,2 0 0 3 年第九届粗糙集、模糊集、数据挖掘与粒度一软计 算国际会议和2 0 0 6 年第一届粗糙集与知识技术国际会议在重庆召开。从2 0 0 7 年起更名为“中国r o u g h 集与软计算学术会议”,很多学者出版了有关粗糙集的 专著,如:刘清【1 1 1 、王国胤【12 1 、曾黄麟1 3 , 1 4 】、张文修【1 5 - 17 1 、胡寿松【1 8 】等。 随着粗集理论广泛深入地研究以及每年国际国内研讨会成功地召开,粗集 理论有了长足地发展,己广泛地应用于机器学习、数据库知识发现、决策支持 与分析、医疗诊断、专家系统、模式识别等领域。 2 1 2 粗集理论的基本思想 粗集理论是针对g f r e g e 的边界线区域思想提出的一种处理含糊和不确定 性问题的新型数学工具。该理论是建立在分类机制基础上的,它将分类理解为 在特定空间上的等价关系,而等价关系构成了对该空间的划分。粗集理论将知 识理解为对数据的划分,每一被划分的集合称为概念,其基本思想是利用已知 的知识库,将不精确或不确定的知识用己知知识库中的知识来( 近似) 刻画。 9 2 1 3 粗集理论的特点 粗集理论通过知识约简,导出问题的决策或分类规则。粗糙集方法能够在 缺少数据先验知识的情况下,以观测数据分类能力为基础,解决模糊或不确定 数据的分析和处理,其算法简单,易于操作。 粗集理论能在创立后的不长时间内得到迅速应用是因为具有如下特点: ( 1 ) 粗集不需要先验知识。粗集分析方法仅仅利用数据本身提供的信息,而 不需要提供问题所需处理的数据集合之外的任何先验知识,所以对问题的不确 定性的描述或处理可以说是比较客观的。 ( 2 ) 粗集是一个强大的数据分析工具,能够表达和处理不完备信息,在保留 关键信息的前提下对数据进行化简并求得知识的最小表达式;可以从经验数据 中获得规则知识;识别并评估数据之间的依赖关系。 ( 3 ) 粗集以不可分辨关系为基础,侧重分类,即根据分析对象的特征属性对对象 的类别进行划分。在粗糙集理论中,最核心的概念就是分类。 2 1 4 粗集知识发现系统 目前,国外基于粗集的知识发现系统已经开发了不少,其中具有代表性的 有l e r s 19 1 、r o s e t 2 0 1 、k d d r 2 1j 和r o u g he n o u g h 2 2 】等。 ( 1 ) l e r s 系统 l e r s 系统是美国k a n s a s 大学开发的基于粗集的实例学习系统,该系统主要 用于环境保护、气候研究和医疗研究等。 ( 2 ) r o s e 系统 r o s e 系统是波兰p o z n a n 工业大学计算科学研究所智能决策支持系统实验 室研制的。该系统实现了p a w l a k 的基本粗糙集模型和可变精度粗糙集模型,并 成功应用于医学、药剂学、技术诊断、金融和管理科学、图像与信号处理、软 件工程评估等。 ( 3 ) k d d r 系统 k d d r 系统是由加拿大r e g i n a 大学研制的,它基于可变精度粗糙集扩展模 型的数据库知识发现系统,采用知识发现的决策矩阵方法。该系统成功应用于 医学数据分析、电信市场的决策分析及水资源调度等。 ( 4 ) r o u g he n o u g h 系统 r o u g he n o u g h 系统是挪威t r o l ld a t ai n e 公司开发的,包括数据输人、预 处理、编辑、生成可辨识矩阵、集合近似、约简、生成规则、预测和分析。 国内也开发了一些系统,如中国科学院计算技术研究所开发的k d t 、南京 大学研制的k n i g h t 、刘清等【2 3 1 运用粗糙集理论开发的血液粘滞综合症血液流变 学诊断专家系统在医疗诊断中得到了很好的应用,达到国际领先水平等。随着 粗糙集广泛地应用,相信一定会有更多的越来越成熟的基于粗集的知识发现系 1 0 统出现。 2 1 5 粗集理论的研究方向 在今后几年内,对粗集知识发现的研究主要集中在以下几个方面: ( 1 ) 快速、高效的约简算法研究 约简算法是粗集知识发现的基础,国内外许多学者在这方面做了大量的 研究,但是目前还还没有一种非常有效的约简算法,因此寻找快速高效的约简 算法是粗集理论的研究热点之一。 ( 2 ) 属性的离散化研究 由于粗集理论只能处理离散化属性,而现实中存在的数据一般都是连续型 的属性,因此,将连续属性的进行离散化处理十分重要。但离散化会造成信息 损失。目前还没有一种比较公理化的离散化处理方法,连续属性的离散化处理 是今后研究的重要课题之一。 ( 3 ) 不确定性问题的理论研究 粗集理论中常用粗糙度和精度来刻画知识的不确定性,如何寻求一个合适 的度量来刻画知识的不确定性是粗集理论研究的一个重要方向。 ( 4 ) 粗集与其他方法的结合问题 目前有很多知识发现方法,粗集如何与其他方法结合,从而提高知识发现 效率,仍需要进一步研究。 2 2 粗集理论的基本概念 2 2 1 信息系统 粗集理论认为知识是人类和其它物种所固有的分类能力。分类是人类的最 基本的智能行为,是推理、学习与决策中的关键问题【8 1 。因此,粗集理论重点 讨论对对象进行分类的能力,实际上就是按照某种特征属性将具有相同属性值 的对象分别归纳在各自的集合中,即按照某种等价关系进行分类。并试图发现 各个属性和分类结果之间的关系,找到描述分类结果的本质特征属性,发现分 类规则。粗集理论采用了一种称为信息系统的数据表达方法,也称为所考虑对 象的近似空间。基于粗集理论进行数据分析的全部对象的数据集合称为信息系 统。 定义2 1 一个近似空间定义为一个关系系统( 或二元组) k = ( u ,r ) ,其中, u o 是由对象组成的有限集合,称为论域,r 是u 上的等价关系的一个族集。 定义2 2 信息系统是指一个四元组s = u ,a ,v ,f 。其中u 是一个非空集合, u = x l ,x 2 ,x n ) 是一个有限的对象的论域构成,x i 表示数据库中的一条记录; a = cu d 是属性集合,子集c = a l ,a 2 ,a m ) 和d = d ) 分别称为条件属性集和决策 属性集,v 是属性值组成的集合;f 是信息函数,用于将记录u 转换为在属性a 上的取值 f :u a v j 即f ( u ,a ) = v ( u u ,a a ,v v ) 信息系统可以很方便地用数据表表示,表的行代表对象u u ,列代表属性 a e a ,表中的数值代表对象u 对应属性a 的属性值,记为a ( u ) 。上面所定义的 信息系统s ,若 d ) 不存在,就是一般意义上的信息表达系统;若 d ) 存在,则 称为决策表信息系统,记为s = u ,cud ,v f 。 例2 1 在表2 1 中给出了一些关于病人是否感冒的决策表信息系统s 1 ,其 中u = x l , x 2 ,x 3 , x 4 ,x 5 ,x 6 ) ,条件属性为c = 头痛,体温,肌肉痛 ,决策属性d = 感冒) 。 表2 1决策表信息系统s 1 u 头痛体温肌肉痛 感冒 x l是很高是 是 x 2 否偏高否是 x 3 否很高是是 x 4 是正常是否 x 5 是偏高是是 x 6否正常 是否 在一个决策表信息系统中,每一个u i 及其所对应的属性值称为一个规则。 当i j 时若存在f ( u i , c ) = f ( u j ,c ) 但f ( u i ,d ) # f ( u j ,d ) ,即两个记录所有的条件属性值 相同,但对应的决策属性值不同,则称该系统为不相容系统,此时,u i 与u j 所 对应的规则为不相容规则。 在决策表信息系统s 2 中记录1 与记录2 所有的条件属性值相同,而对应 的决策属性值不同,如表2 2 所示,因此该决策表信息系统为不相容系统。 表2 2决策表信息系统s 2 uabc d x l 0 ll 0 x 2 01l1 x 3 0 0l0 x 4 lol l x 5 1 l0 1 2 2 2 不可分辨关系 定义2 3 对于信息系统s = u ,a ,v ,d ,bc _ a 且b ,对象x i ,x j u ,称 1 2 二元关系i n d ( b ) 为属性集合b 的不可分辨关系: i n d ( b ) = ( x i ,x j ) u x u l f ( x i ,a ) = f ( x j ,a ) ,v a b ) ( 公式2 1 ) 2 2 3 等价类 定义2 4 在信息系统s = u ,a ,v f ) 中,如果bc a ,则对任意x u ,等价 类为: 【x 】b = y u l ( x ,y ) i n d ( b ) ( 公式2 2 ) 显然,在属性集b 的描述下, x b 中的任意元素之间包含x 对应属性值相 同,因此它们之间不可区别。所有由i n d ( b ) 得出的等价类的并便构成了论域u 上的划分:u i n d ( b ) 如在表2 1 中,b = 头痛,肌肉痛) ,u i n d ( b ) - - x l ,x 4 ,x s , x 2 , x 3 , x 6 ) ,共有3 个等价类,这三个等价类是无法区分的。 2 2 4 集合的近似 定义2 5 粗糙集对不确定概念的描述是通过下近似( 记为b 一( x ) ) 和上近 似( 记为b 一( x ) ) 这两个精确概念来表示的。一个概念的下近似是指,其下近 似中的元素肯定属于该概念:一个概念的上近似是指,其上近似中的元素可能 属于该概念。上近似和下近似构成了粗糙集研究中的两个基本运算。 对于每个集合x g u 和不可分辨关系b ,x 的上近似和下近似可以用下列 式子来表示: b 一( x ) = u y i y i u

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论