前面小编在介绍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; }
数据分析咨询请扫描二维码
大数据分析师证书 针对不同知识,掌握程度的要求分为【领会】、【熟知】、【应用】三个级别,考生应按照不同知识要求进行学习。 ...
2024-10-29拥抱数据分析的世界 - 成为一名数据分析工程师是一个充满挑战和机遇的职业选择。要成功地进入这个领域,你需要掌握一系列关键技 ...
2024-10-28降本增效:管理战略的关键 企业管理中的降本增效不仅是一项重要的战略举措,更是激发竞争力、提高盈利能力的关键。这一理念在当 ...
2024-10-28企业数字化是指利用数字技术和信息化手段,对企业的各个方面进行改造和优化,以提升生产效率、服务质量和市场竞争力的过程。实现 ...
2024-10-28数据科学专业毕业后,毕业生可以选择从事多种不同的岗位和领域。数据科学是一个快速发展且广泛应用的领域,毕业生在企业、学术界 ...
2024-10-28学习数据科学与大数据技术是当今职业发展中至关重要的一环。从基础到高级,以下是一些建议的课程路径: 基础课程: Python编程 ...
2024-10-28在信息技术和数据科学领域,数据架构师扮演着至关重要的角色。他们负责设计和管理企业中复杂的数据基础设施,以支持数据驱动的决 ...
2024-10-28进入21世纪以来,随着信息技术的迅猛发展,大数据已经成为全球最具影响力的技术之一,并成为企业数字化转型的核心驱动力。大数据 ...
2024-10-28随着科技的迅猛发展,数字化转型已成为现代企业保持竞争力和推动增长的关键战略之一。数字化不仅仅是技术的应用,它代表着一种全 ...
2024-10-28银行业正处于一个前所未有的数字化转型时期。在数字经济的驱动下,金融科技如大数据、人工智能、生物识别、物联网和云计算等技术 ...
2024-10-28数据分析可视化是一门艺术与科学相结合的技术,其主要目标是将复杂的数据变得更易于理解和分析。通过将数据以图表的形式呈现,我 ...
2024-10-28数据分析师在现代信息密集型的商业世界中扮演着至关重要的角色。他们通过专业的技能和敏锐的商业洞察力,帮助企业从大量数据中提 ...
2024-10-28在当今快速发展的数据驱动世界中,数据专员的角色变得愈发重要。无论是在企业决策、市场分析还是产品开发中,数据专员都扮演着不 ...
2024-10-27在当今迅速发展的科技时代,数字化对企业的意义无比深远。它不仅提升了企业的竞争力和运营效率,还显著改善了客户体验,推动了企 ...
2024-10-27企业数字化转型是一个全方位的变革过程,旨在通过应用新兴数字技术,重新设计企业的业务流程、组织结构、产品和服务,以在竞争激 ...
2024-10-27数据挖掘是一种集成了统计学、人工智能和机器学习等多种技术的过程,其主要目标是从大量数据中提取有价值的信息和知识。通过分析 ...
2024-10-27数字经济是一种新型的经济形态,以数字技术为基础,通过数据的获取、存储、加工、传输和应用进行经济发展。其核心在于利用数字化 ...
2024-10-27数据科学无疑是现代数字化社会的中流砥柱。随着大数据和人工智能技术的持续飞跃,各行各业对具备数据分析和管理能力的人才需求呈 ...
2024-10-25在当今快速发展的商业环境中,数字化转型已经成为企业保持竞争力和促进业务增长的必然选择。数字化转型不仅意味着技术的变革,更 ...
2024-10-25在当今数据驱动的商业环境中,数据分析已经成为企业决策过程中的核心要素。企业需要处理海量数据,从中提炼出有价值的见解,以支 ...
2024-10-25