Apriori算法

ゝ一纸荒年。 2022-10-05 04:49 280阅读 0赞

Apriori算法是第一个关联规则挖掘算法，也是最经典的算法。它利用逐层搜索的迭代方法找出数据库中项集的关系，以形成规则，其过程由连接（类矩阵运算）与剪枝（去掉那些没必要的中间结果）组成。该算法中项集的概念即为项的集合。包含K个项的集合为k项集。项集出现的频率是包含项集的事务数，称为项集的频率。如果某项集满足最小支持度，则称它为频繁项集。

  1. #!/usr/bin/env python
  2. # -*- coding: utf-8 -*-
  3. from numpy import *
  5. # 构造数据
  6. def loadDataSet():
  7.     from csv import reader
  8.     potus = list(reader(open('../data/EpiData7.0.csv', encoding='UTF-8')))
  9.     # print(potus)
  10.     return potus
  13. # 将所有元素转换为frozenset型字典，存放到列表中
  14. def createC1(dataSet):
  15.     # prinnt('createC1将所有元素转换为frozenset型字典，存放到列表中')
  16.     C1 = []
  17.     for transaction in dataSet:
  18.         for item in transaction:
  19.             if not [item] in C1:
  20.                 C1.append([item])
  21.     C1.sort()
  22.     # 使用frozenset是为了后面可以将这些值作为字典的键
  23.     return list(map(frozenset, C1))  # frozenset一种不可变的集合，set可变集合
  26. # 过滤掉不符合支持度的集合
  27. # 返回 频繁项集列表retList 所有元素的支持度字典
  28. def scanD(D, Ck, minSupport):
  29.     # print('scanD过滤掉不符合支持度的集合')
  30.     ssCnt = { }
  31.     for tid in D:
  32.         for can in Ck:
  33.             if can.issubset(tid):  # 判断can是否是tid的《子集》 （这里使用子集的方式来判断两者的关系）
  34.                 if can not in ssCnt:  # 统计该值在整个记录中满足子集的次数（以字典的形式记录，frozenset为键）
  35.                     ssCnt[can] = 1
  36.                 else:
  37.                     ssCnt[can] += 1
  38.     numItems = float(len(D))
  39.     retList = []  # 重新记录满足条件的数据值（即支持度大于阈值的数据）
  40.     supportData = { }  # 每个数据值的支持度
  41.     for key in ssCnt:
  42.         support = ssCnt[key] / numItems
  43.         if support >= minSupport:
  44.             retList.insert(0, key)
  45.         supportData[key] = support
  46.     return retList, supportData  # 排除不符合支持度元素后的元素 每个元素支持度
  49. # 生成所有可以组合的集合
  50. # 频繁项集列表Lk 项集元素个数k [frozenset({2, 3}), frozenset({3, 5})] -> [frozenset({2, 3, 5})]
  51. def aprioriGen(Lk, k):
  52.     # print('aprioriGen生成所有可以组合的集合')
  53.     retList = []
  54.     lenLk = len(Lk)
  55.     for i in range(lenLk):  # 两层循环比较Lk中的每个元素与其它元素
  56.         for j in range(i + 1, lenLk):
  57.             L1 = list(Lk[i])[:k - 2]  # 将集合转为list后取值
  58.             L2 = list(Lk[j])[:k - 2]
  59.             L1.sort();
  60.             L2.sort()  # 这里说明一下：该函数每次比较两个list的前k-2个元素，如果相同则求并集得到k个元素的集合
  61.             if L1 == L2:
  62.                 retList.append(Lk[i] | Lk[j])  # 求并集
  63.     return retList  # 返回频繁项集列表Ck
  66. # 封装所有步骤的函数
  67. # 返回 所有满足大于阈值的组合 集合支持度列表
  68. def apriori(dataSet, minSupport=0.01):
  69.     print('apriori')
  70.     D = list(map(set, dataSet))  # 转换列表记录为字典 [{1, 3, 4}, {2, 3, 5}, {1, 2, 3, 5}, {2, 5}]
  71.     C1 = createC1(
  72.         dataSet)  # 将每个元素转会为frozenset字典 [frozenset({1}), frozenset({2}), frozenset({3}), frozenset({4}), frozenset({5})]
  73.     L1, supportData = scanD(D, C1, minSupport)  # 过滤数据
  74.     L = [L1]
  75.     k = 2
  76.     while (len(L[k - 2]) > 0):  # 若仍有满足支持度的集合则继续做关联分析
  77.         Ck = aprioriGen(L[k - 2], k)  # Ck候选频繁项集
  78.         Lk, supK = scanD(D, Ck, minSupport)  # Lk频繁项集
  79.         supportData.update(supK)  # 更新字典（把新出现的集合:支持度加入到supportData中）
  80.         L.append(Lk)
  81.         k += 1  # 每次新组合的元素都只增加了一个，所以k也+1（k表示元素个数）
  82.     return L, supportData
  85. dataSet = loadDataSet()
  86. L, suppData = apriori(dataSet)
  87. # print('L',L)
  88. # print('suppData',suppData)
  91. # 获取关联规则的封装函数
  92. def generateRules(L, supportData, minConf=0.8):  # supportData 是一个字典
  93.     print('获取关联规则的封装函数')
  94.     bigRuleList = []
  95.     for i in range(1, len(L)):  # 从为2个元素的集合开始
  96.         for freqSet in L[i]:
  97.             # 只包含单个元素的集合列表
  98.             H1 = [frozenset([item]) for item in freqSet]  # frozenset({2, 3}) 转换为 [frozenset({2}), frozenset({3})]
  99.             # 如果集合元素大于2个，则需要处理才能获得规则
  100.             if (i > 1):
  101.                 rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConf)  # 集合元素 集合拆分后的列表 。。。
  102.             else:
  103.                 calcConf(freqSet, H1, supportData, bigRuleList, minConf)
  104.     return bigRuleList
  107. # 对规则进行评估 获得满足最小可信度的关联规则
  108. def calcConf(freqSet, H, supportData, brl, minConf=0.8):
  109.     print('对规则进行评估 获得满足最小可信度的关联规则')
  110.     prunedH = []  # 创建一个新的列表去返回
  111.     for conseq in H:
  112.         conf = supportData[freqSet] / supportData[freqSet - conseq]  # 计算置信度
  113.         if conf >= minConf:
  114.             print(freqSet - conseq, '-->', conseq, 'conf:', conf)
  115.             brl.append((freqSet - conseq, conseq, conf))
  116.             prunedH.append(conseq)
  117.     return prunedH
  120. # 生成候选规则集合
  121. def rulesFromConseq(freqSet, H, supportData, brl, minConf=0.8):
  122.     print('#生成候选规则集合')
  123.     m = len(H[0])
  124.     if (len(freqSet) > (m + 1)):  # 尝试进一步合并
  125.         Hmp1 = aprioriGen(H, m + 1)  # 将单个集合元素两两合并
  126.         Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)
  127.         if (len(Hmp1) > 1):  # need at least two sets to merge
  128.             rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf)
  131. dataSet = loadDataSet()
  132. L, suppData = apriori(dataSet, minSupport=0.01)
  133. rules = generateRules(L, suppData, minConf=0.8)
  134. # rules = generateRules(L,suppData,minConf=0.5)
  135. print('rules',rules)

