Forêt aléatoire

Les forêts aléatoires ou forêts de décision aléatoires sont une méthode d’ apprentissage d’ensemble pour la classification , la régression et d’autres tâches qui fonctionnent en construisant une multitude d’ arbres de décision au moment de la formation. Pour les tâches de classification, la sortie de la forêt aléatoire est la classe sélectionnée par la plupart des arbres. Pour les tâches de régression, la prédiction moyenne ou moyenne des arbres individuels est renvoyée. ^{[1] [2]} Les forêts de décision aléatoires corrigent l’habitude des arbres de décision de s’adapter à leur ensemble d’entraînement . ^{[3] : 587–588} Les forêts aléatoires surpassent généralement les arbres de décision, mais leur précision est inférieure à celle des arbres à gradient boosté ^{[ citation nécessaire ]} . Cependant, les caractéristiques des données peuvent affecter leurs performances. ^{[4] [5]}

Schéma d’une forêt de décision aléatoire

Le premier algorithme pour les forêts de décision aléatoire a été créé en 1995 par Tin Kam Ho ^[1] en utilisant la méthode du sous-espace aléatoire , ^[2] qui, dans la formulation de Ho, est un moyen de mettre en œuvre l’approche de “discrimination stochastique” de la classification proposée par Eugene Kleinberg . ^{[6] [7] [8]}

Une extension de l’algorithme a été développée par Leo Breiman ^[9] et Adele Cutler , ^[10] qui ont enregistré ^[11] “Random Forests” en tant que marque en 2006 (à partir de 2019 ^{[mettre à jour]}, propriété de Minitab, Inc. ). ^[12] L’extension combine l’idée de ” bagging ” de Breiman et la sélection aléatoire de caractéristiques, introduites d’abord par Ho ^[1] et plus tard indépendamment par Amit et Geman ^[13] afin de construire une collection d’arbres de décision à variance contrôlée.

Les forêts aléatoires sont fréquemment utilisées comme modèles de “boîte noire” dans les entreprises, car elles génèrent des prédictions raisonnables sur une large gamme de données tout en nécessitant peu de configuration.

Histoire

La méthode générale des forêts de décision aléatoires a été proposée pour la première fois par Ho en 1995. ^[1] Ho a établi que les forêts d’arbres se séparant avec des hyperplans obliques peuvent gagner en précision à mesure qu’elles grandissent sans souffrir de surentraînement, tant que les forêts sont restreintes au hasard pour être sensibles. aux seules cotes de fonction sélectionnées. Un travail ultérieur dans le même sens ^[2]ont conclu que d’autres méthodes de fractionnement se comportent de la même manière, tant qu’elles sont forcées au hasard d’être insensibles à certaines dimensions des caractéristiques. Notez que cette observation d’un classificateur plus complexe (une forêt plus grande) devenant plus précise de manière presque monotone contraste fortement avec la croyance commune selon laquelle la complexité d’un classificateur ne peut atteindre qu’un certain niveau de précision avant d’être affectée par un surajustement. L’explication de la résistance de la méthode forestière au surentraînement peut être trouvée dans la théorie de la discrimination stochastique de Kleinberg. ^{[6] [7] [8]}

Le développement précoce de la notion de forêts aléatoires de Breiman a été influencé par les travaux d’Amit et Geman ^[13] qui ont introduit l’idée de rechercher un sous-ensemble aléatoire des décisions disponibles lors de la division d’un nœud, dans le contexte de la croissance d’un seul arbre . L’idée de la sélection aléatoire de sous-espaces de Ho ^[2] a également eu une influence sur la conception des forêts aléatoires. Dans cette méthode, une forêt d’arbres est développée et une variation entre les arbres est introduite en projetant les données d’apprentissage dans un sous-espace choisi au hasard avant d’ajuster chaque arbre ou chaque nœud. Enfin, l’idée d’optimisation de nœud aléatoire, où la décision à chaque nœud est sélectionnée par une procédure aléatoire, plutôt qu’une optimisation déterministe, a été introduite pour la première fois parThomas G. Dietterich . ^[14]

L’introduction appropriée des forêts aléatoires a été faite dans un article de Leo Breiman . ^[9] Cet article décrit une méthode de construction d’une forêt d’arbres non corrélés à l’aide d’une procédure de type CART , combinée à une optimisation et un ensachage de nœuds aléatoires . De plus, cet article combine plusieurs ingrédients, certains déjà connus et d’autres nouveaux, qui forment la base de la pratique moderne des forêts aléatoires, en particulier :

1. Utilisation de l’erreur hors sac comme estimation de l’ erreur de généralisation .
2. Mesurer l’importance des variables par permutation.

Le rapport propose également le premier résultat théorique pour les forêts aléatoires sous la forme d’une borne sur l’ erreur de généralisation qui dépend de la force des arbres dans la forêt et de leur corrélation .

Algorithme

Préliminaires : apprentissage de l’arbre de décision

Les arbres de décision sont une méthode populaire pour diverses tâches d’apprentissage automatique. L’apprentissage par arbre “se rapproche le plus des exigences pour servir de procédure prête à l’emploi pour l’exploration de données”, déclarent Hastie et al. , “parce qu’il est invariant sous la mise à l’échelle et diverses autres transformations de valeurs de caractéristiques, est robuste à l’inclusion de caractéristiques non pertinentes et produit des modèles inspectables. Cependant, ils sont rarement précis”. ^{[3] : 352}

En particulier, les arbres qui poussent très profondément ont tendance à apprendre des modèles très irréguliers : ils surajustent leurs ensembles d’apprentissage, c’est-à-dire qu’ils ont un faible biais, mais une variance très élevée . Les forêts aléatoires sont un moyen de faire la moyenne de plusieurs arbres de décision profonds, entraînés sur différentes parties du même ensemble d’entraînement, dans le but de réduire la variance. ^{[3] : 587–588} Cela se fait au prix d’une légère augmentation du biais et d’une certaine perte d’interprétabilité, mais améliore généralement considérablement les performances du modèle final.

Les forêts sont comme le rassemblement des efforts d’algorithme d’arbre de décision. Prendre le travail d’équipe de nombreux arbres améliorant ainsi les performances d’un seul arbre aléatoire. Bien que pas tout à fait similaires, les forêts donnent les effets d’une validation croisée K-fold.

