Reducing the size of a training set for classification

• US 20070260566A1
• Filed: 04/11/2006
• Published: 11/08/2007
• Est. Priority Date: 04/11/2006
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Urmanov, Aleksey, Bougaev, Anton, Gross, Kenny
• Granted Patent: US 7,478,075 B2
• Time in Patent Office: Days
• US Class Current: 706/25
• CPC Class Codes: G06F 18/214 Generating training patterns; Bootstrap methods, e.g. bagging or boosting
• CPC Class Codes: G06F 18/2453 non-linear, e.g. polynomial classifier

Abstract

A system that reduces the size of a design data set. During this design data set reduction operation, the system computes a decision boundary which separates a first group of data patterns in a training data set from a second group of data patterns in the training data set. For each data pattern in the training data set, the system determines if removing the data pattern from the training data set substantially affects the resulting decision boundary. If so, the system marks the data pattern as a key pattern. The system then removes all data patterns that are not marked as key patterns to produce a reduced training data set which represents the decision boundary.

Claims

1. A method for reducing the size of a design data set, comprising:

computing a decision boundary which separates a first group of data patterns in a training data set from a second group of data patterns in the training data set;

for each data pattern in the training data set,

determining if removing the data pattern from the training data set substantially affects the resulting decision boundary; and

if so, marking the data pattern as a key pattern; and

removing all data patterns that are not marked as key patterns to produce a reduced training data set which represents the decision boundary.

2. The method of claim 1, wherein determining if removing the data pattern substantially affects the decision boundary involves:

computing a first Euclidian distance from the data pattern to the decision boundary;

removing the data pattern from the training data set;

computing a new decision boundary from the data set without the data pattern;

computing a second Euclidian distance from the data pattern to the new decision boundary; and

if the absolute value of the difference between the second Euclidian distance and the first Euclidian distance is greater than a pre-specified tolerance, marking the data pattern as a key pattern.

3. The method of claim 2, wherein the pre-specified tolerance is zero, so that if the second Euclidian distance is not equal to the first Euclidian distance, the data pattern is marked as a key pattern.

4. The method of claim 2, wherein computing the new decision boundary involves:

for each data pattern in the first group of data patterns,

selecting a data pattern from the first group of data patterns;

for each data pattern in the second group of data patterns, generating a separating boundary that separates the data pattern in the first group of data patterns from the data pattern in the second group of data patterns; and

generating a separating bundle which separates the data pattern in the first group of data patterns from all data patterns in the second group of data patterns; and

generating the new decision boundary which separates all data patterns in the first group of data patterns from all data patterns in the second group of data patterns using the separating bundles.

5. The method of claim 1, further comprising using the reduced data set to classify a previously unseen pattern by:

determining the region of the input space in which the previously unseen pattern is located;

if the previously unseen pattern is located within the region which corresponds to the first group of data patterns, classifying the previously unseen data pattern as belonging to the first group of data patterns; and

otherwise, classifying the previously unseen data pattern as belonging to the second group of data patterns.

6. The method of claim 1, further comprising using R-functions to compute a decision boundary which is used to classify data patterns, wherein an R-function is a function whose sign is determined by the signs of its arguments.

7. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for reducing the size of a design data set, the method comprising:

computing a decision boundary which separates a first group of data patterns in a training data set from a second group of data patterns in the training data set;

for each data pattern in the training data set,

determining if removing the data pattern from the training data set substantially affects the resulting decision boundary; and

if so, marking the data pattern as a key pattern; and

removing all data patterns that are not marked as key patterns to produce a reduced training data set which represents the decision boundary.

8. The computer-readable storage medium of claim 7, wherein determining if removing the data pattern substantially affects the decision boundary involves:

computing a first Euclidian distance from the data pattern to the decision boundary;

removing the data pattern from the training data set;

computing a new decision boundary from the data set without the data pattern;

computing a second Euclidian distance from the data pattern to the new decision boundary; and

