概念格构造的两种新方法

发布时间：2018-03-19 01:37

本文选题：概念格　切入点：概念　出处：《河北大学》2017年硕士论文　论文类型：学位论文

【摘要】：概念格理论(Concept Lattice Theory),也称形式概念分析(简称FCA),是1982年由德国数学家R.Wille提出的,主要用于描述形式背景中对象和属性之间的关系。对于一个给定的形式背景,其概念由内涵和外延两部分组成,而概念格是给定形式背景的所有概念的分层结构,因此,如何快速地构造概念格是概念格理论研究的一个重要内容。本文在研究了已有概念格构造算法的基础上,一方面结合图论的思想提出了一种新的概念格构造算法,另一方面依据用户需求,原形式背景中某些属性和对象将不再需要,这使得将形式背景中的一些属性和对象进行删除成为必然。对于属性和对象同时减少后的形式背景,提出一种通过原概念格得到新形式背景下的概念格的便捷有效的概念格构造算法。主要研究内容如下:1.在已有的形式背景之属性拓扑图的基础上,定义了一种弱化的属性拓扑图,从而得到一种概念格的构造算法。算法过程如下:首先,构造形式背景之弱化的属性拓扑图;其次,通过在弱化的属性拓扑图中,寻找每个权值最大圈用以生成概念,进而生成形式背景的所有概念;之后,构造出概念格。通过分析说明此算法复杂度较以往的一些算法复杂度降低。此外,通过一个实例,验证了这一算法的有效性。2.对于依据用户需求的形式背景,提出了一种概念格的构造算法并给出理论证明。算法过程如下:首先,根据形式背景的概念格Hasse图的构造,按照内涵个数将原形式背景的概念格进行分层;其次,按照自底向上的规则,对层中的概念依次判断其类型,以此得到该层中的概念;再者,得到新形式背景下的所有概念。最后,通过一个实例,说明算法的有效性。
[Abstract]:Concept Lattice Theoryn, also known as formal conceptual analysis, was proposed by German mathematician R. Wille in 1982. It is mainly used to describe the relationship between objects and attributes in formal background. The concept consists of two parts: intension and extension, and the concept lattice is the hierarchical structure of all concepts with a given formal background. How to construct concept lattice quickly is an important part of concept lattice theory. Based on the research of existing concept lattice construction algorithm, a new concept lattice construction algorithm based on graph theory is proposed in this paper. On the other hand, some properties and objects in the original formal background will no longer be required according to the user's requirements, which makes it necessary to remove some attributes and objects from the formal background. This paper presents a convenient and effective algorithm for constructing concept lattices under new formal background by using original concept lattices. The main contents of this paper are as follows: 1. On the basis of attribute topology graph of existing formal background, In this paper, a weak attribute topology graph is defined and an algorithm for constructing concept lattices is obtained. The algorithm is as follows: firstly, we construct a weakened attribute topology graph of formal background; secondly, we construct a weak attribute topology graph in a weakened attribute topology graph. The concept lattice is constructed by searching for the maximum cycle of each weight value to generate the concept and then to generate the formal background. The complexity of this algorithm is lower than that of some previous algorithms through analysis. In addition, through an example, the complexity of the algorithm is reduced. The validity of the algorithm is verified. 2. According to the formal background of user requirements, a concept lattice construction algorithm is proposed and the theoretical proof is given. The algorithm process is as follows: firstly, according to the construction of the formal background concept lattice Hasse graph, The concept lattice of the original formal background is stratified according to the number of connotations; secondly, according to the bottom-up rule, the concept in the layer is judged in turn and the concept in that layer is obtained. Finally, an example is given to illustrate the effectiveness of the algorithm.
【学位授予单位】：河北大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O153.1;O157.5

【参考文献】