（控制科学与工程专业论文）粗糙集理论在医学数据挖掘中的应用.pdf

摘要 摘要 粗糙集理论是一种用于处理不确定性和含糊性知识的数学工具，其基本思 想是在保持分类能力不变的前提下，通过知识约筒，导出分类规则。它无需提 供相关数据集合外的任何先验信息，适合于发现数据中隐含的、潜在有用的规 律，找出数据内部的关联关系和特征。经过2 0 多年的完善和发展，粗糙集理论 已成为软计算方法的一个重要分支，其应用范围已经扩展到模式识别、机器学 习、决策分析和知识获取等领域。 本文首先从医学数据的特点出发，阐述了医学数据挖掘的一般步骤、关键 技术和智能化方法。本文主要探讨粗糙集理论在医学数据挖掘中的应用，对粗 糙集的基本理论以及基于粗糙集的知识获取的基本概念进行了详细说明。在数 据预处理方面，着重探讨了连续属性离散化的问题，并改进了布尔推理和粗糙 集理论相结合的离散化算法；在知识约简方面，提出了基于二进制可辨识矩阵 的属性约简算法，并通过实验说明改进是成功的；在规则获取方面，初步研究 了概率规则的获取算法和预测中规则匹配的问题。本文中所提到的算法在m a t l a b 软件环境下都得到了实现，并且应用于一个医学数据集的示例分析中。 关键词：粗糙集理论，医学数据挖掘，知识获取，属性约简 一一 垒! ! 壁璺 ，i h et h e o r ya n da p p l i c a t i o no fr o u - 曲s e t se n j o ye n o 傩o u ss u c c c s s r o u g hs e t s t h e o r yb e c o m e sa ni m p o r t a n tb r a n c ho fs o f tc o m p u t a t i o na n di n v o l v e sm a n yf e l d s i n c l u d i n gp a t t e r ni d e n t i f i c a t i o n ，m a c h i n el e a r n i n g , d e c i s i o n - m a k i n g a n a l y s i s a n d s u p p o r t ，k n o w l e d g ed i s c o v e r y a n da c q u i s i t i o n 1 n h et h e o r yo fr o u g h s e t s ，p r o p o s e db yp a w l a k ，i sa l le x t e n s i o n o fs e tt h e o r yf o rt h e s t u d yo fi n t e l l i g e n ts y s t e m sc h a r a c t e r i z e db yi n s u 蚯c i e n ta n di n c o m p l e t ei n f o r m a t i o n r o u i g hs e t st h e o r yi st y p i c a l l ya p p l i e dw i t h i nd e c i s i o n t a b l e sa n do f f e r sa na l t e r n a t i v e t om o r ec o n v e n t i o n a lt e c h n i q u e sf o rc l a s s i f i c a t i o na n dr u l ei n d u c t i o n r o u g hs e t s t h e o r y i su s e dt od e r i v e i m p l y i n g , p o t e n t i a l a n du s e f u lr u l e sa n dd e t e c tt h e t e l a t i o n s h i pw i t h i nt h eh a t e l l i g e n ts y s t e m s t h i sp a p e rb e 百n sw i t l lt h ec h a r a c t e r i s t i c so fm e d i c a ld a t a ，a n di n t r o d u c e st h es t e p s ， k e yt e c h n i q u e s a n d i n t e l l i g e n ta p p r o a c h e sa p p l i e d t om e d i c a ld a t a m i n i n g i t c o n t i n u e st or e v i e wt h eb a s i ca n de x t e n s i v em o d e l so fr o u g hs e t sa n de x p l o r e st h e d a t ap r e p r o c e s s i n g ，a r 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 ni m p r o v e m e n t o ng r e e da l g o r i t h mi s p r e s e n t e d i nt h e a s p l e c t o fa t t r i b u t ed i s c r e t i z a t i o na n da r c d u c t i o na l g o r i t h mb a s e do nb i n a r yd i s c e r n i b l em a t r i xi sp r o p o s e di nt h ea s p e c to f a t t r i b u t er e d u c t i o n t h ea l g o r i t h m sm e n t i o n e di nt h i sp a p e ra r er e a l i z e di nt h em a t l a b e n v i r o n m e n ta n dd e r i v er e s u l t si nat e s tw i t ham e d i c a ld a t a b a s e k e y w o r d s ：r o u g h s e t st h e o r y , m e d i c a ld a t am i n i n g , k n o w l e d g ca c q u i s i t i o n ， a t t r i b u t er e d u c t i o n 学位论文版权使用授权书 本人完全了解同济大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：荸殍蜂 洲f 年弓月1 占日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名； 年月 口年月 日 同济大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 虢i 习磋牮 ，= 肿r 年雩月 f 占日 第1 章绪论 近年来，随着电子信息技术的迅速发展，医院信息系统( h o s p i t a l i n f o r m a t i o n s y s t e m h i s ) 和数字医疗设备的广泛应用，医院数据库的信息容量不断膨胀， 如何充分利用这些宝贵的医学信息资源来为疾病的诊断和治疗提供科学的决 策，促进医学研究，已成为人们关注的焦点。数据库技术的发展解决了海量数 据的存储和数据检索的效率问题，但无法改变“数据爆炸但知识贫乏”的现象， 而数据挖掘技术可以发现医学信息数据库中潜在的医学诊断规则和模式，从而 辅助医生进行医疗诊断。医学数据挖掘【1 】是一门涉及面广、技术难度大的新兴交 叉学科，需要从事智能信息处理、计算机、应用数学的科研人员与医务工作者 通力合作。 1 1 医学数据的特点 医学数据首先是以治愈患者为目的而搜集的，其次才是用于医学研究的资 源。挖掘医学数据库跟挖掘一般的数据库相比，具有其自身的独特性。医学数 据具有如下特点【1 】： 1 1 1 医学数据的隐私性 医学数据不可避免地涉及到患者的一些隐私信息，当这些隐私信息使患者 在同常生活中遭遇到不可预料的侵扰时，就产生了隐私性问题】。隐私性 ( p r i v a c y ) 不同于安全性( s e c u r i t y ) 和机密性( c o n f i d e n t i a l i t y ) ，当未被授权的 个人或机构设法取得这些隐私信息时，就产生了安全性问题；当拥有隐私信息 的研究人员与未经授权的个人或机构共享这些患者信息时，就暴露出了机密性 问题。医学数据挖掘者有义务和职责在保护患者隐私的基础上进行科学研究， 并且确保这些医学数据的安全性和机密性。 1 1 2 医学数据的多样性 第1 章绪论 由于医学数据是从医学影像、实验数据以及医生与病人的交流中获得的， 所以原始的医学数据具有多种形式。医学数据包括影像( 如s p e c t ) 、信号( 如 e c g ) 、纯数据( 如体征参数、化验结果) 、文本( 如病人的身份记录、症状描 述、检测和诊断结果的文字表述) 等。医学数据的多样性是它区别于其它领域 数据的最显著特征。 1 1 3 医学数据的不完整性 医学数据的搜集和处理过程经常相互脱节，搜集是以治愈患者为直接目的， 而处理是以寻找某种疾病的一般规律为目的，因此搜集的信息可能无法涵盖研 究需要的所有信息。此外，人为因素也可能导致数据记录的偏差和残缺，许多 医学数据的表达、记录本身也具有不确定和模糊性。病例和病案的有限性使医 学数据库不可能对任何一种疾病信息都能全面地反映。 1 1 。4 医学数据的冗余性 医学数据库是一个庞大的数据资源，每天都会有大量的记录存储到数据库 中，其中可能会包含重复的、无关紧要的、甚至是相互矛盾的记录。例如，对 同一疾病，病人所表现的症状、化验结果和治疗措施都可能相同。 此外，医学数据还具有时问性特征，医学检测的信号如e c g 、影像s p e c t 都具有较强的时效性。 1 2 医学数据挖掘的过程 医学数据的特点使得医学数据挖掘与常规的数据挖掘之间存在着差异，但 医学数据挖掘仍遵循一般的知识发现过程，可按以下六个步骤进行f 4 j ： 1 、理解应用领域。这阶段主要包括确定医学研究的问题和目标，熟悉当 前解决此类问题的主流方法，理解相应的医学领域知识，确定医学数据挖掘的 目标和结论的评估标准。 2 、理解数据。这个过程要求初步确定数据挖掘需要的数据属性，并从原始 数据库中小规模采样进行初步挖掘试验，将试验结果与上一一步骤所确定的挖掘 目标进行对照比较，必要时更新数据属性。 第1 章绪论 3 、准备数据。这是决定整个医学数据挖掘结论正确与否的关键性步骤。由 于医学数据的冗余性特征，我们需要在重要性和相关性检验的基础上采样以消 减数据；又由于医学数据的多样性，我们必须针对各种类型的数据采取相应的 数据预处理方法，这方面的内容在第3 章将有详细的讨论。通过这个步骤的数 据准备，将原始数据转换为特定数据挖掘方法所需要的数据形式。 4 、数据挖掘。这是医学知识发现过程中的另一个关键性步骤。这一步骤包 括建模技术的选择，训练与检验程序的确定，模型的建立与评估。实现数据挖 掘的方法包括粗糙集理论、人工神经网络、进化计算、决策树等，在1 4 节将有 详的介绍。数据挖掘的精确度在很大程度上取决于挖掘方法与研究目标的匹配 程度。 5 、评估所得到的知识。对医学数据挖掘的结论进行医学解释，并与最初的 研究目标相比较。追溯整个数据挖掘过程中可能存在的错误的步骤，并且寻找 其解决的方法。通过使用各种挖掘方法，选择最佳的算法，得到最有效的模型。 6 、应用所发现的知识。在应用所得知识的过程中，要有计划性地实施和控 制，发现和解决实施过程中出现的问题，并对应用情况进行阶段性总结，指导 今后的实际应用。 1 3 医学数据挖掘的关键技术 医学数据库是一个复杂数据库，包括电子病历、医学影像、病理参数、化 验结果等，而目前数据挖掘技术主要应用于以结构化数据为主的关系数据库、 事务数据库和数据仓库，对复杂类型数据的挖掘尚处在起步阶段。数据预处理 中隐私信息的匿名化与标识转换，文本数据和影像数据的挖掘等关键技术直接 影响医学数据挖掘的质量。 1 3 1 隐私信息的匿名化与标识转换 数据预处理主要包括数据清沈、数据集成、数据转换和数据消减，是数掘 挖掘过程中的一个重要过程，通常要花费一个完整的数据挖掘过程的6 0 左右 的时间，而挖掘工作仅占整个过程的1 0 左右【5 1 。由于医学数据涉及到患者的 隐私信息，除了需要经过一般的数据预处理以外，还需要进行特别的数据处理， 第1 章绪论 即对患者记录进行匿名化( a n o n y m i z a t i o n ) 和标识转换( d e i d c n t i f i c a t i o n ) ，从 而分离患者与患者记录之间的关联关系1 3 j 。 匿名化是指从记录中去除患者的标识，比如患者的姓名、住址、医院记录 号等，或者用错误的标识代替正确的标识。匿名化之后，研究人员不可能通过 观察记录了解到有关患者的任何信息。标识转换与匿名化有一些细微的差别， 变换后的标识可能仍然隐含着患者的真实信息，但是这些隐含的真实信息只有 那些经过授权的研究人员才能获得，而未经授权的人员根本无法通过隐含的线 索获得患者的任何真实信息。 1 3 2 医学文本数据挖掘 医学文本信息中，医学专家对影像、信号或者其它临床数据的解释是非标准 化的，难以赢接进行数据挖掘，因此需要对文本数据进行标准化处理。目前通 过计算机对医学文本数据进行标准化转换已经起到了一定的成效【“”。机器转换 主要包括三个步骤：分析源语句，转换，产生目标语句。转换的一个难点是源 语句不是唯一的，因此需要无止尽地收集各种形式的源语句，目前的机器转换 只能处理小于1 0 个单词的语句。 x m l ( e x t e n s i b l e m a r k u pl 丑n g l l a g c ) 是一种结构化的语言，提供了文本数据 标准化的另一途径。x m l 不仅能创建包含结构化数据的文本，同时也可以共享 和处理数据。x m l 是数据挖掘和知识发现的关键技术，主要体现在【2 l ：使各种 数据挖掘工具和数据库之间的通信标准化；建立标准数据仓库，实现基于不同 软件平台的各种数据挖掘工具之间的数据共享；实施数据挖掘工具之间的通信 协议：实现数据挖掘和知识发现的不同步骤之间的数据整合和数据共享。 1 3 3 医学影像数据挖掘 当前医学影像数据主要来自一些成像仪器( 如b 超、c t 等) ，它们已被越 来越多的医学专家视为一种可靠的辅助诊断手段，因此，开发有效的影像数据 挖掘工具也成为医学数据挖掘过程中的关键技术之，这不仅仅与纯数字数据 的挖掘方法不同，而且实现更加困难。医学影像数据挖掘主要包括去除或降 低影像噪音的影响，提高目标影像质量或对目标组织进行边缘提取；对目标组 织进行概念描述，并概括这类对象的有关特征，从而获得或验证有关参数的动 第1 章绪论 态范围；医学影像数据的管理与检索。目前，对s p e c t 影像的数据挖掘已取得 了突破性进展【1 0 l 。 此外，研究快速的、鲁棒的挖掘算法，确保挖掘所得知识的准确性和可靠性， 都是医学数据挖掘的关键所在。 1 4 医学数据挖掘的智能化方法 分类和预测是两种数据分析形式，可以用于描述重要数据类的模型或预测 未来的数据趋势。对医学数据库进行数据挖掘和知识发现的主要目的是预测疾 病和对疾病进行分类，常用的智能化方法有粗糙集理论、人工神经网络、决策 树和进化计算等。 1 4 1 粗糙集理论 粗糙集理论【1 l l 是一种用于处理不确定性和含糊性知识的软计算方法，其基 本思想是在保持分类能力不变的前提下，通过知识约简，导出分类规则，并从 中发现隐含的知识，揭示潜在的规律。在医学数据挖掘中，基于粗糙集理论的 规则产生模型可以自动发现临床数据库中的正例和反例知识1 1 2 l ；基于粗糙集理 论的自主判别算法可以诊断肺部肿瘤是良性还是恶性的【1 3 】。 1 4 2 人工神经网络 人工神经网络是近年来颇受关注的一种算法，它模拟人脑神经元结构，通 过训练和学习得到非线性预测模型，可以完成分类、聚类、关联规则挖掘等多 种数据挖掘任务，为解决复杂的问题提供了一种相对有效且简单的方法【1 4 1 。人 工神经网络具有很强的自组织性、鲁棒性和容错性，在医学数据挖掘中得到广 泛的应用。目前，采用b a y e s i a n 神经网络结构，能够找出服用抗精神药物与心 肌炎和心肌病发作的关系l ”】；运用组合神经网络可对危及生命的心律失常进行 归类1 1 6 1 1 还可以通过神经网络来动态检测病人的麻醉深度和控制麻醉药物的用 量【1 7 】。 1 4 3 决策树 第1 章绪论 决策树是一种用树枝状展现数据受各变量的影响情况的分析预测模型，根 据对目标变量产生效应的不同而制定分类规则，它是建立在信息论基础之上对 数据进行分类的一种方法【1 8 】。它首先通过一批已知的训练数据建立一棵决策树， 然后采用建好的决策树对数据进行预测。决策树的建立过程就是数据规则的生 成过程，因此这种方法实现了数据规则的可视化，其输出结果容易理解，精确 度较好，效率较高，因而较常用。决策树在自动诊断心脏s p e c t 影像的课题f 1 0 l 和诊断心肌灌注的知识发现系统【4 l 中有相应的应用。 1 4 4 进化算法 进化算法是由生物进化规律而演化出的一种搜索和优化的计算方法，包括 遗传算法、进化规划、进化策略和遗传编型1 9 】。进化算法从任一初始的群体出 发，通过随机选择、交叉和变异等过程，使群体进化到搜索空间中越来越好的 区域。在医学数据挖掘中，采用遗传编程可对胸痛症状疾病进行诊断【2 0 】，运用 进化算法可对脊柱的侧凸进行分类【2 1 ) 。 此外，模糊系统、支持向量机等其它智能化方法在医学数据挖掘中也得到 了相应的应用。在实际应用中，可对这些方法进行适当的修改、扩充和优化， 从而能在各种医学数据库中进行分类和预测。 1 5 本文的工作内容与结构安排 本文首先对医学数据挖掘进行了全面的阐述，然后着重研究了医学数据挖 掘的智能化方法之一粗糙集理论。本文的结构安排如下： 第1 章绪论 根据医学数据的特点，全面阐述了医学数据挖掘的一般过程、关键技术和智 能化方法。介绍了本文的工作内容和结构安排。 第2 章粗糙集的基本理论 对粗糙集理论的提出背景、研究现状和应用前景作了较为全面的评述，介 绍了粗糙集的基本概念及其思想内涵。 第3 章数据预处理 介绍了数据预处理的相关概念，归纳了缺失信息的处理方法，着重研究了 第1 章绪论 连续属性的离散化算法，初步探讨了概念泛化的基本思想。 第4 章粗糙集理论中的知识约简 知识约简包括属性约简和值约简，本章归纳总结了常见的属性约简算法， 提出了基于二进制可辨识矩阵的属性约简算法，并通过实验说明算法的有效性。 第5 章粗糙集理论中的规则提取 本章讨论了粗糙集理论中的规则获取的相关概念和方法，并通过示例分析 说明概率规则在医学数据挖掘中的应用。 第6 章结束语 对迄今所做工作的总结以及以后工作的展望。 第2 章粗糙集的基本理论 第2 章粗糙集的基本理论 现实世界中，人类的主观认识与客观实际之间存在着差异，事务发生的随 机性、人类知识的不完全、不可靠、不精确和不一致以及自然语言中存在的模 糊性和歧义性都反映了这种差异，都会带来不确定性。不确定性造成了具有相 同描述信息的对象可能属于不同概念，因此解决不确定性问题受到研究者的广 泛重视。 2 1 粗糙集理论的提出背景 在人工智能领域有许多处理不确定性问题的方法，数据挖掘中应用最广泛 的是人工神经网络、模糊集、证据理论以及粗糙集理论。人工神经网络是一种 模拟人的思维的方法，缺点在于不能将输入信息空间维数简化，当输入信息空 间维数较大时，网络不仅结构复杂，而且训练时间也很长【2 2 2 6 1 。模糊集主要利 用隶属度函数表达不确定信息，而定义隶属度函数带有一定的主观性1 2 7 - 3 2 1 。证 据理论使用信任函数或似然函数作为处理不确定性的工具，而信任( 似然) 值 需要专家给出，同样也具有主观因素【3 3 】。 2 0 世纪8 0 年代初，波兰数学家z p a w l a k 教授针对gf r e g e 的边界线区域 思想提出了粗糙集理论【1 1 j ，它是一种研究不完整、不确定知识和数据的表达、 学习、归纳的理论方法，其基本思想是在保持分类能力不变的前提下，通过知 识约简，导出分类规则。粗糙集理论把无法确定的个体归属于边界线区域，而 这边界域被定义为上近似集与下近似集之差集。上近似集和下近似集都可以通 过等价关系给出确定的数学描述，所以含糊元素的数目可以在不需要给出额外 信息的情况下被客观地计算出来。 在处理不精确性问题时，粗糙集理论的优势在于：不需给出额外信息，如 概率统计中的先验概率和模糊集中的隶属度；可以去掉冗余输入信息，简化输 入信息的表达空间；算法简单，易于操作。粗糙集理论存在的主要问题是抗干 扰能力差，如果条件属性受噪声干扰，将会直接影响分类质量。 2 2 粗糙集的基本概念 第2 章粗糙集的基本理论 粗糙集理论的提出至今己2 0 多年，无论是在理论体系、计算模型的建立还 是在应用系统的研制与开发上，都已取得了很多成果。本节主要介绍粗糙集理 论的基本概念。 2 , 2 1 知识与知识库 在信息系统中，人们首先碰到的就是对知识的理解与表达。知识是基于对 对象分类的能力。我们将感兴趣的非空有限对象集称为论域，记作u 。 定义2 1 对于论域u 中的一簇子集讧，x ：，x ，若满足 i ) v f - 1 , 2 ，n ，x j ，妒； i i ) u j f u ； i - i i i i ) 、t - j ，x i n x ，一币n 则称忸，z ：，x 。 为u 的一个划分。 定义2 2 设r 是论域u 上的二元关系，如果对y x e u 有( 工，z ) r ，则称r 是u 上的自反关系。 定义2 3 设r 是论域u 上的二元关系，如果对v x ，y r = u ，有b ，y ) r ，也 必有( y ，x ) e n ，则称r 是u 上的对称关系。 定义2 4 设r 是论域u 上的二元关系，如果对比，y ，z e u ，有b ，y ) r 和 ( _ ，r ，z ) r ，也必有g ，z ) e r ，则称r 是【，上的传递关系。 定义2 5 设r 是论域u 上的二元关系，如果它是自反的、对称的和传递的， 则它是u 上的等价关系。 定义2 6 设论域【，一缸，叠， ，r 是u 上的一个等价关系，与u 中的 一个元素x 相关的所有元素的集合称之为x 的一个等价类，记成【z k 。形式地， x l 。一 yi g ，y ) r j 。 定理2 1 设r 是论域u 上的一个等价关系，那么r 的等价类形成u 的一个 划分。 设等价关系r 的等价类在论域u 上形成的一个划分为忸，工：，x 。 ，那么 对于任意子集z ；g = 1 , 2 ，n ) 都可称之为u 中的一个概念或范畴，用d e s 杠， 表 示概念x ；的描述。空集也是一个特殊的概念。论域u 中的任意概念簇称为关于 第2 章粗糙集的基本理论 u 的抽象知识，简称知识，记为u r 。 论域c ，上的一簇划分称为关于u 的知识库。一个知识库就是一个关系系统 置一妙，只 ，其中u 是论域，霆是矽上的一个等价关系簇。若p r 且p 一簪， 则p 中全部等价关系的交集也是一个等价关系，称为p 上的不可分辨关系，记 i n d p ) ： 口】。( p 1 一n b 】， ( 2 1 ) r 这样u 砌d ( p ) 定义为与等价关系p 的簇相关的知识，称为p 基本知识。为 简便起见，将u i n d ( p ) 记为u p ，p 基本知识记为p 。f 耐( p ) 的等价类称为知 识p 的基本概念或基本范畴。特别地，如果q r ，则q 称为q 初等知识，且q 的等价类称为知识q 的初等范畴。 设置。移，p 和置t 移，q 是两个知识库，若拥d p ) 一拥d ( q ) ，则称知识库置 和k ( p 和q ) 是等价的。知识库茁和茁等价意味着髟和具有相同的基本类， 因两它们具有相同的表达能力。 2 2 2 粗糙纂与近似 粗糙集理论利用集合的上、下近似概念描述不确定性，即利用不可分辨关 系导出的划分来描述论域中的新子集。 定义2 7 设知识库k - 移，异) ，盖u ，b r ，则定义x 的b 下近似垦伍) 和口上近似i 伍) 分别为： a ( x ) 一备( 厂l x l 。x - u 影【，b i r c _ x 致x ) 一仁u i x l 。n 石一 一u 影u ，曰f y n x ，t 妒 ( 2 。2 ) ( 2 3 ) 显然，所有包含于x 的初等集台的并构成照口) ，所有与j 的交为非空的初 等集合的并构成丑啦) 。换言之，垦协) 中的元素一定属于z ，丽否江) 中的元素 可能属于x 。 定义2 ，8 设知识库k t 妙，r ，并u ，b r ，则 z 的b 正域：p o s j ) t 里伍) ： 石的占负域：n e g 日( x ) = u b z ) ： x 的曰边界域：肼。噼) ；b 伍) 盛x ) 。 显然，正域内的对象一定属于z ，负域内的对象定不属于工，边界域内 的对象可能属于石。图2 ，1 描述了莘h 糙集概念模型。 0 第2 章粗糙集的基本理论 图2 1 粗糙集概念示意图 定理2 2 ( 1 ) 当且仅当旦伍) = 否伍) ，称集合x 是口的可定义集 ( 2 ) 当且仅当曼似) 一百伍) ，称集合工是占的粗糙集。 2 2 2 1 非精确性的数字特征 集合( 范畴) 的不确定性是由于边界域的存在而引起的。集合的边界域越 大，其精确性越低。为更准确地表达这一点，我们引入精度的概念，且定义为： d 。伍) = c 4 r d ( r ( x ) ) c a r d 伍( x ) ) ( 2 4 ) 其中，c a r d ( s ) 表示集合s 的基数，且盖- 毋。 精度如伍) 用来反映我们对集合x 表示的知识了解的完全程度。显然，对 于每一个r 和x u ，有0 s d r 伍) s 1 。当如伍) 一1 时，集合j 是全部尺可定 义的；当o 冀 ( 2 9 ) 即如果将集合x 中的元素分到集合y 中，则做出分类错误的比率为 c x ，y ) x 1 0 0 ，真正错分类的元素数目为c 伍，r ) l x f ，称c 伍，y ) x 悟l 为绝对分 类误差。 令o s 口c 0 5 ，多数包含关系定义为 卢、 y d _ x c x ，y ) 芦 ( 2 1 0 ) “多数”要求隐含着z 与】，中的公共元素的数目大于x 中元素的5 0 。 定义2 9 设知识库k 。 u ，r ，x c _ u ，u r 一忙，e ：，e ，) ，则 ( 1 ) 下近似定义为星，伍) t 戗旧u r c ( e 。，并) s 卢j ； ( 2 ) 上近似定义为页# 伍) t 恼慨u r c 幢，x ) s 1 - 声) ： ( 3 ) 卢正域定义为p o s ( x ) 一旦p 伍) ； ( 4 ) 卢负域定义为眦g 凡( x ) - 恼i i e i u ，r c 幢；，工) z 1 - p ； ( 5 ) 卢边界域定义为肼如伍) ；仁。江。( ，r 芦c c 忙。，石) c 1 一卢 。 同样，我们可以参照经典粗糙集模型给出口近似的一些基本性质，属性的 近似依赖性，近似约简等。 2 2 5 基于粗糙集理论的知识获取 近年来，粗糙集理论对模糊和不完全知识的处理比较出色，成为数据库知 识获取研究中的有力工具。粗糙集理论可支持知谚 获取的多个步骤，如数据预 处理、知识约简和规则提取等。本节主要介绍基于粗糙集的知识获取的一些基 本概念，为以后章节讨论具体的知识获取问题奠定基础。 2 2 1 5 1 信息表与不可分辨关系 第2 章粗糙集的基本理论 粗糙集理论利用信息表来描述论域中的对象，关于这些对象的知识是通过 对蒙的属性和属性值来描述的。信息表中每一行描述一个对象，每一列描述对 象的一个属性，行与列的交点是对象的属性值。 定义2 1 0称四元组s c u ，a ，v ，f 为一个信息表，其中 u 。，工：，) 为论域，a 一仁。，n ：，口) 为关于u 的非空有限属性集， y - u k ( 匕表示属性口的值域) ；映射f ：u x a v 称为信息函数，表示对 v x e u ，4 e a ，有f ( x ，a ) e v , 。 具有相同信息所标识的对象是不可分辨的，不可分辨关系构成了粗糙集理 论的数学基础。 定义2 1 1 设信息表i st cu ，a ，v ，f ) ，a 的任何一个属性子集b 确定一个 ，上的不可分辨关系i n d ( b ) ，即 z d 陋卜妊，y 】0 ，y ) u 2 ，v ae b ( i ( x ，口) 一f ( y ，口) ) ( 2 1 1 ) 显然， i n d 佃) 是等价关系，也可表示为： i n d ( b ) 一n 小d ( 每 ) ( 2 1 2 ) 0 日 不可分辨关系上d 恤) 的所有等价类的集合记为u b ，含有元素x 的等价类 记为o b ) 或k b ，同一等价类中的元素是不可分辨的。 等价类的计算是租糙集运算的基础。在信息系统髂一c u ，a ，v ，f ，中，对 于任意的属性集合口互a ，根据不可分辨关系将论域中的对象仁。，矗 分 为七个等价类。 等价类的计算算法： 输入：信息表b 1 1 ) ，则可 将此决策表分解成m 个不同的单一决策表d i - ， 其中 u 。= p o s c ( d j ，u 2 一 u ，、b n c 伍) 。 x e i 瑚n t c 、 由定理2 5 可见，若决策表是不完全相容的，即条件属性和决策属性的依赖 度大于0 且不等于1 ，则可将原决策表唯一地分解为两个子决策表，其中一个子 决策表是完全相容的，而另一个子决策表是完全不相容的。 2 2 5 3 属性重要性 第2 章粗糙集的基本理论 众所周知，用症状描述病人的情况时，有些症状具有更重要的意义。为了 找出某些属性或属性集的重要性，需要从决策表中去掉这些属性，再来考察没 有该属性后分类会怎样变化。若去掉该属性会相应地改变分类，则说明该属性 的重要性高；反之说明该属性的重要性低。粗糙集理论中，我们可以对属性的 重要性进行度量，这个度量是根据论域中的样例来得到的，不依赖于人的先验 知识。 定义2 1 5 设f 是属性集d 导出的划分，属性子集丑在属性集b 中的重要 性( b b ，如果属性集口是默认的，如口为条件属性全集，则可简称为属性子 集口的重要性) 定义为 陋) 一r b 。( ，) ( 2 1 3 ) 这表示当我们从属性集口中去掉属性子集对f 近似分类的质量的影响。 属性的重要性还可以有其他度量方法，如属性子集f 的重要性也可定义为 p o s b - b ( e ) e o s 。( f ) ( 2 1 4 ) 其中，p o s 。忙) 一up o s 。伍) 。 属性的重要性也是以后章节中讨论知识约简问题的一个关键性基础概念。 2 2 5 4 可辨识矩阵 可辨识矩阵也称分明矩阵，是由s k o w r o n 教授提出的一种表示知识的方法。 这种表示有许多有利条件，特别是可以解释和计算核与约简。 定义2 1 6 令信息表系统为腰t c u ，a ，v ，u - k ，工：， 是论域， a - 扛，4 ：，a 。 是属性集合。a i b ，) 是对象x i 在属性a 。上的取值，则信息表系 统的可辨识矩阵定义为： m ( i s ) - b l 。 其中，c 口- * 。k 一n n 。b ，) 一n 。b ，) ，f ，j ：1 ，2 ，行，玎。c a ，d ( u ) 对于决策表系统，我们也可以定义相应的可辨识矩阵。 定义2 1 7 令决策表系统为d r = c u ，c u d ，y ，u = 仁。，戈：，_ ) 是论 域，c 。 口，口：，n ， 和d ；臼 分别是条件属性集和决策属性集。b ，) 是对象 x ，在属性4 ，上的取值，则决策表系统的可辨识矩阵定义为： 第2 章粗糙集的基本理论 m ( d r ) z b l 。 其中，c 。一 暮。 b。)，。仁，)ddb(x。,)。=ddblxi，)lakeca, ) ，f ，j 一1 2 ，n ，n 一r d 眇) 其中，。“。 暑。b 。) ，。仁，8 d b 。) 。d b ，) ，j _ 1 2 ，肌”i r d 眇) 显然，可辨识矩阵是一个依主对角线对称的矩阵，在考虑可辨识矩阵的时 候，只需要考虑其上三角( 或下三角) 部分就可以了。 由可辨识矩阵的定义可知，在决策表系统中，当两个对象的决策属性取值 相同时，它们所对应的可辨识矩阵元素的取值为0 ；当两个对象的决策属性不同 且可以通过某些条件属性的取值不同加以区分时，它们所对应的可辨识矩阵元 素的取值为这两个对象属性值不同的条件属性集合，即可以区分这两个对象的 条件属性集合；当两个对象发生冲突时，即所有的条件属性取值相同而决策属 性的取值不同时，则它们所对应的可辨识矩阵中的元素为空集。显然，可辨识 矩阵元素中是否包含空集元素可以作为决策表系统中是否包含不一致( 冲突) 信息的依据。 2 3 粗糙集理论的研究现状 粗糙集理论自问世以来，经过二十多年的研究与发展，在理论和实际应用 上都取得了长足的进展，特别是由于2 0 世纪8 0 年代末和9 0 年代初在知识发现 等领域得到了成功的应用而受到国际上广泛关注。对粗糙集理论的研究主要集 中在以下几个方面： 2 3 1 粗糙集的数学性质 对粗糙集数学性质【1 1 ，3 4 ，3 5 】的研究，主要包括研究集合和分类近似的性质、决 策表性质、代数结构、粗糙集代数、粗糙集逻辑、粗糙集拓扑结构及其收敛性 问题，它们是粗糙集理论形成和发展的基础。 2 3 2 粗糙集模型的拓广 早期的经典粗糙集模型没有考虑与不确定分类问题有关的概率分布信息。 概率粗糙集模型【3 6 l 通过条件概率来定义概念的上下近似。可变精度粗糙集模型 第2 章粗糙集的基本理论 【3 7 】通过引入两个集合的相等误分类度c 暇，y ) ，把集合的普通包含x y 放宽为 多数包含关系：x 。y c ( x ，y ) s 卢。在允许的分类误差卢下对概念的上近似 和下近似重新定义。相容关系模型【3 8 捌针对经典粗糙集中等价关系条件太强的缺 陷，提出了用相容关系代替传统的等价关系的相容关系模型。 2 3 3 连续属性的离散化 粗糙集理论的数学基础是集合论，其只能处理离散型数据( 如整型、字符 串型、枚举型等) 。实际应用中，必须先对连续属性进行离散化处理。连续属性 的离散化问题在粗糙集理论分析的其他环节之前，故它属于粗糙集理论中的预 处理问题之一。连续属性的离散化使得粗糙集理论对离散和连续的属性都能处 理，扩大了粗糙集理论的应用范围。 2 3 。4 核与约简的求取 粗糙集理论中的两个核心概念是核和约简，它们对知识约简起着重要作用。 核是最重要的属性集合，寻找核的意义在于，从核开始求耿约简，会大大减少 求得约简的计算量。约简往往不止一个，而求出所有的属性约简是n p 难题f 枷， 故常常采用启发方法找出一个最优或次优约简。 2 4 粗糙集理论的应用前景 近年来，粗糙集理论在机器学习、知识发现、决策支持与分析、智能控制、 模式识别等学科领域获得了成功应用并得到了交叉发展。粗糙集理论在许多应 用领域也得到了成功应用，如在金融与股票市场分析、医疗诊断中的病历综合、 银行数据分析、空间行走的生理分析与发现控制规则、全球气候分析、药物的 化学结构分柝等。 粗糙集理论自提出以来一直得到模糊数学创始人z a d e h 的重视，并给予很 高的评价，把它列入他新提倡的软计算的基础理论之一。由此可见，粗糙集理 论及其广泛应用越来越受到重视。 粗糙集理论和其它软计算方法的结合，能够提高数据1 ：采能力，这是由现 实世界的复杂性和处理方法有限能力的矛盾决定的。其中粗糙集理论与神经网 第2 章粗糙集的基本理论 络的结合是研究的热点。粗糙集理论对噪声敏感且泛化能力弱，可以用神经网 络的优点( 自组织、容错和推广能力) 来弥补：神经网络不能确定重要的属性 组合、结构构造缺乏通用的方法且推理过程不透明等都可以用粗糙集理论进行 辅助分析。有关粗糙集理论与遗传算法、模糊集理论等软计算方法的结合也屡 见不鲜，粗糙集理论与其它软计算方法的集成是数据开采的一种趋势。 第3 章数据预处理 第3 章数据预处理 知识获取是指从某个领域的历史数据中获取有用的、未知的知识，由于在 收集历史数据时并没有考虑数据挖掘任务或者考虑甚少，且历史数据有时存储 在多个数据库中，从这些数据库中收集而成的样本数据集并不一定适合直接用 于数据挖掘，通常需要经过预处理后才能使用。 数据预处理根据样本数据集中可能存在的问题以及挖掘算法对样本数据集 的要求，需要完成以下任务： 数据校验。样本数据集中常常存在一些不确定内容，主要表现为字段值标 记错误、有特殊语义的数据值和空值，数据挖掘专家必须配合领域专家对这些 内容进行确认。 离散化与泛化。由于粗糙集理论只能研究离散型属性表示的对象，对于值 域是连续的或很大的属性需做相应的处理。数值型属性的取值常在某个范围内 连续变化，需要对其进行离散化分析：一些名词型属性虽然是离散的，但值域 很大，也不适合挖掘算法的应用，需要对其进行泛化分析。 数据转换。不同的数据挖掘方法对数据输入有不同的要求，数据变换就是 对数据进行编码，使其成为挖掘方法所要求的格式。 3 1 不完备信息的处理 若信息系统中全部对象的所有属性值都是已知的，则该系统是完备的，否 则是不完备的。在很多情况下，我们得到的待处理的信息表并不完备，信息表 中的某些属性值被遗漏掉了，并且无从知道其原始值。由于基于不可辨识关系 的经典粗糙集方法要求信息表是完备的，因此需要使信息系统完备化。目前， 主要通过以下几种途径来对不完备信息进行处理。 3 1 1 删除存在遗漏属性值的对象 虽然将存在遗漏属性值的对象删除不是严格意义上的数据补齐，然而在信 息表数据量巨大并且有遗漏属性值的对象的数目远远小于信息表所包含的