Como as florestas aleatórias não são sensíveis aos valores extremos?

33

Eu li em algumas fontes, incluindo esta , que as florestas aleatórias não são sensíveis a outliers (da mesma forma que a regressão logística e outros métodos de ML são, por exemplo).

No entanto, duas intuições me dizem o contrário:

  1. Sempre que uma árvore de decisão é construída, todos os pontos devem ser classificados. Isso significa que mesmo os outliers serão classificados e, portanto, afetarão as árvores de decisão onde foram selecionadas durante o reforço.

  2. O bootstrapping é parte de como um RandomForest faz subamostragem. O bootstrapping é suscetível a outliers.

Existe alguma maneira de conciliar minha intuição sobre sua sensibilidade a valores extremos, com fontes que discordam?

Hunle
fonte
A resposta abaixo é muito boa. A resposta intuitiva é que uma árvore de decisão trabalha em divisões e as divisões não são sensíveis aos valores discrepantes: uma divisão deve cair apenas em qualquer lugar entre dois grupos de pontos para dividi-las.
Wayne
Então, suponho que, se min_samples_leaf_nodefor 1, pode ser suscetível a discrepâncias.
Hunle
sim min_samples e amostra de bootstrap pode remover completamente a influência de outliers 1b na regressão RF
Soren Havelund Welling
Alguns estatísticos obtêm uma visão de túnel sobre esses inliers, que se pode prever e entender. Aprecie os outliers como 'incógnitas conhecidas' e pergunte-se se o seu modelo de negócios é frágil em relação a eles. Alguns valores atípicos são fundamentalmente imprevisível, mas o seu impacto é muito real ... uma paráfrase de N. Taleb de, 'Black Swan'
Soren Havelund Welling

Respostas:

21

Sua intuição está correta. Esta resposta apenas ilustra isso em um exemplo.

De fato, é um equívoco comum que o CART / RF seja de alguma forma robusto em relação aos valores extremos.

Para ilustrar a falta de robustez do RF à presença de um único outliers, podemos (levemente) modificar o código usado na resposta de Soren Havelund Welling acima para mostrar que um único 'y'-outliers é suficiente para influenciar completamente o modelo de RF ajustado. Por exemplo, se calcularmos o erro médio de previsão das observações não contaminadas em função da distância entre o outlier e o restante dos dados, podemos ver (imagem abaixo) que apresenta um único outlier (substituindo uma das observações originais por um valor arbitrário no espaço 'y') é suficiente para afastar arbitrariamente as previsões do modelo de RF dos valores que eles teriam se calculados com base nos dados originais (não contaminados):

 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")

insira a descrição da imagem aqui

Quão longe? No exemplo acima, o único outlier mudou tanto o ajuste que as observações do erro médio de previsão (nas não contaminadas) agora são 1-2 ordens de magnitude maiores do que teriam sido, se o modelo tivesse sido ajustado nos dados não contaminados.

Portanto, não é verdade que um único erro não possa afetar o ajuste de RF.

Além disso, como aponto em outros lugares , os discrepantes são muito mais difíceis de lidar quando existem potencialmente vários deles (embora não precisem ser uma grande proporção dos dados para que seus efeitos apareçam). Obviamente, os dados contaminados podem conter mais de um erro externo; para medir o impacto de vários valores discrepantes no ajuste de RF, compare o gráfico à esquerda obtido do RF nos dados não contaminados com o gráfico à direita obtido deslocando arbitrariamente 5% dos valores das respostas (o código está abaixo da resposta) .

insira a descrição da imagem aqui insira a descrição da imagem aqui

Finalmente, no contexto da regressão, é importante ressaltar que os valores discrepantes podem se destacar da maior parte dos dados no espaço de design e resposta (1). No contexto específico da RF, os valores discrepantes do projeto afetarão a estimativa dos hiperparâmetros. No entanto, esse segundo efeito é mais manifesto quando o número de dimensões é grande.

O que observamos aqui é um caso particular de um resultado mais geral. A extrema sensibilidade aos valores extremos de métodos de ajuste de dados multivariados com base em funções de perda convexa foi redescoberta várias vezes. Veja (2) uma ilustração no contexto específico dos métodos de ML.

Editar.

