数据流上频繁模式和高效用模式挖掘(txt+pdf+epub+mobi电子书下载)

作者：王乐

出版社：知识产权出版社

格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT

数据流上频繁模式和高效用模式挖掘试读：

前言

数据和信息正以前所未有的速度增长。正如Kevin Kelly在著名的What Technology Wants里面提到的那样，人类几百万年的基因变异，平均速度大约是每年1bit；而现在信息社会每年新增的信息量为40018艾（exa，IE＝10），即人类1s内处理数据的总量，等于我们的DNA用10亿年处理的数据量。在这样的滔天数据洪流面前，如何及时地对已产生的数据进行挖掘和分析，从中提取我们关心的、与企业产能和效益有密切关系的潜在信息，是信息时代的企业需要特别关注的问题；其中一个重要的方面，就是对关联关系（频繁模式）和高效用模式的挖掘。

由于数据流具有海量性、实时性和动态变化性的特点，这就要求数据流上的挖掘算法有较高的时空效率。尽管数据流上模式挖掘技术取得了一定的进展，但是挖掘算法的时空效率仍然是当前数据挖掘领域中的研究焦点之一。

本书以数据流上的频繁模式和高效用模式挖掘计算为背景，介绍该领域相关的概念、理论及近年来相关的最新研究成果，内容包括传统数据集中的频繁模式挖掘及其大数据集下的频繁模式挖掘算法、不确定数据流中的频繁模式挖掘算法、具有效用值的数据流中的高效用模式挖掘算法，以及包含相应静态数据集中的挖掘算法。全书共分为五章：第1章首先对已有的频繁模式和高效用模式挖掘算法进行了回顾，详细地介绍了算法Apriori和FP-Growth等；第2章探讨传统的动态数据中的频繁模式挖掘算法；第3章首先探讨不确定静态数据上的频繁模式挖掘算法，然后探讨了不确定数据流中的频繁模式挖掘算法；第4章探讨静态数据集上的高效用模式挖掘算法，然后基于静态数据集上的挖掘算法，介绍数据流中的高效用模式挖掘算法；第5章以传统数据集为例，介绍了MapReduce框架下的频繁模式挖掘算法。各章内容相对独立又相互联系，较为系统地阐述了数据流中几种模式挖掘算法的研究现状。

本书主要内容为作者在攻读博士学位期间的研究成果，其中部分工作得到国家自然科学基金项目“大数据环境下高维数据流挖掘算法及应用研究”（61370200）、宁波市自然科学基金项目“面向大数据的高频金融时间序列高效用时态频繁模式挖掘研究”（2013A610115）和“多重不确定数据流上模式挖掘的建模及算法研究”（2014A610073）等项目的支持，并得到宁波大红鹰学院优秀博士计划资助。书稿的撰写过程中，大连理工大学的冯林教授、杨元生教授、金博博士等老师给予了大力支持和热心指导，同时也得到姚远、刘胜蓝、张晶、姜玫、吴明飞、王辉兵、蔡磊等同学的关心和合作，在此一并感谢！作者2014年7月于宁波大红鹰学院

主要符号表

智能终端、互联网及无线传感网络的发展将我们带入了一个数据的时代，据市场研究公司Strategy Analytics的分析师预测称：在未来5年内，全球移动用户基数将增加到89亿；中国三家电信运营商的各省份公司也都在构建着自己的数据仓库，而这些数据仓库的总体规模已达到数十PB的水平；腾讯微博每天约有4000万条微博信息；YouTube每月上传的视频近100万h。此外，传感器网络、移动网络、电子邮件、社会网络以及生物信息等领域每天都会产生海量数据，在此推动下，数据流成为未来数据发展的一个主要趋势，而从数据流中挖掘有用的知识得到广泛的重视。

数据挖掘（Data Mining，DM）是从大量的、不完全的、有噪声的、模糊的、随机的数据中提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。当积累的数据越来越多，如何从积累的数据中提取有用的知识成为很多行业的当务之急。数据挖掘的技术主要有关联规则挖掘、聚类分析、分类、预测、时序模式和偏差分析等。

自从数据挖掘技术出现以来，关联规则挖掘一直是数据挖掘领域中的一个最基本和最重要的研究方向。关联规则挖掘的重要工作就是挖掘频繁项集（频繁模式），因此关联规则挖掘也常常称为频繁模式挖掘。根据处理的事务数据集的类型不同，存在传统数据集上的频繁模式挖掘、不确定数据集上的频繁模式挖掘和具有内外部效用值数据集中的高效用模式挖掘等。传统的数据集仅仅考虑了事务项集中的项是否出现，而没有考虑事务项集中的项集效用值；高效用模式挖掘将事务项集中的效用值也考虑到模式的挖掘模型中；不确定事务数据集中的频繁模式挖掘考虑了事务项集中项对应值的不确定性。以上不同类型中的模式挖掘已被广泛应用在商业、企业、过程控制、政府部门及科学研究等领域。如在移动通信数据中，可以通过频繁模式挖掘出高消费客户群的消费规则、不同客户群之间的关系、增值较高的业务组合、客户的消费推荐等；在关联规则产生的过程中，可以同时利用频繁模式和高效用模式来产生利润最大的规则。另外频繁模式挖掘也被扩展到了聚类、分类、预测、序列模式、异常检测等其他数据挖掘技术中。

本书分别对传统数据流、不确定数据流中的频繁模式挖掘算法及数据流中高效用模式挖掘算法进行了分析与研究，分别介绍新的挖掘算法或者对已有算法的改进算法；同时本书也对大数据集中的频繁模式挖掘算法进行了分析与研究，并介绍基于MapReduce并行框架的大数据的频繁模式挖掘算法。1.2　国内外研究现状

由于静态数据集和动态数据流的数据特征不同，从中挖掘频繁模式或高效用模式的算法也有所不同；但是静态数据集的挖掘算法是动态数据流中挖掘算法的基础，本节分别从静态数据集、动态数据流两方面介绍频繁模式和高效用模式挖掘算法的研究现状。1.2.1　传统数据集中频繁模式挖掘算法的研究

1．静态数据集上频繁模式挖掘算法[1]，[2]

