利用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
CSDN博客

责编内容by:CSDN博客阅读原文】。感谢您的支持!

您可能感兴趣的

没有价值观的算法下岗了,但我希望算法能快快长大... 本文首发于百家号,原创文章,未经授权,请勿转载。 航通社 ( ID:lifeissohappy ) 微博: @lishuhang ...
Algorithms: Gray Binary Code – A different w... Gray binary code is a way of expressing binary numbers such that consecut...
基于最大主曲率算法和欧氏距离的指静脉识别 —–附带源码和解析文档... 暑假了就有时间写写博客了,大一的师弟们也要进入算法的领域了,于是我就写了一个简略版基于最大主曲率算法的指静脉识别给他们入门用, 现在图像识别的领域是越来越完...
亲属术语以及其算法 美国人的亲属术语非常简单. Read就研究过它的代数结构. 所有的人只有2个维度: 最近的祖先的辈分以及辈分区别. 只要这几个维度一样, 美国的...
算法系列–二叉树的三种遍历的六种实现... 0. 二叉树是常见的数据结构,二叉树常见的遍历方式有前序遍历,中序遍历和后序遍历。前序遍历就是中-左-右节点的顺序,中序遍历就是左-中-右节点的顺序,后序遍...