简介：这份资源围绕K2算法从数据中学习贝叶斯网络结构这一主题展开，面向已具备概率图模型基础、希望动手实现结构学习的研究生与算法开发者，可用于课程实验、科研复现或小规模数据集上的建模验证。压缩包共7个文件，约10KB，以m脚本为主体，辅以一个C源码文件、一份mat数据样例和一份说明文本，脚本承担对象构造、评分函数与主流程调用等职责，C文件对应K2核心实现，mat样例便于直接加载数据跑通流程。目前已有2169人学习下载，说明其在贝叶斯网络结构学习入门实践中具有一定参考价值。读者可据此理解K2算法以节点序与父节点上限为输入、结合评分准则搜索最优结构的完整思路，并借助样例数据完成从数据到有向无环图的实验闭环，为后续对比其他评分搜索方法打下基础。

1. K2算法：为什么它敢在指数级的结构空间里“贪心”搜索

贝叶斯网络结构学习是个组合爆炸问题：n 个节点最多能组成 $n(n-1)/2$ 条有向边，可能的 DAG 数量随节点数超指数增长，节点数到两位数时穷举就已经不现实。K2 算法给出的答案很反直觉——它不搜索整个空间，而是先给节点排一个序，然后对每个节点只在其“前辈”里挑父节点，用贪心逐条加边，加不动就停。这个“先验排序 + 贪心打分”的组合，把结构学习从玄学式的全局搜索，变成了一个可复现、可解释的局部决策过程。搞懂 K2，等于搞懂了评分函数、父节点集合搜索、先验知识注入这三件事是怎么咬合在一起的，后面再看爬山法、MMHC 这些方法，底层逻辑都是同一套骨架。

2. 评分函数：K2 凭什么判断“这组父节点更好”

2.1 从联合概率到局部可分解

贝叶斯网络的核心假设是：给定父节点，每个节点条件独立于它的非后代。于是联合分布可以写成 $\prod_i P(X_i \mid Pa_i)$。结构学习的本质，是找一个父节点集合 $Pa_i$，让这个乘积在数据上出现的可能性最大。K2 用的是贝叶斯评分，不是最大似然——它把参数也当成随机变量积分掉，得到的是“这组父节点下，数据出现的边际似然”。

关键性质是局部可分解：整个网络的评分等于每个节点局部评分的和。这意味着给某个节点换父节点，不需要重算全图，只重算它自己的局部分数。常见的实现思路是维护一个local_score(node, parents)函数，父节点集合一变就单独调用它。这个性质是后面所有贪心搜索能跑起来的前提，没有它，每加一条边都要全图重算，复杂度直接翻倍。

2.2 K2 局部评分的具体形式

K2 评分针对离散变量，假设参数服从 Dirichlet 先验。对节点 $i$，父节点配置 $j$ 下取值 $k$ 的计数记为 $N_{ijk}$，评分写成：

$$ \text{score}(i, Pa_i) = \sum_{j=1}^{q_i} \left[ \log \frac{\Gamma(\alpha_{ij})}{\Gamma(\alpha_{ij} + N_{ij})} + \sum_{k=1}^{r_i} \log \frac{\Gamma(\alpha_{ijk} + N_{ijk})}{\Gamma(\alpha_{ijk})} \right] $$

其中 $q_i$ 是父节点配置数，$r_i$ 是节点取值数，$\alpha_{ijk}$ 是先验伪计数，通常取 1（均匀先验），$\alpha_{ij} = \sum_k \alpha_{ijk}$。这个式子的直觉是：它奖励“数据支持某种父节点配置”的情况，同时对父节点配置过多带来的稀疏性做惩罚——配置数 $q_i$ 越大，$\Gamma(\alpha_{ij})/\Gamma(\alpha_{ij}+N_{ij})$ 这一项越吃亏。这就是 K2 不会无脑加父节点的原因，惩罚是内建在评分里的，不需要额外加正则项。

