Data Science Stack Exchange is a question and answer site for Data science professionals, Machine Learning specialists, and those interested in learning more about the field. It only takes a minute to sign up.
Sign up to join this community
In which cases is it better to use a Decision tree and other cases a KNN?
Why use one of them in certain cases? And the other in different cases? (By looking at its functionality, not at the algorithm)
Anyone have some explanations or references about this?
They serve different purposes.
KNN is unsupervised, Decision Tree (DT) supervised. (KNN is supervised learning while K-means is unsupervised, I think this answer causes some confusion.) KNN is used for clustering, DT for classification. (Both are used for classification.)
KNN determines neighborhoods, so there must be a distance metric. This implies that all the features must be numeric. Distance metrics may be affected by varying scales between attributes and also high-dimensional space.
DT, on the other hand, predicts a class for a given input vector. The attributes may be numeric or nominal.
So, if you want to find similar examples you could use KNN. If you want to classify examples you could use DT.
knn and k-means are different algorithms and this answer does unfortunately ( and erroneously ) miss those two procedures up. knn is neither unsupervised nor used for clustering! See Q: Diff kNN and kMean
$\endgroup$
Classifiers like Decision Tree, Bayesian, Back-propagation, Support Vector Machine come under the category of "Eager Learners", because they first build a classification model on the training dataset before being able to actually classify an [unseen] observation from test dataset. The learned model is now "eager" (read hungry) to classify previously unseen observations, hence the name.
The KNN-based classifier, however, does not build any classification model. It directly learns from the training instances (observations). It starts processing data only after it is given a test observation to classify. Thus, KNN comes under the category of "Lazy Learner" approaches.
Based on the above foundational differences, we can conclude the following:-
Since KNN performs on-the-spot learning, it requires frequent database lookups, hence, can be computationally expensive. Decision Tree Classifier does not require such lookups as it has in-memory classification model ready.
Since KNN performs instance-based learning, a well-tuned K can model complex decision spaces having arbitrarily complicated decision boundaries, which are not easily modeled by other "eager" learners like Decision Trees.
"Eager" learners work in batches, modeling one group of training observations at a time. So they are not fit for incremental learning. But KNN naturally supports incremental learning (data streams) since it is an instance-based learner.
Further, KNN classifier gives test error rates closer to that of Bayesian classier (the gold standard). As quoted in ISLR:
The Bayes error rate is analogous to the irreducible error
From Sebastian Raschka's Python Machine Learning:
The main advantage of such a memory-based approach [the KNN] is that the classifier immediately adapts as we collect new training data. However, the downside is that the computational complexity for classifying new samples grows linearly with the number of samples in the training dataset in the worst-case scenario—unless the dataset has very few dimensions (features) and the algorithm has been implemented using efficient data structures such as KD-trees. J. H. Friedman, J. L. Bentley, and R. A. Finkel. An algorithm for finding best matches in logarithmic expected time. ACM Transactions on Mathematical Software (TOMS), 3(3):209–226, 1977. Furthermore, we can't discard training samples since no training step is involved. Thus, storage space can become a challenge if we are working with large datasets.
The decision tree, however, can rapidly classify new examples. You're just running a series of boolean comparisons.
I would add that decision trees can be used for both classification and regression tasks. DT on the other hand predicts a class in the accepted answer would be more specific by describing Classification trees which is technically a subtype of the generic DT concept.
One reference(ignoring the bottom layers that discuss specific implementations):
From here
| k-NN | Decision Trees |
|---|---|
| There is no real 'training' time since no computation is performed while training. All that needs to be done is storing the training data. | Training involves iteratively building a tree (considering the ID-3 algorithm) so considerably more time than k-NN. |
| High testing time since the distance needs to be computed between the test point and every training point. | Low testing time since it's a traversal down a tree. |
| The user needs to choose a distance metric in order to use a k-NN for testing. | No need to choose a distance metric since the splits will occur based on values inherent to each feature. |
| Updating an existing model with new data simply means adding that point to the existing dataset | An existing tree cannot be updated - an entire new tree needs to be created |
| Need to store all the training data in order to classify a new incoming point | No need to store the training data - only store the tree model |
Some additional notes:
Both, k-NN and decision trees are supervised algorithms (unlike mentioned in one of the answers). They both require labelled training data in order to label the test data.
k-D trees are a neat way of optimizing the k-NN algorithm. They reject large sections of the data so that classification doesn't take too long.
For more info on decision trees, refer to these excellent lecture notes: http://www.cs.cornell.edu/courses/cs4780/2018fa/lectures/lecturenote17.html
