Welcome to MathOverflow

Question

1

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?

flag	asked Jul 16 2010 at 6:42 David King 13●2

userN · Accepted Answer · 2010-07-16 17:24:56Z UTC

1

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.

answered Jul 16 2010 at 17:24

userN
2,674●9●24

	What about beer? – David King Jul 16 2010 at 17:53
	Beer: +1 , I'd say. – userN Jul 16 2010 at 18:45

Gerry Myerson · Answer 2 · 2010-07-16 06:56:32Z UTC

1

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

answered Jul 16 2010 at 6:56

Gerry Myerson
15.6k●1●47●87

1

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 2010 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 2010 at 12:03

Clustering sets of sparse vectors with high dimensionality

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.