Dealing with lots of ties in kNN model

Question

I have a large data set (400k rows X 60 columns) that I'm trying to use to build a knn model. I'm using the caret package version of knn and the forward.search method from the FSelector package to eliminate variables via cross-validation. My problem is that once I use more than 20k lines of data I get a message about there being too many ties.

Currently I'm only checking k-values between 1-19 (and only odd #'s as they supposedly shrink risk of ties) and only using variables with > 2 levels.

Are there any other tweaks to using big chunks of data into a knn?

EDIT: This is regression problem, not a classification problem.

Answer 1

In some situation you have a lot of data items that are might be considered to be tied in distance, especially if your data is discrete (e.g. your matrix is made up of integers).

A "hack" that might be able to work is that you add a very small pseudo-random noise to the data. This will reduce the number of data items that happen to be equidistant. Note that the noise should be as small as possible so as to bias the results but large enough to reduce the ties.

Answer 2

I guess that you have ties because you are solving a multi-class problem?

This might occur for instance if you pick $k=5$ neighbors and your points belong to $1$ out of $3$ possible classes. Suppose a point $x$ has 2 neighbors of class 1, 2 neighbors of class 2 and 1 neighbor of class 3.

namely $x_1,x_4\in C_1$, $x_2,x_3\in C_2$ and $x_5\in C_3$, and $$ d(x,x_1)<d(x,x_2)<d(x,x_3)<d(x,x_4)<d(x,x_5) $$

Basically you need to choose whether you pick $1$ or $2$. To break a tie you may have to use a different criterion to select the class, such as making partial sums of distances for each class

$$S_1 = e^{-d(x,x_1)-d(x,x_4)}; S_2 = e^{-d(x,x_2)-d(x,x_3)}$$ and pick the label with highest sum, i.e. pick $1$ if $S_1>S_2$.

Another possible approach is to decrease your neighbor size $k$ by $1$ until you solve the tie.

Answer 3

I had this problem in some real world data. Exploring the dataset I found that there were a number of hundreds of rows that all had 0 for the 3 independent vars.

I removed these from the input dataset for the KNN. Problem solved for the KNN to execute. I imputed the mode value for the dependent variable (also 0 in this case) for the hundreds of tied rows.

This is probably the same result I would have gotten from adding noise, but it appears to me to be a cleaner approach. The random noise might have affected other observations.

To summarize, check your data for frequent combinations of the input variables, handle these separately.