Method and device for the generation of a classification tree to unify the supervised and unsupervised approaches, corresponding computer package and storage means

• US 20060195415A1
• Filed: 02/14/2006
• Published: 08/31/2006
• Est. Priority Date: 02/14/2005
• Status: Active Grant

• Current Assignee: Orange S.A.
• Original Assignee: Orange S.A.
• Inventors: Meyer, Franck
• Granted Patent: US 7,584,168 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers

Abstract

A method and apparatus are provided for the generation of a classification tree as a function of a classification model and from a set of data to be classified, described by a set of attributes. The method includes a step for obtaining said classification model, itself comprising a step for defining a mode of use for each attribute, which comprises specifying which property or properties are possessed by said attribute among the following at least two properties, which are not exclusive of each other: an attribute is marked target if it has to be explained; an attribute is marked taboo if it has not to be used as an explanatory attribute, an attribute not marked taboo being an explanatory attribute. Furthermore, the classification model belongs to the group comprising: supervised classification models with one target attribute, in each of which a single attribute is marked target and taboo, the attributes that are not marked target being not marked taboo; supervised classification models with several target attributes, in each of which at least two attributes, but not all the attributes, are marked target and taboo, the attributes not marked target being not marked taboo; and unsupervised classification models, in each of which all the attributes are marked target and at least one attribute is not marked taboo.

Claims

1. A method for the generation of a classification tree as a function of a classification model and from a set of data to be classified, described by a set of attributes, wherein the method comprises obtaining said classification model, itself comprising defining a mode of use for each attribute, which comprises specifying which property or properties are possessed by said attribute among the at least two following properties, which are not exclusive of each other:

an attribute is marked target if it has to be explained; and

an attribute is marked taboo if it has not to be used as an explanatory attribute, an attribute not marked taboo being an explanatory attribute; and

wherein, said classification model belongs to the group comprising;

supervised classification models with one target attribute, in each of which a single attribute is marked target and taboo, the attributes that are not marked target being not marked taboo;

supervised classification models with several target attributes, in each of which at least two attributes, but not all the attributes, are marked target and taboo, the attributes not marked target being not marked taboo; and

unsupervised classification models, in each of which all the attributes are marked target and at least one attribute is not marked taboo.

2. A method according to claim 1 wherein, among the unsupervised classification models, the following can be distinguished:

those in each of which all the attributes are marked target, and no attribute is marked taboo; and

those in each of which all the attributes are marked target, and at least one attribute, but not all the attributes, is marked taboo.

3. A method according to claim 1, wherein the definition of the mode of use for each attribute also takes account of the following property, not excluding the other two properties:

an attribute is marked as being masked if it has not to be taken into account to define said classification model.

4. A method according to claim 1, said decision tree comprising at least one node enabling the definition of a partition on a data subset received by said node, each node being a set of partitioning rules comprising at least one rule defined by at least one condition on at least one of the attributes wherein, to generate the set of rules of each node, the method comprises the following steps, performed iteratively so long as at least one end-of-exploration criterion has not been verified:

a) obtaining a new set of rules enabling the definition of a new partition on the data subset received by the node, the condition or conditions that define each rule pertaining solely to one or more attributes not marked taboo;

b) making a first evaluation of the quality of the new partition, by obtaining a new value of a first indicator computed with the set of data, only the attributes marked target influencing said first indicator; and

c) if the quality of the new partition, evaluated with the first criterion, is greater than that of the partitions evaluated during the preceding iterations, also with the first criterion, the new value of the first indicator is stored and becomes a current optimal value, and the new set of rules is stored and becomes a current optimal set of rules, so that, ultimately, the set of rules of said node is the current optimal set of rules at the time when an end-of-exploration criterion is verified.

5. A method according to claim 4, wherein the obtaining of a new value of the indicator, for a new partition, comprises the following steps:

a weight equal to one is assigned to each of the original attributes marked target and a weight equal to zero is assigned to each of the original attributes not marked target;

the set of original attributes is re-encoded as a set of attributes re-encoded Z_l. . .Z_Q such that;

if said original attribute A_j is of a discrete type and possesses N different modalities, it is re-encoded according to a full disjunctive re-encoding into N re-encoded attributes Z_d(j) . . . Z_f(j) having [O ;

1] as the value domain, with N=f(j)-d(j)+1, each of the N re-encoded attributes being assigned a weight identical to that of the original attribute from which they are derived;

if said original attribute A_j is of a continuous type, it is re-encoded as a re-encoded attribute, in standardizing its value domain at [O ;

1], said re-encoded attribute being assigned a weight identical to that of the original attribute from which it is derived;

