29
$\begingroup$

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?
$\endgroup$
7
  • 3
    $\begingroup$ But I need it for unsupervised clustering, instead of supervised classification This key phrase alone is too brief and doesn't expain clearly what you want. Above it you described what seems to me to be a decision tree. Can you now give a similar passage about the algo you want? $\endgroup$
    – ttnphns
    Commented Jun 11, 2014 at 15:13
  • 1
    $\begingroup$ @ttnphns Hi, as you know, decision tree is a supervised method. You label each feature vector as Class1 or Class2. The algorithm determines the threshold for each feature based on the known labels. However, I am facing a clustering problem. I don't know the correct labels of each feature vector. I want to find an algorithm that automatically determines the threshold for each feature so as to construct a tree. This way, the resulting clustering can be easily interpreted as e.g. Cluster 1 : High A-Low B- Medium C- High D - Low E, Cluster 2 as Low A - High B- Medium C- Medium D - Low E. $\endgroup$
    – nan
    Commented Jun 11, 2014 at 16:53
  • 2
    $\begingroup$ @ttnphns I just found this paper, I think they did what i mean. ftp.cse.buffalo.edu/users/azhang/disc/disc01/cd1/out/papers/… $\endgroup$
    – nan
    Commented Jun 12, 2014 at 7:14
  • 2
    $\begingroup$ @nan have you found any implementation of such trees? They don't provide any link to code in the article $\endgroup$
    – Alleo
    Commented Jan 10, 2015 at 10:30
  • 1
    $\begingroup$ These papers can help you: 1. UNSUPERVISED CLASSIFICATION VIA DECISION TREES: AN INFORMATION-THEORETIC PERSPECTIVE (pdf); 2. Clustering Via Decision Tree Construction (pdf) $\endgroup$
    – Marta
    Commented May 5, 2016 at 8:40

4 Answers 4

19
$\begingroup$

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.

$\endgroup$
2
  • 3
    $\begingroup$ agree that this is "appropriate", but one would, of course, need to always bear in mind that creating a label from a clustering algorithm is not an "actual" feature of an observation. Depending on the quality & type of the clustering, the bias introduced will exist to a greater or lesser extent. $\endgroup$
    – NiuBiBang
    Commented Apr 22, 2016 at 17:20
  • $\begingroup$ Can you point me to a paper which discusses this strategy? $\endgroup$
    – nCessity
    Commented Jul 3, 2019 at 21:46
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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