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

UNIT 4: DATA WAREHOUSING & MINING

I. DATA WAREHOUSE IMPLEMENTATION AND DESIGN

Definition and Key Characteristics of Data Warehouse

A subject-oriented, integrated, time-variant, non-volatile collection of data used to support management decision-making.

[!TIP] Exam Focus: Always list all 4 characteristics with a one-line explanation. Contrast with operational databases (OLTP).

Data Warehouse Architecture and Components

Typical 3-Tier Architecture:

1. Bottom Tier (Data Source Layer): Operational databases, external data, flat files.

2. Middle Tier (Data Warehouse & OLAP Server): Data staging area (ETL), data warehouse database, OLAP server (ROLAP/MOLAP).

3. Top Tier (Front-end Tools): Query/reporting tools, OLAP tools, data mining tools, dashboards.

Core Components:

• ETL Process: Extract, Transform, Load. The most critical and time-consuming phase.

• Metadata Repository: "Data about the data" (source, format, lineage, definitions).

• Data Warehouse Database: Central repository, often a relational DBMS (for ROLAP) or proprietary multidimensional DB (for MOLAP).

Schema Design for Multidimensional Databases

Core Concept: Data is modeled as a data cube with dimensions (perspectives like Time, Product) and measures (quantitative facts like Sales, Quantity).

[!TIP] Exam Question: "Explain Galaxy Schema" – Focus on multiple fact tables and conformed dimensions (e.g., a shared Time dimension used by both Sales and Inventory fact tables).

Physical Implementation Techniques

• Vertical Partitioning: Splitting a table column-wise.

  • How: Frequently accessed columns (e.g., Product_ID, Sales_Amount) are placed in one table; infrequent/large columns (e.g., Product_Description, Image) in another.

  • Goal: Reduce I/O for common queries by reading fewer, narrower pages.

• Indexing: B-tree, bitmap indexes (excellent for low-cardinality dimensions like Region).

• Materialized Views: Pre-computed and stored query results (e.g., total sales per region per month). Drastically improves performance for complex aggregations but requires maintenance overhead.

OLAP Systems

OLAP (Online Analytical Processing): System for complex analytical queries against a DW. OLTP (Online Transaction Processing): System for routine, high-volume transactions (e.g., ATM, order entry).

Types of OLAP:

• ROLAP (Relational OLAP): Uses relational DBMS. Data and aggregations are stored in tables. Scalable for large data volumes. Slower for complex aggregations.

• MOLAP (Multidimensional OLAP): Uses proprietary multidimensional storage (arrays). Pre-computes and stores all possible aggregations in a data cube. Very fast query response. Can have "sparsity" issues (many empty cells), less scalable for huge data.

[!TIP] Diagram for ROLAP: Draw a relational schema (Star Schema) feeding into a relational DBMS, with an OLAP server on top generating SQL. Label the flow: "User Query -> OLAP Server -> SQL -> RDBMS -> Result".

OLAP Servers: Middleware between the DW and front-end tools. They understand multidimensional concepts and translate user queries into appropriate commands for the underlying storage (SQL for ROLAP, array operations for MOLAP).

Data Cubes and Computation:

• A data cube is an n-dimensional array of data.

• Computation Problem: Pre-computing all possible aggregations for a cube is often infeasible (combinatorial explosion).

• Key Methods:

  1. Full Cube: Compute all $$\displaystyle 2^n $$ group-by aggregations. Feasible only for small n.

  2. Partial Cube / Iceberg Cube: Compute only aggregations meeting a minimum support threshold (e.g., COUNT > 100). This is the common practical approach.

  3. Closed Cube / Maximal Cube: Store only the most specific, non-redundant aggregations.

II. DATA PREPROCESSING FOR DATA MINING

Data Cleaning Techniques

Goal: Fix inconsistencies, errors, and missing values.

