数据挖掘期中论文.doc

课程设计报告 ( 2013--2014 年度第二学期) 名 称： 数据仓库与挖掘论文 院 系： 经济管理系 班 级： 信管1101 学生姓名： 聂麟鹏 学 号： 201106040110 指导教师： 王立军 日期：2014年6月 温磊老师在数据仓库与挖掘的课程中，为我们详细的讲述了关联规则的挖掘，并且介绍了两个算法，一种是Apriori算法，另一种是FP—Tree算法，并且做了一系列的习题，经过了温磊老师的讲解后，我们通过算法对关联规则有了更深一步的了解，为了加深我们的印象，老师让我们在课下收集关于关联规则的其他算法，下面我将对几种其他的书中没有介绍过的算法进行详细的讲述。 数据集划分算法 Savasere设计了一个基于划分的算法。这个算法先把数据库从逻辑上分成几个互不相交的块，每次单独考虑一个分块并对它生成所有的频集，然后把产生的频集合并，用来生成所有可能的频集，最后计算这些项集的支持度。这里分块的大小选择要使得每个分块可以被放入主存，每个阶段只需被扫描一次。而算法的正确性是由每一个可能的频集至少在某一个分块中是频集保证的。该算法是可以高度并行的，可以把每一分块分别分配给某一个处理器生成频集。产生频集的每一个循环结束后，处理器之间进行通信来产生全局的候选k-项集。通常这里的通信过程是算法执’，然后求出数据库子集D’中可能在数据库D中成立的所有规则，再用数据库D中剩余部分（D-D’）来验证结果的正确性。它适用于挖掘准确性不太高而挖掘效率较高的环境。采样算法很大程度上减少了扫描数据库的时间开销，但它最大的缺点就是可能产生数据扭曲导致结果不精确。如果频繁项集包含了数据库D中的所有频繁项集，则只需要扫描一次D。否则，为了减少这个问题带来的影响，可以使用更小的支持度阈值在随机样本上做第二次扫描数据库再次产生频繁项集，找出在第一次扫描中遗漏的频繁项集。通过对数据库多次扫描来减少频繁项集的遗漏。对于数据扭曲现象，有人讨论了反扭曲算法来挖掘关联规则，可以使得扫描数据集的次数少于2次。 3、增量式更新算法 增量式更新算法是利用已挖掘的关联规则在变化了的数据库或参数上发现新的关联规则、删除过时的关联规则来维护数据集更新的问题。目前大多数的增量式更新算法都是以Apriori算法为核心进行的改进与演化，包括D.W.Cheung等人提出的FUP和FUP2算法，冯玉才等人提出的IUA和PIUA算法，高峰等人提出的IUAR算法等等。 FUP算法是Apriori算法的改进，也是解决增量更新问题的一种经典算法。FUP算法主要是针对在最小支持度和最小置信度不变的情况下，数据库DB被添加、删除或修改时，如何生成更新后的数据库的关联规则。它利用已挖掘得到的频繁项集信息来避免重复计算频繁项集支持数的时间开销来提高算法效率。FUP2算法同时考虑到增加数据库和修改、删除数据库的情况，比较适用于大量的增加数据库和少量的删除数据库的情况。 IUA、PIUA算法都是主要考虑在最小支持度和最小置信度发生变化而数据库DB不变时，如何生成DB中的关联规则。 IUAR算法主要考虑在最小支持度和最小置信度和数据库DB同时发生变化时，如何生成更新后的关联规则。 4、并行挖掘算法 并行算法是利用同时执行的诸过程的集合相互作用和协调完成对给定问题的求解。包括Agrawal等人提出的CD、DD、CaD算法，Park等人提出的PDM算法，Cheung等人提出的DMA和FDM算法等。 CD算法运行在空闲的处理器上进行并行冗余计算以减小通信量，速度几乎可以达到线性加速比的速度。但它的缺点是通信量和候选频繁项集都比较大。 DD算法通过吧候选集划分到各个处理器来克服CD算法的缺陷，然而DD算法由于数据移动方案效率较低导致通信负载较大、处理器件的交互模式易倒是处理器处于空闲状态、每一笔交易记录都根据多个哈希树进行处理导致冗余计算等缺点。 CaD算法师徒通过划分数据库和候选集的办法来减少处理器之间的数据依赖性，使每个处理器可以独立地进行计算。但它在划分候选集时要对整个的事务数据库进行划分并分配到每一个处理器节点中，从而消耗了大量的时间用于通信。 PDM算法类似于CD算法，所有处理器含有相同的杂凑表和候选集。并行候选集生成的过程是通过每个处理器生成一个候选子项集，然后交换所有处理器上的子项集，然后交换所有处理器上的子项集生成全局候选集来实现。但是PDM算法对非大项集的项目和事务的物理剪枝要涉及大量磁盘的I/