Ensachage

L’algorithme de formation pour les forêts aléatoires applique la technique générale d’ agrégation bootstrap , ou bagging, aux apprenants d’arbres. Étant donné un ensemble d’apprentissage X = x ₁ , …, x _n avec des réponses Y = y ₁ , …, y _n , l’ensachage à plusieurs reprises ( B fois) sélectionne un échantillon aléatoire avec remplacement de l’ensemble d’apprentissage et ajuste les arbres à ceux-ci échantillons :

Pour b = 1, …, B :

1. Echantillon, avec remplacement, n exemples d’apprentissage de X , Y ; appelez-les X _b , Y _b .
2. Former un arbre de classification ou de régression f _b sur X _b , Y _b .

Après la formation, les prédictions pour les échantillons invisibles x’ peuvent être faites en faisant la moyenne des prédictions de tous les arbres de régression individuels sur x’ :

F ^ = 1 B ∑ b = 1 B f b ( x ′ ) {displaystyle {hat {f}}={frac {1}{B}}sum _{b=1}^{B}f_{b}(x’)}

ou en prenant le vote à la majorité dans le cas des arbres de classification.

Cette procédure d’amorçage conduit à de meilleures performances du modèle car elle diminue la variance du modèle, sans augmenter le biais. Cela signifie que si les prédictions d’un seul arbre sont très sensibles au bruit dans son ensemble d’apprentissage, la moyenne de nombreux arbres ne l’est pas, tant que les arbres ne sont pas corrélés. Former simplement de nombreux arbres sur un seul ensemble d’apprentissage donnerait des arbres fortement corrélés (ou même le même arbre plusieurs fois, si l’algorithme d’apprentissage est déterministe); L’échantillonnage bootstrap est un moyen de décorréler les arbres en leur montrant différents ensembles d’apprentissage.

De plus, une estimation de l’incertitude de la prédiction peut être faite comme l’écart type des prédictions de tous les arbres de régression individuels sur x’ :

σ = ∑ b = 1 B ( f b ( x ′ ) − f ^ ) 2 B − 1 . {displaystyle sigma ={sqrt {frac {sum _{b=1}^{B}(f_{b}(x’)-{hat {f}})^{2}}{B -1}}}.}

Le nombre d’échantillons/arbres, B , est un paramètre libre. En règle générale, quelques centaines à plusieurs milliers d’arbres sont utilisés, selon la taille et la nature de l’ensemble d’apprentissage. Un nombre optimal d’arbres B peut être trouvé en utilisant la validation croisée ou en observant l’ erreur hors sac : l’erreur de prédiction moyenne sur chaque échantillon d’apprentissage x _i , en utilisant uniquement les arbres qui n’avaient pas x _i dans leur échantillon bootstrap . ^[15] L’erreur de formation et de test a tendance à se stabiliser après qu’un certain nombre d’arbres ont été ajustés.

De l’ensachage aux forêts aléatoires

La procédure ci-dessus décrit l’algorithme d’ensachage original pour les arbres. Les forêts aléatoires incluent également un autre type de schéma de mise en sac : elles utilisent un algorithme d’apprentissage d’arbre modifié qui sélectionne, à chaque division candidate dans le processus d’apprentissage, un sous-ensemble aléatoire des caractéristiques . Ce processus est parfois appelé « feature bagging ». La raison en est la corrélation des arbres dans un échantillon bootstrap ordinaire : si une ou quelques caractéristiques sont des prédicteurs très forts pour la variable de réponse (sortie cible), ces caractéristiques seront sélectionnées dans de nombreux arbres B , les obligeant à devenir corrélés. Une analyse de la façon dont le bagging et la projection de sous-espace aléatoire contribuent aux gains de précision dans différentes conditions est donnée par Ho. ^[16]

Typiquement, pour un problème de classification avec p caractéristiques, √ p caractéristiques (arrondi vers le bas) sont utilisées dans chaque fractionnement. ^{[3] : 592} Pour les problèmes de régression, les inventeurs recommandent p/3 (arrondi à l’inférieur) avec une taille de nœud minimale de 5 par défaut. ^{[3] : 592} En pratique, les meilleures valeurs pour ces paramètres dépendront du problème, et ils doivent être traités comme des paramètres de réglage. ^{[3] : 592}

Arbres supplémentaires

L’ajout d’une étape supplémentaire de randomisation donne des arbres extrêmement randomisés , ou ExtraTrees. Bien que similaires aux forêts aléatoires ordinaires en ce sens qu’elles constituent un ensemble d’arbres individuels, il existe deux différences principales : premièrement, chaque arbre est formé en utilisant l’ensemble de l’échantillon d’apprentissage (plutôt qu’un échantillon bootstrap), et deuxièmement, la division descendante dans l’arbre apprenant est randomisé. Au lieu de calculer le point de coupure optimal localement pour chaque caractéristique considérée (sur la base, par exemple, du gain d’information ou de l’ impureté de Gini ), unpoint de coupure est sélectionné. Cette valeur est sélectionnée à partir d’une distribution uniforme dans la plage empirique de la fonctionnalité (dans l’ensemble d’apprentissage de l’arbre). Ensuite, parmi toutes les divisions générées aléatoirement, la division qui donne le score le plus élevé est choisie pour diviser le nœud. Semblable aux forêts aléatoires ordinaires, le nombre d’entités sélectionnées au hasard à prendre en compte à chaque nœud peut être spécifié. Les valeurs par défaut de ce paramètre sont p {displaystyle {sqrt {p}}} pour le classement et p {displaystyle p} pour la régression, où p {displaystyle p} est le nombre de caractéristiques du modèle. ^[17]

Propriétés

Importance variable

Les forêts aléatoires peuvent être utilisées pour classer l’importance des variables dans un problème de régression ou de classification de manière naturelle. La technique suivante a été décrite dans l’article original de Breiman ^[9] et est implémentée dans le package R randomForest . ^[dix]

