How are Random Forests not sensitive to outliers? I've read in a few sources, including this one, that Random Forests are not sensitive to outliers (in the way that Logistic Regression and other ML methods are, for example).
However, two pieces of intuition tell me otherwise:


*

*Whenever a decision tree is constructed, all of the points must be classified.  This means that even outliers will get classified, and hence will affect the decision trees where they were selected during boosting.

*Bootstrapping is a part of how a RandomForest does sub-sampling.  Bootstrapping is susceptible to outliers.
Is there any way to reconcile my intuition about its sensitivity to outliers, with sources that disagree?    
 A: Your intuition is correct. This answer merely illustrates it on an example. 
It is indeed a common misconception that CART/RF are somehow robust to outliers.
To illustrate the lack of robustness of RF to the presence of a single outliers, we can (lightly) modify the code used in Soren Havelund Welling's answer above to show that a single 'y'-outliers suffices to completely sway the fitted RF model. For example, if we compute the mean prediction error of the uncontaminated observations as a function of the distance between the outlier and the rest of the data, we can see (image below) that introducing a single outlier (by replacing one of the original observations by an arbitrary value on the 'y'-space) suffices to pull the predictions of the RF model arbitrarily far away from the values they would have had if computed on the original (uncontaminated) data:
 library(forestFloor)
library(randomForest)
library(rgl)
set.seed(1)

X = data.frame(replicate(2,runif(2000)-.5))
y = -sqrt((X[,1])^4+(X[,2])^4)
X[1,]=c(0,0);
y2<-y
rg<-randomForest(X,y)   #RF model fitted without the outlier
outlier<-rel_prediction_error<-rep(NA,10)

for(i in 1:10){
    y2[1]=100*i+2
    rf=randomForest(X,y2)   #RF model fitted with the outlier
    rel_prediction_error[i]<-mean(abs(rf$predict[-1]-y2[-1]))/mean(abs(rg$predict[-1]-y[-1]))
    outlier[i]<-y2[1]
}
plot(outlier,rel_prediction_error,type='l',ylab="Mean prediction error (on the uncontaminated observations) \\\ relative to the fit on clean data",xlab="Distance of the outlier")


