What is the VC dimension of k-nearest-neighbours with k=1?

I would answer that it is $$\infty$$, but I have a gut feeling this may not be the correct answer...

May I present my proof attempt that it is indeed $$\infty$$, so that you can clear any misconceptions I have (if there are any)?

To my understanding, let $$H$$ be the family of all 1-NN classifiers. $$VCdim(H)\geq m$$ if there exists a set $$X$$ of $$m$$ points that is shattered by $$H$$ - that is, if for every possible classification of elements in $$X$$, there is a classifier $$h\in H$$ which yields this classification.

We will show that for each finite $$m$$ every set of $$m$$ points is shattered by $$H$$.

Let $$X$$ be a set of $$m$$ points. Let $$d$$ be the minimum distance between any two points in $$X$$. ($$d>0$$, because otherwise the distance between some two points would be $$0$$, so this would be only one distinct point, so $$X$$ would be a set of at most $$m-1$$ points and not of $$m$$ points).

Let $$C(X)\in\lbrace0,1\rbrace^m$$ be an arbitrary classification of elements of $$X$$. We will construct a classifier $$h\in H$$ that yields this classification. This will be the classifier trained on $$X$$. For every point $$x\in X$$, a 1-NN classifier trained on $$X$$ will yield the classification $$C(x)$$, since the fact that $$d>0$$ guarantees us there will be no ties in voting.

Since for each finite $$m$$ we have $$VCdim(H)\geq m$$ we know that $$VCdim(H)=\infty$$.

Is the above proof correct? Is the VC dimension of 1-nearest-neighbours really $$\infty$$?

• Yes you are right. VC dimension of kNN with k=1 is infinite. See this : quora.com/… Jun 23 '19 at 16:19