Methods and framework for constraint-based activity mining (CMAP)

• US 8,046,322 B2
• Filed: 08/07/2007
• Issued: 10/25/2011
• Est. Priority Date: 08/07/2007
• Status: Active Grant

• Current Assignee: The Boeing Co.
• Original Assignee: The Boeing Co.
• Inventors: Tjoelker, Rodney A., Kao, Anne, Choi, Jai J., Wang, Changzhou
• Primary Examiner(s): CHANNAVAJJALA, SRIRAMA T
• Application Number:
  US11/835,225
• Publication Number:
  US 20090043766A1
• Time in Patent Office: 1,540 Days
• Field of Search: 707/1, 707/3, 707 5- 6, 707/100, 707/102, 707/103.Y, 707/103.Z, 707600-603, 707/694, 707/705, 707/713, 707/725, 707/758, 707/769, 707776-777, 707/780, 707/756, 707/778, 707/792, 707/962, 706 45- 50, 706/909, 717/120, 717/100, 709/224, 715/736
• US Class Current: 706/48
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases

Abstract

A method of mining data to discover activity patterns within the data is described. The method includes receiving data to be mined from at least one data source, determining which of a number of specified interests and constraints are associated with the mining process, selecting corresponding mining agents that combine search algorithms with propagators from the specified constraints, and finding any activity patterns that meet the specified interests and constraints.

Claims

1. A computer-based method of mining data to discover activity patterns within the data, said method comprising:

receiving data to be mined at a computer framework from at least one data source communicatively coupled to the computer framework;

determining which of a number of specified constraints are available for the mining task, the constraints including a syntactic filter constraint configured to utilize a sequence of modes to filter patterns and avoid generation of patterns with redundant atoms, a semantic filter constraint having a minimum frequency threshold, a sequence of modes and a Boolean expression on arguments in the modes, and at least one of a generation rule constraint, a maximum length constraint, an extended length constraint, and a complex constraint;

selecting corresponding mining agents that combine search algorithms with propagators from at least one of the specified constraints;

finding any activity patterns, using the computer framework, that meet at least one of the specified constraints, each activity pattern including one or more atoms, each atom defined on a predicate that includes one or more typed arguments; and

analyzing the activity patterns, using the computer framework, found to meet at least one of the specified constraints.

2. A method according to claim 1 further comprising at least one of saving found activity patterns into one or more computer accessible data repositories and reporting found activity patterns to a user.

3. A method according to claim 1 further comprising at least one of evaluating and matching found activity patterns against newly received data for at least one of categorizing new activities and detecting abnormal activities.

4. A method according to claim 1 wherein receiving data to be mined further comprises representing the received data as facts from a number of logically represented first order predicates.

5. A method according to claim 1 wherein finding any activity patterns comprises representing the pattern as a conjunction of one or more first order predicates.

6. A method according to claim 1 wherein:

receiving data to be mined from at least one data source comprises at least one of adding new data sources for mining, removing data sources from mining, and modifying data sources.

7. A method according to claim 1 further comprising at least one of creating and managing pattern mining tasks.

8. A method according to claim 7 wherein at least one of creating and managing pattern mining tasks further comprises at least one of starting pattern mining tasks, running pattern mining tasks, pausing pattern mining tasks, resuming pattern mining tasks, and canceling pattern mining tasks.

9. A method according to claim 1 wherein analyzing the activity patterns found to meet at least one of the specified constraints comprises at least one of filtering a set of patterns, ranking patterns according to specified attributes, and searching patterns in a pattern set having specific criteria.

10. A method according to claim 1 further comprising at least one of installing a plug in module into a platform, updating a plug in module, and removing a plug in module.

11. A method according to claim 1 further comprising:

at least one of adding, removing, and modifying pattern destinations based on a configuration of the found activity patterns; and

providing mining tasks based on a configuration of the pattern destinations.

12. A computer-based system for constraint-based mining of activity patterns within a framework, said system comprising:

a data input;

a plurality of data mining tools within the framework and operable to run on said system, said data mining tools configured to search data received at said data input for one or both of temporal and spatial patterns for activities of interest within one or more scenarios, each pattern including one or more atoms, each atom defined on a predicate that includes one or more typed arguments;

a plurality of constraints, said constraints based on knowledge and experiences, and operable to cause said system to determine whether one or more patterns satisfies the said constraints, said constraints organized based on a subsumption relationship among the constraints and including a syntactic filter constraint configured to utilize a sequence of modes to filter patterns and avoid generation of patterns with redundant atoms, a semantic filter constraint having a minimum frequency threshold, a sequence of modes and a Boolean expression on arguments in the modes, and at least one of a generation rule constraint, a maximum length constraint, an extended length constraint, and a complex constraint; and

at least one database configured for operation as a pattern repository.

13. A computer-based system according to claim 12 wherein said plurality of constraints comprises a mode constraint, said mode constraint configured to:

specify permissions on each argument for a given predicate; and

specify a maximum number of atoms matching a permission combination allowed in a pattern.

14. A computer-based system according to claim 12 wherein said generation rule constraint comprises:

a sequence of modes as matching conditions; and

a set of modes used to generate new atoms.

15. A computer-based system according to claim 12 wherein to search data received at said data input, said system is configured to:

initialize the search by creating a single pattern using a target predicate; and

invoke a refining process with the single pattern.

16. A computer-based system according to claim 15 wherein to invoke the refining process, said system is configured to stop the refining process if a maximum length is reached or if an extended length constraint cannot be met by the single pattern.

17. A computer-based system according to claim 15 wherein to invoke the refining process, said system is configured to:

generate candidate patterns according to the generation rule constraint if the single pattern does not meet at least one generation rule constraint; and

generate candidate patterns according to mode constraints using variables introduced in a splitting atom, and generate candidate patterns by copying atoms that are younger children of the splitting atom if the single pattern meets all generation rule constraints.

18. A computer-based system according to claim 17 wherein said system is configured to:

remove from a candidate pattern set those candidate patterns that do not met at least one of a specified syntactic constraint, a semantic constraint, a generic data independent constraint, and a generic data dependent constraint; and

recursively invoke the refining process for each candidate pattern in the candidate pattern set.