编
编程不懂
Unregistered / Unconfirmed
GUEST, unregistred user!
基于深度优先的公式发现算法
---- 1 引言
---- 数据开采是从大型数据库或数据仓库中发现并提取隐藏在其中的信息的一种新技术,
目的是帮助决策者寻找数据间潜在的关联, 发现被忽略的要素, 而这些信息对预测趋势和决
策行为也许是十分有用的。数据开采技术能从DW中自动分析数据, 进行归纳性推理, 从中发
掘出潜在的模式,或产生联想, 建立新的业务模型, 帮助决策者调整市场策略,做出正确的决
策。数据开采表明,知识就隐藏在日常积累下来的大量数据之中, 而仅靠复杂的算法和推理并
不能发现知识,数据才是知识的真正源泉。数据开采为AI的发展指出了一条新的发展道路。
---- 机器学习是人工智能的一个重要分支。对机器学习的研究促进了人工智能的在理论方法
和实际应用上的迅速发展。学习和解决问题是人类最重要的两个智能行为。机器学习是让计
算机模拟和实现人类 的学习、获取知识。机器学习也是计算机具有人工智能的重要标志。机
器学习具有快速、可复制、自主性差、机械、学习方法单一等特点。由于机器不存在人类所
具有的生理因素的限制，因此，机器可以“不知疲倦”地学习，而且，在对一些数理化的知
识的学习上，机器也比人的速度要快得多。而且，由于计算机程序易于复制，因此，计算机
的学习是不会终止的，其所具有的知识也可以一直保留下来。但是，计算机的学习方法单一
，只能根据有限的学习方法进行机械学习，本身不能创造方法，尤其是不具有人类学习所特
有的“灵感思维”，这也是机器学习在目前来说尚不可克服的缺陷。所以，我们必须通过有
效的搜索算法和启发式信息才有可能减少这个缺陷带来的影响。
---- 在人工智能（AI）中，机器学习（ML）的早期研究至少可追溯到70年代初Gerwin的工作
，其它著名的发现算法包括数学发现算法AM、规则发现算法Meta-Dendral、经验发现算法BACON
和类比发现算法Phineas等等。这些算法在一定条件下发现了一些有意义的概念、定律和规则
。但它们普遍对复合函数学习能力不强，需要在搜索算法和启发式函数等方面加以改进，才能
对大量呈复合函数规律变化的数据进行令人满意的学习。近年来，人工智能在理论、方法和
实际应用上迅速发展，人们试图克服算法可适应性差的弱点，使其具有学习功能，能自动学
习知识，学习适应新的环境。
---- 2 BACON算法分析
---- BACON算法是运用人工智能技术从试验数据中寻找其规律性比较成功的一个算法，是Pat
Langly于1980年研制的。BACON算法的思想是程序反复地考察数据并使用精炼算子创造新项，
直到创造的这些项中有一个是常数时为止。于是一个概念就用“项＝常数”的形式表示出来
，其中项为经变量运算组合而形成的表达式。
---- 该算法运用的是数据驱动方法，这种方法使用的规则空间与假设空间是分开的。算法的
规则空间包括若干精炼算子，算法使用精炼算子修改假设，所谓精炼算子就是修改假设空间的
子程序，每个精炼算子以特定的方式修改假设空间，整个学习程序由多个精炼算子组成，程序
使用探索知识对提供的训练例进行分析，决定选用哪个精炼算子。
---- BACON算法中所采用的主要精炼算子如下：
---- 1)发现常数：
---- 当某一属性特征向量取某一值至少两次的时候，触发这个算子，该算子建立这个特征向量
等于常数的假设；
---- 2)具体化：
---- 当已经建立的假设同时间相矛盾时触发这一算子，它通过增加合取条件的形式把假设具
体化；
---- 3)斜率和截距的产生：
---- 当发现两个特征向量是线性相互依赖时触发这一算子，它是建立线性关系的斜率和截距
作为新项；
---- 4)积的产生：
---- 当发现两个特征向量以相反方向递增但又不线性依赖时触发该算子，并产生两向量的乘
积作为新项；
---- 5)商的产生：
---- 当发现两向量以相同方向递增但又不线性依赖时触发该算子，并产生两向量的商作为新
项；
---- 6)模n的项的产生：
---- 当发现两向量v1和v2在模某数n相等时触发该算子，并产生v2(mod n)作为新项。
---- BACON算法是用产生式语言OPS实现的。这个任务产生式算法的优点是，它允许人们写一
套小型的一般规律发现程序。这些程序在收集的数据上进行搜索，同时，这些数据仍存放在
工作存储器中。如果数据出现某种规律性，它就会触发某个算子。
---- 按着这种方式，只要关于属性值的某些一般化有效，BACON就增加一个预言其成分值的产
生式。算法还可以审查它的假说。当算法发现了反例时，如果一般化是在物体之间做的，就加
一些例外的限制，如果一般化是对时间做的，则可加上限或下限。事实上，一旦形成一个假设
就不放弃，虽然其形式可能是修改过的，它也总是把假设存入固定的产生式存储。
---- 总的来说，BACON算法是一个较为完善的机器学习算法。但是，BACON算法存在的缺陷也
是显而易见的，即自动学习的能力比较弱，十分强调人工干预的作用，需要用户指明数据之间
的相关性，甚至有时要指出公式的大概形式，才能进行正确的学习，基本上仍局限于一个再
发现算法，需要在自学习方面加以改进。
---- 3 基于深度优先的公式发现算法
---- 本算法的法基本思想是对某一变量取初等函数和另一变量的初等函数或原始数据进行线
形组合，选取逼近效果最好的少数几个初等函数作为进一步搜索的依据，直至确认已学习出
满足要求的公式或认为在给定的阈值条件下无法学习出来为止。例如有变量X1 和X2，在具体
学习时可以先固定X2，对X1进行原型的匹配，选出误差最小的几个原型，若这时最小误差已经
小于阈值，则认为学习成功，否则针对这几个选出的原型，固定X1，对X2进行原型的匹配，再
选出误差最小的几个原型，同时判断是否满足误差阈值，若满足则认为学习到结果，否则退
出学习过程，学习失败。
---- 启发式方法是求解人工智能问题的一个重要方法。一般的启发式方法是建立启发式函数
，用以引导搜索方向，以便用尽量少的搜索次数，从开始状态达到最终状态。把状态的改变连
接起来便成为搜索路径。由于一个状态的改变可以达到多个不同的状态，若把各种可能到达
的状态都展开它的搜索路径，这将形成一棵搜索树，搜索树如果按二叉树考虑，随着深度n
(状态连续改变数）的增加，树的结点数将迅速增加，若盲目进行搜索，搜索时间就以增加。
---- 智能问题的搜索时间是按指数时间执行的，为解决这种组合爆炸现象，人工智能中发展
了一种启发式搜索方法。在搜索过程中挖掘并使用与任务有关的信息以利于减少搜索，这一类
信息通常称为启发性的信息。利用启发信息的搜索过程叫做启发式搜索方法。本算法在执行
搜索的过程中，也隐含着组合爆炸现象，为解决这一问题，采用了启发式方法来实现搜索过程。
在启发式信息的探索中，以一般函数形式来描述：
---- 设对n个变量的观察数据的变化规律为：
---- 固定其它变量，如，只允许两个变量变化，则与之间呈一种线性关系。的原始数据与它
们的函数原型有着一种内在的联系。对某一变量取初等函数和另一变量的初等函数或原始数
据进行线性组合，即从原型库中选取逼近效果最好的少数几个初等函数作为进一步搜索直至
确认的函数原型。本算法的启发式函数形式为：。其线性逼近效果用来度量。
---- 本算法采用了原型搜索优化算法，对原型库中每个原型没有依次与实验数据库中的所有
数据进行匹配运算，在搜索匹配的过程中，能够避开那些显然不可能满足要求的原型，以减少
时间开支。原型搜索优化算法的过程是，在算法进行初始化时，对实验数据库进行一遍扫描
，发现一些数据对某些原型来说在该点没有定义，即该点为这些原型的间断点，则对这些原
型进行标记，在匹配原型时跳过被标记原型。例如，若为负数，则显然诸如一类的原型是不可
选的。通过这一算法，可以使执行效率得到显著提高。
---- 本算法首先针对、进行两次原型匹配，，如果拟合程度较好，即此时的误差小于阈值，
则认为能够学习出基本满足要求的公式，这时，输出结果公式和误差，并且描绘出其曲线。
如果拟合的结果偏差较大，则认为没有得到能够满足要求的结果公式。这时自动舍弃对匹配
的结果，只保留第一次对匹配的五个原型，并转入深度优先的树搜索过程。
---- 下面主要介绍一下生成深度优先搜索树的算法。
---- 该算法主要包括了四个模块：
---- 1) 判断是否得到结果，由此决定是否继续学习；
---- 2) 向更深一层搜索，求出误差小于父结点误差的所有原型，并把它们作为子结点加入到
树结构中去；
---- 3) 若某结点向下搜索时误差都在变大，那么认为它没有孩子结点，此时回溯，扩展搜索
树中那些还没有扩展的结点；
---- 4) 每次进入更深一层的搜索时，都要交换匹配的变量，以实现一次针对，一次针对进行
原型匹配。
---- 在科学试验或统计研究中，人们常常需要从一组测定的数据，例如N个点中去求得因变
量x和自变量y的一个近似表达式。这就是由给定的N个点(i=1,2,3…n)求数据拟合问题。根据
数据之间的关系给出它们之间的数学公式有:
---- 而对其中各个系数的确定常用的是最小二乘法，即使各点的误差平方和最小：
---- 对于如何选择使误差平方和最小，将对求偏微商，再使偏微商等于零，得到应满足的方
程。
---- 求得这组方程的解即得拟合公式。
---- 4 小结
---- 本算法与BACON算法相比，在学习能力上有所进步。首先是能进行两层学习，其次，还
可以有两种学习途径，分别是自动学习和人工学习。自动学习是计算机自己进行两层搜索，
不用人工干预。而人工学习可以由用户根据数据库中的数据及其曲线选择对X1匹配时所选用
的原型，即不用算法进行第一层的搜索，直接进入第二层的学习，可以大大提高学习的效率。
具备了修改误差阈值的功能，通过调整阈值可以控制学习的结果。
---- 我们认为，对本算法而言，还应该加强以下方面研究：
---- 1.在对搜索树进行深度优先搜索时，可以考虑一下控制策略的调整。比如本算法中要求
在向下搜索时误差一旦变大就停止该分支的搜索，这样有可能漏掉正确的分支，可以改进为
允许误差变大一次或两次，从而可以继续向下搜索一至两层，这样，发现公式的余地就会更
大一些。
---- 对原型库的扩充和管理。原型库是算法的核心组成部分，足够的原型是保证学习成功的
必要前提，算法应该具备对原型库的编辑、修改、增加、删除功能。
---- 3．学习规则的增加。侧重于规则库的建立和规则的使用。
---- 4．对多变量公式发现的研究。
---- 另外，还有必要结合当前国际上流行的Internet技术和数据仓库技术，进一步拓宽可视
化公式发现的研究领域。
---- 1 引言
---- 数据开采是从大型数据库或数据仓库中发现并提取隐藏在其中的信息的一种新技术,
目的是帮助决策者寻找数据间潜在的关联, 发现被忽略的要素, 而这些信息对预测趋势和决
策行为也许是十分有用的。数据开采技术能从DW中自动分析数据, 进行归纳性推理, 从中发
掘出潜在的模式,或产生联想, 建立新的业务模型, 帮助决策者调整市场策略,做出正确的决
策。数据开采表明,知识就隐藏在日常积累下来的大量数据之中, 而仅靠复杂的算法和推理并
不能发现知识,数据才是知识的真正源泉。数据开采为AI的发展指出了一条新的发展道路。
---- 机器学习是人工智能的一个重要分支。对机器学习的研究促进了人工智能的在理论方法
和实际应用上的迅速发展。学习和解决问题是人类最重要的两个智能行为。机器学习是让计
算机模拟和实现人类 的学习、获取知识。机器学习也是计算机具有人工智能的重要标志。机
器学习具有快速、可复制、自主性差、机械、学习方法单一等特点。由于机器不存在人类所
具有的生理因素的限制，因此，机器可以“不知疲倦”地学习，而且，在对一些数理化的知
识的学习上，机器也比人的速度要快得多。而且，由于计算机程序易于复制，因此，计算机
的学习是不会终止的，其所具有的知识也可以一直保留下来。但是，计算机的学习方法单一
，只能根据有限的学习方法进行机械学习，本身不能创造方法，尤其是不具有人类学习所特
有的“灵感思维”，这也是机器学习在目前来说尚不可克服的缺陷。所以，我们必须通过有
效的搜索算法和启发式信息才有可能减少这个缺陷带来的影响。
---- 在人工智能（AI）中，机器学习（ML）的早期研究至少可追溯到70年代初Gerwin的工作
，其它著名的发现算法包括数学发现算法AM、规则发现算法Meta-Dendral、经验发现算法BACON
和类比发现算法Phineas等等。这些算法在一定条件下发现了一些有意义的概念、定律和规则
。但它们普遍对复合函数学习能力不强，需要在搜索算法和启发式函数等方面加以改进，才能
对大量呈复合函数规律变化的数据进行令人满意的学习。近年来，人工智能在理论、方法和
实际应用上迅速发展，人们试图克服算法可适应性差的弱点，使其具有学习功能，能自动学
习知识，学习适应新的环境。
---- 2 BACON算法分析
---- BACON算法是运用人工智能技术从试验数据中寻找其规律性比较成功的一个算法，是Pat
Langly于1980年研制的。BACON算法的思想是程序反复地考察数据并使用精炼算子创造新项，
直到创造的这些项中有一个是常数时为止。于是一个概念就用“项＝常数”的形式表示出来
，其中项为经变量运算组合而形成的表达式。
---- 该算法运用的是数据驱动方法，这种方法使用的规则空间与假设空间是分开的。算法的
规则空间包括若干精炼算子，算法使用精炼算子修改假设，所谓精炼算子就是修改假设空间的
子程序，每个精炼算子以特定的方式修改假设空间，整个学习程序由多个精炼算子组成，程序
使用探索知识对提供的训练例进行分析，决定选用哪个精炼算子。
---- BACON算法中所采用的主要精炼算子如下：
---- 1)发现常数：
---- 当某一属性特征向量取某一值至少两次的时候，触发这个算子，该算子建立这个特征向量
等于常数的假设；
---- 2)具体化：
---- 当已经建立的假设同时间相矛盾时触发这一算子，它通过增加合取条件的形式把假设具
体化；
---- 3)斜率和截距的产生：
---- 当发现两个特征向量是线性相互依赖时触发这一算子，它是建立线性关系的斜率和截距
作为新项；
---- 4)积的产生：
---- 当发现两个特征向量以相反方向递增但又不线性依赖时触发该算子，并产生两向量的乘
积作为新项；
---- 5)商的产生：
---- 当发现两向量以相同方向递增但又不线性依赖时触发该算子，并产生两向量的商作为新
项；
---- 6)模n的项的产生：
---- 当发现两向量v1和v2在模某数n相等时触发该算子，并产生v2(mod n)作为新项。
---- BACON算法是用产生式语言OPS实现的。这个任务产生式算法的优点是，它允许人们写一
套小型的一般规律发现程序。这些程序在收集的数据上进行搜索，同时，这些数据仍存放在
工作存储器中。如果数据出现某种规律性，它就会触发某个算子。
---- 按着这种方式，只要关于属性值的某些一般化有效，BACON就增加一个预言其成分值的产
生式。算法还可以审查它的假说。当算法发现了反例时，如果一般化是在物体之间做的，就加
一些例外的限制，如果一般化是对时间做的，则可加上限或下限。事实上，一旦形成一个假设
就不放弃，虽然其形式可能是修改过的，它也总是把假设存入固定的产生式存储。
---- 总的来说，BACON算法是一个较为完善的机器学习算法。但是，BACON算法存在的缺陷也
是显而易见的，即自动学习的能力比较弱，十分强调人工干预的作用，需要用户指明数据之间
的相关性，甚至有时要指出公式的大概形式，才能进行正确的学习，基本上仍局限于一个再
发现算法，需要在自学习方面加以改进。
---- 3 基于深度优先的公式发现算法
---- 本算法的法基本思想是对某一变量取初等函数和另一变量的初等函数或原始数据进行线
形组合，选取逼近效果最好的少数几个初等函数作为进一步搜索的依据，直至确认已学习出
满足要求的公式或认为在给定的阈值条件下无法学习出来为止。例如有变量X1 和X2，在具体
学习时可以先固定X2，对X1进行原型的匹配，选出误差最小的几个原型，若这时最小误差已经
小于阈值，则认为学习成功，否则针对这几个选出的原型，固定X1，对X2进行原型的匹配，再
选出误差最小的几个原型，同时判断是否满足误差阈值，若满足则认为学习到结果，否则退
出学习过程，学习失败。
---- 启发式方法是求解人工智能问题的一个重要方法。一般的启发式方法是建立启发式函数
，用以引导搜索方向，以便用尽量少的搜索次数，从开始状态达到最终状态。把状态的改变连
接起来便成为搜索路径。由于一个状态的改变可以达到多个不同的状态，若把各种可能到达
的状态都展开它的搜索路径，这将形成一棵搜索树，搜索树如果按二叉树考虑，随着深度n
(状态连续改变数）的增加，树的结点数将迅速增加，若盲目进行搜索，搜索时间就以增加。
---- 智能问题的搜索时间是按指数时间执行的，为解决这种组合爆炸现象，人工智能中发展
了一种启发式搜索方法。在搜索过程中挖掘并使用与任务有关的信息以利于减少搜索，这一类
信息通常称为启发性的信息。利用启发信息的搜索过程叫做启发式搜索方法。本算法在执行
搜索的过程中，也隐含着组合爆炸现象，为解决这一问题，采用了启发式方法来实现搜索过程。
在启发式信息的探索中，以一般函数形式来描述：
---- 设对n个变量的观察数据的变化规律为：
---- 固定其它变量，如，只允许两个变量变化，则与之间呈一种线性关系。的原始数据与它
们的函数原型有着一种内在的联系。对某一变量取初等函数和另一变量的初等函数或原始数
据进行线性组合，即从原型库中选取逼近效果最好的少数几个初等函数作为进一步搜索直至
确认的函数原型。本算法的启发式函数形式为：。其线性逼近效果用来度量。
---- 本算法采用了原型搜索优化算法，对原型库中每个原型没有依次与实验数据库中的所有
数据进行匹配运算，在搜索匹配的过程中，能够避开那些显然不可能满足要求的原型，以减少
时间开支。原型搜索优化算法的过程是，在算法进行初始化时，对实验数据库进行一遍扫描
，发现一些数据对某些原型来说在该点没有定义，即该点为这些原型的间断点，则对这些原
型进行标记，在匹配原型时跳过被标记原型。例如，若为负数，则显然诸如一类的原型是不可
选的。通过这一算法，可以使执行效率得到显著提高。
---- 本算法首先针对、进行两次原型匹配，，如果拟合程度较好，即此时的误差小于阈值，
则认为能够学习出基本满足要求的公式，这时，输出结果公式和误差，并且描绘出其曲线。
如果拟合的结果偏差较大，则认为没有得到能够满足要求的结果公式。这时自动舍弃对匹配
的结果，只保留第一次对匹配的五个原型，并转入深度优先的树搜索过程。
---- 下面主要介绍一下生成深度优先搜索树的算法。
---- 该算法主要包括了四个模块：
---- 1) 判断是否得到结果，由此决定是否继续学习；
---- 2) 向更深一层搜索，求出误差小于父结点误差的所有原型，并把它们作为子结点加入到
树结构中去；
---- 3) 若某结点向下搜索时误差都在变大，那么认为它没有孩子结点，此时回溯，扩展搜索
树中那些还没有扩展的结点；
---- 4) 每次进入更深一层的搜索时，都要交换匹配的变量，以实现一次针对，一次针对进行
原型匹配。
---- 在科学试验或统计研究中，人们常常需要从一组测定的数据，例如N个点中去求得因变
量x和自变量y的一个近似表达式。这就是由给定的N个点(i=1,2,3…n)求数据拟合问题。根据
数据之间的关系给出它们之间的数学公式有:
---- 而对其中各个系数的确定常用的是最小二乘法，即使各点的误差平方和最小：
---- 对于如何选择使误差平方和最小，将对求偏微商，再使偏微商等于零，得到应满足的方
程。
---- 求得这组方程的解即得拟合公式。
---- 4 小结
---- 本算法与BACON算法相比，在学习能力上有所进步。首先是能进行两层学习，其次，还
可以有两种学习途径，分别是自动学习和人工学习。自动学习是计算机自己进行两层搜索，
不用人工干预。而人工学习可以由用户根据数据库中的数据及其曲线选择对X1匹配时所选用
的原型，即不用算法进行第一层的搜索，直接进入第二层的学习，可以大大提高学习的效率。
具备了修改误差阈值的功能，通过调整阈值可以控制学习的结果。
---- 我们认为，对本算法而言，还应该加强以下方面研究：
---- 1.在对搜索树进行深度优先搜索时，可以考虑一下控制策略的调整。比如本算法中要求
在向下搜索时误差一旦变大就停止该分支的搜索，这样有可能漏掉正确的分支，可以改进为
允许误差变大一次或两次，从而可以继续向下搜索一至两层，这样，发现公式的余地就会更
大一些。
---- 对原型库的扩充和管理。原型库是算法的核心组成部分，足够的原型是保证学习成功的
必要前提，算法应该具备对原型库的编辑、修改、增加、删除功能。
---- 3．学习规则的增加。侧重于规则库的建立和规则的使用。
---- 4．对多变量公式发现的研究。
---- 另外，还有必要结合当前国际上流行的Internet技术和数据仓库技术，进一步拓宽可视
化公式发现的研究领域。