How far? In the example above, the single outlier has changed the fit so much that the mean prediction error (on the uncontaminated) observations is now 1-2 orders of magnitude bigger than it would have been, had the model been fitted on the uncontaminated data.
So it is not true that a single outlier cannot affect the RF fit.
Furthermore, as I point out elsewhere, outliers are much harder to deal with when there are potentially several of them (though they don't need to be a large proportion of the data for their effects to show up). 
Of course, contaminated data can contain more than one outlier; to measure the impact of several outliers on the RF fit, compare the plot on the left obtained from the RF on the uncontaminated data to the plot on the right obtained by arbitrarily shifting 5% of the responses values (the code is below the answer).  


Finally, in the regression context, it is important to point out that outliers can stand out from the bulk of the data in both the design and response space (1). In the specific context of RF, design outliers will affect the estimation of the hyper-parameters. However, this second effect is more manifest when the number of dimension is large.     
What we observe here is a particular case of a more general result. The extreme sensitivity to outliers of multivariate data fitting methods based on convex loss functions has been rediscovered many times. See (2) for an illustration in the specific context of ML methods. 
Edit.
Fortunately, while the base CART/RF algorithm is emphatically not robust to outliers, it is possible (and quiet easy) to modify the procedure to impart it robustness to "y"-outliers. I will now focus on regression RF's (since this is more specifically the object of the OP's question). More precisely, writing the splitting criterion for an arbitrary node $t$ as:
$$s^∗=\arg\max_{s} [p_L \text{var}(t_L(s))+p_R\text{var}(t_R(s))]$$
where $t_L$ and $t_R$ are emerging child nodes dependent on the choice of $s^∗$ ( $t_L$ and $t_R$ are implicit functions of $s$) and 
 $p_L$ denotes the fraction of data that falls to the left child node $t_L$ and $p_R=1−p_L$ is the share of data in $t_R$. Then, one can impart "y"-space robustness to regression trees (and thus RF's) by replacing the variance functional used in the original definition by a robust alternative. This is in essence the approach used in (4) where the variance is replaced by a robust M-estimator of scale.


*

*(1)  Unmasking Multivariate Outliers and Leverage Points.
Peter J. Rousseeuw and Bert C. van Zomeren
Journal of the American Statistical Association
Vol. 85, No. 411 (Sep., 1990), pp. 633-639 

*(2) Random classification noise defeats all convex potential boosters.   Philip M. Long and      Rocco A. Servedio (2008). http://dl.acm.org/citation.cfm?id=1390233

*(3) C. Becker and U. Gather (1999). The Masking Breakdown Point of Multivariate Outlier Identification Rules.

*(4) Galimberti, G., Pillati, M., & Soffritti, G. (2007). Robust regression trees based on M-estimators.
Statistica, LXVII, 173–190.



    library(forestFloor)
    library(randomForest)
    library(rgl)
    set.seed(1)

    X<-data.frame(replicate(2,runif(2000)-.5))
    y<--sqrt((X[,1])^4+(X[,2])^4)
    Col<-fcol(X,1:2) #make colour pallete by x1 and x2
    #insert outlier2 and colour it black
    y2<-y;Col2<-Col
    y2[1:100]<-rnorm(100,200,1);    #outliers
    Col[1:100]="#000000FF" #black

    #plot training set
    plot3d(X[,1],X[,2],y,col=Col)
    rf=randomForest(X,y)    #RF on clean data
    rg=randomForest(X,y2)   #RF on contaminated data
    vec.plot(rg,X,1:2,col=Col,grid.lines=200)
    mean(abs(rf$predict[-c(1:100)]-y[-c(1:100)]))
    mean(abs(rg$predict[-c(1:100)]-y2[-c(1:100)]))

A: It is not the Random Forest algorithm itself that is robust to outliers, but the base learner it is based on: the decision tree. Decision trees isolate atypical observations into small leaves (i.e., small subspaces of the original space). Furthermore, decision trees are local models. Unlike linear regression, where the same equation holds for the entire space, a very simple model is fitted locally to each subspace (i.e., to each leaf). 


*

*In the case of regression, it is generally a very low-order
regression model (usually only the average of the observations in the
leaf).

*For classification, it is majority voting.


Therefore, for regression for instance, extreme values do not affect the entire model because they get averaged locally. So the fit to the other values is not affected.
Actually, this desirable property carries over to other tree-like structures, like dendograms. Hierarchical clustering, for instance, has long been used for data cleaning because it automatically isolates aberrant observations into small clusters. See for instance Loureiro et al. (2004). Outlier detection using clustering methods: a data cleaning application.
So, in a nutshell, RF inherits its insensitivity to outliers from recursive partitioning and local model fitting.
Note that decision trees are low bias but high variance models: their structure are prone to changing upon a small modification of the training set (removal or addition of a few observations). But this should not be mistaken with sensitivity to outliers, this is a different matter.
A: outlier 1a: This outlier has one or more extreme feature values and is placed distant to any other sample. The outlier will influence the initial splits of the trees as any other sample, so no strong influence. It will have low proximity to any other sample, and will only define the model structure in a remote part of feature space. During prediction most new samples are likely not to be similar to this outlier, and will rarely end up in the same terminal node. Moreover decision trees regards features as if they were ordinal(ranking). The value is either smaller/equal to or larger than break point, thus it does not matter if a feature value is an extreme outlier.
outlier 1b: For classification one single sample may be regarded as an outlier, when embedded in the middle of many sample of a different class. I described earlier how a default RF model will get influenced by this one sample of odd class, but only very close to the sample.
outlier 2: This outlier has an extreme target value perhaps many times higher than any other values, but the feature values are normal. A .631 fraction of the trees will have a terminal node with this sample. The model structure will get affected locally close to the outlier. Notice the model structure is affected mainly parallel to the feature axis, because nodes are split uni-variately.
I included a RF-regression simulation of outlier_2. 1999 points drawn from a smooth rounded structure $y=(x_1^4 + x_2^4 )^{\frac 1 2}$ and one outlier with a much higher target value(y=2, $x_1$=0,$x_2$=0). The training set is shown to the left. The learned RF model-structure is shown the the right.

library(forestFloor)
library(randomForest)
library(rgl)
set.seed(1)

X = data.frame(replicate(2,runif(2000)-.5))
y = -sqrt((X[,1])^4+(X[,2])^4)^1
Col = fcol(X,1:2) #make colour pallete by x1 and x2
#insert outlier2 and colour it black
X[1,] = c(0,0);y[1]=2 ;Col[1] = "#000000FF" #black

#plot training set
plot3d(X[,1],X[,2],y,col=Col)

rf = randomForest(X,y)
vec.plot(rf,X,1:2,col=Col,grid.lines = 400)

EDIT: comment to user603
Yes for extreme outliers on target scale, one should consider to transform target scale before running RF. I added below a robustModel() function which tweaks randomForest. Another solutions would be to log transform before training.
.
##---code by user603
library(forestFloor)
library(randomForest)
library(rgl)
set.seed(1)

X<-data.frame(replicate(2,runif(2000)-.5))
y<--sqrt((X[,1])^4+(X[,2])^4)
Col<-fcol(X,1:2) #make colour pallete by x1 and x2

#insert outlier2 and colour it black
y2<-y;Col2<-Col
y2[1:100]<-rnorm(100,200,1);    #outliers
Col2[1:100]="#000000FF" #black
##---

#function to make models robust
robustModel = function(model,keep.outliers=TRUE) {
  f = function(X,y,lim=c(0.1,.9),keep.outliers="dummy",...) {
  limits = quantile(y,lim)
  if(keep.outliers) {#keep but reduce outliers
  y[limits[1]>y] = limits[1] #lower limit
  y[limits[2]<y] = limits[2] #upper limit
  } else {#completely remove outliers
    thrashThese = mapply("||",limits[1]>y,limits[2]>y)
    y = y[thrashThese]
    X = X[thrashThese,]
  }
  obj = model(x=X,y=y,...)
  class(obj) = c("robustMod",class(obj))
  return(obj)
  }
  formals(f)$keep.outliers = keep.outliers
  return(f)
}

robustRF = robustModel(randomForest) #make RF robust
rh = robustRF(X,y2,sampsize=250)     #train robustRF
vec.plot(rh,X,1:2,col=Col2)          #plot model surface
mean(abs(rh$predict[-c(1:100)]-y2[-c(1:100)]))


