Méthodes de segmentation

Michel Tenenhaus

1
 Les données
- Numérique
Réponse : Y - Ordinale
- Nominale
découpé en 10 classes,
- Numérique puis considéré comme
Prédicteurs : X1,…, Xk - Ordinale ordinale
- Nominale

Objectif :

• Construire un arbre de décision à l’aide des prédicteurs.

• Les segments terminaux sont aussi purs que possible par
rapport à la réponse Y.
2
 Les méthodes

• CHAID : Chi-squared Automatic

Interaction Detector
• CART : Classification And Decision Tree
• SIPINA : Système Interactif pour les
Processus d’Interrogation Non-Arborescent

3
 Exemple : Référendum sur la
constitution européenne
Vote Confiance
Proximité
constitution Sexe Classe d'age Dernier diplôme en son
politique
européenne avenir
Oui Femme 25-34 PS Bac+3/4 Confiant+
Oui Homme 60 et + PS < Bac Confiant-
Oui Femme 35 à 44 ans UMP Bac+3/4 Nsp
Oui Homme 45-59 PS Bac Confiant++
Oui Femme 35 à 44 ans UMP Bac+5/Grande école Confiant++
Oui Homme 25-34 UMP Bac Confiant+
Oui Femme 25-34 UMP Bac Confiant+
Oui Homme 35 à 44 ans PS Bac+5/Grande école Confiant+
Oui Femme 35 à 44 ans UDF Pas de diplôme Confiant+
Oui Homme 45-59 UDF < Bac Confiant--
Oui Homme 25-34 UMP Bac+5/Grande école Confiant+
Oui Homme 60 et + UMP < Bac Confiant+
Oui Femme 35 à 44 ans PS < Bac Confiant+
Oui Homme 18-24 UMP Bac+3/4 Confiant-
Oui Femme 35 à 44 ans PS Bac+2 Confiant-
Oui Femme 18-24 Verts Bac Confiant++
Oui Femme 60 et + UMP < Bac Confiant+
Oui Homme 35 à 44 ans PS Bac+2 Confiant+
Oui Homme 60 et + UMP < Bac Confiant+
4
 C la sse d'age * Vote cons titution européenne
Sexe * Vote constitution européenne % w ithin Classe d'age
% within Sexe Vote co nstitutio n
eu ropée nne
Vote constitution
européenne N on Oui
Classe 18-24 59 .8 % 40.2%
Non Oui d'ag e 25-34 55 .8 % 44.3%
SexeHomme56.1% 43.9%
Femme 35 à 4458an s% 41.2%
.8
53.2% 46.8%
Total 45-59 59 .7 % 40.3%
54.7% 45.3%
60 et + 42 .9 % 57.1%
Tota l 54 .7 % 45.3%
Khi-deux=1.936, NS=.164

Khi-deux=43.62, NS=.000

Proximité politique * Vote constitution européenne

Revenu foyer * Vote constitution européenne
% within Proximité politique
% within Revenu foyer
Vote constitution
Vote constitution
européenne
européenne
Non Oui
Non Oui
Proximité
EG 94.9% 5.1%
Revenu < 1 000 Euros
59.0% 41.0%
politique
PC 98.4% 1.6% foyer 1 000-1 200 €
66.0% 34.0%
PS 58.8% 41.2%
1 200-1 400 €
66.9% 33.1%
Verts 65.8% 34.2%
1 400-1 700 €
60.4% 39.6%
UDF 23.9% 76.1%
1 700-2 000 €
64.4% 35.6%
UMP 22.5% 77.5%
2 000-2 300 €
54.5% 45.5%
MPF 75.0% 25.0%
2 300-3 000 €
58.5% 41.5%
MNR 58.3% 41.7%
3 000-4 500 €
46.1% 53.9%
FN 96.8% 3.2%
> 4 500 €25.3% 74.7%
Aucun partI
71.2% 28.8%
Nsp 54.9% 45.1%
Nsp 56.9% 43.1%
Refus 37.5% 62.5%
Refus 30.0% 70.0%
Total 54.7% 45.3%
Total 54.7% 45.3%

