0
  • 聊天消息
  • 系统消息
  • 评论与回复
登录后你可以
  • 下载海量资料
  • 学习在线课程
  • 观看技术视频
  • 写文章/发帖/加入社区
会员中心
创作中心

完善资料让更多小伙伴认识你,还能领取20积分哦,立即完善>

3天内不再提示

简介Apriori算法并解析该算法的具体策略和步骤,给出Python实现代码

lviY_AI_shequ 2018-01-31 15:04 次阅读

‍‍‍

随着大数据概念的火热,啤酒与尿布的故事广为人知。我们如何发现买啤酒的人往往也会买尿布这一规律?数据挖掘中的用于挖掘频繁项集和关联规则的Apriori算法可以告诉我们。本文首先对Apriori算法进行简介,而后进一步介绍相关的基本概念,之后详细的介绍Apriori算法的具体策略和步骤,最后给出Python实现代码。

1Apriori算法简介

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

2基本概念

项与项集:设itemset={item1, item_2, …, item_m}是所有项的集合,其中,item_k(k=1,2,…,m)成为项。项的集合称为项集(itemset),包含k个项的项集称为k项集(k-itemset)。

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

关联规则:关联规则是形如A=>B的蕴涵式,其中A、B均为itemset的子集且均不为空集,而A交B为空。

支持度(support):关联规则的支持度定义如下:

其中表示事务包含集合A和B的并(即包含A和B中的每个项)的概率。注意与P(A or B)区别,后者表示事务包含A或B的概率。

置信度(confidence):关联规则的置信度定义如下:

项集的出现频度(support count):包含项集的事务数,简称为项集的频度、支持度计数或计数。

频繁项集(frequent itemset):如果项集I的相对支持度满足事先定义好的最小支持度阈值(即I的出现频度大于相应的最小出现频度(支持度计数)阈值),则I是频繁项集。

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

3实现步骤

一般而言,关联规则的挖掘是一个两步的过程:

a. 找出所有的频繁项集

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

3.1挖掘频繁项集

3.1.1相关定义

连接步骤:频繁(k-1)项集Lk-1的自身连接产生候选k项集Ck

Apriori算法假定项集中的项按照字典序排序。如果Lk-1中某两个的元素(项集)itemset1和itemset2的前(k-2)个项是相同的,则称itemset1和itemset2是可连接的。所以itemset1与itemset2连接产生的结果项集是{itemset1[1], itemset1[2], …, itemset1[k-1], itemset2[k-1]}。连接步骤包含在下文代码中的create_Ck函数中。

剪枝策略

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

删除策略

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

3.1.2 步骤

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

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

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

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

3.2 由频繁项集产生关联规则

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

对于每个频繁项集itemset,产生itemset的所有非空子集(这些非空子集一定是频繁项集);

对于itemset的每个非空子集s,如果

4样例以及Python实现代码

下图是《数据挖掘:概念与技术》(第三版)中挖掘频繁项集的样例图解。

简介Apriori算法并解析该算法的具体策略和步骤,给出Python实现代码

本文基于该样例的数据编写Python代码实现Apriori算法。代码需要注意如下两点:

由于Apriori算法假定项集中的项是按字典序排序的,而集合本身是无序的,所以我们在必要时需要进行set和list的转换;

由于要使用字典(support_data)记录项集的支持度,需要用项集作为key,而可变集合无法作为字典的key,因此在合适时机应将项集转为固定集合frozenset。

"""

# Python 2.7

# Filename: apriori.py

# Author: llhthinker

# Email: hangliu56[AT]gmail[DOT]com

# Blog: http://www.cnblogs.com/llhthinker/p/6719779.html

# Date: 2017-04-16

"""

def load_data_set():

"""

Load a sample data set (From Data Mining: Concepts and Techniques, 3th Edition)

Returns:

A data set: A list of transactions. Each transaction contains several items.

"""

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):

