Scribd
Importer
33 vues53 pages

Tanagra Classification

Transféré par

Kaouther Benali
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF ou lisez en ligne sur Scribd
33 vues53 pages

Tanagra Classification

Transféré par

Kaouther Benali
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF ou lisez en ligne sur Scribd
Tutorie! Tanagra r 1 Objectif Théorie et pratique des arbres de classification. La classification automatique ou analyse typologique (« clustering » en anglais) vise les egrouper les individus en paquets homogénes. Les indivicus qui ont des caractéristiques similaires (proches) sont réunis dans un méme groupe (cluster, classe) ; les individus présentant Ges caractéristiques dissemblables (éloignées) sont associés & des groupes différents. Certaines ditficultés sont récurrentes en classification automatique : la détermination du nombre de groupes, leur interprétation, etc. Deux d'entre elles sont particuliérement pénalisantes dans Un contexte industriel. Le déploiement du modéle - on parle également diindustrialisation ~ n'est as facile & mettre en ceuvre. | s'agit d'implanter cans le systéme clinformation un programme permettant d'associer automatiquement un individu supplémentaire - n'ayant pas participé & ta constitution de ta partition - @ un des groupes. Si ce processus repose sur des calculs complexes, lents et cifficiles @ mettre & jour. Les performances et la maintenance poseront problémes sur le long terme. La capacité & traiter de grandes bases est une seconde difficulté qui sera de plus en plus prégnante dans un contexte d'une augmentation constante de la volumétrie des données. Les méthodes de classification automatique les plus répandues ont peine a appréhender ces configurations, soit parce qu’elles requigrent un nombre ce passage important sur la base de données, soit parce qu’elles nécessitent le calcul d'une matrice de distance entre individus impossible @ faire tenir en mémoire des ordinateurs sur de gros volumes. Nous présentons dans ce tutoriel les arbres de classification. lls apportent des solutions aux deux écueils précités. La démarche s'integre dans un cadre cohérent par report aux arbres de décision et régression, bien connus en data mining. La différence réside dans la mise en place Cun critere multivarié pour quantifier la pertinence des segmentations durant la construction de arbre. Nous avions déja présenté succinctement la méthode dans un précédent didacticiel (avril 2008)'. Mais nous nous étions focalisés sur les aspects opérationnels (manipulations dans Tenagra et lecture des résultats). Dans ce nouveau document, nous nous attardons sur les “ Arones de clasefcation », avi 2008 ; itp //utaiale-date-mining blocspetfr/2008/04 /arbres-de-clasofieation tml 18/02/2015 1 Tutorie! Tanagra r fondements théoriques de approche. Nous montrons que nous pouvons apprénender de maniére indifférenciée les bases comportant des variables actives quantitatives ou qualitatives. ou un mix des deux. Par la suite, nous détaillons la mise en ceuvre de la méthode a aide de plusieurs logiciels cont SPAD qui. @ ma connaissance, est le seul @ proposer une interface graphique interactive pour la construction des arbres de classification. Ce texte reprend certains passages dun article que javais naguére écrit sur les arbres de Classification et leur intérét dans des domaines oi Iinterprétation des résultats est au moins 2ussi importante que la performance brute (Rakotomalaia et Le Nouvel, 2007). 2 Les arbres de classification - Fondements théoriques 2.1 Les arbres de classification Lanalogie avec les arbres de décision (Rakotomalala, 2005) joue pleinement pour comprendre la construction des arbres de classification. L'approche s’appuie sur un algorithme récursif de segmentation. Chaque subdivision vise a produire un partitionnement maximisant un critere de qualité en rapport avec la typologie multivariée. Dans cette optique, les arbres de classification constituent une extension de ces approches (arbres de décision ou arbres de régression) ol, au critére de pureté et de variance, est substitué un critere dhomogénéité calculé sur rensemble des variables actives. Les feuilles de l'arbre représentent les classes produites par la typologie Vobjectif de l'apprentissage est de produire des groupes ol l'on chercherait @ minimiser par exemple l'inertie intra-classes. Chaque chemin partant de la racine @ une feuille correspond a une régle logique désignant un groupe. Replacé parmi les techniques de classification. les arbres de classification correspondent @ une méthode descendente, divisive et monothétique. « Divisive » parce que le point de départ est la partition grossiére rassemblant toutes les observations. La démarche consiste a fractionner itérativement les individus de meniére & constituer des groupes homogénes. « Monothétique » parce que la subdivision est réalisée @ partir des valeurs d'une variable, méme si par ailleurs le degré dhomogénéité des groupes est calculé sur l'ensemble des variables actives. Les travaux de Chavent (1998) et Blockeel (1998) constituent des reperes importants dans le domaine. J'y ai également un peu contribué. 18/02/2015 2 Tutoriel Tanagra 2.2 Un exemple introductif © Prenons un exemple simple pour préciser les idées. Nous disposons de la description de n = 28 véhicules @ l'aide de p = 5 variables (pri Nous obtenons cylindrée. puissance. poids. consommation). Fix | Gyineies | Puissance [Powe | Gone: [Ferrer 1s ney 22500 780 es] 1080] 2a lisess Hacriacey | 26200 07 129 1220 10.8] Iwicsan Prmera20 | 20060. 1207 a 1220 2] fopeiasva rei ey | 25000. 1597 7 1080 7a lope omegazc ve —[—a7700 ase] 723 779 a [Peugeotsosxs 108 | 22950 al 7a] 1109] J [suzun sot s0 GUS | 12000) Ea 2a a0] sa [revo Previa eaion | 50000. 43a 7 1800 72] Figure 1 - Tableau de donn arbre suivant sous SPAD. —_— oi Figure 2- Arbre de classification pour les données "Autos" 18/02/2015 Tutorie! Tanagra r Description de I'arbre. Décrivons l'arbre sommairement : Le premier sommet est la racine de rarbre (n° 1). II recense Ia totalité des observations (100% en noit) «Poids » s'est imposé pour effectuer ta premiére segmentation. C'est une variable quantitative, le seuil 1318 permet de définir 2 sous-groupes. Dans le sommet n° 17 (suivant 8 individus la numérotation inteme de SPAD). il contient 10 observations (soit 36% des n de la base). Le pourcentage en rouge (92%) indique le degré chomogénéité du groupe. Nous y reviendrons plus loin lorsquil s'agira de décrire Ia pratique des arbres de classification & aide du logiciel SPAD. Dans leutre sommet (n° 16), nous avons 18 observations (64 % de n = 28). La qualité de la segmentation est matérialisée par le chittte « 67.5 » en fond bleu. II s‘agira pour nous de préciser son mode de calcul dans les sections qui viennent. Le sommet n° 16 est par la suite subdivisée en 2 sous-classes n° 18 et 19 avec respectivement 8 (29%) et 10 (36%) observations. Le « gain » d'information produit par ta segmentation est de « 16.8 » Lecture des régles d’affectation. Nous avons done une partition en 3 classes & Ia sortie. Les ragles de désignation des groupes sont : 1. Si poids < 1315 et prix < 19820 Alors groupe n°4 2. Si poids < 1315 et prix > 19820 Alors groupe n°2 3. Si poids > 1315 Alors groupe n°3. Les régles de désignation des groupes sont clairement lisibles, interprétables, et facile @ implémenter dans les systémes cinformations. Connaissant le poids et le prix d'un nouveau Véhicule, nous saurons facilement & quel groupe rassocier. Commentaires. D’autres remarques nous viennent a la lecture de ces résultats - Seules deux variables interviennent dans latbre. Alors que homogenéité des groupes est calculée sur ensemble des variables. ll y a donc un processus de sélection de variables dans la construction de la partion. C’est une problématique qui revient souvent dans les publications scientifiques. 18/02/2015 4 Tutorie! Tanagra r Néanmoins, pour caractériser les groupes, nous ne pouvons pas nous en tenir aux seules variables de segmentation apparentes. Tout comme dans un arbre de décision, certaines variables peuvent étre pertinentes mais masquées par celles qui ont été sélectionnées pour définir les segmentations. La démarche usuelle dinterprétation des groupes via les méthodes factorielles ou les statistiques descriptives conditionnelles restent dactualité ici. Nous disposons dune hiérarchie de pattitions imbriquées. A rinstar de ce qui peut se faire dans le cadre de la classification ascendente higrarchique (CAH), nous pouvons définir et évaluer des scénarios de solutions cohérentes entres elles. Cette possibilité est particuligrement avantageuse en classification ou, en pratique, la détermination du nombre idoine de classes reste un probleme ouvert, et pour longtemps encore je pense. Wl s‘agit bien d'un partitionnement ; un individu eppartient (est affecté) & une et une seule classe. Processus de construction de arbre. Nous retrouvons ici les mémes problémes @ résoudre que lors de la construction d'un arbre de décision ; Comment choisir la variable de segmentation sur un noeud ? Etant entendu que ‘on choisit la variable la plus pertinente au sens dun critere dhomogéneité : comment quantifier la dispersion d'un groupe ? comment quantifier le gain dhomogénéité lors d'une segmentation ? Lorsque nous souhaitons passer de le partition en K a (K + 1) classes. plusieurs feuilles sont candidates @ la segmentation. Comment choisir celle que nous devons segmenter en priorité ? De fait, nous devons obtenir une partition hiérarchique indicée - un dendrogramme en d'autres termes - permettant de déterminer sans ambiguité la séquence des subdivisions. On souhaite élaborer un arbre binaire. Les variables de segmentation peuvent étre Qualitatives ou quantitatives. Lorsqu’elle est qualitative binaire, la solution est évidente : chaque modalité induit une feuille. Mais lorsquelle est qualitative & L modalités (L > 2). comment procéder au regroupement de maniére @ obtenir une subdivision binaire ? Il faut que la stratégie soit cohérente avec Vobjecti clinduire des groupes les plus purs possibles. De meme, lorsque la veriable prédictive est quantitative, nous devons produire un seuil de découpage optimal au sens de Thomogéngité des sous-groupes. 18/02/2015 s Tutorie! Tanagra r — Question récurrente en classification automatique, comment determiner le nombre ce groupe adéquat ? En d'autres termes, comment décider de larrét de la construction de arbre ? Dans les sections qui suivent, nous essaierons d'apporter des réponses & ces questions. 2.3. Mesure de qualité de segmentation 2.3.1 Indice d’homogénéité -L’inertie Lineriie est une mesure naturelle de cispersion. 11 s'agit dune extension multivariée de ta variance. Sur un ensemble C de n observations, nous le calculerons comme suit : 1(C) = > @(i,G) Oi al) est a distance euciidienne, et G est le barycentre du nuage de points ¢.~a-d, le vecteur des moyennes celculées sur ensemble des p variables, Si les variables sont exprimées dans des unités dittérentes, certaines peuvent prendre le pas sur les autres dans la definition de ta distance lorsqu’elles ont une variance plus grande. Le mieux est alors de les centrer et réduire systématiquement pour éviter cet inconvénient. Ces nouvelles variables s‘écrivent OU G, est récart-type de la variable X, Mécaniquement dans ce cas, le barycentre correspond a lorigine G = (0; ..., 0) et linertie totale des données est égal au nombre de variables T=p En pratique, nous préférons utliser la somme des carrés des écarts a la moyenne S, avec T= S(C)=nxI Nous comprendrons pourquoi lorsque l'on explicitera le gain induit par une segmentation. a xp Pour notte fichier de données, n = 28 et p = 5, ainsi T = 28 x 5 = 140. Aprés centrage et réduction avec les vecteurs « moyennes » et « écarts-type » suivants Moyenne, 28303.75 1809.07] TT 1196.96] 9,08] [Ecareype. 1263.37] [Link]| 31.68] 303.49| 2.19] Figure 3 - Moyennes et écarte-type des variables (Auto 18/02/2015 6 Tutoriel Tenagra r Nous obtenons le tableau des données centrées et réduites = [idee de vance Px | Cyindres | Pussance [Pods | Conea [ciroenZxvelene | ooze | 0009 | case | -o1e8 | 0105 ficFandavambot | aars_| 1496 | 1536 | asse_| 1357, Fora Fiests i27ac | 07m | 0026 | 0717 | -oear_| 1398 Fon Eason 141 PT ‘aes | oaea | 0749 | 0287 | 0217 Honda Cove Jonerta | eee | ara | 0270 | 018 | 0827 Lancia k9018 sea | vers | 2702 | ine | 1208 wards Haenbacev | ose | 1125 | 1388 | 04s | over ieubien Galant ‘0286 | v0e | 0270 | 0340 | 0879 [oper Aare 18116 o2re | ose | oan? | oses_|_-o7sa [opiconstzees | 16 | 100s | a2 | oes | 1036 [oosiomenszsive | ase7 [tage [tase | tses [1018 Peugents06xs 108 | o4er | -o0re | 117 | 0320 | _-oasa Peugecteve 20 ‘o703 | 008 [0.56 | 1.188 [oer eAhembre 20 ‘ose | o2ee | o2a0 | 14se | 1162 Sestivea 20.671 aes | oes | 0230 | 0402 010 [sunery vivo 4” 120s | 1800 [14s | -1508_| -1032 usu wai cis | 1208 | 1009 | 1222 | 1941 | 1494 [Foye Coro ‘0732 | -o7er_| 0717 | 061 | 0901 [Toyota Proviassion | 150 | 1cor | csoe | 1987 | 1098 [vote 25025 ‘ose | 10% | oases | _osro | oar fvowoesoKombian | a7ie | vos | saes_| i228 | 105s [uw cona0cr o2e2 | 0206 | 0200 | 0.108 | 0.198 few Poi 14 60 9825 | sea | 10s | -o7er | 174 Figure 4 Tableau des données centrées et rédultes (Auto 2.3.2 Régularisation — Classification sur facteurs Classification sur facteurs. Le schéma ci-dessus convient lorsque les variables actives sont quantitatives. 1 faudrait s'appuyer sur un autre type de distance si elles sont qualitatives, et un autre encore si nous avons un mix de variables quantitatives et qualitatives. Pour ne pas muttiplier la gestion de cas particuliers, la classification sur facteurs constitue une solution élégante (Lebert et al., 2000 ; page 185 et suivantes). Ainsi, lorsque les variables sont toutes quantitatives, nous réalisons une ACP (analyse en composantes principales). puis nous procédons @ la classification en calculant les ineities sur les facteurs ; lorsau’elles sont toutes qualitatives, nous passons par une ACM (analyse des correspondances multiples) ; et lorsque nous avons un mix de variables, nous utilisons 'AFOM (analyse factorielle des données mixtes). Axes factoriels deux & deux orthogonaux. Nous pouvons ainsi traiter dans un cadre unifié les citférentes configurations. De plus, les facteurs étant deux & deux orthogonaux. l'utilisation de la distance euciidienne est parfaitement justiiée dans ce contexte, 18/02/2015 7 Tutoriel Tenagra r Nettoyage (lissage) des données. Enfin, passer par les axes factoriels est totalement équivalent @ procéder @ partir des variables originelles si nous utilisons tous les facteurs (ex. avec une ACP sur p variables. nous obtenons p facteurs & la sortie). Lintérét de cette étape préliminaire est que nous pouvons choisir un sous-ensemble de facteurs seulement pour réaliser la classification. Nous réalisons ainsi une sorte de nettoyage des données ou le bruit associé aux données capprentissage, portées par les demiers facteurs & trés faible variance, est éliminé. La construction de la partition se concentre sur les premiers axes factoriels, porteurs informations pertinentes, transposables dans la population. a z a 4 Ciroen 2x voleane or ‘oasel oral 0.008] 0077 Datharsu cuore 3.85 oa] aon! -o.a7if 0.250 Fiat Pande Mambo 3306] 0036] 0.113] 0.005) 0.112 FistTempre Léubemy| -0687| oe] -[Link] 0.030] 0.036 Ford Festal. Zetec 1.93 ‘0083 azmi[ -o.170] [Link] Fort escort ae 1a6s__oauil _-[Link] _o.07a] _-o.08) onde Cvicloker ka 1147] 03s] 0.105] 0.100] 0. Hyundal Sonata 3000 248 ‘oso -o267| 0.705] 207 lanciaK 3.015 378i _oma| _a230] _-0-303] a. vazda Hachvback asi o72q| -a.165] -0.109] -0.144 [vitsubishi Galant ‘aoe 0117] aval 0.45] 0.073 Nissan Primera 20 ‘om 0312] -a0xs] 0025 0.309 opel Astra 1.5116 rose ‘0.259 0.363] -o.107) _-0.08 Opel Corsa 1.21 Eco 248 ‘0.206 -o.cr0| 0.263] o.0n Opel Omegs 2.5iVE 3030] 00s] aol -0277] 0.113 Peugeot 305 x5 108, Da ‘oar -az0i[ 107] a2 Peugeot 605 2.0 as ‘070i 0.068] _-o.023) 0.67] Renault Safrane 22. as7i] 0.253] -a.240| 0.063] 0.138 seat Alhambra 70 es] __-100e| _-0.179] _o.o7i] _-0.225 Seat ibiza 2067 08 osu] -aeil [Link] 0.15 Subaru Vivio aw 3.16 ‘0200-0776 73] 0.20 Suzuki Swife LOGI 2.98 ‘oa07| 0.146] 0.073] oz [rovota Corala 157 ‘0x —_o.77| 0.077 0.085 [royots Previa sion s2ui| 1100] a2] 02a) 0.2 [velvoas025 1a ‘0.280 _oro| 0.0%) _o.1e [velvo 960 Kambl aut 321q] 0.115] -a.159] -[Link]] 0.270 [rweoie206r O37 ‘02s orl oro] a2 [ywPolo 1.460 207 ‘ox _o27i[ v.82} 029 Figure 5 - Coordonnées factor os individu (Autos) Un exemple. Nous avons réalisé une ACP normée sur les données « Autos ». Les deux premiers facteurs sont porteurs de 97% de information disponible. Nous retranscrivons les coordonnées factorielies des individus dans le tableau ci-dessus (Figure 5). Pour bien comprendre 'équivalence entre les deux espaces de représentation, calculons le carré de la tance entre les véhicules « Citro8n 2X Voleane » et « Daihatsu Core » & partir des données centrées et réduites (Figure 4). Nous avons 18/02/2015 8 Tutorie! Tanagra r (1,2) = (0.029 — (-1.381)}? + (0.308 — (—1.573) +--+ (-0.125— (1.539) Si lon utilise les coordonnées factorielles maintenant, d,*(1,2) = (0170—(—3.458))° + (0.489 — 0.172)? +--+ (—0.017 — 0.250)" 3.3714 Nous avons une correspondance exacte entre les distances. L’énorme avantage de passer par les axes factoriels est que nous pouvons nous contenter detfectuer les calculs sur les axes pertinents. Par exemple, 'ACP nous indique que les 2 premiers facteurs représentent 97% de information disponible. Si 'on s‘en tient & ces axes, nous aurons comme approximation de la distance entre ces individus : zy p3)"2) =(0170— 3.458) + (0.489 — 0.172) Elle est relativement précise. 2.3.3 Gain induit par une segmentation Qualité d'une partition et choix de Ia variable de segmentation. Lors d'une segmentation, un groupe C est subdivisé en 2 sous-groupes C, et Pour ces demiers, nous pouvons calculer leurs inerties S(C,) et S(C,). Nous pouvons alors les additionner pour former Tinertie intra~ classes W(C,,C,) = S(C,) + S(C,). Vobjectit de la typologie est de créer des sous-groupes aussi homogénes que possible. Par conséquent, lors de ia segmentation. nous choisirons ia configuration (Ia variable de segmentation) qui minimise linertie intra-classes W. En vertu de la formule de Huygens’, nous pouvons décomposer linertie totale en inertie intra~ classes (W) et inter-classes (B), & savoir S(C) = WC, C2) + B(Cr, Ca) De fait, minimiser W revient @ maximiser B. La démarche peut étre done reformulée : nous choisi dinertie inter- ssons comme variable de segmentation celle qui maxi ise le gai classes B. 8 représente Iinertie expliquée par 'appartenance aux groupes. Ainsi, les arbres de classification constituent une vraie généralisation des arbres de régression Cette idée peut étre étendue aux arbres de décision si fon considére que lindice de Gini, ullisé dans la méthode CART (Breiman et al., 1984) par exemple, est une sorte de variance calculée sur variables qualitatives (Light et Margolin, 1971). * Crest une extension muhivariée de Io déconnaostion de la variance, 18/02/2015 9 Tutorie! Tanagra r Un exemple. Considérons la premiére segmentation introduite par SPAD lors du traitement du fichier « autos » (Figure 2). Deux sous ensembles d’observations sont définis : ot Pix | cynics | Pulssance [Pols [| Gone [Hyunda Sonata 2000 | 071 1.290 0.925 0.560 197 [Lancia e3.0Us 1942 1376 2282, 1164 1.208 IMesdaHechbackv | 0642 sz 1398 0498 o7e7 lope Omega 2sive | 1.587 1122 7490 1550 1015 JPevoeot 208 2.0 0708 (0.208 0.58 1196 0787 [RenaultSafane22.V | 0675 0581 0735 0.998 197 [Sestainambra 20 0658 0286 0.230 yaaa 182 [royota Previa salon 7.850 2 0.00 "1987 009) vow 25025 0938 "ze 9 0570 787 [vow B60 Kombat | 1719 7 1498 1729) 1.052 ama [103s [| toa [ tis | 155 20 o Pik | Oyiindiee | Pulssance | Poids | Gonso |ciroen 2X Voleane: 0.020 0.308 0356 0.188 0.125 [Baines Cuore 1387 1578 144 1.08 1530 [FetPanda NamboL | 1.475: 7406 7508 1538 1357 [Fist Tempra 1.6 Liters | 0.476: 0.74 2.401 ‘036 | 0.108) [ForaFiesia 122016 | 0711 0.906 ‘O77 0.847 1.128 [Fon Escon 14iPT 0.685 ‘684 0749 0.287 0217 [Honda Civie owerta | 0.688) oers_| a0 | -0.108 | _-0627 [Misubishi Galant 0.206 ose _| -os70 [0380 [| -0673 [Nissan Primera 20 ona | 0307 0451 0.142 0057 Jope Astra 1.6116. 077 0.246 ‘On 0.386 764 lope Corsa 1 Zi Eco 1118 1,008 1412 0.806 1038 [Peugeot 06xs 108 | 0.487, 0.078 ‘on7 ‘0320 0.038 [Seatibiea 20 GT 0495 | 0204 0.230 ‘ace | oa Subaru Viio 4WO 1.208 =iaas_| 1506 | -1.038) [suzuki Swit 1.0 GLS_| 1.008) 1222 7.841 1408 Foyata Corolla 0782 0.701 ‘O77 2616 0.901 [rw Gono eT) 0269 0.286 020 | 0138 | 0.194 [rw Pato 14 60 0895 ees | 106s | -o797_| _-174 Moyenne aaa | 05 | 0579 | 0m | 060 n2 38 Figure 6- Les classes C1 ot C2 - et leurs barycentres respec - lus de la premiere segmentation (Autos) Nous calculons les inerties dans chaque sous-groupe - S(C) - 11.864 et S(C,) = 33.652. Nous pouvons en déduire linertie intra-classes W = S(C1,C2) = 11.864 + 33.652 = 45.516. Sachant que linertie totale de ensemble des observations est T = s(C Jen x p= 28x5 = 140. Llinertie inter-classes 8 est égale @ B = 140 - 54.516 = 94.484. Rapportée @ l'nertie totale, nous pouvons dire que la segmentation explique.. 18/02/2015 10 Tutorie! Tanagra r B_ 94.484 T 140 de information disponible. C'est le chiffre sur fond bleu @ la sortie du premier sommet de 0.675 = 67.5% arbre de SPAD (Figure 2). Critére de Ward. Construire une subdivision qui maximise finertie inter-classes correspond exactement & la méthode de Ward. Le critére de Ward s'écrit my X Ny 2 ny tn, (Gu G2) 04 (n,, ng) et (G,. G,) sont respectivement les effects et les barycentres des classes C, et C2. Voyons ce quil en est sur nos connées @ partir des informations des tableaux décrivant les classes (Figure 6). 10x18 10+18 = 94.484 Nous retrouvone rinerte inter-classes (B) calculée ci-dessus. [(0.149 —(-0.638)) + (1.033 -(-0.574))? + +--+ (1.156 ~(-0.642))"] La stratégie de subdivision dun nceud peut étre reformulée comme suit: on choisit comme variable de segmentation celle qui maximise le critére de Ward. 2.3.4 Higrarchisation des partitions Les inerties des groupes S(C,) s'additionnement pour former 'inertie intra-classes. ll est par conséquent possible de comparer les mérites des segmentations candidates situées sur deux feuilles différentes de arbre lors du passage d'une partition en K classes @ une partition en ((et) classes. En effet, si fon se rétire & Fexpression de Inertia intra-classes pour K groupes WC, .Cys erg) = S(C)+S(C,) +4 S(Cy) Mettons que la demiére classe C, est subdivisée en Cy, et Cys. Nous avons WCC yy CgysCgy) = (C+ (Cy) ++ S(Cyy) + (Cy) Le gain d’inertie global lors du passage de K & (K + 1) classes s'écrit » BW (GC) Gs Given Selo) =S(Cg)-[S(Cy) + 8(Cxs)] =A Les calculs ne concement que le sommet & segmenter, mais le gain dinertie est bien global Linertie expliquée (il en est de méme pour la part d'inertie expliquée) par chaque segmentation 18/02/2015 " Tutorie! Tanagra r s‘additionne également. II est de fait possible de comparer les segmentations candidates sur les différentes feuilles. Un exemp! Revoyons Tarbre généré par SPAD sur les données « autos » (Figure 2). inertie expliquée par la premiere subdivision est de 67.5%. Si nous segmentons le sommet n°16 (auquel est associée la valeur 16.8), lnertie expliquée par la partition en 3 classes sera dgale & 67.5 + 16.8 = 84.3% de information disponible. En revanche, si nous traitons le sommet n°17, elle serait égale & 67.5 + 2.0 = 69.5%. La premiére configuration - découpage du sommet n“I6 avec un gain relatif dinertie de 16. % = est netiement plus avantageuse. 2.4 Binarisation de la segmentation Dans les arbres de décision (et de régression), ropportunité de rendre obligatoirement binaire chaque segmentation peut se discuter (Rakotomalala, 1997 ; pages 183 4 189)’. Elle est une nécessité dans les arbres de classification. En effet, nous souhaitons construire une hiérarchie ce partitions embottées. Une seule classe additionnelle doit étre générée & chaque étape pour permettre au praticien de choisir le nombre adéquat de classes K" sans avoir & jongler avec les contraintes induites par la structure de rarbre. Le critare de Ward est utilisé pour choisir la variable de segmentation sur un noeud disions-nous plus haut, Il est calculé aprés regroupement binaire des modalités pour les variables qualitatives, et aprés discrétisation pour les variables quantitatives. 2.4.1 Discrétisation des variables de segmentation quantitatives Principe. Pour une variable candidate X, l'algorithme opére en deux temps ; (1) les valeurs de X sont triées de maniére croissante ; (2) toutes les coupures candidates - la borne de découpage est située & mi-chemin entre deux valeurs successives de X - sont évaluées de maniére a optimiser le critére de Ward (ou 'inertie inter-ciasses, c'est la méme chose) Voici un code R ui illustre le procedure. Nous recherchons la bome de découpage de la Variable « Poids » pour la segmentation de la racine de arbre « Autos » (Figute 2) Yohargenent des données Library (x1ox) don < [Link]("autos_suall_ict.x rownames (don) <- [Link](don[,1]) Lex" header: FR. Rakotomalsia, « Granhes dinduction , Université Lyon 1, 1997, 18/02/2015 12 Tutoriel Tanagra don < donl-ti print (head (don) ) #fonction de centrage réduction oR <- function (x) { n< length(x) m <- mean(x) et <- eget ( (n-1) /ntvar (x) return ( (x-m) /et) #centrage réduction des variables [Link] <- [Link]. frame (apply (don, CR) ) print (head ([Link])) gmatrice de distance sur données centrées-réduites n <> nrow([Link]) d <> dist ([Link], "euclidean") #7 =n * intertie totale T = ail 50.0 | a8 a0 | a7 La bome de découpage optimale est Poids = 1315 avec un gain de 67.5%. Ce sont bien les valeurs que l'on retrouve dans tarbre (Figure 2) ‘Temps de calcul. La somme des calculs & effectuer semble considérable, surtout si on pense cr a ent étre réitérés sur chaque noeud & segmenter. En réalité, le cispositi est tres rapide et peut appréhender de grandes bases de données. Il existe des algorithmes de tris efficaces. 1 est également possible de pré-trier les valeurs et de conserver les index de maniére & ne pas avoir @ répéter operation sur chaque noeud (mais au prix d'une occupation supplémentaire de Tespace mémoire). L’évaluation de chaque coupure peut étre réalisée en temps linéaire puisque le critére de Ward ne repose que sur le calcul des barycentres conditionnels. 18/02/2015 14 Tutorie! Tanagra r Reutilisation d’une variable de segmentation quantitative sur plusieurs sommets. Le découpage étant binaire & chaque noeud, la méme variable continue peut étre réintroduite & Gitférents niveaux de arbre, avec des bores de découpages différents cependant (Figure 7). Figure 7- Arbre de classification avec deux sogmontations succossivos basses surla variable “prix” (Autos) 2.4.2 Regroupement des modalités des variables de segmentation qualitatives Lorsque Ia variable candidate est ordinale, il suffit cordonner les modalités et de tester les combinaisons binaires. I y a (L-1) cas @ tester si la variable présente L modalités. Nous nous retrouvons dans une procédure analogue au traitement des variables quantitatives. La situation se complique compliquée lorsque la variable est nominale. Tester toutes les combinaisons possibles revient tester (2“'-1) cas. ce qui est impraticable dés que le nombre de modalités augmente. Pour donner un ordre diidée, si 0, il y a 524.267 configurations binaires & évaluer. Il faut impérativerient trouver une stratégie proposant de « bons » résultats avec un temps de calcul raisonnable Une piste simple consiste a effectuer une classification ascendante hiérarchique (CAH) sur les modalités de la variable de segmentation candidate. L'inertie est toujours calculée sur ensemble Ges variables actives. Il s'agit dune approche pas & pas. le nombre de tests est connu a Tavance, la complexité de calcul est quadratique par rapport au nombre de modalités. Et surtout la démarche est cohérente avec le processus de construction de arbre puisquil s’agit toujours de trouver le regroupement binaire des modalités qui maximise I'inertie inter-classes. Certes, les inconvénients de ce type doptimisation sont connus. Des solutions sous-optimales peuvent se faire jour. Mais on peut se demander finalement si, en lissant ainsi exploration de espace des 18/02/2015 1s Tutoriel Tenagra r solutions, nous ne nous prémunissons pas du surapprentissage. Les combinaisons « optimales » collent trop aux données traitées la plupart du temps. Elles ingérent les particularités de 'échantilon ¢'apprentissage, non transposebles & la population, Dans la copie d'écran ci-dessous (Figure 8). nous montrons le processus de regroupement de modalité de la variable « ancienneté » pour le fichier « crédit » (dont nous reparlerons plus loin n dans cet section 4). La variable a été discrétisée et oil exemple. Nous constatons que la dichotomie la plus pertinente correspond a {ancienneté + de 12 ans} d'un cété (les « vieux » cients), et {anc. 1 an ou moins, anc. de 1a 4 ans, anc. de 4 @ 6 ans, anc. de 6 & 12 ans} de l'autre (les clients plus récents). Anc.+de 12 ans Ane. Lan ou moins [Link] 6a 12 ans [Link] 14 ans Anc.de4 a6 ans. Figure 8 Regroupement des modaltés de “anclenneté(Fchir “Créat) Une variable qualitative peut apparaitre plusieurs fois dans l'arbre, avec des regroupements différents. Lors d'une segmentation, seules les modalités de la variable présentes sur le chemin analysé sont concernées bien entendu. 2.5. Détermination du nombre de groupes La détermination du nombre de classes est le serpent de mer de la classification automatique. Des solutions et indicateurs existent. Mais elles sont souvent trés spécifiques, et finalement peu convaincantes. 18/02/2015 16 Tutoriel Tenagra r Liinterprétation experte des résultats est la premiere solution pratique que fon retrouve dans la littérature. En effet, mettre en avant des groupes qui ne correspondent & rien en termes métiers parelt peu raisonnable. Encore faut-il disposer du recul suffisant pour pouvoir lire correctement les informations quils recélent. Les arbres de classifc n, qui est technique descendante, foumit une hiérarchie de solutions emboitées. Nous sommes dans une situation analogue @ la classification ascendante higrarchique. II est dés lors possible de suivre révolution des crit8res d'évaluation des partitions en fonction du nombre de classes. Une « inflexion » - le fameuse loi du coude - dans cette Evolution indique souvent une modification de la structure des données. Nous pouvons ainsi ous référer & la décroissance des gains d'inertie inter-classes consécutifs & chaque subdivision (Figure 9), ou encore considérer Ia croissance de rinertie expliquée en fonction du nombre de ciasses (Figure 10). 23) 4 se 7 8 © Nombre de classes Figure 9- Gain d'inertie pour chaque segmentation (Autos) 203 4 8 6 7 68 9 Nombre de classes Figure 10 - Inertic expliquée en fonction du nombre de classes (Autos) Les deux points de vue semblent converger sur une partition en 3 classes. 18/02/2015 7 Tutorie! Tanagra r Bien sOr, d'autres pistes existent. Des paramétres inspirés des arbres de décision peuvent aider & guider ta construction des arbres de classification ; Ieffectif minimum pour segmenter (nombre Cobservation minimum sur un sommet pour initier une segmentation) : 'etfectit d'admissibilité (nombre d'observations minimum sur l'ensemble des feuilles pour valider une segmentation) ; Pourquoi pas des tests MANOVA (multivariate analysis of variance) qui seraient une variante de la méthode AID/CHAID ; etc. La construction en deux temps, expansion (growing) et post- élagage (pruning), inspiré de CART (Breiman et al., 1984) peut aussi s'avérer fructueuse dans ce nouveau contexte. Tanagra propose cette solution’. Il cherche le « coude » sur la courbe de décroissance de I'inertie intra~classe calculée sur 'échantillon de validation. 2.6 La question du déploiement Quelques solutions pour le déploiement. La question est peu traitée dans les articles scientifiques et les ouvrages. Elle est pourtant cruciale dans la pratique. Le data mining a pour vocation de mettre en évidence les phénomenes de causalité dans les informations collectées our en tirer parti par la suite, d'une maniére ou d'une autre. Mais il se doit également detre opérationnel. Un ancien sondage (mei 2008)° des KOnuggets permet dy voir un peu plus clair. Concernant I'industrialisation, une grande partie des enquétés (35.8%) s‘appuient directement sur Toutil ayant servi a la construction du modéle. J/avais moi-méme montré comment cela pouvait @tre possible en m’appuyant sur le logiciel R* et le package « filehash »’, Dans un contexte de déploiement grande échelle, cette solution n’est pas tenable. Un logiciel de data mining a pour vocation de créer des modéles. Le faire jouer un autre role induit des contraintes qui pésent sur Vefficacité du dispositit. Cela impliquerait également la nécessité de déployer le logiciel de data mining sur tous les serveurs dédiés, uniquement & des fins de production et non d’analyse. Une seconde partie des sondés (25.3%) s‘appuient sur des systémes de gestion de base de données, en utilisant le langage SQL. Seuls les modéles @ base de régles sont exploitables dans ce cas. Une autre partie (16.8%) propose d'implanter le modéle en limplémentant dans un * « Acores de elassifeaton », avil 2008 , nto. //sutatels-deta-mining blogspot fr/2008/04 /ararae-cla-clsssfestion ht * Date Mining deployment polls, hitp./ wn [Link] ells/2009 /deployment-data-mining-modes. htm * hp. Auman. [Link]/ itp./ utoraln-dota-rining blogs f/2010/06/deploiamant-cia-madeles-racictés-avee ml 18/02/2015 18 Tutorie! Tanagra r langage de programmation quelconque (Java par exemple). Nul doute que le dispositit est tres efficace & usage. Mais cette démarche requiert des compétences en codage hors de portée du tout venant. II nécessite par ailleurs un processus de validation (unitaire, integration) qui peut S‘avérer lourd. D'autant plus contraignant sill apparaft nécessaire de mettre & jour réguliérement les modéles. La solution PMML. Une partie des sondés disent utiiser le langage de déploiement PMML (Predictive Model Market Langage) (13.7% en 2009, sachant quill était 4 4.2% en 2008, Ie pourcentage est vraisembleblement plus élevé encore aujourd'hui). C’est une solution viable dans un contexte de déploiement & grande échelle nécessitant des mises & jour réguliéres Jevais exploré cette idée dans un tutoriel*. Il prend sa pleine mesure lorsque le format est accepté par un outil de management de données. Javais utilisé & cet effet PDI-CE (Pentaho Data Integration - Community Edition)®. Mais la solution proposée par le standard PMML pour la classification automatique (clustering models") m’a un peu décu jfavoue. Le format ne prend en compte que les modéles basés sur des barycentres conditionnels (comme le produirait un k- Means) ou basés sur des distributions conditionnelles (comme le produirait lalgorithme EM), Nous devons faire face @ plusieurs écueils. || faut que le format de description intégre les éventuelles informations de transformation de données pour quill puisse lappliquer aux individus supplémentaires. Le traitement de chaque individu nécessite des calculs de distances. Certes. le nombre de classes est faible généralement. Mais sion peut s'en passer c'est mieux A titre d'exemple, j'ai réalisé un K-Means en 3 classes sur données standardisées sur Knime. Figure 11 - "Fire" sous Knime pour exporter le modiéle K-Means dans un fichier PMML Nous obtenons la description suivante (fichier au format PMML) «Le format PNIML pour Ie dépoiement de modeies », septembre 2010. * rp.7 /community [Link]/ bitp./ Anu dong ora/¥v4-1/ Clustering! hl 18/02/2015 9

Vous aimerez peut-être aussi