[發(fā)明專利]一次性條件下帶弱通配符的自適應(yīng)序列模式挖掘方法

在審

• 申請(qǐng)?zhí)枺?/td>: 202010544308.8
• 申請(qǐng)日: 2020-06-15
• 公開（公告）號(hào): CN111581460A
• 公開（公告）日: 2020-08-25
• 發(fā)明（設(shè)計(jì)）人: 史巧碩;王曉慧;李楊;耿萌;羅嵐方;陳明婕;武優(yōu)西
• 申請(qǐng)（專利權(quán)）人: 河北工業(yè)大學(xué)
• 主分類號(hào): G06F16/903
• 分類號(hào): G06F16/903
• 代理公司: 天津翰林知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙) 12210
• 代理人: 胡安朋

1.一次性條件下帶弱通配符的自適應(yīng)序列模式挖掘方法，其特征在于：采用模式增長(zhǎng)的方式生成候選模式去縮減空間，在計(jì)算一次性條件下帶弱通配符的模式支持度時(shí)，采用了在線倒序填充策略實(shí)現(xiàn)模式支持度的高效計(jì)算，從而實(shí)現(xiàn)了一次性條件下帶弱通配符的自適應(yīng)序列模式挖掘，具體步驟如下：

第一步，讀入序列數(shù)據(jù)庫(kù)SDB，給定字符集Σ、強(qiáng)字符集Γ、弱字符集Ω和最小支持度閾值minsup：

讀入序列數(shù)據(jù)庫(kù)SDB，確定其大小為N，該序列數(shù)據(jù)庫(kù)SDB中的每個(gè)序列分別記為序列S₁、序列S₂、…、序列S_k、…、序列S_N，其中1≤k≤N，序列S_k中的每個(gè)字符分別記作字符s₁、字符s₂、…、字符s_n，給定字符集Σ、強(qiáng)字符集Γ、弱字符集Ω和最小支持度閾值minsup；

第二步，處理模式長(zhǎng)度為1的頻繁模式集合fre₁：

將上述第一步給定的強(qiáng)字符集Γ中的字符加入模式長(zhǎng)度為1的候選模式集合cand₁中，計(jì)算候選模式集合cand₁中每個(gè)模式的出現(xiàn)數(shù)，將出現(xiàn)數(shù)大于等于最小支持度閾值minsup的模式加入模式長(zhǎng)度為1的頻繁模式集合fre₁；

第三步，生成模式長(zhǎng)度為L(zhǎng)+1候選模式集合cand_L+1：

采用模式拼接的方法生成候選模式集合cand_L+1，其中L表示頻繁模式的長(zhǎng)度，操作如下：

①當(dāng)L＝1時(shí)，將上述第二步處理獲得的模式長(zhǎng)度為1的頻繁模式集合fre₁中的字符相互組合，生成模式長(zhǎng)度為L(zhǎng)+1的候選模式集合cand_L+1；

②當(dāng)L1時(shí)，采用模式拼接的方法生成模式長(zhǎng)度為L(zhǎng)+1的候選模式集合cand_L+1，具體操作是：

當(dāng)L1時(shí)，在生成候選模式集合cand_L+1的過程中，對(duì)于模式p＝p₁p₂…p_m-1p_m，除去模式p的最后一個(gè)子模式p_m剩余的部分稱為模式p的前綴，即prefix(p)＝p₁p₂…p_m-1；除去模式p的第一個(gè)子模式p₁剩余的部分稱為模式p的后綴，即suffix(p)＝p₂…p_m-1p_m；當(dāng)存在模式長(zhǎng)度同為L(zhǎng)的模式p和模式q，滿足模式p的后綴與模式q的前綴相等時(shí)，采用模式拼接方法拼接為模式長(zhǎng)度為L(zhǎng)+1的模式r，即suffix(p)＝p₂p₃…p_L＝prefix(q)＝q₁q₂…q_L-1時(shí)，模式

當(dāng)模式長(zhǎng)度為L(zhǎng)的頻繁模式集合fre_L不為空時(shí)，從左到右遍歷頻繁模式集合fre_L，依次取出該頻繁模式集合fre_L中的模式p_i，計(jì)算模式p_i的后綴suffix(p_i)，從左到右尋找滿足suffix(p_i)＝prefix(p_j)條件的模式p_j，對(duì)模式p_i與模式p_j進(jìn)行模式拼接為模式長(zhǎng)度為L(zhǎng)+1的模式將模式r加入模式長(zhǎng)度為L(zhǎng)+1的候選模式集合cand_L+1中，對(duì)頻繁模式集合fre_L中的所有滿足suffix(p_i)＝prefix(p_j)條件的模式p_j進(jìn)行拼接，直到在頻繁模式集合fre_L中模式p_j的下一個(gè)模式p_k，suffix(p_i)≠prefix(p_k)時(shí)，對(duì)模式p_i的拼接結(jié)束，從頻繁模式集合fre_L中模式p_i的下一個(gè)模式開始，繼續(xù)重復(fù)上述步驟，直到最后一個(gè)模式拼接結(jié)束，模式長(zhǎng)度為L(zhǎng)+1的候選模式集合cand_L+1生成完畢；

第四步，計(jì)算模式p_i在序列數(shù)據(jù)庫(kù)SDB中的模式支持度sup(p_i,SDB)：

