UNIT 3: DATA MINING TECHNIQUES AND APPLICATIONS

I. DATA MINING PROCESS (KNOWLEDGE DISCOVERY IN DATABASES - KDD)

Steps Involved in KDD Process

The KDD process is an iterative, multi-step framework for extracting knowledge from data.

[!TIP] Exam Focus: Be prepared to describe each step in 1-2 lines with an example. The process is cyclic—results from Interpretation may send you back to Selection/Preprocessing.

II. DATA PREPROCESSING

Data Transformation Strategies

Transformation prepares data for mining by converting it into appropriate forms.

Handling Missing Values

Common in real-world data. Choice impacts model bias/variance.

[!TIP] Exam Pitfall: "Filling with mean" is not always best—it reduces variance and can bias correlations. Mention this trade-off.

III. DATA WAREHOUSING AND OLAP

OLAP Operations & Systems

OLAP enables multi-dimensional analysis of summarized data.

OLAP System Types:

Snowflake Schema Design

A normalized variant of star schema where dimension tables are normalized into multiple related tables.

Case Study: University Data Warehouse

• Fact Table: Enrollment_Fact (Keys: student_key, course_key, semester_key, instructor_key; Measures: count, avg_grade)

• Dimensions:

  • Student (PK: student_key) → Normalized into Student (details) and Department (dept_id).

  • Course (PK: course_key) → Normalized into Course and Department.

  • Semester (PK: semester_key) → Normalized into Semester and Year.

  • Instructor (PK: instructor_key) → Normalized into Instructor and Department.

Conceptual Levels of Aggregation:

Base Level: avg_grade = actual grade for (Student, Course, Semester, Instructor).

Higher Levels: avg_grade = average grade for (Course, Semester) or (Department, Year), etc.

[!DIAGRAM]

DiagramSNOWFLAKE SCHEMA: University data warehouse with snowflake schema showing normalized dimension tables for Student->Department, Course->Department, Semester->Year, Instructor->Department, connected to central fact table Enrollment_Fact

IV. ASSOCIATION ANALYSIS

Association Rules & Negative Correlation

Rule: X → Y (X and Y are disjoint item sets).

• Support: P(X ∪ Y) – proportion of transactions containing both.

• Confidence: P(Y|X) = support(X ∪ Y) / support(X) – conditional probability.

Critical Insight: High support & confidence do NOT imply positive correlation.

Example:

Let X = {Milk}, Y = {Coke}.

Total transactions = 100.

support(X) = 70, support(Y) = 60, support(X∪Y) = 50.

Confidence = 50/70 ≈ 0.714 (high).

But: P(Y) = 0.60, P(Y|X)=0.714 → P(Y|X) > P(Y) suggests positive correlation?

Check: P(X∪Y) = 0.50 vs P(X)*P(Y) = 0.42. Since 0.50 > 0.42, they are positively correlated.

For Negative Correlation: Need P(X∪Y) < P(X)*P(Y).

Example: X={Bread}, Y={Diet Coke}. If support(X)=80, support(Y)=20, support(X∪Y)=10.

Then P(X)*P(Y)=0.16, P(X∪Y)=0.10 → negatively correlated, yet rule Bread → Diet Coke could have confidence 10/80=0.125 (above min. threshold) and support 0.10 (above min.). Thus, strong rules can be negatively correlated.

Apriori Algorithm & Proof

Prior Knowledge (Apriori Property):

All non-empty subsets of a frequent itemset must also be frequent.

Proof (by contradiction):

Let L be a frequent itemset (support(L) ≥ min_sup).

Assume a subset S ⊂ L is not frequent (support(S) < min_sup).

Any transaction containing L must also contain S (since S ⊂ L).

Therefore, support(L) ≤ support(S).

But support(S) < min_sup implies support(L) < min_sup, contradicting that L is frequent.

Hence, all subsets of a frequent itemset must be frequent.

\boxed{\text{If } L \text{ is frequent, then } \forall S \subset L, S \neq \emptyset, \text{ support}(S) \ge \text{min_sup}}

Apriori Algorithm Steps:

1. Initialize: C₁ = all 1-itemsets. Scan DB to find frequent L₁ (support ≥ min_sup).

2. Iterate (k=2,3,...):

   • Candidate Generation: Cₖ = Lₖ₋₁ ⋈ Lₖ₋₁ (self-join), then prune any candidate with a (k-1)-subset not in Lₖ₋₁ (using Apriori property).

   • Pruning: Scan DB, count support of Cₖ.

   • Frequent Itemsets: Lₖ = {c ∈ Cₖ | support(c) ≥ min_sup}.

3. Stop when Lₖ is empty.

4. Generate Rules: From frequent itemsets L, generate rules X → Y (X∪Y=L) with confidence ≥ min_conf.

[!TIP] Exam Must-Know: Be able to generate candidates for k=2 from L₁, and prune using subset property. The algorithm scans DB k times (once per level).

V. CLASSIFICATION

Decision Tree Pruning

Purpose: Combat overfitting (tree too complex, captures noise).

