基于約束的序列模式關(guān)聯(lián)規(guī)則挖掘算法

張 鈺,劉玉文

(蚌埠醫(yī)學(xué)院,安徽 蚌埠 233000)

基于約束的序列模式關(guān)聯(lián)規(guī)則挖掘算法

張 鈺,劉玉文

(蚌埠醫(yī)學(xué)院,安徽 蚌埠 233000)

約束關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘的一個(gè)主要方向,可以根據(jù)用戶給定的約束條件針對(duì)性的挖掘．目前大多數(shù)的研究都集中在約束頻繁項(xiàng)集挖掘方面,很少進(jìn)行序列模式的約束關(guān)聯(lián)挖掘．本文把序列模式和約束進(jìn)行結(jié)合,提出一種基于約束的序列模式關(guān)聯(lián)規(guī)則挖掘算法．它同時(shí)處理兩類(lèi)約束:反單調(diào)性約束和單調(diào)性約束．可以根據(jù)約束條件挖掘數(shù)據(jù)間的因果關(guān)聯(lián)關(guān)系．通過(guò)實(shí)驗(yàn)驗(yàn)證,該算法在運(yùn)行效率上達(dá)到了較好效果．

序列;單調(diào)性約束;反單調(diào)性約束;約束頻繁項(xiàng)集;序列關(guān)聯(lián)規(guī)則

1 預(yù)備知識(shí)

序列模式關(guān)聯(lián)規(guī)則[1]主要描述數(shù)據(jù)之間的前后或因果關(guān)系,要求各事件按照發(fā)生時(shí)間的先后次序進(jìn)行登記,形成一個(gè)事件序列,然后在序列的基礎(chǔ)上進(jìn)行關(guān)聯(lián)規(guī)則挖掘．在商業(yè)領(lǐng)域,序列模式關(guān)聯(lián)規(guī)則可以用來(lái)預(yù)測(cè)顧客的購(gòu)買(mǎi)行為,優(yōu)化商品銷(xiāo)售策略,促進(jìn)商品銷(xiāo)售．例如A?B,這條規(guī)則表示顧客購(gòu)買(mǎi)了商品A之后,往往會(huì)接著購(gòu)買(mǎi)商品B．然而序列模式關(guān)聯(lián)挖掘只能找出數(shù)據(jù)間的前后關(guān)系,在通常情況下會(huì)出現(xiàn)3個(gè)問(wèn)題:1)可能產(chǎn)生大量不相關(guān)或不感興趣的規(guī)則;2)用戶不能參與到挖掘過(guò)程中,不能進(jìn)行聚焦式的挖掘;3)關(guān)聯(lián)性定義只依賴(lài)于支持度和置信度,沒(méi)有相關(guān)約束條件．所以本文提出一個(gè)基于約束的序列模式關(guān)聯(lián)挖掘算法,允許用戶通過(guò)設(shè)置相關(guān)約束參數(shù)來(lái)進(jìn)行序列模式的挖掘．該算法包括3個(gè)步驟:第一步把數(shù)據(jù)按時(shí)間進(jìn)行排序,轉(zhuǎn)換成序列模式事務(wù)數(shù)據(jù)庫(kù)．第二步挖掘符合約束條件的頻繁序列;第三步產(chǎn)生關(guān)聯(lián)規(guī)則．

文獻(xiàn)[2]提出了一個(gè)序列模式正負(fù)關(guān)聯(lián)規(guī)則挖掘算法,討論了序列模式關(guān)聯(lián)規(guī)則的挖掘過(guò)程．文獻(xiàn)[3]提出了一種基于約束的關(guān)聯(lián)規(guī)則挖掘算法,該算法給出了一個(gè)基于FP-Growth約束處理方法,FP-Growth不產(chǎn)生候選項(xiàng)集,提高了挖掘效率,但在序列模式頻繁項(xiàng)集挖掘方面FP-Growth顯得無(wú)能為力．文獻(xiàn)[4]給出了一種松散的反單調(diào)性約束,并在Apriori基礎(chǔ)上實(shí)現(xiàn)了算法,但是由于Apriori的固有缺陷,導(dǎo)致算法效率不高．文獻(xiàn)[5]提出了一個(gè)帶通配符和One-Off條件的序列模式挖掘算法,該算法設(shè)計(jì)了一種有效的帶有通配符的模式挖掘算法,模式在序列中的出現(xiàn)滿足One-Off條件,使得模式的任意兩次出現(xiàn)都不共享序列中同一位置的字符．

