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

UNIT 1: DATA MINING - COMPREHENSIVE SHORT NOTES

I. INTRODUCTION TO DATA MINING & KNOWLEDGE DISCOVERY

A. Data Mining Definition and Motivation

• Data Mining (DM): The core step in the Knowledge Discovery in Databases (KDD) process involving the application of algorithms to extract implicit, previously unknown, and potentially useful patterns (knowledge) from large amounts of data.

• Motivation:

  • Explosion of data in all domains (business, science, web).

  • Need to convert raw data into competitive knowledge and intelligence.

  • Supports decision-making, prediction, and discovery.

B. The Knowledge Discovery in Databases (KDD) Process

A multi-step process where Data Mining is one specific step.

1. Selection: Target data extraction from sources.

2. Preprocessing: Cleaning, handling missing values, noise reduction.

3. Transformation: Normalization, feature construction, aggregation.

4. Data Mining: Application of intelligent methods (classification, clustering, etc.) to extract patterns.

5. Interpretation/Evaluation: Interpreting mined patterns, validating them, and translating them into knowledge.

!TIP: KDD = Overall process. Data Mining = The "pattern extraction" step within KDD. This distinction is a frequent exam question.

C. Data Mining Tasks and Applications

• Major Tasks:

  • Classification: Predict categorical class labels (e.g., spam/not-spam).

  • Clustering: Group similar objects without predefined labels.

  • Association Analysis: Discover frequent patterns, associations, or correlations (e.g., market baskets).

  • Anomaly/Outlier Detection: Identify unusual data records.

  • Regression: Predict continuous-valued responses.

  • Summarization: Provide compact representations of data (e.g., clustering, histograms).

• Applications: Retail/marketing, fraud detection, web mining, bioinformatics, scientific discovery.

II. DATA WAREHOUSING AND OLAP

A. Data Warehouse Fundamentals

• Definition: A subject-oriented, integrated, time-variant, non-volatile collection of data supporting management's decision-making process.

• Key Characteristics:

  • Subject-Oriented: Organized around key subjects (e.g., Customer, Product).

  • Integrated: Consolidated from multiple heterogeneous sources.

  • Time-Variant: Data is stored with a time dimension.

  • Non-Volatile: Stable, read-only data; not updated in real-time.

• Architecture:

  Data Sources → ETL Process → Data Warehouse → OLAP Engine → Front-end Tools

  • ETL (Extract, Transform, Load): The core process of populating the DW.

B. Multidimensional Data Modeling

• Core Concepts:

  • Measure: Quantitative, numeric data (e.g., sales amount, count).

  • Dimension: Categorical descriptors (e.g., time, product, store).

  • Cube: Multidimensional array of measures indexed by dimensions.

  • Cell: A single value in the cube corresponding to a specific combination of dimension values.

• Schema Designs:

  • Star Schema: Simplest. One central fact table (measures + foreign keys to dimensions) connected to multiple denormalized dimension tables.

  • Snowflake Schema: Normalized version of star schema. Dimensions are broken into multiple related tables.

    !EXAMPLE (University Schema):

    FACT TABLE (Student_Course_Fact)

    Measures: count, avg_grade

    Foreign Keys: student_id, course_id, semester_id, instructor_id

    DIMENSIONS (Snowflaked):

    STUDENT (student_id, name, dept_id) → DEPARTMENT (dept_id, dept_name)

    COURSE (course_id, title, credits)

    SEMESTER (semester_id, year, term)

    INSTRUCTOR (instructor_id, name, rank) → (may link to DEPARTMENT)

C. Online Analytical Processing (OLAP)

• OLAP vs. OLTP:

  | Feature | OLTP (Online Transaction Processing) | OLAP (Online Analytical Processing) | | :--- | :--- | :--- | | Purpose | Real-time business operations | Decision support, analysis | | Data | Current, detailed, volatile | Historical, aggregated, integrated | | Operations | Short, fast transactions (CRUD) | Complex, long-running queries | | Schema | Normalized (3NF/5NF) | Denormalized (Star/Snowflake) | | Users | Clerical staff, operators | Managers, executives, analysts |

