[發明專利]保序序列模式挖掘方法

在審

• 申請號: 202010544303.5
• 申請日: 2020-06-15
• 公開（公告）號: CN111581262A
• 公開（公告）日: 2020-08-25
• 發明（設計）人: 武優西;戶倩;郭媛;王曉慧;趙曉倩;王珠林;崔文峰
• 申請（專利權）人: 河北工業大學
• 主分類號: G06F16/2458
• 分類號: G06F16/2458;G06N5/02
• 代理公司: 天津翰林知識產權代理事務所(普通合伙) 12210
• 代理人: 胡安朋

1.保序序列模式挖掘方法，其特征在于：利用模式融合方法生成候選模式，減少了候選模式的個數、通過一系列轉換和驗證步驟計算候選模式的支持度，具體步驟如下：

第一步，輸入時間序列S和最小支持度閾值minsup：

輸入時間序列S，確定其長度為n，該時間序列S中的每個元素分別記作元素s₁、元素s₂、…、元素s_n，輸入最小支持度閾值minsup，它是由用戶所指定的、所期望的模式在時間序列S中的最小出現數；

第二步，獲得模式長度為2的頻繁模式集合fre₂：

模式長度為2的候選模式集合cand₂＝{(1,2),(2,1)}，按照如下所述的模式支持度的計算步驟，依次計算模式長度為2的候選模式集合cand₂＝{(1,2),(2,1)}中各候選模式P_d在時間序列S中的模式支持度，當候選模式的模式支持度≥最小支持度閾值minsup，該候選模式P_d就是模式長度為2的頻繁模式，并將該候選模式P_d加入到模式長度為2的頻繁模式集合fre₂中，由此獲得模式長度為2的頻繁模式集合fre₂，

模式支持度的計算步驟如下：

首先將當前所處理的候選模式集合中的候選模式P_d的元素按照從小到大的順序進行排序，將排名第i的元素在候選模式P_d中的位置下標記為index[i]，在候選模式P_d中有p_index[i]p_index[i+1]條件成立，其中p_index[i]為候選模式P_d中排名第i的元素，p_index[i+1]是候選模式P_d中排名第i+1的元素，1≤i≤m-1，其中m為當前所處理的候選模式P_d的模式長度，

然后將候選模式P_d按照如下公式(1)轉換為二進制數字串P’，二進制數字串P’中的每個元素分別記作元素a₁、…、元素a_i、…、元素a_m-1，將時間序列S按照如下公式(2)轉換為二進制數字串S’，二進制數字串S’中的每個元素分別記作元素b₁、…、元素b_j、…、元素b_n-1，公式(1)和(2)如下所示，

公式(1)和(2)中，m為當前所處理的候選模式P_d的模式長度，m的初值為2，n為時間序列S的長度，a_i為二進制數字串P’中各元素的值，其中1≤i≤m-1，將候選模式P_d中連續兩個元素p_i和p_i+1進行比較，其中1≤i≤m-1，當p_ip_i+1,那么a_i等于1，當p_ip_i+1,那么a_i等于0；b_j為二進制數字串S’中各元素的值，其中1≤j≤n-1，將時間序列S中連續兩個元素s_j和s_j+1進行比較，其中1≤j≤n-1，當s_js_j+1,那么b_j等于1，當s_js_j+1,那么b_j等于0；

應用經典模式匹配算法在二進制數字串S’中找出二進制數字串P’的出現，每找到一個出現，就根據該出現保留時間序列S中的對應子序列作為候選子序列，并驗證此候選子序列的第一個元素的位置下標l₁是否滿足條件滿足，候選模式P_d的模式支持度加一，不滿足，候選模式P_d的模式支持度不變，其中，為候選子序列中與候選模式P_d的元素p_index[i]的位置相對應的元素，為候選子序列中與候選模式P_d的元素p_index[i+1]的位置相對應的元素，1≤i≤m-1，當所有的出現被找到且所有候選子序列被驗證完成，即可得到候選模式P_d的模式支持度；

第三步，生成模式長度為L+1的候選模式集合cand_L+1：

采用模式融合方法，由模式長度為L的頻繁模式集合fre_L生成模式長度為L+1的候選模式集合cand_L+1，其中，L表示當前所處理的頻繁模式的模式長度，L的初始值為2，在生成候選模式集合的過程中，對于頻繁模式P，它的每個元素分別為元素p₁、元素p₂、…、元素p_L，將頻繁模式P的最后一個元素p_L除去，剩余的部分稱為頻繁模式P的前綴，記作prefix(P)，頻繁模式P的前綴的相對順序記作prefixorder(P)；將頻繁模式P的第一個元素p₁除去，剩余的部分稱為頻繁模式P的后綴，記作suffix(P)，頻繁模式P的后綴的相對順序記作suffixorder(P)，

模式融合方法有以下兩種不同情況下的融合規則：

