（信号与信息处理专业论文）决策树分类算法的研究及其在纳税评估中的应用.pdf

决策树分类算法的研究及其在纳税评估中的应用 两要 数据挖掘( d a t am i n i n g ，d m ) 是从大量数据中发现潜在规律、提取有用知 识的方法和技术。近年来，数据挖掘受到了国内外的普遍关注，已经成为信息系 统和计算机科学领域研究中最活跃的前沿领域。数据挖掘己广泛应用于生物医 学、金融、零售业、电信业等领域，并产生了巨大的效益。本文以为国税开发数 据挖掘项目“纳税评估智能分析系统”为背景，在深入调研与分析国内外数据挖 掘相关理论、应用和技术文献的基础上，详细评述了基于分类数据挖掘的相关理 论与技术；并针对c 4 5 决策树算法实现提出了三种改进策略；并利用u c i ( i r v i n e 大学机器学习数据库) 数据库作为实验数据，比较了改进前与改进后c 4 5 算法 的执行效率，通过实验数据可以看出，改进后的c 4 5 算法( a k 文称之为q c 4 5 ) 在执行效率上有了明显的提高。 本文的主要研究内容为： 1 研究了数据挖掘的概念与发展现状、数据挖掘的过程模型与数据挖掘的 分类等。 2 研究了决策树分类方法，详细阐述了c 4 5 决策树的构造算法、分裂准 则、剪枝准则、评价方法等。 3 针对c 4 5 决策树算法实现，提出了三种改进策略，并通过样本集的特 征选择最合适的策略，从而较好的提高了算法的执行效率。 4 最后把q c 4 5 ( 改进后的c 4 5 算法) 算法应用于纳税评估智能分析系 统中有无避税嫌疑预测，并设计实现；在实际应用中取得了较好的效果。 本文的创新主要体现在：在决策树自顶向下递归构造过程中，对于每一个连 续型属性并不是使用同一种计算方法计算属性的信息增益，而是根据属性值的特 征从三种改进策略中选择一种执行效率最优的策略来计算此连续属性的信息增 益，从而提高整个决策树的生成效率。通过实验数据表明，q c 4 5 的执行效率优 于c 4 5 ，证明了方法的可行性。 关键词：知识发现；数据挖掘；决策树；0 4 5 ：纳税评估 r e s e a r c ho fd e c i s i o nt r e ec i a s s i f i c a t i o na n dl t s a p p li c a t i o nt ot a xa s s e s s m e n t a b s t r a c t d a t am i n i n g ( d m ) a i m sa ta n a l y z i n gm a s s i v ea m o u n t so fd a t aa n de x t r a c t i n g m e a n i n g f u la n dc o m p r e h e n s i b l ep a t t e r n s ，c a l l e dk n o w l e d g e i nr e c e n ty e a r s ，d mh a s g o td o m e s t i ca n d i n t e r n a t i o n a lw i d e s p r e a dc o n c e r na n dh a sb e e nb e c o m i n gm o s th o t r e s e a r c h i n gr e a l mi nt h ef i e l do f i n f o r m a t i o ns y s t e m sa n dc o m p u t e rs c i e n c e d mh a s b e e n w i d e l y u s e di nb i o m e d i c a l f i e l d ，f i n a n c i a lf i e l d ，r e t a i li n d u s t r y a n d t e l e c o m m u n i c a t i o ni n d u s t r y b a s e do nt h r o u g he x p l o r i n ga n da n a l y s i so nt h er e l a t e d l i t e r a t u r e s ，t h es t a t e o f - t h e a r t so fk n o w l e d g ea n dd a t am i n i n g ，t h em a i nc o n t e n t sa n d k e yt e c h n o l o g i e sa r eg e n e r a l i z e da n ds u m m a r i z e d ，t h ed e v e l o p m e n tt r e n d s ，q u e s t i o n s ， a n df t n t h e rt a s k sa r ep a r t i c u l a r l yc o m m e n t e d0 1 3d m t h i sp a p e rp u t sf o r w a r dt h r e e s t r a t e g i e st oi m p r o v ec 4 5a l g o r i t h m a c c o r d i n gt o c h a r a c t e r i s t i c so fd a t at h en e w a l g o r i t h ms e l e c t st h eo p t i m u ms t r a t e g y b a s e do nt h eu c ik n o w l e d g ed i s c o v e r yi n d a t a b a s e sa r c h i v ea n du c im a c h i n e l e a r n i n ga r c h i v ea se x p e r i m e n td a t a ，t h i sp a p e r c o m p a r e sc 4 5w i t hq c 4 5 ( t h en e wa l g o r i t h m ) o n t h ee x e c u t i o ne f c i e n c y ，a n di tc a n b es e et h a tq c 4 5i sb e t t e rt h a nc 4 5 t h em a i nw o r k si nt h i sp a p e ra sf o l l o w s ： 1 r e s e a r c ht h ec o n c e p to fa n dd e v e l o p m e n ti nd a t am i n i n g ，t h ep r o c e s so f d a t a m i n i n g ，t h e c l a s s i f i c a t i o no f d a t a m i n i n g 2 r e s e a r c ht h ed e c i s i o n t r e e ，a n dp a r t i c u l a r l ye x p o u n d t h ec o n s t r u c t o r a l g o r i t h m ，s p l i tc r i t e r i o n ，p r u n i n gc r i t e r i o ne t c 3 r e s e a r c hc 4 5a l g o r i t h m ，a n dp u tf o r w a r dt h r e es t r a t e g i e st oi m p r o v ec 4 5 a l g o r i t h m 4 i m p l yq c 4 5a l g o r i t h m t ot h e s y s t e m o fa t t i t u d et a xa s s e s s m e n tf o r p r e d i c t i v em o d e l ，a n d m a k ea g o o d e f f e c ti np r a c t i c e t h en o v e li d e ai nt h i sp a p e ri st h a t ：i nt h ep r o c e s so f c o n s t r u c t i n gd e c i s i o nt r e e ， a c c o r d i n gt h ec h a r a c t e r i s t i co fd a t as e l e c t t h eo p t i m u ms t r a t e g yt of i n dt h e s p l i t a t t r i b u t e t h i sm e t h o dc a ni m p r o v et h ee x e c u t i o ne f f i c i e n c yo fc 4 5i nt r i a la n di s d o a b 】e k e y w o r d s ：k n o w i e d g ed i s c o v e r y i nd a t a b a s e ：d a t am i n i n g ；d e c i s i o nt r e e c 4 5 ：t a xa s s e s s m e n t 决策树分类算法的研究及其在纳税评估中的应用 第一章绪论 1 1 数据挖掘的研究背景及定义 1 1 1 数据挖掘的研究背景 随着国际互联网的高速发展和电子商务的广泛应用，人们利用信息技术生产 数据的能力大幅度提高，成千上万个数据库被用于商业管理、政府办公、科学研 究和工程开发等等。企业，政府部门和科学团体因此也面对着信息积累的问题。 每日，都有大量的数据产生，信息量以每二十个月翻一番的速度剧增。大量的数 据储存在联机数据库中。信息技术的发展面临着如何从巨大的信息海洋中找到合 适的数据分析方法，获取有用的知识模式来帮助企业、政府做出正确的决策，数 据挖掘( d a t am i n i n g ，d m ) 应运而生。数据挖掘就是从大量数据中发现潜在规律、 提取有用知识的方法和技术【1 , 2 1 。数据挖掘不但能够学习已有的知识，而且能够 发现未知的知识，得到的知识是“显式”的，既能为人所理解，又便于存储和应 用，因此一出现就得到广泛的重视。 由于数据库技术的发展和数据存储成本的降低以及数据库管理系统的广泛 应用，大型数据库系统已经在各行各业普及。数据库和联机事务处理( o l t p ) 已经 被广泛应用于金融、证券f 3 l 、保险、销售以及天气预报、工业生产、分子生物学、 基因工程研究、税务、海关等各行名业。对于这些积累的大量数据，人们已经不 满足于传统的统计分析手段，而需要发现更深层次的规律，提供更高层次的数据 分析功能，更加方便和有效的获取能带来效益的信息。在大量的数据背后隐藏着 许多重要的不被人所知的信息，这些信息可以很好地辅助人们进行决策。可是目 前用于对这些数据进行分析处理的工具却很少。目前人们用到的主要是数据库的 存储功能和简单的查询分析功能，而隐藏在这些数据之后的更重要的信息则没有 被充分发现和利用。这些信息是关于数据的整体特征的描述以及对发展趋势的预 测，在决策生成过程中具有重要的参考价值。例如，银行信用卡的发放和电信局 的客户信用都可以通过查询客户数据库来发现恶意欺骗的信誉度不好的客户模 式。另外，通过数据挖掘，可以处理高维的数据，为用户提供可视化工具，帮助 用户发现隐藏在高维空间的模式。对数据进行可视化的一种有效方法是借助于数 据挖掘方法实现。例如，聚类算法能从高维空间找出有别于其他类别的特征数据 子集，通过其提供的可视化图形可以很容易发现数据模式。 决策树分类算法的研究及其在纳税评估中的应用 目前，数据挖掘不仅被许多研究人员看作是数据库系统和机器学习方面重要 的研究课题，而且被许多工商界人士看作是一个能带来巨大回报的重要领域。从 数据库中发现出来的知识可以用在信息管理、查询响应、决策支持、过程控制等 许多方面。目前，已经有多家知识发现商业产品投入市场，并取得成功的应用。 特别要指出的是，数据挖掘技术从一开始就是面向应用的【4 t 5 ，6 】。它不仅是面 向特定数据库的简单检索查询调用，而且要对这些数据进行微观、中观乃至宏观 的统计、分析、综合和推理，以指导实际问题的求解，企图发现事件问的相互关 联，甚至利用已有的数据对未来的活动进行预测。例如加拿大b c 省电话公司要 求加拿大s i m o nf r a s e r 大学k d d 研究组，根据其拥有十多年的客户数据，总结、 分析并提出新的电话收费和管理办法，制定既有利于公司又有利于客户的优惠政 策。美国著名国家篮球队n b a 的教练，利用i b m 公司提供的数据挖掘技术，临场 决定替换队员，一度在数据挖掘界被传为佳话。本文在下一节将要介绍的纳税评 估系统就是利用数据挖掘技术来进行辅助决策分析的一个实际应用。 1 1 2 数据挖掘的定义 数据挖掘是一门交叉性学科i ”，来自各种不同领域的研究者对它产生了浓厚 的兴趣和广泛的关注，这种情况导致了很多不同的术语。除了数据挖掘称呼外， 主要还有“知识抽取”( i n f o r m a t i o ne x t r a c t i o n ) ，“信息发现”( i n f o r m a t i o n d i s c o v e r y ) ，“知识发现”( k n o w l e d g ed i s c o v e r y ) ，“智能数拒分析”( i n t e l l i g e n t d a t aa n a l y s i s ) ，“信息收获”( i n f o r m a t i o nh a r v e s t i n g ) 等等称法m 】。其中， 最常用的术语是“知识发现”和“数据挖掘”。相对而言，数据挖掘主要流行于 统计界( 最早出现于统计文献中) 、数据分析、数据库和管理信息系统界，而知 识发现则主要流行于人工智能和机器学习界，这两个概念经常会被混淆在一起。 在1 9 9 5 年蒙特利尔第一届国际k d d 会议上，与会者普遍接受了这样一种观点， 即：数据挖掘是k d d 中专门负责发现知识的核心环节；而k d d 是一个交互式、循 环反复的整体过程，除了包括数据挖掘外还包括数据准备和发现结果解释评估等 诸多环节。本文也认同数据挖掘是知识发现过程的一个步骤。然而，在数据库研 究界，术语“数据挖掘”比较长术语“知识发现”更加流行，并且广义的数据挖 掘意义与知识发现相同，因此，本文选用术语数据挖掘代替知识发现。 数据库知识发现( k d d ，k n o w l e d g ed i s c o v e r yi nl a r g ed a t a b a s e ) 这个术 语首先出现在1 9 8 9 年8 月在美国底特律召开的第l l 届国际人工智能联合会议的 专题讨论会上，1 9 9 1 ，1 9 9 3 和1 9 9 4 年又接着继续举行k d d 专题讨论会。随着参 加会议人数的增多，规模由原来的专题讨论会发展到国际学术大会，人数由二三 十人到七八百人，从1 9 9 5 年开始，每年都要举办一次k d d 国际会议。另外从9 7 2 决策树分类算法的研究及其在纳税评估中的应用 年开始，k d d 拥有了自己的专门杂志( k n o w l e d g ed i s c o v e r ya n dd a t am i n i n g 。 不仅如此，在i n t e r n e t 上还有不少k d d 电子出版物，其中以半月刊k n o w l e d g e d i s c o v e r yn u g g e t s 最为权威，如要免费订阅，只需向! ! p ；! 里型：e 4 鲤g g ! ! i ： ! ! 婴i 业i ! ! i b q ：b ! 婴! 发送一份电子邮件即可，还可以下载各种各样的数据挖掘 工具软件和典型的样本数据仓库供人们测试和评价。随着互联网的发展，网络上 设立了很多关于k d d 研究的网站、论坛以及新闻组。除了研究外，也出现了相当 数量的k d d 产品和应用系统，并且获得了一定的成功，得到了业界的广泛关注。 从知识发现诞生至今，人们对于知识发现还没有一个统一的定义，但是随着 知识发现研究的不断深入，其定义也在不断修改，其中一种比较公认的定义是由 f a y y a d 等给出的【8 】。 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 si s t h en o n t r i v i a lp r o c e s so fi d e n t i f y i n gv a l i d ，n o v e l ，p o t e n t i a l l yu s e f u l ，a n du l t i m a t e l yu n d e r s t a n d a b l ep a t t e r n si td a t a 数据库中的知识发现是从数据集中识别出有效的、新颖的、潜在有用的，以 及最终可理解的模式的高级过程 2 1 。 这种定义把数据挖掘的对象定义为大量数据，其中，数据指的是一个有关事 实的集合，如超市销售数据库中的销售信息。它是用来描述事务有关方面的信息， 是我们进一步发现知识的原材料。 数据挖掘的一个显著特征是它所提取的模式是隐含的、事先未知的。这不同 于专家系统仅是对已有知识的学习。并且要将这些新颖的知识以容易被人理解的 形式表现出来，因此挖掘过程也是一个人机交互、螺旋上升的过程，它需要反复 调整，从而挖掘出质量更高更有效的知识。 1 2 课题研究的背景、意义以及主要研究内容 1 2 1 课题研究的背景、意义 纳税评估是国家税务机关为了鉴定和判别纳税人纳税申报的真实性、合法性 的现代税收信息化管理手段。实践证明，纳税评估的信息化管理，可以有效地加 强税收的日常管理和对税源的有效监控。同时，通过对纳税人的纳税申报信息数 据、生产经营信息数据、经营核算信息数据，及其他信息数据的采集，利用信息 调查、指标测算、数据对比、综合分析等信息分析手段，评析和查证申报中存在 的疑点和问题，可以大大减少税收管理中的盲目性。纳税评估工作是加强税收日 常管理的一项专业化、信息化和高效的税收管理手段，是在“多元申报、集中征 决燕树分类算法的研究及其在纳税评估中的应用 收、分类管理、一级稽查”新的税收征管运行机制下，强化税收信息监控、提高 征管质量和效率的“催化剂” 9 】。 但是，随着社会的发展，税收评估作为税务机关的一项强有力的管理手段也 开始逐渐暴露出一些不足。这主要表现以下几个方面： 一、在经济发展的过程中，企业数量也在不断地增长，而征收管理人员的数 量增长是缓慢的。在东营市国税局目前税收管理中存在的一个现实问题和突出问 题就是征收管理人员少、管辖户数多。仅东营市市区国家税务局就管理着辖区内 近1 6 0 0 余户的增值税一般纳税人，这些纳税人中有的经营规模还比较大，而直 接从事一般纳税人日常征收和管理的税务人员却不足3 0 人，税收征管力量明显 不足【l o 】。 二、指标繁多，采集难度大。例如一户商业增值税一般纳税人进行评估，仅 增值税纳税评估分析表指标就有1 8 个大项7 2 个小项，所需历年财务指标 1 3 8 个，另还要查阅大量历年纳税申报资料【l 。 三、部分参考值不确定，计算出的指标没有参照值。例如“各行业税负率正 常峰值”缺乏较权威的测定标准，外界横向比较缺少参照，实际效果并不理想。 面对日益增多的纳税人和纳税人日益增高的征管服务要求，如何使纳税评估 作为一种先进的征管方法在征管中发挥重要作用，单单依靠增加税务工作人员来 “外延型”加强管理是不行的。基于以上原因，开发一种智能的纳税评估系统就 势在必行，而数据挖掘技术的发展为这个系统的开发提供了很好的基础。也就是 充分利用当前税收网络信息化平台，通过数据挖掘技术找出隐藏在大量历史数据 中的有用的数据模式，来辅助评估人员进行更加科学、客观、公正的评估工作， 大幅度地提高税收管理效能。 我国税务管理部门计算机技术应用开始于8 0 年代中后期，从用计算机进行 征收开票，经过基层税务部门在局域网上建立基层小型税务管理信息系统，发展 到今天的基于大型关系数据库和数据仓库的税务管理信息系统【1 2 删。在一些计算 机技术应用水平较高的税务管理部门或地区，十余年的计算机应用，积累了大量 的税务管理数据，这些数据己经成为税务管理、决策的宝贵资源。开发这个智能 的纳税评估系统就要充分利用这些数据，来提取有用的信息辅助税务人员进行纳 税评估。 1 2 2 本文研究的主要内容 本人在这个系统的开发中，主要工作是分类预测模型的建立。就是通过历史 评估结果数据集，建立有无避税嫌疑分类预测模型。由于没有历史经验的借鉴， 本人也只是探索性的使用决策树分类算法c 4 5 来建立这个模型，这主要考虑到 决策树分类算法的研究及其在纳税评估中的应用 决策树计算容易，结构简单，容易生成可以理解的规则。本文在分析数据挖掘主 要研究内容的基础上，针对分类算法在数据挖掘中的重要作用和广泛应用，研究 了决策树各种分类算法，重点研究了c 4 5 分类算法采用的策略、分类准则、剪 枝策略等，并在分析c 4 5 系统运行的实时性特征的基础上，提出了对其实现算 法的三种改进策略，并根据不同样本数据集的特点选择最优的策略。实验证明， 采用改进策略后能有效提高c 4 5 系统的运行效率。 本论文的主要工作和内容如下： 1 研究了数据挖掘的研究现状及发展趋势； 2 研究了决策树分类方法，并重点研究了c 4 5 分类算法 3 针对c 4 5 的算法实现提出了三种改进策略； 4 结合实际，设计与实现了纳税评估智能分析系统中有无避税嫌疑预测模块。 本论文主要包含以下五个章节：第一章绪论，内容包括数据挖掘的研究背景、 定义、发展历史及现状；第二章是数据挖掘的过程，主要研究和介绍了数据挖掘 过程的模型及其研究方法；第三章分类算法及评价方法，介绍了决策树分类算法， 详细介绍了c 4 5 算法，给出了对于分类算法的实验评价方法和准则。第四章基 于c 4 5 算法实现的三神改进策略，这一章是本文的工作重点。本章在分析了c 4 5 算法实现的时间复杂度与空间复杂度的基础上，针对其对连续型属性的处理提出 了三种改进策略，在决策树递归生成过程中，根据属性值的特点选择最优的策略 来计算属性的信息增益；并实验证明了改进后的算法能有效提高原算法的执行效 率：第五章纳税评估智能分析系统中有无避税嫌疑预测模块的设计，以纳税评估 为背景结合前几章决策树分类算法以及算法实现设计了纳税评估智能分析系统 中的有无避税嫌疑预测模块。第六章是结论与展望，总结了该系统在实际应用中 的结果以及还存在的不足，并且展望了未来数据挖掘领域的一些研究焦点。 决策树分类算法的研究及其在纳税评估中的应用 第二章数据挖掘过程 目前对数据挖掘的研究相当活跃而杂乱。针对数据挖掘的过程模型、功能模 型、算法研究、应用等不同层面，国内外每年都有大量的研究文献涌现，并举行 众多的有关数据挖掘理论与应用研究的学术会议。本章将从数据挖掘过程模型和 数据挖掘的研究方法两方面来描述数据挖掘。 2 1 数据挖掘过程模型 2 1 1 f a y y a d 给出的数据挖掘过程模型1 1 3 】 趔i 啦争 图2 - 1 数据挖掘过程模型 f a y y a de t a 1 1 9 9 6 年给出了上图所示的数据挖掘处理过程。是公认的通 用的数据挖掘过程定义。 在数据挖掘过程中，数据被存储在数据库中，根据数据挖掘算法的要求从数 据库中选取数据挖掘所需要的数据，在数据预处理阶段对数据噪音和错误数据进 行处理，然后对数据进行变换满足数据挖掘算法的要求，选择合适的数据挖掘算 法进行数据挖掘，以发现知识模式，这是数据挖掘的核心阶段，最后对发现的模 式进行解释和评估，剔除冗余无关的模式，并要对发现的模式进行可视化，把结 果转换成用户易懂的表示方式。 我们可以看出，数据挖掘过程主要由数据处理，数据挖掘和结果分析三个主 要部分组成。 数据处理 数据处理又可分为三个子步骤：数据选取( d a t as e l e c t i o n ) 、数据预处理 决策树分类算法的研究及其在纳税评估中的应用 ( d a t ap r e p r o c e s s i n g ) 和数据变换( d a t at r a n s f o r m a t i o n ) 。 数据选取的目的是确定发现任务的操作对象，即目标数据( t a r g e td a t a ) ， 是根据用户的需要从原始数据库中抽取的一组数据。数据预处理一般可能包括消 除噪声、推导计算缺值数据、消除重复记录、完成数据类型转换( 如把连续值数 据转换为离散型的数据，以便于符号归纳，或是把离散型的转换为连续值型的， 以便于神经网络等) 。当数据挖掘的对象是数据仓库时，一般来说，数据预处理 已经在生成数据仓库时完成了。数据变换的主要目的是消减数据维数或降维 ( d i m e n s i o nr e d u c t i o n ) ，即从初始特征中找出真正有用的特征以减少数据挖掘 时要考虑的特征或变量个数。 数据挖掘 数据挖掘阶段首先根据对问题的定义明确挖掘的任务或目的，如分类【1 ”、聚 类、关联规则发现【1 6 】或序列模式发现等。确定了挖掘任务后，就要决定使用 什么样的算法。选择实现算法有两个考虑因素：是不同的数据有不同的特点， 因此需要用与之相关的算法来挖掘；二是用户或实际运行系统的要求，有的用户 可能希望获取描述型的( d e s c r i p t i v e ) 、容易理解的知识( 采用规则表示的挖掘方 法显然要好于神经网络之类的方法) ，而有的用户只是希望获取预测准确度尽可 能高的预测型( p r e d i c t i v e ) 知识，并不在意获取的知识是否易于理解。数据挖掘方 法是本文研究的主要内容，本文将在下面章节中重点介绍决策树方法，并详细介 绍了c 4 5 分类算法，以及本文对此算法实现提出得改进策略。 结果解释和评估 数据挖掘阶段发现出来的模式，经过评估，可能存在冗余或无关的模式，这 时需要将其剔除。也有可能模式不满足用户要求，这时则需要整个挖掘过程回退 到前续阶段，如重新选取数据、采用新的数据变换方法、设定新的参数值，甚至 换一种算法等等。另外，由于数据挖掘最终是面向人类用户的，因此可能要对发 现的模式进行可视化，或者把结果转换为用户容易理解的其它表示形式，如把分 类决策树转换为“i f t h e n ”规则。 数据挖掘仅仅是整个过程中的一个步骤。数据挖掘质量的好坏有两个影响要 素：一是所采用的数据挖掘方法的有效性，二是用于挖掘的数据的质量和数量( 数 据量的大小) 。如果选择了错误的数据或不适当的属性，或对数据进行了不适当 的转换，则挖掘的效果不会好。 2 ，1 2 其他的数据挖掘过程模型 数据挖掘过程的整个挖掘过程是一个不断反馈的过程。比如，用户在挖掘途 中发现选择的数据不太好，或使用的挖掘技术产生不了期望的结果，这时，用户 7 决策树分类算法的研究及其在纳税评估中的应用 需要重复先前的过程，甚至从头重新开始。 可视化技术，在数据挖掘的各个阶段都扮演着重要的作用。特别是，在数据 准备阶段，用户可能要使用散点图、直方图等统计可视化技术来显示有关数据， 以期对数据有一个初步的了解，从而为更好地选取数据打下基础。在挖掘阶段， 用户则要使用与领域问题有关的可视化工具。在表示结果阶段，则可能要用到可 视化技术以使得发现的知识更易于理解。 1 9 9 6 年，b r a c h r n a n 和a n a n d 通过对很多数据挖掘用户在实际工作中遇到的 问题的了解，发现用户的很大一部分工作量是与数据库的交互上。他们从用户的 角度对数据挖掘处理过程进行了分析，认为数据挖掘应该更着重于对用户进行数 据挖掘的整个过程的支持，而不是仅仅限于在数据挖掘的一个阶段上，进而提出 了以用户为中心的处理过程模型【 】。该模型特别注重对用户与数据库交互的支 持，用户根据数据库中的数据，提出一种假设模型，然后选择有关数据进行知识 的挖掘，并不断对模型的数据进行调整优化。b r a c h r n a n 和a n a n d 在他们开发的 数据挖掘系统i m a c s ( i n t e r a c t i v em a r k e t i n ga n a l y s i sa n d c l a s s i f i c a t i o ns y s t e m ) q b 采用了这种以用户为中心的处理过程模型。 1 9 9 7 年斯坦福大学的g e o r g eh ，j o h n 在其博士论文中给出另外一种数据挖 掘处理过程模型【1 8 】。该模型强调由数据挖掘人员和领域专家共同参与数据挖掘的 全过程。领域专家对该领域内需要解决的问题非常清楚，在问题的定义阶段由领 域专家向数据挖掘人员解释，数据挖掘人员将数据挖掘采用的技术及其能解决问 题的种类介绍给领域专家。双方经过互相了解，对要解决的问题有一致的处理意 见，包括问题的定义及数据的处理方式。 1 9 9 9 年中国科学院计算研究所的朱廷绍博士认为前述模型对数据挖掘过程 中的反复学习和多目标学习支持不够，即针对某种数据挖掘算法确定一批相关数 据，使用其他算法时，这批数据即告无效，必须重新进行数据的提取和预处理。 为此在他的博士论文中提出支持多数据集多学习目标的数据挖掘处理模型【l9 1 ，将 数据和学习算法尽量分离，以使得数据挖掘更适合实际工作的需要并使得最终用 户和数据挖掘人员的之间的影响尽量小，以提高学习效率。 上述4 种处理模型的共同点是都要经过数据准备、预处理、数据挖掘和后处 理等共同的阶段，如图1 2 所示。 广 厂 广 广 l 数据准备 二= | 预处理 二割数据挖掘 二剖后处理i i 。一i ，一i 一i j 图2 - 2 四种知识发现过程模型的公共处理阶段 其中数据准备阶段包括问题定义和数据收集等准备工作：预处理包括数据清 理、压缩、变换等；数据挖掘阶段选择合适的算法进行数据挖掘。后处理阶段包 决镱树分类算法的研究及其在纳税评估中的应用 括结果解释、输出、评价、分析、使用等。 除上述几种处理模型外，还有d a i m l e r - c h r y s l e r 等公司提出的c r i s p d m 模 型和微软公司提出的数据挖掘模型( d a t a m i n i n g m o d e l ，d m m ) 等。与前面4 种处 理模型不同的是：后两种数据挖掘模型是为使数据挖掘商品化而提出，是企业或 企业集团各自制定的数据挖掘标准的一部分，重点是数据挖掘与数据仓库和其它 应用程序间的接口。 2 2 数据挖掘的方法模型 数据挖掘的方法模型按照功能分为预测模型和描述模型。在预测模型中，用 来预测的称为独立变量，要预测的称为相关变量或e l 标变量。预测模型包括分类 模型、回归模型和时间序列模型：描述模型包括聚类模型、关联模型和序列模型。 前者有时又称为有监督学习，后者称为无监督学习。 1 分类模型( c l a s s i f i c a t i o nm o d e l ) t 1 2 2 6 2 - 7 】 在数据挖掘中，分类模型通过对己知类别的个体进行归纳，找出各类的特征 属性，即分类模式。用于提取能代表群体的特征属性。在有些情况下，先由领域 专家对个体进行分类，再通过分类模型提取分类模式。分类输出的是离散的类别 值。有两种分类技术最为普遍的用于数据挖掘。决策树和简单贝叶斯分类器。著 名的决策树算法是q u i n l a n 的c 4 5 决策树算法1 2 1 1 。被得到了极其广泛的应用。 2 。回归模型( r e g r e s s i o nm o d e l ) 回归模型用属性的历史数据预测未来趋势。在最简单的情况下，可以用标准 统计方法，如线性回归等。但现实中往往非线性问题据多，如股票价格的涨跌、 机械系统故障的发生等，由于受许多因素的影响，问题变得非常复杂。回归模型 的任务就是找出对这些变化的准确描述。回归的输出是连续数值。有些技术既可 以用于分类，又可以用于回归，如c a r t ( c l a s s i f i c a t i o na n dr e g r e s s i o nt r e e s ) 等 2 2 2 3 。 3 时间序列模型( t i m e s e r i e sm o d e l ) 时间序列模型用己有的数据序列预测未来。从这一点上看，与回归模型很相 似。但回归模型不强调数据间的先后顺序，而时间序列模型要考虑时间特性，尤 其要考虑时间周期的层次，如天、周、月、年等，有时还要考虑日历的影响，如 节假曰等。 4 聚类模型( c l u s t e r i n gm o d e l ) t 1 2 - 2 - 5 1 聚类模型是将个群体分成多个类，使同类个体尽可能相似而不同类间个体 差异尽可能大。与分类模型不同的是，聚类模型从未知开始，既不知道具体的分 类标准，也不知道会有些什么类。按照给定的聚类参数( 如距离等) 进行分解、 9 决策树分类算法的研究及其在纳税评估中的应用 合并。得到的结果由领域专家进行甄别，如果不满足目标，需要改动聚类参数， 重新聚类。一旦达到目标，分类规则也就通过聚类参数得到。 5 关联模型( a s s o c i a t i o nm o d e l ) 【1 捌 关联模型用于发现事物间的关联规则，或称相关程度。关联规则的一般形式 是： 如果a 发生，则b 有百分之c 的可能性发生 c 称为关联规则的支持度( c o n f i d e n c e ) 。例如： 如果i b m 的股票价格上升，有7 0 的可能微软的股票价格要下降 序列模型( s e q u e n c em o d e l ) 与关联模型很相似，不同的是序列模型的对象是 在时域分布的，发现的规则也与先后顺序有关。 6 数据汇总( d a t as u m m a r y ) ”；1 数据汇总是对数据进行浓缩，给出它的紧凑描述。传统的也是最简单的数据 汇总方法是计算出数据库的字段上的求和值、平均值、方差值等统计值，或者用 直方图、饼状图等图形方式表示。数据汇总目前主要有两种技术：多维数据分析 方法和面向属性的归纳方法。 多维数据分析1 1 2 2 8 】 多维数据分析( m u l t i d i m e n s i o n a l d a t a a n a l y s i s ) 方法是一种数据仓库( d a t a w a r e h o u s e ) 技术，也称作联机分析处理( o n l i n ea n a l y t i e a p r o c e s s i n g ，简称 o l a p ) 或数据立方体( d a t a c u b e ) 方法。数据仓库是面向决策支持的、集成的、稳 定的、不同时间的历史数据集合。决策的前提是数据分析。在数据分析中经常要 用到诸如求和、总计、平均、最大、最小等汇总操作，这类操作的计算量特别大。 因此一种很自然的想法是，把汇总操作结果预先计算并存储起来，以便于决策支 持系统或其它数据挖掘应用系统的使用。存储汇总操作结果的地方称作多维数据 库，或形象地称为数据立方体。联机分析处理可以对数据立方体进行切片、切块、 钻取和旋转等操作，得到用户所需的分析结果。 面向属性技术眦】 为了处理联机数据，文章提出了一种面向属性的归纳方法。它的思路是直接 对用户感兴趣的数据视图( 用一般的s q l 查询语言即可获得) 进行泛化。方法 的提出者h a r t 对这种数据泛化技术称之为面向属性的归纳方法( a t t r i b u t e o r i e n t e d i n d u c t i o nm e t h o d ) 。面向属性的归纳方法是一种通用的技术，不仅可用于关系数 据库，同样可用于面向对象数据库、空间数据库，以及其它类型的数据库。这种 方法是一种泛化技术的方法，不适用于挖掘低层次上的具体模式。 0 决策树分类算法的研究及其在纳税评估中的应用 第三章分类算法及评价方法 本章介绍了分类数据挖掘算法，详细阐述了c 4 5 决策树算法的构造过程、 分枝准则以及剪枝策略等。最后给出了对于分类挖掘算法的实验评价方法。c 4 5 算法是我们在建立纳税评估有无避税嫌疑预测模块时所采用的决策树算法。 3 1 分类的定义 分类是数据挖掘领域的一种非常重要的方法。分类与聚类不同，聚类是对给 定的一组观察值建立类别，分类是己知现存的类别，要建立类别的描述规则，并 对新的观察值判别归类。聚类被称为无监督学习，分类被称为监督学习。在本论 文中，我们提到的分类问题，为监督学习问题 1 ”。 分类的概念是在己有数据的基础上建立一个分类函数或构造出一个分类模 型( 即我们通常所说的分类器：( c l a s s i f i e r ) ) 。该函数或模型能够把数据库中的数据 纪录映射到给定类别中的某一个，从而可以应用于数据预测。要构造分类器，需 要有一个训练样本数据集作为输入，训练集是构造分类器的基础。训练集 ( t r a i n i n gs e t ) f 1 一组数据库记录或元组构成，每个记录是一个由有关字段值组成 的特征向量，我们把这些字段称作属性( a t t r i b u t e ) ，把用于分类的属性叫做标签 ( l a b e l ) ，标签属性也就是样本的类别标记。标签属性的类型必须是离散的，且标 签属性的可能取值的数目越少越好( 最好是两个或三个值) 。标签值的数目越少， 构造出来的分类器的错误率越低。每一条记录实际上就是一个样本实例，一个具 体的样本的形式可以表示为( v 1 ，v 2 ，人，k ：c ) ，其中v 表示字段值，c 表示类别。 从训练集中自动构造出分类器的算法叫做生成器( i n d u c e r ) 。在生成分类器 后，可以利用它来对数据集中不包含标签属性的记录进行分类，标签属性的值也 可以用分类器来预测。 分类器的构造方法有统计方法、机器学习方法、神经网络方法等等。统计 方法包括贝叶斯法和非参数法( 近邻学习或基于事例的学习：i n s t a n c e - b a s e d l e a r n i n g ，i b l ) 。机器学习方法包括决策树方法和规则归纳法。神经网络方法主 要是b p 算法。在本章中，我们主要分析一种非参数方法，即不需要对数据进行 任何假设的方法，其代表方法是决策树，并详细介绍了决策树方法中具有代表性 的c 4 5 算法。 决策树分类算法的研究及其在纳税评估中的应用 3 2 决策树 3 2 1 决策树的基本概念 决策树方法起源于概念学习系统( c l s ：c o n c e p tl e a r n i n gs y s t e m ) ，然后发 展了i d 3 方法【2 , 2 9 1 并达到高峰，最后又演化为能处理连续型属性的c 4 5 。有名的 决策树方法还有c a r t 和a s s i s t a n t 。 决策树使用的是“分而治之”的策略。它将一个复杂的问题分成更简单的问 题并重复使用这一战术来解决子问题，从而将复杂的问题瓦解。子问题的解通过 组合可以产生复杂问题的解。这是一些众所周知的决策树算法的基本基础，如 i d 3 ，a s s i s t a n t ，c a r t ，c 4 5 等。近来一些统计软件包，如s p l u s ，s t a t i s t i c a 和s p s s 也已经移植了决策树的方法来处理分类和回归的问题。决策树的作用机 理就是将状态空间分成子空间，每个子空间可以适用于不同的模型。 决策树方法是一种通过构造决策树来发现 j i l 练集中分类知识的数据挖掘方 法，其核心是如何构造精度高、规模小的决策树。一个决策树应当是一个带有弧 线的图表。每个节点或者是一个有后续节点的分枝节点或者就是一个叶子节点。 一个叶节点用类来标示，一个分枝节点则对应一组测试数据集。 决策树构造的输入是一组带有类别标记的数据集，构造的结果是一棵二叉或 多叉树。二叉树的内部节点( 非叶子节点) 般表示为一个逻辑判断，如形式为 ( q = v t ) 的逻辑判断，其中a 。是属性，v ，是该属性的某个属性值。树的边是逻辑 判断的分支结果。多叉树的内部节点是最佳扩展属性，叶节点是类别属性值。内 部节点的射出边是最佳扩展属性的取值，有几个属性值，就有几条边。内部节点 对应的数据集是不纯的( 数据属于多种类别) ，根节点对应的数据集是训练集d ， 其它内部节点对应的数据集是d 的子集。叶节点对应的数据集是纯的训练子集 ( 数据属于同一类) ，树的叶子节点都是类别标记。 构造决策树分为两步：( 1 ) 决策树的生长：由训练集生成一棵决策树；( 2 ) 剪 枝：用非训练集中的事例检验生成的决策树，剪去影响预测精度的分枝。 找出最佳扩展属性是生长决策树的关键，它需要先确定扩展属性的形式，找 出符合这种形式的所有扩展属性，然后评价这些扩展属性，选出最具判别能力的 扩展属性作为最佳扩展属性。 扩展属性的形式有单属性、数值联合属性和逻辑联合属性。单属性是描述属 性，它的分枝根据属性的类型分为两种情况：离散型属性一般根据属性值分枝， 有几个属性值就分为几枝：连续性属性一般采用二分法分为两枝。数值型联合属 性的形式是：w 0 + w l 工“+ w ：x “+ a + 工”( 离散性属性应先数值化) ， 1 2 决策树分类算法的研究及其在纳税评估中的应用 x 1 ，x 2 ，a ， 是k 个不同单属性的属性值变量，w o ，w 1 ，人，是系数，f l ，t 2 ，a ，f 是 指数。若t = t ，= af 。= 1 ，则这种数值联合属性为线性联合属性，否则为非线性 联合属性。不同的属性变量、系数和指数构成的数值联合属性形