2021 question paper

Data Mining

26 questions

1. Q1a. Discuss whether or not each of the following activities is a data mining task. Give briefly proper justification : (i) Dividing the customers of a company according to their profitability (ii) Monitoring and predicting failures in a hydropower plant20212m

   Module 2: Data Mining Fundamentals and Association Rule Mining

   Discuss whether or not each of the following activities is a data mining task. Give briefly proper justification :

   (i) Dividing the customers of a company according to their profitability
   (ii) Monitoring and predicting failures in a hydropower plant

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Is it a Data Mining Task?

   (i) Dividing customers according to profitability

   Yes, this is a data mining task.
   This is a clustering/segmentation problem — grouping customers into meaningful segments based on profitability-related attributes (purchase frequency, spend, margin) without predefined labels. Discovering these natural groupings from raw transaction/customer data is a core data mining functionality (unsupervised clustering).

   (ii) Monitoring and predicting failures in a hydropower plant

   Yes, this is a data mining task (specifically the "predicting" part).

   • Monitoring alone (just observing sensor readings in real time) is not mining — it's plain data collection/surveillance.
   • Predicting failures, however, requires learning patterns from historical sensor/operational data to forecast future failures — this is a classification/prediction task, a core data mining functionality.

   So both qualify as data mining tasks, but for different reasons: (i) because segmentation without labels = clustering, and (ii) because predicting future failures from historical patterns = predictive modeling — not because "monitoring" itself is mining.

2. Q1b. Classify the following attributes as binary, discrete or continuous. Also classify them as qualitative (nominal or ordinal) or quantitative (interval or ratio). Some cases may have more than one interpretation, so briefly indicate your reasoning if you think there may be some ambiguity : (i) Distance from center of campus (ii) Ability to pass light in terms of opaque, translucent and transparent20212m

   Module 2: Data Mining Fundamentals and Association Rule Mining

   Classify the following attributes as binary, discrete or continuous. Also classify them as qualitative (nominal or ordinal) or quantitative (interval or ratio). Some cases may have more than one interpretation, so briefly indicate your reasoning if you think there may be some ambiguity :

   (i) Distance from center of campus
   (ii) Ability to pass light in terms of opaque, translucent and transparent

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Attribute Classification

   (i) Distance from center of campus

   • Type: Continuous (can take any real value, e.g., 0.5 km, 1.27 km).
   • Scale: Quantitative — Ratio (has a true zero — "0 distance" means literally at the campus center — and ratios are meaningful: 4 km is twice as far as 2 km).

   (ii) Ability to pass light: opaque, translucent, transparent

   • Type: Discrete (a small, finite set of category values).
   • Scale: Qualitative — Ordinal. There is a natural order — opaque (passes no light) < translucent (passes some light) < transparent (passes most/all light) — but the "distance" between categories isn't numerically meaningful (we can't say translucent is exactly halfway between opaque and transparent in any measurable unit).

   Ambiguity note

   (ii) could arguably be seen as nominal if one ignores the light-passing order and treats the three labels as unordered categories, but since the attribute is explicitly defined by increasing "ability to pass light," the natural/expected interpretation is ordinal.

   Attribute	Discrete/Continuous	Qualitative/Quantitative
   Distance from campus center	Continuous	Quantitative — Ratio
   Opaque/Translucent/Transparent	Discrete	Qualitative — Ordinal

3. Q1c. Differentiate between supervised and unsupervised classification.20212m

   Module 3: Classification and Prediction

   Differentiate between supervised and unsupervised classification.

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: Supervised vs Unsupervised Classification

   • Supervised classification: class labels are known in advance. A set of data objects with known class labels (the training set) is used to build a classification model; this model is then applied to assign class labels to new/unseen objects. In other words, the model is trained on pre-labelled data and the classes are predefined categories.

   • Unsupervised classification: the class label is unknown. It attempts to discover the natural classes/clusters directly from the data itself (using clustering); the number of classes and their boundaries are not known in advance, and are derived by the algorithm (e.g., k-Means clustering, hierarchical clustering).

   Known labels ──▶ Supervised classification ──▶ model ──▶ assign classes to new data
   Unknown labels ──▶ Unsupervised classification ──▶ discover natural groupings/clusters from the data itself
   

   In data mining: supervised classification = predicting a categorical class from a labelled training set; unsupervised classification = clustering (grouping similar objects without predefined labels).

4. Q1d. In real-world data, tuples with missing values for some attributes are a common occurrence. List at least two methods for handling this problem.20212m

   Module 2: Data Mining Fundamentals and Association Rule Mining

   In real-world data, tuples with missing values for some attributes are a common occurrence. List at least two methods for handling this problem.

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Handling Missing Values — At Least Two Methods

   1. Ignore the tuple — Simply discard records with missing values. Only reasonable when the missing attribute is critical (e.g., the class label) and the dataset is large enough that dropping a few rows doesn't hurt.

   2. Fill in the missing value manually — A domain expert examines and fills each gap. Accurate but extremely slow and impractical for large datasets.

   3. Use a global constant — Replace all missing values with a fixed label like "Unknown" or −∞. Simple, but the mining algorithm may mistakenly treat "Unknown" as a meaningful, interesting category.

   4. Use the attribute mean/median — Replace missing numeric values with the mean (or median for skewed data) of that attribute across all tuples.

   5. Use the mean/median of the same class — Replace with the mean of tuples belonging to the same class as the tuple with the missing value (more accurate than a global mean).

   6. Use the most probable value — Predict the missing value using inference methods like regression, decision-tree induction, or Bayesian formalism — the most sophisticated but most accurate approach.

   Missing Value
        │
        ├── Ignore tuple ─────────────▶ (drop row)
        ├── Manual fill ───────────────▶ (expert input)
        ├── Global constant ───────────▶ "Unknown"
        ├── Attribute mean/median ─────▶ statistical fill
        ├── Class-wise mean ───────────▶ context-aware fill
        └── Predicted value (regression/tree/Bayes) ─▶ model-based fill
   

5. Q1e. Describe briefly z-score normalization.20212m

   Module 2: Data Mining Fundamentals and Association Rule Mining

   Describe briefly z-score normalization.

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Z-Score Normalization

   Z-score (zero-mean) normalization rescales an attribute's values based on its mean (μ) and standard deviation (σ):

   $$v' = \frac{v - \mu}{\sigma}$$

   where:

   • $v$ = original value
   • $\mu$ = mean of the attribute
   • $\sigma$ = standard deviation of the attribute
   • $v'$ = normalized value

   Effect

   • The transformed data has mean 0 and standard deviation 1.
   • Values are typically small, ranging roughly from −3 to +3 (assuming a roughly normal distribution), though technically unbounded.

   Why use it

   • Useful when the min/max of an attribute are unknown or when there are outliers that would distort min-max normalization.
   • Puts differently-scaled attributes (e.g., income in lakhs vs age in years) on comparable footing before applying distance-based algorithms (k-NN, k-means, clustering).

   Raw values:  [200, 300, 400, 600, 1000]
                       │  subtract mean, divide by std dev
                       ▼
   Z-scores:    [negative, negative, ~0, positive, large positive]
   

   A z-score of 0 means the value equals the attribute's mean; positive/negative z-scores indicate how many standard deviations above/below the mean the value lies.

