第3章关联规则挖掘

3.基本概念
关联规则挖掘发现大量数据中项集之间有趣的关联联系。如果两项或多项属性之间

存在关联,那么其中一项的属性就可以依据其他属性值进行预测。关联规则挖掘是数据

挖掘中的一个重要的课题,最近已被业界深入研究和广泛应用。

关联规则研究有助于发现交易数据库中不同商品(项)之间的联系,找出顾客购买行
为模式,如购买了某商品对购买其他商品的影响。分析结果可以应用于商品货架布局、存
货安排以及根据购买模式对用户进行分类。

关联规则挖掘问题可以分为两个子问题:第一个是找出事务数据库中所有大于或等

于用户指定的最小支持度的数据项集;第二个是利用频繁项集生成所需要的关联规则,根

据用户设定的最小置信度进行取舍,最后得到强关联规则。识别或发现所有频繁项集是

关联规则发现算法的核心,关联规则的基本描述如下。

1. 
项与项集
数据库中不可分割的最小单位信息称为项(或项目), 用符号
i 
表示,项的集合称为项
集。设集合I={i1,i2,…,
k 
}是项集,-项集。例
如,集合{啤酒,尿布,奶粉} 
i
是一个3-项集
I 
。
中项目的个数为k,则集合
I 
称为k

2. 
事务
设I= 
{1,2,…,k}是由数据库中所有项目构成的集合, {1,2,…, 

iii事务数据库T= 
ttt}是由一系列具有唯一标识的事务组成的。每个事务ti(2,…,

i=1,n)包含的项集都是(n) I 
的子集。例如,顾客在商场里同一次购买多种商品,这些购物信息在数据库中有一个
唯一的标识,用以表示这些商品是同一顾客同一次购买的,称该用户的本次购物活动对应
一个数据库事务。

3. 
项集的频数(支持度计数) 
包括项集的事务数称为项集的频数(支持度计数)。

4. 
关联规则
关联规则是形如X.
Y 
的蕴含式,其中X,并且
X 
∩Y=

Y 
分别是
I 
的真子集, .。
X 
称为规则的前提,
Y 
称为规则的结果。关联规则反映
X 
中的项目出现时,
Y 
中的项目
也跟着出现的规律。


5. 
关联规则的支持度
关联规则的支持度(support)是交易集中同时包含
X 
和
Y 
的交易数与所有交易数之
比,它反映了
X 
和
Y 
中所含的项在事务集中同时出现的频率,记为support(
X 
.Y), 即
support(
X 
.Y)=support(
X 
∪Y)=P(XY) (3-1) 

6. 
关联规则的置信度
关联规则的置信度(confidence)是交易集中包含
X 
和
Y 
的交易数与包含
X 
的交易数
之比,它反映了包含
X 
的事务中出现
Y 
的条件概率,记为confidence(X.Y), 即

cofdne(= support(X) P(

X) (3-2)

niecX.Y)support(X∪Y)=
Y 

7. 
最小支持度与最小置信度
通常用户为了达到一定的要求,需要指定规则必须满足的支持度和置信度阈值,这两
个值称为最小支持度阈值(min_sup)和最小置信度阈值(min_conf)。其中,min_sup描述
了关联规则的最低重要程度,min_conf规定了关联规则必须满足的最低可靠性。

8. 
强关联规则
support(
X 
.Y)≥minsup且confidence(
X 
.Y)≥minconf,称关联规则
X 
.
Y 
为
强关联规则,否则称X.Y为(_) 弱关联规则。通常所说的关联规(_) 则一般是指强关联规则。

9. 
频繁项集
设
U 
.I,项集
U 
在数据集
T 
上的支持度是包含
U 
的事务在
T 
中所占的百分比,即
support(U)=‖{t∈
T 

‖TU‖
.t}‖ (3-3) 
式中,‖·‖表示集合中的元素数目。对项集I,在事务数据库
T 
中所有满足用户指定的
最小支持度的项集,即不小于min_sup的
I 
的非空子集,称为频繁项集或大项集。

10. 
项集空间理论
R.Agrawal等人建立了用于事务数据库挖掘的项集空间理论。理论的核心:频繁项
集的子集仍是频繁项集,非频繁项集的超集是非频繁项集。

3.关联规则挖掘算法———Apiri算法原理
2 
ro

最著名的关联规则发现方法是R.Agrawal提出的Apriori算法。

