数据挖掘与机器学习(part 9) 规则挖掘Rules Mining关联规则(Association Rules) Apriori算法

embedded/2024/12/21 13:12:07/

基于规则的分类器:Classification using rule based classifier

互斥规则(Mutually exclusive rules):

分类器包含互斥规则,如果这些规则彼此独立。
每条记录最多被一条规则覆盖。

穷尽规则(Exhaustive rules):

如果分类器能够考虑到属性值的所有可能组合,那么它具有穷尽的覆盖。
每条记录至少被一条规则覆盖。

这些概念在设计和评估分类系统时非常重要,因为它们确保了分类器的完整性和准确性。互斥规则确保了分类的明确性,而穷尽规则则确保了分类的全面性。

无监督规则发现Unsupervised Rule Discovery

给定一组记录,每组记录都包含给定集合中的一定数量的项目之后生成依赖规则,根据其他项目的出现情况预测项目的出现情况。

规则的使用 

规则并不代表两个项目集之间的任何因果关系或相关性。 

这些规则有助于市场营销、有针对性的广告、楼层规划、库存控制、流失管理、国土安全、...

监督学习:顺序覆盖算法 Supervised learning: sequential covering algorithm

  1. 从一个空规则开始。
  2. 使用“Learn-One-Rule”函数来扩展规则。
  3. 移除被规则覆盖的训练记录。
  4. 重复步骤2和3,直到满足停止条件。

图片中展示了两个阶段的数据:

(i) 原始数据:显示了初始数据集中的正负样本分布

(ii) 第一步:显示了在应用了第一步规则后,被规则覆盖(即被分类)的数据记录。在这个阶段,可以看到一些正样本(+)被规则正确分类,并且从训练集中移除,同时留下了未被覆盖的样本以供下一步处理。

这个流程通常用于迭代地构建分类器,每一步都在尝试提高分类器的性能,直到达到某个性能标准或无法进一步改进为止。

(iii) 第二步:在这个阶段,算法识别并应用了第一条规则(R1),这条规则覆盖了一部分记录。被R1覆盖的记录被移除,剩下的未被覆盖的记录继续用于下一步的规则学习。

(iv) 第三步:在这个阶段,算法识别并应用了第二条规则(R2),这条规则覆盖了剩余未被R1覆盖的记录中的一些。同样,被R2覆盖的记录被移除。

这种方法被称为覆盖法(covering approach)

因为在每个阶段,都会识别出一条规则来覆盖一些记录。这种方法通过迭代地识别和应用规则,逐步减少未分类的记录数量,直到满足停止条件。这种方法有助于构建一个能够覆盖所有训练记录的分类器。

 How to learn-one-rule

通过添加测试(或分割)来生成规则,这个测试能够最大化规则的性能标准(例如准确率)。
这与决策树中选择属性进行分割的情况相似:选择哪个属性进行分割是一个问题。
但是,决策树的目标是最大化整体的纯度。
在这里,每个新的测试(扩展规则)都会减少规则的覆盖范围。

这意味着在构建规则的过程中,每一步都在尝试通过选择最佳的分割条件来提高规则的准确性,但同时,随着规则的细化,它能够覆盖的数据记录范围可能会减小。这种权衡是规则学习中的一个重要考虑因素。

在构建分类规则时如何选择测试(或分割)以优化规则的性能

 这些方法都是为了在构建分类规则时,选择最佳的分割点以提高规则的性能。准确率、熵和信息增益是衡量规则性能的不同标准,每种方法都有其优势和适用场景。

规则可以简化

规则简化的效果

规则不再相互排斥

一条记录可能触发不止一条规则

Solution?:有序规则集 ; 无序规则集--使用表决方案

规则不再穷尽

一条记录可能不触发任何规则

Solution?:使用默认类

无监督学习:关联规则挖掘 Unsupervised learning: association rules mining

关联规则挖掘

由 Agrawal 等人于 1993 年提出。

它是数据库和数据挖掘界广泛研究的一种重要数据挖掘模型。

假定所有数据都是分类数据, 没有适用于数字数据的好算法

 最初用于市场篮子分析,以找出客户购买的商品之间的关联。

EXAMPLE

交易数据:超市数据
市场购物篮交易:t1:{面包、奶酪、牛奶}t2:{苹果、鸡蛋、盐、酸奶}......tn:{饼干、鸡蛋、牛奶}
概念:项目:篮子中的项目/物品
I:商店出售的所有物品的集合
交易:购物篮中购买的物品; 
它可能有 TID(交易 ID)
交易数据集: 一组交易 

