Data Warehousing & Data Mining — Study Guide

DATA WAREHOUSING & DATA MINING

Comprehensive Study Guide
All 5 Units — External Examination Preparation

Units Covered:
Unit I — Basics of Data Warehousing
Unit II — Data Cube and OLAP
Unit III — Basics of Data Mining
Unit IV — Classification Techniques
Unit V — Cluster Analysis

UNIT I — BASICS OF DATA WAREHOUSING

1.1 Introduction to Data Warehouse

A Data Warehouse (DW) is a large, centralized repository of integrated data from multiple sources
designed specifically for querying and analysis rather than transaction processing. The term was coined
by Bill Inmon (1990), often called the 'Father of Data Warehousing'.
Definition (Bill Inmon): A data warehouse is a subject-oriented, integrated, time-variant, and non-
volatile collection of data in support of management's decision-making process.

Four Characteristics of a Data Warehouse:

• Subject-Oriented: Organized around major subjects such as customer, product, sales. Focuses
on modelling and analysis of data for decision-makers.
• Integrated: Data from multiple heterogeneous sources (RDBMS, flat files, online transaction
records) is integrated into a consistent format. Ensures consistency in naming conventions,
encoding structures, and attribute measures.
• Time-Variant: Data is stored with a time dimension, maintaining historical perspective. Data is
accurate only as of some point in time (snapshot).
• Non-Volatile: Once entered into the warehouse, data is never removed. Operations are only:
initial loading of data and access (querying). No real-time updates.
Data Warehousing & Data Mining — Complete Study Guide
Data Warehousing & Data Mining — Study Guide

Q: What is a Data Warehouse? State its characteristics.

A: A Data Warehouse is a subject-oriented, integrated, time-variant, and non-volatile collection of data
used for decision-making. The four characteristics are: (1) Subject-Oriented — focused on business
subjects like sales or customers; (2) Integrated — data from multiple sources is unified; (3) Time-
Variant — stores historical snapshots with time stamps; (4) Non-Volatile — data is read-only once
loaded.
Q: Who coined the term 'Data Warehouse' and when?
A: Bill Inmon coined the term in 1990. He is known as the Father of Data Warehousing.

1.2 Need of Data Warehousing

Organizations generate massive amounts of data from daily transactions. However, operational
databases are optimized for transactional processing (OLTP), not decision support. Data warehousing
addresses this gap.

Why Data Warehousing is Needed:

• Consolidation: Brings data from scattered operational databases into a single unified system.
• Historical Analysis: Stores years of historical data enabling trend analysis, which operational
systems do not maintain.
• Decision Support: Enables management to make informed strategic decisions through complex
analytical queries.
• Data Quality: Cleanses and transforms data, ensuring accuracy and consistency.
• Performance: Offloads heavy analytical queries from operational systems, preventing
performance degradation.
• Cross-functional Analysis: Enables analysis that spans multiple departments (e.g., sales +
inventory + customer data).

Q: What is the need for a Data Warehouse?

A: Operational systems handle day-to-day transactions but are not suitable for complex analysis. Data
warehouses are needed for: historical data storage, cross-departmental data integration, improved
query performance for analytics, data quality and consistency, and management decision support.

1.3 Differences between Operational Database Systems and Data

Warehouses
Operational Database Systems (OLTP) and Data Warehouses (OLAP/DW) differ fundamentally in their
purpose, design, and usage patterns.
• Purpose: OLTP — day-to-day operations (insert, update, delete); DW — decision support and
analysis (read-heavy queries).
• Data Content: OLTP — current, detailed, real-time data; DW — historical, summarized,
integrated data.
• Data Orientation: OLTP — application-oriented (e.g., banking, order entry); DW — subject-
oriented (e.g., customers, sales).
• Design: OLTP — normalized (3NF) to eliminate redundancy; DW — denormalized
(star/snowflake) for fast queries.

Data Warehousing & Data Mining — Complete Study Guide

Data Warehousing & Data Mining — Study Guide

• Users: OLTP — clerks, front-end staff handling thousands of transactions; DW — analysts and
managers running fewer, complex queries.
• Query Type: OLTP — simple, predefined transactions; DW — complex, ad-hoc analytical
queries.
• Update Frequency: OLTP — continuously updated in real-time; DW — periodically updated
(daily/weekly batch loads).
• Data Volume: OLTP — megabytes to gigabytes; DW — gigabytes to terabytes.
• Response Time: OLTP — milliseconds; DW — seconds to minutes for complex queries.
• Backup & Recovery: OLTP — critical for operational continuity; DW — can be reloaded from
source if needed.

Q: Differentiate between OLTP and Data Warehouse (any 5 points).

A: 1. OLTP handles transactions; DW handles analysis. 2. OLTP uses normalized schema; DW uses
denormalized. 3. OLTP stores current data; DW stores historical data. 4. OLTP has many users doing
simple queries; DW has fewer users doing complex queries. 5. OLTP data is volatile; DW data is non-
volatile.

1.4 Multi-Tiered Architecture of Data Warehouse

A data warehouse typically has a three-tier architecture:

Three-Tier Architecture:
• Tier 1 — Bottom Tier (Data Sources Layer): Consists of the source systems — operational
databases, flat files, external data. An ETL (Extract, Transform, Load) tool extracts data,
transforms it, and loads it into the data warehouse.
• Tier 2 — Middle Tier (Data Warehouse / OLAP Server): The actual data warehouse or data
mart. Contains the integrated data. Supported by an OLAP server that provides
multidimensional views of data. Two types: ROLAP (Relational OLAP) and MOLAP
(Multidimensional OLAP).
• Tier 3 — Top Tier (Front-End Client Tools): Tools for querying, reporting, data mining, and
visualization. Includes query tools, report writers, analysis tools, and data mining tools.

Two-Tier Architecture:
Simpler alternative: source systems → data warehouse → end users. Less scalable but simpler to
implement.

Q: Explain the three-tier architecture of a Data Warehouse.

A: Three-tier architecture: Bottom tier has source data and ETL processes. Middle tier has the actual
data warehouse with OLAP server supporting multidimensional analysis. Top tier has client tools like
query tools, report writers, and data mining applications. This separation ensures scalability,
performance, and flexibility.

