2022 question paper

Data Mining

22 questions

1. Q1a. The artifacts are (i) deterministic distortions (ii) non-deterministic distortions (iii) deterministic and non-deterministic distortions (iv) None of the above20222m

   Module 2: Data Mining Fundamentals and Association Rule Mining

   The artifacts are

   (i) deterministic distortions
   (ii) non-deterministic distortions
   (iii) deterministic and non-deterministic distortions
   (iv) None of the above

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (iii) deterministic and non-deterministic distortions

   Artifacts in a dataset are unwanted distortions or errors introduced into the data during collection, transmission, or measurement (e.g., sensor noise, transmission glitches, encoding errors). They can arise from:

   • Deterministic distortions — predictable, systematic effects (e.g., a fixed sensor calibration bias).
   • Non-deterministic distortions — random, unpredictable effects (e.g., random noise).

   Since artifacts can stem from either or both causes, the correct characterization is (iii) both deterministic and non-deterministic distortions.

2. Q1b. Outlier are (i) legitimate data objects (ii) illegitimate data objects (iii) legitimate and illegitimate data objects (iv) None of the above20222m

   Module 4: Cluster Analysis

   Outlier are

   (i) legitimate data objects
   (ii) illegitimate data objects
   (iii) legitimate and illegitimate data objects
   (iv) None of the above

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (iii) legitimate and illegitimate data objects

   In data mining (per Han, Kamber & Pei), outliers are data objects that deviate considerably from the general behaviour or distribution of the rest of the data — and they can be both legitimate and illegitimate:

   • Legitimate outliers — genuine data objects that differ from the majority but are still valid data; they themselves are the main interest in some mining tasks (e.g., fraud detection — an unusual transaction is a valuable event worth investigating, not a mistake).
   • Illegitimate outliers — objects that arise from noise or errors (sensor malfunction, human data-entry mistakes, measurement glitches); these are unwanted and are usually cleaned/removed during preprocessing.

   Because outlier analysis deals with both cases, option (iii) — "legitimate and illegitimate data objects" — is the correct characterization.

   Why the others are wrong:

   • (i) legitimate only and (ii) illegitimate only — each captures only one side; outliers can be either.
   • (iv) None of the above — incorrect since (iii) is correct.