La première étape pour mesurer l’importance de la variable dans un ensemble de données D n = { ( X i , Y i ) } i = 1 n {displaystyle {mathcal {D}}_{n}={(X_{i},Y_{i})}_{i=1}^{n}} consiste à ajuster une forêt aléatoire aux données. Pendant le processus d’ajustement, l’ erreur hors sac pour chaque point de données est enregistrée et moyennée sur la forêt (les erreurs sur un ensemble de test indépendant peuvent être remplacées si l’ensachage n’est pas utilisé pendant la formation).

Pour mesurer l’importance de la j {displaystyle j} -ème caractéristique après entraînement, les valeurs de la j {displaystyle j} -ième caractéristique sont permutées parmi les données d’apprentissage et l’erreur de sortie de sac est à nouveau calculée sur cet ensemble de données perturbées. Le score d’importance pour le j {displaystyle j} -ième caractéristique est calculée en faisant la moyenne de la différence d’erreur hors sac avant et après la permutation sur tous les arbres. Le score est normalisé par l’écart type de ces différences.

Les caractéristiques qui produisent de grandes valeurs pour ce score sont classées comme plus importantes que les caractéristiques qui produisent de petites valeurs. La définition statistique de la mesure d’importance variable a été donnée et analysée par Zhu et al. ^[18]

Cette méthode de détermination de l’importance des variables présente certains inconvénients. Pour les données comprenant des variables catégorielles avec un nombre différent de niveaux, les forêts aléatoires sont biaisées en faveur des attributs avec plus de niveaux. Des méthodes telles que les permutations partielles ^{[19] [20] [4]} et la croissance d’arbres non biaisés ^{[21] [22]} peuvent être utilisées pour résoudre le problème. Si les données contiennent des groupes de caractéristiques corrélées de pertinence similaire pour la sortie, les groupes plus petits sont favorisés par rapport aux groupes plus grands. ^[23]

Relation avec les voisins les plus proches

Une relation entre les forêts aléatoires et l’ algorithme du k – plus proche voisin ( k -NN) a été soulignée par Lin et Jeon en 2002. ^[24] Il s’avère que les deux peuvent être considérés comme des schémas de voisinages pondérés . Ce sont des modèles construits à partir d’un ensemble d’entraînement { ( x i , y i ) } i = 1 n {displaystyle {(x_{i},y_{i})}_{i=1}^{n}} qui font des pronostics y ^ {displaystyle {chapeau {y}}} pour les nouveaux points x’ en regardant le “voisinage” du point, formalisé par une fonction de poids W :

y ^ = ∑ i = 1 n W ( x i , x ′ ) y i . {displaystyle {hat {y}}=sum _{i=1}^{n}W(x_{i},x’),y_{i}.}

Ici, W ( x i , x ′ ) {displaystyle W(x_{i},x’)} est le poids non négatif du i’ième point d’apprentissage par rapport au nouveau point x’ dans le même arbre. Pour tout x’ particulier , les poids des points x i {displaystyle x_{i}} doit totaliser un. Les fonctions de poids sont données comme suit :

• Dans k -NN, les poids sont W ( x i , x ′ ) = 1 k {displaystyle W(x_{i},x’)={frac {1}{k}}} si x _i est l’un des k points les plus proches de x’ , et zéro sinon.
• Dans un arbre, W ( x i , x ′ ) = 1 k ′ {displaystyle W(x_{i},x’)={frac {1}{k’}}} si x _i est un des k’ points de la même feuille que x’ , et zéro sinon.

Puisqu’une forêt fait la moyenne des prédictions d’un ensemble de m arbres avec des fonctions de poids individuelles W j {displaystyle W_{j}} , ses prédictions sont

y ^ = 1 m ∑ j = 1 m ∑ i = 1 n W j ( x i , x ′ ) y i = ∑ i = 1 n ( 1 m ∑ j = 1 m W j ( x i , x ′ ) ) y i . {displaystyle {hat {y}}={frac {1}{m}}sum _{j=1}^{m}sum _{i=1}^{n}W_{j}( x_{i},x’),y_{i}=sum _{i=1}^{n}left({frac {1}{m}}sum _{j=1}^{ m}W_{j}(x_{i},x’)droite),y_{i}.}

Cela montre que la forêt entière est à nouveau un schéma de voisinage pondéré, avec des poids qui font la moyenne de ceux des arbres individuels. Les voisins de x’ dans cette interprétation sont les points x i {displaystyle x_{i}} partageant la même feuille dans n’importe quel arbre j {displaystyle j} . Ainsi, le voisinage de x’ dépend de manière complexe de la structure des arbres, et donc de la structure de l’ensemble d’apprentissage. Lin et Jeon montrent que la forme du voisinage utilisé par une forêt aléatoire s’adapte à l’importance locale de chaque élément. ^[24]

Apprentissage non supervisé avec des forêts aléatoires

Dans le cadre de leur construction, les prédicteurs forestiers aléatoires conduisent naturellement à une mesure de dissemblance entre les observations. On peut également définir une mesure de dissimilitude forestière aléatoire entre des données non étiquetées : l’idée est de construire un prédicteur forestier aléatoire qui distingue les données « observées » des données synthétiques convenablement générées. ^{[9] [25]}Les données observées sont les données originales non étiquetées et les données synthétiques sont tirées d’une distribution de référence. Une dissemblance de forêt aléatoire peut être attrayante car elle gère très bien les types de variables mixtes, est invariante aux transformations monotones des variables d’entrée et est robuste aux observations aberrantes. La dissimilitude de la forêt aléatoire traite facilement un grand nombre de variables semi-continues en raison de sa sélection intrinsèque de variables ; par exemple, la dissimilitude de forêt aléatoire “Addcl 1” pondère la contribution de chaque variable en fonction de sa dépendance vis-à-vis des autres variables. La dissimilarité aléatoire de la forêt a été utilisée dans diverses applications, par exemple pour trouver des groupes de patients sur la base de données de marqueurs tissulaires. ^[26]

Variantes

Au lieu d’arbres de décision, des modèles linéaires ont été proposés et évalués comme estimateurs de base dans les forêts aléatoires, en particulier la régression logistique multinomiale et les classificateurs naïfs de Bayes . ^{[5] [27] [28]} Dans les cas où la relation entre les prédicteurs et la variable cible est linéaire, les apprenants de base peuvent avoir une précision aussi élevée que l’apprenant d’ensemble. ^{[29] [5]}

