一種雙向關聯規則提取算法

摘要：針對互為“前件”和“后件”的單向關聯規則中發現的有趣現象，提出雙向關聯規則的概念，對“置信度”進行了重新的定義和分類，并在分析的基礎上，提出一種雙向關聯規則的挖掘算法。

關鍵詞：雙向關聯規則；左置信度；右置信度；強雙向關聯規則；強弱雙向關聯規則；頻繁項集

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044(2009)05-1204-03

A Extraction Algorithm of Two-way Association Rules

YUAN Cai-hong， ZHANG Lian-tang

(Computer and Information Engineering College of Henan University， Kaifeng 475004， China)

Abstract: Against the interesting phenomenon found in the one-way association rules in which one's ‘before the rule' is other's 'after the rule'， it put forward the concept of two-way association rules and \"confidence\" to be carried out a re-definition and classification. And based on analysis， a two-way algorithm for mining association rules is put forword.

Key words: two-way association rules ;left confidence; right confidence; strong two-way association rules; strong-weak two-way association rules; frequent item sets

1 引言

關聯規則最早是由Agrawal等人提出的[1]，最初提出的動機是針對購物籃分析問題提出的，其目的是為了發現交易數據庫中不同商品之間的聯系規則，這些規則可以用來指導商家科學地安排進貨、庫存及貨架設計等。關聯規則是形如X→Y的蘊含表達式，其中X和Y是不相交的項集[2]。

傳統關聯規則挖掘是單向的[3]，在這些單向規則中我們發現一些有趣的規則，比如：“牛奶→面包（sup=75%，conf=91%）”和“面包→牛奶（sup=75%，conf=95%）”，兩個規則都具有較高的支持度和置信度，說明兩者總同時出現；現有的關聯規則提取算法會把低置信度的規則濾掉，原因是認為它對決策者提取的信息意義不大，但是，如在電腦器材銷售數據庫上的兩條規則：“個人電腦→U盤（sup=67%，conf=95%）”和“U盤→個人電腦（sup=67%，conf=10%）”，其中第一個規則具有較高置信度，而后面的規則支持度較低，說明個人電腦的銷售，對于U盤具有促銷作用，而大多購買U盤的人不會購買個人電腦，這樣一對關聯規則對商家來說，也是非常有意義的。本文提出一種雙向關聯規則提取算法，以挖掘那些在某些領域會更有意義的規則。

2 基本定義和定理

在后面介紹過程中，會用到的定義和定理如下：

定義2.1 雙向關聯規則：設D為事務數據庫，I是D上的項目集，稱“U?圮V”為雙向關聯規則，其中，U?奐Ｉ，Ｖ?奐Ｉ，并且U∩V=∮。其中，U、V稱為規則的左部和右部，兩者互稱為規則的“前件”和“后件”。

性質2.1 雙向關聯規則U?圮V等價于V?圮U。

證明：根據雙向關聯規則定義可證。

定義2.2 左置信度、右置信度：設“U?圮V”為雙向關聯規則，左置信度confidence(U)=support(U∪V)/support(U)，右置信度confidence(V)=support(U∪V)/support(V)。

定義2.3 高最小置信度h_min_conf、低最大置信度l_max_conf：為雙向關聯規則定義的兩個參數，認為大于高最小置信度或低于低最大置信度是有意義的，通常h_min_conf>l_max_conf。

定義2.4強雙向關聯規則：設D為事務數據庫，稱“U?圮V”為D上的強雙向關聯規則，當且僅當左置信度confidence(U)≥h_min_conf，并且右置信度confidence(V)≥h_min_conf。

定義2.5 強弱雙向關聯規則：設D為事務數據庫，稱“U?圮V”為D上的強弱雙向關聯規則，當且僅當左置信度confidence(U)≥h_min_conf并且右置信度confidence(V)≤l_max_conf；或者，左置信度confidence(U)≤l_max_conf并且右置信度confidence(U)≥h_min_conf。

根據定義，強弱雙向關聯規則具有如下性質：

性質2.2 設X?奐Ｉ，Y?奐Ｉ，X?奐Y， X?圮Y-X是強弱雙向關聯規則：

1）若左置信度confidence(X)≤l_max_conf，X’?奐X，則X’?圮Y-X’ 也是強弱雙向關聯規則。

2）若右置信度confidence(Y-X’)≤l_max_conf，Y?勱X’?勱X，則X’?圮Y-X’ 也是強弱雙向關聯規則。

證明：1）由支持度定義，X’的支持度計數suppor(X)一定大于等于X的支持度計數support(X)，即

support(X) ≥support(X)，

所以

confidence(X’)=support(Y)/support(X’) ≤support(Y)/support(X)=confidence(X) ≤l_max_conf

confidence(Y-X’)=support(Y)/support(Y-X’) ≥

support(Y)/support(Y-X)=confidence(Y-X) ≥h_min_conf。

所以X’?圮Y-X’ 也是強弱雙向關聯規則。

2）證明方法如（1），在此不再贅述。

該定理說明，如果一個規則是強弱關聯規則，則以弱置信度側的子集為前件或后件的關聯規則仍是強弱關聯規則，利用這一性質，可以有效的避免對一些肯定是強弱關聯規則的測試。

定義2.6 設n項頻繁項集I={I1，I2，…，In}，它的m（1≤m

