概念格在不完备形式背景中的知识获取模型

王雯，康向平，武燕

（1. 太原工业学院 自动化系，山西 太原 030008; 2. 太原理工大学 信息工程学院，山西 太原 030024; 3. 同济大学嵌入式系统与服务计算教育部重点实验室，上海 201804; 4. 同济大学 计算机科学与技术系，上海 201804）

通过模拟人类的概念认知思维，Wille[1]教授于1982年在格论基础上发展了面向概念建模的概念格理论。作为格论的重要应用分支，概念格具有坚实的数学理论基础，其中概念、格代数结构、对偶伽罗瓦连接等是核心要素。近年来，伴随着概念格自身理论发展以及与粗糙集[2-3]、模糊集等的深度融合，其理论体系日趋成熟，应用范围也得到了极大的拓展。

粗糙集无需借助先验知识，且符合人类的近似思维，易于理解，因此受到了国内外学者的广泛关注[4]。近年来，对于不完备信息的处理，粗糙集已经取得了大量的研究成果。把缺失值理解为任何可能值，Kryszkiewicz[5-6]提出了基于容差关系的拓展粗糙集模型，其中容差关系满足自反性和对称性，随后，将缺失值视为不存在或是不允许比较的未知值，Stefanowski[7]提出了基于不对称相似关系(满足自反性和传递性)的粗糙集拓展模型，结合上述2种模型的优点，王国胤[4]进一步提出了基于限制容差关系(满足自反性和对称性)的扩充模型，该模型相对以往模型更加符合实际，Leung等[8]将极大相容类视为一个粒，探讨了不完备信息系统中的知识获取，张文修[9]将不完备信息系统理解为一个集值信息系统，并探讨了面向集值的相容关系。

目前，关于不完备信息系统已有大量的研究成果，然而对于不完备形式背景的分析处理尚处于起步阶段[10-16]。从研究对象来讲，形式背景本质上是一种特殊的信息系统，它们之间存在着天然联系，具有较强的相容性，这也意味着面向不完备信息系统的知识获取方法对于不完备形式背景的处理具有一定的借鉴作用。事实上，将不完备信息系统中的方法推广到不完备形式背景中，也是一项非常有意义的研究工作，其不仅能为不完备形式背景的分析处理提供必要的支撑，而且也有助于概念格与粗糙集的理论融合。

考虑到不完备形式背景的普遍性以及经典概念格的局限性，在概念格框架体系中，本文融入了粗糙集中的粒化思维，探讨了概念格视角下的信息粒化，提出了基于等价类和基于极大相容类的知识获取方法。这些方法一方面有助于概念格与粗糙集的融合，另一方面也为探索不完备形式背景的分析处理机制提供了有益思路。

1 概念格基本知识

表1 一个典型的不完备形式背景Table 1 A typical incomplete formal context

2 概念格与粒化分析

等价类、极大相容类等是粗糙集中的基本粒。在粒内部，不同对象往往拥有相同的特征和相近的特征值，这就意味着粒内部不同对象之间的特征值是可以相互借鉴的。据此，本文尝试在概念格理论框架内探讨基于二元关系的信息粒化。

二元关系与形式背景存在着天然联系，它们之间可以相互表示。通常，二元关系有2种不同的类型，即内部二元关系和外部二元关系。其中，内部二元关系存在于单个集合的内部，例如，偏序集中的序关系”即是一种内部二元关系；外部二元关系是指存在于集合之间的关系，例如，中的序关系“”即是一种外部二元关系。

推论1 内部二元关系是一种特殊的外部二元关系。例如，虽然与在形式上存在一定差异，但本质上却是相同的。

推论2 内部二元关系与外部二元关系均可以表示为形式背景。在下文中，无论是内部还是外部二元关系均统一表示为形式背景。

在粒化思维下，对于数据集的分析和处理，人们通常注重的是集合，而非单个元素；注重的是集合之间的关系，而非单个元素之间的关系。

证明当时，由定义1可知，对于任意和任意，有成立，这就意味着和是关联的。假设和不是极大关联的，即存在满足。在此情形下，必然有且成立，或且成立，而非且成立，由此即得，显然，该结论与已知条件是相互矛盾的。故当时，和是极大关联的。证毕。

证明当成立时，由定理1得和是极大关联的，这也意味着将满足下述条件：

3 基于等价类的数据分析模型

表2 一个模糊相似关系矩阵Table 2 A fuzzy similarity relation matrix

表3 一个模糊等价关系矩阵Table 3 A fuzzy equivalence relation matrix

为避免单一粒度认知的片面性，对于任意缺失值的估计，用户可以设置多个阈值参数，进而结合多个粒度下的分类结果去分析和求解问题。定义6 设是-阶模糊等价关系矩阵，称是边界值，若不存在满足且。

基于上述判定准则，用户可以对不完备形式背景进行预处理，从而得到一个完备的形式背景。接上例，对于，依据准则1及下述计算结果，即得。

类似地，用户也可以判定其它缺失值，相应的判定结果如表4所示。在此基础上，复用经典概念格生成算法，用户可以从表4生成一个格代数结构，如图1所示。

表4 表1的一个完备化形式背景Table 4 A complete formal context from table 1

图1 基于准则1从表1导出的概念格结构Fig. 1 Concept lattice structure derived from table 1 based on criterion 1

4 基于极大相容类的数据分析模型

表5 一个不完备形式背景Table 5 A incomplete formal context

