[發(fā)明專利]一種對比序列模式挖掘方法和裝置

在審

• 申請?zhí)枺?/td>: 201710702245.2
• 申請日: 2017-08-16
• 公開（公告）號: CN107451293A
• 公開（公告）日: 2017-12-08
• 發(fā)明（設(shè)計）人: 王慧鋒;王曉通;郭鋒
• 申請（專利權(quán)）人: 鄭州云海信息技術(shù)有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京安信方達知識產(chǎn)權(quán)代理有限公司11262
• 代理人: 李紅爽,李丹

技術(shù)領(lǐng)域

本發(fā)明涉及數(shù)據(jù)分析技術(shù)，尤指一種對比序列模式挖掘方法和裝置。

背景技術(shù)

序列模式挖掘作為數(shù)據(jù)挖掘的一項重要任務(wù)，有著廣泛的應(yīng)用。例如：廣電服務(wù)商分析用戶的收視紀錄，發(fā)現(xiàn)用戶的收視喜好，可為節(jié)目編排提供決策支持。與此同時，序列模式挖掘也受到了眾多研究者的關(guān)注，不同類型的序列模式被陸續(xù)提出，如：頻繁序列模式，閉合序列模式，對比序列模式，周期模式，偏序模式等。

給定兩類序列樣本集合，對比序列模式描述在正類序列樣本集合中頻繁(模式的支持度大于指定閾值)，且在負類序列樣本集合中不頻繁(模式的支持度小于指定閾值)的項集。對比序列模式能識別不同類別序列樣本集合間的差異，并描述各類別樣本集合的特征，因此適用于多個領(lǐng)域的序列數(shù)據(jù)分析。例如：在商業(yè)領(lǐng)域，對比不同年齡段顧客的購物行為，發(fā)現(xiàn)各年齡段顧客的購物模式，可以提高商品促銷活動的針對性。

在已有對比序列模式挖掘研究中，主要是針對兩類序列樣本集合，缺乏一種對比序列模式多類別挖掘機制，限制了對數(shù)據(jù)的更深入分析與利用。

發(fā)明內(nèi)容

為了解決上述技術(shù)問題，本發(fā)明提供了一種對比序列模式挖掘方法和裝置。

為了達到本發(fā)明目的，本發(fā)明提供了一種對比序列模式挖掘方法，包括：

收集多類序列樣本數(shù)據(jù)；

計算對比序列模式在所述多類序列樣本數(shù)據(jù)構(gòu)成的數(shù)據(jù)集中出現(xiàn)的頻繁程度；

根據(jù)所述多類序列樣本數(shù)據(jù)構(gòu)成的數(shù)據(jù)集中出現(xiàn)的頻繁程度，計算所述對比序列模式在支持度范圍內(nèi)的對比度；

挖掘得到基于所述多類序列樣本數(shù)據(jù)的對比序列模式。

優(yōu)選的，計算對比序列模式在所述多類序列樣本數(shù)據(jù)構(gòu)成的數(shù)據(jù)集中出現(xiàn)的頻繁程度的步驟具體為：

根據(jù)以下公式計算在所述多類序列樣本數(shù)據(jù)構(gòu)成的數(shù)據(jù)集中出現(xiàn)的頻繁程度：

sup(P，D_i)＝|{S|S∈D_i且P在S中出現(xiàn)}|/|D_i|，

其中，多類序列樣本數(shù)據(jù)D＝{D₁，D₂，…，D_k}，k表示序列數(shù)據(jù)的類別，對比序列模式P＝I₁I₂I₃…I_|P|描述在一類序列樣本數(shù)據(jù)中頻繁出現(xiàn)而在其他類序列樣本數(shù)據(jù)中非頻繁的模式。

優(yōu)選的，根據(jù)所述多類序列樣本數(shù)據(jù)構(gòu)成的數(shù)據(jù)集中出現(xiàn)的頻繁程度，計算所述對比序列模式在支持度范圍內(nèi)的對比度的步驟包括：

設(shè)定間隔約束gap∈[0.g]，其中，g表示對比序列模式中各元素在序列樣本中出現(xiàn)位置的間隔；

設(shè)定支持度范圍，所述支持度范圍包含閾值上限α和下限β；

根據(jù)以下公式計算對比序列模式在序列樣本數(shù)據(jù)集中滿足上限α的對比度：

根據(jù)以下公式計算對比序列模式在序列樣本數(shù)據(jù)集中滿足下限β的對比度：

優(yōu)選的，對所述對比序列模式P的定義包括：

(1)contrast(P|α，g)>γ，其中，α∈(0，1)，γ∈(0，1)；

(2)contrast(P|β，g)<η，其中β∈(0，1)，η∈(0，1)；

(3)模式最小化。

優(yōu)選的，挖掘得到基于所述多類序列樣本數(shù)據(jù)的對比序列模式的步驟包括：

采用深度優(yōu)先的方式生成集合枚舉樹，對于集合枚舉樹中的第一層節(jié)點，通過讀取序列樣本集合D，枚舉D中個元素的位置獲得；

如果某節(jié)點N滿足所述第一定義要求，則將該節(jié)點的子孫節(jié)點全部移除；

如果某節(jié)點N保存的候選模式P的contrast(P|α，g)＝0則將該節(jié)點及其子孫節(jié)點全部移除。

本發(fā)明還提供了一種對比序列模式挖掘裝置，包括：

樣本收集模塊，用于收集多類序列樣本數(shù)據(jù)；

差異對比模塊，用于計算對比序列模式在所述多類序列樣本數(shù)據(jù)構(gòu)成的數(shù)據(jù)集中出現(xiàn)的頻繁程度；

對比度計算模塊，用于根據(jù)所述多類序列樣本數(shù)據(jù)構(gòu)成的數(shù)據(jù)集中出現(xiàn)的頻繁程度，計算所述對比序列模式在支持度范圍內(nèi)的對比度；

對比序列模式生成模塊，用于挖掘得到基于所述多類序列樣本數(shù)據(jù)的對比序列模式。

優(yōu)選的，所述差異對比模塊，具體用于根據(jù)以下公式計算在所述多類序列樣本數(shù)據(jù)構(gòu)成的數(shù)據(jù)集中出現(xiàn)的頻繁程度：