Agrawal等首先提出了频繁模式挖掘问题的原始算法，并给出了著名的Apriori算法。该算法的主要理论依据是频繁项集的两个基本性质：①频繁项集的所有非空子集都是频繁项集；②非频繁项集的超集都是非频繁项集。算法Apriori首先产生频繁1-项集L，然后利用1频繁1-项集产生频繁2-项集L，直到有某个r值使得L为空为止。在第2rk次循环中，算法先产生候选k-项集的集合C，C中每一个项集是用kk两个只有一项不同的L中进行并集产生的。C中的项集是用来产生k-1k频繁k-项集的候选项集，即频繁项集L是C的一个子集。C中的每个kkk项集需要统计在数据集中的个数，从而来决定其是否加入L，即需要k扫描一遍数据集来计算C中的每个项集的支持度。k

Apriori是首次提出采用逐层挖掘的算法，并且是逐层挖掘算法中的代表算法，之后的很多算法都是在此基础上进行改进，如算法

[3]DHP采用Hash技术来优化Apriori算法中候选项集的产生过程。[4]Cheung等采用并行方式对Apriori算法进行改进，将数据集划分为多个小数据块，在每次迭代产生频繁项集过程中，首先并行计算所有候选项集在各个数据块的支持数，然后汇总每个候选项集的总支持数（即可从候选项集中找到频繁项集），最后再利用当前层产生的频繁项集来产生新的候选项集来进行下次的迭代。算法Apriori的主要缺点：①扫描数据集的次数至少等于最长的频繁项集的长度；②需要维护算法过程中产生的候选项集（中间结果）。

算法Apriori在挖掘过程中产生了大量的候选项集，并且需要反复扫描数据集，严重影响了算法效率。为此，Han等人提出了一种无须[5]产生候选项集的算法FP-Growth，该算法只需要扫描数据集两次：第一次扫描数据集得到频繁1-项集；第二次扫描数据集时，利用频繁1-项集来过滤数据集中的非频繁项，同时生成FP-Tree，然后在FP-Tree上执行递归算法，挖掘所有的频繁项集。实验分析表明FP-Growth算法比Apriori算法快一个数量级。

算法FP-Growth是采用模式增长的方式直接生成频繁模式，该算法是模式增长算法中的典型算法，同时也是第一个模式增长算法，之[6]-[18]后提出的模式增长挖掘算法都是在此基础上进行改进的，包括不确定数据集中频繁模式挖掘和高效用模式挖掘中的很多算法。[19]

算法COFI不需要递归的构建子树，该算法通过项集枚举的方法来挖掘频繁模式；在稀疏数据集上，该算法的时间和空间效率优于算法FP-Growth，但在处理稠密数据集或长事务数据集的时候，该算法的处理效率比较低。[20]-[30]

之后提出了很多频繁项集挖掘算法，包含完全频繁项集挖[5][20]，[19]，[21]，[22]，[24]，[26]，[31]-[35]，[28]，[36]掘、闭项集挖掘和最大频繁[23]，[25]，[27]，[29]，[37]项集挖掘；其中国内在这领域研究也有较大的进[7][75][78]，[38]-[74]-[77]，展，包括TOP-K频繁项集挖掘、负关联规则挖掘算法[79]等。

2．数据流中频繁项集挖掘算法

和静态数据集相比，动态数据流上有更多的信息需要跟踪，如以前频繁模式后来变为非频繁项集，或以前非频繁模式后来变为频繁模式；另外，由于数据的流动性，当前内存中维护的数据要不断地调整。数据流中的频繁模式挖掘算法一般采用窗口方法获取当前用户关注的数据；然后基于已有的静态数据集上的频繁模式挖掘算法，提出可以[80]挖掘数据流中被关注数据的算法。目前存在3种典型的窗口模型：界标窗口模型（Landmark Window Model）、时间衰减窗口模型（Damped Window Model）和滑动窗口模型（Sliding Window Model）。

界标窗口模型中的窗口指特定一时间点（或数据流中一条特定的数据）到当前时间（或当前条数据）之间的数据，界标窗口模型如图1.1（a）所示，在C1、C2和C3时刻，窗口中的数据分别包含了从S点到C1点、C2点和C3点之间的数据。文献［81-85］中频繁项集挖掘算法都是基于界标窗口，文献［82］提出算法DSM-FI（Data Stream Mining for Frequent Itemsets）是基于界标窗口，它以数据开始点为界标点，该算法有三个重要特征：①整个挖掘过程只需要一遍数据集扫描；②扩展前缀树存储挖掘的模式；③自上而下的方式挖掘频繁项集。文献［83］提出一个基于界标窗口的频繁闭项集挖掘算法FP-CDS，该算法将一个界标窗口划分为多个基本窗口，每个基本窗口作为一个更新单元（每个基本窗口中的数据也可以称为一批数据）：首先从每个基本窗口中挖掘出潜在的频繁闭项集，同时存储在FP-CDS树上，最终从FP-CDS树上挖掘出所有的频繁闭项集。文献［84］提出一个近似算法Lossy Counting，该算法以批为处理单元，每来一批就更新一次已有频繁项集的支持数，频繁的项集被保留下来，不频繁的被删除，同时也将当前批中新的频繁项集保留下来。图1.1　三种窗口模型S—数据流中指定的起点；C1，C2，C3—3个不同的处理点；S1，S2，S3—3个不同的起点。

时间衰减窗口模型和界标窗口模型所包含的数据是相同的，只是衰减窗口中的每条数据有不同的权重，距离当前时间越近，数据的权重越大，如图1.1（b）所示；实际上，时间衰减窗口模型是界标窗口模型的一个特例。文献［86-90］中算法都是基于时间衰减窗口模型。文献［86］提出一个基于衰减窗口模型的近似算法，该算法用一个树结构FP-stream来存储两类项集：频繁项集和潜在频繁项集。当新来一批数据的时候，更新树结构上这两类项集的支持数，如果更新后的项集既不是频繁项集，也不是潜在频繁项集，则将这类项集从树上删除；同时新来一批数据中新产生的频繁项集或潜在频繁项集也要存储在这个树结构上。文献［87］引入一个时间衰减的函数来计算项集支持数以及总的事务支持数。文献［88］采用固定的衰减值，当新来一个事务项集的时候，已有的频繁项集的支持数都乘以固定的衰减值，如果新来的事务包含某一频繁项集，则该项集的支持数再加上1。

