I have a data set with about 50K rows and 100 columns. You can consider every row to be representing one restaurant.

My goal is to calculate dissimilarities between all the restaurants - Gower's coefficient.

Of those 100 columns (features), a few of them are numeric data and nominal data. The problem is the other columns (about 90) are very sparse binary data (1/0).

I do think that those 90 columns of binary data can be reduced to some smaller number of columns, so that the computational time can be reduced significantly. But I don't know what method I should use to reduce such a large amount of binary data.

Can anyone give me some suggestions?

It will be most helpful if you can provide me some references and R code.

  • 1
    The problem is: be there any dimensionality reduction or not, you stay with 50000 cases. And you want a 50000 x 50000 proximity matrix. Big. (Will your machine cope and in what time?) What you want that matrix for? – ttnphns Nov 4 '13 at 3:09
  • I am working on a recommendation model for restaurants. So i need to have their item-to-item dissimilarities. I have successfully implemented a program for this but that program takes 2 days to complete this task. that is why i think by reducing the dimension, the program can run faster. – Kloser Cheung Nov 4 '13 at 3:17
  • 1
    I wanted to say: dimensionality reduction won't help computationally (and thus isn't necessary). 100 variables isn't much. It is 50K cases which is much. But as you've just said, you don't want to lessen their number and you insist on complete 50K x 50K matrix. I don't know how to help you. – ttnphns Nov 4 '13 at 3:24
  • However, I don't know your implemented program. Have you tried to compute it, say, on 50 variables? How many hours it took? – ttnphns Nov 4 '13 at 3:29

I do think that those 90 columns of binary data can be reduced to some smaller number of columns, so that the computational time can be reduced significantly

This assumption seems unfounded to me. Since the computational time of calculating pairwise dissimilarities corresponds O(n^2) the effect of dimensionality reduction will be merely noticeable. I mean if it takes two days, you wouldn't mind 2-3 hours less.

What I have in mind is

  1. Do you really need all pairwise dissimilarities? Often one actually doesn't. Therefore a spatial index can be used.

  2. If you do need them all: Do you need to update them often? How about keeping the dissimilarities. Adding a single item will take few time

Anyway you should try to reformulate the problem. 10 or 100 variables will make little difference in accomplishing your current approach.

You could try to use PCA to reduce the dimension. It is pretty normal to consider binary numbers as real values when using PCA. Also, an appropriate implementation of PCA should just have to deal with the 100x100 covariance matrix in your case, not 50K x 50K matrix.

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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