Data processing method and apparatus for identifying classification to which data belongs

• US 6,125,362 A
• Filed: 12/04/1997
• Issued: 09/26/2000
• Est. Priority Date: 12/04/1996
• Status: Expired due to Term

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Elworthy, David
• Primary Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US08/985,315
• Time in Patent Office: 1,027 Days
• Field of Search: 707/6, 704/8
• US Class Current: 1/1
• CPC Class Codes: G06F 40/263 Language identification
• CPC Class Codes: G06V 30/246 using linguistic properties, e.g. specific for English or German language
• CPC Class Codes: G06V 30/40 Document-oriented image-based pattern recognition
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A data processing method and apparatus is described for identifying a classification to which data belongs where the data comprises a plurality of features at least some of which are common to a plurality of classifications. The features of the data are extracted as sequential elements which are sequentially input until the classification to which data belongs is identified. The elements are compared with predetermined probability values for the elements of each classification to determine a probability that the elements belong to a classification. The probabilities are accumulated to form an accumulated probability for each classification and a classification to which data belongs is identified from the accumulated probability.

Claims

1. A data processing method for identifying a classification to which data belongs, the data comprising a plurality of features at least some of which are common to a plurality of classifications, the method comprising the steps of:

extracting the features of the data as sequential elements and sequentially inputting the sequential elements or groups of elements until the classification to which data belongs is identified;

for each element or group of elements, comparing the element or group of elements with predetermined probability values for elements or groups of elements of each classification to determine a probability with a specified confidence range that the element or group of elements belong to a classification;

accumulating the probabilities to form an accumulated probability for each classification; and

identifying a classification to which the data belongs from the accumulated probability if the accumulated probability reaches a predetermined probability threshold, and the accumulated probability for the classification is greater than the accumulated probabilities of each of the other classifications by a predetermined amount.

2. A method according to claim 1 including the step of outputting the identified classification.

3. A method according to claim 2 including the step of outputting the accumulated probability for the identified classification.

4. A method according to claim 2 wherein the output identified classification is used for the further processing of data.

5. A method according to claim 4, wherein data belonging to different classifications requires processing differently and the output identified classification is used to select the processing to be carried out on the data.

6. A method according to claim 1 wherein if the accumulated probabilities of the classification do not reach the predetermined probability threshold, several of the classifications having the highest accumulated probabilities are identified as possible classifications to which the data belongs.

7. A method according to claim 6, wherein a user manually selects a classification from among the possible classifications.

8. A method according to claim 1 wherein each of the probabilities and accumulated probabilities comprise a minimum likely value for the probability within a predetermined confidence range, a maximum likely value for the probability within a predetermined confidence range and a base value for the probability which is the most likely value, and a classification is identified as the classification to which the input data belongs if the base value of the accumulated probability for the classification reaches said predetermined probability threshold.

9. A method according to claim 8 wherein if the minimum likely value of the accumulated probability for the classification having the highest base value is not greater than the maximum likely value of the accumulated probabilities of each of the other classifications, the classifications having the maximum likely values of the accumulated probabilities which are greater than the minimum likely values of the classification having the highest base value are identified as possible classifications to which the data belongs.

10. A method according to claim 9, wherein each of the minimum and maximum likely values of the probabilities are calculated as being two or more standard deviations from the base values of the accumulated probabilities.

11. A method according to claim 1 wherein each of the probabilities and accumulated probabilities comprise a minimum likely value for the probability within a predetermined confidence range, a maximum likely value for the probability within a predetermined confidence range, and a base value for the probability which is the most likely value;

and a classification is identified as the classification to which the input data belongs if the base value of the accumulated probability for the classification reaches said predetermined probability threshold and the minimum likely value of the accumulated probability for the classification is greater than the maximum likely values of the accumulated probabilities of each of the other classifications.

12. A method according to claim 11, wherein if the base values of the accumulated probabilities for the classifications do not reach said predetermined probability threshold, several of the classifications having the highest base values of the accumulated probabilities are identified as possible classifications to which the data belongs.

13. A method according to claim 1 wherein a classification is identified as a classification to which the data belongs if the accumulated probability is greater than the accumulated probability of each of the other classifications by a predetermined amount.

14. A method according to claim 13 wherein if the highest accumulated probability is not greater than each of the other accumulated probabilities by said predetermined amount, several of the classifications having the highest accumulated probabilities are identified as possible classifications to which data belongs.

15. A method according to claim 13 wherein each of the probabilities and accumulated probabilities comprise a minimum likely value for the probability within a predetermined confidence range, a maximum likely value for the probability within a predetermined confidence range, and a base value for the probability which is the most likely value;

and a classification is identified as the classification to which the data belongs if the base value of the accumulated probability for the classification is greater than the base values of the accumulated probabilities of the other classifications.

16. A method according to claim 1 wherein said sequential elements are input as groups of sequential elements.

17. A method according to claim 1 wherein the step of extracting the features comprise the step of coding the features of the as data sequential elements.