Forêt aléatoire du noyau

Dans l’apprentissage automatique, les forêts aléatoires du noyau (KeRF) établissent le lien entre les forêts aléatoires et les Méthodes du noyau . En modifiant légèrement leur définition, les forêts aléatoires peuvent être réécrites en tant que Méthodes du noyau , qui sont plus interprétables et plus faciles à analyser. ^[30]

Histoire

Leo Breiman ^[31] a été la première personne à remarquer le lien entre la forêt aléatoire et les Méthodes du noyau . Il a souligné que les forêts aléatoires qui sont cultivées à l’aide de vecteurs aléatoires Iid dans la construction de l’arbre sont équivalentes à un noyau agissant sur la vraie marge. Lin et Jeon ^[32] ont établi le lien entre les forêts aléatoires et le plus proche voisin adaptatif, ce qui implique que les forêts aléatoires peuvent être considérées comme des estimations de noyau adaptatives. Davies et Ghahramani ^[33] ont proposé Random Forest Kernel et montrent qu’il peut surpasser empiriquement les méthodes de noyau de pointe. Mépris ^[30]ont d’abord défini les estimations de KeRF et ont donné le lien explicite entre les estimations de KeRF et la forêt aléatoire. Il a également donné des expressions explicites pour les noyaux basés sur la forêt aléatoire centrée ^[34] et la forêt aléatoire uniforme ^[35] , deux modèles simplifiés de forêt aléatoire. Il a nommé ces deux KeRF Centré KeRF et Uniforme KeRF, et a prouvé des limites supérieures sur leurs taux de cohérence.

Notations et définitions

Préliminaires : Forêts centrées

La forêt centrée ^[34] est un modèle simplifié de la forêt aléatoire originale de Breiman, qui sélectionne uniformément un attribut parmi tous les attributs et effectue des divisions au centre de la cellule le long de l’attribut pré-choisi. L’algorithme s’arrête lorsqu’un arbre entièrement binaire de niveau k {displaystyle k} est construit, où k ∈ N {displaystyle kin mathbb {N} } est un paramètre de l’algorithme.

Forêt uniforme

La forêt uniforme ^[35] est un autre modèle simplifié de la forêt aléatoire originale de Breiman, qui sélectionne uniformément une caractéristique parmi toutes les caractéristiques et effectue des scissions en un point uniformément dessiné sur le côté de la cellule, le long de la caractéristique présélectionnée.

De la forêt aléatoire au KeRF

Étant donné un échantillon de formation D n = { ( X i , Y i ) } i = 1 n {displaystyle {mathcal {D}}_{n}={(mathbf {X} _{i},Y_{i})}_{i=1}^{n}} de [ 0 , 1 ] p × R {displaystyle [0,1]^{p}times mathbb {R} } -variables aléatoires indépendantes valuées distribuées comme la paire de prototypes indépendants ( X , Y ) {displaystyle (mathbf {X} ,Y)} , où E ⁡ [ Y 2 ] < ∞ {displaystyle operatorname {E} [Y^{2}]<infty } . On vise à prédire la réponse Y {displaystyle Y} , associée à la variable aléatoire X {displaystyle mathbf {X} } , en estimant la fonction de régression m ( x ) = E ⁡ [ Y ∣ X = x ] {displaystyle m(mathbf {x} )=operatorname {E} [Ymid mathbf {X} =mathbf {x} ]} . Une forêt de régression aléatoire est un ensemble de M {displaystyle M} arbres de régression randomisés. Dénoter m n ( x , Θ j ) {displaystyle m_{n}(mathbf {x} ,mathbf {Thêta} _{j})} la valeur prédite au point x {displaystyle mathbf {x} } par le j {displaystyle j} -ème arbre, où Θ 1 , … , Θ M {displaystyle mathbf {Thêta} _{1},ldots ,mathbf {Thêta} _{M}} sont des variables aléatoires indépendantes, distribuées comme une variable aléatoire générique Θ {displaystyle mathbf {thêta}} , indépendant de l’échantillon D n {displaystyle {mathcal{D}}_{n}} . Cette variable aléatoire peut être utilisée pour décrire le caractère aléatoire induit par le fractionnement des nœuds et la procédure d’échantillonnage pour la construction de l’arbre. Les arbres sont combinés pour former l’estimation de la forêt finie m M , n ( x , Θ 1 , … , Θ M ) = 1 M ∑ j = 1 M m n ( x , Θ j ) {displaystyle m_{M,n}(mathbf {x} ,Theta _{1},ldots ,Theta _{M})={frac {1}{M}}sum _{j= 1}^{M}m_{n}(mathbf {x} ,Thêta _{j})} . Pour les arbres de régression, nous avons m n = ∑ i = 1 n Y i 1 X i ∈ A n ( x , Θ j ) N n ( x , Θ j ) {displaystyle m_{n}=sum _{i=1}^{n}{frac {Y_{i}mathbf {1} _{mathbf {X} _{i}in A_{n} (mathbf {x} ,Thêta _{j})}}{N_{n}(mathbf {x} ,Thêta _{j})}}} , où A n ( x , Θ j ) {displaystyle A_{n}(mathbf {x} ,Thêta _{j})} est la cellule contenant x {displaystyle mathbf {x} } , conçu avec hasard Θ j {displaystyle Thêta _{j}} et jeu de données D n {displaystyle {mathcal{D}}_{n}} , et N n ( x , Θ j ) = ∑ i = 1 n 1 X i ∈ A n ( x , Θ j ) {displaystyle N_{n}(mathbf {x} ,Theta _{j})=sum _{i=1}^{n}mathbf {1} _{mathbf {X} _{i} in A_{n}(mathbf {x} ,Thêta _{j})}} .

