基于模糊集的時序關聯(lián)規(guī)則的度量準則

宋中山，楊 敏，周 易

(中南民族大學 計算機科學學院，武漢 430074)

Agrawal和Srikant首次提出了序列模式挖掘問題[1]，L A.Zadeh提出了模糊集的重要概念[2]，把經(jīng)典集合推廣到模糊集.現(xiàn)存的模糊序列模式挖掘算法，大多是針對傳統(tǒng)序列模式挖掘算法作適當修改而得到的.Tzung-Pei Hong等人基于AprioriAll算法，提出了模糊序列模式挖掘算法Fuzzy-Apriori算法[3]，該算法不可避免地具有AprioriAll算法多次掃描數(shù)據(jù)庫，不易發(fā)現(xiàn)長序列模式的缺點.模糊序列模式挖掘的一般化架構，需對數(shù)據(jù)庫中的數(shù)量屬性進行模糊化處理.在現(xiàn)實的購物序列數(shù)據(jù)庫中，項的數(shù)量值、交易之間的時間間隔等都是數(shù)量屬性.近年來，針對模糊序列模式挖掘，人們提出了很多新的方法[4-6]，都取得了較好的效果，擴展了模糊序列模式挖掘的應用范圍.

現(xiàn)有時序關聯(lián)規(guī)則算法，一般在處理高密度海量數(shù)據(jù)時會生成規(guī)模龐大的頻繁項候選集，整個過程要消耗大量的時間，并需要重復多次掃描數(shù)據(jù)庫，執(zhí)行效率低.本文針對時序關聯(lián)規(guī)則在解決商品項分類時所出現(xiàn)的不精確和不確定分層情況，對層次型關聯(lián)規(guī)則模式進行模糊擴展，用以克服不同隸屬度項的語義差異的不足，給出了基于模糊集的時序關聯(lián)規(guī)則的度量準則，通過實驗驗證了該方法的有效性.

1 時序關聯(lián)規(guī)則度量

關聯(lián)規(guī)則挖掘最早由Agrawal等人提出，是為了發(fā)現(xiàn)顧客交易數(shù)據(jù)庫中項集間的關聯(lián)信息.由于關聯(lián)規(guī)則挖掘在數(shù)據(jù)挖掘中的廣泛應用，已經(jīng)產(chǎn)生了大量的關聯(lián)規(guī)則挖掘算法.為了揭示關聯(lián)規(guī)則隨時間變化的特性，在處理時序關聯(lián)規(guī)則中，運用支持度向量SV和置信度向量CV來分析關聯(lián)規(guī)則的時序特性[7].

假設在時間t內生成事務數(shù)據(jù)集D，那么可以將t分成n個不相交的時間序列，記為t={t1,t2,…，tn}，由此可以得到n個數(shù)據(jù)子集，記為D={D1,D2,…，Dn}.其中，任意數(shù)據(jù)子集Di是在時間段ti(i∈1,2,…,n})中生成的.

設項集I={i1,i2,…,im}，若X?I,Y?I，且X∩Y=Φ，那么可以將X?Y這樣的蘊涵式稱為關聯(lián)規(guī)則.它的支持度為s和置信度為c，那么，公式s=PD(X∪Y)給出了D中既含X又含Y的概率；公式c=PD(Y|X)給出了D中既出現(xiàn)X又出現(xiàn)Y事務集的概率.

定義1 時序關聯(lián)規(guī)則X?Y的支持度向量SV定義為：

SV=(s(X∪Y)1,s(X∪Y)2,…，s(X∪Y)n),

