UNIT 2: DATA WAREHOUSING & MINING - EXAM-FOCUSED SHORT NOTES

I. DATA PREPROCESSING & PREPARATION

Data Cleaning

Definition: The process of detecting and correcting (or removing) corrupt, inaccurate, or irrelevant data from a dataset. It is a crucial first step in the KDD process to ensure data quality and improve mining accuracy.

Key Techniques:

[!TIP] Exam Focus: Be ready to define each technique with a small example (e.g., "For a missing age, impute with median age of the department").

Data Transformation

Goal: Convert data into a suitable form for mining.

Data Reduction & Discretization

Need: Reduce data volume/complexity while maintaining integrity, to improve mining efficiency.

Strategies:

• Row Reduction: Sampling, feature selection.

• Column Reduction: Feature selection (filter/wrapper/embedded methods), attribute construction (consolidates columns).

Discretization Methods:

• Binning: As above (unsupervised).

• Histogram Analysis: Partition by equal-frequency or equal-width bins.

• Clustering: Use cluster centroids as discrete boundaries.

• Decision Tree: Use tree to partition numeric attributes (supervised).

II. DATA WAREHOUSE FUNDAMENTALS & DESIGN

Data Warehouse (DW) Definition & Characteristics

Definition: A subject-oriented, integrated, time-variant, non-volatile collection of data, organized to support decision-making.

DW Architecture & Components

Three-Tier Architecture:

1. Bottom Tier: Data Sources → Staging Area (ETL processing) → DW Database (relational/ multidimensional DBMS).

2. Middle Tier: OLAP Server (MOLAP/ROLAP/HOLAP). Provides multidimensional view.

3. Top Tier: Front-end Tools (query/reporting, analysis, data mining tools).

ETL Process (Core of DW):

• Extract: Pull data from heterogeneous sources.

• Transform: Clean, integrate, aggregate, derive.

• Load: Populate the DW (full/ incremental refresh).

DW Implementation Techniques & Strategies

• Data Marts: Subset of a DW focused on a specific business line.

  • Dependent: Built from an existing DW (consistent, integrated).

  • Independent: Built directly from operational sources (may cause inconsistency).

  • Hybrid: Combination of both.

• Vertical Partitioning: Splitting a table by columns.

  • Process: Identify frequently accessed columns (hot) vs. infrequent (cold). Store hot columns in fast-access storage, cold in slower/cheaper storage.

  • Goal: Improve I/O performance for common queries.

Multidimensional Data Modeling & Schemas

Core Concept: Data represented as a data cube with dimensions (perspectives) and measures (quantitative facts).

[!TIP] Exam Tip: Be prepared to draw and label a simple star schema and snowflake schema for a "Sales" subject area.

III. OLAP (ONLINE ANALYTICAL PROCESSING)

OLAP vs. OLTP

OLAP Operations (On a Data Cube)

1. Roll-up (Drill-up): Aggregate data up the dimension hierarchy (e.g., City → Country).

2. Drill-down: Reverse of roll-up; go to finer granularity (e.g., Year → Quarter → Month).

3. Slice-and-dice: Slice: Fix one dimension (e.g., Time="2024"). Dice: Select a sub-cube by specifying ranges on multiple dimensions.

4. Pivot (Rotate): Reorient the cube to view data from a different perspective (swap rows/columns).

OLAP Architectures & Servers

[!DIAGRAM: ROLAP] Search: "ROLAP architecture diagram star schema mapping relational tables"

Data Cube Computation

Concept: Pre-computing and storing materialized views (aggregated cuboids) to speed up OLAP queries.

Computation Strategies:

1. Full Materialization: Compute all possible cuboids. Fastest query response, highest storage cost.

2. Partial Materialization: Compute a subset of cuboids based on query workload.

   • Lattice Traversal: View the set of cuboids as a lattice. Use top-down (from apex) or bottom-up (from base) computation.

   • Indexing: Use bitmap index (fast for low-cardinality dimensions) or join index (pre-joins between fact and dimension tables) to speed up ROLAP.

IV. DATA MINING: INTRODUCTION & FRAMEWORK

KDD vs. Data Mining:

• KDD (Knowledge Discovery in Databases): The overall process of extracting knowledge from data (steps: Selection, Preprocessing, Transformation, Data Mining, Interpretation/Evaluation).

• Data Mining: The core step in KDD; the application of algorithms to discover patterns/models from data.

Data Mining Task Primitives (Specify a DM task):

1. Task-relevant data: Subset of database (relevant attributes, tuples).

2. Background knowledge: Domain knowledge, constraints, taxonomies (ontologies).

3. Interestingness measures: Thresholds for support, confidence, correlation, accuracy.

4. Presentation/Visualization: How results are displayed (rules, trees, graphs).

