E**********e
发帖数: 1736 | 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值，最后找到每个... 阅读全帖 |
|
d******e
发帖数: 7844 | 2 【 以下文字转载自 CS 讨论区 】
发信人: drburnie (专门爆料), 信区: CS
标 题: 问两个个KNN的问题
发信站: BBS 未名空间站 (Sat Jan 9 18:37:31 2010, 美东)
使用KNN分类器做两类问题的分类。
实验步骤是分成80%作Training,20%做Testing。
然后再Training Set里用Leave one out cross validation来确定K.
参与cross validation的选取是K=1,3,5,,7... ...
然后选取cross validation error最小的K，如果同时有多个K达到最小的erorr，那么
这是选择最小的K还是最大的K？
另一个问题，有人说KNN的K不应该从1开始选，而是应该指定一个minimum，从这个
minimum开始。标准的KNN分类器有这个说法么？ |
|
d******e
发帖数: 7844 | 3 使用KNN分类器做两类问题的分类。
实验步骤是分成80%作Training,20%做Testing。
然后再Training Set里用Leave one out cross validation来确定K.
参与cross validation的选取是K=1,3,5,,7... ...
然后选取cross validation error最小的K，如果同时有多个K达到最小的erorr，那么
这是选择最小的K还是最大的K？
另一个问题，有人说KNN的K不应该从1开始选，而是应该指定一个minimum，从这个
minimum开始。标准的KNN分类器有这个说法么？ |
|
d******e
发帖数: 7844 | 4 当样本数量很大的时候，这么做没有问题，当样本少的时候就有麻烦了。尤其是高维数
据。
其实普通的KNN overfitting就是很严重，而我也只是拿KNN来做baseline。我导师非要
我弄一个overfitting最小的训练策略然后用这个数据来做baseline。 |
|
A*****n
发帖数: 243 | 5 check knn in e1071 package |
|
A*****n
发帖数: 243 | 6 install.packages("e1071")
help(knn) |
|
B****n
发帖数: 11290 | 7 你可以random 一萬次選擇training set and test set 然後看看選擇到不同的k值的頻
率 選個頻率最大的
還有 knn常常收斂到local解 而不是global解 所以最好用不同的initial values測試
一下讓分類的錯誤率最低 |
|
|
d******e
发帖数: 7844 | 9 对于KNN这种分类器，n-fold cv会出现一个问题，sample density是不一样的。
比如5-fold cv,每次只有80%的样本参与训练,得到的最优参数K对于所有样本都参与训
练的情况会有所不同。 |
|
g********r
发帖数: 8017 | 10 好奇你在多少维上做KNN? 感觉超过三维,就算几千个点也稀疏.除非边界很简单,否则没
啥搞头.假定边界简单,那确实k大点
好. |
|
G***n
发帖数: 877 | 11 sql也是需要一个个loop啊，而且连sql估计更慢。knn算法就是很慢，有很多改进版的
论文，也没有实质提高多少。试试用spark跑？
样：
norminal
distance |
|
r********3
发帖数: 2998 | 12 不过，这篇paper的要说明的问题，和处理large scale data是两回事。
前面有人跟帖说看好KNN的，认为KNN是真正解决large scale data的。KNN跟这篇paper
在对待大数据集上有本质的区别。 这个本质区别在于，KNN可以和数据库的存储索引和
查询优化这些结合起来。而这些技术才是解决真正意义上大规模数据集训练的渠道，而
不是一些局部小trick，五十步和百步的区别。
Yahoo Research Lab的director说过。实际大数据集的公司里面，都只能用linear或者
低于linear的算法。 |
|
p*********g
发帖数: 226 | 13 抛开算法复杂度不谈，在高维条件下，KNN 的 generalization performance 我不知道
会不会比 SVM 好。example 的数量 n 需要随维度 p 而上升，不知道 knn 中 n 对 p
的 dependence 是否好过 SVM。
而且在 testing 的时候，我有一个 weight vector，做一下内积，无论如何总比 knn
要快吧，不论 knn 做何indexing。
paper |
|
a***y
发帖数: 852 | 14 另外，从实用技术考虑来讲
如果kmeans不知道如何指定K，可以用Hierarchical clustering。复杂度高但是一次能
得到整个hierarchy。可以从中选择合适的cluster粒度。X-means指定K的方法没有用过
，不过好像比较流行。我需要去看一看。。。
KNN最大的瓶颈是O(n) complexity。但是KNN的solution space其实是对空间的voronoi
划分。random forest本质上也是对空间的划分。应该是取代KNN最理想的直接选择。 |
|
a***y
发帖数: 852 | 15 另外，从实用技术考虑来讲
如果kmeans不知道如何指定K，可以用Hierarchical clustering。复杂度高但是一次能
得到整个hierarchy。可以从中选择合适的cluster粒度。X-means指定K的方法没有用过
，不过好像比较流行。我需要去看一看。。。
KNN最大的瓶颈是O(n) complexity。但是KNN的solution space其实是对空间的voronoi
划分。random forest本质上也是对空间的划分。应该是取代KNN最理想的直接选择。 |
|
|
|
L****8
发帖数: 3938 | 18 给定 KNN-graph后 怎么找
在KNN-graph随机找一个点A 然后在A的KNN内找最近的 比如B 然后循环 ？ |
|
|
|
b******x
发帖数: 826 | 21
-NN
KNN means "K-nearest-neighbor"吗？在数据量趋于无穷的时候，KNN无敌
哈哈 |
|
d******e
发帖数: 7844 | 22 p增长，knn是完蛋最快的，无论是regression还是classification
p
knn |
|
f*****x
发帖数: 2748 | 23 当p一大时，普通的距离函数就不可靠了，
几乎任何两点之间的距离都差不多，这时kNN得到的结果
已经很不可靠了。
p
knn |
|
l*******m
发帖数: 1096 | 24 DTW was proposed in 1960s for comparing speech signals. DTW defines a
distance between two time serieses. DTW has to be applied to sequences with
time correlation! Also, sequences with different lengths are fine for DTW.
KNN and SVM are all based on distance. As long as you have distance between
any two sequences, you should be able to use KNN and SVM.
Don't think machine learning as complicated math problems, just be intuitive
. Theoretical parts are only useful for academia and smart practicer... 阅读全帖 |
|
l*******m
发帖数: 1096 | 25 没戏。sklearn knn 是要把data装进ram里的。没法用 streaming. 话说sklearn knn
都是用cython写的，比java还快。而且复杂度是nlogn. brute force 是n^2, 肯定没戏
数据多少维？如果大， 考虑上locality sensitive hashing. 这个容易mapreduce
find
python
force |
|
|
a****k
发帖数: 117 | 27 Search 'Knn hadoop'. You will find that there are methods parallel knn
approximated and implemented in hadoop.
Nowadays, many people are researching on how to modify traditional popular
ML algorithms so that they can be computed in parallel for big datasets |
|
e*******n
发帖数: 872 | 28 说在点子上了，不同的数据分布在不同的DataNode上，但是互相之间有依赖，Map
Reduce函数都不知该咋写了。
最近搞了个基于流行学习的算法，每个数据点要有它的KNN才能算出结果，可是KNN可能
在别的Node上，求问大牛如何解决这个并行化的问题。 |
|
s**********e
发帖数: 33562 | 29 你这是矩阵分析的东西，还是广义范围的线性代数而已。
要举反例，最简单就是非线性分类器了，比方说kNN。 |
|
|
|
w********2
发帖数: 632 | 32 knn是二分法的扩展，用距离来比较，优化。好像是把数据换成拓扑学的投影，还是有
用的。 |
|
|
发帖数: 1 | 34 现在的一些个ML方法，什么random forest，knn之流，其实早期根本算不上AI，只不过
现在大锅烩拉进来，其实狗屁学习的概念都没有，就一个parameter fitting。核心用
的优化方法。统计做了个壳。操，垃圾。
真正根红苗正的AI是RL以及机器人方向，从神经，计算机，控制几个方向发展来的。核
心是怎么样才能使机器有自主能力，自主学习的能力。而不是curve fitting的能力。
alpha 狗这种才算是真AI，图像识别只能算是把眼睛练了练 |
|
s**********l
发帖数: 8966 | 35 你是说只有unsupervised才算ml么？
那kmeans也算吧
：现在的一些个ML方法，什么random forest，knn之流，其实早期根本算不上AI，只不
过现在大锅烩拉进来，其实狗屁学习的概念都没有，就一个parameter fitting。核心用
：的优化方法。统计做了个壳。操，垃圾。 |
|
发帖数: 1 | 36 pls是unsupervise，pca是supervise。transform可以做，有时候是data message。cnn
有些package内含pls knn之类的，对用户是透明的。 |
|
z****g
发帖数: 2128 | 37 其实最简单的先换个灯泡，只要你原来的不是HID的，都挺便宜
我自己的HID都老化了，开的时候是蓝白色的，几分钟后，开始变成普通黄色的。
acurazine的人说是老化了，还是它原来设计就是这样的？黄色的HID？knn的 |
|
s******g
发帖数: 3841 | 38 要看楼主是做系统还是算法的，做系统的比如Spark这个record可以找top30 AP了。
如果做算法比如probability query, KNN search，这样record在香港新加坡也能找出
一批，北清华五的青千肯定不行（因为楼主没有工作经历，要破格）。
估计楼主是做算法的，因为系统根本不会投TKDE。建议楼主在美国找AP，不管排名多少
做了2年再申青千，基本稳 |
|
d*********i
发帖数: 104 | 39 Given 2D coordinates , find the k points which are closest to the origin.
Propose a data structure for storing the points and the method to get the k
points. Also point out the complexity of the code.
好像见讨论过，怎么做比较好呢 |
|
|
|
|
d*********i
发帖数: 104 | 43
恩 我也觉得pq, max-heap 这个可行，不知道还有没有更优呢 |
|
f*****e
发帖数: 2992 | 44 quick-sort similar idea, find the kth element in n elements. All elements on
its right are suitable candidates. Not good for online large data. |
|
c********t
发帖数: 5706 | 45 感觉已经最优，除非要求O（1）空间，只能in place sort,时间复杂度就是O(nlogn)了 |
|
l*******b
发帖数: 2586 | 46 heap本身就可以in place 实现吧。O(n)时间构造，O(k log n) 提取k个最小的 |
|
g*****e
发帖数: 282 | 47 面过一个类似的题，其他相同，但不是求离原点最近k个，而是对任意输入，求离这个
点最近的k个点，k是常数。
我给出的是BF，分支定界，但time complexity不变。any better idea? |
|
c********t
发帖数: 5706 | 48 说到这里，我有很菜的java问题，heap,map,set, list,如果存的是object,应该只是存
储reference.对吧? 但是也要算作O(n)储存空间吧，怎么能算in place呢？
你可能与上面说的方法不同,解法是构造 k size的 max heap O(n log k); |
|
c********t
发帖数: 5706 | 49 感觉是一样的，只是每个点先要算一下到给定点距离,比较距离 |
|
l*******b
发帖数: 2586 | 50 嗯，我想的是做一遍heap sort. 数据太大应该用辅助空间比较好。 |
|
