Decision tree vs. KNN

Question

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?

Answer 1

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 features must be numeric. Distance metrics may be effected 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.

Answer 2

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:-

1. 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.

2. 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.

3. "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.

4. 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

Answer 3

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.

Answer 4

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: http://www.simafore.com/blog/bid/62482/2-main-differences-between-classification-and-regression-trees