agrawal apriori算法

agrawal apriori

算法

    Apriori

算法是一种常用于关联规则挖掘的算法。它的核心思想是先找出频繁项集，

然后利用频繁项集来推导出关联规则。

在

Apriori

算法中，频繁项集使用支持度来度量。支持度表示在所有交易中出现该项

集的概率，即

$Support(X)=\frac{count(X)}{|D|}$

，其中

$X$

为项集，

$count(X)$

为项集

出现的次数，

$|D|$

为总交易数。

    Apriori

算法的基本流程如下：

    1. 

扫描数据集，生成候选项集

$C_1$

，每个项集仅包含一个元素。

    2. 

用

$C_1$

生成所有可能的长度为

2

的候选项集，只有包含目前最频繁项集中的项才

是合法的。即如果

$C_1$

中项集为

{a,b,c}

，那么只有包含

{a}

和

{b}

或

{a}

和

{c}

或

{b}

和

{c}

的项集才是合法的。对所有合法的项集统计支持度得到频繁项集

$L_2$

。

    4. 

生成频繁项集之后，可以推导出关联规则。对于频繁项集

$X$

，从中选择任意一个

子集

$Y$

，得到规则

$Y \rightarrow (X-Y)$

。对规则进行评估，如计算置信度

$Conf(Y 

\rightarrow (X-Y))= \frac{Support(X)}{Support(Y)}$

。如果置信度达到设定阈值，则

保留规则。

    Apriori

算法的优点是能够处理大规模数据集，但也存在一些缺点。由于每次扫描数

据集都需要生成候选项集，计算量较大，尤其是在数据集中项的数目比较多、项目集的长

度较长时，效率会很低。此外，

Apriori

算法只考虑项集之间的单向关系，无法处理项集

之间的相互影响。

为了解决

Apriori

算法的缺点，出现了许多改进版的算法，如

FP-Growth

算法、

Eclat

算法等。

    FP-Growth

算法利用

FP

树（频繁模式树）来快速挖掘频繁项集，从而减少候选项集生

成的次数。

Eclat

算法则将

Apriori

算法中的候选项集看做是比较和交集，通过按支持度

排序和垂直数据表示来优化算法。这些改进版算法在效率、灵活性等方面都有所提高，成

为现在关联规则挖掘领域的研究热点之一。