[發明專利]無重疊的三支序列模式挖掘方法

在審

• 申請號: 202010544976.0
• 申請日: 2020-06-15
• 公開（公告）號: CN111581263A
• 公開（公告）日: 2020-08-25
• 發明（設計）人: 武優西;羅嵐方;王月華;李曉峰;馬鵬飛;耿萌;王珠林
• 申請（專利權）人: 河北工業大學
• 主分類號: G06F16/2458
• 分類號: G06F16/2458
• 代理公司: 天津翰林知識產權代理事務所(普通合伙) 12210
• 代理人: 胡安朋

1.無重疊的三支序列模式挖掘方法，其特征在于：利用模式拼接縮減候選模式的空間，通過在隊列中采用深度優先和回溯策略計算候選模式的模式支持度來解決無重疊的三支序列模式挖掘問題，具體步驟如下：

第一步，讀入序列數據庫SDB、強字符集Γ、中字符集Λ、弱字符集Ω、最小間隙min、最大間隙max和最小支持度閾值minsup：

讀入給定的序列數據庫SDB，確定其中包含的序列總數為N，該序列數據庫SDB中的每個序列分別記為序列S₁、序列S₂、…、序列S_k、…、序列S_N，其中1≤k≤N，序列S_k中所包含的字符分別記作字符s₁、字符s₂、…、字符s_n，讀入給定強字符集Γ、中字符集Λ、弱字符集Ω、最小間隙min、最大間隙max和最小支持度閾值minsup；

第二步，處理模式長度為1的頻繁三支序列模式集合fre₁：

計算上述第一步讀入的強字符集和中字符集中各字符的出現次數即為模式支持度，將模式支持度大于等于最小支持度閾值minsup的字符加入模式長度為1的頻繁三支序列模式集合fre₁；

第三步，生成候選模式集合cand_L+1：

生成候選模式集合cand_L+1，其中L表示頻繁三支序列模式的長度，

①當L＝1時，采用fre₁中的字符相互組合的方法生成候選模式集合cand_L+1：

將上述第二步處理獲得的模式長度為1的頻繁三支序列模式集合fre₁中的字符相互組合，生成模式長度為L+1的候選模式集合cand_L+1；

②當L1時，采用模式拼接的方法生成候選模式集合cand_L+1：

當L1時，在生成候選模式的過程中，模式P＝p₁p₂…p_m-1p_m，prefix(P)為模式P的前綴，除去模式P的最后一個子模式p_m剩余的部分稱為模式P的前綴，即prefix(P)＝p₁p₂…p_m-1，suffix(P)為模式P的后綴，除去模式P的第一個子模式p₁剩余的部分稱為模式P的后綴，即suffix(P)＝p₂…p_m-1p_m；當兩個模式長度為L的模式P的后綴與模式Q的前綴相等時，能夠拼接為模式長度為L+1的模式T，即suffix(P)＝p₂p₃…p_L＝prefix(Q)＝q₁q₂…q_L-1時，模式

采用上述模式拼接的方法生成候選模式集合cand_L+1的具體處理方法如下：

當模式長度為L的頻繁三支序列模式集合fre_L不為空時，從左到右遍歷頻繁三支序列模式集合fre_L，依次取出頻繁三支序列模式集合fre_L中的模式P_a，計算suffix(P_a)，然后從左到右尋找滿足suffix(P_a)＝prefix(P_b)條件的模式P_b，對模式P_a與模式P_b進行拼接為模式長度為L+1的模式將模式T加入模式長度為L+1的候選模式集合cand_L+1中，對頻繁三支序列模式集合fre_L中的所有滿足suffix(P_a)＝prefix(P_b)條件的模式P_b進行拼接，直到在頻繁三支序列模式集合fre_L中模式P_b的下一個模式P_c，suffix(P_a)≠prefix(P_c)時，對模式P_a的拼接結束，從頻繁三支序列模式集合fre_L中模式P_a的下一個模式開始，繼續重復上述步驟，直到最后一個模式拼接結束，模式長度為L+1的候選模式集合cand_L+1生成完畢；

第四步，計算模式P_h在序列數據庫SDB中的模式支持度sup(P_h,SDB)：

第(4.1)步，計算模式P_h在序列S_k中的模式支持度sup(P_h,S_k)：

模式P_h在序列S_k中的模式支持度sup(P_h,S_k)通過如下步驟計算：

第(4.1.1)步，確定隊列的個數：

讀入模式P_h，確定其長度為m，該模式P_h的各個子模式分別記作子模式p₁、子模式p₂、…、子模式p_m，這里0m≤n，根據給定模式P_h中的子模式數確定隊列的個數，則確定隊列共有m個，分別記作隊列1、隊列2、…、隊列m，模式支持度sup(P_h,S_k)初始化為0；

第(4.1.2)步，采用深度優先和回溯策略創建隊列中的結點：

根據上述第一步中給定的強字符集Γ、中字符集Λ、弱字符集Ω、最小間隙min、最大間隙max、序列S_k和上述第(4.1.1)步讀入的模式P_h創建在隊列j末尾標簽為i的結點，該結點記為

