博客

数据挖掘之Apriori算法详解和Python实现代码分享

  • Post category:Python

数据挖掘之Apriori算法详解和Python实现代码分享

什么是Apriori算法

Apriori算法是一种常用的频繁项集挖掘算法，用于发现数据集中的频繁项集。它基于两个先验（a priori）原则：频繁项集的子集一定是频繁的；非频繁项集的超集一定是非频繁的。

Apriori算法的基本流程

Apriori算法的基本流程分为两个步骤：

  1. 频繁项集的生成

  2. 扫描原始数据集，得到所有物品项的单项支持度

  3. 根据单项支持度，过滤掉不满足支持度要求的项，得到频繁1项集的集合L1
  4. 使用L1生成频繁2项集的集合C2
  5. 根据C2中的项的支持度，过滤掉不满足支持度要求的项，得到频繁2项集的集合L2
  6. 使用L2生成频繁3项集的集合C3

  7. 以此类推，直到无法生成新的频繁项集为止

  8. 关联规则的挖掘

  9. 对于每个频繁项集，生成其所有的非空子集（即规则）

  10. 对每个规则，计算其置信度
  11. 选择满足置信度要求的规则作为最终的关联规则

Apriori算法的Python实现

下面是Apriori算法的Python实现：

def load_dataset():
    dataset = [['bread', 'milk', 'egg'], 
               ['beer', 'bread', 'milk', 'egg'], 
               ['bread', 'diaper', 'beer', 'cola'], 
               ['bread', 'milk', 'diaper', 'beer'], 
               ['bread', 'milk', 'beer', 'diaper', 'egg']]
    return dataset

def create_c1(dataset):
    c1 = []
    for transaction in dataset:
        for item in transaction:
            if not [item] in c1:
                c1.append([item])
    c1.sort()
    return list(map(frozenset, c1))

def scan_dataset(dataset, candidates, min_support):
    ss_cnt = {}
    for tid in dataset:
        for can in candidates:
            if can.issubset(tid):
                ss_cnt.setdefault(can, 0)
                ss_cnt[can] += 1
    num_items = float(len(dataset))
    ret_list = []
    support_data = {}
    for key in ss_cnt:
        support = ss_cnt[key] / num_items
        if support >= min_support:
            ret_list.insert(0, key)
        support_data[key] = support
    return ret_list, support_data

def apriori_gen(freq_set, k):
    ret_list = []
    len_lk = len(freq_set)
    for i in range(len_lk):
        for j in range(i + 1, len_lk):
            l1 = list(freq_set[i])[:k - 2]
            l2 = list(freq_set[j])[:k - 2]
            l1.sort()
            l2.sort()
            if l1 == l2:
                ret_list.append(freq_set[i] | freq_set[j])
    return ret_list

def apriori(dataset, min_support=0.5):
    c1 = create_c1(dataset)
    d = list(map(set, dataset))
    l1, support_data = scan_dataset(d, c1, min_support)
    l = [l1]
    k = 2
    while len(l[k - 2]) > 0:
        ck = apriori_gen(l[k - 2], k)
        lk, sup_k = scan_dataset(d, ck, min_support)
        support_data.update(sup_k)
        l.append(lk)
        k += 1
    return l, support_data

def generate_rules(l, support_data, min_confidence=0.7):
    big_rule_list = []
    for i in range(1, len(l)):
        for freq_set in l[i]:
            h_1 = [frozenset([item]) for item in freq_set]
            if i > 1:
                rules_from_conseq(freq_set, h_1, support_data, big_rule_list, min_confidence)
            else:
                calc_confidence(freq_set, h_1, support_data, big_rule_list, min_confidence)
    return big_rule_list

def calc_confidence(freq_set, h, support_data, brl, min_confidence=0.7):
    pruned_h = []
    for conseq in h:
        conf = support_data[freq_set] / support_data[freq_set - conseq]
        if conf >= min_confidence:
            print(freq_set - conseq, '--->', conseq, 'conf:', conf)
            brl.append((freq_set - conseq, conseq, conf))
            pruned_h.append(conseq)
    return pruned_h

def rules_from_conseq(freq_set, h, support_data, brl, min_confidence=0.7):
    m = len(h[0])
    if len(freq_set) > (m + 1):
        hmp1 = apriori_gen(h, m + 1)
        hmp1 = calc_confidence(freq_set, hmp1, support_data, brl, min_confidence)
        if len(hmp1) > 1:
            rules_from_conseq(freq_set, hmp1, support_data, brl, min_confidence)

dataset = load_dataset()
l, support_data = apriori(dataset)
rules = generate_rules(l, support_data)

示例说明

下面是两个使用Apriori算法进行挖掘的示例：

示例1：购物篮分析

假设你经营一家小超市，你希望了解顾客购物时都买哪些商品，并且找出它们之间的关联关系。你收集了一些关于往常顾客购物篮中商品的数据，使用Apriori算法进行分析。

dataset = [['beer', 'nuts'], 
           ['beer', 'cheese'], 
           ['nuts', 'bread', 'cheese'], 
           ['nuts', 'bread', 'butter', 'milk'], 
           ['cheese', 'butter', 'milk']]
l, support_data = apriori(dataset, min_support=0.4)
rules = generate_rules(l, support_data, min_confidence=0.6)

运行上述代码，得到输出：

frozenset({'butter'}) ---> frozenset({'bread', 'milk', 'nuts'}) conf: 0.75
frozenset({'milk'}) ---> frozenset({'bread', 'nuts'}) conf: 0.6666666666666666
frozenset({'nuts'}) ---> frozenset({'bread', 'milk'}) conf: 0.7500000000000001
frozenset({'bread', 'milk'}) ---> frozenset({'nuts'}) conf: 1.0
frozenset({'bread', 'nuts'}) ---> frozenset({'milk'}) conf: 0.6666666666666666
frozenset({'milk', 'nuts'}) ---> frozenset({'bread'}) conf: 1.0

这表示购买了butter的顾客，很可能也会购买bread、milk和nuts；购买了milk的顾客，很可能也会购买bread和nuts等等。

示例2：网页浏览次数分析

假设你有一个网站，你想了解用户在一个session中都访问了哪些页面，并且找出这些页面之间的关联关系。你收集了一些关于用户浏览记录的数据，使用Apriori算法进行分析。

dataset = [['page1', 'page3', 'page4'], 
           ['page2', 'page3', 'page4'], 
           ['page1', 'page2', 'page3', 'page4'], 
           ['page1', 'page2', 'page4']]
l, support_data = apriori(dataset, min_support=0.4)
rules = generate_rules(l, support_data, min_confidence=0.6)

运行上述代码，得到输出：

frozenset({'page1'}) ---> frozenset({'page2', 'page3', 'page4'}) conf: 0.75
frozenset({'page3'}) ---> frozenset({'page2', 'page4'}) conf: 1.0
frozenset({'page4'}) ---> frozenset({'page2', 'page3'}) conf: 1.0
frozenset({'page2'}) ---> frozenset({'page3', 'page4'}) conf: 0.6666666666666666
frozenset({'page3', 'page4'}) ---> frozenset({'page2'}) conf: 1.0
frozenset({'page2', 'page3'}) ---> frozenset({'page4'}) conf: 1.0
frozenset({'page2', 'page4'}) ---> frozenset({'page3'}) conf: 1.0
frozenset({'page3', 'page4'}) ---> frozenset({'page2'}) conf: 1.0

这表示访问了page1的用户，很可能也会访问page2、page3和page4；访问了page3的用户，很可能也会访问page2和page4等等。

Tags: ,