Khi-deux=112.5, NS=.000 5
Khi-deux=536.3, NS=.000
Dernier diplôme * Vote constitution européenne
Confiance en son avenir * Vote constitution européenne
% within Dernier diplôme
Vote constitution % within Confiance en son avenir
européenne Vote constitution
Non Oui européenne
Dernier< Bac 64.5% 35.5% Non Oui
diplômeBac 55.9% 44.1% Confiance Confiant++ 30.2% 69.8%
Bac+2 48.8% 51.2% en son Confiant+ 31.7% 68.3%
Bac+3/4 42.2% 57.8% avenir Confiant- 74.1% 25.9%
Bac+5 et plus 29.6% 70.4% Confiant-- 90.7% 9.3%
Pas de diplôme66.9% 33.1% Ns p 43.3% 56.7%
NSP 50.0% 50.0% Total 54.7% 45.3%
Total 54.7% 45.3%

Khi-deux = 545.3, NS = .000

Khi-deux=123.6, NS=.000

Tableau croisé Khi-deux et p-value

Vote*Sexe 1.94 (p = .164)
Vote*Age 43.6 (p = .000)
Vote*[Proximité politique] 536.3 (p = .000)
Vote*[Revenu foyer] 112.5 (p = .000)
Vote*Diplôme 123.6 (p = .000)
Vote*[Confiance en son avenir] 545.3 (p= .000)
6
 Utilisation de CART

Model Summary
Specifications Growing Method CRT
Dependent Variable Vote constitution européenne
Independent Variables Sexe, Classe d'age, Proximité politique,
Revenu foyer, Dernier diplôme , Confiance en
son avenir
Validation None
Maximum Tree Depth 5
Minimum Cases in
50
Parent Node
Minimum Cases in
30
Child Node
Results Independent Variables Confiance en son avenir, Proximité politique,
Included Dernier diplôme , Revenu foyer, Sexe
Number of Nodes 9
Number of Terminal
5
Nodes
Depth 3

Élagage avec la règle de un écart-type

7
8
 Présentation de CHAID
1. Mesures de liaison entre deux variables X et Y
X qualitative à I modalités
Nature de Y Loi sous
Test d’indépendance :
- X * Y  [nij ] Modèle
Statistique utilisée
l’hypothèse
d’indépendance
- mij  E (nij ) 1. Modèle d’indépendance :
n  mˆ ij 
2
Log (mij )    iX   Yj
-  2  
ij
ni.n. j Nominale 2. Modèle saturé : mˆ ij
- mˆ ij  (J modalités)
i j

nij
2[(I-1)(J-1)]
n Log (mij )    iX   Yj  ijXY - G  2 nij Log (
2
)
mˆ ij
- mˆˆ ij  estimation
i j
Test H0 : ijXY  0, i, j
3. Modèle d’association :
de mij à l'aide du Log (mij )
mˆˆ ij
Ordinale X Y
   i    xi ( y j  y ) H  2 nij Log ( )
2
2(I-1)
modèle 3 estimé j
i j mˆ ij
Test H 0 : x1  ...  xI  0
par MV
Analyse de la variance à un
Numérique F F(I-1,n-I)
facteur

9
2. Description d’une étape de CHAID sur un segment

1. Phase de fusion

Pour chaque prédicteur Xj :

- Fusion des modalités i et i’ de Xj telles que les profils

Prob(Y/Xj=i) et Prob(Y/Xj=i’) sur le segment sont voisins.
- Si Xj est ordinale, seules des modalités adjacentes sont
autorisées à fusionner.

- D’où des nouveaux prédicteurs Xj*.

10
 Description d’une étape de CHAID sur un segment

2. Phase de division
Pour chaque prédicteur Xj :

- Étude des tableaux croisés Xj*Y :

Calcul de la p-value du test d’indépendance, éventuellement corrigée pour
tenir compte du nombre de modalités (Mutiplicateur de Bonferroni).
- Sélection du prédicteur Xj* ayant la plus petite p-value et division du
segment selon ce prédicteur.

11
Description d’une étape de CHAID sur un segment

3. Règle d’arrêt basées sur des critères

