Data Mining

Answer: (iii) FP-growth

FP-growth mines frequent patterns by first compressing the transaction database into a compact FP-tree (frequent-pattern tree) and then mining that tree with a divide-and-conquer strategy. It never materialises any candidate itemsets at all, so the number of candidate itemsets generated is zero — the minimum possible for any frequent-pattern technique.

Apriori is the natural comparison: at each level it joins the frequent (k-1)-itemsets to generate candidate k-itemsets and then prunes them, and this candidate generation is exactly the bottleneck FP-growth was designed to remove. Partitioning and dynamic itemset counting both follow the same Apriori-style generate-and-test paradigm, so they do generate candidate itemsets. Hence (iii) is correct.

Answer: (ii) Apriori

Apriori is the classic algorithm for mining frequent itemsets. It uses the Apriori property — any subset of a frequent itemset must itself be frequent — to generate candidate itemsets level by level and prune unpromising ones against a minimum support threshold. The frequent itemsets it returns are then used to generate association rules evaluated by support, confidence and lift.

K-means is a clustering algorithm, a decision tree is a supervised classification/prediction model, and Naive Bayes is a probabilistic classifier. None of them produces frequent itemsets, so (i), (iii) and (iv) are wrong.

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.

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.

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.

Solution

Correct Answer: (iii) Median

Explanation

The median is the middle value of the sorted data. It depends only on the position of values, so a few extreme outliers barely change it. The mean uses every value, so one huge value can pull it far from the typical value.

Example: data 10, 12, 13, 14, 500. Mean = 109.8 (misleading), median = 13 (representative).

Why other options are incorrect:

• (i) Mean - strongly affected by outliers.
• (ii) Variance and (iv) Standard deviation - these measure spread, not central tendency, and are also sensitive to outliers.

Answer: (iii) Median

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.

Solution

Correct Answer: (ii) 25%

Explanation

Support of an itemset = (number of transactions containing the itemset) / (total number of transactions)

Support = 50 / 200 = 0.25 = 25%

Why other options are incorrect:

• (i) 10% = 20/200, (iii) 20% = 40/200, (iv) 50% = 100/200.

Answer: (ii) 25%

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

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.

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.

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

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.

Solution

Correct Answer: (iii) Frequency with which the itemset occurs in the database

Explanation

Support tells how often an itemset appears in the transaction database (as a count or as a fraction/percentage of all transactions). Itemsets whose support is at least the minimum support threshold are called frequent itemsets.

Why other options are incorrect:

• (i) This describes confidence: P(consequent | antecedent).
• (ii) Number of attributes and (iv) Number of rules - not what support means.

Key Points to Remember:

• Support(A => B) = P(A and B)
• Confidence(A => B) = support(A and B) / support(A)

Answer: (iii) Frequency with which the itemset occurs in the database

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.

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.

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

Data Mining and the KDD Process

Definition. Data mining is the task of discovering valid, novel, potentially useful and ultimately understandable patterns — models, rules, clusters, associations — from large volumes of data. It sits at the intersection of database systems, statistics and machine learning, turning stored data into knowledge that supports decision making. A pattern counts as knowledge only if it is previously unknown, holds on new data, and is useful to the user; mining is not a random hunt for anything unusual.

Examples

• A supermarket mines point-of-sale baskets and finds the rule {bread, butter} -> milk with, say, support 8% and confidence 70%, which guides shelf placement and bundle offers.
• A bank mines card transaction histories to flag fraud by matching each transaction against the customer's normal spending profile.
• A telecom operator clusters customers by usage patterns to design targeted tariff plans.

Steps in the KDD Process

Knowledge Discovery in Databases (KDD) is the overall, iterative procedure for converting raw data into usable knowledge; data mining is the single step inside it that extracts the patterns. The standard steps are:

