（计算机软件与理论专业论文）基于矩阵的关联规则挖掘算法的设计与实现.pdf

山东大学硕士学位论文 摘要 数据挖掘技术是解决数据丰富而知识贫乏的有效途径，当属信息科学领域的 前沿研究课题之一，有关的研究和应用极大提高了决策支持的能力，它已被公认 为是数据库研究中一个极富应用前景的领域。本文描述了数据挖掘的概念、功能， 数据挖掘系统的结构与分类，以及数据挖掘与传统数据分析工具和机器学习的区 别。在众多的数据挖掘算法中，基于关联规则的挖掘是一个重要的研究内容。 自a g r a w a lr 等人在1 9 9 3 年提出关联规则的概念，并在1 9 9 4 年提出挖掘关联规 则的经典a p r i o r i 算法之后，有好多学者对其进行了研究并提出了一些新的算法。 本文在对关联规则挖掘问题研究和总结的基础上，对现有的关联规则挖掘 算法进行了分类，深入地分析和探讨了一些典型的关联规则挖掘算法，如a i s 算 法、a p r i o r i 算法及基于划分、基于采样、基于哈希等对该算法的一些改进算法、 f p g r o w t h 算法、d l g 算法等，指出了这些算法的优缺点。同时提出了基于矩阵 的挖掘关联规则的a b m 算法，并将该算法与经典的发现频繁项集的算法进行了 比较，该算法只需要扫描数据库一遍，不需要产生候选集，并且存放辅助信息所 需要的空间也要少。作者在w i n d o w s2 0 0 0 环境下用d e l p h i 6 实现了经典的a p r i o r i 算法和a b m 算法，根据实验结果对这两个算法进行了分析和比较。 现有的许多挖掘关联规则的算法多是针对历史静态数据库的，而对于关联 规则的更新维护问题的研究却比较少。由于应用中的数据库极其巨大，不仅需要 设计高效的算法来挖掘关联规则，而且也需要设计高效的算法来更新维护己开采 出来的规则。本文讨论了事物数据库d 或支持度s 发生变化时关联规则的更新问 题，针对这一问题，提出了两种算法d u a 和u b m 算法，这两种算法的核心问 题在于如何更好的维护旧的关联规则以及利用已有的结果发现新的关联规则。 作为数据挖掘的一个重要课题，关联规则的挖掘研究在各个方面都取得了 山东大学硕士掌位论文 很大的进步，然而，有一种很有用的重要关联规则形式在存在的关联规则挖掘框 架中还没有被发现，如规则：如果m m 和s u n 的股票价格上涨，则微软的第二 天上涨，四天后下跌的可能性是8 0 。与传统的关联规则相比，该规则更有意义， 我们称该规则为事务间关联规则。本文描述了事务问关联规则的有关定义，并给 出了挖掘1 维事务间关联规则的挖掘过程。 关键字：数据挖掘、关联规则、a p r i o r i 算法、关联规则更新、事物间关联规则 山东大学硕士学位论文 a b s t a c t d a t am i n i n gt e c h n o l o g yi sa ne f f e c t i v e a p p r o a c ht o r e s o l v et h ep r o b l e mo f a b u n d a n td a t aa n ds c a n t yi n f o r m a t i o ni tc u r r e n t l yi st h er e s e a r c hf r o n t i e rw i t h i nt h e i n f o r m a t i o ns c i e n c ef i e l dt h er e l a t e dr e s e a r c h e sa n d a p p l i c a t i o n s h a v e g r e a t l y i m p r o v e dt h ea b i l i t yf o rd e c i s i o ns u p p o r t i n gi t h a sb e e nd e e m e dt oaf i e l dt h a th a s b r o a dp r o s p e c to fa p p l i c a t i o ni nd a t a b a s er e s e a c ht h i sp a p e rd e s c r i b e st h ec o n c e p t i o n ， f u n c t i o no fd a t am i n i n g ，t h ef r a m e w o r ka n dc l a s s i f i c a t i o no fd a t am i n i n gs y s t e m ，t h e d i f f e r e n c eb e t w e e nd a t a m i n i n g a n dt r a d i t i o n a l d a t a - a n a l y z i n gi m p l e m e n t ，t h e d i f f e r e n c eb e t w e e nd a t am i n i n ga n dm a c h i n el e a r n i n g ，t h e a p p l i c a t i o ni nm a n y a l g o r i t h m sa b o u td a t am i n i n g ，t h em i n i n gb a s e do r l a s s o c i a t i o nr u l e si sa ni m p o r t a n t r e s e a r c ha s p e c t s i n c ea g r a w a lre t cp u tf o r w a r dt h ec o n c e p to fa s s o c i a t i o nr u l ei n 19 9 3a n db r o u g h tf o r w a r dt h ec l a s s i c a la p r i o r ia 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 i n19 9 4 ，m a n ys c h o l a r sh a v es t u d i e di ta n d p u tf o r w a r ds o m e n e w a l g o r i t h m s b a s e do nt h es t u d ya n ds u m m a r i z a t i o no ft h ep r o b l e mo fa s s o c i o a t i o nr u l e m i n i n g ，t h ee x i s t i n gm i n i n ga l g o r i t h m so f a s s o c i a t i o nr u l ew e r es o r t e sa n ds o m e t y p i c a l a l g o r i t h m sw e r ea n a l y z e da n dd i s c u s s e dt h o r o u g h l y , s u c ha sa i s 、a p r i o r ia n ds o m e c h a n g e da l g o r i t h m s b a s e do n p a r t i t i o n 、s a m p l i n g 、h a s h ，f p g r o w t h 、d l ga l g o r i t h m a n ds oo nt h i sp a p e rp o i n t so u tt h ea d v a n t a g ea n dd i s a d v a n t a g eo ft h e s ea l g o r i t h m s ，a t t h es a m et i m e ，p u tf o r w a r dan e wa b ma l g o r i t h mb a s e do nm a t r i xf o rm i n i n g a s s o c i o a t i o nr u l e sa n dc o m p a r e si tw i t ht r a d i t i o n a la l g o r i t h m sf o rf i n d i n gf r e q u e n t i t e m s e t sa b m a l g o r i t h mo n l yn e e d ss c a nt h ed a t a b a s eo n et i m e ，n e e d n 、tg i v eb i r t ht o c a n d i d a t ei t e m s e t sa n do c c u p i e sf e wm e m o r yf o ra s s i s t a n ti n f o r m a t i o n w ec a r r yo u t t h et y p i c a l a p r i o r ia n da b ma l g o r i t h m si nw i n d o w s2 0 0 0a n dd e l p h i 6 ，a n da n a l y s e t h e i rp e r f o r m a n c e sa c c o r d i n gt ot h ee x p e r i m e n tr e s u l t s s o m ee x i s t i n ga l g o r i t h m sf o rm i n i n ga s s o c i a t i o nr u l e sa i ma th i s t o r i c a ls t a t i c d a t a b a s e sa n df e wc o m ed o w nt ot h eu p d a t i n gp r o b l e mb e c a u s et h ea p p l i e dd a t a b a s e s a r ev e r yl a r g e ，h i g he f f i c i e n ta l g o r i t h m sa r er e q u i r e dn o to n l yt om i n ea s s o c i a t i o n r u l e s ，b u ta l s ot ou p d a t et h er u l e s t h a th a v eb e e nm i n e d t h i sp a p e rd i s c u s s e st h e u p d a t i n gp r o b l e mo f a s s o c i a t i o nr u l e si nt h ec h a n g eo fd a t a b a s edo rs u p p o r tsa n d a c c o r d i n g t ot h i sp r o b l e mp u tf o r w a r dd u a a n du b m a l g o r i t n m s t h ec o r e o f t h e s e t w oa l g o r i t h m si st ov i n d i c a t et h eo l dr u l e sa n dt of i n dn e wr u l e sa c c o r d i n gt oo l d r e s u l t s a sa n i m p o r t a n tt h e m eo nd a t am i n i n g ，a s s o c i a t i o n r u l e m i n i n gr e s e a r c h h a s 山东大学硕士掌位r e 文 p r o g r e s s e di n v a r i o u sd i r e c t i o n s h o w e v e r , t h e r ei sa ni m p o r t a n tf o r mo fa s s o c i a t i o n r u l e sw h i c ha r eu s e f u lb u tc o u l dn o tb ed i s c o v e r e dw i t h i nt h ee x i s t i n ga s s o c i a t i o nr u l e m i n i n g f r a m e w o r k ，s u c ha sr u l e ：i f t h ep r i c e s & i b ma n ds u n g ou p ，m i c r o s o f t sw i l l m o s t l i k e l y ( 8 0 o fp r o b a b i l i t y ) g ou p t h en e x t d a y a n dt h e n d r o p f o u r d a y s a f t e rc o m p a r e dw i t ht h ec l a s s i c a lr u l e s ，t h er u l ei sm o r ei n t e r e s t i n gw ec a l lt h i sr u l e i n t e r - t r a n s a c t i o na s s o c i a t i o nr u l e t h i s p a p e r d e s c r i b e st h e c o n c e p t s a b o u t i n t e r - t r a n s a c t i o na s s o c i a t i o nr u l ea n dt h e m i n i n gp r o c e s s o f1 - d i m e n t i o n a l i n t e r - t r a n s a c t i o na s s o c i a t i o nr u l e 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 ia l g o r i t h m ，t h eu p d a t i n gp r o b l e mo f a s s o c i a t i o nr u l e s ，i n t e r - t r a n s a c t i o na s s o c i a t i o nr u l e 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：生丛整 日甄：竹号像 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意 学校保留或向国家有关部门或机构送交论文的复印件和电子版，允许 论文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手 段保存论文和汇编本学位论文。 f 保密论文在解密后应遵守此规定) 论文作者签名：生! ! 登导师签名：蜷期：型堂日期：竺二_ ：y 山东大学硕士学位论文 基于矩阵的关联规则挖掘算法的设计与实现 第一章引言 1 1 课题提出的背景和意义 随着信息技术的迅猛发展，近年来数据挖掘引起了信息产业界的极大关注， 其主要原因是随着数据库技术的成熟和数据应用的普及，各个领域所积累的数据 量正在以指数速度增长。人们正面临着“数据丰富而知识贫乏”的问题，所以迫 切需要一种新的技术从海量数据中自动、高效地提取所需的有用知识。数据挖掘 技术就是适应这一要求迅速发展起来的一种处理数据的新技术，它可以从大型数 据库中的大量原始数据中提取人们感兴趣的、隐含的、尚未被发现的有用的信息 和知识。数据挖掘是一个融合数据库、机器学习、数理统计、可视化和信息科学 技术为一体的新兴的交叉学科领域。它的发展不仅可以为商务管理、科学研究、 查询优化、过程控制等领域提供决策支持，而且为相关的计算机学科注入新的活 力，从而推进计算机科学向纵深方向发展。毫无疑问，对数据挖掘的深入研究在 计算机理论和应用两个方面都具有十分重大的意义。在数据挖掘所能发现出的众 多知识种类中【”，例如，关联规贝r ( a s s o c i a t i o n ) 的挖掘、分类( c l a s s i f i c a t i o n ) 、聚 类( c l u s t e r i n g ) 、趋势( t r e n d ) 分析、偏差( d e v i a t i o n ) 分析、模式( p a t t e r n ) 分析等， 关联规则的挖掘是目前数据挖掘领域中研究最为广泛的课题之一。 关联规则是描述数据库中数据项之间潜在关系的规则。关联规则挖掘的一 般对象是事务数据库，起初主要应用于零售业，比如超级市场的销售管理。条形 码技术的发展使得数据的收集变得更容易更完整，从而存储了大量交易资料，关 联规则就是通过辨别这些交易资料，来分析顾客的购买模式，根据关联规则提供 的信息可以用做商品销售目录设计、商品布置、针对性的市场营销等。虽然关联 规则是伴随着零售业的飞速发展而产生的一种需求，但它的应用决不仅是在零售 业上。还体现在银行业、制造、经纪业和安全交易、保险业、计算机硬件和软件、 政府和防卫、医药、交通、电信等，所以展开对关联规则的研究具有重大意义。 1 9 9 3 年a g r a w a lr 等人首先提出了挖掘顾客交易数据库中项集问的关联规 山东大掌硕士学位论文 则问题【2 】，并于1 9 9 4 年提出了挖掘关联规则的经典a p r i o r i 算法【3 1 。后来有不少 学者对关联规则的挖掘问题进行了大量的研究。他们的工作包括对原有a p r i o r i 算法进行优化，如引入随机采样、并行的思想【5 】、使用哈希方法 6 1 等，以提高 算法挖掘规则的效率：有的为了避免频繁集产生方法的一些缺陷，提出了独立于 a p r i o r i 算法的挖掘关联规则的新方法，如j i a w e ih a n 等人提出的不产生候选 挖掘频繁项集的f p g r o w t h 方法【7 i 、基于关联图的挖掘关联规则的方法【8 1 等。挖 掘关联规则的挑战性在于数据量巨大，算法的效率是关键，因此有必要研究出占 用内存小、i o 操作少、执行速度快的高效算法。作者在本文提出的基于矩阵的 关联规则挖掘算法一a b m 可以很好地解决这一问题。同时，事物数据库d 或支 持度s 发生变化会引起关联规则的更新问题，怎样利用已有的结果挖掘出新的频 繁项集也是一个值得研究的问题。传统的关联规则所表达的信息是有限的，与其 相比，事物间关联规则更有意义。 1 2 本文的主要研究内容 本文选取目前数据挖掘方面比较集中的课题关联规则的挖掘进行研究分析， 主要工作如下： ( 1 ) 描述了数据挖掘的概念、功能，数据挖掘系统的结构与分类以及数据 挖掘与传统数据分析工具和机器学习的区别。 给出关联规则的有关概念，描述了几种经典算法并分析了其优缺点。 提出了一种基于矩阵的挖掘关联规则的a b m 算法。 在w i n d o w s 2 0 0 0 平台上用d e l p h i 6 0 以t e s tl 、t e s t 2 和s q l s e r v e r 70 自带的n o n h w i n d 数据库为例实现了a b m 算法和a 口r i o r i 算法，并对 其性能进行了分析。 讨论了关联规则的更新问题，最小支持度s 发生变化或事务数据库d 发生变化后，怎样利用已有的挖掘结果产生新的频繁项集，同时提出 了d u a 算法和基于a b m 算法思想的更新算法u b m 算法。 描述了事务间关联规则的有关定义，并给出了1 维事务间关联规则的 挖掘过程。 i ) ) 门 山东大掌硕士掌位论文 第二章课题研究的背景知识 数据挖掘( d a t am i n i n g ) 指的是从大量、部分、模糊、随机的实际应用数据 中提取隐含其中、人们事先不知道的、但又有用的信息，同时用能被人理解的模 式进行高级处理的过程忆它是数据库中知识发现( k d d ) 的核心部分。本文后 面关于关联规则的研究是数据挖掘的一个重要功能。 2 1 数据挖掘功能可以挖掘什么类型的模式 数据挖掘功能用于指定数据挖掘任务中要找的模式类型 1 l 。数据挖掘任务一 般可以分为两类：描述和预测。描述性挖掘任务刻划数据库中数据的一般特性。 预测性挖掘任务在当前数据上进行推断，以进行预测。数据挖掘应用程序的预测 和描述的相对重要性是在不断变化的。通过以下数据挖掘功能以及它们发现的模 式类型可以达到预测和描述的目的。 2 1 1 概念类描述：特征化和区分 概念是思维的基本形式之一，反映客观事物的一般的、本质的特征，概念 描述( c o n c e p t d e s c r i p r i o r i ) 的目的是产生代表概念的数据的特征化和比较描述， 而并非是对数据的简单枚举。概念描述也称为类描述( c l a s sd e s c r i p t i o n ) 。数 据特征化( d a t ac h a r a c t e r i z a t i o n ) 是目标类数据的一般特征或特性的汇总。通 常用户指定类的数据通过数据库查询收集。数据区分( d a t a d i s c r i m i n a t i o n ) 是 将目标类对象的一般特性与一个或多个对比类对象的一般特性比较。目标类和 对比类由用户指定，而对应的数据通过数据库查询检索。 2 1 2 关联分析 关联分析发现关联规则。关联规则是指发现客体之间的相互关系。关联规 则通常表示成x y 即“a l 八八a m 等b 1 八a b 。”这样的形式，其中，a i ( i l ，m ) ) ，b j ( j l ，n ) ) 是属性一值对。它意味着在目标数据中客体b i 八 八b 。倾向于同客体a l 八八a 。一起出现。例如，规则：面包+ 牛奶黄油( 5 ， 4 0 ) 指出在购买面包和牛奶的顾客中有4 0 的人同时购买了黄油。这里，4 0 为关联规则的信任度，而5 为关联规则的支持度。 山东大学硕士学位论文 2 1 3 分类( c l a s s i f i c a t i o n ) 和预测( p r e d i c t i o n ) 分类是指将数据归于一系列已知类中的某一个的分类过程。分类的目的是 学会一个分类函数或分类模型( 也常常称为分类器) ，该模型能把数据库中的数 据项映射到给定类别中的某一个。给定一训练数据集( 即己知其类别标记的客体 集) ，以及基于训练集中数据的特性建立的分类模型，目标是从该分类模型中生 成一系列的分类规则，这些分类规则可用于对其它未来的数据进行分类，从而可 以更好地理解数据库中的每一类。例如，关于疾病的分类规则可以从已知病例( 训 练集) 提取出来，然后结合新病员的症状，可用于对新病员进行诊断。关于申请 贷款者的分类，银行可以根据分类对以后的贷款申请者决定是否给与贷款。 预测是构造和使用模型评估无标号样本类，或评估给定样本可能具有的属性 值或值区间。预测和分类的不同点在于：用预测法预测类标号为分类，用预测法 预测连续值( 例如用回归分析法) 为预测，这是在数据挖掘界被广泛接受的观点。 2 1 4 聚类( c l u s t e r i n g ) 聚类是根据客体属性对一系列未分类客体进行类别的识别，把一组个体按 照相似性归成若干类别，即“物以类聚”。它的目的是使得属于同一类别的个体 之间的距离尽可能的小而不同类别的个体间的距离尽可能的大。客体的聚类应使 得类内相似性最大，而类间相似性最小。一旦聚类得以确定，各个客体就作相应 的聚类标记，并概括同一聚类中的各个客体的共同特性，从而形成类别描述。例 如，一系列的新疾病可以根据其症状的相似性进行分组，从而形成基本类别，同 一类别中各疾病的共同症状便可以用于描述该组疾病。 2 1 5 离群挖掘( o u t l i e rm i n i n g ) 数据库中有可能包含一些数据对象，它们与数据的一般行为或模型不一致， 这些数据对象被称为离群数据，也称为孤立点。大部分数据挖掘方法将孤立点视 为噪声或异常而丢弃。然而，在某些应用中( 如欺骗检测) ，罕见的事件可能比 正常出现的事件更有意义。离群数据的分析称作离群挖掘。 离群数据可以使用统计实验检测。事先假定一个概率分布模型，并选取合 适的距离度量，到其它聚类的距离很大的数据对象被视为离群数据。基于偏差的 方法通过考察一群对象主要特征上的差别识别离群数据，而不是使用统计度量或 山东大掌硕士学位论文 距离度量。 2 1 6 演变分析( e v o l u t i o n a n a l y s i s ) 数据演变分析描述行为随时间变化的对象的规律或趋势，并对其建模。尽管 这可能包括时间相关数据的特征化、区分、关联、分类或聚类，这类分析的不同 特点包括时间序列分析【9 】f 10 1 、序列1 或周期模式匹配和基于类似性的数据分析。 2 。2 数据挖掘系统的结构 典型的数据挖掘系统的结构如图2 1 所示，其主要成分有数据库数据仓库 或其它信息库、数据库或数据仓库服务器、知识库、数据挖掘引擎、模式评估 模块、图形用户界面【1 2 】。 数据 图2 1 典型的数据挖掘系统结构 数据库、数据仓库或其它信息库：它们是进行数据挖掘的数据源，是一 个或一组数据库、数据仓库、电子表格或其它类型的信息库。可以在它们的数 据上进行数据清理和集成。 数据库或数据仓库服务器：根据用户的数据挖掘要求，数据库或数据仓 库服务器负责提取相关的数据。 知识库：这是特定的领域知识，用于指定搜索或评估结果模式的兴趣度。 这种知识可能包括概念分层，用于将属性或属性值组织成不同的抽象层。其中 山东大学硕士学位- v e 文 用户确信方面的知识也可以包含在内。可以使用这种知识，根据非期望性评估 模式的兴趣度。 数据挖掘引擎：这是数据挖掘的最重要的基本部分。由组功能模块组 成，用于特征化、关联、分类、聚类分析以及演变和偏差分析。 模式评估模块：通常此成分使用兴趣度度量，并与数据挖掘模块交互， 以便将搜索聚集在有趣的模式上。它可能使用兴趣度阈值过滤发现的模式。模式 评估模块也可以与挖掘模块集成在一起，这依赖于所用的数据挖掘方法的实现。 对于有效的数据挖掘，建议尽可能深的将模式评估推进到挖掘过程之中，以便将 搜索限制在有兴趣的模式上。 图形用户界面：此模块在用户和数据挖掘系统之间通信，允许用户与系 统交互，指定数据挖掘查询或任务，提供信息、帮助搜索聚焦，根据数据挖掘的 中间结果进行探索式数据挖掘。此外，此成分还允许用户浏览数据库和数据仓库 模式或数据结构，评估挖掘的模式，以不同的形式对模式可视化。 2 。3 数据挖掘与传统数据分析工具和机器学习的区别 对于o l a p ，用户首先建立一个假设，然后用o l a p 检索数据库来验证这个 假设是否正确。比如一个分析师想找到是什么导致拖欠贷款，他可能先做一个初 始假定，认为低收入的人信用度也低，然后他可以用o l a p 来验证他的假设。如 果这个假设没有被证实，他可能去查看那些高负债的账户，如果还不行，他可能 要把收入和负债一起来考虑，继续进行下去直到找到他想要的结果或放弃。也可 以这么说，o l a p 分析师是建立一系列的假设，然后通过o l a p 验证或推翻这些 假设来最终得到自己的结论。o l a p 过程本质上是一个演绎推理的过程。数据挖 掘与o l a p 相比其不同之处在于数据挖掘不是用来验证某个假设的模式( 模型) 的正确性，而是在数据库中自己寻找模型。它在本质上是一个归纳的过程。举个 例子，一个用数据挖掘工具的分析师想找到引起贷款拖欠的风险因素，数据挖掘 可以帮他找到高负债和低收入是引起这个问题的因素，甚至还能发现一些分析师 从没想过或试过的其它因素。同时数据挖掘和o l a p 具有一定的互补性，在利用 数据挖掘得出来的结论采取行动之前可以验证以下如果采取这样的行动会给公 司带来什么样的影响，o l a p 可以回答这个问题。 6 山东大学硕士掌位论文 概括说来，数据挖掘与传统的数据分析( 如查询、报衷、联机分析处理) 的本质区别是数据挖掘是在没有明确假设的前提下去挖掘信息、发现知识【l ”。数 据挖掘所得到的信息应具有原先未知、有效和可实用三个特征。先前未知的信息 是指该信息是预先未预料到的。即数据挖掘是要发现那些不能靠直觉发现的信息 或知识，甚至是违背直觉的信息或知识，挖掘出的信息越是出乎意料，就可能越 有价值。 数据挖掘是从现实世界中存在的一些具体的数据中提取知识，这些数据在 数据挖掘出现之前早己存在；而机器学习所使用的数据是专门为机器学习而特别 准备的数据，这些数据在现实世界中也许毫无意义。由于数据挖掘使用的数据来 自于实际的数据库，所要处理的数据量可能很大，因此数据挖掘算法的效率和可 扩充性就显得尤为重要；此外，数据挖掘所处理的数据由于来自于现实世界，数 据的完整性、一致性和正确性都很难保证，如何将这些数据加工成算法可以接收 的数据也需要进行深入的研究：再者，数据挖掘可以利用目前数据库技术所取得 的研究成果来加快挖掘过程，提高挖掘的效率。最后，由于数据挖掘处理的数据 来自于实际的数据库，而与这些数据库数据有关的还有其他一些背景知识，这些 背景知识的合理运用也会提高算法的效率。 7 山东大学硕士掌位论文 第三章a b m 算法的理论基础 关联规则描述了数据库中数据项之间潜在的关系。在数据挖掘的知识模式 中，关联规则模式是比较重要的一种。关联规则的概念由a g r a w a lr 等在【2 】中提 出，是数据挖掘中一种简单但很实用的规则。关联规则属于描述型模式，发现关 联规则的算法属于无监督学习的方法。 3 1 关联规则的有关定义 设i = f i l i 2 ，i m l 是所有项的集合，相当于超市中产品种类的集合。t 是i 的 子集( t i ) ，即t 为项的集合( t = t l ，t 2 ，t n ) ) ，称之为事务，相当于一个顾客购 买的商品组成的集合。每个事务都有一个标识符，称作t i d 。所有的事务构成事 务集d ，相当于数据库中记录的集合。项的集合称为项集，包含k 项的项集称为 k 项集。关联规则表示为a b 的形式，其中a c i ，b c i ，并且a n b = o ，关联 规则描述了a 的出现影响到b 的出现。现实中，这样的例子很多。例如超级市 场利用前端收款机收集存储了大量的售货数据，这些数据是一条条的购买事务记 录，每条记录存贮了事务处理时间，顾客购买的物品，物品的数量及金额等。这 些数据中常常隐含形式如下的关联规则：在购买铁锤的顾客当中，有7 0 的人同 时购买了铁钉。这些关联规则很有价值，商场管理人员可以根据这些关联规则更 好的规划商场，如把铁锤和铁钉这样的商品摆放在起，能够促进销售。一些数 据不像售货数据那样很容易就能看出一个事务是许多物品的集合，但稍微转换一 下思考角度，仍然可以像售货数据一样处理。比如人寿保险，一份保单就是一个 事务。保险公司在接受保险前，往往需要记录投保人详尽的信息，有时还要到医 院做身体检查。保单上记录有投保人的年龄、性别、健康状况、工作单位、工作 地址、工资水平等。这些投保人的个人信息就可以看作事务中的样品。通过分析 这些数据，可以得到类似以下这样的关联规则：年龄在4 0 岁以上，工作在a 区 的投保人当中，有4 5 的人曾经向保险公司索赔过。在这条规则中，“年龄在4 0 岁以上”是物品甲，“工作在a 区”是物品乙，“向保险公司索赔过”则是物品丙。 可以看得出来，a 区可能污染比较严重，环境比较差，导致工作在该区的人健康 山东大学硕士学位论文 状况不好，索赔率也相对比较高。 描述关联规则属性常用的参数有： 1 ) 支持度( s u p p o r t ) 支持度s 是d 中包含a u b 的事务百分比，它是概率p ( a u b ) ，即 s u p p o n ( a z ，b ) = p ( a u b ) ，它描述了a 和b 这两个物品集的并集在所有的事务中 出现的概率。例m ，一事务数据库中共有1 0 0 0 条记录，其中同时包含a 和b 的 有1 0 0 条，则关联规则a b 的支持度为1 0 0 1 0 0 0 = 1 0 。支持度表示了规则的 频度。满足最小支持度的项集称之为频繁项集。 2 ) 置信度( c o n f i d e n c e ) 置信度c 为d 中包含a 的事务中同时也包含b 的百分比，它是概率p ( b t a ) ， 即c o n f i d e n c e ( a = b ) = p ( b i a ) 。在例m 中，如果有2 0 0 条记录包含a ，则关联规 则a j b 的置信度为1 0 0 2 0 0 = 5 0 。置信度表示了规则的强度。 同时满足最小支持度阈值和最小置信度阀值的规则称作强规则。 3 ) 期望置信度( e x p e c t e d c o n f i d e n c e ) 0 4 1 期望置信度e 为d 中包含b 的事务百分比，即p ( b ) 。期望置信度描述在 没有任何条件影响时，物品集b 在所有事物中出现的概率有多大。在例m 中如 果有1 5 0 条记录包含b ，则关联规则a j b 的期望置信度为1 5 0 1 0 0 0 = 1 5 。 4 ) 作用度( l i f t ) ( 1 4 i 作用度是置信度与期望置信度的比值，即p 0 3 i a ) p ( b 1 。作用度描述了项 集a 的出现对项集b 的出现有多大的影响，作用度越大，说明物品集b 受物品 集a 的影响越大。因为项集b 在所有事务中出现的概率是期望置信度：而项集b 在所有项集a 出现的概率是置信度，通过置信度与期望置信度的比值反映了在加 入“项集a 出现”的这个条件后，项集b 的出现概率发生了多大的变化。在例 m 中，关联规则a j b 的作用度为5 0 1 5 = 1 0 3 * - 33 。一般情况，有用的关联 规则的作用度都应该大于1 ，只有关联规则的可信度大于期望可信度，才说明a 的出现对b 的出现有促进作用，也说明了它们之间某种程度的相关性，如果作用 度不大于1 ，则此关联规则也就没有意义了。 5 ) 兴趣度( i n t e r e s tm e a s u r e ) f 1 5 1 1 1 6 】1 1 7 擂】 在数据挖掘中，并不是所有的强关联规则都是足够的有趣而值得向用户提 山东大学硕士学位论文 供。例如对一个学校的5 0 0 0 名学生进行早晨参与活动与早餐的情况调查。数据 显示：6 0 的学生( 3 0 0 0 ) 打篮球，7 5 的学生( 3 7 5 0 ) 吃谷类早餐，4 0 的学 生( 2 0 0 0 ) 既打篮球又吃谷类早餐。假设最小支持数为2 0 0 0 ，最小嚣信度为6 0 。 则“打篮球j 吃谷类早餐”是一强关联规则，因为其支持数为2 0 0 0 ，置信度为 2 0 0 0 3 0 0 0 = 6 6 ，满足最小支持数和最小置信度的要求。然而以上规则是误导， 因为总的吃谷类早餐的学生占7 5 ，比6 6 还要大。为了修剪一些无趣的规则， 即避免生成“错觉”的关联规则，下面定义了兴趣度这个度量值。 基于差异思想的兴趣度定义：i x 。i i c r 面- i s 页( b 而) ，这个定义是由规则的置 信度和规则右部项集的支持度而产生的。分母上的m a x c r , s ( b ) 只是个标准化因 子，使得ii r l 职业= “秘书”， 山东大学硕士掌位论文 是布尔型关联规则；性别= “女”= a v g ( 收入) = 2 3 0 0 ，涉及的收入是数值类型， 所以是一个数值型关联规则。后面介绍的a b m 算法挖掘的是布尔型关联规则。 2 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。 在单层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个不 同的层次的；而在多层的关联规则中，对数据的多层性已经进行了充分的考虑。 例如：i b m 台式机= s o n y 打印机，是一个细节数据上的单层关联规则；台式机 = s o n y 打印机，是一个较高层次和细节层次之间的多层关联规则。后面介绍的 a b m 算法挖掘的是单层关联规则。 3 。基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。 在单维的关联规则中，我们只涉及到数据的一个维，如用户购买的物品； 而在多维的关联规则中，要处理的数据将会涉及多个维。换成另一句话，单维关 联规则是处理单个属性中的一些关系：多维关联规则是处理各个属性之间的某些 关系。例如：啤酒= ) 尿布，这条规则只涉及到用户购买的物品：性别= “女”= 职业= “秘书”，这条规则就涉及到两个字段的信息，是两个维上的条关联规则。 后面介绍的a b m 算法挖掘的是单维关联规则。 3 3 挖掘关联规则的经典算法 为了描述算法，我们给出以下原事务数据库如图3 1 ，并给每个项目赋一个 整数，b r e a d 一1 ，c o k e 一2 ，m i l k 一3 ，b e e r 一4 ，c a k e 一5 ，得整数化后的数据库如图3 2 。 设最小支持度为2 2 ，因为一共有9 个事务，所以频繁项目集至少要出现2 次。 给定个事务数据库d ，挖掘关联规则的问题就是找出所有满足最小支持度和最 小置信度的关联规则，即挖掘出所有的强规则。该问题可分解为两个子问题l l j ： ( 1 ) 找出所有频繁项目集，即出现频率至少和预定义的最小支持度样的项目集。 ( 2 ) 由频繁项目集产生关联规则。一旦找出了频繁项目集，则由它们产生强关联规 贝。就很简单了，n n n 以nc o n f i d e n c e ( a ：，b ) = p ( b j a ) = ! ! ：；：；篙 来计算置信度，其中s u p p o r t c o u n t ( aub ) 是包含a ub 的事务数， s u p p ( ) r tc o u n t ( a ) 是包含a 的事务数。所以现在的研究都放在了第一步，即找频 繁项目集。 山东大学硕士掌位- g e 文 t i di t e m s e t s t 1 b r o a d 。c o k e ，c a k e t 2 c o k e ，b e e r 1 3 c o k e m i l l ( t 4b r e a d c o k e b e e r t 5b r e a d m 盐 t 6c o k e ，m i l k t 7b r e a d m i i k t 8 b r e a d ，c o k e ，m i n ( ，c a k e 7 9 b r e a d ，c o k e m i l k t i di t e m s e t s t 1 1 ，2 ，5 t 2 2 , 4 t 32 3 t 4 1 , 2 ，4 t 5l - 3 t 6 2 。3 t 7l - 3 t 8 1 , 2 ，3 ，5 t 9 1 2 , 3 图3 1 原事务数据库图3 2 整数化的事务数据库 3 3 1a i s 算法 当数据库被扫描时，候选集被产生并计数。每读一个事物，决定上次扫描找 到的频繁集中有哪些包含在事务中。通过事务中的其它项目来扩展这些频繁集， 从而得到新的候选集，这些候选集被加到扫描的候选集中，或者增加其相应的计 数l ”。这个算法有个很大的缺陷就是产生过多的小候选，因此效率非常低。 3 3 2 a p r i o r i 算法及改进 a p r i o r i 算法是一种最有影响的挖掘布尔关联规则频繁项集的算法，它使用 了频繁项集的所有非空子集都必须也是频繁集的这一性质。其基本思想是：扫描 数据库一遍统计各数据项，从而找出频繁1 一项目集l l ，然后由l 1 得l 2 ，由l 2 得l 3 ，直到不能产生频繁项目集，由k 1 得l k 的过程是将l k _ 1 中满足( 1 l 1 = 1 2 1 ) 八( 1 1 2 = 1 2 2 ) 八( 1 l k - 2 3 = 1 2 k - 2 ) 八( 1 l k 一1 1 2 k 一1 ) 的项目集进行自身 连接，然后再删除( k 1 ) 一子集不属于l k 的项集( 剪枝) ，从而生成候选项目集 c k ，最后再扫描事务数据库，对每个候选项目集计数，根据最小支持度就可得出 l k 3 1 。其具体步骤如图3 3 所示： 该算法在产生候选项目集的时候只用到前一次迭代所产生的频繁项目集， 而没有考虑数据库中的事务，同时还使用了连接和剪枝技术，这样就会产生比 a i s 算法少的候选集。该算法能够比较有效地产生关联规则，但也存在着以下缺 陷：( 1 ) 算法产生太多冗余的规则。当数据库太大或支持度、信任度闽值太低时 产生的规则太多，用户很难人为地对这些规则做出区分、判断。( 2 ) 算法在效率 山东大学硕士掌位论文 上存在着问题。主要是因为数据库扫描次数太多，寻找每个k 一项目集( k = 1 ， k ) 都需要扫描数据库一次，共需要扫描数据库k 次。另外，当模式太长时产生 的候选项目集也多得让人无法接受。因此，当数据库或k 太大时，算法的耗时太 大。 c l l 【口 f 玎，n 4 1 1 , 1 5 l2 i 王1 3 l4 f 1 2 ，1 4 】 2 f 1 2 1 5 2 l ( 1 2 d l7l