滑动窗口模型中当前处理数据的个数固定，或者是当前处理数据的时间段长度固定，如图1.1（c）所示。基于滑动窗口模型的频繁项[91]-[100]集挖掘算法研究比较多。文献［92］提出一个挖掘算法DST，该算法指定一个窗口中有固定批的数据，并且每批数据中事务个数也是固定的，每新到一批数据就更新一次窗口；DST将窗口中事务数据保存到树DST-Tree上，DST-Tree的节点结构如图1.2（a）所示，节点上的P字段记录节点当前窗口中每批数据中的支持数，同时每个节点还用L字段记录更新该节点的最后批次；每新来一批数据，将新到的数据添加到树DST-Tree上，同时修改相应节点上的P值和L值。算法DST在挖掘窗口中频繁项集之前，先把树上不再有用的节点（垃圾节点）从树上删除，然后用算法FP-Growth挖掘每个窗口中的频繁项[93]集。文献［92］的作者后来又提出一个算法DSP，算法DSP和DST的主要区别是DSP采用COFI来挖掘窗口中的频繁项集，而DST是用FP-Growth挖掘窗口中的频繁项集；算法DSP存储事务项集的树结构和DST的相同。图1.2　树DST-Tree和CPS-Tree的节点结构N—节点名；S—总支持数；L—最后更新批次；P—pane-counter ［V，1V，…，V］（V—第i批中的支持数；w—窗口中的总批数）。2wi

文献［95］提出一个基于滑动窗口的频繁项集挖掘算法CPS，在算法CPS中，每个窗口是由固定批的数据组成，以批为单位更新窗口中数据，该算法将窗口中事务项集保存到一棵CPS-Tree树上，树CPS-Tree上有两类节点：正常节点（normal node）和尾节点（tail-node），正常节点上只记录该节点总的支持数S，如图1.2（b）所示；而尾节点要记录总的支持数S，同时还用一个数组P记录一个节点当前窗口中每批数据上的支持数，如图1.2（c）所示。每新来一批数据，该算法会将树中的垃圾节点删除，采用FP-Growth算法挖掘每个窗口中的频繁项集。1.2.2　不确定数据集中的频繁模式挖掘算法的研究

随着数据挖掘技术的广泛应用、数据采集中的不确定性和误差性等原因，现实中会产生很多不确定的数据，例如一个病人在问诊中，往往并不能根据病人的症状而被百分之百地确诊为某一病；通过[101]，[102]RFID或者GPS获取的目标位置都有误差；用商业网站或历史数据中挖掘到的购物习惯来预测某些顾客下一步购买的商品都存在一定的不确定性。表1.1是一个不确定数据集的例子，每个事务表示某一顾客最近要买哪些商品以及买这些商品的可能性（概率）。因此随着不确定数据在很多领域的产生，对该类数据进行挖掘分析又成为数[103]-[124]据挖掘领域一个新的研究问题。由于不确定数据集和传统数据集的数据结构不同，并且两类数据集上的频繁模式挖掘模型也不同，因此不能用传统数据集中的算法来挖掘不确定数据集中的频繁模式。本节根据数据集的静态和动态特性，分别描述不确定数据集上频繁模式挖掘算法的研究现状。表1.1　不确定数据集

事务事务项集t（a∶0.8），（b∶0.7），（d∶0.9），（f∶0.5）1t（c∶0.8），（d∶0.85），（e∶0.4）2t（c∶0.85），（d∶0.6），（e∶0.6）3

1．静态数据集

不确定事务数据集的频繁项集挖掘算法主要分为逐层挖掘（level-wise）和模式增长（pattern-growth）两种方法。逐层挖掘的算法基于算法Apriori，模式增长方式的算法则基于算法FP-Growth。表1.2列出了一些重要算法及其一些特征。表1.2　不确定数据集上的频繁模式挖掘的主要算法[121]

U-Apriori是第一个不确定数据集上的频繁项集挖掘算法，该算法是基于Apriori提出的。该算法和Apriori的主要区别是前者扫描数据集是为了计算每个候选项集的期望支持数，而后者扫描数据集是为了计算候选项集的支持数。因此U-Apriori算法的缺陷同Apriori算法一样：产生候选项集，以及需要多遍扫描数据集来统计每层候选项集的期望支持数，如果最长的频繁项集长度是k，则最少需要扫描k次数据集。因此，如果数据集比较大、事务项集长度比较长或设定的最小期望支持数比较小，则U-Apriori的时间和空间性能都会受到很大的影响。[115]

2011年，Wang等提出一个不确定数据集的频繁项集挖掘算法MBP。该算法主要是对U-Apriori算法的改进，作者提出了两种策略来提高计算候选项集的期望支持数的效率：①在扫描数据集的过程中，如果一个候选项集提前被识别为非频繁项集，就停止计算该项集的实际期望支持数；②扫描数据集的过程中，如果一个候选项集的当前期望支持数已经大于预定义的最小期望支持数，就停止计算该项集的实际期望支持数。因此，算法MBP在时间和空间性能上得到了很大的提升。[111]

2012年，Sun等改善了算法MBP，基于MBP算法给出一个不确定数据集中频繁项集挖掘的近似算法IMBP。IMBP时间和空间性能优于MBP，然而，其准确性并不稳定，并且在稠密数据集中的精确度比较低。[122]

2007年，Leung等提出一个基于树的模式增长的算法UF-Growth，该算法中还提出一个新的树结构UF-Tree来存储不确定事务数据集，采用模式增长的方式从树上挖掘频繁项集。UF-Growth和FP-Growth的主要区别有两点：①UF-Tree树上每个节点除了保存和FP-Tree树上节点相同的信息外，还保存了每个节点的概率值，因此只有项相同，并且其相应的概率值相同的项才能共享同一个节点；而FP-Tree中，只要项相同就可以共享同一节点。②UF-Growth中计算频繁项集的时候都是统计项集的期望支持数，FP-Growth是计算项集的支持数。因此，UF-Tree树上的节点比较多，例如，对于两个不确定事务项集{a：0.50，b：0.70，c：0.23}和{a：0.55，b：0.80，c：0.23}，当按照字典顺序插入树中时，由于两个事务中项a的概率不相等，所以这两个项集不能共享同一个节点a，从而算法UF-Growth需要更多的空间和时间来处理UF-Tree。[120]

