devbox
羊村懒王
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Apriori算法python实现（数据挖掘学习笔记）_apriori怎么剪枝python

作者：羊村懒王 | 2024-04-26 08:17:43

赞

踩

apriori怎么剪枝python

目录

1.算法伪代码

2.算法代码

3.测试数据

4.结果

1.算法伪代码

输入：事务数据库D；最小支持度阈值。

输出：D中的频繁项集L。

方法：  L1 = find_frequent_1_itemsets(D); //找出频繁1-项集的集合L1

           for(k = 2; Lk-1 ≠ ∅; k++) { //产生候选，并剪枝

         Ck = aproiri_gen(Lk-1,min_sup);

       for each transaction t∈D{ //扫描D进行候选计数

         Ct = subset(Ck,t); //得到t的子集

          for each candidate c∈Ct

         c.count++; //支持度计数

         }

          Lk={c∈Ck| c.count ≥min_sup} //返回候选项集中不小于最小支持度的项集

        }

     return L = ∪kLk；//所有的频繁集

第一步（连接 join）

Procedure apriori_gen(Lk-1: frequent (k-1)-itemset; min_sup: support)

1) for each itemset l1∈Lk-1

2) for each itemset l2∈Lk-1

3) if(l1[1]=l2[1])∧...∧(l1[k-2]=l2[k-2])∧(l1[k-1]<l2[k-1]) then{

4) c = l1 l2; //连接步：l1连接l2 //连接步产生候选，若K-1项集中已经存在子集c，则进行剪枝

5) if has_infrequent_subset(c,Lk-1) then

6) delete c; //剪枝步：删除非频繁候选

7) else add c to Ck;

8) }

9) return Ck;

第二步：剪枝（prune）

Procedure has_infrequent_subset(c:candidate k-itemset; Lk-1:frequent (k-1)-itemset) //使用先验定理

1) for each (k-1)-subset s of c

2) if c∉Lk-1 then

3) return TRUE;

4) return FALSE;