• Types of OLAP Systems:

  | Type | Full Form | Storage | Performance | Scalability | | :--- | :--- | :--- | :--- | :--- | | MOLAP | Multidimensional OLAP | Proprietary multidimensional arrays | Very fast for pre-aggregated cubes | Less scalable for huge data | | ROLAP | Relational OLAP | Relational DBMS (tables) | Slower, uses SQL on large tables | Highly scalable | | HOLAP | Hybrid OLAP | Combination (aggregates in MOLAP, detail in ROLAP) | Balanced | Balanced |

• Core OLAP Operations:

  1. Roll-up (Drill-up): Aggregate data up the hierarchy (e.g., city → country).

  2. Drill-down: Reverse of roll-up; get more detailed data (e.g., year → quarter → month).

  3. Slice and Dice:

     • Slice: Select a single dimension value (e.g., Sales where Year = 2023).

     • Dice: Select on multiple dimensions (e.g., Sales for (Product A, B) in (Q1, Q2)).

  4. Pivot (Rotate): Rotate the cube to change the dimensional perspective (e.g., swap rows and columns in a report).

III. DATA PREPROCESSING

A. Data Quality and Cleaning

• Common Problems: Missing values, noise (random errors), outliers (extreme values), inconsistency (format, naming).

• Handling Missing Values:

  | Method | Description | Pros | Cons | | :--- | :--- | :--- | :--- | | Ignore tuple | Discard record | Simple | Loses information if many missing | | Fill constant | e.g., "Unknown", 0 | Simple | May create false patterns | | Fill mean/median/mode | For numerical/categorical | Preserves distribution | Distorts variance/correlation | | Use predictor | ML model to predict missing value | More accurate | Computationally expensive |

B. Data Integration and Transformation

• Integration Issues: Entity identification (same entity different names), redundancy (correlation analysis), tuple duplication.

• Data Transformation Strategies:

  • Smoothing: Remove noise (binning, regression, clustering).

  • Attribute Construction: Create new attributes from existing ones.

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

  • Normalization:

    • Min-Max: $$\displaystyle x' = \frac{x - \min(X)}{\max(X) - \min(X)} $$ → scales to [0,1].

    • Z-score: $$\displaystyle x' = \frac{x - \mu}{\sigma} $$ → mean=0, std=1.

    • Decimal Scaling: $$\displaystyle x' = \frac{x}{10^j} $$ (j smallest integer s.t. max(|x'|) < 1).

  • Discretization: Convert continuous to discrete (binning, histogram analysis).

  • Variable Transformation: Apply mathematical function (log, sqrt) to reduce skew.

C. Data Reduction

• Strategies:

  • Dimensionality Reduction: PCA (Principal Component Analysis), feature selection.

  • Numerosity Reduction: Regression, sampling, clustering.

  • Data Compression: Lossless (e.g., PNG) or lossy (e.g., JPEG).

IV. ASSOCIATION ANALYSIS

A. Fundamental Concepts

• Market Basket Model: Each transaction is a set of items.

• Key Metrics (for itemset X → itemset Y):

  • Support: $$\displaystyle \text{supp}(X) = \frac{\text{transactions containing } X}{\text{total transactions}} $$. Measures frequency.

  • Confidence: $$\displaystyle \text{conf}(X \rightarrow Y) = \frac{\text{supp}(X \cup Y)}{\text{supp}(X)} $$. Measures conditional probability.

  • Lift (Correlation): $$\displaystyle \text{lift}(X \rightarrow Y) = \frac{\text{conf}(X \rightarrow Y)}{\text{supp}(Y)} = \frac{\text{supp}(X \cup Y)}{\text{supp}(X) \times \text{supp}(Y)} $$.

    • Lift = 1: X and Y independent.

    • Lift > 1: Positive correlation (X promotes Y).

    • Lift < 1: Negative correlation (X inhibits Y).