Leung等又改善UF-Growth以减小UF-Tree树的大小。改进算法的思想：先预定义一个k值，只考虑事务项集中概率值小数点之后的前k位数，如果两个概率的小数点之后的前k位数值都相同，则认为这两个概率值相同。例如，设定k值为1，当这两个事务项集{a∶0.50，b：0.70，c：0.23}和{a∶0.55，b∶0.80，c∶0.23}再按字典顺序添加到UF-Tree上时，则项a的概率均为0.5，则这两个项集可以共享同一个节点a；但若k设定为2，则项a概率分别为0.50和0.55，则这两个项集就不能共享同一个节点a。k值越小，改进后的算法消耗的内存越小，但改进后的算法仍然不能创建一棵与原始FP-Tree一样压缩率的UF-Tree，并且改进后的算法还可能会丢失一些频繁项集。[125]

算法UH-Mine也是一个模式增长的算法，它和UF-Growth算法的主要区别：UF-Growth算法采用FP-Tree保存事务项集，而UH-Mine[26]采用非压缩的结构H-struct来保存事务项集。在将事务项集存储到H-struct上时，没有任何的压缩，即任两个项集都不会共享任何节点。H-struct的创建也需要扫描数据集两遍：第一遍，创建一个有序的频繁1-项集头表；第二遍，将事务项集添加到H-struct中，同时按头表的顺序添加，并且删除事务项集中非频繁的项。头表中还保存有每个频繁项在树上的所有节点。该算法在较小的数据集上，能获得较好的效果，然而在大数据集上，因为H-struct需要较多的空间来存储，同时也需要较多的时间来处理H-struct上的所有节点。

文献［125］也将经典算法FP-Growth扩展到不确定事务数据集，扩展后的算法命名为UFP-Growth。UFP-Growth采用FP-Growth的方法创建了一棵同样压缩率的树，但是创建的树会丢失事务项集相应的概率信息，所以UFP-Growth只是先从树上产生候选项集，最后通过一遍原始数据集的扫描确认真正的频繁项集。[109]

2011年，Lin等提出一个新的不确定事务项集的频繁项集挖掘算法CUFP-Mine。该算法是将事务项集压缩到一个新的树结构CUFP-Tree上，一棵CUFP-Tree树的创建需要扫描两遍数据集：第一遍扫描是为创建一个有序的频繁1-项集头表；第二遍扫描中，将事务项集按头表排序，同时删除事务项集中的非频繁项。假设项集Z（{Z，Z，12…，Z，…，Z}）是有序，并且所有项都是频繁的，则当任一项Z被imi添加到树上时，在对应节点上需要将Z的所有超集（超集是由项Z，i1Z，…，Z中的任意项组合的）及每个超集对应的期望支持数保存到2i该节点上。

CUFP-Mine的主要思想：所有的事务项集压缩到树上后，再统计相同节点上所有超集的总的期望支持数，即可判断哪些超集是频繁的。CUFP-Mine的优点是不需要递归的挖掘频繁项集；在设定阈值较大的情况下，能够较快地发现频繁项集。该算法的主要缺点是需要较多的内存来保存事务项集；另外，随着数据集的变大和设定的最小期望支持数变小，该算法很容易发生内存溢出。

2．动态数据流

针对不确定数据流中频繁项集挖掘，已有的算法主要基于UF-[112]-[114]，[116]，[119]，[124]Growth及滑动窗口技术或时间衰减窗口技术。[119]

Leung等提出两个基于滑动窗口的算法UF-streaming和SUF-Growth，每个滑动窗口包含固定批数的数据，当一个窗口满了以后，每来一批数据，都会先从窗口中删除一批最老的数据，然后再将新来数据添加到窗口中。[86]

算法UF-streaming采用FP-streaming的方法，预定义两个最小期望支持数preMinsup和minSup（preMinsup＜minSup），UF-streaming挖掘的频繁项集的支持数大于等于minSup，而支持数介于preMinsup和minSup之间的项集称为潜在频繁项集，也会和频繁项集一起保存到一棵树UF-stream上。该算法利用UF-Growth挖掘每批数据中的支持数大于等于preMinsup的项集作为候选项集，然后将每批数据中的候选项集保存到一个树UF-stream上，UF-stream树上每个节点记录窗口中每批数据的支持数（假设一个窗口中包含w批数据，则每个节点上需要记录w个支持数）；当新来一批数据中的候选项集被添加到UF-stream树上之前，会将树上最老批次数据对应的候选项集从树上删除；当一个节点上总的支持数（所有批上的支持数的和）大于等于minSup，则该节点到根节点对应的项集就是一个频繁项集。该算法是一个近似的挖掘算法，会丢失一部分频繁项集。

SUF-Growth算法主要基于算法UF-Growth，该算法将每批数据添加到树UF-Tree的时候，节点分别记录每批数据的支持数（假设一个窗口中包含w批数据，则每个节点上需要记录w个支持数）；当新来一批数据的时候，会首先将树上最老批次的数据删除；最老批次数据删除之后，则将新来数据添加到树上；挖掘频繁项集的时候从该树上读取数据，采用模式增长的方式挖掘频繁项集。

文献［113，114］中提出的算法采用的是时间衰减窗口模型，仍然采用UF-Tree来存储窗口中的事务项集。由于UF-Tree共享同一个节点时，不仅要求项相同，还要求项对应的概率值也相同，因此该树结构的存储需要大量的空间，同时也需要较多的处理时间。1.2.3　高效用项集挖掘算法的研究