具體處理方法如下：

1)計算隊列1末尾結點的范圍：

根據上述第一步中的序列S_k和上述第(4.1.1)步讀入的模式P_h，通過上述第一步中給定的最小間隙min，用如下公式(1)計算隊列1中的最大結點Maxroot，即隊列1末尾的結點不能超過Maxroot，

Maxroot＝n-m-min*(m-1)+1 (1)，

公式(1)中，n為序列S_k的長度，m為模式P_h的長度，模式的長度m和隊列的個數m相等；

2)判斷是否需要創建隊列j末尾的結點

當字符s_i＝子模式p_j時，分別從以下兩種情況判斷是否創建隊列j末尾的結點

①當字符s_i＝子模式p_j時，結點在隊列j中不存在，在隊列j的末尾創建結點同時通過如下公式(2)和公式(3)分別計算結點的最小邊界和最大邊界

公式(2)和(3)中，i為結點在序列S_k中的字符s_i的位置；

②當字符s_i＝子模式p_j時，結點在隊列j中已經存在，繼續尋找滿足三支間隙條件且與子模式p_j相等的字符；

3)當隊列j末尾的結點被創建之后，通過如下步驟創建隊列j+1末尾的結點：

a)判斷結點在序列S_k中的字符s_i與最小邊界在序列S_k中的字符s_i+min+1之間的字符s_t是否屬于中或弱字符，其中iti+min+1：

①當存在字符s_t不屬于中或弱字符時，說明通過結點不可能存在一個出現，需要采用回溯策略，回溯到隊列j-1末尾的結點從隊列j末尾的結點在序列S_k中的字符s_i的下一個字符s_i+1繼續尋找滿足三支間隙條件且與子模式p_j相等的字符；

②當任意字符s_t均屬于中或弱字符，執行下面的步驟b)；

b)依次判斷從結點的最小邊界在序列S_k中的字符s_i+min+1到最大邊界在序列S_k中的字符s_i+max+1之間的字符s_x是否與子模式p_j+1相等，其中i+min+1≤x≤i+max+1：

①當字符s_x與子模式p_j+1不相等時，先判斷字符s_x是否屬于中字符，當字符s_x屬于中字符，再判斷字符s_x的下一個字符是否與子模式p_j+1相等；當字符s_x不屬于中字符時，說明通過結點不存在一個出現，需要采用回溯策略，與上述步驟a)中的①回溯相同；

②當字符s_x與子模式p_j+1相等時，結點在隊列j+1中不存在，直接在隊列j+1末尾創建結點

③當字符s_x與子模式p_j+1相等時，結點在隊列j+1中已經存在，繼續尋找滿足三支間隙條件且與子模式p_j+1相等的字符；

4)當隊列m中的結點被創建時，說明找到了模式P_h在序列S_k中的一個出現，模式P_h的模式支持度sup(P_h,S_k)加1，然后再從隊列1末尾的結點在序列S_k中的字符s_l1的下一個字符s_l1+1開始繼續創建隊列1末尾的結點，迭代上述過程依次創建隊列2、隊列3、…、隊列m末尾的結點，當創建隊列1末尾的結點時，字符s_r中的rMaxroot，隊列中的結點創建結束，模式P_h在序列S_k中的出現也尋找完畢，Maxroot是依據上述第(4.1.2)步中第1)步的公式(1)計算得到的；

由此完成計算模式P_h在序列S_k中的模式支持度sup(P_h,S_k)；

第(4.2)步，計算模式P_h在給定序列數據庫SDB的模式支持度：

通過如下公式(4)計算候選模式集合cand_L+1中的模式P_h在給定序列數據庫SDB中的模式支持度sup(P_h,SDB)，

公式(4)中，sup(P_h,S_k)為模式P_h在序列S_k中的模式支持度，即出現數，k為序列數據庫SDB中的第k個序列；

通過上述第(4.1)步依次計算模式P_h在序列數據庫SDB中序列S₁、序列S₂、…、序列S_k、…、序列S_N的模式支持度sup(P_h,S₁)、sup(P_h,S₂)、…、sup(P_h,S_k)、…、sup(P_h,S_N)，其中1≤k≤N，然后通過上述公式(4)得到模式P_h在序列數據庫SDB中的模式支持度sup(P_h,SDB)；

第五步，獲得所有模式長度為L+1的頻繁三支序列模式集合fre_L+1：

通過上述第四步依次計算上述第三步生成的模式長度為L+1的候選模式集合cand_L+1中每個模式P_h的模式支持度sup(P_h,SDB)，當sup(P_h,SDB)≥minsup時，添加到模式長度為L+1的頻繁三支序列模式集合fre_L+1中，并且按字母順序排列，由此獲得所有模式長度為L+1的頻繁三支序列模式集合fre_L+1；

第六步，當模式長度為L+1的候選模式集合cand_L+1為空或當模式長度為L+1的頻繁三支序列模式集合fre_L+1為空時，頻繁三支序列模式挖掘完畢。