of these differences. Features which produce large values for this score are ranked as more important than features which produce small values. The statistical definition of the variable importance measure was given and analyzed by Zhu et al. This method of determining variable importance has some drawbacks. For data including categorical variables with different number of levels, random forests are biased in favor of those attributes with more levels. Methods such as partial permutations and growing unbiased trees can be used to solve the problem. If the data contain groups of correlated features of similar relevance for the output, then smaller groups are favored over larger groups. Relationship to nearest neighbors A relationship between random forests and the -nearest neighbor algorithm (-NN) was pointed out by Lin and Jeon in 2002. It turns out that both can be viewed as so-called weighted neighborhoods schemes. These are models built from a training set that make predictions for new points by looking at the "neighborhood" of the point, formalized by a weight function : Here, is the non-negative weight of the 'th training point relative to the new point in the same tree. For any particular , the weights for points must sum to one. Weight functions are given as follows: In -NN, the weights are if is one of the points closest to , and zero otherwise. In a tree, if is one of the points in the same leaf as , and zero otherwise. Since a forest averages the predictions of a set of trees with individual weight functions , its predictions are This shows that the whole forest is again a weighted neighborhood scheme, with weights that average those of the individual trees. The neighbors of in this interpretation are the points sharing the same leaf in any tree . In this way, the neighborhood of depends in a complex way on the structure of the trees, and thus on the structure of the training set. Lin and Jeon show that the shape of the neighborhood used by a random forest adapts to the local importance of each feature. Unsupervised learning with random forests As part of their construction, random forest predictors naturally lead to a dissimilarity measure among the observations. One can also define a random forest dissimilarity measure between unlabeled data: the idea is to construct a random forest predictor that distinguishes the "observed" data from suitably