（计算机软件与理论专业论文）基于ifn的客票营销分析方法的研究.pdf

基于i f n 的客票营销分析方法的研究 内容摘要 随着铁路信息化的发展，铁路客票营销系统积累了丰富的数据，如何以较少 的人力和技术成本合理利用现有的客票数据资源获取有价值的决策信息，臼趋成 为铁路决策部门的迫切需求和铁路客票营销相关部门的工作重点。目前客票中心 对客票营销分析的研究工作仍处于初步的数据统计阶段，这种常规的统讨汇总方 法很难建立有效的预测模型。基于d 3 算法的客票分析方法可以建立较好的预测 分析模型，但是从模型中提取的规则集合规模较大，从中提取决策者感兴趣的规 则比较困难，这是客票营销分析中存在的一个的问题。 针对以上客票营销分析存在的问题，本文以铁路客运为背景，采用 i f n ( i n f o m a t i o n f l i z z yn e t w o r k ) 算法建立相应的数据分析模型，并对其进行了深 入的研究和实验。i f n 算法用互信息度量输入属性，从全局的角度选择较小的输 入属性集合，建立比决策树更简洁准确的网络模型，此模型构造的成本低于其他 分类算法，可从模型中提取维数较少的输入属性和目标属性问的关联规则。i f n 算法中采用的预剪枝的方法是用似然比评估属性在统计上的显著性来判断结点 是否分裂，其优点就是在计算资源受限的情况下可以随时停止模型的构造，得到 的规则集合比传统算法得到的规则集合更简洁，而且也不会产生过度拟合问题。 基于i f n 的方法已经被很好地应用在软件测试、时问序列数据库、医学以及制 造业等领域。根据i f n 算法的这些特点，本文给出了其对实际客票数掘进行数 据分析时建立的预测分析模型，经实验验证了该方法在改善客票数据分析的综合 性能、提高客票营销分析的准确性上的有效性。 研究表明，i f n 算法所建立的客票营销分析的预测模型结点数较少，从模型 中提取的规则集合规模适宜。相对于i d 3 算法建立的预测分析模型可以更有效地 满足铁路客票营销分析的需求，为客票营销分析进一步的研究工作奠定了良好的 基础并提供了一定的理论指导。 关键词：i f n ，互信息，似然比，数据挖掘，分类，铁路客票营销分析 基于i f n 的客票营悄分析方法的研究 a b s t r a c t w i mt l l ed e v c l o p m e n to fi n f o r m a t i o nt e c h n o l o 夥o fc i l i n e s e 痂1 w a y ，r i c ht i c k e t d a t ah a v eb e e nc o l l e c t e di nc h j n ar a i l w a yt r a i ns y s t e m ( c r t t s ) m a k i n gg o o du s e o fm ec u n - e n tt i c k e ti i l | 0 m l a t i o nd a t at oa c q u i r ev a l u a b l ed e c i s i o ni n f 0 肿a t i o nw i t h l e s sh u m a na n dt e c h i l i q u er e s o u r c e si sb c 。o t i l i n gb o m i eu r g e n td e m a i l df o rt h e r a i l w a yd e c i s i o nd e p a r h n e n ia n dt 1 1 ek e yp o i n tf o rt h ei n f o r m a t i o nd 印a 咖e n t sw o r k t h er e s e a r c ho fd c k e tc e n t e ri nc r t t si ss t i ui ni t si n i t i a is t a g e so fs t a t i s t i c a ld a t a ， h o w e v e r c o n v e 】啦i o n a ls t a t i s 蛀c a l1 i 坨删sa r ed i 矗i c u l tt oe s t a b l i s ha ne 丘b c t i v e a g 辨g a t i o np r e d i c t i v em o d e l s i 【ba l g o r i m m sb 鹳e i lo np 硒s e n g e rt i c k e t sa n a l y t i c a l m e t l l o d sc a ne s t a b l i s hb e t t e rp r e d i c t i o na r l a l y s i sm o d e l s ，b u tm o d e l sw i m d r a w 丹d m t 1 1 e1 a r g e rn 】1 es e t s ，c x 昀c t i n gn o v e lr u j e s 舶mw 】1 i c hi sm o r ed j 塌c u 】ff o rd e c i s i o n m a k e r s ，w h i c hi st h ep r o b l e mi nc i u t s a i m e dt ot 1 1 ep r o b l 锄ss h o wa b o v e ，r e g a r d i n gt h er a i l w a yp a s s e l l g e rt r a 衔ca s o u rb a c 蜒即u n d ，w ed od e 印l yr e s e a r c ha r l de x p e r i m e n t so ni f n ( i n f o 肌“o n f u z z y n e t w o r k ) a l g o d t h i l lt oe s t a b l i s ht l l ec o r r e s p o n d m gd a t aa n a l y s i sm o d e l s t h ei f n a 1 9 0 r i m mm e a s u r e sm ei n p u ta t 晡b u t e sb ym u t u a li n f o m l a t 岫玛a i l ds e l e c t ss m a l l e rs e t o f 砌b u t e s 仃o mt h ep e r s p e “v eo fo v e r a i l ，w h i c hc a np r o d u c em u c hm o r ec o m p a c t m o d d sn l a no m e rm e t h o d so fd c c i s i o n t r e e1 e a n l i n gw h i l ep r e s e i n gn e a r l y l es 锄e 1 e v e ro fc i a s s i f i c a t i o na c c u r a c y t h em o d e lc o i l s t r l l c t i o c o s ti sj e s st h 肌o t h e r c l a s s 姬c a t j o na l g o r i l m s ，w “c hc a nb e 镪打a c t e d 如maf 押s m a l l 盯a s s o c i a “o nr u j 鄙 b e 哪e e l l i n p u ta b u t e sa n dt a r g e ta 吲b u t e s t h ep r e - p m l l i n gm e 山o do fi f n a l g o r i m m su s el i k e l i h o o d - r a 石o s t a t i ct oe v a l u a t et l es t a t i s t i c a ls i 鲫f l c a f l c eo ft h e c o n d i t i o n a lm u t u a li n f o 衄a t i o nb e 押e e nai n p u t 删b u t ea n dm et a 唱e ta t 啊b u t e t h e o u t s t a l l d i n gs 廿o n g p o i mo fm ei f na 1 8 0 r i t h i n sp r e p r u n i n gi sm a tt h em o d e l c o n s 咖c t i o nc a nb es u s p e n d e da t 觚yt i m ew t 吼也ec o m p u t i n gr e s o u r c e sa r el i m i t e d ； a n dm er u l es c td b t 如e di sn o tl a r g e rt h a nt h eo n eo b 诅i n e db ya s s o c i a t i o nr u i e a l g o t h m ；m o r e o ve r i td o e sn o th a v et os u s p e n dt h en e tc o n s 1 l c t i o nf o r t h e n 基于i f n 的客票营销分析方法的研究 a v o i d a l l c eo fo v e rf i to rt h ef i n d i n go ft l l eb e s tn e tm o d e l t h em e 吐l o db a s c do ni f n h a v eb e c ni m p l e l l l e l l t e di nt l l ef i d d s 锄c h 船s o m v a r et e s t i n g ，廿m e s e q u e n c ed a t a b a s e ， m e d i c i n e 趾dm a i l u f a c t u r i r 培c t c a c r d i n gt ot l l ec h a r a c t e r so f t l l ei f na l g o 一衄，t 1 1 i s p a p e rp r e s e n t st l l e d a t aa n a l y s i sm o d d 铝t a b l i s h e do ft 1 1 e c a lh c k c td a t a t h e e x p e r i m e n t a l v a l i d a t c st l l i sd a t aa n a l y s i sm e t h o d sc a n i i n p m v e m ei n t e g r a t e d p c r f b m a l l c eo f p a s s e n g e rt i c k e t s 姐a l y s i s 锄d 血ea c c u r a c yi i lc 盯r s s t l l d i e sh a v es h o w nm a ti f na 1 9 0 删：l m se s t a b h s h c da n a l y s i sp r e d i c t i o nm o d e l c l i s t o m sf o rc r ，兀、sh a sf e w e rn o d e s a i l d 血es i z eo f m l es c tc x t r a c t e d 仔o mt h em o d e l i ss l l i t a b l e c o m p a r c dt om ep r e d i c t i v em o d do fi d 3a l g o r i t 畹，血em o d do fi f n a 1 9 0 r i m mc a nm e 就血en e e d so fr 8 i l w a yp a s s e i l g c rd c k e t sm a r k e t i n ga n a l y s i s t h i s p r o v i d e saf h v o n b l e 伊o u n d w o r kt om a k e 缸曲c rr e s e a r c h e sa i l dp m v i d e ss o m e g u i d a n c e k e y w o r d ：i f n ，m u t u a l i n f o m a t i o n ，l i k d i h o o d r a t i o ，d a t am i l l i n d a s s i f i c a t i o n ， r a i l w a yt i c k c t sm a r k e t n ga n a l y s i s i i i 郑重声明 本文的学位论文是在导师指导下独立撰写并完成的，学位论文除 明确标注外没有剽窃、抄袭等违反学术道德、学术规范的侵权行为， 否则，本人愿意承担由此产生的切责任和法律后果，特此郑重声明 学位论文作者( 签名) ： 黝 差 吖? 年月1 日 d e c l a r a t i o n t h i s i s t oc e m 匆t 1 1 a t 1 1 1 l i sm e s i sc o m p r i s e so n l ym yo 订昏n a lw o r kt o w a r d s 也e d e g r e eo f m a s t e rc x c e p tw h e r ci n d i c a t e di nt h ep r c 睹l c e ， 2 【m ea c l ( 1 l o w l e d g e m e n th a sb e 铋m a d ei nt l l et c x tt oa l lo t h e r m a t e r i a lu s e d 3 t h i st l l e s i si sl e s sm a i l5 0 ，0 0 0w o r d si nl e n g t l l ，e x c l u s i v eo f t a b l e s ，m a p s ，b i b l i o g r a p h i e sa 1 1 d 印p e l l d i c e s y a n y a l l “ b e ( z h e n g z h o uu i l i v e r s i t y c h i l l a ，2 0 0 3 ) m a y 2 0 0 6 基于i f n 的客票营销分析方法的研究 第一章绪论 我国幅员辽阔，铁路纵横交错，随着经济的发展，人口流动规模也越来越大。 如何合理有效地组织客运，保证铁路畅通、高效运转是一个值得关注的问题。铁 路客票发售与预定系统每天实时产生和不断积累大量客票发售数据。开发这些数 据资源，提取有用知识，服务客运管理、营销决策，是铁路客运营销部门的迫切 需求。本文根据铁路客票数据的特点用一个新颖的数据分析方法对其进行研究分 析，提取铁路系统决策者所需要的信息知识。 下面将就论文所基于的研究背景和意义、研究现状以及论文的整体布局进行 介绍。 1 1 研究背景和现状 数据库技术的迅速发展以及数据库管理系统的广泛应用，导致人们积累了越 来越多的数据。巨增的数据背后蕴藏着丰富的知识，而目前的数据库技术虽可以 高效地实现数据的查询、统计等功能，但却无法发现数据中存在的关系和规则， 无法根据现有的数据预测未来的发展趋势。数据库中存在着大量的数据，却缺乏 挖掘数据背后隐藏的知识的手段，出现了“数据爆炸而知识贫乏”的现象。在此 背景下，数据库知识发现( k d d ) 及其核心技术数据挖掘( d m ) 便应运而生了。 k d d 的研究内容是，能自动地去处理数据库中大量的原始数据，从中挖掘搜索 出具有规律、富有意义的模式。它的发现过程主要有三个步骤：定义要发现的问 题；根据问题进行数据搜索、模式抽取；评价所发现的知识的好坏。三者之中， 核心技术是第二步，即数据搜索及模式抽取方法。 中国铁路客票发售和预订系统建设和联网售票的实现，极大地方便了旅客购 票，有力推动了客运营销的改革，同时也积累了大量客票发信的生产数据。这些 数据规模巨大，蕴涵丰富的决策信息和知识，开发这些宝贵的信息资源，服务于 客运营销决策，为铁路客运管理人员了解现场售票情况，进行席位发售、售票收 入和客流统计分析、预测、以及辅助决策提供了依据。铁路客票营销分析是铁道 部、铁路局、分局业务管理系统的重要组成部分，系统地、科学地利用这些数据， 基于i f n 的客票营销分析方法的研究 建立铁路客票营销分析系统，对客运管理部门及时做出正确决策，进行合理的运 输调整具有重要意义；同时也是提高铁路客运经营水平、增强铁路客运市场竞争 能力的有力措施【l l 【甜。 目前，客票营销分析系统是以客票数据为依据采用常规的统计方法对旅客发 送、到达、运送人数、旅客周转量、旅客平均行程、旅客运输密度、客流流向、 客票发售和预售情况及票款收入等进行汇总分析。上述方法可以满足短期内一定 程度的业务需求，但是，对于每天都有大量客票数据积累的铁路部门，实现具有 广泛智能特征的决策系统仅用常规的统计学方法显然是不合适的【2 ，3 】。需要寻找 一种合适的模型对客票数据建模。 决策树分类方法是一种数据分析形式，可用于提取描述重要数据类的模型或 预测未来的数据趋势【4 】。它能够产生易于理解和分析的规则，是目自口应用较为广 泛的分类方法。但是此方法应用于铁路客票营销分析构造的决策树比较庞大，从 中提取的规则也是一个庞大的规则集合。面对一个拥有许多规则的规则集合，决 策者要对其进行分析并从中挑出感兴趣的规则将是一件乏味的、困难的事情。所 以对规则集的合理组合和分析，提取更高层次的核心决策信息，是一个有待解决 的问题。 1 2 研究意义 基于i f n 提取的关联规则可以发现数据库中大量数据各项之间有趣的关联， 对于给定数据集，发现的输入和输出之间的联系可以很好的分析真实世界领域中 些具有商业价值的，潜在的信息，因此基于r f n 的方法已经在很多领域得到了很 好的应用，如时间序列数据库f 6 】、软件测试 5 】f 9 1 、医学 7 】、制造业f 8 】等方面。 而随着经济的发展，人口流动规模也越来越大。如何合理有效的组织客运， 保证铁路畅通、高效运转是一个值得关注的问题。全国铁路客票发售和预订系统 每闷产生的售票记录数以百万计，高峰期时可高达4 0 0 万条记录左右，分布存储 在各级服务器的数据库中，以一定周期传输、汇总、集中到铁道部，数据经过整 理压缩并长期保存o ，1 1 】。这些数据为目日口铁路有关决策部门提供了一定范围内 的超大规模数据库查询和相应的统计分析。而这些相对于铁路客票营销分析的目 的束讲，是远远不够的，因为这些传统的数据库技术所获得是一些平凡的知识， 2 基于i f n 的客票营销分析方法的研究 并不能发现隐藏于数据中的非平凡信息，要想获取非平凡的信息，按照传统的查 询和统计报表的做法只能依靠决策者的主观经验和判断来发现和归纳，这样做会 带有明显的人为因素，不容易全面、彻底的发现决策信息，故要实现具有广泛智 能特征的决策系统这种方法显然存在着其应用的局限性。因此，需要结合更为合 理的非平凡的信息提耿手段数据挖掘技术，利用其提供的良好、完整的客票 数据，寻找出蕴含于客票数据中的非平凡信息服务于决策。 数据挖掘的最终目标是从大量的数据中提取或“挖掘”出有用的知识，它适合 了铁路客运营销部门对客票数据分析的需求，在当日u 铁路客票分析中将有相当广 阔的应用前景。目前，在现有的诸多数据挖掘方法中，能够发现数据属性之间联 系的算法可以对客票数据进行建模与分析。其中，关联规则算法可以给出属性问 的关联规则集合，但是关联规则集合规模太庞大，要从中找到有意义的关联规则 却是一件非常困难的事情呲”】；分类算法虽然可以给出相对于关联规则算法来说 较少的规则数目，但是要考虑过度拟合的问题，而且从其应用于铁路客票营销分 析建立的模型中提取的规则集合对于决策者来说仍然比较庞大。因此对于客票数 据挖掘并没有一个具有实际意义的方法指导对客票数据的建模与分析。 l a s t ，m a i n m o n ，k a i l d d 提出i f n ( i n f o r i n a t i o n f i l z z v n e t w o r k ) 【1 4 】算法的突出优 点就是可以自动的减少数据的维数，提取较少的规则数目，而且可以产生决策者 感兴趣的关联规则，作为分类算法，它比其他著名的分类算法( 如决策树算法) 性 能要好的多。因此本文用基于i f n ( i n f o i m a t i o n f u z z y n e 时o r k ) 的方法对铁路客票 销售系统中的客票数据进行的分析与预测研究，帮助决策者建立有效的预测分析 模型，对铁路客票营销目前存在的问题及解决方法有一定的指导意义。 1 3 本文内容与结构 本文主要对基于i f n 的客票营销分析方法进行研究。首先研究了燎于现有 分类方法的问题和不足提出的i f n 算法，此算法的构造过程与决策树类似，但 是它是基于决策树算法的不足提出来的不同于决策树算法的一种新的网络模型 构造算法，所以本文主要把它与决策树算法相比较来研究，并且以铁路客票销售 系统中的客票数据为应用背景研究分析。 本文的组织结构如下： 基于i f n 的客票营销分析方法的研究 第一章绪论 介绍本文的研究背景与现状、研究意义以及具体的研究内容。 第二章相关知识 本章介绍了信息论与分类的相关概念，分类模型中用到的统计学显 著性，以及分类过程中的特征提取。 第三章基于i f n 的规则提取算法 本章主要伴随着决策树算法对i f n 算法进行了详细的描述，并对该 算法的结果进行评估。 第四章i f n 算法的应用研究 本章介绍了铁路客票营销分析特点，客票营销分析的需求及现状。 提出了针对客票数据展开的i f n 算法的应用性研究，通过浚算法对 客票数据进行建模分析，并与决策树算法在客票数据中的应用结果 进行对比分析。 第五章总结与未来的工作 对本文工作进行总结，并指出进一步的工作。 4 基于i f n 的客票营销分析方法的研究 第二章相关知识 数据的分类过程主要是针对减少目标( 分类) 属性的不确定性或增益信息的。 1 9 4 8 年s h a n n o n 用数学的方法度量研究信息【1 7 1 ，提出并发展了信息论，在他的 信息论中，信息被定义为消除或减少事物的不确定性，对于一个分类任务，更多 的信息就意味着分类模型有更高的精确性，有了这些信息就可以表明新样本的预 测类更有可能接近于其真正的类。只有能获取信息的分类模型才是有用的。 分类中的信息论方法学最初是为了查找一个使目标( 分类) 属性具有最大熵 压缩的输入属性的最小集合而提出的”，现在这个方法已经被应用在现实世界 中的时间序列数据库和数据管理等工作中。 本章以下内容主要介绍信息论的相关概念和数理统计上的相关假设检验。 2 1 信息论相关知识 2 1 1 熵 信息论中提出了用熵度量某个随机变量不确定性的方法【1 6 】。设是离散型 随机变量，概率密度p ( x ) = p r 心；算) ，石x ，且z p ( 曲，则离散性随机变量爿 的熵日( ) 定义如下： 定义1 离散型随机变量j 的熵日( j ) 是该随机变量的平均不确定程度： 日( x ) = 一p ( x ) l o gp ( z )( 2 - 1 ) r x 上式中对数l o g 所用的底是2 ，信息论中熵的单位用比特表示。例如：掷均匀 硬币这一事件的熵为l 比特。考虑到由于当x 呻。时，有x l o g x 斗0 ，则可约定 。崦o = o ，因此加上零概率之后不会改变熵的值。 事实上，熵是随机变量工概率分布的一个函数，与z 的实际耿值无关，只 依赖于其概率，并且当媾概率分布时，熵值最大。例如，抛硬币时，结果只有 两种情况，则熵可表示为：h ( 并) = 一p l o g p 一( 1 一p ) l o g ( 1 一p ) ，o p 1 。用普通 硬币做实验得到的各个抽样结果出现的概率都相同，但若硬币是不规则的，则实 5 基于i f n 的客票营销分析方法的研究 验结果会出现概率不相同的情况，并且结果的不确定性减少。根据概率分布的不 同，可以用下面的图示进一步理解熵h ( 并) 和概率分布p 之间的关系。 图2 1 熵趣抑与概率p 之间的关系曲线 从图中可以看到，当p 值趋近于o 5 时，熵最大，为1 ：而当p 值趋向于o 或1 时，熵总是在减小，且到达极端时，都为o ，即硬币总是正面向上或总是反 面向上。从中可知：熵越小，不确定性也越小。因此，在分类任务中，主要的目 标就是最小化目标属性的熵。 2 1 2 联合熵和条件熵 在熵的基础上，信息论中提出了度量两个随机变量之间条件依赖性的方法 【9 l ，即联合熵( j o i n tc n p y ) 月陇】，) ；条件熵( c o n d i d o n a le n 缸u p y ) ，叫y f 田，等等。 定义2 假设一对离散型随机变量( 置d 贴力，则其联合熵月瓯 ) 定义为 日( z ，y ) = 一p ( x ，y ) l o g p ( j ，y ) ( 2 - 2 ) j e x v e y 定义3 如果( x ，y ) p ( x ，y ) ，则条件熵日( y l 卫) 定义为 日( y f x ) = p ( x ) h ( y f x = x ) t e = 一p ( 曲p ( yl 力l o g p ( yi 曲 特xv e y = 一，( z ，y ) 1 0 9 p ( y l j ) ( 2 3 ) 舴xv e y 联合熵和条件熵的定义的这种自然性，可由一个事实得到体现，就是一对随 机变量的熵等于一个随机变量的熵加上另一个随机变量的条件熵。也即： 定理1 链式法则( c h a i nm l e ) 日( 工，y ) = 日( 爿) + h ( y l )( 2 4 ) 6 基于i f n 的客票营销分析方法的研究 2 1 3 互信息( 叫t l l a li n f o r m a t i 蛐) s h 糊o n 的信息论中，信息被定义为消除或减少事物的不确定性，而熵是随 机变量不确定性的度量，它也是在平均意义上描述随机变量所需的信息量增量。 这里我们将介绍一个相关概念：互信息。 定义4 互信息( 上；j ，) 是联合分布p ( x ，y ) 与乘积分布p ( z ) p ( y ) 之间的相对熵， 即： 鹏耻互量比力b s 篙罴 x x v y = d ( p ( 五y ) ) i ip ( 曲p ( y )( 2 5 ) 由定义4 可知：互信息，( 置功o ；等于o 时，当且仅当p ( y ) = p ( x ) p ( ，) ，也 即是j 与y 相互独立。互信息可以用于衡量两个随机变量的依赖程度( 或者独立 性) ，当两个随机变量独立时，它们的互信息刚好为0 ，互信息的取值越火，表明 两个随机变量的依赖程度越高。 2 1 4 熵和互信息的关系 熵，是计算互信息的基础。重写互信息“x ；r ) 的定义可得 删；y ) 2 蚤三如加g 篇 疆xy e yd i 工i 口fv 1 = 磊吾p ( 圳1 0 9 搿 r xy 酣 口f 石l = 一三吾p k y ) 1 0 9 p ( z ) + 三舌p ( x ，y ) 1 。g p ( x i _ y ) = 一乏p ( 曲1 0 9 p ( x ) 一( 一乏p ( 工，y ) l o g p ( 艽i y ) ) j e t e v y = 日( j ) 一日( 工iy ) ( 2 6 ) 由此表明互信息h 置j ，) 就是在给定y 缶识条件下肭不确定度的减少量。 由对称性，j ( _ ；y ) = 日( y ) 一日( y i x ) ( 2 7 ) 因而胎有y 的信息量等同于y 含有肭信息量。 由于坝置幻= 饿司+ 川yj ，则有：瞄；r ) = 日( 鼻) + 爿( y ) 一( j ，y ) ( 2 8 ) 基于i f n 的客票营销分析方法的研究 2 1 5 熵和互信息的链式法则 设有一组随机变量的概率密度为p “，恐，毛) ，则熵的链式法则如下 和： 为 定理2 设墨，五，以p ( 一，) ，则这组随机变量的熵等于条件熵之 何( 五，五，以) = 日( 置+ 五) ( 2 9 ) i = l 定义6 随机变量卫和y 在随机变量z 已知的条件下的条件互信息( x ；l ，iz ) ( 肖；y i z ) = 日( x i z ) 一日( z i 】，z ) 。，k g 裔糍南 = 萎丢萎舭旧地焉器 协 j e jr y = e z p nl 厶，、1l o ， 定理3 随机变量珀q 熵的减少量等于一组随机变量蜀，恐，与y 之间的条 件互信息之和( 互信息的链式法则) ： ( 五，五，；y ) = ，( 置；y i 一一五) ( 2 - 1 1 ) 根据熵的衡量标准，它依赖于一个随机变量的概率分布而不是变量的取 值。因此，在分类工作中，类标号的度量不是重要的，最小化目标( 分类) 属性的 熵才是选择最好属性的一个标准。像i d 3 和c 4 5 算法中用信息增益来查找分裂决 策树结点的最好特征就是这样一个例子，即信息增益最大的输入属性作为决策树 结点的测试属性。本文研究的i f n 算法用互信息作为属性度量的标准，来选择候 选输入属性和目标属性之间互信息最大的候选属性作为测试属性也是同样的道 理，即目标属性熵的减少量等于它和所有候选输入属性之间的互信息。 2 2 统计学假设检验 1 8 】中提到，许多分类算法构造的模型都过于复杂，其扩展性不是很好，向 且会产生过分拟和的现象。过分拟合问题是常见的问题，产生数据过分拟合的原 基于i f n 的客票营销分析方法的研究 因有：第一，事物本身的属性太多，一些学习算法会选用到和分类不相关的属性； 第二。每个属性选择的算法在选取测试属性时，都有自己的倾向性，所以经常会 选择到算法所倾向的，但不是真正和分类相关的属性。所以，要避免选择不相关 的属性。在统计学假设检验中，模型复杂性的增加( 例如分裂决策树的结点时) 和 一个给定样本过分拟台之间的矛盾是众所周知的【2 4 1 。空假设检验凰它通常没有 假设检验h l 复杂) 只有在给定的显著水平充分说明了训练样本非常稀少时才被拒 绝，否则基于这个假设下凰是正确的。这意味着显著水平代表了一个研究者在 做一个拒绝岛的决定时的危险性。 定义7 设五，五，也是相互独立的且皆服从标准正态分布( o l2 ) 的随机 变量，则称随机变量 z 2 = 并卜+ 霹( 2 1 2 ) 为自由度为n 的z 2 变量，其分布成为自由度为n 的z 2 分布。其中参数h 称为自 由度，它表示独立变量的个数。将自由度为n 的z 2 变量或其分布简记为z 2 ( ) 。 在决策树方法中，l d 3 算法已经把已经z 2 分布应用到评估测试属性之恤j 无 关性的空假设检验中，在构造树时，i d 3 把开方分布、信息增益等度量用于评估 分裂的优良性，如果在一个结点划分样本时导致低于预定义闷值的分裂，则给定 子集的进一步划分将停止【4 l 。然而，选取一个适当的阈值是困难的，较高的阈值 可能导致过分简化的树，而较低的闽值可能使得树的简化太少。决策树学习的其 他方法，像c a r t ，c 4 5 算法等为了处理较大的模式集合都采用后剪枝方法( 即 先产生一个完全生长的树，然后再剪枝) 。但是，后剪枝方法可能会带束后剪枝 复杂性和错误剪枝等问题 2 7 】。而基于m d l 的p u b l i c 算法保留后剪枝的特点， 但是不根据期望错误率对树进行剪枝，最佳剪枝树使得编码所需的一进位最小， 这种方法采用最小描述长度( m d l ) 原则。这一原则遵循o c c 哪sr a z o r 的理念： 最简单的解释是最佳的 j 6 。 1 9 2 8 年奈曼一皮尔逊( n e y m a n p e a r s o n ) 提出了一种利用似然比获得统计量的 一般方法，它是寻求新统计量的个重要方法，他们利用似然比建立了个构造 检验的一般方法，叫做似然比检验。此检验法在假设检验中的地位，相当于极大 似然估计在点估计中的地位，由它造出的检验常具有种种最有性质。 9 基于i f n 的客票营销分析方法的研究 定义8 设总体工的密度函数( 或概率函数) 为，( x ，d ，其中p h 。则样本 的联合密度函数为，( t ，d ，如果把它看成护的函数，则似然函数： 工( p ：玉，) = n 厂( ，口) i ；l 定义9 称函数 s u p ( p ；x l ，一，) 倒”) = 盖丽i 丽 为关于检验问题的域：口的似然比。 ( 2 - 1 3 ) ( 2 1 4 ) 定义l o 给定检验水平口，可以找到一个与口无关的常数c ，o t h 的两个子集s l 和s 2 ； 2 ) 对于每个子区间，在当前网络层的每一个结点z 处，求以t h 为阈值的属 性a i 和目标属性t 之间的条件互信息 打以及似然比检验g 2 ：并用似然比评估 给定结点z 处属性a i 和目标属性t 之问条件互信息是否显著，并用阈值1 1 l 标记； 3 ) 找到使属性a i 和目标属性t 之间条件互信息最大的并且统计上显著的闽 值t h ，并返回它所对应的条件互信息； 4 ) 确定闽值的过程递归地用于所得到的每个划分子区间，直到返回的最大 条件互信息为o ； 由上述方法，可计算其他候选输入属性和目标属性a t 之间的条件互信息和 似然比，直到所有输入属性和目标属性之间的条件互信息在统计上不再显著，网 络构造就停止。 ( 3 ) 提取规则时，要计算终结点和目标结点之间的权值，如果权值是正的表 示此目标属性值发生的条件概率高于它的非条件概率，反之亦然。计算权值的公 式如下； 蜓硼z ) l 。g 锗 ( 3 _ 6 ) 一i ， 其中：p ( ：) ，p ( k z ) 是结点z 处目标属性值k 发生的联合概率和条件概 率： p ( k ) 是结点z 处目标属性值e 发生的无条件概率； 根据i f n 算法的基本原理，我们给出i f n 算法的伪代码，其描述如图3 2 所 基于i f n 的客票营销分析方法的研究 算法1 ：g e r 赋a t e - i f n由给定的训练数据产生一个i f n 模型 输入：n 个训练样本( 记录) ，候选输入属性集合e i ，目标属性a t ，判定结点 分裂的最小显著水平s i g n _ 0 1 。 输出：选择的输入属性集合i ，i f n 模型 方法： 1 建立代表训练样本的根结点n o d e o 和代表目标属性的目标层，初始化： i _ 庐，网络层数目l = 0 ，候选输入属性个数为m ； 2 w h i l el q nd o 2 1f o r 每一个网络层结点z 2 1 1 f o r ( i = l ；4 c ia n d4 仨i ；i + + ) d o i f4 是离散的 m e nr e “l n l 输入属性4 和目标属性a 。之间的条件互信息 心( 4 ，t z ) 和评估互信息的似然比g 2 ( 4 ；r z ) ； d s er e t 哪输入属性4 的最好分裂闽值n 和输入属性4 与目标属性a t 之问 的条件互信息 打( 4 ，1 1 ，z ) ； 2 2 找到j j l 打最大并且统计上显著的属性彳； 2 3 i f ( ”= o ) o r ( 没有分裂结点) t l l e ne n d d o e 1 s e 用aj 标记一个新的网络层，l = l + 1 ；p i u ) 3 f 咖m 输入属性集合i 和i f n 模型结构。 上述算法描述中，第2 步中输入属性的选择是关键的一步，首先根据似然 比判断当前层所有结点z 处候选输入属性a i 和目标属性a t 之间的条件互信息是 否在统计上显著，如果显著，则标记该属性a i 分裂结点z ，然后再从分裂结点z 1 4 基于i f n 的客票营销分析方法的研究 的候选输入属性中选择条件互信息最大的属性a 作为下一层的输入属性，根据 属性a 的每个己知的值，对每个分裂结点创建分支并生成下一个网络层的结点， 每个结点z 代表一个样本子集。如果属性a i 不分裂结点z ，则标记z 为终结点， 并计算其与目标层结点连接的权值。每建一个新的网络层时，都递归调用算法重 新计算所有未选的属性的条件互信息， 选择一个提供最大条件互信息并且在统 计上显著的候选输入属性作为下一层的所有结点的输入属性，一个新的网络层的 结点个数是当前层的分裂结点的个数和新的输入属性值个数之间的笛卡尔积。根 据链式f c h i nm l e ) 规则，输入属性和目标属性集合之间的互信息等于所有网络层 结点条件熵减少的总和。 3 2 l f n 模型 由i f n 算法可构造出一个数据分析模型，称为i f n 模型。该模型是个类 似于神经网络的网络结构。这个网络结构的本质f 每一个终结点都直接连接到各 个目标结点) 类似于多层神经网络的拓扑结构【l8 1 ，有输入结点、输出结点和若干 个网络层，因此，这个模型称为一个网络而不是一棵树；但是，i f n 模型又是不 同于神经网络的，因为i f n 模型中定义信息论权值只是为了终结点连接到目标 层，面内部结点的连接只和输入属性值或区间有关，和权值无关，个神经网络 的权值却是和每一个内部连接都是相关的。 i f n 模型的组成部分： f 1 ) i 一网络层数目。每一个网络层唯一对应一个输入属性，第o 层仅仅包括 根节点，它与所有输入属性都无关。从i f n 模型中提取的所有规则中条件的数 目不能大于网络层的数目。 ( 2 ) l 一网络层l 上结点的集合。每一个结点代表一个与输入属性值相关的记 录集合，它类似于标准决策树中一个内部结点的定义。非终结点的每一个分支边 缘对应于离散属性的值。 ( 3 ) k 一目标层结点c t 。每个目标层结点代表一个目标属性的值。 ( 4 ) w z t 一终结点z 和目标结点c t 的连接权值。每一对终结点目标结点 之间的连接表示输入属性和目标属性之间的关联规则，规则权值的计算是基于信 息理论的。 基于i f n 的客票营销分析方法的研究 基于n 的算法首先定义目标层和与所有输入属性无关的根结点n o d eo ( 第 o 层) ，i f n 模型的初始结构如图4 1 所示。 层n o 0关系权值目标层 图3 1i f n 模型的初始结构 i f n 算法构造网络模型的过程是自上而下一个方向完成的，构造完成之后， 没有对网络分支自下向上的后剪枝处理。 i f n 算法遵循下面三个指导原则： ( 1 ) 使输入属性和目标属性之间的豆信息最大： ( 2 ) 查找包含在网络结构中的最小输入属性集合； ( 3 ) 用似然比验证互信息的统计学显著水平。 i f n 模型构造停止的标准利用了标准统计学上的似然比检验，当输入属性和 目标属性之间的条件互信息不显著增加，目标属性条件熵不显著减少时，网络构 造停止。 3 3 模型规则的提取 i f n 模型构造以后，可以从中得到关联规则，提取网络模型表示的知识4 3 1 ， 并以i f 条件t h e n 目标和i f 条件t l l e l ln o t 目标的规则形式表示。i f n 模型中每 一个终结点代表一个与输入属性某个值相关的样本子集，因此，每个终结点和目 标结点之间的连接可以用i f 条件t h e l l 目标和i f 条件廿l e n n o t 目标的形式表示， 而信息论权值与是每一对输入属性目标属性之间的连接相关的。 每一个连接权值代表一个分布即输入属性和目标属性之间互信息的总合，如 果在给定结点处目标属性值的条件概率高于非条件概率，则权值为正，反之胡i 然； 如果权值为o 则表示目标属性值和终结点值是相互独立的。因此，每一个正值可 以用阐述的规则是i f 条件t h e n 目标，每一负值可以阐述的规则是i f 条件t h e n n o t 目标，权值为o 连接可被忽略。 这里我们给出从i f n 模型中提取规则的一般算法描述： 1 6 基于i f n 的客票营销分析方j 去的研究 算法2 ：由i f n 模型提取关联规则 输入：n 模型，网络数目l ，目标属性a t 输出：规则集r 方法： 1 初始化：r = ； 2 f o