灰色Markov模型動態(tài)關聯(lián)規(guī)則趨勢度挖掘方法

張忠林，石皓尹，閆光輝

蘭州交通大學 電子與信息工程學院，蘭州 730070

1 引言

關聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘中重要的研究方法[1]，主要用于發(fā)現(xiàn)事物數(shù)據(jù)集中項與項之間的關系。由于事務數(shù)據(jù)通常具有時間特性[2]，提出了考慮時間因素的序列模式挖掘；為了描述關聯(lián)規(guī)則隨時間變化的特點，提出了動態(tài)關聯(lián)規(guī)則的定義[3]；在以上基礎上進一步改進了動態(tài)關聯(lián)規(guī)則的定義及挖掘算法[4-5]；對動態(tài)關聯(lián)規(guī)則元規(guī)則進行挖掘[6]，可以得到規(guī)則在基于時間序列上的變化情況[7]；為了提高動態(tài)關聯(lián)規(guī)則的挖掘質量，文獻[8]提出了動態(tài)關聯(lián)規(guī)則趨勢度的概念，從而更好地反映規(guī)則隨時間變化的動態(tài)信息。本文在以上研究的基礎上提出了一種將灰色-Markov模型應用在動態(tài)關聯(lián)規(guī)則趨勢度挖掘的方法。該方法在避免生成無用的動態(tài)關聯(lián)規(guī)則的基礎上，挖掘出滿足趨勢度閾值的規(guī)則，提高了挖掘的效率，使挖掘出的動態(tài)關聯(lián)規(guī)則更加全面可靠，并同時解決如何選取趨勢度閾值的問題。

2 動態(tài)關聯(lián)規(guī)則

動態(tài)關聯(lián)規(guī)則能描述自身特性隨時間的變化，而支持度和置信度在時間上構成的向量可以反映關聯(lián)規(guī)則在時間上的變化趨勢。描述如下：

設I={i1，i2，…，in}是項集合，數(shù)據(jù)集D是在時間段t內(nèi)收集到的，t為相等不相交的長度為n的時間序列，即有t={t1，t2，…，tn}。根據(jù)時間段的劃分，將數(shù)據(jù)集D分為n個子數(shù)據(jù)集，其中數(shù)據(jù)子集Di(i∈{1，2，…，n})是在ti(i∈{1，2，…，n})時間段內(nèi)收集的項集T滿足T?I。若A和B為項集，A?I，B?I，并且A∩B=? 。關聯(lián)規(guī)則A?B在D中的支持度Support是事務集D中包含A∪B的百分比，有：Support(A?B)=P(A∪B)，關聯(lián)規(guī)則A?B在D中的置信度Confidence是事務集D中A事務發(fā)生的條件下B事務發(fā)生的百分比，有Confidence(A?B)=P(A|B)。有如下相關定義：

定義1支持度向量（SV）是動態(tài)關聯(lián)規(guī)則A?B（或者項集A∪B）的向量，有如下表示形式：

定義2設項集A∪B的支持度為s，則：

其中，M是D中的事務數(shù)。項集的支持度向量為SV=[f1，f2，…，fn]。

定義3動態(tài)關聯(lián)規(guī)則A?B的置信度向量具有以下的表示形式：

動態(tài)關聯(lián)規(guī)則可以表述為：具有支持度向量SV、置信度向量CV、支持度s、置信度c四個參數(shù)的關聯(lián)規(guī)則；表示形式為：A?B(SV，CV，s，c)。

動態(tài)關聯(lián)規(guī)則引入支持度向量以及置信度向量后，根據(jù)趨勢的變化可以得到動態(tài)關聯(lián)規(guī)則趨勢度的定義。關于動態(tài)關聯(lián)規(guī)則趨勢度的具體定義本文不再闡述和說明，參見文獻[8]中定義1至定義8。

3 灰色-Markov模型

3.1 GM（1，1）預測模型

