论文部分内容阅读
1982年,Z.Pawlak教授提出了粗糙集理论,为现实世界中粗糙现象的解释及粗糙问题的解决提供了理论工具。2002年,史开泉教授将Z.Pawlak粗糙集推广,提出了具有动态特性的粗糙集——奇异粗糙集(Singular Rough Set),简记为S-粗糙集,这使得粗糙集具有更广泛的应用领域。本文以提高粗糙集、S-粗糙集的计算能力为出发点,分别将粗糙集、S-粗糙集与传统图论相结合构造了粗糙图和S-粗糙图,并进一步给出了它们的理论及应用研究。本文的主要研究内容及创新点如下:·主要研究内容构造了粗糙图和S-粗糙图并分别讨论了它们各自的特性;构造了赋权粗糙图、粗糙网络,又将传统赋权图和传统网络中的经典算法推广到赋权粗糙图和粗糙网络中并给出了新算法的应用;最后,构造了基于代数算子的粗糙图结构,并给出了研究粗糙集之间代数关系的图结构分析法以及该方法的应用。第一章绪论,首先介绍了Z.Pawlak粗糙集理论的提出背景、发展和研究近况,并叙述了Z.Pawlak粗糙集的定义和性质。进一步的,给出了S-粗糙集与函数S-粗糙集的基本概念,为以后各章的讨论提供了理论基础。第二章为了提高粗糙集本身的计算能力并能利用图论知识分析粗糙现象,解决粗糙问题,首先通过将传统图论与Z.Pawlak粗糙集相结合构造了粗糙图并给出了它的基本性质。其基本思想是:从传统图的结构入手,将边的两个顶点看成边的属性,并进一步允许边具有多种属性,从而构造了边的属性集合,进而定义了粗糙图。其次,借鉴传统图的各种表示形式,给出了粗糙图占内存空间较小的两种表示形式:邻接矩阵和边目录,为粗糙图的计算奠定基础。再次,对粗糙图的粗糙性进行了较详细的分析,定义了边精度、粗相似度等概念并给出了它们的一些性质。最后,定义了粗糙图中的几种重要子图,如:类路、类圈、类树等,并对粗糙图的类连通性作了分析。第三章针对实际应用分析中做比较的需要,首先通过对粗糙图的边增加权重属性构造了赋权粗糙图,同时定义了赋权粗糙图中的类最短路、类最优树。为了便于计算,又给出了赋权粗糙图的两种表示形式:权矩阵和权目录。其次,分别将传统赋权图中的最优树和最短路算法加以推广,得到了赋权粗糙图中类最优树算法(COTA)和类最短路算法(CSPA),并将它们应用于同一关系层面之内的关系挖掘。第四章针对实际应用分析中区分方向性的需要,首先分别通过单独对粗糙图的边增加方向属性和同时对粗糙图的边增加方向属性和权重属性,构造了有向粗糙图和粗糙网络,同时给出了有向粗糙图中的有向类路和粗糙网络中类流等重要概念。为了计算需要,有向粗糙图和粗糙网络也分别有两种表示形式:有向粗糙图的邻接矩阵和弧目录以及粗糙网络的权矩阵和权目录。其次,将传统网络中的最大流算法加以推广,得到了粗糙网络中的类最大流算法(CMFA),并将其应用于不同关系层面之间的关系挖掘。第五章针对分析研究动态粗糙问题的需要,首先将传统图论与S-粗糙集相结合,构造了S-粗糙图并分析了它的基本性质。其次,相对于粗糙图给出了只存在于S-粗糙图中的具有动态特性的子图及其性质,例如:F-类路,(?)-类路,(?)-类路等。最后,借用粗相似度这一概念比较分析了粗糙图与它的S-粗糙图之间的关系,以便利用粗糙图中的信息和结论来研究它的S-粗糙图。第六章以粗糙集为顶点,粗糙集之间经过代数运算后的结果作为边构造了新的基于代数算子的粗糙图结构,同时提出了研究粗糙集之间代数关系的图结构分析法。又结合基于粗糙集的情感模型,将图结构分析法成功的应用于人工智能领域的热门课题——情感计算中。最后一章总结全文。·本文的创新点创新点1.结合传统图论与粗糙集构造了粗糙图。这是首次将粗糙集与图论知识结合,不但为粗糙集理论的研究开辟了新的领域,而且应用图论中的经典算法提高了粗糙集本身的计算能力,同时使得图论可用于粗糙问题的研究,扩大了图论的应用范围。创新点1列于第二章中。创新点2.通过对粗糙图的边增加不同的属性,构造了赋权粗糙图、有向粗糙图和粗糙网络。并且将传统图论中的最优树、最短路以及最大流算法加以推广得到了类最优树算法(COTA)、类最短路算法(CSPA)和类最大流算法(CMFA)。这些新粗糙图的构造及新算法的设计,不但丰富了粗糙图理论,而且新算法的应用还建立了一套较合理的关系分析与挖掘体系。创新点2列于第三、四章中。创新点3.结合传统图论与S-粗糙集,构造了S-粗糙图,这使粗糙图可应用于具有动态特性粗糙问题的研究。创新点3列于第五章中。创新点4.以粗糙集为顶点,粗糙集之间经过代数运算后的结果作为边构造了新的粗糙图结构,同时提出了粗糙集之间代数关系分析的图结构分析法。进一步的,通过利用粗糙集对情感进行建模,使得该方法成功的应用于情感计算中情感迁移规律的挖掘。创新点4列于第六章中。