1.5 Data Warehouse Models

Enterprise Data Warehouse (EDW):

Data Warehousing & Data Mining — Complete Study Guide

Data Warehousing & Data Mining — Study Guide

A single, centralized warehouse that integrates data from the entire organization. Provides a corporate-
wide view of data. Covers all business subjects. High cost and complexity but maximum coverage.

Data Mart:
A subset of the enterprise data warehouse focused on a single department or subject area (e.g., Sales
Data Mart, Finance Data Mart). Two types:
• Dependent Data Mart: Sourced from the EDW. Consistent and accurate.
• Independent Data Mart: Sourced directly from operational systems. May cause inconsistency.

Virtual Warehouse:
A set of views over the operational databases. Does not physically store data. Efficient for some
purposes but may degrade operational system performance when queries are run.

Q: Explain Enterprise Warehouse, Data Mart, and Virtual Warehouse.

A: Enterprise Warehouse: Organization-wide centralized repository. Data Mart: Department-specific
subset, can be dependent (from EDW) or independent (from operational systems). Virtual Warehouse:
Views over operational databases — no physical separate storage, low cost but impacts operational
system performance.

1.6 Extraction, Transformation and Loading (ETL)

ETL is the backbone process of populating a data warehouse. It moves data from source systems to
the warehouse.

Three Phases:
• Extraction: Data is extracted from heterogeneous source systems (RDBMS, flat files, XML, web
sources). Two types: Initial extraction (one-time full load) and Incremental extraction (periodic
updates of changed data).
• Transformation: Extracted data is cleaned, validated, and transformed. Activities include: data
cleaning (removing duplicates, fixing errors), data integration (resolving naming conflicts), data
format conversion (date formats, currency), and aggregation.
• Loading: Transformed data is loaded into the data warehouse. Two methods: Full load
(complete refresh) and Incremental load (only new/changed records appended).

ETL Challenges:
• Data from multiple incompatible formats
• Handling large data volumes efficiently
• Maintaining data consistency during transformation
• Minimizing downtime during loading

Q: Explain the ETL process in detail.

A: ETL stands for Extract, Transform, Load. Extraction pulls data from source systems. Transformation
cleans, integrates, and formats the data — resolving inconsistencies, removing duplicates,
standardizing formats. Loading places the transformed data into the warehouse — either as a full load
(initial) or incremental updates (ongoing). ETL ensures data quality and consistency in the warehouse.

Data Warehousing & Data Mining — Complete Study Guide

Data Warehousing & Data Mining — Study Guide

1.7 Metadata Repository

Metadata is 'data about data'. In data warehousing, metadata describes the structure, content, and
origin of data stored in the warehouse.

Types of Metadata:
• Business Metadata: Information about the business meaning — what data represents, business
rules.
• Technical Metadata: Information about how data is stored — database schemas, table
definitions, data types.
• Operational Metadata: Logs of ETL processes — when data was loaded, source of data,
transformation rules applied.

Role of Metadata Repository:

• Helps users understand what data is available and what it means
• Tracks data lineage (where data came from)
• Supports ETL processes by defining mappings
• Enables impact analysis — understanding what is affected by a change

Q: What is a Metadata Repository? Explain its types.

A: Metadata is data about data. A metadata repository stores information about the data warehouse
contents. Types: Business metadata (meaning and business rules), Technical metadata (schemas,
data types, storage details), Operational metadata (ETL process logs, data lineage). It helps users
navigate the warehouse, understand data, and manage ETL processes.

1.8 Concept of Data Pond, Data Lake, Data Ocean

Data Pond:
A small, focused collection of raw data from a limited number of sources, typically used by a single
team or department. Less sophisticated than a data lake.

Data Lake:
A large, centralized repository that stores vast amounts of raw data in its native format (structured,
semi-structured, unstructured). Uses a schema-on-read approach — structure is applied when data is
read, not when stored. Technologies: Hadoop, Apache Spark.

Data Ocean:
A conceptual term for an enterprise-wide, massive-scale data repository that goes beyond the data
lake. Spans multiple data lakes and systems across the organization or even across organizations.
Handles petabytes/exabytes of data. Offers real-time data ingestion and advanced analytics.

Comparison:
• Data Pond: Small, structured, team-level
• Data Lake: Large, raw, unstructured, organization-level
• Data Ocean: Massive, enterprise-wide, real-time, cross-organization

Q: Differentiate between Data Lake and Data Warehouse.

Data Warehousing & Data Mining — Complete Study Guide

Data Warehousing & Data Mining — Study Guide

A: Data Warehouse: Structured, processed data; schema-on-write; designed for SQL analytics; high
cost; best for business intelligence. Data Lake: Raw, unprocessed data in any format; schema-on-read;
designed for big data analytics and ML; lower cost storage; best for data scientists and exploratory
analysis.

UNIT II — DATA WAREHOUSE MODELLING: DATA CUBE

AND OLAP

2.1 Data Cube: A Multidimensional Data Model

A Data Cube is a multidimensional representation of data that allows data to be modeled and viewed
from multiple perspectives (dimensions). Each dimension represents an attribute of the data.

Key Concepts:
• Dimension: A perspective or entity for analysis. E.g., Time, Product, Location, Customer.
• Measure: A numerical value that is analyzed across dimensions. E.g., Sales Amount, Quantity
Sold.
• Cell: The intersection of dimension values that holds the measure value.
• Cube: A 3D representation. Higher dimensions are called hypercubes.

Example:
A Sales cube might have dimensions: Time (Year, Quarter, Month), Product (Category, Brand, Item),
Location (Country, State, City). The measure is Sales Amount. A cell at [Q1, Laptop, India] =
₹5,00,000.

Cuboid Lattice:
For a cube with n dimensions, there are 2^n cuboids possible. These form a lattice of cuboids — from
the apex cuboid (all dimensions aggregated) to the base cuboid (finest granularity). For example, a 3D
cube (Time, Product, Location) has 2^3 = 8 cuboids.

Q: What is a Data Cube? Explain with an example.

