5 ms·

Looks like K-nearest neighbor does pretty well.

obmelvin 11y ago
Yes, k-nn is theoretically the one of the best ML algorithms in the sense that it will find the closest items in the training set. For classification or finding similar looking items it is great. However, it has pretty poor running times for evaluation of unseen data (http://nlp.stanford.edu/IR-book/html/htmledition/time-complexity-and-optimality-of-knn-1.html http://nlp.stanford.edu/IR-book/html/htmledition/time-comple...). This is contrary to something like neural networks, which take a while to train, but then evaluate very quickly. For real world use the training times matter to an extent, but in a web app or real time application the latency from knn is just impractical.
- jsyedidia 11y ago
  That's why we developed the "Boundary Forest" algorithm which is a fast nearest-neighbor type algorithm with generalization at least as good as K-NN, while being able to respond to queries very quickly. It maintains trees of examples that let it train and respond to test queries in logarithmic time with the number of stored examples, which can be much less than the overall number of training samples. It thus maintains k-NN's property of very fast training time, and is also an online algorithm, and can be used for regression problems as well as classification. See our paper that was presented at AAAI 2015 here: http://www.disneyresearch.com/publication/the-boundary-forest-algorithm-for-online-supervised-and-unsupervised-learning/ http://www.disneyresearch.com/publication/the-boundary-fores...
- wodenokoto 11y ago
  It also suffers from the curse of dimensionality, making it weaker as the number of features increase.
- andreasvc 11y ago
  I wouldn't call it theoretically the best. It is affected by outliers and doesn't make any generalization at training time. This latter point raises the questions whether it deserves the name learning. I would say linear models are typically a better learning algorithm; I wouldn't know what to call "the best" algorithm, but it might be deep learning nowadays.
darkmighty 11y ago
Try the "Island inside an island" test (put a blue cluster inside an orange island). Only k-means and SVM dealt with it satisfactorily.
- wodenokoto 11y ago
  Shouldn't a neural net with sufficient unit do that too?
  - neolefty 11y ago
    Yes, if you increase the hidden layer from 5 to 10 nodes: http://jsfiddle.net/udb95202/ http://jsfiddle.net/udb95202/
jules 11y ago
These visualisations are great but misleading regarding the performance of these classifiers. In practice you don't have a lot of data in a small number of dimensions (2 in this case). You have a little bit of data in zillions of dimensions. Think of classifying a 100x100 pixel image: that's 3x100x100=30000 dimensional data. You may not even have one training sample per class per dimension. Generalizing from comparatively little data to a very high dimensional space is the true difficulty of machine learning. Unfortunately you can't easily visualize that.

Yes, k-nn is theoretically the one of the best ML algorithms in the sense that it will find the closest items in the training set. For classification or finding similar looking items it is great. However, it has pretty poor running times for evaluation of unseen data (http://nlp.stanford.edu/IR-book/html/htmledition/time-complexity-and-optimality-of-knn-1.html http://nlp.stanford.edu/IR-book/html/htmledition/time-comple...). This is contrary to something like neural networks, which take a while to train, but then evaluate very quickly. For real world use the training times matter to an extent, but in a web app or real time application the latency from knn is just impractical.

jsyedidia 11y ago
That's why we developed the "Boundary Forest" algorithm which is a fast nearest-neighbor type algorithm with generalization at least as good as K-NN, while being able to respond to queries very quickly. It maintains trees of examples that let it train and respond to test queries in logarithmic time with the number of stored examples, which can be much less than the overall number of training samples. It thus maintains k-NN's property of very fast training time, and is also an online algorithm, and can be used for regression problems as well as classification. See our paper that was presented at AAAI 2015 here: http://www.disneyresearch.com/publication/the-boundary-forest-algorithm-for-online-supervised-and-unsupervised-learning/ http://www.disneyresearch.com/publication/the-boundary-fores...
wodenokoto 11y ago
It also suffers from the curse of dimensionality, making it weaker as the number of features increase.
andreasvc 11y ago
I wouldn't call it theoretically the best. It is affected by outliers and doesn't make any generalization at training time. This latter point raises the questions whether it deserves the name learning. I would say linear models are typically a better learning algorithm; I wouldn't know what to call "the best" algorithm, but it might be deep learning nowadays.

darkmighty 11y ago

Try the "Island inside an island" test (put a blue cluster inside an orange island). Only k-means and SVM dealt with it satisfactorily.

wodenokoto 11y ago
Shouldn't a neural net with sufficient unit do that too?
- neolefty 11y ago
  Yes, if you increase the hidden layer from 5 to 10 nodes: http://jsfiddle.net/udb95202/ http://jsfiddle.net/udb95202/

jules 11y ago

These visualisations are great but misleading regarding the performance of these classifiers. In practice you don't have a lot of data in a small number of dimensions (2 in this case). You have a little bit of data in zillions of dimensions. Think of classifying a 100x100 pixel image: that's 3x100x100=30000 dimensional data. You may not even have one training sample per class per dimension. Generalizing from comparatively little data to a very high dimensional space is the true difficulty of machine learning. Unfortunately you can't easily visualize that.