Data Mining

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.

Answer: (ii) knowledge discovery in databases

KDD stands for Knowledge Discovery in Databases — the overall, multi-step process of turning raw data into useful, actionable knowledge. Data mining is technically just one step within KDD (the pattern-extraction step), while KDD as a whole covers:

Data ─▶ Selection ─▶ Preprocessing ─▶ Transformation ─▶ Data Mining ─▶ Interpretation/Evaluation ─▶ Knowledge

People often use "data mining" and "KDD" interchangeably in casual usage, but formally, data mining is embedded inside the broader KDD pipeline.

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.

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

Answer: (iv) Data transformation

Data mining is historically also known by several near-synonyms:

• Knowledge extraction (extracting patterns/knowledge from data)
• Data archaeology (digging through historical data for insight)
• Data exploration (exploratory analysis of a dataset)

All three of these describe the act of mining itself. Data transformation, however, is a preprocessing step (converting/normalizing data into a suitable form) that happens before mining — it's not itself a synonym for or activity that defines data mining, making it the odd one out.

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.

Answer: (iv) Reduce data volume but produce the same analysis results

Data Reduction techniques shrink the size/volume of a dataset while preserving its analytical integrity, so that mining on the reduced data yields (approximately) the same results as mining on the full data — but faster and cheaper.

Common data reduction techniques:

• Dimensionality reduction (PCA, attribute subset selection)
• Numerosity reduction (sampling, histograms, clustering, regression models)
• Data compression (wavelet transforms, lossy/lossless encoding)
• Data cube aggregation

Note: this is distinct from (i) "delete irrelevant data," which is closer to feature/attribute selection — a technique used within data reduction, but the reduction's actual goal (per the standard definition) is volume reduction with result-preserving fidelity.

Answer: (iii) Data discrimination

• Data characterization summarizes the general features of a single target class (e.g., "typical profile of high-spending customers").
• Data discrimination compares the target class against one or more contrasting classes, highlighting the differences (e.g., "how do high-spending customers differ from low-spending customers?").

Since the question explicitly describes a comparison against contrasting classes, the answer is data discrimination, not characterization (which looks at only one class in isolation).

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

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.

Answer: (i) Hidden relationships among items in large datasets

Association rule mining finds interesting co-occurrence relationships between items in large transactional datasets, expressed as rules of the form:

$$\text{Item}_A \Rightarrow \text{Item}_B \quad [\text{support } s, \text{confidence } c]$$

Example: {Bread, Butter} ⇒ {Milk} [support=20%, confidence=75%] — meaning 20% of all transactions contain all three items, and 75% of transactions with Bread+Butter also contain Milk.

It is not regression (ii — a prediction technique), decision-tree rules (iii — a classification technique), or hierarchical clusters (iv — a clustering technique); it's specifically about discovering frequent co-occurrence / hidden relationships among items.

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.

Answer: (iv) Data Encryption

Standard data preprocessing steps in data mining are:

1. Data Cleaning — handle missing values, noise, outliers, inconsistencies.
2. Data Integration — merge data from multiple sources into a coherent store.
3. Data Reduction — reduce volume (dimensionality/numerosity reduction) while preserving analytical value.
4. Data Transformation/Discretization — normalize, aggregate, or bucket data into a mining-ready form.

Data Encryption is a security measure (protecting data confidentiality), not a data-quality or mining-readiness step — it has no role in the standard preprocessing pipeline, making it the correct "NOT a step" answer.

Answer: (iv) useful information

KDD's whole purpose is to convert raw data into useful, actionable knowledge/information through a pipeline of selection, preprocessing, transformation, mining, and interpretation:

Raw Data ──KDD process──▶ Useful, actionable Information (patterns, rules, insights)

Simply "data" (i) or a bare "query" (iii) is not the output of the process — those are inputs/tools. Generic "information" (ii) is too broad; the defining goal of KDD is specifically useful information that supports decision-making, which is why (iv) is the precise answer.

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.

Answer: (ii) Discover how strongly items are related beyond co-occurrence

Plain support/confidence-based association rules can be misleading: a rule can have high confidence purely because the consequent is very common overall, even if there's no real relationship (this is the classic "buys coffee ⇒ buys tea" trap when both items are just individually popular).

Correlation analysis (e.g., using lift or the chi-square test) checks whether the co-occurrence of items is statistically meaningful rather than coincidental:

