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

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

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

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

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

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

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

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

高級(jí)模式挖掘；最大模糊模式；模糊支持度；核心-牽引模式結(jié)構(gòu)；模糊修剪策略

0 引言

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

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

1 模糊模式結(jié)構(gòu)定義

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

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

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

(1)

(2)

(3)

(4)

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

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

圖1 FFP-Tree的構(gòu)建流程Fig. 1 FFP-Tree construction process

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

1) 頭節(jié)點(diǎn)，標(biāo)記為 “Root”。

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

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

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

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

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

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

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

Output: MFFPs

BEGIN

1)

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

2)

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

3)

構(gòu)建基于TDs數(shù)據(jù)集和核心項(xiàng)的FFP-Tree；

4)

構(gòu)建基于陣列結(jié)構(gòu)和條件模式基的FFP-array；

5

if 路徑pi是單路徑 then

6)

生成新的模式npi(通過檢查當(dāng)前路徑上的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結(jié)構(gòu)，在ai’s的條件模式樹上生成新的頻繁項(xiàng)集sfi；

14)

基于項(xiàng)目的模糊度對(duì)生成的sfi按照降序排序

15)

Call MFFP Mining(sfi,minmum_count_number,θ);

16)

endfor

17)

endif

18)

END

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

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

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

圖2 基于核心項(xiàng)集的FFP-TreeFig. 2 FFP-Tree construction based on base patterns

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

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

3 實(shí)驗(yàn)結(jié)果分析

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

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

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

圖3 最大模糊模式與傳統(tǒng)最大頻繁模式挖掘?qū)嶒?yàn)結(jié)果對(duì)比Fig. 3 Comparision of the experiment results between obtained MFFPs and obtained patterns from the traditional frequent pattern mining

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

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

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

obtained patterns from traditional frequent pattern mining

算法的空間復(fù)雜度的對(duì)比結(jié)果見圖5。從圖5可以看出，本文算法所采用的模式搜索策略和陣列技術(shù)大大降低了空間復(fù)雜度。根據(jù)空間復(fù)雜度結(jié)果分析，本文算法具有顯著的性能。算法FPMax*和PADS的空間復(fù)雜度情況非常相似，因?yàn)檫@兩種算法均采用了類FP-tree結(jié)構(gòu)。但是，這兩種算法與本文的算法性能具有巨大的差距。因此，為了能良好地顯示3種算法的空間復(fù)雜度對(duì)比，本文按照不同比例縮小了FPMax*和PADS算法的空間復(fù)雜度結(jié)果。根據(jù)圖5所反映的空間復(fù)雜度挖掘結(jié)果，相對(duì)稠密型數(shù)據(jù)集，本文提出的最大模糊模式挖掘與PADS和FPMax*算法在挖掘稀疏數(shù)據(jù)方面具有更大的優(yōu)越性。針對(duì)不同的數(shù)據(jù)集，本文算法可以優(yōu)化空間復(fù)雜度從一個(gè)數(shù)量級(jí)到兩個(gè)數(shù)量級(jí)不等。最大模糊模式挖掘耗費(fèi)較少的空間復(fù)雜度是因?yàn)樘岢隽诵藜糇訕浼糁Σ呗砸源_保更好地調(diào)度候選模式從而進(jìn)行較少的子模式檢測(cè)。在提出相應(yīng)的剪枝策略和模糊約束的基礎(chǔ)上，在已有的算法需要檢測(cè)的一些子模式并不需要在最大模糊模式算法中檢測(cè)。

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

4 結(jié)語

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

在今后的工作中，從醫(yī)學(xué)的角度，將會(huì)對(duì)比分析相對(duì)頻繁的疾病和相對(duì)較低的并發(fā)癥疾病的臨床資料，從而從醫(yī)學(xué)的角度驗(yàn)證提出的最大模糊模式對(duì)醫(yī)療疾病發(fā)現(xiàn)的有效性；從大數(shù)據(jù)知識(shí)發(fā)現(xiàn)的角度，將會(huì)探究核心-牽引項(xiàng)的模式結(jié)構(gòu)在高級(jí)知識(shí)挖掘中的作用，從而挖掘更優(yōu)的新結(jié)構(gò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對(duì)比序列模式挖掘[J]. 軟件學(xué)報(bào), 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的最大頻繁項(xiàng)目集挖掘改進(jìn)算法[J]. 計(jì)算機(jī)科學(xué), 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。

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

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

1001-9081(2017)05-1424-06

10.11772/j.issn.1001-9081.2017.05.1424

TP311.1

A