08 · 关联规则算法

一、关联规则与"购物篮分析"

关联规则（Association Rules）挖掘的核心目标是：在大量事务（transaction）记录中，自动找出那些"经常同时出现"的项目组合，并用量化指标衡量其关联程度。最经典的场景是超市的购物篮分析——通过分析数百万张购物小票，发现"买了 A 的顾客通常也会买 B"这样的规律，用于指导商品摆放与捆绑促销。

这种思路天然契合医学数据：一位患者的一次就诊，就是一个"购物篮"，其中装的是药物、检查项目、诊断标签等。通过关联规则挖掘，可以从大量医疗记录中发现隐藏的处方模式、诊断共现规律、高风险检查组合等临床知识。

1.1 问题背景与经典示例

1.2 事务数据格式

关联规则挖掘的输入是事务数据库，每条记录（事务）包含一组项（item）。常见的存储格式有两种：

1.3 支持度、置信度与提升度

关联规则的"质量"由三个核心指标衡量。直观上：

1.4 指标公式与数值示例

设有 \(N\) 条事务，项集 \(X\)、\(Y\) 互不相交，规则为 \(X \Rightarrow Y\)：

数值计算示例：假设有 100 条就诊记录：

• 含"二甲双胍"：30 条，\(\text{supp}(\text{二甲双胍}) = 0.30\)
• 含"他汀"：40 条，\(\text{supp}(\text{他汀}) = 0.40\)
• 同时含二者：18 条，\(\text{supp}(\text{二甲双胍} \cup \text{他汀}) = 0.18\)

规则"二甲双胍 ⇒ 他汀"的各项指标：

提升度 1.5 说明：使用二甲双胍的患者开具他汀的概率是随机情况的 1.5 倍，符合"糖尿病合并心血管风险患者联用调脂药"的临床指南。

二、Apriori 算法

Apriori 算法（Agrawal & Srikant，1994）是最经典的关联规则挖掘算法。其名称来自拉丁语"先验的"，反映了算法利用先验知识（频繁项集的子集必须是频繁的）来剪枝加速搜索的核心思想。

2.1 反单调性与剪枝原理

2.2 逐层搜索流程详解

Apriori 采用逐层（level-by-level）搜索策略，从 1-项集开始，每层扫描一次完整数据库：

1. 扫描数据库：统计所有单项的支持度，保留 \(\geq \text{minsup}\) 的项，得到频繁 1-项集 \(L_1\)。
2. 连接（Join）：将 \(L_{k-1}\) 中任意两个具有相同 \((k-2)\) 个前缀项的频繁项集合并，生成候选 \(k\)-项集 \(C_k\)。
3. 剪枝（Prune）：对 \(C_k\) 中每个候选，检查其所有 \((k-1)\)-项子集是否都在 \(L_{k-1}\) 中；否则删除该候选。
4. 扫描数据库：计算 \(C_k\) 中各候选的支持度，保留 \(\geq \text{minsup}\) 的候选，得到 \(L_k\)。
5. 重复步骤 2–4，直到 \(L_k\) 为空，算法终止，合并所有 \(L_k\) 得到全部频繁项集。
6. 生成规则：对每个频繁项集枚举前后件组合，按置信度阈值筛选（见 2.3 节）。

2.3 从频繁项集生成规则

找到所有频繁项集后，对每个大小 \(\geq 2\) 的频繁项集 \(I\)，枚举其所有非空真子集 \(S\)，构成规则 \(S \Rightarrow (I \setminus S)\)，计算置信度：

保留置信度 \(\geq \text{minconf}\) 的规则。规则生成步骤同样可利用反单调性：若 \(S \Rightarrow (I \setminus S)\) 置信度不满足，则部分前缀规则也可快速剪枝。

2.4 R 中使用 arules::apriori

在 R 中，arules 包提供完整的 Apriori 实现，配套 arulesViz 包用于可视化。下面用经典 Groceries 事务数据集演示完整流程。

options(repos = c(CRAN = "https://mirrors.tuna.tsinghua.edu.cn/CRAN/"))
install.packages(c("arules", "arulesViz"))

