SMFK-DPC：通过加权曼哈顿距离改进的密度峰聚类算法

《Knowledge-Based Systems》：SMFK-DPC: Enhanced Density Peak Clustering by the Weighted Manhattan Distance

SMFK-DPC通过加权曼哈顿距离与欧氏距离结合，优化局部密度估计和相对距离计算，并引入k近邻增强低密度区域聚类效果，有效缓解“多米诺效应”，提升复杂数据集的聚类精度，尤其擅长识别低密度簇。

　　密度峰值聚类（Density Peak Clustering, DPC）作为一种聚类算法，因其在检测聚类中心和形成具有实际意义的聚类结构方面的优势而受到广泛关注。然而，DPC在处理不同规模的数据集时，会使用不同的局部密度定义，这种依赖于截断距离（cutoff distance）的方式使得其结果对参数的敏感性较高。此外，DPC的高效单步分配策略可能会引发“多米诺效应”（Domino Effect），从而导致聚类结果偏移。尽管已有大量DPC的变种算法试图解决这些问题，但大多数仍仅依赖于欧几里得距离（Euclidean distance），忽视了特征数量及其数值变化对相似性的影响。这种不足常常影响低密度聚类的识别效果。为了解决这些局限性，我们提出了SMFK-DPC，一种通过加权曼哈顿距离改进的密度峰值聚类算法，它结合了标准差加权曼哈顿距离和加权欧几里得距离。这种双距离方法能够捕捉特征变化的影响，并在稀疏和密集区域之间平衡局部密度。此外，SMFK-DPC引入了k近邻（k-nearest neighbors）来增强低密度区域的相对距离，提高识别稀疏聚类中心的可能性。一个新的相似性度量方法，结合改进的两步分配策略，进一步减轻了“多米诺效应”并提升了整体聚类精度。在多个基准数据集上的广泛实验表明，SMFK-DPC在识别低密度聚类方面显著优于DPC及其变种，尤其在复杂数据集的聚类任务中表现突出。其改进的距离度量方法和稳健的分配策略，使得SMFK-DPC成为一种高效的解决方案。源代码可在GitHub上获取。

聚类分析是数据挖掘的重要方法之一，用于从数据中提取有价值的信息。它是一种无监督学习技术，适用于数据标签缺失的场景。聚类分析通过根据数据点之间的相似性将它们划分为不同的组，旨在组内具有高相似性，组间具有最大差异性。该方法在许多领域都有广泛应用，如图像处理、异常检测、消费者行为分析等。聚类算法大致可以分为五类：基于划分的聚类、基于层次结构的聚类、基于密度的聚类、基于网格的聚类以及基于模型的聚类。尽管存在多种类型的聚类算法，基于密度的聚类方法因其在检测任意形状聚类结构方面的优势而备受青睐。DPC作为一种基于密度的聚类方法，于2014年发表在《科学》杂志上。其基本原理是识别出具有较高局部密度且远离其他更高密度点的点作为聚类中心，利用决策图（decision graph）选择这些中心。随后，每个剩余点被分配到其最近的更高密度邻居所在的聚类，从而以简单高效的方式发现任意形状的聚类。然而，这种算法在定义局部密度时对截断距离或核函数的依赖性较高，导致其对参数的敏感性较强。此外，其在处理不同规模数据集时的局部密度定义存在差异，识别密度峰值需要人工干预，单步分配策略可能引发“多米诺效应”，即一旦某个点被错误分配到某个聚类，这种错误会在后续的分配过程中被放大，影响那些局部密度较低的点的分配结果。

