（应用数学专业论文）决策树方法在高考志愿分析中的应用研究.pdf

河南大学研究生硕士学位论文第1 页 摘要 数据挖掘技术可以透彻地对数据分析、清晰地对数据分类、完善地对数据汇 总、正确地发现和描述数据的趋势、明确地标记异常、敏锐地找出蕴藏在数据中 的有用信息，进而找到尚未发现的知识，据此指导人们的行为，为商业竞争、企 业生产和管理、政府部门决策以及科学探索等提供有效的参考信息。 分类是最常见的数据挖掘任务之一。其中，决策树归纳分类算法使用信息论 原理对大量实例的特征进行信息量分析、找出反映类别的重要特征、准确抓住问 题的本质，是一种最为行之有效的监督学习方法。决策树归纳分类方法显著的亮 点是对样本数量庞大的数据库效果尤其优越，这正是本文把其应用于高考信息处 理的理论依据。 以省为单位，每年高考志愿信息相关记录高达数百万条，分布存储在各地市 的多个数据库中，这些数据规模巨大，蕴涵丰富的决策信息和知识，开发这些宝 贵的信息资源，是服务高考录取工作，指导考生科学地填报志愿的一项重要任务； 是目前迫切需要解决的问题之一。 本文根据高考志愿数据的特点，在对其进行预处理的基础上，灵活运用c 4 5 算法生成非平衡数据集下的二叉决策树，融合规则提取、准确性评估等，对高考 志愿数据进行知识挖掘，获取其中规律性的潜在信息，结合最小二乘法构建高考 志愿录取预测模型，根据考生的成绩、科类、报考的专业和学校等特点对高考录 取情况进行分类和预测，得出高考录取相关规则，提供给考生进行进一步的决策 分析。 据此所开发的“高考志愿信息处理系统”通过对过去三年的河南省高考志愿 数据迸行实验测试，与当年高校实际录取情况分布基本吻合，有理由相信，这些 测试结果对来年考生在填报志愿时有着很好的参考价值。 关键词：数据挖掘；高考志愿分析；c 4 5 算法；非平衡数据集；最小二乘法 第1 | 页河南大学研究生硕士学位论文 a b s t r a c t d a t am i n i n gi su s e dt oa n a l y z ed a t ai n t e n s i v e l y , c l a s s i f yd a t ac l e a r l y , g a t h e rd a t a p e r f e c t l y , f i n da n dd e p i c td a t a st r e n da c c u r a t e l y , m a r ka b n o r m i t yd e f i n i t e l y , f i n do u t u s e f u li n f o r m a t i o ni nd a t a ，a n df i n du n d i s c o v e r e dk n o w l e d g e b yt h i s ，i tc o u l dd i r e c t p e o p l e sa c t i o na n do f f e re f f e c t i v er e f e r e n c et ob u s i n e s sc o m p e t i t i o n ，p r o d u c t i o na n d m a n a g e m e n to fc o r p o r a t i o n s ，g o v e r n m e n t sd e c i s i o n m a k i n ga n ds c i e n c ee x p l o r a t i o n c l a s s i f i c a t i o ni so n eo ft h em o s tf a m i l i a rd a t am i n i n g st a s k s u s i n go ft h et h e o r y o fi n f o r m a t i o n ，t h ea l g o r i t h mo fd e c i s i o nt r e e si n d u c t i o na n dc l a s s i f i c a t i o nc o u l dm a k e t h ea n a l y s i so fi n f o r m a t i o nc o n t e n t ，f i n dt h ei m p o r t a n tc h a r a c t e ro fc a t e g o r y r e f l e c t i o n ， a n ds e i z et h ee s s e n c eo fp r o b l e m se x a c t l y i ti sa ne f f e c t i v em e t h o do fs u p e r v i s i n g l e a r n i n g t h en o t a b l ep o i n to ft h ed e c i s i o nt r e e si n d u c t i o na n dc l a s s i f i c a t i o ni st h a tt h e e f f e c ti sm o r ea s c e n d a n tf o rd a t a b a s ew i t he n o r m o u ss a m p l e s t h i si st h ea c a d e m i cb a s e o fi t sa p p l i c a t i o no ni n f o r m a t i o nm a n a g e m e n to ft h ec o l l e g ee n t r a n c ee x a m i n a t i o n b yp r o v i n c e a sau n i t ，c o r r e l a t i v en o t e so fa n n u a l c o l l e g e e n t r a n c e e x a m i n a t i o n w i l l si n f o r m a t i o ni sm o r et h a nm i l l i o n s ，s t o r e di nm u l t i d a t a b a s e so fe v e r y a r e a s d i s p e r s e d l y n e d a t ai s e n o r m o u s ，c o n t a i n i n ga b u n d a n td e c i s i o n m a k i n g i n f o r m a t i o na n dk n o w l e d g e d e v e l o p i n gt h ep r e c i o u si n f o r m a t i o nr e s o u r c ei so n e i m p o r t a n tt a s ko fs e r v i n gt h ec o l l e g ee n t r a n c ee x a m i n a t i o na n di n s t r u c t i n ge x a m i n e eo f f i l l i n gi nw i l l ss c i e n t i f i c a l l y i ti so n eo ft h ep r o b l e m sw h i c hn e e ds e t t l i n gu r g e n t l ya t p r e s e n t b a s e do nc h a r a c t e r so ft h ec o l l e g ee n t r a n c ee x a m i n a t i o n sw i l l si n f o r m a t i o na n d t a k i n gp r e t r e a t m e n to ni t ，t h ep a p e rd e p i c t so fu s i n gc 4 5a l g o r i t h mn e a t l yf o rb u i l d i n g b i n a r yd e c i s i o nt r e eb a s e do nu n b a l a n c e dd a t a - s e t ，i n o s c u l a t i n gr u l e s e x t r a c t i n g , a n d v e r a c i t ye v a l u a t i o na n ds o o n i tc o u l dm a k ei n f o r m a t i o n - m i n i n gf o r t h ec o l l e g e e n t r a n c ee x a m i n a t i o n sw i l l si n f o r m a t i o n ，g e tl a t e n ti n f o r m a t i o no fo r d e r l i n e s s ，b u i l d t h ef o r e c a s tm o d e lo ft h ec o l l e g ee n t r a n c ee x a m i n a t i o n sw i l l sm a t r i c u l a t eb yl i n k i n g o fl e a s ts q u a r e sm e t h o d b yc h a r a c t e r so f g r a d e ，s u b j e c t ，r e q u e s t e ds p e c i a l t y , s c h o o la n d s oo na b o u te x a m i n e e ，i tc o u l dc l a s s i f ya n df o r e c a s tt h ec o l l e g ee n t r a n c ee x a m i n a t i o n m a t r i c u l a t ei n f o r m a t i o n ，g e tc o r r e l a t i v er u l e so ft h ec o l l e g ee n t r a n c ee x a m i n a t i o n s m a t r i c u l a t ew h i c ha r ep r o v i d e dt oe x a m i n e ef o rt a k i n gd e c i s i o n a n a l y s i su l t e r i o r l y b a s e do nt h ea b o v et h e o r y , t h ed e v e l o p e ds y s t e mc a l l e d t h ec o l l e g ee n t r a n c e e x a m i n a t i o n sw i l l si n f o r m a t i o nm a n a g e m e n ts y s t e m h a se x p e r i m e n t i z e do nd a t ao f 河南大学研究生硕士学位论文第1 ll 页 t h ec o l l e g ee n t r a n c ee x a m i n a t i o n sw i l l si n f o r m a t i o no fh e n a np r o v i n c eo fl a s tt h r e e y e a r s 。t h er e s u l t i si n o s c u l a t e dw i t ht h ed i s t r i b u t i o no ft h ec o l l e g ee n t r a n c e e x a m i n a t i o na c t u a lm a t r i c u l a t ei n f o r m a t i o no ft h a ty e a r t h e r e f o r e ，i ti sr e a l l ys u r et h a t t h et e s t i n gr e s u l t s ，a st h ee f f e c t i v er e f e r e n c ev a l u e ，a r eg o o dt oe x a m i n e eo ft h ec o m i n g y e a rf o rf i l l i n gi nw i l l s 。 k e y w o r d s ：d a t am i n i n g ；a n a l y s i so fc o l l e g ee x a m i n e e si nw i l l - d e c i d i n gb e f o r e e n t r a n c ee x a m i n a t i o n ；u n b a l a n c e dd a t a 。s e t ；1 e a s ts q u a r e sm e t h o d ；c 4 5a l g o r i t h m 关于学位论文独立完成和内容创新的声明 本人向河南大学提出硕士学位中请。本人郑重声明：所呈交的学位论文是 本人在导师的指导下独立完成的，对所研究的课题有新的见解? 据我所知，除 文中特别加以说明、标注和致谢的地方外，论文中不包括其他入已经发表或撰 写过的研究成果，也不包括其他人为获得任何教育、科研机构的学位或证书而 段保存、汇编学位论文( 纸质文本和电子文本) 。 ( 涉及保密肉容的学位论文在解密后适用本授权书) 学位获得者( 学位论文作者) 签名： 2 0 学位论文指导教师签名： 星主：红： 呐o - ? 年占a 如 河南大学研究生硕士学位论文第1 页 第1 章绪论 当前数据挖掘技术已经取得了长足的发展，并被大量应用于国内外很多领域 【l 】。但是鉴于我国高等教育入学考试的特殊性，尚未把此技术应用于高考志愿信息 的分析中。本文针对考生及学校相关数据的特点，灵活运用c 4 5 算法 2 1 1 3 1 1 4 生成非 平衡数据剿5 】下的二叉决策树，满足了高考志愿分析的需要，并且得出丰富的决策 信息，用于指导考生科学的填报志愿。在此对论文的研究背景、研究意义、课题 来源以及论文的整体结构给以简要介绍。 1 1 研究背景 将决策树分类算法 0 3 【1 0 】应用于高考志愿分析中主要有如下四个原因： l 、高考志愿数据已形成数据仓库l l i 】 以河南省2 0 0 5 年高考为例，我省高考考生相关记录高达6 0 0 多万条，分布存 储在各级服务器的数据库中，经过传输、汇总、集中到河南省招办，然后通过进 行重组，采用新的数据组织模式，构成了一个面向主题的、集成的、与时间相关 且不可修改的数据集合。经过上述过程，高考志愿数据已经便于数据挖掘者使用 数据挖掘方法进行多角度的查询与统计、深层次的分析处理以及知识提取。 2 、决策树算法尚未应用到高考志愿分析中 每年高考考生由于志愿填报不当而未能就读理想学校、专业甚至落榜的现象 十分普遍【1 2 】。目前现有的高考志愿分析系统如“腾基高考志愿填报分析系统”使 用心理学、计算数学的分析诊断模型、量表和工具对历年高考数据进行统计分析， 而使用数据挖掘技术对高考志愿相关数据进行深入分析，得出相关规则对考生填 报志愿进行预测性指导的分析系统在我国尚处于不成熟阶段。 3 、计算能力足以承受【l 川 现今硬盘、内存、处理器和f o 带宽连续的降价，已经使得曾经昂贵的仅用于 政府资助的实验室的技术进入普通企业。一些主流供应商，如o r a c l e ，t e r a d a t a 和 m m 的并行关系数据库管理软件的成功引入，已经将并行处理能力带入很多公司 的数据中心。这些并行数据库服务器平台为大规模的数据挖掘提供了极好的运行 环境。 4 、商业数据挖掘软件产品已经易于使用【1 3 】 从新的算法首次出现在学术杂志和会议，到使用这些算法的商业软件变为可 用，从第一个可用产品到其被普遍接受，总有一个时间延迟。对数据挖掘来说， 第2 页河南大学研究生硕士学位论文 目前已经到了普遍可用和普遍接受的阶段。例如决策树技术己经在许多数据挖掘 系统应用中得到研究者和软件公司的极大关注，国内外很多公司均已推出自己的 数据挖掘系统，其中很多都采用了决策树方法，在m i c r o s o f t 、s g i 、s a s 1 棚在已推 出的数据采掘系统中，首选的方法就是决策树方法。 1 2 研究意义 高考志愿分析具有很强的现实意义，在数百万条考生志愿数据中，蕴藏着丰 富的决策信息和知识，开发这些宝贵的信息资源，是服务高考录取工作，指导考 生科学地填报志愿的一项重要任务，也是目前迫切需要解决的问题。高考志愿分 析通过一系列的方法和手段对考生填报志愿的各个方面进行决策分析，得出指导 考生填报志愿的相关知识，对考生填报志愿所需信息进行有效的分析，使其在激 烈的高考竞争中占据优势。高考志愿分析是考生参加高考的一个重要部分，它主 要以考生志愿数据为依据，根据志愿相关的各个属性分析高考录取情况，其中得 到的各种知识，无论是平凡的统计信息还是非平凡的知识模式，都能够为考生提 供丰富的决策信息。 1 3 课题来源 本课题所研究的对象是普通高等学校招生全国统一考试历年产生并积累起来 的大量考生志愿相关数据。这些数据为分析考生志愿提供了丰富、完整、准确的 原始数据，也为数据挖掘者了解录取情况，进行统计、分析、查询和辅助决策提 供了依据。 高考志愿分析使用的数据主要是大量的历史数据，数据库内容是相对静态不 变的，其存储可以是关系型数据库，也可以是多维数据库，数据经过长期存储， 数据量很大。高考志愿分析主要是根据大量历史数据分析处理得出规则，用于对 高考特点和规律进行分析。 对高考志愿数据的分析不仅仅是简单的统计分析，更重要的是找出数据中的 有用信息，进而找到尚未发现的知识。因此，我们需要利用清理集成后的数据， 结合数据挖掘技术，从中提炼出更为有用的决策知识。 针对上述问题，本文着眼于高考志愿分析的具体情况，灵活运用c 4 5 算法和 最小二乘法【1 5 】来构建高考志愿录取预测模型。根据考生的成绩、科类、报考的专 业和学校等特点对高考录取结果进行分类，得出考生能否被录取的相关规则，提 供给考生进行进一步的决策分析。本文给出了包括数据预处理【1 6 j 、决策树生成和 河南大学研究生硕士学位论文第3 页 剪枝、规则提取和修剪【嘲，以及准确性评估的整个数据挖掘过程，实现了决策 树归纳分类技术在高考志愿分析中的应用，有效提高了高考志愿分析的精确度 ( tr e c i s i o n ) 和召回率( r e c a l l ) 【1 9 1 。 1 4 论文的整体结构 本文首先简要介绍了数据挖掘技术中的决策树归纳分类及高考志愿分析的内 容，然后重点介绍了c 4 5 算法在高考志愿分析中的应用，以及高考志愿信息处理 系统设计实现的思想和步骤，并给出了高考志愿录取预测模型的解决方案。各章 内容安排如下： 第一章介绍本文的研究背景、研究意义和课题来源，总结整个研究工作的内 容以及论文的组织结构 第二章首先对数据挖掘的基本思想、方法、过程和内容进行简要介绍，然后 重点介绍分类的概念、基本思想及主要算法，最后介绍了高考志愿分析中的的主 要方法一决策树归纳分类方法。 第三章首先简要介绍了高考志愿分析中志愿数据的来源和高考志愿分析的内 容；然后给出了标准c 4 5 算法对于高考志愿数据的可用性分析；最后主要介绍了 c 4 5 算法在高考志愿分析中的应用研究的全过程，即从数据预处理、算法应用， 到决策树剪枝、规则后修剪，并对出现的问题进行了分析。其中详细介绍了如何 灵活运用c 4 5 算法生成非平衡数据集下的二叉决策树的实现过程以及实验结果。 第四章详细介绍了高考志愿信息处理系统中用户界面和功能模块的设计与实 现。并给出了高考志愿录取预测模型的具体解决方案。 最后对本文的主要研究工作进行了简要的阐述，并探讨和展望了在未来时间 内应当完善的问题。 第4 页河南大学研究生硕士学位论文 第2 章数据挖掘中的分类技术 当前保存在计算机文件和数据库中的数据量正在以惊人的速度增长，如何根 据人们的特定需求，从中找出用户所需要的更精细的信息，便成为目前值得关注 的问题。数据挖掘正是应此要求而迅速发展起来的- - i 学科。本章简要介绍了数 据挖掘及分类技术，并对其中的决策树归纳分类方法做较为详细的介绍。 2 1 数据挖掘概述 数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、随 机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用 的信息和知识的过程。与数据挖掘相近的词有数据融合、数据分析和决策支持等。 这个定义包括好几层含义：数据源必须是真实的、大量的、含噪声的；发现的是 用户感兴趣的知识；发现的知识要可接受、可理解、可运用；并不要求发现绝对 正确的知识，仅支持特定的发现问题。许多人把数据挖掘视为数据库中知识发现 ( 魁) d ) 的一个同义词，而另一些人只是把数据挖掘作为数据库中知识发现的一 个基本步骤【2 0 】。一般认为知识发现过程由以下步骤组成： ( 1 ) 数据清理：清除噪声或不一致数据。 ( 2 ) 数据集成：将多种数据元组合在一起。 ( 3 ) 数据选择：从数据库中检索与分析任务相关的数据。 “) 数据变换：数据变换或统一成适合挖掘的形式，如通过汇总或聚集操作。 ( 5 ) 数据挖掘：k d d 的基本步骤，此阶段使用智能方法提取数据模式。 数据挖掘阶段是知识发现过程中的核心阶段。在这个阶段中，采用若干智能 的方法去提取数据模式，其中包括的要点有：如何产生假设：也就是让数据挖 掘系统为用户产生假设，还是用户自己对于数据库中可能包含的知识提出假设的 问题。前一种称为发现型( d i s c o v e r y - d r i v e n ) 数据挖掘，后一种称为验证型 ( v e r i f i c a t i o n - d r i v e n ) 数据挖掘。选择合适的挖掘工具。知识挖掘的操作。 验证发现的知识。 ( 6 ) 模式评估：根据某种兴趣度度量，识别表示知识的真正有趣的模式。 ( 7 ) 知识表示：使用可视化和知识表示技术，向用户提供挖掘的知识。 河南大学研究生硕士学位论文第5 页 2 2 分类 在数据挖掘众多的任务中，分类是其中最常见的任务之一。国内外的研究人 员在数据挖掘、统计分析、机器学习、神经网络、专家系统等领域中对分类问题 进行了大量的研究，提出了一系列的分类算法，如决策树归纳分类，贝叶斯分类、 贝叶斯网络和神经网络等窿“。近年来，分类技术已被广泛有效地应用于图像和模 式识别、医疗诊断、贷款审批、工业应用中的故障检测以及金融市场走势分类。 2 2 1 分类的基本概念 分类( c l a s s i f i c a t i o n ) 是指提出一个分类函数或分类模型( 也称作分类器) ，该 模型能把数据库中的数据项映射到给定类别中的某一个【l ”。数据分类是一个两步 过程： 第一步，建立一个模型，描述预定义的类或概念集。通过分析由属性描述的 数据库元组来构造模型。假定每个元组属于一个预定义的类，由一个称作类标号 属性的属性确定。对于分类，数据元组也称作样本、实例或对象。为建立模型而 被分析的数据元组形成训练集。训练集中的单个元组称作训练样本，并随机地由 样本群选取由于提供了每个训练样本的类标号，该步骤也称作有指导的学习( 即 在被告知每个训练样本属于哪个类的指导下进行模型的学习) 。它不同于无指导的 学习( 如聚类) ，无指导的学习中，每个训练样本的类标号是未知的，要学习的类 集合和数量也可能事先不知道。 。 通常，学习模型用分类规则、决策树或数学公式的形式提供。例如，给定一 个顾客信用信息的数据库，可以学习分类规则，根据他们的信誉度优良或相当好 来识别顾客。该规则可以用来为以后的数据样本分类，也能对数据库的内容提供 更好的理解 第二步，使用模型进行分类。首先评估模型( 分类方法) 的预测准确率保 持( h o l d o u t ) 方法是一种使用类标号样本测试集的简单方法。这些样本随机选取， 并独立于训练样本。对于每个测试样本，将己知的类标号与该样本的学习模型类 预测比较。被模型正确分类的测试样本的百分比就是模型在给定测试集上的准确 率。值得注意的是，如果模型的准确率根据训练数据集评估，评估可能是乐观的， 因为学习模型倾向于过分适应数据( 即，它可能适应训练集中的某些异常，这些 异常并不总是出现在总体样本群中) 。因此，通常使用测试集来评估分类算法的准 确率。如果认为模型的准确率可以接受，就可以用它对类标号未知的数据元组或 对象进行分类。 第6 页河南大学研究生硕士学位论文 2 2 2 分类的基本技术 经过多年的研究，以及根据分类知识发现的分类模型的不同，有很多种分类 的方法逐渐完善起来，其中主要有：决策树归纳分类、贝叶斯分类、基于神经网 络的分类，以及基于源自关联规则挖掘概念的分类等f 2 1 】【捌。 h 决策树归纳分类 决策树归纳分类方法是分类发现算法中最常见的一种方法，是一种监督学习 的方法【2 3 】【2 6 】。这种方法在对数据进行处理的过程中，将数据按树状结构分成若干 分枝形成决策树，每个叶子代表一个类，每个内部节点描述一个属性，每个分枝 包含数据元组的类别归属共性，从每个分枝中提取有用信息，形成规则。由于决 策树归纳分类方法使用信息论原理对大量实例的特征进行信息量分析，找出反映 类别的重要特征，它抓住了问题的本质，使这种方法很有效。特别地，决策树归 纳分类方法对样本数越大的数据库效果越好。 关于决策树归纳分类方法将在第三节中详细介绍。 口贝叶斯分类 贝叶斯分类是统计学分类方法，它基于贝叶斯定理【2 0 】。可以预测类成员关系 的可能性，如给定样本属于一个特定类的概率。 分类算法的比较研究发现，一种称作朴素贝叶斯分类的简单贝叶斯分类算法 可以与决策树和神经网络分类算法相媲美。朴素贝叶斯分类假定一个属性值对给 定类的影响独立于其它属性的值，该假定称作类条件独立。此假定是为了简化所 需计算，并在此意义下称为“朴素的”。理论上讲，与其它所有分类算法相比，贝 叶斯分类具有最小的出错率。然而，实践中并非总是如此，这是由于对其应用的 假定( 如类条件独立性) 的不准确性，以及缺乏可用的概率数据造成的。 朴素贝叶斯分类假定类条件独立，即给定样本的类标号，属性的值相互条件 独立。这一假定简化了计算。当假定成立时，与其它所有分类算法相比，朴素贝 叶斯分类是最精确的。然而，在实践中，变量之间的依赖可能存在。贝叶斯信念 网络说明联合概率分布能表示属性子集间的依赖，弥补了朴素贝叶斯分类的不足。 它允许在变量的子集间定义类条件独立性。它提供一种因果关系的图形，可以在 其上进行学习。在学习或训练信念网络时，许多情况都是可能的。网络结构可能 预先给定，或由数据导出。网络变量可能是可见的，或隐藏在所有或某些训练样 本中。隐藏数据的情况也称为空缺值或不完全数据。如果网络结构己知并且变量 是可见的，训练网络可以直接进行。该过程由计算c p t 项组成，与朴素贝叶斯分 类涉及的计算概率类似。当网络结构给定，而某些变量隐藏时，则可使用梯度下 降方法训练信念网络。 河南大学研究生硕士学位论文第7 页 贝叶斯网络的研究十分广泛，它可以对不确定性知识进行推理。例如：医疗 诊断，根据病人的症状，判断病人是否得了某种疾病，往往是一种不确定的推理 ( 带概率的推理) ，多数情况下没有百分之百的把握。运用贝叶斯网络进行推理， 可以达到较好的效果。 圆基于神经网络的分类 神经网络的发展源于神经生物学家及心理学家对于研究及测试模拟神经计算 的探索，旨在寻求开发和测试神经的计算模拟。神经网络由一组相关的输入和输 出单元组成，每一个关联有一个权重与之相对应。在学习阶段，通过调整神经网 ；络的权，利用预测输入样本的正确类标号来学习。由于单元之间的连接，神经网 络学习又称连接者学习【2 0 】鲫【2 l 】。 神经网络需要很长的训练时间，因而对于有足够长训练时间的应用更合适。 神经网络已经在很多领域得到了成功的应用，但由于缺乏严密的理论体系的指导， 其应用效果完全取决于使用者的经验。虽然h o m i k 等人证明，仅有一个非线性隐 层的前馈网络就能以任意精度逼近任意复杂度的函数，但一些研究者指出，对网 络的配置和训练是n p 问题。在神经网络训练的过程中，会涉及到大量的参数，这 些参数主要靠经验确定，而这些参数对一般人来说，通常是很难理解的。在实际 应用中，由于缺乏问题的先验知识，往往需经大量费力耗时的实验摸索才能确定 合适的神经网络模型、算法以及参数设置，其应用效果完全取决于使用者的经验。 即使采用同样的方法解决同样的问题，由于操作者不同，其结果也很可能大相径 庭。另外，由于人们很难解释蕴涵在学习权之中的符号含义，神经网络常常因其 可解释性差而受到批评。这些特点使得神经网络在数据挖掘的初期并不看好。 然而，神经网络的优点在于其对噪音数据的高承受能力，以及它对未经训练 的数据的分类能力。此外，最近已提出了一些由训练过的神经网络提取规则的算 法，这些因素都推动了神经网络在数据挖掘分类方面的应用。 锄基于源自关联规则挖掘概念的分类 关联规则挖掘是数据挖掘研究的一个重要的、高度活跃的领域 2 0 l 。最近，数 据挖掘技术已将关联规则挖掘用于分类闯题。下面，我们按历史次序简要介绍三 种方法。前两种方法：a r c s e 2 9 和关联分类【蚓，使用关联规则分类。第三种方法是 c a e p l 3 1 l 挖掘“显露模式0 它考虑挖掘关联规则使用的支持度概念。 第一种方法，首先基于聚类挖掘关联规则，然后使用规则进行分类。a r c s 或关联规则聚类系统挖掘形如a 岬 a q 。础j a c a t 的关联规则；其中i 、a 畸础 是在量化属性区间上的测试( 区间动态地确定) ，而a 。为给定训练数据的分类属 性指定一个类标号。得出的关联规则画在2 - d 栅格上，该算法扫描栅格，搜索规 则的矩形聚类。用这种办法，出现在一个规则聚类内的量化属性的相邻区间可以 第8 页河南大学研究生硕士学位论文 结合。和c 4 5 类似，由关联规则聚类系统产生的关联规则用于分类也有较高的准 确率。 第二种方法称作关联分类。关联分类挖掘形如c o n d s e t j y 的规则；其中， c o n d s e t 是项( 或属性值对) 的集合，而y 是类标号。满足最小支持度的规则是频 繁的；这里，规则具有支持度s ，如果给定数据集中的样本s 包含c o n d s e t 并且属 于类y 。满足最小置信度的规则是精确的；这里，规则的置信度为c ，如果给定数 据集中包含c o n d s e t 的样本c 属于类y 。如果一个规则项集具有相同的c o n d s e t ， 则选择具有最高置信度的规则作为可能规则( p r ) ，代表该集合。 关联分类方法由两步组成。第一步是找出所有频繁的、精确的p k 集合。这些 是类关联规则( c a r ) 。其c o n d s c t 包含k 个规则项称作k - 规则项。算法使用迭代 方法，先验知识用于裁减规则搜索。第二步使用一种启发式方法构造分类。这里， 发现的规则根据支持度和置信度按递减的优先次序组织。 第三种方法c a e p ( 通过聚集显露模式分类) 使用项集支持度挖掘显露模式 ( e m e r g i n gp a t t e r n ，e p ) ，而e p 用于构造分类。粗略地说，e p 是一个项集( 项的 集合) ，其支持度由一个类到另一个类显著增加两个支持度的比称作e p 的增长 率。例如，假定我们有顾客数据集，包含类b u y sc o m p u t e r = ，e s ”或c i 和 b u y s _ _ c o m p u t e r = n o 或c 2 。项集 a g e = “3o ，s t u d e n t s = n o ”) 是一个典型的e p ， 其支持度由在c l 中的o 2 增长到在c 2 中的5 7 6 。增长率5 7 6 0 2 - - - 2 8 8 。 值得注意的是一个项或者是分类属性上的简单相等测试，或者是检查数值属性是 否在某个区间的测试。每个e p 是一个多属性上的测试，并且可能在区分一个类的 实例与另一个类的实例方面非常强。例如，如果一个新样本x 包含在上面的e p 中，我们可以说x 属于c z 的几率为9 9 6 。一般地，e p 的区分能力大约正比于 它的增长率和它在且标类的支持度。 一种替代的分类算法称作j e p 分类算法( j e pc l a s s i f i e r ) 【3 2 】，该算法是基于 跳跃显露模式( j u m p i n ge m e r g i n g p a t t e m ，j e p ) 提出的。其中，j e p 是一种特殊类 型的e p ，定义为这样的项集，其支持度由在一个数据集中的0 陡峭地增长到另 个数据集中的非0 。因为j e p 具有无穷大的增长率，而e p 具有有穷的增长率，所 以j e p 比e p 的区分能力更强。这使得在许多大型数据库( 尤其是维数也很大的数 据库) 中，基于j e p 的分类算法优于基于e p 的分类算法。 其他分类方法 与上述分类方法相比还有一些方法在商业数据挖掘系统中较少用于分类，其 中包括k 最邻近分类、基于案例的推理、遗传算法、粗糙集和模糊集方法。虽然 这些方法还处在原始阶段，然而其日趋流行【2 0 】，因此下面对这些分类方法做简要 介绍。 河南大学研究生硕士学位论文第9 页 ( 1 ) k - 最邻近分类口3 j ：是一种常用的基于距离度量的分类方法。k n n 技术假设 整个训练集不仅包含数据集，而且包含每个元组期望的类别标签。实际上，训练 数据就成为模型。当对一个新元组进行分类时，必须首先确定它与训练集中的每 个元组之间的距离，然后进一步考虑训练集中k 个与新元组相距最近的元组。新 元组将被分配到一个类中，这个类包含了k 个最近元组中的最多的元组。 ( 2 ) 基于案例的推理( e a s e - b a s e dr e a s o n i n g ，c b r ) 3 4 1 ：当给定一个待分类的 新案例时，基于案例的推理首先检查是否存在一个同样的训练案例。如果找到一 个，则返回附在该案例上的解。如果找不到同样的案例，则基于案例的推理将搜 索具有类似于新案例成分的训练案例。概念上讲，这些训练案例可以视为新案例 的邻接者。基于案例的推理试图组合邻近的训练案例，提出新案例的解。如果解 之间出现不相容，可能需要回溯搜索其他解。基于案例的推理可能使用背景知识 和问题求解策略，以便提出可行的组合解。 ( 3 ) 遗传算法( g e n e t i ca l g o r i t h m ) 【3 5 】：是一类借鉴生物乔的进化规律演化而 来的随机化搜索方法。它是由美国的j h o l l a n d 教授1 9 7 5 年首先提出，其主要特点 是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并 行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的 搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质， 已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命 等领域。它是现代有关智能计算中的关键技术之一。 “) 粗糙集( r o u g hs e t ) 3 6 1 和模糊集( f u z z ys e t ) 口7 】理论：是一种刻划不完整 性和不确定性的数学工具其主体思想是在保持分类能力不变的前提下，通过知 识约简，导出问题的决策或分类规则，它能有效地分析和处理不精确、不一致、 不完整等各种不完备信息，并从中发现隐含的知识，揭示潜在的规律。租糙集理 论解决问题的出发点是信息系统中知识的不可分辨性，而模糊集理论着眼于集合 的模糊性，其解决问题的出发点是信息系统中知识的模糊性。粗糙集和模糊集理 论已广泛应用于近似推理、医疗诊断、过程控制、软件工程数据分析、图像处理、 晶体结构分析、预测缄默、结构缄默、股票分析、电力系统等领域。 2 2 3 分类算法的比较标准 力。 常用的分类算法的比较和评估标准有以下几点： ( 1 ) 准确率：表示分类模型正确的预测新的或先前未见过的数据的类标号的能 ( 2 ) 速度：表示产生和使用模型的计算花费，即时间复杂性。 第1 0 页河南大学研究生硕士学位论文 ( 3 ) 健壮性：表示对于给定的带噪声的数据和具有空缺值的数据模型正确预测 的能力。 ( 4 ) 可伸缩性：表示对于给定的不同大小数据集，有效的构造模型的能力。 ( 5 ) 可解释性：反映学习模型提供的理解和洞察的层次。 目前，己有许多关于不同分类算法的比较，并且该问题仍然是一个研究课题。 尚未发现有一种算法对所有数据都优于其它方法。在设计一个算法时，它的准确 性、训练时间、强壮性、可解释性和可规模性都必须考虑，并且可能涉及折衷， 使得寻求更好方法进一步复杂化。实验研究表明，许多算法的准确性非常类似， 其差别是统计不明显的，而训练时间可能显著不同。另外，可规模性也是目前考 虑较多的一个因素，由于出现了越来越多的超大规模的数据库系统，所以是否能 够有效地处理大规模数据也成为衡量算法的重要标准。由于本文的实验采用的是 非平衡数据集，所以采用f - m e a s u r e i l 9 3 的评估方式来对样本在分类后的质量好坏做 评估。其中，f m e a s u r e 包含了召回率( r e c a l l 又称为查全率) 及精确度( p r e c i s i o n 又称为查准率) 。若以t p 代表正确分到本类的记录数，f p 代表不正确分到本类的 记录数，f n 代表不正确分到其他类的记录数则召回率与精确度的公式如下：精 确度为t p ( t p + f p ) 、召回率为t p ( t p + f n ) ，若以r 代表召回率、p 代表精确 度，则f - m e a s u r e 的公式为：f - m e a s u r e - - 2 r p 限+ p ) ，当召回率与精确度的值越高 时，其f - m e a s u r e 的值也越高，这表示其分类的质量也越好。 2 3 决策树归纳分类 决策树学习是以实例为基础的归纳学习算法，j k q u i n l a n 对此作出过详细的 理论描述【6 i - 【加l 。决策树学习着眼于从一组无次序、无规则的事例中推出决策树表 示形式的分类规则。它采用自顶向下的递归方式，在决策树的内部结点进行属性 的比较并根据不同属性值判断从该结点向下的分枝，在决策树的叶结点得到结论。 所以从根到叶结点的一条路径就对应着一条合取规则，整棵决策树就对应着一组 析取表达式规则【2 ”。 一棵决策树的内部结点是属性或属性集，叶结点是所要学习划分的类【2 3 j 。当 经过一批训练实例集的训练产生一棵决策树，决策树可以根据属性的取值对一个 未知实例集进行分类。使用决策树归纳分类的时候，由树根开始对该对象的属性 逐一测试其值，并且顺着分枝向下走，直至到达某个叶结点，此叶结点代表的类 即为对象所处的类。 河南大学研究生硕士学位论文第1 1 页 2 3 1 基本思想 决策树( d e c i s i o nt r y ) ，又称判定树是一种以信息论原理为基础，以决策树这 种数据结构为基础的分类算法例【2 3 】嘲。其是一个类似于流程图的树结构，利用信 息论中互信息( 信息增益网) 寻找数据库中具有最大信息量的字段，建立决策树 的一个结点表示在一个属性上的测试。然后再根据字段的不同取值建立树的分支 代表相应的测试输出，在每个分支集中重复建立树的下层结点和分支，最后每个 树叶结点代表类或类分布。为了对未知的样本进行分类，样本的属性值在判定树 上测试，路径是从根到存放该样本预测的叶结点。这种方法实际上是依循信息论 原理对数据库中存在的大量数据进行信息量分析，在计算数据特征的互信息或信 道容量的基础上提取出反映类别的重要特征。决策树归纳分类实现简单，层次结 构清晰，能够产生易于理解和分析的规则，因此是目前应用较为广泛的分类方法。 决策树归纳的基本算法是贪心算法，它是以自顶向下递归的各个击破方式构 造决策树。算法的基本策略如下 2 0 l ： ( 1 ) 树以代表训练样本的单个结点开始。 ( 2 ) 如果样本都在同一个类，则该结点成为树叶，并用该类标记。 ( 3 ) 否则，算法使用称为信息增益的基于熵的度量作为启发信息，选择能够最 好地将样本分类的属性。该属性成为该结点的“测试”或“决策”属性。 “) 对测试属性的每个已知的值创建一个分枝，并据此划分样本。 ( 5 ) 算法使用同样的过程，递归地形成每个划分上的样本决策树。旦一个属 性出现在一个结点上，就不必在该结点的任何后代上考虑它。 ” ( 6 ) 递归划分步骤仅当下列条件之一成立时停止： 给定结点的所有样本属于同一类。 没有剩余属性可以用来进一步划分样本。在此情况下，使用多数表决。这 涉及将给定的结点转换成树叶，并用样本中的多数所在的类标记它。替换地，可 以存放结点样本的类分布。 分枝t e s t a t t r i b u t e = a i 没有样本在这种情况下，以样本中的多数类创建一 个树叶。 决策树在树的每个结点上使用信息增益( i n f o r i n a t i o ng a i n ) 度量选择测试属性。 这种度量称作属性选择度量或分裂的优劣度量。选择具有最高信息增益( 或最大 熵压缩) 的属性作为当前结点的测试属性。该属性使得对结果划分中的样本分类 所需的信息量最小，并反映划分的最小随机性或“不纯性”。这种信息理论方法使 得对一个对象分类所需的期望测试数日最小，并确保找到一棵简单的树。 设s 是s 个数据样本的集合。假定类标号属性具有m 个不同值，定义m 个不 第1 2 页河南大学研