PadhaikoAll subjects

Introduction

Data Mining (ENCT 435)

Open in the Padhaiko app

1.1 Relationship between Data Mining and Machine Learning

Modern organizations accumulate vast repositories of transactional logs, sensor readings, medical records, and web interactions. Raw data by itself has limited value until meaningful structure is extracted from it. Data mining and machine learning work hand in hand to turn raw observations into actionable knowledge.

Definition

Data Mining and Machine Learning

How Data Mining and Machine Learning Relate

Rather than being competing disciplines, machine learning serves as the algorithmic engine inside the broader data mining workflow:

  1. Machine learning supplies the induction methods: Classification trees, Naive Bayes, association rule miners, support vector machines, and clustering algorithms are ML techniques used to capture regularities in data.
  2. Data mining supplies the end-to-end context: Real-world data mining adds problem formulation, database extraction, denormalization, handling missing/noisy records, scalability to massive datasets, interpretability for domain experts, and ethical governance.
  3. Structural descriptions over black-box memorization: In classic data mining (following Witten, Frank, and Hall), a learned pattern is most valuable when it forms an explicit structural description—something a human analyst can inspect, explain, and use to make predictions on unseen cases.
AspectData MiningMachine Learning
Primary GoalDiscover novel, useful, and understandable patterns in large stored datasetsLearn generalizable predictive or descriptive models from experience
ScopeEnd-to-end process (data selection, preprocessing, transformation, modeling, evaluation)Focuses primarily on learning algorithms, generalization theory, and optimization
Typical Data ScaleOften large historical databases, data warehouses, or transaction logsRanges from small curated benchmarks to massive streaming datasets
Role of InterpretabilityHigh priority on human-readable structural patterns (rules, trees, segments)Ranges from interpretable models to black-box predictors (e.g., deep neural nets)

1.2 Describing structural patterns using examples: The Weather Problem, Contact Lenses, Irises, CPU Performance, and Labor Negotiations.

To understand what "learning a structural pattern" means in practice, data mining introduces five classic benchmark datasets. Each dataset highlights a distinct data challenge—nominal attributes, numeric attributes, regression targets, and messy real-world records.

1. The Weather Problem

The Weather problem is a miniature dataset used to decide whether a hypothetical outdoor game should be played (yes or no) based on four weather attributes: outlook (sunny, overcast, rainy), temperature (hot, mild, cool—or numeric in ), humidity (high, normal—or numeric ), and windy (true, false).

Sample Instances from the Nominal Weather Dataset
OutlookTemperatureHumidityWindyPlay
SunnyHotHighFalseNo
SunnyHotHighTrueNo
OvercastHotHighFalseYes
RainyMildHighFalseYes
RainyCoolNormalFalseYes
RainyCoolNormalTrueNo
OvercastCoolNormalTrueYes
SunnyMildHighFalseNo

From the full -instance weather table, a rule learner can extract concise classification rules such as:

This example shows how a compact set of structural rules can summarize a table of observations and predict outcomes for new days.

2. Contact Lenses

The Contact Lenses dataset records patient ophthalmic examinations to recommend one of three classes: none (no contact lenses), soft lenses, or hard lenses. Its four attributes are all nominal:

A structural decision tree for this domain quickly discovers a decisive root rule: if tear-production-rate = reduced, recommend none. If tear production is normal and astigmatism = yes, myope patients receive hard lenses. Contact Lenses illustrates multi-class classification where domain rules are exact and compact.

