硕士学位论文

学校代码 10345 研究类型 应用基础研究

硕 士 学 位 论 文

题 目: 覆盖粒计算及其应用研究 Research on the Covering and Its Application Based on Granular Computing

学 科 专 业: 年 级: 学 号: 2007210466 研 究 生: 指导教师: 中图分类号: TP301.4 论文提交时间: 2011 年 6 月 日

Research on the Covering and Its Application

Based on Granular Computing

Thesis Submitted to

Zhejiang Normal University

for the degree of Master of Engineering

By Shuang Liu

(Computer Software and Theory) Thesis Supervisor: Professor Jiyi Wang

June, 2011

覆盖粒计算及其应用研究

摘 要

粒计算是研究基于多层次粒结构的思维方法、问题求解方法、信息处理模式及其相关理论、技术和工具的学科。它覆盖了所有和粒度相关的理论、方法和技术，主要用于对不确定、不准确、不完整信息的处理，对大规模海量的数据和对复杂问题的求解。粗糙集作为粒计算的一个重要分支，在理论和应用上不断取得丰硕成果的同时，也得到了广泛有意义的推广。而覆盖广义粗糙集理论是Pawlak粗糙集理论在划分基础上推广到覆盖建立起来的，它是研究与覆盖相关的理论体系及其应用，由于它是在粗糙集理论上的关系推广，有关粗糙集的一些理论和应用并不一定在覆盖广义粗糙集下适用。因此，本文的主要内容是在粒计算思想理论背景下，研究与覆盖相关的理论及其应用。具体研究工作如下：

一、在面向基于粗糙集理论的动态信息系统规则挖掘的研究中，利用覆盖粒计算相关理论提出了一种能消除引起差异信息系统规则挖掘中不一致因素的公理化方法。实验结果表明，在保持时间复杂度不变的情况下，利用改进的规则挖掘算法，通过消除不一致因素而获得的规则能更全面和更大程度地反映条件属性值变化与决策变化趋势之间的内在联系。

二、在面向冲突分析的研究中，在粒计算思想理论背景下，首次提出了“关联冲突”的概念。利用覆盖冲突分析策略,通过“服务—资源”实例建立了关联冲突分析的合理泛化模型，讨论了关联冲突过程中所可能引发异常的阶段，并对不同阶段引发的异常进行了详细的分析，给出了具体的解决方案,从而完善了各个领域冲突的解决。

三、在面向分类法准确性（单标签和多标签数据集）的研究中，利用拓扑覆盖邻域理论，给出了寻找覆盖系统上重叠元素的相关公理化方法。在粒计算的思维体系背景下，以实例辅证，给出了独立于数据标签和不同理想分类结果假设（一种假设为划

I

摘 要

分，另一种假设为覆盖）的评价分类法准确性的统一范式，为提高和评估分类法准确性的计算提供了重要的参考意义。

最后，文章是在同一个思想理论背景下，讨论了基于覆盖的相关理论和应用。以上研究工作是覆盖广义粗糙集的理论及其应用的补充和发展，充分的体现出了粒计算背景下知识发现理论和方法的独特性，具有重要的理论意义及潜在的应用价值。

关键词：粒计算；覆盖；动态信息系统；规则挖掘；关联冲突；分类

II

RESEARCH ON THE COVERING AND ITS APPLICATION

BASED ON GRANULAR COMPUTING

ABSTRACT

Granular 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 partition’s Pawlak rough set theory is extended into covering’s. 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

III

ABSTRACT

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

IV

目 录

摘 要 ............................................................................................................................ I ABSTRACT ................................................................................................................ III 目 录 .......................................................................................................................... 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

V

目 录

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

VI

第一章 绪 论

1.1粒计算

粒计算（Granular Computing, GrC）是一门飞速发展的新学科，它是由美国学者T.Y.Lin于1997年提出的[1]。短短十几年的发展已经见证了它对科学特别是计算机科学的作用和影响。诸多国内外学者就粒计算的基本理论和方法做了大量的工作[2-12]。但为粒计算下一个正式的、精确的、能够广为接受的定义仍然是一件困难的事情。人们对粒计算的描述是建立在对它的直觉认识上的：粒计算是研究基于多层次粒结构的思维方法、问题求解方法、信息处理模式及其相关理论、技术和工具的学科。作为软计算科学的一个重要分支，它覆盖了所有和粒度相关的理论、方法和技术，主要用于对不确定、不准确、不完整信息的处理，对大规模海量的数据和对复杂问题的求解，正逐渐成为人工智能研究领域的热点之一。

1.1.1粒计算提出背景

研究粒计算有许多原因。其一是一致性：现实世界充满了结构和层次，它们体现在各种自然系统、社会系统和人工系统之中。因此，人们对现实世界的感知、理解、解释和表示也是有结构、分层次的。Zadeh将人类的认知能力概括为：粒化、组织和因果推理[13]。粒化是将一个整体分割成部分，每个部分是拥有相同、相似性质的个体的集合。组织是将松散的个体联系在一起，形成有着内在联系的整体。因果推理是找出原因与结果之间的必然联系。粒计算模型应该能描述这三种能力。因而粒计算的结构和现实世界的结构、人们的思维模式及行为方式是一致的。其二是系统性：粒计算的结构提供了对所解决的问题多视角、多层次的理解、概括和操作。作为一个整体，粒计算提供的思维模式和行为方式是系统的、完整的。其三是简化性：粒计算是提倡

1

第一章 绪 论

对问题进行不同层次的抽象和处理。在抽象过程中，可以只重视主要特性而忽略不相关的细节，从而达到对问题的简化。其四是灵活性：粒计算的结构允许人们在不同的时间、不同的情况下，将注意力集中在不同的层次及层与层之间的自然过渡上，缩放和转承是灵活多变的。其五是有效性：用粒计算指导的思维模式和行为方式将复杂问题分解成若干小问题。这种分而治之的方法是非常实用的，可以运用到不同的领域。其六是经济性：粒计算寻求在不同粒度上的近似解。这样的方法可以提高效率、降低成本。其七是容忍性：通过使用不同信息粒度，粒计算可以容忍不确定、不完全或有噪音的信息，从而获得具有鲁棒性的解决方案。

1.1.2粒计算任务和目标

粒计算的形成综合了许多学科的科研成果[14]，它的理论建立在对各个领域的共性进行概括、总结和整理之上，形成了对问题求解的普遍适用的原理、方法和策略。在过去的若干年中，许多学者对粒计算的具体模式和方法进行了研究。同时和粒计算原理相似的研究还在不断地出现，只是在不同的领域中运用了略微不同的名词和术语。将粒计算作为一个独立的学科研究可以防止这种不必要的重复劳动。 (1) 粒计算的任务

作为一个新兴的研究领域，粒计算是一门关于问题求解的艺术。它有着两项特殊的任务：其一是从各个不同的领域中概括出它们的共性，不考虑它们低层次上的差异，从而提炼出抽象的、高层次的、综合的认识；其二是将特定领域中隐含的结构明确化，以期总结出独立于具体领域的普遍原理。 (2) 粒计算的目标

粒计算之所以新且独特，并不完全在于一组具体的方法和策略，而在于提出一个统一的框架，对这些方法和策略进行全面的理解及综合。通过对粒计算的研究试图达到以下目标：将隐式的结构显式化；将不明显的原理明显化；将特定领域的特殊原理普遍化；将下意识的行为变成有意识的行为。

1.1.3粒计算基本要素和理论构成

(1) 粒计算的基本要素[14, 15]

2

第一章 绪 论

(a) 粒

粒是粒计算的初始概念，是粒计算研究对象的单位，是求解问题的基本单位，等同于数据库中的记录，集合中的元素或子集。我们称最小的、不可分或不需要再分解的粒为基本粒，即最低层次的粒称为基本粒，它可以是模糊的，也可以是精确的。

