張海清，李代偉，劉胤田，龔 程，于 曦

(1.成都信息工程大學 軟件工程學院， 成都 610225； 2.成都大學 信息科學與工程學院,成都 610106)

最大模糊頻繁模式挖掘算法

張海清1，李代偉1，劉胤田1，龔 程1，于 曦2*

(1.成都信息工程大學 軟件工程學院， 成都 610225； 2.成都大學 信息科學與工程學院,成都 610106)

(*通信作者電子郵箱yuxi@cdu.edu.cn)

針對有效模式挖掘的組合爆炸及挖掘結果信息如何有效表達的問題，提出了一種基于“核心-牽引”結構的修剪候選模式和考慮項目不確定性的最大模糊模式挖掘算法(MFFP-Tree)。首先，綜合分析項目的模糊性，提出模糊支持度，分析項目在事務數(shù)據(jù)集中的模糊權重，依據(jù)模糊修剪策略修剪候選項集； 其次，僅掃描數(shù)據(jù)集一次，就能成功構建模糊模式挖掘樹，依據(jù)模糊剪枝策略減少模式提取的開銷, 采用FFP-array陣列結構使得搜索方式更精簡，從而進一步降低時空開銷。根據(jù)基準數(shù)據(jù)集的實驗結果，與最大模式挖掘算法PADS和FPMax*對比分析，MFFP-Tree挖掘出的最大模糊模式能夠更準確地反映項目與項目之間的關系；算法的時間復雜度能減半甚至低1個數(shù)量級；算法的空間復雜度降低1～2個數(shù)量級。

高級模式挖掘；最大模糊模式；模糊支持度；核心-牽引模式結構；模糊修剪策略

0 引言

大規(guī)模數(shù)據(jù)集中挖掘潛在有用但隱藏的信息是模式挖掘的主要目標。傳統(tǒng)的模式挖掘方法，主要包括Apriori[1]和 FP-growth[2]算法，并且這兩種算法的特征和性質已經被廣泛應用到其他改進的關聯(lián)規(guī)則的研究中[3-5]。隨著數(shù)據(jù)集的大規(guī)模增長，具有更高算法性能和滿足更多目標需求的算法不斷被提出，其中包括挖掘序列頻繁模式[6-7]、基于(無)閾值約束的Top-K頻繁模式[8-9]、基于數(shù)據(jù)流的頻繁模式[10-11]和基于加權的頻繁模式[12]等。上述頻繁模式挖掘方法均基于傳統(tǒng)的頻繁模式的先驗性質，頻繁項集的所有非空子集也一定是頻繁的，并且挖掘出的模式遵守約束條件，項目出現(xiàn)的頻度必須要大于指定閾值；然而，根據(jù)分析醫(yī)療大規(guī)模數(shù)據(jù)的實踐經驗得知，具有實踐指導意義的模式通常是相對頻繁的項目和出現(xiàn)頻率相對較低的項目的組合。例如，針對一個病人的診斷項目，病人所患的疾病通常涉及多個不同的科室，并且單個病人的患病特征集合一般由常見病特征和該病人“個性化”的疾病特征組成。因此，為了闡述大規(guī)模數(shù)據(jù)集所隱含的模式的復雜性，對頻繁項目和相對不頻繁的項目應該綜合分析。本文主要目的是為了發(fā)現(xiàn)與該疾病密切相關的其他疾病或者由該疾病最易誘發(fā)的其他疾病，而不僅僅是給出常見疾病之間的關聯(lián)性。

