Is there a decision-tree-like algorithm for unsupervised clustering?

Question

I have a dataset consists of 5 features : A, B, C, D, E. They are all numeric values. Instead of doing a density-based clustering, what I want to do is to cluster the data in a decision-tree-like manner.

The approach I mean is something like this:

The algorithm may divide the data into X initial clusters based on feature C, i.e. the X clusters may have small C, medium C, large C and very large C values etc. Next, under each of the X cluster nodes, the algorithm further divide the data into Y clusters based on feature A. The algorithm continues until all the features are used.

The algorithm that I described above is like a decision-tree algorithm. But I need it for unsupervised clustering, instead of supervised classification.

My questions are the following:

1. Do such algorithms already exists? What is the correct name for such algorithm
2. Is there a R/python package/library which has an implementation of this kind of algorithms?

Answer 1

You may want to consider the following approach:

• Use any clustering algorithm that is adequate for your data
• Assume the resulting cluster are classes
• Train a decision tree on the clusters

This will allow you to try different clustering algorithms, but you will get a decision tree approximation for each of them.

Answer 2

The first paper that comes to mind is this: Clustering Via Decision Tree Construction https://pdfs.semanticscholar.org/8996/148e8f0b34308e2d22f78ff89bf1f038d1d6.pdf

As another mentioned, "hierarchical" (top down) and "hierarchical agglomeration" (bottom up) are both well known techniques devised using trees to do clustering. Scipy has this.

If you are ok with custom code because I don't know of any library, there are two techniques I can recommend. Be warned that these are not technically clustering because of the mechanics they rely on. You might call this pseudo clustering.

1) Supervised: This is somewhat similar to the paper (worth reading). Build a single decision tree model to learn some target (you decide what makes sense). The target could be a randomly generated column (requires repeating and evaluating what iteration was best, see below). Define each full path of the tree as a "cluster" since points that fall through that series of branches are technically similar in regards to the target. This only works well on some problems, but it's efficient at large scale. You end up with K clusters (see below).

2) Semisupervised (sort of unsupervised, but mechanically supervised), using #1: you can try building trees to predict columns in a leave one out pattern. i.e. if the schema is [A,B,C], build 3 models [A,B] -> C, [A,C] -> B, [B,C]->A. You get KN clusters (see below). N=len(schema). If some of these features are not interesting or too imbalanced (in the case of categories), don't use them as targets.

Summary: The model will select features in order based on information or purity and clusters will be based on just a few features rather than all. There is no concept of distance in these clusters, but you could certainly devise one based on the centers.

Pros: easy to understand and explain, quick training and inference, works well with few strong features, works with categories. When your features are in essence heterogeneous and you have many features, you don't have to spend as much time deciding which to use in the distance function.

Cons: not standard, must be written, naive bias, collinearity with target causes bad results, having 1000 equally important features will not work well (KMeans with Euclidean distance is better here).

How many clusters do you get? You must, absolutely must restrict the DT model to not grow too much. e.g. Set min samples per leaf, max leaf nodes (preferred), or max depth. Optionally, set purity or entropy constraints. You must check how many clusters this gave you and evaluate if this method is better than real clustering.

Did the techniques and parameters work well for you? Which was best? To find out, you need to do cluster evaluation: Performance metrics to evaluate unsupervised learning

Answer 3

What you're looking for is a divisive clustering algorithm.

Most common algorithms are agglomerative, which cluster the data in a bottom up manner - each observation starts as its own cluster and clusters get merged. Divisive clustering is top down - observations start in one cluster which is gradually divided.

The desire to look like a decision tree limits the choices as most algorithms operate on distances within the complete data space rather than splitting one variable at a time.

DIANA is the only divisive clustering algorithm I know of, and I think it is structured like a decision tree. I would be amazed if there aren't others out there.

You could use a standard decision tree algorithm if you modify the splitting rule to a metric that does not consider a defined dependent variable, but rather uses a cluster goodness metric.

Answer 4

One idea to consider is let suppose you have k features and n points. You can build random trees using (k-1) feature and 1 feature as a dependent variable. Y. You can select a height h after which you will have data points in roots. You can take voting kind of different trees. Just a thought.