6
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ I don't think clustering is going to be useful here. You might look into network analysis. $\endgroup$
    – Peter Flom
    Commented Nov 28, 2012 at 21:39
  • 1
    $\begingroup$ I wonder if correspondence analysis would be helpful for you. You can find a brief guide on Quick-R. $\endgroup$
    – gung - Reinstate Monica
    Commented Nov 28, 2012 at 22:09
  • $\begingroup$ @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. $\endgroup$
    – steffen
    Commented Nov 29, 2012 at 7:46
  • $\begingroup$ 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? $\endgroup$
    – Aman
    Commented Dec 3, 2012 at 18:29

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ (+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). $\endgroup$
    – steffen
    Commented Nov 29, 2012 at 7:34
  • $\begingroup$ 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. $\endgroup$
    – micans
    Commented Nov 29, 2012 at 10:02
  • $\begingroup$ 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. $\endgroup$
    – Has QUIT--Anony-Mousse
    Commented Nov 29, 2012 at 11:53
  • $\begingroup$ @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 $\endgroup$
    – user1848018
    Commented Nov 29, 2012 at 16:25
  • $\begingroup$ @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? $\endgroup$
    – user1848018
    Commented Nov 29, 2012 at 16:28
1
$\begingroup$

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.

The script can be downloaded from : http://www.clusteranalyse.net/sonstiges/zaspringseminar2002/

HTH ftr

Improve this answer
$\endgroup$
1
  • $\begingroup$ FYI, in case you followed the link and hit the back button b/c the web page is in German, Johann Bacher's posted lecture notes are in English. $\endgroup$
    – Aman
    Commented Nov 29, 2012 at 17:15

Your Answer

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

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