本文旨在規(guī)避挖掘具有欺騙性和誤導性的傳統(tǒng)模式的基礎上，在大規(guī)模動態(tài)數(shù)據(jù)集中提取最具代表性的模式。根據(jù)對文獻[1-11]的分析，如何提取最有效的最具代表性的模式并沒有得到良好論證，并且依據(jù)傳統(tǒng)強關聯(lián)規(guī)則所生成的一些頻繁模式、閉模式以及極大模式具有欺騙性和誤導性。相對傳統(tǒng)的頻繁模式挖掘，本文模式具有以下特性：本文中的項目的權重呈現(xiàn)模糊化而非精確值；本文挖掘的項目的獨立性以及提取的規(guī)則的形式不相同；本文所關注的項目規(guī)則對應的網絡和層次結構不相同。根據(jù)文獻[13-14]，項目的不確定性因素分析、數(shù)據(jù)的模糊化處理目前較為成功的解決方案為粗糙集理論和基于模糊集的模糊操作。而本文關注的不確定性問題是項目的模糊程度而非不可分辨關系，因此，采用模糊隸屬度函數(shù)描述項目與項目之間在單條事務中的關系、項目在整個集合中的相對關系、事務與整個集合的關系，從而，在理論和實驗上研究面向大規(guī)模醫(yī)療信息數(shù)據(jù)中隱藏的有價值的基礎模式，以此為依據(jù)引入核心項、牽引項以及模糊加權模式的概念，構建模糊最佳頻繁模式挖掘模型。

1 模糊模式結構定義

根據(jù)醫(yī)療數(shù)據(jù)集的特征分析，患者在一段時間內通常具有若干項主干疾病(核心項)和若干項由核心項所牽引的二階效應的項(牽引項)。例如，老年患者的疾病項目是：〈慢性咽炎，淋巴細胞百分數(shù)升高，消化不良，慢性支氣管炎〉，根據(jù)治療數(shù)據(jù)，該患者的慢性咽炎具有較高的危險等級，其他項目均為該項目的作用下所產生的二階效應項目。因此，本文挖掘的模糊模式定義為核心項 (base pattern, bp)和牽引項(second order effect pattern, sop)的組合。

根據(jù)核心項和牽引項之間的關系，挖掘的模糊模式的結構主要包含兩類：1) 所有特定的核心項目和全部(或者部分)牽引項一起出現(xiàn)。核心項目具有很高的模糊權重，從而具備較強吸附能力來吸附具有較低模糊權重的牽引項。2)部分特定的核心項和全部(或者部分)牽引項一起出現(xiàn)。核心項中某些項不具有較高的模糊權重，只有部分的核心項具有吸附牽引項的能力, 但是規(guī)則模式挖掘還是應該考慮不發(fā)生的核心項對整個核心項和整個事務的影響，因為不發(fā)生的核心項可能會減少或者改變核心項目的吸附能力以及吸附其他項目的活躍性。例如，在診斷患者出現(xiàn)嚴重流感現(xiàn)象時，即使在一段時間內病人并未出現(xiàn)發(fā)熱的情況，醫(yī)療記錄中還是要求必須標記病人的體溫狀況，同時該體溫項目也對其他的核心項有重要的影響?；谀：Ｊ降膬深惤Y構，本文給出模糊模式(Fuzzy Frequent Pattern, FFP)的定義。

定義1 模糊模式(FFP)。根據(jù)以上分析，本文挖掘的模糊模式可以定義為兩類：核心項(base pattern, bp)全部出現(xiàn)和其所吸附的牽引項(second order effect pattern, sop)；核心項部分出現(xiàn)(bp)、核心項中未出現(xiàn)的項(￢bp), 以及出現(xiàn)的核心項所牽引的項(sop)。模糊模式因此可被定義為式(1):

(1)

(2)

(3)

(4)

其中:核心項bp滿足的最小支持度閾值為minsup，核心項需要滿足的最小模糊權重閾值為σ，參數(shù)min_connect_sup用來定義核心項和二階效應項目之間的邊界，θ(θ≤σ)表示sop項目集的最小模糊權重閾值，ε定義為調節(jié)參數(shù)以根據(jù)挖掘模式數(shù)量的需要來個性化的設置變量變化范圍。其中，minsup、θ、min_connect_sup、σ的取值與傳統(tǒng)的支持度取值方式相同，針對不同的數(shù)據(jù)集，無法理論證明最佳的參與閾值，參數(shù)閾值均根據(jù)實驗數(shù)據(jù)來確定，本文的參數(shù)閾值分析見第3章。