类似地，用户也可以判定其它缺失值，相应的判定结果如表6所示。在此基础上，复用经典概念格生成算法，用户可以从表6生成一个格代数结构，如图2所示。

表6 表5的一个完备化形式背景Table 6 Complete formal context generated from table 5

图2 基于准则2从表5导出的概念格结构Fig. 2 Concept lattice structure derived from Table 5 based on Criterion 2

基于准则1和准则2的模型本质上都属于间接处理模型，即需要对原始数据集进行预处理，给出缺失数据的估算值，进而复用经典理论对完备形式背景进行分析处理。

准则3 在任一极大相容类中，不同对象在同一属性下应具有相同的属性值。在此情形下，一个极大相容类在属性下的值域只可能有以下 4种情况，即{1}、{0}、{1, *}、{0, *}，而不可能是{0, 1, *}。

与定义1中的经典算子相类似，从上述算子出发同样可以导出一个格代数结构，相关证明过程与经典算子类似，在此不再详述。

例如，在表5中，从定理2和定义7出发，可判定{1}、{2}、{3, 4}、{5}、{6}、{7, 8}、{7, 9}是极大相容类，如表7所示，进而基于定义7中的算子生成图3所示的格代数结构。除(79, abce)之外，图3、图2中的其他结点均一致，这也从侧面反映了这样一个事实，即无论是基于准则2，还是基于准则3，所构造的模型可能会得到相似的结论。

表7 表5的一个粒化形式背景Table 7 A granular formal context from table 5

图3 基于准则3从表5导出的概念格结构Fig. 3 Concept lattice structure derived from Table 5 based on Criterion 3

基于准则3的知识获取模型，其本质是将分析尺度放大，以极大相容类为研究对象，而非单个对象。在准则3下，任意在属性的取值是确定的，即要么成立，要么成立，这就意味着，不完备形式背景可以转化为一个完备的粒化形式背景。事实上，在准则3下，无论是基于定义7，还是定义8，得到的格代数结构本质上是相同的，仅仅在外延表示形式上存在略微差异。

证明由定义7和定义8即得。证毕。

与准则1和准则2最大的不同是，基于准则3的知识获取模型无需对缺失信息进行预判定并给出估算值，而是直接在原始不完备形式背景上建立知识获取模型。

5 实例分析

表8是一个以医院病例为原型而得到的不完备形式背景，其中Pi(i=)表示患者代码；(H, yes)、(H, no)、(M, yes)等表示身体症状特征，其中 H、M、T、F依次表示 Headache、Muscle-pain、Temperature、Flu；若某患者具有某种症状，则在表 8 中用“1”来表示，反之用“0”来表示；若某诊断结论存在缺失，则用“*”来表示。

表8 一个不完备形式背景Table 8 A incomplete formal context

表9 表8的一个完备化形式背景Table 9 Complete formal context generated from table 8

事实上，表9中的完备化结果与下述事实性规则是吻合的，这也在一定程度上反应了准则1和准则2的合理性和有效性。例如，当患者体温是“very high”时，则其体温一定也是“high”；当患者体温“normal”时，则其体温一定不是“high”和“very high”；当患者“Flu, yes”时，则一定不是“Flu, no”等。

事实性规则：(T, very high)→(T, high)、(T, normal)(T, high)、(T, normal)(T, very high)、(H,yes)(H, no)、(H, no)(H, yes)、(F, no)(F, yes)、(F, yes)(F, no)。

在概念格经典理论中，概念内涵和蕴涵规则都占有极其重要的地位。本文认为，无论间接处理模型，还是直接处理模型，它们都应该得到相同的内涵集和蕴涵规则集(内涵集和蕴涵规则集是相互唯一决定的)。据此，本文提出了如下有效性判定准则：

有效性判定准则对于同一个不完备形式背景，若多个不同模型得到的蕴涵规则集合或内涵集合是相同的，则本文认为这些模型在一定程度上是有效的，得到的结果在一定程度上也是可信的。

准则3相对应的极大相容类有{1}、{2, 7, 8}、{3}、{4, 9}、{5, 8}、{6}。在此基础上，基于定义7或定义8，用户可得到相应的格代数结构。经验证明，基于准则3直接从表8得到的概念内涵集与基于准则1或准则2间接从表8中得到的概念内涵集是相同的。显然，在这种情形下，依据有效性判定准则给出的判定原理，可以在一定程度认为基于准则1、准则2或准则3构建的模型是合理的，相应的求解结果也是可信的。

总体来看，准则1和准则2需要引入阈值参数，属于间接处理模型；而准则3则无需引入阈值，属于直接处理模型。在实际应用中，如果数据缺失量大，本文倾向于选用直接处理模型，因为先选择间接模型可能会导致原始数据集失真；如果数据缺失量少，则无论是直接模型还是间接模型，都可以选用。

6 结束语

为消除不完备信息带来的影响，使概念格模型具有更强的数据处理能力与更广的应用领域，本文尝试将经典形式背景中的知识获取方法进一步拓展到不完备形式背景中，依次探讨了基于等价类的分析模型和基于极大相容类的分析模型。在实际应用中，用户既可以选择基于准则1或准则2的间接处理模型，也可以选择基于准则3的直接处理模型。此外，对于模型的机制有效性和结果可信性，本文也尝试性的进行了探讨，并提出了一些初步的验证方法。相信本文所做的工作能为下一步相关研究提供一些有益的思路。