1. Data cleaning — remove noise and inconsistent records (missing values, duplicates, wrong entries).
2. Data integration — combine data from multiple databases, files or schemas into a coherent store.
3. Data selection — retrieve only the data relevant to the analysis task.
4. Data transformation — normalise, aggregate, summarise and discretise into forms suitable for mining.
5. Data mining — apply intelligent methods (classification, clustering, association rule mining, regression, etc.) to extract patterns.
6. Pattern evaluation — identify genuinely interesting, valid and useful patterns using objective measures (support, confidence, accuracy) together with domain knowledge.
7. Knowledge presentation — present the mined knowledge through visualisation, graphs, reports, queries or rules.

Raw data -> Cleaning -> Integration -> Selection -> Transformation
                                                        |
Knowledge <- Evaluation <- Data mining <----------------+

Because any step may expose problems that send the process back to an earlier step, KDD is a loop rather than a one-pass pipeline.

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 Preprocessing Techniques in Data Mining

Definition. Data preprocessing is the set of operations applied to raw data before mining, in order to improve data quality. Real-world data is typically incomplete, noisy, inconsistent and heterogeneous; mining on dirty data produces misleading results.

1. Data cleaning

1. Missing values — ignore the record, fill in manually, or infer automatically: a global constant, the attribute mean/mode, the most probable value (estimated via regression or a decision tree), or KNN imputation.
2. Noise reduction — binning (equal-width / equal-depth), regression (fit a smooth curve to the data), clustering (points far from every cluster are treated as outliers and removed), or sorting followed by smoothing.
3. Inconsistency and duplicates — resolve naming and code conflicts (CS vs Computer Sci), enforce domain and integrity checks, and remove duplicate records.

2. Data integration

• Combines data from several databases, flat files or cubes into a single store.
• Schema integration — match entity and attribute names (cust-id with customer-id) and resolve structural conflicts.
• Redundancy detection — correlation analysis, $\chi^2$ tests and covariance identify duplicate or closely related attributes; highly correlated features can otherwise create spurious patterns.
• Conflict resolution — reconcile different units, scales and encoding conventions (e.g. kilograms vs pounds) using metadata.

3. Data reduction

Obtain a smaller representation of the data while keeping the mined results essentially the same.

• Dimensionality reduction — feature selection (relief, $\chi^2$) and feature extraction (PCA, SVD, wavelets) to combat the curse of dimensionality.
• Numerosity reduction — parametric methods (regression, log-linear models) or non-parametric methods (histograms, sampling, clustering).
• Compression — lossless vs lossy compression (wavelets, principal components).
• Generalisation — replace low-level values by higher-level concepts through a concept hierarchy (street → city → country).

4. Data transformation

• Normalisation — scale attributes to a common range, essential for distance-based methods such as KNN, K-means and SVM:
  • min–max: $v' = \dfrac{v - \min}{\max - \min}$
  • z-score: $v' = \dfrac{v - \bar{v}}{\sigma}$
  • decimal scaling by a power of 10.
• Encoding — binarisation / one-hot encoding of nominal attributes.
• Aggregation — summarise daily sales into monthly or yearly totals.
• Discretisation — equal-width or equal-depth (quantile) binning, or generalisation into intervals via concept hierarchies.
• Feature construction — derive new meaningful attributes (e.g. $\text{BMI} = \text{weight} / \text{height}^2$) to expose patterns that are hidden in the raw fields.

Conclusion

Preprocessing is iterative and typically occupies the majority of a project's effort (commonly quoted as 60–80%), but it is decisive: no classifier can rescue poorly prepared data, so cleaning, integration, reduction and transformation must be completed before any mining algorithm is run.

Handling Missing Values and Noisy Data

Both are core data cleaning operations, because models and rules mined from poor-quality input are unreliable. The two problems are distinct: a missing value is an absent attribute value, while noise is a random error or deviation in a measured variable.

A. Methods for missing values