1.Apriori算法的基本思想
Apriori算法的基本思想是通过对数据库的多次扫描来计算项集的支持度,发现所有

36 

37 
的频繁项集从而生成关联规则。Apriori算法对数据集进行多次扫描。第次扫描得到频
繁1-项集的集合L1,第k(k>1)次扫描首先利用第(k-1)次扫描的结果Lk-1 来产生候
选k-项集的集合Ck ,然后在扫描的过程中确定Ck 中元素的支持度,最后在每次扫描结束
时计算频繁k-项集的集合Lk ,算法在当候选k-项集的集合Ck 为空时结束。
2.Apriori算法产生频繁项集的过程
Apriori算法产生频繁项集的过程主要分为连接和剪枝两步。
(1)连接。为找到Lk(k ≥2),通过Lk-1与自身进行连接产生候选k-项集的集合
Ck 。设l1 和l2 是Lk-1中的项集。记li j[ ] 表示li 的第j 个项。Apriori算法假定事务或项
集中的项按字典次序排序;对于(k-1)项集li,对应的项排序为li[1]<li 2[ ] <…< 
li[k-1]。如果Lk-1 的元素l1 和l2 的前(k-2)个对应项相等,则l1 和l2 可连接。即如
果(l1[1]=l2[1])∩(l1[2]=l2[2])∩…∩(l1[k-2]=l2[k-2])∩(l1[k-1]<l2[k- 
1])且不为空时,l1 和l2 可连接。条件l1[k-1]<l2[k-1]可以保证不产生重复,而按
照L1,L2,…,Lk-1,Lk ,…,Ln 次序寻找频繁项集可以避免对事务数据库中不可能发生的
项集所进行的搜索和统计工作。连接l1 和l2 产生的结果项集为(l1[1],l1[2],…,l1[k-1], 
l2[k-1])。
(2)剪枝。由Apriori算法的性质可知,频繁k-项集的任何子集必须是频繁项集。由
连接生成的集合Ck 需要进行验证,去除不满足支持度的非频繁k-项集。
3.Apriori算法的主要步骤
Apriori算法的主要步骤如下。
(1)扫描全部数据,产生候选1-项集的集合C1。
(2)根据最小支持度,由候选1-项集的集合C1产生频繁1-项集的集合L1。
(3)对k>1,重复执行步骤(4)~(6)。
(4)由Lk 执行连接和剪枝操作,产生候选(k+1)-项集的集合Ck+1。
(5)根据最小支持度,由候选(k+1)-项集的集合Ck+1产生频繁(k+1)-项集的集
合Lk+1。
(6)若L≠.,则k=k+1,跳往步骤(4);否则,跳往步骤(7)。
(7)根据最小置信度,由频繁项集产生强关联规则,结束。
4.Apriori算法描述
输入:数据库D ,最小支持度阈值min_sup。
输出:D 中的频繁集L。
(1)Begin 
(2)L1=1-频繁项集; 
(3)for(k=2;Lk-1≠.;k++)dobegin 
(4)Ck =Apriori_gen(Lk-1);{调用函数Apriori_gen(Lk-1)通过频繁(k-1)-项集

产生候选k-项集}
(5)for所有数据集t∈
D 
dobegin {扫描
D 
用于计数}
6)Ct=subseCk 
,ubse

(t(t);{ 用st找出该事务中候选的所有子集
}
(7)for所有候选项集c∈Ct 
do
(8)c.count++
;
(9)end;
(c∈Ck|
_


10)Lk 
={c.count≥minsup}
(11)end;
(12)end;
(13)ReturnL1∪L2∪Lk 
∪…∪Lm 
{形成频繁项集的集合
}


3.3 
Apriori算法实例分析
i算法

rioArp

实例分析

笔交易都用唯一的标识符TID 作标记, 
寻找
D 
中频繁项集的过程。

【1】
例3.表3-1是一个数据库的事务列表,在数据库中有9笔交易,即|D|=9。每
交易中的项按字典序存放,下面描述Aprior

i算法

表3-
1 
数据库的事务列表

事务商品ID 
列表事务商品ID 
列表
T100 I1,I2,I5 T600 I2,I3 
T200 I2,I4 T700 I1,I3 
T300 I2,I3 T800 I1,I2,I3,I5 
T400 I1,I2,I4 T900 I1,I2,I3 
T500 I1,I3 

设最小支持度计数为2,即min_sup=2,利用Apriori算法产生候选项集及频繁项集
的过程如下。

1)第一次扫描