- Segment pur
- Prédicteurs constants sur le segment
- Taille du segment
- Taille des segments descendants
- Profondeur de l’arbre
- Valeur de la p-value minimum

12
Étude danoise sur la prospérité (Source : Croux, 2005)

Congélateur
Numéro Secteur Revenu Age Sexe
Oui Non
1 Privé Elevé Agé Masculin 152 39
2 Public Elevé Agé Masculin 82 18
3 Privé Moyen Agé Masculin 135 31
4 Public Moyen Agé Masculin 35 12
5 Privé Bas Agé Masculin 89 45
6 Public Bas Agé Masculin 20 9
7 Privé Elevé Jeune Masculin 259 46
8 Public Elevé Jeune Masculin 101 26
9 Privé Moyen Jeune Masculin 183 55
10 Public Moyen Jeune Masculin 54 15
11 Privé Bas Jeune Masculin 108 54
12 Public Bas Jeune Masculin 22 13
13 Privé Elevé Agé Féminin 82 17
14 Public Elevé Agé Féminin 85 16
15 Privé Moyen Agé Féminin 46 16
16 Public Moyen Agé Féminin 60 11
17 Privé Bas Agé Féminin 29 29
18 Public Bas Agé Féminin 40 18
19 Privé Elevé Jeune Féminin 160 23
20 Public Elevé Jeune Féminin 152 28
21 Privé Moyen Jeune Féminin 89 17
22 Public Moyen Jeune Féminin 56 21
23 Privé Bas Jeune Féminin 57 41
24 Public Bas Jeune Féminin 34 28
13
Utilisation de CHAID pour Y binaire

Model Summary
Specifications Growing Method CHAID
Dependent Variable congelateur
Independent Variables revenu, age, sexe, secteur
Validation None
Maximum Tree Depth 3
Minimum Cases in
100
Parent Node
Minimum Cases in
50
Child Node
Results Independent Variables
revenu, sexe
Included
Number of Nodes 6
Number of Terminal
4
Nodes
Depth 2

Pas de correction de Bonferroni

14
15
 Étude Mali
Test de l’efficacité du diffuseur d’iode RHODIFUSE

Conséquences biologiques du
déficit en iode :
Chez l’enfant :
- Retard mental
- Troubles musculaire
- Paralysie
- Crétinisme

Chez l’adulte :
- Goitre
- Adynamie
- Crétinisme
- Hypoproductivité

16
 Classification des goitres selon l ’OMS

• Groupe 0 : Thyroïde non palpable, ou palpable mais dont les

lobes sont de volume inférieur à la phalange distale du pouce
du sujet.
• Groupe 1A : Nettement palpable, et dont les lobes ont un
volume supérieur à la phalange distale du pouce du sujet, non
visible lorsque la tête est en extension.
• Groupe 1B : Idem, mais visible en extension du cou, mais non
visible en position normale.
• Groupe 2 : Thyroïde nettement visible lorsque la tête est en
position normale.
• Groupe 3 : Thyroïde volumineuse, nettement visible à plus de 5
mètres.

17
 L’expérimentation
N’Djiba

17 Sirablo (Témoin)

19 6
15
4 2
Sebabougou 15
5 Bamako
Woloni

7 37
Niger

18
 Les données

• Y = Niveau de goitre : 1= 0, 2 = IA, 3 = IB, 4 = II

• X1 = Village : 1 = Sirablo (Témoin), 2 = Woloni

3 = N ’Djiba, 4 = Sebabougou

• X2 = Sexe : 1 = Homme, 2 = Femme

• X3 = Jour : 0 = 0, 1 = 180, 2 = 360

• X4 = Iode : 1 = Absence, 2 = Présence

19
 Les données (en effectif)
Répartition des goitres par niveau

VILLAGE SEXE JOUR IODE G1 G2 G3 G4 Total

