Back to results
US 6,189,005 B1Granted
System and method for mining surprising temporal patterns
AssigneeInternational Business Machines Corporation
InventorsSoumen Chakrabarti, Byron Edward Dom, Sunita Sarawagi
Life of this patent
Estimating the term…
Abstract
A system and method for data mining is provided in which temporal patterns of itemsets in transactions having unexpected support values are identified. A surprising temporal pattern is an itemset whose support changes over time. The method may use a minimum description length formulation to discover these surprising temporal patterns.
Claims44
A method for identifying unexpected temporal patterns in a dataset containing a plurality of transactions, each transaction containing one or more items with a time-stamp, the one or more items being grouped into itemsets containing a pattern of items, the method comprising:
- generating one or more support values at predetermined times for each pattern, each support value indicating a portion of the transactions in the dataset containing each-such pattern at a predetermined time;
- selecting unexpected patterns from the dataset which have a support value at a predetermined time that is higher than a predetermined threshold value;
- and
- identifying an unexpected temporal pattern from the selected unexpected patterns, the unexpected temporal pattern having support values over a predetermined time period which change more than a second predetermined threshold value.
1 more element
A method for identifying unexpected temporal patterns in a dataset containing a plurality of transactions, each transaction containing one or more time-stamped items, the one or more items being grouped into itemsets having a pattern of items, the method comprising:
- generating a support value at a predetermined time for each pattern indicating the portion of the transactions in the dataset containing the pattern of items at the predetermined time;
- selecting candidate patterns from the dataset based on the variations in the support value of the pattern over a predetermined time period;
- generating an unconstrained description length for each candidate pattern, the unconstrained description length corresponding to a value indicating changes in the support of the pattern over the predetermined time period;
- generating a constrained description length for each candidate pattern, the constrained description length corresponding to a compressed value indicating the changes in the support of the pattern over the predetermined time period;
- and
- identifying patterns, based on a comparison of the unconstrained description length and the constrained description length, which have a unexpected support value which changes during the predetermined time period to generate unexpected temporal patterns.
3 more elements
A computer system for data mining unexpected temporal patterns, the system comprising:
- a data storage medium to store a database of a plurality of transactions, each transaction containing one or more time-stamped items, the one or more items being grouped into itemsets having a pattern of items;
- an output module to output the identity of the surprising temporal patterns;
- and
- an operating system stored in a computer readable medium with a surprising temporal identifier kernel, which accesses the data storage database, to execute a series of machine-executable instructions that identify surprising temporal patterns as follows:
- generating one or more support values at predetermined times for each pattern, each support value indicating a portion of the transactions in the dataset containing each such pattern at a predetermined time;
- selecting unexpected patterns from the dataset which have a support value at a predetermined time that is higher than a predetermined threshold value;
- and
- identifying an unexpected temporal pattern from the selected unexpected patterns, the unexpected temporal pattern having support values over a predetermined time period which change more than a second predetermined threshold value.
5 more elements
A computer system for data mining unexpected temporal patterns, the system comprising:
- a data storage medium to store a database of a plurality of transactions, each transaction containing one or more time-stamped items, the one or more items being grouped into itemsets having a pattern of items;
- an output module to output the identity of the surprising temporal patterns;
- and
- an operating system stored in a computer readable medium with a surprising temporal identifier kernel, which accesses the data storage database, to execute a series of machine-executable instructions that identify surprising temporal patterns as follows:
- generating a support value at a predetermined time for each pattern indicating the portion of the transactions in the dataset containing the pattern of items at the predetermined time;
- selecting candidate patterns from the dataset based on the variations in the support value of the pattern over a predetermined time period;
- generating an unconstrained description length for each candidate pattern, the unconstrained description length corresponding to a value indicating changes in the support of the pattern over the predetermined time period;
- generating a constrained description length for each candidate pattern, the constrained description length corresponding to a compressed value indicating the changes in the support of the pattern over the predetermined time period;
- and
- identifying patterns, based on a comparison of the unconstrained description length and the constrained description length, which have a unexpected support value which changes during the predetermined time period to generate unexpected temporal patterns.
7 more elements
A computer system for data mining unexpected temporal patterns, the system comprising:
- a client computer including:
- an operating system stored in a computer readable medium with a surprising temporal identifier kernel to execute a series of machine-executable instructions that identify surprising temporal patterns;
- an output module to output the identity of the surprising temporal patterns;
- and a server computer including:
- a processor;
- a data storage medium to store a database of a plurality of transactions, each transaction containing one or more time-stamped items, the one or more items being grouped into itemsets having a pattern of items;
- an operating system stored in a computer readable medium with a surprising temporal identifier kernel, which accesses the data storage database, to execute a series of machine-executable instructions which identify surprising temporal patterns;
- and wherein the surprising temporal identifier kernel executes instructions as follows:
- generating one or more support values at predetermined times for each pattern, each support value indicating a portion of the transactions in the dataset containing each such pattern at a predetermined time;
- selecting unexpected patterns from the dataset which have a support value at a predetermined time that is higher than a predetermined threshold value;
- and
- identifying an unexpected temporal pattern from the selected unexpected patterns, the unexpected temporal pattern having support values over a predetermined time period which change more than a second predetermined threshold value.
9 more elements
A computer system for data mining unexpected temporal patterns, the system comprising:
- a client computer including:
- an operating system stored in a computer readable medium with a surprising temporal identifier kernel to execute a series of machine-executable instructions which identify surprising temporal patterns;
- an output module to output the identity of the surprising temporal patterns;
- and a server computer including:
- a processor;
- a data storage medium to store a database of a plurality of transactions, each transaction containing one or more time-stamped items, the one or more items being grouped into itemsets having a pattern of items;
- an operating system stored in a computer readable medium with a surprising temporal identifier kernel, which accesses the data storage database, to execute a series of machine-executable instructions that identify surprising temporal patterns;
- and
- wherein the surprising temporal identifier kernel executes instructions as follows:
- generating a support value at a predetermined time for each pattern indicating the portion of the transactions in the dataset containing the pattern of items at the predetermined time;
- selecting candidate patterns from the dataset based on the variations in the support value of the pattern over a predetermined time period;
- generating an unconstrained description length for each candidate pattern, the unconstrained description length corresponding to a value indicating changes in the support of the pattern over the predetermined time period;
- generating a constrained description length for each candidate pattern, the constrained description length corresponding to a compressed value indicating the changes in the support of the pattern over the predetermined time period;
- and
- identifying patterns, based on a comparison of the unconstrained description length and the constrained description length, which have a unexpected support value which changes during the predetermined time period to generate unexpected temporal patterns.
12 more elements
Dependencies are inferred from the claim text.