项目集和关联规则 

项目集是一组项目。例如,{牛奶、面包、麦片}就是一个项目集。

k 项集是一个包含 k 个项的项集。给定数据集 D,项集 X 在 D 中的(频率)计数是存在的

关联规则是关于两个不相交的项集 X 和 Y 之间的关系

当 X 出现时,Y 也会出现。

支持度和置信度

Support支持度:

  • 是指某个项集 X 在数据集 DD 中出现的频率。计算公式为 support(X)=count(X)/∣D∣​,其中 count(X) 是项集 X 出现的次数,∣D∣ 是数据集 D 中的总交易数。

 置信度(Confidence):

  • 对于关联规则 X⇒Y,置信度是指在项集 X 出现的情况下,项集 Y 也出现的概率。
  • 计算公式为 confidence(X⇒Y)=support(X∩Y)/support(X),其中 support(X∩Y)support(X∩Y) 是项集 X 和 Y 同时出现的支持度。 

支持度和置信度与联合概率和条件概率的关系

  • 支持度 support(X⇒Y) 可以看作是 X 和 Y 同时出现的联合概率。
  • 置信度 confidence(X⇒Y) 可以看作是在 XX出现的条件下 Y 出现的条件概率。

 A-规则的数量

  • 在一个大型数据集中,可能存在指数级数量的关联规则(A-rules)。这是因为每个项集可以与其他项集形成规则,随着项集大小的增加,可能的规则数量迅速增长。

有趣的关联规则:

  • 在关联规则学习中,我们通常只对那些支持度和置信度都高于某个阈值的规则感兴趣。
  • 这些阈值由数据挖掘者根据具体问题设定,称为最小支持度(minSup)和最小置信度(minConf)。

EXAMPLE 

 

一个具体的例子展示了如何从交易数据中发现频繁项集(frequent itemset)和关联规则(association rules)

假设(Assume)
  • 最小支持度(minsup)= 30%:这意味着一个项集必须在至少30%的交易中出现,才能被认为是频繁的。
  • 最小置信度(minconf)= 80%:这意味着一个规则的置信度必须至少为80%,才能被认为是有趣的。
频繁项集(Frequent Itemset)
  • {Chicken, Clothes, Milk} 的支持度(sup)= 3/7:这个项集在7个交易中的3个(t5, t6, t7)中出现,所以它的支持度是3/7,大约是42.86%,超过了30%的最小支持度阈值。
关联规则(Association Rules)

从频繁项集 {Chicken, Clothes, Milk} 可以生成以下关联规则:

  1. Clothes → Milk, Chicken [sup = 3/7, conf = 3/3]

    • 这个规则表示在包含“Clothes”的交易中,同时包含“Milk”和“Chicken”的概率是100%(3/3),因为“Clothes”在所有包含它的交易中都与“Milk”和“Chicken”一起出现。
  2. Clothes, Chicken → Milk [sup = 3/7, conf = 3/3]

    • 这个规则表示在同时包含“Clothes”和“Chicken”的交易中,包含“Milk”的概率是100%(3/3),因为每当“Clothes”和“Chicken”一起出现时,“Milk”也总是出现。
总结

这个例子展示了如何从交易数据中识别频繁项集,并通过这些项集生成关联规则。频繁项集和关联规则的发现是市场篮子分析中的关键步骤,可以帮助企业了解产品之间的关联性,从而优化产品摆放、促销策略等。在这个例子中,所有生成的规则都满足最小支持度和最小置信度的要求,因此被认为是有趣的。

 

Apriori算法概述

  • Apriori算法:可能是最知名的关联规则学习算法

算法的两个步骤

  1. 寻找频繁项集

    • 找出所有支持度大于或等于最小支持度阈值的项集。这些项集被称为频繁项集(frequent itemsets),有时也称为大项集(large itemsets)。
  2. 生成规则

    • 使用找到的频繁项集来生成关联规则。

 Apriori算法的特点

  • 频繁项集的生成:Apriori算法通过迭代的方式生成候选项集,并计算它们的支持度,然后筛选出频繁项集。这个过程称为“剪枝”(pruning),因为它移除了那些不可能成为频繁项集的候选项集。
  • 关联规则的生成:一旦频繁项集被确定,算法会从这些项集中生成所有可能的规则,并计算每条规则的置信度。只有那些置信度高于最小置信度阈值的规则才会被保留。

Apriori算法的核心优势在于其简单性和有效性,尤其是在处理大型数据集时。通过逐步构建项集并剪枝,算法可以有效地减少计算量,同时找到所有频繁项集和高置信度的关联规则。

