Mahalanobis distance genetic algorithm (MDGA) method and system

• US 20060230018A1
• Filed: 04/08/2005
• Published: 10/12/2006
• Est. Priority Date: 04/08/2005
• Status: Abandoned Application

• Current Assignee: Caterpillar Incorporated
• Original Assignee: Caterpillar Incorporated
• Inventors: Grichnik, Anthony J., Seskin, Michael
• Application Number:
  US11/101,556
• Publication Number:
  US 20060230018A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 2111/06 Multi-objective optimisation, e.g. Pareto optimisation using simulated annealing [SA], ant colony algorithms or genetic algorithms [GA]
• CPC Class Codes: G06F 30/20 Design optimisation, verification or simulation optimisation, verification or simulation of circuit designs G06F30/30

Abstract

A computer-implemented method to provide a desired variable subset. The method may include obtaining a set of data records corresponding a plurality of variables and defining the data records as normal data or abnormal data based on predetermined criteria. The method may also include initializing a genetic algorithm with a subset of variables from the plurality of variables and calculating Mahalanobis distances of the normal data and the abnormal data based on the subset of variables. Further, the method may include identifying a desired subset of the plurality of variables by performing the genetic algorithm based on the Mahalanobis distances.

Claims

1. A computer-implemented method for identifying a desired variable subset, comprising:

obtaining a set of data records corresponding to a plurality of variables;

defining the data records as normal data or abnormal data based on predetermined criteria;

initializing a genetic algorithm with a subset of variables from the plurality of variables;

calculating Mahalanobis distances of the normal data and the abnormal data based on the subset of variables; and

identifying a desired subset of the plurality of variables by performing the genetic algorithm based on the Mahalanobis distances.

2. The computer-implemented method according to claim 1, wherein a total number of the data records is less than a total number of the plurality of variables.

3. The computer-implemented method according to claim 1, further including:

outputting the desired subset to one or more application software programs.

4. The computer-implemented method according to claim 1, wherein defining includes:

defining the data records as normal data or abnormal data based on empirical data.

5. The computer-implemented method according to claim 1, wherein defining includes:

defining the data records as normal data or abnormal data based on one or more results from a clustering algorithm performed on the data records.

6. The computer-implemented method according to claim 1, wherein initializing includes:

randomly determining a subset of variables from the plurality of variables; and

providing a genetic algorithm with the determined subset of variables as an initial input vector.

7. The computer-implemented method according to claim 1, wherein initializing includes:

determining the subset of variables from the plurality of variables based on a correlation between the subset of variables; and

providing the genetic algorithm with the determined subset of variables as an initial input vector.

8. The computer-implemented method according to claim 1, wherein calculating Mahalanobis distances includes:

calculating a first Mahalanobis distance of the normal data based on the subset of variables;

calculating a second Mahalanobis distance of the abnormal data based on the subset of variables; and

determining a Mahalanobis distance deviation between the first Mahalanobis distance and the second Mahalanobis distance.

9. The computer-implemented method according to claim 8,

wherein identifying includes:

setting a goal function of the genetic algorithm to maximize the Mahalanobis distance deviation;

starting the genetic algorithm;

determining whether the genetic algorithm converges; and

identifying the subset of variables as a desired subset variable of the plurality of variables if the genetic algorithm converges.

10. The computer-implemented method according to claim 9,

wherein identifying further includes:

choosing a different subset of variables, based on the subset of variables and according to the genetic algorithm, if the genetic algorithm does not converge;

calculating a different Mahalanobis distance deviation based on the different subset of variables; and

performing the genetic algorithm to identify the desired subset of variables based on the different subset of variables.

11. A computer-implemented method for defining normal data and abnormal data from a data set, comprising:

obtaining two or more clusters by applying a clustering algorithm to the data set;

determining a first cluster and a second cluster that have a largest difference in normalized means; and

defining the first cluster as normal data and the second cluster as abnormal data.

12. The computer-implemented method according to claim 11, further including:

determining a first difference of normalized means between a third cluster and the first cluster;

determining a second difference of normalized means between the third cluster and the second cluster; and

defining the third cluster as normal data if the first difference is smaller than the second difference.

13. The computer-implemented method according to claim 12, further including:

defining the third cluster as abnormal data if the first difference is greater than the second difference.

14. The computer-implemented method according to claim 11, further including:

determining a first difference of normalized means between an individual member of a third cluster and the first cluster;