最大模糊模式是模糊模式中沒有超集的項。挖掘最大模糊模式需要首先定義模糊模式挖掘樹。模糊模式挖掘樹反映事務數(shù)據(jù)集內部之間的關聯(lián)關系，并且將其挖掘結果記為FFP模式。FFP-Tree 管理和維護數(shù)據(jù)庫中不斷增加的事務集以及與之相關的項目綜合權重信息。本文將保留所有的核心項目，如果核心項的模糊權重小于閾值，那么該項目將會采用“￢”項的方式插入到FFP-Tree中，保留模糊權重小于閾值的項目的原因是這些項目仍然對核心所吸附的項目有影響，不出現(xiàn)的核心項目仍然會影響核心所吸附的項或者影響核心的吸附能力。除核心項以外的項目將會采用項目的模糊權重來判斷項目是否出現(xiàn)以及項目出現(xiàn)的強度。綜上，F(xiàn)FP-Tree 的結構定義見定義3。FFP-Tree的構建流程見圖1。

圖1 FFP-Tree的構建流程Fig. 1 FFP-Tree construction process

定義3 FFP-Tree(模糊模式挖掘樹)。模糊模式挖掘樹的結構包含以下4個部分：

1) 頭節(jié)點，標記為 “Root”。

2) 每個節(jié)點包含7個字段：項目名(item-name)、當前分支(branch-level)、父節(jié)點(parent)、子節(jié)點(children)、節(jié)點鏈(node-link)、模糊支持度(fuzzy support)、出現(xiàn)頻度(count number)和核心節(jié)點鏈接(node-link-base)。所有共享同一個節(jié)點名的節(jié)點用節(jié)點鏈連接，凡是包含相同核心項的分支采用自底向上的方式由核心節(jié)點鏈連接,并且事務項的綜合模糊度來自于所有節(jié)點的綜合模糊度和出現(xiàn)頻度的組合計算。為了表示每個項目的出現(xiàn)頻度，頻度數(shù)(count number)也作為一個字段。特別地，頭表當中的出現(xiàn)頻度表示了每一個項目在樹中出現(xiàn)的總頻數(shù)，在FFP-Tree中節(jié)點出現(xiàn)的頻數(shù)是該節(jié)點在當前路徑上的出現(xiàn)頻數(shù)。

3) 核心節(jié)點項目集(baseItems)。該字段主要用來記錄當前核心項目的信息，包含：當前核心項目名、當前未發(fā)生的核心項目、核心項目的頻數(shù)、模糊支持度以及核心節(jié)點鏈(node-link-base)的頭表。

4) 項目的頭表(header table)。 頭表主要放置項目集并且依據(jù)項目的模糊度值來降序排列。頭表主要包含兩個字段：頭表名(item-name)和節(jié)點鏈的頭節(jié)點(head of node-link)，并且該節(jié)點鏈由同一個節(jié)點名的鏈接來連接。

2 最大模糊頻繁模式挖掘算法

最大模糊頻繁模式(Maximal Fuzzy Frequent Pattern, MFFP)挖掘算法見算法1。最大模糊模式挖掘應該提供的參數(shù)有：模糊支持度值(fuzzy support value)、核心項(base patterns)、FFP-Tree和基于FFP-Tree 的陣列結構(FFP-array)。FFP-Tree的結構定義、核心項集的選擇策略、項目的模糊度值、以及項目的出現(xiàn)頻率閾值均作為最大模糊模式挖掘樹的優(yōu)化剪枝策略。其中，最大模糊模式核心項和牽引項的出現(xiàn)需要以下約束條件同時成立：(minsup

算法1 最大模糊模式挖掘(MFFP-Tree Mining)算法。

Input: 事務數(shù)據(jù)集TDs,允許出現(xiàn)的最小頻度minmum_count_number,項目的最小模糊支持度θ

Output: MFFPs

BEGIN

1)

計算模糊支持度SUP(i)并且重新對項目集合按照降序排列；

2)

采用動態(tài)模糊修剪策略來確定項目的核心項集bp；

3)

構建基于TDs數(shù)據(jù)集和核心項的FFP-Tree；

4)

構建基于陣列結構和條件模式基的FFP-array；

5

if 路徑pi是單路徑 then

6)

