数据挖掘实验报告：Apriori算法实现_apriori算法实验心得

数据挖掘实验报告

实验一：Apriori算法实现

一、Apriori算法简介

​ Apriori算法是经典的挖掘频繁项集和关联规则的数据挖掘算法。A priori在拉丁语中指"来自以前"。当定义问题时，通常会使用先验知识或者假设，这被称作"一个先验"（a priori）。Apriori算法的名字正是基于这样的事实：算法使用频繁项集性质的先验性质，即频繁项集的所有非空子集也一定是频繁的。Apriori算法使用一种称为逐层搜索的迭代方法，其中k项集用于探索$(k+1)$项集。首先，通过扫描数据库，累计每个项的计数，并收集满足最小支持度的项，找出频繁1项集的集合。该集合记为$L_1$。然后，使用$L_1$找出频繁2项集的集合$L_2$，使用$L_2$找出$L_3$，如此下去，直到不能再找到频繁k项集。每找出一个$L_k$需要一次数据库的完整扫描。Apriori算法使用频繁项集的先验性质来压缩搜索空间。

二、基本概念

• 项与项集：设$itemset=ite{m}_1,ite{m}_2,\dots ,ite{m}_m$是所有项的集合，其中，$ite{m}_k,(k=1,2,\dots ,m)$称为项。项的集合称为项集$（itemset）$，包含k个项的项集称为k项集$(k-itemset)$。

• 事务与事务集：一个事务T是一个项集，它是itemset的一个子集，每个事务均与一个唯一标识符Tid相联系。不同的事务一起组成了事务集D，它构成了关联规则发现的事务数据库。

• 关联规则：关联规则是形如$A\Rightarrow B$的蕴涵式，其中A、B均为$itemset$的子集且均不为空集，而A交B为空。

• 支持度（support）：关联规则的支持度定义为
  $$support(A\Rightarrow B)=P(A\cup B)$$
  其中$P(A\cup B)$表示事务包含集合A和B的并的概率。

• 置信度（confidence）：关联规则的置信度定义为：
  $$confidence(A\Rightarrow B)=P(B|A)=\frac{support(A\cup B)}{support(A)}=\frac{support\_count(A\cup B)}{support\_count(A)}$$

• 项集的出现频度（support count）：包含项集的事务数，简称为项集的频度、支持度计数或计数。

• 频繁项集（frequent itemset）：如果项集$I$的相对支持度满足事先定义好的最小支持度阈值（即$I$的出现频度大于相应的最小出现频度（支持度计数）阈值），则$I$是频繁项集。

• 强关联规则：满足最小支持度和最小置信度的关联规则，即待挖掘的关联规则。

三、实现步骤

​ 一般而言，关联规则的挖掘是一个两步过程：1.找出所有的频繁项集。2.由频繁项集产生强关联规则。

1.挖掘频繁项集

1）相关定义

• 连接步骤：频繁$k-1$项集$L_{k-1}$的自身连接产生候选k项集$C_k$
  Apriori算法假定项集中的项按照字典序排序。如果$L_{k-1}$中某两个的元素（项集）$itemse{t}_1$和$itemse{t}_2$的前$k-2$个项是相同的，则称$itemse{t}_1$和$itemse{t}_2$是可连接的。所以$itemse{t}_1$与$itemse{t}_2$连接产生的结果项集是{$itemset_1[1], $itemse{t}_1[2]$, …, $itemse{t}_1[k-1]$,$ itemset_2[k-1]$}。连接步骤包含在下文代码中的create_Ck函数中。

• 剪枝策略
  由于存在先验性质：任何非频繁的$k-1$项集都不是频繁$k$项集的子集。因此，如果一个候选$k$项集$C_k$的$k-1$项子集不在$L_{k-1}$中，则该候选也不可能是频繁的，从而可以从$C_k$中删除，获得压缩后的$C_k$。下文代码中的is_apriori函数用于判断是否满足先验性质，create_Ck函数中包含剪枝步骤，即若不满足先验性质，剪枝。

• 删除策略
  基于压缩后的$C_k$，扫描所有事务，对$C_k$中的每个项进行计数，然后删除不满足最小支持度的项，从而获得频繁$k$项集。删除策略包含在下文代码中的generate_Lk_by_Ck函数中。

2）步骤

（1）每个项都是候选$1$项集的集合$C_1$的成员。算法扫描所有的事务，获得每个项，生成$C_1$（见下文代码中的create_C1函数）。然后对每个项进行计数。然后根据最小支持度从$C_1$中删除不满足的项，从而获得频繁$1$项集$L_1$。

（2）对$L_1$的自身连接生成的集合执行剪枝策略产生候选$2$项集的集合$C_2$，然后，扫描所有事务，对$C_2$中每个项进行计数。同样的，根据最小支持度从$C_2$中删除不满足的项，从而获得频繁$2$项集$L_2$。

