METHODS AND SYSTEMS FOR SCALABLE EXTRACTION OF EPISODE RULES USING INCREMENTAL EPISODE TREE CONSTRUCTION IN A MULTI-APPLICATION EVENT SPACE

• US 20130110758A1
• Filed: 10/28/2011
• Published: 05/02/2013
• Est. Priority Date: 10/28/2011
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Jung, Gueyoung, Gnanasambandam, Shanmuga-Nathan, Hernandez, Andres Quiroz, Li, Zhiguo
• Granted Patent: US 9,367,813 B2
• Time in Patent Office: Days
• US Class Current: 706/47
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 5/025 Extracting rules from data
• CPC Class Codes: G06N 5/04 Inference or reasoning models

Abstract

Methods and systems for scalable extraction of episode rules using incremental episode tree construction in a multi-application event space comprise compiling events from multiple, different domain logs into in a universal log file, rolling domain-dependent and domain-independent windows through the universal log file to identify distinct event-pattern episodes, adding episodes to an episode tree data structure, pruning less frequent episodes from the episode tree, analyzing the episode tree to identify frequent episode rules, and applying the frequent episode rules to future interactions with users.

Claims

1. A computer-implemented method of identifying frequently occurring episodes comprising:

collecting records of events in a log file, the events representing actions taken by one or more users within a plurality of service portals;

determining a window comprising a timespan;

identifying, by a processor, a plurality of frequently occurring episodes represented in the log file, wherein each frequently occurring episode comprises a plurality of events occurring within the window.

2. The method of claim 1, wherein identifying the plurality of frequently occurring episodes represented in the log file comprises:

placing the window at a position associated with each event in the log file; and

for each window position, analyzing events within the window to identify one or more event patterns.

3. The method of claim 1, wherein the plurality of events in a frequently occurring episode correspond to actions taken by a single user identity.

4. The method of claim 1, wherein determining the window comprises:

identifying an average user session length within the plurality of service portals.

5. The method of claim 4, wherein identifying the average user session length comprises:

identifying a plurality of user sessions according to time-gaps between the user sessions having lengths greater than a specified threshold; and

computing the average user session length based of the plurality of user sessions.

6. The method of claim 1, further comprising:

adding a plurality of episodes occurring within the window to an episode tree data structure.

7. The method of claim 6, further comprising:

removing episodes from the episode tree having a frequency less than a specified threshold.

8. The method of claim 6, further comprising:

adding all distinct one-event episodes in the log file to the episode tree; and

removing one-event episodes having a frequency less than a specified threshold.

9. The method of claim 8, further comprising:

for each distinct combination of an N-event episode on the episode tree and an event occurring subsequent to the episode within a same window placement as the episode, adding the event to the episode tree to generate an (N+1)-event episode on the episode tree; and

removing (N+1)-event episodes from the episode tree having a frequency less than a specified threshold.

10. The method of claim 9, further comprising:

repeating the steps set forth in claim 9 for incremental values of N, from N=1 until no N-event episodes are found in the log file having a frequency greater than or equal to a specified threshold.

11. The method of claim 6, further comprising:

determining one or more probability rules concerning whether one or more episodes will occur in a future user session based on the episode tree.

12. The method of claim 11, further comprising:

applying the one or more probability rules to future interactions with users.

13. A system configured to identify frequently occurring episodes comprising:

a processing system comprising one or more processors; and

a memory system comprising one or more computer-readable media, wherein the computer-readable media contain instructions stored thereon that, when executed by the processing system, cause the processing system to perform operations comprising;

collecting records of events in a log file, the events representing actions taken by one or more users within a plurality of service portals;

determining a window comprising a timespan;

identifying, by a processor, a plurality of frequently occurring episodes represented in the log file, wherein each frequently occurring episode comprises a plurality of events occurring within the window.

14. The system of claim 13, wherein identifying the plurality of frequently occurring episodes represented in the log file comprises:

placing the window at a position associated with each event in the log file; and

for each window position, analyzing events within the window to identify one or more event patterns.

15. The system of claim 13, wherein the plurality of events in a frequently occurring episode correspond to actions taken by a single user identity.

16. The system of claim 13, wherein determining the window comprises:

identifying an average user session length within the plurality of service portals.

17. The system of claim 16, wherein identifying the average user session length comprises:

identifying a plurality of user sessions according to time-gaps between the user sessions having lengths greater than a specified threshold; and

computing the average user session length based of the plurality of user sessions.

18. The system of claim 13, the operations further comprising:

adding a plurality of episodes occurring within the window to an episode tree data structure.

19. The system of claim 18, the operations further comprising:

removing episodes from the episode tree having a frequency less than a specified threshold.

20. The system of claim 18, the operations further comprising:

adding all distinct one-event episodes in the log file to the episode tree; and

removing one-event episodes having a frequency less than a specified threshold.

21. The system of claim 20, the operations further comprising:

for each distinct combination of an N-event episode on the episode tree and an event occurring subsequent to the episode within a same window placement as the episode, adding the event to the episode tree to generate an (N+1)-event episode on the episode tree; and

removing (N+1)-event episodes from the episode tree having a frequency less than a specified threshold.

22. The system of claim 21, the operations further comprising:

repeating the steps set forth in claim 8 for incremental values of N, from N=1 until no N-event episodes are found in the log file having a frequency greater than or equal to a specified threshold.

23. The system of claim 18, the operations further comprising:

determining one or more probability rules concerning whether one or more episodes will occur in a future user session based on the episode tree.

24. The system of claim 23, the operations further comprising:

applying the one or more probability rules to future interactions with users.