6. Q1f. Describe briefly a priori principle.20212m

   Module 2: Data Mining Fundamentals and Association Rule Mining

   Describe briefly a priori principle.

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   The Apriori (A Priori) Principle

   Statement: "If an itemset is frequent, then all of its subsets must also be frequent."

   Equivalently, by contrapositive: "If an itemset is infrequent, then all of its supersets must also be infrequent" — this is the practical pruning rule actually used by the algorithm.

   Why it holds

   Support is anti-monotone: adding more items to an itemset can only keep or reduce the number of transactions containing it (support never increases as itemset size grows).

   $$X \subseteq Y \implies support(X) \geq support(Y)$$

   Diagram

           {A,B,C,D}   infrequent
          /    |    |    \
     {A,B,C} {A,B,D} {A,C,D} {B,C,D}   ← if {A,B,C,D} infrequent, ALL its
          \    |    |    /              supersets are pruned instantly
            (pruned without counting)
   

   Why it matters

   This principle is the backbone of the Apriori algorithm's efficiency: once an itemset is found infrequent, none of its supersets need to be generated or counted at all — dramatically shrinking the candidate search space compared to brute-force enumeration of all $2^d$ possible itemsets.

7. Q1g. List at least four general characteristics of hierarchical clustering methods.20212m

   Module 4: Cluster Analysis

   List at least four general characteristics of hierarchical clustering methods.

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: Four general characteristics of hierarchical clustering

   Hierarchical clustering methods build a nested hierarchy (dendrogram) of clusters. Their general characteristics include:

   1. No requirement to specify the number of clusters $k$ in advance — the $k$ is chosen afterwards by "cutting" the dendrogram at a chosen similarity/distance level.

   2. Agglomerative (bottom-up) or divisive (top-down) — agglomerative starts with each object in its own cluster and repeatedly merges the two most similar clusters (e.g., AGNES/AGNES), while divisive starts with all objects in one cluster and repeatedly splits (e.g., DIANA).

   3. Merge/split decisions are based on inter-cluster proximity (distance or similarity between clusters), using linking criteria such as:

      • single-link — distance between the closest members,
      • complete-link — distance between the farthest members,
      • average-link — average inter-cluster distance.

   4. The hierarchy is represented by a dendrogram — a tree diagram that records the sequences of merges/splits and the similarity levels at which they occur.

   5. They do not backtrack / are irreversible — once two clusters are merged (agglomerative) they are never separated; once a cluster is split (divisive) it is never re-merged.

   6. They are deterministic and non-linear — no centroid optimisation; no iterative refinement (unlike k-means).

   7. Complexity: typically $O(n^2)$ or more (no need for $k$) — less noisy/sensitive to initial conditions if stable, but costlier than partitioning.

   (At least four of the above are usually quoted — e.g., 1, 2, 3, 4.)

8. Q1h. Compare and contrast k-medoids with k-means.20212m

   Module 4: Cluster Analysis

   Compare and contrast k-medoids with k-means.

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: k-Medoids (PAM) vs k-Means

   Criterion	k-Means	k-Medoids (PAM)
   Proposed center	Centroid: mean vector of the cluster (arithmetic mean — not necessarily a point in the data set)	Medoid: an actual data object within the cluster that is the most centrally located (minimises total distance to all other objects in the cluster)
   Robust to outliers/noise	No — outliers affect the mean and can distort the centre	Yes — the medoid is a real point, so isolated/outlying points affect it much less
   Suitable data type	numerical (mean requires numbers)	any — including categorical data (only distances/ dissimilarities needed)
   Complexity	cheaper for low/$| often$O(n^2)$ or worse — it must evaluate all candidate medoid swaps
   Output	a hard cluster line through "data point at the boundary"	one of the real existing data objects

   When to use k-medoids? When outliers/noise are present, or when the data is not numeric (e.g., some categorical/mixed data), or when the interpretation as an existing prototype is necessary.

   Summary: k-Means uses a mean (centroid, often invented point); k-Medoids uses a medoid — an existing representative object — making it robust to outliers and usable with non-numeric dissimilarity matrices.

9. Q1i. Describe the OLAP operation slice and dice.20212m

   Module 1: Data Warehousing and Business Analysis

   Describe the OLAP operation slice and dice.

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Slice and Dice (OLAP Operations)

   Think of a data cube as a 3D box of numbers indexed along multiple dimensions (e.g., Time, Product, Region).

   Slice

   Selects one specific value on one dimension, "cutting" a single 2D layer out of the cube.

           Product
          /|  /|  /|
         / | / | / |
        /__|/__|/__|
       |   |   |   |     <- Slice at Time = "2024"
   Time|___|___|___|
       |   |   |   |
       |___|___|___|
           Region
   

   Example: "Sales for Time = 2024" → gives a 2D Product × Region table.

   Dice

   Selects a sub-cube by picking a range/subset of values on two or more dimensions simultaneously.

   Full cube ──dice──▶  smaller cube
   (Time × Product × Region)   (Time∈{2023,2024} × Product∈{A,B} × Region=West)
   

   Example: "Sales where Time ∈ {2023, 2024} AND Product ∈ {A, B} AND Region = West."

   Key Difference

   Operation	Dimensions restricted	Result
   Slice	1 dimension fixed to a single value	One lower-dimension "layer" of the cube
   Dice	2+ dimensions restricted to ranges/subsets	A smaller sub-cube (same dimensionality)

   Both are used for interactive, ad-hoc drill-down analysis in OLAP tools without needing to re-query the source data.

10. Q1j. Why data mining is a misnomer?20212m

    Module 2: Data Mining Fundamentals and Association Rule Mining

    Why data mining is a misnomer?

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Why "Data Mining" is a Misnomer

    The term "data mining" literally suggests "mining data" — but strictly speaking, we don't mine data itself; we mine patterns/knowledge from data, much like gold mining extracts gold from rock, not "rock mining."

    Reasoning

    • If taken literally, "mining coal from rocks" is called coal mining, not "rock mining" — the process is named after what is extracted, not the raw material it comes from.
    • Following that convention, the process should really be called "knowledge mining from data" or simply "knowledge mining" — since what we're actually after is the hidden knowledge/patterns, not the data itself (which we already have).
    • The formally correct term for the full pipeline is KDD — Knowledge Discovery in Databases — of which "data mining" is just one (pattern-extraction) step, yet the popular term "data mining" is loosely used for the entire process.

    In short: "data mining" is a misnomer because it names the process after its raw input (data) rather than its actual output (knowledge/patterns) — the opposite convention of how "mining" terms normally work (e.g., gold mining, coal mining name the output, not the source rock).

11. Budget App•POCKETLY

    Pocketly on Android

    Log daily food, travel, and hostel expenses instantly. Set monthly spending limits and see where your money goes without complex spreadsheets.

    Install Pocketly
