Page 237 - 《软件学报》2025年第4期

李梓童 等: 机器遗忘综述 1643

与继续计算相比, 模型分解无需额外存储空间保存中间结果, 但需考虑如何划分机器学习模型和如何聚合子
模型结果等. 该思想关键在于将完整模型转化为子模型, 若划分粒度太小, 则子模型可能由于数据量太少而表现不
佳, 影响整体性能; 若划分粒度太大, 则重新训练子模型时需训练数据量较大, 未必能很好地缩短训练时间. 模型分
解在针对集成树模型、回归模型和聚类模型的机器遗忘方法中有所体现.

2.2.1 集成树模型
集成树模型是以决策树为基础的集成学习器, 决策树对样本特征空间进行递归划分, 希望产生最大的信息增
量, 提高分类准确率.
DaRE (data removal-enabled forests) 是一种支持机器遗忘的集成树算法 [24] . 它充分利用集成树的随机性和数
据缓存特点来提高遗忘效率. 在构成 DaRE 的各个树中, 上层节点多为“随机节点”, 这些节点随机地选择分割属性
和分割阈值. 随机节点对数据依赖度较小, 被更新频率较低. 下层节点多为“贪婪节点”, 它们完整遍历计算每个节
点的基尼系数或信息熵, 以选择最优分割. 此外, DaRE 中的树会记录每个节点上的统计数据和叶子节点的训练数
据, 当遗忘请求到来时, 只更新与该请求有关的树, 避免更新所有树, 降低计算量. DaRE 得到的机器遗忘模型与重
新训练模型完全一致.
HedgeCut 是针对极度随机树 (extremely randomized tree, ERT) 的机器遗忘方法 [25] . 与随机森林不同, ERT 对
树进行划分时, 独立于目标属性而随机选择划分位点. HedgeCut 构造决策树时, 先根据允许构造树的数据点发生
多大变化而不影响原有划分的特性, 将划分分为稳健划分 (robust split) 和非稳健划分 (non-robust split) 两类: 稳健
划分在删除少量记录时, 不改变现有划分; 非稳健划分可能会在以后发生改变. 此处“少量记录”是针对所有数据点
而言, 人为地设置允许改变的阈值, 比如, 若将阈值设置为所有数据点的 0.1%, 则当该树上要遗忘数据点小于所有
数据点的 0.1% 时, 稳健划分并不改变. 在确定某处划分是否为稳健划分时, HedgeCut 先遍历数据点可能发生改变
的所有情况, 以此量化该划分对数据点变化的稳健程度.
对于非稳健划分, HedgeCut 预先维护一组候选划分方法. 当机器遗忘请求到来时, HedgeCut 需要更新树, 此时
稳健划分不需要改变, 只修正叶节点处统计数据; 而非稳健划分会重新计算各候选划分的基尼增益, 采纳增益最高
的划分方法. 为了加快计算叶节点处增益, HedgeCut 在各稳健划分树叶节点处保存了统计数据.

2.2.2 回归模型 K-means 算法, 再递归地合并结果.
回归模型是根据数据集 D, 拟合出最佳刻画 x 和 y 之间的函数 f, 用于预测其他数据点 x 的目标值 f(x ) , 常见
′
′
的回归方式有线性回归和局部加权线性回归等. 第 2.1.2 节的岭回归也是一种回归方法.
对于回归模型, Aldaghri 等人 [50] 设计了一种通过分解实现遗忘的方法. 他们把 D 划分成若干不相交的子集,
每个子集上训练一个子模型, 这些子模型输出结果最终聚合成总体的输出结果. 当要遗忘一个数据点时, 重新训练
使用该数据点的子模型, 不必全局训练. 为了降低训练代价, Aldaghri 等人在划分训练集之前首先对其进行压缩:
随机抽取训练集中的部分数据点, 用这些数据点的聚合值代替原有数据点放入训练集. 该聚合过程可回溯, 若 x ∗
被聚合了, 可在相应的聚合结果中除去其影响.

2.2.3 K-means 聚类
第 2.1 节已对 K-means 聚类做了说明, 并介绍了针对 K-means 的继续计算类机器遗忘方法 Q-k-means. DC-k-
means (divide-and-conquer k-means) 是针对 K-means 的模型分解类机器遗忘方法 [40] . DC-k-means 将 D 划分为若干
子集, 在每个子集上独立运行
DC-k-means 基于树结构实现. 原始数据集被划分至树的叶子节点, 每个叶子节点均通过聚类算法求解其上数
据集的质心. 在将叶子合并到父节点时, 合并后节点对应的新数据集包含了各叶子节点的所有质心. DC-k-means
继续使用聚类算法计算父节点上的新质心, 以此类推. DC-k-means 利用树的层次结构使质心和数据集依赖关系模
块化. 当遗忘请求到来时, 只需重新进行从对应叶子节点到根节点的聚类运算. 根据实验结果 [40] , Q-k-means 运行
速度高于 DC-k-means, 而 DC-k-means 聚类效果略优于 Q-k-means.

2.3 混合方法
混合方法是指同时使用继续计算和模型分解两种方法来进行机器遗忘的方法: 先将完整模型分解为子模型,