1. Ignore the tuple — discard the record entirely. Acceptable only when the missing fraction is very small and records are processed one at a time; otherwise it introduces bias.
2. Fill in manually — a domain expert supplies the value. Most accurate, but expensive, slow and subjective.
3. Use a special value — record an explicit marker such as 'unknown' or '?', which is natural for categorical attributes.
4. Use a central tendency value — substitute the attribute mean, median or mode. A refinement is to fill by class mean (e.g. average salary of the employee's own designation rather than the company-wide average).
5. Predict the most probable value — infer the missing value from the remaining attributes using decision trees, linear regression or Bayesian reasoning. This is generally the most reliable automatic method.

B. Methods for noisy data

1. Binning — sort the values, partition them into equal-frequency bins, then smooth each value by its bin mean, its bin median, or by the bin boundaries (minimum or maximum of the bin). This is local, content-independent smoothing.
2. Regression — fit a function (linear or multiple regression) to the data and smooth the values by fitting them to the regression line, which also absorbs some of the random variation.
3. Clustering — detect and remove outliers; points that do not belong to any cluster or lie far from all cluster centroids are treated as noise and either corrected or discarded.
4. Human inspection — plot the data and let an expert identify and correct obviously wrong values.

Choosing a method

Situation	Preferred method
Very few incomplete records	Ignore the tuple
Categorical attribute	Special 'unknown' value or the mode
Numerical attribute, class label known	Class mean
Other attributes informative about the missing one	Predict most probable value (regression / decision tree)
Skewed numerical variable to be smoothed	Binning
Isolate and remove outliers	Clustering
Small dataset, high cost of error	Manual entry

Applying these steps before mining substantially improves the accuracy, validity and credibility of the discovered patterns.

Preprocessing Pipeline for a Dataset with Numerical, Categorical and Missing Attributes

Raw data is usually incomplete, noisy and inconsistent. The steps below are applied in this order: clean, integrate, transform, reduce, discretize.

Pipeline

Step	What to do	Justification
1. Data cleaning	Missing values: numerical attributes get mean/median (median if skewed); categorical attributes get the mode or an "Unknown" label; if over about 50% of a column is missing, drop it. Noise: smooth by binning or regression. Outliers: detect with IQR or z-score; cap or remove if they are errors. Inconsistency: standardize codes and formats (e.g. "M"/"Male")	Algorithms cannot handle missing values and noise lowers accuracy
2. Data integration	Merge multiple sources, resolve schema and entity conflicts (same customer, different IDs), remove duplicates. Check redundant attributes with correlation (numerical) or chi-square (categorical)	Avoids duplicates and conflicting values and keeps one consistent view
3. Data transformation	Normalize numerical attributes (min-max to [0, 1] or z-score); encode categorical attributes (one-hot, label encoding); apply aggregation or log transform for skewed data	Distance-based methods (KNN, K-means) would otherwise be dominated by large-scale attributes; most algorithms need numbers
4. Data reduction	Attribute subset selection (drop irrelevant/redundant), PCA for dimensionality reduction, sampling (numerosity reduction) if the data is huge	Lowers storage and computation time and reduces the curse of dimensionality
5. Discretization	Convert continuous attributes into intervals using equal-width or equal-frequency binning, and build concept hierarchies (age to young / middle / old)	Needed for association rules and decision trees, and gives more understandable patterns

Why this order

Cleaning must come first, because wrong or missing values would distort later steps. Integration comes before transformation so that scaling is done on the final merged data. Reduction and discretization come last, once the data is clean and consistent.

Example

Attribute Income (numerical, 8% missing): fill with median, cap outliers at the 99th percentile, normalize to [0, 1], then bin into Low / Medium / High. Attribute City (categorical): fix spelling variants and one-hot encode.

Conclusion

The pipeline produces complete, consistent, scaled and compact data, which gives more accurate and reliable mining results.

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.

Functionalities of Data Mining and the Role of Preprocessing

Data mining is the process of discovering interesting patterns and knowledge from large amounts of data. Its functionalities specify the kinds of patterns that can be found.

Major functionalities

Functionality	Description	Example
Concept/class description (characterization and discrimination)	Summarizes the general features of a class, or compares classes	Features of customers who buy a lot vs those who buy little
Association and correlation analysis	Finds items that occur together (frequent patterns)	Bread and butter bought together (market basket)
Classification	Builds a model from labelled data to predict a class label (supervised)	Classify loan applicants as safe or risky
Prediction / regression	Predicts a continuous value	Forecast next month's sales
Clustering	Groups similar objects with no predefined labels (unsupervised)	Customer segmentation
Outlier analysis	Finds objects that do not fit the general behaviour	Credit card fraud detection
Evolution / trend analysis	Studies how objects change over time	Stock price trends

How preprocessing improves quality and reliability

Real-world data is often incomplete, noisy and inconsistent; mining such data gives unreliable results ("garbage in, garbage out"). Preprocessing improves the data on these quality measures:

Quality factor	How preprocessing helps
Accuracy	Cleaning removes noise and errors
Completeness	Missing values are filled or handled
Consistency	Integration and standardization remove conflicts and duplicates
Believability	Verified, cleaned data is trusted more
Interpretability	Discretization and concept hierarchies make patterns easier to understand
Efficiency	Reduction cuts data size and mining time

Effects on the discovered knowledge

• Cleaning prevents wrong patterns caused by errors and outliers.
• Integration gives a single, consistent view across sources.
• Transformation (normalization) stops large-scale attributes from dominating distance-based algorithms.
• Reduction removes irrelevant attributes, so models are simpler and less prone to overfitting.
• Discretization makes rules concise and suitable for algorithms like decision trees and Apriori.

Conclusion

Good preprocessing improves the accuracy, stability and trustworthiness of classification, clustering and association results, and often takes most of the effort in a data mining project.

Association Rule Mining — Definition, Example & Constraint-Based Mining

Definition

Association rule mining searches for interesting co-occurrence relationships among items in a large transactional (or relational) database. The discovered rules have the form

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

where $A$ and $B$ are disjoint itemsets. Support measures how frequently the rule applies, and confidence measures how reliably $B$ appears whenever $A$ appears:

$$\text{support}(A \Rightarrow B) = P(A \cup B) = \frac{\text{no. of transactions containing } A \cup B}{\text{total transactions}}$$

$$\text{confidence}(A \Rightarrow B) = P(B \mid A) = \frac{\text{support}(A \cup B)}{\text{support}(A)}$$

Example

From a supermarket's transaction database:

TID	Items bought
1	Bread, Butter, Milk
2	Bread, Butter
3	Beer, Diaper
4	Bread, Milk
5	Butter, Milk

The rule {Bread} ⇒ {Butter}:

• $\text{support} = \frac{2}{5} = 40\%$ (Bread and Butter appear together in T1, T2)
• $\text{confidence} = \frac{2}{3} \approx 66.7\%$ (of the 3 transactions containing Bread, 2 also contain Butter)

A rule is strong if it exceeds user-specified minimum support ($\text{minsup}$) and minimum confidence ($\text{minconf}$).

Constraint-Based Association Mining

In large databases, plain Apriori/FP-growth can generate an overwhelming number of rules, many of which are uninteresting. Constraint-based mining lets the analyst push user-specified constraints into the mining process so that only rules satisfying the constraints are discovered — this both prunes the search space (better efficiency) and focuses the results to what the user wants.

Kinds of constraints:

1. Rule constraints — limit the form of the rule, e.g., only rules of the form $\text{Sugar} \Rightarrow X$ or rules with 3 or more items in the antecedent.
2. Itemset constraints — require specific items to be present or absent, e.g., only itemsets containing snacks or only itemsets that exclude expensive-items.
3. Support/confidence (interestingness) thresholds — standard minsup/minconf or other measures like lift, e.g., support ≥ 2% AND lift ≥ 1.5.
4. Aggregate constraints — conditions on aggregated values. e.g., "rules for which the average price of items in the rule exceeds $10".

Example:

"Find association rules involving at least one item from the 'Dairy' category whose support is at least 10%."

If the constraint is anti-monotone (e.g., $min(price) \ge 10$), the Apriori pruning property applies — once an itemset violates it, all supersets violate it too, so entire subtrees of the search can be pruned.

Benefit: mining on the constrained space returns far fewer but highly targeted rules, and does so much faster than mining everything and filtering afterwards. Constraint checking is usually pushed inside the candidate-generation step of Apriori or the FP-tree construction step, so only constrained-valid candidates are counted.

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.

Apriori Principle, Candidate Generation and Pruning, and Comparison with FP-Growth

Apriori principle

All non-empty subsets of a frequent itemset must also be frequent. Equivalently, if an itemset is infrequent, every superset of it is also infrequent (the anti-monotone property of support).

Example: if {A, D} is infrequent, then {A, B, D}, {A, C, D} and {A, B, C, D} cannot be frequent, so they need not be checked.

How Apriori works (level-wise search)

1. Scan the database and find frequent 1-itemsets L1.
2. Candidate generation (join step): join Lk-1 with itself to produce candidate k-itemsets Ck.
3. Pruning: remove any candidate that has a (k-1)-subset that is not in Lk-1.
4. Scan the database to count the support of the remaining candidates; keep those with support at least min_sup as Lk.
5. Repeat until no new frequent itemsets are found.

How candidate generation and pruning reduce the search space

With n items there are up to 2^n - 1 possible itemsets, too many to test.

• Join only combines frequent itemsets, so only itemsets that could be frequent are generated.
• Pruning with the Apriori property removes candidates before the costly database scan.

Example: L2 = {AB, AC, AD, BC}. The join step (itemsets sharing the first item) gives ABC, ABD and ACD. ABC survives, because AB, AC and BC are all frequent. ABD is pruned because BD is not in L2, and ACD is pruned because CD is not in L2. Only ABC is counted in the database scan.

Apriori vs FP-Growth

Basis	Apriori	FP-Growth
Approach	Generate-and-test (candidate generation)	Pattern growth using an FP-tree
Candidate generation	Required; can be huge	None
Database scans	One per level (many scans)	Two scans in total
Data structure	Candidate sets and hash trees	Compact FP-tree plus header table
Strategy	Breadth-first, level-wise	Divide-and-conquer (conditional pattern bases)
Speed on large or dense data	Slow	Much faster
Memory	Large candidate sets	FP-tree must fit in memory; compact for dense data
Complexity to implement	Simple	More complex

Conclusion

Apriori is simple and prunes well using the anti-monotone property, but it is costly because of repeated scans and many candidates. FP-Growth removes candidate generation by compressing the data into an FP-tree, so it is more scalable.

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

Types of Association Rules and When Each Is Useful

An association rule A => B states that when A occurs, B tends to occur too, measured by support and confidence.

Types of association rules

Type	Meaning	Example	Useful when
Boolean	Items are only present or absent	computer => antivirus software	Market basket analysis with yes/no purchase data
Quantitative	Involves numeric attributes, which are discretized into ranges	age(30-39) AND income(42K-48K) => buys(HDTV)	Data has numeric attributes such as age, salary, quantity
Single-dimensional	Only one predicate (dimension) is used	buys(X, "milk") => buys(X, "bread")	Simple item-to-item patterns in one table of transactions
Multidimensional	Two or more dimensions or predicates	age(X, "20-29") AND occupation(X, "student") => buys(X, "laptop")	Data warehouses and customer data with many attributes
Positive	Rule on presence of items (A => B)	tea => sugar	Finding items to bundle, promote or place together
Negative	Rule involving absence: A => NOT B, or NOT A => B	buys tea => NOT buys coffee	Finding substitutes and competing products, fraud and anomaly cases

Related types (for completeness)

• Multilevel rules: use concept hierarchies ("milk" => "bread" vs "skim milk" => "wheat bread").
• Single-level rules: all items at the same abstraction level.

Situations where each helps

• Boolean / single-dimensional / positive: supermarket layout, cross-selling and recommendations.
• Quantitative: targeting customers by age or income bands, pricing and credit analysis.
• Multidimensional: customer segmentation and campaigns using several attributes together.
• Negative: detecting substitute products (so you do not stock both aggressively) and unusual behaviour.

Evaluating the rules

Strong rules meet minimum support and confidence; lift is used to check that A and B are really related (lift > 1 means positive correlation).

Conclusion

The choice of rule type depends on the data (binary or numeric, one or many attributes) and the business goal.

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.

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)

