使用Apriori算法进行关联分析

释放双眼,带上耳机,听听看~!

主要内容:Apriori算法、频繁项集生成、关联规则生成、投票中的关联规则发现

缺点:是在大数据集上可能较慢。

当寻找频繁项集时,有两个概念比较重要:
支持度和
可信度。

交易号码 商品
0 豆奶, 莴苣
1 莴苣,尿布,葡萄酒,甜菜
2 莴苣,尿布,葡萄酒,橙汁
3 莴苣,豆奶,尿布,葡萄酒
4 莴苣,豆奶,尿布,橙汁

1
1

支持度:一个项集的支持度(support)被定义为数据集中包含该项集的记录占总记录的比例。从表1 可以看出 项集 {豆奶} 的支持度为 4/5; 而在 5 条交易记录中 3 条包含 {豆奶,尿布},因此 {豆奶,尿布} 的支持度为 3/5.

可信度或置信度(confidence):是针对一条诸如尿布−−>葡萄酒尿布−−>葡萄酒的关联规则来定义的,这条规则的可信度被定义为“ 支持度({尿布,葡萄酒})  /  支持度({尿布})”。在表1 中可以发现  {尿布,葡萄酒} 的支持度是 3/53/5, {尿布} 的支持度为 4/54/5, 所以关联规则 “尿布 –> 葡萄酒”的可信度为 3/4=0.753/4=0.75, 意思是对于所有包含 "尿布"的记录中,该关联规则对其中的 75% 记录都适用。

因为网上的代码和原著的代码运行后会报一些错误,所以本文修改了两个地方,将C1和D都强制转换为list类型,程序才能正常运行。

    # 构建第一个候选项集列表C1
C1 = list(createC1(myDat))
# 构建集合表示的数据集 D
D = list(map(set, myDat))

apriori.py


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
1
2def loadDataSet():
3    '''创建一个用于测试的简单的数据集'''
4    return [ [ 1, 3, 4 ], [ 2, 3, 5 ], [ 1, 2, 3, 5 ], [ 2, 5 ] ]
5
6def createC1( dataSet ):
7    '''
8    构建初始候选项集的列表,即所有候选项集只包含一个元素,
9    C1是大小为1的所有候选项集的集合
10    '''
11    C1 = []
12    for transaction in dataSet:
13        for item in transaction:
14            if [ item ] not in C1:
15                C1.append( [ item ] )
16    C1.sort()
17    return map( frozenset, C1 )
18
19def scanD( D, Ck, minSupport ):
20    '''
21    计算Ck中的项集在数据集合D(记录或者transactions)中的支持度,
22    返回满足最小支持度的项集的集合,和所有项集支持度信息的字典。
23    '''
24    ssCnt = {}
25    for tid in D:
26        # 对于每一条transaction
27        for can in Ck:
28            # 对于每一个候选项集can,检查是否是transaction的一部分
29            # 即该候选can是否得到transaction的支持
30            if can.issubset( tid ):
31                ssCnt[can] = ssCnt.get(can, 0) + 1
32    numItems = float(len(D))
33    retList = []
34    supportData = {}
35    for key in ssCnt:
36        # 每个项集的支持度
37        support = ssCnt[ key ] / numItems
38        # 将满足最小支持度的项集,加入retList
39        if support >= minSupport:
40            retList.insert( 0, key )
41        # 汇总支持度数据
42        supportData[ key ] = support
43    return retList, supportData
44
45if __name__ == '__main__':
46    # 导入数据集
47    myDat = loadDataSet()
48    # 构建第一个候选项集列表C1
49    C1 = list(createC1(myDat))
50    
51    # 构建集合表示的数据集 D
52    D = list(map(set, myDat))
53    
54    # 选择出支持度不小于0.5 的项集作为频繁项集
55    L, suppData = scanD( D, C1, 0.5 )
56  
57    print ("频繁项集L:", L)
58    print ("所有候选项集的支持度信息:", suppData)
59
60

输出:


1
2
3
4
1频繁项集L: [frozenset({5}), frozenset({2}), frozenset({3}), frozenset({1})]
2所有候选项集的支持度信息: {frozenset({1}): 0.5, frozenset({3}): 0.75, frozenset({4}): 0.25, frozenset({2}): 0.75, frozenset({5}): 0.75}
3
4

可以看出,只有支持度不小于 0.5 的项集被选中到 L 中作为频繁项集,根据不同的需求,我们可以设定最小支持度的值,从而得到我们想要的频繁项集。

上述支队单元素进行了检查,为形成完整的apriori算法:

