关联规则挖掘 - Apriori算法

1 Apriori?介绍

Apriori?算法使用频繁项集的先验知识，使用一种称作逐层搜索的迭代方法， k项集用于探索?(k+1)?项集。

首先，通过扫描数据库，累积每个项的计数，并收集满足最小值尺度的项，找出频繁?1?项集的集合，该集合记做?L₁?。然后利用?L₁?找频繁?2?项集的集合?L₂?，L₂?找?L₃?...如此下去，直到不能再找到任何频繁?k?项集。最后再在所有的频繁集中找出强规则，即产生用户感兴趣的关联规则。

其中，?Apriori?算法具有这样一条性质?：频繁项集的所有非空子集也必须是频繁的。

Apriori性质基于这样的观察：如果项集I不满足最小值尺度min_sup，则项集I不是频繁的。即 P(I)<?最小支持度阈值，当有元素?A?添加到?I?中时，结果项集（?A UI?）不可能比?I?出现次数更多。因此?A U ?I?也不是频繁的。

该性质属于一类特殊的性质，即反单调性。指如果一个集合不能通过测试，则它所有的超级也都不能通过相同的测试。

2???使用候选产生发现频繁项集

Apriori?算法采用连接步和剪枝步两种方式来找出所有的频繁项集。

（1）??连接步

为找出?L_k?（所有的频繁?k?项集），通过将?L_k-1?（所有的频繁?k-1?项集）与自身连接产生候选?k项集的集合。该候选集合记作?C_k?。

设?l₁?和?l₂?是?L_k-1?中的成员。记?l_i?[j]?表示?l_i?中的第?j?项（例如?l₁[k-2] 表示l1的倒数第2项）。假设?Apriori?算法对事务或项集中的项按字典次序排序，即对于（?k-1?）项集?l_i?，?l_i?[1]<l_i?[2]<?………?.<l_i?[k-1]?。 L_k-1?与自身连接，如果(l₁?[1]=l₂?[1])&&( l₁?[2]=l₂?[2])&&?……?..&& (l₁?[k-2]=l₂?[k-2])&&(l₁?[k-1]<l₂?[k-1])?，那认为?l₁?和?l₂?是可连接。连接l₁?和?l₂?产生的结果是?{l₁?[1],l₁?[2],?……?,l₁?[k-1],l₂?[k-1]}?。

上面是韩家炜《数据挖掘 - 概念与技术》中的描述。用人的话来说就是：l₁是频繁项集?L_k-1?中的项，在于自身连接时，l₁保持不变，在添加这样的项：除了最后一项，其它与l1相同，组成新的k项。

（2）??剪枝步

C_K?是?L_K?的超集，也就是说，?C_K?的成员可能是也可能不是频繁的，但所有的频繁项集K都包含在C_K?中。通过扫描所有的事务（交易），确定?C_K中每个候选的计数，判断是否小于最小支持度计数，如果不是，则认为该候选是频繁的。要计算C_K?的支持度，就要不断的扫库，成本太高了。

如何压缩C_K?，来减少扫库的次数呢？

我们可以利用Apriori?性质：?任一频繁项集的所有非空子集也必须是频繁的，反之，如果某个候选的非空子集不是频繁的，那么该候选肯定不是频繁的，从而可以将其从?C_K?中删除。即如果K项集的（K-1）项子集不在?L_k-1?中，那么该候选集也不在K项集中。回想连接步的候选集构造，?l₁?和?l₂?本身都是频繁的，只是在连接另一个的元素后产生的不频繁。只需要计算这些项集是否频繁就好了。也可以采用Hash的方法实现，是否能够映射到Hash表中。

3 由频繁项集产生关联规则

一旦由数据库中的事务找出频繁项集（满足最小支持度），可以由他们产生强关联规则（满足最小置信度）。

置信度的计算公式：

其中，支持度用事务数来计算。