UNIT 4: IT Business & Disaster Recovery Planning - Comprehensive Short Notes

I. DATA WAREHOUSING FUNDAMENTALS

Definition and Need for Data Warehouse

Definition: A Data Warehouse (DW) is a subject-oriented, integrated, time-variant, and non-volatile collection of data in support of management's decision-making process.

• Need: To support Decision Support Systems (DSS), Business Intelligence (BI), and analytical reporting by consolidating data from multiple, heterogeneous operational sources into a single, consistent source of truth.

• Primary Goal: Enable knowledge workers (managers, analysts) to perform Online Analytical Processing (OLAP) and data mining for strategic insights, not for daily transaction processing.

Characteristics of Data Warehouse (The 4 pillars)

Data Warehouse Architecture

Core Components:

1. Data Sources: Operational databases, legacy systems, external data.

2. ETL (Extract, Transform, Load): The core process.

   • Extract: Pull data from sources.

   • Transform: Clean, integrate, aggregate, and encode data.

   • Load: Populate the DW (initial load, incremental refresh).

3. Data Warehouse Database: Central repository (often RDBMS, columnar store).

4. Metadata Repository: "Data about the data." Defines source, structure, transformation rules, and meaning.

5. Query & Analysis Tools: Front-end for OLAP, reporting, data mining.

Three-Tier Architecture:

• Bottom Tier: Data Sources & ETL tools. Raw data acquisition.

• Middle Tier (Data Warehouse Database): The core DBMS that stores integrated, historical data. Often includes Data Marts (subsets for specific departments).

• Top Tier: Front-end client tools (Query tools, OLAP tools, Reporting tools, Data Mining tools).

Data Warehouse Implementation Techniques

• Vertical Partitioning: Splitting a table by columns.

  • How: Frequently accessed columns (e.g., Customer_ID, Name) are placed in one table; less frequently accessed or large columns (e.g., Customer_Feedback_Text, Photo) in another.

  • Goal: Improve query performance on active columns by reducing I/O per row fetched.

  • Trade-off: Joins become necessary to reconstruct a full row.

• Other Strategies: Horizontal Partitioning (by rows), Indexing, Materialized Views, Aggregation Tables.

II. DATA WAREHOUSE DESIGN & SCHEMAS

Multidimensional Data Model

• Core Concept: Data is viewed as a cube with dimensions and measures.

  • Dimensions: Perspectives to analyze data (e.g., Time, Product, Store). Have hierarchies (Day->Month->Quarter->Year).

  • Measures: Quantitative, numeric facts (e.g., Sales_Amount, Units_Sold). Subject to aggregation (SUM, AVG, COUNT).

• Data Cube: A multidimensional representation of facts. A cell contains a measure value for a specific combination of dimension members.

Schema Designs for Multidimensional Databases

1. Star Schema

• Structure: One large central Fact Table connected to multiple Denormalized Dimension Tables.

  • Fact Table: Contains foreign keys to all dimensions and the numeric measures. Very large.

  • Dimension Tables: Contain descriptive attributes. Denormalized (redundant, single table per dimension). Have a surrogate primary key.

• Advantage: Simple, fast query performance (fewer joins).

• Disadvantage: Data redundancy in dimensions.

• Example: Sales_Fact(FK_Time, FK_Product, FK_Store, Sales_Amount) connected to Dim_Time, Dim_Product, Dim_Store.

2. Snowflake Schema

• Structure: A normalized extension of the star schema. Dimension tables are decomposed into multiple related tables.

• Example: Dim_Product might be split into Dim_Product (Product_ID, Product_Name, Brand_ID) and Dim_Brand (Brand_ID, Brand_Name, Category_ID).

• Advantage: Reduces data redundancy, saves storage, easier to maintain (update in one place).

• Disadvantage: More complex queries (more joins), potentially slower performance.

• Use When: Dimensions are very large and sparse (e.g., a Customer dimension with thousands of attributes).

3. Galaxy Schema / Fact Constellations

• Structure: Multiple fact tables share common dimension tables. It's a collection of star schemas.

• Example: A Sales_Fact table and a Inventory_Fact table both share the Dim_Product and Dim_Time tables.

• Advantage: Models complex business processes with multiple metrics.

• Disadvantage: Most complex to design and query. Requires careful management of shared dimensions.

• Use When: The data warehouse supports multiple, interconnected business processes.

III. ONLINE ANALYTICAL PROCESSING (OLAP)

OLAP vs. OLTP

OLAP Operations (On a Data Cube)

• Roll-up (Drill-up): Aggregation up a hierarchy (e.g., Daily Sales -> Monthly Sales -> Quarterly Sales).

• Drill-down (Roll-down): Reverse of roll-up; moving down a hierarchy to finer details (e.g., 2024 Sales -> Q1 2024 Sales -> Jan 2024 Sales).

• Slice: Selecting a single dimension value to create a sub-cube (e.g., Sales for Product = "Laptop").

