16
$\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
  • 3
    $\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.

$\endgroup$
5
  • $\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
  • 12
    $\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$ 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
9
$\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

$\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.

$\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

$\endgroup$
0
$\begingroup$
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

$\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.