Apriori算法原理及实现

***********************************************声明******************************************************

      原创作品，出自 “晓风残月xj” 博客，欢迎转载，转载时请务必注明出处（http://blog.csdn.net/xiaofengcanyuexj）。

      由于各种原因，可能存在诸多不足，欢迎斧正！

*********************************************************************************************************

        有这样一个故事：美国的妇女们经常会嘱咐她们的丈夫下班后为孩子买尿布，而丈夫在买完尿布后又要顺 手买回自己爱喝的啤酒，因此啤酒和尿布在一起被购买的机会很多。这个举措使尿布和啤酒的销量双双增加，并一直为众商家所津津乐道。"尿布和啤酒"：关联规则的一个非常有名的故事。关联规则的是在一个数据集中找出项与项之间的关系，也被称为购物蓝分析。

      提到关联规则，一个概念很重要?频繁项集：支持度大于等于最小支持度项集。有两个比较重要的度量参数：

1）、支持度
支持度是交易集同时包含X和Y的交易数与总交易数|D|之比。
   support(X?Y)=count(X?Y)/|D|
支持度反映了X、Y同时出现的概率。关联规则的支持度等于频繁集的支持度。
2）、置信度
置信度是指包含X和Y的交易数与包含X的交易数之比。即：
    confidence(X?Y)=support(X?Y)/support(X)
可信度反映了如果交易中包含X，则交易包含Y的概率。一般来说，只有支持度和可信度较高的关联规则才是用户感兴趣的。

     关联规则寻找频繁项集的Apriori算法，Apriori算法是挖掘布尔型关联规则频繁项集的最为经典、最为基本的算法，该算法需要不断寻找候选集，然后剪枝即去掉包含非频繁子集的候选集，时间复杂度由暴力枚举所有子集的指数级别O(n^2) 降为多项式级别，多项式具体系数是底层实现情况而定 。Apriori算法基于这样的事实：算法使用频繁项集性质的先验知识。Apriori使用一种称作逐层搜索的迭代方法，k-项集用于探索(k+1)-项集。首先，找出频繁1-项集的集合。该集合记作L1。L1用于找频繁2-项集的集合L2，而L2用于找L3，如此下去，直到不能找到频繁k-项集。Ariori算法有两个主要步骤：

1、连接

     利用已经找到的Lk，通过两两连接得出Ck+1，注意进行连接的Lk[i]，Lk[j]，必须有k-1个属性值相同，然后另外两个不同的分别分布在Lk[i]，Lk[j]，这样的求出的Ck+1为Lk+1的候选集。

2、剪枝

   候选集Ck+1中的并不都是频繁项集，必须剪枝去掉，越早越好以防止所处理的数据无效项越来越多。只有当子集都是频繁集的候选集才是频繁集，这是剪枝的依据.

  

       

//Apriori.h
<span style="font-family:Verdana;font-size:14px;"><span style="font-family:Verdana;font-size:14px;"></span></span><pre name="code" class="cpp">/**
 * Created by xujin on 2014/12/1.
   All Rights Reserved，but you can use this program.
 */

#ifndef APRIORI_H#define APRIORI_H#include"Transaction.h"#include"TransactionSet.h"class CApriori{private:double m_dMinConfidence;double m_dMinSupport;int m_nSize; int m_nMinConfidence;int m_nMinSupport;int m_nK;CTransactionSet *m_pCTransactionSet;CTransactionSet *m_pCDateCandidateSet;private:void eraseCandidateSet();bool hasInfrequentSubSet(vector<string> &tVecCandidateSet);void aprioriGen(); void findFrequent1ItemSet();bool isFrequentSet(vector<string> &tVecCandidateSet);bool isExist(vector<string> &tVecCandidateSet);public:CApriori(double tMinCon,double tMinSup,int tK,CTransactionSet *tPDaSet);void findFrequentKItemSet();void print();};#endif

//Apriori<span style="font-family:Verdana;">.cpp
<span style="font-family:Verdana;font-size:14px;"><span style="font-family:Verdana;font-size:14px;"></span></span></span><pre name="code" class="cpp">/**
 * Created by xujin on 2014/12/1.
   All Rights Reserved，but you can use this program.
 */

