# Clustering binary categorical data

I have some data where I have certain classes (c1, c2, c3, c4 ...) and the data comprises of binary vectors where 1 and 0 denote that an entry belongs to a class or not. The number of classes will be > 200. The data will look like this:

c1    c2    c3    c4    ...
1     0     0     0    ...
0     1     1     0


Would this data come under "Categorical" type?

Details:

• Sample Size : ~20000

• No. of classes : 300

• Data Matrix Sparsity : 99.52%

• Problem Statement: The classes that I am talking about are medical services provided by Hospitals. If a hospital provides the service we just put 1 or else 0 in the binary vector. I want to cluster similar hospitals on the basis of their services.

I tried out PCA for dimension reduction on this dataset and I even got good clusters with DBSCAN but I read that for categorical sparse data PCA is not recommended and also Euclidian distance as the distance measure is not good.

I am planning to use MCA (Multiple Correspondence Analysis) but I cannot figure out how am I supposed to represent the data for that.

• Next question: what is your actual research question? Jul 5 '14 at 1:38
• Check out Sokal-Snaith and Sokal-Michener as possible distance metrics for clustering binary data. And you can use multidimensional scaling with any distance metric you choose.
– user49537
Jul 5 '14 at 1:43
• Ok, (1) yes, that's categorical data, (2) it's not clear that you have sparse data, since $n>>p$, which does not answer your question about whether PCA meets your needs or not. Jul 5 '14 at 3:01
• @Alexis But the binary matrix that I have is of dimensions 20000 X 300 and it primarily populated with zeros! I calculated the sparsity it is around 99%. And sorry there was a typo, the sample size is 20000. Jul 5 '14 at 3:16
• @AnimeshPandey, If every of the 20000 rows (clinics) contain 1's then 99.52% sparsity means that too few rows share 1's in the same columns; and clustering is senseless. Or, if there are many fully sparse rows then you should delete them first. Jul 5 '14 at 17:24

A simple approach is to fit a mixture of "Naive Bayes" models using EM. The structure of the mixture model is $P(x_{i1},\ldots,x_{in}) = \sum_k P(y_i=k) \prod_j P(x_{ij}|y_i=k)$. Here, $i$ indexes the data points, each of which is a vector of $n$ binary features. $y_i$ is the index of the cluster to which data point $i$ belongs. $P(y_i=k)$ is the (learned) probability of a point being generated by cluster $k$. $P(x_{ij}|y_i=k)$ is the (learned) probability of generating the value of feature $j$ for points belonging to class $k$.

This model treats the binary values in each cluster as independent conditioned on their membership in the cluster. This is the discrete analogue of fitting a (diagonal) Gaussian mixture model. My former student Tony Fountain and I applied this kind of model to cluster patterns of die failure on silicon wafers.

This model is an instance of what is known variously as Latent Class Analysis or Latent Trait Analysis. A good overview of these techniques can be found at this website by John Uebersax in which he discusses a variety of Latent Class models including Probit Discrete Latent Trait Models. The Probit model uses a latent multivariate Gaussian distribution to model each cluster, which can capture pairwise correlations among the binary responses within the cluster. I believe Uebersax provides a software package, but I have not tried it.

First try to figure out what a meaningful similarity function is for your use case. This is very much use case dependant, so there is no one-size-fits-all solution.

Once you have a working notion of similarity, try hierarchical clustering or DBSCAN with this similarity. Note that having a working similarity is a requirement for these algorithms to yield good results.

## Think outside the box of vectors, and think in your data world

Mathematically, you have a vector space. But that isn't what your data means. PCA will maximize variance in this vector space, but what does this mean?

Instead, choose approaches that mean something for your data. For example, frequent itemsets and association rules could mean much more on your data. Your data probably isn't random numbers, but there is some reality, some semantics attached to it. You need to get this tie to reality into your analysis.

• I've seen you give this advice a number of times. I think it's good advice, but for those who are sufficiently beginners to be asking these questions "figure out what a meaningful similarity function is for your use case" may be too abstract to be usable. I think what would help is to have a list of briefly described scenarios (say a paragraph each). Then for each scenario we could have a possible dissimilarity function & a couple of sentences explaining why that is a good choice for that scenario. (If you'd be interested, I could ask this as a new question.) Apr 19 '15 at 15:45
• Well, there are whole books just on similarity measures (e.g. the encyclopedia of distances), and so on preprocessing. Doing a good preprocessing, feature extraction and similarity measures are probably 99% of the work, but everybody just teaches the 1% fancy algorithm part. Apr 19 '15 at 16:45
• I am aware the the Encyclopedia of distances. I don't think it would benefit the OP or CV generally to try to reproduce it here. There are a small number of distances that are commonly used (in the binary context: matching vs Jaccard, eg; in the continuous context: Manhattan vs Euclidean vs maximum, eg). In this case, you are contrasting any distance w/ FIM &/or AR (FTR, I know nothing about FIM & AR), & saying they should use the 1 that fits better w/ their situation. It would be best if we can help them think through which might fit better & why. Apr 19 '15 at 17:33
• A small set of short, concrete examples might do that. And then we could link subsequent questions (this seems to come up often) back to that discussion. If there is a good book on preprocessing, pitched at an applied level appropriate for the OPs asking these Qs (ie, not the Encyclopedia of distances), it might be worthwhile to cite &/or link to it as well. Apr 19 '15 at 17:35
• (I don't mean to come off as critical. I do think this is good advice & I upvoted it. I just wonder how much of this can actually be taken away & used by the OP.) Apr 19 '15 at 17:38

Affinity propagation clustering could be an interesting method for you to try. But it is more important to pick a binary metric that matches you requirements. If you have an appropriate similarity metric, it would also be helpful to visualize the data with MDS methods (or non-linear dimensionality reduction) in 2D or 3D space.

• I did think over picking a metric. I came down to Jaccard Coefficient and Hamming Distance among which I feel Jaccard might suit my needs. Jul 5 '14 at 16:29

I used hierarchical clustering with cosine distance for a similar problem and it worked well. If they have no services in common the distance will be 1. If they have exacltly the same services the distance will be 0.