你的位置:首页 > 数据库

[数据库]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. 算法的伪代码



        在第三步产生新的项集之后,需要统计每个项集的频度,主要采取的算法是,对数据库中的每个条目,遍历一遍候选项集,对每个包含该条目的候选项集计数加一。这样的话需要重新扫描一遍数据库,产生大量的计算
    2. 算法的问题:
      1. 在计算项目集 的支持度时需要对数据库的全部记录进行一遍扫描比较,一般情况下数据库的规模会很庞大,这样会极大的增加系统的I/O开销。
      2. 在每一步中,产生候选项集时循环产生的组合过多,没有排除不应该参与组合的元素,即没有用到性质三
    3. 优化:主要考虑三个方面
      1. 第一,数据库的压缩,如果一个条目(或者说项目)不包含任何一个K-项集,那么它不可能包含任何一个K+1项集,即在下一次的遍历数据库时,不需要再去对该条目进行检查(通常做法是删除该条目,或者将这个条目做上标记)。
      2. 第二,缩小候选项集的个数,即动态项集计数。在某个条目的统计之后,如果发现某个候选项集的计数已经满足了最小支持度,那么可以将这个项集直接放入到频繁项集中,这样以后就不用对该项集进行计数了
      3. 第三,在连接的步骤之前,先对项集进行利用性质三进行筛选,提前删除不满足的项集。对K-1项项集中的每一个元素进行计数,若某个元素的个数小于K-1,则将K-1项集中删除包含该元素的项集。这样可以极大的减小了可能产生的候选项集的数量。
    4. 优化的步骤如下: