数据挖掘|序列模式挖掘及其算法的python实现

1. 序列模式挖掘

序列(sequence)模式挖掘也称为序列分析。
序列模式发现（Sequential Patterns Discovery）是由R．Agrawal于1995年首先提出的。
序列模式寻找的是事件之间在顺序上的相关性。

• 例如，“凡是买了喷墨打印机的顾客中，80%的人在三个月之后又买了墨盒”，就是一个序列关联规则。对于保险行业，通过分析顾客不同次的购买行为发现，顾客本次购买重疾险，下次购买分红保险，则企业可以通过对重疾险销量的统计来预测分红险的销售量。

序列模式挖掘在交易数据库分析、Web访问日志分析以及通信网络分析等领域具有广泛的应用前景。

2. 基本概念

设$I=i_1,i_2,...,i_n$是一个项集，序列就是若事件（元素）组成的有序列表。

一个序列$Se$可表示为$<s_1,s_2,...,s_n>$，其中$s_j(j=1,2,\dots ,n)$为事件，也称为$Se$的元素。

元素由不同的项组成。当元素只包含一项时，一般省去括号，例如， { i 2 } \{i_2\} {i2​}一般表示为$i_2$。

元素之间是有顺序的，但元素内的项是无序的，一般定义为词典序。序列包含项的个数称为序列的长度，长度为$L$的序列记为$L-序列$。

序列数据库就是元组$<sid,Se>$的集合，即有序事件序列组成的数据库，其中$Se$是序列，$sid$ 是该序列的序列号。

存在两个序列$\alpha =<a_1,a_2,...,a_n>,\beta =<b_1,b_2,\dots ,b_n>$，如果存在整数$1\le i_1<i_2<\dots <i_n\le m$ 且 $a_1\subseteq b_{i1},a_2\subseteq b_{i2},\dots ,a_n\subseteq b_{in}$，那么称序列$\alpha$是$\beta$ 的子序列（subsequence），或者序列$\beta$ 包含$\alpha$，记作$\alpha \subseteq \beta$ 。

序列在序列数据库$Se$ 中的支持度为序列数据库 $Se$ 中包含序列$\alpha$的序列个数除以总的序列数，记为 $support(\alpha )$。给定支持度阈值$\tau$，如果序列$\alpha$在序列数据库中的支持度不低于$\tau$，则称序列$\alpha$为序列模式（频繁序列）。

3. 序列模式挖掘实例

现有事务数据库如下表1所示，交易中不考虑顾客购买物品的数量，只考虑物品有没有被购买。整理后可得到顾客购物序列库，如表2所示。

• 表1：顾客购物事务数据库

• 表2：顾客购物序列库

设最小支持度为 25%，从表2中可以看出，<30,90> 是 <30, {40,70},90> 的子序列。两个序列<30,90>、<30,{40,70},90>的支持度都为 40%，因此是序列模式。

4. 类Apriori算法（GSP算法）

序列模式挖掘是在给定序列数据库中找出满足最小支持度阈值的序列模式的过程。

4.1 算法思想

采用分而治之的思想，不断产生序列数据库的多个更小的投影数据库，然后在各个投影数据库上进行序列模式挖掘。

4.2 算法步骤

1. 扫描序列数据库，得到长度为$1$的序列模式$L1$，作为初始的种子集。
2. 根据长度为$i$ 的种子集$L_i(i\ge 1)$ 通过连接操作生成长度为$i+1$的候选序列模式$C_{i+1}$；然后扫描序列数据库，计算每个候选序列模式的支持数，产生长度为$i+1$的序列模式$L_{i+1}$，并将 $L_{i+1}$ 作为新的种子集。
3. 重复第二步，直到没有新的序列模式或新的候选序列模式产生为止

4.3 基于Python的算法实现

问题：原始序列为：<1,2,3,4>，<{1,5},2,3,4>, <1,3,4,{3,5}>, <1,3,5>, <4,5>，挖掘其中的序列模式。
以下代码是本人自己实现的。感觉原始序列的数据结构使用的不太好，导致子模式识别较为麻烦，可能存在错误，仅保证本算例正确，敬请谅解。

