A Novel Clustering Algorithm for Categorical Data With MGR Based Reference Set Selection Method

本文面向分类数据聚类中两个长期存在的难点展开研究：一是传统距离度量往往忽略不同属性的信息量差异，二是代表对象或参考集的选择会显著影响后续聚类质量与效率。作者提出一种基于 MGR（Mean Gain Ratio）的参考集选择方法，并将其与面向分类数据的加权距离度量和空间结构建模结合，形成新的 MGR-c 聚类算法，目标是在保证聚类效果的同时降低计算开销。

研究背景

分类数据聚类不同于数值数据聚类，属性之间通常不存在自然的大小关系，均值、方差等经典数值统计量也难以直接使用。以 k-modes 为代表的方法虽然在分类数据聚类中应用广泛，但通常面临几个问题：

1. 距离或不相似度设计过于粗糙，难以体现不同属性的重要性差异；
2. 聚类初始化或参考对象选择高度敏感，容易导致局部最优；
3. 当数据规模增大或属性空间复杂时，计算效率与稳定性都会下降。

从论文结构看，作者将已有工作归纳为三条主线：基于熵的分类距离加权、基于空间结构的分类聚类，以及三支决策/三路空间结构对分类聚类的支持。这说明本文不是仅在单一距离公式上做微调，而是试图把“度量设计 + 参考集表示 + 聚类机制”统一起来。

主要贡献

1. 基于熵的分类距离加权思想

   论文在相关工作中单列了“Entropy-based weighting for categorical data distance metrics”，表明该方法显式考虑属性的信息量差异。直观上，信息量更高、判别力更强的属性应在距离计算中占据更大权重，这能缓解所有属性被等权处理带来的聚类失真问题。

2. MGR 参考集选择机制

   论文的核心创新点体现在“ MGR based reference set selection for categorical data representation ”。从题名和章节命名可以判断，作者并不直接对原始对象逐一聚类，而是先通过 MGR 指标挑选具有代表性的参考集，再借助该参考集重构数据表示。这种思路的价值在于：

   • 降低对随机初始化的依赖；
   • 提升参考对象的代表性与区分度；
   • 为后续聚类建立更稳定的结构化输入。

3. MGR-c 聚类算法

   在“ MGR-c algorithm for clustering categorical datasets ”一节中，作者将加权距离、参考集选择和空间结构方法整合为完整算法。按照论文结构，这一算法应是全文的主体方法，重点不是单点改进，而是构建一套适合分类数据的聚类流程。

4. 空间结构视角的分类聚类建模

   论文专门讨论了“Space structure-based clustering for categorical data”与“三路空间结构（Three-way space structure）”。这意味着作者强调分类对象之间不仅是简单的点对点相似性关系，还可能存在更高层次的结构组织形式。将空间结构纳入聚类过程，有助于提升类别边界的可解释性和整体稳定性。

实验与结果解读

从章节结构可知，实验部分被分为四个层次：

1. Clustering performance analysis：验证聚类质量是否优于现有方法；
2. Computational performance analysis：评估运行效率与时间开销；
3. Scalability analysis：测试在更大数据规模下的适应性；
4. Ablation study：拆解 MGR 参考集、熵权距离、空间结构等模块的独立贡献。

这套实验设计说明作者关注的不只是“指标是否更高”，还包括算法是否可扩展、各组成模块是否真的有效。换句话说，这篇工作更偏向一篇完整算法论文，而不是只给出一个轻量级的改进公式。

从方法设计上看，本文最值得关注的点在于同时处理了聚类中的两个关键环节：

• 前端的数据表示与参考对象选择；
• 后端的相似性度量与结构化聚类机制。

很多分类聚类工作只优化其中一个环节，因此提升往往有限；而本文尝试把两端联动起来，这是它相对更有研究价值的地方。

简要评价

这篇文章的贡献可以概括为一句话：通过 MGR 驱动的参考集选择，把分类数据的“表示问题”和“聚类问题”耦合起来处理。

从研究路线看，它适合与以下方向结合：

• 面向大规模离散型数据的高效聚类；
• 具备可解释结构的分类数据表示学习；
• 将粗糙集、三支决策或信息粒化思想引入聚类框架。

如果后续要继续跟进这条线，一个自然的延伸方向是：把 MGR 参考集选择与深度离散表示、图结构聚类或混合型数据聚类进一步结合。

基本信息