1 Sirablo Homme 0 Absence 106 12 46 11 175
2 Sirablo Homme 180 Absence 60 31 46 15 152
3 Sirablo Homme 360 Absence 64 23 50 14 151
4 Sirablo Femme 0 Absence 77 21 71 65 234
5 Sirablo Femme 180 Absence 46 28 63 65 202
6 Sirablo Femme 360 Absence 44 29 67 57 197
7 Woloni Homme 0 Absence 127 27 45 12 211
8 Woloni Homme 180 Présence 145 28 19 1 193
9 Woloni Homme 360 Présence 161 16 12 2 191
10 Woloni Femme 0 Absence 69 21 65 50 205
11 Woloni Femme 180 Présence 76 40 41 13 170
12 Woloni Femme 360 Présence 89 28 33 10 160
13 N'Djiba Homme 0 Absence 91 8 14 6 119
14 N'Djiba Homme 180 Présence 94 14 10 0 118
15 N'Djiba Homme 360 Présence 99 7 12 0 118
16 N'Djiba Femme 0 Absence 42 18 45 34 139
17 N'Djiba Femme 180 Présence 50 29 38 13 130
18 N'Djiba Femme 360 Présence 67 18 32 6 123
19 Sebabougou Homme 0 Absence 112 47 30 13 202
20 Sebabougou Homme 180 Présence 155 26 10 1 192
21 Sebabougou Homme 360 Présence 171 12 12 2 197
22 Sebabougou Femme 0 Absence 86 40 47 55 228
23 Sebabougou Femme 180 Présence 119 26 39 18 202
24 Sebabougou Femme 360 Présence 132 12 41 22 207

20
 Les données (en fréquence)
Fréquence de répartition des goitres

VILLAGE SEXE JOUR IODE Goitre 1 Goitre 2 Goitre 3 Goitre 4

1 Sirablo Homme 0 Absence .61 .07 .26 .06
2 Sirablo Homme 180 Absence .39 .20 .30 .10
3 Sirablo Homme 360 Absence .42 .15 .33 .09
4 Sirablo Femme 0 Absence .33 .09 .30 .28
5 Sirablo Femme 180 Absence .23 .14 .31 .32
6 Sirablo Femme 360 Absence .22 .15 .34 .29
7 Woloni Homme 0 Absence .60 .13 .21 .06
8 Woloni Homme 180 Présence .75 .15 .10 .01
9 Woloni Homme 360 Présence .84 .08 .06 .01
10 Woloni Femme 0 Absence .34 .10 .32 .24
11 Woloni Femme 180 Présence .45 .24 .24 .08
12 Woloni Femme 360 Présence .56 .18 .21 .06
13 N'Djiba Homme 0 Absence .76 .07 .12 .05
14 N'Djiba Homme 180 Présence .80 .12 .08 .00
15 N'Djiba Homme 360 Présence .84 .06 .10 .00
16 N'Djiba Femme 0 Absence .30 .13 .32 .24
17 N'Djiba Femme 180 Présence .38 .22 .29 .10
18 N'Djiba Femme 360 Présence .54 .15 .26 .05
19 Sebabougou Homme 0 Absence .55 .23 .15 .06
20 Sebabougou Homme 180 Présence .81 .14 .05 .01
21 Sebabougou Homme 360 Présence .87 .06 .06 .01
22 Sebabougou Femme 0 Absence .38 .18 .21 .24
23 Sebabougou Femme 180 Présence .59 .13 .19 .09
24 Sebabougou Femme 360 Présence .64 .06 .20 .11
21
Évolution des niveaux moyens de goitre
SIRABLO (Témoin) WOLONI
2.8 2.6

2.4
2.6
2.2

2.4
2.0

Niveau moyen de goitre

Niveau moyen de goitre

2.2 1.8

1.6
2.0
SEXE 1.4 SEXE
1.8
Homme 1.2 Homme

1.6 Femme 1.0 Femme

0 180 360 0 180 360

JOUR JOUR

N'DJIBA SEBABOUGOU
2.6 2.6

2.4 2.4

2.2 2.2

2.0 Niveau moyen de goitre 2.0

Niveau moyen de goitre

1.8 1.8

1.6 1.6

1.4 SEXE 1.4 SEXE

1.2 Homme 1.2 Homme

1.0 Femme 1.0 Femme

0 180 360 0 180 360

JOUR JOUR
22
Utilisation
de CHAID
pour Y ordinale
Population des
hommes

23
Population des
femmes

24
 École de Management Avancé

