4
$\begingroup$

I got a dataset with about 5,000 columns and about 135,000 rows - all fields contain boolean (binary) data. I am looking to classify each of these columns into one of 50 groups, based on similarity.

Can anyone point me in the right direction where to start? Will a k-mean style algorithm suit me? Any library in R that I can easily access?

Note: data is quite asymmetric in that about 95% of values are 0, 5% are 1.

$\endgroup$
2
  • 1
    $\begingroup$ The key point here is about "similarity". Do you have any ideas about what sort of similarity you want? $\endgroup$
    – ttnphns
    Sep 16, 2013 at 8:28
  • $\begingroup$ I would have thought the proportion of rows which both hold '1' would be a good measure... $\endgroup$
    – willy_pond
    Sep 17, 2013 at 5:57

1 Answer 1

3
$\begingroup$

There are dedicated clustering algorithms for binary data. You may want to get e.g. the book

  • G. Gan, C. Ma, and J. Wu. Data Clustering. Theory, Algorithms, and Applications. Society for Industrial and Applied Mathematics (SIAM), 2007

which should discuss methods such as COOLCAT, ROCK, STUCCO. Frequent itemset methods may also be applicable, i.e. APRIORI, FPGrowth, Eclat, etc.

If you want to use methods such as hierarchical clustering (which probably won't scale up to 135000 rows anyway), you will need to define a good measure of similarity first. Then think of ways to search for similar items more efficiently than performing all pairwise comparisons.

$\endgroup$
2
  • $\begingroup$ Thanks - I will look up those methods and their R implementations. As for measure of similarity: is it silly that similarity be just defined as 'matching row proportion'? The comparisons could be reduced by just sampling each field rather than calculating for the whole set.... $\endgroup$
    – willy_pond
    Sep 17, 2013 at 5:55
  • $\begingroup$ It may work, or not. Depends on your data. "matching row proportion" for twitter data is not working well. $\endgroup$ Sep 17, 2013 at 7:32

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.