web数据挖掘.ppt

改进的 PrefixSpan算法在 Web挖掘中的应用
课程:Web数据挖掘
任课老师: 吴扬扬
主讲人: 王芳芳
目录
概述
01
PrefixSpan算法-相关概念
02
PrefixSpan算法改进
04
PrefixSpan*算法应用于Web挖掘
05
结束语
06
PrefixSpan算法描述
03
2
01. 概述
随着的飞速发展,各种网络数据量呈指数级的速度增长,如何在浩瀚的数据中找到有价值的信息,是 Web挖掘要解决的问题。日志挖掘是 Web挖掘的一个重要研究方向,而 prefixSpan在日志挖掘中的效率远胜于其他经典数据挖掘算法。
本次报告的目的:针对 PrefixSpan算法在挖掘中产生的投影数据库需占用大量的存储空间, 对其扫描时也需花费相当多的时间。提出基于投影的 PrefixSpan* (舍弃非频繁项)算法, 通过删除非频繁项以及判断投影序列数与最小支持数的关系, 减少了不必要的存储空间, 提高了查询速度。
实验证明: PrefixSpan* 算法比 PrefixSpan 算法具有更好的时空性能。
3
02. PrefixSpan算法-相关概念
1 子序列( Sub-Sequence)
假设序列 s1 = <α1 ,α2 , …,αn > , s2 = <β1 , β2 ,…,βm > ( n≤m ) , s1是 s2的子序列,当且仅当存在 1≤j1 < j2 <. . . < jn ≤m,使得α1 βj1,α2 βj2, …,αn βjn。
2 前缀( Prefix)
假设两个给定的序列 s1 与 s2 中全部数据项都按字母顺序排列,其中 s1 = <α1 ,α2 ,…,αn > , s2 =<β1 , β2 ,…,βm > ( n≥m ) ,若 s2 是 s1 的前缀,当且仅当:αi=βi, i≤m;βm ≤αm ; (αm -βm )中的所有数据项均按字母顺序排序,且均排在βm 之后。
4
3 投影( Projection)
给定序列 s1 , s2 ( s2 s1 ) , s′1称为 s1 对应序列 s2 的投影,当且仅当(1) s2是 s′1的前缀; (2) s′1是 s1 的满足条件(1)的最大子序列。
4 序列模式( Sequential Pattern)
S的支持度( support (S) )是指在给定的序列数据库D中包含 S的序列个数, support ( S ) = | ( s′∈D)∩( s′ S ) | ,给定最小支持度 min_sup,如果每个子序列 S在序列数据库中的支持度均大于阈值 min_sup,则称 S是频繁序列模式,简称序列模式。
02. PrefixSpan算法-相关概念(续)
5
例子:<a(abc)(ac)d(cf)>
<a> <(abc)(ac)d(cf)>
<aa> <(_bc)(ac)d(cf)>
a(ab)
a(abc)
<ab> <(_c)(ac)d(cf)>
02. PrefixSpan算法-相关概念(续)
6
03. PrefixSpan算法描述
PrefixSpan算法:
是序列模式挖掘算法之一:PrefixSpan算法是基于序列投影的一种模式增长算法。
PrefixSpan算法是一种深度优先搜索算法,其基本思想是使用频繁前缀划分搜索空间和投影序列数据库,并搜索相关的序列。首先检查前缀子序列,只将其相应的后缀子序列投影到数据库中。该算法同时采用分治的策略,不断产生序列数据库的多个更小的投影数据库,然后在各个投影数据库上进行序列模式挖掘。
7
03. PrefixSpan算法描述
PrefixSpan算法的主要思想是利用序列前缀划分搜索空间和投影序列数据库,搜索相关符合要求的序列。
输入:序列数据库 S 及最小支持度阈值min_sup.
输出:所有的序列模式。
方法:调用子程序 PrefixSpan(< >, 0, S)。
其中子程序 PrefixSpan(α, L,S|α)的描述如下:
参数:;;S|,则为S,否则为α的投影数据库。
(1)扫描 S|α,找到满足下述要求的长度为 1的序列模式 b;
1)b 可以添加到α的最后一个元素中并为序列模式;
2)<b>中可以作为α的最后一个元素中并为序列模式;
(2)对每个生成的序列模式 b,将 b 添加到α形成序列模式α′,并输出α′;
(3)对每个α′,构造α′的投影数据库 S|α,并调用子程序 PS(α′,L+1,S|α′)。
8
03. PrefixSpan算法描述(续)
PrefixSpan算法描述:
扫描序列数据库,生成所有长度为1的序列模