$$\text{lift}(A, B) = \frac{P(A \cup B)}{P(A) \cdot P(B)}$$

• lift = 1 → A and B are independent (no real relationship, despite whatever confidence says).
• lift > 1 → positively correlated (occurring together more than expected by chance).
• lift < 1 → negatively correlated.

This is why correlation analysis "goes beyond" simple co-occurrence counting — it tells you whether the relationship is genuinely meaningful, not just frequent. It does not establish causation (option i) — correlation ≠ causation even in this context.

Answer: (i) additional acquaintance used by a learning algorithm to facilitate the learning process

Background knowledge refers to prior/domain knowledge (concept hierarchies, known constraints, expert rules, etc.) that is supplied to a learning/mining algorithm in addition to the raw training data, to guide and improve the learning process — e.g., helping generalize concepts, constrain hypothesis search, or interpret discovered patterns more meaningfully.

It is not itself a specific architecture like a hidden-layer neural network (ii), nor a synonym for "automatic learning" in general (iii) — it's specifically the extra contextual information fed into a learning system.

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).

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.

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).

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?"

Data Mining as Knowledge Discovery — Steps

Data mining, viewed within the KDD (Knowledge Discovery in Databases) framework, involves the following iterative steps:

Raw Data
   │
   ▼
1. Data Cleaning ───────────▶ remove noise, inconsistent data
   │
   ▼
2. Data Integration ────────▶ combine multiple data sources
   │
   ▼
3. Data Selection ──────────▶ retrieve data relevant to the task
   │
   ▼
4. Data Transformation ─────▶ consolidate into forms suitable for mining
   │                           (aggregation, normalization)
   ▼
5. Data Mining ─────────────▶ apply algorithms to extract patterns
   │                           (classification, clustering, association)
   ▼
6. Pattern Evaluation ──────▶ identify truly interesting patterns
   │                           using interestingness measures
   ▼
7. Knowledge Presentation ──▶ visualize/present mined knowledge
   │                           (reports, graphs, rules)
   ▼
Useful Knowledge

Step-by-step explanation

1. Data Cleaning — removes noise and inconsistent/incomplete data.
2. Data Integration — merges data from multiple heterogeneous sources into one coherent store.
3. Data Selection — retrieves only the data relevant to the analysis task at hand.
4. Data Transformation — converts/consolidates data into forms appropriate for mining (e.g., aggregation, normalization, discretization).
5. Data Mining — the essential step where intelligent methods (classification, clustering, association rule mining, etc.) are applied to extract data patterns.
6. Pattern Evaluation — identifies truly interesting patterns representing knowledge, based on interestingness measures (support, confidence, novelty).
7. Knowledge Presentation — visualization and knowledge representation techniques present the mined knowledge to users in an understandable form.

Steps 1–4 together are often called preprocessing, and this whole pipeline is typically iterative — insights from later steps may send you back to refine earlier ones (e.g., pattern evaluation might reveal that different data selection is needed).

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.

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.

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.

Data Mining vs Data Warehousing + 3 Functionalities

What is Data Mining?

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

Data Mining vs Data Warehousing

Aspect	Data Warehousing	Data Mining
Purpose	Store integrated, historical data for querying/reporting	Discover hidden patterns/knowledge from that data
Process	ETL (extract, transform, load) + storage in fact/dimension tables	Applies algorithms (classification, clustering, association)
Output	Organized, queryable repository	Patterns, rules, predictive models
User interaction	User explores via OLAP (roll-up, drill-down, slice, dice)	System (semi-)automatically extracts patterns
Relationship	Provides clean, integrated data as input to mining	Consumes warehouse data to produce insight

Raw Sources ──ETL──▶ Data Warehouse ──mining algorithms──▶ Data Mining (patterns/knowledge)

In short: a data warehouse is the organized store; data mining is the analysis engine that runs on top of it (though mining can also run on data outside a warehouse).

Three Functionalities of Data Mining

1. Classification — assigns data objects to predefined categories/classes based on a model learned from labeled training data (e.g., classifying an email as spam/not spam using decision trees, naïve Bayes, or neural networks).

2. Clustering — groups data objects into clusters such that objects within a cluster are similar to each other, and dissimilar to objects in other clusters, without using predefined labels (e.g., segmenting customers by purchase behavior using k-means).

3. Association Rule Mining — discovers interesting relationships (rules) between items that co-occur frequently in transactional data (e.g., {Bread, Butter} ⇒ {Milk} [support=20%, confidence=75%] in market-basket analysis).

