（计算机软件与理论专业论文）决策树分类方法及其在铁路客票营销分析中的应用.pdf

摘要 随着计算机科学的不断发展，大量的原始数据被不断收集并存储到计算机 中，面数援处理能力的低下，造成了尽嚣信息丰富，知识贫乏的现状。数据挖援 用非平凡的方法从大量数据中发现商用的知识，正是应此要求而迅速发展起 来的一门科学。数据挖掘包含众多任务，分类是其中一项被广泛应用舱技术。分 类经过长麓的发最已产生了众多算法，德其串大部分帮是内存驻留算法，通常假 定数据量很小。随著数据库中数据量越来越大，建立高效的、适用于大型数据库 系统款分炎葵i 翊置戏失数据挖攥懿一个瓣竣毪翔熬。 铁路中的客票系统蕴含了丰富的数据信息，如何从这海掇的信息中挖掘出有 用的知识，是一会亟待研究解决豹阀题。本文将数据挖掘中能分类技术月于铁鼹 客票营销分析中的客票分类，形成了一种新的分类方法t td t c ( d e c i s i o nt r e e c l a s s i f i c a t i o nb a s e do l lt r a i nt i c k e t s ) , 该方法针对铁路客票的实际特点，采用掰 的基于文件分割秘定量规则兹决燕树分类冀法s fd t ( d e c i s i o nt r e e c l a s s i f i c a t i o na l g o r i t h mb a s e do l ls p l i t t i n gf i l e s ) 对客票数据谶行分析，以达到依 攒窖票属黢特征对客蔡发售及列车运营蓊提避行势类及颈涎瓣鞫懿。该方法被瑙 予客票分析，得出了能够指导列车营运的非平凡模式和决策信息，实现了分类技 术与大规模客票数据库系统捆缝合的一次尝试。 t td t c 方法以铁路客票数据为基础，以铁路客票营销分析为目的，针对铁 路客票信息数据量大、属性复杂、域值广等特点，实现了从数据预处理、决策树 塞残至l 燕潮提取、戋识产生等一系列遥稳。该方法宪垒适应铁路窖票营销分析豹 需要，能够对客票数据进行较为有效的分析和处理，得出指导铁路营运的决策信 息。 s f _ d t 算法以决策树分类算法i d 3 的基本思想为基础，用基于文件分割的方 法代替原有的基于内存的算法，提高了算法的可规模性，可以处理超大觏模的数 据。另外，算法还产童了带有统计信息的定量规则，能够清晰地提供主类的分布 情况，为数据分析提供了更为详细的信息。 遥遘稀究，蔽镪为分类技术懿发震翎建了薪熬波蠢鹜豢，为其进一步研究奠 定了应用熬础。另方面，也将数据挖掘的技术用于铁路客浆营销分析，为铁路 客运豹台瑷安接及缎级管理提供了丰富豹决策信惠。 关键字：数据挖掘，分类，决策树，客票营销分析，定量规则，客运 a b s t r a c t w i t ht h ed e v e l o p m e n to fc o m p u t e rs c i e n c e ，m o r ea n dm o r eo r i g i n a ld a t ai s c o l l e e t e da n ds t o r e di nc o m p u t e r s 。t 如p o o r a b m t yo f m a n a g i n g d a t am a k e sd a t ar i c h a n dk n o w l e d g el e a n i ti sf o rt h i sr e a s o nt h a td a t am i n i n 幽t od i s c o v e ru s e f u l k n o w l e d g ef r o ma m o u n t o fd a t a b yu n c o m m o nm e t h o d s ，h a sd e v e l o p e dv e r yq u i c k l y c l a s s i f i c a t i o ni saw i d e l yu s e dt e c h n o l o g yi nd a t am i n i n g 。t h e r ea r em a n ya l g o r i t h m s t h a th a v eb e e n p r o p o s e dr e c e n t l y , b u tm o s to f t h e mw e r em e m o r yb a s e da n du s u a l l y a s s u m et h a tt h ea m o u n to fd a t ai sn o tv e r yl a r g e w 热t h el a r g e ra n d l a r g e ra m o u n t o f d a t a , i tb e c o m e sac h a l l e n g i n gp r o b l e mt of i n da ne f f i c i e n c yc l a s s i f i c a t i o na l g o r i t h m t h a ta d a p t st ol a r g ed a t a b a s e w i t l lr i c hd a t ai nw a i nt i c k e t s s y s t e m 。h o wt o m i n eu s e f u lk n o w l e d g ei sa l l i m p o r t a n tp r o b l e m a p p l y i n gt h et e c h n o l o g yo fc l a s s i f i c a t i o ni nt r a i nt i c k e t sa n a l y s i s ， w ec o n s t r u c tan e wc l a s s i f i c a t i o nm e t h o dt t _ d t c ( d e c i s i o nt r e ec l a s s i f i c a t i o n b a s e do nt r a i nt i c k e t s ) 。w ea p p l yn e wc l a s s i f i c a t i o na l g o r i t h ms f d t ( d e c i s i o n t r e ec l a s s i f i c a t i o na l g o r i t h mb a s e do n s p l i t t i n gf i l e s ) t h a t b a s e so n s p l i t t i n gf i l e sa n d q u a n t i t yr u l e s ，w h i c ha i m e da tt h ec h a r a c t e r so ft r a i nf i c k e t s w er e a l i z et h ea n a l y s i s a n d p r e d i c t i o na b o u tt i c k e t ss a l ea n d t r a i no p e r a t i o nb yt h i sm e t h o d t 毯sm e t h o dh a s b e e nu s e di nw a i nt i c k e t sa n a l y s i ss u c c e s s f u l l y , a n d p r o v i d e d b n c o i n i n o n p a t t e r n sa n d d e c i s i o n i n f o r m a t i o n ，a n da c c o m p l i s h e d t h ec o n n e c t i o nb e t w e e nc l a s s i f i c a t i o n t e c h n o l o g y a n d l a r g ed a t a b a s e + t t _ d t cr e a l i z e sas e r i e so fp r o c e s s e si n c l u d i n gd a t ap r e p r o c e s s ，d e c i s i o nt r e e c l a s s i f i c a t i o n ，p r o d u c i n gr u l e sa n dp r e d i c t i o na n a l y s i s ，w h i c hb a s e do nt h ed a t ao f t r a i nt i c k e t sa n da i m e da tt h ec h a r a c t e r so ft r a i nf i c k e bw h i c hh a v el a r g ea m o u n to f d a t aa n dc o m p l e xa t t r i b u t e s 羽_ l i sm e t h o dc a nf u l l ym e e tt r a i nt i c k e t s a n a l y s i si n r a i l w a y , c a l le f f i c i e n t l ya n a l y z e a n dd e a lw i t ht r a i nt i c k e t sa n da t t a i nd e c i s i o n k n o w l e d g e w h i c hd k e mt h et r a i n o p e r a t i o n 。 t h e a l g o r i t h mo fs f _ d t , w h i c h b a s e so nt h ei d e ao fd e c i s i o nt r e ec l a s s i f i c a t i o n a l g o r i t h mi d 3 ，u s et h em e a n so f f i l es p l i t t i n gt a k et h ep l a c eo f t h em e a n sw h i c hb a s e s o n m e m o r y i ti m p r o v e st h es c a l a b i l i t yo fc l a s s i f i c a t i o na l g o r i t h ma n dc a l ld e a lw i t h v e r yl a r g e d a t a b a s e m o r e o v e rt h i s a l g o r i t h m e a r l p r o d u c eq u a n t i t y r u l e sw i t h s t a t i s t i c a li n f o r m a t i o na n ds u p p l yt h ed i s t r i b u t i o no fm a i nc l a s si nd e t a i l s s oi tc a n s u p p l y m o r ed e t a i li n f o r m a t i o nf o rd a t a a n a l y s i s w ef o u n dan e w a p p l i c a t i o nb a c k g r o u n df o rc l a s s i f i c a t i o nf o rf u r t h e rr e s e a r c h m o r e o v e r , b ya p p l y i n gt h ec l a s s i f i c a t i o ni nt h et r a i nt i c k e t sa n a l y s i s ，w ep r o v i d er i c h d e c i s i 强i n f o r m a t i o nf o rt h e m a n a g e m e n t o f t r a i no p e r a t i o n k e yw o r d s ：d a t am i n i n g ，c l a s s i f i c a t i o n , d e c i s i o nt r e e ，t r a i nt i c k e t sa n a l y s i s ， q u a m i 够r u l e s ，p a s s e n g e rt r a n s p o r t h 决繁秘分类旁法及箕在铁路客幕营销分析中韵程疆 第一章绪论 尽管数据挖掘技术已经窝了很大的发展，并息应用于社会生产的蒜个方面， 但是鉴予铁路客票数据的特殊往，一直未能应用劐铁路客桑营销分帮千中。本文 针对客票数据的特点研制开发了适用予客票挖掘的决策树分类方法鞭d t c ， 并将其盘翅予铁路塞票营销分析，褥出了丰富的决策信息，用于指导裙车营运。 下面就论文的研究背景、研究意义以及论文的蹩体结构作一介绍。 l 。l 论文髓研究背景 在数据库技术迅猛发展的今天，人们产生和收集各种类型数据的能力迅速 提高，造成数据的大量堆积。其中包括条码在商晶中的广泛使用，商务、科学 和行政事务的计算机化，以及由文本和图像扫描平台到卫星遥感系统豹数据收 集工其静遴步。魏矫，律必全球信息系统的万维两的流幸予，更是将我们淹没在 数据和信息的汪洋太海中。存储数据的爆炸性增长激起了对新技术和自动工具 鹃嚣求，以帮助我们将海量数据转换成绩息和酝识。尽管很早就出魏了篱摹的 数据统计技术，能够对数据谶行一定的分析，但这远远不够，我们需要更为先 避的智g 数据分拯工其对海鬈鹣数据售感进露更为深入斡瑗鳃秘分磐擎。 因此，在商业领域和科学研究领域都迫切要求发展这样的技术，能够从如 此海量的数据中抽敬如非平凡模式，找出数据变化的规律和数据之潮的楣互依 存关系，使人们能够从宏观的商层次的角度来审视数据，充分发掘数掰的潜力， 指导人们的行为，为决策和科学发展提供有力的支持。 于是，数据挖搦由大量数据中，雳菲平凡的方法发现有用的知识，就 成了一种自然而迫切的社会需求。正是这种广泛的社会需求引起了人们的关注， 导致了数据挖撼研突翘蓬勃野展穗数据挖掘技米的不断进步。数据挖掘任务一 般可以分为两类：描述和预测。描述性挖掘刻画数据库中数据的一般特性；预 测性挖掇怒在当翦数据上进褥接薮，以送行颓溅。数据携掇主要袁狱下凄能： 对概念和类进行描述；利用关联分析发现关联规则；分类和预测；聚类分析； 孤立点分橱；演变分撰，攒述行为随时阀变化懿对象的规律或趋势，并对其建 模f 1 】磁。 数据库蕴含大量的信息，可以用来做出各种勰能的商务决策。农数据挖握 决镱糖分类隽法及箕在铁镶骞票营镛努辑孛斡盘甬 众多的功能中，分类是其中一项非常重要的任务。分类是这样的过程，它找出 绉述并区分数据类或穰念豹横嫠，以矮能够使薅模型预测类标号未知的对象类 【2 】。分类的目的是提出一个分类函数或分类模型，该模型能把数据库中的数据 项映射到绘定类剐中瓣菜一个。分类楚数据挖掘审的一令重要问题，匿蠹外的 研究人员在数据挖掘、统计分析、机器学习、神经网络、专家系统等领域中对 分类闻题避行了大鬟的硬究，提出了一系列鲍分类算法，如决策树分类、贝时 斯分类、贝叶斯网络和神经网络等( 详见【3 】) 。j 琏年来，分类技术已l 被广泛、 有效地应用于科学实验、医疗诊断、气象预擐、商业预测、寨件侦破等领域， 引起了工业界和学术界的极大关注。 决策树学习是以实例为基础的归纳学习方法【4 】【s 1 。它者眼于从一组无次序、 嚣痰羹| l 斡实镶中捺臻决策瓣袭示形式秘分类规赠。它采蕉蠹瓒向下静递归方式， 在决策树的内部结点进行属性的比较并根据不同属性值判断从该结点向下的分 枝，在决策树鼹时缩点得戮结论。所蔽从壤到时绦点翳一条籍径葳对应着一条 合取规则，整棵决策树就对应着一组析取表达式规则。决策树分类法实现简单， 层次绩椽涛曦，够产生荔予理烬和分析懿巍则，困既是臻蔻瘟援较必广泛懿 分类方法阶【1 0 1 。 本文中我们将决策树分类阕铁路客票营销分掇相结合，测用决策楗的方法 对客票数据进行分类，并将分类得出的预测信息，应用于铁路客运的上层决策 分析旧f l l 】【1 鲫。 我霞铁路窖票系统每嚣产生的售鬃记录高遮3 0 0 余万条，分布存储在各级 服务器的数据库中，以一定周期传输、汇总、集中到铁道部，数据经过整理压 缩劳长裁保存【l l 】h2 】。为了实现较高速发的怒大援模数据瘁套诲和多楚度豹统计 分析，铁道部门对上述交易数据进行了避一步的烂理和重组，形成了以决策分 粝鸯主要瓣的大型数据疼系统客鬃营销分稷蓉裂嘲，它是采震全耨戆数攒 模式组织的大型数据库系统，其中存储了大量的原始客票数据，这必数据规模 巨大，蕴涵丰富的决策信息和知识，开发这些宝赛驰信息资源，服务予客运营 销决策，是提高铁路客运市场竞争力的一项重要 壬务，也是目前迫切需要解决 的问题。 铁路客票营销分祈不仪仅是简单的统计分析，最主要的是散非平凡模式的 2 决策树分类青法爱其在铁路饔象营镳分辑串豹盘阉 知识提取。因此，我们需要利用其提供的良好的数据，结合数据挖掘的技术， 获中提炼出更为有踊的决策知识。本文将数据挖掘中分类的决策树惑想用于客 运营销分析中客票的属性分析，对客票发售的时间、数量、种类、列率运营的 特点等进褥分类亵疆溺，褥出客运中鹃羲于规律，提供给上屡决策部门避行进 一步的决策分析( 详见【1 1 1 ) 。 1 2 论文的研究意义 我国地广物博，人口巨大，市场经济的迅速发展需要人流物流的大规模转 移，氇就适成了莓前我国大规模的入日流动现状。特鬟是春节、寒暑假、五一、 十一长假更是客流的高峰，这种大规模的人口流动大大加重了客运负担。就我 国嚣蔫弱壤况，铁路运输仍然愚最重要豹客运方式，我蚕有大规模翡铁路阏络， 每天有几酉万的客流量，如何合理有效的组织客运，控帝9 客流，保证铁路畅通， 合理离效运转是一个常僮樽关注的谣蘧h “。 客票睹销分析怒对大规模客票数据进行的决饿分析，它建立在超大规模的 客票数据摩系统之上，该系绕包含蓑蓑干年的客浆发售记蒙，露这些数握中蕴 涵着丰富的决策信息。目前在这些数据上只能做些简单的统计分析，无法进 行真正意义上的营销分析，提取有用的决策信息。因此，急鼹将数据挖掘技术 葡客票营销分析葙结合，以使对巨量的客票数据进行分析和处理，产生应用予 铁路营销分析的决策知识。数据挖掘技术在铁路窖票分析中有着相当广泛的应 瘸蓠景，密票系统斡数器量錾繁重大，疆盈惫含麓丰塞的决策蓓怠，因魏，从 中挖掘出商用的知识模式指导列车营运，合理分配客流是非常必要和迫切需要 解决的阀鬏。 在数据挖掘技术日益成熟的今天，已经出现了很多数据挖掘的软件工具， 如s a s 、d b m i n e r 、b u s i n e s s o b j e e t 、q u e s t 、m i n e s e t 等。这些都是逶鼹豹数 据挖掘商业软件，它们都有较强的数据挖掘能力，能够对一定规模的商业数据 进行关联飙则、分类、聚类等操作。但这些工具对于超太规模的客票数据的她 理却受到缀大的限制，而且这些工具酌设诗着眼予通用的商业角度，因此不能 针对铁路裙票数据的实际情况进行相应的分析处遐，无法直接应用予客票数据 浆挖撼。 针对这种情况，本文着眼于铁路客票营销分析的具体情况，针对客票数据 决蒙裢分类旁法及其在铁链客票藿销分析中朗瘦麓 的具体特征和客票信息挖掘的具体要求，研究开发一种利用决策树分类的基本 恿想，适合予铁路客蔡努类鹣方法耵d t c ( d e c i s i o n t r e e c l a s s i f i c a t i o n b a s e d o n t r a i nt i c k e t s ) 。其中对决策糖分类算法进行了相成的改进，使之适台大规模客 桑数摄戆楚疆。零文零l 瘸改避 舞豹毅算法s f _ d t ( d e c i s i o nt r e ec l a s s i f i c a t i o n a l g o r i t h m b a s e d o n s p l i t f i n g f i l e s ) ，将数据挖掘分类中的决策树技术用予客票营 镶分橱孛麴客票穆类分接，报攫客票翡实际记录遴行实验，褥塞了猎簿列车营 运的决策信息，实现了分类技术在客票旃销分析中的应用。 通过研究，我们验涯了将数据挖掘技术应用予铁路窖檠营锩分析的可行性 和有效性，劳发现了相应的问题，也就是纯粹的理论研究与实际应用之间的差 距。我们针对铁道科学院电子计算技术研究所客隳分析的实际震要，努力从理 论和应用两个方面解决这个阐题。 1 3 论文的整体绫构 本文简要介绍了数据挖掘技术中的决策村分类及铁路客票营销分析的内 容，重点分缨我们针对铁路客梁营销分析设计开发的分类方法t td t c ，及改进 韵决策树分类算法s fd t ，最后将我们设计的决策树分类方法哪t c 和铁路 客票营销分柝相结食，对客檠数据进行分析。 各章内容安排如下： 第一帮绪论 介绍本文静研究背景及研究意义，总结整个研究工作的内容以 及论文的组织结构。 第二灌数蕹挖摇孛熬分类技术 首先对数据挖掘的基本慰想、方法、过程、内容进行简要介绍， 然惑燕点分缨分类的概念、基本感想及主要舞法，接下来舟绍零 文中应用的主臻方法一决策树分类。 第三颦铁路客票营销分析 本章主要介绍铁路客票篱销分析的内容和背景，客票数据的来 源及其特点，以及客票落销分析的内容和意义。 第溷鬻基予铁路客鬃薷锖分帮亍的决策瓣分类方法n d t c 本章详细介绍了决策树分类方法1 t - d t c 的全过程，从数据预 4 决锤键分类方法及其在铁褥窖票藿镇分辑中载班甩 第五章 第六嫩 处理、决策树分类算法、到剪枝、规则形成，最后对其中出现的 翊题进 亍分祈。其中详缁介绍了该分类方法的藿点内容基子 文件分割和定量规则的改进的决策树算法s f d t ，给出算法的 援述积实现过程。 t td t c 在铁路客票营销分析中的应用 本鬻将t td t c 方法应惩予铰爨容票营镑分梧，跟踪狂d t c 实现的全过程，从实例的角度详细分析整个方法的执行，并对 产生的结果进行分析，缮蹬有益予上层决策分辑的知识。 结束语 对全文进行总缝，并指嫩鼹要进一步傲的研究。 决镀藕赞类壳法疆其在铁游客幕营销分辑孛的蠹蹋 第二章数据挖掘中的分类技术 信息科学的发展引起数据的高度膨胀，如何有效地处理大规模的数据信息， 褥出有用知识，馒成为嚣藏俊褥关注的阏题。数掇挖掘放大援模数据孛发 现非平凡模式，正怒应此要求迅速发展起来的- - v j 科学。本章简要介绍了数据 挖掘及分类技术，并对其中的决策树分类做较为详细昀介缁。 2 1 数据挖掘概述 蘧麓镶惑科学鼓术弱迅速发建，数掇量鑫盏纛大，数据麴浚集箱存镶邀越 来越容易。一方面，许多新型的数据收集过程更有效、更精确。例如，在商场 销售系统中使用斡条碣读入器能够分辨掰败买纛菇憨秘类、凝号及侩揍等售塞， 使商场能够很容易收集到完善的销售记渌。许多原来依靠人工才能完成的数据 收集过程殴经半自动化或全自动化，使褥单位时阅内可以收集到的数据量迅速 增加。此辫，一些新的装置能够收集原来很困难躐根本不可能收集到的信息。 另一方面，数据存储设备的价格已大幅下降，存储的形式甏趋多样化，且性能 趸强。一魏新懿存德奔震，镄翔可读写豹先盘，w 戳方便撼存储大蝥豹数据。 由于以上两方面的原因，使得目前能够以合理的成本收集和存储大量的数据， 这些数摇一般毒德予鼗器摩孛，铁零l 予梭索帮嚣绥戆处理。 这些既为从数据中抽取有用的信息提供了机遇，同时也给大规模数据的知 识接取撮爨了挑竣。麓蕈的绞计分橱，跑据计算媳篷、标臻方差等，一定程度 上是有用的。但是，这种简单分析的结果还不能够揭示出隐含在大量数据中的 知识。因此，急需一军申好的方法对大规模的数据避行分拆处理。 数据挖掘，又称数据库中的知识发现，是描从数据库中提取非平凡模式 【2 】【1 3 】。这燃模式是有效的、新颖的、有潜在实用价值的和易于理解的。提取的 知识霹戳袭示为禳念、规粥、规律和禳残等形式。 数据挖掘作为知识发现的过程，分三个主要阶段：数据准备、数据挖掘、 结采评价灏表这暖 ( 1 ) 数据准备 数蘩瞧签除段囊一些子狳浚穆藏，箕孛包摇：数据涛溪( d a t a 如蕊n g ) ， 去除噪声或不一致的数据；数据集成( d a t ai n t e g r a t i n g ) ，将多个数据源的数据 6 决镶挺努类鸯法及其在铁终客票营销分辑串鞠盛精 归并在一起；数据选择( d a t as e l e c t i n g ) ，从数据库中检索与分析任务相关的数 攥；数器变换( d a t a t r a n s f o r m i n g ) ，将数撩交换或统一成适合挖掘的形袋e ( 2 ) 数据挖掘 数据挖掘除段楚知识发袋过程中的核心除段。在这个狯段，采鬻蒗予智能 的方法去提取数据模式，其中包括的要点有： 掘程产生瑕设：也裁怒让数据挖掇系统隽惩户产生镁浚，还楚攥户自己 对于数据摩中可能包含的知识提出假设的问题。前一种称为发现型 ( 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 ) 数据 挖掘。 选择合适的挖掘工具。 知识挖掘静操作。 验证发现的知识。 ( 3 ) 结果评俊霹表达 根据用户的决策目的，对提取的倍息进行分析和评价，把最有价值的信息 嚣分出来，共量逶遐决策支持工具提交绘决策考。这一步豹镊务不仪懋怒结果 表达出来，还要对挖掘出的数据模式进行评价、过滤处理。 2 2 分类 分类是数据挖掘中一项非常重要的任务，目前在商业上应用非常广泛1 4 】。 下嚣对分类接本骰更为详缨戆奔绍。 2 2 1 分类的基本概念 分类( c l a s s i f i c a t i o n ) 是攒提出一个分类丞数或分类模鍪( 也穗终分类器) ， 该模型能把数据库中的数据项映射到给定类别中的某一个1 2 1 。数据分类是一个 两步过程； 第一步，建立一个模型，描述预定的数据类或概念集。通过分析由属性描 述的数据库元组来构造模型。假定每个元组属于一个预定义的类，由一个称作 梁标号瘸性豹属性确定。对予分类，数据元组也称作样本、实铡或对象。为建 拒模型而被分析的数据元组影成训练数据集。训练数据集中的单个元组称作训 练徉零，荠隧惑遮内样本群选取。由予提供了每个调练样本的类标弩，该步骤 也称作有指导的学习( 即在被告知每个训练样本属于哪个类的指导下进行模型 决策树分类方法及其在铁路客票营销分析孛的瘟舄 戆学习) 。它不霜予无撵导豹学习( 如袋类) ，在郑里，每个调练样本鹊类标号 是未知的，要学习的类集合和数量也可能事先不知道。通常，学习模测用分类 烧刘、决策树或数学公式豹形式提供。该溉剐可滋用来瓷以后翡数据样本分类， 也能对数据库的内容提供更好的理解。 第二步，使用模型进行分类。首先译佑模型( 分类法) 的礞测准确率。保 持( h o l d o m ) 方法魑一种使用桊标号样本测试集的简单方法。这些样本随机选 取，并独立于训练样本。对于每个测试样本，将融知的类标号与该样本的学习 模型类预测比较。被模型正确分类的测试样本的褥分比就楚模型在给定测试集 上的准确率。注意，如果模型的准确率根据训练数据集评估，评估可能是乐观 酌，医兔学习模鍪l 倾向予过分适合数据( 韶，它荀能并入曹i l 练数据中菜些异常， 这些异常不出现在总体样本群中) 。因此，通常使用测试集来评估分类算法的准 确率。鬣果认为摸型的准确率胃戮接受，就可默翔它对类标号未知的数程元组 或对象进行分类。 2 。2 。2 分类的基本技术 经过多年的研究，目前已产生了众多的分类技术，下面将简要介绍一些常 用戆分类鼓本，鸯馨决策辩分类、燹时裁分类、基予搴孛经圈终瓣分类，黻及源予 关联规则挖掘概念的分类【3 】f 1 ”。 ( - - ) 决策褥分类 基于决策树的分类方法是一种监督学习的方法【1 5 】- 1 2 0 ，树的数量由分类的精 度和树的大小决定。这种方法蓠先选择训练样本熬一令子集以形成一橡决策挺， 如果此树没有为所有的对象给出一个芷确的答案，则将例外情况加入到树中， 不断重复这一过程直到发现正确的决定榘。最终将形成这样一棵树：每一片盱 子代表一个类名，每个内部节点描述一个属性，节点的每一个分枝对应于该属 性的每一个可能的值。 关于捩策耱分类在第三繁串详箍套缡。 ( 二) 贝叶斯分类 贝时斯分类是统计学分类方法，它麓于贝时新定理【捌。可以预测类成员关 系的可能性，如给寇样本属于个特定类的概率。 分类算法酾院较磷究发现，一种称佟朴素翼时斯分类的简单贝叶簸分类算 决镣挺分类京法爱其在铁海客票营镑馈辑中韵敷褥 法可以与决策树和神经网络分类算法相媲美。朴素贝叶斯分类假定一个属性值 对给定类的影晌独立于其它耩性的值。该假定称作类条件独立。散此假定是为 了简化所需计算，并在此意义下称为“朴素的”。理论上讲，与其它所肖分类算 法楣毙，贝时蓑分类具有最， 、熬出错率。然两，实践牵并簿总是如魏，这是由 于对其应用的假定( 如类条件独立性) 的不准确性，以及缺泛可用的概率数据 造成懿。 朴素贝叶斯分类假定类条传独立，即给定样本的类标号，属性的值相互条 孛独立。这一假定镌化了计冀。当瑕定成立时，与其它援鸯分类算法稠毙，$ 索贝叶斯分类是最精确的。然而，在实践中，变赞之间的依赖可能存在。贝叶 巅信念刚络说明联合概率分布，能表示属性子集闻的依赖，弥补了 索贝叶斯 分类的不足。它允许在变量豹予集间定义类条件独立性。它提供一种因采关系 的图形，可阱在其上进行学习。在学习或训练信念网络时，许多情况都是可能 的。弼络结构霹g l 预先给定，或由数据等密。网络变量可能是可见静，或隐藏 在所有或某些训练样本中。隐藏数据的情况也称为空缺值或不完全数据。如果 羽终缝构酲强蒡量变量是哥藏麴，训练阚络毒豁警接送行。该逶覆垂计算c p t 项组成，与朴素贝叶斯分类涉及的计算概率类似。当网络结构给定，丽某些变 璧是隐藏的时，则霹使用梯魔下海方法谖练售念髓终。 贝叶斯网络的研究在国外十分广泛，它可以对不确定性知识迸彳亍推理。例 如：医生看病，根据病人的疲状，判断瘸人是否得了菜穆疾病，往绽是一种不 确定的推理( 带概翠的推理) ，多数情况下没有百分之百的把握。运用贝叶斯网 络进行推理，可以达到较好的效果。 ( 三) 基于神经网络的分类 神经网络最早照由心理学家和神经举家提出的，旨在罨求开发和澳4 试神经 静计算穰拟。褪略辘说，神经网络是一缀连接的输入糯出单元，其中每个连接 都与一个权相联。在学习阶段，通过调熬神经网络的权，利用预测输入样本的 正确类标号来学习。由于擎元之阕鹣连接，神经丽络学习又称连接者学习 【1 9 】【2 0 】雎1 1 。 撩经网络嚣要很长的潮练对间，因露对于有足够长铡练时间蛉建鞠更合适。 神经网络已| 经在很多领域得到了成功的应用，但由于缺乏严密的理论体系的指 决镣撼静类方法及其在铁魏窖票藿镳分橇孛匏寝甬 导，其应用效果完全取决于使用者的经验。虽然h o r n i k 等人证明，仅商一个非 线牲隐整鹣前馕潮络就能戳任意疆瘦遥避任意复杂度浆嚣数，毽一些研究者指 出，对网络的配置和训练是n p 问题。在实际应用中，由于缺乏问题的先验知 识，往往鼹经大量赞力耗对驰实验摸索孝能确定会逶豹专枣经鼷终摸受、算法良 及参数设置，其应用效果完全取决于使用者的经验。即使采用同样的方法解决 同样的闻题，由于操作者不同，其结果也很可能大糖径庭。另终，由予人们缀 难解释蕴涵在学习权之中韵符号含义，神经网络常常因其可解释性差而受到批 评。这些特点使得神经网络在数据挖掘的初期并不看好。 然焉，卒孛经两络的优点包括其对嗓谱数据的离承受能力，以及它对未经训 练的数据的分类能力。此外，最近已提出了一些由训练过的神经网络提取规则 熬算法，这些因素撼动了襻缀网终在数据挖掘分类方面静瘦爆。 ( 四) 源于关联规则挖掘概念的分类 关联麓粼挖掘怒数蕹挖瓣磷究静一个重要的、高度活跃静领域h 9 1 。最近， 数据挖掘技术己将关联规则挖掘用于分类问题。下面，我们按历史次序简要介 绥三秘方法。羲嚣释方法，a r c s 帮关联分类，嫒用关联规剽分类。第三群方 法c a e p 挖掘“显露模式”，宦考虑挖掘关联规则使用的支持度概念。 第一秘方法，基于聚类挖撅关联规则，然羼使用规则进行分类。a r c s 或关 联规则聚淡系统挖掘形如a q 。m l 。味苷a 。m 的关联规则；菠中，a q u 枷l ，a q 。“1 2 是在量化属性区间上的测试( 区闯动态地确定) ，褥氏。为给定训练数据的分类 满性指定一个类标号。关联规则画在2 - 1 ) 栅格上。算法扫描栅格，搜索规则的 矩形聚类。用这种办法，出现在一个规贝| j 聚类内的量化属性的楣邻区间可以结 会。壶a r c s 产生瀚聚类关联蕊燹| l 霜予分类，其臻确率可与c 4 。5 媲美。 第二种方法称作关联分类。它挖掘形如c o n d s e t ；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 r 集合。这 1 0 决繁树分类去法及其在铁潞窖票营销论辑中的硒 麓是类关联瓣弼( e a 釉。荚c o n d s e t 奄会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 s _ c o m p u t e r = “y e s 或c l 和 b u y s _ c o m p u t e r = “n o 或c 2 。袋集 a g e 菇一- 3 0 ，：s t u d e n t s 。w 是一个典型的 e p ，其支持度由在c l 中的o 2 增长到猩c 2 中的5 7 6 ，增长率罟等= 2 8 8 。 注意，一个项或者避分类属性上的简单棚等测试，或者是梭饔数值璃能是否在 桀个区间的测试。每个e p 是一个多属性上的测试，并且可能在区分一个类的 实钢与另一个类静实镄方嚣菲常强。雾 | 翔，弼采一个新样本x 雹台在上嚣静e p 中，我们可以说x 属于c 2 的几率为9 9 6 。一般地，e p 的区分能力火约正比 予它懿撞长率纛宅穗嚣糖类豹支簿度。 一种将代的分类算法称作j e p 分类算法( j e pc l a s s i f i e r ) ；该算法怒基于跳 跃显露模式( j u m p i n g e m e r g i n g p a t t e r n ，j e p ) 提出的。其中，j e p 是一释特殊类 型的e p ，定义为这样的项集，其支持度由在一个数据集中的0 陡峭地增长到另 一个数据袋中的非0 。医为j e p 具有无穷大的增长攀，而e p 爨有有穷的增长率， 所以j e p 比e p 的隧分能力懿强。这使褥在许多大型数据群( 尤其是维数也很 大的数据麾) 中，糕于j e p 的分类算法优于基于船的分类葬法。 2 2 3 分类算法豹阮较标准 常用的分类算法的比较和评估标准肖以下几点： ( 1 ) 预铡静壤确率：涉及模型正确魏预测新豹或先前寒见过的数据的类标 号的能力。 ( 2 ) 速菠：涉及产生秘矮霜模墼斡诗算花赞。 ( 3 ) 强壮性：涉及给定噪音数据或具有空缺值的数据，模型正确预测的能 力。 ( 4 ) 可规模性：涉及给定大量数据，有效地构造模型的能力。 ( 5 ) 可解释性：涉及学淫模型提供憋理鳃翻漏察的屡次。 决镶褥静粪方法及萁在铁鼹骞票营销静辑串靛敷稿 目前，已有许多关于不同分类算法的比较，并且该问题仍然是一个研究课 藤。海未发现有秘算法对掰有数据都饶于其它方法。魏准确性、调练时闯、 强壮性、可解释性和可规模性必须考虑，并且可能涉及折衷，使得寻求更好方 法进一步复杂经。实验研究表麓，许多冀法豹准确性豢癸似，其差溺是统计 不明显的，而训练时间可能显著不同。另外，可规模性也是目前考虑较多的一 个嚣素，峦予出瑷了越来越多瓣超大援摸静数据瘁系统，魇戮是否熬够有效蟪 处理大规模数据也成为衡量算法的重要标准。 2 。3 决策树分类 分类是数据挖掘中一项非常重要的任务，分类的目的怒提出一个分类函数 或分类摸型( 分类器) ，该攘燮娩把数据痒孛鹁数据项获射裂给定类裂巾豹某一 个。决策树学习是以实例为基础的归纳学习算法。它着眼于从一组无次序、无 翘劐的事例中推出决策树表示形式的分类规刘。它采用蠡 樊向下的递归方式， 在决策树的内部结点进行属性的比较并根据不同属性值判断从该结点向下的分 棱，在决策树的叶缩点褥到结论。所以从根到叶结点的一条路径就对应着一条 龠取规剐，整操决策树就对藏着一组析取表达式规则i 2 0 】。 一棵决策树的内部结点是属性或属性集，叶结点是所要学习划分的类【1 6 1 。 造经过一撬譬l | 练实翻集敬调练产生一裸决策树，决策树茸戳根据属佼豹取蓬对 一个未知实例集进行分类。使用决策树分类的时候，由树搬开始对该对象的属 链遂一测试其毽，弗且顺羞分技匀下走，壹至到达菜拿辞终点，毙跨络点代表 的类即为对象所处的类。 2 。3 。1 基本恿想 决策树分类是一种以决镣树这种数据结构为基础的分类算法1 1 5 州9 】。决策树 ( d e c i s i o nt r e e ) ，又称判定糖，是一个类壁雯予滚糕圈戆撼缭麴，其中每个内部 结点表示在一个属性上的测试，每个分枝代表一个测试输出，而每个树叶结点 代表类或类分布。为了对未知的样本分类，样本的属性僮农判定楗上测试，路 径由根到存放该样本预测的时结点。决策树很容翳转换成分类规则【3 4 1 【3 鳓。 决策树归纳的基本算法悬贪心算法，它是以自顶向下递归的各个诲破方式 梅造决策树。算法的基本策略如下【1 朝： ( 1 ) 树以代表训练样本的单个结点开始。 决饿树分类夯法及其在铁鼹客票营销分析中曲盛嗣 ( 2 ) 如累样本都在同一个类，则该结熹残为树时，势用该类标记。 ( 3 ) 否则，算法使用称为信息增靛的基于熵的度量作为启发信息，选择 髓够最盎 遮将样本分类的属梭。该属性成蕊该续患的“测试”或“决 策”属性。 ( 4 ) 对测试属性的每个殴知的馕，剑建一个分技，并据此划分样本。 ( 5 ) 算法使翊同样的过稷，递归地形成每个划分上的样本决策树。一旦 一个属性出现在一个结点上，就不必在该结点的任何后代上考虑它。 ( 6 ) 递妇翊分步骤仅警下菊条 串之一成立对停止： 给定结点的所有样本属于同一类。 没商剩余霾饿霹以用来避一步划分样本。农此情嚣下，使用多 数袭决。这涉及将给定的结点转换成树叶，并用样本中的多数 鼹在的类标记宅。替换缝，霹以存放缝点样本的类分毒。 分枝t e s ta t t r i b u t e = 口f 没有样本。在这种情况下，以样本中的 多数类创建一个越时。 在树的每个结点上使用信息增益( i n f o r m a t i o ng a i n ) 度量选择测试属性。 这种度量称作属性选择度量或分裂的优劣度量。选器具有媛齑信息增薤( 或最 大熵压缩) 的属性作为当前缩点的测试涡性。该属性使得对结果划分中的样本 分类所需的信息量最小，并反映划分的最小随机性或“不纯性”。这申信息理论 方法使得对一个对象分类所鬻的期望测试数强最小，并确保找到一棵简单的树。 设s 是s 个数据样本的集合。假定类标号属性具有m 个不同值，定义m 个 苓嚣类c i ( i = l ，+ ，哟。设毋楚类c 中的样本数。对一个绘定的样本分类所器的 期望信息由下式给出： * 砸l ，s 2 ，$ 。) = p fl 0 9 2 ( p 1 ) j 1 1 其中，辣是任意撵本耩予舀瀚概率，并瘸曲s 话诗。注意，对数函数戳2 为底， 因为信息用二进位编码。 设属性崖具鸯v 个不矮嫠 露。硝e 霹菝罴属性蠢将s 划分走v 个子集 & ，。 岛 ；其中，s g 含s 中这样一些样本，它们在4 上具有值嘶。如果一选作测试 属性( 即，最好静划分属性) ，则这些子集对应于鸯趣含集合s 懿结蔗生长出采 决镶楗癸类宠漩及其在铁镶客票营镜分辑中钓盘臻 的分枝。设曲是子集s j 中类a 的样本数。根据爿划分子集的熵( e n 廿o p y ) 或期望 镶惠盘下鼗绘密： g ( a ) ：窆型竿玛吣，嘶) f 硝 。 项旦坐二i ：! 堕充当第j 个子集的权，并风等于子集( 即，a 值为a j ) 中的样本 个数豫戳s 中懿群零总数。麓谯越小，子集麓分的统度越麓。注意，辩于给定 的子集s ， 砸s 护，s w ) = p 口l 0 9 2 ( 聊) 其中，p f = 羔，怒昌中的样本属于舀的概率。 i u ，l 在上分棱将获得懿编磷信息是 g a i n ( a ) = j 瓴，s 2 ，) 一e o ) 换言之，g a i n ( a ) 魁由于知道j j 甄性的假而导致的熵的期望雁缩。 算法计算每个麟性的信崽增益。具有最毫信爨增益毂鼹性选终绘定集会s 的测试属性。创建一个结点，并以该属性标记，对属性的每个值创建分枝，并 据此划分样本。 基予多种原因，决策树分类已经被广泛地粥予多种数据挖掘工其中，用乎 产生分类