Method for dicretizing attributes of a database

• US 20040158548A1
• Filed: 11/20/2003
• Published: 08/12/2004
• Est. Priority Date: 05/23/2001
• Status: Abandoned Application

• Current Assignee: France Telecom SA (Orange S.A.)
• Original Assignee: France Telecom SA (Orange S.A.)
• Inventors: Boulle, Marc
• Application Number:
  US10/478,880
• Publication Number:
  US 20040158548A1
• Time in Patent Office: Days
• US Class Current: 707/1
• CPC Class Codes: G06F 16/35 Clustering; Classification

Abstract

A discretization method for a database attribute containing a population of individuals, said attribute known as the source attribute, capable of assuming several modalities, the method characterized by an initial stage in which said source attribute modalities are regrouped into elementary groups, and a source and a target attribute contingency table is used to determine from among a set of elementary group pairs in a second stage the pair of elementary groups whose merger most extensively decreases the probability of independence of the source and the target attribute, and in a third stage the pair of elementary groups thus determined is merged, said second and third stages being iterative inasmuch as there is a pair of elementary groups allowing for said probability of independence to be decreased.

Claims

1. A discretization method for a database attribute containing a population of individuals, said attribute, known as the source attribute, capable of assuming several modalities, wherein in an initial stage said source attribute modalities are regrouped into elementary groups and wherein a source and a target attribute contingency table is used in a second stage to determine from among a set of elementary group pairs the pair of elementary groups whose merger most extensively decreases the probability of independence of the source and the target attribute, and wherein in a third stage the pair of elementary groups thus determined is merged, said second and third stages being iterative in as much as there is a pair of elementary groups allowing for said probability of independence to be decreased.

2. The discretization method of claim 1, wherein to determine the pair of elementary groups in the second stage an estimate is made of the value of Π

² in the contingency table for each pair of elementary groups of said set after merging said pair, and the pair producing the highest value of Π

² after merger is selected.

3. The discretization method of claim 2, wherein for each pair of elementary groups, a calculation is made of the variation of Π

² in the contingency table before and after merger of said pair.

4. The discretization method of claim 3, wherein variations of Π

² associated with the different pairs are arranged in the form of a list of decreasing values and the first pair on the list is selected.

5. The discretization method of any one of claims 2 to 4, wherein after selecting the pair of elementary groups, merger of said pair is then performed if the probability of Π

² relative to the contingency table after merger of said pair is less than the probability of Π

² relative to the contingency table before merger.

6. The discretization method of claim 5, wherein the probabilities of Π

² relative to the contingency table before and after merger are expressed logarithmically.

7. The discretization method of any one of the previous claims, wherein said set of elementary group pairs is comprised of all pairs of adjacent groups in the sense of a predetermined adjacency relationship.

8. The discretization method of claim 7, wherein among the pairs of adjacent elementary groups one searches for those comprising at least one group presenting at least one theoretical count per contingency table cell less than a predetermined minimum count and they are identified as priority pairs by means of identification data.

9. The discretization method of claim 8, wherein if there are one or more priority pairs, the priority pair producing the highest value of Π

² after merger is selected.

10. The discretization method of any one of claims 7 to 10 [sic], wherein when the source attribute is a one-dimensional numerical attribute the adjacent elementary groups are comprised of adjacent intervals.

11. The discretization method of any one of claims 7 to 10, wherein when the source attribute is a multi-dimensional numerical attribute formed by multiple one-dimensional and numerical attributes and the individuals of the population are represented by points in space of said attributes, said elementary groups are Voronoi cells of said space containing said points.

12. The discretization method of claim 11, wherein the Delaunay graph associated with the Voronoi cells is constructed and all arcs linking two adjacent cells by passing through a third are eliminated, with the pairs of elementary groups now given by the arcs of said Delaunay graph following the elimination stage.

13. The discretization method of any one of claims 7 to 10, wherein the source attribute is of a symbolic type.

14. A method for evaluating the dependence of a database attribute with regard to a target attribute, wherein said attribute is discretized by the discretization method according to any one of claims 1 to 13 and the dependence of said attributed is estimated on the basis on the probability of the value of Π

² for the attribute thus discretized.

15. A method for evaluating the dependence of a one-dimensional numerical attribute formed by a pair of one-dimensional numerical attributes with regard to a target attribute and with the individuals in the population represented by points in the plane of said attributes, wherein the one-dimensional attribute is discretized by the discretization method of claim 12 and wherein by visualization methods one can visualize groups of Voronoi cells merged by said method.

16. Data mining software comprising a discretization program for at least one database attribute, wherein when said program is run on a computer said program performs the stages of the method according to any one of the previous claims.