1. 为什么要给代码聚类加上教学这个锚点我带过一届学生的课程设计之后彻底对传统的代码聚类失去了信心。当时手里有三百多份学生提交的Python作业想用聚类算法自动把学生的实现方案归归类看看大家普遍倾向于什么写法。我直接用了最常见的TF-IDF加KMeans结果聚出来的类别让人哭笑不得——所有的循环都被分到了一起所有用了f-string的又被分到了一起而真正想看的递归实现和迭代实现反而被切得四分五裂。原因其实很简单传统代码聚类的相似度计算完全建立在代码文本或者调用关系上它压根不理解这道题的教学意图。同样是递归A同学写的斐波那契和B同学写的文件目录遍历在词法层面截然不同但教学意图完全一致。这就是我说的教学锚定问题——聚类结果只有对齐到教学目标、知识点、练习编号这些教育维度才对教学分析真正有意义。Pedagogically Anchored Code ClusteringPACC解决的问题就是这样一件事它不是单纯把代码当成文本来聚类而是把代码的语义特征和教学锚点绑在一起让聚类结果既能反映代码的结构异同又能对学习分析说得上话。我写这篇文章就是想把PACC从想法到落地的全链路讲清楚。适合三类人读做编程教育平台的技术人员、研究学习分析的学生或同行、以及想在作业自动分组上少走弯路的老师。我会从教学锚点的数学化定义讲起一直讲到特征提取、约束谱聚类实现、评测调参和我在真实场景里踩过的坑。全程默认你懂Python知道聚类是干什么的但不需要你是算法专家——拉普拉斯矩阵、谱聚类这类东西我会从为什么需要它讲起。2. 教学锚点怎么变成矩阵里的约束PACC的数学框架最开始接触这个概念的人都会问同一个问题教学锚点到底是个什么东西抽象一点说锚点是聚类过程中不允许被忽略的教学语义信息。它在实际系统里通常表现为几类数据题目编号Exercise ID、学习目标Learning Goal、知识点标签Concept Tag、评分维度Rubric Item有时候还包括题目的难度等级和所属章节。这些数据平时躺在课程管理系统的数据库里看起来和代码本身没什么关系。但PACC的思想是把它们从属性字段升级成聚类约束——也就是在算法眼里这些信息不是等聚类完了再拿来做标注而是从一开始就参与决定哪些代码应该被分到同一个簇。2.1 教学锚点如何转化为约束条件锚点有两种最基本的转化方式。第一种叫必须相连约束must-link表示两份代码在教学目标上是同一类。比如两道题目都是练习二分查找那它们最常见的几种实现方式应当被分到一起。第二种叫禁止相连约束cannot-link表示两份代码在教学维度上明确属于不同类别。比如一道题练的是面向对象封装另一道题练的是函数式递归即使它们文本碰巧用了相似的变量名聚类时也不该被混在一起。你可以把这两种约束想象成橡皮筋——有的橡皮筋把点往一起拉有的橡皮筋把点往开撑。传统聚类算法只用点与点之间的距离来决定分组而PACC等于在这些距离之上额外叠了一层教学橡皮筋的拉力。这个思路有个很关键的优势它不需要为每道题单独训练一个分类模型。只要把约束矩阵搭好任何基于相似度的聚类算法都能在后续接入。后面你会看到我用谱聚类来承接约束但如果你偏好层次聚类或者标签传播算法PACC的约束矩阵同样能喂进去。2.2 目标函数里锚定是什么数学含义如果把PACC写成一个目标函数它的形式大致如下。设一共有n份代码我们想找的聚类指示向量是yy的第i个元素代表第i份代码属于哪个簇代码本身的相似度矩阵是W则传统谱聚类要最小化的是归一化切割Normalized Cut。PACC在此基础上增加了一个锚点对齐项[ \min_{y} ; y^T L_{sym} y \lambda \cdot | y - y_{anchor} |^2 ]这里L_sym是归一化拉普拉斯矩阵它编码了代码之间的结构相似度y_anchor是教学锚点给出的软标签向量λ是一个权重系数控制教学信息对聚类结果的拉扯强度。稍微解释一下为什么要写成这样。第一项是谱聚类的标准项目的是让同一个簇内部的代码相似度高、不同簇之间相似度低。第二项则是PACC的差异所在——它不让聚类结果在所有情况下都只由代码相似度说了算而是要求结果尽量靠近锚点给出的教学分组。λ如果设成0PACC就退化成普通谱聚类λ设得过大聚类又可能被锚点完全主导导致代码本身的结构差异被淹没。实际调参里λ的取值范围我认为最值得关注的区间是0.1到1.5之间这个后面评测部分会展开。2.3 硬约束与软约束的关键取舍很多第一次实现PACC的朋友容易犯一个错误把教学锚点全部做成硬约束认为这样聚类结果一定更干净。实际经验恰恰相反教育数据里锚点本身就有噪声。举个例子一道作业题标注了知识点是循环嵌套但有一部分学生提交的代码用的是递归或者列表推导式。如果你把这道题的所有提交全部硬性绑定为must-link递归实现就会被强行揉进循环嵌套的簇里簇内一致性立刻裂开。因此在真实系统里我强烈建议用软约束——锚点信息指导聚类方向但同时允许模型根据代码结构和锚点不一致时做出偏离。这也就是上面目标函数里λ的定位。软约束的实现形式一般是用一个锚点亲和矩阵A_anchor把它按比例加到亲和矩阵上再去做谱聚类。这样既保住了教学维度的指导也保留了代码特征本身的话语权。3. 从学生代码到相似度矩阵特征提取的完整链路理论框架说完了现在讲真正动手写代码时最关键的步骤怎么把一份份学生提交的代码变成谱聚类能吃的相似度矩阵。这一步做不好后面的约束再精确都白搭。我试过好几条路最后稳定下来的是AST结构特征浅层语义特征调用关系特征三条腿走路。3.1 为什么不能只用文本向量初版实现的时候我图省事直接对代码字符串做TF-IDF向量化。结果前面也说了惨不忍睹。文本向量有两个与生俱来的问题。第一个问题是它对标识符的命名太敏感。学生A喜欢用lst、tmp这种缩写学生B喜欢用numbers、result这种全称它们在文本上几乎是完全不同的词但代码行为一模一样。第二个问题是它完全不理解代码结构。两个学生都用while循环实现同一个算法但其中一个多写了一个辅助函数、另一个把判断逻辑内联在循环体里文本分布差别巨大语义上却只有一种实现路线。相比之下抽象语法树AST把代码从字符串变成结构树保留了控制流、函数调用、变量作用域这些真正影响代码行为的维度。这也是我在PACC实现里把AST特征作为主特征的原因。3.2 AST高层特征节点类型频率与结构统计我用Python的ast模块做第一层特征提取。具体做法是解析源码生成AST然后统计每个节点类型在整个树里的出现频率。节点类型包括FunctionDef、For、While、If、Call、Subscript、BinOp等等。这一步本质上是在给代码拍一张骨架X光片——不同写法的骨架差异会直接体现在节点类型的分布上。除了频率以外我还额外提取一组结构统计量最大嵌套深度、函数个数、各类控制流语句的总数、平均函数长度、是否存在递归调用通过检测函数体内是否调用了函数自身的名字。这些特征对教学维度特别有价值因为很多入门课程的编码目标就是练这些结构比如用递归实现目录树的遍历在节点频率上就会很自然地和用循环实现遍历分开。import ast from collections import Counter def extract_ast_features(source_code: str) - dict: tree ast.parse(source_code) node_counter Counter() max_depth 0 def walk_with_depth(node, depth): nonlocal max_depth max_depth max(max_depth, depth) node_counter[type(node).__name__] 1 for child in ast.iter_child_nodes(node): walk_with_depth(child, depth 1) walk_with_depth(tree, 0) func_count node_counter.get(FunctionDef, 0) node_counter.get(AsyncFunctionDef, 0) features { max_depth: max_depth, func_count: func_count, for_count: node_counter.get(For, 0), while_count: node_counter.get(While, 0), if_count: node_counter.get(If, 0), call_count: node_counter.get(Call, 0), } return features注意这里有个细节如果输入代码本身有语法错误ast.parse会直接抛异常。学生提交的代码里语法错误率比你想象的高得多因此我在接数据时统一用try-except捕获并对解析失败的代码单独打标——这部分代码不参与聚类但会被记录下来供老师重点查看因为语法错误本身就是重要的教学信号。3.3 把代码变成向量AST节点序列化嵌入光有节点频率还不够因为频率统计丢掉了子树之间的顺序和层级关系。比如同样是两个If节点一个嵌套在循环里、一个挂在函数顶层语义差别很大但频率统计完全一样。所以我加了一层AST序列化嵌入把AST按先序遍历拍平成节点序列再用类似Word2Vec的嵌入方法给每个节点类型学一个向量最后把整棵树的嵌入向量做平均池化作为代码的语义向量。具体工程上我建议直接用tree-sitter的Python绑定来生成语法树再配上astnode2vec这类工具做节点嵌入比自己手写AST遍历要省力得多。如果你不想引入那么多外部库也可以用ast模块先把节点类型序列化成字符串序列然后用gensim里的Word2Vec训练节点嵌入。两条路我都跑过后者在代码量级一两万份以下完全够用区别不大。3.4 构建相似度矩阵的完整代码骨架特征提取完之后相似度矩阵W的构建就是一个标准动作。最简单的方案是计算两两特征向量的高斯核相似度import numpy as np from sklearn.metrics.pairwise import rbf_kernel def build_similarity_matrix(feature_matrix, gamma0.1): W rbf_kernel(feature_matrix, gammagamma) np.fill_diagonal(W, 0) return W高斯核里的gamma也是个值得调的超参数。gamma太小所有代码的相似度都趋近于1聚类没有区分度gamma太大相似度衰减太剧烈只有一模一样的代码才算相似。我一开始用默认值1/n_features效果很差后来改用网格搜索发现对本项目场景gamma取0.05到0.2之间表现最稳定。相似度矩阵构建完成后别忘了做稀疏化处理——把每行除了K个最近邻之外的距离全部置零。K一般取20到50之间。稀疏化有两个好处一是让后续特征分解更快二是去掉长尾的弱连接让聚类边界更清晰。4. 约束谱聚类的核心实现一份可直接改的代码骨架现在到了PACC最核心的环节怎么把教学锚点矩阵和谱聚类缝合在一起。这一节我会给出一份可以直接跑的骨架代码然后逐步解释每一步为什么要这么做。4.1 从相似度矩阵到归一化拉普拉斯谱聚类的起点是相似度矩阵W。我们已经有了W接下来要构造拉普拉斯矩阵。常用的有三种未归一化的L对称归一化的L_sym以及随机游走归一化的L_rw。考虑到后续要叠加锚点约束项我建议用对称归一化版本即[ L_{sym} I - D^{-1/2} W D^{-1/2} ]D是对角矩阵D[i][i]等于W第i行的和也就是度矩阵。用归一化版本的好处是特征值范围被压缩到[0,2]之间数值稳定性更好对度不均匀的数据集比如有的代码很长、有的很短导致相似度规模差异大也更耐受。实现上直接调用numpy就行def normalized_laplacian(W): d np.sum(W, axis1) d_inv_sqrt np.power(d 1e-10, -0.5) D_inv_sqrt np.diag(d_inv_sqrt) I np.eye(W.shape[0]) L_sym I - D_inv_sqrt W D_inv_sqrt return L_sym4.2 锚点约束矩阵的编码方式锚点约束矩阵的构建取决于你的锚点数据长什么样。最简单的情况是每份代码被标注了知识点标签。比如代码i标了recursion代码j也标了recursion那么A_anchor[i][j]就设成一个正值代码i标了recursion代码k标了iterationA_anchor[i][k]设成负值或者零。更一般的情况里锚点可能是一个多标签集合。比如一份代码既涉及循环又涉及条件判断另一份代码只有循环。这时候直接用标签相等与否太粗暴我推荐用标签集合的余弦相似度或者Jaccard相似度作为锚点亲和度def build_anchor_matrix(labels, methodcosine): n len(labels) A np.zeros((n, n)) for i in range(n): for j in range(n): set_i set(labels[i]) set_j set(labels[j]) if method jaccard: union len(set_i | set_j) 1e-8 inter len(set_i set_j) A[i, j] inter / union elif method cosine: vec_i np.array([1.0 if tag in set_i else 0.0 for tag in all_tags]) vec_j np.array([1.0 if tag in set_j else 0.0 for tag in all_tags]) norm np.linalg.norm(vec_i) * np.linalg.norm(vec_j) 1e-8 A[i, j] np.dot(vec_i, vec_j) / norm return AJaccard和余弦各有各的适用场景。如果标签之间彼此独立、没有层次关系用Jaccard干净利落。如果标签本身是从一个概念树里取出来的比如迭代包含while循环和for循环余弦方法配上一套one-hot向量会更灵活。我自己的系统里用的是层级标签的余弦版本因为某个学习平台的课程体系就是树状的知识点天然有父子关系。4.3 约束融合与特征分解有了L_sym和锚点矩阵A_anchorPACC的求解就落到了广义特征分解上。目标矩阵变成[ L_{pacc} L_{sym} \lambda \cdot (D_{anchor} - A_{anchor}) ]后一项的D_anchor是锚点矩阵的度矩阵减出来的玩意儿本质上是一个锚点拉普拉斯。λ控制锚点约束权重。然后我们对L_pacc做特征分解取前k个最小特征值对应的特征向量组成一个n行k列的矩阵每行就是这个代码点在低维空间的坐标。最后对这组坐标做KMeans就能得到聚类标签from sklearn.cluster import KMeans def pacc_cluster(W, A_anchor, n_clusters, lam0.5): L_sym normalized_laplacian(W) D_anchor np.diag(A_anchor.sum(axis1)) L_anchor D_anchor - A_anchor L_pacc L_sym lam * L_anchor eigenvals, eigenvecs np.linalg.eigh(L_pacc) # 跳过数值接近0的最小特征值避免数值噪声 k n_clusters Z eigenvecs[:, :k] Z Z / (np.linalg.norm(Z, axis1, keepdimsTrue) 1e-10) labels KMeans(n_clustersn_clusters, n_init10, random_state42).fit_predict(Z) return labels这段代码已经可以直接跑通一个最小版本。np.linalg.eigh对对称矩阵做特征分解返回的特征值从小到大排列我们直接取前k个即可。Z矩阵的归一化步骤容易被忽略但其重要性很高——如果不做行归一化特征向量的尺度差异会主导后续的KMeans距离计算聚类结果噪声会大很多。4.4 为什么要用谱聚类而不是直接对锚点矩阵做聚类这个问题的答案其实藏在前面。如果只对锚点矩阵聚类就相当于完全信任教学标签忽略了代码本身的语义差异如果只对相似度矩阵聚类就回到了传统方法的困境。PACC的价值在于它让两股力量在目标函数里对话。谱聚类之所以是合适的载体是因为它的数学结构和约束融合天然匹配——目标函数里的两个矩阵都是拉普拉斯算子特征分解统一求解理论与实践都干净。如果你追求工程上的极致效率可以改用scipy.sparse.linalg.eigsh配合稀疏化后的相似度矩阵做部分特征分解能显著减少内存占用。我在处理几千份代码时用numpy的稠密分解没问题但数据量到两三万时稠密矩阵的内存占用会到几个GB必须换成稀疏版本。5. 评测与调参NMI、ARI和那个影响最大的超参数算法写出来只是第一步怎么证明它不是玄学是第二步。我用了两组数据来做评测一组是模拟项目X的合成数据代码由模板加上变异生成锚点标签完全可控另一组来自真实课程的历届作业提交经过匿名化处理锚点由助教手工标注。评测指标选了标准化互信息NMI和调整兰德指数ARI因为它们对簇数量不敏感适合用来对比不同算法在不同K下的表现。5.1 与传统谱聚类的对比结果我跑了三组对比普通KMeans直接做代码文本向量聚类、无锚点的谱聚类、以及PACC。结果如下表方法NMI合成数据ARI合成数据NMI真实数据ARI真实数据TF-IDF KMeans0.420.310.350.22AST特征 谱聚类0.710.640.580.50PACCλ0.50.870.820.740.66从表里能看出两个信息。第一AST特征相比文本特征提升巨大说明结构信息在代码聚类的相似度计算里确实更本质。第二叠加锚点约束的PACC在合成数据上NMI提升约0.16在真实数据上提升约0.16到0.17说明教学锚点确实把聚类的方向往教学目标上拉了一把。5.2 锚点权重λ的影响规律λ是我在做评测时最关注的超参数没有之一。我画了一条λ从0到2.0的扫描曲线观察NMI的变化。结果是一个明显的倒U形λ在0到0.3之间NMI快速上升在0.3到1.0之间保持在平台期超过1.5以后NMI开始下滑。λ2.0时聚类结果几乎与纯锚点矩阵聚类相同代码结构相似度完全被压制。这个现象在真实数据上比合成数据更明显。原因也好理解真实数据里锚点标签本身就存在标注噪声学生提交的代码和标准实现偏差大锚点权重太高会把噪声放大传导到聚类结果。因此我的结论是如果你手里的锚点标签准确度较高来自考题编号、标准知识点λ可以取0.3到0.7如果锚点来自自动识别模型或助教快速标注建议从λ0.2起步宁小勿大。5.3 学习率式调参思路与应用经验在实际项目里我不会一股脑直接跑一次λ扫描就完事。更有效的思路是分两阶段第一阶段在标注锚点上先跑无锚点谱聚类看代码结构聚类结果里哪些簇和锚点天然一致、哪些冲突明显。第二阶段对那些冲突明显的区域针对性调λ——具体做法是把锚点矩阵拆成子块对不同的知识点分别赋予不同权重相当于给每个教学锚点配一个可学习的强度系数。我在某学习平台的作业分组系统里就是这样实践的。循环与条件判断这类基础知识点锚点强度高因为学生的实现差异小、标签准确递归与栈这类容易有风格分叉的知识点锚点强度降到0.2让学生代码的语义特征有更大发言权。这套办法让整体NMI又提升了0.05左右。6. 落地时最容易翻车的几个场景与我的修正方案最后这部分写给准备在真实教学系统里集成PACC的朋友。我踩过不少坑其中最疼的有四个每一个都直接影响了聚类结果的质量。6.1 学生代码的半成品会污染相似度矩阵真实课程作业里总有相当比例的学生提交没有完整跑通的代码。他们可能写了函数开头的参数校验但核心逻辑是个TODO注释也可能finally块里只打了一行日志没做任何清理。这些半成品和完整实现之间AST特征的差异非常大但在教学语义上它们恰恰是最需要被识别出来的未掌握信号。如果直接把半成品和完整代码混在一起聚类半成品会因为结构残缺被分到几个杂乱的边角簇里完全丧失分析价值。我的修正方案是先对每一份代码做一次完成度评估比如是否包含主函数入口、核心算法关键词在AST里搜索关键函数调用、函数是否有return语句、是否有可执行的主流程。完成度低于阈值的代码单独拉出来归档为需关注类别不参与PACC聚类。这样聚类出来的簇全是完整实现每个簇内部的代码风格差异也更有解释力。6.2 题目之间的代码复用会让锚点张冠李戴有一道作业题练的是链表反转很多学生直接复制了上一道题数组反转的代码改吧改吧交上来。从教学锚点看它应该属于链表反转这道题的提交从代码特征看它却和数组反转的实现高度相似。这种跨题复用如果规模不大锚点约束能从全局角度把少数复用代码拉回到正确簇里如果某个班级里超过三分之一的人都这么干锚点就会被拉歪整个簇结构都会乱。针对这个问题我后来在特征提取阶段加入了一道指纹向量提取代码里所有函数名、全局变量名、字符串常量做一个去重后的集合。两段代码的指纹重合度超过80%时我在相似度矩阵的对应位置设一个复用标记。聚类完成后标记过的代码对会被单独抽出来做二次检查。它不一定错了但它值得关注。6.3 簇数量K的选择不再是拍脑袋传统谱聚类里K的选择常用肘部法则看特征值分布。但PACC有个额外优势锚点的知识点数量天然给了K一个参考范围。比如这一章有五个知识点那K的合理范围就在5附近浮动。它不是必须等于5因为同一个知识点下可能存在多个实现风格簇但偏离5太多通常意味着聚类被无关特征带偏了。我实际使用的方法是以锚点类别数K0为中心扫描K从K0-2到K03对每个K跑5次PACC选NMI最高且各簇样本量不低于总样本量3%的结果。这样选出来的K既贴紧了教学目标又允许风格差异带来的簇内细分。6.4 冷启动新题目没有锚点怎么办PACC依赖锚点但新作业题刚上线时大概率没有任何标注数据。我尝试过的折中方案是迁移锚点从题库里找出和这道新题相似的历史题目——相似计算可以用题目描述文本的向量匹配——把历史题目的锚点映射过来作为新题的初始化锚点。由于代码被共享的可能是递归、状态管理等通用知识点这个方案跑下来的结果比完全不设锚点要稳定得多。新题积累了几十份提交后再请助教抽查修正锚点聚类的可靠性就会快速回升。另一个我自己比较偏好的办法是让锚点从聚类结果中自举先跑几轮无锚点谱聚类然后抽取每个簇里距离质心最近的三五份代码让老师只标注这小撮代码的知识点再把标注扩散回整个簇当作锚点。这样可以有效减少人工标注量非常适合每周都有新题上线的教学周期。6.5 工程接入建议把它当作一条异步流水线最后提醒一点不要把PACC写进同步的API调用链路里。聚类不是毫秒级操作当代码量上万时特征分解加KMeans可能跑十几秒到几分钟。学生提交作业后不可能等这么久。我的做法是每次作业截止后由定时任务触发PACC流水线跑完后把聚类结果写入课程数据库生成的簇报告推送给教师端。老师上课前就能看到本班作业的主要实现风格分布这比在提交瞬间给一个临时分组要实用得多——因为教学分析的决策点本来就在课后不在提交那一刻。