• Dice: Selecting on multiple dimensions to create a sub-cube (e.g., Sales for Product in {"Laptop", "Tablet"} AND Region in {"North", "South"}).

• Pivot (Rotate): Re-orienting the cube, swapping dimensions between rows and columns for different analytical views.

Types of OLAP Servers

1. MOLAP (Multidimensional OLAP)

• Need: For maximum query performance on pre-aggregated, multi-dimensional data.

• How: Uses a proprietary, multidimensional array storage (not relational tables). Data is pre-computed and aggregated across all possible dimension combinations.

• Pros: Very fast response times for all OLAP operations.

• Cons: Data duplication, lengthy ETL/aggregation process, limited scalability for very large data volumes (sparse cubes waste space).

• Example: Microsoft Analysis Services (SSAS), Oracle Essbase.

2. ROLAP (Relational OLAP)

• Concept: Uses relational DBMS as the backend. Data and aggregations are stored in relational tables (star/snowflake schema).

• How: Complex SQL queries (with GROUP BY, CUBE, ROLLUP) are dynamically generated to answer queries. May use materialized views (aggregation tables) for performance.

• Diagram:

  DiagramROLAP: Client Tool -> OLAP Server (generates SQL) -> Relational DB (Star Schema)

• Pros: Scalable to very large data volumes, leverages mature RDBMS technology.

• Cons: Slower than MOLAP for complex queries, performance depends on SQL optimization and indexing.

3. HOLAP (Hybrid OLAP)

• Concept: Combines MOLAP and ROLAP. Detailed data is stored in relational tables, while aggregations/summaries are stored in a multidimensional array.

• Goal: Balance fast query performance on summaries with scalability of relational storage for details.

• How: Drill-down to detail level may hit the relational store, while higher-level queries hit the MOLAP store.

OLAP Server Architecture & Role

• Role: Acts as the middleware between the client/query tool and the data storage (RDBMS or multidimensional store).

• Functions:

  1. Metadata Management: Understands the logical cube model (dimensions, hierarchies, measures).

  2. Query Processing: Translates user OLAP operations (drill-down, slice) into efficient SQL (for ROLAP) or array operations (for MOLAP).

  3. Aggregation Management: Pre-computes and manages aggregations (in MOLAP/HOLAP) or suggests/materializes views (in ROLAP).

  4. Caching: Stores query results for faster repeat access.

Data Cube Computation

• Process: Pre-computing all possible group-by aggregations for a given set of dimensions.

• Example: For dimensions {A, B, C}, the full cube requires computing GROUP BY A,B,C; A,B; A,C; B,C; A; B; C; and `` (grand total).

• Challenge: The number of possible aggregations is exponential (2^n for n dimensions). This is the "curse of dimensionality."

• Techniques to Improve Efficiency:

  • Materialized Views: Store computed aggregations in the database.

  • Indexing: Use bitmap, join, or composite indexes on foreign keys in fact tables.

  • Partitioning: Partition large fact tables by time or region.

  • OLAP Server Aggregation Design: MOLAP servers automatically select which aggregations to pre-compute based on query patterns.

IV. DATA MINING OVERVIEW & PROCESS

Definition and Purpose

• Definition: The process of discovering interesting patterns and knowledge from large amounts of data. It is a core step in the Knowledge Discovery in Databases (KDD) process.

• Purpose: To extract implicit, previously unknown, and potentially useful information from data to support decision-making.

• Examples: Customer segmentation, fraud detection, market basket analysis, prediction.

Data Mining vs. KDD

• KDD: The overall process of knowledge discovery. It includes:

  1. Selection (data from sources)

  2. Preprocessing (cleaning, integration)

  3. Transformation (normalization, feature construction)

  4. Data Mining (applying algorithms)

  5. Interpretation/Evaluation

• Data Mining: The "core" computational step (step 4) of KDD. It's the application of specific algorithms to find patterns.

Data Mining Task Primitives

These define the specification of a data mining task:

1. Task-Relevant Data: The subset of the database to be mined.

2. Knowledge Type: The kind of pattern to be discovered (e.g., classification, clustering, association).

3. Background Knowledge: Useful prior knowledge (e.g., taxonomies/hierarchies for concept hierarchies).

4. Interestingness Measures: Metrics to evaluate patterns (e.g., Support, Confidence, Accuracy).

5. Pattern/Output Representation: How the discovered knowledge should be presented (e.g., rules, trees, clusters).

Role of Data Mining Engine in KDD

• It is the algorithmic engine that executes the data mining task specified by the primitives.

• It interacts with the database or data warehouse to access the task-relevant data.

• It uses background knowledge (like hierarchies) to guide the search for patterns.

• It outputs patterns which are then evaluated by the user or expert system for interestingness and validity.

Pros and Cons of Data Mining

Types of Data on which Data Mining is Applied

1. Relational Databases: Standard tables with rows and columns.

