 |
|
|
|
|
|
 Title: |
US5794209:
System and method for quickly mining association rules in databases
[ Derwent Title ]
|
| Country: |
US United States of America
|
| |
| Inventor: |
Agrawal, Rakesh; San Jose, CA
Srikant, Ramakrishnan; San Jose, CA
|
| Assignee: |
International Business Machines Corporation, Armonk, NY
other patents from INTERNATIONAL BUSINESS MACHINES CORPORATION (280070) (approx. 44,393)
News, Profiles, Stocks and More about this company
|
| Published / Filed: |
1998-08-11
/ 1995-03-31
|
| Application Number: |
US1995000415006
|
| IPC Code: |
Advanced:
G06F 17/30;
G06Q 10/00;
G06Q 30/00;
G06Q 50/00;
G07G 1/12;
Core:
more...
IPC-7:
G06F 17/60;
|
| ECLA Code: |
G06Q30/00A;
|
| U.S. Class: |
Current:
705/010;
707/005;
709/200;
Original:
705/010;
707/005;
|
| Field of Search: |
395/600,210
364/403
705/010
707/3;5
|
| Priority Number: |
| 1995-03-31 |
US1995000415006 |
|
| Abstract: |
A system and method for discovering consumer purchasing tendencies includes a computer-implemented program which identifies consumer transaction itemsets that are stored in a database and which appear in the database a user-defined minimum number of times, referred to as minimum support. Then, the system discovers association rules in the itemsets by comparing the ratio of the number of times each of the large itemsets appears in the database to the number of times particular subsets of the itemset appear in the database. When the ratio exceeds a predetermined minimum confidence value, the system outputs an association rule which is representative of purchasing tendencies of consumers.
|
| Attorney, Agent or Firm: |
Gray Cary Ware Freidenrich ;
|
| Primary / Asst. Examiners: |
Cosimano, Edward R.; Bainbridge, Barton L.
|
| Maintenance Status: |
CC Certificate of Correction issued
|
| INPADOC Legal Status: |
Show legal status actions
Family Legal Status Report
|
| Parent Case: |
CROSS REFERENCE TO RELATED APPLICATIONS
This application contains material related to the following co-pending U.S. Patent Applications, which are commonly assigned with this application.
U.S. patent application Ser. No. 08/227,428, now U.S. Pat. No. 5,664,171, filed Apr. 14, 1994, for "SYSTEM AND METHOD FOR QUERY OPTIMIZATION USING QUANTILE VALUES OF A LARGE UNORDERED DATA SET"; and
U.S. patent application Ser. No. 08/398,640, filed Mar. 3, 1995, now abandoned, for "SYSTEM AND METHOD FOR MINING SEQUENTIAL PATTERNS IN A LARGE DATABASE".
The above-referenced U.S. patent application Ser. No. 08/398,640, is incorporated herein by reference.
|
| Designated Country: |
DE FR GB
|
| Family: |
Show 13 known family members
|
First Claim:
Show all 19 claims |
We claim:
1. A method executable by a computer having a computer program storage device readable by the computer and a program means on the program storage device and including instructions executable by the computer for performing method steps identifying association rules in itemsets in transactions which are stored in a database, each itemset characterized by one or more items, the method comprising:
- entering an itemset into a set of large itemsets when the number of times the itemset is present in the database exceeds a predefined minimum support value;
- concatenating itemsets in the set of large itemsets in accordance with a predetermined concatenation regime to generate a next set of candidate large itemsets and discarding all candidate large itemsets whose subsets are not large itemsets;
- comparing each itemset in the next set of candidate large itemsets to the itemsets in the database to determine the number of times the candidate large itemset is present in the database;
- entering a candidate large itemset into a next forward set of large itemsets only when the number of times the candidate large itemset is present in the database is greater than the minimum support value;
- for at least some of the itemsets in the next forward set of large itemsets, determining the number of times selected subsets of the itemsets appear in the database; and
- outputting an association rule when the ratio of the number of times a selected subset having a plurality of items appears in the database to the number of times the associated itemset appears in the database exceeds a predetermined minimum confidence value and thereby satisfies a minimum confidence constraint.
|
| Background / Summary: |
Show background / summary
|
| Drawing Descriptions: |
Show drawing descriptions
|
| Description: |
Show description
|
| Forward References: |
Show 38 U.S. patent(s) that reference this one
|
|
|
|
|
|
|
| Foreign References: |
None
|
| Other Abstract Info: |
DERABS G96-435889
|
| Other References: |
Agrawal et al., "Mining Association Rules between Sets of Items in Large Databases", Proceedings of the 1993 ACM SIGMOD Conference, May 1993.
R. Agrawal et al., "Mining Association Rules Between Sets of Items in Large Databases", PROC. 1993 ACM SIGMOD Conf., pp. 207-216, 1993.
R. Agrawal et al., "Fast Algorithms for Mining Association Rules", Proceedings of the 1994 VLDB Conference, pp. 487-499, 1994.
M. Houtsma et al., "Set-Oriented Mining for Association Rules in Relational Databases", Proc. 11th Conference on Data Engineering, pp. 25-33, 1995.
H. Mannila et al., "Improved Methods for Finding Association Rules", Pub. No. C-1993-65, 20 pages, Univ. Helsinki, 1993.
J.J. Bernardo et al., Sequencing Rules for Productivity Improvements, Pub. Decis. Sci., V. 22, #3, pp. 620-634, Jul.-Aug., 1991.
(15 pages)
Cited by 2 patents
[ISI abstract]
M.D. Merrill, et al., Instructional Transaction Shells: Responsibilities, Methods, and Parameters, Pub. Educ. Technol. V. 32, #2, pp. 5-25, Feb. 1992.
W.D. Hopkins, et al., "Sequential Pattern Recognition Machine", IBM TDB, vol. 16, No. 1, pp. 97-99, 6/73.
H. Manilla et al., "Dependency Interference", Proc. 13th VLDB Conf., pp. 155-158, Brighton, 1987.
O. Klaassen, "Modeling Data Base Reference Behavior", Computer Performance Evaluation, G. Balbo, et al, eds, pp. 47-60, 1992.
G. Piatetsky-Shapiro, "Discovery, Analysis, and Presentation of Strong Rules", Knowledge Discovery in Databases, G. Piatelsby-Shapiro et al., eds., pp. 231-248, Menlo Park, 1991.
H. Mannila et al., "Efficient Algorithms for Discovering Association Rules", 1994, pp. 181-192, AAAI-94 Workshop on Knowledge Discovery in Databases.
R. Agrawal et al., "Quest: A Project on Database Mining", 1994, p. 514, Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data.
|
|
 Nominate this for the Gallery...
|
|
