信息与计算科学毕业论文：形式背景组合运算与概念计算.doc

1、 本科毕业论文 （ 20 届） 形式背景组合运算与概念计算 所在学院 专业班级 信息与计算科学 学生姓名 学号 指导教师 职称 完成日期 年 月 I 摘要 形式概念分析是数据挖掘和信息处理的一种有效数学工具 , 备受广大科研工作者的关注 , 在众多实际领域都有广泛的应用 . 本文是在形 式概念分析理论框架下 , 对形式背景组合运算及其概念计算问题进行研究 . 首先回顾了形式概念分析的基本研究状况 , 复习相关的基本概念 . 论文创造性地给出各种形式背景的组合运算 , 对各种形式背景组合运算的性质进行了研究 . 之后 , 组合形式背景中的形式概念的生产问题进行了研究 , 给出各种形式背景下概念的

2、计算方法 . 关键词： 形式背景 ; 形式概念 ; 形式背景组合 ; 概念计算 II Abstract Formal Concept Analysis (FCA) is a king of effective mathematical tool for data mining and information processing, which have been paid much attention by many researchers, and it has many important applications on many practical domains. The study

3、of this thesis is faced on composition operations of formal contexts and corresponding formal concepts computation. First, basic research situation is reviewed, and some related notions for FCA are examined. The thesis proposes some new notions of composition formal contexts constructively. Subseque

4、ntly, the properties of composition formal contexts are discussed in detail. Finally, the computation of the formal concepts of composition formal contexts is investigated, and methods for the computations are given. Keywords: Formal context; Formal concept; Composition formal context; Concept compu

5、tation III 目录 中文摘要 .I 英文摘要 . .II 1 前言 错误 !未定义书签。 2 形式背景与概念格理论 . . .3 2.1 形式背景 . . .3 2.2 概念格 . . . .4 3 形式背景的组合运算 . . . .7 3.1 组合形式背景的构造 . . .7 3.2 组合形式背景的性质 . . .10 4 组合形式背景中的概念计算 . 12 4.1 子形式背景下的概念 . .12 4.2 补背景的概念计算 . .13 4.3 积形式背景的概念计算 . .14 4.4 和与差形式背景的概念计算 . .15 4.5 直和形式背景的概念计算 . .15 4.6 对称差形式

6、背景的概念计算 . .16 5 小结 . 17 参考文献 . 18 致 谢 . .18 1 1 前言 形式概念分析 , 是一种形式化数据表示和处理方法 . 自从德国的 Wille教授在 20世纪 80年代初提出了以来 , 在过去的二十几年里经过不断地实践与发展 , 其理论与方法日趋完善和成熟 . 发展成为聚类 、 数据分析 、 信息挖掘 、 知识发现、本体工程等的有力工具 , 在超过 200多项科学工程中得到应用 . 到今天已成为一个非常活跃又富有吸引力的研究领域 . 形式概念分析的方法和论题也在迅速扩大 , ICFCA(International Conference of Formal C

7、oncept Analysis)自 2003 年开始 , 每年举办一次 , 会上主要反映形式概念分析的理论基础及其实际应用的发展和拓宽领域的一些成就 , 并出版会议文集 . 国内早在 1995 年就有学者开始关注概念格的发展 , 相关文献主要收录在中国知网的中国学术期刊全文数据库 、 中国优秀博硕士学位论文全文数据库、中国重要会议论文全文数据库和计算机类的核心期刊中 , 在我国近两年以来一直保持在较高的发展水平之上 , 呈现出了高速发展的态势 . 概念格 1, 作为形式概念分析理论中的一种核心数据结构 , 其核心思想是采用形式概念分析方法 , 将知识的表达结构化 . 作为一个年轻并高速发展的领

8、域 , 越来越多的国内外学者开始从事或关注概念格的理论研究及其发展、应用 . 从 CNKI 的 1994 年到 2006 年对概念格的学术关注度来看其呈逐年上升趋势 , 尤其是近几年 , 上升趋势格外明显 . 概念格理论的研究主要集中在以下几个方面 : 1. 构建概念格 2, 3. 建格的过程实际上是概念聚类的过程 . 概念格的建造算法可分两类 :批处理算法和增量算法 . T. B. Ho. (1997)研究了基于概念格的概念聚类算法 , 并实现了一些学 习系统 . 安广伟 (2007)等提出基于 n 阶形式背景核的概念格同构建造出新的概念格 , 并给出了 n 阶形式背景核的基本算法 . 2.

