一種基于時態因子約束的關聯規則挖掘算法

邵保勝，孟志青，蔣 敏

（浙江工業大學 經貿管理學院，浙江 杭州 310023）

一種基于時態因子約束的關聯規則挖掘算法

邵保勝，孟志青，蔣 敏

（浙江工業大學 經貿管理學院，浙江 杭州 310023）

時間是事物本身固有的性質，挖掘關聯規則的時候把時間因素考慮進去會更符合現實的情況，時態關聯規則挖掘是一種考慮帶時間約束的關聯規則挖掘方法.研究如何對關聯規則進行時間上的約束是一個有待解決的問題，運用時態因子對關聯規則進行時間上的約束是解決問題的一個辦法，在給出時態因子的相關定義后，提出基于時態因子的關聯規則相關概念，并給出了一種基于時態因子約束的關聯規則的算法.最后結合實驗結果，給出了一種關聯規則實驗結果分析方法，這種分析方法使得所挖掘的實際結果更為直觀.

時態關聯規則；時態因子；SQL語言

關聯規則是數據挖掘的一個重要研究領域，由Agrawal等［1］提出.人們很快發現隨著時間的變化，關聯規則過一段時間也許不適用了.此后，Cheung等［2］提出了增量式關聯規則挖掘，使得關聯規則隨著數據的更新規則不斷的變化.在現實世界中，由于時間是事務本身固有的因素，例如超市交易記錄中的交易時間等.時態數據的出現使我們有必要在數據挖掘中考慮時間因素，挖掘某種時態約束的規則將可以更好地描述客觀現實情況，稱這樣的規則為時態關聯規則.由于時態關聯規則更能體現規則的有效性，近年來，大量的研究者們對時態關聯規則的理論與實證進行了研究，也產生了大量的時態關聯規則論文.孟志青教授［3］提出了時態關聯規則的有關概念和相關性質，給出了時態挖掘模型，但是沒有提出相關的算法進行挖掘.基于日歷模式的時序關聯規則［4］可以發現任意日歷模式的關聯規則，但是分析和理解起來比較困難，算法也比較復雜，有些細小的日歷模式一般情況下并沒有太大意義.有研究者提出一種容易理解的時態關聯規則［5］，算法也比較簡潔.但是，它只對某些特定的時段進行挖掘，有些時候必須要知道商品的生命周期，這樣實踐起來會比較麻煩，也沒有很好的從整個歷史時間上考察時態關聯規則隨時間的變化性質.動態關聯規則挖掘［6］可以考察關聯規則隨時間變化而變化的性質，但是只是把靜態的關聯規則進行切分，使它變成了“動態”.在時態型定義與時態關聯規則模型的基礎上，提出了基于時態因子約束的關聯規則挖掘算法.這種挖掘算法簡便可行，可以在有效時間區間上考察關聯規則的隨時間的變化情況，還可以在每個時態因子上觀察該時態因子中的關聯規則.

1 時態關聯規則模型建立

C.Betti［7］首次提出了時態型的概念，王俊華等［8］系統地論述了時態型和時間粒度的相關概念和理論.在給出時態型的相關概念后，提出基于時態因子的時態關聯規則挖掘，并提出了相關的定義和挖掘算法.

定義1 設μ是從絕對時刻t到絕對時間的映射，也即R→2R，如果μ滿足下列性質，則我們稱μ為時態型，μ（t）為μ的時態因子［8］.

1）（非空性）t∈μ（t）.

2）（單調性）若t1＜t2且μ（t1）∩μ（t2）＝?，?t′∈μ（t1）和?t″∈μ（t2），t′＜t″.記作μ（t1）＜μ（t2）.

3）（同一性）?t′∈μ（t），μ（t′）＝μ（t）.

4）（有界性）?t′∈μ（t），｜t′｜＜＋∞.

顯然，時態型μ是對時間軸T的一個劃分，每個時態因子μ（t）是一個絕對時刻的集合.秒、分、小時、日、周、月和年等可以用來劃分時間數軸R，并且它們都滿足上述性質，因此都是時態型，見圖1.

圖1 有關時態型的映射Fig.1 The mapping of temporal

性質1 若t1≠t2，則μ（t1）∩μ（t2）＝?或者μ（t1）＝μ（t2）［8］.

性質3 ?t∈R，μ（t）存在上確界supμ（t）和下確界infμ（t）.也即?ti∈μ（t），ti≤supμ（t），ti≥infμ（t）［8］.

定義2 一個基于時態因子的關聯規則可以看作是一個二元式＜AR，v（t）＞，式中AR為一條形如X?Y的關聯規則，v（t）為一個時態因子，例如年、月、星期、日等.二元式＜AR，v（t）＞表示了在時態因子v（t）中關聯規則AR都成立.

根據以上定義和性質，我們給出以下定義：

