Density estimation from unweighted k-nearest neighbor graphs: a roadmap
Density estimation from unweighted k-nearest neighbor graphs: a roadmap
复制标题
根据未加权 k 最近邻图进行密度估计：路线图
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Morteza Alamgir
中科院分区：
文献类型：
--
作者：
U. V. Luxburg;Morteza Alamgir
考虑一个未加权的k-最近邻图，图中的n个点都是i.i.d.采样的。从未知的密度p中分离出来。我们证明了如何可以估计密度p只是从未加权的邻接矩阵的图形，而不知道点本身或任何距离或相似性得分。关键的见解是，局部差异的链接数可以用来估计局部函数的梯度p，并集成此功能沿着最短路径导致估计的潜在密度。
Consider an unweighted k-nearest neighbor graph on n points that have been sampled i.i.d. from some unknown density p on ℝd. We prove how one can estimate the density p just from the unweighted adjacency matrix of the graph, without knowing the points themselves or any distance or similarity scores. The key insights are that local differences in link numbers can be used to estimate a local function of the gradient of p, and that integrating this function along shortest paths leads to an estimate of the underlying density.