上述第三步生成的模式長(zhǎng)度為L(zhǎng)+1的候選模式集合cand_L+1中每個(gè)模式p_i為上述第三步中的當(dāng)模式長(zhǎng)度為L(zhǎng)的頻繁模式集合fre_L不為空時(shí)，從左到右遍歷頻繁模式集合fre_L，依次取出該頻繁模式集合fre_L中的模式p_i，序列S_k為上述第一步中的序列數(shù)據(jù)庫(kù)SDB中的一個(gè)序列，計(jì)算模式p_i在序列數(shù)據(jù)庫(kù)SDB中的模式支持度sup(p_i,SDB)的操作如下：

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

計(jì)算步驟如下，

第(4.1.1)步，確定隊(duì)列的個(gè)數(shù)：

讀入模式p_i，確定其長(zhǎng)度為m，該模式p_i的各個(gè)子模式分別記作子模式p_i1、子模式p_i2、…子模式p_ij、…子模式p_im，這里(0j≤m)，根據(jù)給定模式p_i中的子模式數(shù)確定隊(duì)列的個(gè)數(shù)，則確定隊(duì)列共有m個(gè)，分別記作隊(duì)列1、隊(duì)列2、…、隊(duì)列j、…、隊(duì)列m，這里0j≤m，模式支持度sup(p_i,S_k)初始化為0；

第(4.1.2)步，創(chuàng)建隊(duì)列結(jié)點(diǎn)：

在一次性條件下挖掘頻繁模式過程中，所有結(jié)點(diǎn)不可重復(fù)使用，根據(jù)上述第一步中給定的強(qiáng)字符集Γ、弱字符集Ω和序列S_k和上述第(4.1.1)步讀入的模式p_i，采用倒序匹配策略創(chuàng)建隊(duì)列結(jié)點(diǎn)，創(chuàng)建隊(duì)列結(jié)點(diǎn)，具體方法如下：

依次讀入序列S_k中的字符，依次從模式p_i最后一層即子模式p_m開始做判斷，判斷序列S_k中的字符是否與模式p_i中字符相同，結(jié)果如下：

1)序列S_k中的字符與模式p_i中的字符不相同，無法創(chuàng)建隊(duì)列結(jié)點(diǎn)；

2)序列S_k中的字符與模式p_i中的字符相同，分下列兩種情況做判斷：

①在上述隊(duì)列1即當(dāng)j＝1時(shí)，直接在隊(duì)列1中創(chuàng)建標(biāo)簽為i的結(jié)點(diǎn)

②在上述除隊(duì)列1之外的隊(duì)列，即當(dāng)j1時(shí)，需要同時(shí)滿足以下兩個(gè)條件，結(jié)點(diǎn)才能創(chuàng)建：

a)隊(duì)列j和隊(duì)列j-1滿足num_jnum_j-1，其中num表示結(jié)點(diǎn)個(gè)數(shù)；

b)結(jié)點(diǎn)和上層隊(duì)列對(duì)應(yīng)結(jié)點(diǎn)滿足弱通配符的要求，即間隙中的字符只能屬于弱字符集Ω，當(dāng)不滿足間隙中的字符只能屬于弱字符集Ω時(shí)，要將結(jié)點(diǎn)和上層隊(duì)列對(duì)應(yīng)結(jié)點(diǎn)所在的隊(duì)列都刪除；

當(dāng)上述最后一層隊(duì)列m即當(dāng)j＝m不為空時(shí)，代表隊(duì)列中存在一組出現(xiàn)，模式p_i的模式支持度sup(p_i,S_k)加1，直至讀完序列中的所有字符，找到所有的一次性出現(xiàn)，模式p_i在序列S_k中的出現(xiàn)尋找完畢，模式p_i的模式支持度sup(p_i,S_k)計(jì)算結(jié)束；

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

第(4.2)步，計(jì)算模式p_i在序列數(shù)據(jù)庫(kù)SDB中的模式支持度sup(p_i,SDB)：

通過如下公式(1)計(jì)算候選模式集合cand_L+1中的模式p_i在上述第一步中讀入的序列數(shù)據(jù)庫(kù)SDB中的模式支持度sup(p_i,SDB)，

公式(1)中，sup(p_i,S_k)為模式p_i在序列S_k中的模式支持度，即出現(xiàn)數(shù)，S_k為序列數(shù)據(jù)庫(kù)SDB中的第k個(gè)序列；

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

第五步，獲得所有模式長(zhǎng)度為L(zhǎng)+1的頻繁模式集合fre_L+1：

通過上述第四步依次計(jì)算上述第三步生成的模式長(zhǎng)度為L(zhǎng)+1的候選模式集合cand_L+1中每個(gè)模式p_i的模式支持度sup(p_i,SDB)，當(dāng)sup(p_i,SDB)≥最小支持度閾值minsup時(shí)，添加到模式長(zhǎng)度為L(zhǎng)+1的頻繁模式集合fre_L+1中，并且按字母順序排列，由此獲得所有模式長(zhǎng)度為L(zhǎng)+1的頻繁模式集合fre_L+1；

第六步，一次性條件下帶弱通配符的自適應(yīng)序列模式挖掘結(jié)束：

當(dāng)上述第三步生成的模式長(zhǎng)度為L(zhǎng)+1的候選模式集合cand_L+1為空或當(dāng)上述第五步獲得的所有模式長(zhǎng)度為L(zhǎng)+1的頻繁模式集合fre_L+1為空時(shí)，頻繁模式挖掘完畢，由此，一次性條件下帶弱通配符的自適應(yīng)序列模式挖掘結(jié)束。