[go: up one dir, main page]

WO2002095620A2 - Procede de discretisation d'attributs d'une base de donnees - Google Patents

Procede de discretisation d'attributs d'une base de donnees Download PDF

Info

Publication number
WO2002095620A2
WO2002095620A2 PCT/FR2002/001711 FR0201711W WO02095620A2 WO 2002095620 A2 WO2002095620 A2 WO 2002095620A2 FR 0201711 W FR0201711 W FR 0201711W WO 02095620 A2 WO02095620 A2 WO 02095620A2
Authority
WO
WIPO (PCT)
Prior art keywords
attribute
discretization
groups
elementary groups
pair
Prior art date
Application number
PCT/FR2002/001711
Other languages
English (en)
Other versions
WO2002095620A3 (fr
Inventor
Marc Boulle
Original Assignee
France Telecom Sa
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by France Telecom Sa filed Critical France Telecom Sa
Priority to EP20020735548 priority Critical patent/EP1389325A2/fr
Priority to US10/478,880 priority patent/US20040158548A1/en
Publication of WO2002095620A2 publication Critical patent/WO2002095620A2/fr
Publication of WO2002095620A3 publication Critical patent/WO2002095620A3/fr

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/30—Information retrieval; Database structures therefor; File system structures therefor of unstructured textual data
    • G06F16/35—Clustering; Classification

Definitions

  • the present invention relates to a method for discretizing attributes of a database.
  • the invention finds particular application in the statistical exploitation of data, in particular in the field of supervised learning.
  • Data mining generally aims to explore, classify and extract the rules of associations underlying the. within a database. It is notably used to build classification or prediction models.
  • the classification makes it possible to identify within the database of categories from combinations of attributes, then to organize the data according to these categories. For example, if the database relates to purchases of products by consumers, these could be classified into different categories: loyal customers, occasional customers, customers looking for discounted products, customers looking for high-end products, etc.
  • Prediction aims to describe how one or more attributes of the database are will behave in the future. In the example of the purchasing database mentioned above, it may be interesting to predict the behavior of these consumers based on a drop or an increase in the price of a particular product.
  • supervised data mining is the construction of a predictive model aimed at predicting a given attribute.
  • This construction consists in searching among the attributes of the database considered to identify the one or those which have the strongest statistical dependence with a target attribute and to describe this dependence. For example, if we have classified consumers according to their annual purchase amounts into different consumption categories: heavy consumption, medium consumption, low consumption, it will be interesting to determine what are the attributes of the purchasing database which are the most correlated (or equivalently, the least statistically independent) of the attribute giving the consumption class. Note that instead of the target attribute
  • the values (also called modalities) taken by an attribute can be numeric (for example an amount of purchases) or symbolic (for example a category of consumption).
  • modalities for example an amount of purchases
  • symbolic attribute for example a category of consumption
  • certain methods of supervised data mining require a "discretization" of the numerical attributes.
  • discretization of a numerical attribute is meant here a division of the domain of the values taken by an attribute into a finite number of intervals. If the domain in question is a range of continuous values, the discretization will result in a quantification of this range. If this domain already consists of ordered discrete values, the discretization will have the function of grouping these values into groups of consecutive values.
  • top-down methods start from the full interval to be discretized and seek the best cut-off point in the interval by optimizing a predetermined criterion.
  • bottom-up methods start from elementary intervals and seek the best fusion of two adjacent intervals by optimizing a predetermined criterion. In both cases, they are applied iteratively until a stop criterion is satisfied.
  • Table 1 shows the contingency table of the variables S and T with the following conventions: n v is the number of individuals observed for the z 'th modality of the variable S and the th modality of the variable T. n t] is also called the observed number in box (ij); n, is the total number of individuals for the zth modality of the variable S. n, is also called observed workforce of line i; n j is the total number of individuals for the me modality of the variable T. n ⁇ is also called the observed workforce in column j; N is the total number of individuals.
  • I and J respectively the number of modalities of the attribute S and the number of modalities of the attribute T.
  • n is the number of the line / and " / + ⁇ is the number of the line z ' + l
  • the, + i j represent the observed proportions of modalities of T for the line i + 1.
  • the local probability distribution q, q ' ⁇ , .., q' j of the modalities of the target attribute can be expressed by:
  • ⁇ l + l is a random variable following a law from ⁇ 2 to J -1 degrees of freedom.
  • the ChiMerge method proposes to merge the lines z and z ' + l if:
  • prob (a, K) denotes the probability that ⁇ > ⁇ for the law of ⁇ 2 at K degrees of freedom and pn is a predetermined threshold value setting the method.
  • the value prob (, K) is obtained from a classic table of yr 2 giving the value of ⁇ as a function of d prob (, K) and K.
  • Condition (5) expresses that the probability of independence of S and T in view of the two lines considered is less than a threshold value.
  • the merging of consecutive lines is iterated as long as condition (5) is satisfied.
  • the merger of two lines leads to the consolidation of their terms and the summation of their staff. For example in the case of a numeric attribute with continuous values, we have before fusion:
  • a first problem raised by the use of the ChiMerge method is the choice of the parameter pn which must not be too high under penalty of merging all the lines nor too weak under penalty of merging no pair of them. In practice, it is very difficult to find a compromise.
  • a second intrinsic problem with this method is to operate locally without taking into account all the modalities (or the number of intervals) of the source attribute. We do not know a priori if the result of the discretization is globally optimal on this set.
  • the ChiMerge method is limited to one-dimensional discretization in the sense that it can operate on only one source attribute at a time and not on a p-tuple of attributes.
  • the ChiMerge method does not allow the probability of independence between a source attribute and a target attribute to be measured and, consequently, to classify source attributes according to their probability of independence vis opposite the target attribute.
  • the objective of the present invention is to propose a method for discretizing attributes which does not have the drawbacks and limitations stated above.
  • the invention is defined by a method for discretizing an attribute of a database containing a population of individuals, said attribute, called source attribute. can take several modalities, said method comprising a first step in which said modalities of the source attribute are grouped into elementary groups and, a second step in which one determines, from the contingency table of the source attribute and a target attribute, among a set of pairs of elementary groups, the pair of elementary groups whose fusion most strongly decreases the probability of independence of the source attribute and the target attribute. and a third step in which the pair of elementary groups thus determined is merged, said second and third steps being iterated as long as there is a pair of elementary groups making it possible to reduce said probability of independence.
  • the variation of jr 2 of the contingency table is calculated before and after fusion of said pair.
  • the variations of the ⁇ associated with the different couples will then be sorted in the form of a list of decreasing values and that the first couple in the list will be selected.
  • the pair of elementary groups being selected said pair will be merged if the probability of ⁇ relating to the contingency table after merging said pair is less than the probability of tf relating to the contingency table before merging.
  • the probabilities of ⁇ 2 relating to the contingency table before and after fusion are expressed in a logarithmic manner.
  • said set of pairs of elementary groups consists of all the pairs of neighboring groups in the sense of a predetermined neighborhood relationship.
  • One preferably searches among the pairs of neighboring elementary groups for those comprising at least one group having at least one theoretical workforce per cell of the contingency table less than a predetermined minimum workforce and they are identified as priority couples by means of information of identification. In this case, if there is one or more priority couples, the priority couple is produced, producing the highest value of% after fusion.
  • the source attribute being a mono-dimensional numeric attribute
  • the neighboring elementary groups are formed by adjacent intervals.
  • the source attribute being a multidimensional numeric attribute formed by plurality of monodimensional numeric attributes and the individuals of the population being represented by points in the space of said attributes, said elementary groups are the Voronoi cells in this space, containing said points.
  • the source attribute is of symbolic type.
  • the invention also relates to a method for evaluating the dependence of a two-dimensional digital attribute, formed by a pair of digital attributes. mono-dimensional, with respect to a target attribute.
  • the individuals of the population are represented by points in the plane of said attributes.
  • the two-dimensional attribute is discretized by the multidimensional discretization method mentioned above and is visualized by means of visualization of the groups of Voronoi cells fused by said method.
  • the invention relates to data mining software comprising a discretization program of at least one attribute of a database, such that its execution on a computer performs the steps of the method described above.
  • FIG. . 1 illustrates in the form of a flowchart the method for discretizing attributes according to an embodiment of the invention
  • Fig. 2 illustrates a first example of discretization of a symbolic attribute
  • Fig. 3 illustrates a second example of discretization of a symbolic attribute before and after fusion
  • Fig. 4 shows an example of a Noronoi diagram
  • Fig. 5 shows the Delaunay diagram associated with the Voronoi diagram of FIG. 4
  • Fig. 6 represents a set of individuals projected on the plane of two numerical attributes
  • Fig. 7 shows the Delaunay diagram associated with the set of individuals in FIG. 6
  • Fig. 8 represents the discretization zones associated with the set of individuals in FIG. 5.
  • a first general idea underlying the invention is to discretize a source attribute by optimizing a statistical criterion relating to the entire contingency table.
  • a second general idea on which the invention is based is to extrapolate this discretization to the multi-dimensional case by using a Delaunay graph.
  • Expression (8) can be expressed simply as a function of the value of the pre-merger:
  • ⁇ ⁇ , +1 is the variation of the result of the fusion of lines z and z ' + l.
  • the value of ⁇ ⁇ , +]) can be calculated explicitly as a function of the proportions of staff in lines z and z ' + l:
  • condition (12) reflects a decrease in the probability of independence of S and T after merging of the lines and i +1.
  • the value of ⁇ 2 can only decrease with fusion. Since prob (a, K) is a decreasing function of ⁇ and increasing of K, the relation (12) can be checked only thanks to the reduction in the number of degrees of freedom.
  • the decrease in the probability of independence will be all the more important as A ⁇ , t +]) will be low in absolute value, that is to say from relation (11) that the proportions observed for the lines considered will be more close and this for the smallest proportions q.
  • condition (12) If condition (12) is satisfied, the lines z ' o and z ' o + 1 are merged. On the other hand, if condition (12) is not verified, then it is not verified for any index as a result of the decrease in prob (, K) as a function of ⁇ . The merging process is then stopped.
  • the method described above leads to an ad hoc discretization of the domain of modalities, that is to say to a discretization which minimizes the independence between the source attribute and the target attribute over the entire domain.
  • the discretization method makes it possible to group adjacent intervals having similar prediction behaviors with respect to the target attribute, the grouping being stopped when it affects the quality of prediction, in other words when it no longer does decrease the probability of independence of attributes.
  • We obtain by successive mergers a contingency table whose number of lines is reduced and whose numbers per cell increase.
  • Fig. 1 illustrates the algorithm of an example of a discretization method according to the invention.
  • the algorithm begins with a step 100 of partitioning the domain of values of the source law into ordered elementary intervals.
  • the value of ⁇ 2 for the contingency table and the values ⁇ t) for the / rows of the table are calculated at 110.
  • the values ⁇ ⁇ + I) are then deducted from the values ⁇ in step 120 and sorted by decreasing values in the form of a list at 130.
  • Each element of the list corresponds to the possible fusion of a couple of lines z and z ' + l.
  • Step 140 tests whether the minimum staffing condition (13) is verified. If yes, we go directly to the test
  • step 145 If not, we continue with step 145.
  • step 145 priority is given (by means of flags) to the pairs of lines of which at least one of them has not reached the minimum number and in 165 the first priority couple of the list that we will note (io, z ' o + 1). The process continued in 170.
  • step 150 it is tested whether the first element of the list satisfies the condition (12).
  • step 170 the process ends in 190. If so, the first pair in the list is selected in 160, which we will also note (z ' o, z ' o + 1) and we continue with step 170.
  • step 170 the lines io and, _ • +! of the selected couple are merged, i.e. the intervals S, and S, * +1 are concatenated.
  • the new value of ⁇ ⁇ 2 la) is then calculated in 180 as well as the new values of ⁇ ⁇ ⁇ and ⁇ ⁇ +1) for the adjacent intervals, if they exist.
  • the list of values ⁇ ⁇ (+ I) is updated: the old values A ⁇ ⁇ l _ l ⁇ ) and ⁇ ⁇ t +1) are deleted and the new values are stored.
  • the list of values A ⁇ l +1) is advantageously organized in the form of a balanced binary search tree making it possible to manage insertions / deletions while maintaining the order relation in the list. Thus, it is not necessary to completely sort the list at each step.
  • the list of flags is also updated. After the update, the process returns to test step 140.
  • the list is constituted by the (positive) values ⁇ j , n +]) instead of being constituted by (negative) values A ⁇ l + 1 ⁇ .
  • the value of ⁇ 2 of the discretized attribute At the end of the discretization process, we have the value of ⁇ 2 of the discretized attribute.
  • the numerical modalities are first ordered to form the rows of the contingency table for S and T and then grouped by elementary groups, an elementary group can, if necessary, contain only one element.
  • the discretization method operates on the same principle as above, merging the elementary groups as long as the probability of independence of S and T decreases.
  • the discretization method can still operate on symbolic attributes, with the difference that there is not necessarily a total order relation between the modalities of the attribute. If such an order relation exists, we can come back to the previous case by ordering the modalities according to this order relation.
  • Fig. 2 illustrates this situation: the individuals are grouped by elementary groups G ⁇ , G 2 , .., G ⁇ , each group containing the individuals relating to a modality or to an interval of terms (within the meaning of the aforementioned order relation).
  • the groups are equivalent to the rows in the contingency table. They can be ordered within a linear graph, each node corresponding to a group. The fusion can only be carried out according to the arcs of this graph, between neighboring groups.
  • the operation of the discretization method will be illustrated using an example relating to a database containing attributes of flowers of the Iris family.
  • the population of the database considered is 150 individuals.
  • the source attribute is a numeric attribute with continuous values and the target attribute is a symbolic attribute with 3 modalities.
  • the contingency table is given below:
  • ⁇ associated with the discretized law is 70.74, which corresponds to a probability of independence of 1.66 IO "14 (law of ⁇ 2 to 4 degrees of freedom). Two merges of intervals are still the best of them is the first fusion, which corresponds to a ⁇ 2 of value 54.17.
  • the associated probability of independence is 1.73 10 "12 (law of ⁇ 2 to 2 degrees of freedom). This merger does not respect condition (12) (it increases the probability of independence) and is therefore refused.
  • the attribute “sep width” has been discretized in 3 intervals. In the first interval, the class Iris setosa is very rare. In the second, there is a balance between the three classes and in the last, the Iris setosa class is by far the most frequent. This partition is the one that minimizes the probability of independence of the attributes "width of sepal" and "class of the flower”.
  • D two-dimensional numerical attribute
  • Each individual can then be represented as a point having as coordinates the modalities of S and S 2 of the individual.
  • the population of N individuals in the database can thus be "projected" into a plane (S 1 , S 2 ) in the form of a set £ of points.
  • the neighborhood relationships between these points can be viewed from the Voronoi diagram of the set £.
  • the Noronoi diagram associated with a set £ of points is a partition of space (here a plane) in cells each containing a point of £, each cell being defined as the set of points in space which are closer to a given £ point than to any other £ point.
  • a cell is formed of a convex polyhedron (here a polygon) surrounding a point of £, each face of the polyhedron being a mediating plane of the point of £ associated with the cell and a neighboring point.
  • a Voronoi diagram associated with a set of points is shown in Fig. 4. From the Voronoi diagram we can construct a dual diagram, called the Delaunay diagram, connecting the points of £ belonging to adjacent cells. There is shown in FIG.
  • each arc of the Delaunay graph represents a neighborhood relationship between two points of £.
  • the discretization method builds the Delaunay graph of £ and uses the arcs of the Delaunay graph to partition the space into elementary areas. More precisely, the graph consists of direct arcs and indirect arcs.
  • the direct arcs between two nodes only pass through the two adjacent cells associated with these nodes.
  • the nearest neighbor is always a of the two points of the two adjacent cells.
  • the indirect arcs pass through at least a third Voronoi cell.
  • the nearest neighbor may be a third point not belonging to one of the two adjacent cells.
  • the indirect arcs are eliminated. Only the direct arcs, translating a direct relation of proximity are taken into account during the initialization of the method of discretization.
  • the fusion of Voronoi cells according to the direct arcs of the Delaunay graph provides the elementary zones.
  • the discretization method After having partitioned the space into elementary zones, the discretization method operates iteratively by merging zones, the only authorized mergers being indicated by an arc (direct) in the Delaunay graph. As in the mono-dimensional case the fusion of two zones is carried out only if the condition (12) is satisfied, that is to say that if this fusion leads to a reduction in the probability of independence of the attributes S and T.
  • the discretization provides connected regions - each region being in fact a connected union of Voronoi cells. Each region groups together individuals who are statistically homogeneous with regard to the target attribute and, conversely, two distinct regions have distinct behavior with regard to this attribute.
  • the independence probability value obtained at the end of the discretization makes it possible to compare the pairs (generally the n-tuples) of continuous attributes and to classify them according to their predictive value of a target attribute.
  • the multidimensional discretization method still applies to a symbolic multidimensional attribute, that is to say to an attribute are symbolic attributes.
  • a symbolic multidimensional attribute that is to say to an attribute are symbolic attributes.
  • FIG. 6 represents a population of individuals of a database projected on the plane defined by two continuous numeric attributes.
  • the target attribute is the class of individuals who can take the “class 1” modality represented by a diamond or the “class 2” modality represented by a point.
  • Fig. 7 shows the associated Delaunay diagram.
  • the discretization method as exposed above leads to four zones, indicated in Fig. 8 by different gray levels. These related zones are formed by the fusion of Voronoi cells, each containing an individual from the initial population.
  • the discretization makes it possible to visualize the behavior of the couple of numerical attributes with respect to the target attribute. In the example shown, a spiral dependence relationship will be observed between the pair of attributes and the target attribute.
  • the contingency table is actually the following:
  • zones 1 and 2 are overwhelmingly made up of class 2 individuals, while zone 3 is essentially made up of class 1 individuals.

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Data Mining & Analysis (AREA)
  • Databases & Information Systems (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
  • Complex Calculations (AREA)

Abstract

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, la méthode étant 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, à 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.

Description

Procédé de discrétisation d'attributs d'une base de données
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 tf 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 tf 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 : nv est le nombre d'individus observés pour la z'ème modalité de la variable S et la eme modalité de la variable T . nt] est encore appelé effectif observé de la case (ij) ; n, est le nombre total d'individus pour la z'eme modalité de la variable S . n, est encore appelé effectif observé de la ligne i ; nj est le nombre total d'individus pour la me modalité de la variable T . n} est encore appelé effectif observé de la colonne j ; N est le nombre total d'individus.
Figure imgf000005_0001
Figure imgf000006_0002
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. n n On définit l'effectif théorique ey de la case (if) par =-~- . etJ 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 :
Figure imgf000006_0001
Plus la valeur de 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 a (Z-l).(J-l) degrés de liberté. La loi du tf est celle suivie par une somme quadratique de valeurs aléatoires normales centrées. Elle a de fait l'expression d'une loi γ 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 tf 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 à / modalités et d'un attribut T à J modalités. La méthode ChiMerge considère seulement deux lignes consécutives i et z'+l du tableau de contingence. Soit q ,q 'ι,..,q '] la distribution locale (c'est-à-dire dans le contexte local des lignes consécutives i et i+1) de probabilité des modalités pour l'attribut cible T. Si n, est l'effectif de la ligne / et «/+ι est l'effectif de la ligne z'+l, les effectifs observés et théoriques de la ligne i s'expriment respectivement par «y=αy", et e =q' n où les ay représentent les proportions d'effectifs observés pour la ligne De même, les effectifs observés et théoriques de la ligne z'+l s'expriment respectivement par n,+1J=al+lJnl+u et e,^ j~q'jnι+l où les ,+ij représentent les proportions observées de modalités de T pour la ligne i+ 1. La distribution locale de probabilité q ,q 'ι,..,q 'j des modalités de l'attribut cible peut être exprimée par :
^+ ι.
* n +n (2)
',*+!,
Selon la méthode ChiMerge, on calcule la valeur du χ2 pour les lignes / et z'+l. j J soit, en tenant compte du fait que ∑«3r,,=-:∑fl, ==l :
Figure imgf000007_0001
soit encore après transformation :
Figure imgf000007_0002
χ l+l est une variable aléatoire suivant une loi du χ2 à J -1 degrés de liberté. La méthode ChiMerge propose de fusionner les lignes z et z'+l si :
prob(χυ+l,J-l)≤p n (5) où prob(a,K) désigne la probabilité que ^ >α pour la loi du χ2 à K degrés de libertés et pn est une valeur de seuil prédéterminée paramétrant la méthode. En pratique, la valeur prob( ,K) est obtenue à partir d'une table classique du yr2 donnant la valeur de α en fonction d prob( ,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 :
Figure imgf000008_0001
Tableau 2 et après fusion
Figure imgf000008_0002
Tableau 3
Un premier problème soulevé par l'emploi de la méthode ChiMerge est le choix du paramètre pn 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 mono- dimensionnelle en ce sens qu'elle ne peut opérer que sur un seul attribut source à la fois et non sur un p-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 jr2 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 tf relative au tableau de contingence avant fusion. Selon une variante, les probabilités du χ2 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 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.
Dans ce cas, on construit le graphe de Delaunay associé aux cellules de Noronoï 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 multi- dimensionnelle 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 Noronoï ; 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-dirnensionnel à 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 S*^.?/, -?*+![, i=l,..,I. Nous souhaitons évaluer le degré d'indépendance de cet attribut avec un attribut cible T de modalités Tj,j=l,..,J. Ces modalités 7 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 :
Figure imgf000012_0004
Tableau 4
D'après (1) la valeur du ^ sur l'ensemble du tableau peut s'exprimer par
Figure imgf000012_0001
Soit encore en notant
Figure imgf000012_0002
la distribution de probabilité des modalités de l'attribut cible et αtJ les proportions d'effectifs observés pour la ligne / et en j i remarquant que ey -= ,«, , n =αl}nt et ^≈ -^≈l : j=l }=\
Figure imgf000012_0003
où χ^ est la valeur du Pour -*a uSne z. L'expression (7) signifie que le est additif par rapport aux lignes du tableau. Supposons maintenant que deux lignes consécutives / et z'+l soient fusionnées. La valeur du après fusion, notée
Figure imgf000013_0001
peut s'écrire :
Figure imgf000013_0002
où % ) est la valeur du pour la ligne résultant de la fusion, c'est-à-dire
Figure imgf000013_0003
L'expression (8) peut s'exprimer simplement en fonction de valeur du avant fusion :
2 _ 2 2 2 2 _ 2 . 2 f(u+î)~X ~ ~X( (ι,ι+l) " Λf(,ή)— X Λ-{(ι,++Xl))~% +ΔX( (ι;,/,+!) (10)
où Δ^,+1) est la variation du résultant de la fusion des lignes z et z'+l. La valeur de Δ^,+]) peut être calculée explicitement en fonction des proportions d'effectifs des lignes z et z'+l :
Figure imgf000013_0004
La liste des valeurs de A (+1 est triée par valeurs décroissantes. Soit Aχ. (Vo+l) premier élément de la liste. On teste alors si :
Figure imgf000013_0005
On notera que la loi du χ2 pour le premier terme n'a plus que (/-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 et i +1. Etant donné la valeur négative Δ^o,o+I) 5 la valeur du χ2 ne peut que décroître avec la fusion. Etant donné que prob(a,K) est une fonction décroissante de α 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χ, t +]) sera faible en valeur 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 z'o et z'o+1. En revanche, si la condition (12) n'est pas vérifiée, alors elle n'est vérifiée pour aucun indice par suite de la décroissance de prob( ,K) en fonction de α. Le processus de fusion est alors arrêté.
Si les lignes z'o et z'o+1 ont été fusionnées, on met à jour la liste des valeurs Aχ l+X) . 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 zVj-1 et z'o+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 χ2 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 ey un phénomène, dit de « sur-apprentissage » dans lequel, à partir d'une valeur élevée du χ2 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 ig:
eio J≥\og2(lON) ≈l, -,J (13)
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+1 portant un tel drapeau. Après fusion on met à jour les drapeaux des lignes adjacentes z'o-1 et z'o+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 χ2 pour le tableau de contingence et les valeurs χt) pour les / lignes du tableau sont calculées en 110. Les valeurs Δ^ +I) sont ensuite déduites des valeurs ^ à 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 z et z'+l. 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, z'o+1). 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 (z'o , z'o+1) et l'on poursuit par l'étape 170.
A l'étape 170, les lignes io et ,_•+! du couple sélectionné sont fusionnées, c'est- à-dire les intervalles S, et S,*+1 sont concaténés. La nouvelle valeur de χ{ 2 la) est ensuite calculée en 180 ainsi que les nouvelles valeurs de χ^ ^ et Δ^ +1) pour les intervalles adjacents, s'ils existent. En 185, La liste des valeurs Δ^(+I) est mise à jour: les anciennes valeurs Aχ{l _lΛ) et χ^t +1) sont supprimées et les nouvelles valeurs sont stockées. La liste des valeurs Aχl +1) est 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) χj,n+]) au lieu d'être constituée par valeurs (négatives) A ^l+1} . Au terme du processus de discrétisation, on dispose de la valeur du χ2 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 capacité prédictive vis à vis de l'attribut cible en comparant les probabilités prob[χk 2,akj où les
Figure imgf000016_0001
sont les valeurs de χ2 et les degrés de liberté respectifs des attributs discrétisés. Nous avons supposé jusqu'à présent que l'attribut S était numérique mono- dimensionnel à 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écessairement 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 G\,G2,..,Gι, 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 :
Figure imgf000018_0002
Tableau 5
Lors de l'initialisation, on partitionne le domaine des modalités de la largeur de sépale [θ,+∞[en 23 intervalles élémentaires : ]- ∞; 2,1], ]2,1; 2,25] ... ]4,15; 4,3], ]4,3; +oo[. La valeur du χ2 est de 88,36. En prenant la loi du χ2 à 44 degrés de libertés correspondante (44=(23-l)*(3-l)), on obtient une probabilité d'indépendance de 8,3 10"5. Comme indiqué dans le tableau 6, on calcule alors le χ2 résultant de chaque fusion d'intervalles :
Figure imgf000018_0001
- Par exemple, la fusion des intervalles ]-α>; 2,1], ]2,1;
2,25] domie un nouvel intervalle ]-<x>; 2,25] et le χ2 résultant de la nouvelle table réduite a une valeur de 87,86.
Figure imgf000019_0001
On cherche alors la fusion qui maximise le χ2 Ici, la valeur maximale du χ2 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 χ2 à 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 (q\=qr=qi) 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.
Figure imgf000020_0001
Figure imgf000020_0002
Tableau 7
Au bout d'une vingtaine d'étapes, on arrive à la loi discrétisée suivante:
Figure imgf000020_0003
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 IO"14 (loi du χ2 à 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 χ2 de valeur 54,17. La probabilité d'indépendance associée est 1,73 10"12 (loi du χ2 à 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 multi- dimensionnel, c'est-à-dire où l'attribut peut s'exprimer comme un vecteur S=(SX , ..,S°) où D est la dimension de l'attribut et Sd, d=\,..,D sont des attributs mono- dimensionnels. Nous considérerons pour simplifier le cas d'un attribut numérique bi- dimensionnel (D=2). Chaque individu peut alors être représenté comme un point ayant pour coordonnées les modalités de S et S2 de l'individu. La population des N individus de la base de donnée peut être ainsi « projetée » dans un plan (S1, 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 Noronoï 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 £ que de tous les autres points de £. 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 £ 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
Figure imgf000022_0001
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 :
Figure imgf000023_0001
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.

Claims

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 χ2 du tableau de contingence après fusion dudit couple et l'on sélectionne le couple produisant la valeur du χ2 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 χ2 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 χ2 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 χ2 relative au tableau de contingence après fusion dudit couple est inférieure à la probabilité du χ2 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 χ2 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 χ2 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 χ2 de l'attribut ainsi discrétisé.
. 15) 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 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.
PCT/FR2002/001711 2001-05-23 2002-05-21 Procede de discretisation d'attributs d'une base de donnees WO2002095620A2 (fr)

Priority Applications (2)

Application Number Priority Date Filing Date Title
EP20020735548 EP1389325A2 (fr) 2001-05-23 2002-05-21 Procede de discretisation d'attributs d'une base de donnees
US10/478,880 US20040158548A1 (en) 2001-05-23 2002-05-21 Method for dicretizing attributes of a database

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
FR01/07006 2001-05-23
FR0107006A FR2825168A1 (fr) 2001-05-23 2001-05-23 Procede de discretisation d'attributs d'une base de donnees

Publications (2)

Publication Number Publication Date
WO2002095620A2 true WO2002095620A2 (fr) 2002-11-28
WO2002095620A3 WO2002095620A3 (fr) 2003-03-06

Family

ID=8863733

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/FR2002/001711 WO2002095620A2 (fr) 2001-05-23 2002-05-21 Procede de discretisation d'attributs d'une base de donnees

Country Status (4)

Country Link
US (1) US20040158548A1 (fr)
EP (1) EP1389325A2 (fr)
FR (1) FR2825168A1 (fr)
WO (1) WO2002095620A2 (fr)

Families Citing this family (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
FR2849249A1 (fr) * 2002-12-19 2004-06-25 France Telecom Methode de discretisation/groupage d'un attribut source ou d'un groupe attributs source d'une base de donnees
US7644083B1 (en) * 2004-09-30 2010-01-05 Teradata Us, Inc. Efficiently performing inequality joins
US8135667B2 (en) * 2009-12-31 2012-03-13 Teradata Us, Inc. System, method, and computer-readable medium that facilitate in-database analytics with supervised data discretization
US11314826B2 (en) 2014-05-23 2022-04-26 Samsung Electronics Co., Ltd. Method for searching and device thereof
US9990433B2 (en) 2014-05-23 2018-06-05 Samsung Electronics Co., Ltd. Method for searching and device thereof
TWI684936B (zh) * 2017-04-19 2020-02-11 鎮裕貿易股份有限公司 具商業模式功能之售後系統平台

Family Cites Families (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH0877010A (ja) * 1994-09-07 1996-03-22 Hitachi Ltd データ分析方法および装置
JP2001519070A (ja) * 1997-03-24 2001-10-16 クイーンズ ユニバーシティー アット キングストン 一致検出の方法、製品および装置
US6192360B1 (en) * 1998-06-23 2001-02-20 Microsoft Corporation Methods and apparatus for classifying text and for building a text classifier
US6742003B2 (en) * 2001-04-30 2004-05-25 Microsoft Corporation Apparatus and accompanying methods for visualizing clusters of data and hierarchical cluster classifications

Non-Patent Citations (4)

* Cited by examiner, † Cited by third party
Title
BAY S D: "Multivariate discretization for set mining" KNOWLEDGE AND INFORMATION SYSTEMS, NOV. 2001, SPRINGER-VERLAG, UK, vol. 3, no. 4, pages 491-512, XP002204468 ISSN: 0219-1377 *
DOUGHERTY J ET AL: "Supervised and unsupervised discretization of continuous features" MACHINE LEARNING. PROCEEDINGS OF THE TWELFTH INTERNATIONAL CONFERENCE ON MACHINE LEARNING, PROCEEDINGS OF 12TH INTERNATIONAL CONFERENCE ON MACHINE LEARNING, TAHOE CITY, CA, USA, 9-12 JULY 1995, pages 194-202, XP002204467 1995, San Francisco, CA, USA, Morgan Kaufmann Publishers, USA *
HUAN LIU ET AL: "Chi2: feature selection and discretization of numeric attributes" PROCEEDINGS. SEVENTH INTERNATIONAL CONFERENCE ON TOOLS WITH ARTIFICIAL INTELLIGENCE (CAT. NO.95CB35878), PROCEEDINGS OF 7TH IEEE INTERNATIONAL CONFERENCE ON TOOLS WITH ARTIFICIAL INTELLIGENCE, HERNDON, VA, USA, 5-8 NOV. 1995, pages 388-391, XP002204465 1995, Los Alamitos, CA, USA, IEEE Comput. Soc. Press, USA ISBN: 0-8186-7312-5 *
KERBER R: "ChiMerge: discretization of numeric attributes" AAAI-92. PROCEEDINGS TENTH NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE, SAN JOSE, CA, USA, 12-16 JULY 1992, pages 123-128, XP002204466 1992, Menlo Park, CA, USA, AAAI Press, USA *

Also Published As

Publication number Publication date
FR2825168A1 (fr) 2002-11-29
EP1389325A2 (fr) 2004-02-18
WO2002095620A3 (fr) 2003-03-06
US20040158548A1 (en) 2004-08-12

Similar Documents

Publication Publication Date Title
Lopes et al. Dynamic recommendation system using web usage mining for e-commerce users
US20190286752A1 (en) Efficient convolutional network for recommender systems
Alexander et al. Task-driven comparison of topic models
EP1483693B1 (fr) Representation informatique d&#39;une structure de donnees arborescente et methodes de codage/decodage associees
CN109325182B (zh) 基于会话的信息推送方法、装置、计算机设备及存储介质
EP2356493B1 (fr) Procede de modelisation geologique de donnees sismiques par correlation de traces
CN108763496B (zh) 一种基于网格和密度的动静态数据融合客户分类方法
US11232153B2 (en) Providing query recommendations
WO2007059033A1 (fr) Procede et dispositif permettant d&#39;identifier des donnees presentant un interet dans une base de donnees
WO2019129977A1 (fr) Detection d&#39;anomalies par une approche combinant apprentissage supervise et non-supervise
CN119128177A (zh) 基于用户需求的化塑产品推荐方法及系统
EP1746521A1 (fr) Procédé de classement d&#39;un ensemble de documents électroniques du type pouvant contenir des liens hypertextes vers d&#39;autres documents électroniques
Fahim A clustering algorithm based on local density of points
WO2006008350A1 (fr) Recherche automatique de similarite entre images incluant une intervention humaine
EP1389325A2 (fr) Procede de discretisation d&#39;attributs d&#39;une base de donnees
EP1984873A1 (fr) Procede et dispositif d&#39;aide a la construction d&#39;une arborescence de groupe de documents electroniques
EP1912170A1 (fr) Dispositif informatique de corrélation propagative
CN108921431A (zh) 政企客户聚类方法及装置
EP3622445B1 (fr) Procede, mise en oeuvre par ordinateur, de recherche de regles d&#39;association dans une base de donnees
EP1431880A1 (fr) Méthode de discrétisation/groupage d&#39;un attribut source ou d&#39;un groupe attributs source d&#39;une base de données
CN111814059B (zh) 基于网络表示学习和社团结构的矩阵分解推荐方法及系统
CN110197056B (zh) 关系网络和关联身份识别方法、装置、设备和存储介质
Miller Toward a personal recommender system
US20250045301A1 (en) Systems and methods for classifying substructure in graph data
Yadhati et al. Movie Recommender System with Visualized Embeddings

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A2

Designated state(s): AE AG AL AM AT AU AZ BA BB BG BR BY BZ CA CH CN CO CR CU CZ DE DK DM DZ EC EE ES FI GB GD GE GH GM HR HU ID IL IN IS JP KE KG KP KR KZ LC LK LR LS LT LU LV MA MD MG MK MN MW MX MZ NO NZ OM PH PL PT RO RU SD SE SG SI SK SL TJ TM TN TR TT TZ UA UG US UZ VN YU ZA ZM ZW

AL Designated countries for regional patents

Kind code of ref document: A2

Designated state(s): GH GM KE LS MW MZ SD SL SZ TZ UG ZM ZW AM AZ BY KG KZ MD RU TJ TM AT BE CH CY DE DK ES FI FR GB GR IE IT LU MC NL PT SE TR BF BJ CF CG CI CM GA GN GQ GW ML MR NE SN TD TG

121 Ep: the epo has been informed by wipo that ep was designated in this application
AK Designated states

Kind code of ref document: A3

Designated state(s): AE AG AL AM AT AU AZ BA BB BG BR BY BZ CA CH CN CO CR CU CZ DE DK DM DZ EC EE ES FI GB GD GE GH GM HR HU ID IL IN IS JP KE KG KP KR KZ LC LK LR LS LT LU LV MA MD MG MK MN MW MX MZ NO NZ OM PH PL PT RO RU SD SE SG SI SK SL TJ TM TN TR TT TZ UA UG US UZ VN YU ZA ZM ZW

AL Designated countries for regional patents

Kind code of ref document: A3

Designated state(s): GH GM KE LS MW MZ SD SL SZ TZ UG ZM ZW AM AZ BY KG KZ MD RU TJ TM AT BE CH CY DE DK ES FI FR GB GR IE IT LU MC NL PT SE TR BF BJ CF CG CI CM GA GN GQ GW ML MR NE SN TD TG

DFPE Request for preliminary examination filed prior to expiration of 19th month from priority date (pct application filed before 20040101)
WWE Wipo information: entry into national phase

Ref document number: 2002735548

Country of ref document: EP

WWE Wipo information: entry into national phase

Ref document number: 10478880

Country of ref document: US

WWP Wipo information: published in national office

Ref document number: 2002735548

Country of ref document: EP

REG Reference to national code

Ref country code: DE

Ref legal event code: 8642

NENP Non-entry into the national phase

Ref country code: JP

WWW Wipo information: withdrawn in national office

Country of ref document: JP

WWW Wipo information: withdrawn in national office

Ref document number: 2002735548

Country of ref document: EP