面向名义和序数属性的分类数据聚类中可学习加权内部属性距离

# 分类数据聚类中名义与有序属性内距离的可学习加权方法  
**来源：** https://arxiv.org/html/2607.05464  

###### 摘要  
分类数据聚类的成功通常很大程度上依赖于衡量两个对象之间差异程度的距离度量。然而，现有的聚类方法在计算差异时大多将两种分类子类型（即名义属性和有序属性）同等对待，而未考虑有序值之间的相对顺序信息。此外，名义属性和有序属性之间可能存在相互依赖关系，这种关系值得探索以指示差异。因此，本文将从类似图的角度研究名义和有序属性值的内在差异与联系。据此，我们提出了一种新颖的距离度量，以统一的方式测量名义属性和有序属性的属性内距离，同时保留有序值之间的顺序关系。随后，我们提出了一种新的聚类算法，将属性内距离权重的学习与数据对象的分区整合到单一学习范式中，而非两个独立步骤，从而避免次优解。实验表明，与现有算法相比，所提算法具有有效性。  

###### 索引词：  
分类数据聚类、名义与有序属性、属性内距离、可学习加权。  

## 1 引言  

广泛存在的分类数据可通过问卷调查、医疗量表、评分系统等轻松收集[1]。作为最常用的机器学习和模式识别技术之一，在无监督环境中将数据对象划分为同质组的聚类[7,26]已被普遍用于分类数据分析[25,56]。为了更好地发现同质簇，许多现有聚类算法[20,9,32,6,28]采用根据属性对聚类任务的重要性进行加权的方法[57]。由于对属性加权等价于对该属性上测量的所有属性内距离进行均匀加权，这些算法实际上基于一个假设：所有属性内距离都已得到良好定义，这对于具有明确定义距离度量的数值数据[48]是合理的。然而，对于距离度量通常未良好定义的分类数据，均匀加权属性内距离显然不合理[12]。  

为解决此问题，大多数现有方法集中于探索适当的距离度量[8,4]和属性加权机制[28]。在探索适当距离度量的成功尝试包括：Lin的[41]相似性度量、耦合[29]相似性度量、基于关联的[35]、Ahmad的[3]、基于上下文的[23,24]以及Jia的[27]距离度量。上述度量根据可能值的统计信息（例如出现频率和条件出现概率）定义属性内距离。Lin的度量计算有序可能值范围（例如，对于一个可能值为{非常好，好，一般，差，非常差}的有序属性，相邻可能值{好，一般，差}的累积熵）来指示相应的属性内距离（即好与差之间的距离），同时保留顺序关系，适用于有序数据的距离测量。其他度量则根据相互依赖属性间条件概率分布所反映的上下文信息定义属性内距离，对名义数据效果良好。近年来，更强大的基于表示的方法（包括基于结构的[49]、耦合的[30,31]和异质耦合[63]表示）被提出，通过嵌入值、属性和对象层面更丰富、更复杂的关系来表示分类数据，从而实现更合理的距离测量。不幸的是，它们仍然仅对名义数据有效。  

总之，上述所有度量在提出时均未考虑一个非常常见的情况：真实分类数据通常由名义属性和有序属性混合组成[2,33]。如表I所示的医疗量表数据集片段，有序属性1的值代表淋巴结肿大的程度，名义属性2的值代表淋巴结的特殊形态，类别属性的值表示诊断结果，即聚类分析中期望的真实簇标签。  

**表I：淋巴结造影数据集片段**  
| 编号 | 属性1（肿大） | 属性2（形态） | 类别（诊断） |
|------|----------------|----------------|--------------|
| 1    | ↑              | non-special    | normal       |
| 2    | ↑              | vesicles       | fibrosis     |
| 3    | ↑↑             | vesicles       | fibrosis     |
| 4    | ↑↑↑            | chalices       | metastases   |
| 5    | ↑↑↑            | chalices       | malign       |
| 6    | ↑↑↑↑           | vesicles       | malign       |

在医学上，通常认为纤维化、转移和恶性的严重程度依次递增。显然，如果将属性1的有序值视为名义值，属性1值与真实类别标签之间的单调关系所提供的信息将丢失[19]，这直接影响聚类精度。此外，名义属性和有序属性提供的簇信息之间存在尴尬的差距，因为有序属性的值包含相对顺序信息，而名义属性的值则没有。因此，为避免重要信息丢失，基于熵的距离度量[59,62]被提出，以信息熵[46]的统一方式量化名义属性和有序属性的属性内距离。然而，它们并未为数据聚类建立名义属性与有序属性之间的本质联系。  