传统数据集中频繁模式挖掘仅仅考虑了一个项集在多少个事务中出现，并没有考虑项集中各项的重要度、利润、价格和数量等效用值相关的信息，而效用值可以度量项集的成本、利润值或其他重要度等信息。例如，在传统数据集的购物单中，只考虑一个购物单中包含了哪些商品，而没有考虑一个购物单中每个商品的数量、价格或利润，然而在现实的很多应用中，购物单中商品的数量以及每种商品的单位利润都是很重要的。表1.3和表1.4是一个具有效用信息的数据集，该类数据中的高效用模式可以用来最大化一个企业的商业利润，这里称此类数据为带有效用的数据集。其中表1.3的前两列是一个包含7个事务的事务数据集，表1.4是各事务项的单位利润（效用）值；表1.3中的第三列tu（T）给出了每个事务的总效用值，后面三列则分别是iB、C、{BC}三个项集在每个事务上的效用值。下面给出静态和动态数据集上的高效用模式挖掘算法的研究现状。表1.3　高效用数据集实例表1.4　利润（外部效用值）表项利润项利润A10E3B3F1C1G1  D2

1．静态数据集

表1.5列出了一些高效用模式挖掘的主要算法。2004年，Yao等[126]首先提出了高效用项集挖掘的相应定义和数学模型：数据集D上ut一个项集X的效用值u（X），被定义为X在所有事务t上的效用值的总和，即，其中D是一个带有效ut用值的数据集、u（X，t）是项集X在事务t上的效用；它是一个项集的总的利润（总的效用值），例如：“牛奶”＋“面包”组合为所有的购物记录中所产生的利润的总和。高效用项集挖掘的目标，就是找出效用值u（X）高出用户预先设定的最小效用值的所有项集。

在文献［126］中Yao等还提出一种挖掘算法，该算法首先估计项集效用的期望值，然后用估计的期望值来判断一个项集是否是一个候选项集。但是，当用户设定的最小效用值比较低的时候，或者事务中包含比较多的事务项集的时候，该方法产生的候选项集个数接近于所有项的组合数。针对上述算法中产生大量候选项集的问题，在2006年，他们又在文献［127］中提出了两个新的算法：UMining和UMining_H。UMining算法采用效用值上限的剪枝策略来降低候选项集个数，UMining_H算法采用启发式的策略来降低候选项集的个数；同时这两个算法会失去一些高效用项集，并且产生的候选项集个数还是比较多。表1.5　高效用模式挖掘的主要算法

自Yao等提出高效用项集挖掘之后，高效用项集挖掘也成为一个[126][128]-[140]研究热点。2005年，Liu等提出了一个典型算法Two-Phase，同时作者还提出一个twu（transaction-weighted-utilization）模型，即一个项集的twu值不小于用户设定的最小效用值，该项集就是一个候选项集。该模型同时也满足向下封闭属性，即如果一个项集的twu值不小于用户设定的最小效用值，则该项集的任何非空子集的twu值也不小于用户设定的最小效用值；如果一个项集的twu值小于用户设定的最小效用值，则该项集的任何超集的twu值也小于用户设定的最小效用值。Two-Phase算法主要分为两步来完成：首先利用twu模型和Apriori算法，挖掘出所有的候选项集；再扫描一遍数据集来确定哪些候选项集是高效用项集。Two-Phase算法确实优于文献［126］中的方法，但是该算法包含了Apriori算法需要扫描多遍数据集的缺点；同时该方法也是通过候选项集来产生高效用项集，其时间效率仍然不是很理想。

为了解决已存在算法的低效率问题，特别是挖掘稠密数据集时的[137]低效率问题，2007年，Erwin等提出了一个基于树结构的高效用项集挖掘算法CTU-Mine。然而，该算法只是在挖掘稠密数据集或用户设定的最小效用值比较低的时候，性能才优于Two-Phase算法。[135]

2008年，Li等针对Two-Phase算法中产生过多候选项集的问题，提出了降低候选项集的策略IIDS（Isolated Items Discarding Strategy），并将提出的策略应用到已存在的层次挖掘算法中，分别得到两个新的算法FUM和DCG＋。这两个算法都优于它们原来的算法，但是这两个算法还是存在同样的问题：通过候选项集来挖掘高效[136]用项集。2007年，Hu等还提出一个近似的方法来挖掘高效用项集；[134]2011年，Lin等提出一个新算法HUP-Growth，该算法首先通过两遍数据集扫描，将事务项集维护在一棵类FP-Tree的树上，处理树上每一项的时候，需要产生包含该项的所有项集，同时需要计算这些项集的效用值，即可以从中确认真实的高效用项集；该算法的计算量比较大，但是该算法的时间效率优于算法Two-Phase。

以上提出的算法基本上都是通过多遍扫描数据集来产生候选项[132]集；2009年，Ahmed等提出一个不需要多次扫描数据集的算法IHUP。算法IHUP先将事务项集及效用信息存储在一棵IHUP-Tree上，这里以表1.3和表1.4的数据为例来描述算法IHUP，最小效用值（记为minUti）设为70。

该算法首先扫描一遍数据集，计算各项的twu值，删除twu值小于70的项，然后将剩余的项按twu值大小的逆序排序，如图1.3中左边的头表。创建好头表后，接下来就可以创建树，首先将事务项集按头表中项的顺序排序，同时删除不在头表中的项，计算修改后的事务项集的twu值，再将有序的项集添加到树上，同时将新计算到的twu值累加到该项集在树中的所有节点上。表1.3和表1.4中数据所对应的IHUP-Tree如图1.3所示。创建完树后，采用模式增长的方式从树上产生候选项集；最后再扫描一遍数据集从候选项集中识别出高效用项集。该算法的挖掘效率相对于已有的算法有很大的提高。图1.3　一棵IHUP-Tree（minUT＝70）

Tseng等在文献［130，131］中对算法IHUP进行改进，主要是针对建树方法的改进，进而得到算法UP-Growth。Tseng等考虑到处理树上每个节点的时候，子孙节点不再参与当前节点的处理过程，因此Tseng等人在将一个准备好的项集添加到树上，并在处理该项集中每一项的时候，只将该项及祖先项的效用值的和累加到该项在树上对应的节点上，如图1.4所示，当表1.3中第二个事务（B，2）（C，2）（E，1）（G，4）被添加到树上的时候，首先被处理的项集为“C：2，E：3，B：6”（其中的数值为各项在该事务中的效用值），当各项被添加到树上的时候，如项E对应的节点只将项C和E的效用值累加到该节点效用值上，项B对应的节点将这三项的效用值都累加到该节点效用值上，如图1.4的路径root-C-E-B所示。对比图1.3和图1.4，会发现后者树上很多节点的效用值降低了很多，从而在创建条件子树的时候，会有很多项排除在条件子树之外，即条件子树中节点也会减少，因此UP-Growth算法的效率比IHUP算法提高了很多。图1.4　一棵UP-Tree（minUT＝70）2[141]

