15
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ KNN is NOT unsupervised. Perhaps the answer was thinking about k-means? $\endgroup$ – user14705 Dec 12 '15 at 14:31
  • 2
    $\begingroup$ Decision tree learning is also not unsupervised. en.wikipedia.org/wiki/Supervised_learning. $\endgroup$ – Valentas Dec 14 '15 at 8:50
9
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Clarification: Clustering, but a single k-sized cluster around a given input vector. It is not necessarily true that all features must be numeric. For example, you could use Jaccard similarity to define a distance where features are nominal. $\endgroup$ – user13684 Dec 14 '15 at 12:15
  • 11
    $\begingroup$ Actually, they're both supervised. Supervised just means that the learner has access to a labeled training set. Unsupervised algorithms do things like clustering, not label prediction. $\endgroup$ – Jordan A Dec 15 '15 at 1:47
  • 1
    $\begingroup$ You can also classify with KNN based exactly on the majority of your K neighbors $\endgroup$ – Jekaterina Kokatjuhha Jun 21 '17 at 16:30
  • 3
    $\begingroup$ -1 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$ – SebNag Oct 27 '17 at 8:55
  • $\begingroup$ @SebNag, is it fair to say that sci-kit learn's "Unsupervised Nearest Neighbors" section is really just talking about k-means in disguise? scikit-learn.org/stable/modules/neighbors.html It seems like that section uses knn but just with a distance measure of some sort instead to determine clusters with no label knowledge.. i.e this sounds like k-means. $\endgroup$ – Frikster May 2 '18 at 3:07
8
$\begingroup$

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

| improve this answer | |
$\endgroup$
4
$\begingroup$

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.

| improve this answer | |
$\endgroup$
2
$\begingroup$

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

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.