Preprocessing means for use in a pattern classification system

• US 5,347,595 A
• Filed: 08/23/1991
• Issued: 09/13/1994
• Est. Priority Date: 10/10/1985
• Status: Expired due to Term

• Current Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Original Assignee: The Palantir Corp.
• Inventors: Bokser, Mindy R.
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US07/749,282
• Time in Patent Office: 1,117 Days
• Field of Search: 382/14, 382/15, 382/38, 382/36, 395/20, 395/21
• US Class Current: 382/225
• CPC Class Codes: G06F 18/23 Clustering techniques

Abstract

A method for preprocessing reference feature vectors representing patterns in order to form, for each selected pattern class, collections of regions. A hierarchy of possibility regions is formed, wherein all reference feature vectors of a pattern class are contained in each level of the hierarchy of possibility regions associated with the pattern class. This hierarchy is later used to exclude a pattern class from consideration if a feature vector representing an unknown pattern is not contained in some level of its associated hierarchy of possibility regions. A collection of certainty regions is used, wherein no reference feature vector not of a pattern class is contained within any certainty region associated with the pattern class. The certainty regions are later used to classify a feature vector representing an unknown pattern as belonging to a pattern class. A collection of confidence regions is used to identify, although not with certainty, an unknown input pattern, and assign a confidence value indicating the relative confidence associated with the possibility that this unknown input pattern belongs to the pattern class.

Claims

1. A method for processing reference data comprising the steps of:

obtaining reference data defining one or more references;

sorting said references into one or more classes;

forming a plurality of sets of ringed clusters, each said set of ringed clusters being uniquely associated with an associated class, such that each said set has associated therewith all of said references for its associated class,

wherein each said ringed cluster is a medium ringed cluster comprising;

possibility sphere, such that all said references of said associated class of a selected set of medium ringed clusters is contained in at least one of said possibility spheres said selected set of medium ringed clusters;

a certainty sphere in which is contained a plurality said references such that all of said references contained on said certainty sphere belong to said associated class of said medium ringed cluster; and

a confidence sphere lying between said certainty sphere and said possibility sphere.

3. The method of claims 1 or 2 wherein said confidence sphere is created by reading data not contained in said reference data and establishing confidence spheres for each said ringed cluster based upon said data which is not contained in one or more of said certainty spheres.

4. The method of claim 3 wherein said confidence spheres are created as enlarged certainty spheres, such that all of said data is contained in said confidence spheres of associated sets of ringed clusters.

5. The method of claim 4 wherein said certainty spheres of each said ringed cluster is enlarged by the same factor to create said confidence spheres.

6. The method of claim 4 wherein said certainty spheres of each said ringed cluster is enlarged by one of a selected set of factors to create said confidence spheres.

7. The method of claims 1 or 2 wherein said step of forming a plurality of sets of ringed clusters comprises the steps of:

selecting one of said classes;

selecting a relatively small number of said references belonging to said selected class such that said relatively small number of said references each form the center of one of said ringed clusters of said set of ringed clusters associated with said selected class.

8. The method of claim 7 wherein each of said references said selected class is associated with a selected one of said ringed clusters associated with said class.

9. The method of claim 8 wherein said ringed clusters include a possibility sphere such that all references of said class are contained within one or more possibility spheres associated with said class and said possibility spheres contain a minimum of references not belonging to said selected class.

10. The method of claims 1 or 2 wherein said step of forming a plurality of sets of ringed clusters comprises the steps of:

selecting one of said classes;

selecting the minimum number of said references belonging to said selected class such that said minimum number of said references each form the center of said ringed clusters for said set of ringed clusters associated with said selected class and such that all references of said selected class, and no references not of said selected class, are contained in a certainty sphere for said selected class.

2. A method for processing reference data comprising the steps of:

obtaining reference data defining one or more references;

sorting said references into one or more classes;

forming a plurality of sets of ringed clusters, each said set of ringed clusters being uniquely associated with an associated class, such that each said set has associated therewith all of said references for its associated class,

wherein each said ringed cluster is a fine ringed cluster including a certainty sphere in which is contained a plurality of said references such that all of said references of a class are contained in one or more of said certainty spheres belonging to a set of said fine ringed clusters, and

wherein each said fine ringed cluster includes a confidence sphere lying outside of said certainty sphere.