生成新的模式npi(通過檢查當前路徑上的bpi(all of the items {i} in pathpi)

7)

if(SUP(npi)≥θand superset_check(npi) is false)

8)

MFFP=MFFP∪npi;

9)

else

10)

記錄更新MFFP=MFFP∪bpi;

11)

else

12)

for each itemaiinTDs.header

13)

基于FFP-array結構，在ai’s的條件模式樹上生成新的頻繁項集sfi；

14)

基于項目的模糊度對生成的sfi按照降序排序

15)

Call MFFP Mining(sfi,minmum_count_number,θ);

16)

endfor

17)

endif

18)

END

根據(jù)算法1，如果當前路徑是單路徑(算法1中的第5)行)，則通過對當前路徑的項目超集檢測和當前項目的模糊支持度最小閾值檢測以確定新的npi模式。如果計算的模糊支持度大于等于最小閾值并且當前求取的模式并無超集，那么此時產生的MFFP模式即為求取的最大模糊模式(算法1

中的第6)～8)行);否則，當前求取的MFFP模式并不滿足最大模糊模式的求取條件，算法則選取具有強吸附力的核心項集作為當前路徑的最大模糊模式(算法1中的第10)行)。對于多路徑，基于FFP-array結構生成條件模式樹，并基于模糊度值對項目進行降序排列，然后依據(jù)項目頭表對新產生的核心項設置模糊度值，并遞歸調用該函數(shù)直到產生單路徑(算法1中的第12)～16)行)。

給定事務數(shù)據(jù)表1，依據(jù)模糊模式的構建流程(圖1)，構建FFP-Tree(見圖2)。

圖2 基于核心項集的FFP-TreeFig. 2 FFP-Tree construction based on base patterns

基于算法1，得到最大模糊模式為〈j,(h,b,o)〉、〈(m,b,o)〉, 其中，(h,b,o)、(m,b,o)為分支核具有較強的吸附力，且對其他項具有較強的吸附力。然而，依據(jù)傳統(tǒng)的最大頻繁模式挖掘算法[1-5, 15]，僅能夠挖掘得到最大頻繁模式〈j〉、〈m,b,o〉,并且挖掘得到的最大頻繁模式也不能夠反映項目與項目之間的重要關系。

表1 在θ=0.2和 minmum_count_number=2之下的樣例數(shù)據(jù)集Tab. 1 Sample Database under θ=0.2 and minmum_count_number=2

3 實驗結果分析