A: A data cube is a multidimensional model for data warehousing. It has dimensions (like Time,
Product, Location) and measures (like Sales). Each cell of the cube stores a measure value at the
intersection of dimension values. For example, a Sales cube can show sales by (Year, Product,
Region). This enables quick multi-angle analysis. For n dimensions, 2^n cuboids are possible, forming
a lattice.

2.2 Stars, Snowflakes, and Fact Constellations

Star Schema:
The simplest and most common schema for data warehouses. One central fact table surrounded by
multiple dimension tables. Dimension tables are denormalized (not further decomposed).

Data Warehousing & Data Mining — Complete Study Guide

Data Warehousing & Data Mining — Study Guide

• Fact Table: Contains foreign keys to all dimension tables and the measures/metrics.
• Dimension Tables: One per dimension, denormalized, connected directly to the fact table.
• Advantage: Simple, fast queries, easy to understand.
• Disadvantage: Data redundancy in dimension tables.

Snowflake Schema:
An extension of the Star Schema where dimension tables are normalized — broken into sub-dimension
tables forming a snowflake shape.
• Advantage: Reduces data redundancy, saves storage.
• Disadvantage: More complex queries, multiple joins needed.

Fact Constellation (Galaxy Schema):

Multiple fact tables share common dimension tables. Used for complex modeling requirements. Also
called the Galaxy Schema.
• Example: Both Sales and Inventory fact tables share a Time and Product dimension table.
• Advantage: Supports multiple business processes.
• Disadvantage: Most complex schema, hardest to maintain.

Q: Differentiate between Star Schema and Snowflake Schema.

A: Star Schema: One fact table with denormalized dimension tables directly connected. Simple, fast,
but redundant. Snowflake Schema: Dimension tables are further normalized into sub-tables. Less
redundancy, saves storage, but requires more joins, making queries complex. Star schema is preferred
for performance; snowflake for storage efficiency.
Q: What is a Fact Constellation Schema?
A: Also called Galaxy Schema. It has multiple fact tables sharing common dimension tables. Used
when multiple business processes need to be modeled (e.g., Sales and Inventory sharing Time and
Product dimensions). Most flexible but most complex schema.

2.3 Dimensions: The Role of Concept Hierarchies

A Concept Hierarchy defines a sequence of mappings from a set of low-level concepts to higher-level,
more general concepts. Hierarchies enable drill-down and roll-up OLAP operations.

Types of Concept Hierarchies:

• Schema Hierarchy: Defined by the schema (total order). Example: day → month → quarter →
year.
• Set-Grouping Hierarchy: Values grouped based on sets. Example: {1,2,3,4} → Q1, {5,6,7,8} →
Q2.
• Operation-Derived Hierarchy: Derived from data operations. Example: customer grouped by
purchase frequency.
• Rule-Based Hierarchy: Defined by rules. Example: age: young (<30), middle-aged (30-60),
senior (>60).

Data Warehousing & Data Mining — Complete Study Guide

Data Warehousing & Data Mining — Study Guide

Example Hierarchies:
• Time: Second → Minute → Hour → Day → Week → Month → Quarter → Year
• Location: Street → City → State → Country → Continent
• Product: Brand → Category → Industry

Q: Explain concept hierarchies with examples.

A: A concept hierarchy organizes dimension values from most specific (low level) to most general (high
level). Time hierarchy: day → month → quarter → year. Location hierarchy: city → state → country.
They enable roll-up (going up) and drill-down (going down) OLAP operations. Types include schema
hierarchies (defined in schema), set-grouping hierarchies, rule-based hierarchies, and operation-
derived hierarchies.

2.4 Measures: Categorization and Computation

Measures are the numerical values stored in a data cube's fact table. They represent what is being
analyzed.

Types of Measures:
• Distributive Measures: Can be computed by dividing data into portions and computing the
aggregate. Examples: COUNT(), SUM(), MIN(), MAX(). These are fully distributive — easy to
compute in parallel.
• Algebraic Measures: Can be computed by applying algebraic functions to distributive measures.
Examples: AVG() = SUM()/COUNT(), Standard Deviation. Computed from a finite number of
distributive measures.
• Holistic Measures: Cannot be computed from sub-aggregates; require the entire dataset.
Examples: Median, Mode, Rank. Most expensive to compute.

Q: Explain the categorization of measures in OLAP.

A: Measures are categorized as: (1) Distributive — computed by partitioning data (SUM, COUNT, MIN,
MAX). (2) Algebraic — derived from distributive measures (AVG = SUM/COUNT, Standard Deviation).
(3) Holistic — require all data, cannot be computed from subsets (Median, Mode, Rank). Distributive
measures are cheapest to compute; holistic are most expensive.

2.5 OLAP Operations: Roll-up, Drill-down, Slice and Dice

OLAP (Online Analytical Processing) provides multidimensional interactive analysis of data. Key OLAP
operations allow analysts to view data at different granularities and from different perspectives.

Roll-up (Drill-up):
Aggregates data by climbing up a concept hierarchy or reducing a dimension. Moves from detailed data
to summary data.
Example: Roll up from City sales to State sales to Country sales. Sum sales for all cities in a state to
get state total.

Drill-down:

Data Warehousing & Data Mining — Complete Study Guide

Data Warehousing & Data Mining — Study Guide

The reverse of roll-up. Moves from summary data to detailed data by stepping down a hierarchy or
adding a new dimension.
Example: From Year sales, drill down to Quarter, then to Month, then to Day.

Slice:
Selects a single value for one dimension, resulting in a sub-cube with one fewer dimension.
Example: Slice the Sales cube for Time = 'Q1' — you get a 2D sub-cube of (Product x Location) for Q1
only.

Dice:
Selects two or more values for two or more dimensions, resulting in a sub-cube.
Example: Dice where Time = Q1 or Q2, Product = Laptop or Mobile, Location = India or USA.

Pivot (Rotate):
Rotates the data axes to provide an alternative presentation of data. Changes the orientation of the
data cube view.

Other Operations:
• Drill-across: Queries multiple fact tables linked by shared dimensions.
• Drill-through: Goes from the data cube to the backend relational database for row-level detail.

