将相似度矩阵转换为(欧几里得)距离矩阵

机器算法验证 随机森林 距离 相似之处 欧几里得
2022-02-05 07:35:58

在随机森林算法中,Breiman(作者)构造相似度矩阵如下:

  1. 将所有学习示例发送到森林中的每棵树下

  2. 如果两个示例落在同一叶中,则相似矩阵中的对应元素增加 1

  3. 用树的数量对矩阵进行归一化

他说:

案例 n 和 k 之间的接近度形成矩阵 {prox(n,k)}。根据他们的定义,很容易证明这个矩阵是对称的、正定的,并且以 1 为界,对角线元素等于 1。因此,值 1-prox(n,k) 是欧几里得距离的平方空间维度不大于案例数。来源

在他的实现中,他使用sqrt(1-prox)将其转换为距离矩阵,其中prox是一个相似度矩阵。我想这与上面引用的“欧几里得空间中的平方距离”有关。

有人能解释一下为什么 1-prox 是欧几里得空间中的平方距离,以及为什么他使用平方根来获得距离矩阵吗?

1个回答

在此处输入图像描述

根据余弦定理,在欧几里得空间中,两点(向量)1 和 2 之间的(欧几里得)平方距离为平方长度分别是点 1 和 2 的平方坐标之和(它们是毕达哥拉斯斜边)。数量称为向量 1 和 2 的标量积(= 点积,= 内积)。d122=h12+h222h1h2cosϕh12h22h1h2cosϕ

标量积也称为 1 和 2 之间的角度类型相似度,在欧几里德空间中,它是几何上最有效的相似度度量,因为它很容易转换为欧几里德距离,反之亦然(另见此处)。

协方差系数和皮尔逊相关标量积。如果您将多元数据居中(使原点位于点云的中心),则的归一化是向量的方差(不是上图中的变量 X 和 Y),而是 Pearson因此,标量积是协方差。[附注。如果您现在正在考虑变量之间的协方差/相关性,而不是数据点,您可能会问是否可以将变量绘制为上图中的向量。是的,可能的,它被称为“主题空间”h2cosϕrσ1σ2r12” 表示方式。不管在这个实例中被视为“向量”——数据点或数据特征,余弦定理仍然正确。]

每当我们有一个对角线上为 1 的相似度矩阵- 也就是说,所有都设置为 1,并且我们相信/期望相似度欧几里得标量积,我们可以将其转换为平方欧几里得距离,如果我们需要它(例如,用于进行需要距离和理想欧几里得距离的聚类或 MDS)。因为,根据上述余弦定理公式,是欧几里得的平方。如果您的分析不需要,您当然可以放弃因子hsd2=2(1s)d2d2=1s. 作为一个经常遇到的例子,这些公式用于将 Pearson转换为欧几里得距离。(另请参阅这个和那里的整个线程,质疑一些将转换为距离的公式。)rr

就在上面我说如果“我们相信/期望……”。如果矩阵没有负特征值,您可以检查并确保相似性矩阵(手头上的一个特定矩阵)在几何上是“OK”标量积矩阵。但是,如果它具有这些,则意味着不是真正的标量积,因为中存在某种程度的几何不收敛,“隐藏”在矩阵后面。在将其转换为欧几里德距离之前,有一些方法可以尝试“修复”这样的矩阵。sshd