问题标签 [nearest-neighbor]

我一直在尝试使用与 weka 机器学习库一起使用的 Ibk 最近邻算法。

我知道如何对实例进行分类，但我想实现协同过滤功能，因此我需要实际获取最接近感兴趣对象的实际对象列表。

我将如何在 weka 中使用其 java API 实际执行此操作？

给定 3D 中数千个点的集合，我需要获取每个粒子的邻居列表，这些粒子落在某个截止值内（根据欧几里德距离），如果可能的话，从最远的最近排序。

在 CUDA 或 OpenCL 语言中，哪个是最快的 GPU 算法？

我需要发现 Linux 中的所有网络邻居（他们也在运行 Linux），我需要获取他们的 IP 地址（第 3 层）。任何想法如何做到这一点？

顺便说一句，我需要这样做，而C不是shell

提前谢谢了！

从排序的地图中，我想检索n个条目的子集，从指定值 v之前的m个条目开始。例如，对于键集k = {0.2, 0.3, 0.4, 0.6, 0.8, 0.9, 1.0}，n = 5, m =2, v =0.5 的查询将返回 {0.3, 0.4, 0.6, 0.8 , 0.9}。Java 中是否有数据结构的实现支持这样的查询，而不必遍历整个（大）集合？

我需要这个做什么？插值。我想根据地图中的值在v处进行插值。但是，我有很多v。它们已排序，并且它们之间的间距比k中的间距小得多。因此，我从地图中获取一系列条目，对它们进行一些昂贵的准备计算（例如计算多项式的系数），然后可以快速插入该范围内的另一个值（通过使用该值评估多项式）。

但是为什么我需要m之前的条目v？k中的值通常是等间距的，为了避免插值区间末端出现高震荡的龙格现象，我简单地把它们剪掉了，这意味着在插值的实际有效区间之前我需要一些节点。

那有意义吗？你有什么建议？

（如果像 java.util.TreeMap.ceilingEntry() 这样的方法会返回一个迭代器，那会很有趣，我可以用它后退两次。）

在一个立方体中，我在 R^3 中有一个大的收集点。我想为每个点找到 k 个最近的邻居。通常我会考虑使用类似 kd 树的东西，但在这种情况下，我有周期性的边界条件。据我了解，kd 树的工作原理是通过将空间切割成少一维的超平面来划分空间，即在 3D 中，我们将通过绘制 2D 平面来分割空间。对于任何给定的点，它要么在平面上，要么在其上方，要么在其下方。但是，当您使用周期性边界条件分割空间时，可以认为一个点位于任一侧！

在 R^3 中查找和维护具有周期性边界条件的最近邻列表的最有效方法是什么？

近似值是不够的，并且一次只能移动一个点（想想蒙特卡罗而不是 N 体模拟）。

我想做一些植绒模拟，如此处所述。

为此，我需要搜索每个 2D 点的最近邻居。但是，我不能使用像 kd 树这样的静态数据结构，因为点总是在移动......

什么是能够实现这一目标的好（简单）数据结构/库？我正在使用 C++ ...

我正在为外汇市场设计一个自动交易软件。在 MYSQL 数据库中，我每隔五分钟就有多年的市场数据。除了价格和时间，我有 5 个不同的数据指标。

Time是主键，M1通过M5是不同的指标（例如标准差或移动平均线的斜率）。

M1给定, M2, M3, , 和 M5的输入，M4我如何有效地定位最近的 5,000 个邻居？请注意，每个指标都是浮点数并且具有不同的分布/范围。

我正在为外汇市场设计一个自动交易软件。在 MYSQL 数据库中，我每隔五分钟就有多年的市场数据。除了价格和时间，我有 4 个不同的数据指标。

Time是主键，M1通过M4是不同的指标（例如标准差或移动平均线的斜率）。

这是一个真实的例子（摘录：）

给定输入M1, M2, M3, 并且M4我想（快速准确地）找到 5,000 个最接近的匹配项。

样本输入：

我认为这些指标中的每一个都可以被视为一个“维度”，并且我可以做一个nearest neighbor search来定位这个多维空间中最近的数据点。

似乎最简单的方法是遍历每个数据点并测量到我的输入点的多维距离；但速度至关重要！

我读到了一种叫做K-D Trees用于此目的的东西。谁能解释一下或向我提供一些解释如何在 MYSQL 中实现这一点的材料？

值得一提的是，我可以对表格进行预处理，但输入是实时接收的。

目前我只是围绕每个维度上的数据独立地做了一个粗略的聚类：

重要的是要了解我对排名感兴趣的距离，而不是价值。

编辑：我更接近于理解如何做到这一点（我认为）：我需要预处理每个指标的每一行并为其分配一个percentile代表其在其范围内的位置（百分比）的值。

例如，对于任何给定的值M1：

如果我计算输入的百分位数并将其用于最近邻搜索而不是实际值，我将有效地缩放各种指标，以便它们可以用作维度。

不过，我仍然不知道如何进行实际搜索。这甚至可以在 MySQL 中有效地完成吗？

我已经成功实现了一种使用 Fortune 方法生成二维 Voronoi 图的方法。但现在我试图将它用于最近邻查询一个点（这不是用于生成图表的原始点之一）。我一直看到人们说它可以在 O(lg n) 时间内完成（我相信他们），但我找不到关于它实际上是如何完成的描述。

我对二分搜索很熟悉，但我想不出一个好的标准来保证这个上限。我还想也许它可能与将点插入图表和更新周围的单元格有关，但想不出（或找到）一个好的方法来做到这一点。

任何人都可以提示我，或者指出一个描述更全面的地方吗？

以下伪代码来自《算法设计手册》在线预览版的第一章（本 PDF的第 7 页）。

这个例子是一个有缺陷的算法，但我仍然很想理解它：

[...] 一个不同的想法可能是重复连接最近的一对端点，它们的连接不会产生问题，例如循环的提前终止。每个顶点都从​​它自己的单个顶点链开始。将所有内容合并在一起后，我们将最终得到一个包含其中所有点的链。连接最后两个端点给了我们一个循环。在执行此最近对启发式的任何步骤中，我们将有一组可用于合并的单个顶点和顶点不相交的链。在伪代码中：

请注意smandtm应该是smand tm。

首先，我不明白“来自不同的顶点链”是什么意思。其次，i在外循环中用作计数器，但i它本身从未在任何地方实际使用过！比我聪明的人可以解释一下这里到底发生了什么吗？