s.t.s(X∪Y)i=f(X∪Y)i/|Di|(i∈(1,2,…,n).

(1)

其中，f(X∪Y)i為項集X∪Y在數(shù)據(jù)子集Di(i∈{1,2,…,n})中出現(xiàn)的頻數(shù)；|Di|為Di中的事務數(shù).那么，s(X∪Y)i反映了項集X∪Y在Di中的支持度.X?的支持度s可表示為：

(2)

其中，f(X∪Y)為項集X∪Y在D中出現(xiàn)的頻數(shù)；s(X∪Y)為項集X∪Y在D中的支持度.M是D中的事務數(shù).

定義2 時序關聯(lián)規(guī)則X?Y(或者項集X∪Y)的置信度向量CV定義為：

CV=(c(X∪Y)1,c(X∪Y)2,…，c(X∪Y)n),

(3)

其中，s(X∪Y)i為項集(X∪Y)的SV中的第i個元素；sXi為項集X的SV中的第i個元素.

上述定義中，c(X∪Y)i反映了項集(X∪Y)在Di中的支持度量.X?Y的置信度c可表示為：

c=s(X∪Y)/SX.

(4)

綜上所述，可以得到新的時序關聯(lián)規(guī)則的完整定義.

定義3 時序關聯(lián)規(guī)則的完整定義包括支持度s、置信度c、支持度向量SV和置信度向量CV等4個參數(shù)，完整定義如下：

X?Y(SV,CV,s,c),

(5)

其中，SV、s、CV和c分別由公式(1)、(2)、(3)和(4)給出.

定義4 時序關聯(lián)規(guī)則X?Y的頻數(shù)向量可以定義為：

FV=(f(X∪Y)1,f(X∪Y)2,…，f(X∪Y)n),

(6)

其中，f(X∪Y)i為項集(X∪Y)在數(shù)據(jù)子集Di(i∈{1,2,…，n})中出現(xiàn)的頻數(shù).

那么，時序關聯(lián)規(guī)則挖掘的過程如下：

(1) 計算頻數(shù)向量FV和頻繁項集L；

(2) 由L生成時序規(guī)則，F(xiàn)V生成SV、CV.

2 模糊時序關聯(lián)規(guī)則

模糊集理論最根本的特征是承認事物變化的過渡狀態(tài)，若模糊集A是論域X上滿足某些性質的一類對象，其中每個對象都有一個隸屬于A的程度稱為隸屬度，隸屬函數(shù)μA(x)(x∈X)將每個對象x映射到區(qū)間[0, 1].人們把L. Zadeh的模糊理論用于語義研究[8]，認識到模糊性也存在于人類自然語言中，是它的一種客觀屬性，而它描述的是詞語所指范圍的不確定性.由于人們在認知過程中對有中間狀態(tài)的事物或現(xiàn)象具有認識上的任意性或主觀性，就不可避免地會產(chǎn)生模糊語義.

模糊語義指語義的模糊性，針對層次型關聯(lián)規(guī)則在構造層次分類樹的過程中時所出現(xiàn)的不精確和不確定分層情況，對其進行模糊擴展：即對于X?Y這樣的蘊涵式，若X和Y是模糊集合，則對應的關聯(lián)規(guī)則就為模糊關聯(lián)規(guī)則(Fuzzy Association Rule).

模糊層次分類結構是指具有隸屬度模糊的概念層次樹[9].通過建立帶語義差異的模糊層次分類結構，就能夠計算項間距離、項集間距離，逐步得到最終的關聯(lián)規(guī)則間距離度量的方法.

定義5 設有帶語義差異的模糊層次分類結構T=，x,y∈I,項x和y之間的距離定義為：

(7)

其中，w′(e)是有向邊e的語義差異權值，x是y的祖先，lmin(x,y)是x和y間所有向路徑中語義差異權值最小的.

本文使用平均距離來計算項集間距離，這樣就有：

定義6 設有基數(shù)為m的項集X={x1,x2,…,xm}和基數(shù)為n的項集Y={y1,y2,…,yn}，則X和Y之間的項集距離定義為：

(8)

在對關聯(lián)規(guī)則距離進行度量的過程中，分析對其起決定作用的2個因子：結構差異和規(guī)則度量差異，進而由規(guī)則的結構距離、規(guī)則度量距離來定義規(guī)則距離.

定義7 在帶語義差異的模糊層次分類結構T=中，有關聯(lián)規(guī)則r1:X1?Y1，r2:X2?Y2，X1，X2，Y1，Y2∈I，且λ1,λ2，λ3≥0,則r1和r2間的規(guī)則結構距離可表示為：

Distrule,stru(r1,r2)=λ1×Distset(X1,X2)+λ2×

Distset(Y1,Y2)+λ3×Distset(X1∪Y1,X2∪Y2).

(9)

若Conf(r1),Sup(r1),Conf(r2),Sup(r2)分別為規(guī)則r1,r2的支持度和置信度，λ4,λ5≥0，則r1,r2間的規(guī)則度量距離可表示為：

Distrule,meas(r1,r2)=λ4×|Sup(r1)-Sup(r2)|+λ5×

|Conf(r1)-Conf(r2)|.

(10)

這樣，設有權重w1,w2，則r1和r2間的規(guī)則距離可表示為：

Distrule(r1,r2)=

(11)

綜上所述，λ1,λ2,λ3是結構距離Distrule,stru(r1,r2)中前項、后項和兩者并集的差異的權重；λ4,λ5是度量距離Distrule,measu(r1,r2)中支持度和信任度的差異的權重；w1,w2是規(guī)則距離Distrule(r1,r2)中用戶定義的結構差異和度量差異的值.

3 實驗設計

本文使用George Karypis等人研發(fā)的gCLUTO聚類工具包，進行關聯(lián)規(guī)則的聚類和可視化，本文選擇重復對分(Repeated Bisections)的聚類算法.

通過對T10I4D100K數(shù)據(jù)集進行測試來驗證關聯(lián)規(guī)則距離度量方法的有效性，其中，T10I4D100K來自IBM Almaden Quest 研究組的頻繁項集，處于稀疏型數(shù)據(jù)和密集型數(shù)據(jù)之間.對于數(shù)據(jù)集中的1000個商品項目，共有100000條交易數(shù)據(jù)，給它設定不同的支持度和置信度，用OFP-Growth算法對時序關聯(lián)規(guī)則進行挖掘[10].

由于經(jīng)過時序關聯(lián)規(guī)則挖掘后得到的規(guī)則數(shù)量較大，而且其距離度量計算過程中的消耗較大，不能進行實時處理.本文有必要將整個實驗分為2部分進行.

如表1所示，在給定的支持度和置信度下，本文得到關聯(lián)規(guī)則集RS1和RS2，其中RS1用于時序關聯(lián)規(guī)則距離度量的實驗；RS2用于聚類及規(guī)則間相似性的可視化實驗.

表1 OFP-Growth算法得到關聯(lián)規(guī)則結果

本文將T10I4D100K數(shù)據(jù)集的模糊層次分類結構記為T，根據(jù)其定義，就可以進行如下描述.

(1)T共有1個有向無環(huán)圖，可將其分為4層，最上面的是樹根節(jié)點ROOT，平均扇出為10；

(2) 建立模糊層次分類結構有向邊時，可以隨機生成其模糊隸屬度，使l/3的模糊隸屬度隨機均勻分布在區(qū)間[0.5, l]中，2/3的模糊隸屬度為1；

(3) 相鄰不同層次a,a+1,1≤a≤3的層次語義差異計算函數(shù)設置ld(a,a+1)=(3-a+1)/10；

(4) 不相鄰層次a,a+n,n>1的層次語義差異計算函數(shù)設置為：

(5)權重參數(shù)設置為：

λ1=1,λ2=1,λ3=0,w1=1,w2=0.

本文的實驗平臺為PC，2GB內存，Intel Core i3 CPU，Windows7操作系統(tǒng)，用VC 6.0來編程實現(xiàn)關聯(lián)規(guī)則距離的度量.

在進行關聯(lián)規(guī)則距離度量的過程中，本文使用RS1規(guī)則集，并以每次遞增600條關聯(lián)規(guī)則的方式來測試計算時的速度.當規(guī)則數(shù)量為n時，關聯(lián)規(guī)則間距離的度量需要計算n×(n+1)/2次規(guī)則間的距離.

因為在關聯(lián)規(guī)則距離度量的過程中，構建帶語義差異的模糊層次分類結構T所耗費的時間與整體性能相比很小，可以忽略不計.

將本文由公式(8)給出的項集度量方法與文獻[11]、文獻[12]的方法進行比較.它們隨關聯(lián)規(guī)則數(shù)量的增加所消耗的時間對比如圖1所示.

圖1 關聯(lián)規(guī)則距離度量耗時Fig.1 Execution time of measuring distance among association rules

本文使用gCLUTO聚類工具包來聚類分析關聯(lián)規(guī)則結果，并對結果進行可視化展示[10].本文使用規(guī)則集RS2，設置重復對分(Repeated Bisections)類別為8類.取得了較好的效果，如圖2、圖3所示.

圖2 關聯(lián)規(guī)則聚類的山丘視圖Fig.2 Mountain view of association rules clustered

圖2中可視化山丘將8個類群顯示為8個山丘，并標記了相應的類號.每個山丘的形狀為高斯曲線.這種形狀用來作為每個類內數(shù)據(jù)分布的粗略估計.山丘的高度與類內相似性成比例，體積與類群包含的對象數(shù)量成比例.合成的高斯曲線相加在一起形成可視化山丘的地形.山丘的顏色與類內標準差成比例.紅色代表低標準差，藍色代表高標準差.只有峰頂?shù)念伾怯幸饬x的.在其他所用區(qū)域，顏色混合以產(chǎn)生平滑過渡.

