覆盖粒计算及其应用研究 _硕士学位论文.doc

学校代码 10345 研究类型 应用基础研究硕 士 学 位 论 文 题 目: 覆盖粒计算及其应用研究 Research on the Covering and Its Application Based on Granular Computing Research on the Covering and Its ApplicationBased on Granular ComputingThesis Submitted toZhejiang Normal Universityfor the degree ofMaster of EngineeringByShuang Liu(Computer Software and Theory)Thesis Supervisor: Professor Jiyi WangJune, 2011摘 要覆盖粒计算及其应用研究摘 要粒计算是研究基于多层次粒结构的思维方法、问题求解方法、信息处理模式及其相关理论、技术和工具的学科。它覆盖了所有和粒度相关的理论、方法和技术，主要用于对不确定、不准确、不完整信息的处理，对大规模海量的数据和对复杂问题的求解。粗糙集作为粒计算的一个重要分支，在理论和应用上不断取得丰硕成果的同时，也得到了广泛有意义的推广。而覆盖广义粗糙集理论是Pawlak粗糙集理论在划分基础上推广到覆盖建立起来的，它是研究与覆盖相关的理论体系及其应用，由于它是在粗糙集理论上的关系推广，有关粗糙集的一些理论和应用并不一定在覆盖广义粗糙集下适用。因此，本文的主要内容是在粒计算思想理论背景下，研究与覆盖相关的理论及其应用。具体研究工作如下：矚慫润厲钐瘗睞枥庑赖。一、在面向基于粗糙集理论的动态信息系统规则挖掘的研究中，利用覆盖粒计算相关理论提出了一种能消除引起差异信息系统规则挖掘中不一致因素的公理化方法。实验结果表明，在保持时间复杂度不变的情况下，利用改进的规则挖掘算法，通过消除不一致因素而获得的规则能更全面和更大程度地反映条件属性值变化与决策变化趋势之间的内在联系。聞創沟燴鐺險爱氇谴净。二、在面向冲突分析的研究中，在粒计算思想理论背景下，首次提出了“关联冲突”的概念。利用覆盖冲突分析策略,通过“服务资源”实例建立了关联冲突分析的合理泛化模型，讨论了关联冲突过程中所可能引发异常的阶段，并对不同阶段引发的异常进行了详细的分析，给出了具体的解决方案,从而完善了各个领域冲突的解决。残骛楼諍锩瀨濟溆塹籟。三、在面向分类法准确性（单标签和多标签数据集）的研究中，利用拓扑覆盖邻域理论，给出了寻找覆盖系统上重叠元素的相关公理化方法。在粒计算的思维体系背景下，以实例辅证，给出了独立于数据标签和不同理想分类结果假设（一种假设为划分，另一种假设为覆盖）的评价分类法准确性的统一范式，为提高和评估分类法准确性的计算提供了重要的参考意义。酽锕极額閉镇桧猪訣锥。最后，文章是在同一个思想理论背景下，讨论了基于覆盖的相关理论和应用。以上研究工作是覆盖广义粗糙集的理论及其应用的补充和发展，充分的体现出了粒计算背景下知识发现理论和方法的独特性，具有重要的理论意义及潜在的应用价值。彈贸摄尔霁毙攬砖卤庑。 关键词：粒计算；覆盖；动态信息系统；规则挖掘；关联冲突；分类62ABSTRACTRESEARCH ON THE COVERING AND ITS APPLICATION BASED ON GRANULAR COMPUTING謀荞抟箧飆鐸怼类蒋薔。ABSTRACTGranular computing (GrC) is viewed as an interdisciplinary study of computation in nature, society and science, characterized by structured thinking, structured problem solving and structured information processing with an underlying notion of multiple levels of granulation. It consists of all the theories, methodologies, techniques and tools related to the granularity, which is mainly used to deal with uncertainty, imprecise and incomplete information and seek resolutions from the large-scale massive dataset or complicated problem. Rough set, as a very important branch of GrC, is being improving and perfecting on theory and application as well as is being extending widely and significantly. Generalized rough set on covering is the one that partitions Pawlak rough set theory is extended into coverings. It focuses on the study of covering, so that many theories and applications in the Pawlak rough set are not tenable and suitable in the generalized rough set on covering. Therefore, this dissertation will mainly make research on covering theories and its applications under background of GrC, whose content is shown as follows:厦礴恳蹒骈時盡继價骚。First of all, for the rules mining based on rough set theory in dynamic information system, a pre-process approach to eliminate the elements that cause inconsistence of rules mining in difference information system is proposed under the background of covering theory based on granular computing. Experiment shows that relationship between the changes of condition attributes values and trend of decision-making can be fully reflected as much as possible by a modified rules mining algorithm under the same time complexity through this pre-process approach.茕桢广鳓鯡选块网羈泪。Secondly, for the conflict analysis, associated-conflict is firstly introduced in the perspective of GrC, and a reasonable and comprehensive approach to its analysis, using covering based on granular computing, is outlined. We argue that this model of associated-conflict analysis, given by the example of service-resource, will provide more profound insight for the conflict resolution in different fields.鹅娅尽損鹌惨歷茏鴛賴。Thirdly, for the accuracy of classification method on single label dataset or multi label dataset, a unified paradigm for the accuracy used to evaluate different classification methods, using topological covering based on GrC, is presented, independent on number of data labels and different assumptions of ideal classification result(one assumption is partition, the other is covering). And some corresponding examples are also discussed to illustrate the accuracy in different classification situations. This unified paradigm will provide important reference value for the evaluation and improvement of accuracy of classification method.籟丛妈羥为贍偾蛏练淨。In brief, this paper discusses theories and applications related to the covering under the same theory background, and it can be treated as supplement and development of generalized rough set on covering. And it reflects the specificity on theories, methodologies, techniques and tools of knowledge discovery under the background of GrC, with significant referred and applied value in the future.預頌圣鉉儐歲龈讶骅籴。 KEY WORDS: GrC; Covering; Dynamic Information System; Rules Mining; Associated-conflict; Classification渗釤呛俨匀谔鱉调硯錦。目 录目 录摘 要I铙誅卧泻噦圣骋贶頂廡。ABSTRACTIII擁締凤袜备訊顎轮烂蔷。目 录V贓熱俣阃歲匱阊邺镓騷。第一章 绪 论1坛摶乡囂忏蒌鍥铃氈淚。1.1粒计算1蜡變黲癟報伥铉锚鈰赘。1.1.1粒计算提出背景1買鲷鴯譖昙膚遙闫撷凄。1.1.2粒计算任务和目标2綾镝鯛駕櫬鹕踪韦辚糴。1.1.3粒计算基本要素和理论构成2驅踬髏彦浃绥譎饴憂锦。1.1.4粒计算研究方向与方法5猫虿驢绘燈鮒诛髅貺庑。1.1.5粒计算基本思想和实质6锹籁饗迳琐筆襖鸥娅薔。1.2覆盖广义粗糙集理论6構氽頑黉碩饨荠龈话骛。1.2.1覆盖广义粗糙集的研究背景7輒峄陽檉簖疖網儂號泶。1.2.2覆盖广义粗糙集的国内外研究现状8尧侧閆繭絳闕绚勵蜆贅。1.3本文研究的意义、目标、方法和主要内容以及创新点8识饒鎂錕缢灩筧嚌俨淒。1.3.1本文研究的意义8凍鈹鋨劳臘锴痫婦胫籴。1.3.2本文研究的目标8恥諤銪灭萦欢煬鞏鹜錦。1.3.3本文研究的方法9鯊腎鑰诎褳鉀沩懼統庫。1.3.4本文研究的主要内容以及创新点9硕癘鄴颃诌攆檸攜驤蔹。第二章 粒计算的独特魅力11阌擻輳嬪諫迁择楨秘騖。 以孤立点挖掘为例11氬嚕躑竄贸恳彈瀘颔澩。2.1引言11釷鹆資贏車贖孙滅獅赘。2.2引起孤立点的原因12怂阐譜鯪迳導嘯畫長凉。2.3孤立点挖掘方法的思想描述12谚辞調担鈧谄动禪泻類。2.4讨论13嘰觐詿缧铴嗫偽純铪锩。2.5小结15熒绐譏钲鏌觶鷹緇機库。第三章 覆盖粒计算在基于粗糙集的动态信息系统规则挖掘中的应用17鶼渍螻偉阅劍鲰腎邏蘞。3.1引言17纣忧蔣氳頑莶驅藥悯骛。3.2预备知识17颖刍莖蛺饽亿顿裊赔泷。3.3规则挖掘19濫驂膽閉驟羥闈詔寢賻。3.3.1动态信息系统中不一致性的辨识和消除19銚銻縵哜鳗鸿锓謎諏涼。3.2.2规则挖掘算法20挤貼綬电麥结鈺贖哓类。3.4实例分析22赔荊紳谘侖驟辽輩袜錈。3.5小结24塤礙籟馐决穩賽釙冊庫。第四章 基于覆盖粒计算的关联冲突分析26裊樣祕廬廂颤谚鍘羋蔺。4.1引言26仓嫗盤紲嘱珑詁鍬齊驁。4.2预备知识27绽萬璉轆娛閬蛏鬮绾瀧。4.3粒计算背景下的相关工作27骁顾燁鶚巯瀆蕪領鲡赙。4.4粒计算视角下的关联冲突29瑣钋濺暧惲锟缟馭篩凉。4.4.1关联冲突定义30鎦诗涇艳损楼紲鯗餳類。4.4.2关联冲突分析建模30栉缏歐锄棗鈕种鵑瑶锬。4.5讨论37辔烨棟剛殓攬瑤丽阄应。4.6小结39峴扬斕滾澗辐滠兴渙藺。第五章 基于覆盖粒计算的分类准确性研究40詩叁撻訥烬忧毀厉鋨骜。5.1引言40则鯤愜韋瘓賈晖园栋泷。5.2预备知识41胀鏝彈奥秘孫戶孪钇賻。5.3讨论42鳃躋峽祷紉诵帮废掃減。5.3.1理想分类结果假设为划分42稟虛嬪赈维哜妝扩踴粜。5.3.2理想分类结果假设为覆盖44陽簍埡鲑罷規呜旧岿錟。5.4粒计算视角下的分类准确性统一范式45沩氣嘮戇苌鑿鑿槠谔應。5.5多标签数据分类准确性探究47钡嵐縣緱虜荣产涛團蔺。5.6小结50懨俠劑鈍触乐鹇烬觶騮。第六章 总结与展望52謾饱兗争詣繚鮐癞别瀘。6.1总结52呙铉們欤谦鸪饺竞荡赚。6.2展望53莹谐龌蕲賞组靄绉嚴减。参考文献54麸肃鹏镟轿騍镣缚縟糶。攻读硕士学位期间取得的研究成果61納畴鳗吶鄖禎銣腻鰲锬。致 谢62風撵鲔貓铁频钙蓟纠庙。浙江师范大学学位论文独创性声明63灭嗳骇諗鋅猎輛觏馊藹。学位论文使用授权声明63铹鸝饷飾镡閌赀诨癱骝。第一章 绪 论第一章 绪 论1.1粒计算 粒计算（Granular Computing, GrC）是一门飞速发展的新学科，它是由美国学者T.Y.Lin于1997年提出的1。短短十几年的发展已经见证了它对科学特别是计算机科学的作用和影响。诸多国内外学者就粒计算的基本理论和方法做了大量的工作2-12。但为粒计算下一个正式的、精确的、能够广为接受的定义仍然是一件困难的事情。人们对粒计算的描述是建立在对它的直觉认识上的：粒计算是研究基于多层次粒结构的思维方法、问题求解方法、信息处理模式及其相关理论、技术和工具的学科。作为软计算科学的一个重要分支，它覆盖了所有和粒度相关的理论、方法和技术，主要用于对不确定、不准确、不完整信息的处理，对大规模海量的数据和对复杂问题的求解，正逐渐成为人工智能研究领域的热点之一。攙閿频嵘陣澇諗谴隴泸。1.1.1粒计算提出背景研究粒计算有许多原因。其一是一致性：现实世界充满了结构和层次，它们体现在各种自然系统、社会系统和人工系统之中。因此，人们对现实世界的感知、理解、解释和表示也是有结构、分层次的。Zadeh将人类的认知能力概括为：粒化、组织和因果推理13。粒化是将一个整体分割成部分，每个部分是拥有相同、相似性质的个体的集合。组织是将松散的个体联系在一起，形成有着内在联系的整体。因果推理是找出原因与结果之间的必然联系。粒计算模型应该能描述这三种能力。因而粒计算的结构和现实世界的结构、人们的思维模式及行为方式是一致的。其二是系统性：粒计算的结构提供了对所解决的问题多视角、多层次的理解、概括和操作。作为一个整体，粒计算提供的思维模式和行为方式是系统的、完整的。其三是简化性：粒计算是提倡对问题进行不同层次的抽象和处理。在抽象过程中，可以只重视主要特性而忽略不相关的细节，从而达到对问题的简化。其四是灵活性：粒计算的结构允许人们在不同的时间、不同的情况下，将注意力集中在不同的层次及层与层之间的自然过渡上，缩放和转承是灵活多变的。其五是有效性：用粒计算指导的思维模式和行为方式将复杂问题分解成若干小问题。这种分而治之的方法是非常实用的，可以运用到不同的领域。其六是经济性：粒计算寻求在不同粒度上的近似解。这样的方法可以提高效率、降低成本。其七是容忍性：通过使用不同信息粒度，粒计算可以容忍不确定、不完全或有噪音的信息，从而获得具有鲁棒性的解决方案。趕輾雏纨颗锊讨跃满賺。1.1.2粒计算任务和目标粒计算的形成综合了许多学科的科研成果14，它的理论建立在对各个领域的共性进行概括、总结和整理之上，形成了对问题求解的普遍适用的原理、方法和策略。在过去的若干年中，许多学者对粒计算的具体模式和方法进行了研究。同时和粒计算原理相似的研究还在不断地出现，只是在不同的领域中运用了略微不同的名词和术语。将粒计算作为一个独立的学科研究可以防止这种不必要的重复劳动。夹覡闾辁駁档驀迁锬減。 (1) 粒计算的任务作为一个新兴的研究领域，粒计算是一门关于问题求解的艺术。它有着两项特殊的任务：其一是从各个不同的领域中概括出它们的共性，不考虑它们低层次上的差异，从而提炼出抽象的、高层次的、综合的认识；其二是将特定领域中隐含的结构明确化，以期总结出独立于具体领域的普遍原理。视絀镘鸸鲚鐘脑钧欖粝。 (2) 粒计算的目标粒计算之所以新且独特，并不完全在于一组具体的方法和策略，而在于提出一个统一的框架，对这些方法和策略进行全面的理解及综合。通过对粒计算的研究试图达到以下目标：将隐式的结构显式化；将不明显的原理明显化；将特定领域的特殊原理普遍化；将下意识的行为变成有意识的行为。偽澀锟攢鴛擋緬铹鈞錠。1.1.3粒计算基本要素和理论构成 (1) 粒计算的基本要素14, 15 (a) 粒粒是粒计算的初始概念，是粒计算研究对象的单位，是求解问题的基本单位，等同于数据库中的记录，集合中的元素或子集。我们称最小的、不可分或不需要再分解的粒为基本粒，即最低层次的粒称为基本粒，它可以是模糊的，也可以是精确的。緦徑铫膾龋轿级镗挢廟。粒具有双重身份，它可以是某个整体中相对独立的一个部分，也可以是一些粒共同组成的一个粒。所有的粒都具有内在属性、外在属性和环境属性。当粒作为整体时，所要考虑的是粒的内在属性，内在属性由粒所拥有的元素决定。当粒作为部分时，所要考虑的是粒的外在属性，由于具有外在属性，粒就能够被人们直接认识。粒的环境属性是指粒对外部环境变化的应对情况，对其内在属性和外在属性的保持与调整以及对外部环境的影响和回应。粒的双重身份决定了它的内在属性通常需要强调其它所包含的细小个体的不同特性，是对它内部各个基本组成成分性质的描述，而其外在属性则是强调把它作为一个整体时所体现出的综合特性。騅憑钶銘侥张礫阵轸蔼。 (b) 层次粒存在于特定的层次中，人们在粒计算的不同层次中研究不同类型的粒，这些粒之间是有联系的，同一层次的粒与粒之间可以是相交的关系也可以是层叠的关系，它们是该层次上研究的主体。层次中每一个粒表述了一个特定的粒化观点。所有的粒化观点相互补充、相互呼应，完整表达了在这个层次上对同一个问题的描述。每个层次都具有内在属性、外在属性、环境属性，同一层次的粒属性共同体现本层次特性。疠骐錾农剎貯狱颢幗騮。 在问题求解中，选择在最合适的粒度层次上产生对一个问题的描述，能帮助更好更快地解决问题。较高层次包含较低层次，或者由较低层次组成。较高层次为较低层次提供背景和约束。较高层次一般由较高集成度和较高结合力的粒组成。每一层次都存在一定程度的独立性。任意两层次之间的连接和交互是通过偏序关系的传递性和桥接原理来表示和体现的。粒计算模型的主要作用是能够在不同粒度层次上进行问题求解，使不同粒度层次上的解能够进行相互转化。镞锊过润启婭澗骆讕瀘。 (c) 分层结构 分层结构由若干个层次组成，层次间的递进反映了由表及里、由抽象到具体、由粗糙到细致、由笼统到具体的变化。这种递进是有序的，高层次会对低层次进行约束，并为低层次的描述提供背景。一个高层次的粒可以分解为若干个低层次的粒。相反，若干个低层次的粒可以组合成一个高层次的粒。低层次的粒为高层次的粒提供更详细的描述或者更多的信息。另一个方面，高层次的粒将与本层次的不相关的细节忽略掉，为低层次的粒提供更粗粒度的描述。榿贰轲誊壟该槛鲻垲赛。 (d) 粒结构在粒计算研究中强调的是全面、整体的观点，而不是局部、离散的观点。若要达到该目标，不仅要考虑一个分层结构中的多个层次，还需要将多个分层结构综合考虑。粒结构包括三个要素，即粒的内在结构、粒的结构、粒的总体结构，它是多层次和多个分层结构的结合。邁茑赚陉宾呗擷鹪讼凑。粒计算借助于其他学科的哲学思想和方法论，并将它们抽象成为与具体领域无关的方法和策略。它的独特性体现在用系统的、结构化的理解和方法来解决复杂问题。对复杂问题的全面理解通常是多视角的，从每一个视角着眼的理解又是多层次的。由此可以得出，粒计算的过程就是对复杂问题的求解过程。它的结果表现为一个多视角、多层次的粒结构。这个粒结构是对复杂问题的系统且近似的描述和解答。嵝硖贪塒廩袞悯倉華糲。 (2) 粒计算的理论构成7, 8 目前，粒计算有3个主要理论以及其它一些非主流理论：其一是词计算理论：人类思考、判断、推理主要是用语言，而语言是一个很粗的粒，如何用语言进行推理判断，这就是词计算。其二是商空间理论：商空间理论把概念用子集表示，不同粒的概念体现为不同粒的子集，一簇概念构成空间的一个划分商空间，不同的概念簇就构成了不同的商空间。故粒计算，就是研究在给定知识基上的各种子集合之间的关系和转换，以及对同一问题取不同的适当的粒，从对不同的粒的研究中，综合获取对原问题的了解。其三是粗糙集理论：粗糙集理论于1982年由Pawlak提出，它是一种刻划不完整性、不确定性的数学工具，主要解决信息粒的近似方面的问题。另外许多学者也在研究粒计算，并将各种相关理论用于粒计算，有邻域系统粒计算、信息熵粒计算、概念格粒计算、覆盖粒计算、进化粒模型、基于相容粒度空间的粒计算模型以及各模型相互交叉整合的模型方法等，在许多领域中得以实现或应用。该栎谖碼戆沖巋鳧薩锭。1.1.4粒计算研究方向与方法粒计算的形成和发展积累了多种思想、模型、范式、方法论、技术及工具。对粒计算的研究应该着眼于三个观点2：粒计算的哲学思想观点、方法论观点及计算模式观点。从哲学思想观点考虑，粒计算试图将人类的认知方式抽象化、形式化，从而提炼出结构化的思维模式，而结构化的思维模式是人类智能的重要体现，它对设计基于知识的信息系统有着非常重要的影响，它有两个基本假设：一个是所有问题都可以视作是其内在要素之间的网络状或分层结构的关联，另一个是所有的问题都有着类似的模式和特征；从方法论观点考虑，粒计算着重研究系统化的方法和技术，将问题求解的过程规范为结构化的、自上而下的逐步求精过程；从计算模式观点考虑，粒计算关注于结构化的信息处理。信息处理是有层次的，其研究领域涉及抽象的信息处理、人脑中的信息处理及计算机中的信息处理。计算模式是方法论的具体表现形式。在计算机学科中，人们通常将兴趣集中在基于计算机的信息处理模型上，并将其独立出来进行分析。劇妆诨貰攖苹埘呂仑庙。粒计算的哲学研究基于粒结构的思维方式。基本问题7, 10, 15包括：如何定义粒、层次及分层结构的内在属性、外在属性和环境属性；如何定义它们的关系；如何准确表达它们的关系；如何实现它们的关联和切花；如何使它们的综合功能最大化。哲学层面的研究是抽象的，同时又是方法论和计算模式的前提和保障。臠龍讹驄桠业變墊罗蘄。粒计算的方法论致力于将粒计算哲学思想具体到问题求解的方法、技术和工具的研究和开发中去。需要考虑到粒计算方法的有效性、可靠性、准确性、简便性、计算成本和价值。对于不同的应用还需考虑其问题的特定及限制。鰻順褛悦漚縫冁屜鸭骞。粒计算的信息处理强调以计算机为主体的信息处理与以人为主体的信息处理的差别。一方面，以计算机为主体的信息处理依靠人来制定、设计、实施和优化；另一方面，计算机的信息处理也促进方法论的研究。粒计算的哲学思想和方法论的完善为计算机的信息处理实践提供了可以依据的准绳和保障，计算机的信息处理实践反过来也会促进对粒计算哲学思想和方法论的研究，成为支持粒计算哲学思想的有力证据和改善粒计算方法论的原动力。穑釓虚绺滟鳗絲懷紓泺。总之，如何定义粒（粒化）以及如何选择合适的粒度是粒计算解决问题的首要任务6, 9。1.1.5粒计算基本思想和实质粒计算从不同粒层次上研究问题，从人类求解问题的经验方法中提取基本原理如粒、层次、等级。从人类思考和求解问题上看，“人类以粒的观点看世界”，“人们观察、衡量、概括和推理的实体都是粒”16。当人们面对复杂的、难于准确把握的问题时由于能力有限，通常不是采用系统、精确的方法去追求问题的最优解，而是通过逐步尝试的办法达到有限的、合理的目标，也就是采用由粗到细、不断求精的多粒度分析法，避免复杂的计算，从而获得足够满足的解，使得原来看似非多项式的难解问题迎刃而解。人类智能的一个公认特点，就是人们能从极不相同的粒上观察和分析同一问题。人们能在不同粒的世界上进行问题求解，且能够很快地从一个粒世界跳转到另一个粒世界，往返自如，毫无困难。这种处理不同粒世界的能力，正是人类问题求解的强有力的表现，这也正是粒计算的基本思想4。粒计算方法是人工智能领域中的一种新理念和新方法，它覆盖了所有和粒度相关的理论、方法和技术，在可以容忍的程度内，主要用于对不确定、不准确、不完整信息的处理，对大规模海量的数据和对复杂问题的求解，使其达到可处理性、鲁棒性、小代价和谐调性。粒计算的实质4就是通过选择合适的粒度，来寻找一种较好的、近似的解决方案，从而降低问题求解的难度。隶誆荧鉴獫纲鴣攣駘賽。而事实上，从真实世界上看，许多自然系统、社会系统、人工系统都是基于层次的，粒计算可以真实自然地表示这类系统。从简化问题上看，多层系统的不同层次关注不同的粒特征，粒计算忽略了不必要和不相关的细节，只关注适当层次，从而简化了问题。从实用角度上看，许多问题是不完整的、不确定的，或者含有模糊信息，很难区分元素，只能认为是粒。且在许多实际问题中也不要求精确解，或者获取精确信息的代价不菲，粒计算可以提高效率和降低代价。浹繢腻叢着駕骠構砀湊。1.2覆盖广义粗糙集理论定义1.117 设是非空有限论域，是上的一簇子集且，对于任意，如果，那么为的一个划分。定义1.233 设是非空有限论域，是上的一簇子集，如果中任一子集非空且，则为的一个覆盖。1.2.1覆盖广义粗糙集的研究背景随着计算机及网络的日益普及，丰富的数据与贫乏的知识之间的矛盾日渐突出。不同领域的人都希望能从复杂的数据中得到自己所需要的知识，因此数据挖掘这门学科就应运而生了。该学科涉及分类、概念形成和数据分析。这些都需要对不完全和不充分的信息进行处理，围绕这个问题产生了许多理论，如模糊理论、神经网络、商空间理论、词计算、粗糙集理论等。而其中的粗糙集理论17于20世纪80年代提出以来，无论从理论上还是从应用上都取得了丰硕的成果，尤其在数据挖掘领域里18。它是通过不可区分关系为不完全和不充分信息的处理提供了一套系统的方法。通常，人们用一组属性来描述事物，不可区分关系就是由这些事物相应的属性值来定义的。如果两个事物对于这组属性的属性值相等，也就是说具有相同的描述，就认为它们是不可区分的。从集合中关系这个角度来看，这种不可区分关系实际上就是等价关系。这样，所有具有相同描述的事物构成一个等价类，而所有的等价类构成所考虑事物的一个划分。在粗糙集理论中，这些等价类又称为初等集，若干个初等集的并称为确定。利用这个划分，任意的事物的集合可以用两个确定集来上下逼近，这两个确定集分别是该事物集合的上近似和下近似。它无需提供问题所需处理的数据集合之外的任何先验信息，对问题的不确定性的描述或处理是比较客观的。由于这个理论未包含处理不精确或不确定原始数据的机制，所以与概率论、模糊数学和证据理论等其他处理不确定或不精确问题的理论有很强的互补性。鈀燭罚櫝箋礱颼畢韫粝。 而随着粗糙集理论得到广泛的应用以来，为使该理论能有更大的应用空间，人们对Pawlak粗糙集理论进行了许多有意义的推广，如将等价关系放宽为相容关系19、相似关系20、一般二元关系21；与模糊理论结合，将粗糙集理论推广到模糊粗糙集理论22和广义模糊粗糙集理论23；将经典粗糙集模型推广到变精度粗糙集模型24；从等价关系等同于划分这个角度出发，Zakowski把划分放宽为覆盖25,将Pawlak粗糙集理论推广到覆盖广义粗糙集理论。惬執缉蘿绅颀阳灣熗鍵。1.2.2覆盖广义粗糙集的国内外研究现状 然而，自从Pawlak粗糙集理论被推广到覆盖广义粗糙集理论之后，国内外学者对其做了大量的研究。文献26-53, 54-58对覆盖广义粗糙集理论进行了深入研究，其中文献30讨论了覆盖广义粗糙集的近似算子，文献29主要研究覆盖上下近似运算分别成为Kuratowski闭包和内部运算的充分必要条件，文献27-28主要研究了覆盖广义粗糙集中一阶集合运算，文献26主要结合形式概念分析来研究覆盖广义粗糙集，文献31, 53讨论了广义粗糙集理论的代数结构，文献49, 57对基于关系的广义粗糙集进行了研究，文献33, 43, 44, 54, 56对在覆盖广义粗糙集理论下的约简和不确定性度量进行了研究，文献34-36, 39, 41-42, 45-48, 51, 58对覆盖广义粗糙集理论中的上下近似运算进行了公理化的研究，文献38, 40, 52分别对覆盖广义粗糙模糊集和拓扑相关性质进行了研究，而文献60-63对变精度的覆盖广义粗糙集理论及其模型进行了研究，以及其他的一些有关覆盖广义粗糙集理论的研究和总结32, 50, 55, 59。就应用方面而言，覆盖广义粗糙集理论已应用于冲突分析37、信息检索64等领域。贞廈给鏌綞牵鎮獵鎦龐。1.3本文研究的意义、目标、方法和主要内容以及创新点1.3.1本文研究的意义 由于覆盖广义粗糙集理论是将Pawlak粗糙集理论在划分基础上推广到覆盖而建立起来的，而覆盖广义粗糙集理论主要研究与覆盖相关的理论体系及应用，所以有关粗糙集一些理论和应用并不一定在覆盖广义粗糙集下适用，那么在粒计算思想理论背景下研究覆盖广义粗糙集的相关理论和应用就显的十分有意义。嚌鲭级厨胀鑲铟礦毁蕲。1.3.2本文研究的目标 虽然覆盖广义粗糙集有了一定的理论基础和应用领域，但与粗糙集相比，需要不断丰富其理论基础和应用领域，而继续建立覆盖近似运算公理化理论体系、覆盖约简及近似性度量和不断寻求覆盖广义粗糙集的适用方向是进一步研究的具体目标，本文旨在对覆盖广义粗糙集的应用基础进行研究。薊镔竖牍熒浹醬籬铃騫。1.3.3本文研究的方法、技术路线及可行性分析本文将采用由浅入深、并行开展的研究方法。首先，介绍了粒计算思想理论体系的新颖性以及独特性以孤立点挖掘为例。其次，在粒计算思想理论体系下，利用覆盖相关理论分别对基于粗糙集的动态信息系统规则挖掘、关联冲突分析、分类准确率三个方面进行独立研究。齡践砚语蜗铸转絹攤濼。 (1) 在基于粗糙集的动态信息系统规则挖掘中的应用研究中，主要利用条件属性和决策属性的交叉一致性来寻找引起差异信息系统中的不一致因素，然后利用改进的规则挖掘算法通过实验对比来实现。绅薮疮颧訝标販繯轅赛。(2) 在面向冲突分析的研究中，将冲突看作是在不同结构层上的粒化过程，提出关联冲突的概念，给出其形式化的定义，然后并对其进行分析和建模，最后给出关联冲突过程中所可能引发异常的阶段，将对不同阶段引发的异常进行详细的分析饪箩狞屬诺釙诬苧径凛。(3) 在面向分类准确性研究中，利用拓扑覆盖邻域理论来寻找覆盖系统上重叠元素，然后在粒计算的思维体系背景下，以实例辅证，采用折中方式给出独立于数据标签和理想分类结果假设的评价分类法准确性的统一范式。烴毙潜籬賢擔視蠶贲粵。 以上提出的研究方法和技术路线是在前人对覆盖广义粗糙集理论和应用以及相应领域研究基础上的再探索。虽然涉及领域比较宽泛，但都是在粒计算背景下研究的与覆盖相关的理论和应用，所以本文实施和所采用的技术路线是可行的。鋝岂涛軌跃轮莳講嫗键。1.3.4本文研究的主要内容以及创新点本文主要是在粒计算的思想理论背景下研究与覆盖相关的理论及其应用。具体包括以下六章内容： 第一章为绪论。首先介绍了粒计算的相关理论知识；然后介绍了覆盖广义粗糙集的研究背景，分析了国内外研究现状；最后介绍了本文的研究意义、目标、方法和主要内容以及创新点。撷伪氢鱧轍幂聹諛詼庞。 第二章为粒计算的独特魅力。本章主要讨论了粒计算的新颖性和独特性以孤立点挖掘为例，创新性地给出了孤立点挖掘总的指导原则和具体实施的流程图，为孤立点挖掘算法的选择、改进和创新提供了实际的参考价值，以此来揭示粒计算的独特思维模式和研究方法，进而体现本文的写作意图即受粒计算思想与理论的影响，获取与覆盖相关的创新思想来源。踪飯梦掺钓貞绫賁发蘄。 第三章为覆盖粒计算在基于粗糙集的动态信息系统规则挖掘中的应用研究。本章针对差异信息系统构造过程中会引起新的不一致这个问题，利用覆盖粒计算相关理论提出了一种新的能消除这种不一致因素的公理化方法。实验结果表明，在保持时间复杂度不变的情况下，利用改进的规则挖掘算法，通过消除不一致因素而获得的规则更全面和更大程度地反映了条件属性值变化与决策变化趋势之间的内在联系。婭鑠机职銦夾簣軒蚀骞。 第四章为基于覆盖粒计算的关联冲突分析。本章在粒计算思想理论背景下，首次提出了“关联冲突”的概念，利用覆盖冲突分析策略,通过“服务资源”实例建立了关联冲突分析的合理泛化模型，讨论了关联冲突过程中所可能引发异常的阶段，并对不同阶段引发的异常进行了详细的分析，给出了具体的解决方案。譽諶掺铒锭试监鄺儕泻。 第五章为基于覆盖粒计算的分类准确性研究。在面向分类法准确性（单标签和多标签数据集）的研究中，本章利用拓扑覆盖邻域理论，给出了一种新的寻找覆盖系统上重叠元素的相关的公理化方法。在粒计算的思维体系背景下，以实例辅证，创新性地给出了独立于数据标签和理想分类结果假设（一种假设为划分，另一种假设为覆盖）的评价分类法准确性的统一范式。需要说明的是，本章对于分类法准确性统一范式的给出采取的折中处理方式值得借鉴。俦聹执償閏号燴鈿膽賾。 第六章为总结与展望。文章在同一个思想理论背景下，讨论了基于覆盖的相关理论和应用，它是覆盖广义粗糙集的理论及其应用的补充和发展，并且更体现出了粒计算背景下知识发现理论和方法的独特性，具有重要的理论意义及潜在的应用价值，同时对该领域理论和应用研究的发展方向提出了新的展望。缜電怅淺靓蠐浅錒鵬凜。 此外，本文收录了一些该领域内最新的研究成果，以期能为科研工作者认识和深入研究提供便利。第二章 粒计算的独特魅力第二章 粒计算的独特魅力 以孤立点挖掘为例 本章主要讨论粒计算的新颖性和独特性，以此来揭示粒计算的独特思维模式和研究方法，从中体现出本文的写作意图，在粒计算思想理论背景下的覆盖理论及其研究的问题即受粒计算思想与理论的影响，获取与覆盖相关的创新思想来源。以孤立点挖掘为例，在粒计算的思想理论背景下，给出了孤立点挖掘总的指导原则和具体实施的流程图，为孤立点挖掘算法的选择、改进和创新提供了实际的参考价值，将会对孤立点的挖掘产生一定深远的影响。骥擯帜褸饜兗椏長绛粤。2.1引言孤立点也即异常点65，是指数据集中不符合一般模型的那些对象，即和其他数据有着不同的性质。对于某些度量而言，这些对象与数据集中的其他数据有着显著的不同。目前，针对不同的数据挖掘任务和挖掘背景，一些数据挖掘算法尽量去减少孤立点带来的影响或者甚至是从数据集中消除他们，然而，这可能会导致一些重要的隐秘信息的缺失。换句话说，孤立点本身在诸如入侵检测等事件中有着特殊的意义，它可以表示入侵的异常行为。因此，孤立点的检测和分析（即孤立点挖掘）在数据挖掘中就显得非常重要。一般，孤立点挖掘问题可以看作两个子问题：一个是在给定的数据集中定义一个什么样的数据可以被认为是孤立点或不一致的；另一个是找到一个有效的方法去挖掘这些定义的孤立点。癱噴导閽骋艳捣靨骢鍵。在过去的一个多世纪里，人们对孤立点的研究经历了几个兴衰交替。现在，它再一次成为信息科学里的一个活跃分支，并在数据挖掘领域里受到越来越广泛的关注。孤立点挖掘之所以有着广泛的应用，是与其所在的实际领域里的特殊性决定，诸如入侵检测、市场营销和医疗等领域。孤立点的引起是有一些原因的66，同时相应的也有一些检测或挖掘孤立点的方法67-76。然而，每种方法总是存在着不可避免的缺点或者略势，没有一个普遍有效的方法来检查数据集中的孤立点77。特别在检测孤立点的过程中，如何选择一个合适的检测方法没有一个普遍的准则，而且就孤立点目前研究的热点和未来的发展来说77，挖掘任务会变得非常困难。因此，寻求一个适用于孤立点挖掘的总的指导原则就成为了最急需要解决的问题。鑣鸽夺圆鯢齙慫餞離龐。2.2引起孤立点的原因 (1) 数据来自不同的类 一个数据不同于其他数据，可能因为它来自不同的类或属于不同的类型。例如，一个在进行信用卡欺诈的人可能被归为不合法的信用卡用户而不是非法的用户。相同地，诸如欺诈、入侵、疾病暴发和异常的实验结果等都可以被认为是造成孤立点的例子。榄阈团皱鹏緦寿驏頦蕴。 (2) 自然变异在统计知识的背景下，一些诸如正太分布等模型可以用来模拟许多数据集的分布。随着数据点离正太分布的中心距离的增加，该点出现的可能性就会急剧地减少。换句话说，对于大多数点来说，离中心（平均对象）越近，不同于这个平均对象的可能性就越小。例如，假定一个男性特别的高，当他独自一人时，没有人与之形成对比，他没有什么特别之处。但是一旦于其他人在高度上做比较时，他就是一个孤立点，在这群人里他是一个高度上的极值。通常这些极值点或没有任何变异的点作为孤立点是非常有意思的。逊输吴贝义鲽國鳩犹騸。 (3) 数据度量和收集导致的误差 在数据收集和度量的过程中，所导致的误差是引起孤立点的另一个根源。例如，由于人为失误、设备误差或者数据本身具有噪音导致所记录的度量值不正确。一般情况下都会删除这些孤立点，因为他们不能提供有用的信息，相反他们会降低数据分析的质量。但这些数据能反映出一些有用的信息，例如误差的根源是人为、设备还是其他的原因造成的等。幘觇匮骇儺红卤齡镰瀉。2.3孤立点挖掘方法的思想描述 (1) 基于统计模型的孤立点检测方法67, 68许多检测技术首先都会构造一个数据模型。孤立点就是这些不能够很好拟合这个模型的数据对象。例如，数据的分布模型可以通过估计概率分布的参数来构造。如果一个数据对象不能够很好的拟合这个模型，它可能不服从这个分布，那它就是孤立点。如果模型是簇的集合，那么孤立点会明显的不属于任何簇。或者当使用回归模型时，孤立点会相对的远离模型的预测值。誦终决懷区馱倆侧澩赜。 (2) 基于距离的孤立点检测方法69, 70目前，许多孤立点检测的方法都是基于距离的。孤立点就是远离大多数点的点。当数据分散在二维或三维的图中时，我们可以通过基于距离的方法，用肉眼或简单方法分辨出哪些点是孤立点。医涤侣綃噲睞齒办銩凛。 (3) 基于偏差的孤立点检测方法71, 72我们也可以通过比较一组数据的主要特征来检测孤立点。根据问题的要求，可以事先给定数据所对应的一些特征，那么孤立点就是这些不能像特征所描述的那样的点。舻当为遙头韪鳍哕晕糞。 (4) 基于密度的孤立点检测方法73, 74数据分布的密度估计是相对可以通过计算得到的，尤其是对数据之间存在距离的点来说。那些处于低密度的数据点相对地远离他们的邻居可以被认为是孤立点。但是考虑到数据集可能有不同的密度区域，因此当一个点所在的区域的密度明显低于它的大多数邻居的时候，它可以被归为孤立点。鸪凑鸛齏嶇烛罵奖选锯。 (5) 基于聚类的孤立点检测方法75, 76聚类分析和孤立点检测有不同的目标。聚类分析通常被用于发现强相关的对象，而孤立点检测则被用来发现那些和强相关的对象没有关系的对象。显然，聚类可以用于孤立点检测。筧驪鴨栌怀鏇颐嵘悅废。2.4讨论 在数据挖掘中，粒计算有着广泛的应用78-80。数据的粒化，尤其是复杂数据的粒化，是基于粒计算的数据挖掘的必要前提。粒化的程度直接影响数据挖掘的效率和计算复杂度。既要避免粒度过粗而造成求解失败，又要避免粒度过细造成信息的冗余而导致求解效率低下。因此，选择最优粒化程度是粒计算数据挖掘的关键。另外，当粒化的程度已知时，粒化的方法直接决定了粒化的效率。韋鋯鯖荣擬滄閡悬贖蘊。孤立点挖掘是一个将孤立点从数据集中分离出来的过程。通过对引起孤立点的原因进行分析，我们发现孤立点大都是各种情况里的不寻常的对象。他们由突发事