标签: nearest-neighbor

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

[Time|Price|M1|M2|M3|M4] 
x ~400,0000

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

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

+------------+--------+-----------+--------+-----------+-----------+
|  Time      | Price  |     M1    |   M2   |    M3     |     M4    |
+------------+--------+-----------+--------+-----------+-----------+
| 1105410300 | 1.3101 |   12.9132 | 0.4647 |   29.6703 |        50 |
| 1105410600 | 1.3103 |    14.056 | 0.5305 | 29.230801 |        50 |
| 1105410900 | 1.3105 |   15.3613 | 0.5722 |   26.8132 |        25 |
| 1105411200 | 1.3106 | 16.627501 | 0.4433 | …

我已经实现了 n 个点的四叉树结构以及返回给定矩形内的点数组的方法。我似乎无法找到一种算法来有效地找到最接近另一个给定点的点。我错过了一些明显的东西吗？我认为递归解决方案是正确的方法吗？

我正在使用 Objective C，但伪代码就可以了。此外，我实际上存储了经纬度数据，并且点之间的距离沿着一个大圆。

编辑： 这是我的树插入和细分代码

- (BOOL)insert:(id<PASQuadTreeDataPoint>)dataPoint {

    BOOL pointAdded = false;

    // If the point lies within the region
    if(CGRectContainsPoint(self.region, dataPoint.point)) {

        // If there are less than 4 points then add this point
        if(self.dataPoints.count < kMaxPointsPerNode) {
            [self.dataPoints addObject:dataPoint];
            pointAdded = true;
        }
        else {

            // Subdivide into 4 quadrants if not already subdivided
            if(northEast == nil) [self subdivide];

            // Attempt to add the point to one of the 4 subdivided quadrants
            if([northEast insert:dataPoint]) return …

我有一个dict需要整数键的：

a = {}
a[1] = 100
a[55] = 101
a[127] = 102

我希望在询问时能够选择最近的邻居：

a[20] # should return a[1] = 100
a[58] # should return a[55] = 101
a[167] # should return a[127] = 102

有没有一种Python式的方法可以做到这一点？（我想这可以通过循环所有字典来完成，但这可能不是最优雅的解决方案？）

双索引（也是整数）同样的问题：

 b[90, 1] = 100, b[90, 55] = 101, b[90, 127] = 102
 b[70, 1] = 40, b[70, 45] = 41, b[70, 107] = 42

我希望能够得到 b[73, 40] = b[70, 45] = 41，即二维平面中的最近邻。

我正在使用 Windows 7 8gb RAM。

这是我用来对 52MB 训练数据集中的自由文本列进行矢量化的矢量化器

vec = CountVectorizer(analyzer='word',stop_words='english',decode_error='ignore',binary=True)

我想用这个数据集计算 18MB 测试集的 5 个最近邻。

nbrs = NearestNeighbors(n_neighbors=5).fit(vec.transform(data['clean_sum']))
vectors = vec.transform(data_test['clean_sum'])
distances,indices = nbrs.kneighbors(vectors)

这是堆栈跟踪 -

Traceback (most recent call last):
  File "cr_nearness.py", line 224, in <module>
    distances,indices = nbrs.kneighbors(vectors)
  File "C:\Anaconda2\lib\site-packages\sklearn\neighbors\base.py", line 371,
kneighbors
    n_jobs=n_jobs, squared=True)
  File "C:\Anaconda2\lib\site-packages\sklearn\metrics\pairwise.py", line 12
in pairwise_distances
    return _parallel_pairwise(X, Y, func, n_jobs, **kwds)
  File "C:\Anaconda2\lib\site-packages\sklearn\metrics\pairwise.py", line 10
in _parallel_pairwise
    return func(X, Y, **kwds)
  File "C:\Anaconda2\lib\site-packages\sklearn\metrics\pairwise.py", line 23
n euclidean_distances
    distances = safe_sparse_dot(X, Y.T, …

我正在开展一项研究，试图根据特定个人的地址将颗粒物暴露情况分配给他们。我有两个带有经度和纬度坐标的数据集。一个 if 用于个人，一个 if 用于下午暴露块。我想根据最接近的块为每个主题分配一个下午曝光块。

library(sp)
library(raster)
library(tidyverse)

#subject level data
subjectID<-c("A1","A2","A3","A4")

subjects<-data.frame(tribble(
~lon,~lat,
-70.9821391,    42.3769511,
-61.8668537,    45.5267133,
-70.9344039,    41.6220337,
-70.7283830,    41.7123494
))

row.names(subjects)<-subjectID

#PM Block Locations 
blockID<-c("B1","B2","B3","B4","B5")

blocks<-data.frame(tribble(
~lon,~lat,
-70.9824591,    42.3769451,
-61.8664537,    45.5267453,
-70.9344539,    41.6220457,
-70.7284530,    41.7123454,
-70.7284430,    41.7193454
))

row.names(blocks)<-blockID

#Creating distance matrix
dis_matrix<-pointDistance(blocks,subjects,lonlat = TRUE)

###The above code doesnt preserve the row names. Is there a way to to do 
that?

###I'm unsure about the below code
colnames(dis_matrix)<-row.names(subjects)
row.names(dis_matrix)<-row.names(blocks)

dis_data<-data.frame(dis_matrix)

###Finding nearst neighbor and coercing to usable …

我想对周期框中超过 10k 的点进行最近邻搜索，并返回这些点的距离及其索引。

到目前为止，我尝试sklearn.neighbors.KDTree(positions).query_radius(positions, r=maximum_distance,return_distance=True)返回最大范围内的最近邻居距离。半径，但它不适用于周期性边界条件 (PBC)。我探索的另一种方法是scipy.spatial.cKDTree(positions, boxsize=box_size).query_pairs(r=maximum_distance)与 PBC 一起使用，但不返回对之间的距离。

是否有可能 像现在sklearn.neighbors.KDTree这样扩展处理 PBC 的能力scipy.spatial.cKDTree？

或者

是否可以scipy.spatial.cKDTree通过返回线对距离的能力进行扩展？

fasttext 官方网站 (fasttext.cc) 上的示例（与单词表示相关）表明，可以计算使用 cbow（或skip-gram 模型）导出的向量（简而言之，在无监督学习模型上）的最近邻。据称，这可以使用get_nearest_neighbors模型 ( model.get_nearest_neighbors) 上的函数来完成。然而，当我尝试执行该操作时，Python (3.7.) 向我显示了一条消息，即对于无监督学习模型，fasttext 中不存在此函数，事实上，当我查看 fasttext 帮助时，我没有看到此函数。唯一存在的类似函数是模型上的谓词（model.predict（其中指定 k）），但这只能在监督学习模型上完成。

谁能向我解释发生了什么事，并帮助我解决这个问题？有什么方法可以计算 fasttext 中无监督学习模型的最近邻居吗？:-)

我有40万个客户数据，每个客户有40个属性。DataFame 看起来像：

          A1 A2 ... A40
0         xx xx ... xx
1         xx xx ... xx
2         xx xx ... xx
...       ...
399,999   xx xx ... xx

我首先通过 sklearn 的 StandardScaler 对这些数据进行标准化。现在我们得到处理后的数据X_data。

所以现在我们有 400,000 个客户（点/向量），每个客户有 40 个维度。

然后我使用 NearestNeighbors 来计算前 5 个最近点。到目前为止，一切都很好。

但结果有一点问题。

结果包含点本身，并且它出现在随机位置，并不总是第一个。

结果如下：

(
 [[0,0.04,0.06,0.09,0.1,0.12],        ---case a
  [0,0.01,0.05,0.07,0.08,0.09],       ---case b
  [0,0,0,0.04,0.05,0.06,0.08],        ---case c
  ...
  [0,0,0,0,0,0],                      ---case d
  [0,0.06,0.07,0.09,0.1,0.12],        ---case e
  [0,0.01,0.03,0.05,0.07,0.,8]],      ---case f

 [[0,2143,14134,54253,242425,3423],   ---case a
  [1,43242,132,34324,31234,44355],    ---case b
  [343245,32113,2,32435,23451,54131]  ---case c
  ... …

我有两个data.table。它们包含某些点的 x 和 y 坐标。它们如下：-

set.seed(123)

a <- data.table(x = runif(10), y = runif(10))

a
            x           y
 1: 0.9036218 0.005233401
 2: 0.1914482 0.219560561
 3: 0.6089018 0.275966545
 4: 0.2307832 0.665939467
 5: 0.5959250 0.221657568
 6: 0.2343375 0.228499024
 7: 0.2620843 0.846292513
 8: 0.8499895 0.888969644
 9: 0.5707878 0.305334950
10: 0.4771339 0.714933915

b <- data.table(x = runif(30), y = runif(30))

b

             x          y
  1: 0.86444548 0.26182116
  2: 0.54160133 0.14384453
  3: 0.84231617 0.78842707
  4: 0.26452802 0.56285334
  5: 0.31283576 0.63412792
  6: 0.85437689 0.91124597
  7: 0.71066455 …

我有很多用户，每个用户都有一个关联的向量。我想计算每个用户之间的余弦相似度。从尺寸来看，这是令人望而却步的。看起来 LSH 是一个很好的近似步骤，据我所知，它将创建存储桶，在这种情况下，用户被映射到同一个存储桶，其中它们很可能是相似的。在 Pyspark 中，示例如下：

from pyspark.ml.feature import BucketedRandomProjectionLSH
from pyspark.ml.linalg import Vectors
from pyspark.sql.functions import col

dataA = [(0, Vectors.dense([1.0, 1.0]),),
         (1, Vectors.dense([1.0, -1.0]),),
         (4, Vectors.dense([1.0, -1.0]),),
         (5, Vectors.dense([1.1, -1.0]),),
         (2, Vectors.dense([-1.0, -1.0]),),
         (3, Vectors.dense([-1.0, 1.0]),)]
dfA = ss.createDataFrame(dataA, ["id", "features"])

brp = BucketedRandomProjectionLSH(inputCol="features", outputCol="hashes", bucketLength=1.0, numHashTables=3)
model = brp.fit(dfA)
model.transform(dfA).show(truncate=False)


+---+-----------+-----------------------+
|id |features   |hashes                 |
+---+-----------+-----------------------+
|0  |[1.0,1.0]  |[[-1.0], [0.0], [-1.0]]|
|1  |[1.0,-1.0] |[[-2.0], [-2.0], [1.0]]|
|4  |[1.0,-1.0] |[[-2.0], [-2.0], [1.0]]|
|5  |[1.1,-1.0] |[[-2.0], [-2.0], [1.0]]|
|2  |[-1.0,-1.0]|[[0.0], …