Felizmente, embora o algoritmo CART / RF base não seja enfaticamente robusto para discrepantes, é possível (e silencioso e fácil) modificar o procedimento para conferir robustez aos discadores "y". Agora vou me concentrar nas RF de regressão (já que esse é mais especificamente o objeto da pergunta do OP). Mais precisamente, escrevendo o critério de divisão para um nó arbitrário como:t

s=argmaxs[pLvar(tL(s))+pRvar(tR(s))]

onde e estão criança que emerge nodos dependente da escolha de ( e são funções implícitas de ) e denota a fração de dados que cai para o nó filho esquerdo e é a parcela de dados em . Então, pode-se conferir robustez do espaço "y" a árvores de regressão (e, portanto, RFs) substituindo a funcionalidade de variância usada na definição original por uma alternativa robusta. Essa é, essencialmente, a abordagem usada em (4), onde a variação é substituída por um estimador M robusto de escala.tLtRstLtRspLtLpR=1pLtR

  • (1) Desmascaramento de outliers multivariados e pontos de alavancagem. Peter J. Rousseeuw e Bert C. van Zomeren Jornal da Associação Estatística Americana vol. 85, n. 411 (setembro de 1990), pp. 633-639
  • (2) O ruído de classificação aleatória derrota todos os potenciais impulsionadores convexos. Philip M. Long e Rocco A. Servedio (2008). http://dl.acm.org/citation.cfm?id=1390233
  • (3) C. Becker e U. Gather (1999). O ponto de decomposição do mascaramento das regras de identificação multivariada de outlier.
  • (4) Galimberti, G., Pillati, M. e Soffritti, G. (2007). Árvores de regressão robustas baseadas em estimadores-M. 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)]))
user603
fonte
Obrigado pela sua resposta detalhada. Se existem vários valores discrepantes no mesmo espaço de alta dimensão, ele questiona qual é o nosso critério para chamar de "discrepante"? Nesse caso, pergunto-me que hiper parâmetros podem ser definidos para que eu possa especificar algum tipo de critério para um outlier a priori?
Hunle
1
Eu adicionei meus comentários anteriores à minha resposta. Espero que agora faça um trabalho melhor ao responder sua pergunta!
usar o seguinte comando
1
Obrigado. O que são pe sna fórmula?
Hunle,
1
Por que os valores discrepantes combinados (1a + 2) são ruins? No seu exemplo, o modelo de RF se encaixa perfeitamente na estrutura de dados, 99,99% OOB MSE. A estrutura do modelo da área intermediária entre os dois clusters é bastante difícil, sim, e é mais um produto do modelo do que dos dados. Porém, nenhuma inferência e / ou previsões devem estar nessa área desconhecida, portanto isso não importa. A robustez absoluta em relação aos valores extremos é inevitavelmente ignorar possíveis eventos raros, mas talvez importantes. A maioria dos algos ML adotaria, por padrão, uma posição intermediária entre robustez e 'flexibilidade', mas pode ser aprimorada para aumentar a robustez.
Soren Havelund Welling
1
@ user603 Nada a acrescentar à discussão técnica, exceto que Heart of Darkness era meu livro favorito quando criança, com The Trial de Franz Kafka por um segundo (talvez fosse o primeiro se tivesse terminado e talvez escrito em inglês - então mais uma vez, talvez fosse adequado que não estivesse terminado). Eu realmente não pensei sobre isso do ponto de vista externo, além de considerar Heart of Darkness e The Trials como (bons) outliers entre o mar da "literatura séria" da BS, eu tinha que ler e fazer imagens BS-escuro-escuras e a análise semelhante em.
Mark L. Stone
11

outlier 1a: esse outlier possui um ou mais valores extremos de características e é colocado distante de qualquer outra amostra. O outlier influenciará as divisões iniciais das árvores como qualquer outra amostra, portanto, nenhuma influência forte. Ele terá pouca proximidade com qualquer outra amostra e definirá apenas a estrutura do modelo em uma parte remota do espaço de recurso. Durante a previsão, a maioria das amostras novas provavelmente não será semelhante a essa discrepância e raramente terminará no mesmo nó terminal. Além disso, as árvores de decisão consideram os recursos como se fossem ordinais (classificação). O valor é menor / igual ou maior que o ponto de interrupção, portanto, não importa se um valor de recurso é extremamente extremos.

outlier 1b: Para a classificação, uma única amostra pode ser considerada outlier, quando incorporada no meio de muitas amostras de uma classe diferente. Eu descrevi anteriormente como um modelo de RF padrão será influenciado por essa amostra de classe ímpar, mas apenas muito próxima da amostra.

