基于规则的分类器：Classification using rule based classifier
互斥规则（Mutually exclusive rules）：
分类器包含互斥规则，如果这些规则彼此独立。
每条记录最多被一条规则覆盖。
穷尽规则（Exhaustive rules）：
如果分类器能够考虑到属性值的所有可能组合，那么它具有穷尽的覆盖。
每条记录至少被一条规则覆盖。
这些概念在设计和评估分类系统时非常重要，因为它们确保了分类器的完整性和准确性。互斥规则确保了分类的明确性，而穷尽规则则确保了分类的全面性。
无监督规则发现Unsupervised Rule Discovery
给定一组记录，每组记录都包含给定集合中的一定数量的项目之后生成依赖规则，根据其他项目的出现情况预测项目的出现情况。
规则的使用
规则并不代表两个项目集之间的任何因果关系或相关性。
这些规则有助于市场营销、有针对性的广告、楼层规划、库存控制、流失管理、国土安全、...
监督学习：顺序覆盖算法 Supervised learning: sequential covering algorithm
- 从一个空规则开始。
- 使用“Learn-One-Rule”函数来扩展规则。
- 移除被规则覆盖的训练记录。
- 重复步骤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} 可以生成以下关联规则：
-
Clothes → Milk, Chicken [sup = 3/7, conf = 3/3]
- 这个规则表示在包含“Clothes”的交易中，同时包含“Milk”和“Chicken”的概率是100%（3/3），因为“Clothes”在所有包含它的交易中都与“Milk”和“Chicken”一起出现。
-
Clothes, Chicken → Milk [sup = 3/7, conf = 3/3]
- 这个规则表示在同时包含“Clothes”和“Chicken”的交易中，包含“Milk”的概率是100%（3/3），因为每当“Clothes”和“Chicken”一起出现时，“Milk”也总是出现。
总结
这个例子展示了如何从交易数据中识别频繁项集，并通过这些项集生成关联规则。频繁项集和关联规则的发现是市场篮子分析中的关键步骤，可以帮助企业了解产品之间的关联性，从而优化产品摆放、促销策略等。在这个例子中，所有生成的规则都满足最小支持度和最小置信度的要求，因此被认为是有趣的。
Apriori算法概述
- Apriori算法：可能是最知名的关联规则学习算法。
算法的两个步骤
-
寻找频繁项集：
- 找出所有支持度大于或等于最小支持度阈值的项集。这些项集被称为频繁项集（frequent itemsets），有时也称为大项集（large itemsets）。
-
生成规则：
- 使用找到的频繁项集来生成关联规则。
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 的支持度相同。
- 置信度（Confidence）：Confidence(A → B) ≥ minconf。置信度是衡量在 A 出现的情况下 B 也出现的概率，计算公式为
生成规则的步骤概述：
- 确定频繁项集：首先，通过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模型，可以更有效地控制规则的数量和质量。这种方法可以在保持算法效率的同时，提高规则的相关性和实用性。
总结：
关联规则挖掘在数据挖掘领域已经被广泛研究。
存在许多高效的算法和模型变体。
其他相关工作包括：
多层次或广义规则挖掘：这涉及到挖掘不同抽象层次上的规则，或者挖掘具有更广义条件的规则。
约束规则挖掘：在挖掘过程中加入特定的约束条件，以满足特定的业务需求或数据特性。
增量规则挖掘：随着新数据的不断加入，更新现有的关联规则，而不是每次都重新挖掘整个数据集。
最大频繁项集挖掘：寻找在数据集中出现频率最高的项集，这些项集可能不包含在任何更大的频繁项集中。
数值关联规则挖掘：处理数值型数据，挖掘数值项之间的关联规则。
规则有趣性度量和可视化：评估规则的有趣性，并通过可视化技术展示规则，以便于理解和分析。
并行算法：利用多处理器或分布式计算资源来加速关联规则挖掘过程。