Voronoi 图(Voronoi 分解图)是一种直观地表示距离矩阵 (DM) 的方法。
使用 R 创建和绘制它们也很简单——您可以在一行 R 代码中完成这两者。
如果您不熟悉计算几何的这一方面,则两者(VD 和 DM)之间的关系很简单,尽管简要总结可能会有所帮助。
距离矩阵——即显示一个点与其他点之间的距离的 2D 矩阵,是 kNN 计算期间的中间输出(即 k-最近邻,一种机器学习算法,它基于基于它的“k”个最近邻居的加权平均值,距离,其中“k”是某个整数,通常在 3 到 5 之间。)
kNN 在概念上非常简单——训练集中的每个数据点本质上是某个 n 维空间中的“位置”,因此下一步是使用一些距离度量来计算每个点与每个其他点之间的距离(例如、欧几里得、曼哈顿等)。虽然训练步骤(即构造距离矩阵)很简单,但使用它来预测新数据点的值实际上会受到数据检索的阻碍——从几千或几百万中找到最接近的 3 或 4 个点分散在 n 维空间中。
两种数据结构通常用于解决该问题:kd-trees 和 Voroni 分解(又名“Dirichlet tesselation”)。
Voronoi 分解 (VD) 由距离矩阵唯一确定——即,有一个 1:1 的映射;所以它确实是距离矩阵的视觉表示,尽管这又不是他们的目的——他们的主要目的是有效存储用于基于 kNN 的预测的数据。
除此之外,以这种方式表示距离矩阵是否是一个好主意可能主要取决于您的受众。对大多数人来说,VD 和先行距离矩阵之间的关系并不直观。但这并不意味着它不正确——如果没有接受过任何统计培训的人想知道两个总体是否具有相似的概率分布,并且您向他们展示了 QQ 图,他们可能会认为您没有回答他们的问题。因此,对于那些知道自己在看什么的人来说,VD 是 DM 的紧凑、完整和准确的表示。
那你怎么做一个?
Voronoi decomp 是通过从训练集中选择(通常是随机的)点的子集来构建的(这个数字因情况而异,但如果我们有 1,000,000 个点,那么 100 是这个子集的合理数字)。这 100 个数据点是 Voronoi 中心(“VC”)。
Voronoi decomp 背后的基本思想是,不必筛选 1,000,000 个数据点来找到最近的邻居,您只需查看这 100 个,然后一旦找到最近的 VC,您对实际最近邻居的搜索是仅限于该 Voronoi 单元内的点。接下来,对于训练集中的每个数据点,计算它最接近的 VC。最后,对于每个 VC 及其关联点,计算凸包——从概念上讲,只是由该 VC 分配的离 VC 最远的点形成的外边界。这个围绕 Voronoi 中心的凸包形成了一个“Voronoi 单元”。完整的 VD 是将这三个步骤应用于训练集中的每个 VC 的结果。这将为您提供完美的曲面镶嵌(参见下图)。
要计算 R 中的 VD,请使用tripack包。关键功能是“voronoi.mosaic”,您只需将 x 和 y 坐标分别传递给它——原始数据,而不是DM——然后你可以将 voronoi.mosaic 传递给“plot”。
library(tripack)
plot(voronoi.mosaic(runif(100), runif(100), duplicate="remove"))