(Other functionalities include: characterization, discrimination, prediction/regression, outlier analysis, and evolution/trend analysis.)

Data Reduction, Data Discretization & Preprocessing Steps

Data Reduction

Obtains a reduced representation of a dataset that is much smaller in volume, yet closely maintains the integrity/analytical value of the original data — so mining on the reduced data is far more efficient and produces (nearly) the same results.

Techniques:

• Dimensionality reduction — reduces the number of attributes (PCA, attribute subset selection/wrapper methods).
• Numerosity reduction — replaces data with a smaller representation: parametric (regression models) or non-parametric (histograms, clustering, sampling, data cube aggregation).
• Data compression — encoding transformations (wavelet transforms, lossy/lossless compression) to shrink storage size.

Original Data (large) ──[reduction techniques]──▶ Reduced Data (small, representative)

Data Discretization

Converts continuous attribute values into a small number of interval labels or categories, reducing the number of distinct values and making the data suitable for algorithms that work with categorical data.

Methods:

• Binning — equal-width or equal-frequency bins.
• Histogram analysis — partitioning based on data distribution.
• Entropy-based discretization — splits chosen to maximize class purity (supervised).
• Concept hierarchy generation — organizes discretized values into multi-level hierarchies (e.g., Age → {Young, Middle-aged, Senior} → further grouped).

Continuous: 18, 22, 25, 40, 45, 60, 65
Discretized: [18-30)="Young", [30-55)="Middle-aged", [55-70)="Senior"

Major Steps in Data Preprocessing

Raw Data
   │
   ▼
1. Data Cleaning  ────▶ handle missing values, noise, outliers, inconsistencies
   │
   ▼
2. Data Integration ──▶ merge multiple heterogeneous sources into one dataset
   │
   ▼
3. Data Reduction ────▶ shrink volume via dimensionality/numerosity reduction
   │
   ▼
4. Data Transformation/Discretization ──▶ normalize, aggregate, bucket into
   │                                        mining-ready form
   ▼
Clean, Integrated, Reduced, Transformed Data → ready for Mining

1. Data Cleaning — fills missing values, smooths noisy data, identifies/removes outliers, resolves inconsistencies.
2. Data Integration — combines data from multiple databases/files/sources, resolving entity and schema conflicts.
3. Data Reduction — reduces data volume while preserving analytical results (as described above).
4. Data Transformation (including Discretization) — normalizes, aggregates, and converts continuous attributes into discrete categories for algorithms that need them.

These four steps together turn messy, real-world raw data into a clean dataset ready for accurate and efficient mining.

Data Cleaning & Approaches for Missing Values

What is Data Cleaning?

Data cleaning (data cleansing/scrubbing) is the preprocessing step that detects and corrects (or removes) inaccurate, incomplete, inconsistent, or noisy data from a dataset — filling missing values, smoothing noise, identifying/handling outliers, and resolving inconsistencies — so that mining algorithms operate on trustworthy, high-quality data.

Approaches for Handling Missing Values

1. Ignore the tuple
   Discard the entire record. Only reasonable when the missing attribute is essential (e.g., the class label) and the dataset is large enough to absorb the loss.

2. Fill in manually
   A domain expert inspects and enters the correct value. Accurate but time-consuming and infeasible for large datasets.

3. Use a global constant
   Replace all missing entries with a fixed placeholder (e.g., "Unknown", -999). Simple but risky — the mining algorithm may misinterpret the placeholder as a meaningful pattern.

4. Use the attribute mean/median
   Fill numeric gaps with the mean (or median, for skewed distributions) of that attribute computed over all available tuples.

5. Use the mean/median for the same class
   More accurate than a global mean — uses the mean of tuples belonging to the same class as the one with the missing value.

6. Use the most probable value
   Predict the missing value using inference-based methods: regression, Bayesian formalism, or decision-tree induction based on other attributes. This is the most sophisticated and generally most accurate method, since it uses the relationships already present in the data.

                Missing Value Handling
                        │
   ┌─────────┬──────────┼──────────┬────────────┬───────────┐
Ignore    Manual     Global     Attribute    Class-wise   Predicted
tuple      fill      constant   mean/median  mean/median  (regression/
                                                            Bayes/tree)

In practice, methods 4–6 (statistical/model-based imputation) are most commonly used in real mining pipelines because they preserve dataset size while introducing minimal bias, compared to simply dropping records.