Q: Explain Roll-up, Drill-down, Slice, and Dice OLAP operations with examples.
A: Roll-up: Aggregates data going up a hierarchy (city → state → country). Drill-down: Breaks data into
finer detail going down a hierarchy (year → quarter → month). Slice: Selects one value for one
dimension reducing the cube by one dimension (e.g., Time=Q1 gives a Product×Location sub-cube).
Dice: Selects ranges for multiple dimensions resulting in a sub-cube (Time=Q1,Q2;
Product=Laptop,Mobile).
Q: What is OLAP? How does it differ from OLTP?
A: OLAP (Online Analytical Processing) is designed for complex queries, data analysis, and decision
support. OLTP (Online Transaction Processing) handles real-time transactional operations. OLAP:
historical, read-heavy, complex joins, few users, supports roll-up/drill-down. OLTP: current data, read-
write, simple queries, many users, no aggregation operations.

UNIT III — BASICS OF DATA MINING

3.1 Market Basket Analysis

Market Basket Analysis is a data mining technique used to discover relationships between items
purchased together. Originally applied to supermarket transaction data.
Goal: Find which items tend to be purchased together. Used for product placement, promotions, cross-
selling.

Core Concepts:

Data Warehousing & Data Mining — Complete Study Guide

Data Warehousing & Data Mining — Study Guide

• Transaction: A set of items bought together in one purchase. E.g., {Bread, Butter, Milk}.
• Itemset: Any subset of items. A k-itemset has k items.
• Support: Fraction of transactions containing a given itemset. Support({A,B}) = Transactions
containing both A and B / Total Transactions.
• Confidence: Conditional probability that B is bought given A is bought. Confidence(A→B) =
Support(A∪B) / Support(A).
• Lift: Measures how much more often A and B are bought together than expected. Lift(A→B) =
Confidence(A→B) / Support(B). Lift > 1 means positive correlation.

Q: What is Market Basket Analysis? Define Support and Confidence.

A: Market Basket Analysis finds items frequently bought together. Support of itemset X = |transactions
containing X| / |total transactions| — measures frequency. Confidence of rule A→B =
Support(A∪B)/Support(A) — measures reliability of the rule. Example: If Support({Bread,Butter})=0.4
and Support({Bread})=0.6, Confidence(Bread→Butter)=0.4/0.6=0.67, meaning 67% of customers who
buy bread also buy butter.

3.2 Frequent Itemsets, Closed Itemsets, and Association Rules

Frequent Itemset:
An itemset whose support is greater than or equal to a user-defined minimum support threshold
(min_sup). Used as the basis for association rule mining.

Closed Itemset:
An itemset X is closed if there is no proper superset of X that has the same support as X. Closed
itemsets are a lossless compression of frequent itemsets — they preserve all support information
without redundancy.

Maximal Itemset:
An itemset X is maximal if none of its immediate supersets are frequent. Maximal itemsets are the
largest frequent itemsets but are lossy (support of subsets not preserved).

Association Rules:
Rules of the form A → B where A and B are disjoint itemsets. Interpreted as: 'If a transaction contains
A, it is likely to contain B.'
• Strong Association Rule: Support ≥ min_sup AND Confidence ≥ min_conf.
• Example: {Diaper} → {Beer} with Support=0.3, Confidence=0.7.

Two-Step Process for Association Rule Mining:

• Step 1: Find all frequent itemsets (using Apriori or FP-Growth).
• Step 2: Generate strong association rules from frequent itemsets.

Q: Differentiate between Frequent, Closed, and Maximal Itemsets.

