Prediction apparatus for predicting based on similar cases and method thereof

• US 6,418,425 B1
• Filed: 10/19/1999
• Issued: 07/09/2002
• Est. Priority Date: 11/24/1998
• Status: Expired due to Term

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Maeda, Kazuho, Yaginuma, Yoshinori
• Primary Examiner(s): Black, Thomas
• Assistant Examiner(s): Holmes, Michael B.
• Application Number:
  US09/420,780
• Time in Patent Office: 994 Days
• Field of Search: 706/47, 706/25, 706/16, 706/14, 706/45, 707/2
• US Class Current: 706/47
• CPC Class Codes: G06N 5/00 Computing arrangements using knowledge-based models

Abstract

An optimum similar case extracting condition is automatically determined using a known case aggregate, and the unknown field of an unknown case aggregate is predicted from the known case aggregate using the condition. At this point, the degree of similarity depending on the distribution of the values of the unknown field in the known case aggregate is calculated and a similar case aggregate is extracted based on the degree of similarity. When it is confirmed that the degree of similarity does not satisfy a predetermined condition, the similarity calculation is stopped.

Claims

1. A prediction apparatus for making a prediction based on similar cases, comprising:

determining means for automatically determining a similar case extracting condition to extract one or more pieces of similar case data similar to unknown case data from an aggregate of known case data consisting of one or more fields; and

predicting means for extracting the one or more pieces of similar case data using the similar case extracting condition determined by the determining means, predicting a value of an unknown field of the unknown case data, and outputting a prediction value.

2. The prediction apparatus according to claim 1, wherein said determining means evaluates a plurality of similar case extracting conditions and selects an appropriate similar extracting condition based on an evaluation result.

3. The prediction apparatus according to claim 1, wherein said determining means includes:

condition outputting means for outputting both class information for designating a class of the similar case extracting condition and range information for designating a range of the designated similar case extracting condition;

maximum condition calculating means for obtaining a maximum condition including an output of the condition outputting means;

input case generating means for generating both an aggregate of case data for inputting known cases and an aggregate of case data for inputting unknown cases from the aggregate of the known case data;

similar case extracting means for extracting an aggregate of similar case data similar to the case data for inputting unknown cases from the aggregate of the case data for inputting known cases according to the maximum condition; and

condition determining means for selecting an appropriate similar case extracting condition from the range of the similar case extracting condition using the aggregate of the similar case data, and outputting information about the appropriate similar case extracting condition.

4. The prediction apparatus according to claim 3, wherein said condition outputting means outputs a number of similar cases as the class information and outputs a range of the number of similar cases as the range information.

5. The prediction apparatus according to claim 3, wherein said condition outputting means outputs a threshold value of a degree of similarity as the class information and outputs a range of the threshold value as the range information.

6. The prediction apparatus according to claim 3, wherein said condition outputting means outputs a conditional expression including both the number of similar cases and a degree of similarity as the class information and outputs an inspection range of the conditional expression as the range information.

7. The prediction apparatus according to claim 3, wherein said input case generating means divides the aggregate of the known case data into two groups, outputs one group as the aggregate of the case data for inputting known cases and outputs the other group as the aggregate of the case data for inputting unknown cases.

8. The prediction apparatus according to claim 3, wherein said input case generating means outputs the aggregate of the known case data as the aggregate of the case data for inputting unknown cases and outputs an aggregate obtained by deleting one piece of the case data for inputting unknown cases from the aggregate of the known case data, as an aggregate of case data for inputting known cases for the one piece of the case data for inputting unknown cases.

9. The prediction apparatus according to claim 3, wherein said input case generating means outputs an aggregate obtained by sampling one or more pieces of case data from the aggregate of the known case data as the aggregate of the case data for inputting unknown cases and outputs an aggregate obtained by deleting one piece of the case data for inputting unknown cases from the aggregate of the known case data as an aggregate of case data for inputting known cases for the one piece of the case data for inputting unknown data.

10. The prediction apparatus according to claim 3, wherein said determining means further includes:

maximum condition modifying means, when the aggregate of the case data for inputting known cases includes case data overlapping with the case data for inputting unknown cases, for modifying the maximum condition and outputting the maximum condition to said similar case extracting means; and

similar case deleting means, when the maximum condition is modified, for deleting case data from the aggregate of the similar case data outputted by said similar case extracting means, and outputting a modified aggregate of similar case data to said condition determining means.

