System and method for constraint based sequential pattern mining
AssigneeLucent Technologies Inc.
InventorsMinos N. Garofalakis, Rajeev Rastogi, Kyuseok Shim
Life of this patent
Estimating the term…
Abstract
The present invention provides a method and system for sequential pattern mining with a given constraint. A Regular Expression (RE) is used for identifying the family of interesting frequent patterns. A family of methods that enforce the RE constraint to different degrees within the generating and pruning of candidate patterns during the mining process is utilized. This is accomplished by employing different relaxations of the RE constraint in the mining loop. Those sequences which satisfy the given constraint are thus identified most expeditiously.
Claims18
A method for sequential pattern mining using a given constraint, said method comprising the steps of:
- selecting a second constraint less restrictive than the given constraint;
- identifying a set of frequent items which satisfy the second less restrictive constraint;
- producing a set of candidate sequences that satisfy the second less restrictive constraint;
- removing from the set of candidate sequences those sequences containing at least one subsequence that satisfies the second less restrictive constraint and is not frequent;
- counting support for all remaining candidate sequences;
- and
- continuing to successively produce a set of candidate sequences that satisfy the second less restrictive constraint, remove from the set of candidate sequences those sequences containing at least one subsequence that satisfies the second less restrictive constraint and is not frequent, and count support for all remaining candidate sequences until a given terminating condition is satisfied.
A method for producing candidate sets of item sequences for use in sequential pattern mining using a given constraint, said method comprising the steps of:
- determining an automaton which represents the given constraint;
- selecting a second constraint less restrictive than the given constraint;
- and
- producing a candidate set of item sequences which satisfies the second less restrictive constraint by composing those potentially frequent k-item sequences for the automaton from the set consisting of those (1) which are legal with respect to some state of the automaton, (2) which are valid with respect to some state of the automaton, or (3) which are valid for the automaton, depending on the degree to which the second constraint is less restrictive than the given constraint.
A method for producing candidate sets of itemset sequences for use in sequential pattern mining using a given constraint, said method comprising the steps of:
- determining an automaton which represents the given constraint;
- selecting a second constraint less restrictive than the given constraint;
- and
- producing a candidate set of itemset sequences which satisfies the second less restrictive constraint by composing those potentially frequent k-itemset sequences for the automaton from the set consisting of those (1) which are semi-legal with respect to some state of the automaton, (2) which are semi-valid with respect to some state of the automaton, or (3) which are valid for the automaton, depending on the degree to which the second constraint is less restrictive than the given constraint.
A method for pruning candidate item sequences having subsequences for use in sequential pattern mining using a given constraint, said method comprising the steps of:
- determining which automaton representing the given constraint was used to produce the candidate set;
- determining which second constraint less restrictive than the given constraint was used to produce the candidate set;
- and
- pruning the candidate set of k-item sequences which satisfy the second less restrictive constraint by removing from the set of candidate k-item sequences those containing at least one subsequence which is not frequent and (1) which is legal with respect to a state of the automaton, (2) which is valid with respect to a state of the automaton, or (3) which is valid for the automaton, depending on which second constraint is less restrictive than the given constraint was used to produce the candidate set.
A method for pruning candidate itemset sequences having subsequences for use in sequential pattern mining using a given constraint, said method comprising the steps of:
- determining which automaton representing the given constraint was used to produce the candidate set;
- determining which second constraint less restrictive than the given constraint was used to produce the candidate set;
- and
- pruning the candidate set of k-itemset sequences which satisfy the second less restrictive constraint by removing from the candidate set of k-itemset sequences those containing at least one subsequence which is not frequent and (1) which is semi-legal with respect to a state of the automaton, (2) which is semi-valid with respect to a state of the automaton, or (3) which is valid for the automaton, depending on which second constraint is less restrictive than the given constraint was used to produce the candidate set.
A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for sequential pattern mining using a given constraint, said method steps comprising:
- selecting a second constraint less restrictive than the given constraint;
- identifying a set of frequent items which satisfy the second less restrictive constraint;
- producing a set of candidate sequences that satisfy the second less restrictive constraint;
- removing from the set of candidate sequences those sequences containing at least one subsequence that satisfies the second less restrictive constraint and is not frequent;
- counting support for all remaining candidate sequences;
- and
- continuing to produce a set of candidate sequences that satisfy the second less restrictive constraint, remove from the set of candidate sequences those sequences containing at least one subsequence that satisfies the second less restrictive constraint and is not frequent, and count support for all remaining candidate sequences until a given terminating condition is satisfied.
Dependencies are inferred from the claim text.