백엔드 개발 파이썬 튜토리얼 数据挖掘之Apriori算法详解和Python实现代码分享

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

Jun 10, 2016 pm 03:19 PM
선험적 알고리즘 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으로 문의하세요.

뜨거운 기사 태그

메모장++7.3.1

메모장++7.3.1

사용하기 쉬운 무료 코드 편집기

SublimeText3 중국어 버전

SublimeText3 중국어 버전

중국어 버전, 사용하기 매우 쉽습니다.

스튜디오 13.0.1 보내기

스튜디오 13.0.1 보내기

강력한 PHP 통합 개발 환경

드림위버 CS6

드림위버 CS6

시각적 웹 개발 도구

SublimeText3 Mac 버전

SublimeText3 Mac 버전

신 수준의 코드 편집 소프트웨어(SublimeText3)

템플릿의 장점과 단점은 무엇입니까? 템플릿의 장점과 단점은 무엇입니까? May 08, 2024 pm 03:51 PM

템플릿의 장점과 단점은 무엇입니까?

Google AI, 개발자를 위한 Gemini 1.5 Pro 및 Gemma 2 발표 Google AI, 개발자를 위한 Gemini 1.5 Pro 및 Gemma 2 발표 Jul 01, 2024 am 07:22 AM

Google AI, 개발자를 위한 Gemini 1.5 Pro 및 Gemma 2 발표

DeepSeek Xiaomi를 다운로드하는 방법 DeepSeek Xiaomi를 다운로드하는 방법 Feb 19, 2025 pm 05:27 PM

DeepSeek Xiaomi를 다운로드하는 방법

단 250달러에 Hugging Face의 기술 디렉터가 Llama 3를 단계별로 미세 조정하는 방법을 알려드립니다. 단 250달러에 Hugging Face의 기술 디렉터가 Llama 3를 단계별로 미세 조정하는 방법을 알려드립니다. May 06, 2024 pm 03:52 PM

단 250달러에 Hugging Face의 기술 디렉터가 Llama 3를 단계별로 미세 조정하는 방법을 알려드립니다.

여러 .NET 오픈 소스 AI 및 LLM 관련 프로젝트 프레임워크 공유 여러 .NET 오픈 소스 AI 및 LLM 관련 프로젝트 프레임워크 공유 May 06, 2024 pm 04:43 PM

여러 .NET 오픈 소스 AI 및 LLM 관련 프로젝트 프레임워크 공유

golang 함수 디버깅 및 분석에 대한 완벽한 가이드 golang 함수 디버깅 및 분석에 대한 완벽한 가이드 May 06, 2024 pm 02:00 PM

golang 함수 디버깅 및 분석에 대한 완벽한 가이드

당신은 그에게 Deepseek에게 어떻게 물어 봐요 당신은 그에게 Deepseek에게 어떻게 물어 봐요 Feb 19, 2025 pm 04:42 PM

당신은 그에게 Deepseek에게 어떻게 물어 봐요

평가 기능을 저장하는 방법 평가 기능을 저장하는 방법 May 07, 2024 am 01:09 AM

평가 기능을 저장하는 방법

See all articles