鄧聚龍教授于1982年首次提出了灰色系統(tǒng)理論?；疑到y(tǒng)理論是建立系統(tǒng)運行趨勢模型的有效理論方法[9-10]?；疑到y(tǒng)理論適用于動態(tài)預測，且只需少量已知信息就可建立預測模型[11]?；疑獹M（1，1）預測模型的具體步驟如下所示。

（2）按照GM（1，1）建模過程可得：

其中：

（4）把估計值a、b代入式（5）中得到時間影響方程：

當t=1，2，…，n-1時，由式（9）得到的是擬合值，而當k≥n時，得到的是預測值。

（5）對序列x^(1)(k+1)做累減還原處理可得原始數(shù)據(jù)預測。公式：

其中n為序列x(0)的長度。發(fā)展系數(shù) -a是GM（1，1）模型適用性范圍的標準，模型適用范圍與發(fā)展系數(shù) -a相關[12-13]，如表1所示。

表1 GM（1，1）模型適用范圍表

3.2 Markov鏈及其轉移概率矩陣

馬爾科夫鏈適用于波動較大的動態(tài)過程[14-15]，在這一點上恰恰可以彌補灰色預測的局限性。

設{Xn，n∈T}為隨機過程，若對于任意的整數(shù)n∈T和任意的狀態(tài)i0，i1，…，in+1∈I，條件概率滿足：P(Xn+1=in+1|X0=i0，X1=i1，…，Xn=in)=P(Xn+1=in+1|Xn=in)，則 稱{Xn，n∈T}為馬爾科夫鏈。馬爾科夫鏈具有無后效性，它表示系統(tǒng)未來(t=n+1)所處的狀態(tài)僅與其現(xiàn)在(t=n)所處的狀態(tài)有關，而與其過去(t≤n-1)所處的狀態(tài)無關。設Ei是系統(tǒng)在時間t所處的狀態(tài)，Xn是與狀態(tài)空間相對應，并形成了Markov鏈。對任意的n∈T和狀態(tài)i，j∈I，稱pij(n)=P(Xn+1=j|Xn=i)為馬爾科夫鏈的轉移概率，表示系統(tǒng)在i狀態(tài)條件下向狀態(tài)j轉換的概率。由pij可得系統(tǒng)狀態(tài)的轉移概率矩陣：

4 算法過程描述

目前最常用到的不確定性系統(tǒng)的研究方法主要有：概率統(tǒng)計、模糊數(shù)學和灰色系統(tǒng)理論，這三種方法的共同點是研究對象都具有某種不確定性。但是正是研究對象在不確定性上的區(qū)別，才產(chǎn)生了這三種各有特色的不確定性科學：模糊數(shù)學著重研究“認知不確定”的問題，主要通過借助于隸屬函數(shù)進行處理；概率統(tǒng)計研究的是“隨即不確定”現(xiàn)象，著重于現(xiàn)象的統(tǒng)計規(guī)律。其出發(fā)點是大樣本，并且要求對象服從某種典型的分布。而本文所采用的灰色系統(tǒng)理論著重研究以上兩種方法難以解決的“小樣本”、“貧信息”的不確定性問題?；疑到y(tǒng)理論最重要的特點也是它最大的優(yōu)點就是“少數(shù)據(jù)建?！?，因此在原始數(shù)據(jù)非常少的情況下，使用灰色系統(tǒng)理論進行建模以及預測結果的準確度會高于其他方法，這正是本文采用灰色系統(tǒng)來建模的原因。

