Method and apparatus for input classification using a neuron-based voting scheme

• US 5,452,399 A
• Filed: 12/30/1993
• Issued: 09/19/1995
• Est. Priority Date: 06/19/1992
• Status: Expired due to Term

• Current Assignee: United Parcel Service Of America Incorporated (United Parcel Service Incorporated)
• Original Assignee: United Parcel Service Of America Incorporated (United Parcel Service Incorporated)
• Inventors: Moed, Michael C.
• Primary Examiner(s): MacDonald, Allen R.
• Assistant Examiner(s): Shapiro, Stuart B.
• Application Number:
  US08/176,075
• Time in Patent Office: 628 Days
• Field of Search: 395/22, 395/23, 395/24, 382/14, 382/15
• US Class Current: 706/20
• CPC Class Codes: G06F 18/23213 with fixed number of clusters, e.g. K-means clustering
• CPC Class Codes: G06F 18/24137 Distances to cluster centroïds
• CPC Class Codes: G06F 18/2414 Smoothing the distance, e.g. radial basis function networks [RBFN]
• CPC Class Codes: G06F 18/24143 Distances to neighbourhood prototypes, e.g. restricted Coulomb energy networks [RCEN]
• CPC Class Codes: G06V 30/19107 Clustering techniques
• CPC Class Codes: G06V 30/19173 Classification techniques

Abstract

The present invention is a classification method and apparatus for classifying an input into one of a plurality of possible outputs. The invention generates a feature vector representative of the input. The invention then calculates a distance measure from the feature vector to the center of each neuron of a plurality of neurons, where each neuron is associated with one of the possible outputs. The invention then selects each neuron that encompasses the feature vector in accordance with the distance measure. The invention then determines a vote for each possible output, where the vote is the number of selected neurons that are associated with each possible output. If the vote for one of the possible outputs is greater than all other votes for all other possible outputs, then the invention selects that possible output as corresponding to the input. Otherwise, if the vote for one of the possible outputs is not greater than all other votes for all other possible outputs, then the invention identifies the neuron that has the smallest distance measure of all other neurons. If that smallest distance measure is less than a specified value, then the invention selects the possible output associated with that identified neuron as corresponding to the input.

Claims

1. A classification method for classifying an input into one of a plurality of possible outputs, comprising the steps of:

(a) generating, with a computer processor, a feature vector in a feature space, said feature vector being representative of said input;

(b) calculating, with the computer processor, a distance measure in said feature space from said feature vector to the center of each neuron of a neural network in said feature space, said neural network comprising a plurality of neurons, wherein said each neuron is associated with one possible output of said plurality of possible outputs;

(c) selecting, with the computer processor, each neuron of said plurality of neurons that encompasses said feature vector in accordance with said distance measure;

(d) determining, with the computer processor, a vote for each possible output of said plurality of possible outputs, wherein said vote is a function of the number of said selected neurons that are associated with said each possible output;

(e) if one said vote for a possible output is greater than all other said votes for all other possible outputs then classifying, with the computer processor, said input to be said possible output that has the greatest vote; and

(f) if one said vote for a possible output is not greater than all other said votes for all other possible outputs then;

(f) (1) identifying, with the computer processor, a neuron of said plurality of neurons that has the smallest distance measure of all other said neurons; and

(f) (2) classifying, with the computer processor, said input to be the possible output associated with said identified neuron.

2. The classification method of claim 1, wherein step (d) comprises the step of determining a vote for each possible output of said plurality of possible outputs by generating the number of said selected neurons that are associated with said each possible output.

3. The classification method of claim 1, wherein step (b) comprises the step of generating the distance measure from said feature vector to the center of a non-spherical neuron of said neural network, said non-spherical neuron comprising a boundary defined by two or more neuron axes of different length.

4. The classification method of claim 2, wherein step (b) comprises the step of generating the distance measure from said feature vector to the center of a non-spherical neuron of said neural network, said non-spherical neuron comprising a boundary defined by two or more neuron axes of different length.

5. The classification method of claim 1, wherein step (f)(2) comprises the step of classifying said input to be the possible output associated with said identified neuron only if said smallest distance measure is less than a specified value.

6. The classification method of claim 1, wherein step (d) comprises the step of determining a vote for each possible output of said plurality of possible outputs by generating the number of said selected neurons that are associated with said each possible output as weighted by the number of training feature vectors in said feature space that are associated with each selected neuron.

7. The classification method of claim 1, wherein:

