基于实例学习[1]是一种重要的学习范式。k-最近邻（简称k-NN）[2]是一种代表性的基于实例的分类器，它将未标记的实例分配给其k个最近邻中最常见的类。由于其简单和有效性，k-NN分类器已被广泛应用于模式分类领域。大多数基于实例的分类器使用给定的度量来衡量未标记实例与其邻居之间的相似性。当属性为数值时，归一化欧氏距离是衡量实例相似性的自然度量标准。然而，对于许多应用程序来说，可能不存在一些自然的度量概念。在这种情况下，许多设计用于处理数值属性的基于实例的分类器将面临困难，并且通常使用更简单的度量来衡量分类属性值之间的距离。尽管这些简单的度量在某些情况下表现良好，但在其他情况下可能表现不佳。