library(arules)
data("Groceries")

# 查看数据基本信息：9835 条事务，169 个商品
Groceries
summary(Groceries)

# 查看前 5 条事务内容
inspect(head(Groceries, 5))

# 各商品出现频率（前 15 高频项）
itemFrequency(Groceries)[
  order(itemFrequency(Groceries), decreasing = TRUE)
][1:15]

# 频率条形图
itemFrequencyPlot(Groceries, topN = 15,
                  main = "Top 15 高频商品",
                  col  = "#b2dfdb")

# ── 运行 Apriori ──────────────────────────────────────────
rules <- apriori(
  Groceries,
  parameter = list(
    supp   = 0.01,   # 最小支持度（约 98 条事务中出现）
    conf   = 0.5,    # 最小置信度
    minlen = 2,      # 至少 2 个项（排除空前件）
    maxlen = 5       # 最多 5 个项
  )
)

rules
# 按提升度从高到低排序，查看前 10 条
rules_sorted <- sort(rules, by = "lift", decreasing = TRUE)
inspect(head(rules_sorted, 10))

# ── 筛选感兴趣的规则 ──────────────────────────────────────
# 后件为 "whole milk" 的规则
rules_milk <- subset(rules, rhs %in% "whole milk")
inspect(sort(rules_milk, by = "lift"))

# 前件包含 "yogurt" 的规则
rules_yogurt <- subset(rules, lhs %in% "yogurt")
inspect(rules_yogurt)

# lift > 2 的强关联规则
rules_strong <- subset(rules, lift > 2)
inspect(sort(rules_strong, by = "confidence", decreasing = TRUE))

关键参数说明：

• supp：最小支持度，越低挖掘到的规则越多，计算量越大。医学数据样本量较小（几百条）时可设 0.05–0.1。
• conf：最小置信度，通常 ≥ 0.5，过低会产生大量弱规则。
• minlen / maxlen：规则最小/最大项数，minlen=2 排除无前件的单项规则，maxlen 不宜太大（规则难以解读）。

三、FP-Growth 算法

FP-Growth（Han et al.，2000）针对 Apriori 中"候选项集过多、多次扫描数据库"的性能瓶颈提出改进：将整个事务数据库压缩存储为一棵紧凑的前缀树（FP-Tree），然后在树上递归挖掘，完全不生成显式候选项集。

3.1 FP-Tree 的构建过程

FP-Tree 的构建只需两次扫描数据库：

1. 第一次扫描：统计各项支持度，删去不频繁项，将频繁项按支持度从高到低排序。
2. 第二次扫描：对每条事务，将其频繁项按排好的顺序提取出来，逐项插入 FP-Tree：从根节点出发，已存在的子节点计数加 1；否则新建节点，计数初始化为 1。相同前缀的事务会共享路径节点。

3.2 条件模式基与递归挖掘

FP-Tree 构建后，挖掘过程利用条件模式基（Conditional Pattern Base）递归进行：

1. 从支持度最低的频繁项（树最底层）开始，找出该项在 FP-Tree 中所有路径（前缀路径）。
2. 每条前缀路径的计数 = 路径末端该项节点的计数，由此构成该项的条件模式基。
3. 在条件模式基上重建一棵小 FP-Tree（条件 FP-Tree），去掉不满足 minsup 的项。
4. 在条件 FP-Tree 上递归执行，直到树为空或只剩单条路径（直接枚举路径上的所有项集组合）。
5. 将递归挖掘到的项集与当前处理的项合并，得到包含该项的所有频繁项集。

3.3 与 Apriori 的对比

四、规则评估与筛选

关联规则挖掘往往产生数百乃至数千条规则，如何筛选出真正有价值的规则是实际应用的关键。除三大核心指标外，还有一些补充性指标和可视化手段。

4.1 提升度的深入理解

