ABSTRACT

The concept lattice is the structure of dates which is established according to the information in formal context. This structure reveals the nature of the relationship between attributes of the object. It is an effective tool for concept discovery from dates and has been widely used in information retrieval, digital library, software engineering and knowledge discovery. The attribute reduction is important. There are a lot of similarities in the research technique between formal context and topology. This paper tries to watch attribute reduction in concept lattice from the perspective of topology, establishing some connections with subbase reduction in topology. This paper tries to define the restrictions and product of formal context according to the definition of a new topological space, looking whether some topological property can be maintained. Thus the content of formal context has been enriched in some degree.

Keywords:Formal Context, Concept Lattice, Attribute Reduction, Distinguishable Attributes Matrix, Subbase Reduction

概念格与拓扑

李伯权¹，鲍玉曦²

¹安徽师范大学数学计算机科学学院，安徽 芜湖

²南京师范大学附属中学树人学校，江苏 南京

收稿日期：2016年9月5日；录用日期：2016年9月20日；发布日期：2016年9月26日

摘 要

概念格是根据形式背景中信息建立起来的数据结构,这一结构从本质上揭示了对象与属性之间的关系。它是数据中概念发现的有效工具，广泛应用在情报检索、数字式图书馆、软件工程和知识发现领域。概念格中的属性约简是其研究的一个重要内容。鉴于形式背景与点集拓扑这两者在研究方法上有许多相似之处，本文尝试从拓扑学角度来观看概念格中的属性约简，建立其与拓扑学中子基约简的某种联系。接着由拓扑子空间的构造方法来定义形式背景上的限制及叉乘，看是否能保持一些拓扑性质的不变，从而丰富了形式背景的研究内容。

关键词 :形式背景，概念格，属性约简，可辨识属性矩阵，子基约简

1. 引言

Wille.R于1982年提出的形式概念分析 [1] [2] 是以序理论和完备格理论为基础，依据数据库中提供的基本信息建立起来的一种刻画对象和属性之间的关系的数学结构，这种概念及概念层次的数学化使形式概念分析成为数据挖掘与知识发现的重要方法，并广泛应用于许多领域。形式概念分析与点集拓扑这两者在研究方法上有许多相似之处，本文尝试从拓扑学角度来观看概念格中的属性约简。文献 [3] 中，作者张文修等给出了若干协调集判定定理以及寻找属性约简的方法，本文由该文献中证明的一个协调集判定定理出发，建立起概念格中的属性约简与拓扑学 [4] - [7] 中子基约简的某种联系。本文还从构造拓扑子空间的方法来定义形式背景上的限制及叉乘，从而看是否能保持一些拓扑性质的不变。

2. 概念格的属性约简与拓扑子基

2.1. 概念格的基本概念与性质

定义2.1.1 [2] 称为一个形式背景，其中为对象集，每个称为一个对象。为属性集，每个称为一个属性。为与之间的二元关系，即。若，则说具有属性，记为，否则说不具有属性，记作。

若用1表示，用0表示，则形式背景就可以表示为只有0与1的表格。

对于形式背景，，，分别定义运算：

，

简记为，简记作。若且，且，则称形式背景是正则的。对于形式背景的正则性表现为：该形式背景所表示的0-1表格不会有全为0或全为1的行与列。本文所研究的形式背景都是正则的。

定义2.1.2 [2] 设为形式背景，若二元组满足且，则称是一个形式概念，简称概念(在形式背景中一般用表示)，其中称为概念的外延，称为概念的内涵。

形式背景的概念可以用超概念与子概念的关系来定义它们之间的序关系：

的所有概念按以上偏序关系“≤”构成一个偏序集，记为，称为概念格。其中上、下确界定义如下：

形式背景的概念有以下基本性质 [2] ：

1)，；

2)，；

3)，；

4)；

5)，；

6)，；

7)和都是概念。

定义2.1.3 [3] 设是形式背景，，称

为与的可辨识属性集，称

为形式背景的可辨识属性矩阵。

在形式背景的可辨识属性矩阵中，只有非空元素对我们的研究有意义，因此我们不加区别的把非空元素的集合记为。

定义2.1.4 [3] 设和是两个概念格，若对于，总存在，使得，则称细于，记作：。

若且，则称这两个概念格同构，记作：。

在形式背景下，，记，则也是一个形式背景，对于运算，在下用表示，则显然，。易证总有。

2.2. 概念格的属性约简与拓扑子基

定义2.2.1 [3] 对于形式背景，若存在属性集，使得，则称为的协调集。若进一步，，则称为的约简。

由定义2.2.1知概念格上约简满足：①为协调集；②不是协调集。

文 [3] 中，作者给出了若干协调集判定定理以及寻找属性约简的方法。文 [3] 中证明了如下定理：

定理2.2.2 [3] 设为形式背景，，，，则：

为协调集，使得：。

此定理建立了概念格的属性约简与拓扑学中的子基约简的某种联系。

令对象集，属性集，其中，令，则由形式背景的正则性知，即是构成的一个有限覆盖。

由文献 [4] 第二章定理2.6.4：设是一个集合，是的一个子集族，若，则有唯一的一个拓扑以为子基。对于上述讨论的，上唯一的拓扑以为子基，由于我们讨论的对象集为有限集，从而在这里我们讨论的拓扑也相应于有限集上的拓扑，即拓扑是由中元素作有限交、有限并生成的。