粒具有双重身份，它可以是某个整体中相对独立的一个部分，也可以是一些粒共同组成的一个粒。所有的粒都具有内在属性、外在属性和环境属性。当粒作为整体时，所要考虑的是粒的内在属性，内在属性由粒所拥有的元素决定。当粒作为部分时，所要考虑的是粒的外在属性，由于具有外在属性，粒就能够被人们直接认识。粒的环境属性是指粒对外部环境变化的应对情况，对其内在属性和外在属性的保持与调整以及对外部环境的影响和回应。粒的双重身份决定了它的内在属性通常需要强调其它所包含的细小个体的不同特性，是对它内部各个基本组成成分性质的描述，而其外在属性则是强调把它作为一个整体时所体现出的综合特性。 (b) 层次

粒存在于特定的层次中，人们在粒计算的不同层次中研究不同类型的粒，这些粒之间是有联系的，同一层次的粒与粒之间可以是相交的关系也可以是层叠的关系，它们是该层次上研究的主体。层次中每一个粒表述了一个特定的粒化观点。所有的粒化观点相互补充、相互呼应，完整表达了在这个层次上对同一个问题的描述。每个层次都具有内在属性、外在属性、环境属性，同一层次的粒属性共同体现本层次特性。 在问题求解中，选择在最合适的粒度层次上产生对一个问题的描述，能帮助更好更快地解决问题。较高层次包含较低层次，或者由较低层次组成。较高层次为较低层次提供背景和约束。较高层次一般由较高集成度和较高结合力的粒组成。每一层次都存在一定程度的独立性。任意两层次之间的连接和交互是通过偏序关系的传递性和桥接原理来表示和体现的。粒计算模型的主要作用是能够在不同粒度层次上进行问题求解，使不同粒度层次上的解能够进行相互转化。 (c) 分层结构

分层结构由若干个层次组成，层次间的递进反映了由表及里、由抽象到具体、由粗糙到细致、由笼统到具体的变化。这种递进是有序的，高层次会对低层次进行约束，

3

第一章 绪 论

并为低层次的描述提供背景。一个高层次的粒可以分解为若干个低层次的粒。相反，若干个低层次的粒可以组合成一个高层次的粒。低层次的粒为高层次的粒提供更详细的描述或者更多的信息。另一个方面，高层次的粒将与本层次的不相关的细节忽略掉，为低层次的粒提供更粗粒度的描述。 (d) 粒结构

在粒计算研究中强调的是全面、整体的观点，而不是局部、离散的观点。若要达到该目标，不仅要考虑一个分层结构中的多个层次，还需要将多个分层结构综合考虑。粒结构包括三个要素，即粒的内在结构、粒的结构、粒的总体结构，它是多层次和多个分层结构的结合。

粒计算借助于其他学科的哲学思想和方法论，并将它们抽象成为与具体领域无关的方法和策略。它的独特性体现在用系统的、结构化的理解和方法来解决复杂问题。对复杂问题的全面理解通常是多视角的，从每一个视角着眼的理解又是多层次的。由此可以得出，粒计算的过程就是对复杂问题的求解过程。它的结果表现为一个多视角、多层次的粒结构。这个粒结构是对复杂问题的系统且近似的描述和解答。 (2) 粒计算的理论构成[7, 8]

目前，粒计算有3个主要理论以及其它一些非主流理论：其一是词计算理论：人

类思考、判断、推理主要是用语言，而语言是一个很粗的粒，如何用语言进行推理判断，这就是词计算。其二是商空间理论：商空间理论把概念用子集表示，不同粒的概念体现为不同粒的子集，一簇概念构成空间的一个划分——商空间，不同的概念簇就构成了不同的商空间。故粒计算，就是研究在给定知识基上的各种子集合之间的关系和转换，以及对同一问题取不同的适当的粒，从对不同的粒的研究中，综合获取对原问题的了解。其三是粗糙集理论：粗糙集理论于1982年由Pawlak提出，它是一种刻划不完整性、不确定性的数学工具，主要解决信息粒的近似方面的问题。另外许多学者也在研究粒计算，并将各种相关理论用于粒计算，有邻域系统粒计算、信息熵粒计算、概念格粒计算、覆盖粒计算、进化粒模型、基于相容粒度空间的粒计算模型以及各模型相互交叉整合的模型方法等，在许多领域中得以实现或应用。

4

第一章 绪 论

1.1.4粒计算研究方向与方法

粒计算的形成和发展积累了多种思想、模型、范式、方法论、技术及工具。对粒计算的研究应该着眼于三个观点[2]：粒计算的哲学思想观点、方法论观点及计算模式观点。从哲学思想观点考虑，粒计算试图将人类的认知方式抽象化、形式化，从而提炼出结构化的思维模式，而结构化的思维模式是人类智能的重要体现，它对设计基于知识的信息系统有着非常重要的影响，它有两个基本假设：一个是所有问题都可以视作是其内在要素之间的网络状或分层结构的关联，另一个是所有的问题都有着类似的模式和特征；从方法论观点考虑，粒计算着重研究系统化的方法和技术，将问题求解的过程规范为结构化的、自上而下的逐步求精过程；从计算模式观点考虑，粒计算关注于结构化的信息处理。信息处理是有层次的，其研究领域涉及抽象的信息处理、人脑中的信息处理及计算机中的信息处理。计算模式是方法论的具体表现形式。在计算机学科中，人们通常将兴趣集中在基于计算机的信息处理模型上，并将其独立出来进行分析。

粒计算的哲学研究基于粒结构的思维方式。基本问题[7, 10, 15]包括：如何定义粒、层次及分层结构的内在属性、外在属性和环境属性；如何定义它们的关系；如何准确表达它们的关系；如何实现它们的关联和切花；如何使它们的综合功能最大化。哲学层面的研究是抽象的，同时又是方法论和计算模式的前提和保障。

粒计算的方法论致力于将粒计算哲学思想具体到问题求解的方法、技术和工具的研究和开发中去。需要考虑到粒计算方法的有效性、可靠性、准确性、简便性、计算成本和价值。对于不同的应用还需考虑其问题的特定及限制。

粒计算的信息处理强调以计算机为主体的信息处理与以人为主体的信息处理的差别。一方面，以计算机为主体的信息处理依靠人来制定、设计、实施和优化；另一方面，计算机的信息处理也促进方法论的研究。粒计算的哲学思想和方法论的完善为计算机的信息处理实践提供了可以依据的准绳和保障，计算机的信息处理实践反过来也会促进对粒计算哲学思想和方法论的研究，成为支持粒计算哲学思想的有力证据和改善粒计算方法论的原动力。

总之，如何定义粒（粒化）以及如何选择合适的粒度是粒计算解决问题的首要任

5

第一章 绪 论

务[6, 9]。

1.1.5粒计算基本思想和实质

粒计算从不同粒层次上研究问题，从人类求解问题的经验方法中提取基本原理如粒、层次、等级。从人类思考和求解问题上看，“人类以粒的观点看世界”，“人们观察、衡量、概括和推理的实体都是粒”[16]。当人们面对复杂的、难于准确把握的问题时由于能力有限，通常不是采用系统、精确的方法去追求问题的最优解，而是通过逐步尝试的办法达到有限的、合理的目标，也就是采用由粗到细、不断求精的多粒度分析法，避免复杂的计算，从而获得足够满足的解，使得原来看似非多项式的难解问题迎刃而解。人类智能的一个公认特点，就是人们能从极不相同的粒上观察和分析同一问题。人们能在不同粒的世界上进行问题求解，且能够很快地从一个粒世界跳转到另一个粒世界，往返自如，毫无困难。这种处理不同粒世界的能力，正是人类问题求解的强有力的表现，这也正是粒计算的基本思想[4]。粒计算方法是人工智能领域中的一种新理念和新方法，它覆盖了所有和粒度相关的理论、方法和技术，在可以容忍的程度内，主要用于对不确定、不准确、不完整信息的处理，对大规模海量的数据和对复杂问题的求解，使其达到可处理性、鲁棒性、小代价和谐调性。粒计算的实质[4]就是通过选择合适的粒度，来寻找一种较好的、近似的解决方案，从而降低问题求解的难度。

