METHOD FOR STABLE AND LINEAR UNSUPERVISED CLASSIFICATION UPON THE COMMAND ON OBJECTS

• US 20090287723A1
• Filed: 12/14/2006
• Published: 11/19/2009
• Est. Priority Date: 12/16/2005
• Status: Active Grant

• Current Assignee: Thales SA
• Original Assignee: Thales SA
• Inventors: Benhadda, Hamid, Ah-Pine, Julien, Lemoine, Julien
• Granted Patent: US 8,423,549 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification

Abstract

A method of linear unsupervised classification allowing a database composed of objects and of descriptors to be structured, which is stable on the order of the objects, comprises an initial step for transformation of the qualitative, quantitative or textual data into presence-absence binary data. A structural threshold α_s function is determined of the n² agreements between the objects to be classified with the structural threshold defining an optimization criterion adapted to the data. The descriptors are used as structuring and construction generators of a partition or set of classes. A class generated by a descriptor and a partition (40, 41, 42) progressively merged. For an optimization criterion involving a function ƒ(C_ii,C_i′i′)=Min(C_ii,C_i′i′), sums of Minimum functions are linearized.

Claims

1. A method of linear unsupervised classification allowing a database composed of objects and of descriptors to be structured, which is stable on the order of the objects, comprising an initial step for transformation of the qualitative, quantitative or textual data into presence-absence binary data, wherein it comprises the following steps:

determining a structural threshold α

_s function of the n² agreements between the objects to be classified, the structural threshold defining an optimization criterion adapted to the data,

using the descriptors as structuring and construction generators of a partition or set of classes,

progressively merging a class generated by a descriptor and a partition (40, 41, 42),

for an optimization criterion involving a function ƒ

(C_ii,C<sub>i′

i′</sub>

)=Min(C_ii,C<sub>i′

i′</sub>

), linearizing sums of Minimum functions.

2. The method as claimed in claim 1, comprising a step where the classes of the partition are regrouped amongst themselves.

3. The method as claimed in claim 1, wherein the merge step comprises a step where, based on two intersecting classes, the best operation (in terms of the optimization of the criterion) is determined from among the following 4:

breaking of the first class and formation of two classes;

breaking of the second class and formation of two classes;

breaking of the two classes in order to form three classes; and

joining of the two intersecting classes in order to form one single class.

4. The method of classification as claimed in claim 2, wherein the regrouping of the classes of a partition is carried out over several hierarchical levels and comprises the following steps:

decreasing at each level the value of the structural threshold in such a manner that the weakly negative contributions can become positive,

maximizing links between the classes formed where the links are determined by using the contribution from a pair of objects

$\begin{array}{c}\mathrm{Lien}<br><br>\left(C_q,C_{q^{\mathrm{\prime <br><br>}}}\right)=\underset{i\in <br><br>\mathrm{Cq}}{\sum <br><br>}<br><br>\underset{i^{\mathrm{\prime <br><br>}}\in <br><br>{\mathrm{Cq}}^{\mathrm{\prime <br><br>}}}{\sum <br><br>}<br><br>{\mathrm{Contrib}}_{{\mathrm{ii}}^{\mathrm{\prime <br><br>}}}\\ =\underset{i\in <br><br>\mathrm{Cq}}{\overset{}{\sum <br><br>}}<br><br>\underset{i^{\mathrm{\prime <br><br>}}\in <br><br>{\mathrm{Cq}}^{\mathrm{\prime <br><br>}}}{\sum <br><br>}<br><br>C_{{\mathrm{ii}}^{\mathrm{\prime <br><br>}}}-{\mathrm{\alpha <br><br>}}^{\mathrm{\prime <br><br>}}\times <br><br>f<br><br>\left(C_{\mathrm{ii}},C_{i^{\mathrm{\prime <br><br>}}<br><br>i^{\mathrm{\prime <br><br>}}}\right)\end{array}$

with α

′

the new value of α

combining two classes whose link is positive, and reiterate this process over all the levels.

5. A device allowing linear unsupervised classification that allows a database composed of objects and of descriptors to be structured, which is stable on the order of the objects, comprising an initial step for transformation of the qualitative, quantitative or textual data into presence-absence binary data, wherein it comprises at least the following elements:

a computer comprising a memory, a database and a processor adapted to implement the steps of the method as claimed in claim 1.

6. The device as claimed in claim 5, comprising a means for undertaking actions depending on the results of the classification.

7. A device allowing linear unsupervised classification that allows a database composed of object and of descriptors to be structured, which is stable on the order of the objects, comprising an initial step for transformation of the qualitative, quantitative or textual data into presence-absence binary data, wherein in comprises at least the following elements:

a computer comprising a memory, a database and a processor adapted to implement the steps of the method as claimed in claim 2.

8. The device as claimed in claim 5, wherein said processor is adapted to implement the steps of the method as claimed in claim 3.

9. The device as claimed in claim 7, wherein said processor is adapted to implement the steps of the method as claimed in claim 4.