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

摘要 摘要 数据挖掘技术是数据库和人工智能领域研究的热点课题，用于发现潜藏在 大量数据中的有用知识。随着数据库规模的不断增长，数据挖掘方法面对的数 据对象越来越大且在不断变化中，使用传统的数据挖掘方法很难处理。而数据 挖掘过程本身是一个反复交互式过程，数据变化或挖掘参数改变前后的挖掘结 果存在重复性，因此通过继承以往挖掘结果可以加快挖掘进程。本文主要研究 数据挖掘中关联规则知识的继承性挖掘。 关联规则挖掘是数据挖掘研究中的一个重要的研究内容，用于发现大量数 据中项集之间有趣的关联或相关联系。目前，在数据挖掘研究中，对关联规则 挖掘的研究开展得比较深入。本文详细介绍了关联规则的基本概念和基本理论， 并针对关联规则挖掘的特征分析其继承性挖掘的特点。通过研究发现直接继承 数据挖掘的结果存在一定困难，因此文中提出了基于中问挖掘结果的继承性挖 掘方法。通过继承中间结果可以直接得到改变后的最终挖掘结果，无需要访问 原始数据。 关联规则的继承包括挖掘参数变化和数据改变两种情况下的继承，文中对 两种继承分别展开研究。对参数改变问题，文中主要针对最小支持度阂值参数 改变，提出了基于中间挖掘结果b p 树的挖掘方法b pi u a 。通过只挖掘支持度 阈值在【n ，b 】范围内的频繁模式，b p 方法大大缩小了继承挖掘时频繁模式_iua 搜索空间，提高了挖掘效率。 对数据改变问题，本文研究新数据加入时的继承性挖掘，以往研究也称之 为数据增量式关联规则挖掘。本文结合两种中问挖掘结果s f p 树和i t e m b i t m a p ，提出新的数据库投影挖掘算法b i t m a pp r o j e c t i o n 。利用两种结构的可归 并性，脱离原始数据库，对更新后的数据进行挖掘。 最后，本文实现了一个关联规则继承性挖掘试验系统，该系统中包括基于 f pg r o w t h 算法的非继承性挖掘模块，基于b pi u a 算法的参数改变时继承性挖 掘模块和基于b i t m a pp r o j e c t i o n 算法的数据增量时继承性挖掘模块。实验表明 本文提出的两种算法在处理继承问题时是高效可行的。 关键词：关联规则继承性数据挖掘参数变化数据增量中间结果 a b s t r a c t d a t am i n i n gi sa ne m e r g i n gr e s e a r c ht o p i ci nd a t a b a s ea n da r t i f i c i a li n t e l l i g e n c e f i e l d st of i n dt h eu s e f u lk n o w l e d g eh i d d e ni nt h ev a s td a t a w i t ht h ei n c r e a s i n go f d a t a b a s es c a l e ，d a t a s e tt h a tw a si nt h ef a c eo fd a t am i n i n gm e t h o dw a sa u g m e n t i n g r a p i d l y , w h i c hi sh a r dt oh a n d l ef o rt h et r a d i t i o n a ld a t am i n i n gm e t h o d t h ep r o c e s so f d a t am i n i n gi si t e r a t i v ea n dm u t u a l ，m i n i n gr e s u l t sb e t w e e nd a t ac h a n g i n ga n d p a r a m e t e rc h a n g i n gh a v er e p e t i t i v e n e s s ，s oi n h e r i t i n gt h ep a s tr e s u l tw i l la c c e l e c r a t e m i n i n gp r o c e s s i nt h i st h e s i s ，w em a i n l yr e s e a r c hi n h e r i t a b l em i n i n go fa s s o c i a t i o n r u l e sw h i c hb e l o n g st od a t am i n i n g a s s o c i a t i o nr u l e si so n eo ft h em o s ti m p o r t a n tr e s e a r c h i n ga r e a si nd a t am i n i n g f i e l d ，w h i c hi st of i n ds o m ei n t e r e s t i n gr e l a t i o nb e t w e e nd a t ai t e m s e t s i nt h i st h e s i s ， w ei n t r o d u c e dt h ee s s e n t i a lc o n c e p ta n dt h e o r yo fa s s o c i a t i o nr u l e s ，a n da n a l y z e dt h e i t sc h a r a c t e r i s t i co fi n h e r i t a b l em i n i n ga c c o r d i n gt oi t sf e a t u r e b yr e s e a r c h i n g ，w e f o u n di ti sd i f f i c u l tt oi n h e r i tt h em i n i n gr e s u l td i r e c t l y , s ow ep r o p o s et h ei n h e r i t a b l e m i n i n gm e t h o db a s e do nt h em i d d l er e s u l t b yt h i sw a y , w ec a ng e tt h ef i n a lm i n i g r e s u l tf r o mm i d d l er e s u l tw i t h o u ta c c e s s i n go r i g i n a ld a t a i n h e r i t a b l em i n i n go fa s s o c i a t i o nr u l ec o n s i s to ft w ok i n d so fi n h e r i t i n gi nt h e c o n d i t i o no fp a r a m e t e rc h a n g i n ga n dd a t ac h a n g i n g ，w h i c hi sd i s c u s s e di nt h i st h e s i s r e s p e c t i v e l y a st h ep a r a m e t e rc h a n g i n gp r o b l e m ，m a i n l yt op r o b l e mo fm i n i m a l s u p p o r tt h r e s h o l dc h a n g i n g ，w ep r e s e n t e dt h eb p _ i u am e t h o db a s e do nt h em i d d l e r e s u l tb pt r e e w h e ni n h e r i t a b l em i n g i n gb p _ i u am e t h o do n l ym i n e dt h ef r e q u e n t p a r t e r ui nt h eb o u n do ffa ，b 】，r e d u c et h es e a r c h i n gs p a c el a r g e l y a st h ed a t ac h a n g i n gp r o b l e m ，w em a i n l yr e s e a r c ht h ep r o b l e mo fi n h e r i t a b l e m i n i n gw h e nn e wd a t a w a sa d d e dt ot h eo r i g i n a ld a t a b a s e ，w h i c hi sc a l l e d i n c r e m e n t a lm i n i n go fa s s o c i a t i o nr u l e s t h i st h e s i sc o m b i n e dt w ok i n d so fm i d d l e r e s u l ts f p _ t r e ea n di t e m _ b i t m a p ，p r e s e n t e dan e wd a t a b a s ep r o j e c t i o nm e t h o ds o c a l l e db i t m a p _ p r o j e c t i o n u s i n gt h em e r g a b l ef e a t u r eo ft h e s et w om i d d l er e s u l t s ，w e c a nu p d a t ef i n a lr e s u l tw i t h o u to r g i n a ld a t a b a s e a b s j i r a c t f i n a l l y , w ei m p l e m e n t a l l e x p e r i m e n t a ls y s t e m f o ri n h e r i t a b l e m i n i n g o f a s s o c i a t i o nr o l e s ，w h i c hi n c l u d i n gm o d u l e so ff p _ g r o w t h m i n i n g , i n h e r i t a b l em i n i n g b a s e do nb p _ i u aw h e np a r a m e t e rc h a n g i n g ，a n di n h e r i t a b l em i n i n gb a s e do n b i t m a p _ p r o j e c t i o nw h e nd a t ai n c r e a s i n g t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h e s e t w oa l g o r i t h m sa r ev a l i da n de f f i c i e n t k e y w o r d s ：a s s o c i a t i o nr u l e s ，i n h e r i t a b l ed a t am i n i n g ，p a r a m e t e rc h a n g e ，i n c r e m e n t a l m i n i n g , m i d d l er e s u l t 第一章绪论 1 1 引言 第一章绪论 数据挖掘( d a t a m i n i n g ) 就是从大量的数据中，抽取出潜在的、有价值的信息， 对发展趋势进行预测。随着数据库规模的不断增长，数据挖掘要处理的数据对 象越来越大。以超市交易数据为例，一个月的交易数据库通常达到g 比特数量 级。面对这种不断变化中的海量数据，传统的数据挖掘方法很难处理，挖掘算 法的时空开销很大；另一方面，数据挖掘过程本身又是一个反复的交互式过程， 用户的本次要求与前次要求往往有较大的重复性，这种重复性主要反映在三方 面： r 1 1 数据集的渐增性 ( 2 ) 算法参数改变前后挖掘结果的相似性 ( 3 ) 不同数据挖掘知识类型之间存在相似性 利用数据挖掘过程相似性，可以在新的挖掘时继承原有的挖掘结果，一定 程度上解决传统数据挖掘不能处理的问题。因此在新的挖掘时能否继承原有的 挖掘结果就成为重要的问题，这类问题称为数据挖掘的可继承性问题，该问题 由作者所在的南开大学智能信息处理实验室首先提出，并在诸多方面开展了研 究。本文针对数据挖掘中最重要的领域之一关联规则知识，从参数变化和数据 变化两方面进行可继承性研究。 1 2 数据挖掘概述 1 2 1 数据挖掘技术的现实背景 随着计算机技术、网络技术和信息技术的发展，人们生产和搜集数据的能 力大幅度提高。在商业管理、政府办公、科学研究和工程开发等各个领域，每 1 第一章绪论 天产生大量数据。2 0 世纪7 0 年代以来，数据库系统的研究和开发己经从层次 和网状数据库系统发展到开发关系数据库系统、数据建模工具、索引和数据组 织技术。自8 0 年代中期以来，数据库技术的特点是广泛接受关系技术，研究和 开发新的、功能强大的数据库系统。异种数据库和基于i n t e m e t 的全球信息系统， 成为信息产业的生力军。尽管数据库技术日趋成熟，可以比较方便查询到数据， 但是面对大型数据库中的海量数据，人们却很难从中找到需要的知识，大量的 数据形成了一座座“信息坟墓，i 引。人们迫切需要解决快速增长的数据量与日益 频繁的信息量之间的矛盾。这就需要更加强有力的分析工具，来理解这些海量 的、类型各异的数据，摆脱大量数据的困扰，并从中及时、高效地发现有用的 信息，以帮助人们发现隐藏的规律，支持决策的制定。 数据挖掘技术正是在这种背景下应运而生的。数据挖掘方法的提出，让人 们最终有能力认识到数据的真正价值，即蕴藏在数据中的信息和知识。 1 2 2 数据挖掘概念和应用 数据挖掘( d a t am i n i n g ) 指的是从大型数据库或数据仓库中提取人们感兴 趣的知识，这些知识是隐含的、事先未知的、潜在的有用信息【2 1 】【竭。这个定义 包括以下含义：数据源必须是真实的、大量的、含噪声的；发现的是用户感兴 趣的知识；发现的知识要可接受、可理解、可运用，最好能用自然语言表达发 现结果；并不是要求发现放之四海皆准的知识，也不是要去发现崭新的自然科 学定理和纯数学公式，更不是什么机器定理证明，所有发现的知识都是相对的， 是有特定前提和约束条件、面向特定领域的。 数据挖掘即知识发现( k d d ) 的主要过程如图卜1 所示，主要由四个部分组成： 1 ) 数据清理( 消除噪音或不一致数据) 和集成( 多种数据源可以组合在一起) 2 ) 数据选择( 从数据库中提取与分析任务相关的数据) 和变换( 数据变换或 统一成适合挖掘的形式) 3 ) 数据挖掘( 基本步骤，使用智能方法提取数据模式) 4 ) 模式评估( 根据某种兴趣度度量，识别提供知识的真正有趣的模式) 和知 识表示( 使用可视化和知识表示技术，向用户提供挖掘的知识) 目前，在国外，数据挖掘技术及其相关的决策支持系统发展得很快，它们 在商业界，公共服务行业等众多行业被广泛应用，并快速、直接的带来了吃惊 2 第一章绪论 的利润，同时也带动了这些行业的飞速发展。因此，有人称这项技术为二十世 纪影响人类的计算机方面的三大事件之一。 r 一一一一一1 一一一一一一一一i 一一一一一一一i 一一一一 十 数据挖掘 h l _ t _ ，r 1 2 3 数据挖掘技术的分类 图1 - 1 知识发现过程模型 从不同的视角看，数据挖掘技术有几种分类方法【2 j ：根据发现知识的种类分 类、根据挖掘的数据库的种类分类和根据采用的技术分类。这里主要根据知识 的种类来进行分类和不同类型之间的比较。 关联分析：关联分析发现关联规则，这些规则展示属性一值频繁地在给定数据 集中一起出现的条件。更形式地，关联规则是形如x y ，即”a i aa m b ， b 。”的规则；其中，a i ( i e 1 ，m ) ) ，b j ( i 1 ，n ) 是属性值对。关联规则解 释为“满足x 中条件的数据库元组多半也满足y 中条件”。 关联规则是数据挖掘最重要的知识类型，本文的主要研究对象就是针对关 联规则知识。在下一章，将对关联规则知识做更具体的介绍。 分类和预测：找描述或识别数据类或概念的模型( 或函数) ，以便能够使用模 3 姑 ，赫甜 理 匕 !印 第一章绪论 型预测类标号未知的对象。导出模型是基于对训练数据集( 即，其类标号已知 的数据对象) 的分析。 导出模式可以用多种形式表示，如分类( i f - t h e n ) 规则、判定树、数学公 式、或神经网络。判定树是一个类似于流程图的结构，每个结点代表一个属性 值上的测试，每个分枝代表测试的一个输出，树叶代表类或类分布。判定树容 易转换成分类规则。当用于分类时，神经网络是一组类似于神经元的处理单元， 单元之间加权连接。分类可以用来预测数据对象的类标号。然而，在某些应用 中，人们可能希望预测某些遗漏的或不知道的数据值，而不是类标号。当被预 测的值是数值数据时，通常称之为预测。尽管预测可以涉及数据值预测和类标 号预测，通常预测限于值预测，并因此不同于分类。预测也包含基于可用数据 的分布趋势识别。 聚类分析：聚类分析数据对象，而不考虑已知的类标号。一般地，训练数 据中不提供类标号，因为不知道从何开始。聚类可以产生这种标号。对象根据 最大化类内的相似性、最小化类间的相似性的原则进行聚类或分组。 即对象的聚类这样形成，使得在一个聚类中的对象具有很高的相似性，而 与其它聚类中的对象很不相似。所形成的每个聚类可以看作一个对象类，由它 可以导出规则。聚类也便于分类编制，将观察组织成类分层结构，类似的事件 组织在一起。 局外者分析：又称为奇异点分析，数据库中可能包含一些数据对象，它们 与数据的一般行为或模型不一致。这些数据对象是局外者。大部分数据挖掘方 法将局外者视为噪音或例外而丢弃。然而，在一些应用中( 如，欺骗检测) ， 罕见的事件可能比正规出现的那些更有趣。局外者数据分析称作局外者挖掘。 局外者可以使用统计试验检测。它假定一个数据分布或概率模型，并使用 距离度量，到其它聚类的距离很大的对象被视为局外者。基于偏差的方法通过 考察一群对象主要特征上的差别识别局外者，而不是使用统计或距离度量。 局外者分析可以发现信用卡欺骗。通过检测一个给定账号与正常的付费相 比，付款数额特别大来发现信用卡欺骗性使用。局外者还可以通过购物地点和 类型，或购物频率来检测。 演变分析：数据演变分析描述行为随时问变化的对象的规律或趋势，并对 其建模。尽管这可能包括时间相关数据的特征、区分、关联、分类或聚类，这 4 第一章绪论 类分析的不同特点包括时间序列数据分析、序列或周期模式匹配和基于类似性 的数据分析。 1 3 数据挖掘中的继承性问题 1 3 1 继承性研究背景及现实意义 数据挖掘技术的处理对象是现实世界中的数据。随着计算机技术在生活中 的广泛应用，数据挖掘要处理的数据表现为两个主要特征：数据规模不断扩大， 人类一切可查阅的数据基本都以各种形式在计算机内储存，数据挖掘要面对海 量数据进行处理；数据在不断变化中，例如超市交易数据、w e bl o g 记录等等， 每天都有大量的数据更新。面对这种不断变化中的海量数据，传统的数据挖掘 方法很难处理，无法及时得到有指导意义的知识。 通过对数据挖掘过程研究可以发现，数据挖掘本身是一个反复的交互式过 程，用户的本次要求与前次要求往往有较大的重复性，这种重复性主要反映在 三方面： ( 1 ) 数据集的增量性( 渐进性) 数据挖掘过程的数据采集往往与时间紧密相 关。在很多情况下，本次挖掘的数据集与前次挖掘的数据集有很大的重叠。举 例来说，数据挖掘的要求可能是“基于以往6 个月的数据，寻找家电部所有商品 的顾客购买模式”。为了紧跟市场，这种数据分析每月都要进行一次。 实际上， 对于相邻的两个月来说，数据挖掘的数据集的重复率达8 0 以上。 ( 2 ) 算法参数改变时结果的相似性。在同一次挖掘过程中，用户一般也会不 断地调整算法参数( 如最小支持度、最小置信度等) ，通过反复试探逐步聚焦到真 正感兴趣的问题上。参数的调整是渐进的过程，相邻两次调整间的结果有较大 的相似性。 ( 3 ) 不同知识类型之间存在相似性。例如关联挖掘得到的关联规则与分类挖 掘得到的分类规则在形式上相似。通过对关联规则挖掘方法的特殊处理，可以 提取关联规则中的一部分用于分类，实现不同知识之间的继承。 利用数据挖掘过程相似性，可以在新的挖掘时继承原有的挖掘结果，一定 程度上解决传统数据挖掘不能处理的问题，使数据挖掘从理论走向实际应用。 5 第一章绪论 1 3 2 数据变化时的继承 原则上讲，数据挖掘可以在任何类型的信息存储上进行。这包括关系数据 库、数据仓库、事务数据库、先进的数据库系统、文件和w w w 。先进的数据 库系统包括面向对象和对象一关系数据库；面向特殊应用的数据库，如空问数据 库、时问序列数据库、文本数据库和多媒体数据库。 传统的数据挖掘方法在处理这些数据时，一般采用静态的方法。即把某一 时刻的全部数据作为一个处理对象，用特定的数据挖掘算法进行分析得到指导 性的知识。当数据发生改变时，再把这一时刻的全部数据作为处理对象进行分 析。 现实世界中的数据变化是渐进性的，新数据并不会改变以往存储的数据， 而是作为新的记录存储在数据库中。为了及时得到指导性的知识，需要经常性 的对不断变化的数据用数据挖掘方法进行分析。由于数据变化的渐进性特征， 采用传统的数据挖掘方法处理实际数据时会产生大量的重复工作，主要表现在 对老数据集挖掘得到的知识不能在新数据集挖掘时得到继承。 以超市交易数据为例，假设某超市月平均交易数为一百万条，为了指导销售 该超市每月采用数据挖掘方法分析交易数据。为了反映该超市交易的整体特征， 每次需要对超市近一年内的交易数据进行分析。这样虽然每月增加的数据量为 一百万条，但需要处理的数据将超过一千万条。 数据变化时的继承性研究就是为了解决这一问题，对于老数据集挖掘得到 的知识采用中间知识的形式存储起来。当有新数据加入时，只需把新数据进行 挖掘得到的中间知识与老的中间知识耦合到一起，再把中问知识转化为人类可 理解的知识反馈给用户。设计良好的中间存储形式能较好的实现知识的耦合， 大幅度的提高数据变化时的挖掘效率。 1 3 3 参数改变时的继承 与其他人工智能领域的算法类似，数据挖掘方法在挖掘开始前，需要人为 的设置一些参数来指导挖掘过程。例如对未知类别数据进行k _ m e a n s 4 3 1 聚类分 析，首先要设定该数据可能属于几类数据，同时还需要指定类别初始中心点位 置( k - m e a n s 的初始中心点是随机选取的) ，不同的类别数和中心点位置得到的最 6 第一章绪论 终聚类结果大相径庭。由于数据的未知性，初始参数类别数k 和中心点位置很 可能与真实的数据分布有很大不同。为了得到更好的聚类结果，需要反复的改 变初始参数。 对分类神经网络学习算法存在同样的问题。神经网络i 巧】是一组连接的输入 输出单元，其中每个连接都与一个权相相联。在学习阶段，通过调整神经网络 的权，使得能够预测输入样本的正确类标号来学习。神经网络需要很长的训练 时间，因而对于有足够长训练时间的应用更合适。它需要大量的参数，这些通 常主要靠经验确定，例如网络的层数，输入层输出层节点个数等等。理论上说， 神经网络可以模拟任意的函数或映射，也就是说对给定的以分类的训练数据集， 一定可以用某种形式的神经网络，对该数据进行正确区分。但这种高准确性是 以正确的初始参数为基础的。对u c l 标准数据集中的z o o 数据库进行实验， 当中间层节点个数增加两个时，最终训练得到的神经网络准确性从7 0 增加到 9 5 以上。由于这些参数一般只能靠经验确定，很难迅速得到适合的参数，因此 神经网络的训练通常是多次循环往复的过程。 传统的数据挖掘方法，当挖掘参数改变时，只是以新的参数重复运行数据 挖掘算法。一般情况下，在原来参数下挖掘得到的结果也是有意义的，这些原 参数下挖掘的知识也可以继承到新参数下的挖掘过程中。 1 4 本文的研究内容和组织结构 数据挖掘技术是近年来数据库和人工智能领域研究的热点课题，其众多研 究方向中关联规则是较早开展的，关联规则的挖掘是数据挖掘领域中一个非常 重要的研究课题。数据挖掘的继承性研究是数据挖掘技术从理论走向实际应用 的一个重要研究方向。本文研究重点是关联规则挖掘的可继承性问题。 文中第一章介绍数据挖掘技术的有关概念，以及数据挖掘产生的背景、现 实意义、目前的研究现状和技术方法，并初步介绍数据挖掘继承的概念和三种 不同意义上的继承性。 从第二章开始讨论数据挖掘技术中的关联规则继承性挖掘问题，首先介绍 关联规则的基本概念和分类情况，然后详细描述了联规则的研究方向及其经典 算法，最后介绍关联规则继承问题的概念和分类，并简单介绍已有的研究成果 和继承性关联规则挖掘算法。 7 第一章 绪论 第三章主要研究用于继承性关联规则挖掘的中间存储形式。数据挖掘的继 承需要对以前的挖掘结果迅速的进行存储、查询和计算。因此挖掘结果的表示 就成为研究的重点内容。为此，我们提出中间知识的概念。在这一章首先介绍 中间知识的概念和作为中间存储形式应该具有的特殊性质。然后针对关联规则 知识，分析两种不同类型的中间存储形式。 第四、五章是论文的核心内容，分别研究关联规则继承性挖掘的两个重要 方面。第四章研究参数变化时的关联规则继承性，通过对参数改变问题的实质 进行探讨，选择适合的中间存储形式，提出b pi u a 算法对支持度改变后的频 繁模式进行增量更新。第五章研究数据变化时的关联规则继承性，提出基于两 种中间存储形式的b i t m a p _ p r o j e c t i o n 算法处理数据增量时的频繁模式继承问题， 并初步探讨了数据变化与参数变化问题的相关性。 第六章介绍论文实验系统的设计与实验分析。针对继承性问题的特殊性， 首先提出继承性挖掘系统的设计原则，并介绍实验数据的选择和实验模型的设 计。并进一步设计实验，验证在处理参数变化或数据变化的关联规则挖掘问题 时，使用继承性的挖掘算法的有效性。 论文最后对研究工作进行总结，并提出进一步的研究方向。 8 第二章 关联规则继承性算法 第二章关联规则继承性算法基本问题 2 1 数据挖掘中的关联规则问题 关联规则最早由r a g r a w a l l l 】等人提出，是数据挖掘的一个重要研究方向， 也是数据挖掘中最成熟、最活跃的研究领域。关联规则挖掘就是发现大量数据 中项集之间有趣的关联或相关联系。随着大量数据不停地收集和存储，许多人 士对于从他们的数据库中挖掘关联规则越来越感兴趣。从大量商务事务集中发 现有趣的关联关系，可以帮助许多商务决策的制定，如分类设计、交叉购物分 析。 2 1 1 关联规则问题定义 挖掘关联规则的问题，最早是超级市场的数据，交易集由顾客购买的项目 组成，数据看成是二进制的( 在交易中出现时为1 ，否则为0 ) ，不考虑交易中 项目的数量。a g r a w a l 在给中给出了在数据库中挖掘关联规则问题的定义， 描述如下：令i - i 1 ，i 2 , i 3 ，i m ) 是m 个不同项目( i t e m ) 的集合，d 是给定的针对i 的交易数据集，d 中包含有n 项交易，每一项交易t 是i 中的一组项目集，t c _ i 。 每项交易都有一个标示符t i d 。 定义2 1 ：令x 是i 中任一项目集，若其中含有k 个项目，则称其为k 项目 集。 定义2 2 ：当且仅当x _ t 时，称交易t 支持x ，一个项目集x 的支持度 ( s u p p o n ) 为数据集d 中包含x 的事务数量与数据集d 的总事务数量之比。 定义2 - 3 ：若项目集x 在d 中的支持度s u p p o g ( x ) 大于用户提前明确的最 小支持度( m i n s u p ) ，则此项目集为频繁项目集( 大项目集) 。否则为不频繁项目 集( 小项目集) 。 定义2 4 ：一条关联规则蕴含式形如；x j y ，其中x c i ，y c i ，x ny = 囝。 这里x 称为规则的前部( a n t e c e d e n t ) ，y 称为规则的后部( c o n s e q u e n t ) 。若交易 0 第二章关联规则继承性算法 d 中s 的交易包含x 的同时也包含y ，则规则在d 中的支持度为s ，表示出来 就是s = s u p ( x u 的；若交易集d 中包含x 的交易的c 也包含y ，则规则在d 中的置信度( c o n l i d e n c e ) 为c ，用公式表示就是c ：c 。；s u p ( x _ = u _ y ) 。可以看出 s u p ( aj 其实置信度是一个条件概率，是在给定x 条件下y 出现的概率。 支持度表示规则在数据库中出现的频度，置信度表示规则的强度。最小支 持度阈值( m i n _ s u p ) 表示项目集在统计意义上的最低主要性。最小置信度阈值 ( r a i n 度闽值，支持度和置信度大于规定的闽值的规则称为强关联规则，反之，为弱 关联规则。挖掘关联规则的任务就是发现所有支持度和置信度大于用户给定阈 值的强规则，即产生所有形式为x y 的关联规则，其中 s u p ( 爿r u r ) m i ns u p i d i ，c o n f ：s u p ( x u y ) m i n c o n f 。 s u p ( x ) 关联规则挖掘问题可以分成两个子问 疆1 2 1 ： ( 1 ) 产生所有支持度大于用户指定阈值的项目集，也就是频繁项目集； ( 2 ) 利用这些频繁项目集生成关联规则。对子每一个大项目集l ，找出它 的所有非空子集，对每一个非空子集a ，如果兰! 班掣z r a i n _ c o n f ，则生成形式 s u p o ) 为a l a 的规则。那些在第一步被发现是频繁的项目集的支持度要保留，以供 第二步计算规则的置信度时使用。为了方面描述，后文中的最小支持度闽值和 最小置信度阈值分别简称为支持度阈值和置信度阈值。 2 1 2 关联规则挖掘算法介绍 关联规则挖掘问题可分解为两个子问题，其中由频繁模式生成规则部分， 解决思路比较直接，不同算法的处理方法基本相同。目前关联规则算法研究都 集中在从数据中挖掘频繁项目集问题。根据频繁集的生成顺序，关联规则挖掘 算法分为广度优先的a p r i o r i 算法体系和深度优先的f p g r o w t h 算法体系。下面 介绍a p r i o r i 算法时，将描述关联规则挖掘的两个阶段的完整过程，介绍 f p g r o w t h 算法时将主要针对频繁模式的产生过程，对两种方法进行比较。 1 0 第二章关联规则继承性算法 a p r i o r i l l 算法是一种最有影响的挖掘关联规则频繁项集的算法。a p r i o r i 使用 一种称作逐层搜索的迭代方法，虹项集用于探索他+ 1 ) 项集。首先，找出频繁1 项集的集合。该集合记作工l 。功用于找频繁2 项集的集合2 ，而幻用于找l 3 ， 如此下去，直到不能找到频繁七项集。找每个k 需要一次数据库扫描。 a p r i o r i 算法利用频繁集挖掘过程中的反单调性质来对搜索空间进行剪枝， 提高挖掘效率。频繁项集的所有非空子集都必须也是频繁的。a p r i o d 性质基于 如下观察：根据定义，如果项集，不满足最小支持度阈值s ，则，不是频繁的， 即尸 s ，那么s u p 。 s ，即 c l ( c l ) ，故有l l l jl l 成立。同样可证性质4 1 的后半部分。 由性质1 可知，在第( 2 ) 种情况下，频繁项目集的更新是很简单的，只需在原来 的频繁项目集l 中删除所有支持度小于s 的项目集即可；在第( 1 ) 种情况下，当前 3 2 第四章参数变化时时的关联规则继承性研究 己发现的频繁项目集l 仍然生效，而原有的一些非频繁项目集可能成为新的频繁 项目集。因此，如何发现d 中所有新的频繁项目集( 记为l 咀) 将是第( 1 ) 种情况的 关键问题。 性质4 2 设l 。- - l 。，l 。一 c 己l c n l 。g i s o ； c l l c n l 。一o ，c 萑l ， 贝0 i s 。n t ；o - 彩，l n n l - o ，l l u l 。，l 。t l 。u l 。 证明：性质中k ，表示新增的频繁项目，l 。表示包含新增频繁项的新增频繁 项集，表示不包含新增频繁项的新增频繁项集。 l 。n l 。一a ，i s 。a l o ，lz l u l 。显然成立。对l 。一i s u k ，设任意项目集x ， 如果x e i s 。u i s 。，那么x e l ，且x 诺l ，因此x 为新增的频繁项目集，即x k 。 反之，如果x i 咀，用反证法可证。 由性质4 1 2 可知，支持度降低时新增的频繁模式由两部分组成，一部分是由 于支持度降低新产生的频繁项与以前的频繁项连接产生的频繁项集，另一部分 是原来的频繁项连接后支持度小于老支持度，但大于新支持度。 4 4 2 基于b f t r e e 中间存储形式的继承性算法 b f t r e e ( b o u n dp a r e r nt r e e ) 是对f p 树的扩展，建树过程不对非频繁项过滤， 而是挂接到频繁项节点下方。通过b o u n d 节点区分频繁项节点和非频繁项节点。 相应的项目头表中非频繁项目处于表下方，通过b o u n d 标记与频繁项进行区分。 b f 树的项目头表具有以下性质： 性质4 3 设h t a b l e 1 ：m ，h t a b l e 【1 ：m 】分别表示支持度为s ，s 时的项目头表中 的频繁项目，n = l l n l i ，。h t = h t a b l e 【k 】i t e m - n a m e im m i n _ s u p b o u n d _ m o v e 叫o d e ( y ) ) ； 标记n o d e ( x ) 为非b o u n d 节点 e l s e 标记n o d e ( x ) 为b o u n d 节点 图3 2 所示示例数据， 1 1 ：2 支持数由2 降低至1 时， b o u n dm o v e 操作前后的 b p 树比较如图4 2 所示。 通过一次项目头表 b o u n d 改变和5 次树中节 点的b o u n dm o v e 递归过 程，即可得到新支持度下 第四章参数变化时时的关联规则继承性研究 图4 2b o u n dm o v e 过程示例 的b p 树。算法运行时间 1 1 ：2远小于在重新建树时 间。由于b p 树结构具有 前缀特性，项集共享共 同的上层节点。因此b p 树存储空间与原始数据 库大小保持线性相关。 对稠密数据集具有 一定的压缩能力。 由性质5 2 ，当支持度降低时，产生的新频繁模式由两部分组成。一部分包 含新增的频繁一项集，对于这部分频繁模式，直接在b p 树上建立新增频繁项的 条件模式树，在树中由b o u n d 节点向上直接调用f pg r o w t h 方法产生。由于b p 树中新增频繁项目对应的节点通过b o u n dm o v e 操作，都标志为b o u n d 节点， 因此很容易建立其对应的条件模式树。 另一部分不包含新增频繁项，对于这部分模式需要在非b o u n d 节点上建立 条件模式树，在条件模式树上挖掘时利用性质4 5 进行剪枝。 性质4 5 设原支持数阈值为s ，新支持数阈值s ，s s 。对b p 树中非b o u n d 节点n o d e ( x ) ，如果n o d e ( x ) 的条件模式树中存在一条分支支持数大于原支持数 阈值m i ns u p ，则对该分支产生频繁模式后删除该分支不影响最后挖掘的频繁模 式。 证明：由f pg r o w t h 挖掘过程可知，对项目x ，包含x 的所有频繁模式都 在x 的条件模式树中。如果在新的支持度下x 的条件模式树中有分支支持数大 于原来的支持数阈值，则所有由该分支产生的频繁模式在原支持数阈值下已经 产生过，因此无需对该分支继续进行挖掘。 利用性质4 5 ，对第二部分频繁模式进行挖掘时，产生条件模式树过程中， 可直接删除递归过程中出现的支持数大于原支持数闽值的分支。 综合两部分模式挖掘过程，基于b p 树的参数改变时的频繁模式继承算法 b p1 u a 算法伪代码如下所示。 3 5 第四章参数变化时时的关联规则继承性研究 算法：b p j u a 。参数改变时基于b p 树的频繁模式更新算法 输入：原支持数阈值s ，新支持数阈值s ，支持数为s 时的b p 树和频繁模式。 输出：更新的b p 树和频繁模式 ( 1 ) 挖掘主程序b p _ i u a 0 i fs s ， 标志该节点为b o u n d ) e l s en 支持度降低 b p 树项目头表b o u n d 节点下移至s 1 f 项目头表b o u n d 节点变化腩新项目产生 f o re a c h 树中b o u n d 节点n o d e ( x ) b o u n d _ m o v e ( n o d e ( x ) ) 对项目头表中b o u n d 之间项目x f p g r o w t h ( t r e e ，x ) f o r e a c h 项目头表中原b o u n d 节点上层项目x b p _ g r o w t h ( t r e e ，x ) ) ( 2 ) b p _ g r o w t h 子程序，用于第二部分频繁模式产生。 b p g r o w t h ( t r e e ，均 i ft r e e 中存在单条路径 产生频繁模式 第四章参数变化时时的关联规则继承性研究 e l s e 对多个路径每个分支y 产生新模式x y 对x y 建立条件模式树t r e e ( x y ) ； 利用性质4 5 剪枝 i f 树中存在分支支持度 s 删除树中该分支 b p _ g r o w t h ( t r e e ( x y ) ，x y ) ) 如前所示，支持度改变时关联规则继承性挖掘的实质是挖掘支持度在【a ，b 】 范围内的模式。通过剪枝操作，b p _ i u a 算法在挖掘不包含新增频繁项目的新增 频繁模式时只产生支持度在i s ，s 】范围内的模式。而包含新增频繁项目的新增频 繁模式支持度一定属于【s ，s 】。因此b p _ i u a 算法能有效的处理该问题。 在第六章实验分析中，我们对该算法处理实际数据的有效性进行了分析。 第五章数据变化时的关联规则继承性研究 第五章数据变化时的关联规则继承性研究 5 1 数据变化时的中间存储形式设计 关联规则处理的数据对象通常是处于不断变化中的，例如超市中的交易数 据，网络入侵检测中的流数据。为了迅速对变化的数据进行处理，及时得到指 导性规则需要对以往的挖掘