（计算机应用技术专业论文）面向超市数据的关联规则挖掘算法研究及其应用.pdf

东北大学嘎 j 学位论叟 摘要 面向超市数据的关联规则挖掘算法研究及其应用 摘要 数据挖掘是由大多数零售商面临的决策支持问题所促使产生的。由于条形码技术的 发展，零售部门可以利用前端收款机收集存储大量的售货数据。因此，如果对这些历史 事务数据进行分析，则可对顾客的购买行为提供极有价值的信息。 关联规则是数据挖掘的核心技术之一。本文首先介绍了数据挖掘的概念、任务及应 用；其次给出关联规则的概念、属性、形式和种类；再次对关联规则挖掘技术的几种算 法进行了研究分析，给出a p r i o r i 算法和f p g r o w t h 算法的优缺点比较，同时论述了散列、 事务压缩、杂凑、划分、选样、动态项集计算、基于形式概念分析的关联规则挖掘的改 进算法，讨论了关联规则的扩展问题。 对大型超市数据仓库的设计与o l a p 的应用进行了描述，引出负关联规则，给出了 负关联规则的定义和挖掘算法，也把基于正负关联规则挖掘方法用于超市问题上，分析 商品的相关属性，找出正负关联规则，对于正负关联规则带来的一些诸如非频繁项集和 自向矛盾等新问题，提出了两个算法：一个是基于两级支持度的同时挖掘频繁项集与非 频繁项集的算法；二是结合相关性的研究设计了一个能够同时挖掘频繁项集与非频繁项 集中的正、负关联规则算法，从而找到优化的解决方案。 讨论了关联规则的具体应用问题，在挖掘关联规则的同时加入商品利润的概念，针 对“关联规则发现需要优先考虑利润，然后才是统计学上的显著性”这一实际问题，提 出了具有利润约束的关联规则问题。为了解决该问题，在关联规则问题中引入了利润约 束与利润集参数，提出了解决该问题高效的算法。最后研究大型数据库分层次提取关联 规则的技术，把一个大型超市的交易数据库中有关食品的交易记录提取出来，对以上基 于概念层次树的多层次关联规则算法进行仿真，挖掘出食品间的多层次关联规则。 此外，本文在可信度、支持度的基础上，利用种新的评估手段反映规则的意义， 用来发现那些虽然可信度、支持度较低，但仍然有一定意义的规则，并通过试验进行了 证明。 关键词：数据挖掘；关联规则：负关联规则 查些叁兰堡兰兰丝堡兰 垒堕塑 a l g o r i t h m sr e s e a r c h a n d a p p l i c a t i o n so f a s s o c i a t i o nr u l e so r i e n t e ds u p e r m a r k e td a t a a b s t r a c t t h ed a t am i n i n gi sp r o m o t e da n db r o u g h tb yt h ei s s u eo fd e c i s i o ns u p p o r tc o n f r o n t e d w i t ht h em o s tt r a d e s m e n b e c a u s eo ft h ed e v e l o p m e n to ft h eb a r - c o d et e c h n o l o g y , r e t a i l d e a l e rc a nu t i l i z et h ef r o n t - e n dp a y i n g - m a c h i n et oc o l l e c ta n ds t o r ea b u n d a n tt r a d i n g i n f o r m a t i o n t h e r e f o r e ，i ft h ea n a l y s i si s c o n d u c t e dt ot h e s eh i s t o r i ca f f a i rd a t a , t h e i n f o r m a t i o nw i t hu t m o s tv a l u ei ss u p p l i e df o rt h eb u y i n ga c t i v i t i e so f t h ec u s t o m e r t h i sp a p e rm a i n l ys t u d i e st h ea l g o r i t h m sa n dt h ea p p l i c a t i o nf o ra s s o c i a t i o nr u l e si nd a t a m i n i n g a s s o c i a t i o nr u l e sm i n i n gi so n eo f t h ek e r n e lt e c h n o l o g i e so f t h ed a t am i n i n g t h i st h e s i s f i r s ti n t r o d u c e st h ec o n c e p t i o n s ，t a s k sa n da p p l i c a t i o n so ft h ed a t am i n i n g ；t h e ng i v e st h e c o n c e p t i o n s ，p r o p e r t i e s ，f o r m sa n dv a r i e t i e so f a s s o c i a t i o nr o l e s i ta g a i ns t u d i e sa n da n a l y s e s s e v e r a la l g o r i t h m sf o rm i n i n gt e c ha s s o c i a t i o nr u l e s ，a n dc o m p a r e st h ea d v a n t a g e sa n dt h e d i s a d v a n t a g e so ft h ea p r i o r ia l g o r i t h ma n dt h ef p g r o w t ha l g o r i t h m a tt h es a m et i m e ，i t d i s c u s s e st h ec a l c u l a t i o no fh a s h ，t r a n s a c t i o nc o m p r e s s i o n ，o m n i u m g a t h e r u m ，p a r t i t i o n ， s a m p l i n g ，d y n a m i ci t e mc o l l e c t i o n ，a n dt h ei m p r o v e da l g o r i t h mf o rm i n i n ga s s o c i a t i o nr u l e s b a s e do nf o r ma n dc o n c e p t i o na n a l y s i s t h ee x p a n d i n gi s s u e so ft h ea s s o c i a t i o nr o l e d i s c o v e r ya l s oa r ed e b a t e d t h ed e s i g no ft h ed a t ab a s eo ft h es u p e r - m a r k e ta n da p p l i c a t i o no fo l a pa r ed e s c r i b e d t h en e g a t i v ea s s o c i a t i o nr u l e sa r ee d u c e d t h ed e f i n i t i o no fn e g a t i v ea s s o c i a t i o nr u l e sa n d m i n i n ga l g o r i t h ma r ep r e s e n t e d t h em i n i n gm e t h o d s b a s e df o rp o s i t i v ea n dn e g a t i v e a s s o c i a t i o nr u l e sa r eu s e df o r t h ei s s u e so fs u p e r - m a r k e t t h ec o r r e l a t i o nf e a t u r e so f c o m m o d i t i e sa r ea n a l y z e d t h ep o s i t i v ea n dn e g a t i v ea s s o c i a t i o nr u l e sa r ef o u n do u t f o rt h e n e wi s s u e ss u c ha sn o n - f r e q u e n ti t e m ss e t sa n dt h es e l f - d i r e c t i o nc o n t r a d i c t i o nb r o u g h tb yt h e p o s i t i v ea n dn e g a t i v ea s s o c i a t i o nr u l e s ，t w oc a l c u l a t i o nm e t h o d sa r ep u tf o r w a r d ：f i r s ti st h e c a l c u l a t i o nm e t h o dw h i c hs i m u l t a n e o u s l ym i n e st h ef r e q u e n ti t e ms e t sa n dt h en o n - f r e q u e n t mo 东北大学硕上学位论史 i t e ms e t sb a s e do nt w ol e v e l ss u p p o r td e g r e e ；s e c o n d , c o m b i n i n gw i t i lt h er e s e a r c ho ft h e r e l a t i v i t y , d e s i g n st h ep o s i t i v ea n dn e g a t i v ea s s o c i a t i o nr u l em i n i n gm e t h o d sw h i c hc a t l s i m u l t a n e o u s l ym i n et h ef r e q u e n ti t e ms e t sa n dt h en o n f r e q u e n ti t e ms e t s ，t h e r e b yt h e o p t i m a ls o l u t i o ni sp r o p o s e d t h ec o n c r e t ea p p l i c a t i o ni s s u e so ft h ea s s o c i a t i o nr u l e sa r ed i s c u s s e d ，t h ec o n c e p t i o no f t h ec o m m o d i t yp r o f i ti sc o n s i d e r e dw h e nt h ea s s o c i a t i o nr u l e sa l em i n e d a i ma tt h ep r a c t i c e i s s u eo f 咀1 ea s s o c i a t i o nr u l ed i s c o v e r yn e e d st of i r s t l yc o n s i d e rt h ep r o f i t a n dt h e ni st h e s i g n i f i c a n c et h es t a t i s t i c s ”t h ei s s u e so fm i n i n ga s s o c i a t i o nr u l e sw i mt h ep r o f i tr e s t r i c t i o na l e p u tf o r w a r d i no r d e rt os o l v e t h e s ei s s u e s ，i nt h ei s s u eo f a s s o c i a t i o nr u l et h ep r o f i tr e s t r i c t i o n a n dt h ep r o f i tc o l l e c t i o np a r a m e t e ra r ei n t r o d u c e d ，a n dah i g h - e f f i c i e n c ya l g o r i t h mt os o l v e t h i sp r o b l e mi sp u tf o r w a r d f i n a l l y , t h et e c h n i q u eo fp i e k i n g - u pt h ea s s o c i a t i o nr u l eb y l e v e l si nl a r g ed a t a - b a s ei sr e s e a l c h e d t h et r a d er e c o r dc o n c e r n i n gt h ef o o d s t u f ff r o mt h e t r a n s a c t i o nd a m - b a s ei nal a r g es u p e r - m a r k e ti st a k e n a n dt h em u l t i i e v e la s s o c i a t i o nr u l e a l g o r i t h mb a s e do na b o v e - m e n t i o n e dc o n c e p l e v e lt r e ei s s i m u l a t e d ，t h em u l t i l e v e l a s s o c i a t i o nr u l ea m o n gt h ef o o d s t u f f i sf o u n d b e s i d e s ，t h i sp a p e r , b a s e do nt h er e l i a b i l i t ya n ds u p p o r t i n gd e g r e e ，u t i l i z e sak i n do fn e w e v a l u a t i o nm e t h o dt of e e d b a c kt h es i g n i f i c a t i o no ft h er u l e ，a n dt ob eu s e dt of i n do u tt h o s e r u l e sw h i c ha r eo fh o w e v e rc e r t a i ns i g n i f i c a t i o n ( a l t h o u g ht h o s er u l e sa l ew i t hl o wr e l i a b i l i t y a n ds u p p o r t i n gd e g r e e ) ，a n dt h et e s t i f i c a t i o nh a sb e e nc o n d u c t e db yt h ee x p e r i m e n t a t i o n k e yw o r d s ：d a mm i n i n g ；a s s o c i a t i o nr u l e s ；n e g a t i v ea s s o c i a t i o nr u l e s l v 东北大学碗十学位论文 独创性声明 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加 以标注和致谢的地方外，不包含其他人已经发表或撰写过的研究成果，也不包括本人为 获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论 文中作了明确的说明并表示诚挚的谢意。 学位论文作者签名：了专毛乙 签字h 期：洲、z 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定： 即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查 阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进 行检索、交流。 ( 如作者和导师同意网上交流，请在下方签名：否则视为不间意) 学位论文作者签名：导师签名： 签字日期：签字h 期 东北人学硕：学位论义 第一章弓i 言 1 1 研究背景 第一章引言 随着社会经济的迅速发展和科学技术的全面进步，导致计算机事业飞速发展，以计 算机与通信技术为基础的信息产业正处于蓬勃发展的时期。信息的产生使得人们获得了 火量的数据，而存储在数据库中的数据如何发展和管理昵? 海量的数据背后隐藏着许多 重要的信息，人们希望能够对其进行更高层次的分析，以便更好地利用这些数据。目前 的数据库系统可以高效地实现数据的录入、查询、统计等功能，但无法发现数据中存在 的关系和规则，无法根据现有的数据预钡i 未来的发展趋势。缺乏挖掘数据背后隐藏的知 识的手段，导致了“数据爆炸但知识贫乏”的现象。 计算机技术的一个重要应用领域是人工智能，自1 9 5 6 年诞生之后人工智能取得了 重大进展。经历了博弈时期、自然语言理解、知识工程等阶段，目前的研究热点是机器 学习。机器学习是用计算机模拟人类学习的一门科学，比较成熟的算法有神经网络、遗 传算法、线形规划等。 数据库中的知识发现( k d d ：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 s ) 的产生是由数据库的 管理系统和机器学习方法结合面产生的，也就是用数据库管理系统来存储数据，用机器 学习的方法来分析数据，挖掘大量数据背后的知识。实际上，k d d 是一门交叉性学科， 涉及到很多领域，例如机器学习、模式识别、统计学、智能数据库、知识获取、数据可 视化、高性能计算、专家系统等多个领域。从数据库中发现出来的知识可以用在信息管 理、过程控制、科学研究、决策支持等许多方面。 1 9 8 9 年8 月在美国底特律召开的第l l 届国际人工智能联合会议的专题讨论会上首 次出现k d d h l 这个术语。随后在1 9 9 1 年、1 9 9 3 年和1 9 9 4 年都举行k d d 专题讨论会， 汇集来自各个领域的研究人员和应用开发者，集中讨论数据统计、海量数据分析算法、 知识表示、知识运用等问题。随着参与人员的不断增多，k d d 国际会议发展成为年会。 1 9 9 8 年在美国纽约举行的第四届知识发现与数据挖掘国际学术会议不仅进行了学术讨 论，并且有3 0 多家软件公司展示了他们的数据挖掘软件产品，不少软件已在北美、欧 洲等国得到应用。 数据挖掘是k d d 最核心的部分，是采用机器学习、统计等方法进行知识学习的阶 东北大学硕士学位论文 第一章引言 段。数据挖掘算法的好坏将直接影响到所发现知识的好坏。目前大多数的研究都集中在 数据挖掘算法和应用上。人们往往不严格区分数据挖掘和数据库中的知识发现，把两者 混淆使用。一般在科研领域中称为k d d ，而在工程领域则称为数据挖掘”。 1 2 数据挖掘的任务 数据挖掘的任务是从数据中发现模式i 引。对于模式，通常采用如下的定义：模式是 一个用语占l 来表示的一个表达式e ，它可用来描述数据集f 中数据的特性，e 所描述 的数据是集合f 的一个子集f e 。e 作为一个模式要求它比列举数据子集f e 中所有元素 的描述方法简单。例如，“如果成绩在8 1 9 0 之间，则成绩优良”可称为一个模式，而 如果成绩为8 l 、8 2 、8 3 、8 4 、8 5 、8 6 、8 7 、8 8 、8 9 或9 0 ，则成绩优良”就不能称之 为一个模式。 模式有很多种，按功能可分有两大类：预测型( p r e d i c t i v e ) 模式和描述型( d e s c r i p t i v e ) 模式。 预测型模式是可以根据数据项的值精确确定某种结果的模式。挖掘预测型模式所使 用的数据也都是可以明确知道结果的。例如，根据各种动物的资料，可以建立这样的模 式：凡是胎生的动物都是哺乳类动物。当有新的动物资料时，就可以根据这个模式判别 此动物是否是哺乳动物。 描述型模式是对数据中存在的规则做一种描述，或者根据数据的相似性把数据分 组。描述型模式不能直接用于预测。例如，在地球上，7 0 的表面被水覆盖，3 0 是土 地。 1 3 数据挖掘的具体任务及其应用 数据挖掘是由大多数大型零售商面临的决策支持( d e c i s i o ns u p p o r t ) i h q 题所促使产生 的。条形码( b 觚c o d e ) 技术的进步使得零售商有能力收集和储存大量的销售数据，称为 购物篮( b a s k e t ) 数据。一条记录通常是由交易( t r a n s a c t i o n ) 数据和交易中所买的项( i t e m ) 一 一即物品组成。更通常的是，数据记录也包含了客户号( c u s t o m e r - i d ) ，特别当买主是持 有信用卡或商店优惠卡的顾客时。 由于条形码技术的发展，零售部门可以利用前端收款机收集存储大量的售货数据。因 此，如果对这些历史事务数据进行分析，则可对顾客的购买行为提供极有价值的信息。例 如，可以帮助如何摆放货架上的商品( 如把顾客经常同时买的商品放在一起) 帮助如何规 - - 2 - - 垄垄查兰竺主竺竺垒兰 里二兰二坐二 划市场( 怎样相互搭配进货) 。由此可见，从事务数据中发现关联规则并以此为基础挖掘出 序列模式，对于改进零售业等商业活动的决策非常重要。 关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。它在数据挖掘中是 一个重要的课题，最近几年已被业界所广泛研究。关联觌贝i j 挖掘的一个典型例子是购物 篮分析。关联规则研究有助于发现交易数据库中不同商品( 项) 之间的联系，找出顾客 购买行为模式，如购买了某一商品对购买其他商品的影响。分析结果可以应用于商品货 架布局、货存安排以及根据购买模式对用户进行分类。 1 4 数据源的形式 我们给定一个由客户交易( c u s t o m e rt r a n s a c t i o n ) 组 的大型数据库，每个交易 ( t r a n s a c t i o n ) 由客户( c u s t o m e r - i d ) ，交易时间( 咖s a c t i o n t i m e ) 以及在交易中购买的项 ( i t e m ) 组成。同一个顾客在一个交易时间只能进行一次交易( 这是显而易见的) ，我们不去 考虑顾客在一次交易中所购买物品的数量，每种物品( 也就是商品) 都由一个二进制变量 代替，而不管它是否在交易中被购买与否。以这种形式组织的源数据库见表1 1 。 表1 1 以客户号( c u s i _ l d ) 及交易时间( 1 协t i m e ) 排序的源数据库 t a b l e1 1t h es o u r c ed a t a b a n kc o n s t r u c t e d a c c o r d i n g t o c u s t - i da n d t r a n t i m e 客户号( c u s t _ i d )交易时间( t r a n _ t i m e l物品( i t e m l 1j u n e2 5 9 9 3 0 1j u n e3 0 9 9 9 0 2j u n e1 0 9 91 0 2 0 2j u n e1 5 9 93 0 2j u n e2 0 9 9 4 0 6 0 。7 0 3j u n e2 5 9 9 3 0 ，5 0 ，7 0 4j u n e2 5 9 93 0 4j u n e3 0 9 9 4 0 ，7 0 4 j u l y2 5 9 9 9 0 5 j u n e1 2 9 99 0 1 5 数据挖掘的商业定义 东北大学硪士学位论文 菇一章j 言 划市场( 怎样相互搭配进货) 。由此可见，从事务数据中发现关联规则并以此为基础挖掘出 序列模式，对于改进零售业等商业活动的决策非常重要。 关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。它在数据挖掘中是 一个重要的课题，最近几年已被业界所广泛研究。关联规则挖掘的一个典型例予是购物 篮分析。关联规则研究有助于发现交易数据库中不同商品( 项) 之问的联系，找出顾客 购买行为模式，如购买了某一商品对购买其他商晶的影响。分析结果可以应用于商品货 架布局、货存安排以及根据购买模式对用户进行分类。 1 4 数据源的形式 我们给定一个由客户交易( c u s t o m e rt r a n s a c t i o n ) 组成的大型数据库，每个交易 f t r a n s a c t i o n ) 由客户号( c u s t o m e r - i d ) ，交易时间( t r a n s a c t i o n - t i m e ) 以及在交易中购买的项 ( i t e m ) 组成。i 刊一个顾客在一个交易时问只能进行一次交易( 这是显而易见的) ，我们不去 考虑顾客在一次交易中所购买物品的数量，每种物品( 也就是商品) 都由一个二进制变量 代替，而不管它是否在交易中被购买与否。以这种形式组织的源数据库见表11 。 表1 1 以客户号( c u s t _ i d ) 及交易时间舶一t i m e ) 排序的源数据库 t a b l ei 1t h e $ o u t c e d a t a b a a kc o n s t r u c t e d a c c o r d i n g t o c u s t i da n d t r a i t t i m e i 客户号( c u s ti d )交易时间( t r a n _ t i m e )物品( i t e m ) ： j u n e2 57 9 93 0 j u n e3 0 9 99 0 2j u n e1 0 9 91 0 2 0 2j u n e1 5 9 9 3 0 2 j u n e2 0 9 94 0 6 0 7 0 3j u n e2 5 9 9 3 0 ，5 0 ，7 0 d j u n e2 5 9 93 0 4 j u n e3 0 9 9 4 0 ，7 0 4 j u l y2 5 9 99 0 5j u n el 2 9 99 0 1 5 数据挖掘的商业定义 1 5 数据挖掘的商业定义 垄垄查兰竺主竺竺垒兰 里二兰二坐二 划市场( 怎样相互搭配进货) 。由此可见，从事务数据中发现关联规则并以此为基础挖掘出 序列模式，对于改进零售业等商业活动的决策非常重要。 关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。它在数据挖掘中是 一个重要的课题，最近几年已被业界所广泛研究。关联觌贝i j 挖掘的一个典型例子是购物 篮分析。关联规则研究有助于发现交易数据库中不同商品( 项) 之间的联系，找出顾客 购买行为模式，如购买了某一商品对购买其他商品的影响。分析结果可以应用于商品货 架布局、货存安排以及根据购买模式对用户进行分类。 1 4 数据源的形式 我们给定一个由客户交易( c u s t o m e rt r a n s a c t i o n ) 组 的大型数据库，每个交易 ( t r a n s a c t i o n ) 由客户( c u s t o m e r - i d ) ，交易时间( 咖s a c t i o n t i m e ) 以及在交易中购买的项 ( i t e m ) 组成。同一个顾客在一个交易时间只能进行一次交易( 这是显而易见的) ，我们不去 考虑顾客在一次交易中所购买物品的数量，每种物品( 也就是商品) 都由一个二进制变量 代替，而不管它是否在交易中被购买与否。以这种形式组织的源数据库见表1 1 。 表1 1 以客户号( c u s i _ l d ) 及交易时间( 1 协t i m e ) 排序的源数据库 t a b l e1 1t h es o u r c ed a t a b a n kc o n s t r u c t e d a c c o r d i n g t o c u s t - i da n d t r a n t i m e 客户号( c u s t _ i d )交易时间( t r a n _ t i m e l物品( i t e m l 1j u n e2 5 9 9 3 0 1j u n e3 0 9 9 9 0 2j u n e1 0 9 91 0 2 0 2j u n e1 5 9 93 0 2j u n e2 0 9 9 4 0 6 0 。7 0 3j u n e2 5 9 9 3 0 ，5 0 ，7 0 4j u n e2 5 9 93 0 4j u n e3 0 9 9 4 0 ，7 0 4 j u l y2 5 9 9 9 0 5 j u n e1 2 9 99 0 1 5 数据挖掘的商业定义 叁垄查兰堡生兰堡垒茎 一墨二至三! 羔 从商业应用角度看，数据挖掘是一种崭新的商业信息处理技术。其主要特点是对 商业数据库中的大量业务数据进行抽取、转化、分析和模式化处理，从中提取辅助商业 决策的关键知识，即从一个数据库中自动发现相关商业模式。实际上多年前，统计学家 就开始手工挖掘数据库，从数据库中寻找符合统计学规律的有意义的模式。这也是统计 学类型的数据挖掘技术，是目前数据挖掘技术最为成熟的重要原因之一。 数据挖掘是利用统计学和机器学习的技术，探求那些符合市场、客户行为的模式。 目前，数据挖掘已经可使挖掘技术自动化，将数据挖掘与商业数据仓库相结合，以适当 的形式将挖掘结果展示给企业经营管理人员。对于数据挖掘的应用不仅依靠良好的算法 建立模型，而且更重要的是要解决如何将数据挖掘技术集成到当今复杂的信息技术应用 环境中。其次，还要有数据挖掘分析人员参与，因为数据挖掘技术不具备人所特有的经 验和直觉，不能区分哪些挖掘出的模式在现实中是有意义的，哪些是无意义的。因此， 数据挖掘分析人员的参与是必不可少的。 简而言之，数据挖掘是一类深层次的数据分析。数据分析本身已经有很多年的历史， 只不过以往数据挖掘收集和分析的目的是用于科学研究，而且限于当时计算能力的限 制，对大数据量进行分析的复杂数据分析方法无法得到实际的应用。现在，由于业务处 理自动化系统的实现，在商业领域中生成了大量的业务数据。这些数据并不是为了分析 的目的而收集的，而是由于业务处理操作而获取、积累的。面对这些数据，所有企业都 面临一个共同的问题：企业所积累的数据量越来越大，但其中能被企业直接利用的真正 有价值的信息却很少。因此从大量的数据中经过深层次分析，获得有利于商业运作、提 高商业竞争力的信息，就像从矿石中发掘金子一样困难。数据挖掘可以描述成：按企业 既定业务日标，对大量的企业数据进行探索和分析，揭示隐藏的、未知的或验证己知的 商业规律，且迸一步将其模式化的数据处理方法。它最吸引人的地方就是能够建立预测 模型而不是回顾型的模型。将数据挖掘工具与传统的数据工具进行比较，可以发现传统 数据分析工具的分析重点在于向管理人员提供过去已经发生什么，描述过去的事实。例 如，下个月的市场需求情况怎样，或者某些客户为什么会转向竞争对手。分析的目的也 不同，前者是为了从过去的事实中列出管理人员感兴趣的事实。例如，哪些是公司最大 的客户。而后者则是要找出未来可能成为公司最大的客户。从两者进行分析时所需要的 数据量看，也有明显的差异，前者需要的数据量并不很大，而后者则需要海量数据才能 运行。两者的启动方式也有较大的差别，前者主要依靠各种人员启动，后者则依靠数据 东北人学硕i j 学位诠殳 第一章引言 本身和系统来启动。当然，前者的技术已经相当成熟，而后者除统计分析外，其他的工 具则处于发展阶段中。 1 6 数据挖掘与数据仓库关系 根据数据挖掘的定义可以看出，数据挖掘包含一系列旨在从数据库中发现有用而未 发现的模式的技术，如果将其与数据仓库紧密联系在一起，将获取意外的成功。传统的 观点认为数据挖掘技术扎根于计算科学和数学，不需要也不得益于数据仓库。这种观点 并不正确，成功的数据挖掘的关键之一就是通过访问萨确、完整和集成的数据，才能进 行深层次的分析，寻求有益的信息。而这些正是数据仓库所能提供的，数据仓库不仅是 集成数据的一种方式，而且数据仓库的联机分析功能o l a p 还为数据挖掘提供了一个 极佳的操作平台。如果数据仓库与数据挖掘能够实现有效的联结，将会给数据挖掘带来 各种便利和功能。 首先，由于大多数数据挖掘工具要在集成的、一致的、经过清理的数据上进行挖掘。 这就需要在数据挖掘中有一个昂贵的数据清理、数据变换和数据集成过程，作为数据挖 掘的预处理。而已经完成数据清理、数据变换和数据集成的数据仓库，完全能为数据挖 掘提供它所需要的挖掘数据。使数据挖掘免除了数据准备的繁杂过程。 其次，在数据仓库的构造过程中已经围绕数据仓库组建了包括数据存取、数据集成、 数据合并、异种数据库的转换、o d b c o l e d b 、w e b 访问和服务工具以及报表与o l a p 分析工具等全面的数据处理和数据分析基础设旌。在数据挖掘过程中所需要的数据处理 与分析 ：具完全可在数据仓库的数据处理与数据分析工具中找到，根本没有必要为数据 挖掘重新设置同样的基础设施。 此外，在数据挖掘过程中，常常需要进行探测式的数据分析，穿越各种数据库，选 择相关数据，对各种数据选择不同的粒度，以不同的形式提供知识或结果。而数据仓库 中的o l a p 完全可以为数据挖掘提供相关的数据操作支持，例如，对数据立方体或数据 挖掘中间结果进行数据的下钻、上卷、旋转、过滤、切块或切片，且以o l a p 的可视化 功能为数据挖掘过程或挖掘结果提供良好的操作平台，这些都将极大地增强数据挖掘地 功能和灵活性。 最后，在数据挖掘过程中，如果将数据挖掘与数据仓库进行有效地联结，将增加数 据挖掘地联机挖掘功能。用户在数据挖掘地过程中，可以利用数据仓库地o l a p 与各种 数据挖掘工具地联结，使用户可以为数据挖掘选择合适地数据挖掘工具，能够在数据挖 东北大学硕士学位论丈 第一章引言 掘过程中灵活地组织挖掘工具以增强数据挖掘能力，同时还为用户灵活地改变数据挖掘 地模式与任务提供便利。 1 7 数据挖掘工具的评价标准 随着数据挖掘技术日益发展的同时，出现了许多数据挖掘工具。如何选择满足需要 的数据挖掘工具，成了数据挖掘应用中首要解决的问题。在选择数据挖掘工具时，一般 可以参照以下标准。 ( 1 ) 模式种类的数量 数据挖掘工具能够提供的模式越多，它的知识发现能力越强；多种类型模式的结合 应用，有助于降低问题的复杂性。例如，可以先用聚类将数据集分组，再在各数据组上 挖掘预测性模式，要比单纯在整个数据集上进行数据挖掘更加有效。 ( 2 ) 解决复杂问题的能力 由于挖掘数据量一般比较大，因此，算法的时空复杂性成为许多挖掘工具实际应用 中的重要限制因素。如果算法的复杂性随着数据量的增大、模式精细度的提高、准确度 要求的增加而呈现指数增长，就将严重限制数据挖掘工具的应用。 为了了解数据挖掘工具解决复杂问题的能力大小可从挖掘工具的模式应用、数据 选择和转换能力、可视化程度、扩展性等方面考察。 多种类别模式的结合使用往往有助于发现有用的商业模式，降低问题的复杂性。特 别是与分类有关的模式，可用不同的算法来实现，以适应不同的需求环境。数据挖掘工 具如果能够提供多种途径产生同种模式，可以提高其解决复杂问题的能力。 数据选择和转换能力对挖掘工具解决复杂问题能力的影响也是相当大的。因为知识 模式通常被大量的数据项所隐藏，这些数据有的是冗余的，有的是完全无关的。这些数 据项的存在会影响有价值模式发现的能力。数据挖掘工具的一个很重要功能，就是能够 减低数据的复杂性，提供选择正确数据项和转化数据值的能力，这些能力都将增加数据 挖掘工具解决复杂问题的能力。 可视化工具不仅为用户提供了直观、简洁的数据挖掘方法，方便了用户使用数据挖 掘工具；更重要的是可视化工具有助于用户对重要数据的定位，对模式质量的评价，从 而降低解决复杂问题时建模的难度。 数据挖掘工具的扩展性也是提高挖掘工具解决复杂问题能力的一个重要因素。数据 挖掘工具的扩展性可以提高处理大量数据的效率。这就要在选择数据挖掘工具时了解挖 东北大学顽士学位论文 第一章引言 掘工具能否充分利用硬件资源? 是否支持并行计算? 当处理器的数量增加，计算规模是 否相应增长? 是否支持数据并行存储? 为单处理器的计算机编写的数据挖掘算法不会 在并行计算机上自动以更快的速度运行。为了更好地发挥并行计算机地优点，需要有支 持并行计算机的算法。 ( 3 ) 操作性能 操作性能的好坏是一个影响挖掘工具性能的重要因素。图形界面友好的工具可以方 便用户，引导用户执行任务，为用户节省数据挖掘时间。具有嵌入技术( a p i ) 挖掘工 具能使数据挖掘工具的性能得到提高，应用程序能够嵌入挖掘工具，缩短开发时间。如 果数据挖掘工具能够允许用户通过g u i 、程序设计语言或s q l 语言将模式运用到已经 存在或新增加的数据上，或将模式导出到程序或数据库中，将极大地提高挖掘1 ：具的易 操作性。 ( 4 ) 数据获取能力 数据挖掘工具地使用基础是数据库或数据仓库。因此，一个优秀的数据挖掘工具 可以使用s q l 语句直接从数据库或数据仓库中读取数据，这样可以简化数据准备工作， 并且可以充分利用数据库的优点。没有一种工具可以支持所有类型的数据库或数据仓 库，但应该能够通过通用接口连接大多数流行的数据库或数据仓库，这将提高数据挖掘 工具的使用范围。 ( 5 ) 挖掘结果的输出 数据挖掘工具不仅能够将挖掘结果以多种方式输出，而且要求输出的结果便于用 户的理解与应用。传统的查询工具、可视化工具可以帮助用户理解数据挖掘结果。因此 数据挖掘工具能否提供与传统工具集成的简易途径接口，是衡量数据挖掘工具好坏的标 准。如果这些挖掘结果的输出能够以图形、报告、逻辑公式等可视化方式输出，或以先 验知识方式输出，为今后的数据挖掘提供准备，都能提高数据挖掘工具的性能。 ( 6 ) 噪声数据的处理及挖掘工具的鲁棒性 在许多情况下，数据源都包含噪声，数据挖掘工具应该能对携带噪声的数据进行 挖掘，或对带噪声数据适当处理后也能进行正常的数据挖掘。噪声数据的处理从另一个 角度说明挖掘工具需要具有一定的鲁棒性。从数据挖掘工具的目标看，希望对未知的对 象做出正确的判断，但要求挖掘工具能对所有的对象做出这种预测是不可能的。不过， 数据挖掘工具至少要有一定的数据误差处理能力，能够应对非法输入、内存空问不足能 异常情况。 东北大学硕士学位论文 第一章弓l 鲁 1 8 本文主要内容 本文的组织如下。第二部分引出关联规则的定义和属性、形式和种类等；第三章给 出流行的关联规则的算法以及展望；第四部分介绍了超市中数据的组织；第五部分首先 讨论了负规则，对基于利润约束的关联规则问题给出了描述和解决方法，然后解决超市 中使用关联规则的方法；最后给出本文的结论与未来工作方向。 东北大学顶士学位论文 第二章关联规则挖掘概述 第二章关联规则挖掘概述 关联规则是给定数据集中数据项之间的联系。关联规则的发现是一种非常重要的数 据挖掘类型。 如何使用关联规则进行挖掘? 一个典型的例子是在超市里很多顾客会同时购买某些商品。当顾客购买面包时，其 他顾客也很有可能购买面包。通常零售商希望通过商品之间的关系导致销售增加，例如 在面包附近搭配牛奶；僵是零售商可能没有预期到的顾客想要一起购买的其他商品是什 么? 一个经常被引用的例子是，在美国很多人通常一起购买啤酒和尿布1 2 】。 关联规则最直接的应用就是在电子商务中。网站可以很明显的从强大的关联规则中 的受益。网站可以从数据库中对数据进行挖掘得到关联规则，然后设置顾客有意要一起 购买的捆绑组合。网站也可以使用关联规则设置相应的交叉销售( c r o s s s e l l i n g ) 和向上 销售( u p s e l l i n g ) ，也就是购买某种商品的顾客会看到相关的另外一种商品的广告。 2 1 关联规则的引出 关联规则挖掘问题由r a g m w a l 在1 9 9 3 年首次提出简单的说，关联规则的挖掘就 是在指定的事务数据库d 中发现满足用户提出的最小支持度和最小可信度的规则，后 面将给出关联规则的经典定义。 关联规则的一个典型应用就是用束进行店铺的布局，也就是货篮摆放问题。假定作 为大型超市的经理，可能希望能够通过了解顾客的购物习惯从而采取适当的店面布局策 略来促进销售。例如，哪些商品组合会使顾客会在一次购物时同时购买? 如果从大量销 售数据中发现顾客有购买啤酒的同时也购买面包的购物习愤，那么可以将这两类商品布 置的近一些，以便刺激这些商品共同销售：或者故意将这两类商品放在超市的两端，使 需要购买这些商品的顾客一路走去，从而增加挑选其他商品的机会。 表2 1 是商品代号一商品名称对照表。表2 2 是某超市的零售数据，每行记录一张 售货小票中出现的所有商品代号( 相同商品代号不重复记录，不计销售数量) ，t i d 是 售货小票的序列号。顾客的购物习惯指那些以较高概率出现在同一张小票中的商品组 合。这些商品组合就是对零售数据进行挖掘后得到的关联规则。 东北大学碘士学位论文 第二章关联规则挖掘概述 表2 1 商品代号一商品名称对照表 t a b l e21t h ec o m m o