（计算机应用技术专业论文）数据挖掘中关联规则挖掘算法的分析与研究.pdf

原创性声明 本入郑重声明：所呈交的学位论文，是本人在导师的指浮下，独立 进行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含 任何萁袍个入躐集体已经发表或撰写过的科研畿巢。对本文的磺究作出 重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到 本声鹗豹法律赛任由本人承担。 论文作者签名：鎏芝差 匿期： 堡至塞翌 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校 保辫或肉国家有关部门或梳掏送交论文的复印件嗣电子版，允许论文被 查澜和借阅；本人授权山东大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或其他复制手段保存论文 和汇编本学位论文。 f 保密论文在解密后应遵守此规定) 论文作者签名：塞兰薯导师签名： 日飙华 山东大学硕士学位论文 摘要 数据挖掘是从数据中析取、识别和发现潜在f 确和有用、先前未知的、最 终可理解的知识( 规则或模型) 的过程。数据挖掘技术要在已有数据中识别数 据的模式，以帮助用户理解现有的信息，并在己有信息的基础上，对未来的状 况作出预测。 数据挖掘着眼于设计高效的算法以达到从海量数据中发现知识的目的。所 谓知识，从工程角度定义，就是有助于解决问题的有格式的，可复用的信息。 在传统的决策支持系统中，知识库中的知识和规则是由专家或程序人员建立的， 是由外部输入的。而数据挖掘的任务是从大量数据中发现尚未被发现的知识， 是从数据内部自动获取知识的过程。 关联规则的挖掘是数据挖掘领域的重要研究方向。关联规则反映的是数据 间一种内在的关联联系。发现数据之间的这种内在的联系，有利于决策者利用 这些规则作出正确和合理的决策。 本文首先对关联规则的挖掘的基本理论和方法进行了详细的阐述，并在此 基础上，对经典的关联规则的挖掘算法进行了改进，从而提高了关联规则挖掘 的性能。本文的工作主要包括以下内容： ( 1 ) 论述了关联规则有趣性问题可从客观和主观两方面进行评测。利用 模板将用户感兴趣的规则和不感兴趣的规则区分开，以此来完成关联规则有 趣性的主观评测，对关联规则的有趣性的客观评测增加了约束，并给出模板 匹配算法。 ( 2 ) 利用视图机制对原始数据进行预处理，把符合条件的数据和有用的 属性放入视图中。根据一维( l ) 和二维( k ) 中的频繁数据项集对数据库中 的属性进行过滤，以达到减少数据属性的目的，从而压缩数据库中的数据， 为提高关联规则挖掘算法的性能打下基础。 ( 3 ) 利用f i s h e r 聚类方法对定量属性变量进行分段，在处理时考虑了 数据间隔的大小及数据间隔的稠密度，得到的定量关联规则可以近似地反映 规则中数据项集的关联性。 ( 4 ) 分析基于关系操作的关联规则挖掘算法r s ( r e l a t i o ns e t ) ，算法 第3 页 山东大学硕士学位论文 r s 将扫描空间分为若干简单的较小分区，每个分区可以在内存中分别处理。 算法r s 主要使用简单的交操作，可用数据库系统中的s q l 语言表示。同时还 给出了在给定概念层上对r s 算法的改进算法一挖掘广义关联规则的算法 g r s ( g e n e r a l jz e dr e l a t i o ns e t ) 。实验结果表明，这两个算法具有高效性和 可扩展性。 关键词：数据挖掘，关联规则，频繁项目集，有趣性，过滤，模板。 第4 页 山东大学硕士学位论文 a b s t r a c t d a t am in i n gi st h ep r o c e s so fe x t r a c t j n g ，jd e n t i f y in ga n dd is c o v e r i n g p o t e n t i a l lyv a l i d ，u s e f u l ，p r e v i o u s lyu n k n o w n ， a n du l t i m a t e l y u n d e r s t a n d a b l ek n o w l e d g e ( r u l e so rp a t t e r n s ) d a t am in i n gt e c h n o l o g yc a n i d e n t jf yd i f f e r e n td a t am o d e l sf r o mt h ee x i s t i n gd a t a ，s oi tcanh e l p t h eu s e ru n d e r s t a n dt h ee x i s t i n gi n f o r m a t i o na n dp r e d i c tt h ef u t u r e d e v e l o p m e n to ft h eb u s i n e s s b a s e do nt h ep r e s e n tc o n d i t i o n d a t am i n i n gi sm a i m ya b o u td e s i g n i n ge f f i c i e n ta l g o r i t h m st o d is c o v e rk n o w l e d g ef r o mm a g n i t u d ed a t a f r o mt h ev i e w p o i n to f e n g i n e e r i n g t h es o c a l l e dk n o w l e d g ei st h ef o r m a t t e da n dr e u s a b l e i n f o r m a t i o n ，w h i c hi sb e n e f i c i a lt os o l v ep r o b l e m s i nt r a d i t i o n a ld s s t h ek n o w l e d g ea n di t sr u e sa r ee s t a b l is h e db yt h ee x p e r t so rt h e p r o g r a m m e r sa n di n p u tf r o mt h ee x t e r i o r ，i nc o n t r a s t ，t h et a s k o fd a t a m i n i n gi st od i s c o v e rt h eu n r e v e a l e dk n o w l e d g ef r o mm a g n i t u d ed a t a ，s o i t i sa na u t o m a t i cp r o c e s s i n go fk n o w l e d g eo b t a i n i n gf r o mt h ei n t e r i o r d a t a t h ed a t am i n i n go fa s s o c i a t i o nr u l e si sa ni m p o r t a n tr e s e a r c ha s p e c t i nt h ed a t am i n i n gf i e l d s a s s o c i a t i o nr u l e sr e f l e c tt h ei n n e r r e l a t i o n s h i po fd a t a d i s c o v e r i n gt h e s ea s s o c i a t i o n sisb e n e f i c i a lt o t h ec o r r e c ta n da p p r o p r i a t ed e c i s i o n m a d eb yd e c i s i o n m a k e r s t h i sp a p e rf i r s t l yi n t r o d u c e st h ep r i n c i p l e so fd a t am i n i n ga n dt h e m e t h o d so fa s s o e i a t i o nr u l e si nd e t a i l o nt h eb a s i so ft h i st h e o r y ，m u c h i m p r o v e m e n ti sm a d ei nc l a s s i cd a t am i n i n ga l g o r i t h mi no r d e rt oe n h a n c e t h ed a t am i n i n gp e r f o r m a n c eo fa s s o c i a t i o nr u l e s t h em a i nc o n t e n to f t h i sp a p e risa sf o l l o w s ： ( 1 ) t h ei n t e r e s t i n g n e s so fa s s o c i a t i o nr u l e sc a nb ee v a l u a t e db yb o t h s u b j e c t i v e m e a s u r ea n do b j e c t i v em e a s u r e u s i n gt e m p l a t e s t o d i f f e r e n t i a t et h er u l e si n t e r e s t e dt ot h eu s e ro rn o ti st h em a i na p p r o a c h 第5 页 山东大学硕士学位论文 o ff u l f i l l i n gs u b j e c t i v ee v a u a t i o no ft h ei n t e r e s t i n g n e s s t h u sw em u s t i n c r e a s et h er e s t r ic t i o no fo b j e c t i v ee v a l u a t jo no ft h ei n t e r e s t i n g n e s s a t l a s tat e m p l a t em a t c h i n ga g o r i t h misp r e s e n t e da sw e l l ( 2 ) t h ed a t am e e t i n gs o m ec o n d i t i o na n du s e f u la t t r i b a t e sare e x t r a c t e di n t ov i e w su s i n gt h em e e h a n i s mo fv i e wt op r e t r e a tt h ep r i m a r y d a t a a t t r i b u t e si nt h ed a t a b a s ea r ef i l t r a t e da c c o r d i n gt ot h ef r e q u e n t d a t ai t e ms e t so fl a r g eonei t e m s e t s ( l 1 ) a n dl a r g et w oi t e m s e t s ( l 2 ) i no r d e rt or e d u c et h en u m b e ro fd a t aa t t r i b u t e s ，a tt h es a m et i m e c o m p r e s st h ed a t av o l u m eo ft h ed a t a b a s e t h u sw es h o u l dm a k et h e i n f r a s t r u c t u r eo ft h eh i g hp e r f o r m a n c ed a t am i n i n ga l g o r i t h mo f a s s o c i a t i o nr u l e s ( 3 ) q u a n t i t i v ea t t r i b u t e v a r i a b l e sa r ep a r t i t i o n i n gu s i n gf i s h e r c l u s t e r i n g t h es i z ea n dt h ed e n s i t yo fd a t ai n t e r v a l sa r et a k e ni n t o a c c o u n td u r i n gd i s p o s a l t h ed i s c o v e r e dq u a n t i t i v ea s s o c i a t i o nr u l e scan r e f l e c tt h ea s s o c i a t i o n sa m o n gd a t ai t e ms e t si n v o l v e da p p r o x i m a t e l y ( 4 ) t h er s ( r e l a t i o ns e t ) a l g o r i t h mb a s e do nr e l a t i o na l g e b r aa n d g r s ( g e n e r a l i z e dr e l a t i o ns e t ) a l g o r i t h ma r ea n a l y z e da sw e l l u s i n gr s a l g o r i t h m ，t h es e a r c hs p a c ei sd e c o m p o s e di n t os i m p l ys m a l lp i e c e s e a c h p i e c ecanb ep r o c e s s e ds e p a r a t e l yi nm a i nm e m o r y f u r t h e r m o r e ，t h er s a l g o r i t h mm a i n l yu s e st h ei n t e r s e c t i o no p e r a t i o no fs e t ，s oi t i se a s y t ob ee x p r e s s e dd i r e c t l yi ns q l t h ea d v a n t a g eo fr si sa c c e l e r a t i n gt h e c r e a t i o no fm u l t i d i m e n s i o n a lf r e q u e n td a t ai t e ms e t s 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 s ，i n t e r e s t i n g n e s s ，f i i t r a t e t e m p l a t e 第6 页 山东大学硕士学位论文 1 引言 1 1 数据挖掘的基本概念 随着数据量的急剧增长，现在的用户很难自己根据数掘的分布找出规律， 并根据此规律进行分析决策。因此必须借助于相应的数据挖掘工具，自动发现 数据中隐藏的规律或模式，为决策提供支持。数据挖掘技术主要用于从大量的 数据中发现隐藏于其后的规律或数据间的关系，它通常采用机器自动识别的方 式，不需要更多的人工干预。 确切地说，数据挖掘( d a t am i n i n g ，d m ) ，又称数据库中的知识发现 ( 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 ，k d d ) ，是指从存放于大型数据库或数据仓库 中的海量集合中，提取出人们感兴趣的知识，这些知识是隐含的、未知的、非 平凡的、潜在的有价值的知识( 模型或规则) 的过程。它是数据库研究中的一 个很有应用价值的新领域，目前国际上数据库和信息决策领域的最前沿研究方 向之一，融合了数据库、人工智能、机器学习、统计学等多个领域的理论和技 术，引起了学术界和产业界的广泛关注。 1 2 目前研究现状与发展趋势 目前，数据挖掘的研究重点转向多种发现策略和技术的集成，以及多种学科 之间的相互渗透。其他内容的专题会议也把数据挖掘和知识发现列为议题之一， 成为当前计算机科学界的一大热点。 此外，数据库、人工智能、信息处理、知识工程等领域的国际学术刊物也 纷纷开辟了k d d 专题或专刊。不仅如此，在i n t e r n e t 上还有不少k d d 电子出 版物，其中以半月刊k n o w l e d g ed i s c o v e r yn u g g e t s 最为权威，还可以下载各种 各样的数据挖掘工具软件和典型的样本数据仓库，供人们测试和评价。另一份 在线周刊为d s 术( d s 代表决策支持，d e c i s i o ns u p p o r t ) ，还有一个自由论坛d m e m a i lc 1 u b ，人们通过电子邮件相互讨论d m k d ( d a t am i n i n gk n o w l e d g e d i s c o v e r y ) 的热点问题。而领导整个潮流的d m k d 开发和研究中心，设在美国 e m d e n 的i b m 公司开发部。当前，世界上比较有影响的典型数据挖掘系统有 c o v e r s t o r y 、k n o w l e d g ed i s c o v e r yw o r k b e n c h 、d b m i n e r 、q u e s t 等 1 。 第7 页 山东大学硕士学位论文 作为一门新兴的且有着广阔发展前景的研究领域，数据挖掘技术仍然面临 许多挑战和需要解决的问题。 在不同的应用领域中存在不同的数据和数掘库，而且经常包含复杂的数据 类型，数据类型的多样性和不同的数据挖掘目标，造成了一个挖掘系统不可能 处理不同类型的数据，针对特定的数据类型，建立与之相适应的数据挖掘系统。 ( 1 )目前，存储上百万条记录，具有千兆字节大小的数据库相当普遍，兆兆 ( 1 0 ”) 字节大小的数据库已开始出现，而且在数据库中不仅有大量的 记录，而且记录的域的数量也相当大，产生了多维问题。因此，在多维 数据库中高效地挖掘关联规则是一个值得研究的问题。 ( 2 )大多数数据库的内容经常变化，这种变化可能使先前发现的知识失效。 有必要考虑动态关联规则挖掘算法。 ( 3 )数据挖掘算法的有效性和可测性。 ( 4 )数据挖掘与其他系统的集成。一个单独的数据挖掘系统可能用处不大。 典型的集成是在数据挖掘系统与d b m s ( 如：通过个查询界面) 、可视 化工具、实时数据采集设备之间进行的。 ( 5 )从不同的数据源挖掘规则。 1 3 本文工作简介 发现蕴涵在海量数据之间的某些内在联系，有利于决策者作出正确和合理 的决策。关联规则就是反映数据间内在关联联系的知识。本文主要从数据挖掘 的方法入手，对关联规则的挖掘问题及相关算法进行了分析与研究。 ( 1 ) 从大规模的数据中挖掘关联规则，产生的关联规则的数量也将非常 大，用户往往可能只对部分数据项集间的关联规则感兴趣。本文引入了关联 规则兴趣度的概念，并从主观和客观两个方面论述了对兴趣度的测评，提出 了可利用模板对用户不感兴趣的规则进行过滤，在客观评测方面，提出了可 对关联规则的有趣性增加约束，以达到显著减少关联规则产生的数量的目的。 文中给出模板匹配算法。 ( 2 ) 在大多数商业和科学领域中使用的数据库数据量非常大，通常应该对 数据进行一些预处理。本文提出可利用视图机制对原始数据进行预处理，把符 第8 页 山东大学硕士学位论文 合条件的数掘和有用的属性放入视图中。根据一维( l ) 和二维( k ) 中的频繁 数据项集对数据库中的属性进行过滤，以达到减少数据属性的目的，从而压缩 数据库中的数据，为提高关联规则挖掘算法的性能打下基础。 ( 3 ) 分析了利用f i s h e r 聚类方法对定量属性变量进行分段的方法，在处 理这种变量分段时考虑了数据间隔的大小及数据阳j 隔的稠密度，得到的定量 关联规则可以近似地反映规则中数据项集的关联性。 ( 4 ) 分析了基于关系操作的关联规则挖掘算法r s ( r e l a t i o ns e t ) 和广 义关联规则的算法g r s ( g e n e r a l i z e dr e l a t i o ns e t ) ，算法r s 将扫描空间分 为若干简单的较小分区，每个分区可以在内存中分别处理。算法r s 主要使用 简单的交操作，可用数据库系统中的s q l 语言表示，其主要优点是加快对多 维频繁数据项集的生成。 第9 页 山东大学硕士学位论文 2 数据挖掘简介 2 1 数据挖掘的起源 随着数据库技术的不断发展及数据库管理系统的广泛应用，数据库中存储 的数据量急剧增大，在大量的数据背后隐藏着许多重要的信息，如果能把这些 信息从数据库中抽耿出来，将为数据拥有者提供很多有价值的知识，例如，为 商业企业提高产品销售提供辅助决策等，数据挖掘的概念就是从这样的商业角 度引发出来的。 1 9 8 9 年8 月在美国底特律召开的第l l 届国际人工智能联合会议的专题讨论 会上首次出现k d d 这个术语。随后在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 ，而在工程领 域则称为数据挖掘。 数据挖掘研究的主要目标是发展相关的方法、理论和工具，以支持从大量 数据中提取有用的和让人感兴趣的知识和模式，可以帮助人们依据这种关联性 作出抉择和处理信息。数据挖掘意味着在一些事实或观察数据的集合中寻找模 式的决策支持过程。数据挖掘的对象可以是数据库，也可以是文件系统，或其 他任何组织起来的数据集合，例如w e b 信息资源。 2 2 数据挖掘的目的与过程 数据挖掘着眼于设计高效的算法以达到从海量数据中发现知识的目的。所 谓知识，从工程角度定义，就是有助于解决问题的有格式的，可复用的信息。 在传统的决策支持系统中，知识库中的知识和规则是有专家或程序人员建立的， 第1 0 页 山东大学硕士学位论文 是有外部输入的。而数据挖掘的任务是发现大量数据中尚未被发现的的知识， 是从数据内部自动获取知识的过程。 由数据挖掘所发现的知识的形式主要有：概念、规则、规律、模式、约束、 可视化等。 数据挖掘的一般过程 2 包括以下步骤： 图21 数据的挖掘过程 ( 1 ) 预处理数据。收集和净化来自各种数据源或数据仓库的信息，并加以存 储，一般是将其存放在数据仓库中。 ( 2 ) 模型搜索。利用数据挖掘工具在数据中匹配模型，这个搜索过程可以由 系统自动执行，自底向上搜索原始数据以发现它们之间的某种联系。也可以加 入用户交互过程，由分析人员主动发问，从下到上地寻找以验证假定的正确性。 对于一个问题的搜索过程可能用到许多模型，例如，神经网络、基于规则的系 统( 决策树) 、基于实例的推理、机器学习、统计方法( 聚类分析) 等。 ( 3 ) 评价输出结果。一般地说，数据挖掘的搜索过程需要反复多次，因为当 分析人员评价输出结果后，可能会形成一些新的问题或要求对某一方面做更细 致的查询。 第1 1 页 山东大学硕士学位论文 ( 4 ) 生成最后的结果报告和解释结果报告。对结果进行解释，依据此结果采 取相应的商业措施。 2 3 数据挖掘的任务分类 从不同的视角看，数据挖掘技术有几种分类方法 3 。根据发现知识的种类 分类、根据挖掘的数据库的种类分类和根据采用的技术分类。 ( 1 ) 根据发现知识的种类分类 这种分类方法有：总结( s u m m a r i z a t i o n ) 规则挖掘、特征( c h a r a c t e r i z a t i o n ) 规则挖掘、关联( 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 na n a l y s i s ) 等。如果以挖掘知识的抽象层次划分，又有原始层次 ( p r i m i t i v el e v e l ) 的数据挖掘、高层次( h i g hl e v e l ) 的数据挖掘和多层次 ( m u l t i p l el e v e l ) 的数据挖掘等。 ( 2 ) 根据挖掘的数据库分类 数据挖掘基于的数据库类型有：关系型( r e l a t i o n a l ) 、事务型 ( t r a n s a c t i o n a l ) 、面向对象型( o b j e c t e d o r i e n t i e d ) 、主动型( a c t i v e ) 、空间 型( s p a t i a l ) 、时间型( t e m p o r a l ) 、文本型( t e x t u a l ) 、多媒体( m u l t i m e d i a ) 、 异质( h e t e r o g e n e o u s ) 数据库和遗留( l e g a c y ) 系统等。 ( 3 ) 根据采用的技术分类 最常用的数据挖掘技术是： 1 ) 人工神经网络。它从结构上模仿生物神经网络，是一种通过训练来学 习的非线性预测模型。可以完成分类、聚类、特征挖掘等多种数据挖掘任务。 2 ) 决策树。用树形结构来表示决策集合。这些决策集合通过对数据集的 分类产生规则。典型的决策树方法有分类回归树( c a r t ) ，典型的应用是分类规 则的挖掘。 3 ) 遗传算法。是一种新的优化技术，基于生物进化的概念设计了一系列 的过程来达到优化的目的。这些过程有基因组合、交叉、变异和自然选择。为 了应用遗传算法，需要把数据挖掘任务表达为一种搜索问题而发挥遗传算法的 优化搜索能力。 4 ) 最近邻技术。这种技术通过k 个与之最相近的历史记录的组合来辨别 第1 2 页 山东大学硕士学位论文 新的记录。这种技术可以用作聚类、偏差分析等挖掘任务。 5 ) 规则归纳。通过统计方法归纳、提取有价值的i f - 一t h e n 规则。规则 归纳的技术在数据挖掘中被广泛使用，例如关联规则的挖掘。 6 ) 可视化。采用直观的图形方式将信息模式、数掘的关联或趋势呈现给 决策者，决策者可以通过可视化技术交互式地分析数据关系。 ( 4 ) 根据模式的实际作用分类 1 ) 分类模式。分类( c l a s s i f i c a t i o n ) 模式 4 5 6 是一个分类函数( 分类 器) ，能够把数据集中的数据项映射到某个给定的类上。主要功能是根据商业数 据的属性将数据分派到不同的组中。在实际应用过程中，分类模式可以分柝分 组中数据的各种属性，并找出数据的属性模型，确定哪些数据模型属于哪些组。 这样我们就可以利用该模型来分析已有数据，并预测新数据将属于哪一个组。 分类模式往往表现为一棵分类树，根据数据的值从树根开始搜索，沿着数据满 足的分支往上走，走到树叶就能确定类别。 2 ) 回归模式。回归模式的函数定义与分类模式相似，它们的差别在于分 类模式的预测值是离散的，回归模式的预测值是连续的。 3 ) 时间序列模式。时间序列( t i m es e q u e n c e ) 模式根据数据随时间变化的 趋势预测将来的值。这里要考虑到时间的特殊性质，像一些周期性的时间定义 如星期、月、季节、年等，不同的日子如节假日可能造成的影响，日期本身的 计算方法，还有一些需要特殊考虑的地方，如时间前后的相关性( 过去的事情对 将来有多大的影响力) 等。只有充分考虑时间因素，利用现有数据随时间变化的 一系列的值，才能更好地预测将来的值。 4 ) 聚类模式。聚类( c l u s t e r i 嘲模式 7 8 把数据划分到不同的组中，组之 间的差别尽可能大，组内的差别尽可能小。要分析的数据缺乏描述信息，或者 是无法组织成任何分类模式时，可以采用聚类模式。与分类模式不同，进行聚 类前并不知道将要划分成几个组和什么样的组，也不知道根据哪一( 几) 个数据 项来定义组。一般来说，业务知识丰富的人应该可以理解这些组的含义，如果 产生的模式无法理解或不可用，则该模式可能是无意义的，需要回到上阶段重 新组织数据。 5 ) 关联模式。关联( a s s o c i a t i o n ) 模式 9 1 0 1 1 1 2 主要是描述了一 第1 3 页 山东大学硕士学位论文 组数据项目的密切度或关系。关系或规则总是用一些最小置信度级别来描述的。 置信度级别度量了关联规则的强度。关联模式的一个典型例子是市场菜篮分析 ( m a r k e t i n gb a s k e ta n a l y s is ) ，通过挖掘数据派生关联规则，利用此规则可 以了解客户的行为。采用关联模型比较典型的案例是“尿布与啤酒”的故事。 在美国一些年轻的父亲下班后经常要到超市买婴儿尿布，超市也因此发现了一 个规律，在购买婴儿尿布的年轻父亲们中，有3 0 4 0 的人同时要买一些啤酒。 超市随后调整了货架的摆放，把尿布和啤酒放在一起，明显增加了销售额。同 样的，我们还可以根据关联规则在商品销售方面做各种促销活动。 6 ) 序列模式。序列( s e q u e n c e ) 模式 1 3 与关联模式相仿，而把数据之间 的关联性与时间联系起来。为了发现序列模式，不仅需要知道事件是否发生， 而且需要确定事件发生的时间。例如，在购买奶瓶的人们当中，6 4 的人会在 1 个月内购买奶粉。 在解决实际问题时，经常要同时使用多种模式。分类模式和回归模式是使 用最普遍的模式。分类模式、回归模式、时间序列模式也被认为是受监督知识， 因为在建立模式前数据的结果是己知的，可以直接用来检测模式的准确性，模 式的产生是在受监督的情况下进行的。一般在建立这些模式时，使用一部分数 据作为样本，用另一部分数据来检验、校正模式。聚类模式、关联模式、序列 模式则是非监督知识，因为在模式建立前结果是未知的，模式的产生不受任何 监督。 2 4 数据挖掘分析方法及工具 目前，国外有许多研究机构、公司和学术组织从事数据挖掘工具的研制和 丌发。这些工具主要采用基于人工智能的技术，包括决策树、规则归纳、神经元 网络、可视化、模糊建模等，另外也采用了传统的统计方法。这些数据挖掘工具 差别很大，不仅体现在关键技术上，还体现在运行平台、数据存取、价格等方 面。 根据所采用的技术，挖掘工具大致分为六类： ( 1 ) 基于规则和决策树( d e c i s i o nt r e e ) 的工具：大部分数据挖掘工具采 用规则发现和决策树分类技术来发现数据模式和规则，其核心是某种归纳算法。 它通常先对数据库中的数据进行挖掘，生成规则和决策树，然后对新数据进行 第1 4 页 山东大学硕士学位论文 分析和预测。决策树是通过一系列规则对数据进行分类的过程。采用决策树， 可以将数据规则可视化，其输出结果也容易理解。例如，在金融领域中将贷款 对象分为低贷款风险与高贷款风险两类。通过决策树，我们可以很容易地确定 贷款申请者是属于高风险的还是低风险的。比如说，如果某一个人的月收入 4 0 0 0 元，同时属于“高贷款”，将被认为是“低风险”人群。如果某一个人的 月收入 5 年，将被认为是“高风险”人群。决策树方法精 确度比较高，同时系统也不需要长时间的构造过程，因此比较常用。然而，采 用决策树方法也有其缺点。决策数方法很难基于多个变量组合发现规则。不同 决策树分支之间的分裂也不平滑。 ( 2 ) 基于神经元网络( n e u r a ln e t w o r k ) 的工具：基于神经元网络的工具由于 具有对非线性数据的快速建模能力，因此越来越流行。挖掘过程基本上是将数 据簇类，然后分类计算权值。神经网络的处理过程主要是通过网络的学习功能 找到一个恰当的连接加权值来得到最佳结果。其比较典型的学习方法是回溯法 ( b a c k p r o p a g a t i o n ) 。它通过将输出结果同一些己知值进行一系列比较，加权 值不断调整，得到一个新的输出值，再经过不断的学习过程，最后该神经网络 得到一个稳定的结果。神经网络系统也存在着如下问题：首先，神经网络对分 类模式比较适合。但是，神经网络的隐藏层可以说是一个黑盒子，得出结论的 因素并不十分明显。同时其输出结果也没有任何解释，这将影响结果的可信度 及可接受程度。其次，神经网络需要较长的学习时间，因此当数据量很大时， 性能可能会出现问题。 ( 3 ) 数据可视化( d a t av i s u a l i z a t i o n ) 方法：数据仓库中包含大量的数据， 并且充实着各种数据模型，将如此大量的数据可视化，需要复杂的数据可视化 工具。数据挖掘和数据可视化可以很好地协作。就数据可视化系统本身而言， 由于数据仓库中的数据量很大，很容易使分析人员变得不知所措，数据挖掘工 具可以设定通过富有成效的探索的起点并按恰当的隐喻来表示数据，为数据分 析人员提供很好的帮助。这类工具大大扩展了传统商业图形的能力，支持多维 数据的可视化，同时提供了多方向同时进行数据分析的图形方法。 ( 4 ) 模糊发现方法：应用模糊逻辑进行数据查询排序。 ( 5 ) 统计方法：这些工具没有使用人工智能技术，因此更适于分析现有信息， 第1 5 页 山东大学硕士学位论文 而不是从原始数据中发现数据模式和规则。 ( 6 ) 综合多方法：许多工具采用了多种挖掘方法，一般规模较大 1 4 。 工具系统的总体发展趋势是，使数据挖掘技术进一步为用户所接受和使用 另一方面也可以理解成以使用者的语言表达知识概念。 第】6 页 山东大学硕士学位论文 3 关联规则挖掘基本方法 在数据库的数据挖掘中，关联规则就是描述这种在一个事务中物品之间同 时出现的规律的知识模式。更确切的说，关联规则通过量化的数字描述物品甲 的出现对物品乙的出现有多大的影响。例如，在购买电脑的顾客中三个月内4 0 都会购买电脑视保屏，这样我们就可以利用这条规则对电脑视保屏进行促销。 3 1 关联规则的形式描述 超级市场利用前端收款机收集存储了大量的售货数据，这些数据是一条条 的购买事务记录，每条记录存储了事务处理时间，顾客购买的物品、物品的数 量及金额等。顾客的购买模式表现为某些商品之间存在的联系，顾客在购买了 某些商品的同时总是购买另外一些商品，为了便于问题的描述我们把这些商品 的名称称为项目。根据参考文献 1 5 1 6 ，关联规则的形式化描述 1 7 如下。 定义1 集合i = i ，i ：，i 。) 为标识符的集合，其中m 为整数，ik ( k = l 。2 ， m ) 称为项目。 项目是一个从具体问题中抽象出的概念。在超级市场的关联规则挖掘问题 中，项目表示各种商品，如牛奶、啤酒等；也可以表示一类商品，如女装商品 ( 包括各种品牌的外衣、内衣等多种商品) 。在其他领域的关联规则挖掘问题中， 项目可能有不同的含义。 由于在超级市场的关联规则挖掘中，并不关心顾客购买的商品的数量和价 格等。因此顾客的一次购物可以用该顾客所购买的所有商品的名称来表示，称 为事务，用符号t 来表示，很显然t i ( t 是i 的子集) 。一条事务仅包含其涉 及到的项目，而不包含项目的具体信息。所有事务的集合就构成了关联规则挖 掘的数据集，称为事务数据库，用符号d 来表示，事务数据库的记录数用jd 来表示。 定义2 项目集是由i 中项目构成的集合。若项目集包含的项目数为k ，则 称此项目集为k 项目集。 定义3 对任意项目集x ，若数据库d 中s 的事务包含项目集x ，则项目集 x 的支持率为，记为s u p p o r t ( x ) = s ，其中包含项目集x 的事务数称为项目集 x 的频度，记为c o u n t ( x ) = c 。若项目集x 的支持率大于或等于用户指定的最小 第1 7 页 由东大学硕士学位论文 支持率，剐项目集x 称为频繁项目集或大项目集，否则项霸粲x 称为非颓繁颈 | ；! | 集或小项目集。 定义4 关联j ；5 【! 则是形如x = y 的规则，其中x 、y 为项圈辍且x n y = m 。 定义5 在数搬露蚤中，若s 的攀务趣含x u ￥，鬟关联瓣；l | | x = y 豹支持发 为s ；在数据库d 中，若c 豹包含i 耍罄x 的事务篷包含项秘y ，鄹关联援剐x = y 的置信度为c 。 定义6 若关联规则x = y 的支持鹰和置信度分别大于戚等于用户指定的最 小支持度和最小置信度，则关联规则x = ￥为强关联援则：答则称为弱关联规剥。 在溪实羹赛中，普遍存在多缓匏疆念，攒强，枣时、分、移：雀巢奶粉慧 奶粉的一个分类等。在许多应用中，数据项集之间的有用豹关联规则常常出现 在相对较高的概念艨中。从较低概念层中很难发现有用的关联规则。考虑图3 1 所示的分类层，可熊很难在原始概念上挖撅出销售上海产的点心和销售青岛产 豹爵乐类之闽懿联系，瑟在鞍裹壤念鼷上褰易挖掘出镑售上海产翡点心秘镄餐 青岛产的可乐类之间的联系。但在较低概念层往往可以发现铰特殊和专门的信 息，如：也许有销俺上海产的点心和销售青岛的可乐类之间的联系。在给定的 概念层中关联规则挖掘重点在较高概念滕，同时又不放弃较低概念层中的有用 规则。在多级概念鼷上关联规则挖掘楚关联规则挖掘的一个燕要的内容，称作 携掇广义关联蕊粼。 幽3 1艨次分类日倒 簿1 8 页 山东大学硕士学位论文 3 2 关联规则挖掘的目的与任务 在给定的交易集中，发现所有的强关联规则，这些规则的支持数和置信度 分别高于用户定义的最小支持数( m i n s u p ) 和最小置信度( m i n c o n f ) 。 可以将关联规则挖掘的任务分解为以下的两步： ( 1 )找出所有的数据项频繁集。给定m 个数据项，就有2 m 一1 个潜在的频繁 数据项集。需要有效的方法从这些潜在的数据项集中，枚举出所有的数 据项频繁集。 ( 2 )使用数据项频繁集产生强关联规则。例如：如果有a b c d 和a b 是数据项 频繁集，可以通过计算c o n f = s u p p o r t ( a b c d ) s u p p o r t ( a b ) 决定规则 a bj c d 是否成立。如果c o n f 一 m i n c o n f ，那么规则a bjc d 为强关 联规则。 下面是一个超市销售数据库中关联规则挖掘简例。设有4 个不同的数据项 组成一个集合i = ( 甲，乙，丙，丁】，i 中的数据项甲、乙、丙、丁为商品名称。 设销售数据库中包含购买这四种商品的顾客，图3 2 给出了数据库中的部分交 易记录，图3 3 给出至少出现在三条以上顾客交易中的所有频繁数据项集。图 3 4 给出该销售数据库中的关联规则，其中最小置信度为1 0 0 。 交易标识符数据项集 t 1 甲乙丁 t 2 乙丙丁 t 3甲乙丁 t 4甲乙丙丁 t 5 甲乙丙丁 t 6 乙丙 支持数数据项集 6乙 5丁，乙丁 4 甲，丙，甲乙，甲丁， 乙丙，甲乙丁 3 丙丁，乙丙丁 图3 2 销售数据库中部分交易记录图3 3 销售数据库的频繁数据项集 图3 4 销售数据库中的关联规则 第1 9 页 山东大学硕士学位论文 3 3 关联规则挖掘算法a p r io r i a p r i o r i 算法 16 1 8 是在给定的数据库中对特定长度的数据项集进行计 数的迭代算法。该算法首先扫描数据库中的全部交易，计算一维频繁数据项集。 接着，利用一维频繁数据项集构造可能是二维频繁数据项集的候选数据项集。 再次扫描数据库，对二维候选数据项集进行计数，如果某个候选数据项的支持 数大于用户定义的最小支持数，那么将该候选数据项确定为二维频繁数据项集。 重复以上过程，直到枚举出所有的数据项集。a p r i o r i 算法有三个主要步骤： ( 1 ) 利用( k 1 ) 维频繁数据项集f 。中产生k 维候选数据项集c 。例如： f 产 1 2 ，1 3 ，1 4 ，1 5 ，2 3 ，2 4 ，2 5 ，则c 产 1 2 3 ，1 2 4 ，1 2 5 ，1 3 4 ， 1 3 5 ，1 4 5 ，2 3 4 ，2 3 5 ，2 4 5 1 。 ( 2 ) 如果候选集中至少有一个子集不是频繁数据项集，则删除该数据项 集合。例如，因为3 4 不是频繁数据项，所以可以将1 3 4 ，2 3 4 删除。 经过删除后，可以得到一个数据项集合c 。： 1 2 3 ，1 2 4 ，1 2 5 ) 。 ( 3 )候选数据项集组成h a s h 索引，通过h a s h 索引可以快速查出支持该 数据项的交易集，从而获得其支持数。 l ，= l a r g e 卜i t e m s e t s ) ： f o r ( 膏= 2 ：l h