import numpy as np from scipy.special import gammaln def k2_local_score(data, node, parents, r_i, alpha=1.0): """ data: shape (N, n) 的离散数据矩阵 node: 当前节点索引 parents: 父节点索引列表 r_i: 节点 node 的取值个数 alpha: Dirichlet 先验伪计数 """ N = data.shape[0] if len(parents) == 0: # 无父节点：只有一种配置 counts = np.bincount(data[:, node], minlength=r_i) score = gammaln(alpha) - gammaln(alpha + N) score += np.sum(gammaln(alpha + counts) - gammaln(alpha)) return score # 把父节点取值编码成配置编号 parent_vals = data[:, parents] config_ids = np.ravel_multi_index(parent_vals.T, [r_i] * len(parents)) q_i = r_i ** len(parents) score = 0.0 for j in range(q_i): mask = config_ids == j N_ij = mask.sum() if N_ij == 0: continue counts = np.bincount(data[mask, node], minlength=r_i) score += gammaln(alpha) - gammaln(alpha + N_ij) score += np.sum(gammaln(alpha + counts) - gammaln(alpha)) return score

这段代码里有两个容易翻车的点。第一，np.ravel_multi_index要求父节点取值从 0 开始连续编码，如果原始数据里有缺失值或者编码跳号，配置编号会错位，评分全乱。第二，q_i = r_i ** len(parents)在父节点多、取值多时会爆炸，比如 5 个父节点各 4 个取值就是 1024 种配置，每种配置平均分不到几个样本，评分里的稀疏惩罚会非常重——这其实是 K2 在替你踩刹车，但计算上要提前做配置数上限检查，否则内存和时间都扛不住。

2.3 为什么用 Gamma 函数而不是直接算阶乘

$\Gamma(n) = (n-1)!$，理论上可以直接用阶乘。但样本量上千时阶乘溢出，浮点数直接变 inf。gammaln是对数 Gamma，把乘法变成加法，数值稳定。这是血泪经验：早期实现里用math.factorial算似然，数据量一上来全是 nan，排查半天才发现是溢出。所有贝叶斯评分实现里，对数空间计算是标配，不是优化，是正确性要求。

3. 父节点集合搜索：K2 的贪心到底贪在哪

3.1 算法主循环的精确语义

K2 的搜索过程可以精确描述为：给定节点顺序 $\sigma$，对每个节点 $i$，候选父节点集合是排在 $i$ 前面的所有节点，记为 $Pred(i)$。从空集开始，每轮尝试把 $Pred(i)$ 中还没加入的节点逐个加进来，算局部评分，选提升最大的那个；如果最大提升为正，就正式加入，进入下一轮；如果所有候选都让评分下降，停止，当前集合就是 $i$ 的父节点。

这里有个细节常被忽略：K2 原文的停止条件是“评分不再增加”，但实现上通常要求严格增加才继续，否则在评分持平的边上会陷入无意义的循环尝试。另一个细节是候选父节点的遍历顺序——如果按节点索引顺序遍历，遇到第一个正提升就加，这叫 first-improvement；如果算完所有候选再选最好的，叫 best-improvement。K2 原始描述偏向后者，但很多实现为了省计算用前者，结果对节点顺序更敏感，这是踩坑高发区。

def k2_structure(data, order, r, max_parents=None, alpha=1.0): """ order: 节点顺序，list，前面的节点可以是后面节点的父节点 r: 每个节点的取值个数列表 max_parents: 父节点数量上限，防止配置爆炸 """ n = data.shape[1] dag = {i: [] for i in range(n)} for idx, node in enumerate(order): predecessors = order[:idx] current_parents = [] current_score = k2_local_score(data, node, [], r[node], alpha) while True: if max_parents is not None and len(current_parents) >= max_parents: break best_gain = 0.0 best_candidate = None for cand in predecessors: if cand in current_parents: continue trial = current_parents + [cand] trial_score = k2_local_score(data, node, trial, r[node], alpha) gain = trial_score - current_score if gain > best_gain: best_gain = gain best_candidate = cand if best_candidate is None: break current_parents.append(best_candidate) current_score += best_gain dag[node] = current_parents return dag

