序列模式挖掘详解

《序列模式挖掘详解》由会员分享，可在线阅读，更多相关《序列模式挖掘详解（103页珍藏版）》请在金锄头文库上搜索。

1、数据挖掘与商务智能 Data Mining for (k = 1; Fk !=; k+) do begin Ck+1 = candidates generated from Fk ; for each transaction t in database do increment the count of all candidates in Ck+1 that are contained in t Fk+1 = candidates in Ck+1 with min_support end return k Fk; Apriori算法伪代码： 知识回顾 p支持度度量满足单调性(X为X的子集) p

2、 置信度一般不满足单调性(X为X的子集) p 如果关联规则产生自同一项集，则置信度满足单调性 知识回顾 Pruned supersets 基于支持度的候选项集剪枝 知识回顾 Pruned Rules Low Confidence Rule 基于置信度的候选规则剪枝 GSP算法 算法思想(候选产生测试法)： 类似于Apriori算法，采用冗余候选模式的剪除 策略和特殊的数据结构-哈希树来实现候选模 式的快速访存。 GSP算法描述 1.扫描序列数据库，得到长度为1的序列模式F1，作为 初始的种子集 2.根据长度为i 的种子集Fi ，通过连接操作和修剪操作 生成长度为i+1的候选序列模式Ci+1；扫

3、描序列数据库 ，计算每个候选序列模式的支持度，产生长度为i+1的 序列模式Fi+1，并将Fi+1作为新的种子集 3.重复第二步，直到没有新的序列模式或新的候选序列 模式产生为止 F1 C2 F2 C3 F3 C4 F4 GSP算法伪代码 p输入：大项集阶段转换后的序列数据库DT。 p输出：最大序列 （1） L1 = large 1-sequences； （2） FOR （k = 2；Lk-1 ；k+） DO BEGIN （3） Ck = GSPgenerate(Lk-1)； （4） FOR each customer-sequence c in the database DT DO （5） I

4、ncrement the count of all candidates in Ck that are contained in c ； （6） Lk = Candidates in Ck with minimum support； （7） END； （8） Answer = Maximal Sequences in kLk； GSP算法 n产生候选序列模式主要分两步： 连接阶段：如果去掉序列模式s1的第一个元素与去掉序列模式 s2的最后一个元素所得到的序列相同，则可以将s1与s2进行连 接，即将s2的最后一个元素添加到s1中 剪枝阶段：若某候选序列模式的某个子序列不是序列模式， 则此候选序列

5、模式不可能是序列模式，将它从候选序列模式 中删除 L1 C2 L2 C3 L3 C4 L4 GSP算法 n序列合并过程 序列s1与另一个序列s2合并，s2的最后一个单项可以作 为最后一个单项合并到s1的最后一个元素中，也可以作 为一个单独的元素。取决于以下条件： 如果s2的最后两个单项属于相同的元素，则s2的最后一个 单项在合并后的序列中是s1的最后一个元素的一部分。 如果s2的最后两个单项属于不同的元素，则s2的最后一个 单项在合并后的序列中成为连接到s1尾部的元素。 GSP算法 n候选序列模式的支持度计算：对于给定的候选序列模式集合C ，扫描序列数据库，对于其中的每一条序列s,找出集合C中

6、被s 所包含的所有候选序列模式，并增加其支持度计数 举例 哈希树 nGSP采用哈希树存储候选序列模式。哈希树的 节点分为三类： 根节点 内部节点 叶子节点 哈希树 n根节点和内部节点中存放的是一个哈希表，每个哈希表 项指向其它的节点。而叶子节点内存放的是一组候选序 列模式。 n例： 添加候选序列模式 n从根节点开始，用哈希函数对序列的第一个元素做映射 来决定从哪个分支向下，依次在第n层对序列的第n个单 项作映射来决定从哪个分支向下，直到到达一个叶子节 点。将序列储存在此叶子节点。 n初始时所有节点都是叶子节点，当一个叶子节点所存放 的序列数目达到一个阈值，它将转化为一个内部节点。 计算候选序列

7、模式的支持度 o 给定一个序列s是序列数据库的一个记录： 1.对于根节点，用哈希函数对序列s的每一个单项做映射来并 从相应的表项向下迭代的进行操作 2）。 2.对于内部节点，如果s是通过对单项x做哈希映射来到此节点 的，则对s中每一个和x在一个元素中的单项以及在x所在元 素之后第一个元素的第一个单项做哈希映射，然后从相应的 表项向下迭代做操作 2）或 3）。 3.对一个叶子节点，检查每个候选序列模式c是不是s的子序列. 如果是相应的候选序列模式支持度加一。 计算候选序列模式的支持度 nhash树存储的优点 这种计算候选序列的支持度的方法避免了大量无用的扫描，对 于一条序列，仅检验那些最有可能成

8、为它子序列的候选序列模 式。扫描的时间复杂度由O(n*m)降为O(n*t),其中n表示序列数量 ，m表示候选序列模式的数量，t代表哈希树叶子节点的最大容 量 GSP算法存在的主要问题 n如果序列数据库的规模比较大，则有可能会产生大量的候 选序列模式 n需要对序列数据库进行循环扫描 n对于序列模式的长度比较长的情况，由于其对应的短的序 列模式规模太大，本算法很难处理 SPADE算法 nSPADE(Sequential PAttern Discovery using Equivalent Class) developed by Zaki 2001 n基于Apriori的垂直数据格式的序列模式挖掘算

