What are the votes in R's unsupervised random Forest?

Question

I’m trying to better understand unsupervised random forests. An important part of understanding unsupervised random forests is being able to assess how good / appropriate a given forest is. For instance Breiman's page on unsupervised forests says:

If the oob misclassification rate in the two-class problem is, say, 40% or more, it implies that the x -variables look too much like independent variables to random forests. The dependencies do not have a large role and not much discrimination is taking place. If the misclassification rate is lower, then the dependencies are playing an important role.

However, the R implementation does not return a misclassification rate in such an unsupervised forest. It does however return a ‘votes’ component which, in the supervised case, can be readily translated into a confusion matrix and a misclassification rate. The thought is that examining this votes component should help understand the misclassification in the unsupervised forest. However, I’m confused as to what these votes actually represent.

My understanding is that, in the unsupervised case, classification is being done between the actual data and a randomised dataset something like this:

set.seed(23)
require(dplyr)
require(randomForest)
n      <- nrow(iris)
irisBS <- mutate_each(iris,funs(sample(.,replace=TRUE)))
y      <- factor(c(rep(1, n), rep(2, n)))
rfPU   <- randomForest(x=rbind(iris,irisBS), y=y)

As expected, this returns a votes component with twice the number of rows of the original data (iris):

n
# [1] 150
nrow(rfPU$votes)
# [1] 300

However, the actual unsupervised forest returns a votes component with the same number of rows as the original data:

set.seed(23)
rfU <- randomForest(x=iris)
nrow(rfPU$votes)
# [1] 150

The question is then what these represent. The total votes for class two in the actual unsupervised forest are somewhere between those in my pseudo-unsupervised version above when either the correct or incorrect classification is considered:

sum(rfU$votes[,2])
# [1] 87.12367
sum(rfPU$votes[1:n,2])
# [1] 24.34562
sum(rfPU$votes[(n+1):(2*n),2])
# [1] 119.3299

That is, the value from the unsupervised forest is somewhat above the midpoint of the two other values, but it’s not obvious to me what’s going on. Doing all this many times suggests this is representative.

Answer 1

Reading from here we confirm your understanding of unsupervised Breiman's Random Forests.

Unsupervised learning

In unsupervised learning the data consist of a set of x -vectors of the same dimension with no class labels or response variables. There is no figure of merit to optimize, leaving the field open to ambiguous conclusions. The usual goal is to cluster the data - to see if it falls into different piles, each of which can be assigned some meaning.

The approach in random forests is to consider the original data as class 1 and to create a synthetic second class of the same size that will be labeled as class 2. The synthetic second class is created by sampling at random from the univariate distributions of the original data. Here is how a single member of class two is created - the first coordinate is sampled from the N values {x(1,n)}. The second coordinate is sampled independently from the N values {x(2,n)}, and so forth.

Thus, class two has the distribution of independent random variables, each one having the same univariate distribution as the corresponding variable in the original data. Class 2 thus destroys the dependency structure in the original data. But now, there are two classes and this artificial two-class problem can be run through random forests. This allows all of the random forests options to be applied to the original unlabeled data set.

If the oob misclassification rate in the two-class problem is, say, 40% or more, it implies that the x -variables look too much like independent variables to random forests. The dependencies do not have a large role and not much discrimination is taking place. If the misclassification rate is lower, then the dependencies are playing an important role.

Formulating it as a two class problem has a number of payoffs. Missing values can be replaced effectively. Outliers can be found. Variable importance can be measured. Scaling can be performed (in this case, if the original data had labels, the unsupervised scaling often retains the structure of the original scaling). But the most important payoff is the possibility of clustering.

The reason the total number of votes is the number of "true" samples (class 1) is simply due to the fact that there's no reason to return votes for "fake" samples (class 2). These are random and their probability density function is entirely known.

Compare the distributions of vote in both yours PU and U models:

png("unsupervisedRF.png")
par(mfrow = c(1,2), mar = c(5.1, 3.6, 4.1, 1.6))
boxplot(rfPU$votes[1:150,], names = c("PU-1","PU-2"), col = c("green","red"))
boxplot(rfU$votes, names = c("U-1","U-2"), col = c("green","red"))
dev.off()