為了驗證本文算法的有效性，本章對比分析MFFP算法與傳統(tǒng)最大頻繁模式挖掘PADS和FPMax*算法的時間復雜度和空間復雜度。由于頻繁模式算法挖掘的時空復雜度通常由幾部分組成，而每個算法的組成部分均不相同，故通常對比算法的關鍵部分。例如，F(xiàn)P-Tree算法的時間復雜度包含：條件模式基、構造頭表、構造FP-Tree和FP-growth挖掘，而FP-growth是整個算法的核心，故進行算法性能分析時分析的是FP-growth的性能。同樣地，本文對比最大模糊模式算法、FPMax*,以及PADS的核心部分。對比的數(shù)據(jù)集包括真實數(shù)據(jù)集：Chess、Mushroom，以及人工數(shù)據(jù)集T10I4D100K 和 T40I10D100K(http://fimi.ua.ac.be/data/)，同時本文提供了一個新的Medical數(shù)據(jù)集(http://medical.witaction.com:808/medical)，該數(shù)據(jù)屬于稀疏數(shù)據(jù)集并且包含真實病人檢測出的疾病事務項。表2給出了數(shù)據(jù)集的特征。算法實驗平臺均采用2.20 GHz Pentium i7-3632QM處理器，8 GB內存，700 GB硬盤，操作系統(tǒng)為Windows 7, 所有算法均是采用 C++語言實現(xiàn)并在Microsoft Visual Studio 2010下面編碼實現(xiàn)。

表2 事務數(shù)據(jù)集的特征描述Tab. 2 Transaction dataset description

首先對Medical 數(shù)據(jù)集挖掘結果進行分析(見圖3)，當允許出現(xiàn)的核心項的最小模糊支持度(σ)和允許出現(xiàn)項的支持度(θ)間距增大時，那么挖掘出的醫(yī)療數(shù)據(jù)集會大幅度增加。

圖3 最大模糊模式與傳統(tǒng)最大頻繁模式挖掘實驗結果對比Fig. 3 Comparision of the experiment results between obtained MFFPs and obtained patterns from the traditional frequent pattern mining

當σ=0.6 和θ=0.15時，挖掘出的最大模糊模式的數(shù)量將會達到最高點，但是此時會產生一定數(shù)量的“假”模糊模式，因此，需要修改約束條件以提高挖掘模糊模式的有效性。同時，在參數(shù)σ=0.348和θ=0.05時，挖掘出的最大模糊模式的數(shù)量和質量是最佳的。同樣，通過探測修改參數(shù)閾值，該算法能夠探測到最佳挖掘點并且為其他的數(shù)據(jù)集挖掘到最大模糊模式。根據(jù)實驗結果分析，可以得出一般結論，對于稠密型數(shù)據(jù)集、核心項集和最大模糊模式的出現(xiàn)相對集中(特別是Chess 數(shù)據(jù)集)。該研究發(fā)現(xiàn)稠密數(shù)據(jù)集所隱藏的規(guī)律是較為集中和穩(wěn)定的，且稠密數(shù)據(jù)集的挖掘跟項目出現(xiàn)的頻度有強相關性，更改項目的模糊權重對稠密數(shù)據(jù)集影響不大。然而，稀疏數(shù)據(jù)集的最大模糊模式相對離散，需要多次探測才能夠確定最終的模糊模式。此外，通過實驗結果相比，傳統(tǒng)的頻繁模式挖掘、最頻繁模式挖掘以及閉頻繁模式的挖掘結果離實際需求有較大的差距, 說明新型模式挖掘需要增加考慮數(shù)據(jù)不確定性和離散性。

根據(jù)算法時間復雜度分析，提出的MFFP-Tree模糊模式挖掘算法比FPMax*和PADS算法具有最好的時間性能。由于模糊修剪策略的提出，即使參數(shù)模糊權重和項目的出現(xiàn)頻度驟增時，本文提出的最大模糊模式挖掘算法仍具有較低的運行時間增量。同時，在事務數(shù)據(jù)集的規(guī)模增大和項目出現(xiàn)的頻度閾值設定較小時，本文算法的優(yōu)越性更加顯著。對所有的數(shù)據(jù)集，算法FPMax*具有最差的時間性能，且當項目的出現(xiàn)頻度下降時，該算法的時間復雜度將會驟增。綜上，本文算法對實驗數(shù)據(jù)集具有最好的時間性能，針對不同的數(shù)據(jù)集分別降低時間復雜度一半甚至更低。算法的時間復雜度對比結果見圖4。

圖4 最大模糊模式與傳統(tǒng)最大頻繁模式挖掘時間復雜度對比Fig. 4 Comparison of runtime complexity between obtained MFFPs and

obtained patterns from traditional frequent pattern mining

算法的空間復雜度的對比結果見圖5。從圖5可以看出，本文算法所采用的模式搜索策略和陣列技術大大降低了空間復雜度。根據(jù)空間復雜度結果分析，本文算法具有顯著的性能。算法FPMax*和PADS的空間復雜度情況非常相似，因為這兩種算法均采用了類FP-tree結構。但是，這兩種算法與本文的算法性能具有巨大的差距。因此，為了能良好地顯示3種算法的空間復雜度對比，本文按照不同比例縮小了FPMax*和PADS算法的空間復雜度結果。根據(jù)圖5所反映的空間復雜度挖掘結果，相對稠密型數(shù)據(jù)集，本文提出的最大模糊模式挖掘與PADS和FPMax*算法在挖掘稀疏數(shù)據(jù)方面具有更大的優(yōu)越性。針對不同的數(shù)據(jù)集，本文算法可以優(yōu)化空間復雜度從一個數(shù)量級到兩個數(shù)量級不等。最大模糊模式挖掘耗費較少的空間復雜度是因為提出了修剪子樹剪枝策略以確保更好地調度候選模式從而進行較少的子模式檢測。在提出相應的剪枝策略和模糊約束的基礎上，在已有的算法需要檢測的一些子模式并不需要在最大模糊模式算法中檢測。

圖5 最大模糊模式挖掘與傳統(tǒng)最大頻繁模式挖掘空間復雜度對比Fig. 5 Comparison of memory usage between obtained MFFPs and obtained patterns from the traditional frequent pattern mining

4 結語

高級模式挖掘對潛在的隱藏信息發(fā)現(xiàn)和有用信息的恰當表達至關重要。本研究創(chuàng)新性地提出了模糊模式結構：核心項和相應的牽引項的組合，并且提出了模糊支持度以及基于模糊支持度的剪枝策略來分析和挖掘隱藏在項目集中的有用信息。為了分析最大模糊模式挖掘算法的有效性，本文對挖掘結果、時間和空間復雜度進行了對比分析，相對于PADS和FPMax*算法。結果表明，最大模糊模式考慮模糊權重來分析項目的不確定性從而更加準確地反映了項目與項目之間的關系。在時間復雜度方面，最大模糊模式挖掘算法比PADS和FPMax*算法快2倍至一個數(shù)量級。在空間復雜度方面，最大模糊模式挖掘算法比PADS和FPMax*算法優(yōu)越一個數(shù)量級至兩個數(shù)量級。根據(jù)挖掘的有效信息的數(shù)量和質量分析，該算法更適合處理頻繁項和出現(xiàn)次數(shù)較低的項目的組合。

在今后的工作中，從醫(yī)學的角度，將會對比分析相對頻繁的疾病和相對較低的并發(fā)癥疾病的臨床資料，從而從醫(yī)學的角度驗證提出的最大模糊模式對醫(yī)療疾病發(fā)現(xiàn)的有效性；從大數(shù)據(jù)知識發(fā)現(xiàn)的角度，將會探究核心-牽引項的模式結構在高級知識挖掘中的作用，從而挖掘更優(yōu)的新結構和發(fā)現(xiàn)更有效的新特征。

References)