3. Irises (Fisher's Iris Dataset)

Collected by Edgar Anderson and analyzed by R. A. Fisher (), the Iris dataset contains flower specimens divided equally across three species ( each): Iris setosa, Iris versicolor, and Iris virginica. Unlike the nominal Weather and Contact Lenses tables, every input attribute is continuous (numeric) measured in centimeters:

Because inputs are numeric, structural patterns take the form of inequality thresholds (e.g., petal length < 2.45 cm cleanly separates Iris setosa from the other two species) or linear/geometric decision boundaries.

4. CPU Performance

The CPU Performance dataset (209 computer hardware models) predicts a processor's published relative performance (PRP) from six numeric hardware specifications: machine cycle time (MYCT), minimum and maximum main memory (MMIN, MMAX), cache size (CACH), and minimum/maximum channels (CHMIN, CHMAX).

Here, the target output is a continuous numeric quantity rather than a category. Instead of decision rules yielding yes or no, the structural pattern is a regression equation (linear model):

CPU Performance demonstrates numeric prediction (regression).

5. Labor Negotiations

The Labor Negotiations dataset summarizes collective bargaining agreements in Canada, classified as good or bad contracts. It contains attributes mixing numeric values (duration, first-year wage increase, working hours) and nominal values (cost-of-living adjustment, pension plan, standby pay, dental plan). Crucially, many fields contain missing values (?) because not every contract specifies every clause. This dataset demonstrates that practical data mining algorithms must handle mixed attribute types, noise, and incomplete records.

Summary of the Five Classic Benchmark Datasets
DatasetInput AttributesOutput (Target)Key Data Mining Lesson
Weather ProblemNominal (or mixed numeric)Binary (yes / no)Extracting compact human-readable rules and trees
Contact LensesNominal ( attributes)Multi-class ( classes)Exact, complete classification rules for medical choices
IrisesNumeric ( measurements)Multi-class ( species)Threshold splits and boundaries on continuous features
CPU PerformanceNumeric ( hardware specs)Continuous number (PRP)Numeric prediction via linear regression models
Labor NegotiationsMixed numeric and nominalBinary (good / bad)Handling missing values and messy real-world records

1.3 Fielded applications and the distinction between machine learning and statistics

Fielded Applications of Data Mining

Data mining has moved far beyond academic benchmarks into everyday operational systems:

  1. Web Mining and Recommender Systems: Search engines rank pages using link structure and click logs; e-commerce and streaming platforms recommend products or movies using collaborative filtering and association patterns.
  2. Finance, Credit Scoring, and Fraud Detection: Banks evaluate loan applications using historical default patterns and flag anomalous credit-card transactions in real time based on deviations from a cardholder's normal spending profile.
  3. Healthcare and Bioinformatics: Hospitals predict patient readmission risk, classify medical images, and discover gene-expression patterns linked to diseases.
  4. Customer Relationship Management (CRM) and Market Basket Analysis: Retailers analyze point-of-sale baskets to place frequently co-purchased items together, design targeted promotions, and predict customer churn before subscribers leave.
  5. Engineering and Predictive Maintenance: Manufacturing plants and power grids monitor vibration, temperature, and voltage streams to forecast equipment failure before breakdowns occur.

Distinction Between Machine Learning and Statistics

Machine learning and statistics share many mathematical foundations (probability, optimization, estimation), yet they emerged from different traditions and emphasize different priorities:

AspectMachine LearningStatistics
Core EmphasisPredictive accuracy, algorithmic efficiency, and scalability to large datasetsInference, uncertainty quantification, hypothesis testing, and parameter estimation
Model AssumptionsOften nonparametric or distribution-free (trees, k-NN, neural networks, SVM)Frequently assumes explicit probability distributions and parametric forms (e.g., Gaussian errors)
DimensionalityRoutinely handles hundreds to millions of features ( or high )Classical methods designed for smaller, carefully sampled studies with controlled variables
Validation CultureEmpirical evaluation on held-out test sets and -fold cross-validation-values, confidence intervals, goodness-of-fit tests, and asymptotic theory
Structural OutputRules, decision trees, clusters, and learned representationsEquations, test statistics, and parameter estimates with standard errors

1.4 Ethics in data mining: Reidentification and personal information

Data mining derives immense value from personal records—medical histories, browsing behavior, financial transactions, and location traces—creating serious ethical and legal responsibilities.

Core Ethical Risks

Reidentification and Personal Information

A common misconception is that anonymizing a dataset simply means deleting direct identifiers (such as full name, phone number, email, or citizenship/SSN number). In reality, remaining attributes can uniquely pinpoint individuals.

Definition

Quasi-Identifiers and Reidentification (Linkage Attack)

Safeguards Against Reidentification

  1. Generalization and Suppression (-Anonymity): Modify quasi-identifiers (e.g., replace exact birth date with -year age bands, truncate postal codes) or suppress outlier records so every record is indistinguishable from at least other records in the same equivalence class.
  2. -Diversity: Require each -anonymous equivalence class to contain at least distinct (well-represented) values of the sensitive attribute, preventing homogeneity attacks (where all people share the same disease).
  3. Differential Privacy: Inject calibrated mathematical noise into query answers or aggregates so the presence or absence of any single individual cannot be reliably inferred.
  4. Data Minimization and Purpose Limitation: Collect only attributes strictly necessary for the task, retain them no longer than required, and enforce access controls.

Worked Examples

Example 1

Formulating Structural Patterns on the Weather Subset (5 marks)

Consider the -instance subset of the Weather dataset shown in Section 1.2 (containing Yes and No instances).

  1. Identify the baseline (Zero-R) accuracy if we always predict the majority or default class Yes.
  2. Formulate a minimal set of If ... then ... structural rules using Outlook and Windy (or Humidity) that classifies all instances accurately, and compute the coverage and accuracy of each rule.

Baseline accuracy (predicting a single default class): In the -row table, Yes appears times (rows ) and No appears times (rows ). Predicting Yes for every row gets out of correct:

Inspecting single-attribute splits starting with Outlook:

  • When Outlook = Overcast (rows ): both instances have Play = Yes ( accuracy).
  • When Outlook = Sunny (rows ): all three instances in this subset have Humidity = High and Play = No ( accuracy).
  • When Outlook = Rainy (rows ): rows and have Windy = False and Play = Yes (), whereas row has Windy = True and Play = No ().

Constructing the complete rule set:

  1. (covers , correct ).
  2. (covers , correct ).
  3. (covers , correct ).
  4. (covers , correct ).

Total covered instances with training accuracy.

Answer:

Baseline accuracy is (). Using Outlook and Windy, the -rule structural description (Overcast -> Yes, Sunny -> No, Rainy AND Not Windy -> Yes, Rainy AND Windy -> No) covers all instances with accuracy on this subset.

Example 2

Assessing Reidentification Risk via k-Anonymity (5 marks)

A clinic releases an "anonymized" table of patient records after removing names and phone numbers, keeping only {Age, Postal Prefix, Gender, Diagnosis}:

RecordAgePostalGenderDiagnosis
R1MFlu
R2MGastritis
R3FDiabetes
R4FDiabetes
R5MHypertension
R6FAsthma
  1. Identify the quasi-identifiers and the equivalence classes in this released table.
  2. Which records fail -anonymity, and why does {R3, R4} still pose a privacy risk even though it has size ?
  3. Propose a minimal generalization on {Age, Postal, Gender} so that the entire table satisfies -anonymity.

Identifying quasi-identifiers and equivalence classes: The quasi-identifiers are {Age, Postal, Gender}, and Diagnosis is the sensitive attribute. Grouping records with identical quasi-identifiers gives four equivalence classes:

  • Class with (24, 44600, M) size .
  • Class with (31, 44700, F) size .
  • Class with (58, 44600, M) size .
  • Class with (59, 44601, F) size .

Evaluating -anonymity and homogeneity risk:

  • For -anonymity with , every equivalence class must have size . Here, R5 and R6 form singleton equivalence classes (), so an attacker knowing the age, postal code, and gender of either individual can uniquely reidentify them ( linkage certainty).
  • Class has size (satisfies -anonymity), yet both records share the exact same diagnosis (Diabetes). An attacker who knows a woman aged in postal code is in the table learns her diagnosis with certainty without distinguishing R3 from R4 (homogeneity attack; it fails -diversity).

Generalizing to achieve -anonymity across all records: We can generalize Age to , mask the last digit of Postal as 4460*, and generalize Gender to * for R5 and R6 so they merge into one equivalence class of size :

  • R1, R2: (24, 44600, M) (size )
  • R3, R4: (31, 44700, F) (size )
  • R5, R6: (50–60, 4460*, *) (size , containing two distinct diagnoses: Hypertension and Asthma).

Now all equivalence classes have size , so the table is -anonymous (and in fact -diverse for and ).

Answer:
  1. Quasi-identifiers: {Age, Postal, Gender}. Equivalence classes: {R1, R2} (size ), {R3, R4} (size ), {R5} (size ), {R6} (size ).
  2. R5 and R6 violate -anonymity because each is unique. {R3, R4} satisfies -anonymity but fails -diversity because both records have Diabetes (vulnerable to a homogeneity attack).
  3. Generalizing R5 and R6 to (50–60, 4460*, *) merges them into a size- class, achieving -anonymity across all records.

Exercises

Practice Exercises — Introduction to Data Mining

Question 1

Explain the relationship between data mining and machine learning. Why is an explicit structural pattern often preferred over a raw lookup table or opaque score in data mining?

Relationship between Data Mining and Machine Learning: Data mining is the broader knowledge-discovery process aimed at finding valid, novel, potentially useful, and understandable patterns in large datasets. Machine learning provides the core induction algorithms—such as decision trees, rule learners, Bayesian models, neural networks, and clustering—that extract those patterns from data.

Value of Structural Patterns: An explicit structural description (such as decision rules, a decision tree, or a linear regression equation) compresses thousands of raw instances into a compact representation. Unlike a raw lookup table, it generalizes to unseen instances; unlike an opaque black-box score, it lets domain experts inspect, verify, and explain why a prediction was made (for example, explaining why a loan application was rejected or which patient symptom drives a diagnosis).

Answer:

Data mining is the end-to-end discovery process over large datasets, while machine learning supplies the learning algorithms that induce models from examples. Explicit structural patterns are preferred because they generalize beyond memorized training rows and remain interpretable, auditable, and explainable to human decision-makers.

Question 2

Compare the Contact Lenses, Irises, CPU Performance, and Labor Negotiations datasets in terms of attribute types, target output type, and the specific data mining challenge each illustrates.

Comparing Attribute and Target Types:

  • Contact Lenses: purely nominal inputs (age, spectacle-prescription, astigmatism, tear-production-rate) predicting a -class nominal output (none, soft, hard).
  • Irises: purely continuous numeric inputs (sepal/petal length and width) predicting Iris species.
  • CPU Performance: numeric hardware specifications predicting a continuous numeric output (PRP).
  • Labor Negotiations: mixed nominal and numeric attributes with frequent missing values predicting a binary contract rating (good or bad).

Data Mining Challenge Illustrated by Each: Contact Lenses demonstrates clean symbolic multi-class rules; Irises demonstrates threshold splitting and numeric boundaries; CPU Performance demonstrates numeric prediction (regression) rather than classification; Labor Negotiations demonstrates dealing with heterogeneous attributes and missing values in messy real-world records.

Answer:

Contact Lenses (nominal inputs, multi-class) teaches symbolic rule induction; Irises (numeric inputs, multi-class) teaches numeric split boundaries; CPU Performance (numeric inputs, continuous output) teaches regression; and Labor Negotiations (mixed inputs with missing values, binary class) teaches handling incomplete, noisy real-world data.

Question 3

Distinguish between machine learning and classical statistics across four dimensions, and list three real-world fielded applications of data mining.

Machine Learning vs. Classical Statistics:

  1. Primary Objective: ML prioritizes out-of-sample predictive accuracy and scalable algorithms; statistics prioritizes parameter estimation, confidence intervals, and hypothesis testing.
  2. Distributional Assumptions: ML frequently uses flexible nonparametric models (decision trees, -NN, SVMs) without assuming a specific parametric distribution; classical statistics often builds explicit probabilistic models (e.g., normal error assumptions).
  3. Data Size & Dimensionality: ML routinely handles large, high-dimensional observational data; classical statistics traditionally focuses on smaller, carefully designed samples.
  4. Validation: ML relies heavily on train/test splits and cross-validation; statistics emphasizes -values, likelihood ratio tests, and goodness-of-fit statistics.

Three Fielded Applications:

  1. Credit Risk & Fraud Detection: Flagging anomalous card transactions and scoring loan default risk.
  2. Market Basket Analysis & Recommenders: Discovering product associations and generating personalized item recommendations.
  3. Medical Diagnosis & Predictive Maintenance: Predicting disease risk from clinical records or impending machine failures from sensor streams.
Answer:

Machine learning focuses on predictive accuracy, algorithmic scalability, nonparametric models, and cross-validation, whereas classical statistics focuses on inference, hypothesis testing, parametric probability assumptions, and smaller controlled samples. Fielded applications include fraud detection/credit scoring, recommender systems/market basket analysis, and medical/predictive maintenance diagnostics.

Question 4

A simplified linear regression model for CPU Performance predicts relative performance () from memory and cache attributes as:

Given a processor with , , , and , whose actual published performance is :

  1. Compute the predicted .
  2. Compute the absolute prediction error and state why this task is numeric prediction rather than classification.

Substituting the hardware specifications into the linear model:

Computing the absolute prediction error:

Because the output is a continuous numerical quantity measured on an unbounded real scale rather than a discrete categorical label, the task is numeric prediction (regression) rather than classification.

Answer:
  1. Predicted performance: .
  2. Absolute error: . This is numeric prediction because the target variable is continuous rather than a discrete class label.
Question 5

An open municipal dataset of de-identified citizen surveys strips names and IDs but keeps {Ward, Birth Year, Gender}. Suppose records have a unique (Ward, Birth Year, Gender) combination, while the remaining records fall into equivalence classes of size or more.

  1. What percentage of records in this dataset are vulnerable to single-record reidentification via linkage with a public voter list containing {Name, Ward, Birth Year, Gender}?
  2. Explain why stripping direct identifiers was insufficient and propose two mitigation techniques.

Computing the unique reidentification rate: Each of the records with a unique (Ward, Birth Year, Gender) tuple forms an equivalence class of size . Because the voter roll also contains {Ward, Birth Year, Gender} alongside Name, those individuals can be matched -to-:

Only belong to equivalence classes of size .

Why stripping direct identifiers failed and mitigations: Removing names and IDs leaves quasi-identifiers (Ward, Birth Year, Gender) whose combination is nearly unique. Two effective mitigations are:

  1. -Anonymity (Generalization/Suppression): Coarsen Birth Year into -year or -year bands and group small wards so every equivalence class has size .
  2. -Diversity / Differential Privacy: Ensure each equivalence class contains diverse sensitive values (-diversity) or release perturbed aggregate statistics rather than individual microdata (differential privacy).
Answer:
  1. ( out of records) are uniquely reidentifiable via linkage on {Ward, Birth Year, Gender}.
  2. Direct-identifier removal fails because quasi-identifiers uniquely identify individuals when joined with public records. Mitigations include -anonymity (generalizing birth years/wards) and -diversity or differential privacy.
Input: Concepts, Instances, and Attributes →