【作者】 何童；

【导师】 史开泉；

【作者基本信息】 山东大学 ， 系统理论， 2008， 博士

【摘要】 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列于第六章中。更多还原

【Abstract】 In 1982,Professor Z.Pawlak presented rough set theory,which provides theory tool for explanation of rough phenomena and solution of rough problems in the real world.In 2002,by extending Z.Pawlak rough set Professor Shi Kaiquan presented singular rough set which has dynamic properties,denoted as S-rough set for short,which enables rough set to apply to more fields.This thesis aims to improve computation ability of rough set and S-rough set and constructs rough graph and S-rough graph by combining classical graph theory with rough set and S-rough set respectively.Furthermore,this thesis gives theory and application researches of rough graph and S-rough graph.The main research contents and innovation points of this thesis are as follows:·Main Research ContentsRough graph and S-rough graph are constructed and their properties are discussed respectively.Weighted rough graph and rough network are constructed.Some important algorithms of weighted rough graph and rough network are designed by extending corresponding algorithms in classical weighted graph and classical network and their applications are also given.Finally,a new rough graph structure which based on algebraic operators is constructed.The graph structure analysis method of algebraic relationship among rough sets is presented and its application is also given.Chapter 1 firstly provides a brief introduction of background and recent situation of development and research of rough set and gives definition and properties of Z.Pawlak rough set.Secondly,it gives definition of S-rough set and function S-rough set,which provide theory basis for the research in the following chapters.Chapter 2 firstly constructs rough graph by combining classical graph with Z.Pawlak rough set for the purpose of improving computation ability of rough set and analyzing rough phenomena and solving rough problems by using graph theory knowledge.The basic idea is that based on the structure of classical graph,take vertices of an edge as its attribute.Furthermore,allow edge to have more attributes and construct attribute set of edge,so get the definition of rough graph.Secondly,based on several kinds of representation form of classical graph,two presentation forms of rough graph which take up less computer space are presented,and they are adjacency matrix and edge list,which supplies convenience for the computation in rough graph.Thirdly,the rough characteristic of rough graph is analyzed in detail.Some conceptions such as edge precision,rough similarity degree and so on are defined and their properties are also given.Finally,some kinds of important subgraph of rough graph such as class path,class cycle,class tree and so on are defined and the class connection of rough graph is analyzed.Chapter 3 firstly constructs weighted rough graph by adding weight attribute to edge of rough graph for the necessity of doing comparison in actual application,and some conceptions in weighted rough graph such as class shortest path,class optimum tree and so on are defined.For the convenience of computation,two representation forms of weighted rough graph are given,which are weight matrix and weight list.Secondly,class optimum tree algorithm(COTA) and class shortest path algorithm(CSPA) in weighted rough graph are designed by extending optimum tree algorithm and shortest path algorithm in classical weighted graph respectively and they are successfully applied to relationship mining at same relationship level.Chapter 4 firstly constructs directed rough graph and rough network by only adding direction attribute to edge of rough graph and adding both direction attribute and weight attribute to edge of rough graph at same time respectively for the necessity of differentiating direction in actual application.Meanwhile,some important conceptions such as directed class path in directed rough graph,class flow in rough network and so on are given.For the convenience of computation,two representation forms of directed rough graph and rough network are represented respectively,which are adjacency matrix and arc list of directed rough graph and weight matrix and weight list of weighted rough graph.Secondly,class maximum flow algorithm(CMFA) in rough network is designed by extending maximum flow algorithm in classical network and it is successfully applied to relationship mining between different relationship levels. Chapter 5 firstly constructs S-rough graph by combining classical graph with S-rough set for the necessity of analyzing rough problem which has dynamic properties,and its basic properties is also analyzed.Secondly,some subgraphs which have dynamic properties and only exist in S-rough graph are presented,such as F-class path,F-class path,(?)-class path and so on and their properties are also given.Finally,the comparison between rough graph and its S-rough graph is given by using rough similarity degree, which enables us to analyze S-rough graph according to the information and results of rough graph.Chapter 6 constructs a new rough graph structure by taking rough set as vertex and the result of algebraic operation between rough sets as edge.Furthermore,graph structure analysis method of algebraic relationship analysis among rough sets is presented and it is successfully applied to affective computing,which is one of hotspots in artificial intelligence field.Chapter 7 concludes the whole thesis.·Innovation Points of ThesisInnovation point 1.Rough graph is constructed by combining classical graph theory with rough set.This is the first time to combine rough set with graph knowledge,which is not only a new research direction of rough set theory,but also the algorithms in classical graph theory can improve the computation ability of rough set.Furthermore,rough graph enables graph theory to research rough problem,which widen the application field of graph theory.Innovation point 1 can be found in Chapter 2.Innovation point 2.Weighted rough graph,directed rough graph and rough network are constructed by adding different attributes to edge of rough graph.And class optimum tree algorithm(COTA),class shortest path algorithm(CSPA) and class maximum flow algorithm(CMFA) are designed by extending optimum tree algorithm,shortest path algorithm and maximum flow algorithm in classical graph.The construction of new kind of rough graphs and designation of new algorithms not only enrich rough graph theory, but also the applications of new algorithms still have built a rational relationship analysis and relationship mining system.Innovation point 2 can be found in Chapter 3 and Chapter 4. Innovation point 3.S-rough graph is constructed by combining classical graph theory with S-rough set theory,which enables rough graph to research rough problems that have dynamic properties.Innovation point 3 can be found in Chapter 5.Innovation point 4.A new rough graph structure is constructed by taking rough set as vertex and the result of algebraic operation between rough sets as edge.Meanwhile, graph structure analysis method of algebraic relationship analysis among rough sets is presented.Furthermore,by modeling human emotions based on rough set,this method is successfully applied to mining affective transfer law in affective computing,which is one of hotspots in artificial intelligence field.Innovation point 4 can be found in Chapter 6.更多还原