非度量距离是什么？不满足三角不等式等公理的“距离”

非度量距离（Non-Metric Distance）是指那些不完全满足数学上“距离”定义的全部条件的距离或差异度量。在机器学习和数据分析中，我们常常需要衡量两个对象之间有多相似或者有多不同，而现实中很多有用的衡量方式，并不满足严格的数学距离的要求。

什么是“度量”

在数学中，一个函数要成为真正的距离，也叫度量，需要满足四个基本的条件：非负性，任意两点之间的距离不能是负数；同一性，一个点到它自身的距离为零，并且只有完全相同的两个点之间距离才为零；对称性，从 A 到 B 的距离等于从 B 到 A 的距离；三角不等式，从 A 直接到 C 的距离，不会超过从 A 经过 B 再到 C 的距离之和，也就是“两点之间直线最短”。我们熟悉的欧氏距离、曼哈顿距离都满足这四个条件。不满足其中任何一个或多个条件的距离，就被称为非度量距离。

不满足三角不等式的例子

周志华在《机器学习》中举过一个很好的例子：在衡量概念的相似程度时，“人”和“马”很不相似，但“人马”（神话中的半人半马）与“人”很相似，与“马”也很相似。如果用相似程度来定义距离，那么“人”到“人马”的距离很小，“人马”到“马”的距离也很小，但“人”到“马”的距离却很大，大于前两者之和，这就违反了三角不等式。这说明，人类对相似性的判断往往并不满足严格的数学距离的性质。心理学家阿莫斯·特沃斯基在 1977 年的研究中也指出，人对相似性的判断经常违反对称性和三角不等式：比如人们往往认为“朝鲜像中国”的程度，比“中国像朝鲜”的程度更高。

其他常见的非度量距离

KL 散度：用来衡量两个概率分布之间差异的指标，被广泛用于机器学习中。但它是不对称的，从分布 P 到分布 Q 的 KL 散度，一般不等于从 Q 到 P 的 KL 散度，它也不满足三角不等式，所以它被称为“散度”而不是距离。余弦距离：常用“一减去余弦相似度”来定义，它在文本和向量检索中使用广泛，但并不满足三角不等式。动态时间规整距离：用来比较两段时间序列的相似程度，允许它们在时间轴上有一定的伸缩和错位，常用于语音识别和手势识别，但它也不满足三角不等式。此外，平方欧氏距离也不满足三角不等式。

非度量距离带来的影响

使用非度量距离需要特别注意，因为很多算法和数据结构都隐含地依赖于距离的数学性质。比如在大规模的相似性搜索中，KD 树、球树、VP 树等索引结构，以及很多加速的近邻搜索算法，都利用三角不等式来排除那些不可能是最近邻的候选对象，从而大大减少计算量。如果距离不满足三角不等式，这些方法就可能出错，漏掉真正的最近邻。多维缩放等降维方法在处理非度量距离时，也需要使用专门的变体，即非度量多维缩放，它只要求保持距离的大小顺序，而不要求保持距离的具体数值。

度量学习

在实际的任务中，与其事先固定一个距离，不如根据数据和任务来学习一个合适的距离，这就是度量学习的研究内容。学到的距离可能是度量的，也可能是非度量的，关键在于它能否更好地反映任务所需要的相似性。