2 基本概念和定義

定義1[2](序列)指按發(fā)生時(shí)間先后排成一列的對(duì)象或事件．

設(shè)I是事件的集合,I={i1,i2,…,in},in表示事件稱(chēng)為項(xiàng)．由k個(gè)項(xiàng)組成的序列稱(chēng)為k-序列．設(shè)序列a和序列b,如果存在i1

Supp(S)≥min-sup,則稱(chēng)S為頻繁序列．頻繁序列中滿足最小置信度的關(guān)聯(lián)規(guī)則稱(chēng)為序列模式關(guān)聯(lián)規(guī)則．

定義2[3](約束)作用于項(xiàng)I的約束可以看成一個(gè)謂詞,表示為C:2I→{True,False}．一個(gè)序列X滿足約束C,當(dāng)且僅當(dāng)C(X)=True．

定義3 (約束集)指由n個(gè)約束組成的集合,表示為SC={C1,C2,…,Cn}．一個(gè)序列X滿足約束集SC(即:SC(X)=True),當(dāng)且僅當(dāng)C1(X)∧C2(X)∧…∧Cn(X)=True．

定義4 (多維約束)指作用于多維屬性上的約束．

多維屬性是指一個(gè)項(xiàng)有多個(gè)屬性．比如把一個(gè)商品看成是一個(gè)項(xiàng),該商品有若干個(gè)屬性,如成本、價(jià)格等．

定義5[3](反單調(diào)性約束)給定一個(gè)約束C,如果序列X不滿足C,X的任一超集也不滿足C,則稱(chēng)C為反單調(diào)性約束．

定義6[3](單調(diào)性約束)給定一個(gè)約束C,如果序列X滿足C,X的任一超集也滿足C,則稱(chēng)C為單調(diào)性約束．

定義7 (約束頻繁序列)給定一個(gè)約束集SC,對(duì)于序列X,如果SC(X)=True,且支持度大于最小支持度閾值,則稱(chēng)X為約束頻繁序列．

3 基于約束的序列模式關(guān)聯(lián)規(guī)則挖掘算法

3.1 算法的基本思想

本算法同時(shí)處理兩類(lèi)約束,即反單調(diào)性約束和單調(diào)性約束．首先把數(shù)據(jù)庫(kù)轉(zhuǎn)換成序列模式事務(wù)數(shù)據(jù)庫(kù),然后產(chǎn)生序列模式約束頻繁項(xiàng)集,最后產(chǎn)生規(guī)則．以表1和表2所列的數(shù)據(jù)為例來(lái)說(shuō)明算法思想．

表1 事務(wù)數(shù)據(jù)庫(kù)D

表2 事務(wù)數(shù)據(jù)庫(kù)D中的項(xiàng)及其屬性

事務(wù)數(shù)據(jù)庫(kù)D是以UID為關(guān)鍵字,并按時(shí)間先后登記的數(shù)據(jù)集合,首先要把它轉(zhuǎn)換成序列模式事務(wù)數(shù)據(jù)庫(kù)．另外,我們考慮兩類(lèi)具體的約束形式:(1)max(S.cost)≤min(S.price);(2)total(S.price)≥100．其中S是序列,cost和price是S中項(xiàng)的兩個(gè)屬性．max(S.cost)指在S中屬性cost最大的項(xiàng)．min(S.price)指S中屬性price最小的項(xiàng)．顯然,第(1)個(gè)約束是反單調(diào)性約束,第(2)個(gè)約束是單調(diào)性約束．用C1代表約束max(S.cost)≤min(S.price),用C2代表約束total(S.price)≥100,則約束集SC={C1,C2}．算法的結(jié)果是輸出符合約束集SC的頻繁序列．

引理1 設(shè)序列X和Y,Y?X,C1為反單調(diào)性約束,如果C1(Y)=False,則C1(X)=False．

證明:由于Y?X,而C1為反單調(diào)性約束,由反單調(diào)性約束的定義可以得到結(jié)論．