9、 约简概念格 4, 5, 6, 7, 8. 约简概念格是形式概念知识表示中解决复杂性的重要途径 . 张文修等借助粗糙集约简理论研究了概念格约简理论与方法 4.王国俊等人对概念格的属性约简做了判定 5.胡春玉 (2006)利用相似关系研究模糊概念个的精确约简和近似约简 , 又利用变精度 概念格研究模糊概念格的约简 . 3. 规则提取 9. 概念格上提取的规则相对于其它分类器具有更好的分类效果 . Godin. R(1994)等在其提出的增量式建格算法基础上给出了由概念格来提取蕴含规则的算法 , Hu. K. Y. (1999)提出了一种在概念格上提取分类和关联规则的集成算法 . 绍明文 (200

10、6)等给出了协调决策形式背景与不协调决策背景规则的获取方法 . 2 4. 与粗糙集的关系 10, 11, 12, 13,. 概念格与粗糙集在研究背景与研究目标存在着一定的联系 . Kent(1996)提出粗糙 概念分析 , 提出了一种 在形式概念分析的框架下 , 更具一般性的新方法 Yao. Y. Y. (2004)基于粗糙集理论 , 构造了三种与形式概念相关而又不同的概念格 , 为深刻理解数据分析提供了一种新的途径 10. 张文修 (2006)等在文中重点分析了概念格与分划之间的关系 , 并证明两者是可以互相转换 . 5. 应用 14, 15. 概念格理论已被广泛应用于知识工程、数字图书馆、

11、信息检索、软件工程等领域 , 并在经济学等领域中开始发挥作用 . 在知识发现方面 , 有不少作者探讨过从格上提取规则的问题 . 也有作者直接 用格节点进行实例匹配而进行分类 (Ho, 1997). 在数字图书馆及文献检索方面 , Neuss 和 Kent (1999)使用概念格进行 Internet上文档元信息的自动分类和分析 . Kent 和 Bowman (1995)建造了基于概念格的用于数字图书馆的系统 Nebula 及相应接口 . 在导航能力方面 , Eklun 和 Martin (1998)展示了概念层次进行 Web 文档索引和导航的能力 . 在 软件工程方面 , Corbett 和

12、 Burrow (1996)提出使用概念格表示建筑早期设计软件支持环境 (SEED)中的状态图的表示 . Godin 和 Mineau 等人描述了使用概念格方法从现存软件系统中生成和检索摘要的方法 . 在经济学方面 , 汪丁丁提出 1998 年以来经济学和认知科学交界处的三个基本概念 , 它们来自代数学 “格论 ”, 其中之一为概念格 , “概念格 ”理论 , 作为认知科学的最新成果 , 对于知识的经济学研究极其重要 . Rudolf Wille 等在讲述了概念格的性质 . 孙舒杨等讲述了背景格的定义及其构造方法 , 并给出了背景格的若干性质以及完备性证明 13. 张晓东等利用 Galois

13、联络对概念格的基本性质进行 了深入的研究 . 但是 , 对于形式背景组合运算与概念计算研究尚未见到有关报道 . 在此基础之上 , 本文讨论 具有相同属性集和对象集的形式背景 , 通过对它们二元关系的组合构成的新的形式背景及其 所对应的概念格的性质进行研究 . 进一步扩充了概念格理论 , 对概念格理论研究与应用有着一定意义 . 3 2 形式背景与概念格理论 2.1 形式背景 形式背景 ( , , )UAI 是形式概念分析的基础 . 定义 2.11 称 ( , , )UAI 为一个形式背景 , 其中 1 ,., nU x x 为对象集 , 每个 ()ix i n称为一个对象 ; 1,. mA a

14、a 为属性集 , 每个 ja j m()称为一个属性 ; I 为 U 和 A 之间的二元关系 , I U A. 若 ,xa I(), 则说 x 具有属性 a , 记为 xIa . 本文中 , 用 表示 ,xa I(), 用 *表示 ,xa I(), 这样 , 形式背景就可以表示为只有 和*的表 格 . 例 2.1 设 ,UAI()是一 个有关动物的形式背景 , 其中对象集 U 老虎 , 鸽子 , 老鹰 , 山羊 , 鸵鸟 , 属性集 A 捕食的 , 会飞的 , 鸟类 , 哺乳类 , 这些由表格简要说明 . 下面的表描述了一些动物 , 它们具有以上提到过的属性 . 其中 *表示一个动物和对应属性