P
r
o
fe
ss
e
urI
n
di
ceA
g
e S
e
xeE
M
A D
o
c
to
r
atD
i
r
ect
eu
rR
ec
h
er
c
heP
éd
a
go
g
ie
1 2
0 6
0 M0 1 1 2 4
2 2
0 5
3 M0 1 1 3 3
3 2
0 5
2 M1 1 1 2 4
4 2
0 5
0 M0 1 0 5 4
5 2
0 4
8 M0 1 0 5 4
6 2
0 4
8 M1 1 1 1 4
7 1
9 5
5 M0 0 0 1 4
        
9
4 3 4
6 F 0 1 0 1 3
9
5 3 3
0 M 1 0 0 1 4
9
6 1 4
4 M 0 1 0 1 1

25
Utilisation de CHAID pour Y numérique
Model Summary
Specifications Growing Method CHAID
Dependent Variable Indice
Independent Variables Age, Homme, EMA, Doctorat, Directeur,
Pédagogie, Recherche
Validation None
Maximum Tree Depth 3
Minimum Cases in
10
Parent Node
Minimum Cases in
5
Child Node
Results Independent Variables
Age, EMA, Pédagogie, Recherche
Included
Number of Nodes 10
Number of Terminal
6
Nodes
Depth 3

Avec de correction de Bonferroni

26
27
 Présentation de CART
Exemple : Crédit
On observe sur n = 323 personnes :

Réponse Y : Credit ranking (good/bad)

4 prédicteurs X :
- X1 = Classe d’age (young, middle, old)

- X2 = Has AMEX card (yes/no)

- X3 = Paid Weekly/Monthly (weekly pay/monthly salary)

- X4 = Social Class (management, professional, clerical,

skilled, unskilled). 28
 Mesures de liaison entre X binaire et Y
Y nominale : le critère Gini
Mesure de l’impureté d’un segment : Indice de Gini
i (t )   p ( j | t ) p (k | t )
j ,k
j k
Entropie
  p( j | t ) 1  p( j | t ) 
j quadratique
 1    p( j | t ) 
2

où p(j|t) = fréquence de la modalité j de Y sur le segment t

1
Résultat : 0  i (t )  1 
J 29
 Exemple

Impureté = Prob(Bad)*Prob(Good) + Prob(Good)*Prob(Bad)

 .5201*.4799  .4799*.5201  .49919198
 1  .52012  .47992
1
 1   .5
2

Segment très impur 30

 Division d’un segment
Segment t
Effectif = nt
Impureté i(t)

X=1 X X1  a

Segment tgauche Segment tdroit

Effectif = ntgauche Effectif = ntdroit
Impureté i(tgauche) Impureté i(tdroit)

Diminution de l’impureté = mesure de liaison entre X et Y

ntg ntd
 Gini (t g , td )  i (t )  i (t g )  i (t d )
Critère nt nt
Gini ntg ntd  2
 2    p( j | t g )  p( j | td )  
 
nt  j  31
 Exemple

(0) i(0)=.49919198

(1) (2)

i(1)=.23106222 i(2)=.26634552
Diminution de l’impureté = Critère de Gini
n1 n
i (0)  i (1)  2 i (2)
n n
 .4992  .5108  .23106  .4892  .26635
32
 .2508
Y nominale : le critère Twoing
Segment t
Effectif = nt

X=1 X X=0

Segment tgauche Segment tdroit

Effectif = ntgauche Effectif = ntdroit

2
ntg ntd  
Twoing (t g , td )  2   p( j | t g )  p( j | t d ) 
nt  j 
33
Y ordinale : le critère Ordered Twoing
Segment t
Effectif = nt

X=1 X X=0

Segment tgauche Segment tdroit

Effectif = ntgauche Effectif = ntdroit

ntg ntd
Max  p(Y  j | t g )  p(Y  j | td ) 
2
 Ordered Twoing (t g , td )  2
nt
j

34
Y numérique : le critère LSD
(Least Square Deviation)

Segment t
Effectif = nt

X=1 X X=0

Segment tgauche Segment tdroit

Effectif = ntgauche Effectif = ntdroit

