MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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). 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?

share|cite|improve this question
up vote 1 down vote accepted

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.

share|cite|improve this answer
What about beer? – David King Jul 16 '10 at 17:53
Beer: +1 , I'd say. – userN Jul 16 '10 at 18:45

You are running, or working for, a commercial enterprise. I suggest you hire a mathematician as a consultant.

share|cite|improve this answer
Actually, this is something that I'm doing for fun. But it's easiest to explain in terms of products and categories. – David King Jul 16 '10 at 7:02
How do you define a "commercial enterprise" (which according to your anwser (looks like a comment) do not deserve an answer to a question in a question/anwser web site). Is it somwhere really deep under the ground near hell :) ? – robin girard Jul 16 '10 at 12:03

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.