第11卷第3期 智能系统学报 Vol.11 No.3 2016年6月 CAAI Transactions on Intelligent Systems Jun.2016 D0I:10.11992/is.201603055 网络出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20160513.0920.018.html 一种基于概念格的集值信息系统中的知识获取方法 康向平12，苗夺谦12 (1.同济大学计算机科学与技术系，上海201804：2.同济大学嵌入式系统与服务计算教育部重点实验室，上海 201804) 摘要：以集值信息系统为研究背景，以概念格为理论基础，提出了一种基于概念格的集值信息系统中的知识获取 方法。该模型首先将复杂的集值信息系统转化为形式上更加简单的单值背景，然后借助概念格理论，重点探讨了基 于相容关系的粒化模型和集值系统中的格代数结构，该代数结构可以将论域中的所有覆盖以格的形式有机结织起 来。此外，探讨了集值信息系统中的约简、核等问题。本文有助于拓展概念格的应用范围，同时也为集值信息系统 的分析和处理提供了一种有益思路。 关键词：粗糙集：概念格：集值信息系统：相容关系：代数结构 中图分类号：TP18文献标志码：A文章编号：1673-4785(2016)03-0287-07 中文引用格式：康向平，苗夺谦.一种基于概念格的集值信息系统中的知识获取方法[J】.智能系统学报，2016,11(3)：287-293. 英文引用格式：KANG Xiangping,MIAO Duoqian..A knowledge acquisition method based on concept lattice in set-valued informa- tion systems [J].CAAI transactions on intelligent systems,2016,11(3):287-293. A knowledge acquisition method based on concept lattice in set-valued information systems KANG Xiangping'2,MIAO Duoqian'2 (1.Department of Computer Science and Technology,Tongji University,Shanghai 201804,China;2.Key Laboratory of Embedded System and Service Computing.Ministry of Education,Tongji University,Shanghai 201804,China) Abstract:The paper takes set-valued information systems as research background,proposes a knowledge acquisition method on the basis of concept lattice.The model can transforms a complicated set-valued information system into a simpler one-valued context,and then by means of concept lattice,emphasizes the granularity model based on toler- ance relation and the algebra structure in the set-valued information system,where the algebraic structure can or- ganize all covers in the form of lattice structure,and it can be considered an important algebraic structure in the set- valued information system.Meanwhile,the paper also offers some simple solutions to common problems,such as re- duction,core.In short,this paper not only helps to explore the application range of concept lattice,but also offers a useful idea for the analysis and processing of set-valued information systems. Keywords:rough set;concept lattice;set-valued information systems;tolerance relations;algebraic structure 针对模糊、不确定等问题，波兰学者Pawlak基 效获取知识，相对来讲会更加客观和易用。近年来， 于粒化和近似思想于1982年提出了粗糙集)，该理 粗糙集正快速从单一理论向多理论融合方向发展、 论于20世纪90年代逐步走向成熟并随后引起了国 从简单应用向复杂数据建模方向延伸，其相关研究 内外学者的广泛关注)。与其他类似理论相比较， 成果已被广泛应用于数据挖掘、机器学习等领 其不需要借助复杂的先验知识便可以在数据集中有 域[3]。 概念格是与粗糙集同时代产生的一种数据分析 收稿日期：2016-03-28.网络出版日期：2016-05-13. 基金项目：国家自然科学基金项目(61273304,61202170)：国家博士后 工具)，其最早是由德国学者Wille基于人脑的概 科学基金项目(2014M560352);高等学校博士学科点专项科 念思维提出来的。在概念格构筑的理论体系中，概 研基金项目(20130072130004). 通信作者：康向平.E-mail:tongji_kangxp@sina.com 念、格代数结构，伽罗瓦(Galois)连接等是核心要
第 １１ 卷第 ３ 期 智 能 系 统 学 报 Ｖｏｌ．１１ №．３ ２０１６ 年 ６ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｊｕｎ． ２０１６ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１６０３０５５ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１６０５１３．０９２０．０１８．ｈｔｍｌ 一种基于概念格的集值信息系统中的知识获取方法 康向平１，２ ， 苗夺谦１，２ （１．同济大学 计算机科学与技术系，上海 ２０１８０４； ２． 同济大学 嵌入式系统与服务计算教育部重点实验室，上海 ２０１８０４） 摘 要：以集值信息系统为研究背景，以概念格为理论基础，提出了一种基于概念格的集值信息系统中的知识获取 方法。 该模型首先将复杂的集值信息系统转化为形式上更加简单的单值背景，然后借助概念格理论，重点探讨了基 于相容关系的粒化模型和集值系统中的格代数结构，该代数结构可以将论域中的所有覆盖以格的形式有机结织起 来。 此外，探讨了集值信息系统中的约简、核等问题。 本文有助于拓展概念格的应用范围，同时也为集值信息系统 的分析和处理提供了一种有益思路。 关键词：粗糙集；概念格；集值信息系统；相容关系；代数结构 中图分类号：ＴＰ１８ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１６）０３⁃０２８７⁃０７ 中文引用格式：康向平， 苗夺谦．一种基于概念格的集值信息系统中的知识获取方法［Ｊ］． 智能系统学报， ２０１６， １１（３）： ２８７⁃２９３． 英文引用格式：ＫＡＮＧ Ｘｉａｎｇｐｉｎｇ， ＭＩＡＯ Ｄｕｏｑｉａｎ． Ａ ｋｎｏｗｌｅｄｇｅ ａｃｑｕｉｓｉｔｉｏｎ ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ ｉｎ ｓｅｔ⁃ｖａｌｕｅｄ ｉｎｆｏｒｍａ⁃ ｔｉｏｎ ｓｙｓｔｅｍｓ ［Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１６，１１（３）： ２８７⁃２９３． Ａ ｋｎｏｗｌｅｄｇｅ ａｃｑｕｉｓｉｔｉｏｎ ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ ｉｎ ｓｅｔ⁃ｖａｌｕｅｄ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍｓ ＫＡＮＧ Ｘｉａｎｇｐｉｎｇ １，２ ， ＭＩＡＯ Ｄｕｏｑｉａｎ １，２ （１． Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， Ｔｏｎｇｊｉ Ｕｎｉｖｅｒｓｉｔｙ， Ｓｈａｎｇｈａｉ ２０１８０４， Ｃｈｉｎａ； ２． Ｋｅｙ Ｌａｂｏｒａｔｏｒｙ ｏｆ Ｅｍｂｅｄｄｅｄ Ｓｙｓｔｅｍ ａｎｄ Ｓｅｒｖｉｃｅ Ｃｏｍｐｕｔｉｎｇ， Ｍｉｎｉｓｔｒｙ ｏｆ Ｅｄｕｃａｔｉｏｎ， Ｔｏｎｇｊｉ Ｕｎｉｖｅｒｓｉｔｙ， Ｓｈａｎｇｈａｉ ２０１８０４， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｐａｐｅｒ ｔａｋｅｓ ｓｅｔ⁃ｖａｌｕｅｄ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍｓ ａｓ ｒｅｓｅａｒｃｈ ｂａｃｋｇｒｏｕｎｄ， ｐｒｏｐｏｓｅｓ ａ ｋｎｏｗｌｅｄｇｅ ａｃｑｕｉｓｉｔｉｏｎ ｍｅｔｈｏｄ ｏｎ ｔｈｅ ｂａｓｉｓ ｏｆ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ． Ｔｈｅ ｍｏｄｅｌ ｃａｎ ｔｒａｎｓｆｏｒｍｓ ａ ｃｏｍｐｌｉｃａｔｅｄ ｓｅｔ⁃ｖａｌｕｅｄ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍ ｉｎｔｏ ａ ｓｉｍｐｌｅｒ ｏｎｅ⁃ｖａｌｕｅｄ ｃｏｎｔｅｘｔ， ａｎｄ ｔｈｅｎ ｂｙ ｍｅａｎｓ ｏｆ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ， ｅｍｐｈａｓｉｚｅｓ ｔｈｅ ｇｒａｎｕｌａｒｉｔｙ ｍｏｄｅｌ ｂａｓｅｄ ｏｎ ｔｏｌｅｒ⁃ ａｎｃｅ ｒｅｌａｔｉｏｎ ａｎｄ ｔｈｅ ａｌｇｅｂｒａ ｓｔｒｕｃｔｕｒｅ ｉｎ ｔｈｅ ｓｅｔ⁃ｖａｌｕｅｄ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍ， ｗｈｅｒｅ ｔｈｅ ａｌｇｅｂｒａｉｃ ｓｔｒｕｃｔｕｒｅ ｃａｎ ｏｒ⁃ ｇａｎｉｚｅ ａｌｌ ｃｏｖｅｒｓ ｉｎ ｔｈｅ ｆｏｒｍ ｏｆ ｌａｔｔｉｃｅ ｓｔｒｕｃｔｕｒｅ， ａｎｄ ｉｔ ｃａｎ ｂｅ ｃｏｎｓｉｄｅｒｅｄ ａｎ ｉｍｐｏｒｔａｎｔ ａｌｇｅｂｒａｉｃ ｓｔｒｕｃｔｕｒｅ ｉｎ ｔｈｅ ｓｅｔ⁃ ｖａｌｕｅｄ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍ． Ｍｅａｎｗｈｉｌｅ， ｔｈｅ ｐａｐｅｒ ａｌｓｏ ｏｆｆｅｒｓ ｓｏｍｅ ｓｉｍｐｌｅ ｓｏｌｕｔｉｏｎｓ ｔｏ ｃｏｍｍｏｎ ｐｒｏｂｌｅｍｓ， ｓｕｃｈ ａｓ ｒｅ⁃ ｄｕｃｔｉｏｎ， ｃｏｒｅ． Ｉｎ ｓｈｏｒｔ， ｔｈｉｓ ｐａｐｅｒ ｎｏｔ ｏｎｌｙ ｈｅｌｐｓ ｔｏ ｅｘｐｌｏｒｅ ｔｈｅ ａｐｐｌｉｃａｔｉｏｎ ｒａｎｇｅ ｏｆ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ， ｂｕｔ ａｌｓｏ ｏｆｆｅｒｓ ａ ｕｓｅｆｕｌ ｉｄｅａ ｆｏｒ ｔｈｅ ａｎａｌｙｓｉｓ ａｎｄ ｐｒｏｃｅｓｓｉｎｇ ｏｆ ｓｅｔ⁃ｖａｌｕｅｄ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍｓ． Ｋｅｙｗｏｒｄｓ：ｒｏｕｇｈ ｓｅｔ； ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ； ｓｅｔ⁃ｖａｌｕｅｄ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍｓ； ｔｏｌｅｒａｎｃｅ ｒｅｌａｔｉｏｎｓ； ａｌｇｅｂｒａｉｃ ｓｔｒｕｃｔｕｒｅ 收稿日期：２０１６⁃０３⁃２８． 网络出版日期：２０１６⁃０５⁃１３． 基金项目：国家自然科学基金项目（ ６１２７３３０４， ６１２０２１７０）；国家博士后 科学基金项目（２０１４Ｍ５６０３５２）；高等学校博士学科点专项科 研基金项目（２０１３００７２１３０００４）． 通信作者：康向平． Ｅ⁃ｍａｉｌ：ｔｏｎｇｊｉ＿ｋａｎｇｘｐ＠ ｓｉｎａ．ｃｏｍ． 针对模糊、不确定等问题，波兰学者 Ｐａｗｌａｋ 基 于粒化和近似思想于 １９８２ 年提出了粗糙集［１］ ，该理 论于 ２０ 世纪 ９０ 年代逐步走向成熟并随后引起了国 内外学者的广泛关注［２］ 。 与其他类似理论相比较， 其不需要借助复杂的先验知识便可以在数据集中有 效获取知识，相对来讲会更加客观和易用。 近年来， 粗糙集正快速从单一理论向多理论融合方向发展、 从简单应用向复杂数据建模方向延伸，其相关研究 成果已 被 广 泛 应 用 于 数 据 挖 掘、 机 器 学 习 等 领 域［３⁃５］ 。 概念格是与粗糙集同时代产生的一种数据分析 工具［６］ ，其最早是由德国学者 Ｗｉｌｌｅ 基于人脑的概 念思维提出来的。 在概念格构筑的理论体系中，概 念、格代数结构，伽罗瓦（Ｇａｌｏｉｓ） 连接等是核心要
·288· 智能系统学报 第11卷 素。其中，概念可以分别从内涵和外延两个不同角 差信息，存在一定的局限性。针对上述情况，许多学 度进行刻画，具有丰富的语义，有助于深化人们对现 者尝试发展直接面向集值信息系统的知识获取方 实生活中概念的概要认识和准确理解：代数格结构 法[3]，诸如基于相容关系、优势关系等的粗糙集 作为一种基于序关系建立起来的概念层次模型，客 模型。直接处理方法不经过数据预处理，能直接对 观上反映了概念之间的泛化/特化关系：伽罗瓦连接 原始数据进行处理，可以有效避免由于数据预处理 则为生成概念和代数结构的核心理论基础。近年 不当所导致的偏差逐层传导扩大。 来，关于概念格的基础理论研究和应用拓展已经取 针对上述不确定性问题，同时考虑到概念格在 得了一系列重要成果[.1o] 二元关系分析中的良好数学基础，本文引入了概念 虽然上述理论方法上存在一定差异，但集合论 格，并重点探讨了基于相容关系的粒化模型和集值 和二元关系都是它们的建模基础，同时它们均面向 系统中的格代数结构，该代数结构可以将论域中的 相类似的数据集，这就意味着它们之间可能存在着 所有覆盖以格的形式有机结织起来。此外，本文还 某种紧密的关联。在充分挖掘它们各自理论优势的 重点探讨了集值信息系统中的约简、核等问题。总 基础上，探讨二者之间的融合理论必将有助于粗糙 的来讲，本文结论一方面有助于拓展概念格的应用 集和概念格的进一步拓展。近年来，许多学者探讨 范围，另一方面也为集值信息系统的分析和处理提 了它们之间的融合理论。一些学者把概念格中 供了一种有益思路。 的概念思维、格代数结构、伽罗瓦连接等要素引入到 1概念格 粗糙集中，探讨了信息系统中的格代数结构、约简、 规则获取等2)：一些学者把形式背景视为一类特 定义1一个形式背景通常由一个三元组 殊的信息系统，然后借助粗糙集中的近似算子和区 (G,M,I)来表示，其中G和M分别是非空有限的对 分矩阵，提出了概念格中的粗糙概念分析、属性约 象集和属性集，I二GxM。一个典型的形式背景如表 简，以及上近似格和下近似格等[46；一些学者从 1所示，其中websitel,website2,…,website6分别 不同角度对比了两种理论，揭示了它们之间的紧密 表示一些网站的编号；Finance,Culture,…,Shop 联系[20]，这样做不仅有助于人们从不同角度深化 ping则表示上述网站可能涉及的一些主题：若某个 对单一理论的认识和理解，同时也有助于两种理论 网站含有某种主题，用“×”进行标记。 之间的深度融合。 表1一个典型的形式背景 在关于经典信息系统的描述中，对象在属性下 Table 1 A typical formal context 的取值是唯一的。然而，在一些复杂的信息系统，对 Finance Culture Military History Shopping 象在属性下的取值有时可能不是一个值，而是由若 website 1 + 干个元素组成的一个非空集合，即取值不是一个值 website 2 + 而是一个集合。当取值是一个集合时，若其代表一 website 3 个取值范围，那么此时取值就存在一定的不确定性。 website 4 × 例如，在地震预测中，不同专家可能得出不一样的预 测结果，也许这些预测结果都是合理的，但却只有一 website 5 种预测是正确的。据此，人们将经典信息系统进一 website 6 步泛化为集值信息系统。本质上，信息的不完备性 定义2定义1在形式背景(G,M,)中，对于 也可以理解为上述不确定性的一种特殊情况2122]。 任意X∈P(G),定义 例如，在不完备信息系统中，针对取值缺失的情况， X°={m∈Ml(x,m)∈I,Hx∈X} 人们通常会用一个集合替代某个缺失值，即依据先 相应地，对于任意B∈P(M),定义 验知识或算法将缺失值限定在某个范围，并将该范 B·={x∈Gl(x,m)∈I,Hm∈B} 围视为缺失值。在此意义下，不完备信息系统本质 其中P(G)和P(M)分别是G和M的幂集。如 上是一种特殊的集值信息系统。针对上述不确定 果X·=B且B·=X,则称(X,B)是一个形式概念，其 性，以往人们更多采用的是一些间接的知识获取方 中X和B分别是外延和内涵。若将任意概念 法，即数据建模是建立在对数据预处理的基础之上。 (X1,B)和(X2,B2)之间的序关系“≤”定义为 此类方法虽然简单易用，但数据预处理可能会丢失 (X1,B)≤(X2,B2)台X1SX2台B12B2 大量的有用信息或由于人为因素增加一些额外的偏 在此意义下，偏序集(B(G,M,I),≤)本质上是
素。 其中，概念可以分别从内涵和外延两个不同角 度进行刻画，具有丰富的语义，有助于深化人们对现 实生活中概念的概要认识和准确理解；代数格结构 作为一种基于序关系建立起来的概念层次模型，客 观上反映了概念之间的泛化／ 特化关系；伽罗瓦连接 则为生成概念和代数结构的核心理论基础。 近年 来，关于概念格的基础理论研究和应用拓展已经取 得了一系列重要成果［７⁃１０］ 。 虽然上述理论方法上存在一定差异，但集合论 和二元关系都是它们的建模基础，同时它们均面向 相类似的数据集，这就意味着它们之间可能存在着 某种紧密的关联。 在充分挖掘它们各自理论优势的 基础上，探讨二者之间的融合理论必将有助于粗糙 集和概念格的进一步拓展。 近年来，许多学者探讨 了它们之间的融合理论［１１］ 。 一些学者把概念格中 的概念思维、格代数结构、伽罗瓦连接等要素引入到 粗糙集中，探讨了信息系统中的格代数结构、约简、 规则获取等［１２⁃１３］ ；一些学者把形式背景视为一类特 殊的信息系统，然后借助粗糙集中的近似算子和区 分矩阵，提出了概念格中的粗糙概念分析、属性约 简，以及上近似格和下近似格等［１４⁃１６］ ；一些学者从 不同角度对比了两种理论，揭示了它们之间的紧密 联系［１７⁃２０］ ，这样做不仅有助于人们从不同角度深化 对单一理论的认识和理解，同时也有助于两种理论 之间的深度融合。 在关于经典信息系统的描述中，对象在属性下 的取值是唯一的。 然而，在一些复杂的信息系统，对 象在属性下的取值有时可能不是一个值，而是由若 干个元素组成的一个非空集合，即取值不是一个值 而是一个集合。 当取值是一个集合时，若其代表一 个取值范围，那么此时取值就存在一定的不确定性。 例如，在地震预测中，不同专家可能得出不一样的预 测结果，也许这些预测结果都是合理的，但却只有一 种预测是正确的。 据此，人们将经典信息系统进一 步泛化为集值信息系统。 本质上，信息的不完备性 也可以理解为上述不确定性的一种特殊情况［２１⁃２２］ 。 例如，在不完备信息系统中，针对取值缺失的情况， 人们通常会用一个集合替代某个缺失值，即依据先 验知识或算法将缺失值限定在某个范围，并将该范 围视为缺失值。 在此意义下，不完备信息系统本质 上是一种特殊的集值信息系统。 针对上述不确定 性，以往人们更多采用的是一些间接的知识获取方 法，即数据建模是建立在对数据预处理的基础之上。 此类方法虽然简单易用，但数据预处理可能会丢失 大量的有用信息或由于人为因素增加一些额外的偏 差信息，存在一定的局限性。 针对上述情况，许多学 者尝试发展直接面向集值信息系统的知识获取方 法［２３⁃２８］ ，诸如基于相容关系、优势关系等的粗糙集 模型。 直接处理方法不经过数据预处理，能直接对 原始数据进行处理，可以有效避免由于数据预处理 不当所导致的偏差逐层传导扩大。 针对上述不确定性问题，同时考虑到概念格在 二元关系分析中的良好数学基础，本文引入了概念 格，并重点探讨了基于相容关系的粒化模型和集值 系统中的格代数结构，该代数结构可以将论域中的 所有覆盖以格的形式有机结织起来。 此外，本文还 重点探讨了集值信息系统中的约简、核等问题。 总 的来讲，本文结论一方面有助于拓展概念格的应用 范围，另一方面也为集值信息系统的分析和处理提 供了一种有益思路。 １ 概念格 定义 １ 一个形式背景通常由一个三元组 (Ｇ，Ｍ，Ｉ) 来表示，其中 Ｇ 和 Ｍ 分别是非空有限的对 象集和属性集，Ｉ⊆Ｇ×Ｍ。 一个典型的形式背景如表 １ 所示，其中 ｗｅｂｓｉｔｅ１， ｗｅｂｓｉｔｅ２， …， ｗｅｂｓｉｔｅ６ 分别 表示一些网站的编号；Ｆｉｎａｎｃｅ， Ｃｕｌｔｕｒｅ， …， Ｓｈｏｐ⁃ ｐｉｎｇ 则表示上述网站可能涉及的一些主题；若某个 网站含有某种主题，用“×”进行标记。 表 １ 一个典型的形式背景 Ｔａｂｌｅ １ Ａ ｔｙｐｉｃａｌ ｆｏｒｍａｌ ｃｏｎｔｅｘｔ Ｆｉｎａｎｃｅ Ｃｕｌｔｕｒｅ Ｍｉｌｉｔａｒｙ Ｈｉｓｔｏｒｙ Ｓｈｏｐｐｉｎｇ ｗｅｂｓｉｔｅ １ × × × ｗｅｂｓｉｔｅ ２ × × × × ｗｅｂｓｉｔｅ ３ × × × × ｗｅｂｓｉｔｅ ４ × × × × ｗｅｂｓｉｔｅ ５ × × × × ｗｅｂｓｉｔｅ ６ × × × 定义 ２ 定义 １ 在形式背景(Ｇ，Ｍ，Ｉ) 中，对于 任意 Ｘ∈Ｐ(Ｇ) ，定义 Ｘ ∗ ＝ {ｍ ∈ Ｍ ｜ (ｘ，ｍ) ∈ Ｉ，∀ｘ ∈ Ｘ} 相应地，对于任意 Ｂ∈Ｐ(Ｍ) ，定义 Ｂ ∗ ＝ {ｘ ∈ Ｇ ｜ (ｘ，ｍ) ∈ Ｉ，∀ｍ ∈ Ｂ} 其中 Ｐ(Ｇ) 和 Ｐ(Ｍ) 分别是 Ｇ 和 Ｍ 的幂集。 如 果 Ｘ ∗ ＝Ｂ 且 Ｂ ∗ ＝Ｘ，则称(Ｘ，Ｂ) 是一个形式概念，其 中 Ｘ 和 Ｂ 分 别 是 外 延 和 内 涵。 若 将 任 意 概 念 Ｘ１ ，Ｂ１ ( ) 和 Ｘ２ ，Ｂ２ ( ) 之间的序关系“≤”定义为 Ｘ１ ，Ｂ１ ( ) ≤ Ｘ２ ，Ｂ２ ( ) ⇔Ｘ１ ⊆ Ｘ２⇔Ｂ１ ⊇ Ｂ２ 在此意义下，偏序集(Ｂ(Ｇ，Ｍ，Ｉ) ，≤) 本质上是 ·２８８· 智 能 系 统 学 报 第 １１ 卷
第3期 康向平，等：一种基于概念格的集值信息系统中的知识获取方法 .289. 一个完备格，其中B(G,M,)是所有概念组的集合。 单值背景中的经典算子往往并不适用于多值的 引理1在形式背景(G,M,)中，对于任意BC 信息系统。即若采用定义1中的算子，必须将信息 M,有 系统转化为单值形式背景。由此，针对集值信息系 B··=n{L∈Int(G,M,I)IBCL} 统，本文采用了如下转化策略。 式中Int(G,M,)表示所有概念内涵组成的集合。 定义3设(U,AT,V,F)是一个集值信息系统， 定义3在表1所示的背景中，若a1=Finance、 称(UxU,AT,)是(U,AT,V,F)的衍生形式背景，其 a2=Culture、a3=Military、a4=History、as=Shopping, 中J被描述为：对于任意(x,y）∈U,m∈AT,有 且将websitel,website2.,…,website(6简记为l,2, (x,y）,m)eJs+f(x,m)∩fy,m)≠☑ …,6,则表1中的概念格如图1所示，图1可以直 由于衍生背景不再保留原信息系统中属性值自 观反映信息在不同层次上的聚类。例如，概念 身的信息，仅体现相同属性下不同对象之间的关系， (456,a3auas)揭示website4、website5和website6等 因而在形式上较原信息系统更加简单明了。一个由 网站均含有主题Military、History和Shopping。 表2所示集值信息系统衍生的形式背景如表3。 (123456.a,) 表3一个衍生形式背景 Table 3 A derivative formal context (12345.a,a) (23456.,a,a,) 6 (u1,u1) 123,,a,a) 2345,a,a,a) (1,2) (456,a,0 (u1,u3) + (23,a,a,,a (45.a,04a (41,44) (d,aaaaa) (u1,45) 图1从表1导出的概念格结构 (u1,46) Fig.1 The concept lattice derived from table 1 定义4关于概念格的详细介绍请参阅文献 (ug,u3)】 [29]。 (g,44） 2集值信息系统和单值形式背景 (g,u) (ug,u6） 一个集值信息系统一般由四元组 (ug,4,） (U,AT,V,F)进行表示。其中U是一个非空对象 (us,us) 集，称为论域；AT是一个非空属性集；V=UnEAT'm, 其中Vm是属性m的值域；F={fm:m∈AT},其中 3 集值信息系统中的代数结构和粒 fm:U→P(Vn)。一个典型的集值信息系统如表2。 化模型 表2一个典型的集值信息系统 概念格是一类重要的格代数结构，其在形式概 Table 2 A typical set-valued information system 念分析理论中扮演了重要的角色。据此，本文尝试 b 基于形式概念分析理论重点探讨集值信息系统中的 1,3 格代数结构、信息粒化等问题。其中，本文提到的粒 D1,3 化模型是基于定义3中的相容关系构造的。 "1,D2 2 定义42】设(U,AT,V,F)是一个集值信息系 U1,D2 3 V2 统，对于任意B二AT,论域U中的相容关系定义为 D1, Re={(x,y)∈U1Hm∈B,fx,m)∩fy,m)≠) 定理1设(UxU,AT,J)是(U,AT,V,F)的衍生 D1, 背景，对于任意BCAT,有B·=RB。 4 U1,D2 证明由定义1、定义2和定义3即得，证毕。 Us U1,D3 定义5设R是论域U中的一个相容关系
一个完备格，其中 Ｂ(Ｇ，Ｍ，Ｉ) 是所有概念组的集合。 引理 １ 在形式背景(Ｇ，Ｍ，Ｉ) 中，对于任意 Ｂ⊆ Ｍ，有 Ｂ ∗∗ ＝∩ {Ｌ ∈ Ｉｎｔ(Ｇ，Ｍ，Ｉ) ｜ Ｂ ⊆ Ｌ} 式中 Ｉｎｔ(Ｇ，Ｍ，Ｉ) 表示所有概念内涵组成的集合。 定义 ３ 在表 １ 所示的背景中，若 ａ１ ＝ Ｆｉｎａｎｃｅ、 ａ２ ＝Ｃｕｌｔｕｒｅ、ａ３ ＝ Ｍｉｌｉｔａｒｙ、ａ４ ＝ Ｈｉｓｔｏｒｙ、ａ５ ＝ Ｓｈｏｐｐｉｎｇ， 且将 ｗｅｂｓｉｔｅ１， ｗｅｂｓｉｔｅ２， …， ｗｅｂｓｉｔｅ６ 简记为 １， ２， …， ６，则表 １ 中的概念格如图 １ 所示，图 １ 可以直 观反 映 信 息 在 不 同 层 次 上 的 聚 类。 例 如， 概 念 ４５６，ａ３ ａ４ ａ５ ( ) 揭示 ｗｅｂｓｉｔｅ４、ｗｅｂｓｉｔｅ５ 和 ｗｅｂｓｉｔｅ６ 等 网站均含有主题 Ｍｉｌｉｔａｒｙ、Ｈｉｓｔｏｒｙ 和 Ｓｈｏｐｐｉｎｇ。 图 １ 从表 １ 导出的概念格结构 Ｆｉｇ．１ Ｔｈｅ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ ｄｅｒｉｖｅｄ ｆｒｏｍ ｔａｂｌｅ １ 定义 ４ 关于概念格的详细介绍请参阅文献 ［２９］。 ２ 集值信息系统和单值形式背景 一 个 集 值 信 息 系 统 一 般 由 四 元 组 (Ｕ，ＡＴ，Ｖ，Ｆ) 进行表示。 其中 Ｕ 是一个非空对象 集，称为论域；ＡＴ 是一个非空属性集；Ｖ ＝ ∪ｍ∈ＡＴ Ｖｍ ， 其中 Ｖｍ 是属性 ｍ 的值域；Ｆ ＝ ｆ { ｍ ：ｍ∈ＡＴ} ，其中 ｆｍ ：Ｕ→Ｐ Ｖｍ ( ) 。 一个典型的集值信息系统如表 ２。 表 ２ 一个典型的集值信息系统 Ｔａｂｌｅ ２ Ａ ｔｙｐｉｃａｌ ｓｅｔ⁃ｖａｌｕｅｄ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍ ａ ｂ ｃ ｄ ｅ ｕ１ ｖ１ ｖ１ ｖ１ ｖ１ ｖ１ ， ｖ３ ｕ２ ｖ１ ｖ１ ｖ１ ｖ１ ｖ１ ， ｖ３ ｕ３ ｖ１ ， ｖ２ ｖ１ ｖ１ ， ｖ２ ｖ２ ｖ２ ｕ４ ｖ１ ， ｖ２ ｖ１ ｖ１ ， ｖ２ ｖ２ ｖ２ ｕ５ ｖ２ ， ｖ３ ｖ１ ， ｖ２ ｖ２ ｖ１ ｖ１ ， ｖ２ ｕ６ ｖ２ ， ｖ３ ｖ１ ， ｖ２ ｖ２ ｖ１ ｖ１ ， ｖ２ ｕ７ ｖ３ ｖ２ ｖ２ ｖ１ ， ｖ２ ｖ３ ｕ８ ｖ３ ｖ２ ｖ２ ｖ１ ， ｖ２ ｖ３ 单值背景中的经典算子往往并不适用于多值的 信息系统。 即若采用定义 １ 中的算子，必须将信息 系统转化为单值形式背景。 由此，针对集值信息系 统，本文采用了如下转化策略。 定义 ３ 设(Ｕ，ＡＴ，Ｖ，Ｆ) 是一个集值信息系统， 称(Ｕ×Ｕ，ＡＴ，Ｊ) 是(Ｕ，ＡＴ，Ｖ，Ｆ) 的衍生形式背景，其 中 Ｊ 被描述为：对于任意(ｘ，ｙ) ∈Ｕ ２ ，ｍ∈ＡＴ，有 ( (ｘ，ｙ) ，ｍ) ∈ ＪＳ⇔ｆ(ｘ，ｍ) ∩ ｆ(ｙ，ｍ) ≠ ⌀ 由于衍生背景不再保留原信息系统中属性值自 身的信息，仅体现相同属性下不同对象之间的关系， 因而在形式上较原信息系统更加简单明了。 一个由 表 ２ 所示集值信息系统衍生的形式背景如表 ３。 表 ３ 一个衍生形式背景 Ｔａｂｌｅ ３ Ａ ｄｅｒｉｖａｔｉｖｅ ｆｏｒｍａｌ ｃｏｎｔｅｘｔ ａ ｂ ｃ ｄ ｅ （ｕ１ ， ｕ１ ） × × × × × （ｕ１ ， ｕ２ ） × × × × × （ｕ１ ， ｕ３ ） × × × （ｕ１ ，ｕ４ ） × × × （ｕ１ ，ｕ５ ） × × × （ｕ１ ， ｕ６ ） × × × ︙ ︙ ︙ ︙ ︙ ︙ （ｕ８ ， ｕ３ ） × × （ｕ８ ， ｕ４ ） × × （ｕ８ ， ｕ５ ） × × × × （ｕ８ ， ｕ６ ） × × × × （ｕ８ ， ｕ７ ） × × × × × （ｕ８ ， ｕ８ ） × × × × × ３ 集值信息系统中的代数结构和粒 化模型 概念格是一类重要的格代数结构，其在形式概 念分析理论中扮演了重要的角色。 据此，本文尝试 基于形式概念分析理论重点探讨集值信息系统中的 格代数结构、信息粒化等问题。 其中，本文提到的粒 化模型是基于定义 ３ 中的相容关系构造的。 定义 ４ ［２３］ 设(Ｕ，ＡＴ，Ｖ，Ｆ) 是一个集值信息系 统，对于任意 Ｂ⊆ＡＴ，论域 Ｕ 中的相容关系定义为 ＲＢ ＝ （ｘ，ｙ） ∈Ｕ ２ { ｜ ∀ｍ ∈Ｂ， ｆ（ｘ，ｍ） ∩ｆ（ｙ，ｍ） ≠⌀} 定理 １ 设(Ｕ×Ｕ，ＡＴ，Ｊ) 是(Ｕ，ＡＴ，Ｖ，Ｆ) 的衍生 背景，对于任意 Ｂ⊆ＡＴ，有 Ｂ ∗ ＝ＲＢ 。 证明 由定义 １、定义 ２ 和定义 ３ 即得，证毕。 定义 ５ 设 Ｒ 是论域 Ｕ 中的一个相容关系， 第 ３ 期 康向平，等：一种基于概念格的集值信息系统中的知识获取方法 ·２８９·
.290 智能系统学报 第11卷 HCU。若HXHCR,且不存在N×NCR满足HxHC (123456.a,) NxN,称H是一个极大相容类。U中所有极大相容 类组成的集合记为U/R。设R,和R,是U中的相 12345,a,a) .(23456.a,a, 容关系，对于任意X∈U/R,若存在Y∈U/R2且满 足XCY,则称U/R2相对于U/R,是一种更粗的粒 123a,a,a) (2345.a,4,a,) 化结果，记为U/R,CU/R2。 (456.a,a4) 引理2在定义4中，有下述结论成立： (23.a,aa,0, (45.a,a,aa) 1)若R,和R,是论域U中的相容关系，则R,C R,+U/R CU/R,; (d,aaaaa 2)在(U,AT,V,F)中，设B,DCAT,则BCD曰 图2从表4导出的概念格结构 RpERBo Fig.2 A concept lattice derived from table 4 定义6若R是论域U中的一个相容关系，则 生背景，映射+：v(L)→P(AT)被描述为 称(U,U,R)是由R决定的中间背景。 C=(B(C))°={m∈AT1((x,y),m)∈J, 定理2在上述背景(U,U,R)中，有下述结论 H(x,y)∈B(C)} 成立： 映射+：P(AT)→w(L)被描述为 R=U{X×XIX∈U/R} B*=a(B)={XI(X,X)∈B(U,U,B·)} X∈U/R台(X,X)∈B(U,U,R) 式中BCAT,C∈v(L)。若C=B且B=C,则称 证明由定义1和定义4即得，证毕。 (C,B)是(U,AT,V,F)中的相容概念。对于任意相 在表2中，表4是由R决定的中间背景，相应 容概念(C,B,)和(C2,B2),它们之间的偏序关系 的概念格如图2所示。显然，依据定理2，可以判定 “≤”定义为 {山1,42，山5，u6}、u1,2,山1,4g}、{u3,u4}均是U/RB (C1,B1)≤(C2,B2)台C1≤C2台B2CB1 中的极大相容类。在图2中，“u,”简化表示为“”。 偏序集(B(U,AT,V,F),≤)是一个完备格，其 表4一个中间背景 中B(U,AT,V,F)是由所有相容概念构成的集合。 Table 4 A intermediate context 该结论与经典概念格中的相关结论类似，具体证明 4344u364, g 详见文献[29]，在此不再详述。事实上，依据上述 定义，对于任意覆盖U/R,有 (U/R)+=R·={m∈ATI(x,y),m)∈J, H(x,y)∈R} 43 对于任意属性子集BCAT,有 B*=a(Rg)={XI (X,X)E B(U,U,Rg))=U/Rg us 定理3设(C,B)是一个相容概念，则C=U/Rs。 证明由于(C,B)是一个相容概念，所以由定 4 义7即得B*=C。又由于B*=U/Rg,故C=U/RB成 立，证毕。 依据定理2，本文在集值信息系统中进一步定 定理4在上述定义中，设R,R,和R2是论域 义如下α和B映射。 U中的相容关系，B,DSAT。有下述结论成立： 定义7设v(R)和v(L)分别是由论域U中所 1)U/R CU/R,=(U/R2)C(U/R)* 有相容关系和覆盖组成的集合。映射a:v(R)→v 2)BCD→D+CB (L)定义为 3)U/RC(U/R):BCB a(R)=(XI (X,X)E B(U,U,R)) 4)(U/R)+=(U/R)+:B*=B+ 映射B:v(L)→w(R)定义为 B(C)=U{X×XIX∈C} 证明1)当U/R,CU/R2时，有B(U/R,)CB 式中R∈v(R)和C∈v(L)。 (U/R2),进而由定义7即得结论成立。 定义8设(U×U,AT,J)是(U,AT,V,F)的衍 2)由于BCD→R,CRB→U/R,EU/RB→D*E
Ｈ⊆Ｕ。 若 Ｈ×Ｈ⊆Ｒ，且不存在 Ｎ×Ｎ⊆Ｒ满足 Ｈ×Ｈ⊂ Ｎ×Ｎ，称 Ｈ 是一个极大相容类。 Ｕ 中所有极大相容 类组成的集合记为 Ｕ／ Ｒ。 设 Ｒ１ 和 Ｒ２ 是 Ｕ 中的相 容关系，对于任意 Ｘ∈Ｕ／ Ｒ１ ，若存在 Ｙ∈Ｕ／ Ｒ２ 且满 足 Ｘ⊆Ｙ，则称 Ｕ／ Ｒ２ 相对于 Ｕ／ Ｒ１ 是一种更粗的粒 化结果，记为 Ｕ／ Ｒ１⊆Ｕ／ Ｒ２ 。 引理 ２ 在定义 ４ 中，有下述结论成立： １）若 Ｒ１ 和 Ｒ２ 是论域 Ｕ 中的相容关系，则 Ｒ１⊆ Ｒ２⇔Ｕ／ Ｒ１⊆Ｕ／ Ｒ２ ； ２）在(Ｕ，ＡＴ，Ｖ，Ｆ) 中，设 Ｂ，Ｄ⊆ＡＴ，则 Ｂ⊆Ｄ⇒ ＲＤ⊆ＲＢ 。 定义 ６ 若 Ｒ 是论域 Ｕ 中的一个相容关系，则 称(Ｕ，Ｕ，Ｒ) 是由 Ｒ 决定的中间背景。 定理 ２ 在上述背景 (Ｕ，Ｕ，Ｒ) 中，有下述结论 成立： Ｒ ＝∪ {Ｘ × Ｘ ｜ Ｘ ∈ Ｕ／ Ｒ} Ｘ ∈ Ｕ／ Ｒ⇔(Ｘ，Ｘ) ∈ Ｂ(Ｕ，Ｕ，Ｒ) 证明 由定义 １ 和定义 ４ 即得，证毕。 在表 ２ 中，表 ４ 是由 Ｒ｛ｄ，ｅ｝ 决定的中间背景，相应 的概念格如图 ２ 所示。 显然，依据定理 ２，可以判定 ｛ｕ１， ｕ２， ｕ５， ｕ６｝、｛ｕ１， ｕ２， ｕ７， ｕ８｝、｛ｕ３， ｕ４｝均是 Ｕ／ ＲＢ 中的极大相容类。 在图 ２ 中，“ｕｉ”简化表示为“ｉ”。 表 ４ 一个中间背景 Ｔａｂｌｅ ４ Ａ ｉｎｔｅｒｍｅｄｉａｔｅ ｃｏｎｔｅｘｔ ｕ１ ｕ２ ｕ３ ｕ４ ｕ５ ｕ６ ｕ７ ｕ８ ｕ１ × × × × × × ｕ２ × × × × × × ｕ３ × × ｕ４ × × ｕ５ × × × × ｕ６ × × × × ｕ７ × × × × ｕ８ × × × × 依据定理 ２，本文在集值信息系统中进一步定 义如下 α 和 β 映射。 定义 ７ 设 ν(Ｒ) 和 ν (Ｌ) 分别是由论域 Ｕ 中所 有相容关系和覆盖组成的集合。 映射 α：ν (Ｒ) →ν (Ｌ) 定义为 α(Ｒ) ＝ {Ｘ ｜ (Ｘ，Ｘ) ∈ Ｂ(Ｕ，Ｕ，Ｒ) } 映射 β：ν(Ｌ) →ν(Ｒ) 定义为 β(Ｃ) ＝∪ {Ｘ × Ｘ ｜ Ｘ ∈ Ｃ} 式中 Ｒ∈ν(Ｒ) 和 Ｃ∈ν(Ｌ) 。 定义 ８ 设（Ｕ×Ｕ，ＡＴ，Ｊ） 是（Ｕ，ＡＴ，Ｖ，Ｆ） 的衍 图 ２ 从表 ４ 导出的概念格结构 Ｆｉｇ． ２ Ａ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ ｄｅｒｉｖｅｄ ｆｒｏｍ ｔａｂｌｅ ４ 生背景，映射＋：ν（Ｌ）→Ｐ（ＡＴ）被描述为 Ｃ ＋ ＝ （β（Ｃ）） ∗ ＝ {ｍ ∈ ＡＴ ｜ （（ｘ，ｙ）），ｍ） ∈ Ｊ， ∀（ｘ，ｙ） ∈ β（Ｃ）} 映射＋：Ｐ（ＡＴ）→ν（Ｌ）被描述为 Ｂ ＋ ＝ α Ｂ ∗ ( ) ＝ Ｘ ｜ （Ｘ，Ｘ） ∈ Ｂ Ｕ，Ｕ，Ｂ ∗ { ( ) } 式中 Ｂ⊆ＡＴ，Ｃ∈ν（ Ｌ）。 若 Ｃ ＋ ＝ Ｂ 且 Ｂ ＋ ＝ Ｃ，则称 （Ｃ，Ｂ）是（Ｕ，ＡＴ，Ｖ，Ｆ）中的相容概念。 对于任意相 容概念 Ｃ１ ，Ｂ１ ( ) 和 Ｃ２ ，Ｂ２ ( ) ，它们之间的偏序关系 “≤”定义为 Ｃ１ ，Ｂ１ ( ) ≤ Ｃ２ ，Ｂ２ ( ) ⇔Ｃ１ ⊆Ｃ２⇔Ｂ２ ⊆ Ｂ１ 偏序集 (Ｂ(Ｕ，ＡＴ，Ｖ，Ｆ) ，≤) 是一个完备格，其 中 Ｂ (Ｕ，ＡＴ，Ｖ，Ｆ) 是由所有相容概念构成的集合。 该结论与经典概念格中的相关结论类似，具体证明 详见文献［２９］，在此不再详述。 事实上，依据上述 定义，对于任意覆盖 Ｕ／ Ｒ，有 (Ｕ／ Ｒ) ＋ ＝ Ｒ ∗ ＝ {ｍ ∈ ＡＴ ｜ (（ｘ，ｙ），ｍ) ∈ Ｊ， ∀（ｘ，ｙ） ∈ Ｒ} 对于任意属性子集 Ｂ⊆ＡＴ，有 Ｂ ＋ ＝ α ＲＢ ( ) ＝ Ｘ ｜ （Ｘ，Ｘ） ∈ Ｂ Ｕ，Ｕ，ＲＢ { ( ) } ＝ Ｕ／ ＲＢ 定理 ３ 设（Ｃ，Ｂ）是一个相容概念，则 Ｃ＝Ｕ／ ＲＢ。 证明 由于(Ｃ，Ｂ) 是一个相容概念，所以由定 义 ７ 即得 Ｂ ＋ ＝Ｃ。 又由于 Ｂ ＋ ＝Ｕ／ ＲＢ ，故 Ｃ ＝ Ｕ／ ＲＢ 成 立，证毕。 定理 ４ 在上述定义中，设 Ｒ，Ｒ１ 和 Ｒ２ 是论域 Ｕ 中的相容关系，Ｂ，Ｄ⊆ＡＴ。 有下述结论成立： １）Ｕ／ Ｒ１⊆Ｕ／ Ｒ２⇒ Ｕ／ Ｒ２ ( ) ＋⊆ Ｕ／ Ｒ１ ( ) ＋ ２）Ｂ⊆Ｄ⇒Ｄ ＋⊆Ｂ ＋ ３）Ｕ／ Ｒ⊆(Ｕ／ Ｒ) ＋＋ ；Ｂ⊆Ｂ ＋＋ ４） (Ｕ／ Ｒ) ＋ ＝ (Ｕ／ Ｒ) ＋＋＋ ；Ｂ ＋ ＝Ｂ ＋＋＋ 证明 １） 当 Ｕ／ Ｒ１ ⊆Ｕ／ Ｒ２ 时，有 β Ｕ／ Ｒ１ ( ) ⊆β Ｕ／ Ｒ２ ( ) ，进而由定义 ７ 即得结论成立。 ２）由于 Ｂ⊆Ｄ⇒ＲＤ⊆ＲＢ⇒Ｕ／ ＲＤ⊆Ｕ／ ＲＢ⇒Ｄ ＋⊆ ·２９０· 智 能 系 统 学 报 第 １１ 卷
第3期 康向平，等：一种基于概念格的集值信息系统中的知识获取方法 ·291· B,故BCD曰DCB成立。 4 集值信息系统中的约简、核、依赖等 3)当(U/R)+=B时，有(U/R)=B*=U/RB成 知识的获取 立。又(U/R)+=B={m∈ATIRC{m}},故 m∈B台RC{m}·台RCRm,从而有RCRg。显然， 定理1约简、核、依赖等作为粗糙集研究的重 要组成部分，也是本文研究的重点。针对集值信息 此时由RCRB即得U/RCU/RB,进而U/RC 系统中的相关问题，本文给出一种基于定理6的求 (U/R)成立。由于 解方法。此节内容是通过借鉴文献[12]得到的。 B=(U/Rg)=BUm E (AT-B)I Rg Cm) 在S=(U,AT,V,F)中，设m∈BCAT,若RB≠ 故结论BCB成立。 Ra-m,称m是B中的必要属性；B中所有必要属性的 4)由上述结论可知U/RC(U/R)艹→ 集合称为B的核，记为Core(B);设CCBCAT,若C (U/R)艹(U/R),此外，又由结论3)即得 是满足Rg=Rc的最小属性子集，称C是B的一个 (U/R)+C(U/R))+=(U/R)艹，故(U/R)+= 约简；设B,DCAT,若R&RD,称B→D是一个 (U/R)艹成立；同理可证B*=B艹，证毕。 依赖。 定理5对于任意BCAT,(B*,B)是一个相 定理7设m∈BCAT,若满足下述条件： 容概念，且U/Rg是(B*,B+)的外延。 {L E Int(S)I(B-m)CL}≠{L∈Int(S)IBSL 证明由B+=B即得(B,B“)是一个相容概 定理4则m∈Core(B)成立。 念，进而由B*=U/Rg可知U/Rg是相容概念 证明假设m生Core(B)成立。有如下结论： (B*,B)的外延。证毕。 Rg-m=Ra→U/Ra-m=U/Rg台(B-m)+=B+ 进而由(B-m)艹=B艹即得 由上述定理可知，(B(U,AT,V,F),≤)可以将 所有覆盖的集合{U/ReIB二AT}以格的形式有机地 {L∈Int(S)I(B-m)*≤L}= 组织起来，由此，本文将其视为集值信息系统 {L∈Int(S)IB+CL} (U,AT,V,F)中的重要代数结构。 又(B-m)CL台(B-m)艹CL且BCL台B艹CL,故 定理6设nt(S)是S=(U,AT,V,F)中所有相 {L∈nt(S)I(B-m)CL={L∈Int(S)IBCL} 容概念内涵的集合，则对于任意B二AT,有 与条件相矛盾！所以m∈Core(B)成立，证毕。 B**=L C Int(S)I B CL 定理8设CCBCAT,若C是满足下述条件的 证明与参考文献[29]中有关结论的证明过 最小属性子集： 程相类似，在此不再详述。证毕。 {L∈Int(S)IBCL}={L∈Int(S)ICCL} 例如，基于定义7中的算子，可以从表3导出一 则C是B的一个约简。 个如图3的格结构，该结构即为表2所示集值信息 证明基于定理6，由上述条件即得B*=C+, 系统中的相容概念格。图3中的X,/X2/…/X,表示 进而有 覆盖{X1,X2,…,X},任意“u:”表简化表示为“”。 B+=C+台B*=C台U/RB=U/Rc台RB=Rc 又由于C是满足上述条件的B的最小属性子集，故 (12345678.d) C是B的一个约简，证毕。 (123456/5678,b) (1256783478,d 在表2中所示的集值信息系统中，当B={a,b, 1234/34578.c9(d356/34567 c,d}时，依据上述定理，并参照表5中的包含关系， (1234/3456/5678.g6c) (56456&6 (1256/1278/34.de) 我们不难发现{a,d}和{b,c,d}是B的约简， 45678.be (1234785678e0 Core(B)={d;而当B={a,b,c}时，{a}和{b,c}是 (12/3456/78.abce)234/5678,4bcd B的约简，Core(B)=☑。为便于表示，表5中的任 125634/78.be) 意属性子集{m1,m2,…,mn}简化为m1m2…mno (12/34/56/78.abcde) 定理9设B,DCAT,若满足条件： {L∈Int(S)IBSL}S{L∈Int(S)lDCL} 图3一个相容概念格 则B→D是一个依赖。 Fig.3 A tolerance concept lattice 证明由条件可知： n{L∈Int(S)IDCL}Cn{L∈nt(S)IBCL 进而由定理6即得DSB+。由于
Ｂ ＋ ，故 Ｂ⊆Ｄ⇒Ｄ ＋⊆Ｂ ＋成立。 ３）当(Ｕ／ Ｒ) ＋ ＝ Ｂ 时，有(Ｕ／ Ｒ) ＋＋ ＝ Ｂ ＋ ＝ Ｕ／ ＲＢ 成 立。 又 (Ｕ／ Ｒ) ＋ ＝ Ｂ ＝ ｍ ∈ ＡＴ ｜ Ｒ ⊆ {ｍ} ∗ { } ， 故 ｍ∈Ｂ⇔Ｒ⊆{ｍ} ∗ ⇔Ｒ⊆Ｒｍ ，从而有 Ｒ⊆ＲＢ 。 显然， 此时 由 Ｒ ⊆ ＲＢ 即 得 Ｕ／ Ｒ ⊆ Ｕ／ ＲＢ ， 进 而 Ｕ／ Ｒ ⊆ (Ｕ／ Ｒ) ＋＋成立。 由于 Ｂ ＋＋ ＝ Ｕ／ ＲＢ ( ) ＋ ＝ Ｂ ∪ ｍ ∈ (ＡＴ － Ｂ) ｜ ＲＢ ⊆{ｍ} ∗ { } 故结论 Ｂ⊆Ｂ ＋＋成立。 ４） 由 上 述 结 论 可 知 Ｕ／ Ｒ ⊆ (Ｕ／ Ｒ) ＋＋ ⇒ (Ｕ／ Ｒ) ＋＋＋⊆ (Ｕ／ Ｒ) ＋ ， 此 外， 又 由 结 论 ３ ） 即 得 (Ｕ／ Ｒ) ＋ ⊆ (Ｕ／ Ｒ) ＋ ( ) ＋＋ ＝ (Ｕ／ Ｒ) ＋＋＋ ， 故 (Ｕ／ Ｒ) ＋ ＝ (Ｕ／ Ｒ) ＋＋＋成立；同理可证 Ｂ ＋ ＝Ｂ ＋＋＋ ，证毕。 定理 ５ 对于任意 Ｂ⊆ＡＴ， Ｂ ＋ ，Ｂ ＋＋ ( ) 是一个相 容概念，且 Ｕ／ ＲＢ 是 Ｂ ＋ ，Ｂ ＋＋ ( ) 的外延。 证明 由 Ｂ ＋＋＋ ＝Ｂ ＋即得 Ｂ ＋ ，Ｂ ＋＋ ( ) 是一个相容概 念，进 而 由 Ｂ ＋ ＝ Ｕ／ ＲＢ 可 知 Ｕ／ ＲＢ 是 相 容 概 念 Ｂ ＋ ，Ｂ ＋＋ ( ) 的外延。 证毕。 由上述定理可知， (Ｂ(Ｕ，ＡＴ，Ｖ，Ｆ) ，≤) 可以将 所有覆盖的集合｛Ｕ／ ＲＢ ｜ Ｂ⊆ＡＴ｝以格的形式有机地 组织 起 来， 由 此， 本 文 将 其 视 为 集 值 信 息 系 统 (Ｕ，ＡＴ，Ｖ，Ｆ) 中的重要代数结构。 定理 ６ 设 Ｉｎｔ(Ｓ) 是 Ｓ ＝ (Ｕ，ＡＴ，Ｖ，Ｆ) 中所有相 容概念内涵的集合，则对于任意 Ｂ⊆ＡＴ，有 Ｂ ＋ ＋ ＝ ｛Ｌ ⊆ Ｉｎｔ(Ｓ) ｜ Ｂ ⊆ Ｌ｝ 证明 与参考文献［２９］中有关结论的证明过 程相类似，在此不再详述。 证毕。 例如，基于定义 ７ 中的算子，可以从表 ３ 导出一 个如图 ３ 的格结构，该结构即为表 ２ 所示集值信息 系统中的相容概念格。 图 ３ 中的 Ｘ１ ／ Ｘ２ ／ …／ Ｘｌ 表示 覆盖｛Ｘ１ ，Ｘ２ ，…，Ｘｌ｝，任意“ｕｉ”表简化表示为“ｉ”。 图 ３ 一个相容概念格 Ｆｉｇ．３ Ａ ｔｏｌｅｒａｎｃｅ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ ４ 集值信息系统中的约简、核、依赖等 知识的获取 定理 １ 约简、核、依赖等作为粗糙集研究的重 要组成部分，也是本文研究的重点。 针对集值信息 系统中的相关问题，本文给出一种基于定理 ６ 的求 解方法。 此节内容是通过借鉴文献［１２］得到的。 在 Ｓ ＝ (Ｕ，ＡＴ，Ｖ，Ｆ) 中，设 ｍ∈Ｂ⊆ＡＴ，若 ＲＢ ≠ ＲＢ－ｍ ，称 ｍ 是 Ｂ 中的必要属性；Ｂ 中所有必要属性的 集合称为 Ｂ 的核，记为 Ｃｏｒｅ (Ｂ) ；设 Ｃ⊆Ｂ⊆ＡＴ，若 Ｃ 是满足 ＲＢ ＝ ＲＣ 的最小属性子集，称 Ｃ 是 Ｂ 的一个 约简；设 Ｂ，Ｄ⊆ＡＴ，若 ＲＢ ⊆ＲＤ，称 Ｂ→Ｄ 是一个 依赖。 定理 ７ 设 ｍ∈Ｂ⊆ＡＴ，若满足下述条件： {Ｌ ∈ Ｉｎｔ(Ｓ) ｜ （Ｂ － ｍ） ⊆ Ｌ} ≠ {Ｌ ∈ Ｉｎｔ(Ｓ) ｜ Ｂ ⊆ Ｌ} 定理 ４ 则 ｍ∈Ｃｏｒｅ (Ｂ) 成立。 证明 假设 ｍ∉Ｃｏｒｅ (Ｂ) 成立。 有如下结论： ＲＢ－ｍ ＝ ＲＢ⇔Ｕ／ ＲＢ－ｍ ＝ Ｕ／ ＲＢ⇔ （Ｂ － ｍ） ＋ ＋ ＝ Ｂ ＋ ＋ 进而由（Ｂ－ｍ） ＋＋ ＝Ｂ ＋＋即得 Ｌ ∈ Ｉｎｔ(Ｓ) ｜ （Ｂ － ｍ） { ＋ ＋ ⊆ Ｌ} ＝ Ｌ ∈ Ｉｎｔ(Ｓ) ｜ Ｂ { ＋ ＋ ⊆ Ｌ} 又(Ｂ－ｍ) ⊆Ｌ⇔(Ｂ－ｍ) ＋＋⊆Ｌ 且 Ｂ⊆Ｌ⇔Ｂ ＋＋⊆Ｌ，故 {Ｌ ∈Ｉｎｔ(Ｓ) ｜ （Ｂ － ｍ） ⊆Ｌ} ＝ {Ｌ ∈Ｉｎｔ(Ｓ) ｜ Ｂ ⊆Ｌ} 与条件相矛盾！ 所以 ｍ∈Ｃｏｒｅ（Ｂ）成立，证毕。 定理 ８ 设 Ｃ⊆Ｂ⊆ＡＴ，若 Ｃ 是满足下述条件的 最小属性子集： {Ｌ ∈ Ｉｎｔ(Ｓ) ｜ Ｂ ⊆ Ｌ} ＝ {Ｌ ∈ Ｉｎｔ(Ｓ) ｜ Ｃ ⊆ Ｌ} 则 Ｃ 是 Ｂ 的一个约简。 证明 基于定理 ６，由上述条件即得 Ｂ ＋＋ ＝ Ｃ ＋＋ ， 进而有 Ｂ ＋ ＋ ＝ Ｃ ＋ ＋⇔Ｂ ＋ ＝ Ｃ ＋ ⇔Ｕ／ ＲＢ ＝ Ｕ／ ＲＣ⇔ＲＢ ＝ ＲＣ 又由于 Ｃ 是满足上述条件的 Ｂ 的最小属性子集，故 Ｃ 是 Ｂ 的一个约简，证毕。 在表 ２ 中所示的集值信息系统中，当 Ｂ ＝ ｛ａ，ｂ， ｃ，ｄ｝时，依据上述定理，并参照表 ５ 中的包含关系， 我们不 难 发 现 ｛ ａ， ｄ ｝ 和 ｛ ｂ， ｃ， ｄ ｝ 是 Ｂ 的 约 简， Ｃｏｒｅ（Ｂ）＝ ｛ｄ｝；而当 Ｂ ＝ ｛ａ，ｂ，ｃ｝时，｛ ａ｝和｛ ｂ，ｃ｝是 Ｂ 的约简，Ｃｏｒｅ（Ｂ） ＝ ⌀。 为便于表示，表 ５ 中的任 意属性子集｛ｍ１ ，ｍ２ ，…， ｍｎ ｝简化为 ｍ１ｍ２… ｍｎ 。 定理 ９ 设 Ｂ，Ｄ⊆ＡＴ，若满足条件： ｛Ｌ ∈ Ｉｎｔ(Ｓ) ｜ Ｂ ⊆ Ｌ｝ ⊆ ｛Ｌ ∈ Ｉｎｔ(Ｓ) ｜ Ｄ ⊆ Ｌ｝ 则 Ｂ→Ｄ 是一个依赖。 证明 由条件可知： ∩ ｛Ｌ ∈ Ｉｎｔ(Ｓ) ｜ Ｄ ⊆ Ｌ｝ ⊆∩ ｛Ｌ ∈ Ｉｎｔ(Ｓ) ｜ Ｂ ⊆ Ｌ｝ 进而由定理 ６ 即得 Ｄ ＋＋⊆Ｂ ＋＋ 。 由于 第 ３ 期 康向平，等：一种基于概念格的集值信息系统中的知识获取方法 ·２９１·
.292. 智能系统学报 第11卷 D+≤B*+台B*CD*曰U/RBCU/Ro台RE C RD D2CD1时，由B,→D1可以推导出B2→D2,即B2→D2 故B→D是一个依赖。证毕。 是相对冗余的。在表2中，去掉上述冗余依赖后，一 一个信息系统中往往包含着大量的冗余依赖，例 个规模较小的依赖集如表6。在表6中，m1m2…m。 如，当D二B时，B→D是绝对冗余的：当B,CB2且 表示集合{m1,m2,…,mn}。 表5一些属性子集与内涵之间的包含关系 Table 5 Inclusion relation between some attributes sets and intents 相容概念内涵 属性子集 0 b d bd be cd de abe bde abed abce abcde abed S S a C b C C c d C C ac C C ad be bd ed abe abd acd bed S S 0 ( CC 表6一个依赖集 Table 6 A dependency set 参考文献： a-abe ad-abed bed-abcd ae→abce [1]PAWLAK Z.Rough sets[J].International journal of com- puter information sciences,1982,11(5):341-356. ade→abcde cde→abcde ce→abce bc-*abc [2]PAWLAK Z.Rough sets:theoretical aspects of reasoning a- bout data[M].Dordrecht:Kluwer Academic Publishers, 5 结束语 1991. [3]王国胤，张清华，胡军.粒计算研究综述[J].智能系统 我们知道，二元关系是粗糙集的核心要素，而概 学报，2007,2(6)：8-26 念格本质上又是一种以二元关系为研究对象的数学 WANG Guoyin,ZHANG Qinghua,HU Jun.An overview of 工具，因此将概念格融入到粗糙集研究中，必将有助 granular computing[J].CAAI transactions on intelligent sys- 于拓展粗糙集的分析能力。本文尝试将概念格中的 tems,2007,2(6):8-26. 概念思维、格代数结构、伽罗瓦连接等引入到集值信 [4]王国胤，姚一豫，于洪.粗糙集理论及应用研究综述[J刀 息系统中，重点探讨了基于相容关系的粒化模型和 计算机学报，2009,32(7)：1229-1246. WANG Guoyin,YAO Yiyu,YU Hong.A survey on rough 集值系统中的格代数结构，该代数结构可以将论域 set theory and applications[J].Chinese journal of comput- 中的所有覆盖以格的形式有机结织起来。此外，本 es,2009,32(7):1229-1246. 文还探讨了集值信息系统中的约简、核等问题。理[5]伞治，叶玉玲.粗糙集理论及其在智能系统中的应用 论推理和实例验证揭示了本文结论的合理性和有效 [J].智能系统学报，2007,4(2)：40-47. 性。本文从概念格视角提出了集值信息系统中的知 SAN Ye,YE Yuling.Rough set theory and its application in the intelligent systems[J].CAAI transactions on intelligent 识获取方法，有助于人们深入理解粗糙集理论，也有 systems,.2007,4(2):40-47. 助于揭示两种理论之间的紧密联系。相关研究内容 [6]WILLE R.Restructuring lattice theory:an approach based 仍将是我们下一阶段的研究重点。 on hierarchies of concepts[M]//RIVAL I.Ordered Sets
Ｄ ＋ ＋ ⊆ Ｂ ＋ ＋⇔Ｂ ＋⊆ － Ｄ ＋ ⇔Ｕ／ ＲＢ ⊆ － Ｕ／ ＲＤ⇔ＲＢ ⊆ ＲＤ 故 Ｂ→Ｄ 是一个依赖。 证毕。 一个信息系统中往往包含着大量的冗余依赖，例 如，当 Ｄ⊆Ｂ 时，Ｂ→Ｄ 是绝对冗余的；当Ｂ１⊆Ｂ２ 且 Ｄ２⊆Ｄ１ 时，由 Ｂ１→Ｄ１ 可以推导出Ｂ２→Ｄ２ ，即Ｂ２→Ｄ２ 是相对冗余的。 在表 ２ 中，去掉上述冗余依赖后，一 个规模较小的依赖集如表 ６。 在表 ６ 中，ｍ１ｍ２…ｍｎ 表示集合｛ｍ１ ，ｍ２ ，…，ｍｎ ｝。 表 ５ 一些属性子集与内涵之间的包含关系 Ｔａｂｌｅ ５ Ｉｎｃｌｕｓｉｏｎ ｒｅｌａｔｉｏｎ ｂｅｔｗｅｅｎ ｓｏｍｅ ａｔｔｒｉｂｕｔｅｓ ｓｅｔｓ ａｎｄ ｉｎｔｅｎｔｓ 属性子集 相容概念内涵 ⌀ ｂ ｃ ｄ ｅ ｂｄ ｂｅ ｃｄ ｄｅ ａｂｃ ｂｄｅ ａｂｃｄ ａｂｃｅ ａｂｃｄｅ ａｂｃｄ ⊆ ⊆ ａ ⊆ ⊆ ⊆ ⊆ ｂ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ｃ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ｄ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ａｂ ⊆ ⊆ ⊆ ⊆ ａｃ ⊆ ⊆ ⊆ ⊆ ａｄ ⊆ ⊆ ｂｃ ⊆ ⊆ ⊆ ⊆ ｂｄ ⊆ ⊆ ⊆ ⊆ ｃｄ ⊆ ⊆ ⊆ ａｂｃ ⊆ ⊆ ⊆ ⊆ ａｂｄ ⊆ ⊆ ａｃｄ ⊆ ⊆ ｂｃｄ ⊆ ⊆ ⌀ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ 表 ６ 一个依赖集 Ｔａｂｌｅ ６ Ａ ｄｅｐｅｎｄｅｎｃｙ ｓｅｔ ａ→ａｂｃ ａｄ→ａｂｃｄ ｂｃｄ→ａｂｃｄ ａｅ→ａｂｃｅ ａｄｅ→ａｂｃｄｅ ｃｄｅ→ａｂｃｄｅ ｃｅ→ａｂｃｅ ｂｃ→ａｂｃ ５ 结束语 我们知道，二元关系是粗糙集的核心要素，而概 念格本质上又是一种以二元关系为研究对象的数学 工具，因此将概念格融入到粗糙集研究中，必将有助 于拓展粗糙集的分析能力。 本文尝试将概念格中的 概念思维、格代数结构、伽罗瓦连接等引入到集值信 息系统中，重点探讨了基于相容关系的粒化模型和 集值系统中的格代数结构，该代数结构可以将论域 中的所有覆盖以格的形式有机结织起来。 此外，本 文还探讨了集值信息系统中的约简、核等问题。 理 论推理和实例验证揭示了本文结论的合理性和有效 性。 本文从概念格视角提出了集值信息系统中的知 识获取方法，有助于人们深入理解粗糙集理论，也有 助于揭示两种理论之间的紧密联系。 相关研究内容 仍将是我们下一阶段的研究重点。 参考文献： ［１］ＰＡＷＬＡＫ Ｚ． Ｒｏｕｇｈ ｓｅｔｓ［ Ｊ］． Ｉｎｔｅｒｎａｔｉｏｎａｌ ｊｏｕｒｎａｌ ｏｆ ｃｏｍ⁃ ｐｕｔｅｒ ＆ ｉｎｆｏｒｍａｔｉｏｎ ｓｃｉｅｎｃｅｓ， １９８２， １１（５）： ３４１⁃３５６． ［２］ＰＡＷＬＡＫ Ｚ． Ｒｏｕｇｈ ｓｅｔｓ： ｔｈｅｏｒｅｔｉｃａｌ ａｓｐｅｃｔｓ ｏｆ ｒｅａｓｏｎｉｎｇ ａ⁃ ｂｏｕｔ ｄａｔａ ［ Ｍ］． Ｄｏｒｄｒｅｃｈｔ： Ｋｌｕｗｅｒ Ａｃａｄｅｍｉｃ Ｐｕｂｌｉｓｈｅｒｓ， １９９１． ［３］王国胤， 张清华， 胡军． 粒计算研究综述［ Ｊ］． 智能系统 学报， ２００７， ２（６）： ８⁃２６． ＷＡＮＧ Ｇｕｏｙｉｎ， ＺＨＡＮＧ Ｑｉｎｇｈｕａ， ＨＵ Ｊｕｎ． Ａｎ ｏｖｅｒｖｉｅｗ ｏｆ ｇｒａｎｕｌａｒ ｃｏｍｐｕｔｉｎｇ［Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓ⁃ ｔｅｍｓ， ２００７， ２（６）： ８⁃２６． ［４］王国胤， 姚一豫， 于洪． 粗糙集理论及应用研究综述［Ｊ］． 计算机学报， ２００９， ３２（７）： １２２９⁃１２４６． ＷＡＮＧ Ｇｕｏｙｉｎ， ＹＡＯ Ｙｉｙｕ， ＹＵ Ｈｏｎｇ． Ａ ｓｕｒｖｅｙ ｏｎ ｒｏｕｇｈ ｓｅｔ ｔｈｅｏｒｙ ａｎｄ ａｐｐｌｉｃａｔｉｏｎｓ［ Ｊ］． Ｃｈｉｎｅｓｅ ｊｏｕｒｎａｌ ｏｆ ｃｏｍｐｕｔ⁃ ｅｒｓ， ２００９， ３２（７）： １２２９⁃１２４６． ［５］伞冶， 叶玉玲． 粗糙集理论及其在智能系统中的应用 ［Ｊ］． 智能系统学报， ２００７， ４（２）： ４０⁃４７． ＳＡＮ Ｙｅ， ＹＥ Ｙｕｌｉｎｇ． Ｒｏｕｇｈ ｓｅｔ ｔｈｅｏｒｙ ａｎｄ ｉｔｓ ａｐｐｌｉｃａｔｉｏｎ ｉｎ ｔｈｅ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ［ Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２００７， ４（２）： ４０⁃４７． ［６］ ＷＩＬＬＥ Ｒ． Ｒｅｓｔｒｕｃｔｕｒｉｎｇ ｌａｔｔｉｃｅ ｔｈｅｏｒｙ： ａｎ ａｐｐｒｏａｃｈ ｂａｓｅｄ ｏｎ ｈｉｅｒａｒｃｈｉｅｓ ｏｆ ｃｏｎｃｅｐｔｓ ［ Ｍ］ ／ ／ ＲＩＶＡＬ Ｉ． Ｏｒｄｅｒｅｄ Ｓｅｔｓ． ·２９２· 智 能 系 统 学 报 第 １１ 卷
第3期 康向平，等：一种基于概念格的集值信息系统中的知识获取方法 ·293· Netherlands:Springer,1982:445-470. [21]KRYSZKIEWICZ M.Rough set approach to incomplete in- [7]LI Jinhai,MEI Changlin,WANG Lidong,et al.On infer- formation systemsJ.Information sciences,1998,112(1/ ence rules in decision formal contexts[J].International jour- 2/3/4):39-49. nal of computational intelligence systems,2015,8(1): [22]KRYSZKIEWICZ M.Rules in incomplete information sys- 175-186. tems[J].Information sciences,1999,113(3/4):271- [8]LI Jinhai,MEI Changlin,WANG Junhong,et al.Rule-pre- 292. served object compression in formal decision contexts using [23]王国胤.Rough集理论在不完备信息系统中的扩充[J] concept lattices[J].Knowledge-based systems,2014,71: 计算机研究与发展.2002.39(10)：1238-1243. 435-445. WANG Guoyin.Extension of rough set under incomplete in- [9]QI Jianjun,QIAN Ting,WEI Ling.The connections be- formation systems[].Joumal of computer research and de- tween three-way and classical concept lattices[J].Knowl- velopment,.2002,39(10):1238-1243. edge-based systems,2016,91:143-151. [24]LEUNG Y,LI Deyu.Maximal consistent block technique [10]ZHAI Yanhui,LI Deyu,QU Kaishe.Decision implication for rule acquisition in incomplete information systems[J]. canonical basis:a logical perspective[].Journal of com- Information sciences,2003,153:85-106. puter and system sciences,2015,81(1):208-218. [25]ZHANG Wenxiu,MI Jusheng.Incomplete information sys- [11]张文修，姚一豫，梁怡.粗糙集与概念格[M].西安：西 tem and its optimal selections[J].Computers mathemat- 安交通大学出版社，2006. ics with applications,2004,48(5/6):691-698. [12]KANG Xianping,LI Deyu,WANG Suge,et al.Rough set [26]GUAN Yanyong,WANG Hongkai.Set-valued information model based on formal concept analysis[].Information systems[J].Information sciences,2006,176(17):2507- sciences,2013,222:611-625. 2525. [13]曲开社，翟岩慧，梁吉业，等.形式概念分析对粗糙集 [27]QIAN Yuhua,DANG Chuangyin,LIANG Jiye,et al.Set- 理论的表示及扩展[J].软件学报，2007,18(9)：2174- valued ordered information systems[J].Information sci- 2182. ences,2009,179(16):2809-2832. QU Kaishe,ZHAI Yanhui,LIANG Jiye,et al.Representa- [28]QIAN Y H,LIANG J Y,SONG P,et al.On dominance tion and extension of rough set theory based on formal con- relations in disjunctive set-valued ordered information sys- cept analysis[J].Journal of software,2007,18(9):2174- tems[J].International journal of information technology 2182. decision making,2010,9(1):9-33. [14]仇国芳，张志霞，张炜.基于粗糙集方法的概念格理论 29 GANTER B,WILLE R.Formal concept analysis:mathe- 研究综述[J].模糊系统与数学，2014,28(1)：168- matical foundations[M].Berlin Heidelberg:Springer-Ver- 177. lag,1999. QIU Guofang,ZHANG Zhixia,ZHANG Wei.A survey for 作者简介： study on concept lattice theory via rough set[J].Fuzzy sys- 康向平，男，1982年生，博土 tems and mathematics,2014,28(1):168-177. 后，主要研究方向为概念格、粗糙 [15]WAN Qing,WEI Ling.Approximate concepts acquisition 集、粒计算。 based on formal contexts[J].Knowledge-based systems, 2015,75:78-86. [16]KENT R E.Rough concept analysis:a synthesis of rough sets and formal concept analysis[J].Fundamenta informati- cae,1996,27(2-3):169-181. 苗夺谦，男，1964年生，教授，博 [17]CHEN Jinkun,LI Jinjin,LIN Yaojin,et al.Relations of 士生导师，中国人工智能学会理事、中 reduction between covering generalized rough sets and con- 国计算机学会杰出会员、中国自动化学 cept lattices[J].Information sciences,2015,304:16-27. 会智能自动化专委会委员、上海市计算 [18 ]LI Jinhai,REN Yue,MEI Changlin,et al.A comparative 机学会理事、上海市人工智能学会理 study of multigranulation rough sets and concept lattices via 事，主要研究方向为粗糙集、粒计算、 rule acquisition[J].Knowledge-based systems,2016,91: Wb智能、，数据挖掘和机器学习。主持完成国家级、省部级 152-164. 自然科学基金与科技攻关项目多项，参与完成973计划项 [19]SHAO Mingwen,LEUNG Y.Relations between granular 目、863计划项目、国家自然科学基金重大研究计划项目、上 reduct and dominance reduct in formal contexts [J]. 海市科委重大科技攻关项目等多项。作为项目组成员，曾 Knowledge-based systems,2014,65:1-11. 获国家教委科技进步三等奖、教育部科技进步一等奖、上海 [20]TAN Anhui,LI Jinjin,LIN Guoping.Connections between 市技术发明一等奖、重庆市自然科学一等奖等。发表学术论 covering-based rough sets and concept lattices[].Interna- 文260余篇，其中被SCI或EI检索150余篇.编著教材及著 tional journal of approximate reasoning,2015,56:43-58. 作12部，获得专利授权9项
Ｎｅｔｈｅｒｌａｎｄｓ： Ｓｐｒｉｎｇｅｒ， １９８２： ４４５⁃４７０． ［７］ ＬＩ Ｊｉｎｈａｉ， ＭＥＩ Ｃｈａｎｇｌｉｎ， ＷＡＮＧ Ｌｉｄｏｎｇ， ｅｔ ａｌ． Ｏｎ ｉｎｆｅｒ⁃ ｅｎｃｅ ｒｕｌｅｓ ｉｎ ｄｅｃｉｓｉｏｎ ｆｏｒｍａｌ ｃｏｎｔｅｘｔｓ［Ｊ］． Ｉｎｔｅｒｎａｔｉｏｎａｌ ｊｏｕｒ⁃ ｎａｌ ｏｆ ｃｏｍｐｕｔａｔｉｏｎａｌ ｉｎｔｅｌｌｉｇｅｎｃｅ ｓｙｓｔｅｍｓ， ２０１５， ８ （ １ ）： １７５⁃１８６． ［８］ＬＩ Ｊｉｎｈａｉ， ＭＥＩ Ｃｈａｎｇｌｉｎ， ＷＡＮＧ Ｊｕｎｈｏｎｇ， ｅｔ ａｌ． Ｒｕｌｅ⁃ｐｒｅ⁃ ｓｅｒｖｅｄ ｏｂｊｅｃｔ ｃｏｍｐｒｅｓｓｉｏｎ ｉｎ ｆｏｒｍａｌ ｄｅｃｉｓｉｏｎ ｃｏｎｔｅｘｔｓ ｕｓｉｎｇ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅｓ［ Ｊ］． Ｋｎｏｗｌｅｄｇｅ⁃ｂａｓｅｄ ｓｙｓｔｅｍｓ， ２０１４， ７１： ４３５⁃４４５． ［９］ ＱＩ Ｊｉａｎｊｕｎ， ＱＩＡＮ Ｔｉｎｇ， ＷＥＩ Ｌｉｎｇ． Ｔｈｅ ｃｏｎｎｅｃｔｉｏｎｓ ｂｅ⁃ ｔｗｅｅｎ ｔｈｒｅｅ⁃ｗａｙ ａｎｄ ｃｌａｓｓｉｃａｌ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅｓ ［ Ｊ］． Ｋｎｏｗｌ⁃ ｅｄｇｅ⁃ｂａｓｅｄ ｓｙｓｔｅｍｓ， ２０１６， ９１： １４３⁃１５１． ［１０］ＺＨＡＩ Ｙａｎｈｕｉ， ＬＩ Ｄｅｙｕ， ＱＵ Ｋａｉｓｈｅ． Ｄｅｃｉｓｉｏｎ ｉｍｐｌｉｃａｔｉｏｎ ｃａｎｏｎｉｃａｌ ｂａｓｉｓ： ａ ｌｏｇｉｃａｌ ｐｅｒｓｐｅｃｔｉｖｅ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｃｏｍ⁃ ｐｕｔｅｒ ａｎｄ ｓｙｓｔｅｍ ｓｃｉｅｎｃｅｓ， ２０１５， ８１（１）： ２０８⁃２１８． ［１１］张文修， 姚一豫， 梁怡． 粗糙集与概念格［Ｍ］． 西安： 西 安交通大学出版社， ２００６． ［１２］ＫＡＮＧ Ｘｉａｎｐｉｎｇ， ＬＩ Ｄｅｙｕ， ＷＡＮＧ Ｓｕｇｅ， ｅｔ ａｌ． Ｒｏｕｇｈ ｓｅｔ ｍｏｄｅｌ ｂａｓｅｄ ｏｎ ｆｏｒｍａｌ ｃｏｎｃｅｐｔ ａｎａｌｙｓｉｓ ［ Ｊ］． Ｉｎｆｏｒｍａｔｉｏｎ ｓｃｉｅｎｃｅｓ， ２０１３， ２２２： ６１１⁃６２５． ［１３］曲开社， 翟岩慧， 梁吉业， 等． 形式概念分析对粗糙集 理论的表示及扩展［Ｊ］． 软件学报， ２００７， １８（９）： ２１７４⁃ ２１８２． ＱＵ Ｋａｉｓｈｅ， ＺＨＡＩ Ｙａｎｈｕｉ， ＬＩＡＮＧ Ｊｉｙｅ， ｅｔ ａｌ． Ｒｅｐｒｅｓｅｎｔａ⁃ ｔｉｏｎ ａｎｄ ｅｘｔｅｎｓｉｏｎ ｏｆ ｒｏｕｇｈ ｓｅｔ ｔｈｅｏｒｙ ｂａｓｅｄ ｏｎ ｆｏｒｍａｌ ｃｏｎ⁃ ｃｅｐｔ ａｎａｌｙｓｉｓ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｓｏｆｔｗａｒｅ， ２００７， １８（９）： ２１７４⁃ ２１８２． ［１４］仇国芳， 张志霞， 张炜． 基于粗糙集方法的概念格理论 研究综述［ Ｊ］． 模糊系统与数学， ２０１４， ２８ （ １）： １６８⁃ １７７． ＱＩＵ Ｇｕｏｆａｎｇ， ＺＨＡＮＧ Ｚｈｉｘｉａ， ＺＨＡＮＧ Ｗｅｉ． Ａ ｓｕｒｖｅｙ ｆｏｒ ｓｔｕｄｙ ｏｎ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ ｔｈｅｏｒｙ ｖｉａ ｒｏｕｇｈ ｓｅｔ［Ｊ］． Ｆｕｚｚｙ ｓｙｓ⁃ ｔｅｍｓ ａｎｄ ｍａｔｈｅｍａｔｉｃｓ， ２０１４， ２８（１）： １６８⁃１７７． ［１５］ ＷＡＮ Ｑｉｎｇ， ＷＥＩ Ｌｉｎｇ． Ａｐｐｒｏｘｉｍａｔｅ ｃｏｎｃｅｐｔｓ ａｃｑｕｉｓｉｔｉｏｎ ｂａｓｅｄ ｏｎ ｆｏｒｍａｌ ｃｏｎｔｅｘｔｓ ［ Ｊ］． Ｋｎｏｗｌｅｄｇｅ⁃ｂａｓｅｄ ｓｙｓｔｅｍｓ， ２０１５， ７５： ７８⁃８６． ［１６］ＫＥＮＴ Ｒ Ｅ． Ｒｏｕｇｈ ｃｏｎｃｅｐｔ ａｎａｌｙｓｉｓ： ａ ｓｙｎｔｈｅｓｉｓ ｏｆ ｒｏｕｇｈ ｓｅｔｓ ａｎｄ ｆｏｒｍａｌ ｃｏｎｃｅｐｔ ａｎａｌｙｓｉｓ［Ｊ］． Ｆｕｎｄａｍｅｎｔａ ｉｎｆｏｒｍａｔｉ⁃ ｃａｅ， １９９６， ２７（２⁃３）： １６９⁃１８１． ［１７］ ＣＨＥＮ Ｊｉｎｋｕｎ， ＬＩ Ｊｉｎｊｉｎ， ＬＩＮ Ｙａｏｊｉｎ， ｅｔ ａｌ． Ｒｅｌａｔｉｏｎｓ ｏｆ ｒｅｄｕｃｔｉｏｎ ｂｅｔｗｅｅｎ ｃｏｖｅｒｉｎｇ ｇｅｎｅｒａｌｉｚｅｄ ｒｏｕｇｈ ｓｅｔｓ ａｎｄ ｃｏｎ⁃ ｃｅｐｔ ｌａｔｔｉｃｅｓ［Ｊ］． Ｉｎｆｏｒｍａｔｉｏｎ ｓｃｉｅｎｃｅｓ， ２０１５， ３０４： １６⁃２７． ［１８］ＬＩ Ｊｉｎｈａｉ， ＲＥＮ Ｙｕｅ， ＭＥＩ Ｃｈａｎｇｌｉｎ， ｅｔ ａｌ． Ａ ｃｏｍｐａｒａｔｉｖｅ ｓｔｕｄｙ ｏｆ ｍｕｌｔｉｇｒａｎｕｌａｔｉｏｎ ｒｏｕｇｈ ｓｅｔｓ ａｎｄ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅｓ ｖｉａ ｒｕｌｅ ａｃｑｕｉｓｉｔｉｏｎ［Ｊ］． Ｋｎｏｗｌｅｄｇｅ⁃ｂａｓｅｄ ｓｙｓｔｅｍｓ， ２０１６， ９１： １５２⁃１６４． ［１９］ ＳＨＡＯ Ｍｉｎｇｗｅｎ， ＬＥＵＮＧ Ｙ． Ｒｅｌａｔｉｏｎｓ ｂｅｔｗｅｅｎ ｇｒａｎｕｌａｒ ｒｅｄｕｃｔ ａｎｄ ｄｏｍｉｎａｎｃｅ ｒｅｄｕｃｔ ｉｎ ｆｏｒｍａｌ ｃｏｎｔｅｘｔｓ ［ Ｊ ］． Ｋｎｏｗｌｅｄｇｅ⁃ｂａｓｅｄ ｓｙｓｔｅｍｓ， ２０１４， ６５： １⁃１１． ［２０］ＴＡＮ Ａｎｈｕｉ， ＬＩ Ｊｉｎｊｉｎ， ＬＩＮ Ｇｕｏｐｉｎｇ． Ｃｏｎｎｅｃｔｉｏｎｓ ｂｅｔｗｅｅｎ ｃｏｖｅｒｉｎｇ⁃ｂａｓｅｄ ｒｏｕｇｈ ｓｅｔｓ ａｎｄ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅｓ［Ｊ］． Ｉｎｔｅｒｎａ⁃ ｔｉｏｎａｌ ｊｏｕｒｎａｌ ｏｆ ａｐｐｒｏｘｉｍａｔｅ ｒｅａｓｏｎｉｎｇ， ２０１５， ５６： ４３⁃５８． ［２１］ＫＲＹＳＺＫＩＥＷＩＣＺ Ｍ． Ｒｏｕｇｈ ｓｅｔ ａｐｐｒｏａｃｈ ｔｏ ｉｎｃｏｍｐｌｅｔｅ ｉｎ⁃ ｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍｓ［Ｊ］． Ｉｎｆｏｒｍａｔｉｏｎ ｓｃｉｅｎｃｅｓ， １９９８， １１２（１ ／ ２ ／ ３ ／ ４）： ３９⁃４９． ［２２］ＫＲＹＳＺＫＩＥＷＩＣＺ Ｍ． Ｒｕｌｅｓ ｉｎ ｉｎｃｏｍｐｌｅｔｅ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓ⁃ ｔｅｍｓ［ Ｊ］． Ｉｎｆｏｒｍａｔｉｏｎ ｓｃｉｅｎｃｅｓ， １９９９， １１３ （ ３ ／ ４）： ２７１⁃ ２９２． ［２３］王国胤． Ｒｏｕｇｈ 集理论在不完备信息系统中的扩充［ Ｊ］． 计算机研究与发展， ２００２， ３９（１０）： １２３８⁃１２４３． ＷＡＮＧ Ｇｕｏｙｉｎ． Ｅｘｔｅｎｓｉｏｎ ｏｆ ｒｏｕｇｈ ｓｅｔ ｕｎｄｅｒ ｉｎｃｏｍｐｌｅｔｅ ｉｎ⁃ ｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍｓ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｃｏｍｐｕｔｅｒ ｒｅｓｅａｒｃｈ ａｎｄ ｄｅ⁃ ｖｅｌｏｐｍｅｎｔ， ２００２， ３９（１０）： １２３８⁃１２４３． ［２４］ ＬＥＵＮＧ Ｙ， ＬＩ Ｄｅｙｕ． Ｍａｘｉｍａｌ ｃｏｎｓｉｓｔｅｎｔ ｂｌｏｃｋ ｔｅｃｈｎｉｑｕｅ ｆｏｒ ｒｕｌｅ ａｃｑｕｉｓｉｔｉｏｎ ｉｎ ｉｎｃｏｍｐｌｅｔｅ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍｓ［ Ｊ］． Ｉｎｆｏｒｍａｔｉｏｎ ｓｃｉｅｎｃｅｓ， ２００３， １５３： ８５⁃１０６． ［２５］ＺＨＡＮＧ Ｗｅｎｘｉｕ， ＭＩ Ｊｕｓｈｅｎｇ． Ｉｎｃｏｍｐｌｅｔｅ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓ⁃ ｔｅｍ ａｎｄ ｉｔｓ ｏｐｔｉｍａｌ ｓｅｌｅｃｔｉｏｎｓ［Ｊ］． Ｃｏｍｐｕｔｅｒｓ ＆ ｍａｔｈｅｍａｔ⁃ ｉｃｓ ｗｉｔｈ ａｐｐｌｉｃａｔｉｏｎｓ， ２００４， ４８（５ ／ ６）： ６９１⁃６９８． ［２６］ ＧＵＡＮ Ｙａｎｙｏｎｇ， ＷＡＮＧ Ｈｏｎｇｋａｉ． Ｓｅｔ⁃ｖａｌｕｅｄ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍｓ［Ｊ］． Ｉｎｆｏｒｍａｔｉｏｎ ｓｃｉｅｎｃｅｓ， ２００６， １７６（１７）： ２５０７⁃ ２５２５． ［２７］ＱＩＡＮ Ｙｕｈｕａ， ＤＡＮＧ Ｃｈｕａｎｇｙｉｎ， ＬＩＡＮＧ Ｊｉｙｅ， ｅｔ ａｌ． Ｓｅｔ⁃ ｖａｌｕｅｄ ｏｒｄｅｒｅｄ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍｓ ［ Ｊ］． Ｉｎｆｏｒｍａｔｉｏｎ ｓｃｉ⁃ ｅｎｃｅｓ， ２００９， １７９（１６）： ２８０９⁃２８３２． ［２８］ＱＩＡＮ Ｙ Ｈ， ＬＩＡＮＧ Ｊ Ｙ， ＳＯＮＧ Ｐ， ｅｔ ａｌ． Ｏｎ ｄｏｍｉｎａｎｃｅ ｒｅｌａｔｉｏｎｓ ｉｎ ｄｉｓｊｕｎｃｔｉｖｅ ｓｅｔ⁃ｖａｌｕｅｄ ｏｒｄｅｒｅｄ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓ⁃ ｔｅｍｓ［Ｊ］． Ｉｎｔｅｒｎａｔｉｏｎａｌ ｊｏｕｒｎａｌ ｏｆ ｉｎｆｏｒｍａｔｉｏｎ ｔｅｃｈｎｏｌｏｇｙ ＆ ｄｅｃｉｓｉｏｎ ｍａｋｉｎｇ， ２０１０， ９（１）： ９⁃３３． ［２９］ＧＡＮＴＥＲ Ｂ， ＷＩＬＬＥ Ｒ． Ｆｏｒｍａｌ ｃｏｎｃｅｐｔ ａｎａｌｙｓｉｓ： ｍａｔｈｅ⁃ ｍａｔｉｃａｌ ｆｏｕｎｄａｔｉｏｎｓ［Ｍ］． Ｂｅｒｌｉｎ Ｈｅｉｄｅｌｂｅｒｇ： Ｓｐｒｉｎｇｅｒ⁃Ｖｅｒ⁃ ｌａｇ， １９９９． 作者简介： 康向 平， 男， １９８２ 年 生， 博 士 后， 主 要 研 究 方 向 为 概 念 格、 粗 糙 集、粒计算。 苗夺谦， 男， １９６４ 年生， 教授， 博 士生导师，中国人工智能学会理事、中 国计算机学会杰出会员、中国自动化学 会智能自动化专委会委员、上海市计算 机学会理事、上海市人工智能学会理 事，主要研究方向为粗糙集、粒计算、 Ｗｅｂ 智能、数据挖掘和机器学习。 主持完成国家级、省部级 自然科学基金与科技攻关项目多项， 参与完成 ９７３ 计划项 目、８６３ 计划项目、国家自然科学基金重大研究计划项目、上 海市科委重大科技攻关项目等多项。 作为项目组成员， 曾 获国家教委科技进步三等奖、教育部科技进步一等奖、上海 市技术发明一等奖、重庆市自然科学一等奖等。 发表学术论 文 ２６０ 余篇， 其中被 ＳＣＩ 或 ＥＩ 检索 １５０ 余篇． 编著教材及著 作 １２ 部， 获得专利授权 ９ 项。 第 ３ 期 康向平，等：一种基于概念格的集值信息系统中的知识获取方法 ·２９３·