简介：这份资源围绕K2算法从数据中学习贝叶斯网络结构这一经典问题展开，面向具备一定概率图模型基础、希望动手实现结构学习的研究生与算法工程师。包内共7个文件，以4个m脚本、1个c源码、1个mat数据文件和1个txt说明为主，压缩包约10KB，其中m文件承担主流程与子函数调用，c源码对应K2评分核心计算，mat文件提供可直接加载的实验样本数据，便于快速复现与调试。资源已有2168人学习下载，说明其在贝叶斯网络结构学习入门与教学场景中具有一定参考价值。读者可借此理解K2算法依赖节点序、评分函数与父节点上限的搜索逻辑，掌握从数据构造学习对象、计算评分到输出有向无环图的完整链路，并在此基础上修改评分准则或替换数据集，用于课程实验、论文复现与算法对比，是一份轻量但结构完整的实践素材。
1. K2算法：为什么它敢在指数级搜索空间里“贪心”找结构
贝叶斯网络结构学习，本质上是在一个超指数级的 DAG 空间里找一张“最像数据生成过程”的图。节点是变量，边是条件依赖，评分函数衡量图与数据的拟合度。问题在于，n 个变量的可能 DAG 数量随 n 超指数增长——10 个变量已经超过 4×10^18 种可能。穷举不可能，于是有了评分搜索、约束搜索、混合搜索三大流派。K2 算法属于评分搜索里最“朴素”也最“大胆”的一支：它不回溯、不全局优化，只做贪心加边，却能在很多真实数据集上给出可解释的结构。为什么这种“短视”策略能 work？因为它把结构学习问题转化成了一个带拓扑序约束的局部评分最大化问题，而拓扑序一旦给定，搜索空间就从超指数塌缩成多项式级的逐节点父集选择。搞懂 K2，就搞懂了评分搜索类算法最核心的设计取舍：用先验顺序换搜索可行性，用局部评分换全局近似。这份资源把 K2 的评分函数、加边准则、伪代码和实现细节拆得很细，适合想从“会调包”走到“能改算法”的开发者。
2. K2的评分函数：为什么是CH评分而不是别的
2.1 CH评分：把边际似然写成可累加的形式
K2 算法用的评分函数是 Cooper-Herskowitz 评分（简称 CH 评分），它本质上是贝叶斯评分的一种可分解形式。给定一个节点 $X_i$ 和它的父节点集合 $\pi_i$，CH 评分定义为：
$$ g(i, \pi_i) = \sum_{j=1}^{q_i} \left[ \log \frac{(r_i - 1)!}{(N_{ij} + r_i - 1)!} + \sum_{k=1}^{r_i} \log N_{ijk}! \right] $$
其中 $r_i$ 是节点 $X_i$ 的取值个数，$q_i$ 是父节点组合的个数，$N_{ijk}$ 是数据中 $X_i=k$ 且父节点取第 $j$ 种组合的样本数，$N_{ij} = \sum_k N_{ijk}$。
这个公式看起来吓人，但拆开看就三件事：第一项是归一化常数，第二项是父节点组合的遍历，第三项是每个取值下样本数的阶乘对数。关键性质是可分解——整张图的评分等于所有节点的局部评分之和。这意味着加一条边只需要重算目标节点的局部评分，不需要重新扫描全图。K2 的贪心加边之所以快，根子就在这个可分解性上。
常见的实现思路是预先算好所有 $N_{ijk}$ 的阶乘对数表，避免每次评分都做阶乘运算。因为 $N_{ijk}$ 最大就是样本数，开一个长度为样本数+1 的数组，用递推log_fact[i] = log_fact[i-1] + log(i)预计算，评分时直接查表。这一步优化能把评分速度拉高一个数量级。
2.2 为什么不用BIC或MDL
BIC 评分是另一套常用方案，形式是BIC = 对数似然 - (参数个数/2) * log(样本数)。它和 CH 评分的核心差别在于惩罚项：BIC 显式惩罚参数数量，CH 评分则通过边际似然里的阶乘项隐式惩罚。CH 评分对稀疏数据更友好，因为它不依赖大样本渐近假设；BIC 在样本量很大时更稳定，但小样本下容易过拟合或欠拟合。
K2 选 CH 评分还有一个历史原因：Cooper 和 Herskowitz 在 1992 年提出 K2 时，目标是从数据中恢复结构并做预测，CH 评分在他们的实验里表现更稳。实际工程中，如果数据量超过几万行，BIC 往往更省事；如果数据稀疏、变量取值多，CH 评分更合适。这份资源里对两种评分的对比有具体实验数据，能帮你判断什么时候该换评分函数。
2.3 评分函数的可分解性：K2能贪心的数学前提
可分解性不只是工程优化，它是 K2 贪心策略成立的数学前提。如果评分不可分解，加一条边会影响全图评分，局部搜索就失去了“只重算局部”的合法性。CH 评分和 BIC 评分都满足可分解性，所以 K2 和爬山法都能用。但 K2 比爬山法更“激进”：爬山法允许加边、删边、反向边，K2 只允许加边，而且加边的方向由给定的拓扑序决定。
这个限制看起来是缺点，实际上是 K2 的设计核心。拓扑序把 DAG 搜索变成了“每个节点只从它前面的节点里选父节点”，搜索空间从超指数降到 $\prod_i 2^{i-1}$，虽然还是指数级，但每个节点的父集选择是独立的，可以逐节点贪心。K2 的伪代码里，外层循环遍历节点，内层循环尝试加父节点，一旦某个父节点不能提升评分就停止——这就是“贪心”的具体含义。
3. K2的贪心加边：伪代码背后的搜索逻辑
3.1 伪代码逐行拆解
K2 的经典伪代码不长，但每一行都有讲究。下面是我按常见实现整理的版本：
def k2_score(node, parents, data, log_fact): """计算节点在给定父集下的CH评分""" # 统计 N_ijk：按父节点组合和节点取值分组计数 counts = count_ijk(node, parents, data) score = 0.0 for j in range(counts.shape[0]): # 遍历父节点组合 n_ij = counts[j].sum() score += log_fact[counts[j]].sum() # 第三项：sum log N_ijk! score -= log_fact[n_ij + r_i - 1] # 第一项：归一化 return score def k2_search(nodes, data, order, max_parents): """K2主循环：按拓扑序逐节点贪心加父""" dag = {node: [] for node in nodes} for i, node in enumerate(order): parents = [] score_old = k2_score(node, parents, data, log_fact) while True: best_gain = 0 best_parent = None # 只从拓扑序在 node 之前的节点里选 for candidate in order[:i]: if candidate in parents: continue if len(parents) >= max_parents: break score_new = k2_score(node, parents + [candidate], data, log_fact) gain = score_new - score_old if gain > best_gain: best_gain = gain best_parent = candidate if best_parent is None: break parents.append(best_parent) score_old += best_gain dag[node] = parents[:] return dag外层循环for i, node in enumerate(order)按拓扑序处理节点，保证加边方向永远从前往后，不会成环。内层while True是贪心加父的核心：每次从候选集里挑一个能让评分提升最大的节点，加进去；如果没有任何候选能提升评分，就停止。max_parents是工程上必须加的约束，否则父集可能膨胀到不可接受，评分也会过拟合。
3.2 拓扑序：K2的“先验”到底有多强
K2 最受争议的地方就是它要求用户提供拓扑序。这个序从哪来？常见来源有三种：领域知识（比如时间先后、因果方向）、变量排序（按某种相关性度量排）、随机序。拓扑序的质量直接决定 K2 的输出质量——如果序完全反了，K2 只能学到一张空图或极稀疏的图。
我一般会这么理解：拓扑序是 K2 用“先验换搜索效率”的代价。它把结构学习从“找 DAG”降级成“在给定序下找最优父集”，搜索空间小了，但对先验的依赖强了。实际工程里，如果领域知识不可靠，可以先跑一遍基于约束的算法（比如 PC 算法）得到一个粗略序，再喂给 K2。这份资源里提到一种做法：用互信息矩阵做变量排序，按互信息从大到小排，效果比随机序稳很多。
3.3 加边停止条件：评分增益为负就停
K2 的停止条件看起来简单——评分不再提升就停——但这里有个坑：CH 评分的增益可能因为数值精度问题出现微小波动。如果直接用gain > 0判断，可能因为浮点误差在某个候选上反复横跳。常见的实现思路是设一个阈值epsilon = 1e-6，只有gain > epsilon才加边。另一个坑是max_parents设得太大，导致父集包含弱相关变量，评分虚高但结构不可解释。经验值是max_parents = 3到5，超过这个数，CH 评分的边际收益急剧下降。
还有一个容易被忽略的点：K2 的贪心是“一次性”的，加进去的父节点不会因为后续加边而被移除。这意味着如果早期加了一个弱相关父节点，它可能挡住后面更强父节点的路。爬山法允许删边和反向边，能部分缓解这个问题，但 K2 不行。所以 K2 对拓扑序和评分函数的精度要求更高。
4. 从伪代码到工程实现：K2的坑与优化
4.1 数据预处理：离散化和缺失值
K2 的 CH 评分假设所有变量是离散的，且没有缺失值。真实数据往往不满足这两条。连续变量需要先离散化，常见做法是等频分箱或基于信息熵的分箱。等频分箱简单但可能破坏变量间的依赖关系；基于熵的分箱更保结构，但计算量大。这份资源里给了一个折中方案：先用等频分箱粗分，再用卡方检验合并相邻箱，直到箱间分布差异显著。
缺失值处理更麻烦。CH 评分的计数 $N_{ijk}$ 要求每个样本在每个变量上都有取值。常见做法是删缺失样本或填众数，但删样本会丢信息，填众数会引入偏差。更稳的做法是用 EM 算法迭代估计缺失值，但 K2 本身不包含 EM，需要在外层套一个循环。如果缺失率低于 5%，删样本通常可接受；高于 20%，建议先做缺失值插补再跑 K2。
4.2 计数表的稀疏问题
当父节点组合数 $q_i$ 很大时，很多 $N_{ij}$ 会是 0 或很小，CH 评分里的阶乘项会变得不稳定。比如 $N_{ij}=0$ 时，log_fact[0 + r_i - 1]可能是一个很大的负数，导致评分异常。常见的处理是加一个平滑项，把 $N_{ijk}$ 初始化为 1 而不是 0，相当于给每个取值一个均匀先验。这个平滑项的大小可以调，太大则评分偏向空图，太小则稀疏组合的评分波动大。经验值是平滑项取 1 到 2 之间。
另一个稀疏问题是内存：如果变量取值多、父集大，计数表可能大到内存放不下。常见的优化是用稀疏字典存储非零计数，只遍历出现过的父节点组合。这份资源里的实现用了哈希表加数组的混合结构，对稀疏数据比较友好。
4.3 并行化：逐节点独立计算
K2 的逐节点贪心天然适合并行：每个节点的父集选择不依赖其他节点的选择，只依赖拓扑序。所以可以把节点分到多个线程或进程里，各自算各自的父集，最后合并成 DAG。并行化的难点在于计数表的共享——如果每个线程都重新扫一遍数据，I/O 会成为瓶颈。常见的做法是先一次性把所有节点的计数表算好，存成稀疏矩阵，然后并行跑评分和加边。这份资源里提到用多进程加共享内存的方式，在 20 个变量、10 万样本的数据集上，把运行时间从几分钟压到几十秒。
注意：并行化时拓扑序的约束不能丢。如果线程 A 处理节点 i，线程 B 处理节点 j，且 i 在 j 之前，那么 j 的候选父集里不能包含 i 之后的节点。这个约束在并行实现里容易写错，导致成环。
5. K2避坑与排查：那些跑完才发现结构不对的情况
5.1 现象：学出来的图全是孤立节点
原因通常是拓扑序完全反了，或者评分函数里的平滑项设得太大。拓扑序反了，每个节点的候选父集都在它后面，K2 找不到任何能提升评分的父节点，只能输出空图。平滑项太大，评分对加边的惩罚过重，也会导致空图。解决方法是先检查拓扑序是否与变量间的因果关系一致，再把平滑项降到 1 以下试跑。
5.2 现象：图里出现大量反向边
K2 本身不会产生反向边，因为加边方向由拓扑序固定。如果输出里出现反向边，说明拓扑序和实际依赖方向冲突，或者后处理阶段做了反向边修正。解决方法是重新审视拓扑序的来源，如果是随机序，换成基于互信息或领域知识的序。
5.3 现象：评分很高但结构不可解释
这通常是max_parents设得太大，或者数据里有强噪声变量。CH 评分对噪声变量敏感，噪声变量可能因为偶然相关被加进父集，拉高评分但破坏结构。解决方法是先做变量筛选，把与目标变量互信息低于阈值的变量剔除，再跑 K2。另一个办法是加 L1 正则项，惩罚父集大小，但这会改变 CH 评分的可分解性，需要重新推导。
5.4 现象：运行时间随变量数爆炸
K2 的复杂度是 $O(n \cdot m \cdot q_i \cdot r_i)$，其中 n 是变量数，m 是候选父节点数，$q_i$ 是父集组合数。当 n 超过 50，即使max_parents=3，运行时间也可能到小时级。解决方法是先用约束算法（比如基于条件独立检验）筛掉大部分候选边，再在稀疏候选集上跑 K2。这份资源里给了一个两阶段方案：第一阶段用互信息筛边，第二阶段用 K2 精修，在 100 个变量的数据集上把时间从几小时压到几分钟。
5.5 现象：不同拓扑序跑出完全不同的图
这是 K2 的固有特性，不是 bug。拓扑序是强先验，换序等于换搜索空间。解决方法是跑多个序，取评分最高的图，或者用集成方法把多个序的结果投票合并。常见的做法是跑 10 到 20 个随机序，保留评分前 20% 的图，再取边的交集或并集。
6. 设计取舍：K2的“贪心”到底值不值得
K2 的核心取舍是：用拓扑序先验换搜索可行性，用局部贪心换全局近似。这个取舍在什么情况下值得？我的判断标准是三条：第一，领域知识能给出可靠的拓扑序；第二，变量数在几十到几百之间，穷举不可行但贪心够用；第三，对结构的要求是“可解释”而不是“最优”。如果三条都满足，K2 是性价比很高的选择；如果拓扑序不可靠，或者变量数上千，K2 就不如基于约束的算法或混合算法。
和爬山法比，K2 的优势是快、稳定、不会陷入局部最优的“删边-加边”循环；劣势是不能修正早期错误加边。和 PC 算法比，K2 的优势是对噪声和稀疏数据更鲁棒；劣势是需要拓扑序，而 PC 算法不需要。实际工程里，我一般会先跑 PC 算法得到一个粗略序，再用 K2 精修，最后用 BIC 评分做模型选择。这个组合在多个数据集上比单跑 K2 稳。
验证 K2 结果的方法有三层：第一层是评分对比，用留出数据算 CH 评分或 BIC 评分，看是否比空图和随机图高；第二层是结构对比，如果有领域专家，让专家判断边的合理性；第三层是预测对比，把学到的网络用于推理，看预测精度是否提升。三层都过，才敢把结构用于下游任务。
这份资源里对 K2 的实现细节、参数调优和避坑方案讲得比较透，尤其是计数表优化和并行化部分，是很多教程里没有的。如果你正在做贝叶斯网络结构学习，或者想从“调包”走到“改算法”，这份材料能帮你省掉不少自己踩坑的时间。从那以后我每次跑 K2 之前，都强制走一遍拓扑序检查、平滑项调参和候选边筛选，再也没出现过跑完才发现结构全错的情况。希望帮到你。
本文还有配套的精品资源，点击获取