灰色系統(tǒng)理論中的GM（1，1）模型可以在原始數(shù)據(jù)非常少的情況下進行建模，而且還可以得到精度較高的結果。但是通過對GM（1，1）模型研究發(fā)現(xiàn)，GM（1，1）模型只能得到原始數(shù)據(jù)的整體變化趨勢，對于數(shù)據(jù)的波動性變化則沒有顯現(xiàn)，因此利用Markov鏈的相關理論對其進行補充是十分必要的。Markov鏈理論是基于概率統(tǒng)計的理論，適用于具有隨機變化的動態(tài)過程，通過狀態(tài)轉移矩陣可以得到系統(tǒng)在下一個時刻所處狀態(tài)的概率，因此將兩者結合起來可以得到更加準確的預測結果。利用灰色-Markov模型進行挖掘比單純使用灰色G（1，1）模型預測一個值的結果要更加合理，本模型由于在灰色模型的基礎上使用了Markov知識，比灰色GM（1，1）模型的應用范圍要廣，總體效果要優(yōu)于灰色GM（1，1）模型。

本文所提出的基于灰色-Markov模型的動態(tài)關聯(lián)規(guī)則趨勢度挖掘方法的重點是對灰色-Markov模型的運用。在描述算法之前將算法中所用到的名詞進行解釋，F(xiàn)P-Growth算法：文獻[16]提出的一種經(jīng)典的關聯(lián)規(guī)則的挖掘方法；ITS算法：文獻[4]提出的一種動態(tài)關聯(lián)規(guī)則的挖掘算法；DRI：Definition of Rule Index，趨勢度閾值；SRI：Support of Rule Index，趨勢度[8]。下面將本文所提出方法的具體過程以及建模的過程進行詳細描述：

（1）調(diào)用FP-Growth算法挖掘出滿足支持度閾值的頻繁項集。

（2）再次掃描數(shù)據(jù)庫，得到每個頻繁項集的支持度計數(shù)。

（3）根據(jù)支持度向量的變化趨勢以及支持度向量的分類計算各頻繁項集的趨勢度SRI。

（4）判斷各頻繁項集的SRI是否大于趨勢度閾值DRI。

（5）將不滿足DRI要求的頻繁項集的支持度計數(shù)序列用GM（1，1）模型進行建模，從而得到原始數(shù)據(jù)的預測公式。

（6）由預測公式得到原始數(shù)據(jù)的擬合值，進一步得到殘差和殘差百分比。運用Markov鏈分析方法，結合實際情況進行狀態(tài)劃分。

（7）計算每一個狀態(tài)轉移到其他任何狀態(tài)的轉移概率pij，進而得到一步轉移概率矩陣 p和k步轉移概率矩陣 p(k)。

（8）通過一步轉移概率矩陣預測下一狀態(tài)，通過k步轉移概率矩陣預測當前狀態(tài)下一狀態(tài)開始的第k個狀態(tài)，通過預測便可得知此支持度向量下一個或第k個值的取值的概率。

（9）確定預測對象未來的狀態(tài)轉移后，即確定了預測值的變動灰色區(qū)間，取灰區(qū)間的中值作為最終的預測的支持度計數(shù)。

（10）將預測得到的支持度計數(shù)加入原頻繁項集支持度向量，判斷新的支持度序列是否滿足支持度閾值要求。

（11）判斷（10）中滿足支持度閾值的支持度序列的趨勢度是否大于DRI。

（12）將（4）和（11）中滿足要求的規(guī)則作為強趨勢度動態(tài)關聯(lián)規(guī)則進行輸出。

算法流程圖如圖1所示。

圖1 算法流程圖

5 實例分析

實驗數(shù)據(jù)采用SQL Server 2005自帶的某商場2004年的銷售數(shù)據(jù)作為實驗數(shù)據(jù)。挖掘出形如{I1，I2}頻繁項集，其含義為消費者購買I1產(chǎn)品之后購買I2產(chǎn)品在2004年每個月的支持度計數(shù)，其中I1、I2為商品的編號。設最小支持度為0.4，最小支持度數(shù)為40，最小置信度為0.4，趨勢度閾值DRI=0.55。

實例分析過程：

第一步 調(diào)用FP-Growth算法進行挖掘，得到頻繁項集：{I1，I2}，{I2，I4}，{I2，I5}，{I4，I5}。

