Why is this nearest neighbors algorithm classifier implementation giving low accuracy?

Question

I'm applying nearest neighbors algorithm KNN classifier on a movie rating dataset, it was a sparse document-term matrix in the Matrix-Market format.

I've converted it into a format same as this IRIS dataset.

There are 5000 features and 2000 instances. I'm using this code for building this classifier.

The Euclidian Distance measure gives poor results like 6% accuracy, I then tried Cosine Similarity function. The code is as following:

def dot_product(a, b):
return sum(map(lambda x: x[0] * x[1], zip(a, b)))

def cosineSimilarity(a, b):
    sumxx, sumxy, sumyy = 0, 0, 0
    for i in range(len(a)):
        x = a[i]; y = b[i]
        sumxx += x*x
        sumyy += y*y
        sumxy += x*y
    return sumxy/math.sqrt(sumxx*sumyy)

Even this did not improve results. Most of them are Zeros since not everyone is rating all movies. So I read it somewhere that chaging all zeros to 0.1 will improve results, but that did not improve results as well.

I've tried K-Fold cross-validation too, but as you guessed, it did not improve anything.

My general setting is: k=3, split for Training/testing = 0.9

Are there any obvious improvements? Any mistakes in my code? For now, I am trying only unweighted voting, but suggestions for weighted majority voting are welcome as well.

Note: Using ML libraries is not an option.

Answer 1

You should probably try to reduce the number of variables to a sensible set before trying to classify using nearest neighbors. Otherwise you'll fall victim to the curse of dimensionality, which is referenced in the Wikipedia article on $k$-nearest neighbors. You might also consider some sort of scaling of the variables so that no particular attribute has an undue influence on your classifications.

Your Python code could also be simplified quite a bit. Instead of defining these functions you could use the inner product function from numpy:

import math
import numpy as np

# inner product
np.dot(a, b)

# cosine similarity
np.dot(a, b) / math.sqrt(np.dot(a, a) * np.dot(b, b))