您的位置是:网站首页>Python编程Python编程

如何理解关联规则apriori算法

少儿编程网2021-01-04 13:20:01Python编程 人已围观 来源:少儿编程 -用户投稿

简介理解关联规则apriori算法:Apriori算法是第一个关联规则挖掘算法,也是最经典的算法,它利用逐层搜索的迭代方法找出数据库中项集的关系,以形成规则,其过程由连接【类矩阵运算】与剪枝【去掉那些没必要的中间结果】组成。理解关联规则apriori算法:一、概念表1某超市的交易数据库交易号TID顾客购

理解关联规则apriori算法:Apriori算法是第一个关联规则挖掘算法,也是**经典的算法,它利用逐层搜索的迭代方法找出数据库中项集的关系,以形成规则,其过程由连接【类矩阵运算】与剪枝【去掉那些没必要的中间结果】组成。uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

理解关联规则apriori算法:uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

一、概念 uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

表1 某超市的交易数据库uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

交易号TIDuxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

顾客购买的商品uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

交易号TIDuxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

顾客购买的商品uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

T1uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

bread, cream, milk, teauxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

T6uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

bread, teauxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

T2uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

bread, cream, milkuxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

T7uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

beer, milk, teauxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

T3uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

cake, milkuxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

T8uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

bread, teauxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

T4uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

milk, teauxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

T9uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

bread, cream, milk, teauxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

T5uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

bread, cake, milkuxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

T10uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

bread, milk, teauxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

定义一:设I={i1,i2,…,im},是m个不同的项目的集合,每个ik称为一个项目。项目的集合I称为项集。其元素的个数称为项集的长度,长度为k的项集称为k-项集。引例中每个商品就是一个项目,项集为I={bread, beer, cake,cream, milk, tea},I的长度为6。uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

定义二:每笔交易T是项集I的一个子集。对应每一个交易有一个**标识交易号,记作TID。交易全体构成了交易数据库D,|D|等于D中交易的个数。引例中包含10笔交易,因此|D|=10。uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

定义三:对于项集X,设定count(X⊆T)为交易集D中包含X的交易的数量,则项集X的支持度为:uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

support(X)=count(X⊆T)/|D|uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

引例中X={bread, milk}出现在T1,T2,T5,T9和T10中,所以支持度为0.5。uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

定义四**小支持度是项集的**小支持阀值,记为SUPmin,代表了用户关心的关联规则的**低重要性。支持度不小于SUPmin 的项集称为频繁集,长度为k的频繁集称为k-频繁集。如果设定SUPmin为0.3,引例中{bread, milk}的支持度是0.5,所以是2-频繁集。uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

定义五关联规则是一个蕴含式:uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

R:X⇒YuxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

其中X⊂I,Y⊂I,并且X∩Y=⌀。表示项集X在某一交易中出现,则导致Y以某一概率也会出现。用户关心的关联规则,可以用两个标准来衡量:支持度和可信度。uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

定义六:关联规则R的支持度是交易集同时包含X和Y的交易数与|D|之比。即:uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

support(X⇒Y)=count(X⋃Y)/|D|uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

支持度反映了X、Y同时出现的概率。关联规则的支持度等于频繁集的支持度。 uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

定义七:对于关联规则R,可信度是指包含X和Y的交易数与包含X的交易数之比。即:uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

confidence(X⇒Y)=support(X⇒Y)/support(X)uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

可信度反映了如果交易中包含X,则交易包含Y的概率。一般来说,只有支持度和可信度较高的关联规则才是用户感兴趣的。uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

定义八:设定关联规则的**小支持度和**小可信度为SUPmin和CONFmin。规则R的支持度和可信度均不小于SUPmin和CONFmin ,则称为强关联规则。关联规则挖掘的目的就是找出强关联规则,从而指导商家的决策。uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

这八个定义包含了关联规则相关的几个重要基本概念,关联规则挖掘主要有两个问题:uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

  1. 找出交易数据库中所有大于或等于用户指定的**小支持度的频繁项集。
  2. 利用频繁项集生成所需要的关联规则,根据用户设定的**小可信度筛选出强关联规则。

目前研究人员主要针对第一个问题进行研究,找出频繁集是比较困难的,而有了频繁集再生成强关联规则就相对容易了。uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

二、理论基础 uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

首先来看一个频繁集的性质。uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

定理:如果项目集X是频繁集,那么它的非空子集都是频繁集uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

