張 鈺,劉玉文

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

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

張 鈺,劉玉文

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

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

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

1 預備知識

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

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

2 基本概念和定義

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

設I是事件的集合,I={i1,i2,…,in},in表示事件稱為項．由k個項組成的序列稱為k-序列．設序列a和序列b,如果存在i1

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

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

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

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

多維屬性是指一個項有多個屬性．比如把一個商品看成是一個項,該商品有若干個屬性,如成本、價格等．

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

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

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

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

3.1 算法的基本思想

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

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

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

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

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

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

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

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

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

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

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

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

定理1 設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?X,由引理1可知C1(X)=False,所以C1(X)∧C2(X)=False．(2)因為Y?X,如果C1(Y)=True,且C1為反單調(diào)性約束,所以可能存在C1(X)=True;又因為C2為單調(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)生候選序列是本文算法的主要的步驟之一,很多文獻對候選序列的產(chǎn)生提出了改進方法．本文采用文獻[6]的方法,首先把頻繁(k-1)-序列按照字典順序排序,對2個頻繁(k-1)-序列X和Y(X

3.2 算法描述

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

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

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

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

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

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

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

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

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

算法1

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

輸出:所有同時滿足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ù)庫為例,反單調(diào)性約束C1:max(S.cost)≤min(S.price),單調(diào)性約束C2:total(S.price)≥100,最小支持度為20%．

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

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

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

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

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

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

掃描序列模式事務數(shù)據(jù)庫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)},掃描事務數(shù)據(jù)庫,求得頻繁序列S3={(BCD),(BCE)},又因為C1(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ù)據(jù)選擇文獻[5]提供的數(shù)據(jù),并選擇文獻[3]中的MCAL算法作為比較對象．在AMDathlon64 8000MHz,2GRAM,WinXP,C#環(huán)境下實現(xiàn)了本文算法和MCAL算法．為了表達方便,本文算法用CSAR表示．二者比較如下:

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

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

圖2 隨著最小支持度的變化兩種算法運行時間對比

圖2顯示當最小支持度大于32%時,CSAR的運算時間多于MCAL,但當最小支持度小于32%時CSAR的挖掘時間要明顯小于MCAL,這是因為隨著支持度的減小,頻繁項集的數(shù)量就會增加,從而會挖掘出大量長項集．因此在長項集挖掘方面CSAR要優(yōu)于MCAL．

5 結(jié)語

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

[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] 郭躍斌,翟延富,董祥軍,等.基于序列模式的正負關聯(lián)規(guī)則研究[J].山東大學學報(理學版),2007,42 (9): 88-90

[3] 李廣原,楊炳儒,周如旗.一種基于約束的關聯(lián)規(guī)則挖掘算法[J].計算機科學,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].軟件學報, 2013,24(8):1804-1815[6] 催貫勛,李 梁,王柯柯,等.關聯(lián)規(guī)則挖掘中Apriori算法的研究與改進[J].計算機應用,2010,30(11):2952-2955

[7] 宋余慶,朱玉全,孫志揮,等.基于FP-tree的最大頻繁項目集挖掘及更新算法[J].軟件學報,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 基金項目:安徽省高等教育省級振興計劃項目(2013zytz037),安徽省教育廳自然科學研究項目(kj2013z211);安徽省教育廳教學研究項目(2013jyxm120);蚌埠醫(yī)學院教學研究項目(jyxm1307);國家級大學生創(chuàng)新創(chuàng)業(yè)訓練計劃項目(201210367022).

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

1672-2027(2015)01-0044-05

TP311

A