推荐算法——Apriori算法原理

news/2024/5/19 23:20:13 标签: 算法, 推荐算法, 人工智能

0、前言：

  • 首先名字别读错：an pu ruo ao rui 【拼音发音】
  • Apriori是一种推荐算法
  • 推荐系统：从海量数据中，帮助用户进行信息的过滤和选择。主要推荐方法有：基于内容的推荐、协同过滤推荐、基于关联规则的推荐、基于知识的推荐、混合推荐。
  • 关联分析：是一种在大规模数据集中寻找有趣关系的非监督学习算法，是利用一些有趣性的量度来识别数据库中发现的强规则。

1、基础概念

  • 频繁项集：经常【需要量化】出现在一块的物品的集合
  • 关联规则：暗示两种物品之间可能存在很强的关系
  • 事务：将数据看成一条条交易记录的集合，事务就是一条交易
  • 项：交易的每一个物品称为一个项
  • 项集：包含零个或者多个项的集合
  • k-项集：包含k个项的项集
  • 前件和后件：一个规则中先买了尿布后买了啤酒，尿布就是啤酒的前件、啤酒就是尿布的后件
  • 常用频繁项集的评估标准有：支持度、置信度、提升度；
    • 支持度就是几个关联的数据在数据集中出现次数占总数据集的比重。(举例：超市一天卖了5单，其中有2单同时出现了尿布和啤酒，那么{尿布、啤酒}的支持度就是2/5=0.4)，支持度常用来删除一些没意义的规则。
    • 置信度就是一个数据出现后，另一个数据出现的概率。（举例：买了尿布后会买啤酒的概率=两者同时出现的概率（两者的支持度）/尿布出现的概率（尿布的支持度））
    • 提升度：如果A事件的支持度本来就很高，然后求B事件发生后A事件的置信度，发现也很高，但并没有A事件本身的支持度高，就有可能误以为B事件的发生导致A事件发生的可能性增加了。所以加入了提升度的概念（举例：求A事件发生对B事件的提升度=AB同时发生的支持度/B事件发生的持度度），提升度大于1，表明A对B是有效的强关联规则，小于1表明A对B是无效的强关联规则。等于1，说明没有提升。
  • ★发现频繁项集和关联规则：如果一一遍历去找关联规则和频繁项集，计算量非常大，所以要进行筛选。
    • 1、首先设定最小支持度，最小置信度，找到满足最小支持度的所有项集，这些项集叫做频繁项集。
    • 2、从频繁项集中提取所有高置信度的规则，这些规则就是强关联规则。
    • 注意：如果一个项集是频繁的，那么它的所有子集也是频繁的。
    • 注意：如果一个项集是非频繁的，那么所有包含它的集合也是非频繁的。【通过这条规则减少计算量】

2、算法实现过程

  • Apriori算法原理：所有非频繁项集不用计算，减少计算量。获取apriori频繁项集是第一步，要通过apriori最终获取强关联规则，就要在频繁项集支持度的基础上，计算每种规则的支持度。
    在这里插入图片描述
  • 原始候选集构建1-项集：
# 数据集
dataset = [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]
# 让候选集每一项变成不可变集合，进而获取1-项集
def creat_c1(data_set):
    c1 = []
    for data in data_set:
        for i in data:
            if i not in c1:
                c1.append(i)
    c1.sort()
    return list(map(frozenset,[{i} for i in c1])) # frozenset是将集合变成不可变集合，目的是最后让frozenset作为字典的key
c1 = creat_c1(dataset)
'''
[frozenset({1}),
 frozenset({2}),
 frozenset({3}),
 frozenset({4}),
 frozenset({5})]
'''
  • 由1-项集（C1）转为1-项频繁集（L1）推出k-项集转k-项频繁集的函数：通过支持度筛选频繁集；scanD()函数：获取所有k-项集的支持度和k-项集对应的k-项频繁集
# C1(1项集):L1（1项频繁项集）
# D：数据集
# Ck：k项集
# min_support:最小支持度
def scanD(D,Ck,min_support=0.1):
    support_dic = {}
    # 遍历原始交易记录
    for d in D:
        for c in Ck:
            # 判断是否是子集，是的话数量加1
            if c.issubset(d):
                support_dic[c] = support_dic.get(c,0) + 1 # 防止刚开始support_dic是空
    support_data = {} # 所有项集的支持度
    LK = [] # 频繁项集
    # 计算支持度
    for k,v in support_dic.items():
        support = v/len(D)
        support_data[k] = support
#     print(support_data) # 打印支持度
        # 获得频繁项集
        if support >= min_support:
            LK.append(k)
    # 返回频繁项集、所有项集支持度：
    return LK, support_data
  • 由1-项频繁集产生2-项集的方法推出：k-项频繁集产生k+1-项集的方法；apriori_gen()函数：获取所有k-项频繁集（Lk）对应的k+1-项集（Ck+1），如下图以2-项集生成方法说明：
    在这里插入图片描述