• Missing Data:

  • Ignore tuple: Discard record (only if few missing values).

  • Fill manually: Impractical for large datasets.

  • Global constant: Fill with a special value (e.g., Unknown).

  • Attribute mean/median: Fill with central tendency of that attribute.

  • Most probable value: Use regression, decision tree, or k-NN to impute.

• Noisy Data (Errors/Outliers):

  • Binning: Sort values, partition into bins (equal-frequency/width), then smooth by bin mean/median/boundaries.

  • Regression: Fit a function to smooth data.

  • Clustering: Group similar values; outliers may form tiny clusters.

  • Computer/ Human inspection: Verify with domain experts.

Data Transformation Methods

Goal: Convert data into appropriate form for mining.

• Normalization: Scale numeric attributes to a small, specified range (e.g., 0-1).

  • Min-Max Normalization: $$\displaystyle v' = \frac{v - min_A}{max_A - min_A} \times (new\_max_A - new\_min_A) + new\_min_A $$

  • Z-Score Normalization: $$\displaystyle v' = \frac{v - \mu_A}{\sigma_A} $$ (mean=0, std dev=1)

• Attribute Construction: Create new attributes from existing ones (e.g., BMI from Height and Weight).

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

• Generalization: Replace low-level values with higher-level concepts (e.g., 25 -> Young, USA -> North America).

• Discretization: Convert continuous attributes to categorical (e.g., Age -> {Youth, Middle, Senior}). Methods: binning, histogram analysis, k-means clustering, decision trees.

III. DATA MINING PROCESS AND TASK SPECIFICATION

KDD Process and Role of Data Mining Engine

KDD (Knowledge Discovery in Databases) is the overall process of extracting knowledge from data. The data mining engine is the core algorithmic component within this process.

KDD Steps:

1. Selection: Target data from sources.

2. Preprocessing: Cleaning, integration (as in Unit II).

3. Transformation: Normalization, feature construction (as in Unit II).

4. Data Mining: Apply core algorithms (association, classification, clustering) to find patterns.

5. Interpretation/Evaluation: Assess and interpret mined patterns; may return to previous steps.

6. Knowledge: Final, actionable information presented to user.

