Brevet FR2825168A1 — publié le 20021129

La présente invention concerne une méthode de discrétisation d'attributs d'une base de données. L'invention trouve particulièrement application dans l'exploitation statistique des données, notamment dans le domaine de l'apprentissage supervisé. L'analyse statistique des données (encore appelée data mining ) a pris un essor considérable ces dernières années avec l'extension du commerce électronique et l'apparition de très grandes bases de données. Le data mining vise de manière générale à explorer, classifier et extraire des règles d'associations sous-jacentes au sein d'une base de données. Il est notamment utilisé pour construire des modèles de classification ou de prédiction. La classification permet d'identifier au sein de la base de données des catégories à partir de combinaisons d'attributs, puis de ranger les données en fonction de ces catégories. Par exemple, si la base de données est relative à des achats de produits par des consommateurs, ceux-ci pourront être rangés en différentes catégories : clients fidèles, clients occasionnels, clients recherchant les produits soldés, clients recherchant les produits haut de gamme etc. La prédiction, quant à elle, vise à décrire comment un ou plusieurs attributs de la base de données se comporteront dans le futur. Dans l'exemple de la base de données d'achats évoqué plus haut, il pourra être intéressant de prévoir le comportement de ces consommateurs en fonction d'une baisse ou d'une hausse de prix de tel ou tel produit. Un des objectifs du data mining dit supervisé est la construction d'un modèle prédictif visant à prédire un attribut déterminé. Cette construction consiste à chercher parmi les attributs de la base de données considérée à identifier celui ou ceux qui présentent la plus forte dépendance statistique avec un attribut cible et à décrire cette dépendance. Par exemple, si l'on a classé les consommateurs en fonction de leurs montants d'achats annuels en différentes catégories de consommation : grosse consommation, moyenne consommation, faible consommation, il sera intéressant de déterminer quels sont les attributs de la base de données achats qui sont les plus corrélés (ou de manière équivalente, les moins indépendants statistiquement) de l'attibut donnant la classe de consommation. On notera qu'au lieu de d'attribut cible catégorie de consommation , on aurait pu prendre directement l'attribut montant d'achats annuels . De manière générale, les valeurs (encore appelées modalités) prises par un attribut peuvent être numériques (par exemple un montant d'achats) ou symbolique (par exemple une catégorie de consommation). On parle dans le premier cas d'attribut numérique et dans le second cas d'attribut symbolique. Certaines méthodes de data mining supervisé requièrent une discrétisation des attributs numériques. On entend ici par discrétisation d'un attribut numérique un découpage du domaine des valeurs prises par un attribut en un nombre fini d'intervalles. Si le domaine en question est une plage de valeurs continues la discrétisation se traduira par une quantification de cette plage. Si ce domaine est déjà constitué de valeurs discrètes ordonnées, la discrétisation aura pour fonction de regrouper ces valeurs en groupes de valeurs consécutives. La discrétisation des attributs numériques a été largement traitée dans la littérature. On en trouvera par exemple une description dans l'ouvrage de Zighed et al. intitulé Graphes d'induction publié chez HERMES Science Publications. On distingue deux types de méthodes de discrétisation : les méthodes descendantes et les méthodes ascendantes. Les méthodes descendantes partent de l'intervalle complet à discrétiser et cherche le meilleur point de coupure de l'intervalle en optimisant un critère prédéterminé. Les méthodes ascendantes partent d'intervalles élémentaires et cherchent la meilleure fusion de deux intervalles adjacents en optimisant un critère prédéterminé. Dans les deux cas, elles sont appliquées itérativement jusqu'à ce qu'un critère d'arrêt soit satisfait. Une méthode de discrétisation ascendante utilisant le critère du est connu dans la littérature sous le nom de ChiMerge. De même une méthode de discrétisation descendante utilisant le critère du XI est connu sous le nom de ChiSplit. Avant de présenter la méthode ChiMerge on rappellera tout d'abord que le critère du permet sous certaines hypothèses de déterminer le degré d'indépendance de deux variables aléatoires. Soit S un attribut source et T un attribut cible. On supposera pour fixer les idées que S présente quatre modalités a, b, c, d et T trois modalités A, B, C. Le Tableau 1 montre le tableau de contingence des variables S et T avec les conventions suivantes : ny est le nombre d'individus observés pour la lme modalité de la variable S et la jème modalité de la variable T. nij est encore appelé effectif observé de la case (iJ) ; n, est le nombre total d'individus pour la ième modalité de la variable S. n, est encore appelé effectif observé de la ligne i ; nJ est le nombre total d'individus pour la jme modalité de la variable T. nj est encore appelé effectif observé de la colonne j ; N est le nombre total d'individus. S/T A B C Total A nu n12 n13 n1. B n21 n22 n23 n2 C n31 n32 n33 n3 D n41 n42 n43 n4 E ns1 n52 n53 ns. Total n.1 n2 n3 N Tableau 1 De manière générale, on notera I et J respectivement le nombre de modalités de l'attribut S et le nombre de modalités de l'attribut T. nn On définit l'effectif théorique ey de la case (i, j) par = N. ey représente le nombre d'individus qui serait observé dans la case du tableau de contingence dans le cas de variables indépendantes. L'écart à l'indépendance des variables S et T est mesuré par : Plus la valeur de #2 est élevée, moins l'hypothèse d'indépendance des variables aléatoires S et T est probable. On parle par abus de langage de probabilité d'indépendance des variables. Plus précisément est une variable aléatoire dont on peut montrer que la densité suit une loi dite du à (I-1). (J-l) degrés de liberté. La loi du est celle suivie par une somme quadratique de valeurs aléatoires normales centrées. Elle a de fait l'expression d'une loi y et tend vers une loi gaussienne lorsque le nombre de degrés de liberté est élevé. Par exemple si 1=5 et J=3, le nombre de degrés de liberté vaut 8. Si la valeur de calculée par (1) vaut 20, la loi du à 8 degrés de liberté donne une probabilité d'indépendance de S et T de 1%. Nous présenterons ci-après la méthode de discrétisation ChiMerge. Nous nous plaçons dans le cas général d'un attribut source S à 1 modalités et d'un attribut T à J modalités. La méthode ChiMerge considère seulement deux lignes consécutives i et i+ 1 du tableau de contingence. Soit 't. .-. 'j la distribution locale (c'est-à-dire dans le contexte local des lignes consécutives i et i+l) de probabilité des modalités pour l'attribut cible T. Si n, est l'effectif de la ligne i et n, +1 est l'effectif de la ligne i+l, les effectifs observés et théoriques de la ligne i s'expriment respectivement par =a, n, et e-' où les ay représentent les proportions d'effectifs observés pour la ligne i. De même, les effectifs observés et théoriques de la ligne i+1 s'expriment respectivement par et où les a, +,, représentent les proportions observées de modalités de T pour la ligne i+l. La distribution locale de probabilité q' 1,q'2,...,q'J des modalités de l'attribut cible peut être exprimée par : Selon la méthode ChiMerge, on calcule la valeur du pour les lignes i et i+ 1, L, soit, en tenant compte du fait que 2 ) =1) =1 soit encore après transformation : 2 , est une variable aléatoire suivant une loi du à J-1 degrés de liberté. La méthode ChiMerge propose de fusionner les lignes i et i+ 1 si : 1 oùprob (a, K) désigne la probabilité que ira pour la loi du à K degrés de libertés et pTh est une valeur de seuil prédéterminée paramétrant la méthode. En pratique, la valeur prob (a, K) est obtenue à partir d'une table classique du donnant la valeur de a en fonction de prob (a, K) et de K La condition (5) exprime que la probabilité d'indépendance de S et T au vu des deux lignes considérées est inférieure à une valeur de seuil. La fusion de lignes consécutives est itérée tant que la condition (5) est vérifiée. La fusion de deux lignes entraîne le regroupement de leurs modalités et la sommation de leurs effectifs. Par exemple dans le cas d'un attribut numérique à valeurs continues on a avant fusion : [Sl,+1,Sl+2[ nl,1 nl+1,2 .... nl,J nl, [Sl+1,Sl+2[ nl+1,1 nl+1,2 .... nl+1,J nl+1, Tableau 2 et après fusion : [Sl,SI+2[ nI,l+nl+1,1 nl+1,2+nl+1,2 .... nl,J+nl+1,J nl,+nl+1, Tableau 3 Un premier problème soulevé par l'emploi de la méthode ChiMerge est le choix du paramètre pith qui ne doit pas trop élevé sous peine de fusionner toutes les lignes ni trop faible sous peine de n'en fusionner aucune paire. En pratique, il est très difficile de trouver un compromis. Un second problème intrinsèque à cette méthode est d'opérer localement sans tenir compte de l'ensemble des modalités (ou du nombre d'intervalles) de l'attribut source. On ne sait pas a priori si le résultat de la discrétisation est globalement optimal sur cet ensemble. En outre, la méthode ChiMerge est limitée à une discrétisation monodimensionnelle en ce sens qu'elle ne peut opérer que sur un seul attribut source à la fois et non sur unp-uplet d'attributs. Enfin, la méthode ChiMerge ne permet pas de mesurer la probabilité d'indépendance entre un attribut source et un attribut cible et, par voie de conséquence, pour un attribut cible donné, de classer des attributs source en fonction de leurs probabilités d'indépendance vis à vis de l'attribut cible. L'objectif de la présente invention est de proposer une méthode de discrétisation d'attributs qui ne présente pas les inconvénients et limitations énoncés ci-dessus. A cet effet, l'invention est définie par une méthode de discrétisation d'un attribut d'une base de données contenant une population d'individus, ledit attribut, dit attribut source, pouvant prendre plusieurs modalités, ladite méthode comprenant une première étape dans laquelle on regroupe lesdites modalités de l'attribut source en groupes élémentaires et, une seconde étape dans laquelle on détermine, à partir du tableau de contingence de l'attribut source et d'un attribut cible, parmi un ensemble de couples de groupes élémentaires, le couple de groupes élémentaires dont la fusion diminue le plus fortement la probabilité d'indépendance de l'attribut source et de l'attribut cible, et une troisième étape dans laquelle on fusionne le couple de groupes élémentaires ainsi déterminé, lesdites seconde et troisième étapes étant itérées tant qu'il existe un couple de groupes élémentaires permettant de diminuer ladite probabilité d'indépendance. Afin de déterminer le couple de groupes élémentaires dans la seconde étape, on pourra estimer pour chaque couple de groupes élémentaires dudit ensemble, la valeur du du tableau de contingence après fusion dudit couple et l'on sélectionnera le couple produisant la valeur du après fusion la plus élevée. Avantageusement, pour chaque couple de groupes élémentaires, on calcule la variation du du tableau de contingence avant et après fusion dudit couple. Les variations du associées aux différents couples seront alors triées sous forme de liste de valeurs décroissantes et que l'on sélectionnera le premier couple de la liste. Le couple de groupes élémentaires étant sélectionné, on procèdera à la fusion dudit couple si la probabilité du relative au tableau de contingence après fusion dudit couple est inférieure à la probabilité du relative au tableau de contingence avant fusion. Selon une variante, les probabilités du i relatives au tableau de contingence avant et après fusion sont exprimées de manière logarithmique. Typiquement, ledit ensemble de couples de groupes élémentaires est constitué de tous les couples de groupes voisins au sens d'une relation de voisinage prédéterminée. On recherche de préférence parmi les couples de groupes élémentaires voisins ceux comprenant au moins un groupe présentant au moins un effectif théorique par case du tableau de contingence inférieur à un effectif minimum prédéterminé et on les identifie comme couples prioritaires au moyen d'une information d'identification. Dans ce cas, s'il existe un ou des couples prioritaires, on fusionne le couple prioritaire produisant la valeur du après fusion la plus élevée. Selon un premier mode de réalisation, l'attribut source étant un attribut numérique mono-dimensionnel, les groupes élémentaires voisins sont constitués par des intervalles adjacents. Selon un second mode de réalisation, l'attribut source étant un attribut numérique multi-dimensionnel formé par pluralité d'attributs numériques monodimensionnels et les individus de la population étant représentés par des points dans l'espace desdits attributs, lesdits groupes élémentaires sont les cellules de Voronoï de cet espace, contenant lesdits points. Dans ce cas, on construit le graphe de Delaunay associé aux cellules de Voronoï et l'on élimine de ce graphe tout arc joignant deux cellules voisines en passant par une troisième, les couples de groupes élémentaires voisins étant alors donnés par les arcs du graphe de Delaunay après l'étape d'élimination. Selon un troisième mode de réalisation, l'attribut source est de type symbolique. L'invention concerne encore une méthode d'évaluation de la dépendance d'un attribut numérique bi-dimensionnel, formé par un couple d'attributs numériques mono-dimensionnels, vis à vis d'un attribut cible. Les individus de la population sont représentés par des points dans le plan desdits attributs. Selon cette méthode, on discrétise l'attribut bi-dimensionnel par la méthode de discrétisation multidimensionnelle mentionnée plus haut et l'on visualise par des moyens de visualisation des goupes de cellules de Voronoï fusionnées par ladite méthode. L'invention concerne enfin un logiciel de data mining comprenant un programme de discrétisation d'au moins un attribut d'une base de données, tel que son exécution sur un ordinateur effectue les étapes de la méthode exposée ci-dessus. Les caractéristiques de l'invention mentionnées ci-dessus, ainsi que d'autres, apparaîtront plus clairement à la lecture de la description suivante d'un exemple de réalisation, ladite description étant faite en relation avec les dessins joints, parmi lesquels : la Fig. 1 illustre sous forme d'organigramme la méthode de discrétisation d'attributs selon un mode de réalisation de l'invention ; la Fig. 2 illustre un premier exemple de discrétisation d'un attribut symbolique ; la Fig. 3 illustre un second exemple de discrétisation d'un attribut symbolique avant et après fusion ; la Fig. 4 représente un exemple de diagramme de Voronoï ; la Fig. 5 représente le diagramme de Delaunay associé au diagramme de Voronoï de la Fig. 4 ; la Fig. 6 représente un ensemble d'individus projetés sur le plan de deux attributs numériques ; la Fig. 7 représente le diagramme de Delaunay associé à l'ensemble d'individus de la Fig. 6 ; la Fig. 8 représente les zones de discrétisation associées à l'ensemble d'individus de la Fig. 5. Une première idée générale à la base de l'invention est de discrétiser un attribut source en optimisant un critère statistique portant sur l'ensemble du tableau de contingence. Une seconde idée générale à la base de l'invention est d'extrapoler cette discrétisation au cas multi-dimensionnel en faisant appel à un graphe de Delaunay. Nous exposerons l'invention tout d'abord dans le cas d'un attribut S numérique mono-dimensionnel à valeurs continues. Après avoir ordonné les modalités de S, l'ensemble de ces modalités peut être découpé en intervalles élémentaires Si= [s, s, +, [, i=l,.., l. Nous souhaitons évaluer le degré d'indépendance de cet attribut avec un attribut cible T de modalités T., j=l,.., J Ces modalités T. peuvent être des modalités symboliques ou numériques. Dans ce dernier cas elles peuvent être des valeurs discrètes ou des intervalles de valeurs continues. On peut représenter le tableau de contingence : S/T T1 T2 ... TJ Total S1 n1,1 n1,2 ... n1,J n1. SI n1,1 n1,2 ... nI,J nl S1+1 nI+1,1 nI+1,2 ... n1+1,J nl+1,. si n,,, nI, 2... n,,-, ni, Total . i K... M, y N Tableau 4 D'après (1) la valeur du XI sur l'ensemble du tableau peut s'exprimer par : Soit encore en notant ql, Q2,.., qJ la distribution de probabilité des modalités de l'attribut cible et a. les proportions d'effectifs observés pour la ligne i et en remarquant que =,, -a, et =-1 : J=l J=l 1 2 2 où ) est la valeur du pour la ligne i. L'expression (7) signifie que le est additif par rapport aux lignes du tableau. Supposons maintenant que deux lignes consécutives i et i+1 soient fusionnées. La valeur du après fusion, notée ,, + [) peut s'écrire : xx, 1 2 où est la valeur du pour la ligne résultant de la fusion, c'est-à-dire : L'expression (8) peut s'exprimer simplement en fonction de valeur du avant fusion : où Aest la variation du résultant de la fusion des lignes i et i+ 1. La 2 valeur de A, . peut être calculée explicitement en fonction des proportions d'effectifs des lignes i et i+ 1 : 2 2 La liste des valeurs de est triée par valeurs décroissantes. Soit A,, premier élément de la liste. On teste alors si : On notera que la loi du pour le premier terme n'a plus que (I-2) (J-1) degrés de liberté suite à la fusion. En pratique, étant donné les faibles valeurs que peuvent prendre les termes de (12), la comparaison portera avantageusement sur les logarithmes de ces probabilités. La condition (12) traduit une diminution de la probabilité d'indépendance de S et T après fusion des lignes io et io+l. Etant donné la valeur négative ##2(Io,io+1), la valeur du ne peut que décroître avec la fusion. Etant donné que prob (a, K) est une fonction décroissante de a et croissante de K, la relation (12) ne peut être vérifiée que grâce à la diminution du nombre de degrés de liberté. La diminution de la probabilité d'indépendance sera d'autant plus importante que A, sera faible en valeur AIZio, lo+') absolue, c'est à dire d'après la relation (11) que les proportions observées pour les lignes considérées seront plus proches et ce pour les proportions q, les plus faibles. Si la condition (12) est vérifiée, on fusionne les lignes io et io+l. En revanche, si la condition (12) n'est pas vérifiée, alors elle n'est vérifiée pour aucun indice i par suite de la décroissance de prob (a, en fonction de a. Le processus de fusion est alors arrêté. Si les lignes io et io+l ont été fusionnées, on met à jour la liste des valeurs 2 (o+n- On notera que cette mise à jour ne concerne en fait que les valeurs relatives aux lignes contiguës aux lignes fusionnées à savoir les lignes d'indices io-1 et io+2 avant fusion (si elles existent). Le processus de fusion est itéré tant que la condition (12) est satisfaite. La méthode décrite ci-dessus conduit à une discrétisation ad hoc du domaine des modalités, c'est-à-dire à une discrétisation qui minimise l'indépendance entre l'attribut source et l'attribut cible sur l'ensemble du domaine. La méthode de discrétisation permet de regrouper des intervalles adjacents ayant des comportements de prédiction similaires vis à vis de l'attribut cible, le regroupement étant arrêté lorsqu'il nuit à la qualité de prédiction, en d'autres termes lorsqu'il ne fait plus décroître la probabilité d'indépendance des attributs. On obtient par fusions successives un tableau de contingence dont le nombre de lignes se réduit et dont les effectifs par case augmentent. Afin de pouvoir tirer des conclusions fiables quant à la dépendance ou l'indépendance des attributs source et cible il est souhaitable d'avoir un effectif minimum par case. Il est communément admis que le test du est fiable pour des effectifs théoriques supérieurs à 5 par case. Qui plus est, une distribution inhomogène étant plus probable pour une faible population que pour une population plus importante, on observe pour de faibles valeurs d'effectifs théoriques e. un phénomène, dit de sur-apprentissage dans 2 lequel, à partir d'une valeur élevée du i on conclut indûment à une dépendance des attributs. On pourra alors convenir de respecter un effectif théorique minimum par case. On peut montrer qu'un effectif moyen minimum de l'ordre de log2 (10N) (où N est le nombre total d'individus) par case permet d'éviter de conclure de manière erronée à la dépendance des attributs. La méthode de discrétisation est alors adaptée de la manière suivante : on accorde d'abord la priorité aux fusions de lignes vérifiant (12) qui permettent de vérifier un critère d'effectif minimum Le critère d'effectif minimum pourra, par exemple, s'écrire pour la ligne io : Pour ce faire, on pourra marquer d'un drapeau les couples de lignes dont au moins l'une d'elles ne vérifie pas la condition d'effectif minimum (13) et l'on fusionnera le premier couple de lignes d'indices io et io+l portant un tel drapeau. Après fusion on met à jour les drapeaux des lignes adjacentes io-l et io+2 en fonction de l'effectif atteint par la ligne fusionnée. Lorsque toutes les lignes ont atteint l'effectif minimum, seule la condition (12) est prise en compte puisque critère le critère d'effectif minimum est rempli. La Fig. 1 illustre l'algorithme d'un exemple de méthode de discrétisation selon l'invention. L'algorithme débute par une étape 100 de partition du domaine de valeurs de la loi source en intervalles élémentaires ordonnés. La valeur de pour le tableau de contingence et les valeurs X (,) pour les 1 lignes du tableau sont calculées en 110. Les valeurs sont ensuite déduites des valeurs X (l) à l'étape 120 et triées par valeurs décroissantes sous forme de liste en 130. Chaque élément de la liste correspond à la fusion possible d'un couple de lignes i et i+ 1. L'étape 140 teste si la condition d'effectif minimum (13) est vérifiée. Dans l'affirmative, on passe directement au test 150. Dans la négative, on poursuit par l'étape 145. A l'étape 145, on donne priorité (au moyen de drapeaux) aux couples de lignes dont l'une d'entre elles au moins n'a pas atteint l'effectif minimum et l'on sélectionne en 165 le premier couple prioritaire de la liste que nous noterons (io, io+l). Le processus se poursuit en 170. A l'étape 150, on teste si le premier élément de la liste vérifie la condition (12). Si ce n'est pas le cas, le processus se termine en 190. En revanche, dans l'affirmative, on sélectionne en 160 le premier couple de la liste, que nous noterons également (io, io+l) et l'on poursuit par l'étape 170. A l'étape 170, les lignes io et io+1 du couple sélectionné sont fusionnées, c'est- à-dire les intervalles S, et Sil sont concaténés. La nouvelle valeur de est ensuite 2 calculée en 180 ainsi que les nouvelles valeurs de A et A, pour les intervalles adjacents, s'ils existent. En 185, La liste des valeurs est mise à jour : 2 2 sont sup rime les anciennes valeurs A,,, et A, sont supprimées et les nouvelles valeurs 0'0 0'0 sont stockées. La liste des valeurs Aest avantageusement organisée sous forme d'arbre binaire de recherche équilibré permettant de gérer les insertions/suppressions tout en maintenant la relation d'ordre dans la liste. Ainsi, il n'est pas nécessaire de trier complètement la liste à chaque étape. La liste des drapeaux est également mise à jour. Après la mise à jour, le processus retourne à l'étape de test 140. Selon une variante de réalisation, la liste est constituée par les valeurs (positives) X"HI) au lieu d'être constituée par valeurs (negatives) Au terme du processus de discrétisation, on dispose de la valeur du : 1 de l'attribut discrétisé. Ainsi, si l'on procède à la discrétisation d'une pluralité d'attributs source Sk. on peut comparer leur ca source Sk, on peut comparer leur capacité prédictive vis à vis de l'attribut cible en 2 comparant les probabilités prOXk, Ak) où les et ak sont les valeurs de : 1 et les k c degrés de liberté respectifs des attributs discrétisés. Nous avons supposé jusqu'à présent que l'attribut S était numérique monodimensionnel à valeurs continues. La méthode de discrétisation exposée ci-dessus est encore applicable lorsque S est à valeurs numériques discrètes. Les modalités numériques sont d'abord ordonnées pour former les lignes du tableau de contingence de S et T puis regroupées par groupes élémentaires, un groupe élémentaire pouvant, le cas échéant, ne contenir qu'un seul élément. La méthode de discrétisation opère selon le même principe que précédemment, en fusionnant les groupes élémentaires tant que la probabilité d'indépendance de S et T diminue. La méthode de discrétisation peut encore opérer sur des attributs symboliques, à la différence qu'il n'existe pas nécéssairement de relation d'ordre total entre les modalités de l'attribut. Si une telle relation d'ordre existe, on peut se ramener au cas précédent en ordonnant les modalités selon cette relation d'ordre. La Fig. 2 illustre cette situation : les individus sont regroupés par groupes élémentaires Gl, G2,.., G1, chaque groupe contenant les individus relatifs à une modalité ou à un intervalle de modalités (au sens de la relation d'ordre précitée). Les groupes sont équivalents aux lignes du tableau de contingence. Ils peuvent être ordonnés au sein d'un graphe linéaire, chaque noeud correspondant à un groupe. La fusion ne peut être réalisée que selon les arcs de ce graphe, entre groupes voisins. En revanche, si l'ensemble des modalités de l'attribut source n'est pas pourvue d'une relation d'ordre total, on peut néanmoins définir des relations de voisinage par des arcs d'un graphe, comme représenté dans la partie gauche de la Fig. 3. Les arcs indiquent les fusions possibles entre les groupes. Après fusion de deux groupes, les arcs du graphe sont réorganisés. La partie droite de la Fig. 3 représente une réorganisation du graphe après fusion des groupes 3 et 4. La méthode de discrétisation opère ici sur les noeuds du graphe de la même façon qu'elle opérait précédemment sur les lignes du tableau de contigence. Le fonctionnement de la méthode de discrétisation sera illustré à l'aide d'un exemple relatif à une base de données contenant des attributs de fleurs de la famille des Iris. La population de la base de données considérée est de 150 individus. Nous envisagerons l'attribut source largeur de sépale et l'attribut cible classe de la fleur : Iris setosa, Iris versicolor, Iris virginica. Dans cet exemple, l'attribut source est un attribut numérique à valeurs continues et l'attribut cible est un attribut symbolique à 3 modalités. Le tableau de contingence est donné ci-après : Largeur de Iris Ins Iris Total sépale versicolor virginica setosa 2 1 0 0 1 2, 2 2 1 0 3 2,3 3 0 1 4 2, 4 3 0 0 3 2, 5 4 4 0 8 2, 63205 2, 7 5 4 0 9 2, 8 6 8 0 14 2, 9 7 2 1 10 3 8 12 6 26 3, 1 3 4 5 12 3, 2 3 5 5 13 3, 3 1 3 2 6 3, 4 1 2 9 12 3, 5 0 0 6 6 3, 6 0 1 2 3 3, 7 0 0 3 3 3,8 0 2 4 6 3,9 0 0 2 2 4 0 0 1 1 4, 1 0 0 1 1 4,2 0 0 1 1 4,4 0 0 1 1 Total 50 50 50 150 Tableau 5 Lors de l'initialisation, on partitionne le domaine des modalités de la largeur de sépale [0, +oo [en 23 intervalles élémentaires :]-oo ; 2, 1],] 2, 1 ; 2, 25]...] 4, 15 ; 4, 3],] 4, 3 ; +oo [. La valeur du est de 88, 36. En prenant la loi du à 44 degrés de libertés correspondante (44= (23-1) * (3-1)), on obtient une probabilité d'indépendance de 8,3 10-5. Comme indiqué dans le tableau 6, on calcule alors le résultant de chaque 2 fusion d'intervalles : Par exemple, la fusion des intervalles ]-00 ; 2, 1],] 2, 1 ; 2, 25] donne un nouvel intervalle]-oo ; 2, 25] et le i résultant de la nouvelle table réduite a une valeur de 87,86. 2 Intervalle fusionné #f(i,i+1) ]#; 2, 25] 87,86 ] 2, 10 ; 2, 35] 87,44 ] 2, 25,2, 45] 87,72 ] 2, 35 ; 2, 55] 85,09 ]2,45 ; 2, 65] 88, 18 ] 2, 55 ; 2, 75] 88,33 ] 2, 65 ; 2, 85] 87,83 ]2, 75 ; 2, 95] 84,49 ] 2, 85,3, 05] 83, 18 ]2, 95 ; 3, 15] 87,03 ]3, 05,3, 25] 88, 29 ]3, 15 ; 3, 35] 88,12 ] 3, 25 ; 3, 45] 84,86 ] 3, 35, 3, 55] 87,20 ]3, 45 ; 3, 65] 87,03 ]3, 55 ; 3, 75] 87,36 ] 3, 65 ; 3, 85] 87,03 J3, 75 ; 3, 95] 87,36 ] 3, 85 ; 4, 05J 88,36 ] 3, 95 ; 4, 15] 88,36 ]4,05 ; 4, 25] 88, 36 ]4,15; +# [ 88 36 Tableau 6 On cherche alors la fusion qui maximise le Ici, la valeur maximale du i résultant d'une fusion est de 88, 36, atteinte par exemple pour la fusion des deux derniers intervalles 4, 15 ; 4, 3] et] 4, 3 ; +oo [. En prenant la loi du à 42 degrés de liberté correspondante (il y a un intervalle en moins), on obtient une probabilité d'indépendance de 3, 8 10-5. La probabilité d'indépendance diminuant, la discrétisation est améliorée et on réalise la fusion correspondante. On recommence ces étapes tant qu'il y a amélioration de la discrétisation. Le tableau 7 illustre les étapes successives de discrétisation. Les chiffres en gras indiquent que l'effectif minimum est atteint, au sens de la relation (13). Ici, étant donné que les modalités de l'attribut cible sont équiréparties (ql=q2=q3) la relation (13) est équivalente à un effectif théorique par ligne de 33 (3. 1og2 (10*150)). Lorsque cet effectif est atteint pour toutes les lignes, on ne tient plus compte du critère d'effectif minimum. Largeur Iris Iris Iris Total de sépale versicolor virginica 2 1 0 0 1 3-1-0 9-1-1 34-21-2 2,2 2 1 0 3 2,3 3 0 1 4 6-0-1 2,4 3 0 0 3 2,5 4 4 0 8 12-10-0 18-18-0 25-20-1 2,6 3 2 0 5 8-6-0 2,7 5 4 0 9 2,8 6 8 0 14 2,9 7 2 1 10 3 8 12 6 26 15-24-18 3,1 3 4 5 12 6-9-10 7-12-12 3,2 3 5 5 13 3,3 1 3 2 6 3,4 1 2 9 12 1-2-15 1-5-24 1-5-30 3,5 0 0 6 6 3,6 0 1 2 3 0-1-5 0-3-9 3,7 0 0 3 3 3,8 0 2 4 6 3,9 0 0 2 2 0-0-6 4 0 0 1 1 0-0-2 0-0-4 4,1 0 0 1 1 4,2 0 0 1 1 0-0-2 4,4 0 0 1 1 Total 50 50 50 50 Tableau 7 Au bout d'une vingtaine d' Au bout d'une vingtaine d'étapes, on arrive à la loi discrétisée suivante : Largeur Iris Iris Iris Total de sépale versicolor virginica Setosa ]- ; 2. 95 [342257 [2. 95 ; 3. 35 [15241857 [3. 35 ; oo [1 5 30 36 Total 50 50 50 150 Tableau 8 La valeur du associée à la loi discrétisée est de 70, 74, ce qui correspond à une probabilité d'indépendance de 1, 66 10-14 (loi du à 4 degrés de libertés). Deux fusions d'intervalles sont encore possibles. La meilleure d'entre elles est la première fusion, qui correspond à un de valeur 54, 17. La probabilité d'indépendance associée est 1, 73 10-12 (loi du à 2 degrés de libertés). Cette fusion ne respecte pas la condition (12) (elle augmente la probabilité d'indépendance) et est donc refusée. L'attribut largeur de sépale) > a été discrétisé en 3 intervalles. Dans le premier intervalle, la classe Iris setosa est très rare. Dans les second, il y a équilibre entre les trois classes et dans le dernier, la classe Iris setosa est de loin la plus fréquente. Cette partition est celle qui minimise la probabilité d'indépendance des attributs largeur de sépale et classe de la fleur . Nous envisagerons maintenant le cas où l'attribut à discrétiser est multidimensionnel, c'est-à-dire où l'attribut peut s'exprimer comme un vecteur S= (S',.., e) où D est la dimension de l'attribut et Sd, d=1,.., D sont des attributs monodimensionnels. Nous considérerons pour simplifier le cas d'un attribut numérique bidimensionnel (D=2). Chaque individu peut alors être représenté comme un point ayant pour coordonnées les modalités de et individus de la base de donnée peut être ainsi projetée dans un plan (, S2) sous la forme d'un ensemble & de points. Les relations de voisinage entre ces points peuvent être visualisée à partir du diagramme de Voronoï de l'ensemble & . On rappelle que le diagramme de Voronoï associé à un ensemble & de points est une partition de l'espace (ici un plan) en cellules contenant chacune un point de & , chaque cellule étant définie comme l'ensemble des points de l'espace qui sont plus proches d'un point donné de S que de tous les autres points de S. Une cellule est formée d'un polyèdre (ici un polygone) convexe entourant un point de & , chaque face du polyèdre étant un plan médiateur du point de & associé à la cellule et d'un point voisin. A titre d'exemple, un diagramme de Voronoï associé à un ensemble de points est représenté en Fig. 4. A partir du diagramme de Voronoï on peut construire un diagramme dual, dit diagramme de Delaunay, reliant les points de & appartenant à des cellules adjacentes. On a représenté en Fig. 5 le diagramme (ou graphe) de Delaunay associé au diagramme de Voronoï de la Fig. 4. Chaque arc du graphe de Delaunay représente une relation de voisinage entre deux points de & . La méthode de discrétisation construit le graphe de Delaunay de S et utilise les arcs du graphe de Delaunay pour effectuer une partition de l'espace en zones élémentaires. Plus précisément, le graphe se compose d'arcs directs et d'arcs indirects. Les arcs directs entre deux noeuds ne passent que par les deux cellules adjacentes associées à ces noeuds. Le long d'un arc direct, le plus proche voisin est toujours un des deux points des deux cellules adjacentes. Les arcs indirects passent par au moins une troisième cellule de Voronoï. Le long d'un arc indirect, le plus proche voisin peut être un troisième point n'appartenant pas à une des deux cellules adjacentes. Lors d'un prétraitement, les arcs indirects sont éliminés. Seuls les arcs directs, traduisant une relation directe de proximité sont pris en compte lors de l'initialisation de la méthode de discrétisation. La fusion des cellules de Voronoï selon les arcs directs du graphe de Delaunay fournit les zones élémentaires. Après avoir effectué une partition de l'espace en zones élémentaires, la méthode de discrétisation opère itérativement par fusion de zones, les seules fusions autorisées étant indiquées par un arc (direct) dans le graphe de Delaunay. Comme dans le cas mono-dimensionnel la fusion de deux zones n'est réalisée que si la condition (12) est vérifiée, c'est-à-dire que si cette fusion conduit à une diminution de la probabilité d'indépendance des attributs S et T. La discrétisation fournit des régions connexes, chaque région étant en fait une réunion connexe de cellules de Voronoï. Chaque région regroupe des individus homogènes statistiquement vis à vis de l'attribut cible et a contrario deux régions distinctes ont un comportement distinct vis à vis de cet attribut. En outre, comme pour le cas mono-dimensionnel la valeur de probabilité d'indépendance obtenue à l'issue de la discrétisation permet de comparer les paires (de manière générales les n-uplets) d'attributs continus et de les classer en fonction de leur valeur prédictive d'un attribut cible. La méthode de discrétisation multi-dimensionnelle s'applique encore à un attribut symbolique multi-dimensionnel, c'est-à-dire à un attribut S= (S',.., SI) où fi sont des attributs symboliques. Comme dans le cas mono-dimensionnel on construit un graphe dont les noeuds sont des modalités ou des groupes de modalités et l'on spécifie par des arcs les fusions possibles entre groupes. A titre d'exemple, la Fig. 6 représente une population d'individus d'une base de données projetée sur le plan défini par deux attributs numériques continus. L'attribut cible est la classe des individus pouvant prendre la modalité classe 1 représentée par un losange ou la modalité classe 2 représentée par un point. La Fig. 7 représente le diagramme de Delaunay associé. On rappelle que l'on ne retiendra de ce diagramme que les arcs directs pour initialiser la liste des fusions possibles. La méthode de discrétisation telle qu'exposée ci-dessus conduit à quatre zones, indiquées en Fig. 8 par des niveaux de gris différents. Ces zones connexes sont formées par la fusion de cellules de Voronoï contenant chacune un individu de la population initiale. La discrétisation permet de visualiser le comportement du couple d'attributs numérique vis à vis de l'attribut cible. Dans l'exemple représenté, on observera une relation de dépendance en spirale entre le couple d'attributs et l'attribut cible. Le tableau de contingence est en fait le suivant : Classe 1 Classe 2 Effectifs Zone 1 11, 8% 88, 2% 212 Zone 2 2, 5% 97,5% 122 Zone 3 88, 7% 11, 3% 512 Zone 4 69, 5% 30,5% 154 Tableau 9 Ainsi, les zones 1 et 2 sont très majoritairement constituées d'individus de la classe 2 alors que la zone 3 est essentiellement constituée d'individus de la classe 1. REVENDICATIONS 1) Méthode de discrétisation d'un attribut d'une base de données contenant une population d'individus, ledit attribut, dit attribut source, pouvant prendre plusieurs modalités, caractérisée en ce que, dans une première étape, on regroupe lesdites modalités de l'attribut source en groupes élémentaires et, qu'à partir du tableau de contingence de l'attribut source et d'un attribut cible, on détermine, dans une seconde étape, parmi un ensemble de couples de groupes élémentaires, le couple de groupes élémentaires dont la fusion diminue le plus fortement la probabilité d'indépendance de l'attribut source et de l'attribut cible, et que l'on fusionne dans une troisième étape le couple de groupes élémentaires ainsi déterminé, lesdites seconde et troisième étapes étant itérées tant qu'il existe un couple de groupes élémentaires permettant de diminuer ladite probabilité d'indépendance. 2) Méthode de discrétisation selon la revendication 1, caractérisée en ce que, pour déterminer le couple de groupes élémentaires dans la seconde étape, on estime pour chaque couple de groupes élémentaires dudit ensemble, la valeur du du tableau de contingence après fusion dudit couple et l'on sélectionne le couple produisant la valeur du après fusion la plus élevée. 3) Méthode de discrétisation selon la revendication 2, caractérisée en ce que, pour chaque couple de groupes élémentaires, on calcule la variation du i du tableau de contingence avant et après fusion dudit couple. 4) Méthode de discrétisation selon la revendication 3, caractérisée en ce que les variations du associées aux différents couples sont triées sous forme de liste de valeurs décroissantes et que l'on sélectionne le premier couple de la liste. 5) Méthode de discrétisation selon l'une des revendications 2 à 4, caractérisée en ce que, le couple de groupes élémentaires étant sélectionné, on procède à la fusion dudit couple si la probabilité du i relative au tableau de contingence après fusion 2 dudit couple est inférieure à la probabilité du relative au tableau de contingence avant fusion. 6) Méthode de discrétisation selon la revendication 5, caractérisée en ce que les probabilités du i relatives au tableau de contingence avant et après fusion sont exprimées de manière logarithmique. 7) Méthode de discrétisation selon l'une des revendications précédentes, carcatérisée en ce que ledit ensemble de couples de groupes élémentaires est constitué de tous les couples de groupes voisins au sens d'une relation de voisinage prédéterminée. 8) Méthode de discrétisation selon la revendication 7, caractérisée en ce que l'on recherche parmi les couples de groupes élémentaires voisins ceux comprenant au moins un groupe présentant au moins un effectif théorique par case du tableau de contingence inférieur à un effectif minimum prédéterminé et qu'on les identifie comme couples prioritaires au moyen d'une information d'identification. 9) Méthode de discrétisation selon la revendication 8, caractérisée en ce que, s'il existe un ou des couples prioritaires, on fusionne le couple prioritaire produisant la valeur du après fusion la plus élevée. 10) Méthode de discrétisation selon l'une des revendications 7 à 10, caractérisée en ce que, l'attribut source étant un attribut numérique mono-dimensionnel, les groupes élémentaires voisins sont constitués par des intervalles adjacents. 11) Méthode de discrétisation selon l'une des revendications 7 à 10, caractérisée en ce que, l'attribut source étant un attribut numérique multi-dimensionnel formé par pluralité d'attributs numériques mono-dimensionnels et les individus de la population étant représentés par des points dans l'espace desdits attributs, lesdits groupes élémentaires sont les cellules de Voronoï de cet espace, contenant lesdits points. 12) Méthode de discrétisation selon la revendication 11, caractérisée en ce que l'on construit le graphe de Delaunay associé aux cellules de Voronoï et que l'on élimine de ce graphe tout arc joignant deux cellules voisines en passant par une troisième, les couples de groupes élémentaires voisins étant alors donnés par les arcs du graphe de Delaunay après l'étape d'élimination. 13) Méthode de discrétisation selon l'une des revendications 7 à 10, caractérisée en ce que l'attribut source est de type symbolique. 14) Méthode d'évaluation de la dépendance d'un attribut d'une base de données vis à vis d'un attribut cible, caractérisée en ce que ledit attribut est discrétisé par la méthode de discrétisation selon l'une des revendications 1 à 13 et que la dépendance dudit attribut est estimée à partir de la probabilité de la valeur du de l'attribut ainsi discrétisé. 15) Méthode d'évaluation de la dépendance d'un attribut numérique bidimensionnel, formé par un couple d'attributs numériques mono-dimensionnels, vis à vis d'un attribut cible et les individus de la population étant représentés par des points dans le plan desdits attributs, caractérisée en ce que l'attribut bi-dimensionnel est discrétisé par la méthode de discrétisation selon la revendication 12 et que l'on visualise par des moyens de visualisation des goupes de cellules de Voronoï fusionnées par ladite méthode. 16) Logiciel de data mining comprenant un programme de discrétisation d'au moins un attribut d'une base de données, caractérisé en que son exécution sur un ordinateur effectue les étapes de la méthode revendiquée selon l'une des revendications précédentes.