k-nearest neighbors is a simple approach for prediction in machine learning. The objective is to predict the value of a function at some point for which we don'

k-nearest neighbors is a simple approach for prediction in machine learning. The objective is to predict the value of a function at some point for which we don't have an observation in the training set. In the Netflix Prize, this means predicting the rating a user U would give to some unrated movie M. The kNN approach is: 1. Identify the k users most similar to U. This is called the "neighborhood". 2. Have these k neighbors vote on the rating that U should assign to M. The premise behind the above scheme is that similar users will assign approximately the same rating to a particular movie. To actually implement the kNN scheme requires a notion of "similarity" for step 1 and "voting" for step 2. The linked article is using Pearson Correlation as the similarity function (aka the "distance metric"), and some kind of weighted average as the voting function (as mentioned in http://dmnewbie.blogspot.com/2007/09/greater-collaborative-filtering.html http://dmnewbie.blogspot.com/2007/09/greater-collaborative-f... ) I don't think this would work very well on the Netflix dataset because the training set is super sparse. I deliberately glossed over this above, but users in U's neighborhood who haven't rated the movie M are useless when voting on the value that U should assign to M! So you have to make a call about how you form the neighborhood: do you just find the k nearest users and only average over the <= k users who actually rated M? Or do you find the k nearest users who actually assigned a rating to M (ignoring U's neighbors who haven't rated M)? Either way, with a dataset that's as sparse as the Netflix data, you're going to have a hard time forming useful neighborhoods since either you're going to have neighborhoods where there's very little information to go off of, or the "k most similar" users are actually really not very similar to U at all, leading to inaccurate prediction. More info: http://en.wikipedia.org/wiki/K-nearest_neighbor_algorithm http://en.wikipedia.org/wiki/K-nearest_neighbor_algorithm Chapter two of the excellent and free book "Elements of Statistical Learning" has a better exposition of this idea. http://www-stat.stanford.edu/~tibs/ElemStatLearn/download.html http://www-stat.stanford.edu/~tibs/ElemStatLearn/download.ht...