Method and system for selecting pattern recognition training vectors

• US 5,796,924 A
• Filed: 03/19/1996
• Issued: 08/18/1998
• Est. Priority Date: 03/19/1996
• Status: Expired due to Term

• Current Assignee: Motorola Solutions, Inc.
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Errico, James H., Mazurkiewicz, Theodore
• Primary Examiner(s): Hafiz, Tariq R.
• Application Number:
  US08/618,223
• Time in Patent Office: 882 Days
• Field of Search: 382/155, 382/161, 395/20-25, 395/27
• US Class Current: 706/25
• CPC Class Codes: G06F 18/2321 using statistics or function optimisation, e.g. modelling of probability density functions
• CPC Class Codes: G06F 18/2453 non-linear, e.g. polynomial classifier

Abstract

A computer-based method and system selects a plurality of training vectors for a pattern recognition system by creating a plurality of clusters and then uniformly sampling the clusters. Each of the clusters is associated with a particular class and includes a plurality of example signals. The example signals are assigned to the clusters as a function of cluster-example distances. If a cluster includes one or more overlapping example signals, the number of clusters associated with the overlapping cluster is increased and the example signals are re-assigned to the clusters.

Claims

1. In a computer, a method of selecting a plurality of training vectors for a pattern recognition system, the method comprising the following steps:

receiving a plurality of example signals representing a plurality of classes within an example space, each of the plurality of example signals being associated with a respective class;

defining a plurality of clusters, each of the plurality of clusters being associated with one of the plurality of classes;

assigning the plurality of example signals to the plurality of clusters as a function of a plurality of cluster-example distances;

determining whether at least one decision boundary needs greater definition, if so, increasing in number the plurality of clusters and repeating the step of assigning;

selecting the plurality of training vectors by sampling of the plurality of example signals from each of the plurality of clusters; and

fitting a polynomial expansion to the plurality of training vectors using a least squares estimate, wherein the polynomial expansion has a form ##EQU3## wherein x represents at least one element of a training vector, i, j, and n are integers, y represents a discriminant signal, a₀ represents a zero-order coefficient, b_i represents a first-order coefficient, and c_ij represents a second-order coefficient.

2. The method of claim 1, wherein the step of selecting includes:

performing a uniform sampling of the plurality of example signals from each of the plurality of clusters.

3. The method of claim 1, wherein the step of determining includes:

determining whether the at least one decision boundary needs greater definition based on a ratio of intra-cluster and inter-cluster distances.

4. The method of claim 1, wherein the step of determining includes:

determining whether the at least one decision boundary needs greater definition based on at least one cluster size.

5. The method of claim 1, wherein the step of determining includes:

determining whether at least one of the clusters includes a quantity of overlapping example signals that exceeds an overlap threshold, if so, increasing in number the plurality of clusters and repeating the step of assigning.

6. The method of claim 5, wherein the steps of assigning and determining are repeated until the quantity of overlapping example signals does not exceed the overlap threshold.

7. The method of claim 1, wherein the step of defining includes the following sub-step:

clustering the plurality of example signals within each of the plurality of classes using a K-means clustering algorithm.

8. The method of claim 7, wherein the step of defining includes the following sub-step:

clustering the plurality of example signals within each of the plurality of classes using a binary-split algorithm.

9. The method of claim 1, wherein the step of defining includes the following sub-step:

limiting each of the plurality of clusters to having an intra-cluster distance which is less than a distance threshold.

10. The method of claim 1, wherein the step of assigning includes the following sub-step:

assigning each of the plurality of example signals to a closest one of the plurality of clusters by performing a nearest-neighbor search between the plurality of clusters and the plurality of example signals.

11. In a computer, a method of selecting a plurality of training vectors for a pattern recognition system, the method comprising the following steps:

receiving a plurality of example signals representing a plurality of classes within an example space, each of the plurality of example signals being associated with a respective class;

generating a plurality of cluster centroids by applying a K-means clustering algorithm to the example signals, each of the cluster centroids corresponding to one of the classes;

assigning each of the plurality of example signals to a closest one of the plurality of cluster centroids by performing a nearest-neighbor search between the plurality of cluster centroids and the plurality of example signals, whereby producing a plurality of clusters;

determining whether at least one of the clusters includes a quantity of overlapping example signals that exceeds an overlap threshold, if so, increasing in number the plurality of cluster centroids and repeating the step of assigning;

selecting the plurality of training vectors by a uniform sampling of the plurality of example signals from each of the plurality of clusters; and

fitting a polynomial expansion to the plurality of training vectors using a least squares estimate wherein the polynomial expansion has a form ##EQU4## wherein x represents at least one element of a training vector, i, j, and n are integers, y represents a discriminant signal, a₀ represents a zero-order coefficient, b_i represents a first-order coefficient, and c_ij represents a second-order coefficient.

12. The method of claim 11, wherein the steps of assigning and determining are repeated until the quantity of overlapping example signals does not exceed the overlap threshold.

13. The method of claim 11, wherein the step of generating includes the following sub-step:

applying a binary-split algorithm to the plurality of example signals.

14. The method of claim 11, wherein the step of determining includes the following sub-step:

defining at least one additional cluster centroid based on a plurality of overlapping example signals.

15. The method of claim 11, wherein the step of determining includes the following sub-step:

using a K-means algorithm to increase in number the plurality of cluster centroids.

16. A computer system for selecting a plurality of training vectors for a pattern recognition system, which comprises:

an input interface for receiving a plurality of example signals representing a plurality of classes within an example space, each of the plurality of example signals being associated with a respective class;

a cluster processor, operatively associated with the input interface, for defining a plurality of clusters, each of the plurality of clusters being associated with one of the plurality of classes;