[1] AGRAWAL R, IMIELINSKI T, SWAMI A. Mining association rules between sets of items in large databases[J].ACM SIGMOD Record, 1993, 22(2): 207-216.

[2] HAN J, PEI J, YIN Y, et al. Mining frequent patterns without candidate generation: a frequent-pattern tree approach[J]. Data Mining and Knowledge Discovery, 2004, 8(1): 53-87.

[3] TSENG V S, SHIE B E, WU C W, et al. Efficient algorithms for mining high utility itemsets from transactional databases[J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(8): 1772-1786.

[4] GRAHNE G, ZHU J. Fast algorithms for frequent itemset mining using FP-trees[J]. IEEE Transactions on Knowledge and Data Engineering, 2005, 17(10): 1347-1362.

[5] ZENG X, PEI J, WANG K, et al. PADS: a simple yet effective pattern-aware dynamic search method for fast maximal frequent pattern mining [J]. Knowledge and Information Systems, 2009, 20(3): 375-391.

[6] MUZAMMAL M, RAMAN R. Mining sequential patterns from probabilistic databases[C]// Proceedings of the 2011 Pacific-Asia Conference on Knowledge Discovery and Data Mining. Berlin: Springer, 2011: 210-221.

[7] AGGARWAL C, HAN J. Frequent Pattern Mining [M]. Berlin: Springer, 2014:19-61.

[8] ZHANG X, ZHANG Y. Sliding-window top-kpattern mining on uncertain streams[J]. Journal of Computational Information Systems, 2011, 7(3): 984-992.

[9] 楊皓, 段磊, 胡斌, 等. 帶間隔約束的 Top-k對比序列模式挖掘[J]. 軟件學報, 2015, 26(11): 2994-3009.(YANG H, DUAN L, HU B, et al. Mining Top-kdistinguishing sequential patterns with gap constraint[J]. Journal of Software, 2015, 26(11): 2994-3009.)

[10] CHEN H. Mining top-kfrequent patterns over data streams sliding window[J]. Journal of Intelligent Information Systems, 2014, 42(1): 111-131.

[11] ZIHAYAT M, AN A. Mining top-khigh utility patterns over data streams[J]. Information Sciences, 2014, 285(1): 138-161.

[12] YUN U, LEE G. Sliding window based weighted erasable stream pattern mining for stream data applications[J]. Future Generation Computer Systems, 2016, 59(C): 1-20.

[13] LI T. Fuzziness in systems modelling[J]. International Journal of General Systems, 2013, 42(1): 1-2.

[14] CHEN H, LI T, LUO C, et al. A decision-theoretic rough set approach for dynamic data mining[J]. IEEE Transactions on Fuzzy Systems, 2015, 23(6): 1958-1970.

[15] 牛新征, 余堃. 基于 FPMAX的最大頻繁項目集挖掘改進算法[J]. 計算機科學, 2013, 40(12): 223-228.(NIU X Z, SHE K. Mining maximal frequent item sets with improved algorithm of FPMAX [J]. Computer Science, 2013, 40(12): 223-228.)

This work is partially supported by the National Natural Science Foundation of China (61602064, 61502059), the Scientific Research Foundation of Chengdu University of Information Technology (KYTZ201615).

ZHANG Haiqing, born in 1986, Ph. D., lecturer. Her research interests include fuzzy set, decision making, data mining.

LI Daiwei, born in 1976, M. S. associate professor. His research interests include data integration and visualization, machine learning.

LIU Yintian, born in 1972, Ph. D., professor. His research interests include data integration and visualization, machine learning, data mining.

YU Xi, born in 1973, Ph. D., associate professor. His research interests include neural networks, decision making.

Mining algorithm of maximal fuzzy frequent patterns

ZHANG Haiqing1, LI Daiwei1, LIU Yintian1, GONG Cheng1, YU Xi2*

(1.CollegeofSoftwareEngineering,ChengduUniversityofInformationTechnology,ChengduSichuan610225,China;2.CollegeofInformationScienceandEngineering,ChengduUniversity,ChengduSichuan610106,China)

Combinatorial explosion and the effectiveness of mining results are the essential challenges of meaningful pattern extraction, a Maximal Fuzzy Frequent Pattern Tree Algorithm (MFFP-Tree) based on base-(second-order-effect) pattern structure and uncertainty consideration of items was proposed. Firstly, the fuzziness of items was analyzed comprehensively, the fuzzy support was given, and the fuzzy weight of items in the transaction data set was analyzed, the candidate item set was trimmed according to the fuzzy pruning strategy. Secondly, the database was scanned once to build FFP-Tree, and the overhead of pattern extraction was reduced based on fuzzy pruning strategy. The FFP-array structure was used to streamline the search method to further reduce the space and time complexity. The experimental results gained from the benchmark datasets reveal that the proposed MFFP-Tree has outstanding performance by comparing with PADS and FPMax*algorithms: the time complexity of the proposed algorithm is optimized by twice to one order of magnitude for different datasets, and the spatial complexity of the proposed algorithm is optimized by one order of magnitude to two orders of magnitude, respectively.

advanced pattern mining; maximum fuzzy pattern; fuzzy support; base-(second-order-effect) pattern structure; fuzzy pruning strategy

2016-10-08;

2016-12-23。

國家自然科學基金青年基金資助項目(61602064，61502059);成都信息工程大學科研基金資助項目(KYTZ201615)。

張海清(1986—)，女，山東聊城人，講師，博士研究生，主要研究方向：大數(shù)據(jù)分析; 李代偉 (1976—)，男，四川達縣人，副教授，碩士研究生，主要研究方向：數(shù)據(jù)集成與可視化、機器學習； 劉胤田(1972—)，男，四川隆昌人，教授，博士研究生，主要研究方向：數(shù)據(jù)挖掘；于曦(1973—)男，吉林長春人，副教授，博士研究生，主要研究方向：決策系統(tǒng)、神經網絡。

1001-9081(2017)05-1424-06

10.11772/j.issn.1001-9081.2017.05.1424

TP311.1

A