覆盖粒计算及其应用研究_硕士学位论文(编辑修改稿)

覆盖粒计算及其应用研究_硕士学位论文(编辑修改稿)内容摘要：

因与结果之间的必然联系。 粒计算模型应该能描述这三种能力。 因而粒计算的结构和现实世界的结构、人们的思维模式及行为方式是一致的。 其二是系统性：粒计算的结构 提供了对所解决 的问题多视角、多层次的理解、概括和操作。 作为一个整体，粒计算提供的思维模式和行为方式是系统的、完整的。 其三是简化性：粒计算是提倡第 一 章 绪 论 2 对问题进行不同层次的抽象和处理。 在抽象过程中，可以只重视主要特性而忽略不相关的细节，从而达到对问题的简化。 其四是灵活性：粒计算的结构允许人们在不同的时 间、不同的情况下，将注意力集中在不同的层次及层与层之间的自然过渡上，缩放和转承是灵活多变的。 其五是有效性：用粒计算指导的思维模式和行为方式将复杂问题分解成若干小问题。 这种分而治之的方法是非常实用的，可以运用到不同的领域。 其六是经济性：粒计算寻求在不同粒度上的近似解。 这样的方法可以提高效率、降低成本。 其七是容忍性：通过使用不同信息粒度，粒计算可以容忍不确定、不完全或有噪音的信息，从而获得具有鲁棒性的解决方案。 粒计算 任务和目标 粒计算的形成综合了许多学科的科研成果 [14]，它的理论建立在对各个领域的 共性进行概括、总结和整理之上，形成了对问题求解的普遍适用的原理、方法和策略。 在过去的若干年中，许多学者对粒计算的具体模式和方法进行了研究。 同时和粒计算原理相似的研究还在不断地出现，只是在不同 的领域中运用了略微不同的名词和术语。 将粒计算作为一个独立的学科研究可以防止这种不必要的重复劳动。 (1) 粒计算的任务 作为一个新兴的研究领域，粒计算是一门关于问题求解的艺术。 它有着两项特殊的任务：其一是从各个不同的领域中概括出它们的共性，不考虑它们低层次上的差异，从而提炼出抽象的、高层次的、综合的认识；其二是将特定 领域中隐含的结构明确化，以期总结出独立于具体领域的普遍原理。 (2) 粒计算的目标 粒计算之所以新且独特，并不完全在于一组具体的方法和策略，而在于提出一个统一的框架，对这些方法和策略进行全面的理解及综合。 通过对粒计算的研究试图达到以下目标： 将隐式的结构显式化；将不明显的原理明显化；将特定领域的特殊原理普遍化；将下意识的行为变成有意识的行为。 粒计算基本要素 和理论构成 (1) 粒计算的基本要素 [14, 15] 第 一 章 绪 论 3 (a) 粒 粒是粒计算的初始概念，是粒计算研究对象的单位，是求解问题的基本 单位， 等同于数据库中的记录，集合中的元素或子集。 我们称最小的、不可分或不需要再分解的粒为基本粒，即最低层次的粒称为基本粒，它可以是模糊的，也可以是精确的。 粒 具有 双重身份，它可以是某个整体中相对独立的一个部分，也可以是一些粒共同组成的一个粒。 所有的粒 都具有内在属性、外在属性和环境属性。 当粒作为整体时，所要考虑的是 粒的内在属性，内在属性由粒所拥有的元素决定。 当粒作为部分时， 所要考虑的是粒的外在属性，由于具有外在属性，粒就能够被人们直接认识。 粒的环 境属性是指粒对外部环境变化的应对情况，对其内在属性和外在属性的保 持与调整以及对外部环境的影响和回应。 粒的双重身份决定了它 的内在属性通常需要强调 其它所包含的细小个体的不同特性，是对它内部各个基本组成成分性质的描述，而其 外在属性则是强调把它 作为 一个整体时所体现出的综合特性。 (b) 层次 粒存在于特定的层次中， 人们在粒计算的不同层次中研究不同类型的 粒，这些粒之间是有联系的，同一层次的粒与粒之间可以是相交的关系 也可以是层叠的关系 ， 它们是该层次上研究的主体。 层次中每一个粒表述了一个特定的粒化观点。 所有的粒化观点相互补充、相互呼应，完整表达了在这个层次上对 同 一个问题的描述。 每个层次都具有内在属性、外在属性、环境属性，同一层次的粒属性共同体现本层次特性。 在问题求解中，选择在最合适的粒度层次上产生对一个问题的描述，能帮助更好更快地解决问题。 较高层次包含较低层次，或者由较低层次组成。 较高层次为较低层次提供背景和约束。 较高层次一般由 较高集成度和较高结合力的 粒组成。 每一 层次都存在一定 程度 的独立性。 任意两层次之间的连接和交互 是通过偏序关系的传递性和桥接原理来表示和体现的。 粒计算模型的主要作用是能够在不同粒度层次上进行问题求解，使不同粒度层次上的解能够进行相互转化。 (c) 分层结构 分层结构由若干个层次组成，层次间的递进反映了由表及里、由抽象到具体、由粗糙到细致、由笼统到具体的变化。 这种递进是有序的，高层次会对低层次进行约束，第 一 章 绪 论 4 并为低层次的描述提供背景。 一个高层次的粒可以分解为若干个低层次的粒。 相反，若干个低层次的粒可以组合成一个高层次的粒。 低层次的粒为高层次的粒提供更详细的描述或者更多的信息。 另一个方面，高层次的粒将与本层次的不相关的细节忽略掉，为低层次的粒提供更粗粒度的描述。 (d) 粒结构 在粒计算研究中强调的是全面、整体的观点，而不是局部、离散的观 点。 若要达到该目标，不仅要考虑一个分层结构中的多个层次，还需要将多个分层结构综合考虑。 粒结构包括三个要素，即粒的内在结构、粒的结构、粒的总体结构，它是多层次和多个分层结构的结合。 粒计算借助于其他学科的哲学思想和方法论，并将它们抽象成为与具体领域无关的方法和策略。 它的独特性体现在用系统的、结构化的理解和方法来解决复杂问题。 对复杂问题的全面理解通常是多视角的，从每一个视角着眼的理解又是多层次的。 由此可以得出，粒计算的过程就是对复杂问题的求解过程。 它的结果表现为一个多视角、多层次的粒结构。 这个粒结构是对复杂问题 的系统且近似的描述和解答。 (2) 粒计算的理论构成 [7, 8] 目前，粒计算有 3 个主要理论 以及其它一些非主流理论： 其一是 词计算理论：人类思考、判断、推理主要是用语言，而语言是一个很粗的粒，如何用语言进行推理判断，这就是词计算。 其二是 商空间理论：商空间理论把概念用子集表示，不同粒的概念体现为不同粒的子集，一簇概念构成空间的一个划分 —— 商空间，不同的概念簇就构成了不同的商空间。 故粒计算，就是研究在给定知识基上的各种子集合之间的关系和转换，以及对同一问题取不同的适当的粒，从对不同的粒的研究中，综合获 取对原问题的了解。 其三是 粗糙集理论：粗糙集理论于 1982 年由 Pawlak 提出，它是一种刻划不完整性、不确定性的数学工具，主要解决信息粒的近似方面的问题。 另外许多学者也在研究粒计算，并将各种相关理论用于粒计算，有邻域系统粒计算 、信息熵粒计算、概念格粒计算、覆盖粒计算 、进化粒模型、基于 相容粒度空间 的粒计算 模型 以及各模型相互交叉整合的模型方法等 ， 在许多领域中 得以 实现或应用。 第 一 章 绪 论 5 粒计算研究 方向 与 方法 粒计算的形成和发展积累了多种思想、模型、范式、方法论、技术及工具。 对粒计算的研究应该着眼于三个观点 [2]：粒 计算的哲学思想观点、方法论观点及计算模式观点。 从哲学思想观点考虑，粒计算试图将人类的认知方式抽象化、形式化，从而提炼出结构化的思维模式 ，而结构化的思维模式是人类智能的重要体现，它对设计基于知识的信息系统有着非常重要的影响 ， 它有两个基本假设 ：一个是所有问题都可以视作是其内在要素之间的网络状或分层结构的关联，另一个是所有的问题都有着类似的模式和特征 ；从方法论观点考虑，粒计算着重研究系统化的方法和技术，将问题求解的过程规范为结构化的、自上而下的逐步求精过程；从计算模式观点考虑，粒计算关注于结构化的信息处理。 信息处 理是有层次的，其研究领域涉及抽象的信息处理、人脑中的信息处理及计算机中的信息处理。 计算模式是方法论的具体表现形式。 在计算机学科中，人们通常将兴趣集中在基于计算机的信息处理模型上，并将其独立出来进行分析。 粒计算的哲学研究基于粒结构的思维方式。 基本 问题 [7, 10, 15]包括：如何定义粒、层次及分层结构的内在属性、外在属性和环境属性；如何定义它们的关系；如何准确表达它们的关系；如何实现它们的关联和切花；如何使它们的综合功能最大化。 哲学层面的研究是抽象的，同时又是方法论和计算模式的前提和保障。 粒计算的方法论 致力于将粒计算哲学思想具体到问题求解的方法、技术和工具的研究和开发中去。 需要考虑到粒计算方法的有效性、可靠性、准确性、简便性、计算成本和价值。 对于不同的应用还需考虑其问题的特定及限制。 粒计算的信息处理强调以计算机为主体的信息处理与以人为主体的信息处理的差别。 一方面，以计算机为主体的信息处理依靠人来制定、设计、实施和优化；另一方面，计算机的信息处理也促进方法论的研究。 粒计算的哲学思想和方法论的完善为计算机的信息处理实践提供了可以依据的准绳和保障，计算机的信息处理实践反过来也会促进对粒计算哲学思想和方法论的研 究，成为支持粒计算哲学思想的有力证据和改善粒计算方法论的原动力。 总之，如何定义粒 （粒化） 以及如何选择合适的粒度是粒计算解决问题的首要任第 一 章 绪 论 6 务 [6, 9]。 粒计算基本思想和实质 粒计算从不同粒层次上研究问题，从人类求解问题的经验方法中提取基本原理如粒、层次、等级。 从人类思考和求解问题上看，“人类以粒的观点看世界”，“人们观察、衡量、概括和推理的实体都是粒” [16]。 当人们面对复杂的、难于准确把握的问题时由于能力有限，通常不是采用系统、精确的方法去追求问题的最优解，而是通过逐步尝试的办法达到有限的、合 理的目标，也就是采用由粗到细、不断求精的多粒度分析法，避免复杂的计算，从而获得足够满足的解，使得原来看似非多项式的难解问题迎刃而解。 人类智能的一个公认特点，就是人们能从极不相同的粒上观察和分析同一问题。 人们能在不同粒的世界上进行问题求解，且能够很快地从一个粒世界跳转到另一个粒世界，往返自如，毫无困难。 这种处理不同粒世界的能力，正是人类问题求解的强有力的表现，这也正是 粒计算的基本思想 [4]。 粒计算方法是人工智能领域中的一种新理念和新方法，它覆盖了所有和粒度相关的理论、方法和技术， 在可以容忍的程度内， 主要用于对 不确定、不准确、不完整信息的处理，对大规模海量的数据和对复杂问题的求解 ，使其达到可处理性、鲁棒性、小代价和谐调性。 粒计算的实质 [4]就是通过选择合适的粒度，来寻找一种较好的、近似的解决方案，从而降低问题求解的难度。 而 事实上， 从真实世界上看，许多自然系统、社会系统、人工系统都是基于层次的，粒计算可以真实自然地表示这类系统。 从简化问题上看，多层系统的不同层次关注不同的粒特征，粒计算忽略了不必要和不相关的细节，只关注适当层次，从而简化了问题。 从实用角度上看，许多问题是不完整的、不确定的，或者含有模糊信息，很难区 分元素，只能认为是粒。 且在许多实际问题中也不要求精确解，或者获取精确信息的代价不菲， 粒计算可以 提高效率和降低代价。 覆盖广义粗糙集 理论 定义 [17] 设 U 是非空有限论域， P 是 U 上的一簇子集 且 PU ， 对于任意第 一 章 绪 论 7 12,P P P ， 如果 12PP ， 那么 P 为 U 的一个 划分。 定义 [33] 设 U 是非空有限论域， C 是 U 上的一簇子集，如果 C 中任一子集非空且CU ，则 C 为 U 的一个覆盖。 覆盖广义粗糙集的研究背景 随着计算机及网络的日益普及，丰富的数据与贫乏的知识之间的矛盾日渐突出。 不同领域的人都希望能从复杂的数据中得到自己所需要的知识，因此数据挖掘这门学科就应运而生了。 该学科涉及分类、概念形成和数据分析。 这些都需要对不完全和不充分的信息进行处理，围绕这个问题产生了许多理论，如模糊理论、神经网络、商空间理论、词计算、粗糙集理论等。 而其中的粗糙集理论 [17]于 20 世纪 80 年代提出以来，无论从理论上还是从应用上都取得了丰硕的成果，尤其在数据挖掘领域里 [18]。 它是通过不可区分关系为不完全和不充分信息的处理提供了一套系统的方法。 通常，人们用一组属性来描述事物，不可区分关系就是由这些事物相应的属性值来定义的。 如果两个事物对于这组属性的属性值相等，也就是说具有相同的描述，就认为它们是不可区分的。 从集合中关系这个角度来看，这种不可区分关系实际上就是 等价关系。 这样，所有具有相同描述的事物构成一个等价类，而所有的等价类构成所考虑事物的一个划分。 在粗糙集理论中，这些等价类又称为初等 集，若干个初等集的并称为确定。 利用这个划分，任意的事物的集合可以用两个确定集来上下逼近，这两个确定集分别是该事物集合的上近似和下近似。 它无需提供问题所需处理的数据集合之外的任何先验信息，对问题的不确定性的描述或处理是比较客观的。 由于这个理论未包含处理不精确或不确定原始数据的机制，所以与概率论、模糊数学和证据理论等其他处理不确定或不精确问题的理论有很强的互补性。 而随着粗糙集理论得到广泛的应用以来 ， 为使该理论能有更大的应用空间， 人们对 Pawlak 粗糙集理论进行了许多有意义的推广，如将等价关系放宽为相容 关系 [19]、相似关系 [20]、一般二元关系 [21]；与模糊理论结合，将粗糙集理论推广到模糊粗糙集理论 [22]和广义模糊粗糙集理论 [23]；将经典粗糙集模型推广到变精度粗糙集模型 [24]；从等价关系等同于划分这个角度出发， Zakowski 把划分放宽为覆盖 [25],将 Pawlak 粗第 一 章 绪 论 8 糙集理论推广到覆。