前面小编在介绍FP-Growth算法时,提到了Apriori算法,其实FP-Growth是基于Apriori的,今天小编就具体给大家介绍一下Apriori算法。
一、什么是Apriori算法
Apriori算法是一种最有影响的挖掘数据关联规则频繁项集的算法,能够发现事物数据库中频繁出现的数据集,通过这些联系构成的规则,能够帮助用户找出某些行为特征,从而帮助企业进行决策。
Apriori算法基于这样的事实:算法使用频繁项集性质的先验知识。Apriori使用一种称作逐层搜索的迭代方法,k-项集用于探索(k+1)-项集。首先,找出频繁1-项集的集合。该集合记作L1.L1用于找频繁2-项集的集合L2.而L2用于找L3.如此下去,直到不能找到频繁k-项集。找每个Lk需要一次数据库扫描。
算法原始数据如下:
算法的基本过程如下图:
二、Apriori算法原理
1.扫描数据集,得到所有出现过的数据,作为候选1项集。
2.挖掘频繁k项集。
3.扫描计算候选k项集的支持度。
4.剪枝去掉候选k项集中支持度低于最小支持度α的数据集,得到频繁k项集。如果频繁k项集为空,则返回频繁k-1项集的集合作为算法结果,算法结束。如果得到的频繁k项集只有一项,则直接返回频繁k项集的集合作为算法结果,算法结束。
5.基于频繁k项集,连接生成候选k+1项集。
6.利用步骤2.迭代得到k=k+1项集结果。
三、Apriori算法利弊分析
1.利:
适合于稀疏数据集。
算法原理简单,很容易实现。
适合事务数据库的关联规则挖掘。
2.弊
有可能产生庞大的候选集。
算法需多次遍历数据集,效率比较低,而且耗时。
三、算法实现
假如有项目集合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。
*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=0;
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+1;
}
}
return v;
}
void genarateOneFrequenceSet() //生成1-频繁项目集
{
int i,j;
vector<string> f; //存储1-频繁项目集
for(i=0;i<T.size();i++)
{
string t = T[i];
vector<string> v=split(t,' '); //将输入的事务集进行切分,如输入1 2 3,切分得到"1","2","3"
for(j=0;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()!=0)
{
F.push_back(f);
}
}
bool judgeItem(vector<string> v1,vector<string> v2) //判断v1和v2是否只有最后一项不同
{
int i,j;
i=0;
j=0;
while(i<v1.size()-1&&j<v2.size()-1)
{
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=0;i<v.size();i++)
{
string str;
for(j=0;j<v.size();j++)
{
if(j!=i)
str+=v[j]+" ";
}
str=str.substr(0,str.size()-1);
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=0;
for(i=0;i<T.size();i++)
{
vector<string> t=split(T[i],' ');
for(j=0;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=2;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-1];
for(i=0;i<f.size()-1;i++)
{
vector<string> v1=split(f[i],' ');
for(j=i+1;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()-1]);
sort(tempVector.begin(),tempVector.end()); //对元素排序,方便判断是否进行连接
//剪枝的过程
//判断 v1的(k-1)的子集是否都在Fk-1中以及是否满足最低支持度
if(judgeSubset(tempVector,f)&&judgeSupport(tempVector))
{
int p;
string tempStr;
for(p=0;p<tempVector.size()-1;p++)
tempStr+=tempVector[p]+" ";
tempStr+=tempVector[p];
c.push_back(tempStr);
}
}
}
}
if(c.size()!=0)
F.push_back(c);
}
}
}
vector<string> removeItemFromSet(vector<string> v1,vector<string> v2) //从v1中剔除v2
{
int i;
vector<string> result=v1;
for(i=0;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=0;i<v1.size();i++)
rStr+=v1[i]+" ";
rStr=rStr.substr(0,rStr.size()-1);
rStr+="->";
for(i=0;i<v2.size();i++)
rStr+=v2[i]+" ";
rStr=rStr.substr(0,rStr.size()-1);
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=0;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=0;j<v.size();j++)
{
if(j!=i)
tempStr+=v[j]+" ";
}
tempStr=tempStr.substr(0,tempStr.size()-1);
tempStr+="->"+v[i];
R.push_back((tempStr));
}
}
H.push_back(v);
if(h.size()!=0)
H.push_back(h);
for(k=2;k<v.size();k++) //生成k-后件关联规则
{
h=H[k-1];
vector<string> addH;
for(i=0;i<h.size()-1;i++)
{
vector<string> v1=split(h[i],' ');
for(j=i+1;j<h.size();j++)
{
vector<string> v2=split(h[j],' ');
if(judgeItem(v1,v2))
{
vector<string> tempVector=v1;
tempVector.push_back(v2[v2.size()-1]); //得到后件集合
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=0;s<tempVector.size();s++)
hStr+=tempVector[s]+" ";
hStr=hStr.substr(0,hStr.size()-1);
addH.push_back(hStr); //得到一个新的后件集合
R.push_back(rStr);
}
}
}
}
if(addH.size()!=0) //将所有的k-后件集合加入到H中
H.push_back(addH);
}
}
void generateRules() //生成关联规则
{
int i,j,k;
for(k=2;k<F.size();k++)
{
vector<string> f=F[k];
for(i=0;i<f.size();i++)
{
string str=f[i];
ap_generateRules(str);
}
}
}
void outputFrequenceSet() //输出频繁项目集
{
int i,k;
if(F.size()==1)
{
cout<<"无频繁项目集!"<<endl;
return;
}
for(k=1;k<F.size();k++)
{
cout<<k<<"-频繁项目集:"<<endl;
vector<string> f=F[k];
for(i=0;i<f.size();i++)
cout<<f[i]<<endl;
}
}
void outputRules() //输出关联规则
{
int i;
cout<<"关联规则:"<<endl;
for(i=0;i<R.size();i++)
{
cout<<R[i]<<endl;
}
}
void Apriori()
{
initTransactionSet();
genarateOneFrequenceSet();
generateKFrequenceSet();
outputFrequenceSet();
generateRules();
outputRules();
}
int main(int argc, char *argv[])
{
Apriori();
return 0;
}