你的位置:首页 > 软件开发 > 数据库 > apriori算法的简介和改进总结

apriori算法的简介和改进总结

发布时间:2016-03-27 10:00:11
apriori算法的简介:利用的相关性质:频繁项集 的非空子集也必须是频繁项集非频繁项集的任一超集也必然不是频繁项集如果K-维频繁项集集合中包含单个项目i的个数小于K-1,则i不可能在频繁K项集中(apriori算法中并没有用到这个性质,可以借助这个性质来进行优化,性质会在后面举 ...
    1. apriori算法的简介:
      1. 利用的相关性质:
        • 频繁项集 的非空子集也必须是频繁项集
        • 非频繁项集的任一超集也必然不是频繁项集
        • 如果K-维频繁项集集合中包含单个项目i的个数小于K-1,则i不可能在频繁K项集中(apriori算法中并没有用到这个性质,可以借助这个性质来进行优化,性质会在后面举例)
      2. 算法的主要思想是:
        1. 第一步,通过迭代,检索出食物数据库给中所有的频繁项集,主要依据用户设定的最小支持度的阈值
        2. 第二步,用频繁项集构造出满足用户最小信任度的关联规则。其中第一步是占算法的主要计算部分,我们也主要研究的是第一步。
      3. 迭代过程主要分为连接和剪枝两个步骤:(由k-1维项集产生K维项集
        1. 连接:两个项集的前K-2项相同,最后的K-1项不同,则连接产生的K维项集就是前K-2项加上两个项集中不同的项
        2. 剪枝:利用性质一和性质二:如果新产生的项集有存在一个子集不在K-1维的频繁项集中,则删掉该新产生的项集
      4. 算法的伪代码apriori算法的简介和改进总结在第三步产生新的项集之后,需要统计每个项集的频度,主要采取的算法是,对数据库中的每个条目,遍历一遍候选项集,对每个包含该条目的候选项集计数加一。这样的话需要重新扫描一遍数据库,产生大量的计算
    2. 算法的问题:
      1. 在计算项目集 的支持度时需要对数据库的全部记录进行一遍扫描比较,一般情况下数据库的规模会很庞大,这样会极大的增加系统的I/O开销。
      2. 在每一步中,产生候选项集时循环产生的组合过多,没有排除不应该参与组合的元素,即没有用到性质三
    3. 优化:主要考虑三个方面
      1. 第一,数据库的压缩,如果一个条目(或者说项目)不包含任何一个K-项集,那么它不可能包含任何一个K+1项集,即在下一次的遍历数据库时,不需要再去对该条目进行检查(通常做法是删除该条目,或者将这个条目做上标记)。
      2. 第二,缩小候选项集的个数,即动态项集计数。在某个条目的统计之后,如果发现某个候选项集的计数已经满足了最小支持度,那么可以将这个项集直接放入到频繁项集中,这样以后就不用对该项集进行计数了
      3. 第三,在连接的步骤之前,先对项集进行利用性质三进行筛选,提前删除不满足的项集。对K-1项项集中的每一个元素进行计数,若某个元素的个数小于K-1,则将K-1项集中删除包含该元素的项集。这样可以极大的减小了可能产生的候选项集的数量。
    4. 优化的步骤如下:                  apriori算法的简介和改进总结apriori算法的简介和改进总结apriori算法的简介和改进总结

原标题:apriori算法的简介和改进总结

关键词:

*特别声明:以上内容来自于网络收集,著作权属原作者所有,如有侵权,请联系我们: admin#shaoqun.com (#换成@)。

可能感兴趣文章

我的浏览记录