Data processing: artificial intelligence – Knowledge processing system
Reexamination Certificate
1998-09-14
2001-05-22
Powell, Mark R. (Department: 2122)
Data processing: artificial intelligence
Knowledge processing system
C706S047000, C707S793000
Reexamination Certificate
active
06236982
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a system and associated methods for mining for user-defined patterns in association rules. More particularly, the invention discloses methods for analyzing transactional data to discover calendric association rules, which allow for interpretation of the data taking into account user-defined time periods.
BACKGROUND OF THE INVENTION
With the recent advances in computing technology, many businesses have begun to maintain detailed records of all aspects of business operation, particularly data concerning transactions. This data may be used, inter alia, to determine which products or services are moving well, which products or services should be discontinued, packaged together, sold at the same retail outlet, etc. It can be readily appreciated that thorough analysis of transaction data can be used by businesses to more effectively control and distribute inventory and create effective store displays. For example, if a retail store sells both beer and nuts, it would be helpful from a marketing standpoint to know if there was an association rule expressing the percentage of customers buying beer who also buy nuts. Specifically, an association rule captures the notion of a set of data items occurring together in transactions. For example, in a database of a retail store which sells beer and nuts an association rule might be of the form:
beer→nuts (support: 3%, confidence: 87%),
which indicates that 3% of all transactions stored in the database and mined for association rules contain the data items beer and nuts and that 87% of the transactions that have the item beer also have the item nuts. The two percentage terms above are commonly referred to “support” and “confidence”, respectively.
There are many prior art systems for generating association rules or “mining” data for association rules. However, these systems do not allow for the mining of association rules within user specified time intervals or calendars such as, “first day of the month”, or “government paydays”. Thus the variance of association rules over time given such a user defined calendar cannot be discovered using prior art methods. More specifically, the prior art methods handle the transaction data as one large segment and do not permit segmentation of the data so as to allow the above queries. For example, a user could not determine which part of the day the most transactions occurred with respect to beer and nuts. That is, analysis cannot be done of the data in finer time granularity may reveal that the association rule exists only in certain time intervals and does not occur in the remaining time intervals.
Accordingly, there is a need to provide a method for mining for association rules where there is a temporal component, specifically, a user defined calendar. Generating these calendric association rules allows the user to do a more detailed analysis of the transactions, and correspondingly provides the user with a more powerful tool with which to control business operations more efficiently.
SUMMARY OF THE INVENTION
The invention is a methodology for discovering association rules exhibiting temporal variations of interest to users. The method uses calendars to describe the variation of association rules over time, where a specific calendar is defined as a collection of time intervals describing some phenomenon. A calendar algebra is used by the method of the invention to permit the user to select or define interesting calendars or specifically, to describe complicated temporal phenomena of interest to the user. The supplied calendars are then processed by the method to determine which calendars hold for which association rules.
In accordance with the invention, there are provided methods for identifying calendric association rules in time-stamped transactional data. The transactional data in a preferred embodiment is assumed to be segmented by the user based on natural time units like hours, days, etc. An exemplary method for discovering calendric association rules first determines all the association rules in all the time units of the data. The method of the invention then analyzes the behavior exhibited by each such resulting association rule over time to discover whether the association rule exhibits any of the temporal behavior specified in any of the user-defined calendars.
Another exemplary method for discovering calendric association rules first determines the behavior of small itemsets (which are components that determine association rules) over the time units to discover the user-defined temporal patterns that the small itemsets exhibit. The method then uses this information to limit the amount of work that needs to be performed to determine the behavior of the larger itemsets. After discovering the behavior of all the relevant itemsets, this method then determines the association rules that exhibit the user-defined patterns or calendars.
REFERENCES:
patent: 5615341 (1997-03-01), Agrawal et al.
patent: 5668988 (1997-09-01), Chen et al.
patent: 5742811 (1998-04-01), Agrawal et al.
patent: 5752020 (1998-05-01), Ando
patent: 5842200 (1998-11-01), Agarwal et al.
patent: 5884305 (1999-03-01), Kleingerg et al.
patent: 5920855 (1999-06-01), Aggarwal et al.
patent: 5943667 (1999-08-01), Aggarwal et al.
patent: 5946683 (1999-08-01), Rastogi et al.
patent: 5983222 (1999-11-01), Morimoto et al.
patent: 6003029 (1999-12-01), Agarwal et al.
patent: 6078955 (2000-06-01), Konno et al.
patent: 6094645 (2000-07-01), Aggarwal et al.
Agarwal et al, “Mining association rules between sets of items in large databases”, ACM SIGMOD pp 207-216, May 1993.*
Klemettinen et al, “Finding intresting rules form large sets of discovered association rules”, ACM CIKM pp 401-407, Mar. 1994.*
Park et al, “Efficient parallel data mining for association rules”, AC< CIKM pp 31-36, Jun. 1995.*
Srikant et al, “Mining quantitaive association rules in large relational tables”, ACM SIGMOD pp 1-12, Apr. 1996.*
Dunkel et al, “Data organization and access for efficeint data mining”, pp 522-529 IEEE, Apr. 1999.*
Shen et al, “New algorithm for efficient mining of association rules” IEEE, pp 234-241, 1999.*
Wur et al, “An effective boolen algorith for mining association rules in large database”, IEEE, pp 179-186, Jun. 1999.*
Han et al, “Mining multiple level association rules in large database”, IEEE, pp 798-805, Apr. 1999.
Mahajan Sameer
Ramaswamy Sridhar
Silberschatz Abraham
Khatri Anil
Lucent Technologies - Inc.
Powell Mark R.
Wolff & Samson
LandOfFree
System and method for discovering calendric association rules does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for discovering calendric association rules, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for discovering calendric association rules will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2561940