《数据挖掘期中论文》由会员分享，可在线阅读，更多相关《数据挖掘期中论文（7页珍藏版）》请在金锄头文库上搜索。
1、课程设计报告( 2013-2014 年度第二学期)名 称： 数据仓库与挖掘论文院 系： 经济管理系 班 级： 信管 1101 学生姓名： 聂麟鹏 学 号： 201106040110 指导教师： 王立军 日期：2014 年 6 月温磊老师在数据仓库与挖掘的课程中，为我们详细的讲述了关联规则的挖掘，并且介绍了两个算法，一种是 Apriori 算法，另一种是 FPTree 算法，并且做了一系列的习题，经过了温磊老师的讲解后，我们通过算法对关联规则有了更深一步的了解，为了加深我们的印象，老师让我们在课下收集关于关联规则的其他算法，下面我将对几种其他的书中没有介绍过的算法进行详细的讲述。1、 数据集划分
2、算法Savasere 设计了一个基于划分的算法。这个算法先把数据库从逻辑上分成几个互不相交的块，每次单独考虑一个分块并对它生成所有的频集，然后把产生的频集合并，用来生成所有可能的频集，最后计算这些项集的支持度。这里分块的大小选择要使得每个分块可以被放入主存，每个阶段只需被扫描一次。而算法的正确性是由每一个可能的频集至少在某一个分块中是频集保证的。该算法是可以高度并行的，可以把每一分块分别分配给某一个处理器生成频集。产生频集的每一个循环结束后，处理器之间进行通信来产生全局的候选 k-项集。通常这里的通信过程是算法执行时间的主要瓶颈；而另一方面，每个独立的处理器生成频集的时间也是一个瓶颈。2、采样
3、算法采样算法包括由 Park 等人提出的可调精度的挖掘算法、Toivonen 提出的 Sampling 算法等。Sampling 算法是从数据库 D 中随机抽取一个可以调入内存的数据库子集 D，然后求出数据库子集D中可能在数据库 D 中成立的所有规则，再用数据库 D 中剩余部分（D-D）来验证结果的正确性。它适用于挖掘准确性不太高而挖掘效率较高的环境。采样算法很大程度上减少了扫描数据库的时间开销，但它最大的缺点就是可能产生数据扭曲导致结果不精确。如果频繁项集包含了数据库 D 中的所有频繁项集，则只需要扫描一次 D。否则，为了减少这个问题带来的影响，可以使用更小的支持度阈值在随机样本上做第二次扫
4、描数据库再次产生频繁项集，找出在第一次扫描中遗漏的频繁项集。通过对数据库多次扫描来减少频繁项集的遗漏。对于数据扭曲现象，有人讨论了反扭曲算法来挖掘关联规则，可以使得扫描数据集的次数少于 2 次。3、增量式更新算法增量式更新算法是利用已挖掘的关联规则在变化了的数据库或参数上发现新的关联规则、删除过时的关联规则来维护数据集更新的问题。目前大多数的增量式更新算法都是以 Apriori 算法为核心进行的改进与演化，包括 D.W.Cheung 等人提出的 FUP 和 FUP2 算法，冯玉才等人提出的 IUA 和PIUA 算法，高峰等人提出的 IUAR 算法等等。FUP 算法是 Apriori 算法的改进
5、，也是解决增量更新问题的一种经典算法。FUP 算法主要是针对在最小支持度和最小置信度不变的情况下，数据库 DB 被添加、删除或修改时，如何生成更新后的数据库的关联规则。它利用已挖掘得到的频繁项集信息来避免重复计算频繁项集支持数的时间开销来提高算法效率。FUP2 算法同时考虑到增加数据库和修改、删除数据库的情况，比较适用于大量的增加数据库和少量的删除数据库的情况。IUA、PIUA 算法都是主要考虑在最小支持度和最小置信度发生变化而数据库 DB 不变时，如何生成 DB 中的关联规则。IUAR 算法主要考虑在最小支持度和最小置信度和数据库 DB 同时发生变化时，如何生成更新后的关联规则。4、并行挖掘
6、算法并行算法是利用同时执行的诸过程的集合相互作用和协调完成对给定问题的求解。包括Agrawal 等人提出的 CD、DD、CaD 算法，Park 等人提出的 PDM 算法，Cheung 等人提出的 DMA 和 FDM算法等。CD 算法运行在空闲的处理器上进行并行冗余计算以减小通信量，速度几乎可以达到线性加速比的速度。但它的缺点是通信量和候选频繁项集都比较大。DD 算法通过吧候选集划分到各个处理器来克服 CD 算法的缺陷，然而 DD 算法由于数据移动方案效率较低导致通信负载较大、处理器件的交互模式易倒是处理器处于空闲状态、每一笔交易记录都根据多个哈希树进行处理导致冗余计算等缺点。CaD 算法师徒通
7、过划分数据库和候选集的办法来减少处理器之间的数据依赖性，使每个处理器可以独立地进行计算。但它在划分候选集时要对整个的事务数据库进行划分并分配到每一个处理器节点中，从而消耗了大量的时间用于通信。PDM 算法类似于 CD 算法，所有处理器含有相同的杂凑表和候选集。并行候选集生成的过程是通过每个处理器生成一个候选子项集，然后交换所有处理器上的子项集，然后交换所有处理器上的子项集生成全局候选集来实现。但是 PDM 算法对非大项集的项目和事务的物理剪枝要涉及大量磁盘的 I/O 操作。简单的介绍了四种算法后，下面我引用例子对增量式更新算法和并行挖掘算法进行详细的介绍。例1：设I =il，i2，im是m个不
8、同项目的集合.给定事务数据库D，对于项目集XI在D中的支持数是指D中包含X的事务数，记为X.countD. X在D中的支持度是指 D中包含X事务的百分比，记为X .supD . 如果X的支持度不小于用户给定的最小支持度阈值s，则称X 为频繁项目集，如果 X 包含I个项目，那么又称X为频繁I-项目集，频繁l-项目集简称频繁项目.挖掘出所有频繁项目集是关联规则挖掘的核心问题，占据整个计算量的大部分。给定事务数据库D，事务数据集dl及d2 （ d2cD）.针对实际应用需求，关联规则的更新问题可以分为如下两种情况：（l）最小支持度s 发生变化后如何生成D 中的频繁项目集；（ 2）事务数据库D 发生变化
9、后如何生成最新事务数据库D + dl - d2中的频繁项目集.最小支持度S发生变化后关联规则增量式更新算法FIUA1：设旧的最小支持度为s，Ll为D 中频繁项目的集合，L 为D 中频繁项目集的集合. 同样地，对于新的最小支持度s，Ll为D 中频繁项目的集合，L为D中频繁项目集的集合. 当最小支持度发生改变时，可分为两种情况：（l）s s；（2）s s输入：支持度为s 时D 中的所有频繁项目集L和FP-tree，新的支持度s .输出：支持度为s时D 中的所有频繁项目集L和FP-tree .if（ Ln1）then调用AdjUstFP-tree(FP-tree，Ln1）得到FP-tree；调用FP
10、-growth（FP-tree，null，0，Ln1，L1）；/ / 求Ln调用FP- growth（FP-tree，null，1，L1，Ln1）；/ / 求LOL = L U LnU LO事务数据库发生变化后关联规则的更新算法FIUA2：本节仅考虑当最小支持度不变，一个事务数据集d添加到事务数据库D中去时，如何生成事务数据库DUd中的频繁项目集. 对此，我们将其分解为以下两个子问题：（1）找出D 中不再生效或仍然生效的频繁项目集；（2）找出DUd 中新的频繁项目集. 对于前者，只需扫描d一次即可，由于D中的频繁项目集和d均较小，因此其运算量也较小，故下面的工作主要集中在第2个子问题上，即找出
11、所有新的频繁项目集。基本步骤：1、求d中的候选强频繁k-项目集Cdk；2、求候选新频繁k-项目集Cnk；3、求出Cnk中各项目集在D中的支持数；4、确定DUd 中的所有新频繁k-项目集Lnk。一般情况下，经过1，2步的处理后，Cnk中项目集的个数是较少的，因此如何有效地利用已有的一切信息来求Cnk中各项目集在D 中的支持数将是更新算法FIUA2的核心问题.对于D 中的任何一条事务t，设t1 = tL1，t2 =tLn1，显然，t1t2 = . 由FP-tree 的构造原理可知，t1中的各项目必将同时出现在FP-tree 的某唯一条路径p上，因此如果能将t2中的各项目添加到FP-tree的路径p
12、上，那么t 中的频繁项目将映射到FPtree的某唯一条路径上. 由于Ln1中各项目在D 中的支持度均小于L1中任意项目的支持度，因此直接调用AdjustFP-tree（FP-tree，Ln1）即可实现此功能，设调整后的模式树为P-tree，项目头表为Htable1：q，其中q= I L1 I + I Ln1 I . 由此可见，求项目集在D中的支持数可以转换成求P-tree 中包含此项目集的路径数，从而得到求Cnk在D 中的支持数算法，算法描述如下：Procedure computercount（ P-tree，）/=1，2，p按其支持数降序排列搜索项目头表Htable1：g的项目名称域item
13、-name，假设Htableq1.item-name =p；根据Htableq1. head 找到P-tree 中节点名称为p的节点nd1，nd2，ndh；根据nd1，nd2，ndh及其前缀节点的父节点指针域找到包含p的所有路径P1，P2，Ph；for（ i = 1；ih；i + + ）do如果路径Pi,包含，那么的支持数增加ndi . count输入：事务数据库D 及其所有频繁项目集L；事务数据集d；最小支持度S；输出：事务数据库DUd 中的所有频繁项目集LDd .扫描d求D中的强频繁项目集LD并求出d 中的强频繁1-项目集Ld1及 Ln1；调用AdjustFP- tree（FP-tree，
14、Ln1）得到模式树P-tree；Cd2 = Apriori- gen（Lfd1）；for（ k = 2；Cd；k+）do扫描d求Cdk中各项目集在d 中的支持数并删除d中的非频繁项目集得到Cdk；Cnk = Cdk - Lk；if（Cn）thenfor each=1，2，tCnk调用 computercount（ P-tree，）；Ldk =cCdk|c.SupDdS ；Cd（ k+1）= Apriori- gen（ Ldk）；Lnk =cCnk|c .SupDdS；/ / Lnk为新频繁k-项目集LDd = LnkLD并行算法PFP-growth算法1、 全局频繁项产生首先将事务数据集分配给
15、各个可利用的处理机。每个处理机读取和分析大致相同数量的数据。设处理机的个数为p，结果所有数据被均匀划分为p等份。每个处理机对分配到的事务进行读取和分析，统计局部频繁项（local frequent item）。设全局频繁阈值为，则局部频繁阈值设为local=/p。这个过程如表1所示。表1 事务数据分配TID Transaction Processors1 A B C D E2 F B D E G3 B D A E GProcessor 04 A B F G D5 B F D G K6 A B F G DProcessor 17 A R M K O8 A F G A D9 A B F M OProcessor 2 当局部频繁项产生后，各处理机将局部频繁项表示为一字符串。例如对processor 0，它将频繁项表示为“A:2|B:3|C:1|D:3|E:3|F:1|”。按照图1所示的数据传输策略，一些处理机将自己的字符串传给另外一些处理机。当一个处理机收到从另外处理机发过来的频繁项字符串后，将收到的字符串和自身的字符串合并为一个字符串作为自己的字符串，并按图1所示策略继续传给另外的处理机。对 processor 0，它收到processor 1 发给它的字符串“A:2|B:3|D:3|F:3|G:3|K:1|”。并将这个收到的字符串与自己的串“A:2|B:3|C:1|D:3|E:3|