the new partition is re-encoded in the space of the re-encoded attributes;

and

the Intra-Class Inertia of the new partition, re-encoded in the space of the re-encoded attributes, is computed.

6. A method according to claim 5, wherein the Intra-Class Inertia is defined by:

Intra (P)=Σ

^k_j=1(Σ

<sub>xjε

Cj</sub>P_id²(x_j,g_k))

where P is a partition of n points, formed by K subsets C_l. . . C_K, d(. ) is a function of distance between two points, p_i is the weight of the point number i, the sum of the weights p_i being equal to one, and

g_k is the center of gravity of the set of points belonging to the subset C_k, and wherein the distance function d( . ), for the data re-encoded in the space of the attributes re-encoded Z_l. . . Z_Q, is defined by;

d(d_a, d_b)=√

{square root over (Σ

^Q_j=1(DistanceZ_j(Z_ja, Z_jb)poidsZ(j))²)}

where d_a(Z_1a, Z_2a,. . . Z_Qa) and d_b(Z_1b, Z_2b,. . . Z_Qb) are two pieces of data re-encoded in the space of the re-encoded data Z_l. . . Z_Q, and;

DistanceZ_j(x_j,y_j)=|x_j-y_j| if Z_j is a re-encoded attribute coming from a continuous type of attribute,

Distance Z_j(x_j,y_j)=|x_j-y_j|/2 if Z_j is a re-encoded attribute coming from a full disjunctive re-encoding of a discrete attribute.

7. A method according to claim 4, wherein the step of obtaining a new set of rules, enabling the definition of a new partition, is performed according to a mode of stochastic generation of the partitions.

8. A method according to claim 7, wherein the mode of stochastic generation of the partition is based on a combinatorial optimization meta-heuristic of the VNS or “

variable neighborhood search”

type.

9. A method according to claim 1, said decision tree comprising at least one node enabling the definition of a partition on a data subset received by said node, each node being a set of partitioning rules comprising at least one rule defined by at least one condition on at least one of the attributes wherein, to generate the set of rules of each node, the method comprises the following steps, performed iteratively so long as at least one end-of-exploration criterion has not been verified:

a) obtaining a new set of rules enabling the definition of a new partition on the data subset received by the node, the condition or conditions that define each rule pertaining solely to one or more attributes not marked taboo;

b) making a first evaluation of the quality of the new partition, by obtaining a new value of a first indicator computed with the set of data, only the attributes marked target influencing said first indicator; and

c) if the quality of the new partition, evaluated with the first criterion, is greater than that of the partitions evaluated during the previous iterations, with the first criterion, then;

a second evaluation is made of the quality of the new partition, by obtaining a new value of a second indicator, having the same nature as the first indicator but being computed with a subset of test data;

if the quality of the new partition, evaluated with the second criterion, is greater than that of the partition evaluated during the previous iterations, with the second criterion, the new values of the first and second indicators are stored and become current optimal values and the new set of rules is stored and becomes a current optimal set of rules, and

if the quality of the new partition, evaluated with the second criterion, is lower than or equal to that of the partition evaluated during the previous iterations, with the second criterion, a counter is implemented and, if the counter has reached a determined threshold, an end-of-exploration criterion is considered to have been verified;

if not the new values of the first and second indicators are stored and become current optimal values and the new set of rules is stored and becomes a current optimal set of rules.

10. A computer program product comprising program code instructions to execute the steps of the method according to claim 1, when said program is executed on a computer.

11. A computer-readable storage means, which may be totally or partially detachable, storing a set of instructions executable by said computer to implement the method according to claim 1.

12. A device for the generation of a classification tree as a function of a classification model and from a set of data to be classified, described by a set of attributes, wherein the device comprises means for obtaining said classification model, the means themselves comprising means to define a mode of use for each attribute, making it possible to specify which property or properties are possessed by said attribute among the at least two following properties, which are not exclusive of each other:

an attribute is marked target if it has to be explained; and

an attribute is marked taboo if it has not to be used as an explanatory attribute, an attribute not marked taboo being an explanatory attribute, and wherein, said classification model belongs to the group comprising;

supervised classification models with one target attribute, in each of which a single attribute is marked target and taboo, the attributes that are not marked target being not marked taboo;

supervised classification models with several target attributes, in each of which at least two attributes, but not all the attributes, are marked target and taboo, the attributes not marked target being not marked taboo; and

unsupervised classification models, in each of which all the attributes are marked target and at least one attribute is not marked taboo.