如何获得有效的距离度量?

机器算法验证 机器学习 聚类 相似之处 公制
2022-03-13 00:53:08

我有一个问题来设计一个距离度量来获得向量的相似性度量。有人建议我使用点积,在我看来这与余弦相似度度量相同;但是在维基百科(余弦相似度)中,它提到余弦相似度不是适当的距离度量,因为它不具有三角形不等式属性并且违反了重合公理(适当的距离度量应该满足四个条件(距离度量))。

我的问题是:

  1. 什么是正确的距离度量?请列举一些例子。

  2. Dice 系数和 Jaccard 指数是正确的距离度量吗?

  3. 使用点积有什么缺点吗?(点积受欢迎的原因之一是它的评估效率很高)。

非常感谢。一个。

3个回答

首先,在许多应用程序中,您不需要距离度量,但相异性就可以了因此,请确保需要三角不等式。

在数学中,三角不等式是度量定义的一部分,数学中的距离是度量的同义词。但是在数据库文献中,距离通常不需要是度量的。

其次,如果我们不知道您的数据,我们无法为您的数据推荐指标。

第三,余弦与欧几里得距离密切相关。假设所有数据都归一化为单位长度(),那么 因此,如果您的数据被标准化为单位长度,则 是一个度量。因为如上所示,||x||=1=||y||

Euclid2(x,y)=i(xiyi)2=ix2+iy22ixiyi=1+12xy=2(1xy)
1xy
1xy=12Euclid(x,y)

虽然这可能会让您对基于点积的度量过于兴奋,但请记住,这仅在您的所有数据都位于单位圆上这只是欧几里德度量时才成立。如果这是您想要的行为,请规范化您的数据并使用欧几里得距离......余弦距离正是这种规范化。它包括向量长度的归一化项,以确保它们具有单位长度...

如果您的数据是sparse,并且您可以将所有向量长度保存在内存中,那么这可能是计算欧几里得距离的更快方法。如果您的稀疏度为,则点积的预期稀疏度为 ,因此如果您有良好的实现,这可以产生ss21/s

更新:有人向我指出,以这种方式计算欧几里得可能会遭受称为“灾难性抵消”的数值不稳定性。

什么是正确的距离度量?请列举一些例子。

欧几里得距离、列文斯坦距离、曼哈顿距离。正如你所写的,任何距离度量都满足距离的定义,所以有很多。在 Gunnar Carlsson 的一篇关于拓扑数据分析的文章中,他使用(我相信是)原始距离度量来分析论文的特定主题。唯一的限制是距离定义的约束。

Dice 系数和 Jaccard 指数是正确的距离度量吗?

Dice 的系数违反了三角不等式。来自维基百科

最简单的反例是由三个集合 {a}、{b} 和 {a,b} 给出的,前两个之间的距离为 1,第三个与其他每个之间的差为三分之一. 为了满足三角不等式,这三个边中的任何两条之和必须大于或等于其余边。但是,{a} 和 {a,b} 之间的距离加上 {b} 和 {a,b} 之间的距离等于 2/3,因此小于 {a} 和 {b} 之间的距离,即 1。

Jaccard 指数不是距离度量。但是从 1 中减去 Jaccard 指数会产生距离度量

使用点积有什么缺点吗?(点积受欢迎的原因之一是它的评估效率很高)。

没有额外的上下文是不可能全面回答这个问题的。如果您的应用程序需要适当的距离函数,那么您可能会遇到一些麻烦。

指标的选择取决于您的问题。有关余弦相似度以及如何基于它构建距离函数的讨论,请参见此答案。此外,还有一篇关于讨论高维设置中距离函数问题的论文的参考资料。

交叉产品的问题是您需要小心使用它。例如,将数据白化(中心和比例方差为 1)通常是一个好主意,这样特征的不同缩放不会使您的结果产生偏差。