📘 Unit II – Concept Description & Association Rule Mining
1. Concept Description
Concept description is about summarizing and characterizing data at a higher level of abstraction.
a) Definition
It provides concise, descriptive summaries of data classes or concepts.
Example: Instead of listing all student records, summarize:
“Average GPA of Computer Science students is 8.2, with 60% male and 40% female.”
b) Data Generalization
Replace low-level data with higher-level concepts.
Example:
o Raw: {“Lucknow”, “Kanpur”, “Varanasi”}
o Generalized: {“Uttar Pradesh”}
Achieved using concept hierarchies (city → state → country).
c) Analytical Characterization
Summarizes the characteristics of a target class.
Example: “Customers who buy sports shoes are mostly aged 18–30, with average income
₹40,000.”
d) Analysis of Attribute Relevance
Identifies which attributes are most important for describing a class.
Example: For predicting “buys computer,” income and education may be more relevant than
zip code.
e) Mining Class Comparisons
Compares two or more classes by summarizing their distinguishing features.
Example:
o “Customers who buy laptops are younger and have higher income than those who
buy desktops.”
2. Statistical Measures in Large Databases
Before mining, we often use statistics to understand data distribution.
a) Measures of Central Tendency
Mean (μ): Average value.
Median: Middle value when sorted.
Mode: Most frequent value.
b) Measures of Dispersion
Range: Max – Min.
Variance (σ²): Average squared deviation from mean.
Standard Deviation (σ): Square root of variance.
IQR (Interquartile Range): Q3 – Q1, robust to outliers.
c) Graphical Displays
Histogram: Frequency distribution.
Boxplot: Shows median, quartiles, and outliers.
Scatter plot: Relationship between two variables.
3. Association Rule Mining
This is the heart of Unit II — discovering interesting relationships among items in large datasets.
a) Definition
An association rule is an implication of the form:
X → Y, where X and Y are itemsets.
Example: {Milk, Bread} → {Butter}
b) Key Metrics
Fraction of transactions containing X ∪ Y.
Support (s):
$$Support(X→Y) = \frac{Transactions(X∪Y)}{Total\ Transactions}$$
Confidence (c):
Probability that Y occurs given X.
$$Confidence(X→Y) = \frac{Transactions(X∪Y)}{Transactions(X)}$$
Lift:
Measures how much more likely Y is bought when X is bought compared to random chance.
$$Lift(X→Y) = \frac{Confidence(X→Y)}{Support(Y)}$$
4. Apriori Algorithm
The most famous algorithm for mining frequent itemsets.
a) Core Idea
Uses the downward closure property:
If an itemset is frequent, all its subsets are frequent.
If an itemset is infrequent, all its supersets are infrequent.
b) Steps
1. Generate candidate itemsets of length k.
2. Prune those whose subsets are not frequent.
3. Count support in the database.
4. Keep frequent itemsets (support ≥ min_support).
5. Repeat until no more frequent itemsets.
c) Example
Transactions:
T1: {Milk, Bread, Butter}
T2: {Milk, Bread}
T3: {Bread, Butter}
T4: {Milk, Butter}
Frequent 1-itemsets: {Milk}, {Bread}, {Butter}
Frequent 2-itemsets: {Milk, Bread}, {Milk, Butter}, {Bread, Butter}
Rule: {Milk, Bread} → {Butter}
o Support = 2/4 = 50%
o Confidence = 2/2 = 100%
5. Types of Association Rules
Single-Dimensional Boolean Rules:
Items are either present or absent.
Example: {Milk} → {Bread}.
Multi-Level Rules:
Rules at different abstraction levels.
Example: {Milk} → {Dairy Products}.
Multi-Dimensional Rules:
Involve multiple attributes.
Example: {Age=20–30, Income=High} → {Buys=Laptop}.
📝 Quick Revision Pointers
Concept Description = summarization, generalization, comparison.
Statistics = mean, median, variance, histograms.
Association Rules = support, confidence, lift.
Apriori = candidate generation + pruning.
Rule Types = Boolean, Multi-level, Multi-dimensional.