Data Mining (IT-603 (B)) - Unit 4 Short Notes

UNIT 4: Data Mining – Core Concepts, Techniques & Applications

1. Knowledge Discovery in Databases (KDD) Process

The KDD process is the comprehensive, iterative method for extracting useful knowledge from data. It is not synonymous with data mining; data mining is a single step within KDD.

Steps of the KDD Process:

1. Selection: Focus on a target dataset or subset relevant to the analysis.

2. Preprocessing: Clean the data (handle noise, missing values, outliers).

3. Transformation: Convert data into suitable forms (normalization, aggregation).

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

5. Interpretation/Evaluation: Assess and interpret mined patterns, potentially returning to earlier steps.

[!TIP] Exam Focus: Be prepared to describe the goal and key activities of each phase. Emphasize the iterative nature—results from evaluation often trigger reprocessing.

2. Data Warehousing and OLAP

A Data Warehouse (DW) is a subject-oriented, integrated, time-variant, non-volatile collection of data for decision support. OLAP (Online Analytical Processing) enables interactive, multidimensional analysis of DW data.

OLAP Architectures:

Core OLAP Operations (on a multidimensional cube):

• Roll-up (Drill-up): Aggregate data by climbing up a hierarchy (e.g., City → Country).

• Drill-down (Roll-down): Navigate from summary to detailed data (e.g., Year → Quarter → Month).

• Slice: Select a single dimension value, creating a sub-cube (e.g., Sales[Time=2023]).

• Dice: Select a sub-cube by specifying ranges on multiple dimensions.

• Pivot (Rotate): Reorient the cube to view data from a different perspective.

Data Warehouse Schemas:

• Star Schema: Central fact table (with measures/foreign keys) connected to denormalized dimension tables. Simple, fast queries.

• Snowflake Schema: Normalized version of the star schema. Dimension tables are split into multiple related tables. Reduces redundancy but increases join complexity.

Designing a Snowflake Schema: University Data Warehouse

• Fact Table: Academic_Fact(Student_ID, Course_ID, Semester_ID, Instructor_ID, Count, Avg_Grade)

• Dimensions: Hierarchical (e.g., Semester → Term → Year; Course → Department).

• Measures: Count (additive), Avg_Grade (semi-additive; average across time but not across students).

3. Data Preprocessing

Real-world data is often incomplete, noisy, and inconsistent.

Data Transformation Strategies:

• Normalization: Scale attributes to a small range.

  • Min-Max: $$\displaystyle x' = \frac{x - \min}{\max - \min} $$ → range $[0,1]$.

  • Z-Score (Standardization): $$\displaystyle x' = \frac{x - \mu}{\sigma} $$ → mean 0, std dev 1.

  • Decimal Scaling: $$\displaystyle x' = \frac{x}{10^j} $$ where $j$ is smallest integer such that $$\displaystyle |x'| < 1 $$.

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

• Generalization: Replace low-level values with higher-level concepts (e.g., age → age group).

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

• Attribute/Value Merging & Splitting: Combine or split attributes/values based on domain knowledge.

Handling Missing Values:

[!TIP] Common Pitfall: Never blindly apply mean imputation for skewed data; median is often more robust.

4. Association Rule Mining

Discovers interesting relationships (rules) among items in transactional databases.

Fundamentals:

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

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

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

• Confidence (c): Conditional probability of Y given X.

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

• Frequent Itemset: An itemset with support ≥ minimum support threshold (min_sup).

Apriori Algorithm: Core Principle (Apriori Property): All non-empty subsets of a frequent itemset must themselves be frequent.

Proof (by Contradiction): Let $I$ be a frequent itemset. Suppose a subset $S \subset I$ is not frequent ($$\displaystyle support(S) < min\_sup $$). Since $support(I) \leq support(S)$ (any transaction containing $I$ must contain $S$), it follows $$\displaystyle support(I) < min\_sup $$, contradicting that $I$ is frequent. ∎

Steps:

1. Candidate Generation (Cₖ): Generate candidate k-itemsets from frequent (k-1)-itemsets ($$\displaystyle L_{k-1} $$) using self-join.

2. Pruning: Remove candidates with any subset not in $$\displaystyle L_{k-1} $$ (using Apriori property).

3. Support Counting: Scan DB to count support of remaining candidates.

4. Frequent Itemsets: $$\displaystyle L_k $$ = candidates with support ≥ min_sup.

5. Terminate when $$\displaystyle L_k $$ is empty.

Advanced Rule Metrics:

• Lift: Measures deviation from independence. $$\displaystyle \text{lift}(X \Rightarrow Y) = \frac{c(X \Rightarrow Y)}{s(Y)} $$. Lift > 1 ⇒ positive correlation.

• Conviction: $$\displaystyle \text{conviction}(X \Rightarrow Y) = \frac{1 - s(Y)}{1 - c(X \Rightarrow Y)} $$. Higher ⇒ stronger rule.

• Leverage: $$\displaystyle \text{lev}(X \Rightarrow Y) = s(X \cup Y) - s(X)s(Y) $$. Measures difference from independence.

Negative Correlation in Strong Rules:

A rule can have high support & confidence but still be negatively correlated. Example: Rule {Diapers} ⇒ {Beer} has high support/confidence in supermarket data. But if we compute correlation coefficient, it might be near zero or slightly negative. The rule is "strong" statistically but may not imply a true causal or positive relationship—it could be coincidental or due to a confounding factor (e.g., both bought by the same shopper on weekends).

5. Classification: Decision Trees