ntg ntd 2
(t g , td )  2
 y (t g )  y (td ) 
nt

35
 Construction de l’arbre maximum TMax

• On part de l’échantillon de base t0.

• Pour chaque prédicteur Xj, on cherche la dichotomie
des modalités de Xj conduisant à deux segments
descendants tg et td maximisant (tg,td).
• Si X est nominale, la dichotomie est quelconque.
• Si X est ordinale, la dichotomie est {[X  i],[X > i]}
• On itère la procédure sur chaque segment descendant.
• La procédure est stoppée en fonction de règles d’arrête
définies par l’utilisateur.
36
 Exemple Crédit
Credit ranking (1=Good)

Règles d’arrêt : Node 0

Category % n
- Improvement minimum = 0.01 Good
Bad
47.99
52.01
155
168

- Effectif segment parent minimum = 25 Total (100.00) 323

Paid Weekly/Monthly
- Effectif segment descendant minimum = 1 Improvement=0.2508

Monthly salary Weekly pay

Node 1 Node 2
Category % n Category % n
Good 84.18 133 Good 13.33 22
Bad 15.82 25 Bad 86.67 143
Total (48.92) 158 Total (51.08) 165

Age Categorical Age Categorical

Improvement=0.0484 Improvement=0.0340

Young (< 25) Middle (25-35);Old ( > 35) Middle (25-35);Young (< 25) Old ( > 35)

Node 3 Node 4 Node 5 Node 6

Category % n Category % n Category % n Category % n
Good 51.02 25 Good 99.08 108 Good 9.49 15 Good 100.00 7
Bad 48.98 24 Bad 0.92 1 Bad 90.51 143 Bad 0.00 0
Total (15.17) 49 Total (33.75) 109 Total (48.92) 158 Total (2.17) 7

Social Class
Improvement=0.0142

Professional Clerical;Management

Node 7 Node 8
Category % n Category % n
Good 41.46 17 Good 100.00 8 37
Bad 58.54 24 Bad 0.00 0
Total (12.69) 41 Total (2.48) 8
 Les règles d’arrêt
• Les prédicteurs sont constants sur le segment.
• Le segment est pur.
• Profondeur de l’arbre égale au maximum spécifié.
• Taille du segment < minimum spécifié (ici 20).
• Taille du sous-segment < minimum spécifié (ici 5).
• Diminution de l’impureté < minimum spécifié
(ici .0001).

38
 Risque global
• Chaque segment terminal est affecté
à la modalité de Y la plus fréquente
dans le segment.

• Risque = % de mal classés

39
Tableau de classification et risque global

Misclassification Matrix

Actual Category
Good Bad Total
Predicted Category Good 123 1 124
Bad 32 167 199
Total 155 168 323

Resubstitution
Risk Estimate 0.102167 33 / 323
SE of Risk Estimate 0.016852

.102167  (1  .102167)
323 40
 Tableau des gains

nt
nt - Gain = Nb de réponses cibles dans le segment t
n
- Gain (%) = % de réponses cibles de l’échantillon
total dans le segment t
- Resp (%) = % de réponses cibles dans le segment t

Proportion de réponses cibles dans le segment t

- Index (%) =
Proportion de réponses cibles dans l'échantillon total

41
 Élagage (Pruning)
• On construit l’arbre maximum Tmax.
• On recherche le plus petit arbre T dont le risque
de mauvaise classification
n   max nk (t )
tT
k Nb de mal classés
C (T )  
n n

est peu supérieur à celui de l’arbre complet.

(T = ensemble des segments terminaux)

42
 Mesure de coût-complexité C(T)
C (T )  C (T )   T

- T = Nombre de segments terminaux de l'arbre T

-  = Pénalité attribuée à chaque segments terminal

- T ( ) = Arbre construit dans la phase de construction
de Tmax minimisant C (T )
- T (0) = Tmax arbre de complexité maximum
- Plus  augmente, plus le nombre de segments
terminaux de T ( ) diminue. 43
 L’algorithme d’élagage de CART
- Soit Tracine = Segment racine = Echantillon de base.
- L'algorithme de CART permet de construire
une suite d'arbres emboités Tk  T ( k ) :