Data Mining Functionalities: Characterization, Association and Discrimination

Data-mining functionalities define the kind of patterns a system can discover. Three important ones are:

1. Data characterization

Definition. Data characterization is an automatic summarisation of the general characteristics of a target class of data - the class the user is interested in - drawn from a data set, usually at several abstraction levels.

How it is done: statistical description (count, mean, median, variance), attribute-oriented induction, OLAP roll-up / drill-down on a data cube, or decision-tree induction in which the tree itself is the profile of the class.

Example: a supermarket wants to characterize customers who buy a baby product. The result may read: 80% of these buyers are aged 30-45, 70% shop on weekends and their average bill is Rs. 1,200. This profile supports targeted marketing. Only one class is involved.

2. Data association

Definition. Data association (association rule mining / correlation analysis) discovers interesting associations, correlations, frequent patterns and causal structures among items or attributes in large data sets, without any class label.

Measurements: support and confidence, found by algorithms such as Apriori and FP-growth.

Example - market basket analysis:

$$\{Bread, Butter\} \Rightarrow \{Milk\} \quad (support = 60\%,\ confidence = 100\%)$$

Other examples: the classic diapers and beer rule, web click-stream association (users who open page A also open page B), and correlation between hot weather and soft-drink sales.

3. Data discrimination

