序列模式挖掘详解.ppt

实验步骤 3.要分析的数据输入完毕后，我们需要选择分析数据的模型，这里我们选择“序列”模型对数据进行分析。 单击选中数据流区域的“用户输入”，再双击“选项板区”中“建模”下的“序列”，将其添加至数据流区域，它将自动与“用户输入”连接，如下： 实验步骤 双击数据流区域的“无目标”，得到对话框如下： 实验步骤 将对话框填写如下，点击“执行” 注：点击 可以看到可选字段。 实验步骤 你将在右上角看到分析结果节点，如右图： 双击“id”将其添加到数据流区域，如下： 实验步骤 双击数据流区域中的“id”，得到分析结果如下： 实验步骤 点击上图中的“ ”，选择“显示全部”，则实验结果如下： 实验结果分析 实验结果分析 下面我们以 为例，对实验结果进行分析。第一栏为前项，其有两行构成，表示先购买c，再购买b。后项为d。实例为1，表示先购买了c，再购买了b，则之后购买了d的个体个数。规则支持为20%，即实例与样本总体的比值，即1/5。出现前项的个体个数，即先购买了c，再购买了b的个体个数，为3个，故置信度为实例/前项的个体个数，即1/3，为33.333%。而支持度与时间先后无关，则它表示购买了b、c、d三件商品的个体个数与样本总体的比值，而购买了b、c、d三件商品的个体个数为3个，则3/5等于60%。 Thank you! 举例 在上面的投影数据库中，前缀(1)的投影数据库中还有频繁单项_3，前缀(3)的投影数据库中还有频繁单项7. 生成频繁2序列(1,3)，(3)(7), 然后为其生成投影数据库.其中没有频繁项目，算法终止。 Sid Suffix for prefix (1,3) 1 3 (8)(7) Sid Suffix for prefix (3)(7) 2 3 PrefixSpan算法分析 PrefixSpan算法不需要产生候选序列模式，从而大大缩减了检索空间 相对于原始的序列数据库而言，投影数据库的规模不断减小 PrefixSpan算法的主要开销在于投影数据库的构造。可以通过伪投影技术进行效率提升。 伪投影 当数据库可以直接放入内存时，并不需要构造所有的序列模式对应的投影数据库，我们可以使用指向数据库中序列的指针及其偏移量作为伪投影 例子：假设上述序列数据库可以放入内存，在构造a投影数据库时，序列 S1 = a(abc)(ac)d(cf)所对应的伪投影为：一个指向S1的指针，指针偏移设定为2。同样的，序列S1的ab投影数据库对应的伪投影为：一个指向S1的指针，指针偏移设定为4 伪投影与物理投影对比 伪投影避免了物理投影拷贝后缀的过程 当数据库可以存放入主内存中，伪投影在时间和空间上都是很高效的 但是当数据库不可以放入内存中时，伪投影技术是非常低效的 硬盘随机访问时很低效的 建议策略: 集成伪投影和物理投影技术 当数据集可以放入内存时候，使用伪投影技术 算法效率比较 伪投影与物理投影比较 闭序列模式挖掘 闭序列模式：如果不存在序列s，其中s是s的真超序列，并且s与s具有相同的支持度，那么称s为闭序列模式 例子：以下序列哪一个为闭序列模式? abc: 20, abcd:20, abcde: 15 CloSpan:Mining Closed Sequential Patterns in Large Datasets Xifeng Yan. Jiawei Han 序列扩展 项集扩展： ，同时 序列扩展： 字典序树 字典序： ,同时 ，如果满足下列条件之一，则tt 举例：(a,f)(b,f),(a,b)(a,b,c) 字典序树 字典序序列 如果s=s?p,则ss；(序列大于它的前缀序列) 如果s=a?ip，同时s=a?sp,无论p与p之间的序列关系都有ss；(项集扩展小于序列扩展) 如果s=a?ip，s=a?ip，pp则有ss；(同种扩展与后缀大小相关) 如果s=a?sp，同时s=a?sp，pp则ss； 举例：(ab) (ab)(a),(ab) (a)(b) 字典序序列树构造 字典序序列树构造 示例 示例 PrefixSpan算法 PrefixSpan算法 特点：在前缀有哪些信誉好的足球投注网站树上有哪些信誉好的足球投注网站所有的频繁项集 终止条件：序列s的投影数据库中序