Can a decision tree recreate the exact same classification as a nearest neighbor classifier?

Please explain why. This is a general question so it is okay to give a general answer.

I would use both classifiers on the exact same data set. Would I be able to recreate exact same classification?

• Do you mean: "Is it possible to get the same classification using on one hand KNN and on the other hand a decision tree?" or "Given a KNN classifier, is it possible to find a decision tree giving the exact same classification?" ? I think this would not lead to the same answer. My first thought is also that it depends on the data. If you have points with the exact same coordinates, KNN may chose to use only some of these points while performing KNN, that could not be done by a decision tree. Commented Feb 20, 2017 at 9:33
• Yes to both variants of the question. If it depends on the data then it is a valid anser. Commented Feb 20, 2017 at 10:36

Can a decision tree recreate the exact same classification as a nearest neighbor classifier?

Yes.

Think about a trivial data set with only two points (0,0),(1,0), each belonging to a different class. The decision boundary of a 1-NN will be the perpendicular bisector of the segment.

Now, if you look for a splitter for this two points, using a decision tree, you will find a line (probably the parallel to the y-axis going through 1/2 (1)).

I think any 1-dimensional data with perfect separation between two classes would produce the same "decision boundary" for 1-NN and decision trees.

What are the odds that a decision tree recreates the exact same classification as a nearest neighbor classifier?

In more than 1 dimension, almost certainly (2) no. The decision boundary for nearest neighbours are Voronoi diagrams :

Whereas the decision boundary of a decision tree are lines parallel to the axis.

More details can be found here : Questions on some data-mining algorithms

(1) Most decision tree implementations look at the splitters defined by the average between two consecutive points. Therefore, 1/2 could be one of the decision boundary chosen by the algorithm, but this is implementation dependant.

(2) If you assume a distribution over Voronoi diagrams, we can assume that the measure is rotation-invariant. Therefore making the probability of all the lines of a Voronoi diagram being parallel to the axis zero.

As pointed out in my comment, there are two ways to analyze your question. But in both cases, the answer will be "it depends on the data" and on the implementations of KNN and the decision tree. I wrote about data having the same coordinates that can be treated differently by KNN and the decision tree (depending on the implementation of KNN). Also, in a decision tree, you cannot chose precisely the number of points in each leaves (you can specify the minimum number of points to split a node, but again the specific number of points per leaf will depend on the data you have).

We could rephrase the question as: "can we find implementations of KNN and decision tree that would lead to the exact same classification for a specific dataset?"

Maybe in some cases (only one covariate, k = 1 and complete decision tree) it might work, but in general I think it would not.

Even if all your points have different coordinates, the optimization for a split in a decision tree is made on entropy or Gini, using only one variable per split. That leads to division of the space in hypercubs, not in geometrical balls.