而事实上，从真实世界上看，许多自然系统、社会系统、人工系统都是基于层次的，粒计算可以真实自然地表示这类系统。从简化问题上看，多层系统的不同层次关注不同的粒特征，粒计算忽略了不必要和不相关的细节，只关注适当层次，从而简化了问题。从实用角度上看，许多问题是不完整的、不确定的，或者含有模糊信息，很难区分元素，只能认为是粒。且在许多实际问题中也不要求精确解，或者获取精确信息的代价不菲，粒计算可以提高效率和降低代价。

1.2覆盖广义粗糙集理论

定义1.1[17] 设U是非空有限论域，P是U上的一簇子集且?P?U，对于任意

6

第一章 绪 论

P1,P2?P，如果P1?P2??，那么P为U的一个划分。

定义1.2[33] 设U是非空有限论域，C是U上的一簇子集，如果C中任一子集非空且

?C?U，则C为U的一个覆盖。

1.2.1覆盖广义粗糙集的研究背景

随着计算机及网络的日益普及，丰富的数据与贫乏的知识之间的矛盾日渐突出。不同领域的人都希望能从复杂的数据中得到自己所需要的知识，因此数据挖掘这门学科就应运而生了。该学科涉及分类、概念形成和数据分析。这些都需要对不完全和不充分的信息进行处理，围绕这个问题产生了许多理论，如模糊理论、神经网络、商空间理论、词计算、粗糙集理论等。而其中的粗糙集理论[17]于20世纪80年代提出以来，无论从理论上还是从应用上都取得了丰硕的成果，尤其在数据挖掘领域里[18]。它是通过不可区分关系为不完全和不充分信息的处理提供了一套系统的方法。通常，人们用一组属性来描述事物，不可区分关系就是由这些事物相应的属性值来定义的。如果两个事物对于这组属性的属性值相等，也就是说具有相同的描述，就认为它们是不可区分的。从集合中关系这个角度来看，这种不可区分关系实际上就是等价关系。这样，所有具有相同描述的事物构成一个等价类，而所有的等价类构成所考虑事物的一个划分。在粗糙集理论中，这些等价类又称为初等集，若干个初等集的并称为确定。利用这个划分，任意的事物的集合可以用两个确定集来上下逼近，这两个确定集分别是该事物集合的上近似和下近似。它无需提供问题所需处理的数据集合之外的任何先验信息，对问题的不确定性的描述或处理是比较客观的。由于这个理论未包含处理不精确或不确定原始数据的机制，所以与概率论、模糊数学和证据理论等其他处理不确定或不精确问题的理论有很强的互补性。

而随着粗糙集理论得到广泛的应用以来，为使该理论能有更大的应用空间，人们对Pawlak粗糙集理论进行了许多有意义的推广，如将等价关系放宽为相容关系[19]、相似关系[20]、一般二元关系[21]；与模糊理论结合，将粗糙集理论推广到模糊粗糙集理论[22]和广义模糊粗糙集理论[23]；将经典粗糙集模型推广到变精度粗糙集模型[24]；从等价关系等同于划分这个角度出发，Zakowski把划分放宽为覆盖[25],将Pawlak粗

7

第一章 绪 论

糙集理论推广到覆盖广义粗糙集理论。

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本文研究的目标

虽然覆盖广义粗糙集有了一定的理论基础和应用领域，但与粗糙集相比，需要不断丰富其理论基础和应用领域，而继续建立覆盖近似运算公理化理论体系、覆盖约简及近似性度量和不断寻求覆盖广义粗糙集的适用方向是进一步研究的具体目标，本文

8

第一章 绪 论

旨在对覆盖广义粗糙集的应用基础进行研究。

1.3.3本文研究的方法、技术路线及可行性分析

本文将采用由浅入深、并行开展的研究方法。首先，介绍了粒计算思想理论体系的新颖性以及独特性——以孤立点挖掘为例。其次，在粒计算思想理论体系下，利用覆盖相关理论分别对基于粗糙集的动态信息系统规则挖掘、关联冲突分析、分类准确率三个方面进行独立研究。

(1) 在基于粗糙集的动态信息系统规则挖掘中的应用研究中，主要利用条件属性和决策属性的交叉一致性来寻找引起差异信息系统中的不一致因素，然后利用改进的规则挖掘算法通过实验对比来实现。

(2) 在面向冲突分析的研究中，将冲突看作是在不同结构层上的粒化过程，提出关联冲突的概念，给出其形式化的定义，然后并对其进行分析和建模，最后给出关联冲突过程中所可能引发异常的阶段，将对不同阶段引发的异常进行详细的分析 (3) 在面向分类准确性研究中，利用拓扑覆盖邻域理论来寻找覆盖系统上重叠元素，然后在粒计算的思维体系背景下，以实例辅证，采用折中方式给出独立于数据标签和理想分类结果假设的评价分类法准确性的统一范式。

以上提出的研究方法和技术路线是在前人对覆盖广义粗糙集理论和应用以及相应领域研究基础上的再探索。虽然涉及领域比较宽泛，但都是在粒计算背景下研究的与覆盖相关的理论和应用，所以本文实施和所采用的技术路线是可行的。

1.3.4本文研究的主要内容以及创新点

本文主要是在粒计算的思想理论背景下研究与覆盖相关的理论及其应用。具体包括以下六章内容：

第一章为绪论。首先介绍了粒计算的相关理论知识；然后介绍了覆盖广义粗糙集的研究背景，分析了国内外研究现状；最后介绍了本文的研究意义、目标、方法和主要内容以及创新点。

第二章为粒计算的独特魅力。本章主要讨论了粒计算的新颖性和独特性——以孤立点挖掘为例，创新性地给出了孤立点挖掘总的指导原则和具体实施的流程图，为孤

9

第一章 绪 论

立点挖掘算法的选择、改进和创新提供了实际的参考价值，以此来揭示粒计算的独特思维模式和研究方法，进而体现本文的写作意图即受粒计算思想与理论的影响，获取与覆盖相关的创新思想来源。

第三章为覆盖粒计算在基于粗糙集的动态信息系统规则挖掘中的应用研究。本章针对差异信息系统构造过程中会引起新的不一致这个问题，利用覆盖粒计算相关理论提出了一种新的能消除这种不一致因素的公理化方法。实验结果表明，在保持时间复杂度不变的情况下，利用改进的规则挖掘算法，通过消除不一致因素而获得的规则更全面和更大程度地反映了条件属性值变化与决策变化趋势之间的内在联系。 第四章为基于覆盖粒计算的关联冲突分析。本章在粒计算思想理论背景下，首次提出了“关联冲突”的概念，利用覆盖冲突分析策略,通过“服务——资源”实例建立了关联冲突分析的合理泛化模型，讨论了关联冲突过程中所可能引发异常的阶段，并对不同阶段引发的异常进行了详细的分析，给出了具体的解决方案。

第五章为基于覆盖粒计算的分类准确性研究。在面向分类法准确性（单标签和多标签数据集）的研究中，本章利用拓扑覆盖邻域理论，给出了一种新的寻找覆盖系统上重叠元素的相关的公理化方法。在粒计算的思维体系背景下，以实例辅证，创新性地给出了独立于数据标签和理想分类结果假设（一种假设为划分，另一种假设为覆盖）的评价分类法准确性的统一范式。需要说明的是，本章对于分类法准确性统一范式的给出采取的折中处理方式值得借鉴。

第六章为总结与展望。文章在同一个思想理论背景下，讨论了基于覆盖的相关理论和应用，它是覆盖广义粗糙集的理论及其应用的补充和发展，并且更体现出了粒计算背景下知识发现理论和方法的独特性，具有重要的理论意义及潜在的应用价值，同时对该领域理论和应用研究的发展方向提出了新的展望。

此外，本文收录了一些该领域内最新的研究成果，以期能为科研工作者认识和深入研究提供便利。

10

第二章 粒计算的独特魅力

——以孤立点挖掘为例

