维度的诅咒——余弦相似度是否更好,如果是,为什么?

机器算法验证 聚类 高维 余弦相似度
2022-02-15 14:25:19

在处理高维数据时,使用欧几里得距离比较数据点几乎没有用——这是维度的诅咒。

但是,我读过使用不同的距离度量,例如余弦相似度,在高维数据中表现更好。

为什么是这样?有一些数学证明/直觉吗?

我的直觉是,这是因为余弦度量只关注数据点之间的角度,并且任何两个数据点与原点之间的平面都是 3 维的。但是,如果两个数据点的角度非常小,但彼此之间“相距甚远”(在绝对差异意义上)——那么它们如何仍被视为接近/相似呢?

3个回答

与各种未经证实的说法相反,余弦不能明显更好

很容易看出余弦在归一化数据上与欧几里得基本相同。归一化带走了一个自由度。因此,1000 维空间上的余弦与 999 维空间上的欧几里得一样“被诅咒”。

通常不同的是您将使用一个与另一个的数据。欧几里得通常用于密集的连续变量。每个维度都很重要,20 维空间可能具有挑战性。余弦主要用于非常稀疏的离散域,例如文本。在这里,大多数维度都是 0,根本不重要。一个 100.000 维的向量空间可能只有大约 50 个非零维来进行距离计算;其中许多将具有较低的权重(停用词)。因此,余弦的典型用例没有被诅咒,即使它理论上是一个非常高维的空间。

有一个术语:内在维度与表示维度。

但是,我读过使用不同的距离度量,例如余弦相似度,在高维数据中表现更好。

很可能取决于上下文。

余弦距离并非不受维数诅咒的影响——在高维中,两个随机挑选的向量将几乎以高概率正交,请参阅这些注释中的 0.2 有趣的事实。

余弦相似度是相关性,对于具有相似角度的对象,例如从原点 (0,0,0,0,....) 超过特征值,相关性更大。所以相关性是一个相似性指标。与原点具有相同距离和角度的物体之间的欧几里得距离最低。因此,具有相同角度(corr)的两个对象可以彼此相距很远(欧几里得)。

我不会说欧几里得距离对任何事情都没有用。相关性将识别具有相似特征值但在对象之间具有相加或相乘平移的对象。例如,两个对象xi=(1,2,3,4)xj=(1,4,6,8)它们彼此相距为 2 的乘法常数将具有完美的相关性(统一性)。还有两个对象xi=(1,2,3,4)xj=(1.25,2.25,3.25,4.25)它们是相距 0.25 的加法常数,将具有完美的相关性(统一性)。然而,欧几里得距离,d(xi,xj)>0-- 将大于零。

您正在寻找的问题称为“重叠问题”,在上述两个完美相关示例中,对象可以完全相关但距离不同。

在层次聚类分析中,如果您想要聚集具有几乎相同级别的特征值的对象(即几乎相同的对象),您将使用欧几里德距离。但是,如果您想将具有相似模式的对象聚集在一起,这些模式可能会因恒定的加法或乘法平移而变化,那么您将使用相关性,或 1 减相关性,这使得相关性看起来像一个范围为 [0,2] 的距离。

例如,在生物学中,您希望最好使用相关性来识别可能被共同调节或关联(相关)的基因,其表达模式在对象上相互关联(“共同变化”-> 协方差)。然而,在这种情况下,使用欧几里得距离只能识别具有相同表达水平的基因,这在试图寻找共同调控基因时意义不大。欧几里得距离最适合寻找具有低或高特征值的相似对象。

仅供参考 - 维度诅咒通常是造成“小样本问题”的问题(p>>n),当与对象的数量相比,特征太多时。它与距离度量没有任何关系,因为您始终可以将均值归零标准化、归一化、使用百分位数或模糊化特征值来摆脱规模问题。