Event detection through pattern discovery

• US 8,682,032 B2
• Filed: 08/19/2011
• Issued: 03/25/2014
• Est. Priority Date: 08/19/2011
• Status: Active Grant

• Current Assignee: Kyndryl Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Fan, Quanfu, Gabbur, Prasad, Miyazawa, Sachiko, Pan, Jiyan, Pankanti, Sharathchandra U., Trinh, Hoang
• Primary Examiner(s): Werner, Brian P
• Application Number:
  US13/213,262
• Publication Number:
  US 20130044942A1
• Time in Patent Office: 949 Days
• Field of Search: None
• US Class Current: 382/103
• CPC Class Codes: G06F 18/254 of classification results, e.g. of results related to same input data
• CPC Class Codes: G06V 30/1918 Fusion techniques, i.e. combining data from various sources, e.g. sensor fusion
• CPC Class Codes: G06V 30/1985 Syntactic analysis, e.g. using a grammatical approach syntactic image representation G06V30/18171

Abstract

Events are classified through string pattern recognition. Text labels are assigned to image primitives in a time-ordered set of training images and to related time-ordered transactions in an associated training transaction log in a combined time-ordered training string of text labels as a function of image types. Transactions are labeled in a training transaction log with a transaction label, a training primitive image of a start of a transaction with a start image text label, a training primitive of an entry of a transaction into the log with an entry image text label, and a training primitive of a conclusion of a transaction with an ending image text label. Positive subset string patterns are discovered representing true events from the combined time-ordered training string of text labels, and negative subset string patterns defined by removing single transaction primitive labels from the positive subset string patterns.

Claims

1. A method for classifying events through string pattern recognition, the method comprising:

assigning text labels to image primitives in a time-ordered set of training images and to related time-ordered transactions in an associated training transaction log in a combined time-ordered training string of text labels as a function of image types, the assigning comprising labeling a transaction in the associated training transaction log with a transaction label, a training primitive image of a start of a transaction with a start image text label, a training primitive of an entry of a transaction into the log with an entry image text label, and a training primitive of a conclusion of a transaction with an ending image text label;

discovering via a processor a plurality of positive subset string patterns representing true events from the combined time-ordered training string of text labels that are each repeated in at least two of the positive subset string patterns, start with a start image label, end with an ending image label, and comprise a single transaction primitive label; and

defining a plurality of negative subset string patterns by removing the single transaction primitive label from each of the plurality of positive subset string patterns.

2. The method of claim 1, further comprising:

assigning text labels to time-ordered image primitives in input image data and to related time-ordered transactions in an associated input transaction log in a combined time-ordered input string of text labels, the assigning comprising labeling a transaction in the associated input transaction log with the transaction label, an input primitive image of a start of a transaction with the start image text label, an input primitive image of an entry of a transaction into the log with the entry image text label, and an input primitive image of a conclusion of a transaction with the ending image text label;

finding substrings within the combined time-ordered input string of text labels that match the discovered positive subset string patterns, wherein each positive subset string pattern match contributes a positive vote to each component primitive within said matching input substring;

accumulating the positive votes for each labeled input primitive;

finding substrings within the combined time-ordered input string of text labels that match the defined negative subset string patterns, wherein each negative subset string pattern match contributes a negative vote to each component primitive within said matching input substring;

accumulating the negative votes for each labeled input primitive;

classifying each of the labeled input primitives into a classified string of text labels as belonging to a true class if their accumulated positive votes exceed their accumulated negative votes, or as belonging to a false class if their accumulated negative votes exceed their accumulated positive votes;

segmenting continuous stretches of the classified string false labels into false transaction subset strings such that each false transaction subset string has a single entry image primitive; and

reporting the entry images within each of the false transaction subset strings as detected false events.

3. The method of claim 2, wherein the discovering the positive subset string patterns further comprises:

discovering a plurality of positive subset string patterns representing true events from the combined time-ordered training strings of text labels that each also observe a maximum length limit.

