4
$\begingroup$

I am having some issues understanding how unsupervised Random Forest works according to Breiman. I only have unlabeled data, so the thought arose to use unsupervised Random Forest and use the resulting dissimilarity matrix as input for a cluster algorithm. One "constraint" is that I have to use Weka.

Can someone explain to me how exactly I have to understand the usage of original and synthetic data? As I understand it right now I have to:

  • artificially add a class attribute with a value of, e.g., "0" for the original data
  • make a randomized copy of the original data resulting in the synthetic data and add a class attribute with a value of, e.g., "1"

Questions:

  1. Did I understand it correctly?
  2. What am I supposed to do next?
  3. Do I have to join these two data sets? Isn't that highly impractical for a, say, very large dataset, as I have to store the whole data while running it with Weka?
  4. How do I get the resulting dissimilarity matrix in Weka?

I'm a little confused right now...

$\endgroup$
5
$\begingroup$

I do not use Weka, but I will try to explain how things works, and I hope you will find the way to do that in Weka.

Transform the unsupervised into a supervised problem

So RF knows only supervised learning. However, in order to do unsupervised learning you have to set up your problem as a supervised learning one. In order to transform you problem into a supervised one you create a new data made from original data set and a synthetic one. Also you need a new feature, a target feature which is a binary nominal variable. You set with one label the original observations, with the other labels the synthetic observations.

Now, the train you will use is made from the reunion of both original and synthetic data set. To create a synthetic data set there are a multiple algorithms. The most popular one is to create a synthetic data set with the same number of instances as the original, and with the same features. The values from the features are drawn randomly for each feature separately, in an independent way.

Suppose you have two features: $x_1$ a continuous variable which comes from a $Normal(0, 1)$ and $x_2$ a nominal binary feature, having sample probabilities for labels like $p[male]=0.4$ and $p[female]=0.6$. Your new synthetic instances will draw randomly for $x_1$ a value from all the values of the original data, and for $x_2$ a value from Bernoulli with according probabilities.

Another approach is to estimate the real distributions of the variables and draw sample values from these distributions.

Pay attention that the random drawings are independent.

There are 2 reasons why this is done in RF: 1. Using randomization one can study how a variable is important for predictions. 2. The variables are de-correlated.

Now your training data set is created by simply joining the instances of those 2 data sets.

Use additional features of RF to create distance matrix

Among other things, RF has a feature which is called proximities. A proximity matrix is a matrix with $N$ columns and $N$ rows, where $N$ is the number of instances. This matrix collects information about how instances ends up being in the same terminal node. Basically, while learning, RF builds trees. For each tree, and for each terminal node, add 1 to the proximity matrix for each instance $i$ and instance $j$ from the terminal node.

Now you are not interested into distances which involves the synthetic data set. So you have to reduce the original proximity matrix, by eliminating all the rows and all the columns for synthetic instances.

In the end divide all elements from the proximity matrix with the number of trees, set up with $1$ all elements from diagonal $proximity[i][i]=1$, and you have a proximity matrix.

Now for clustering you need a distance. The used way to transform from proximity to a distance is to transform each element of the proximity matrix with $proximity[i][j] = \sqrt{(1-proximity[i][j])}$. Now you have a distance matrix for instances of the original data set.

Clustering original data using the RF distances

This step is straight-forward. There are many clustering algorithms and usually this algorithms needs a distance function. This distance function can be also given usually in the form of a distance matrix since you are interested only in clustering the instances from a limited data set.

Additional note

I do not know what happens for large data sets, since the distance matrix can be prohibitive. There are some implementations which are able to reduce the memory consumption, but I have no idea how these works.

$\endgroup$
  • $\begingroup$ Thanks for your answer! I'm still a bit confused about the synthetic data set. Are the values from the features drawn randomly with or without replacement? $\endgroup$ – Lex88 Apr 8 '14 at 13:48
  • $\begingroup$ Weka does a shuffle on each column, which mean without replacement. Intuitively, I would prefer a bootstrap (with replacement) since we are talking about RF which leverage the induced randomization, but I do not have arguments to support that. $\endgroup$ – rapaio Apr 8 '14 at 17:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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