一種雙向關聯(lián)規(guī)則提取算法

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

關鍵詞：雙向關聯(lián)規(guī)則；左置信度；右置信度；強雙向關聯(lián)規(guī)則；強弱雙向關聯(lián)規(guī)則；頻繁項集

中圖分類號：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 引言

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

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

2 基本定義和定理

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

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

性質2.1 雙向關聯(lián)規(guī)則U?圮V等價于V?圮U。

證明：根據(jù)雙向關聯(lián)規(guī)則定義可證。

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

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

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

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

根據(jù)定義，強弱雙向關聯(lián)規(guī)則具有如下性質：

性質2.2 設X?奐Ｉ，Y?奐Ｉ，X?奐Y， X?圮Y-X是強弱雙向關聯(lián)規(guī)則：

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

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

證明：1）由支持度定義，X’的支持度計數(shù)suppor(X)一定大于等于X的支持度計數(shù)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’ 也是強弱雙向關聯(lián)規(guī)則。

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

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

定義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上的雙向關聯(lián)規(guī)則X?圮I-X，若規(guī)則左部長度|X|=m，則，右部長度|I-X|一定等于n-m。

證明：由數(shù)學補集的概念可證。

3 算法思想

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

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

2）采用寬度優(yōu)先的方式各頻繁項集上的雙向關聯(lián)規(guī)則。如頻繁項集長度為n，則先產(chǎn)生規(guī)則左部長度為n-1的規(guī)則，之后長度為n-2的，直到產(chǎn)生規(guī)則左部的長度為[n/2]。

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

左部長度 右部長度

n-1 1

n-2 2

..

..

..

1n-1

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

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

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

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所示的事務數(shù)據(jù)庫，頻繁k（k>=2）項集為{I1，I2}， {I1，I5}， {I2，I5}， {I2，I3}，{I1，I2，I5}。挖掘每個頻繁項集上的雙向關聯(lián)規(guī)則，假設，h_min_conf=75%，l_min_conf=40%。

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

{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%

根據(jù)h_min_conf=75%，l_min_conf=40%，則{I1，I2，I5}上的強雙向關聯(lián)規(guī)則只有一條：

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

并且沒有強弱雙向關聯(lián)規(guī)則。

同樣的方法，可以挖掘其他頻繁項集上強雙向關聯(lián)規(guī)則或強弱雙向關聯(lián)規(guī)則，最終還可以發(fā)現(xiàn){I1，I5}上強雙向關聯(lián)規(guī)則一條，{I2，I3}上強弱雙向關聯(lián)規(guī)則一條，如下：

{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 結束語

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

參考文獻：

[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.