1)普通情況：對于兩個模式長度都為L的頻繁模式P和頻繁模式Q，頻繁模式P的每個元素分別為元素p₁、元素p₂、…、元素p_L，頻繁模式Q的每個元素分別為元素q₁、元素q₂、…、元素q_L，當頻繁模式P的后綴的相對順序與頻繁模式Q的前綴的相對順序相等，但是頻繁模式P的后綴和頻繁模式Q的前綴不相等，那么頻繁模式P和頻繁模式Q能夠融合為一個模式長度為L+1的候選模式，記為候選模式X，候選模式X的每個元素分別為元素x₁、元素x₂、…、元素x_L+1，此為普通情況，其具體融合規則如下：

比較頻繁模式P的第一個元素p₁和頻繁模式Q的最后一個元素q_L的大小：

①當p₁q_L時，令候選模式X的第一個元素x₁＝p₁，候選模式X的最后一個元素x_L+1＝q_L+1，然后將頻繁模式P的除第一個元素以外的其他位置的元素p_u與頻繁模式Q的最后一個元素q_L相比較，當p_uq_L，那么候選模式X的對應位置元素x_u＝p_u+1，否則，x_u＝p_u，其中2≤u≤L；

②當p₁q_L時，令候選模式X的第一個元素x₁＝p₁+1，候選模式X的最后一個元素x_L+1＝q_L，然后將頻繁模式Q的除最后一個元素以外的其他位置的元素q_v與頻繁模式P的第一個元素p₁進行比較，當q_vp₁，那么候選模式X的對應位置元素x_v+1＝q_v+1，否則，x_v+1＝q_v，其中1≤v≤L-1；

2)特殊情況：對于兩個模式長度都為L的頻繁模式P和頻繁模式Q，頻繁模式P的每個元素分別為元素p₁、元素p₂、…、元素p_L，頻繁模式Q的每個元素分別為元素q₁、元素q₂、…、元素q_L，當不僅頻繁模式P的后綴的相對順序和頻繁模式Q的前綴的相對順序相等，而且頻繁模式P的后綴和頻繁模式Q的前綴也相等，那么頻繁模式P和頻繁模式Q能夠融合為兩個模式長度為L+1的候選模式，分別記為候選模式T和候選模式K，候選模式T的每個元素分別為元素t₁、元素t₂、…、元素t_L+1，候選模式K的每個元素分別為元素k₁、元素k₂、…、元素k_L+1，此為特殊情況，其具體融合規則如下：

在生成候選模式T時，令候選模式T的第一個元素t₁＝p₁+1，候選模式T的最后一個元素t_L+1＝p₁，然后將頻繁模式P的除第一個元素以外的其他位置的元素p_u與p₁進行比較，當p_up₁，那么候選模式T的對應位置元素t_u＝p_u+1，否則，t_u＝p_u，其中2≤u≤L；

在生成候選模式K時，令候選模式K的第一個元素k₁＝p₁，K的最后一個元素k_L+1＝p₁+1，然后將頻繁模式P的除第一個元素以外的其他位置的元素p_u與p₁進行比較，當p_up₁，那么候選模式K的對應位置元素k_u＝p_u+1，否則，k_u＝p_u，其中2≤u≤L；

采用上述模式融合方法，由模式長度為L的頻繁模式集合fre_L生成模式長度為L+1的候選模式集合cand_L+1的具體處理方法如下：

當模式長度為L的頻繁模式集合fre_L不為空時，首先取出頻繁模式集合fre_L中的第一個頻繁模式P_a，計算頻繁模式P_a的后綴和后綴的相對順序，然后從左到右依次遍歷頻繁模式集合fre_L中的每一個頻繁模式P_b，并依次判斷頻繁模式P_b與頻繁模式P_a是否滿足上述模式融合方法中的兩種情況，當滿足任一情況就按照對應的融合規則進行融合生成模式長度為L+1的候選模式，然后將生成的模式長度為L+1的候選模式加入到模式長度為L+1的候選模式集合cand_L+1中，當遍歷完所有的頻繁模式P_b，對頻繁模式P_a的融合處理結束，然后從頻繁模式集合fre_L中的第一個頻繁模式P_a的下一個頻繁模式開始，繼續重復上述步驟，直到處理完頻繁模式集合fre_L中的最后一個頻繁模式，完成生成模式長度為L+1的候選模式集合cand_L+1；

第四步，獲得模式長度為L+1的頻繁模式集合fre_L+1：

按照上述第二步所述的模式支持度的計算方法，依次計算模式長度為L+1的候選模式集合cand_L+1中的每個候選模式P_d的模式支持度sup(P_d,S)，當候選模式P_d的模式支持度sup(P_d,S)≥最小支持度閾值minsup時，將候選模式P_d添加到模式長度為L+1的頻繁模式集合fre_L+1中，當計算完候選模式集合cand_L+1中所有候選模式的模式支持度，即獲得模式長度為L+1的頻繁模式集合fre_L+1；

第五步，完畢保序序列模式挖掘：

當模式長度為L+1的頻繁模式集合fre_L+1不為空時，循環上述的第三步和第四步，直到模式長度為L+1的候選模式集合cand_L+1為空或模式長度為L+1的頻繁模式集合fre_L+1為空，完畢保序序列模式挖掘。