数据挖掘|序列模式挖掘及其算法的python实现
数据挖掘|序列模式挖掘及其算法的python实现
- 1. 序列模式分析
- 2. 基础知识
- 3. 序列模式分析实例
- 4. 类Apriori算法（GSP算法）
- 4.1 算法工作原理
- 4.2 实现流程解析
- 4.3 Python实现细节
1. 序列模式挖掘
序列型数据挖掘也被认为是序列分析的一种形式。
序列模式发现（Sequential Patterns Discovery）这一概念是由R．Agrawal首次提出于1995年。
该方法旨在识别事件之间基于顺序关系的内在联系。
在购买了喷墨打印机的所有顾客中，在三个月后约有80%再次购买了墨盒（墨盒），这构成了一个序列关联规则（Sequence association rule）。对于保险行业而言，在研究客户重复购买行为时发现：当客户近期选择了重疾险时，在下一次购买阶段倾向于选择分红保险（Dividend insurance）。因此，在实际运营过程中，保险公司可以通过统计重疾险产品的销量来预估并满足未来对分红保险的需求量（Sales volume）
该技术作为序列数据挖掘的一种有效手段，在多个领域展现出其应用潜力。
2. 基本概念
设I={i_1,i_2,...,i_n}是一个项集，序列就是若事件（元素）组成的有序列表。
一个序列Se可表示为
该系统由多种组件集成而成。当系统仅包含一个组件时，请注意通常会省略集成符号，并如上所述示例所示，则该系统可直接表示为C₁₂³。
存在一定的顺序关系，在于各元素之间有明确的位置排列；然而，在于每个元素内部的各项之间没有固定的顺序关系。通常以字典顺序进行排序的一种有序数据结构被称为词典序结构。对于一个由若干个项组成的有序集合而言，在计算机科学中我们称其为一个序列，并用符号L表示，则这样的序列为L-序列
序列数据库即由满足特定条件的元组
满足条件的两个序列\alpha = \langle a_1, a_2, \dots, a_n \rangle与\beta = \langle b_1, b_2, \dots, b_m \rangle之间存在这样的对应关系：即存在一组严格递增的索引集合\{i_1, i_2, \dots, i_n\}（其中1 \leq i_1 < i_2 < \dots < i_n \leq m），使得对于每一个k（1 \leq k \leq n），都有a_k包含于b_{i_k}之中。基于此关系定义，在数学领域中我们称前者\alpha为后者的子序列（subsequence），并用符号表示为\alpha\subseteq\beta。
在序列数据库Se中定义了支持度的概念：其支持度等于在Se中出现过α的所有序列表示为与总序贯数量之比。设预设的支持度阈值为τ，则当某序贯α在其所属数据库中的出现次数及其排列顺序均满足其支持度≥τ时，则称该序贯α为该数据库中的频繁序列（即频繁模式）。
3. 序列模式挖掘实例
现有事务数据库如下表1所示，在交易过程中不考虑顾客购买物品的数量仅关注是否进行了物品的购买记录。经过整理后可以得到顾客的购物序列库，请参考图2
- 表1：顾客购物事务数据库
| 时间 | 顾客ID | 购物项集 |
|---|---|---|
| 2023.12.10 | 2 | 10，20 |
| 2023.12.11 | 5 | 90 |
| 2023.12.12 | 2 | 30 |
| 2023.12.13 | 2 | 40，60，70 |
| 2023.12.14 | 4 | 30 |
| 2023.12.15 | 3 | 30，50，70 |
| 2023.12.17 | 1 | 30 |
| 2023.12.17 | 1 | 90 |
| 2023.12.18 | 4 | 40，70 |
| 2023.12.19 | 4 | 90 |
- 表2：顾客购物序列库
| 顾客ID | 顾客购物序列 |
|---|---|
| 1 | <30,90> |
| 2 | <{10,20},30,{40,60,70}> |
| 3 | <{30,50,70}> |
| 4 | <30,{40,70},90> |
| 5 | <90> |
将最低支持度设定为25%后，在表2的数据中可以看出，在这种情况下<31.18%,66.67%>被认为是<18.18%, 66.67% >的一个子序列段。经过计算分析可知，在这两个不同的序列中均呈现出相同的支持度水平（均为4.8），从而可以推断出它们构成了一种特定的序列模式。
4. 类Apriori算法（GSP算法）
序贯式数据挖掘是在预设的序列数据库环境中识别出符合最低支持度标准的所有序贯式数据的过程
4.1 算法思想
基于分而治之的方法论框架下展开研究，在这一过程中持续生成一系列更小规模且更具特化的子数据库集合，并通过系统性地对每个子数据库执行深入分析与挖掘工作以实现整体目标
4.2 算法步骤
分析该数据库中的事务行为数据集合（Transaction Data Set），提取出所有长度为1的有效项集（Frequent 1-itemsets），并将其定义为空间初始种群（Initial Population）。
基于当前种子集（Current Seed Set），通过结合运算（Join Operation）生成下一层次的所有候选项集（Candidate Sets）。接着对提取出的所有候选序列进行统计（Statistical Analysis），筛选出满足最小支持度阈值的新项集（New Frequent Itemsets），并将其作为新的空间初始种群参与后续迭代过程。
持续执行上述步骤直至不再发现新的有效模式为止。
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： [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