示例

  • 频繁项集:{Chicken, Clothes, Milk}

    • 支持度(sup)= 3/7:这个项集在7个交易中的3个中出现,支持度为42.86%,如果最小支持度阈值设置为30%,那么这个项集被认为是频繁的。
  • 关联规则:Clothes → Milk, Chicken

    • 支持度(sup)= 3/7:这个规则表示在所有包含“Clothes”的交易中,有3个交易同时包含“Milk”和“Chicken”。
    • 置信度(conf)= 3/3:这个规则的置信度是100%,意味着在所有包含“Clothes”的交易中,100%的交易也包含“Milk”和“Chicken”。

步骤 1:挖掘所有频繁项集

频繁项集是指支持度≥minsup的项集。

关键思路: apriori 属性(向下闭合属性):频繁项集的任何子集也是频繁项集 

 

算法:迭代算法。 (也称逐级搜索):

初始:查找所有 1 项频繁项集;然后是所有 2 项频繁项集,依此类推。 

在每次迭代 k 时,只考虑包含某个 k-1 频繁项集的项集。 这是基于Apriori原理,即如果一个项集是频繁的,那么它的所有子集也必须是频繁的。

具体步骤

  • F1​:首先找到所有1项频繁项集。
  • Ck​:对于 k≥2,Ck​ 是大小为 k 的候选项集,这些项集可能在给定 Fk−1​ 的情况下是频繁的。这意味着 Ck 中的每个项集都至少包含一个 Fk−1​ 中的项集。
  • Fk​:Fk​ 是那些实际上频繁的项集,即 Fk​ 是 Ck的子集。为了确定 Fk​,需要扫描数据库一次,计算 Ck中每个项集的支持度,并与最小支持度阈值进行比较。

算法优势

  • 效率:通过在每次迭代中只考虑可能成为频繁项集的候选项集,Apriori算法减少了需要评估的项集数量。
  • 简单性算法易于理解和实现,适用于各种规模的数据集。

总结

Apriori算法通过迭代地增加项集的大小,并在每次迭代中只考虑那些可能成为频繁项集的候选项集,有效地发现数据集中的频繁项集。这种方法不仅提高了算法的效率,而且确保了算法的简单性和可扩展性。

伪代码

 

Python实现EXAMPLE

from mlxtend.preprocessing import TransactionEncoder
from mlxtend.frequent_patterns import apriori, association_rules# 示例交易数据集
dataset = [['牛奶', '面包', '苹果'],['牛奶', '饼干'],['牛奶', '面包', '饼干', '苹果'],['面包', '饼干'],['牛奶', '面包', '苹果', '饼干'],
]# 初始化TransactionEncoder
te = TransactionEncoder()
te_ary = te.fit(dataset).transform(dataset)# 将数据转换为DataFrame
import pandas as pd
df = pd.DataFrame(te_ary, columns=te.columns_)# 使用apriori算法找出频繁项集
frequent_itemsets = apriori(df, min_support=0.6, use_colnames=True)# 生成关联规则
rules = association_rules(frequent_itemsets, metric="confidence", min_threshold=0.7)# 打印频繁项集
print("频繁项集:")
print(frequent_itemsets)# 打印关联规则
print("\n关联规则:")
print(rules)#实现Apriori算法候选项集生成的简化示例
def candidate_gen(Fk_minus_1):Ck = []for i in range(len(Fk_minus_1)):for j in range(i + 1, len(Fk_minus_1)):# 连接步骤:合并项集L1 = list(Fk_minus_1[i])[:-1]L2 = list(Fk_minus_1[j])[:-1]L1.sort()L2.sort()if L1 == L2:# 合并最后一个元素Ck.append(Fk_minus_1[i] | Fk_minus_1[j])return Ckdef prune(Ck, Fk_minus_1):# 剪枝步骤:移除非频繁项集return [c for c in Ck if all(c.difference(f) == set() for f in Fk_minus_1)]# 示例频繁项集 F2
F2 = [{('牛奶', '面包')}, {('牛奶', '苹果')}, {('面包', '苹果')}]# 生成候选项集 C3
C3 = candidate_gen(F2)# 剪枝
C3 = prune(C3, F2)#Python实现从频繁项集生成关联规则的简化示例:
from mlxtend.frequent_patterns import association_rules# 假设频繁项集已经通过Apriori算法找到并存储在frequent_itemsets中
frequent_itemsets = [['牛奶', '面包'],['牛奶', '苹果'],['面包', '苹果'],['牛奶', '面包', '苹果']
]# 生成关联规则
rules = association_rules(frequent_itemsets, metric="confidence", min_threshold=0.7)# 打印关联规则
print("关联规则:")
print(rules)