Role of Data Mining Engine: The "black box" that executes the chosen data mining algorithms (e.g., Apriori, ID3, k-means) on the prepared data.

Pros and Cons:

Types of Data for Mining:

• Relational, Transactional, Data Warehouses, Flat Files.

• Advanced: Data Streams, Graphs, Spatial/Temporal, Text, Web.

V. ASSOCIATION RULE MINING

Basic Concepts

• Market Basket Analysis: Finding associations between items purchased together.

• Itemset: Set of items (e.g., {Milk, Bread}).

• Support (σ): Fraction of transactions containing the itemset.

$$ \text{support}(X) = \frac{\text{transactions containing } X}{\text{total transactions}} $$

• Confidence (c): Conditional probability that Y is bought given X is bought.

$$ \text{confidence}(X \rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X)} $$

• Frequent Itemset: Itemset with support ≥ min_sup threshold.

• Strong Rule: Rule with support ≥ min_sup and confidence ≥ min_conf.

Apriori Algorithm (Step-by-Step)

Core Principle (Apriori Property): All subsets of a frequent itemset must also be frequent. (Used for pruning).

Algorithm:

1. Find Frequent Itemsets (L_k):

   • k=1: Scan DB, count items, find L_1 (frequent 1-itemsets).

   • k>1: Candidate Generation (C_k): Join L_{k-1} with itself (self-join) to create candidate k-itemsets.

   • Prune: Remove candidates with any (k-1)-subset not in L_{k-1} (using Apriori property).

   • Scan DB, count support of C_k, find L_k (candidates with support ≥ min_sup).

   • Repeat until L_k is empty.

2. Generate Rules: For each frequent itemset l (size ≥ 2), generate all non-empty subsets. For each subset s, if confidence(s → (l-s)) ≥ min_conf, output rule.

[!EXAMPLE] Example: For min_sup=0.5, min_conf=0.8, DB: {A,B,C}, {A,B}, {A,C}, {B,C}, {A,B,C}. L1={A:4, B:4, C:4} → L2 candidates: {A,B}, {A,C}, {B,C}. Support all=0.8? {A,B}:3/5=0.6, {A,C}:2/5=0.4 (pruned), {B,C}:3/5=0.6. L2={{A,B},{B,C}}. Rules: {A,B}→∅ (none). {B,C}→A: conf=2/3=0.66 <0.8 (reject). {A,B}→C: conf=2/3=0.66 (reject). {B,C}→A: same. No strong rules found.

FP-Growth Algorithm

Idea: Avoid candidate generation & multiple scans (like Apriori). Use a compressed representation: FP-tree (Frequent Pattern Tree).

Steps:

1. Scan DB once: Find L (frequent items), order by descending support.

2. Build FP-tree:

   • Sort each transaction's items by order in L.

   • Insert sorted transaction into tree, sharing common prefixes. Nodes store item name & count.

   • Maintain header table linking all nodes of same item.

3. Mine FP-tree (Recursive):

   • For each item in L (starting from least frequent), construct its conditional pattern base (prefix paths to that item).

   • Build conditional FP-tree from conditional pattern base.

   • Recursively mine conditional FP-tree, appending the item to patterns.

[!TIP] Key Advantage: FP-Growth is often faster than Apriori as it uses a compact tree structure and avoids costly candidate generation.

Improving Efficiency of Apriori

1. Hashing: Use hash table on k-itemsets during candidate generation to prune early.

2. Transaction Reduction: Remove transactions that don't contain any frequent items from future scans.

3. Partitioning: Partition DB, find local frequent itemsets (must be globally frequent), then global scan.

4. Sampling: Mine a random sample; may miss some global frequent itemsets (use lower min_sup).

5. Dynamic Item Set Counting: Add candidate itemsets dynamically during scan (not at start of each pass).

Advanced Association Concepts

• Boolean Association Rule Mining: For categorical/boolean attributes. Convert attributes to boolean items (e.g., Age=Young, Income=High).

• Multilevel Association Rules: Mine at multiple abstraction levels using taxonomies (e.g., Computer → Laptop → BrandX). Can use support-confidence or support-ratio thresholds at different levels.

• Multidimensional Association Rules: Rules involving multiple dimensions (not just single "items" dimension). E.g., age=20-30 ∧ income=high ⇒ buys=LCD_TV. Can be mined using SQL-based or cube-based approaches.

• Constraint-Based Association Mining: Incorporate user-specified constraints (e.g., "must include laptop", "max 3 items") to focus search and improve efficiency.

• Time Series Association Rules: Rules with temporal patterns (e.g., "if buys umbrella, then buys raincoat within 3 days").

VI. CLASSIFICATION

Definition & Process

• Definition: Learning a model (classifier) from labeled training data to predict the class label of unseen instances.