determining a second difference of normalized means between the individual member of the third cluster and the second cluster; and

defining the individual member as normal data or abnormal data based on the first and the second differences.

15. The computer-implemented method according to claim 11, further including:

providing the normal data and abnormal data to a Mahalanobis distance genetic algorithm (MDGA).

16. A computer system, comprising:

a console;

at least one input device; and

a central processing unit (CPU) configured to;

obtain a set of data records corresponding to a plurality of variables, wherein a total number of the data records is less than a total number of the plurality of variables;

define the data records as normal data or abnormal data based on predetermined criteria;

initialize a genetic algorithm with a subset of variables from the plurality of variables;

calculate Mahalanobis distances of the normal data and the abnormal data based on the subset of variables; and

identify a desired subset of the plurality of variables by performing the genetic algorithm based on the Mahalanobis distances.

17. The computer system according to claim 16, wherein, to define the data records, the CPU is configured to:

define the data records as normal data or abnormal data based on one or more results from a clustering algorithm performed on the data records.

18. The computer system according to claim 16, wherein, to calculate Mahalanobis distances, the CPU is configured to:

calculate a first Mahalanobis distance of the normal data based on the subset of variables;

calculate a second Mahalanobis distance of the abnormal data based on the subset of variables; and

determine a Mahalanobis distance deviation between the first Mahalanobis distance and the second Mahalanobis distance.

19. The computer system according to claim 18, wherein, to identify the desired subset, the CPU is configured to:

set a goal function of the genetic algorithm to maximize the Mahalanobis distance deviation;

start the genetic algorithm;

determine whether the genetic algorithm converges; and

identify the subset of variables as a desired subset variable of the plurality of variables if the genetic algorithm converges.

20. The computer system according to claim 19, wherein the CPU is further configured to:

choose a different subset of variables, based on the subset of variables and according to the genetic algorithm, if the genetic algorithm does not converge;

calculate a different Mahalanobis distance deviation based on the different subset of variables; and

perform the genetic algorithm to identify the desired subset of variables based on the different subset of variables.

21. The computer system according to claim 16, further including:

one or more databases; and

one or more network interfaces.

22. A computer-readable medium for use on a computer system configured to perform a variable reducing procedure, the computer-readable medium having computer-executable instructions for performing a method comprising:

obtaining a set of data records corresponding to a plurality of variables, wherein a total number of the data records is less than a total number of the plurality of variables;

defining the data records as normal data or abnormal data based on predetermined criteria;

initializing a genetic algorithm with a subset of variables from the plurality of variables;

calculating Mahalanobis distances of the normal data and the abnormal data based on the subset of variables; and

identifying a desired subset of the plurality of variables by performing the genetic algorithm based on the Mahalanobis distances.

23. The computer-readable medium according to claim 22, wherein the method further includes:

outputting the desired subset to one or more application software programs.

24. The computer-readable medium according to claim 22, wherein defining includes:

defining the data records as normal data or abnormal data based on one or more results from a clustering algorithm performed on the data records.

25. The computer-readable medium according to claim 22, wherein initializing includes:

randomly determining a subset of variables from the plurality of variables; and

providing a genetic algorithm with the determined subset of variables as an initial input vector.

26. The computer-readable medium according to claim 22, wherein initializing includes:

determining the subset of variables from the plurality of variables based on a correlation between the subset of variables; and

providing the genetic algorithm with the determined subset of variables as an initial input vector.

27. The computer-readable medium according to claim 22, wherein calculating Mahalanobis distances includes:

calculating a first Mahalanobis distance of the normal data based on the subset of variables;

calculating a second Mahalanobis distance of the abnormal data based on the subset of variables; and

determining a Mahalanobis distance deviation between the first Mahalanobis distance and the second Mahalanobis distance.

28. The computer-readable medium according to claim 22, wherein identifying includes:

setting a goal function of the genetic algorithm to maximize the Mahalanobis distance deviation;

starting the genetic algorithm;

determining whether the genetic algorithm converges; and

identifying the subset of variables as a desired subset variable of the plurality of variables if the genetic algorithm converges.

29. The computer-readable medium according to claim 28, wherein identifying further includes:

choosing a different subset of variables, based on the subset of variables and according to the genetic algorithm, if the genetic algorithm does not converge;

calculating a different Mahalanobis distance deviation based on the different subset of variables; and

performing the genetic algorithm to identify the desired subset of variables based on the different subset of variables.