Normalizing Data: 200, 300, 400, 600, 1000

Method 1: Min-Max Normalization (new_min=0, new_max=1)

$$v' = \frac{v - min}{max - min} \times (\text{new\_max} - \text{new\_min}) + \text{new\_min}$$

Here $min = 200$, $max = 1000$, range $= 800$, new_min=0, new_max=1, so simply:
$$v' = \frac{v - 200}{800}$$

v	Calculation	v'
200	(200-200)/800	0.000
300	(300-200)/800	0.125
400	(400-200)/800	0.250
600	(600-200)/800	0.500
1000	(1000-200)/800	1.000

Method 2: Z-Score Normalization

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

Mean: $\mu = \dfrac{200+300+400+600+1000}{5} = \dfrac{2500}{5} = 500$

Variance (population):
$$\sigma^2 = \frac{(200-500)^2+(300-500)^2+(400-500)^2+(600-500)^2+(1000-500)^2}{5}$$
$$= \frac{90000+40000+10000+10000+250000}{5} = \frac{400000}{5} = 80000$$

Std dev: $\sigma = \sqrt{80000} \approx 282.84$

v	v − μ	z = (v−μ)/σ
200	−300	−1.06
300	−200	−0.71
400	−100	−0.35
600	+100	+0.35
1000	+500	+1.77

Summary

Original	Min-Max [0,1]	Z-Score
200	0.000	−1.06
300	0.125	−0.71
400	0.250	−0.35
600	0.500	+0.35
1000	1.000	+1.77

Min-max squeezes everything cleanly into [0,1] (bounded by the observed extremes), while z-score centers the data at 0 with unit spread — the value 1000, being furthest from the mean, gets the largest magnitude z-score (+1.77), reflecting how much of an outlier it is relative to the rest of the group.

Association Rule Mining: Definition, Support, Confidence & Correlation Extension

Definition with Example

Association Rule Mining discovers interesting relationships (rules) between items that frequently co-occur in a transactional dataset. A rule has the form:

$$A \Rightarrow B \quad [\text{support } s,\ \text{confidence } c]$$

Example: In supermarket transaction data, the rule
$$\{\text{Bread, Butter}\} \Rightarrow \{\text{Milk}\} \quad [s=20\%, c=75\%]$$
means: 20% of all transactions contain Bread, Butter, and Milk together, and 75% of the transactions that contain Bread and Butter also contain Milk.

Support and Confidence

Support — the fraction of transactions in the database that contain the itemset:
$$support(A \Rightarrow B) = P(A \cup B) = \frac{\text{transactions containing } A \cup B}{\text{total transactions}}$$
It measures how frequently the rule applies — i.e., its statistical significance.

Confidence — the conditional probability that a transaction containing A also contains B:
$$confidence(A \Rightarrow B) = P(B \mid A) = \frac{support(A \cup B)}{support(A)}$$
It measures the strength/reliability of the rule.

A rule is called strong if it satisfies both a minimum support threshold and a minimum confidence threshold.

Extending to Correlation Analysis

Support and confidence alone can be misleading — a rule can have high confidence purely because the consequent B is very common overall, even if A and B have no real relationship (the classic "coffee ⇒ tea" trap when both are individually popular). To check whether A and B are genuinely related, we compute lift:

$$lift(A, B) = \frac{P(A \cup B)}{P(A) \cdot P(B)} = \frac{confidence(A \Rightarrow B)}{support(B)}$$

• lift = 1 → A and B are statistically independent — the "association" is coincidental.
• lift > 1 → A and B are positively correlated (occur together more than expected by chance) — a genuinely useful rule.
• lift < 1 → A and B are negatively correlated (occurrence of A discourages B).

Worked Example

Suppose in 5000 transactions: 3000 contain "computer games", 3750 contain "videos", and 2000 contain both.

• $support(\text{games} \Rightarrow \text{videos}) = 2000/5000 = 40\%$
• $confidence(\text{games} \Rightarrow \text{videos}) = 2000/3000 = 66.7\%$ (looks "strong")
• $lift = \dfrac{2000/5000}{(3000/5000)(3750/5000)} = \dfrac{0.4}{0.6 \times 0.75} = \dfrac{0.4}{0.45} \approx 0.89$

Since lift < 1, buying games actually negatively correlates with buying videos — the high confidence was misleading because videos are popular on their own (75% of all customers buy them anyway). This shows why correlation analysis (lift) is essential beyond raw support/confidence.