本章主要讨论粒计算的新颖性和独特性，以此来揭示粒计算的独特思维模式和研究方法，从中体现出本文的写作意图，在粒计算思想理论背景下的覆盖理论及其研究的问题即受粒计算思想与理论的影响，获取与覆盖相关的创新思想来源。以孤立点挖掘为例，在粒计算的思想理论背景下，给出了孤立点挖掘总的指导原则和具体实施的流程图，为孤立点挖掘算法的选择、改进和创新提供了实际的参考价值，将会对孤立点的挖掘产生一定深远的影响。

2.1引言

孤立点也即异常点[65]，是指数据集中不符合一般模型的那些对象，即和其他数据有着不同的性质。对于某些度量而言，这些对象与数据集中的其他数据有着显著的不同。目前，针对不同的数据挖掘任务和挖掘背景，一些数据挖掘算法尽量去减少孤立点带来的影响或者甚至是从数据集中消除他们，然而，这可能会导致一些重要的隐秘信息的缺失。换句话说，孤立点本身在诸如入侵检测等事件中有着特殊的意义，它可以表示入侵的异常行为。因此，孤立点的检测和分析（即孤立点挖掘）在数据挖掘中就显得非常重要。一般，孤立点挖掘问题可以看作两个子问题：一个是在给定的数据集中定义一个什么样的数据可以被认为是孤立点或不一致的；另一个是找到一个有效的方法去挖掘这些定义的孤立点。

在过去的一个多世纪里，人们对孤立点的研究经历了几个兴衰交替。现在，它再一次成为信息科学里的一个活跃分支，并在数据挖掘领域里受到越来越广泛的关注。孤立点挖掘之所以有着广泛的应用，是与其所在的实际领域里的特殊性决定，诸如入侵检测、市场营销和医疗等领域。孤立点的引起是有一些原因的[66]，同时相应的也有一些检测或挖掘孤立点的方法[67-76]。然而，每种方法总是存在着不可避免的缺点或者略势，没有一个普遍有效的方法来检查数据集中的孤立点[77]。特别在检测孤立点的过

11

第二章 粒计算的独特魅力

程中，如何选择一个合适的检测方法没有一个普遍的准则，而且就孤立点目前研究的热点和未来的发展来说[77]，挖掘任务会变得非常困难。因此，寻求一个适用于孤立点挖掘的总的指导原则就成为了最急需要解决的问题。

2.2引起孤立点的原因

(1) 数据来自不同的类

一个数据不同于其他数据，可能因为它来自不同的类或属于不同的类型。例如，一个在进行信用卡欺诈的人可能被归为不合法的信用卡用户而不是非法的用户。相同地，诸如欺诈、入侵、疾病暴发和异常的实验结果等都可以被认为是造成孤立点的例子。

(2) 自然变异

在统计知识的背景下，一些诸如正太分布等模型可以用来模拟许多数据集的分布。随着数据点离正太分布的中心距离的增加，该点出现的可能性就会急剧地减少。换句话说，对于大多数点来说，离中心（平均对象）越近，不同于这个平均对象的可能性就越小。例如，假定一个男性特别的高，当他独自一人时，没有人与之形成对比，他没有什么特别之处。但是一旦于其他人在高度上做比较时，他就是一个孤立点，在这群人里他是一个高度上的极值。通常这些极值点或没有任何变异的点作为孤立点是非常有意思的。

(3) 数据度量和收集导致的误差

在数据收集和度量的过程中，所导致的误差是引起孤立点的另一个根源。例如，由于人为失误、设备误差或者数据本身具有噪音导致所记录的度量值不正确。一般情况下都会删除这些孤立点，因为他们不能提供有用的信息，相反他们会降低数据分析的质量。但这些数据能反映出一些有用的信息，例如误差的根源是人为、设备还是其他的原因造成的等。

2.3孤立点挖掘方法的思想描述

(1) 基于统计模型的孤立点检测方法[67, 68]

许多检测技术首先都会构造一个数据模型。孤立点就是这些不能够很好拟合这个

12

第二章 粒计算的独特魅力

模型的数据对象。例如，数据的分布模型可以通过估计概率分布的参数来构造。如果一个数据对象不能够很好的拟合这个模型，它可能不服从这个分布，那它就是孤立点。如果模型是簇的集合，那么孤立点会明显的不属于任何簇。或者当使用回归模型时，孤立点会相对的远离模型的预测值。 (2) 基于距离的孤立点检测方法[69, 70]

目前，许多孤立点检测的方法都是基于距离的。孤立点就是远离大多数点的点。当数据分散在二维或三维的图中时，我们可以通过基于距离的方法，用肉眼或简单方法分辨出哪些点是孤立点。

(3) 基于偏差的孤立点检测方法[71, 72]

我们也可以通过比较一组数据的主要特征来检测孤立点。根据问题的要求，可以事先给定数据所对应的一些特征，那么孤立点就是这些不能像特征所描述的那样的点。

(4) 基于密度的孤立点检测方法[73, 74]

数据分布的密度估计是相对可以通过计算得到的，尤其是对数据之间存在距离的点来说。那些处于低密度的数据点相对地远离他们的邻居可以被认为是孤立点。但是考虑到数据集可能有不同的密度区域，因此当一个点所在的区域的密度明显低于它的大多数邻居的时候，它可以被归为孤立点。 (5) 基于聚类的孤立点检测方法[75, 76]

聚类分析和孤立点检测有不同的目标。聚类分析通常被用于发现强相关的对象，而孤立点检测则被用来发现那些和强相关的对象没有关系的对象。显然，聚类可以用于孤立点检测。

2.4讨论

在数据挖掘中，粒计算有着广泛的应用[78-80]。数据的粒化，尤其是复杂数据的粒化，是基于粒计算的数据挖掘的必要前提。粒化的程度直接影响数据挖掘的效率和计算复杂度。既要避免粒度过粗而造成求解失败，又要避免粒度过细造成信息的冗余而导致求解效率低下。因此，选择最优粒化程度是粒计算数据挖掘的关键。另外，当粒化的程度已知时，粒化的方法直接决定了粒化的效率。

13

第二章 粒计算的独特魅力

孤立点挖掘是一个将孤立点从数据集中分离出来的过程。通过对引起孤立点的原因进行分析，我们发现孤立点大都是各种情况里的不寻常的对象。他们由突发事件、人为因素或环境原因等所引起的，所以我们需要不同的实施过程将它们分离出来。事实上，从粒计算的观点来看，分离的过程就是粒化的过程，并且上面所列出的孤立点的检测方法都是基于粒化思想的。正如Zadeh所认为[13]的：人类的认知能力概括为粒化、组织和因果推理，人们对孤立点挖据方法的设计正是人类认知能力尤其粒化能力的反应，例如，基于距离、密度和聚类的孤立点检测方法可以看作为基于空间粒化的方法，而基于统计模型和偏离的孤立点检测方法可以被看作为基于模糊匹配信息的粒化方法。而且分离的思想与粒度有着非常近的关联，在不同的粒化水平上，通过使用一些特殊的方法或策略，我们可以选择合适的粒度来缩小孤立点的检测范围，这样就可以提高孤立点挖掘的效率并降低挖掘的时间复杂度，尤其对大数据集中的孤立点挖掘来说效果和意义更明显。

我们换个角度来考虑孤立点检测的方法。粒计算新颖和独特的原因不完全在于提供具体的方法和策略，而在于提出了一个统一的框架，对这些方法和策略进行全面理解及综合。如果我们通过粒结构将知识和系统合为一体。由此产生的结果是，人们能将普遍适用的粒计算哲学有意识地运用到各自面对的问题中去，从而对问题进行更有效的求解。同时，对高层次的粒结构的认识可以防止人们对相同、相似理论和方法的重复发现和发明，避免浪费精力。因此，将粒计算的新颖和独特之处运用到孤立点挖掘中，有如下指导原则：

通过对引起孤立点原因和孤立点检测方法的分析，结合粒计算的观点，从方法本身的高层粒结构出发，独立于检测方法的孤立点挖掘总的指导原则是粒化观点，同时表明了在选择合理的粒度之前，它在孤立点挖掘中扮演着非常重要的角色，根据不同的检测目标，有着不同的粒化原则。而且粒化观点是一种新的求解系统，它是孤立点检测过程中首先并且唯一开始着手的思想。换句话说，对孤立点检测方法的选择、改进和创新，它提供了统一的、正面的和有效的说明。在信息科学快速发展的背景下，它将对孤立点的挖掘产生深远的影响。

