apriori算法_apriori算法例题 - CSDN
精华内容
参与话题
  • Apriori算法原理及实现

    千次阅读 2016-10-23 15:37:41
    有这样一个故事:美国的妇女们经常会嘱咐她们的丈夫下班后为孩子买尿布,而丈夫在买完尿布后又要顺 手买回自己爱喝的啤酒,因此啤酒和尿布在一起被购买的机会很多。这个举措使尿布和啤酒的销量双双增加,并一直为众...

    原创作品,出自 “晓风残月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(2^n) 降为多项式级别,多项式具体系数是底层实现情况而定 。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
    /**
     * 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.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操作,比较耗时(当然可以不用数据库)。           




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



    展开全文
  • Apriori算法详解之【一、相关概念和核心步骤】

    万次阅读 多人点赞 2013-06-09 11:07:42
    一、Apriori算法简介: Apriori算法是一种挖掘关联规则的频繁项集算法,其核心思想是通过候选集生成和情节的向下封闭检测两个阶段来挖掘频繁项集。 Apriori(先验的,推测的)算法应用广泛,可用于消费市场价格分析...

        感谢红兰整理的PPT,简单易懂,现在将其中精彩之处整理,与大家分享。

    一、Apriori算法简介:  Apriori算法是一种挖掘关联规则的频繁项集算法,其核心思想是通过候选集生成和情节的向下封闭检测两个阶段来挖掘频繁项集。 Apriori(先验的,推测的)算法应用广泛,可用于消费市场价格分析,猜测顾客的消费习惯;网络安全领域中的入侵检测技术;可用在用于高校管理中,根据挖掘规则可以有效地辅助学校管理部门有针对性的开展贫困助学工作;也可用在移动通信领域中,指导运营商的业务运营和辅助业务提供商的决策制定。

    二、挖掘步骤:

    1.依据支持度找出所有频繁项集(频度)

    2.依据置信度产生关联规则(强度)

    三、基本概念

    对于A->B

    ①支持度:P(A ∩ B),既有A又有B的概率

    ②置信度:

    P(B|A),在A发生的事件中同时发生B的概率 p(AB)/P(A)     例如购物篮分析:牛奶 ⇒ 面包

    例子:[支持度:3%,置信度:40%]

    支持度3%:意味着3%顾客同时购买牛奶和面包

    置信度40%:意味着购买牛奶的顾客40%也购买面包

    ③如果事件A中包含k个元素,那么称这个事件Ak项集事件A满足最小支持度阈值的事件称为频繁k项集。

    ④同时满足最小支持度阈值和最小置信度阈值的规则称为强规则

    四、实现步骤

        Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法Apriori使用一种称作逐层搜索的迭代方法,“K-1项集”用于搜索“K项集”。

    首先,找出频繁“1项集”的集合,该集合记作L1L1用于找频繁“2项集”的集合L2,而L2用于找L3。如此下去,直到不能找到“K项集”。找每个Lk都需要一次数据库扫描。

    核心思想是:连接步和剪枝步。连接步是自连接,原则是保证前k-2项相同,并按照字典顺序连接。剪枝步,是使任一频繁项集的所有非空子集也必须是频繁的。反之,如果某

    个候选的非空子集不是频繁的,那么该候选肯定不是频繁的,从而可以将其从CK中删除。

    简单的讲,1发现频繁项集,过程为(1)扫描(2)计数(3)比较(4)产生频繁项集(5)连接、剪枝,产生候选项集   重复步骤(1~5)直到不能发现更大的频集

    2产生关联规则,过程为:根据前面提到的置信度的定义,关联规则的产生如下:

    1)对于每个频繁项集L,产生L的所有非空子集;

    2)对于L的每个非空子集S,如果

                    PL/PS)≧min_conf

    则输出规则“SàL-S

    注:L-S表示在项集L中除去S子集的项集


      在下一篇文章中将有伪代码实现和例子(Apriori算法详解之【二、伪代码和例子】http://blog.csdn.net/lizhengnanhua/article/details/9061887

    展开全文
  • 数据挖掘十大算法(四):Apriori(关联分析算法

    万次阅读 多人点赞 2019-01-29 10:11:22
    这里主要介绍的是叫做Apriori的‘一个先验’算法,通过该算法我们可以对数据集做关联分析——在大规模的数据中寻找有趣关系的任务,本文主要介绍使用Apriori算法发现数据的(频繁项集、关联规则)。 这些关系可以有...

    终于到了机器学习实战的第十一章了,这也是继K-均值后的第二个无监督学习算法了。同样的该算法也是在一堆数据集中寻找数据之间的某种关联,这里主要介绍的是叫做Apriori‘一个先验’算法,通过该算法我们可以对数据集做关联分析——在大规模的数据中寻找有趣关系的任务,本文主要介绍使用Apriori算法发现数据的(频繁项集、关联规则)。

    这些关系可以有两种形式:频繁项集、关联规则

            频繁项集:经常出现在一块的物品的集合

            关联规则:暗示两种物品之间可能存在很强的关系

    一个具体的例子:

    频繁项集是指那些经常出现在一起的物品,例如上图的{葡萄酒、尿布、豆奶},从上面的数据集中也可以找到尿布->葡萄酒的关联规则,这意味着有人买了尿布,那很有可能他也会购买葡萄酒。那如何定义和表示频繁项集和关联规则呢?这里引入支持度和可信度(置信度)。

    支持度:一个项集的支持度被定义为数据集中包含该项集的记录所占的比例,上图中,豆奶的支持度为4/5,(豆奶、尿布)为3/5。支持度是针对项集来说的,因此可以定义一个最小支持度,只保留最小支持度的项集。

    可信度(置信度):针对如{尿布}->{葡萄酒}这样的关联规则来定义的。计算为 支持度{尿布,葡萄酒}/支持度{尿布},其中{尿布,葡萄酒}的支持度为3/5,{尿布}的支持度为4/5,所以“尿布->葡萄酒”的可行度为3/4=0.75,这意味着尿布的记录中,我们的规则有75%都适用。

    有了可以量化的计算方式,我们却还不能立刻运算,这是因为如果我们直接运算所有的数据,运算量极其的大,很难实现,这里说明一下,假设我们只有 4 种商品:商品0,商品1,商品 2,商品3. 那么如何得可能被一起购买的商品的组合?

    上图显示了物品之间所有可能的组合,从上往下一个集合是 Ø,表示不包含任何物品的空集,物品集合之间的连线表明两个或者更多集合可以组合形成一个更大的集合。我们的目标是找到经常在一起购买的物品集合。这里使用集合的支持度来度量其出现的频率。一个集合出现的支持度是指有多少比例的交易记录包含该集合。例如,对于上图,要计算 0,3 的支持度,直接的想法是遍历每条记录,统计包含有 0 和 3 的记录的数量,使用该数量除以总记录数,就可以得到支持度。而这只是针对单个集合 0,3. 要获得每种可能集合的支持度就需要多次重复上述过程。对于上图,虽然仅有4中物品,也需要遍历数据15次。随着物品数目的增加,遍历次数会急剧增加,对于包含 N 种物品的数据集共有 2^N−1 种项集组合。为了降低计算时间,研究人员发现了 Apriori 原理,可以帮我们减少感兴趣的频繁项集的数目。

    Apriori 的原理:如果某个项集是频繁项集,那么它所有的子集也是频繁的。即如果 {0,1} 是频繁的,那么 {0}, {1} 也一定是频繁的。

    这个原理直观上没有什么用,但是反过来看就有用了,也就是说如果一个项集是非频繁的,那么它的所有超集也是非频繁的。如下图所示:

    频繁项集:

    主要步骤:

        首先会生成所有单个物品的项集列表
        扫描交易记录来查看哪些项集满足最小支持度要求,那些不满足最小支持度的集合会被去掉
        对剩下的集合进行组合以生成包含两个元素的项集
        接下来重新扫描交易记录,去掉不满足最小支持度的项集,重复进行直到所有项集都被去掉

    代码(代码中有详细注释):

    from numpy import *
    
    # 构造数据
    def loadDataSet():
        return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]
    
    # 将所有元素转换为frozenset型字典,存放到列表中
    def createC1(dataSet):
        C1 = []
        for transaction in dataSet:
            for item in transaction:
                if not [item] in C1:
                    C1.append([item])
        C1.sort()
        # 使用frozenset是为了后面可以将这些值作为字典的键
        return list(map(frozenset, C1))  # frozenset一种不可变的集合,set可变集合
    
    # 过滤掉不符合支持度的集合
    # 返回 频繁项集列表retList 所有元素的支持度字典
    def scanD(D, Ck, minSupport):
        ssCnt = {}
        for tid in D:
            for can in Ck:
                if can.issubset(tid):   # 判断can是否是tid的《子集》 (这里使用子集的方式来判断两者的关系)
                    if can not in ssCnt:    # 统计该值在整个记录中满足子集的次数(以字典的形式记录,frozenset为键)
                        ssCnt[can] = 1
                    else:
                        ssCnt[can] += 1
        numItems = float(len(D))
        retList = []        # 重新记录满足条件的数据值(即支持度大于阈值的数据)
        supportData = {}    # 每个数据值的支持度
        for key in ssCnt:
            support = ssCnt[key] / numItems
            if support >= minSupport:
                retList.insert(0, key)
            supportData[key] = support
        return retList, supportData # 排除不符合支持度元素后的元素 每个元素支持度
    
    # 生成所有可以组合的集合
    # 频繁项集列表Lk 项集元素个数k  [frozenset({2, 3}), frozenset({3, 5})] -> [frozenset({2, 3, 5})]
    def aprioriGen(Lk, k):
        retList = []
        lenLk = len(Lk)
        for i in range(lenLk): # 两层循环比较Lk中的每个元素与其它元素
            for j in range(i+1, lenLk):
                L1 = list(Lk[i])[:k-2]  # 将集合转为list后取值
                L2 = list(Lk[j])[:k-2]
                L1.sort(); L2.sort()        # 这里说明一下:该函数每次比较两个list的前k-2个元素,如果相同则求并集得到k个元素的集合
                if L1==L2:
                    retList.append(Lk[i] | Lk[j]) # 求并集
        return retList  # 返回频繁项集列表Ck
    
    # 封装所有步骤的函数
    # 返回 所有满足大于阈值的组合 集合支持度列表
    def apriori(dataSet, minSupport = 0.5):
        D = list(map(set, dataSet)) # 转换列表记录为字典  [{1, 3, 4}, {2, 3, 5}, {1, 2, 3, 5}, {2, 5}]
        C1 = createC1(dataSet)      # 将每个元素转会为frozenset字典    [frozenset({1}), frozenset({2}), frozenset({3}), frozenset({4}), frozenset({5})]
        L1, supportData = scanD(D, C1, minSupport)  # 过滤数据
        L = [L1]
        k = 2
        while (len(L[k-2]) > 0):    # 若仍有满足支持度的集合则继续做关联分析
            Ck = aprioriGen(L[k-2], k)  # Ck候选频繁项集
            Lk, supK = scanD(D, Ck, minSupport) # Lk频繁项集
            supportData.update(supK)    # 更新字典(把新出现的集合:支持度加入到supportData中)
            L.append(Lk)
            k += 1  # 每次新组合的元素都只增加了一个,所以k也+1(k表示元素个数)
        return L, supportData
    
    dataSet = loadDataSet()
    L,suppData = apriori(dataSet)
    print(L)
    print(suppData)

    返回频繁项集与支持度

    上面代码获取数据的频繁项集,下面通过其他函数来获得关联规则。

    关联规则:

    # 获取关联规则的封装函数
    def generateRules(L, supportData, minConf=0.7):  # supportData 是一个字典
        bigRuleList = []
        for i in range(1, len(L)):  # 从为2个元素的集合开始
            for freqSet in L[i]:
                # 只包含单个元素的集合列表
                H1 = [frozenset([item]) for item in freqSet]    # frozenset({2, 3}) 转换为 [frozenset({2}), frozenset({3})]
                # 如果集合元素大于2个,则需要处理才能获得规则
                if (i > 1):
                    rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConf) # 集合元素 集合拆分后的列表 。。。
                else:
                    calcConf(freqSet, H1, supportData, bigRuleList, minConf)
        return bigRuleList
    
    # 对规则进行评估 获得满足最小可信度的关联规则
    def calcConf(freqSet, H, supportData, brl, minConf=0.7):
        prunedH = []  # 创建一个新的列表去返回
        for conseq in H:
            conf = supportData[freqSet]/supportData[freqSet-conseq]  # 计算置信度
            if conf >= minConf:
                print(freqSet-conseq,'-->',conseq,'conf:',conf)
                brl.append((freqSet-conseq, conseq, conf))
                prunedH.append(conseq)
        return prunedH
    
    # 生成候选规则集合
    def rulesFromConseq(freqSet, H, supportData, brl, minConf=0.7):
        m = len(H[0])
        if (len(freqSet) > (m + 1)): # 尝试进一步合并
            Hmp1 = aprioriGen(H, m+1) # 将单个集合元素两两合并
            Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)
            if (len(Hmp1) > 1):    #need at least two sets to merge
                rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf)
    
    dataSet = loadDataSet()
    L,suppData = apriori(dataSet,minSupport=0.5)
    rules = generateRules(L,suppData,minConf=0.7)
    # rules = generateRules(L,suppData,minConf=0.5)
    print(rules)

    返回关联规则:

    上面的函数稍微有点复杂,因为使用的数据结构有点多,可能会搞混,所以下面说明一下函数意义。(由于我个人叙述可能不太清楚,所以这里引用作者的原话我觉得更好理解一点,稍微有点详细):

    以上便是引用作者对这三个函数的详细描述,在函数中的具体代码,我也有相关的注释,慢慢来应该能够理解的。

    下面对一个毒蘑菇的例子进行运算,检查一下在实际数据中的反应:

    第一个特征表示有毒或者可以使用。如果有毒则为2,可以食用为1。下一个特征蘑菇形状,有3-8六种可能,下面我们找出毒蘑菇中存在的公共特征:

    mushDatSet = [line.split() for line in open('mushroom.dat').readlines()]
    L,suppData = apriori(mushDatSet,minSupport=0.3)
    print(L)
    for item in L[1]:   # 只查看两个元素的集合
        if(item.intersection('2')): # intersection交集(选出毒蘑菇)
            print(item)

    输出了频繁项集和与毒蘑菇相关的特征:

    以上为Apriori算法构建模型的全部内容,该算法不仅适用于零售行业,同样适用于相同技术的其他行业,如网站流量分析以及医药行业等。

     

    参考书籍:《机器学习实战》

    展开全文
  • Apriori算法的原理和流程

    万次阅读 多人点赞 2020-05-04 17:30:06
    Apriori算法——关联规则挖掘 前言: 首先,关联规则挖掘的目的是找出事物之间存在的隐藏的关系,比如经典的案例啤酒和尿布的的故事,用我们人的思维来思考的话,男性在买尿布的时候会买几瓶啤酒,这二者并没有...

    Apriori算法——关联规则挖掘

    前言:

    首先,关联规则挖掘的目的是找出事物之间存在的隐藏的关系,比如经典的案例啤酒和尿布的的故事,用我们人的思维来思考的话,男性在买尿布的时候会买几瓶啤酒,这二者并没有什么因果关系。然而通过对海量数据进行关联分析,却能够发现这个有趣的知识,在超市调整货架后,明显的提升了超市啤酒尿布的销量。

    基本概念:

    1.关联规则的表示:   泡面 => 火腿 [support=2%;confidence=70%] 。这个就是关联规则的表示方法,其中支持度(support)和 (置信度)confidence是两个衡量这个规则是否有趣的度量标准。

    2.支持度:按照上面的例子来讲,已知了支持度是2%,意味着所有事务的2%显示同时买了泡面和火腿。如果这个有疑惑大可不必着急,这个在还会在后续的例子里面具体阐述。

    3.置信度:例如上述的置信度为70%,意味着所有买泡面的顾客,70%的顾客都买了火腿。

    4.项集:项集就是项的集合,例如:{矿泉水,泡面,火腿}  这是一个3项集,项集的出现频度是包含项集的事务数,把它记作支持度计数,通俗的来说,假设有三个顾客分别买了{矿泉水,泡面,火腿}、{矿泉水,泡面,火腿、牛栏山}、{矿泉水,火腿}。那么这个3项集的支持度计数就是2。

    5.频繁项集:如果我们预定义的支持度计数是2,也就是此时的支持度计数阈值为2,而上述的3项集的支持度计数是2,所以该3项集是频繁项集。

    6.置信度计算公式:confidence( 泡面 => 火腿 ) = P(火腿  |  泡面) = {\color{Green} }\frac{support(noodles \bigcup ham)}{support(noodles)}   

                                                                                                                     =   \frac{supportcount(noodles \cup ham)}{supportcount(noodles)}

    所以想求置信度,核心是求频繁项集。关联规则挖掘的步骤分两步:1.找所有的频繁项集。2.根据频繁项集生产强关联规则

    Apriori算法举例:

    接下来用一个例子用apriori算法来走一遍关联规则的流程(本例子预定义的支持度为2),下图是事物数据,9个顾客分别买了不同的商品列表(我们假定I1表示泡面,I2表示矿泉水,I3表示牛栏山,I4表示雪碧,I5表示火腿)。

    首先我们要做的是第一次迭代,扫描所有的事物,对每个项进行计数得到候选项集,得到如下图所示的结果,记为C1

    此时,我们要对支持度计数和支持度的阈值进行比较,剔除小于支持度阈值的项集,显而易见,在本例中C1的项集都达到了阈值。我们便可以得出频繁1项集记作L1

    接下来我们要进行第二次迭代,目的是得出频繁2项集,所以要使用连接来产生候选项集2项集。L1 \bowtie L1 得出

    连接这一步,我们把它叫做连接步,连接得到C2后,接下来做的是剪枝步,就是剪掉项集中包含不频繁项的项集,在本例中1项集全部都是频繁项集,例如{I1,I2}中没有不频繁项集,此项集不剪,{I1,I3}中没有不频繁项集,同理不剪,以此类推。所以C2中所有的项集都不需要剪掉。到此连接步、剪枝步全部完成。(这里值得注意的是剪枝是必须的一步,不能省略)最后再计一下数得出最终的C2。如下图所示。

    将支持度计数小于阈值2的全部剔除,得出频繁2项集L2,如下图所示。


    现在开始进行第三次迭代,L2 \bowtie L2 得出候选项集C3,如下图所示。

    在这一步同样是经过了连接步剪枝步。L2自连接得到

    然而除了之外。中都含有不频繁项集,第一个{I3,I5}不是L2的元素所以要剪枝,后面以此类推,最终得到上图的C3。(再重视一下,这个剪枝不能省略)。最后记一下数,得出最终的候选项集C3

    得到候选项集C3后与支持度阈值比较,得出频繁3项集L3。

    现在继续第四次迭代L3 自连接得到  {I1,I2,I3,I5} ,接下来剪枝,因为这个项集中{I2,I3,I5}不属于L3,所以剪掉,C4为空了,所以算法到此结束,现在得出了所有的频繁项集

    到此为止,我们做完了第一步:找出所有的频繁项集。接下来要做的便是输出强关联规则

    现在我们拿X = {I1,I2,I5}为例,输出关联规则。X的非空子集为{I1,I2}、{I1,I5}、{I2,I5}、{I1}、{I2}、{I5}。所以组合一下关联规则如下:

    置信度我们根据上文提到的公式来算,拿第一个{I1,I2} => I5为例。confidence = P(I5  |   {I1,I2})

                                                                                                             =  support_count({I2 , I1, I5}) /   support_count({I1,I2})

    通过查找L3,{I1,I2,I5}的支持度计数为2,通过查L2,{I1,I2}的支持度计数为4。即最终可以计算出confidence = \frac{2}{4} =  50%。剩下的以此类推,假定我们预定义70%的置信度。在这些规则中,我们可以输出强关联规则的只有三个。即三个100%置信度的规则。那么我们可以得到买泡面和火腿的一定会买矿泉水,买矿泉水和火腿的一定会买泡面,买火腿的一定会买泡面和矿泉水这三个关联规则。

    算法评价:

    到此为止,用apriori算法实现关联规则挖掘的流程全部结束,可以看出的是,apriori算法要生成大量的候选项集,每生成频繁项集都要生成候选项集。其次要一直迭代重复的扫描事物数据来计算支持度。所以带来的问题很明显,这会导致效率会比较低下。所以apriori算法也有其他的变形优化,这个我们之后再谈。

    参考:

    本篇文章的例子出自韩家炜教授主编的《数据挖掘概念与技术》(第三版)的第六章。

    展开全文
  • Apriori算法详解

    千次阅读 2019-09-30 17:09:02
    Apriori算法总结 一、背景 关联规则学习(Association rule learning)是一种在大型数据库中发现变量之间的有趣性关系的方法。它的目的是利用一些有趣性的量度来识别数据库中发现的强规则。 关联分析是一种在大...
  • Apriori算法

    万次阅读 多人点赞 2018-09-17 12:04:47
    学习Apriori算法首先要了解几个概念:项集、支持度、置信度、最小支持度、最小置信度、频繁项集。 项集:顾名思义,即项的集合。eg:牛奶、面包组成一个集合{牛奶、面包},其中牛奶和面包为项,{牛奶、面包}为项集...
  • python实现Apriori算法

    千次阅读 2019-04-12 11:06:41
    Apriori算法正是来解决这一问题。 物品之间的关系一般可以有两种形式:频繁项集和关联规则。 频繁项集:数据集中经常出现在一块的物品的集合。 关联规则:两种物品之间可能存在很强的关系。 ...
  • 数据挖掘--Apriori算法(例题)

    万次阅读 2018-12-01 23:43:31
    Apriori算法是关联规则挖掘的代表性算法,十大数据挖掘算法之一,可见其重要性。它的主要作用是发现事物之间的内在联系。 Apriori算法的基本思想是通过对数据的多次扫描来计算项集的支持度,发现所有的频繁项集从而...
  • Apriori算法和FP-growth算法比较

    万次阅读 2018-04-13 19:52:59
    关联分析可以用于回答“哪些商品经常被同时购买?”之类的问题关联分析是在大规模数据集中寻找有趣关系的...可信度或者是置信度是针对关联规则来定义的,我们的规则对其中多少的记录都适用Apriori算法是发现频繁项...
  • Apriori算法详解之【二、伪代码和例子】

    万次阅读 多人点赞 2013-06-09 11:05:39
    上一篇文章中对Apriori算法进行了简单的描述(Apriori算法详解之【一、相关概念和核心步骤】http://blog.csdn.net/lizhengnanhua/article/details/9061755),现在用伪代码实现,及对经典例子进行描述(红兰PPT上之...
  • Apriori算法实例

    万次阅读 2017-12-19 14:51:41
    Apriori算法的一个实例
  • Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里,所有支持度大于最小支持度的项集称为频繁项集,...
  • Apriori中的hash tree

    万次阅读 2014-02-11 13:07:59
    总算把hash tree算法弄懂了,不敢独乐,特来分享 hash tree(哈希树),是由tree和hash table结合,旨在优化hash table冲突解决方案的一种数据结构。 在链式hash table中,若关键字发生冲突,则创建单个新节点链到冲突...
  • Apriori算法总结

    万次阅读 2016-06-14 21:34:57
    Apriori algorithm是关联规则里一项基本算法。是由Rakesh Agrawal和Ramakrishnan Srikant两位博士在1994年提出的关联规则挖掘算法。关联规则的目的就是在一个数据集中找出项与项之间的关系,也被称为购物蓝分析 ...
  • 一、概述本篇博文主要阐述数据挖掘相关的关联规则挖掘的算法(Apriori算法)。主要介绍关联规则的基本概念、Apriori算法原理和Apriori算法实例,文章末尾处附加Apriori算法源程序。二、关联规则挖掘的基本概念关联...
  • Apriori算法介绍及实现代码

    千次阅读 2018-07-19 15:07:38
    引言:什么是数据挖掘  随着大数据时代的到来我们生活中的方方面面都受到了数据挖掘的影响,比如你在淘宝上买了一件商品,当你下次登录的时候在淘宝的界面上会出现各种与你曾经购物信息相关的商品。...
  • 关于apriori算法中置信度、支持度怎么理解的问题

    万次阅读 多人点赞 2020-10-15 11:30:17
    比如说啤酒和尿布的问题:TID是transaction ID 即交易编号,说白了就是有五个人在超市买了这样的东西(Iteams),现在我们统计一下,大家买的东西之间有没有什么规律,比如买面包的是不是很可能同时买牛奶这样的规律...
  • 机器学习之Apriori算法

    千次阅读 2019-01-09 00:37:44
    1.Apriori算法简介 Apriori算法是常用于挖掘出数据关联规则的算法,能够发现事物数据库中频繁出现的数据集,这些联系构成的规则可帮助用户找出某些行为特征,以便进行企业决策。例如,某食品商店希望发现顾客的购买...
  • Apriori算法以及MS-Apriori算法均采用逐级搜索的方法来生成k阶频繁项目集,k阶频繁项目集仅由k-1阶频繁项目集两两合并而来。我要说明的是:为什么k-1阶频繁项目集两两合并的结果就一定是k阶频繁项目集的超集(算法...
  • Apriori算法,MATLAB代码实现

    万次阅读 热门讨论 2017-06-19 16:28:59
    Apriori算法简介:想必大家都知道apriori算法的原理吧,最著名的关联规则发现方法R.Agrawal提出的Apriori算法。 1 Apriori 算法的基本思想 2 Apriori算法的基本思想是通过对数据库的多次扫描来计算项集的支持度,...
1 2 3 4 5 ... 20
收藏数 9,562
精华内容 3,824
关键字:

apriori算法