这段代码首先定义了一个交易数据集,然后使用TransactionEncoder将数据集转换为适合机器学习模型的格式。接着,使用apriori函数找出频繁项集,其中min_support=0.6表示最小支持度阈值为60%。最后,使用association_rules函数生成关联规则,metric="confidence"表示使用置信度作为评估指标,min_threshold=0.7表示最小置信度阈值为70%。 

Apriori候选项集的生成(candidate generation) 

1. 连接步骤(Join Step)

连接步骤的目的是生成所有可能的候选项集 CkCk​,这些项集的长度为 kk。这是通过将 Fk−1Fk−1​(长度为 k−1k−1 的频繁项集)中的项集两两组合来实现的。具体操作如下:

  • 对于 Fk−1Fk−1​ 中的每一对项集 XX 和 YY,如果 XX 和 YY 的前 k−2k−2 个元素相同(即它们有相同的前缀),则将 XX 和 YY 的最后一个元素合并,形成一个新的长度为 kk 的项集。
  • 这种合并操作会生成所有可能的 kk-项候选项集。

2. 剪枝步骤(Prune Step)

剪枝步骤的目的是移除那些不可能成为频繁项集的候选项集,从而减少需要进一步评估的项集数量。具体操作如下:

  • 对于 CkCk​ 中的每个候选项集 CC,检查其所有长度为 k−1k−1 的子集。
  • 如果 CC 的任何一个子集不在 Fk−1Fk−1​ 中(即不是频繁项集),则 CC 不能是频繁项集,因此可以从 CkCk​ 中移除。
  • 这种剪枝操作基于Apriori原理,即如果一个项集是频繁的,那么它的所有子集也必须是频繁的。

示例

假设 F2F2​(2-项频繁项集)为 {牛奶, 面包}, {牛奶, 苹果}, {面包, 苹果}。要生成 C3C3​(3-项候选项集),我们执行以下操作:

  • 连接步骤:合并具有相同前缀的项集,生成 {牛奶, 面包, 苹果}。
  • 剪枝步骤:检查 {牛奶, 面包, 苹果} 的所有子集 {牛奶, 面包}, {牛奶, 苹果}, {面包, 苹果} 是否都在 F2F2​ 中。由于它们都在,{牛奶, 面包, 苹果} 保留在 C3C3​ 中。

 步骤 2:根据频繁项集生成规则

 频繁项集与关联规则的区别

  • 频繁项集:是数据集中经常出现的项的集合。
  • 关联规则:是一种蕴含关系,表示如果一个项集(A)出现,那么另一个项集(B)也很可能出现。关联规则的形式为 A → B

生成关联规则的步骤

  • 对于每个频繁项集 X:
    • 考虑 X 的所有非空真子集 A(即 A 是 X 的子集,但 A 不等于 X)。
    • 计算 B = X - A,即 B 包含 X 中除了 A 之外的所有项。

评估关联规则

  • 一个关联规则 A → B 被认为是有效的,如果:
    • 置信度(Confidence):Confidence(A → B) ≥ minconf。置信度是衡量在 A 出现的情况下 B 也出现的概率,计算公式为 confidence(A → B) = support(A ∪ B) / support(A)。这里,support(A ∪ B) 等于 support(X),因为 A ∪ B 就是 X。
    • 支持度(Support):support(A → B) = support(A ∪ B) = support(X)。这意味着规则 A → B 的支持度与项集 X 的支持度相同。

 生成规则的步骤概述:

  • 确定频繁项集:首先,通过Apriori算法或其他方法确定数据集中的频繁项集。
  • 生成子集:对于每个频繁项集,生成所有可能的非空真子集。
  • 计算置信度:对于每个子集A和对应的补集B(即频繁项集减去A),计算置信度(confidence),公式为 confidence(A → B) = support(A ∪ B) / support(A)
  • 筛选规则:只保留那些置信度大于或等于最小置信度阈值的规则。

 多个最小支持度(Multiple Minimum Supports,简称 Multiple minsups)模型

 在Multiple minsups模型中,规则的最小支持度(minsup)是根据规则中出现的项的最小项支持度(Minimum Item Support,简称MIS)来表达的。这意味着每个项都可以有一个特定的最小支持度要求。