为了克服这些限制，许多DPC的变种算法被提出。例如，KNN-DPC通过引入点的k近邻信息来估计其局部密度，从而减少对任意截断距离的依赖，并采用两步分配策略以减轻“多米诺效应”。FKNN-DPC进一步引入了模糊加权k近邻成员关系，以概率形式表示聚类分配，提升聚类精度。SFKNN-DPC则通过标准差加权的方式优化距离计算，认识到不同特征对点间距离的贡献可能存在差异。ANN-DPC采用自适应近邻的方法来定义点的准确局部密度，并结合超核心点吸收技术和依赖向量来同时识别密集和稀疏聚类中心。WANN-DPC在此基础上进一步优化，通过将自适应近邻划分为近邻和远邻，并对这两类邻居的贡献进行加权，从而获得更准确的点的局部密度。它能够自动检测聚类中心，识别聚类冠、聚类原型以及最终的聚类结果，减少人工干预，确保最终聚类尽可能准确。

MDDPC引入了两种度量方式来平衡局部密度，并结合基于密度分布的分配策略。DPC-CE将欧几里得距离与基于图的局部中心性连接度相结合，以评估潜在聚类中心的相似性，从而实现更可靠的中心选择。DPC-DLP利用k近邻的概念定义全局截断距离和局部密度，然后在基于图的框架中传播标签以完成聚类。R-MDPC通过其稳健的决策图有效确保聚类中心的识别，并通过在相关区域内的分配处理复杂聚类。AG-CPC引入了一种基于连接性峰值的聚类方法，通过引入新的连接性概念来识别低密度聚类和边界点，并采用稳健的两步分配策略，确保非密度峰值点被分配到最合适的聚类。

HFDPC引入了水平联邦学习（horizontal federated learning）和客户端参数传输的保护机制，以增强DPC的性能，缓解其“多米诺效应”。基于粒状球（granular ball）的密度峰值聚类算法引入了粒状球的概念，以粗粒度的方式表示数据，避免传统DPC的高计算复杂性，并使用粒状球的密度代替点的局部密度，以及使用粒状球的δ距离代替点的相对距离，从而在不使用任何参数的情况下，实现与原始DPC相似甚至更好的聚类效果，同时运行时间显著减少。Bombing结合了全局（修改后的高斯核密度）和局部密度（基于k近邻）的估计，并通过“轰炸”过程从核心点向外传播聚类，以有效缓解聚类形状、重叠和噪声的影响。此外，Bombing可以通过分析邻接度来自动检测最优的聚类数量。

尽管这些方法在一定程度上提高了DPC的性能，但新的方法仍然面临挑战。基于k近邻的方法虽然减少了对截断距离的依赖，但对k值的选择和高维数据中的噪声仍然较为敏感。模糊和标准差加权方法虽然更加稳健，但可能增加计算负担和参数复杂度。基于图的方法如DPC-CE可能在可扩展性方面存在不足，并对稀疏或高维数据较为敏感。标签传播方法如DPC-DLP和Bombing有时会导致错误的传播。稳健的R-MDPC无法用于极高维数据集的聚类。此外，对于数据集中包含极高密度和极低密度聚类的情况，识别正确的聚类中心仍然是一个具有挑战性的问题。然而，每个变种都在一定程度上加强了DPC的性能，拓展了其适用范围，并提高了聚类效果。同时，数据预处理在识别数据集中隐藏的真实聚类结构中也起着重要作用，特别是在现实世界的应用场景中，如将同一个体或同一物种的图像进行分组，或者进行图像特征提取，这些预处理步骤对最终的聚类算法结果至关重要。

SMFK-DPC算法的提出正是为了应对上述挑战。该算法的核心创新在于采用加权曼哈顿距离和加权欧几里得距离的组合，以更全面地捕捉数据点之间的相似性。曼哈顿距离能够反映每个特征维度的差异，而欧几里得距离则更关注整体空间中的距离。这种双距离方法能够更好地处理不同特征对点间距离的贡献差异，同时避免单一距离度量带来的局限性。在计算过程中，SMFK-DPC首先计算点之间的标准差加权曼哈顿距离，然后基于该距离估算点的局部密度和相对距离。接下来，通过引入k近邻机制，进一步增强低密度区域的相对距离，从而更有效地识别稀疏聚类中心。此外，SMFK-DPC还设计了一种新的相似性度量方法，结合改进的两步分配策略，以更精确地分配点到合适的聚类，同时减轻“多米诺效应”的影响。

