AprioriAll算法

AprioriAll本质上是Apriori思想的扩张，只是在产生候选序列和频繁序列方面考虑序列元素有序的特点，将项集的处理改为序列的处理。

类Apriori算法将序列模式挖掘过程分为5个具体阶段，即排序阶段、找频繁项集阶段、转换阶段、产生频繁序列阶段以及最大化阶段。

1. 排序阶段

对原始数据表按客户号（作为主关键字）和交易时间（作为次关键字）进行排序，排序后通过对同一客户的事件进行合并得到对应的序列数据库。

2. 找频繁项集阶段

这个阶段根据min_sup找出所有的频繁项集，也同步得到所有频繁1-序列组成的集合L1。这个过程是从所有项集合I开始进行的。

然后将频繁1-项集映射成连续的整数。例如，将上面得到的L1映射成下表对应的整数。

由于比较频繁项集花费一定时间，这样做后可以减少检查一个序列是否被包含于一个客户序列中的时间，从而使处理过程方便且高效。

3. 转换阶段

在寻找序列模式的过程中，要不断地进行检测一个给定的大序列集合是否包含于一个客户序列中。为此做这样的转换：

每个事件被包含于该事件中所有频繁项集替换。如果一个事件不包含任何频繁项集，则将其删除。如果一个客户序列不包含任何频繁项集，则将该序列删除。

这样转换后，一个客户序列由一个频繁项集组成的集合所取代。每个频繁项集的集合表示为{e1，e2，…，ek}，其中ei（1≤i≤k）表示一个频繁项集。

4. 产生频繁序列阶段

利用转换后的序列数据库寻找频繁序列，AprioriAll算法如下：

输入：转换后的序列数据库S，所有项集合I，

　　　最小支持度阈值min_sup

输出：序列模式集合L

上述算法中利用频繁序列Lk-1生成候选k-序列Ck的过程说明如下

（1）连接

对于Lk-1中任意两个序列s1和s2，如果s1与s2的前k-2项相同，即s1=<e1，e2，…，ek-2，f1>，s2=<e1，e2，…，ek-2，f2>，则合并序列s1和s2，得到候选k-序列<e1，e2，…，ek-2，f1，f2>和<e1，e2，…，ek-2，f2，f1>。

（2）剪枝

剪枝的原则：一个候选k-序列，如果它的(k-1)-序列有一个是非频繁的，则删除它。

5. 最大化阶段

在频繁序列模式集合中找出最大频繁序列模式集合。

【例6.4】对于表6.5所示的序列数据库S1，从前面的过程看到，产生的所有频繁序列集合：L={<1>，<2>，<3>，<4>，<5>，<1，2>，<1，3>，<1，4>，<1，5>，<2，3>，<2，4>，<3，4>，<3，5>，<4，5>，<1，2，3>，<1，2，4>，<1，3，4>，<1，3，5>，<2，3，4>，<1，2，3，4>}

　删除子序列得到最大序列的过程如下：

   由于最长的序列是4，因此所有4-序列都是最大序列，这里只有<1，2，3，4>是最大序列。

　　对于4-序列<1，2，3，4>，从L中删除它的3-子序列<1，2，3>、<1，2，4>、<1，3，4>、<2，3，4>，2-子序列<1，2>、<1，3>、<1，4>、<2，3>、<2，4>、<3，4>和1-子序列<1>、<2>、<3>、<4>，剩下的3-序列<1，3，5>是最大序列。

对于3-序列<1，3，5>，从L中删除它的2-子序列<1，5>、<3，5>和1-子序列<5>，剩下的2-序列<4，5>是最大序列。

　　到此，L中已没有可以再删除的子序列了，得到的序列模式如下表所示。

当求出所有序列模式集合L后，可以采用类似Apriori算法生成所有的强关联规则。

例如，假设有一个频繁3-序列<{D}，{B，F}，{A}>，其支持度计数为2，它的一个子序列<{D}，{B，F}>的支持度计数也为2。

　　若置信度阈值min_conf=75%，则：

<{D}，{B，F}>→<{D}，{B，F}，{A}>

是一条强关联规则，因为它的置信度=2/2=100%。