max_parents这个参数不是 K2 原文的东西，是工程上必须加的护栏。原因在 2.2 节说过：配置数随父节点数指数增长，不加限制的话，节点顺序靠后的节点候选父节点多，很容易在某个节点上把配置数撑到几千，单次评分计算就要遍历几千个空配置，整个算法从秒级退化到分钟级。常见的实现思路是设一个 3 到 5 的上限，或者按样本量动态算：配置数不超过样本量的十分之一。

3.2 节点顺序：K2 最大的先验，也是最大的软肋

K2 要求输入一个节点顺序，且只允许前面的节点当后面的节点的父节点。这个约束保证了输出一定是 DAG——因为边只能从序靠前指向序靠后，不可能成环。这是 K2 用先验换复杂度的核心交易：你告诉我一个合理的因果顺序，我保证不给你环，搜索空间从所有 DAG 缩到与这个顺序一致的 DAG。

代价也很直接：顺序错了，真结构就学不出来。如果真实边是从序后指向序前，K2 永远加不上这条边，评分再高也没用。所以实际使用时，节点顺序要么来自领域知识，要么先用别的办法（比如基于互信息的排序、或者对多个随机顺序跑多次取评分最高的）粗排一下。我一般会这么理解：K2 不是“学习”结构，是“在给定因果序下做父节点选择”，把它当纯黑盒结构学习器用，翻车是迟早的事。

3.3 和爬山法的本质差别

爬山法（hill climbing）从空图或随机图出发，做加边、删边、转边三种操作，每步选评分提升最大的操作，直到局部最优。它不要求节点顺序，搜索空间是所有 DAG，但需要每步检查操作后是否成环，检查本身有开销，而且容易卡在局部最优，通常要配合随机重启或 tabu 列表。

K2 的差别在于：它把“不成环”这个约束前置到了输入里，搜索过程中完全不用做环检测，每一步都是独立的父节点集合扩展。这让 K2 的实现极简，单次运行极快，但代价是顺序先验的强假设。两者不是谁替代谁的关系——K2 适合领域知识能给出大致因果序、样本量中等、追求可解释性的场景；爬山法适合顺序完全未知、愿意用计算换搜索广度的场景。很多工具库里两者并存，K2 常被当作“有先验时的快速基线”。

4. 避坑与排查：K2 跑出来的结构不对劲，先查这几处

4.1 学出来的图边特别少，几乎全是孤立节点

现象：跑完 K2，每个节点的父节点集合都是空的，或者只有一两条边，和预期差很远。

原因：最常见的是评分里的稀疏惩罚被数据放大。样本量小、节点取值多、父节点配置数一上去，每种配置下样本寥寥，$\Gamma$ 项的惩罚压过了数据支持带来的增益，任何加父节点的尝试都是负提升，算法在第一轮就停了。另一个可能是数据离散化太粗或太细，取值分布极度不均衡，某些配置下计数为 0，评分贡献接近零。

解决：先看样本量和配置数的比值，配置数超过样本量十分之一就调小max_parents或者合并取值。再检查每个节点的取值分布，出现某个取值占比超过 90% 的情况，考虑重新离散化。最后确认alpha没被设成很小的值——alpha太小会让先验过强，数据说话的分量不够。

4.2 明明有强相关的两个变量，边却加不上

现象：两个变量在数据里相关性很明显，但 K2 输出的图里没有这条边。

原因：九成是节点顺序问题。如果强相关的边方向是从序后指向序前，K2 的候选父节点集合里根本不含这个方向，永远加不上。剩下的一成是这条边被别的父节点“解释掉”了——条件独立检验下，给定其他父节点后这两个变量不再独立增益，评分不涨。