Definition. Data discrimination builds a description (discriminant rules) that distinguishes a target class from a contrasting (background) class. It compares the two rather than describing only one.

How it is done: comparison of attribute distributions (box plots, histograms), decision-tree induction on both classes, or statistical significance tests.

Example: in a bank, discriminate good credit-risk customers (target) from bad credit-risk customers (contrast): good-risk customers are usually salaried, aged 30-50, with a debt-to-income ratio below 0.3. Other examples: heavy users vs. light users of a product, buyers vs. non-buyers of a car.

Quick comparison

Functionality	Classes involved	Output	Example
Data characterization	One target class	Profile / summary	Summarize festival shoppers
Data association	None (item to item)	Frequent patterns / rules	Bread + Butter -> Milk
Data discrimination	Target vs. contrast	Discriminant rules	Good vs. bad credit risk

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.

Partitioning Technique for Frequent Itemset Generation

1. Principle

The partition algorithm (Savasere, Omiecinski and Navathe) avoids the repeated database scans of Apriori by splitting the database into pieces that fit in main memory and scanning the data only twice.

Phase 1 - local mining (one pass, partition by partition):

1. Divide the transaction database $D$ into $n$ non-overlapping partitions $D_1, D_2, \dots, D_n$, each small enough to fit in memory.
2. In each partition $D_i$, find the itemsets whose support in that partition is at least $minsup \times |D_i|$ (using Apriori or a hash tree, entirely in memory).
3. Take the union of all locally frequent itemsets as the candidate set $C^*$ for Phase 2.