根据定理,已知一个k-频繁集的项集X,X的所有k-1阶子集都肯定是频繁集,也就肯定可以找到两个k-1频繁集的项集,它们只有一项不同,且连接后等于X。这证明了通过连接k-1频繁集产生的k-候选集覆盖了k-频繁集。同时,如果k-候选集中的项集Y,包含有某个k-1阶子集不属于k-1频繁集,那么Y就不可能是频繁集,应该从候选集中裁剪掉。Apriori算法就是利用了频繁集的这个性质。uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

三、算法步骤: uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

首先是测试数据:uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

交易IDuxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

商品ID列表uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

T100uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

I1,I2,I5uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

T200uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

I2,I4uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

T300uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

I2,I3uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

T400uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

I1,I2,I4uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

T500uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

I1,I3uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

T600uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

I2,I3uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

T700uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

I1,I3uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

T800uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

I1,I2,I3,I5uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

T900uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

I1,I2,I3uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

算法的步骤图:uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

可以看到,第三轮的候选集发生了明显的缩小,这是为什么呢?uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

请注意取候选集的两个条件:uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

1.两个K项集能够连接的两个条件是,它们有K-1项是相同的。所以,(I2,I4)和(I3,I5)这种是不能够进行连接的。缩小了候选集。uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

2.如果一个项集是频繁集,那么它不存在不是子集的频繁集。比如(I1,I2)和(I1,I4)得到(I1,I2,I4),而(I1,I2,I4)存在子集(I1,I4)不是频繁集。缩小了候选集。uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

第三轮得到的2个候选集,正好支持度等于**小支持度。所以,都算入频繁集。uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

这时再看第四轮的候选集与频繁集结果为空uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

可以看到,候选集和频繁集居然为空了!因为通过第三轮得到的频繁集自连接得到{I1,I2,I3,I5},它拥有子集{I2,I3,I5},而{I2,I3,I5}不是频繁集,不满足:频繁集的子集也是频繁集这一条件,所以被剪枝剪掉了。所以整个算法终止,取**后一次计算得到的频繁集作为**终的频繁集结果:uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

也就是:['I1,I2,I3', 'I1,I2,I5']uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

四、代码:uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

编写python代码实现Apriori算法。代码需要注意如下两点:uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

  • 由于Apriori算法假定项集中的项是按字典序排序的,而集合本身是无序的,所以我们在必要时需要进行set和list的转换;
  • 由于要使用字典(support_data)记录项集的支持度,需要用项集作为key,而可变集合无法作为字典的key,因此在合适时机应将项集转为固定集合frozenset。
