Data classification apparatus and method thereof

• US 7,072,873 B1
• Filed: 11/09/1999
• Issued: 07/04/2006
• Est. Priority Date: 11/09/1998
• Status: Expired due to Fees

• Current Assignee: Universal Prediction Limited
• Original Assignee: Royal Holloway University of London
• Inventors: Gammerman, Alex, Vovk, Volodya
• Primary Examiner(s): Starks, Wilbert L.
• Assistant Examiner(s): Tran, Mai T.
• Application Number:
  US09/831,262
• Time in Patent Office: 2,429 Days
• Field of Search: 706/20, 706/21, 706/25, 706/48, 600/301, 704/203, 704/251, 704239-240
• US Class Current: 706/20
• CPC Class Codes: G06F 18/21 Design or setup of recognition systems or techniques; Extraction of features in feature space; Blind source separation

Abstract

The data classification apparatus and method is adapted to high-dimensional classification problems and provide a universal measure of confidence that is valid under the iid assumption. The method employs the assignment of strangeness values to classification sets constructed using classification training examples and an unclassified example. The strangeness values of p-values are compared to identify the classification set containing the most likely potential classification for the unclassified example. The measure of confidence is then computed on the basis of the strangeness value of the classification set containing the second most likely potential classification.

Claims

1. A data classification apparatus comprising:

an input device for receiving a plurality of training classified examples and at least one unclassified example;

a memory for storing said classified and unclassified examples;

an output terminal for outputting a predicted classification for said at least one unclassified example; and

a processor for identifying the predicted classification of said at least one unclassified example

wherein the processor includes;

classification allocation means for allocating potential classifications to each said unclassified example and for generating a plurality of classification sets, each said classification set containing said plurality (l) of training classified examples with their classification and said at least one unclassified example (l+1) with its said allocated potential classification;

assay means including an example valuation device which determines individual strangeness values (α

_i) for each said training classified example (i=1,2 . . . l) and said at least one unclassified example (i=l+1) having an allocated potential classification (y), the assay means determining a single strangeness value (d(y)) valid under the independently and identically distributed assumption for each said classification set in dependence on said individual strangeness values (α

_i) of each example by the formula

$d<br><br>\left(y\right)=\frac{<br><br>\left\{i;<br><br>{\mathrm{\alpha <br><br>}}_i\ge <br><br>{\mathrm{\alpha <br><br>}}_{l+1}\right\}<br><br>}{l+1},<br><br>\mathrm{where}<br><br><br><br>i=1,2<br><br><br><br>\mathrm{\dots <br><br>}<br><br><br><br>l,l+1;<br><br>$

a comparative device for selecting the classification set to which the most likely allocated potential classification for said at least one unclassified example belongs, wherein said predicted classification output by the output terminal is said most likely allocated classification according to said single strangeness values assigned by said assay means; and

a strength of prediction monitoring device for determining a confidence value for said predicted classification on the basis of said single strangeness value assigned by said assay means to one of said classification sets to which the second most likely allocated potential classification of said at least one unclassified example belongs.

2. A data classification apparatus as claimed in claim 1, wherein Lagrange multipliers are used to determine said individual strangeness values.

3. A data classification apparatus comprising:

an input device for receiving a plurality of training classified examples and at least one unclassified example;

a memory for storing said classified and unclassified examples;

stored programs including an example classification program;

an output terminal for outputting a predicted classification for said at least one unclassified example; and

a processor controlled by said stored programs for identifying the predicted classification of said at least one unclassified example, wherein said processor includes;

classification allocation means for allocating potential classifications to each said unclassified example and for generating a plurality of classification sets, each said classification set containing said plurality (l) of training classified examples with their classification and said at least one unclassified example (l+1) with its allocated potential classification;

assay means including an example valuation device which determines individual strangeness values (α

_l) for each said training classified example (i=1,2 . . . l) and said at least one unclassified example (i=l+1) having an allocated potential classification (y), the assay means determining a single strangeness value (d(y)) valid under the independently and identically distributed assumption for each said classification set in dependence on said individual strangeness values (α

_i) of each example by the formula

