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

ops/2024/12/21 13:05:48/

基于规则的分类器: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/ops/143763.html

相关文章

第一章 操作系统引论

本文总结了操作系统第一章的重点知识,非常时候预习和复习的小伙伴们。大家可以根据目录先考考自己能回忆起多少知识! 目录 1、 理解操作系统的目标、作用和定义 2、 脱机 I/O 方式 3、 多道程序设计的概念及引入的原因 4、 多道批处理系统的优缺点 …

barin.js(十四)GRU实战教程 - 文本情感分析之有害内容检测

系列文章: (一):brain.js概要介绍(二):项目集成方式(三):手把手教你配置和训练神经网络(四):利用异步训练和交叉验证来优…

uniapp小程序抽奖怎么做?直接使用【almost-lottery转盘组件】或者【自定义宫格转盘】

直接使用almost-lottery 地址:GitHub - ialmost/almost-components_uniapp: uni-app 使用的多端组件集合,支持APP、H5、小程序uni-app 使用的多端组件集合,支持APP、H5、小程序. Contribute to ialmost/almost-components_uniapp developmen…

图书馆管理系统(四)基于jquery、ajax--完结篇

任务3.6 后端代码编写 任务描述 这个部分主要想实现图书馆管理系统的后端,使用 Express 框架来处理 HTTP 请求,并将书籍数据存储在一个文本文件 books.txt 中。 任务实施 3.6.1 引入模块及创建 Express 应用 const express require(express); cons…

同源策略:为什么XMLHttpRequest不能跨域请求资源?

一.浏览器安全 浏览器安全可以分为三大块——Web页面安全、浏览器网络安全****和浏览器系统安全 假设,如果页面中没有安全策略的话,Web世界会是什么样子的呢? Web世界会是开放的,任何资源都可以接入其中,我们的网站可…

Docker镜像制作

目录 1. 镜像制作的原因和方式2. 快照方式制作镜像2.1 docker commit命令来制作镜像2.2 实战C HelloWorld 镜像制作 3. Dockerfile 制作镜像3.1 Dockerfile 是什么3.2 为什么需要 Dockerfile3.3 Dockerfile 指令3.3.1 指令清单3.3.2 FROM指令3.3.3 MAINTAINER指令3.3.4 LABEL指…

【WPF】把DockPanel的内容生成图像

要在WPF中将一个 DockPanel 的内容生成为图像并保存,可以按照与之前类似的步骤进行,但这次我们将专注于 DockPanel 控件而不是整个窗口。 DockPanel的使用 WPF(Windows Presentation Foundation)中的 DockPanel 是一种布局控件&…

Hive内部表和外部表的区别

Hive是基于Hadoop的数据仓库工具,hive本身并不存储数据,而是将表数据文件存储在hdfs中,hive能将此数据文件映射为一张表,并提供解析编译sql的功能,将用户提交的sql转换为mr job,在mapreduce引擎上对数据进行…