图2.1是基于粒计算的孤立点挖掘的统一过程框架图，它是粒计算思想应用到孤立点挖掘中的很好体现，其中有阴影部分是背景知识：

14

第二章 粒计算的独特魅力

图2.1 孤立点挖据的统一实施过程

2.5小结

对于粒计算而言，其思想和理论在孤立点挖掘上得到了充分的体现。在对孤立点挖掘方法的分析和概括的基础上，总结出了独立于方法之上的方法论原则（粒化指导原则），使得孤立点挖掘的着手点集中在粒化的思想上，避免了许多重复性的工作和不必要的麻烦，这是粒计算任务和目标的体现。而孤立点挖掘的统一实施过程流程图体现了粒计算的其他方面：挖掘过程本身是有先后顺序之分，因此是具有一定层次性；而挖掘过程中，粒度大小的选择即合适层次上的粒化，以获取粒化原则用以选择、创新和改进挖掘方法；由于粒度大小选择上原因导致挖掘结果不是很满意，需要调节粒度，因此，这是一个循环反复的过程（体现出了分层结构以及粒结构），其间需要粒计算理论注入其中以求对所要解决的问题选择合理的层次和粒度。

对于孤立点挖掘而言，粒化观点是孤立点挖掘方法的选择、改进和创新的切入点，它的引入使得人们对孤立点挖掘的研究更广泛和更集中即不断的将新的粒化方法引入到孤立点挖掘中和只将挖掘任务放在粒化的思想上进行考虑，这样一方面使得挖掘算法得到不断改进和创新，另一方面又可以避免许多不必要的重复劳动。而孤立点挖

15

第二章 粒计算的独特魅力

掘统一实施过程图的引入，使得孤立点挖掘任务的实施更一致化、明了化和细致化，尤其面对复杂数据诸如数据流、高维数据集和Web数据等中的孤立点挖掘时，该过程图更能体现其优势所在，而且粒计算本身就具有其独特的处理复杂数据的能力。

最后对于二者而言，基于粒计算的孤立点挖掘将会给孤立点挖掘的研究和分析提供一种新的策略和模式，它将对孤立点的挖掘产生深远的影响。而将粒计算思想理论应用于孤立点挖掘，全面体现了粒计算独特的思维模式和研究方法，显示出了它的独特性和新颖性，更体现出了本文的写作意图，将在粒计算的思想理论背景下研究与覆盖相关的理论及其应用即受粒计算思想与理论的影响，获取与覆盖相关的创新思想来源。

16

第三章 覆盖粒计算在基于粗糙集的动态信息系统规则挖掘中

的应用

在动态信息系统中，采用粗糙集方法来挖掘系统中潜在的规则。对于这类问题，由于信息系统的不一致性以及差异信息系统构造过程中的不确定性和差异性，规则挖掘的结果不甚理想：在粒计算的思想理论背景下，本章将覆盖相关理论运用到规则挖掘中，提出了一种消除引起差异信息系统规则挖掘中不一致因素的方法。实验结果表明，在保持时间复杂度不变的情况下，利用改进的规则挖掘算法，通过消除不一致因素而获得的规则将能更全面和更大程度地反映条件属性值变化与决策变化趋势之间的内在联系。

3.1引言

粗糙集方法是一种用于处理不确定性和模糊性数据的数学工具[17, 81]。但由于客观世界的不确定性问题通常表现为易变性和过程性，传统的粗糙集很难体现出不确定性的变化过程和变化趋势，即在信息系统中体现为属性随着时间的推移而不断地变化[82,

83]

。在决策信息系统中，利用粗糙集理论建立属性值随时间和场景变化的动态信息系

统模型[84]，可以挖掘出条件属性值变化与决策属性值变化之间存在的内在联系。可是由于动态信息系统构造过程中会产生新的不一致性[85]，使得从差异信息系统上获得的决策规则不甚理想。为了能获得理想的决策规则，本文给出了一种能消除引起差异信息系统不一致因素的方法，并给出了改进的基于粗糙集的启发式规则挖掘算法，最终使决策规则能更好更全面的反应条件属性值的变化与决策变化趋势之间的关系。

3.2预备知识

一个信息系统S表示为一个四元组：S?{U,A,V,f}，其中U是对象的集合，即论域；A是属性集（A?CN?D，CN为条件属性集，D为决策属性集）；V?Va表示a的值域；f:U?A?V?Va?Aa，

是一个信息函数。由于单个信息系统无法描述信息

17

第三章 覆盖粒计算在基于粗糙集的动态信息系统规则挖掘中的应用

和信息量随时间和场景的变化的状态，文献[84]中给出了信息变换函数f:T?S??的概念，函数的定义域是时间和场景的区域，其中时间序列集合为T?{t1,t2,...}，场景集合为S?{s1,s2,...}，状态序列集??{?ts,?ts,...}，每个?ts都是一个决策表且论

1122ii域、条件属性、决策属性均相同，属性值随着时间和场景的变化而变化。有： 定义3.1 动态信息系统为状态序列??{?ts,?ts,...}。

1122 抽取信息系统?ts和?ts（j?i），?Vca?Vca?ts?Vca?ts称为条件属性值差异，其

iijjjjii中Vca?ts表示对象个体c（c?U）关于属性a（a?CN）在ti时刻si场景下的属性值，

ii条件属性值差异描述了条件属性值的变化量。记CN'?{?a,?b,...}，其中?a是对条件属性a值的差异描述，?a的属性值为a的属性值差异。

而(Vce?ts?Vce?ts)?Ve?Ve称为决策变化趋势，其中e?D，描述了相同的对象个

iijj体的决策值从Vce?ts变化到Vce?ts。若两个不同个体k,h?U具有相同的变化趋势

iijj(Vke?tisi?Vke?tjsj)=(Vhe?tisi?Vhe?tjsj)，当且仅当Vke?ts?Vhe?ts和Vke?tjsj?Vhe?tjsj同时成立。记

iiiiD?{e,g,...}，e''''是对决策属性e变化趋势的描述，e'的属性值为e的决策变化趋势。

定义3.2 差异信息系统为???(U',A',V',f')，其中U'?U，A'?CN'?D'，

V?'?V，fa?A'''a':U?A?V'''，CN'、D'为差异信息系统的条件属性和决策属性。

由粗糙集理论可以得出，若信息系统?ts和?ts关于决策属性D的等价类记为：

iijj[u]D(i)和[u]D(j)，差异信息系统??ij中关于决策属性D'的等价类记为：[u]D(i?j)，则有

'[u]D'(i?j)=[u]D(i)?[u]D(j)。特殊的，当j?i?1时，此时的差异信息系统被称为相邻差

异信息系统。则有下面定义：