算法DHUP采用项集枚举的方法挖掘高效用项集，该算法主要通过剪枝策略提高挖掘的时间效率，但是需要大量的空间来维护枚[133]举树和事务项集。HUI-Miner同Apriori算法采用层次方式产生高效用项集，每层中需要产生大量的项集，并计算每个项集的效用值；同时还需要维护每个项集所在事务ID、相应事务中的效用值和事务中其余项的效用值信息，因此该算法空间消耗较大。

2．动态数据流[138]，[139]

Tseng等提出了第一个数据流中高效用项集挖掘算法THUI，该算法整合了Two-Phase算法和滑动窗口的方式来挖掘数据流上的高效用项集，每个窗口中有固定批数的数据，每批数据又有固定个数的事务项集。该算法首先挖掘出窗口的第一批数据中的候选2项集，当第二批数据到来的时候，再挖掘出前二批数据中的候选2项集，依次挖掘出整个窗口中的候选2项集，用所有的候选2项集再产生全部的候选项集，最后还需要再扫描一遍数据集从候选项集中确认高效用项集。维护候选2项集的时候，还将每个候选项集产生的开始批次保存下来，当删除老数据的时候，只将候选项集的twu值减去该项集在最老批次数据中的twu值，同时将修改项集的开始批次增加1；当新来数据的时候，修改当前维护的候选项集的twu值，同时将新来批数据中新产生的候选项集添加到维护的候选项集集合中。该算法是一个近似算法，它的主要问题是需要产生并维护候选项集，并且还需要扫描数据集来统计每个候选项集的效用值，甚至有时候会产生大量的候选项集。[129]

Li等提出两个基于滑动窗口的算法：MHUI-BIT和MHUI-TID，这两个算法都采用类Apriori算法的特点逐层产生所有的候选项集，然后再扫描数据集来统计候选项集的效用值。算法MHUI-BIT和MHUI-TID分别采用bit-vector和TID-lists两个结构来存储当前窗口中每批数据，利用这两个结构能检索到与候选项集相关的事务，从而可以快速地统计候选项集的效用值，实验结果也验证了这两个算法的时间效率优于算法THUI。[140]

2010年，Ahmed等提出一个仍然基于滑动窗口的算法HUPMS，该算法采用树结构来维护窗口中每批数据的事务项集，通过一遍数据集扫描，将窗口中的事务项集维护在一棵树上，当新来一批数据的时候，先将最老数据从树上删除，再将新的数据添加到树上；当需要挖掘窗口中的高效用项集的时候，采用模式增长的方式从树上挖掘出所有的候选项集；最后再扫描一次数据集来统计所有候选项集的效用值。该算法相对算法MHUI-BIT和MHUI-TID，可以有效地减少候选项集的个数，实验也验证了该算法有比较好的时间性能。1.2.4　大数据集下的频繁模式挖掘研究

目前，针对大数据环境下的数据流频繁模式挖掘算法研究比较[142]少，主要集中在静态的大数据中研究。PFP是一个基于MapReduce的FP-Growth算法的实现，该算法需要两次MapReduce。首先，PFP算法利用MapReduce建立一个头表。第二次MapReduce，在Map过程中，每个事务项集都按头表的顺序排序，并且删除事务项集中不频繁的项，将有序事务项集中每项之前的项集（称为子事务项集）作为value值，该项作为key值输出，即如果一个事务项集中包含k项，则该事务项集会产生（k-1）个（key，value）键值对，即一个事务项集被分配给全局头表中多项来创建子树；在Reduce过程中，采用FP-Growth算法挖掘各项对应的子事务项集中的频繁项集。PFP算法的最大缺点是不能将数据均匀分配给各个节点，有的节点上数据量会很大，因此会影响到整体的时间效率。文献［143］针对云制造环境下数据挖掘的需求，提出了一种新的利用键值存储系统优化PFP-Growth算法。

Apriori算法的MapReduce实现的研究比较多，文献［144-151］中的算法都是基于MapReduce的Apriori实现的研究。已存在的基于Apriori的算法主要采用多次MapReduce来实现Apriori算法的并行算法，如果数据集中存在最大长度是k的频繁项集，则需要最少k次MapReduce。首先MapReduce一遍数据集产生频繁1-项集；然后用频繁1-项集组合产生候选2-项集，将候选2-项集分配到各个节点上，进行第二次MapReduce扫描数据集，统计各个候选项集在各个节点上支持数，在Reduce过程中再统计各个候选项集在全部数据集上的支持数，即可发现频繁2-项集；继续产生候选k-项集，进行k次MapReduce扫描数据集，从中发现频繁k项集（k≥3）。文献［151］中还提出三个算法FPC和DPC和SPC：FPC在每次迭代过程中，产生固定层次的候选项集，如产生k＋1，k＋2，…，k＋l的候选项集（l为某一固定值）；而算法DPC是对FPC的一个改进，在每次的迭代过程[151]中，将FPC中的l变为一动态值；算法SPC是每次迭代中只产生一层候选项集。通过实验分析，发现算法SPC和FPC的时间性能比较好，并且两算法的时间性能也比较接近，但是算法FPC在每次迭代中会产生过多候选项集，内存需求会比较多。

文献［147］提出了基于MapReduce的Apriori算法近似频繁项集挖掘算法PSON，通过两次MapReduce（第一次是挖掘每个节点上的局部频繁项集，然后合并所有节点上的局部频繁项集作为候选项集；第二次MapReduce，再扫描一遍数据集统计所有候选项集的支持数），即可从候选项集中发现所有支持数大于等于设定的最小支持数的频繁项集。该算法的问题就是输出的是＜key，1＞键值对，并且该算法挖掘的结果中会丢失部分频繁项集。第2章传统事务数据集中的频繁模式挖掘算法2.1　引言