Tree Pruning: Reduces overfitting by removing branches that reflect noise or anomalies.

• Pre-pruning (Early Stopping): Halt tree growth during induction using criteria (e.g., max depth, min samples per leaf, statistical significance test).

• Post-pruning (Pruning after construction): Grow full tree, then remove subtrees. Common methods: Reduced Error Pruning, Cost-Complexity Pruning.

Drawback of Using a Separate Validation Set for Pruning Evaluation:

• Data Scarcity: Reduces the amount of data available for actual training.

• High Variance: Performance estimates on a small validation set can be unstable and unrepresentative of the true model performance, leading to suboptimal pruning decisions.

6. Clustering

k-means Algorithm: Input: Dataset $D$, number of clusters $k$. Output: $k$ clusters with minimal within-cluster variation (sum of squared distances to centroid).

Steps:

1. Initialize: Randomly select $k$ data points as initial centroids $$\displaystyle \{c_1, ..., c_k\} $$.

2. Assign: For each point $$\displaystyle x_i $$, assign it to the cluster whose centroid is nearest (using Euclidean distance).

3. Update: Recompute centroids as the mean of all points assigned to each cluster.

4. Repeat Steps 2 & 3 until centroids no longer change (convergence) or max iterations.

Worked Example (Small Dataset):

Data: $\{(1,1), (1,2), (2,1), (8,8), (8,9), (9,8)\}$, $$\displaystyle k=2 $$.

• Init centroids: $$\displaystyle c_1=(1,1), c_2=(8,8) $$.

• Assign: Cluster1: first three points; Cluster2: last three.

• Update: $$\displaystyle c_1' = (4/3, 4/3) ≈ (1.33,1.33) $$; $$\displaystyle c_2' = (8.33,8.33) $$.

• Reassign: No change → Converged.

Limitations of k-means:

• Sensitive to initial centroids: Poor initialization can lead to suboptimal local minima.

• Requires pre-specifying $k$: True $k$ is often unknown.

• Assumes spherical clusters: Struggles with non-convex shapes (e.g., moons, rings).

• Sensitive to scale: Attributes with larger ranges dominate distance calculations.

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

[!TIP] Exam Example: Show two initial centroid choices on a dataset with two clear clusters but one outlier. One choice leads to correct clusters; the other, due to outlier influence, splits a natural cluster.

7. Outlier Detection

Clustering-Based Outlier Detection:

• Outliers are points in very small/sparse clusters or far from any cluster centroid.

• Multi-Granularity: Using hierarchical clustering, outliers can be detected at different levels of the dendrogram. A point might be an outlier in a fine-grained cluster but normal when clusters are merged at a higher level.

• Method: For a point $p$, compute its cluster membership and distance to its centroid (or to the $$\displaystyle k^{th} $$ nearest neighbor within its cluster). Points with high distance or in clusters of size 1 are outliers.

Semi-Supervised Outlier Detection:

• Uses a small set of labeled outliers and a large set of unlabeled data (which contains both normal and outlier points).

• Advantage of Unlabeled Objects: The vast majority of unlabeled data represents the normal data distribution. Algorithms (e.g., semi-supervised SVM, positive-unlabeled learning) can learn a robust model of "normality" from this abundant data, improving detection accuracy without needing exhaustive, expensive outlier labels.

8. Specialized Data Mining Domains

Web Mining: Application of DM techniques to web data.

• Web Content Mining: Extracting useful information from web page contents (text, images, multimedia). Example: Mining product reviews for sentiment.

• Web Structure Mining: Discovering structure from hyperlinks. Example: PageRank algorithm, finding authoritative pages.

• Web Usage Mining: Analyzing user access patterns from web logs. Example: Identifying common navigation paths, personalization.

Spatial Data Mining: DM from spatial databases (data with implicit/explicit location).

• Spatial Autocorrelation: Nearby objects tend to be more similar than distant ones (Tobler's First Law).

• Spatial Association Rules: Rules with spatial predicates (e.g., near, intersects). Example: Houses_near(lake) ⇒ high_price.

• Example: Finding hotspots of crime incidents, predicting soil types from neighboring samples.

Temporal Data Mining: DM from time-related data.

• Time-Series Patterns: Trends, seasonality, cycles in sequential numeric data. Example: Monthly sales showing upward trend and yearly seasonality.

• Sequential Patterns: Frequent subsequences in ordered event data. Example: {A, B} ⇒ {C} in customer purchase sequences (A then B, then C).

• Example: Analyzing patient visit sequences to predict disease progression, mining stock price movements.

9. Ethical, Social, and Security Issues

Security and Privacy Concerns:

• Data Misuse: Using mined knowledge for purposes other than originally consented (e.g., discriminatory pricing).

• Inference Attacks: Deducing sensitive information about individuals from non-sensitive data in a released dataset (e.g., knowing a person's zip code, birthdate, and gender can uniquely identify them).

• Privacy Breaches: Re-identification of anonymized data by linking with external datasets.

• Challenges: Balancing utility of data mining with privacy preservation; securing data mining systems against unauthorized access.

Broader Ethical Implications:

• Discrimination & Fairness: Models can perpetuate or amplify societal biases present in training data (e.g., biased hiring or loan approval algorithms).

• Transparency & Explainability: "Black box" models (e.g., complex neural networks) make it hard to understand decisions, affecting accountability.

• Accountability: Determining responsibility for decisions made or actions taken based on data mining outputs.

• Social Impact: Job displacement due to automation, filter bubbles in recommendation systems.