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

中文摘要 数据挖掘是致力于数据分析和理解，揭示数据内部蕴涵知识的技术，成为未 来信息技术应用的重要目标之一。关联规则是数据挖掘的重要模式之一，有着极 其重要的应用价值。 在整个数据挖掘的研究中，高效算法的研究占有特别重要的地位。由于数据 挖掘面对的是大量的数据集，因此算法的效率将对其应用起关键的作用。现有的 算法在时问和空间的复杂性有着难以克服的局限性。鉴于此，本文着重对关联规 则挖掘算法进行了研究。 本文概述了数据挖掘的现状和趋势，对关联规则做了一般性的讨论，包括关 联规则的概念，性质，种类，关联规则价值的衡量方法以及它的应用。在此基础 上，对关联规则算法做了深入的研究，分析了关联规则中经典a p r i o r i 算法及其 他学者对a p r i o r i 算法的改进算法，总结了算法存在的问题。 本文提出了针对于a p r i o r i 算法局限性的两种改进方案。第一种改进方案， 采用了项集有序特点和优化的事务压缩技术相结合的思想，减少了传统算法中需 要大量进行的操作和对数据库的扫描，以提高算法效率。第二种改进方案，针对 a p r i o r i 算法只适用于挖掘单维关联规则的问题，首先采用等深分箱的方法将量 化属性按引进的最大支持度进行离散化处理，然后在得到频繁集的时候对a p r i o f i 算法做了改进，实现其在多维关联规则中的应用，并在此基础上引入了函数依赖 概念，通过函数依赖和关联规则相互作用的性质对算法进行改进，缩小了候选集 的大小，提高算法效率，同时分析了这种该改进算法的应用性。最后提出了两种 a p r i o r i 算法改进方案结合的思想。 关键词：数据挖掘关联规则a p r i o r i 算法项集有序事务压缩函数依赖 d a t am i n i n gi sat e c h n i q u et h a ta i m st oa n a l y z ea n du n d e r s t a n dl a r g es o u r c ed a t a a n dr e v e a lk n o w l e d g eh i d d e ni nt h ed a t a i th a sb e e nv i e w e da sa ni m p o r t a n t e v o l u t i o nf o ri n f o r m a t i o np r o c e s s i n g a s s o c i a t i o nr u l ei so n eo ft h ei m p o r t a n t m o d e l so f d a t am i n i n g ，a n dh a st h em o s ts i g n i f i c a n ta p p l i c a t i o nf u t u r e a l g o r i t h mi sak e yp a r ti nd a t am i n i n g d a t am i n i n gi su s e df o rl a r g ed a t a b a s e s y s t e m s a n dt h ee f f i c i e n c yo fa l g o r i t h mi st h ek e y n l cc u r r e n ta l g o r i t h m sh a v ea d i s a d v a n t a g ei nt e r m so fs p a c ea n dt i m ec o m p u t a t i o nf u rag i v e nc o m p l e xp r o b l e m t h ea l g o r i t h mo fd a t am i n i n gw a ss t u d i e di nt h i sw o r k t h i ss t u d yb r i e f l yi n t r o d u c e dt h ec u r r e n ts t a t u sa n dd e v e l o p m e n tt r e n do fd a t a m i n i n g 1 1 1 ea s s o c i a t i o n r u l e si n c l u d i n gc o n c e p t sa n dp a t t e r n s ，c h a r a c t e r i s t i c s ， s y s t e m a t i cc l a s s i f i c a t i o n s ，t h ep a a e mo fv a l u em e a s u r e i n ga n dt h ea p p l i c a t i o no ft h e a s s o c i a t i o nr o l e sw e r ea l s od i s c u s s e di ng e n e r a l t h ea s s o c i a t i o nr u l ea l g o r i t h m s w h i c ha l ei m p o r t a n tp a r t si nt h ed a t am i n i n gw e r ed i s c u s s e di n - d e p t h c l a s s c i a l a p r i o na l g o r i t h m a n di m p r o v e da l g o r i t h m so fa p f i o f iw e r es t u d i e d b o t h a d v a n t a g e sa n dd i s a d v a n t a g e so f t h e s ea l g o r i t h m sw e r ep o i n t e do u ta sw e l l t w oi m p r o v e ds o l u t i o n so fa p d o r ia l g o r i t h mw e r ep r o p o s e di nt h i ss t u d y t h e f i r s ts o l u t i o na d o p t st h ec o m b i n a t i o no ft h eo r d e ri t e m s e t sa n dt r a n s a c t i o nr e d u c e d t e c h n i q u et os p e e du pp e r f o r m a n c eo f t h eo p e r a t i o n sa n ds c a n n i n gt h ed a t a b a s e n e s e c o n ds o l u t i o na l m st oo v e r c o m eo n e d i m e n s i o n a ld i s a d v a n t a g eo fa p r i o r ia l g o r i t h m a s s o c i a t i o nr u l e f o rt h es e c o n ds o l u t i o ni t a d o p t st h em e t h o do fe q u i d e p t h d i s c r e t i z a t i o nt od e a lw i t hq u a n t i t a t i v ea t t r i b u t e f i e l db yt h em a xs u p p o r t f o r o b t a i n i n gf r e q u e n ti t e m s e tv i ai m p r o v i n gt h ec l a s s i c a la p r i o r id i m e n s i o na l g o r i t h m ， t h em 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 eh a sb e e ni m p l e m e n t e d b a s e do nt h i sa d a p t i o n ， t h ec o n c e p to ff u n c t i o n a ld e p e n d e n c i e sh a sb e e ni n l x o d u c e d t h ea l g o r i t h mb yu s i n g t h ei n t e r a c t i o nb e t w e e nf u n c t i o n a ld e p e n d e n c i e sa n da s s o c i a t i o nr u l ew a si m p r o v e d ， a n dt h ea p p l i c a b i l i t yo ft h ee n h a n c e da l g o r i t h mw a sa l s oa n a l y z e d l a s ti nt h i ss t u d y ， as o l u t i o no ft h ec o m b i n a t i o no ft h ef i r s ts o l u t i o na n dt l l es e c o n ds o l u t i o nf o r e n h a n c i n gt h ee f f i c e n c yo f t h ea l g o r i t h mw a sp r o p o s e d 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 nm l e ，a p r i o r ia l g o r i t h m ，i t e m s e t s o r d e r t r a n s a c t i o nr e d u c e d ，f u n c t i o n a ld e p e n d e n c i e s 1 i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得盘生盘茔或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名： 凼莲歌 、j 签字日期： 衫年d z 月 日 学位论文版权使用授权书 本学位论文作者完全了解：苤生盘茎有关保留、使用学位论文的规定。 特授权墨洼盘茎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 自莲丧 导师签名：；景色芳文) 签字日期：西年扩2 月 日签字日期：口r 年。月日 天津大学硕士学位论文第一章绪论 1 1 课题研究背景 第一章绪论 随着数据库容量的膨胀，特别是数据仓库以及w e b 等新型数据源的日益普 及，联机分析处理、决策支持以及分类、聚类等复杂应用成为必然。面对这一挑 战，数据挖掘技术应运而生。数据挖掘( d a t am i n i n g ，d m ) 就是从大量的数据中 挖掘出人们感兴趣的知识，把人们对数据库的应用从低层次的末端查询工作提高 到为各级经营决策者提供决策支持的过程。 经过若于年的研究和实践，数据挖掘技术已经吸收了许多学科的最新研究成 果而形成独具特色的研究分支。象其它新技术的发展历程一样，数据挖掘也必须 经过概念提出、概念接受、广泛研究和探索、逐步应用和大量应用等阶段。从目 前的现状看，大部分学者认为数据挖掘的研究仍然处于广泛研究和探索阶段。一 方面，数据挖掘的概念已经被广泛接受。在理论上，一批具有挑战性和前瞻性的 问题被提出，吸引越来越多的研究者。数据挖掘的概念从二十世纪八十年代被提 出后，其经济价值已经显现出来，而且被众多商业厂家所推崇，形成初步的市场。 另一方面，目前的数据挖掘技术仍存在许多问题需要研究和探索。 1 1 1 数据挖掘概述 1 1 1 1 数据挖掘的产生 随着数据库技术的成熟和数据应用的普及，人类积累的数据量正在以指数速 度增长。进入上个世纪九十年代，伴随着因特网的出现和发展，以及随之而来的 企业内部网和企业外部网以及虚拟私有网的产生和应用，将整个世界联成一个小 小的地球村，人们可以跨越时空地在网上交换数据信息和协同工作。这样，展现 在人们面前的已不是局限于本部门，本单位和本行业的庞大数据库，而是浩瀚无 垠的信息海洋，数据洪水正向人们滚滚涌来。当数据量极度增长时，如果没有有效 的方法，由计算机及信息技术来提取有用信息和知识，人们也会感到面对信息海 洋像大海捞针一样束手无策。据估计，一个大型企业数据库中数据，只有百分之 七得到很好应用。这样，相对于“数据过剩”和“信息爆炸”，人们又感到“信 息贫乏”和“数据关在牢笼中”，奈斯伯特( j o h n n a i s b e t t ) 惊, 呼“人类正被数据淹 没，却饥渴于知识”。 天津大学硕士学位论文 第一章绪论 面临浩渺无际的数据，人们呼唤从数据汪洋中来一个去粗存精、去伪存真的 技术。从数据库中发现知识( 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 9 8 9 年8 月美国 底特律召开的第1 1 届国际人工智能联合会议上，是一门交叉学科，涉及到机器 学习、模式识别、统计学、智能数据库、知识获取、数据可视化、高性能计算、 专家系统等各个领域。 1 1 1 2 数据挖掘的概念 数据挖掘是一类深层次的数据分析方法，被认为是解决“数据爆炸知识贫乏” 的有效方法之一，在最近几年里已被数据库暴广泛研究。数据挖掘的一种较为公 认的定义是g p i a t e t s k ys h a p i r o 等人提出的：数据挖掘是从静态的存储于大型数 据库中的结构化数据中提取人们感兴趣的数据模式、内在联系、规律、发展趋势 等知识，这些知识是隐含的、事先不知的、潜在有用的信息，提取的知识般可 以表示为概念、规则、规律、模式等形式。这个定义包括好几层含义；数据源必 须是真实的、大量的、含噪声的；发现的是用户感兴趣的知识；发现的知识要可 接受、可理解、可运用：并不要求发现放之四海皆准的知识，仅支持特定的发现 问题即可。数据挖掘也称为数据库中的知识发现、数据考古、知识开采等，其最 重要的价值在于人们可以利用数据挖掘技术提出预言模型、验证预言模型、改善 预言模型。 1 1 1 3 数据挖掘系统 从知识发现的角度，可以把数据挖掘视为数据库中知识发现过程的一个基本 步骤。一般知识发现的过程由以下几个步骤组成： 1 ) 数据清理：消除噪声或不一致的数据； 2 ) 数据集成：多种数据源可以组合在一起； 3 ) 数据选择：从数据库中检索与分析任务相关的数据： 4 ) 数据变换：数据变换或统一成适合挖掘的形式，如通过汇总或聚类操作； 5 ) 数据挖掘：基本步骤，使用智能方法提取数据模式： 6 ) 模式评佶：根据某种兴趣度量，识别表示知识的真正有趣的模式： 7 ) 知识表示：使用可视化和知识表现技术，向用户提供挖掘知识； 数据挖掘步骤可以与用户或知识库交互。有趣的模式提供给用户，或作为新 的知识存取放在知识库中。从数据挖掘的广义观点来看，数据挖掘是从存放在数 据库、数据仓库、或其他信息库中的大量数据中挖掘有趣知识的过程。 基于这种观点，典型的数据挖掘系统具有以下主要成分。1 ( 如图1 1 ) ： 天津大学硕士学位论文 第一章绪论 图1 1 典型的数据挖掘系统结构 1 ) 数据库、数据仓库或其他信息库：这是一个或者一组数据库、数据仓库、 电子表格或其他类型的信息库。可以在数据上进行数据清理和集成。 2 ) 数据库或数据仓库服务器：根据用户的数据挖掘请求，数据库或数据仓 库服务器负责提取相关数据。 3 ) 知识库：这是领域知识，用于指导搜索，或评估结果模式的兴趣度。这 天津大学硕士学位论文 第一章绪论 种知识可能包括概念分层，用于将属性或属性值组成不同的抽象层。用 户确信方面的知识也可以包含在内。可以使用这种知识，根据非期望性 评估模式的兴趣度。领域知识的其他例子有兴趣度限制或阈值和元数据 ( 例如，描述来自多个异种数据源的数据) 。 4 ) 数据挖掘引擎：这是数据挖掘系统基本的部分，由一组功能模块组成， 用于特征化、关联、分类、聚类分析以及演变和偏差分析。 5 ) 模式评估模块：通常，此成分使用兴趣度度量，并与数据挖掘模块交互， 以便将搜索聚焦在有趣的模式上。它可能使用兴趣度闽值过滤发现的模 式。模式评估模块也可以与挖掘模块集成在一起，这依赖于所用的数据 挖掘方法的实现。对于有效的数据挖掘，建议尽可能深地将模式评估推 进到挖掘过程之中，以便将搜索限制在有兴趣的模式上。 6 ) 图形用户界面：本模块在用户和数据挖掘系统之间通信，允许用户与系 统交互，制定数据挖掘查询任务，提供信息、帮助搜索聚焦，根据数据 挖掘中的中间结果进行搜索式数据挖掘。此外，此成分还允许用户浏览 数据库和数据仓库模式或数据结构，评估挖掘的模式以不同的形式对模 式可视化。 1 1 1 4 数据挖掘的任务 1 1 关联分析：关联规则挖掘是由r a k e s ha p w a l 等人首先提出的。两个或 两个以上变量的取值之间存在某种规律性，就称为关联。数据关联是数 据库中存在的一类重要的、可被发现的知识。关联分为简单关联、时序 关联和因果关联。关联分析的目的是找出数据库中隐藏的关联网。一般 用支持度和可信度两个阀值来度量关联规则的相关性，还不断引入兴趣 度、相关性等参数，使得所挖掘的规则更符合需求。 2 ) 分类：数据分类作为数据挖掘的一个重要的主题，在统计学、机器学习、 人工神经网络等得到了较早的研究，但是只是在最近几年，人们才将它 与数据库技术结合起来。数据分类实际上是从数据库对象中发现共性， 并将数据对象分成不同类别的过程。分类之前先选择保持整体数据库中 数据元组的所有属性的样本数据库当作训练集，对训练集中的样本进行 分析，提炼数据的特征属性，给出每个类别的属性描述和各个样本的类 属信息，然后利用各个类别的属性信息对数据库中的其它数据进行分 类，或利用总数据库中的数据对象形成各个类别的更好的描述形式。 3 ) 预测：预测是利用历史数据找出变化规律，建立模型，并由此模型对未 来数据的种类及特征进行预测。预测关心的是精度和不确定性，通常用 天津大学硕士学位论文 第一章绪论 预测方差来度量。 4 ) 聚类分析：聚类就是将物理的或者抽象的对象分成几个群体，使得各个 群体内部对象之间的相似度较高，而群体间对象的相似度较低。聚类分 析可以建立宏观的概念，发现数据的分布模式，以及可能的数据属性之 间的相互关系。聚类也是进行分类，其与数据分类不同之处在于，在数 据分类中，提前知道样本的类属信息，而在聚类中，样本的类属信息是 不知道的。 5 ) 时序模式：时序模式是指通过时间序列搜索出的重复发生概率较高的模 式。与回归一样，它也是用己知的数据预测未来的值，但这些数据的区 别是变量所处时间的不同。 6 ) 偏差分析：在偏差中包括很多有用的知识，数据库中的数据存在很多异 常情况，发现数据库中数据存在的异常情况是非常重要的。偏差检验的 基本方法就是寻找观察结果与参照之间的差别。 1 1 2 数据挖掘研究 1 1 2 1 数据挖掘研究的主要内容 数据挖掘是一个以数据库、人工智能、数理统计、可视化四大支柱技术为基 础，多学科交叉、渗透、融合形成的新的交叉学科，其研究内容十分广泛。目前 存在很多数据挖掘方法或算法，因此有必要对这些方法进行分门别类。描述或说 明一个算法涉及三个部分：输入、输出和处理过程。数据挖掘算法的输入是数据 库，算法的输出是要发现的知识或模式，算法的处理过程则涉及具体的搜索方法。 从算法的输入、输出和处理过程三个角度分，可以确定这样几种分类标准：挖掘 对象、挖掘任务、挖掘方法。 根据挖掘对象分，有如下若干种数据库或数据源：关系数据库、面向对象数 据库、空间数据库、时态数据库、文本数据源、多媒体数据库、异质数据库、历 史( 1 e g a c y ) 数据库，以及万维网( w e b ) 。 根据挖掘方法分，可粗分为：统计方法、机器学习方法、神经网络方法和数 据库方法。统计方法可细分为：回归分析、判别分析、聚类分析、探索性分析等。 机器学习可细分为：归纳学习方法、基于范例学习、遗传算法等。神经网络方法 可细分为：前向神经网络、自组织神经网络等。数据库方法主要是多维数据分析 或o l a p 方法，另外还有面向属性的归纳方法。 根据挖掘任务分，数据挖掘主要发现以下五类知识： 1 ) 广义型知识：根据数据的微观特性发现其表征的、带有普遍性的、较高 天津大学硕士学位论文第一章绪论 层次概念的、中观或宏观的知识。 2 ) 分类型知识：反映同类事物共同性质的特征型知识和不同事物之间差异 型特征知识。用于反映数据的汇聚模式或根据对象的属性区分其所属类 别。 3 1 关联型知识：反映一个事件和其它事件之间依赖或关联的知识，又称依 赖关系。这类知识可用于数据库中的归一化，查询优化等。 4 1 预测型知识：通过时间序列型数据，由历史的和当前的数据去预测未来 的情况。它实际上是一种以时间为关键属性的关联知识。 5 1 偏差型知识：通过分析标准类以外的特例，数据聚类外的离群值，实际 观测值和系统预测值间的显著差别，来对差异和极端特例进行描述。 1 1 2 2 数据挖掘的应用 近年来随着数据库和网络技术的广泛使用，加上使用先进的自动数据程成和 采集工具，人们所拥有的数据量急剧增加，使得数据挖掘技术得到广泛的应用， 如科学研究、金融投资、市场营销、保险、医疗卫生、产品制造业、通信网络管 理等行业。 1 ) 科学研究：在信息量极为庞大的天文、气象、生物技术等领域中，由于 所获得的大量实验和观测数据靠传统的数据分析工具已难于对付，因此 对功能强大的智能化自动分析工具要求迫切，这种需求推动了数据挖掘 技术在科学研究领域的应用发展，并且已经获得一些重要的应用成果。 2 ) 金融投资：在银行等金融机构中产生的金融数据通常相对比较完整，可 靠和质量较高，因此，数据挖掘在这一领域中的应用相对比较成熟，也 取得了较好的社会效益和经济效益。由于金融投资风险很大，在进行投 资决策时，需要对各种投资方向的有关数据进行分析，以选择最佳的投 资方向，而数据挖掘是通过对已有的数据进行处理，并利用学习得到的 模式进行市场预测，以选择最佳的投资方向，可使金融投资的风险降低。 通过分析市场波动的因素，建立预测模型，进行投资分析和预测，改进 预测市场波动的能力，为投资决策提供科学的依据。 3 1 保险业：随着社会保障体系的日益健全，保险业取得了蓬勃的发展，发 挥着越来越重要的作用。保险是一项风险业务，保险公司的一个重要工 作就是进行风险评估。通过研究证明，可以利用数据挖掘技术来进行风 险分析，在保险公司建立的保单及索赔信息数据库的基础上，寻找傈单 风险较大的领域，从而得出一些实用的控制风险的规则，以指导保险公 司的工作，数据挖掘技在保险业中的应用，有利于保险公司开展业绩评 天津大学硕士学位论文 第一章绪论 价、业务预算、市场分析、风险评估和风险预测等，大大提高企业防范 和抵抗经营风险的能力和水平，也为管理人员提供科学的决策依据。 4 1 零售业：零售业是数据挖掘应用较为活跃的一个领域。了解客户的购买 习惯和趋向，对于零售商制定销售策略是至关重要的。销售分析人员运 用关联规则挖掘技术对大量的销售数据进行分析，可以发现顾客购买模 式和趋势，改进服务质量，取得更好的顾客保持力和满意程度，提高货 品销售比率，设计更好的货品运输和分销策略，减少商业成本。购物篮 分析是数据挖掘技术应用在零售业中的一种有效的方式，可用于销售搭 配、产品目录设计、产品定价和促销等。 5 ) 制造业：随着现代技术越来越多地应用于制造业，产品生产已不是人们 想象中的手工劳动，而是集成了许多先进技术的流水作业。在产品的生 产制造过程中常常伴随着大量的数据，如产品的各种加工条件或控制参 数，这些数据反映可每个生产环节的状态，不仅为生产的顺利进行提供 了保证，而且通过这些数据的分析，得到产品的质量与参数之间的关系。 这样通过数据挖掘对这些数据的分析，可以对改进的产品质量提出针对 性很强的建议，而且可能提出新的更高效节约的控制模式，从而为制造 厂家带来极大的回报。 6 1 电信业：电信业已经从单纯的提供市话和长话服务演变成提供综合服务 电信业务，如语音、传真、寻呼、移动电话、图像、电子邮件、计算机 和w e b 数据传输，以及其他数据通信服务。而且随着许多国家对电信 业的开放和新兴计算与通信技术的发展，电信市场正在迅速扩张并越发 竞争激烈。因此，利用数据挖掘技术来帮助理解商业行为、确定电信模 式、捕捉盗用行为、更好地利用资源和提高服务质量是非常必要的。 7 1 其他应用领域：医疗数据挖掘可用于病例、病人行为特征的分析，以及 用于药方管理等，以安排治疗方案、判断药方的有效性等；司法数据挖 掘可用于案件调查、案例分析、犯罪监控等，还可用于犯罪行为特征模 式的分析，从而为案件的侦破提供指导，进而为教育和改造犯罪寻求有 效方法；工业部门数据挖掘技术可用于进行故障诊断、生产过程优化等。 制造业应用数据挖掘技术来进行零件故障诊断、资源优化、生产过程分 析等，通过对生产数据进行分析，可发现容易产生质量问题的工序以及 相关的故障因素等：在网络入侵监测领域中的应用。计算机的网络化和 操作系统的日益复杂化给系统带来的安全隐患，以及黑客的活动日益活 跃，这就对网络安全工作提出了挑战。如何从大量审计数据中发现用户 的行为模式，并提取出具有代表性的系统特征模式，从而发现异常的访 天律太学硕士学位论文第一章绪论 问模式，是入侵监测急需解决的关键问题。数据挖掘技术是用于从海量 数据中提取用户有用的数据。将该技术用于入侵检测领域，利用数据挖 掘中的关联分析，序列模式分析等算法提取相关的用户行为特征，并根 据这些特征生成安全事件的分类模型，应用于安全事件的自动鉴别。 1 1 3 数据挖掘的趋势和面临的困难 尽管取得了许多进展，数据挖掘仍面临着许多困难与挑战： 1 ) 源白于数据库本身，现实世界数据库中的数据是动态的且数量庞大，有 时数据是不完全的，存在噪音、不确定性、信息丢失、信息冗余、数据 分布稀疏等问题。 2 ) 数据挖掘技术与特定数据存储类型的适应问题。数据库类型多样性，不 同的数据存储方式会影响数据挖掘的具体实现机制、目标定位、技术有 效一眭等，比如适用于关系数据库的算法未必适用于面向对象数据库。指 望一种通用的应用模式适合所有的数据存储方式下发现有效知识是不 现实的。因此，针对不同数据存储类型的特点，进行针对性研究是目前 流行而且也是将来一段时间所必须面对的问题。 3 ) 知识的表示形式，它包括如何对挖掘到的知识进行有效的表示，使人们 容易理解，比如如何对数据进行可视化，推动人们主动地从中发现知识。 可视化要求已经成为目前信息处理系统的必不可少技术。对于一个数据 挖掘系统来说，它更是重要的。可视化挖掘除了要和良好的交互式技术 结合外，还必须在挖掘结果或知识模式的可视化、挖掘过程的可视化以 及可视化指导用户挖掘等方面进行探索和实践。因此知识表示的深入研 究将是数据挖掘实用化的一个重要步骤。 4 ) 目前的数据挖掘系统还不尽如人意，人们还不能象关系数据库系统那样 调用s q l 语言就能快速查询到自己想要的东西。虽然经过多年的探索， 数据挖掘系统的基本构架和过程已经趋于明朗，但是受到应用领域、挖 掘数据类型以及知识表达模式等的影响，在具体的实现机制、技术路线 以及各阶段或部件( 如数据清洗、知识形成、模式评估等) 的功能定位 等方面仍需细化和深入研究。由于数据挖掘是在大量的源数据集中发现 潜在的、事先并不知道的知识，因此和用户交互式进行探索性挖掘是必 然的。这种交互可能发生在数据挖掘的各个不同阶段，从小同角度或不 同粒度进行交互。所以良好的交互式挖掘( i n t e r a c t i o nm i n i n g ) 也是数 据挖掘系统成功的前提。 5 1 现有的理论和算泫本身还有待发展完善，象定性定量转换、不确定性推 5 1 现有的理论和算泫本身还有待发展完善，象定性定量转换、不确定性推 天津大学硕士学位论文 第一章绪论 理等一些根本性的问题还没有得到很好的解决，同时为了有效地从数据 库的大量数据中提取信息，数据挖掘算法必须是有效的和可伸缩的。换 句话说，对于大型数据库，数据挖掘算法的运行时间必须是可预计的和 可接受的。所以需要发展高效的数据挖掘算法。 另外数据挖掘系统与实际应用相结合得还不够，除了经典的“啤酒”与“尿 布”外，还没有太多数据挖掘成功的范例。因此数据挖掘与其它技术特别是数据 仓库技术的结合将是今后一个重要的发展方向。 1 2 选题动机 数据挖掘理论与算法研究。经过十几年的研究，数据挖掘已经在继承和发展 相关基础学科( 如机器学习、统计学等) 已有成果方面取得了可喜的进步，探索 出了许多独具特色的理论体系。但是，这决不意味着挖掘理论的探索已经结束， 恰恰相反它留给了研究者丰富的理论课题。一方面，在这些大的理论框架下有许 多面向实际应用目标的挖掘理论等待探索和创新。另一方面，随着数据挖掘技术 本身和相关技术的发展，新的挖掘理论的诞生是必然的，而且可能对特定的应用 产生推动作用。新理论的发展必然促进新的挖掘算法的产生，这些算法可能扩展 挖掘的有效性，如针对数据挖掘的某些阶段、某些数据类型、大容量源数据集等 更有效：可能提高挖掘的精度或效率；可能融合特定的应用目标，如c r m 、电 子商务等。因此，对数据挖掘理论和算法的探讨将是长期而艰巨的任务。 1 3 论文的结构安排 本文的结构安排如下： 第一章：介绍了与课题相关的背景知识，包括数据挖掘概念、规则、主要的 研究内容和应用发展等。 第二章：阐述了数据挖掘中关联规则的基本概念、性质、种类以及其价值的 衡量方法等。 第三章：介绍了单维和多维关联规则挖掘算法。详细分析了经典的a p f i o n 算法及其他学者对a p f i o f i 算法的改进算法，总结了算法存在的问题。 第四章：针对于a p r i o r i 算法局限性提出了两种改进方案，旨在提高算法效 率和适用性。第一种改进方案减少了原算法中大量进行的判断操作并缩小了扫描 数据库的大小；在第二种改进方案中介绍了对于多维关联规则量化属性的预处理 方法，并对a p r i o r i 算法进行改进，实现其在多维关联规则中的应用，在此基础 天律大学硕士学位论文 第一章绪论 上引入函数依赖性质，缩小了候选集的大小，提高算法效率。本章结尾还给出了 两种改进方案相结合提高算法效率的思想。 第五章：总结了本文的重要工作并展望了未来的研究方向。 天津大学硕士学位论文 第二章关联规则概述 2 1 引言 第二章关联规则概述 关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。它在数据挖 掘中是一个重要的课题。随着大量数据不停地收集和存储，许多业界人士对于从 他们的数据库中挖掘关联规则越来越感兴趣。 关联规则挖掘的一个典型例子是购物篮分析。该过程通过发现顾客放入其购 物篮中不同商品之间的联系( 比如发现9 0 的顾客在购买面包和黄油的同时也会 购买牛奶) ，分析顾客的购买习惯。关联规则研究有助于发现交易数据库中不同 商品( 项) 之间的联系，找出顾客购买行为模式，如购买了某一商品对购买其他 商品的影响。分析结果可以应用于商品货架布局、货存安排以及根据购买模式对 用户进行分类。 a g r a w a l 等于1 9 9 3 年首先提出了挖掘顾客交易数据库中项集间的关联规则 问题0 3 ，以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。本章将 对关联规则的基本概念、性质、种类、价值衡量方法等进行详细的描述。 2 2 基本概念 设i = i 1 ，i 2 ，i m ) 是i r l 个不同项目的一个集合。设任务相关的数据d 是数 据库事务的集合，其中每个事务t 是项的集合。每一个事务有一个唯一的标识符， 称作t i d 。如果对于i 中的一个子集x ，有x c _ t ，我们就说一个事务包含x 。 关联规则就是一个形如“x j y ”的蕴涵式，其中x i ，y c i ，而且x n y = m 。 如果以上面的例子为例，那么x 中就包含了“面包”、“黄油”两个项目，y 中包含了“牛奶”一个项目。 规则x j y 在事务集d 中成立，具有支持度( s u p p o r t ) s ，其中s 是d 中事 务包含x u y ( 即x 和y 两者) 的百分比，它是概率p ( x i j 。即是 s u p p o r t ( x j y ) = p ( x u y ) 公式( 2 - 1 ) 规则x j y 在事务集d 中具有置信度( c o n f i d e n c e ) c ，如果d 中包含x 的 天津大学硕士学位论文第二章关联规则概述 事务同时也包含y 的百分比是c ，这是条件概率p ( x y ) 。即是 c o n f i d e n c e ( xjy ) = p ( x y ) 公式( 2 - 2 ) 关联规则的挖掘问题就是生成所有满足用户指定的最小支持度( m j _ n s u p ) 和 最小信任度( m i n c o n f ) 的关联规则，即这些关联规则的支持度和信任度分别不 小于最小支持度和最小信任度。 满足最小支持度和最小信任度的关联规则称为强关联规则( s t r o n g a s s o c i a t i o nr u l e s ) 。 项的集合称为项集( i t e m s e t ) 。包含k 个项的项集成为k 项集。项集的出现 频率是包含项集的事务数，简称为项集的频率、支持计数或者计数。项集满足最 小支持度m i n s u p ，就是说项集的出现频率大于或者等于m i n s u p 与d 中事务总数 的乘积。如果项集满足最小支持度，则称它为频繁项集( f r e q u e n ti t e m s e t ) 。频 繁k - 项集记作l k 。 关联规则的挖掘是一个两步的过程： 1 ) 找出所有频繁项集：根据定义这些项集出现的频繁性至少和预定义的最 小支持计数一样。 2 ) 由频繁项集产生强关联规则：根据定义，这些规则必须满足晟下支持度 和最小置信度。 这两步中，第2 步在内存、i 0 以及算法效率上都较第一步更为容易与直观， 在文献 3 给出了算法，因此目前大量的研究工作主要都集中在第1 步上。 2 3 关联规则的性质 性质2 1 ：设u = u t ，u 2 ，u k l 为项集，且u g i ，噼巾，q u ，对于给定的 数据库事务集d 和最小支持度m i n s u p ，如果项集u 为频繁集，则q 也是频繁集。 证明：。项集u 为频繁集，且满足s u p p o r t ( u ) 兰m i n s u p 设数据库中包含项集u 的事务集为d o 又。q u 则数据库中包含项集u 的事务集d o 一定包含项集n ，s u p p o r t ( n ) s u p p o n ( u ) m i n s u p 7 q 必为频繁集 性质2 2 ：设u ； u l ，u 2 ，u k 为项集，且u c h c i ，u 由，对于给定的数据 库事务集d 和最小支持度m i n s u p ，如果项集u 为非频繁集，则h 也一定是非频 天津大学硕士学位论文 第二章关联规则概述 繁集。 证明：使用反证法，假设h 是频繁集 。u h g i ，u m 。由性质1 可知项集u 为频繁集( 与题设矛盾) ? 。h 是非频繁集 性质2 3 ：设关联规则x j y ，满足x i ，y g i ，而且x o ，y 母，x n y 如 对于给定的最小支持度m i n s u p 和最小信任度m i n c o n f ；x j y 为强关联规则；如 果y t c y ，那么x j y 也为强关联规则。 证明：( 1 ) 首先证明s u p p o r t ( ) ( j y ) 最小支持度m i n s u p x j y 为强关联规则 ：s u p p o r t ( x jy ) = p ( x u y ) m i n s u p y s y x u y 量x u y 7 由性质l 知s u p p o r t ( xu y ) s u p p o r t ( xu 兰m i n s u p s u p p o r t ( x j y ) 三m i n s u p ( 2 ) 证明c o n f i d e n c e ( x j y ) 最小信任度m i n c o n f c o n f i d e n c e ( ) 【等y 1 ：s u p p o r t ( x u y ) x 1 0 0 、 s u p p o r t ( x ) ：。由( 1 ) 知s u p p o r t ( xuy ) s u p p o r t ( xv y ) -篙support砌。兰婴s u p 篙p o r t 紫m 蝴 ( x 1( x ) 。c o n f i d e n c e ( ) ( j y ) c o n f i d e n c e j d 。x j y 为强关联规则且c o n f i d e n c e ( ) ( j 三m i n c o n f 。c o n f i d e n c e ( x j y ) 三c o n f i d e n c e j 三m i n c o r t f 综合以上( 1 ) ，( 2 ) 知x j y 也为强关联规则 性质2 4 ：设关联规则x j y ，满足i u y 且x 0 ，y o ，x f 7 y = 由。对于 给定的最小支持度m i n s u p 和最小信任度m i n c o n f 的强关联规则；如果x c x ， 满足i = x u y 咀x o ，y 中，x tny f = o ，那么x _ y 。，也为满足给定条件的强 关联规则。 证明：。x j y 是强关联规则 s u p p o r t ( x = 事y ) 三m i n s u p 且c o n f i d e n c e ( x j _ m i n c o n f 。x c x 且i = x u y 。，x m ，y m ，x f 7y = 西 天津大学硕士学位论文第二章关联规则概述 - s u p p o r t ( x ) 兰s u p p o r t ( x 1 1 。i = x u y = x u y 7 s u p p o r t ( x 。uy ) 2s u p p o r t ( xuy ) !竺等support(x1。兰!鬻supporc(x)1。 、 c o n f i d e n c e ( ) ( j y ) c o n f i d e n c e ( x j 的三m i n c o n f x j y 也为满足给定条件的强关联规则 2 4 关联规贝, l jf 1 9 ,种类 关联规则按不同的情况分类： 1 1 基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。布 尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间 的关系：而数值型关联规则可以和多维关联或多层关联规则结合起来， 对数值型字段进行处理，将其进行动态的分割，或者直接对原始的数据 进行处理，当然数值型关联规则中也可以包含种类变量。例如：性别= “女”j 职业= “秘书”，是布尔型关联规则；性别= “女”j a v g ( 收 入】= 2 3 0 0 ，涉及的收入是数值类型，所以是一个数值型关联规则。 2 ) 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。 在单层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个 不同的层次的；而在多层的关联规则中，对数据的多层性己经进行了充 分的考虑。例如：i b m 台式机js o n y 打印机，是一个细节数据上的单 层关联规则；台式机s o n y 打印机，是一个较高层次和细节层次之间 的多层关联规则。 3 1 基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。 在单维的关联规则中，只涉及到数据的一个维，如用户购买的物品；而 在多维的关联规则中，要处理的数据将会涉及多个维。换句话说，单维 关联规则是处理单个属性中的一些关系：多维关联规则是处理各个属性 之间的某些关系。例如：啤酒j 尿布，这条规则只涉及到用户的购买的 物品；性别= “女”j 职业= “秘书”，这条规则就涉及到两个字段的信 息，是两个维上的一条关联规则。 天津大学硕士学位论文 第二章关联规则概述 2 5 关联规则价值衡量的方法 当采用挖掘算法得出了一些结果之后，可以通过两个层面衡量评价这些规则 的价值，即系统客观的层面和用户主观的层面。 2 5 1 系统客观层面 当前，在系统客观层面，关联规则的评价标准一般有两个：支持度和置信度。 它们分别反映了所发现规则的有用性和确定性。但是采用“支持度一置信度”框 架的挖掘算法经常会产生有误导性的，甚至错误的结果。可以通过下面的一个例 子来说明：考察某超市的顾客购买咖啡和绿茶的情况，假设在该超市的底层事务 数据库中挖掘任务相关的任务为4 0 0 0 条记录，其中购买咖啡的记录有2 2 0 0 条， 购买绿茶的记录有2 7 5 0 条，即购买咖啡又购买绿茶的记录18 0 0 条。如果最小支 持度和最小置信度分别为4 0 和6 0 ，将会发现关联规则： 咖啡j 绿茶( 1 ) 这条规则其实是错误的，因为买绿茶的顾客的比例是