if the absolute value of the difference between the second Euclidian distance and the first Euclidian distance is greater than a pre-specified tolerance, marking the data pattern as a key pattern.

9. The computer-readable storage medium of claim 8, wherein the pre-specified tolerance is zero, so that if the second Euclidian distance is not equal to the first Euclidian distance, the data pattern is marked as a key pattern.

10. The computer-readable storage medium of claim 8, wherein computing the new decision boundary involves:

for each data pattern in the first group of data patterns,

selecting a data pattern from the first group of data patterns;

for each data pattern in the second group of data patterns, generating a separating boundary that separates the data pattern in the first group of data patterns from the data pattern in the second group of data patterns; and

generating a separating bundle which separates the data pattern in the first group of data patterns from all data patterns in the second group of data patterns; and

generating the new decision boundary which separates all data patterns in the first group of data patterns from all data patterns in the second group of data patterns using the separating bundles.

11. The computer-readable storage medium of claim 7, the method further comprising using the reduced data set to classify a previously unseen pattern by:

determining the region of the input space in which the previously unseen pattern is located;

if the previously unseen pattern is located within the region which corresponds to the first group of data patterns, classifying the previously unseen data pattern as belonging to the first group of data patterns; and

otherwise, classifying the previously unseen data pattern as belonging to the second group of data patterns.

12. The computer-readable storage medium of claim 7, the method further comprising using R-functions to compute a decision boundary which is used to classify data patterns, wherein an R-function is a function whose sign is determined by the signs of its arguments.

13. An apparatus that reduces the size of a design data set, comprising:

a computing mechanism configured to compute a decision boundary which separates a first group of data patterns in a training data set from a second group of data patterns in the training data set;

a pattern-reduction mechanism configured to;

for each data pattern in the training data set, to

determine if removing the data pattern from the training data set substantially affects the resulting decision boundary; and

if so, to mark the data pattern as a key pattern; and

to

remove all data patterns that are not marked as key patterns to produce a reduced training data set which represents the decision boundary.

14. The apparatus of claim 13, wherein while determining if removing the data pattern substantially affects the decision boundary, the pattern-reduction mechanism is configured to:

compute a first Euclidian distance from the data pattern to the decision boundary;

remove the data pattern from the training data set;

compute a new decision boundary from the data set without the data pattern;

compute a second Euclidian distance from the data pattern to the new decision boundary; and

if the absolute value of the difference between the second Euclidian distance and the first Euclidian distance is greater than a pre-specified tolerance, to mark the data pattern as a key pattern.

15. The apparatus of claim 14, wherein the pre-specified tolerance is zero, so that if the second Euclidian distance is not equal to the first Euclidian distance, the data pattern is marked as a key pattern.

16. The apparatus of claim 14, wherein while computing the new decision boundary, the pattern-reduction mechanism is configured to:

for each data pattern in the first group of data patterns, to

select a data pattern from the first group of data patterns;

for each data pattern in the second group of data patterns, to generate a separating boundary that separates the data pattern in the first group of data patterns from the data pattern in the second group of data patterns; and

to

generate a separating bundle which separates the data pattern in the first group of data patterns from all data patterns in the second group of data patterns; and

to

generate the new decision boundary which separates all data patterns in the first group of data patterns from all data patterns in the second group of data patterns using the separating bundles.

17. The apparatus of claim 13, further comprising a pattern-classifying mechanism configured to use the reduced data set to classify a previously unseen pattern.

18. The apparatus of claim 17, wherein while using the reduced data set to classify a previously unseen pattern, the pattern-classification mechanism is configured to:

determine the region of the input space in which the previously unseen pattern is located;

if the previously unseen pattern is located within the region which corresponds to the first group of data patterns, classify the previously unseen data pattern as belonging to the first group of data patterns; and

otherwise, to classify the previously unseen data pattern as belonging to the second group of data patterns.

19. The apparatus of claim 13, wherein the computing mechanism is configured to use R-functions to compute a decision boundary which is used to classify data patterns, wherein an R-function is a function whose sign is determined by the signs of its arguments.