4. The method of claim 3, wherein the discovering the plurality of positive subset string patterns representing true events further comprises:

using a Teiresias pattern discovery algorithm to discover the plurality of positive subset string patterns representing true events that discovers all repeated unique maximal <

L, W>

patterns that each have a given maximum number of (W−

L) wildcard characters within any of their substrings of a given length (W).

5. The method of claim 4, wherein the discovering the plurality of positive subset string patterns representing true events further comprises:

constructing a co-occurrence matrix, each row in the matrix corresponding to a unique discovered pattern and each column to an input transaction used for pattern discovery; and

performing a singular value decomposition on the co-occurrence matrix.

6. The method of claim 4, wherein the step of classifying each of the labeled input primitives into the classified string of text labels as belonging to the true class or as belonging to the false class further comprises:

determining respective likelihoods of labeled input primitives as being a part of a true or a false event as a function of the context of the primitives and in relative proportion to a total number of positive and negative subset string patterns that match a substring containing the primitive; and

assigning the labeled input primitives to one of the true and false classes having a higher determined likelihood.

7. The method of claim 6, further comprising:

weighting the discovered positive and negative subset string patterns as a function of frequency weightings determined in inverse proportion to their occurrence frequency across all transactions used for pattern discovery.

8. The method of claim 7, wherein the step weighting the discovered positive and negative subset string patterns as the function of the frequency weightings further comprises:

determining support vector machine weightings for the discovered positive and negative subset string patterns by learning relative importances of the discovered patterns for classifying a primitive into true or false scan based on matches to their contexts; and

weighting each of the discovered positive and negative subset string patterns by respective sums of their frequency weightings and their support vector machine weightings.

9. A method of providing a service for classifying events through string pattern recognition, the method comprising:

providing a string text labeler device that assigns text labels to image primitives in a time-ordered set of images and to related time-ordered transactions in an associated training log in a combined time-ordered string of text labels as a function of image types; and

providing a pattern discoverer device that discovers positive subset string patterns representing true events from the combined time-ordered string of text labels that are each repeated in at least two of the positive subset strings, start with a start image label, end with an ending image label, and comprise a single transaction primitive label, and that defines a plurality of negative subset string patterns by removing the single transaction primitive label from each of the plurality of positive subset string patterns.

10. The method of claim 9, further comprising:

providing a string parser device that finds substrings within the combined time-ordered string of text labels that match the positive and negative subset string patterns, wherein each positive subset string pattern match contributes a positive vote, and each negative subset string pattern match contributes a negative vote, to each component primitive and within the respective matching substrings;

providing a classifier device that classifies the labeled primitives into a classified string of text labels as belonging to a true class if their accumulated positive votes exceed their accumulated negative votes, or as belonging to a false class if their accumulated negative votes exceed their accumulated positive votes;

providing a segmenter device that segments the classified, labeled primitives into true or false transaction subset strings such that each false transaction subset string has a single entry image primitive; and

providing a false event detector device that reports entry images within each of the false transaction subset strings as detected false events.

11. The method of claim 10, wherein the pattern discoverer device discovers the positive subset string patterns by discovering a plurality of positive subset string patterns representing true events from the combined time-ordered training strings of text labels that each also observe a maximum length limit.

12. The method of claim 11, wherein the pattern discoverer device discovers the plurality of positive subset string patterns representing true events by using a Teiresias pattern discovery algorithm to discover the plurality of positive subset string patterns representing true events that discovers all repeated unique maximal <

L, W>

patterns that each have a given maximum number of (W−

L) wildcard characters within any of their substrings of a given length (W).

13. The method of claim 12, wherein the pattern discoverer device discovers the plurality of positive subset string patterns representing true events by:

constructing a co-occurrence matrix, each row in the matrix corresponding to a unique discovered pattern and each column to an input transaction used for pattern discovery; and

