2022 question paper

Data Mining

22 questions

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 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 →
Search Google Ask 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.
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 →
Search Google Ask AI
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 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 →
Search Google Ask 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.
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 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 →
Search Google Ask 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.
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 →
Search Google Ask AI
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 →
Search Google Ask AI
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 →
Search Google Ask AI
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 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 →
Search Google Ask 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:

Choosing a non-empty itemset $Y$ from the $d$ items to be the "antecedent ∪ consequent" (the full rule itemset).

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).
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 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 →
Search Google Ask 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.
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 →
Search Google Ask AI

Q2a. What is data mining? Differentiate data mining with traditional database system.20227m

Module 2: Data Mining and Association Rule Mining

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

View this question on its own page →

Search Google Ask 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?"

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 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 →
Search Google Ask 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

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.

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.

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

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.

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 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 →

Search Google Ask 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.

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 →
Search Google Ask AI
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 →
Search Google Ask AI
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 →
Search Google Ask AI
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 →
Search Google Ask AI
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 →
Search Google Ask AI
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 →
Search Google Ask AI

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 →

Search Google Ask 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:

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.
Available information processing infrastructure — ETL, metadata, indexing, and OLAP engines built for the warehouse can be reused for mining, avoiding duplicate infrastructure.
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.
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.

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 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 →

Search Google Ask 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.

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 →
Search Google Ask AI

Previous year2021 Next year2025

Data Mining

Derivation

What is Data Mining? Data Mining vs Traditional Database Systems

Definition

Data Mining vs Traditional Database System

Handling Duplicate and Redundant Data

Methods

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

Part A — Apriori Algorithm

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

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

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

Final Frequent Itemsets (Apriori)

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)

FP-Tree Structure

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

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

Efficiency Comparison

Data Warehouse Usage Types & Motivation for OLAM

Three Types of Data Warehouse Usage

Motivation for OLAP Mining (OLAM)

Similarity/Distance Measures — Two Vector Pairs

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

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

Summary Table