Support/Confidence  ──▶  "Looks like a strong rule" (66.7% confidence)
        +
     Lift check      ──▶  Reveals TRUE relationship (lift=0.89 < 1 → negatively correlated!)

Value Ranges of Normalization Methods

Method	Formula	Value Range
Min-Max Normalization	$v' = \dfrac{v-min}{max-min}(\text{new\_max}-\text{new\_min}) + \text{new\_min}$	Bounded exactly to [new_min, new_max] (commonly [0,1])
Z-Score Normalization	$v' = \dfrac{v-\mu}{\sigma}$	Unbounded in theory; in practice typically falls roughly in [−3, +3] for approximately normal data
Decimal Scaling	$v' = \dfrac{v}{10^j}$, where $j$ is the smallest integer such that $\max(|v'|) < 1$	Bounded to (−1, 1)

Notes

• Min-max preserves the exact relationships in the original data and gives a strictly bounded range — but it's sensitive to outliers (a single extreme value stretches/compresses everything else).
• Z-score has no hard bounds since it depends on how far a value is from the mean in standard-deviation units — extreme outliers can produce large |z| values well beyond ±3.
• Decimal scaling normalizes by moving the decimal point, controlled by the maximum absolute value in the data, guaranteeing the result always lies strictly between −1 and 1.

Min-Max:        [0 ──────────── 1]        (fixed, bounded)
Z-Score:      (-∞ ...  -3  0  +3  ... +∞)  (unbounded, ~[-3,3] typical)
Decimal Scale:   (-1 ──────── 1)           (bounded, data-dependent)

Apriori Algorithm — Pseudocode & Key Terms

Pseudocode

Algorithm Apriori(D, min_sup):
    Input:  D = transaction database, min_sup = minimum support threshold
    Output: L = all frequent itemsets in D

    L1 = {frequent 1-itemsets found by scanning D}
    k = 2
    while (L(k-1) is not empty):
        Ck = apriori_gen(L(k-1))          // candidate generation
        for each transaction t in D:
            Ct = subset(Ck, t)             // candidates contained in t
            for each candidate c in Ct:
                c.count++
        Lk = { c in Ck | c.count >= min_sup }
        L = L ∪ Lk
        k = k + 1
    return L

Function apriori_gen(L(k-1)):
    Ck = ∅
    // Join step: join L(k-1) with itself
    for each pair (p, q) in L(k-1) x L(k-1):
        if p and q share the first (k-2) items:
            c = p ∪ {last item of q}
            // Prune step: remove candidates with an infrequent subset
            if all (k-1)-subsets of c are in L(k-1):
                Ck = Ck ∪ {c}
    return Ck

Explanation

1. First pass: count individual items to find frequent 1-itemsets (L1).
2. Iterative passes: for k = 2, 3, ..., generate candidate k-itemsets (Ck) by joining frequent (k-1)-itemsets that share a common (k-2)-item prefix.
3. Prune step: discard any candidate whose any (k-1)-subset is not frequent (using the apriori property: all subsets of a frequent itemset must be frequent).
4. Count & filter: scan the database, count support for surviving candidates, keep only those meeting min_sup → Lk.
5. Repeat until no new frequent itemsets are found.

Key Terms

(i) Support Count
The number of transactions in the database that contain a given itemset:
$$support\_count(X) = |\{t \in D : X \subseteq t\}|$$
Support (as a fraction) = support_count / |D|. It measures how frequently an itemset appears.

(ii) Confidence
For a rule $A \Rightarrow B$, confidence measures how reliably B follows when A is present:
$$confidence(A \Rightarrow B) = \frac{support\_count(A \cup B)}{support\_count(A)}$$
It is the conditional probability $P(B \mid A)$ — the fraction of transactions containing A that also contain B.

Support: "How often does this itemset occur overall?"
Confidence: "Given the antecedent occurred, how often does the consequent follow?"

Apriori Algorithm — 15-Transaction Database (9 Binary Attributes)

Given: min_sup count = 2, min_conf = 70%, database D of 15 transactions over items A1–A9.

Step 1: Scan D → Count 1-itemsets (C1)

Item	Support count	Frequent (≥2)?
A1	2	✅
A2	6	✅
A3	6	✅
A4	4	✅
A5	8	✅
A6	5	✅
A7	7	✅
A8	4	✅
A9	2	✅