提升度有一个容易被忽视的性质：它关于 \(X\) 和 \(Y\) 是对称的，即 \(\text{lift}(X \Rightarrow Y) = \text{lift}(Y \Rightarrow X)\)。这意味着提升度衡量的是双向关联强度，而置信度是有方向的。因此，规则"二甲双胍 ⇒ 他汀"和"他汀 ⇒ 二甲双胍"的提升度相同，但置信度可能不同——在临床解读时，高置信度的方向往往更有实际意义（"见到 A 就几乎必然有 B"）。

4.2 其他评估指标

4.3 规则可视化

arulesViz 包提供多种可视化方法，帮助从大量规则中快速发现最值得关注的规则：

library(arules)
library(arulesViz)
data("Groceries")

rules <- apriori(
  Groceries,
  parameter = list(supp = 0.01, conf = 0.5, minlen = 2)
)

# 1）散点图：横轴支持度，纵轴置信度，颜色=提升度
#    颜色深（提升度高）且支持度高的规则最有价值
plot(rules,
     measure  = c("support", "confidence"),
     shading  = "lift",
     main     = "规则散点图（颜色 = 提升度）")

# 2）分组矩阵图：行=LHS，列=RHS，圆圈大小=支持度
plot(head(sort(rules, by = "lift"), 20),
     method = "grouped",
     main   = "前 20 条高提升度规则矩阵气泡图")

# 3）网络关系图：节点为项，边为规则
plot(head(sort(rules, by = "lift"), 15),
     method = "graph",
     main   = "规则网络图")

# 4）平行坐标图：每条线是一条规则
plot(head(sort(rules, by = "lift"), 20),
     method = "paracoord")

五、医学场景示例：处方/检查组合

下面给出一个模拟的处方/检查数据完整示例，演示从数据整理、事务转换、规则挖掘到可视化报告的全流程。真实项目中，只需将示例数据替换为自己的 EMR/处方数据，代码结构基本可直接复用。

5.1 数据整理为"事务"

医疗信息系统导出的处方数据通常是长表格式（每行一条"就诊-药物/检查"记录），需先按就诊 ID 聚合，转换为 arules 所需的 transactions 对象。

library(arules)

# ── 模拟处方/检查数据（长表格式） ────────────────────────
presc_long <- data.frame(
  visit_id = c(
     1,  1,  1,  1,
     2,  2,  2,
     3,  3,  3,  3,
     4,  4,  4,
     5,  5,
     6,  6,  6,
     7,  7,  7,  7,
     8,  8,
     9,  9,  9,
    10, 10, 10
  ),
  item = c(
    "二甲双胍", "胰岛素",   "血糖",     "糖化血红蛋白",
    "ACEI",     "利尿剂",   "肌酐",
    "二甲双胍", "他汀",     "血脂",     "空腹血糖",
    "头孢",     "布洛芬",   "血常规",
    "二甲双胍", "他汀",
    "ACEI",     "他汀",     "阿司匹林",
    "胰岛素",   "二甲双胍", "血糖",     "血脂",
    "头孢",     "血常规",
    "ACEI",     "利尿剂",   "血钾",
    "他汀",     "阿司匹林", "血脂"
  ),
  stringsAsFactors = FALSE
)

# 按 visit_id 聚合为 list，转为 transactions 对象
presc_split <- split(presc_long$item, presc_long$visit_id)
presc_trans <- as(presc_split, "transactions")

presc_trans
summary(presc_trans)
inspect(presc_trans)

# 各项目出现频率条形图
itemFrequencyPlot(presc_trans,
                  topN = 12,
                  type = "relative",
                  main = "各药物/检查出现频率",
                  col  = "#b2dfdb")

5.2 规则挖掘与解读

# ── Apriori 挖掘 ─────────────────────────────────────────
rules_rx <- apriori(
  presc_trans,
  parameter = list(
    supp   = 0.2,    # 10 条记录中至少 2 条出现
    conf   = 0.6,
    minlen = 2,
    maxlen = 4
  )
)

rules_rx
# 按提升度排序，查看全部规则
inspect(sort(rules_rx, by = "lift", decreasing = TRUE))