第二步 掃描數(shù)據(jù)庫，得到各頻繁項集支持度向量SV。SV{I1，I2}=[41，40，42，41，43，44，40，41] ；SV{I2，I4}=[37，39，40，40，41，42，43，45]；SV{I2，I5}=[43，39，39，42，40，43，42，40]；SV{I4，I5}=[43，38，38，42，41，39，42，40]。

第三步 根據(jù)趨勢度的定義[8]，計算各頻繁項集的趨勢度。{I1，I2}支持度向量中每個元素的支持度均大于最小支持度閾值，它屬于支持度穩(wěn)定型向量，SRI(I2，I4)=1；{I2，I4}支持度向量屬于支持度上升型頻繁向量，SRI(I2，I4)=1；{I2，I5}最大上升子時間序列長度為4，最大下降子時間序列向量長度為4，可得：SRI(I2，I5)=0.5 ；{I4，I5}最大上升子時間序列長度和最大下降子時間序列向量長度均為4，可得：SRI(I4，I5)=0.5。

第四步 根據(jù)趨勢度閾值{I1，I2}和{I2，I4}為強動態(tài)關聯(lián)規(guī)則，{I2，I5}和{I4，I5}為非強動態(tài)關聯(lián)規(guī)則。

第五步 對非強動態(tài)關聯(lián)規(guī)則{I2，I5}和{I4，I5}的支持度向量，運用GM（1，1）模型進行建模。

對規(guī)則{I2，I5}和{I4，I5}的支持度序列[43，39，39，42，40，43，42，40]和[43，38，38，42，41，39，42，40]分別作為原始序列：{x(0)=(x(0)(1)，x(0)(2)，…，x(0)(n))，n=1，2，…，8}和 {y(0)=(y(0)(1)，y(0)(2)，…，y(0)(n))，n=1，2，…，8} 。按以下步驟進行：

（1）首先根據(jù)公式（11）獲得級比序列。經(jīng)檢驗級比σ(k)滿足：

（2）不再對原序列進行預處理，直接對原始序列{x(0)=(x(0)(1),x(0)(2),…,x(0)(n))，n=1,2,…,8}建立 GM（1，1）模型。分別得到兩個參數(shù)：a1=-0.008 618，b1=39.127 803；a2=-0.009 673，b2=38.245 032。根據(jù)表1可知，可以運用GM（1，1）模型對其進行中短期預測，分別得到兩序列的時間影響方程：

第六步 利用時間影響方程得到模擬序列，分析規(guī)則{I2，I5}和{I4，I5}支持度的模擬值、殘差和殘差百分比，如表2所示。

表2 模擬值分析表

通過計算表中數(shù)據(jù)可知：序列x(1)的變化趨勢是逐步減小的，根據(jù)這個灰色預測曲線方程得到的模擬值序列x的平均相對誤差為2.54%，而年度最大誤差為4.51%；序列y(1)的變化趨勢是逐步增大的，根據(jù)這個灰色預測曲線方程得到的模擬值序列y(1)的平均相對誤差為2.87%，而年度最大誤差為5.71%，故此灰色模型預測的結果是可以接受的。

根據(jù)規(guī)則的支持度計數(shù)擬合結果和殘差百分比劃分出五種狀態(tài)：E1、E2、E3、E4和E5。殘差百分比小于 -8%設為E1；殘差百分比大于 -8%且小于 -2%設為E2；殘差百分比大于 -2%且小于2%設為E3；殘差百分比大于2%且小于8%設為E4；殘差百分比大于8%設為E5。

第七步 計算狀態(tài)轉移概率，確定狀態(tài)轉移矩陣。由上分析可知，規(guī)則{I2，I5}，{I4，I5}各狀態(tài)轉移情況如表3所示。

表3 狀態(tài)轉移表

進一步得到一步狀態(tài)轉移概率矩陣和兩步狀態(tài)轉移概率矩陣：