outlier 2: esse outlier tem um valor-alvo extremo, talvez muitas vezes mais alto que quaisquer outros valores, mas os valores dos recursos são normais. Uma fração .631 das árvores terá um nó terminal com esta amostra. A estrutura do modelo será afetada localmente perto do outlier. Observe que a estrutura do modelo é afetada principalmente em paralelo ao eixo do recurso, porque os nós são divididos uni-variadamente.

Incluí uma simulação de regressão RF de outlier_2. 1999 pontos extraídos de uma estrutura arredondada suave e um valor externo com um valor-alvo muito mais alto (y = 2, = 0, = 0). O conjunto de treinamento é mostrado à esquerda. A estrutura do modelo de RF aprendida é mostrada à direita.y=(x14+x24)12x1x2

insira a descrição da imagem aqui

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: comentar para o usuário603

Sim, para valores extremos extremos na escala alvo, deve-se considerar transformar a escala alvo antes de executar a RF. Eu adicionei abaixo uma função robustModel () que ajusta randomForest. Outra solução seria registrar a transformação antes do treinamento.

.
##---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)]))

insira a descrição da imagem aqui

Soren Havelund Welling
fonte
Você escreve "nenhuma outra previsão será afetada". Se você mudar o valor único para fora, y[1]=200você verá que, sozinho, faz com que o erro de previsão nas observações não contaminadas salte por um fator de 20!
usar o seguinte comando
@ user603 É verdade que, nesses casos, a escala de destino pode ser transformada monotonicamente antes de ser entregue à RF. Eu adicionei um 'robustModel: torna os modelos robustos' à minha resposta ... claro que prever esses outlier (s) aleatórios de destino (tipo 2) permanece impossível, mas a estrutura restante do modelo não precisa sofrer
Soren Havelund Welling
A transformação Log não é , em geral, uma solução contra outliers (apenas oculta o problema). A robustez do RF que você propõe é essencialmente a abordagem defendida em Galimberti, G., Pillati, M. e Soffritti, G. (veja minha resposta). A principal diferença é que sua abordagem '' robustModel "tem um ponto de interrupção máximo de 25% no espaço de resposta (pode suportar 25% ou 'y' outliers arbitrários), enquanto a deles tem um bdp de 50%. é robusto para outliers no espaço de design
#
8

Não é o algoritmo Random Forest propriamente dito que é robusto para discrepantes, mas o aluno básico em que se baseia: a árvore de decisão . As árvores de decisão isolam observações atípicas em folhas pequenas (isto é, pequenos subespaços do espaço original). Além disso, as árvores de decisão são modelos locais . Diferentemente da regressão linear, onde a mesma equação se aplica a todo o espaço, um modelo muito simples é ajustado localmente em cada subespaço (isto é, em cada folha).

  • No caso de regressão, geralmente é um modelo de regressão de ordem muito baixa (geralmente apenas a média das observações na folha).
  • Para classificação, é votação majoritária.

Portanto, para regressão, por exemplo, valores extremos não afetam o modelo inteiro porque são calculados em média localmente. Portanto, o ajuste aos outros valores não é afetado.

Na verdade, essa propriedade desejável é transferida para outras estruturas semelhantes a árvores, como dendogramas. O cluster hierárquico, por exemplo, é usado há muito tempo para a limpeza de dados, porque isola automaticamente observações aberrantes em pequenos agrupamentos. Veja, por exemplo, Loureiro et al. (2004). Detecção de outlier usando métodos de cluster: um aplicativo de limpeza de dados .

Portanto, em poucas palavras, o RF herda sua insensibilidade a outliers do particionamento recursivo e do ajuste do modelo local .

Observe que as árvores de decisão têm baixa tendência, mas são modelos de alta variação: sua estrutura está sujeita a alterações mediante uma pequena modificação no conjunto de treinamento (remoção ou adição de algumas observações). Mas isso não deve ser confundido com sensibilidade a valores extremos, isso é uma questão diferente.

Antoine
fonte
Na verdade, considerei usar um método de agrupamento, como você sugere, para a detecção de valores discrepantes. Mas não tenho certeza de onde aplicar o cluster. Deve ser aplicado labeledou unlabeleddados? E como esse agrupamento seria alcançado com dados heterogêneos que contêm recursos categóricos e numéricos?
Hunle