Data mining -- Introduction to the basis of association analysis (Part 1)

One 、 Premise introduction ：

Beer and diapers ：

In American families with babies , Usually the mother looks after the baby at home , Young father Go to the supermarket to buy diapers in person . While my father was buying diapers , They often buy for themselves Buy beer , In this way, beer and diapers, two seemingly unrelated goods, often The phenomenon of appearing in the same shopping basket . If the young father can only buy one of two items in the store, he is likely to give up shopping and go to another store , Until you can Buy beer and diapers at the same time . Wal Mart has discovered this unique phenomenon , Start to try to put beer and diapers in the same area in the store so that young fathers can find these two products at the same time , And finish shopping quickly , So as to obtain a good sales revenue of goods , This is it. “ Beer and diapers ” The origin of the story . The baby said ：“ After drinking beer, I change diapers faster ”！！

Two 、 Basic knowledge points

1. Association rules ：

In a typical case , Considered interesting , If it meets the minimum confidence threshold and the minimum support threshold . These thresholds are set by experts .

Two measures of rule interest ：

Support （support）、 Degree of confidence （confidence）

2. Support （support）、 Degree of confidence （confidence） The calculation method of the relationship with the support count is as follows ：

3. The mining process of association rules ：

（1） Find all frequent itemsets ： The number of occurrences of each itemset must be greater than or equal to the minimum support count .

（2） Strong association rules are generated from frequent itemsets （ Strong association rules are the rules that must meet the minimum support and minimum confidence ）

（3） Closed frequent itemsets ： If X It's frequent , And there is no true hyperitemset Y send Y And X stay D Has the same support count in .

（4） Maximal frequent itemsets ： If X It's frequent , And there is no superitem set Y bring X Y Ì also Y stay D Is frequent .

A priori principle （ Super easy to use ）： All non empty subsets of frequent itemsets must also be frequent Of . conversely , All supersets of infrequent itemsets must also be infrequent .

3、 ... and 、Apriori Algorithm

Apriori The algorithm is Agrawal and R.Srikant On 1994 Put forward in , Mining frequent items for Boolean association rules The original algorithm of set

1. The process ：

Apriori The algorithm is an iterative method of layer by layer search ： First , Scan database , Accumulate the count of each item , And collect the items that meet the minimum support , Find out how often 1 Itemsets L1; then , Use L1 Find out how often 2 Itemsets L2, Use L2 find L3, … Go on like this , Until you can't find frequent k Itemsets .

Example of manual calculation ：