Tmax  T1  T2  T3  ...  Tracine

correspondant à une suite croissante de

pénalités de complexité k :

0  1   2   3  ...
44
 Choix de l’arbre à retenir
- Calcul des risques de mauvaise classification
de la suite de sous-arbres :
C (Tmax )  C (T1 )  C (T2 )  ...  C (Tracine )

- Calcul de l'écart-type de C (Tmax ) :

C (Tmax )  1  C (Tmax ) 
Ecart-type C (Tmax )  
n

- Choix de l'arbre T j ayant le plus petit nombre

de segments terminaux et vérifiant :
Par défaut
C (T j )  C (Tmax ) + *Ecart-type C (Tmax ) 
=1 45
 Exemple : Qualité des vins de Bordeaux

Variables observées sur 34 années (1924 - 1957)

• TEMPERATURE : Somme des températures

moyennes journalières
• SOLEIL : Durée d’insolation
• CHALEUR : Nombre de jours de grande chaleur
• PLUIE : Hauteur des pluies
• QUALITE DU VIN : Bon (1), Moyen (2), Médiocre (3)

46
Les données
Température Soleil Chaleur Pluie Qualité
1 3064 1201 10 361 2
2 3000 1053 11 338 3
3 3155 1133 19 393 2
4 3085 970 4 467 3
5 3245 1258 36 294 1
6 3267 1386 35 225 1
7 3080 966 13 417 3
8 2974 1189 12 488 3
9 3038 1103 14 677 3
10 3318 1310 29 427 2
11 3317 1362 25 326 1
12 3182 1171 28 326 3
13 2998 1102 9 349 3
14 3221 1424 21 382 1
15 3019 1230 16 275 2
16 3022 1285 9 303 2
17 3094 1329 11 339 2
18 3009 1210 15 536 3
19 3227 1331 21 414 2
20 3308 1366 24 282 1
21 3212 1289 17 302 2
22 3361 1444 25 253 1
23 3061 1175 12 261 2
24 3478 1317 42 259 1
25 3126 1248 11 315 2
26 3458 1508 43 286 1
27 3252 1361 26 346 2
28 3052 1186 14 443 3
29 3270 1399 24 306 1
30 3198 1259 20 367 1
31 2904 1164 6 311 3
32 3247 1277 19 375 1
33 3083 1195 5 441 3
34 3043 1208 14 371 3 47
Arbre de taille
maximale T1

48
T2 T3

T4 T5

49
Q u e l a rb re fa u t-il c h o is ir ? C a lc u lo n s le s c o û ts d ’e rre u r d e c la s s e m e n t (o u p ro p o rtio n s d e m a l
c la s s é s ) a s s o c ié s à c e s d iffé re n ts a rb re s :

A rb re P é n a lité  C o û t
T 1 = T m ax 0 2 /3 4 = .0 5 8 8
T 2 .0 2 9 4 /3 4 = .1 1 7 6
T 3 .0 5 9 6 /3 4 = .1 7 6 4
T 4 .1 4 7 1 1 /3 4 = .3 2 3 5
T 5 = T r a c in e .3 2 4 2 2 /3 4 = .6 4 7 0

Ic i l’é c a rt-ty p e d u c o û t d e l’a rb re d e ta ille m a x im a le v a u t

.0 5 8 8  (1  .0 5 8 8 )
E T (C (T m a x ))   .0 4 0 3
3 4

L a rè g le d u « u n é c a rt-ty p e » c o n d u it d o n c à s é le c tio n n e r le p lu s p e tit a rb re T j te l q u e

C (T j)  C (T m a x )  E T (C (T m a x ) )  .0 5 8 8  0 .0 4 0 3  .0 9 9 1

D ’o ù la s é le c tio n d e l’a rb re T m ax. S i l’o n a p p liq u e la rè g le d u « d e u x é c a rts -ty p e s » , o n u tilis e

le s e u il .1 3 9 4 e t o n e s t a lo r s a m e n é à s é le c tio n n e r l’ a rb r e T 2 . P o u r tro is é c a rts - ty p e s , le s e u il
50
d e v ie n t .1 7 9 7 e t l’ a r b r e s é le c tio n n é d e v ie n t T 3 .
 Présentation de SIPINA
