数据挖掘领域，关联规则是数据中一种简单但很实用的规则。发现关联规则的算法属于无监督学习的方法，常用的有三种：Apriori算法、基于划分的算法、FP-树频集算法。
Apriori算法
基本思想： 如果一个项集是频繁项目集，那么它的非空子集必定是频繁项目集。它先生成1-频繁项目集，再利用1-频繁项目集生成2-频繁项目集。。。然后根据2-频繁项目集生成3-频繁项目集。。。依次类推，直至生成所有的频繁项目集，然后从频繁项目集中找出符合条件的关联规则。
下面证明一下为何可以通过k-频繁项目集生成（k+1）-频繁项目集：
假设某个项目集S={s1，s2…，sn}是频繁项目集，那么它的（n-1）非空子集{s1，s2，…sn-1}，{s1，s2，…sn-2，sn}…{s2，s3，…sn}必定都是频繁项目集，通过观察，任何一个含有n个元素的集合A={a1，a2，…an}，它的（n-1）非空子集必行包含两项{a1，a2，…an-2，an-1}和 {a1，a2，…an-2，an}，对比这两个子集可以发现，它们的前（n-2）项是相同的，它们的并集就是集合A。对于2-频繁项目集，它的所有1非空子集也必定是频繁项目集，对于2-频繁项目集中的任一个，在1-频繁项目集中必定存在2个集合的并集与它相同。因此在所有的1-频繁项目集中找出只有最后一项不同的集合，将其合并，即可得到所有的包含2个元素的项目集，得到的这些包含2个元素的项目集不一定都是频繁项目集，所以需要进行剪枝。剪枝的办法是看它的所有1非空子集是否在1-频繁项目集中，如果存在1非空子集不在1-频繁项目集中，则将该2项目集剔除。经过该步骤之后，剩下的则全是频繁项目集，即2-频繁项目集。依次类推，可以生成3-频繁项目集。。直至生成所有的频繁项目集。
得到频繁项目集之后，则需要从频繁项目集中找出符合条件的关联规则。最简单的办法是：遍历所有的频繁项目集，然后从每个项目集中依次取1、2、…k个元素作为后件，该项目集中的其他元素作为前件，计算该规则的置信度进行筛选即可。这样的穷举效率显然很低。假如对于一个频繁项目集f，可以生成下面这样的关联规则：
（f-β）—>β
那么这条规则的置信度=f.count/(f-β).count
根据这个置信度计算公式可知，对于一个频繁项目集f.count是不变的，而假设该规则是强关联规则，则（f-βsub）—>βsub也是强关联规则，其中βsub是β的子集，因为(f-βsub).count肯定小于(f-β).count。即给定一个频繁项目集f，如果一条强关联规则的后件为β，那么以β的非空子集为后件的关联规则都是强关联规则。所以可以先生成所有的1-后件（后件只有一项）强关联规则，然后再生成2-后件强关联规则，依次类推，直至生成所有的强关联规则。
下面举例说明Apiori算法的具体流程：
假如有项目集合I={1，2，3，4，5}，有事务集T：
1,2,3
1,2,4
1,3,4
1,2,3,5
1,3,5
2,4,5
1,2,3,4
设定minsup=3/7，misconf=5/7。
首先：生成频繁项目集：
1-频繁项目集：{1}，{2}，{3}，{4}，{5}
生成2-频繁项目集：
根据1-频繁项目集生成所有的包含2个元素的项目集：任意取两个只有最后一个元素不同的1-频繁项目集，求其并集，由于每个1-频繁项目集元素只有一个，所以生成的项目集如下：
{1，2}，{1，3}，{1，4}，{1，5}
{2，3}，{2，4}，{2，5}
{3，4}，{3，5}
{4，5}
计算它们的支持度，发现只有{1，2}，{1，3}，{1，4}，{2，3}，{2，4}，{2，5}的支持度满足要求，因此求得2-频繁项目集：
{1，2}，{1，3}，{1，4}，{2，3}，{2，4}
生成3-频繁项目集：
因为{1，2}，{1，3}，{1，4}除了最后一个元素以外都相同，所以求{1，2}，{1，3}的并集得到{1，2，3}， {1，2}和{1，4}的并集得到{1，2，4}，{1，3}和{1，4}的并集得到{1，3，4}。但是由于{1，3，4}的子集{3，4}不在2-频繁项目集中，所以需要把{1，3，4}剔除掉。然后再来计算{1，2，3}和{1，2，4}的支持度，发现{1，2，3}的支持度为3/7 ，{1，2，4}的支持度为2/7，所以需要把{1，2，4}剔除。同理可以对{2，3}，{2，4}求并集得到{2，3，4} ，但是{2，3，4}的支持度不满足要求，所以需要剔除掉。
因此得到3-频繁项目集：{1，2，3}。
到此频繁项目集生成过程结束。注意生成频繁项目集的时候，频繁项目集中的元素个数最大值为事务集中事务中含有的最大元素个数，即若事务集中事务包含的最大元素个数为k，那么最多能生成k-频繁项目集，这个原因很简单，因为事务集合中的所有事务都不包含（k+1）个元素，所以不可能存在（k+1）-频繁项目集。在生成过程中，若得到的频繁项目集个数小于2，生成过程也可以结束了。
现在需要生成强关联规则：
这里只说明3-频繁项目集生成关联规则的过程：
对于集合{1，2，3}
先生成1-后件的关联规则：
（1，2）—>3， 置信度=3/4
（1，3）—>2， 置信度=3/5
（2，3）—>1 置信度=3/3
（1，3）—>2的置信度不满足要求，所以剔除掉。因此得到1后件的集合{1}，{3}，然后再以{1，3}作为后件
2—>1，3 置信度=3/5不满足要求，所以对于3-频繁项目集生成的强关联规则为：（1，2）—>3和（2，3）—>1。
算法实现：
/*Apriori算法 2012.10.31*/
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;
vector<string> T; //保存初始输入的事务集
double minSup,minConf; //用户设定的最小支持度和置信度
map<string,int> mp; //保存项目集中每个元素在事务集中出现的次数
vector< vector<string> > F; //存放频繁项目集
vector<string> R; //存放关联规则
void initTransactionSet() //获取事务集
{
int n;
cout<<"请输入事务集的个数:"<<endl;
cin>>n;
getchar();
cout<<"请输入事务集:"<<endl;
while(n--)
{
string str;
getline(cin,str); //输入的事务集中每个元素以空格隔开,并且只能输入数字
T.push_back(str);
}
cout<<"请输入最小支持度和置信度:"<<endl; //支持度和置信度为小数表示形式
cin>>minSup>>minConf;
}
vector<string> split(string str,char ch)
{
vector<string> v;
int i,j;
i=;
while(i<str.size())
{
if(str[i]==ch)
i++;
else
{
j=i;
while(j<str.size())
{
if(str[j]!=ch)
j++;
else
break;
}
string temp=str.substr(i,j-i);
v.push_back(temp);
i=j+;
}
}
return v;
}
void genarateOneFrequenceSet() //生成1-频繁项目集
{
int i,j;
vector<string> f; //存储1-频繁项目集
for(i=;i<T.size();i++)
{
string t = T[i];
vector<string> v=split(t,' '); //将输入的事务集进行切分，如输入1 2 3，切分得到"1","2","3"
for(j=;j<v.size();j++) //统计每个元素出现的次数，注意map默认按照key的升序排序
{
mp[v[j]]++;
}
}
for(map<string,int>::iterator it=mp.begin();it!=mp.end();it++) //剔除不满足最小支持度要求的项集
{
if( (*it).second >= minSup*T.size())
{
f.push_back((*it).first);
}
}
F.push_back(T); //方便用F[1]表示1-频繁项目集
if(f.size()!=)
{
F.push_back(f);
}
}
bool judgeItem(vector<string> v1,vector<string> v2) //判断v1和v2是否只有最后一项不同
{
int i,j;
i=;
j=;
while(i<v1.size()-&&j<v2.size()-)
{
if(v1[i]!=v2[j])
return false;
i++;
j++;
}
return true;
}
bool judgeSubset(vector<string> v,vector<string> f) //判断v的所有k-1子集是否在f中
{
int i,j;
bool flag=true;
for(i=;i<v.size();i++)
{
string str;
for(j=;j<v.size();j++)
{
if(j!=i)
str+=v[j]+" ";
}
str=str.substr(,str.size()-);
vector<string>::iterator it=find(f.begin(),f.end(),str);
if(it==f.end())
flag=false;
}
return flag;
}
int calculateSupportCount(vector<string> v) //计算支持度计数
{
int i,j;
int count=;
for(i=;i<T.size();i++)
{
vector<string> t=split(T[i],' ');
for(j=;j<v.size();j++)
{
vector<string>::iterator it=find(t.begin(),t.end(),v[j]);
if(it==t.end())
break;
}
if(j==v.size())
count++;
}
return count;
}
bool judgeSupport(vector<string> v) //判断一个项集的支持度是否满足要求
{
int count=calculateSupportCount(v);
if(count >= ceil(minSup*T.size()))
return true;
return false;
}
void generateKFrequenceSet() //生成k-频繁项目集
{
int k;
for(k=;k<=mp.size();k++)
{
if(F.size()< k) //如果Fk-1为空，则退出
break;
else //根据Fk-1生成Ck候选项集
{
int i,j;
vector<string> c;
vector<string> f=F[k-];
for(i=;i<f.size()-;i++)
{
vector<string> v1=split(f[i],' ');
for(j=i+;j<f.size();j++)
{
vector<string> v2=split(f[j],' ');
if(judgeItem(v1,v2)) //如果v1和v2只有最后一项不同，则进行连接
{
vector<string> tempVector=v1;
tempVector.push_back(v2[v2.size()-]);
sort(tempVector.begin(),tempVector.end()); //对元素排序，方便判断是否进行连接
//剪枝的过程
//判断 v1的(k-1)的子集是否都在Fk-1中以及是否满足最低支持度
if(judgeSubset(tempVector,f)&&judgeSupport(tempVector))
{
int p;
string tempStr;
for(p=;p<tempVector.size()-;p++)
tempStr+=tempVector[p]+" ";
tempStr+=tempVector[p];
c.push_back(tempStr);
}
}
}
}
if(c.size()!=)
F.push_back(c);
}
}
}
vector<string> removeItemFromSet(vector<string> v1,vector<string> v2) //从v1中剔除v2
{
int i;
vector<string> result=v1;
for(i=;i<v2.size();i++)
{
vector<string>::iterator it= find(result.begin(),result.end(),v2[i]);
if(it!=result.end())
result.erase(it);
}
return result;
}
string getStr(vector<string> v1,vector<string> v2) //根据前件和后件得到规则
{
int i;
string rStr;
for(i=;i<v1.size();i++)
rStr+=v1[i]+" ";
rStr=rStr.substr(,rStr.size()-);
rStr+="->";
for(i=;i<v2.size();i++)
rStr+=v2[i]+" ";
rStr=rStr.substr(,rStr.size()-);
return rStr;
}
void ap_generateRules(string fs)
{
int i,j,k;
vector<string> v=split(fs,' ');
vector<string> h;
vector< vector<string> > H; //存放所有的后件
int fCount=calculateSupportCount(v); //f的支持度计数
for(i=;i<v.size();i++) //先生成1-后件关联规则
{
vector<string> temp=v;
temp.erase(temp.begin()+i);
int aCount=calculateSupportCount(temp);
if( fCount >= ceil(aCount*minConf)) //如果满足置信度要求
{
h.push_back(v[i]);
string tempStr;
for(j=;j<v.size();j++)
{
if(j!=i)
tempStr+=v[j]+" ";
}
tempStr=tempStr.substr(,tempStr.size()-);
tempStr+="->"+v[i];
R.push_back((tempStr));
}
}
H.push_back(v);
if(h.size()!=)
H.push_back(h);
for(k=;k<v.size();k++) //生成k-后件关联规则
{
h=H[k-];
vector<string> addH;
for(i=;i<h.size()-;i++)
{
vector<string> v1=split(h[i],' ');
for(j=i+;j<h.size();j++)
{
vector<string> v2=split(h[j],' ');
if(judgeItem(v1,v2))
{
vector<string> tempVector=v1;
tempVector.push_back(v2[v2.size()-]); //得到后件集合
sort(tempVector.begin(),tempVector.end());
vector<string> filterV=removeItemFromSet(v,tempVector); //得到前件集合
int aCount=calculateSupportCount(filterV); //计算前件支持度计数
if(fCount >= ceil(aCount*minConf)) //如果满足置信度要求
{
string rStr=getStr(filterV,tempVector); //根据前件和后件得到规则
string hStr;
for(int s=;s<tempVector.size();s++)
hStr+=tempVector[s]+" ";
hStr=hStr.substr(,hStr.size()-);
addH.push_back(hStr); //得到一个新的后件集合
R.push_back(rStr);
}
}
}
}
if(addH.size()!=) //将所有的k-后件集合加入到H中
H.push_back(addH);
}
}
void generateRules() //生成关联规则
{
int i,j,k;
for(k=;k<F.size();k++)
{
vector<string> f=F[k];
for(i=;i<f.size();i++)
{
string str=f[i];
ap_generateRules(str);
}
}
}
void outputFrequenceSet() //输出频繁项目集
{
int i,k;
if(F.size()==)
{
cout<<"无频繁项目集!"<<endl;
return;
}
for(k=;k<F.size();k++)
{
cout<<k<<"-频繁项目集:"<<endl;
vector<string> f=F[k];
for(i=;i<f.size();i++)
cout<<f[i]<<endl;
}
}
void outputRules() //输出关联规则
{
int i;
cout<<"关联规则:"<<endl;
for(i=;i<R.size();i++)
{
cout<<R[i]<<endl;
}
}
void Apriori()
{
initTransactionSet();
genarateOneFrequenceSet();
generateKFrequenceSet();
outputFrequenceSet();
generateRules();
outputRules();
}
int main(int argc, char *argv[])
{
Apriori();
return ;
}
测试数据：
7
1 2 3
1 4
4 5
1 2 4
1 2 6 4 3
2 6 3
2 3 6
0.3 0.8
运行结果：
1-频繁项目集:
1
2
3
4
6
2-频繁项目集:
1 2
1 4
2 3
2 6
3 6
3-频繁项目集:
2 3 6
关联规则:
3->2
2->3
6->2
6->3
3 6->2
2 6->3
6->2 3
请按任意键继续…
Apriori算法采用了逐层搜索的迭代的方法，简单明了易于实现。但其有一些难以克服的缺点：
（1）对数据库的扫描次数过多。
（2）Apriori算法会产生大量的中间项集。
（3）采用唯一支持度。
（4）算法的适应面窄。