Ainsi, les estimations forestières aléatoires satisfont, pour tout x ∈ [ 0 , 1 ] d {displaystyle mathbf {x} in [0,1]^{d}} , m M , n ( x , Θ 1 , … , Θ M ) = 1 M ∑ j = 1 M ( ∑ i = 1 n Y i 1 X i ∈ A n ( x , Θ j ) N n ( x , Θ j ) ) {displaystyle m_{M,n}(mathbf {x} ,Theta _{1},ldots ,Theta _{M})={frac {1}{M}}sum _{j= 1}^{M}left(sum _{i=1}^{n}{frac {Y_{i}mathbf {1} _{mathbf {X} _{i}in A_{n }(mathbf {x} ,Thêta _{j})}}{N_{n}(mathbf {x} ,Thêta _{j})}}right)} . La forêt de régression aléatoire a deux niveaux de moyenne, d’abord sur les échantillons de la cellule cible d’un arbre, puis sur tous les arbres. Ainsi, les contributions des observations qui se trouvent dans des cellules à forte densité de points de données sont plus petites que celles des observations qui appartiennent à des cellules moins peuplées. Afin d’améliorer les méthodes de forêts aléatoires et de compenser la mauvaise estimation, Scornet ^[30] a défini KeRF par

m ~ M , n ( x , Θ 1 , … , Θ M ) = 1 ∑ j = 1 M N n ( x , Θ j ) ∑ j = 1 M ∑ i = 1 n Y i 1 X i ∈ A n ( x , Θ j ) , {displaystyle {tilde {m}}_{M,n}(mathbf {x} ,Theta _{1},ldots ,Theta _{M})={frac {1}{sum _{j=1}^{M}N_{n}(mathbf {x} ,Theta _{j})}}sum _{j=1}^{M}sum _{i=1} ^{n}Y_{i}mathbf {1} _{mathbf {X} _{i}in A_{n}(mathbf {x} ,Theta _{j})},}

qui est égal à la moyenne des Y i {displaystyle Y_{i}} tombe dans les cellules contenant x {displaystyle mathbf {x} } dans la foret. Si nous définissons la fonction de connexion du M {displaystyle M} forêt finie comme K M , n ( x , z ) = 1 M ∑ j = 1 M 1 z ∈ A n ( x , Θ j ) {displaystyle K_{M,n}(mathbf {x} ,mathbf {z} )={frac {1}{M}}sum _{j=1}^{M}mathbf {1} _{mathbf {z} in A_{n}(mathbf {x} ,Theta _{j})}} , c’est-à-dire la proportion de cellules partagées entre x {displaystyle mathbf {x} } et z {displaystyle mathbf {z} } , alors on a presque sûrement m ~ M , n ( x , Θ 1 , … , Θ M ) = ∑ i = 1 n Y i K M , n ( x , x i ) ∑ l = 1 n K M , n ( x , x l ) {displaystyle {tilde {m}}_{M,n}(mathbf {x} ,Theta _{1},ldots ,Theta _{M})={frac {sum _{i =1}^{n}Y_{i}K_{M,n}(mathbf {x} ,mathbf {x} _{i})}{sum _{ell =1}^{n}K_ {M,n}(mathbf {x} ,mathbf {x} _{ell })}}} , qui définit le KeRF.

KeRF centré

La construction de KeRF Centré de niveau k {displaystyle k} est la même que pour la forêt centrée, sauf que les prédictions sont faites par m ~ M , n ( x , Θ 1 , … , Θ M ) {displaystyle {tilde {m}}_{M,n}(mathbf {x} ,Thêta _{1},ldots ,Thêta _{M})} , la fonction noyau correspondante ou la fonction de connexion est

K k c c ( x , z ) = ∑ k 1 , … , k d , ∑ j = 1 d k j = k k ! k 1 ! ⋯ k d ! ( 1 d ) k ∏ j = 1 d 1 ⌈ 2 k j x j ⌉ = ⌈ 2 k j z j ⌉ , for all x , z ∈ [ 0 , 1 ] d . {displaystyle {begin{aligned}K_{k}^{cc}(mathbf {x} ,mathbf {z} )=sum _{k_{1},ldots ,k_{d},sum _{j=1}^{d}k_{j}=k}&{frac {k!}{k_{1}!cdots k_{d}!}}left({frac {1}{ d}}right)^{k}prod _{j=1}^{d}mathbf {1} _{lceil 2^{k_{j}}x_{j}rceil =lceil 2^ {k_{j}}z_{j}rceil },\&{text{ for all }}mathbf {x} ,mathbf {z} in [0,1]^{d}.end {aligné}}} KeRF uniforme

Uniform KeRF est construit de la même manière que la forêt uniforme, sauf que les prédictions sont faites par m ~ M , n ( x , Θ 1 , … , Θ M ) {displaystyle {tilde {m}}_{M,n}(mathbf {x} ,Thêta _{1},ldots ,Thêta _{M})} , la fonction noyau correspondante ou la fonction de connexion est

K k u f ( 0 , x ) = ∑ k 1 , … , k d , ∑ j = 1 d k j = k k ! k 1 ! … k d ! ( 1 d ) k ∏ m = 1 d ( 1 − | x m | ∑ j = 0 k m − 1 ( − ln ⁡ | x m | ) j j ! ) for all x ∈ [ 0 , 1 ] d . {displaystyle K_{k}^{uf}(mathbf {0} ,mathbf {x} )=sum _{k_{1},ldots ,k_{d},sum _{j=1} ^{d}k_{j}=k}{frac {k!}{k_{1}!ldots k_{d}!}}left({frac {1}{d}}right)^ {k}prod _{m=1}^{d}left(1-|x_{m}|sum _{j=0}^{k_{m}-1}{frac {(- ln |x_{m}|)^{j}}{j!}}right){text{ for all }}mathbf {x} in [0,1]^{d}.}

Propriétés

Relation entre KeRF et forêt aléatoire

Les prédictions données par KeRF et les forêts aléatoires sont proches si le nombre de points dans chaque cellule est contrôlé :

Supposons qu’il existe des séquences ( a n ) , ( b n ) {displaystyle (a_{n}),(b_{n})} de sorte que, presque sûrement,

a n ≤ N n ( x , Θ ) ≤ b n and a n ≤ 1 M ∑ m = 1 M N n x , Θ m ≤ b n . {displaystyle a_{n}leq N_{n}(mathbf {x} ,Theta )leq b_{n}{text{ and }}a_{n}leq {frac {1}{M }}sum _{m=1}^{M}N_{n}{mathbf {x} ,Theta _{m}}leq b_{n}.}

Alors presque sûrement,

