# Best approach for this unsupervised clustering problem with categorical data?

I'm a software engineer new to Machine Learning. I've read about basic non-supervised techniques like k-means and hierarchical clustering and now I'm trying to put them into practice with a basic problem.

Say I've got a lot of rows of data with each row looking something like this:

"employeesRange": "11-50",
"category": "Lobbying",
"categoryGroup": "Polication Action",
"sector": "Industrials",
"subCategory": "Direct",
"tags": [ "Progressive", "Libertarian", "PAC" ]


I want to analyze this data and look for patterns, i.e. clusters of information that frequently appear together. For example maybe it's a common pattern to find smaller groups of lobbyists 11-50 people for "Progressive", "Libertarian" causes but "Presidential" or "Local Politics" groups tend to skew larger.

Or maybe there's another link to be found between categories and sector, that kind of thing.

This seems a little harder then the examples I've read about because some of my data is a tag cloud (the "Tags" field) which is unstructured can contain multiple entries and the more structured fields of categories and employees range.

It seems a good place to start is using hierarchical clustering (since I don't know k a-priori) maybe following the recommendations here:

https://stackoverflow.com/questions/23943391/how-to-cluster-users-based-on-tags

I have a few questions about this. First, is this a good approach? And is Mahout the best tool for this? Any obvious ways to simplify? And finally, how can I combine the tag clustering approach with the other more structured data in the rows?

• Mahout is about the worst tool for this, unless you have billions of records. Don't use clustering at all - use association rule mining. Jul 20 '16 at 19:45
• You should have mentioned that all of your data is categorical (and in fact, nominal categoricals); except employeesRange which is ordinal categorical.
– smci
Nov 28 '16 at 13:27

## 5 Answers

1. K-means is a reasonable approach and a sensible way to understand the data.

2. I've never used mahout, but I would use R or Python for this sort of analysis because of the nice libraries available to quickly implement K-means.

3. The clustering approach with the tags is fairly straightforward. You can essentially encode this using an indicator variable (also known as a binary encoding). You can set this variable/feature to 1 if the tag appeared in the list of tags and 0 otherwise. Then you only need to allocate space for the total number of tags that exist. If you have a large set of tags, you can limit them by taking tags with at least some frequency or some other "sensible" way.

4. You can choose $k$ in a number of ways. Typically people choose K arbitrarily because they want, e.g., 10 groups to segment their customers or data into. In the simulation I've provided, it'll give you a lame way to optimize for K using an incremental improvement.

I've made a notebook with a simulation walking you through how to "tokenize" your tags and represent them with a binary/one-hot encoding. It's worth noting that this tokenization ignores the order of the tags, which may be okay for your use case.

It's also worth noting that K-means certainly isn't the only way to measure the similarity of your data but I think it's a nice intuitive start.

Again, for choosing $k$ the approach outlined in the notebook is exhaustive, since it starts from 1 and goes until each observation is a cluster. This means you'll have to run K-means $n$ times, which is silly in practice to do but useful from a learning perspective here. In general, this isn't ideal because it's expensive and typically you don't want to set $k = n$ but this simulation gives nice intuition about what's happening.

In practice, you can just do it in gaps for a large number of clusters (e.g., 5, 10, 15, 20, .., 100) or something like that and choose the one that has the biggest drop-off by eye-balling it. This is a very arbitrary and unsatisfying way to choose $k$, but it seems to work okay for many people.

as already answered here, k-means in its original way won't be very effective, as Euclidean distances won't do the job with categorical data.

Some extensions exist (e.g. k-modes) or modifications with other distances (e.g. Gower). The discussion is expanded here.

I don't have a straight answer, but I suggest to look to the different possibilities already implemented and consider pros and cons of each one. Here you can find a lot of different methodologies that maybe can be adapted to your problem.

Hope it helps

If you are looking to cluster a very large amount of data located in a relational SQL or Hadoop type database you may want to use some of the algorithms built for parallel processing on Spark. The ML Lib main package for Spark can do this but I would recommend the H2O package as the documentation seems top notch, gives you a choice of many languages and can consume Terabytes of data quickly. If you already have a good development background this may play more to your engineering skill set and with H2O's great documentation you can focus more on your data pipeline, and feature selection than the theoretical underpinnings of your clustering model. You can implement H2O on Spark in Java or Scala as well staying with more of your engineering prospective, rather than working in a scripting language like R or Python.

Link to their K-means algorithm documentation

http://docs.h2o.ai/h2o/latest-stable/h2o-docs/data-science/k-means.html

K-means is neat strategy for these sort of problems. However you could also explore recent methods including topological data analyses to see clusters of features/individuals.

You first need to convert this data into some numerical representation, and then you can use clustering.

One of such ways is applying TF-IDF weighting to tags, and then calculate the cosine similarity between them and, finally, apply some hierarchical clustering to the results. Or you can encode the entire record (including category, sector, etc) in a similar way, and do the same thing afterwards.

Also, you can apply K-Means to these TF-IDF weights - but if dimensionality of this matrix is large, prior to that you may need to reduce it with SVD or something similar.

I wouldn't use Mahout for this and start with scikit-learn. You may want to have a look at these classes and methods:

• No you don't need to convert categorical to numerical. There are many well-known distance metrics for categorical data
– smci
Nov 28 '16 at 13:46
• @smci maybe then you could give your answer here as well? Nov 28 '16 at 14:33
• There are tons of good answers already for clustering categorical data on CrossValidated
– smci
Nov 28 '16 at 14:54
• why don't you point to one you think is exemplary Nov 28 '16 at 15:32
• If I could offhand, I would have already. The point is that it's perfectly acceptable to treat categorical data as categorical data, and that distance metrics exist. OP can do some reading and let us know what worked best.
– smci
Nov 28 '16 at 15:48