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

UNIT 5: Data Mining – Core Concepts & Applications

1. Knowledge Discovery in Databases (KDD) Process

Definition: KDD is the overall process of discovering useful knowledge from data. Data mining is a core step within this process, focused on the actual application of algorithms to find patterns.

Steps of the KDD Process (in order):

1. Selection: Retrieve the target dataset from the data source (e.g., data warehouse, database).

2. Preprocessing: Clean the data (handle noise, missing values) and integrate multiple data sources.

3. Transformation: Convert data into a suitable format for mining (e.g., normalization, aggregation).

4. Data Mining: Apply intelligent methods to extract hidden patterns (e.g., clustering, classification, association).

5. Interpretation/Evaluation: Interpret the mined patterns, assess their validity and usefulness, and present the discovered knowledge.

[!TIP] Exam Focus: Be prepared to differentiate KDD from Data Mining. KDD is the entire process (like a project lifecycle), while Data Mining is the specific analytical step within it.

2. Data Warehousing and OLAP

Data Warehouse (DW): A subject-oriented, integrated, time-variant, non-volatile collection of data for decision support.

Schema Designs

OLAP (Online Analytical Processing)

Operations:

• Roll-up (Drill-up): Summarize data by moving up a hierarchy (e.g., city → country).

• Drill-down: View finer details by moving down a hierarchy (e.g., year → quarter → month).

• Slice-and-dice: Select a subset of data (slice) and then view it from different perspectives (dice).

• Pivot (Rotate): Reorient the multidimensional view (e.g., swap rows and columns).

Types of OLAP

Measures vs. Dimensions:

• Dimensions: Categorical descriptors (Who? What? Where? When? Why?). e.g., student, course, semester.

• Measures: Quantitative, additive facts. e.g., count (of enrollments), avg_grade.

3. Data Preprocessing

Data Transformation Strategies

• Normalization: Scale numeric values to a small, specified range (e.g., min-max to [0,1], z-score).

$$x' = \frac{x - \min(X)}{\max(X) - \min(X)}$$

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

• Generalization: Replace low-level values with higher-level concepts using concept hierarchies (e.g., age → youth/adult/senior).

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

Handling Missing Values

[!TIP] Common Pitfall: Blindly using mean imputation can distort data distribution and correlations. Consider the pattern of missingness (MCAR, MAR, MNAR).

4. Association Analysis

Goal: Discover interesting relationships (rules) among items in large transactional datasets.

Key Metrics (for rule $$\displaystyle X \rightarrow Y $$)

• Support: Fraction of transactions containing $X \cup Y$.

$$\text{support}(X \cup Y) = \frac{\text{transactions containing } X \text{ and } Y}{\text{total transactions}}$$

• Confidence: Conditional probability that $Y$ occurs given $X$.

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

• Lift: Measures correlation between $X$ and $Y$.

$$\text{lift}(X \rightarrow Y) = \frac{\text{confidence}(X \rightarrow Y)}{\text{support}(Y)}$$

*   `Lift > 1`: Positive correlation (rule is potentially interesting).

*   `Lift = 1`: Independence.

*   `Lift < 1`: Negative correlation.

Apriori Algorithm

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

1. Let $L$ be a frequent itemset with support $$\displaystyle \ge \text{min\_sup} $$.

2. Assume a subset $S \subset L$ is not frequent (support $$\displaystyle < \text{min\_sup} $$).

3. Any transaction containing $L$ must also contain $S$ (since $S \subset L$).

4. Therefore, the support of $L$ cannot exceed the support of $S$.

5. But support($L$) $\ge$ min_sup and support($S$) $$\displaystyle < $$ min_sup → Contradiction.

6. Hence, all subsets $S$ must be frequent. \boxed{\text{All subsets of a frequent itemset are frequent.}}

Algorithm Steps:

1. Find all frequent 1-itemsets ($$\displaystyle L_1 $$) by scanning DB.

2. Use $$\displaystyle L_{k-1} $$ to generate candidate $k$-itemsets ($$\displaystyle C_k $$) via self-join.

3. Prune $$\displaystyle C_k $$ by deleting candidates with any $(k-1)$-subset not in $$\displaystyle L_{k-1} $$ (Apriori property).

4. Scan DB to count support of candidates in $$\displaystyle C_k $$, form $$\displaystyle L_k $$.

5. Repeat until $$\displaystyle L_k $$ is empty.

6. Generate strong association rules from frequent itemsets using min_confidence.

Negative Correlation in Strong Rules

A rule can have high support & confidence but items may be negatively correlated. Example: {buys_phone} → {buys_landline}.

• Support might be high (many buy both).

• Confidence might be high (most phone buyers also buy landlines).

• But Lift < 1 because buying a phone reduces the probability of buying a landline compared to its baseline. The rule is misleading without lift.

5. Classification

Decision Tree Induction & Overfitting

• Induction: Recursively split data using attribute selection measures (Gini index, entropy/gain).

• Overfitting: Tree becomes too complex, fitting noise in training data → poor performance on unseen data.

Tree Pruning