引理2 設(shè)序列X和Y,Y?X,C1為反單調(diào)性約束,如果C1(X)=True,則C1(Y)=True．

引理2的證明和引理1相似．

引理3 設(shè)序列X和Y,Y?X,C2為單調(diào)性約束,如果C2(Y)=True,則C2(X)=True．

證明:由于Y?X,而C2為單調(diào)性約束,由單調(diào)性約束的定義可以得到結(jié)論．

引理4 設(shè)序列X和Y,Y?X,C2為單調(diào)性約束,如果C2(X)=False,則C2(Y)=False．

引理4的證明和引理3相似．

定理1 設(shè)X,Y是兩序列,Y?X,C1和C2分別為反單調(diào)性約束和單調(diào)性約束．(1)如果C1(Y)=False,則C1(X)∧C2(X)=False．(2)如果C1(Y)=True,則可能存在C1(X)∧C2(X)=True．

證明:(1)因?yàn)閅?X,由引理1可知C1(X)=False,所以C1(X)∧C2(X)=False．(2)因?yàn)閅?X,如果C1(Y)=True,且C1為反單調(diào)性約束,所以可能存在C1(X)=True;又因?yàn)镃2為單調(diào)性約束,也可能存在C2(X)=True,所以可能存在C1(X)∧C2(X)=True．

利用定理1可以有效地減少候選序列的產(chǎn)生．

例如,序列ABC和序列ABD,如果C1(ABC)∧C1(ABD)∧C1(CD)=True,則序列ABCD可能滿足C1(ABCD)=True．

產(chǎn)生候選序列是本文算法的主要的步驟之一,很多文獻(xiàn)對(duì)候選序列的產(chǎn)生提出了改進(jìn)方法．本文采用文獻(xiàn)[6]的方法,首先把頻繁(k-1)-序列按照字典順序排序,對(duì)2個(gè)頻繁(k-1)-序列X和Y(X

3.2 算法描述

基于約束的序列模式關(guān)聯(lián)規(guī)則挖掘算法的核心是約束頻繁序列的挖掘,其挖掘步驟如下:

Step1 產(chǎn)生頻繁1-項(xiàng)集．

Step2 客戶序列轉(zhuǎn)換成序列模式事務(wù)數(shù)據(jù)庫(kù)．

Step3 產(chǎn)生頻繁1-序列．

Step4 調(diào)用算法2產(chǎn)生滿足約束C1的候選k-序列．

Step5 計(jì)算每個(gè)候選k-序列的支持度,如果大于最小支持度閾值,則為滿足約束C1的頻繁k-序列,并入Sk．

Step6 把Sk中滿足約束C2的k-序列并入SPk中．

Step7 跳轉(zhuǎn)到Step4,直到無(wú)法產(chǎn)生候選序列為止．

Step8 合并SPk得到所有滿足約束C1和C2的頻繁序列SP．

算法1

輸入:數(shù)據(jù)庫(kù)D,最小支持度min-sup,反單調(diào)性約束C1:max(S.cost)≤min(S.price),單調(diào)性約束C2:total(S.price)≥100．

輸出:所有同時(shí)滿足C1和C2的頻繁序列．

(1)S1=frequent 1-sequences

(2)For(k=2;Sk-1≠0;k++)Do begin

(3)Ck=Apriori-gen(Sk-1,C1,min-sup)//調(diào)用算法2產(chǎn)生候選k-序列

(4)For each custormer-sequence t∈D Do begin

(5)Ct=subset(Ck,t)

(6)For each candidate c∈Ct

(7)c.count++

(8)End For

(9)Sk={c∈Ck|c.count≥min-sup}

(10)SPk={s∈Sk|C2(s)=True}//得到滿足C1和C2的頻繁k-序列

(11)End For

(12)Answer=UkSPk

算法2

(1)Function Aprori-gen(Sk-1,C1,min-sup)

(2)For each lx∈Sk-1Do begin

(3)For each ly∈Sk-1∧ly>lxDo begin

(4)If lx[1]=ly[1]∧lx[2]=ly[2]∧…∧lx[k-2]=ly[k-2]∧lx[k-1]

(5)If C1(lx[k-1]∞ly[k-1])=True Then

(6)c=lx∞ly

(7)If(C1(c)=True) Then Ck=c∪Ck//lx和ly滿足C1,根據(jù)推論1僅需判斷c是否滿足C1．

(8)End If

(9)else Break//lx與ly后面的序列都不能連接,跳出此次循環(huán)．

(10)End If

(11)End for

(12)End for

(13)Return Ck;

(14)End Function

3.3 例題分析

以表1提供的數(shù)據(jù)庫(kù)為例,反單調(diào)性約束C1:max(S.cost)≤min(S.price),單調(diào)性約束C2:total(S.price)≥100,最小支持度為20%．

(1)求出頻繁1-項(xiàng)集．L1={A,B,C,D,E}．

(2)產(chǎn)生序列模式事務(wù)數(shù)據(jù)庫(kù)．

以UID為關(guān)鍵字產(chǎn)生用戶的序列模式事務(wù)數(shù)據(jù)庫(kù)SD,表3所示．

表3 序列模式事務(wù)數(shù)據(jù)庫(kù)SD

方括號(hào)[]表示序列的一個(gè)項(xiàng),其包含的子項(xiàng)表示在同一時(shí)間內(nèi)產(chǎn)生的事件．比如[(A),(B),(A,B)]表示用戶在一次購(gòu)買(mǎi)中,同時(shí)買(mǎi)了A和B．

(3)產(chǎn)生頻繁1-序列

掃描序列模式事務(wù)數(shù)據(jù)庫(kù)SD得到頻繁1-序列S1={(A),(B),(C),(D),(E)}．

(4)產(chǎn)生約束頻繁2-序列

根據(jù)S1,求得頻繁序列S2={(BC),(BD), (BE),(CD),(CE),(DE)},由于C1(DE)=False,所以刪除DE得到S2={(BC),(BD),(BE),(CD),(CE)},其中除BD之外均滿足C2,得到滿足約束集SC={C1,C2}的約束頻繁序列SP2={(BC),(BE),(CD),(CE)}．

(5)產(chǎn)生約束頻繁3-序列

根據(jù)S2和推論1,由于C1(DE)=False,所以BD和BE及CD和CE均不滿足鏈接條件,最后得到候選3-序列C3={(BCD), (BCE)},掃描事務(wù)數(shù)據(jù)庫(kù),求得頻繁序列S3={(BCD),(BCE)},又因?yàn)镃1(BCD)∧C2(BCD)=True及C1(BCE)∧C2(BCE)=True,所以得到約束頻繁3-序列SP3={(BCD),(BCE)}．

