1. 序列模式挖掘
序列(sequence)模式挖掘也稱為序列分析。
序列模式發(fā)現(xiàn)（Sequential Patterns Discovery）是由R．Agrawal于1995年首先提出的。
序列模式尋找的是事件之間在順序上的相關(guān)性。
- 例如，“凡是買了噴墨打印機(jī)的顧客中，80%的人在三個(gè)月之后又買了墨盒”，就是一個(gè)序列關(guān)聯(lián)規(guī)則。對(duì)于保險(xiǎn)行業(yè)，通過分析顧客不同次的購(gòu)買行為發(fā)現(xiàn)，顧客本次購(gòu)買重疾險(xiǎn)，下次購(gòu)買分紅保險(xiǎn)，則企業(yè)可以通過對(duì)重疾險(xiǎn)銷量的統(tǒng)計(jì)來預(yù)測(cè)分紅險(xiǎn)的銷售量。
序列模式挖掘在交易數(shù)據(jù)庫(kù)分析、Web訪問日志分析以及通信網(wǎng)絡(luò)分析等領(lǐng)域具有廣泛的應(yīng)用前景。
2. 基本概念
設(shè) I = i 1 , i 2 , . . . , i n I={i_1,i_2,...,i_n} I=i1?,i2?,...,in?是一個(gè)項(xiàng)集，序列就是若事件（元素）組成的有序列表。
一個(gè)序列 S e Se Se可表示為 < s 1 , s 2 , . . . , s n > <s_1,s_2,...,s_n> <s1?,s2?,...,sn?>，其中 s j ( j = 1 , 2 , … , n ) s_j(j=1,2, …, n) sj?(j=1,2,…,n)為事件，也稱為 S e Se Se的元素。
元素由不同的項(xiàng)組成。當(dāng)元素只包含一項(xiàng)時(shí)，一般省去括號(hào)，例如， { i 2 } \{i_2\} {i2?}一般表示為 i 2 i_2 i2?。
元素之間是有順序的，但元素內(nèi)的項(xiàng)是無(wú)序的，一般定義為詞典序。序列包含項(xiàng)的個(gè)數(shù)稱為序列的長(zhǎng)度，長(zhǎng)度為 L L L的序列記為 L ? 序列 L-序列 L?序列。
序列數(shù)據(jù)庫(kù)就是元組 < s i d , S e > <sid, Se> <sid,Se>的集合，即有序事件序列組成的數(shù)據(jù)庫(kù)，其中 S e Se Se是序列， s i d sid sid 是該序列的序列號(hào)。
存在兩個(gè)序列 α = < a 1 , a 2 , . . . , a n > , β = < b 1 , b 2 , … , b n > \alpha = <a_1, a_2, ...,a_n>, \beta = <b_1, b_2, …, b_n> α=<a1?,a2?,...,an?>,β=<b1?,b2?,…,bn?>，如果存在整數(shù) 1 ≤ i 1 < i 2 < … < i n ≤ m 1\leq i_1 < i_2 <…<i_n \leq m 1≤i1?<i2?<…<in?≤m 且 a 1 ? b i 1 , a 2 ? b i 2 , … , a n ? b i n a_1\subseteq b_{i1}, a_2 \subseteq b_{i2}, …, a_n \subseteq b_{in} a1??bi1?,a2??bi2?,…,an??bin?，那么稱序列 α \alpha α是 β \beta β 的子序列（subsequence），或者序列 β \beta β 包含 α \alpha α，記作 α ? β \alpha\subseteq \beta α?β 。
序列在序列數(shù)據(jù)庫(kù) S e Se Se 中的支持度為序列數(shù)據(jù)庫(kù) S e Se Se 中包含序列 α \alpha α的序列個(gè)數(shù)除以總的序列數(shù)，記為 s u p p o r t ( α ) support (\alpha) support(α)。給定支持度閾值 τ \tau τ，如果序列 α \alpha α在序列數(shù)據(jù)庫(kù)中的支持度不低于 τ \tau τ，則稱序列 α \alpha α為序列模式（頻繁序列）。
3. 序列模式挖掘?qū)嵗?/h2>
現(xiàn)有事務(wù)數(shù)據(jù)庫(kù)如下表1所示，交易中不考慮顧客購(gòu)買物品的數(shù)量，只考慮物品有沒有被購(gòu)買。整理后可得到顧客購(gòu)物序列庫(kù)，如表2所示。
- 表1：顧客購(gòu)物事務(wù)數(shù)據(jù)庫(kù)
| 時(shí)間 | 顧客ID | 購(gòu)物項(xiàng)集 |
|---|---|---|
| 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：顧客購(gòu)物序列庫(kù)
| 顧客ID | 顧客購(gòu)物序列 |
|---|---|
| 1 | <30,90> |
| 2 | <{10,20},30,{40,60,70}> |
| 3 | <{30,50,70}> |
| 4 | <30,{40,70},90> |
| 5 | <90> |
設(shè)最小支持度為 25%，從表2中可以看出，<30,90> 是 <30, {40,70},90> 的子序列。兩個(gè)序列<30,90>、<30,{40,70},90>的支持度都為 40%，因此是序列模式。
4. 類Apriori算法（GSP算法）
序列模式挖掘是在給定序列數(shù)據(jù)庫(kù)中找出滿足最小支持度閾值的序列模式的過程。
4.1 算法思想
采用分而治之的思想，不斷產(chǎn)生序列數(shù)據(jù)庫(kù)的多個(gè)更小的投影數(shù)據(jù)庫(kù)，然后在各個(gè)投影數(shù)據(jù)庫(kù)上進(jìn)行序列模式挖掘。
4.2 算法步驟
- 掃描序列數(shù)據(jù)庫(kù)，得到長(zhǎng)度為 1 1 1的序列模式 L 1 L1 L1，作為初始的種子集。
- 根據(jù)長(zhǎng)度為 i i i 的種子集 L i ( i ≥ 1 ) L_i (i\geq1) Li?(i≥1) 通過連接操作生成長(zhǎng)度為 i + 1 i+1 i+1的候選序列模式 C i + 1 C_{i+1} Ci+1?；然后掃描序列數(shù)據(jù)庫(kù)，計(jì)算每個(gè)候選序列模式的支持?jǐn)?shù)，產(chǎn)生長(zhǎng)度為 i + 1 i+1 i+1的序列模式 L i + 1 L_{i+1} Li+1?，并將 L i + 1 L_{i+1} Li+1? 作為新的種子集。
- 重復(fù)第二步，直到?jīng)]有新的序列模式或新的候選序列模式產(chǎn)生為止
4.3 基于Python的算法實(shí)現(xiàn)
問題：原始序列為：<1,2,3,4>，<{1,5},2,3,4>, <1,3,4,{3,5}>, <1,3,5>, <4,5>，挖掘其中的序列模式。
以下代碼是本人自己實(shí)現(xiàn)的。感覺原始序列的數(shù)據(jù)結(jié)構(gòu)使用的不太好，導(dǎo)致子模式識(shí)別較為麻煩，可能存在錯(cuò)誤，僅保證本算例正確，敬請(qǐng)諒解。文章來源：http://www.zghlxwxcb.cn/news/detail-845497.html
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數(shù)據(jù)集
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數(shù)據(jù)集
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數(shù)據(jù)集
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數(shù)據(jù)集
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
#計(jì)算支持度
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])
輸出：文章來源地址http://www.zghlxwxcb.cn/news/detail-845497.html
序列-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
到了這里，關(guān)于數(shù)據(jù)挖掘|序列模式挖掘及其算法的python實(shí)現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