11. The prediction apparatus according to claim 10, wherein said input case generating means outputs the aggregate of the known case data as both the aggregate of the case data for inputting unknown cases and the aggregate of the case data for inputting known cases, said maximum condition modifying means modifies the maximum condition so as to increase the number of similar cases by one, and said similar case deleting means deletes case data overlapping with one piece of case data for inputting unknown cases from an aggregate of similar case data for the one piece of the case data for inputting unknown cases.

12. The prediction apparatus according to claim 10, wherein said input case generating means outputs an aggregate obtained by sampling one or more pieces of case data from the aggregate of the known case data as the aggregate of the case data for inputting unknown cases and outputs the aggregate of the known case data as the aggregate of the case data for inputting known cases, said maximum condition modifying means modifying the maximum condition so as to increase the number of similar cases by one and said similar case deleting means deletes case data overlapping with one piece of case data for inputting unknown cases from an aggregate of similar case data for the one piece of the case data for inputting unknown cases.

13. The prediction apparatus according to claim 3, wherein said similar case extracting means extracts the aggregate of the similar case data similar to the case data for inputting unknown cases using one of memory-based reasoning and case-based reasoning.

14. The prediction apparatus according to claim 3, wherein said condition determining means includes:

condition discretizing means for discretizing and outputting conditions included in the range of the similar case extracting condition;

conditioned similar case extracting means for extracting an aggregate of similar case data for each condition, which satisfying each of discretized conditions, from the aggregate of the similar case data similar to the case data for inputting unknown cases;

prediction result generating means for predicting a value of a field to be predicted in the case data for inputting unknown cases for each condition using the aggregate of the similar case data for each condition, and outputting a prediction value for each condition;

condition evaluating means for obtaining an evaluation value for each condition from the prediction value for each condition; and

condition selecting means for selecting the appropriate similar case extracting condition from the discretized conditions based on the evaluation value for each condition.

15. The prediction apparatus according to claim 14, wherein said prediction result generating means generates the prediction result using one of memory-based reasoning and case-based reasoning.

16. The prediction apparatus according to claim 14, wherein when the prediction value is a category value, said condition evaluating means compares the prediction value with a true value of the field to be predicted, and generates the evaluation value based on whether the prediction value matches the true value.

17. The prediction apparatus according to claim 14, wherein when the prediction value is a continuous value, said condition evaluating means compares the prediction value with a true value of the field to be predicted, and generates the prediction value using difference between the prediction value and the true value.

18. The prediction apparatus according to claim 14, wherein said condition evaluating means generates the prediction value taking into consideration a degree of probability accompanying the prediction value.

19. The prediction apparatus according to claim 14, wherein said condition evaluating means obtains a weight from both the prediction value and a true value of the field to be predicted, and generates the evaluation value taking the weight into consideration.

20. The prediction apparatus according to claim 14, wherein said condition evaluating means estimates an execution time of a similar case extraction using at least one of one discretized condition and an aggregate of similar case data satisfying the one discretized condition, and generates the evaluation value taking the estimated execution time into consideration.

21. The prediction apparatus according to claim 14, wherein said condition selecting means selects a condition corresponding to a best value of given evaluation values as the appropriate similar case extracting condition.

22. The prediction apparatus according to claim 14, wherein said condition selecting means calculates a moving average of given evaluation values, and selects a condition corresponding to a best value of obtained average evaluation values as the appropriate similar case extracting condition.

23. The prediction apparatus according to claim 14, wherein said condition selecting means approximates given evaluation values using a function of a condition, and selects a condition corresponding to a best value of obtained approximate evaluation values as the appropriate similar case extracting condition.

24. A prediction apparatus for making a prediction based on similar cases, comprising:

similar case extracting means for extracting one or more pieces of similar case data similar to unknown case data from an aggregate of known case data consisting of one or more fields, based on a degree of similarity;

prediction result generating means for predicting a value of an unknown field of the unknown case data using the one or more pieces of similar case data, and outputting a prediction value; and

similarity calculating means for calculating both a distribution of values of the unknown field in the known case data and a weight depending on the value of the unknown field of the unknown case data for each field, and calculating the degree of similarity using the weight for each field.

25. The prediction apparatus according to claim 24, wherein said similarity calculating means divides the aggregate of the known case data according to a value of each field into partial aggregates for each field, and calculates a weight which the smaller it becomes, the closer to a distribution of values of the unknown field as a whole approaches a distribution of values of the unknown field in a partial aggregate to which the unknown case data belong, and which the larger it becomes, the farther from the distribution of the values of the unknown field as a whole moves the distribution of the values of the unknown field of the partial aggregate to which the unknown case data belong.