至于属性加权机制，大多数工作尝试为每个簇加权属性，这称为子空间聚类。典型的子空间方法包括[20,9,6,28]，它们为每个簇学习不同的属性权重组合，以探索更合适的子空间来聚集同质数据对象。然而，它们对同一属性上测量的所有属性内距离进行均匀加权，这使得这些方法仍无法调整不同属性内距离的贡献，以搜索更合适的聚类结果。最近，一种基于距离加权的聚类算法[61]被提出，能够在聚类过程中自动学习属性内距离的权重。该算法在有序数据集上表现显著，但它依赖于属性值之间的顺序关系来学习距离权重，因此仅适用于有序数据。据我们所知，能够为包含名义和有序属性的分类数据学习属性内距离权重的聚类算法尚未被提出。  

在本文中，我们将提出一种新的聚类方法，包含新颖的距离定义和自动距离加权机制，适用于任意类型的分类数据聚类，即由名义属性和有序属性任意组合而成的数据。具体来说，我们研究名义属性和有序属性的内在差异与联系，并将名义属性的每个可能值（例如表I中属性2的“vesicles”）转换为一个布尔属性，具有两个可能值“vesicles”和“not vesicles”。这种布尔属性是有序属性的特例，即具有两个极端程度“vesicles”和“not vesicles”的有序属性。因此，名义属性和有序属性提供的异质聚类信息变为有序属性提供的同质信息。在此基础上，利用三种情况（即(i)两个属性均为名义属性，(ii)两个属性均为有序属性，(iii)一个为名义属性、另一个为有序属性）中相互依赖属性提供的信息，以统一方式测量名义属性和有序属性的属性内距离。由于定义的距离未与特定聚类任务关联，我们还提出了一种新颖的属性内距离加权机制，根据当前数据分区结果迭代学习距离权重，以搜索更好的聚类结果。所提出的距离定义和加权机制在聚类中相互补充。事实证明，利用它们的聚类算法能够胜任任意类型分类数据的聚类分析。  

本文的主要贡献总结如下：  
- • 研究了名义属性与有序属性的内在联系，并据此提出了一种适用于任意类型分类数据聚类的属性内距离测量新方法。  
- • 设计了一种属性内距离加权机制，通过迭代更新距离权重以搜索更好的数据分区（如果存在），使得测量的属性内距离变得可学习。  
- • 利用可学习的距离度量提出了一种新的分类数据聚类算法。该算法无参数，且在任意类型分类数据上具有优越的聚类性能。  

本文其余部分组织如下。第2节回顾相关工作。第3节阐述研究问题。第4节提出同质距离度量的设计。然后，第5节介绍以新颖距离加权机制为核心的新聚类算法。第6节给出实验结果。最后，第7节进行总结。  

## 2 相关工作  

本节概述现有的分类数据聚类相关研究工作。  

### 2.1 距离度量  

用于分类数据聚类的距离度量大致可分为直接度量、基于上下文的度量和基于表示的度量。最简单的直接度量[5]分别将相同和不同的属性内距离赋值为0和1。其他直接度量[41,60,59]根据可能值的出现频率计算两个可能值之间的属性内距离。直接度量易于使用且计算效率高，因为其计算不涉及参数选择、上下文信息提取、迭代学习等。然而，由于完全忽略了相关属性提供的有价值信息，它们定义的属性内距离在指示真实差异程度时并不总是合理。  

相比之下，基于上下文的度量[29,35,3,23,24,27,62]根据上下文信息（即与目标属性相关的其他属性提供的统计信息）计算两个属性内值之间的距离。通常，这些度量优于直接度量，但其性能更依赖于属性间的相互依赖关系。对于由独立属性组成的数据，一些仅依赖于相互依赖属性提供信息的间接度量[35,3,23,24]甚至可能在距离测量中失败。  

在上述所有间接和基于上下文的度量中，有两种度量[59,62]将名义属性和有序属性的距离概念统一为信息散度以避免信息损失，适用于任意类型分类数据聚类。然而，它们仅提供了尺度层面的距离统一，尚未考虑名义属性与有序属性之间的内在联系。  

基于表示的距离度量将分类值编码为数值，然后可以利用为数值数据提出的高级距离度量和聚类算法。在许多实际应用场景中，编码由领域专家完成，这使得性能对先验知识敏感。此外，对于大规模、高维度、多变量的分类数据，编码过程是一项费时且不平凡的任务。绕过这些问题的常用方法是将名义属性的每个可能值简单编码为二值数值属性，并将每个有序属性的有序可能值编码为连续整数，这称为简单编码。事实证明简单编码适用于任何类型的分类数据。然而，由于它忽略了可能值的原始统计信息，并且为不同的...