传统数据集上的频繁模式挖掘算法已经得到深入的研究和广泛的应用，它也为不确定数据集中频繁模式挖掘和高效用模式挖掘奠定了基础，但是提高挖掘算法的时空效率仍然是研究的热点问题，在通过对已有算法分析研究的基础上，本章主要介绍一个基于滑动窗口的数据流的频繁模式挖掘算法。2.2　传统数据集中频繁模式挖掘的典型算法

传统数据集中的频繁模式挖掘算法不仅是对应数据流中频繁模式[111]，挖掘算法的基础，同时也是不确定数据集中频繁模式挖掘算法[115][127]，[120]-[122]，[125]-[132]和高效用模式挖掘算法的基础，同时在序列[152][73]-[155]，[156]-[159]模式挖掘、事务间的频繁项集挖掘、异常检测、分[157][164]，[160]-[163]类和聚类算法中得到应用。

本节主要详细描述几个传统数据集中典型的频繁模式挖掘算法。2.2.1　Apriori算法

Apriori算法是一个典型的逐层挖掘算法，后继的很多逐层挖掘算法都是基于Apriori算法的改进。以Apriori算法为例说明逐层挖掘的算法步骤：①扫描一遍数据集，找出所有频繁1-项集。②用任两个频繁1-项集组合产生所有的候选2-项集，再扫描一遍数据集统计候选项集中每个项集的支持数，从中找出所有的频繁2-项集。③用频繁2-项集组合产生候选3-项集，要求组合的两个2-项集中有一个元素（项）相同；如果产生的3-项集的子集中存在长度为2的项集不是频繁2-项集，则该3-项集就不是一个候选项集；候选项集产生以后，再扫描一遍数据集统计候选3-项集中每个项集的支持数，从中找出所有的频繁3-项集。④同③中方法，逐次挖掘出频繁k-项集（k≥4），直到没有新的频繁项集产生为止。

算法Apriori的主要缺点是需要多次扫描数据集来统计候选项集的支持数，如果产生的最长频繁项集的长度是k，则算法需要k或k＋1次数据集扫描；如果用户预定义的最小阈值比较小或者数据集比较大，则候选项集就会很多，因此该类算法的效率会受到很大的影响。2.2.2　FP-Growth算法

FP-Growth算法是一个典型的模式增长算法，并且也是第一个模式增长算法，后继的很多模式增长算法都是基于该算法进行改进。FP-Growth算法相对Apriori算法，在很多情况下（如用户预定义最小阈值比较低、数据集包含的项比较多或者数据集中包含的长事务项集比较多等），FP-Growth算法的效率得到了很大的提高。以表2.1中数据集为例说明FP-Growth算法的挖掘步骤（这里设定用户预定义的最小支持数为3）。表2.1　一个传统事务数据集实例事务事务项集ta，c，d1tb，d2t3a，b，c，dta，b，c4ta5ta，c6ta，b，d7t8a，b，c，dta，c9

步骤1　扫描一遍数据集，统计各项的支持数，并将支持数大于等于最小支持数的项按支持数从大到小保存到一个头表H中，图2.1（a）为实例中数据统计的头表H（其中头表中的link字段存储每项在树上的所有节点指针；还有另外一种处理方法，只将每个项在树上的第一个节点保存在link中，下一个同名节点的指针依次保存在上一个节点中）。图2.1　FP-Tree的构建实例

步骤2　再次扫描数据集，将数据集中的所有事务项集添加到一棵树上，首先删除事务项集中不频繁的项（不在头表中的项都是不频繁的），事务项集中剩余项按头表的顺序添加到树上，对应的每个节点支持数都增加1。图2.1（b）是表2.1中第一个事务项集添加到树上后的结果，同时也将新建的节点指针保存到头表对应项的link中，节点上数字表示该节点的支持数；图2.1（c）是前两个事务项集添加到树上后的结果；当第三个事务项集{a，b，c，d}往树上添加的时候，由于可以和路径root-a-c-d共享节点a和c，所以只需将已存在的两个节点的支持数增加1，然后将剩余的项依次添加到节点c的子孙中，图2.1（d）是前三个事务项集添加到树上后的结果；图2.1（e）是所有事务项集添加到树上后的结果（为了能使FP-Tree看起来清晰，图2.1（e）中没有标识头表中link的信息）。

步骤3　从头表H的最后一项开始依次处理每一项，如头表H中的最后一项d，首先将该项添加到初始值为空的基项集base-itemset中，即base-itemset＝{d}；从头表H中的link信息中可以找到项d在FP-Tree上的所有节点，扫描每个节点d到根节点路径，统计出现的所有项及项的支持数，其中同一路径上所有项的支持数都为该路径上节点d的支持数，将统计的结果保存到同头表H结构相同的一个新头表subH（该头表也称为子头表），同样该子头表中仅仅保存支持数大d于等于最小支持数3的项，同时头表中所有项按支持数从小到大排序，新创建的头表subH如图2.2（a）所示；再次扫描所有节点d到根节点d的路径，将路径上的所有项按子头表subH的顺序排序，同时删除不d在子头表中的项，然后将有序的项集和支持数（所有项的支持数都等于节点d的支持数）添加到一棵子树subH（该树也称为当前基项集d{d}的条件子树，简称子树），如图2.2（b）所示；按照以上处理方法递归处理子头表subH和子树subT，分别能得到两个新的基项集{dc}、dd{dca}、{db}、{dba}和{da}，图2.2（c）是项集{dc}的子树和子头表。图2.2　子（条件）FP-Tree和子头表

步骤4　从当前基项集base-itemset中删除当前处理的项。

步骤5　继续处理当前被处理头表的下一项。

FP-Growth算法的步骤可以简述如下：

步骤1　扫描数据集，创建头表H，如图2.1（a）中头表。

步骤2　扫描数据集，创建FP-Tree，如图2.1（e）中的FP-Tree。

步骤3　依次处理头表H中所有项（从最后一项开始，假设当前处理的项为Q）：

步骤3.1　将当前处理项Q添加到一个初始值为空的基项集（每新产生一个基项集，即为一个新频繁项集）。