圖3 關聯(lián)規(guī)則聚類的樹形視圖Fig.3 Tree view of association rules clustered

圖3中的可視化矩陣中，顏色代表原始數(shù)據(jù)矩陣中的數(shù)值.gCLUTO用白色代表接近零值，逐漸加深的紅色代表較大的數(shù)值，逐漸加深的綠色代表負值.矩陣的行重新排列，使得同一類的行列在一起.黑色的水平線隔開各個類.左面和上面關聯(lián)規(guī)則聚類后得到的樹形結構，說明了規(guī)則間的組織方式；右下角部分給出了可視化的關聯(lián)規(guī)則的相似性.右下角部分的每一點都說明了橫縱坐標對應的兩個規(guī)則間的相似性，紅顏色越深，表示規(guī)則間的相似性越高.

觀察圖3可以發(fā)現(xiàn)，對角線上紅顏色很深，表示類間的關聯(lián)規(guī)則間的相似性較低，類中的關聯(lián)規(guī)則間的相似性比較高.

4 結語

本文針引入的層次型關聯(lián)規(guī)則的模糊擴展，即基于隸屬度模糊的層次分類結構，克服了原有分類結構僅僅考慮不同層次之間的語義差異，而沒有進一步考慮具有不同隸屬度項的語義差異的不足.使用本文定義的項間距離、項集間距離和關聯(lián)規(guī)則間距離的度量，構建模糊層次分類結構，實驗結果表明，該方法是有效的，并具有良好的性能.將時序關聯(lián)規(guī)則結果進行聚類分析，得到規(guī)則和規(guī)則之間相似性，并進行可視化展示.在實際問題中，模糊集的時序關聯(lián)規(guī)則將其應用到帶語義模糊的商品分類中，為企業(yè)合理有效的管理提供依據(jù)，并可根據(jù)發(fā)現(xiàn)的知識和規(guī)律廣泛地應用到描述客觀現(xiàn)實情況，重現(xiàn)及識別動態(tài)系統(tǒng)，及時調整企業(yè)經(jīng)營策略.

