论文标题
超越KNN：通过最佳运输的自适应，稀疏的邻里图
Beyond kNN: Adaptive, Sparse Neighborhood Graphs via Optimal Transport
论文作者
论文摘要
最近的邻居图被广泛用于捕获数据集的几何形状或拓扑。构建此类图的最常见策略之一是基于为每个点选择固定数字K（KNN）。但是，当抽样密度或噪声水平在数据集各不相同时，KNN启发式可能会变得不合适。试图解决此问题的策略通常会引入需要调整的其他参数。我们提出了一种简单的方法，以基于四次正规化的最佳传输来构建单个参数的自适应邻域图。我们的数值实验表明，以这种方式构建的图在无监督和半监督的学习应用中表现出色。
Nearest neighbour graphs are widely used to capture the geometry or topology of a dataset. One of the most common strategies to construct such a graph is based on selecting a fixed number k of nearest neighbours (kNN) for each point. However, the kNN heuristic may become inappropriate when sampling density or noise level varies across datasets. Strategies that try to get around this typically introduce additional parameters that need to be tuned. We propose a simple approach to construct an adaptive neighbourhood graph from a single parameter, based on quadratically regularised optimal transport. Our numerical experiments show that graphs constructed in this manner perform favourably in unsupervised and semi-supervised learning applications.
