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

华北电力大学硕士学位论文摘要 摘要 数据挖掘是面向海量数据的知识发现技术，关联规则是数据挖掘的重要模式之 一，有着极其重要应用价值。文中给出了一种不需要产生候选项的频繁模式增长算 法，避免了多次扫描数据库，降低了时间复杂度。由于支持度和信任度的评价标准 有一定的局限性，给出了一个新的评价阈值一兴趣度，用来修剪无趣的规则，从而 提高了数据挖掘结果的质量。并且通过对f p _ g r o w t h 算法进行扩展，给出了一个 高效的多层关联规则挖掘算法f p c h ，经实验证明该算法确实有效。 关键词：数据挖掘，关联规则，兴趣度，多层关联规则 a b s t r a c t d a t am i i l i n gi sm ek n o w l e d g ed i s c 0 v e d rt e 出l i q u eo r i 豇l t e dt 0ag r e a td e a lo fd a t 乱 a s s 0 c i a t i o nn 1 1 ei so r l eo ft 1 1 ei n l p o r t a n tm o d e l so fd a t am i l l 证g ，觚dh 笛廿l em o s ts i g m j e i c a n t a p p l i c a t i o nv a l u e h 也ea r t i d eg a v eo n ek 血dn o tt 0 北e dt 0h a v c 也ec a n d i d a t e 血q u e n t p a t t e mg r o w t l la l g o r i t l l i 玛a v o i d e ds c 甜m i n g 也ed a t a ：b 鹤em a i l yt i m 懿，a n dr e d l l c e dt h e 缸e o r d e ro fc 0 i n p l e 】【i 够b e c a 吣e 血e 跚p p 酣a n d 1 ec 0 血d c el 吖e 1e v a l u 撕o n 耐t 耐ah a v e c e r t a i l ll i m i t a t i o n ，h 弱百v e nan i e wa p p r a i s a lt 1 1 r e s h o l dv 面u e - i n t e r e 瓯u s e s 内rt 0p r 毗心也e s a l s e l 懿sr u l e ，t l i i i si l l l p r 0 、1 甜也ed a t am i i l i l l gr 销u nq 砌i t ya n dt h m u g h 涮懿o nt h ee x p a n s i o n t 0t l l ef pg 1 o 砒a l g o r i 也m ，h 嬲西v 钮h i g l l l ye 彘c t i v em u l 矗- l a y e r e dc o 皿e c t i o nm l e 懿c a v 撕a l g o r i 也m f p c h ，心e rt h ee x p e r i m 胁tp r 0 v e d 也a tn l i sa l g o r i 血ni s 衄i l ye 能“v e w 缸gs h a o h u a ( c o m p u t e ra p p l i e dt e c h n 0 1 0 9 y ) d i r e c t e db yp r o f w a n gc u i m k e yw o r d s ：d a t am i n i n 舀a s s o c i a t i o nr l d e s ，i n t e r e s tm e a s u r e ，m i l l 出l e v e la s s o c i a t i o n r u l e 华北电力大学硕士学位论文摘要 摘要 数据挖掘是面向海量数据的知识发现技术，关联规则是数据挖掘的重要模式之 一，有着极其重要应用价值。文中给出了一种不需要产生候选项的频繁模式增长算 法，避免了多次扫描数据库，降低了时间复杂度。由于支持度和信任度的评价标准 有一定的局限性，给出了一个新的评价阈值一兴趣度，用来修剪无趣的规则，从而 提高了数据挖掘结果的质量。并且通过对f p _ g r o w t h 算法进行扩展，给出了一个 高效的多层关联规则挖掘算法f p c h ，经实验证明该算法确实有效。 关键词：数据挖掘，关联规则，兴趣度，多层关联规则 a b s t r a c t d a t am i i l i n gi sm ek n o w l e d g ed i s c 0 v e d rt e 出l i q u eo r i 豇l t e dt 0ag r e a td e a lo fd a t 乱 a s s 0 c i a t i o nn 1 1 ei so r l eo ft 1 1 ei n l p o r t a n tm o d e l so fd a t am i l l 证g ，觚dh 笛廿l em o s ts i g m j e i c a n t a p p l i c a t i o nv a l u e h 也ea r t i d eg a v eo n ek 血dn o tt 0 北e dt 0h a v c 也ec a n d i d a t e 血q u e n t p a t t e mg r o w t l la l g o r i t l l i 玛a v o i d e ds c 甜m i n g 也ed a t a ：b 鹤em a i l yt i m 懿，a n dr e d l l c e dt h e 缸e o r d e ro fc 0 i n p l e 】【i 够b e c a 吣e 血e 跚p p 酣a n d 1 ec 0 血d c el 吖e 1e v a l u 撕o n 耐t 耐ah a v e c e r t a i l ll i m i t a t i o n ，h 弱百v e nan i e wa p p r a i s a lt 1 1 r e s h o l dv 面u e - i n t e r e 瓯u s e s 内rt 0p r 毗心也e s a l s e l 懿sr u l e ，t l i i i si l l l p r 0 、1 甜也ed a t am i i l i l l gr 销u nq 砌i t ya n dt h m u g h 涮懿o nt h ee x p a n s i o n t 0t l l ef pg 1 o 砒a l g o r i 也m ，h 嬲西v 钮h i g l l l ye 彘c t i v em u l 矗- l a y e r e dc o 皿e c t i o nm l e 懿c a v 撕a l g o r i 也m f p c h ，心e rt h ee x p e r i m 胁tp r 0 v e d 也a tn l i sa l g o r i 血ni s 衄i l ye 能“v e w 缸gs h a o h u a ( c o m p u t e ra p p l i e dt e c h n 0 1 0 9 y ) d i r e c t e db yp r o f w a n gc u i m k e yw o r d s ：d a t am i n i n 舀a s s o c i a t i o nr l d e s ，i n t e r e s tm e a s u r e ，m i l l 出l e v e la s s o c i a t i o n r u l e 声明尸明 本人郑重声明：此处所提交的硕士学位论文数据挖掘中关联规则算法的研究， 是本人在华北电力大学攻读硕士学位期间，在导师指导下进行的研究工作和取得的研究 成果。据本人所知，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得华北电力大学或其他教育机构的学位或证书而 使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示了谢意。 学位论文作者签名： 王生釜 日期： 关于学位论文使用授权的说明 本人完全了解华北电力大学有关保留、使用学位论文的规定，即：学校有权保管、 并向有关部门送交学位论文的原件与复印件；学校可以采用影印、缩印或其它复制手 段复制并保存学位论文：学校可允许学位论文被查阅或借阅；学校可以学术交流为 目的，复制赠送和交换学位论文；同意学校可以用不同方式在不同媒体上发表、传播学 位论文的全部或部分内容。 ( 涉密的学位论文在解密后遵守此规定) 作者签名：三垒坐 日期：邋缒 导师签名： 日期： 华北电力大学硕士学位论文 1 1 数据挖掘的研究背景 第一章引言 科技的进步，特别是信息产业的发展，把我们带入了一个崭新的信息时代。随 着计算机应用的普及和数据库技术的不断发展，数据库管理系统的应用领域越来越 广泛。条形码和信用卡的普及和使用，进一步加速了商业、金融、保险等领域的信 息化进程。在工业、商业、科研、行政、医疗、保险等应用领域中，大量的数据被 搜集和存储在各种数据库中，例如：美国的w a 卜m a r t 公司每天增加两千万条事务数 据记录。由于这些数据十分繁杂，如何有效的利用这些数据，从这些数据中发现有 价值的信息或知识，达到为决策服务的目的，就成了一项非常艰巨的任务。 采用传统的数据分析方法和数据查询、验证方法，对这些巨量数据进行分析和 处理，不仅耗费大量的计算时间，而且完全依赖于预先对数据之间关系的假设和估 计，这些方法已经不能满足人们日益增长的对数据中隐含知识的渴求。大量的信息 在给人们带来方便的同时，也带来了一系列问题，面对海量数据库和大量繁杂信息， 如何才能从中提取有价值的知识，进一步提高信息的利用率，由此引发了一个新的 研究方向：数据挖掘( d a t am i n i n g ) ，也就是基于数据库的知识发现( k d d ) ，其中关 联规则数据挖掘算法尤为引人注目。 数据挖掘方法的提出，让人们最终有能力认识到数据的真正价值，即蕴含在数 据中的信息和知识。数据挖掘是目前国际数据库和信息决策领域的最前沿研究方向 之一，已经引起了学术界和工业界的广泛关注。一些国际上高级别的实验室，例如 i b ma 1 衄d e n ，g t e 以及众多的学术单位都在这个领域开展了各种各样的研究计划。 研究的目的主要是发展有关的方法、理论和工具，以支持从大量的数据中提取有用 的、让人感兴趣的知识。 数据库中的知识发现始于8 0 年代后期，1 9 8 9 年召开了第一次关于知识发现和 数据挖掘的国际会议。1 9 9 5 年8 月，在加拿大的m o n t r e a l ，召开了首届知识发现 和数据挖掘的国际讨论会。亚太地区于1 9 9 7 年在新加坡举行了首届亚太知识发现 和数据挖掘的国际会议( p a k d d ，9 7 ) ；欧洲也于1 9 9 8 年召开了首届欧洲知识发现和 数据挖掘的学术会议。 知识发现和数据挖掘的研究一直作为数据库和机器学习的一个分支，处于依附 的地位。直至01 9 9 8 年6 月，a c ms i g k d d ( a s s o c i a t i o nf o rc o m p u t i n gm a c h i n e r y s p e c i a li n t e r e s tg r o u po nk n o w l e d g ed i s c o v e r ya n dd a t am i n i n g ) 正式成立， 标志着知识发现和数据挖掘正式成为一个独立的学科。 1 华北电力大学硕士学位论文 数据挖掘的研究已经和数据仓库的研究结合起来。数据仓库也是近年来才提出 的新概念。所谓数据仓库是一种数据的存储地，来自于异地、异构的数据源或数据 库的数据经过加工后在数据仓库中存储、提取和维护。传统数据库主要面向业务处 理，而数据仓库面向复杂的数据分析、高层决策支持。数据仓库提供来自于种类不 同的应用系统的集成化和历史化的数据，为有关部门或企业进行全局范围的战略决 策和长期分析提供了有效的支持。数据仓库拥有任意提取数据的自由，而不干扰数 据库的正常运行。 目前，在国外，数据挖掘技术及其相关的决策支持系统发展得很快，它们在商 业界，公共服务行业等众多行业被广泛应用，并快速、直接的带来了令人吃惊的利 润，同时也带动了这些行业的飞速发展。因此，有人称这项技术为二十世纪影响人 类的计算机方面的三大事件之一。 1 2 数据挖掘中的关联规则 目前，数据挖掘的主要研究领域为数据总结、分类、聚类、关联规则等方面。 关联规则表示数据库中一组对象之间某种关联关系的规则。例如，关联规则可以表 示为“购买了项目a 和b 的顾客中有9 5 的人又买了c 和d 。从这些规则可找出顾 客购买行为模式，可以应用于商品货架设计、生产安排、针对性的市场营销等。采 用关联模型比较典型的例子是“啤酒和尿布打的故事。在美国，一些年轻的父亲下 班后经常到超市去买婴儿尿布，超市经过对顾客的购物信息进行挖掘，发现在购买 婴儿尿布的年轻父亲中，有3 0 4 0 的人同时要买一些啤酒。超市随后调整了货架 的摆放，把尿布和啤酒放在一起。结果是：销售额明显增加了。 关联规则问题由a g r a w a ln 1 等于1 9 9 3 年首先提出，以后诸多的研究人员对关 联规则的挖掘问题进行了大量的研究2 q 1 。他们的工作包括对原有的算法进行优化， 如引入随机采样、并行的思想、增加衡量标准、规则约减、改变存储结构等，以提 高算法挖掘规则的效率：对关联规则的应用进行推广，从最初的商业指导到生活中 的其他领域，如教育、科研、医学等。 1 3 本文的主要工作 数据挖掘是近年来兴起的多学科相互融合的应用技术，广泛地应用于各个领 域，特别是金融业、电信业、市场分析以及科学研究等领域，引起了学术界的广泛 关注。本文主要对关联规则的挖掘算法作了一些探索性的研究，内容主要集中在以 下几个方面：分析关联规则挖掘( m i n i n ga s s o c i a t i o nr u l e s ) 中产生频繁集的常用 算法、算法的不足以及对这些不足进行改进的新算法。本论文的主要工作如下： 2 华北电力大学硕士学位论文 ( 1 ) 研究了数据挖掘技术产生的背景，研究和分析数据挖掘的概念、挖掘的对 象功能以及可以发现的知识模式等。 ( 2 ) 对关联规则的基本概念和经典定义进行研究分析，研究了关联规则的种类， 分析不同类型的关联规则，研究了关联规则常用的挖掘方法。 ( 3 ) 分析了经典关联规则挖掘算法a p r i o r i 算法的基本性质，分析了该算法的 性能和特点，给出了其他学者对a p r i o r i 算法的一些改进算法。给出了 f p g r o w t h ( f r e q u e n tp a t t e r ng r o w t h ，频繁模式增长) 算法，它从根本上改进了 a p r i o r i 算法产生庞大候选频繁集的缺点，是一种基于f p t r e e ( f r e q u e n tp a t t e r n t r e e ，频繁模式树) 的不产生频繁候选集的关联规则挖掘算法。给出了f p t r e e 的 构造过程和f p g r o w t h 算法的工作过程，分析f p g r o w t h 算法具有节省时间和空间 的优势。 ( 4 ) 关联规则的算法是从大量的数据中发现数据间的关联模式，为了发现用户 感兴趣而有用的关联模式，分析了目前广泛使用的关联规则的评价标准的局限性， 给出了关联规则的又一个评价标准一兴趣度，将支持度、置信度和兴趣度一起作为 有效关联规则的评价标准。基于前人对关联规则定义的改进和基于相关性的兴趣度 定义，改进了基于支持一置信一兴趣度的关联规则挖掘算法，并对算法的性能和特点 进行了分析。 ( 5 ) 多层关联规则方面的内容。先研究了进行多层关联规则挖掘的必要性，然 后研究和分析了多层关联规则的定义和多层关联规则挖掘的一般步骤，给出了一个 基于f p t r e e 的多层关联规则挖掘算法f p c h ，该算法是通过对f p g r o w t h 算法进 行扩展得到的，它有效克服了基于a p r i o r i 算法的多层关联规则挖掘算法的效率低 的缺点，能够正确、高效地挖掘多层关联规则。该算法在对同层关联规则的挖掘中， 明显地提高了效率。 ( 6 ) 对所做的工作进行总结，并展望了论文中有待于进一步解决的问题。 华北电力大学硕士学位论文 第二章数据挖掘技术综述 2 1 数据挖掘技术的概念 从1 9 8 9 年到现在，k d d 的定义随着人们研究的不断深入也在不断完善，目前比 较公认的定义是f a y y a 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 ) 。但是，更科学的说法 是将数据挖掘视为数据库知识发现的一个基本步骤。在这种情况下，数据库的知识 发现过程如图2 一l 所示，由以下几个步骤组成 1 。 数据清理：消除噪声或者不一致数据。 数据集成：多种数据源可以组合在一起。 数据选择：从数据库中检索与分析任务相关的数据。 数据变换：将数据变换或统一成适合挖掘的形式，如通过汇总或聚集操作。 数据挖掘：使用智能方法提取数据模式。 模式评估：根据某种兴趣度度量，识别表示知识的真正有趣的模式。 知识表示：使用可视化和知识表示技术，向用户提供挖掘的知识。 知谓 图2 1 数据挖掘的过程 尽管将数据挖掘视为数据库知识发现过程的一个基本步骤更为科学，但是在产 4 华北电力大学硕士学位论文 业界、媒体和数据库研究界，将数据挖掘直接当作数据库中的知识发现更为流行。 因此数据挖掘有了一个更加广泛的概念：数据挖掘是从存放在数据库、数据仓库或 其他信息库中的大量数据中挖掘有趣知识的过程。基于这种观点，一个典型的数据 挖掘系统可以由以下几个主要成分组成( 如图2 2 所示) ： 数据库、数据仓库或其他信息库：这是一个或一组数据库、数据仓库、电子表 格或其他类型的信息库。可以在数据上进行数据清理和集成。 数据库或数据仓库服务器：根据用户的数据挖掘请求，数据库或数据仓库服务 器负责提取相关数据。 知识库：用于指导搜索或评估结果模式的兴趣度。 数据挖掘引擎：数据挖掘系统基本的部分，由一组功能模块组成，用于特征化、 关联、分类、聚类分析以及演变和偏差分析。 模式评估模块：通常，此部分使用兴趣度度量，并与数据挖掘模块交互，以使 将搜索聚焦在有趣的模式上。它可能使用兴趣度阈值过滤发现的模式。模式评估模 块也可以与挖掘模块集成在一起，这依赖于所用的数据挖掘方法的实现。 图形用户界面：实现用户和数据挖掘系统之间的通信，允许用户与系统交互， 指定数据挖掘查询或任务，提供信息、帮助搜索聚焦，根据数据挖掘的中间结果进 行探索式数据挖掘。此外，此部分还允许用户浏览数据库和数据仓库模式或数据结 构，评估挖掘的模式，以不同的形式对模式可视化。 觳 蓐用户鼻田 上彳 曩吱评估 l l下 数据挖掘引鼙 上t f 敷据犀豇蚊捃仓蓐脏务嚣1 图2 2 典型的数据挖掘系统结构 要指出的是，数据挖掘技术从一开始就是面向应用的。它不仅是面向特定数据 库的简单检索查询调用，而且要对这些数据进行微观、宏观的统计、分析、综合和 华北电力大学硕士学位论文 推理，以指导实际问题的求解，企图发现事件间的相互关联，甚至利用已有的数据 对未来的活动进行预测。这样一来，就把人们对数据的应用，从低层次的末端查询 操作，提高到为各级经营决策者提供决策支持。这种需求驱动力，比数据库查询更 为强大。 2 2 数据挖掘的功能和分类 2 2 1 数据挖掘的功能 数据挖掘功能用于指定数据挖掘任务中要找的模式类型。数据挖掘任务一般可 以分为两类：描述和预测。描述性挖掘任务刻画数据库中数据的一般特性，而预测 性挖掘任务则在当前数据上进行推断，以进行预测。 数据挖掘的功能以及可以发现的模式类型有8 1 ：类概念描述、关联分析、分类 和预测、聚类分析、孤立点分析和演变分析。 1 类概念描述 数据可以与类或概念相关联。用汇总的、简洁的、精确的方式描述每个类和概 念可能是有用的。这种类或概念的描述称为类概念描述。 2 关联分析 关联分析用于发现关联规则，关联规则描述了给定数据集中的项之间的有趣联 系。关联分析广泛应用于购物篮或事务数据分析。从大量商务事务记录中发现有趣 的关联关系，可以帮助许多商务决策的制定，如分类设计、交叉购物和贱卖分析等。 3 分类和预测 分类是找出描述并区分数据类或概念的模型的过程，以便能够使用模型预测类 标号未知的对象类。预测是构造和使用模型评估无标号样本类，或评估给定样本可 能具有的属性值或值区间。分类和预测之间的区别在于，分类是预测类标号( 或离 散值) ，而预测是建立连续值函数模型。 4 聚类分析 聚类将数据对象分组成为多个类或簇，在同一个簇中的对象之间具有较高的相 似度，而不同簇中的对象差别较大。与分类不同的是，它要划分的类是未知的。 5 孤立点分析 在数据库中经常存在一些数据对象，它们不符合数据的般模型。这样的数据 对象被称为孤立点，它们与数据的其他的部分不同或不一致。孤立点可能是度量或 6 华北电力大学硕士学位论文 执行错误所导致的。 6 演变分析 数据演变分析描述行为随时间变化的对象的规律或趋势，并对其建模。这种分 析可能包括时间相关数据的特征化、区分、关联、分类或聚类，但是它的不同特点 包括时间序列数据分析、序列或周期模式匹配和基于类似性的数据分析。 2 2 2 数据挖掘的分类 从不同的角度看，数据挖掘技术有几种分类方法：根据发现知识的种类进行分 类：根据挖掘的数据库的种类进行分类和根据采用的技术分类n 钔。 1 根据发现知识的种类分类。这种分类方法有：总结( s u 衄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 1 a s s i f i c a t i o n ) 挖 掘、聚类( c 1 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 o r i e n t e d ) 、主动型( a c t i v e ) 、空 间型( s p a t i a l ) 、文本型( ( t e x t ) 、多媒体( m u f t i m e d i a ) 、异质( h e t e r o g e n e o u s ) 数 据库等等。 3 根据采用的技术，最常用的数据挖掘技术有： 人工神经网络：它从结构上模仿生物神经网络，是一种通过训练来学习的非线 性预测模刑。可以完成分类、聚类、特征挖掘等多种数据挖掘任务。 决策树：用树型结构来表示决策集合。这些决策集合通过对数据集的分类产生 规则。典型的决策树方法有分类回归树。 。 遗传算法：是一种新的优化技术，基于生物进化的概念设计了一系列的过程来 达到优化的目的。这些过程有基因组合、交叉、变异和自然选择。为了应用遗传算 法，需要把数据挖掘任务表达为一种搜索问题而发挥遗传算法的优化搜索能力。 最邻近技术：这种技术通过k 个与之最相近的历史记录的组合来辨认新的纪录。 也称k 一最邻近方法。这种技术可以用作聚类、偏差分析等数据挖掘任务。 规则归纳：通过统计方法归纳、提取有价值的i f t h e n 规则。规则归纳的技术 在数据挖掘中被广泛使用，例如关联规则挖掘。 7 华北电力大学硕士学位论文 可视化：采用直观的图形方式将信息模式、数据的关联或趋势呈现给决策者， 决策者可以通过可视化技术交互式的分析数据关系。 2 3 数据挖掘的过程 数据挖掘过程一般需要经历确定挖掘对象、准备数据、建立模型、数据挖掘、 结果分析与知识应用这样几个阶段，这些阶段在具体实施中可能需要重复多次。为 完成这些阶段的任务，需要不同专业人员参与其中，这些专业人员主要是业务分析 人员、数据分析人员和数据管理人员。 1 确定挖掘对象 定义清晰的挖掘对象，认清数据挖掘的目标是数据挖掘的第一步。 2 准备数据 ( 1 ) 数据的选择 在确定数据挖掘的业务对象后，需要搜索所有与业务对象有关的内部和外部数 据，从中选出适合于数据挖掘应用的数据。 ( 2 ) 数据的预处理 在选择数据后，还需要对数据进行预处理，对数据进行清洗，解决数据中的缺 值、冗余、数据值的不一致、数据定义的不一致、过时的数据等问题。 3 挖掘模型的构建 将数据构建成一个分析模型，这个分析模型是针对挖掘算法建立的。建立一个 真正适合挖掘算法的分析模型，是数据挖掘成功的关键。模型的建立必须从数据的 分析开始，为模型选择变量。然后从原始数据中构建新的预示值。从数据中选取一 个子集或样本建立分析模型。最后，通过转化变量，使之和选定用来建立模型的算 法一致。 4 数据挖掘 对所得到的经过转化的数据进行挖掘，除了完善与选择合适的算法需要人工干 预外，数据挖掘工作都由挖掘工具自动完成。 5 结果分析 当数据挖掘出现结果后，要对挖掘结果进行解释并且评估。具体的解释与评估 方法一般根据数据挖掘操作结果所制定的决策成败来定。 6 知识的应用 华北电力大学硕士学位论文 数据挖掘的结果经过业务决策人员的认可，才能实际利厨。为使数据挖掘结果 能在实际中得到应用，需要将分析所得到的知识集成到业务信息系统的组织机构中 去，使这些知识在实际的管理决策分析中得到应用。 2 4 数据挖掘面临的主要问题 数据挖掘面临的主要问题有三大类乜3 1 ：挖掘方法和用户交互的问题、性能问题 和存储数据的数据库类型具有多样性的问题。 1 挖掘方法和用户交互问题 这类问题涉及到数据挖掘技术的多个方面，主要有以下一些内容： 在数据库中挖掘不同类型的知识：由于不同的用户感兴趣的知识类型可能会 很不相同，这就要求数据挖掘系统应当覆盖范围很广的数据分析和知识发现任务， 包括数据特征化、区分、关联、分类、聚类、趋势和偏差分析以及类似性分析。 多个抽象层的交互知识挖掘：由于在进行数据挖掘之前很难知道将要挖掘出 来的是什么样的知识，因此需要数据挖掘的过程具有交互性。 结合背景知识：可以使用背景知识或关于所研究领域的信息来指导发现过程， 并使得发现的模式以简洁的形式在不同的抽象层表示。 数据挖掘查询语言和特定的数据挖掘：与现在存在大量的高级程序开发语言 相比，数据挖掘还缺乏一门统一的高级语言用于描述数据挖掘的过程和结果。 数据挖掘结果的表示和显示：高级语言、可视化表示或其他形式的表示方法可 以使知识易于理解，能够被人们直接使用。这要求系统采用有表达能力的知识表示 技术，如树、表、规则、图、图表、交叉表、矩阵或曲线等。 处理噪声和不完全数据：存放在数据库中的数据可能反映噪声、异常情况或不 完全的数据对象，它们可能搞乱分析过程，导致数据与所构造的知识模型过分适应， 由此导致所发现的模式精确性很差。这就需要处理数据噪声的数据清理方法和数据 分析方法，以及发现和分析异常情况的孤立点挖掘方法。 模式评估一兴趣度问题：数据挖掘方法发现的模式通常数以千计，怎样从中选 择出用户感兴趣的模式是一个极具挑战性的问题。 2 性能问题 数据挖掘算法的有效性和可伸缩性口引：数据挖掘算法的有效性要求算法的运 行时间应尽可能地少，而可伸缩性则要求算法能够适应不同大小的数据库容量，算 法的运行时间应尽可能地与数据库的容量保持线性比例的增减关系。 9 华北电力大学硕士学位论文 并行、分布式和增量挖掘算法：并行和分布式数据挖掘算法将数据划分成多个 部分，这些部分可以并行处理，然后将多个处理结果合并。 3 关于数据库类型的多样性问题 关系的和复杂的数据类型的处理：由于数据库类型的多样性，指望一个系统挖 掘所有类型的数据是不现实的。为挖掘特定类型的数据，应当构造特定的数据挖掘 系统。 由异种数据库和全球信息系统挖掘信息：局域网和广域网( 如互连网) 提供了 大量庞大的、分布式的和异种的数据库。从具有不同语义的结构化的、半结构化的 和非结构化的不同数据源发现知识，是数据挖掘技术面临的一个巨大挑战。 2 5 数据挖掘的研究与开发方向 数据挖掘现在是数据库研究、开发和应用最活跃的分支之一，作为一门新兴 的技术，数据挖掘的发展也应适应科技发展大潮流的需要。针对数据挖掘现在面临 的主要问题乜训，数据挖掘的研究与开发最主要的方向有以下一些： 与数据仓库与在线分析处理技术结合：数据仓库可以为在线分析处理和数据 挖掘提供经过滤化的、完整的数据资源。在线分析处理可以看作为一个简化的对数 据进行聚合的数据挖掘形式。 挖掘多种类型的知识：数据挖掘除了最常见的分类与关联之外，还有许多重要 的任务待开发，包括描述、比较、聚合、预测模型以及时间相关形式分析等等。 提供对数据挖掘的查询语言和高效、交互式及特殊数据挖掘的支持：与相关语 言类似，高层次的数据挖掘语言应该能够允许用户定制特殊的数据挖掘任务。 处理复杂数据：挖掘关联性和事务性的数据是目前数据挖掘的中心。但是对于 半结构化以及非结构化的数据进行挖掘，也是一个非常重要而极富挑战性的方面。 高性能的数据挖掘：高效性和可伸缩性是目前数据挖掘算法的焦点，随着并行 的、分布式的以及增长式的数据挖掘技术的发展，这种趋势将会继续得到发展。 可视化和数据挖掘：数据库内容和数据挖掘结果的可视化可以帮助用户理解 和评估挖掘结果，从而对数据挖掘进行相应的调整。 数据挖掘的应用：如何将数据挖掘技术应用于现实世界也是一个非常重要的课题。 2 6 本章小结 本章研究了数据挖掘技术的基本概念，功能和步骤，研究和分析了数据挖掘技 术的一些基本理论基础。 l o 华北电力大学硕士学位论文 第三章关联规则算法的研究 关联规则挖掘是数据挖掘中最活跃的研究方法之一。最早是由a g r a w a l 等人于 1 9 9 3 n 年提出了挖掘交易数据库中项集间的关联规则问题，关联规则是发现数据库 中不同商品( 项) 之间的联系，这些规则找出顾客购买行为模式，如购买了某一商品 对购买其他商品的影响。一个典型例子是购物篮分析m 。该过程通过发现顾客放入 其购物篮中不同商品( 图3 1 ) 之间的联系，分析顾客的购买习惯。通过了解哪些商 品频繁地被顾客同时购买，这种关联的发现可以帮助零售商制定营销策略。 购篮 崮碴曲 赢客l一客2 曩客3 i 丑并n 图3 1 购物篮分析 目前关联规则挖掘问题已经引起了数据库、人工智能、统计学、信息检索、可 视化及信息科学等诸多领域里的广大学者和研究机构的格外重视，并取得了不少的 研究成果。由于关联规则形式简洁、易于解释和理解并可以有效的捕捉数据间的重 要关系，因此从大型数据库中挖掘关联规则的问题已经成为近年来数据挖掘研究领 域中的一个热点。 3 1 关联规则的基本概念 3 1 1 基本概念 定义3 1 项与项集 数据库中不可分割的最小单位信息，称为项，一般用i 表示。项的集合称为项 集。设集合i = f ，f 2 ，) 是项集，i 中项目的数量为k ，则集合i 称为k 项集。 定义3 2 事务 设i = f ，之， 是由数据库中所有项目构成的集合，一次处理所含项目的集合 用t 表示，使得t s i ，并使每一个t 都有唯一的标识t i d 。那么我们称二元组 为数据库事务。在不引起误会的情况下，一般简单表示为t 。 华北电力大学硕士学位论文 定义3 3 项集的频率 设u = 鸭，吃， 为项集，且u si ，u 1 2 j ，d = 互，互乙 为数据库中的 所有事务集，事务集q = ( t iit 。d ，u s t 。 ，则项集u 在事务集d 中的频率为： 以u ) = p ( 吃 甜。) = lqi idi 定义3 4 关联规则 关联规则是形如x = y 的蕴涵式，其中x ci ，yci ，并且x n y = a 。x 称为前项， y 称为后项：关联规则反映x 中的项目出现时，y 中的项目也跟着出现的规律。 定义3 5 关联规则的支持度( ( s u p p o r t ) 关联规则的支持度是交易集中同时包含x 和y 的交易数与所有交易数之比，记 为s u p p ( x = y ) ，即 s u p p ( x = y ) = s u p p ( x uy ) = p ( x y ) 支持度反映了x 和y 中所含的项在事务集同时出现的概率。例如“同时购买乒 乓球拍和乒乓球网的顾客有4 8 。 定义3 6 关联规则的置信度( c o n f i d e n c e ) 关联规则的置信度是交易集中包含x 和y 的交易数与包含x 交易数之比，记为c o n f ( x = y ) ，即 c o n f ( x = y ) = s u p p ( x u y ) s u p p ( x ) = p ( yix ) 置信度反映了在包含x 的事务中，出现y 的条件概率。例如“在所有购买乒乓 球拍的顾客中有6 0 的顾客购买了乒乓球网刀。 关联规则的支持度和置信度分别反映了所发现规则的有用性和确定性。一般 地，用户可以定义两个阈值，分别为最小支持度阈值和最小置信度阈值。当挖掘出 的关联规则的支持度和置信度都满足这两个阈值时，我们就认为这个规则是有效 的，否则，就是无效的。这些阈值一般可由领域专家设定。 定义3 7 频繁项集 如果项集u = “。，“：，) 出现的频率大于或等于最小支持计数，即满足最小支 持度阈值，则称它为频繁项集( f r e q u e n t i t e m s e t ) 。频繁k 一项集的集合通常记为 l k 。 定义3 8 强规则 同时满足最小支持度阈值( m i n s u p p ) 和最小置信度阈值( m i n c o n f ) 的规则称 作强规则。强规则可由频繁项集产生。 1 2 华北电力大学硕士学位论文 挖掘关联规则的问题就是找出这样一些规则，它们的支持度和置信度分别大于 用户指定的最小支持度阈值( m i n s u p ) 和最小置信度阈值( i n c o n f ) ，将这样的规 则称作强规则。为方便计算，我们用0 和1 0 0 之间的值而不是用0 到1 之间的值 表示支持度和置信度。 3 1 2 关联规则的种类 关联规则按照不同的标准有不同的分类口1 ： ( 1 ) 基于规则中处理的变量类别，关联规则可以分为布尔型和量化型。 布尔型关联规则( b 0 0 1 e a na s s o c i a t i o nr u l e ) 处理的值都是离散的、种类化 的，它显示了这些变量的存在与否。 量化型关联规则( q u a n t i t a t i v ea s s o c i a t i o nr u l e ) 描述的是量化的项或属性 之间的关联，也称为数值型关联规则。在这种规则中，项或属性的量化值划分为区 间。对量化型字段进行处理时，将其进行动态的分割，或者直接对原始的数据进行 处理。 例如，下面的关联规则是布尔型关联规则： 购买计算机= 购买财务管理软件 下面的关联规则是量化关联规则： 年龄( “3 0 3 9 一) 人年薪( “5 万元以上一) = 购买( “轿车一) ( 2 ) 基于规则中涉及到的数据维，关联规则可以分为单维关联规则和多维关联 规则。 在单维关联规则( s i n g l e d i m e n s i o n a la s s o c i a t i o nr u l e ) 中，只涉及到数据 的一个维，处理单个属性中的一些关系。 在多维关联规则( m u l t i d i m e n s i o n a la s s o c i a t i o nr u l e ) 中，要处理的数据将 会涉及两个或多个维，处理各个属性之间的某些关系。 例如，下面这条规则只涉及到用户购买的物品，是单维关联规则： 啤酒= 尿布 而下面这条规则就涉及到两个字段的信息，是在两个维上的一条关联规则，故 而是多维关联规则： 性别= “女”= 职业= “秘书 ( 3 ) 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。 1 3 华北电力大学硕士学位论文 在单层关联规则( s i n g l e 一1 e v e la s s o c i a t i o nr u l e ) 中，只考虑处于同一概念 层次的项或属性间的关联，不涉及不同的概念层。 在多层关联规则( m u l t i l e v e la s s o c i a t i o nr u l e ) 中，考虑来源于不同概念层 次的项或属性间的关联。 例如，下面的关联规则处于同一概念层次上，所以是单层关联规则： “计算机= 打印机 下面的关联规则考虑了一个较高层次和细节层次之间的关联，故而是多层关联 规则： “i b m 台式机= “s o n y 打印机 ( 4 ) 根据关联挖掘的各种扩充，关联挖掘可以扩充到相关分析，还可以扩充到 挖掘最大模式和频繁闭项集。使用最大模式和频繁闭项集可以显著地压缩挖掘所产 生的频繁项集数。 给出了关联规则的分类之后，在以后的分析过程中，就可以考虑某个具体的方 法适用于哪一类规则的挖掘，某类规则又可以用哪些不同的方法进行处理。 3 1 3 关联规则的挖掘方法 关联规则的挖掘已经取得了令人瞩目的成果，到目前为止，已经产生了各种不 同的挖掘算法。归纳起来，主要有以下几种： ( 1 ) 多循环方式的挖掘方法 多循环方式的挖掘方法是关联规则挖掘的基本方法。此类算法包括a g r a w a l 等人提出的a p r i o r i ，p a r k 等人提出的分割算法p a r t i t i o n 以及t o i v o n e n 提出的 s a m p l i n g 抽样算法等等。 ( 2 ) 并行挖掘方法 目前提出的基于并行挖掘关联规则的算法有：a g r a w a l 等人提出的c d ( c o u n t d i s t r i b u t i o n ) ，c a d ( c a n d i d a t e d 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 ) ，p a r k 等人提出的p d m ( e f f i c i e n tp a r a l l e ld a t am i n i n gf o ra s s o c l a t i o nr u l e s ) c h u e n g 等人提出的算法d 姒( d i s t r i b u t e dm i n i n go fa s s o c i a t i o nr u l e s ) ，虽然是基于分 布式数据库的挖掘算法，但仍然适用于并行挖掘。 ( 3 ) 增量式更新方法 关联规则的增量式更新口们问题主要有两种情况：在给定的最小支持度和最小 置信度条件下，当数据库添加或者删除记录后，如何生成数据库中的关联规则； 1 4 华北电力大学硕士学位论文 给定一个数据库，当最小支持度和最小置信度发生变化时，如何生成数据库中的关 联规则。关联规则的更新算法有f u p ( f a s tu p d a t e ) ，i u a ( 1 a e r e m e n t a lu p d a t i n g a l g o r i t h m ) 、 p i u a ( p a r a l l e li n c r e m e n t a lu p d a t i n ga l g o r i t h m ) 和n i u a ( n e w i n c r e m e n t a lu p d a t i ga l g o r i t h m ) 。 ( 4 ) 基于约束的挖掘方法 基于约束的关联规则挖掘是在用户提供的各种约束的指导下发现更有趣、更实 用、更特别的关联规则的挖掘方法。这些约束条件包括知识类型约束、数据约束、 维层约束、兴趣度约束和规则约束等。 ( 5 ) 基于多值属性的挖掘方法 多值属性关联规则可分为数量关联规则和类别关联规则。 3 1 4 关联规则挖掘的研究方向 目前，关联规则挖掘方面的研究己经取得了较大的进展，但对下列问题仍有待 于进一步研究： 1 高效的挖掘算法 随着数据库的规模不断增大，不仅加大了挖掘算法的搜索空间，而且也增加了 盲目挖掘的可能性。因此必须结合领域知识去提取与我们发现任务有关的数据，删 除无用数据，有效地降低问题的维数，提高挖掘算法的效率。在这方面，基于约束 的关联规则挖掘具有广阔的前途乜t2 钉。 2 基于不同对象的挖掘 目前大多数挖掘关联规则算法都是基于关系数据库或事务数据库的算法，而数 据挖掘的对象是多种多样的，如：面向对象数据库、多维数据库、数据仓库等。设 计应用于不同类型数据库的关联规则挖掘算法也将是十分有意义的工作。 3 可视化挖掘 设计一个灵活方便的用户界面，允许用户与挖掘系统进行交互，并对所挖掘的 结果以可视化形式表示，使得挖掘的知识便于用户理解和使用。 4 模式评估 目前的关联规则的衡量标准可能会发现一些冗余的