定義3 設I＝｛i1，i2，…，im｝是項的集合，任務相關的數據D為數據庫事務的集合，事務數記作｜D｜，每個事務T為項的集合，使得T?I并且都有一個時間戳t；所有t∈v（t）的事務集合記作d，d中的事務個數記作｜d｜.

1）設X?I，項集X的時態支持度是事務集d中包含X 的事務數與d中事務數之比，記為sup（X，v（t））），即

2）設X?I，Y?I并且＝X∩Y＝?，規則X?Y在事務數據庫D中的時態支持度是事務集d中包含X和Y的事務數與d中事務數之比，記為sup（X?Y，v（t）），即

sup（X?Y，v（t））＝｜｛T：X∪Y?T，T∈d｝｜／｜d｜

3）規則X?Y在事務集中的時態置信度是指事務集d中包含X和Y的事務數與包含X的事務數之比，記為conf（X?Y，v（t）），即

2 基于時態因子的關聯規則挖掘算法

挖掘基于時態因子的關聯規則首先要把整個數據庫中的事務按照時態因子劃分成一個個基本數據庫.在每個時態因子數據庫中產生時態支持度和時態置信度分別大于用戶給定的最小支持度（minsup）和最小置信度（minconf）的關聯規則.挖掘過程可以分兩步：

1）對每個時態因子，求頻繁項集X使sup（X，v（t））≥minsup，用頻繁項集X發現規則對于每一個A∪B＝X，A∩B＝?驗證conf（A?B，v（t））≥minconf.

2）綜合所有時態因子中的大項集和關聯規則.

算法也是根據上面的過程來進行，為了求得候選項集c的時態因子支持度sup（c，v（t）），就必須先求出時態因子內包含項集c的事務數和時態因子數據庫中的事務總數.關聯規則根據每個時態因子數據庫中的頻繁項集算得，最后合并每個時態因子中的頻繁項集和關聯規則，下面的算法說明了相應的過程.

算法中規定d為每個時態因子v（t）中的數據庫，｜d｜為相應的事務數，Li為每個時態因子v（t）中的頻繁項集，Ai為每個時態因子v（t）中的關聯規則，具體算法如下：

輸入：D為根據時態因子劃分好的數據庫，minsup：最小支持度，minconf：最小置信度.

輸出：以時態因子為單位的數據庫中的所有頻繁項集和所有關聯規則.

Apriori-gen（）函數就是通常的候選項集產生函數，Association-rule-gen（）函數是根據頻繁項集產生關聯規則，最后面是得到所有時態因子上的頻繁項集和關聯規則.

該算法是在傳統Apriori算法上的改進，較容易理解，采用時態因子劃分數據庫簡單易行，得到的結果也容易理解.

3 實驗結果及分析

數值試驗取月作為時態因子約束，因為許多超市銷售，一般都會以一個月作為觀察對象.下面是按月作為約束挖掘.運用前面的算法來進行分析，算法采用PHP語言進行實現的，實驗平臺：CPU是Pentium（R）Dual-Core E5300 2.60 GHz，內存2 G，操作系統是Windows XP.

采用的是SQL SERVER2005自帶的AdventureWorks數據庫，對其中的銷售數據進行關聯規則挖掘.經過預處理，訂單號相同的放在一個購物籃里，取其中的2003年8月1號到2004年7月31號一整年的數據進行分析，總共有23 434條記錄.最小支持度為0.04，最小置信度為50%.

在這里，提出了一種基于數據庫表格的分析方法，把算法運行的結果導入到數據庫表格中，頻繁項集和關聯規則的表格設計如表1，2所示，并分別把兩個表格命名為Largesets和Rules.在表2中，我們把小數點設置為4位是因為置信度一般是以百分比形式，我們會在此后的分析中運用百分比，并且精確到后面兩位.

表1 頻繁項集的數據表 （Largesets）Table 1 The table design of the frequent itemsets（Largesets）

表2 關聯規則的數據表 （Rules）Table 2 The table design of association rules（Rules）

在得到表1，2之后，我們就可以用SQL語言來進行查詢分析.如果我們要得到某個時態因子上的頻繁項集，只需要給出時態因子約束就可以進行查詢了，SQL查詢語句：SELECT largesets，support FromLargesets WHERE v（t）＝TIME，TIME 代表某個時態因子.如果要觀察某個頻繁項集在哪些時態因子上有效，SQL查詢語句為：SELECE largesets，v（t），support FROmLargesets WHERE largesets＝X ORDER BY v（t），X 表示某個頻繁項集.對關聯規則的查詢分析和頻繁項集的查詢類似，在此省略.

我們根據算法的運行結果，可以得到每月的關聯規則，在算法中運用INSERT INTO語句把結果放入SQL數據庫表格中，這樣不管關聯規則的數量如何，都能實現自動化，部分結果如表3所示.

