DM11 - Frequent Itemsets and Association Rules Flashcards

Question 1

What is the Support of an itemset?

Accepted Answer

The frequency or proportion of transactions in the dataset that contain that specific itemset.

Question 2

What is the Confidence of an association rule $X \Rightarrow Y$?

Accepted Answer

The conditional probability that a transaction containing itemset $X$ also contains itemset $Y$.

Question 3

What is the mathematical formula for the Confidence of the rule $X \Rightarrow Y$?

Accepted Answer

$	ext{Confidence}(X \Rightarrow Y) = \frac{	ext{Support}(X \cup Y)}{	ext{Support}(X)}$

Question 4

What is the Apriori Principle?

Accepted Answer

The rule of anti-monotonicity: if an itemset is frequent, then all of its subsets must also be frequent.

Question 5

How does the Apriori algorithm use the Apriori Principle to prune candidates?

Accepted Answer

If any candidate itemset has a subset that is infrequent, the candidate itself is immediately pruned without needing to scan the database.

Question 6

What are the two main phases in each iteration of the Apriori algorithm?

Accepted Answer

1. Candidate generation (joining frequent itemsets from the previous step) and 2. Support counting (scanning the database to filter valid candidates).

Question 7

In the Apriori algorithm, how are candidate $(k+1)$-itemsets generated?

Accepted Answer

By self-joining the set of frequent $k$-itemsets, specifically combining pairs that share their exact first $k-1$ items.

Question 8

What is a major performance bottleneck of the Apriori algorithm?

Accepted Answer

It requires multiple full scans of the database (one full scan per maximum itemset length) and generates a massive, memory-heavy number of candidates.

Question 9

How does the FP-Growth algorithm fundamentally differ from the Apriori algorithm?

Accepted Answer

It does not use candidate generation;instead, it compresses the database into an FP-tree and recursively mines it.

Question 10

Before building an FP-Tree, how must the items in each transaction be ordered?

Accepted Answer

They must be sorted in descending order of their global frequency (support) to maximize path sharing and compression at the top of the tree.

Question 11

What is the Header Table in an FP-Tree used for?

Accepted Answer

It stores a list of all frequent items along with pointers to their first occurrence in the tree, allowing rapid traversal of specific item paths.

Question 12

In the FP-Growth algorithm, what is a Conditional Pattern Base?

Accepted Answer

A sub-database consisting of all prefix paths in the FP-tree that co-occur with a specific suffix item, used to build smaller conditional trees.

Question 13

How is a Conditional FP-Tree built?

Accepted Answer

By taking a Conditional Pattern Base for a suffix item, recalculating the support of items within it, and building a new, smaller FP-tree that excludes any items that fall below minimum support.

Question 14

What is the absolute worst-case scenario for the size of an FP-Tree?

Accepted Answer

When all transactions in the database are completely unique with no shared items, resulting in a tree that is physically larger than the original database.

Question 15

What is Lift in association rule mining?

Accepted Answer

A metric that measures how much more likely item $Y$ is to be purchased given $X$, compared to $Y$'s baseline probability of being purchased.

Question 16

What does a Lift value greater than 1 indicate?

Accepted Answer

A positive correlation, meaning the occurrence of item $X$ actively increases the likelihood of item $Y$ occurring.

Question 17

What is the minimum support threshold (minsup)?

Accepted Answer

A user-defined parameter that specifies the absolute minimum frequency an itemset must reach to be considered frequent.

Question 18

Why do confidence-based pruning strategies work differently than support-based pruning?

Accepted Answer

Because confidence is not strictly anti-monotone globally, but it *is* anti-monotone when moving items from the left-hand side to the right-hand side of a rule generated from the same frequent itemset.

Question 19

What is the primary goal of frequent itemset mining?

Accepted Answer

To find sets of items that frequently co-occur together in a transactional dataset (e.g., market basket analysis).

Question 20

What is an FP-Tree (Frequent Pattern Tree)?

Accepted Answer

A highly compressed, prefix-tree representation of a transactional database where paths represent overlapping transactions and nodes store item counts.

DM11 - Frequent Itemsets and Association Rules

Card Preview

Related Flashcard Sets

Classical Mechanics - Newtonian Laws & Energy Conservation

General Pharmacology - Pharmacodynamics & Pharmacokinetics

Neuroscience Fundamentals - Brain Anatomy & Neurotransmitters

Cell Biology - Cellular Structure & Function