Arbres de régression et modèles de durée

Université d’été (Paris, le 7 juillet 2014)ISUP, IA et ENSAE ParisTech

O. Lopez1,2, X. Milhaud1 et P. Thérond3,4

1 ENSAE ParisTech et CREST (LFA)2 Université Pierre et Marie Curie3 ISFA, Laboratoire SAF4 Galéa & Associés

1 / 47

Plan de l’exposé

1 Introduction à la problématique

2 Exemples d’utilisation

3 Construction de l’arbre

4 Procédure d’élagage de l’arbre

5 Robustesse de la méthode CART

6 Retour au problème de données censurées et extension

2 / 47

Contexte classique d’étude des risques en assurance

L’analyse des engagements d’un assureur nécessite decomprendre l’impact de caractéristiques sur le risque.

Les bases de données des assureurs comportent un ensembled’informations sur

les caractéristiques de l’assuré,

les options du contrat,

les conditions de marché.

Ces informations jouent un rôle crucial dans les prévisions desinistralité⇒ il faut tenir compte de ces caractéristiques indiv.

3 / 47

Deux problèmes de données censurées

On cherche à estimer la durée de vie d’un individu T ayant unensemble de caractéristiques X ∈ Rd .

On sait que l’individu a déjà vécu une durée Y avant decesser d’être observé : observation censurée.

Un sinistre a été ouvert depuis une durée Y (non clos).

Le montant total du sinistre M n’est pas connu, on n’a payéjusqu’à présent que N ≤ M au titre de ce sinistre.

On cherche à prédire M (éventuellement la durée totale dedéveloppement T ) à partir des caractéristiques X ∈ Rd dusinistre.

4 / 47

Deux problèmes de données censurées

On cherche à estimer la durée de vie d’un individu T ayant unensemble de caractéristiques X ∈ Rd .

On sait que l’individu a déjà vécu une durée Y avant decesser d’être observé : observation censurée.

Un sinistre a été ouvert depuis une durée Y (non clos).

Le montant total du sinistre M n’est pas connu, on n’a payéjusqu’à présent que N ≤ M au titre de ce sinistre.

On cherche à prédire M (éventuellement la durée totale dedéveloppement T ) à partir des caractéristiques X ∈ Rd dusinistre.

4 / 47

Observations (dans le second exemple)

ObservationsOn observe des réalisations i.i.d. de variables (Yi ,Ni , δi ,Xi)1≤i≤n demême loi que (Y ,N, δ,X), où{

Y = inf(T ,C),N = inf(M,D),

etδ = 1T≤C = 1M≤D .

C et D sont des variables de censures. Exemple :C = temps entre aujourd’hui et la date d’ouverture du sinistre ;D = montant réglé jusqu’à présent au titre du sinistre.

5 / 47

Formalisation du problème

Le sinistre est ouvert depuis une durée Y , pour un montantréglé jusqu’à présent de N.

Il n’est pas clos, donc δ = 0.

La meilleure prédiction de M à partir des données disponiblessur le sinistre est

M∗ = E [M | δ = 0,N,Y ,X ] .

But : déterminer un estimateur du prédicteur idéal M∗ à partirdes observations.

Difficultés : on n’observe pas des réalisations i.i.d. de M, doncles méthodes "standards" ne marchent pas.

6 / 47

Objectif : construction d’une classification fine desindividus et analyse du risque sur ces classes

Regrouper des indiv. hétérogènes en classes de risquehomogènes...∃ de nombreuses techniques de classification (création degroupes d’assurés homogènes), parmi lesquelles :

pour la classification non-supervisée :→ les algorithmes dits des k -plus proches voisins ;→ les techniques ascendantes d’arbre de classification (CAH) ;→ la classification par model-based clustering (mélanges finis).

pour la classification supervisée :→ les modèles de choix (LOGIT) ;→ les réseaux de neurones ;→ les méthodes descendantes d’arbre (CART, CHAID, ...) ;

7 / 47

Quelques références sur l’utilisation des arbres enactuariat (non exhaustif)

1) Assurance vie :

Prévision de taux de mortalité par tranche d’âge : [Olb12].

Prévision des comportements de rachat : [MMDL11]

2) Assurance non vie :

