机器学习：序列模式挖掘算法

------------------------------------------------------------------------------------------------------------------------

题目：下面有关序列模式挖掘算法的描述，错误的是？

??AprioriAll算法和GSP算法都属于Apriori类算法，都要产生大量的候选序列

? FreeSpan算法和PrefixSpan算法不生成大量的候选序列以及不需要反复扫描原数据库

? 在时空的执行效率上，FreeSpan比PrefixSpan更优（错）

??和AprioriAll相比，GSP的执行效率比较高

------------------------------------------------------------------------------------------------------------------------

关联分析之序列模式

关键算法：

1. Apriori算法 ：关联分析原始算法，用于从候选项集中发现频繁项集。两个步骤：进行自连接、进行剪枝。缺点：无时序先后性。

AprioriAll算法：AprioriAll算法与Apriori算法的执行过程是一样的，不同点在于候选集的产生，需要区分最后两个元素的前后。

AprioriSome算法：可以看做是AprioriAll算法的改进

AprioriAll算法和AprioriSome算法的比较：

（1）AprioriAll用 去计算出所有的候选Ck，而AprioriSome会直接用 去计算所有的候选 ，因为 包含 ，所以AprioriSome会产生比较多的候选。

（2）虽然AprioriSome跳跃式计算候选，但因为它所产生的候选比较多，可能在回溯阶段前就占满内存。

（3）如果内存占满了，AprioriSome就会被迫去计算最后一组的候选。

（4）对于较低的支持度，有较长的大序列，AprioriSome算法要好些。

2. GPS算法：类Apriori算法。用于从候选项集中发现具有时序先后性的频繁项集。两个步骤：进行自连接、进行剪枝。缺点：每次计算支持度，都需要扫描全部数据集；对序列模式很长的情况，由于其对应的短的序列模式规模太大，算法很难处理。

3. SPADE算法：改进的GPS算法，规避多次对数据集D进行全表扫描的问题。与GSP算法大体相同，多了一个ID_LIST记录，使得每一次的ID_LIST根据上一次的ID_LIST得到（从而得到支持度）。而ID_LIST的规模是随着剪枝的不断进行而缩小的。所以也就解决了GSP算法多次扫描数据集D问题。

4.??FreeSpan算法：即频繁模式投影的序列模式挖掘。核心思想是分治算法。基本思想为：利用频繁项递归地将序列数据库投影到更小的投影数据库集中，在每个投影数据库中生成子序列片断。这一过程对数据和待检验的频繁模式集进行了分割，并且将每一次检验限制在与其相符合的更小的投影数据库中。

优点：减少产生候选序列所需的开销。缺点：可能会产生许多投影数据库，开销很大，会产生很多的

5.?PrefixSpan 算法：从FreeSpan中推导演化而来的。收缩速度比FreeSpan还要更快些。