在机器学习的实际应用场景中，模型的训练数据是有变化的，常会出现训练数据无法使用，需要删除的情况：

• 用户不再授权使用自己的信息。
• 数据达到有效期限，不再具有有效性。

对于现有的机器学习算法，当训练集中有数据被删除时，往往需要重新训练整个模型，但这种方法会带来很大的开销。

高效的数据删除算法能够在数据被删除的情况下快速地计算出新的模型，不需要对模型进行重新训练，能够有效降低在数据删除场景中的计算开销。

Antonio等[1]对k-means算法进行了改进，提出了两种高效的数据删除算法：Quantized K-Means和Divide-and-Conquer K-Means，相较于传统的 K-Means++算法有超过100倍的性能提升，同时聚类质量相近。

本小组本次大作业复现了文章中的两种算法，并使用和本文使用的两个数据集对实验结果进行分析评价。

假设有一个机器学习模型，其使用$n$个数据的训练集进行训练。将第$i$项训练数据从模型的训练集删除后，应当得到与第$i$项数据无关的模型。

在数据删除的场景下，传统的做法是利用删除后的训练集重新对整个模型进行训练。我们实现的两种改进的K-Means算法方法避免了对整个模型的重新训练，从而实现高效的数据从删除算法。

我们对传统的K-Means算法进行了改进，实现了如下两种删除高效的K-Means算法

对于K-Means算法，从大量数据中删除一个数据点，每个簇的中心点变化不大，利用这一性质可以提出一种量化的K-Means算法。

量化K-Means算法与传统的K-Means算法的不同点如下：

1. 使用量化的方法：将K-Means聚类的中心点映射到以$\epsilon$为间距的网格的交点处。为了消除该过程中的偏差，每次量化前会对网格加入随机的偏移。
2. 在元数据中记录迭代过程中的状态信息（类中心点、损失函数等）
3. 引入权重修正步骤，对较小规模的聚类进行补偿，确保聚类的大小均匀
4. 由于量化步骤无法保证每次迭代存世函数下降，引入提前终止的判断

在每次数据删除后，会使用元数据中记录的信息判断量化的簇中心点是否改变，若未改变则只需要修改元数据，不需要对模型进行重新训练，利用此方法降低数据删除所需时间。

使用经典的分治**，进行点的删除：

• 将所有数据集均匀划分为不同的子集
• 对子集进行聚类，然后将子集聚类所得中心点传递给母节点，母节点对中心再进行聚类
• 依次递归直到根节点聚类

删除时只需将对应的叶子节点中的数据点进行删除，然后递归更新母节点的聚类结果即可。

原文中使用了五种公开数据集，由于原文作者提供的数据集为加密的matlab数据，无法使用，我们选择了其中两种数据集，并自行进行了数据预处理。选择的数据集如下：

使用上述两个数据集进行分析。

使用三种指标度量算法效果：

• 优化损失率（optimal loss ratio）：

  • 新方法的损失与普通kmeans方法的损失之比。
  • 该值越大，说明新方法的聚类损失越大。

• 轮廓系数（Silhouette Coefficient）：

  • 对某个样本$i$而言，

  • 簇内不相似度$a(i)$：$a(i)$为样本$i$到同簇其他样本的平均距离，$a(i)$越小说明样本$i$越应该被分到该簇。

  • 簇间不相似度$b(i)$：$c_i(j)$为样本$i$到簇$j$的所有样本的平均距离，$b(i)=\min_{j}c_i(j)$

  • 轮廓系数$s(i)$：

    $$ s(i)=\frac{b(i)-a(i)}{\max{a(i),b(i)}}= \left{ \begin{aligned} 1-\frac{a(i)}{b(i)}&,&a(i)<b(i)\ 0&,&a(i)=b(i)\ \frac{b(i)}{a(i)}-1&,&a(i)>b(i) \end{aligned} \right. $$

  • $s(i)$越大（接近$1$），说明样本$i$聚类越合理；$s(i)$越小（接近$-1$），说明样本$i$越可能聚类错误。

  • 对所有样本的轮廓系数取平均值。

• 归一化的互信息 （Normalized Mutual Information）

  • 使用此度量值需要一个标准的分类结果。设自己的聚类结果分出的类目标签集为$A$，标准的分类结果标签集为$B$

  • $A$和$B$的互信息： $$ \begin{align*} I(A,B)&=H(A)+H(B)-H(AB)\ &=-\sum_{a\in A}p(a)\log_2(p(a))-\sum_{b\in B}p(b)\log_2(p(b))-\sum_{a\in A}\sum_{b\in B}p(a,b)\log_2(p(a,b))\ &=-\sum_{a\in A}\sum_{b\in B}p(a,b)\log_2\Big(\frac{p(a)p(b)}{p(a,b)}\Big)\ &=\sum_{a\in A}\sum_{b\in B}p(a,b)\log_2\Big(\frac{p(a,b)}{p(a)p(b)}\Big) \end{align*} $$

  • 归一化的互信息： $$ NMI=2\frac{I(A,B)}{H(A)+H(B)} $$

  • $NMI$的范围在$0\sim1$之间，$NMI$越大，说明两种分类方法越吻合。

​ 首先，对比了10000条数据下不同算法的表现

可以看出，kmeans优化损失率比qkmeans和dckmeans要小，轮廓系数和归一化的互信息都比后两者大。因此qkmeans和dckmeans在聚类的准确率上略低于kmeans，但差别不大，约为10%。

接下来，验证删除算法对结果的影响。对10000个样本训练完毕后，从中删去100个样本进行测试。将使用删除算法得到的结果记为$rerun$，将对删除后剩余的9900个样本重新使用kmeans训练得到的结果记为$rerun$，结果如下：

可以看出， 运行删除算法的结果与重新训练删除后的数据集的结果基本相同，删除算法在效果上有保障。

最后，测试了运行删除算所需的时间：

kmeans的删除即为重新训练9900个样本。可以看到，qkmeans和dckmeans的删除效率是kmeans的$3\sim25$倍，在效率上有很大的提升。

2017013620 周唤海：查找数据集并进行数据预处理

2017011397 张嘉睿：实现Q-KMeans算法

2017011434 张小健：实现DC-Kmeans算法

2017013571 杨子江：进行数据分析评价