| m M , n ( x ) − m ~ M , n ( x ) | ≤ b n − a n a n m ~ M , n ( x ) . {displaystyle |m_{M,n}(mathbf {x} )-{tilde {m}}_{M,n}(mathbf {x} )|leq {frac {b_{n}- a_{n}}{a_{n}}}{tilde {m}}_{M,n}(mathbf {x} ).}

Relation entre KeRF infini et forêt aléatoire infinie

Lorsque le nombre d’arbres M {displaystyle M} va à l’infini, alors nous avons une forêt aléatoire infinie et un KeRF infini. Leurs estimations sont proches si le nombre d’observations dans chaque cellule est borné :

Supposons qu’il existe des séquences ( ε n ) , ( a n ) , ( b n ) {displaystyle (varepsilon _{n}),(a_{n}),(b_{n})} de sorte que, presque sûrement

• E ⁡ [ N n ( x , Θ ) ] ≥ 1 , {displaystyle operatorname {E} [N_{n}(mathbf {x} ,Theta )]geq 1,}
• P ⁡ [ a n ≤ N n ( x , Θ ) ≤ b n ∣ D n ] ≥ 1 − ε n / 2 , {displaystyle operatorname {P} [a_{n}leq N_{n}(mathbf {x} ,Theta )leq b_{n}mid {mathcal {D}}_{n}] geq 1-varepsilon _{n}/2,}
• P ⁡ [ a n ≤ E Θ ⁡ [ N n ( x , Θ ) ] ≤ b n ∣ D n ] ≥ 1 − ε n / 2 , {displaystyle operatorname {P} [a_{n}leq operatorname {E} _{Theta }[N_{n}(mathbf {x} ,Theta )]leq b_{n}mid { mathcal {D}}_{n}]geq 1-varepsilon _{n}/2,}

Alors presque sûrement,

| m ∞ , n ( x ) − m ~ ∞ , n ( x ) | ≤ b n − a n a n m ~ ∞ , n ( x ) + n ε n ( max 1 ≤ i ≤ n Y i ) . {displaystyle |m_{infty ,n}(mathbf {x} )-{tilde {m}}_{infty ,n}(mathbf {x} )|leq {frac {b_{n }-a_{n}}{a_{n}}}{tilde {m}}_{infty ,n}(mathbf {x} )+nvarepsilon _{n}left(max _{ 1leq ileq n}Y_{i}right).}

Résultats de cohérence

Suppose que Y = m ( X ) + ε {displaystyle Y=m(mathbf {X} )+varepsilon} , où ε {displaystyle varepsilon} est un bruit gaussien centré, indépendant de X {displaystyle mathbf {X} } , de variance finie σ 2 < ∞ {displaystyle sigma ^{2}<infty} . En outre, X {displaystyle mathbf {X} } est uniformément réparti sur [ 0 , 1 ] d {style d’affichage [0,1]^{d}} et m {displaystyle m} est Lipschitz . Scornet ^[30] a prouvé des limites supérieures sur les taux de cohérence pour le KeRF centré et le KeRF uniforme.

Cohérence du KeRF centré

Fournir k → ∞ {displaystyle kflèche droite infty} et n / 2 k → ∞ {displaystyle n/2^{k}rightarrow infty} , il existe une constante C 1 > 0 {displaystyle C_{1}>0} telle que, pour tout n {displaystyle n} , E [ m ~ n c c ( X ) − m ( X ) ] 2 ≤ C 1 n − 1 / ( 3 + d log ⁡ 2 ) ( log ⁡ n ) 2 {displaystyle mathbb {E} [{tilde {m}}_{n}^{cc}(mathbf {X} )-m(mathbf {X} )]^{2}leq C_{1 }n^{-1/(3+dlog 2)}(log n)^{2}} .

Cohérence du KeRF uniforme

Fournir k → ∞ {displaystyle kflèche droite infty} et n / 2 k → ∞ {displaystyle n/2^{k}rightarrow infty} , il existe une constante C > 0 {displaystyle C>0} tel que, E [ m ~ n u f ( X ) − m ( X ) ] 2 ≤ C n − 2 / ( 6 + 3 d log ⁡ 2 ) ( log ⁡ n ) 2 {displaystyle mathbb {E} [{tilde {m}}_{n}^{uf}(mathbf {X} )-m(mathbf {X} )]^{2}leq Cn^{ -2/(6+3dlog 2)}(log n)^{2}} .

Désavantages

Alors que les forêts aléatoires atteignent souvent une plus grande précision qu’un arbre de décision unique, elles sacrifient l’ interprétabilité intrinsèque présente dans les arbres de décision. Les arbres de décision font partie d’une famille assez restreinte de modèles d’apprentissage automatique qui sont facilement interprétables avec les modèles linéaires, les modèles basés sur des règles et les modèles basés sur l’attention . Cette interprétabilité est l’une des qualités les plus souhaitables des arbres de décision. Il permet aux développeurs de confirmer que le modèle a appris des informations réalistes à partir des données et permet aux utilisateurs finaux d’avoir confiance dans les décisions prises par le modèle. ^{[5] [3]}Par exemple, suivre le chemin qu’un arbre de décision emprunte pour prendre sa décision est assez trivial, mais suivre les chemins de dizaines ou de centaines d’arbres est beaucoup plus difficile. Pour atteindre à la fois performance et interprétabilité, certaines techniques de compression de modèles permettent de transformer une forêt aléatoire en un arbre de décision minimal “born-again” qui reproduit fidèlement la même fonction de décision. ^{[5] [36] [37]} S’il est établi que les attributs prédictifs sont linéairement corrélés avec la variable cible, l’utilisation de la forêt aléatoire peut ne pas améliorer la précision de l’apprenant de base. ^{[5] [29]} De plus, dans les problèmes avec plusieurs variables catégorielles, la forêt aléatoire peut ne pas être en mesure d’augmenter la précision de l’apprenant de base. ^[38]

Voir également

• Boosting – Méthode en machine learning
• Apprentissage par arbre de décision – Algorithme d’apprentissage automatique
• Apprentissage d’ensemble – Statistiques et technique d’apprentissage automatique
• Gradient boosting – Technique d’apprentissage automatique
• Statistiques non paramétriques
• Algorithme randomisé – Algorithme qui utilise un degré d’aléatoire dans le cadre de sa logique ou de sa procédure