运行结果展示

  1. 获取关联规则的封装函数
  2. 对规则进行评估 获得满足最小可信度的关联规则
  3. 对规则进行评估 获得满足最小可信度的关联规则
  4. 对规则进行评估 获得满足最小可信度的关联规则
  5. 对规则进行评估 获得满足最小可信度的关联规则
  6. 对规则进行评估 获得满足最小可信度的关联规则
  7. 对规则进行评估 获得满足最小可信度的关联规则
  8. 对规则进行评估 获得满足最小可信度的关联规则
  9. 对规则进行评估 获得满足最小可信度的关联规则
  10. 对规则进行评估 获得满足最小可信度的关联规则
  11. 对规则进行评估 获得满足最小可信度的关联规则
  12. 对规则进行评估 获得满足最小可信度的关联规则
  13. 对规则进行评估 获得满足最小可信度的关联规则
  14. 对规则进行评估 获得满足最小可信度的关联规则
  15. frozenset({ '神经症'}) --> frozenset({ '女'}) conf: 1.0
  16. 对规则进行评估 获得满足最小可信度的关联规则
  17. frozenset({ '神经症'}) --> frozenset({ '无跌倒风险'}) conf: 1.0
  18. 对规则进行评估 获得满足最小可信度的关联规则
  19. frozenset({ '神经症'}) --> frozenset({ '跌倒时无妄想或幻觉'}) conf: 1.0
  20. #生成候选规则集合
  21. 对规则进行评估 获得满足最小可信度的关联规则
  22. frozenset({ '无后果', '精神分裂', '无跌倒风险', '病室', '中年人'}) --> frozenset({ '跌倒时无妄想或幻觉', '女'}) conf: 0.8571428571428571
  23. frozenset({ '无后果', '精神分裂', '女', '病室', '中年人'}) --> frozenset({ '无跌倒风险', '跌倒时无妄想或幻觉'}) conf: 1.0
  24. frozenset({ '无后果', '跌倒时无妄想或幻觉', '精神分裂', '病室', '中年人'}) --> frozenset({ '无跌倒风险', '女'}) conf: 0.8571428571428571
  25. #生成候选规则集合
  26. 对规则进行评估 获得满足最小可信度的关联规则
  27. frozenset({ '无后果', '精神分裂', '病室', '中年人'}) --> frozenset({ '无跌倒风险', '跌倒时无妄想或幻觉', '女'}) conf: 0.8571428571428571
  28. #生成候选规则集合
  29. 对规则进行评估 获得满足最小可信度的关联规则
  30. frozenset({ '入院3月内', '无后果', '精神分裂', '中年人'}) --> frozenset({ '跌倒时无妄想或幻觉', '病室', '无跌倒风险', '女'}) conf: 0.8
  31. #生成候选规则集合
  32. 对规则进行评估 获得满足最小可信度的关联规则
  33. frozenset({ '无后果', '精神分裂', '女', '年轻老年人', '饭厅', '无跌倒风险'}) --> frozenset({ '入院6月以上', '跌倒时无妄想或幻觉'}) conf: 1.0
  34. frozenset({ '无后果', '入院6月以上', '女', '年轻老年人', '饭厅', '无跌倒风险'}) --> frozenset({ '精神分裂', '跌倒时无妄想或幻觉'}) conf: 1.0
  35. frozenset({ '无后果', '入院6月以上', '精神分裂', '女', '饭厅', '无跌倒风险'}) --> frozenset({ '年轻老年人', '跌倒时无妄想或幻觉'}) conf: 1.0
  36. frozenset({ '无后果', '入院6月以上', '精神分裂', '女', '年轻老年人', '饭厅'}) --> frozenset({ '无跌倒风险', '跌倒时无妄想或幻觉'}) conf: 1.0
  37. frozenset({ '无后果', '跌倒时无妄想或幻觉', '入院6月以上', '女', '饭厅', '无跌倒风险'}) --> frozenset({ '年轻老年人', '精神分裂'}) conf: 1.0
  38. frozenset({ '无后果', '跌倒时无妄想或幻觉', '入院6月以上', '女', '年轻老年人', '饭厅'}) --> frozenset({ '精神分裂', '无跌倒风险'}) conf: 1.0
  39. frozenset({ '无后果', '跌倒时无妄想或幻觉', '入院6月以上', '精神分裂', '女', '饭厅'}) --> frozenset({ '年轻老年人', '无跌倒风险'}) conf: 1.0
  40. #生成候选规则集合
  41. 对规则进行评估 获得满足最小可信度的关联规则
  42. frozenset({ '无后果', '入院6月以上', '女', '年轻老年人', '饭厅'}) --> frozenset({ '精神分裂', '跌倒时无妄想或幻觉', '无跌倒风险'}) conf: 1.0
  43. frozenset({ '无后果', '入院6月以上', '女', '饭厅', '无跌倒风险'}) --> frozenset({ '年轻老年人', '精神分裂', '跌倒时无妄想或幻觉'}) conf: 1.0
  44. frozenset({ '无后果', '入院6月以上', '精神分裂', '女', '饭厅'}) --> frozenset({ '年轻老年人', '无跌倒风险', '跌倒时无妄想或幻觉'}) conf: 1.0
  45. frozenset({ '无后果', '跌倒时无妄想或幻觉', '入院6月以上', '女', '饭厅'}) --> frozenset({ '年轻老年人', '精神分裂', '无跌倒风险'}) conf: 1.0
  46. #生成候选规则集合
  47. 对规则进行评估 获得满足最小可信度的关联规则
  48. frozenset({ '入院6月以上', '无后果', '饭厅', '女'}) --> frozenset({ '年轻老年人', '跌倒时无妄想或幻觉', '无跌倒风险', '精神分裂'}) conf: 1.0
  49. rules [(frozenset({ '神经症'}), frozenset({ '女'}), 1.0), (frozenset({ '神经症'}), frozenset({ '无跌倒风险'}), 1.0), (frozenset({ '神经症'}), frozenset({ '跌倒时无妄想或幻觉'}), 1.0), (frozenset({ '跌倒时有妄想或幻觉'}), frozenset({ '无跌倒风险'}), 0.8333333333333334), (frozenset({ '跌倒时有妄想或幻觉'}), frozenset({ '精神分裂'}), 0.8333333333333334), (frozenset({ '其他地点'}), frozenset({ '无跌倒风险'}), 1.0), (frozenset({ '其他地点'}), frozenset({ '跌倒时无妄想或幻觉'}), 1.0), (frozenset({ '其他地点'}), frozenset({ '年轻老年人'}), 1.0), (frozenset({ '其他地点'}), frozenset({ '精神分裂'}), 1.0), (frozenset({ '痴呆'}), frozenset({ '跌倒时无妄想或幻觉'}), 1.0), (frozenset({ '入院6月内'}), frozenset({ '无跌倒风险'}), 0.875), (frozenset({ '入院6月内'}), frozenset({ '跌倒时无妄想或幻觉'}), 0.9375), (frozenset({ '走廊'}), frozenset({ '跌倒时无妄想或幻觉'}), 0.9428571428571428), (frozenset({ '重度后果'}), frozenset({ '无跌倒风险'}), 0.8125), (frozenset({ '重度后果'}), frozenset({ '跌倒时无妄想或幻觉'}), 0.9375), (frozenset({ '老年人'}), frozenset({ '跌倒时无妄想或幻觉'}), 0.9230769230769231), (frozenset({ '入院1月内'}), frozenset({ '跌倒时无妄想或幻

发表评论

表情：
评论列表 （有 0 条评论，280人围观）

还没有评论，来说两句吧...

相关阅读

    相关 Apriori算法

    Apriori算法是第一个关联规则挖掘算法，也是最经典的算法。它利用逐层搜索的迭代方法找出数据库中项集的关系，以形成规则，其过程由连接（类矩阵运算）与剪枝（去掉那些没必要的中间

    ゝ一纸荒年。ゝ一纸荒年。/ 0 赞/ 281 阅读

    相关 apriori推荐算法

    Apriori算法是一种挖掘关联规则的频繁项集算法，其核心思想是通过候选集生成和情节的向下封闭检测两个阶段来挖掘频繁项集。 概念 （1）支持度（Supp

    ゝ一纸荒年。ゝ一纸荒年。/ 0 赞/ 302 阅读

    相关 Apriori算法

     Apriori算法是我的第一个数据挖掘算法，算处女作吧，哈哈哈。在这之前我对数据挖掘算法恐惧，觉得太难了，只是大致看了下原理，然后在clementine上拖几个控件跑下dem

    以你之姓@以你之姓@/ 0 赞/ 314 阅读

    相关 apriori算法

    一、Apriori[算法][Link 1]简介： Apriori算法是一种挖掘关联规则的频繁项集算法，其核心思想是通过候选集生成和情节的向下封闭检测两个阶段来挖掘频繁项集。 A

    我会带着你远行我会带着你远行/ 0 赞/ 306 阅读

    相关 数据挖掘-Apriori算法

    微信搜索：“二十同学” 公众号，欢迎关注一条不一样的成长之路 引子：啤酒与尿布 据说这是一个真实的案例：沃尔玛在分析销售记录时，发现啤酒和尿布经常一起被购买，于是他们调

    迈不过友情╰迈不过友情╰/ 0 赞/ 761 阅读