2009-8-20 史忠植 高级人工智能 1
第九章 知识发现史忠植中科院计算所
2009-8-20 史忠植 高级人工智能 2
内容第一部分,知识发现第二部分,数据库中知识发现第三部分,粗糙集
2009-8-20 史忠植 高级人工智能 3
9.1 概述
数据变知识
信息变知识
2009-8-20 史忠植 高级人工智能 4
知识发现
Gerwin在 1974年开始机器发现的研究,他研究噪声数据下归纳单变量复杂函数。
1978年,Buchanan和 Mitchell开发 META-
DENDRAL,它可以发现规则,描述怎样产生分子结构。
1977年 Lenat开发的 AM系统可以重新发现数论的数学概念。
从 1976年到 1983年,Langley,Simon和
Bradshaw 开发了 BACON系统。
Kokar采用模型驱动,开发的 COPER系统可以进行数值发现 。
2009-8-20 史忠植 高级人工智能 5
科学发现的过程采集数据寻找描述形成理论测试
2009-8-20 史忠植 高级人工智能 6
科学发现与数据库中知识发现的不同
科学发现具有极强的目的性，是被控制的，
其数据来自精心设计的实验,去掉了无关因素，仅保留少数的参数，并对目标参数进行解释。而一般典型的商业数据库的记录，
却具有许多信息以适应组织的不同目标的需要。
科学发现中可对实验重新设计，而一般数据库却不会频繁地改变它的结构，不会重新收集数据。
2009-8-20 史忠植 高级人工智能 7
9.2 数据驱动知识发现 —— BACON
从 1976到 1983年，共研制了六个版本：
BACON.1可以看成是一种通用规则归纳器。
BACON.2包括启发式处理顺序信息，增加了两种操作。一种用于计算差别以便发现递归序列，另一种用于产生多项式项。
BACON.3用不变性检查提出的假设来修改训练例子。
BACON.4主要解决数据集怎样能以简明方式描述。
BACON.5能够处理对称假设,简单的类比,并能处理噪声。
BACON.6能够处理数据中的大量噪声,使用差分技术,寻找相关两项的最优的多项式函数。
2009-8-20 史忠植 高级人工智能 8
BACON系统的特点
采用数据驱动
通过启发式约束搜索
依赖于理论数据项
递归应用一些通用的发现方法
2009-8-20 史忠植 高级人工智能 9
BACON系统采用的一般方法
(1) BACON产生函数,描述一组数据。
(2) 系统设 个变量为常数,仅一个变量 改变，所以分析函数,而 保持为常数。
(3) BACON 处理数据时采用启发式，设 是线性的，或者双曲线函数 或,其中 取决于变量 。
(4) 如果这些假设之一符合数据，那么 BACON分别导出假设或者 。 所有这些都称为“理论项”。如果自变量 是规范型,随 而改变，那么称其具有“本征特性”，其值赋给 作为初值。
(5) 设 或 作为依赖 的新变量。
(6) 假定 （或 ），重复整个过程。
),.,,,,( 21 nxxxfy?
1?n 1X
)( 11 xfy? nxx,...,2
1f
Cxy? 1 Cxy C nxx,...,2
Cxy?1/ Cxy 1
1x y 1x
y
1/ xy 1xy? nxx,...,2
21 '/ xCxyC 2/' xC
2009-8-20 史忠植 高级人工智能 10
开普勒定律的训练实例实例 行星水星 1 1
金星 8 4
地球 27 9
p d
1I
2I
3I
2009-8-20 史忠植 高级人工智能 11
新项的值实例 行星水星 1 1
金星 8 4
地球 27 9
p d
1I
2I
3I
pd/ pd /2 23 / pd
1.0
0.5
0.33
1.0
2.0
3.0
1
1
1
2009-8-20 史忠植 高级人工智能 12
BACON 的操作
1) 不变性检查：若某个变量至少两次取同样值
V,则假设该变量保持为常量 V。
2) 特化：在以前得到的假设与数据冲突时，就增加合取条件来使假设特化。
3) 产生斜率和截距：若发现两个变量保持线性关系，则产生的新项是斜率和截距。
4) 产生乘积：若两个变量反向变化而且斜率不同，则产生的新项是二者乘积。
5) 产生商数：若两个变量同向变化但斜率不同，
则产生的新项是二者的商。
2009-8-20 史忠植 高级人工智能 13
BACON的优缺点
优点：
能发现实值变量间关系的定律。
规则空间操作可以组合现有项，以产生新项。
BACON.3在发现局部规律性后，修改训练例子的表示。
缺点：
仅在特殊情况下才使用操作，这使程序对变量的次序和训练例子的选择很敏感。
不能处理有噪声的训练例子。
只能处理简单概念,例如不能发现析取概念。
2009-8-20 史忠植 高级人工智能 14
9.3 模型驱动知识发现 —— COPER
COPER知识发现算法：
1) 决定生成新的描述的基本描述和词法规则。
2) 确定函数初始的自变量和因变量。
3) 从自变量中选取基本参数。
4) 使用生成规则,根据基本参数表示其它参数,这些是导出参数。
5) 设计实验,基本参数改变时,导出参数将保持不变。
6) 对于每种轨迹计算函数的预测值,并与观测值比较。
7) 如果预测值与观测值相差很大,那么生成一个新的描述符。
形成新的描述符后,将会产生新的划分。
重复步骤 (5) 到 (7)。
2009-8-20 史忠植 高级人工智能 15
例子 —— 自由落体运动其中 S是距离,V是速度,t是时间,g是重力加速度。设输入是一组数据,作为自变量和因变量的值。
2/2tgtVS
2009-8-20 史忠植 高级人工智能 16
第一步：标识描述空间的生成符和生成导出描述符的规则。
生成符,(米 )和 (秒 )，分别表示长度和时间。
每个描述符可以表示成,。
第二步：标识依赖参数和知道的独立参数。
依赖参数：
独立参数：
函数形式：
第三步：系统选择基本参数。
选择 t和 V为基本参数。
第四步：用基本参数表示其它参数
m s
210 aaa smeX?
11tVbS s?
mesmeS ss 01
smesmeV vv /11
221 / smesmeg gg
sesmet tt 10
),,( gtVFS?
11 tVbg g
2009-8-20 史忠植 高级人工智能 17
第五步：设计实验来验证
)(st)/( smV
自由落体定律的值
)/( 2smg S-预测值 S-观测值
6
9
12
15
18
21
2
3
4
5
6
7
10
10
10
10
10
10
32
72
128
200
288
392
32
72
128
200
288
392
2009-8-20 史忠植 高级人工智能 18
)(st)/( smV
g未知的自由落体值
S-预测值 S-观测值
5
10
15
20
25
39
2
12
10
8
6
4
32
384
480
752
480
384
32
840
650
480
330
200
2009-8-20 史忠植 高级人工智能 19
第六步：计算第一个实验点的 值,。 然后计算 S的预测值。比较 S的预测值和观测值，可以发现它们相差很大。这表明整个相关条件不成立。
第七步：生成漏掉的参数。这个参数表示为：
根据第五步，设计一种轨迹,保持为常数。
从实验结果看出，预测值与观测值相差很大，因此，系统拒绝 X为候选参数。 COPER使用 m和 s生成全部可能的候选参数，并且进行评价。参数 给出的误差最小，因此该项被选，完成函数的参数集。
2.3)25/(32sbsb
22tVbX x?
22tV
11 tVbg g
2009-8-20 史忠植 高级人工智能 20
)(st)/( smV )( 2mX S-预测值 S-观测值
1
2
4
8
16
32
32
16
8
4
2
1
1
1
1
1
1
1
5152
5152
5152
5152
5152
5152
5152
1312
352
112
52
37
相关的测试结果)( 2mX
2009-8-20 史忠植 高级人工智能 21
9.4 理论驱动式发现方法理论驱动式发现方法的典型事例是 AM程序，
即发现初等数学概念和集合论概念的计算机程序。 AM程序运用启发式发现新概念和新猜想。
AM用最基本的数学知识直接建立有兴趣的数学概念及其评价。它使用求精算子的处理方式,在数学概念空间中包含 115个概念。
在 AM运行时将进行启发式搜索,建立新概念,
并提出概念之间相互关系的猜想。
2009-8-20 史忠植 高级人工智能 22
AM的特点
框架表示
每个概念表示为一个框架，每一个框架含有同样确定的槽。
每一概念都有定义槽、该概念的已知正面和反面例子槽、链接该概念与其推广及特例概念的槽、该概念的价值槽,以及若干个其它槽。
产生式系统
概念的每个槽上都附有试探规则,可执行这些规则以填充一个槽的内容或检查该槽内容是否正确。
附于 AM知识库中概念槽上共有 242个启发式规则。
规则由条件部分和行为部分构成。
启发式驱动的,最佳优先,算法
通过修改概念的兴趣槽和价值槽以及建立和确认任务的启发式信息控制搜索。
AM有 59条启发式规则用来估价概念和任务的兴趣分。
2009-8-20 史忠植 高级人工智能 23
素数的框架表示名称,Prime Numbers
定义：
初始,Number-of-divisors-of(x)=2
谓词演算：
迭代,(for x>1):for i from 2 to sqrt(x),┐(i|x)
IS-A,Set
例子,2,3,5,7,11,13,17
边界,2,3
边界出错,0,1
出错,12
泛化：数，有偶数个因子的数，有素数个因子的数。
特化：奇素数，素数对，可唯一表示成素数之和的素数。
)1|)(()(Pr xzzxzzxi m e
2009-8-20 史忠植 高级人工智能 24
猜想：唯一的因子分解，哥德巴赫猜想，因子个数的极端情况。
类比：可被最多个数整除的数，是因子个数极小的数的逆向极端,将非单群分解为单群。
兴趣：将概念 Primes与 Times及 Divisor-of相联系的猜想具有兴趣。
价值,800
初始,Divisors-of-1
Defined-using,Divisors-of
历史：
N-Good-Examples,840
N-Bad-Examples,5000
N-Good-Conjectures,3
N-Bad-Conjectures,7
2009-8-20 史忠植 高级人工智能 25
启发式规则的行为
1) 填充某概念 C的槽 S。
2) 查概念 C的槽 S,包括确认该槽内容正确性和注意关于某槽有趣事实。常有通过某一规则检查一个槽从而发现应当执行一些新任务的情形。
3) 建立新概念。通过向知识库中加入一个新的框架并填充该框架的定义槽而建立。通常此时也填充该概念的价值槽。
4) 向日程表中加入新任务。
5) 修改日程表中任务的兴趣分。于是规则可以给已有任务增加新的理由,这是引导对概念和猜想搜索的又一方式。
2009-8-20 史忠植 高级人工智能 26
AM学习算法
1) 选择一个概念，求其价值，并产行该概念的实例，
即搜索实例空间。
2) 检查实例以寻找规律，根据这些规律，
①更新该概念的兴趣估值；
②产生新概念；
③提出新猜想。
也就是检查这些实例概念空间 (规则空间 )和猜想空间。
3) 将所获得知识 (特别是那些从猜想得到的知识 ) 传播到系统中其它概念上去,即进行记录以保持知识库的完整性和一致性。
2009-8-20 史忠植 高级人工智能 27
产生实例
AM采用下列几类技术产生实例：
将定义的符号例化。
生成并测试。
实例的继承。
应用概念的算法。
用观察或类比进行推理。
2009-8-20 史忠植 高级人工智能 28
搜索规则空间的方法
1) 泛化。 AM 以一定形式实现了几乎在所有其它 AI程序中出现过的泛化规则,实现了去条件、增加任选,变常量为变量等规则。实现了特例化否定合取技术、推广含有量词的表达式、应用于递归的泛化规则等。
2) 特化。进行特化的规则是泛化规则的逆规则。
3) 例外情况处理。当一个概念具有许多例外情况 (临界反例 )
时,可建立一个新概念。还可建立仅包含原来概念的一般正例的新概念。
4) 类比推理。若 J是一个猜想,而 J'是类似的一个猜想,那么就产生概念 {b'|J'(b')}以及概念 {b'|A!→J'(b')} 分别是使 J'为真的对象的集合和使 J'为假的对象的集合。
2009-8-20 史忠植 高级人工智能 29
AM中提出猜想的规则的形式
1)C1是 C2的实例；
2)C1是 C2的特例 (泛化 )；
3)C1与 C2等价；
4)C1通过 X与 C_2相关 (X是某一谓词 )；
5)操作 C1具有定义域 D或值域 R。
2009-8-20 史忠植 高级人工智能 30
AM的初始概念树任何事物任何概念 非概念作用操作 谓词 关系 原子 猜想 结构
第九章 知识发现史忠植中科院计算所
2009-8-20 史忠植 高级人工智能 2
内容第一部分,知识发现第二部分,数据库中知识发现第三部分,粗糙集
2009-8-20 史忠植 高级人工智能 3
9.1 概述
数据变知识
信息变知识
2009-8-20 史忠植 高级人工智能 4
知识发现
Gerwin在 1974年开始机器发现的研究,他研究噪声数据下归纳单变量复杂函数。
1978年,Buchanan和 Mitchell开发 META-
DENDRAL,它可以发现规则,描述怎样产生分子结构。
1977年 Lenat开发的 AM系统可以重新发现数论的数学概念。
从 1976年到 1983年,Langley,Simon和
Bradshaw 开发了 BACON系统。
Kokar采用模型驱动,开发的 COPER系统可以进行数值发现 。
2009-8-20 史忠植 高级人工智能 5
科学发现的过程采集数据寻找描述形成理论测试
2009-8-20 史忠植 高级人工智能 6
科学发现与数据库中知识发现的不同
科学发现具有极强的目的性，是被控制的，
其数据来自精心设计的实验,去掉了无关因素，仅保留少数的参数，并对目标参数进行解释。而一般典型的商业数据库的记录，
却具有许多信息以适应组织的不同目标的需要。
科学发现中可对实验重新设计，而一般数据库却不会频繁地改变它的结构，不会重新收集数据。
2009-8-20 史忠植 高级人工智能 7
9.2 数据驱动知识发现 —— BACON
从 1976到 1983年，共研制了六个版本：
BACON.1可以看成是一种通用规则归纳器。
BACON.2包括启发式处理顺序信息，增加了两种操作。一种用于计算差别以便发现递归序列，另一种用于产生多项式项。
BACON.3用不变性检查提出的假设来修改训练例子。
BACON.4主要解决数据集怎样能以简明方式描述。
BACON.5能够处理对称假设,简单的类比,并能处理噪声。
BACON.6能够处理数据中的大量噪声,使用差分技术,寻找相关两项的最优的多项式函数。
2009-8-20 史忠植 高级人工智能 8
BACON系统的特点
采用数据驱动
通过启发式约束搜索
依赖于理论数据项
递归应用一些通用的发现方法
2009-8-20 史忠植 高级人工智能 9
BACON系统采用的一般方法
(1) BACON产生函数,描述一组数据。
(2) 系统设 个变量为常数,仅一个变量 改变，所以分析函数,而 保持为常数。
(3) BACON 处理数据时采用启发式，设 是线性的，或者双曲线函数 或,其中 取决于变量 。
(4) 如果这些假设之一符合数据，那么 BACON分别导出假设或者 。 所有这些都称为“理论项”。如果自变量 是规范型,随 而改变，那么称其具有“本征特性”，其值赋给 作为初值。
(5) 设 或 作为依赖 的新变量。
(6) 假定 （或 ），重复整个过程。
),.,,,,( 21 nxxxfy?
1?n 1X
)( 11 xfy? nxx,...,2
1f
Cxy? 1 Cxy C nxx,...,2
Cxy?1/ Cxy 1
1x y 1x
y
1/ xy 1xy? nxx,...,2
21 '/ xCxyC 2/' xC
2009-8-20 史忠植 高级人工智能 10
开普勒定律的训练实例实例 行星水星 1 1
金星 8 4
地球 27 9
p d
1I
2I
3I
2009-8-20 史忠植 高级人工智能 11
新项的值实例 行星水星 1 1
金星 8 4
地球 27 9
p d
1I
2I
3I
pd/ pd /2 23 / pd
1.0
0.5
0.33
1.0
2.0
3.0
1
1
1
2009-8-20 史忠植 高级人工智能 12
BACON 的操作
1) 不变性检查：若某个变量至少两次取同样值
V,则假设该变量保持为常量 V。
2) 特化：在以前得到的假设与数据冲突时，就增加合取条件来使假设特化。
3) 产生斜率和截距：若发现两个变量保持线性关系，则产生的新项是斜率和截距。
4) 产生乘积：若两个变量反向变化而且斜率不同，则产生的新项是二者乘积。
5) 产生商数：若两个变量同向变化但斜率不同，
则产生的新项是二者的商。
2009-8-20 史忠植 高级人工智能 13
BACON的优缺点
优点：
能发现实值变量间关系的定律。
规则空间操作可以组合现有项，以产生新项。
BACON.3在发现局部规律性后，修改训练例子的表示。
缺点：
仅在特殊情况下才使用操作，这使程序对变量的次序和训练例子的选择很敏感。
不能处理有噪声的训练例子。
只能处理简单概念,例如不能发现析取概念。
2009-8-20 史忠植 高级人工智能 14
9.3 模型驱动知识发现 —— COPER
COPER知识发现算法：
1) 决定生成新的描述的基本描述和词法规则。
2) 确定函数初始的自变量和因变量。
3) 从自变量中选取基本参数。
4) 使用生成规则,根据基本参数表示其它参数,这些是导出参数。
5) 设计实验,基本参数改变时,导出参数将保持不变。
6) 对于每种轨迹计算函数的预测值,并与观测值比较。
7) 如果预测值与观测值相差很大,那么生成一个新的描述符。
形成新的描述符后,将会产生新的划分。
重复步骤 (5) 到 (7)。
2009-8-20 史忠植 高级人工智能 15
例子 —— 自由落体运动其中 S是距离,V是速度,t是时间,g是重力加速度。设输入是一组数据,作为自变量和因变量的值。
2/2tgtVS
2009-8-20 史忠植 高级人工智能 16
第一步：标识描述空间的生成符和生成导出描述符的规则。
生成符,(米 )和 (秒 )，分别表示长度和时间。
每个描述符可以表示成,。
第二步：标识依赖参数和知道的独立参数。
依赖参数：
独立参数：
函数形式：
第三步：系统选择基本参数。
选择 t和 V为基本参数。
第四步：用基本参数表示其它参数
m s
210 aaa smeX?
11tVbS s?
mesmeS ss 01
smesmeV vv /11
221 / smesmeg gg
sesmet tt 10
),,( gtVFS?
11 tVbg g
2009-8-20 史忠植 高级人工智能 17
第五步：设计实验来验证
)(st)/( smV
自由落体定律的值
)/( 2smg S-预测值 S-观测值
6
9
12
15
18
21
2
3
4
5
6
7
10
10
10
10
10
10
32
72
128
200
288
392
32
72
128
200
288
392
2009-8-20 史忠植 高级人工智能 18
)(st)/( smV
g未知的自由落体值
S-预测值 S-观测值
5
10
15
20
25
39
2
12
10
8
6
4
32
384
480
752
480
384
32
840
650
480
330
200
2009-8-20 史忠植 高级人工智能 19
第六步：计算第一个实验点的 值,。 然后计算 S的预测值。比较 S的预测值和观测值，可以发现它们相差很大。这表明整个相关条件不成立。
第七步：生成漏掉的参数。这个参数表示为：
根据第五步，设计一种轨迹,保持为常数。
从实验结果看出，预测值与观测值相差很大，因此，系统拒绝 X为候选参数。 COPER使用 m和 s生成全部可能的候选参数，并且进行评价。参数 给出的误差最小，因此该项被选，完成函数的参数集。
2.3)25/(32sbsb
22tVbX x?
22tV
11 tVbg g
2009-8-20 史忠植 高级人工智能 20
)(st)/( smV )( 2mX S-预测值 S-观测值
1
2
4
8
16
32
32
16
8
4
2
1
1
1
1
1
1
1
5152
5152
5152
5152
5152
5152
5152
1312
352
112
52
37
相关的测试结果)( 2mX
2009-8-20 史忠植 高级人工智能 21
9.4 理论驱动式发现方法理论驱动式发现方法的典型事例是 AM程序，
即发现初等数学概念和集合论概念的计算机程序。 AM程序运用启发式发现新概念和新猜想。
AM用最基本的数学知识直接建立有兴趣的数学概念及其评价。它使用求精算子的处理方式,在数学概念空间中包含 115个概念。
在 AM运行时将进行启发式搜索,建立新概念,
并提出概念之间相互关系的猜想。
2009-8-20 史忠植 高级人工智能 22
AM的特点
框架表示
每个概念表示为一个框架，每一个框架含有同样确定的槽。
每一概念都有定义槽、该概念的已知正面和反面例子槽、链接该概念与其推广及特例概念的槽、该概念的价值槽,以及若干个其它槽。
产生式系统
概念的每个槽上都附有试探规则,可执行这些规则以填充一个槽的内容或检查该槽内容是否正确。
附于 AM知识库中概念槽上共有 242个启发式规则。
规则由条件部分和行为部分构成。
启发式驱动的,最佳优先,算法
通过修改概念的兴趣槽和价值槽以及建立和确认任务的启发式信息控制搜索。
AM有 59条启发式规则用来估价概念和任务的兴趣分。
2009-8-20 史忠植 高级人工智能 23
素数的框架表示名称,Prime Numbers
定义：
初始,Number-of-divisors-of(x)=2
谓词演算：
迭代,(for x>1):for i from 2 to sqrt(x),┐(i|x)
IS-A,Set
例子,2,3,5,7,11,13,17
边界,2,3
边界出错,0,1
出错,12
泛化：数，有偶数个因子的数，有素数个因子的数。
特化：奇素数，素数对，可唯一表示成素数之和的素数。
)1|)(()(Pr xzzxzzxi m e
2009-8-20 史忠植 高级人工智能 24
猜想：唯一的因子分解，哥德巴赫猜想，因子个数的极端情况。
类比：可被最多个数整除的数，是因子个数极小的数的逆向极端,将非单群分解为单群。
兴趣：将概念 Primes与 Times及 Divisor-of相联系的猜想具有兴趣。
价值,800
初始,Divisors-of-1
Defined-using,Divisors-of
历史：
N-Good-Examples,840
N-Bad-Examples,5000
N-Good-Conjectures,3
N-Bad-Conjectures,7
2009-8-20 史忠植 高级人工智能 25
启发式规则的行为
1) 填充某概念 C的槽 S。
2) 查概念 C的槽 S,包括确认该槽内容正确性和注意关于某槽有趣事实。常有通过某一规则检查一个槽从而发现应当执行一些新任务的情形。
3) 建立新概念。通过向知识库中加入一个新的框架并填充该框架的定义槽而建立。通常此时也填充该概念的价值槽。
4) 向日程表中加入新任务。
5) 修改日程表中任务的兴趣分。于是规则可以给已有任务增加新的理由,这是引导对概念和猜想搜索的又一方式。
2009-8-20 史忠植 高级人工智能 26
AM学习算法
1) 选择一个概念，求其价值，并产行该概念的实例，
即搜索实例空间。
2) 检查实例以寻找规律，根据这些规律，
①更新该概念的兴趣估值；
②产生新概念；
③提出新猜想。
也就是检查这些实例概念空间 (规则空间 )和猜想空间。
3) 将所获得知识 (特别是那些从猜想得到的知识 ) 传播到系统中其它概念上去,即进行记录以保持知识库的完整性和一致性。
2009-8-20 史忠植 高级人工智能 27
产生实例
AM采用下列几类技术产生实例：
将定义的符号例化。
生成并测试。
实例的继承。
应用概念的算法。
用观察或类比进行推理。
2009-8-20 史忠植 高级人工智能 28
搜索规则空间的方法
1) 泛化。 AM 以一定形式实现了几乎在所有其它 AI程序中出现过的泛化规则,实现了去条件、增加任选,变常量为变量等规则。实现了特例化否定合取技术、推广含有量词的表达式、应用于递归的泛化规则等。
2) 特化。进行特化的规则是泛化规则的逆规则。
3) 例外情况处理。当一个概念具有许多例外情况 (临界反例 )
时,可建立一个新概念。还可建立仅包含原来概念的一般正例的新概念。
4) 类比推理。若 J是一个猜想,而 J'是类似的一个猜想,那么就产生概念 {b'|J'(b')}以及概念 {b'|A!→J'(b')} 分别是使 J'为真的对象的集合和使 J'为假的对象的集合。
2009-8-20 史忠植 高级人工智能 29
AM中提出猜想的规则的形式
1)C1是 C2的实例；
2)C1是 C2的特例 (泛化 )；
3)C1与 C2等价；
4)C1通过 X与 C_2相关 (X是某一谓词 )；
5)操作 C1具有定义域 D或值域 R。
2009-8-20 史忠植 高级人工智能 30
AM的初始概念树任何事物任何概念 非概念作用操作 谓词 关系 原子 猜想 结构