R.A. DERRIG et L. FRANCIS, Casualty Actuarial Society(CAS), Variance, vol. 2 issue 2.

[PPG11] (BFA), mais aussi [Bel14] (mémoire d’actuariat).

Lien entre scoring d’assurés par arbre et pertes : GUSZCZA,WU et CHENG-SHENG (CAS Forum, 2003).

8 / 47

Arbre et clustering : quelques premiers éléments

Pour estimer notre quantité d’intérêt, on choisit d’utiliser un arbre...Mais qu’est-ce qu’un arbre ?

1 Une racine : contient l’ensemble de la population à segmenter(le portefeuille global)⇒ c’est le point de départ ;

2 Un tronc et des branches : contiennent les règles de divisionqui permettent de segmenter la population ;

3 Des feuilles : contiennent les sous-populations homogènescréées, fournissent l’estimation de la quantité d’intérêt.

9 / 47

2 Exemples d’utilisationUne méthode populaire : un premier exempleApplication à la classification du statut propriétaire

10 / 47

Aparté sur la lecture d’un arbre

Un arbre de classification / régression se lit de la racine vers lesfeuilles.

A chaque ramification, une règle de division apparait : dans CART,

cette règle (' question) admet une réponse binaire,

elle n’est basée que sur un facteur de risque.

Un noeud est l’intersection d’un ensemble de règles. L’estimationde la quantité d’intérêt se lit dans les noeuds terminaux (feuilles).

N’importe quel individu de la population initiale appartient à uneunique feuille : les sous-populations créées sont disjointes.

11 / 47

Exemple 1 : prévisions des résultats des primaires aux US

Il s’agit de déterminer les facteurs clefs qui ont joué sur lesrésultats des primaires de 2008 aux USA :

Qui de H. Clinton ou B. Obama remportera tel ou tel état ?

Entre Clinton et Obama, deux critères de population de votantsapparaissent comme essentiels :

1 la couleur de peau des votants,2 leur niveau d’éducation.

On peut visualiser ces résultats sur la publication suivante du NYTimes...

12 / 47

Exemple 2 : prévisions propriétaire | salaire et surface

!"#$%&#'(

! )*'+,-./01,*2'3#'456/71&#8',/$#.,/2'2.914#.'1*'$9:#*'3#'7&,88#.'&#8'+,$/&&#8'3,*8'1*#'4/&&#'01/'89*2';'$<$#'3=,76#2#.'1*'456/71&#'#2'7#&&#8'01/'*#'89*2'%,8'%.<2#*2';'#*',76#2#.>')*'576,*2/&&9*'3#'(?'%.9%./52,/.#8'#2'(?'*9*@%.9%./52,/.#8'#82'769/8/>'A#8'3#1"'4,./,-&#8'/*35%#*3,*2#8'89*2'B'"('C!"#$%&'91'.#4#*18D'#2'"?'C'$()*!+&'91'81.+,7#'#*'%/#38'%,.'$?D

!"#$%&#'(

! )*'+,-./01,*2'3#'456/71&#8',/$#.,/2'2.914#.'1*'$9:#*'3#'7&,88#.'&#8'+,$/&&#8'3,*8'1*#'4/&&#'01/'89*2';'$<$#'3=,76#2#.'1*'456/71&#'#2'7#&&#8'01/'*#'89*2'%,8'%.<2#*2';'#*',76#2#.>')*'576,*2/&&9*'3#'(?'%.9%./52,/.#8'#2'(?'*9*@%.9%./52,/.#8'#82'769/8/>'A#8'3#1"'4,./,-&#8'/*35%#*3,*2#8'89*2'B'"('C!"#$%&'91'.#4#*18D'#2'"?'C'$()*!+&'91'81.+,7#'#*'%/#38'%,.'$?D

13 / 47

Partitionnement et arbre correspondant

!"# $%&'# ()*+# ,)--%"'# .%#$/+'*'*)""%-%"'# +0,&+1*2#$%+-%'#34/22*"%+#.4%"1%-5.%#3%1#+%,'/"6.%1# $)&+# 3%(%"*+# $.&1#$&+1# 3%# ./# -/"*7+%# 3)"'#$+),73%#.4/.6)+*8'-%9#

:# 3+)*'%# )"# ()*'# .40'/$%# 2*"/.%#3&#$/+'*'*)""%-%"'#+0,&+1*29