• Frequent Itemset: An itemset with support ≥ min_support threshold.

• Strong Association Rule: A rule with support ≥ min_support and confidence ≥ min_confidence.

B. Frequent Pattern Mining: Apriori Algorithm

• Principle (Apriori Property / Anti-Monotonicity): All non-empty subsets of a frequent itemset must also be frequent.

  Proof: Let $I$ be a frequent itemset ($$\displaystyle \text{supp}(I) \geq \text{min\_sup} $$). For any non-empty subset $J \subset I$, every transaction containing $I$ must also contain $J$. Therefore, $$\displaystyle \text{supp}(J) \geq \text{supp}(I) \geq \text{min\_sup} $$. Hence, $J$ is frequent. ∎

• Algorithm Steps:

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

  2. Iterate (k=2,3,... until $$\displaystyle L_k $$ empty):

     • Candidate Generation: $$\displaystyle C_k $$ = generate candidates from $$\displaystyle L_{k-1} $$ using Apriori property (join & prune).

     • Pruning: Count support of each candidate by scanning DB.

     • Frequent Itemsets: $$\displaystyle L_k $$ = candidates in $$\displaystyle C_k $$ with support ≥ min_sup.

  3. Result: $$\displaystyle L = \bigcup_k L_k $$ (all frequent itemsets).

C. Association Rule Generation and Evaluation

• Generate strong rules from frequent itemsets $L$ (for each $l \in L$, $|l| \geq 2$):

  • For every non-empty subset $A \subset l$, form rule $$\displaystyle A \rightarrow (l - A) $$.

  • Compute confidence. If ≥ min_conf, output rule.

• Example: Negative Correlation in Strong Rules:

  • Consider 1000 transactions.

  • $$\displaystyle \text{supp}(A) = 0.4 $$, $$\displaystyle \text{supp}(B) = 0.4 $$, $$\displaystyle \text{supp}(A \cup B) = 0.1 $$.

  • $$\displaystyle \text{conf}(A \rightarrow B) = 0.1/0.4 = 0.25 $$ (may be above min_conf=0.2).

  • $$\displaystyle \text{lift}(A \rightarrow B) = 0.1/(0.4*0.4) = 0.625 < 1 $$.

  • Conclusion: Rule $$\displaystyle A \rightarrow B $$ is "strong" by confidence threshold but shows negative correlation. Buying A makes B less likely.

V. CLASSIFICATION

A. Decision Tree Induction

• Basic Algorithm: Greedy, top-down, recursive partitioning.

  1. Start with all training tuples at root.

  2. Select best attribute to split on (using selection measure).

  3. Create branches for each attribute value.

  4. Recurse on subsets until stopping condition (e.g., all tuples same class, no attributes left).

• Attribute Selection Measures:

  • Information Gain (ID3/C4.5): Based on entropy reduction.

    • $$\displaystyle \text{Entropy}(S) = -\sum_{i=1}^{c} p_i \log_2 p_i $$

    • $$\displaystyle \text{Gain}(S, A) = \text{Entropy}(S) - \sum_{v \in \text{values}(A)} \frac{|S_v|}{|S|} \text{Entropy}(S_v) $$

  • Gini Index (CART): Measures impurity.

    • $$\displaystyle \text{Gini}(S) = 1 - \sum_{i=1}^{c} p_i^2 $$

    • $$\displaystyle \text{Gini\_Split}(S, A) = \sum_{v} \frac{|S_v|}{|S|} \text{Gini}(S_v) $$

  • Gain Ratio (C4.5): Adjusts Information Gain by intrinsic information to penalize many-valued attributes.

    • $$\displaystyle \text{GainRatio}(S, A) = \frac{\text{Gain}(S, A)}{\text{IntrinsicInfo}(S, A)} $$

B. Tree Pruning

• Purpose: Combat overfitting (tree too complex, captures noise). Improve generalization to unseen data.