Références

1. ^ ^{un bcd Ho , Tin} Kam (1995). Forêts de décision aléatoire (PDF) . Actes de la 3e Conférence internationale sur l’analyse et la reconnaissance de documents, Montréal, QC, 14–16 août 1995. pp. 278–282. Archivé de l’original (PDF) le 17 avril 2016 . Récupéré le 5 juin 2016 .
2. ^ ^{un bcd Ho TK} (1998). “La méthode de sous-espace aléatoire pour la construction de forêts de décision” (PDF) . Transactions IEEE sur l’analyse de modèles et l’intelligence artificielle . 20 (8): 832–844. doi : 10.1109/34.709601 .
3. ^ ^{un bcdefg Hastie} , ^Trevor ; ^{_ _ _} Tibshirani, Robert ; Friedman, Jérôme (2008). Les éléments de l’apprentissage statistique (2e éd.). Springer. ISBN 0-387-95284-5.
4. ^ ^{un b} Piryonesi S. Madeh; El-Diraby Tamer E. (2020-06-01). “Rôle de l’analyse de données dans la gestion des actifs d’infrastructure : surmonter les problèmes de taille et de qualité des données”. Journal of Transportation Engineering, Partie B : Chaussées . 146 (2) : 04020022. doi : 10.1061/JPEODX.0000175 . S2CID 216485629 .
5. ^ ^{un bcdef Piryonesi , S. Madeh} ; El-Diraby, Tamer E. (2021-02-01). “Utilisation de l’apprentissage automatique pour examiner l’impact du type d’indicateur de performance sur la modélisation flexible de la détérioration de la chaussée” . Journal des systèmes d’infrastructure . 27 (2): 04021005. doi : 10.1061/(ASCE)IS.1943-555X.0000602 . ISSN 1076-0342 . S2CID 233550030 .
6. ^ ^{un b} Kleinberg E (1990). “Discrimination stochastique” (PDF) . Annales de Mathématiques et d’Intelligence Artificielle . 1 (1–4): 207–239. CiteSeerX 10.1.1.25.6750 . doi : 10.1007/BF01531079 . S2CID 206795835 . Archivé de l’original (PDF) le 2018-01-18.
7. ^ ^{un b} Kleinberg E (1996). “Une méthode de modélisation stochastique résistante au surentraînement pour la reconnaissance de formes” . Annales de statistiques . 24 (6): 2319–2349. doi : 10.1214/aos/1032181157 . M. 1425956 .
8. ^ ^{un b} Kleinberg E (2000). “Sur la mise en œuvre algorithmique de la discrimination stochastique” (PDF) . Transactions IEEE sur PAMI . 22 (5): 473–490. CiteSeerX 10.1.1.33.4131 . doi : 10.1109/34.857004 . S2CID 3563126 . Archivé de l’original (PDF) le 2018-01-18.
9. ^ ^{un bcd Breiman L} ( 2001). “Forêts aléatoires” . Apprentissage automatique . 45 (1): 5–32. Bibcode : 2001MachL..45….5B . doi : 10.1023/A:1010933404324 .
10. ^ ^{un b} Liaw A (16 octobre 2012). “Documentation pour le package R randomForest” (PDF) . Récupéré le 15 mars 2013 .
11. ^ Numéro d’enregistrement de la marque américaine 3185828, enregistrée le 19/12/2006.
12. ^ “RANDOM FORESTS Marque déposée de Health Care Productivity, Inc. – Numéro d’enregistrement 3185828 – Numéro de série 78642027 :: Justia Trademarks” .
13. ^ ^{un b} Amit Y, Geman D (1997). “Quantification de forme et reconnaissance avec des arbres aléatoires” (PDF) . Calcul neuronal . 9 (7): 1545-1588. CiteSeerX 10.1.1.57.6069 . doi : 10.1162/neco.1997.9.7.1545 . S2CID 12470146 .
14. ^ Dietterich, Thomas (2000). “Une comparaison expérimentale de trois méthodes de construction d’ensembles d’arbres de décision : mise en sac, amplification et randomisation” . Apprentissage automatique . 40 (2): 139–157. doi : 10.1023/A:1007607513941 .
15. ^ Gareth James; Daniela Witten; Trevor Hastie; Robert Tibshirani (2013). Une introduction à l’apprentissage statistique . Springer. p. 316–321.
16. ^ Ho, Tin Kam (2002). “Une analyse de la complexité des données des avantages comparatifs des constructeurs de forêts de décision” (PDF) . Analyse de modèle et applications . 5 (2): 102–112. doi : 10.1007/s100440200009 . S2CID 7415435 .
17. ^ Geurts P, Ernst D, Wehenkel L (2006). “Arbres extrêmement aléatoires” (PDF) . Apprentissage automatique . 63 : 3–42. doi : 10.1007/s10994-006-6226-1 .
18. ^ Zhu R, Zeng D, Kosorok MR (2015). “Arbres d’apprentissage de renforcement” . Journal de l’Association statistique américaine . 110 (512): 1770-1784. doi : 10.1080/01621459.2015.1036994 . PMC 4760114 . PMID 26903687 .
19. ^ Deng, H.; Runger, G.; En ligneTuv, E. (2011). Biais des mesures d’importance pour les attributs et les solutions à valeurs multiples . Actes de la 21e Conférence internationale sur les réseaux de neurones artificiels (ICANN). p. 293–300.
20. ^ Altmann A, Tolosi L, Sander O, Lengauer T (mai 2010). “Importance de permutation: une mesure d’importance de caractéristique corrigée” . Bioinformatique . 26 (10): 1340–7. doi : 10.1093/bioinformatique/btq134 . PMID 20385727 .
21. ^ Strobl C, Boulesteix A, Augustin T (2007). “Sélection fractionnée impartiale pour les arbres de classification basés sur l’indice de Gini” (PDF) . Statistiques informatiques et analyse de données . 52 : 483–501. CiteSeerX 10.1.1.525.3178 . doi : 10.1016/j.csda.2006.12.030 .
22. ^ Painsky A, Rosset S (2017). “La sélection de variables à validation croisée dans les méthodes arborescentes améliore les performances prédictives”. Transactions IEEE sur l’analyse de modèles et l’intelligence artificielle . 39 (11): 2142–2153. arXiv : 1512.03444 . doi : 10.1109/tpami.2016.2636831 . PMID 28114007 . S2CID 5381516 .
23. ^ Tolosi L, Lengauer T (juillet 2011). “Classification avec des fonctionnalités corrélées : manque de fiabilité du classement des fonctionnalités et des solutions” . Bioinformatique . 27 (14): 1986–94. doi : 10.1093/bioinformatique/btr300 . PMID 21576180 .
24. ^ ^{un b} Lin, Yi; Jeon, Yongho (2002). Forêts aléatoires et plus proches voisins adaptatifs (Rapport technique). Rapport technique n° 1055. Université du Wisconsin. CiteSeerX 10.1.1.153.9168 .
25. ^ Shi, T., Horvath, S. (2006). “Apprentissage non supervisé avec des prédicteurs de forêt aléatoire”. Journal of Computational and Graphical Statistics . 15 (1): 118–138. CiteSeerX 10.1.1.698.2365 . doi : 10.1198/106186006X94072 . JSTOR 27594168 . S2CID 245216 . {{cite journal}}: CS1 maint: uses authors parameter (link)
26. ^ Shi T, Seligson D, Belldegrun AS, Palotie A, Horvath S (avril 2005). “Classification des tumeurs par profilage des microréseaux tissulaires : regroupement aléatoire de forêts appliqué au carcinome à cellules rénales” . Pathologie moderne . 18 (4): 547–57. doi : 10.1038/modpathol.3800322 . PMID 15529185 .
27. ^ Prinzie, A., Van den Poel, D. (2008). “Forêts aléatoires pour la classification multiclasse: Logit multinomial aléatoire”. Systèmes experts avec applications . 34 (3): 1721-1732. doi : 10.1016/j.eswa.2007.01.029 . {{cite journal}}: CS1 maint: uses authors parameter (link)
28. ^ Prinzie, Anita (2007). “Classification multiclasse aléatoire: généralisation des forêts aléatoires au MNL aléatoire et au NB aléatoire”. Dans Roland Wagner; Norman Revell; Günther Pernul (éd.). Bases de données et applications de systèmes experts : 18e conférence internationale, DEXA 2007, Regensburg, Allemagne, 3-7 septembre 2007, Actes . Notes de cours en informatique. Vol. 4653. pp. 349–358. doi : 10.1007/978-3-540-74469-6_35 . ISBN 978-3-540-74467-2.
29. ^ ^{un b} Smith, Paul F.; Ganesh, Shiva ; Liu, Ping (2013-10-01). “Une comparaison de la régression forestière aléatoire et de la régression linéaire multiple pour la prédiction en neurosciences” . Tourillon des méthodes de neuroscience . 220 (1): 85–91. doi : 10.1016/j.jneumeth.2013.08.024 . PMID 24012917 . S2CID 13195700 .
30. ^ ^{un bcd Scornet , Erwan} (2015). “Forêts aléatoires et méthodes de noyau”. arXiv : 1502.03836 [ math.ST ].
31. ^ Breiman, Lion (2000). “Une théorie de l’infini pour les ensembles de prédicteurs” . Rapport technique 579, Département des statistiques UCB. {{cite journal}}: Cite journal requires |journal= (help)
32. ^ Lin, Yi; Jeon, Yongho (2006). “Forêts aléatoires et voisins les plus proches adaptatifs”. Journal de l’Association statistique américaine . 101 (474): 578–590. CiteSeerX 10.1.1.153.9168 . doi : 10.1198/016214505000001230 . S2CID 2469856 .
33. ^ Davies, Alex; En ligneGhahramani, Zoubin (2014). “Le noyau de forêt aléatoire et d’autres noyaux pour les données volumineuses à partir de partitions aléatoires”. arXiv : 1402.4293 [ stat.ML ].
34. ^ ^{un b} Breiman L, Ghahramani Z (2004). “Cohérence pour un modèle simple de forêts aléatoires”. Département de statistique, Université de Californie à Berkeley. Rapport technique (670). CiteSeerX 10.1.1.618.90 .
35. ^ ^{un b} Arlot S, Genuer R (2014). “Analyse du biais des forêts purement aléatoires”. arXiv : 1407.3939 [ math.ST ].
36. ^ Sagi, Omer; Rokach, Lior (2020). “Forêt de décision explicable : transformer une forêt de décision en arbre interprétable” . Fusion d’informations . 61 : 124–138. doi : 10.1016/j.inffus.2020.03.013 . S2CID 216444882 .
37. ↑ Vidal, Thibaut ; Schiffer, Maximilien (2020). “Ensembles d’arbres nés de nouveau” . Conférence internationale sur l’apprentissage automatique . PMLR. 119 : 9743–9753. arXiv : 2003.11132 .
38. ^ Piryonesi, Sayed Madeh (novembre 2019). Piryonesi, SM (2019). The Application of Data Analytics to Asset Management: Deterioration and Climate Change Adaptation in Ontario Roads (Dissertation de doctorat) (Thèse).

Lectures complémentaires

Scholia a un profil de sujet pour Random forest .

• Prinzie A, Poel D (2007). “Classification aléatoire multiclasse: généralisation des forêts aléatoires au MNL aléatoire et au NB aléatoire” . Applications de bases de données et de systèmes experts . Notes de cours en informatique . Vol. 4653. p. 349. doi : 10.1007/978-3-540-74469-6_35 . ISBN 978-3-540-74467-2.
• Denisko D, Hoffman MM (février 2018). “Classification et interaction dans les forêts aléatoires” . Actes de l’Académie nationale des sciences des États-Unis d’Amérique . 115 (8) : 1690–1692. doi : 10.1073/pnas.1800256115 . PMC 5828645 . PMID 29440440 .

Liens externes

• Description du classificateur Random Forests (site de Leo Breiman)
• Liaw, Andy & Wiener, Matthew “Classification et régression par randomForest” R News (2002) Vol. 2/3 p. 18 (Discussion sur l’utilisation du package forêt aléatoire pour R )