• Process:

  1. Training: Build classifier using labeled training set (X, y).

  2. Testing: Evaluate classifier on unseen test set.

  3. Prediction: Use classifier to classify new, unlabeled instances.

Decision Tree Induction

Goal: Build a tree where internal nodes are tests on attributes, branches are outcomes, leaf nodes are class labels.

Algorithm (e.g., ID3, C4.5, CART):

1. Start with all training instances at root.

2. Select Best Attribute: Use attribute selection measure to split.

3. Create Branches: For each outcome of the selected attribute, create a branch.

4. Recurse: For each branch, repeat with remaining instances/attributes until:

   • All instances belong to same class → leaf (with that class).

   • No more attributes → leaf (with majority class of instances).

   • No instances → leaf (with majority class of parent).

Attribute Selection Measures:

• Entropy (Information Theory): Measure of impurity/uncertainty.

$$ \text{Entropy}(t) = -\sum_{i=1}^{c} p_i \log_2 p_i $$

where $$\displaystyle p_i $$ = proportion of class $i$ in node $t$.

• Information Gain (ID3): Reduction in entropy after splitting on attribute $A$.

$$ \text{Gain}(A) = \text{Entropy}(parent) - \sum_{\text{values } v \text{ of } A} \frac{|S_v|}{|S|} \text{Entropy}(S_v) $$

Choose attribute with **highest Gain**.

• Gini Index (CART): Measure of impurity.

$$ \text{Gini}(t) = 1 - \sum_{i=1}^{c} p_i^2 $$

Choose attribute that gives **largest decrease in weighted Gini** (Gini split).

Pruning:

• Pre-pruning (Early stopping): Stop tree growth early (e.g., min samples per leaf, max depth).

• Post-pruning: Build full tree, then remove branches (e.g., error-based pruning, cost-complexity pruning).

Bayesian Classification (Naïve Bayes)

Based on Bayes' Theorem:

$$ P(C|X) = \frac{P(X|C) P(C)}{P(X)} $$

where $C$ is class, $$\displaystyle X=(x_1,...,x_n) $$ is attribute vector.

Naïve Assumption: Conditional Independence – attributes are independent given the class.

$$ P(X|C) = P(x_1|C) \times P(x_2|C) \times ... \times P(x_n|C) $$

Classifier: Predict class $c$ that maximizes $$\displaystyle P(C=c) \prod_{i=1}^{n} P(x_i|c) $$.

[!TIP] Works well despite independence assumption often being violated. Handles numeric attributes (using Gaussian distribution) and categorical.

Rule-Based Classification

• IF-THEN Rules: IF condition THEN conclusion (class).

• Rule Extraction from Decision Trees: Each root-to-leaf path forms a rule (conjunction of tests → class).

• Rule Ordering (Sequential Covering):

  1. Learn one rule (e.g., using separate-and-conquer).

  2. Remove covered examples.

  3. Repeat until stopping condition.

  • Ordering: Rules can be ordered (first-match) or unordered (vote).

Classifier Evaluation & Accuracy

Evaluation Methods:

1. Holdout: Split data into train and test sets (e.g., 70%-30%).

2. k-Fold Cross-Validation: Partition data into k folds; train on k-1, test on 1; repeat k times; average results.

3. Bootstrap: Sample with replacement; train on sample, test on out-of-bag samples.

Metrics (from Confusion Matrix):

• Accuracy: $$\displaystyle \frac{TP+TN}{Total} $$

• Error Rate: $1 - \text{Accuracy}$

• Precision (Positive Predictive Value): $$\displaystyle \frac{TP}{TP+FP} $$ (How many selected are relevant?)

• Recall (Sensitivity, True Positive Rate): $$\displaystyle \frac{TP}{TP+FN} $$ (How many relevant are selected?)

• F-measure (F1 Score): Harmonic mean of Precision & Recall.

$$ F_1 = 2 \times \frac{\text{Precision} \times \text{Recall}}{\text{Precision} + \text{Recall}} $$

• Specificity (True Negative Rate): $$\displaystyle \frac{TN}{TN+FP} $$

[!TIP] High Precision = few false positives. High Recall = few false negatives. F1 balances both.

Probabilistic Classifiers

Classifiers that output class probabilities $P(C|X)$ rather than a single label. Examples: Naïve Bayes, Logistic Regression, Bayesian Networks. Allows for threshold tuning (e.g., classify as "Yes" only if $$\displaystyle P(Yes|X) > 0.7 $$).

VII. CLUSTERING

Definition & Types

Definition: Grouping data objects into clusters such that objects within a cluster are highly similar to each other and dissimilar to objects in other clusters. Unsupervised learning (no class labels).

Main Types:

• Partitioning: Divide n objects into k clusters (e.g., k-Means).

• Hierarchical: Create a tree (dendrogram) of clusters (e.g., Agglomerative).