在实验验证方面，SMFK-DPC在多个基准数据集上进行了测试，包括10个合成数据集和10个来自UCI机器学习仓库的现实世界数据集，以及5个高维基因数据集。实验结果表明，SMFK-DPC在识别低密度聚类方面表现优于DPC及其变种算法，尤其是在处理混合密度数据集时，能够更准确地识别稀疏和密集区域的聚类中心。此外，SMFK-DPC在保持高计算效率的同时，提高了聚类结果的鲁棒性。其改进的距离度量方法不仅增强了对不同特征的适应能力，还有效缓解了对参数的依赖性，使得算法在实际应用中更具灵活性和稳定性。

从理论角度来看，SMFK-DPC的改进基于对数据特征多样性的深入理解。在传统DPC中，局部密度的定义依赖于固定的截断距离，这在处理不同规模的数据集时可能无法准确反映数据的真实分布情况。而SMFK-DPC通过引入标准差加权曼哈顿距离，能够更精确地衡量不同特征对点间距离的影响，从而在识别聚类中心时减少人为干预。同时，该算法通过k近邻机制，增强了低密度区域的相对距离，使得稀疏聚类中心更容易被识别。在实际应用中，这种方法能够有效应对数据集中存在的噪声和重叠问题，提高聚类结果的准确性。

此外，SMFK-DPC的两步分配策略进一步优化了聚类过程。在传统DPC中，单步分配策略可能导致错误的传播，使得后续的点被错误地分配到同一个聚类。而SMFK-DPC的两步分配策略能够更有效地纠正这种错误，提高聚类结果的鲁棒性。该策略首先基于局部密度和相对距离对点进行初步分配，然后通过进一步的优化调整，确保每个点被分配到最合适的聚类。这种方法不仅减少了“多米诺效应”的影响，还提高了整体的聚类精度。

在应用层面，SMFK-DPC的改进使其能够更好地适应复杂的数据集。特别是在处理包含极高密度和极低密度聚类的数据集时，传统的DPC方法往往难以准确识别所有聚类中心，而SMFK-DPC通过结合标准差加权曼哈顿距离和加权欧几里得距离，能够在不同密度区域之间建立更合理的平衡。这种平衡不仅有助于识别稀疏聚类中心，还能够避免对密集区域的误判，提高聚类结果的全面性和准确性。

在实际应用场景中，SMFK-DPC的性能得到了验证。例如，在图像处理领域，该算法能够更有效地识别不同个体或物种的图像，提高图像分组的准确性。在异常检测中，SMFK-DPC能够更精确地识别出异常点，避免误将正常点归类为异常。在消费者行为分析中，该算法能够更准确地识别出不同群体的消费者行为模式，提高分析结果的可靠性。这些应用表明，SMFK-DPC不仅在理论上具有创新性，在实际应用中也展现出良好的性能。

此外，SMFK-DPC的改进方法在计算效率方面也有所提升。相比于传统DPC，该算法在计算过程中采用了更优化的距离度量方式，减少了不必要的计算步骤，从而提高了整体的运行效率。同时，其两步分配策略能够在保持高效的同时，提高聚类结果的准确性，使得算法在处理大规模数据集时更具优势。这些改进使得SMFK-DPC在实际应用中更加实用，能够满足不同场景下的需求。

总的来说，SMFK-DPC作为一种改进的密度峰值聚类算法，通过引入标准差加权曼哈顿距离和加权欧几里得距离的组合，结合k近邻机制和两步分配策略，有效解决了传统DPC在处理不同规模数据集时的局限性。该算法不仅提高了对参数的鲁棒性，还增强了对不同特征和密度区域的适应能力，使得聚类结果更加准确和可靠。在实际应用中，SMFK-DPC展现出良好的性能，能够适应各种复杂的数据集，包括混合密度、高维数据等。这些优势使得SMFK-DPC成为一种高效且实用的聚类解决方案，具有广泛的应用前景。