（计算机系统结构专业论文）bp算法并行化及在数据挖掘中的应用研究.pdf

重庆大学硕士学位论文中文摘要 摘要 数据挖掘是帮助人们在海量数据中发现信息和知识的工具。近年来数据挖掘 技术成了商业智能的核心技术，被广泛应用到了诸多领域，引起了学术界极大的 关注。数据挖掘是一个决策支持过程，技术基础是人工智能。目前数据挖掘主要 利用人工智能中的一些的算法和技术，包括人工神经网络技术等来进行预测、模 式识别、分类和聚类分析。本文主要针对神经网络作为数据挖掘的一种手段，在 商业行为趋势预测方面的应用研究。 b p ( b a c kp r o p a g a t i o n ) 算法，即误差反传训练算法，以箕良好的非线性映射逼 近能力和泛化能力以及易实现性成为人工神经网络应用最广泛的训练算法。但是 b p 算法也有其明显的缺陷，即训练速度馒、容易陷入局部极值等。通过反复的实 验研究和分析发现，通常为了避免初始权值过大，导致训练伊始就使网络处于s 型函数的饱和区，使训练陷入局部极小，在选取初始权值的时候，通常选取较小 随机数。如果选取的权值范围距离目标极值区域很远，搜索空间越大，目标极值 区域越窄，搜索时间就越长，训练速度就越缓慢。针对这种情况，本文提出了首 先通过不等量划分权值搜索空间获取全局最小极值区域，在此基础上均衡分配训 练样本集进行并行训练的二次并行搜索策略，实验证明这种新的并行算法能在迅 速找到全局最小的基础上大大提高收敛速度，得到优于一般并行算法的加速比。 此并行算法实现简单有效，能更好地应用于现实问题。 本文选用通过商用网络连接起来的p c 机，以及并行虚拟机p v m 和分布式操 作系统l i n u x ，共同构成了一个机群系统作为并行计算平台。在并行程序的模型 上选用了m a s t e r s l a v e 模型。算法并行化方式采用了将训练数据平均分配到各节点 机的数据并行方式。 最后，讨论了b p 算法在数据挖掘中的应用。将此策略应用于医药物流系统的 销售预测，建立了基于并行b p 算法的物流销售预测模型。本文详细地讨论了销售 预测模型的样本的选择和预处理方法、网络拓扑结构的选定，如输入输出层以及 隐含层数和隐含层节点数的选择、网络参数的选择等。最后实现了一个可视化的 预测系统，可以在此基础上方便的选择不同训练集重新训练网络，并将训练好的 网络用于真实的销售趋势预测，取得了令人满意的效果。 关键词：人工神经网络，b p 算法，数据挖掘，并行算法，销售预测 重庆大学硕士学位论文 英文摘要 a b s t r a c t d a t am i n i n g t e c h n o l o g y i su s e dt o h e l pp e o p l ef i n d i n g t h ei n f o r m a t i o na n d k n o w l e d g e i nt h ed a t a i th a sb e c o m et h ec o r et e c h n o l o g yo f t h ei n t e l l i g e n c ec o m m e r c e i th a sb e e nw i d e l yu s e di nm a n ya r e a sa n dd r a w nt h ea t t e n t i o no ft h ew h o l ea c a d e m e s o m ea l g o r i t h m sa n dt e c h n i q u e so fa r t i f i c i a li n t e l l i g e n c e ，i n c l u d i n gn e u r a ln e t w o r k s ， h a v eb e e n a p p l i e d i nd a t am i n i n gt od op r e d i c t i o n , p a r e m r e c o g n i t i o n ，c l a s s i f i c a t i o na n d c l u s t e r i n g o n ei m p o r t a n ta p p l i c a t i o no f n e u r a ln e t w o r k i nd a t am i n i n gi ss a l e st r e n dp r e d i c t i o n b p ( b a c kp r o p a g a t i o n ) a l g o r i t h m i st h em o s tp o p u l a r t r a i n i n ga l g o r i t h m i n a p p l i c a t i o n sf o ri t sn o n - l i n e a rm a p p i n ga p p r o a c hc a p a b i l i t ya n dr o b u s t n e s s h o w e v e r , i t i sk n o w nt oh a v es o m ed e f e c t s ，s u c ha s c o n v e r g i n gs l o w l ya n di m m e r s i n gi n l o c a l v i b r a t i o nf r e q u e n t l y , g e n e r a l l y , w eo f t e nc h o o s es m a l lr a n d o mi n i t i a lw e i g h t st ov o i d t r a i n i n gp r o c e s si m m e r s e i nl o c a lm i n i m u m i fi ti sf a rf r o mc h o s e nr a n g eo f w e i g h t s t o g o a la r e a , t h es e a r c hs p a c ei sw i d e r , g o a la r e ai sn a r r o w e r , s e a r c ht i m ei sl o n g e ra n d t r a i n i n gs p e e di ss l o w e r t os o l v et h i sp r o b l e m ，t h ep a p e rp r o p o s e das o l u t i o nn a m e d t w ot i m e sp a r a l l e ls e a r c hs t r a t e g y , t h a ti s ，o b t a i n i n gg l o b a lm i n i m u ma r e ab yd i v i d i n g w e i g h ts p a c eu n e q u a l l ya tf i r s ta n dt h e nt r a i n i n gn e t w o r ku s i n gd a t ap a r a l l e l i s m ，t h e e x p e r i m e n tr e s u l t ss h o wt h a tt h es t r a t e g yr e a c h e sg l o b a lm i n i n l u n ls o o na n dc o n v e r g e s 砒m g hr a t e e s p e c i a l l yt oal a r g et r a i n i n gs a m p l e s t h eh a r d w a r e p l a t f o r m i sp cc o n n e c t e dw i t hl a n t h es o r w a r c p l a t f o r mi sp v m a n dl i n u x t h e yc o n s t r u c tt h ew h o l ep c - c l u s t e rs y s t e m t h ep a r a l l e lp r o g r a mm o d e l i sm a s t e r s l a v em o d e l t h e a l g o r i t h ma s s i g n d a t as e tt oe a c hn o d er e a l i z e st h e d a t a - p a r a l l e l t h ea p p l i c a t i o no fb p a l g o r i t h mi n d a t am i n i n gi sd i s c u s s e di nt h i sp a p e r t h e s t r a t e g ym e n t i o n e di sa p p l i e dt os a l e sp r e d i c t i o no fm e d i c i n el o g i s t i c ss y s t e ma n da s a l e sp r e d i c t i o nm o d e lb a s e do np a r a l l e la l g o r i t h mi se s t a b l i s h e d h o wt oc h o o s ea n d p r e p r o c e s st r a i n i n gs e ta n dh o w t os e l e c tn e t w o r k t o p o l o g y i sp r o p o s e di nd e t a i li nt h i s p a p e n a tl a s t ，av i s u a lp r e d i c t i o ns y s t e mi sr e a l i z e dt oa c h i e v e p r e d i c t i o nr e s u l t , w h i c h m a k e s p r e d i c t i o nw o r k se a s y k e y w o r d s ：n e u r a ln e t w o r k s ，b p a l g o r i t h m ，d a t am i n i n g , p a r a l l e la l g o r i t h m ， s a i e sp r e d i c t i o n i i 重庆大学硕士学位论文 1 绪论 1绪论 1 1 论文的研究背景及选题意义 在过去的若干年中，商业、政府和科学数据库的急剧增长和存储设备的不断 升级，给我们积累了大量的历史数据。要想使数据成为一个公司的资源，只有充 分利用它为公司自身的业务决策和战略发展服务才行，否则大量的数据可能成为 包袱，甚至成为垃圾。人们对于数据的应用已经从单纯的数据本身发展到对大量 数据内所包含的隐含模式的索取。数据量的单纯增加并不能使人们获得有用的信 息，正如j o h nn a i s b e t t 所说”人类正被数据淹没，而人类却饥渴于知识”。这里 所指的4 知识”就是数据中隐含的信息。 数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、随机 的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知 识的过程“。数据挖掘的对象可以是结构化的，如关系数据库中的数据，也可以 是半结构化的，如文本、图形、图象数据，甚至是分布在网络上的异构型数据。 发现知识的方法可以是数学的，也可以是非数学的；可以是演绎的，也可以是归 纳的”1 。挖掘出的知识可以被用于信息管理、查询优化、决策支持、过程控制等， 还可以用于自身的维护“”。因此，数据挖掘是一门很广义的交叉学科，涉及人工 智能技术、统计技术与数据库技术等多种技术。它汇聚了不同领域的研究者，尤 其是数据库、人工智能、数理统计、可视化、并行计算等方面的学者和工程技术 人员。 数据挖掘是一个决策支持过程，技术基础是人工智能。人工智能是通过模拟 人类宏观外观的思维行为，从而高效率地解决现实世界的问题。目前数据挖掘主 要利用人工智能中的一些的算法和技术，包括人工神经网络技术等来进行预测、 模式识别、分类和聚类分析“1 。本文主要针对神经网络作为数据挖掘的一种手段， 在商业行为趋势预测方面的应用研究。 由于常用的预测方法如指数平滑、曲线拟台等都存在一个共同的局限性：就 是预先知道被控对象的数学模型，但实际上许多对象具有复杂的不确定性和时变 性，此外，还具有复杂的非线性，要进行有效的实时预测就非常困难。人工神经 网络有表示任意非线性关系和学习等能力，给解决这类问题提供了新思想和新方 法。 在人工神经网络的训练算法中，应用最广泛的是b p ( b a c kp r o p a g a t i 。n ) 算法， 据统计，约有8 0 的神经网络训练算法采用b p 算法，即误差反传训练算法。b p 算 法以其良好的非线性映射逼近能力和泛化能力以及易实现性得到了人们的青睐。 重庆大学硕士学位论文 i 绪论 但是，它也有非常明显的缺点，如：( 1 ) 网络结构设计困难，特别是隐含层数和隐 层节点数难以确定。( 2 ) 9 jj 练易陷入瘫痪，收敛速度较慢。( 3 ) 易形成局部极值。这 些缺点极大的影响了b p 算法的推广应用。为此，许多学者和科学工作者对b p 算 法本身进行了各种改进，包括基于梯度下降和基于数值优化的算法。这些改进算 法在很大程度上提高了b p 算法的性能，使其能更好地应用。而b p 算法的改进也 成为了一个研究的热点。在数据挖掘的应用中，要找出蕴涵在数据中的潜在规律， 就需要对大量历史数据进行训练，如此在单机上处理大量数据的b p 算法就不满足 实际应用的要求。我的论文是在一种性能相对较优的改进算法：r p r o p ( r e s i l i e n t b a e k p r o p a g a t i o n ) ，即弹性b p 算法的基础上对其进行并行化，提出了二次并行搜索 策略，给出了并行算法。此策略可以很大程度上避免算法训练过程陷入局部极值， 并极大的提高算法的收敛速度，以此提高预测速度和精度，使其实用性更强。因 此，本课题具有实用价值和理论意义。 1 。2 国内外现状综述 人工神经网络的理论研究是一门新兴的边缘和交叉学科1 。它有表示任意非 线性关系和学习等能力，给解决很多具有复杂的不确定性和时变性的实际问题提 供了新思想和新方法。它之所以能得到广泛的应用，是因为它有以下一些特性。3 ： ( 1 ) 通过非线性映射，学习系统的特性具有近似地表示任意非线性函数及其逆 的能力。 ( 2 ) 通过离线和在线两方面的权重自适应提供给不确定系统自适应和自学习。 ( 3 ) 可提供大规模动力学系统允许快速处理的并行分布处理结构。 ( 4 ) 提供鲁棒性强的结构，因为网络自身有容错性和联想功能。 ( 5 ) 信息被转换成网络内部的表示，这种表示允许定性和定量信号两者的数据 融合。 训练神经网络是一种最优化问题，目标是通过输入输出样本对 ( 工1 ，f 1 ) ，( x # ，) ， ”，t “) ) 适当调整网络权值向量w ，使误差函数e ( w ) 最小。 目前已发展了多种迭代算法来计算网络的权值w ，一类是a d h o c 技术，例如， b p 算法，有m o m e n t u m 的变学习率b p 算法1 ，学习速率可变的b p 算法“3 3 侧和弹 性b p 算法( r p r o p ) 。1 等n 町。b p 算法的计算复杂度主要是由计算偏导数引起的， 只有0 ( n ) ，但是，这种基于梯度的下降方法只是线性收敛，速度很慢，另一种具 有同样复杂度的启发式算法是有m o m e n t u m 梯度算法，可看作是共轭梯度法的近似。 但是，这是一个高度启发式的过程，必须谨慎地选择学习率和m o m e n t u m 参数“。 另一类是利用标准的数值优化技术，例如共轭梯度法、牛顿法和l m 法等n ”。牛顿 法具有良好的局部收敛性质。当接近个极小点时它是平方收敛的，在远离解的 2 重庆大学硕士学位论文l 绪论 地方则需要做些修正。l e v e n b e r g m a r q u a r d t ( 简称l m ) 算法 5 儿3 是梯度下降法 与高斯一牛顿法的结合。它即有高斯一牛顿法的局部收敛性，又具有梯度下降法的 全局特性“。以上这些方法都不同程度存在局部极小的问题。近年来，随着模拟 退火算法，遗传算法和混沌算法的兴起，有人将这些算法与b p 网络结合，利用它 们的全局特性优化神经网络算法，取得了可喜的结论。文献 6 1 8 儿1 9 2 0 2 6 4 1 对各种b p 网络改进算法的性能对比和优缺点做了比较 详尽的描述。文献 1 2 1 7 各提出了一种据说性能大幅提高的新方法。 b p 算法是一种常用的训练方法。它的主要思想是把学习过程分为两个阶段： 第一阶段( 正向传播阶段) ，给出输入信息通过输入层经隐含层逐层处理并计算每 个单元的实际输出值：第二阶段( 反向过程) ，若在输出层未能得到期望的输出值， 则逐层递归地计算实际输出与期望输出之差( 即误差) ，以便根据此差调节权值， 具体些说，就是可对每一个权重计算出接收单元的误差值与发送单元的激活值的 积。因为这个积和误差对权重的( 负) 微商成正比( 又称梯度下降算法) ，把它称 作权重误差微商。权重的实际改变可由权重误差微商一个模式一个模式地计算出 来，即他们可以在这组模式集上进行累加1 。 1 9 9 3 年德国m a r t i nr i e d m i l l e r 和h e i n r i c hb r a u n 在论文 8 中提出了 r e s i l i e n tb a c k p r o p a g a t i o n 方法( r p r o p 弹性b p 算法) ，这是一种在多层感知器 中实现有指导批处理学习的局部自适应学习方案。这种方法的原理打算消除偏导 数的大小有害的影响权步，因此，惟有导数的符号被认为表示权更新的方向。权 改变的大小仅仅由权专门的“更新值”础确定”3 。 文献 6 儿1 8 1 9 2 0 2 6 3 8 4 1 通过对各种b p 改进算法的对比研究，均 不约而同的充分肯定了r p r o p 在收敛速度、稳定性、鲁棒性等较其他大多数算法 有突出的优势，文献 4 4 3 9 在原始r p r o p 的基础上给出了改进的r p r o p 算法并 给出了详细的实验比较，证明有性能上的提高。 b p 算法的运算量大，收敛速度缓慢是影响该算法应用推广的一个重要原因， 也是现在人工神经网络领域研究的一个重点。特别是训练样本较多时。无法满足 实时运算的要求，为此可利用以局域网为依托的机群进行计算，从而有效地加快 其计算速度，增强其实用性o “。对b p 算法进行并行化，可以有多种方法：按横向 分配神经元到各处理器；按层分配神经元到各处理器；按训练集分配等。减少通 信是提高并行效率的最有效途径，而理论和实践也证明了将训练集均衡地分配到 各处理器上进行计算，其效率最高”“。文献 2 8 3 4 儿3 7 研究表明，对b p 算法的 并行化比较适合使用主从模式。这种算法的特点在于它有一个控制程序称为主进 程( m a s t e r ) 和若干从进程( s l a v e ) ，主进程运行于一台计算机上，负责从进程的生 成、初始化、计算任务的分配、收集并显示结果，而其余从进程运行于其他计算 重庆大学硕士学位论文 1 绪论 机上，他们进行实际计算，执同的程序，但处理的数据不同，且均来自于主进程， 同时计算的结果也直接送回主进程，面不是给其他的从进程继续进行处理，所以 从进程之间没有通信，是完全独立的。文献e 2 8 卜 3 5 ， 3 7 给出了具体的标准b p 的并行算法，并证明在大数据集的情况下并行加速比达到满意效果。 b p 网络的隐层及隐层节点个数难以确定，关于这方面，文献 1 1 2 1 儿3 8 有 相应的记载。对于多层神经元网络来讲，首先确定选用几层隐含层。1 9 8 8 年c y b e n k o 指出，当各节点均采用s 型函数时，一个隐含层就足以实现任意判决分类问题， 两个隐含层则足以表示输入图形的任意输出函数o 。目前人们认为二进制分类或 判决边界问题，一个隐含层就够了。但是，如果要求输出是输入的任意连续函数， 那就要用两个隐含层或者采用不同的激活函数。有时即使是连续输出的情况，用 一个隐含层也可以满足要求，这取决于问题的性质。在线性可分的情况下，隐含 层是不需要的1 。在隐层神经元数的确定上，文献 3 8 罗列了八条各国研究者得 出的经验公式，其中，有人提出隐层神经元数应等于输入、输出神经元之和的一 半或者再开方的所谓“大拇指规则”( r u l e so ft h u m b ) ，也有人赞成从输入层到 输出层节点数不断减少的“金字塔规则”( g e o m e t r i cp y r a m i dr u l e ) ，但是，这 些都证据不足。目前最基本的是实验试凑法，即用同样本对具有不同隐节点数 的网络进行训练，直到权值不再变化，网络稳定为止，然后，依据测试误差最小， 确定网络的隐节点数。显然，这种方法比较费时。“。 目前，人工神经网络特别是b p 网络已得到了日益广泛的研究和应用，它的广 阔前景在于其良好的预测性和实用性，其发展潜力巨大。基于神经网络的预测方 式是神经网络近几年形成的一个分支，正得到快速发展。9 0 年代中期，美国 f r o n t i e rf i n a n c i a l 公司利用神经网络来对股票市场进行预测，再由相应的专家 给出建议等。在国内也有相似的应用，如文献 2 2 利用b p 网络进行股市预测，重 点对利用各种不同网络结构和网络参数所得预测结果进行分析，提出了综合股票 历史价格和其他经济因素的精确预测方法。澳大利亚学者s h a m s u d d i na h m e d 和 j a m e sc r o s s 在文献 9 中利用神经网络预测旅馆住宿消费额。文献 2 3 在管理信 息系统( m i s ) 中集成基于b p 网络的专家系统，用以解决复杂的非线性预测问题和 提高m i s 智能化水平。文献 2 5 把附加动量项和自适应算法相结合而形成的快速 b p 神经网络算法用于对城市可持续发展综合评价，取得了较好的效果。 1 3 论文研究的内容及组织 本论文研究的内容有以下几个方面： ( 1 ) 训练易陷入局部极值和收敛速度缓慢是b p 神经网络的不足之处，通过反 复的实验比较，认为可以通过将算法并行化来提高算法执行的效率，传统的并行 4 重庆大学硕士学位论文1 绪论 方法是基于标准b p 算法，本论文在弹性b p 算法的高效基础上并行，并突破原有 的只将算法本身并行化的方法，另辟奚径，提出先并行找出搜索空间的最小极值 区域，在此基础上再进行算法并行化的二次并行搜索策略，从而在很大程度克服 b p 算法的两个缺陷。 ( 2 ) 算法选择运行的并行平台尽量使用现有的商品化部件。从而降低用户的 投资成本，使算法具有更高的实用性。算法运行的软件平台应该采用流行的并行 计算软件，从而使程序具有更高的可移植性。算法在并行方式上，尽量多的采用 数据并行的方法，从而使并行程序获得更高的加速比。在算法的并行化过程中， 选择适合并行平台的粒度，使并行程序的执行获得较好的负载平衡。在结点间通 信的数据结构上，选用简单的数据结构，提高结点间通信效率。 ( 3 ) 采用不同数据集对算法进行测试。改变结点机的数目，得到不同的程序 执行时间，计算出并行算法实际执行的加速比。从实际实行效果上对并行算法进 行评价。 ( 4 ) 将此算法用于一个实际的应用，本文选择了医药物流系统的销售预测， 利用实际数据来验证本文提出的销售预测模型的效果。 重庆大学硕士学位论文 2 数据挖掘中的人工神经网络技术 2 数据挖掘中的人工神经网络技术 2 1 数据挖掘技术简介 2 1 1 数据挖掘的定义 数据挖掘，英文是d a t am i n i n g 。目前对数据挖掘技术一种比较公认的定义是 w j f r a w l e y ，g p i a t e t s k y - s h a p i r o 等人提出的1 ：数据挖掘，就是从大型数 据库的数据中提取人们感兴趣的知识。这些知识是隐含的、事先未知的潜在有用 信息，提取的知识表示为概念( c o n c e p t s ) 、规则( r u l e s ) 、规律( r e g u l a r i t i e s ) 等形式。这种定义把数据挖掘的对象定义为数据库。而更广义的说法是“”：数据 挖掘意味着在一些事实或观察数据的集合中寻找模式的决策支持过程。模式是一 个用语言l 来表示的一个表达式e ，它可以用来描述数据集合f 中数据的特性，e 所描述的数据是集合f 的一个子集f e 。e 作为一个模式要求它比列举数据子集f e 中所有元素的描述方法简单。数据挖掘的对象不仅是数据库，也可以是文件系统， 或其它任何组织在一起的数据集合，例如w w w 信息资源。目前发展的热点是数据 挖掘技术和数据仓库技术的结合。数据仓库中包含了大量历史数据，这些数据是 经过了规范化并且面向主题组织的，对数据仓库中数据进行数据挖掘是最容易的。 2 1 2 数据挖掘的任务及相关技术 数据挖掘与知识发现是一个以数据库、人工智能、数理统计、可视化四大支 柱技术为基础，多学科交叉、渗透、融合形成的新的交叉学科，其研究内容十分 广泛。数据挖掘作为d m k d 的核心部分，目前被研究得最多，存在很多数据挖掘 方法或算法，因此有必要对这些方法进行分门别类。描述或说明一个算法涉及三 个部分：输入、输出和处理过程。数据挖掘算法的输入是数据库，算法的输出是 要发现的知识或模式，算法的处理过程则涉及具体的搜索方法。从算法的输入、 输出和处理过程三个角度分，可以确定这样几种分类标准：挖掘对象、挖掘任务、 挖掘方法。 根据挖掘对象分，有如下若干种数据库或数据源：关系数据库、面向对象数 据库、空间数据库、时态数据库、文本数据源、多媒体数据库、异质数据库、历 史( 1 e g a c y ) 数据库，以及万维网( w e b ) 。 根据挖掘方法分，可粗分为：统计方法、机器学习方法、神经网络方法和数 据库方法。统计方法可细分为：回归分析、判别分析、聚类分析、探索性分析等。 机器学习可细分为：归纳学习方法、基于范例学习、遗传算法等。神经网络方法 可细分为：前向 申经髓络、自组织神经髓络等。数据库方法主要是多维数据分丰厅 6 重庆大学硕士学位论文 2 数据挖掘中的人工神经网络技术 或o l a p 方法，另外还有面向属性的归纳方法。 根据挖掘任务分，数据挖掘主要发现以下五类知识： ( 1 1 广义型知识( g e n e r a l i z a t i o n ) ： 根据数据的微观特性发现其表征的、带有普遍性的、较高层次概念的、中观 或宏观的知识。 ( 2 ) 分类型知识( c l a s s i f i c a t i o n & c l u s t e r i n g ) ： 反映同类事物共同性质的特征型知识和不同事物之间差异型特征知识。用于 反映数据的汇聚模式或根据对象的属性区分其所属类别。 ( 3 ) 关联型知识( a s s o c i a t i o n ) ： 反映一个事件和其它事件之间依赖或关联的知识，又称依赖( d e p e n d e n c y ) 关 系。这类知识可用于数据库中的归一化，查询优化等。 ( 4 ) 偏差型知识( d e v i a t i o n ) ： 通过分析标准类以外的特例，数据聚类外的离群值，实际观测值和系统预测 值间的显著差别，来对差异和极端特例进行描述。 ( 5 ) 预测型知识( p r e d i c t i o n ) ： 通过时间序列型数据，由历史的和当前的数据去预测未来的情况。它实际上 是一种以时间为关键属性的关联知识。 2 1 ，3 数据挖掘的常用算法 数据挖掘的技术基础是人工智能，它利用了人工智能中一些已经成熟的算法 和技术，例如：人工神经网络( n e u r a ln e t w o r k ) 、遗传算法( g e n e t i ca l g o r i t h m s ) 、 决策树( d e c i s i o nt r e e s ) 、邻近搜索方法( n e a r e s tn e i g h b o rm e t h o d ) 、规则推理 ( r u l ei n d u c t i o n ) 、模糊逻辑( f u z z yl o g i c ) 等，但问题的复杂度和难度却比人工 智能降低了许多，下面是数据挖掘技术中的常用算法： ( 1 ) 人工神经网络。人工神经元网络方法模拟人脑神经元结构，以m p 模型和 h e b b 学习规则为基础，一般分为三种网络模型o ： 前馈型网络。一般前馈型网络无反馈的特征，这类网络能够串联地连接起 来以建立多层网络，在这样的网络中，一层的输出是下一层的输入。输入输出节 点可与外界相联，可直接受外界环境的影响，所以可称为可见层，而其中层间与 外间无直接联系，所以称为隐含层。节点有输入、计算单元和输出三类。每一计 算单元可以有任意个输入但只有一个输出，其输出可以耦合到任意多个其他节点 的输入。两层的前馈网络只有单层计算单元，这实际上就是网络最简单的形式一 一感知器。前馈型网络以感知器、反向传播模型、函数型网络为代表，可用于预 测、模式识别等方面。 反馈型网络。反馈型网络所有节点都是计算单元，同时既可接受输入，又 重庆大学硕士学位论文2 数据挖掘中的人工神经网络技术 可向外界输出。通过网络神经元状态的变迁而最终稳定于某一状态，从而得到联 想存储或者神经计算的结果。它以离散型h o p f i e l d 神经元网络和连续模型为代表， 分别用于联想记忆和优化计算。 自组织网络。它以a r t 模型、k o h o l o n 模型为代表，用于聚类分析等方面。 人工神经网络的知识体现在网络连接的权值上，是一个分布式矩阵结构。起 学习体现在网络权值的逐步计算上。 ( 2 ) 遗传算法。 遗传算法是模拟生物进化过程的算法，由三个基本算予组成。： 繁殖( 选择) ，即从一个1 日群体( 父代) 选出一个生命力强的个体，产生新的 种群( 后代) 的过程。 交叉( 重组) ，即选择两个不同个体( 染色体) 的部分( 基因) 进行交换，形成 新个体的过程。 变异( 突变) ，即对某些个体的某些基因进行变异( o 变1 、1 变0 ) ，形成新 个体的过程。 这种遗传算法可起到优良后代的作用。这些后代需满足适应值，经过若干代 的遗传，将得到满足要求的后代( 即问题的解) 。遗传算法已在优化计算和分类机 器学习方面发挥了显著作用。 ( 3 ) 决策树。决策树是通过一系列规则对数据进行分类的过程。采用决策树， 可将数据规则可视化，也不需要长时间的构造过程，输出结果容易理解，精度较 高，因此决策树在知识发现系统中应用较广。然而，采用决策树方法也有其缺点。 决策树方法很难基于多个变量组合发现规则。不同决策树分支之间的分裂也不平 滑。 ( 4 ) 公式发现。即在工程和科学数据库( 由实验数据组成) 中对若干数据项( 变 量) 进行一定的数学运算，求得相应的数学公式。 ( 5 ) 统计分析方法。利用统计学中的数学原理对数据库进行分析，有如下方 法1 6 “： 相关分析和回归分析。相关分析是用相关技术来度量变量间的相关程度。 回归分析是用数学方程来表示变量间的数量关系，方法有线性回归和非线性回归。 差异分析。从样本统计量的值得出的差异来确定总体参数之间是否存在差 异( 假设检验) 。典型的方法为方差分析，它是通过分析实验数据中不同来源的变 异对总体变异的贡献大小，从而确定实验中的可控因素( 自变量) 是否对实验结果 ( 因变量) 有重要的影响。 重庆大学硕士学位论文 2 数据挖掘中的人工神经网络技术 因子分析。它是用较少的综合变量来表达多个观察变量，根据相关性大小 把变量分组，使得同组变量之间相关性较高，不同变量阊的相关较低。 ( 6 ) 其他技术”“。 模糊论方法。利用模糊集合论对实际问题进行模糊评判、模糊决策、模糊 模式识别和模糊聚类分析。由于模糊性是客观存在的，而且系统的复杂性越高， 对它的精确化能力便越低，也就意味着模糊性越强，这就是z a d e h 总结出来的互 克性原理。以上提到的模糊方法都取得了较好的效果。 可视化技术。可视化数据分析技术拓宽了传统的图表功能，使用户对数据 的剖析更清楚。例如把数据库中多维的数据变成多种图形，这对揭示数据中的状 况、内在本质及其规律性都起到了很强的作用。 以上的方法各有千秋，总的来说，应该根据不同的问题环境和应用层面来选 择合适的方法，并且灵活应用来解决数据挖掘中遇到的难题。 2 1 4 数据挖掘的应用 目前，数据挖掘的应用领域包括以下八个方面，而每个领域又都有自己的应 用领域和应用背景。1 ( 1 ) 金融。金融事务需要收集和处理大量的数据，通过对这些数据进行分析， 发现其数据模式及特征，然后可能发现某个客户、消费群体或组织的金融和商业 兴趣，也可观察金融市场的变化趋势。数据挖掘在金融领域的应用广泛，包括数 据清理、金融市场分析预测、帐户分类、信用评估等。 ( 2 ) 医疗保健。医疗保健业有大量的数据需要处理，但这个行业的数据由不 同的信息管理系统管理，数据以不同的格式保存，从总体看，数据是无组织的。 在这个行业中，数据挖掘的关键任务是进行数据清理、预测医疗保健的费用。例 如g t e 实验室开发的k e f i r ，它能进行多维分析，用于分析g t e 的医疗保健数据， 对比数据和预测数据，在定量范围内解释偏差，生成超文本报表。3 ( 3 ) 市场业。市场业应用数据挖掘技术进行市场定位、消费者分析、辅助制 定市场营销策略等。 ( 4 ) 零售业。零售业是最早运用数据挖掘技术的行业。目前，主要运用于销 售预测、库存需求、零售点的选择、价格分析等。 ( 5 ) 制造业。制造业应用数据挖掘技术进行零部件故障诊断、资源优化、生 产过程分析等。 ( 6 ) 司法。数据挖掘也可应用于案件调查、诈骗检测、犯罪行为分析等方面， 这些都可以给司法工作带来巨大的利益。 ( 7 ) 工程和科学。在信息量极为庞大的天文、气象、生物技术等领域中，所 获得的大量实验和观察数据用靠传统的数据分析工具难以应付，因此对功能强大 9 重庆大学硕士学位论文 2 数据挖掘中的人工神经网络技术 的智能化自动分析工具要求迫切，这种需求推动了d m 技术在科学研究领域的应用 发展，目前已获得了一些重要的研究成果，例如：j e tp r o p u l s i o n 实验室利用决 策树方法对上百万天体数据进行分析，帮助天文学家发现了1 6 个星的星体，效果 要比人工更快，更准确。 ( 8 ) 保险业。对受险人员的分类将有助于确定适当的保险金额度。通过数据 挖掘可以得到对不同行业、不同年龄段、不同社会层次的人，他们的险金应该如 何确定。另外，还可进行险种关联分析，分析购买了某种保险的人是否又同时购 买另种保险，也可预测什么样的顾客将会购买新险种。 2 2 数据挖掘中人工神经网络的数学模型 2 ，2 1 神经网络的定义 人工神经网络的基本单位是神经元，人工神经元的结构模型如图21 所示。 而 x 2 “ 吲2 1 神经元的结构模型 f i 9 2 1 其中3 c i 工z ，为输入信号，毪为神经元内部状态，g 为阈值，k 为越，到“ 连接的权值，暑表示外部输入信号( 在某些情况下，它可以控制神经元虬，使虬可 以保持在某一状态) ，厂( ) 为激发函数，y i 为输出，上述模型可以描述为： q = x j + j f 只( 2 1 ) j “，。亭p 。) ( 2 2 ) ，_ h ( u ，) = 厂( 盯，) = ，( _ + 一只)( 2 3 ) f = h x g ( 2 4 ) 当享孛经元没有内部状态时，可令只= “i ，厂( f ) = 亭( ) 。通常的情况是没有。i 鼢。 l o 重庆大学硕士学位论文 2 数据挖掘中的人工神经网络技术 此时，每一个神经元的输入接受前一级神经元的输出，因此，对神经元f 的总作用 盯，为所有i 的输出只为其当前状态仃，的函数。 上面都是针对稳定状态来说的，如果考虑到反映时间，那么必须用微分方程 来表示 申经元的状态变化，在最简单的情况下，以下的式子成立 r 等竹，= _ ( f ) 一p 。 ( 2 5 ) j y 。( f ) = ，( 盯i ( f ) ) ( 2 6 ) 注意到在最简单的情况下，神经元的状态与输入成比例，而且内某一个初态 衰减。 般来说，人工神经网络可以定义为啪1 ：人工神经网络是生理学上的真实人 脑神经网络的结构和功能，以及若干基本特征的某种理论抽象、简化和模拟而构 成的种信息处理系统。从系统的观点看，人工神经网络是由大量神经元通过极 其丰富和完善的联接而构成的自适应非线性动态系统。由于神经元之间有着不同 的连接方式。所以组成不同结构形态的神经网络系统是可能的。1 现在的人工神 经元网络模型只是生物神经系统的一种高度简化后的近似。它是用大量的简单神 经元广泛互连成的一种计算结构，属于自适应非线性动力学系统，它具有学习、 记忆、计算和各种智能处理功能。它在不同程度和层次上模仿人脑神经系统的结 构及信息处理、存储和检索等功能。 2 2 2 神经网络在数据挖掘中的常用模型 目前神经网络已有4 0 多种，按网络结构可分为前馈型、反馈型和自组织网络。 按网络性能可分为连续性和离散性、确定性和随机性网络。按学习方式可分为有 导师( 指导) 和无导师( 自组织学习包括在内) 学习。按突触连接的性质分为一阶线 性关联与高阶非线性关联网络。 ( 1 ) 前馈型网络 考察一个接受n 个输入的州个神经元构成的基本的前馈型网络结构，它的输入 和输出向量分别表示如下”1 彳= k ，z ：，r y = 【y 。班，y ，】r ( 2 7 ) 权值是把第f 个神经元和第，输入连接起来。权的第1 、2 个下标分别表示 目标和源节点的标记，丁表示转置。对第i 个神经元的激活值，则能够写成为 n e t ，= 嘞。 i = 1 ，2 ，m ( 2 8 ) j = l 重庆大学硕士学位论文2 数据挖掘中的人工神经网络技术 包含有激活函数f ( n e t ，) ，i = 1 , 2 ，m 的非线性变换完成对x 的处理，对随络中 m 个神经元的每一个逐个进行变换，这种变换用下式表示了强非线性映射 y 。= ( 形。x )f = 1 , 2 ，7 1( 2 9 ) 其中权向量彬包含引向第f 个输出节点的所有权并把它定义为 = w f 。，1 4 。，1 r( 2 1 0 ) 引入非线性算子i ，由网络实现的输入空间x 映射到输出空间y 能够表达成 为以下形式 y = r w x 】( 2 i 1 ) r ( ) = ，( 0 ： o 0 厂( ) ： j o 0 0 ： ，( 一) ( 2 1 2 ) 其中形是权矩阵亦称为联接矩阵。在矩阵算子r 的对角线上的非线性激活函 数必) 对每个神经元的激活值n e t ，按分量逐个进行操作，每个激活值顺序地输入 和各自权向量的标量积。 输入和输出向量x 和r 常常分别称作为输入和输出模式，因为在输入x 和输 出y 之间不包含延时，所以正像式( 2 1 1 ) 所表示的那样，输入模式映射成为输出模 式具有前馈和瞬时类型，那么我们以含有时间f 的显式重新写式( 2 11 ) 为。1 ( 2 1 3 ) 虽然前馈型网络没有明显的反馈连接，当z ( f ) 被映射成为r ( f ) 时，输出常常 与教师的信息相比，这个教师的信息提供期望的输出值，而且还有一个误差信号 能够被用作网络的权值实行自适应1 。前馈型网络以感知器、反向传播模型、r b f 网络为代表，可用于预测、模式识别等方面。 ( 2 ) 反馈型网络 反馈型网络所有的节点都是计算单元，同时既可接受输入，又可向外界输出， 报显然，可用一个完全的无向图表示。若总节点数为以，那么每一个节点有( n 1 1 个输入和一个输出。闭合反馈环的本质是通过 y ，= 1 , 2 ，m 能够控制输出y ，。如 果当前输出y ( f ) 控制下一时刻的输出y ( t + ) ，这种控制是特别有意义的。在t 和 f + 之间经过时间通过反馈环中延迟元件引入到网络中。时延有符号含义， 它模拟了基本生物神经元模型的难控制的周期。沿用前馈型网络中曾用过的符号 y ( f ) 映射成r ( t + ) ，现在能写成 重庆大学硕士学位论文2 数据挖掘中的人工神经网络技术 y o + ) = r l 矸o r ( t ) l ( 2 1 4 ) 单层反馈网络有离散和递归两种主要类型。如果我们考虑时间为离散变量， 并且决定在离散时刻，2 ，3 ，上去观察网络性能，这个系统称作为离散时间类 型。递归网络在( 七十1 ) 时刻，它的响应取决于在k = 0 处开始网络的整个历史。递 归网络典型地运行在数据的离散表示情况下，他们使用具有硬( 严厉) 限制型激活 函数。具有离散输入和离散数据表示的系统称为自动机。它以离散型h o p f i e l d 神 经元网络和连续模型为代表，分别用于联想记忆和优化计算。 ( 3 ) 自组织网络。它以a r t 模型、k o h o l o n 模型为代表，用于聚类分析等方面。 由于不是我们研究的方向，不再细说。 2 3 小结 本章主要介绍了数据挖掘和人工神经网络的相关知识，其中包括了数据挖掘 的定义、数据挖掘的任务和相关技术、数据挖掘的常用算法以及在各实际领域的 应用。然后详细介绍了应用于数据挖掘的三种主要网络；前馈型网络、反馈型网 络