2. Transactional Databases: Data stored as transactions (e.g., market baskets: {item1, item2, item3}).

3. Data Warehouses: Integrated, subject-oriented, time-variant stores. Often the primary source for data mining.

4. Advanced Types:

   • Spatial Data: Geographic information systems (GIS).

   • Temporal/Time-Series Data: Data indexed by time (stock prices, sensor readings).

   • Text Data: Unstructured documents, emails, web pages.

   • Web Data: Hypertext, web logs (usage mining).

   • Multimedia Data: Images, audio, video.

V. DATA PREPROCESSING

Data Cleaning

Techniques to handle incomplete (missing), noisy, and inconsistent data.

• Missing Data:

  • Ignore tuple: Discard record (only if many attributes missing).

  • Fill manually: Impractical for large datasets.

  • Impute with global constant: (e.g., "Unknown").

  • Impute with measure of central tendency: Mean, median, mode for numerical; most frequent for categorical.

  • Impute with most probable value: Use regression, decision tree, or k-NN to predict missing value.

• Noisy Data (errors/outliers):

  • Binning: Sort values, partition into bins, smooth by bin mean/median/boundaries.

  • Regression: Fit a function (linear, multi-linear) to smooth data.

  • Clustering: Group similar values; outliers may form small clusters.

  • Computer/Manual Inspection: Identify and correct known errors.

• Inconsistent Data:

  • Check for domain constraints (e.g., Age cannot be > 150).

  • Check for unique constraints (duplicate records).

  • Check for format consistency (e.g., Date in MM/DD/YYYY vs DD-MM-YYYY).

Data Transformation

Methods to convert data into appropriate forms for mining.

• Smoothing: Remove noise (see binning, regression above).

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

• Generalization: Replace low-level values with higher-level concepts using concept hierarchies (e.g., 25 -> young, USA -> North America).

• Normalization: Scale attribute values to a small, specified range.

  • Min-Max Normalization: $$\displaystyle v' = \frac{v - min_A}{max_A - min_A} (new\_max_A - new\_min_A) + new\_min_A $$ (typically to [0,1]).

  • Z-Score Normalization: $$\displaystyle v' = \frac{v - \mu_A}{\sigma_A} $$ (mean=0, std dev=1).

• Feature Construction: Create new, more informative attributes from existing ones (e.g., BMI from Height and Weight).

Data Integration and Reduction

• Integration: Merge data from multiple sources. Handle schema integration (resolve naming conflicts) and redundancy (detect and eliminate).

• Reduction: Obtain a reduced representation of the dataset that is smaller in volume but produces the same (or almost same) analytical results.

  • Dimensionality Reduction: PCA, Feature Selection.

  • Numerosity Reduction: Regression, Histograms, Clustering, Sampling.

  • Data Compression: Wavelet transforms, PCA.

VI. ASSOCIATION RULE MINING

Association Rule Mining Concepts

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

• Frequent Itemset: An itemset whose support count is greater than or equal to a user-specified minimum support (min_sup) threshold.

• Association Rule: An implication of the form $$\displaystyle X \rightarrow Y $$, where $X$ and $Y$ are disjoint itemsets ($$\displaystyle X \cap Y = \emptyset $$).

• Support (supp): Fraction of transactions that contain $X \cup Y$.

$$\text{supp}(X \rightarrow Y) = P(X \cup Y) = \frac{\text{count}(X \cup Y)}{\text{total transactions}}$$

• Confidence (conf): Conditional probability that a transaction containing $X$ also contains $Y$.

$$\text{conf}(X \rightarrow Y) = P(Y|X) = \frac{\text{supp}(X \cup Y)}{\text{supp}(X)}$$

• Strong Rule: A rule that satisfies both min_sup and min_conf thresholds.

Boolean Association Rule Mining

• Mining rules from transactional data where each attribute is binary (present/absent).

• Example: Market Basket Analysis. {Diaper} -> {Beer}.

• Core Problem: Find all frequent itemsets, then generate strong association rules from them.

Apriori Algorithm (Detailed Steps with Example)

Key Principle (Apriori Property): All subsets of a frequent itemset must also be frequent. (If {A,B,C} is frequent, then {A,B}, {A,C}, {B,C}, {A}, {B}, {C} must be frequent). Anti-monotone property.

Steps:

1. Scan DB to find frequent 1-itemsets ($$\displaystyle L_1 $$).

2. Join Step: Use $$\displaystyle L_{k-1} $$ to generate candidate k-itemsets ($$\displaystyle C_k $$). ($$\displaystyle L_1 \bowtie L_1 = C_2 $$).

3. Prune Step: Remove candidates from $$\displaystyle C_k $$ that have any (k-1)-subset not in $$\displaystyle L_{k-1} $$ (using Apriori property).

4. Scan DB again to count support of candidates in $$\displaystyle C_k $$.

