利用Apriori算法进行关联分析

综合技术 2017-08-19

1. Apriori算法

Apriori算法是一种挖掘关联规则的频繁项集算法,这些关系有两种形式 : 频繁项集和关联规则。

举个例子就知道了:著名的”尿布与啤酒”。

这就是通过关联分析来获取到的结果。

2. 名词解释

前后文中存在的名词都放在这里了

1. 频繁项集 : 在事件集合中出现频繁的项目

2. 关联规则 : 尿布-啤酒 关联等等 说明有很大的几率同时出现

3. 支持度:该项出现的次数/数据集的大小

4. 置信度:对于尿布-啤酒这一关联 置信度的定义 支持度(尿布与啤酒)/支持度(尿布)

一般的,A-B置信度 : conf(A-B) = support(AB)/support(A),这也是关联规则中很重要的依靠的一个数据

3. 主要算法伪代码以及思想

主要思想

  • 先计算各项的支持度,然后计算其置信度,如果直接运算如此多的数据,会有很大的计算开销,那么这时候你就要给算法一个阈值或者说是支持度置信度最小值,如果比这个值小就在后续中“剪”掉,这样一来就会节省很多时间………
  • 所谓的Apriori原理,是说如果一个项是频繁的,那么他的子集也是频繁的,看他的逆否命题:一个项非频繁,那么他的超集也是非频繁的……是不是很有道理……例如:{{0},{1}}频繁 , 那么{0},{1}也频繁;如果{0}非频繁,那么{{0},{1}}就是非频繁……..或者把01换成实际生活中盒装奶与吸管…..理解一下…..

优缺点

优点 : 算法简单

缺点:数据过大运算量大

伪代码

# 1. scanData 生成频繁项集
for 数据集中的每条交易记录item:
    for 每个候选项集elem:
        检查elem是否是item的子集
        如果是,则增加elem的计数
for 每个候选项集:
    如果其支持度不低于最小值,则保留该项集以及支持度
返回所有频繁项集列表以及对应支持度列表

# 2. AprioriGen 生成候选项集
for i-len(频繁项集)
    for i+1-len(频繁项集)
        合并操作
返回候选集

# 3. Apriori 算法
当频繁项集中的项的个数大于0时:
    生成候选集(AprioriGen 函数)
    计算候选项集的支持度,删除非频繁项集
    生成频繁项集(scanData 函数)
返回频繁项集以及对应支持度

# 4. 关联规则挖掘见代码注释...

4. 代码

# coding:utf-8

from numpy import *


def loadSimpleData():
    return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5]]


def creatC1(data):  # 创建一个候选集合 其中包含几个size为1的小集合
    c1 = []  # python不允许一个集合只包含一个数字 所以用list代替 [[],[],[],[]]
    for item in data:  # for "账单"条目
        for elem in item:  # for 条目的每个元素
            if [elem] not in c1:
                c1.append([elem])
    c1.sort()  # sort to 123...
    return map(frozenset, c1)  # frozen意为冻住的,返回一个不可更改的list


def scanData(data, Ck, minSupport):  # creat Lk from Ck (L代表频繁集 C代表候选集)
    appearNum = {}  # 记录候选集在数据中出现的次数
    for item in data:  # for 数据条目
        for elem in Ck:  # for 候选集元素
            if elem.issubset(item):  # 如果候选集出现在条目中
                if not appearNum.has_key(elem):  # 计数操作
                    appearNum[elem] = 1
                else:
                    appearNum[elem] += 1
    sum = float(len(data))  # 数据总条目数 float
    Lk = []  # LK记录
    supportData = {}  # 支持度的list
    for elem in appearNum:
        support = appearNum[elem] / sum  # 计算支持度
        if support >= minSupport:  # 打擂台 并且记录
            Lk.append(elem)
            supportData[elem] = support
    return Lk, supportData  # 返回频繁项集 以及 支持度


def AprioriGen(Lk, k):  # creat Ck+1 form Lk
    Ck = []
    lenLk = len(Lk)
    for i in range(lenLk):
        for j in range(i + 1, lenLk):  # 合并的过程很巧妙
            l1 = list(Lk[i])[:k - 2]  # 例如过程 [0] [1] [2] -> [01] [02] [12] -> [012]
            l2 = list(Lk[j])[:k - 2]  # [01][02][12]直接合并会出现3组[012]需要去重
            l1.sort()  # 而利用k-2这个筛选条件就只会出现 01|02 -> 012 这一种情况,以此类推
            l2.sort()
            if l1 == l2:
                Ck.append(Lk[i] | Lk[j])  # 集合并集
    return Ck  # 返回候选集


