View
226
Download
1
Category
Preview:
Citation preview
SEGMENTATIONSEGMENTATION
Pierre-Louis GONZALEZ1
I. Les méthodes de segmentation. Introductiong
Les méthodes de segmentation cherchent à résoudre les problèmes dediscrimination et de régression en divisant de façon progressiveg ç p gl’échantillon en sous-groupes (segments), pour construire un arbre dedécision.
Lors de chaque dichotomie, les deux parties sont les plus contrastéesvis-à-vis de la variable à expliquer.
Les premières approches ont été proposées par Sonquist et Morgan(1964) l é h d di A (A i i i )(1964) avec la méthode dite AID (Automatic Interaction Detection).
I Les méthodes de segmentation IntroductionI. Les méthodes de segmentation. Introduction
Les travaux de Breiman , Friedman, Olshen et Stone (1984) connussous le nom de méthode CART ( Classification And RegressionTree) ont donné un nouvel essor à la segmentation.
Notons que les méthodes ne sont pas toujours présentes dans leslogiciels statistiques « classiques » Par contre de nombreux produitslogiciels statistiques « classiques ». Par contre de nombreux produitsspécifiques sont présents sur le marché et connaissent un succèscroissant avec le développement du data mining.
3
I. Les méthodes de segmentation. Introduction
qualitative :Ménage propriétaire de sa résidence Ménage propriétaire de sa résidence
principaleHôtel équipé de la climatisationDiagnostic médicalDiagnostic médical
ARBRE DE DECISIONExpliquer une variable
quantitative :qC.A. d’entreprise/salariéTaux de mémorisation d’une annonceSalaire d’un cadreSalaire d un cadre
REGRESSION PAR ARBRE
I. Les méthodes de segmentation. Introduction
Arbre de décision
T
t1 t2
t3 t4 t5 t6
t7 t8
S t i t édi it : Segments intermédiaires
: Segments terminauxt8
t1
5
II. Les méthodes de segmentation. ExempleII. Les méthodes de segmentation. Exemple
Intéressons-nous à l’audience d’une revue mensuelle auprès d’unéchantillon de 10000 personnes. La variable à expliquer Y est le fait deli d li l L i bl li ti tlire ou de ne pas lire la revue. Les variables explicatives sont aunombre de 6 :
• Sexe (2) : M F• Âge (2) : <20, 20-34, 35-49, 50-64, >=65 ans• Niveau d’études (5) : Primaire, Primaire-Sup, Technique,
Secondaire, Supérieur• CSP (6)( )• Catégorie commune (7)• Région OJD (12)
II. Les méthodes de segmentation. Exemple
Population totale
10 000 1 620162
Segment n° 1
Sexe masculin
Segment n° 2
Sexe féminin
162
4 800 168 5 200 1 45235 279
Segment n° 1
Sexe masculin4 800 168
Segment n° 2Sexe féminin
5 200 1 4524 800 168 5 200 1 452
Segment n° 11 Segment n° 12 Segment n° 21 Segment n° 2235 270
Sexe masculin
Communes ruraleset - de 10 000 habitants
Sexe masculin
+ de 10 000 habitants
Sexe fémininPrimaire,
primaire-supérieur,technique ou commercial
Sexe féminin
Secondaire-supérieur
71 950 36 2 850 132 4 675 1 224
technique ou commercial525 228
18 43426246
II. Les méthodes de segmentation. Exemple
Segment n° 21 Segment n° 22
Sexe féminin
Primaire, etc.
Sexe féminin
Secondaire, supérieur
4 675 1 224 525 228262 434
Segment n° 221 Segment n° 222
Segment n° 211
Sexe féminin P i i
Segment n° 212
Sexe féminin
P i i
Sexe féminin
Secondaire, supérieur
Sexe féminin
Secondaire, supérieur
3 689 922
Primaire, etc.
Province
986 302
Primaire, etc.
Région parisienne
235 87
Communes rurales- de 10 000 habitants
290 141
+ de 10 000 habitants
3 689 922 986 302 235 87 290 141486370306250
II. Les méthodes de segmentation. ExempleII. Les méthodes de segmentation. Exemple
Segment n° 12Sexe masculin
d 10 000 h bi
2 850 132
+ de 10 000 habitants
46
Segment n° 121Sexe masculin
Segment n° 122Sexe masculin
+ de 10 000 habitants
Primaire,i i é i
+ de 10 000 habitants
Technique ou commercial,d i é i
2 215 71
primaire-supérieur
635 61
secondaire, supérieur
32 96
9
III Principe des méthodes
III.1 Les dichotomies
Le nombre de dichotomies possibles d’une variable qualitative à m modalités est égal à : 2m-1-1.m modalités est égal à : 2 1.
Exemple: 4 catégories A, B, C, D.Exemple: 4 catégories A, B, C, D.A,BCD AB,CD B,ACD AC,DBC,ABD AD,BC D,ABC 7 dichotomies
m2m-1-1
21
33
47
515
631
763
8127
9255
10511
111023
122047
10
III Principe des méthodes
Si la variable est à modalités ordonnées, et que l’on souhaite respecter cet ordre lors des dichotomies, m-1 dichotomies sont possiblespossibles.
A,BCD AB,CD ABC,D
III.2 Les étapes de l’algorithme
A chaque étape de la segmentation, pour chaque variable:
il faut chercher sa meilleure dichotomieil faut chercher sa meilleure dichotomieet retenir la meilleure variable.
11
III Principe des méthodesIII Principe des méthodes
III. 3 Les critères
III 3 1 Variable à expliquer quantitative YIII.3.1. Variable à expliquer quantitative Y
Méthode AID (Morgan Sonquist 1963)
L’objectif est d’avoir des moyennes des deux groupes, d’effectifs , les plus différentes possible à chaque coupure.
y y1 2 n n1 2 , p p q p
Maximiser la variance interclasse:
1 2
( ) ( )[ ]Max n y y n n y y n s -1 12
2 22 2/ / /+ −
12
III Principe des méthodesIII Principe des méthodes
( )→ max n n y y1 2 2( )→ − maxns
y y2 1 2
R O t i i i i l i i t lRemarque: On peut aussi minimiser la variance intra-classe
→ + min nn s n
n s112 2
22
n n
Simplification :
Il est inutile avec ce critère d’étudier les dichotomies dechaque variable, suffisent.
2 11m− −m − 1q
En effet, la meilleure dichotomie doit respecter l’ordre des moyennes.On ordonne y y ym1 2, ,...
13Exemple : si n = 12, alors on étudie 11 dichotomies au lieu de 2 047.
III Principe des méthodesIII Principe des méthodes
III.3.2. Variable à expliquer Y qualitative à deux modalités
On calcule le Khi-deux associé à chaque dichotomie possible et on choisit la dichotomie qui maximise ce critère.
( ) ( )22ij i j i j
i, jn n n / n / n n / n⋅ ⋅ ⋅ ⋅χ = −∑
, j
III Principe des méthodes
• Tableau de contingence • Effectifs espérés sous hypothèse d’indépendancehypothèse d indépendance
M F
Lit 168 1452 1620
Ne lit 4632 3748 8380
777,6 842,2
Ne lit pas
4632 3748 8380
4800 5200 100004022,4 4357,6
nij ni.n.j/n
15
III Principe des méthodes
On choisit la dichotomie qui rend le max.χ2On choisit la dichotomie qui rend le max.
Soient f1 et f2 les pourcentages de la première catégorie de Y dans lesdeux groupes
χ
deux groupes.
( ) ( )χ21 2
21 2 1= − × −f f n n nf f/
où ( )f n f n f n= +1 1 2 2 /Il s’agit d’un cas particulier de la méthode AID
( )
→ A I D avec Y =1
0
16
0
III Principe des méthodes
III.4. Les règles d’arrêt.
Elles prennent en compte :
Effectif minimum par segment.
Y quantitative: test de Student comparant les moyennes dans les deux segments .
Y qualitative: Critère du Khi-deux significatif pour un risque α( en général 5%) défini par l’utilisateur.( g ) p
III Principe des méthodes
III.5. Précautions
Méthode très dépendante de l’échantillon
Nécessité de grands échantillons ( environ 1000 observationsNécessité de grands échantillons ( environ 1000 observations au minimum )
Validation sur échantillons testsValidation sur échantillons tests.
18
IV La méthode CART
Méthode proposée par Breiman, Friedman, Ohlsen, Stone
IV. La méthode CART
p p p(1984)
L éth d CART t d t i b d dé i iLa méthode CART permet de construire un arbre de décision binaire par divisions successives de l ’échantillon en deux sous-ensembles.
Contrairement aux autres méthodes de segmentation, elle n’imposeaucune règle d’arrêt de division des segments basée sur uneg gapproche statistique. Elle fournit, à partir de l’arbre binaire complet,la séquence des sous-arbres obtenue en utilisant une procédured’élagage.d élagage.Celle-ci est basée sur la suppression successive des branches les moinsinformatives.
IV La méthode CARTIV. La méthode CART
• Au cours de la phase d’élagage, la méthode sélectionne un sous-arbreoptimal, en se fondant sur l’estimation de l’erreur théoriqued’ ff i d é i i ( éd ti d itè d’i té) àd’affectation ou de prévision (réduction du critère d’impureté) àl’aide soit d’un échantillon-test, quand on dispose de suffisammentd’observations, soit par techniques de validation croisée.
• La meilleure division d* d’un nœud est celle qui assure la plus granderéduction de l’impureté en passant du nœud à ses segmentsréduction de l impureté en passant du nœud à ses segmentsdescendants. Cette notion de maximum absolu est très stricte. Il peutexister en effet des divisions presque aussi bonnes, pouvant jouer unôl i t t i d i t ét ti t i d i i t à lrôle important au niveau des interprétations et qui conduiraient à la
construction d’un arbre différent.
IV. La méthode CART
IV.1 Choix des meilleures divisions: Cas des variables explicatives quantitativesquantitatives
djm = mième
Valeurs ordonnées
de xj
dj mdivision
αm
de xj
dj* = ‘meilleure’
division
α*
La meilleure division pour la variable xj
21
IV La méthode CARTIV. La méthode CART
x1 xj xp d * = ‘meilleure’dj = meilleure division pour xj
d* = ‘meilleure’ division globale
Meilleures divisions pour l ’ensemble des variables
division globale
22
IV La méthode CARTIV. La méthode CART
IV.2 Choix des meilleures divisions: Cas des variables explicatives qualitatives
Selon le nombre de modalités et la présence ou non d ’un ordre logique entre elles, on obtient les possibilités de division :
Une variable binaire fournit une division
Une variable nominale N (k modalités non ordonnées) ( )fournit 2k-1 - 1 divisions
Une variable ordinale O (k modalités ordonnées) fournit k-1 divisions possiblesdivisions possibles
23
IV. La méthode CART
IV.3 Discrimination : critère de division
k k
∑∑Avec r≠ s et où P(r/t) et P(s/t) sont les
• Mesure de l’impureté associée au segment t :
r s i(t) P(r / t)P(s / t)= ∑∑ proportions d ’individus dans les
classes cr et cs dans le segment t ( i(t) est l ’indice de diversité de Gini )( ( ) )
Exemple: Segment tTaille 313 i(t)=2[(135/313) *(178/313)a e 3 3Oui 135Non 178
( ) [( ) ( )
= 0,49056
Segment pur : ne contient que des individus d ’une classe, i(t) = 0Segment mélangé : i(t) ≠ 0. Plus le mélange des classes dans le segment est important plus l’impureté i(t) est élevée
24
est important, plus l impureté i(t) est élevée.
IV. La méthode CART
Réduction de l’impureté
Chaque division d’un segment entraîne une réduction de l’impureté
g g d d i(s, t) i(t) p i(t ) p i(t )Δ = − −
Chaque division d un segment entraîne une réduction de l’impureté
Segment t
tg td
les pg sont les proportions d ’individus du nœud t respectivement dans les segments descendants tg et td (la fonction i(t) étant concave, g g d ( ( )l ’impureté moyenne ne peut que décroître par division d ’un nœud).
25
IV. La méthode CART
Exemple de calcul de l’impuretép p
Segment t taille 313Oui 135Non 178
Segment t taille 202 Segment t taille 111Segment tg taille 202Oui 105Non 97
Segment td taille 111Oui 30Non 81
Δ= 2[(135/313)∗(178∗313)] − (202/313)∗2∗[(105/202)∗(97/202)
(111/313)∗2∗[(30/111)∗(81/111)]− (111/313)∗2∗[(30/111)∗(81/111)]
=0,49056−0,645∗0,4992−0,355∗0,3944
0 028526
=0,0285
IV. La méthode CART
Réduction maximale pour chaque variable
* i(s , t) max{ i(s, t)}Δ = Δ( ) { ( )}
Réduction maximale pour l’ensemble des p variables
*j 1...p * max { i(s , t)}=Δ = Δ
27
IV. La méthode CART
êIV.4 Discrimination : Arrêt des divisions, affectation, taux d’erreur apparent (T.E.A.)
N d t i lNœud terminal :
s’il est pur (il contient des observations toutes identiques)
s’il contient trop peu d’observations
Un segment terminal est affecté à la classe qui est la plusUn segment terminal est affecté à la classe qui est la plus représentée
Taux d ’erreur apparent de classement (T E A) associé àTaux d ’erreur apparent de classement (T.E.A) associé à un segment terminal de l ’arbre T affecté à la classe s:
k p(r/t) = est la proportion d ’individus du
28r 1R(s / t) p(r / t)
=
= ∑p( ) p psegment t affectés à la classe cs et qui appartiennent à la classe cr
IV. La méthode CART
Taux d’erreur associé à l’arbre
n(t)TEA(T) R(s / t)n
= ∑ où n(t) = effectif du segment tt T n∈
∑ segment t
TEA(T) représente la proportion d’individus mal classés dans l’ensemble des segments terminaux.
29
IV. La méthode CART
IV.5 Discrimination : Sélection du meilleur sous-arbre.
Échantillon d’apprentissage:
Construction de l ’arbre complet Tmax puis élagage : à partir deConstruction de l arbre complet Tmax, puis élagage : à partir de l’arbre complet, on détermine la séquence optimale de sous-arbres emboîtés: {T max-1,…Th, …T1} avec 1 ≤ h < max
Le taux d ’erreur apparent (TEA) de Th vérifie :
TEA(T ) min {TEA(T)}= où Sh est l ’ensemble des sous-arbres hh T STEA(T ) min {TEA(T)}∈= h
de Tmax ayant h segments terminaux
Échantillon test:Échantillon test:Choix de T* tel que l ’erreur théorique de classement (ETC) vérifie :
*ETC(T ) min {ETC(T )}30
1 h max hETC(T ) min {ETC(T )}≤ ≤=
IV. La méthode CART
IV.6 Sélection du meilleur sous-arbre par validation croiséeIV.6 Sélection du meilleur sous arbre par validation croisée
Dans le cas d’un échantillon de petite taille il est impossible de sélectionnerl’arbre sur un échantillon d’apprentissage On procède alors par validationl arbre sur un échantillon d apprentissage. On procède alors par validationcroisée.
P édProcédure:
La première étape consiste à déterminer la séquence de sous-arbres emboîtés, à partir du grand arbre Tmax construit à l’aide de l’échantillon total L
La deuxième étape consiste à diviser l’échantillon L en V sous-ensembles, pqui vont permettre de déterminer l’arbre optimal et d’évaluer ses performances
31
Sélection du meilleur sous-arbre par validation croisée. Exemplep p
Présentons cette approche à l’aide d’un exemple développé dansl’ouvrage de Jean-Pierre Nakache et Josiane Confais:« Statistique explicative appliquée » TECHNIP 2003
Les tableaux qui suivent présentent:
1. La séquence de sous-arbres associée à l’arbre Tmax construit q maxsur l’ensemble des données.
2. Les séquences d’élagage construits sur les sous-ensemblesL1 L2 L10L1 L2 ….. L10
3. Le choix du meilleur sous-arbre et l’évaluation de ses performances.
Remarque: La validation présentée utilise la notion de coût-complexité d’un arbre, notion prenant en compte le coût deserreurs de classement et la complexité de l’arbre: nombre de
32
erreurs de classement et la complexité de l’arbre: nombre debranches et de segments.
Sélection du meilleur sous-arbre par validation croisée ExempleSélection du meilleur sous arbre par validation croisée. Exemple
33
Sélection du meilleur sous-arbre par validation croisée ExempleSélection du meilleur sous arbre par validation croisée. Exemple
34
Sélection du meilleur sous-arbre par validation croisée ExempleSélection du meilleur sous arbre par validation croisée. Exemple
35
Sélection du meilleur sous-arbre par validation croisée. Exemple
36
IV. La méthode CART
IV7 Compléments concernant la méthode CART
IV.7.1. Divisions concurrentes et divisions suppléantesLa meilleure division d* d’un nœud est celle qui assure la plus grande
IV.7 Compléments concernant la méthode CART
La meilleure division d* d’un nœud est celle qui assure la plus granderéduction de l’impureté en passant du nœud à ses segmentsdescendants. Cette notion de maximum absolu est très stricte. Il peutexister en effet des divisions presque aussi bonnes pouvant jouer unexister en effet des divisions presque aussi bonnes, pouvant jouer unrôle important au niveau des interprétations et qui conduiraient à laconstruction d’un arbre différent.De façon à apporter des solutions à ce problème deux optionsDe façon à apporter des solutions à ce problème, deux options supplémentaires sont proposées dans l’approche CART :les divisions concurrentes (équi-réductrices dans SPAD) qui
t è d* l l f t éd ti d l’i té Ellassurent, après d* les plus fortes réductions de l’impureté. Ellespermettent d’intervenir sur le choix de la meilleure variableexplicative. On peut définir la première division concurrente, puis ladeuxième et ainsi de suitedeuxième et ainsi de suite.
IV. La méthode CART
les divisions suppléantes ( équi-divisantes dans SPAD) qui fournissentles répartitions les plus proches de la division d*. Elles permettent de gérerl’existence de données manquantes dans l’affectation d’un nouvel individuà une classe.Quand pour un individu une donnée est manquante pour une variabledivisant un segment, on cherche la variable la remplaçant au mieux.Comme pour les divisions équi-réductrices, il est possible de définir lapremière, la deuxième,…, meilleure division suppléante.
IV7 2 C ût d l tIV.7.2. Coût de classementIl est possible d’associer des coûts aux erreurs de classement.
38
V. Comparaison des méthodes de segmentation avec les p gautres méthodes de discrimination et de classement
La segmentation n’est pas vraiment multidimensionnelle au sensgéométrique du terme ( pas de calcul de distance comme en analyseg q ( p yfactorielle discriminante ).
P ili l i bl li i di i ll lPar contre on utilise les variables explicatives conditionnellement lesunes par rapport aux autres. On peut donc parfois atteindre des effetsd’interaction assez difficiles à saisir par d’autres méthodes. Ceci nesignifie d’ailleurs pas qu’ils sont tous étudiés.
V 1 Avantages des méthodes de segmentation :V.1 Avantages des méthodes de segmentation :
’ i é l’ b d dé i i bi i li ibll’ergonomie des résultats : l’arbre de décision binaire est lisible partout utilisateur et constitue à ce titre un moyen de communication desrésultats très apprécié.la mixité des variables qu’accepte la procédure : variables nominales,ordinales, continues peuvent être mélangées au niveau des variablesexplicativesexplicatives .la validation par une méthode de rééchantillonnage est une destechniques de validation les plus transparentes pour l’utilisateur.la robustesse de la méthode vis à vis des valeurs extrêmes et desdonnées erronées.
V 2 Incon énients des méthodes de segmentation :V.2 Inconvénients des méthodes de segmentation :
On doit également reconnaître aux méthodes de segmentation un certainb d i t f ibl i d t tili ti l inombre de points faibles, qui rendent son utilisation exclusive
insuffisante.
l’aspect séquentiel est redoutable : les covariations qui servent àsélectionner les variables ne mesurent pas un lien causal et une variablepeut en cacher une autre beaucoup plus fondamentale, qui n’apparaîtrapas dans la suite du processus.Les divisions de réserve ( concurrentes et suppléantes ) sont là pourLes divisions de réserve ( concurrentes et suppléantes ) sont là pourpallier partiellement cet inconvénient. L’approche par segmentation perdalors en simplicité. En effet l’utilisateur est alors souvent déconcerté parl’instabilité des arbres obtenusl instabilité des arbres obtenus.De nouvelles pratiques apparaissent pour tenter d’apporter des solutionsà ce problème: Bagging , Boosting.
La sélection des variables présente un léger biais du fait que lesp g qvariables explicatives ayant un plus grand nombre de modalités, enoffrant plus de divisions possibles, sont plus souvent sélectionnées.
Il se peut que la nature du phénomène étudié fasse que descombinaisons linéaires (après éventuel recodage) soient optimales pourprévoir la variable étudiée (ou son logit ou toute autre fonction).
Les méthodes de segmentation nécessitent des échantillons deLes méthodes de segmentation nécessitent des échantillons de
grande taille.
V.3 NOUVELLES PRATIQUES
BAGGING
Un arbre T est construit à partir de l’échantillon « boostrapé » EB qui fournitUn arbre Tt est construit à partir de l échantillon « boostrapé » EBt qui fournitune règle de décision Rt conduisant à une estimation ct du coût associé àl’arbre Tt. La règle de décision finale R* est fournie par l’agrégation des règlesR (t 1 2 ) Ai i l i di id t l l k tRt (t= 1,2…n). Ainsi pour classer un individu x, un vote pour la classe k estenregistré pour chaque règle Rt, pour laquelle Rt(x)= k et R*(x) est alors laclasse avec le plus de votes (classe majoritaire)
Breiman rapporte dans deux articles les résultats de cette méthode obtenus sur7 fichiers de taille moyenne. En utilisant 50 échantillons « boostrapés », le coûtmoyen de la règle R* est égal au coût de la règle obtenu en utilisantmoyen de la règle R* est égal au coût de la règle, obtenu en utilisantuniquement l’échantillon de base, multiplié par une valeur a comprisedans l’intervalle [0,57 ; 0,94].
43
V3 NOUVELLES PRATIQUESV.3 NOUVELLES PRATIQUES
BAGGING
Un cas particulier de bagging est celui appliqué à des arbres dedécision avec introduction d’un tirage aléatoire parmi lesvariables explicatives. On a dans ce cas une double randomisation
BOOSTING ( algorithme Adaboost 1999)
variables explicatives. On a dans ce cas une double randomisationet on parle de forêts aléatoires ( Breiman 2001)
BOOSTING ( algorithme Adaboost 1999)
L’idée est de générer plusieurs règles d’affectation d’un individu. Dans laconstruction de la deuxième règle, une attention particulière est portéeg , p paux individus mal classés par la première règle pour essayer de lesclasser correctement, et ainsi de suite.
En général dix règles permettent de réduire le nombre d’erreurs del’échantillon test d’environ 25%.
44
VI .Conclusions.
La validation ( validation croisée ou utilisation d’un échantillon test ) est un aspect les plus importants lors de la mise en œuvre des méthodes de segmentation et de discriminationméthodes de segmentation et de discrimination. Utiliser plusieurs techniques.
Nouvelles méthodes:Analyse discriminante PLS et régression logistique PLS.F êt lé t iForêts aléatoires.
Recommended