# L1(1频繁项集) => C2（2项集）
def apriori_gen(LK):
    Ck = []
    for i in range(len(LK)-1):
        for j in range(i+1,len(LK)):
            f_set = LK[i] | LK[j]
            # print(f_set)
            # 不能重复，新项集只能是k+1项
            if f_set not in Ck and len(f_set) == len(LK[0])+1:
                Ck.append(f_set)
    # print(Ck)
    return Ck
  • 获取频繁项集和频繁项集生成过程中产生的项集的支持度
import time
def apriori(D, min_support=0.1):
    c1 = creat_c1(D)
    L1,support1 = scanD(D,c1,min_support)
    
    # 所有频繁项集
    L_f = []
    # 所有项集支持度就直接添加到support1中
    
    # 循环
    while True:
        L_f.append(L1)
        # 项集
        C = apriori_gen(L1)
        # 项集——频繁项集
        L,support = scanD(D,C,min_support)
        L1 = L
        support1.update(support)
        if len(L1)==0:
            break
    return L_f,support1
  • 获取k项集满足最小置信度的强关联规则的集合
    计算置信度：confidence(X -> Y) = P(Y|X) = P(XY) / P(X)【在x发生的条件下Y发生的置信度】
    calculate_conf()函数：计算某个频繁项集对应的满足最小置信度的强关联规则的集合。
# 计算一个项集的所有强关联规则
# 计算置信度
# freqSet: 频繁项集
# H=[frozenset({i}) for i in freqSet]
# L, support_Data = apriori(dataset, min_support=n)
# brl = [ ]   # 保存强关联规则的列表
def calculate_conf(freqSet, H, supportData, brl, minConf=0.5):
    newH = [ ]
    
    # 遍历H
    for s in H:
        # 置信度
        conf = supportData[freqSet] / supportData[freqSet - s]
        # conf(3,5->1) = P(1, 3, 5) / P(3,5)  
        # display(f'--- {freqSet - s} -> {s} = {conf} ---')
        
        # 大于最小置信度的规则是强规则
        if conf >= minConf:
            # 保存强关联规则到brl中
            brl.append( (freqSet - s, "->" , s, ' = ', conf) )  
            newH.append(s)
    
    return newH

用一个2-项集测试下函数calculate_conf，发现对于2-项集，函数能够获取所有满足置信度要求的关联规则。

freqSet = frozenset({1, 3})
H = [frozenset({i}) for i in freqSet]
L, support_data = apriori(dataset, min_support=0.2)
brl = [ ]   # 保存强关联规则的列表
# display(freqSet, H)

# 计算单个项集的置信度
calculate_conf(freqSet, H, support_data, brl, minConf=0.1)
brl
'''
[(frozenset({3}), '->', frozenset({1}), ' = ', 0.6666666666666666),
 (frozenset({1}), '->', frozenset({3}), ' = ', 1.0)]
'''
# 3-项集
freqSet = frozenset({1, 3, 5})
H = [frozenset({i}) for i in freqSet]
L, support_data = apriori(dataset, min_support=0.2)
brl = [ ]   # 保存强关联规则的列表
# display(freqSet, H)

# 计算单个项集的置信度
calculate_conf(freqSet, H, support_data, brl, minConf=0.1)
brl
'''
[(frozenset({3, 5}), '->', frozenset({1}), ' = ', 0.5),
 (frozenset({1, 5}), '->', frozenset({3}), ' = ', 1.0),
 (frozenset({1, 3}), '->', frozenset({5}), ' = ', 0.5)]
'''

可以发现：在3项集中出现了问题，3项集中只有2-项集作为前件的情况，没有1-项集作为前件的情况，出现了统计不完全的情况。因此为了让统计结果齐全，需要重新写个函数完善calculate_conf()函数。

# 考虑2-项集，3-项集，4-项集...
def rules_from_freq(freqSet, H, supportData, brl, minConf=0.7):
    tmp = True
    while tmp:
        tmp = False
        
        # 计算置信度
        newH = calculate_conf(freqSet, H, supportData, brl, minConf=minConf)
        # display(f'newH: {newH}')
        
        H = apriori_gen(newH)
        # display(f'H: {H}')
        # print('*' * 100)
        
        tmp =  not  (H==[ ] or len(H[0]) == len(freqSet))

测试：通过测试结果可以看出，完善之后的函数就能够获得所有满足要求置信度的关联规则

# 3-项集
freqSet = frozenset({1, 3, 5})
H = [frozenset({i}) for i in freqSet]
L, support_data = apriori(dataset, min_support=0.2)
brl = [ ]   # 保存强关联规则的列表
# display(freqSet, H)

