（计算机应用技术专业论文）基于决策树学习和规则提取的热轧数据分析.pdf

武汉科技大学硕士学位论文 第1 页 摘要 数据库中的知识发现( i d ) 是将未加工的数据转换为有用信息的整个过程，而数据 挖掘是其不可缺少的一部分。数据挖掘是一个多学科交叉研究领域，它将传统的数据分析 方法与处理大量数据的复杂算法相结合，为探查和分析新的数据类型以及用新方法分析旧 有数据类型提供了令人振奋的机会。分类是具有广泛应用领域的数据挖掘算法之一，它是 对一个事件或一组对象进行归类，通过对训练数据集的挖掘获得分类模型。用分类模型能 够分析已有的数据，还可以用分类模型来预测未来趋势。决策树是一种典型的分类算法， 它可以从一组无次序、无规则的事例中推理出决策树表示形式的分类规则。 o l ed bf - 0 rd m 规范是m i c r o s o f i 为数据挖掘市场提供一个工业标准而提出的一套 a p i 。o l ed bf o rd m 规范的提出使数据库应用程序的开发者能够在他们的数据库中构造 数据挖掘模型，并用这些模型来完成大量的预测和分析任务，以及和其它的应用程序来分 享这些模型。 本文在对热连轧精轧机组数据进行分析处理后，采用v i s u a lc 抖6 0 与o l ed bf o rd m 规范相结合，使用s q ls e r v c r 数据挖掘解决方案生成决策树，并根据决策产生式规则本身 的特点，提出了基于关系数据库的决策树规则存储模型，以及规则的提取方法。本文提出 的数据挖掘系统的应用模型设计方法、开发步骤及数据表现形式，对基于s q ls e r v e r 数据 挖掘的设计及开发工作具有一定的参考价值。 关键词：数据挖掘；决策树；产生式规则；规则提取；o l ed b 硒rd m ；s q ls e r v 盯 第1 i 页武汉科技大学硕士学位论文 a b s t r a c t k n o w l e d g ed i s c o v e r yi nd a t a b a s e ( k d d ) i s aw h o l ep r o c e s st h a tc o n v e r tt h er a wd a t ai n t o u s e f u li n f o r m a t i o n ，a n dd a t am i n i n gi s a ni n d i s p e n s a b l ep a r to fi t d a t am i n i n gi sa m u l t i d i s c i p l i n a r yf i e l do fi n t e r d i s c i p l i n a r yr e s e a r c h ，i t c a l lc o m b i n et r a d i t i o n a ld a t aa n a l y s i s m e t h o d sw i t hc o m p l e xa l g o r i t h mo fd e a lw i t hal a r g ea m o u n td a t a , a n di tp r o v i d e se x c i t i n g o p p o r t u n i t i e sf o r t h ee x p l o r a t i o na n da n a l y s i so fn e w d a t at y p e sa n dn e wm e t h o d st oa n a l y s i so l d d a t at y p e s c l a s s i f i c a t i o ni saw i d e l yu s e do n eb r a n c ho ft h ef i e l di nd a t am i n i n ga l g o r i t h m s a n e v e n to rag r o u po fo b j e c t sa r ec l a s s i f i e db yi t t h r o u g ht h et r a i n i n gd a t as e to fm i n i n g c l a s s i f i c a t i o nm o d e la v a i l a b l e c l a s s i f i c a t i o nm o d e lu s e dt oa n a l y z ee x i s t i n gd a t a ；i tc a na l s ou s e t op r e d i c tt h ef u t u r et r e n d s d e c i s i o nt r e ei sat y p i c a lc l a s s i f i c a t i o na l g o r i t h m ，i tc a nr e a s o no u t c l a s s i f i c a t i o nr u l e so fd e c i s i o nt r e ef o r mf r o mo n eg r o u p1 1 0o r d e ra n do nr u l e sc a s e s o l ed bf o rd mn o r mi sas e to fa p i t h a ti ti sp r o p o s e db ym i c r o s o f tf o rt h ed a t am i n i n g m a r k e tt op r o v i d ea ni n d u s t r ys t a n d a r d ，d a t a b a s ea p p l i c a t i o nd e v e l o p e r sc a l ls t r u c t u r ed a t a m i n i n gm o d e l si nt h e i rd a t a b a s e sb yo l e d bf o rd m n o r l l l ，t h e yu s et h e s em o d e l st oc o m p l e t ea l a r g ea m o u n to fp r e d i c t i o na n da n a l y s i sm i s s i o n ，a n dt h e s em o d e l sc a nb es h a r e dw i t ho t h e r a p p l i c a t i o n s t h i sp a p e ra n a l y s i sc o n t i n u o u sh o t r o l l e dm i l l sd a t a , u s i n gs q ls e r v e rd a t am i n i n g s o l u t i o n st og e n e r a t ed e c i s i o nt r e e sb yc o m b i n i n gw i t hv i s u a lc + + 6 0a n do l ed bf o rd m n o r m ，a s t o r a g em o d e lo fd e c i s i o nt r e er u l e sb a s e do nr e l a t i o n a ld a t a b a s ea n dt h er u l ee x t r a c t i o n m e t h o db r i n gf o r w a r da c c o r d a n c ew i t ht h ec h a r a c t e r i s t i c so fd e c i s i o n - m a k i n gp r o d u c t i o nr u l e s i t s e l f t h em e t h o d so fa p p l i c a t i o nm o d e la n dt h ep r o c e s so fd a t am i n i n gs y s t e mi nt h ep a p e r a r e v e r yu s e f u lt od e s i g na n d t oi m p l e m e n td a t am i n i n gb a s e do ns q ls e r v e r k e y w o r d s ：d a t am i n i n g ，d e c i s i o nt r e e ，p r o d u c t i o n ，r u l er u l e se x t r a c t i o n ，o l ed bf o rd m ， s q l s e r v e r 武汉科技大学 研究生学位论文创新性声明 本人郑重声明：所呈交的学位论文是本人在导师指导下，独立进行研 究所取得的成果。除了文中已经注明引用的内容或属合作研究共同完成的 工作外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 论文作者签名： 日期：骅 研究生学位论文版权使用授权声明 本论文的研究成果归武汉科技大学所有，其研究内容不得以其它单位 ： 的名义发表。本人完全了解武汉科技大学有关保留、使用学位论文的规定， 同意学校保留并向有关部门( 按照武汉科技大学关于研究生学位论文收录 工作的规定执行) 送交论文的复印件和电子版本，允许论文被查阅和借阅， 同意学校将本论文的全部或部分内容编入学校认可的国家相关数据库进行 检索和对外服务。 论文作者签名： 指导教师签名： 日期： 武汉科技大学硕士学位论文第1 页 第一章绪论 本章介绍了论文的选题背景、主要研究内容和工作，并给出了文章的结构安排。 1 1 本课题的选题来源 数据库技术的迅速发展以及数据库管理系统的广泛应用，导致人们积累了越来越多的 数据。剧增的数据背后蕴藏着丰富的知识，而目前的数据库技术虽可以高效地实现数据的 查询、统计等功能，却无法发现数据中存在的关系和规则，更无法根据现有的数据预测未 来的发展趋势。也就是说数据库中存在着大量的数据，人们却缺乏挖掘数据背后隐藏的知 识的手段，出现了“数据爆炸而知识贫乏”的现象。面对这一挑战，数据挖掘和知识发现技 术应运而生，并逐渐显示出强大的生命力。数据挖掘和知识发现使数据处理技术进入了一 个更高级的阶段。它不仅能对过去的数据进行查询，而且能够找出过去数据之问的潜在联 系，从而进行更高层次的分析，以便更好地解决决策、预测等问题。 在完成国家8 6 3 课题“热连轧精轧机组终轧温度及厚度多变量预测控制”中，我们对精 轧机组终轧温度的控制精度将直接影响到最终热轧带钢产品的组织性能，精轧出口带钢厚 度精度也是提高热轧产品质量的主要指标；终轧温度的控制精度，对各精轧机架的轧制力 和负荷分配有直接影响，从而也影响精轧出口带钢厚度的控制精度。生产过程中，影响精 轧终轧温度的因素众多，为了稳定精确地控制精轧机组带钢全长终轧温度和出口厚度，我 们要对现场数据库中的大量实际生产数据进行分析。 本课题应用s q ls e r v e r 数据挖掘解决方案对热轧数据进行分析处理，在生成决策树的 基础上，设计并开发出了实用性较强的、基于关系型数据库的产生式决策规则存储模型， 规则的提取简单通用，为课题后续的开展提供了决策支持。 1 2 本文主要研究内容和所做工作 本文主要研究内容包括数据挖掘的主要算法，决策树产生式规则存储和提取方法以及 s q ls e r v e r 数据挖掘解决方案的应用。 本文介绍了数据挖掘技术的相关概念，研究了如何借助s q ls e r v e r 数据挖掘解决方案 对数据进行有效分析的方法。在此基础上，独立设计并实现了基于关系数据库的决策树产 生式规则存储和提耿方法，并给出了具体设计步骤和相关效果图。 实验结果表明，借助于s q ls e r v e r 数据挖掘解决方案，可缩短数据挖掘系统应用模型 的设计周期，提高丌发工作效率。笔者利用s q ls e r v e r 数据挖掘解决方案和热轧数据资源， 设计并开发的实用性较强的决策规则存储模型，为本课题的后续工作开展提供了有效的决 策支持。该方法对设计与开发基于s q ls e r v e r 数据挖掘的相关应用系统具有一定的参考价 值。 第2 页武汉科技大学硕士学位论文 1 3 本文的组织和结构 论文各章节内容安排如下： 第一章：绪论论述了论文研究的背景和选题来源、研究内容和工作。 第二章：数据挖掘技术介绍了数据挖掘的概念和过程、数据挖掘相关算法以及国内 外数据挖掘的研究现状和发展方向。 第三章：决策树分类方法介绍了分类的概念和过程，决策树算法生成和修剪的基本 原理以及对比了常用决策树算法。 第四章：s q ls e r v e r 数据挖掘解决方案介绍了o l ed bf o rd m 规范的相关概念和 m i c r o s o t t 决策树的基本原理和概念。 第五章：热轧数据的分析详细介绍了运用s q ls e r v e r 数据挖掘解决方案生成决策树 的过程，依据决策产生式规则自身特点，设计与实现了基于关系型数据库的决策规则存储 模型，以及规则的提取与显示。 第六章：总结和展望介绍了本文研究的总结、论文创新之处，需要完善之处和下一 步的工作重点。 武汉科技大学硕士学位论文第3 页 第二章数据挖掘技术 本章介绍了数据挖掘技术的基本概念、任务、过程、关键方法以及国内外研究现状和 发展方向。本章内容是基于数据挖掘系统设计和开发的基础。 2 1 数据挖掘的定义 数据挖掘是指从数据集合中自动抽取隐藏在其中的那些有用信息的非平凡过程。这些 信息的表现形式为：规则、概念、规律及模式等。数据挖掘可帮助决策者分析历史数据及 当前数据，并从中发现隐藏的关系和模式，进而预测未来可能发生的行为。数据挖掘的过 程也称为知识发现的过程，它是一门涉及面很广的交叉性新兴学科，涉及到数据库、人工 智能、数理统计、可视化、并行计算等领域。数据挖掘是一种新的信息处理技术，其主要 特点是对数据库中的大量数据进行抽取、转换、分析和其他模型化处理，并从中提取辅助 决策的关键性数据。数据挖掘是k d d ( 1 ( n o w l e d g ed i s c 0 v e r yi nd a t a b m e ) 中的重要技术， 它并不是用规范的数据库查询语言( 如s q l ) 进行查询，而是对查询的内容进行模式的总 结和内在规律的搜索。传统的查询和报表处理只是得到事件发生的结果，并没有深入研究 发生的原因，而数据挖掘则主要了解发生的原因，并且以一定的置信度对未来进行预测， 用于为决策行为提供有利的支持。 通常数据挖掘被视作以提取有用信息为目的的“数据簇聚”或“数据产生”过程，数据为 信息处理者提取新的和有用的规则服务，并能够根据已有的信息对实际未发生行为的结果 做出预测。数据挖掘是从大量数据中挖掘出隐含的、先前未知的、对决策有潜在价值的知 识和规则【i 】。这些规则蕴含了数据库中一组对象之间的特定联系，揭示出一些有用的信息， 为经营决策、市场策划、经营预测、工业控制提供依据。通过数据挖掘，有价值的知识、 规则或高层次的信息就能从数据库的相关数据集合中抽取出来，并从不同角度显示，从而 使大型数据库作为一个丰富可靠的资源为知识归纳服务。与传统信息处理方法相比，数据 挖掘技术有其自身的特剧1 】【2 】【3 】【5 】： 1 ) 处理对象为大规模数据库，数据规模十分巨大； 2 ) 信息查询一般是由决策制定者( 用户) 提出的即时随机查询，往往没有精确的查询要 求，需要靠数据挖掘技术寻找其可能感兴趣的东西； 3 ) 在些应用中，某些行动并没有实际发生或很少发生，因而它们对输出所造成的影 响没有在数据库中体现出来，需要利用数据挖掘技术从数据库中提取有用的规则，为这种 情况提出预测； 4 ) 在一些应用中，由于数据变化迅速可能很快过时，因此要求数据挖掘技术能快速对 数据变化做出反应以提供决策支持。数据挖掘既要发现潜在的规则，还要管理和维护规则。 而规则是动态的，当前的规则只能反应当前状态的数据库特征，随着新数据的不断加入， 规则需要随之更新； 第4 页武汉科技大学硕士学位论文 5 ) 数据挖掘中规则的发现主要基于大样本的统计规律，发现的规则不必适用于所有的 数据，当达到某一阈值时便可认为有此规律。 2 2 数据挖掘的方法 数据挖掘的研究融合了多个不同学科领域的技术与成果，使得目前的数据挖掘方法表 现出多种多样的形式。从统计分析类的角度来说，统计分析技术中使用的数据挖掘模型有 线性分析和非线性分析、回归分析、逻辑回归分析、单变量分析、多变量分析、时间序列 分析、最近序列分析、最近邻算法和聚类分析等方法。利用这些技术可以检查那些异常形 式的数据，然后，利用各种统计模型和数学模型解释这些数据，解释隐藏在这些数据背后 的市场规律和商业机会。知识发现类数据挖掘技术是一种与统计分析类数据挖掘技术完全 不同的挖掘技术，包括人工神经元网络、支持向量机、决策树、遗传算法、粗糙集、规则 发现和关联顺序等【6 】【7 】【8 1 。 2 2 1 统计方法 传统的统计学为数据挖掘提供了许多判别和回归分析方法，常用的有贝叶斯推理、回 归分析、方差分析等技术。贝叶斯推理是在知道新的信息后修j 下数据集概率分布的基本工 具，处理数据挖掘中的分类问题；回归分析用来找到一个输入变量和输出变量关系的最佳 模型，在回归分析中有用来描述一个变量的变化趋势和别的变量值关系的线性回归，还有 用来为某些事件发生的概率建模，为预测变量集的对数回归；统计方法中的方差分析一般 用于分析估计回归直线的性能和自变量对最终回归的影响，是许多数据挖掘应用中有力的 工具之一。 2 2 2 关联规则 关联规则是一种简单，实用的分析规则，它描述了一个事物中某些属性同时出现的规 律和模式，是数据挖掘中最成熟的主要技术之一。它是由r a g r a w a l 等人首先提出的，最经 典的关联规则的挖掘算法是a p d o n ，该算法先挖出所有的频繁项集，然后，由频繁项集产 生关联规则，许多关联规则频繁项集的挖掘算法都是由它演变而来的。关联规则在数据挖 掘领域应用很广泛适合于在大型数据集中发现数据之间的有意义关系，原因之一是它不受 只选择一个因变量的限制，关联规则在数据挖掘领域最典型的应用是购物篮分析。大多数 关联规则挖掘算法能够无遗漏发现隐藏在所挖掘数据中的所有关联关系，所挖掘出的关联 规则量往往非常巨大，但是，并不是所有通过关联得到的属性之间的关系都有实际应用价 值，对这些关联规则进行有效的评价，筛选出用户真正感兴趣的有意义的关联规则尤为重 要。 武汉科技大学硕士学位论文第5 页 2 2 3 聚类分析 聚类分析是根据所选样本间关联的标准将其划分成几个组，同组内的样本具有较高的 相似度，不同组的则相异，常用的技术有分裂算法，凝聚算法，划分聚类和增量聚类。聚 类方法适合于探讨样本间的内部关系，从而对样本结构做出合理的评价。此外，聚类分析 还用于对孤立点的检测。有时进行聚类不是为了将对象相聚在一起，而是为了更容易地使 某个对象从其他对象中分离出来。聚类分析已被应用于经济分析、模式识别、图像处理等 多种领域，尤其在商业上，聚类分析可以帮助市场人员发现顾客群中所存在的不同特征组 群。聚类分析的技术关键除了算法的选择之外，就是对样本的度量标准的选择。并非由聚 类分析算法得到的类对决策都有效，在运用某一个算法之前，一般要先对数据的聚类趋势 进行检验。 2 2 4 决策树方法 决策树学习是一种通过逼近离散值目标函数的方法，通过把实例从根节点排列到某个 叶子节点来分类实例，叶子节点即为实例所属的分类。树上的每个结点说明了对实例的某 个属性的测试，该结点的每一个后继分支对应于该属性的一个可能值，分类实例的方法是 从这棵树的根节点丌始，测试这个结点指定的属性，然后按照给定实例的该属性值对应的 树枝向下移动。决策树方法应用于数据挖掘的分类方面。 2 2 5 神经网络法 神经网络建立在自学习的数学模型基础之上；能够对大量复杂的数据进行分析，并可 以完成对人脑或其他计算机来说极为复杂的模式抽取及趋势分析。神经网络既可以表现为 有指导的学习也可以是无指导聚类，无论哪一种，输入到神经网络中的值都是数值型的。 人工神经元网络模拟人脑神经元结构，以m p 模型和h e b b 学习规则为基础，建立三大类多 种神经元网络，具有非线性映射特性、信息的分布存储、并行处理和全局集体的作用、高 度的自学习、自组织和自适应能力的种种优点。前馈神经元网络以感知器网络、b p 网络等 为代表，可以用于分类和预测等方面；反馈式网络以h o p f i e l d 网络为代表，用于联想记忆和 优化计算；自组织网络以u 汀模型、k o h o n o n 模型为代表，用于聚类【4 j 。 2 2 6 遗传算法 遗传算法是一种受生物进化启发的学习方法，通过变异和重组当前己知的最好假设来 生成后续的假设。每一步，通过使用目前适应性最高的假设的后代替代群体的某个部分， 来更新当前群体的一组假设，来实现各个个体的适应性的提高。遗传算法由三个基本过程 组成：繁殖( 选择) 是从一个旧种群( 父代) 选出生命力强的个体，产生新种群( 后代) 的过程；交叉( 重组) 选择两个不同个体( 染色体) 的部分( 基因) 进行交换，形成新个 体的过程；变异( 突变) 是对某些个体的某些基因进行变异的过程。在数据挖掘中，可以 第6 页武汉科技大学硕士学位论文 被用作评估其他算法的适合度。 2 2 7 粗糙集法 粗糙集能够在缺少关于数据先验知识的情况下，只以考察数据的分类能力为基础，解 决模糊或不确定数据的分析和处理问题。粗糙集用于从数据库中发现分类规则的基本思想 是将数据库中的属性分为条件属性和结论属性，对数据库中的元组根据各个属性不同的属 性值分成相应的子集，然后对条件属性划分的子集与结论属性划分的子集之间上下近似关 系生成判定规则。所有相似对象的集合称为初等集合，形成知识的基本成分。任何初等集 合的并集称为精确集，否则，一个集合就是粗糙的( 不精确的) 。每个粗糙集都具有边界元 素，也就是那些既不能确定为集合元素，也不能确定为集合补集元素的元素。粗糙集理论 可以应用于数据挖掘中的分类、发现不准确数据或噪声数据内在的结构联系。 2 2 8 支持向量机法 支持向量机( s v m ) 是在统计学习理论的基础上发展出来的一种新的机器学习方法。它 基于结构风险最小化原则，尽量提高学习机的泛化能力，具有良好的推广性能和较好的分 类精确性，能有效地解决过学习问题，现已成为训练多层感知器、r b f 神经网络和多项式 神经元网络的替代性方法。另外，支持向量机算法是一个凸优化问题，局部最优解一定是 全局最优解，这些特点都是包括神经元网络在内的其它算法所不能及的。支持向量机可以 应用于数据挖掘的分类、回归、对未知事物的探索等方面。 除上述方法外，还有把数据与结果转化和表达成可视化技术、云模型方法和归纳逻辑 程序等方法。 、： 事实上，任何一种挖掘工具往往是根据具体问题来选择合适挖掘方法，很难说哪种方 法好，那种方法劣，而是视具体问题而定。 2 3 数据挖掘的过程 数据挖掘过程包括很多处理阶段的复杂处理过程，其一般流程主要包括三个阶段：数 据准备、数据挖掘、结果解释和评价【4 2 1 。图2 1 是u s a m am f r y y a d 等人给出的一个典型的 数据挖掘处理过程模型。 武汉科技大学硕士学位论文第7 页 图2 1 数据挖掘处理过程图 在整个过程中包括很多处理阶段，其突出特点是阶梯状递进的。按照u s 锄am f 删 的最初设计，主要有九个处理阶段，这九个处理阶段分别是数据准备、数据选择、数据预 处理、数据缩减、l d 目标确定、挖掘算法确定、数据挖掘、模式解释及知识评价。 1 ) 数据准备：了解l d 相关领域的有关情况，熟悉有关的背景知识，并弄清楚用户的 要求，确定挖掘的总体目标和方法。了解相关的源数据结构并加以分析，确定数据选择的 原则： 2 ) 数据选择：根据用户的要求从数据库中提取与l d 目标相关的数据。在此过程中， l d 系统将从各选的源数据中进行知识提取。这种数据选择工作可以借助于数据库操作语 言或专门的工具来进行； 3 ) 数据预处理：主要是对上一阶段产生的数据进行再加工，检查数据的完整性及数据 的一致性，对其中的噪声数据进行处理，对丢失的数据可以利用统计方法进行填补。对一 些不适合于操作的数据进行必要的处理等； 4 ) 数据缩减：对经过预处理的数据，根据知识发现的任务对数据进行必要的再处理， 使数据集中在用户的挖掘目标上。此过程对l d 系统的精度和效率起着至关重要的作用。 它也可以通过数据库中的投影等相关操作或专门的工具来完成； 5 ) l d 目标确定：根据挖掘的目标和用户的要求，确定l d 所发现的具体知识模式和 类型，为选择或开发适合用户要求的数据挖掘算法提供模式或模板； 6 ) 挖掘算法确定：根据上一阶段所确定的模式，选择合适的数据挖掘算法，这包括选 取合适的参数、知识表示方式，并保证数据挖掘算法与整个k d d 的评判标准相一致： 7 ) 数据挖掘：运用选定的算法，从数据中提取出用户所需要的知识。这些知识可以用 一种特定的方式表示或使用一些常用的表示方式，如产生式规则等； 8 1 模式解释：对发现的模式进行解释。在此过程中，为了取得更为有效的知识，可能 会返回前面处理步骤中的某些步加以改进结果，保证提取出的知识是有效的和可用的； 第8 页武汉科技大学硕士学位论文 9 ) 知识评价：将发现的知识以用户能了解的方式呈现给用户。这期间也包含对知识的 一致性的检查，以确信本次发现的知识与以前发现的知识不相抵触。 可以看出，以上整个数据挖掘过程是不断地循环和反复的，因而可以对所挖掘出来的 知识不断求精和深化，最终达到用户所满意的结果。 2 4 数据挖掘系统的体系结构 在常用的数据挖掘系统中，一般将其分为三层结构，如图2 2 所示。其中，第一层是 数据源，包括数据库、数据仓库等。第二层是挖掘器，利用数据挖掘系统提供的各种数据 挖掘方法分析和提取数据库中的数据，以达到用户的需求。第三层是用户层，使用多种方 式将获取的信息和发现的知识反馈给用户。 2 5 数据挖掘技术现状和发展方向 图2 2 数据挖掘系统体系结构 2 5 1 国内外数据挖掘技术的研究现状 经过十几年的研究和实践，数据挖掘技术已经吸收了许多学科的最新研究成果，从而 形成了独具特色的研究分支。毋庸置疑，数据挖掘研究和应用具有很大的挑战性。像其他 新技术的发展历程一样，数据挖掘也必须经过概念的提出、概念的接受、广泛研究和探索、 逐步应用和大量应用等阶段。从目前的现状看，大部分学者认为数据挖掘的研究仍然处于 广泛研究和探索阶段。一方面，数据挖掘的概念已经被广泛接受。在理论上，一批具有挑 战性和前瞻性的问题被提出，吸引了越来越多的研究者：另一方面，数据挖掘的大面积广 泛应用还有待时同，需要深入的研究积累和丰富的工程实践。 数据挖掘的概念从2 0 世纪8 0 年代被提出后，其经济价值就已经显现出来，而且被众 多商业厂家所推崇，形成初步的市场。一份最近的g a r t n e r 报告中列举了在今后3 5 年内 图园图 武汉科技大学硕士学位论文第9 页 对工业将产生重要影响的五项关键技术，其中数据挖掘和人工智能排名第一。同时，这份 报告将并行计算机体系结构研究和数据挖掘列入今后5 年内公司应该投资的1 0 个新技术 领域。另一方面。目前的数据挖掘系统也绝不是像一些商家为了宣传自己的商品所说的那 样神奇，仍有许多问题需要研究和探索。把目前数据挖掘的研究现状描述为鸿沟( c h u m ) 阶段是比较准确的。所谓c h u m 阶段是说数据挖掘技术在广泛被应用之前仍有许多“鸿沟 需要跨越。例如，就目前商家推出的数据挖掘系统而言，它们都是一些通用的辅助开发工 具。这些工具只能给那些熟悉数据挖掘技术的专家或高级技术人员使用，仅对专业人员的 开发应用起到加速或横向解决方案( h o f i z o n t a ls o l u t i o n ) 的作用。但是，数据挖掘来自于 商业应用，而商业应用又会由于应用的领域不同而存在很大差异。大多数学者赞成这样的 观点：数据挖掘在商业上的成功不能期望通过通用的辅助丌发工具，而应该是数据挖掘概 念与特定领域商业逻辑相结合的纵向解决方案( n i c a ls o l m i o n ) 。 随着数据挖掘概念在学术界和工业界的影响越来越大，数据挖掘的研究向着更深入和 更实用的技术方向发展。从事数据挖掘研究的人员主要在大学、研究机构，也有部分在企 业或公司。所涉及的研究领域很多，研究集中在学习算法的研究、数据挖掘的实际应用以 及有关数据挖掘理论等方面。进行的大多数基础研究项目是由政府资助进行的，而公司的 研究更注重和时间商业问题相结合。 2 5 2 数据挖掘技术的发展方向 在分析了目前国内外的研究和应用现状后，我们得知数据挖掘应在如下几个方面重点 开展工作。 数据挖掘技术与特定商业逻辑的平滑继承问题：一方面，数据挖掘技术需要有效的 应用实例来证明；另一方面，数据挖掘技术只有和实际的商业逻辑融合才能从根本上解决 问题。 数据挖掘技术与特定数据存储类型的适应问题：不同的数据存储方式会影响数据挖 掘的具体实现机制、目标定位和技术有效性等。针对不同数据存储类型的特点，进行针对 性研究是将来一段时间所必须面对的问题。 大型数据的选择与规格化问题：数据挖掘技术必须面对大容量数据集，与之相适应 的，一系列在挖掘前的预处理( 如数据清洗、数据选择等) 工作是必须的。同时，针对特 定挖掘方法进行数据规格化也是一个无法避免的问题。 数据挖掘系统的构架与交互式挖掘技术：受应用领域、挖掘数据类型以及知识表达 模式等的影响，数据挖掘应用系统需要在一般性构架和结合具体应用特点两个方面开展工 作。良好的交互式挖掘也是数据挖掘系统成功的关键。 数据挖掘语言与系统的可视化问题：对于数据挖掘技术而言，丌发相应的数据挖掘 操作语言是一件极具挑战性的工作。从某种意义上说，挖掘语言是数据挖掘系统的关键， 它制约着数据挖掘应用的深度。数据的可视化从某种角度说起到了推动人们主动进行知识 发现的作用，因为它可以是人们对l d 的神秘感受变成可以直观理解的知识和形象的过 第l o 页武汉科技大学硕士学位论文 程。 数据挖掘理论与算法研究：一方面，十几年的研究探索出了许多独具特色的数据挖 掘理论体系；另一方面，需要更深入的新颖理论和算法来促进研究和应用的发展。 武汉科技大学硕士学位论文第1 1 页 第三章决策树分类方法 决策树( d e c i s i o nt r e e ) 技术是一种对海量数据集进行分类的非常有效的方法。通过 构造决策树模型，提取有价值的分类规则，帮助决策者做出准确的预测已经应用在很多领 域。 3 1 分类概述 分类( c l a s s i f i c a t i o n ) 在数据挖掘中是一项非常重要的任务。分类的目的是构造一个分 类函数或分类模型( 也称分类器) ，通过分类模型，把数据库中的元组映射到给定类别中的 某一个，即要发现一些指定的数据对象是否属于某一特定的数据子集的规则。一般把分类 模型的输入称做“训练集，它的每一元组的属性和数据库的元组的属性相同，并且每个 元组都有一个类别标志。训练集的样本个体的类别属性标志是己知的，分类发现的任务就 是根据从训练样本数据的属性中发现个体或对象的一般分类规则，从而根据该规则对非样 本数据进行分类。分类具有广泛的应用，例如欺诈检测、针对销售、信用卡系统中的信用 分级、市场调查、疗效诊断等等【4 引。 分类器的构造方法有统计方法、机器学习方法和神经网络方法等。 统计方法：包括贝叶斯法和非参数法等。常见的临近学习或基于事例的学习 ( i n s t a n c e b a s e dl e a r n i n g ，i b l ) 属于非参数方法。对应的知识表示则为判断函数和原型 事例( 原型事例即有代表性的典型的记录，它的表示是原始记录形式) 。 - 机器学习方法：包括决策树法和规则归纳法。前者对应的表示为决策树或判别树， 后者则有决策表( d e c i s i o nl i s t ) 和产生式规则等。 神经网络方法：主要是b p 算法，它的模型表示是前向反馈神经网络模型( 由代表 神经元的结点和代表联接权值的边组成的一种体系结构) ，b p 算法本质上是一种非线性判 别函数。 3 1 1 分类的过程 分类的处理过程分为分类模型的建立和分类模型的应用两个阶段，如图3 1 所示。 第1 2 页 武汉科技大学硕士学位论文 图3 1 分类的处理过程步骤。 ( 1 ) 分类模型的建立 第一阶段就是要建立一个模型，描述预定的数据类或概念集。在该阶段中，通过分析 训练样本数据来完成分类模型的建立。训练样本数据中的每一个样本属于一个事先定义好 的类，这个事先定义好的类是由一个特定属性来标识的，称该属性为类别标识属性( c i a s s l a b e la t t f i b u t e ) 。由于提供了每一个训练样本的类别标号，这个阶段也称为有指导的学习( 即 在被告知每个训练样本属于哪个类的指导下进行模型的学习) 。与无指导的学习( 如聚类) 不 同，每个训练样本的类标号是未知的，要学习的类集合和数量也可能事先不知道。一般情 况下，分类模型以分类规则、决策树或数学公式的方式给出，该规则可以用来为以后的数 据样本分类，也能对数据库的内容提供更好的解释。 ( 2 ) 使用模型进行分类 在使用建立的分类模型进行分类前，要首先对建立的模型进行评估，在确保分类模型 的准确性和精确度的情况下，才能使用该模型对未知类别的数据样本进行分类处理。 3 1 2 分类模型的评估 利用训练集归纳学习获得一个分类模型并利用训练数据对其预测正确率进行估计，将 会得到一个过分乐观且具有误导性的评估结果。因为一般归纳学习算法都倾向于过分近似 所要学习的数据样本，保持方法和交叉验证是两种常用评估分类模型预测准确率的方法。 它们都是通过在给定数据集中随机取样来划分数据。 ( 1 ) 保持( h o l d o u t ) 法 在保持方法中，将给定数据集随机地划分成两个独立的集合：训练集和测试集。通常， 随机选取数据集的2 3 作为训练集，而剩余的l 厂3 被用作测试集。利用训练集数据学习获 得一个分类模型；然后使用测试集对该分类模型的预测准确率进行评估，得出的错误率就 是评估错误率。这种方法虽然速度很快，但是由于仅仅使用一部分数据构造分类模型，并 没有充分利用所有的数据来进行学习，因此对所得分类模型预测准确性的估计是悲观的。 如果使用所有的数据，可能可以构造出更精确的分类模型。 ( 2 ) k 交叉确认法( k f o l dr o s s v a l i d a t i o nm e t h o d ) 武汉科技大学硕士学位论文第1 3 页 交叉验证方法是保持方法的一种演化，它是重复利用保持方法进行预测准确率估计k 次，最后对这k 次所得的预测准确率求平均值，即为最终获得的预测准确率。具体地说， 交叉验证法是将数据集分成k 个互不相交的子集，每个子集大小基本相同。学习和测试分 别循环进行k 次，每一次都使用其中一个子集作为测试集，而用其余的k 1 个子集的并集 作为训练集。而对整个数据集所得分类模型的准确率估计，则可用k 次循环中所得的正确 分类数目之和除以数据集的大小来获得。 交叉验证法可以被重复t 次( 萨1 ) ，对于一个t 次k 分的交叉验证法，k * t 个分类模型 被构造和评估。这意味着交叉验证法的时间是分类模型构造时问的k * t 倍。通常地，k = 1 0 ， t = l 时，交叉验证法大约要花掉构造单个分类模型l o 倍的时问。增加重复的次数意味着运 行时间的增长和准确率评估的改善。可以对k 的值进行调整，将它减少到3 或5 ，这样可 以缩短运行时间。然而，减小训练集有可能使得评估产生更大的偏差。也可以增大k ，但 通常只有在数据集小的时候才这么做。一般地，保持评估方法常用在最初试验性的场合， 或者比较大的数据集；交叉验证法则应用于建立最终的分类模型，或者较小的数据集。 3 2 决策树方法 从数据中生成分类器的一个特别有效的方法是生成一个决策树( d e c i s i o nt r e e ) 。所谓 决策树【1 0 】【l l 】【1 2 】【1 3 】【1 4 】【1 5 1 就是一个类似流程图的树型结构，其中树的每个内部节点代表对一 个属性的测试，其分支就代表测试的每个结果，而树的每个叶节点就代表一个类别，树的 最高层节点就是根节点，是整个决策树的开始。决策树表示方法是应用最广泛的逻辑方法 之一，它从一组无次序、无规则的事例中推理出决策树表示形式的分类规则。决策树分类 方法采用自顶向下的递归方式，在决策树的内部结点进行属性值的比较并根据不同的属性 。值判断从该结点向下的分支，在决策树的叶节点得到结论。所以从决策树的根到叶节点的 一条路径就对应着一条合取规则，整棵决策树就对应着一组析取表达式规则。基于决策树 的分类算法的一个最大优点就是它在学习过程中不需要使用者了解很多背景知识( 这同时 也是它的最大缺点) ，只要训练例子能够用属性结论式表示出来，就能使用该算法来学习 【4 6 】 o 决策树分为分类树和回归树两种【1 6 1 ，分类树对离散变量做决策树，回归树对连续变量 做决策树。一般的数据挖掘工具，允许选择分裂条件和修剪规则，以及控制参数( 最小节点 的大小，最大树的深度等等) 来限制决策树。决策树作为一棵树，树的根节点是整个数据集 合空间，每个分节点是对一个单一变量的测试，该测试将数据集合空间分割成两个或更多 块。每个叶节点是属于单一类别的记录。构造决策树的过程为：首先寻找初始分裂。整个 训练集作为产生决策树的集合，训练集每个记录必须是已经分好类的。决定哪个属性域 ( f i e l d ) 作为目前最好的分类指标。一般的做法是穷尽所有的属性域，对每个属性域分裂的 好坏做出量化，计算出最好的一个分裂。不同的算法的计算属性域分裂的标准也不太相同。 其次，重复第一步，直至每个叶节点内的记录都属于同一类，增长到一棵完整的树。构造 决策树的目的是找出属性和类别间的关系，用它来预测将来未知类别的记录的类别。这种 第1 4 页武汉科技大学硕士学位论文 具有预测功能的系统叫做决策树分类器。 图3 2 决策树示意图 图3 2 是一棵典型的决策树，它表示概念b u y s ，它预测顾客是否可能购买计 算机。每个内部节点( 方形框) 代表对某个属性的一次_ c o 检m p 测u t 。e r 每片叶子( 椭圆框) 代表一个类 ( b u y s _ c o m p u t e r = y e s 或者b u y s _ c o m p u t e r = n o ) 。这个例子中，训练集的样本向量格式如下： ( a g e ，s t u d e n t ，c r e d i t _ r a t i n g ，b u y s _ c o m p u t e r ) 待预测的样本向量格式如下：( a g e ，s t u d e n t ，c r e d i tr a t i n g ) 如果输入待预测的样本为( a g e = 2 5 ，s t u d e n t = y e s ，c r e d i tr a t i n g = f a i r ) ，可以预测该学生 可能购买计算机，即预测属性b u v sc o m p u t e r 的值为y e s 。 3 2 1 决策树基本算法概述 决策树分类算法通常分为两个步骤，决策树生成和决策树修剪。 1 ) 决策树生成算法 i 决策树生成算法的输入是一组带有类别标记的例子，构造的结果是一棵二叉树或多叉 树。二叉树的内部结点( 非叶子节点) 一般表示为一个逻辑判断，如形式为( a t i - - v i ) 的逻 辑判断，其中a i 是属性，v i 是该属性的某个属性值。树的边是逻辑判断的分支结果。多叉 树的内部结点是属性，边是该属性的所有取值，有几个属性值，就有几条边。树的叶子节 点都是类别标记。 决策树的构建是一种自上而下、分而治之的归纳过程，本质是贪心算法【4 5 】。从根节点 开始，对每个非叶节点，找出其对应样本集中的一个属性( 分裂属性) ，对样本集进行测试， 根据不同的测试结果将训练样本集划分成若干个子样本集，每个子样本集构成一个新叶节 点，对新叶节点再重复上述划分过程，这样不断循环，直至达到特定的终止条件。其中， 分裂属性的选择和如何划分样本集是构建决策树的关键环节。 下面给出决策树的生成算法，如图3 3 所示。 武汉科技大学硕士学位论文第1 5 页 决策树生成算法g e n e r a t e d e c i s i o n t r e e 输入：训练样本s a m p l e s ，由离散值属性表示；候选属性的集合a t t r i b u t e l i s t 。 输出：由给定的数据生成一棵决策树 ( 1 ) 创建结点n ； ( 2 ) i fs a m p l e s 都4 ：闷一个类ct h e n ( 3 ) 返i - in 作为叶结点，以类c 标记； ( 4 ) i fa t t r i b u t e l i s t 为窄t h e n ( 5 )返【口ln 作为叶结点，标记为s a m p l e s 中最普通的类； ( 6 ) 选择a t t r i b u t e l i s t 中具有最高信息增益的属性t e s t a t t r i b u t e ( 7 ) 标记结点n 为t e s t a t t r i b u t e ： ( 8 ) f o re a c ht e s t _ a t t r i b u t e 中的已知值a i 划分s a m p l e s ( 9 )由结点n 长h ：一个条件为t e s t a t t r i b u t e = a 。的分支； ( 1 0 ) 设s i 足s a m p l e s 中t e s t a t t r i b u t e = a i 的样本的集合； ( 1 1 ) i fs 。为窄t h e n ( 1 2 ) 加卜一个树