在上面代码中添加:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
1
2# Aprior算法
3def aprioriGen( Lk, k ):
4    '''
5    由初始候选项集的集合Lk生成新的生成候选项集,
6    k表示生成的新项集中所含有的元素个数
7    '''
8    retList = []
9    lenLk = len( Lk )
10    for i in range( lenLk ):
11        for j in range( i + 1, lenLk ):
12            L1 = list( Lk[ i ] )[ : k - 2 ];
13            L2 = list( Lk[ j ] )[ : k - 2 ];
14            L1.sort();L2.sort()
15            if L1 == L2:
16                retList.append( Lk[ i ] | Lk[ j ] )
17    return retList
18
19def apriori( dataSet, minSupport = 0.5 ):
20    # 构建初始候选项集C1
21    C1 = list(createC1( dataSet ))
22    # 将dataSet集合化,以满足scanD的格式要求
23    D = list(map( set, dataSet ))
24    # 构建初始的频繁项集,即所有项集只有一个元素
25    L1, suppData = scanD( D, C1, minSupport )
26    L = [ L1 ]
27    # 最初的L1中的每个项集含有一个元素,新生成的
28    # 项集应该含有2个元素,所以 k=2
29    k = 2
30    while ( len( L[ k - 2 ] ) > 0 ):
31        Ck = aprioriGen( L[ k - 2 ], k )
32        Lk, supK = scanD( D, Ck, minSupport )
33        # 将新的项集的支持度数据加入原来的总支持度字典中
34        suppData.update( supK )
35        # 将符合最小支持度要求的项集加入L
36        L.append( Lk )
37        # 新生成的项集中的元素个数应不断增加
38        k += 1
39    # 返回所有满足条件的频繁项集的列表,和所有候选项集的支持度信息
40    return L, suppData
41
42if __name__ == '__main__':
43#     # 导入数据集
44#     myDat = loadDataSet()
45#     # 构建第一个候选项集列表C1
46#     C1 = list(createC1(myDat))
47#     # 构建集合表示的数据集 D
48#     D = list(map(set, myDat))
49#     # 选择出支持度不小于0.5 的项集作为频繁项集
50#     L, suppData = scanD( D, C1, 0.5 )
51#     print ("频繁项集L:", L)
52#     print ("所有候选项集的支持度信息:", suppData)
53
54    # 导入数据集
55    myDat = loadDataSet()    
56    # 选择频繁项集
57    L, suppData = apriori( myDat, 0.5 )
58    print ("频繁项集L:", L)
59    print ("所有候选项集的支持度信息:", suppData)
60

输出:


1
2
3
4
1频繁项集L: [[frozenset({5}), frozenset({2}), frozenset({3}), frozenset({1})], [frozenset({2, 3}), frozenset({3, 5}), frozenset({2, 5}), frozenset({1, 3})], [frozenset({2, 3, 5})], []]
2所有候选项集的支持度信息: {frozenset({1}): 0.5, frozenset({3}): 0.75, frozenset({4}): 0.25, frozenset({2}): 0.75, frozenset({5}): 0.75, frozenset({1, 3}): 0.5, frozenset({2, 5}): 0.75, frozenset({3, 5}): 0.5, frozenset({2, 3}): 0.5, frozenset({1, 5}): 0.25, frozenset({1, 2}): 0.25, frozenset({2, 3, 5}): 0.5}
3
4

 

从频繁项集中挖掘关联规则:

要找到关联规则,先从一个频繁集开始,我们想知道对于频繁项集中的元素能否获取其它内容,即某个元素或者某个集合可能会推导出另一个元素。从表1 可以得到,如果有一个频繁项集 {豆奶,莴苣},那么就可能有一条关联规则 "豆奶 –> 莴苣",意味着如果有人购买了豆奶,那么在统计上他会购买莴苣的概率较大。但是这一条反过来并不一定成立。

从一个频繁项集可以产生多少条关联规则呢?可以基于该频繁项集生成一个可能的规则列表,然后测试每条规则的可信度,如果可信度不满足最小值要求,则去掉该规则。类似于前面讨论的频繁项集生成,一个频繁项集可以产生许多可能的关联规则,如果能在计算规则可信度之前就减少规则的数目,就会很好的提高计算效率。

这里有一条规律就是:如果某条规则并不满足最小可信度要求,那么该规则的所有子集也不会满足最小可信度要求,例如下图的解释:

使用Apriori算法进行关联分析

 

所以,可以利用上图所示的性质来减少测试的规则数目。

关联规则生成函数清单: 