Partitionnement qui maximise l’homogénéité dans chq rectangle.

14 / 47

Voici l'arbre complet. On a représenté par des cercles les noeuds qui ont des successeurs. Les nombres à l'intérieur des cercles sont les valeurs de division et le nom de la variable choisie pour la division à ce noeud est écrit sous le noeud. Les nombres sur la fourche gauche à un noeud de décision ont des valeurs inférieures ou égales à la valeur de division tandis que le nombre de la fourche droite montre un nombre qui a une valeur plus grande.

15 / 47

3 Construction de l’arbreCroissance de l’arbre pour estimer une moyenneLien avec le problème de régression classiqueArrêt de la ramificationGénéralisation et extensions

16 / 47

Notations lorsque la v.a. réponse n’est pas censurée

→ i ∈ ~1, n� : identifiant de l’individu / l’assuré ;

→ j ∈ ~1, k� : identifiant du facteur de risque (continu ou discret) ;

→ Yi : réponse OBSERVEE du ième individu (continue/discrète) ;

→ Xi = (Xi1, ...,Xik ) : vecteur des facteurs de risque de l’indiv. i ;

→ X : espace des covariables (facteurs de risque) ;

→ l ∈ ~1, L� : identifiant des feuilles de l’arbre ;

→ Xl : ensemble de la partition correspondant à la feuille l.

17 / 47

Arbre de régression : cas classique avec Y continue

Dans le cas d’une régression classique, la quantité d’intérêt est

π0(x) = E0[Y |X = x] (1)

En supposant une relation linéaire (dc se restreignant à une classed’estimateurs), on estime les paramètres de régression par MCO.

En toute généralité, on ne peut pas considérer ts les estimateurspotentiels de π0(x)⇒ arbres sont 1 autre classe d’estimateurs :ce sont des fonct. constantes par morceaux pour le problème (1).

Construire un arbre génére une suite d’estimateurs selon uneprocédure spécifique : divisions successives de l’espace X.

18 / 47

Construction de l’arbre : critère de division

La ramification de l’arbre est basée sur la définition d’un critère dedivision cohérent avec l’estimation de la quantité d’intérêt.

Dans l’estimation de (1), les MCO sont utilisés car la solution estdonnée par

π0(x) = arg minπ(x)

E0[Φ(Y , π(x)) |X = x], (2)

où Φ(Y , π(x)) = (Y − π(x))2.

La fonction de perte Φ correspond donc à l’erreur quadratique, etle critère est la minimisation de l’EQM.

19 / 47

Lien entre régression et arbre : la notion de “règles”

Tout arbre de régression est un ensemble de règles. Pour chaquenoeud m, une règle Rm est associée à un ss-ensemble Xm ⊆ X.

Notation : dans la suite, En[Y ] désigne la moyenne empirique deY , et Xpa(m) est le sous-ensemble associé au noeud parent de m.

L’arbre est associé à la fonction de régression

π(x) =M∑

m=1

βtreem Rm(x) (3)

où βtreem = En[Y | x ∈ Xm] − En[Y | x ∈ Xpa(m)] si m , racine,βtree

m = En[Y ] sinon.

20 / 47

Cela équivaut en régression classique à chercher

βtree = arg minβtree

En

[(Y −

∑βtree

m Rm(x))2

].

A partir de (3) et en sommant sur ts les noeuds :

π(x) := πL (x) =L∑

l=1

γl Rl(x) (4)

L est le nombre de feuilles de l’arbre, l leur indice,

Rl(x) = 11(x ∈ Xl) : une “règle” de division,

γl = En[Y | x ∈ Xl] : moyenne empirique de Y dans la feuille l,les sous-ensembles Xl ⊆ X de la partition sont

disjoints (Xl ∩ Xl′ = ∅, l , l′

),exhaustifs (X = ∪l Xl).

21 / 47

(4) généralisable qlq soit la quantité d’intérêt. Ainsi, tout arbre peutêtre vu comme un estimateur par morceaux.

Interprétation :

chaque morceau est une feuille, dont la valeur est la moyenneempirique des valeurs de Y de cette feuille,

chaque division vise à minimiser la somme des variancesintra-noeuds résultantes. Idée : maximiser l’homogénéité...