Why no globally frequent itemset is missed: if an itemset $X$ were infrequent in every partition, then

$$count_i(X) < minsup \cdot |D_i| \ \ \forall i \ \Longrightarrow \ \sum_i count_i(X) < minsup \cdot \sum_i |D_i| = minsup \cdot |D|$$

so $X$ would also be globally infrequent. Contrapositively, every globally frequent itemset must be frequent in at least one partition - Phase 1 cannot drop a true frequent itemset (no false negatives).

Phase 2 - global counting (one single pass over the whole DB): scan $D$ once, count the support of each candidate in $C^*$, and keep only those whose total support is at least $minsup \times |D|$. These are the globally frequent itemsets.

Partition the database D into D1, D2, ..., Dn
for each partition Di:
    find locally frequent itemsets (support >= minsup * |Di|)
    C* = union of all locally frequent itemsets
scan the whole database once:
    count support of every candidate in C*
    L = { X in C* : support(X) >= minsup * |D| }

2. Why it is more efficient than the Apriori algorithm

1. Only two passes over the data, no matter how long the frequent itemsets are; Apriori needs one full scan per level ($k+1$ scans for itemsets of size $k$) plus candidate generation/pruning at every level.
2. Phase 1 works in memory on a small partition, so expensive candidate-set handling and repeated disk I/O of the whole database are avoided.
3. Parallelism and scalability: partitions can be processed simultaneously on different processors, and a database larger than memory can be handled because only one partition is resident at a time.
4. Candidate set $C^*$ is generally much smaller than the level-wise candidate set of Apriori, so the single counting pass in Phase 2 is cheap.