"""

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 C1

def 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 True

def 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 Ck

def 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 Lk

def 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_data

def 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_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]

代码运行结果截图如下:

声明:本文内容及配图由入驻作者撰写或者入驻合作网站授权转载。文章观点仅代表作者本人,不代表电子发烧友网立场。文章及其配图仅供工程师学习之用,如有内容侵权或者其他违规问题,请联系本站处理。 举报投诉
  • Apriori算法
    +关注

    关注

    0

    文章

    14

    浏览量

    10562
  • python
    +关注

    关注

    56

    文章

    4795

    浏览量

    84661

原文标题:Apriori算法介绍(Python实现)

文章出处:【微信号:AI_shequ,微信公众号:人工智能爱好者社区】欢迎添加关注!文章转载请注明出处。

收藏 人收藏

    评论

    相关推荐

    PythonApriori算法和FP-Growth算法是什么

    [源码和文档分享]基于Python实现Apriori算法和FP-Growth算法的频繁项集挖掘的研究与
    发表于 06-04 12:49

    Apriori算法的一种优化方法

    介绍关联规则挖掘中的经典算法――Apriori算法的关键思想。针对传统Apriori算法效率上的不足,提出一种改进的
    发表于 04-10 08:48 19次下载

    一种新的改进的Apriori算法

    本文通过对关联规则挖掘算法Apriori 算法的分析和研究,指出了其在具体应用中存在的主要问题。提出与以往不同的改进策略:在约简数据库事务的
    发表于 12-25 12:59 11次下载

    一种基于矩阵压缩的Apriori优化算法

    挖掘关联规则是数据挖掘中一个重要的课题,产生频繁项集是其中的一个关键步骤。文章提出了一种基于矩阵压缩的Apriori 优化算法,并将该算法Apri
    发表于 12-25 14:21 9次下载

    基于关联规则的Apriori-Partition算法的可视化

    关联规则的提取是数据挖掘中的重要研究内容,对关联规则提取中的Apriori算法进行了分析与研究,针对该算法的运算效率不高,对该算法进行了优化。Partition
    发表于 01-15 13:51 15次下载

    一种新的改进Apriori算法

    通过对Apriori算法的核心思想进行研究分析,结合Apriori性质,对Apriori中连接的步骤进行了改进.通过该方法,可以有效地减少连
    发表于 10-21 16:31 0次下载

    关联规则Apriori算法的改进

    关联规则是数据挖掘研究的一个重要分支。Apriori算法是关联规则挖掘中最有影响的经典算法。本文在介绍了关联规则的概念,在分析Apriori算法
    发表于 05-13 16:37 0次下载

    数据挖掘Apriori算法的改进

    为了解决数据挖掘中关联规则Apriori算法存在的缺陷,提出了一种全新的基于对候选项集处理的改进算法该算法主要采用一次扫描数据库和对候选项集进行计数处理的方法,
    发表于 08-19 17:44 17次下载
    数据挖掘<b class='flag-5'>Apriori</b><b class='flag-5'>算法</b>的改进

    基于Apriori_Pro算法的辅助知识获取技术研究

    为了解决产生式规则专家系统知识获取难的问题,采用了一种新的Apriori Pro改进算法,并且将该算法成功的应用于火炮故障诊断专家系统中。实验结果显示改进后的Apriori
    发表于 12-21 10:19 9次下载

    蚁群算法matlab程序代码

    本文详细解析了关于蚁群算法matlab程序代码具体步骤请看下文。
    发表于 02-02 10:21 3.8w次阅读
    蚁群<b class='flag-5'>算法</b>matlab程序<b class='flag-5'>代码</b>

    蚁群算法python编程实现

    本文主要介绍了Python编程实现蚁群算法详解,涉及蚂蚁算法简介,主要原理及公式,以及Python
    发表于 02-02 10:36 7467次阅读
    蚁群<b class='flag-5'>算法</b><b class='flag-5'>python</b>编程<b class='flag-5'>实现</b>

    Matlab关于Apriori算法设计

    本文详细介绍了Matlab关于Apriori算法设计。Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法
    发表于 02-02 16:20 5129次阅读
    Matlab关于<b class='flag-5'>Apriori</b><b class='flag-5'>算法</b>设计

    Apriori算法详解

    本文主要是对Apriori算法的详解,包括了Apriori算法详细介绍概括和步骤Apriori
    发表于 02-02 16:35 2.1w次阅读
    <b class='flag-5'>Apriori</b><b class='flag-5'>算法</b>详解

    组合29个简单Python代码块,自动发现新算法

    本文提出了一种基于演化算法的搜索策略,将其AAD中实现。AAD可以基于Python的子集作为语法结构,组合成复杂度相对较高的程序(循环,嵌套块,嵌套函数调用等),
    的头像 发表于 04-19 13:47 3528次阅读

    [源代码]Python算法详解

    [源代码]Python算法详解[源代码]Python算法详解
    发表于 06-06 17:50 0次下载