关联规则挖掘算法综述

时间：2011-04-24 作者：秩名

2)基于散列的技术
散列表具有不同的桶，每个桶有个地址，在扫描D时对每个事务产生其所有的k项集，然后根据散列函数计算每个k项集的地址，并把齐放入相应的桶中，相应的桶技术加1，对所有的事务作完后，计数小于

的桶中的k项集则不可能是频繁的k项集，可把它从候选集中删除。
3)事务压缩：压缩进一步迭代扫描事务集
根据：不包含任何k项集的事务是不可能包含任务（k+1）项集，可把这些事务加上标记，扫描时不扫描它们。
4)基于hash的方法：
通过实验可以发现寻找频繁集主要的计算是在生成频繁2-项集Lk上，Park等就是利用了这个性质引入hash技术来改进产生频繁2-项集的方法。论文格式。
5)基于采样的方法
基本思想是在给定数据的一个子集挖掘。对前一遍扫描得到的信息，仔细地组合分析，可以得到一个改进的算法，Mannila等先考虑了这一点，他们认为采样是发现规则的一个有效途径。随后又由Toivonen进一步发展了这个思想，先使用从数据库中抽取出来的采样得到一些在整个数据库中可能成立的规则，然后对数据库的剩余部分验证这个结果。Toivonen的算法相当简单并显著地减少了I/O代价，但是一个很大的缺点就是产生的结果不精确，即存在所谓的数据扭曲(data skew)。分布在同一页面上的数据时常是高度相关的，可能不能表示整个数据库中模式的分布，由此而导致的是采样5%的交易数据所花费的代价可能同扫描一遍数据库相近。
6)动态项集计数
Brin等人给出该算法。动态项集计数技术将数据库划分为标记开始点的块。不象Apriori仅在每次完整的数据库扫描之前确定新的候选，在这种变形中，可以在任何开始点添加新的候选项集。该技术动态地评估以被计数的所有项集的支持度，如果一个项集的所有子集以被确定为频繁的，则添加它作为新的候选。结果算法需要的数据库扫描比Apriori 少。
7)FA(Fast Apriori)算法：
在计算频繁项集的同时记录包含在频繁集中相应事务TID，每次计算

支持度时对不包含在

中的各事务直接删除，不必进行支持度计算，同时删除不包含

中的任何项的事务，在以后的支持度计算中不加考虑，这样计算候选项集支持度所涉及的记录数目将小于事务数据库中的原记录数目，提高了整个算法的效率。
3、Apriori算法的缺陷：
1)算法可能会产生大量的候选集；
2)算法必须多次重复扫描数据库，对候选集进行模式匹配，因此效率低下。
（二）、FP-growth算法：不产生候选集挖掘频繁项集
1、FP-growth算法步骤
1)扫描事务集D找出频繁1项集，并按支持度降序排序，记作：L；
2)创建FP树的根节点，用“null”标记；
3)对每个事务创建一个分支，按L中的次序处理每个项：第一项连接到根，第二项作为第一项的孩子，第三项作为第二项的孩子，如此下去，每个节点计数为1，若树中有此分支的前若干项，则将这几项合并。
4)从L的最后一项l开始，构造l的条件模式基，即FP树种l出现的分支上l前的项的集合，这些分支构成FP条件树；
5)将l与FP树中的项连接，以产生频繁项集。
2、FP-growth算法的优点：
对于挖掘长的和短的频繁模式，他都是有效的和可伸缩的，并且大约比Apriori算法快一个数量级。
（三）、其他挖掘频繁项集的算法
Apriori算法得出的关系都是频繁出现的，但是在实际的应用中，我们可能需要寻找一些高度相关的元素，即使这些元素不是频繁出现的。在apriori算法中，起决定作用的是支持度，而我们现在将把可信度放在第一位，挖掘一些具有非常高可信度的规则。整个算法基本上分成三个步骤：计算特征、生成候选集、过滤候选集。在三个步骤中，关键的地方就是在计算特征时Hash方法的使用。在考虑方法的时候，有几个衡量好坏的指数：时空效率、错误率和遗漏率。基本的方法有两类Min_Hashing(MH),Locality_Sensitive_Hashing(LSH):
Min_Hashing的基本想法是：将一条记录中的头k个为1的字段的位置作为一个Hash函数。
Locality_Sentitive_Hashing的基本想法是：将整个数据库用一种基于概率的方法进行分类，使得相似的列在一起的可能性更大，不相似的列在一起的可能性较小。我们再对这两个方法比较一下。
MH的遗漏率为零，错误率可以由k严格控制，但是时空效率相对的较差。LSH的遗漏率和错误率是无法同时降低的，但是它的时空效率却相对的好很多。所以应该视具体的情况而定。这种方法能产生一些有用的规则。
(四)、多层和多维关联规则的挖掘
1、多层关联规则：
对于很多的应用来说，由于数据分布的分散性，所以很难在数据最细节的层次上发现一些强关联规则。当我们引入概念层次后，就可以在较高的层次上进行挖掘。虽然较高层次上得出的规则可能是更普通的信息，但是对于一个用户来说是普通的信息，对于另一个用户却未必如此。所以数据挖掘应该提供这样一种在多个层次上进行挖掘的功能。
1)分类：
根据规则中涉及到的层次，多层关联规则可以分为同层和层间关联规则。
2)挖掘方法：
多层关联规则的挖掘基本上可以沿用“支持度-可信度”的框架。一般可采用自顶向下策略，由概念层1开始向下，到较低的更特定的概念层，在每个概念层累加计数计算频繁项集，如此下去。对每一层可以使用发现频繁项集的任何算法，Apriori或它的变形。只不过，在支持度设置的问题上有一些要考虑的东西。
同层关联规则可以采用两种支持度策略：
①统一的最小支持度。对于不同的层次，都使用同一个最小支持度阈值。
这样对于用户和算法实现来说都比较的容易，但是弊端也是显然的：较低层次抽象地项不大可能像较高层次抽象的项出现得那么频繁。如果最小支持度阈值设置太高，可能丢掉出现在较低抽象层中有意义的关联规则。如果设置太低，可能会产生出现在较高抽象层的无兴趣的关联规则。

2/3 首页上一页 1 2 3 下一页尾页

查看相关论文专题：

	加入收藏打印本文
上一篇论文：高校网络教学资源平台建设的探究
下一篇论文：关于海航装备信息管理信息化的思考

科技论文分类

相关计算机论文

无相关信息

最新计算机论文

读者推荐的计算机论文