# 前件为"二甲双胍"的规则：糖尿病处方模式
rules_dm <- subset(rules_rx, lhs %in% "二甲双胍")
inspect(sort(rules_dm, by = "confidence", decreasing = TRUE))

# 后件为"他汀"的规则：哪些情况下会联用调脂药？
rules_statin <- subset(rules_rx, rhs %in% "他汀")
inspect(sort(rules_statin, by = "lift", decreasing = TRUE))

# ACEI 相关规则（降压药联用模式）
rules_acei <- subset(rules_rx, items %in% "ACEI")
inspect(sort(rules_acei, by = "lift", decreasing = TRUE))

5.3 可视化与结果报告

library(arulesViz)

# 散点图：观察支持度-置信度-提升度的整体分布
if (length(rules_rx) > 0) {
  plot(rules_rx,
       measure = c("support", "confidence"),
       shading = "lift",
       main    = "处方关联规则分布（颜色=提升度）")
}

# 网络图：节点为药物/检查，边为关联规则
plot(rules_rx,
     method = "graph",
     main   = "处方关联规则网络图")

# ── 生成可报告的规则汇总表 ────────────────────────────────
rules_df <- as(rules_rx, "data.frame")

# 格式化数值
rules_df$support    <- round(rules_df$support,    3)
rules_df$confidence <- round(rules_df$confidence, 3)
rules_df$lift       <- round(rules_df$lift,       3)
rules_df$coverage   <- round(rules_df$coverage,   3)

# 按提升度排序，查看前 15 条
head(rules_df[order(rules_df$lift, decreasing = TRUE), ], 15)

# 导出 CSV，方便后续在 Word/Excel 整理
write.csv(
  rules_df[order(rules_df$lift, decreasing = TRUE), ],
  file      = "association_rules_results.csv",
  row.names = FALSE
)

在实际大规模处方数据挖掘中，还可以进一步：

• 按科室、病种、时间段分层挖掘，找出不同亚组的特异性处方模式。
• 结合不良事件、再入院、住院费用等结局，识别潜在的高风险药物组合。
• 用网络中心性分析识别核心节点（高连接度的关键药物/检查项目）。
• 与临床药师合作，对高提升度的意外规则进行人工审核，区分"真实临床模式"与"数据噪声"。
• 在大数据平台上（如 Spark MLlib 的 FP-Growth）处理千万级就诊记录。

六、实战案例

中医药预防结直肠癌术后复发的关联规则分析，展示如何将关联规则算法应用于中医药处方分析，以探索预防结直肠癌术后复发的用药规律。

6.1 研究背景与目的

结直肠癌（CRC）是全球常见的恶性肿瘤，具有高发病率和死亡率，复发是患者死亡的主要原因。尽管手术技术和药物治疗取得了显著进展，但根治性切除和抗癌治疗后的复发仍然是CRC管理中的主要挑战。据流行病学数据显示，约20%接受根治性手术的患者在5年内会经历肿瘤复发，且复发率随肿瘤分期增加而升高。

中医药通过整体认知方法确定草药治疗策略，在延缓肿瘤疾病进展和提高患者生活质量方面显示出显著疗效。然而，由于临床医生个性化辨证推理和经验知识的差异，草药处方策略存在差异，对复方配伍规律的系统理解仍不足。

研究目的：基于高水平证据和临床应用，识别明确有效的中医药处方，通过关联规则和复杂网络社区算法等方法，系统探索预防和治疗CRC复发的中医药配方配伍原则。

6.2 研究方法

6.3 研究结果

6.3.1 草药组成与特性分析

对38个处方的分析显示，这些处方由多种草药组合而成，最终包含185种不同的草药。草药的性味分析表明，大多数草药具有收敛和苦味特性。从药性功能角度，这些草药主要对应寒凉性质。根据中医理论，清热、止血、化瘀、燥湿是这些草药的核心功能，符合CRC复发的病机需求。

6.3.2 关联规则分析

