Dataware Housing & Mining (CY-604 (C)) - Unit 1 Short Notes

UNIT 1: DATA WAREHOUSING & MINING - SHORT NOTES

I. FUNDAMENTALS & OVERVIEW

1.1 Introduction to Data Warehousing (DW)

• Definition: A Data Warehouse (DW) is a subject-oriented, integrated, time-variant, and non-volatile collection of data in support of management's decision-making process.

• Need: To support OLAP (Online Analytical Processing) for complex queries, historical analysis, and business intelligence, distinct from day-to-day OLTP (Online Transaction Processing).

• OLTP vs. OLAP:

  | Feature | OLTP (Operational DB) | OLAP (Data Warehouse) | | :--- | :--- | :--- | | Purpose | Day-to-day operations (e.g., booking a ticket) | Decision support, analysis (e.g., sales trends) | | Data | Current, detailed, volatile | Historical, summarized, integrated, non-volatile | | Schema | Normalized (3NF/BCNF) | Denormalized (Star/Snowflake) | | Queries | Short, frequent, read/write | Long, complex, read-only | | Users | Clerical staff, DB admins | Managers, executives, analysts |

• Characteristics of a Data Warehouse (Inmon's Def):

  1. Subject-Oriented: Organized around key subjects (Customer, Product, Sales), not applications.

  2. Integrated: Consistent naming, formats, and encoding from multiple heterogeneous sources.

  3. Time-Variant: Data is stored with a time dimension; historical data is preserved.

  4. Non-volatile: Data is stable; not updated/deleted in real-time. Only periodic batch loads and additions occur.

[!TIP] Exam Focus: OLTP vs. OLAP comparison and the 4 characteristics are very high-frequency. Be ready to draw a simple architecture diagram.

1.2 Data Mining: Concepts & KDD Process

• Definition: Data Mining is the process of discovering interesting patterns and knowledge from large amounts of data. It is the core analytical step of the Knowledge Discovery in Databases (KDD) process.

• KDD Process Steps:

  1. Selection (Target data)

  2. Preprocessing (Cleaning, integration)

  3. Transformation (Normalization, feature construction)

  4. Data Mining (Applying algorithms)

  5. Interpretation/Evaluation (Pattern evaluation)

  6. Knowledge (Presentation)

• Role of Data Mining Engine: The "engine" is the core component where algorithms (Apriori, Decision Tree, K-means) are executed on the preprocessed data to discover patterns.

• Data Mining Task Primitives: Specify the task using:

  • Task-relevant data (What data to use?)

  • Background knowledge (e.g., concept hierarchies)

  • Interestingness measures (e.g., Support, Confidence, Accuracy)

  • Representation of output (e.g., rules, trees, clusters)

• Types of Data:

  | Type | Description | Example | | :--- | :--- | :--- | | Relational | Standard database tables | Customer table with attributes | | Transactional | Sequence of transactions (items bought) | Market-basket data | | Data Warehouse | Multidimensional, integrated, historical | Sales data cube | | Advanced: Text, Web, Spatial, Time-series | Specialized formats | Emails, web logs, maps, stock prices |

[!TIP] Common Pitfall: Do not confuse Data Mining (the step) with KDD (the entire process). Data Mining is a subset of KDD.

1.3 Major Data Mining Tasks & Applications

• Classification: Predict categorical class labels (e.g., "Will customer churn? Yes/No"). Algorithms: Decision Trees, Naïve Bayes.

• Clustering: Group similar objects without predefined labels (e.g., segment customers). Algorithms: K-means, DBSCAN.

• Association Rule Mining: Discover frequent patterns/associations (e.g., "If bread, then milk"). Algorithm: Apriori, FP-growth.

• Regression: Predict continuous-valued outcomes (e.g., house price).

• Sequential Pattern Mining: Find patterns over time (e.g., customers who buy X then Y).

• Deviation Detection: Identify significant irregularities (e.g., fraud detection).

• Specialized Domains:

  • Web Usage Mining: Analyze web logs to understand user behavior.

  • Text Mining: Extract patterns from unstructured text (sentiment analysis).

  • Spatial Mining: Discover patterns in spatial data (GIS).

  • Time Series Mining: Forecast and find patterns in time-ordered data (stock analysis).

[!TIP] Key Distinction: Classification (predictive, supervised) vs. Clustering (descriptive, unsupervised).

II. DATA WAREHOUSE DESIGN & IMPLEMENTATION

2.1 Data Warehouse Schemas

• Star Schema:

  • Fact Table: Central table containing foreign keys to dimensions and measures (numerical facts like sales_amount).

  • Dimension Tables: Surrounding tables containing descriptive attributes (e.g., Time_dim, Product_dim). Denormalized (fewer joins).

  • Degenerate Dimension: A dimension with no attributes, just the key (e.g., transaction_id in fact table).

  • Diagram:

    DiagramSTAR SCHEMA

• Snowflake Schema:

  • Normalized version of Star Schema. Dimension tables are decomposed into multiple related tables (e.g., Product -> Product & Category).

  • Advantage: Reduces redundancy, saves space.

  • Disadvantage: More complex queries (more joins), potentially slower.

  • High-Frequency Topic.

• Galaxy Schema / Fact Constellation:

  • Multiple fact tables share dimension tables.

  • Used for complex subjects with multiple business processes (e.g., Sales_fact and Inventory_fact sharing Product_dim and Time_dim).

  • High-Frequency Topic.

• Schema Selection: Star for query speed & simplicity; Snowflake for normalized dimensions & storage; Galaxy for multiple fact tables.

[!TIP] Exam Tip: Be prepared to draw and explain Snowflake and Galaxy schemas with examples. Galaxy is often asked as "Multidimensional Database Schema".

2.2 Implementation Techniques & Architecture

• MOLAP (Multidimensional OLAP):

  • Uses proprietary multidimensional storage (array-based).

  • Data is pre-aggregated and stored in cubes.

  • Advantages: Very fast query response, optimized for slicing/dicing.

  • Disadvantages: Limited scalability (data volume), proprietary, expensive.

  • Need for MOLAP Server: To provide fast, interactive analysis on pre-computed aggregates, crucial for business users needing instant responses.

• ROLAP (Relational OLAP):

  • Uses relational DBMS (RDBMS) and SQL.

  • Data and aggregates stored in relational tables.

  • Advantages: Scalable (handles huge data), uses standard RDBMS, cost-effective.

  • Disadvantages: Slower than MOLAP (many joins, complex SQL), performance depends on RDBMS.

  • ROLAP Architecture Diagram:

    DiagramROLAP ARCHITECTURE
    (Show: Client -> OLAP Server (SQL Generator) -> Relational DB -> Data Warehouse).

• HOLAP (Hybrid OLAP):

  • Combines MOLAP & ROLAP. Stores detailed data in RDBMS, aggregates in MOLAP cube.

  • Advantage: Balances scalability and performance.

  • Disadvantage: Complexity in management.

• Vertical Partitioning:

  • Splitting a table by columns (attributes) into multiple tables.

  • How: Frequently accessed columns (e.g., customer_id, name) are separated from infrequently accessed columns (e.g., biography, notes).

  • Purpose: Improves query performance for common queries (smaller I/O), reduces contention.

  • High-Frequency Topic.

[!TIP] Comparison is Key: Know the pros/cons of MOLAP vs ROLAP and where HOLAP fits. Vertical partitioning is about column-wise splitting.

2.3 Multidimensional Data Modeling & Data Cubes

• Multidimensional Database (MDDB): Organizes data in a cube (n-dimensional array). Each cell contains a measure (e.g., sales). Dimensions are like Product, Time, Store.

• Data Cube: A multidimensional view of data, allowing analysis along multiple dimensions.

  • Example: 3-D Cube (Time x Product x Store) containing sales.

• Data Cube Computation (Materialization):

  • Lattice: All possible group-by combinations (views) of dimensions form a lattice.

  • Full Materialization: Compute and store all possible views. Fast queries, huge storage.

  • Partial Materialization: Compute and store only a subset of views (e.g., common ones). Trade-off between storage and query speed.

  • Methods: Bottom-up (compute smaller aggregates to build larger), Top-down (start from largest).

  • High-Frequency Topic.

• Indexing:

  • Bitmap Index: For low-cardinality dimensions (e.g., Gender). Fast set operations (AND/OR).

  • Join Index: Pre-computes joins between fact and dimension tables to speed up star join queries.

III. ONLINE ANALYTICAL PROCESSING (OLAP)

3.1 OLAP Fundamentals

• Definition: OLAP is a category of software tools that provide analysis of data stored in a data warehouse. It enables users to analyze data from multiple perspectives.

• OLAP vs. OLTP: (See table in I.1.1)

• Core OLAP Operations:

  1. Roll-up (Drill-up): Summarize data by climbing up a dimension hierarchy (e.g., City -> State -> Country).

  2. Drill-down (Roll-down): Go to finer granularity (e.g., 2023 -> Q1 -> Jan).

  3. Slice-and-dice: Select a subset of the cube by fixing a dimension value (slice) and then viewing across other dimensions (dice).

  4. Pivot (Rotate): Reorient the cube to see a different dimensional view (swap rows/columns).

• OLAP Server: Middleware between client and DB. Receives SQL/MDX queries, optimizes, and retrieves data from DW. Manages cube metadata and aggregates.

[!TIP] Remember: Roll-up = Summarize, Drill-down = Detail.

3.2 OLAP Types & Realization

• ROLAP (Relational OLAP): (See II.2.2)

• MOLAP (Multidimensional OLAP): (See II.2.2)

• HOLAP (Hybrid OLAP): (See II.2.2)

• Comparison Table:

IV. DATA PREPROCESSING (FOR MINING)

4.1 Data Cleaning

• Definition: The process of detecting and correcting (or removing) corrupt, inaccurate, or irrelevant data.

• Techniques:

  • Missing Values: Ignore tuple, fill manually, use mean/median/mode, use ML predictor.

  • Noisy Data: Binning (smoothing by bin means/medians), Regression, Clustering, Manual inspection.

  • Outlier Detection: Use statistical methods (e.g., > 3σ), boxplot analysis, clustering.

[!TIP] Common Question: "Define data cleaning. Discuss techniques." Always list missing, noisy, outlier with 1-2 line explanations each.

4.2 Data Transformation & Reduction

• Transformation Methods:

  • Smoothing: Remove noise (binning, regression).

  • Aggregation: Summarize data (e.g., daily sales to monthly).

  • Generalization: Replace low-level values with higher-level concepts (using concept hierarchies).

  • Feature Construction: Create new attributes from existing ones (e.g., BMI from height & weight).

  • Normalization: Scale data to a small range.

    • Min-Max Normalization: $$\displaystyle x' = \frac{x - \min}{\max - \min} $$

    • Z-score Normalization: $$\displaystyle x' = \frac{x - \mu}{\sigma} $$

• Data Reduction:

  • Dimensionality Reduction: PCA, Feature Selection.

  • Numerosity Reduction: Parametric (regression), Non-parametric (histograms, clustering, sampling).

V. ASSOCIATION RULE MINING

5.1 Fundamentals

• What: Finding interesting associations/relationships among large sets of data items. Market-Basket Model is typical.

• Key Terminology:

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

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

$$\text{Support}(X \Rightarrow Y) = P(X \cup Y)$$

*   **Confidence (c):** Conditional probability that Y occurs given X.

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

*   **Frequent Itemset:** Itemset with support ≥ **min_support** threshold.

*   **Strong Rule:** Rule that satisfies both **min_support** and **min_confidence**.

[!TIP] Formula Box: $$\displaystyle \boxed{\text{Confidence} = \frac{\text{Support}(X \cup Y)}{\text{Support}(X)}} $$

5.2 Apriori Algorithm (Frequent)

• Core Principle: All non-empty subsets of a frequent itemset must themselves be frequent. (Anti-monotone property).

• Steps:

  1. Find frequent k-itemsets by joining (k-1)-itemsets and pruning using Apriori property.

  2. Generate association rules from frequent itemsets, pruning rules that don't meet min_confidence.

• Example: Given transactions, find L1 (1-itemsets), L2 (2-itemsets), L3 (3-itemsets) by iterative candidate generation and pruning.

• Drawback: Multiple passes over data, huge candidate sets.

5.3 FP-growth Algorithm (Frequent)

• Idea: Avoid candidate generation. Uses a compact data structure called FP-tree.

• Steps:

  1. Scan DB once to build FP-tree (frequent pattern tree). Each node is an item with count.

  2. Mine tree recursively: For each frequent item, construct conditional pattern base and conditional FP-tree. Extract patterns directly.

• Advantage over Apriori: No candidate generation, only 2 scans of DB, typically faster.

5.4 Improving Apriori Efficiency (Frequent)

• Hash-based Technique: Use hash tables to prune candidate itemsets early (hash collisions indicate infrequent subsets).

• Transaction Reduction: Reduce size of DB by removing irrelevant transactions (those not containing any current frequent itemset).

• Partitioning: Split DB into partitions. Find local frequent itemsets in each partition, then global (any itemset frequent globally must be frequent in at least one partition).

• Sampling: Mine a random sample of DB; results may be approximate, need verification on full DB.

[!TIP] Algorithm Comparison: Apriori = Candidate generation & test, FP-growth = Pattern growth in FP-tree. Know the steps for both with a small example (3-4 transactions).

VI. CLASSIFICATION

6.1 Fundamentals

• Definition: The process of predicting the class label of a new instance based on a model built from training data (labeled).

• Process:

  1. Training: Build model from labeled data.

  2. Testing: Apply model to unseen test data.

  3. Evaluation: Measure accuracy using metrics.

• Accuracy Verification Methods:

  • Holdout: Split data into train/test (e.g., 70%/30%).

  • Cross-validation (k-fold): Partition data into k subsets, use k-1 for train, 1 for test, repeat k times.

  • Bootstrapping: Sample with replacement to create multiple training sets.

• Evaluation Metrics (from Confusion Matrix):

  • Accuracy: $(TP + TN) / Total$

  • Precision: $TP / (TP + FP)$

  • Recall (Sensitivity): $TP / (TP + FN)$

  • F1-Score: $$\displaystyle 2 \times \frac{Precision \times Recall}{Precision + Recall} $$

6.2 Decision Tree Induction (Frequent)

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

• Algorithms: ID3 (uses Entropy), C4.5 (uses Gain Ratio), CART (uses Gini Index).

• Splitting Criteria:

  • Entropy (ID3): Measures impurity.

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

*   **Information Gain:** $$\displaystyle Gain(D, A) = Entropy(D) - \sum_{v \in Values(A)} \frac{|D_v|}{|D|} Entropy(D_v) $$

*   **Gini Index (CART):** $$\displaystyle Gini(D) = 1 - \sum_{i=1}^{c} p_i^2 $$

• Pruning: Remove branches that have low predictive power to avoid overfitting.

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

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

[!TIP] Must-Know: Calculate Entropy and Information Gain for a small dataset (2-3 attributes). Know the difference between ID3 (Entropy) and CART (Gini).

6.3 Rule-Based & Bayesian Classification

• Rule-Based (e.g., Sequential Covering, RIPPER):

  • Learn a set of IF-THEN rules.

  • Sequential Covering: Iteratively learn one rule, remove covered examples, repeat.

• Bayesian Classification:

  • Naïve Bayes: Assumes attribute independence given the class.

$$P(C|X) = \frac{P(C) \prod_{i=1}^{n} P(x_i|C)}{P(X)} \propto P(C) \prod_{i=1}^{n} P(x_i|C)$$

    Predict class $C$ with highest posterior probability.

*   **Bayesian Belief Networks (BBNs):** Graphical model representing conditional dependencies among variables via a DAG.

[!TIP] Naïve Bayes Formula: $$\displaystyle \boxed{P(C|X) \propto P(C) \prod_{i=1}^{n} P(x_i|C)} $$ (The "naïve" independence assumption is key).

6.4 Probabilistic Classifiers

• Definition: Classifiers that output a probability distribution over classes, not just a single label.

• Examples: Naïve Bayes, Logistic Regression, BBNs.

• Advantage: Provides confidence measure for predictions.

VII. CLUSTERING

7.1 Fundamentals

• Definition: Grouping a set of objects such that objects in the same group (cluster) are more similar to each other than to those in other groups. Unsupervised learning.

• Requirements: Scalability, ability to handle various attributes, discovery of arbitrary shapes, minimal domain knowledge.

7.2 Partitioning Methods (K-means, K-medoids)

• K-means:

  • Input: k (number of clusters).

  • Steps: (1) Initialize k centroids randomly. (2) Assign each point to nearest centroid. (3) Recompute centroids as mean of points. (4) Repeat 2-3 until convergence.

  • Distance: Usually Euclidean.

  • Pros: Fast, scalable. Cons: Sensitive to outliers, k must be specified, assumes spherical clusters.

• K-medoids (PAM): Uses actual data points as cluster centers (medoids). More robust to outliers.

7.3 Hierarchical Methods

• Agglomerative (Bottom-up, e.g., AGNES):

  • Start with each point as a cluster.

  • Iteratively merge the two closest clusters until one cluster remains or stopping criterion.

  • Produces a dendrogram.

• Divisive (Top-down, e.g., DIANA):

  • Start with all points in one cluster.

  • Iteratively split clusters until each point is its own cluster or stopping criterion.

• Comparison:

  | | Agglomerative (Bottom-up) | Divisive (Top-down) | | :--- | :--- | :--- | | Approach | Merge small clusters | Split large clusters | | Complexity | $$\displaystyle O(n^3) $$ (can be $$\displaystyle O(n^2 \log n) $$) | $$\displaystyle O(2^{n-1}) $$ (expensive) | | Use Case | More common, intuitive | Less common |

[!TIP] High-Frequency: Differentiate between top-down (Divisive) and bottom-up (Agglomerative). Know AGNES (AGglomerative NESting) and DIANA (DIvisive ANAlysis).

7.4 Other Methods

• DBSCAN (Density-based): Forms clusters based on density. Can find arbitrarily shaped clusters, robust to outliers. Key parameters: eps (radius), MinPts (minimum points in eps-neighborhood).

• STING (Grid-based): Divides space into grid cells, performs clustering on grid structure. Fast, independent of data order.

VIII. ADVANCED & SPECIALIZED TOPICS (Brief)

8.1 Data Prediction

• Definition: Forecasting future values based on historical data.

• Link to: Regression (linear, polynomial) for continuous prediction, Time Series Mining (ARIMA, Exponential Smoothing) for temporal data.

8.2 Web Usage Mining

• Process: (1) Preprocessing (clean web logs, identify users/sessions). (2) Pattern Discovery (association, clustering, sequential patterns). (3) Pattern Analysis.

• Applications: Personalization, site redesign, marketing, adaptive websites.

8.3 Text Mining

• Process: (1) Text Preprocessing (tokenization, stop-word removal, stemming). (2) Transformation (create Document-Term Matrix). (3) Mining (clustering, classification, topic modeling).

• Difference from Traditional DM: Deals with unstructured/semi-structured text, requires NLP techniques.

8.4 Spatial Mining

• Types of Spatial Data: Raster (grid), Vector (points, lines, polygons).

• Methods: Spatial association rules, spatial clustering (e.g., spatial DBSCAN), spatial classification (considering spatial autocorrelation).

8.5 Time Series Mining

• Pattern Discovery: Find frequent patterns (motifs), shapelets, trends.

• Forecasting: Use models like ARIMA (AutoRegressive Integrated Moving Average), Exponential Smoothing.

• Association Rules: Mine rules like "After a peak in stock A, stock B rises within 2 days."

[!TIP] For specialized topics, focus on process steps and 1-2 key applications. They are often asked as 7-mark "Write about..." questions.