PrefixSpan频繁序列算法快速理解
经典例子
首先,图中两图间没有关系,只是说明两种数据的形式区别;
然后,我们只需要关注序列数据;
最后,我们需要理解“<>”代表什么意思?
项的理解
<a(abc)(ac)d(cf)>是表中的第一项可以理解为SID为10的用户,5次来商店购买的商品集,第一次只买了a商品,第二次买了a、b、c,第三次买了a、c,第四次只买了d,第五次买了c、f。
所以,"<>“表示一个序列项,”()“表示单次购买多个商品,单个商品不用”()"。
PrefixSpan怎么实现的
图片还是copy别人的,上图左上角表是序列表,
1。从列表中统计出单个项(这里忽略括号,相当于单个用户购买项目不去重陈列)的频数。
2。去出不频繁的g项目开头的项。剩下有a,b,c,d,e,f开头的项。
3。上图下面模型是,分别以a,b,c,d,e,f开头的子序列集合。
4。每用户的所有项从左到右,开头字母不在子序列体现,比如<a(abc)(ac)d(cf)>变为a—> <(abc)(ac)d(cf)>。
5。某用户单次购买多个项,这些项中含有开头字母对应项,则用“_”代替开头字母(用于区别单个字母出现的情况)。
比如第二个用户a开头的是<(ad)c(bc)(ae)>是a—><(_d)c(bc)(ae)>,如果是a—><(d)c(bc)(ae)>表示的是<a(d)c(bc)(ae)>
进一步是分别在a,b,c,d,e,f开头的子序列集合中进行上面的操作,同样先统计各用户子项中的频数。
不过值得注意的是,这次的统计出的开头和前一次的统计开头没有序列顺序关系,比如:前一次a的子序列中,有3个f:
<(abc)(ac)d(cf)>
<(_b)(df)cb>
<(_f)cbc>
分别转换为 af----><>(这种情况不会发生在这,只是说明,不频繁已经在前面删除),af----><_cb>,af----><_cbc>,其中a和f不是挨着的。
递归计算就能找出频繁序列