首页 后端开发 Python教程 数据挖掘之Apriori算法详解和Python实现代码分享

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

Jun 10, 2016 pm 03:19 PM
apriori算法 python 数据挖掘

关联规则挖掘(Association rule mining)是数据挖掘中最活跃的研究方法之一,可以用来发现事情之间的联系,最早是为了发现超市交易数据库中不同的商品之间的关系。(啤酒与尿布)

基本概念

1、支持度的定义:support(X-->Y) = |X交Y|/N=集合X与集合Y中的项在一条记录中同时出现的次数/数据记录的个数。例如:support({啤酒}-->{尿布}) = 啤酒和尿布同时出现的次数/数据记录数 = 3/5=60%。

2、自信度的定义:confidence(X-->Y) = |X交Y|/|X| = 集合X与集合Y中的项在一条记录中同时出现的次数/集合X出现的个数 。例如:confidence({啤酒}-->{尿布}) = 啤酒和尿布同时出现的次数/啤酒出现的次数=3/3=100%;confidence({尿布}-->{啤酒}) = 啤酒和尿布同时出现的次数/尿布出现的次数 = 3/4 = 75%

同时满足最小支持度阈值(min_sup)和最小置信度阈值(min_conf)的规则称作强规则 ,如果项集满足最小支持度,则称它为频繁项集

“如何由大型数据库挖掘关联规则?”关联规则的挖掘是一个两步的过程:

1、找出所有频繁项集:根据定义,这些项集出现的频繁性至少和预定义的最小支持计数一样。
2、由频繁项集产生强关联规则:根据定义,这些规则必须满足最小支持度和最小置信度。

Apriori定律

为了减少频繁项集的生成时间,我们应该尽早的消除一些完全不可能是频繁项集的集合,Apriori的两条定律就是干这事的。

Apriori定律1:如果一个集合是频繁项集,则它的所有子集都是频繁项集。举例:假设一个集合{A,B}是频繁项集,即A、B同时出现在一条记录的次数大于等于最小支持度min_support,则它的子集{A},{B}出现次数必定大于等于min_support,即它的子集都是频繁项集。

Apriori定律2:如果一个集合不是频繁项集,则它的所有超集都不是频繁项集。举例:假设集合{A}不是频繁项集,即A出现的次数小于min_support,则它的任何超集如{A,B}出现的次数必定小于min_support,因此其超集必定也不是频繁项集。

上面的图演示了Apriori算法的过程,注意看由二级频繁项集生成三级候选项集时,没有{牛奶,面包,啤酒},那是因为{面包,啤酒}不是二级频繁项集,这里利用了Apriori定理。最后生成三级频繁项集后,没有更高一级的候选项集,因此整个算法结束,{牛奶,面包,尿布}是最大频繁子集。

Python实现代码:

复制代码 代码如下:

Skip to content
Sign up Sign in This repository
Explore
Features
Enterprise
Blog
 Star 0  Fork 0 taizilongxu/datamining
 branch: master  datamining / apriori / apriori.py