步骤3.2　扫描FP-Tree上所有节点Q到根节点路径，构建一个子头表subH，构建子头表的具体方法如上例中子头表subH的构建Qd（图2.2（a））。

步骤3.3　如果子头表subH不为空，则为基项集构建一棵条件Q子树subT，具体构建方法如上例中条件子树subT的构建，否则执Qd行步骤4。

步骤3.4　按照处理头表H的方法，递归处理子头表subH和子树QsubT。d

步骤4　将当前处理的项从基项集中删除。

步骤5　处理当前处理头表的下一项。2.2.3　COFI算法

COFI算法同FP-Growth一样，通过两遍数据集的扫描，创建一个头表H和一棵FP-Tree。接下来，就不像FP-Growth那样递归处理建好的树和头表，COFI是通过为头表中每一项构建一棵COFI-Tree来挖掘包含该项的所有频繁项集，下面以表2.1的数据为例来说明COFI算法的挖掘步骤。

步骤1　通过两遍数据集的扫描，构建了头表H和FP-Tree，如图2.3（a）、（b）所示，这里的头表和FP-Tree同图2.1（a）、（e）中的相同。

步骤2　从头表H的最后一项开始依次处理每项，扫描图2.3（b）中所有节点d到根节点root路径，统计出现项的支持数，得到图2.3（c）中的头表subH。d

步骤3　如果头表subH不为空，按如下的子步骤创建一棵以d为d根的COFI-Tree；否则执行步骤5。

步骤3.1　扫描图2.3（b）中所有节点d到根节点root的路径，将每个路径上所有项取出来（路径上取出的所有项记为项集X）。

步骤3.2　将项集X中不频繁的项（不在头表subH中的项）删d除。

步骤3.3　按头表subH的顺序排列项集X中所有的项。d

步骤3.4　将有序的项集X添加到一棵以d为根的COFI-Tree上。

按步骤3.1～3.3处理完所有包含节点d的路径后，得到4个项集：{a，c}、{b，a}、{b，a，c}和{b}，前3个的支持数都为1，最后一个是2；用这4个有序的项集所创建的以d为根的COFI-Tree，如图2.3（c）的树subT所示，树上每个节点记录2个数值：一个是节点的总支持数，d一个是节点参与支持数（该支持数是在挖掘过程中使用，初始值为0）。图2.3　COFI算法的挖掘实例

步骤4　挖掘以d为根的COFI-Tree，挖掘的步骤如下：

步骤4.1　依次处理头表subH中的每一项，从头表的最后一项cd开始处理，树subT上有两个路径上包含节点c，依次处理每个路径：d①将第一个路径d-a-b-c上的所有节点的参与支持数（节点上记录的第二个数）增加2（2是该路径上节点c的支持数），如图2.3（d）上的路径d-a-b-c所示，同时取出路径上所有项，即ab和c；②用这些项组合产生了一个项集的集合CS，该集合中每个项集的支持数都为节点c的支持数，即CS＝{a：2，ab：2，ac：2，abc：2，b：2，bc：2，c：2}；③将项d添加到该集合的每个元素中，CS＝{ad：2，abd：2，acd：2，abcd：2，bd：2，bcd：2，cd：2}。

步骤4.2　依次处理包含节点c的另外一路径d-a-c：①将该路径上所有节点的参与支持数都增加1（1是该路径上节点c的支持数），如图2.3（e）上的路径d-a-c所示，同时取出该路径上所有项a和c；②用这些项组合产生了一个项集的集合CS0，该集合中每个项集的支持数都为节点c的支持数，即CS0＝{a：1，ac：1，c：1}；③将项d添加到该集合的每个元素中，CS0＝{ad：1，acd：1，cd：1}；④将CS0中每个元素合并到CS中，如果元素存在，则将对应元素（项集）的支持数累加到CS相应的元素中，合并后的CS＝{ad：3，abd：2，acd：3，abcd：2，bd：2，bcd：2，cd：3}。

步骤4.3　依次处理头表subH的第二项b，树subT上有两个路径dd上包含节点b，依次处理这两个路径：①在第一个路径d-a-b上，节点b的支持数和参与支持数之差是1，即大于0，所以可以进一步对该路径进行处理；②将该路径上所有节点的参与支持数都增加1（1是该路径上节点b的支持数和参与支持数之差），如图2.3（f）上的路径d-a-b，同时取出该路径上项a和b；③用这些项组合产生了一个项集的集合CS0，每个项集的支持数都为节点b的支持数和参与支持数之差，即CS0＝{a：1，ab：1，b：1}；④将项d添加到该集合的每个元素中，CS0＝{ad：1，abd：1，bd：1}；⑤将CS0中每个元素合并到CS中，如果元素存在，则将对应元素（项集）的支持数累加到CS相应的元素中，合并后的CS＝{ad：4，abd：3，acd：3，abcd：2，bd：3，bcd：2，cd：3}。

步骤4.4　处理包含节点b的第二个路径d-b，节点b的支持数和参与支持数的差是1，大于0，所以可以进一步对该路径进行处理：①将该路径上所有节点的参与支持数都增加1（1是该路径上节点b的支持数和参与支持数之差），如图2.3（f）上的路径d-b，同时取出该路径上项b；②用这些项组合产生了一个项集的集合CS0，每个项集的支持数都为节点b的支持数和参与支持数之差，即CS0＝{b：1}；③将项d添加到该集合的每个元素中，CS0＝{bd：1}；④将CS0中每个元素合并到CS中，如果元素存在，则将对应元素（项集）的支持数累加到CS相应的元素中，合并后的CS＝{ad：4，abd：3，acd：3，abcd：2，bd：4，bcd：2，cd：3}。

步骤4.5　按照步骤4.3和步骤4.4的方法处理头表H中下一项a，d处理完之后，树T如图2.3（g）所示，CS＝{ad：4，abd：3，acd：d3，abcd：2，bd：3，bcd：2，cd：3}。

步骤4.6　直到处理完subH中的所有项之后，将CS中支持数大d于等于3的项集添加到频繁项集FI中，清空项集CS。

步骤5　回到步骤2处理头表H中的下一项，直到处理完所有项为止。

试读结束[说明：试读内容隐藏了图片]

下载完整电子书