step (a) comprises the step of generating, with the computer processor, a character feature vector in said feature space, said feature vector being representative of a character input;

step (b) comprises the step of calculating, with the computer processor, the distance measure in said feature space from the character feature vector to the center of each character-based neuron of a character-based neural network in said feature space, said neural network comprising a plurality of character-based neurons, wherein said each character-based neuron is associated with one possible character output of a plurality of possible character outputs;

step (c) comprises the step of selecting, with the computer processor, each character-based neuron of said plurality of character-based neurons that encompasses said character feature vector in accordance with said distance measure;

step (d) comprises the step of determining, with the computer processor, the vote for each possible character output of said plurality of possible character outputs, wherein said vote is a function of the number of said selected character-based neurons that are associated with said each possible character output;

step (e) comprises the step of, if one said vote for a possible character output is greater than all other said votes for all other possible character outputs then classifying, with the computer processor, said character input to be said possible character output that has the greatest vote; and

step (f) comprises the steps of, if one said vote for a possible character output is not greater than all other said votes for all other possible character outputs then;

step (f)(1) comprises identifying, with the computer processor, a character-based neuron of said plurality of character-based neurons that has the smallest distance measure of all other said character-based neurons; and

step (f) (2) comprises classifying, with the computer processor, said character input to be the possible character output associated with said identified character-based neuron.

8. A classification apparatus for classifying an input into one of a plurality of possible outputs, comprising:

(a) generating means for generating a feature vector in a feature space, said feature vector being representative of said input;

(b) calculating means for calculating a distance measure in said feature space from said feature vector to the center of each neuron of a neural network in said feature spaces said neural network comprising a plurality of neurons, wherein said each neuron is associated with one possible output of said plurality of possible outputs;

(c) selecting means for selecting each neuron of said plurality of neurons that encompasses said feature vector in accordance with said distance measure;

(d) determining means for determining a vote for each possible output of said plurality of possible outputs, wherein said vote is a function of the number of said selected neurons that are associated with said each possible output;

(e) voting means for classifying said input to be a possible output, if said vote for said possible output is greater than all other said votes for all other possible outputs; and

(f) identifying means for identifying a neuron of said plurality of neurons that has the smallest distance measure of all other said neurons and for classifying said input to be the possible output associated with said identified neuron, if one said vote for a possible output is not greater than all other said votes for all other possible outputs.

9. The classification apparatus of claim 8, wherein said determining means determines a vote for each possible output of said plurality of possible outputs by generating the number of said selected neurons that are associated with said each possible output.

10. The classification apparatus of claim 8, wherein the calculating means comprises means for calculating the distance measure from said feature vector to the center of a non-spherical neuron of said neural network, said non-spherical neuron comprising a boundary defined by two or more neuron axes of different length.

11. The classification apparatus of claim 9, wherein the calculating means comprises means for calculating the distance measure from said feature vector to the center of a non-spherical neuron of said neural network, said non-spherical neuron comprising a boundary defined by two or more neuron axes of different length.

12. The classification apparatus of claim 8, wherein means (f) comprises means for classifying said input to be the possible output associated with said identified neuron only if said smallest distance measure is less than a specified value.

13. The classification apparatus of claim 8, wherein means (d) comprises means for determining a vote for each possible output of said plurality of possible outputs by generating the number of said selected neurons that are associated with said each possible output as weighted by the number of training feature vectors in said feature space that are associated with each selected neuron.

14. The classification apparatus of claim 8, wherein:

means (a) generates a character feature vector in said feature space, said feature vector being representative of a character input;

means (b) calculates a distance measure in said feature space from said character feature vector to the center of each character-based neuron of a character-based neural network in said feature space, said neural network comprising a plurality of character-based neurons, wherein said each character-based neuron is associated with one possible character output of said plurality of possible character outputs;

means (c) selects each character-based neuron of said plurality of character-based neurons that encompasses said character feature vector in accordance with said distance measure;

means (d) determines a vote for each possible character output of said plurality of possible character outputs wherein said vote is a function of the number of said selected character-based neurons that are associated with said each possible character output;

means (e) characterizes said character input to be a possible character output, if said vote for said possible character output is greater than all other said votes for all other possible character outputs; and

means (f) identifies a character-based neuron of said plurality of character-based neurons that has the smallest distance measure of all other said character-based neurons and characterizes said character input to be the possible character output associated with said identified character-based neuron, if one said vote for a possible character output is not greater than all other said votes for all other possible character outputs.