定义2.2.3 设为拓扑空间的子基，若的子集族，使得，且以为子基生成的拓扑与相同，则称为子基的一个约简。进一步，若中任意去掉一个元后，都不是的约简，此时称为子基的一个极小约简。

例如，

，

为的一个约简，且为极小约简。

引理2.2.4 设为拓扑空间的一个子基，若存在子集族，，使得：，都，使得，则为子基的一个约简。

证明：首先，由题意知，则。

设以为子基生成的拓扑为，下证。显然由知。

对，即为中若干元作有限交、有限并所生成，若这些元全在中，则显然；若存在若干元，则分别存在，使得。由中元均为有限知：，从而，即为的一个约简。

定理2.2.5 设为形式背景，，，

为概念格的一个属性约简。令

，

则以为子基生成拓扑空间，构成子基的一个约简。

证明：令，，则，使得，由为的约简，故为的协调集，从而由定理2.2.2知：，使得，又，故，即，且。故由引理2.2.4知构成子基的一个约简。

注：① 上述定理中为约简集条件可弱化为协调集。

② 由于概念格的属性约简不一定唯一，相应地对于拓扑学来说，子基的约简也不一定唯一，且上述定理中不一定是子基的一个极小约简。

例2.2.6 设形式背景如下：，

该形式背景有10个概念，分别为：

；；；；；；；；；。

则该形式背景所对应的可辨识属性矩阵可表示为：

或写成：

由文献 [3] 的定理11：设为形式背景，

，

则：为协调集。即寻找形式背景的约简实际上寻找满足条件的最小属性集。

对于此例中形式背景的约简只有一个，即为。下面从拓扑学角度来讨论：令

显然为子基的一个约简，若令

，则分别以为子基生成相同的拓扑：

。

从而不是的一个极小约简。

例2.2.7 令形式背景为，

该形式背景有6个概念如下：

；；；；；。

该形式背景所对应的可辨识属性矩阵可表示如下：

则该形式背景的属性约简仍为.令，则以为子基生成拓扑：

令，则又构成另外一个形式背景如下：

通过计算可知该形式背景的约简只有一个，即。

从而，对于同一拓扑来说，的两个不同子基所对应的两个不同的形式背景的属性约简也可能不同，甚至差别很大。

3. 形式背景上的限制及叉乘

3.1. 形式背景上限制的定义

形式概念分析与点集拓扑二者在研究方法上有许多类似之处，下面我们尝试从拓扑空间中构造拓扑子空间的方法来研究形式背景。如何定义形式背景上的限制与形式背景的叉乘，而又保持某些拓扑性质不变是一个值得探讨的问题。

定义3.1.1 设是一个形式背景，，。称：

为属性集在对象集上的限制，记作。

注：①也构成一个形式背景，其所对应的0-1表格为原形式背景所表示的0-1表格去掉若干行和若干列。

②定义中“，使得且，使得”是保证了形式背景的正则性。

性质3.1.2 (1)，，使得

，。

(2) 若对非空，

，有

，

则为的协调集。

证明：(1) 对，记，，则，且显然有：，。

(2)

则：

由条件，则非空，故为的协调集。

例3.1.3 如前例2.2.6中，取，则

该形式背景有如下概念：

；；；；；；；。

可由性质(1)与例2.2.6中概念对应。

其可辨识属性矩阵为：

其约简集为(约简集一定为协调集)。

注：满足性质3.1.2(2)条件的不一定为的约简，即使为的约简也不一定能保证。例如例2.2.6中取时情形。

3.2. 形式背景的叉乘

下面考虑如何定义形式背景的叉乘，又能保持一些拓扑性质不变。为此引入一个定理：

定理3.2.1 [4] 设是个拓扑空间的积空间，令为的拓扑，为的拓扑，。则以它的子集族为它的一个子基，其中为投射。

不失一般性，我们在此只讨论时形式背景叉乘的情形。

对于形式背景与，令

则分别以为子基生成和上的拓扑和，即对于每个形式背景来说都相对应于一个拓扑空间，即：

由前讨论知，一个子基就对应一个形式背景，而由定理3.2.1知：

即为拓扑空间的一个子基，从而可以由此来定义形式背景的叉乘。

现举例如下：

例3.2.2 设为例2.2.6中形式背景，为例2.2.7中形式背景.

下面通过子基导出上述两形式背景的叉乘(注意：在构造表格过程中，为了保证形式背景的正则性，应去掉全为0或全为1的行与列，即不考虑及)

性质3.2.3 由例3.2.2中所得形式背景所对应的拓扑即为乘积拓扑。

4. 结论

鉴于形式概念分析与点集拓扑两者在研究方法上有许多相似之处，本文由概念格的属性约简理论出发，从拓扑学角度来观看概念格的属性约简。建立其与拓扑学中子基约简的某种联系，再定义了形式背景上的限制与叉乘，探讨是否可以保持某些拓扑性质不变。本文还有许多内容有待研究，如在定义了形式背景的叉乘后，，，三个形式背景的属性约简有何关系等等，因此还需进一步的研究。

基金项目

安徽省高校自然科学研究重点项目基金(KJ2016A269)资助。

文章引用

李伯权,鲍玉曦. 概念格与拓扑
Concept Lattice and Topology[J]. 理论数学, 2016, 06(05): 427-436. http://dx.doi.org/10.12677/PM.2016.65058

参考文献 (References)