Python算法总结（十一）Apriori算法（附手写python实现代码）_apriori算法python代码

一、算法类型

无监督算法

（小广告）重要事情说三遍~

想听我讲代码，请点这里，进入B站
想听我讲代码，请点这里，进入B站
想听我讲代码，请点这里，进入B站

二、算法原理

（1）算法流程

（2）指标

三、手写Python算法

（1）产生频繁项集

def create_c1(dataset):
    """
    #辅助函数1
    函数功能：⽣成第⼀个候选项集c1，每个项集只有1个item
    参数说明：
     dataset：原始数据集
    返回：
     frozenset形式的候选集合c1
    """
    c1=[]
    for transaction in dataset:
        for item in transaction:
            if not {item} in c1:
                c1.append({item})
    c1.sort()
    return list(map(frozenset,c1))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

def create_freq_transaction(dataset,ck,min_support=0.5):
    """
    #辅助函数2
    函数功能：⽣成满⾜最⼩⽀持度的频繁项集
    参数说明:
     dataset:原始数据集
     ck:候选项集
     min_support:最⼩⽀持度
    返回：
    support_data：候选项集ck的⽀持度字典(key:候选项， value:⽀持度)
    freq_transaction：给定min_support下的ck中的频繁项集
    
    注意：如果ck中得不到频繁项集，则返回的是空list
    """
    sscnt={} #存放项集及频次
    for transaction in dataset:
        for can in ck: #候选项集
            if can.issubset(transaction):
                sscnt[can]=sscnt.get(can,0)+1 #频次+1
    
    num_transactions=float(len(dataset)) #事务总量
    freq_transaction=[] #频繁项集,如果ck中得不到频繁项集，则返回的是空list
    
    support_data={} #存放项集及支持度
    for key in sscnt:
        support=sscnt[key]/num_transactions
        support_data[key]=support
        if support>=min_support:
            freq_transaction.append(key)
    return support_data,freq_transaction
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

def create_ck(freq_k_transaction): 
    """
    #辅助函数3
    函数功能：由频繁k项集⽣成k+1候选项集。
    参数说明：
    freq_k_transaction：频繁k项集
        这里用频繁K项集，而非k项集，体现了先验原理。即如果⼀个项集是频繁的，则它的所有⼦集⼀定也是频繁的。
        反之，如果⼀个项集是⾮频繁项集， 那么它的所有超集也是⾮频繁的。
    返回：
     ck：k+1候选项集。
         这里不是返回频繁k+1项集，暂时没有用支持度阈值对结果过滤。
    
    #特别重要，体现算法原理，节约计算资源。有3个关键点。
        1、不是从k候选项集生成k+1候选项集。目标是频繁项集，非频繁项集能不计算的就不计算，节约计算资源。
        2、频繁k项集两两组合。为何不是k频繁项集和1-频繁项集两两组合，是为了节约计算资源。先验原理告诉我们，这是可行的。
        3、只保留k+1候选项集，逐步计算。
    """
    ck=[] #k+1候选项集
    k=len(freq_k_transaction)
    for i in range(k):
        for j in range(i+1,k):
            t1=freq_k_transaction[i]
            t2=freq_k_transaction[j]
            t=t1|t2
            if (not t in ck) and (len(t)==len(freq_k_transaction[0])+1):
                ck.append(t)
    return ck
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

def apriori(dataset,min_support=0.5):
    '''
    # 主函数
    函数说明：生成大于支持度阈值下的频繁项集，以及所有候选项集及其支持度
    参数说明：
    dataset:原始数据事务集
    min_support:最⼩⽀持度
    返回：
    support_data：所有候选项集ck的⽀持度字典(key:候选项， value:⽀持度)
    all_freq_transaction：给定min_support下的所有频繁项集
    '''
    c1=create_c1(dataset)
    support_data,freq_transaction_1=create_freq_transaction(dataset,c1,min_support=min_support)
    all_freq_transaction=[freq_transaction_1]
    
    k=2 #初始化，辅助参数，没有实际意义
    while len(all_freq_transaction[-1])>0 :
        ck=create_ck(all_freq_transaction[-1])
        support_data_k,freq_transaction_k=create_freq_transaction(dataset,ck,min_support=min_support)
        support_data.update(support_data_k) #更新字典，批量增加
        all_freq_transaction.append(freq_transaction_k)
        k=k+1
    return support_data,all_freq_transaction
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

（2）产生关联规则

def create_subset(fromlist,tolist):
    '''
    #辅助函数1
    函数功能：已知列表fromlist的所有子集，结果保存到tolist，tolist中的元素格式是冻集合。
    '''
    for i in range(len(fromlist)):
        t=[fromlist[i]]
        tt=frozenset(set(fromlist)-set(t))
        if not tt in tolist:
            tolist.append(tt)
            
            tt=list(t)
            if len(tt)>1:
                create_subset(tt,tolist)    
    return None
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def cal_conf(fre_set,h,support_data,rulelist,min_conf):
    '''
    #辅助函数2
    函数功能：给定一个频繁项集，得到它子集中所有可能的关联规则，满足置信度阈值的强关联规则保存在rulelist中。
    参数说明：h是fre_set的所有子集集合。
    提升度需大于1
    
    
    将辅助函数之前，先看下置信度公式
    '''
    for after in h:
        conf=support_data[fre_set]/support_data[fre_set-after] #计算以after为后项以fre_set-after为前项的置信度
        lift=support_data[fre_set]/(support_data[fre_set-after] * support_data[after])
        if conf>= min_conf and lift>1:
            print(fre_set-after,'-->',after,'\n',
                  'before support:',round(support_data[fre_set-after],3),',',
                  'after support:',round(support_data[after],3),',',
                  'together support:',round(support_data[fre_set],3),',',
                  'conf:',round(conf,3),',',
                  'lift:',round(lift,3))
            rulelist.append((fre_set-after,after,round(conf,3))) #以元组形式保存
    return None
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

def create_rules(support_data,all_freq_transaction,min_conf=0.8):
    '''
    #主函数
    函数功能：生成给定频繁项集下的所有关联规则项。
    '''
    all_rulelist=[]
    for i in range(1,len(all_freq_transaction)):
        for fre_set in all_freq_transaction[i]:
            #求k项集的所有非空子集，1项集，2项集，直到k-1项集，用h表示，为list类型，元素为frozenset类型
            fre_list=list(fre_set)
            all_subset=[]
            create_subset(fre_list,all_subset)
            cal_conf(fre_set,all_subset,support_data,all_rulelist,min_conf)
    return all_rulelist
1
2
3
4
5
6
7
8
9
10
11
12
13
14

四、附调用手写函数