#include"Apriori.h"CApriori::CApriori(double tMinCon,double tMinSup,int tK,CTransactionSet *tPDaSet){this->m_dMinConfidence=tMinCon;this->m_dMinSupport=tMinSup;this->m_nK=tK;this->m_pCTransactionSet = tPDaSet;this->m_nSize = tPDaSet->getSize();this->m_nMinConfidence=this->m_dMinConfidence*this->m_nSize;this->m_nMinSupport=this->m_dMinSupport*this->m_nSize;//cout<<"m_nMinConfidence m_nMinSupport m_nK m_nSize"<<m_nMinConfidence<<" "<<m_nMinSupport<<" "<<m_nK<<" "<<m_nSize<<endl;this->m_pCDateCandidateSet=new CTransactionSet();}bool CApriori::hasInfrequentSubSet(vector<string> &tVecCandidateSet){bool bRet=false;if(this->m_pCDateCandidateSet!=NULL){for(vector<string>::iterator out=tVecCandidateSet.begin();out!=tVecCandidateSet.end();++out){vector<string>tmp;tmp.clear();for(vector<string>::iterator in=tVecCandidateSet.begin();in!=tVecCandidateSet.end();++in){if(*out!=*in){tmp.push_back(*in);}}if(!this->m_pCDateCandidateSet->isContain(tmp)){bRet=true;break;}}}return bRet;}void CApriori::aprioriGen(){vector<string> can;CTransactionSet *CandidateSet=new CTransactionSet();for(size_t i=0;i<(this->m_pCDateCandidateSet->getSize());++i){for(size_t j=0;j<(this->m_pCDateCandidateSet->getSize());++j){if(i!=j){can.clear();if(this->m_pCDateCandidateSet->combineFrequentSet(i,j,can)){if(!this->hasInfrequentSubSet(can)&&!CandidateSet->isExist(can))CandidateSet->addTransaction(CTransaction(can));}}}}eraseCandidateSet();this->m_pCDateCandidateSet=CandidateSet;}void CApriori::eraseCandidateSet(){for(vector<CTransaction>::iterator iter=this->m_pCDateCandidateSet->getVeCTransaction().begin();iter!=this->m_pCDateCandidateSet->getVeCTransaction().end();++iter){iter->getVecItem().clear();}this->m_pCDateCandidateSet->getVeCTransaction().clear();delete this->m_pCDateCandidateSet;this->m_pCDateCandidateSet=NULL;}bool CApriori::isFrequentSet(vector<string> &tVecCandidateSet){int sup=this->m_pCTransactionSet->getSupportCount(tVecCandidateSet);if(sup<m_nMinSupport)return false;return true;}void CApriori::findFrequent1ItemSet(){for(vector<CTransaction>::iterator iter=this->m_pCTransactionSet->getVeCTransaction().begin();iter!=this->m_pCTransactionSet->getVeCTransaction().end();++iter){for(vector<string>::iterator strIter=iter->getVecItem().begin();strIter!=iter->getVecItem().end();++strIter){vector<string> vec1Itemset;vec1Itemset.push_back(*strIter);if(this->isFrequentSet(vec1Itemset)){if(!this->isExist(vec1Itemset)) m_pCDateCandidateSet->addTransaction(CTransaction(vec1Itemset));}}}}void CApriori::findFrequentKItemSet(){this->findFrequent1ItemSet();//this->print();for(int i=2;i<=this->m_nK;++i){this->aprioriGen();// this->print();if(this->m_pCDateCandidateSet->getVeCTransaction().size()==0)return ;//cout<<"*********"<<endl;for(vector<CTransaction>::iterator iter=this->m_pCDateCandidateSet->getVeCTransaction().begin();iter!=(this->m_pCDateCandidateSet->getVeCTransaction().end());){int sup=this->m_pCTransactionSet->getSupportCount(iter->getVecItem());//cout<<"&&&&sup="<<sup<<" m_nMinSupport="<<m_nMinSupport<<endl;if(sup<this->m_nMinSupport){iter=this->m_pCDateCandidateSet->getVeCTransaction().erase(iter);// cout<<"!!!!!!!!!"<<endl;}else ++iter;// cout<<"^^^^&&&&sup="<<sup<<" m_nMinSupport="<<m_nMinSupport<<endl;}// cout<<"&&&&&&"<<endl;}}void CApriori::print(){m_pCDateCandidateSet->print();}bool CApriori::isExist(vector<string> &tVecCandidateSet){ if(this->m_pCDateCandidateSet->isExist(tVecCandidateSet))return true;return false;}

      Apriori算法的主要瓶颈在于不断寻找候选项集，可不可以找到一种不用频繁寻找候选项集的算法呢？而且当待挖掘的数据很大进而需要存储在数据库中时，Apriori算法还有一个无可回避的问题就是每次都要扫描数据库，涉及大量I/O操作，比较耗时（当然可以不用数据库）。           

    由于时间有限，在写博文的过程中参考过一些文献，在此表示感谢；同时鉴于水平原因，你难免有不足之处，欢迎斧正！