• Methods:

  • Pre-pruning (Early Stopping): Halt tree growth early (e.g., stop if split not statistically significant, minimum tuples per node).

  • Post-pruning: Grow full tree, then remove/replace subtrees.

• Drawback of Separate Validation Set for Pruning:

  • Reduced Training Data: Using a separate set for pruning reduces the data available for actual tree construction, potentially leading to a less accurate tree.

  • Potential Bias: The validation set might not be perfectly representative of the overall data distribution.

VI. CLUSTERING AND OUTLIER DETECTION

A. Partitioning Methods: k-means

• Algorithm:

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

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

  3. Update: Recompute centroids as mean of assigned points.

  4. Repeat 2-3 until centroids stabilize (no change) or max iterations.

• Example Limitation (Not Global Optimum):

  • Consider 4 points: A(1,1), B(1,2), C(10,1), D(10,2). True clusters: {A,B} and {C,D}.

  • If initial centroids chosen as A and C, algorithm converges perfectly.

  • If initial centroids chosen as A and B, both are in same cluster. Then C and D form second cluster. Result: Suboptimal clustering (within-cluster variation higher than true partition). Sensitive to initial seeds; can get stuck in local minima.

B. Outlier Detection

• Definition: Data objects that deviate significantly from the general data distribution.

• Types:

  • Global vs. Contextual (Conditional): An outlier globally may be normal in a specific context (e.g., 100kg is normal for an adult but outlier for a baby).

  • Univariate vs. Multivariate: Outlier in one dimension vs. outlier considering relationships between multiple dimensions.

• Clustering-Based Outlier Detection:

  • Idea: Outliers are points that are far from cluster centroids, belong to very small/sparse clusters, or are not part of any dense cluster.

  • Finding Outliers at Different Granularity Levels:

    !EXAMPLE (Hierarchical Clustering):

    In a dendrogram, cutting at a high level (few large clusters) might reveal points that merge very late (at low similarity) as global outliers. Cutting at a lower level (more, smaller clusters) might reveal points that are outliers within their local dense region (contextual outliers). Thus, by examining the hierarchy, outliers can be identified at multiple granularities.

• Semi-Supervised Outlier Detection:

  • Uses a small set of labeled normal and outlier examples along with a large set of unlabeled data.

  • Advantage of Unlabeled Objects: They are typically abundant and cheap to obtain. They help learn a more robust and general model of the "normal" data distribution (or the boundary between normal and outlier) by providing a richer sample of the overall data space, reducing overfitting to the small labeled set.

VII. ADVANCED AND SPECIALIZED TOPICS

A. Web Mining

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

• Types:

  1. Web Content Mining: Mining text, images, audio on web pages (e.g., topic discovery, sentiment analysis).

  2. Web Structure Mining: Mining web link structure (e.g., PageRank, discovering hub/authority pages).

  3. Web Usage Mining: Mining web server logs to understand user behavior (e.g., session clustering, recommendation).

B. Security and Privacy in Data Mining

• Key Issues:

  • Inference Attacks: Using published data mining results to deduce sensitive information about individuals.

  • Privacy-Preserving Data Mining (PPDM): Techniques to protect privacy while mining data (e.g., data anonymization, perturbation, secure multi-party computation).

  • Data Disclosure Risks: Re-identification of individuals from supposedly anonymized data.

C. Spatial and Temporal Data Mining

• Spatial Data Mining:

  • Characteristics: Spatial autocorrelation (nearby objects are more similar), complex spatial relationships (topology, distance).

  • Example Tasks: Spatial clustering (e.g., grouping houses by location/price), spatial association rules (e.g., "if near lake then high value"), spatial classification (e.g., land cover prediction).

• Temporal Data Mining:

  • Characteristics: Time-series data (ordered, time-dependent), sequential patterns.

  • Example Tasks: Trend analysis (stock prices), sequence mining (customer purchase sequences), periodicity discovery (seasonal sales patterns).