分布式聚类型缺失数据的回归插补方法

《Journal of Multivariate Analysis》：Distributed regression imputation for distributed cluster-type missing data

　　摘要为了解决插补精度低和计算成本高的问题，人们提出了修剪得分回归法作为处理含有缺失值的聚类数据的插补方法，该方法旨在实现簇内同质性和簇间异质性。然而，作为一种集中式方法，修剪得分回归法在大规模场景下存在严重的计算瓶颈。为克服这些限制，我们在分布式框架下提出了分布式修剪得分回归法。我们以Demi法和DRPCA法以及修剪得分回归法作为基准进行比较。通过模拟实验和真实数据分析，从插补精度和计算效率两个方面对分布式修剪得分回归法进行了评估。结果表明，该方法的插补精度与修剪得分回归法相当，且相比集中式版本显著降低了运行时间。同时，其运行时间与Demi法和DRPCA法相近，在精度和效率之间取得了更好的平衡。

引言聚类分析是一种基本的无监督学习方法，其目的是将数据集划分为互不重叠的子集，即簇（MacQueen，1967），从而实现簇内同质性和簇间异质性。它在数据挖掘、模式识别和工程应用中发挥着不可或缺的作用。然而，在现实世界的聚类任务中，由于设备故障、记录错误、仪器限制、数据传输丢失或人为因素，缺失数据十分常见。例如，天文数据往往因仪器限制或记录错误而存在缺失值，这会影响天体聚类的准确性。传感器故障可能导致温度和压力数据缺失。基因表达数据也可能因为芯片损坏、分辨率不足或杂交效果差而出现缺失，使得聚类分析难以可靠地进行。传统的集中式插补方法受到单机内存、计算能力和运行时间的限制，难以直接应用于超大规模数据集。此外，在物联网监测、多中心医疗系统以及跨机构数据协作等分布式场景中，由于隐私法规和带宽限制，原始数据无法整合到单个节点中。因此，如何实现对簇型缺失数据的准确、高效且分布式的插补，已成为一个亟需解决的实际问题。为确保在存在缺失值的情况下仍能进行可靠的聚类分析，需要解决若干关键问题。例如，如何在分布式系统中保证数据一致性和容错性？在进行聚类分析的回归插补时，如何选择合适的回归模型来预测缺失值而不引入偏差？如何在保持高插补精度的同时克服集中式方法的计算瓶颈？这些问题构成了本研究的出发点与动力。缺失数据处理和聚类分析已经得到了广泛研究，人们开发出了许多插补方法以提高不完整数据下的聚类精度和稳定性。例如，Tuikkala等人（2008）和de Souto等人（2015）的研究表明，适当的插补可以有效提升基因表达聚类和微阵列数据分析的性能。针对DNA微阵列数据，人们提出了多种缺失值估计方法，包括基于模糊聚类的方法（Honda等人，2001；Troyanskaya等人，2001；B?等人，2004；Celton等人，2010）、基于层次聚类的方法（De Brevern等人，2004）以及混合插补策略（Zhao等人，2015）。近年来，随着数据规模的扩大，分布式计算和隐私保护技术逐渐被应用于聚类和插补任务。Li等人（2017）和Lin等人（2020）研究的实时聚类技术使得在时间敏感型应用中能够对流式数据进行分析。分布式框架能够在多个节点上并行处理大规模数据，从而缓解了单机计算的局限性。然而，现有的分布式插补方法仍存在明显缺陷。基于分布式EM的插补法（Demi）在迭代过程中需要频繁交换局部协方差矩阵，从而导致较高的通信成本和较低的收敛速度。基于分布式PCA的插补法（DRPCA）则会导致插补精度下降，且对具有簇结构的数据缺乏鲁棒性。此外，一些其他分布式插补方法是为一般类型的缺失模式设计的，并非针对簇型缺失数据，因此无法充分体现聚类数据的结构特征。另外，Guo等人（2024）提出了一种用于多视图数据的在线正则化K均值聚类方法，通过矩阵分解和正则化手段防止过拟合。他们还开发了一种适用于高缺失比例K均值聚类的修剪得分回归法，提升了聚类精度。该修正后的修剪得分回归法基于主成分分析和修剪策略，能为含有缺失值的聚类数据提供高精度插补结果。但作为一种集中式方法，它依赖于全局奇异值分解和全样本回归，因此在处理大规模和超大规模数据时会导致极高的计算复杂度、过多的内存占用以及不可接受的运行时间。它还不支持分布式存储和分布式计算，这极大地限制了其在大数据场景中的应用。这些研究成果体现了聚类分析领域，尤其是在处理缺失数据和大规模数据集方面的巨大进步。然而，在面对簇型缺失数据时，现有的分布式插补方法面临着两难困境：分布式方法虽然通信成本较高，但插补精度不足或对簇型缺失数据的适用性较差。目前还没有一种方法能够同时实现高插补精度、分布式计算、低通信成本以及对聚类数据的良好适应性。正是这一差距促使我们提出了一种针对簇型缺失数据的新型分布式插补方法。为解决上述问题，我们提出了一种分布式修剪得分回归法，通过分布式架构优化插补过程，从而在大规模数据集中实现更高效的聚类分析。该方法将集中式修剪得分回归法扩展到分布式并行框架中，在保留其插补精度的同时提升了计算效率和可扩展性。本文的主要贡献如下：首先，分布式修剪得分回归法实现了大规模聚类数据的高效并行插补。通过划分数据集并在多个节点上进行分布式计算，该方法在保持与修剪得分回归法相当精度的同时，降低了运行时间和内存使用量，从而解决了修剪得分回归法在大规模场景下的计算瓶颈问题。其次，通过使用Guo和Niu（2024）提供的分布式修剪得分回归法包，在多项数值研究中，该方法在单变量缺失和一般缺失模式下均表现出较强的稳定性和适应性。它在不同的样本规模、特征维度、缺失比例和节点数量下都能保持高插补精度。第三，我们分析了分布式修剪得分回归法的通信复杂性，证明其与Demi法和DRPCA法相比具有更低的通信成本，尤其是在高维数据中更为明显。第四，我们给出了误差界限，证明分布式修剪得分回归法的插补结果与修剪得分回归法的结果在渐近意义上是一致的。通过大量的模拟实验和真实数据分析，验证了该方法的有效性、高效性和可行性。本文的结构如下：第2节详细介绍分布式修剪得分回归法及其缺失值插补流程；第3节介绍用于比较的分布式方法；第4节展示了多项实验结果，表明分布式修剪得分回归法不仅在精度上与现有方法相当，而且在计算效率方面更具优势；第5节为结论部分。

