2
$\begingroup$

I am looking to cluster users together in a database, with each user represented by a number of features that are both discrete and continuous in nature. "Similar" users should be clustered together in a way that underlying strongly correlated features can be easily discovered. A few other requirements:

  • The number of clusters is unknown
  • The runtime execution time is not a concern
  • The number of users can be on the order of 100,000 and number of features around 50

There are a number of clustering techniques, from KNN, k-means, matrix factorization, even PCA, but many seem to hide the underlying correlations that tie the users together. Any advice?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ There's a good chance your question might get shunted off to metaoptimize.com, but I'll essay an answer here. $\endgroup$
    – Suresh Venkat
    Dec 8, 2010 at 5:17
  • $\begingroup$ Thanks! Should I cross post there? $\endgroup$
    – DanB
    Dec 8, 2010 at 5:27
  • $\begingroup$ could you elaborate on the statement "many seem to hide the underlying correlations"? The SVD, for example, will give you a projection onto a lower dimensional hyperplane, and you can deduce the significance of each feature from the "angle" of this hyperplane. Is this what you're looking for? $\endgroup$
    – gabgoh
    Dec 8, 2010 at 5:32
  • $\begingroup$ It took me some time to realize that “K-NN” stood for “K-nearest neighbors.” Can you spell it out somewhere in the question? $\endgroup$
    – Tsuyoshi Ito
    Dec 8, 2010 at 16:25
  • $\begingroup$ See my comments below... $\endgroup$
    – DanB
    Dec 8, 2010 at 17:17

1 Answer 1

Reset to default
2
$\begingroup$

You're asking essentially a modelling question, and so the answer really depends on your data. If you're saying that strong correlations are not being identified by the methods you listed, it's possible that the correlations are non-linear (the above methods with the exception of k-NN are linear), and so you might try something like ICA.

For something closer to home, have you considered correlation clustering ? you don't say how the data is presented, but if you have similarity and dissimilarity information, then correlation clustering is a good solution, and also does not require you to specify the number of clusters.

Another idea would be to try spectral methods (if all you have is a distance function) like spectral clustering.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Helpful! Nothing has been implemented yet, but I was under the assumption that the nature of how clustered users are correlated (ie, what are their principle components) is not clear with most methods. Would such relations be revealed by ICA? $\endgroup$
    – DanB
    Dec 8, 2010 at 5:36
  • $\begingroup$ I'm not sure what that means. With PCA, you get a matrix that describes how the space has been transformed. With ICA, you'd get some similar information as well. $\endgroup$
    – Suresh Venkat
    Dec 8, 2010 at 5:47
  • $\begingroup$ I can see that with PCA, but is that really clustering? (apologies, my background is in engineering but not CS, so I understand SVD from an axis-rotation information-theoretic standpoint). Let me make my example more concrete. Let's say the features per user are: $\endgroup$
    – DanB
    Dec 8, 2010 at 17:06
  • $\begingroup$ (hit enter too soon!) gender (m/f), location (one of 10 cities), and favorite color (red/green/blue). Let's say that we have N users and that favorite color is a R.V. dependent on gender and city. How are we to discover strong correlations with gender and/or location and favorite colors? $\endgroup$
    – DanB
    Dec 8, 2010 at 17:16
  • $\begingroup$ we're getting well out of the scope of this site at this point. But the transformation that PCA provides is an axis transformation. the "strongest" axis is some combination of the primary axes, which indicates how the relevant variables correlate. But I agree that PCA is not the ideal solution. I think your best bet is to post on stats.stackexchange.com and/or the ML site. If you want a fast algorithm after they tell you what to do, come back here :) $\endgroup$
    – Suresh Venkat
    Dec 8, 2010 at 17:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.