表3 關聯規則的數據庫表格Table 3 The table of association rules

得到這個表格后，我們就可以用SQL語句進行查詢分析了.例如，我們我要得到8月份的關聯規則，我們可以使用下面的SELECT語句：SELECT associationRules，confidence FROM Rules WHERE v（t）＝’2003－8’，我們可以得到如表4所示的8月份的關聯規則.

表4 2003年8月份的關聯規則Table 4 The association rules in August.2003

我們還可以對上面的查詢結果進行圖表分析，從而更能直觀的對關聯規則進行分析.如果要對某個時間段的關聯規則進行EXCEL圖表分析，把SQL查詢結果導入到EXCEL表格中，對圖3中的表作EXCEL圖表分析，得到圖2.

圖2 2003年8月份的關聯規則置信度柱狀圖Fig.2 The confidence histogram of association rules in August.2003

我們想要得到關聯規則871→870在各個時態因子上的置信度情況，我們可以使用如下的SELECT語句：SELECT associationRules，v（t），confi-dence FROM Rules WHERE associationRules＝'871→870'，可以得到見表5的數據庫表格.

表5 關聯規則在各個月份的置信度Table 5 The confidence of association rules in each month

如果要運用圖表觀察某個關聯規則在各個時間段的置信度情況，同樣地利用上面SQL的查詢結果來進行EXCEL圖表分析，首先我們需要對查詢結果作一點修正，如果這個關聯規則在某個時間段查詢不到，說明它在這個時間段不是一個規則，我們就把這個時間段的置信度設置為零.從圖5中我們可以發現，關聯規則871→870在每個月上都是有效的，我們對它進行EXCEL圖表分析，如圖3所示.

圖3 關聯規則在各個月的置信度折線圖Fig.3 The confidence curve of association rules in each month

對于圖3，可以利用時間序列方法對這個關聯規則做預測.在這里，我們采用線性回歸方法來對關聯規則871→870進行下一個月的預測，得到回歸方程為

式中：x為月份的序列號；y為該關聯規則的置信度.根據方程式，我們預測2004年8月關聯規則871→870的置信度為82%.

4 結 論

擴展了時態關聯規則的挖掘方法，把整個數據庫按時態因子進行劃分，分析每個時態因子上的關聯規則，考慮了關聯規則的時間約束性質.并提出了一種算法來挖掘時態因子關聯規則，并應用實例進行了數值試驗.還提出了一種的關聯規則結果分析方法，能靈活的運用圖表進行分析，并在一些情況下可以利用某些方法對關聯規則進行預測.

［1］RAKESH A，TOMASZ I，ARUN S.Mining association rules between sets of items in large database［C］.Washington：ACM SIGMOD，1993：207-216.

［2］DAVID W L C，HAN Jia-wei，VINCENT N C，et al.Maintenance of discovered association rules in large databases：an incremental updating technique［C］.New Orleans：Proceeding of ICDE，1996：106-114.

［3］孟志青.時態關聯規則挖掘的若干性質［J］.計算機工程與應用，2001，37（10）：86-87.

［4］崔曉軍，薛永生.基于日歷的時序關聯規則挖掘算法［J］.計算機應用，2006，26（8）：1898-1903.

［5］董祥軍，宋瀚濤，姜合，等，時態關聯規則的研究［J］.計算機工程，2005，31（15）：24-26.

［6］榮岡，劉進鋒，顧海杰.數據庫中動態關聯規則的挖掘［J］.控制理論與應用，2007，24（1）：128-131.

［7］CLAUDIO B.Testing complex temporal relationships involving multiple granularities and its application to data mining［J］.ACM，1996，12（4）：86-88.

［8］王俊華.增量式時態關聯規則［D］.杭州：浙江工業大學經貿管理學院，2008.

A mining algorithm of association rules based on temporal factor

SHAO Bao-sheng，MENG Zhi-qing，JIANG Min
（College of Business Administration，Zhejiang University of Technology，Hongzhou 310023，China）

Time is inherent in the nature of the things itself.Considering time factor will be more realistic when the association rules are mined.Temporal association rule is a kind of mining method with time constraints.How to constrain time on associtaion rules is an issue to be resolved.Using temporal factors，on association rules is a solution.After defining temporal factors，we propose the concepts of temporal factor and temporal association rules.The algorithm of association rules based on temporal factor is also explained.Finally，experiment results are provided and a method to analyzing the experiment results of association rules is given.The method makes the mined results more intuitive.

temporal association rules；temporal factor；SQL Language

TP311.132

A

1006-4303（2012）01-0060-05

2010-10-22

邵保勝（1986—），男，浙江衢州人，碩士研究生，主要從事數據挖掘研究，E-mail：nbrsuperson＠126.com.

（

劉 巖）