Trade-off: the union of local frequent itemsets may contain a few globally infrequent itemsets (false positives), which Phase 2 filters out; this is a small price for cutting the number of full database scans from many to two.

Q7(b) - Frequent Itemsets and Association Rules by the Apriori Algorithm

Given: 5 transactions, minimum support = 30%, minimum confidence = 80%.

$$minsup\ count = 30\% \ \text{of} \ 5 = 0.30 \times 5 = 1.5 \ \Rightarrow \ an\ itemset\ must\ occur\ in\ \ge 2\ transactions$$

Abbreviations: Bread = B, Butter = Bu, Milk = M, Coke = C, Jelly = J.

TID	Items
T1	Bread, Jelly, Butter
T2	Bread, Butter
T3	Bread, Milk, Butter
T4	Coke, Bread
T5	Coke, Milk

Step 1 - Scan 1: 1-itemsets

Itemset	Transactions	Count	Support	Frequent?
{Bread}	T1, T2, T3, T4	4	4/5 = 80%	Yes
{Butter}	T1, T2, T3	3	3/5 = 60%	Yes
{Milk}	T3, T5	2	2/5 = 40%	Yes
{Coke}	T4, T5	2	2/5 = 40%	Yes
{Jelly}	T1	1	1/5 = 20%	No (< 30%)

$$L_1 = \{\{Bread\}:4,\ \{Butter\}:3,\ \{Milk\}:2,\ \{Coke\}:2\}$$

Jelly is dropped, so no itemset containing Jelly can ever be frequent (Apriori property / downward closure).

Step 2 - Scan 2: candidate 2-itemsets from $L_1$

Candidate	Transactions	Count	Support	Frequent?
{Bread, Butter}	T1, T2, T3	3	3/5 = 60%	Yes
{Bread, Milk}	T3, T4	2	2/5 = 40%	Yes
{Bread, Coke}	T4	1	1/5 = 20%	No
{Butter, Milk}	T3	1	1/5 = 20%	No
{Butter, Coke}	-	0	0%	No
{Milk, Coke}	T5	1	1/5 = 20%	No

$$L_2 = \{\{Bread, Butter\}:3,\ \{Bread, Milk\}:2\}$$

Step 3 - Scan 3: 3-itemsets

The only join candidate is {Bread, Butter, Milk}. Its subset {Butter, Milk} is not in $L_2$, so by the Apriori property the candidate is pruned and no scan is required.

$$L_3 = \varnothing \quad \Rightarrow \quad \textbf{stop}$$

All frequent itemsets

Level	Frequent itemset	Support count	Support %
1	{Bread}	4	80%
1	{Butter}	3	60%
1	{Milk}	2	40%
1	{Coke}	2	40%
2	{Bread, Butter}	3	60%
2	{Bread, Milk}	2	40%

Step 4 - Association rules (minimum confidence 80%)

$$confidence(X \Rightarrow Y) = \frac{support(X \cup Y)}{support(X)}$$

Rules are generated only from itemsets with two or more items:

Rule	Confidence calculation	Confidence	Passes 80%?
Bread $\Rightarrow$ Butter	3/4	75%	No
Butter $\Rightarrow$ Bread	3/3	100%	Yes
Bread $\Rightarrow$ Milk	2/4	50%	No
Milk $\Rightarrow$ Bread	2/2	100%	Yes

Result

Frequent itemsets: {Bread} 80%, {Butter} 60%, {Milk} 40%, {Coke} 40%, {Bread, Butter} 60%, {Bread, Milk} 40%.

Strong (valid) association rules with support $\ge$ 30% and confidence $\ge$ 80%:

1. $\{Butter\} \Rightarrow \{Bread\}$ - support 60%, confidence 100%
2. $\{Milk\} \Rightarrow \{Bread\}$ - support 40%, confidence 100%

The other two candidate rules fail the 80% confidence test (75% and 50%), so they are rejected.