一种针对分类数据的新聚类算法，采用基于MGR的参考集选择方法

《Neurocomputing》：A novel clustering algorithm for categorical data with MGR based reference set selection method

分类数据聚类中，现有方法仅考虑对象层次，未充分利用属性信息导致计算复杂。本文提出基于Mean Gain Ratio（MGR）的参考集选择方法，结合k-means算法，通过属性分层分析构建空间结构，减少数据量并提升效率。实验证明该方法在聚类精度和可扩展性上优于传统方法。

　　在当今数据科学与机器学习领域，随着各类数据类型的不断增长，对非数值型数据（即分类数据）的聚类分析逐渐成为研究的热点之一。分类数据因其不具有明确的数值空间结构，给传统的聚类方法带来了诸多挑战。许多研究者尝试通过将分类数据映射到欧几里得空间，以增强数据对象之间的可区分性。然而，现有的空间映射方法及分类数据聚类算法往往仅关注数据对象层面，忽略了分类数据本身的属性特性，未能有效利用属性信息对数据集进行缩减。此外，当数据集规模增大时，这些算法的时间复杂度显著增加，导致计算效率低下。

分类数据的属性本身具有划分数据集的能力。这意味着，通过分析属性层面的数据分布，可以更准确地选择能够代表数据分布的参考集，并构建合理的分类数据空间结构。基于这一认识，本文提出了一种新的分类数据聚类算法，该算法采用基于平均增益率（Mean Gain Ratio, MGR）的参考集选择方法。具体而言，该方法首先选取具有最高MGR值的属性，然后从该属性划分出的等价类中各选取一个对象，形成参考集。随后，将这种基于MGR的表示方法与k-means算法相结合，构建分类数据的聚类模型。实验结果表明，所提出的方法在聚类性能上优于现有方法，尤其是在处理大规模数据集时，表现出更高的时间效率和可扩展性。

聚类分析的目标是将相似的对象归为一类，将差异较大的对象分配到不同的类别中，从而更好地理解数据的结构和特征。传统聚类算法，如k-means，主要适用于数值型数据，因其能够利用欧几里得距离等几何度量方式来衡量对象之间的相似性。然而，随着数据类型的多样化，分类数据的处理成为一项更具挑战性的任务。分类数据通常由有限数量的离散值构成，缺乏自然的数值顺序，使得传统的距离计算方法难以直接应用。此外，分类数据的高维度和高基数（即每个属性可能有大量不同的取值）进一步增加了聚类的复杂性。

为了解决这些挑战，研究者们提出了多种分类数据聚类方法。例如，Huang在1997年提出的k-modes算法，通过引入汉明距离（Hamming distance）作为分类数据的度量方式，为分类数据聚类提供了重要的基础。汉明距离定义为两个分类向量在相同位置上取值不同的数量，适用于比较长度相等的分类数据。随后，研究者们在此基础上进行了诸多改进，如k-prototypes算法，它结合了k-means和k-modes的优点，适用于同时包含数值和分类属性的数据集。此外，SV-k-modes算法则通过引入创新的距离函数和集合值聚类中心表示，为处理集合值特征的分类数据提供了更优的解决方案。

尽管这些方法在一定程度上提高了分类数据聚类的效率和准确性，但它们通常依赖于基于重叠的度量方式，而这种度量方式存在两个主要问题。首先，这些方法假设所有属性之间是相互独立的，因此难以捕捉属性之间的相关性。其次，这些方法对属性值的分布较为敏感，如果某个属性出现频率过高，可能会对聚类结果产生不利影响。为了解决这些问题，Qian等人提出了基于结构的分类数据聚类（SBC）算法，该算法通过计算不同对象之间的相似性矩阵，将分类数据映射到欧几里得空间，再使用k-means进行聚类。然而，这种方法在处理大规模数据集时面临计算量大、内存占用高以及距离度量性能下降等问题。

