[發(fā)明專利]一種基于圖的存儲模式挖掘方法

無效

• 申請?zhí)枺?/td>: 201110040963.0
• 申請日: 2011-02-18
• 公開（公告）號: CN102096719A
• 公開（公告）日: 2011-06-15
• 發(fā)明（設(shè)計）人: 張敬亮;梁爽
• 申請（專利權(quán)）人: 中國科學(xué)院計算技術(shù)研究所;天津中科藍鯨信息技術(shù)有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京泛華偉業(yè)知識產(chǎn)權(quán)代理有限公司 11280
• 代理人: 王勇

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

本發(fā)明涉及存儲模式挖掘，尤其涉及基于圖的存儲模式挖掘方法。

背景技術(shù)

應(yīng)用數(shù)據(jù)集及存儲系統(tǒng)規(guī)模的不斷擴大對模式分析的效率提出了極高的要求。但現(xiàn)有存儲模式挖掘基于數(shù)據(jù)挖掘領(lǐng)域中的序列模式SP(Sequential?Pattern)(參見SP定義)方法進行。現(xiàn)有挖掘方法的巨大開銷使其難以在實際系統(tǒng)中應(yīng)用。這是因為SP模式基于元素間相關(guān)性來定義，而對序列中相關(guān)性的挖掘是一個NP難題(NP-hard)，隨著問題規(guī)模增大，模式挖掘的時空性能急劇惡化。因而其對大規(guī)模數(shù)據(jù)密集型應(yīng)用場景中的存儲模式挖掘無能為力，更無法滿足基于存儲模式的實時優(yōu)化需求。基于SP的存儲模式挖掘方法的局限性表現(xiàn)為如下兩個方面：

1.時空開銷大：由于模式中松耦合關(guān)系的定義以及無法避免的對原始序列的多遍掃描，導(dǎo)致了相應(yīng)的挖掘方法有很高的時空復(fù)雜度。更為嚴重的是，隨著問題規(guī)模擴大，方法的時空開銷會呈現(xiàn)指數(shù)劇增。因而對于大規(guī)模實際存儲系統(tǒng)而言，以往挖掘方法的時空開銷導(dǎo)致其基本無法應(yīng)用。

2.無法支持在線流式挖掘：SP模式的挖掘方式為對序列數(shù)據(jù)庫的整體挖掘而非增量式挖掘。因而在原始序列發(fā)生變化時不能在之前挖掘模式的基礎(chǔ)上進行模式的增量更新挖掘。基于上述局限性，當前SP方法大都采用靜態(tài)挖掘方式，將長時間累積的IO序列通過集中挖掘的方式來進行整體模式更新。在海量IO序列信息面前，集中模式挖掘的方式代價高昂，無法支持存儲系統(tǒng)中實時在線優(yōu)化的需求。

另外，與傳統(tǒng)數(shù)據(jù)挖掘不同，存儲模式挖掘的目標在于將模式應(yīng)用于后續(xù)的性能優(yōu)化，因而其不要求結(jié)果精確(比如頻度精確)，而只要對優(yōu)化有效即可(頻繁出現(xiàn)即可)。同時因為利用模式進行性能優(yōu)化時模式挖掘處于IO關(guān)鍵路徑中，因而要求模式挖掘的效率高且時空復(fù)雜度低。緊鄰序列模式CISP(Contiguous?Item?Sequential?Pattern)(參見CISP定義)的挖掘方法雖然對于SP模式進行了簡化，但要求所挖掘出的模式頻度也是精確的，雖然可以部分縮減挖掘空間，但其仍是類SP模式的挖掘方法，所以在對大規(guī)模數(shù)據(jù)密集型應(yīng)用場景中的存儲模式挖掘中仍然無法解決上述問題。

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

本發(fā)明的目的在于克服上述現(xiàn)有技術(shù)的缺陷，提供一種適合大規(guī)模數(shù)據(jù)密集應(yīng)用的存儲模式挖掘方法，并且可以支持在線流式挖掘。

本發(fā)明的目的是通過以下技術(shù)方案實現(xiàn)的：

本發(fā)明提出了一種基于圖的存儲模式挖掘方法FPG-Grow(FrequentPattern?Graph-Grow)，包括以下步驟：

(a)基于原始序列來構(gòu)建頻繁模式圖FPG(Frequent?Pattern?Graph)，其中所述原始序列是信息元素的有序集合；所述頻繁模式圖的節(jié)點集合是由具有相同長度的片段的集合構(gòu)成的，所述片段是原始序列的子序列，所述頻繁模式圖的邊是有后繼關(guān)系的兩個片段之間的有向邊，所述有后繼關(guān)系的兩個片段是指后片段的頭元素為先片段頭元素的后繼；邊的頻度，為此后繼關(guān)系在原始序列中出現(xiàn)的總次數(shù)；

(b)從所述頻繁模式圖中未被訪問的邊集合中選取頻度最高的邊；

(c)沿所述頻度最高的邊向兩側(cè)進行模式擴展，直到不能滿足模式生長條件為止；

(d)重復(fù)步驟(b)(c)直到所有頻度大于最小閾值的邊都被訪問過為止。

根據(jù)本發(fā)明優(yōu)選實施例的基于圖的存儲模式挖掘方法，在所述步驟(a)中的所述頻繁模式圖是由原始序列和片段的長度唯一確定的，所述片段的長度可以根據(jù)實際應(yīng)用模式的特點或用戶需求進行設(shè)置，但必須是大于1的正整數(shù)。

根據(jù)本發(fā)明優(yōu)選實施例的基于圖的存儲模式挖掘方法，在所述步驟(d)中的所述最小閾值可以根據(jù)實際應(yīng)用模式的特點，用戶需求或內(nèi)存容量進行設(shè)置，但不應(yīng)低于1。

根據(jù)本發(fā)明優(yōu)選實施例的基于圖的存儲模式挖掘方法，在所述步驟(c)中的所述模式生長條件是指相鄰的兩條邊的權(quán)重之和與這兩條邊的共同節(jié)點的所有邊的權(quán)重總和之間的比值大于給定的閥值。在一些實施例中，所述給定的閥值是可設(shè)置的，但必須大于0.5。在本發(fā)明的優(yōu)選實施例中所述給定的閥值為0.85。

根據(jù)本發(fā)明優(yōu)選實施例的基于圖的存儲模式挖掘方法，所述步驟(a)基于原始序列來構(gòu)建頻繁模式圖包括以下步驟：

(1)為原始序列設(shè)置滑動指針，指向原始序列的初始位置；

(2)從滑動指針所指原始序列位置截取長度為L的片段，將所述片段加入頻繁模式圖的節(jié)點集合，并設(shè)置該片段為頻繁模式圖的當前節(jié)點；

(3)滑動指針向前滑動一位；