6
$\begingroup$

I recently met some guys that employed CART (Classification and Regression Trees) for unsupervised learning. In particular for clustering.

The idea is very simple:

  • Make a copy of the original data;
  • Shuffle each column individually;
  • Label the original data as the positive class, and label shuffled data as the negative class;
  • Run CART on the new dataset.

If CART is able to distinguish between positive and negative records, it means that in the original dataset there are regions with high density: i.e. clusters.

There is just one minor detail we have to keep in mind. CART will not be able to find the initial split at the root node if the distribution between positive and negative class is the same for each feature. So, it is better to obtain the copy of our dataset (labelled with the negative class) with bootstrapping.


I ran an example: I generated a 2-dimensional dataset with 2 clusters. One is centred in [5,5] and the other one is centred in [15,15]:

enter image description here

Then I generated the shuffled copy (bootstrapped) of the data and labelled it with the negative class (red):

enter image description here

Now it is clear that with CART we can identify the original clusters by performing classification. This is an example in R:

library(rpart)
library("partykit")

treefit <- rpart(Class ~ X1 + X2, data = dataset)
plot(as.party(treefit))

enter image description here

In particular, Node 4, 8 and Node 11 identify our original clusters.


This technique looks very interesting to me because:

  1. It automatically identifies the number of clusters in the dataset;
  2. Each cluster is identified by cut-offs on the features, which makes the cluster interpretation easier.

My questions are: Is it a common technique in machine learning? Have you ever seen this technique before? Did anybody analyse its performance across different datasets? I could not find the original paper. I could only find this link from Salford-systems where they say that the original idea belongs to Breiman.

$\endgroup$
3
  • 1
    $\begingroup$ >> "it is better to obtain the copy of our dataset (labelled with the negative class) with bootstrapping" Is this your experience or do you have a source for that? Hastie et al. in their "ESL" book mention the initial split issue in Exercise 14.3. However, they do not give an answer. I wonder, what is the best solution: bootstrapping, subsampling, forced initial split (random or based on quantile)? Have you come across any analysis of this problem in the literature? Thanks. $\endgroup$ Commented Mar 21, 2023 at 21:21
  • 1
    $\begingroup$ Thanks @paperskilltrees I actually never saw the original literature for this approach. Finally, the ESL book! I remember seeing this at a presentation with no explanations. My comment above came from a practical issue: only doing random permutations of the values got CART stuck. Imagine the following example: two clusters (actually two data points) $(1,1)$ and $(2,2)$. If you create the negative class by permutations you end up with these two points: $(1,2)$ and $(2,1)$. This is dataset of 4 points is actually the XOR problem. We know that CART has problems with the first split with this. $\endgroup$
    – Simone
    Commented Mar 22, 2023 at 6:11
  • 1
    $\begingroup$ Bostrapping (after permutations) was working well because it would change slightly the distribution of the two classes. And CART would work. In the example above, by bootstrapping with might end up with e.g. $(1,1), (2,2), (1,1)$ for the positive class and $(2,1)$ for the negative (I guess you can do bootstrapping on top of all the dataset). CART would work in this case. As final analysis: I wouldn't force the initial split because it sounds like ad-hoc, and subsampling might work but bootstrapping keeps the right proportions between classes. Unfortunately I don't have any references for this. $\endgroup$
    – Simone
    Commented Mar 22, 2023 at 6:17

1 Answer 1

3
$\begingroup$

I think this will only work on toy data sets like this, and where there is plenty of dead space. It relies on a shuffled object $(x_1,y_2)$ being totally different than the real data.

Try the same on a toy data set with four clusters, at (5,5), (5,15), (15,5), (5,5) and it will no longer work. Clusters and dense areas exist, but your approach will fail on this data.

There exists a similar approach for measuring if two attributes are associated, though. I.e. a form of correlation between X and Y. If X and Y are independen, you cannot distinguish (X,Y) from a shuffled version (X,Y').

$\endgroup$
1
  • $\begingroup$ Yes, it looks really like how feature importance is computed in random forests. However, it is true that is seems more suited to find correlations rather than clusters. $\endgroup$
    – Simone
    Commented Oct 26, 2015 at 2:10

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.