I'm trying to write a simple recommendation system. I have a set of products that exist in a set of categories and I know whether a given customer liked a subset of the items. From this I can deduce an "affinity" from each customer to each category (a number 0..1 defining the fraction of the products from that category that they liked).


Given these affinities I can place the user in a vector space in N dimensions (where N==the number of categories), cluster together similar customers and recommend to them the top products in categories that they might like but not know that we carry. There are a very high number of categories (although a much smaller number that are active in any given period), users, and products.


I'm trying to cluster them using the kmeans algorithm ([specifically this Haskell library](http://hackage.haskell.org/packages/archive/kmeans/0.1.1/doc/html/src/Data-KMeans.html#kmeans)). The problem I'm having is deciding how to compute the distance between the vectors of two customers, given their sparseness. Not only am I worried about the computational complexity and storage of having to expand the vector of every customer to a dimensionality that will fit every category (even though a given customer has probably only rated items from ten categories in the common case), I also can't just assume that the value of a missing dimension is 0, because that's a meaningful value (they hated every item from that category that they purchased).


Is there a well-defined way to compare vectors with undefined values?



Clustering sets of sparse vectors with high dimensionality
Let affinity range between -1 and 1, with zero representing indifference/no opinion/haven't tried it. Customers have a right to hate.


Storage is much easier: You need only store the non-zero affinities. e.g. A.J. = [MathOverFlow : 1, Coffee : 1, Decaf: -1]


My consulting fee is $5. I accept cash or check.