第八步 確定接下來兩個月支持度計數(shù)的狀態(tài)。規(guī)則{I2，I5}在第8個月處于狀態(tài)E2，根據(jù)一步狀態(tài)轉移矩陣 P和兩步狀態(tài)轉移矩陣 P(2)，可知規(guī)則{I2，I5}在接下來兩個月支持度計數(shù)分別處于E4和E2；規(guī)則{I4，I5}在第8個月處于狀態(tài)E2，根據(jù)一步狀態(tài)轉移矩陣P′和兩步狀態(tài)轉移矩陣 P′(2)，可知規(guī)則{I4，I5}在接下來兩個月支持度計數(shù)都將處于狀態(tài)E4。

第九步 分別預測兩規(guī)則在接下來兩個月的值。得到規(guī)則{I2，I5}和{I4，I5}接下來兩個月的支持度計數(shù)如表4所示。

第十步 將預測值添加到原規(guī)則支持度序列中。加入預測值后兩規(guī)則的支持度向量分別為：

表4 支持度預測

第十一步 對預測之后的規(guī)則支持度向量再次計算趨勢度。{I2，I5}最大上升子時間支持度序列長度為5，最大下降子時間支持度序列長度為4，根據(jù)公式（4）得：最大上升子時間支持度序列長度為6，最大下降子時間支持度序列長度為4，根據(jù)公式（4）得：SRI(I4，I5)=0.6 。

第十二步 生成規(guī)則階段。分析規(guī)則{I1，I2}和{I2，I4}，它的支持度和置信度都大于閾值，并且趨勢度為1，因此它們都是強動態(tài)關聯(lián)規(guī)則；頻繁項集{I2，I5}的支持度和置信度都滿足閾值要求，但是它的趨勢度0.5＜DRI=0.55，并且對支持度序列進行預測之后仍然小于趨勢度閾值，因此它不是強動態(tài)關聯(lián)規(guī)則；頻繁項集{I4，I5}的支持度和置信度都滿足閾值，且對其支持度序列進行預測之后滿足閾值要求0.6＞DRI=0.55，因此將{I4，I5}作為強動態(tài)關聯(lián)規(guī)則輸出。最終得到三組共6條高趨勢度的動態(tài) 關 聯(lián) 規(guī) 則 ：I1?I2，I2?I1，I2?I4，I4?I2，I4?I5，I5?I4。

結果對比：

為了說明算法的有效性，本文用傳統(tǒng)動態(tài)關聯(lián)規(guī)則挖掘算法ITS算法[4]以及文獻[8]中提出的基于趨勢度的動態(tài)關聯(lián)規(guī)則挖掘算法兩種算法作對比，研究三種挖掘算法產(chǎn)生的規(guī)則。結果如表5所示。

表5 三種方法結果對比表

用傳統(tǒng)的動態(tài)關聯(lián)規(guī)則挖掘算法得到的強動態(tài)關聯(lián)規(guī)則有8條，而用基于趨勢度的動態(tài)關聯(lián)規(guī)則挖掘算法可以得到4條高趨勢度的動態(tài)關聯(lián)規(guī)則，用本文所提出的方法可以得到6條高趨勢度的動態(tài)關聯(lián)規(guī)則。經(jīng)過分析可知，規(guī)則I2?I5和I5?I2其支持度計數(shù)變化隨機性比較大，決策者不能從中得到有效的決策信息；而對于規(guī)則I4?I5和I5?I4，研究其支持度向量序列可知，雖然現(xiàn)有的支持度計數(shù)變化隨機性比較大，但是通過對支持度計數(shù)進行預測發(fā)現(xiàn)其支持度計數(shù)隨機性在逐漸降低，可以從中得到有效的信息，所以將其作為強趨勢度動態(tài)關聯(lián)規(guī)則進行輸出。因此，新的動態(tài)關聯(lián)規(guī)則挖掘算法可以根據(jù)用戶設定的趨勢度閾值，針對動態(tài)關聯(lián)規(guī)則中有一定變化趨勢的規(guī)則進行挖掘，充分考慮到規(guī)則隨時間而變化的特性，在一定程度上提高了規(guī)則挖掘的質量，同時也為決策者提供了更加全面、有效的信息，從而使決策更有依據(jù)、更可靠。

