# Clustering high-dimensional sparse binary data

I am trying to cluster Facebook users based on their likes.

I have two problems: First, since there is no dislike in Facebook all I have is having likes (1) for some items but for the rest of the items, the value is unknown and not necessarily zero (corresponding to a dislike). If use 0 for unknowns, then I think my clusters will be biased. Any suggestion?

Second, supposed I assign 0 to unknown items and cluster them, using a hierarchichal clustering method using a binary measure distance such as Jaccard, Tanimoto,...

How can I evaluate the clustering results? The within and outside SSE is not appropriate for binary data. If I use median centers, I m afraid most of them are going to be zero as I have a sparse feature matrix. So what would be a good way to evaluate the clusters?

• I don't think clustering is going to be useful here. You might look into network analysis. Commented Nov 28, 2012 at 21:39
• I wonder if correspondence analysis would be helpful for you. You can find a brief guide on Quick-R. Commented Nov 28, 2012 at 22:09
• @user1848018 setting the unknown user-item-combinations to 0 is fine. 0 of course means only "no like given yet" and allows no differentation between "does not like" and "unknown", but this is no issue, since Jaccard et. all define similarity of two users by the overlap of items both users like. Commented Nov 29, 2012 at 7:46
• Are suggestions for graph or network approaches inspired by the fact that this is Facebook data? // Let's pretend our data is high dimensional and sparse and binary -- but the data and our objectives are completely unrelated to SNA. We want to cluster objects based on a large number of binary features. What's the approach, and is it possible to address the OP's concern about confusing '0' with 'NaN's?
– Aman
Commented Dec 3, 2012 at 18:29

Consider using a graph based approach.

Try to find a threshold to define when users are "somewhat similar". It can be quite low. Build a graph of these somewhat similar users.

Then use a Clique detection approach to find groups in this graph.

• (+1) yes, graph clustering is the way to go. I recommend this survey (Graph clustering by Satu Elisa Schaeffer), which also deals with the evaluation of clusters (see 4.2). Commented Nov 29, 2012 at 7:34
• I agree with the general approach (and suggest using e.g. tanimoto similarity between 'like' sets), but why specifically Clique detection? It's one of the (types of) algorithms I favour least -- the definition of a cluster is very sensitive to removal of a single edge. Commented Nov 29, 2012 at 10:02
• Just as a starter to point him towards graph based methods instead of vector data point clustering. Starting with Clique he will surely discover approximate cliques etc. Commented Nov 29, 2012 at 11:53
• @Anony-Mousse thanks for always providing good feedback, would a graph based approach, scale for large data. For traditional clustering I could use MAHOUT which is claimed to scale well so how about graph base approach. I already know R has quite a few packages, any suggestion? R-base or Java base Commented Nov 29, 2012 at 16:25
• @micans, I liked your comment about the cliques, but would be an alternative to a clique detection approach? Would it be A model base statistical approach? Commented Nov 29, 2012 at 16:28

I suggest a cluster analysis. Joachim Bacher discusses the different dissimilarity coefficients in depth in his script about cluster analysis, in particular the effects of treating the absence of a treat. For instance : are two items correlated when both show zero ? I remember that he also works with a multiple-response example from survey research which is close to your problem.