Bài 3: Nhập môn Khai phá dữ liệu và máy học - IT61

Summary

The lesson introduces association rule mining, a data-mining method for discovering which items tend to occur together in transaction data. A common application is market-basket analysis: if a customer buys certain products, the system can suggest other products they may also want.

Core Concepts

• Transaction database: A collection of transactions, each recording a group of items bought together.
• Itemset: A set of one or more items. An itemset containing k items is called a k-itemset.
• Association rule: A rule written as X → Y, where X is the premise and Y is the consequence. X and Y are non-empty, disjoint itemsets. The rule expresses a tendency—not a guarantee—that transactions containing X also contain Y.
• Frequent itemset: An itemset whose support meets or exceeds a chosen minimum-support threshold.
• Strong association rule: A rule that meets the required support and confidence thresholds.

Association-rule mining generally has two stages:

1. Find frequent itemsets using a minimum-support threshold.
2. Generate rules from those itemsets and retain the rules that meet a minimum-confidence threshold.

Measures for Evaluating Rules

For a rule X → Y:

• Support measures how often X and Y occur together in the full database: support(X → Y) = support(X ∪ Y) = count(X ∪ Y) / total transactions

• Confidence measures how often Y occurs among transactions that contain X: confidence(X → Y) = support(X ∪ Y) / support(X) Higher confidence indicates that the rule is more reliable in the observed data.

• Lift compares the rule’s confidence with the baseline frequency of Y: lift(X → Y) = confidence(X → Y) / support(Y)

  • Lift > 1: X and Y are positively associated.
  • Lift = 1: They are statistically independent according to this measure.
  • Lift < 1: They are negatively associated.

Apriori Algorithm

Apriori finds frequent itemsets level by level, using a key pruning principle:

• Every subset of a frequent itemset must also be frequent.
• If an itemset is infrequent, any larger itemset containing it must also be infrequent.

The main procedure is:

1. Count each individual item and keep those meeting minimum support to form L1.
2. Use the frequent itemsets at level k to generate candidate itemsets of size k + 1.
3. Count each candidate’s support in the transaction database.
4. Remove candidates below minimum support to produce the next frequent-itemset level.
5. Repeat until no new frequent itemsets remain.
6. For each frequent itemset containing at least two items, generate rules by splitting it into a premise and consequence.
7. Calculate rule confidence and keep rules that meet minimum confidence.

The lecture walks through a small transaction example using minimum support of 40%, equivalent to appearing in at least two of five transactions. It demonstrates filtering candidates at successive itemset sizes.

FP-Growth Algorithm

FP-Growth also finds frequent itemsets, but avoids repeatedly generating candidate itemsets—a limitation of Apriori.

The main procedure is:

1. Count item frequencies and discard items below minimum support.
2. Order the remaining items by frequency.
3. Reorder each transaction using that frequency order.
4. Insert the ordered transactions into an FP-tree, combining shared prefixes and tracking counts.
5. Starting with less frequent items, form conditional pattern bases and corresponding conditional FP-trees.
6. Mine those conditional trees to obtain frequent itemsets.
7. Generate and filter association rules using confidence, as with Apriori.

The lecture presents FP-Growth as especially useful when transactions share many items, because the tree compresses repeated patterns.

Python Implementation with mlxtend

The lesson demonstrates using the mlxtend library to implement both algorithms:

• Encode transactions as one-hot data using a transaction encoder.
• Run apriori or fpgrowth with a minimum-support value to obtain frequent itemsets.
• Pass those itemsets to association_rules, selecting confidence as the filtering measure and specifying a minimum-confidence threshold.
• Inspect results such as the premise, consequence, support, confidence, and lift.

The example uses a minimum support of 0.4 and illustrates filtering rules with a minimum confidence of 0.8.

Saving Rules and Using Them for Recommendations

Association rules can be applied in a product-recommendation workflow:

1. Save the generated rules, such as to a CSV file, for later use.
2. Read the saved rules into a data frame when the application runs.
3. Accept the items in a customer’s current transaction.
4. Compare the entered items with the premises of the rules.
5. When a premise matches, add its consequence items to a recommendation set, avoiding duplicates.
6. Display the recommendations, or report that no matching rule was found.

The demonstration uses sample transactions and saved rules to show how entering different products can produce recommendations. The lesson closes by emphasizing the broader workflow: mine patterns from data, then put the resulting rules into a practical application.

Speakers and Sources Featured

• Le Huu Dung — instructor and speaker.
• Course reference material #2 — identified in the lecture as the primary theoretical reference; its title is not given in the subtitles.
• Apriori research — cited in the lecture as a 1994 proposal; the authors’ names are garbled in the subtitles.
• FP-Growth research — the lecture cites a paper titled “Mining Frequent Patterns Without Candidate Generation”; the author names are unclear in the subtitles.
• Software and tools mentioned: Python, mlxtend, pandas, and scikit-learn.