3. Q1c. Jaccard coefficient is frequently used to handle objects consisting of (i) symmetric binary attribute (ii) asymmetric binary attribute (iii) Both (i) and (ii) (iv) None of the above20222m

   Module 2: Data Mining Fundamentals and Association Rule Mining

   Jaccard coefficient is frequently used to handle objects consisting of

   (i) symmetric binary attribute
   (ii) asymmetric binary attribute
   (iii) Both (i) and (ii)
   (iv) None of the above

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (ii) asymmetric binary attribute

   The Jaccard coefficient is defined as:
   $$J(x, y) = \frac{\text{number of 1-1 matches}}{\text{number of attributes that are 1 in at least one object}} = \frac{f_{11}}{f_{01} + f_{10} + f_{11}}$$

   It deliberately ignores 0-0 matches (f_00). This is the right choice when one value (say, 1 = "present") is much rarer and more meaningful than the other (0 = "absent") — i.e., an asymmetric binary attribute, like "bought item" (1) vs "didn't buy" (0) in market-basket data. Counting the huge number of 0-0 matches (both didn't buy) would dilute similarity meaninglessly.

   For symmetric binary attributes (both outcomes equally important, e.g., gender M/F), the Simple Matching Coefficient (SMC) is used instead, since it includes 0-0 matches.

4. Q1d. The 0 (zero) correlation value between two data object indicates (i) no linear relationship between two objects (ii) non-linear relationship between two objects (iii) linear relationship between two objects (iv) Both (i) and (ii)20222m

   Module 2: Data Mining Fundamentals and Association Rule Mining

   The 0 (zero) correlation value between two data object indicates

   (i) no linear relationship between two objects
   (ii) non-linear relationship between two objects
   (iii) linear relationship between two objects
   (iv) Both (i) and (ii)

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (i) no linear relationship between two objects

   The Pearson correlation coefficient measures the strength of a linear relationship between two variables/objects, ranging from -1 to +1:

   -1              0              +1
   Strong        No linear      Strong
   negative      relationship   positive
   linear                       linear
   

   A correlation of 0 means there is no linear relationship — but importantly, this does not rule out a strong non-linear relationship (e.g., y = x², which can have a correlation near 0 despite being a perfect functional dependency). So option (i) is correct, and (ii) is a common misconception — correlation says nothing definitive about non-linear relationships.

5. Q1e. The decision boundaries produced in nearest-neighbor classifiers are (i) rectilinear (ii) oblique (iii) arbitrary (iv) None of the above20222m

   Module 3: Classification and Prediction

   The decision boundaries produced in nearest-neighbor classifiers are

   (i) rectilinear
   (ii) oblique
   (iii) arbitrary
   (iv) None of the above

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (iii) arbitrary

   In nearest-neighbour (k-NN) classification, a new object is assigned to the class most common among its $k$ closest labelled training objects. The decision boundaries it produces are exactly the perimeters of Voronoi diagrams: each training object owns a "cell" of the feature space containing all points closer to it than to any other object, and cell boundaries (perpendicular bisectors) form the class boundaries.

   • These boundaries are not restricted to axis-parallel rectilinear lines (option i),
   • nor to fixed oblique/hyperplanar shapes such as SVM or logistic-regression bounds (option ii).

   For that reason the textbook (Han & Kamber) states that the decision boundaries of nearest-neighbour classifiers are arbitrary — they can take any irregular, data-driven shape determined purely by where the local training points lie.

   Hence the correct answer is (iii) arbitrary.

6. Q1f. The margin of the decision boundary in SVM is given by (i) d = \frac{1}{|w|} (ii) d = \frac{1}{2 \cdot |w|} (iii) d = \frac{2}{\|w\|} (iv) d = \frac{1}{|w|^2}20222m

   Module 3: Classification and Prediction

   The margin of the decision boundary in SVM is given by

   (i) $d = \frac{1}{|w|}$
   (ii) $d = \frac{1}{2 \cdot |w|}$
   (iii) $d = \frac{2}{\|w\|}$
   (iv) $d = \frac{1}{|w|^2}$

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (iii) $d = \frac{2}{\|w\|}$

   Explanation

   For a linear SVM with separating hyperplane

   $$w \cdot x + b = 0$$

   the perpendicular distance from the origin to the plane is $|b|/\|w\|$. If the margin is defined by the two boundary hyperplanes

   $$w \cdot x + b = +1 \quad \text{and} \quad w \cdot x + b = -1$$

   then the total margin (width) is the distance between them:

   $$d = \frac{|1 - (-1)|}{\|w\|} = \frac{2}{\|w\|}$$

   This is the quantity maximised by SVM: maximising the margin $2/\|w\|$ is equivalent to minimising $\frac12\|w\|^2$ subject to the classification constraints.

   Why the others are wrong:

   • (i) $1/|w|$ — that is the distance of one of the boundary planes from the hyperplane centre (the half-margin), not the full margin.
   • (ii) $1/(2|w|)$ — half of option (i), not the margin.
   • (iv) $1/|w|^2$ — has no such role in the SVM margin formula.

   Hence the margin of the decision boundary in SVM is $d = 2/\|w\|$.

7. Q1g. The classification and prediction methods are affected by (i) accuracy (ii) speed (iii) robustness (iv) All of the above20222m

   Module 3: Classification and Prediction

   The classification and prediction methods are affected by

   (i) accuracy
   (ii) speed
   (iii) robustness
   (iv) All of the above

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (iv) All of the above

   According to Han, Kamber & Pei (Data Mining: Concepts and Techniques), classification and prediction methods are evaluated/affected by the following criteria:

   1. Accuracy — the ability of the model to correctly predict the class label of new or previously unseen data.
   2. Speed — the computation cost of both building the model (training time) and using it (classification time).
   3. Robustness — the ability of the model to handle missing values, noise, and outliers, and to make correct predictions even when the data is imperfect.
   4. Scalability — performance as the amount of data grows (not listed but part of the same set).
   5. Interpretability/comprehensibility — the extent to which the model is understandable to the user.

   Since accuracy, speed, and robustness are all standard criteria that affect classification/prediction methods, the correct option is (iv) All of the above.

8. Q1h. The total number of possible rule extracted from a data set that contains d item is (i) R = 3^{d+1} - 2^d + 1 (ii) R = 3^{d+1} - 2^{d+1} + 1 (iii) R = 3^d - 2^{d+1} + 1 (iv) R = 3^d - 2^d + 120222m

   Module 2: Data Mining Fundamentals and Association Rule Mining

   The total number of possible rule extracted from a data set that contains $d$ item is

   (i) $R = 3^{d+1} - 2^d + 1$
   (ii) $R = 3^{d+1} - 2^{d+1} + 1$
   (iii) $R = 3^d - 2^{d+1} + 1$
   (iv) $R = 3^d - 2^d + 1$

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (iii) $R = 3^d - 2^{d+1} + 1$

   Derivation

   For a dataset with $d$ distinct items, every possible association rule is formed by:

   1. Choosing a non-empty itemset $Y$ from the $d$ items to be the "antecedent ∪ consequent" (the full rule itemset).
   2. Splitting $Y$ into a non-empty antecedent (X) and non-empty consequent (Y − X).

   For each item, it can go into: antecedent, consequent, or neither (not part of the rule) → giving $3^d$ total combinations.

   From this $3^d$, we must subtract:

   • The cases where no item is in the consequent (i.e., only antecedent+neither combos): $2^d$
   • The cases where no item is in the antecedent (only consequent+neither combos): $2^d$
   • Add back the case counted twice (no item in either — the empty rule): $+1$

   $$R = 3^d - 2 \cdot 2^d + 1 = 3^d - 2^{d+1} + 1$$

   This is the standard result from Tan/Steinbach/Kumar's Introduction to Data Mining — confirming option (iii).

9. Q1i. The computational complexity of Apriori algorithm increases with the _______ in the bound of support threshold. (i) increase (ii) decrease (iii) Does not depend (iv) None of the above20222m

   Module 2: Data Mining Fundamentals and Association Rule Mining

   The computational complexity of Apriori algorithm increases with the _______ in the bound of support threshold.

   (i) increase
   (ii) decrease
   (iii) Does not depend
   (iv) None of the above

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (ii) decrease

   Apriori's runtime is dominated by candidate generation and database scans. As min_sup decreases, more itemsets clear the support bar and become "frequent" — so:

   • More frequent itemsets survive at every level (L1, L2, L3, ...).
   • More candidate itemsets get generated at each join step.
   • More database scans/counting passes are needed to evaluate them.

   min_sup HIGH  → few frequent itemsets → fast (small search space)
   min_sup LOW   → many frequent itemsets → slow (huge search space)
   

   So computational complexity increases as the support threshold decreases — a lower bar lets far more candidates through, exploding the search space combinatorially.

10. Q1j. The training time is _______ and testing time is _______ of ANN. (i) low, high (ii) high, low (iii) low, low (iv) high, high20222m

    Module 3: Classification and Prediction

    The training time is _______ and testing time is _______ of ANN.

    (i) low, high
    (ii) high, low
    (iii) low, low
    (iv) high, high

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Answer: (ii) high, low

    In an Artificial Neural Network (ANN), the training time is high while the testing (application) time is low:

    • Training (high): learning uses the backpropagation algorithm, which requires many forward-backward passes over the training data, repeated over many epochs, adjusting weights by gradient descent until the error converges. This is computationally expensive and slow — especially for large datasets and deep networks.

    • Testing (low): once the network is trained, classifying a new input is just a single forward pass through the fixed-weight network (a sequence of weighted sums and activation functions), which is very fast.

    Training phase (slow):  data ──▶ [weight initialization] ──▶ [forward pass]
                                                ▲                  │
                                                └── backward pass / weight update ◀── error
    Testing phase (fast):   single forward pass ──▶ output class
    

    Why the others are wrong:

    • (i) low, high — the reverse of the truth.
    • (iii) low, low — training of ANNs is definitely not fast.
    • (iv) high, high — testing is fast, not high.

    Hence training time is high and testing time is low for ANN — option (ii).

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. What is data mining? Differentiate data mining with traditional database system.20227m

    Module 2: Data Mining Fundamentals and Association Rule Mining

    What is data mining? Differentiate data mining with traditional database system.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    What is Data Mining? Data Mining vs Traditional Database Systems

    Definition

    Data mining is the process of discovering interesting, previously unknown, and potentially useful patterns, correlations, trends, or knowledge from large volumes of data, using techniques from statistics, machine learning, and database systems.

    Data Mining vs Traditional Database System

    Aspect	Traditional Database System	Data Mining
    Goal	Store, retrieve, and manage data accurately	Discover hidden patterns and knowledge
    Query type	Precise queries (SQL) — user knows exactly what they want	Exploratory — patterns not known in advance
    Output	Exact records matching the query	Patterns, rules, models, predictions
    Data volume handled	Handles current, operational data	Handles large historical/aggregated data
    Techniques	Relational algebra, SQL, indexing	Statistics, ML (classification, clustering, association)
    User interaction	User specifies exact criteria	System (semi-)automatically finds interesting patterns
    Example	"List all customers who bought milk on 2024-05-01"	"Discover which items are frequently bought together"

    Traditional DB:  Query ──▶ Exact matching records
    Data Mining:     Data  ──▶ [pattern discovery algorithms] ──▶ Hidden knowledge
    

    In short: a database system answers known questions precisely; data mining discovers unknown patterns automatically — moving from "what is stored?" to "what does the data actually mean?"

13. Q2b. In real-world data, tuples with duplicate and redundant values for some attributes are a common occurrence. Describe various methods for handling this problem.20227m

    Module 2: Data Mining Fundamentals and Association Rule Mining

    In real-world data, tuples with duplicate and redundant values for some attributes are a common occurrence. Describe various methods for handling this problem.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Handling Duplicate and Redundant Data

    Duplicate tuples are exact (or near-exact) repeated records; redundant attributes are columns that can be derived from other columns (adding no new information). Both inflate storage and can bias mining results (e.g., an over-represented duplicate customer skews clustering/statistics).

    Methods

    1. Duplicate detection & removal

       • Exact match: simple SELECT DISTINCT / sort-and-compare to find and drop identical rows.
       • Near-duplicate/fuzzy match: use similarity measures (edit distance, Jaccard) for records that are "almost" the same due to typos/format differences (e.g., "Jon Smith" vs "John Smith"), then merge or drop.

    2. Correlation analysis for redundant attributes

       • Numeric attributes — compute the Pearson correlation coefficient; a high $|r|$ (close to ±1) suggests redundancy, and one of the two attributes can be dropped.
       • Categorical attributes — use the chi-square (χ²) test of independence; a high χ² value with low p-value indicates the attributes are strongly related and possibly redundant.

    3. Covariance analysis — for numeric attributes, examine how they vary together; strong covariance patterns can also flag redundancy.

    4. Careful integration design — during data integration, applying entity identification (recognizing the same real-world entity across different sources with different keys/names) prevents introducing duplicates in the first place.

    Duplicate Tuples          Redundant Attributes
          │                          │
      Exact match  Fuzzy match   Correlation (numeric)  χ² test (categorical)
          │             │             │                       │
       Remove       Merge/Remove   Drop one if |r| high   Drop one if dependent
    

    In short: duplicates are handled by detection (exact or fuzzy) and removal/merging, while redundant attributes are identified via statistical correlation/independence tests and pruned before mining.

14. Q3. A database has five transactions. Let min sup = 60% and min con f = 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} | Find all frequent item sets using Apriori and FP-growth, respectively. Compare the efficiency of the two mining processes.202214m

    Module 2: Data Mining Fundamentals and Association Rule Mining

    A database has five transactions. Let min sup = 60% and min con f = 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}

    Find all frequent item sets using Apriori and FP-growth, respectively. Compare the efficiency of the two mining processes.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Frequent Itemsets — Apriori vs FP-Growth (MONKEY Dataset)

    Data: 5 transactions, 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

    ---

    Part A — Apriori Algorithm

    Step 1: Scan DB → Count 1-itemsets (C1 → L1)

    Item	Count	Frequent?
    M	3	✅
    O	3	✅
    N	2	❌
    K	5	✅
    E	4	✅
    Y	3	✅
    D,A,U,C,I	1–2	❌

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

    Step 2: Generate C2 from L1 (join L1×L1), scan DB → count → prune (L2)

    Pair	Count	Frequent?
    {M,O}	1	❌
    {M,K}	3	✅
    {M,E}	2	❌
    {M,Y}	2	❌
    {O,K}	3	✅
    {O,E}	3	✅
    {O,Y}	2	❌
    {K,E}	4	✅
    {K,Y}	3	✅
    {E,Y}	2	❌

    L2 = {M,K}, {O,K}, {O,E}, {K,E}, {K,Y} (all count ≥3)

    Step 3: Generate C3 from L2 (apriori-gen + prune by apriori property)

    Only pairs sharing a prefix and whose all 2-subsets are in L2 survive:

    • {K,M,O}: needs {M,O} ∈ L2? No → pruned
    • {K,M,Y}: needs {M,Y} ∈ L2? No → pruned
    • {K,O,Y}: needs {O,Y} ∈ L2? No → pruned
    • {K,O,E}: needs {K,O}✅, {K,E}✅, {O,E}✅ → valid candidate

    Count {K,O,E} across DB → appears in T100, T200, T500 → count = 3 → ✅ frequent

    L3 = {K,O,E} (count 3)

    No candidates can be generated for L4 (only one itemset in L3).

    Final Frequent Itemsets (Apriori)

    L1: {M}(3) {O}(3) {K}(5) {E}(4) {Y}(3)
    L2: {K,M}(3) {K,O}(3) {O,E}(3) {K,E}(4) {K,Y}(3)
    L3: {K,O,E}(3)
    

    Total = 11 frequent itemsets

    ---

    Part B — FP-Growth Algorithm

    Step 1: One scan → order items by frequency (descending): K(5) > E(4) > M(3) = O(3) = Y(3)

    Step 2: Second scan → build FP-tree (each transaction's frequent items reordered by the above list)

    TID	Ordered frequent items
    T100	K,E,M,O,Y
    T200	K,E,O,Y
    T300	K,E,M
    T400	K,M,Y
    T500	K,E,O

    FP-Tree Structure

    Root
    └── K:5
        ├── E:4
        │   ├── M:2
        │   │   └── O:1
        │   │       └── Y:1
        │   └── O:2
        │       └── Y:1
        └── M:1
            └── Y:1
    

    Step 3: Mine conditional pattern bases, bottom-up (least frequent item first)

    Item	Conditional Pattern Base	Conditional FP-tree (≥3)	Frequent patterns generated
    Y	{K,E,M,O:1}, {K,E,O:1}, {K,M:1}	K:3	{K,Y}:3
    O	{K,E,M:1}, {K,E:2}	K:3, E:3	{K,O}:3, {O,E}:3, {K,O,E}:3
    M	{K,E:2}, {K:1}	K:3	{K,M}:3
    E	{K:4}	K:4	{K,E}:4

    (Base single-item frequent sets {K}, {E}, {M}, {O}, {Y} carry over directly.)

    Final Frequent Itemsets (FP-Growth) — identical to Apriori

    {M}, {O}, {K}, {E}, {Y}, {K,M}, {K,O}, {O,E}, {K,E}, {K,Y}, {K,O,E} → 11 itemsets

    ---

    Efficiency Comparison

    Aspect	Apriori	FP-Growth
    DB scans required	Multiple (1 per itemset-length level → 4 scans here)	Only 2 scans total
    Candidate generation	Explicit — generates and tests many candidates (join + prune)	None — mines directly via conditional pattern bases
    Memory	Candidate sets can explode for large/dense data	FP-tree is typically compact (shared prefixes)
    Best suited for	Sparse data, small number of frequent items	Dense data, long frequent patterns
    Overall for this dataset	Works fine (small data), but does more redundant counting passes	Fewer scans, no candidate explosion — generally faster/more scalable

    Conclusion: Both algorithms produce the same 11 frequent itemsets, but FP-growth is generally more efficient because it avoids the costly candidate-generation-and-test cycle of Apriori, needing only two database scans regardless of how long the frequent itemsets are.

15. Q4a. Why is naive Bayesian classification called 'naive'? Briefly outline the major ideas of naive Bayesian classification.20227m

    Module 3: Classification and Prediction

    Why is naive Bayesian classification called 'naive'? Briefly outline the major ideas of naive Bayesian classification.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Naïve Bayesian Classification — Why "Naïve" & Main Ideas

    Why is it called "naïve"?

    The naïve Bayes classifier applies Bayes' theorem but makes one strong ("naïve") simplifying assumption: it assumes that all attributes are conditionally independent of one another given the class label. In other words, the value of one attribute is assumed to have no influence on any other attribute once the class is known:

    $$P(X \mid C) = P(x_1, x_2, \dots, x_n \mid C) = \prod_{k=1}^{n} P(x_k \mid C)$$

    This independence assumption is rarely true in real-world data — for example, "age" and "income", or "smoking" and "lung disease", are usually correlated. Because this simplifying assumption is unrealistic, the classifier is called naïve.

    Major Ideas of Naïve Bayesian Classification

    1. Estimate probabilities from training data. For each class $C_i$ compute:

       • the class prior $P(C_i)$ — the proportion of training tuples belonging to $C_i$;
       • the conditional probabilities $P(x_k \mid C_i)$ for each attribute value $x_k$ (from frequency counts; Gaussian density for continuous attributes).

    2. Classify by the maximum-a-posteriori (MAP) rule. For a new tuple $X = (x_1, \dots, x_n)$, Bayes' theorem gives:

    $$P(C_i \mid X) = \frac{P(X \mid C_i)\, P(C_i)}{P(X)}$$

    Since $P(X)$ is the same for every class, assign $X$ to the class with the maximum value of $P(X \mid C_i)\, P(C_i)$:

    $$\text{assign } X \text{ to } C_i \text{ that maximises } P(C_i)\prod_{k=1}^{n} P(x_k \mid C_i)$$

    3. Independence assumption makes it computable — the joint probability becomes a simple product of per-attribute probabilities, so the classifier is very fast even for high-dimensional data.

    4. Laplacian (add-one) smoothing — avoids a single zero conditional probability $P(x_k \mid C_i)=0$ from forcing the whole product to zero.

    Advantages: extremely fast, works well on high-dimensional data such as text, robust to irrelevant attributes, probabilistically principled. Major limitation: the independence assumption is usually violated in real data, which can reduce accuracy — yet in practice (e.g., spam filtering) it still performs surprisingly well.

16. Q4b. What is boosting? State why it may improve the accuracy of decision tree induction.20227m

    Module 3: Classification and Prediction

    What is boosting? State why it may improve the accuracy of decision tree induction.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Boosting — Concept and Why It Improves Decision Tree Accuracy

    What is Boosting?

    Boosting is an ensemble method that combines several weak learners (classifiers only slightly better than random guessing) into a single strong classifier by training them sequentially, gradually focusing more weight on the tuples that earlier learners misclassified.

    Main (AdaBoost-style) idea:

    1. Assign an equal initial weight to every training tuple.
    2. Train a weak learner (typically a single-level decision tree / decision stump) on the weighted data.
    3. Increase the weights of misclassified tuples and decrease the weights of correctly classified ones, so the next learner concentrates on the "hard" cases.
    4. Repeat for $T$ rounds; each new learner specialises in the mistakes of its predecessors.
    5. Combine all $T$ models by weighted voting, where each classifier's vote is weighted by its accuracy:

    $$\text{final}_{}(x) = \operatorname{sign}\left(\sum_{t=1}^{T} \alpha_t \, h_t(x)\right), \qquad \alpha_t = \frac12 \ln\frac{1-\varepsilon_t}{\varepsilon_t}$$

       weighted data ──▶ T1 ──▶ raise weights of errors ──▶ T2 ──▶ ... ──▶ weighted vote
                        (weak)                                          (strong ensemble)
    

    Why boosting may improve the accuracy of decision tree induction

    • Focuses on hard instances. Instead of a single tree that may miss complex regions, boosting builds many simple trees, each paying special attention to tuples the earlier trees got wrong — so subtle patterns that no single stump could capture are learned by the committee.
    • Reduces variance and bias. Decision trees are unstable (small data changes → very different trees). Averaging many trees in an ensemble drastically reduces variance; the committee can also express relationships that are beyond any single shallow tree, reducing bias.
    • Margin-based generalisation. Weighted combinations of weak classifiers tend to produce large margins on the training points, and larger margins yield better theoretical generalisation bounds.

    Limitation / caution: boosting aggressively emphasises hard tuples, so it is sensitive to noise and outliers — with very noisy data it can overfit. Also, the rounds are sequential, so it is not trivially parallelised.

17. Q5a. What is data classification? How does it differ from prediction?20227m

    Module 3: Classification and Prediction

    What is data classification? How does it differ from prediction?

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Data Classification — Definition & Difference from Prediction

    What is Data Classification?

    Data classification is a two-step, supervised process:

    1. Learning / model construction step: a classification algorithm analyses a labelled training set (tuples whose class labels are known) and builds a model, e.g., a decision tree, a set of classification rules, a neural network, or an SVM.
    2. Classification step: the learned model is applied to new, unseen tuples, assigning each to one of the predefined discrete class labels.

    Its output is a categorical label (e.g., low-risk/high-risk, spam/not-spam), and its quality is assessed by accuracy (percentage of correctly classified test tuples).

    Classification vs Prediction

    Aspect	Classification	Prediction (regression)
    Output	Discrete / categorical class labels	Continuous / numeric values
    Nature	Predicts class of an object	Predicts a numerical value of an attribute
    Evaluation	Accuracy / error rate (count of correct labels)	Mean squared error, mean absolute error, correlation
    Examples	Predicting "yes/no", "spam/not-spam", loan rating	Predicting house price, sales figure, temperature
    Techniques	Decision tree, rule-based, Bayesian, neural, SVM	Linear/ non-linear regression, neural net regression

    Important nuance: In a broad sense, "prediction" covers both numeric prediction (regression) and classification — classification is a special case of prediction when the predicted value is a categorical label. In textbook terminology (Han & Kamber), classification predicts categorical labels while numeric prediction (regression) predicts continuous values; the two together form the "classification and prediction" task that examines both discrete & numeric outputs.

18. Q5b. Describe the ID3 algorithm for decision tree construction. Why is it unsuitable for decision tree construction?20227m

    Module 3: Classification and Prediction

    Describe the ID3 algorithm for decision tree construction. Why is it unsuitable for decision tree construction?

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    ID3 Algorithm for Decision Tree Construction — Description & Limitations

    Overview

    ID3 (Iterative Dichotomiser 3), by J. Ross Quinlan, builds a decision tree top-down, greedily, choosing the attribute with the highest Information Gain (based on entropy) at each node.

    Entropy — the impurity of a data set $D$ with $m$ classes is

    $$H(D) = -\sum_{i=1}^{m} p_i \log_2 p_i$$

    where $p_i$ is the fraction of tuples in $D$ belonging to class $C_i$.

    Information Gain of partitioning $D$ on attribute $A$ with distinct values $\{a_1, \dots, a_v\}$:

    $$\text{Gain}(A) = H(D) - \sum_{j=1}^{v} \frac{|D_j|}{|D|}\, H(D_j)$$

    where $D_j$ is the subset of $D$ with $A = a_j$.

    Algorithm Steps

    Algorithm ID3(D: training set, Attributes)
    1. Create a root node for D.
    2. If all tuples in D belong to the same class C → label node C and return.
    3. If Attributes is empty → label node with majority class and return.
    4. Else pick A_best = the attribute with maximum Gain(A).
    5. Label node with A_best; for each distinct value a_j of A_best create one branch.
    6. For each branch: D_j = {tuples with A_best = a_j}
       - if D_j empty → leaf labelled with majority class of D
       - else recursively run ID3(D_j, Attributes − {A_best})
    7. Return the resulting tree.
    

    Why ID3 is unsuitable — main limitations

    1. Handles only categorical attributes — continuous/numeric data must be discretized first; it cannot branch on < / <= thresholds.
    2. Bias toward multi-valued attributes — information gain favours an attribute with many distinct values (e.g. a "customer-ID" attribute would give maximal gain yet be useless), producing poor generalisation. This is fixed in C4.5 by using the gain ratio.
    3. No pruning → overfitting — it grows the tree until it fits the training data perfectly, thereby memorising noise and hurting accuracy on unseen test data.
    4. Greedy, no backtracking — a locally optimal split may lead to a globally sub-optimal tree.
    5. Handles missing values / noise poorly and is unstable — small changes in the training data produce quite different trees.

    Despite these limitations, ID3 is the foundation for C4.5 / C5.0 (adding gain ratio, continuous attributes, and pruning) and further scalable classifiers such as CART, SLIQ, SPRINT, and RainForest.

19. Q6. The support vector machine (SVM) is a highly accurate classification method. However, SVM classifiers suffer from slow processing when training with a large set of data tuples. Discuss how to overcome this difficulty and develop a scalable SVM algorithm for efficient SVM classification in large data sets.202214m

    Module 3: Classification and Prediction

    The support vector machine (SVM) is a highly accurate classification method. However, SVM classifiers suffer from slow processing when training with a large set of data tuples. Discuss how to overcome this difficulty and develop a scalable SVM algorithm for efficient SVM classification in large data sets.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Scaling Up SVM for Large Data Sets

    The Problem

    The standard SVM solves a quadratic programming (QP) problem whose (dual) size is proportional to the number of training tuples $n$. The final classifier depends only on the support vectors, but finding them costs up to O(n²)–O(n³) in time and O(n²) in memory (the full kernel matrix). For large data sets (millions of tuples) that makes straightforward SVM training impractically slow.

    Why can it be made scalable?

    SVMs satisfy the KKT (Karush–Kuhn–Tucker) optimality conditions, and the solution is captured entirely by the support vectors; most training points do not matter. If we can isolate the support vectors without solving the full QP, training can be made near-linear. All scalable methods exploit this sparsity.

    ---

    Methods for Scalable SVM

    1. Chunking (Vapnik).
    Never hold the full set in memory: keep a small working set ("chunk"), solve the QP on it, discard the non-support vectors, and bring in the tuples that most violate the KKT conditions from the remaining data. Repeat until all tuples satisfy KKT. Memory drops from O(n^2) to O(chunk^2).

    2. Decomposition methods (Osuna).
    At each iteration, optimise only a fixed-size sub-problem (a small subset of the variables) while keeping the others fixed at their previous values. The subset is chosen to contain the variables that most violate KKT, and convergence is guaranteed because the objective strictly decreases. This is the framework underlying SVMlight.

    3. Sequential Minimal Optimization (SMO).
    A special case of decomposition that optimises exactly two Lagrange multipliers per step using a closed-form analytic update — so no inner QP solver is needed. Memory use is minimal and each step is cheap; implemented in libSVM, it converges very quickly in practice (often near-linear). Working-set heuristics pick the most violating pair.

    4. Active sampling / core-set methods.
    Since only points near the boundary matter, first sample the likely support vectors (points closest to the current separating surface), train a preliminary SVM, then feed back the misclassified / boundary points. Compact core sets (e.g., core-set SVM, RSVM — Reduced SVM) can be built with a guaranteed O(1/ε²) size for a target accuracy ε.

    5. Incremental / online learning.
    Add tuples one (or a block) at a time: the KKT conditions indicate exactly which existing support vectors must change, so only a local update is needed. This suits streaming or very large data sets and data that grows over time.

    6. Parallel and distributed implementations.

    • Cascade SVM — split the data across processors; each trains its own SVM; support-vector sets are merged pairwise and retrained until only one compact set remains.
    • MapReduce / Spark approaches — map: train local SVMs on partitions; reduce: combine their support-vector sets; iterate until convergence.
    • Kernel approximation — use low-rank approximations (Nyström) or random Fourier feature maps so that a simple linear SVM can be trained on the lifted feature space, dramatically speeding up training.

    ---

    Summary Table

    Method	Key idea	Efficiency gain
    Chunking	solve QP on small working subset	memory reduced to O(k²)
    Decomposition	optimise a small subset, fix rest	avoids solving full QP
    SMO	exact 2-variable analytic updates	no QP solver, very fast
    Core-set / active sampling	train only on boundary candidates	compact O(1/ε) core set
    Incremental	sequential KKT updates	streaming-friendly
    Cascade / parallel	pool local support vectors across machines	horizontal scaling

    Conclusion: because only the support vectors (boundary points) determine an SVM, scalable algorithms identify them by repeatedly concentrating on the KKT-violating points (chunking, decomposition, SMO) or by data-level strategies (sampling, core sets, incremental, parallel) — avoiding the O(n^3) full-QP solve and making SVM practical for large data sets.

20. Q7. Briefly describe the following approaches to clustering: * partitioning methods * hierarchical methods * density-based methods * grid-based methods * model-based methods * methods for high-dimensional data * constraint-based methods Give examples in each case.202214m

    Module 4: Cluster Analysis

    Briefly describe the following approaches to clustering:

    • partitioning methods
    • hierarchical methods
    • density-based methods
    • grid-based methods
    • model-based methods
    • methods for high-dimensional data
    • constraint-based methods

    Give examples in each case.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Overview of Clustering Approaches (with Examples)

    Clustering groups objects so that objects within a cluster are similar and objects in different clusters are dissimilar. The main approaches are:

    1. Partitioning Methods

    Partition $n$ objects into a pre-specified number $k$ of clusters by iteratively refining the cluster representatives until a criterion (typically the squared error) is minimised.

    • Examples: k-Means (mean-based centroid), k-Medoids / PAM (uses actual data points as medoids — robust to outliers).

    2. Hierarchical Methods

    Create a nested hierarchy (dendrogram) either:

    • agglomeratively (bottom-up) — each object is its own cluster initially; repeatedly merge the two closest clusters (AGNES);
    • divisively (top-down) — start with one cluster and split (DIANA).
      No $k$ is required in advance — choose it by cutting the dendrogram.
    • Examples: AGNES, DIANA, BIRCH (scalable, uses CF-trees), CURE (multiple representative points, handles arbitrary shapes).

    3. Density-Based Methods

    Clusters are dense regions of points separated by low-density areas. They can find clusters of arbitrary shape and naturally identify noise.

    • Examples: DBSCAN (dense regions via ε-neighbourhood and MinPts: core/border/noise points), OPTICS (handles varying densities), DENCLUE.

    4. Grid-Based Methods

    Overlay the data space with a grid of cells and do the clustering on the cells, not on individual objects — the cost depends on the number of cells, not on the number of data objects, so clustering is very fast.

    • Examples: STING (statistical summaries per cell), CLIQUE (grid + subspace), WaveCluster.

    5. Model-Based Methods

    Assume the data follow a probabilistic (mixture) model — one probability distribution per cluster — and find the model that best fits the data (highest likelihood). Membership becomes a probability rather than a hard assignment.

    • Examples: EM (Expectation–Maximization) for Gaussian mixtures, Self-Organising Maps (Kohonen nets), COBWEB (conceptual clustering).

    6. Methods for High-Dimensional Data

    In high dimensions distances concentrate and standard clustering degrades (curse of dimensionality). Approaches:

    • subspace clustering — find clusters in lower-dimensional subspaces;
    • co-clustering / bi-clustering — group rows and columns simultaneously (common in gene-expression analysis);
    • dimension-reduction pre-processing, e.g. PCA, before clustering.
    • Examples: CLIQUE, PROCLUS (projected clustering), co-clustering / block clustering.

    7. Constraint-Based Methods

    Perform clustering subject to user or application constraints, e.g. must-link / cannot-link pairs, or spatial obstacles.

    • Examples: COD (Clustering with Obstacles), COP-KMEANS (must-link / cannot-link constraints).

    Summary Table

    Approach	Core idea	Example
    Partitioning	split into k clusters, iterate	k-means, PAM
    Hierarchical	nested dendrogram; merge/split	AGNES, BIRCH, CURE
    Density-based	dense regions separated by sparse areas	DBSCAN, OPTICS
    Grid-based	operate on grid cells	STING, CLIQUE
    Model-based	fit a probability model	EM / GMM, SOM
    High-dimensional	subspace / co-clustering	CLIQUE, PROCLUS
    Constraint-based	obey background constraints	COP-KMEANS, COD

21. Q8. What are the differences between the three main types of data warehouse usage — information processing, analytical processing and data mining? Discuss the motivation behind OLAP mining (OLAM).202214m

    Module 1: Data Warehousing and Business Analysis

    What are the differences between the three main types of data warehouse usage — information processing, analytical processing and data mining? Discuss the motivation behind OLAP mining (OLAM).

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Data Warehouse Usage Types & Motivation for OLAM

    Three Types of Data Warehouse Usage

    Aspect	Information Processing	Analytical Processing	Data Mining
    Goal	Query, basic statistics, reporting	Multidimensional analysis (OLAP)	Discover hidden patterns/knowledge
    Operations	Simple queries, cross-tabs, charts	Roll-up, drill-down, slice, dice, pivot	Classification, clustering, association, prediction
    User interaction	Passive — user asks, system reports	Interactive — user explores the cube	Can be automatic — system discovers patterns
    Output	Reports, summary tables	Multidimensional views	Rules, models, clusters, predictions
    Example	"Total sales last quarter"	"Sales by Region × Product × Time, drilled to month"	"Which customers are likely to churn?"

    • Information processing = basic querying/reporting — answers known questions.
    • Analytical processing (OLAP) = interactive multidimensional exploration — user still drives the analysis by choosing what to slice/dice.
    • Data mining = automated discovery — finds patterns the user didn't know to ask about (association rules, clusters, classifiers, outliers).

    Motivation for OLAP Mining (OLAM)

    OLAM (On-Line Analytical Mining) integrates OLAP with data mining, applying mining techniques directly on multidimensional data cubes rather than flat/raw data. Motivations:

    1. High quality of data in warehouses — DW data is already cleaned, integrated, and consistent, so mining results are more reliable than mining raw operational data directly.
    2. Available information processing infrastructure — ETL, metadata, indexing, and OLAP engines built for the warehouse can be reused for mining, avoiding duplicate infrastructure.
    3. OLAP-based exploratory data analysis — users can interactively drill/roll/slice/dice to first narrow down interesting regions of data, then apply mining algorithms only where needed — much more efficient than mining the whole raw dataset blindly.
    4. On-line selection of mining functions — integrating mining with OLAP navigation lets users flexibly switch between different mining tasks (classification, association, clustering) at different cube cells/granularities during the same interactive session.

            Data Warehouse (Cube)
                   │
         ┌─────────┼─────────┐
         ▼         ▼         ▼
       OLAP     OLAM       Mining
     (explore) (integrated) (patterns)
         └─────────┴─────────┘
            Combined interactive,
            multi-level analysis
    

    In short: OLAM lets analysts interactively navigate to the right subset of data using OLAP, then mine that subset for deeper patterns — combining the strengths of both technologies instead of treating them as separate tools.

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. Q9a. For the following vectors, \mathbf{x} and \mathbf{y}, calculate the indicated similarity or distance measures : (i) \mathbf{x} = (0, -1, 0, 1), \mathbf{y} = (1, 0, -1, 0) cosine, correlation (ii) \mathbf{x} = (0, 1, 0, 1), \mathbf{y} = (1, 0, 1, 0) Euclidean, SMC20227m

    Module 2: Data Mining Fundamentals and Association Rule Mining

    For the following vectors, $\mathbf{x}$ and $\mathbf{y}$, calculate the indicated similarity or distance measures :

    (i) $\mathbf{x} = (0, -1, 0, 1)$, $\mathbf{y} = (1, 0, -1, 0)$ cosine, correlation
    (ii) $\mathbf{x} = (0, 1, 0, 1)$, $\mathbf{y} = (1, 0, 1, 0)$ Euclidean, SMC

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Similarity/Distance Measures — Two Vector Pairs

    (i) x = (0, -1, 0, 1), y = (1, 0, -1, 0) — Cosine & Correlation

    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}$$

    Correlation:
    Mean $\bar{x} = \dfrac{0-1+0+1}{4} = 0$, mean $\bar{y} = \dfrac{1+0-1+0}{4} = 0$

    Since both means are already 0, $(x_i-\bar{x}) = x_i$ and $(y_i-\bar{y})=y_i$:

    $$r = \frac{\sum x_i y_i}{\sqrt{\sum x_i^2 \cdot \sum y_i^2}} = \frac{0}{\sqrt{2 \times 2}} = \boxed{0}$$

    Both cosine and correlation are 0 — x and y are orthogonal/uncorrelated.

    ---

    (ii) x = (0, 1, 0, 1), y = (1, 0, 1, 0) — Euclidean & SMC

    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}$$

    Simple Matching Coefficient (SMC) — counts matches including 0-0 (used for symmetric binary attributes):
    $$SMC = \frac{f_{11}+f_{00}}{f_{11}+f_{00}+f_{01}+f_{10}}$$

    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_{00}=0,\ f_{01}=2,\ f_{10}=2$

    $$SMC = \frac{0+0}{0+0+2+2} = \boxed{0}$$

    Summary Table

    Pair	Measure	Value	Interpretation
    x,y (set i)	Cosine	0	Orthogonal (no directional similarity)
    x,y (set i)	Correlation	0	No linear relationship
    x,y (set ii)	Euclidean distance	2	Maximum distance for these binary 4-D vectors
    x,y (set ii)	SMC	0	Zero matching bits (complete complements) — no 0-0 or 1-1 overlap

    Both vector pairs turn out to be complete "opposites" of each other bit-wise, which is why every measure returns either 0 (no similarity/correlation) or the maximum possible distance.