• Density-Based: Connect dense regions (e.g., DBSCAN).

• Grid-Based: Quantize space into grid cells (e.g., STING).

• Model-Based: Assume data fits a probability model (e.g., Gaussian Mixture Models).

Partitioning Methods: K-Means

Algorithm:

1. Initialize: Choose k initial centroids (randomly or k-means++).

2. Assign: For each point, assign to cluster with nearest centroid (using Euclidean distance).

3. Update: Recompute centroids as mean of all points in the cluster.

4. Repeat steps 2-3 until centroids stabilize (no change) or max iterations.

Limitations:

• Requires k to be specified.

• Sensitive to initial centroids (can converge to local optimum).

• Assumes spherical, equally sized clusters.

• Sensitive to outliers (centroids pulled by extreme values).

Hierarchical Methods

• Agglomerative (Bottom-Up):

  1. Start: each object as its own cluster.

  2. Merge the two closest clusters.

  3. Repeat until one cluster (or k clusters).

  • Linkage Criteria (Cluster Proximity):

    • Single Link: Min distance between clusters (chaining effect).

    • Complete Link: Max distance between clusters (compact clusters).

    • Average Link: Avg distance between all pairs.

• Divisive (Top-Down):

  1. Start: all objects in one cluster.

  2. Split a cluster into smaller clusters (e.g., using k-Means on subset).

  3. Repeat until each object is separate or k clusters.

• Differentiation: Agglomerative is more common. Divisive requires a criterion for splitting, often more computationally expensive initially.

Density-Based: DBSCAN

Core Idea: Clusters are dense regions separated by sparse regions.

Parameters:

• ε (eps): Radius of neighborhood.

• MinPts: Minimum number of points in ε-neighborhood to form a dense region.

Point Types:

• Core Point: Has ≥ MinPts points within ε.

• Border Point: In ε-neighborhood of a core point, but has < MinPts.

• Noise Point: Neither core nor border.

Algorithm:

1. Pick arbitrary point p.

2. Retrieve all points density-reachable from p (via core points). If p is core, forms a cluster.

3. Repeat for next unvisited point.

• Advantages: Finds arbitrarily shaped clusters, robust to outliers (noise).

Cluster Validity

Internal Measures (no external labels):

• Cohesion (Compactness): How close points are within cluster (e.g., SSE - Sum of Squared Errors).

$$ SSE = \sum_{i=1}^{k} \sum_{x \in C_i} \text{dist}(x, c_i)^2 $$

• Separation: How well-separated clusters are from each other (e.g., Silhouette Coefficient).

External Measures (with true labels):

• Entropy: Measures purity of clusters w.r.t. class labels. Low entropy = good.

• Purity: $$\displaystyle \frac{\sum_{i=1}^{k} \max_j |C_i \cap T_j|}{N} $$ where $$\displaystyle T_j $$ are true classes.

VIII. SPECIALIZED DATA MINING APPLICATIONS

Web Usage Mining

Process:

1. Log Preprocessing: Clean server logs (remove bots, errors), identify users/sessions, complete missing references.

2. Transaction Identification: Convert sessions into meaningful transactions (pageviews, navigation paths).

3. Pattern Discovery: Apply association rules, sequential patterns, clustering, classification on transactions. Applications: Personalization, site redesign, marketing, adaptive websites.

Text Mining

Process:

1. Text Preprocessing: Tokenization, stop-word removal, stemming/lemmatization.

2. Transformation: Convert text to structured data (Bag-of-Words, TF-IDF, topic modeling vectors).

3. Mining: Apply classification (spam detection), clustering (topic discovery), association (co-occurring terms), sentiment analysis. Applications: Sentiment analysis, document categorization, information retrieval, topic modeling (LDA).

Spatial Mining

Characteristics of Spatial Data: Spatial autocorrelation (Tobler's law: "everything is related, but near things more so"), complex objects (points, polygons, raster).

Key Tasks:

• Spatial Association Rules: Rules with spatial predicates (e.g., near, intersects). E.g., House Type = Villa ∧ near(Lake) → Price = High.

• Spatial Classification: Use spatial attributes (location, neighborhood) as features.

• Spatial Clustering: Group spatial objects based on location and non-spatial attributes (e.g., DBSCAN for geo-points).

Data Prediction

Definition: The task of predicting continuous-valued outcomes (regression), distinct from classification (categorical).

• Covered under: Regression models (linear regression, decision tree regression), time-series forecasting.

• Process: Similar to classification – train model on (X, y_continuous), predict y for new X.

• Evaluation Metrics: Mean Absolute Error (MAE), Mean Squared Error (MSE), R-squared.

[!CAUTION] Common Pitfall: Confusing prediction (numeric) with classification (categorical). In exam context, "Data Prediction" often refers to regression tasks.