（计算机软件与理论专业论文）挖掘关联规则的算法研究.pdf

独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为 获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 签名： 日期：理年6 月j 7 日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 徘斟黧冁 摘要 数据挖掘就是从大量的数据中提取或者“挖掘”知识，因此数据挖掘又被 称为数据库中的知识发现。它是一个涉及多学科领域的新兴学科，并随着这些 学科的发展而不断发展。数据挖掘具有几个功能，关联分析就是其中一项非常 重要的功能。 关联分析用于发现关联规则，关联规则描述了给定数据集的项之间的有趣 联系。目前，已经提出了许多挖掘关联规则的算法，其中最著名的是a p r i o r i 算 法及其变形。这些传统的算法大多存在项集生成瓶颈和难以确定合适的支持度 阀值的问题，并且没有考虑数据库的被分析项的各自不同的重要性。为了解决 这些问题，本文提出一个新算法b a s e s e t算法。_weight 本文首先介绍了数据挖掘的基本概念、存在问题及发展方向。其次介绍了 关联分析的基本概念、分类及一些常见的算法思想，其中着重讨论了挖掘关联 规则的经典算法a 砷o r i 算法的基本思想，并介绍了旨在提高该算法效率的 一些变形算法。最后，针对如a p r i o r i 算法这样的传统算法存在的一些问题，提 出了一种基于种子项和权的新算法b a s e s e tw e i g h t 算法，并详细讨论了该算 法的设计思路、设计过程及性能研究。 关键词：数据挖掘，关联规则，基集，种子项，权 a b s t r a c t d a t am i n i n gi st oe x t r a c to rm i n ek n o w l e d g ef r o ml a r g ea m o u n to fd a t a s oi ti s a l s oc a l l e dk n o w l e a g ed i s c o v e r yi nd a t a b a s e i ti san e ws u b j e c tt h a ti n v o l v e sal o t o fs u b j e c t sa n dd e v e l o p sw i t ht h e s es u b j e c t s d a t am i n i n gh a ss e v e r a lf u n c t i o n s a s s o c i a t i o na n a l y s i si so n eo f t h ei m p o r t a n tf u n c t i o n s a s s o c i a t i o na n a l y s i si st of i n da s s o c i a t i o nr u l e s a s s o c i a t i o nr u l e sd e s c r i b et h e i n t e r e s t i n gr e l a t i o n so f t h ei t e m si nt h eg i v e nd a t as e t a tp r e s e n t ，l o t so fa l g o r i t h m s f o rm i n i n ga s s o c i a t i o nr u l e sh a v eb e e nb r o u g h tf o r w a r d t h em o s tf a m o u sa l g o r i t h m s a r ea p r i o r ia n di t st r a n s f i g u r a t i o n t h e s et r a d i t i o n a la l g o r i t h m so f t e ns u f f e rf r o mt h e b o t t l e n e c ko fi t e m s e tg e n e r a t i o na n dd i f f i c u l t l yc o n f i r mas u i t a b l em i n i m u ms u p p o r t i nt h i sp a p e r , an e wa l g o r i t h mc a l l e db a s e 耽动fi sp r o p o s e dt os o l v et h ea b o v e p r o b l e m s f i r s t l y , i nt h i sp a p e r ；w ei n t r o d u c e dt h eb a s i cc o n c e p t ，p r o b l e me x i s t e da n d d e v e l o p m e n tw a y ；s e c o n d l nw ei n t r o d u c e dt h eb a s i cc o n c e p t ，c l a s s i f i c a t i o na n ds o m e f a m i l i a ra l g o r i t h mi d e a so fa s s o c i a t i o na n a l y s i s t h ei d e ao ft h ec l a s s i c a la l g o r i t h m a p r i o r ii st h ee m p h a s i sa n ds o m eo fk st r a n s f o r m a t i v ea l g o r i t h m sa r ei n t r o d u c e dt o i m p r o v et h ee f f i c i e n c y i nt h ee n d ，t os o l v et h ep r o b l e m se x i s t e di nt h et r a d i t i o n a l a l g o r i t h m ss u c ha sa p r i o r i ，an e wa l g o r i t h mc a l l e db a s e r v e 动tb a s e do nt h es e e di t e ma n d w e i g h ti sp r o p o s e d i t sd e s i g ni d e a , d e s i g np r o c e s sa n dp e r f o r m a n c es t u d ya r ed i s c u s s e d a tl a r g e k e y w 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 ，b a s es e t ，s e e di t e m ，w e i g h t 。 1 1 挖掘关联规则的算法研究 引言 在二十世纪后半段，信息技术以日新月异的速度飞速发展，由此带动了数 据库技术的迅猛发展。各种存储着大量信息的数据库不断出现，这些数据库大 多容量巨大，需要有有效的数据处理技术对它们进行分析处理，以从中得到人 们想要的信息。数据挖掘技术就是一门重要的数据处理技术。 数据挖掘可以采用多种技术对数据进行分析处理，在这当中，关联分析是 最重要的技术之一。关联分析以关联规则的形式来描述不同数据之间的联系， 通过这些描述，可以帮助人们完成许多有用的工作。目前，挖掘关联规则的技 术正处在一个不断发展的过程中，有着很好的发展前景。 本论文的课题来源于国家自然科学基金项目“神经网络的动力学行为”。在 章毅教授的指导下，我选择了“挖掘关联规则的算法研究”作为我的毕业论文 的题目。 经过一段时间的资料查阅、理论研究和与指导教师及同教研室同学的多次 讨论后，我对关联规则的挖掘这一技术有了比较多的了解和掌握，并形成了自 己的一些心得。在总结这些心得的基础上，经过章毅教授的精心指导，我写了 一篇名为( ( m i n i n ga s s o c i a t i o nr u l e sb a s e do ns e e di t e m sa n dw e i g h t s ) ) 的文章， 并已向j o u r n a l o f c o m p u t e r s c i e n c ea n d t e c h n o l o g y ( 计算机科学与技术) 杂志投 稿。本论文就是在这篇投稿论文的基础上形成的。 本文共分三章，具体内容如下： 第一章：数据挖掘。本章首先介绍了数据挖掘的产生。然后介绍了数据挖 掘的基本概念、应用范围和功能。最后介绍了数据挖掘面临的主要问题及其发 展方向。 第二章：关联规则。本章首先从一个示例出发，介绍了关联规则的基本概 念。然后讨论了关联规则的分类。最后详细介绍了挖掘关联规则的常用算法的 基本思想，并讨论了提高关联规则挖掘效率一些方法。 第三章：个挖掘关联规则的新算法b a s e s e tw e i g h t 算法。本章提出的 b a s e s e tw e i g h t 算法是为了解决传统的挖掘关联规则的算法存在的一些问题。在 本章中，b a s e s e tw e i g h t 算法的产生动机、设计思路、详细过程以及性能测试都 作了详细的介绍说明。本章的最后还介绍了个基于b a s e s e tw e i g h t 算法的关联 规则挖掘系统。 挖掘关联规则的算法研究 第一章数据挖掘 数据挖掘是数据库研究、开发和应用最活跃的分支之一。它不满足于对数 据的简单查询，而是想从众多的数据中找出更多有用的东西( 知识) ，所以数据 挖掘的过程又被称为知识发现的过程。从某种意义上讲，数据挖掘的自主性使 得计算机具有一定的“智能”，可以实现许多人力所无法完成的事情，因此让计 算机对人类的辅助作用得到了更大的发挥，信息资源也得到了更大的利用。 1 i 数据挖掘的产生 近年来，随着数据库技术的不断发展，存储在数据库中的信息量也在大量 增加，怎样从一大堆随机的数据中发掘出一些有价值的信息逐渐成为一个重要 的课题，由此带动了数据挖掘技术的产生和飞速发展。 自数据库这一概念出现以来，数据库技术的发展经历了几个重要的阶段。 最初的数据是由一些原始的文件来存储，在2 0 世纪6 0 年代，功能强大也更加 复杂的数据库系统取代了原始的文件处理，数据库技术正式进入了飞速发展的 崭新阶段。自7 0 年代以来，数据库系统的研究和开发已经从层次和网状数据库 系统发展到开发关系数据库系统、数据建模工具、索引和数据库组织技术。此 外，用户通过查询语言、用户界面、优化的查询处理和事务管理，可以方便、 灵活地访问数据。在8 0 年代中期以后，各种纷繁复杂的数据库技术更是如雨后 春笋般地出现。首先是各种类型的数据模型被广泛采用，如扩充关系模型、面 向对象模型、对象关系模型和演绎模型。其次是数据库存储的内容的应用 的范围不断丰富，包括空间的、时间的、多媒体的、主动的和科学的数据库、 知识库及办公信息库。同时，涉及分布性、多样性和数据共享问题被广泛研究。 在最近的几年，异种数据库和基于互连网的全球信息系统，如w w w 也已出现， 并成为信息产业的主力军。图1 1 归纳了数据库技术的演化过程。 数据的丰富带来了对强有力的数据分析工具的需求。大量的数据被描述为 “数据丰富，但信息贫乏”，因为存储在大型数据库中的数据可以用海量来形容， 理解这些数据中隐含的知识已经超出了人力的范围，没有强有力的分析工具， 这些数据就变成了“数据坟墓”很难再访问的数据档案。于是，数据挖掘 技术应运而生，利用数据挖掘工具进行数据分析，可以发现重要的数据模式， 对商务决策、知识库、科学和医学研究作出了重大贡献。数据和信息之间的鸿 挖掘关联规则的算法研究 沟要求系统地开发数据挖掘工具，将数据的“坟墓”转变成知识的“金块”。 数据收集和数据库创建 ( 20 世纪60 年代和更早) 一原始文件处理 数据库管理系统 ( 70 年代) 一层次和网状数据库系统 一关系数据库系统 一数据建模工具：实体联系模型等 一索引和数据库组织技术：b + 树，散列等 一查询语言：s q l 等 一用户界面：表单、报告等 一查询处理和查询优化 一事务管理：恢复和并发控制等 一联机事务处理( o l t p ) 高级数据库系统 ( 80 年代中期一现在) 一高级数据模型： 扩充关系、面向对象、对象 关系、演绎 一面向应用： 空间的、时间的、多媒体的、 主动的、科学的、知识库 基于w e b 的数据库系统 ( 90 年代一现在) 一基于x m l 的数据库系统 一w e b 挖掘 数据仓库和数据挖掘 ( 80 年代后期一现在) 数据仓库和o l a p 技术 数据挖掘和知识发现 新一代综合信息系统 ( 20 00 一) 图卜i 数据库技术的演化 3 挖掘关联规则的算法研究 1 2 数据挖掘的一般性讨论 1 2 1 什么是数据挖掘 简单地说，数据挖掘就是从大量的数据中提取或者“挖掘”知识。在许多 场合下，数据挖掘又被称为数据库中的知识发现( k n o w l e d g ed i s c o v e r yi n d a t a b a s e ，简称k d d ) 。但是，更科学的说法是将数据挖掘视为数据库知识发现 的一个基本步骤。在这种情况下，数据库的知识发现过程由以下几个步骤组成： ( 1 ) 数据清理：消除噪声或者不一致数据。 ( 2 ) 数据集成：多种数据源可以组合在起。它和数据清理一起被视为 预处理步骤，结果数据存放在数据仓库中。 ( 3 ) 数据选择：从数据库中检索与分析任务相关的数据。 ( 4 ) 数据变换：将数据变换或统一成适合挖掘的形式，如通过汇总或聚 集操作。在有些场合下，数据变换在数据选择过程之前进行，特别 是在数据仓库的情况下。 ( 5 ) 数据挖掘：使用智能方法提取数据模式。 ( 6 ) 模式评估：根据某种兴趣度度量，识别表示知识的真正有趣的模式。 ( 7 ) 知识表示：使用可视化和知识表示技术，向用户提供挖掘的知识。 尽管将数据挖掘视为数据库知识发现过程的一个基本步骤更为科学，但是 在产业界、媒体和数据库研究界，将数据挖掘直接当作数据库中的知识发现更 为流行。因此数据挖掘有了一个更加广泛的概念：数据挖掘是从存放在数据库、 数据仓库或其他信息库中的大量数据中挖掘有趣知识的过程。基于这种观点， 一个典型的数据挖掘系统可以由以下几个主要成分组成( 如图1 2 所示) ： 数据库、数据仓库或其他信息库：这是一个或一组数据库、数据仓库、 电子表格或其他类型的信息库。可以在数据上进行数据清理和集成。 数据库或数据仓库服务器：根据用户的数据挖掘请求，数据库或数据仓 库服务器负责提取相关数据。 知识库：用于指导搜索或评估结果模式的兴趣度。 数据挖掘引擎：数据挖掘系统基本的部分，由一组功能模块组成，用于 特征化、关联、分类、聚类分析以及演变和偏差分析。 模式评估模块：通常，此成分使用兴趣度度量，并与数据挖掘模块交互， 4 挖掘关联规则的算法研究 以使将搜索聚焦在有趣的模式上。它可能使用兴趣度阀值过滤发现的模式。模 式评估模块也可以与挖掘模块集成在一起，这依赖于所用的数据挖掘方法的实 现。 图形用户界面：实现用户和数据挖掘系统之间的通信，允许用户与系统 交互，指定数据挖掘查询或任务，提供信息、帮助搜索聚焦，根据数据挖掘的 中间结果进行探索式数据挖掘。此外，此成分还允许用户浏览数据库和数据仓 库模式或数据结构，评估挖掘的模式，以不同的形式对模式可视化。 图形用户界面 上f 模式评估 j r下 数据挖掘引擎 上t 数据库或数据仓库服务器 图l 一2 典型的数据挖掘系统结构 1 2 2 数据挖掘的应用范围 数据挖掘的应用范围是指数据挖掘能够在什么样的数据存储上进行。从原 则上讲，数据挖掘应该能够在任何类型的信息存储上进行，包括关系数据库、 数据仓库、事务数据库、高级数据库系统、展开文件和w w w 。 l 、关系数据库 数据库系统，通常又被称为数据库管理系统( d b m s ) ，由一组内部相关的 挖掘关联规则的算法研究 数据和一组管理和存储数据的软件程序组成。软件程序涉及以下机制：数据库 结构定义，数据存储，并发、共享、或分布的数据访问，在面对系统瘫痪或未 经授权的访问时确保数据的一致性和安全性。 关系数据库是表的结合，每个表都赋予一个唯一的名字。每个表包含一组 属性( 列或字段) ，并通常存放大量元组( 记录或行) 。关系中的每个元组代表 一个被唯一的关键字标识的对象，并被一组属性值描述。语义数据模型，如实 体联系( e r ) 数据模型，将数据库作为一组实体和它们之间的联系进行建 模。 关系数据库通常采用数据查询的方式进行访问，数据查询使用关系查询语 言，如著名的s q l 语言，或者借助于图形用户界面书写。当数据挖掘应用于关 系数据库时，可以进一步搜索趋势或数据模式。例如，数据挖掘系统可以分析 顾客数据，根据顾客的收入、年龄和以前的信用信息来预测新顾客的信用风险。 在数据挖掘应用的数据源中，关系数据库是最流行和最丰富的，因此也是数据 挖掘研究的主要数据形式。 2 、数据仓库 数据仓库是一种全新的数据存储模式。它是一种语义上一致的数据存储， 充当决策支持数据模型的物理实现，并存放企业战略决策所需的信息。与其他 数据存储系统相比，数据仓库具有以下四个明显的特征： 面向主题的：数据仓库围绕一些主题，如顾客、供应商、产品和销售进 行组织。数据仓库关注决策者的建模与分析，而不是集中于组织机构的日常操 作和事务处理。 集成的：数据仓库通常是将多个异种数据源，如关系数据库、一般文件 和联机事务处理记录，集成在一起。因此，数据仓库排除对于决策无用的数据， 提供特定主题的简明视图。 时变的：数据存储从历史( 如过去的5 1 0 年) 的角度提供信息。数据仓 库中的关键结构，隐式或显式地包含时间元素。 非易失的：数据仓库总是物理地分离存放数据，这些数据源于操作环境 下的应用数据。由于这种分离，数据仓库不需要事务处理、恢复和并发控制机 制。通常，它只需要两种数据访问：数据的初始化装入和数据访问。 数据仓库最常见的应用有三种： 信息处理：支持查询和基本的统计分析，并使用交叉表、表、图表或图 挖掘关联规则的算法研究 进行报告。 分析处理：支持基本的联机分析处理( o l a p ) 操作。一般地，它在汇总 的和细节的历史数据上操作。同时，它支持数据仓库的多维数据分析。 数据挖掘：支持知识发现，包括找出隐藏的模式和关联，构造分析模型， 进行分类和预测，并用可视化工具提供挖掘结果。 在数据仓库的三种应用中，信息处理可以反映直接存放在数据库中的信息， 但并不反映复杂的模式或隐藏在数据库中的规律。联机分析处理可以由用户选 定的数据仓库子集，在多粒度上导出汇总的信息，由此帮助简化数据分析。而 数据挖掘则更进一层，它的目标是尽可能自动地发现隐藏在大量数据中的隐含 模式和有趣知识。 3 、事务数据库 事务数据库通常由一个文件组成，其中每个记录代表一个事务。通常，一 个事务包含一个唯一的事务标识号( t r a n s a c t i o ni d ，简称t i d ) ，和一个组成事 务的项的列表。事务可以存放在表中，每个记录代表一个事务。 4 、高级数据库系统和高级数据库应用 高级数据库系统是面向特殊应用的数据库系统，包括以下一些： 面向对象的数据库：采用基于面向对象的程序设计范例。每个实体被看 作为一个对象，涉及一个对象的数据和代码封装在一个单元中。 对象关系数据库：基于对象关系模型构造。此模型通过提供处 理复杂对象的丰富数据类型和对象定位，扩充关系模型。此外，它还包含关系 查询语言的特殊构造，以便管理增加的数据类型。 空间数据库：包含涉及空间的信息。这种数据库包含地理( 地图) 数据 库，v l s l ( v e r yl a r g es c a l ei n t e g r a t i o n ，超大规模集成电路) 芯片设计数据库、 医疗和卫星图象数据库。空间可能以光栅格式( r a s t e rf o r m a t ) 提供，由n 维位 图或象素图构成。 时间和时间序列数据库：存放与时间有关的数据。 文本数据库：包含对象文字描述的数据库。通常这种描述不是简单的关 键词，而是长句子或短文，如产品介绍、汇总报告等。文本数据库可能是高度 非结构化的( 如w w w 上的网页) ，可能是半结构化的( 如e - m a i l 消息和一些 x m l h t m l 网页) ，也可能是良结构化的( 如图书馆数据库) 。 多媒体数据库：存放图象、音频和视频数据。它们用于基于图象内容的 挖掘关联规则的算法研究 检索、声音传递、视频点播、w w w 和识别口语命令的基于语音的用户界面等 方面。 异种数据库：由一组互连的、自治的成员数据库组成。这些成员间相互 通信，以便交换信息和回答查询。一个成员数据库中的对象可能与其他成员数 据库中的对象很不相同，使得很难将它们的语义吸收进一个整体的异种数据库 中。 遗产数据库：是一组异种数据库，它将不同的数据系统组合在一起。 基于w w w 的全球信息系统：w w w 和与之关联的分布式信息服务提供 了丰富的、世界范围的联机信息服务。在这里，数据对象被链接在一起，便于 交互访问。 1 2 3 数据挖掘的功能 数据挖掘功能用于指定数据挖掘任务中要找的模式类型。数据挖掘任务一 般可以分为两类：描述和预测。描述性挖掘任务刻划数据库中数据的一般特性， 而预测性挖掘任务则在当前数据上进行推断，以进行预测。 在很多情况，用户并不知道什么样的模式是有趣的，因此可能想探索多种 不同的模式，以从中选择出自己感兴趣的模式。这就要求数据挖掘系统应该能 够挖掘多种类型的模式，以适应不同的需求。此外，数据挖掘系统应该能够发 现各种粒度( 即不同的抽象层) 的模式，应当允许用户给出提示，指导或聚焦 有趣模式的搜索。 数据挖掘的功能以及可以发现的模式类型有：概念类描述、关联分析、分 类和预测、聚类分析、孤立点分析和演变分析。 l 、类概念描述 数据可以与类或概念相关联。用汇总的、简洁的、精确的方式描述每个类 和概念可能是有用的。这种类或概念的描述称为类概念描述。这种描述可以通 过以下方法得到： 数据特征化：是目标类数据的一般特征或特性的汇总。 数据区分：将目标类对象的一般特性与一个或多个对比类对象的一般特 性比较。 数据特征化和区分：同时应用数据特征化和数据区分进行描述。 2 、关联分析 挖掘关联规则的算法研究 关联分析用于发现关联规则，关联规则描述了给定数据集中的项之间的有 趣联系。关联分析广泛应用于购物篮或事务数据分析。从大量商务事务记录中 发现有趣的关联关系，可以帮助许多商务决策的制定，如分类设计、交叉购物 和贱卖分析等。 3 、分类和预测 分类是找出描述并区分数据类或概念的模型的过程，以便能够使用模型预 测类标记未知的对象类。预测是构造和使用模型评估无标号样本类，或评估给 定样本可能具有的属性值或值区间。分类和预测之间的区别在于，分类是预测 类标号( 或离散值) ，而预测是建立连续值函数模型。例如，可以建立一个分类 模型，对银行贷款的安全或风险进行分类；同时可以建立预测模型，给定潜在 顾客的收入和职业，预测他们在计算机设备上的花费。 4 、聚类分析 聚类将数据对象分组成为多个类或簇，在同一个簇中的对象之间具有较高 的相似度，而不同簇中的对象差别较大。与分类不同的是，它要划分的类是未 知的。 5 、孤立点分析 在数据库中经常存在一些数据对象，它们不符合数据的般模型。这样的 数据对象被称未孤立点，它们与数据的其他的部分不同或不一致。孤立点可能 是度量或执行错误所导致的。例如，数据库记录中有一些人的年龄是一9 9 9 ，这可 能是这些人年龄没有被记录，而系统给未记录的年龄的缺省值就是9 9 9 。孤立点 也可能是固有的数据变异后的结果。例如，一个公司总裁的薪水可能远远高于 其他职员的薪水，他的薪水就成为了一个孤立点。在许多时候，孤立点被视为 噪声或遗产而被丢弃，但是，在一些应用中，孤立点可能会很有用。例如，在 医疗分析中，某些对多种治疗方式的不寻常的反应数据可能成为孤立点，但是 这些数据对于治疗却非常重要。对孤立点数据进行分析称为孤立点分析。 6 、演变分析 数据演变分析描述行为随时间变化的对象的规律或趋势，并对其建模。这 种分析可能包括时间相关数据的特征化、区分、关联、分类或聚类，但是它的 不同特点包括时间序列数据分析、序列或周期模式匹配和基于类似性的数据分 析。 挖掘关联规则的算法研究 1 3 数据挖掘面临的主要问题 数据挖掘面临的主要问题有三大类：挖掘方法和用户交互的问题、性能问 题和存储数据的数据库类型具有多样性的问题。 1 、挖掘方法和用户交互问题 这类问题涉及到数据挖掘技术的多个方面，主要有以下一些内容： 在数据库中挖掘不同类型的知识：由于不同的用户感兴趣的知识类型可 能会很不相同，这就要求数据挖掘系统应当覆盖范围很广的数据分析和知识发 现任务，包括数据特征化、区分、关联、分类、聚类、趋势和偏差分析以及类 似性分析。这些方式可能以不同的方式使用相同的数据库，并需要开发大量的 数据挖掘技术。 多个抽象层的交互知识挖掘：由于在进行数据挖掘之前很难知道将要挖 掘出来的是什么样的知识，因此需要数据挖掘的过程具有交互性。对于大型的 数据库，应当使用抽样技术进行交互式的数据探查。交互式挖掘允许用户聚焦 搜索模式，根据返回的结果提出和精炼数据挖掘请求，从而使用户可以以不同 的粒度和从不同的角度观察数据和发现模式。 结合背景知识：可以使用背景知识或关于所研究领域的信息来指导发现 过程，并使得发现的模式以简洁的形式在不同的抽象层表示。关于数据库的领 域知识，如完整性约束和演绎规则，可以帮助聚焦和加快数据挖掘过程，或评 估发现的模式的兴趣度。 数据挖掘查询语言和特定的数据挖掘：与现在存在大量的高级程序开发 语言相比，数据挖掘还缺乏一门统一的高级语言用于描述数据挖掘的过程和结 果。关系查询语言( 如s q l ) 智能允许用户提出特定的数据检索查询，而对数据 挖掘高级语言的要求则更高，它应该能够使用户通过说明分析任务的相关数据 集、领域知识、所挖掘的数据类型、被发现的模式必须满足的条件和约束，描 述特定的数据挖掘任务。这种语言应当与数据库或数据仓库查询语言集成，并 且对于有效的、灵活的数据挖掘是优化的。 数据挖掘结果的表示和显示：高级语言、可视化表示或其他形式的表示 方法可以使知识易于理解，能够被人们直接使用。这要求系统采用有表达能力 的知识表示技术，如树、表、规则、图、图表、交叉表、矩阵或曲线。 处理噪声和不完全数据：存放在数据库中的数据可能反映噪声、异常情 况或不完全的数据对象，它们可能搞乱分析过程，导致数据与所构造的知识模 型过分适应，由此导致所发现的模式精确性很差。这就需要处理数据噪声的数 挖掘关联规则的算法研究 据清理方法和数据分析方法，以及发现和分析异常情况的孤立点挖掘方法。 模式评估兴趣度问题：数据挖掘方法发现的模式通常数以千计，怎 样从中选择出用户感兴趣的模式是一个极具挑战性的问题。 2 、性能问题 数据挖掘算法的有效性和可伸缩性：数据挖掘算法的有效性要求算法的 运行时间应尽可能地少，而可伸缩性则要求算法能够适应不同大小的数据库容 量，算法的运行时间应尽可能地与数据库的容量保持线性比例的增减关系。 并行、分布式和增量挖掘算法：并行和分布式数据挖掘算法将数据划分 成多个部分，这些部分可以并且处理，然后将各个处理结果合并。这种类型的 算法可以对付数据库的大容量、数据的广泛分布和一些数据挖掘算法的计算复 杂性的问题。而数据挖掘过程的高花费导致了对增量挖掘算法的需求，这种类 型的算法和数据库更新结合在一起，它不必随着数据库的更新重新挖掘全部数 据，而只需要在原有挖掘结果的基础上修正和加强业已发现的知识。 3 、关于数据库类型的多样性问题 关系的和复杂的数据类型的处理：由于数据库类型的多样性，指望个 系统挖掘所有类型的数据是不现实的。为挖掘特定类型的数据，应当构造特定 的数据挖掘系统。 由异种数据库和全球信息系统挖掘信息：局域网和广域网( 如互连网) 提供了大量庞大的、分布式的和异种的数据库。从具有不同语义的结构化的、 半结构化的和非结构化的不同数据源发现知识，是数据挖掘技术面临的一个巨 大挑战。 1 4 数据挖掘的研究与开发方向 数据挖掘现在是数据库研究、开发和应用最活跃的分支之一，它涉及了计 算机科学中的多个领域，这些领域包括传统的数据库技术、人工智能、机器学 习、神经网络、统计学、模式识别、知识库系统、知识获取、信息提取、高性 能计算和数据可视化等学科。随着这些学科的不断发展，数据挖掘也需要不断 的发展。作为一门新兴的技术，数据挖掘的发展也是适应科技发展大潮流的需 要。针对数据挖掘现在面临的主要问题，数据挖掘的研究与开发最主要的方向 有以下一些： 与数据仓库与在线分析处理技术结合：数据仓库可以为在线分析处理和 数据挖掘提供经过滤化的、完整的数据资源。在线分析处理可以看作为一个简 挖掘关联规则的算法研究 化的对数据进行聚合的数据挖掘形式。与在线分析处理工具相结合，一个数据 挖掘器( d a t am i n e r ) 能够深入到一个数据立方体( d a t ac u b e ) 的任意一维，从而在 不同的抽象层上找到用户感兴趣的形式，由此也增加了数据挖掘与数据仓库系 统的用途。 挖掘多种类型的知识：数据挖掘除了最常见的分类与关联之外，还有许 多重要的任务待开发，包括描述、比较、聚合、预测模型以及时间相关形式分 析等等。 提供对数据挖掘的查询语言和高效、交互式及特殊数据挖掘的支持：与 相关语言类似，高层次的数据挖掘语言应该能够允许用户定制特殊的数据挖掘 任务。 处理复杂数据：挖掘关联性和事务性的数据是目前数据挖掘的中心。但 是对于半结构化以及非结构化的数据进行挖掘，也是一个非常重要而极富挑战 性的方面。 高性能的数据挖掘：高效性和可伸缩性是目前数据挖掘算法的焦点，随 着并行的、分布式的以及增长式的数据挖掘技术的发展，这种趋势将会继续得 到发展。 可视化和数据挖掘：数据库内容和数据挖掘结果的可视化可以帮助用户 理解和评估挖掘结果，从而对数据挖掘进行相应的调整。对交互式的挖掘来说， 开发易用与易看的工具是一个很有发展空间的领域。 数据挖掘的应用：如何将数据挖掘技术应用于现实世界也是一个非常重 要的课题。 挖掘关联规则的算法研究 第二章关联规则 关联分析是数据挖掘诸多功能中的一种，也是虽为重要和应用最广泛的一 种。关联分析用于发现关联规则，关联规则描述了给定数据集的项之间的有趣 联系。通过这些描述，可以从大量的商务事务记录中发现有趣的关联关系，可 以帮助许多商务决策的制定，如分类设计、交叉购物和贱卖分析等。因此，购 物篮或事务数据分析是关联分析应用最多的场合。 2 1 关联规则的基本概念及问题描述 2 1 1 挖掘关联规则的一个典型例子 购屋篮分析是关联规则挖掘应用最多的场合之一。假如有一个销售计算机 软、硬件的商店，购物篮分析可以帮助经理设计不同的商店布局。例如，用户 在购买计算机的同时一般要购买一些工具软件，那么把销售工具软件的柜台放 到与销售计算机的柜台临近的地方，就可以促进工具软件的销量。又比如，可 以将计算机与销售情况最好的软件( 如家庭财务软件) 分别放置在商店的两端， 在两者之间放置一些销售情况一般甚至较差的软件( 如家庭安全系统软件) ，那 么用户在决定购买计算机之后，他一般要购买家庭财务软件，在从销售计算机 的柜台到销售家庭财务软件的柜台的路途上，他看到了家庭安全系统软件，这 就可能促使他产生购买该软件的愿望。购物篮分析也可以帮助商家进行贱卖分 析，例如，如果一些用户趋向于在购买计算机的同时购买一台打印机，那么打 印机的降价就可能既促进打印机的销售情况，又促进计算机的销售情况。 关联规则可以以蕴涵式来表示上述购物篮分析的具体应用情况，例如，购 买计算机的同时趋向于购买财务软件的具体情况可以用如下的关联规则来表 不： 计算机j 财务管理软件( 支持度= 3 5 ，置信度= 7 0 ) 规则的支持度与置信度是衡量规则兴趣度的两个度量。支持度用于衡量规 则的有用性，3 5 的支持度表示了占全部事务总数的3 5 的事务同时购买了计 算机和财务关联软件。置信度用于衡量规则的确定性，7 0 的置信度表示了购买 计算机的顾客中有7 0 的顾客同时又购买了财务管理软件。如果上述的支持度 和置信度的值均大于事先给定的支持度阀值和置信度阀值，那么这个关联规则 就是有趣的。 挖掘关联规则的算法研究 2 1 2 关联规则的基本概念 关联规则的基本概念可以通过一系列的定义来进行描述。设1 - i l ，屯，谢 是项( i t e m ) 的非空集合，用2 j 表示，的所有子集。设d 为事务t 的集合，而事务 ，则是某些项的集合，并且丁量，。每一个事务有唯一的标识符，记作t i d 。项 的集合称为项集( i t e m s e t ) ，包含k 个项的项集称为k 一项集。设z 是一个项集， 如果x c t ，那么称事务丁包含j ，。 定义一：设工y 2 7 并且x n 卜毋，形如j 壬j y 的蕴涵式称为一个关联规则。 定义二：包含项集x 的事务7 1 在d 中所占的百分比称为项集z 的支持度， 记作，i 殉。，是一个值域为( 0 ，1 ) 的函数，并且对于任意的z 】，都存在f i x ) 兰，m 的关系式。空集的支持度为1 ，即斤剀= 1 。关联规则j o 】，的支持度记为 f ( x u ，即包含x 和y 二者的事务在d 中所占的百分比。 定义三：设正】，为一个关联规则，同时包含爿和y 二者的事务在d 中所占 的百分比称为该关联规则的置信度，它的值为f ( x t oy ) f ( x ) 。 定义四：设xy 2 7 并且x n l i - - 曲，形如j ， l ，的蕴涵式称为一个对等关 联规则。它的支持度记为f ( x u 习，置信度的值为m i n f ( x uy ) f ( x ) ，f ( x ud f ( y ) 】。 定义五：给定一个事务集d ，挖掘关联规则问题就是产生支持度和置信度分 别大于用户给定的支持度阀值f 5 印) 和置信度阀值( m i n c o 劝的关联规则，这样 的规则也被称为强规则。 定义六：设x e 2 ，如果f i x ) 量m i n s u p ，则称为频繁项集。 2 2 关联规则的分类 根据不同的标准，关联规则有多种分类方法： 1 、根据规则中所处理的值类型：可以分为布尔关联规则和量化关联规则。 如果规则考虑的关联是项的在与不在，则它是布尔关联规则。如果规则描述的 是量化的项或属性之间的关联，则它是量化关联规则。在这种规则中，项或属 性的量化值划分为区间。 例如，下面的关联规则是布尔关联规则： 购买计算机= 购买财务软件 下面的关联规则是量化关联规则： 年龄( “2 5 ，3 5 ”) 八年收入( “4 万，5 万”) = 购买计算机 2 、根据规则集所涉及的抽象层：可以分为单层关联规则和多层关联规则。 在单层关联规则中，规则不涉及不同抽象层的项或属性；而在多层关联规则中， 4 挖掘关联规则的算法研究 规则涉及不同抽象层的项或属性。 例如，下面的关联规则是单层关联规则： 年龄( “2 5 ，3 5 ”) = 购买计算机 下面的关联规则是多层关联规则： 年龄( “2 5 ，3 5 ”) ： 购买计算机，年龄( “2 5 ，3 5 ”) = 购买台式计算机 3 、根据规则中涉及的数据的维数：可以分为单维关联规则和多维关联规则。 如果关联规则中的项或属性每个只涉及一个维，则它是单维关联规则；如果规 则涉及两个或多个维，则它是多维关联规则。 例如，下面的关联规则是单维关联规则，它只涉及了一个维“购买”： 购买计算机= 购买财务软件 下面的关联规则是多维关联规则，它涉及了三个维“年龄”、“年收入” 和“购买”： 年龄( “2 5 ，3 5 ”) 八年收入( “4 万，5 万”) = 购买计算机 4 、根据对关联挖掘的不同扩充：可以扩充为相关分析、最大频繁模式与频 繁闭项集挖掘。相关分析可以识别项是否相关。最大模式是一个频繁模式p ，使 得p 的任何真超模式( 即包含p 的模式) 都不是频繁的。频繁闭项集是一个频 繁的闭的项集，即如果项集c 是闭的，那么就不存在c 的任何真超集c ，使得包 含c 的子模式的每个事务也包含c 。使用最大频繁模式与频繁闭项集可以显著地 减少挖掘所产生的频繁项集的数量。 2 3 挖掘关联规则的基本步骤 挖掘关联规则的步骤大体可以由一个两步的过程来进行描述： ( 1 ) 找出所有的频繁项集。即找出所有那些支持度大于事先给定的支持度 阀值的项集。 ( 2 ) 在找出的频繁项集的基础上产生强关联规则。即产生那些支持度和置 信度分别大于或等于事先给定的支持度阀值和置信度阀值的关联规则。 在上述两个步骤中，第二个步骤相对要容易一些，因为它只需要在已经找 出的频繁项集的基础上列出所有可能的关联规则，然后用支持度阀值和置信度 阀值来衡量这些关联规则，同时满足支持度阀值和置信度阀值要求的关联规则 就被认为是有趣的关联规则。事实上，由于所有的关联规则都是在频繁项集的 基础上产生的，它们就已经自动地满足了支持度阀值的要求，从而只需要考虑 置信度阀值的要求。第一个步骤是挖掘关联规则的关键步骤，挖掘关联规则的 挖掘关联规则的算法研究 总体性能由第一个步骤决定，因此所有挖掘关联规则的算法都是着重于研究第 个步骤。 2 4 挖掘关联规则的经典算法一a p r io ri 算法 早在i b m 的a l m a d e n 研究中心的成员a g r a w a l 等在1 9 9 3 年发表的论文1 2 j 中 首次提出关联规则的概念时，就已经给出了一个挖掘关联规则的算法，但是这 个算法更多的是表明了关联规则的挖掘在理论上是可行的，而明显地在效率上 存在着很大的不足，因此难以实际应用到现实世界中。直到1 9 9 4 年，也是由 a g r a w a l 等在1 9 9 4 年发表的论文【) 1 中提出了一个著名的算法a p r i o r i 算法， 这个算法后来成为了关联规则挖掘算法中最经典的个算法，大量后续的研究 工作都是围绕着提高这个算法的效率进行。相对于a g r a w a l 等在1 9 9 3 年第一次 提出的算法，a p f i o r i 算法在效率上实现了质的飞跃，从而使挖掘关联规则的理 论可以实际地应用到现实世界中。 a p r i o r i 算法的基本思想可以用一段伪代码描述如下 ( 1 ) l l = l a r g e1 - i t e m s e t s ；倾繁1 一项集 ( 2 ) f o r ( k = 2 ；l k 1 m ；k + + ) ( 3 ) c k = a p r i o r i - g e n ( l k 1 ) ； 新的候选集 ( 4 )f o ra l lt r a n s a c t i o n st e d c 。= s u b s e t ( c k ，t ) ； 事务t 中包含的候选集 f o ra 1 1c a n d i d a t e sc c t ( 9 ) l k = c ec ni c c o u n t m i n s u p ) ( 1 0 ) ) ( 1 1 ) a n s w e r = u k l k ； 正如前面所述，挖掘关联规则的总体性能由产生频繁项集的步骤决定，因此 这段算法只讨论了怎样产生频繁项集。a p f i o d 算法采用了一种逐层搜索的迭代 方法：首先产生所有的频繁1 项集，然后在此基础上依次产生频繁2 项集、频 繁3 项集，直到不能找到频繁“项集。在此过程中，女一项集用于探索( 抖1 ) 项集。产生每个频繁项集需要扫描一次数据库。 6 i) 5 6 7 8；( 挖掘关联规则的算法研究 函数a p r i o r i g e n ( l k 1 ) 用于在频繁项集l k _ j 的基础上产生新的侯选集，它的基 本思想可以由两个步骤来进行描述： ( 1 ) 连接步：在第k 次循环中，过程先产生候选“项集的集合g ，g 中的 每一个项集是对两个只有一个项不同的属于l m 的频繁项集做一个( k - 2 ) 一连接来 产生的，其具体思想可以用一个s q l 命令语句描述如下： 1 n s e r t l n j o c k s e l e c tp i t e m t ，p i t e m 2 ，p i t e m k i ，q i t e m k 1 f r o m l k 1 p ，l k 1q w h e r e p i t e m 】= q i t e m l ，p i t e m k _ 2 2 q i t e m k 2 ，p i t e m k 1 一m i n c o 萌则输出规则s j 弘妙， 其中，m i n c o 是置信度阀值。 例如，对于前面产生的频繁3 一项集埘b e ) ，它的非空子集有即b ) ， ae ， b e ) ， a ， 占) 和 日，可能输出的关联规则如表2 - 8 所示。 关联规黜置信麦 a b j e o5 a e j b 1 b e j a 1 a j b eo3 3 b j a e o 2 9 e j a b l 表2 - 8 由频繁3 一项集 ab 日可能产生的关联规则 将这些关联规则的置