(6)產(chǎn)生約束頻繁4-序列

根據(jù)S3和推論1,由于C1(DE)=False,所以BCD和BCE不滿足鏈接條件．

(7)最后,得到滿足約束集SC={C1,C2}的所有約束頻繁序列SP={(BC),(BE),(CD),(CE),(BCD),(BCE)}．

4 實(shí)驗(yàn)分析

為了測(cè)試算法性能,測(cè)試數(shù)據(jù)選擇文獻(xiàn)[5]提供的數(shù)據(jù),并選擇文獻(xiàn)[3]中的MCAL算法作為比較對(duì)象．在AMDathlon64 8000MHz,2GRAM,WinXP,C#環(huán)境下實(shí)現(xiàn)了本文算法和MCAL算法．為了表達(dá)方便,本文算法用CSAR表示．二者比較如下:

支持度設(shè)為20%時(shí),圖1顯示隨著交易數(shù)量的增加,兩者挖掘時(shí)間也隨之增加,但CSAR算法要明顯優(yōu)于MCAL算法,因?yàn)镸CAL算法在頻繁項(xiàng)集鏈接時(shí)產(chǎn)生大量候選項(xiàng)集,而且計(jì)算頻繁項(xiàng)集時(shí)多次掃描數(shù)據(jù)庫(kù),浪費(fèi)了運(yùn)行時(shí)間．而CSAR算法對(duì)候選項(xiàng)集進(jìn)行了有效剪枝,提高了運(yùn)行效率．

圖1 隨著交易數(shù)量的增加兩種算法運(yùn)行時(shí)間對(duì)比

圖2 隨著最小支持度的變化兩種算法運(yùn)行時(shí)間對(duì)比