12. Q2a. How does instance-based classifier work? List two instance-based classifiers.20216m

    Module 3: Classification and Prediction

    How does instance-based classifier work? List two instance-based classifiers.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Instance-Based Classifiers

    How an instance-based classifier works

    Instance-based (lazy) classifiers do not build an explicit global model (such as a decision tree or a weight vector) during a separate training phase. Instead they store the training tuples and, at classification time, compare a new tuple with those stored tuples by a similarity/distance measure, then assign it a class based on the local neighbourhood of the most similar stored instances.

    k-Nearest Neighbour (k-NN) is the classic algorithm:

    1. Given a new, unseen query tuple $x_q$, compute its distance (usually Euclidean) to every stored training tuple.
    2. Select the $k$ closest tuples; $k$ is typically an odd number (to avoid ties) chosen empirically by cross-validation.
    3. Assign $x_q$ to the class held by the majority of these $k$ nearest neighbours.

          Training set (stored)          New tuple
          (features, class)                │
                  │  distance
                  ▼
              select k nearest neighbours
                  │  majority vote
                  ▼
               predicted class
    

    Nearest-neighbour classifiers may also use weighted voting (nearer neighbours vote more heavily).

    Two instance-based classifiers:

    1. k-Nearest Neighbours (k-NN) — lazy, non-parametric, the workhorse of instance-based classification.
    2. Case-based reasoning (CBR) — stores previously solved cases (problem–solution pairs); a new problem is solved by retrieving the most similar stored case(s) and adapting their solutions.
    3. Rote classifier — pure lookup: a new tuple is classified only if there is an exactly matching stored tuple (no generalisation at all; fragile when no exact match exists).

    (For the exam, k-NN and case-based reasoning are the two commonly named.)

13. Q2b. What do you mean by under-fitting and over-fitting of a classification model?20214m

    Module 3: Classification and Prediction

    What do you mean by under-fitting and over-fitting of a classification model?

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Under-fitting and Over-fitting of a Classification Model

    Over-fitting (Overfitting)

    Overfitting occurs when a classification model fits the training data too well — including its random noise, outliers, and accidental patterns — at the cost of generalisation to new/unseen data. Such a model typically has very low (even zero) training error but high test error.

    When does it happen?

    • The model is too complex for the underlying problem (e.g., a very deep decision tree, a high-degree polynomial, too many neural-network hidden units).
    • Training continues too long, so the learner starts memorising noise.
    • The training set is small and noisy relative to the model's capacity.

    Under-fitting (Underfitting)

    Underfitting occurs when the model is too simple to capture the genuine structure of the data, so it fails to learn even the training set: both training and test errors are high (a high-bias situation).

    When does it happen?

    • The model is too simple (e.g., a linear model for a curved relationship, a one-leaf tree).
    • Too few relevant attributes are provided, or the data are over-aggregated/discretized.
    • Training is stopped too early, or the wrong model class is used.

              Training error   Test error
    Overfit:     very low           high
    Underfit:     high              high
    (good model): low-mid          low-mid (small gap)
    

    Diagnosis & remedies:

    • Overfit: reduce model complexity, use cross-validation, prune trees, add more data, apply regularisation, early stopping, or ensemble (bagging/random forest).
    • Underfit: increase model complexity, engineer/add more relevant features, choose a richer model class, and ensure training runs long enough.

    Both problems stem from mismatch between model complexity and the data's true complexity — too complex ⇒ overfit; too simple ⇒ underfit.

    Analogy

    Fitting a curve to measurements: overfit = wiggly curve passing exactly through every noisy point (terrible on new points); underfit = a straight line through strongly curved data (misses the trend).