hackerxutaizilongxu 20 days ago backup
1 contributor
156 lines (140 sloc)  6.302 kb RawBlameHistory  
#-*- encoding: UTF-8 -*-
#---------------------------------import------------------------------------
#---------------------------------------------------------------------------
class Apriori(object):

    def __init__(self, filename, min_support, item_start, item_end):
        self.filename = filename
        self.min_support = min_support # 最小支持度
        self.min_confidence = 50
        self.line_num = 0 # item的行数
        self.item_start = item_start #  取哪行的item
        self.item_end = item_end

        self.location = [[i] for i in range(self.item_end - self.item_start + 1)]
        self.support = self.sut(self.location)
        self.num = list(sorted(set([j for i in self.location for j in i])))# 记录item

        self.pre_support = [] # 保存前一个support,location,num
        self.pre_location = []
        self.pre_num = []

        self.item_name = [] # 项目名
        self.find_item_name()
        self.loop()
        self.confidence_sup()

    def deal_line(self, line):
        "提取出需要的项"
        return [i.strip() for i in line.split(' ') if i][self.item_start - 1:self.item_end]

    def find_item_name(self):
        "根据第一行抽取item_name"
        with open(self.filename, 'r') as F:
            for index,line in enumerate(F.readlines()):
                if index == 0:
                    self.item_name = self.deal_line(line)
                    break

    def sut(self, location):
        """
        输入[[1,2,3],[2,3,4],[1,3,5]...]
        输出每个位置集的support [123,435,234...]
        """
        with open(self.filename, 'r') as F:
            support = [0] * len(location)
            for index,line in enumerate(F.readlines()):
                if index == 0: continue
                # 提取每信息
                item_line = self.deal_line(line)
                for index_num,i in enumerate(location):
                    flag = 0
                    for j in i:
                        if item_line[j] != 'T':
                            flag = 1
                            break
                    if not flag:
                        support[index_num] += 1
            self.line_num = index # 一共多少行,出去第一行的item_name
        return support

    def select(self, c):
        "返回位置"
        stack = []
        for i in self.location:
            for j in self.num:
                if j in i:
                    if len(i) == c:
                        stack.append(i)
                else:
                    stack.append([j] + i)
        # 多重列表去重
        import itertools
        s = sorted([sorted(i) for i in stack])
        location = list(s for s,_ in itertools.groupby(s))
        return location

    def del_location(self, support, location):
        "清除不满足条件的候选集"
        # 小于最小支持度的剔除
        for index,i in enumerate(support):
            if i                 support[index] = 0
        # apriori第二条规则,剔除
        for index,j in enumerate(location):
            sub_location = [j[:index_loc] + j[index_loc+1:]for index_loc in range(len(j))]
            flag = 0
            for k in sub_location:
                if k not in self.location:
                    flag = 1
                    break
            if flag:
                support[index] = 0
        # 删除没用的位置
        location = [i for i,j in zip(location,support) if j != 0]
        support = [i for i in support if i != 0]
        return support, location

    def loop(self):
        "s级频繁项级的迭代"
        s = 2
        while True:
            print '-'*80
            print 'The' ,s - 1,'loop'
            print 'location' , self.location
            print 'support' , self.support
            print 'num' , self.num
            print '-'*80

            # 生成下一级候选集
            location = self.select(s)
            support = self.sut(location)
            support, location = self.del_location(support, location)
            num = list(sorted(set([j for i in location for j in i])))
            s += 1
            if  location and support and num:
                self.pre_num = self.num
                self.pre_location = self.location
                self.pre_support = self.support

                self.num = num
                self.location = location
                self.support = support
            else:
                break

    def confidence_sup(self):
        "计算confidence"
        if sum(self.pre_support) == 0:
            print 'min_support error' # 第一次迭代即失败
        else:
            for index_location,each_location in enumerate(self.location):
                del_num = [each_location[:index] + each_location[index+1:] for index in range(len(each_location))] # 生成上一级频繁项级
                del_num = [i for i in del_num if i in self.pre_location] # 删除不存在上一级频繁项级子集
                del_support = [self.pre_support[self.pre_location.index(i)] for i in del_num if i in self.pre_location] # 从上一级支持度查找
                # print del_num
                # print self.support[index_location]
                # print del_support
                for index,i in enumerate(del_num): # 计算每个关联规则支持度和自信度
                    index_support = 0
                    if len(self.support) != 1:
                        index_support = index
                    support =  float(self.support[index_location])/self.line_num * 100 # 支持度
                    s = [j for index_item,j in enumerate(self.item_name) if index_item in i]
                    if del_support[index]:
                        confidence = float(self.support[index_location])/del_support[index] * 100
                        if confidence > self.min_confidence:
                            print ','.join(s) , '->>' , self.item_name[each_location[index]] , ' min_support: ' , str(support) + '%' , ' min_confidence:' , str(confidence) + '%'

def main():
    c = Apriori('basket.txt', 14, 3, 13)
    d = Apriori('simple.txt', 50, 2, 6)

if __name__ == '__main__':
    main()
############################################################################
Status API Training Shop Blog About
© 2014 GitHub, Inc. Terms Privacy Security Contact

Apriori算法

Apriori(filename, min_support, item_start, item_end)

参数说明

filename:(路径)文件名
min_support:最小支持度
item_start:item起始位置
item_end:item结束位置

使用例子:

复制代码 代码如下:

import apriori
c = apriori.Apriori('basket.txt', 11, 3, 13)

输出:

复制代码 代码如下:

--------------------------------------------------------------------------------
The 1 loop
location [[0], [1], [2], [3], [4], [5], [6], [7], [8], [9], [10]]
support [299, 183, 177, 303, 204, 302, 293, 287, 184, 292, 276]
num [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
The 2 loop
location [[0, 9], [3, 5], [3, 6], [5, 6], [7, 10]]
support [145, 173, 167, 170, 144]
num [0, 3, 5, 6, 7, 9, 10]
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
The 3 loop
location [[3, 5, 6]]
support [146]
num [3, 5, 6]
--------------------------------------------------------------------------------
frozenmeal,beer ->> cannedveg  min_support:  14.6%  min_confidence: 0.858823529412
cannedveg,beer ->> frozenmeal  min_support:  14.6%  min_confidence: 0.874251497006
cannedveg,frozenmeal ->> beer  min_support:  14.6%  min_confidence: 0.843930635838
--------------------------------------------------------------------------------
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

Video Face Swap

Video Face Swap

使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸!

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

PHP和Python:解释了不同的范例 PHP和Python:解释了不同的范例 Apr 18, 2025 am 12:26 AM

PHP主要是过程式编程,但也支持面向对象编程(OOP);Python支持多种范式,包括OOP、函数式和过程式编程。PHP适合web开发,Python适用于多种应用,如数据分析和机器学习。

在PHP和Python之间进行选择:指南 在PHP和Python之间进行选择:指南 Apr 18, 2025 am 12:24 AM

PHP适合网页开发和快速原型开发,Python适用于数据科学和机器学习。1.PHP用于动态网页开发,语法简单,适合快速开发。2.Python语法简洁,适用于多领域,库生态系统强大。

Python vs. JavaScript:学习曲线和易用性 Python vs. JavaScript:学习曲线和易用性 Apr 16, 2025 am 12:12 AM

Python更适合初学者,学习曲线平缓,语法简洁;JavaScript适合前端开发,学习曲线较陡,语法灵活。1.Python语法直观,适用于数据科学和后端开发。2.JavaScript灵活,广泛用于前端和服务器端编程。

visual studio code 可以用于 python 吗 visual studio code 可以用于 python 吗 Apr 15, 2025 pm 08:18 PM

VS Code 可用于编写 Python,并提供许多功能,使其成为开发 Python 应用程序的理想工具。它允许用户:安装 Python 扩展,以获得代码补全、语法高亮和调试等功能。使用调试器逐步跟踪代码,查找和修复错误。集成 Git,进行版本控制。使用代码格式化工具,保持代码一致性。使用 Linting 工具,提前发现潜在问题。

vscode 扩展是否是恶意的 vscode 扩展是否是恶意的 Apr 15, 2025 pm 07:57 PM

VS Code 扩展存在恶意风险,例如隐藏恶意代码、利用漏洞、伪装成合法扩展。识别恶意扩展的方法包括:检查发布者、阅读评论、检查代码、谨慎安装。安全措施还包括:安全意识、良好习惯、定期更新和杀毒软件。

PHP和Python:深入了解他们的历史 PHP和Python:深入了解他们的历史 Apr 18, 2025 am 12:25 AM

PHP起源于1994年,由RasmusLerdorf开发,最初用于跟踪网站访问者,逐渐演变为服务器端脚本语言,广泛应用于网页开发。Python由GuidovanRossum于1980年代末开发,1991年首次发布,强调代码可读性和简洁性,适用于科学计算、数据分析等领域。

vs code 可以在 Windows 8 中运行吗 vs code 可以在 Windows 8 中运行吗 Apr 15, 2025 pm 07:24 PM

VS Code可以在Windows 8上运行,但体验可能不佳。首先确保系统已更新到最新补丁,然后下载与系统架构匹配的VS Code安装包,按照提示安装。安装后,注意某些扩展程序可能与Windows 8不兼容,需要寻找替代扩展或在虚拟机中使用更新的Windows系统。安装必要的扩展,检查是否正常工作。尽管VS Code在Windows 8上可行,但建议升级到更新的Windows系统以获得更好的开发体验和安全保障。

vscode怎么在终端运行程序 vscode怎么在终端运行程序 Apr 15, 2025 pm 06:42 PM

在 VS Code 中,可以通过以下步骤在终端运行程序:准备代码和打开集成终端确保代码目录与终端工作目录一致根据编程语言选择运行命令(如 Python 的 python your_file_name.py)检查是否成功运行并解决错误利用调试器提升调试效率

See all articles