9、法 n通过简单的连接K序列任意长度为(k-1)子序列的ID_list，可以 确定任意K序列的支持度。ID_list的长度等于K序列的支持度 ，即可确定是否是序列模式。 n数据库表示形式： SPADE算法 minsup =2 SPADE算法总结 n优点： 垂直数据格式的使用连同ID_list的创建，可以减少对序列数据库 的扫描。 ID_list携带了计算候选序列支持度的必要信息，随着频繁序列长 度的增加，导致连接速度加快。 n缺点： 同GSP，使用宽度优先和先验剪枝产生很大的候选集。 序列模式挖掘算法概述 n基于划分的模式生长算法 该类算法基于分治的思想，迭代的将原始数据集进行划分，减少 数据规

10、模，同时在划分的过程中动态的挖掘序列模式，并将新发现 的序列模式作为新的划分元。典型的代表有FreeSpan算法和 PrefixSpan算法 PrefixSpan算法 p算法思想：基于FP-Growth算法 Pei, et al.ICDE01 采用分治的思想，不断产生序列数据库的多个更小的 投影数据库，然后在各个投影数据库上进行序列模式 挖掘 知识回顾 nFP-Growth算法 通过逐个读入事务，并把每一个事务映射到 FP树中的一条路径的方法构造FP-Tree。 在FP-Tree上利用递归分治的方法挖掘频繁项 集 知识回顾 null A:1 B:1 null A:1 B:1 B:1 C:1 D

11、:1 After reading TID=1: After reading TID=2: 知识回顾 nul l A:7 B:5 B:3 C:3 D:1 C:1 D:1 C:3 D:1 D:1 E:1 E:1 Pointers are used to assist frequent itemset generation D:1 E:1 Transaction Database Header table 基本概念 n前缀：设每个元素中的所有单项按照字典序排列。 给定序列 = ， = (m n) ，如果ei = ei (i m - 1)， em em，并且(em - em)中 的单项均在em中单项的

12、后面， 则称是的前缀 例：序列 是序列 的一个前缀 ；序列则不是 。 基本概念 n投影：给定序列和 ，如果是的子序列，则 关于的投影必须满足： 是的前缀，是 的满足上述条件的最大子序列 例：对于 序列 =， 其子序列 = 的投影是 = ; 的投影 是原序列。 基本概念 p后缀： 序列关于子序列 = 的投影 为 = (n = m)，则序列关于子序列 的后缀为， 其中em” = (em - em) n例：对于 序列，其子序列的投影 是，则对于的后缀为 。 总结：后缀即是投影去掉它自身； 举例 n例： 基本概念 n投影数据库：设为序列数据库S中的一个序列 模式，则的投影数据库为S中所有以为前缀 的序

13、列相对于的后缀，记为S| n投影数据库中的支持度：设为序列数据库S中 的一个序列，序列以为前缀，则在的投影 数据库S|中的支持度为S|中满足条件 .的 序列的个数 举例 n例：对于如下的序列数据库生成一系列的投影数据库 SidSequence 10 20 30 40 举例 n扫描序列数据库S，产生长度为1的序列模式有 ： : 4, :4, : 4, : 3, : 3, : 3 n序列模式的全集必然可以分为分别以， ，和为前缀的序列模式的集 合，构造不同前缀所对应的投影数据库，结果 如下页图所示 举例 PrefixProject Database Prefix-Span算法描述 n扫描序列数据库

14、，生成所有长度为1的序列模式 n根据长度为1的序列模式，生成相应的投影数据库 n在相应的投影数据库上重复上述步骤，直到在相应的 投影数据库上不能产生长度为1的序列模式为止 n分别对不同的投影数据库重复上述过程，直到没有新 的长度为1的序列模式产生为止 S S1 Sm S11 S1n Sm1 Smp 算法伪码 nPrefixSpan算法 输入：序列数据库S及最小支持度阈值 min_sup 输出：所有的序列模式 方法：去除所有非频繁的项目，然后调用子 程序PrefixSpan(, 0, S) 算法伪码 n子程序PrefixSpan(, L, S|) n参数： : 一个序列模式 ; L:序列模式的长

15、度 ; S| :如果为空，则为S，否则为的投影数据库 扫描S|，找到满足下述要求的长度为1的序列模式b： nb可以添加到的最后一个元素中并为序列模式 n可以作为的最后一个元素并为序列模式 对每个生成的序列模式b，将b添加到形成序列模式 ，并输出 对每个,构造的投影数据库S| ,并调用子程序 PrefixSpan(, L + 1, S|) PrefixSpan算法 n序列合并过程 序列s1与另一个序列s2合并，s2的最后一个单项可以作 为最后一个单项合并到s1的最后一个单项中，也可以作 为一个单独的单项。取决于以下条件： 如果s2的最后两个单项属于相同的元素，则s2的最后一个 单项在合并后的序列中是s1的最后一个元素的一部分。 如果s2的最后两个单项属于不同的元素，则s2的最后一个 单项在合并后的序列中成为连接到s1尾部的元素。 举例 Sid sequence 1 2 3 4 给定如下的序列数据库：minsup = 2 举例 n找出频繁单项：1，3，7，8；