System and method for discovering calendric association rules

• US 6,236,982 B1
• Filed: 09/14/1998
• Issued: 05/22/2001
• Est. Priority Date: 09/14/1998
• Status: Expired due to Term

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Mahajan, Sameer, Silberschatz, Abraham, Ramaswamy, Sridhar
• Primary Examiner(s): Powell, Mark R.
• Assistant Examiner(s): Khatri, Anil
• Application Number:
  US09/152,770
• Time in Patent Office: 981 Days
• Field of Search: 706/45, 706/46, 706/47, 707/6, 707/100, 707/102, 707/200, 707/1, 707/104
• US Class Current: 706/45
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

A system and method for determining calendric association rules are provided. 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. In accordance with the invention, there is provided a method for identifying calendric association rules in transactional data with time stamped data items. In one exemplary embodiment, the method identifies large itemsets in each time unit, where a large itemset is an itemset that occurs in the transactions more than a given threshold. The method then identifies association rules of the form X—Y from the large itemsets by determining if a requisite support for the itemset XY and a given confidence threshold (ratio of (support of XY)/(support of X)) has been satisfied. Calendric association rules are then generated by examining identified association rules to determine which ones exhibit the temporal patterns specified by given calendars. In another embodiment, the method identifies large itemsets in each time unit, where an itemset includes at least one item type. The method then identifies calendars that belong to the large itemsets. Potential calendars for increasingly larger item type itemsets are generated by using previously identified calendars. Support values are calculated to determine which potential calendars actually belong to the itemsets and this is then used to determine what potential calendar association rules exist. The potential calendar association rule information and support values are used to determine which potential calendars actually belong to association rules.

Claims

1. A method for identifying calendric association rules in transactions with time-stamped data items, comprising the steps of:

identifying a plurality of time intervals as constituting a calendar of interest;

identifying large itemsets in each time interval, where a large itemset is an itemset that occurs in the transactions at least as frequently as a preselected support threshold;

identifying association rules from said large itemsets by determining if said preselected support and a confidence threshold has been satisfied; and

generating calendric association rules by examining identified association rules to determine which ones exhibit temporal patterns as specified by a given calendar.

2. The method according to claim 1, wherein said association rules are of the form X→

Y.

3. The method according to claim 2, wherein said preselected support is for a XY itemset.

4. The method according to claim 3, wherein said given confidence threshold is a ratio of support of Itemset XY over support of Itemset X.

5. The method according to claim 1, wherein said confidence threshold is a user defined variable.

6. The method according to claim 1, wherein said preselected support is a user defined variable.

7. The method according to claim 1, wherein said given calendars are user defined.

8. The method according to claim 1, wherein said given calendars are selected by a user from a list of calendars.

9. The method according to claim 1, wherein said given calendars are selected by a user using calendar algebra to define interesting calendars.

10. The method according to claim 1, further including the steps of:

using said large itemsets and said preselected support to ascertain which calendars actually belong to said large itemsets;

using ascertained calendars to determine what potential calendar association rules exist; and

using potential calendar association rule information and computed support values to determine which of said calendars actually belong to association rules.

11. A method for identifying calendric association rules in transactions with time-stamped data items, comprising the steps of:

identifying a plurality of time intervals as constituting a calendar of interest;

identifying large itemsets in each time interval, where a large itemset is an itemset that occurs in the transactions at least as frequently as a preselected support threshold and an itemset includes at least one item type;

identifying calendars that belong to said large itemsets;

generating potential calendars for itemsets including additional item types by using previously identified itemsets and their calendars;

computing support for said itemsets in each time unit to determine which of said potential calendars actually belong to said itemsets;

using said itemsets and associated potential calendars to determine what potential calendric association rules exist; and

using potential calendar association rule information and computed support values to determine which of said potential calendars actually belong to association rules.

12. The method according to claim 11, wherein a calendar is said to belong to said itemset if said itemset is large during every time unit contained in said calendar.

13. The method according to claim 11, wherein said step of generating increases by one the number of item types in each itemset.

14. The method according to claim 11, further including the step of restricting itemsets and time units for whom support has to be computed by using said potential calendars.

15. The method according to claim 11, further including the step of eliminating potential calendars from consideration if it is determined during support calculation that a potential calendar cannot belong to a certain itemset.

16. A system for identifying calendric association rules from transaction data having time-stamped items, comprising:

a computing device including memory for storing said transaction data;

said computing device operable to identify a plurality of time intervals as constituting a calendar of interest;

said computing device further operable to identify large itemsets in each time unit, where a large itemset is an itemset that occurs in the transactions at least as frequently as a preselected threshold;

said computing device further operable to identify association rules from said large itemsets by determining if a preselected support and a confidence threshold has been satisfied; and

said computing device further operable to generate calendric association rules by examining identified association rules to determine which ones exhibit temporal patterns as specified by given calendars.

17. The system according to claim 16, wherein:

said association rules are of the form X→

Y;

said preselected support is for a XY itemset; and

said confidence threshold is a ratio of support of Itemset XY over support of Itemset X.

18. The system according to claim 16, further including an interface for identifying said given calendars from a plurality of predefined calendars.

19. The system according to claim 18, wherein said interface is further operable to input a value for said confidence threshold and said preselected threshold.

20. The system according to claim 16, further including an interface for using calendar algebra to define interesting calendars as said given calendars.

21. The system according to claim 16, wherein:

said computing device is further operable to use said large itemsets and said preselected support to ascertain which calendars actually belong to said large itemsets;

said computing device is further operable to use ascertained calendars to determine what potential calendar association rules exist; and

said computing device is further operable to use potential calendar association rule information and computed support values to determine which of said calendars actually belong to association rules.

22. A system for identifying calendric association rules in transactional data with time-stamped data items, comprising:

a processor having a memory, said memory storing said transactional data;

said processor operable to identify a plurality of time intervals as constituting a calendar of interest;

said processor further operable to identify large itemsets in each time unit, where a large itemset is an itemset that occurs in the transactions at least as frequently as a preselected support threshold and an itemset includes at least one item type;

said processor further operable to identify calendars that belong to said large itemsets;

said processor further operable to generate potential calendars for increasingly larger item type itemsets by using previously identified calendars;

said processor further operable to compute support for said itemsets in each time unit to determine which of said potential calendars actually belong to said itemsets;

said processor further operable to use said itemsets and associated potential calendars to determine what potential calendar association rules exist; and

said processor further operable to use potential calendric association rule information and computed support values to determine which of said potential calendars actually belong to association rules.

23. The system according to claim 22, wherein a calendar is said to belong to said itemset if said itemset is large during every time unit contained in said calendar.

24. The system according to claim 22, wherein said processor is further operable to restrict itemsets and time units for whom support has to be computed by using said potential calendars.

25. The system according to claim 22, wherein said processor is further operable to eliminate potential calendars from consideration if it is determined during support calculation that a potential calendar cannot belong to a certain itemset.