24. Q9b. Discuss overfitting and underfitting in decision tree construction with suitable example.20227m

    Module 3: Classification and Prediction

    Discuss overfitting and underfitting in decision tree construction with suitable example.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Overfitting and Underfitting in Decision Tree Construction

    Overfitting

    Overfitting is when the decision tree is grown to fit the training data too precisely — including random noise, outliers, and accidental coincidences — rather than the true underlying pattern. The tree gets very low (often zero) training error but performs poorly on unseen test data because it has memorised the training set instead of generalising.

    Causes in decision trees:

    • Growing the tree until every training tuple is perfectly classified (no pruning, or an extremely small minimum-leaf-size).
    • Building a very deep, bushy tree that creates a separate branch/leaf for noisy or uncommon attribute combinations.
    • Choosing splitting attributes that over-segment the data (accidental patterns in small partitions are treated as real structure).

    Detection: a large gap between the training accuracy and hold-out/validation accuracy is a classic symptom.

    Remedies:

    • Pre-pruning — stop growing the tree early (e.g., when the information-gain of the best split falls below a threshold, or when a node contains fewer than a minimum number of tuples).
    • Post-pruning — grow the full tree and then prune branches that do not improve accuracy on a validation set (cost-complexity or reduced-error pruning).
    • Limit the maximum depth; use cross-validation to choose tree size; use ensembles such as random forests which average many trees and reduce variance.

    Underfitting

    Underfitting occurs when the decision tree is too simple to capture the structure of the data — for example, a tiny tree with only one or two leaves that ignores most attributes. Both training and test errors are high because the model cannot express the true decision boundary (a high-bias problem).

    Remedies:

    • Allow deeper trees / larger splits (relax the minimum-samples and pruning thresholds).
    • Provide more informative features and more training data.
    • Use a more expressive model (e.g., increase depth or switch to an ensemble / larger-capacity classifier).

    Suitable Examples

    • Overfitting example: In a "play tennis?" dataset, a fully grown tree may create a branch such as "Outlook = Sunny ∧ Humidity = 65 → No", created only to satisfy the one noisy training example sitting at that point. Training accuracy becomes 100%, but on a new day with Humidity = 65 the tree irrationally predicts "No", where the general pattern would suggest "Yes".
    • Underfitting example: If the tree is limited to a single leaf ("always predict Play = Yes"), it is too simple to capture the seasonal/temperature structure in the data, giving a high error on both the training and test sets.

    Trade-off

    There is a bias–variance trade-off: underfitting ↔ high bias (too simple); overfitting ↔ high variance (too complex). The right tree complexity is usually chosen with cross-validation and pruning, so that the final tree generalises well while remaining interpretable.