第14卷第5期 智能系统学报 Vol.14 No.5 2019年9月 CAAI Transactions on Intelligent Systems Sep.2019 D0:10.11992/tis.201809021 网络出版地址：http:/kns.net/kcms/detail/23.1538.tp.20190520.1330.004.html 概念格在不完备形式背景中的知识获取模型 王雯2，康向平，武燕2 (1.太原工业学院自动化系，山西太原030008,2.太原理工大学信息工程学院，山西太原030024；3.同济大学 嵌入式系统与服务计算教育部重点实验室，上海201804：4.同济大学计算机科学与技术系，上海201804) 摘要：为了使概念格模型具有更强的数据处理能力，消除不完备信息带来的影响，针对经典概念格的局限性， 本文将粗糙集中的粒化思维融入到概念格中。首先探讨了概念格视角下的信息粒化方法，然后提出了基于等 价类和基于极大相容类的知识获取方法，最后给出了实例分析。这些方法一方面有助于概念格与粗糙集的融 合，另一方面也为探索不完备形式背景的分析处理机制提供了有益思路。 关键词：概念格；粗糙集；不完备形式背景：等价类：极大相容类；信息粒化：数据处理 中图分类号：TP18 文献标志码：A文章编号：1673-4785(2019)05-1048-08 中文引用格式：王要，康向平，武燕.概念格在不完备形式背景中的知识获取模型「J引.智能系统学报，2019,14(5)： 1048-1055. 英文引用格式：WANG Wen,.KANG Xiangping,WU Yan..Knowledge acquisition model of concept lattice in an incomplete formal context[Jl.CAAI transactions on intelligent systems,2019,14(5):1048-1055. Knowledge acquisition model of concept lattice in an incomplete formal context WANG Wen,KANG Xiangping,WU Yan2 (1.Department of Automation,Taiyuan Industrial College,Taiyuan 030008,China;2.College of Information Engineering,Taiyuan University of Technology,Taiyuan 030024,China;3.Key Laboratory of Embedded System and Service Computing,Ministry of Education,Tongji University,Shanghai 201804,China;4.Department of Computer Science and Technology,Tongji University, Shanghai 201804,China) Abstract:To improve the data processing ability of the concept lattice model and eliminate the impact of incomplete in- formation,in this paper,considering the limitations of classical concept lattice in actual applications,the granulation idea in rough sets is integrated into concept lattice.First,we explore information granulation methods from the perspect- ive of concept lattice and then propose a knowledge acquisition method based on the equivalence class and maximal tol- erance class,and then,carry out the case analysis.These methods are helpful for the integration of concept lattice and rough sets.Moreover,they also provide some useful ideas for exploring the analysis and processing mechanism of in- complete formal contexts. Keywords:concept lattice;rough set;incomplete formal context;equivalence class;maximal tolerance class;informa- tion granulation;data processing 通过模拟人类的概念认知思维，Wile四教授 构、对偶伽罗瓦连接等是核心要素。近年来，伴 于1982年在格论基础上发展了面向概念建模的 随着概念格自身理论发展以及与粗糙集]、模糊 概念格理论。作为格论的重要应用分支，概念格 集等的深度融合，其理论体系日趋成熟，应用范 具有坚实的数学理论基础，其中概念、格代数结 围也得到了极大的拓展。 粗糙集无需借助先验知识，且符合人类的近 收稿日期：2018-09-13.网络出版日期：2019-05-21. 似思维，易于理解，因此受到了国内外学者的广 基金项目：国家自然科学基金项目(61603278). 通信作者：王雯.E-mail:wangwen80971@163.com 泛关注。近年来，对于不完备信息的处理，粗糙
DOI: 10.11992/tis.201809021 网络出版地址: http://kns.net/kcms/detail/23.1538.tp.20190520.1330.004.html 概念格在不完备形式背景中的知识获取模型 王雯1,2，康向平3,4，武燕2 （1. 太原工业学院 自动化系，山西 太原 030008; 2. 太原理工大学 信息工程学院，山西 太原 030024; 3. 同济大学 嵌入式系统与服务计算教育部重点实验室，上海 201804; 4. 同济大学 计算机科学与技术系，上海 201804） 摘 要：为了使概念格模型具有更强的数据处理能力，消除不完备信息带来的影响，针对经典概念格的局限性， 本文将粗糙集中的粒化思维融入到概念格中。首先探讨了概念格视角下的信息粒化方法，然后提出了基于等 价类和基于极大相容类的知识获取方法，最后给出了实例分析。这些方法一方面有助于概念格与粗糙集的融 合，另一方面也为探索不完备形式背景的分析处理机制提供了有益思路。 关键词：概念格；粗糙集；不完备形式背景；等价类；极大相容类；信息粒化；数据处理 中图分类号：TP18 文献标志码：A 文章编号：1673−4785(2019)05−1048−08 中文引用格式：王雯, 康向平, 武燕. 概念格在不完备形式背景中的知识获取模型 [J]. 智能系统学报, 2019, 14(5): 1048–1055. 英文引用格式：WANG Wen, KANG Xiangping, WU Yan. Knowledge acquisition model of concept lattice in an incomplete formal context[J]. CAAI transactions on intelligent systems, 2019, 14(5): 1048–1055. Knowledge acquisition model of concept lattice in an incomplete formal context WANG Wen1,2 ，KANG Xiangping3,4 ，WU Yan2 (1. Department of Automation, Taiyuan Industrial College, Taiyuan 030008, China; 2. College of Information Engineering, Taiyuan University of Technology, Taiyuan 030024, China; 3. Key Laboratory of Embedded System and Service Computing, Ministry of Education, Tongji University, Shanghai 201804, China; 4. Department of Computer Science and Technology, Tongji University, Shanghai 201804, China) Abstract: To improve the data processing ability of the concept lattice model and eliminate the impact of incomplete information, in this paper, considering the limitations of classical concept lattice in actual applications, the granulation idea in rough sets is integrated into concept lattice. First, we explore information granulation methods from the perspective of concept lattice and then propose a knowledge acquisition method based on the equivalence class and maximal tolerance class, and then, carry out the case analysis. These methods are helpful for the integration of concept lattice and rough sets. Moreover, they also provide some useful ideas for exploring the analysis and processing mechanism of incomplete formal contexts. Keywords: concept lattice; rough set; incomplete formal context; equivalence class; maximal tolerance class; information granulation; data processing 通过模拟人类的概念认知思维，Wille[1] 教授 于 1982 年在格论基础上发展了面向概念建模的 概念格理论。作为格论的重要应用分支，概念格 具有坚实的数学理论基础，其中概念、格代数结 构、对偶伽罗瓦连接等是核心要素。近年来，伴 随着概念格自身理论发展以及与粗糙集[2-3] 、模糊 集等的深度融合，其理论体系日趋成熟，应用范 围也得到了极大的拓展。 粗糙集无需借助先验知识，且符合人类的近 似思维，易于理解，因此受到了国内外学者的广 泛关注[4]。近年来，对于不完备信息的处理，粗糙 收稿日期：2018−09−13. 网络出版日期：2019−05−21. 基金项目：国家自然科学基金项目 (61603278). 通信作者：王雯. E-mail：wangwen80971@163.com. 第 14 卷第 5 期 智 能 系 统 学 报 Vol.14 No.5 2019 年 9 月 CAAI Transactions on Intelligent Systems Sep. 2019
第5期 王雯，等：概念格在不完备形式背景中的知识获取模型 ·1049· 集已经取得了大量的研究成果。把缺失值理解为 (X1,B1)≤(X2,B2)台X1≤X2台B2≤B 任何可能值，Kryszkiewicz-提出了基于容差关 基于上述认识和理解，一个格代数结构 系的拓展粗糙集模型，其中容差关系满足自反性 (B(K),≤)可以从K中推导出来，其中B(K)是K中 和对称性，随后，将缺失值视为不存在或是不允 所有概念的集合。关于概念格详细资料请查阅文 许比较的未知值，Stefanowski提出了基于不对 献[17刀。 称相似关系（满足自反性和传递性）的粗糙集拓 对象和属性之间的关系如果存在缺失，则称 展模型，结合上述2种模型的优点，王国胤进一 (G,M)是一个不完备形式背景。一个典型的不 步提出了基于限制容差关系（满足自反性和对称 完备形式背景如表1所示，其中，若x∈G和 性)的扩充模型，该模型相对以往模型更加符合 m∈M之间的关系是缺失的（即无法确定是 实际，Leung等将极大相容类视为一个粒，探讨 (x,m)eI还是(x,m)生I),则记为m(x)=*。 了不完备信息系统中的知识获取，张文修将不 表1一个典型的不完备形式背景 完备信息系统理解为一个集值信息系统，并探讨 Table 1 A typical incomplete formal context 了面向集值的相容关系。 d 目前，关于不完备信息系统已有大量的研究 成果，然而对于不完备形式背景的分析处理尚处 于起步阶段6。从研究对象来讲，形式背景本 0 质上是一种特殊的信息系统，它们之间存在着天 0 然联系，具有较强的相容性，这也意味着面向不 完备信息系统的知识获取方法对于不完备形式背 0 0 景的处理具有一定的借鉴作用。事实上，将不完 6 0 0 备信息系统中的方法推广到不完备形式背景中， 1 也是一项非常有意义的研究工作，其不仅能为不 完备形式背景的分析处理提供必要的支撑，而且 9 也有助于概念格与粗糙集的理论融合。 考虑到不完备形式背景的普遍性以及经典概 2 念格的局限性，在概念格框架体系中，本文融入 概念格与粒化分析 了粗糙集中的粒化思维，探讨了概念格视角下的 等价类、极大相容类等是粗糙集中的基本 信息粒化，提出了基于等价类和基于极大相容类 粒。在粒内部，不同对象往往拥有相同的特征和 的知识获取方法。这些方法一方面有助于概念格 相近的特征值，这就意味着粒内部不同对象之间 与粗糙集的融合，另一方面也为探索不完备形式 的特征值是可以相互借鉴的。据此，本文尝试在 背景的分析处理机制提供了有益思路。 概念格理论框架内探讨基于二元关系的信息 粒化。 1概念格基本知识 二元关系与形式背景存在着天然联系，它们 通常，称(G,M,I)是一个形式背景，若G是 之间可以相互表示。通常，二元关系有2种不同 对象集，M是属性集，I表示G和M之间的二元 的类型，即内部二元关系和外部二元关系。其 关系。在此意义下，(x,m)∈I或m(x)=1表示对象 中，内部二元关系存在于单个集合的内部，例如， x∈G拥有属性m∈M,相反，(x,m)生I或m(x)=0 偏序集(V,≤)中的序关系“≤”即是一种内部二元 表示对象x不拥有属性m。 关系；外部二元关系是指存在于集合之间的关 定义1在K=(G,M,I)中，对于任意Xe2G和 系，例如，(V,W,≤)中的序关系“≤”即是一种外部 B∈2M,相应的经典内涵算子与外延算子定义为 二元关系。 X={m∈M(x,m)∈I,Hx∈X) (1) 推论1内部二元关系是一种特殊的外部二 B={x∈G(x,m)∈L,Vm∈B) (2) 元关系。例如，虽然(V,≤)与(V,V,≤)在形式上存 式中2是集合X的幂集。若B=X且X=B,称 在一定差异，但本质上却是相同的。 (X,B)是一个概念，其中X和B分别称为概念的 推论2内部二元关系与外部二元关系均可 外延和内涵。在此意义下，任意概念(X,B)和 以表示为形式背景。在下文中，无论是内部还是 (X2,B2)之间的序关系定义为 外部二元关系均统一表示为形式背景
集已经取得了大量的研究成果。把缺失值理解为 任何可能值，Kryszkiewicz[5-6] 提出了基于容差关 系的拓展粗糙集模型，其中容差关系满足自反性 和对称性，随后，将缺失值视为不存在或是不允 许比较的未知值，Stefanowski[7] 提出了基于不对 称相似关系 (满足自反性和传递性) 的粗糙集拓 展模型，结合上述 2 种模型的优点，王国胤[4] 进一 步提出了基于限制容差关系 (满足自反性和对称 性) 的扩充模型，该模型相对以往模型更加符合 实际，Leung 等 [8] 将极大相容类视为一个粒，探讨 了不完备信息系统中的知识获取，张文修[9] 将不 完备信息系统理解为一个集值信息系统，并探讨 了面向集值的相容关系。 目前，关于不完备信息系统已有大量的研究 成果，然而对于不完备形式背景的分析处理尚处 于起步阶段[10-16]。从研究对象来讲，形式背景本 质上是一种特殊的信息系统，它们之间存在着天 然联系，具有较强的相容性，这也意味着面向不 完备信息系统的知识获取方法对于不完备形式背 景的处理具有一定的借鉴作用。事实上，将不完 备信息系统中的方法推广到不完备形式背景中， 也是一项非常有意义的研究工作，其不仅能为不 完备形式背景的分析处理提供必要的支撑，而且 也有助于概念格与粗糙集的理论融合。 考虑到不完备形式背景的普遍性以及经典概 念格的局限性，在概念格框架体系中，本文融入 了粗糙集中的粒化思维，探讨了概念格视角下的 信息粒化，提出了基于等价类和基于极大相容类 的知识获取方法。这些方法一方面有助于概念格 与粗糙集的融合，另一方面也为探索不完备形式 背景的分析处理机制提供了有益思路。 1 概念格基本知识 (G, M, I) G (x,m) ∈ I m(x) = 1 x ∈ G m ∈ M (x,m) < I m(x) = 0 x m 通常，称 是一个形式背景，若 是 对象集，M 是属性集，I 表示 G 和 M 之间的二元 关系。在此意义下， 或 表示对象 拥有属性 ，相反， 或 表示对象 不拥有属性 。 K = (G, M, I) X ∈ 2 G B ∈ 2 M 定义 1 在 中，对于任意 和 ，相应的经典内涵算子与外延算子定义为 X ∗ = {m ∈ M| (x,m) ∈ I, ∀x ∈ X} (1) B ∗ = { x ∈ G| (x,m) ∈ I, ∀m ∈ B} (2) 2 X X B = X ∗ X = B ∗ (X,B) (X1,B1) (X2,B2) 式中 是集合 的幂集。若 且 ，称 是一个概念，其中 X 和 B 分别称为概念的 外延和内涵。在此意义下，任意概念 和 之间的序关系定义为 (X1 ,B1) ⩽ (X2 ,B2) ⇔ X1 ⊆ X2 ⇔ B2 ⊆ B1 (B(K), ⩽) B(K) 基于上述认识和理解，一个格代数结构 可以从 K 中推导出来，其中 是 K 中 所有概念的集合。关于概念格详细资料请查阅文 献 [17]。 (G, M, I) x ∈ G m ∈ M (x,m) ∈ I (x,m) < I m(x) = ∗ 对象和属性之间的关系如果存在缺失，则称 是一个不完备形式背景。一个典型的不 完备形式背景如 表 1 所示，其中，若 和 之间的关系是缺失 的 ( 即无法确定是 还是 )，则记为 。 表 1 一个典型的不完备形式背景 Table 1 A typical incomplete formal context a b c d e 1 1 1 0 0 1 2 1 * 0 0 0 3 0 0 0 1 1 4 0 * 0 1 1 5 0 1 1 1 0 6 0 1 1 * 0 7 1 0 1 * 1 8 1 0 1 0 1 9 1 * 1 1 1 2 概念格与粒化分析 等价类、极大相容类等是粗糙集中的基本 粒。在粒内部，不同对象往往拥有相同的特征和 相近的特征值，这就意味着粒内部不同对象之间 的特征值是可以相互借鉴的。据此，本文尝试在 概念格理论框架内探讨基于二元关系的信息 粒化。 (V,⩽) ⩽ (V,W,⩽) ⩽ 二元关系与形式背景存在着天然联系，它们 之间可以相互表示。通常，二元关系有 2 种不同 的类型，即内部二元关系和外部二元关系。其 中，内部二元关系存在于单个集合的内部，例如， 偏序集 中的序关系“ ”即是一种内部二元 关系；外部二元关系是指存在于集合之间的关 系，例如， 中的序关系“ ”即是一种外部 二元关系。 (V,⩽) (V,V,⩽) 推论 1 内部二元关系是一种特殊的外部二 元关系。例如，虽然 与 在形式上存 在一定差异，但本质上却是相同的。 推论 2 内部二元关系与外部二元关系均可 以表示为形式背景。在下文中，无论是内部还是 外部二元关系均统一表示为形式背景。 第 5 期 王雯，等：概念格在不完备形式背景中的知识获取模型 ·1049·
·1050· 智能系统学报 第14卷 在粒化思维下，对于数据集的分析和处理，人 一个满足自反性和对称性的相容关系时，粒D本 们通常注重的是集合，而非单个元素：注重的是 质上是一个相容类；当R是一个满足自反性、对 集合之间的关系，而非单个元素之间的关系。 称性和传递性的等价关系时，粒D是一个等价类。 定义2设R是非空集合X中的一个二元关 系。若XX和Y≤X之间满足下述条件： 3基于等价类的数据分析模型 对于任意x∈X和任意y∈Y,均有(x,y)∈R, 定义5设(G,M,D是一个不完备形式背景， 即X×YSR,称X和Y是关联的。设X和Y是 0≤6≤1,1≤K≤2。对于任意x∈G和yeG,它们 关联的，即X×YSR。若不存在X,×Y,SR满足 之间的相似度定义为 X×YCX×Y,称X和Y是极大关联的。 ISam_(x,yl+6×Lac_(x,y川 定义3称K=(X,X,R是一个关系背景，其 Sim(x,y)= ISam-(x,yl+6×Lac-(x,y川+k×Dif(x,y川 中R是非空集合X中的一个二元关系。 (3) 式中： 定理1在关系背景K=(X,X,R中，下列论 Sam_(x,y)={a∈Mm(x)=my)=1orm(x)=my）)=0 述是等价的： (4) 1)(X,Y)∈K): Lac_(x,y)=(mE MI m(x)=*or m(y)=*}(5) 2)x和Y是极大关联的。 Dif_(x,y)= 证明当(X,)∈B(K)时，由定义1可知，对 (mE MIm(x)=0 and m(y)=1,or m(x)=1 and m(y)=0) (6) 于任意x∈X和任意y∈Y,有(x,y)∈R成立，这就 参数6<1意味着Lac-对Sim的影响力要小 意味着X和Y是关联的。假设X和Y不是极大 于Sam和Dif;参数1<k≤2意味着Dif对Sim 关联的，即存在X×YSR满足X×YcX1×Y。 的影响力大于Sam和Lac-。从相似度Sim出 在此情形下，必然有YcX且XSY成立，或 发，首先会生成一个模糊相似关系矩阵，进而借 Y≤X且XcY成立，而非Y=X且X=Y成立， 助传递闭包算法将？转化为模糊等价关系矩阵 由此即得(X,)B(K,显然，该结论与已知条件 及。在此基础上，用户设置阈值参数0≤入≤1，可 (X,)∈B(K)是相互矛盾的。故当(X,)∈B(K) 最终得到一个A-阶等价关系矩阵R。R,本质上 时，X和Y是极大关联的。证毕。 是一个等价关系。此时，用户可依据定理2从R 定义4设R是非空集合X中的一个二元关 推导出若干个等价类，其中x∈G决定的等价类记 系。若D是满足下述条件的X中的最大子集， 为[x]ao 对于任意x,y∈D,均有(x,y)ER,即XxXCR;则 当6=K=1时，用户从表1能推导出如表2、 称D是X中的一个信息粒。 表3所示的模糊相似关系矩阵和模糊等价关系矩 定理2在关系背景K=(X,X,R)中，下述结 阵。当=1时，{1}、{2}、{3,4}、{5,6}、{7,8} 论成立： {9}是等价类；当1=0.8时，{1,2}、{3,4}、{5,6}、 (D,D)∈B(K),当且仅当D是一个信息粒 {7,8,9}是等价类；当1=0.6时，{1,2，…，91是唯一 证明当(D,D)∈B()成立时，由定理1得 的等价类。 D和D是极大关联的，这也意味着D将满足下 表2一个模糊相似关系矩阵 述条件： Table 2 A fuzzy similarity relation matrix 对于任意x,y∈D,均有(x,y)∈R,即D×DSR 2 34567 8 9 假设D,是满足上述条件的最大集合，其中 11.00.80.40.60.20.40.60.60.6 DcD。在此情形下，D,×D,cR是成立的，进而 20.8 1.00.40.40.40.60.60.6 0.4 判定(D,D)使B(K)。显然，该结论与(D,D)EB(K 是矛盾的。故当(D,D)∈B(K)成立时，D是满足 30.40.41.01.00.40.40.60.4 0.6 上述条件的最大集合，即D是一个信息粒。 40.60.41.01.00.60.60.6 0.4 0.6 反过来，当D是信息粒时，由定义4即得 50.20.40.40.6 1.0 1.00.4 0.2 0.6 D×DSR,且不存在D1×D1SR满足DcD1。在 60.4 0.6 0.40.6 1.0 1.0 0.4 0.4 0.6 此情形下，由定义2可知D和D是极大关联的 70.6 0.6 0.6 0.6 0.4 0.4 1.0 1.0 1.0 进而由定理1得(D,D)∈B()。故当D是一个信 80.60.6 0.4 04 0.2 0.4 1.0 1.0 0.8 息粒，有(D,D)∈B(K)成立。证毕。 90.60.40.60.60.60.61.00.81.0 在定理2中，对于任意(D,D)∈B(K,当R是
在粒化思维下，对于数据集的分析和处理，人 们通常注重的是集合，而非单个元素；注重的是 集合之间的关系，而非单个元素之间的关系。 R X X ⊆ X Y ⊆ X 定义 2 设 是非空集合 中的一个二元关 系。若 和 之间满足下述条件： x ∈ X y ∈ Y (x, y) ∈ R X×Y ⊆ R X Y X Y X×Y ⊆ R X1 ×Y1 ⊆ R X×Y ⊂ X1 ×Y1 X Y 对于任意 和任意 ，均有 ， 即 ，称 和 是关联的。设 和 是 关联的，即 。若不存在 满足 ，称 和 是极大关联的。 K = (X,X,R) R X 定义 3 称 是一个关系背景，其 中 是非空集合 中的一个二元关系。 定理 1 在关系背景 K = (X,X,R) 中，下列论 述是等价的： 1) (X,Y) ∈ B(K) ； 2) X 和 Y 是极大关联的。 (X,Y) ∈ B(K) x ∈ X y ∈ Y (x, y) ∈ R X Y X Y X1 ×Y1 ⊆ R X×Y ⊂ X1 ×Y1 Y ⊂ X ∗ X ⊆ Y ∗ Y ⊆ X ∗ X ⊂ Y ∗ Y = X ∗ X = Y ∗ (X,Y) < B(K) (X,Y) ∈ B(K) (X,Y) ∈ B(K) X Y 证明 当 时，由定义 1 可知，对 于任意 和任意 ，有 成立，这就 意味着 和 是关联的。假设 和 不是极大 关联的，即存在 满足 。 在此情形下，必然有 且 成立，或 且 成立，而非 且 成立， 由此即得 ，显然，该结论与已知条件 是相互矛盾的。故当 时， 和 是极大关联的。证毕。 R X D X x, y ∈ D (x, y) ∈ R ×X ⊆ R D X 定义 4 设 是非空集合 中的一个二元关 系。若 是满足下述条件的 中的最大子集， 对于任意 ，均有 ，即 X ；则 称 是 中的一个信息粒。 定理 2 在关系背景 K = (X,X,R) 中，下述结 论成立： (D,D) ∈ B(K) ，当且仅当 D 是一个信息粒 (D,D) ∈ B(K) D D D 证明 当 成立时，由定理 1 得 和 是极大关联的，这也意味着 将满足下 述条件： 对于任意 x, y ∈ D ，均有 (x, y) ∈ R ，即 D ×D ⊆ R D1 D ⊂ D1 D1 ×D1 ⊆ R (D,D) < B(K) (D,D) ∈ B(K) (D,D) ∈ B(K) D D 假设 是满足上述条件的最大集合，其中 。在此情形下， 是成立的，进而 判定 。显然，该结论与 是矛盾的。故当 成立时， 是满足 上述条件的最大集合，即 是一个信息粒。 D D ×D ⊆ R D1 ×D1 ⊆ R D ⊂ D1 D D (D,D) ∈ B(K) D (D,D) ∈ B(K) 反过来，当 是信息粒时，由定义 4 即得 ，且不存在 满足 。在 此情形下，由定义 2 可知 和 是极大关联的， 进而由定理 1 得 。故当 是一个信 息粒，有 成立。证毕。 在定理 2 中，对于任意 (D,D) ∈ B(K) ，当 R 是 D R D 一个满足自反性和对称性的相容关系时，粒 本 质上是一个相容类；当 是一个满足自反性、对 称性和传递性的等价关系时，粒 是一个等价类。 3 基于等价类的数据分析模型 (G, M, I) 0 ⩽ δ ⩽ 1 1 ⩽ κ ⩽ 2 x ∈ G y ∈ G 定义 5 设 是一个不完备形式背景， ， 。对于任意 和 ，它们 之间的相似度定义为 Sim(x, y) = |Sam−(x, y)|+ δ× |Lac−(x, y)| |Sam−(x, y)|+ δ × |Lac−(x, y)|+ κ × |Dif−(x, y)| (3) 式中： Sam−(x, y) = {a ∈ M|m(x) = m(y) = 1 or m(x) = m(y) = 0} (4) Lac−(x, y) = {m ∈ M| m(x) = ∗ or m(y) = ∗} (5) Dif−(x, y) = {m ∈ M|m(x) = 0 and m(y) = 1, or m(x) = 1 and m(y) = 0} (6) δ < 1 Lac− Sim Sam− Dif− 1 <κ ⩽ 2 Dif− Sim Sam− Lac− Sim R˜ R˜ R¯ 0 ⩽ λ ⩽ 1 λ Rλ Rλ Rλ x ∈ G [x]λ 参数 意味着 对 的影响力要小 于 和 ；参数 意味着 对 的影响力大于 和 。从相似度 出 发，首先会生成一个模糊相似关系矩阵 ，进而借 助传递闭包算法将 转化为模糊等价关系矩阵 。在此基础上，用户设置阈值参数 ，可 最终得到一个 -阶等价关系矩阵 。 本质上 是一个等价关系。此时，用户可依据定理 2 从 推导出若干个等价类，其中 决定的等价类记 为 。 δ = κ = 1 λ = 1 λ = 0.8 λ = 0.6 {1,2,··· ,9} 当 时，用户从表 1 能推导出如表 2、 表 3 所示的模糊相似关系矩阵和模糊等价关系矩 阵。当 时，{1}、{2}、{3, 4}、{5, 6}、{7, 8}、 {9}是等价类；当 时，{1, 2}、{3, 4}、{5, 6}、 {7, 8, 9}是等价类；当 时， 是唯一 的等价类。 表 2 一个模糊相似关系矩阵 Table 2 A fuzzy similarity relation matrix 1 2 3 4 5 6 7 8 9 1 1.0 0.8 0.4 0.6 0.2 0.4 0.6 0.6 0.6 2 0.8 1.0 0.4 0.4 0.4 0.6 0.6 0.6 0.4 3 0.4 0.4 1.0 1.0 0.4 0.4 0.6 0.4 0.6 4 0.6 0.4 1.0 1.0 0.6 0.6 0.6 0.4 0.6 5 0.2 0.4 0.4 0.6 1.0 1.0 0.4 0.2 0.6 6 0.4 0.6 0.4 0.6 1.0 1.0 0.4 0.4 0.6 7 0.6 0.6 0.6 0.6 0.4 0.4 1.0 1.0 1.0 8 0.6 0.6 0.4 0.4 0.2 0.4 1.0 1.0 0.8 9 0.6 0.4 0.6 0.6 0.6 0.6 1.0 0.8 1.0 ·1050· 智 能 系 统 学 报 第 14 卷
第5期 王雯，等：概念格在不完备形式背景中的知识获取模型 ·1051· 表3一个模糊等价关系矩阵 表4表1的一个完备化形式背景 Table 3 A fuzzy equivalence relation matrix Table 4 A complete formal context from table 1 23 4 5 6 1 9 110.80.60.6 0.6 0.60.6 0.6 0.6 20.81 0.60.60.60.60.60.60.6 30.60.6 1.00.60.60.60.60.6 40.60.6 10 0.6 0.6 0.6 0.6 50.60.6 0.6 0.6 0.6 0.6 60.6 0.6 06 0.6 0.6 70.60.6 6 1.0 1.0 80.60.60.6 0.6 0.60.61.0 1 90.60.60.60.6 0.60.61.0 1 为避免单一粒度认知的片面性，对于任意缺 ●(123456789，o) 失值的估计，用户可以设置多个阈值参数 1,2,…,w,0≤≤1，进而结合多个粒度下的 (12789,a) (34569,d0 1256,bN 分类结果去分析和求解问题。 (13789,e (56789,c) 定义6设R是阶模糊等价关系矩阵，称 是边界值，若不存在4满足≥B,则m)=1;若a<B,则m(e)=0。 其中(0123)=(10.80.6 其中 类似地，用户也可以判定其它缺失值，相应的 判定结果如表4所示。在此基础上，复用经典概 P,(x,m,1),(c,m,0) 念格生成算法，用户可以从表4生成一个格代数 (aB)=(DlD2…Dw)× 结构，如图1所示。 py(x,m,1)(x,m,0)
表 3 一个模糊等价关系矩阵 Table 3 A fuzzy equivalence relation matrix 1 2 3 4 5 6 7 8 9 1 1 0.8 0.6 0.6 0.6 0.6 0.6 0.6 0.6 2 0.8 1 0.6 0.6 0.6 0.6 0.6 0.6 0.6 3 0.6 0.6 1 1.0 0.6 0.6 0.6 0.6 0.6 4 0.6 0.6 1.0 1 0.6 0.6 0.6 0.6 0.6 5 0.6 0.6 0.6 0.6 1 1.0 0.6 0.6 0.6 6 0.6 0.6 0.6 0.6 1.0 1 0.6 0.6 0.6 7 0.6 0.6 0.6 0.6 0.6 0.6 1 1.0 1.0 8 0.6 0.6 0.6 0.6 0.6 0.6 1.0 1 1 9 0.6 0.6 0.6 0.6 0.6 0.6 1.0 1 1 λ1，λ2，···，λN 0 ⩽ λi ⩽ 1 为避免单一粒度认知的片面性，对于任意缺 失值的估计，用户可以设置多个阈值参数 ， ，进而结合多个粒度下的 分类结果去分析和求解问题。 Rλi λi λi λk λi < λk Rλi = Rλk 定义 6 设 是 -阶模糊等价关系矩阵，称 是边界值，若不存在 满足 且 。 (G, M, I) m(x) = ∗ λi i = 1,2,··· ,N 准则 1 在不完备形式背景 中，设 ， 是边界值， 。 若 α ⩾ β ，则 m(x) = 1 ；若 α < β ，则 m(x) = 0。 其中 (α β) = ( λ1 λ2 ··· λN ) × ρλ1 (x,m,1) ϕλ1 (x,m,0) . . . . . . ρλN (x,m,1) ϕλN (x,m,0) ρλi (x,m,1) = { y ∈ [x]λi | m(y) = 1} |[x]λi | ϕλi (x,m,0) = {y ∈ [x]λi | m(y) = 0} |[x]λi | d(7) = ∗ d(7) = 0 基于上述判定准则，用户可以对不完备形式 背景进行预处理，从而得到一个完备的形式背 景。接上例，对于 ，依据准则 1 及下述计 算结果，即得 。 ( 1 0.8 0.6 ) × 0.00 0.50 0.33 0.33 0.44 0.33 = ( 0.53 0.97 ) 其中 (λ1 λ2 λ3) = (1 0.8 0.6) 类似地，用户也可以判定其它缺失值，相应的 判定结果如表 4 所示。在此基础上，复用经典概 念格生成算法，用户可以从表 4 生成一个格代数 结构，如图 1 所示。 表 4 表 1 的一个完备化形式背景 Table 4 A complete formal context from table 1 a b c d e 1 1 1 0 0 1 2 1 1 0 0 0 3 0 0 0 1 1 4 0 0 0 1 1 5 0 1 1 1 0 6 0 1 1 1 0 7 1 0 1 0 1 8 1 0 1 0 1 9 1 0 1 1 1 (12789, a) (13789, e) (1789, ae) (12, ab) (1, abe) (789, ace) (349, de) (9, acde) (56, bcd) (569, cd) (34 569, d) (123456789, ø) (56789, c) (1256,b) (ø, abcde) 图 1 基于准则 1 从表 1 导出的概念格结构 Fig. 1 Concept lattice structure derived from table 1 based on criterion 1 4 基于极大相容类的数据分析模型 (G, M, I) Rσ 在不完备形式背景 中，一个相容关 系 可以描述为 Rσ = { (x, y) ∈ G×G| Sim(x, y) ⩾ σ},0 ⩽ σ ⩽ 1 SimRσ 式中 是定义 5 中构造的相似度模型。从定理 2 和 出发，用户即可推导出若干个极大相容 类，并基于准则 2 对缺失值进行判定。 m(x) = ∗ x ∈ G N D1,D2,··· ,DN 准则 2 设 ， 同时属于 个极大 相容类 。 ⌢ α ⩾ ⌢ β m(x) = 1 ⌢ α < ⌢ 若 ，则 ；若 β ，则 m(x) = 0。 其中 ( ⌢ α ⌢ β )=(|D1| |D2| ··· |DN|) × ⌢ ρ1 (x,m,1) ⌢ ϕ1 (x,m,0) . . . . . . ⌢ ρN (x,m,1) ⌢ ϕN (x,m,0) 第 5 期 王雯，等：概念格在不完备形式背景中的知识获取模型 ·1051·
·1052· 智能系统学报 第14卷 P(x.m.1)=IxED.Im()=1+1 9(123456789.0) I{x∈Dm(x)=0川+1 (23456789.a (x,m,0)= I{x∈Dlm()=0川+1 (12789,e) (12345,d I{x∈D,lm(x)=1川+1 在表5中，当6=k=1、σ=0.8时，{1,2}、{2 (56789,ac) (2345,ad0 3,4}、{3,4,5}、{5,6,7}、{6,7,8}、{7,8,9}、{2, 2789,ae12,de) 7}是极大相容类。基于准则2，用户可以对不完 (789,ace) 备形式背景进行预处理，进而得到一个完备的形 (2,ade) (5,acd) (9.abce) 式背景。例如，对于d(7)=*,基于准则2和下述 计算结果 (o,abcde) 1 图2基于准则2从表5导出的概念格结构 (3332)× 1/3 3 (922) Fig.2 Concept lattice structure derived from Table 5 1/3 3 based on Criterion 2 21/2 即可判定d(7)=0,其中，D1、D2、D、D,依次表 基于准则1和准则2的模型本质上都属于间 接处理模型，即需要对原始数据集进行预处理， 示{5,6,7}、{6,7,8}、{7,8,9}、{2,7}。 给出缺失数据的估算值，进而复用经典理论对完 表5一个不完备形式背景 Table 5 A incomplete formal context 备形式背景进行分析处理。 在不完备形式背景(G,MD中，一个相容关 d 系R可以描述为 0 R={(x,y)）eG×Gm(x)=my)or m(x)= 0 *0rmy=*,Hm∈M} 0 0 0 下文中，由上述相容关系决定的极大相容类 0 0 的集合记为△。 0 准则3在任一极大相容类中，不同对象在 1 同一属性下应具有相同的属性值。在此情形下， 6 0 0 0 一个极大相容类D在属性meM下的值域只可 能有以下4种情况，即{1}、{0；、{1，*}、0，*}，而 不可能是{0,1，*}。 0 当D在m下的值域为{1，*}时，若“*”代表 类似地，用户也可以判定其它缺失值，相应的 “0”,则必然与准则3相违背，此时，“*”代表的只 判定结果如表6所示。在此基础上，复用经典概 能是“1”；同理，若D在m下的值域为{0，*}，则 念格生成算法，用户可以从表6生成一个格代数 “*”代表的值只能是“0”。下文中，Vm(D)=1表示 结构，如图2所示。 D在m下的值域为{1}或{1，*}；Vm(D)=0表示D 在m下的值域为{0；或0，*}。 表6表5的一个完备化形式背景 Table 6 Complete formal context generated from table 5 定义7设(G,M,I)是一个不完备形式背 景，对于任意集合X∈29，记 6 X*={m∈M(m(x)=1)or 0 0 0 1 (3D∈4，x∈D,Vm(D)=1),Hx∈X) 0 0 1 对于任意集合B∈2M,记 0 0 B={x∈G(m(x)=1)or 4 0 1 0 (3D∈4，x∈D,Vm(D)=1),Ym∈B) 1 0 与定义1中的经典算子相类似，从上述算子 出发同样可以导出一个格代数结构，相关证明过 6 0 0 0 程与经典算子类似，在此不再详述。 例如，在表5中，从定理2和定义7出发，可 0 0 0 判定{1}、{2；、{3,4}、{5}、{6}、{7,8}、{7,9}是极 大相容类，如表7所示，进而基于定义7中的算子
⌢ ρi (x,m,1) = | { x ∈ Di | m(x) = 1} |+1 | { x ∈ Di | m(x) = 0} |+1 ⌢ ϕi (x,m,0) = | { x ∈ Di | m(x) = 0} |+1 | { x ∈ Di | m(x) = 1} |+1 δ = κ = 1 σ = 0.8 d(7) = ∗ 在表 5 中，当 、 时，{1, 2}、{2, 3, 4}、{3, 4, 5}、{5, 6, 7}、{6, 7, 8}、{7, 8, 9}、{2, 7}是极大相容类。基于准则 2，用户可以对不完 备形式背景进行预处理，进而得到一个完备的形 式背景。例如，对于 ，基于准则 2 和下述 计算结果 (3 3 3 2)× 1 1 1/3 3 1/3 3 2 1/2 = (9 22) 即可判定 d(7) = 0 ，其中， D1、D2、D3、D4 依次表 示{5, 6, 7}、{6, 7, 8}、{7, 8, 9}、{2, 7}。 表 5 一个不完备形式背景 Table 5 A incomplete formal context a b c d e 1 0 0 0 1 1 2 1 0 0 1 1 3 1 0 0 1 0 4 1 * 0 1 0 5 1 0 1 1 0 6 1 0 1 0 0 7 1 * 1 * 1 8 1 0 1 0 1 9 1 1 1 0 1 类似地，用户也可以判定其它缺失值，相应的 判定结果如表 6 所示。在此基础上，复用经典概 念格生成算法，用户可以从表 6 生成一个格代数 结构，如图 2 所示。 表 6 表 5 的一个完备化形式背景 Table 6 Complete formal context generated from table 5 a b c d e 1 0 0 0 1 1 2 1 0 0 1 1 3 1 0 0 1 0 4 1 0 0 1 0 5 1 0 1 1 0 6 1 0 1 0 0 7 1 0 1 0 1 8 1 0 1 0 1 9 1 1 1 0 1 (23456789,a) (123456789,ø) (ø,abcde) (12345,d) (12789,e) (12,de) (2,ade) (2789,ae) (2345,ad) (56789,ac) (5,acd) (789,ace) (9,abce) 图 2 基于准则 2 从表 5 导出的概念格结构 Fig. 2 Concept lattice structure derived from Table 5 based on Criterion 2 基于准则 1 和准则 2 的模型本质上都属于间 接处理模型，即需要对原始数据集进行预处理， 给出缺失数据的估算值，进而复用经典理论对完 备形式背景进行分析处理。 在不完备形式背景 (G, M, I) 中，一个相容关 系 R 可以描述为 R ={(x, y) ∈ G×G|m(x) = m(y) or m(x) = ∗ or m(y) = ∗, ∀m ∈ M} ∆ 下文中，由上述相容关系决定的极大相容类 的集合记为 。 D m ∈ M 准则 3 在任一极大相容类中，不同对象在 同一属性下应具有相同的属性值。在此情形下， 一个极大相容类 在属性 下的值域只可 能有以下 4 种情况，即{1}、{0}、{1, *}、{0, *}，而 不可能是{0, 1, ﹡}。 D m D m Vm(D) = 1 D m Vm(D) = 0 D m 当 在 下的值域为{1, *}时，若“*”代表 “0”，则必然与准则 3 相违背，此时，“*”代表的只 能是“1”；同理，若 在 下的值域为{0, *}，则 “*”代表的值只能是“0”。下文中， 表示 在 下的值域为{1}或{1, *}； 表示 在 下的值域为{0}或{0, *}。 (G, M, I) X ∈ 2 G 定义 7 设 是一个不完备形式背 景，对于任意集合 ，记 X + ={m ∈ M| (m(x) = 1) or (∃D ∈ ∆, x ∈ D, Vm(D) = 1), ∀x ∈ X} B ∈ 2 对于任意集合 M，记 B + ={ x ∈ G| (m(x) = 1) or (∃D ∈ ∆, x ∈ D, Vm(D) = 1), ∀m ∈ B} 与定义 1 中的经典算子相类似，从上述算子 出发同样可以导出一个格代数结构，相关证明过 程与经典算子类似，在此不再详述。 例如，在表 5 中，从定理 2 和定义 7 出发，可 判定{1}、{2}、{3, 4}、{5}、{6}、{7, 8}、{7, 9}是极 大相容类，如表 7 所示，进而基于定义 7 中的算子 ·1052· 智 能 系 统 学 报 第 14 卷
第5期 王雯，等：概念格在不完备形式背景中的知识获取模型 ·1053· 生成图3所示的格代数结构。除(79，abce)之外， (D,m)∈J台Vm(D)=1 图3、图2中的其他结点均一致，这也从侧面反映 在粒化背景K中，对于任意X∈24，记 了这样一个事实，即无论是基于准则2，还是基于 X={m∈M(D,m)eJ,VDeX) 准则3，所构造的模型可能会得到相似的结论。 对于任意Be2M,记 B={D∈△(D,m)∈J,Hm∈B} 表7表5的一个粒化形式背景 Table 7 A granular formal context from table 5 其中，(D,m)∈J亦可表示为m(D)=1。 基于准则3的知识获取模型，其本质是将分 a 6 d e 析尺度放大，以极大相容类为研究对象，而非单 1} 0 0 0 个对象。在准则3下，任意D在属性m的取值是 2} 1 0 0 确定的，即要么m(D)=1成立，要么m(D)=0成 {3,49 0 0 0 立，这就意味着，不完备形式背景可以转化为一 5} 1 0 0 个完备的粒化形式背景。事实上，在准则3下，无 6} 1 0 0 0 论是基于定义7，还是定义8，得到的格代数结构 本质上是相同的，仅仅在外延表示形式上存在略 {7,8} 1 0 0 微差异。 {7,9} 0 定理3若(X,B)∈B(K),(X,B)∈B(K),则 Q(123456789,0) x=UoosD 证明由定义7和定义8即得。证毕。 (23456789.a (12789,e) Q(12345,d0 与准则1和准则2最大的不同是，基于准则 3的知识获取模型无需对缺失信息进行预判定并 (56789,ac) (2345,ad) d2789,ae12,de) 给出估算值，而是直接在原始不完备形式背景上 建立知识获取模型。 (789,ace) (2ade) 5实例分析 (5,acd) (79,abce) 表8是一个以医院病例为原型而得到的不完 (o,abcde) 备形式背景，其中P(=1,2,…,9)表示患者代码； 图3基于准则3从表5导出的概念格结构 (H,yes)、(Hno)、(M,yes)等表示身体症状特征， Fig.3 Concept lattice structure derived from Table 5 其中H、M、T、F依次表示Headache、Muscle-pain、 based on Criterion 3 Temperature、Flu;若某患者具有某种症状，则在 定义8称K=(4,M,)是K=(G,M,I)的 表8中用“1”来表示，反之用“0”来表示；若某诊断 粒化背景，若 结论存在缺失，则用“*”来表示。 表8一个不完备形式背景 Table 8 A incomplete formal context 患者 (H,yes) (H,no)(M,yes) (M,no) (7,high) (T,very high) (T,normal) (F,yes)(F,no) P 0 0 0 P 0 0 0 0 0 P 1 0 0 1 0 0 Pa 0 1 1 0 0 0 1 0 1 Ps 0 0 1 0 0 0 1 P6 0 1 0 1 0 1 0 P 1 0 0 0 0 Ps 1 0 0 1 0 0 Po 0 1 1 0 0 0
生成图 3 所示的格代数结构。除 (79, abce) 之外， 图 3、图 2 中的其他结点均一致，这也从侧面反映 了这样一个事实，即无论是基于准则 2，还是基于 准则 3，所构造的模型可能会得到相似的结论。 表 7 表 5 的一个粒化形式背景 Table 7 A granular formal context from table 5 a b c d e {1} 0 0 0 1 1 {2} 1 0 0 1 1 {3, 4} 1 0 0 1 0 {5} 1 0 1 1 0 {6} 1 0 1 0 0 {7, 8} 1 0 1 0 1 {7, 9} 1 1 1 0 1 (23456789,a) (123456789,ø) (ø,abcde) (12345,d) (12789,e) (12,de) (2,ade) (2789,ae) (2345,ad) (56789,ac) (5,acd) (789,ace) (79,abce) 图 3 基于准则 3 从表 5 导出的概念格结构 Fig. 3 Concept lattice structure derived from Table 5 based on Criterion 3 ⌢ 定义 8 称 K = (∆, M, J) 是 K = (G, M, I) 的 粒化背景，若 (D, m) ∈ J ⇔ Vm(D) = 1 ⌢ K ⌢ X ∈ 2 在粒化背景 中，对于任意 ∆，记 ⌢ X ′ = {m ∈ M| (D, m) ∈ J, ∀D ∈ ⌢ X} B ∈ 2 对于任意 M ，记 B ′ = {D ∈ ∆| (D, m) ∈ J, ∀m ∈ B} 其中， (D, m) ∈ J 亦可表示为 m(D) = 1。 D m m(D) = 1 m(D) = 0 基于准则 3 的知识获取模型，其本质是将分 析尺度放大，以极大相容类为研究对象，而非单 个对象。在准则 3 下，任意 在属性 的取值是 确定的，即要么 成立，要么 成 立，这就意味着，不完备形式背景可以转化为一 个完备的粒化形式背景。事实上，在准则 3 下，无 论是基于定义 7，还是定义 8，得到的格代数结构 本质上是相同的，仅仅在外延表示形式上存在略 微差异。 (X,B) ∈ B(K) ( ⌢ X,B) ∈ B( ⌢ 定理 3 若 ， K) ，则 X = ∪ D∈ ⌢ X D 证明 由定义 7 和定义 8 即得。证毕。 与准则 1 和准则 2 最大的不同是，基于准则 3 的知识获取模型无需对缺失信息进行预判定并 给出估算值，而是直接在原始不完备形式背景上 建立知识获取模型。 5 实例分析 1,2,··· ,9 表 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 患者 (H, yes) (H, no) (M, yes) (M, no) (T, high) (T, very high) (T, normal) (F, yes) (F, no) P1 0 1 1 0 1 0 0 1 0 P2 1 0 0 1 1 0 0 1 0 P3 1 0 1 0 1 1 0 1 0 P4 0 1 1 0 0 0 1 0 1 P5 * 0 0 1 1 0 0 0 1 P6 0 1 1 0 * 1 0 1 0 P7 1 0 0 1 1 0 * 1 0 P8 1 0 0 1 1 0 0 * * P9 0 1 1 0 * 0 1 0 1 第 5 期 王雯，等：概念格在不完备形式背景中的知识获取模型 ·1053·
·1054· 智能系统学报 第14卷 当6=k=1时，用户基于准则1得到的预处理 6}、{2,5,7,8}、{3}、{4,9}是等价类；当1=0.78 结果，如表9所示。其中，当=1时，{1}、{2,5,7， 时，{1,3,6}、{2,5,7,8}、{4,9}是等价类；当 8}、{3}、{6}、{4,9}是等价类；当1=0.89时，{1， A=0.67时，1,2,3,4,5,6,7,8,9}是唯一等价类。 表9表8的一个完备化形式背景 Table 9 Complete formal context generated from table 8 患者 (H,yes) (H,no)(M,yes)(M,no) (T,high) (T,very high) (T,normal) (F,yes) (F,no) P 0 0 0 0 0 P 1 0 0 0 0 1 0 P3 1 0 0 1 0 1 0 Pa 0 0 0 0 1 0 1 Ps 1 0 0 1 0 0 0 1 P6 0 0 1 0 0 P 0 0 0 0 P& 0 0 0 0 0 0 1 当6=k=1、σ=0.78时，用户基于准则2同样 {3}、{4,9}、{5,8}、{6}。在此基础上，基于定义 可以得到如表9所示的预处理结果，其中，{1,6}、 7或定义8，用户可得到相应的格代数结构。经验 {2,5,7,8}、{3,6}、{4,9}是极大相容类。 证明，基于准则3直接从表8得到的概念内涵集 事实上，表9中的完备化结果与下述事实性 与基于准则1或准则2间接从表8中得到的概念 规则是吻合的，这也在一定程度上反应了准则 内涵集是相同的。显然，在这种情形下，依据有 1和准则2的合理性和有效性。例如，当患者体 效性判定准则给出的判定原理，可以在一定程度 温是“very high'”时，则其体温一定也是high”;当 认为基于准则1、准则2或准则3构建的模型是 患者体温“normal'时，则其体温一定不是high” 合理的，相应的求解结果也是可信的。 和“very high”;当患者“Flu,yes”时，则一定不是 总体来看，准则1和准则2需要引人阈值参 Flu,no”等。 数，属于间接处理模型：而准则3则无需引入阈 事实性规则：(T,very high)→(T,high)、(T,nor- 值，属于直接处理模型。在实际应用中，如果数 mal)(T,high)、(T,normal)(T,very high)、(H, 据缺失量大，本文倾向于选用直接处理模型，因 yes)(H,no)、(H,no)(H,yes)、(F,no)(F,yes)、 为先选择间接模型可能会导致原始数据集失真： (F,yes)(F,no) 如果数据缺失量少，则无论是直接模型还是间接 在概念格经典理论中，概念内涵和蕴涵规则 模型，都可以选用。 都占有极其重要的地位。本文认为，无论间接处 理模型，还是直接处理模型，它们都应该得到相 6结束语 同的内涵集和蕴涵规则集（内涵集和蕴涵规则集 是相互唯一决定的)。据此，本文提出了如下有效 为消除不完备信息带来的影响，使概念格模 性判定准则： 型具有更强的数据处理能力与更广的应用领域， 有效性判定准则对于同一个不完备形式背 本文尝试将经典形式背景中的知识获取方法进一 景，若多个不同模型得到的蕴涵规则集合或内涵 步拓展到不完备形式背景中，依次探讨了基于等 集合是相同的，则本文认为这些模型在一定程 价类的分析模型和基于极大相容类的分析模型。 度上是有效的，得到的结果在一定程度上也是可 在实际应用中，用户既可以选择基于准则1或准 信的。 则2的间接处理模型，也可以选择基于准则3的 定义9设K=(G,M,)为一个形式背景， 直接处理模型。此外，对于模型的机制有效性和 B1、B2SM。若B1SB,则称B1→B2是K中的蕴 结果可信性，本文也尝试性的进行了探讨，并提 涵规则。 出了一些初步的验证方法。相信本文所做的工作 准则3相对应的极大相容类有{1}、2,7,8}、 能为下一步相关研究提供一些有益的思路
δ = κ = 1 λ = 1 λ = 0.89 当 时，用户基于准则 1 得到的预处理 结果，如表 9 所示。其中，当 时，{1}、{2, 5, 7, 8}、{3}、{6}、{4, 9}是等价类；当 时，{1, λ = 0.78 λ = 0.67 6}、{2, 5, 7, 8}、{3}、{4, 9}是等价类；当 时 ，{1, 3, 6}、{2, 5, 7, 8}、{4, 9}是等价类；当 时，{1, 2, 3, 4, 5, 6, 7, 8, 9}是唯一等价类。 表 9 表 8 的一个完备化形式背景 Table 9 Complete formal context generated from table 8 患者 (H, yes) (H, no) (M, yes) (M, no) (T, high) (T, very high) (T, normal) (F, yes) (F, no) P1 0 1 1 0 1 0 0 1 0 P2 1 0 0 1 1 0 0 1 0 P3 1 0 1 0 1 1 0 1 0 P4 0 1 1 0 0 0 1 0 1 P5 1 0 0 1 1 0 0 0 1 P6 0 1 1 0 1 1 0 1 0 P7 1 0 0 1 1 0 0 1 0 P8 1 0 0 1 1 0 0 1 0 P9 0 1 1 0 0 0 1 0 1 当 δ = κ = 1、σ = 0.78 时，用户基于准则 2 同样 可以得到如表 9 所示的预处理结果，其中，{1, 6}、 {2, 5, 7, 8}、{3, 6}、{4, 9}是极大相容类。 事实上，表 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)。 在概念格经典理论中，概念内涵和蕴涵规则 都占有极其重要的地位。本文认为，无论间接处 理模型，还是直接处理模型，它们都应该得到相 同的内涵集和蕴涵规则集 (内涵集和蕴涵规则集 是相互唯一决定的)。据此，本文提出了如下有效 性判定准则： 有效性判定准则对于同一个不完备形式背 景，若多个不同模型得到的蕴涵规则集合或内涵 集合是相同的，则本文认为这些模型在一定程 度上是有效的，得到的结果在一定程度上也是可 信的。 K = (G, M, I) B1 B2 ⊆ M B ′ 1 ⊆ B ′ 2 B1 → B2 K 定义 9 设 为一个形式背景， 、 。若 ，则称 是 中的蕴 涵规则。 准则 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 的 直接处理模型。此外，对于模型的机制有效性和 结果可信性，本文也尝试性的进行了探讨，并提 出了一些初步的验证方法。相信本文所做的工作 能为下一步相关研究提供一些有益的思路。 ·1054· 智 能 系 统 学 报 第 14 卷
第5期 王雯，等：概念格在不完备形式背景中的知识获取模型 ·1055· 参考文献： ZHANG Huiwen,LIU Wenqi,LI Jinhai.Axiomatic char- acterizations of approximate concept lattices in incom- [1]WILLE R.Restructuring lattice theory:an approach based plete contexts[J].Computer science,2015,42(6):67-70, on hierarchies of concepts[M].RIVAL I.Ordered Sets. 92 Dordrecht:Reidel,1982:445-470. [14]智慧来.不完备形式背景上的知识表示[.计算机科 [2]张文修，姚一豫，梁怡.粗糙集与概念格M.西安：西安 学，2015.42(1)：276-278. 交通大学出版社，2006. ZHI Huilai.Knowledge representation on incomplete [3]仇国芳，张志霞，张炜.基于粗糙集方法的概念格理论研 formal context[J].Computer science,2015,42(1): 究综述).模糊系统与数学，2014,28(1)少：168-177. 276-278. QIU Guofang,ZHANG Zhixia,ZHANG Wei.A survey for [15]李磊军，李美争，解滨，等.三支决策视角下概念格的分 study on concept lattice theory via rough set[J].Fuzzy sys- 析和比较J1.模式识别与人工智能，2016,29(10)： tems and mathematics,2014,28(1):168-177. 951-960. [4]王国胤.Rough集理论在不完备信息系统中的扩充). LI Leijun,LI Meizheng,XIE Bin,et al.Analysis and 计算机研究与发展，2002,39(10)：1238-1243. comparison of concept lattices from the perspective of WANG Guoyin.Extension of rough set under incomplete three-way decisions[J].Pattern recognition and artificial information systems[J].Journal of computer research and intelligence,2016,29(10y:951-960. development,.2002,39(10):1238-1243. [16]王振，魏玲.基于单边区间集概念格的不完备形式背景 [5]KRYSZKIEWICZ M.Rough set approach to incomplete 的属性约简[U.计算机科学，2018,45(1)：73-78. information systems[J].Information sciences,1998, WANG Zhen,WEI Ling.Attribute reduction of partially- 112(1/2/3/4):39-49. known formal concept lattices for incomplete contexts[J]. [6]KRYSZKIEWICZ M.Rules in incomplete information Computer science,2018,45(1):73-78. systems[J].Information sciences,1999,113(3/4):271-292. [17]GANTER B,WILLE R.Formal concept analysis:math- [7]STEFANOWSKI J,TSOUKIAS A.Incomplete informa- ematical foundations[M].Berlin:Springer-Verlag,1999. tion tables and rough classification[J].Computational intel- 作者简介： 1 igence,.2001,17(3):546-566. 王雯，女，1984年生，硕士研究 [8]LEUNG Y.LI Deyu.Maximal consistent block technique 生，主要研究方向为智能控制理论及 for rule acquisition in incomplete information systems[J]. 应用、粒计算。 Information sciences,2003,153:85-106. [9]ZHANG Wenxiu,MI Jusheng.Incomplete information system and its optimal selections[J].Computers &mathem- atics with applications.2004,48(5/6):691-698. [10]YAO Yiyu.Interval sets and three-way concept analysis 康向平，男，1982年生，博士研究 in incomplete contexts[J].International journal of ma 生，主要研究方向为粗糙集、概念格、 chine learning and cybernetics,2017,8(1):3-20. 粒计算。 [11]LI Jinhai,MEI Changlin,LV Yuejin.Incomplete de- cision contexts:approximate concept construction,rule acquisition and knowledge reduction[J].International journal of approximate reasoning,2013,54(1):149-165 [12]LI Meizheng,WANG Guoyi.Approximate concept con- 武燕，女，1982年生，硕士研究 生，主要研究方向为智能信息处理。 struction with three-way decisions and attribute reduction in incomplete contexts[J].Knowledge-based systems, 2016.91:165-178 [13]张慧雯，刘文奇，李金海.完备形式背景下近似概念格 的公理化方法[.计算机科学，2015,42(6)：67-70,92
参考文献： WILLE R. Restructuring lattice theory: an approach based on hierarchies of concepts[M].RIVAL I. Ordered Sets. Dordrecht: Reidel, 1982: 445–470. [1] 张文修, 姚一豫, 梁怡. 粗糙集与概念格 [M]. 西安: 西安 交通大学出版社, 2006. [2] 仇国芳, 张志霞, 张炜. 基于粗糙集方法的概念格理论研 究综述 [J]. 模糊系统与数学, 2014, 28(1): 168–177. QIU Guofang, ZHANG Zhixia, ZHANG Wei. A survey for study on concept lattice theory via rough set[J]. Fuzzy systems and mathematics, 2014, 28(1): 168–177. [3] 王国胤. Rough 集理论在不完备信息系统中的扩充 [J]. 计算机研究与发展, 2002, 39(10): 1238–1243. WANG Guoyin. Extension of rough set under incomplete information systems[J]. Journal of computer research and development, 2002, 39(10): 1238–1243. [4] KRYSZKIEWICZ M. Rough set approach to incomplete information systems[J]. Information sciences, 1998, 112(1/2/3/4): 39–49. [5] KRYSZKIEWICZ M. Rules in incomplete information systems[J]. Information sciences, 1999, 113(3/4): 271–292. [6] STEFANOWSKI J, TSOUKIÀS A. Incomplete information tables and rough classification[J]. Computational intelligence, 2001, 17(3): 546–566. [7] LEUNG Y, LI Deyu. Maximal consistent block technique for rule acquisition in incomplete information systems[J]. Information sciences, 2003, 153: 85–106. [8] ZHANG Wenxiu, MI Jusheng. Incomplete information system and its optimal selections[J]. Computers &mathematics with applications, 2004, 48(5/6): 691–698. [9] YAO Yiyu. Interval sets and three-way concept analysis in incomplete contexts[J]. International journal of machine learning and cybernetics, 2017, 8(1): 3–20. [10] LI Jinhai, MEI Changlin, LV Yuejin. Incomplete decision contexts: approximate concept construction, rule acquisition and knowledge reduction[J]. International journal of approximate reasoning, 2013, 54(1): 149–165. [11] LI Meizheng, WANG Guoyi. Approximate concept construction with three-way decisions and attribute reduction in incomplete contexts[J]. Knowledge-based systems, 2016, 91: 165–178. [12] 张慧雯, 刘文奇, 李金海. 完备形式背景下近似概念格 的公理化方法 [J]. 计算机科学, 2015, 42(6): 67–70, 92. [13] ZHANG Huiwen, LIU Wenqi, LI Jinhai. Axiomatic characterizations of approximate concept lattices in incomplete contexts[J]. Computer science, 2015, 42(6): 67–70, 92. 智慧来. 不完备形式背景上的知识表示 [J]. 计算机科 学, 2015, 42(1): 276–278. ZHI Huilai. Knowledge representation on incomplete formal context[J]. Computer science, 2015, 42(1): 276–278. [14] 李磊军, 李美争, 解滨, 等. 三支决策视角下概念格的分 析和比较 [J]. 模式识别与人工智能, 2016, 29(10): 951–960. LI Leijun, LI Meizheng, XIE Bin, et al. Analysis and comparison of concept lattices from the perspective of three-way decisions[J]. Pattern recognition and artificial intelligence, 2016, 29(10): 951–960. [15] 王振, 魏玲. 基于单边区间集概念格的不完备形式背景 的属性约简 [J]. 计算机科学, 2018, 45(1): 73–78. WANG Zhen, WEI Ling. Attribute reduction of partiallyknown formal concept lattices for incomplete contexts[J]. Computer science, 2018, 45(1): 73–78. [16] GANTER B, WILLE R. Formal concept analysis: mathematical foundations[M]. Berlin: Springer-Verlag, 1999. [17] 作者简介： 王雯，女，1984 年生，硕士研究 生，主要研究方向为智能控制理论及 应用、粒计算。 康向平，男，1982 年生，博士研究 生，主要研究方向为粗糙集、概念格、 粒计算。 武燕，女，1982 年生，硕士研究 生，主要研究方向为智能信息处理。 第 5 期 王雯，等：概念格在不完备形式背景中的知识获取模型 ·1055·