基于深度优先的公式发现算法

《基于深度优先的公式发现算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基于深度优先的公式发现算法秦小虎杨波（后勤工程学院研究生队重庆400016）（总后科研所北京100071）----1引言----数据开采是从大型数据库或数据仓库中发现并提取隐藏在其中的信息的一种新技术,目的是帮助决策者寻找数据间潜在的关联,发现被忽略的要素,而这些信息对预测趋势和决策行为也许是十分有用的。数据开采技术能从DW中自动分析数据,进行归纳性推理,从中发掘出潜在的模式,或产生联想,建立新的业务模型,帮助决策者调整市场策略,做出正确的决策。数据开采表明,知识就隐藏在日常积累下来的大量数据之中,而仅靠复杂的算法和推理

2、并不能发现知识,数据才是知识的真正源泉。数据开采为AI的发展指出了一条新的发展道路。----机器学习是人工智能的一个重要分支。对机器学习的研究促进了人工智能的在理论方法和实际应用上的迅速发展。学习和解决问题是人类最重要的两个智能行为。机器学习是让计算机模拟和实现人类的学习、获取知识。机器学习也是计算机具有人工智能的重要标志。机器学习具有快速、可复制、自主性差、机械、学习方法单一等特点。由于机器不存在人类所具有的生理因素的限制，因此，机器可以“不知疲倦”地学习，而且，在对一些数理化的知识的学习上，机器也比人的速度要快得多。

3、而且，由于计算机程序易于复制，因此，计算机的学习是不会终止的，其所具有的知识也可以一直保留下来。但是，计算机的学习方法单一，只能根据有限的学习方法进行机械学习，本身不能创造方法，尤其是不具有人类学习所特有的“灵感思维”，这也是机器学习在目前来说尚不可克服的缺陷。所以，我们必须通过有效的搜索算法和启发式信息才有可能减少这个缺陷带来的影响。----在人工智能（AI）中，机器学习（ML）的早期研究至少可追溯到70年代初Gerwin的工作，其它著名的发现算法包括数学发现算法AM、规则发现算法Meta-Dendral、经验发现算法

4、BACON和类比发现算法Phineas等等。这些算法在一定条件下发现了一些有意义的概念、定律和规则。但它们普遍对复合函数学习能力不强，需要在搜索算法和启发式函数等方面加以改进，才能对大量呈复合函数规律变化的数据进行令人满意的学习。近年来，人工智能在理论、方法和实际应用上迅速发展，人们试图克服算法可适应性差的弱点，使其具有学习功能，能自动学习知识，学习适应新的环境。----2BACON算法分析----BACON算法是运用人工智能技术从试验数据中寻找其规律性比较成功的一个算法，是PatLangly于1980年研制的。BACO

5、N算法的思想是程序反复地考察数据并使用精炼算子创造新项，直到创造的这些项中有一个是常数时为止。于是一个概念就用“项＝常数”的形式表示出来，其中项为经变量运算组合而形成的表达式。----该算法运用的是数据驱动方法，这种方法使用的规则空间与假设空间是分开的。算法的规则空间包括若干精炼算子，算法使用精炼算子修改假设，所谓精炼算子就是修改假设空间的子程序，每个精炼算子以特定的方式修改假设空间，整个学习程序由多个精炼算子组成，程序使用探索知识对提供的训练例进行分析，决定选用哪个精炼算子。----BACON算法中所采用的主要精炼算子

6、如下：----1)发现常数：----当某一属性特征向量取某一值至少两次的时候，触发这个算子，该算子建立这个特征向量等于常数的假设；----2)具体化：----当已经建立的假设同时间相矛盾时触发这一算子，它通过增加合取条件的形式把假设具体化；----3)斜率和截距的产生：----当发现两个特征向量是线性相互依赖时触发这一算子，它是建立线性关系的斜率和截距作为新项；----4)积的产生：----当发现两个特征向量以相反方向递增但又不线性依赖时触发该算子，并产生两向量的乘积作为新项；----5)商的产生：----当发现两向量以

7、相同方向递增但又不线性依赖时触发该算子，并产生两向量的商作为新项；----6)模n的项的产生：----当发现两向量v1和v2在模某数n相等时触发该算子，并产生v2(modn)作为新项。----BACON算法是用产生式语言OPS实现的。这个任务产生式算法的优点是，它允许人们写一套小型的一般规律发现程序。这些程序在收集的数据上进行搜索，同时，这些数据仍存放在工作存储器中。如果数据出现某种规律性，它就会触发某个算子。----按着这种方式，只要关于属性值的某些一般化有效，BACON就增加一个预言其成分值的产生式。算法还可以审查它

8、的假说。当算法发现了反例时，如果一般化是在物体之间做的，就加一些例外的限制，如果一般化是对时间做的，则可加上限或下限。事实上，一旦形成一个假设就不放弃，虽然其形式可能是修改过的，它也总是把假设存入固定的产生式存储。----总的来说，BACON算法是一个较为完善的机器学习算法。但是，BACON算法存在的缺陷也是显而易见