精华内容
下载资源
问答
  • 资源中包含apriori关联分析算法Python代码,python的版本为3.6,使用pycharm平台运行即可。
  • Python --深入浅出Apriori关联分析算法(一) 这次呢,我们会在上次的基础上,讲讲如何分析物品的关联规则得出关联结果,以及给出用apyori这个运行得出关联结果的代码。 一. 基础知识 上次我们介绍了几个关联分析...

    上一篇我们讲了关联分析的几个概念,支持度,置信度,提升度。以及如何利用Apriori算法高效地根据物品的支持度找出所有物品的频繁项集。

    这次呢,我们会在上次的基础上,讲讲如何分析物品的关联规则得出关联结果,以及给出用apyori这个库运行得出关联结果的代码。

    一. 基础知识

    上次我们介绍了几个关联分析的概念,支持度,置信度,提升度。这次我们重点回顾一下置信度和提升度:

    置信度(Confidence):置信度是指如果购买物品A,有较大可能购买物品B。计算方式是这样:

    置信度( A -> B) = (包含物品A和B的记录数量) / (包含 A 的记录数量)

    举例:我们已经知道,(牛奶,鸡蛋)一起购买的次数是两次,鸡蛋的购买次数是4次。那么置信度Confidence(牛奶->鸡蛋)的计算方式是Confidence(牛奶->鸡蛋)=2 / 4。
    提升度(Lift):提升度指当销售一个物品时,另一个物品销售率会增加多少。计算方式是:

    提升度( A -> B) = 置信度( A -> B) / (支持度 A)

    举例:上面我们计算了牛奶和鸡蛋的置信度Confidence(牛奶->鸡蛋)=2/4。牛奶的支持度Support(牛奶)=3 / 5,那么我们就能计算牛奶和鸡蛋的支持度Lift(牛奶->鸡蛋)=0.83

    当提升度(A->B)的值大于1的时候,说明物品A卖得越多,B也会卖得越多。而提升度等于1则意味着产品A和B之间没有关联。最后,提升度小于1那么意味着购买A反而会减少B的销量

    举个例子,有了这个指标,你就能看出卖越多的汉堡就会卖越多的番茄酱。但卖越多的沐浴露,则可能香皂的销量会下降。

    二. 关联规则

    我们前面已经用Apriori得到频繁项集了。那么我们就可以在频繁项集的基础上,找到这里面的关联规则。而计算关联规则所用到的,就是我们上面所说的置信度和提升度

    这里有一点要注意,当我们发现置信度(A->B)很高的时候,反过来的值置信度(B->A)不一定很高。

    一个物品的关联结果是非常多的。但好在,我们上一节学习了Apriori思想。运用在置信度上也是合适的:

    如果一个关联结果的置信度低,那么它的所有超集的置信度也低

    这样一来,我们就能节省很多的计算量。

    三. Apriori关联规则实战

    我们还是用mlxtend库,根据上一篇找到的频繁项集,计算出它们的关联规则。在此之前,还是先介绍一下相应API的参数。

    association_rules(df, metric="confidence",
                          min_threshold=0.8,
                          support_only=False):
    
    参数介绍:
    - df:这个不用说,就是 Apriori 计算后的频繁项集。
    - metric:可选值['support','confidence','lift','leverage','conviction']。
    里面比较常用的就是置信度和支持度。这个参数和下面的min_threshold参数配合使用。
    - min_threshold:参数类型是浮点型,根据 metric 不同可选值有不同的范围,
        metric = 'support'  => 取值范围 [0,1]
        metric = 'confidence'  => 取值范围 [0,1]
        metric = 'lift'  => 取值范围 [0, inf]
    support_only:默认是 False。仅计算有支持度的项集,若缺失支持度则用 NaNs 填充。
    

    完整代码如下:

    import pandas as pd
    from mlxtend.preprocessing import TransactionEncoder
    from mlxtend.frequent_patterns import apriori
    
    #设置数据集
    dataset = [['牛奶','洋葱','肉豆蔻','芸豆','鸡蛋','酸奶'],
            ['莳萝','洋葱','肉豆蔻','芸豆','鸡蛋','酸奶'],
            ['牛奶','苹果','芸豆','鸡蛋'],
            ['牛奶','独角兽','玉米','芸豆','酸奶'],
            ['玉米','洋葱','洋葱','芸豆','冰淇淋','鸡蛋']]
    		
    te = TransactionEncoder()
    #进行 one-hot 编码
    te_ary = te.fit(records).transform(records)
    df = pd.DataFrame(te_ary, columns=te.columns_)
    #利用 Apriori 找出频繁项集
    freq = apriori(df, min_support=0.05, use_colnames=True)
    
    #导入关联规则包
    from mlxtend.frequent_patterns import association_rules
    #计算关联规则
    result = association_rules(freq, metric="confidence", min_threshold=0.6)
    
    

    这里我们根据置信度来计算,找出置信度大于0.6的关联规则。

    计算结果如下:

       antecedents      consequents        antecedent support              consequent support       support           confidence      lift       leverage            conviction 
    0         (洋葱)        (芸豆)                    0.6                         1.0                0.6                 1.00          1.00          0.00                  inf   
    1         (芸豆)        (洋葱)                    1.0                         0.6                0.6                 0.60          1.00          0.00             1.000000   
    2         (洋葱)        (鸡蛋)                    0.6                         0.8                0.6                 1.00          1.25          0.12                  inf   
    3         (鸡蛋)        (洋葱)                    0.8                         0.6                0.6                 0.75          1.25          0.12             1.600000   
    4         (芸豆)        (牛奶)                    1.0                         0.6                0.6                 0.60          1.00          0.00             1.000000   
    5         (牛奶)        (芸豆)                    0.6                         1.0                0.6                 1.00          1.00          0.00                  inf   
    6         (酸奶)        (芸豆)                    0.6                         1.0                0.6                 1.00          1.00          0.00                  inf   
    7         (芸豆)        (酸奶)                    1.0                         0.6                0.6                 0.60          1.00          0.00             1.000000   
    8         (芸豆)        (鸡蛋)                    1.0                         0.8                0.8                 0.80          1.00          0.00             1.000000   
    9         (鸡蛋)        (芸豆)                    0.8                         1.0                0.8                 1.00          1.00          0.00                  inf   
    10    (洋葱, 芸豆)        (鸡蛋)                  0.6                      	0.8         	    0.6                 1.00         1.25           0.12                 inf  
    11    (洋葱, 鸡蛋)        (芸豆)                  0.6                      	1.0         	    0.6                 1.00         1.00           0.00                 inf  
    12    (鸡蛋, 芸豆)        (洋葱)                  0.8                      	0.6         	    0.6                 0.75         1.25           0.12            1.600000  
    13        (洋葱)    (鸡蛋, 芸豆)                  0.6                      	0.8         	    0.6                 1.00         1.25           0.12                 inf  
    14        (芸豆)    (洋葱, 鸡蛋)                  1.0                      	0.6         	    0.6                 0.60         1.00           0.00            1.000000  
    15        (鸡蛋)    (洋葱, 芸豆)                  0.8                      	0.6         	    0.6                 0.75         1.25           0.12            1.600000  
    

    我们可以发现,除了置信度(confidence),提升度(lift)外,还有两个指标,leverage和conviction。这两个用得比较少,和置信度,提升度也有些类似,就不展开说了。

    既然返回的结果是Dataframe,那么就可以很方便得用pandas的排序方法找出置信度或提升度高的物品组合,方法如下:

    DataFrame.sort_values

    比如上面例子中要找出最大的置信度,用

    result.sort_values(by = ‘confidence’,ascending=False,axis=1)

    上面例子中我们可以发现,{洋葱 -> 鸡蛋,芸豆} 的置信度是 1.00 ,而它们的提升度是 1.25 。这说明买了洋葱的人很可能会再购买 1.25 份的 {鸡蛋,芸豆} 。所以可以让它们放到一起出售。

    OK,相信通过这个前面的介绍和这次的这个例子,已经能够明白Apriori算法的原理以及如何使用它。当然Apriori只能算是关联挖掘算法中比较基础的一个,还有其他的关联挖掘算法,比如FP-growth,以后有机会再介绍吧。

    对了,我从网上找了个关联分析的数据和大概针对这个数据写了个小的demo代码。
    关联分析数据

    数据是超市的购物清单,大概有7500条,足够我们来运算分析了。

    我把数据和我写的一点点demo代码放在我的公众号中了,关联公众号:哈尔的数据城堡,回复“apriori”(不需要双引号),就能获得下载链接了。

    以上~

    展开全文
  • 电商,物流,存储,仓储,商品关联分析python,Apriori
  • 关联分析的Apriori算法 in Python

    千次阅读 2016-02-22 20:37:14
    关联分析的Apriori算法 in Python

    前面介绍的机器学习算法均为监督学习方法,即“对于输入数据X能预测变量Y”,下面学习几个非监督学习算法,即回答“从数据X中能发现什么”问题,这里需要回答的X方面的问题可能是“构成X的最佳5个数据簇有哪些”或者“X中哪三个特征最频繁地一起出现”等。简单的聚类方法(包括k均值聚类)就不赘述了,直接介绍两个关系分析算法:Apriori算法,FP-growth算法。


    从大规模数据中寻找物品间的隐含关系被称为关联分析,或者关联规则学习。这些关系可以有两种形式:频繁项集,关联规则。

    显然,暴力搜索法是不可行的,下面介绍一种高效的算法 —— Apriori算法。


    1、Apriori原理

    Apriori原理是说如果某个相集是频繁的,那么它的所有子集也是频繁的。

    关键是其逆否命题:如果一个相集是非频繁集,那么它的所有超集也是非频繁的。

    显然,此原理可以避免相集数目的指数增长,减少在数据集上进行检查的集合的数目。


    2、使用Apriori发现频繁集

    算法流程可以概括为

    根据数据集构建初始集合C_1
    当集合中项的个数k大于0时:
    	对C_k以最小支持度进行过滤,生成频繁项集集合L_k
    	对L_k中元素相互组合,生成候选项集集合C_k+1

    我们在来看步骤“对L_k中元素相互组合,生成候选项集集合C_k+1”,假设共有M个长度为k的项集,机器学习实战中采用下述方法将项集两两组合:满足两两中前k-1个元素相同,只后一个元素要求前一条记录的商品名称小于后一条记录的商品名称,这样是为了避免重复组合,求它们的并集得到长度为k+1的准频繁项集。可见,这个过程最多共有C(M,2)中组合,这对于M很大的情况显然并不理想。其实,可以采用Apriori原理先对L_k进行预处理,再进行元素组合得到C_k+1。

    具体说来,对L_k中的每个项集,观察该项集的任意k-1长度的子项集是否包含在L_k-1中,如果没有,说明该子项集为非频繁项集,那么根据Apriori原理,其超项集必然也不是频繁项集,因此,L-k中的该项集应该被删除。

    可见Apriori算法有个最大的问题就是要产生大量准频繁项集或者说候选集,效率不高,并且要多次扫描数据库,在后面的FP-growth算法将避免了这两个个问题。


    3、从频繁集挖掘关联规则

    前面给出了频繁项集的量化定义,即它满足最小支持度要求。对于关联规则,这种量化指标成为可信度。

    Apriori原理应用到关联规则的结论是:假设规则{0,1,2}到{3}不满足最小可信度要求,那么任何前件(左部)为{0,1,2,}的自己的规则都不会满足最小可信度要求。


    4、总结

    可以看到,Apriori算法在每次增加频繁集项的大小时,都要重新扫描整个数据集,当数据集很大时,这会显著降低频繁项集发现的速度。后面较少的FP-growth算法则只需要对数据集进行两次遍历,能够显著加快频繁项集的速度


    5、Python实现

    ###	helper functions
    def loadDataSet():
    	return [[1,3,4], [2,3,5], [1,2,3,5], [2,5]]
    
    # create the initial itemset C1 	
    def createC1(dataSet):
    	C1 = []
    	for tran in dataSet:
    		for item in tran:
    			if not [item] in C1:
    				C1.append([item])
    	C1.sort()
    	return map(frozenset, C1)
    	
    # scan the dataSet to filter C_k into L_k
    def scanD(D, Ck, minSupport):
    	ssCnt = {}
    	for tran in D:
    		for can in Ck:
    			if can.issubset(tran):
    				if not ssCnt.has_key(can):
    					ssCnt[can] = 1
    				else:
    					ssCnt[can] += 1
    	numItems = float(len(D))
    	# L_k
    	retList = []
    	# a dict combine C_k with its support
    	supportData = {}
    	for key in ssCnt:
    		support = ssCnt[key]/numItems
    		if support >= minSupport:
    			retList.insert(0,key)
    		supportData[key] = support
    	return retList, supportData
    
    
    ### Apriori algorithm to find the frequent item sets
    # create the C_k
    # actually the Lk in function denotes L_k-1
    def aprioriGen(Lk,k):
    	retList = []
    	lenLk = len(Lk)
    	for ii in range(lenLk):
    		for jj in range(ii+1, lenLk):
    			L1 = list(Lk[ii])[:k-2]
    			L1.sort()
    			L2 = list(Lk[jj])[:k-2]
    			L2.sort()
    			if L1 == L2 :
    				retList.append(Lk[ii] | Lk[jj]) 
    	return retList
    
    def apriori(dataSet, minSupport=0.5):
    	C1 = createC1(dataSet)
    	D = map(set, dataSet)
    	L1,supportData = scanD(D, C1, minSupport)
    	L = [L1]
    	k = 2
    	while (len(L[k-2]) > 0):
    		Ck = aprioriGen(L[k-2], k)
    		Lk, supK = scanD(D, Ck, minSupport)
    		supportData.update(supK)
    		L.append(Lk)
    		k += 1
    	return L, supportData
    
    
    ### Explore the association rules
    


    展开全文
  • 1:关联分析 2:Apriori算法和FP-growth算法原理 3:使用Apriori算法发现频繁项集 4:使用FP-growth高效发现频繁项集 5:实例:从新闻站点点击流中挖掘新闻报道 以下程序用到的源代码下载地址:GitHub 一:关联...

    =====================================================================

    《机器学习实战》系列博客是博主阅读《机器学习实战》这本书的笔记也包含一些其他python实现的机器学习算法
                                              算法实现均采用python

    github 源码同步:https://github.com/Thinkgamer/Machine-Learning-With-Python

    =====================================================================

    1:关联分析

    2:Apriori算法和FP-growth算法原理

    3:使用Apriori算法发现频繁项集

    4:使用FP-growth高效发现频繁项集

    5:实例:从新闻站点点击流中挖掘新闻报道

    以下程序用到的源代码下载地址:GitHub点击查看


    一:关联分析

    1:相关概念

    关联分析(association analysis):从大规模数据集中寻找商品的隐含关系

    项集 (itemset):包含0个或者多个项的集合称为项集

    频繁项集:那些经常一起出现的物品集合

    支持度计数(support count):一个项集出现的次数也就是整个交易数据集中包含该项集的事物数


    关联规则是形如A->B的表达式,规则A->B的度量包括支持度和置信度

    项集支持度:一个项集出现的次数与数据集所有事物数的百分比称为项集的支持度

    eg:support(A->B)=support_count(A并B) / N

    项集置信度(confidence):数据集中同时包含A,B的百分比

    eg:confidence(A->B) = support_count(A并B) / support_count(A)


    2:关联分析一些应用

    (1):购物篮分析,通过查看那些商品经常在一起出售,可以帮助商店了解用户的购物行为,这种从数据的海洋中抽取只是可以用于商品定价、市场促销、存货管理等环节

    (2):在Twitter源中发现一些公共词。对于给定的搜索词,发现推文中频繁出现的单词集合

    (3):从新闻网站点击流中挖掘新闻流行趋势,挖掘哪些新闻广泛被用户浏览到

    (4):搜索引擎推荐,在用户输入查询时推荐同时相关的查询词项

    (5):发现毒蘑菇的相似特征。这里只对包含某个特征元素(有毒素)的项集感兴趣,从中寻找毒蘑菇中的一些公共特征,利用这些特征来避免迟到哪些有毒的蘑菇


    3:样例(下文分析所依据的样本,交易数据表)

    交易号码

    商品

    100

    Cola,Egg,Ham

    200

    Cola,Diaper,Beer

    300

    Cola,Diaper,Beer,Ham

    400

    Diaper,Beer


    二:Apriori算法和FP-growth算法原理

    1:Apriori算法原理

    找出所有可能是频繁项集的项集,即候选项集,然后根据最小支持度计数删选出频繁项集,最简单的办法是穷举法,即把每个项集都作为候选项集,统计他在数据集中出现的次数,如果出现次数大于最小支持度计数,则为频繁项集。

                     
                                             所有的可能的项集(E:Egg     C:Cola     D:Diaper    B:Beer     H:Ham)

    频繁项集的发现过程如下(假定给定的最小支持度为2):
                            
                                                                         频繁项集的发现过程

    经过剪枝后的图为(红色圆圈内即为剪枝去掉的部分):

                                 剪枝后的候选集为(E:Egg     C:Cola    D:Diaper    B:Beer    H:Ham)

    那么CD,CB,CH,DB,DH,BH,DBH即为所求的候选集

    2:FP-growth算法原理


    FP-growth算法不同于Apriori算法生成候选项集再检查是否频繁的”产生-测试“方法,而是使用一种称为频繁模式树(FP-Tree,PF代表频繁模式,Frequent Pattern)菜单紧凑数据结构组织数据,并直接从该结构中提取频繁项集,下面针对

    交易号码

    商品

    100

    Cola,Egg,Ham

    200

    Cola,Diaper,Beer

    300

    Cola,Diaper,Beer,Ham

    400

    Diaper,Beer

    FP-growth算法分为两个过程,一是根据原始数据构造FP-Tree,二是在FP-Tree上挖掘频繁模式
    做出FP-Tree,频繁模式树的挖掘形成过程
    首先扫描一遍数据集,找出频繁项的列表L,按照他们的支持度计数递减排序,即 L = <(Cola:3),(Diaper:3),(Beer:3),(Ham:2)>
    再次扫描数据库,利用每个事物中的频繁项构造FP-Tree,FP-Tree的根节点为null,处理每个事物时按照L中的顺序将事物中出现的频繁项添加到中的一个分支
    例如,第一个事物创建一个分支<(Cola:1),(Ham:1)>,第二个事物中包含频繁项排序后为<(Cola,Diaper,Beer)>,与树中的分支共享前缀(Cola),因此将树中的节点Cola的计数分别加一,在Cola节点创建分支<(Diaper:1),(Beer:1)>,依次类推,将数据集中的事物都添加到FP-Tree中,为便于遍历树,创建一个头节点表,使得每个项通过一个节点链指向他在树中的出现,相同的链在一个链表中,构造好的FP-Tree树如下图:
                                    
                     
                                                                         根据上表构造的FP-Tree
    在FP-Tree上挖掘频繁模式:
    挖掘FP-Tree采用自低向上的迭代模式,首先查找以”Ham“为后缀的频繁项集,然后依次是”Beer“,”Diaper“,”Cola“
    查找以”Ham“为后缀的频繁项集,首先在FP-Tree中找出所有包含”Ham“的记录,利用头节点表和树节点的链接,找出包含”Ham“的两个分支,<Cola:3,Ham:1>和<(Cola:3,Diaper:2,Beer:1,Ham:1)>,说明在该FP-Tree所代表的数据集中记录(Cola,Ham)和(Cola,Diaper,Beer,Ham)各出现了一次,利用这两个分支所代表的记录构造”Ham“的条件模式基。条件模式基可以看作是一个“子数据集”,由FP-Tree中与后缀模式一起出现的前缀路径组成,Ham作为后缀模式时,”Ham“的两个前缀路径{(Cola:1),(Cola Diaper Beer:1)}构成了”Ham“的条件模式基。利用”Ham“的条件模式基构造FP-TRee,即“Ham”的条件FP树。“Ham ”的条件模式基中,Cola出现了2次,Diaper,Beer只出现了1次,所以Diaper,Beer是非频繁项,不包含在“Ham”的条件模式树中,“Ham”的条件模式树只有一个分支<Cola:2>,得到条件频繁项集{Cola:2},条件频繁项集与后缀模式“Ham“合并,得到频繁项集{Cola Ham :2}
    同理查找”Beer“为后缀的频繁项集,得到{ {Diaper  Beer :3} ,  {Cola  Diaper  Beer:2}, {Cola  Beer:2}  }
    查找”Diaper“为结尾的频繁项集,得到 {Cola Diaper :2}


    三:使用Apriori算法发现频繁项集和挖掘相关规则

    1:发现频繁项集

    Apriori算法是发现频繁项集的一种方法。Apriori算法的两个输入参数分别是最小支持度和数据集。该算法首先会生成所有单个元素的项集列表。接着扫描数据集来查看哪些项集满足最小支持度要求,那些不满足最小支持度的集合会被去掉。然后,对剩下来的集合进行组合以生成包含两个元素的项集。接下来,再重新扫描交易记录,去掉不满足最小支持度的项集。该过程重复进行直到所有项集都被去掉,创建 Apriori.py文件,加入以下代码
    #-*-coding:utf-8-*-
    '''
    Created on 2016年5月8日

    @author: Gamer Think
    '''
    from pydoc import apropos

    #=========================     准备函数 (下)      ==========================================
    #加载数据集
    def loadDataSet():
        return [[1,3,4],[2,3,5],[1,2,3,5],[2,5]]

    def createC1(dataSet):
        C1 = []   #C1为大小为1的项的集合
        for transaction in dataSet:  #遍历数据集中的每一条交易
            for item in transaction: #遍历每一条交易中的每个商品
                if not [item] in C1:
                    C1.append([item])
        C1.sort()
        #map函数表示遍历C1中的每一个元素执行forzenset,frozenset表示“冰冻”的集合,即不可改变
        return map(frozenset,C1)

    #Ck表示数据集,D表示候选集合的列表,minSupport表示最小支持度
    #该函数用于从C1生成L1,L1表示满足最低支持度的元素集合
    def scanD(D,Ck,minSupport):
        ssCnt = {}
        for tid in D:
            for can in Ck:
                #issubset:表示如果集合can中的每一元素都在tid中则返回true  
                if can.issubset(tid):
                    #统计各个集合scan出现的次数,存入ssCnt字典中,字典的key是集合,value是统计出现的次数
                    if not ssCnt.has_key(can):
                        ssCnt[can] = 1
                    else:
                        ssCnt[can] += 1
        numItems = float(len(D))
        retList = []
        supportData = {}
        for key in ssCnt:
            #计算每个项集的支持度,如果满足条件则把该项集加入到retList列表中
            support = ssCnt[key]/numItems
            if support >= minSupport:
                retList.insert(0, key)
            #构建支持的项集的字典
            supportData[key] = support
        return retList,supportData
    #====================                准备函数(上)              =============================

    #======================          Apriori算法(下)               =================================
    #Create Ck,CaprioriGen ()的输人参数为频繁项集列表Lk与项集元素个数k,输出为Ck
    def aprioriGen(Lk,k):
        retList = []
        lenLk = len(Lk)
        for i in range(lenLk):
            for j in range(i+1,lenLk):
                #前k-2项相同时合并两个集合
                L1 = list(Lk[i])[:k-2]
                L2 = list(Lk[j])[:k-2]
                L1.sort()
                L2.sort()
                if L1 == L2:
                    retList.append(Lk[i] | Lk[j])

        return retList

    def apriori(dataSet, minSupport=0.5):
        C1 = createC1(dataSet)  #创建C1
        #D: [set([1, 3, 4]), set([2, 3, 5]), set([1, 2, 3, 5]), set([2, 5])]
        D = map(set,dataSet)
        L1,supportData = scanD(D, C1, minSupport)
        L = [L1]
        #若两个项集的长度为k - 1,则必须前k-2项相同才可连接,即求并集,所以[:k-2]的实际作用为取列表的前k-1个元素
        k = 2
        while(len(L[k-2]) > 0):
            Ck = aprioriGen(L[k-2], k)
            Lk,supK = scanD(D,Ck, minSupport)
            supportData.update(supK)
            L.append(Lk)
            k +=1
        return L,supportData
    #======================          Apriori算法(上)               =================================

    if __name__=="__main__":
        dataSet = loadDataSet()
        L,suppData = apriori(dataSet)
        i = 0
        for one in L:
            print "项数为 %s 的频繁项集:" % (i + 1), one,"\n"
            i +=1
    运行上边代码的输出结果是:


    2:挖掘相关规则

    要找到关联规则,我们首先从一个频繁项集开始。从文章开始说的那个交易数据表的例子可以得到,如果有一个频繁项集{Diaper,Beer},那么就可能有一条关联规则“Diaper➞Beer”。这意味着如果有人购买了Diaper,那么在统计上他会购买Beer的概率较大。注意这一条反过来并不总是成立,也就是说,可信度(“Diaper➞Beer”)并不等于可信度(“Beer➞Diaper”)。

    前文也提到过,一条规则P➞H的可信度定义为support(P 并 H)/support(P)。可见可信度的计算是基于项集的支持度的。

    下图给出了从项集{0,1,2,3}产生的所有关联规则,其中阴影区域给出的是低可信度的规则。可以发现如果{0,1,2}➞{3}是一条低可信度规则,那么所有其他以3作为后件(箭头右部包含3)的规则均为低可信度的。


                                                    频繁项集{0,1,2,3}的关联规则网格示意图


    可以观察到,如果某条规则并不满足最小可信度要求,那么该规则的所有子集也不会满足最小可信度要求。以图4为例,假设规则{0,1,2} ➞ {3}并不满足最小可信度要求,那么就知道任何左部为{0,1,2}子集的规则也不会满足最小可信度要求。可以利用关联规则的上述性质属性来减少需要测试的规则数目,类似于Apriori算法求解频繁项集。

    下面我们看一下书中的源代码是怎么写

    关联规则生成函数:

    def generateRules(L, supportData, minConf=0.7):
        bigRuleList = []
        for in range(1, len(L)):
            for freqSet in L[i]:
                H1 = [frozenset([item]) for item in freqSet]
                if (i > 1):
                    # 三个及以上元素的集合
                    rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConf)
                else:
                    # 两个元素的集合
                    calcConf(freqSet, H1, supportData, bigRuleList, minConf)
        return bigRuleList

    这个函数是主函数,调用其他两个函数。其他两个函数是rulesFromConseq()和calcConf(),分别用于生成候选规则集合以及对规则进行评估(计算支持度)

    函数generateRules()有3个参数:频繁项集列表L、包含那些频繁项集支持数据的字典supportData、最小可信度阈值minConf。函数最后要生成一个包含可信度的规则列表bigRuleList,后面可以基于可信度对它们进行排序。L和supportData正好为函数apriori()的输出。该函数遍历L中的每一个频繁项集,并对每个频繁项集构建只包含单个元素集合的列表H1。代码中的i指示当前遍历的频繁项集包含的元素个数,freqSet为当前遍历的频繁项集(回忆L的组织结构是先把具有相同元素个数的频繁项集组织成列表,再将各个列表组成一个大列表,所以为遍历L中的频繁项集,需要使用两层for循环)。

    辅助函数——计算规则的可信度,并过滤出满足最小可信度要求的规则

    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

    计算规则的可信度以及找出满足最小可信度要求的规则。函数返回一个满足最小可信度要求的规则列表,并将这个规则列表添加到主函数的bigRuleList中(通过参数brl)。返回值prunedH保存规则列表的右部,这个值将在下一个函数rulesFromConseq()中用到。

    辅助函数——根据当前候选规则集H生成下一层候选规则集

    def rulesFromConseq(freqSet, H, supportData, brl, minConf=0.7):
        ''' 生成候选规则集 '''
        = len(H[0])
        if (len(freqSet) > (m + 1)):
            Hmpl = aprioriGen(H, m + 1)
            Hmpl = calcConf(freqSet, Hmpl, supportData, brl, minConf)
            if (len(Hmpl) > 1):
                rulesFromConseq(freqSet, Hmpl, supportData, brl, minConf)

    从最初的项集中生成更多的关联规则。该函数有两个参数:频繁项集freqSet,可以出现在规则右部的元素列表H。其余参数:supportData保存项集的支持度,brl保存生成的关联规则,minConf同主函数。函数先计算H中的频繁项集大小m。接下来查看该频繁项集是否大到可以移除大小为m的子集。如果可以的话,则将其移除。使用函数aprioriGen()来生成H中元素的无重复组合,结果保存在Hmp1中,这也是下一次迭代的H列表。

    将上边的三个函数加入 Apriori.py中

    main函数修改为:

    if __name__=="__main__":
        dataSet = loadDataSet()
        L,suppData = apriori(dataSet)
        i = 0
        for one in L:
            print "项数为 %s 的频繁项集:" % (i + 1), one,"\n"
            i +=1

        print "minConf=0.7时:"
        rules = generateRules(L,suppData, minConf=0.7)

        print "\nminConf=0.5时:"
        rules = generateRules(L,suppData, minConf=0.5)
    运行结果如下:

    关于rulesFromConseq()函数的问题

    如果仔细看下上述代码和输出,会发现这里面是一些问题的。

    1 问题的提出

    频繁项集L的值前面提到过。我们在其中计算通过{2, 3, 5}生成的关联规则,可以发现关联规则{3, 5}➞{2}和{2, 3}➞{5}的可信度都应该为1.0的,因而也应该包括在当minConf = 0.7时的rules中——但是这在前面的运行结果中并没有体现出来。minConf = 0.5时也是一样,{3, 5}➞{2}的可信度为1.0,{2, 5}➞{3}的可信度为2/3,{2, 3}➞{5}的可信度为1.0,也没有体现在rules中。

    通过分析程序代码,我们可以发现:

    • 当i = 1时,generateRules()函数直接调用了calcConf()函数直接计算其可信度,因为这时L[1]中的频繁项集均包含两个元素,可以直接生成和判断候选关联规则。比如L[1]中的{2, 3},生成的候选关联规则为{2}➞{3}、{3}➞{2},这样就可以了。
    • 当i > 1时,generateRules()函数调用了rulesFromConseq()函数,这时L[i]中至少包含3个元素,如{2, 3, 5},对候选关联规则的生成和判断的过程需要分层进行(图4)。这里,将初始的H1(表示初始关联规则的右部,即箭头右边的部分)作为参数传递给了rulesFromConseq()函数。

    例如,对于频繁项集{a, b, c, …},H1的值为[a, b, c, …](代码中实际为frozenset类型)。如果将H1带入计算可信度的calcConf()函数,在函数中会依次计算关联规则{b, c, d, …}➞{a}、{a, c, d, …}➞{b}、{a, b, d, …}➞{c}……的支持度,并保存支持度大于最小支持度的关联规则,并保存这些规则的右部(prunedH,即对H的过滤,删除支持度过小的关联规则)。

    当i > 1时没有直接调用calcConf()函数计算通过H1生成的规则集。在rulesFromConseq()函数中,首先获得当前H的元素数m = len(H[0])(记当前的H为H)。当Hm可以进一步合并为m+1元素数的集合Hm+1时(判断条件:len(freqSet) > (m + 1)),依次:

    • 生成Hm+1:Hmpl = aprioriGen(H, m + 1)
    • 计算Hm+1的可信度:Hmpl = calcConf(freqSet, Hmpl, …)
    • 递归计算由Hm+1生成的关联规则:rulesFromConseq(freqSet, Hmpl, …)

    所以这里的问题是,在i>1时,rulesFromConseq()函数中并没有调用calcConf()函数计算H1的可信度,而是直接由H1生成H2,从H2开始计算关联规则——于是由元素数>3的频繁项集生成的{a, b, c, …}➞{x}形式的关联规则(图4中的第2层)均缺失了。由于代码示例数据中的对H1的剪枝prunedH没有删除任何元素,结果只是“巧合”地缺失了一层。正常情况下如果没有对H1进行过滤,直接生成H2,将给下一层带入错误的结果(如图4中的012➞3会被错误得留下来)。

    在i>1时,将对H1调用calcConf()的过程加上就可以了。比如可以这样:

    def generateRules2(L, supportData, minConf=0.7):
        bigRuleList = []
        for in range(1len(L)):
            for freqSet in L[i]:
                H1 = [frozenset([item]) for item in freqSet]
                if (i > 1):
                    # 三个及以上元素的集合
                    H1 = calcConf(freqSet, H1, supportData, bigRuleList, minConf)
                    rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConf)
                else:
                    # 两个元素的集合
                    calcConf(freqSet, H1, supportData, bigRuleList, minConf)
        return bigRuleList

    这里就只需要修改generateRules()函数。这样实际运行效果中,刚才丢失的那几个关联规则就都出来了。

     

    进一步修改:当i=1时的else部分并没有独特的逻辑,这个if语句可以合并,然后再修改rulesFromConseq()函数,保证其会调用calcConf(freqSet, H1, …):

    def generateRules3(L, supportData, minConf=0.7):
        bigRuleList = []
        for in range(1len(L)):
            for freqSet in L[i]:
                H1 = [frozenset([item]) for item in freqSet]
                rulesFromConseq2(freqSet, H1, supportData, bigRuleList, minConf)
        return bigRuleList
     
    def rulesFromConseq2(freqSet, H, supportData, brl, minConf=0.7):
        = len(H[0])
        if (len(freqSet) > m): # 判断长度改为 > m,这时即可以求H的可信度
            Hmpl = calcConf(freqSet, H, supportData, brl, minConf)
            if (len(Hmpl) > 1): # 判断求完可信度后是否还有可信度大于阈值的项用来生成下一层H
                Hmpl = aprioriGen(Hmpl, m + 1)
                rulesFromConseq2(freqSet, Hmpl, supportData, brl, minConf) # 递归计算,不变

    运行结果和generateRules2相同。

     

    进一步修改:消除rulesFromConseq2()函数中的递归项。这个递归纯粹是偷懒的结果,没有简化任何逻辑和增加任何可读性,可以直接用一个循环代替:

    def rulesFromConseq3(freqSet, H, supportData, brl, minConf=0.7):
        = len(H[0])
        while (len(freqSet) > m): # 判断长度 > m,这时即可求H的可信度
            = calcConf(freqSet, H, supportData, brl, minConf)
            if (len(H) > 1): # 判断求完可信度后是否还有可信度大于阈值的项用来生成下一层H
                = aprioriGen(H, m + 1)
                += 1
            else# 不能继续生成下一层候选关联规则,提前退出循环
                break

    另一个主要的区别是去掉了多余的Hmpl变量。运行的结果和generateRules2相同。

    此为修改后的运行结果:

                                


    至此,一个完整的Apriori算法就完成了。


    Apriori算法总结:

    关联分析是用于发现大数据集中元素间有趣关系的一个工具集,可以采用两种方式来量化这些有趣的关系。第一种方式是使用频繁项集,它会给出经常在一起出现的元素项。第二种方式是关联规则,每条关联规则意味着元素项之间的“如果……那么”关系。

    发现元素项间不同的组合是个十分耗时的任务,不可避免需要大量昂贵的计算资源,这就需要一些更智能的方法在合理的时间范围内找到频繁项集。能够实现这一目标的一个方法是Apriori算法,它使用Apriori原理来减少在数据库上进行检查的集合的数目。Apriori原理是说如果一个元素项是不频繁的,那么那些包含该元素的超集也是不频繁的。Apriori算法从单元素项集开始,通过组合满足最小支持度要求的项集来形成更大的集合。支持度用来度量一个集合在原始数据中出现的频率。

    关联分析可以用在许多不同物品上。商店中的商品以及网站的访问页面是其中比较常见的例子。

    每次增加频繁项集的大小,Apriori算法都会重新扫描整个数据集。当数据集很大时,这会显著降低频繁项集发现的速度。下面会介绍FP-growth算法,和Apriori算法相比,该算法只需要对数据库进行两次遍历,能够显著加快发现频繁项集的速度。

     

    四:使用FP-growth高效发现频繁项集

    (拿书中的数据举例)FP-growth算法将数据存储在一种称为FP树的紧凑数据结构中。FP代表频繁模式(Frequent Pattern)。一棵FP树看上去与计算机科学中的其他树结构类似,但是它通过链接(link)来连接相似元素,被连起来的元素项可以看成一个链表。图5给出了FP树的一个例子。

                                                                                          


                                                  上图为 一棵FP树,和一般的树结构类似,包含着连接相似节点(值相同的节点)的连接 

     与搜索树不同的是,一个元素项可以在一棵FP树种出现多次。FP树辉存储项集的出现频率,而每个项集会以路径的方式存储在数中。存在相似元素的集合会共享树的一部分。只有当集合之间完全不同时,树才会分叉。 树节点上给出集合中的单个元素及其在序列中的出现次数,路径会给出该序列的出现次数。

    相似项之间的链接称为节点链接(node link),用于快速发现相似项的位置。

    举例说明,下表用来产生图5的FP树:     

    用于生成图5中FP树的事务数据样例
    事务ID 事务中的元素项
    001 r, z, h, j, p
    002 z, y, x, w, v, u, t, s
    003 z
    004 r, x, n, o, s
    005 y, r, x, z, q, t, p
    006 y, z, x, e, q, s, t, m

    对FP树的解读:

    图5中,元素项z出现了5次,集合{r, z}出现了1次。于是可以得出结论:z一定是自己本身或者和其他符号一起出现了4次。集合{t, s, y, x, z}出现了2次,集合{t, r, y, x, z}出现了1次,z本身单独出现1次。就像这样,FP树的解读方式是读取某个节点开始到根节点的路径。路径上的元素构成一个频繁项集,开始节点的值表示这个项集的支持度。根据图5,我们可以快速读出项集{z}的支持度为5、项集{t, s, y, x, z}的支持度为2、项集{r, y, x, z}的支持度为1、项集{r, s, x}的支持度为1。FP树中会多次出现相同的元素项,也是因为同一个元素项会存在于多条路径,构成多个频繁项集。但是频繁项集的共享路径是会合并的,如图中的{t, s, y, x, z}和{t, r, y, x, z}

    和之前一样,我们取一个最小阈值,出现次数低于最小阈值的元素项将被直接忽略。图5中将最小支持度设为3,所以q和p没有在FP中出现。

    FP-growth算法的工作流程如下。首先构建FP树,然后利用它来挖掘频繁项集。为构建FP树,需要对原始数据集扫描两遍。第一遍对所有元素项的出现次数进行计数。数据库的第一遍扫描用来统计出现的频率,而第二遍扫描中只考虑那些频繁元素


    1:创建FP树的数据结构

    由于树节点的结构比较复杂,我们使用一个类表示。创建文件fpGrowth.py并加入下列代码:

    class treeNode:
        def __init__(self, nameValue, numOccur, parentNode):
            self.name = nameValue
            self.count = numOccur
            self.nodeLink = None
            self.parent = parentNode
            self.children = {}
     
        def inc(self, numOccur):
            self.count += numOccur
     
        def disp(self, ind=1):
            print ' ' * ind, self.name, ' 'self.count
            for child in self.children.values():
                child.disp(ind + 1)

    每个树节点由五个数据项组成:

    • name:节点元素名称,在构造时初始化为给定值
    • count:出现次数,在构造时初始化为给定值
    • nodeLink:指向下一个相似节点的指针,默认为None
    • parent:指向父节点的指针,在构造时初始化为给定值
    • children:指向子节点的字典,以子节点的元素名称为键,指向子节点的指针为值,初始化为空字典

    成员函数:

    • inc():增加节点的出现次数值
    • disp():输出节点和子节点的FP树结构

    测试代码:

    >>>import fpGrowth
    >>> rootNode = fpGrowth.treeNode('pyramid'9None)
    >>> rootNode.children['eye'= fpGrowth.treeNode('eye'13None)
    >>> rootNode.children['phoenix'= fpGrowth.treeNode('phoenix'3None)
    >>> rootNode.disp()

    2:构建FP树

    头指针表

    FP-growth算法还需要一个称为头指针表的数据结构,其实很简单,就是用来记录各个元素项的总出现次数的数组,再附带一个指针指向FP树中该元素项的第一个节点。这样每个元素项都构成一条单链表。图示说明:

                              
                                        带头指针表的FP树,头指针表作为一个起始指针来发现相似元素项

    这里使用Python字典作为数据结构,来保存头指针表。以元素项名称为键,保存出现的总次数和一个指向第一个相似元素项的指针。

    第一次遍历数据集会获得每个元素项的出现频率,去掉不满足最小支持度的元素项,生成这个头指针表。

    元素项排序

    上文提到过,FP树会合并相同的频繁项集(或相同的部分)。因此为判断两个项集的相似程度需要对项集中的元素进行排序(不过原因也不仅如此,还有其它好处)。排序基于元素项的绝对出现频率(总的出现次数)来进行。在第二次遍历数据集时,会读入每个项集(读取),去掉不满足最小支持度的元素项(过滤),然后对元素进行排序(重排序)。

    对示例数据集进行过滤和重排序的结果如下:

    事务ID 事务中的元素项 过滤及重排序后的事务
    001 r, z, h, j, p z, r
    002 z, y, x, w, v, u, t, s z, x, y, s, t
    003 z z
    004 r, x, n, o, s x, s, r
    005 y, r, x, z, q, t, p z, x, y, r, t
    006 y, z, x, e, q, s, t, m z, x, y, s, t

     

    构建FP树

    在对事务记录过滤和排序之后,就可以构建FP树了。从空集开始,将过滤和重排序后的频繁项集一次添加到树中。如果树中已存在现有元素,则增加现有元素的值;如果现有元素不存在,则向树添加一个分支。对前两条事务进行添加的过程:

                                   
                                                                          FP树构建过程示意(添加前两条事务)

    算法:构建FP树

    输入:数据集、最小值尺度
    输出:FP树、头指针表
    1. 遍历数据集,统计各元素项出现次数,创建头指针表
    2. 移除头指针表中不满足最小值尺度的元素项
    3. 第二次遍历数据集,创建FP树。对每个数据集中的项集:
        3.1 初始化空FP树
        3.2 对每个项集进行过滤和重排序
        3.3 使用这个项集更新FP树,从FP树的根节点开始:
            3.3.1 如果当前项集的第一个元素项存在于FP树当前节点的子节点中,则更新这个子节点的计数值
            3.3.2 否则,创建新的子节点,更新头指针表
            3.3.3 对当前项集的其余元素项和当前元素项的对应子节点递归3.3的过程

    代码(在fpGrowth.py中加入下面的代码):

    1: 总函数:createTree

    def createTree(dataSet, minSup=1):
        ''' 创建FP树 '''
        # 第一次遍历数据集,创建头指针表
        headerTable = {}
        for trans in dataSet:
            for item in trans:
                headerTable[item] = headerTable.get(item, 0+ dataSet[trans]
        # 移除不满足最小支持度的元素项
        for in headerTable.keys():
            if headerTable[k] < minSup:
                del(headerTable[k])
        # 空元素集,返回空
        freqItemSet = set(headerTable.keys())
        if len(freqItemSet) == 0:
            return NoneNone
        # 增加一个数据项,用于存放指向相似元素项指针
        for in headerTable:
            headerTable[k] = [headerTable[k], None]
        retTree = treeNode('Null Set'1None# 根节点
        # 第二次遍历数据集,创建FP树
        for tranSet, count in dataSet.items():
            localD = {} # 对一个项集tranSet,记录其中每个元素项的全局频率,用于排序
            for item in tranSet:
                if item in freqItemSet:
                    localD[item] = headerTable[item][0# 注意这个[0],因为之前加过一个数据项
            if len(localD) > 0:
                orderedItems = [v[0for in sorted(localD.items(), key=lambda p: p[1], reverse=True)] # 排序
                updateTree(orderedItems, retTree, headerTable, count) # 更新FP树
        return retTree, headerTable

    (代码比较宽,大家的显示器都那么大,应该没关系吧……)

    需要注意的是,参数中的dataSet的格式比较奇特,不是直觉上得集合的list,而是一个集合的字典,以这个集合为键,值部分记录的是这个集合出现的次数。于是要生成这个dataSet还需要后面的createInitSet()函数辅助。因此代码中第7行中的dataSet[trans]实际获得了这个trans集合的出现次数(在本例中均为1),同样第21行的“for tranSet, count in dataSet.items():”获得了tranSet和count分别表示一个项集和该项集的出现次数。——这样做是为了适应后面在挖掘频繁项集时生成的条件FP树。

    2:辅助函数:updateTree

    def updateTree(items, inTree, headerTable, count):
        if items[0in inTree.children:
            # 有该元素项时计数值+1
            inTree.children[items[0]].inc(count)
        else:
            # 没有这个元素项时创建一个新节点
            inTree.children[items[0]] = treeNode(items[0], count, inTree)
            # 更新头指针表或前一个相似元素项节点的指针指向新节点
            if headerTable[items[0]][1== None:
                headerTable[items[0]][1= inTree.children[items[0]]
            else:
                updateHeader(headerTable[items[0]][1], inTree.children[items[0]])
     
        if len(items) > 1:
            # 对剩下的元素项迭代调用updateTree函数
            updateTree(items[1::], inTree.children[items[0]], headerTable, count)

    3: 辅助函数:updateHeader

    def updateHeader(nodeToTest, targetNode):
        while (nodeToTest.nodeLink != None):
            nodeToTest = nodeToTest.nodeLink
        nodeToTest.nodeLink = targetNode

    这个函数其实只做了一件事,就是获取头指针表中该元素项对应的单链表的尾节点,然后将其指向新节点targetNode。

     

    生成数据集

    def loadSimpDat():
        simpDat = [['r''z''h''j''p'],
                   ['z''y''x''w''v''u''t''s'],
                   ['z'],
                   ['r''x''n''o''s'],
                   ['y''r''x''z''q''t''p'],
                   ['y''z''x''e''q''s''t''m']]
        return simpDat
     
    def createInitSet(dataSet):
        retDict = {}
        for trans in dataSet:
            retDict[frozenset(trans)] = 1
        return retDict

    生成的样例数据同文中用得一样。这个诡异的输入格式就是createInitSet()函数中这样来得。

     

    测试代码

    >>> import fpGrowth
    >>> simpDat = fpGrowth.loadSimpDat()
    >>> initSet = fpGrowth.createInitSet(simpDat)
    >>> myFPtree, myHeaderTab = fpGrowth.createTree(initSet, 3)
    >>> myFPtree.disp()

    结果是这样的(连字都懒得打了,直接截图……):

                                                                                 

    得到的FP树也和图5中的一样



    3:从一棵FP树中挖掘频繁项集

    从FP树中抽取频繁项集的三个基本步骤如下:

    1. 从FP树中获得条件模式基;
    2. 利用条件模式基,构建一个条件FP树;
    3. 迭代重复步骤1步骤2,直到树包含一个元素项为止。


    1 抽取条件模式基

    (什么鬼……)

    首先从头指针表中的每个频繁元素项开始,对每个元素项,获得其对应的条件模式基(conditional pattern base)。条件模式基是以所查找元素项为结尾的路径集合。每一条路径其实都是一条前缀路径(prefix path)。简而言之,一条前缀路径是介于所查找元素项与树根节点之间的所有内容。

    将图5重新贴在这里:

                                                                                           

    则每一个频繁元素项的所有前缀路径(条件模式基)为:

    频繁项 前缀路径
    z {}: 5
    r {x, s}: 1, {z, x, y}: 1, {z}: 1
    x {z}: 3, {}: 1
    y {z, x}: 3
    s {z, x, y}: 2, {x}: 1
    t {z, x, y, s}: 2, {z, x, y, r}: 1

    发现规律了吗,z存在于路径{z}中,因此前缀路径为空,另添加一项该路径中z节点的计数值5构成其条件模式基;r存在于路径{r, z}、{r, y, x, z}、{r, s, x}中,分别获得前缀路径{z}、{y, x, z}、{s, x},另添加对应路径中r节点的计数值(均为1)构成r的条件模式基;以此类推。

    前缀路径将在下一步中用于构建条件FP树,暂时先不考虑。如何发现某个频繁元素项的所在的路径?利用先前创建的头指针表和FP树中的相似元素节点指针,我们已经有了每个元素对应的单链表,因而可以直接获取。

    下面的程序给出了创建前缀路径的代码:

    1 主函数:findPrefixPath

    def findPrefixPath(basePat, treeNode):
        ''' 创建前缀路径 '''
        condPats = {}
        while treeNode != None:
            prefixPath = []
            ascendTree(treeNode, prefixPath)
            if len(prefixPath) > 1:
                condPats[frozenset(prefixPath[1:])] = treeNode.count
            treeNode = treeNode.nodeLink
        return condPats

    该函数代码用于为给定元素项生成一个条件模式基(前缀路径),这通过访问树中所有包含给定元素项的节点来完成。参数basePet表示输入的频繁项,treeNode为当前FP树种对应的第一个节点(可在函数外部通过headerTable[basePat][1]获取)。函数返回值即为条件模式基condPats,用一个字典表示,键为前缀路径,值为计数值。

    2 辅助函数:ascendTree

    def ascendTree(leafNode, prefixPath):
        if leafNode.parent != None:
            prefixPath.append(leafNode.name)
            ascendTree(leafNode.parent, prefixPath)

    这个函数直接修改prefixPath的值,将当前节点leafNode添加到prefixPath的末尾,然后递归添加其父节点。最终结果,prefixPath就是一条从treeNode(包括treeNode)到根节点(不包括根节点)的路径。在主函数findPrefixPath()中再取prefixPath[1:],即为treeNode的前缀路径。

    测试代码:

    >>> fpGrowth.findPrefixPath('x', myHeaderTab['x'][1])
    >>> fpGrowth.findPrefixPath('z', myHeaderTab['z'][1])
    >>> fpGrowth.findPrefixPath('r', myHeaderTab['r'][1])
    输出结果:

    2 创建条件FP树

    (又是什么鬼……)

    对于每一个频繁项,都要创建一棵条件FP树。可以使用刚才发现的条件模式基作为输入数据,并通过相同的建树代码来构建这些树。例如,对于r,即以“{x, s}: 1, {z, x, y}: 1, {z}: 1”为输入,调用函数createTree()获得r的条件FP树;对于t,输入是对应的条件模式基“{z, x, y, s}: 2, {z, x, y, r}: 1”。

    代码(直接调用createTree()函数):

    condPattBases = findPrefixPath(basePat, headerTable[basePat][1])
    myCondTree, myHead = createTree(condPattBases, minSup)

    示例:t的条件FP树

                             

                                                                                      t的条件FP树的创建过程

    在图8中,注意到元素项s以及r是条件模式基的一部分,但是它们并不属于条件FP树。因为在当前的输入中,s和r不满足最小支持度的条件。

    3 递归查找频繁项集

    有了FP树和条件FP树,我们就可以在前两步的基础上递归得查找频繁项集。

    递归的过程是这样的:

    输入:我们有当前数据集的FP树(inTree,headerTable)
    1. 初始化一个空列表preFix表示前缀
    2. 初始化一个空列表freqItemList接收生成的频繁项集(作为输出)
    3. 对headerTable中的每个元素basePat(按计数值由小到大),递归:
            3.1 记basePat + preFix为当前频繁项集newFreqSet
            3.2 将newFreqSet添加到freqItemList中
            3.3 计算t的条件FP树(myCondTree、myHead)
            3.4 当条件FP树不为空时,继续下一步;否则退出递归
            3.4 以myCondTree、myHead为新的输入,以newFreqSet为新的preFix,外加freqItemList,递归这个过程

    函数如下:

    def mineTree(inTree, headerTable, minSup, preFix, freqItemList):
        bigL = [v[0for in sorted(headerTable.items(), key=lambda p: p[1])]
        for basePat in bigL:
            newFreqSet = preFix.copy()
            newFreqSet.add(basePat)
            freqItemList.append(newFreqSet)
            condPattBases = findPrefixPath(basePat, headerTable[basePat][1])
            myCondTree, myHead = createTree(condPattBases, minSup)
     
            if myHead != None:
                # 用于测试
                print 'conditional tree for:', newFreqSet
                myCondTree.disp()
     
                mineTree(myCondTree, myHead, minSup, newFreqSet, freqItemList)

    输入参数:

    • inTree和headerTable是由createTree()函数生成的数据集的FP树
    • minSup表示最小支持度
    • preFix请传入一个空集合(set([])),将在函数中用于保存当前前缀
    • freqItemList请传入一个空列表([]),将用来储存生成的频繁项集

    测试代码:

    >>> freqItems = []
    >>> fpGrowth.mineTree(myFPtree, myHeaderTab, 3set([]), freqItems)
    >>> freqItems

    [set(['y']), set(['y', 'x']), set(['y', 'z']), set(['y', 'x', 'z']), set(['s']), set(['x', 's']), set(['t']), set(['z', 't']), set(['x', 'z', 't']), set(['y', 'x', 'z', 't']), set(['y', 'z', 't']), set(['x', 't']), set(['y', 'x', 't']), set(['y', 't']), set(['r']), set(['x']), set(['x', 'z']), set(['z'])]

    想这一段代码解释清楚比较难,因为中间涉及到很多递归。直接举例说明,我们在这里分解输入myFPtree和myHeaderTab后,“for basePat in bigL:”一行当basePat为’t’时的过程:

    图9 mineTree函数解构图(basePat = ‘t’)

    图中红色加粗的部分即实际添加到freqItemList中的频繁项集。

    4 封装

    至此,完整的FP-growth算法已经可以运行。封装整个过程如下:

    def fpGrowth(dataSet, minSup=3):
        initSet = createInitSet(dataSet)
        myFPtree, myHeaderTab = createTree(initSet, minSup)
        freqItems = []
        mineTree(myFPtree, myHeaderTab, minSup, set([]), freqItems)
        return freqItems

    测试代码:

    >>> import fpGrowth
    >>> dataSet = fpGrowth.loadSimpDat()
    >>> freqItems = fpGrowth.fpGrowth(dataSet)
    >>> freqItems

    和之前的输出相同。

    5 总结

    FP-growth算法是一种用于发现数据集中频繁模式的有效方法。FP-growth算法利用Apriori原则,执行更快。Apriori算法产生候选项集,然后扫描数据集来检查它们是否频繁。由于只对数据集扫描两次,因此FP-growth算法执行更快。在FP-growth算法中,数据集存储在一个称为FP树的结构中。FP树构建完成后,可以通过查找元素项的条件基及构建条件FP树来发现频繁项集。该过程不断以更多元素作为条件重复进行,直到FP树只包含一个元素为止。

    FP-growth算法还有一个map-reduce版本的实现,它也很不错,可以扩展到多台机器上运行。Google使用该算法通过遍历大量文本来发现频繁共现词,其做法和我们刚才介绍的例子非常类似(参见扩展阅读:FP-growth算法)。



    五:实例:从新闻站点点击流中挖掘新闻报道

    书中的这两章有不少精彩的示例,这里只选取比较有代表性的一个——从新闻网站点击流中挖掘热门新闻报道。这是一个很大的数据集,有将近100万条记录(参见扩展阅读:kosarak)。在源数据集合保存在文件kosarak.dat(http://fimi.ua.ac.be/data/)中。该文件中的每一行包含某个用户浏览过的新闻报道。新闻报道被编码成整数,我们可以使用Apriori或FP-growth算法挖掘其中的频繁项集,查看那些新闻ID被用户大量观看到。

    首先,将数据集导入到列表:

    >>> parsedDat = [line.split() for line in open('kosarak.dat').readlines()]

    接下来需要对初始集合格式化:

    >>> import fpGrowth
    >>> initSet = fpGrowth.createInitSet(parsedDat)

    然后构建FP树,并从中寻找那些至少被10万人浏览过的新闻报道。

    >>> myFPtree, myHeaderTab = fpGrowth.createTree(initSet, 100000)

    下面创建一个空列表来保存这些频繁项集:

    >>> myFreqList = []
    >>> fpGrowth.mineTree(myFPtree, myHeaderTab, 100000set([]), myFreqList)

    接下来看下有多少新闻报道或报道集合曾经被10万或者更多的人浏览过:

    >>> len(myFreqList)

    9

    总共有9个。下面看看都是那些:

    >>> myFreqList

    [set(['1']), set(['1', '6']), set(['3']), set(['11', '3']), set(['11', '3', '6']), set(['3', '6']), set(['11']), set(['11', '6']), set(['6'])]


    至此Apriori算法和FP-Tree算法已经讲解分析完毕,当然我这里讲的有很多不足的地方,希望大家指正。

    展开全文
  • 小伙伴们,继续一起学习机器学习算法啦,今天学习关联分析、Apriori算法啦!大家肯定很熟悉一个故事-沃尔玛超市数据总结出的啤酒与尿布的相关性(知乎上也有牛人们在讨论这个故事的真假) 图1来自《机器学习实战》这...

    小伙伴们,继续一起学习机器学习算法啦,今天学习关联分析、Apriori算法啦!大家肯定很熟悉一个故事-沃尔玛超市数据总结出的啤酒与尿布的相关性(知乎上也有牛人们在讨论这个故事的真假)


    图1

    来自《机器学习实战》这本书里提到的一个例子,展示了如下的一个购物清单:



    图2

    在上述购物交易单中发现,{尿布,葡萄酒}出现的次数较多,辣么,他们之间真的有木有关系呢?这就需要关联分析。

    关联分析:在大规模数据集中寻找有趣关系的任务。这些关系可以有两种形式:频繁项集或者关联规则。频繁项集(frequent item sets)是指经常出现在一起的物品的集合,关联关系(association rules)暗示两种物品之间可能存在很强的关系。比如上面的{尿布,葡萄酒}就频繁出现,他们之间可能存在一些关系,辣么,如何来确定是否是频繁项集呢?主要是依靠支持度和可信度。

    一个项集的支持度(support)被定义为数据集中包含该项集的记录所占的比例。比如,图2中{豆奶}的支持度为4/5。支持度是针对项集来说的,因此可以定义一个最小支持度,而只保留满足最小支持度的项集。可信度或置信度(confidence)是针对一条诸如{尿布}->{葡萄酒}的关联关系来定义的。这条规则的可信度被定义为“支持度({尿布,葡萄酒})/支持度({尿布})”

    可是,如何计算一个集合中的频繁项集的支持度,首先需要遍历全部可能的项集,比如针对一个包含了4个产品的集合,那么购买该集合产品的可能集合数目为2^4-1=15,而针对包含N项的集合,就需要遍历2^N-1。显然,这样的计算量很大。因此,出现了Apriori原理。

    Apriori原理:如果某个项集是频繁的,那么它的所有子集也是频繁的。该定理的逆反定理为:如果某一个项集是非频繁的,那么它的所有超集(包含该集合的集合)也是非频繁的。Apriori原理的出现,可以在得知某些项集是非频繁之后,不需要计算该集合的超集,有效地避免项集数目的指数增长,从而在合理时间内计算出频繁项集。

    Apriori算法实现:Apriori算法是发现频繁项集的一种方法。Apriori算法的两个输入参数分别是最小支持度和数据集。该算法首先会生成所有单个物品的项集列表->接着扫描交易记录来查看哪些项集满足最小支持度要求,其中不满足最小支持度的集合会被去掉->然后对剩下的集合进行组合以生成包含两个数据集的项集->接着重新扫描交易记录,去掉不满足最小支持度的项集->该过程重复进行直到所有项集都被滤掉。

    Apriori算法Python编程

    1)准备数据



    图3

    在图2中提到的createC1()函数中的C1指的是最原始的待选项集,也就是所有单个物品的项集列表;为什么这里将C1转换为frozenset,而不是一般额set呢,简单解释:

    set无序排序且不重复,是可变的,有add(),remove()等方法。既然是可变的,所以它不存在哈希值。基本功能包括关系测试和消除重复元素. 集合对象还支持union(联合), intersection(交集), difference(差集)和sysmmetric difference(对称差集)等数学运算。sets 支持 x in set, len(set),和 for x in set 。作为一个无序的集合,sets不记录元素位置或者插入点。因此,sets不支持 indexing, 或其它类序列的操作。

    frozenset是冻结的集合,它是不可变的,存在哈希值,好处是它可以作为字典的key,也可以作为其它集合的元素。缺点是一旦创建便不能更改,没有add,remove方法。详情见set与frozenset

    2)过滤函数:根据待选项集Ck的情况,判断数据集D中Ck元素的出现频率,过滤掉低于最低支持度的项集。



    图4

    3)当待选项集不是单个元素时,比如K>=2的情况下,合并元素时容易出现出现重复,因此针对包含K个元素的频繁项集,对比每个频繁项集第K-2位是否一致。详情如下:



    图5



    图6

    4)Apriori算法核心



    图7

    基于上述算法,仿真得到,不同的最小支持度得到的频繁项集是不同的。

    当minSupport=0.5时,得到的频繁项集是:[[frozenset([1]), frozenset([3]), frozenset([2]), frozenset([5])], [frozenset([1, 3]), frozenset([2, 5]), frozenset([2, 3]), frozenset([3, 5])], [frozenset([2, 3, 5])], []]

    当minSupport=0.7时,得到的频繁项集是:[[frozenset([3]), frozenset([2]), frozenset([5])], [frozenset([2, 5])], []];

    实际每个项集的支持度为:{frozenset([5]): 0.75, frozenset([3]): 0.75, frozenset([3, 5]): 0.5, frozenset([4]): 0.25, frozenset([2, 3]): 0.5, frozenset([2, 5]): 0.75, frozenset([1]): 0.5, frozenset([2]): 0.75}

    基于Apriori算法,从频繁项集挖掘关联规则

    基于Apriori算法可以获得频繁项,基于这些频繁项集可以产生很多关联规则。如果能够减少规则数目来确保问题的可解性,可以较大的减少计算复杂度。易知,如果某条规则不满足最小可信度要求,那么该规则的所有子集也不会满足最小可信度要求。利用关联规则的上述性质,基于Apriori算法,首先从一个频繁项集开始,接着创建一个规则列表,其中规则右部只包含一个元素,,然后对这些规则进行测试。接下来合并所有的剩余规则列表来创建一个新的规则列表,其中规则右部包含两个元素。这种方法称作分级法。



    图8



    图9 针对图8张函数说明

    好哒,关于Apriori算法的初步学习基本到这里,希望对大家有用,欢迎大牛不吝赐教哈,各位朋友,晚安、早安啦~~


    展开全文
  •  关联分析主要分为:频繁项集生成和关联规则生成1.频繁项集生成——Apriori算法代码:def createC1(dataSet): ''' 构建大小为1的所有候选项的集合,存储不重复的项值 map(function,data)映射函数,在python3中...
  • 关联分析的FP-growth算法 in Python

    千次阅读 2016-02-25 11:32:54
    关联分析的FP-growth算法 in Python
  • 刘思峰教授提出的广义灰色关联分析python算法实现。其中包括绝对关联度,相对关联度和综合关联度的计算实现。
  • Python关联分析之——Apriori算法

    万次阅读 2017-12-01 09:18:19
    使用Apriori算法进行关联分析Apriori原理 如果某个项集是频繁的,那么它的所有子集也是频繁的。即如果{0,1}是频繁的,则{0},{1}也是频繁的。 这个原理直观上并没有什么帮助,但如果反过来看,就有用了。 ...
  • 包含四个程序,分别从dat文件,txt文件,csv文件,xls文件中读取数据,并利用MIC算法进行数据关联性挖掘,后以图片形式呈现结果。文件包含源码和测试数据。
  • Apriori算法--关联分析算法(一)

    万次阅读 多人点赞 2017-10-16 15:49:49
    在实际生产生活我们经常会遇到一些“关联分析”(Association Analyse)的任务。举几个实际例子。1.人们的购物清单里面的各个商品有没有什么关联呢?就像下面这个购物清单写的那样子,右边是各个顾客所买的东西。 有...
  • 本代码主要利用Python工具实现Apriori算法进行关联分析,简单明了,易于理解
  • 一个实例带你搞懂Apriori关联分析算法

    千次阅读 多人点赞 2020-05-31 16:13:01
    关联分析算法 关联分析是一种在大规模数据集中寻找有趣关系的任务。这些关系可以有两种形式:频繁项集或者关联规则。 附算法分析以及详细代码示例
  • 调用apriori进行关联规则分析,具体代码如下,其中数据集选取本博客 “机器学习算法——关联规则” 中的例子,可进行参考,设置最小支持度(min_support)为0.4,最小置信度(min_threshold)为0.1, 最小提升度...
  • Aprior算法是比较经典的关联规则挖掘算法。 核心思想 核心就是先验原理,即频繁项集的子集必定是频繁项集。反之,若子集非频繁,则超集必定非频繁。 算法简介 基本概念 购物篮事务...
  • 支持度计数二、Apriori算法:使用候选产生频繁项集1.Apriori的性质2.Apriori算法实现过程3.Apriori算法实现过程实例三.Apriori算法python实现 引言   关联规则分析是数据挖掘中最活跃的研究方法之一,目的是在一...
  • python实现关联规则分析Apriori算法

    千次阅读 2017-09-16 00:27:19
    Apriori其实是为了降低搜索空间以及提高搜索速度而设计的一种算法,本文采用python实现,彻底理解“频繁项集的所有非空子集一定是频繁的”这句话,并实现连接步、剪枝步、规则生成、提升度计算等。 本节代码参考...
  • Apriori关联分析python实现(含数据集),结构清晰易懂
  • 分类算法必须需要训练数据,训练数据包含物品的特征和类别(label,也可以被称作标签),这相当于对这些数据建立了映射规则,这种映射规则可以通过机器学习相应的算法来建立,当需要对新的数据进行分类时,就可以直接...
  • 灰色关联分析python

    千次阅读 2020-08-18 21:31:22
    灰色关联分析代码python import pandas as pd x=pd.read_csv('data4.csv') x=x.iloc[:,:].T # 1、数据均值化处理 x_mean=x.mean(axis=1) for i in range(x.index.size): x.iloc[i,:] = x.iloc[i,:]/x_mean[i] #...
  • 关联规则Apriori算法Python实现带数据集,Apriori算法是一种挖掘关联规则的频繁项集算法,其核心思想是通过候选集生成和情节的向下封闭检测两个阶段来挖掘频繁项集。
  • 机器学习之关联规则挖掘Apriori算法
  • 《C站最全Python标准总结》,登顶了【全站综合热榜】和【python领域热榜】,获得了2362多次点赞、998次评论、2072次收藏,谢谢各位小伙伴。
  • 本模块重点介绍什么是关联规则挖掘和Apriori算法,以及Apriori算法的用法。此外,在小型企业场景中,我们将借助Python编程语言构建一个Apriori模型。 什么是关联规则挖掘? 如前所述,Apriori算法用于关联...
  • 关联分析——FP树增长算法以及Python实现

    千次阅读 多人点赞 2018-05-07 21:58:27
    FP树增长算法是一种挖掘频繁项集的算法。Apriori算法虽然简单易实现,效果也不错,但是需要频繁地扫描数据集,IO费用很大。FP树增长算法有效地解决了这一问题,其通过两次扫描数据集构建FP树,然后通过FP树挖掘频繁...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 32,928
精华内容 13,171
关键字:

关联分析算法python库

python 订阅