L1 = {A1, A2, A3, A4, A5, A6, A7, A8, A9} — every item clears the low min_sup=2 threshold.

L1: [A1]─[A2]─[A3]─[A4]─[A5]─[A6]─[A7]─[A8]─[A9]
     2    6    6    4    8    5    7    4    2

Step 2: Generate C2 (all pairs of L1), scan D, prune → L2

Only pairs with support count ≥ 2 survive (out of the 36 possible pairs, most drop out):

Pair	Count	Pair	Count
A1,A5	2 ✅	A4,A7	2 ✅
A2,A3	3 ✅	A5,A6	3 ✅
A2,A4	3 ✅	A5,A7	5 ✅
A2,A6	2 ✅	A5,A8	2 ✅
A2,A7	2 ✅	A6,A7	3 ✅
A2,A9	2 ✅	A6,A8	2 ✅
A3,A5	3 ✅
A3,A7	3 ✅

(All other 22 pairs, e.g. A1-A2, A1-A3, A2-A5, A3-A4, A4-A5, A7-A8, etc., had count ≤1 and were pruned.)

L2 = {A1A5, A2A3, A2A4, A2A6, A2A7, A2A9, A3A5, A3A7, A4A7, A5A6, A5A7, A5A8, A6A7, A6A8} (14 itemsets)

        L1 (9 items) ──join+prune──▶ L2 (14 pairs, out of 36 possible)

Step 3: Generate C3 via apriori-gen (join L2 with itself + prune using apriori property)

Joining pairs sharing a common first item, keeping only candidates whose every 2-subset is in L2:

Candidate	2-subsets check	Valid?	DB count	Frequent?
A2,A3,A7	A2A3✅ A2A7✅ A3A7✅	✅	0	❌
A2,A4,A7	A2A4✅ A2A7✅ A4A7✅	✅	1	❌
A2,A6,A7	A2A6✅ A2A7✅ A6A7✅	✅	2	✅
A3,A5,A7	A3A5✅ A3A7✅ A5A7✅	✅	3	✅
A5,A6,A7	A5A6✅ A5A7✅ A6A7✅	✅	1	❌
A5,A6,A8	A5A6✅ A5A8✅ A6A8✅	✅	2	✅

L3 = {A2A6A7(2), A3A5A7(3), A5A6A8(2)}

Step 4: Try C4

No two itemsets in L3 share a common 2-item prefix (A2A6A7, A3A5A7, A5A6A8 are all disjoint in their first two items) → no valid C4 candidates → algorithm terminates.

Final Frequent Itemsets

L1 (9):  A1 A2 A3 A4 A5 A6 A7 A8 A9
L2 (14): A1A5  A2A3  A2A4  A2A6  A2A7  A2A9  A3A5
         A3A7  A4A7  A5A6  A5A7  A5A8  A6A7  A6A8
L3 (3):  A2A6A7   A3A5A7   A5A6A8

Total = 26 frequent itemsets

Strong Rules Example (from the maximal itemset A3,A5,A7 — count 3)

Confidence check for rules generated from {A3,A5,A7}:

• A3,A5 ⇒ A7: conf = 3/support(A3A5)=3/3 = 100% ✅ strong
• A3,A7 ⇒ A5: conf = 3/support(A3A7)=3/3 = 100% ✅ strong
• A5,A7 ⇒ A3: conf = 3/support(A5A7)=3/5 = 60% ❌ below 70% threshold

Only the first two rules meet min_conf = 70% and would be output as strong association rules.

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.

