怎样能才能快速的找到KNN - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>DataSciences - 数据科学

怎样能才能快速的找到KNN

怎样能才能快速的找到KNN# DataSciences - 数据科学

E*e2015-09-05 07:09

1 楼

一个sampling的code，自己写的KNN的R code，因为是continuous 和norminal 混合，
连续变量用euclidean 距离， norminal变量需要另外算distance。基本问题是这样：
总共是500个记录， 60个norminal变量。需要找到每个记录的KNN。每条距离搜寻需
要5seconds，所以这个KNN需要20分钟。因为要做bootstrap，所以一个main
function，运行100需要两天时间。现在想加快这个KNN搜寻。问题是就在norminal
距离的KNN计算，需要5秒时间。
我看了下问题。 60个norminal变量的distance 矩阵单独完成，很快。
现在的主要任务就是算每条记录的KNN，用的是两个loop，需要从所有变量的distance
矩阵里，一对一的需要找到每个记录里每个变量所对应的具体距离，这样就很慢了。我
是通过每个distance矩阵的的row 和col names同每个记录里的变量值对应才找到需要
的distance，然后sum所有每个记录里60个变量的distance值，最后找到每个记录的KNN
。
现在问题就简化成，假设现在有60个变量各自的distanc矩阵，怎样快速的找到每个记
录的KNN。用double loop很慢。能用是么sql表查询码？
谢谢。

c*h2015-09-05 07:09

2 楼

Kd tree?

G*n2015-09-05 07:09

3 楼

sql也是需要一个个loop啊，而且连sql估计更慢。knn算法就是很慢，有很多改进版的
论文，也没有实质提高多少。试试用spark跑？

样：
norminal
distance

【在 E**********e 的大作中提到】

: 一个sampling的code，自己写的KNN的R code，因为是continuous 和norminal 混合，
: 连续变量用euclidean 距离， norminal变量需要另外算distance。基本问题是这样：
: 总共是500个记录， 60个norminal变量。需要找到每个记录的KNN。每条距离搜寻需
: 要5seconds，所以这个KNN需要20分钟。因为要做bootstrap，所以一个main
: function，运行100需要两天时间。现在想加快这个KNN搜寻。问题是就在norminal
: 距离的KNN计算，需要5秒时间。
: 我看了下问题。 60个norminal变量的distance 矩阵单独完成，很快。
: 现在的主要任务就是算每条记录的KNN，用的是两个loop，需要从所有变量的distance
: 矩阵里，一对一的需要找到每个记录里每个变量所对应的具体距离，这样就很慢了。我
: 是通过每个distance矩阵的的row 和col names同每个记录里的变量值对应才找到需要

l*m2015-09-05 07:09

4 楼

用轮子吧

样：
norminal
distance

【在 E**********e 的大作中提到】

r*y2015-09-05 07:09

5 楼

小的愚钝 norminal是啥

E*e2015-09-05 07:09

6 楼

Norminal 就是名义变量，可以包括ordinal 和 nonordinal变量。一般可以code成 1
,2,3，...

【在 r*******y 的大作中提到】

: 小的愚钝 norminal是啥

E*e2015-09-05 07:09

7 楼

轮子是是么？谢谢。

【在 l*******m 的大作中提到】

: 用轮子吧
:
: 样：
: norminal
: distance

w*g2015-09-05 07:09

8 楼

https://github.com/erikbern/ann-benchmarks
其中的kgraph和LSHKIT是我写的。你这个数据量非常小，速度慢不是算法问题，
而是因为用R手写了代码。你随便找个用C/C++实现的R的轮子就能解决问题了。
可惜我不会R帮不了你。

样：
norminal
distance

【在 E**********e 的大作中提到】

b*l2015-09-05 07:09

9 楼

膜拜大牛。。。原来您毕业论文就是搞这个的。。。太厉害了。。。

【在 w***g 的大作中提到】

: https://github.com/erikbern/ann-benchmarks
: 其中的kgraph和LSHKIT是我写的。你这个数据量非常小，速度慢不是算法问题，
: 而是因为用R手写了代码。你随便找个用C/C++实现的R的轮子就能解决问题了。
: 可惜我不会R帮不了你。
:
: 样：
: norminal
: distance