片段摘录分布式修剪得分回归法修剪得分回归法是一种用于处理聚类数据中缺失值的稳健方法，它基于主成分分析，旨在有效处理高缺失比例的数据。有关其应用情况，可参考Troyanskaya等人2001年、de Souto等人2015年以及Guo等人2024年的研究。该方法的主要步骤如下：•数据预处理：用列均值替换数据矩阵中的缺失值，从而构建完整的数据矩阵。然后对完整数据矩阵进行列中心化处理，确保每列都满足特定条件。比较方法分布式修剪得分回归法是一种分布式插补方法。为验证其在处理簇型缺失值方面的性能，我们采用了基于EMimpute和RPCA的Demi法（分布式期望最大化插补法）和DRPCA法（分布式正则化PCA法）作为分布式插补方法的对比对象。以下将介绍Demi法和DRPCA法。为进一步凸显分布式修剪得分回归法的通信效率，我们将其通信成本与两种主流方法进行了比较。准备对于每个数据子矩阵XId，其均方根误差值定义为RMSEd=1nId∑i,jnId,m(XId,ij?X?Id,ij)2,d∈{1,…,D}，其中XId,ij和X?Id,ij分别表示子数据矩阵XId中真实的值和缺失值的值。通过加权平均法，可以得到分布式指标RMSED，其计算公式为RMSED=∑d=1Dwd×RMSEd，其中wd为权重，即数据子矩阵XId的样本大小nId与总样本大小n的比值。RMSED值越小，表示……结论通过实验分析，从插补精度和计算效率两个方面验证了分布式修剪得分回归法在处理簇型缺失数据时的性能。具体而言，我们使用R软件生成簇数据，然后根据随机缺失原则创建单变量缺失模式和一般缺失模式的簇数据。我们使用分布式修剪得分回归法对这两种缺失模式下的模拟簇数据中的缺失值进行插补，同时还将Demi法、DRPCA法和TSR法用于对比。致谢作者们要感谢编辑和审稿人们的辛勤工作以及富有建设性的建议，这些都有助于大幅提升本文的质量。Guangbao Guo的研究得到了国家自然科学基金项目（NSSC23BTJ059）的支持。Guangbao Guo|James Allison|Guoqi Qian