(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.

Multilevel Association Rule Mining

What is it?

Multilevel association rule mining discovers association rules at multiple levels of abstraction, using a concept hierarchy over the items (e.g., Item → Subcategory → Category). Mining only at the lowest (raw item) level often misses valuable patterns, because individual items may be too specific to have high support, while their generalized categories do.

                All Items
                /        \
          Beverages      Bakery
          /      \        /    \
      Milk      Juice  Bread  Cookies
      /   \
 Amul Milk  Nestle Milk

Rules can be mined at any level:

• Low level (too specific, low support): {Amul Milk} ⇒ {Nestle Cookies}
• High level (general, higher support): {Beverages} ⇒ {Bakery}

Approaches to Multilevel Mining

1. Uniform Minimum Support
The same min_sup threshold is used across all levels of the hierarchy.

Level 1 (General):   min_sup = 5%  ──▶  applied
Level 2 (Specific):  min_sup = 5%  ──▶  same threshold

• Pros: simple, single threshold to set.
• Cons: high-level (general) items naturally have more support, while low-level (specific) items may fail the same threshold even if they represent genuinely important niche patterns — some interesting low-level rules are missed.

2. Reduced (Level-Specific) Minimum Support
Each level of the hierarchy has its own, typically lower, minimum support threshold as you go deeper.

Level 1 (General):   min_sup = 5%
Level 2 (Category):  min_sup = 3%
Level 3 (Specific):  min_sup = 1%

• Pros: accounts for the fact that specific items are naturally rarer; lets genuinely interesting low-level patterns surface.
• Cons: more thresholds to tune; poor tuning can either flood results with noise or still miss patterns.

Within reduced support, there are two search strategies:

• Level-by-level independent — each level is mined independently regardless of results at other levels.
• Level-cross filtering by single/k-itemset — an itemset at a lower level is examined only if its corresponding ancestor itemset at the level above was found frequent (this prunes the search space significantly using apriori-style reasoning across levels).

3. Group-Based (Item-Specific) Minimum Support
Different groups of items (rather than levels) get their own custom support thresholds, letting users assign lower thresholds to specific item groups they know to be rare-but-important (e.g., luxury goods) and higher thresholds elsewhere.

Summary

Approach	Threshold granularity	Trade-off
Uniform min_sup	One threshold, all levels	Simple, but biased toward general-level rules
Reduced min_sup	One threshold per level	Captures specific-level rules, more tuning needed
Group-based min_sup	Custom threshold per item group	Most flexible, most tuning effort

In short: multilevel mining lets analysts see both broad, general trends and narrow, specific patterns by mining across a concept hierarchy — with reduced/level-specific support being the most common practical approach to avoid missing important niche rules.

Data Cleaning & Data Integration

What is Data Cleaning? Why is it needed?

Data Cleaning (data scrubbing) is the preprocessing step that detects and fixes (or removes) inaccurate, incomplete, noisy, or inconsistent data before mining.

Typical cleaning tasks:

• Missing values — filled via ignoring the tuple, manual entry, global constant, attribute/class mean, or predicted values (regression/Bayesian/decision-tree inference).
• Noisy data — smoothed using binning, regression, or clustering (to detect and remove outliers).
• Inconsistent data — resolved using domain knowledge, functional dependencies, or manual correction (e.g., fixing "NY" vs "New York" mismatches).

Why it's needed: real-world data is "dirty" — incomplete (missing attribute values), noisy (containing errors/outliers), and inconsistent (discrepancies across records). Mining on dirty data produces unreliable, misleading, or outright wrong patterns — "garbage in, garbage out." Clean data is a prerequisite for trustworthy analysis.

Dirty Data ──[Data Cleaning]──▶ Clean Data ──▶ reliable mining results
   │
   ├─ missing values
   ├─ noise/outliers
   └─ inconsistencies

What is Data Integration? Its Role in Data Mining

Data Integration merges data from multiple heterogeneous sources (different databases, flat files, ERP systems, external feeds) into a single, coherent data store for mining.

Key challenges handled during integration:

1. Entity identification problem — recognizing that the same real-world entity may be represented differently across sources (e.g., "customer_id" in one DB vs "cust_no" in another) — requires matching schema and metadata.
2. Redundancy and correlation analysis — an attribute may be redundant if it can be derived from another attribute (present in a different source under a different name); correlation tests (Pearson r for numeric, chi-square for categorical) help detect and eliminate such redundancy.
3. Detection and resolution of data value conflicts — the same real-world entity may have different attribute values in different sources due to different scales, encodings, or units (e.g., weight in kg vs lbs).

Source A (RDBMS) ──┐
Source B (Files)  ──┼──▶ [Data Integration: entity matching, redundancy
Source C (ERP)    ──┘     removal, conflict resolution] ──▶ Unified Dataset

Role in Data Mining

Data integration ensures that the mining algorithms operate on a single, consistent view of the data rather than fragmented, conflicting sources. Without proper integration:

• Duplicate records (from unresolved entity matches) can bias frequency-based mining (e.g., inflating support counts in association rule mining).
• Conflicting values for the same entity can corrupt classification/clustering models.
• Redundant attributes can slow down mining and distort distance/similarity-based algorithms.

In short: data cleaning ensures the data is accurate, while data integration ensures the data is complete and consistent across sources — together they form the foundation that makes all downstream mining results trustworthy.

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.