MMD_2b_NearestNeighborLearning

Large scale machine learning ways

• k-nearest neighbor(instance based learning)
• support vector machine
• decision tree

main question: how to efficiently train (build model and find model parameters)?

Instance Based Learning

概述

具体方法

• 1NN
• KNN
• KernalRegression

发现NN

通常，有两种发现问题：

1. 选择距离最近的K个
2. 设定距离的阈值，发现小于该阈值的NN点

当数据量大到一定程度时，不可能分别比较每个点与query点得距离，这样的话所用的时间是线性的，不适合解决大规模的问题。 这个时候，使用LSH(local sensitive hashing)，可以缩减问题的规模，使得所用的时间是constant的。