例如，5項頻繁項集{I1，I2，I3，I4，I5}中的3項頻繁子集序列為：{I1，I2，I3}、{I1，I2，I4}、{I1，I2，I5}、{I1，I3，I4}、{I1，I3，I5}、{I1，I4，I5}、{I2，I3，I4}、{I2，I3，I5}、{I3，I4，I5}。

性質2.3 設頻繁n項集I上的雙向關聯規則X?圮I-X，若規則左部長度|X|=m，則，右部長度|I-X|一定等于n-m。

證明：由數學補集的概念可證。

3 算法思想

基于以上的定義和性質，算法思想描述如下：

1）對頻繁項集的頻繁子集按定義2.6進行排列；

2）采用寬度優先的方式各頻繁項集上的雙向關聯規則。如頻繁項集長度為n，則先產生規則左部長度為n-1的規則，之后長度為n-2的，直到產生規則左部的長度為[n/2]。

根據性質2.3，頻繁n項集I上左部長度為m的雙向關聯規則X?圮I-X，規則右部的長度為n-m，再根據性質2.1，X?圮I-X等價于I-X?圮X，該規則左部的長度為n-m，右部的長度為m。按照寬度優先的方式產生頻繁項集上的雙向關聯規則，若讓左部的長度從n-1到1，則規則左部和右部的變化過程為：

左部長度 右部長度

n-1 1

n-2 2

..

..

..

1n-1

則左部長度為n-1的雙向關聯規則形成的集合等價于右部長度為n-1（左部長度為1）的規則集合，左部長度為n-2的雙向關聯規則形成的集合等價于右部長度為n-2（左部長度為2）的規則集合，……，因此，只需產生左部長度不超過[n/2]的雙向關聯規則。

另外，若n為偶數，n-[n/2]= [n/2]，則左部長度為[n/2]，右部長度相同。此時，只需按照深度優先的方式產生一半長度為[n/2]的子集即可。

3）產生雙向關聯規則為X?圮I-X，并且左置信度confidence(X)≤l_max_conf，右置信度confidence(I-X)≥h_min_conf，則不再產生所有以X為子集的雙向關聯規則。

4 算法描述

Rule-generate(L，h_min_conf，l_max_conf)

for each frequent itemset lk in L

genrules(lk，k，{});

genrules(lk:frequent k-itemset， m:int，del_itemset:m-2_itemset subsets of m-1_itemset)

if ((k mod 2==0) and (m-1==k/2))

X={(m-1)-itemsets xm-1|half of xm-1 in lk}-del_itmset;

X={(m-1)-itemsets xm-1|xm-1 in lk}-del_itmset;

for each xm-1 in X

{

l_ conf=support(lk)/support(xm-1);

r_conf=support(lk)/support(lk-xm-1);

if (l_conf≥h_min_conf)and (r_conf≥h_min_conf) or

(l_conf≥h_min_conf)and (r_conf≤l_max_conf)or

(l_conf≤h_min_conf)and (r_conf≥l-max_conf)

cout<<“xm-1?圮(lk-xm-1)，support=support(lk)，”<<” l_confidence=”<

i f( (l_conf≤h_min_conf)and (r_conf≥l-max_conf)) del_itemset∪=m-2_subset(xm-1);

}

if (m-1>k/2) then genrules(lk， m-1， del_itemset);

}

5 應用示例

對表1所示的事務數據庫，頻繁k（k>=2）項集為{I1，I2}， {I1，I5}， {I2，I5}， {I2，I3}，{I1，I2，I5}。挖掘每個頻繁項集上的雙向關聯規則，假設，h_min_conf=75%，l_min_conf=40%。

首先，從最大的頻繁項集開始，挖掘{I1，I2，I5}上的雙向關聯規則過程為：

{I1，I2}?圮{I5}l_conf=3/3=100% r_conf=3/4=75%

{I1，I5}?圮{I2}l_conf=3/4=75% r_conf=3/5=60%

{I2，I5}?圮{I1}l_conf=3/3=100% r_conf=3/5=60%

根據h_min_conf=75%，l_min_conf=40%，則{I1，I2，I5}上的強雙向關聯規則只有一條：

{I1，I2}?圮{I5}l_conf=3/3=100% r_conf=3/4=75%

并且沒有強弱雙向關聯規則。

同樣的方法，可以挖掘其他頻繁項集上強雙向關聯規則或強弱雙向關聯規則，最終還可以發現{I1，I5}上強雙向關聯規則一條，{I2，I3}上強弱雙向關聯規則一條，如下：

{I1}?圮{I5}l_conf=4/5=80% r_conf=4/4=100%

{I2}?圮{I3}l_conf=2/5=40% r_conf=2/2=100%

6 結束語

本文提出的算法用于在頻繁項集上挖掘強雙向關聯規則或者強弱雙向關聯規則，對頻繁項集設定了一種排列方式，使得挖掘過程更容易實現對集合的操作；提出一種刪除冗余規則的方法，在一定程度上能夠減少冗余規則的產生。但是，若強弱雙向關聯規則中弱項在右部，則不能利用本文提出的方法進行冗余規則的刪除。

參考文獻：

[1] Jiawei Han， Micheline Kamber，Data Mining:Concepts and Techniques[J].Morgan Kaufman Puclishers，2001.154-155.

[2] Pang-Ning Tan Michael Steinbach Vipin Kumar，Introduction to Data Mining[M].Pearson Education Inc，2006：231-233.

[3] Rakesh Agrawal， Tomasz Imielinski， Arun Swami. Mining Association Rules between Sets of Items in Large Databases，1993.