A: Frequent Itemset: support ≥ min_sup. Closed Itemset: frequent itemset with no superset having the
same support — compact and lossless representation. Maximal Itemset: frequent itemset with no
frequent superset — most compact but lossy (can't recover support of subsets). Relationship: Maximal
⊆ Closed ⊆ Frequent Itemsets.
Data Warehousing & Data Mining — Complete Study Guide
Data Warehousing & Data Mining — Study Guide

3.3 Apriori Algorithm: Finding Frequent Itemsets by Confined Candidate

Generation
Apriori is the classic algorithm for mining frequent itemsets for association rule mining, proposed by
Agrawal and Srikant (1994).

Apriori Property (Anti-monotone):

Any subset of a frequent itemset must be frequent. Equivalently, if an itemset is infrequent, all its
supersets are also infrequent. This allows pruning of candidates.

Algorithm Steps:
• Step 1: Scan database to find all frequent 1-itemsets (L1). Itemsets with support ≥ min_sup are
frequent.
• Step 2: Use L1 to generate candidate 2-itemsets (C2). Scan database to find frequent 2-
itemsets (L2).
• Step 3: Use L(k-1) to generate candidates Ck. Prune candidates using Apriori property. Scan
database to find Lk.
• Step 4: Repeat until no new frequent itemsets found.

Candidate Generation (Join Step):

Join L(k-1) with itself to generate Ck: two (k-1)-itemsets are joined if they share the first k-2 items.

Candidate Pruning (Prune Step):

Remove any candidate c from Ck if any (k-1)-subset of c is not in L(k-1).

Example:
Transactions: T1={A,B,C}, T2={A,C}, T3={A,B}, T4={A,B,C,D}. min_sup=50% (2 transactions).
• L1 = {A:4, B:3, C:3, D:1} → frequent: {A},{B},{C} (D pruned, support=1<2)
• C2 = {AB,AC,BC}. After scan: {AB:3, AC:3, BC:2} → all frequent.
• C3 = {ABC}. Scan: {ABC:2} → frequent. Final: L3={ABC}.

Drawbacks of Apriori:
• Multiple database scans required (one per itemset size)
• Huge number of candidate itemsets generated
• Tedious database scans for counting support

Q: Explain the Apriori Algorithm with an example.

A: Apriori finds frequent itemsets using the anti-monotone property: subsets of frequent itemsets are
frequent; supersets of infrequent itemsets are infrequent. Steps: (1) Find frequent 1-itemsets. (2) Join
frequent (k-1)-itemsets to get k-candidates. (3) Prune candidates where any subset is infrequent. (4)
Scan DB to count support. (5) Repeat. Drawback: Multiple DB scans and large candidate generation.
Example: Given min_sup=2, transactions T1={A,B,C}, T2={A,C}, T3={A,B}, T4={A,B,C,D}, we find
L1={A,B,C}, L2={AB,AC,BC}, L3={ABC}.

3.4 Mining Frequent Itemsets Using Vertical Data Format

Data Warehousing & Data Mining — Complete Study Guide

Data Warehousing & Data Mining — Study Guide

The Vertical Data Format approach, used by the ECLAT (Equivalence Class Clustering and bottom-up
Lattice Traversal) algorithm, represents each item by its transaction ID list (tid-list).

Horizontal vs Vertical Format:

• Horizontal Format: Transaction-based. TID: Itemset. E.g., T1: {A,B,C}, T2: {A,C}.
• Vertical Format: Item-based. Itemset: TID-list. E.g., A: {T1,T2,T3,T4}, B: {T1,T3,T4}.

ECLAT Algorithm:
• Step 1: Convert horizontal format to vertical (item: TID-list).
• Step 2: Support of an itemset = size of its TID-list.
• Step 3: To find support of itemset {A,B}: intersect TID-list(A) ∩ TID-list(B).
• Step 4: If intersection size ≥ min_sup, {A,B} is frequent.

Advantages:
• No repeated database scans after initial scan — all support counting via set intersection
• Faster than Apriori for dense datasets
• TID-list intersections are fast operations

Disadvantage:
• TID-lists can be very large, consuming significant memory

Q: Explain mining frequent itemsets using Vertical Data Format.

A: Vertical data format assigns each item a TID-list (transaction ID list). Support = size of TID-list. To
find support of {A,B}: intersect TID-list(A) and TID-list(B). This is the basis of ECLAT algorithm.
Advantages: Only one DB scan needed, then set intersections. Disadvantage: High memory usage for
large datasets.

3.5 Mining Closed and Max Patterns

Mining Closed Itemsets — CHARM Algorithm:
CHARM simultaneously mines both the itemset space and the TID-list space (tidset space). It uses the
following four properties:
• If tidset(A)=tidset(B): Both have same transactions. Replace A by A∪B everywhere and remove
B.
• If tidset(A)⊂tidset(B): Every transaction with A also has B. Replace A by A∪B, keep B.
• If tidset(B)⊂tidset(A): Replace B by A∪B, keep A.
• If tidset(A)≠tidset(B): Explore both.

Mining Maximal Frequent Itemsets — MaxMiner Algorithm:

MaxMiner uses a breadth-first search approach and performs superset frequency pruning: if an itemset
is frequent, mark all its subsets as frequent without verifying. Efficiently finds the boundary between
frequent and infrequent itemsets.

Why Mine Closed/Max Patterns?

• Frequent itemset space can be exponentially large.
• Closed itemsets are a lossless compression — no information lost.

Data Warehousing & Data Mining — Complete Study Guide

Data Warehousing & Data Mining — Study Guide

• Max itemsets are most compact but lossy.

• Fewer patterns are more manageable for users.

Q: Why are Closed and Max Patterns preferred over all Frequent Itemsets?
A: All frequent itemsets can be exponentially many. Closed itemsets are a lossless compact
representation — support of any itemset can be derived from closed itemsets. Maximal itemsets are the
most compact but are lossy (sub-itemset supports not recoverable). Mining closed/max patterns
reduces the output size while preserving essential information.

UNIT IV — CLASSIFICATION TECHNIQUES

4.1 Introduction to Classification

Classification is a supervised learning technique in data mining that predicts the class label of an
unknown sample based on a trained model.

Key Terms:
• Training Set: Labeled data used to build the model.
• Test Set: Unlabeled data used to evaluate model accuracy.
• Class Label: The category/output attribute being predicted (e.g., Yes/No, Spam/Not-Spam).
• Model: The classification function learned from training data.

Steps in Classification:
• Step 1 — Learning (Training): Classification algorithm builds a model from training data.
• Step 2 — Classification (Testing): Model is applied to test data to predict class labels.
• Step 3 — Evaluation: Model accuracy is measured on test data.

Common Classification Methods:

• Decision Trees
• Naive Bayes Classifier
• Rule-Based Classification (IF-THEN)
• k-Nearest Neighbors (k-NN)
• Support Vector Machines (SVM)
• Neural Networks

Model Evaluation Metrics:

• Accuracy = (TP + TN) / (TP + TN + FP + FN)
• Precision = TP / (TP + FP)
• Recall = TP / (TP + FN)
• F1-Score = 2 × (Precision × Recall) / (Precision + Recall)

Q: What is Classification in Data Mining? Explain with steps.

Data Warehousing & Data Mining — Complete Study Guide

Data Warehousing & Data Mining — Study Guide

A: Classification predicts the class of unknown instances by learning from labeled training data. Steps:
(1) Training: learn a model from labeled training data. (2) Testing: apply model to test data. (3)
Evaluation: measure accuracy. Supervised learning because class labels are known during training.
Example: Classifying emails as spam/not-spam based on training on labeled emails.

4.2 Decision Tree — Induction, Attribute Selection, Tree Pruning

A Decision Tree is a flowchart-like tree structure where each internal node represents a test on an
attribute, each branch represents an outcome of the test, and each leaf node represents a class label.

Decision Tree Induction:

Algorithm (ID3/C4.5/CART) builds the tree top-down using a divide-and-conquer strategy:
• Select the best attribute to split on (using an attribute selection measure).
• Create a node for this attribute.
• Partition training data by attribute values.
• Recursively apply to each partition.
• Stop when: all samples in a node belong to same class, no attributes remain, or no samples
remain.

Attribute Selection Measures:

• Information Gain (ID3): Measures reduction in entropy after split. Select attribute with highest
information gain. Biased towards attributes with many values.
• Gain Ratio (C4.5): Corrects bias of information gain by normalizing by split information. Gain
Ratio = Information Gain / Split Information.
• Gini Index (CART): Measures impurity. Gini(T) = 1 - Σ(pi²). Select attribute with lowest Gini
index after split.

Entropy Formula:
Entropy(S) = -Σ pi × log2(pi), where pi is the proportion of class i in set S. Entropy = 0 means pure
node. Entropy = 1 means equally mixed.

Information Gain Formula:

Gain(A) = Entropy(S) - Σ |Sv|/|S| × Entropy(Sv), where Sv is the subset for value v of attribute A.

Tree Pruning:
Pruning removes branches that overfit the training data. Two types:
• Pre-pruning (Early Stopping): Stop growing the tree early — stop if gain below threshold, or
using chi-square test.
• Post-pruning: Fully grow tree then remove subtrees/branches. Methods: Cost Complexity
Pruning, Reduced Error Pruning, Minimum Description Length.

Advantages of Decision Trees:

• Easy to understand and visualize
• Handles both numerical and categorical data
• No normalization needed
• Feature selection built-in

Disadvantages:
Data Warehousing & Data Mining — Complete Study Guide
Data Warehousing & Data Mining — Study Guide

• Prone to overfitting
• Unstable — small data changes cause large tree changes
• Biased with imbalanced datasets

Q: Explain Decision Tree Induction. What is Information Gain?

A: Decision tree induction builds a tree top-down. At each step, the best attribute is selected using
information gain. Information Gain = Entropy(parent) - weighted sum of child entropies. Entropy = -Σ
pi×log2(pi). Higher gain = better split. The algorithm recursively partitions data until leaves are pure or
stopping criteria met. Example: To classify whether to play tennis, attributes like Outlook, Humidity,
Wind are evaluated by information gain to determine root and branches.
Q: What is Tree Pruning? Differentiate pre-pruning and post-pruning.
A: Tree pruning reduces overfitting. Pre-pruning stops tree growth early using thresholds on gain or
significance tests. Post-pruning grows the full tree then removes branches — cheaper subtrees replace
complex ones based on test error. Post-pruning generally gives better results as it has full information
about the tree structure.

4.3 Bayes Classification Methods

Bayes Theorem:
Bayes Theorem provides a way to compute posterior probability from prior probability and likelihood.
P(H|X) = P(X|H) × P(H) / P(X)
• P(H|X): Posterior probability — probability of hypothesis H given observed data X.
• P(X|H): Likelihood — probability of observing X given H is true.
• P(H): Prior probability of H.
• P(X): Prior probability of X (normalizing constant).

Naive Bayes Classifier:

Assumes class conditional independence — each attribute is independent of others given the class.
Despite this 'naive' assumption, it works remarkably well in practice, especially for text classification.

Classification Rule:
Given tuple X = (x1, x2, ..., xn), assign X to class Ci that maximizes P(Ci|X) ∝ P(Ci) × Π P(xk|Ci).

Steps:
• Step 1: Compute prior P(Ci) = frequency of class Ci in training data.
• Step 2: For each attribute, compute P(xk|Ci) from training data.
• Step 3: For a new X, compute P(Ci) × Π P(xk|Ci) for each class.
• Step 4: Assign X to class with maximum value.

Laplacian Correction:
If P(xk|Ci) = 0 for any attribute, the entire product is zero. Fix: add 1 to each count (Laplace smoothing).
P(xk|Ci) = (count + 1) / (total count + number of unique values).

Advantages:
• Fast, simple, and easy to implement
• Works well with small training data
Data Warehousing & Data Mining — Complete Study Guide
Data Warehousing & Data Mining — Study Guide

• Handles missing values

• Good for text classification (spam filtering, sentiment analysis)

Disadvantages:
• Naive independence assumption often violated
• Poor probability estimates when independence doesn't hold

Q: Explain the Naive Bayes Classifier with steps.

A: Naive Bayes classifies by applying Bayes Theorem with independence assumption. Steps: (1)
Compute P(Ci) for each class. (2) For each class and attribute value, compute P(xk|Ci). (3) For new
instance X, compute P(Ci)×∏P(xk|Ci) for each class. (4) Predict class with highest posterior. The 'naive'
assumption is that attributes are conditionally independent given the class. Laplace smoothing handles
zero probabilities.
Q: State and explain Bayes Theorem.
A: Bayes Theorem: P(H|X) = P(X|H)×P(H)/P(X). P(H|X) is posterior (probability of hypothesis after
seeing data), P(X|H) is likelihood, P(H) is prior, P(X) is evidence. In classification, H is a class and X is
the observed tuple. We classify X into the class with highest posterior probability.

4.4 Rule-Based Classification Using IF-THEN Rules

Rule-Based Classification uses a set of IF-THEN rules for classification. Each rule covers a subset of
the training data.

IF-THEN Rule Structure:

IF (condition1 AND condition2 AND ...) THEN class = Ci
Example: IF age = young AND income = high THEN buys_computer = yes

Rule Properties:
• Coverage: Fraction of training tuples satisfying the rule's antecedent.
• Accuracy: Fraction of rule-covered tuples that are correctly classified.

Conflict Resolution:
When multiple rules fire for one tuple:
• Size Ordering: Prefer the rule with most conditions (most specific).
• Class-Based Ordering: Order by class prevalence.
• Rule-Based Ordering: Order rules by accuracy, coverage, or other measures.

Extracting Rules from Decision Trees:

Each path from root to leaf forms one rule. Antecedent = conjunction of tests along path. Consequent =
leaf class label. Pruning removes redundant conditions.

Sequential Covering Algorithm:

• Learn one rule that covers many positive examples.
• Remove covered examples.
• Repeat until all positives covered.

FOIL (First Order Inductive Learner):

Data Warehousing & Data Mining — Complete Study Guide
Data Warehousing & Data Mining — Study Guide

Adds conditions to a rule one at a time, selecting condition that maximizes FOIL gain (measures
improvement in coverage of positive vs negative examples).

Q: Explain Rule-Based Classification. How are rules extracted from Decision Trees?
A: Rule-Based Classification uses IF-THEN rules. Each rule: IF (conditions) THEN class. Rules
extracted from decision trees: each root-to-leaf path → one rule; path tests → antecedent conditions;
leaf class → consequent. Redundant conditions are removed. Rules may conflict — resolved by size
ordering (most specific wins), class ordering, or rule priority ordering. A default rule handles unclassified
tuples.

UNIT V — CLUSTER ANALYSIS

5.1 Introduction to Clustering

Clustering is an unsupervised learning technique that groups similar data objects into clusters such that
objects within a cluster are more similar to each other than to objects in other clusters. No class labels
are used.
Definition: Clustering is the process of organizing objects into groups (clusters) whose members are
similar in some way.

Characteristics of Good Clustering:

• High intra-cluster similarity (objects within a cluster are similar)
• Low inter-cluster similarity (objects in different clusters are dissimilar)

Applications of Clustering:
• Customer Segmentation: Group customers by purchasing behavior for targeted marketing.
• Document Clustering: Group similar documents for information retrieval.
• Image Segmentation: Group pixels by color/intensity.
• Anomaly Detection: Outliers don't belong to any cluster.
• Bioinformatics: Group genes with similar expression patterns.

Similarity/Distance Measures:
• Euclidean Distance: d(x,y) = √Σ(xi - yi)². Most common for continuous attributes.
• Manhattan Distance: d(x,y) = Σ|xi - yi|. Less sensitive to outliers.
• Cosine Similarity: Measures angle between vectors. Used for text data.
• Jaccard Similarity: For binary/set data. |A∩B| / |A∪B|.

Q: What is Clustering? How does it differ from Classification?

A: Clustering groups similar objects without predefined class labels (unsupervised). Classification
predicts predefined class labels using labeled training data (supervised). Clustering discovers hidden
structure; classification builds a model to predict known classes. Example: Clustering groups customers
by behavior; Classification predicts whether a customer will churn.

Data Warehousing & Data Mining — Complete Study Guide

Data Warehousing & Data Mining — Study Guide

5.2 Cluster Analysis: Features and Applications

Types of Clustering Methods:
• Partitioning Methods: Divide data into k non-overlapping clusters. Example: k-Means, k-
Medoids.
• Hierarchical Methods: Build a tree (dendrogram) of clusters. Example: AGNES, DIANA.
• Density-Based Methods: Clusters are dense regions separated by sparse regions. Example:
DBSCAN.
• Grid-Based Methods: Data space quantized into grids. Example: STING, CLIQUE.
• Model-Based Methods: Assume statistical models for clusters. Example: EM algorithm, GMM.

Requirements of Clustering Algorithms:

• Scalability: Handle large datasets.
• Ability to handle different attribute types: Numerical, categorical, mixed.
• Discovery of clusters with arbitrary shape.
• Minimal requirements for domain knowledge.
• Ability to handle noise and outliers.
• Insensitivity to input order.
• Interpretability and usability.

Q: What are the requirements of a good clustering algorithm?

A: A good clustering algorithm should: (1) be scalable to large datasets, (2) handle various attribute
types, (3) discover arbitrary shaped clusters, (4) require minimal user input, (5) handle noise and
outliers, (6) be insensitive to input order, (7) produce interpretable results, (8) work well with high-
dimensional data.

5.3 Partitioning Methods: k-Means and k-Medoids

k-Means Algorithm:
The most popular clustering algorithm. Partitions n objects into k clusters by minimizing the sum of
squared distances from each point to its cluster centroid.

Algorithm Steps:
• Step 1: Choose k initial centroids (randomly or using heuristics).
• Step 2: Assign each object to the nearest centroid (forming k clusters).
• Step 3: Recompute centroid of each cluster (mean of all objects in cluster).
• Step 4: Repeat Steps 2-3 until centroids no longer change (convergence).

Objective Function:
Minimize E = Σ Σ |x - mean(Ci)|², where the sum is over all clusters and all points in each cluster.

Advantages of k-Means:
• Simple and efficient — O(tkn) where t=iterations, k=clusters, n=objects
• Works well for spherical clusters

Disadvantages of k-Means:

Data Warehousing & Data Mining — Complete Study Guide

Data Warehousing & Data Mining — Study Guide

• Must specify k in advance

• Sensitive to outliers (outliers distort centroids)
• Works only for numerical data
• Sensitive to initial centroid selection
• Cannot handle non-convex clusters

k-Medoids (PAM — Partitioning Around Medoids):

Instead of using the mean (centroid), k-Medoids uses actual data points as cluster representatives
(medoids). A medoid is the most centrally located object in a cluster.

k-Medoids Algorithm Steps:

• Step 1: Randomly select k objects as initial medoids.
• Step 2: Assign each non-medoid object to nearest medoid.
• Step 3: For each medoid m and each non-medoid object o, compute cost of swapping m with o.
• Step 4: If total cost decreases after swap, perform the swap.
• Step 5: Repeat until no improvement.

Advantages of k-Medoids:
• More robust to outliers than k-Means (medoid is actual data point)
• Works with any distance measure
• Works with categorical data

Disadvantages:
• O(k(n-k)²) per iteration — expensive for large n
• Still requires k to be specified

Q: Explain the k-Means algorithm with an example.

A: k-Means partitions data into k clusters. Steps: (1) Initialize k centroids randomly. (2) Assign each
point to nearest centroid. (3) Recompute centroids as mean of assigned points. (4) Repeat 2-3 until
convergence. Example: k=2 for points {2,4,10,12,3,11,20}: Initial centroids 2 and 12. Assign:
cluster1={2,4,3}, cluster2={10,12,11,20}. New means: 3, 13.25. Reassign. Converge. Weakness:
sensitive to outliers and initial selection.
Q: Compare k-Means and k-Medoids.
A: k-Means uses mean of cluster as centroid — fast but sensitive to outliers and handles only numerical
data. k-Medoids uses an actual data point (medoid) as representative — more robust to outliers, works
with categorical data, but is computationally more expensive O(k(n-k)²). Both require k to be pre-
specified.

5.4 Hierarchical Methods: Agglomerative vs Divisive

Hierarchical clustering creates a hierarchy of clusters represented as a dendrogram (tree diagram).
Two strategies:

Agglomerative (Bottom-Up) — AGNES:

• Start: Each object is its own cluster (n clusters).

Data Warehousing & Data Mining — Complete Study Guide

Data Warehousing & Data Mining — Study Guide

• Merge: Iteratively merge the two closest clusters into one.

• Stop: All objects are in one cluster (or desired k clusters reached).
• Result: A dendrogram showing merge history. Cut dendrogram at desired level to get k clusters.

Divisive (Top-Down) — DIANA:

• Start: All objects in one cluster.
• Split: Iteratively split the most heterogeneous cluster.
• Stop: Each object is its own cluster (or desired k reached).

Linkage Criteria (How to measure distance between clusters):

• Single Linkage (MIN): Distance between two clusters = minimum distance between any two
points in the clusters. Produces elongated, chain-like clusters.
• Complete Linkage (MAX): Distance = maximum distance between any two points. Produces
compact, spherical clusters.
• Average Linkage: Distance = average of all pairwise distances between points in two clusters.
• Centroid Linkage: Distance between centroids of two clusters.
• Ward's Method: Minimize increase in total within-cluster variance after merge.

Dendrogram:
A tree diagram showing the order and distance of merges/splits. The y-axis shows the distance at
which clusters are merged. Horizontal cuts at different heights give different numbers of clusters.

Advantages:
• No need to specify k in advance
• Produces hierarchy of clusters (useful insight)
• Deterministic (no random initialization)

Disadvantages:
• O(n²) or O(n² log n) time and O(n²) space — not scalable
• Cannot undo a merge/split (greedy)
• Sensitive to noise and outliers

Q: Compare Agglomerative and Divisive Hierarchical Clustering.

A: Agglomerative (AGNES, bottom-up): starts with n individual clusters, merges closest pairs iteratively
until one cluster remains. Divisive (DIANA, top-down): starts with one cluster, splits into smaller
clusters. Both produce dendrograms. Agglomerative is more commonly used and computationally
simpler. Divisive is more expensive but conceptually useful. Both require choosing a linkage criterion
(single, complete, average, Ward's).
Q: What is a Dendrogram? How is it used to determine the number of clusters?
A: A dendrogram is a tree diagram used to visualize the result of hierarchical clustering. Each leaf is a
data point; branches show merges (agglomerative) or splits (divisive). The y-axis shows the distance at
which merging occurs. To get k clusters, cut the dendrogram horizontally at a height that results in k
branches. Larger gaps between merge levels suggest more natural cluster boundaries.

Q: What is DBSCAN? How does it differ from k-Means?

A: DBSCAN (Density-Based Spatial Clustering of Applications with Noise) defines clusters as dense
regions of points. Parameters: epsilon (neighborhood radius) and MinPts (minimum points in
Data Warehousing & Data Mining — Complete Study Guide
Data Warehousing & Data Mining — Study Guide

neighborhood). Points: Core (dense neighborhood), Border (reachable from core), Noise (outliers).
Advantages over k-Means: no need to specify k, discovers arbitrary shaped clusters, handles
noise/outliers. Disadvantage: sensitive to epsilon and MinPts parameters.

QUICK REVISION SUMMARY

Key Formulas to Remember

• Entropy: E(S) = -Σ pi × log2(pi)
• Information Gain: Gain(A) = E(S) - Σ |Sv|/|S| × E(Sv)
• Gini Index: Gini(T) = 1 - Σ(pi²)
• Support: Support(X) = |Trans containing X| / |Total Trans|
• Confidence: Conf(A→B) = Support(A∪B) / Support(A)
• Lift: Lift(A→B) = Conf(A→B) / Support(B)
• Bayes: P(H|X) = P(X|H) × P(H) / P(X)
• Euclidean Distance: d(x,y) = √Σ(xi - yi)²
• k-Means Objective: E = Σ Σ |x - mean(Ci)|²

Algorithm Comparison Table

• Apriori: Multiple DB scans, large candidate sets, easy to understand.
• ECLAT: One DB scan, set intersection for support, memory intensive.
• FP-Growth (bonus): Uses FP-tree, two DB scans, fastest for dense data.
• ID3: Information Gain for splitting, biased to multi-valued attributes.
• C4.5: Gain Ratio, handles continuous attributes and missing values.
• CART: Gini Index, produces binary trees.
• k-Means: Fast O(tkn), sensitive to outliers, needs k.
• k-Medoids: Robust, expensive O(k(n-k)²), needs k.
• AGNES/Agglomerative: Bottom-up, produces dendrogram, O(n²).
• DIANA/Divisive: Top-down, produces dendrogram, more expensive.

Key Differences to Remember

• OLTP vs OLAP: Transaction vs Analysis, Normalized vs Denormalized, Current vs Historical.
• Data Lake vs DW: Raw/unstructured vs Processed/structured, Schema-on-read vs Schema-on-
write.
• Frequent vs Closed vs Maximal Itemsets: Maximal ⊆ Closed ⊆ Frequent.
• Pre-pruning vs Post-pruning: Stop early vs Grow fully then prune.
• Classification vs Clustering: Supervised (labels known) vs Unsupervised (no labels).
• Star vs Snowflake Schema: Denormalized (fast, redundant) vs Normalized (efficient, complex).
Data Warehousing & Data Mining — Complete Study Guide
Data Warehousing & Data Mining — Study Guide

• k-Means vs k-Medoids: Mean centroid (fast, sensitive) vs Actual point (robust, slow).
• Agglomerative vs Divisive: Bottom-up (merge) vs Top-down (split).

Important Definitions
• ETL: Extract-Transform-Load — process of populating a data warehouse.
• OLAP: Online Analytical Processing — multidimensional data analysis.
• Support: Frequency of an itemset in transactions.
• Confidence: Conditional probability of consequent given antecedent.
• Entropy: Measure of impurity/uncertainty in a dataset.
• Centroid: Mean point of a cluster in k-Means.
• Medoid: Most central actual data point in a cluster in k-Medoids.
• Dendrogram: Tree diagram showing hierarchical cluster relationships.
• Apriori Property: Subsets of frequent itemsets are frequent (anti-monotone).
• Naive Bayes Assumption: Attributes are conditionally independent given class.

— END OF STUDY GUIDE — All the Best for Your Examination! —

Data Warehousing & Data Mining — Complete Study Guide