# 计算单个项集的置信度
rules_from_freq(freqSet, H, support_data, brl, minConf=0.1)
brl
'''
[(frozenset({3, 5}), '->', frozenset({1}), ' = ', 0.5),
 (frozenset({1, 5}), '->', frozenset({3}), ' = ', 1.0),
 (frozenset({1, 3}), '->', frozenset({5}), ' = ', 0.5),
 (frozenset({5}), '->', frozenset({1, 3}), ' = ', 0.3333333333333333),
 (frozenset({3}), '->', frozenset({1, 5}), ' = ', 0.3333333333333333),
 (frozenset({1}), '->', frozenset({3, 5}), ' = ', 0.5)]
'''
  • 获取强关联规则的置信度：获取给定项集L中满足置信度要求的强关联规则
def gen_rules(L, support_data, min_conf=0.5):
    big_rule_list = [ ]
    
    for i in range(1, len(L)):  # 遍历所有行，第一行除外
        for freqSet in L[i]:  # 遍历每一行的所有元素
            # display(freqSet)
            H = [frozenset({i}) for i in freqSet]
            # 求每个项集的强关联规则，会保存在big_rule_list中
            rules_from_freq(freqSet, H, support_data, big_rule_list, minConf=min_conf)
    
    return big_rule_list

3、apriori算法总结：通过总结疏通下apriori算法中求频繁项集和求强关联规则的函数构造方法

在这里插入图片描述


http://www.niftyadmin.cn/n/5061114.html

相关文章

点餐小程序实战教程02用户注册

点餐小程序实战教程02用户注册

按照我们的需求分析，本篇开始我们进入到具体的开发部分。低代码开发的基础是先创建数据源，我们本篇介绍用户注册功能，先需要创建一个用于存放用户信息的数据源。 1 用户分类 未使用过低代码工具的初学者，可能对低代码的用户分类…
阅读更多...
python - random模块随机数常用方法

python - random模块随机数常用方法

文章目录 前言python - random模块随机数常用方法1. 返回1-10之间的随机数，不包括102. 返回1-10的随机数，包括103. 随机选取0到100之间的偶数4. 返回一个随机浮点数5. 返回一个给定数据集合中的随机字符6. 从多个字符中选取特定数量的字符7. 生成随机字符…
阅读更多...
【Ubuntu18.04】Autoware安装

【Ubuntu18.04】Autoware安装

Autoware安装 引言1 ROS安装2 Ubuntu18.04安装Qt5.14.23 安装GCC、G4 Autoware-1.14.0安装与编译4.1 源码的编译4.1.1 使用python2.7环境4.1.2 针对Ubuntu 18.04 / Melodic的依赖包安装4.1.3 先安装一些缺的ros依赖4.1.4 安装eigen3.3.74.1.5 安装opencv 3.4.164.1.6 编译4.1.7…
阅读更多...
软件过程的介绍

软件过程的介绍

软件过程概述 软件的诞生和生命周期是一个过程，我们总体上称这个过程为软件过程。软件过程是为了开发出软件产品，或者是为了完成软件工程项目而需要完成的有关软件工程的活动，每一项活动又可以分为一系列的工程任务。任何一个软件开发组织&a…
阅读更多...
《MySQL高级篇》十六、主从复制

《MySQL高级篇》十六、主从复制

文章目录 1、主从复制概述1.1 如何提升数据库并发能力1.2 主从复制的作用 2、主从复制的原理2.1 原理剖析2.2 复制的基本原则 3、一主一从架构搭建3.1 准备工作3.2 主机配置文件3.3 从机配置文件3.4 主机：建立账户并授权3.5 从机：配置需要复制的主机3.6 …
阅读更多...
一文简要了解星闪技术优势点

一文简要了解星闪技术优势点

文章目录 星闪推出的背景星闪的几个概念星闪技术的优势点传输速率高传输延迟极低连接数量多抗干扰能力强 小结 星闪推出的背景 提示：制裁之后星闪联盟诞生 由于美国对其进行了19年的制裁，华为被迫退出了国际蓝牙联盟，因此华为自主成立了星闪…
阅读更多...
【VR】【unity】如何在VR中实现远程投屏功能？

【VR】【unity】如何在VR中实现远程投屏功能？

【背景】 目前主流的VD应用，用于娱乐很棒，但是用于工作还是无法效率地操作键鼠。用虚拟键盘工作则显然是不现实的。为了让自己的头显能够起到小面积代替多显示屏的作用，自己动手开发投屏VR应用。 【思路】 先实现C#的投屏应用。研究如何将C#投屏应用用Unity 3D项目转写。…
阅读更多...
凉鞋的 Godot 笔记 101. Hello Godot!

凉鞋的 Godot 笔记 101. Hello Godot!

101. Hello Godot 学习任何一门技术，第一件事就是先完成 Hello World！的输出 所以我们也来先完成 Godot 的 Hello World。 我们所使用的 Godot 版本是 4.x 版本。 安装的过程就不给大家展示了，笔者更推荐初学者用 Steam 版本的 Godot&…
阅读更多...
最新文章

Copyright @ 2022~2023