扫描数据库
D 
获得每个候选项的计数: 


由于最小事务支持数为2,没有删除任何项目。可以确定频繁1-项集的集合L1,它

38 


由具有最小支持度的候选1-项集组成。

2)第二次扫描

为发现频繁2-项集的集合L2,算法使用L1∞L1产生候选2-项集的集合C2。在剪枝
步骤没有候选从C2中删除,因为这些候选的每个子集也是频繁的。


3)第三次扫描
L2∞L2产生候选3-项集的集合C3。


候选3-项集的集合C3产生的详细地列表如下。

(1)连接: 
C3=L2∞L2 
={{I2},{I3},{I5},{I3},{I4},{I5}}∞

I1,I1,I1,I2,I2,I2,

{{I2},{I3},{I5},{I3},{I4},{I5}} 

I1,I1,I1,I2,I2,I2,
={{I1,I2,I1,I5},{I3,I2,I4},{I3,

I3},{I2,I1,I5},{I3,I2,I5}, 
{I4,

I2,I5}}。
riorI1,

(2)使用Api性质剪枝:频繁项集的所有非空子集也必须是频繁的。例如,{
I3,I1,I5} I5 I3,I5}

I5}的2-项子集是{I3},{和{}。{不是L2 的元素,所以不是频
I1,I1,I5 

I1,I3,

繁的。因此,从C3中删除{}。剪枝C3={{I3},{}}。
4)第四次扫描
I1,I3,I5 I2,I2,
算法使用L3∞L3产生候选4-项集的集合C4。L3∞L3={{I1,I2,I3,I5}}, 根据

Apriori性质,因为它的子集{I3,不是频繁的,所以这个项集被删除。这样C4=.,

I2,I5}
因此算法终止,找出了所有的频繁项集。
【例3.表3-riori算法发现
D 
中的频繁

项集。
2】2为某超市销售事务数据库D,使用Ap

39 

40 
表3-2 某超市销售事务数据库
TID 商品ID 列表TID 商品ID 列表
T100 I1,I2,I5 T600 I2,I3 
T200 I2,I4 T700 I1,I3 
T300 I2,I3 T800 I1,I2,I3,I5 
T400 I1,I2,I4 T900 I1,I2,I3 
T500 I1,I3 
事务数据库D 中有9个事务,即‖D ‖=9。超市中有5件商品可供顾客选择,即
I={I1,I2,I3,I4,I5} ,且‖I‖=5。设最小支持数minsup_count=2,则对应的最小支
持度为2/9=22%。
寻找所有频繁项集的过程如下。

41 
3.4 Apriori算法源程序分析 
#include <iostream> 
#include <string> 
#include <vector> 
#include <map> 
#include <algorithm> 
using namespace std; 
class Apriori 
{p
ublic: 
Apriori(size_t is =0,unsigned int mv=0) 
{ 
item_size =is; 
min_value =mv; 
} 
//~Apriori() {}; 
void getItem(); 
map<vector<string>,unsigned int>find_freitem(); //求事务的频繁项 
//连接两个k-1 级频繁项, 得到第k 级频繁项 
map <vector<string>,unsigned int >apri_gen(unsigned int K, map<vector 
<string>,unsigned int>K_item); 
//展示频繁项集 
void showAprioriItem(unsigned int K,map< vector< string>,unsigned int > 
showmap); 
private: 
map<int, vector<string>>item; //存储所有最开始的事务及其项 
map<vector<string>,unsigned int>K_item; //存储频繁项集 
size_t item_size; //事务数目 
unsigned int min_value; //最小阈值
}; 
void Apriori::getItem() //用户输入最初的事务集
{ 
int ci=item_size; 
for (int i=0;i<ci;i++) 
{ 
string str; 
vector<string>temp; 
cout<<"请输入第"<<i+1<<"个事务的项集(123 end):"; 
while (cin>>str && str !="123")

42 
{ 
temp.push_back(str); 
} 
sort(temp.begin(),temp.end()); 
pair<map<int, vector<string>>::iterator, bool>ret =item.insert(make 
_pair(i+1, temp)); 
if (!ret.second) 
{ 
--i; 
cout<<"您输入的元素已存在!请重新输入!"<<endl; 
} 
} 
cout<<"-------------运行结果如下:--------------"<<endl; 
}
map<vector<string>,unsigned int>Apriori::find_freitem() 
{ 
unsigned int i=1; 
bool isEmpty=false; 
map<int, vector<string>>::iterator mit; 
for (mit=item.begin();mit!=item.end();mit++) 
{ 
vector<string>vec=mit->second; 
if(vec.size() !=0) 
break; 
} 
if(mit==item.end()) //事务集为空 
{ 
isEmpty=true; 
cout<<"事务集为空!程序无法进行……"<<endl; 
map<vector<string>,unsigned int>empty; 
return empty; 
} 
while(1) 
{ 
map<vector<string>,unsigned int>K_itemTemp=K_item; 
K_item =apri_gen(i++,K_item); 
if (K_itemTemp ==K_item) 
{ 
i=UINT_MAX; 
break; 
} 
//判断是否需要进行下一次寻找 
map<vector<string>,unsigned int>pre_K_item=K_item; 
size_t Kitemsize=K_item.size(); 
//存储应该删除的第K 级频繁项集, 不能和其他K 级频繁项集构成第K+1 级项集的
//集合

43 
if(Kitemsize!=1 && i!=1) 
{ 
vector<map<vector<string>,unsigned int>::iterator >eraseVecMit; 
map<vector<string>,unsigned int>::iterator pre_K_item_it1= pre_K 
_item.begin(), pre_K_item_it2; 
while (pre_K_item_it1!=pre_K_item.end()) 
{ 
map<vector<string>,unsigned int>::iterator mit =pre_K_item_it1; 
bool isExist=true; 
vector<string>vec1; 
vec1=pre_K_item_it1->first; 
vector<string>vec11(vec1.begin(),vec1.end()-1); 
while (mit!=pre_K_item.end()) 
{ 
vector<string>vec2; 
vec2=mit->first; 
vector<string>vec22(vec2.begin(),vec2.end()-1); 
if (vec11==vec22) 
break; 
++mit; 
} 
if(mit==pre_K_item.end()) 
isExist=false; 
if(!isExist && pre_K_item_it1!=pre_K_item.end()) 
eraseVecMit.push_back(pre_K_item_it1);//该第K 级频繁项应该
//删除 
++pre_K_item_it1; 
} 
size_t eraseSetSize=eraseVecMit.size(); 
if (eraseSetSize==Kitemsize) 
break; 
else 
{ 
vector < map < vector < string >, unsigned int >:: iterator >:: 
iterator currentErs=eraseVecMit.begin(); 
while (currentErs!=eraseVecMit.end())//删除所有应该删除的第K 级
//频繁项 
{ 
map<vector<string>,unsigned int>::iterator eraseMit= 
*currentErs; 
K_item.erase(eraseMit); 
++currentErs; 
} 
} 
} 
else 
if(Kitemsize ==1) 
break; 
}

44 
cout<<endl; 
showAprioriItem(i,K_item); 
return K_item; 
}
map<vector< string >, unsigned int > Apriori:: apri _gen(unsigned int K, map < 
vector<string>,unsigned int>K_item) 
{ 
if(1==K) //求候选项集C1 
{ 
size_t c1=item_size; 
map<int, vector<string>>::iterator mapit=item.begin(); 
vector<string>vec; 
map<string,unsigned int>c1_itemtemp; 
while (mapit!=item.end()) //将原事务中所有的单项统计出来 
{ 
vector<string>temp=mapit->second; 
vector<string>::iterator vecit=temp.begin(); 
while (vecit!=temp.end()) 
{ 
pair<map<string,unsigned int>::iterator, bool>ret=c1_ 
itemtemp.insert(make_pair(*vecit++, 1)); 
if (!ret.second) 
{ 
++ret.first->second; 
} 
} 
++mapit; 
} 
map<string,unsigned int>::iterator item_it=c1_itemtemp.begin(); 
map<vector<string>,unsigned int>c1_item; 
while (item_it!=c1_itemtemp.end()) //构造第1 级频繁项集 
{ 
vector<string>temp; 
if(item_it->second >=min_value) 
{ 
temp.push_back(item_it->first); 
c1_item.insert(make_pair(temp, item_it->second)); 
} 
++item_it; 
} 
return c1_item; 
} 
else 
{ 
cout<<endl; 
showAprioriItem(K-1,K_item);

45 
map<vector<string>,unsigned int>::iterator ck_item_it1=K_item.begin(), 
ck_item_it2; 
map<vector<string>,unsigned int>ck_item; 
while (ck_item_it1!=K_item.end()) 
{ 
ck_item_it2=ck_item_it1; 
++ck_item_it2; 
map<vector<string>,unsigned int>::iterator mit=ck_item_it2; 
//取当前第K 级频繁项与其后面的第K 级频繁项集联合, 但要注意联合条件 
//联合条件:两个频繁项的前K-1 项完全相同, 只是第K 项不同, 然后两个联合
//生成第K+1 级候选频繁项 
while(mit!=K_item.end()) 
{ 
vector<string>vec,vec1,vec2; 
vec1=ck_item_it1->first; 
vec2=mit->first; 
vector<string>::iterator vit1,vit2; 
vit1=vec1.begin(); 
vit2=vec2.begin(); 
while (vit1<vec1.end() && vit2<vec2.end()) 
{ 
string str1 =*vit1; 
string str2 =*vit2; 
++vit1; 
++vit2; 
if (K==2 || str1==str2) 
{ 
if(vit1!=vec1.end() && vit2!=vec2.end()) 
{ 
vec.push_back(str1); 
} 
} 
else 
break; 
} 
if(vit1==vec1.end() && vit2==vec2.end()) 
{ 
--vit1; 
--vit2; 
string str1 =*vit1; 
string str2 =*vit2; 
if (str1>str2) 
{ 
vec.push_back(str2); 
vec.push_back(str1); 
} 
else

46 
{ 
vec.push_back(str1); 
vec.push_back(str2); 
} 
map<int, vector<string>>::iterator base_item=item.begin(); 
unsigned int Acount=0; 
while (base_item!=item.end() )//统计该K+1 级候选项在原事务集
//出现的次数 
{ 
unsigned int count=0,mincount=UINT_MAX; 
vector<string>vv=base_item->second; 
vector<string>::iterator vecit, bvit; 
for (vecit=vec.begin();vecit <vec.end();vecit++) 
{ 
string t=*vecit; 
count=0; 
for (bvit=vv.begin();bvit <vv.end();bvit++) 
{ 
if(t==*bvit) 
count++; 
} 
mincount=(count <mincount? count: mincount); 
} 
if(mincount>=1 && mincount!=UINT_MAX) 
Acount+=mincount; 
++base_item; 
} 
if(Acount >=min_value && Acount!=0) 
{ 
sort(vec.begin(),vec.end()); 
//该第K+1 级候选项为频繁项, 插入频繁项集 
pair<map<vector<string>,unsigned int>::iterator, 
bool>ret=ck_item.insert(make_pair(vec,Acount)); 
if (!ret.second) 
{ 
ret.first->second +=Acount; 
} 
} 
} 
++mit; 
} 
++ck_item_it1; 
} 
if (ck_item.empty()) //该第K+1 级频繁项集为空, 说明调用结束, 返回上一级
//频繁项集 
return K_item; 
else 
return ck_item; 
}

47 
}v
oid Apriori::showAprioriItem(unsigned int K,map<vector<string>,unsigned int> 
showmap) 
{ 
map<vector<string>,unsigned int>::iterator showit=showmap.begin(); 
if(K!=UINT_MAX) 
cout<<endl<<"第"<<K<<" 级频繁项集:"<<endl; 
else 
cout<<"最终的频繁项集:"<<endl; 
cout<<"项 集"<<" \t "<<"频 率"<<endl; 
while (showit!=showmap.end()) 
{ 
vector<string>vec=showit->first; 
vector<string>::iterator vecit=vec.begin(); 
cout<<"{ "; 
while (vecit!=vec.end()) 
{ 
cout<<*vecit<<" "; 
++vecit; 
} 
cout<<"}"<<" \t "; 
cout<<showit->second<<endl; 
++showit; 
} 
}
unsigned int parseNumber(const char *str) //对用户输入的数字进行判断和转换
{ 
if(str==NULL) 
return 0; 
else 
{ 
unsigned int num=0; 
size_t len=strlen(str); 
for(size_t i=0;i<len;i++) 
{ 
num *=10; 
if(str[i]>='0' && str[i]<='9') 
num +=str[i] -'0'; 
else 
return 0; 
} 
return num; 
} 
}
void main() 
{ 
//Apriori a;

48 
unsigned int itemsize=0; 
unsigned int min; 
do 
{ 
cout<<"请输入事务数:"; 
char *str=new char; 
cin>>str; 
itemsize=parseNumber(str); 
if (itemsize==0) 
{ 
cout<<"请输入大于0 的正整数!"<<endl; 
} 
} while (itemsize==0); 
do 
{ 
cout<<"请输入最小阈值:"; 
char *str=new char; 
cin>>str; 
min=parseNumber(str); 
if (min==0) 
{ 
cout<<"请输入大于0 的正整数!"<<endl; 
} 
} while(min==0); 
Apriori a(itemsize,min); 
a.getItem(); 
map<vector<string>,unsigned int>AprioriMap=a.find_freitem(); 
//a.showAprioriItem(UINT_MAX,AprioriMap); 
system("pause"); 
}
上述程序的运行结果如图3-1所示。输入事务数为9,最小阈值为2。9个事务的项集如
下:{I1,I2,I5} ,{I2,I4} ,{I2,I3} ,{I1,I2,I4} ,{I1,I3} ,{I2,I3} ,{I1,I3} ,{I1,I2,I3,I5} , 
{I1,I2,I3} 。程序首先搜索9个事务的项集,统计第1级备选项的支持度,如图3-1所
示。将备选项的支持度与最小阈值进行比较。由于最小阈值为2,因此不需要删除备选
项,所得的第1级频繁项集:{I1} ,{I2} ,{I3} ,{I4} ,{I5} 。为产生第2级频繁项集,程
序进行连接,将第1级频繁项集与自身连接得到第2级备选项,然后进行剪枝,去除非频
繁备选项,再比较所剩备选项的支持度与最小阈值,即得第2级频繁项集:{I1,I2} , 
{I1,I3} ,{I1,I5} ,{I2,I3} ,{I2,I4} ,{I2,I5} 。按照上述步骤进行下去得到最终的频
繁项集:{I1,I2,I3} ,{I1,I2,I5} 。

图3-
1 
程序运行结果

3.5 
Apriori算法的特点及应用
3.5.1 
Apriori算法特点
Apriori算法是应用最广泛的关联规则挖掘算法,它有如下优点。

(1)Apriori算法是一个迭代算法。该算法首先挖掘生成L1,然后由L1 生成C2,再
由C2扫描事务数据库得到L2;根据L2生成C3,由C3扫描事务数据库得到L3;直到Ck 
为空而产生所有频繁项集,Apriori算法将生成所有大于或等于最小支持度的频繁项集。

(2)数据采用水平组织方式。水平组织就是数据按照{事务编号,项集}的形式组织。
(3)采用Apriori优化方法。Apriori优化就是利用Apriori性质进行的优化。
(4)适合事务数据库的关联规则挖掘。
(5)适合稀疏数据集。根据以往的研究,该算法只能适合稀疏数据集的关联规则挖
掘,也就是频繁项集长度稍小的数据集。
49 


Apriori算法作为经典的频繁项集生成算法,在数据挖掘中具有里程碑的作用,但是
随着研究的深入,它的缺点也暴露出来,主要有以下3个缺点。

(1)多次扫描事务数据库,需要很大的I/O负载。在Apriori算法的扫描中,对第
k 
次循环,候选项集Ck 
中的每个元素都要扫描数据库一遍来验证其是否加入Lk 
,假如一个
频繁项集包含10 项,那么就至少需要扫描数据库10 遍。当数据库中存放大量的事务数
据时,在有限的内存容量下系统I/O负载相当大,每次扫描数据库的时间就会很长,这样
效率就会非常低。
(2)可能产生庞大的候选项集。Apriori算法由Lk-1 产生k-候选项集Ck 
,其结果是
指数增长的,例如,104 个频繁1-项集就有可能产生接近107 个元素的候选2-项集。如此
大的候选项集对时间和内存容量都是一种挑战。
(3)在频繁项集长度变大的情况下,运算时间显著增加。当频繁项集长度变大时,支
持该频繁项集的事务会减少。从理论上讲,计算其支持度需要的时间不会明显增加,但
Apriori算法仍然是在原来事务数据库中来计算长频繁项集的支持度。由于每个频繁项
集的项目变多了,所以在确定每个频繁项集是否被事务支持的开销也增大了,而且事务没
有减少,因此频繁项集长度增加了,运算时间也显著增加了。
3.2 
Apiri算法应用
5.ro

Apriori算法是应用最广泛的关联规则挖掘算法,通过对各种领域数据的关联性进行
分析,挖掘成果在相关的决策制定过程中具有重要的参考价值。

Apriori算法广泛应用于商业中,例如,应用于消费市场价格分析中,它能够很快地求
出各种产品之间的价格关系和它们之间的影响。通过数据挖掘,市场人员可以瞄准目标
客户,采用个人股票行市、最新信息、特殊的市场推广活动或其他一些特殊的信息手段,从
而极大地减少广告预算,增加收入。

Apriori算法应用于网络安全领域,如入侵检测技术。早期中大型的计算机系统中都
收集了审计信息来建立跟踪档案,这些审计跟踪的目的多是为了性能测试或计费,因此对
攻击检测提供的有用信息比较少。它通过模式学习和训练可以发现网络用户的异常行为
模式,使网络入侵检测系统可以快速发现用户的行为模式,能够快速锁定攻击者,提高了
基于关联规则的入侵检测系统的检测性能。

Apriori算法应用于高校管理中。随着高校贫困生人数的不断增加,学校管理部门资
助工作难度也越来越大,数据挖掘算法可以帮助相关部门解决上述问题。例如,有的研究
者将关联规则的Apriori算法应用到贫困助学体系中,并且针对经典Apriori挖掘算法存
在的不足进行改进,先将事务数据库映射为一个布尔矩阵,用一种逐层递增的思想来动态
地分配内存进行存储,再利用向量求“与”运算,寻找频繁项集。实验结果表明,这种改进
后的Apriori算法在运行效率上有了很大的提升,挖掘出的规则也可以有效地辅助学校
管理部门有针对性地开展贫困助学工作。

Apriori算法被广泛应用于移动通信领域。移动增值业务逐渐成为移动通信市场上
最有活力、最具潜力、最受瞩目的业务。随着产业的复苏,越来越多的增值业务表现出强

50 

51 
劲的发展势头,呈现出应用多元化、营销品牌化、管理集中化、合作纵深化的特点。针对这
种趋势,在关联规则数据挖掘中广泛应用的Apriori算法被很多公司应用。例如,依托某
电信运营商正在建设的增值业务Web数据仓库平台,对来自移动增值业务方面的调查数
据进行了相关的挖掘处理,从而获得了关于用户行为特征和需求的间接反映市场动态的
有用信息,这些信息在指导运营商的业务运营和辅助业务提供商的决策制定等方面具有
十分重要的参考价值。
3.6 小结
本章详细地介绍了关联规则挖掘的基本概念,对经典的关联规则挖掘算法——— 
Apriori算法的原理,以及发现频繁项集的过程进行了描述,并用实例进行了说明,同时还
分析了Apriori算法的特点和该算法存在的缺陷,得出它在发现频繁项集的过程中需要
多次扫描事务数据库,此外还要产生大量的候选项集,这都会对算法的效率产生很大的影
响,并且在频繁项集长度变大的情况下,运算时间显著增加,最后介绍了Apriori算法在
商业、网络安全、高校管理和移动通信等领域的应用。
思考题
1.解释关联规则的定义。
2.描述Apriori关联规则挖掘算法。
3.如表3-3所示的数据库有5个事物。设min_sup=60%,min_conf=80%。
表3-3 数据库
TID 购买的商品TID 购买的商品
I100 {M,O,N,K,E,Y} I400 {M,U,C,K,Y} 
I200 {D,O,N,K,E,Y} I500 {C,O,O,K,I,E} 
I300 {M,A,K,E} 
(1)分别使用Apriori和FP增长算法找出所有频繁项集。比较两种挖掘过程的
效率。
(2)列举所有与下面的元规则匹配的强关联规则(给出支持度s 和置信度c),其中, 
X 代表客户的变量;itemi 表示项的变量(如A、B等): 
.x∈transaction,buys(X ,item1)∧buys(X ,item2).buys(X ,item3)s[ ,c] 
4.如表3-4所示的关系表People是要挖掘的数据集,有3个属性(Age,Married, 
NumCars)。假如用户指定的min_sup=60%,min_conf=80%,试挖掘表3-4中的数量
关联规则。

表3-
4 
关系表People 

RecordID 
Age 
Maried 
NumCars 
RecordID 
Age 
Maried 
NumCars 
100 23 No 0 400 34 Yes 2 
200 25 Yes 1 500 38 Yes 2 
300 29 No 1 

52