15、间不存在关系 , 表示一个动物和对应属性存在关系 . 例如表 2.1 中第一行中的 、 *、 *、 表示老虎具有 “捕食的 , 哺乳类 ”这两个属性 , 不具有 “会飞的 , 鸟类 ”这两个属 性 . 表 2.1 有关动物的背景 T 动物 捕食的 会飞的 鸟类 哺乳类 老虎 * * 鸽子 * * 老鹰 * 山羊 * * * 鸵鸟 * * * 定义 2.2 对于形式背景 ( , , )UAI , 在对象集 XU 和属性集 BA 上分别定义运算 : | , ,X a a A x X x Ia , | , ,B x x U x B xIa . 4 xU , 记 x 为 x ; aA , 记 a 为

16、a . 若 xU , x , xA , 且aA , a , aU , 则形式背景是正则的 . 定义 2.2 中 X 表示 X 中所有对象共同具有的属性的集合 ; B 表示共同具有 B 中所有属性的对象集合 . 2.2 概念格 定义 2.31 设 ,UAI()为一个形式背景 . 对于 XU , BA 如果 XB , 且XB , 则称 ,XB()是一个形式概念 , 简称概念 . 其中 , X 称为概念的外延 , B 称为概念的内涵 形式概念 ,XB()的外延 X 是具有属性集 B 的最大对象集 , 内涵 B 是对象集 X 所共有的最大属性集 . 近来 , 有工作者对形式概念进行了推广 6: 设 ,

17、UAI()是一个形式背景 , 记 xI y A xIy A | , Iy x U xIy U | . xI 表示对象 x 所具有的属性集 , Iy 表示属性 y 被具有的对象集 . 显然 xIy y xI x Iy . 推广 xI 到 U 的子集 X , Iy 到 A 的子集到子集 Y , 得 : xXXI xI, yYIY Iy. 形式背景 ,UAI()有以下基本性质 1: 1X , 2X , XU , 1B , 2B , BA , (1) 1 2 2 1X X X X , 1 2 2 1B B B B ; (2) XX , BB ; (3) XX , BB ; (4) X B B X ;

18、(5) 1 2 1 2X X X X () , 1 2 1 2B B B B () ; (6) 1 2 1 2X X X X () , 1 2 1 2B B B B () ; (7) ,XX ()和 ,BB ()都是概念 . 5 定义 2.41 若 11,XB(), 22,XB()是某个背景上的两个概念 , 而且 12XX (等价于21BB ), 则我们称 11,XB()是 22,XB()的子概念 , 22,XB()是 11,XB()的超概念 , 并记作1 1 2 2, ( , )X B X B() . 关系 称为是概念的序 , 简称 “序 ”. ,UAI()的所有概念用这种序组成的集合用 ,

19、L U AI（ ） 表示 , 称它为背景 ,UAI()上的概念格 . 例 2.2 形式背景同例 2.1, 为表述简洁 , 我们将 U 中的 “老虎 ”, “鸽子 ”, “老鹰 ”, “山羊 ”和“鸵鸟 ”分别用 1、 2、 3、 4 和 5 来记 , 则 5,4,3,2,1U . 将 A 的属性 “捕食的 ”、 “会飞的 ” “鸟类 ”和 “哺乳类 ”分别用 a、 b、 c和 d 来记 , 则 , dcbaA . 该背景一共有 7 个概念 : 1,ad(), 3,abc(), 23,bc(), 13,a(), 14,d(), ,U(), ,A(). 它们构成的概念格的 Hasse图由图2.1

20、给出 . 图 2.1 动物的形式背景 T 的概念格 定 理 2.21 概念格 ( , , )LU AI 是一个完 备 格 , 其上确界和下确界分别是 , ( , ( ) )t t t ttT t T t TX B X B () , , ( ( ) , )t t t ttT t T t TX B X B () , 其中 , T 为索引集 . 定义 2.55 设 11( , , )LU A I 和 22( , , )LU A I 是两个概念格 , 如果对于任意( , )XB 22( , , )LU A I , 总存在 11( , ) ( , , )X B L U A I , 使得 XX , 则称

21、11( , , )LU A I 细于 22( , , )LU A I , 记作 1 1 2 2( , , ) ( , , )L U A I L U A I . 6 如果 1 1 2 2( , , ) ( , , )L U A I L U A I 且 2 2 1 1( , , ) ( , , )L U A I L U A I , 那么称两个概念格同构 , 记作 1 1 2 2( , , ) ( , , )L U A I L U A I . 定义 2.61 一个背景 ( , , )UAI 称为净化的 , 如果任何两个满足 xy ( ,xy U )都有xy , 而且对偶地任意两个满足 ab ( ,ab A )都有 ab .