5. Generate $$\displaystyle L_k $$: Keep candidates with support >= min_sup.

6. Terminate when no new frequent itemsets are found.

7. Generate Rules: For each frequent itemset $l$ of size >=2, for every non-empty subset $A$ of $l$, form rule $$\displaystyle A \rightarrow (l - A) $$. Keep rules with confidence >= min_conf.

Example (min_sup=2):

Transactions: T1:{A,B,C}, T2:{A,C}, T3:{A,B}, T4:{B,C}, T5:{A,B,C}

• $$\displaystyle L_1 $$: {A:4, B:3, C:3}

• $$\displaystyle C_2 $$: {A,B}, {A,C}, {B,C}. Counts: 3,3,3 -> All frequent ($$\displaystyle L_2 $$).

• $$\displaystyle C_3 $$: {A,B,C}. Count=2 -> Frequent ($$\displaystyle L_3 $$).

• Rules from {A,B,C}: e.g., {A,B}->{C} (conf=2/3=66.6%), {A,C}->{B} (conf=2/3=66.6%), etc.

Techniques to Improve Apriori Efficiency

• Hash-based Technique: Use hash tables to generate and count candidate 2-itemsets ($$\displaystyle C_2 $$) more efficiently, pruning many candidates early.

• Transaction Reduction (Reduction of DB Size):

  • Remove transactions that don't contain any frequent items (after $$\displaystyle L_1 $$).

  • Remove infrequent items from remaining transactions.

• Partitioning: Partition DB into segments. Find local frequent itemsets in each partition (can be frequent globally if >= global min_sup). Merge to generate global candidates (2 scans only).

• Sampling: Mine a random sample of DB. Use lower min_sup to find candidate rules, then verify on full DB.

• Dynamic Item Counting: Add candidate itemsets during a single DB scan if their subsets are already frequent.

FP-Growth Algorithm (with example)

• Idea: Avoid costly candidate generation and multiple DB scans of Apriori. Uses a compressed, frequent-pattern tree (FP-tree).

• Steps:

  1. First Scan: Count item frequencies, determine frequent items (>= min_sup). Order them by descending frequency.

  2. Build FP-tree: Second scan. For each transaction, insert only frequent items (in frequency order) into the tree. Share common prefixes. Nodes store item name and count.

  3. Mine FP-tree: Recursively grow frequent patterns from the tree via conditional pattern bases and conditional FP-trees.

     • For each item in header table (starting from least frequent), construct its conditional pattern base (set of prefix paths).

     • Build conditional FP-tree from this base.

     • Recursively mine this conditional tree. Patterns are formed by suffixing the item to patterns from the conditional tree.

• Advantage: Only two scans of DB. No candidate generation. Often much faster than Apriori.

Mining Multiple-Level and Multidimensional Association Rules

• Multiple-Level (Concept Hierarchies): Mine rules at different levels of abstraction.

  • Example: {Milk} -> {Cereal} (high level) vs {Whole_Milk} -> {Corn_Flakes} (low level).

  • Approach: Use support thresholds that decrease as you go down the hierarchy (min_sup(high) > min_sup(low)).

• Multidimensional Association Rules: Rules involving more than one dimension.

  • Example: age(X, "30...39") AND income(X, "high") -> buys(X, "sports_car").

  • Approach: Can be treated as categorical attributes in a single table. Use categorical association rule mining (e.g., extend Apriori to handle non-binary attributes).

Time Series Mining Association Rules

• Challenge: Time series data has temporal ordering and sequential dependencies.

• Approach: Transform time series into a symbolic sequence (using SAX - Symbolic Aggregate approXimation) or discretize into intervals.

• Then apply sequential pattern mining or modified association rule mining (considering time lags).

• Example Rule: If Stock Price rises for 3 consecutive days (pattern A), then it falls on the 4th day (pattern B) with confidence 70%.

VII. CLASSIFICATION

Classification Process

1. Learning Phase (Training):

   • A training dataset $D$ is given, consisting of training tuples (records) and their associated class labels.

   • A classification algorithm analyzes $D$ to learn a model (or classifier) that describes the relationship between the attribute set and the class label.

   • The model is a mapping function $$\displaystyle f: \text{Attributes} \rightarrow \text{Class} $$.

2. Classification Phase (Testing):

   • A test dataset (unseen during training) is used to evaluate the model's accuracy.

   • For each tuple in the test set, the model predicts its class label based on its attribute values.

   • The predicted labels are compared to the actual labels to measure performance.

Decision Tree Induction

• Idea: Build a tree where:

  • Internal nodes: Test on an attribute.

  • Branches: Outcomes of the test.

  • Leaf nodes: Class labels.

