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

摘要 “数据爆炸、知识贫乏”是信息时代所面临的一个严峻的问题，数据挖掘是解决该问 题的一种十分有效的手段。数据挖掘就是数据库中的知识发现，是从海量数据信息中挖 掘出潜在、有用知识的过程。该技术能发现隐含的、先前未知的、对决策有潜在价值的 知识以指导实际问题的求解，因此对数据挖掘技术的研究有着重要的应用意义。 本课题着重对关联规则挖掘算法进行了研究，详细探讨了关联规则挖掘中经典的 a p f i o f i 算法，介绍了它的基本原理，存在的不足和算法发展的瓶颈。针对算法的缺陷介 绍了已经存在的改进算法，如采样方法、划分方法和散列方法等。然后对a p n o d 算法 的两个主要不足之处，即产生大量候选集和大规模数据库在挖掘过程中保持不变，介绍 三种方法，以求能降低算法的时间复杂度。 1 、减小候选集算法。挖掘过程中产生大量候选集，在访问数据库统计候选集的支 持数之前，运用新的算法减小候选集数目，从而减小访问数据库的次数。 2 、精简数据库算法。随着挖掘过程的不断深入，数据库中有些数据记录可能不再 需要，因而我们可以删除无用的数据记录。不断减小数据库的规模，减小访问数据库的 次数。 3 、数据的垂直表示方法。扫描数据库得到频繁一项集，同时将数据从水平格式变 成垂直格式，此后的频繁集产生不再需要访问数据库。 关键词：数据挖掘，关联规则，a p n o d 算法，候选项目集，频繁项目集 a b s t r a c t “d a t ae x p l o s i o n ，p o o rk n o w l e d g e ”i sas e r i o u sp r o b l e mi nt h ei n f o r m a t i o na g e ，d a t a m i n i n gi sav e r yu s e f u lm e t h o dt os o l v et h ep r o b l e m d a t am i n i n gi sd e f i n e da sf i n d i n g k n o w l e d g ef r o md a t a b a s e ，w h i c hi sak i n do fp r o c e s st h a tr e v e a l sp o t e n t i o nu s e f u lk n o w l e d g e f r o mm a s s i v ed a t a i tc a nf i n dt h eh i d d e n ，p r e v i o u s l yu n k n o w ni n f o r m a t i o nw h i c hh a st h e p o t e n t i a lv a l u ew h e nm a k i n gd e c i s i o n s s or e s e a r c h i n go nd a t am i n i n gt e c h n o l o g yi sv e r y s i g n i f i c a n ti nt h ef i e l do fa p p l i c a t i o n t h i sd i s s e r t a t i o ns t u d i e sm a i n l yo nm i n i n ga l g o r i t h mo fa s s o c i a t i o nr u l e ，d i s c u s s e st h e c l a s s i c a lm i n i n ga l g o r i t h m ，a p r i o r ia l g o r i t h m ，i n t r o d u c e si t sb a s i cp r i n c i p l e ，e x t i s t e dd r a w b a c k s a n db o t t l e n e c k s m e a n w h i l e ，s e v e r a li m p r o v e da l g o r i t h m s ，s u c ha ss a m p l i n ga l g o r i t h m ， p a r t i t i o na l g o r i t h ma n d h a s ha l g o r i t h m ，a r ei n t r o d u c e df o ro v e r c o m et h i sb o t t l e n e c k s a p r i o r i a l g o r i t h mh a st w om a i nd r a w b a c k s o n ei sp r o d u c i n gm o s to fc a n d i d a t ei t e ms e t s i nt h e p r o c e s so fm i n i n g t h eo t h e ri st h a tt h es c a l eo fd a t a b a s er e m a i n su n c h a n g e di nt h ec o u r s eo f m i n i n g t h e nb a s e do nt h i sd r a w b a c k s ，t h r e em e t h o d sh a v eb e e ni n t r o d u c e di no r d e rt o d e c r e a s et h et i m e so fs c a n n i n gd a t a b a s e 1 t h ea l g o r i t h mo fr e d u c i n gc a n d i d a t ei t e ms e t s l a r g en u m b e ro fc a n d i d a t es e t sw i l l b ep r o d u c e di nt h ec o u r s eo fm i n i n g ，n e wa l g o r i t h mc a nr e d u c ec a n d i d a t es e t ss ot h a td e c r e a s e t h en u m b e ro fa c c e s s i n gd a t a b a s e 2 h ea l g o r i t h mo fr e d u c i n gt h es c a l eo fd a t a b a s e w i t hd e e p e n i n go fm i n i n g ，s o m e r e c o r d si nd a t a b a s ea r en o tn e e d e da n ym o r e ，s ot h e s er e c o r d sc a nb ed e l e t e d a sar e s u l t ，t h e s c o p eo fd a t a b a s ew i l lb ed e c r e a s e dg r a d u a l l y 3 v e r t i c a ld a t aa l g o r i t h m w h i l es c a n n i n gd a t a b a s ef o ro n ef r e q u e n ti t e ms e t s ，d a t a f o r m a tc a nb ec o n v e r t e df r o ms t a n d a r ds t y l et ov e r t i c a ls t y 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 s ，a p r i o r ia l g o r i t h m ，c a n d i d a t ei t e ms e t ， f r e q u e n ti t e ms e t 论文独创性声明 本人声明：本人所呈交的学位论文是在导师的指导下，独立进行研究工 作所取得的成果。除论文中已经注明引用的内容外，对论文的研究做出重 要贡献的个人和集体，均己在文中以明确方式标明。本论文中不包含任何 未加明确注明的其他个人或集体已经公开发表的成果。 本声明的法律责任由本人承担。 敝作者硌店毗午 必年6 月1 日 论文知识产权权属声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归属学 校。学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权 利。本人离校后发表或使用学位论文或与该论文直接相关的学术论文或成 果时，署名单位仍然为长安大学。 ( 保密的论文在解密后应遵守此规定) 一：乓嗍午 导师签名：孤洳， 铅年石月1 日 矿占年6 月了日 长安人学硕士学位论文 1 1课题的目的和意义 第一章绪论 今天我们进入了信息时代，信息对社会的发展起到了至关重要的作用。对一个企业 而言，信息量的大小以及是否合理利用关乎一个企业的发展前景。由于企业业务的发展， 海量的数据信息随之出现，人们需要对数据信息进行深层次的处理，从中找出关联和模 式，以便利用数据进行更好的决策和研究。目前的数据库系统无法发现数据中存在的关 联和规则，无法根据现有的数据预测将来的发展趋势，从而出现了一种奇怪的数据爆炸 但知识匮乏现象。面对“人们被知识淹没，但饥渴于知识”的挑战，数据挖掘和知识发现 技术应运而生。数据挖掘技术将逐渐运用于数据库和数据仓库的知识发现过程中。 数据挖掘就是数据库中的知识发现，是从海量数据信息中挖掘出有趣知识的过程。 对数据挖掘有多种类似的定义，其中比较权威的是加拿大j i a w e ih a n 教授提出的数据挖 掘是从大量的、不完全的、有噪声的、模糊的、随机的数据中提取隐含在其中的：人们 事先不知道的、但又潜在有用的信息的知识的过程【l 】。提取的知识表示为概念、规则、 规律、模式等形式。数据挖掘主要是从数据库中发现合理的、新奇的、有用的、可理解 的模式的过程。 数据挖掘是一门交叉学科，涉及数据库、人工智能、数理统计、并行计算、可视化 等多方面的知识。它和人工智能相结合，利用人工智能的一些成熟算法如遗传算法、神 经网络、决策树、关联规则、粗糙集等方法。数据挖掘的主体是发现合适的算法，对数 据进行挖掘，从而发现有趣的知识。数据挖掘过程是一个深层次的数据分析，其核心部 分是建立数据模型的过程，不同的挖掘方法建立数据模型的方式也不同，进行数据挖掘 时可采取多种方法，比如：关联规则发现，决策树，神经网络，遗传算法和可视化技术 等。数据挖掘的应用极其广泛，数据挖掘发现的知识可以应用于信息管理、决策支持、 工程控制能领域，也激发了相关多个行业专家的浓厚兴趣。针对特定领域的应用，人们 研发了许多专用的数据挖掘工具，包括天文学、生物医学、医疗保健、d n a 分析、银 行、金融、超市等。 关联规则算法是数据挖掘的重要研究课题，该问题自从1 9 9 3 年被a g r a w a l 等提出 来以来一直受到广泛关注，成为近几年来的研究热剧2 1 。对关联规则的需求最早来之于 超市，比如大家熟知的啤酒尿布关联，利用关联规则可以找出不同商品项之间的关系， 第一章绪论 通过这些规则找出顾客的购买习惯，指导商家制定营销策略，提高超市的营业额。在关 联规则挖掘算法中一种广为人知的就是a p r i o r i 算法，a g r a w a l 等人1 9 9 3 年提出a p r i o r i 算法之后，1 9 9 4 年又提出了改进算法a p r i o r i t i d l 3 】。这些算法的基本思想都是基于频繁 项目集的，关键问题是找出满足由于最小支持度要求的频繁项目集。算法有两个主要缺 陷，在求频繁项目集的过程中：一个方面是产生大量侯选集，尤其是第二侯选集的数量 过大就会造成后面的项集呈指数级增长；另外一个方面，频繁访问数据库，使得需要数 据到内存的多次i o 操作及事务记录和项集之间多次的比较检索都需要大量时间。本课 题对a p r i o r i 算法及其改进算法进行详细研究，在此基础上针对算法的不足之处，介绍 新的策略方法，力求减小原算法访问数据库的次数，减小算法时间。 1 2 国内外研究历史和现状 从1 9 9 3 年a p r i o r i 算法提出以后得到广泛关注和研究，随之出来相关的多种改进算 法。 1 并行发现算法 并行关联规则的数据挖掘算法有：a g r a w a l 等人提出的c d ( c o u n td i s t r i b u t i o n ) 、 c a d ( c a n d i d a t ed i s t r i b u t i o n ) 和d d ( d a t ad i s t r i b u t i o n ) 掣4 1 。 2 增量式更新算法 这种算法有两类，一类是由华中理工大学冯玉才等提出的两种高效的增量式更新算 法i u a ( i n c r e m e n t a iu p d a t i n ga l g o r i t h m ) $ up i u a ( p a r a l l e li n c r e m e n t a iu p d a t i n ga l g o r i t h m1 这类算法中心一点是数据库不变，但挖掘中用到的两个参数最小支持度和最小置信度不 断调整，从而得到用户感兴趣的关联规则。 由d a v i dw c h e u n g 等提出的增量式关联规则的挖掘算法对传统a p r i o f i 算法进行了 改进。这个与上一个是相反的，它是最小支持度和最小置信度不变，改变数据库，当一 个新的数据库加入到原来的数据库，如何生成合成数据库的关联规则问题【5 1 。 3 多属性值关联规则挖掘 关联规则可分为布尔型关联规则和多值性关联规则。多值属性又分为数量属性和类 别属性。但是目前多数情况下还是将多值性转换为布尔型，即将多值属性的值划分为多 个区间，每个区间算作一个属性，将类别属性的每一个类算作一个属性【6 1 。 4 多循环式的挖掘算法 2 长安大学硕士学位论文 此类算法包括a g r a w a l 等人提出的a p r i o r i 、a p r i o r i t i d 、a i s ，p a r k 等人提出的 d h p ，s a v a s e r e 等人的p a r t i t i o n 以及t o i v o n e d 提出的s a m p l i n g 等。此类算法是现在数据 挖掘的研究重点，得到广泛运用。主要的原理是对数据库进行多次扫描，第k + 1 次扫描 时利用第k 次扫描的结果。在后面的章节将陆续提到此类算法及改进措施【_ 7 1 。 5 多层关联规则挖掘 在许多实际应用中，由于数据库中的数据过于具体，使得挖掘的项目集没有足够的 支持度，从而造成用户感兴趣的强关联规则很难得到。另外，如果用户需要更抽象的概 念，但由于概念层次在要挖掘的数据库中是不存在的，因此数据挖掘需要提供一种在多 个抽象层次进行数据挖掘的功能，并可在不同层次进行转换。目前也有一些这样的算法， 如m lt 2 l 1 及m lt 1 l a 、m lt m l l 、m lt 2 l a 等【。 6 基于约束的关联规则挖掘 基于约束的关联规则挖掘是在提供布尔表达式约束条件情况下的挖掘算法。这种布 尔表达式可以让用户指定其感兴趣的关联规则集合，比如有的挖掘算法加入利润属性， 从而在商业挖掘中能得到更合理的数据信息。这种约束不仅可以对数据库进行预处理， 而且可以运用于挖掘算法中，从而提高算法效掣引。 1 3 课题的研究内容 本课题的主要工作是： 1 充分研究与分析现有的基于频繁项目集的数据挖掘算法，及其改进措施和不足 之处。 2 在现有算法的基础上，针对出现的两个瓶颈问题提出解决策略。主要有以下几 点： ( 1 ) 减小候选集的数目 ( 2 ) 数据挖掘过程中数据库的不断精简，从而不断降低查询时间 ( 3 ) 数据库中事务新的组织方式，垂列式的使用，减小访问数据库的次数 3 根据改进措施给出新的挖掘算法，运用事务记录验证算法。 1 4 论文的组织 第一章为绪论，介绍了论文的研究目的和意义，主要讨论了数据挖掘技术国内外的 研究现状，以及本文所研究的重点。 3 第一章绪论 第二章系统介绍了数据挖掘的概念与相关技术。首先详细讨论了数据挖掘的定义和 数据的预处理过程；最后讨论了数据挖掘的商业应用和面临的挑战。 第三章主要讨论关联规则。首先详细介绍了关联规则的概念和性质，接下来给出了 关联规则挖掘过程的步骤。最后重点讨论了关联规则挖掘的典型算法，以及算法的效率 和优缺性。 第四章重点讨论传统的a p r i o r i 算法。详细介绍了算法原理，运用实例实现算法， 分析算法存在不足。然后针对算法存在的缺陷介绍一些已经存在的改进算法，如采样、 散列和划分等。 第五章，针对上一章提到的a p r i o r i 算法的缺陷，通过自己的研究理解，介绍三个 新算法，并举例分析新算法。关联规则数据挖掘是一个新兴热门的研究课题，在商业中 得到越来越多地应用，随着研究和实践的不断深入，会有更多、更优化的算法不断涌现。 最后对论文所作的工作进行了总结，并对今后的研究方向和进一步工作做出展望。 1 5 本章小结 数据挖掘技术是一个新兴的领域，它的商业价值逐渐的被大家所认可。本章详细介 绍了数据挖掘技术的历史和现状以及它的商业价值。提到了数据挖掘算法存在的瓶颈， 针对不足之处提出自己的意见。 4 长安火学硕上学位论文 第二章数据挖掘概述 面对信息时代出现的大量数据信息，需要能够对其进行更深层次的分析，从中找出 隐藏的重要信息。但是由于缺乏相应的挖掘算法，导致了数据爆炸但知识匮乏。于是人 们尝试在传统的数据库管理系统中引入机器学习的方法来分析数据，挖掘出大量的潜在 的知识，这就是数据库中的知识发现，成了近几年来人工智能和数据库应用领域的研究 热点。 2 1 数据挖掘概念 数据挖掘起源于8 0 年代末期的“在数据库中的知识发现”，1 9 8 9 年8 月份召开了一 次关于数据挖掘和知识发现的国际研讨会，1 9 9 5 年在加拿大召开了首届知识发现和数据 挖掘的国际性会议( i d 9 5 ) ，1 9 9 8 年在新加坡举行了首届亚太数据挖掘会议。迄今 为止，由美国人工智能协会主办的k d d 国际研讨会议召开了多次，规模也不断扩大， 从原来的发现方法逐渐趋向于系统应用，注重多策略和技术的集成，以及多学科的相互 渗透【9 】。尤其是这几年许多企业也意识到数据挖掘己成为提高公司决策能力增加企业效 益的一个重要方面。数据挖掘发现的知识可以应用于信息管理、决策支持、工程控制能 领域，也激发了相关多个行业专家的浓厚兴趣。 数据挖掘就是数据库中的知识发现，是从海量数据信息中挖掘出有趣知识的过程。 数据挖掘是- i 7 交叉学科，涉及数据库、人工智能、数理统计、并行计算、可视化等多 方面的知识。它和人工智能相结合，利用人工智能的一些成熟算法如遗传算法、神经网 络、决策树、关联规则、粗糙集等方法进行信息的挖掘提取。 对数据挖掘有多种类似的定义，其中比较权威的是加拿大j i a w e ih a n 教授提出的 数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的数据中提取隐含在其中的、 人们事先不知道的、但又潜在有用的信息的知识的过程。提取的知识表示为概念、规则、 规律、模式等形式。数据挖掘主要是从数据库中发现合理的、新奇的、有用的、可理解 的模式的过程。其主体是发现何时的算法，对数据进行挖掘，从而发现有趣的知识。 5 第二章数据挖掘概述 2 2 数据来源和数据预处理 数据挖掘就是处理数据的，然而自然界的数据多种多样，面对形式各异的数据，转 换数据格式变成适于数据挖掘的数据格式。另外好多数据是完全的、有噪声的，在挖掘 之前要先对数据进行处理。 2 2 1 数据挖掘的数据来源 数据挖掘依赖的数据源多种多样，有关系型数据库、事务型数据库、文本数据库等。 目前，数据挖掘处理的数据主要来之于数据库和数据仓库【10 1 。 1 关系型数据库 随着企业业务量的增加，不仅数据规模不断变大，数据格式也会发生变化，因而在 对其进行数据挖掘之前需要进行必要的处理。 2 数据仓库 随着大量数据的产生，数据仓库已成为数据挖掘技术的一个重要的数据来源。数据 仓库中的数据在入库之前已进行了数据清理，解决了一致性问题，这样在进行数据挖掘 时就没必要进行清理了。 在数据挖掘之前通常要把数据仓库中的数据取到数据库中或数据集市中，数据挖掘 库可能是数据仓库的一个逻辑子集，也可能是一个单独建立的数据挖掘库。 3 事务数据库 由于一个的数据仓库的建立是一个巨大的工程，所以如果仅为了数据挖掘，通常是 建立一个只读的数据挖掘库将相关的事务数据库包括进来，作为数据集市来进行挖掘。 2 2 2 数据准备与预处理 1 几种常用的几种数量属性划分方法 由于数量属性通常都包含无限多个值，所以要把连续属性离散化，通常的做法是把 数量属性值划分为若干区间，主要有如下几种划分方法【1 1 】。 ( 1 ) 等宽法 等宽法实际上是一种静态离散化方法，它是人们根据一定的先验知识，将属性值固 定地划分为几个区间，每个区间的宽度相等。如数量属性a g e ，其取值范围为1 到1 0 0 ， 则可将区间划分为四个区间 1 ，2 5 ， 2 6 ，5 0 ， 5 1 ，7 5 ， 7 6 ，l o o 。 6 长安大学硕士学位论文 这是最简单、最原始的方法，操作起来很方便，但是这种方法首先需要先验知识， 这就要求相应的领域专家地参与，但并不是都可找到相应的领域专家。 ( 2 ) 等深划分 等深划分法是由f u k u d a 等人提出来的，这种方法是把每个属性值划分为n 个区间， 每一个区间包含大致相同的样本个数。例如，根据等深度划分思想将储户的存款额划分 为若干区间，使得每个区间的储户人数大致相等。 ( 3 ) 部分k 度完全方法 在把数量属性划分为几个区间的过程中，会导致如下两个问题： 1 ) 过小支持度 划分的区间数目过多，则支持每个区间的记录数减少，区间的支持度下降，很多项集 都因为支持度小于m i n i s u p p o r t 而被删除掉，因此不能有效地生成全部频繁项集。 2 ) 过小置信度问题 若划分的区间的数目过少，则支持区间的元组数目增加，包含区间的频繁项集的支 持度上升，但在频繁项集的子集支持度不变的情况下，将导致右端包含该子集的规则置 信度下降，若不能达到置信度阈值，就会造成信息丢失。 ( 4 ) 转化为模糊集方法 把数量属性转化为k 个模糊集合，每个集合的隶属函数由相应领域的专家给定。如 对于a g e 属性，其值域为1 到1 0 0 ，则可把它表示为四个模糊集合 少年、青年、中年、 老年，。 上述的四种方法中，前三种方法都是把属性值划分为区间，这样就会使区间的边界 过于“僵硬”，而且同一区间中的数据不一定都有相同的行为。最后一种方法采用模糊集的 方法软化了区间的边界，但其隶属函数需要预先给定，而且不是依照数量属性本身来给 定，则带有很大的主观性，另外，并不一定会找到相应的专家给出其隶属函数。 2 属性映射 无论是把属性划分为区间，还是把属性划分为模糊集，都要将属性映射为具体的值， 就是把连续值离散化，然后再把它转化为布尔关联规则挖掘【l l 】。下面给出一个超市管理 系统中顾客关系表单： 下面这个表单，包含两个数量属性字段，年龄和收入，一个字符属性字段，性别，按 如下步骤进行属性映射： 7 第二章数据挖掘概述 表2 1 数值属性关系表 记录号年龄性别年收入( 万) 0 0 12 6 男 4 5 0 0 22 4 男 2 2 0 0 33 6 女 6 5 0 0 44 2 男 1 2 0 0 5 5 8 女 7 8 采用一种划分方法将数量属性划分为区间或变成模糊集。在本例中采用等宽方法将 其划分为区间，把年龄划分为4 个区间，年收入划分为五个区间，把每个区间用不同的 映射值替代： 表2 2 年龄表2 3 年收入 替代值区间段 11 0 2 5 22 6 3 5 33 6 5 5 45 6 8 0 替代值区间段 1 小于等丁2 5 2 大于2 5 小于等于5 3 人于5 小于等于7 5 4 大于7 5 小于等于1 0 51 0 万以上 在这里把年龄按这个区间划分是因为顾客的购买行为和他的年龄有关，也和不同阶 段的身份有关。小于2 5 岁的一般都是没有收入来源的学生，2 6 到3 5 岁之间的青年人的 购买习惯和3 6 到5 5 之间的中年人不同，5 6 岁以上的老年人的购买力会明显下降。 对性别字段，用1 代表男，2 代表女。则转换后的关系表如下： 表2 4 性别字段映射表 记录号年龄性别年收入 121 。 2 211l 3323 4315 5424 3 转化为布尔关联规则挖掘 将数量属性划分为若干个区间或模糊集合，视每个区间或模糊集合为一个属性，在 一个记录中，若该属性对应的值属于某个区间或某个模糊集合，则取1 ，否则取0 。如 以下数据库中，把年龄属性划分为4 个区f b j i o ，2 5 ， 2 6 ，3 4 ， 3 6 ，5 4 1 ， 5 6 ，8 0 ， 对应于0 0 1 记录，其年龄为2 6 ，2 6 在 2 6 ，3 5 区间中，则该位置取1 ，而在 1 0 ，2 5 ， 3 6 ，5 5 】， 5 6 ，8 0 中，则取0 。将数量属性关系表转化成布尔关系表： 8 长安火学硕l 学位论文 表2 5 年龄字段布尔表 记录号年龄( 1 0 2 5 )年龄( 2 6 3 5 )年龄( 3 6 5 5 )年龄( 5 6 8 0 ) 0 0 1o1 0 0 0 0 21oo0 0 0 3oo1o 0 0 4 0o10 0 0 50o 0 1 表2 6 年收入字段布尔表 大于2 5 小于大于5 小于等大于7 5 小于 记录号2 5 以下1 0 以上 等于5于7 5 等于1 0 0 0 1ol0o0 0 0 2l0ooo 0 0 3 0o1o0 0 0 4000o1 0 0 500010 2 3 数据挖掘方法 数据挖掘有多种方法，例如分类分析、聚类分析、关联分析、粗糙集、模糊理论、 序列模式分析和可视化等忆13 1 。 1 关联分析 关联分析最常用到的就是关联规则挖掘。关联规则是19 9 3 年由a g r a w a l 等人在对 超市购物篮问题( m a r k e tb a s k e t a n a l y s i s ) 分析时首次提出的，用以发现商品销售中顾 客的购买模式，是数据中一种很实用的规则。关联规则挖掘( a s s o c i a t i o nr u l em i n i n g ) 是数据挖掘的一个重要分支，近几年来别广泛关注，越来越多被运用于商业领域。 关联类型算法有两个任务，首先找出频繁项集，然后由频繁项集得到关联规则。在 这里举个例子说明超市商品之间的关联性。一个典型的规则： 商品= “百事可乐”，商品 = “薯片”lj 商品= “果汁”，概率为8 0 。这个规则很明显：如果一个顾客买了百事可乐 和薯片，则有8 0 的可能性买果汁。 关联规则发现的趋势是从单一概念层次关联规则的发现发展到多概念层次的规则 的发现，即在具体应用中挖掘算法可作用到数据库的不同层次上。比如在分析超市的销 售情况时，可以发现更深层的关联信息，如从食品到家电等。随着人们对关联规则算法 的不断研究改进，算法的效率逐渐提高。 2 分类分析 9 第二章数据挖掘概述 分类分析是对数据库中的一组对象进行分析，找出其共同属性，构造分类器，然后 利用分类器对其他对象进行分类预测。若预测的变量是离散的，这类问题就是分类；若 预测的变量是连续的，则称之为回归。分类和回归都可用于预测，即根据历史数据构造 出分类模型，然后借助于分类模型自动预测未来数据。 构造分类模型，需要一个训练样本集( t r a i n i n gs e t ) 作为输入数据，分类的过程为： 给定一个训练集集合t ，数据库t 中每个元素由若干个属性值描述。其中有一个主关键 字用来唯一标识一个记录。属性集合用矢量x = ( x l ，x 。) 表示，其中每个属性有不同的 值域，即x i = x l ，x m ，用c 表示类别属性，c = c 1 ，c k ) ，即数据集有k 个不同的类 别。那么，这时候一个影射函数h 就确立了，它是从矢量x 到类别c 的隐含映射函数： h ：f ( x ) j c ，分类的目的就是找出隐含函数h 。 在分类分析中，构造分类器有多种方法，如：神经网络方法、统计方法和机器学习 方法等。神经网络方法主要用到的是b p 网的算法，即在多层前向神经网络中的误差反 馈思想。该算法的本质是一种非线性判别函数。统计学的方法包括非参数法( 邻近学习 或基于事例的学习) 和贝叶斯法，对应的知识表示为判别函数或事例原形。机器学习方 法包括规则归纳法和决策树法，规则归纳法一般为产生式规则。另外，后来又出现了一 种粗糙集方法，将知识表示为产生式规则。 3 聚类分析 聚类分析是把一组事务或对象按相似性归为若干类别，也成为“无监督分类”。理想 的目标就是尽可能的增加内聚力，减小外联性。即同一类别对象之间的距离尽可能的小， 不同类别对象之间的距离尽可能的大。然而对复杂的多维数据( 数据仓库里的大量数 据) ，数据点的分布不会太均匀，此时聚类分析要找到稀疏或稠密的位置，近而发现整 个数据空间的分布模式。当要分类的数据用分类方法无法组织成任何模式或所处理的数 据描述信息很少，这时利用聚类分析就可很容易的得到类别结果。 与分类分析一样，聚类分析所采用的方法也是统计方法，神经网络方法以及机器学 习方法。统计方法是基于几何距离的，是一种基于全局比较的方法，要求所要处理的数 据必须事先给出，不能动态生成。对于每一次聚类决策，对于所有的数据或己存在的聚 类都同等对待，忽略其距离的远近。这种方法要考察所有的对象才能决定类的划分，因 此复杂度较高。神经网路中一种主要的聚类方法是无监督自学习方法。如k o h o n e n 自组 织特征映射方法和竞争学习网络。而在机器学习中，分类的样本没有类别标识，学习的 数据需要聚类学习算法自主确定。 1 0 长安大学硕上学位论文 常用的聚类分析算法有：层次法、分裂法、基于网络的方法、基于密度的方法和基 于模型的方法等。 聚类分析用途很广，在生物学领域，可用于研究生物的分类。在网络中对不同的类 型文档分类。在商业领域对消费者进行分类等等。聚类分析作为数据挖掘的一种方法可 以进行数据挖掘，也可以与其他数据挖掘算法一起使用，作为一个预处理过程。 4 序列分析及时间序列 序列分析用于发现离散序列中的模式。序列有一串离散值( 或状态) 组成。例如： d n a 序列是由a 、g 、c 和t ，4 种不同的状态组成的长序列。w e b 点击序列包含一系 列u r l 地址。客户购买商品的次序也可以建模为序列数据。例如，某用户先买了一台 电脑，然后买了一个扬声器，最后买了一个w e b c a m 。序列数据和时间序列数据都是连 续的观察值，这些值是相互依赖的。它们的区别是序列包含离散的状态，而时间序列包 含的是连续的数值。 序列和关联数据有点相似，它们都包含一个项集或一组状态。序列模型和关联模型 区别在于：序列模型分析的是状态的转移，关联模型认为在客户购物车中的每个商品都 是平等的和相互独立的。通过序列模式可知，先买扬声器再买电脑和先买电脑再买扬声 器是两个不同的序列。但是如果使用关联算法，则认为它们是相同的项集。 序列分析是一种相对较新的挖掘任务，主要由于存在两种运用：w e b 日志分析和 d n a 分析。目前有几种不同的序列分析技术可用，例如m a r k o n 链，研究人员正在研究 这个领域中的新算法。 5 偏差分析 偏差分析是为了找出一些特殊的事例，这些事例的行为与其他事例有明显的不同， 偏差分析也叫孤立点( o u t l i e r ) 检测，它用来检测与前面观察的行为有重大改变的行为。 偏差分析可以在许多应用中使用。最常见的是信用卡欺诈行为检测，但是从数百万个事 例中鉴别出异常情况是一件非常困难的事。其他的应用包括网络入侵检测，劣质产品分 析等等。 目前还没有标准的偏差分析技术，它仍然是一个热门的研究方向。一般情况下，分 析员利用改进的决策树算法、聚类算法或者神经网络算法解决这类问题。为了得到重要 的规则，分析员需要在数据集中将异常情况忽略掉( 或进行特殊处理) 。 6 可视化技术 第二章数据挖掘概述 可视化技术是指用图形、图像方式来显示知识，是数据挖掘中一种重要的技术。它 拓展了传统图表的功能，使用户对数据的理解更清楚。通过可视化技术可以把数据库中 的多维数据转化为多种图形，从而可以更明了、深刻地理解数据。 可视化数据挖掘可分为数据可视化、挖掘结果可视化、挖掘过程可视化和交互式数 据可视化等。 7 粗糙集方法 粗糙集理论( r o u g hs e tt h e o r y ) 用来描述数据的不完全性和不精确性。 基本思想是将数据库中的属性分为条件属性和结论属性，对数据库中的记录根据属 性值分类，然后给予条件属性值划分得子集于基于结论属性值划分得子集间的上下近似 关系生成判定规则。 粗糙集的方法与传统的统计、模糊集的方法不同之处是它只依赖数据内部的知识， 用数据间的关系表示不确定性。而后者依赖先验知识对不确定性的定量描述，如统计分 析中的先验概率、模糊集理论中的模糊度等。用粗糙集处理不确定性问题的最大优点是 不需要数据的预先信息。 2 4 数据挖掘的体系结构与步骤 数据挖掘系统由几个模块组成，如数据挖掘模块、用户交互模块和数据库接口等。 数据挖掘的过程大体可分为四个阶段，分别为：问题定义( t a s kd e f i n i t i o n ) 、数据准 备( d a t ap r e p a r a t i o na n dp r e p r o c e s s i n g ) 、数据挖掘( d a t am i n i n g ) 、以及模型解释与 评价( i n t e r p r e t a t i o n ) - 具体到实际的应用系统因为所要处理的数据不同，用户要求也不同，挖掘体系和步 骤都可能有所不同。 2 4 1 数据挖掘的体系结构 典型的数据挖掘系统如图2 1 所示1 2 】。其中，数据挖掘模块式整个系统的核心，包 括针对各种应用而开发的挖掘子模块，如分类分析模块、聚类分析模块、关联规则挖掘 模块等；数据挖掘的对象信息存储在数据库、数据仓库或是其他一些存储媒介中；数据 库接口为相应数据挖掘模块提供相应的数据；应用领域知识库主要用来指导挖掘的过 程，评价挖掘出来的候选模式；图形用户界面是用户与挖掘系统的交互。 1 2 长安人学硕上学位论文 数据库接口 2 4 2 数据挖掘的步骤 图2 1 数据挖掘系统结构图 数据挖掘是一个循环反复的过程，包括很多反馈回路，每个步骤一旦不能达到预期 目标都要返回到前面的步骤，重新调整，重新执行。 数据挖掘的过程大体可分为四个阶段，分别为：问题定义( t a s kd e f i n i t i o n ) 、数 据准备( d a t ap r e p a r a t i o na n dp r e p r o c e s s i n g ) 、数据挖掘( d a t am i n i n g ) 、以及模型解 释与评价( i i l t e r p r e t a t i o n ) 【14 1 。 1 问题定义 了解应用的范围，用户需要达到的目标，并根据了解的内容准备相关的知识。 然后为本次挖掘选择比较可行的挖掘算法。 2 数据准备 数据准备分为三个阶段：数据选择( d a t as e l e c t i o n ) 、数据预处理( d a t ap r e p r o e e s s i n g ) 、 数据变换与压缩( d a t at r a n s f o r m a t i o n ) 。 ( 1 ) 数据选择 数据选择就是根据用户的需求从原始数据库中抽取数据挖掘所需的数据，形成原数 据。 ( 2 ) 数据预处理 数据预处理包括消除噪声、消除重复记录、数据类型转换、数据一致性等。当数据 挖掘的对象是数据仓库时，一般在建立数据仓库时已经进行了数据预处理。 1 3 第二章数据挖掘概述 ( 3 ) 数据变换与压缩 数据一般由多个初始特征来标示，然而在数据挖掘时为了简便性要根据任务要求， 从初始特征中找出真正有用的特征，以减少数据挖掘时的特征或变量个数。常用的方法 是把数据投影到某个空间上以利于问题解决。 3 数据挖掘 ( 1 ) 选择数据挖掘方法。 7 7 根据挖掘的任务，选择适当的挖掘方法，比如统计分析、神经网络、机器学习、模 式识别等。 ( 2 ) 选择数据挖掘算法。 选择合适高效的算法有两个因素要考虑，一是根据需要处理数据的特点，选择与之 相关的算法。二是根据用户或实际系统的要求。 ( 3 ) 进行数据挖掘。 查找感兴趣的模式，建立模型，使之用来处理后续的数据。 4 模型解释与评价 对所采用挖掘系统模型用已有的经验相关的领域知识进行解释和评价。 5 结果表达 将数据挖掘阶段得道的模型，用直观，容易理解，便于使用的方式表示出来，比如 可利用直观可视化图形表示。 6 结果评价 有的挖掘结果未必是用户需要的信息，比如由具有很高的支持度和置信度的频繁项 集得到的关联模式得到强关联规则。相反一些非频繁项集能得到我们感兴趣的关联。索 沃要筛选和评价挖掘结果中的有用部分，查找可接受的结果。 7 知识巩固 把挖掘出的知识运用到实际的系统中，验证知识的实际效果，以便对以后的数据挖 掘提供改建方案。 2 5 数据挖掘的知识发现及商业应用 1 应于数据挖掘所采用的不同方法，数据挖掘能够发现的知识模式有5 类【1 2 】。 ( 1 ) 广义型知识 1 4 长安大学硕士学位论文 指类别特征的概括性描述知识。根据数据的微观特性发现其表征、带有普遍性的、 较高层次的、宏观的知识，是对数据的概括和抽象，反应的同类事物的共性。 ( 2 ) 预测性知识 根据历史和当前的数据推测未来的数据，也可以理解为是以时间为关键属性的关联 知识。 ( 3 ) 关联型知识 反映事物之间依赖或关联关系的知识，如果多项属性之间存在关联，那么其中一项 的知识可以通过其他项来预测。 ( 4 ) 偏差型知识 通过对差异特例的描述，揭示事物偏离常规的异常现象。如标准类外的特例、数据 聚类外的离群值等。 ( 5 ) 分类知识 特征性知识：反映同类事物的共同性质的知识。 差异性知识：反映不同事物之间的属性差别的知识。 2 数据挖掘的应用 数据挖掘的应用极其广泛。针对特定领域的应用，人们研发了许多专用的数据挖掘 工具，包括天文学、生物医学、医疗保健、d n a 分析、银行、金融、超市等。 数据挖掘在天文上有一个非常著名的应用系统s k i c a t ( s k yi m a g ec a t a l o g i n ga n d a n a l y s i st 0 0 1 ) 1 1 5 】。它是由加州理工学院研发的用于帮助天文家发现遥远星体的工具，其 任务是构造星体分类器对星体进行分类。 数据挖掘在生物医学上的应用主要在集中于分子生物学，尤其是基因工程的研究。 它在分子生物学上的工作可分为两种：一种是从各种生物体的d n a 序列中定位出具有 某种功能的基因串；二是在基因数据库中搜索与某种具有高阶结构或功能的蛋白质相识 的高阶结构。 数据挖掘在市场营销中的应用可分为两类：数据库市场营销和购物篮分析。前者的 任务是通过交互查询、数据分割个模型预测等方法来选择有潜力的顾客以便向他们推销 产品。后者的任务是分析市场销售数据以识别顾客的购买行为模式，从而帮助确定商品 货架的布局，促进商品的销售。成熟的商用数据挖掘系统中，较著名的有i n t e l l i g e n t m i n e r 、d b m i n e r 、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 ，它们分别是由m m 公司的r a g r a w a l 1 5 第二章数据挖掘概述 等人、加拿大s i m o nf r a s e r 大学的韩家炜等人、美国的k d d 专家p i a t e r t s k y - s h a p i o o 等 人开发的数据挖掘工具【1 5 】。 在银行业，数据挖掘主要用于信用欺诈的建模和预测、风险评估、趋势分析、收益 分析以及辅助直销活动。在金融市场，己将神经网络用于股票价格预测、购买权交易、 债券等级评分、资产组合管理、商品价格预测、合并和买进以及金融危机预测等方面。 2 6 数据挖掘研究面临的挑战 目前数据挖掘研究还很不成熟，其应用还有较大的局限性，很多的研究问题亟待解 决，如数据量巨大、动态性、缺值等，数据挖掘所面临的挑战性主要有以下几个方面。 1 算法效率与可伸缩性 数据挖掘与传统的机器学习的区别在于：数据挖掘直接面向海量的数据库系统，这 类数据库通常由上百个属性和数万条记录，并且数据表之间包含复杂的关系，这就必然 导致数据挖掘过程中搜索维数和搜索空间的激增。为了有效地从数据库中发现信息，数 据挖掘算法必须是有效的和可度量的，也就是说基于大型数据库的数据挖掘算法的运行 时间必须是可预测的和可接受的。另外。大量的属性和记录的存在也增加了出现不确定 性和病态模式的可能性。因而，提高算法的效率以及具有规模伸缩性是它们实际应用中 必须面对的巨大挑战。 2 数据挖掘系统的交互性 数据挖掘是一个复杂的过程，数据挖掘过程中操作者的适当参与是必不可少的。系 统的交互能力对系统性能够很重要，为用户提供方便的平台使其表达要求和策略是关 键。另一方面，交互系统把挖掘的结果显示给用户。由于生成的结果是多种多样的，因 此准确而直观地描述挖掘结果、提供友好高效的用户界面一直是这方面研究的重要课 题。 3 互联网上的数据挖掘 互联网规模的爆炸性增长，使其成为一个全球规模的信息源。从中可以发现大量的 新知识。因此，国际互联网数据挖掘是一个新的研究课题，激发了越来越多专家学