在py文件中添加:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
1# 规则生成与评价  
2def calcConf( freqSet, H, supportData, brl, minConf=0.7 ):
3    '''
4    计算规则的可信度,返回满足最小可信度的规则。
5    
6    freqSet(frozenset):频繁项集
7    H(frozenset):频繁项集中所有的元素
8    supportData(dic):频繁项集中所有元素的支持度
9    brl(tuple):满足可信度条件的关联规则
10    minConf(float):最小可信度
11    '''
12    prunedH = []
13    for conseq in H:
14        conf = supportData[ freqSet ] / supportData[ freqSet - conseq ]
15        if conf >= minConf:
16            print(freqSet - conseq, '-->', conseq, 'conf:', conf)
17            brl.append( ( freqSet - conseq, conseq, conf ) )
18            prunedH.append( conseq )
19    return prunedH
20
21def rulesFromConseq( freqSet, H, supportData, brl, minConf=0.7 ):
22    '''
23    对频繁项集中元素超过2的项集进行合并。
24    
25    freqSet(frozenset):频繁项集
26    H(frozenset):频繁项集中的所有元素,即可以出现在规则右部的元素
27    supportData(dict):所有项集的支持度信息
28    brl(tuple):生成的规则
29    
30    '''
31    m = len( H[ 0 ] )
32    
33    # 查看频繁项集是否大到移除大小为 m 的子集
34    if len( freqSet ) > m + 1:
35        Hmp1 = aprioriGen( H, m + 1 )
36        Hmp1 = calcConf( freqSet, Hmp1, supportData, brl, minConf )
37        
38        # 如果不止一条规则满足要求,进一步递归合并
39        if len( Hmp1 ) > 1:
40            rulesFromConseq( freqSet, Hmp1, supportData, brl, minConf )
41
42def generateRules( L, supportData, minConf=0.7 ):
43    '''
44    根据频繁项集和最小可信度生成规则。
45    
46    L(list):存储频繁项集
47    supportData(dict):存储着所有项集(不仅仅是频繁项集)的支持度
48    minConf(float):最小可信度
49    '''
50    bigRuleList = []
51    for i in range( 1, len( L ) ):
52        for freqSet in L[ i ]:
53            # 对于每一个频繁项集的集合freqSet
54            H1 = [ frozenset( [ item ] ) for item in freqSet ]
55            
56            # 如果频繁项集中的元素个数大于2,需要进一步合并
57            if i > 1:
58                rulesFromConseq( freqSet, H1, supportData, bigRuleList, minConf )
59            else:
60                calcConf( freqSet, H1, supportData, bigRuleList, minConf )
61    return bigRuleList
62
63if __name__ == '__main__':
64#     # 导入数据集
65#     myDat = loadDataSet()
66#     # 构建第一个候选项集列表C1
67#     C1 = list(createC1(myDat))
68#     # 构建集合表示的数据集 D
69#     D = list(map(set, myDat))
70#     # 选择出支持度不小于0.5 的项集作为频繁项集
71#     L, suppData = scanD( D, C1, 0.5 )
72#     print ("频繁项集L:", L)
73#     print ("所有候选项集的支持度信息:", suppData)
74
75
76#     # 导入数据集
77#     myDat = loadDataSet()    
78#     # 选择频繁项集
79#     L, suppData = apriori( myDat, 0.7 )
80#     print ("频繁项集L:", L)
81#     print ("所有候选项集的支持度信息:", suppData)
82
83    # 导入数据集
84    myDat = loadDataSet()    
85    # 选择频繁项集
86    L, suppData = apriori( myDat, 0.5 ) #调节支持度
87    
88    rules = generateRules( L, suppData, minConf=0.7 ) #调节可信度
89    print('rules:\n', rules)
90

输出:


1
2
3
4
5
6
7
1frozenset({5}) --> frozenset({2}) conf: 1.0
2frozenset({2}) --> frozenset({5}) conf: 1.0
3frozenset({1}) --> frozenset({3}) conf: 1.0
4rules:
5 [(frozenset({5}), frozenset({2}), 1.0), (frozenset({2}), frozenset({5}), 1.0), (frozenset({1}), frozenset({3}), 1.0)]
6
7

一旦降低可信度阈值,就可以获得更多的规则。

有上面分析可以看出 Apriori 算法易编码,缺点是在大数据集上可能较慢。

给TA打赏
共{{data.count}}人
人已打赏
安全运维

MySQL和MongoDB数据相互迁移

2021-12-11 11:36:11

安全运维

Ubuntu上NFS的安装配置

2021-12-19 17:36:11

个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索