（计算机应用技术专业论文）关联规则经典算法改进及其在商业智能上的应用研究.pdf

中文摘要 随着数据库技术的成熟和数据应用的普及，人类积累的数据量正在以指数速 度增长。当数据量极度增长时，如果没有有效的方法，由计算机及信息技术来提 取有用信息和知识，人们也会感到面对信息海洋像大海捞针一样束手无策。面对 这一挑战，数据挖掘技术应运而生。数据挖掘( d a t am i n i n g ，d m ) 就是从大量 的数据中挖掘出入们感兴趣的知识，它是一类深层次的数据分析方法，被认为是 解决“数据爆炸知识贫乏”的有效方法之一。最近几年里己被数据库界广泛研究。 经过若干年的研究和实践，其经济价值已经显现出来，被广泛应用于科学研究、 金融投资、市场营销、保险、医疗卫生、产品制造业、通信网络管理等行业。 在整个数据挖掘的研究中，高效率的算法始终占有特别重要的地位。由于数 据挖掘面对的是大量的数据集，因此算法的效率将对其应用起关键的作用。现有 的算法总有着这样或那样难以克服的局限性。鉴于此，本文着重对关联规则挖掘 算法进行了研究。 在研究经典a p r i o r i 算法的基础上，给出了一个新的算法，分别从减小时间 消耗和有效挖掘小概率重要规则两个方面对a p r i o r i 算法进行了改进：一方面， 针对a p r i o r i 生成的潜在频繁项目集规模过大，新算法尽量减小潜在2 项集的规 模，使之尽可能的接近频繁2 项集，大大缩短了时间消耗；另一方面，针对数据 库中项目分布不均匀，出现概率相差较大，所挖掘出的关联规则将可能涉及不到 出现频率较低的项目的问题，通过给他们赋以不同权值，区别对待数据库中的每 个项目，从而可以挖掘出a p r i o r i 挖不出但却极具价值的规则。 经过改进，新算法在时间上的消耗明显少于a p r i o r i 算法，大大提高了算法 的效率；同时，由于加入权值，使得算法能够挖掘出隐藏在小概率事件后的关联 规则，这些规则恰恰是一般改进算法易于丢弃或挖掘不出的。基于此，算法将会 在诸如旅行社发掘新的线路，银行发掘新的留学贷款项目等商业智能应用中起到 重要作用。 关键词：数据挖掘关联规则a p r i o r i 算法加权商业智能 a b s t r a c t a st h ed e v e l o p m e n to ft h ed a t a b a s et e c h n o l o g ya l eb e c o m i n gm o r em a t t t r ea n d w i d e s p r e a d , t h ea m o u n to fd a t aw h i c hp e o p l ec o l l e c t e di sg r o w i n gi ne x p o n e n t i a l s p e e d w h e nt h ea m o u n to fd a t ag r o w se x t r e m e l y , w ew i l lf e e ll o s ti nf r o n to ft h e i n f o r m a t i o n ai fw ed o n th a v ea l le f f e c t i v em e t h o d w i t ht h eh e l po fc o m p u t e rt o d i s t i l lu s e f u li n f o r m a t i o n sa n dk n o w l e d g e s t oc o p i n gw i mt h i se h a u e n g e d a t a m i n i n gt e c h n o l o g yi sg i v e nb i r t h d a t am i n i n g ( d m ) i sd e f i n d e d a sm i n i n g k n o w l e d g e st h a tp e o p l eg e ti n t e r e s t e df r o mm a s sd a t a i ti so n e k i n do f d a t aa n a l y z i n g m e t h o di nd e e pl e v e l w h i e l ah a sb e e nc o n s i d e r e d 勰a 1 1 e f f e c t i v ew a yt os o l v es o c a l l e d d a t ae x p l o d e sb u tk a _ o w l e d g el a c k s p r o b l e m i nr e c e n ty e a r s , i th a sb e e n r e s e a r c h i n ga l lo v e rt h ed a t a b a s ew o r l d a f t e rp r a c t i c e sa n dr e s e a r c h e so f s e v e r a ly e a r s ， i t se c o n o m i cv a l u eh a ss h o w n i l pa n dh a sb e e nl a r g e l y a p p l i e di ns c i e n t i f i cr e s e a r c h e s ， f i n a n c i a li n v e s t m e n t s ，m a r k e t i n g , i n s u r a n c e , m e d i c i n e ，p r o d u c t i o na n dm a n a g e m e n to f c o m m u n i c a t i o nn e t w o r k s h i g h l ye f f e c t i v em i n i n ga r i t h m e t i ch a sa l w a y sb e e np u t o na ni m p o r t a n tp l a c et h r o u g h t h ew h o l ed a t am i n i n gr e s e a r c h a sw ef a c eam e 鼯o fd a t as e t s t h ee f f i c i e n c yo ft h e a r i t h m e t i ci st h ek e y b u tw h a tw eh a v en o wh a v ea l w a y sd r a w b a c k sh e r ea n dt h e r e ， a n db e c a u s eo f t h a t , t h i sa r t i c l ep u t sm o r ea t t e n t i o no i lm i n i n ga r i t h m e t i co f a s s o c i a t e d r u l e 。 o nt h eb a s i so f h a v i n gr e s e a r c h i n go na p r i o r iw h i c hi sac l a s s i ca r i t h m e t i c , t h i sa r t i c l e g i v e saf l e w0 1 l e w h i c hi m p r o v e sa p r i o r if r o mt w oa s p e c t s f i r s t , i tr e d u c e st h et i m e c o n s u m e ；s e c o n d , i tc a nm i r l e ：r u l e sh i d i n gb e h i n ds m a l lp r o b a b i l i t ye v e n t s 嘞i st o s a y , 0 1 1o n e ：h a n d 勰t h ep o t e n t i a lf r e q u e n ti t e ms e t sp r o d u c e db ya p r i o r ih a v et o ob i g s c a l e s ，t h el l e wa r i t h m e t i ct r i e sb e s tt or e d u c et h es c a l eo f t h ep o t e n t i a lf r e q u e n t2 - i t e m s e ta n dt og e te v e nc l o s e rt of r e q u e n t2 一i t e ms e t b yd o i n gt h i s t h et i m ec o n s i l m e g r e a t l yr e d u c e d o nt h eo t h e rl u m d , a st h ei t e m si n t h ed a t a b a s ea r cn o te v e n , t h e p r o b a b i l i t i e sa r ev e r yd i f f e r e n tf r o me a c ho t h e r , w h i c hr e s u l t si ng e t t i n gr u l e st h a t c a n n o tc o n c e r n i n gw i t hi t e m sw i t hl o wp r o b a b i l i t i e s s ow eg a v et h e md i f f e r e n t w e i g h t sa n dw e c a l lg e tv e r yv a l u a b l er u l e st h a ta p r i o r ic a n t a r e ri m p r o v i n g t h er c wa r i t h m e t i cg e t sl e s st i m eo o n s u m ct h a na p r i o r id o e s g r e a t l ye n h a n c e dt h ee f f i c i e n c y m e a n w h i l e , b e c a u s eo fw e i g h t s n e wa r i t h m e t i cc a n m i n cr u l e sh i d i n gb e h i n ds m a l lp r o b 曲i l i t i e se v e n t s w h i c ha r ct h ev e r yr u l e so t h e r i m p r o v i n ga r i t h m e t i c sc a n t t b e c a u s eo ft 1 1 a t - t h i sa r i t h m e t i cw i l lp l a ya l li m p o r t a n t r o l ei ns e r i e so fb u s i n e s si n t e l l i g e n t ( b i ) a p p l i c a t i o n ss u c ha sf i n d i n gn e w w a y sf o r t r a v e la g e n c i e s ，n o wl o a no a s c sf o rb a n k sa n ds oo i l k e yw o r d s ：d a t am i n i n g , a s s o c i a t i o nr u l e , a p r i o r i ，w e i g h t , b u s i n e s s i n t e l l i g e n t ( b 1 ) 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得鑫鲞盘茎或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者躲j 班签字隰跏6 年2 月z 弓日 学位论文版权使用授权书 本学位论文作者完全了解鑫洼盘鲎有关保留、使用学位论文的规定。 特授权墨生盘鲎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名7 主趸 签字日期：2 g 年2 月7 日 导师签名：驯 签字日期：功影年。月吗日 第一章绪论 第一章绪论 随着数据库容量的膨胀，特别是数据仓库以及w e b 等新型数据源的日益普 及，联机分析处理、决策支持以及分类、聚类等复杂应用成为必然。面对这一挑 战，数据挖掘技术应运而生。数据挖掘( d a t am i n i n g ，d m ) 就是从大量的数据 中挖掘出入们感兴趣的知识，把人们对数据库的应用从低层次的末端查询工作提 高到为各级经营决策者提供决策支持的过程。 经过若干年的研究和实践，数据挖掘技术已经吸收了许多学科的最新研究成 果而形成独具特色的研究分支。像其它新技术的发展历程一样，数据挖掘也必须 经过概念提出、概念接受、广泛研究和探索、逐步应用和大量应用等阶段。从目 前的现状看，大部分学者认为数据挖掘的研究仍然处于广泛研究和探索阶段。一 方面，数据挖掘的概念已经被广泛接受。在理论上，一批具有挑战性和前瞻性的 问题被提出，吸引越来越多的研究者。数据挖掘的概念从二十世纪八十年代被提 出以后，其经济价值已经显现出来，而且被众多商业厂家所推崇，形成初步的市 场。另一方面，目前的数据挖掘技术仍存在许多问题需要研究和探索。经过十几 年的研究，数据挖掘已经在继承和发展相关基础学科( 如机器学习、统计学等) 已有成果方面取得了可喜的进步，探索出了许多独具特色的理论体系。但是这决 不意味着挖掘理论的探索已经结束，恰恰相反，他留给了研究者丰富的理论课题。 一方面，在这些大的理论框架下有许多面向实际应用目标的挖掘理论等待探索和 创新。另一方面，随着数据挖掘技术本身和相关技术的发展，新的挖掘理论的诞 生是必然的，而且可能对特定的应用产生推动作用。新理论的发展必然促进新的 挖掘算法的产生，这些算法可能扩展挖掘的有效性，如针对数据挖掘的某些阶段、 某些数据类型、大容量源数据集等更有效：可能提高挖掘的精度或效率；可能融 合特定的应用目标，如c r m 、电子商务等。因此，对数据挖掘理论和算法的探 讨将是长期而艰巨的任务。 关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。它在数据挖 掘中是一个重要的课题，最近几年已被业界所广泛研究。关联规则挖掘的一个典 型例子是购物篮分析。关联规则研究有助于发现交易数据库中不同商品( 项) 之 间的联系，找出顾客购买行为模式，如购买了某一商品对购买其他商品的影响。 分析结果可以应用于商品货架布局、货存安排以及根据购买模式对用户进行分 类。a g r a w a l 等于1 9 9 3 年首先提出了挖掘顾客交易数据库中项集间的关联规则 第一章绪论 问题 5 1 1 ，以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。他 们的工作包括对原有的算法进行优化，如引入随机采样、并行的思想等，以提高 算法挖掘规则的效率；对关联规则的应用进行推广。最近也有独立于a g r a w a l 的频集方法的工作 5 2 】，以避免频集方法的一些缺陷，探索挖掘关联规则的新方 法。也有一些工作【5 3 】注重于对挖掘到的模式的价值进行评估，他们提出的模型 建议了一些值得考虑的研究方向。由于计算机数据采集工具以及关系数据库技 术的发展，目前各行业存储了大量的数据，航空航天、气象、医疗、农业等行业 尤为突出。传统的数据分析手段难以应付，导致越来越严重的数据灾难，迫使 决策者出现或是穷子应付，或是置之不理的事实。关系数据库提供的简单查询及 报表生成功能，只能获得数据的表层信息，而不能获得数据属性的内在关系和隐 含的信息，即淹没了包含的知识，造成了资源的浪费。为了使消耗大量财力与 物力所收集与整理的宝贵数据资源得以利用，有效解决数据丰富性及知识贫乏性 的矛盾，需要新技术智能、自动地分析处理原始数据，促使了数据库中的知识发 现( k d d 。k n o w l 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 ) 技术的出现 5 4 】。文 5 8 】中认为k d d 是一个综合的过程，它包括数据录入、迭代 求解、用户交互以及许多定制要求和决策设计等，而d a t am i n i n g 只是k d d 中 的一个具体却是关键的步骤。数据库中的知识发现术语是在1 9 8 9 年的第一届 k d d 专题讨论会上被首次采用，它强调了知识是数据发现的最终产品。 这一研究领域兴起于八十年代初，它是一个众多学科诸如人工智能、机器学 习、模式识别、统计学、数据库和知识库、数据可视化等相互交叉、融合所形成 的一个新兴的且具有广阔前景的领域。从数据库中发现出来的知识可以用在信息 管理、过程控制、科学研究、决策支持等许多方面 5 5 】- 5 7 】 1 9 9 8 年第四届知识发现与数据挖掘国际会议上不仅进行了学术讨论，并且 有3 0 多家软件公司展示了数据挖掘软件产品，在北美、欧洲等国得到较大应用。 在我国，许多单位也已开始此项技术研究，但目前取得成功应用的例子还未见报 道。 通过国家“七五”，“八五”和正在进行的“九五”科技攻关。国家品种资源 研究所目前已建成了拥有1 8 0 种作物、3 5 万份种质信息、将近2 g 字节的数据记 录的中国作物种质资源信息系统( c g g i s ) 。c g r i s 是世界上最大的植物遗传资源 信息查询系统之一。包括国家种质库管理、国家复份库管理、国家种质资源圃管 理、中期库管理、农作物特性评价鉴定、优异资源综合评价和国内外种质交换7 个子系统，近7 0 0 个数据库表，1 1 2 万条记录。但目前这一大型的农作物种质资源 数据库仅仅用于查询、检索。隐藏的丰富知识内容有待于通过有效的知识发现工 具，为农业部门的信息决策提供帮助，使数据库得到进一步的利用。 第一章绪论 目前的大多数频繁项集挖掘算法都会产生数目庞大的频繁项集，并且其中的 绝大多数并不是客户所期望得到的。为了解决这个问题，通过加入约束条件，允 许用户通过一组约束条件来表达在频集挖掘中的侧重点。除了用户可以对挖掘的 方向和重点控制之外，还可以把这些条件放入到挖掘过程中进行检验，从而可以 减少产生频繁项集的模式空间，进而提高整个挖掘过程的执行效率。 约束条件自身有一些可以遵循的规律，也正是这些规律才使我们可以把它们 放入挖掘算法以便在挖掘过程中进行校验。文献 2 】， 3 中介绍了两大类约束条 件：简明( s u c c i n c t ) 约束和反单调( a n t i - m o n o t o n e ) 约束。文献 4 】， 5 则在关 联规则的挖掘中，既研究了上述两种约束，又研究了第三种类型的约束一单调 ( m o n o t o n e ) 约束。尽管如此，还是有一些约束条件不在这三类约束条件之中。 文献【1 】介绍了可能化约束的概念，其思想是：通过某种转换，使一些约束条件 可以归为这三类之中，从而可以把它们放入挖掘算法中去。但是可转化约束的转 换是基于项的某个排序，不同的约束可能基于不同的排序才是可转化的。在多约 束的情况下，要找到某个序列使那些可转化约束条件在该序列下都是可转化的， 几乎是不可能的。文献【6 】采用了折衷方案，即把焦点集中在一些常用的序列上， 并采用一个抽样数据库对约束条件进行检验，进而找出一个较优的方案来进行频 繁项集的挖掘。近几年人们广泛研究相联规则模型和算法【7 曲】，绝大部分研究 工作都有一个共性，即不论项目属性如何，一律采用统一的最小支持度和最小信 任度阙值。支持度阙值能够控制规则的涉猎范围，制约产生规则的数量，规定统 一的最小支持度阙值的意义在于简化了知识发现问题的复杂度。由于仅仅关注项 目或项目集的出现频率，屏蔽掉了各个项目自身固有的属性特征，使模型与实际 应用之间产生了差异。在现实数据库中，一些项目经常出现，另一些稀有项目出 现频率较低，但很有可能这些出现频率低的项目也是我们关注的。如果采用这种 与现实需求有较大差异的单一支持度相联规则，就会出现如下问题 1 0 ：( 1 ) 如 果将最小支持度阙值设嚣过高，就不能发现包含稀有项目的规则；( 2 ) 为了发现 包含稀有项目的规则，只能采用很低的最小支持度阙值，结果导致产生大量冗余 规则。 解决上述问题的方法主要分为两类：一种是根据项目集出现频繁度分成几个 区域，每个区域用自己的最小支持度阙值【1 l 】；另一种是把稀有项目组成一个抽 象的项目集合，把它们视为一类，进行概念提升，达到增加频度值的目的r 1 1 ， 1 2 。而由此又会带来新的问题：即采用第一种方法，很难发现有块区域的项目 构成的规则；用第二种方法又针对性太强，只能用于发现具有某种特定属性的规 则。 很多情况下，发现含有稀有项目的规则是必要的1 1 0 ，如一些价格昂贵的耐 第一章绪论 用品，虽然购买频率很低，但商家会从中获得较高的利润。为有效提取这些含有 稀有项目的规则，b i n 等人提出对不同的数据项目采用不同的最小支持度阙值的 思想【1 0 】，但效果不甚理想。文献 1 3 1 扩展了相联规则模型：不仅仅利用项目“是 否出现”这样的二值属性，同时考虑项目的多个描述属性，通过模糊综合评判确 定各个项目的最小支持度阙值。为及时减少冗余规则和无意义的规则，提出支持 度区间思想，根据项目属性与出现频率决定一个项目的重要程度，同时加入主观 评价，剔除冗余规则，最终得到对决策有价值的规则。 布尔型属性关联规则是a p r i o f i 类的。还有一类是数量型关联，在股市分析， 银行存款分析和医疗诊断等众多方面都有重要应用价值。数量关联用来描述数量 型属性特征之间的相互关系。文献 1 4 】首先讨论数量型关联规则，文中的挖掘算 法将数量型属性划分成多个区间，但存在边界过硬的缺点。【1 5 】用模糊集软化划 分边界，并提出模糊关联规则的概念。【1 6 】用相关的模糊c - 均值算法划分数量型 属性，并给出语言值关联规则的挖掘算法。 1 7 】用正态云软化划分边界并提出正 态云关联规则的概念。 现有算法均基于可信度和支持度的阙值。但在实际应用中仅考虑这两个因素 是不够的，并且还可能引起误导。文献【1 8 】提出了增加第三个阙值：兴趣度。即 一条即使可信度和支持度都很高的规则，其实际利用价值已经难以肯定了，即它 的兴趣降低了。文章引出一条规则的兴趣度越大于0 ，说明我们对这条规则越感 兴趣，即其实际利用价值越大；一条规则的兴趣度越小于0 ，说明我们对这条规 则的反面规则越感兴趣。另一个事实是兴趣度阙值定得越高，挖掘出的规则越少， 反之则越多。 空间统计分析主要用于空间数据的分类和综合评价。它涉及到空间和非空间 数据的处理和统计计算。空间统计分析包括主成分分析、层次分析、系统聚类分 析、判别分析、空间自相关分析和g 统计分析。文献【1 9 】用空间自相关分析和g 统计分析方法来挖掘数据之间的关联规则。 1 9 9 8 年r o b e r t oj 和b a y a r d oj r 2 1 1 利用自底向上搜索和项目集排序的方法建 立了一种挖掘长型频繁项的m a x - m i n e r 算法；l i nd 和z k e d e mf 2 0 提出了一 种双向钳型搜索p i n c e r - s e a r c h 方法，利用自底向上搜索产生的非频繁项集来约束 和修剪自项向下方向的最大候选频繁项集。两种方法细节虽不同，但修剪最大频 繁项的思想类似。 j a w c ih a r t 等人针对挖掘大频繁项的困难提出一种f p t r e e 方法 2 2 1 。主要是 采用分而治之的思想，利用扩展前缀树这种数据结构存储经过压缩的频繁项关键 信息，按f p t r e e 的生长趋势划分和投影数据库。 文献 2 3 】提出将事务组合构成一个事物搜索空间( 或事物域) ，用t 表示； 第一章绪论 项目组合构成一个项目搜索空间( 或项目域) ，用x 表示。挖掘频繁项要在t , x 两个空间中同时搜索满足条件的目标：所以应该同时压缩两个搜索空间才能获得 最佳搜索路径。 这种双空间搜索方法利用了计数特征和结构特征两种信息，从一个空间到另 一个空间，这样就比只在单个空间中搜索效率提高很多。 统计分析方法是最基本的数据挖掘技术方法之- - 2 4 。常用的有：判别分析、 因子分析、相关分析、多元回归分析、偏最小二乘回归方法等。文献【2 5 】永祥贵 数学模型来研究人口增长率和g d p 间的相关关系 由于数据库为非静态的，而是动态的。研究关联规则更新算法具有十分重要 的意义。已提出的关联规则更新算法的共同的不足是频繁集的负边界的求解代价 高 2 6 , - , 3 1 】( 包括空间代价和时间代价) ；d e l t a 算法 3 1 】对文献 2 8 - 3 0 进行了综 合改进，但仍需求解大量频繁项集的负边界空间。由于以前的算法缺乏记忆功能， 文献【3 3 】提出了一种前缀广义链表( g l ) 及基于此种结构的快速关联规则挖掘算 法( p g l a r ) ，前缀广义表比f p - t r e e 灵活 3 2 1 ，可以方便的进行分解和合并， 有利于增量更新算法实现。 基于规则模板的挖掘 3 4 】，使用元规则限定挖掘的关联规则形式，降低了挖 掘难度，但也使其应用受到一定限制。采用类i p r i o r i 算法的方法通过求频繁谓 词集得到多维关联规贝j j 3 5 1 ，具有很好的可扩展性，能够处理大量数据，但其处 理多维谓词的i o 开销较大。利用数据立方进行多位关联规则挖掘的算法 3 6 】具 有较好的i o 性能，特别是当数据立方较小，可以用多位数组有效实现，或者使 用元规则对项集加以限制时，其i o 性能特别好。但是，由于数据立方不能有效 地处理集合值，当事务数据库非常大时，其性能明显下降。 文献 3 7 】将数据立方技术和a p r i o r i 算法的思想结合在一起，采用数据立方计 算频繁维谓词集，而使用与a p n o d 算法类似的方法求多维频繁项集。此外，还 引入了一种频繁谓词集索引树结构，以加快多维频繁项集计算速度。算法不仅有 较好的i o 效率，还有很好的可扩展性。 s u p p o r t - c o n f i d e n c e 模型是正关联规则挖掘普遍应用的模型，用s u p p o r t ( x u v ) 和e o n f ( x 硝0 来度量关联规则x - y 的不确定性，但会得到如x - y 但x 与y 不相关的规则。可见此模型还不完善。实际应用中，我们还要挖掘负关联规则。 针对s u p p o r t - c o n f i d e n c e 模型存在的不足，很多研究者提出了度量关联规则不 确定性的方法。在文献【3 9 】中，p i a t e r t s k y - s h a p i r o 提出关系上的规则的概念。文 献 3 8 中m o t w a n i 和s i l v e r s t e i n 从经典的统计学角度利用c h i s q u a r e d 测试项集的 相关性来度量关联规则的有效性。然而，该模型依然存在许多不足：( 1 ) 运用 e h i s q u a r e d 值只能确定x 与y 是否独立；( 2 ) 若x 与y 不独立，则需要一个机 第一章绪论 制来决定x 与y 是正相关还是负相关；( 3 ) 若x 与y 是负相关的，则还需要另 外的方法决定是哪种形式。在文献【4 0 】中，a g g a r n a l 和y u 提出聚集强度模型以 度量关联规则的关注程度。然而，该模型并没有考虑p i a t c r t s k y - s h a p i r o 的观点， 而且当挖掘负关联规则时，需重新计算s u p p 和c o n f 的值。 现实问题是，面对海量数以及数据自身之间的复杂的关系，数据集随时间不 停地变化，不同时期的数据集之间的联系，怎样才能正确地维护、继承已经开采 出来的规则，以期发现更多，更准确的知识。文献 4 1 】在关联规则的维护中，运 用时间序列对事件进行预测，并把预测结果用于关联规则的改进与维护过程，分 析了用时间序列来预测事件的发生，把事件与数据集对应起来。分析了关联规则 的维护在基于动态变化的数据集时的不足，并加以改进，得到了新的对大项目集 的判别算法。 文献 4 2 】考虑了发现经常性周期关联规则的问题。假如在一系列有一定周期 间隔的时间单元内，一条关联规则的发生次数达到用户指定的比率，就称其为一 条“经常性周期关联规则”。通过研究周期、数据子集和大项目集等的联系，提 出了多种发现周期性关联规则的方法 本文的内容和结构安排如下： 第一章：绪论，介绍了与课题相关的背景知识，问题的提出，本领域的研究 动态以及论文的结构安排； 第二章：阐述了商业智能的有关知识； 第三章：阐述了数据挖掘的产生、概念、系统结构、任务、研究的主要内容 及应用；还简单介绍了有关商业智能的一些基本知识； 第四章：阐述了关联规则的概念，基本性质，种类及应用。重点介绍了关联 规则的挖掘算法的基本模型和经典的a p r i o r i 算法。 第五章：针对a p r i o r i 算法的局限性提出了改进算法，从时间消耗和挖掘隐藏 在小概率事件之后的有价值规则两方面，通过理论推导和实验，证明改进算法在 这两方面的改进效果不甚明显。 第六章：总结了本文的工作并对未来的研究方向进行了展望。 第二章商业智能概述 第二章商业智能概述 bi ( b u s i n e s si n t e l l i g e n c e ，商业智能) 是随着i n t e m e t 的高速发展和企业信 息化的不断深入而产生的。bi 使得企业的决策者能够对企业信息进行有效、合 理地分析和处理，为生产决策提供可靠的依据。它把先进的信息技术应用到整个 企业，不仅为企业提供信息获取能力，而且通过对信息的开发，将其转变为企业 的竞争优势，也有人称之为混沌世界中的智能。因此，越来越多的企业提出他们 对b i 的需求，把b i 作为一种帮助企业达到经营目标的一种有效手段。 根据硅谷动力网在2 0 0 1 年底对1 0 3 家企业的c i o 所做的调查，在未来两年 里，c i o 们最优先考虑实施的信息化项目，排在首位的是商业智能( 3 7 2 ) ，位 列信息存储和灾难恢复系统( 3 3 5 ) 、客户关系管理( 2 9 8 ) 和网络安全系统 ( 2 8 7 ) 之前。既然商业智能被如此重视，究竟什么是商业智能昵? 2 1 商业智能的概念及产生背景 2 1 1 什么是商业智能 商业智能这一术语1 9 8 9 年由g a r t n e rg r o u p 的h o w a r dd r e s n e r 首次提出， 它描述了一系列的概念和方法，通过应用基于事实的支持系统来辅助商业决策的 制定。商业智能技术提供使企业迅速分析数据的技术和方法，包括收集、管理和 分析数据，将这些数据转化为有用的信息，然后分发到企业各处。 学术界对bi 有不同的定义：d a t a wa r e h o u s ei n s t i t u t e 组织认为“bi 是将 数据转换成知识并将知识应用到商业行为上的一个过程”； g a r t n e rg r o u p 则认 为“bi 是将数据转换成信息的过程，然后通过发现将信息转化为知识”。确切 地讲， bi 并不是一项新技术， 它将数据仓库( d w ) 、联机分析处j 里( o l ap ) 、 数据挖掘( d m ) 等技术与客户关系管理( c r m ) 结合起来应用于商业活动实际 过程当中，实现了技术服务于决策的目的。 商业智能系统从企业运作的日常数据中开发出结论性的、基于事实的和具有 可实施性的信息，使企业能够更快更容易的做出更好的商业决策。使企业管理者 和决策者以一种更清晰的角度看待业务数据，提高企业运转效率、增加利润并建 立良好的客户关系，使企业以最短的时间发现商业机会捕捉商业机遇。如何时何 第二章商业智能概述 地进入何市场，如何选择和管理大客户联系，以及如何选择和有效地推出商品优 惠策略等。同时通过提供决策分析能力，使企业更有效地实现了财务分析、风险 管理、诈骗检测、分销和后勤管理，以及销售状况分析等。 商业智能系统可以说是一个智能决策支持系统，它不是一种产品或服务，从 某种意义上商业智能是一种概念或者说是一种商业理念，它是在企业数据仓库的 基础上，利用数据挖掘和信息挖掘工具获取商业信息，以辅助和支持商业决策的 全过程。通过商业智能技术，用户更充分地了解他们的产品、服务、客户以及销 售趋势。目前在国外商业智能软件与o f f i c e 办公软件，浏览器一起已经成为企 业必不可少的桌面办公软件之一。商业智能在我国尚处于起步阶段，商业智能系 统适合应用的行业依次是：零售、保险、银行、通信、离散制造、政府、医疗、 分销、流程制造、教育。然而，从各种资料上看，商业智能、数据仓库和客户关 系管理在我国只在少数的银行、保险、电信行业有实施的案例。 2 1 2 商业智能的产生背景 1 、企业的“数据监狱”( d a t aj a i l ) 现象 商务活动从办公自动化出现的早期开始就在其运作过程中收集大量的数据， 包括销售、成本、质量控制、库存、客户服务等各方面息息相关的企业数据，分 别存储于数据库、数据集市、数据仓库、多维数据库、第三方的应用或其它文件 中。因此对大部分企业来说数据处理的问题不是数据缺乏，而是大量的数据冗余 和数据不一致。庞大的数据量和传统数据管理方法的缺陷，使大部分企业出现了 “数据拥挤”( 数据监狱) 现象，既不利于企业的管理也不利于信息的有效利用。 因此，如何解决数据拥挤，同时又能使这些数据充分地发挥作用这己成为企业商 务发展的一个热点问题。 2 、“数据= 资产”新企业观念的建立 在企业界，数据资产的观念正在进入企业的资源规划( e p , p ) 系统中，而把 数据转换为资产的方法和技术也正在成为企业投资i t 的热点。因为目前大部分 大中规模的企业都是信息丰富的组织，而一个信息丰富的组织的绩效不仅仅依赖 于产品，服务或地点等因素，而更重要的是依赖知识。而从数据信息一知识是 一个并不简单的过程。商业智能的本质正是把数据转化为知识，致力于知识发现 和挖掘，使企业的数据资产能带来明显的经济效益，减少不确定性因素的影响， 使企业取得新的竞争优势。 3 、企业运营模式的变化 第二章商业智能概述 电子商务正在改变着全球商务活动的方式，信息在经济活动中越来越占据着 重要的地位。对企业来说信息包括生产、销售、市场、顾客和竞争对手的信息， 信息是企业竞争的战略性资源。建立在i n t e r n e t 之上的企业经营模式电子商务： 电子邮件、电子数据交换、电子支付系统、电子营销等技术的发展和应用为商业 智能系统提供了市场和生存环境。 4 、数据库和人工智能技术的发展 商业智能的发展也得益于相关技术的发展，并行处理系统、廉价数据存储、 新数据挖掘算法、神经网络技术、人工智能技术、决策支持技术、从大量数据中 发现其后潜藏的商业机会等等技术的发展，使企业能以更低的成本投资商业智 能，并取得更高的r r 投资回报率。 2 2 商业智能的体系结构及架构过程 所谓体系结构( a r c h i t e c t u r e ) 是指一整套的规则和结构，为一个系统或产品 的整体设计提供主框架。而一个商业智能的体系结构是指通过识别和理解数据在 系统中的流动过程和数据在企业中的应用过程来提供商业智能系统应用的主框 架。商业智能的体系结构指导商业智能系统的建立，其建立步骤为： l 、识别和确定数据源 商业智能的数据来自于多种数据源，包括电子商务数据、交易处理数据以及 相关的外部数据等。如从交易处理应用软件中获取订单信息、顾客信息和产品信 息，从电子商务网站中获取访问和点击信息，还可以从账务系统中获得账务信息， 从市场部门获得市场信息等。 2 、进行数据集成和存储管理 数据集成可以分为“懒散型”数据集成和“急切型”数据集成。懒散型数据 集成一般应用在数据库系统中，其显著特征是集成发生在查询产生之后。用户提 出一个查询后，系统确定查询所需的数据来源，为每一个来源产生子查询和命令， 然后从数据源中获取信息，执行一定的转换、过滤和合并后把最终结果返回给用 户或客户系统。数据在查询出现后才从原始资料中提取。急切型数据集成通常出 现在数据仓库技术中，它提前预测用户的需求，把可能会被用到的数据提前从数 据源系统中抽取出来，经过变换、过滤及与其它相关信息的合并，然后存储在集 中的仓库中。当一个查询出现后，直接在仓库中运行，不需要进入最初的数据源 系统中去。这种急切型的数据集成方法使数据仓库中存储着大量经过预先计算的 第二章商业智能概述 总计数据和累加数据，在查询时能显著加快查询速度，满足用户对响应时间的需 求。 3 、数据分析和建模 商业智能建立的本质目的是获得高的投资回报率( r o d ，投资回报主要体现 在商业智能的应用状况上。通过数据分析和建模将数据转化为信息，通常由数据 分析工具负责完成。在商业智能系统中，交互式信息分析、挖掘工具、数据分析 软件、商业智能工具与商业运营规则相结合对数据的模式和趋势进行分析，提供 给用户企业商务的方方面面的详细信息，以辅助商务活动决策获得更高的r o i 和利润。 2 3 商业智能的典型应用 1 经营分析 经营分析包括经营指标分析、经营业绩分析和财务分析三部分。 经营指标分析是指对企业不同的业务流程和业务环节的指标，如：利润率、 应收率、销售率、库存量、单品销售情况及所占营业比例、风险采购和库存评价 指标等进行搜集和分析。但这些指标只能反映局部的经营状况。为了解企业的整 体经营状况，还需对这些指标进行科学的组织和分析，利用智能管理技术，形成 一个能反映企业整体情况的数学模型。这样通过观察总指标并设置告警，才能获 得整个企业的经营状况。 经营业绩分析是指对各部门的营业额、销售量等进行统计，在此基础上，进 行同期比较分析、应收分析、盈亏分析、各种商品的风险度分析等等。经营业绩 分析有利于企业实时掌握自身的发展和经营情况，有利于企业及时调整经营业 务、化解经营风险。 财务分析是指对企业财务数据中的利润、费用支出、资金占用及其他具体经 济指标进行有效分析。通过财务分析，可以及时掌握企业在资金使用方面的实际 情况，为及时调整和降低企业成本提供数据依据。 2 战略决策支持 在经营分析的基础上，将各类数据、信息进行高度的概括和总结，然后形成 供高级决策者进行战略决策时参考的企业经营状况分析报告，是商业智能的优势 所在。 商业智能对战略决策的支持，分别表现在对公司战略、业务战略和职能战略 第二章商业智能概述 的支持上。在公司战略决策支持层面上，可以根据公司各战略业务单元的经营业 绩和经营定位，选择一种合理的投资组合战略；在业务战略决策支持层面上，由 于商业智能系统中集成了更多的外部数据，如外部环境和行业信息，各战略业务 单元可据此分别制定自身的竞争战略；在职能战略决策支持层面上，由于来自于 企业内部的各种信息，源源不断地输入进来，相应地可以提供营销、生产、财务、 人力资源等决策支持。 3 绩效管理 商业智能技术能够从企业各种应用系统中提取出各种基础绩效指标与关键 绩效指标( k p i , k e y p e r f o r m a n c e i n d i c a t o r ) 。为了考核员工的绩效，企业可以先将 希望员工要做的工作进行量化，然后借助商业智能工具，管理人员可以追踪、衡 量和评价员工的工作绩效，引导员工的思想方向和行动与企业的整体目标保持一 致。 4 与各种企业信息化系统的关系 商业智能作为一种企业信息集成解决方案，为企业不同的应用系统，如企业 资源规划( e r p ) 、客户关系管理( c 砌旧、供应链管理( s c m ) 、办公自动化( o a ) 、 电子商务( e - c o m m e r c e ) 以及外部环境扫描( e n v i r o n m e n t a ls c a n n i n g ) 等系统之间 架起了互通的桥梁。同时，这些信息化系统也为商业智能提供了数据源，离开了 它们，商业智能就会成为无源之水，无本之木。但商业智能的价值又在这些系统 之上，因为它可以发现数据背后隐藏的商机或威胁，获得洞察力，了解企业和市 场的现状，把握趋势，识别异常情况，理解企业业务的推动力量，认清正在对企 业的业务产生影响的行为及影响程度如何等。 2 4 商业智能的应用实施 企业在实施商业智能技术时，有两种方法可供选择。一种较稳妥的方法是从 企业中某一个局部的商业需求开始，尝试着进行商业智能的实施。这种方法容易 实现，回报快，三年r o i ( 投资回报率) 较高。另一种方法则是在企业所有领域 全面实施商业智能，以支持企业的所有业务过程，满足跨企业的决策支持。这种 方法较前一种方法更具挑战性，三年r o i 较低，收回投资的平均年限也较长。 无论采用哪一种方法，企业要建立自己的商业智能系统，都需要经历商业智能系 统分析、系统设计和系统维护与管理三个阶段。 1 商业智能系统分析 商业智能系统分析，又可分为企业需求分析、信息来源分析、逻辑信息模型 第二章商业智能概述 设计，商业智能系统结构设计等步骤。 企业需求分析可包含c r m 分析、经营分析、产品组合分析、产品促销推广 分析、财务风险分析与电子商务分析等等。 信息来源分析要对可能的信息来源进行调查，包括从顾客服务、商品销售、 存货采购、会计财务、人力资源、推广促销、市场调查与电子商