$d<br><br>\left(y\right)=\frac{<br><br>\left\{i;<br><br>{\mathrm{\alpha <br><br>}}_i\ge <br><br>{\mathrm{\alpha <br><br>}}_{l+1}\right\}<br><br>}{l+1},<br><br>\mathrm{where}<br><br><br><br>i=1,2<br><br><br><br>\mathrm{\dots <br><br>}<br><br><br><br>l,l+1;<br><br>$

a comparative device for selecting the classification set to which the most likely allocated potential classification for said at least one unclassified example belongs, wherein the predicted classification output by said output terminal is the most likely allocated potential classification according to said single strangeness values assigned by said assay means and

a strength of prediction monitoring device for determining a confidence value for said predicted classification on the basis of said single strangeness value assigned by said assay means to one of said classification sets to which the second most likely allocated potential classification of said at least one unclassified example belongs.

4. A computer-implemented data classification method comprising:

inputting a plurality of training classified examples and at least one unclassified example;

identifying a predicted classification of said at least one unclassified example which includes,

allocating potential classifications to each said unclassified example;

generating a plurality (l) of classification sets, each said classification set containing said plurality of training classified examples with their classification and said at least one unclassified example (l+1) with its allocated potential classification;

determining an individual strangeness value (α

_i) for each said training classified example (i=1,2 . . . l) and said at least one unclassified example (i=l+1) having an allocated potential classification (y), and a single strangeness value (d(y)) valid under the independently and identically distributed assumption for each said classification set in dependence on the individual strangeness values (α

_i) of each example by the formula

$d<br><br>\left(y\right)=\frac{<br><br>\left\{i;<br><br>{\mathrm{\alpha <br><br>}}_i\ge <br><br>{\mathrm{\alpha <br><br>}}_{l+1}\right\}<br><br>}{l+1},<br><br>\mathrm{where}<br><br><br><br>i=1,2<br><br><br><br>\mathrm{\dots <br><br>}<br><br><br><br>l,l+1;<br><br>$

selecting the said classification set to which the most likely allocated potential classification for said at least one unclassified example belongs, wherein said predicted classification is the most likely allocated potential classification in dependence on said single strangeness values;

determining a confidence value for said predicted classification on the basis of the single strangeness value assigned to one of said classification sets to which the second most likely allocated potential classification for said at least one unclassified example belongs; and

outputting said predicted classification for said at least one unclassified example and said confidence value for said predicted classification.

5. A computer-implemented data classification method as claimed in claim 4, wherein said selected classification set is selected without the application of any general rules determined from the said training set.

6. A classification program stored on a computer readable medium for classifying data by performing the following steps:

generating a plurality of classification sets, each said classification set containing a plurality (l) of training classified examples with their classification and at least one unclassified example (l+1) that has been allocated a potential classification;

determining an individual strangeness value (α

_i) for each said training classified example (i=1,2 . . . l) and said at least one unclassified example (i=l+1) having an allocated potential classification (y), and a single strangeness value (d(y)) valid under the independently and identically distributed assumption for each said classification set in dependence on said individual strangeness values (α

_l) of each example by the formula

$d<br><br>\left(y\right)=\frac{<br><br>\left\{i;<br><br>{\mathrm{\alpha <br><br>}}_i\ge <br><br>{\mathrm{\alpha <br><br>}}_{l+1}\right\}<br><br>}{l+1},<br><br>\mathrm{where}<br><br><br><br>i=1,2<br><br><br><br>\mathrm{\dots <br><br>}<br><br><br><br>l,l+1;<br><br>$

selecting the classification set to which the most likely allocated potential classification for the said at least one unclassified example belongs, wherein the predicted classification is the most likely allocated potential classification in dependence on said single strangeness values; and

determining a confidence value for said predicted classification on the basis of said single strangeness value assigned to one of said classification sets to which the second most likely allocated potential classification for said at least one unclassified example belongs.