Exemple : Titanic
Survivant Pourcentage
Classe Age Sexe de
Oui Non survivants
M 57 118 33
Adulte
F 140 4 97
Première
M 5 0 100
Enfant
F 1 0 100
M 14 154 8
Adulte
F 80 13 86
Deuxième
M 11 0 100
Enfant
F 13 0 100
M 75 387 16
Adulte
F 76 89 46
Troisième
M 13 35 27
Enfant
F 14 17 45
M 192 670 22
Equipage Adulte
F 20 3 87

51
 Mesure de liaison entre X et Y nominale

Mesure de l’impureté (entropie, incertitude)

d’un segment t : Indice de Gini corrigée

 n j (t ) 
2 Indépendant
i (t )  1    p ( j | t )  1   
2
Dans CART :  de la taille
j j  n(t ) 
du segment

 n j (t )   
2 Diminue lorsque la
Dans SIPINA : i (t )  1     taille du segment
j  n(t )  J  
augmente

Le paramètre  est fixé automatiquement par SIPINA.

52
Le graphe latticiel de SIPINA
Survie au naufrage du Titanic

53
 Mesure de liaison entre X et Y nominale

Mesure de l’incertitude
sur une partition K
n(tk )  n
 j k(t )    
2

i ( S )   1     
S = {t1,…, tK} de k 1 n 
 j  n(tk )  J   

l’échantillon de base t0

Mesure de l’incertitude
I
ni   n
 ij    
2
sur une partition induite par X i ( S X )   1     
SX = {t1=[X=1],…, tI=[X=I]} i 1 n  j  ni   J   
 
de l’échantillon de base t0

Mesure de la force
de la liaison entre X et Y : I (t0 , S X )  i (t0 )  i ( S X )
Gain sur l’incertitude 54
 Description de l’algorithme SIPINA
Recherche de la partition S1
• La partition initiale S0 est formée de l’échantillon
de base.
• Le paramètre  est fixé de manière automatique.
• Recherche de la variable Xj conduisant à la
meilleure partition S1, soit maximisant le gain sur
l’incertitude
I ( S0 , S X j )  i ( S0 )  i ( S X j )
55
 Description de l’algorithme SIPINA
Opérations de base pour le passage
de la partition Si à Si+1

• Éclatement : Un segment t de Si est divisé à l’aide

d’un prédicteur X en I segments th = t[X = h].
D’où : Si+1 = Si – {t} + {t1}+…+{tI}.
• Fusion : On fusionne les deux segments tq et tr de Si.
D’où : Si+1 = Si – {tq}{tr } + tqtr .

• Partition admissible : Si+1 est admissible si

Gain sur I ( Si , Si 1 )  i ( Si )  i ( Si 1 )  0
l’incertitude
56
Exemples des opérations de base sur Titanic
Éclatement :

S1

Fusion :

S3

57
 Exemple sur Titanic
Fusion :

58
 Description de l’algorithme SIPINA
Passage de la partition Si à Si+1
• Fusion : On fusionne les deux segments de Si conduisant à une partition S'i+1
maximisant le gain sur l’incertitude I(Si,S'i+1). Si gain > 0, on pose Si+1=
S'i+1 et on repasse une étape de fusion. Sinon, passage à la phase suivante.
• Fusion-éclatement : On construit toutes les partitions obtenues par fusion de
deux segments de Si. Pour chacune de ces partitions, on recherche le prédicteur
conduisant au meilleur éclatement des deux segments fusionnés. On retient la
partition à gain sur incertitude maximum. Si cette partition est admissible, elle
définit Si+1. et on retourne à l’étape Fusion. Sinon on passe à la phase suivante.
• Éclatement : Pour chaque segment de Si, on recherche la meilleure partition
admissible obtenue par éclatement à l’aide d’un prédicteur. On retient celle qui
conduit au meilleur gain sur l’incertitude. Si cette meilleure partition admissible
existe, elle définit Si+1 et on repart en phase 1. Sinon le processus s’arrête et Si
est optimale.

59