王子悦
看完了AprioriAll算法 尝试了一点实现 写了一篇解释这个算法的博客
终于有时间来研究这个算法了。上上次说到这个算法非常适合学习路径的挖掘，为什么呢这是一种频繁序列挖掘，与通常的频繁模式挖掘不同，它考虑到了事件出现的序列，这是非常适合学习路径的特点的，有点类似于先导课和后延课的感觉。
举个栗子：某华辑同学在某段时间学习了离散数学课程，接下来又学习了数据结构课程，那我们接下来应该给他推荐什么课呢数据库里显示，学过这两门课的同学还学过Java编程语言和数据库原理两门课，那么我们应该推荐哪一门呢这两门课和华辑同学学的两门课的关联程度不相上下，但是熟悉计算机或者软件专业教学安排的同学可能有一些模糊的感觉，Java编程语言看起来是更基础的课程，而数据库结构更像是学会了数据结构之后应该学的东西。没错，这就是一种序列模式，当我们匹配到频繁序列之后，我们就可以推荐之后的事件，而不是关联度同样高的之前事件了。
在AprioriAll之前先说一下Apriori思想：如果某个项集是频繁的，那么它的所有子集也是频繁的。这一思想用到关联模式发掘中就是非常成功的Apriori算法，可以快速的找到频繁项集。这一算法的详细解释一搜就有好多，这里不再赘述了。
AprioriAll本质上是Apriori思想的扩张，只是在产生候选序列和频繁序列方面考虑序列元素有序的特点，将项集的处理改为序列的处理。
基于水平格式的Apriori类算法将序列模式挖掘过程分为5个具体阶段，即排序阶段、找频繁项集阶段、转换阶段、产生频繁序列阶段以及最大化阶段。AprioriAll也是如此：
1) 排序阶段。数据库D以客户 为主键，交易时间为次键进行排序。这个阶段将原来的事务数据库转换成由客户序列组成的数据库。
2) 频繁项集阶段。找出所有频繁项集组成的集合L。也同步得到所有频繁1-序列组成的集合。
3) 转换阶段。在找序列模式的过程中，要不断地进行检测一个给定的频繁集是否包含于一个客户序列中。
4) 序列阶段。利用已知的频繁集的集合来找到所需的序列。类似于关联的Apriori算法。
5）最大化阶段。在频繁序列模式集合中持出最大频繁序列模式集合
1.排序阶段
对原始数据表（交易数据库D）按客户 （作为主关键字）和交易时间（作为次关键字）进行排序，排序后通过对同一客户的事件进行合并得到对应的序列数据库（序列数据库S）。
最后求得的频繁1-序列L1={{30}，{40}，{70}，{40，70}，{80}}。
然后将频繁1-项集映射成连续的整数。例如，将上面得到的L1映射成表6.4对应的整数。由于比较频繁项集花费一定时间，这样做后可以减少检查一个序列是否被包含于一个客户序列中的时间，从而使处理过程方便且高效。
4.产生频繁序列阶段
利用转换后的序列数据库寻找频繁序列，AprioriAll算法如下：
输入：转换后的序列数据库S，所有项集合I，
最小支持度阈值min_sup
输出：序列模式集合L
方法：其过程描述如下：
（2）剪枝
剪枝的原则：一个候选k-序列，如果它的(k-1)-序列有一个是非频繁的，则删除它。由Ck剪枝产生Lk的过程如下：
序列数据库S2
① 先求出L1，由其产生L2的过程如图6.2所示，实际上这个过程不需要剪枝，因为C2中每个2-序列的所有子序列一定属于L1。
产生L3的过程
③ 由L3连接并剪枝产生C4，扫描序列数据库S1，删除小于min_sup的序列得到L4，其过程如下所示。
例：对于前面的序列数据库S2，从前面的过程看到，产生的所有频繁序列集合：
L={，，，，，，，，，，，，，，，，，，，}
删除子序列得到最大序列的过程如下：
由于最长的序列是4，因此所有4-序列都是最大序列，这里只有是最大序列。
对于4-序列，从L中删除它的3-子序列、、、，2-子序列、、、、、和1-子序列、、、，剩下的3-序列是最大序列。
对于3-序列，从L中删除它的2-子序列、和1-子序列，剩下的2-序列是最大序列。
到此，L中已没有可以再删除的子序列了，得到的序列模式如下表所示。
到此为止，AprioriAll算法就得到了频繁序列。
梁惠欣
正在训练wiki语料集，，估计要跑一两天
邵长旭
改了Blog的UI，在弄上传图片功能，还没弄好，明天继续
声明：本站部分文章及图片源自用户投稿，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！