2.算法代码

  1. import itertools
  2. import time
  3. import psutil
  4. import os
  5.  
  6. def item(dataset):  # 求第一次扫描数据库后的 候选集，（它没法加入循环）
  7.     c1 = []  # 存放候选集元素
  8.  
  9.     for x in dataset:  # 就是求这个数据库中出现了几个元素，然后返回
  10.         for y in x:
  11.             if [y] not in c1:
  12.                 c1.append([y])
  13.     c1.sort()
  14.     # print(c1)
  15.     return c1
  16.  
  17. def get_frequent_item(dataset, c, min_support):
  18.     cut_branch = {}  # 用来存放所有项集的支持度的字典
  19.     for x in c:
  20.         for y in dataset:
  21.             if set(x).issubset(set(y)):  # 如果 x 不在 y中，就把对应元素后面加 1
  22.                 cut_branch[tuple(x)] = cut_branch.get(tuple(x),
  23.                                                       0) + 1  # cut_branch[y] = new_cand.get(y, 0)表示如果字典里面没有想要的关键词，就返回0
  24.     # print(cut_branch)
  25.  
  26.     Fk = []  # 支持度大于最小支持度的项集，  即频繁项集
  27.     sup_dataK = {}  # 用来存放所有 频繁 项集的支持度的字典
  28.  
  29.     for i in cut_branch:
  30.         if cut_branch[i] >= min_support:  # Apriori定律1  小于支持度，则就将它舍去，它的超集必然不是频繁项集
  31.             Fk.append(list(i))
  32.             sup_dataK[i] = cut_branch[i]
  33.     # print(Fk)
  34.     return Fk, sup_dataK
  35.  
  36. def get_candidate(Fk, K):  # 求第k次候选集
  37.     ck = []  # 存放产生候选集
  38.     for i in range(len(Fk)):
  39.         for j in range(i + 1, len(Fk)):
  40.             L1 = list(Fk[i])[:K - 2]
  41.             L2 = list(Fk[j])[:K - 2]
  42.             L1.sort()
  43.             L2.sort()  # 先排序，在进行组合
  44.  
  45.             if L1 == L2:
  46.                 if K > 2:  # 第二次求候选集，不需要进行减枝，因为第一次候选集都是单元素，且已经减枝了，组合为双元素肯定不会出现不满足支持度的元素
  47.                     new = list(set(Fk[i]) ^ set(Fk[j]))  # 集合运算 对称差集 ^ （含义，集合的元素在t或s中，但不会同时出现在二者中）
  48.                     # new表示，这两个记录中，不同的元素集合
  49.                     # 为什么要用new？ 比如 1，2     1，3  两个合并成 1，2，3   我们知道1，2 和 1，3 一定是频繁项集，但 2，3呢，我们要判断2，3是否为频繁项集
  50.                     # Apriori定律1 如果一个集合不是频繁项集，则它的所有超集都不是频繁项集
  51.                 else:
  52.                     new = set()
  53.                 for x in Fk:
  54.                     if set(new).issubset(set(x)) and list(
  55.                             set(Fk[i]) | set(Fk[j])) not in ck:  # 减枝 new是 x 的子集，并且 还没有加入 ck 中
  56.                         ck.append(list(set(Fk[i]) | set(Fk[j])))
  57.     # print(ck)
  58.     return ck
  59.  
  60. def Apriori(dataset, min_support=2):
  61.     c1 = item(dataset)  # 返回一个二维列表，里面的每一个一维列表，都是第一次候选集的元素
  62.     f1, sup_1 = get_frequent_item(dataset, c1, min_support)  # 求第一次候选集
  63.  
  64.     F = [f1]  # 将第一次候选集产生的频繁项集放入 F ,以后每次扫描产生的所有频繁项集都放入里面
  65.     sup_data = sup_1  # 一个字典，里面存放所有产生的候选集，及其支持度
  66.  
  67.     K = 2  # 从第二个开始循环求解，先求候选集，在求频繁项集
  68.  
  69.     while (len(F[K - 2]) > 1):  # k-2是因为F是从0开始数的     #前一个的频繁项集个数在2个或2个以上，才继续循环，否则退出
  70.         ck = get_candidate(F[K - 2], K)  # 求第k次候选集
  71.         fk, sup_k = get_frequent_item(dataset, ck, min_support)  # 求第k次频繁项集
  72.  
  73.         F.append(fk)  # 把新产生的候选集假如F
  74.         sup_data.update(sup_k)  # 字典更新，加入新得出的数据
  75.         K += 1
  76.     return F, sup_data  # 返回所有频繁项集， 以及存放频繁项集支持度的字典
  77.  
  78. def generate_association_rules(patterns, confidence_threshold):
  79.     rules = []
  80.     for itemset in patterns.keys():
  81.         upper_support = patterns[itemset]
  82.  
  83.         for i in range(1, len(itemset)):
  84.             for antecedent in itertools.combinations(itemset, i):
  85.                 antecedent = tuple(sorted(antecedent))
  86.                 consequent = tuple(sorted(set(itemset) - set(antecedent)))
  87.  
  88.                 if antecedent in patterns:
  89.                     lower_support = patterns[antecedent]
  90.                     confidence = float(upper_support) / lower_support
  91.  
  92.                     if confidence >= confidence_threshold:
  93.                         rules.append([antecedent, consequent, confidence])
  94.     return rules
  95.  
  96. def printPatterns(patterns):
  97.     keys1 = list(patterns.keys())
  98.     values1 = list(patterns.values())
  99.     for i in range(len(keys1)):
  100.         keys1[i] = list(keys1[i])
  101.  
  102.     for i in range(len(keys1)):
  103.         for j in range(len(keys1[i])):
  104.             print(keys1[i][j], end=" ")
  105.         for i2 in range(10 - 2 * len(keys1[i])):
  106.             print(" ", end="")
  107.         print(" : ", end="")
  108.         print(values1[i], end="\n")
  109.  
  110. def printRules2(rlues):
  111.     keys1 = []
  112.     values1 = []
  113.     for i in range(len(rules)):
  114.         keys1.append(list(rules[i][0]))
  115.         values1.append(list(rules[i][1]))
  116.  
  117.     for i in range(len(keys1)):
  118.         for j in range(len(keys1[i])):
  119.             print(keys1[i][j], end=" ")
  120.         for i2 in range(10 - 2 * len(keys1[i])):
  121.             print(" ", end="")
  122.         print(" --> ", end="")
  123.         for i1 in range(len(values1[i])):
  124.             print(values1[i][i1], end=" ")
  125.         for i3 in range(10 - 2 * len(values1[i])):
  126.             print(" ", end="")
  127.         print(":  " + str(rules[i][2]), end="\n")
  128.  
  129. if __name__ == '__main__':
  130.     begin_time = time.time()
  131.     dataset = [
  132.         ['M', 'O', 'N', 'K', 'E', 'Y'],
  133.         ['D', 'O', 'N', 'K', 'E', 'Y'],
  134.         ['M', 'A', 'K', 'E'],
  135.         ['M', 'U', 'C', 'K', 'Y'],
  136.         ['C', 'O', 'O', 'K', 'I', 'E']
  137.     ]  # 装入数据 二维列表
  138.     F, sup_data = Apriori(dataset, min_support=3)  # 最小支持度设置为3
  139.     rules = generate_association_rules(sup_data, 0.8)  # 置信度(条件概率)删选
  140.  
  141.     print("各频繁集及其出现次数", end="\n")
  142.     printPatterns(sup_data)
  143.     print('---------------------------------')
  144.     print("各强关联规则及其置信度", end="\n")
  145.     printRules2(rules)
  146.     end_time = time.time()
  147.     timeget = end_time - begin_time
  148.     print("程序开始时间:",begin_time)
  149.     print("程序结束时间：",end_time)
  150.     print("程序花费时间：",timeget)
  151.     print(u'当前进程的内存使用：%.4f GB' % (psutil.Process(os.getpid()).memory_info().rss / 1024 / 1024 / 1024))

注：代码具体来源已找不到

3.测试数据

['M', 'O', 'N', 'K', 'E', 'Y'],
['D', 'O', 'N', 'K', 'E', 'Y'],
['M', 'A', 'K', 'E'],
['M', 'U', 'C', 'K', 'Y'],
['C', 'O', 'O', 'K', 'I', 'E']

4.结果

程序开始时间: 1648740721.5249064

程序结束时间： 1648740721.525904

程序花费时间： 0.0009975433349609375

当前进程的内存使用：0.0132 GB

各频繁集及其出现次数

E   : 4

K   : 5

M   : 3

O   : 3

Y   : 3

K E  : 4

O E  : 3

K M  : 3

O K  : 3

Y K  : 3

O K E  : 3

各强关联规则及其置信度

K --> E:  0.8

E --> K:  1.0

O --> E:  1.0

M --> K:  1.0

O --> K:  1.0

Y --> K:  1.0

O--> E K:  1.0

执行Apriori算法花费的时间和占有的内存。

程序花费时间： 0.0009975433349609375

当前进程的内存使用：0.0132 GB

 

基础知识参考：

大白话解析Apriori算法python实现（含源代码详解）_A little storm的博客-CSDN博客_apriori算法python实现

关联规则挖掘——Apriori算法的基本原理以及改进_水澹澹兮生烟的博客-CSDN博客_apriori算法

本文仅仅是个人的学习笔记，如有错误，敬请指正！ 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/羊村懒王/article/detail/489929
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号