使用基于Apriori的关联规则分析38个处方，共识别出36条有效关联规则。以提升度为排序标准，关联规则"莪术、黄芪→三棱"显示出最高的提升度。在该规则下，当处方中存在莪术和黄芪的组合时，三棱的出现概率达到100%（置信度=1）。同时，与单独使用三棱的概率相比，这种组合可以将使用三棱的可能性提高11倍。

此外，规则"莪术、黄芪→三棱"和"三棱、黄芪→莪术"之间存在交互选择现象，表明莪术、黄芪和三棱在配伍中可能发挥协同作用，这与中医经典配伍原则高度一致，即"相须"（性质相似的草药配伍以增强功效）或"相使"（主药与辅助药配伍以提高主药的功效）。

6.3.3 网络分析

为更准确地展示关联规则之间的内在联系，构建了网络图。同时，应用复杂网络社区算法探索这些草药中的关键节点网络。结果显示，所有包含的草药可分为6个独立社区，其中黄芪和莪术属于社区1。这进一步证实了三种草药之间密切的配伍关联，形成了上述关联规则的补充。

6.3.4 靶基因和通路富集分析

结合Apriori关联规则和复杂网络社区算法的结果，最终确定黄芪、三棱和莪术为后续研究的核心组合草药。GO功能富集分析显示，靶基因在生物过程（BP）、细胞成分（CC）和分子功能（MF）中具有重要作用。在BP中，它们参与对外部刺激和氧化应激的反应，与肿瘤微环境和代谢重编程有关。在CC中，它们富集在脂筏和突触后膜中，表明在细胞信号传导和转运中的作用。在MF中，它们参与转录因子结合和核受体活性，强调了它们在基因表达和信号传导中的重要性。

KEGG通路富集分析表明，筛选出的潜在靶基因显著富集在包括脂质和动脉粥样硬化、化学致癌-受体激活、前列腺癌、IL17信号通路和TNF信号通路等通路中。多个靶基因集中在与肿瘤发生发展、炎症反应和代谢紊乱密切相关的通路中，进一步证实了这种草药组合在CRC复发预防中的潜在作用。

6.4 实验验证

研究进一步通过体外实验验证了核心草药组合的活性成分（如槲皮素和山柰酚）对结直肠癌细胞的影响，包括细胞活力、细胞周期、凋亡、迁移和侵袭等方面。实验结果表明，这些活性成分能够抑制结直肠癌细胞的增殖和迁移，诱导细胞凋亡，从而发挥潜在的抗肿瘤作用。

6.5 研究结论与临床意义

本研究通过关联规则和网络分析等数据挖掘方法，系统探索了中医药预防和治疗CRC复发的配方配伍原则。研究结果表明，黄芪、三棱和莪术是预防CRC复发的核心草药组合，其潜在机制可能通过调节多个与肿瘤发生发展相关的信号通路实现。

临床意义：

• 为中医药在CRC术后预防和治疗中的临床应用提供了科学依据
• 有助于标准化中医药处方策略，减少因医生经验差异导致的处方 variability
• 为开发更有效的中医药复方提供了理论基础
• 展示了数据挖掘技术在中医药研究中的应用价值

七、小结与练习

本章系统介绍了关联规则挖掘的完整体系：从三大核心指标（支持度、置信度、提升度）的数学定义与直觉理解，到两种经典算法（Apriori 与 FP-Growth）的原理与对比，再到规则评估筛选和医学场景的实战示例。主要知识点归纳：

• 支持度衡量规则的普遍性（出现频率），置信度衡量规则的准确率（条件概率），提升度是去除后件基础概率后的真实关联强度——三者结合才能筛选出有价值的规则。
• Apriori 利用反单调性剪枝，逐层搜索频繁项集，思路清晰适合教学；多次数据库扫描和候选集爆炸是主要瓶颈。
• FP-Growth 将数据压缩为 FP-Tree，仅需两次扫描，无需显式候选项集，在大规模、低支持度场景下性能显著优于 Apriori。
• 医学应用中需结合临床知识解读规则，区分"合理处方模式验证"、"新处方知识发现"和"潜在风险信号预警"三类场景。