• Pre-pruning (Early Stopping): Halt tree growth during induction (e.g., stop if samples < threshold, gain < threshold).

• Post-pruning (Backward Pruning): Build full tree, then remove/replace subtrees.

  • Error-based: Replace subtree with leaf if it reduces error on a separate validation set.

  • Cost-complexity: Balance tree size vs. error.

[!TIP] Drawback of Separate Validation Set: Using a separate set for pruning reduces the amount of data available for actual training. A better approach is k-fold cross-validation or using the training set with statistical tests (e.g., chi-square).

6. Clustering

K-Means Algorithm

Input: $k$, dataset $D$. Steps:

1. Initialize $k$ centroids (randomly).

2. Repeat:

   • Assignment: Assign each point to nearest centroid.

   • Update: Recompute centroids as mean of assigned points.

3. Until centroids stabilize.

Objective Function (Within-Cluster Variation):

$$W(C) = \sum_{i=1}^{k} \sum_{x \in C_i} ||x - \mu_i||^2$$

where $$\displaystyle \mu_i $$ is centroid of cluster $$\displaystyle C_i $$.

Limitation - Failure to Find Global Optimum:

• K-means is sensitive to initial centroid selection and can converge to a local optimum.

• Example: Two well-separated clusters with one initial centroid placed between them. The algorithm may split one cluster poorly instead of finding the two natural clusters.

Hierarchical Clustering

• Agglomerative (Bottom-up): Start with each point as a cluster, merge closest clusters.

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

• Produces a dendrogram (cluster hierarchy). No need to specify $k$ initially.

Clustering-Based Outlier Detection (Multi-Granularity)

• Method: Use a clustering algorithm (e.g., DBSCAN) that can identify clusters of varying density.

• Outliers: Points that do not belong to any cluster (noise points in DBSCAN) or belong to very small, sparse clusters.

• Multi-granularity: Different clustering parameters (e.g., eps in DBSCAN) reveal outliers at different density levels. A point might be an outlier in a fine-grained clustering but part of a cluster in a coarser one.

7. Outlier Detection

Clustering-Based Methods

• Distance to nearest cluster: Outliers are far from any cluster centroid.

• Density-based: Outliers are in low-density regions (e.g., DBSCAN noise).

• Cluster-based: Points in small, isolated clusters may be outliers.

Semi-Supervised Outlier Detection

• Uses both labeled (normal/outlier) and unlabeled data.

• Advantage of Unlabeled Objects: They are typically abundant in real scenarios. They help the model learn the underlying data distribution of the "normal" class more accurately, improving detection of novel outliers that differ from the limited labeled examples.

Overview of Techniques

• Statistical: Assume data follows a distribution (e.g., Gaussian); outliers are points with low probability.

• Proximity-based: Distance to nearest neighbors (e.g., k-NN distance).

• Density-based: Local density (e.g., LOF - Local Outlier Factor).

• Classification-based: Train a classifier (one-class SVM, autoencoders).

8. Web Mining

Definition: Application of data mining techniques to discover patterns from web data.

Types

9. Security and Privacy in Data Mining

Security Issues

• Malicious Use: Data mining for cyber-attacks (e.g., intrusion detection evasion, spam targeting).

• Infrastructure Attacks: Attacks on the data mining system itself (data poisoning, model stealing).

Privacy Concerns

• Data Disclosure: Releasing mined patterns that reveal sensitive individual information.

• Inference Attacks: Using public data/mining results to deduce private information about individuals (e.g., from aggregate statistics).

• Purpose Creep: Using data for purposes other than originally consented.

Protective Techniques (Brief)

• Anonymization: Remove or generalize identifiers (k-anonymity, l-diversity).

• Differential Privacy: Add statistical noise to queries/results to protect individual records.

• Secure Multi-Party Computation: Compute on distributed data without sharing raw data.

• Access Control & Auditing: Restrict data/mining tool access, log usage.

10. Spatial and Temporal Data Mining

Spatial Data Mining

• Data: Objects with spatial location/attributes (e.g., geographic features, satellite images).

• Examples:

  • Geographic pattern discovery: Find regions with high crime rates.

  • Spatial association: "Houses near parks have higher value."

  • Spatial clustering: Group similar geographic areas.

• Challenges: Spatial autocorrelation (nearby objects are similar), complex data types (raster, vector), computational cost of spatial operations.

Temporal Data Mining

• Data: Sequences of data points indexed in time order (time series, event sequences).

• Examples:

  • Time-series pattern analysis: Stock price trend prediction, seasonal sales patterns.

  • Sequential pattern mining: "Customers who buy X often buy Y within a week."

• Challenges: High dimensionality, noise, irregular intervals, concept drift (patterns change over time).

Common Applications

• Spatial: Urban planning, environmental monitoring, GIS.

• Temporal: Fraud detection (transaction sequences), healthcare (patient monitoring), predictive maintenance.

[!TIP] Remember: Spatial considers where (location-based relationships), Temporal considers when (time-based sequences). Often combined as spatio-temporal (e.g., tracking disease spread over geography and time).