• Algorithm (e.g., ID3, C4.5):

  1. Start with all training tuples at the root.

  2. Select Splitting Attribute: Use a measure of impurity/disorder to choose the "best" attribute to split on at each node.

     • ID3: Uses Information Gain (IG) based on Entropy.

     • C4.5: Uses Gain Ratio (IG / SplitInfo) to correct IG's bias towards many-valued attributes.

  3. Partition tuples based on the selected attribute's values.

  4. Recurse on each partition until:

     • All tuples in a node belong to the same class (make leaf).

     • No more attributes to split on (make leaf with majority class).

     • No tuples in a partition (use majority class of parent).

• Tree Pruning: To avoid overfitting (tree too complex, fits noise).

  • Pre-pruning (Early Stopping): Stop tree growth during induction (e.g., stop if split doesn't improve purity by a threshold, or if node has very few tuples).

  • Post-pruning: Build full tree, then remove branches. More common. Use a separate validation set to estimate error of pruned vs. unpruned tree. (e.g., Reduced Error Pruning, Cost-Complexity Pruning).

Rule-Based Classification Algorithms

• Idea: Represent the model as a set of IF-THEN rules.

• Approach 1: Separate-and-Conquer (Ripper, CN2):

  • Learn one rule at a time.

  • Covering: Find a rule that covers many tuples of a single class.

  • Remove covered tuples.

  • Repeat for remaining tuples until all covered or no more rules.

• Approach 2: Extract Rules from Decision Tree:

  • Each path from root to leaf is a conjunction of attribute tests -> a rule.

  • Prune conditions from the rule to improve generalization (reduce error on validation set).

Bayesian Classification

Naïve Bayes Classifier

• Based on: Bayes' Theorem with "naïve" assumption of conditional independence among attributes given the class.

$$P(C|A_1, A_2, ..., A_n) = \frac{P(C) \prod_{i=1}^{n} P(A_i|C)}{P(A_1, A_2, ..., A_n)}$$

• Classifier: Assigns to class $C$ that maximizes $$\displaystyle P(C) \prod_{i=1}^{n} P(A_i|C) $$ (since denominator $P(attributes)$ is constant for all classes).

• How to get probabilities: From training data.

  • $P(C)$: Prior probability of class $C$.

  • $$\displaystyle P(A_i|C) $$: Conditional probability of attribute value $$\displaystyle A_i $$ given class $C$.

• Advantages: Simple, fast, works well even with small training data. Handles missing values naturally.

• Disadvantages: Independence assumption is often violated in reality (e.g., Height and Weight are correlated).

Bayesian Belief Networks (BBNs)

• A graphical model that represents a set of variables and their conditional dependencies via a Directed Acyclic Graph (DAG).

• Nodes: Random variables (attributes, class).

• Edges: Direct conditional dependencies.

• Each node has a Conditional Probability Table (CPT) quantifying the effect of its parents.

• Advantage over Naïve Bayes: Can model dependencies among attributes. More expressive.

• Disadvantage: Learning the network structure from data is computationally hard.

Probabilistic Classifiers

• Definition: Classifiers that output a probability distribution over the possible classes, not just a single class label.

• Examples: Naïve Bayes, Logistic Regression, BBNs.

• Output: For a tuple, returns $$\displaystyle P(C_1|x), P(C_2|x), ... $$. The predicted class is $$\displaystyle \arg\max_C P(C|x) $$.

• Usefulness: Allows for confidence in prediction, useful for cost-sensitive decisions.

Classifier Evaluation and Accuracy Verification

Methods for Estimating Accuracy

1. Holdout: Split data into training set (e.g., 2/3) and test set (1/3). Train on train, evaluate on test. Simple, but variance depends on split.

2. k-Fold Cross-Validation:

   • Partition data into k equal-sized folds.

   • Iterate k times: Use 1 fold as test set, remaining k-1 as training set.

   • Average accuracy over k iterations. (k=10 is common). Reduces variance.

3. Bootstrap: Sample n tuples from dataset of size n with replacement to form a training set (same size). The tuples not selected (~36.8%) form the test set ("out-of-bag" estimates). Repeat many times.

Metrics for Evaluation (Beyond Simple Accuracy)

• Accuracy: $$\displaystyle \frac{\text{Number of Correctly Classified Tuples}}{\text{Total Number of Tuples}} $$

• Precision (Positive Predictive Value): $$\displaystyle \boxed{\text{Precision} = \frac{TP}{TP + FP}} $$ (Of all predicted positives, how many are correct?)

• Recall (True Positive Rate, Sensitivity): $$\displaystyle \boxed{\text{Recall} = \frac{TP}{TP + FN}} $$ (Of all actual positives, how many were found?)

• F-measure (F1 Score): Harmonic mean of Precision and Recall.

$$\boxed{F1 = \frac{2 \times \text{Precision} \times \text{Recall}}{\text{Precision} + \text{Recall}}}$$

• ROC Curve: Plots True Positive Rate (Recall) vs. False Positive Rate ($$\displaystyle \frac{FP}{FP+TN} $$) at different classification thresholds. Area Under Curve (AUC) summarizes performance.

Data Prediction (as part of Classification)

• Definition: Using a classification model to predict the unknown class label of a new, unseen data tuple.

• Process: The trained model's mapping function $f$ is applied to the attribute vector of the new tuple: $$\displaystyle \text{Predicted Class} = f(\text{attr}_1, \text{attr}_2, ..., \text{attr}_n) $$.

• Output: The single most likely class (hard classification) or the full probability distribution (soft classification).

VIII. CLUSTERING

Definition and Types of Clustering

• Definition: The process of grouping a set of data objects into clusters such that objects within a cluster are highly similar to each other (high intra-cluster similarity) and dissimilar to objects in other clusters (low inter-cluster similarity).

• Types:

  • Partitioning: Divides data into non-overlapping subsets (e.g., K-means).

  • Hierarchical: Creates a tree (dendrogram) of clusters (e.g., Agglomerative, Divisive).

  • Density-Based: Connects regions of high density (e.g., DBSCAN).

  • Grid-Based: Quantizes space into grid cells (e.g., STING).

  • Model-Based: Assumes data is generated by a mixture of probability distributions (e.g., Gaussian Mixture Models).

Hierarchical Clustering

• Agglomerative (Bottom-up):

  1. Start: Each tuple is its own cluster.

  2. Merge: Iteratively merge the two closest clusters.

  3. Stop: When all tuples in one cluster or desired number of clusters reached.

• Divisive (Top-down):

  1. Start: All tuples in one cluster.

  2. Split: Iteratively split clusters into smaller ones.

  3. Stop: When each tuple is its own cluster or desired number reached.

• Detailed Comparison:

  | Agglomerative | Divisive | | :--- | :--- | | More common, natural. | Less common, computationally expensive (exponential). | | Decisions are final (once merged, can't split). | Can make global optimal splits at top levels. | | Requires only a proximity matrix (can use any distance). | Requires a flat clustering method at each split. | | Complexity: Usually $$\displaystyle O(n^3) $$ or $$\displaystyle O(n^2 \log n) $$ with optimizations. | Complexity: Often $$\displaystyle O(2^{n-1}) $$, heuristics used. |

• Linkage Measures (for Agglomerative): Define "closeness" between two clusters.

  • Single Linkage (Min): $$\displaystyle \text{dist}(C_i, C_j) = \min_{x \in C_i, y \in C_j} \text{dist}(x,y) $$. Chaining effect (elongated clusters).

  • Complete Linkage (Max): $$\displaystyle \text{dist}(C_i, C_j) = \max_{x \in C_i, y \in C_j} \text{dist}(x,y) $$. Produces compact, spherical clusters.

  • Average Linkage: $$\displaystyle \text{dist}(C_i, C_j) = \frac{1}{|C_i||C_j|} \sum_{x \in C_i} \sum_{y \in C_j} \text{dist}(x,y) $$. Compromise between single and complete.

Partitioning Methods (K-means)

• Algorithm:

  1. Choose k (number of clusters) and initial centroids (randomly or heuristically).

  2. Assignment Step: Assign each tuple to the cluster whose centroid is closest (using Euclidean distance).

  3. Update Step: Recompute centroids as the mean of all tuples in each cluster.

  4. Repeat steps 2 & 3 until convergence (centroids no longer change significantly or assignments unchanged).

• Pros: Simple, efficient for large datasets ($O(kn)$ per iteration).

• Cons: Requires k a priori. Sensitive to initial centroids (can converge to local optimum). Sensitive to outliers. Assumes spherical clusters of similar size/density.

Density-Based Methods (DBSCAN)

• Core Idea: Clusters are dense regions of points, separated by sparse regions.

• Key Parameters:

  • ε (eps): Radius of the neighborhood.

  • MinPts: Minimum number of points in the ε-neighborhood to define a core point.

• Point Types:

  • Core Point: Has at least MinPts points within ε.

  • Border Point: Within ε of a core point but has fewer than MinPts in its own neighborhood.

  • Noise/Outlier: Neither core nor border point.

• Algorithm:

  1. Pick an unvisited point. Retrieve its ε-neighborhood.

  2. If it's a core point, start a new cluster and add all density-reachable points (recursively).

  3. If it's not a core point, label as noise (may later become border of another cluster).

• Pros: Discovers clusters of arbitrary shape. Robust to outliers (identifies noise). Doesn't require number of clusters k.

• Cons: Sensitive to parameters ε and MinPts. Struggles with varying densities.

Cluster Evaluation

• Internal Evaluation: Use data itself to evaluate clusters (no external labels).

  • Cohesion: How close are points within the same cluster? (e.g., Sum of Squared Errors (SSE) for K-means: $$\displaystyle \sum_{i=1}^{k} \sum_{x \in C_i} \text{dist}(x, \mu_i)^2 $$).

  • Separation: How well-separated are different clusters? (e.g., Silhouette Coefficient).

• External Evaluation: Compare clustering to a known ground truth (external labels).

  • Entropy: Measures purity of clusters w.r.t. class labels. Lower is better.

  • Purity: $$\displaystyle \frac{1}{n} \sum_{i=1}^{k} \max_j |C_i \cap L_j| $$, where $$\displaystyle L_j $$ is a true class.

  • Normalized Mutual Information (NMI), Adjusted Rand Index (ARI).

IX. ADVANCED DATA MINING TOPICS

Web Usage Mining

• Goal: Discover patterns from web server logs to understand user behavior.

• Data Sources: Server logs, client-side cookies, proxy logs.

• Key Tasks:

  • Preprocessing: Data cleaning (remove robots, errors), user identification, session identification, path completion.

  • Pattern Discovery: Frequent访问 patterns (pages, sequences), association rules (pages visited together), clustering (user sessions, pages), classification (predicting next page, user demographics).

• Applications: Website redesign, personalized recommendations, adaptive sites, business intelligence.

Text Mining

• Goal: Discover patterns, trends, and knowledge from unstructured text documents.

• Key Steps:

  1. Text Preprocessing: Tokenization, stop-word removal, stemming/lemmatization.

  2. Vectorization: Convert text to numerical features.

     • Bag-of-Words (BoW): Word frequency vectors.

     • TF-IDF: Term Frequency-Inverse Document Frequency (weights words by importance).

  3. Pattern Discovery: Apply standard data mining tasks (classification, clustering, association) on the feature vectors.

• Applications: Sentiment analysis, topic modeling (LDA), document classification, spam filtering.

Spatial Mining

• Goal: Discover patterns from spatial databases (data with spatial/geographic attributes).

• Challenges: Spatial autocorrelation (nearby objects are similar), complex data types (points, polygons, lines), spatial relationships (topological, distance, direction).

• Key Tasks:

  • Spatial Association Rules: Rules with spatial predicates (e.g., near, intersects). If house is near(lake) AND size=large THEN price=high.

  • Spatial Classification: Use spatial attributes (location, neighborhood stats) as features.

  • Spatial Clustering: Group spatially proximate objects (e.g., DBSCAN is naturally spatial).

• Applications: GIS, location-based services, environmental studies, urban planning.

Multidimensional Databases (concepts and mining)

• Concept: Databases organized in a multidimensional model (data cubes) with dimensions and measures. The physical storage is often in star/snowflake schemas.

• Mining on MDDBs: The pre-aggregated, summarized structure of a data warehouse facilitates data mining.

  • OLAP-driven Mining: Use OLAP operations to slice/dice the cube, then apply mining algorithms on the resulting subset.

  • Direct Mining on Cubes: Some algorithms (like multi-dimensional clustering) operate directly on cube cells.

• Advantage: Faster mining due to pre-aggregation and quality-integrated data.

X. OBJECT-ORIENTED ANALYSIS & DESIGN (OOAD)

Fundamental OO Concepts

• Encapsulation: Bundling data (attributes) and methods (operations) that operate on the data into a single unit (the object). Restricting direct access to internal state via access modifiers (private, public). Goal: Information hiding, modularity.

• Inheritance: Mechanism where a subclass (child) acquires the properties and behaviors of a superclass (parent). Promotes code reuse and establishes a hierarchical relationship ("is-a").

• Polymorphism: Ability of objects of different classes to respond to the same message (method call) in different ways.

  • Compile-time (Overloading): Same method name, different parameters in same class.

  • Run-time (Overriding): Subclass provides a specific implementation of a method defined in its superclass.

• Abstraction: Identifying essential characteristics of an object while ignoring non-essential details. Using abstract classes/interfaces to define contracts.

Object-Oriented Approach vs. Procedural

How OO Helps Manage Complexity in Large Systems

1. Modularity: System is decomposed into cohesive, loosely-coupled objects. Changes in one object have minimal impact on others.

2. Abstraction: Hides implementation details behind well-defined interfaces. Developers work at the level of objects, not low-level code.

3. Reusability: Inheritance and composition allow building new systems from existing, tested components.

4. Maintainability: Encapsulation localizes changes. Fixing a bug or adding a feature is often confined to a single class or a few related classes.

5. Natural Mapping: Models real-world entities and their relationships, making system design more intuitive and aligned with the problem domain.

Primary Goals of UML

• Standardize the visual modeling language for specifying, constructing, visualizing, and documenting software systems.

• Provide a common vocabulary for stakeholders (analysts, designers, developers, clients).

• Manage complexity by providing different views (diagrams) of the system.

• Facilitate communication and understanding of the system architecture and design.

UML Diagrams (Focus on Class Diagram)

Class Diagram Elements:

• Class: Rectangle with three compartments: Name, Attributes (with visibility + public, - private, # protected), Operations (methods).

• Relationships:

  • Association: Structural relationship ("has-a"). Solid line. Can have multiplicity (1, 0.., 1..), role names.

  • Aggregation: Special association, "whole-part" but parts can exist independently. Hollow diamond on whole side.

  • Composition: Stronger "whole-part", parts cannot exist independently of the whole. Filled diamond on whole side.

  • Inheritance (Generalization): "is-a" relationship. Solid line with hollow arrowhead pointing to superclass.

  • Dependency: Using relationship ("uses"). Dashed arrow from client to supplier. Weaker than association.

Object-Oriented Design (OOD)

• Definition: The process of defining the logical solution to the problem identified during analysis. It focuses on the static architecture (classes, relationships) and dynamic behavior (collaborations) of the system.

• Process (Typical):

  1. Use Case Realization: For each use case, identify collaborating objects, responsibilities, and interactions (sequence/collaboration diagrams).

  2. Identify Classes & Objects: From analysis model, refine into design classes (add design-specific attributes/methods).

  3. Define Relationships: Establish associations, inheritances, dependencies.

  4. Assign Responsibilities: To classes (cohesion) and collaborations (coupling).

  5. Design Patterns: Apply reusable solutions (e.g., Singleton, Observer).

  6. Package Design: Group classes into packages/subsystems.

  7. Create Design Model: Primarily Class Diagrams, Sequence Diagrams, Package Diagrams.

Translating OOD into Implementation

1. Map Design Classes to Code: Each design class becomes a class in the implementation language (Java, C#, Python).

2. Map Relationships:

   • Inheritance: extends (Java) or : (C++).

   • Association: Typically implemented as an attribute that is a reference/pointer to an object of the associated class. Multiplicity 1 -> single reference; * -> collection (List, Set).

   • Aggregation/Composition: Similar to association, but composition implies strong lifecycle dependency (contained object created/destroyed with container).

3. Implement Methods: Translate operations into class methods with specified signatures.

4. Apply Design Patterns: Implement patterns identified in design.

5. Generate Code: Use UML tools with code generation capabilities (forward engineering).

Object-Oriented Databases (OODB)

• Definition: Databases that store objects directly (persistent objects), preserving their structure, behavior, and relationships as defined in OO programming languages.

• Motivation: Impedance Mismatch - The difficulty of mapping complex objects and relationships in an OO program to the flat, tabular structure of an RDBMS.

• Query Languages for OODB: Extend OO programming languages with declarative query capabilities.

  • Examples: OQL (Object Query Language) - SQL-like syntax but navigates object structures (SELECT p.name FROM Person p WHERE p.address.city = "London").

  • Language Integrated Query (LINQ) in C#/.NET is a modern example of this paradigm.

• Comparison with SQL (RDBMS):

  | Feature | RDBMS (SQL) | OODB | | :--- | :--- | :--- | | Data Model | Tables (Rows/Columns). | Objects (Classes, Attributes, Methods). | | Relationships | Foreign keys, joins. | Direct object references (pointers). | | Complex Data | Difficult (BLOBs, nested tables). | Natural (nested objects, arrays, collections). | | Schema Evolution | Rigid (ALTER TABLE). | More flexible (class versioning). | | Query Language | Declarative, set-oriented (SQL). | Often language-integrated (OQL, LINQ). | | Impedance Mismatch | High (object-relational mapping needed). | Low/Negligible. |

Fundamental Characteristics of Object-Oriented Languages

1. Everything is an Object: Primitive types may be objects (e.g., in Python, int is an object).

2. Objects have Identity: Each object has a unique identity (memory address), separate from its state (attribute values).

3. Objects have State: Defined by the values of their attributes at a point in time.

4. Objects have Behavior: Defined by the methods they can perform.

5. Message Passing: Objects interact by sending messages (invoking methods) to each other.

6. Class-Based: Objects are instances of classes. Classes define the blueprint.

7. Inheritance: Supports class hierarchies and reuse.

8. Dynamic Binding (Polymorphism): The method invoked is determined at runtime based on the actual object type.

Models in Object-Oriented Methodology and their Relationships

The OO development process produces a series of inter-related models:

1. Use Case Model: What the system should do. Describes functional requirements via use cases, actors, and scenarios. (UML: Use Case Diagrams).

2. Analysis Model: What the system must do, in terms of problem domain concepts. Identifies key objects, their attributes, relationships, and responsibilities. (UML: Class Diagrams (analysis view), Sequence Diagrams for key scenarios). Technology-independent.

3. Design Model: How the system will be built. Refines analysis classes into design classes with implementation-specific details (e.g., specific data structures, interfaces, frameworks). Defines software architecture, subsystems, design patterns. (UML: Class Diagrams (design view), Component Diagrams, Deployment Diagrams).

4. Implementation Model: The actual source code in a specific programming language. Directly derived from the design model.

Relationship: The models form a traceability chain. Requirements (Use Cases) -> Analysis Concepts -> Design Specifications -> Implementation Code. Each model refines and elaborates the previous one, adding necessary detail for the next phase.