非完整数据聚类初探
目录
2 基于惩罚不相似方法的缺失值聚类 (Machine Learning, 2018)
3 基于最优运输的深度分布保留(Distribution-preserving)非完整数据聚类 (arXiv, 2021)
面向非完整数据的聚类，目前分为两种框架，分别是非完整多视图聚类和非完整单视图聚类。然而，两阶段的聚类模型，容易忽略填补对聚类过程的负面影响。同时，有文章表明非完整数据聚类，其核心是尽量缓解由缺失值导致的聚类中心偏移或者不确定性的问题。
本期分享关注单视图的非完整数据聚类，即原始数据含缺失，对含缺失的原始数据执行聚类操作。
下面分析一下关于致力于聚类的填补一点思考：
传统的先填补后聚类的想法，在标签缺乏的情况下，只能从已有的完整数据分布中进行学习，从而协助填补，但是此时填补对于聚类的好坏无法评判。聚类是无监督学习，此时填补是不带标签的填补，即无法评估填补的好坏。
两阶段的方式，并不能保证对下游任务是最优的。此外，填补的好坏在聚类任务中是无法评估的，但是其终极目的还是为下游任务提供服务。在实际包含缺失且标签缺乏的序列数据中，填补的好坏评判是一个伪命题。因此，此时采用一阶段，通过聚类来指导填补，同时填补更加有利于聚类。
真实数据的填补，由于没有标签，所以就没有判别的准则。但是已有的文章说有已有的完整数据，来指导缺失的数据进行填补，这样的思路，在实际的实验过程中，是否可行？是否需要用相似度来衡量填补的好于坏呢？
最后放一下关于三种不同缺失模式的解释，此处解释的原始来源于我对接的大三本科同学的周报内容：
缺失值分为两种：存在但尚未被观测到，或根本不存在。
1）MCAR，完全随机缺失：
定义：某个变量是否缺失与它自身的值无关，也与其他任何变量的值无关。例如，由于测量设备出故障导致某些值缺失。
特点：MCAR机制方便我们处理数据，但往往不切实际。
2）MAR，随机缺失：
定义：某个变量是否缺失与它自身的值无关，但和其他变量已观测到的值有关。如：人们是否透露收入可能与性别、教育程度、职业等因素有关系。如果这些因素都观测到了，而且尽管收入缺失的比例在不同性别、教育程度、职业的人群之间有差异，但是在每一类人群内收入是否缺失与收入本身的值无关，那么收入就是随机缺失的。
特点：MAR比MCAR更具一般性，更符合实际。现代缺失数据方法通常从MAR假设开始。
3）MNAR（NMAR），非随机缺失：
定义：某个变量是否缺失不仅和其他变量的值有关，还与它自身的值有关。如：在控制了性别、教育程度、职业等已观测因素之后，如果收入是否缺失还依赖于收入本身的值，那么收入就是非随机缺失的。
特点：三种缺失机制中最复杂的一种。处理策略是找到有关缺失原因的更多数据，或者用假设分析来查看结果在各种情况下的敏感性。
1基于模糊C均值的非完整数据聚类 (TSMC, 2001)
代码：暂无
1.1动机
现实生活场景中，由于数据采集和存储不当，导致数据经常是缺失的。模糊C均值(FCM)算法是一种有效的聚类算法，然而不能直接用于非完整数据的聚类。
1.2贡献
本文针对传统的FCM不能用于缺失数据聚类的问题，提出了四种面向非完整数据聚类的策略，其中三种属于FCM算法的修改版本，并且这四种方法都提供了聚类中心位置的估计值和数据的模糊分区。
本文方法的目标是将数据集划分为模糊的簇，并给出其聚类簇中心的估计值。具体的示例图如下：
上图1左边表示完整的数据，对应下方两个圆圈的簇中心。图1右边表示缺失后的数据，而实际可能会预估出四个不同的簇中心位置。上述示例说明了不完整数据数据所面临的一个固有的困难问题。
（1）整体数据策略(Whole Data Strategy, WDS)
如果不完整数据的比例很小，那么可以简单地删除所有不完整数据，对剩余的完整数据应用FCM。本文将其称为整体数据策略(WDS)。上述简单策略实施的前提是，完整可观察到的数据占比大于75%。
本策略可能对估计簇中心起到有效作用，然而其没有利用对应列的完整信息，从而造成了信息缺失。本文将该策略简称为WDSFCM。
（2）部分距离策略(Partial Distance Strtegy)
本策略是由Dixon[1]推荐使用所有可用的(即非缺失的)特征值来计算部分(欧几里得)距离，然后用所使用组分比例的倒数来缩放这个量。本文将其称为部分距离策略(partial distance strategy, PDS)。具体估计公式如下：
本文将上述策略称为PDSFCM。采用上述策略可以直接为包含缺失数据计算到具体簇中心的隶属度，或者说软标签。
（3）最优补全策略 (Optimal Completion Strtegy, OCS)
第三种不完整数据的FCM聚类方法是基于我们所说的最优补全策略(OCS)。在这种方法中，我们视缺失的组件为我们优化的额外变量，以获得FCM函数的最小可能值。也就是说，我们的策略是通过使给定可用数据的可能值最小的方式来补全数据集缺失的部分。对FCM的这种修改，在这里称为OCSFCM。
具体的算法步骤如下：
我的个人见解：采用模糊的簇中心，以及当前的数据隶属度来完成对应数据缺失部位的补全，并且使得最终的簇中心估计的损失最小。本策略其中的距离计算采用的是策略2中PDSFCM算法公式。
（4）最近原型策略(Nearest Prototype Strategy, NPS)
最后一种方法使用最近原型策略(NPS)，可以描述为OCSFCM的一个简单修改。将OCSFCM算法中的步骤5：
修改为如下：
在一个不完整的数据与两个或多个原型的距离相等的罕见情况下，在定义时必须使用打破平局的规则。虽然NPSFCM在所有数值试验中都是终止的，但我们还没有从理论上确定该过程必须收敛。
1.3实验分析
本文的实验主要对比WDS, PDS，OCS和NPS结合FCM执行非完整数据距离的效果。其中，WDS适用缺失率低可直接忽略数据，PDS直接使用缺失的数据执行距离计算，即不需要采用填补手段，而OCS和NPS均是对缺失部分执行了填补，而NPS则是采用了PDS含缺失数据计算距离的思路，对OCS算法最后一步的填补进行了置换。
基于后四列的误差，OCS方法的原型估计精度至少与其他方法相同。最简单的策略，WDS，提供了高达20%的良好测试错误。尽管PDS、OCS和NPS的总体准确率和误分类误差在最坏的情况下(75%)非常相似，但PDS方法几乎总是比其他三种方法需要更少的迭代。
上图是作者仿照IrIs数据集做的人工合成缺失数据实验，最终距离成为两个簇，刚好和文章的图1和图2对应。
另外，是距离效果相差不大的情况下，即当数据结构清晰时，所有四种方法都相当平等，在这种情况下最好的选择可能是选择 WDS 或 PDS，它们都比 OCS 和 NPS 终止得更快。
WDS能够以最快的速度收敛。同时，就分类错误而言，NPS 和 OCS 是整体表现最好的。PDS 和 WDS 在终端原型精度方面表现良好。
1.4我的思考
本文的策略2提出的PDS策略，直接采用含缺失数据计算距离执行聚类的思想，能够在有效确保原始数据信息不丢失的情况下，只能聚类，并且还不会引入填补的误差，这个误差有好也有坏。这样的策略，可以反映一个问题：即非完整数据的聚类并不一定需要补全，关于该策略后续看看有没有最新的文章能够分析清楚该问题。
2 基于惩罚不相似方法的缺失值聚类 (Machine Learning, 2018)
2.1 动机
许多真实世界的聚类问题都被不完整的数据所困扰，这些数据的特征是缺少某些或所有数据实例的特性。如果不进行填补或边缘化预处理，传统的聚类方法是不能直接应用于这类数据。
零填补和均值填补，其目的均是为分类或者聚类服务，但是这样的填补是属于两阶段，割裂了与分类或者聚类的联系。另一方面呢，目前已有的填补方法追求填补的好于坏，这是建立在有完整数据的假设前提下，这在实际真实缺失的填补是无意义的，或者说是一个假命题。
假命题的解释：如果缺失位置对应的其它数据只能拥有很少或者有效的真实分布，那么在这样的情况下执行填补是无意义的。那么在这样的情况下，简单地执行零填补或者均值填补，或者对当前所在列缺失较大的数据全部舍弃处理，直接对包含有效信息的完整未缺失或者缺失程度较小的数据执行聚类可能会更好。
另外，一般把原始完整数据进行缺失处理后，原始的数据分布可能就会发生变化，即其有较大可能变成了一种不同的分布，此时在这样的分布上进行填补，其核心目的是为了聚类更好，而不是为了填补更好。如果是为了填补更好，按这个问题就是研究填补了，而不是聚类。此外，填补也是不可避免会为聚类带来偏差和误差。
当缺失位置的特征数据依赖于观察到的特征时，此时填补的好很大可能是有利于聚类，反之则可能没有帮助，甚至会导致聚类效果变差。
缺失值进行忽略或者边缘化不能应用于有大量缺失值的数据，因为它可能会导致大量信息的丢失。因此，需要用复杂的方法来填补数据中的空缺，从而可以随后使用传统的学习方法。
然而，这些技术中的大多数都假定缺失模式为MCAR或MAR，因为这允许使用更简单的缺失模型。这样简单的模型不太可能在MNAR情况下表现良好，因为缺失模式也包含信息。由于MNAR缺失模式的数据也包含重要信息， 因此必须设计其他方法来处理不完整的数据。此外，先填补再聚类往往会导致数据中引入噪声和不确定性
2.2 贡献
在本文中，我们利用一种惩罚性的不相似测度来克服这一缺陷，我们称之为基于特征加权惩罚的不相似测度不同(FWPD)。利用FWPD测度，我们对传统的k-means聚类算法和标准的分层聚类算法进行了改进，使其直接适用于特征缺失的数据集。 （即无需填补，直接采用包含缺失的原始数据，且不会丢失原始数据信息的情况下执行聚类操作）
我们对这些新技术进行了时间复杂度分析，并进行了详细的理论分析，表明新的基于FWPD的k-means算法在有限的迭代次数内收敛到局部最优。我们还提出了一种详细的模拟随机和特征依赖缺失的方法。
由于公共观测子空间中的距离不能反映未观测子空间中的距离，PDS得到了不恰当的距离估计值。如前所述，这是PDS（2001年TSMC的部分距离相似）方法的主要缺点。由于两个数据实例之间的观察距离本质上是它们之间欧几里德距离的一个下界(如果它们被完全观察到的话)，在这个下界上加一个适当的惩罚可以得到实际距离的一个合理的近似。本处提到的基于惩罚项的部分距离相似策略，和PDS的区别在于加了一个简单的惩罚项目，简单示例如下：
不同缺失填补处理策略，和原始真实完整数据直接的距离差异如下：
特征权重惩罚项的定义如下：
依据上述的特征权重惩罚项，结合PDS距离，和定义的相关联的超参数alpha，得到的基于特征权重惩罚项的距离度量公式如下：
结合上述提到的FWPD距离相似度量策略，本文作者将其集合K-means算法执行距离，即可以直接对非完整缺失且无需填补操作的距离，具体步骤如下：
其中z表示簇中心，u表示当前数据属于哪个簇，最后依据u和原始数据x进行加权平均求取最终的簇中心。
2.3实验分析
本文实验所用数据集如下：
上述未使用真实缺失数据集，去拿不都是UCI或者JGD上面的真实完整数据集。
下述实验结果用于表明K-means-FWPD与多种先填补后聚类方法模型的对比，分别在四种不同缺失机制下的实验结果：
上述实验结果表明，本文提出的无需填补的K-means-FWPD方法的聚类效果要明显优于先填补后聚类的方法。另外，采用KNNI执行填补然后聚类的效果要大概率优于零填补、均值填补和SVDI填补方法，说明设计好的填补方法大概率也是有利于聚类。
2.4 我的思考
本文最大的亮点在于深入探讨分类不填补和相对于填补聚类的优势，并且分析了三种不同缺失机制下的聚类效果，并且进行了分析。本文的实验内容比较详尽，可以作为直接采用原始缺失数据执行聚类，本文的方法可以重点考虑作为采用填补结合聚类模型的重点baseline方法。在非完整数据聚类的研究中，后续可以考虑如何采用深度学习模型对含缺失的数据直接执行聚类，而无需填补的操作。
3 基于最优运输的深度分布保留(Distribution-preserving)非完整数据聚类 (arXiv, 2021)
代码：暂无
3.1 动机
聚类是计算机视觉和机器学习领域的一项基本任务。虽然已有各种方法被提出，但现有方法在处理不完整的高维数据(这在现实应用中很常见)时性能会急剧下降。
3.2 贡献
为了解决这一问题，我们提出了一种新的深度不完全聚类方法，即DDIC-OT (deep Distribution- preserving incomplete clustering with Optimal Transport)。为避免现有方法中全观测样本较少而导致样本利用率不足的问题，我们提出用最优传输度量分布距离来进行重建评估，而不是传统的像素级损失函数。此外，引入潜在特征的聚类损失，使嵌入规则化，具有更强的识别能力。因此，该网络对缺失特征具有更强的鲁棒性，而将聚类和样本imputation结合起来的统一框架使这两个程序能够更好地相互协商服务。
本文模型的框架如下：
OT的分布Loss定义如下：
本文的聚类Loss沿用了ICML2016年的DEC中的KL散度Loss, 其联合优化思路沿用了IJCAI2017年的IDEC模型和框架，具体如下：
3.3 实验分析
本文两阶段中的深度填补方法策略中的GAIN, VAEAC和MIWAE方法都是MDIOT填补方法(ICML, 2020)文章中的重点对比方法，即其填补的效果都要比MDIOT差。本文采用了六种高维数据集，具体的缺失处理机制在文章中没有说明，具体的实验效果如下：
消解实验分析如下：
模型的初始化填补值的分析如下，分别采用零值和均值填补处理：
3.4 我的思考
本文最大的贡献在于将IDEC 2017年的IJCAI文章中的重构loss置换为了OT分布Loss，然后对于原始高维缺失数据采用Encoder-Decoder模型进行embedding的学习，并且采用OT分布Loss进行样本分布上的重构，而以往的完整数据是基于原始图片像素级别的重构。本文模型的实质是没有对原始相似缺失部分进行填补处理，而是对学习的特征表示进行Decoder后采用OT loss执行样本分布上面的重构。
然而，对于OT loss实现样本分布层面的重构后，就能大幅提高最终的聚类效果：我的猜想，即原始未缺失部分的数据就具有较强的聚类判别性能，而采用简单的零值或者均值填补后，很大可能会引入填补的误差，即使得聚类性能变坏的误差。而且本文采用的高维数据集都是IDEC文章中和DEC2016ICML文章中模型经过精细化调参能够学习良好Embedding执行聚类的数据集。对于本文模型的鲁棒性，如果尝试采用MNAR和MNR缺失机制参数的高维数据集，或者采用CIFAR10等三维像素数据集，采用MCAR缺失处理，然后使用本文的模型执行聚类的效果可能并不能取得理想的结果。
最后，对于本文的实验，其中最大的一个质疑就是：作者没有提供其在真实高维缺失数据集上的聚类效果，本文所使用的数据集都是图像或者文本领域最基准的baseline数据集，其缺失处理都是人工制造的缺失，相关数据集的聚类可能会受到模型的encoder影响较大，如果换一个真实的非完整数据集执行聚类分析，模型的鲁棒性需要等待进一步验证和分析。此外，本文对于缺失的机制（PS：目前公认有三种，分别是MCAR, MNAR和MNR）没有探讨和分析，这也是本文一个亟需解决的问题。
4 基于Split神经网络含缺失特征的层次聚类的鲁棒性探讨 (AAAI, 2021)
本文基于一篇2018年直接采用缺失数据训练神经网络的工作，提出了一种层次聚类的分割神经网络，能够直接对非完整数据（只需要执行简单的均值填补）进行建模学习，从而提高最终的分类效果(或者说能够达到较好的分类效果，且只需要简单的填补处理)。
本文的标题中虽然又说是做聚类，但是其实际的任务是做分类，另外本文一个AAAI的学生版本，总共只有两页，不过本文在后续可以考虑作为含缺失数据聚类的深度学习模型作探讨和研究。
5 如何采用Rubin规则衡量面向缺失数据聚类的性能？ (arXiv, 2020)
代码：暂无
本文表明多重填补是处理缺失数据的常用方法，但是如何评估非完整数据聚类的不稳定仍然是一个问题。针对上述问题，本文提出采用bootstrap理论集合多重填补解释了不完整数据聚类的不稳定性问题。