解决：把这两个变量的顺序对调再跑一次，看边是否出现。如果出现，说明顺序先验和真实因果方向冲突，需要重新审视顺序来源。如果对调后还是不出现，用互信息或条件互信息单独验证这两个变量的依赖关系，确认是不是被其他变量中介了。

4.3 同一个数据集跑两次，结果不一样

现象：数据没变，代码没变，两次运行的边集不同。

原因：如果实现里用了字典遍历或者集合遍历来选候选父节点，Python 的哈希随机化会导致遍历顺序在不同进程间不同，first-improvement 策略下先遇到哪个正提升就加哪个，结果自然不稳定。另一个可能是浮点累加顺序不同导致的评分微小差异，在评分持平的边上被放大成不同的选择。

解决：候选父节点遍历前先排序，固定顺序。评分比较时加一个极小的容差（比如1e-9），避免浮点噪声决定边。如果用了并行计算局部评分，确保归约顺序确定。

4.4 节点一多就卡死或者内存爆掉

现象：节点数到二三十，运行时间从秒级跳到几分钟，内存占用飙升。

原因：q_i = r_i ** len(parents)的指数爆炸，加上每个候选父节点都要重算局部评分，候选数乘以配置数，复杂度是 $O(n^2 \cdot q)$ 量级。如果实现里还对每个配置做了全量数据 mask，内存里反复生成布尔数组，开销更大。

解决：加max_parents硬上限；局部评分里用配置计数缓存，同一组父节点配置只遍历一次数据；对父节点候选做预剪枝，先用互信息筛掉明显无关的候选，再进 K2 主循环。这些不是算法层面的改动，是工程护栏，但不加的话 K2 在中等规模数据上根本跑不完。

5. 设计取舍：K2 用先验换确定性，这笔交易划不划算

K2 最值得琢磨的地方，是它把结构学习里最难的部分——保证无环——用“输入一个顺序”这个看似粗暴的方式解决了。所有 DAG 搜索方法都要面对环检测，要么在搜索中动态检查，要么在评分里加惩罚，要么用复杂的图论操作。K2 直接说：你给顺序，我保证无环。这是一个非常工程化的取舍，用领域先验换掉了搜索过程中最贵的那部分计算。

这笔交易划不划算，取决于顺序先验的质量。顺序完全正确时，K2 又快又准，单次运行复杂度接近 $O(n^2 \cdot \bar{q})$，比爬山法低一个量级。顺序部分正确时，K2 会漏掉反向边，但不会产生假边——它只会少学，不会乱学，这个性质在某些场景下比召回率更重要。顺序完全错误时，K2 退化成只能学同向边的弱学习器，这时候应该换方法，而不是硬调参数。

验证 K2 结果是否可信，我习惯做两件事。一是顺序敏感性测试：对节点顺序做若干次随机扰动（保持局部相邻节点交换），看学出的边集变化有多大，变化剧烈说明顺序先验不稳，结果不能直接信。二是留出数据做似然检验：用学出的结构在留出集上算对数似然，和空图、全连接图（受max_parents限制）对比，确认结构确实带来了泛化增益，而不是过拟合了训练集的噪声。

进阶方向上，K2 的评分函数可以换成 BDeu、BIC，搜索策略可以从贪心换成对父节点集合做精确动态规划（父节点数少时可行），顺序先验也可以从硬约束放松成软偏好，在评分里加一个顺序一致性的先验项。这些变体的骨架都是 K2 这一套：局部可分解评分 + 父节点集合搜索 + 先验约束。把 K2 的这三个部件拆清楚，再看别的结构学习算法，基本都能对上号。

从那以后我每次用 K2，都强制先跑一遍顺序敏感性测试，顺序不稳就先解决顺序问题，绝不直接拿结果去下游建模。希望帮到你。

本文还有配套的精品资源，点击获取