參 考 文 獻

[1] Agrawal R, Srikant R. Mining sequential patterns[C]// ICDE.Proc of the International Conference on Data Engineering (ICDE). Taibei: IEEE, 1995: 3-14.

[2] Zadeh L A. Fuzzy sets[J]. Information and Control, 1965, 8(3): 338-353.

[3] Hong T P, Kuo C S, and Wang S L. A fuzzy AprioriTid mining algorithm with reduced computational time[J]. Applied Soft Computing, 2004, 5(1): 1-10.

[4] Zabihi F, Pedram M M, Ramezan M, et al. Fuzzy sequential pattern mining with sliding window constraint[C]//ICETC. 2010 2nd International Conference on Education Technology and Computer (ICETC). Shanghai: IEEE, 2010, 5: 396-400.

[5] Chang C I, Chueh H E, Luo Y C. An integrated sequential patterns mining with fuzzy time-intervals[C]//ICSAI. 2012 International Conference on Systems and Informatics (ICSAI). Yantai: IEEE, 2012: 2294-2298.

[6] Ouyang W. Discovery of direct and indirect fuzzy sequential patterns with multiple minimum supports in transaction databases[C]//FSKD. 2012 9th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD). Chengdu: IEEE, 2012: 302-306.

[7] 榮 岡,劉進鋒,顧海杰.數(shù)據(jù)庫中動態(tài)關聯(lián)規(guī)則的挖掘[J]. 控制理論與應用, 2007, 24(1): 127-131.

[8] Zadeh L A. Fuzzy sets as a basis for a theory of possibility [J]. Fuzzy Sets and Systems, 1999, 100(1): 9-34.

[9] Chen G, Qiang W. Fuzzy association rules and the extended mining algorithms[J]. Information Sciences, 2002, 147(1-4): 201-228.

[10] 宋中山,周 騰,周晶平.一種改進的蟻群聚類算法在客戶細分中的應用[J].中南民族大學學報:自然科學版,2013,32(3):77-81.

[11] 阮備軍,朱揚勇.基于商品分類信息的關聯(lián)規(guī)則聚類[J]. 計算機研究與發(fā)展, 2004, 41(2): 352-360.

[12] Gupta G, Strehl A, Ghosh J. Distance based clustering of association rules[C]//ANNIE. Proc of Intelligent Engineering Systems Through Artificial Neural Networks (ANNIE 1999). St. Louis: ASME Press, 1999: 759-764.