圖2顯示當(dāng)最小支持度大于32%時(shí),CSAR的運(yùn)算時(shí)間多于MCAL,但當(dāng)最小支持度小于32%時(shí)CSAR的挖掘時(shí)間要明顯小于MCAL,這是因?yàn)殡S著支持度的減小,頻繁項(xiàng)集的數(shù)量就會(huì)增加,從而會(huì)挖掘出大量長(zhǎng)項(xiàng)集．因此在長(zhǎng)項(xiàng)集挖掘方面CSAR要優(yōu)于MCAL．

5 結(jié)語(yǔ)

本文給出了約束和序列模式的基本概念,并將兩者結(jié)合應(yīng)用在關(guān)聯(lián)規(guī)則挖掘過(guò)程中,可以根據(jù)用約束條件針對(duì)性的挖掘數(shù)據(jù)間之間的因果關(guān)聯(lián)關(guān)系．通過(guò)實(shí)驗(yàn)分析,該算法在運(yùn)行效率上有較好的性能．但在異構(gòu)數(shù)據(jù),多關(guān)系、分布式數(shù)據(jù)的約束挖掘是今后研究的一個(gè)主要方向．

[1] Agrawal R, Imielinski T, Swami A. Mining Association Rules between Sets of Items in Large Database[C]//Proceedings of the ACM SIGMOD Conference on Management of Data. Washington, USA: ACM Press, 1993

[2] 郭躍斌,翟延富,董祥軍,等.基于序列模式的正負(fù)關(guān)聯(lián)規(guī)則研究[J].山東大學(xué)學(xué)報(bào)(理學(xué)版),2007,42 (9): 88-90

[3] 李廣原,楊炳儒,周如旗.一種基于約束的關(guān)聯(lián)規(guī)則挖掘算法[J].計(jì)算機(jī)科學(xué),2012,39(1):244-247

[4] bonchi F,Lucchese C.Trasarti R.Pushing tougher constraints in frequent pattern mining[C]//9th Pacific-Asia Conference on Knowledge Discovery and data Mining.Hanoi,Vietnam,May 2005

[5] 吳信東,謝 飛,黃詠明,等.帶通配符和One-Off條件的序列模式挖掘[J].軟件學(xué)報(bào), 2013,24(8):1804-1815[6] 催貫勛,李 梁,王柯柯,等.關(guān)聯(lián)規(guī)則挖掘中Apriori算法的研究與改進(jìn)[J].計(jì)算機(jī)應(yīng)用,2010,30(11):2952-2955

[7] 宋余慶,朱玉全,孫志揮,等.基于FP-tree的最大頻繁項(xiàng)目集挖掘及更新算法[J].軟件學(xué)報(bào),2003,14(9):1586-1592

[8] Anthony J,Lin Wan-chuen.Mining association rules with multi-dimensional constraints[J].The Journal of Systems and Software,2006(79):79-92

Sequential Pattern Algorithm of Association Rules Based on Constraint

Zhang Yu, Liu Yuwen

(Computer Department,Bengbu Medical College,Bengbu 233000,China)

Constrained association rules is a major aspect of data mining, According to the constraint conditions can be mining user given targeted. Most of the studies are concentrated in the constrained frequent itemsets mining, very few mining constrained association sequence pattern. Proposes a sequential pattern mining algorithm of association rules based on constraint, It also deals with two constraint: anti monotonicity constraints and monotonicity constraint. According to constraint conditions for mining causal correlation between data. Through experimental verification, The algorithm has good effect on the running time and scalability.

sequence;monotonicity constraint;anti-monotonicity constraints;constrained frequent itemsets;sequential association rules

2014-12-11 基金項(xiàng)目:安徽省高等教育省級(jí)振興計(jì)劃項(xiàng)目(2013zytz037),安徽省教育廳自然科學(xué)研究項(xiàng)目(kj2013z211);安徽省教育廳教學(xué)研究項(xiàng)目(2013jyxm120);蚌埠醫(yī)學(xué)院教學(xué)研究項(xiàng)目(jyxm1307);國(guó)家級(jí)大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計(jì)劃項(xiàng)目(201210367022).

張 鈺(1979-),女,安徽蚌埠人,碩士,蚌埠醫(yī)學(xué)院講師,主要從事數(shù)據(jù)挖掘、虛擬現(xiàn)實(shí)技術(shù)研究.

1672-2027(2015)01-0044-05

TP311

A