18. A method according to claim 17 wherein the coding step comprises coding to generate a reduced number of different elements compared with the number of different features in the data.

19. A method according to claim 1 wherein the step of extracting the features comprises identifying each element in the data which comprises a feature.

20. A method according to claim 1 including the preliminary steps to determine said predetermined probability values of:

a) extracting the features of training data representative of a known classification as sequential elements and sequentially inputting the sequential elements,

b) calculating probability values for the sequential elements, and

c) storing the calculated probability values, and repeating steps a to c for each classification.

21. A method according to claim 20 wherein the step of calculating the probability values for the sequential elements or groups of elements includes determining the frequency of occurrence of each element or group of sequential elements.

22. A method according to claim 20 wherein the probability values are calculated using Bayes Rule such that the probability values are given by:

##EQU8## where;

p(l|t) is the probability of the classification given the element or groups of elements

p(t|l) is the probability of the element given the classification

p(l) is the probability of the classification

p(t) is the probability of the element or group of elements.

23. A method as claimed in claim 20 wherein the step of calculating the predetermined probability values for the sequential elements includes the steps of calculating the probability of the occurrence of an element or group of elements in the data input for all of the classifications, setting the probability of the occurrence of the classification to a preset level, and calculating the probability of an element occurring in a classification.

24. A method as claimed in claim 23 wherein the probability of the occupance of a classification is the same for all classifications and is therefore ignored in the calculations.

25. A method according to claim 20 wherein the predetermined probability values comprise a minimum likely value for the probability, a maximum likely value for the probability and a base value for the probability which is the most likely value, the minimum and maximum likely values being calculated as probability values lying within a predetermined confidence range of the base value.

26. A method according to claim 20 wherein the step of calculating values including the step of calculating probability values for each classification for elements or groups of elements which do not occur in the training data.

27. A method of sorting data comprising the data processing method for identifying a classification to which the data belongs in accordance with claim 1, and the step of sorting the data in accordance with the identified classification.

28. A method of processing data comprising the method for identifying a classification to which the data belongs in accordance with claim 1, and the step of processing the data in accordance with the identified classification.

29. Data processing apparatus for identifying a classification to which data belongs, the data comprising a plurality of features at least some of which are common to a plurality of classifications, the apparatus comprising:

an inputter and extractor, which extracts the features of the data as sequential elements and sequentially inputs the sequential elements until the classification to which the data belongs is identified;

memory for storing predetermined probability values for elements or groups of elements of each classification;

a comparator arranged to receive and sequentially compare each element or group of elements with said predetermined probability values for each classification to determine a probability that the element or group of elements belong to a classification;

an accumulator that accumulates the probabilities to form an accumulated probability with a specified confidence range for each classification; and

an identification processor that identifies a classification to which the data belongs from the accumulated probability, said identification processor being arranged to identify a classification as a classification to which the data belongs if the accumulated probability of the classification reaches a predetermined probability threshold and the accumulated probability for the classification is greater than the accumulated probabilities of each of the other classifications by predetermined amount.

30. Data processing apparatus according to claim 29 including an output unit that outputs the accumulated probability.

31. Data processing apparatus according to claim 30 wherein said output unit is arranged to also output the accumulated probability for the identified classification.

32. Data processing apparatus according to claim 30 or claim 31 including a processor that performs further processing on the data.

33. Data processing apparatus according to claim 32 wherein said processor is arranged to process the data differently for data of different classifications and is responsive to said identified classification to process the data accordingly.

34. Data processing apparatus according to claim 29 wherein said identification processor is arranged to identify several of the classifications having the highest accumulated probabilities as possible classifications to which the data belongs if the accumulated probabilities of the classifications do not reach the predetermined probability threshold.

35. Data processing apparatus according to claim 34 wherein said identification processor is arranged to identify several of the classifications having the highest base values of the accumulated probabilities as possible classifications to which the data belongs if the base values of the accumulated probabilities for the classifications do not reach said predetermined probability threshold.

36. Data processing apparatus according to claim 34, including user operable selection beams for selecting a classification from among the possible classifications.

37. Data processing apparatus according to claim 29 wherein each of the probabilities and accumulated probabilities comprise a minimum likely value for the probability within a predetermined confidence range, a maximum likely value for the probability within a predetermined confidence range, and a base value for the probability which is the most likely value, said identification means being arranged to identify a classification as the classification to which the input data belongs if the use value of the accumulated probability for the classification reaches said predetermined probability threshold, and the minimum likely value of the accumulated probability for the classification is greater than the maximum likely values of the accumulated probabilities of each of the other classifications.

38. Data processing apparatus according to claim 37 wherein if the minimum likely value of the accumulated probability for the classification having the highest base value is not greater than the maximum likely value of the accumulated probabilities of each of the classifications, said identification processor is arranged to identify the classifications having the maximum likely values of the accumulated probabilities which are greater than the minimum likely values of the classification having the highest base value as possible classifications to which the data belongs.

