机器学习算法-Apriori

发布于 25 天前  91 次阅读


关联分析(Apriori)

基本概念

项集

项集是指若干个项的集合

支持度

支持度定义为数据集中包含该项集的记录的比例,或者说几个数据关联出现的概率。如果我们有两个想分析关联性的数据X和Y,则对应的支持度为:
$$
Support(X,Y) = P(XY) = \frac{number(XY)}{num(All Samples)}
$$
以此类推,如果我们有三个想分析关联性的数据X,Y和Z,则对应的支持度为:
$$
Support(X,Y,Z) = P(XYZ) = \frac{number(XYZ)}{num(All Samples)}
$$

频繁项集

频繁项集是指支持度大于等于最小支持度的集合

置信度

置信度体现了一个数据出现后,另一个数据出现的概率,或者说数据的条件概率。如果我们有两个想分析关联性的数据X和Y,X对Y的置信度为:
$$
Confidence(X \Leftarrow Y) = P(X|Y)=\frac{P(XY)}{P(Y)}
$$

最小支持度

最小支持度:最小支持度就是人为按照实际意义规定的阈值,表示项集在统计意义上的最低重要性。

最小置信度

最小置信度:最小置信度也是人为按照实际意义规定的阈值,表示关联规则最低可靠性。

原理

如果某个项集是频繁的,那么它的子集也是频繁的,应用它的逆否命题,我们可以减少很多计算量

频繁项集算法

当集合中项大于0时:
    构建一个k个项组成的候选项集列表
    检查数据以确保每一个项集都是频繁的
    保留频繁项并构建k+1项组成的候选项的列表

关联项集算法

当k(k>=2)项候补集数目大于0时:
    对每一个k项数据集:
          计算1~k-1项数据集的支持度
          计算1~k-1项数据集的置信度

代码

# coding=gbk


def loaddataset():
    return [['豆奶', '莴苣'], ['豆奶', '尿布', '葡萄酒', '甜菜'], ['豆奶', '尿布', '葡萄酒', '橙汁'], ['豆奶', '尿布', '葡萄酒', '莴苣'],
            ['豆奶', '尿布', '橙汁', '莴苣']]


def create_c1(dataset):
    c1 = []
    for transaction in dataset:
        for item in transaction:
            if [item] not in c1:
                c1.append([item])
    c1.sort()
    return list(map(frozenset, c1))


def scan_d(d, ck, minsupport):
    sscnt = {}
    for tid in d:
        for can in ck:
            if can.issubset(tid):
                if can not in sscnt:
                    sscnt[can] = 1
                else:
                    sscnt[can] += 1
    numitems = float(len(d))
    retlist = []
    supportdata = {}
    for key in sscnt:
        support = sscnt[key] / numitems
        if support >= minsupport:
            retlist.insert(0, key)
        supportdata[key] = support
    return retlist, supportdata


def apriori_gen(lk, k):
    retlist = []
    lenlk = len(lk)
    for i in range(lenlk):
        for j in range(i + 1, lenlk):
            l1 = list(lk[i])[:k - 2]
            l2 = list(lk[j])[:k - 2]
            l1.sort()
            l2.sort()
            if l1 == l2:
                retlist.append(lk[i] | lk[j])
    return retlist


def apriori(dataset, minsupport=0.5):
    c1 = create_c1(data)
    d = list(map(set, data))
    l1, support = scan_d(d, c1, minsupport)
    l = [l1]
    k = 2
    while (len(l[k - 2]) > 0):
        ck = apriori_gen(l[k - 2], k)
        lk, supportk = scan_d(d, ck, minsupport)
        support.update(supportk)
        l.append(lk)
        k += 1
    return l, support


def calc_conf(freqset, h1, supportdata, bigrulelist, minconf=0.7):
    prunedh = []
    for conseq in h1:
        conf = supportdata[freqset] / supportdata[freqset - conseq]
        if conf >= minconf:
            print(freqset - conseq, '-->', conseq, 'conf', conf)
            bigrulelist.append((freqset - conseq, conseq, conf))
            prunedh.append(conseq)
    return prunedh


def rules_from_conseq(freqset, h1, supportdata, bigrulelist, minconf=0.7):
    m = len(h1[0])
    if (len(freqset)) > (m + 1):
        hmp1 = apriori_gen(h1, m + 1)
        hmp1 = calc_conf(freqset, hmp1, supportdata, bigrulelist, minconf)
        if len(hmp1) > 1:
            rules_from_conseq(freqset, hmp1, supportdata, bigrulelist, minconf)


def generate_rule(l, supportdata, minconf=0.7):
    big_rule_list = []
    for i in range(1, len(l)):
        for freq_set in l[i]:
            h1 = [frozenset([item]) for item in freq_set]
            if (i > 1):
                rules_from_conseq(freq_set, h1, supportdata, big_rule_list, minconf)
            else:
                calc_conf(freq_set, h1, supportdata, big_rule_list, minconf)
    return big_rule_list


if __name__ == "__main__":
    data = loaddataset()
    l, support = apriori(data)
    print(generate_rule(l, support, 0.8))

总结

说实话这个代码我自己写可能要花too much time,因为关键的连接步({0,1,2}->{(0,1),(1,2),(0,2)})就是很不好写,但是自己写伪代码应该是可以的,其实这个算法还存在一个提升度的概念,用来度量关联规则的价值,这都是深入了,以后遇到了会说的。


浪子三唱,不唱悲歌