（计算机应用技术专业论文）基于关联规则的数据挖掘模型smminer的设计与实现.pdf

基于关联规则的数据挖掘模型- - s m - m i n e r 的设计与实现 摘要 f f 数据挖掘是2 0 世纪9 0 年代中期兴起的一项新技术，它是知识发现过程中的关 键步骤，也是当前知识发现领域中的一个研究热点。近年来，国内外学术界和企 业界，都非常重视对数据挖掘技术和软件工具的研究和开发，也取得一些成果。 关联规则的发现是数据挖掘中的一项重要任务。关联规则表示数据库中一组对 象之间某种关联关系的规则( 例如“同时发生”或者“从一个对象可以推出另一 个”) 。关联规则的简单表示形式是：x _ y ，x 称作规则的前提，y 是规则的结果。 通常，对于。个规则的衡量有两个标准：支持度( s u p p o r t ) 和可信度( c o n f i d e n c e ) 。 挖掘关联规则的问题就是找出这样的一些规则：他们的s u p p o r t 和c o n f i d e n c e 分 别大于用户指定的最小s u p p o r t 和最小c o n f i d e n c e 限度。这个问题的主要挑战性 在于数据量巨大( 数据库容量达到若干g b 字节，甚至t b 字节) ，因此算法的效率 是关键。目前研究的重点是如何找出l a r g ei t e m s e t ，围绕这个问题，r a g r a w a l 等在1 9 9 4 年提出了a p r i o r i 算法，它是种经典的频集方法，但是a p r i o r i 算法 也存在一些固有的缺陷：多次重复扫描数据库，增加了挖掘过程中i o 操作的 次数，加重了c p u 的负担，影响计算效率。无法对稀有数据进行分析。l ，。? 本文首先从理论和应用两个角度分析了a p r i o r i 算法的局限性，并且针对该算 法的不足，设计了一种新的算法，新的算法：将可信度放在首位，能够对稀有 数据进行分析。扫描数据库一次，将数据库中的交易信息转换成位图结构体， 以后的挖掘都以该位图结构体为基础，这样就避免过多地扫描数据库，减轻了系 统的i o 负载，获得较好的计算效率。 然后，根据新的挖掘算法，结合超市日常零售业务的实际情况，设计了面向超 市行业的数据挖掘模型s m - m i n e r ，在挖掘模型s m - m i n e r 的实现过程中，运用支持 多平台的j a v a 开发语言，采用了面向对象的设计和开发方法。同时，在知识的表 达和解释机制方面也作了很多工作，使知识的表达不仅限于数字和符号，而是更 容易理解的表格、图形等。 最后，总结出设计挖掘算法和挖掘模型的方法，为将来超市行业数据挖掘系统 的设计和研究提供了一种新思路。 ( s m - m i n e r 挖掘模型以大型超市为行业背景，功能完善，操作简单，可扩展性 基于关联规则的数据挖掘模型一s m m i n e r 的设计与实现 强。同时，s m - m i n e r 挖掘模型在二次开发上并不受行业限制，通过分析具体的行 、 业领域数据，本模型完全可以应用到银行、保险、气象等其它行业中。- 声7 关键字数据挖掘i 关联规则，a p r i o r i 算法j i i 垂戛两多一， 基于关联规则的数据挖掘模型一s m m i n e r 的设计与实现 a b s t r a c t a san b w t e c h n o l o g yb o o m e d i nt h em i d - 1 9 9 0 s d a t am i n i n gr e p r e s e n t sak e ys t e pj n t h ep r o c e d u r e so fk n o w l e d g e d i s c o v e r i n ga n di sa l s oah o tr e s e a r c ht o p i ci nt h ed o m a i no f k n o w l e d g ed i s c o v e r i n g 1 nr e c e n ty e a r s t h ea c a d e m i c c i r c l ea n de n t e r p r i s e sh a v ea t t a c h e d i m p o r t a n c et oa n da c h i e v e ds o m er e s u l 协i nt h er e s e a r c ha n dd e v e l o p m e n to ft h ed a t a m i n i n gt e c h n i q u e sa n ds o f t w a r et 0 0 1 t h ed i s c o v e w o fa s s o c i a t i o nr i l l i ei sa ni m p o r t a n t 协s k j nd a t am i m i n g a s s o c i a t i o nr u l er e p r e s e n t ss o m ea s s o c i a t i o nr e l a t i o n sr u i eb e t w e e nas e t o fo b j e c t s ( f o r e x a m p l e c o r c u r r e n u yh a p p e n e d 。o r d e d u c e f r o mo n eo b j e c tt oa n o t h e r ) i t c a nb e s i m p l i f i e d a s x = y x i s t h e p r e m i s e o f t h er u l e 。y t h er e s u l t g e n e r a l l y , t h e r e a r e t w o s t a n d a r dt om e a s u r ear u l e ：s u p p o r ta n dc o n f i d e n c e t h es t u d yo fm i n i n ga s s o c i a t i o nr u l e a i m st of i n dt h ef o i l o w i n gr u l e a ：t h e i rs u p p e da n dc o n f i d e n c ea r em o r et h a nt h eu s e r 。s m i n i m u m r e s p e c t i v e l y t h e d i f f c u i t y o f t h er e s e a m h i i e s n t o o l a r g e a m o u n t s o f d a t a ( s e v e r a i g b b y t eo re v e nt bb y t e ) a n dt h e r e f o r et h ee f f i c i e n c yo fa l g o r i t h mi st h ek e y t h ec u r r e n t r e s e a r c hp i e c e si t se m p h a s i so nh o wt od i s c o v e rl a r g ei t e m s e t ，a n dr a g r a w a la n do t h e r s p u tf o r w a r dt h ea p d o da l g o r i t h mi n1 9 9 4 ni sac l a s s i cf r e q u e n t s e tm e t h o db u ti th a si t s i n h e r e n td e f a u i t s ：1r e p e a t e ds c a n n i n go fd a t a b a s ei n c r e a s e dt h ei i ot i m e si nm i n i n g t h u s a d d i n gt o c p u sb u r d e na n da k e c n gt h ec o m p u t i n ge t r m i e n c y 2c a n n o ta n a l y z et h e s c a r c ed a t a t h i s p a p e ra n a l y s e s t h e a p f i o da l g o r i t h m f r o mt h et h e o r e t i c a la n d p r a c t i c a l p e r s p e c t i v e sa n d t om a k e u p f o ri t sd e f i c i e n c yd e s i g n san e wa l g o r i t h m 。w h i c hm e a n s ：1 t h ep r i o r i t yi sg i v e nt oc o n f i d e n c es oa st oa n a l y z et h es c a r c ed a t a 2 t h ed a t a b a s ei s s c a n n e do n l yo n c et ot r a n s f o r mt h et r a n s a c t i o ni n f o r m a t i o no ft h ed a t a b a s et o b i t c o n s t r u c t u r e 。w h i c hw i l ib et h eb a s i so f t h ef o l k ，w i o gm i n j n g ta n d t h u sa v o i d i n gu n n e c e s s a r y d a t a b a s es c a n n i o gs oa st oe a s et h e1 1 0b u r d e no ft h es y s t e ma n da c h i e v eab e t t e r e f f i c i e n c y b a s e do nt h en e wm i n ea l g o r i t h ma n dt a k i n gt h ed a i l y r e t a i lb u s i n e s so ft h e s u p e m l a r k e t si n t oc o n s i d e r a t i o n ，t h ea u t h o rd e s i g n sas u p e r m a r k e t - o r i e n t e dd a t am i n i n g m n d e l ：s m - m i n e r i nt h er e a l i z a t i o no ft h em i n i o gm o d e io fs m - m i n e r ，t h ea u t h o r e m p l o y sj a v ad e v e l o pl a n g u a g ew h i c hs u p p o r tm u 撼口l a 怕n n a n dt h eo b j e c t - o r i e n t e d m e t h o do fd e s i g n i n ga n dd e v e l o p i n g m e a n w h i l e ，t h ea u t h o rh a sw o r k e dal o ti nk n o w l e d g e e x p r e s s i o na n de x p 恼n a d o n t oe n a b i et h a tt h ek n o w l e d g ei sn o to n l yd e m o n s t r a t e db yd i g i t a n ds y m b o lb u t 协b l e sa n dg r a p h i c sw h i c ha r ee a s i l yc o m p r e h e n d e d f i n a l l yt h et h e s i sc o n c l u d e s t h em e t h o do fd e a i g n i o gm i n ea l g o r i t h ma n dm i n em o d e l w h i c hm e a n san e wt r a i no ft h o o g h tf o rt h ed e s i g na n dr e a e a m h o fd a t am i n i n gs y s t e mf o r t h es u p e r m a r k e t s t a k i n gl a r g es u p e r m a r k e t a si t sb a c k g r o u n d s m - m i n e rm i n em o d e li sc h a r a c t e r i z e d b yp e r f e c tf u n c t i o n 。s i m p l eo p e r a t i o n a n ds t r o n ge x t e n s i b i l i t y m e a n w h i l e ，i ti sn o tc o n f i n e di n o n ea r e aw h e nd e v e i o i n e df o rt h es e c o n dt i m e a n db ya n a l y z i n gs p e c i a ld o m a i nd a t a ，t h e m o d a ic a nb e a p p l i e di nt h ei n d u s t r i e so fb a n k i n g ，i n s u r a n c e ，m e t o o r e l o g y ，a n d s oo n z h a n gy o u p i n g ( c o m p u t e r s c i e n c ea n da p p l i c a t i o n ) d i r e c t e db yp r o f y a n gl i p i n g 3 基于关联规则的数据挖掘模型s m m i n e r 的设计与实现 k e y w o r d s ：d a t a m i n i n g ，a s s o c i a t i o nr u l e s ，a p r i o da l g o r i t h m ，c o n f i d e n c e ，s u p p o r t 4 基于关联规则的数据挖掘模型- - s m - m i n e r 的设计与实现 引言 过去几十年，随着关系型数据库技术的发展和数据库的广泛应用，各行各业 积累数据的能力和速度达到了惊人的地步，造成了海量数据的存储。随着商业竞 争的日益加剧，各行各业都意识到必须从现有的历史数据中挖掘隐藏着的信息， 用于分析和决策。例如超级市场的经理人员需要从过去几年的销售记录中分析出 顾客的消费习惯和行为；金融业需要从银行的交易数据中分析客户的信用等级， 从而降低风险、增加收益。然而，多数数据库应用仍只能对数据库进行录入、查 询、统计等简单操作。这样，数据不能转化成有用的知识，用户只能被数据的海 洋所淹没。人们正面临“数据丰富而知识贫乏”的问题，迫切需要找出大量数据 背后隐藏的规则和模式，从而预测未来的趋势。 数据挖掘技术的出现为解决此问题开辟了一条道路。它通过一些专门的算 法，借助计算机强大的运算能力，从浩瀚的数据海洋中揭示出鲜为人知的秘密规 律，从而对未来进行有限和有效的预测。 数据挖掘【l 】( d a t am i n i n g ，3 m ) 技术兴起于八十年代末，在最近几年里数据 挖掘已被数据库界所广泛研究。数据挖掘是从大量的、不完全的、有噪声的、模 糊的、随机的应用数据中，提取出隐含在其中的、人们事先不知道的、但又是潜 在有用的信息和知识的过程。这些信息对预测趋势和决策行为是至关重要的。 但是数据挖掘的效率和可用性一直是个大难题。虽然也有一些特定行业的数 据挖掘系统产品，但是这些产品在挖掘效率和二次开发上都存在很大的缺陷。 众所周知，超市已经成为人们日常生活中必不可缺的部分，每天大量的商 品通过超市进进出出，在这繁忙物流的背后，伴随着大量有用数据的存储。但是 大多数的超市对收银台获取的数据并没有二次利用，在超市行业竞争日益激烈的 今天，从现有销售数据中发现顾客的购买行为，无疑是提高超市自身竞争能力的 重要举措。从2 0 0 2 年4 月开始，在可的超市海运店的大力配合下，在导师的指 导下，设计了“可的超市数据挖掘模型s m - m i n e r ”，该模型采用了新设计的关联 规则算法，保证了挖掘的高效性。另外在模型的实现过程中，采用了j a v a 语言 和面向对象的思想，为挖掘系统的二次开发打下了基础。本论文的撰写正是随着 该项目的开展而完成的。 1 基于关联规则的数据挖掘模型一s m - m i n e r 的设计与实现 本论文分为七章。第一章介绍了数据仓库的基础知识。第二章是对数据挖掘 技术的介绍。在第三章，介绍了一种挖掘技术一关联规则。第四章，对关联规 则挖掘算法进行详细分析并且提出了新的算法。第五、六章重点介绍了s m - m i n e r 的设计方案和相关的开发工作，主要包括总体系统结构设计、数据库设计、数据 模型设计、业务流程、数据流设计和界面风格设计。第七章介绍了面向对象的编 程方法及其在s m - m i n e r 中的具体应用。 2 基于关联规则的数据挖掘模型一s m - m i n e r 的设计与实现 第一章数据仓库简介 当前的数据处理可以大致地刘分为两大类：事务型处理( 又称操作型处理) 和分析型处理( 又称信息型处理) 。事务型处理是指对d b 联机的日常操作，例 如对一个或一组记录的查询和修改，主要为企业日常业务服务。分析型处理则用 于高层管理人员的决策分析，例如d s s 和多维分析，他们通常要访问大量的历史 数据。数据库系统作为数据管理手段，主要用于事务处理。数据仓库则是为了构 建分析型处理环境而出现的一种数据存储和组织技术。 1 1 数据仓库的概念 根据w h i n m o n 关于数据仓库 2 1 ( d a t aw a r e h o u s e ，d w ) 的定义：数据仓库 是一个面向主题的、集成的、时变的、非易失的数据集合，支持管理部门的决策 过程。 1 2 数据仓库的特征 数据仓库的面向主题性。 主题是构成企业经营运作的主要框架或方向，它是在较高层次上对数据进行 归类的标准。每一个主题基本对应一个宏观的分析领域，典型的例子有顾客、产 品、销售等。面向主题的数据组织方式通常是在较高层次上，对数据进行描述， 它能完整、统一地刻画各个分析对象所涉及的企业的各项数据，以及数据之间的 联系。基于应用的数据的组织则完全不同，它的数据只是为处理数据应用而组织 在一起的。按照主题进行数据组织的方式具有更高的数据抽象级别。 数据仓库的集成性。 数据仓库的数据是从原有的分散的数据库中抽取出来的，因此在数据进入数 据仓库之前，必须要经过统一和综合这一步是数据仓库建设中最关键、最复杂 的一步。首先，要统一原始数据中的所有矛盾之处，比如命名约定、编码结构、 属性度量等，还要将原始数据结构作一个从面向应用到面向主题的转换。 数据仓库的稳定性。 数据仓库的数据主要供企业决策分析之用，所涉及的数据操作主要是数据查 3 基于关联规则的数据挖掘模型一s m - m i n e r 的设计与实现 询，一般情况下并不进行更新操作。所以数据仓库管理系统( d 咖s ) 相对d b m s 而言在数据处理上要简单些，如实体完整性、参照完整性等，在数据仓库的管 理中几乎可以省去。数据仓库通常只进行数据的初始化装入和数据访问两种数据 操作。 数据仓库的时变性 它表现在以下几个方面： 首先，数据仓库中的数据驻留期限要远远长于操作型数据库系统中的数据驻 留期限。前者一般在5 1 0 年，而后者的驻留期限通常以天计算，甚至更短。数 据仓库保存数据时限较长是为了适应进行趋势分析的要求。 其次，操作型环境包含当前数据，即在存取时是正确有效的数据；而数据仓 库中的数据都是历史数据。 最后，数据仓库数据的码键结构，隐式或显式地包含时间元素，从而表明了 该数据的历史时期。 1 3 数据仓库的体系结构 数据仓库既是一种结构，也是一种方法。数据和信息从不同的数据源提取出 来，然后把这些数据转化成公共的数据模型并且和仓库中已有的数据集成在一 起。当用户向仓库进行查询时，需要的信息已经准备好了，数据冲突、表达不一 致等问题已经得到了解决，这使得决策查询更容易、更有效。 作为一个系统，数据仓库至少应包括3 个基本的功能部分： 数据获取 这个部分负责从外部数据源获取数据。数据被区分出来，进行数据导入或重 新定义格式等处理后，准备载入数据仓库。 数据存储和管理 这个部分负责数据仓库的内部维护和管理，提供的服务包括数据存储的组 织、数据的维护、数据的分发、数据仓库的例行维护等。 信息访问 信息访问部分属于数据仓库的前端，面向不f 司种类的最终用户，这里主要由 桌面系统的各种工具组成。数据仓库的最终用户在这里提取信息、分析数据集、 4 基于关联规则的数据挖掘模型- - s m - m i n e r 的设计与实现 实旋决策分析，从而能够在竞争中取得优势。进行数据访问的软件工具，主要是 查询生成工具、多维分析工具和数据挖掘工具等。 虽然制造商们迫不及待地推出支持数据仓库的商业产品，但是大多数只是原 有技术或系统的稍加改进，这些系统都有很多局限性。建立个真正通用、有效、 灵活的数据仓库体系结构是十分必要的。在数据仓库的研究中，斯坦福大学的数 据仓库计划提出了一种有普遍代表性的数据仓库体系结构，如图卜1 所示，这是 一个典型的三层数据仓库体系结构。 图1 1 数据仓库的体系结构 底层是数据库服务器，它几乎总是一个关系型数据库系统。底层和中间 层通过o d b c ( 开放数据库连接) 、o l e - d b ( 数据库开放链接和嵌入) 、 j o a c ( j a v a 数据库连接) 等网闯连接程序交换数据。 中间层是o l a p 服务器，其典型的实现方法包括：( i ) 关系o l a p ( r o l a p ) 模型，即扩充的关系d b m s ，它将多维数据上的操作映射为标准的关系操 作；( i i ) 多维o l a p ( 舯l a p ) 模型，一种特殊的服务器，它直接实现多维 数据和操作。 顶层是数据呈现，它包括查询和报告工具、分析工具和数据挖掘工具。 1 4 数据仓库的数据模型 最流行的数据仓库数据模型是多维数据模型。这种模型可以以星型模式、雪 花模式和事实星座模式形式存在。 基于关联规则的数据挖掘模型一s m m i n e r 的设计与实现 星型模式。最常见的模型范例。其中数据仓库包括中心表( 事实表) 和 附属表( 维表) 。这种模式图很像星星爆发，维表围绕事实表显示在射线 上。 雪花模式：雪花模式是星型模式的变种，其中某些维表是规范化的，把 数据进一步分解到附加的表中，形成类似于雪花的形状。 事实星座：多个事实表共享维表，这种模式可以看作星型模式集，因此 也可以称为星系模式。 6 基于关联规则的数据挖掘模型s m m n e r 的设计与实现 第二章数据挖掘技术 2 1 数据挖掘定义 定义：数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的实际应 用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知 识的过程。 数据挖掘是一门交叉学科，受多个学科影响( 见图2 - 1 ) ，包括数据库系统、 统计学、机器学习、可视化、信息科学及其他科学。 图2 - 1 数据挖掘与其它学科的关系 数据挖掘的对象不仅是数据库、数据仓库，而且也可以是文件系统或其它形 式的数据集合，例如t r i m 信息资源。 2 2j 良据挖掘钓过程 数据挖掘过程一般由3 个主要的阶段组成：数据准备、挖掘操作、结果表达 和解释。知识的发现可以描述为这3 个阶段的反复过程，如图2 2 所示： 基于关联规则的数据挖掘模型一s m m i n e r 的设计与实现 图2 - 2 数据挖掘的过程 2 2 1 数据准备 这个阶段又可进一步分成3 个子步骤：数据集成、数据选择和数据预处理。 数据集成将多文件或多数据库运行环境中的数据进行合并处理，解决语义模糊 性、处理数据中的遗漏和清洗脏数据等。数据选择的目的是辨别出需要分析的数 据集合，缩小处理范围，提高数据挖掘的质量。预处理是为了克服目前数据挖掘 工具的局限性。 2 2 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 ) 的数据挖掘。 选择合适的工具 挖掘知识的操作 r 基于关联规则的数据挖掘模型s m - m i n e r 的设计与实现 证实发现的知识 2 2 3 结果表述和解释 根据最终用户的决策目的对提出的信息进行分析，把最有价值的信息区分出 来，并且通过决策支持工具提交给决策者。因此，这一步骤的任务不仅是把结果 表达出来( 例如采用信息可视化方法) ，还要对信息进行过滤处理。如果不能令 决策者满意，需要重复以上数据挖掘的过程。 2 3 数据挖掘的分类 根据挖掘的数据库类型分为：关系的、空间的、时间的、文本的和多媒 体的。 根据挖掘的知识类型分为：关联、聚类和特征化等。 根据所用的技术分为：神经网络、机器学习和统计学等。 根据应用分为：电信、金融、股票和超市等。 2 4 数据挖掘模式 并非所有的数据挖掘模式都是有效的。一个模式是有效的，要满足下面四个 条件： 它易于被人理解 在某种程度上，对于新的或测试数据是有效的 它是潜在有用的 是新颖的 对模式的度量，通常采用： 客观度量( 支持度、可信度) 主观度量 意外( 与用户的理念矛盾) 提供用户可用的策略信息 9 基于关联规则的数据挖掘模型一s m m i n e r 的设计与实现 第三章关联规则基本概念 关联分析1 3 】是为了挖掘出隐藏在数据间的相互关系，从一组给定的数据项以 及交易集合中，分析出数据项集在交易集合中出现的频度关系。使用关联分析方 法挖掘的模式称为关联规则。关联规则揭示了交易数据库中不同商品( 项) 之间 的联系，利用这些规则能够找出顾客的购买行为模式，如：购买了某一商品对购 买其它商品的影响。发现这样的规则可以应用于商品货架设计、促销设计、货存 安排以及根据购买模式对用户进行分类等。 3 1 关联规则典型应用 考察一些涉及许多物品的事务：事务l 中出现了物品甲，事务2 中出现了物 品乙，事务3 中则同时出现了物品甲和乙。那么，物品甲和乙在事务中的出现相 互之间是否有规律可循呢? 在数据库的知识发现中，关联规则就是描述这种在一 个事务中物品之间同时出现的规律的知识模式。更确切地说，关联规则是通过量 化的数字描述物品甲的出现对物品乙出现的影响。 现实中，超级市场利用前端收款机收集存储了大量的售货数据，这些数据构 成一条条的购买事务记录，每条记录存储了事务处理时间、顾客购买的物品、物 品的数量及金额等。这些数据中常常隐含形式如下的关联规则：在购买香烟的顾 客当中，有7 0 的人同时购买了打火机。这种形式的关联规贝很有应用价值， 商场管理人员可以根据这些关联规则更好地规划商场，如把香烟和打火机这样的 商品摆放在一起，能够促进香烟和打火机的销售；或者将香烟和打火机分别摆放 在商场的两端，这样顾客在寻找打火机的过程中就可能购买其他的商品，促进其 他商品的销售。 有些数据不像超市售货数据那样很容易就能看出一个事务是许多物品的集 合，但稍微转换一下思考角度，仍然可以像售货数据一样处理。比如人寿保险， 一份保单就是一个事务。保险公司在接受保险前，往往需要记录投保人详尽的信 息，有时还要到医院做身体检查。保单上记录有投保人的年龄、性别、健康状况、 工作单位、工作地址、工资水平等。这些投保人的个人信息就可以看作销售事务 1 0 基于关联规则的数据挖掘模型一s m m i n e r 的设计与实现 中的物品。通过分析这些数据，可以得到类似以下这样的关联规则：年龄在4 0 岁以上，工作在a 区的投保人当中，有4 5 的人曾经向保险公司索赔过。在这 条规则中，“年龄在4 0 岁以上”是物品甲，“工作在a 区”是物品乙，“向保 险公司索赔过”则是物品丙。可以看出，a 区可能污染比较严重，环境比较差， 导致工作在该区的人健康状况不好，索赔率也相对比较高。 3 2 关联规则的基本概念和问题描述 设i = ( i 。，i 。，i 是二进制文字的集合，其中的元素称为项( i t e m ) 。记 d 为交易( r a n s a e t i o n ) t 的集合，这里交易t 是项的集合，并且t i 。对应每 一个交易有唯一的标识，如交易号，记作t i d 。设x 是个i 中项的集合，如果 x _ c t ，那么称交易t 包含x 。 一个关联规则是形如x j y 的蕴涵式，这里x c l ，y c i ，并且x n y = 。一 般用两个参数来描述一个关联规则的属性： 、( 1 ) 可信度( c o n f i d e n c e ) 设d 中支持物品集x 的事务中，有c 的事务同时也支持物品集y ，c 称 为关联规则x j y 的可信度。简单地说，可信度就是指在出现了物品集x 的事务 t 中，物品集y 也同时出现的概率有多大。如上面所举的香烟和打火机的例子， 该关联规则的可信度就回答了这样一个问题：如果一个顾客购买了香烟，那么 他也购买打火机的可能性有多大呢? 在上述例子中，购买香烟的顾客中有7 0 的人购买了打火机，所以可信度是7 0 。 规则x j y 在交易集d 中的可信度是指包含x 和y 的交易数与包含x 的交易 数之比，它反应了关联规则的最低可靠度，记为c o n f i d e n c e ( x = “) ，即 c o n f i d e n c e ( x = = y ) = ff t ：x u y c t ，t d f f t ：x _ c t ，t d l 1 d i ：表示d 的长度。 ( 2 ) 支持度( s u p p o r t ) 设d 中有s 的事务同时支持物品集x 和y ，s 称为关联规则x j y 的支持 度。支持度描述了x 和y 这两个物品的并集x y 在所有的事务中出现的概率有多 大。如果某天共有1 0 0 0 个顾客到商场购买物品，其中有1 0 0 个顾客同时购买了 香烟和打火机，那么上述关联规则的支持度就是1 0 。 1 1 基于关联规则的数据挖掘模型s m m i n e r 的设计与实现 规则x j y 在交易数据库d 中的支持度( s u p p o r t ) 是交易集中包含x 和y 的交易数与所有交易数之比，它表示了一组物品集在统计意义上需满足的最低 程度，记为s u p p o r t ( x y ) ，即 s u p p o r t ( x = j y ) = f ( t ：x u yc t ，t e d ) f f d f 给定一个交易集d ，关联规则挖掘问题就是产生支持度和可信度分别大于用 户指定的最小支持度( m i n s u p p ) 和最小可信度( m i n c o n f ) 的关联规则。 表3 - 1 可信度、支持度的计算公式 可信度是对关联规则准确度的衡量，支持度是对关联规则重要性的衡量。 支持度说明了这条规则在所有事务中有着多大的代表性，显然，支持度越大， 关联规则就越重要。有些关联规则可信度虽然很高，但支持度却很低，说明该关 联规则实用的机会很小，一般而言不重要，但是在某些情况下可能会很重要。 3 3 关联规则价值衡量的方法 当我们用数据挖掘的算法得出了一些结果之后，数据挖掘系统如何知道哪些 规则对于用户来说是有用的、有价值的? 这里有两个判断标准：系统客观的层面 和用户主观的层面。 3 3 1 系统客观层面： 很多的算法都使用“支持度一可信度”的框架。使用“支持度一可信度”的框 架时，时常会产生一些没有价值甚至是错误的规则。看下面的例子： 表3 2 咖啡与牛奶购买关系表 基于关联规则的数据挖掘模型s m m i n e r 的设计与实现 由表格，我们可以了解到如果设定最小支持度m i n s u p p ( s ) 和最小可信度 m i n c o n f ( c ) 分别为0 2 和0 6 ，按照定义得到关联规则： 买牛奶j 买咖啡( s = 2 0 1 0 0 = o 2 ，c = 2 0 2 5 = 0 8 ) 即8 0 的人买了牛奶就会买咖啡。但从表中，我们同时也可以得到：“9 0 9 6 的 人肯定会买咖啡”。换句话说，买牛奶这个事件对于买咖啡这个事件的刺激作用 ( 8 0 ) 并没有想象中的( 9 傩) 那么大。反而是规则： 买咖啡j ( 不) 买牛奶( s = 7 0 1 0 0 = 0 7 ，c = 7 0 9 0 = 0 7 8 ) 更为精确。 因此，基于支持度一可信度的关联规则的评估体系存在着问题。 为避免生成“错觉”的关联规则，通常需要引入“期望可信度一作用度”框 架，用来修剪无用的规则。 ( 1 ) 期望可信度( e x p e c t e dc o n f i d e n c e ) 设t 中有e 的事务支持物品集y ，e 称为关联规则x j y 的期望可信度。 期望可信度描述了在没有任何条件影响时，物品集y 在所有事务中出现的概率有 多大。如果某天共有1 0 0 0 个顾客到商场购买物品，其中有2 0 0 个顾客购买了香 烟，则上述的关联规则的期望可信度就是2 0 。 ( 2 ) 作用度( l i f t ) 作用度是可信度与期望可信度的比值。作用度描述物品集x 的出现对物品 集y 的出现有多大的影响。因为物品集y 在所有事务中出现的概率是期望可信 度；而物品集y 在物品集x 出现的事务中出现的概率是可信度，通过可信度对 期望可信度的比值反映了在加入“物品集x 出现”这个条件后，物品集y 的出 现概率发生了多大的变化。在上例中作用度就是7 0 2 0 = 3 5 。 给定关联规则x j y 和交易集d ，该关联规则的作用度( 提高率) i = s ( x y ) s ( x ) s ( y ) 其中，s ( x ) 为x 在交易集中的支持度。 当i i 。 1 时( i 。为最小兴趣度，类似予最小支持度的定义) ，规则是有意义 的；当o d ，x = e ，x _ a ，x = c ，x - f ， x = b 然后开始挖掘两位的规则： ( 】) 首先从x = d 开始挖掘两位的规则，如x = d a 。 删除所有d 列中数值等于0 的记录行，生成新的结构体数据，如表4 - - 5 所示： 2 0 基于关联规则的数据挖掘模型s m m i n e r 的设计与实现 表4 5 删除d 列中数值等于0 的记录后的结构体 删除s l i m 行中数值小于2 的列，使挖掘范围进一步缩小，得到新的数据 如表4 - - 6 所示： 表4 6 删除s u m 行中数值小于2 的列之后的结构体 得到两位的规则：x = d f ，x = d b ( 即：x = 肋) 依此为基础，进一步挖掘三位的规则： 一从x = d f 开始，数据如表4 - 7 所示 表4 7 挖掘两位规则的结构体 观察上表，删除s u m 行中数字小于2 的列，缩小搜索范围，在这张表中， 所有的s l i n l 值都大于等于2 ，因此有规则：x = d f b ( 即：x = b d f ) 一然后从x = d b 开始挖掘，因为x = d f 已经挖掘过了，所以将f 列从数据 中删除，缩小挖掘范围，删除后的数据如表4 8 所示： 表4 8 删除f 列之后的数据结构体 因为数据结构体仅剩下d 、b ，所以不存在元素进一步进行挖掘，从x - d 开始的挖掘到此停止，算法返回，再从x - e 开始挖掘。 ( 2 ) 从x = e 开始挖掘两位的规则，如x ： e a 。 基于关联规则的数据挖掘模型一s m ，m i n e r 的设计与实现 因为含有d 的所有规则已经挖掘完毕，所以删除d 列，使挖掘范围进一 步缩小。删除后的数据如表4 - 9 ： 表4 - 9 删除d 列之后的数据 删除所有e 列中数值等于0 的记录行，删除后的数据如表4 - 1 0 所示，可 以看出，数据缩小范围相当大。 表4 1 0 删除e 列中数值等于0 的行之后的数据 删除s u m 行中数字小于2 的列c ，缩小搜索范围，结果如表4 - i1 所示： 表 i l 删除s u m 行中数值小于2 的列之后的结构体 观察上表，得到两位的规则：x = e a 、x = e f 、x = e b 。 进步挖掘三位的规则： 一从x = e a 开始 从x = e a f ? 开始，得到数据如表4 - 1 2 所示： 基于关联规则的数据挖掘模型- - s m - m i n e r 的设计与实现 表4 1 2 挖掘3 位规则时的结构体 观察上表，e a f 列在s u m 行中的数值大于等于2 ，因此得到规则： x = e a f ( x = a e f ) 。 进一步挖掘四位的规则：x = e a f b ? e a f b 列s u m 行数值大于等于2 ，因此x = e a f b ( x _ a b e f ) 成立。 x = e a b ? f 已经挖掘过了，因此从数据结构中删除f 列。得到新的数据结构体， 如表4 - 1 3 所示： 表4 一1 3 删除后的结构体 通过观察，s u m 行中的数值都大于等于2 ，因此规则x = f a b ( x = a b e ) 成立。 从x = e f 开始 a 相关的规则已经挖掘完毕，因此将a 列删除，得到数据如表4 一1 4 所示： 表4 - 1 4 删除a 列后的结构体 观察上表s u m 行，规则x = e f b ( x ： b e f ) 成立。 一从x = e b 开始 关于f 的规则已经挖掘完毕，删除f 列，得到数据如表4 一1 5 所示。 基于关联规则的数据挖掘模型一s m m i n e r 的设计与实现 表4 1 5 删除f 列之后的数据结构体 观察上表，朗列s u m 行中的数据大于等于2 ，因此规则x = e b 成立。 ( 3 ) 按照相同的方法，依次挖掘x = a ? 、x ： c ? 、x = f ? 、x i b ? 为首的规则， 得到：x = a bx = a cx = a fx = b cx - - b fx = c fx = a b cx - a b fx = b c f ( 4 ) 综合前面3 个步骤得到的所有规则，得到规则集： x = a ，x = b ，x = c ，x = d ，) 【_ e ，x = f x - a bx _ a cx = a ex = a fx _ b cx - 叻x = b ex = b fx = c fx - - d fx = e f x = a b cx = a b ex = b fx = a e fx = b c fx = b d fx = b e f x = a b e f ( 5 ) 加入m i n s u p p 限制，删除支持度小于m i n s u p p 的规则 (