performing a singular value decomposition on the co-occurrence matrix.

14. The method of claim 13, wherein the classifier device classifies each of the labeled input primitives into the classified string of text labels as belonging to the true class or as belonging to the false class by:

determining respective likelihoods of labeled input primitives as being a part of a true or a false event as a function of the context of the primitives and in relative proportion to a total number of positive and negative subset string patterns that match a substring containing the primitive; and

assigning the labeled input primitives to one of the true and false classes having a higher determined likelihood.

15. A system, comprising:

a processor;

a computer readable memory in circuit communication with the processor; and

a computer-readable storage medium in circuit communication with the processor and the computer readable memory;

wherein the processor, when executing program instructions stored on the computer-readable storage medium via the computer readable memory;

assigns text labels to image primitives in a time-ordered set of training images and to related time-ordered transactions in an associated training transaction log in a combined time-ordered training string of text labels as a function of image types, the assigning comprising labeling a transaction in the associated training transaction log with a transaction label, a training primitive image of a start of a transaction with a start image text label, a training primitive of an entry of a transaction into the log with an entry image text label, and a training primitive of a conclusion of a transaction with an ending image text label;

discovers a plurality of positive subset string patterns representing true events from the combined time-ordered training string of text labels that are each repeated in at least two of the positive subset string patterns, start with a start image label, end with an ending image label, and comprise a single transaction primitive label; and

defines a plurality of negative subset string patterns by removing the single transaction primitive label from each of the plurality of positive subset string patterns.

16. The system of claim 15, wherein the processor, when executing the program instructions stored on the computer-readable storage medium via the computer readable memory, further:

assigns text labels to time-ordered image primitives in input image data and to related time-ordered transactions in an associated input transaction log in a combined time-ordered input string of text labels, the assigning comprising labeling a transaction in the associated input transaction log with the transaction label, an input primitive image of a start of a transaction with the start image text label, an input primitive image of an entry of a transaction into the log with the entry image text label, and an input primitive image of a conclusion of a transaction with the ending image text label;

finds substrings within the combined time-ordered input string of text labels that match the discovered positive subset string patterns, wherein each positive subset string pattern match contributes a positive vote to each component primitive within said matching input substring;

accumulates the positive votes for each labeled input primitive;

finds substrings within the combined time-ordered input string of text labels that match the defined negative subset string patterns, wherein each negative subset string pattern match contributes a negative vote to each component primitive within said matching input substring;

accumulates the negative votes for each labeled input primitive;

classifies each of the labeled input primitives into a classified string of text labels as belonging to a true class if their accumulated positive votes exceed their accumulated negative votes, or as belonging to a false class if their accumulated negative votes exceed their accumulated positive votes;

segments continuous stretches of the classified string false labels into false transaction subset strings such that each false transaction subset string has a single entry image primitive; and

reports the entry images within each of the false transaction subset strings as detected false events.

17. The system of claim 16, wherein the processor, when executing the program instructions stored on the computer-readable storage medium via the computer readable memory, further discovers the positive subset string patterns by discovering a plurality of positive subset string patterns representing true events from the combined time-ordered training strings of text labels that each also observe a maximum length limit.

18. The system of claim 17, wherein the processor, when executing the program instructions stored on the computer-readable storage medium via the computer readable memory, further discovers the plurality of positive subset string patterns representing true events by using a Teiresias pattern discovery algorithm to discover the plurality of positive subset string patterns representing true events that discovers all repeated unique maximal <

L, W>

patterns that each have a given maximum number of (W−

L) wildcard characters within any of their substrings of a given length (W).

19. The system of claim 18, wherein the processor, when executing the program instructions stored on the computer-readable storage medium via the computer readable memory, further classifies each of the labeled input primitives into the classified string of text labels as belonging to the true class or as belonging to the false class by:

determining respective likelihoods of labeled input primitives as being a part of a true or a false event as a function of the context of the primitives and in relative proportion to a total number of positive and negative subset string patterns that match a substring containing the primitive; and

