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

江苏大学硕士研究生学位论文 摘要 数据挖掘是指从大量的、不完全地、有噪声的、模糊的、随机的数据中提取 人们感兴趣的知识和规则的过程，数据挖掘的研究已经取得了重大的进展，而且 被应用到众多的领域。关联规则挖掘是数据挖掘研究中一个重要课题，它主要用 于从给定的数据集中发现频繁出现的项集模式知识。 本文首先介绍了数据挖掘的任务和过程以及它的应用情况和发展趋势，关联 规则挖掘的基本概念、分类方法和经典算法，然后重点对如何高效挖掘最大频繁 项集、生成关联规则以及缩减规则的规模进行了研究，对根据得到的币规则挖掘 隐含的负规则进行了探讨，最后设计并实现了江苏财经职业技术学院教学质量评 价分析系统。本文的主要工作和研究成果如下： 1 、对如何高效挖掘最大频繁项集进行了研究，针对现有算法中存在的需要 超集检测和递归的建立条件频繁模式树问题提出基于有序f p 树和n b n 策略挖掘 最大频繁项集的m m f i 算法，对算法的性能和效率进行了分析和实验验证。 2 、针对m m f i 算法中需要反复检索相同项目结点链影响挖掘效率的问题进一 步修改了用于挖掘的数据结构，提出基于含叶子结点链的有序f p 树挖掘最大频 繁项集的i i f i 算法，通过实验对算法的性能和效率进行了验证。 3 、对生成关联规则的方法进行了研究，针对基本生成方法导致的“规则爆 炸”问题分析了现有缩减规则规模方法中存在的问题，提出了最大关联规则m a r 的概念，类似于用挖掘最大频繁项集取代挖掘完全频繁项集，用挖掘最大关联规 则取代挖掘所有的关联规则，提出基于候选规则队列集结构挖掘单个最大频繁项 集的最大关联规则的m m a r i 算法，并用实例对算法的性能进行了验证。 4 、分析了用m m a r i 算法挖掘整个事务数据库的最大关联规则存在的问题， 提出了挖掘整个事务数据库最大关联规则的m i a r d 算法，对算法在不同情况下应 选取的策略进行了论证，并通过实例对算法的性能进行了验证。 5 、对冗余规则问题进行了研究，提出一种在特定情况下根据挖掘出的j r f 关 联规则直接获得隐含的置信度更高的负关联规则的方法。 6 、设计并实现了江苏财经职业技术学院教学评价信息分析系统。 关键词：数据挖掘，关联规则，最大频繁项集，最大关联规则，隐含负规则 江苏大学硕士研究生学位论文 a bs t r a c t d a t am i n i n gw h i c hi st h ep r o c e s so fe x t r a c t i n gt h eu s e f u lk n o w l e d g ea n dr u l e s f r o mt h eh u g ea n di n c o m p l e t ea n dy a w pa n df u z z ya n dr a n d o md a t a sh a sg e tt h e m a j o rp r o g r e s sa n di th a sb e e na p p l i e di nm a n yf i e l d s a s s o c i a t i o nr u l ei so n eo ft h e i m p o r t a n tr e s e a r c h a r e ai nd a t am i n i n g i t s g o a l i st od i s c o v e ri t e m s e tp a r e m k n o w l e d g ew h i c hf r e q u e n ta p p e a r sf r o ml a r g ed a t a b a s e s f i r s t l y , t h i sp a p e rb r i e f l yi n t r o d u c e st h et a s k ，p r o c e s s ，a p p l i c a t i o na n dt h e p r o s p e c t so ft h ed a t am i n i n g ，t h eb a s i cc o n c e p t s ，s o r t sa n dr e s e a r c hh o t s p o t so ft h e a s s o c i a t i o nr u l e s ，t h e nt h i sp a p e rr e s e a r c h sm o s t l yh o wt om i n em a x i m a lf r e q u e n t i t e m s e t se f f i c i e n t l y , g e n e r a t ea s s o c i a t i o nr u l e sa n dr e d u c et h ed i m e n s i o no fr u l e s i t a l s od i s c u s s e sh o wt og e tt h ec o n n o t a t i v en e g a t i v er u l e st h r o u g ht h ep l u sr u l e s ，a n d h o wt od e s i g na n dr e a l i z et h ea n a l y z i n gs y s t e mo ft e a c h i n ge v a l u a t i n gi n f o r m a t i o no f t h ej i a n g s uv o c a t i o n a la n dt e c h n i c a lc o l l e g eo ff i n a n c e & e c o n o m i c s i nt h i sp a p e r ， t h em a i n w o r ka n dr e s e a r c hr e s u l t sa r ea sf o l l o w s 1 r e s e a r c ho nh o wt oe f f i c i e n t l ym i n i n gm a x i m a lf r e q u e n ti t e m s e t sa n d p r o p o s e dt h em m f ia l g o r i t h mf o rm i n i n gm a x i m a lf r e q u e n ti t e m s e t sb a s e do nt h e o r d e r e df p - t r e ea n dn b ns t r a t e g ya i m e da tt h a tt h ep r e s e n ta l g o r i t h m sh a v et od o s u p e r s e tc h e c k i n ga n dc o n s t r u c t i n gc o n d i t i o n a lf r e q u e n tp a t t e r nt r e e sr e c u r s i v e l y t h e a l g o r i t h mp e r f o r m a n c ea n de f f i c i e n c ya r ea n a l y z e da n de x p e r i m e n t a lv e r i f i c a t i o n 2 m o d i f yt h es t r u c t u r ef a r t h e ra n dp r o p o s e dt h ei m m f ia l g o r i t h mf o rm i n i n g m a x i m a lf r e q u e n ti t e m s e t sb a s e do nt h eo r d e r e df p t r e ew h i c hc o n t a i n st h el e a f n o d e sc h a i na i m e da tt h a tt h em m f ia l g o r i t h mh a v et or e t r i e v et h es a m ei t e mn o d e s c h a i nr e p e a t e d l yw h i c hm a k e st h ea l g o r i t h mi n e f f i c i e n t t h ea l g o r i t h mp e r f o r m a n c e a n de f f i c i e n c ya r ea n a l y z e da n de x p e r i m e n t a lv e r i f i c a t i o n 3 r e s e a r c ho nh o wt og e n a r a t et h ea s s o c i a t i o nr u l e sa n da n a l y z e dt h em e t h o d st o r e d u c et h er u l e ss c a l ea i m e da tt h e r u l e se x p l o s i o n i nb a s i cg e n e r a t i o nm e t h o da n d p r o p o s e dt h ec o n c e p tm a r ( m a x i m a la s s o c i a t i o nr u l e s ) w ep r o p o s e dt om i n et h e m a rt or e p l a c em i n i n ga l la s s o c i a t i o nr u l e sj u s ts i m i l a rt or e p l a c em i n i n ga l lf r e q u e n t i t e m s e t sw i t hm i n i n gm a x i m a lf r e q u e n ti t e m s e t so n l y w ea l s op r o p o s e dt h em m a r i a l g o r i t h mf o rm i n i n gt h em a r o faf r e q u e n ti t e m s e tb a s e do nt h es t r u c t u r ec a n d i d a t e r u l e sq u e u e s ，a n dv e r i f i e st h ea l g o r i t h m sp e r f o r m a n c eb yi n s t a n c e 江苏大学硕士研究生学位论文 4 a n a l y z et h eq u e s t i o no fu s i n gt h em m a r ia l g o r i t h mt om i n et h em a r o f w h o l et r a n s a c t i o nd a t a b a s ea n dp r o p o s e dt h em m a r da l g o r i t h mf o rm i n i n gt h e m a ro fw h o l et r a n s a c t i o na n dd e m o n s t r a t e dh o wt os e l e c ts t r a t e g yi nd i f f e r e n tt i m e ， a n dv e r i f i e st h ea l g o r i t h m sp e r f o r m a n c eb yi n s t a n c e 5 r e s e a r c ho nt h er e d u n d a n tr u l e sa n dp r o p o s e dam e t h o dt od i s c o v e rt h e c o n n o t a t i v en e g a t i v ea s s o c i a t i o nr u l e sh a v i n gh i g h e rc o n f i d e n c et h a nt h ed i s c o v e r e d p l u sa s s o c i a t i o nr u l e su n d e rs o m es p e c i f i cc i r c u m s t a n c e s 6 d e s i g na n dr e a l i z et h ea n a l y z i n gs y s t e mo ft e a c h i n ge v a l u a t i n gi n f o r m a t i o no f t h ej i a n g s uv o c m i o n a la n dt e c h n i c a lc o l l e g eo ff i n a n c e & e c o n o m i c s 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 ，m a x i m a lf r e q u e n ti t e m s e t s ，m a x i m a l a s s o c i a t i o nr u l e s ，c o n n o t a t i v en e g a t i v er u l e s 独创i 生声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容以外，本论文 不包含任何其他个人或集体己经发表或撰写过的作品成果。对本文的 研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人 完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 日期：年 月 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权江苏大学可以将本学位论文的全部 内容或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用奉授权书。 本学位论文属于 不保密i - - i 。 学位论文作者签名：导师签名： 签字日期：年月日签字日期：年月日 江苏大学硕士研究生学位论文 第一章绪论 随着以计算机和网络技术为代表的信息技术的发展，越来越多的企业、政府 组织、教育机构和科研单位实现了信息的数字化处理。大型数据库，特别是数据 仓库已被广泛地应用于企业管理、产品销售、科学计算和信息服务等领域，由此 而引起的数据量快速增长，对数据库的存储、管理和分析提出了更高的要求：一 方面，面对庞大的飞速增长的数据量，人们需要新的处理工具，以便能自动化地 把搜集的数据转化为有价值的信息和知识；另一方面，剧增的数据中有可能隐藏 着许多重要的信息，人们希望能够对已经占有的信息进行更高层次的分析，以便 更好地利用这些数据。目前的数据库系统虽然可以较好地实现数据的录入、查询 和统计等功能，但尚不支持对海量数据背后重要信息的挖掘，从而导致了“数据 丰富，知识贫乏” 1 1 的现象。 数据挖掘( d a t am i n i n g ，简称d m ) 技术正是在上述的应用要求下产生的。 它不但可以帮助人们从数据库特别是数据仓库的相关数据中提取出所感兴趣的 知识、规律或更高层次的信息，而且也可以帮助人们从不同程度上去分析它们， 从而可以更有效地利用数据库或数据仓库中的数据。它不仅可以用于描述过去数 据的发展过程，而且还能进一步预测末来的发展趋势。因此，数据挖掘技术成为 一个新的、日益受到重视的热点研究领域。目前在国内外的许多高校和研究机构 都在从事此领域的研究工作，并产生了大量的研究成果。 1 1 数据挖据概述 数据挖掘是人们多年来对数据库技术进行大量研究和开发的成果，在2 0 世 纪8 0 年代末有了很大的发展。数据挖掘足指从数据库或数据仓库的大量数据中 揭示出隐含的、先前未知的、潜在有用的信息的非平凡过程，这个定义是由w j f r a w l e y1 2 j 等人提出的。它作为知识发现过程中一个特定的步骤，是一系列技术 及其应用，或者说是对大容量数据及数据i 、n j 关系进行考察和建模的方法集。它的 目标是将大容量数据转化为有用的知谚 和信息。目前，数据挖掘技术已经在许多 行业都得到应用并取得了一定的实效。 江苏大学硕士研究生学位论文 1 1 1 数据挖掘技术的出现 在1 9 8 9 年第1 1 届国际人工智能联合会议的专题讨论会上，首次提出数据 库中的知识发现( 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 ) 技术，而数据 挖掘可视为数据库中知识发现过程的一个核心步骤，许多学者将其视为数据库中 知识发现的同义词【l 】，本文也不再将k d d 和d m 作严格地区分。从1 9 9 5 年 开始，每年主办一次k d d 国际学术会议，将k d d 和d m 方面的研究推向了 高潮，从此，“数据挖掘”一词开始流行。 数据挖掘技术在数十年的发展中其实是一个逐渐演变的过程。在电子化数据 处理的初期，人们就试图通过某些方法来实现自动决策支持，当时机器学习成为 人们关心的焦点。之后，随着神经网络技术的形成和发展，人们的注意力转向了 知识工程。知识工程不同于机器学习，它不是为计算机输入范例由其生成出规则， 而是直接为计算机输入已被代码化的规则，计算机通过使用这些规则来解决某些 问题，专家系统就是这种方法所得到的成果。2 0 世纪8 0 年代人们又在新的神 经网络理论的指导下，重新回到机器学习的方法上，并将其成果应用于处理大型 商业数据库，从而产生了一个新的术语一数据库中的知识发现。 k d d 泛指所有从源数据中发现模式或联系的方法，常用来描述整个数据挖 掘的过程，包括最开始的制定业务目标到最终的结果分析。近几年，数据挖掘中 有许多工作逐渐开始使用统计方法来完成，并将统计方法与数据挖掘有机的结合 起来。 目前数据挖掘的研究重点也逐渐从发现方法转向系统应用，注重多种发现策 略和技术的集成，以及多种学科之间的相互渗透。i e e e 的k n o w l e d g ea n dd a t a e n g i n e e r i n g 会刊率先出版了k d d 技术专刊。并行计算、计算机网络和信息工 程等其它领域的国际学会、学刊也把数据挖掘和知识发现列为专题和专刊讨论。 与国外相比，国内对数据挖掘和知识发现的研究稍晚，没有形成整体力量。 1 9 9 3 年国家自然科学基金首次支持了对该领域的研究项目。目前，国内的许多 科研单位和高等院校也在竞相开展知识发现的基础理论及其应用研究。 1 1 2 数据挖掘的任务与过程 总体来讲，根据数据挖掘发现的模式类别，可以将其分两种：描述性数据挖 掘和预测性数据挖掘。描述性数据挖掘意在刻画数据的特性和特征。预测性数据 2 江苏大学硕士研究生学位论文 挖掘任务在当前数据上进行推断，以进行预测。另外，数据挖掘能够发现各种位 于不同抽象层的模式。 这些数据模式由不同的视角为用户提供领域的知识，为用户聚焦有趣模式的 搜索带来了方便。具体来讲，数据挖掘任务大略可以归纳为6 种：概念描述、 关联分析、分类和预测、聚类分析、异类分析和演化分析，下面分别简述此6 种 功能。 ( 1 ) 概念描述( c o n c e p td e s c r i p t i o n ) 一个概念常常是对一个包含大量数据的数据集合总体情况的概述。对含有大 量数据的数据集合进行概述性的总结并获得简明、准确的描述，这种描述就称为 概念描述。获得概念描述的方法主要有以下两种： 利用更为广义的属性，对所分析数据进行概要总结，其中被分析的数据 就称为目标数据集。 对两类所分析的数据特点进行对比并对对比结果给出概要性总结，而其 中两类被分析的数据集分别被称为目标数据集和对比数据集。 ( 2 ) 关联分析( a s s o c i a t i o na n a l y s i s ) 关联分析就是从给定的数据集中发现频繁出现的项集模式知识( 又称为关联 规则a s s o c i a t i o nr u l e s ) 1 1 , 3 , 4 1 。关联分析广泛应用于市场营销、事务分析等应 用领域。在大型数据库中，存在很多关联规则，对用户来说其中有些是有用的， 而有些则是无用的，因此需要进行筛选。在实际进行关联规则数据挖掘时，一般 用支持度( s u p p o r t ) 和置信度( c o n f i d e n c e ) 两个阈值来淘汰那些无用的关联 规则。近年来，关联数据挖掘研究方兴未艾，提出了许多高效的关联规则数据挖 掘算法，有关这方面的挖掘方法将在后面有关章节详细介绍。 ( 3 ) 分类和预测( c l a s s i f i c a t i o na n dp r e d i c a t i o n ) 分类就是找出一组能够描述数据集合典型特征的模型( 或函数) ，以便能够 分类识别未知数据的归属或类别，即将未知事例映射到某种离散的类别之一 1 1 , 5 , 6 】。分类模型( 或函数) 可以通过分类挖掘算法从一组训练样本数据( 其类别 归属已知) 中学习获得。分类挖掘所获得的分类模型可以采用多种形式加以描述 输出。其中主要的表示方法有：分类规则、决策树、数学公式和神经网络。 分类通常用于预测未知数据实例的归埔类别( 有限离散值) ，如一个银行客 户的信用等级是属于a 级、b 级还是c 级。但在一些情况下，需要预测某数值 3 江苏大学硕士研究生学位论文 属性的值( 连续数值) ，这样的分类就被称为预测。尽管预测既包括连续数值的 预测，也包括有限离散值的分类，但一般还是使用预测来表示对连续数值的预测， 而使用分类来表示对有限离散值的预测。 ( 4 ) 聚类分析( c l u s t e r i n g a n a l y s i s ) 聚类分析与分类预测方法明显不同之处在于，后者所学习获取分类预测模型 所使用的数据是已知类别归属，属于有教师监督学习方法，而聚类分析( 无论是 在学习还是在归类预测时) 所分析处理的数据均是无类别归属，类别归属标志在 聚类分析处理的数据集中是不存在的【1 。究其原因很简单，它们原来就不存在， 因此聚类分析属于无教师监督学习方法。 聚类分析中，首先需要根据“各聚集内部数据对象间的相似度最大化和各聚 集对象间相似度最小化 的基本聚类分析原则，以及度量数据对象之间相似度的 计算公式，将聚类分析的数据对象划分为若干组。因此一个组中数据对象间的相 似度要比不同组数据对象问的相似度要大。每个聚类分析所获得的组就可视为是 一个同类别归属的数据对象集合，更进一步从这些同类别数据集中，又可以通过 分类学习获得相应的分类预测模型( 规则) 。此外通过反复不断地对所获得的聚 类组进行聚类分析，还可以获得初始数据集合的层次模型。 ( 5 ) 异类分析( o u t li e r a n a l y s i s ) 一个数据库中的数据一般不可能都符合分类预测或聚类分析所获得的模型。 那些不符合由大多数数据对象所构成的规律的数据对象就被成为异类。以前许多 数据挖掘方法都在正式进行数据挖掘之前就将这些异类作为噪声或意外而排除 在数据挖掘的分析处理范围之外。但在一些应用场合，如各种商业欺诈行为的自 动检测，小概率发生的事件往往比经常发生的事件更有价值。对异类数据的分析 处理通常就称为异类挖掘1 1 , 8 1 。 数据中异类可以利用数理统计方法分析获得，即利用己知数据所获得的概率 统计分布模型，或利用相似度计算所获得的相似数据对象分布，分析确认异类数 据。而偏离检测就是从数据已有或期望值中找出某些关键测度显著的变化。 ( 6 ) 演化分析( e v o l u t i o n a n a l y s i s ) 数据演化分析就是对随时间变化的数据对象的变化规律和趋势进行建模描 述1 1 1 。这一建模手段包括：概念描述、对比概念描述、关联分析、分类分析、时 问相关数据分析等。 4 江苏大学硕士研究生学位论文 在数据挖掘的上述6 种功能中，当前研究较多也较为成熟的是关联分析， 它是由r a k e s ha g r a w a l 等人在文献【3 j 中首先引入的。关联分析是指从给定的数 据集中发现关联规则，这些规则反映了大量数据中项目集之间有趣的关联或相关 联系。 数据挖掘过程一般由确定挖掘对象、数据准备、模型建立、数据挖掘、结构 分析表述和挖掘应用这几个主要的阶段组成，数据挖掘可以描述为这几个阶段的 反复过程。数据挖掘可以描述为这几个阶段的反复过程。 1 1 3 数据挖掘的应用与发展趋势 数据挖掘技术旨在发现大量数据中所隐藏的知识，以用来解决“数据丰富、 知识贫乏”的问题。近年来随着数据库和网络技术的广泛应用，加上使用先进的 自动数据生成和采集工具，人们所拥有的数据量急剧增加，使数据挖掘技术在科 学研究、金融投资、市场营销、保险、医疗卫生、产品制造业、通信网络管理等 行业已得到应用。 数据挖掘任务和数据挖掘方法的多样性，给数据挖掘提出了许多挑战性的课 题。数据挖掘语言的设计、高效而有效的数据挖掘方法和系统的开发、交互和集 成的数据挖掘环境的建立和应用数据挖掘技术解决大型应用问题，都是目前数据 挖掘研究人员、系统和应用开发人员所面临的主要问题。下面是数据挖掘的发展 趋势： ( 1 ) 应用的探索 数据挖掘最早应用于零售业和金融业的数据分析。它是一种功能强大的应用 技术，主要为企业和管理人员进行销售和决策提供依据。目前在保险业、制造业、 电信和医学等领域也得到了广泛的应用，并取得了显著的效果。信息产业的发展 为数据挖掘提供了广阔的空间，数据挖掘技术的应用范围将不断得到拓宽，特别 是在生物工程、商业智能、网络服务等领域的应用将成为新的研究热点【9 1 。 ( 2 ) 可伸缩的数据挖掘方法 数据挖掘必须尽可能交互式地、有效地处理大量数据。由于数据量在不断地 激增，因此针对单独和集成的数据挖掘功能的可伸缩算法显得十分重要。一个重 要的方向是所谓基于约束的挖掘( c o n s t r a i n t b a s e dm i n i n g ) 1 1 0 , 1 1 】。它致力于在增 加用户交互的同时，如何改进挖掘处理的总体效率。它提供了额外的控制方法， s 江苏大学硕士研究生学位论文 允许用户说明和使用约束，引导数据挖掘系统对感兴趣模式的搜索。 ( 3 ) 数据挖掘与数据库系统、数据仓库系统和w e b 数据库系统的集成 数据库系统、数据仓库系统和w w w 己经成为信息处理系统的主流，而数 据挖掘系统的理想体系结构是与数据库和数据仓库的紧耦合方式。事务管理、查 询处理、联机分析处理和联机分析挖掘应集成在一个统一框架中。这将保证数据 的可获得性，数据挖掘的可移植性、可伸缩性、高性能以及对多维数据分析和探 查的集成信息处理【1 2 1 。 ( 4 ) 数据挖掘语言的研究 在进行数据挖掘时，让挖掘系统自动挖掘整个大型数据库或数据仓库中隐藏 的所有有价值的知识往往是不切实际的，总是需要在用户的指导下进行有目的的 挖掘。这就需要为用户提供一组与数据挖掘系统通信的语言，可以把这组语言称 为数据挖掘语言。这组语言用于说明用户感兴趣的数据集、要挖掘的知识类型、 用于指导挖掘过程的背景知识、模式评估兴趣度量以及如何显示所发现的知识等 等。这组语言使得用户可以在数据挖掘的过程中与数据挖掘系统进行交互，从不 同的角度和深度检查发现结果。研究专门用于知识发现的数据挖掘语言，也许会 像s q l 语言一样走向形式化和标准化【1 3 , 1 4 , 1 5 1 。 ( 5 ) 可视化数据挖掘 可视化数据挖掘是从大量数据中发现知识的有效途径，系统研究和开发可视 化数据挖掘技术将有助于推进数据挖掘作为数据分析的基本工具。目i j 数据挖掘 的可视化仅体现在结果的简单描述，并没有达到真正意义上的可视化。数据可视 化、挖掘过程可视化和结果可视化，将揭开数据挖掘复杂和神秘的面纱，使其变 得更为生动、形象和具体，用户可以随时了解整个过程的进展情况，减少了行为 过程的卣目性。数据和结果的图形展示可以放大、缩小、平移、旋转和变换角度， 使分析人员和用户更加容易理解，这将大大推动数据挖掘工具在发现知识和数据 分析中的应用。因此，加强数据可视化和知识发现过程的可视化具有重要的理论 意义和应用价值1 1 6 , 1 7 j 。 ( 6 ) 复杂数据类型挖掘的新方法 复杂数据类型挖掘足数据挖掘中一项重要的前沿研究课题。虽然在地理空间 挖掘、多媒体挖掘、时序挖掘、序列挖掘以及文本挖掘方面取得一些进展，但它 们与实际应用的需要仍存在很大的距离。对此需要进一步的研究，尤其是把针对 6 江苏大学硕士研究生学位论文 上述数据类型的现存数据分析技术与数据挖掘方法集成起来的研究 i s j 9 】。 ( 7 ) w e b 挖掘 由于w e b 上存在大量信息，并且w e b 在当今社会扮演越来越重要的角色， 有关w e b 内容挖掘、w e b 日志挖掘和因特网上的数据挖掘服务，将成为数据挖 掘中一个最为重要和繁荣的子领域【2 0 2 1 1 。 ( 8 ) 数据挖掘中的隐私保护与信息安全 随着数据挖掘工具和电信与计算机网络的日益普及，数据挖掘要面对的一个 重要问题是隐私保护和信息安全。需要进一步开发有关方法，以便在适当的信息 访问和数据挖掘过程中确保隐私保护与信息安全【2 2 1 。 1 - 2 关联规则概述 关联规则数据挖掘( 简称关联规则挖掘) 就是从大量的数据中挖掘出有价值 的描述数据项之间相互联系的有关知识。随着收集和存储在数据库中的数据规模 越来越大，人们对从这些数据中挖掘相应的关联知识越来越有兴趣。挖掘关联知 识的一个典型应用实例就是市场购物分析。根据被放到一个购物篮中的内容记录 数据而发现的不同商品之间存在的关联知识，无疑将会帮助商家分析客户的购买 习惯。发现常在一起购买的商品( 关联知识) 将帮助商家制定有针对性的市场营 销策略。自1 9 9 3 年a g r a w a l l 4 j 等人首先提出关联规则概念以来，关联规则挖掘便 迅速受到数据挖掘领域专家的广泛关注，得到了较为深入的发展。 1 2 1 基本概念 设i = i l ，赴，m 为m 个不同文字的集合，其中的文字称为项( i t e m ) ，或者商 品。我们称任何x ，为一个项集( 如果i x l = k ，则称x 为露项集) 。记d = 死，死，瓦 ， 其中正称为一个交易或事务( t r a n s a c t i o n ) ，称d 为，上的交易集或者数据集 ( d a t a s e t ) ，简称交易集或者数据集。 基于上述基本假设，我们给出关联规则的定义1 3 , 4 , 2 3 】： 定义1 1 关联规贝l j ( a s s o c i a t i o nr u l e s ) 给定，关联规则就是形如x jy 的一个表达式，其中，x c _ ly c i ，m 净o 。 7 江苏大学硕士研究生学位论文 衡量关联规则是否有意义的标准有两个，一个是支持度( s u p p o r t ) ，另一个是 置信度( c o n f i d e n c e ) 。它们的定义都是以数据集投影的定义为基础的。 定义1 2 数据集d 在项集上的投影 给定，和，上的数据集d ，对项集x c _ i ，记d x = t i t e d a x c _ 乃，我们称 d x 为数据集d 在项集x 上的投影。d x 即为d 中包含项集x 的所有事务的集合。 支持度和置信度定义如下： 定义1 3 关联规则的支持度( s u p p o r t ) 给定数据集d 和关联规则x jy ，令： s u p 舭引) = 剖( 0 s u p r ) ( 柏y ) y ) 一m i n _ c o n f 时，称关联规则x jy 为数据集 d 上的强关联规则，简称强关联规则。其中，m i ns u p 称为最小支持度，m i nc o n f 称为最小置信度。 8 江苏大学硕士研究生学位论文 需要说明的是，这里的最小支持度和最小置信度都是由用户自定义的阀值。 对于给定的m i n _ s u p 和m i n c o n f , 挖掘数据集d 上的强关联规则可分解为 两个子问题【3 ，4 】： ( 1 ) 生成数据集d 上的支持度不小于m i ns u p 的频繁项集。 ( 2 ) 对于第l 步生成的频繁项集，生成数据集d 上置信度不小于m i nc o n f 的强关联规则。 一旦知道频繁项集里面所有频繁子项集的支持度，得到想要的强关联规则就 很直接了：对每一个频繁项集x 进行划分，通过计算置信度检查所有的规则， 去掉那些没有达到最低置信度的规则。因此，第一步的频繁项集挖掘是强关联规 则挖掘里面计算量较大的一部分。许多研究人员把对强关联规则的挖掘问题集中 在对频繁项集的挖掘上，并为此进行了大量的研究工作。频繁项集根据性质可以 分为完全频繁项集、频繁闭项集和最大频繁项集，下面先给出完全频繁项集的定 义和性质。 定义1 6 完全频繁项集( f r e q u e n tl t e m s e t ) 给定。和项集兄并给定m i n _ s u p ( 。，1 ) ， s u p o ( x ) = 爿为项集x 在数 据集d 上的支持度( 简记为s u p ( x ) ) ，当s u p ( x ) 一 m i n _ s u p 时，项集x 称为d 上的 完全频繁项集，有时简称频繁项集。d 上所有频繁项集的集合汜为：= 珥y c _ i as u p ( x ) 一m i n _ s u p ) 。 简单的说，频繁项集就是在d 上的支持度大于等于最小支持度的项集。此 外，我们称在数据集d 上不是频繁项集的项集为d 上的非频繁项集。定义2 6 里的最小支持度也就是强关联规则定义里面的最小支持度，是由用户自定义的阀 值。 性质1 1 数据集d 上的频繁项集的子集也是d 上的频繁项集 对于给定的数据集d 和最小支持度m i n _ s u p ，对于项集x 和y ，如果有s u p ( x ) 一 m i n _ s u p 且y c x , 则有s u p ( n 一m i n _ s u p 。 证明：因为y c _ x 所以d 中包含x 的事务一定包含l ，故i d y i i d x l ，因此： 9 江苏大学硕士研究生学位论文 s u p ( 胪爿饼一艄) m ；n 一唧 证毕。 性质1 1 是频繁项集的一个基本性质，许多挖掘算法都利用性质2 1 来进行 剪枝。由性质1 1 易得： 性质1 2 数据集d 上的非频繁项集的超集也是d 上的非频繁项集 性质1 2 显然成立，证明略。 1 2 2 关联规则的分类 关联规则挖掘源于超级市场的购物篮问趔3 1 ，是指发现数据库中各项间有价 值的关联关系，然而它只是关联规则挖掘的一种最简单的形式。随着关联规则挖 掘研究的发展，出现了很多全新形式的关联规则。关联规则挖掘研究根据处理的 数据集的性质和挖掘结果的不同有不同的分类方式【l ，8 】： 1 根据规则里所处理的值的类型，关联规则可以分为布尔型关联规则和数 值型关联规i 贝1 8 , 1 6 - 1 9 1 。 布尔型关联规则处理的变量的取值都是离散的、种类化的，它显示了这些变 量之间存在的相互依存的关系；例如关联规则：啤酒= 尿布就是一个典型的布 尔型关联规则。啤酒和尿布只是超市中商品的一个分类名称，而实际应用数据集 中存储的数据不全是命尔型的变量，绝大多数数据是连续型的数值( 如工资、考 试分数、体重等) 。数值型关联规则处理的变量的取值是连续的，数值化的。例 如一条关联规则：年龄 3 0 j 平均收入= 2 3 0 0 ，涉及的收入是数值类型，所以是 一个数值型关联规则。对于数值型关联规则挖掘最主要考虑的问题是如何把连续 的数值属性在值域上进行划分，将每一个划分的区f b j 映射到布尔属性的取值。对 于一个数值属性来讲，如果在值域上划分的区问过多的话，每一个区问的支持度 就会很小，导致包含该属性的关联规则由于不能满足支持度要求而不能被发现。 而区l i 戈1 分过大时，一些有价值的规则又由于不能满足置信度的要求而无法发 现。 2 根据规则中数据所涉及的抽缘层次，关联规则可以分为单层关联规则和 多层关联规i ! 1 1 1 2 8 , 2 9 1 在单层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同 l o 江苏大学硕士研究生学位论文 的层次的，而在多层的关联规则中，对数据的多层性己经进行了充分的考虑。例 如：i b m 台式机js o n y 打印机，是一个细节数据上的单层关联规则；台式机 s o n y 打印机，是一个较高层次和细节层次之间的多层关联规则。 3 根据规则中涉及到的数据的维数，关联规则可以分为单维关联规则和多 维关联规贝1 3 0 , 3 1 】 在单维关联规则挖掘中，我们只涉及到数据的一个维，如用户购买的物品， 而在多维关联规则中，要处理的数据将会涉及多个维。换成另一句话，单维关联 规则是处理单个属性间的一些关系，而多维关联规则挖掘是处理数据中多个属性 之间的某些关系。例如：性别= 女职业= 秘书，这条规则就涉及到两个字段 ( 性别和职业) 的信息，是一条二维关联规则。 自从关联规则概念提出后，近1 0 年的发展，使得关联规则的应用领域从最 初的购物篮分析发展到了对各类频繁项集的挖掘和分析。其前沿的研究焦点主要 集中在以下几个方面： ( 1 ) 关联规则算法效率的研究 从最初的宽度优先挖掘算法到后来的深度优先挖掘算法，从最初只挖掘频繁 项集到挖掘频繁闭项集再到挖掘最大频繁项集，关联规则挖掘算法的运行效率逐 步提高。然而迅速增长的海量数据对算法的效率提出了更高的要求。 ( 2 ) 关联规则衡量标准的研究 通过设定各类主观或客观的衡量标准，进一步对关联规则进行精练，以获取 更有意义、对用户更实用的规则。人们不但提出了一些新的衡量标准1 3 2 , 3 3 , 3 4 1 来完 善支持度一置信度的评价体系，也希望实现对这两个度量值的综合评笋l j l 3 5 , 3 6 。 ( 3 ) 基于规则约束的关联规则挖掘研究 规则约束是指对关联规则形式的约束，主要研究如何使用一些附加的约束来 缩小挖掘过程中所面对的搜索空间。h a n 在这方面把规则约束分为五类1 3 2 , 3 7 】：反 单调约束、单调约束、简洁胜约束、可转变约束和不可转变约束。人们不但在将 前四类约束用于实际挖掘算法方面取得了一定进展，还在努力寻找不可转变约束 中是否存在有可以充分利用起来的约束。 ( 4 ) 关联规则在其它领域的应用 例如在生物信息学、医药学、大规模科学数据分析、文本关联分析，分布式 环境f 与w e b 挖掘等领域，关联规则技术也在充分发挥其作用。但总的来看， 1 l 江苏大学硕士研究生学位论文 不管关联规则运用于哪些新领域，所面临的计算效率问题始终是困扰人们的一个 主要问题。 1 2 3 关联规则挖掘经典算法 用于关联规则挖掘的算法很多，其中最著名最有影响的是由a g r a w a l 等人提 出的a p r i o r i 算法。该算法是挖掘产生布尔关联规则频繁项目集的经典算法，从 其产生到现在对关联规则挖掘方面的研究有着很大的影响。该算法利用一个逐层 搜索的迭代方法来完成频繁项目集的挖掘，这一迭代方法就是利用k 项集来产 生( k + 1 ) 项集。具体的做法如下：首先找出频繁l 一项集，记为l l ；然后利用l l 来挖掘l 2 ，即频繁2 项集；如此不断地循环下去直至不能找到频繁k 项集为止， 其中在发现每个l k 的过程中需要对整个事务数据库扫描一遍。为了提高频繁项 目集逐层产生的效率，a p r i o r i 算法利用了1 1 和1 2 这两个重要的性质，用于压 缩搜索的空间。 在许多情况下，a p r i o r i 算法的侯选产生检查方法大幅度地压缩了侯选项集 的大小，并且导致很好的性能。但该算法中存在的两个问题，一是该算法在计算 的过程中需要产生大量的候选项目集，二是该算法需要对数据库进行多次扫描， 并通过模式匹配检查候选项目集。如果数据库的容量很大或要进行匹配的模式很 长时，算法的效率会大大降低。 为了减小a p r i o r i 算法中存在的问题所带来的影响，提高a p r i o r i 算法的执 行性能，许多学者以其为基础进行了大量的研究，提出了一些改进的算法。 ( 1 ) 基于h a s h 表的技术 利用h a s h 表技术可以帮助有效地减少候选k 项集c k ( k 1 ) 所占用的空问。 例如：在扫描事务数据库以便从候选1 一项集c 1 中产生频繁1 项集l 1 时，就 可以为每个事务产生所有的2 项集并将它们哈希到h a s h 表的不同栏目中，且增 加相应栏目的计数。在文献 3 8 】中p a r k 等人提出了一种基于h a s h 的高效地产 生频繁项目集的算法d h p ，该算法中采用h a s h 技术改进了a p r i o r i 算法中产生 频繁2 一项集的方法，使其产生候选项目集的效率更高。 ( 2 ) 减少交易个数的方法 减少用于未来扫描的事务集的大小。一个基本的原理就是若某个事务不包含 长度为k