📘 Data Mining & Warehousing Unit 5

🎯 Unit 5 Overview

Unit 5 covers unsupervised learning techniques such as clustering and association rule mining. It includes hierarchical algorithms, partitional algorithms, clustering large databases, BIRCH, DBSCAN, CURE, Apriori algorithm and FP-Growth algorithm.

🔗 Clustering

Clustering is an unsupervised learning technique used to group similar data objects together. Objects inside one cluster are similar to each other and different from objects of other clusters.

Example

Customers can be grouped based on buying behavior such as low buyers, medium buyers and high buyers.

Applications

• Customer segmentation
• Image segmentation
• Document grouping
• Market analysis
• Fraud detection
• Social network analysis

📂 Types of Clustering Algorithms

🌳 Hierarchical Clustering

Hierarchical clustering builds a hierarchy of clusters. It represents clusters using a tree-like diagram called dendrogram.

Types

• Agglomerative: Bottom-up approach. Each object starts as separate cluster and clusters are merged step by step.
• Divisive: Top-down approach. All objects start in one cluster and are divided step by step.

Advantages

• No need to specify number of clusters initially
• Easy to understand using dendrogram
• Useful for small datasets

Limitations

• Computationally expensive for large data
• Once merge or split is done, it cannot be undone

📊 Partitional Clustering

Partitional clustering divides data into a fixed number of clusters. Each data object belongs to one cluster.

K-Means Algorithm

1. Select number of clusters K.
2. Choose K initial cluster centers.
3. Assign each data object to nearest cluster center.
4. Recalculate cluster centers.
5. Repeat until clusters become stable.

Advantages

• Simple and fast
• Works well for large datasets
• Easy to implement

Limitations

• Need to choose K in advance
• Sensitive to outliers
• Initial centroid selection affects result

⚖️ Hierarchical vs Partitional Clustering

🏢 Clustering Large Databases

Large databases contain huge amounts of data, so normal clustering algorithms may become slow. Special scalable algorithms are used for clustering large datasets.

Requirements

• Scalability
• High speed
• Ability to handle noise
• Minimum memory usage
• Support for high dimensional data

🌿 BIRCH Algorithm

BIRCH stands for Balanced Iterative Reducing and Clustering using Hierarchies. It is designed for clustering very large datasets.

Features

• Uses clustering feature tree
• Works efficiently on large databases
• Reduces data size before clustering
• Memory efficient
• Good for incremental clustering

Steps

1. Scan data and build clustering feature tree.
2. Compress data into smaller summaries.
3. Apply clustering algorithm on leaf entries.
4. Refine clusters if required.

🧭 DBSCAN Algorithm

DBSCAN stands for Density-Based Spatial Clustering of Applications with Noise. It forms clusters based on density of data points.

Important Terms

• Epsilon: Radius around a point.
• MinPts: Minimum points required to form dense region.
• Core Point: Point having at least MinPts within epsilon radius.
• Border Point: Point near a core point but not core itself.
• Noise Point: Point that does not belong to any cluster.

Advantages

• Finds arbitrary shaped clusters
• Detects noise and outliers
• No need to specify number of clusters

🎯 CURE Algorithm

CURE stands for Clustering Using Representatives. It uses representative points to identify clusters and can handle non-spherical cluster shapes.

Features

• Uses multiple representative points
• Handles outliers better
• Works with complex cluster shapes
• Suitable for large datasets with sampling

🛒 Association Rule Mining

Association rule mining finds relationships among items in large datasets. It is commonly used in market basket analysis.

Example

If customers buy bread and butter together, then store can recommend jam also.

Rule Format

A → B means if item A is purchased, item B is likely to be purchased.

📌 Support, Confidence and Lift

🧮 Apriori Algorithm

Apriori algorithm is used to find frequent itemsets and generate association rules. It works on the principle that all subsets of a frequent itemset must also be frequent.

Steps

1. Set minimum support and confidence.
2. Find frequent 1-itemsets.
3. Generate candidate 2-itemsets.
4. Remove itemsets below minimum support.
5. Repeat for larger itemsets.
6. Generate association rules from frequent itemsets.

Advantages

• Simple and easy to understand
• Useful for market basket analysis
• Finds frequent itemsets systematically

Limitation

• Generates many candidate itemsets
• Requires multiple database scans
• Can be slow for large datasets

⚡ FP-Growth Algorithm

FP-Growth stands for Frequent Pattern Growth. It finds frequent itemsets without generating large candidate sets like Apriori.

Steps

1. Scan database and find frequent items.
2. Sort frequent items by frequency.
3. Build FP-tree.
4. Generate frequent patterns from FP-tree.

Advantages

• Faster than Apriori
• No candidate generation
• Requires fewer database scans
• Efficient for large datasets

⚖️ Apriori vs FP-Growth

⭐ Important Questions

1. Define clustering and explain its applications.
2. Explain hierarchical clustering and its types.
3. Explain partitional clustering with K-Means algorithm.
4. Differentiate between hierarchical and partitional clustering.
5. Explain clustering large databases.
6. Explain BIRCH algorithm.
7. Explain DBSCAN algorithm with important terms.
8. Explain CURE algorithm.
9. Explain association rule mining with support and confidence.
10. Explain Apriori and FP-Growth algorithms.

🔥 Last Minute Revision

• Clustering groups similar objects.
• Hierarchical clustering uses dendrogram.
• Partitional clustering uses fixed K clusters.
• K-Means is fast but needs K value.
• BIRCH uses clustering feature tree.
• DBSCAN is density-based and detects noise.
• CURE uses representative points.
• Association rule mining finds item relationships.
• Apriori generates candidate itemsets.
• FP-Growth uses FP-tree and is faster than Apriori.

🔗 Related Links