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

news/2024/12/20 20:51: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/news/1556731.html

相关文章

D99【python 接口自动化学习】- pytest进阶之fixture用法

day99 pytest使用conftest管理fixture 学习日期:20241216 学习目标:pytest基础用法 -- pytest使用conftest管理fixture 学习笔记: fixture(scope"function") conftest.py为固定写法,不可修改名字,使用c…

集团业务发展与数字化转型建设统一规划项目案例(365页PPT)

方案介绍: 随着信息技术的飞速发展和市场竞争的日益激烈,数字化转型已成为企业提升竞争力、实现可持续发展的关键路径。某大型集团企业,作为行业内的佼佼者,深刻认识到数字化转型对于推动业务创新、优化运营流程、提升客户体验的…

在 Windows 上添加 github SSH 密钥

在 Windows 上添加 SSH 密钥的步骤如下: 1. 检查是否已有SSH密钥 首先,打开 Git Bash 或 Windows Terminal,输入以下命令查看是否已有 SSH 密钥: ls -al ~/.ssh如果你看到 id_rsa 和 id_rsa.pub(或其他的文件名以 .…

从机器人到高速线,线缆行业如何提升竞争力

【哔哥哔特导读】机器人行业发展有何新趋势?AI高速线的竞争格局如何?线缆行业如何避免“内卷式竞争”?对话业内人士,解析行业最新发展趋势。 当前,机器人作为热门市场,成为智能制造整体战略方向中的重要板…

[LeetCode-Python版] 876. 链表的中间结点

题目 给你单链表的头结点 head ,请你找出并返回链表的中间结点。 如果有两个中间结点,则返回第二个中间结点。 示例 1: 输入:head [1,2,3,4,5] 输出:[3,4,5] 解释:链表只有一个中间结点,值为…

LeetCode 刷题笔记

LeetCode 刷题笔记 1. 20241218 &#xff08;1&#xff09;2447 std::gcd是C17引入的一个函数&#xff0c;用于计算两个整数的最大公因数。位于<numeric>头文件中。 #include <iostream> #include <numeric> // std::gcdint main() {int a 36;int b 60…

BlueLM:以2.6万亿token铸就7B参数超大规模语言模型

一、介绍 BlueLM 是由 vivo AI 全球研究院自主研发的大规模预训练语言模型&#xff0c;本次发布包含 7B 基础 (base) 模型和 7B 对话 (chat) 模型&#xff0c;同时我们开源了支持 32K 的长文本基础 (base) 模型和对话 (chat) 模型。 更大量的优质数据 &#xff1a;高质量语料…

使用Python进行excel的数据简单分析

Python代码&#xff0c;需要将处理后分析得到的数据存储到与当前目录下的一个Excel文件中去。 完整的Python代码&#xff08;初&#xff09;&#xff1a; import pandas as pd import os# 读取Excel文件 file_path 供应链分析.xlsx excel_data pd.ExcelFile(file_path)# 读取…