第1章 概念背景图的数学基础
　　概念背景图（concept context graph，CCG）中的“概念”一词，借鉴人类自然语言中的“概念”，包含外延和内涵。概念的内涵是指一个概念反映的事物的本质属性的总和，即概念的内容。例如：“商品是用来交换的劳动产品”，其中，“用来交换的劳动产品”就是概念“商品”的内涵。概念的外延是指这个概念所反映的事物对象（人、地、事、物）的范围，即具有概念所反映的属性的事物或对象。内涵和外延之间存在着某种特殊的联系，这种联系表明，内涵所描述的属性是外延所有对象共同具有的，外延包含的所有对象也只能具有其内涵描述的属性。内涵对外延来讲是封闭的，外延对内涵来讲也是封闭的。一些概念之间存在着泛化、特化、同义、近义等关系。形式概念分析利用数学中的序、格将自然语言中的概念进行了形式化的定义，并对概念之间的这些关系进行讨论。本章重点讨论一些相关的序、格、概念格等内容。
　　1.1 偏序
　　一般来讲两个具有固定秩序的客体x和y组成一个序偶。序偶是有序二元组，与集合不同。对于集合而言。但对于序偶和，它们是不相等的。比如集合与集合是相同的，包括2和3两个元素，而直角坐标系上的点序偶和分别表示不同的点。
　　定义1.1（序偶相等）序偶和相等，即，当且仅当且。
　　在许多研究中，序偶常常来源于两个不同的集合或领域，用来研究两类不同事物之间的关系。任意给定两个集合，可以定义一种序偶。建立在一定应用背景下的序偶，其中的两个集合具有一定的联系，那么这样的序偶就有特定的意义。没有建立在一定应用背景下的序偶，是没有实际意义的。
　　定义1.2（笛卡儿积）令X与Y是任意两个集合，对于序偶，x是X中的元素，y是Y中的元素。所有这样的序偶的集合，称为集合X和Y的笛卡儿积或直积，记作，定义式为
　　（1.1）
　　例1.1 设X是三个网页的集合，包含三个不同的URL，即，Y是三个网页共有关键词的集合，包括人工智能（artificial intelligence，AI）和深度学习（deep learning，DL）。
　　定义1.3（二元关系）[1] 令X与Y是任意两个集合，集合，称R是X，Y的二元关系；若序偶，则记作。若，则说R是X上的二元关系。常用表示的逆关系，与是等价的。
　　例1.2
　　R1，R2，R3，R4，R5，R6都是集合，上的二元关系。
　　定义1.4（偏序关系）[1] 集合X上的二元关系R称为一个偏序关系，如果满足：
　　自反性（对任意，有）；
　　反对称性（对任意，若且，那么一定不存在）；
　　传递性（对任意，若且）。
　　在这里必须说明几个问题：
　　（1）关于偏序关系反对称性，对任意，若且，则。
　　（2）常常把偏序关系表示为，称为小于等于关系，一个集合X上的偏序记为。
　　①定义1.4中自反性可以描述为对任意，有；
　　②反对称性可以描述为对任意，若且，那么一定不存在；
　　③传递性可以描述为对任意，若且。
　　（3）R是X上的偏序关系，若对于，必有或，则R称为X上的全序。
　　①其反自反性可以描述为对任意，有；
　　②反对称性可以描述为对任意，若且，那么；
　　③传递性可以描述为对任意，若且。
　　例1.3 设，其是对任意包含的人物群体的包含关系，则为一个偏序集，也是一种非严格偏序。
　　设；X是Y的幂集合，其是对任意集合包含关系，则为一个偏序集，也是一种非严格偏序。
　　设X是互联网中网页的集合，其是对任意不存在环路的网页链接通路关系，由于网页自己不能链接自己，这种关系只能是。则为一个偏序集，也是一种严格偏序。
　　设X是世界所有人，其是对任意长晚辈关系，由于自己和自己不能构成长晚辈关系，这种关系只能是。则为一个偏序集，也是一种严格偏序。
　　设，X是Y的幂集合，其是对任意集合包含关系。则为一个偏序集，也是一种非严格偏序。
　　1.2 偏序与有向无环图
　　偏序关系可以用一个有向无环图表示，任意的是图中的结点，其具体代表X集合中的元素。该偏序中的任意一个有序对必然对应G中的一段弧。
　　定义1.5（邻近）[1] 在偏序关系中，对任意，若，且不存在，则称是的下邻近，是的上邻近。
　　例1.4 设，其是对任意集合包含关系，则图1.1是的偏序关系图。
　　图1.1 的偏序关系图
　　这种偏序关系图，可以理解为箭头结点比箭尾结点大，默认下端比上端的结点小，可以省略图中箭头，这样的图常常称为Hasse图。图1.2示意了常见的具有1到4格点半序关系的Hasse图。
　　图1.2 具有1到4格点半序关系的Hasse图[1]
　　定义1.6（偏序直积）[1] 两个偏序关系和，它们的直积定义为：，直积中关系表示满足且。
　　例1.5 设X是实数集，是实数的大小关系，它们构成二维直角坐标x轴，是一个偏序关系。设Y是实数集，是实数的大小关系，它们构成二维直角坐标y轴，是一个偏序关系。就是平面直角坐标系中的点，中满足，也即满足且。
　　1.3 格
　　在一个偏序关系中，N是X的一个子集，X中的元素满足对任意的，都有，则称是N的一个下界；如果N的所有下界组成的集合中有*大元素，则称这个元素为N的下确界。反之，在一个偏序关系中，N是X的一个子集，X中的元素s满足对任意的，都有，则称s是N的一个上界；如果N的所有上界组成的集合中有*小元素，则称这个元素为N的上确界。
　　图1.3是一个由10个结点组成的偏序关系，其中，则集合满足N的下界条件，1是N的下确界；集合满足N的上界条件，8是N的上确界。
　　图1.3 10个结点组成的偏序关系图[1]
　　定义1.7（完全格）[1] 设是偏序关系，若X的任意二元子集都存在上确界以及下确界，则称是格（lattice）。若X中任意子集都存在上确界以及下确界，则称是完全格。
　　（1）完全格中存在一个*大的元素（*小的上确界），称为1元素，也存在一个*小的元素（*大的下确界），称为0元素。
　　（2）在完全格中，*小元和*大元都为。
　　（3）在完全格上，定义两个运算和。对任意，若，则。运算和运算分别称为取大和取小运算。
　　（4）运算和运算满足结合律、交换律和分配律。对任意，有
　　结合律：
　　分配律：
　　交换律：
　　1.4 闭包算子和Galois连接
　　定义1.8（闭包算子）[1] 给定偏序关系，在X上的闭包算子是函数，如果满足以下三个条件：
　　（1）且，具有扩展性；
　　（2）若，则，是单调递增函数；
　　（3）且，是幂等函数。
　　定义1.9（Galois连接）[1] 给定两个偏序关系和，令和是它们之间的两个单调函数，与是Galois连接，当且仅当和满足以下三个条件：
　　（1）若，则；
　　（2）若，则；
　　（3）
　　Galois连接在其他参考文献中有另一种等价定义：和，如果，则，即，也称和是两个偏序关系和上的Galois连接。
　　定义1.10（关系Galois连接）[1] 集合X和Y上的任意一个二元关系，则X与Y之间的关系Galois连接和定义为
　　（1.2）
　　也即子集关系映射。
　　1.5 概念与概念格
　　概念是人类进行思维的*基本单位，是用来组织成为诸如判断、结论等更为复杂思想的基础，是人类进行知识表述的一种有效手段，属于哲学的范畴。基于Birkhoff对格理论的贡献，德国的Rudolf Wille在1982年首先将形式概念分析

