association rule learning
In plain wordsFinding 'if this, then often that' patterns in large records of transactions, such as noticing that shoppers who buy pasta and tomatoes often buy parmesan too.
An unsupervisedunsupervised learning, n.: Machine learning without answer keys: the computer looks at unlabeled data and finds structure on its own, such as groups of similar customers or the main ways in which data vary. data-mining technique that searches a database of transactions, such as shopping baskets, web sessions or diagnoses, for implications of the form X ⇒ Y between sets of items that tend to occur together. Rules are scored by support (the fraction of transactions containing both X and Y), confidence (the fraction of transactions containing X that also contain Y) and lift (confidence divided by the overall frequency of Y, so values above 1 indicate association beyond chance). Mining proceeds in two stages: find all itemsets whose support exceeds a minimum, then generate rules whose confidence exceeds a minimum. The Apriori algorithm prunes the search using the fact that every subset of a frequent itemset must itself be frequent; FP-growth avoids generating candidates by compressing transactions into a prefix tree. Rules describe co-occurrence, not causation, and the large rule sets produced must be filtered by interestingness measures.
Mining the pharmacy baskets turned up {sunscreen, after-sun} ⇒ {aloe gel} with a lift of 4.2.
Origin
Petr Hájek, Ivan Havel and Metoděj Chytil described rules of this kind in their GUHA method in 1966. The modern formulation was popularized by Rakesh Agrawal, Tomasz Imieliński and Arun Swami at SIGMOD 1993, followed by the Apriori algorithm of Agrawal and Ramakrishnan Srikant (VLDB 1994); Jiawei Han, Jian Pei and Yiwen Yin introduced FP-growth at SIGMOD 2000.
Usage note
The often-told 'beer and diapers' story traces to a 1992 analysis of drugstore sales that found both bought in the early evening; how much of the popular version is true is disputed, and the store reportedly never moved the products together.
Related
- unsupervised learningunsupervised learning, n.: Machine learning without answer keys: the computer looks at unlabeled data and finds structure on its own, such as groups of similar customers or the main ways in which data vary.
- recommender systemrecommender system, n.: Software that guesses which songs, products, posts or jobs you are most likely to want and shows those first, as when a video app lines up the next clip or a shop suggests an add-on.
- clusteringclustering, n.: Automatically sorting things into groups of similar items when nobody has said in advance what the groups should be, like sorting a drawer of odd socks into piles by color and size.
- collaborative filteringcollaborative filtering, n.: Recommending things based on what people with similar tastes liked, without needing to know anything about the things themselves, as in 'people who bought this also bought…'.
- data sciencedata science, n.: The practice of collecting, cleaning, analyzing and interpreting data, using statistics, programming and machine learning, to answer questions and guide decisions.
Sources
- Agrawal, R., Imieliński, T. & Swami, A. (1993). Mining Association Rules between Sets of Items in Large Databases. Proc. ACM SIGMOD 1993.
- Agrawal, R. & Srikant, R. (1994). Fast Algorithms for Mining Association Rules. Proc. 20th International Conference on Very Large Data Bases (VLDB).
- Hájek, P., Havel, I. & Chytil, M. (1966). The GUHA Method of Automatic Hypotheses Determination. Computing 1.
Mentioned in
data miningdata mining, n.: Searching large collections of data with computers to discover useful patterns, such as products often bought together or signs that a transaction may be fraudulent., rule-based systemrule-based system, n.: A computer system that makes decisions by following a list of 'if… then…' rules written by people, rather than by learning from examples.