前面小编在介绍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; }
数据分析咨询请扫描二维码
若不方便扫码,搜微信号:CDAshujufenxi
活动介绍 为了助力大家在数据分析领域不断精进技能,我们特别举办本期打卡活动。在这里,你可以充分利用碎片化时间在线学习,让 ...
2025-02-071、闺女,醒醒,媒人把相亲的带来了。 我。。。。。。。 2、前年春节相亲相了40个, 去年春节相亲50个, 祖宗,今年你想相多少个 ...
2025-02-06在数据科学的广阔领域中,统计分析与数据挖掘占据了重要位置。尽管它们常常被视为有关联的领域,但两者在理论基础、目标、方法及 ...
2025-02-05在数据分析的世界里,“对比”是一种简单且有效的方法。这就像两个女孩子穿同一款式的衣服,效果不一样。 很多人都听过“货比三 ...
2025-02-05当我们只有非常少量的已标记数据,同时有大量未标记数据点时,可以使用半监督学习算法来处理。在sklearn中,基于图算法的半监督 ...
2025-02-05考虑一种棘手的情况:训练数据中大部分样本没有标签。此时,我们可以考虑使用半监督学习方法来处理。半监督学习能够利用这些额 ...
2025-02-04一、数学函数 1、取整 =INT(数字) 2、求余数 =MOD(除数,被除数) 3、四舍五入 =ROUND(数字,保留小数位数) 4、取绝对值 =AB ...
2025-02-03作者:CDA持证人 余治国 一般各平台出薪资报告,都会哀嚎遍野。举个例子,去年某招聘平台发布《中国女性职场现状调查报告》, ...
2025-02-02真正的数据分析大神是什么样的呢?有人认为他们能轻松驾驭各种分析工具,能够从海量数据中找到潜在关联,或者一眼识别报告中的数 ...
2025-02-01现今社会,“转行”似乎成无数职场人无法回避的话题。但行业就像座围城:外行人看光鲜,内行人看心酸。数据分析这个行业,近几年 ...
2025-01-31本人基本情况: 学校及专业:厦门大学经济学院应用统计 实习经历:快手数据分析、字节数据分析、百度数据分析 Offer情况:北京 ...
2025-01-3001专家简介 徐杨老师,CDA数据科学研究院教研副总监,主要负责CDA认证项目以及机器学习/人工智能类课程的研发与授课,负责过中 ...
2025-01-29持证人简介 郭畅,CDA数据分析师二级持证人,安徽大学毕业,目前就职于徽商银行总行大数据部,两年工作经验,主要参与两项跨部 ...
2025-01-282025年刚开启,知乎上就出现了一个热帖: 2024年突然出现的经济下行,使各行各业都感觉到压力山大。有人说,大环境越来越不好了 ...
2025-01-27在数据分析的世界里,“对比”是一种简单且有效的方法。这就像两个女孩子穿同一款式的衣服,效果不一样。 很多人都听过“货比三 ...
2025-01-26数据指标体系 “数据为王”相信大家都听说过。当前,数据信息不再仅仅是传递的媒介,它成为了驱动经济发展的新燃料。对于企业而 ...
2025-01-26在职场中,当你遇到问题的时候,如果感到无从下手,或者抓不到重点,可能是因为你掌握的思维模型不够多。 一个好用的思维模型, ...
2025-01-25俗话说的好“文不如表,表不如图”,图的信息传达效率很高,是数据汇报、数据展示的重要手段。好的数据展示不仅需要有图,还要选 ...
2025-01-24数据分析报告至关重要 一份高质量的数据分析报告不仅能够揭示数据背后的真相,还能为企业决策者提供有价值的洞察和建议。 年薪70 ...
2025-01-24又到一年年终时,各位打工人也迎来了展示成果的关键时刻 —— 年终述职。一份出色的年终述职报告,不仅能全面呈现你的工作价值, ...
2025-01-23