• Pre-pruning (Early Stopping): Halt tree growth during induction.

  • Methods: Stop if split doesn't improve purity (e.g., info gain < threshold), limit tree depth, minimum samples per leaf.

  • Advantage: Computationally efficient.

  • Disadvantage: Myopic; may stop too early.

• Post-pruning (Backward Pruning): Grow full tree, then remove branches.

  • Methods: Error rate pruning (use separate validation set), cost-complexity pruning.

  • Advantage: More robust; considers full tree.

  • Disadvantage: Computationally expensive.

Drawback of Separate Validation Set for Pruning:

• Reduces Training Data Size: Data split into training, validation, test → smaller training set may lead to underfitting or higher variance in the induced tree.

• Potential Bias: Validation set may not be perfectly representative of the full data distribution, leading to suboptimal pruning decisions.

• Variance in Evaluation: Pruning decisions become sensitive to the specific validation set split, reducing stability.

[!TIP] Exam Answer Structure: 1) State purpose (overfitting). 2) Contrast pre vs post. 3) For drawback: mention data inefficiency and evaluation instability.

VI. CLUSTERING ANALYSIS

k-means Clustering

Goal: Partition n objects into k clusters minimizing within-cluster sum of squares (WCSS).

Algorithm:

1. Initialize: Choose k initial centroids (randomly or by heuristic).

2. Repeat until convergence:

   • Assignment Step: Assign each point to nearest centroid (using Euclidean distance).

   • Update Step: Recompute centroids as mean of assigned points.

3. Output: Cluster assignments.

Numerical Example (k=2):

Data: {(1,1), (1,2), (2,1), (5,5), (6,5), (5,6)}

Init centroids: c1=(1,1), c2=(5,5).
Iteration 1 Assignment:

Cluster1: {(1,1),(1,2),(2,1)}; Cluster2: {(5,5),(6,5),(5,6)}.
Update: c1_new = ((1+1+2)/3, (1+2+1)/3) = (1.33, 1.33); c2_new = ((5+6+5)/3, (5+5+6)/3) = (5.33, 5.33).

Repeat until centroids stabilize.

Limitation (Local Optimum):

k-means is sensitive to initial centroids and may converge to a suboptimal partition (local minimum of WCSS).
Example: With k=2 and data in three dense groups, bad initialization may merge two groups into one cluster, yielding higher WCSS than the global optimum.

\boxed{\text{WCSS} = \sum_{i=1}^{k} \sum_{\mathbf{x} \in C_i} |\mathbf{x} - \boldsymbol{\mu}_i|^2}

where $$\displaystyle \boldsymbol{\mu}_i $$ is centroid of cluster $$\displaystyle C_i $$.

Clustering for Multi-Granularity Outlier Detection

Clusters form a hierarchy (e.g., via hierarchical clustering or running k-means with varying k). Outliers can exist at different granularities:

1. Global Outliers: Far from all clusters (detected at coarse granularity).

2. Local Outliers: In sparse regions near a cluster (detected at finer granularity).

3. Collective Outliers: A small group of points forming a micro-cluster (detected as outlier cluster at some level).

Method:

• Build clustering hierarchy (e.g., by repeatedly clustering clusters or using density-based clustering like DBSCAN with varying eps).

• At each level, identify points with low density or far from cluster centroids.

• Points flagged as outliers at multiple levels are strong candidates.

• Advantage: Captures outliers relative to their local context, not just global density.

VII. OUTLIER DETECTION (ADVANCED)

Semi-Supervised Outlier Detection

Scenario: Training data has few labeled outliers and many unlabeled objects (which may be normal or outliers).

Advantage of Using Unlabeled Objects:

• Better Model of Normal Behavior: Unlabeled data (mostly normal) provides a richer, more representative sample of the normal class distribution. This helps in building a more accurate boundary between normal and outlier.

• Reduces Bias: With only few labeled outliers, a purely supervised model may overfit to those specific outlier patterns. Unlabeled data acts as a regularizer, forcing the model to learn the dominant normal patterns more robustly.

• Semi-supervised frameworks (e.g., using EM, self-training, or positive-unlabeled learning) leverage unlabeled data to refine the decision boundary by assuming most unlabeled data are normal, thus improving detection accuracy for unseen outliers.

Example: In fraud detection, only a tiny fraction of transactions are labeled fraud. Using millions of unlabeled (mostly legitimate) transactions helps model "normal" spending patterns better, making anomalous fraud more detectable.

VIII. SPECIALIZED DATA MINING TYPES

Web Mining

Application of data mining techniques to web data.

Spatial and Temporal Data Mining

[!TIP] Distinguish: Spatial = where (geography); Temporal = when (time). Often combined (spatio-temporal).

IX. SOCIAL AND ETHICAL ISSUES

Security and Privacy Issues in Data Mining

Potential Countermeasures:

• Technical: Anonymization (k-anonymity, l-diversity), Differential Privacy, Encryption, Secure Multi-party Computation.

• Policy/Legal: Informed consent, data ownership rights (GDPR, CCPA), audit trails, ethical guidelines for data scientists.

• Organizational: Privacy-by-design, data governance frameworks, transparency reports.

Ethical Principle: Beneficence (do good) vs Non-maleficence (do no harm). Mining should benefit society without causing unjust harm or discrimination.