定义3.3 在差异信息系统??ij中，对任意的属性?a?CN'，?a的重要度Sig(?a)定义为Sig(?a)??CN(D')??CN??a(D')，式中：?P(Q)?''card(POSPQ)card(U)，POSPQ表示Q的

P正域[81]。重要度表明了属性对于决策分类能力的贡献程度。

定义3.4 设card(U')?m，card(A')?n，card(D')?d(d?n)（差异决策表有m行n列，决策属性d列），构造??上第p行的辨识矩阵M(p)?[wi,j](m?1?)n，其中如果

18

第三章 覆盖粒计算在基于粗糙集的动态信息系统规则挖掘中的应用

（xp?xi）则wi,j?1；否则wi,j?0。 f(xp,?aj)?f(xi,?aj)，

''定义3.5 设从差异信息系统??ij上获取的决策规则集为{r1,r2,...,rs}[86]，规则表示形式为?a????b???...?e'?(s1?s2)?...，定义决策规则的覆盖广度为

s?card(r)vv?1scard(U)，其中card(rv)为??i'j上满足该决策规则的记录数；决策规则的

s准确率为?bcard(rv)v?1?v?1fcard(rv)，其中fcard(rv)、bcard(rv)分别为??ij上满足该

决策规则前件和后件的记录数。

从中可以看出，通过某个挖掘算法得到的决策规则，其覆盖广度与准确率并不成正比，即在同样的时间复杂度下，一个改进的挖掘算法得到的挖掘规则，其覆盖广度和准确率都必须同时增大，因此决策规则更准确并且覆盖记录也就更广泛。

3.3规则挖掘

3.3.1动态信息系统中不一致性的辨识和消除

从粒计算的观点来看，如果我们将构成差异信息系统??ij的两个决策信息表看作是同一层次上的两个粒，那么差异信息系统??ij就直接为其上一层的粒，上层粒就会包含下层粒。因此，对于动态信息系统的状态序列?中决策表存在着一致或不一致这个问题，随着时间和场景的变化，就会有引起差异信息系统??ij中不一致的因素包含引起构成差异信息系统??ij的两个决策信息表中的不一致的因素的并，那么??ij中可能会产生新的不一致因素。对于这些新的不一致因素，我们将采取下面方法来消除：

由于不一致表现为在??ij中条件属性值均相同，而决策属性值存在不同，我们可以通过构造??ij上的覆盖，消除其上引起不一致的记录，使其成为一致差异决策表。设差异条件属性CN'构成的划分为X?{X1,X2,...,XM}，差异决策属性D'构成的划分按每个类所含记录多少降序排列为Y?{Y1,Y2,...,YN}（0

19

第三章 覆盖粒计算在基于粗糙集的动态信息系统规则挖掘中的应用

性构成的分类为基础，构造??ij上的覆盖Y'?{Y1',Y2',...,YN'}（由定义1.2可知）。其过程为：依次对每一个Yi?Y，满足若对?yik?Yi，?Xj?X，0?k?card(Yi)有yik?Xj，则Yi'?Yi'?Xj并且X?X?{Xi}；否则Yi'?Yi。

定理3.1 { ?Yi' | ?Yi'?Y', ?Yj'?Y',i?j且0?i,j?N,有Yi'?Yj'}为引起??ij上不一致原因的记录集合。

证明：根据以上算法描述，显然在差异决策属性D'构成的划分中，引起不一致原因的记录不会存在于card(Yi)?1的分类中，只会存在于card(Yi)?1的分类中。而在差异条件属性CN'构成的划分中，引起不一致原因的记录不会存在于card(Xj)=1的分类中，只会存在于card(Xj)?1的分类中。通过上述方法构造的??ij上的覆盖Y'，引起不一致原因的记录就会存在于card(Y'i)?1的Yi'中，同时card(Y'i)?1的Yi'中保留了引起不一致原因的记录，最终就有满足?Yi'?Y', ?Yk'?Y',有Yi'?Yk'的所有Yi'的并集

?Yi 为引起??i'j上不一致原因的记录集，其中i?k且0?i,k?N。证毕！

例3.1 U'?{1,2,3,4,5,6,7,8}，假设CN'构成的划分为X?{{1},{2,5},{3},{4,6}{7}{8}}，

'那么D构成的划分按每个类所含记录多少降序排列为Y?{{1,6},{2,3}{4}{5}{7}{8}}，

''''''Y1?{1,4,6}，Y2?{2,3,5}，Y3?{4}，Y4?{5}，Y5?{7}Y8?{8}，按照Y'的构造过程有：

不一致因素为{4,5}。

3.2.2规则挖掘算法

输入：信息系统?ts与?ts；

iijj输出：约简后的决策规则（表示形式为?a????b???...?e'?(s1?s2)?...）。 步骤1：根据定义3.2，构造相应的差异信息系统??ij?(U',CN'?D',V',f')； 步骤2：根据定理3.1，构造??ij上的覆盖，找出引起不一致的记录，并在??ij中设置对应记录所在行为空；

20

第三章 覆盖粒计算在基于粗糙集的动态信息系统规则挖掘中的应用