assigning the labeled input primitives to one of the true and false classes having a higher determined likelihood.

20. The system of claim 19, wherein the processor, when executing the program instructions stored on the computer-readable storage medium via the computer readable memory, further weights the discovered positive and negative subset string patterns as a function of frequency weightings determined in inverse proportion to their occurrence frequency across all transactions used for pattern discovery.

21. An article of manufacture, comprising:

a tangible computer readable storage hardware device having computer readable program code embodied therewith, the computer readable program code comprising instructions that, when executed by a computer processor, cause the computer processor to;

assign text labels to image primitives in a time-ordered set of training images and to related time-ordered transactions in an associated training transaction log in a combined time-ordered training string of text labels as a function of image types, the assigning comprising labeling a transaction in the associated training transaction log with a transaction label, a training primitive image of a start of a transaction with a start image text label, a training primitive of an entry of a transaction into the log with an entry image text label, and a training primitive of a conclusion of a transaction with an ending image text label;

discover a plurality of positive subset string patterns representing true events from the combined time-ordered training string of text labels that are each repeated in at least two of the positive subset string patterns, start with a start image label, end with an ending image label, and comprise a single transaction primitive label; and

define a plurality of negative subset string patterns by removing the single transaction primitive label from each of the plurality of positive subset string patterns.

22. The article of manufacture of claim 21, wherein the computer readable program code instructions, when executed by the computer processor, further cause the computer processor to:

assign text labels to time-ordered image primitives in input image data and to related time-ordered transactions in an associated input transaction log in a combined time-ordered input string of text labels, the assigning comprising labeling a transaction in the associated input transaction log with the transaction label, an input primitive image of a start of a transaction with the start image text label, an input primitive image of an entry of a transaction into the log with the entry image text label, and an input primitive image of a conclusion of a transaction with the ending image text label;

find substrings within the combined time-ordered input string of text labels that match the discovered positive subset string patterns, wherein each positive subset string pattern match contributes a positive vote to each component primitive within said matching input substring;

accumulate the positive votes for each labeled input primitive;

find substrings within the combined time-ordered input string of text labels that match the defined negative subset string patterns, wherein each negative subset string pattern match contributes a negative vote to each component primitive within said matching input substring;

accumulate the negative votes for each labeled input primitive;

classify each of the labeled input primitives into a classified string of text labels as belonging to a true class if their accumulated positive votes exceed their accumulated negative votes, or as belonging to a false class if their accumulated negative votes exceed their accumulated positive votes;

segment continuous stretches of the classified string false labels into false transaction subset strings such that each false transaction subset string has a single entry image primitive; and

report the entry images within each of the false transaction subset strings as detected false events.

23. The article of manufacture of claim 22, wherein the computer readable program code instructions, when executed by the computer processor, further cause the computer processor to discover the positive subset string patterns by discovering a plurality of positive subset string patterns representing true events from the combined time-ordered training strings of text labels that each also observe a maximum length limit.

24. The article of manufacture of claim 23, wherein the computer readable program code instructions, when executed by the computer processor, further cause the computer processor to discover the plurality of positive subset string patterns representing true events by using a Teiresias pattern discovery algorithm to discover the plurality of positive subset string patterns representing true events that discovers all repeated unique maximal <

L, W>

patterns that each have a given maximum number of (W−

L) wildcard characters within any of their substrings of a given length (W).

25. The article of manufacture of claim 24, wherein the computer readable program code instructions, when executed by the computer processor, further cause the computer processor to classify each of the labeled input primitives into the classified string of text labels as belonging to the true class or as belonging to the false class by:

determining respective likelihoods of labeled input primitives as being a part of a true or a false event as a function of the context of the primitives and in relative proportion to a total number of positive and negative subset string patterns that match a substring containing the primitive; and

assigning the labeled input primitives to one of the true and false classes having a higher determined likelihood.