La construction étant récursive, on génère une suite d’estimateursdepuis le nd racine : soit une suite {ΠK } de ss-espaces t.q. ΠK ⊆ Π,

ΠK ={πL (.) =

L∑l=1

γl Rl(.) : L ∈ N∗, L ≤ K}. (5)

22 / 47

A K fixé, on cherche πK0 tq

πK0 (x) = arg min

π(x)∈ΠKE0[Φ(Y , π(x)) |X = x].

En pratique on cherche la version empirique, πK , telle que

πK (x) = arg minπ(x)∈ΠK

En[ Φ(Y , π(x)) ].

ou encoreπK (x) = arg min

γ=(γ1,...,γL )

En[ Φ(Y , πL (x)) ]. (6)

Les estimateurs par arbre ne cherchent pas tous les estimateurspossibles avec L ≤ K : ils approchent ce minimum récursivement.

23 / 47

Arrêt de la procédure de division

Le principe de l’algorithme CART est de ne pas fixer de règled’arrêt arbitraire pour la procédure.

L’algorithme arrête ainsi de diviser les feuilles quand :

il n’y a qu’une observation dans la feuille, ou

les individus de la feuille ont les mêmes valeurs de facteursde risque.

On construit ainsi l’arbre “maximal”, qui sera ensuite élagué.

Arbre maximal = estimateur par morceaux final le plus complexede la suite d’estimateurs construits→ CV garantie ([BFOS84]).

24 / 47

Généralisation et extensions avec Φ fonction de perte

π0(x) = arg minπ(x)

E0[Φ(Y , π(x)) |X = x]

Estimation de moyenne : π0(x) = E0[Y |X = x]→ critère de division (MCO) : Φ(Y , π(x)) = (Y − π(x))2.

Quantile : π0(x) = QY (α |X = x) = inf{y : F(y |X = x) ≥ α}Φα(y, π(x)) = α|y−π(x)|11(y > π(x)) + (1−α)|y−π(x)|11(y ≤ π(x))

Estimation de densité de la loi de Y→ Φ(Y , π(x)) = − log π(Y , x), avec π la densité jointe de (Y ,X).

25 / 47

4 Procédure d’élagage de l’arbreCritère d’élagage de l’arbreAlgorithme d’élagage de l’arbre

26 / 47

Elagage : critère coût-complexité

Une fois l’arbre maximal construit (de taille K(n)), on obtient unesuite d’estimateurs (πK (x))K=1,...,K(n).

Eviter estimateur trop complexe⇒ trouver le meilleur sous-arbrede l’arbre maximal selon un critère “adéquation - complexité” :

Rα(πK (x)) = En[ Φ(Y , πK (x)) ] + α (K/n).

Pour α fixé, l’estimateur retenu satisfait

πKα (x) = arg min

(πK )K=1,...,K(n)

Rα(πK (x)). (7)

27 / 47

Elagage : procédure de sélection de modèle et estimateur final

On fait croître itérativement α : 0 = α1 < ... < αz < ... < αZ−1 < αZ ,et on choisit pour chaque αz le meilleur estimateur donné par (7).

Par construction, on a une suite décroissante de sous-arbresoptimaux de l’arbre maximal vers la racine. Dans cette listed’estimateurs, on choisit finalement α tel que

πKα (x) = arg min

(πKαz )α=α1 ,...,αZ

Rαz (πKαz

(x)). (8)

Consistance : voir [GN05] et [MDvdL04] (V-fold).

28 / 47

5 Robustesse de la méthode CART

29 / 47

Un mot sur la robustesse de la méthode CART

Certaines techniques ont été développées afin de stabiliser laprévision donnée par un estimateur arbre.

En effet, la construction d’un arbre optimal peut varier fortementquand bien même le jeu de données initial varie peu.

D’où l’idée de proposer des procédures avec

1 choix aléatoire des facteurs de risque considérés lors d’unedivision (random forests).

2 tirage aléatoire de sous-jeux de données (bagging : boostrapaggregating).

30 / 47

Exemple le plus connu : les forêts aléatoires

L’objectif des forêts aléatoires est de proposer un estimateur detype “bootstrap” afin d’améliorer la robustesse de l’estimation de laquantité d’intérêt.