[!TIP] Role of DM Engine: It is the "pattern discovery" step (#4). It takes the prepared data and executes algorithms like Apriori, k-means, or decision tree induction.

Data Mining Task Primitives

A formal way to specify a data mining task. The Data Mining Query Language (DMQL) uses these.

1. Task-relevant data: (Database, Tables, Conditions) – What data to mine?

2. Type of knowledge to be mined: (Characterization, Association, Classification, Clustering, etc.)

3. Background knowledge: (Concept hierarchies, ontologies) – Used to generalize/prune results.

4. Interestingness measures: (Support, Confidence, Accuracy, Lift) – Thresholds to filter patterns.

5. Presentation/Visualization of discovered patterns: (Rules, tables, charts, graphs).

Types of Data for Data Mining

IV. ASSOCIATION RULE MINING

Fundamentals and Boolean Association Rules

• Item: A variable/value (e.g., Bread, Milk).

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

• Transaction: A record containing a set of items (e.g., a market basket).

• Association Rule: $X \Rightarrow Y$ (where $$\displaystyle X \cap Y = \emptyset $$). "If a transaction contains X, it is likely to contain Y."

• Support (supp): $$\displaystyle supp(X \Rightarrow Y) = \frac{| \{t : X \cup Y \subseteq t\} |}{|T|} $$. Frequency of the rule.

• Confidence (conf): $$\displaystyle conf(X \Rightarrow Y) = \frac{supp(X \cup Y)}{supp(X)} $$. Conditional probability of Y given X.

• Goal: Find all rules satisfying min_supp and min_conf.

Apriori Algorithm (with example)

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

Pseudocode:

C1 = {all 1-itemsets}

L1 = {itemsets in C1 with support >= min_supp}

k = 2

while Lk-1 != ∅ do:

    Ck = apriori-gen(Lk-1)  // Join & Prune step

    Count support of all candidates in Ck by scanning DB

    Lk = {c in Ck | support(c) >= min_supp}

    k = k + 1

return ∪k Lk

Example (min_supp=2):

• T1: {A,B,C} T2: {A,C} T3: {A,B} T4: {B,C} T5: {A,B,C}

• C1: {A(4), B(4), C(4)} -> L1: {A,B,C}

• C2 (from L1): {A,B(3), A,C(3), B,C(3)} -> L2: {A,B}, {A,C}, {B,C} (all supp=3)

• C3 (from L2): {A,B,C(2)} -> L3: {A,B,C} (supp=2)

• Frequent Itemsets: All in L1, L2, L3.

• Generate Rules from L3: e.g., A,B -> C (conf = supp(A,B,C)/supp(A,B) = 2/3 = 66.7%).

FP-growth Algorithm (with example)

Idea: Avoid candidate generation and multiple DB scans. Uses a compact data structure: FP-tree.

Steps:

1. Scan DB once to get frequency of each item. Order items by descending frequency.

2. Build FP-tree:

   • Start with root null.

   • For each transaction, sort items by global frequency order.

   • Insert sorted items into tree, sharing common prefixes. Nodes store item name and count. Maintain header table linking all nodes of same item.

3. Mine FP-tree recursively:

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

   • Build conditional FP-tree from this base.

   • Recursively mine the conditional FP-tree. Patterns are formed by suffixing the item.

Example: Simple, but conceptually, FP-tree is much more compact than candidate lists, especially with many items.

Techniques to Improve Apriori Efficiency

1. Hash-based technique: Use hash tables during candidate generation to prune candidates early based on hash collisions.

2. Transaction Reduction: Reduce the size of the number of transactions to be scanned in future passes by removing irrelevant transactions (those that don't contain any current frequent itemset).

3. Partitioning: Partition the database into disjoint chunks. Find all local frequent itemsets (can have false positives). Global frequent itemsets must be locally frequent. Final pass to verify.

4. Sampling: Mine a random sample of the DB. Lower support threshold used. Final verification on full DB.

5. Dynamic Item Counting: Add candidate itemsets during a database pass based on partially counted information.

V. CLASSIFICATION AND PREDICTIVE MODELING

Learning Phase in Classification

Process of building a classifier or predictive model from a labeled training dataset $$\displaystyle D = \{(x_i, y_i)\} $$.

1. Model Construction: Algorithm learns a mapping $$\displaystyle f: X \rightarrow Y $$ from input features $X$ to class label $Y$.

2. Model Evaluation (Testing): Use a separate test set (not used in training) to estimate accuracy. Common method: holdout (split 70/30) or k-fold cross-validation.

3. Model Usage: Apply the model to classify new, unseen instances.

Decision Tree Induction Algorithm (e.g., ID3, C4.5)

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

Core: Attribute Selection Measure.

• ID3: Uses Information Gain (IG) based on Entropy.

  • Entropy($D$) = $$\displaystyle -\sum_{i=1}^{c} p_i \log_2 p_i $$ (purity of class distribution in set D).

  • IG($D$, $A$) = Entropy($D$) - $$\displaystyle \sum_{v \in Values(A)} \frac{|D_v|}{|D|} Entropy(D_v) $$

  • Choose attribute with highest IG.

• C4.5: Uses Gain Ratio to correct IG's bias towards multi-valued attributes.

  • GainRatio($A$) = $$\displaystyle \frac{IG(A)}{SplitInfo(A)} $$ where $$\displaystyle SplitInfo(A) = -\sum_{v} \frac{|D_v|}{|D|} \log_2 \frac{|D_v|}{|D|} $$

  • Choose attribute with highest Gain Ratio.

Algorithm (Recursive):

1. If all tuples in current node belong to same class, make leaf with that class.

2. If no attributes left, make leaf with majority class of current tuples.

3. Else, select best attribute (A) using IG/Gain Ratio.

4. Create branch for each value $v$ of A.

5. For each branch, create subtree with $$\displaystyle D_v $$ (tuples where A=v) and remaining attributes. Recurse.

[!TIP] Example: Given a small table, calculate Entropy and IG for attributes like Outlook, Temperature to decide the root node.

Rule-based Classification Algorithms (e.g., RIPPER)

• Separate-and-Conquer: Build rules one at a time.

• RIPPER Algorithm:

  1. Growing Phase: Start with an empty rule IF THEN. Add conditions (tests on attributes) to the rule's antecedent to maximize information gain (minimize error) on the training set. Stop when rule is perfect or a minimum description length criterion is met.

  2. Pruning Phase: Remove conditions from the rule (from last to first) if pruning reduces error on a separate validation set.

  3. Repeat until all positive examples are covered or error rate exceeds a threshold.

• Pros: Rules are often more understandable than trees, can represent disjunctive concepts (OR).

• Cons: Can be sensitive to rule ordering.

Bayesian Classification (Naïve Bayes)

Based on Bayes' Theorem: $$\displaystyle P(Y|X) = \frac{P(X|Y) P(Y)}{P(X)} $$

• Naïve Assumption: Attributes are conditionally independent given the class.

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

• Classifier: For a new instance $$\displaystyle x = (x_1, ..., x_n) $$, compute $$\displaystyle P(Y=c|x) \propto P(Y=c) \prod_{i} P(x_i|c) $$ for each class $c$. Predict class with highest posterior probability.

• Advantages: Simple, fast, works well with high-dimensional data. Handles numeric attributes (using Gaussian distribution) and categorical.

• Disadvantages: The conditional independence assumption is often violated in practice.

Probabilistic Classifiers

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

• Examples: Naïve Bayes, Logistic Regression, some neural networks.

• Output: $$\displaystyle P(Y=c_1|x), P(Y=c_2|x), ... $$

• Use: Provides confidence in prediction. Useful for cost-sensitive classification or when the "best guess" is uncertain.

Classifier Accuracy Verification

• Holdout Method: Split data into training set and test set (e.g., 2/3 train, 1/3 test). Accuracy = $$\displaystyle \frac{\text{correctly classified test tuples}}{\text{total test tuples}} $$.

• k-Fold Cross-Validation:

  1. Partition data into k mutually exclusive subsets (folds) of equal size.

  2. For each i from 1 to k: Train on all folds except fold i, test on fold i.

  3. Overall accuracy = average of the k accuracies.

  • Common: k=10.

• Bootstrap: Sample n tuples from the dataset with replacement to form a training set (same size as original). The tuples not selected form the test set. Repeat many times (e.g., 100). Aggregated estimate is more robust.

[!TIP] Key Difference: Holdout uses one split. Cross-validation uses k different train/test splits and averages.

Data Prediction Concepts

• Prediction: Using a model to estimate the value of a continuous target variable (regression) or a categorical label (classification).

• Process: Same as classification: train model on labeled data, apply to new data with unknown target.

• Evaluation Metrics (for continuous):

  • Mean Absolute Error (MAE): $$\displaystyle \frac{1}{n}\sum_{i=1}^{n} |y_i - \hat{y}_i| $$

  • Mean Squared Error (MSE): $$\displaystyle \frac{1}{n}\sum_{i=1}^{n} (y_i - \hat{y}_i)^2 $$

  • Root Mean Squared Error (RMSE): $\sqrt{MSE}$

VI. CLUSTERING

Overview of Clustering Methods

• Goal: Group objects into clusters such that intra-cluster similarity is high and inter-cluster similarity is low.

• Partitioning Methods: Divide n objects into k clusters (e.g., k-means). Optimize an objective function (e.g., sum of squared distances).

• Hierarchical Methods: Create a tree (dendrogram) of clusters.

  • Agglomerative (Bottom-up): Start with each object as its own cluster, merge closest pairs.

  • Divisive (Top-down): Start with all objects in one cluster, split recursively.

• Density-based Methods: Grow clusters as long as density in a neighborhood exceeds a threshold (e.g., DBSCAN). Can find arbitrarily shaped clusters and handle noise.

Hierarchical Clustering Algorithms

Agglomerative (e.g., Single/Complete/Average Linkage):

1. Compute pairwise proximity matrix.

2. Repeat:

   • Merge the two closest clusters.

   • Update proximity matrix to reflect new cluster.

3. Until only one cluster remains.

Linkage Criteria (how to measure cluster-to-cluster distance):

• Single Linkage (MIN): $$\displaystyle d(C_i, C_j) = \min_{x \in C_i, y \in C_j} d(x,y) $$. Sensitive to noise, chaining effect.

• Complete Linkage (MAX): $$\displaystyle d(C_i, C_j) = \max_{x \in C_i, y \in C_j} d(x,y) $$. Produces compact clusters.

• Average Linkage: $$\displaystyle d(C_i, C_j) = \frac{1}{|C_i||C_j|} \sum_{x \in C_i} \sum_{y \in C_j} d(x,y) $$. Compromise.

Divisive (e.g., DIANA):

1. Start with all objects in one cluster.

2. Recursively:

   • Select the cluster with largest diameter (or other measure of heterogeneity).

   • Split it using a partitioning method (often k-means with k=2).

   • Continue until each cluster has 1 object or meets a stopping criterion.

[!TIP] Differentiate: Agglomerative is bottom-up (many clusters -> one). Divisive is top-down (one cluster -> many). Agglomerative is more common.

VII. SPECIALIZED DATA MINING APPLICATIONS

Web Usage Mining

• Goal: Discover patterns from web server logs to understand user behavior.

• Data Sources: Server logs, client-side cookies, proxy logs, browser histories.

• Key Tasks:

  • Preprocessing: Data cleaning (remove robots, errors), user identification (from IP/agent), session identification, path completion.

  • Pattern Discovery: Association rules (pages visited together), Sequential patterns (ordered page sequences), Clustering (similar user sessions), Classification (predicting next page).

• Applications: Website redesign, personalized recommendations, adaptive sites, marketing.

Text Mining

• Goal: Discover knowledge from unstructured text documents.

• Major Challenge: Text is high-dimensional, sparse, and noisy.

• Key Steps:

  1. Text Preprocessing:

     • Tokenization (split text into words).

     • Stop-word removal (remove common words: the, is, and).

     • Stemming/Lemmatization (reduce words to root form: "running" -> "run").

  2. Vector Space Model: Represent each document as a term vector (e.g., TF-IDF weights).

  3. Pattern Discovery: Apply standard DM tasks on vectors:

     • Clustering: Group similar documents (e.g., news articles).

     • Classification: Categorize documents (e.g., spam vs. ham).

     • Topic Modeling: (e.g., LDA) discover latent topics in a corpus.

• Applications: Sentiment analysis, news categorization, patent search, legal document analysis.

Spatial Mining

• Goal: Discover patterns from spatial databases (data with implicit/ explicit location).

• Spatial Data Types: Points (cities), lines (rivers), polygons (counties), raster (satellite images).

• Key Challenges: Spatial Autocorrelation (nearby objects tend to be similar), complex spatial relationships (topological, distance, directional).

• Patterns:

  • Spatial Association Rules: If (near(house, lake)) and (size=large) Then (price=high).

  • Spatial Clustering: (e.g., DBSCAN with spatial distance). Find hotspots.

  • Spatial Classification: Use spatial attributes (e.g., distance_to_city_center) as features.

  • Spatial Trend Detection: How a non-spatial attribute (e.g., crime_rate) changes over space.

• Applications: GIS, urban planning, environmental monitoring, location-based services.

VIII. EVALUATION AND IMPLICATIONS OF DATA MINING

Pros and Cons of Data Mining

[!TIP] Exam Answer Structure: For "Pros and Cons," present as a balanced table or two clear lists. Always connect technical limitations (accuracy, complexity) with social/ethical implications (privacy, discrimination).