6 結語

本文在GM（1，1）模型和馬爾科夫鏈理論相結合的基礎上，將其組成的組合模型運用到動態(tài)關聯(lián)規(guī)則趨勢度的挖掘中。在動態(tài)關聯(lián)規(guī)則趨勢度的挖掘中運用本方法，不僅能直觀了解到規(guī)則趨勢度的總體的變化情況，還可以對其進行預測。結果表明本文方法能夠在一定程度上提高規(guī)則挖掘的效率，為決策提供更可靠的信息。今后的主要研究方向將放在當原始數(shù)列波動性過大且無明顯規(guī)律時如何保證預測的精度；對象為大數(shù)據(jù)庫或者海量數(shù)據(jù)時，如何提高挖掘算法的效率和準確性[17]。

[1]Agrawal R，Imeielinksi T，Swami A.Mining association rules between sets of items in large databases[C]//Proceedings of the 1993 ACM SIGMOD Conference，1993：207-2l6.

[2]Au W H，Chan K C C.Mining changes in association rules：a fuzzy approach[J].Fuzzy Sets Syst，2005，149（1）：87-104.

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

[4]沈斌，姚敏.一種新的動態(tài)關聯(lián)規(guī)則及其挖掘算法[J].控制與決策，2009，24（9）：1310-1315.

[5]Shen Bin，Yao Min，Wu Zhaohui，et al.Mining dynamic association rules with comments[J].Knowledge and Information Systems，2010，23（1）：73-98.

[6]張忠林，許凡.基于小波變換的動態(tài)關聯(lián)規(guī)則元規(guī)則挖掘方法[J].計算機應用，2012，32（7）：1983-1986.

[7]劉俊，張忠林，謝彥峰，等.基于時間序列模型的動態(tài)關聯(lián)規(guī)則元規(guī)則挖掘[J].計算機工程，2009（15）：94-96.

[8]張忠林，曾慶飛，許凡.動態(tài)關聯(lián)規(guī)則的趨勢度挖掘方法[J].計算機應用，2012，32（1）：196-198.

[9]Zhang Yi，Wei Yong，Zhou Ping.Improved approach of gray derivative in GM（1，1）model[J].The Journal of Grey System，2006，116（10）：160-162.

[10]Sun Yanna.Optimization of grey derivative in GM（1，1）based on the discrete exponential sequence[C]//Proceedings of the 2nd International Symposium on Information Processing（ISTP2009），2009：313-315.

[11]Yang Jiangtian.Multivariable trend analysis using grey model for machinery condition monitoring[C]//Proceedings of the 11th World Congress in Mechanism and Machine Science，2004：2188-2191.

[12]劉思峰，黨耀國，方志耕，等.灰色系統(tǒng)理論及其應用[M].北京：科學出版社，2004：142-146.

[13]劉思峰，鄧聚龍.GM（1，1）模型的適用范圍[J].系統(tǒng)工程理論及實踐，2000，20（5）：121-124.

[14]劉俊，謝彥峰，張忠林.基于灰色Markov模型動態(tài)關聯(lián)規(guī)則元規(guī)則挖掘[J].計算機應用，2008，28（9）：2353-2356.

[15]張忠林，劉俊，謝彥峰.AR-Markov模型在動態(tài)關聯(lián)規(guī)則挖掘中的應用[J].計算機工程與應用，2010，46（14）：135-137.

[16]Han J，Pei J，Yin Y.Mining frequent patterns without candidate generation[C]//Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data，Dallas，2000：1-12.

[17]Kuri-Morales A，Rodriguez-Erazo F.A search space reduction methodology for data mining in large databases[J].Engineering Applications of Artificial Intelligence，2009，22（1）：57-65.