贝叶斯规则列表

知识点概述

贝叶斯规则列表（Bayesian Rule Lists, BRL）是一种结合了“频繁模式挖掘”和“贝叶斯统计”的决策列表学习算法。它的目标是生成一个简短的、有序的IF-THEN规则列表，这个列表不仅在数据上表现准确，而且本身具有很高的可解释性。

贝叶斯规则列表 (Letham 等人, 2015)[18] (Bayesian Rule Lists) 或简称为 BRL。BRL 使用贝叶斯统计从频繁模式中学习决策列表, 这些频繁模式已使用 FP-tree (Borgelt, 2005)[19] 算法进行了预先挖掘。

BRL算法的流程分为两个主要步骤：

目标: 从原始数据集中找出频繁出现的特征值组合（即“模式”）。这些模式将作为后续构建决策规则的“条件”部分的候选集。
方法: 使用频繁项集挖掘算法，如 Apriori 或 FP-Growth。
过程:
1. 设定一个最小支持度 (Support) 阈值。
2. 算法找出数据集中出现频率高于该阈值的所有单个特征值（如 size=medium）。
3. 然后，算法迭代地将这些频繁模式组合成更高阶的模式（如 size=medium AND location=bad），并保留那些仍然满足最小支持度阈值的组合。
结果: 得到一个包含大量潜在规则条件的“模式池”。

目标: 从上一步的“模式池”中，选择一个最优的子集，并将它们排列成一个有序的决策列表。
方法: BRL将这个问题构建为一个贝叶斯模型。它定义了一个包含先验分布 (Prior) 和似然 (Likelihood) 的后验分布 (Posterior)，然后通过采样来寻找后验概率最大的那个决策列表。
贝叶斯模型的组成:
- 先验分布: 体现了我们对“好”的决策列表的偏好。BRL的先验假设是：
  - 列表应该很短（包含的规则数量少）。
  - 每条规则的条件也应该很短（包含的特征组合少）。
- 似然: 衡量一个给定的决策列表在多大程度上能够准确地拟合（解释）训练数据。
- 后验分布: 结合了先验和似然，后验 ∝ 似然 × 先验。一个好的决策列表，既要能很好地拟合数据（高似然），又要满足我们对简洁性的要求（高先验概率）。
学习过程:
1. 初始化: 随机生成一个初始的决策列表。
2. MCMC采样: 使用马尔可夫链蒙特卡洛（MCMC）方法，通过迭代地对当前列表进行微小的修改（如添加、删除或移动规则）来从后验分布中采样大量的候选决策列表。
3. 选择最佳: 最后，从所有采样的列表中，选择那个具有最高后验概率的列表作为最终模型。