39. Data processing apparatus according to claim 37, wherein said memory stores said base values, and said minimum and maximum likely values which are calculated as being two or more standard deviations from the base values of the accumulated probabilities.

40. Data processing apparatus according to claim 29 wherein each of the probabilities and accumulated probabilities comprise a minimum likely value for the probability within a predetermined confidence range, a maximum likely value for the probability within a predetermined confidence range, and a base value for the probability which is the most likely value;

said identification means being arranged to identify the classification to which the input data belongs if the base value of the accumulated probability for the classification reaches said predetermined probability threshold.

41. Data processing apparatus according to claim 29 wherein said identifications processor is arranged to identify a classification as a classification to which data belongs if the accumulated probability for a classification having the highest accumulated probability is greater than the accumulated probabilities of each of the other classifications by a predetermined amount.

42. Data processing apparatus according to claim 41 wherein said identification processor is arranged to identify several of the classifications having the highest accumulated probabilities as possible classifications to which the data belongs if the highest accumulated probability is not greater than each of the other accumulated probabilities by said predetermined amount.

43. Data processing apparatus according to claim 41 wherein each of the probabilities and accumulated probabilities comprise a minimum likely value for the probability within a predetermined confidence range, a maximum likely value for the probability within a predetermined confidence range, and a base value for the probability which is the most likely value;

said identification processor being arranged to identify a classification as the classification to which the data belongs if the base value of the accumulated probability for the classification is greater than the base values of the accumulated probabilities of the other classifications by said predetermined amount, and the minimum likely values of the accumulated probability for the classification is greater than the maximum values of the accumulated probabilities of each of the other classifications.

44. Data processing apparatus according to claim 29 wherein said inputter and extractor is arranged to input said elements as groups of sequential amounts.

45. Data processing apparatus according to claim 29 wherein said inputter and extractor includes a coding unit that extracts the features of the data by coding the features as sequential elements.

46. Data processing apparatus according to claim 45 wherein said coding unit is arranged to code the features to generate a reduced number of different elements compared with the number of different values in the data.

47. Data processing apparatus according to claim 29 wherein said inputter and extractor is arranged to extract the features of the data by identifying each element in the data which comprises a feature.

48. Data processing apparatus according to claim 29 including a training unit that calculates and stores said predetermined probability values in said memory, said training unit being responsive to training data input by said inputter and extractor to calculate said predetermined probability values, said training data comprising data representative of a known classification.

49. Data processing apparatus according to claim 48 wherein said training unit includes means for determining the frequency of occupance of each element or group of sequential elements.

50. Data processing apparatus according to claim 48 wherein said training unit is arranged to calculate the predetermined probability values using Bayes Rule such that the probability values are given by:

##EQU9## where;

p(l|t) is the probability of the classification given the element,

p(t|l) is the probability of the element given the classification,

p(l) is the probability of the classification, and

p(t) is the probability of the element.

51. Data processing apparatus according to claim 48 wherein said training unit is arranged to calculate the predetermined probability values for the sequential elements by calculating the probability of the occurrence of an element in the data input for all of the classification, setting the probability of the occurrence of a classification to a preset level, and calculating the probability of an element occurring in a classification.

52. Data processing apparatus according to claim 51 wherein the probability of the occurrence of a classification is the same and said training unit is arranged to calculate said predetermined probability values by ignoring the probability of the occurrence of a classification.

53. Data processing apparatus according to claim 48 wherein said memory stores the predetermined probability values comprising a minimum likely value for the probability, a maximum likely value for the probability, and a base value for the probability which is the most likely value, said training unit being arranged to calculate the minimum and maximum values as probability values lying within a predetermined confidence range of the base value.

54. Data processing apparatus according to claim 48 wherein said training unit is arranged to calculate probability values for each classification for elements or groups of elements which do not occur in the training data.

55. Data sorting apparatus comprising the data processing apparatus according to claim 29, and a sorting unit for sorting the data in accordance with the identified classification.

56. Data processing apparatus according to claim 29 including a processing unit that processes the data in accordance with the identified classification.

57. A computer usable medium having computer readable instructions stored therein for causing a processor in a data processing apparatus to process signals defining data comprising a plurality of features at least some of which are common to a plurality of classification to identify a classification to which the data belongs, the instructions comprising instructions for:

extracting the features of the data as sequential elements and sequentially inputting the sequential elements or groups of elements until the classification to which data belongs is identified;

for each element or group of elements, comparing the element or group of elements with predetermined probability values for elements or groups of elements of each classification to determine a probability with a specified confidence range that the element or group of elements belong to a classification;

accumulating the probabilities to form an accumulated probability for each classification; and

identifying a classification to which the data belongs from the accumulated probability if the accumulated probability reaches a predetermined probability threshold, and the accumulated probability for the classification is greater than the accumulated probabilities of each of the other classifications by a predetermined amount.