def Apriori(data, minSupport=0.5):  # minSupport is default 0.5
    c1 = creatC1(data)
    D = map(set, data)  # 内部去重 例如[1,1,2]->[1,2] ?
    L1, supportData = scanData(data, c1, minSupport)
    L = [L1]  # L集合存放了长度为i的频繁项集
    k = 2  # k=2 设计很巧妙
    while len(L[k - 2]) > 0:
        Ck = AprioriGen(L[k - 2], k)  # 从LK 生成 CK
        Lk, supportLK = scanData(D, Ck, minSupport)
        supportData.update(supportLK)
        L.append(Lk)  # 频繁项添加
        k += 1
    return L, supportData


def generateRules(L, supportData, minConf=0.7):  # 生成一定置信度的关联组合
    bigRuleList = []
    for i in range(1, len(L)):  # 只得到大于两元素的集合
        for freqSet in L[i]:
            H1 = [frozenset([item]) for item in freqSet]  # 拆分每个频繁项
            ''' 理解注释 '''
            # print "index is :", i
            # print "freqSet :", freqSet
            # print "H1 :", H1
            ''' 理解注释 '''
            if i > 1: # 如果大于两个元素 需要进一步关联规则生成以及判断置信度
                rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConf)
            else: # 如果只是两个元素 直接判断其置信度
                # print "+ + + + + generateRules else begin + + + + +"
                calcConf(freqSet, H1, supportData, bigRuleList, minConf)
                # print "+ + + + + generateRules else end + + + + +"
            # print 'bigRuleList is :', bigRuleList, 'n-------------------------- generateRules for end ---------------------------------------------------'
    return bigRuleList


def calcConf(freqSet, H, supportData, bigRuleList, minConf=0.7):  # 计算其 freq->H的置信度
    Hmp1 = []  # 返回置信度符合条件的H
    for elem in H:
        conf = supportData[freqSet] / supportData[freqSet - elem]  # 计算置信度 利用了集合减法
        if conf >= minConf:
            print freqSet - elem, '-->', elem, 'conf:', conf
            bigRuleList.append((freqSet - elem, elem, conf))
            Hmp1.append(elem)  # 此时不满足条件不会加入list 因为其超集也不会频繁
    return Hmp1


def rulesFromConseq(freqSet, H, supportData, bigRuleList, minConf=0.7):  # 生成关联规则
    m = len(H[0])
    ''' 理解注释 '''
    # print "---------  +  + +  rulesFromConseq  + +   +  -----------"
    # print "H0 is :", H[0]
    # print "m is :", m
    # print "freqSet is :", len(freqSet)

    # 为什么len > m+1呢 简单来说 既要生成CK+1 又不能和freqSet长度相等(以防无法进行关联计算freqSet->H)
    # 4个元素的关联规则 len:2->2,1->3 (本文 递归执行)
    # 消除注释可见过程
    ''' 理解注释 '''
    if len(freqSet) > (m + 1):
        Hmp1 = AprioriGen(H, m + 1)  # 生成Hm+1(Hm plus 1)的Cm+1 来进行关联分析
        Hmp1 = calcConf(freqSet, Hmp1, supportData, bigRuleList, minConf)
        if len(Hmp1) > 1:  # 满足条件 递归
            rulesFromConseq(freqSet, Hmp1, supportData, bigRuleList, minConf)


if __name__ == '__main__':
    data = loadSimpleData()
    c1 = creatC1(data)
    L, support = Apriori(data, 0.5)
    rules = generateRules(L, support, 0.5)
    print '----'
    for x in rules:
        print x

您可能感兴趣的

算法系列——调整数组顺序使奇数位于偶数前面... 题目描述 输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。 解题思路 提供以下下两种方法 相对位置不发生变化可以创建两个数组,分别存储原数组中奇数和...
We need to talk about mathematical backdoors in en... Security researchers regularly set out to find implementation problems in cryptographic algorithms, but not enough effort is going in comparison is be...
Difference between Flowchart and Algorithm Welcome back readers, today I’ll be discussing the difference between flowchart and algorithm. But before getting started, I want to discuss a bit abo...
《深度学习Ng》课程学习笔记02week2——优化算法... 2.1 Mini-batch 梯度下降法 2.2 理解 mini-batch 梯度下降法 2.3 指数加权平均 对温度做指数加权平均曲线: β = 0.98 时,会得到更加平缓的曲线,如图绿色。 β = 0.5 时,会得...
九章算法 – 秋季校招备战指南(国内IT技术岗位)... 专栏 | 九章算法 一、校招求职路径包括三种不同的方式 实习转正:包括少量面试到实习反馈,最终到转正面试 正常秋招:包括笔试,技术面试,其他面试 内推:比正常秋招少一个笔试 实习转正是求职最好的途径,第一,在正常招聘中,面试轮数有限,因此,能完全展示自...