为缓解SBC算法的计算负担，Zheng等人提出了基于预聚类的SBC算法（SBC-C），通过选择部分具有代表性的对象作为参考集，计算相似性矩阵，从而减少冗余计算，提高聚类的效率和准确性。此外，Zhang等人还提出了基于三元空间结构的分类数据聚类算法（TWSBC），该方法受到三元概念理论的启发，通过构建更精细的空间结构来提高聚类性能。然而，TWSBC算法的时间复杂度仍然较高，尤其是在处理大规模数据集时，三元方法带来的额外计算负担可能影响其应用范围。

近年来，研究者们越来越关注分类数据的分布特性，以更有效地计算对象之间的距离。例如，Kar等人提出了一种基于信息理论的新型距离度量方法（DME-KM），用于衡量分类数据点之间的差异。Kuo等人则开发了基于多变量模糊加权k-modes和概率距离的算法（MFWKM），该算法是对多变量模糊k-modes方法的扩展，能够更好地处理分类数据的复杂性。此外，针对分类数据的解释性问题，Hu等人提出了一种基于显著性的决策树聚类方法，通过将聚类结果与属性显著性联系起来，提高了模型的可解释性。对于更加复杂的异构特征数据，Chen等人引入了四元数图表示学习（QGRL）方法，利用四元数操作学习具有信息量的嵌入表示，从而提升分类数据聚类的效果。

为了更清晰地描述高维分类数据的属性子空间，Peng等人实现了一种多阶段增量子空间聚类算法（ICE）的原型。这些方法反映了当前分类数据聚类研究的最新趋势，即在传统聚类方法的基础上，探索更具鲁棒性、高效性和解释性的模型。

在本文中，我们提出了一种基于MGR的参考集选择方法，该方法通过分析属性层面的数据分布，选择能够更好代表数据分布的属性，进而从该属性划分出的等价类中选取参考对象，构建分类数据的空间结构。这种方法的优势在于，它能够充分利用分类数据的属性信息，减少数据集的冗余，同时保持较高的聚类精度。通过将基于MGR的空间结构表示方法与k-means算法相结合，我们构建了一种新的分类数据聚类算法（MGR-C）。实验结果表明，该算法在多个实际应用的分类数据集上表现优异，具有更高的准确性和可扩展性。

本文的主要贡献包括三个方面：首先，我们提出了一种基于MGR的参考集选择策略，该策略在计算复杂度上优于传统的预聚类方法；其次，我们开发了一种新的分类数据空间结构表示方法，该方法在计算时间上具有显著优势，使得算法能够更高效地处理大规模数据集；最后，我们将基于MGR的表示方法与k-means算法相结合，提出了一种新的分类数据聚类方法。实验结果表明，该方法在聚类精度上优于现有方法，同时在处理大规模数据集时表现出更好的性能。

在本文的结构安排上，第二部分将对与本文相关的熵值加权分类数据距离度量方法和基于空间结构的分类数据聚类算法进行简要回顾。第三部分将详细介绍我们提出的基于MGR的参考集选择方法和MGR-C算法。第四部分将通过对比实验分析我们算法的优势。最后，第五部分将总结本文的研究成果，并展望未来的研究方向。

通过引入基于MGR的参考集选择策略，我们为分类数据聚类提供了一种新的视角。这种方法不仅能够有效降低计算复杂度，还能够更好地利用分类数据的属性特性，提高聚类的准确性和效率。在实际应用中，分类数据广泛存在于医疗、金融、社会科学等多个领域，因此，开发高效且准确的分类数据聚类算法具有重要的现实意义。未来的研究可以进一步探索如何结合不同的属性选择策略，以适应不同应用场景下的分类数据特点。此外，还可以考虑引入更复杂的模型结构，以提高算法的鲁棒性和适应性。总之，本文提出的方法为分类数据聚类提供了一种新的解决方案，具有广阔的应用前景和研究价值。