I wish to cluster users together in a database, with each user represented by a number of features that are both discrete and continuous in nature. The aim is to define a small number of archetypal "users" with specific set of features. All other users are then categorized as being similar to one or other of these archetypes. An important consideration is that I expect the features to have strong dependency structures, and I would like the method to be effective at making these explicitly visible.

For example say the features per user are:

  • gender (m/f)
  • location (one of 10 cities)
  • 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 possible strong correlations with gender and/or location and favorite colors? There are a number of clustering techniques, from K-NN, k-means, matrix factorization, even PCA, but many seem to hide the underlying correlations that tie the users together.

Could anyone recommend suitable methods for this unsupervised learning task?

[heavily edited in an effort to revive and resolve]

  • $\begingroup$ in addition to Galit: Do you want primarily to find correlations and hence clustering is just the way, not the goal, or do you want to find clusters of users to discover some knowledge in the data (with respect to correlation) ? $\endgroup$
    – steffen
    Commented Dec 10, 2010 at 10:53
  • $\begingroup$ I'm not clear on whether you are after unsupervised clustering (where all variables are treated equally) or in supervised classification (where you have a Y variable and a set of X variables). K-NN is a supervised method, while k-means clustering and PCA are unsupervised. Can you explain the purpose of clustering the users? $\endgroup$ Commented Jan 9, 2011 at 12:49
  • $\begingroup$ Both of you are right, I may have jumped the gun on clustering. The goal is to find "archetypes" for users in the database, that is, some number of user groups much less than the total number of users, where each group can be described using the fewest number of features while minimizing the average distance between the description and each user. This is definitely unsupervised. $\endgroup$
    – DanB
    Commented Jan 9, 2011 at 12:49
  • 3
    $\begingroup$ @Corone, I appreciate the work you're doing to find, edit, & revive the dead Q's in CV's backlogs. This edit was rather extensive, & perhaps controversial. I tried to split the difference by using the explication of the Q that you had derived from the comments, but maintaining the example the OP had wondered about. I hope that's OK. $\endgroup$ Commented Feb 13, 2013 at 4:16
  • $\begingroup$ I've never used it, just heard about it, so I dont want to write this as an answer proper, but it looks like an application for Cutler and Breiman's "archetypal analysis". $\endgroup$ Commented Feb 13, 2013 at 5:13

1 Answer 1


Using exemplars, i.e. data points which could best describe the dataset as a whole, should be a reasonable first step. The most common exemplar clustering method is the Affinity Propagation (AP) methodology put forward by Frey & Dueck (2007) Clustering by Passing Messages Between Data Points; it is considered somewhat more robust to noise than standard $k$-means but usually quite slower too.

AP allows us "making these (dependency structures) explicitly visible" by looking at the fitted availabilities and responsibilities matrices; roughly speaking these matrices encode how suitable is candidate instance $j$ is to be cluster centre (i.e. overall examplar) for point $i$ and how well the point $i$ will do to choose point $j$ as its exemplar, respectively. The R package apcluster is actually much more faithful to the original MATLAB implementation of the algorithm than the Python sklearn implementation of the Affinity Propagation clustering methodology so I would suggest familiarising oneself first with the R version.


Your Answer

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