目录
第1章　概念背景图的数学基础　1
1.1　偏序　1
1.2　偏序与有向无环图　3
1.3　格　5
1.4　闭包算子和Galois连接　6
1.5　概念与概念格　6
第2章　概念及其挖掘　10
2.1　概念格的构建算法　10
2.1.1　批处理算法　10
2.1.2　增量算法　11
2.2　基于信息系统的概念提取方法　12
2.3　多值形式背景概念格的构建　14
2.3.1　形式背景与概念　15
2.3.2　构造概念格的算法　19
2.3.3　算法复杂度分析　25
2.3.4　正确性分析　26
2.3.5　有效性分析　28
2.3.6　实验分析　28
2.4　基于矩阵运算的概念格构建　30
2.4.1　获取形式概念　31
2.4.2　建格算法　33
2.4.3　实例分析　36
2.4.4　算法分析　37
2.4.5　仿真实验　38
2.4.6　实验分析　41
第3章　概念之间的关系　43
3.1　格上概念相似度的计算　43
3.2　基于编辑距离的相似性度量方法　45
3.3　概念相似度计算　47
3.4　概念相似度的典型应用　49
3.4.1　概念与Agent间的相似度计算方法　49
3.4.2　Agents间的相似度计算方法　50
3.4.3　两个Agent Crawlers间的理解度　50
第4章　知识图谱相关技术　54
4.1　实体获取主要方法　55
4.1.1　基于词典知识库的方法　56
4.1.2　基于种子概念的方法　56
4.1.3　基于语言学规则的方法　57
4.1.4　基于统计机器学习的方法　57
4.1.5　混合方法　58
4.2　关系提取　59
4.2.1　人物互动关系提取算法　59
4.2.2　微博的特点改进依赖三元核　60
4.2.3　依赖三元核词项语义特征和句法特征改进方法　61
4.3　微博人物互动关系分类　67
4.3.1　关系描述词提取规则　68
4.3.2　词典分类关系描述词　69
4.4　知识图谱的建立　73
第5章　相关背景图及其构建　75
5.1　链接背景图　75
5.2　相关背景图的研究　77
5.2.1　相关背景图在链接上存在的缺陷　79
5.2.2　改进思路　80
5.2.3　改进方法　81
5.2.4　算法举例说明　84
5.2.5　链接路径的相关背景图的改进实验结果　86
5.3　网页语义上的相关背景图的改进　90
5.3.1　HowNet的相关预备知识　90
5.3.2　单词的相似性计算　92
5.3.3　文档的相似性　94
5.3.4　重新定义相关性信任度　94
5.3.5　扩展主题特征词　95
5.3.6　网页语义的相关背景图的改进实验结果　96
5.4　相关背景图的应用　99
5.4.1　发现与主题相关的微博用户　99
5.4.2　主题相关用户的收集　102
5.5　实验以及评价　104
5.5.1　构造实验数据集　104
5.5.2　评价指标　105
5.5.3　实验结果与分析　106
第6章　概念背景图及构建　108
6.1　概念格上隐含的关系　108
6.2　格上核心概念的定义　109
6.3　格上概念距离的计算　110
6.4　概念相似度的应用　113
6.5　概念背景图的构建　114
6.6　概念背景图在网页挖掘中的应用　118
6.7　概念背景图的更新　123
6.7.1　增量概念及其产生算法　123
6.7.2　更新概念背景图　126
6.7.3　删除主题不相关概念　128
6.8　概念背景图的系统实现及应用　132
6.8.1　系统构建　132
6.8.2　实验数据集的介绍　133
6.8.3　评价指标　135
6.8.4　结果分析　135
第7章　不同类型的概念背景图　138
7.1　领域本体的语义相关度度量　138
7.1.1　语义相关度　138
7.1.2　语义相关度度量　139
7.2　WordNet与语义相关度　141
7.2.1　WordNet概述　141
7.2.2　基于WordNet的语义相关度　142
7.2.3　信息内容与语义相关度　143
7.3　领域本体和相似概念背景图的主题爬行策略　144
7.3.1　链接分析概述　145
7.3.2　领域本体和相似概念背景图的主题爬行流程　145
7.4　实验及结果分析　150
7.4.1　准备数据集　150
7.4.2　收集主题数据及处理　152
7.4.3　构建相似概念背景图　153
7.4.4　计算锚文本相关度及预测URL优先级分值　154
7.5　实验结果对比分析　155
第8章　概念背景图的分层　158
8.1　概念背景图的参数确定　158
8.2　概念背景图的层次划分　158
8.3　获取OSCCG及OPV的详细过程　162
8.4　概念背景图的更新机制　163
8.4.1　相关概念　163
8.4.2　概念背景图中概念的更新　164
8.4.3　概念背景图层次的更新　167
8.5　实验及结果分析　169
8.5.1　第一部分实验结果　171
8.5.2　第二部分实验结果　173
参考文献　175