（系统理论专业论文）关联规则算法研究及其在铁路隧道安全管理中的应用.pdf

中文摘要 摘要；数据挖掘技术是伴随信息量的迅速增长而诞生的，如何满足人们对知 识与信息的渴求，以便快速地获取知识以及应用于决策领域，已经成为当前信息 处理中的热门课题之一。 数据挖掘的方法很多，其中关联规则挖掘是一种主要的也是用途最广的数据 挖掘方法，关联规则概念最早是由在i b m 工作的r a k e s hh g r a w a l 博士等于1 9 9 3 年提出的，用于刻画事务数据库中各交易项目之间的关系，即频繁关系，白此，对 关联规则的研究已有l o 余年时问并取得了很多成果，但还有很多问题亟待解决 本论文对此作了详细介绍，并对关联规则挖掘理论特别是关联规则挖掘算法进行 了深入研究，取得了一定的研究成果。 文章首先介绍了数据挖掘的内涵、过程和一些方法，并简介了国内外目前的 研究现状。关联规则方法是被实践( 沃尔玛) 证明了的一种非常有用的数据挖掘 方法。关联规则的主要任务就是获得频繁项集，获得频繁项集的经典算法是 a p r i o r i 算法和f p g r o w t h 算法，从算法的数据结构看这两种算法分别是基于数组 和基于树的；文章还介绍并分析了a p r i o r i 算法的几种改进算法a p r i o r i t i d 和 a p r i o r i h a s h 等，同时还介绍并分析了f p - g r o w t h 算法的改进算法p f p - g r o w t h 。 在总结了这些算法的特性后，作者提出了基于数组的a p r i o r i n 算法，此算法通过 编码的方式把对数据库的操作转化到对内存的操作上，虽然此算法对处理机的内 存要求较高，但大大提高了算法的效率；同时还提出了基于f p - t r e e 的高性能关 联规则挖掘算法f p g r o w t h n 算法，可以通过增加一个额外的数据结构加快项集的 遍历速度，在第二遍扫描数据库时，建立基本f p - t r e e ( t ) 的同时生成一个矩阵 4 ，这个矩阵用来保存频繁2 一项集。 我国的铁路隧道多数存在病害，以往大量历史病害数据没能为治理和防治工 作提供有效的决策支持，而数据挖掘的关联规则方法可以通过挖掘历史数据为隧 道病害防治和治理提供有效指导。由于作者提出的新算法f p - g r o w t h n 特别适合那 些数据量很大但数据项很稀疏的数据挖掘，文章将这种新算法应用于挖掘铁路隧 道各病害的关联，通过对成都铁路局掌握的2 0 0 5 年的2 7 8 7 条隧道病害数据的3 4 3 条重点隧道有效病害数据的关联分析，找出了各隧道病害之间隐藏着的关系，对 铁路部门制定检测标准和防治隧道病害有一定的指导作用。文章最后通过结合关 联规则挖掘方法介绍了一个隧道安全管理的决策支持项目，指出了数据挖掘方法 在此项目中的意义。 本文最后对研究工作进行了总结，提出了今后进一步的研究思路。 关键词：数据挖掘；关联规则；频繁项集；f p - t r e e ；隧道病害 分类号$ t p 3 1 1 a b s t r a c t a b s t r a c t ：t h ed a t am i n i n gt e c h n i q u ew a sb o ma c c o m p a n i e db yt h ee x p l o s i v e g r o w t hf o r t h ea m o u n to fi n f o r m a t i o mh o wt om e e tt h en e 。d so f p e o p l ew h oa r ee a g e r f o rk n o w l e d g ea n di n f o r m a t i o ni no r d e rt h a tt h e yc a na c q u i r ek n o w l e d g eq u i c k l ya n d a p p l yi t t ot h ed e c i s i o nm a k i n gf i e l d , h a sb c o m eo n eo ft h eh o tt o p i c si nc u r r e n t i n f o r m a t i o np r o c e s s i n g t h e r ea r cm a n ym e t h o d sf o rd a t am i n i n g , o f w h i c ht h ea s s o c i a t i o nr u l em i n i n gi sa d a t am i n i n gm e t h o dt h a ti si nt h e l e a da n dw i t ht h ew i d e s tu s a g e t h ec o n c e p to f a s s o c i a t i o nr u l ew a sf i r s tp r e s e n t e di n1 9 9 3b yd r r a k e s ha g r a w a lw h oh e l dap o s t i o n i nm ma n do t h e r si no r d e rt ob eu s e df o rd e p i c t i n gt h er e l a t i o n s h i p sa m o n gt h e t r a n s a c t i o ni t e m si nt r a n s a c t i o nd a t a b a s e , i e t h ef r e q u e n tr e l a t i o n s h i p s t h er e s e a r c ho h i th a sl a s t e dm o r et h a n1 0y e a r st i l ln o wa n dh a sm a d e g r e a ta c h i e v e m e n t s b u tt h e r ea g e s t i l lm a n yp r o b l e m si nu r g e n tn e e do fb e i n gs o l v e d t h i sa r t i c l ei n t r o d u c e st h e s ei n d e t a i l s ，a n dg o e si n t ot h ea s s o c i a t i o nn i l em i n i n gt h e o r y , e s p e c i a l l yt h ea s s o c i a t i o nr u l e m i n i n ga l g o r i t h m , w i mc e r t a i na c h i e v e m e n t sm a d e t h ea r t i c l ea tf i r s ti n t r o d u c e st h em e a n i n g , p r o c e s sa n ds o m em e t h o d sf o rd a t a m i n i n g , a n dt h e ni n t r o d u c e si nb r i e ft h ep r e s e n tr e s e a r c hs i t u a t i o na th o m ea n da b r o a d t h ea s s o c i a t i o nr u l em e t h o di sad a t am i n i n gm e t h o dt h a ti sp r o v e dv e r yu s e f u li n p r a c t i c e ( i nw a l - m a r t ) t h em a i nt a s ko ft h ea s s o c i a t i o nr u l ei st oo b t a i nf r e q u e n t i t e m s e t s ，t h ec l a s s i c a la l g o r i t h m sf o rw h i c ha r ea p r i o r ia l g o r i t h ma n df p g r o w t h a l g o r i t h m f r o mt h ep o i n to fv i e wo ft h ed a t as i 矾“由1 f o ra l g o r i t h m t h e s et w o a l g o r i t h m sa g eb a s e do na r r a y sa n dt r e e sr e s p e c t i v e l y t h ea r t i c l ea l s oi n t r o d u c e sa n d a n a l y z e ss e v e r a li m p r o v e da l g o r i t h m ss u c ha sa p r i o r i t i da n da p r i o r i h a s h , a n da n i m p r o v e da l g o r i t h mo ff p g r o w t ha l g o r i t h m p f p g r o w t ha sw e l l a f t e rs u m m a r i z i n g t h ec h a r a c t e r i s t i c so f t h e s ea l g o r i t h m s ，t h ea u t h o rp r e s e n t sa p r i o r i na l g o r i t h mb a s e do n a r r a y s t h i sa l g o r i t h mc o n v e r t st h eo p e r a t i o no nd a t a b a s ei n t ot h eo p e r a t i o no nm e m o r y v i ac o d i n g , e n h a n c i n gt h ee f f i c i e n c yo ft h ea l g o r i t h ms i g n i f i c a n t l y b u ti th a sh i g h e r d e m a n d so f t h ep r o c e s s o r a tt h es a m et i m e ，t h ea u t h o ra l s op r e s e n t sa h i g hp e r f o r m a n c e a s s o c i a t i o nr u l em i n i n ga l g o r i t h mb a s e do nf p - t r e c - f p g r o w t ha l g o r i t h m , w h i c h q m c k e n st h et r a v e r s es p e e do fi t e m s e t st h r o u g ha d d i n ga ne x t r ad a t as t r u c t u r e d u r i n g t h es e c o n d - t i m es c a no ft h ed a t a b a s e , am a t r i x4t h a tc a nb eu s e df o rs a v i n g 2 - f i e q u e n ti t e m s e t si sg e n e r a t e dw h i l et h eb a s i cf p t r ot , ) i sc r e a t e d t h e r ea r ed a m a g ei nm o s to ft h er a i l w a yt u n n e l si no u rc o u n t r y i nt h ep a s t ，t h e g r e a tb u l ko f h i s t o r i c a ld a m a g ed a t af a i l e dt op r o v i d ee f f e c t i v ed e c i s i o nm a k i n g $ u p p o r t f o rt h ew o r ko fg o v e r n i n ga n dc o n t r o l l i n g h o w e v e r , t h ea s s o c i a t i o nr u l em e t h o df o r d a t am i n i n gc a l lp r o v i d ee f f e c t i v ei n s t r u c t i o nf o rt h ec o n t r o l l i n ga n dg o v e r n i n go ft h e t u n n e ld i s e a s e st h r o u g hm i n i n gh i s t o r i c a ld a t a s i n c ef p - g r o w t h n , t h en e wa l g o r i t h m p r e s e n t e db y t h ea u t h o rf o rr e a $ o n sg i v e na b o v e , i se s p e c i a l l ys u i t a b l ef o rm i n i n gt h e d a t at h a th a v el a r g ed a t av o l u m eb u tv e r ys p a r s ed a t ai t e m s t h ea r t i c l ea p p l i e st h i sn 钾 a l g o r i t h mt om i n i n gt h ea s s o c i a t i o no ft h ed a m a g ef o rr a i l w a yt u n n e l s t h eh i d d e n r e l a t i o n sa m o n gt h et u n n e ld a m a g ea r ed i s c o v e r e dt h r o u g ht h ea s s o c i a t i o na n a l y s i so f 3 4 3p i e c ：0 8o fe f f e c t i v ed i s e a s ed a t af o rm a j o rt u n n e l si nt h e2 7 8 7p i e c e so ft u n n e l d a m a g ed a t ao f y e a r2 0 0 5 w h i c ha r en 】l e do v e rb yt h ec h e n g d ar a i l w a yb u r e a u t h e y c a np r o v i d ec e r t a i ni n s t r u c t i o n sf o rr a i l w a yd e p a r t m e n t st oc o n s t i t u t et h ed e t e c t i o n c r i t e r i o na n dc o n t r o lt h et u n n e ld a m a g e t h ea r t i c l ei n c o r p o r a t e st h ea s s o c i a t i o nr u l e m i n i n gm e t h o da n di n t r o d u c e sad e c i s i o nm a k i n gs u p p o r tp r o j e c to ft u n n e ls a f e t y m a n a g e m e n ti nt h ee n d , p o i n t i n go u tt h em e a n i n go fd a t am i n i n gm e t h o d si nt h i s p r o j e c t f i n a l l y , t h i sa r t i c l e8 u m n l a r i z e st h er e s e a r c hw o r k ，a n dp r e s e n t st h ef u r t h e rr e s e a r c h d i r e c t i o nf o rt h ef u t u r e k e y w o r d s ：d a t am i n i n ga s s o c i a t i o nr u l e s ；f r e q u e n ti t e m s e t s ；f p - t r e e ；t u n n e l d a m a g e c l a s s n o ：什3 1 1 致谢 本论文的工作是在我的导师徐维祥教授的悉心指导下完成的，徐维祥教授严 谨的治学态度和科学的工作方法给了我极大的帮助和影响，其广博的知识拓宽了 作者的思路。作者衷心感谢徐维祥老师在我研究生期间给予的悉心指导和宝贵建 议。 同时还要感谢钟雁教授，他有渊博的知识和敏锐的观察力。在他的指导下， 我的论文最终在算法改进上和实际应用方面得到了比较大的提高。 在实验室工作及撰写论文期间，李晓争、符国庆等同学对我论文中的资料收 集工作给予了热情帮助，在此向他们表达我的感激之情。 另外也感谢家人郭英，她的理解和支持使我能够在学校专心完成我的学业。 1绪论 1 1 论文研究的目的和意义 2 1 世纪信息爆炸，随着数据库技术和数据库管理系统的广泛应用，全球范围 内数据库中存储的数据量急剧增大，有些面向科学研究的数据库中的数据也非常 惊人但是，传统的数据库应用仅限于简单的查询、统计及报表的打印，数据库 中隐藏着的丰富知识远远没有得到充分的挖掘和应用。以指数级速度增长的数据 库与人们从中获取的知识形成强烈的反差，势必造成信息腐烂，导致大量的数据 垃圾，人们迫切需要利用一种崭新的技术和工具智能地、自动地将数据转变为知 识，这种情况下数据挖掘术应运而生。人们迫切地想从信息中找到知识，数据挖 掘就提供了很多有效的方法；挖掘关联规则是数据挖掘中一个重要组成部分，关 联规则是单向的，它是指某类项目或特征与另一类项目或特征间所存在的单向影 响关系。 r h g r a w a l 等于1 9 9 3 年首先提出了挖掘顾客交易数据库中项集间的关联规则 问题，以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究，包括对原 有的算法进行优化，如引入随机采样、并行的思想等，以提高算法挖掘规则的效 率。最传统的关联规则算法是h p r i o r i 算法i l l ，但是由于其致命的两大缺点：( 1 ) 频繁扫描数据库浪费i o 时间；( 2 ) 识别频繁项目集时，算法采用模式匹配，效 率较低。因为现实中的数据往往是海量的，所以必须要找出一些更快、占用资源 更少的算法，这些算法可以运用在金融、保险、网站日志分析以及铁路隧道海量 监测数据的关联规则挖掘中。 我国自1 8 8 8 年开始建造第一座铁路隧道以来，迄今已有1 1 0 余年的修建历史。 根据国家发展与改革委员会2 0 0 4 年的统计，我国铁路运营隧道己达7 4 0 0 余座， 总长达4 2 0 0k m ，但大量隧道存在病害。铁路部门2 0 0 5 年秋检资料统计显示，以 成都局所管辖的隧道为例，6 7 5 存在着不同程度的病害，这些病害有的已经危及 到了行车安全，有的尚未危及但是有向恶性发展的趋势。铁路部门每年都要对隧 道安全指标数据进行检测，已经积累了大量的数据，但这些数据基本上都被闲置， 没有为病害的预测和防治起到有效作用，一些传统的管理系统只是对这些采集到 的数据作一些简单的查询及统计工作，而并没有挖掘出这些数据中潜藏的病害规 律。铁路部门每年都投入大量的人力、物力和资金用于隧道病害的维修和整治，但 隧道的状况仍然没有根本好转。 因此，需要通过系统的分析，总结铁路隧道的病害特点 2 1 ，及通过大量隧道缺 陷数据来找到这些存在于铁路隧道中的病害数据之间隐藏着的一些微妙的关系， 为铁路隧道的日常维护、病害检测、病害整治提供强有力的决策支持。数据挖掘 的关联规则方法就是帮助我们达到这个目的的有力工具。 1 2 数据挖掘的内涵、过程和方法 1 2 1 数据挖掘的内涵 所谓数据挖掘( d a t am i n i n g ) ，就是从大量的、不完全的、有噪声的、模糊的、 随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有 用的信息和知识的过程。这个定义包括好几层含义；数据源必须是真实的、大量 的、含噪声的；发现的是用户感兴趣的知识；发现的知识要可接受、可理解、可 运用；并不要求发现放之四海皆准的知识，仅支持特定的发现问题。 什么是知识? 从广义上理解，概念、规则、模式、规律和约束等都是知识， 而数据可以看作是形成知识的源泉。数据可以是结构化的，如关系数据库中的数 据，也可以是半结构化的，如文本、图形和图像数据。发现知识的方法可以是数 学的，也可以是非数学的；可以是演绎的，也可以是归纳的。发现的知识可以被 用于信息管理，查询优化，决策支持和过程控制等，还可以用于数据自身的维护。 因此，数据挖掘是- n 交叉学科，它把人们对数据的应用从低层次的简单查询， 提升到从数据中挖掘知识，提供决策。 与传统分析方法( 如查询、联机应用分析) 相比，数据挖掘是在没有明确假 设的前提下挖掘信息、发现知识。数据挖掘所得到的信息应具有事先未知、有效 和可实用三个特征【1 | 。数据挖掘是要发现那些不能靠直觉发现的信息或知识，甚至 是违背直觉的信息或知识，挖掘出的信息越是出乎意料，就可能越有价值。 在商业应用中，数据挖掘是一种新的信息处理技术，其主要特点是对商业数 据库中的大量业务数据进行抽取、转换、分析和模型化处理，从中提取辅助商业 2 决策的关键性数据。因此，数据挖掘可以描述为：按企业既定业务目标，对大量 的企业数据进行探索和分析，揭示隐藏的、未知的或验证已知的规律性，并进一 步模型化的先进有效的方法。 图1 数据挖掘与其他学科之间的关系 c h a r t1 t h er e l a t i o n s h i pb f = t v v e e nd a t am i n i n ga n do t h e rd i s c i p l i n e s 1 2 2 数据挖掘的过程 数据挖掘的过程包括如下步骤： ( 1 ) 数据定义和理解：通过使用或创建元数据，定义了解相关领域的有关情况， 熟悉背景知识，弄清用户要求，这是创建数据仓库和数据质量改进程序的第一个 步骤。 ( 2 ) 数据质量的改进：即执行任何必需的数据清理工作。 ( 3 ) 数据准备：数据准备是数据挖掘的重要组成部分，对前一段产生的数据进 行再加工，检查数据的完整性及一致性，其中主要是对噪音数据进行处理，对丢 失的数据进行填补。 ( 4 ) 数据挖掘模型开发：选择知识发现的方法，确定模型。 ( 5 ) 数据挖掘：运用确定的数据挖掘模型，从数据中提取出用户所需要的知识， 3 这些知识可以用一种特定的方式表示或使用一些常用的表示方式。 ( 6 ) 知识评估：包含解释、外攉及模型调整。将发现的知识以用户能理解的方 式表示，根据需要对知识发现过程中的某些处理阶段进行优化，直至满足要求。 1 2 3 数据挖掘的方法 图2k d d 过程 c h a r t 2t h ep r o c e s so f f m d 我们面对的是大量的隐藏在数据内部的有用信息。如何获取信息是我们所要 解决的问题，数据挖掘从一个新的角度把数据库技术、机器学习、统计学等领域 结合起来，从更深层次发掘存在于数据内部新颖、有效、具有潜在效用的乃至最 终可理解的模式。具体讲，数据挖掘技术有以下几种方法。 ( 1 ) 数学统计方法：使用这种方法一般是首先建立一个数学模型或统计模型， 然后根据这种模型提取出有关的知识。如：可由聚类的学习方法从数据中提取出 有关的知识。因为机器学习经过多年的研究，已取得了一些较为满意的成果，因 此，在k d d 中，可以利用目前比较成熟的机器学习方法。 ( 2 ) 面向数据库的方法：随着数据库技术的发展，其中的一些数据处理方法 不断完善并趋于成熟，在k d d 中，利用现有的数据库技术和某些专门针对于数 据库的一些启发方法，可以提取出数据库中的一些特征知识。 ( 3 ) 混合方法：上述各种方法各有其优缺点，为提高k d d 的效率，可将各 种方法有效地结合起来，取长补短，以发现更有价值的知识。如机器学习中的推 4 导方法可以和演绎数据结合起来。前者用于知识的推导，后者可以验证发现知识 的正确性 还有其它方法，如数据可视化技术、知识表示等等。在实际操作中具体有以 下几种主要的数据挖掘方法： ( 1 ) 关联规则 关联规则挖掘( a s s o c i a t i o nr u l em i n i n g ) 是数据挖掘的一个重要分支，关联 规则是数据挖掘的众多知识类型中最为典型的一种。该问题于1 9 9 3 年由a g r a w a l 等人在对市场购物篮问题( m a r k e t b a s k e t a n a l y s i s ) 进行分析肘首次提出的，用以 发现商品销售中顾客的购买形式。关联规则就是发现存在于大数据集中的关联性， 若两个或多个数据项的取值之间重复出现且频率很高时，它们就存在某种关联， 可以建立起这些数据项的关联规则。关联规则的例子有：“9 0 0 , 4 的顾客在购买面包 的同时也会购买牛奶”、“9 8 的购买轮胎和汽车配件的顾客也购买汽车保养服务” 及“在购买铁锤时，有7 0 的人同时购买了铁钉”等，直观的意义是顾客在购买 某些商品时，有多大的倾向会购买另外一些商品。 在大型数据库中，这种关联规则是很多的，需要进行筛选，一般用“支持度” 和“可信度”两个阈值来淘汰那些无用的关联规则。“支持度”表示该规则所代表 的事例( 元组) 占全部事例( 元组) 的百分比。如买面包又买牛奶的顾客占全部 顾客的百分比。“可信度”表示该规则所代表事例占满足前提条件事例的百分比。 如买面包又买牛奶的顾客占买面包顾客中的9 0 ，可信度为9 0 。 ( 2 ) 决策树方法 利用信息论中的互信息( 信息增益) 寻找数据库中具有最大信息量的字段， 建立决策树的一个结点，再根据字段的不同取值建立树的分枝；在每个分枝的子 集中，重复建立树的下层结点和分枝的过程，即可建立决策树。国际上最有影响 的和最早的决策树方法是j r q u i n l a n 提出的i d 3 方法，在i d 3 基础上后人又发展 了各种决策树方法。 ( 3 ) 神经网络方法 模拟人脑神经元方法，以m p 模型和h e b b 学习规则为基础，建立了三类多 种神经网络模型：前馈式网络、反馈式网络、自组织网络，它是一种通过训练来 学习的非线性预测模型，可以完成分类、聚类、特征挖掘等多种数据挖掘任务。 5 ( 4 ) 粗糙集方法 粗糙集理论的特点是不需要预先给定某些特征或属性的数量描述，如统计学 中的概率分布，模糊集理论中的隶属度或隶属函数等，而是直接从给定问题出发， 通过不可分辨关系和不可分辨类确定问题的近似域，从而找出该问题中的内在规 律。粗糙集理论同模糊集、神经网络、证据理论等其它理论一起成为不确定性计 算的一个重要分支。粗糙集理论与模糊数学既有关系又有区别，但粗糙集的理论 源于模糊数学 数据挖掘算法是针对上述挖掘方法的具体体现，任何数据开采算法都包含三 个主要成份：模型表示、模型评价和搜索。 1 3 国内外研究现状 1 3 1 数据挖掘技术的研究现状 数据挖掘技术( d a t am i n i n g , d m ) 是9 0 年代兴起的一项决策支持的新技术，许 多人把数据挖掘视为另一个常用的术语数据库中的知识发现或k d d 的同义词。而 另一些人只是把数据挖掘视为数据库中知识发现过程的一个基本步骤；在本文中 提到的数据挖掘都是指整个知识发现过程。 目前，数据挖掘技术及知识发现己成为计算机科学界的一大研究热点。美国 人工智能协会主办的k d d 国际研讨会及数据库、人工智能、信息处理、知识工程 等领域的国际学术刊物都开辟了知识发现专刊，i e e e 的k n o w l e d g ea n dd a t a e n g i n e e r i n g 会刊领先在1 9 9 3 年出版了k d d 技术专刊，所发表的5 篇论文代表了 当时k d d 研究的最新成果和动态，较全面地论述了k d d 系统方法论、发现结果 的评价、k d d 系统设计的逻辑方法，集中讨论了数据库的动态性冗余、高噪声和 不确定性、空值等问题，k d d 系统与其它传统的机器学习、专家系统、人工神经 网络、数理统计分析系统的联系和区别，以及相应的基本对策，展示了k d d 在从 建立分子模型到设计制造业的具体应用。 不仅如此，在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 最为权威，另一份在线周刊为d s ( d s 代表决策支持) ，1 9 9 7 年 1 0 月7 日开始出版。在网上，还有一个自由论坛d me m a i lc l u b ，人们通过电子 6 邮件相互讨论d m k d 的热点问题。而领导整个潮流的d m k d 开发和研究中心则 是设在美国e m d e n 的m m 公司开发部。至于d m k d 书籍，可以在任何计算机 书店找到十多本，但大多带有商业色彩。 国外很多计算机公司非常重视数据挖掘的开发应用，i n f o r m i x 公司于1 9 9 8 年 底收购了在数据挖掘技术上卓有成效的r e db r i c k 公司。r e db r i c k 数据挖掘在关系 引擎中通过创建模型完成，这些模型在数据库中表现为相应的表，并且这些模型 可以通过结构查询语言( s q l ) ，像普通表一样被访问和操作。向模型中插入数据的 时候，数据挖掘计算就被执行了，然后建立含有计算结果的表。后者可以被观察， 用于对计算结果的理解，并在其它数据集合中进行预测。除此之外，m m 和微软 也成立了相应的研究中心进行这方面的工作，一些公司也已经提出了基于数据挖 掘技术的商业智能解决方案。此外，相关软件也开始在国内销售，如s a s ，s p s s ， p l a t i n u m , b o 以及i b m 等。 与国外相比，国内对数据挖掘的研究稍晚，没有形成整体力量，直到1 9 9 3 年 国家自然科学基金才首次支持该领域的研究项目，并且目前进行的大多数研究项 目是由政府资助进行的，如8 6 3 计划、“九五”计划等，从事数据挖掘研究的人员 主要在大学，也有部分在研究所或公司。研究所涉及的领域很多，一般集中于学 习算法的研究、数据挖掘的实际应用以及有关数据挖掘理论方面的研究，如北京 系统工程研究所对模糊方法在知识发现中的应用进行了较深入的研究；北京大学 也在开展对数据立方体代数的研究；华中理工大学、复旦大学、浙江大学、中国 科技大学、中科院数学研究所、吉林大学等单位开展了对关联规则开采算法的优 化和改造；南京大学、四川联合大学和上海交通大学等单位探讨、研究了非结构 化数据的知识发现以及w e b 数据挖掘。但是到目前为止还没有商用工具问世，像 复旦大学设计的基于关联规则的数据挖掘工具a r m i n e r 等也只是处于实验室研究 阶段。 目前，国外数据挖掘的发展趋势其研究方面主要有：对知识发现方法的研究 进一步发展，如近年来注重对b a y e s ( 贝叶斯) 方法以及b o o s t i n g 方法的研究和提高； 传统的统计学回归法在k d d 中的应用；k d d 与数据库的紧密结合。在应用方面 包括k d d 商业软件工具不断产生和完善，注重建立解决问题的整体系统，而不是 孤立的过程，这些软件的用户主要集中在大型银行、保险公司、电信公司和销售 7 j t 豆窑道盔堂亟整焦j 金塞 业。 1 3 2 数据挖掘在商业中的应用 在商业领域中，数据挖掘已经应用到金融业、保险业、电信业，零售业、电 力系统等行业，下面简单列出数据挖掘技术在其中一些行业中的应用问题。 在金融业中，数据挖掘可以用于对帐户进行信用等级的评估、分析信用卡的 使用模式，检测信用卡的恶性透支，探测金融政策与金融业行情之间相互影响的 关联关系、发现隐藏在数据后面的不同财政金融指数之间的联系等。由于银行经 常发生诈骗行为，给单位造成巨大的损失，因此进行诈骗甄别也受到特别的关注， 对这类诈骗进行预测，哪怕正确率很低也会减少诈骗的发生川。在进行预测时，主 要通过总结正常的行为和诈骗行为之间的关系，得到诈骗行为的一些特征，这样 当某些业务符合这些特征时，可以向决策人员提出警告。在该领域应用非常成功 的系统有：f a l c o n 系统和f a i s 系统。f a l c o n 是h n c 公司开发的信用卡欺诈 估测系统，它已被相当数量的零售银行用于探测可疑的信用卡交易；f a l c o n 的 数据格式主要针对一些流行的信用卡公司，如v i s a ，m a s t e r 等，因此它的应用 面很大。f a i s 则是一个用于识别与洗钱有关的金融交易的系统，它使用的是一般 的政府数据表单。 保险是一项风险业务，保险公司的一个重要工作就是进行风险评估，及对不 同风险领域的鉴定和分析。风险评估对保险公司的正常运作起着至关重要的作用， 保费和保单的设计都需要比较详细的风险分析。风险评估从过去的保单及其索赔 信息出发，利用数据挖掘技术寻找保单中风险较大的领域，从而得到一些实用的 风险规则，对保险公司的工作起到指导作用。 评估一项保险投资组合的效果如何，既需要对该投资组合进行整体分析，又 需要进行投资组合内部的分析。通过整体分析可以判断以前的投资组合是否赢利， 而通过投资组合内部的详细分析可以揭示该投资组合在哪些领域赢利大，在哪些 领域损失大。投资组合内部的分析对一个保险公司来说是很重要的，因为它对于 该公司是否既能保持很高的竞争力，又能保持高赢利起着很重要的作用。如果一 个公司不知道其投资组合中的哪一部分存在大的风险，那么，尽管这项投资组合 8 目前是赢利的，但要维持下去却是很难的。投资组合的整体分析可以在总保费和 总索赔的基础之上用统计的方法来实现，而对其内部的分析则需要更复杂、更精 确的方法。进行投资组合内部分析的一般方法是将该投资组合划分成些小的风 险领域，这些风险领域由一系列的风险等级来表示，风险等级则由意外事故表列 出。这种分析方法将每一个风险等级因素与索赔频率和索赔金额的关系用一个模 型来表示，模型的参数用过去己有的数据( 保单索赔等) 来估算。参数确定后，就可 用该模型预测将来在不同的风险等级参数下的索赔频率和索赔金额。由于分析的 复杂性，这种方法只能考虑几个参数( 索赔频率、索赔金额等) 。用这种方法，风险 等级参数必须是明确的，一个连续的参数就需要将其划分成一些等级。在分析详 细程度和模型的可行性两方面应选择一种平衡，而且参数之间的相互作用处理起 来很困难，因此也被忽略了。在参数多、多值变量多的情况下，这种相互作用是 很多的。 风险分析还有其它一些方法，它们大都用在保险统计领域中。s i e b c s 将这一问 题引入到数据挖掘领域，利用概率论的方法对风险领域进行研究，将每年的保险 赔偿看成是b e r n o u l l i 实验。这项工作导致了保险投资组合类别的相等概率及同一 描述思想的发展。 目前，像零售业、电信业这样的服务性行业中，为了保持竞争力，企业采取 面向客户、客户驱动和以客户为中心的发展策略，如在零售业中，分析顾客的购 买行为和习惯，有助于决定市场商品的摆放和产品的捆绑；将顾客按照其行为或 特征模式的相似性划分为若干细分市场，以采取有针对性地营销策略；分析商场 销售商品的构成，进行商品销售预测等。成功案例如美国的读者文摘出版公司， 该公司运行着一个容纳遍布全球的一亿多订户资料的业务数据库，基于对客户资 料数据库进行数据挖掘的优势，使读者文摘出版公司能够从通俗杂志扩展到专业 杂志、书刊、声像制品的出版和发行业务，极大地扩展了自己的业务范围。 数据挖掘技术在其他一些领域也有应用：医疗数据挖掘可以用于病例、病人 行为特征分析，以及用于药方管理等，以安排治疗方案、判断药方的有效性等； 司法数据挖掘可以用于案件调查、案例分析、犯罪控制等，还可以用于犯罪行为 特征分析；工业部门数据挖掘技术可以用于进行故障诊断、生产过程优化等；在 通讯网的运行中，可以使用数据挖掘技术对己有的警告信息进行分析，得到警告 9 之问的关联规则，这些有价值的信息可用于网络故障的定位检测和严重故障的预 测等任务中。 1 3 3 数据挖掘在隧道安全中的应用 我国是一个铁路大国，由于地形多变，同时也是一个隧道大国；每年铁路隧 道管理部门都要对我国境内的铁路隧道进行多次检测，并且积累了大量的隧道病 害数据，这些数据基本上都被闲置，没有为病害的预测和防治起到有效作用，虽 然一些传统的管理系统对这些采集到的数据作了一些简单的查询及统计工作，然 而并没有挖掘出这些数据中潜藏的病害规律。铁路部门每年都投入大量的人力、 物力和资金用于隧道病害的维修和整治，但隧道的状况仍然没有根本好转。 国内外对隧道病害及安全性问题都进行了大量的研究工作。国外主要侧重于 隧道的定期养护，而国内则偏重于防治方面的研究。已有的研究工作也大多是局限 于某一类具体的病害及某一类具体的工程条件，而且对隧道病害机理的认识不够 深入，因此整治措施的可靠性和可操作性均不够理想。此外，研究工作也没有参考 传统的病害数据，缺乏系统性和科学性，研究深度不够，使得病害整治技术还比较 落后。当前数据挖掘已经广泛应用于银行、保险、电力以及金融等行业中，但在 隧道安全管理应用中的研究比较少，国内外目前还没有相关研究的文献或者成果。 因此，选择正确的数据挖掘方法，对这些病害数据进行挖掘，找出各病害之 间的关系，为铁路隧道检测部门提供治理依据变得异常迫切。 1 4 本文的研究工作和内容安排 本文首先对关联规则数据挖掘方法进行介绍，然后对以往提出的关联规则算 法进行总结，并在这些算法的基础上提出两种新的关联规则算法，其中一种是对 传统a p d o r i 算法的改进算法a p r i o r i n ，另一种则是最近比较流行的基于f p - t r e e 的f p - g r o w t h 算法的改进算法f p g r o w t h n 。文章将结合我国目前铁路隧道病害的 实际情况，选择f p g r o w t h n 算法对隧道病害进行关联规则挖掘，得到对铁路隧道 管理部门非常有用的隧道病害关联情况。最后文章以作者参加的一个科研项目结 束。该项目是为成都铁路局开发的一个隧道安全管理决策支持系统，为铁路隧道 1 0 的安全管理提供决策和支持，其中较大一部分来自于数据挖掘的关联规则算法。 j e 塞銮逼塞堂亟堂焦监塞 2关联规则算法研究 2 1 引言 关联规则挖掘问题是r a g r a w a l 等人予1 9 9 3 年在文献中首先提出来的。关联 规则挖掘就是从大量的数据中挖掘出有价值的描述数据项之间相互联系的有关知 识。随着数据集和存储在数据库中的数据规模越来越大，人们对从这些数据中挖 掘相应的关联知识越来越有兴趣。例如：从大量的商业交易记录中发现有价值的 关联知识就可帮助进行商品目录的设计、交叉营销或帮助进行其它有关的商业决 策。关联规则是描述数据库中一组数据项之间的某种潜在关系的规则。一个典型 的关联规则豹例子就是：在超市中，9 0 的顾客在购买面包和黄油的同时也会购买 牛奶。其直观的意义是顾客在购买某种商品时有多大的倾向也会购买另外一些商 品。找出所有类似这样的规则，对于企业确定生产销售、产品分类设计、产品排 放、市场分析以及市场营销策略多方面等都是很有价值的。 挖掘关联知识的一个典型应用实例就是市场购物分析。根据被放到一个购物 袋的( 购物) 内容记录数据而发现的不同( 被购买) 商品之间所存在的关联知识 无疑将会帮助商家分析顾客的购买习惯。发现常在一起被购买的商品( 关联知识) 将帮助商家制定有针对性的市场营销策略。比如：顾客在购买牛奶时，是否也可 能同时购买面包或会购买哪个牌子的面包，显然能够回答这些问题的有关信息肯 定会有效地帮助商家进行有针对性的促销，以及进行合适的货架商品摆放。如可 以将牛奶和面包放在相近的地方或许会促进这两个商品的销售。 如何从交易记录数据库或关系数据库的大量数据中挖掘出关联规则知识呢? 关联规则目前的算法都有哪些? 这些算法的优劣如何? 本章主要解决这几个方面 的问题，本章首先将介绍关联规则的基本概念，然后结合一个传统的a p r i o r i 算法 给出一个关联规则的例子，同时再介绍几种已有的关联规则改进算法，最后对它 们的性能优劣进行评价。 2 2 关联规则挖掘介绍 1 2 2 2 1 关联规则挖掘基本概念 设，= ，厶，乇) 是数据项集合；设d 为与任务相关的数据集合，也就是一 个交易数据库；其中的每个交易7 是一个数据项子集，e p r _ c i ；每个交易均包 含一个识别编号t d 设，哇为一个数据项集合，当且仅当爿主t 时就称交易r 包 含彳一个关联规则就是具有“aj 占”形式的蕴含式：其中有4 c 五四c 且彳n b = a 。规则：a ：- - - b 在交易数据集d 中成立，且具有j 支持度和c 信任度。这也就 意味着交易数据集d 中有s 比例的交易t 包含彳u 口数据项；且交易数据集d 中有c 比例的交易t 满足“若包含，l 就包含口条件