（3）对$L_2$的自身连接生成的集合执行剪枝策略产生候选$3$项集的集合$C_3$，然后，扫描所有事务，对$C_3$每个项进行计数。同样的，根据最小支持度从$C_3$中删除不满足的项，从而获得频繁$3$项集$L_3$。

（4）以此类推，对$L_{k-1}$的自身连接生成的集合执行剪枝策略产生候选$k$项集$C_k$，然后，扫描所有事务，对$C_k$中的每个项进行计数。然后根据最小支持度从$C_k$中删除不满足的项，从而获得频繁$k$项集。

2.由频繁项集产生关联规则

​ 一旦找出了频繁项集，就可以直接由它们产生强关联规则。产生步骤如下：

• 对于每个频繁项集itemset，产生itemset的所有非空子集（这些非空子集一定是频繁项集）。
• 对于itemset的每个非空子集$s$，如果$\frac{support\_count(l)}{support\_count(s)}\ge min\_conf$，则输出$s\Rightarrow (l-s)$，其中$min\_conf$是最小置信度阈值。

四、Python实现代码

​ 《数据挖掘：概念与技术》（第三版）中挖掘频繁项集的样例图解。本实验基于该样例的数据编写Python代码实现Apriori算法。

def load_data_set():
    """
加载一个样本数据集（来自数据挖掘:概念和技术，第3版）
返回:
数据集:事务列表。每个事务都包含若干项。
    """
    data_set = [['l1', 'l2', 'l5'], ['l2', 'l4'], ['l2', 'l3'],
            ['l1', 'l2', 'l4'], ['l1', 'l3'], ['l2', 'l3'],
            ['l1', 'l3'], ['l1', 'l2', 'l3', 'l5'], ['l1', 'l2', 'l3']]
    return data_set


def create_C1(data_set):
    """
通过扫描数据集创建频繁候选1-itemset C1。
参数:
data_set:事务列表。每个事务都包含若干项。
返回:
C1:包含所有频繁候选1-项目集的集合
    """
    C1 = set()
    for t in data_set:
        for item in t:
            item_set = frozenset([item])
            C1.add(item_set)
    return C1


def is_apriori(Ck_item, Lksub1):
    """
判断频繁候选k-项集是否满足Apriori性质。
参数:
Ck_item: Ck中的一个频繁候选k-itemset，它包含所有的频繁项
k-itemsets候选人。
Lksub1: Lk-1，一个包含所有频繁候选(k-1)项集的集合。
返回:
真:满足Apriori性质。
错误:不满足Apriori性质。
    """
    for item in Ck_item:
        sub_Ck = Ck_item - frozenset([item])
        if sub_Ck not in Lksub1:
            return False
    return True


def create_Ck(Lksub1, k):
    """
创建Ck，一个包含所有频繁候选k-itemset的集合
通过Lk-1自己的连接操作。
参数:
Lksub1: Lk-1，一个包含所有频繁候选(k-1)项集的集合。
k:频繁项目集的项目号。
返回:
Ck:包含所有频繁候选k-itemset的集合。
    """
    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 Ck


def generate_Lk_by_Ck(data_set, Ck, min_support, support_data):
    """
通过从Ck执行删除策略来生成Lk。
参数:
data_set:事务列表。每个事务都包含若干项。
Ck:包含所有频繁候选k-itemset的集合。
min_support:最小支持度。
support_data:一个字典。关键字为“frequent itemset”，取值为“support”。
返回:
Lk:包含所有频繁k-itemset的集合。
    """
    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 Lk


def generate_L(data_set, k, min_support):
    """
生成所有频繁项集。
参数:
data_set:事务列表。每个事务都包含若干项。
k:所有频繁项目集的最大项目数量。
min_support:最小支持度。
返回:
L: Lk的名单。
support_data:一个字典。关键字为“frequent itemset”，取值为“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_data


def generate_big_rules(L, support_data, min_conf):
    """
从频繁项目集生成强规则。
参数:
L: Lk的名单。
support_data:一本字典。关键字为“frequent itemset”，取值为“support”。
min_conf:最小的置信度。
返回:
big_rule_list:包含所有大规则的列表。每个大规则都表示为一个3元组。
    """
    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:
                        big_rule_list.append(big_rule)
            sub_set_list.append(freq_set)
    return big_rule_list


if __name__ == "__main__":
    """
    Test
    """
    data_set = load_data_set()
    L, support_data = generate_L(data_set, k=3, min_support=0.2)
    big_rules_list = generate_big_rules(L, support_data, min_conf=0.7)
    for Lk in L:
        print "="*50
        print "frequent " + str(len(list(Lk)[0])) + "-itemsets\t\tsupport"
        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]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167

五、实验结果

​ 代码运行结果如下图：