（检测技术与自动化装置专业论文）基于数据挖掘技术的交通流预测系统设计.pdf

t 、 o -j ， 疆 l t h e d e s i g no ft r a f f i cf l o wf o r e c a s t i n gs y s t e m b a s e d o nd a t am i n i n g ad i s s e r t a t i o ns u b m i t t e df o rt h ed e g r e eo fm a s t e r c a n d i d a t e ：l in a s u p e r v i s o r ：p r o f w a n gg u i p i n g c h a n g a nu n i v e r s i t y , x i a n ，c h i n a 6 820洲3 7川i_哪y 论文独创性声明 本人声明：本人所呈交的学位论文是在导师的指导下，独立进行研究工 作所取得的成果。除论文中已经注明引用的内容外，对论文的研究做出重 要贡献的个人和集体，均已在文中以明确方式标明。本论文中不包含任何 未加明确注明的其他个人或集体已经公开发表的成果。 本声明的法律责任由本人承担。 论文作者签名： 椰 2 0 o 年厂月昭日 论文知识产权权属声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归属学 校。学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权 利。本人离校后发表或使用学位论文或与该论文直接相关的学术论文或成 果时，署名单位仍然为长安大学。 ( 保密的论文在解密后应遵守此规定) 论文作者签名：右面沪 别币雠： 2 咖年月f 弓日 钞cq 年月汐 摘要 在我国，高速公路的快速发展在带来巨大经济与社会效益的同时，高速公路运行过 程中存在着交通拥挤、交通安全和环境污染等问题也日渐突出，人们越来越迫切地期望 获得高速、安全、舒适和高效的出行环境。因此，提高高速公路管理部门和其他决策部 门的服务质量已成为大势所趋，这也为智能交通系统的推广及应用开辟一片广阔的空 间。 智能交通系统是由通讯系统将运输系统中的人、车、路三要素紧密地结合在一起， 最大限度的发挥整个交通运输系统的运输和管理效率。正确的交通流预测，是智能交通 系统的实时交通信号控制，交通分配、路径诱导、自动导航，事故检测等的前提。总结 以往交通流预测的研究方法，可以分成基于传统统计理论的方法、基于神经网络的方法、 基于非线性理论的方法和基于新兴技术的预测方法。 本文以统计理论为基础，在数据挖掘分类方法的指导下，根据交通流数据自身的特 点，提出一种变异的基于距离的分类方法。该方法认为数据间相似的一组数值即是一 “类”，在预测阶段通过查找与新案例同“类”的记录来估计未知数值。本文首先根据交通 流预测系统的开发目标，进行具体的系统设计需求分析。其次，以数据挖掘技术为指导 思想，对交通流预测系统进行详细的软件设计。最后，对开发的交通流预测系统的实际 性能进行评价。 关键词：数据挖掘、交通流预测、分类方法、系统设计、软件设计 t h ep r e d i c t i o ns t a g e ，t h eu n k n o w nv a l u eo fan e wc a s ec a nb ee s t i m a t e db yr e t r i e v i n ga n d c o m p u t i n gt h es a m e ”c l a s s ”o fr e c o r d s i nt h i sp a p e r , f i r s t ，a c c o r d i n gt od e v e l o p m e n tg o a l so f t r a f f i cf l o wf o r e c a s t i n gs y s t e m ，m a k e sas p e c i f i cs y s t e md e s i g nr e q u i r e m e n t sa n a l y s i sr e p o r t s e c o n d l y , u n d e rt h eg u i d a n c eo fd a t am i n i n g ，m a k ead e t a i l e ds o f t w a r ed e s i g no ft r a f f i cf l o w f o r e c a s t i n gs y s t e m f i n a l l y , e v a l u a t et h e a c t u a lp e r f o r m a n c eo ft h et r a f f i cf l o wf o r e c a s t i n g s y s t e m k e yw o r d s ：d a t am i n i n g ，t r a f f i cf l o wp r e d i c t i o n ，c l a s s i f i c a t i o nm e t h o d ，s y s t e md e s i g n , 第 第 2 1 数据挖掘概述9 2 1 1 数据挖掘技术产生的背景1 0 2 1 2 数据挖掘的概念1 1 2 1 3 数据挖掘研究对象。1 3 2 1 4 数据挖掘的任务1 3 2 2 知识发现的基本过程1 4 2 3 本章小结1 6 第三章分类方法17 3 1 分类方法概述1 7 3 2 分类的基本概念与步骤1 7 3 3 经典分类算法1 9 3 3 1 基于距离的分类方法1 9 3 3 2 决策树分类方法2 1 3 3 3 贝叶斯分类2 6 3 3 4 粗糙集分类2 8 3 4 本章小结3 0 第四章系统设计需求分析31 4 1 系统设计目标3l 4 2 系统设计功能要求3 2 4 3 数据流图与数据字典3 3 4 3 1 数据流图3 3 4 3 2 数据字典3 4 5 5 模式评估及其预测4 9 5 5 1 模式评估4 9 5 5 2 预测界面。4 9 5 5 3 预测的核心代码5 0 5 6 本章小结5 1 第六章交通流预测系统性能评价5 2 6 1 评价指标5 2 6 1 1 平均误差。5 2 6 1 2 相关系数一5 2 6 2 预测分析。5 3 结论和建议5 4 参考文献5 6 致谢5 8 长安大学硕士学位论文 1 1 研究背景 第一章绪论 我国高速公路经过2 1 年的持续快速发展，使公路基础设施总体水平实现了历史性 跨越。“十五”期间中国共建成高速公路2 4 7 万公里，是“八五”和“九五”建成高速公路总 和的1 5 倍。截止2 0 0 9 年底，中国高速公路的通车总里程达6 5 万公里，稳居世界第二 位，仅次于美国。高速公路的快速发展，大大缩短了省际之间、重要城市之间的时空距 离，加快了区域间人员、商品、技术、信息的交流速度，有效降低了生产运输成本，在 更大空间上实现了资源有效配置，拓展了市场，对提高企业竞争力、促进国民经济发展 和社会进步都起到了重要的作用。在高速公路的发展产生巨大的经济与社会效益的同 时，高速公路运营现状也存在诸多问题。 高速公路在运行过程中仍然存在交通拥挤、交通安全和环境污染等问题，特别是近 年来交通需求量的持续高速增长，使高峰期入城和市区高速公路拥挤、阻塞日益严重， 城间高速公路事故频发。产生交通拥挤的根本原因是交通供求关系的不平衡【i 】。目前， 我国绝大部分省份高速公路已形成路网，单独路段的异常事件影响的范围越来越广，必 然要求相临路段之间能互通协调，这就带来了联网的需求，联网监控已经成为大势所趋。 智能交通系统i t s ( i n t e l l i g e n tt r a n s p o r t a t i o ns y s t e m s ) 是近年来迅速发展的城市道路 和高速公路控制管理的新技术。该系统是在联网监控的基础上，由先进的交通管理系统、 先进的交通控制系统、先进的公共交通系统、先进的营运车辆调度系统、先进的驾驶员 信息系统、先进的城市间交通系统等组成。智能交通系统的目标是通过通讯系统将运输 系统中的人、车、路三要素紧密地结合在一起，最大限度的发挥整个交通运输系统的运 输和管理效率。智能交通系统中先进的交通控制系统与先进的交通管理系统均要求为其 提供实时的交通流信息。由于正确的交通流预测，是智能交通系统的实时交通信号控制， 交通分配、路径诱导、自动导航，事故检测等的前提，因此，对交通流预测方法的研究 具有非常重要的意义【2 1 。 目前有关交通流预测是一个热门话题，尽管已经形成了基于不同理论的多种预测模 型和方法，但迄今为止任没有哪一种方法可以适用于所有的情况。本文正是基于以上背 景，以研究预测商界高速交通流为例，应用当前先进的数据挖掘技术，通过问题定义、 数据抽取、数据预处理、数据挖掘以及模式评估五个步骤学习历史数据，基于分类理论 第一章绪论 提出一种交通流预测的方法，据此设计交通流预测系统用来预测未来的发展趋势并且给 出具体的预测值。知识发现过程的五个步骤如图1 1 所示。 问题 源数据 数据 数据 预处理知识 定义抽取 r预处 数据。 数据模式模式 挖掘评估 理 1 2 国内外研究现状 图1 1知识发现的基本过程 较早期的交通流预测方法主要有：历史平均模型( h a ) 、自回归模型( a r ) 、滑动平 均模型( m a ) 、自回归滑动平均模型( a r m a ) 和b o x c o x 法等。由于上述各种方法不同 程度上存在着一定的局限性，在随后逐步深入的研究过程中，又出现了一批更复杂的、 精度更高的预测方法。总结起来，大致可分成以下4 类方法：基于统计学理论的方法、 基于神经网络的方法、基于非线性理论的方法和基于新兴技术的预测方法。 一、基于统计方法的模型( s t a t i s t i c b a s e dm o d e l ) 这类模型是基于数理统计的理论处理交通历史数据，如交通流量、交通速度、旅行 时间等，在假设未来预测的数据与过去的数据有相同特性的前提下，通过使用历史数据 预测未来数值。基于统计方法的模型主要有历史平均模型、线性回归模型、时间序列模 型、卡尔曼滤波模型、m a r k o v 预测、极大似然估计模型等。 1 历史平均模型( h i s t o r ya v e r a g em o d e l ) ：历史平均模型预测交通流属于一种静 态的方法。这种方法认为交通流量和时间具有严格的周期性。历史平均模型中的算法、 历史均值法基于这样一个假设：一个点的交通流量是遵循一定的规律的。它是以一天为 周期重复再现的。它的优点是计算方法简单，但精度较差，虽然可以在一定程度内解决 不同时间、不同时段内的交通流变化问题，但其静态性的本质具有先天性的不足，因此 它不能解决非常规和突发的交通状况，如交通事故等【3 】。 2 线性回归模型( l i n e a rr e g r e s s i v em o d e l ) ：是一种通过分析事物之间因果关系和 影响程度进行预测的方法。它的优点是方法比较成熟，所需检测设备比较简单，但缺点 也很明显，主要是适用性差、实时性不强。线性回归是通过分析影响交通流因素的基础 上，确定交通流预测的回归方程，由于单纯依据预先确定的方程进行预测，因此只适用 2 长安大学硕士学位论文 于特定路段的特定流量范围且不能及时修正误差。当实际情况与参数标定时的交通状态 相差较远时，预测误差将会增大，而在线标定多元线性回归的参数又比较困难。此外， 在将主要影响因素量化的过程中还存在着一些不确定性。 3 时间序列模型( t i m es e r i a lm o d e l ) 是一种参数化模型处理动态随机数据的统 计方法，该方法基于随机过程理论和数理统计学方法，研究随机数据序列所遵从的统计 规律。通过对实测的数据序列进行统计分析，将其拟合成一个参数模型，再利用该模型 分析研究实测数据序列内在的统计特性，从而根据其规律使用现在、过去的观测值来预 测其未来值。主要模型有：自回归模型0 恹) 、滑动平均模型( m ) 、自回归滑动平均混 合模型( a r - m a ) 、a r i m a 模型和i m a 模型。 时间序列模型建模简单，容易理解，既考虑了观测数据在时间序列上的依存性，又 考虑了随机波动的干扰，在数据充分的情况下，具有较高的预测精度，但同时也存在以 下不足：由于该方法只考虑交通流的历史数据而没考虑其他的影响因素，因此在交通 状态急剧变化的情况下，如交通拥挤等，其预测结果存在明显的时间延迟；在应用于 受随机干扰小，确定性较强的短时交通流建模过程中，该方法的预测效果较好，但当此 条件无法满足时j 其模型结构辨识和检验的过程比较繁琐；由于模型参数求解是离线 的，且在预测的过程中参数是固定的，因此该方法不适用于短时交通流动态预测。 总的来说，基于统计方法的模型理论简单、计算简便，但由于模型的建立是基于线 性的基础，所以当预测间隔小于5 m i n 时，随着交通流量变化的随机性和非线性的加强， 使得模型预测效果降低。另外，预测时仅仅利用本路段的历史数据，而没有考虑相邻路 段的影响，这也是影响其预测精度的原因之一。 二、神经网络模型( n e u r a ln e t w o r km o d e l ) 神经网络是一种新兴的数学建模方法，它具有识别复杂非线性系统的特性，基于神 经网络进行预测的原理为：首先，利用一部分数据进行训练，确定网络模型的结构，它 包括确定网络的隐含层数、各层节点数、各层连接权值以及各层神经元的传递函数；其 次，在网络结构确定后，利用剩余部分数据进行预测。总结起来分成3 类：单一的神经 网络模型；多种神经网络相结合的优化模型；神经网络结合其他先进理论进行预测的综 合模型等。 1 单一的神经网络模型：该类模型包括反向传播b p 神经网络、径向基r b f 神经 网络、递归神经网络、时间延迟神经网络、多层反馈神经网络、谱分析人工神经网络、 对偶传播神经网络等。 3 第一章绪论 反向传播( b a c kp r o p a g a t i o n ) 神经网络：是一个具有三层或三层以上的层次神经网 络。基于b p 算法的多层前馈型神经网络的结构如图1 2 所示，输入层为已知上游位置 的交通流量、速度及其他历史数据，经隐含层输出为当前位置的预测交通流量。 误差反传( 学习算法) 输入屡隐含层输出层 信号流 图1 2 基于b p 算法的神经网络的结构 虽然b p 网络得到了广泛的应用，但自身也存在一些固有的缺陷和不足：确定网络 结构的过程中，网络隐含层的层数和单元数的选择尚无理论上的指导，一般是根据经验 或者通过反复实验确定；b p 算法可以使权值收敛到某个值，但并不保证其为误差平面 的全局最小值，这是因为采用梯度下降法可能产生一个局部最小值；由于学习速率是固 定的，因此网络的收敛速度慢，修要较长的训练时间；而且此网络运行是单向传播，没 有反馈；再者，在训练中，此网络结构学习新样本有遗忘旧样本的趋势。 径向基r b f ( r a d i a lb a s i sf u n c t i o n ) 神经网络：同b p 网络一样，r b f 网络也是一种 前向网络，它由一个隐含层( 径向基层) 和一个线性输出层组成，其输出层是线性求和 单元，即输出是各隐含层的加权求和，其结构如图1 3 所示。隐含层采用径向基函数作 为网络的激活函数，输入层和隐含层的所有权重固定为1 ，隐含层r b f 单元的中心及半 径通常也预先确定，只有隐含层和输出层的权重可调。 图1 3r b f 神经网络结构 4 长安大学硕士学位论文 r b f 神经网络利用在多维空间中插值的传统技术，可以对几乎所有的系统进行辨识 和建模，它不仅在理论上有着任意逼近性能和最佳逼近性能，而且在应用中具有很多优 势：算法速度大大高于一般的b p 算法，经过对实际交通流数据预测结果对比，r b f 网 络学习速度比b p 方法快1 0 3 - - 一1 0 4 倍；r b f 神经网络不但在理论上是前向网络中最优 的网络，而且学习方法也避免了局部最优的问题。但其同时也存在以下缺点：不能向用 户提出必要的询问，而且当数据不充分时，神经网络就无法进行工作；r b f 神经网络的 非线性映射能力体现在隐层基函数上，而基函数的特性主要由基函数的中心确定，从数 据点中任意选取中心构造出来的r b f 神经网络显然不能令人满意。 2 优化的神经网络预测模型：在短期交通流预测的研究领域中，神经网络应用较 多，但是每种神经网络模型都有其自身的优势和局限性，若将不同的神经网络相结合应 用，能相互“取长补短”，同时也促进了多种神经网络相结合的混合优化预测模型的研究。 3 综合神经网络模型：随着科学的发展，促进了多学科的交叉与融合。在交通流 预测领域中，逐步出现了神经网络技术与其他领域的先进理论相结合的应用方式，如神 经网络与优化算法( 遗传算法、粒子群优化算法、蚁群优化算法、模拟退火算法等) 的结 合、神经网络与模糊逻辑相结合、神经网络与粗集理论相结合、神经网络与时间序列相 结合等等，对比单一的、优化的神经网络模型其综合模型的预测精度有很大的提高。 神经网络具有识别复杂非线性系统的特性，交通系统是复杂巨系统，因此神经网络 比较适用于短期交通流预测的应用。目前研究已从单一神经网络，发展到不同的神经网 络模型组合，再到神经网络模型和其他领域的先进理论结合进行预测，模型精度和预测 效果已大大提高。但同时应注意到该应用的局限和不足：神经网络“黑箱”式的学习模 式，使得无法获得容易被人理解的输入输出关系，且在训练过程中原始数据不足会导致 预测效果不佳；训练完成的网络仅能应用于当前研究路段，当路网的交通状况发生变化 时，已生成的模型不再适用，也不能应用于其他路段，所以推广能力差；同时，神经网 络的学习算法采用经验风险最小化原理，不能实现期望风险最小化使得其理论上存在缺 陷。神经网络模型的训练过程只能通过调整神经元的权值进行数据处理，即只有神经元 外部的处理能力，这种不足导致这类网络存在着局部极小、收敛速度慢以及难以实现在 线调整等问题。 三、基于非线性理论的预测方法 非线性预测主要以混沌理论、耗散结构论、协同论、自组织理论等非线性系统理论 为基础，利用有关混沌吸引子概念、分形概念、相空间重构方法，数字生态模拟法等建 5 第一章绪论 立预测模型。其中发展较成熟的预测方法是混沌理论、小波分析和分形预测。当预测周 期垃缩小到5 m i n 或更短，交通流的不确定性、非线性更强，采用非线性预测有很强的 ， 适应性。 1 基于混沌理论的预测方法：混沌理论用以探讨动态系统中( 如：人口移动、化 学反应、气象变化、社会行为等) 无法用单一的数据关系，而必须用整体、连续的数据 关系才能加以解释及预测的行为。混沌现象发生于易变动的物体或系统，该物体在行动 之初极为单纯，但经过一定规则的连续变动之后，却产生始料未及的后果，也就是混沌 状态。但此混沌状态不同于一般杂乱无章的混乱状况，此混沌现象经过长期及完整分析 之后，可以从中找出某种规则。混沌理论的研究目的是揭示貌似随机的现象背后可能隐 藏的简单规律，以求利用这些规律来解决复杂系统的问题。交通流系统是人的群体参与 的开放的复杂巨系统，因此交通中存在着混沌。由于混沌理论对非线性、不确定性系统 的预测非常适合，所以这类模型对交通流预测将会有很好的发展应用前景 4 1 。 2 基于小波分析的预测方法：许多分析应用最终都可以归结为信号处理问题，小 波分析是处理非稳定信号强有力的工具。小波分析是通过小波变换将信号一层一层分解 到不同的频率通道上，且这种变换是时间和频率的局域变换，由于分解后的信号在各通 道上的频率成分单一，且小波分解对信号作了平滑处理，因此分解后的信号的平稳性比 原始信号好得多。这样，小波分解后的时间序列可以当作平稳时间序列处理。利用小波 变换分解交通系统的非稳定信号，将交通流序列分解为多个分量，对各信号分量分别进 行预测，再合成最终的预测结果，极大地提高了预测准确度。基于小波理论的模型有很 大的应用前景，但在交通流预测领域应用不多，将有待继续研究。 3 分形理论模型：分形理论是非线性科学的前沿和重要分支，它是描述复杂系统 的一种强有力的工具。自相似性是分形理论的重要观点，它表征分形在通常的几何变换 下具有不变性，即标度无关性。利用分形理论进行交通流预测有一个基本前提，要求当前 的交通流演化过程与历史交通流的变化过程具有自相似性，由于短时交通系统存在自相 似性，所以可以使用分形理论进行预测。然而，分形预测一旦逾越无标度区间的范围， 自相似将不复存在，系统也没有分形规律了。利用分形理论在现阶段还仅仅是分维，若 要进行短时交通流预测还需要进一步的研究【3 j 。 四、基于动态交通分配的模型( d t a 模型) 动态交通分配是通过采集到的交通流数据和出行者出行选择的行为，按照一定的准 6 长安大学硕士学位论文 则将动态交通需求量合理地分配到路网上，从而得到路段实时交通量的方法，实现降低 交通拥挤程度和提高路网运行效率的目的。此方法是以传统的静态交通分配的方法解决 随时间变化的动态交通流问题，虽然理论充分，但是也存在以下不足之处：假设条件苛 刻，在实际路网中难于做到或无法做到的动态o d 信息；已有的动态交通分配模型的解 释性虽然较好，但普遍存在优化计算时间过长，预测的实时性差；由于采用递推方式计 算，计算过程中积累的误差会使得分配结果的可靠度降低，因此在实践应用中没有取得 良好的使用效果【5 j 。 在短期实时的交通流预测中，单纯依赖一种预测模型和方法，很难满足在多种不同 条件下的实际应用，难以获得令人满意的预测结果。纵观该领域的研究历史与现状，研 究的中心始终围绕着交通流的随机性、非线性的特点，充分发挥各理论或方法的优势进 行预测。近年来的研究成果表明，多种神经网络相结合的优化模型比单一的神经网络模 型的预测效果要好，而将神经网络模型与其他领域的研究相结合的综合模型的预测效果 要好于优化模型。因此，短时交通流预测方法发展的趋势将是神经网络与各相关学科的 人工智能技术有机结合【3 】。 目前国内外采用数据挖掘技术进行短时交通流预测主要是针对特定方面的应用，例 如分析何时需要进行道路养护。一般对交通流预测属于定性分类，例如车流量大或小， 从而判断何时适合封闭车道以及哪个车道进行道路养护，而不是对交通流数值本身进行 预测计算。一般的数据挖掘过程也都是通过数据挖掘软件( 例如s p s sc l e m e n t i n e ) 来 实现具体操作的：通过导入源数据，运行软件中预先定义好的模式模块单元，得出挖掘 知识，最后使用这些知识服务于特定问题的应用，对问题的解决其决策支持作用。 1 3 研究目的和意义 结合以往交通流预测研究的成果，以先进的数据挖掘思想为技术支撑，以满足高速 公路管理部门和决策机构对车流量预测的业务需求为首要目标，充分考虑特定路段车辆 行驶的实际情况，研究出一个应用于具体环境下、可行的、实用的、可靠的交通流预测 系统，要求系统能够推导出一个贴近实际交通流量的预测值，进而为智能交通系统的实 时控制与诱导提供服务，最大限度的发挥整个交通运输系统的运输和管理效率。 交通运输是国民经济的基础产业，对于经济发展和社会进步具有极其重要的作用。 加快交通基础设施建设，综合运用检测、通信、计算机、控制、g p s 和g i s 等现代高新 7 第一章绪论 技术，提高交通基础设施的利用效率、减少交通公害对加速发展我国公路交通运输事业 具有十分重要的意义。智能交通系统通过通讯系统将运输系统中的人、车、路三要素紧 密地结合在起，通过对系统内的资源统一协调、规划，最大限度的发挥整个交通运输 系统的运输和管理效率，最终实现高速公路高速、安全、舒适和高效的特性。 1 4 本文研究内容及结构 本文主要是运用数据挖掘技术，以研究预测商界高速交通流为例，通过问题定义、 数据抽取、数据预处理、数据挖掘以及模式评估五个步骤学习历史数据，基于分类理论 建立一种交通流预测的方法，据此设计一个可行的、实用的、可靠的交通流预测系统， 系统最终可预测出一个贴近实际交通流量的估计值。本文组织结构安排如下： 第一章绪论部分介绍了论文的研究背景、国内外研究现状、论述了课题研究的目的 和意义，概括本文的主要内容和组织结构； 第二章数据挖掘技术。本章从产生背景、概念、研究对象和任务几个方面概述数据 挖掘技术，以及介绍知识发现的五个步骤。 第三章分类方法。本章概述分类、介绍分类的基本概念和步骤以及经典的分类算法； 第四章系统设计需求分析。本章以软件需求分析规格说明书为模板，从系统设计目 标、设计功能要求、数据流图和数据字典、系统接口、系统设计原则以及其他需求六个 方面进行分析，提出系统软件设计的需求； 第五章基于数据挖掘技术的交通流预测系统软件设计。本章结合数据挖掘技术的思 想，分别从知识发现过程的五个步骤( 即问题定义、数据抽取、数据预处理、数据挖掘 和模式评估) 介绍系统软件开发的具体过程，其中还包含部分的程序流程图、系统界面 以及核心代码； 第六章交通流预测系统性能评价。根据设定的评价指标，通过对预测系统实际运行 效果的分析，给出其性能客观评价。 最后对全文进行了总结，并对后续的研究工作给出了一些有益的建议。 8 长安大学硕士学位论文 2 1 数据挖掘概述 第二章数据挖掘技术 数据挖掘( d a t am i n i n g ) 是一个多学科交叉的研究领域，它融合了数据库( d a t a b a s e ) 技术、人工智能( a r t i f i c i a li n t e l l i g e n c e ) 、机器学习( m a c h i n el e a m i n g ) 、统计学( s t a t i s t i c s ) 、 知识工程( i n f o r m a t i o ne n g i n e e r i n g ) 、面向对象方法( o b j e c t o r i e n t e dm e t h o d ) 、信息检 索( i n f o r m a t i o nr e t r i e v a l ) 、高性能计算( h i g h p e r f o r m a n c ec o m p u t i n g ) 以及数据可视 化( d a t av i s u a l i z a t i o n ) 等最新技术的研究成果。经过十几年的研究，产生了许多新概 念和新方法。特别是近几年来，一些基本概念和方法逐步清晰化，其研究正向着更加深 入的方向发展。 数据挖掘被称为未来信息处理的骨干技术之一，主要源于它是以一种全新的概念改 变着人类利用数据的方式，并使数据处理技术进入了一个更高级的阶段。2 0 世纪，数据 库技术取得了决定性的成果并且在各个行业都得到了广泛的应用。但是，数据库技术作 为一种基本的信息存储和管理方式，仍然以联机事务处理( o n l i n et r a n s a c t i o n p r o c e s s i n g ，o l t p ) 为应用核心，缺少对决策、分析、预测等高级功能的支持机制。众 所周知，随着数据库容量的膨胀，特别是数据仓库( d a t aw a r e h o u s e ) 以及w e b 等新型 数据源的日益普及，联机分析处理( o n l i n ea n a l y t i cp r o c e s s i n g ，o l a p ) 决策支持 ( d e c i s i o ns u p p o r t ) 以及分类( c l a s s i f i c a t i o n ) 、聚类( c l u s t e r i n g ) 等复杂应用成为必然。 面对这一挑战，数据挖掘和知识发现( k n o w l e d g ed i s c o v e r y ) 技术应运而生，并显示出 强大的生命力。它不仅能对过去的数据进行查询，而且能够找出过去数据之间的潜在联 系，进行更高层次的分析，以便更好地做出理想的决策、预测未来的发展趋势等。通过 数据挖掘分析，可以将有价值的知识、规则或高层次的信息从数据库的相关数据集合中 抽取出来，从而使大型数据库作为一个丰富、可靠的资源为知识的提取服务。 特别需要指出的是，数据挖掘技术从一开始就是面向实际应用的。它不仅是对数据 库进行简单的检索查询调用，更要实现对这些数据进行微观、中观乃至宏观的统计、分 析、综合和推理。这里所说的知识发现，不是发现放之四海皆准的客观规律或崭新的自 然科学定理或数学公式，所有发现的知识都是相对的，是面向特定领域的，同时还要能 够易于被用户理解。 9 第二章数据挖掘技术 2 1 1 数据挖掘技术产生的背景 任何一项技术的产生都不是空虚来风的，而是有其自身存在的前提，这其中包含有 应用的需要和技术环境的支撑，两者缺一不可。数据挖掘也正是在这样的背景下应运而 生的： 一、数据挖掘技术的商业需求 数据挖掘之所以吸引专家学者的研究兴趣和引起商业厂家的广泛关注，主要在于把 大型数据系统中的数据转换成有用知识的迫切需要以及由此可带来潜在的、巨大的商业 利润的强烈渴望。从2 0 世纪6 0 年代简单的文件处理系统转变到数据库系统开始，经过 7 0 年代的大力推动层次、网络和关系型数据库的研究和开发，再到8 0 年代关系型数据 库及其相关的数据模型工具、数据索引及数据组织技术被广泛采用，直至9 0 年代分布 式数据库理论趋于成熟，分布式数据库技术得到了广泛应用，数据的存储技术在几十年 间发生了质的变革。近年来，信息技术的高速发展，数据库应用的规模、范围和深度不 断扩大，已经从单台机器发展到网络环境，同时，数据采集技术的更新也导致产生了大 规模的数据。随着数据的急剧增长，现有信息管理系统中的数据分析工具已无法适应新 的需求。因为无论是查询、统计还是报表，其处理方式都是对指定数据进行简单的数字 处理，而不能对其所包含的内在信息进行提取。 数据( d a t a ) 、信息( i n f o r m a t i o n ) 和知识( k n o w l e d g e ) 可视为广义数据表现的不 同形式。计算机存储技术和网络技术的发展帮助人们扩大了数据收集的范围和容量，但 也导致了“数据丰富而信息贫乏( d a t ar i c h & i n f o r m a t i o np o o r ) ”现象的产生。信息是指 对人们有帮助的数据，然而面对计算机中海量的数据，人们又缺乏行之有效的获取信息 的手段。知识是以一种概念、规则、模式或规律的形式存在，它不像数据或信息那么具 体，但是它却是人们一直不懈追求的目标。因此，随着数据的膨胀和技术环境的进步， 人们对联机决策和分析等高级信息处理的要求越来越迫切，在2 0 世纪8 0 年代后期，产 生了数据仓库和数据挖掘等信息处理思想。 二、数据挖掘产生的技术背景 任何技术的产生总是离不开其技术背景的支持，数据挖掘技术也不例外。数据挖掘 技术的提出和普遍接受是由于计算机及其相关技术的发展为其提供了研究和应用的技 术基础。归纳数据挖掘产生的技术背景，下面一些相关技术的发展起到了决定性的作用： 数据库、数据仓库和i n t e m e t 等信息技术的发展； 1 0 长安大学硕士学位论文 计算机性能的提高和先进的体系结构的发展； 统计学和人工智能等方法在数据分析中的研究和应用。 数据库技术从2 0 世纪8 0 年代开始，已经得到广泛的普及和应用。在关系型数据库 的研究和产品提升过程中，人们一直在探索组织大型数据和快速访问的相关技术。数据 仓库作为一种新型的数据存储和处理手段，成为多数据源集成的一种有效的技术支撑环 境。另外，i n t e m e t 的普及也为人们提供了丰富的数据源，形成了以w e b 计算为核心的 信息处理技术。因此，人们已经具备了利用多种方式存储海量数据的能力，为数据挖掘 技术的研究和应用提供了丰富的土壤。 随着计算机芯片技术的发展，计算机的处理速度和存储能力日益提高。计算机硬件 的关键指标大约以每1 8 个月翻一番的速度在增长，随之而来的是硬盘、c p u 等关键部 件的价格大幅度下降，使得人们收集、存储和处理数据的能力和欲望不断提高。计算机 体系结构经过几十年的发展，随着并行处理技术理论逐步成熟和广泛应用，已经成为支 持大型数据处理应用的基础。计算机性能的提高和先进体系结构的发展为数据挖掘技术 的研究和应用提供了技术上的保障。 历经了几十年的发展，人们已经成功地将统计学、人工智能等理论和技术成果应用 到商业数据处理和分析中，而这些理论自身的发展和应用也为数据挖掘技术提供了前瞻 性的指导。数理统计是一个有着几百年发展历史的应用数学学科，在数据库的使用从被 动查询变成主动发现知识的过程中，概率论和数理统计可以为我们从数据归纳到知识生 产提供理论基础。 人工智能是计算机科学研究中争议最多而又始终保持强大生命力的研究领域。专家 系统是人工智能最活跃的一个分支，它是把从特定研究领域的专家那里获得知识与经 验，进行规则抽象并整理表达，以便使用这些规则模拟人类专家决策指导该领域的问题。 但是，由于知识获取中的随机性和主观性，用i f - t h e n 等规则表达的局限性，以及缺乏大 量背景知识等原因，使得这种机制不可避免地带有偏见和错误，限制了专家系统的应用。 数据挖掘继承了专家系统的高度实用性的特点，并且以数据为基本出发点，正视现实生 活中大量的、不完全的、有噪声的大数据样本，真正客观地从数据集中发现蕴藏的知识。 2 1 2 数据挖掘的概念 一、从商业的角度看数据挖掘技术 数据挖掘从商业角度上说是一种新的商业信息处理技术。数据挖掘技术使人们对数 第二章数据挖掘技术 据的应用有了重新的认识，从低层次的联机查询操作，提高到决策支持、分析预测等更 高级应用上。商业内数据挖掘就是按企业的既定业务目标，对大量的企业数据进行深层 次的统计、分析、综合和推理，发现数据间隐藏的、未知的、规律性的知识，从而用来 指导商业决策活动。数据挖掘技术从提出之日起就具有很强的商业应用目的，并且它只 有面向特定的商业领域才有应用价值，所发现的知识也都是相对的。 二、数据挖掘的技术含义 数据挖掘，在人工智能领域，习惯上又称为数据库中知识发现( k n o w l e d g ed i s c o v e r y i nd a t a b a s e ，l d ) ，也有人把数据挖掘视为数据库中知识发现过程的一个基本步骤。 针对知识发现与数据挖掘间关系的不同观点，我们可以了解数据挖掘的技术含义。 1 知识发现看成数据挖掘的一个特例 早期观点认为，数据挖掘可以在关系型数据库、事务数据库、数据仓库、空间数据 库、文本数据以及诸如w e b 等多种数据组织形式中挖掘知识，因此数据库中的知识发 现只是数据挖掘的一个方面。从这个意义上说，数据挖掘就是从数据库、数据仓库以及 其他数据存储方式中挖掘有用知识的过程。 2 数据挖掘是知识发现过程的一个步骤 为了统一认识，在1 9 9 6 年出版的权威文集知识发现与数据进展中给出了知识 发现和数据挖掘的最新定义，将二者加以区分。 知识发现是从数据中辨别有效的、新颖的、潜在有用的、最终可理解的模式的 过程。 数据挖掘是知识发现中通过特定的算法在可接受的计算效率限制内生成特定模 式的一个步骤。 这种观点得到学者的广泛认同。虽然可以从数据仓库、w e b 等源数据中挖掘知识， 但是这些数据源都是和数据库技术相关的。知识发现是一个更广义的范畴，它包括数据 清洗、数据集成、数据选择、数据挖掘、模式生成及评价等一系列步骤。因此，把知识 发现看作是一系列模块系统化的工作，而数据挖掘则是这个系统中的一个关键部分，这 样可以更容易聚焦研究重点，更能有效解决问题。 3 、知识发现与数据挖掘含义相同 在现今的文献和许多场合中，知识发现与数据挖掘这两个术语都是不加区分地使用 着。有人说，知识发现在人工智能界更流行，而数据挖掘在数据库界使用更多。也有人 说，一般在研究领域被称作知识发现，在工程领域则称之为数据挖掘。 1 2 长安大学硕士学位论文 综上所述，数据挖掘定义有广义和狭义之分。广义观点认为，数据挖掘是从大型数 据集中挖掘隐含的、未知的、对决策有用的知识过程。狭义观点认为，数据挖掘是从特 定形式的数据集中提炼知识的过程。从以上的描述中可以看出，数据挖掘概念可以在不 同的技术层面上来理解，但是其核心仍然是从数据中挖掘知识。 2 1 3 数据挖掘研究对象 从原理上说，数据挖掘可以应用到任何信息存储方式下的知识挖掘中，因此数据挖 掘的研究对象是各种存储类型下的源数据。根据数据存储类型将数据挖掘的研究对象分 为：事务数据库、关系型数据库、数据仓库、在关系模型基础上发展的新型数据库( 如 面向对象数据库、对象关系型数据库以及演绎等) 、面向应用的新型数据源( 如空间数 据库、时态数据库、工程数据库和多媒体数据库等) 和w e b 数据源【1 l 】。 2 1 4 数据挖掘的任务 数据挖掘的任务包含预测任务和描述任务，如图2 1 所示，具体分为以下四类： 图2 1四种主要数据挖掘任务 一、预测建模( p r e d i c t i v em o d e l i n g ) 涉及以说明变量函数的方式为目标变量建立模 型。有两类预测建模任务：分类( c l a s s i f i c a t i o n ) ，用于预测离散的目标变量；回归 ( r e g r e s s i o n ) ，用于预测连续的目标变量。例如，预测一个w 曲用户是否会在网上书店 买书是分类任务，因为该目标变量是二值的。预测某股票的未来价格是回归任务，因为 价格具有连续值属性。两项任务目标都是训练一个模型，使目标变量预测值与实际值之 间的误差达到最小。预测建模可以用来确定顾客对产品促销活动的反应，预测地球生态 13 第二章数据挖掘技术 系统的扰动，或根据检查结果判断病人是否患有某种特定的疾病。 二、关联分析( a s s o c i a t i o na n a l y s i s ) 用来发现描述数据中强关联特征的模式。所发 现的模式通常用蕴涵规则或特征子集的形式表示。由于搜索空间是指数规模的，关联分 析的目标是以有效的方式提取最有趣的模式。关联分析的应用包括找出具有相关功能的 基因组、识别一起访问的w e b 页面、理解地球气候系统不同元素之间的联系等。 三、聚类分析( c l u s t e ra n a l y s i s ) 旨在发现紧密相关的观测值组群，使得与属于不同 簇的观测值相比，属于同一簇的观测值相互之间尽可能类似。聚类可用来对相关的顾客 分组、找出显著影响地球气候的海洋区域以及压缩数据等。 四、异常检测( a n o m a l yd e t e c t i o n ) 的任务是识别其特征显著不同于其他数据的观 测值。这样的观测值称为异常点( a n o m a l y ) 或离群点( o u t l i e r ) 。异常检测算法的目标 是发现真正的异常点，而避免错误地将正常的对象标注为异常点。换言之，一个好的异 常检测器必须具有高检测率和低误报率。异常检测的应用包括检测欺诈、网络攻击、疾 病的不寻常模式、生态系统扰动等【1 2 1 。 2 2 知识发现的基本过程 从源数据中发现有价值的知识是一个系统化的过程，该过程可以简单地概括如下： 首先需要对已知的源数据进行分析，从中抽取感兴趣的数据，并把它组织成适合挖掘的 数据组织形式；然后，调用相应的算法生成所需的知识；最后对生成的知识模式进行评 估，并把有价值的知识集成到企业的智能系统中。一般地说，发现知识是一个多步骤的 处理过程，分为问题定义、数据抽取、数据预处理、数据挖掘以及模式评估等基本阶段。 1 问题定义阶段 知识发现的目标是在大量源数据中发现有用的感兴趣的信息，因此确定发现何种知 识就成为整个过程中首要的一个问题。在问题定义过程中，数据挖掘人员需要和领域专 家以及最终用户紧密协作，一方面了解相关领域的具体情况和背景知识，弄清用户要求， 确定挖掘的目的等；另一方面通过对各种学习算法的对比进而确定可用的学习算法。后 续学习算法的选择和数据集的准备都是在此基础上进行的。 2 数据抽取阶段 数据抽取的目的是根据问题定义阶段的分析，从源数据库中提取相关的数据。源数 据库的选取以及从中抽取数据的原则和具体规则必须依据系统的任务来界定。 1 4 长安大学硕士学位论文 具体操作如下：在弄清源数据的信息和结构的基础上，首先需要准确地界定所选取 的数据源和抽取原则，将多数据库环境下的数据进行合并处理实现数据集成，然后设计 存储新数据的结构和准确定义它与源数据的转换和装载机制，以便正确地从每个数据源 中抽