a sorter, operatively associated with the cluster processor, for assigning the plurality of example signals to the plurality of clusters as a function of a plurality of cluster-example distances;

a comparator, operatively associated with the sorter, for determining whether at least one of the clusters includes a quantity of overlapping example signals that exceeds an overlap threshold, if so, the comparator increasing in number the plurality of clusters associated with the overlapping example signals;

a selector, operatively associated with the comparator, for selecting the plurality of training vectors by a uniform sampling of the plurality of example signals from each of the plurality of clusters;

wherein the sorter re-assigns the plurality of example signals to the plurality of clusters in response to the comparator increasing in number the plurality of clusters; and

regression means for fitting a polynomial expansion to the plurality of training vectors using a least squares estimate, wherein the polynomial expansion has a form ##EQU5## wherein x represents at least one element of a training vector, i, j, and n are integers, y represents a discriminant signal, a₀ represents a zero-order coefficient, b_i represents a first-order coefficient, and c_ij represents a second-order coefficient.

17. The computer system of claim 16, wherein the sorter and the selector cooperatively function until the quantity of overlapping example signals is less than the overlap threshold.

18. The computer system of claim 16, wherein the cluster processor uses a K-means clustering algorithm to cluster the plurality of example signals within each of the plurality of classes.

19. The computer system of claim 18, wherein the cluster processor uses a binary-split algorithm to cluster the plurality of example signals within each of the plurality of classes.

20. The computer system of claim 16, wherein the cluster processor limits each of the plurality of clusters to having an intra-cluster distance which is less than a distance threshold.

21. The computer system of claim 16, wherein the sorter assigns each of the plurality of example signals to a closest one of the plurality of clusters by performing a nearest-neighbor search between the plurality of clusters and the plurality of example signals.

22. An article of manufacture, which comprises:

a computer-readable memory usable for causing a computer to select a plurality of training vectors for a pattern recognition system, the computer-readable memory having a structure defined by storing a computer program in the computer-readable memory;

wherein the computer program includes a method for selecting the plurality of training vectors, the method comprising the following steps;

receiving a plurality of example signals representing a plurality of classes within an example space, each of the plurality of example signals being associated with a respective class;

defining a plurality of clusters, each of the plurality of clusters being associated with one of the plurality of classes;

assigning the plurality of example signals to the plurality of clusters as a function of a plurality of cluster-example distances;

determining whether at least one of the clusters includes a quantity of overlapping example signals that exceeds an overlap threshold, if so, increasing in number the plurality of clusters and repeating the step of assigning;

selecting the plurality of training vectors by a uniform sampling of the plurality of example signals from each of the plurality of clusters; and

fitting a polynomial expansion to the plurality of training vectors using a least squares estimate.

23. The article of manufacture of claim 22, wherein the method steps of assigning and determining are repeated until the quantity of overlapping example signals does not exceed the overlap threshold.

24. The article of manufacture of claim 22, wherein the method step of defining includes the following sub-step:

clustering the plurality of example signals within each of the plurality of classes using a K-means clustering algorithm.

25. The article of manufacture of claim 24, wherein the method step of defining includes the following sub-step:

clustering the plurality of example signals within each of the plurality of classes using a binary-split algorithm.

26. The article of manufacture of claim 22, wherein the method step of defining includes the following sub-step:

limiting each of the plurality of clusters to having an intra-cluster distance which is less than a distance threshold.

27. The article of manufacture of claim 22, wherein the method step of assigning includes the following sub-step:

assigning each of the plurality of example signals to a closest one of the plurality of clusters by performing a nearest-neighbor search between the plurality of clusters and the plurality of example signals.

28. The article of manufacture of claim 22, wherein the polynomial expansion has a form ##EQU6## wherein x represents at least one element of a training vector, i, j, and n are integers, y represents a discriminant signal, a₀ represents a zero-order coefficient, b_i represents a first-order coefficient, and c_ij represents a second-order coefficient.

29. A computer system for selecting a plurality of training vectors for a pattern recognition system, which comprises:

an input interface for receiving a plurality of example signals representing a plurality of classes within an example space, each of the plurality of example signals being associated with a respective class;

a cluster processor, operatively associated with the input interface, for defining a plurality of clusters, each of the plurality of clusters being associated with one of the plurality of classes;

a sorter, operatively associated with the cluster processor, for assigning the plurality of example signals to the plurality of clusters as a function of a plurality of cluster-example distances;

a comparator, operatively associated with the sorter, for determining whether at least one of the clusters includes a quantity of overlapping example signals that exceeds an overlap threshold;

a selector, operatively associated with the comparator, for selecting the plurality of training vectors by a uniform sampling of the plurality of example signals from each of the plurality of clusters;

wherein the sorter re-assigns the plurality of example signals to the plurality of clusters in response to the comparator increasing in number the plurality of clusters; and

a regression fitting module for fitting a polynomial expansion to the plurality of training vectors, wherein the polynomial expansion is a function of at least one element of a training vector and a plurality of coefficients, at least one of the plurality of coefficients comprising a second-order coefficient.

30. The computer system of claim 29, wherein the polynomial expansion has a form ##EQU7## wherein x represents at least one element of a training vector, i, j, and n are integers, y represents a discriminant signal, a₀ represents a zero-order coefficient, b_i represents a first-order coefficient, and c_ij represents a second-order coefficient.

31. The computer system of claim 29, wherein the comparator increases in number the plurality of clusters associated with the overlapping example signals.

32. The computer system of claim 31, wherein the sorter re-assigns the plurality of example signals to the plurality of clusters in response to the comparator increasing in number the plurality of clusters.