Cross-Group Aligned Problem Difficulty Clustering Using Attention-Weighted Feature Learning

技术摘要：基于注意力加权特征学习的跨组对齐问题难度聚类

问题陈述
在线判题（OJ）平台是编程教育的关键基础设施，提供了海量的题目和提交日志。然而，利用这些数据面临的一个重大挑战是学习者的异质性：同一个问题对于不同能力水平的用户来说，可能会被感知为简单或困难。现有的难度分类方法通常依赖于全局聚合的行为特征，这掩盖了依赖于专业水平的交互模式。此外，独立应用于不同用户组的标准聚类方法往往会导致不一致的难度标签（例如，一个对高级用户标记为“简单”的问题，对初学者可能被标记为“困难”），从而破坏了连贯的学习进阶过程。此外，OJ 特征（如提交次数、尝试次数）通常具有高度偏斜和长尾分布的特性，这可能会使基于距离的聚类算法产生偏差。

研究方法
作者提出了一种感知专业水平分组的框架，该框架集成了统计建模、基于注意力的特征学习和跨组对齐。工作流程包含五个主要阶段：

1. 数据预处理与特征提取：

   • 数据集： 本研究利用了来自 Aizu Online Judge (AOJ) 的大规模提交日志，包含约 960 万次提交、3,047 道题目和 83,495 名用户。
   • Rasch 模型： 对二元提交结果（通过 vs. 错误）进行 Rasch (1PL) 模型拟合，以估计潜在用户能力 ($\theta$) 和题目难度 ($\beta$)。
   • 用户聚类： 根据潜在能力和准确率，利用 K-means 将用户聚类为三个专业水平组（初学者、中级、高级）。
   • 特征构建： 为每个用户组聚合题目级特征，包括：
     • 行为特征： 提交次数、平均尝试次数、通过率、平均耗时。
     • 潜在特征： 基于 Rasch 模型的难度得分。
   • 预处理： 为了处理偏斜和异常值，对提交次数、平均尝试次数和耗时进行对数变换。随后使用 Z-score 标准化将特征映射到统一尺度。

2. 基于注意力的难度聚类 (FA–K-means)：

   • 该框架并未假设特征权重是均匀的，而是采用了特征注意力引导的 K-means (FA–K-means) 算法。
   • 特征注意力模块学习每个用户组特定的权重 ($A^{(g)}$)。该模块通过线性变换结合 tanh 激活函数和 softmax 函数来生成注意力分数，进而创建加权特征表示 ($Z^{(g)}$)。
   • 该模块通过重构损失（最小化输入与重构特征之间的差异）进行训练，然后在加权表示上应用 K-means 聚类，以识别难度等级（简单、中等、困难）。

3. 跨组难度对齐：

   • 为了解决各组间标签不一致的问题，引入了全局难度对齐步骤。
   • 该方法将非单调排序 (NMO) 定义为衡量不一致性的指标，即如果 $Difficulty_{Beginner} < Difficulty_{Intermediate} < Difficulty_{Advanced}$（假设较高的标签表示更高的难度）这一预期顺序未得到维持，则视为违反了顺序。
   • 对齐过程通过聚合所有组中相同难度等级的质心来计算“全局难度中心”。这些全局中心通过各自组特定的预处理和注意力模块映射回各组，以创建组特定的锚点。随后，问题被重新分配到最近的锚点，从而确保在不同专业水平之间实现统一且单调的难度量表。

4. 评估：

   • 指标： 使用轮廓系数 (SS)、丹维斯-布尔丁指数 (DBI) 和卡林斯基-哈拉巴兹指数 (CHI) 来评估聚类质量。通过 NMO 衡量跨组一致性。
   • 基准模型： 将所提方法与标准 K-means、模糊 C-均值 (FCM)、Ward 层次聚类和 BIRCH 进行对比。
   • 验证： 使用 Kruskal-Wallis (KW) 检验和效应量 ($\epsilon^2$) 进行统计显著性评估，以验证不同特征在聚类间的分离度。

核心贡献

• 感知专业水平的框架： 研究引入了一个能够针对三个专业水平组分别进行题目难度分类的框架，捕捉了群体级方法所忽略的交互模式。
• NMO 的形式化： 作者将非单调排序 (NMO) 正式化为一个可解释的指标，用于量化并最小化跨组标签的不一致性。
• FA–K-means 算法： 集成特征注意力引导的 K-means 使得学习组特定的自适应特征权重成为可能，与标准的均匀权重相比，提高了组内聚类的质量。
• 全局对齐策略： 提出了一个系统的对齐步骤来产生统一的难度量表，显著降低了 NMM。
• 可解释性： 框架识别出了驱动难度区分的关键特征（特别是通过率和平均尝试次数），并得到了统计测试的支持。

实验结果

• 聚类质量： 在 AOJ 数据集上，FA–K-means 在所有专业水平组中均一致优于基准模型（K-means, FCM, Ward, BIRCH）。它实现了最高的轮廓系数（例如，初学者组为 0.42，而 K-means 为 0.34）、最高的卡林斯基-哈拉巴兹指数以及最低的丹维斯-布尔丁指数。
• 跨组一致性： 全局对齐步骤大幅降低了 NMO。对于 FA–K-means，NMO 从对齐前的 30.41% 降至对齐后的 9.69%。其降幅优于基准模型（基准模型在对齐后仍处于 21.50%–26.63% 之间）。
• 特征重要性： 注意力权重分析和 KW 检验表明，通过率和平均尝试次数是区分难度等级最显著的指标。
• 泛化性： 在通过基于秩的高斯 Copula 生成的合成数据集上的实验重现了 AOJ 的发现，证实了该框架的稳定性以及基于注意力的重加权和对齐策略的鲁棒性。
• 可视化： 开发了一个轻量级的 Web 端仪表板，用以展示用户层面的派生难度等级检查。

意义与主张
论文声称，该框架为基于专业水平分组的 OJ 编程教育提供了一个有效且可解释的难度分类基础。通过承认难度相对于用户专业水平而存在差异，该方法比全局聚合方法提供了更连贯的难度量表。作者断言，其方法不仅提高了聚类有效性指标，而且产生的难度标签在不同学习者组之间保持了一致性，从而支持了更好的学习进阶，并为教师提供了更科学的题目组织依据。研究强调，虽然该框架在 AOJ 上得到了验证，但其设计具有可扩展性，适用于其他具有异质用户组和共享任务的领域。作者对局限性保持了审慎态度，指出该框架依赖于基于提交的特征，且性能可能会因不同平台的数据稀疏性或特征特性而有所不同。