不同项的不同MIS值:通过为不同的项提供不同的MIS值,用户可以有效地表达对不同规则的不同支持度要求。这种方法允许算法在挖掘过程中考虑到项的自然属性和频率,从而生成更有意义的规则。

利用数据稀疏性:关联规则挖掘算法利用数据的稀疏性,通过设置较高的最小支持度和最小置信度值来减少生成的规则数量。这种方法有助于过滤掉那些不那么重要的规则,只保留那些具有较高置信度和支持度的规则。

算法效率:尽管关联规则挖掘可能会产生大量的规则,但通过使用Multiple minsups模型,可以更有效地控制规则的数量和质量。这种方法可以在保持算法效率的同时,提高规则的相关性和实用性。

 

总结:

关联规则挖掘在数据挖掘领域已经被广泛研究。
存在许多高效的算法和模型变体。
其他相关工作包括:
多层次或广义规则挖掘:这涉及到挖掘不同抽象层次上的规则,或者挖掘具有更广义条件的规则。
约束规则挖掘:在挖掘过程中加入特定的约束条件,以满足特定的业务需求或数据特性。
增量规则挖掘:随着新数据的不断加入,更新现有的关联规则,而不是每次都重新挖掘整个数据集。
最大频繁项集挖掘:寻找在数据集中出现频率最高的项集,这些项集可能不包含在任何更大的频繁项集中。
数值关联规则挖掘:处理数值型数据,挖掘数值项之间的关联规则。
规则有趣性度量和可视化:评估规则的有趣性,并通过可视化技术展示规则,以便于理解和分析。
并行算法:利用多处理器或分布式计算资源来加速关联规则挖掘过程。

 

 

 

 

 

 

 


http://www.ppmy.cn/embedded/147536.html

相关文章

VarifocalLoss在Yolov8中的应用

调用VFL Loss 在ultralytics/utils/loss.py可以发现v8实现了VarifocalLoss,但是好像和原论文有点不一样,这里有待考证原文地址:论文在cls损失处 # Cls lossloss[1] self.varifocal_loss(pred_scores, target_scores, target_labels) / targ…

XML基础学习

参考文章链接: XML基础学习 在w3school看到了XML的教程,想到以前工作学习中也接触到了XML,但只是简单搜索了解了下,没有认真去学习XML的基础,所以现在认真看下其基础部分,并写篇博客作为笔记记录下。 XML 简介 XML 被设计用来传输和存储数据。 什么是 XML? XML 指可…

【蓝桥杯每日一题】扫雷——暴力搜索

扫雷 蓝桥杯每日一题 2024-12-20 扫雷 暴力搜索 题目大意 在一个 n 行 m 列的方格图上有一些位置有地雷,另外一些位置为空。 请为每个空位置标一个整数,表示周围八个相邻的方格中有多少个地雷。 解题思路 今天算是水了一道暴力搜索题,还是接着…

C# Winform双色纸牌接龙小游戏源码

文章目录 一、设计来源双色纸牌接龙小游戏讲解1.1 主界面1.2 游戏界面1.3 游戏界面快成功了 二、效果和源码2.1 动态效果2.2 源代码 源码下载更多优质源码分享 作者:xcLeigh 文章地址:https://blog.csdn.net/weixin_43151418/article/details/144419994 …

maven权威指南(读书笔记一)

以下用【】的是阅读时候想到的问题 maven: 是什么:构建工具,项目管理工具、多模块管理、模块复用、生命周期 特点:约定大于配置。详见项目结构 核心概念:??? 【Maven Archetype插件…

Function 和 BiFunction 的使用例

Function 在Java中,Function接口是java.util.function包中的一个核心函数式接口。它代表了一个接受一个参数并产生结果的函数。Function接口的主要作用是简化代码,提高可读性和可维护性,特别是在使用Lambda表达式和方法引用的情况下。以下是…

git bash中文显示问题

个人博客地址&#xff1a;git bash中文显示问题 | 一张假钞的真实世界。 默认情况下git bash中文以ASCII编码&#xff0c;不方便查看&#xff0c;如下&#xff1a; $ git status 位于分支 master尚无提交要提交的变更&#xff1a;&#xff08;使用 "git rm --cached <…

C05S11-MySQL数据库索引

一、索引 1. 索引概述 索引是一个排序的列表&#xff0c;在这个列表当中存储了索引的值和这个值对应数据所在的物理地址。使用索引之后&#xff0c;查询数据表时&#xff0c;不用全表扫描来定位数据所在行&#xff0c;而是通过索引直接找到该行数据对应的物理地址&#xff0c…