14. Q2c. For the following vectors, x and y, calculate the indicated similarity or distance measures : \mathbf{x} = \{0, 1, 0, 1\}, \quad \mathbf{y} = \{1, 0, 1, 0\} Calculate: 1. Cosine similarity 2. Correlation 3. Euclidean distance 4. Jaccard similarity20214m

    Module 2: Data Mining Fundamentals and Association Rule Mining

    For the following vectors, x and y, calculate the indicated similarity or distance measures :

    $$\mathbf{x} = \{0, 1, 0, 1\}, \quad \mathbf{y} = \{1, 0, 1, 0\}$$

    Calculate:

    1. Cosine similarity
    2. Correlation
    3. Euclidean distance
    4. Jaccard similarity

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Similarity/Distance Measures for x = {0,1,0,1}, y = {1,0,1,0}

    Setup

    $$\mathbf{x} = (0, 1, 0, 1), \quad \mathbf{y} = (1, 0, 1, 0)$$

    1. Cosine Similarity

    $$\cos(\mathbf{x}, \mathbf{y}) = \frac{\mathbf{x} \cdot \mathbf{y}}{\|\mathbf{x}\|\|\mathbf{y}\|}$$

    • Dot product: $(0)(1)+(1)(0)+(0)(1)+(1)(0) = 0$
    • $\|\mathbf{x}\| = \sqrt{0^2+1^2+0^2+1^2} = \sqrt{2}$
    • $\|\mathbf{y}\| = \sqrt{1^2+0^2+1^2+0^2} = \sqrt{2}$

    $$\cos(\mathbf{x},\mathbf{y}) = \frac{0}{\sqrt{2}\cdot\sqrt{2}} = \boxed{0}$$

    2. Correlation

    Mean: $\bar{x} = \bar{y} = 0.5$

    i	$x_i-\bar{x}$	$y_i-\bar{y}$	product	$(x_i-\bar{x})^2$	$(y_i-\bar{y})^2$
    1	-0.5	0.5	-0.25	0.25	0.25
    2	0.5	-0.5	-0.25	0.25	0.25
    3	-0.5	0.5	-0.25	0.25	0.25
    4	0.5	-0.5	-0.25	0.25	0.25
    Σ			-1.0	1.0	1.0

    $$r = \frac{-1.0}{\sqrt{1.0 \times 1.0}} = \boxed{-1}$$
    (makes sense: y is exactly the complement of x, so they're perfectly negatively correlated)

    3. Euclidean Distance

    $$d(\mathbf{x},\mathbf{y}) = \sqrt{(0-1)^2+(1-0)^2+(0-1)^2+(1-0)^2} = \sqrt{1+1+1+1} = \sqrt{4} = \boxed{2}$$

    4. Jaccard Similarity

    Binary co-occurrence counts across the 4 positions:

    Position	x	y	Match type
    1	0	1	f01
    2	1	0	f10
    3	0	1	f01
    4	1	0	f10

    $f_{11}=0,\ f_{01}=2,\ f_{10}=2,\ f_{00}=0$

    $$J(\mathbf{x},\mathbf{y}) = \frac{f_{11}}{f_{01}+f_{10}+f_{11}} = \frac{0}{2+2+0} = \boxed{0}$$

    Summary

    Measure	Value	Interpretation
    Cosine similarity	0	Vectors are orthogonal
    Correlation	-1	Perfectly negatively correlated
    Euclidean distance	2	Maximum possible distance for these binary vectors
    Jaccard similarity	0	No 1-1 overlap at all — completely dissimilar on "presence"

    All four measures agree that x and y are maximally dissimilar — they're exact bitwise complements of each other.

15. Q3a. Build a decision tree using the training data in the table given below. Divide the height attribute into ranges as follows : \{0, 1.6\], (1.6, 1.7\], (1.7, 1.8\], (1.8, 1.9\], (1.9, 2.0\], (2.0, 5.0\] | Gender | Height (m) | Class | |:---:|:---:|:---:| | F | 1.6 | Short | | M | 2 | Tall | | F | 1.9 | Medium | | F | 1.88 | Medium | | F | 1.7 | Short | | M | 1.85 | Medium | | F | 1.6 | Short | | M | 1.7 | Short | | M | 2.2 | Tall | | M | 2.1 | Tall | | F | 1.8 | Medium | | M | 1.95 | Medium | | F | 1.9 | Medium | | F | 1.8 | Medium | | F | 1.75 | Medium |20218m

    Module 3: Classification and Prediction

    Build a decision tree using the training data in the table given below. Divide the height attribute into ranges as follows :
    \{0, 1.6\], (1.6, 1.7\], (1.7, 1.8\], (1.8, 1.9\], (1.9, 2.0\], (2.0, 5.0\]

    Gender	Height (m)	Class
    F	1.6	Short
    M	2	Tall
    F	1.9	Medium
    F	1.88	Medium
    F	1.7	Short
    M	1.85	Medium
    F	1.6	Short
    M	1.7	Short
    M	2.2	Tall
    M	2.1	Tall
    F	1.8	Medium
    M	1.95	Medium
    F	1.9	Medium
    F	1.8	Medium
    F	1.75	Medium

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Building a Decision Tree — Height/Gender Data

    Step 1: Discretize Height into the given ranges

    Gender	Height (m)	Range	Class
    F	1.6	(0,1.6]	Short
    M	2.0	(1.9,2.0]	Tall
    F	1.9	(1.8,1.9]	Medium
    F	1.88	(1.8,1.9]	Medium
    F	1.7	(1.6,1.7]	Short
    M	1.85	(1.8,1.9]	Medium
    F	1.6	(0,1.6]	Short
    M	1.7	(1.6,1.7]	Short
    M	2.2	(2.0,5.0]	Tall
    M	2.1	(2.0,5.0]	Tall
    F	1.8	(1.7,1.8]	Medium
    M	1.95	(1.9,2.0]	Medium
    F	1.9	(1.8,1.9]	Medium
    F	1.8	(1.7,1.8]	Medium
    F	1.75	(1.7,1.8]	Medium

    Class distribution: Short = 4, Medium = 8, Tall = 3 (15 tuples).

    Step 2: Root entropy

    $$H(D) = -\frac{4}{15}\log_2\frac{4}{15} -\frac{8}{15}\log_2\frac{8}{15} -\frac{3}{15}\log_2\frac{3}{15} \approx 1.46$$

    Step 3: Choose the best attribute by Information Gain

    Splitting on Height ranges (each row of the discretization table):

    Range	Tuples	Classes	Entropy
    (0,1.6]	2	Short, Short	0
    (1.6,1.7]	2	Short, Short	0
    (1.7,1.8]	3	Medium ×3	0
    (1.8,1.9]	4	Medium ×4	0
    (1.9,2.0]	2	Tall, Medium	1
    (2.0,5.0]	2	Tall, Tall	0

    Weighted entropy $= \frac{2}{15}(1) = 0.13$; therefore

    $$\text{Gain(Height)} = 1.46 - 0.13 = 1.33$$

    Splitting on Gender:

    • Female (9): Short 3, Medium 6 → $H(F) = 0.92$, contributes $\frac{9}{15}\cdot0.92 = 0.55$
    • Male (6): Short 1, Medium 2, Tall 3 → $H(M) = 1.46$, contributes $\frac{6}{15}\cdot1.46 = 0.58$

    $$\text{Gain(Gender)} = 1.46 - (0.55+0.58) = 0.33$$

    Since Gain(Height) = 1.33 > Gain(Gender) = 0.33, split on Height at the root.

    Step 4: Resulting Decision Tree

                          Height range?
            ┌──────────────┬────────────┬───────────┬────────--┬──────────┬──────────┐
          (0,1.6]      (1.6,1.7]   (1.7,1.8]  (1.8,1.9]   (1.9,2.0]    (2.0,5.0]
             │             │            │          │           │             │
          Short         Short       Medium     Medium        │           Tall
                                                             │
                                                 Height ≥ 2.0 ?
                                                /             \
                                          Tall            Medium
                                         (2.0)            (1.95)
    

    Explanation

    • Every range except (1.9,2.0] is already pure (all classes identical), so it becomes a leaf directly.
    • The range (1.9,2.0] contains two male students: height 2.0 → Tall, height 1.95 → Medium — Gender cannot separate them (both M), so the only distinguishing feature left is a finer height threshold (≥ 2.0 → Tall, else Medium).
    • The final tree separates students into the three classes Short / Medium / Tall using their height, giving perfect classification on this training set.
16. Q3b. What is over-fitting and under-fitting of a model? When do they happen?20216m

    Module 3: Classification and Prediction

    What is over-fitting and under-fitting of a model? When do they happen?

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    What are Over-fitting and Under-fitting? When do they happen?

    Over-fitting

    Over-fitting — the model learns the training data too precisely, capturing random noise, outliers, and chance coincidences in addition to the true signal. Result: near-zero training error but poor accuracy on new/unseen data (high variance).

    When does it occur?

    • Model too complex — too many parameters/leaves compared with the amount of data (e.g., a fully-grown, unpruned decision tree; a very deep neural net; a high-order polynomial).
    • Training for too many epochs/iterations, especially on small, noisy data sets.
    • Using too many irrelevant/multivalued attributes so the learner finds spurious patterns.

    Under-fitting

    Under-fitting — the model is too simple to represent the underlying relationship, so it fails to capture even the main trend: both training and test errors are high (high bias).

    When does it occur?

    • Model too simple for the data (e.g., a linear model fitted to clearly non-linear data; a single-leaf tree).
    • Not enough useful features/attributes; inappropriate discretization.
    • Training stopped too early or the wrong type of model is chosen.

              Training   Test
    Overfit:     low       high      (low bias, high variance)
    Underfit:   high       high      (high bias)
    Good:       low-mid    low-mid   (balanced)
    

    Why (the bias–variance trade-off)

    Overfitting is driven by increased variance: excessively flexible models respond to every random fluctuation. Underfitting is driven by high bias: overly rigid models cannot express the data's true relation. The ideal model complexity balances both.

    When they matter / detection

    The clearest sign is a large gap between training and validation (test) accuracy — low train / high test ⇒ over-fit; both high ⇒ under-fit. We detect and fix them with cross-validation, pruning /regularisation, adjusting model complexity, and gathering more or better data.

17. Q4a. A university plans to build a data warehouse that would help them in analyzing the performance of the students in various courses in different academic sessions. They want to analyze if there is any relation between the average grade of a course and the number of students attending it. They would also like to know if there were some courses offered but did not have any students registered for them. Relative performance among boys and girls and average grades of students from various States and cities of the country for each course must be analyzed and also overall CGPA. Design a star schema for such a data warehouse clearly identifying the fact table(s) and dimension table(s), their primary key(s) and foreign key(s). Your schema should at least be able to satisfy the above-mentioned analysis requirements. You may consider other suitable attributes for the dimension table(s).202110m

    Module 1: Data Warehousing and Business Analysis

    A university plans to build a data warehouse that would help them in analyzing the performance of the students in various courses in different academic sessions. They want to analyze if there is any relation between the average grade of a course and the number of students attending it. They would also like to know if there were some courses offered but did not have any students registered for them. Relative performance among boys and girls and average grades of students from various States and cities of the country for each course must be analyzed and also overall CGPA.

    Design a star schema for such a data warehouse clearly identifying the fact table(s) and dimension table(s), their primary key(s) and foreign key(s). Your schema should at least be able to satisfy the above-mentioned analysis requirements. You may consider other suitable attributes for the dimension table(s).

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Star Schema Design — University Performance Data Warehouse

    Requirements Analysis

    We need to analyze: grade-vs-enrollment relation, courses with zero registrations, gender-wise performance, state/city-wise average grade per course, and overall CGPA. This means our grain (finest fact-table row) should be one student's performance in one course, in one academic session.

    Fact Table

    FACT_PERFORMANCE

    Column	Type	Key
    student_key	FK → DIM_STUDENT	PK (composite)
    course_key	FK → DIM_COURSE	PK (composite)
    session_key	FK → DIM_SESSION	PK (composite)
    grade_point	Measure
    sgpa	Measure
    is_registered	Measure (flag, 1/0)

    Using a is_registered flag (or simply having a row exist) lets us detect courses offered but with zero enrolled students via a LEFT JOIN from DIM_COURSE × DIM_SESSION against the fact table.

    Dimension Tables

    DIM_STUDENT
    | student_key (PK) | student_id | name | gender | state | city | cgpa |

    DIM_COURSE
    | course_key (PK) | course_id | course_name | department | credits |

    DIM_SESSION
    | session_key (PK) | academic_year | semester_type (Odd/Even) |

    Schema Diagram

                      DIM_STUDENT
                     (student_key PK)
                      gender, state, city, cgpa
                            │
                            │FK
                            ▼
    DIM_COURSE ──FK──▶ FACT_PERFORMANCE ◀──FK── DIM_SESSION
    (course_key PK)     (student_key,        (session_key PK)
    course_name,         course_key,          academic_year,
    department           session_key,         semester_type
                          grade_point,
                          sgpa,
                          is_registered)
    

    How it satisfies the requirements

    • Grade vs enrollment relation → aggregate AVG(grade_point) and COUNT(student_key) grouped by course_key.
    • Courses with no students → DIM_COURSE LEFT JOIN FACT_PERFORMANCE, filter WHERE fact IS NULL.
    • Gender-wise performance → join DIM_STUDENT.gender, group by course & gender.
    • State/city-wise average grade → join DIM_STUDENT.state/city, group by course.
    • Overall CGPA → stored directly in DIM_STUDENT.cgpa (or derived as AVG(sgpa) across sessions per student).

    This is a classic star schema: one fact table with numeric measures (grade_point, sgpa) surrounded by denormalized dimension tables, which keeps analytical queries fast (few joins, simple filters).

18. Q4b. Write an SQL query that runs on the schema designed in Q4a and returns the average SGPA of boys from the State of Karnataka for each Autumn (odd) semester during the years 2005–2009.20214m

    Module 1: Data Warehousing and Business Analysis

    Write an SQL query that runs on the schema designed in Q4a and returns the average SGPA of boys from the State of Karnataka for each Autumn (odd) semester during the years 2005–2009.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    SQL Query — Avg SGPA of Boys from Karnataka, Odd Semesters (2005–2009)

    Using the star schema from Q4a (FACT_PERFORMANCE, DIM_STUDENT, DIM_SESSION):

    SELECT
        ds.academic_year,
        AVG(fp.sgpa) AS avg_sgpa
    FROM
        FACT_PERFORMANCE fp
        JOIN DIM_STUDENT  st ON fp.student_key  = st.student_key
        JOIN DIM_SESSION  ds ON fp.session_key  = ds.session_key
    WHERE
        st.gender = 'M'
        AND st.state = 'Karnataka'
        AND ds.semester_type = 'Odd'
        AND ds.academic_year BETWEEN 2005 AND 2009
    GROUP BY
        ds.academic_year
    ORDER BY
        ds.academic_year;
    

    How it maps to the requirement

    • st.gender = 'M' → restricts to boys.
    • st.state = 'Karnataka' → restricts to the given state.
    • ds.semester_type = 'Odd' → restricts to Autumn semesters only.
    • ds.academic_year BETWEEN 2005 AND 2009 → restricts the year range.
    • GROUP BY ds.academic_year → produces one average SGPA row per year, as required ("for each Autumn semester during 2005–2009").
    • The joins connect the fact table's measures (sgpa) to the descriptive attributes (gender, state, academic_year) stored in the dimension tables — this is exactly why a star schema keeps such analytical queries simple (only two joins, no deep nesting).
19. Q5a. The results of an exam are recorded along with some data about the students. The results can be found in the table below : | ID | Cell No. | Language | Passed all Assignments | GPA | Passed Exam | | :---: | :---: | :---: | :---: | :---: | :---: | | 1 | 93333-11101 | Java | No | 3.1 | Yes | | 2 | 93333-11112 | Java | No | 2.0 | No | | 3 | 93333-11102 | C++ | Yes | 3.5 | Yes | | 4 | 93333-11113 | Python | Yes | 2.5 | Yes | | 5 | 93333-11103 | Java | Yes | 3.9 | No | | 6 | 93333-11114 | C++ | No | 2.9 | No | | 7 | 93333-11104 | Java | No | 1.9 | No | | 8 | 93333-11115 | Python | Yes | 3.2 | Yes | In no more than one page of text, describe the design of a K-Nearest Neighbour classifier to predict if a student will fail or pass the exam.202110m

    Module 3: Classification and Prediction

    The results of an exam are recorded along with some data about the students. The results can be found in the table below :

    ID	Cell No.	Language	Passed all Assignments	GPA	Passed Exam
    1	93333-11101	Java	No	3.1	Yes
    2	93333-11112	Java	No	2.0	No
    3	93333-11102	C++	Yes	3.5	Yes
    4	93333-11113	Python	Yes	2.5	Yes
    5	93333-11103	Java	Yes	3.9	No
    6	93333-11114	C++	No	2.9	No
    7	93333-11104	Java	No	1.9	No
    8	93333-11115	Python	Yes	3.2	Yes

    In no more than one page of text, describe the design of a K-Nearest Neighbour classifier to predict if a student will fail or pass the exam.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Designing a K-Nearest Neighbour (k-NN) Classifier for Exam Pass/Fail Prediction

    1. Choose the attributes (features)

    From the given table, use prediction-relevant attributes and drop identifiers:

    Attribute	Type	Role
    ID, Cell No.	identifier	ignored (no predictive value)
    Language	categorical (nominal): Java/C++/Python	matching feature
    Passed all Assignments	binary (Yes/No)	matching feature
    GPA	numeric (continuous)	main numeric feature
    Passed Exam	binary (Yes/No)	class label to predict

    2. Encode attributes for distance computation

    • GPA — numeric; normalise it (e.g., min–max or z-score) so its scale does not dominate distances.
    • Passed all Assignments — encode as 1 (Yes) / 0 (No).
    • Language — a categorical matching indicator: 1 if the student's language equals the new student's language, else 0.
    • For "Cell No.", a student's phone number should NOT be used (like an ID — it would destroy the algorithm).

    3. Define the distance measure

    Combine the per-attribute differences, e.g. the weighted Euclidean distance:

    $$d(q, t) = \sqrt{w_g\,(gpa_q - gpa_t)^2 + w_a\,(\text{assign}_q - \text{assign}_t)^2 + w_l\,(\text{lang}_q - \text{lang}_t)^2}$$

    with default weights 1 for each feature (GPA already normalised). Binary/categorical features contribute 0 (match) or 1 (mismatch).

    4. Choose $k$ and the voting rule

    • Use small odd $k$ (typically $k=3$ or $k=5$) to avoid ties.
    • Tune $k$ by leave-one-out cross-validation on the 8 training tuples (training set is small — each tuple is the test set once, rest train).
    • Voting: assign the new student the majority class ("Passed Exam? = Yes/No") among the $k$ nearest neighbours. Ties broken by nearer neighbours or by choosing the smaller distance sum.

    5. Evaluation

    Compute the classifier's accuracy = (correct predictions)/(total test tuples), and measure the confusion matrix showing false positives (predicted pass, actually failed) vs false negatives — important because failing a student who would pass is arguably worse.

    6. Algorithm summary

    1. Store all training tuples (X, y): X = (GPA, Assign, Language), y = PassedExam.
    2. For a new student q:
          a. normalise GPA features consistently;
          b. compute d(q, t_i) for every stored tuple;
          c. take the k tuples with smallest distance;
          d. output = majority class among those k neighbours.
    3. Tune k (and weights) by leave-one-out cross-validation.
    

    This design uses the given table as the training set and predicts Passed Exam for any new student using their GPA, assignment performance, and programming language similarity.

20. Q5b. Using the dataset from Q5a, use your K-NN classifier to predict whether the following student (who overslept and missed the original exam) will pass the re-exam : | ID | Cell No. | Language | Passed all Assignments | GPA | Passed Exam | | :---: | :---: | :---: | :---: | :---: | :---: | | 9 | 93333-11109 | C++ | Yes | 3.0 | ?? |20214m

    Module 3: Classification and Prediction

    Using the dataset from Q5a, use your K-NN classifier to predict whether the following student (who overslept and missed the original exam) will pass the re-exam :

    ID	Cell No.	Language	Passed all Assignments	GPA	Passed Exam
    9	93333-11109	C++	Yes	3.0	??

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Applying k-NN — Predict Student 9's Re-exam Result

    Student 9 to classify

    ID	Language	Passed all Assignments	GPA	Passed Exam
    9	C++	Yes	3.0	??

    The training set is table Q5a; I use the features (GPA, Passed all Assignments, Language = C++) with the distance

    $$d = \sqrt{(\Delta\text{GPA})^2 + (\Delta\text{Assign})^2 + (\Delta\text{Language})^2}$$

    where mismatches count 1. (Normalisation is omitted here only for a clean illustration; in real use GPA would first be min–max normalised.)

    Distances from student 9 to every training tuple

    T	Language	Assign	GPA	Passed Exam	ΔGPA	ΔAssign	ΔLang	d
    1	Java	No	3.1	Yes	0.1	1	1	1.42
    2	Java	No	2.0	No	1.0	1	1	1.73
    3	C++	Yes	3.5	Yes	0.5	0	0	0.50
    4	Python	Yes	2.5	Yes	0.5	0	1	1.12
    5	Java	Yes	3.9	No	0.9	0	1	1.35
    6	C++	No	2.9	No	0.1	1	0	1.00
    7	Java	No	1.9	No	1.1	1	1	1.79
    8	Python	Yes	3.2	Yes	0.2	0	1	1.02

    k = 3 nearest neighbours

    Closest three tuples: #3 (d=0.50, Pass=Yes), #6 (d=1.00, Pass=No), #8 (d=1.02, Pass=Yes).

    • Voting: Yes (2) vs No (1) → majority class = Yes.

    Answer

    Student 9 (C++, passed all assignments, GPA 3.0) is predicted to PASS the re-exam under a k=3 nearest-neighbour classifier.

    (Note: if GPA were normalised the ranking could shift slightly, but the closest student #3 — identical language, same assignment status, close GPA — strongly dominates the vote; the same conclusion typically holds for k=1, 3 and 5.)

21. Q6. Define any four of the following briefly : (a) Occam's Razor (b) ROC Curve (c) Vector Space Model (d) Data Marts (e) Multilevel Association Rules (f) OLAM202114m

    Module 2: Data Mining Fundamentals and Association Rule Mining

    Define any four of the following briefly :

    (a) Occam's Razor
    (b) ROC Curve
    (c) Vector Space Model
    (d) Data Marts
    (e) Multilevel Association Rules
    (f) OLAM

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Six Key Terms Defined (pick any four for the exam)

    (a) Occam's Razor

    A principle stating that among competing hypotheses that fit the data equally well, the simplest one should be preferred. In data mining/ML, this motivates choosing simpler models (fewer parameters, shallower decision trees) over needlessly complex ones, since simpler models generalize better and are less prone to overfitting.

    (b) ROC Curve

    Receiver Operating Characteristic curve — plots the True Positive Rate (Sensitivity) against the False Positive Rate (1−Specificity) at various classification thresholds.

    TPR
     1 │        ●───●
       │      ●
       │    ●
       │  ●
       │●
     0 └──────────────── FPR
       0              1
    

    The Area Under the Curve (AUC) summarizes overall classifier performance — AUC=1 is a perfect classifier, AUC=0.5 is random guessing (the diagonal line).

    (c) Vector Space Model (VSM)

    An algebraic model used mainly in text/document mining and information retrieval, where each document (or object) is represented as a vector of feature weights (e.g., TF-IDF term weights) in a high-dimensional space. Similarity between documents is then computed geometrically, typically using cosine similarity between their vectors.

    (d) Data Marts

    A subset of a data warehouse, scoped to a specific business line, department, or subject area (e.g., a Sales data mart, an HR data mart). Data marts are smaller, faster to query, and easier to maintain than the full enterprise warehouse, letting individual teams get focused analytical access without querying the entire warehouse.

    (e) Multilevel Association Rules

    Association rules mined at different levels of a concept hierarchy rather than only at the raw item level. For example, instead of just "{Bread} ⇒ {Butter}", multilevel mining can surface rules at higher abstraction levels like "{Bakery Items} ⇒ {Dairy Items}", or at lower levels like "{Whole Wheat Bread} ⇒ {Salted Butter}". This reveals patterns that might be too sparse (low support) at the finest level but become significant when items are generalized.

    (f) OLAM (On-Line Analytical Mining)

    Integrates OLAP with data mining, allowing mining algorithms to be applied directly on multidimensional data cubes rather than flat/raw data. This lets analysts interactively drill/roll/slice/dice to narrow down interesting regions of the cube, then apply mining functions (classification, clustering, association) at whatever granularity they've navigated to — combining OLAP's exploratory interactivity with mining's automatic pattern discovery.

22. Budget App•POCKETLY

    Pocketly on Android

    Log daily food, travel, and hostel expenses instantly. Set monthly spending limits and see where your money goes without complex spreadsheets.

    Install Pocketly
23. Q7a. A database has five transactions. Let min_sup = 60% and min_conf = 80%. | TID | Items_bought | |---|---| | T100 | {M, O, N, K, E, Y} | | T200 | {D, O, N, K, E, Y} | | T300 | {M, A, K, E} | | T400 | {M, U, C, K, Y} | | T500 | {C, O, O, K, I, E} | (i) Find all frequent item sets using a priori algorithm. (ii) List all the strong association rules (with support s and confidence c) matching the following metarule, where X is a variable representing customers: \forall x \in \text{transactions}, \text{buys}(X, \text{item}_1) \wedge \text{buys}(X, \text{item}_2) \Rightarrow \text{buys}(X, \text{item}_3)\ [s, c]20218m

    Module 2: Data Mining Fundamentals and Association Rule Mining

    A database has five transactions. Let min_sup = 60% and min_conf = 80%.

    TID	Items_bought
    T100	{M, O, N, K, E, Y}
    T200	{D, O, N, K, E, Y}
    T300	{M, A, K, E}
    T400	{M, U, C, K, Y}
    T500	{C, O, O, K, I, E}

    (i) Find all frequent item sets using a priori algorithm.

    (ii) List all the strong association rules (with support $s$ and confidence $c$) matching the following metarule, where $X$ is a variable representing customers:
    $$\forall x \in \text{transactions}, \text{buys}(X, \text{item}_1) \wedge \text{buys}(X, \text{item}_2) \Rightarrow \text{buys}(X, \text{item}_3)\ [s, c]$$

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    (i) Frequent Itemsets via Apriori — MONKEY Dataset

    Same dataset as before, min_sup = 60% (count ≥ 3), min_conf = 80%.

    TID	Items
    T100	M, O, N, K, E, Y
    T200	D, O, N, K, E, Y
    T300	M, A, K, E
    T400	M, U, C, K, Y
    T500	C, O, K, I, E

    L1 (count ≥3)

    {M}:3, {O}:3, {K}:5, {E}:4, {Y}:3

    L2 (count ≥3, from valid C2 candidates)

    {K,M}:3, {K,O}:3, {O,E}:3, {K,E}:4, {K,Y}:3

    L3

    Only candidate surviving the apriori-prune test: {K,O,E} — check: {K,O}✅ {K,E}✅ {O,E}✅ all in L2 → count in DB (T100, T200, T500) = 3 → frequent.

    All frequent itemsets:

    {M} {O} {K} {E} {Y}
    {K,M} {K,O} {O,E} {K,E} {K,Y}
    {K,O,E}
    

    (11 itemsets total — see full step-by-step derivation in Q65's solution for the same dataset.)

    ---

    (ii) Strong Rules Matching the Metarule

    Metarule: $\forall x, \text{buys}(X,\text{item}_1) \wedge \text{buys}(X,\text{item}_2) \Rightarrow \text{buys}(X,\text{item}_3)\ [s,c]$

    This asks specifically for rules with exactly 2 items in the antecedent and 1 item in the consequent. The only frequent itemset large enough to produce such a rule is the 3-itemset {K, O, E} (support count = 3, support = 3/5 = 60%).

    We test all three possible 2→1 splits of {K, O, E}:

    Rule	Confidence = support({K,O,E}) / support(antecedent)	Strong? (≥80%)
    {K,O} ⇒ E	3/3 = 100%	✅
    {K,E} ⇒ O	3/4 = 75%	❌
    {O,E} ⇒ K	3/3 = 100%	✅

    Strong Association Rules (matching the metarule)

    $$\text{buys}(X, K) \wedge \text{buys}(X, O) \Rightarrow \text{buys}(X, E) \quad [s = 60\%,\ c = 100\%]$$

    $$\text{buys}(X, O) \wedge \text{buys}(X, E) \Rightarrow \text{buys}(X, K) \quad [s = 60\%,\ c = 100\%]$$

    The rule {K,E} ⇒ O fails the min_conf = 80% threshold (only 75%), so it is not a strong rule and is excluded — even though {K,O,E} itself is a frequent (frequent) itemset, not every rule derived from it clears the confidence bar.

24. Q7b. Explain DBSCAN briefly.20216m

    Module 4: Cluster Analysis

    Explain DBSCAN briefly.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    DBSCAN (Density-Based Spatial Clustering of Applications with Noise)

    DBSCAN is a density-based clustering algorithm that groups points that are closely packed together, marking points in low-density regions as noise. It finds clusters of arbitrary shape and needs no predefined number of clusters $k$.

    Key Concepts

    • ε-neighbourhood (Eps): for a point $p$, the set of points within distance $\varepsilon$ of $p$.
    • MinPts: minimum number of points required to form a dense region.
    • A point $p$ is:
      • a core point if its ε-neighbourhood contains at least MinPts points (including itself);
      • a border point if it is within the ε-neighbourhood of a core point but is not itself a core point;
      • a noise point if it is neither core nor border.

    Algorithm

    DBSCAN(D, Eps, MinPts)
    1. Mark all points as unvisited.
    2. For each unvisited point p in D:
         a. find all points q within Eps of p (N_eps(p));
         b. if |N_eps(p)| < MinPts → mark p as noise (temporarily);
         c. else make p a new cluster C and expand:
              - for every point q in N_eps(p): if q is unvisited,
                mark q visited, find its neighbourhood,
                if q is a core point add its neighbours to the cluster,
                if q was labelled noise, add q to cluster C.
    3. Repeat until all points are processed.
    

    Expansion merges any overlapping dense neighbourhoods: cluster grows by absorbing every point reachable through a chain of core points.

    Properties

    • Detects clusters of arbitrary shape (e.g., donut/C shapes), unlike k-Means.
    • Handles noise/outliers explicitly.
    • Needs only two parameters (Eps, MinPts) — no $k$ in advance.
    • Sensitivity: results depend strongly on a good choice of Eps and MinPts (often found via a k-distance graph).
    • Complexity: O(n log n) with a spatial index (e.g., R-tree); O(n²) without.

        ● ● ●   (dense region = cluster)
      ● ● ● ● ●
        ● ● ●
             ●            ← noise point (isolated)
    

    Here the dense blob forms one cluster and the isolated point is flagged as noise.

25. Q8a. Why do we use ensemble methods? Describe an ensemble method.20217m

    Module 3: Classification and Prediction

    Why do we use ensemble methods? Describe an ensemble method.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Ensemble Methods — Why and How

    Why do we use ensemble methods?

    A single classification model may be unstable (small data changes → big model changes, e.g. decision trees), or may be too weak to express the true decision boundary. Ensembles combine several base models and aggregate their predictions to obtain a single, stronger and more stable classifier. Benefits:

    1. Improved accuracy — averaging/voting corrects individual model errors; different models make different mistakes, so combining them reduces the overall error.
    2. Reduced variance — averaging many unstable models (e.g., trees) smooths out their erratic behaviour.
    3. Reduced bias — a committee of models can represent relationships that a single simple model cannot.
    4. Robustness — less sensitive to noise, overfitting, and outliers; often better generalisation.

    Key Requirement

    For an ensemble to help, the base models must be accurate (better than random) and diverse (make different errors).

    Bagging (Bootstrap Aggregating) — an ensemble method

    Steps:

    1. Generate $m$ bootstrap samples from the original training set, each obtained by sampling with replacement (some tuples repeated, others omitted).
    2. Train a base classifier (e.g., a decision tree) on each sample — typically grown without pruning (high variance, but diverse).
    3. Combine the $m$ classifiers by majority voting for classification (or averaging for regression).

    Training set ──bootstrap──▶ S1 ──▶ C1 ─┐
                           S2 ──▶ C2 ─┼─▶ majority vote ─▶ final class
                           ...              │
                           Sm ──▶ Cm ─┘
    

    Why it works: each bootstrap sample differs slightly, so the trees are diverse; voting reduces variance without increasing bias, so overall accuracy improves.

    Other ensemble methods

    • Random Forest = bagging + random attribute selection at each split.
    • Boosting (AdaBoost) = sequential training that re-weights misclassified tuples and combines by weighted vote.
    • Stacking = combine heterogeneous base learners with a meta-classifier.

    Summary: we use ensembles to get higher, more stable accuracy than any single classifier; a classic simple ensemble is bagging, which trains diverse models on bootstrap samples and votes.

26. Q8b. Differentiate among OLAP, MOLAP and HOLAP.20217m

    Module 1: Data Warehousing and Business Analysis

    Differentiate among OLAP, MOLAP and HOLAP.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    OLAP vs MOLAP vs HOLAP

    These are three server architectures for implementing OLAP, differing in where and how the multidimensional data is physically stored.

    ROLAP (Relational OLAP)

    • Stores data in standard relational tables (star/snowflake schema).
    • Multidimensional operations are translated into SQL at query time.
    • Pros: scales to very large data volumes, reuses existing RDBMS technology.
    • Cons: slower query performance (SQL translation overhead), limited by SQL's multidimensional expressiveness.

    MOLAP (Multidimensional OLAP)

    • Stores data in a proprietary multidimensional array/cube structure (pre-computed).
    • Pros: very fast query response (data pre-aggregated), rich analytical functions.
    • Cons: cube-build time can be long, storage can explode for high-cardinality/sparse dimensions ("data explosion"), limited scalability for very large datasets.

    HOLAP (Hybrid OLAP)

    • Combines both: detailed data stays in relational tables (ROLAP), while summary/aggregated data is stored in MOLAP cubes.
    • Pros: balances MOLAP's speed for aggregates with ROLAP's scalability for detailed data.
    • Cons: more complex architecture to build and maintain.

    Comparison Table

    Aspect	ROLAP	MOLAP	HOLAP
    Storage	Relational tables	Multidimensional array/cube	Mixed (relational + cube)
    Query speed	Slower (SQL translation)	Fastest (pre-computed)	Balanced
    Scalability	Very high (large data)	Limited (cube size)	High
    Storage overhead	Low	High (sparse data explosion)	Moderate
    Best for	Very large, detailed datasets	Fast, smaller/aggregated cubes	Mix of both needs

    ROLAP:  [Relational DB] ──SQL──▶ query engine ──▶ result
    MOLAP:  [Precomputed Cube] ──direct lookup──▶ result   (fast!)
    HOLAP:  [Detail: Relational] + [Summary: Cube] ──▶ result (best of both)
    

    In short: ROLAP trades speed for scalability, MOLAP trades scalability for speed, and HOLAP tries to get both by splitting detail vs summary data across the two storage models.

27. Q9a. Describe classification accuracy. How do we measure it? Differentiate classification accuracy with precision.20217m

    Module 3: Classification and Prediction

    Describe classification accuracy. How do we measure it? Differentiate classification accuracy with precision.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Classification Accuracy — Definition, Measurement & Accuracy vs Precision

    What is classification accuracy?

    Classification accuracy is the percentage of test tuples that the classifier correctly labels:

    $$\text{Accuracy} = \frac{\text{number of correctly classified test tuples}}{\text{total number of test tuples}}$$

    It evaluates the classifier's overall ability to make correct predictions, measured on a test set of tuples whose class labels are already known but hidden from the classifier.

    Measurement procedure

    1. Train/construct the classifier on the training set.
    2. Apply it to a separate test set (or use stratified k-fold cross-validation) — the test tuples are classed and correctness is determined by whether predicted label = known label.
    3. Compute:
       • Accuracy = (TP + TN) / (P + N)
       • Also compute the error rate = 1 − accuracy.
       • Analyse the confusion matrix:

    	Predicted: Yes	Predicted: No
    Actual: Yes	TP	FN
    Actual: No	FP	TN

    Accuracy vs Precision

    Measure	Definition	Where used
    Recall / Sensitivity / True Positive Rate	TP / (TP + FN) — fraction of actual positives correctly found	When missing the positive class is costly
    Precision / Positive Predictive Value	TP / (TP + FP) — fraction of points predicted positive that are truly positive	When a false positive is costly (e.g., spam in inbox)
    F-score / F-measure	harmonic mean of precision & recall	To balance both

    • Accuracy answers: "Of all tuples, what fraction did the model get right?"
    • Precision answers: "Of the tuples the model calls positive, how many are really positive?"

    Both are needed because accuracy alone is misleading in imbalanced class problems: e.g., 95% No / 5% Yes → a model that predicts "No" for everything is 95% accurate yet has 0% precision for the "Yes" class.

    For the exam, define accuracy as the overall correctness measure, state its formula Accuracy = (TP+TN)/(TP+TN+FP+FN), then explain precision Precision = TP/(TP+FP) and contrast it with accuracy.

28. Q9b. Distinguish between noise and outliers. (i) Is noise ever interesting or desirable? Outliers? (ii) Can noise objects be outliers? (iii) Can noise make a typical value into an unusual one or vice versa?20217m

    Module 4: Cluster Analysis

    Distinguish between noise and outliers.

    (i) Is noise ever interesting or desirable? Outliers?
    (ii) Can noise objects be outliers?
    (iii) Can noise make a typical value into an unusual one or vice versa?

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Noise vs Outliers — Differences and Answers

    Definitions

    • Noise is the random (or nonsystematic) component or distortion in the measured data — e.g., typing errors, random measurement error, or blurred/unclear attributes. It is the random part of a value that obscures the true pattern.
    • Outliers are data objects (points, tuples) that behave very differently from the general behaviour or distribution of the rest of the data — they always deviate systematically in some interesting direction.

    Aspect	Noise	Outliers
    Source	random errors / random fluctuations	occasional exceptional data (can be legitimate interest or genuine anomaly)
    Form	adds fuzziness to many points	a few points deviate strongly from the bulk
    Data quality	generally removed/cleaned	can be kept (they may BE the target in fraud detection)
    Relationship	noise can cause outliers	outliers are not necessarily noise

    (i) Is noise ever interesting or desirable? Are outliers?

    • Noise is usually not interesting or desirable — it is an undesirable error component; however some randomness/perturbation can be used in simulation or regularisation.
    • Outliers ARE often interesting/desirable: in fraud detection, network intrusion, and medical anomaly detection an unusual tuple may be exactly what we are mining for.

    (ii) Can noise objects be outliers?

    Yes. Since noise is random error, in a small data set a noisy point can easily appear as an outlier — a tuple that deviates strongly from the rest — thereby becoming an outlier (noise-generated outlier).

    (iii) Can noise make a typical value unusual or vice-versa?

    Noise can easily change a typical attribute value into an unusual one (e.g., the measured age of a person typed 218 instead of 28 → the noisy value looks like an outlier). Conversely, an outlier can't become a "typical" point merely by adding noise; but noise can randomly mask a true-outlier so it appears normal/typical (e.g., extreme transaction value 4500 accidentally recorded as 450 masks it as uninteresting noise). So yes, noise can make a typical value look unusual and noise can also make an unusual value look typical.

      Tuples within same cluster are similar; different clusters are dissimilar.
      Clusters can be of arbitrary shape; outliers/noise are explicitly marked.
                                        |
                  ┌─────────┴─────────┐
                 ● ● ●        noise point
    

    Summary

    • Noise: random measurement error; usually removed/ignored.
    • Outliers: genuinely deviant points; can be interesting and kept.
    • Overlap: noise can produce outliers; outliers are not always noise; and noise can mask or create apparently "normal"/"unusual" values.