26. A prediction apparatus for making a prediction based on similar cases, comprising:

similarity calculating means for calculating a similarity condition for adding known case data to a temporary aggregate of previously obtained similar case data using both a similar case extracting condition and the temporary aggregate of the similar case data;

conditioned similarity calculating means for calculating a degree of similarity between the known case data and unknown case data, when the degree of similarity satisfies the similarity condition, for outputting the known case data as similar case data, and when it is confirmed that the degree of similarity does not satisfy the similarity condition, stopping calculation; and

generating means for generating a new aggregate of similar case data using the similar case data outputted by said conditioned similarity calculating means.

27. The prediction apparatus according to claim 26, wherein said generating means includes:

similar case aggregate updating means for adding the similar case data outputted from said conditioned similar calculating means to the temporary aggregate of the similar case data, deleting extra case data so as to match the similar case extracting condition, and generating a new aggregate of similar case data; and

similar case aggregate storing means for storing the new aggregate of the similar case data as a temporary aggregate of similar case data,

and when processes of all the given known case data are terminated, said generating means outputs an aggregate of similar case data stored in said similar case aggregate storing means.

28. A computer-readable storage medium on which is recorded a program for enabling a computer to make a prediction based on similar cases, said program comprising the steps of:

automatically determining a similar case extracting condition for extracting one or more pieces of similar case data similar to unknown case data from an aggregate of known case data consisting of one or more fields;

extracting the one or more pieces of similar case data using the determined similar case extracting condition; and

predicting a value of an unknown field of the unknown case data using the one or more pieces of similar case data, and generating a prediction value.

29. A computer-readable storage medium on which is recorded a program for enabling a computer to make a prediction based on similar cases, said program comprising the steps of:

calculating a distribution of values of a field corresponding to an unknown field of unknown case data in an aggregate of known case data consisting of one or more fields;

calculating a weight depending on the distribution for each field;

calculating a degree of similarity using the weight for each field;

extracting one or more pieces of similar case data similar to the unknown case data from the aggregate of the known case data, based on the degree of similarity; and

predicting a value of the unknown field of the unknown case data using the one or more pieces of similar case data, and generating a prediction value.

30. A computer-readable storage medium on which is recorded a program for enabling a computer to make a predictions based on similar cases, said program comprising the steps of:

calculating a similarity condition for adding known case data to a temporary aggregate of previously obtained similar case data using both a similar case extracting condition and the temporary aggregate of the similar case data;

calculating a degree of similarity between the known case data and unknown case data;

determining the known case data as similar case data when the degree of similarity satisfies the similarity condition;

stopping calculation when it is confirmed that the degree of similarity does not satisfy the similarity condition; and

generating a new aggregate of similar case data using the determined similar case data.

31. A prediction method based on similar cases using a computer, comprising the steps of:

automatically determining a similar case extracting condition for extracting one or more pieces of similar case data similar to unknown case data from an aggregate of known case data consisting of one or more fields;

extracting the one or more pieces of similar case data using the determined similar case extracting condition; and

predicting a value of an unknown field of the unknown case data using the one or more pieces of similar case data.

32. A prediction method based on similar cases using a computer, comprising the steps of:

calculating a distribution of values of a field corresponding to an unknown field of unknown case data in an aggregate of known case data consisting of one or more fields;

calculating a weight depending on the distribution for each field;

calculating a degree of similarity using the weight for each field;

extracting one or more pieces of similar case data similar to the unknown case data from the aggregate of the known case data, based on the degree of similarity; and

predicting a value of the unknown field of the unknown case data.

33. A prediction method based on similar cases using a computer, comprising the steps of:

calculating a similarity condition for adding known case data to a temporary aggregate of previously obtained similar case data using both a similar case extracting condition and the temporary aggregate of the similar case data;

calculating a degree of similarity between the known case data and unknown case data;

determining the known case data as similar case data when the degree of similarity satisfies the similarity condition;

stopping calculation when it is confirmed that the degree of similarity does not satisfy the similarity condition;

generating a new aggregate of similar case data using the determined similar case data; and

predicting a value of an unknown field of the unknown case data using the generated aggregate of the similar case data when processes of all the given known case data are terminated.