def local_data(file_path):    import pandas as pd

    dt = pd.read_excel(file_path)
    data = dt['con']
    locdata = []    for i in data:
        locdata.append(str(i).split(","))   # print(locdata)  # change to [[1,2,3],[1,2,3]]
    length = []    for i in locdata:
        length.append(len(i))  # 计算长度并存储
   # print(length)
    ki = length[length.index(max(length))]   # print(length[length.index(max(length))])  # length.index(max(length)读取**大值的位置,然后再定位取出**大值

    return locdata,kidef create_C1(data_set):    """
    Create frequent candidate 1-itemset C1 by scaning data set.
    Args:
        data_set: A list of transactions. Each transaction contains several items.
    Returns:
        C1: A set which contains all frequent candidate 1-itemsets    """
    C1 = set()    for t in data_set:        for item in t:
            item_set = frozenset([item])
            C1.add(item_set)    return C1def is_apriori(Ck_item, Lksub1):    """
    Judge whether a frequent candidate k-itemset satisfy Apriori property.
    Args:
        Ck_item: a frequent candidate k-itemset in Ck which contains all frequent
                 candidate k-itemsets.
        Lksub1: Lk-1, a set which contains all frequent candidate (k-1)-itemsets.
    Returns:
        True: satisfying Apriori property.
        False: Not satisfying Apriori property.    """
    for item in Ck_item:
        sub_Ck = Ck_item - frozenset([item])        if sub_Ck not in Lksub1:            return False    return Truedef create_Ck(Lksub1, k):    """
    Create Ck, a set which contains all all frequent candidate k-itemsets
    by Lk-1's own connection operation.
    Args:
        Lksub1: Lk-1, a set which contains all frequent candidate (k-1)-itemsets.
        k: the item number of a frequent itemset.
    Return:
        Ck: a set which contains all all frequent candidate k-itemsets.    """
    Ck = set()
    len_Lksub1 = len(Lksub1)
    list_Lksub1 = list(Lksub1)    for i in range(len_Lksub1):        for j in range(1, len_Lksub1):
            l1 = list(list_Lksub1[i])
            l2 = list(list_Lksub1[j])
            l1.sort()
            l2.sort()            if l1[0:k-2] == l2[0:k-2]:
                Ck_item = list_Lksub1[i] | list_Lksub1[j]                # pruning
                if is_apriori(Ck_item, Lksub1):
                    Ck.add(Ck_item)    return Ckdef generate_Lk_by_Ck(data_set, Ck, min_support, support_data):    """
    Generate Lk by executing a delete policy from Ck.
    Args:
        data_set: A list of transactions. Each transaction contains several items.
        Ck: A set which contains all all frequent candidate k-itemsets.
        min_support: The minimum support.
        support_data: A dictionary. The key is frequent itemset and the value is support.
    Returns:
        Lk: A set which contains all all frequent k-itemsets.    """
    Lk = set()
    item_count = {}    for t in data_set:        for item in Ck:            if item.issubset(t):                if item not in item_count:
                    item_count[item] = 1                else:
                    item_count[item] += 1
    t_num = float(len(data_set))    for item in item_count:        if (item_count[item] / t_num) >= min_support:
            Lk.add(item)
            support_data[item] = item_count[item] / t_num    return Lkdef generate_L(data_set, k, min_support):    """
    Generate all frequent itemsets.
    Args:
        data_set: A list of transactions. Each transaction contains several items.
        k: Maximum number of items for all frequent itemsets.
        min_support: The minimum support.
    Returns:
        L: The list of Lk.
        support_data: A dictionary. The key is frequent itemset and the value is support.    """
    support_data = {}
    C1 = create_C1(data_set)
    L1 = generate_Lk_by_Ck(data_set, C1, min_support, support_data)
    Lksub1 = L1.copy()
    L = []
    L.append(Lksub1)    for i in range(2, k+1):
        Ci = create_Ck(Lksub1, i)
        Li = generate_Lk_by_Ck(data_set, Ci, min_support, support_data)
        Lksub1 = Li.copy()
        L.append(Lksub1)    return L, support_datadef generate_big_rules(L, support_data, min_conf):    """
    Generate big rules from frequent itemsets.
    Args:
        L: The list of Lk.
        support_data: A dictionary. The key is frequent itemset and the value is support.
        min_conf: Minimal confidence.
    Returns:
        big_rule_list: A list which contains all big rules. Each big rule is represented
                       as a 3-tuple.    """
    big_rule_list = []
    sub_set_list = []    for i in range(0, len(L)):        for freq_set in L[i]:            for sub_set in sub_set_list:                if sub_set.issubset(freq_set):
                    conf = support_data[freq_set] / support_data[freq_set - sub_set]
                    big_rule = (freq_set - sub_set, sub_set, conf)                    if conf >= min_conf and big_rule not in big_rule_list:                        # print freq_set-sub_set, " => ", sub_set, "conf: ", conf                        big_rule_list.append(big_rule)
            sub_set_list.append(freq_set)    return big_rule_listif __name__ == "__main__":    """
    Test    """
    file_path = "test_aa.xlsx"
  
    data_set,k = local_data(file_path)
    L, support_data = generate_L(data_set, k, min_support=0.2)
    big_rules_list = generate_big_rules(L, support_data, min_conf=0.4)    print(L)    for Lk in L:        if len(list(Lk)) == 0:            break
        print("="*50)        print("frequent " + str(len(list(Lk)[0])) + "-itemsets		support")        print("="*50)        for freq_set in Lk:            print(freq_set, support_data[freq_set])    print()    print("Big Rules")    for item in big_rules_list:        print(item[0], "=>", item[1], "conf: ", item[2]) 

文件格式:uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

test_aa.xlsxuxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

name    con
T1     2,3,5T2     1,2,4T3     3,5T5     2,3,4T6     2,3,5T7     1,2,4T8     3,5T9     2,3,4T10    1,2,3,4,5

相关免费学习推荐:python视频教程uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

以上就是如何理解关联规则apriori算法的详细内容,更多请关注少儿编程网其它相关文章!uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

来源:php中文网uxO少儿编程网-Scratch_Python_教程_免费儿童编程学习平台


相关文章:

支持一下 ( )

如何理解关联规则apriori算法

      匿名评论
    • 评论
    人参与,条评论
    如何理解关联规则apriori算法

微信公众号

免费视频教程

先知道