import numpy as np
#子模式判断 
def isSubSeq(seq,subseq)->bool:
    i=0;
    if len(subseq)>len(seq):
        return False
    for sel in subseq:
        if i >= len(seq):
            return False
        for j in range(i,len(seq)):
            if type(seq[j])==list:
                if sel in seq[j]:
                    i=j+1
                    break
                elif j==len(seq)-1:
                    return False
            elif sel==seq[j]:
                i=j+1
                break
            elif j==len(seq)-1:
                return False
            else:
                continue
    return True          

# 获取L1数据集
def getL1(seq):
    ds=[]
    for ss in seq:
        for s in ss:
            if type(s)==list:
                for e in s:
                    if [e] not in ds:
                        ds.append([e])
            else:
                if [s] not in ds:
                    ds.append([s])
    return np.array(ds)

# 获取L2数据集
def getL2(l1seq)->np.ndarray:
    ds=[]
    for i in range(len(l1seq)):
        for j in range(len(l1seq)):
            if i != j:
                #np.append(ds, [l1seq[i],l1seq[j]])
                ds.append([l1seq[i][0],l1seq[j][0]])    
    return  np.array(ds)  

# 获取L3数据集
def getL3(l1seq,l2seq):
     ds=[]
     for se2 in l2seq:
         for se1 in l1seq:
             if se1 not in se2:
                 ds.append(np.append(se2, se1))         
     return  ds  
# 获取L4数据集
def getL4(l1seq,l3seq):
     ds=[]
     for se3 in l3seq:
         for se1 in l1seq:
             if se1 not in se3:
                 ds.append(np.append(se3, se1))         
     return  ds        
 
#计算支持度
def calSup(dsq,seq):
    i=0.0
    for s in dsq:
        if isSubSeq(s,seq):
            i=i+1
    return i/len(dsq)

if __name__ == "__main__":
    min_support = 0.4  #最小支持度
    dsq = np.array([[1,2,3,4],[[1,5],2,3,4],
                         [1,3,4,[3,5]],[1,3,5],[4,5]],dtype=object)

    l1=getL1(dsq)
    for l in l1:
        print('序列-1：',l,'的支持度为：',calSup(dsq, l))
    l2 = getL2(l1)
    l2seq=[]
    for i in range(len(l2)):
        sups=calSup(dsq, l2[i])
        if sups >=min_support:
            print('序列-2：',l2[i],'的支持度为：',sups)
            l2seq.append(l2[i])
    l3=getL3(l1,l2seq)
    l3seq=[]
    for i in range(len(l3)):
        sups=calSup(dsq, l3[i])
        if sups >=min_support:
            print('序列-3：',l3[i],'的支持度为：',sups)
            l3seq.append(l3[i])
    l4=getL4(l1,l3seq)
    l4seq=[]
    for i in range(len(l4)):
        sups=calSup(dsq, l4[i])
        if sups >=min_support:
            print('序列-4：',l4[i],'的支持度为：',sups)
            l4seq.append(l4[i])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

输出：

	序列-1： [1] 的支持度为： 0.8
	序列-1： [2] 的支持度为： 0.4
	序列-1： [3] 的支持度为： 0.8
	序列-1： [4] 的支持度为： 0.8
	序列-1： [5] 的支持度为： 0.8
	序列-2： [1 2] 的支持度为： 0.4
	序列-2： [1 3] 的支持度为： 0.8
	序列-2： [1 4] 的支持度为： 0.6
	序列-2： [1 5] 的支持度为： 0.4
	序列-2： [2 3] 的支持度为： 0.4
	序列-2： [2 4] 的支持度为： 0.4
	序列-2： [3 4] 的支持度为： 0.6
	序列-2： [3 5] 的支持度为： 0.4
	序列-2： [4 5] 的支持度为： 0.4
	序列-3： [1 2 3] 的支持度为： 0.4
	序列-3： [1 2 4] 的支持度为： 0.4
	序列-3： [1 3 4] 的支持度为： 0.6
	序列-3： [1 3 5] 的支持度为： 0.4
	序列-3： [2 3 4] 的支持度为： 0.4
	序列-4： [1 2 3 4] 的支持度为： 0.4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20