基于粗糙集理论疾病初步诊断决策支持研究

《基于粗糙集理论疾病初步诊断决策支持研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

安徽工业大学硕士学位论文基于粗糙集理论疾病初步诊断决策支持研究论文题目：Basedonroughsettheoryofdiseasetheinitialdiagnosisdecisionsupportresearch作者：吴俊学院：研究生学院指导教师：胡宏智单位：计算机学院论文提交日期：2013年5月30日学位授予单位：安徽工业大学安徽马鞍山243002 摘要摘要近年来，计算机科学与信息技术在医学领域得到了飞速的发展，随着国家对医疗卫生事业信息化的不断投入，已使其成为临床、科研、医学教育、医院管理的重要组成部分。计算机硬件的改进、功能的提升、应用医疗软件的开发以及有线无线网络系统的建设，使计算机成为医生、护士和医院管理人员一种不可缺少的工具。病人临床资料不断在计算机内存储，使我们积累了大量的数据资料，各种检测，化验数据堆积如山。如何从这些庞大的数据中挖掘出“金子”，是我们计算机应用专业跨学科应用研究的一个十分具有意义和挑战性的研究方向。本文主要应用了数据挖掘领域中的粗糙集理论方法，对病例数据中冗余的病症属性进行删减，得到简化的疾病诊断规则，为“疾病诊断”提供决策支持。论文中，我们对医学数据进行数据预处理、针对具体医学应用，设计了新的基于条件信息熵的属性约简算法，该算法放弃了求属性的最小约简，而是求属性的所有约简，得到更适合医学应用的规则。并且针对目前属性约简算法实现上存在的实用性、快速、有效性的缺点和不足,提出了一种基于数据库查询语句计算条件信息熵实现属性约简的方法，并结合实例说明实现方法的实现过程。将粗糙集的属性约简算法融入到数据库系统当中去，发挥数据库系统的优点，并发挥数据库查询语言操作大规模数据功能强大的优点。最后,建立联合诊断规则表，参与多种疾病的联合初步诊断，能帮助医生在后续确诊过程中快速确诊疾病，并能有效防止医生错诊漏诊。关键字：疾病诊断；粗糙集；属性约简；数据挖掘I AbstractAbstractInrecentyears,computerscienceandinformationtechnologyinthemedicalfieldhasbeenrapiddevelopment,ascountriescontinuetoinvestinthecauseofhealthinformatization,ithasbecomeanimportantpartofclinicalresearch,medicaledu-cation,hospitalmanagement.Computerhardwareimprovements,improvedfunct-ionality,theapplicationmedicalsoftwaredevelopmentaswellastheconstructionofthewiredandwirelessnetworksystems,causingacomputertobecomeanindispensabletoolfordoctors,nursesandhospitaladministrators.Patientclinicaldatacontinuetobestoredinthecomputer,wehaveaccumulatedalotofdata,varioustesting,laboratorydatapileduplikeamountain.Howthesemassivedatamining"gold"isaverymeaningfulandchallengingresearchdirectionsofourcomputerapplicationprofessionalinterdisciplinaryappliedresearch.Thisthesisismainlyappliedinthefieldofdataminingmethodsofroughsettheory,Deletionofthethecasedataredundancyillnessattributessimplifieddiagn-osticrules,andprovidedecisionsupportforthediagnosis.Inthethesis,wehavedatapre-processingofmedicaldata,designedforspecificmedicalapplications,anewattri-butereductionalgorithmbasedonconditionalinformationentropy.Thealgorithmtogiveupthesmallestreductionandproperty,butseekingpropertyreductionrulestobemoresuitableformedicalapplications,Andforattributereductionalgorithmimplem-entationonpracticality,fast,theshortcomingsanddeficienciesofthevalidityofacalculatedbasedonthedatabasequeryconditioninformationentropyattributereductionmethods.withexamplestoillustratethealgorithmimplementationproc-ess.Roughsetattributereductionalgorithmintoadatabasesystemwhichplaytotheadvantagesofthedatabasesystemandplayadatabasequerylanguageoperatinglarge-scaledatapowerfuladvantages.Finally,thetheestablishmentofjointdiagnosticrulestable,involvedinavarietyofdiseasesjointpreliminarydiagnosis,beabletohelpdoctorsInthefollow-updiagnosedtheprocessoffastdiagnoseddiseases,andcaneffectivelypreventdoctorswrongdiagnosisandmisseddiagnosis.Keywords:diseasediagnosis;roughset;attributereduction;dataminingII 目录第一章绪论.........................................................11.1研究的背景及意义............................................11.2数据挖掘在医学领域中的研究现状概括..........................11.3粗糙集理论在医学中的应用现状................................21.4论文研究的主要工作及论文组织架构............................2第二章粗糙集理论基础..............................................32.1集合与集合运算..............................................42.2集合论中等价关系(不可区分关系)和等价类......................52.3粗糙集理论中的等价关系、等价类与划分.......................52.4粗糙集理论诞生的背景及发展历程..............................92.5粗糙集理论的理论特点及优势.................................102.6粗糙集理论的研究现状及其发展方向...........................112.7粗糙集理论概念和粗糙集定义.................................112.8属性依赖度与属性必要性.....................................132.9属性约简与核...............................................132.10决策表的属性约简与决策规则获取............................142.11本章小结..................................................15第三章粗糙集属性约简经典算法研究..................................163.1基于正域的属性约简算法.....................................163.2基于属性依赖度(重要度)的属性约简算法.......................183.3基于条件信息熵的属性约简算法...............................193.4基于差别矩阵的属性约简算法.................................223.5本章小结...................................................23第四章实际应用角度改进属性约简算法................................244.1能得到所有约简子集的条件信息熵属性约简改进算法.............244.2基于SQL语句计算条件信息熵的属性约简实现方法...............274.3本章小结...................................................32第五章粗糙集理论应用于疾病初诊决策支持研究........................335.1应用的整个流程概述.........................................345.2数据预处理.................................................355.3决策表约简.................................................385.4决策规则生成...............................................425.5生成联合诊断规则表.........................................445.6本章小结...................................................46第六章总结和展望..................................................47参考文献...........................................................48在学研究成果.......................................................51致谢...............................................................52III 第一章绪论第一章绪论1.1研究的背景及意义近年来，计算机科学与信息技术在医学领域得到了飞速的发展，随着国家对医疗卫生事业信息化的不断投入，已使其成为临床、科研、医学教育、医院管理的重要组成部分。计算机硬件的改进、功能的提升、应用医疗软件的开发以及有线无线网络系统的建设，使台式计算机、笔记本电脑、平板电脑等设备已成为医生、护士、卫生防御人员和医院管理人员一种不可缺少的工具。病人临床资料的不断在计算机内存储，使我们积累了大量的数据资料，各种检测，化验数据堆积如山。这些庞大的数据中到底有没有“金子”，这是毋庸置疑的，数据中肯定蕴含着有用的知识和规律。但这些“金子”如何挖掘出来，是我们科研人员关注的焦点。如何对医学数据进行有效的处理、分析、理解为疾病诊断、治疗、和预防提供帮助是目前广大医学、医药工作者十分关心的热点问题，也是我们计算机应用专业跨学科应用研究的一个十分具有意义和挑战性的研究方向，我们应该为之努力。本文主要的意义在于使用数据挖掘领域中的粗糙集理论方法，对病例数据中冗余的病症属性进行删减，得到简化的疾病诊断规则，为疾病诊断提供决策支持。论文中我们对医学数据进行数据预处理、病症属性约简、诊治规则的提取和约简，并建立联合诊断规则表，参与多种疾病的联合诊断，能够防止医生错诊漏诊，能够使疾病得到快速确诊，使医生的检查化验更具有针对性，可以为医院节省医疗资源，为病人减少就医成本和就医程序。1.2数据挖掘在医学领域中的研究现状概括近年来,数据挖掘技术在医学领域中的应用越来越广泛。在疾病诊断、治疗、器官移植、基因研究、图像分析、康复、药物开发等方面都获得了可喜的成果。在国外，南加州大学脊椎病医院利用InformationDiscovery进行数据挖掘，该技术已应用到肿瘤学、肝脏病理学、肝炎的生存几率预测、泌尿学、甲状腺病例诊断、风湿病学、皮肤病诊断、心脏病学、神经心理学、妇科学、产科学等医学[1]领域。Igorkononko等从医学诊断的角度阐述了统计或模式识别方法、符号[2]法则的归纳学习、人造神经网络3类机器学习算法在医学领域中的应用。MiroslavKubat等针对心电图、脑电图等医学推测信号的分析，提出使用决策树来初[3]始化神经网络，可以大大提高对测试样本的分类准确率。RobeitGroth对聚类[4]技术在患者术后康复问题分析的应用进行了研究等。在国内，第四军医大的陈[5]雪峰等利用数据库和数据挖掘技术建立的恶性血液病数据库分析系统，不仅可辅助医生做出初步诊断而且对数据具有强大挖掘和分析功能。富春枫等研究了机器学习的分类方法logitBoost在判别分析中的应用及其在医学领域中的应用[6,7]前景。刘建波等人对635例脑瘫患儿数据进行了数据挖掘研究，结果表明极高的危险因素有9项，其中新生儿因素、分娩因素和妊娠因素在脑瘫的发病中具[8]有非常重要的意义，该研究为脑瘫病因分类提供了一种新的方法，科学有效地理顺了脑瘫发病与相关病因的关系，较传统分类更明确清晰。罗森林等人将数据[9]挖掘技术应用于2型糖尿病病因的研究，他们选用C4.5算法自动建立决策分类树，该训练系统通过各项参数识别2型糖尿病患者因素间的相互关系并判断是否患病，得出血糖为5.85的分类临界值对糖尿病的高危因素分类具有极为重要1 基于粗糙集理论疾病初步诊断决策支持研究的意义。1.3粗糙集理论在医学中的应用现状粗糙集理论为数据挖掘和知识发现领域提供了一种有效而新颖的理论。它是一种能有效处理不精确、不一致、和不完备知识的数学工具。它可以从大量数据中分析、推理、挖掘隐含的知识和规律。近年来，粗糙集理论在各个领域的决策分析应用中取得了较大进展，同时它也被广泛的应用于医学各类数据分析。运用粗糙集理论可以根据以往的病例归纳出诊断规则，用来指导新病例的诊断。例如美国医学工作者应用粗糙集理论对大量病例进行分析，发现黑人妇女患乳腺癌的死亡率比白人妇女高。到目前为止，早产的预测在医学上还比较困难的，现在的人工预测方法的准确率只有17%~58%,而应用粗糙集理论则可将准确率提[10]高到68%~90%。秦中广等提出把粗糙集应用于中医类风湿症候诊断，并在类风[11]湿病的各症候应用于临床诊断。叶明全，姚应水应用粗糙集差别矩阵筛选医学[12]诊断因子得到疾病的主要诊断因子和次要诊断因子。粗糙集理论在医学决策分析中的应用大致可以分两类:（1）利用粗糙集理论的属性约简，与值约简及核属性，直接从决策表中获取规则；(2)将粗糙集理论与其他方法结合起来进行使用，利用粗糙集理论删除冗余属性，选择对决策重要的属性，并结合决策树、神经网络或支持向量机等方法，共同构成一个决策系统。1.4论文研究的主要工作及论文组织架构本文从六个方面阐述课题的研究内容，概述如下:第一章描述了课题研究的背景和意义、概述了国内外数据挖掘技术在医学领域的研究现状，以及粗糙集理论在医学应用中的现状，并对本文的主要研究内容和论文架构进行了说明。第二章主要介绍了粗糙集理论的基本知识，简述了集合与集合运算，集合和粗糙集中的等价关系与等价类，粗糙集的诞生背景、发展历程、理论特点、研究现状和发展前景等。对信息表达系统、信息表、决策表、粗糙集的上下近似集、属性约简与核、属性必要性和属性依赖度、决策规则约简等相关概念的定义等相关知识的简要回顾，以加深对粗糙集理论的理解,为后续章节奠定良好的理论基础。第三章主要研究了属性约简的四种经典属性约简算法，包括:基于正域的约简算法、基于属性依赖度（重要度）的约简算法、基于条件信息熵的属性约简算法和基于差别矩阵的属性约简算法，较深刻细致的描述了算法的基本思想，算法的步骤和流程示意图，并对算法的性能做了分析。通过本章的算法研究，加深了对粗糙集属性约简算法的认识和理解，为设计新算法，奠定了基础。第四章是本论文的两个重点工作之一，本章针对第五章要涉及的具体医学应用，设计了新的基于条件信息熵的属性约简算法，该算法放弃了求属性的最小约简，而是求属性的所有约简，得到更适合医学应用的规则。并且针对目前属性约简算法实现上存在的实用性、快速、有效性的缺点和不足,提出了一种新的基于SQL语句计算条件信息熵实现属性约简方法，并结合实例说明实现算法的实现过程。将粗糙集的属性约简算法融入到数据库系统当中去，发挥数据库系统的存取效率高、存储空间利用率高、适合大规模数据存储等优点，并发挥数据库查询语言操作大规模数据功能强大的优点。本文的第五章描述另外一个重点工作，遵循数据挖掘的基本过程，运用数据2 第一章绪论挖掘中的相关技术，详细的描述了数据从采集到预处理再到被挖掘的整个过程。从病历数据中提取病例数据，采集处理了两种疾病的数据，对两种疾病建立决策表，再用第四章提出的粗糙集属性约简改进算法，和实现算法对两种疾病进行病症属性约简，得到简化的决策表，并从决策表中得到疾病诊断的规则，并简化这些规则，运用这些规则建立联合诊断规则表，参与支持医生疾病初诊决策。并分析了应用的联合诊断规则表的优势和不足，并面对实际应用的可实现性，确定了联合诊断规则表的应用方向。第六章是对本课题的总结和展望。3 第二章粗糙集理论基础第二章粗糙集理论基础粗糙集(roughset，RS)理论亦称粗集理论是1982年波兰华沙理工大学的Pawlak教授提出的一种能有效地处理不一致、不精确、不完备知识的数学工具，它可以从大量数据中分析、推理、挖掘隐含的知识及规律，为智能信息处理提供了十分有效的方法。其主要思想就是在保持分类能力不变的前提下，通过知识约简，揭示数据中潜在的规律和隐含的信息，导出问题的决策和分类规则。粗糙集理论的主要优点是不需要数据的任何先验和附加知识，这有别于传统的随机、统计、概率、证据理论及模糊方法等。目前，粗糙集理论已被广泛应用于机器学习、过程控制、模式识别、故障及医学诊断、图像处理及关系数据库中的知识获取与决策分析等各种应用领域。其核心内容是属性重要度的度量和属性约简，应用属性重要度的度量可以分析数据中不同因素的重要程度并可以剔除数据中的冗余成分，保持关键的信息，从而为科学的管理和决策提供支持。粗糙集理论应用于医学诊断研究，可以利用疾病诊断的结果和临床症状表现数据之间的关系进行挖掘，确定疾病的主要症状和冗余症状，得到最小有效症状组合，提取简洁实用的诊断规则，从而为疾病诊断提供科学的决策依据。本章主要介绍粗糙集理论的相关知识，为后文各章节中将要涉及的概念和技术提供有力的理论保证，打下强有力的理论基础。2.1集合与集合运算集合论作为数学中最富创造性的伟大成果之一，是在19世纪末德国的康托(Cantor)创立起来的，但是，它的萌芽、孕育的历史却源远流长，至少可以追溯到两千年前。按现代数学观点，数学各分支的研究对象或者本身是带有某种特定结构的集合，如群、环、拓扑空间，或者是可以通过集合来定义的(如自然数、[13,14]实数、函数)。从这个意义上说，集合论可以说是整个现代数学的基础。2.1.1集合的理解集合没有精确的数学定义，集合可以理解为由离散个体构成的整体称为集合，称这些个体为集合的元素。常见的集合有N,Z,Q,R,C等分别表示自然数、整数、有理数、实数、负数集合。2.1.2集合表示法集合论为我们描述离散世界中的各种事件提供了十分有用的基础，集合的表[15]示通常有三种表示方法。(1)枚举法------通过罗列出集合中全体元素来表示集合。通常在集合所含元素少的情况下使用这种方法，实例：如表示性别的集合{男，女}。(2)谓词表示法------通过谓词概括集合元素的性质。实例：s={x|x是正整数，x<10000}2.1.3集合的运算通常一个集合用大写字母表示，而集合的元素多用小写字母表示。某个元素a属于集合A，或不属于集合A，分别表示为a∈A和a∉A。如果集合B中的元素全部都能在集合A中找到且集合A中元素个数不等于B集合中的元素个数，则集合B被称为集合A的子集，记作B⊆A或A⊇B。如果集合A和集合B中的元素是一样的，则集合A=集合B，集合有两个特殊的子集，空集Φ和全集U。集合的基本运算包括[15]交、并、补和差运算。4 基于粗糙集理论疾病初步诊断决策支持研究定义2.1集合并:A∪B={x|x∈A∨x∈B}。集合交:A∩B={x|∈A∧x|x∈B}。集合相对补:A-B={x|x∈A∧x∉B}。集合对称差：A⊕B=(A-B)∪(B-A)。集合绝对补：∼A=E-A。图2.1集合运算的文氏图表示2.2集合论中等价关系(不可区分关系)和等价类2.2.1二元关系设S是一个非空集合，R是关于S的元素的一个条件。如果对S中任意一个有序元素对(a，b)，我们总能确定a与b是否满足条件R，就称R是S的一个关系(relation).如果a与b满足条件R，则称a与b有关系R，记做aRb；否则称a与b无关[16]系R。关系R也成为二元关系。2.2.2等价关系和等价类集合论中的相关定义如下，定义2.2设R是集合A到集合A的二元关系，如果对∀a∈A有(a，a)∈R，则称R是A上的自反关系.定义2.3设R是集合A上的二元关系，如果对∀a，b∈A有(a，b)∈R，也必有(b，a)∈R，则称R是A上的对称关系。定义2.4设R是集合A上的二元关系，如果对∀a，b，c∈A，如果无论何时有(a，b)∈R和(b，c)∈R,必有(a，c)∈R，则称R是A上的传递关系。定义2.5设集合R是集合A上的二元关系，如果它是自反的、对称的、传递的，则它是集合A上的等价关系(不可区分关系)。定义2.6设R是A上的一个等价关系，与A中的一个元素a相关的所有元素的集合被称做a的一个等价类，记成[a]R。当仅考虑一个关系时，我们可略去下标，而简写成[a]。形式地，[a]R={s：(a，s)∈R}。2.3粗糙集理论中的等价关系、等价类与划分2.3.1知识的概念和知识库5 第二章粗糙集理论基础“知识”这个概念在不同范畴内有多种不同的含义。在粗糙集理论中，知识被认为是一种根据特征属性对现实和抽象对象进行分类的能力。人们的行为是基于分辨现实的或抽象的对象的能力。如远古时代，人类为了生存必须能分辨出什么可以食用，什么不可以食用。医生给病人看病，必须辨别出病人得的是哪一种疾病。这些根据事务的特征差别将其分门别类的能力均可以看做是一种知识。粗糙集理论认为知识与分类是密不可分的,知识是一种能根据属性集将对象集进行分类的能力。粗糙集理论拓展了经典的集合论，把分类的知识嵌入集合内，作为集合一部分。为了对知识能进行严密而有效的操作，粗糙集理论对知识进行了形式化定义。粗糙集理论认为知识必须以关于对象的分类能力为基础，这里对象是指感兴趣的所有东西，称之为论域、如状态、事务、过程、抽象概念等。知识被理解成关于论域的一族划分模式。设U是感兴趣的对象组成的集合，即论域。U上的一个子集族C={X1，X2，…，Xn}成为U的一个划分或分类，如果他满足：nXi⊆U,Xi≠Ф,对∀i≠j,i、j=1，2，…，n,且∪Xi=U，这样，一个U上i=1的分类族被定义U上的知识库，它构成了一个特定论域U的分类。知识库表达了[17,18]一个或一组智能机构的各种基本方式。为了便于数学推导，通常我们用等价关系代替分类，这里，这两个概念是完全可以相互替代的，而且关系更容易理解。这样，一个知识库就可以理解成为一个关系系统：K=(U,R)其中，U为非空论域，R是U上的一族等价关系。2.3.2知识表达系统在粗糙集理论中，知识表达系统可用信息表或决策表以关系数据库的形式表示出来，这样有利于将粗糙集理论中相关算法嵌入到数据库系统中去。定义2.7知识表达系统(信息系统)可以表示为四元有序组：S=(U，A，V，f)其中，U为非空的有限对象集合(称为论域)，U={x1,x2,…，xn},xi为对象(元组)；A为描述对象的非空有限属性集合，V为属性值集合，V=∪Va,Va是属性a的值域；f为一个函数，即U·A→V的一个信息函数，它指定U中的每个对象x在属性a下的值，即∀a∈A,xi∈U,f(xi,a)∈Va。知识表达系统也称为信息系[19,20]统，属性值表。定义2.8决策表定义：设S=(U,A,V,f)为一知识表达系统,A=C∪D,C∩D=Ф,C称为条件属性集,D为决策属性集，这种同时具有条件属性和决策属性的知识表达系统称为决策表。6 基于粗糙集理论疾病初步诊断决策支持研究表2.1关系表格式的决策表示意图条件属性集C决策属性集DVaAUc1…cKd1…dnx1v11…v1kd11…d1nx2v21…v2kd21…d2nxnvn1…vnkdn1…dnn决策表是一类特殊而重要的知识表达系统，它是粗糙集理论中重要的研究对象。决策表是以二维关系表形式来描述论域中的对象，关系表的每一行对应要研究的对象，每一列对象的属性，对象的信息是通过指定对象的各种属性值来表达的，决策表属性分为条件属性和决策属性，当对象满足某些条件(属性)，决策(属性)应当怎样进行。根据条件属性取值的不同，论域中的对象被划分到具有不同决策属性的决策类。决策表的决策属性通常只有一个。2.3.3不可区分关系(等价关系)在现实生活中，人类通常用一组属性来描述和认识现实世界所存在的各种对象，不可区分关系(不可辨别关系)就是由这些对象相应的属性值定义的。如果两个对象在某组属性上的属性值相等，即具有相同的描述，就认为他们是不可区[21,22,23]分的，它们的关系就是不可区分关系。例如两个红色(颜色属性值)物体在颜色属性的角度是不可区分的，它们是不可区分关系，而一个红色和一个黄色物体是可以区分的，它们是可区分关系。从集合关系角度来看，不可区分关系就是等价关系,因此所有具有相同描述的对象构成一个等价类，而所有等价类构成对[19,20]象的一个划分。定义2.9不可区分关系概念数学定义：设S=(U,A,V,f),R⊆A,定义属性R的不可区分关系为：IND(R)={(x,y)|(x,y)∈U×U,∀r∈R,f(x,r)=f(y,r)}当(x,y)∈IND(R)，则称x和y在属性集(知识)R上是不可区分关系的。显然，不可区分关系IND(R)是U上的一个等价关系，且r∈R时，IND(R)=∩IND(r)[13]定义2.10等价类概念数学定义：设S=(U，A，V，f),对属性集R⊆A中具有相同等价关系的对象集合称为等价关系IND(R)的等价类，可表示为：[x]R={y|(x,y)∈IND(R)}[x]R表示所有与R不可区分的对象组成的集合，即由x决定的等价类。2.3.4论域划分7 第二章粗糙集理论基础论域划分可称为分类，它将研究对象分成不同的类，类之间互不相交，且每一个对象均包含在某一类中。[14]定义2.11论域划分数学定义：设S=(U，A，V，f),R⊆A,U/IND(R)表示IND(R)在U上导出的划分，简记为U/R,其中，Ri⊆U，Ri≠Φ；Ri∩Rj=Φ,i≠j,i,j=1,2…;∪Ri=U。U/R其实表示属性集R的所有等价类构成的集合。粗糙集理论中以等价关系代替分类。当用R表示论域U中对象之间的等价关系时，则R的等价类形成U的一个划分，它将论域U中的对象划分成各不相交的子集。例2.2:设空间物体某集合U={x1,x2,x3,x4,x5,x6,x7,x8},集合U中含有8个物体，区分和描述物体的属性有“颜色”、“形状”、“体积”三种属性。“颜色”的属性值取红、黄、绿。形状的属性值取值为圆、方、三角形。体积取大，小。物体的描述如下表所示，表2.4空间物体集合U表属属性颜色形状体积性物值体x1红圆小x2绿方大x3红三角形小x4绿三角形小x5黄圆小x6黄方小x7红三角形大x8黄三角形大U中的物体，按照“颜色”这一等价关系，可以划分为“红色物体”={xl，x3,x7}、“黄色物体”={x5，x6，x8}、“绿色的物体”={x2，x4}集合；按照“形状”这一等价关系，可以划分为“方的物体”={x2，x6}、“圆的物体”={xl，x5}、“三角形的物体”={x3，x4，x7，x8}等集合；按照“体积”这一等价关系，可以划分为“大的物体”={x2，x7，x8)、“小的物体”={x1，x3，x4，x5，x6}集合。如果仅依据“颜色”属性去区别物体，“颜色”属性值相等的不同物体是不可区分的，如｛x2,x4｝是不可区分的，因为它们的颜色属性值都是绿色。如果以“颜色”和“体积”两个属性去区分物体，由表可知，x1,x3是不可区分的，因为它们都是红色小物体。8 基于粗糙集理论疾病初步诊断决策支持研究U分别关于“颜色”、“形状”、“体积”属性的划分如下，U|“颜色”={{xl，x3，x7}，{x2，x4}，{x5，x6，x8}}，U|“形状”={{xl，x5}，{x2，x6}，{x3，x4，x7，x8)}},U|“颜色+形状”={{x1},{x2},{x3,x7},{x4},{x5},{x6},{x8}},U|“颜色+体积”={{x1,x3},{x7},{x2},{x4}{x5,x6},{x8}},U|“形状+体积”={{x1,x5},{x2},{x6},{x3,x4},{x7,x8}},U|“颜色+形状+体积”={{x1},{x2},{x3},{x4},{x5},{x6},{x7},{x8}}。x1,x2.x3x3,x4,x7,x2,x7,x8x8x2x5,x6,x1,x5x1,x3,x4x4x8x2,x6x5,x6U|“颜色”U|“形状”U|“体积”x1x2x1x2x1x4x3x3x4x5x5x2x5x6x7x7x6x7x6x8x8x8x3x4U|“颜色+形状”U|“颜色+体积”U|“形状+体积”x1x2x3x4x5x6x7x8U|“颜色+形状+体积”图2.2集合U在各属性下的划分示意图2.4粗糙集理论诞生的背景及发展历程1904年，谓词逻辑创始人G．Frege提出了含糊边界线问题,即如何计算边界线上含糊元素数量，许多数学家和计算机科学家都为之而进行研究.L.A.Zadeh于1965年提出了Fuzzy集，试图通过这一理论解决G.Frege的含糊概念,但遗憾的是模糊集理论没有给出精确的数学公式描述这模糊概念。故无法计算出G.Frege边界线上具体的含糊元素数目.如模糊集中的隶属函数μ和模糊逻辑中的算子λ都是如此.时隔20年后的1982年波兰华沙理工大学的Pawlak教授针对G.Frege的9 第二章粗糙集理论基础边界线区域思想提出了Rough集,把那些无法确认的元素都归属于边界线区域,而这种边界线区域被定义为上近似集和下近似集之差集。由于上近似集和下近似集都可以通过等价关系给出确定的数学公式描述,所以边界线上的含糊元素数目被认为是可以计算出来的。从而实现了G.Frege的边界线思想。1982年ZPawlak发表了经典论文RoughSets，宣告了粗糙集理论的诞生。1991年，ZPawlak出版的专著RoughSets，成为粗糙集理论研究的第一个里程牌．2003年10月，第9届粗糙集、模糊集、数据挖掘与粒度计算国际会议(RSDFGRC)在重庆邮电学院成功召开。2004年第四界粗糙集与计算趋势的专题国际会议(RSCTC)在挪威BioninformaticsUppsalaUniversity召开。经过30年的长足发展研究，粗糙集理论已成为人工智能领域中的一个新学术热点，在机器学习、知识获取、知识发现和决策分析等领域得到了广泛的研究与应用。2.5粗糙集理论的理论特点及优势粗糙集理论在分类意义下定义了模糊性和不确定性的概念，能够有效地分析不精确、不一致、不完整等各种不完备信息，还可以对数据进行分析和推理，从中发现隐含的知识，揭示潜在的规律。模糊集和基于概率方法的证据理论是处理不确定信息的两种方法，已用于一些实际的领域。但这些方法有时需要一些数据的附加信息或先验知识，如模糊隶属函数、基本概率指派函数(BasicProbabilityAssignment，BPA)和有关统计概率分布等，而这些信息有时并不容易获得。模糊集和粗糙集理论在处理不确定和不精确性问题方面都推广了经典集合论，它们都可以用来描述知识的不精确性和不完全性。模糊集和粗糙集的不同主要体现在以下四方面：表2.5粗糙集和模糊集比较角度粗糙集理论模糊集理论从知识的”粒度”上来粗糙集着眼于知识的模糊集主要着眼于知看粗糙性识的模糊性粗糙集是通过一个集模糊集是通过对象关从知识描述的方法上合关于某个已知的可利用于集合的隶属程度来近似来看的信息库(即近似空间)的描述的一对上，下近似来描述的粗糙集研究的是不同模糊集研究的是属于从研究的对象来看类中的对象组成的集合之同一类的不同对象的隶属间的关系，重在分类关系，重在隶属程度粗糙集强调的是集合模糊集强调的是集合从集合的对象间的关对象问的不可分辨性边界的病态定义，既边界的系来看不分明性粗糙集和模糊集是两种不同的理论，但它们之间也不是相互对立的。它们在处理不完整数据方面可以互为补充。10 基于粗糙集理论疾病初步诊断决策支持研究粗糙集理论的特点主要表现在以下几个方面：(1)它能处理各种数据，包括不完备的数据和拥有众多变量的数据。(2)它能对属性和值进行约简．它在不降低分类精度的条件下，可以识别和删除冗余的和不相关的数据，仅保留关键信息，并可求得知识表达的精简规则。(3)它能产生精确而又易于检查和证实的规则，特别适合于智能控制中规则的自动生成．2.6粗糙集理论的研究现状及其发展方向目前，粗糙集理论的研究主要集中在：粗糙集模型的推广、问题的不确定性的研究、与其他数学理论结合研究、粗糙集的算法研究和与数据挖掘、人工智能的应用结合研究。关于模型推广主要进展是出现了模糊粗糙集模型、可变精度粗糙集模型、粗糙模糊集模型、基于优先关系的粗糙集模型、基于相似关系的粗糙集模型、不完全信息系统下的粗糙集模型等．目前，粗糙集理论中的算法研究主要集中在导出规则的增量式算法，约简的启发式算法，粗糙集基本并行算法，以及与粗糙集有关的神经网络和遗传算法研究等．目前，粗糙集理论在应用方面的研究也在快速的发展，国际上已经开发出了一些应用粗糙集的实用化软件，如加拿大Regina大学开发的基于可变精度粗糙集模型的系统KDD—R，美国肯萨斯大学开发了一套基于粗糙集的经验学习系统，名为LERS，它能从大量经验数据中抽取出规则，挪威TrollData公司开发的基于粗糙集理论的数据挖掘工具RoughEnough等。粗糙集理论已成为信息科学、人工智能、数据挖掘研究中最活跃的领域之一．今后的研究方向将主要会集中在：(1)对不完备信息处理方法研究。(2)大数据集问题研究。(3)高效约简算法研究。(4)多方法互补融合研究。(5)方法实践应用研究。2.7粗糙集理论概念和粗糙集定义Pawlak教授提出的粗糙集理论中所有的概念和运算都是通过代数的等价关系和集合的运算来定义的，被称为粗糙集理论的代数观描述(传统的粗糙集理论)。它是以不可区分关系为基础的，通过引入上近似集合下近似集在集合运算上进行定义并得到不同的确定性概念和近似概念。2.7.1集合X的上近似集与下近似集[20]定义2.12集合X的上下近似集定义：设S=(U，A，V，f),R⊆A，X⊆U，属性集R的等价类Ri=[x]R,则X的R下近似集与R上近似集分别定义为：R(X)=RR∪{|∈⊆U/R且RX}iiiRX={|（）RR∪∩∈≠U/R且RX}∅iii下近似集和上近似集还可以定义为：RX={x|（）∪[]x[]⊆X}RRRX={x|（）∪[]x[]⊆X}RR可以看出下近似集为所有那些被包含在X里面的等价类的并集，上近似集为所有与X相交非空的等价类。[20]2.7.2集合X的正域、负域与边界域定义2.13设S=(U，A，V，f),R⊆A，X⊆U，论域U根据属性集R来划分，可11 第二章粗糙集理论基础以将U划分为X的R正域，X的R负域，X的R边界域等三个互不相交的区域(子集)分别记为POSR(X)，NEGR(X)，BNDR(X)，其定义分别如下：POSR(X)=RX（）其中POSR(X)表示根据现有属性集R(知识)判断肯定属于X的U中对象所组成的集合。NEGR(X)=U-RX（）其中NEGR(X)表示根据现有属性集R(知识)判断肯定不属于X的U中对象所组成的集合。BNDR(X)=RX（）－RX（）其中BNDR(X)表示根据现有属性集R(知识)既不能判断肯定属于X又不能判断肯定属于U-X的U中对象所组成的集合。2.7.3粗糙集定义可以看出RX（）实际上是由那些根据现有的属性集R(知识)判断可能属于X的U中对象所组成的集合。如果RX（）=RX（），则BNDR(X)=∅,即边界区域为空，称X为R的可定义集；否则X为R的不可定义集，即X为R的粗糙集。关于粗糙集的定义如下图所示：论域U上近似边界概念X下近似图2.3粗糙集示意图粗糙集理论(RS理论)认为知识就是一种分类能力，它把那些无法确认的个体都归属于边界区域，而这种边界区域被定义为上近似集与下近似集之间的差集。因此，利用等价类划分，任意的对象集合可以用该对象集合的上近似和下近似两个确定的集合来上下逼近，进行粗糙地定义。2.7.4集合X的确定度定义2.14设S=(U，A，V，f),R⊆A，X⊆U，论域U根据属性集R来划[21,22]分，集合X的确定度定义为：U-RX-RX（）（）γ(X)=RU12 基于粗糙集理论疾病初步诊断决策支持研究其中，|U|与RX-（）（）RX分别表示集合Ｕ与RX-（）（）RX中对象的个数。γ(X)的值反映了Ｕ中的能根据R中各属性的属性值就能确定其属于或不R属于X的比例，即对U中的任意一个对象，根据R中各属性的属性值确定它属于或不属于X的可信度。集合X的确定度γ(X)满足0≦γ(X)≦1，其性质如下：RR(1)若γ(X)=0，则X为R的完全不可定义集。U中全部对象都不能根据RR中的各属性的属性值来确定其是否属于X。(2)若0＜γ(X)＜1，则X为R的部分可定义集。U中部分对象根据R中的R各属性的属性值就可以确定其是否属于X，而另一部分对象是不能确定其是否属于X。(3)若γ(X)=1，则X为R的可定义集。U中全部对象能够根据R中的各属R性的属性值就可以确定其是否属于X。当0≦γ(X)＜1时，称X为R的粗糙集。R2.8属性依赖度与属性必要性[23,24]2.8.1属性依赖度定义2.15设S=(U,A,V,f)，其中A=C∪D,C∩D=Ф,C称为条件属性集,D为决策属性集，根据决策属性集D的划分U/D={Y1,Y2,…,YN},[25]则决策属性集D对条件属性集C的依赖程度K(C,D)定义为：K(C,D)=|POSC(D)|/|U|其中，POSC(D)为条件属性集C相对于决策属性集D的正域，POSC(D)=∪CY（）i(i=1,2,…,n)。|POSC(D)|表示正域POSC(D)的对象个数。|U|表示论域U中对象的个数。可知，K(C,D)表示条件属性集C能区分决策属性集D等价类的能力。属性依赖度K(C,D)满足0≤K(C,D)≤1，其性质如下：(1)若K(C,D)=0，则称D完全不依赖于C，表示根据条件属性集C的取值，不能对U中对象进行准确分类。(2)若0＜K(C,D)＜1，则称D部分依赖于C，表示根据条件属性集C的取值，只能将U中属于正域的对象进行准确分类。(3)若K(C,D)=1，则称D完全依赖于C，表示根据条件属性集C的取值，可以对U中所有对象进行准确分类。如果属性依赖度K(C,D)=1，则称决策表是一致的，否则称决策表是不一致的。2.8.2属性必要性设S=(U,A,V,f)，其中A=C∪D,C∩D=Ф,C称为条件属性集,D为决策属性集，c∈C,若POSC(D)≠POSC-{c}(D),则称c为C中相对于D必要的，是不可省略的；否则，称c为C中相对于D不必要(可省略的)。2.9属性约简与核“属性约简”是指对于给定的一个知识库(决策表),删除其中的一些属性,[26,27]而又使它与原来的知识库具有相同的表达能力，“属性约简”是粗糙集理论13 第二章粗糙集理论基础中的核心内容之一。定义2.16设S=(U,A,V,f)，其中A=C∪D,C∩D=Ф,C称为条件属性集,D为决策属性集，P⊆C，如果P中的每一个属性c∈P,在P中相对于D是必要的，即，POSP(D)≠POSP-{c}(D),则称P是相对于D是独立的。如果P相对于D独立的，且POSP(D)=POSc(D),则称P是C中相对于D的属性约简，记为redD(C),简称约简。C中所有相对于D必要的属性组成的集合，称为C相对于D的核(简称核)，记为coreD(C)。C中相对于D的所有属性约简的交就是C相对于D的核，即coreD(C)=∩redD(C)。显然，核属性是绝对必要的条件属性，去掉[28,29]其中任何一个核属性，都会改变决策表的分类能力。2.10决策表的属性约简与决策规则获取2.10.1决策表的属性约简与信息表提供的U中对象的信息不同，决策表关心的是通过条件属性集C预测或表示决策属性集D。也就是说可根据决策属性将全部对象划分为各不相交的决策等价类，决策表的属性约简是指在保持决策表的分类能力或决策能力不变[30,31]的前提下，删除其中不重要或不相关的属性，使产生的决策规则更加简练。因此，具有很强的应用价值。2.10.2决策表的决策规则定义与约简定义2.17设S=(U,A,V,f)，其中A=C∪D,C∩D=Ф,C称为条件属性集,D为决策属性集，U中关于C的划分U/C={X1，X2，…，Xn},Xi(i=1,2,…,n)表示U/C中的条件等价类，U中关于D的划分U/D={Y1，Y2，…，Ym},Yj(j=1,2,…,m)表示U/C中的决策等价类，des(Xi)表示对条件等价类Xi的特征描述，即等价类Xi对于各条件属性的特定取值，des(Yj)表示对决策等价类Yj的特征描述，即等价类Yj对于各决策属性的特定取值，下图表示条件等价类Xi和决策等价类Yj的上下近似集关系。X1YjX3X2图2.4Xi与Yj的上下近似关系[32]定义2.18决策表的一个决策规则可定义为：GZij:des(Xi)→des(Yj)式中Xi∩Yj≠∅；des(Xi)是指决策规则的前提(条件)，如疾病特征；des(Yj)为规则的结论，如可能的疾病(诊断结果)。决策规则也可定义为：GZij:IFdes(Xi)THENdes(Yj)[33]定义2.19决策表的一个决策规则可信度定义为：cf(Xi,Yj)=|Xi∩Yj|/|Xi|其中，|Xi∩Yj|表示集合Xi∩Yj中的对象个数，|Xi|表示集合Xi中的对象个数。依据上述定义，通过分析决策表的条件等价类和决策等价类两个划分之间的14 基于粗糙集理论疾病初步诊断决策支持研究关系来获取规则，会产生大量决策规则，但是这些规则概括能力差，冗余较多，有必要对产生的规则进行简化。通常决策规则分为两类，一类是规则可信度小于1的，即由上近似集产生的规则，会出现多条具有条件相同而结论不同的规则，该类规则不便简化，另一类是可信度为1的规则，是由下近似集产生的规则，这类规则可以简化。[34]决策规则约简的原则是在条件属性中删除某些属性后，规则的可信度依然为1。设c∈C,C’=C-{c},在C’下的等价集Xi’与决策属性集D的等价集Yj之间仍存在：Xi’∩Yj=Xi’时则属性c是可以省略的否则c是不可省略的。决策表规则的约简是利用决策逻辑分别通过消去决策表中每个决策规则的不必要条件，它不是整体上约简属性，而是针对每一个决策规则，去掉表达该规则时的冗余属性值，以便进一步使决策规则最小化。2.11本章小结本章主要介绍了粗糙集理论的基本知识,给出了集合与集合运算，集合和粗糙集中的等价关系与等价类，粗糙集的诞生的背景、发展历程、理论特点、研究现状和发展前景等相关论述。并给出了信息表达系统、信息表、决策表、粗糙集的上下近似集、属性约简与核、属性必要性和属性依赖度、决策规则约简等相关概念的定义。通过这些必要知识的学习和理解，可以加深对粗糙集理论的理解,为后续章节奠定理论基础。15 第三章粗糙集属性约简经典算法研究近年来，人类进入信息时代，人们获得信息越来越容易，随着大规模数据库的广泛使用和Internet迅猛发展，数据库中存储的数据量越来越大，且数据还在不断动态变化，形成庞大的、多维的、冗余的海量数据。这些海量未处理的数据并未为人类带来十足的好处，反而使人类陷入“数据灾难”、“决策灾难”。导致要么“疲于应付”，要么“弃之不用”。具体的说特别是大量冗余的数据会带来两方面的负面影响，一方面,数据需要大量的存储空间,会造成存储资源的浪费；另一方面,冗余数据会干扰人们做出正确而简洁的决策，使数据的作用性大大降低。对解决这类问题的研究，一般称为“从数据库中发现知识(KDD)”与“DataMining”。在数据挖掘中往往要对数据进行预处理，数据预处理的通常一个步骤是属性约简。粗集理论(RoughSet)一个最重要的贡献是提供了一种对数据库中的知识进行约简的方法。属性约简是粗糙集理论研究的核心内容之一，它是在保持知识库分类能力不变的条件下，删除其中不相关或不重要的属性。通过属性约简可以从特征信息中提取有用的信息，简化知识处理过程及获得知识的分类规则[35,36]。约简后属性的个数将直接影响粗集导出的规则的规模。一般来说,约简后的属性越少,则由它导出的规则数就越少、越简单,用这些规则对新的对象进行分类时的检验代价就越低。在实际应用中,人们总是希望找出信息系统或决策表的尽量小的约简。属性约简在决策表处理中的作用体现如图3.1所示：带有冗余属性属性约简作用原决策表简化的的产生约简子集决策表决策表图3.1属性约简在决策表处理中的作用体现示意图本章主要分析研究属性约简的一些经典算法，作者称这些算法为经典算法是因为关于属性约简的其它算法一般都是由这些算法演化而来的。下文从算法思想，算法性能等方面对各属性约简算法进行了分析总结,理解和发现目前存在算法的不足之处,为后文能够提出改进算法奠定基础。本章主要涉及的经典算法主要有：基于正域的属性约简算法基于属性依赖度(重要度)的属性约简算法基于条件信息嫡的属性约简算法基于差别矩阵的属性约简算法3.1基于正域的属性约简算法(1)基于正域的属性约简算法的基本思想基于正域的属性约简算法，主要是利用粗糙集正域及粗糙集上下近似等基本概念来进行属性约简的，简单来说,基于正域的属性约简算法,就是在信息系统或决策表中，依次去掉某个属性,考察剩余的属性对正域的影响，若正域发生变化,则应该保留该属性；若正域没有发生变化,则去掉该属性。算法的实质是考察属性去除对正域的影响。(2)基于正域的属性约简算法的算法描述及流程图基于正域的属性约简算法步骤描述如下:算法输入：信息系统S=(U，A，V，f)，其中U为非空的有限对象集合，称为论域，A为描述对象的非空有限属性集合，且A=C∪D，C∩D=Φ，C为条件属性集，D为决策属性集。算法输出：约简子集red16 基于粗糙集理论疾病初步诊断决策支持研究步骤1.初始化red=C，temp=C。步骤2.计算正域POSC(D)。步骤3.如果temp≠Φ，循环取a∈temp，如果POSred-{a}(D)=POSC(D)，则red=red-{a}；否则temp=temp-{a}。步骤4.当temp=Φ时，循环终止。步骤5.输出约简子集red。算法流程图如下图所示：开始输入信息系统S=(U，A，V，f)初始化red=C,temp=C计算正域POSC(D)选择属性集合temp中一个属性a否循环终止条件temp≠Φ是否判断temp=temp-{a}POSred-{a}=POSC(D)是red=red-{a}输出约简子集red结束图3.2基于正域的属性约简算法的流程图(3)基于正域的属性约简算法的性能分析由上算法可知，输出约简子集必须计算正域POSC(D)一次，计算相对正域POSred-{a}需要|C|次，|C|表示决策系统条件属性的个数，根据粗糙集理论的基本概念,求正域的过程中要考虑到最坏情况下计算等价关系和求上下近似的时间复17 第三章粗糙集属性约简经典算法研究2[37,38]杂度O(|A||U|)和O(|A||U|log|U|)。随着属性集规模的增大,会产生大量的属性组合,因此算法的时间复杂度会很大。由此可知,基于正域的属性约简算法适用于信息系统的条件属性和对象的数目较少的情况，在此条件下可以产生约简子集，但是不能保证此约简是满意约简。许多学者在基于正区域求解约简方面做了大量研究，例如，刘少辉等人采用快速排序法对属性集c排序后划分等价类，将[39,40]正区域计算时间复杂度降为O(|C|×|U|log|U|)，更有甚者，从决策系统的不一致情况出发，给出了不一致度的概念及其性质，并证明了不一致记录与正区域的等价关系。然后，提出了基于Hash的正区域计算方法，其时间复杂度下降[40]为O(|U|)。3.2基于属性依赖度(重要度)的属性约简算法属性重要度的定义定义3.1设S=(U，A，V，f)，其中A=C∪D，C∩D=Φ，C为条件属性集，D[41]为决策属性集。P⊂C，则对任意属性c∈C-P的重要度定义为：SGF(c，P，D)=k(P∪{c}，D)-k(P，D)其中k(P，D)表示决策属性D对条件属性P的依赖性，k(P∪{c}，D)表示决策属性D对条件属性P∪{c}的依赖性。SGF(c，P，D)的值越大，说明在已知条件属性子集P的条件下，条件属性c对决策属性集D就越大。（1）算法的基本思想由粗糙集的理论可知，任何决策表的核是所有属性约简的交集，是唯一的，因此属性的约简算法可以将核作为求解属性约简的起点，基于属性依赖度的属性约简算法就是一种以核为起点的启发式算法，它的主要思想是利用正域先计算决策系统的核属性，然后，根据粗糙集属性依赖度定义和计算属性重要度，再依次将除核以外的属性中重要度最大的属性加入到约简子集中,直至求出约简子集为止。（2）算法描述及流程图基于属性依赖度(重要度)的属性约简算法描述如下：算法输入：信息系统S=(U，A，V，f)，其中U为非空的有限对象集合，称为论域，A为描述对象的非空有限属性集合，且A=C∪D，C∩D=Φ，C为条件属性集，D为决策属性集。算法输出：约简子集P步骤1.计算决策属性集D对条件属性集C的属性依赖度k(C，D)。步骤2.计算C相对于D的核coreD(C)，并令P=coreD(C)。步骤3.计算k(P，D)，若k(P，D)=k(C，D)，则终止转步骤5；否责转步骤4。步骤4.对每一个属性c∈C-P，计算其属性重要度SGF(c，P，D)，选择SGF(c，P，D)值最大的属性，记作p。令P=P∪{p}，转步骤3。步骤5.输出一个约简子集P。对于步骤2,具体可操作为：.初始化coreD(C)=Φ对于任意的a∈C,计算其相对正域,如果POSC-{a}≠POSC(D)则coreD(C)=coreD(C)+{a}。算法的流程图如下图所示：18 基于粗糙集理论疾病初步诊断决策支持研究开始输入信息系统S=(U，A，V，f)是k(P，D)=k(C，D)计算属性依赖度k(C,D)否计算coreD(C)，令P=coreD(C)计算每一个属性c∈C-P的SGF(c，P，D)选择最大SGF(c，P，D)的属性记作p,令P=P∪{p}计算k(P，D)输出约简子集P结束图3.3基于属性依赖度(重要度)的属性约简算法流程图（3）算法性能分析采用属性依赖性(重要度)的约简算法并不能保证一定能够找到信息系统的最优解。原因在于属性的“组合爆炸”。在信息系统中各个属性并不是孤立存在[42]的，而是存在着相互之间的联系和影响。对于某些属性虽然它们的单个重要度都很小，但是当这些属性组合在一起时，却能对整个信息系统的正确分类产生很大的作用，而这一点有时仅仅凭借单个属性的重要性评价方法是很难发现的，因为那些重要性很小的属性很难被约简算法所选择。该算法只能得到信息系统的一个约简,但不能保证得到的约简是最优约简。3.3基于条件信息熵的属性约简算法(1)信息熵的定义定义3.2设S=(U，A，V，f)是一个信息表，P⊆A，U/P={X1,X2，…，Xs},则[43]知识(属性集合)P的信息熵H(P)定义为：sHP=-（）（）∑ppXli2iog(X)（）i=1其中p(Xi)表示基于P的划分的等价类Xi的概率，计算方法是|Xi|/|U|，表示某个等价类中对象的个数与论域中所有对象个数的比。信息熵的简单理解是，在信息表中，已知属性P，此时要对对象准确分类还需要的信息量就是P的信息熵H(P)。(2)条件信息熵的定义19 第三章粗糙集属性约简经典算法研究定义3.3设S=(U，A，V，f)是一个信息表，P⊆A，Q⊆A，X=U/P={X1,X2，…，Xs}，Y=U/Q={Y1，Y2，…，Yt}，则知识(属性集合)Q相对于知识(属性集合)P的[43]条件信息熵定义为：stHQ|P=（）-∑∑pp(X)(Y|X)log(Y|X)iji2jipi1==j1其中，p(Yj|Xi)=|Yj∩Xi|/|Xi|，由条件信息熵的定义可知，H(Q|P)=H(Q∪P)-H(P)。(3)基于信息熵的属性重要度的定义定义3.4设S=(U，A，V，f)其中A=C∪D，C∩D=Φ，C为条件属性集，D为[41]决策属性集。P∈C，则对任意属性c∈C-P的重要度定义为：SGF(c，P，D)=H(D|P)-H(D|P∪{c})SGF(c，P，D)的值越大，说明在已知条件属性P的条件下，条件属性c对决策属性集D就越重要。（4）算法的基本思想基于条件信息熵的属性约简算法是把条件信息熵变化的大小作为启发式信息，即在决策表中添加某个属性所引起的条件信息熵的变化作为该属性重要度的度量。（5）算法的描述及流程图基于条件信息熵的属性约简算法描述如下：算法输入：信息系统S=(U，A，V，f)，其中U为非空的有限对象集合，称为论域，A为描述对象的非空有限属性集合，且A=C∪D，C∩D=Φ，C为条件属性集，D为决策属性集。算法输出：约简子集P步骤1.计算决策属性集D相对条件属性集C的条件信息熵H(D|C)。步骤2.计算C相对于D的核coreD(C)，并令P=coreD(C)。步骤3.计算H(D|P)，若H(D|P)=H(D|C)，则终止转步骤5；否责转步骤4。步骤4.对每一个属性c∈C-P，计算其属性重要度SGF(c，P，D)，选择SGF(c，P，D)值最大的属性，记作p,令P=P∪{p}，转步骤3。步骤5.输出一个约简子集P。在步骤2中求核的方法是：取每个c∈C,若H(D|C)≠H(D|Ｃ－｛ｃ｝)，则c属于核集合。20 基于粗糙集理论疾病初步诊断决策支持研究算法的流程图如下所示：开始输入信息系统S=(U，A，V，f)计算条件信息熵H(D|C)计算coreD(C)，令P=coreD(C)计算H(D|P)是H(D|P)=H(D|C)否计算每一个属性c∈C-P的SGF(c，P，D)选择最大SGF(c，P，D)的属性记作p,令P=P∪{p}输出约简子集P结束图3.4基于条件信息熵的属性约简算法流程图（6）算法的性能分析基于条件信息熵的属性约简算法和基于属性依赖度的属性约简算法都属于启发式约简算法，只是它们的属性重要度计算方法不同，它们算法的局限性相差不大，基于信息熵的属性约简算法中,从信息的角度重新定义了一种属性重要度，重视了属性之间相互联系和影响的作用，分析可知，算法在最坏的情况下，每次所考虑的属性数依次为|C|，|C|-1，|C|-2，…，1(|C|为决策表的条件属性数)，故总次数为|C|+(|C|-1)+(|C|-2)+…+1=|C|(|C|+1)/2。如果忽略对象数对时间2[39]的影响,那么,在最坏的情况下,以上算法的时间复杂度为O(|C|)。该算法在空间不复杂的情况下可能找到最优解,但是随着数据集规模的增大，算法效率会有所下降，当属性间关系比较复杂的情况下,容易陷入局部最优，利用启发式算法的确能够提高约简的求解速度,而且在解空间不复杂的情况21 第三章粗糙集属性约简经典算法研究下有可能得到最优解或次优解,但在解空间较复杂或属性间关系较为复杂的情况下,用这些方法找到的解极有可能陷入局部最优解,这种算法并非对所有的知识表达系统都适用。3.4基于差别矩阵的属性约简算法[44,45](1)差别矩阵和差别函数差别矩阵也称作可辨识矩阵或分明矩阵，是由波兰华沙大学数学家斯科龙(Skowron)教授于1991年提出的，为我们求取最佳属性约简提供了很好的方法。该方法将决策表中所有有关属性区分信息都浓缩进一个矩阵当中，通过该矩阵利用简单的数学逻辑运算可方便地得到决策表的属性核。有关差别矩阵的定义描述如下：定义3.5设S=(U，A)为一个决策系统，U为论域且U=(x1，x2，…，xn)，A是属性集合，可分为条件属性和决策属性，及A=C∪{d}。a(x)是对象x在属性a上的值，差别矩阵可表示为一个n阶矩阵：M(S)=(Cij)n×n其中Cij称为差别矩阵的元素，当xi=xj时，Cij=Φ，当xi≠xj时Cij={a∈A|a(xi)≠a(xj)}，Cij其实是使第i个个体xi与第j个个体xj属性值不相等的那些属性构成的集合，或说是所有能区分开个体xi和xj的属性构成的集合。因为不存在把样本xi与自身区分开的属性。且M(S)是对称的，可只用其下三角部分表示。通过逻辑运算将所有差别元素的合取式化为析取试后，记作fM(s)，称为信息系统S=(U，A)的差别函数，任意的差别矩阵M(S)都唯一地确定了一个差别函数fM(s)。则该函数的最小简化的析取范式对应信息系统的全体约简。（2）算法的基本思想基于差别矩阵的属性约简算法的基本思想是首先根据信息表构造差别矩阵，并根据差别矩阵得到差别函数，然后将差别函数转化为析取范式,每个析取项就构成信息表的约简，具体的说差别函数通过吸收律，合取范式的结合律、交换律，合取关于析取式的分配律将由差别元素的析取式表示的所有子句组成的合取式化成最简析取范式，则每个最简析取范式对应的一个约简。由此给出针对信息表的计算约简的一种算法。(3)算法的描述与流程图基于差别矩阵的属性约简算法描述如下；算法输入：信息系统S=(U，A，V，f)，其中U为非空的有限对象集合，称为论域，A为描述对象的非空有限属性集合，且A=C∪D，C∩D=Φ，C为条件属性集，D为决策属性集。算法输出：约简子集P步骤1.计算信息系统的差别矩阵M(S)。步骤2.计算与差别矩阵M(S)相关的差别函数fM(s)。步骤3.计算差别函数fM(s)的最小析取范式，它将给出所有的约简。22 基于粗糙集理论疾病初步诊断决策支持研究算法的流程图如下所示：开始输入信息系统S=(U，A，V，f)计算差别矩阵M(S)计算差别函数fM(s)计算差别函数fM(s)的最小析取范式得到所有约简结束图3.5基于差别矩阵的属性约简算法流程图（4）算法的性能分析基于差别矩阵的属性约简算法的优点是算法直观，易于理解，并且能容易计算出信息表的核属性和所有可能的约简。但该算法的缺陷十分明显:首先，当论域的对象与属性的规模较大时，差别矩阵将占有大量的存储空间，例如，当条件属性的个数为100单元，对象个数为1000000单元，则存放差别矩阵的最坏的空13间需要100×1000000×(1000000-1)/2=5×10单元。这样的决策表可能不算大,但其差别矩阵所需的存储空间却很大，这对算法的实现很不利。算法时间复杂度22为O(|C||U|)。在这类算法中，首先要求出决策表的分明矩阵，而求决策表的2分明矩阵的时间复杂度和空间复杂度均为O(|C||U|);故这种方法不仅耗时，而且要消耗大量的空间，一旦数据量很大，计算机的存储空间就会出现问题，由此可见，随着数据集规模的增大，算法的执行效率会大幅下降，对于大规模数据集，[46]约简不具备良好的操作性。3.5本章小结本章主要研究了属性约简的四种属性约简算法，包括:基于正域的约简算法、基于属性依赖度(重要度)的约简算法、基于条件信息熵的属性约简算法和基于差别矩阵的属性约简算法。通过算法研究发现:基于正域的属性约简算法能得到信息系统的一个约简，但并不能保证是最满意的约简;基于属性依赖度和基于条件信息熵的属性约简算法从两个角度定义属性重要度，能得到一个较为满意的约简，但是得到的子集不能保证是最小的;基于差别矩阵的属性约简算法能得到信23 第三章粗糙集属性约简经典算法研究息系统的多个约简，但是随着数据规模的增大，算法的效率会急剧下降。通过本章的理论研究，加深了对粗糙集属性约简算法的认识和理解，为后续设计新算法，奠定了基础。第四章实际应用角度改进属性约简算法本章重点研究从实际应用的角度改进“基于条件信息熵的属性约简算法”，实际应用的角度主要包括两个角度(1)如何实用、有效实现属性约简算法的角度。(2)针对临床医学疾病诊断具体应用的角度。在算法实现上，我们结合数据库技术和数据库查询语言提出基于SQL语句计算条件信息熵的属性约简实现方法，实例证明这种方法具有实用、快速、有效、编程工作量小且易实现的优点，在大规模数据环境下执行效率高的特点。在针对医学具体应用方面，我们改进了条件熵属性约简算法，提出了新的适用方法，取名为“能得到所有约简子集的条件信息熵属性约简改进算法”，该算法放弃了求属性的最小约简，而是利用SQL语句，简化计算条件信息熵，实现属性的所有约简，得到更适合医学应用的规则。具体请见下文。4.1能得到所有约简子集的条件信息熵属性约简改进算法(1)算法改进的原因原因一:在疾病的实际诊断中，病人与症状的关系相当复杂，由于病人与疾病之间存在“多对多关系”（一个病人可能患有多种疾病，一种疾病能够侵害多人），导致病人与症状的关系就相当乱了，还有个导致病人与症状关系乱的原因是患者身体差异，现实中同病种患者的病症很可能不同，如同样得了感冒的人，一个人咳嗽，一个人不咳嗽。面对这个多对多交织的复杂关系，原算法只能得到决策表的一个最小约简，如果要诊断疾病的话只能通过这一个约简产生规则诊断疾病，即只能通过一组症状组合去诊断疾病，但疾病决策表中的属性约简可能不止一种约简，存在多种属性约简，就说明存在多种症状属性组合能够诊断疾病。因为如果遗失一种约简，就意味着遗漏一种能够诊断疾病的症状属性集合，可能导致误诊。原因二:原算法，输出的是属性的最小约简，条件属性得到最大程度的消减，但这种最大程度的消减不一定会对具体应用带来好处。对医学实际诊断操作来说，对于最小约简中遗留的症状条件属性可能它的属性值对医生来说是最难验证，最难辨别的。如果要准确验证对医生的学识和医院的软硬件资源要求可能很高。对病人来说确诊他的疾病可能会让他提高就医成本。如果放弃求最小约简，得到所有约简，就可以多角度去诊断疾病，可以选择容易验证的症状属性组诊断疾病。原因三:新算法在实现上我们可以用简单的数据库查询语言去实现算法中最重要的求信息熵的运算，十分容易得到算法的结果，而不需要用其他编程算法编写基于内存的复杂算法实现。发挥数据库管理系统的优势，适应当前数据大多存储在数据库中的现状。（2）算法的基本思想算法依然计算属性的条件信息熵，利用条件信息熵的变化计算核属性。再利用核属性与其它属性组合进行并运算，计算并后的条件信息熵的值是否等于H(D|C)，等于就得到属性的一个约简。组合运算完毕后得到所有属性约简。24 基于粗糙集理论疾病初步诊断决策支持研究(3)算法的描述和流程图改进的基于条件信息熵的属性约简算法描述如下：算法输入：信息系统S=(U，A，V，f)，其中U为非空的有限对象集合，称为论域，A为描述对象的非空有限属性集合，且A=C∪D，C∩D=Φ，C为条件属性集，D为决策属性集。算法输出:所有约简子集。步骤1.计算决策属性集D相对条件属性集C的条件信息熵H(D|C)。步骤2.计算C相对于D的核coreD(C)，并令P=coreD(C)。步骤3.计算H(D|P)，若H(D|P)=H(D|C)，则终止转步骤5；否责转步骤4。步骤4.计算|C-P|，从C-P中分别选择1，2，…，|C-P|个属性元素构成一个集合，所有集合构成一个大集合，按照小集合中元素的个数，对小集合进行从小到到大排序。，依次计算H(D|P∪小集合i)，如果H(D|P∪小集合i)=H(D|C)。输出约简子集{P∪小集合i中元素}，同时删除后续中所有包含此小集合的集合。直到遍历完整个大集合为止。得到所有属性约简。步骤5.输出一个约简子集P。算法流程图如下（见下一页)。25 第四章实际应用角度改进属性约简算法开始输入信息系统S=(U，A，V，f)条件信息熵H(D|C)计算coreD(C)，令P=coreD(C)计算H(D|P)是H(D|P)=H(D|C)否计算|C-P|从C-P中选属性构成大集合对大集合中小集合排序否是大集合中还有小集合依次计算H(D|P∪小集合i)否H(D|P∪小集合i)=回到大集合中H(D|C)是输出约简子集{P∪小集合i中元素}删除后续中所有包含此小集合的集合结束图4.1改进算法流程图26 基于粗糙集理论疾病初步诊断决策支持研究(4)改进算法的改进实质分析改进的算法与“基于条件信息熵的属性约简算法”相比，改进的不是算法本身，因为它们输出的对象不同，前者输出所有属性约简子集，后者只输出最简约简子集，两种算法要达到的根本目的不同。是完全不同的算法。所以不需要比较两者算法的效率问题，没有可比性，但从某个具体实际应用角度来说，可以使新算法和原算法产生关系和交集。如果在具体应用中认为产生所有约简子集对于产生一个最小约简子集是一个改进的话可以称新算法在原算法上是一种在应用上的改进，本文的认为的“改进”就是从这个应用角度来说的。如果认为产生最小约简子集比产生所有约简子集是一种改进的话则新算法则就变成一种倒退算法，“改进”与“倒退”是要针对具体应用的角度来说的。改不改进的提法需要具体应用背景。本文中的改进提法实质是在原算法的基础上修改成一个新算法，扩展与原算法在同一应用领域的功能及效果，本文中的这一领域是疾病诊断领域。4.2基于SQL语句计算条件信息熵的属性约简实现方法粗糙集理论在数据挖掘中的应用研究目前正成为信息科学中的一个研究热点，其应用已经日益广泛，发展空间也非常广阔，属性约简是粗糙集理论中重要的研究内容之一,目前的属性约简算法通常有一个很大的弊端是：算法多是基于[47,48]主存的。基于主存的算法通常会带来以下两个问题，(1)算法编程工作量较大，运算耗时。(2)无法处理大规模数据集，当所处理的数据量较大时，算法的时空代价将大大增加。这两个问题直接制约了属性约简算法在实际中的应用，也限制了粗糙集理论在数据挖掘中的实际应用。多数经典属性约简算法还有一个的[49]问题是，无法将粗糙集的约简算法融入到数据库体系中，我们知道数据库系统具有存取效率高、存储空间利用率高、适合大规模数据存储等优点，数据库查询语言具有操作大规模数据功能强大的优点。而且在现实生活当中，我们所关心的大多数据都是存储在数据库系统当中的，所以如何将粗糙集理论与数据库技术进行综合运用是一个十分值得研究的内容。在经典基于条件信息熵的属性约简算法中，决策表的核和条件属性等计算都是通过计算信息熵来实现的。本节通过数据库查询SQL语句来实现条件信息熵的计算，该方法具有能与数据库系统结合、实用、快速有效、易开发的特点。在粗糙集理论中，决策表若以关系数据库形式表示，可将粗糙集理论中相关算法嵌入到数据库应用系统中。根据不可区分关系U/P={X1，X2，…，Xn}的定义，两个对象同属于一个等价类当且仅当对知识P中的每个属性，它们的属性值都相等。在标准SQL语言中，GROUPBY子句和聚集函数COUNT(*)可将数据库中记录按某一列(属性)或多列(属性)值分组，值相等的为一组，同时得到每组所包含的记录个数。组的个数在粗糙集理论中也就是划分的等价类的数目，每组所包含记录的个数也就是等价类所包含的对象数目。因此，根据p(Xi)=COUNT(*)/|U|可得到知识P在U的子集组成的σ-代数上的概率分布。而根据聚集函数SUM(*)求和，可得到知识P的信息熵H(P)=－∑p(Xi)log(p(Xi))＝-SUM(p(Xi)log(p(Xi)))=-SUM(p(Xi)*(log(p(Xi)/log(2)))。设S=(U，A，V，f),其中A=C∪D,C∪D=Φ,C是条件属性集，D={d}为决策属性集，P={r1,r2,r3}是属性集A的子集，U/P={X1，X2，…，Xn},Xi表示U/P中第i个等价类，p(Xi)=|Xi|/|U|表示U/P中第i个等价类的概率分布。则计算属性集P的信息熵H(P)的SELECT批处理语句为：27 第四章实际应用角度改进属性约简算法SELECTCOUNT(*)/|U|ascount_pINTOtable_1FROMtableGROUPBYr1,r2,r3SELECTSUM(p(Xi)*(log(p(Xi)/log(2)))ASh_pFROMtable_1GO第一个SELECT语句分别统计概率分布p(X1)、p(X2)、…、p(Xn)的值，并放在table_1数据表中；第二个SELECT语句汇总计算-∑p(Xi)log2(p(Xi)),得到信息熵H(P)，由于对于条件信息熵H(D|P)=H(D∪P)-H(P),所以条件信息熵的计算和计算信息熵的原理一样。我们从信息熵的定义去解释和理解以上SQL语句，依据信息熵的定义公式H(P)=-∑p(Xi)log2(p(Xi))可知，要计算出H(P)，首先要计算p(Xi),它表示U/P中第i个等价类的概率。对于它的计算可采用公式p(Xi)=|Xi|/|U|，我们对|Xi|的求解可以依靠SQL语句来实现。先把决策信息表依据P={r1,r2,r3}的个属性分组。然后用COUNT(*)统计各分组的元组数就等同于在Xi等价类下对象的个数，所以能计算出|Xi|，(i=1,2，…，n)当|Xi|用SQL语句计算出来以后，就可以计算出p(Xi)，(i=1,2，…，n)将它放入table_1数据表中,然后再在table_1数据表中，执行SUM(p(Xi)*(log(p(Xi)/log(2)))，得到H(P)。示例如下：例4.1以下表4.1和表4.2，提供了一组有关诊断肺结核的病例知识库(决策表)，每个病例包括4个症状表现(条件属性)和一个诊断结果(决策属性)。试根据基于SQL语句计算条件信息熵的属性约简实现方法，实现属性约简，推出诊断肺结核病例的症状集合。表4.1肺结核诊断结果与症状表现的定义症状与诊断结果数据离散化发热(c1)不发热=0，低热=1，中度热=2，高热=3咳嗽(c2)轻微咳嗽=0，中度咳嗽=1，剧烈咳嗽=2X线阴影(c3)片状=0，点状=1.索条状=2，空洞=3听诊(c4)正常=0，干鸣音=1，水泡音=2诊断结果(d)肺炎=0，肺结核=128 基于粗糙集理论疾病初步诊断决策支持研究表4.2肺结核诊断决策表Uc1c2c3c4dUc1c2c3c4d13202011002012220201232311320100131020143102014201215200201511021621020160120173210017201118211001802101931120191030110321202032211我们用SQL2008中的数据库查询语言来实现基于条件信息熵的属性约简算法，求出属性的约简与核。具体步骤如下：首先，利用SQLServer2008创建数据库WJ，在数据库中建立数据表WJTable存放表4.2提供的原始数据。数据表WJTable中的字段分别与该决策表的条件属性集C={c1,c2,c3,c4}和决策属性集D={d}一一对应。（1）计算决策属性集D相对于条件属性集C的条件信息熵H(D|C)。计算H(C)、H(D∪C)的Select查询语句与结果如图4.2、图4.3所示，图4.2计算H(C)的select查询语句与结果29 第四章实际应用角度改进属性约简算法图4.3计算H(D∪C)的select查询语句与结果。由图4.2和图4.3，可得可得，H(D|C)=H(D∪C)-H(C)=4.32192809488736-4.32192809488736=0。（2）计算C相对于D的核coreD(C)由基于条件信息熵的属性必要性可知，计算coreD(C)的过程就是计算各条件属性在C中相对于D的必要性。首先计算第一个条件属性(c1)在C中相当于D的必要性。计算H(C-{c1})和H(D∪(C-{c1}))的select语句如图4.4,图4.5所示。图4.4计算H(C-{c1})的select查询语句与结果30 基于粗糙集理论疾病初步诊断决策支持研究图4.5计算H(D∪(C-{c1}))的select查询语句与结果由图4.4和图4.5可得，H(D|(C-{c1}))=H(D∪(C-{c1}))-H(C-{c1})=4.02192809488736-3.78418371977919≈0.3377。可知H(D|(C-{c1}))≠H(D|C)，所以条件属性c1在C中相对于D是必要的。同理可得，可用select查询语句计算出H(C-{c2})、H(D∪(C-{c2}))、H(C-{c3})、H(D∪(C-{c3}))、H(C-{c4})和H(D∪(C-{c4}))的结果。对结果进行计算后得:H(D|(C-{c2}))=0=H(D|C)，H(D|(C-{c3}))≈0.1≠H(D|C),H(D|(C-{c4}))≈0.1377≠H(D|C)。所以可得到：条件属性c2在C中相对于D是不必要的，而条件c3和c4在C中相对于D是不要的。所以C相对于D的核coreD(C)={c1,c3,c4}。令P={c1,c3,c4}。(3)计算H(D|P)。由本题可知H(D|P)=H(D|(C-{c2}))=H(D|C)，计算的select语句完全与判断属性c2是不是核属性的语句完全一样在此不累述，可知H(D|P)=H(D|(C-{c2}))=H(D|C)=0。因而，P是决策表的一个属性约简，同时P也是决策表的属性核。由此可知确诊肺结核主要诊断症状是发热(c1)、X线阴影(c3)、和听诊3个症状表现。而咳嗽症状对诊断结果无影响。对于本例题P是决策表的核，也是决策表的约简，若当P是决策表的核但不是决策表的约简时，即H(D|P)≠H(C|D)时，要进行(4)运算。(4)计算|C-P|，从C-P中分别选择1，2，…，|C-P|个属性元素构成一个集合，所有集合构成一个大集合，按照小集合中元素的个数，对小集合进行从小到到大排序。，依次计算H(D|P∪小集合i)，如果H(D|P∪小集合i)=H(D|C)。输出约简子集{P∪小集合i中元素}，同时删除后续中所有包含此小集合的集合。直到遍历完整个大集合为止。得到所有属性约简。方法总结：基于SQL语句计算条件信息熵的属性约简实现方法，这种实现方法的优点是：31 第四章实际应用角度改进属性约简算法（1）将粗糙集的约简算法融入到数据库体系中。（2）无需编写复杂且基于主存程序。（3）计算各信息熵的SQL语句相似度大，易实现，满足实用、快速、有效的优点。4.3本章小结本章的第一个工作是：针对第五章要涉及的具体医学应用，设计了新的基于条件信息熵的属性约简算法，该算法放弃了求属性的最小约简，而是求属性的所有约简，得到更适合医学应用的规则，具体实例可参见第五章。本章第二个工作是：针对目前属性约简算法实现上存在的实用性、快速、有效性的缺点和不足,提出了一种新的基于SQL语句计算条件信息熵实现属性约简方法，并结合实例说明实现算法的实现过程。将粗糙集的属性约简算法融入到数据库系统当中去，能够发挥数据库系统的存取效率高、存储空间利用率高、适合大规模数据存储等优点，也能够发挥数据库查询语言操作大规模数据功能强大的优点。并且也符合了现实生活中的数据往往存储在数据库系统中的特点。32 第五章粗糙集理论应用于疾病初诊决策支持研究第五章粗糙集理论应用于疾病初诊决策支持研究在医学决策分析研究中所收集的信息和所构建的知识体系中一直存在着含糊性等问题，数据的含糊性主要体现在三个方面：（1）医学术语的模糊性(如高矮、胖瘦)。（2）医学数据的不确定性(如噪声干扰)。（3）医学知识体系的不确定性(如诊断规则的前后依赖关系之间存在不可靠因素)。粗糙集理论正是解决数据模糊性的重要方法。粗糙集理论理论在分类意义下定义了模糊性和不确定性的概念，能够有效地排除和处理数据中异常模式和噪声干扰，为数据挖掘和知识发现领域提供了一种有效而新颖的理论。近年来粗糙集理论在医学数据领域的研究逐渐成为热点。疾病初步诊断过程多是病人初次就诊时的诊断过程，是医生根据病人就诊时的病症表现，在临床理论和临床实践的指导下，进行分析、综合、推理病种病情的一系列过程。因此病人的临床症状是诊断的主要依据。可以利用大量已确诊的医学病例所提供的诊断知识建立医学诊断决策表。令U＝｛x1，x2，…，xn｝为对象集，xi表示第i个病例；C={c1，c2，…，cm}为条件属性集，cj为第j个临床症状；D={d}则是决策属性集，d表示属于哪种疾病（病种）。在定义好医学决策表后，进行症状属性约简与病例约简，产生病症与病种的联系，可以产生有助于疾病诊断的临床诊断规则。本章是作者的主要工作之一，主要研究粗糙集理论在疾病初诊时的一个简单而重要的应用。本章用实例详细论述该理论的应用整个过程。概括的说，本章是应用粗糙集理论对疾病病症数据进行数据挖掘，挖掘出普通疾病的诊断规则，建立联合诊断规则表（决策表），应用于疾病初步诊断时的决策支持。33 基于粗糙集理论疾病初步诊断决策支持研究5.1应用的整个流程概述理论应用的整个流程可由下图5.1所示：确定挖掘目标病例数据采集原始医学数据属性选择确定数据预处理连续数据离散生成决策信息表噪声缺省处理粗糙集属性约简属性编码简化决策表规则获取生成诊断规则构成多病种诊断规则库加入规则库建立多病种症状属性并的联合诊断规则数据表应用于疾病初步诊断决策支持图5.1理论应用的整个流程示意图上述整个流程示意图所表达的含义是这样的，首先确定挖掘目标，对原始医学数据进行数据预处理，预处理的过程包括病例数据的采集、条件属性（疾病症状属性）和决策属性（病种属性）的选择确定、噪声缺省值处理、连续数据的离散化、属性及属性值进行编码，数据预处理后就可以构成一个医学决策信息表，然后对生成的决策信息表采用粗糙集的属性约简算法，对冗余无意义或具有极少意义的属性（症状）进行删减。对决策表条件属性进行删减后，并对决策表中重复行进行删减，最终得到一个简化的医学诊断决策表，再对简化的决策表进行规则提取，得到疾病的诊断规则。此时得到的是单病种的诊断规则，同样的方法得到其它病种的诊断规则，形成多病种诊断规则库，最后，建立一个多病种症状属性并的联合诊断规则数据表，这里的属性并是指诊断规则数据表中所能诊断的所有疾病的病状的并集。例如一个联合规则表中只有A、B两种疾病的诊断规则，它只能诊断A、B两种疾病，假如诊断A疾病所要考虑的病状属性是体温、血压。34 第五章粗糙集理论应用于疾病初诊决策支持研究诊断B疾病所涉及的病状属性是体温和精神状态。则建立A、B的联合诊断规则表时，此表应包括的病状属性是（体温、血压）∪（体温、精神状态）=（体温、血压、精神状态）。当建立这个联合诊断规则数据表后，医生就可以同时诊断和辨别A、B两种疾病。为医生依据病状诊断疾病提供决策支持。5.2数据预处理[51,52]5.2.1医学数据的特点在应用研究中，面对医学数据的处理，自己最大体会是：病历数据具有数量大、记录形式不够统一、大量缺省值存在、简略、存在噪声数据等特点，对于电子病历常常会出现“一个医生，一种疾病，一个模板，所有病人，同样病历”这种病历记录情况，原因是医生并不关心数据质量对以后医学研究的价值，他们只图眼前治好病就行。这对我从病历中提取病例数据带来不小的困难。病历信息涵盖了医疗过程和医院活动的全部数据资源，包括临床医疗信息和医院管理信息，数据量大，针对疾病诊断规则挖掘需要从中甄选小部分有用的信息。由于病历是由医生或非医学专业人员手工录入文本或数据库的，这就会存在记录错误，存在噪声。不同的病历是由不同的医生撰写的,记录方式会有不同，记录形式不够统一。具体表现为，（1）医生往往根据自身的用词习惯决定记录用词，例如有的医生对感冒喜欢用“感冒”，有的用“上呼吸道感染”和“上感”，有的医生喜欢用“双下肢浮肿”有的用“两下肢浮肿”，而有的则用“双下肢中度可凹性浮”。（2）医生对病人病症描述的不同，医生经常根据自己的主观感受和已往的经验进行病情描述，如有的医生认为是“血压略显过高”，有的认为“血压严重过高”，还有同种病情不同病人描述病情也会不同，有的病人描述“轻微疼痛”，有的病人描述“剧烈疼痛”。这都会导致记录形式不够统一。病历记录最大的问题是存在大量缺省值，影响数据质量和粒度。缺省的原因主要有：（1）医生依据自身的医学知识经验，只是看化验单，从不记录化验单中包含的有用信息。（2）医生一般只在病状出现病变时才对它们做出相应的记录。（3）基本医学常识的省略。病历都是给医生、护士使用的，所以一些医学上的基本常识经常不写,例如,有的疾病名称的ICD号码。（4）同病种不同病人检查项目不同引起的相对缺失，由于一些检测项目可以互相替代，医生根据习惯、病人根据经济能力和效果，相同的病症因医生和病人的不同会导致检查项目的不同。因此在病历当中，某些项目的缺损率很高。以上所述不仅点明了医学病历数据的特点，而且为研究的展开奠定了基调和方向。根据医学数据的特点，我们必须对数据进行预处理。数据预处理是粗糙集理论参与医学决策分析的一个十分重要的步骤，基于粗糙集理论的数据挖掘系统都满足数据挖掘系统的一般特点，遵循数据挖掘的一般过程。数据预处理目的是对目标数据库中的数据进行再加工，检查数据的一致性和完整性，对其中的噪声数据进行处理，它一般包括数据缺省值的处理，数据的离散化等，并将数据库中的数据转换成某种容易处理的决策表形式，为决策表约简做好准备。5.2.2具体应用的数据预处理方法和步骤本章将对上呼吸道感染（感冒）和肺炎两种疾病采用粗糙集理论进行数据挖掘，挖掘出它们的诊断规则，然后加入到联合诊断规则表中。其中数据源自安徽省马鞍山市某综合医院的电子病历中。病历中数据量杂多，需要针对挖掘目的对数据进行针对性采集和预处理。数据预处理主要包括病例数据采集,属性选择,35 基于粗糙集理论疾病初步诊断决策支持研究连续属性离散化,数据中的噪声及丢失值处理,实例选择等其中的详细步骤如下所述。（1）病例数据采集数据挖掘的对象是上呼吸道感染（感冒）和肺炎两种疾病，所以从医院电子病历中采集这两种疾病的确诊病例，和症状相似的其它疾病的病例相互佐证。（2）属性选择确定疾病的病症属性可能有许多个，包括疾病的外在表征（症状）和内在病理学原理属性。我们挖掘的目的是为了辅助医生诊断疾病，主要提供医生在初诊时的决策支持，提高初诊准确率。所以我们选择疾病属性偏向于病状属性和较容易检查得到病理学属性。对于需要复杂检查验证的疾病属性我们不做考虑，留给疾病确诊过程处理。同时我们还要兼顾病种的医学常识选择条件属性，对于上呼吸道感染疾病我们选择的条件属性是头痛、体温、鼻塞流涕、全身酸痛为条件属性决策属性为病种感冒。对于肺炎我们选择的条件属性是头痛、体温、咳嗽、X光阴影、恶心、腹胀，听诊。决策属性是病种肺炎。这些条件属性都与病种存在较紧密的关系。对于与病种无关的属性，如病人姓名，身高，年龄，家庭住址属性直接不做考虑。（3）连续数据离散化。选择完条件属性和确定好决策属性后，我们分别为这两种疾病在数据库中建立一张数据信息表S=（U，A，V，f），其中U为病例论域，A为条件属性C和决策属性D的并集，且C∩D=Ф。V为各属性值集合，f为U×A→V的信息函数。在数据库中以病例编号表示U的个数，A中个属性为字段。当建立数据表后，我们就可以整理采集病历中的数据填入表中，这个表相当于最原始的决策表。在填数据时会遇到连续数据，对于连续数据我们需要离散化处理，离散的原则是（1）属性离散归一化后的空间维数尽量小，即属性值的分段尽量小（2）属性值离散化后的信息丢失保持在最小。如应用中对体温条件属性的离散化为：正常(36.5℃~38℃)，中度发烧(38℃~39℃)，高烧(39℃~42℃)。低温不做考虑。（4）噪声及缺省处理在本应用案例中，处理噪声数据比较简单，直接删除就可以，对于缺省值的处理，在病例中常常只记录非正常值，不记录正常值，如医生书写病历时只会记录咳嗽病状，很少对病人不咳嗽症状做记录，所以病例中的缺省属性我们以“正常”填充。（5）属性编码为了以后生成一个简单的，利于算法运算的决策表，我们还需要对信息数据表中的值和字段进行编码，对于上呼吸道感染和肺炎两种疾病的编码如表5.1和5.2所示。36 第五章粗糙集理论应用于疾病初诊决策支持研究表5.1上呼吸道感染诊断结果与症状表现编码定义症状与诊断结果数据离散化及编码头痛（c1）0不头痛，1头痛体温(c2)0正常，1高，2很高鼻塞流涕(c3)0无鼻塞流涕，1鼻塞流涕全身酸痛(c4)0无全身酸痛，1全身酸痛上呼吸道感染（感冒）（d）0非感冒，1感冒表5.2肺炎诊断结果与症状表现编码定义症状与诊断结果数据离散化及编码头痛（c1）0不头痛，1头痛体温(c2)0正常，1高，2很高咳嗽(c3)0不咳嗽，1微咳，2咳嗽严重X光阴影(c4)0片状，1点状，2索条状，3空洞听诊情况(c5)0正常，1干鸣音，2小泡音肺炎（d）0非肺炎，1肺炎当建立信息数据表后，数据表含有多个病例数据，此时要对信息数据表进行简化生成决策信息表，简化的方法是，删除病例中重复的病例和出现概率较少的病例，因为出现概率较少的病例一般是孤立的特殊病例，不具有考虑价值。信息表简化后就得到了决策信息表。以上两种疾病的诊断决策表如表5.3，表5.4所示。表5.3上呼吸道感染（感冒）决策表病例头痛体温鼻塞流涕全身酸痛感冒(U)（c1）(c2)(c3)(c4)（d）10211021001030011040110051111161211171201180110137 基于粗糙集理论疾病初步诊断决策支持研究表5.4肺炎决策表病例头痛体温咳嗽X光阴影听诊情况肺炎(U)（c1）(c2)(c3)(c4)(c5)（d）11220212112021300020041101015122311600020071210218110021911102110122101111101201200102013001200141111011512112116122121171111101800210019000300201222105.3决策表约简决策表的各个条件属性之间往往存在着某种程度上的依赖关系。约简可以理解为在不丢失信息的前提下，能较简单地表示决策系统的决策属性集合对条件属性集合的依赖关系，即约简后决策表具有更少的条件属性。决策表的属性约简过程就是从决策表系统的条件属性中去掉不必要的条件属性，从而分析所得约简中的条件属性对于决策属性的决策规则。38 第五章粗糙集理论应用于疾病初诊决策支持研究决策表约简的步骤：（1）约简条件属性，即把决策表中某些列消去。（2）消去决策表的重复行。约简以后的决策表是一个“不完全”的决策表，它与信息系统的一般表示相比，这里的行不表示对任何实际对象的描述。因此重复行表示的是同样的决策，所以可以把他们消去。它仅包含那些在决策时所必须的条件属性值，但它具有原始信息系统的所有知识。5.3.1约简条件属性现在我们采用第四章所论述的基于SQL语句计算条件信息熵的属性约简实现方法，来快速有效的实现条件属性约简。约简上呼吸道感染（感冒）决策表方法步骤如下：（1）计算决策属性集D相对于条件属性集C的条件信息熵H(D|C)。因为H(D|C)=H(D∪C)-H(C)。所以要计算H(D∪C)，和H(C)。计算和查询的结果分别如下图5.2和图5.3所示。图5.2计算H(D∪C)的select查询语句与结果图5.3计算H(C)的select查询语句与结果由查询结果可得H(D|C)=H(D∪C)-H(C)=0.25。39 基于粗糙集理论疾病初步诊断决策支持研究（1）计算C相对于D的核coreD（C）同（1）计算H(D|C)的方法，计算得H(D|(C-{c1}))=0.5，H(D|(C-{c2}))=0.5，H(D|(C-{c3}))=0.25，H(D|(C-{c4}))=0.25。因为H((D|C)=H(D|C-{c3}))=H(D|(C-{c4}))所以c3和c4属性是不必要属性，可删除。因为H(D|C)≠H(D|(C-{c1})),H((D|C)≠H(D|(C-{c2}))，所以c1和c2是必要属性，是核属性。coreD(C)={c1,c2}。令P={c1,c2}。（2）计算H(D|P)。同理计算H(D|P)=0.25=H(D|C)所以P是决策表的属性约简，同时P也是决策表的属性核，c3，c4可以同时省略。我们可以推断出：根据表5.3上呼吸道感染（感冒）决策表所提供的知识，感冒的诊断症状主要是“头痛”和“体温”。“鼻塞流涕”和“全身酸痛”对诊断结果没有影响。5.3.2简化决策表根据以上5.3.1的计算结果，我们可以对原表5.3提供的上呼吸道感染（感冒）决策表进行简化，消去冗余属性和重复行得以下决策表表5.5：表5.5上呼吸道感染（感冒）简化决策表病例头痛体温感冒(U)（c1）(c2)（d）1020210030004010511161217011同理我们约简表5.4肺炎决策表的步骤简单叙述如下：（1）计算H(D|C)=0（2）计算决策表的核coreD(C)={c4,c5}，令P={c4,c5}。（3）H(D|P)=H(D|c4∪c5)≠H(D|C)，所以，c1，c2，c3不能同时省略。其中：H(D|P∪{c1})≈0.14≠H(D|C)。H(D|P∪{c2})=0=H(D|C)。H(D|P∪{c3})≈0.24≠H(D|C)。H(D|P∪{c1，c3})=0=H(D|C)由上计算可知，决策表存在两种约简，一种是{c2，c4，c5}，另一种是{c1，c3，c4，c5}针对这两种约简，得到两个简化的肺炎决策表表5.6和表5.7。40 第五章粗糙集理论应用于疾病初诊决策支持研究表5.6肺炎简化决策表（c2，c4，c5）病例体温X光阴影听诊情况肺炎(U)(c2)(c4)(c5)（d）12021210213020041101523116210171120800209212110111011010012030013221041 基于粗糙集理论疾病初步诊断决策支持研究表5.7肺炎简化决策表（c1，c3，c4，c5）病例头痛咳嗽X光阴影听诊情况肺炎(U)（c1）(c3)(c4)(c5)（d）112021200200310101412311511021610021712101810120901020100120011111011211121131212114111101502100160030017122105.4决策规则生成5.4.1上呼吸道感染（感冒）的决策规则根据表5.5上呼吸道感染（感冒）简化决策表，我们可以得到决策规则，这里我们只取确诊为感冒的规则，并且计算它的可信度。规则1：头痛c1=1∧体温c2=1→d=1(感冒)可信度cf=1。规则2：头痛c1=1∧体温c2=2→d=1(感冒)可信度cf=1。简化决策表中病例U=7与病例U=4不相容，所以不生成规则。5.4.2肺炎的决策规则根据表5.6和表5.7得到确诊为肺炎的决策规则如下：规则1：体温c2=2∧X光阴影c4=0∧听诊情况c5=2→d=1(肺42 第五章粗糙集理论应用于疾病初诊决策支持研究炎)可信度cf=1。规则2：体温c2=1∧X光阴影c4=0∧听诊情况c5=2→d=1(肺炎)可信度cf=1。规则3：体温c2=1∧X光阴影c4=1∧听诊情况c5=0→d=1(肺炎)可信度cf=1。规则4：体温c2=2∧X光阴影c4=3∧听诊情况c5=1→d=1(肺炎)可信度cf=1。规则5：体温c2=2∧X光阴影c4=1∧听诊情况c5=0→d=1(肺炎)可信度cf=1。规则6：体温c2=2∧X光阴影c4=1∧听诊情况c5=2→d=1(肺炎)可信度cf=1。规则7：头痛c1=1∧咳嗽c3=2∧X光阴影c4=0∧听诊情况c5=2→d=1(肺炎)可信度cf=1。规则8：头痛c1=1∧咳嗽c3=0∧X光阴影c4=1∧听诊情况c5=0→d=1(肺炎)可信度cf=1。规则9：头痛c1=1∧咳嗽c3=2∧X光阴影c4=3∧听诊情况c5=1→d=1(肺炎)可信度cf=1。规则10：头痛c1=1∧咳嗽c3=1∧X光阴影c4=0∧听诊情况c5=2→d=1(肺炎)可信度cf=1。规则11：头痛c1=1∧咳嗽c3=0∧X光阴影c4=0∧听诊情况c5=2→d=1(肺炎)可信度cf=1。规则12：头痛c1=1∧咳嗽c3=2∧X光阴影c4=1∧听诊情况c5=0→d=1(肺炎)可信度cf=1。规则13：头痛c1=1∧咳嗽c3=1∧X光阴影c4=1∧听诊情况c5=0→d=1(肺炎)可信度cf=1。规则14：头痛c1=1∧咳嗽c3=1∧X光阴影c4=1∧听诊情况c5=2→d=1(肺炎)可信度cf=1。规则15：头痛c1=1∧咳嗽c3=2∧X光阴影c4=1∧听诊情况c5=2→d=1(肺炎)可信度cf=1。5.4.3对肺炎规则进行简化对规则7，规则10，规则11进行简化，因为三个规则在“头痛c1=1”，“X光阴影c4=0”，“听诊情况c5=2”完全相同的情况下，使咳嗽c3的值分别为2，1，0，取到了咳嗽的全值，所以在“头痛c1=1”，“X光阴影c4=0”，“听诊情况c5=2”的情况下，不需要咳嗽属性就能判断结果，所以约简三个规则中的咳嗽属性，三个规则变成一个规则，规则为：头痛c1=1∧X光阴影c4=0∧听诊情况c5=2→d=1(肺炎)可信度cf=1。同理对规则8，规则12，规则13,进行约简得到一个规则，规则为：头痛c1=1∧X光阴影c4=1∧听诊情况c5=0→d=1(肺炎)可信度cf=1。约简后的规则（可信度都为1）为：规则1：体温c2=2∧X光阴影c4=0∧听诊情况c5=2→(肺炎)规则2：体温c2=1∧X光阴影c4=0∧听诊情况c5=2→(肺炎)规则3：体温c2=1∧X光阴影c4=1∧听诊情况c5=0→(肺炎)43 基于粗糙集理论疾病初步诊断决策支持研究规则4：体温c2=2∧X光阴影c4=3∧听诊情况c5=1→(肺炎)规则5：体温c2=2∧X光阴影c4=1∧听诊情况c5=0→(肺炎)规则6：体温c2=2∧X光阴影c4=1∧听诊情况c5=2→(肺炎)规则7：头痛c1=1∧咳嗽c3=2∧X光阴影c4=3∧听诊情况c5=1→(肺炎)规则8：头痛c1=1∧咳嗽c3=1∧X光阴影c4=1∧听诊情况c5=2→(肺炎)规则9：头痛c1=1∧咳嗽c3=2∧X光阴影c4=1∧听诊情况c5=2→(肺炎)规则10：头痛c1=1∧X光阴影c4=0∧听诊情况c5=2→(肺炎)规则11：头痛c1=1∧X光阴影c4=1∧听诊情况c5=0→(肺炎)5.5生成联合诊断规则表5.5.1生成联合诊断规则表过程由以上两种疾病的诊断规则我们可以构成联合诊断规则表辅助诊断决策。生成表的方法是：考虑联合决策诊断规则表能够同时诊断哪些疾病，用这些疾病的病症属性的并，构成规则表的条件属性，以疾病的名称构成决策属性。当建立这个联合诊断规则表后，医生就可以同时诊断和辨别多种疾病。为医生依据病状诊断疾病提供决策支持。规则表如下（编码如前）：表5.8联合诊断规则表规则编号头痛体温咳嗽X光阴影听证情况病种111感冒212感冒3202肺炎4100肺炎5110肺炎6231肺炎7210肺炎8212肺炎91231肺炎101112肺炎112212肺炎12102肺炎13110肺炎5.5.2联合诊断规则表医学疾病诊断应用解读联合诊断规则表里面所存储的规则，都是从数据角度经过数据预处理，粗糙集属性约简，规则提取简化得到的最简规则，但要特别注意，通过这张联合诊断规则表中的规则所诊断出的疾病，不要认为就是这种疾病，而只是可能患有的疾病，原因是：在此决策表中的规则，只是通过疾病的部分易观测，易检查的表面病症属性产生的规则，不是疾病的全病症属性产生的规则，规则表中的规则只能说明通过这些现有的部分病症属性暂时判断出属于那种疾病。千万不要把其中的44 第五章粗糙集理论应用于疾病初诊决策支持研究规则当成是确诊规则。生成这种联合诊断规则表的主要目的是辅助医生在初诊时期的诊断决策，联合诊断规则表意在在疾病初诊时期，通过表面或易检查的病人症状数据，告诉医生病人可能患有的那些疾病，指导医生有针对性检查辨别，消除医生的盲目性。这种表的应用优点可以概括为以下几点：（1）规则集成化，此表可以收集多种疾病在一定病症属性下的诊断规则，可以用此表存储多种疾病的诊断规则。诊断病人可能患有的疾病。（2）应用简单，如果多种疾病规则加入此表，此表可能很大，使用数据库技术操作此表速度影响甚微。（3）规则最简和客观性，此表中的规则都是经过数据挖掘过程得到的，经过了数据预处理，粗糙集属性约简，规则提取和简化，规则的冗余性大大降低，还有规则都是从数据本身的角度出发演算而来，极少带有人为主观性。（4）此表可以同时诊断多种疾病，防止错诊和漏诊。当医生得到病人基本病症和基本检查结果后就可以利用该表进行疾病搜索。搜索出与这些病症有关的疾病。当搜索结果不只一个时，就会使医生对病人所患疾病的考虑范围和考虑角度加大，医生就要辨别病人是患搜索出的疾病中的一种，还是同时患有搜索中的多种疾病。避免医生漏诊疾病，毕竟一人多病的情况多有发生，如果不是病人同时患有多种疾病的情况，也能给医生准确诊断疾病提供大致的辨别方向，大大降低医生检查的盲目性。降低盲目性，就会帮助医生在用其它方法和仪器进一步确诊时缩短确诊疾病的时间。并在检查过程中能针对性选择检查项目，降低过度检查的概率。从医院的角度讲，可以节省医疗资源，避免浪费，从病人的角度讲，可以减少就医成本和就医程序。这是此表的最主要应用。上例中医生就可以同时诊断肺炎和感冒两种疾病，为这两种疾病做针对性检查，快速辨别这两种疾病。5.5.3联合诊断规则表应用不足之处解读对于应用联合诊断决策表的不足之处主要表现为：表中规则生成过程过于客观，完全从数据的角度生成规则，可以加入一些主观因素修正诊断规则，比如加入一些专家经验，会使规则更准确。5.5.4联合诊断规则表面对现实应用分析应用联合诊断规则表诊断疾病虽然具有很多的好处和优势，但我们不能仅仅依靠一张表囊括所有疾病诊断规则信息也不能追求联合诊断规则表中的规则都是能确诊的规则。如果这样必须建立一张极其细致的规则表，规则表中的条件属性须十分细化，必须具有很小的数据粒度，医学中不管是图像还是声音数据都必须数字化，规范化，精细化，对数据要求较高，数据的采集难度十分不易。这张表的建立就是一个很大的难题，工作量繁重巨大。面对这个现实，我们必须放弃对细致规则表的追求，不追求细致精准的诊断规则，放弃在表中建立粒度较小的属性，对某些属性的值进行汇总概化，降低规则数量，生成一个粗糙的联合诊断规则表，粗糙的规则表会降低搜索的精度，降低规则表对疾病的区分能力，但大大降低了规则表的组建难度。我们可以利用粗糙一点的规则表参与疾病的初诊诊断决策支持，用疾病的比较表面化和概化的病状属性作为条件属性，如中医中的对疾病的诊断方法，就是根据“望”，“闻”“问”“切”捕获病人的外表病症表现诊断疾病，建立粗糙一点的规则表，实现大体判定疾病病种，具体确诊需要结合精密的仪器数据和医生的医学经验，这部分往往是数据最难收集的。建立较粗糙的规则表参与疾病的初诊诊断，更具有实际应用可行性。也符合现实生活中45 基于粗糙集理论疾病初步诊断决策支持研究的就医程序(先初诊，再确诊)。5.6本章小结本章是作者的主要工作之一，工作中遵循了数据挖掘的基本过程，运用了数据挖掘技术中的相关内容，文中详细的描述了数据从采集、预处理再到被挖掘的整个过程。以两种疾病的实际病历数据为案例，从建立两种疾病决策表、病症属性约简，得到简化的决策表，从而得到疾病诊断的规则，并简化这些规则，运用这些规则建立联合诊断规则表，参与支持医生疾病初诊决策。在决策表属性约简过程中采用了第四章提出的粗糙集属性约简改进算法，并分析了联合诊断规则表的优势和不足。面对联合诊断规则表可构造的难易程度，分析出联合诊断规则表中的规则不应该追求能确诊疾病，并分析出联合诊断规则表在疾病诊断过程中的应用阶段应该是疾病初诊阶段为好。46 第六章总结和展望第六章总结和展望本文的重点工作是本文的第四章和第五章的内容，在第四章里，针对第五章要涉及的具体医学应用，设计了新的基于条件信息熵的属性约简算法，该算法放弃了求属性的最小约简，而是求属性的所有约简，得到更适合医学应用的规则。并且针对目前属性约简算法实现上存在的实用性、快速、有效性的缺点和不足,提出了一种新的基于SQL语句计算条件信息熵实现属性约简方法，并结合实例说明实现算法的实现过程。将粗糙集的属性约简算法融入到数据库系统当中去，发挥数据库系统的存取效率高、存储空间利用率高、适合大规模数据存储等优点，并发挥数据库查询语言操作大规模数据功能强大的优点。在第五章里，遵循了数据挖掘的基本过程，运用了数据挖掘技术中的相关内容，文中详细的描述了数据从采集、预处理，到被挖掘的整个过程，文中从病历数据中提取病例数据，采集处理了两种疾病的数据，对两种疾病建立决策表，再用第四章提出的粗糙集属性约简改进算法，和实现方法对两种疾病进行病症属性约简，得到简化的决策表，并从决策表中得到疾病诊断的规则，并简化这些规则，运用这些规则建立联合诊断规则表，参与支持医生疾病初诊决策。并分析了应用的联合诊断规则表的优势和不足，并面对实际应用的可实现性，确定了联合诊断规则表的应用方向。然而,由于本文作者能力有限,其研究成效还存在某些不足之处，例如，由于本人是计算机专业，不是医学专业，所以在计算机交叉应用时缺乏一定的医学知识和修养，在疾病数据的预处理阶段可能只站在数据的角度，没有充分考虑医学实际。对于文中提到的改进算法，是从实际应用的角度去改进算法，还需要在更多的具体应用中验证或做更深刻的对比分析。展望下一步工作，在以后的工作里，我希望自己能够多学习一些与计算机交叉学科的内容，使计算机真正能够更好的应用到某些特定的领域，实现计算机技术的真正价值。47 参考文献参考文献[1]范明,孟小峰.数据挖掘:概念与技术[M].北京:机械工业出版社,2001[2]黄慧琳.病案信息资源的开发和利用[J].中国医院统计,2001,8(1)：55-57[3]徐刚,袁兆康.数据挖掘及其在医学领域中的应用和展望[J]．实用临床医学，2006,7(11):196-198[4]丁卫平,祁恒,董建成.基于关联规则的电子病历挖掘算法研究与应用[J].电子学与计算机,2007,24(3):69-73[5]陈雪峰,蔡锋,王静.恶性血液病数据库分析系统的建立[J].第四军医大学学报,2005,25:252-254[6]富春枫,荀鹏程,等.Logitboost及其在判别分析中的应用[J].中国卫生统计,2006,23(2):98-100[7]丁祥武,杨莹.数据挖掘在医学上的应用[J].郧阳医学报,1999,3:130-132[8]刘建波,平振会,袁会珍.聚类分析在小儿脑性瘫痪危险因素分类中的应[J].中华物理医学与康复杂志,2003,25(11):665-667[9]罗森林,张铁梅.知识发现在2型糖尿病数据处理中应用研究[J].计算机工程与应用,2004,40(17):198-201[10]崔雷.医学数据挖掘[M].北京:高等教育出版社,2006,7[11]秦中广,毛宗源.粗糙集在中医类风湿症候诊断中的应用[J].中国生物医学工程学报,2001,20(4):357-363[12]叶明全,姚应水.应用粗糙集差别矩阵筛选医学诊断因子的研究[J].中国卫生统计,2009,26(3):325-327[13]姜淑珍.集合论[M].吉林:吉林大学出版社,2009,3[14]石纯一.数理逻辑与集合论[M].北京:清华大学出版社,2000,12[15]戴牧民,陈海燕,郑顶伟.公理集合论导引[M].北京:科学出版社,2011,6[16]周怡,叶明全,张艳,周金海.医学信息决策与支持系统[M].北京:人民卫生出版社,2009,2[17]桂现才.决策表化简及其属性约简方法[J].计算机工程与设计.2007(08)[18]王国撒.决策表核属性的计算方法[J].计算机学报,2003,26(5):611-615[19]谭建豪,张兢,黄耀,胡章谋.数据挖掘技术[M].北京:中国水利水电出版社,2009,1[20]PawlakZ．Roughsets．IntemationaljournalofinformationandcomputerScience,1982,11(5):341-356[21]PawlakZ.Roughsets.Theoreticalaspectsofreasoningaboutdata,dordrecht.TheNetherlands：KluwerAcademicPublishers,1991,1-168[22]Bonikowskiz，Algebraicstructuresofroughsets.1n：Ziarkow(Ed．)，Roughsets,FuzzySetsandKonwledgeDiscovery,Springer-Verlag．1994,242-247[23]吴静;邹海.基于属性重要性的属性约简算法[J].计算机应用与软件.2010(02)[24]BinHan,Tie-unWu.DataMininginMulti-sensorSystembasedonRoughSetTheory.AmericanControlConference,2001,l(6):4427-4431[25]李同军,张文修,马建敏.基于粗糙集的形式背景属性约简及属性特征．计算48 基于粗糙集理论疾病初步诊断决策支持系统机科学.2006,33(9):178-180[26]邓春燕,吕跃进,李金海.决策表的高效属性约简算法[J].计算机工程与应用.2009(04)[27]刘勇,熊蓉,褚健.Hash快速属性约简算法[J].计算机学报,2009,32(8)：1493-1499[28]王国撒.决策表核属性的计算方法[J].计算机学报,2003,26(5):611-615[29]YangMing,SunZhiHui.ImprovementofDiscernibilityMatrixandtheComputationofaCore[J].JournalofFudanUniversity(NaturalScience),2004,43(5):865-868[30]DuntschI.,GedigaG..UncertaintymeasuresofroughsetPrediction[J].ArtificialIntelligence,1998,106:109-137[31]苗夺谦,王珏.粗糙集理论中概念与运算的信息表示[J].软件学报.1999(02)2[32]徐章艳,刘作鹏,杨炳儒,宋威.一个复杂度为max(O(|C||U|)，O(|C||U／C|)的快速属性约简算法[J].计算机学报,2006,29(3):391-399[33]官礼和;王国胤;于洪.属性序下的增量式Pawlak约简算法[J].西南交通大学学报.2011(03)[34]K.P.SomanShyamDiwakarV.Ajay著范明,牛常勇译.数据挖掘基础教程[M].北京:机械工业出版社,2009.1[35]叶东毅.Jelonek属性约简算法的一个改进[J].电子学报,2000,28(12):81-82[36]HUXiao-hua,CERCONEN.Learninginrelationaldatabases:aroughsetapproach[J].ComputationalIntelligence,1995,11(12):323-337[37]张成江.医学数据仓库与数据挖掘[M].北京:中国中医药出版社,2008.10[38]徐章艳,侯伟,宋威,杨炳儒.一个有效的基于信息熵的启发式属性约简算法[J].小型微型计算机系统.2009(09)[39]刘少辉,盛秋戬,吴斌,等．Rough集高效算法的研究[J].计算机学报,2003，26(5):524-529[40]PawlakZ,WongSKM，ZiarkoW.Roughset:ProbabilisticVersusDeterministic.Approach[J].IntJMan-MachineStudies,1988,29:81-95[41]王国胤,于洪,杨大春.基于条件信息熵的决策表约简[J].计算机学报,2002,25(7):759-766[42]官礼和;王国胤;于洪.属性序下的增量式Pawlak约简算法[J].西南交通大学学报.2011(03)[43]吴子特,叶东毅.一种可伸缩的快速属性约简算法[J].模式识别与人工智能.2009(02)[44]刘文军，谷云龙等．基于区分矩阵求决策算法的约简．北京师范大学学报(自然科学版),2003,39(3):311-315[45]秦奕青,杨炳儒,徐章艳.基于Skowron分明矩阵的有效属性约简算法[J].北京科技大学学报.2009(03)[46]蒋瑜,刘胤田,李超.基于BucketSort的快速属性约简算法[J].控制与决49 参考文献策.2011(02)[47]KryszkiewiczM.Roughsetsapproachtoincompleteinformationsystems.InformationScience,1998.11(2):39-49[48]葛浩,李龙澍,杨传健.改进的快速属性约简算法[J].小型微型计算机系统.2009(02)[49]谭旭.改进分辨矩阵下的增量式条件属性约简算法[J].系统工程理论与实践.2010(09)[51]李南,朱立宇,等.基于粗糙集的数据挖掘技术及其在临床医学诊断中的应用[J].上海生物医学工程,2002,23(2):3-7[52]徐刚,袁兆康.数据挖掘及其在医学领域中的应用和展望[J].实用临床医学,2006,7(11):196-19850 在学研究成果在学研究成果[1]胡宏智，吴俊.嫁接决策树用于相似性疾病诊断研究[J].计算机光盘软件与应用,2012(3):151-15251 致谢致谢时光飞逝，很快三年的硕士学习生活就要结束，铺陈纸笔书写后记，内心不禁涌上感激之情，本次毕业论文的完成，凝聚着多人的关怀和帮助，在此向所有关怀和支持过我的老师，同学和朋友表示诚挚的感谢！首先，我要深深地感谢我的导师胡老师，感谢胡老师三年来对我悉心栽培，鼓舞和催促，胡老师学识渊博，经验丰富,准确把握专业发展的方向，正确引导我开展研究工作。从本论文的开题，研究工作的开展以及论文的撰写修改都是在他的精心指导下完成的。胡老师生活中为人诚恳！平易近人,科研教学工作中治学严谨，勤勉，求实，一丝不苟的工作作风深深地影响了我这个80后，胡老师不仅关注我的研究，还时常传授我做人的道理，是我一生的学习的榜样，这些都会成为我今后人生道路上的重要财富。在以后的人生道路上,我将铭记他的教诲，不断开拓进取，值此论文完成之际,谨向我的导师致以最衷心的感谢!感谢安徽工业大学计算机系的老师们,正是他们扎实的理论知识和丰富的经验，让我顺利完成了理论知识的学习。感谢马鞍山市人民医院信息中心的吴飞主任和王超工程师，正是得到了他们的帮助我才能得到丰富的医学数据，为完成研究打下了坚实的基础。也要感谢我身边的同学们，有了你们使我不孤独，不无助，不失落，你们给我的研究生活带来了无限的乐趣,留下了美好的回忆!感谢各位专家和学者在百忙之中抽出宝贵时间对本论文进行评阅及提出的宝贵意见!特别感谢我的父母和家人给我的关心!爱护和支持!正是他们无私的爱,使我能够专心学习,顺利完成学业!最后,向所有曾经帮助过我的人致以最诚挚的感谢!并送上我最真心的祝福！吴俊2013年3月52