Il s’agit de moyenner les prévisions obtenues.Cette approche est intéressante pour deux raisons principales :

on peut dégager un classement robuste du pouvoir explicatifde chacun des facteurs de risque,

sa consistance a été démontrée récemment dans plusieursarticles récents : [IK10], [Mei09], [Mei06].

31 / 47

6 Retour au problème de données censurées et extension

32 / 47

Rappel sur les données

ObservationsOn observe des réalisations i.i.d. de variables (Yi ,Ni , δi ,Xi)1≤i≤n demême loi que (Y ,N, δ,X), où{

Y = inf(T ,C),N = inf(M,D),

etδ = 1T≤C = 1M≤D .

C et D sont des variables de censures.

33 / 47

Retour au problème initial

Le sinistre est ouvert depuis une durée Y , pour un montantréglé jusqu’à présent de N.

Il n’est pas clos, donc δ = 0.

La meilleure prédiction de M à partir des données disponiblessur le sinistre est

M∗ = E [M|δ = 0,N,Y ,X ] .

But : déterminer un estimateur du prédicteur idéal M∗ à partirdes observations.

34 / 47

Illustration des problèmes causés par la censure

Considérons le problème plus simple d’estimer m = E[M].

Si j’observe (M1, ...,Mn) i.i.d., je peux estimer m par

m =1n

n∑i=1

Mi →p.s. m.

Que se passe-t-il si je n’observe que (N1, δ1, ...,Nn, δn) ?

Mauvaise idée 1 : m1 = 1n∑n

i=1 Ni .

Mauvaise idée 2 : m2 = 1∑nj=1 δj

∑ni=1 δiNi .

35 / 47

Illustration des problèmes causés par la censure

Exemple naif : M ∼ E(λ), et D ∼ E(µ), avec M et Dindépendants.

Dans ce cas, m1 tend vers

E [inf(M,D)] =1

λ + µ.

De plus, m2 tend vers

E [δM]

E[δ]=

1λ + µ

Dans les deux cas, on sous-estime la valeur moyenne de M.

Solution : corriger la présence de la censure en essayant decompenser cette sous-estimation.

36 / 47

Premier ingrédient : l’estimateur de Kaplan-Meier

On suppose que T est indépendant de C .

On définit :

F(t) = 1 −∏Yi≤t

1 − δi∑nj=1 1Yj≥Yi

.Cet estimateur converge vers F(t) = P(T ≤ t).

Ecriture additive : F(t) =∑n

i=1 Wi,n1Yi≤t ,

avecWi,n =

δi

n[1 − G(Yi−)],

et G(t) estimateur de Kaplan-Meier de G(t) = P(C ≤ t).

37 / 47

Comment utiliser Kaplan-Meier pour estimer unemoyenne ?

Supposons que je veuille estimer E[T ].

On peut estimer E[T ] par l’espérance de la distributionassociée Ãa F , i.e. ∫

tdF(t) =n∑

i=1

Wi,nYi ,

i.e. une somme pondérée des Yi observés.

Plus généralement, θ = E[φ(T)] s’estime par

n∑i=1

Wi,nφ(Yi).

38 / 47

Pourquoi cela fonctionne ?

On rappelle que Wi,n = 1n

δi

1−G(Yi−).

Wi,n est "proche" de W∗i,n = 1

nδi

1−G(Yi−).

De plus,

n∑i=1

W∗i,nφ(Yi) =

1n

n∑i=1

δiφ(Yi)

1 − G(Yi−)→p.s. E

[δφ(Y)

1 − G(Y−)

].

PropositionPour toute fonction φ telle que E[φ(T)] < ∞,

E[

δφ(Y)

1 − G(Y−)

]= E[φ(T)].

39 / 47

2ème ingrédient : Inverse Prob. of Censoring Weights

Dans l’exemple qui nous intéresse, on va vouloir déterminer desquantités du type E[φ(T ,M,X)].

PropositionOn suppose que :

C indépendant de (T ,M,X);

{N < M} = {T < C}.

Alors

E[δφ(Y ,N,X)

n(1 − G(Y−))

]= E[φ(T ,M,X)],

et

E[δφ(Y ,N,X)

n(1 − G(Y−))|X

]= E[φ(T ,M,X)|X ].

40 / 47

2ème ingrédient : Inverse Prob. of Censoring Weights

Donc pour estimer une quantité du type E[φ(T ,M,X)], onutilisera

1n

n∑i=1

δiφ(Yi ,Ni ,Xi)

1 − G(Yi−)=

n∑i=1

Wi,nφ(Yi ,Ni ,Xi).

Donc pour estimer, par exemple, des quantités du type

E[(φ(Ti ,Mi) − a)21Xi∈X

],

où X est un ensemble, on calculera

n∑i=1

Wi,n(φ(Yi ,Ni) − a)21Xi∈X.

41 / 47

Décomposition de notre problème

On rappelle qu’on cherche à estimer

E [M | δ = 0,X ,Y ,N] .

On a

E [M|δ = 0,X = x,Y = y,N = n] = E [M|M ≥ n,T ≥ y,X = x]

=E

[M1M≥n,T≥y |X = x

]P(T ≥ y,M ≥ n|X = x)

.

On définit φ1(t ,m) = m1m≥n,T≥y , et φ2(t ,m) = 1t≥y,m≥n. Ondoit donc estimer

E[φ1(T ,M)|X = x], et E[φ2(T ,M)|X = x].

42 / 47

Quelques idées d’application pratique en assurance

Ce type de données est largement utilisé en assurance (vie etIARD). Nous pourrions par exemple utiliser ces techniques pour...

Provisionnement ligne à ligne et estimation du montant finaldu sinistre (en évitant les hyp. de type Merz & Wuthrich).

Détermination de plafond de garantie.

Risque incapacité - invalidité.

Portefeuille de plusieurs entités.

Evaluation de mesure de risque (quantile) à des finsrèglementaires.

43 / 47

Conclusion

Pourquoi cette technique est-elle intéressante pour le big data ?

→ Algorithme naturellement adapté à la gestion de grandes basesde données ;

→ Technique non-paramétrique : pas d’hypothèses sur le lienentre quantité d’intérêt et facteurs de risque ;

→ Simplicité de l’estimateur final : faible dimension, interprétationde l’arbre et visionnage des résultats ;

→ Consistance de la procédure théoriquement prouvée ;

→ Classement naturel du pouvoir discriminant des covariables ;

44 / 47

→ Multiples extensions possibles en travaillant sur les propriétésde la fonction de perte.

Quels en sont les points faibles ?

→ Hypothèses sous-jacentes pouvant parfois être remises encause ;

→ Manque de résultats théoriques (étape élagage) dans des casmoins classiques ;

→ Instabilité : nécessité de la compléter avec des techniques detype forêts aléatoires.

45 / 47

Bibliographie

R. Bellina.Méthodes d’apprentissage appliquées à la tarification non-vie.Mémoire d’actuariat, 2014.

L. Breiman, J. Friedman, R. A. Olshen, and C. J. Stone.Classification and Regression Trees.Chapman and Hall, 1984.

Servane Gey and Elodie Nedelec.Model selection for cart regression trees.IEEE Transactions on Information Theory, 51(2) :658–670, 2005.

Hemant Ishwaran and Udaya B. Kogalur.Consistency of random survival forests.Statistics and Probability Letters, 80(13-14) :1056–1064, 2010.

Annette M. Molinaro, Sandrine Dudoit, and Mark J. van der Laan.Tree-based multivariate regression and density estimation with right-censored data.JMVA, 90(1) :154–177, 2004.

46 / 47

Nicolai Meinshausen.Quantile regression forests.Journal of Machine Learning Research, 7 :983–999, 2006.

Nicolai Meinshausen.Forest garrote.Electronic Journal of Statistics, 3 :1288–1304, 2009.

X. Milhaud, V. Maume-Deschamps, and S. Loisel.Surrender triggers in life insurance : what main features affect the surrender behaviorin a classical economic context ?Bulletin Français d’Actuariat, 22 :5–48, 2011.

Walter Olbricht.Tree-based methods : a useful tool for life insurance.European Actuarial Journal, 2(1) :129–147, 2012.

A. Paglia and M.V. Phelippe-Guinvarc’h.Tarification des risques en assurance non-vie, une approche par modèled’apprentissage statistique.Bulletin français d’Actuariat, 11(22) :49–81, 2011.

47 / 47