西安交通大学数据仓库与数据挖掘第二次作业 计算机 11 班 2013 年 3 月 12 日 第四章作业 找出所有找出支持度大于 50 的所有序列模式 用所讲的两种算法 解 首先对原始数据库进行处理 S1 A B C D E C S2 A B C D E S3 BAB D E S4 C D E CE S5 BA B C A D 1 GSP 算法 长度为 1 且满足支持度的序列模式有 长度为 2 且满足支持度的序列求法如下 标红满足 A B C D E A AA AB AC AD AE B BA BB BC BD BE C CA CB CC CD CE D DA DB DC DD DE E EA EB EC ED EE A B C D E A AB AC AD AE B BC BD BE C CD CE D DE E 求得满足条件的序列模式为 长度为 3 序列模式的求法如下 k 2 连接 剪枝 AC ACD AD ACE AE BCD BC BCE BD A DE BE B DE CD C DE CE DE 同理 求得最终的序列模式集合为 到此完毕 2 PrefixSpan 算法 S1 A B C D E C S2 A B C D E S3 BAB D E S4 C D E CE S5 BA B C A D 长度为 1 且满足支持度的序列模式有 构造以为前缀的投影数据库 projected database S1 B C D E C S2 B C D E S3 B D E S4 S5 B C A D 扫描 projected database 一次 找到所有具有 前缀的 length 2 序 列模式 扫描 projected database 一次 找到所有具有 前缀的 length 3 序列模式 构造以为前缀的投影数据库 projected database 如下 S1 D E C S2 D E S3 S4 S5 A D 空的 针对的扫描终止 至此 由出发的序列模式构造完成 分别对 和 重复以上过程 得到序列模式为 到此完毕