步骤3：根据定义3.3，对??ij对每个条件属性计算其重要性，得到属性重要性升序的序列，用数组Sig[card(CN')]保存，设置属性值不变的记录为空，用LN保存空行所在的行号；

步骤4：for i?1 to m

{

if(i?LN) {

根据定义3.4，构造第i行的辨识矩阵M(i); if(M(i)的后d列存在非零行) {

获取M(i)中所有非零行的前n?d列上的所有非零元素所在列号;

根据所获得的列号, 设置??ij第i行其他列号的条件属性值

为’*’;

continue;

} else

for j?1 to card(CN')

{

设置M(i)的第sig[j]列为1;

if(M(i)中不存在某行前card(CN')列全为1，且后d列存在

0)

设置??ij第i行第sig[j]列的属性值为’*’;

else

break;

} }

else

continue;

21

第三章 覆盖粒计算在基于粗糙集的动态信息系统规则挖掘中的应用

}

步骤5：整理合并相同规则，得到动态信息系统的最简决策规则。

算法的时间复杂度为o(n(n?d)m2)[87]，由于求信息系统的最优约简是NP问题

[88]

，所以算法试图生成的是最重要的尽可能全部的决策规则。

3.4实例分析

表3.1 ?ts?(U,CN?{e},V,f)ts

iiii

A U 1 2 3 4 5 6 7 8 a b c e 5 3 3 2 2 4 1 3 4 2 3 3 1 5 1 2 4 3 2 2 2 5 1 2 4 3 3 2 1 4 1 2 表3.2 ?t

Ai?1si?1?(U,CN?{e},V,f)ti?1si?1

U 1 2 3 4 5 6 7 8 a b c e 4 4 3 1 3 3 2 4 2 3 4 3 2 5 1 3 1 5 5 2 4 5 2 5 3 4 4 1 3 3 2 4 对癌症病人的临床诊断的数据中，抽取部分数据并通过排序得到的状态集

??{?ts,?t112s2,...}，选出在时刻ti与场景si的信息系统为?ts?(U,A,V,f)ts，其中U为

iiii全体病人，A?CN?D，CN?{a,b,c}为条件属性集，表示诊断项目，D?{e}为决策属性集，表示病人的状态，共分为4种状态。对属性值进行量化后，如表3.1所示；又选出在时刻ti?1与场景si?1的信息系统为?ti?1si?1?(U,A,V,f)ti?1si?1，如表3.2所示。

22

第三章 覆盖粒计算在基于粗糙集的动态信息系统规则挖掘中的应用

表3.3 ??ii?1?(U',CN'?{e'},V',f')

U 'A ?a ?b ?c 'e '1 2 3 4 5 6 7 8 -1 1 0 -1 1 -1 1 1 -2 1 1 0 1 0 0 1 -3 2 3 0 2 0 1 3 (4→3) (3→4) (3→4) (2→1) (1→3) (4→3) (1→2) (2→4) 规则挖掘过程为：计算信息系统?ts和?tiii?1si?1的条件值差异与决策变化趋势，得

到相邻差异信息系统??ii?1，如表3.3所示。由定义3.3求出??ii?1中?a，?b，?c分别为14，0，18，则Sig[3]={?b,?c,?a}。构造??ii?1上的覆盖，求出引起不一致的记录所在行号，由于没有属性值不变的记录，所以LN?{4,5}，并设置??ii?1上对应LN行号为空。由定义3.4构造??ii?1中每行记录的辨识矩阵，利用给出的算法得到决策规则表3.4。

表3.4 决策规则表

A U ''?a ?b ?c e '1 2 3 4 5 6 7 8 -1 * * -1 * 1 * 1 1 * * * * * * * 1 3 (4→3) (3→4) (3→4) (4→3) (1→2) (2→4) 最后整理上表得到决策规则：

? ?a??1?e'?(43) ，

23

第三章 覆盖粒计算在基于粗糙集的动态信息系统规则挖掘中的应用

?b?1?e'?(3? ?c?1?e'?(1?

?a?1??c?3?e'，4) ，2)

(?2。?4)

由定义3.5得出决策规则的覆盖广度和准确率分别为34、23。决策规则说明了具体是哪个或哪些条件属性值的变化造成了系统状态的改变，挖掘出条件属性值变化和系统状态改变之间的内在联系。规则?a??1?e?(4?3)表明，病人a'诊断项目

的值减少1个等级，病人病情有从4状态向3状态变化的趋势，这为医生的下一步治疗方案提供了依据。

而如果没有去掉不一致因素，即算法中不加入预处理步骤，那么规则挖掘算法挖掘出的决策规则为： ?a??1?e'?(4? ?a?1?e'?(3? ?c?1?e'?(1?

?a?1??c?3?e'，3) ，4) ，2)

(?2。?4)

该决策规则的覆盖广度和准确率分别为58、59。

显然，通过文章给出的预处理改进的算法挖掘出的决策规则在覆盖广度和准确率上都优于上述决策规则。

3.5小结

在基于粗糙集的动态信息系统中，本文利用覆盖粒计算思想理论克服了因不一致问题所导致的规则挖掘不理想的问题。文章中给出了一种消除引起不一致因素的方法，即利用差异信息系统中的条件属性值和决策属性值的差异描述构成的分类，来构造该差异信息系统上的一个覆盖，然后以决策属性值差异描述构成的分类为标准，获取引起差异信息系统不一致的记录，引入定理并作了相应的证明，给出了改进的规则挖掘算法以及决策规则评价标准，通过实例说明了最终挖掘出的决策规则能更全面和更大程度地反映条件属性值的变化与决策变化趋势之间的内在联系。为了能更好的处理因不一致而导致规则挖掘不理想的问题，文章给出的消除不一致因素的方法是否能

24

第三章 覆盖粒计算在基于粗糙集的动态信息系统规则挖掘中的应用

运用到一般的决策信息系统中是以后研究的重点。

25

第四章 基于覆盖粒计算的关联冲突分析

冲突是社会上的一种非常普遍的现象，对它们的研究无论从理论上还是从实际上都是非常重要的。目前，人们已经提出了很多数学模型和方法用来模拟冲突过程和解决冲突带来的影响。本章主要对关联冲突进行分析和建模：在粒计算的思想理论背景下，首次提出了关联冲突的概念，利用覆盖冲突分析策略,通过“服务——资源”实例建立了关联冲突分析的合理泛化模型，讨论了关联冲突过程中所可能引发异常的阶段，并对不同阶段引发的异常进行了详细的分析，给出了具体的解决方案，从而最终使得关联冲突的提出和分析有助于完善社会各个领域中冲突的解决。

4.1引言

由于人类多样性、资源分配不均和地区文化差异等原因，冲突无处不在，从人与人之间的冲突到国家与国家之间的冲突。在机械系统、电子系统和软件系统等中都存在各种各样的冲突。因此，对冲突的相应分析和解决在诸如商业、政治、法律诉讼和人力资源管理等社会领域或系统里都扮演着非常重要的角色。目前，人们已经提出了很多模型和方法用来模拟冲突过程和解决冲突带来的影响，同时，也有使用图论、拓扑和微分方程等各种各样的工具和技术来辅以冲突的分析和解决[89-103]。

然而，所有的这些研究把重点放在了冲突本身，例如引起冲突的原因、冲突关系的整合、各种领域里冲突的分析等，即把冲突当成是一个对象来研究。根据粒计算相关思想理论，如果我们换个角度来研究冲突即将冲突看成是有着不同结构层次的粒化过程的话，将会有一些非常有意思的发现。也就是说有这样一些情况，单个事件或过程中事实上包含了两个或两个以上的冲突关系（我们称此为关联冲突或多联冲突），例如客户们需要得到一些公司提供的服务，而每一种所提供的服务又需要得到其他一些提供资源的公司的支持，那么这个客户需要服务的事件中，就可能有两个冲突利益关系同时存在这些公司当中，分别对应着服务冲突和资源冲突。那么如果有两个冲突利益关系存在，在这样的一些事件或过程中，一系列诸如边缘对象（如客户和资源）的关系、事件或过程中存在的潜在安全危险（如资源短缺）和如何决策等可能存在的

26

第四章 基于覆盖粒计算的关联冲突分析

问题就成为了急需要解决的问题。

针对以上问题，本文引入了关联冲突的概念，将会利用基于覆盖粒计算[103]的冲突分析策略对关联冲突进行分析和建模，用以解决一系列相关问题。

4.2预备知识

一般地，一个信息系统S表示为一个四元组：S?{U,A,V,f}，其中U是对象的集合，即论域；A是属性集；V??Va?Aa，Va表示a的值域；f:U?A?V是一个信

息函数。因此，?B?A，|B|?0，对所有的(x,y)?U?U，U内元素在属性集B上关于S的辨识矩阵M(B)定义为

mB(x,y?){?aB:a(?x)[104, 105]

：M(B)=(mB(x,y))|U|?|U|，其中

a(By中能区分x和y的所有属性的集合。 是

评论4.1 特别地，|mB(x,y)|?1就意味着x和y仅能被B中的一个属性所区分，这就表明了，对于给定的信息系统S和属性集B来说，这个属性在S中扮演着非常重要的角色，它是不可或缺的[104, 105]。因此，在一些特殊的情况下，当|mB(x,y)|是最大值或最小值时，x和y应当引起足够多的重视。

4.3粒计算背景下的相关工作

基于Pawlak粗糙集理论提出了一种冲突分析的方法[94-97]。在这种方法中先选取冲突的问题及参与冲突的实体和他们的在冲突中的立场：冲突，联盟，还是中立。T. Y. Lin[99-102]利用粒计算方法在文献[98]的基础上提出了长城安全策略的冲突分析和对策的修正模型。在这个模型中，有两个核心的概念：利益冲突关系（CIR）和同盟关系（IAR）。在文献[98]中，CIR是一个等价关系。但正如T. Y. Lin指出的那样，这不是总能成立的，因此将CIR改造成为满足对称性、反自反性和反传递性的关系，而将

IAR作为CIR关系的补，是一个等价关系。而在文献[103]中，W. Zhu指出尽管T. Y. Lin

的模型在许多情况下是个有用的模型，但IAR并不总是等价关系。朋友的朋友并不总是朋友。CIR关系中的反传递性是没有必要的。覆盖是一个更合适的模型来刻画利益

27

第四章 基于覆盖粒计算的关联冲突分析

冲突关系这个问题，因为覆盖本质上具有对称性。

设U是所有客体，C是U的一个覆盖，?K?C，K中的客体是相互冲突的。这样的覆盖C被称为利益冲突族，以区分文献[98]里的模型中的利益冲突类，它是划分。在这个覆盖下，x?U，x的敌人定义为conflict(x)??{K?C|x?K}?{x}。如果一个主体已经访问过客体x，那么这个主体不能访问conflict(x)中的任何一个客体。相应地，x的同盟集定义为ally(x)?U?conflict(x)。作为U上的二元关系，IAR可以定义为IAR?{(x,y)|y?ally(x)}。

评论4.2 在覆盖模型中，数据集的访问权或者需求权可以如下这样授予： 假设一个主体已经访问或需求了的客体是x1,...,xm，而这个主体要求访问或需求客体o。只有在客体o不在conflict(x1)?...?conflict(xm)中，才授予这个主体访问或需求o的权力。换句话说，只有在客体o在ally(x1)?...?ally(xm)中，这个主体才能访问或需求

o。

例4.1 假设一个顾问公司CONSULT为下列公司提供服务：U?{A,B,C,D,E,F,G}，这些被服务公司之间的利益冲突关系见下表4.1，利益冲突族为C?{K1,K2,K3,K4,K5}，其中K1?{A,C,E}，K2?{C,D}，K3?{A,F}，K4?{C,G}，K5?{B,D,E}，那么每个公司的敌人集（conflict(x)）和同盟集（ally(x)）如下：

conflict(A)?{C,E,F}，conflict(B)?{D,E}，conflict(C)?{A,D,E,G}，

conflict(D)?{B,C,E}，conflict(E)?{A,B,C,D}，conflict(F)?{A}，conflict(G)?{C}；ally(A)?{A,B,D,G}，ally(B)?{A,B,C,F,G}，ally(C)?{B,C,F}，ally(D)?{A,D,F,G}，ally(E)?{E,F,G}，ally(F)?{B,C,D,E,F,G}，ally(G)?{A,B,D,E,F,G}。

例4.2 举例说明长城安全策略。

假设利益冲突关系如例4.1所示。长城安全策略将是这样的：起初，CONSULT公司的一个工作人员可以访问或需求任何一个公司的数据集，例如这个工作人员访问或需求了公司A，那么他不能访问公司C、E、和F，因为这些公司都在conflict(A)中。但他可以访问或需求ally(A)中B、D和G公司的数据集。所以，如果他再选择访问

28

第四章 基于覆盖粒计算的关联冲突分析

或需求公司D后，他就不允许访问conflict(A)?conflict(D)中的B、C、E和F，但他仍可以访问或需求ally(A)?ally(D)中的A、D和G公司，以此类推下去。

综合考虑，我们将选择比较合适的覆盖冲突模型应用到关联冲突的分析和建模当中去。

表4.1 公司的利益冲突关系

company A A A B B C C C C D D D E E E E F G company C E F D E A D E G B C E A B C D A C 4.4粒计算视角下的关联冲突

冲突存在于不同的等级层次当中[106]。引起冲突的原因是为了某种利益对象之间相互作用而导致的。当有外部因素作用于这些对象上后，冲突就会发生，因为处于冲突中的对象本身并不能导致冲突的发生。换句话说，当冲突发生后，外部因素和这些对象之间就建立了一种关系，我们称这种关系为一个冲突过程或一个冲突事件。我们知道，粒计算是一门研究基于多层次粒结构的思维方法、问题求解方法、信息处理模式及其相关理论、技术和工具的学科。它覆盖了所有和粒度相关的理论、方法和技术。如果我们将冲突看成是有着不同结构层次的粒化过程的话，将会有一些非常有意思的发现，也就是说有这样一些情况，单个冲突事件或过程中事实上包含了两个或两个以上的冲突关系。

29

第四章 基于覆盖粒计算的关联冲突分析

4.4.1关联冲突定义

图4.1 关联冲突

受粒计算思想理论的启发，我们引入了关联冲突（如图4.1所示），在给出概念之前先对这个流程图做一下详细的解释：

这个图可以被看作是一个冲突过程或事件，在这个过程或事件当中有两个分别代表着不同冲突层次的关系。一个是处于第一层次上的主动关系，用来表示agents和冲突对象集之间的关系，其中agents是主体而冲突对象是客体，主动关系可以随agents的改变而改变，例如agents的个数、范围和顺序等，agents在这个关系中是外部因素或触发源，当agents作用于这些冲突对象后，利益冲突就会发生，即关系就会建立（如例4.2中一个工作人员访问了需要访问的公司的数据库后）；对于所有的agents来说，另一个关系是处于第二层次上的隐含关系，它是一个固定的不能被改变的关系，用来表示冲突对象集和隐含的冲突对象集之间的关系，就像一个工程需要一些固定的不变的程序或资源一样，每个冲突对象也固定不变的需要一些隐含的冲突对象的支持，因此这个关系是不能改变的，它是固定，也就是说冲突对象集和隐含的冲突对象集之间的关系本来就有的，另外，二者都是冲突源，相对于隐含的冲突对象集来说，冲突对象集是外部因素，但相对于agents来说，隐含的冲突对象集就是隐含着的了。 评论4.3 正如图4.1所示，我们称这个过程或事件为关联冲突，它是由两个独特的关系连接着一个触发源、一个冲突对象集源和一个隐含的冲突对象集源组成。因此，我们也可以定义多联冲突，它是由至少三个关系连接一个触发源、一个冲突对象集源和至少两个以上的隐含冲突对象集源组成，隐含的冲突对象集之间的关系可以如上面描述的隐含关系。

4.4.2关联冲突分析建模

为了能尽可能全面的分析关联冲突的各种情况，我们将以服务——资源为例，不考虑相关的应用背景，意图是为了帮助了解关联冲突的概念和构建关联冲突的分析模型。而进一步的相关应用背景的分析将在4.5节进行讨论。

30

第四章 基于覆盖粒计算的关联冲突分析

表4.2 服务的利益冲突关系

表4.3 资源的利益冲突关系

service A A A B B C C C C D D E E E E F G service B C E A C A B D E C E A C D G G F

resource a a a a b c c c d d d d d d resource d f g h f d e g a c e f g h resource e e e f f f f g g g g g h h resource c d g a b d g a c d e f a d 为了方便起见，我们将表4.2和4.3的表头用相应的英文表示。

假设：有七种服务（冲突对象集），U1?{A,B,C,D,E,F,G}，这七种服务之间的

U2?{a,b,c,d,e,f,g,h} 利益冲突关系如表4.2所示；有八种资源（隐含的冲突对象集），

，这八种资源的利益冲突关系如表4.3所示。

因此，在表4.2中，每一个服务的冲突集是conflict(A)?{B,C,E}，

31

第四章 基于覆盖粒计算的关联冲突分析

conflict(B)?{A,C}，conflict(C)?{A,B,D,E}，conflict(D)?{C,E}，conflict(E)?{A,C,D,G}，conflict(F)?{G}，conflict(G)?{E,F}和同盟集是all(y)?A{,AD,F,，Gally(B)?{B,D,E,F,G}，ally(C)?{C,F,G}，ally(D)?{A,B,D,F,G}，ally(E)?{B,E,F}，ally(F)?{A,B,C,D,E,F}，ally(G)?{A,B,C,D,G}。

在表4.3中，每一个资源的冲突集是conflict(a)?{d,f,g,h}，conflict(b)?{f}，

conflict(c)?{d,e,g}，conflict(d)?{a,c,e,f,g,h}，conflict(e)?{c,d,g}，

conflict(f)?{a,b,d,g}，conflict(g)?{a,c,d,e,f}，conflict(h)?{a,d}和同盟集是ally(c)?{a,b,c,f,h}，ally(d)?{b,d}，ally(a)?{a,b,c,e}，ally(b)?{a,b,c,d,e,g,h}，

ally(e)?{a,b,e,f,h}，ally(f)?{c,e,f,h}，ally(g)?{b,g,h}，ally(h)?{b,c,e,f,g,h}。

服务集和资源集都是冲突源，所以他们的关系（隐含的固有不变的关系）是固有的不变的。我们假定他们之间的关系是A?{a,c}，B?{g,a,h}，C?{a,b}，

D?{d,f}，E?{c,e,b,g}，F?{d}，G?{h,f}。因此，对于给定的冲突源来说，关

系是已经确定了的，不能改变且不受任何外界因素的影响。

现在有五个agents（外部因素或触发源）作用于（访问或需求）这些服务。这样二者之间的关系（主动关系）已经建立了，假定他们之间的关系是agent(1)?{D,A}，

agent(2)?{A,G}，agent(3)?{E,B,D}，agent(4)?{C}，agent(5)?{D,F,C,G}，

因为agents是外部因素，所以二者之间的关系可以随agents的个数、优先级和访问或需求范围等因素而改变。

为了让关联冲突分析的模型更具有适应性和普遍性，我们做如下假设（外部条件）：第一层次的冲突源中每个服务的优先级是相同的；第二层次的冲突源中每一个资源的优先级也是相同的并且每个资源同一时间可以最多使用三次，即每个资源同一时间可以最多提供给三个服务使用（每个资源的数量在不同的应用背景下可以是不同的或者是互不相同的）；另外，访问或需求服务的每个agent的优先级可能不同，优先级向量暂设为x?(215,415,615,115,215)（可以改变），其中

1?p?|agent|且|x|?|agent|，对应着每一个

|agent|?p?1x(p)?1，

agent的优先级。其他的一些外部条件将

在4.5部分进行讨论。

最后，根据覆盖冲突分析模型的授予的访问权和需求权策略，我们可以构建关联

32

本文来源：https://www.bwwdw.com/article/py96.html