时间序列频繁模式挖掘:A->(EFG)->C 模式的思考
首先了解一下 A->(EFG)->C 是个什么形式: 这里面被括号包覆的部分表示EFG是无序存在的,比如EFG,EGF,GEF,GFE他们都可以统一写成(EFG)的形式,假设这四个项集都只在A~C的时间段内出现了一次,但是一旦把他们看成(EFG)的形式,那么他们就相当于出现了四次,如果min_sup<=4的话那(EFG)就可以被认为是频繁的。 这种挖掘模式的意义: 导师没有跟我说明这种挖掘模式的意义何在,我大概想了一下可能是这种情况:两位老师A、C发言之间有EFG三位学生在短时间内在多个时间点进行过频繁交流,但是他们说话的次序是乱序的。通过本模式就可以找出这三位同学很可能是技术伙伴或者是合伙人等等,但是依靠传统的模式他们的交流很可能就不是频繁的,也就找不出他们的关系了。 当然这种形式也未必非得是在某两个事件A,C之间进行的,这并不重要,如何挖掘(EFG)模式才是关键。 解决思路: 1. 将A->( ?)->C中 ( ?)里地部分全部挖掘出来(要标记A,C发生的时间点,在后面会减少时间复杂度) 时间复杂度O(n) 2. ?将挖出来的含有非freq1元素的项集pop掉 比如 A->KEF->C 中,如果K元素并不是freq1项集的成员,那么?A->KEF->C 这个项集就剪掉不要了 3. 提取中间项: 把“A-”>和“->C”去掉 4. 假如现在提取出来了三个字符串:MEFG、EMFG、HEGF 下面要做的跟Apriori做的就一样了,先去freq1项集,再找freq2.....,这里注意一下,找的项集是无序的 比如:‘’EF’‘都出现在了这三个成员之中,只要是出现了,就记它的频度+1,最后跟min_sup比较一下就行了 最终我提取出乱序freq-3项集有(min_sup=2):(EFG),(EFM),(FGM),(EGM) 还可以提出一个freq-4项集:(EFGM) 字母在括号内的顺序是可以打乱的,这个无所谓。 关于时间复杂度: 我大致估计了一下,不会超过常数倍O(n^2),与之前的GSP算法结合一下时间复杂度依旧常数倍O(n^2)的时间复杂度,可以接 受。 代码实现:(完善中,敬请期待...) (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |