Algorithms: The Basic Methods
Open in the Padhaiko app4.1 Inferring rudimentary rules (1R algorithm) and statistical modeling (Naive Bayes)
Before reaching for complex models, data mining establishes simple, surprisingly competitive baselines: 1R (a one-level rule learner) and Naive Bayes (a probabilistic classifier).
1. Inferring Rudimentary Rules: The 1R Algorithm
The 1R (One-Rule) algorithm (Holte, ) builds a one-level decision tree—a single set of classification rules that tests just one attribute and predicts the majority class for each value of that attribute.
for each attribute A:
for each value v of attribute A:
count how often each class appears when A = v
find the most frequent class c*
construct rule: IF A = v THEN class = c*
compute total classification errors of A's rule set over all training rows
choose the attribute A* with the smallest total training error (break ties randomly)- Handling Numeric Attributes: 1R sorts instances by the numeric attribute and partitions the range into intervals so each bucket contains at least a minimum number of instances (commonly ) belonging to the majority class, preventing extreme overfitting where every distinct number gets its own rule.
- Overfitting Warning on Identifier Attributes: An attribute like
Student_IDorDatewith a unique value per row achieves training error under 1R, yet generalizes terribly; identifier columns must be excluded before running 1R.
2. Statistical Modeling: Naive Bayes
Rather than picking a single attribute, Naive Bayes uses all attributes simultaneously under Bayes' theorem, assuming that attributes are conditionally independent given the class label .
Naive Bayes Classifier
Given an instance and class , Bayes' theorem gives:
Assuming conditional independence of attributes given :
Since the denominator is identical for all classes, Naive Bayes predicts:
Practical Refinements in Naive Bayes
- Zero-Frequency Problem and Laplace Estimator: If an attribute value never occurred with class in the training set, wipes out the entire product regardless of strong evidence from other attributes. Adding a small pseudocount (typically , Laplace smoothing) for an attribute with distinct values gives:
- Missing Values: Ignored cleanly—simply omit the missing attribute from the product for that instance during both counting and prediction.
- Numeric Attributes (Gaussian Naive Bayes): Model each numeric attribute within class as a normal distribution with class-conditional mean and standard deviation :
- Log-Space Computation: Multiplying many small probabilities risks floating-point underflow; implementations maximize instead.
4.2 Divide-and-conquer: Constructing decision trees (ID3) and calculating Information Gain
Decision tree learners such as ID3 (Iterative Dichotomiser 3, Quinlan ) build a tree top-down using a divide-and-conquer strategy: select the best attribute to split the dataset at the root, partition the data by the attribute's values, and recurse on each child subset until a subset is pure (all instances share one class) or no attributes remain.
Entropy and Information Gain
ID3 measures node impurity using Shannon entropy from information theory—the expected number of bits needed to encode the class of a randomly drawn instance from dataset .
Entropy and Information Gain (ID3)
Let dataset have classes with proportions ():
- Entropy of :
- Expected Entropy after Splitting on Attribute (with values partitioning into ):
- Information Gain of Attribute :
ID3 selects the attribute with the maximum at each node.
4.3 Covering algorithms: Constructing classification rules (PRISM)
Whereas ID3 uses divide-and-conquer to build a tree for all classes at once, covering algorithms use separate-and-conquer to learn IF-THEN classification rules one class at a time.
How the PRISM Algorithm Works
PRISM (Cendrowska, ) targets a single chosen class and iteratively builds pure rules for :
for each class C:
E = copy of full training dataset
while E still contains instances of class C:
start with empty rule: IF (true) THEN class = C
repeat until rule covers only instances of class C (100% pure) or no attributes remain:
for each unused attribute-value pair (A = v):
let p = count of class C covered by adding (A = v)
let t = total instances covered by adding (A = v)
compute accuracy ratio p / t
pick (A = v) maximizing p / t (break ties by maximizing p)
append (A = v) to the rule antecedent and restrict current subset to matches
output the completed rule
remove all instances covered by this rule from E| Aspect | ID3 (Divide-and-Conquer) | PRISM (Separate-and-Conquer) |
|---|---|---|
| Output Structure | Decision tree covering all classes simultaneously | Independent IF-THEN rules learned per target class |
| Splitting Criterion | Maximize Information Gain across all classes | Maximize target-class precision (tie-break on ) |
| Granularity of Choice | Tests an entire attribute (all branches at once) | Tests a single attribute-value pair at a time |
| Replicated Subtrees | Suffers from replicated subtrees on disjunctive concepts | Avoids replicated subtrees by building independent rules |
4.4 Mining association rules: Item sets and the Apriori algorithm
Association rule mining searches transactional databases (such as supermarket baskets) for strong co-occurrences without fixing a target class.
Itemsets, Support, and Confidence
Let be all items and be transactions.
- Itemset: A subset (-itemset if ).
- Support Count : Number of transactions containing . Support is .
- Frequent Itemset: An itemset satisfying .
- Association Rule ():
The Apriori Principle and Algorithm
Naively counting all itemsets is computationally infeasible. Apriori (Agrawal & Srikant, ) exploits the anti-monotonicity (downward closure) property of support:
Apriori Principle (Downward Closure of Support)
If an itemset is frequent, then every non-empty subset of must also be frequent. Equivalently, if an itemset is infrequent, every superset of is guaranteed to be infrequent and can be pruned without scanning the database.
Two-Phase Apriori Workflow
- Find all frequent itemsets ():
- Scan database to obtain frequent -itemsets .
- Candidate Generation ():
- Join step: Merge pairs of sorted -itemsets in that share their first items.
- Prune step: Discard any candidate -itemset if any -subset of is not in .
- Scan transactions to count remaining candidates in and keep those with as . Repeat until .
- Generate association rules from each frequent itemset ():
- For every non-empty proper subset , form rule and retain it if .
4.5 Linear models: Linear/Logistic regression, the Perceptron
When attributes are numeric, linear methods fit hyperplanes directly in attribute space.
1. Linear Regression (Ordinary Least Squares)
Linear regression predicts a continuous target by choosing weights to minimize the Sum of Squared Errors (SSE) across training instances:
For a single predictor (), setting partial derivatives to zero yields the closed-form solution:
In dimensions with design matrix (including a column of s for ), the normal equations give .
2. Logistic Regression
Linear regression cannot safely output class probabilities because is unbounded in . Logistic regression passes the linear score through the logistic (sigmoid) function:
Equivalently, the log-odds (logit) is linear: . Parameters are estimated by maximizing the conditional log-likelihood (minimizing binary cross-entropy) via iterative optimization such as gradient descent or Newton–Raphson.
3. The Perceptron
The Perceptron (Rosenblatt, ) learns a binary separating hyperplane for classes using an online error-driven update:
initialize weights w = 0, bias b = 0, learning rate eta > 0
repeat until no training errors (or max epochs):
for each training instance (x_i, y_i) with y_i in {+1, -1}:
y_hat = +1 if (dot(w, x_i) + b) >= 0 else -1
if y_hat != y_i:
w = w + eta * y_i * x_i
b = b + eta * y_i- Perceptron Convergence Theorem: If the training data is linearly separable, the perceptron algorithm is guaranteed to converge to a separating hyperplane in a finite number of updates. If the data is not linearly separable (such as the XOR function), it cycles indefinitely unless stopped or replaced with a soft-margin / multi-layer model.
4.6 Instance-based learning (k-nearest-neighbor) and Clustering (k-means)
1. Instance-Based Learning: -Nearest-Neighbor (-NN)
-NN performs lazy learning: it stores the training set during training and defers computation until a query arrives.
- Distance Metric: Standard Euclidean distance (or Manhattan ). For nominal attributes, distance is if values match and if they differ.
- Mandatory Normalization: Attributes with large numeric ranges (e.g.,
salaryin thousands vs.agein tens) dominate unnormalized distances. Always scale numeric attributes via min-max normalization or -score standardization . - Prediction and Choice of : Find the closest training instances to and predict the majority class (optionally weighting each neighbor by ), or the mean target value for regression. Small (e.g., ) gives jagged, noise-sensitive boundaries; very large oversmooths local structure.
2. Clustering: The -Means Algorithm
-Means partitions unlabeled instances into disjoint clusters so as to minimize the Within-Cluster Sum of Squared Errors (WCSS / SSE):
choose k initial centroids mu_1, ..., mu_k (randomly or via k-means++)
repeat:
Assignment step: assign each point x_i to cluster j minimizing ||x_i - mu_j||^2
Update step: recompute each centroid mu_j as the mean of points assigned to C_j
until cluster assignments no longer change- Properties and Limitations: Each iteration strictly reduces or preserves SSE and converges rapidly to a local optimum. However, -means requires specifying upfront (often guided by the elbow method), is sensitive to initial centroid placement (mitigated by -means++ or multiple random restarts), struggles with non-spherical clusters of varying densities, and is sensitive to outliers because it uses arithmetic means.
Worked Examples
ID3 Information Gain vs. Laplace-Smoothed Naive Bayes
Consider an -instance dataset predicting Buys_Computer (Yes: , No: ) from two binary attributes Student (Yes, No) and Credit (Fair, Excellent):
| ID | Student | Credit | Buys |
|---|---|---|---|
| Yes | Fair | Yes | |
| Yes | Fair | Yes | |
| Yes | Fair | Yes | |
| Yes | Excellent | No | |
| No | Fair | Yes | |
| No | Excellent | Yes | |
| No | Excellent | No | |
| No | Excellent | No |
- Using ID3, compute and and state which attribute becomes the root node.
- Using Naive Bayes with Laplace smoothing (), compute the posterior probabilities and for the query and classify .
Computing dataset entropy : With Yes and No out of instances:
Computing and :
- For
Student:Student = Yes( rows:Yes,No): .Student = No( rows:Yes,No): .- .
- .
- For
Credit:Credit = Fair( rows:Yes,No): .Credit = Excellent( rows:Yes,No): .- .
- .
Since , Credit is chosen as the root node.
Naive Bayes with Laplace smoothing ( values per attribute) for : Prior probabilities: , .
Normalizing the two unnormalized likelihoods:
Hence Naive Bayes classifies as No.
- ,
Creditis selected as the root. - Laplace Naive Bayes gives and predicted class is
No.
Finding Frequent Itemsets and Rules with Apriori
Apply the Apriori algorithm to the following transactions using minimum support () and minimum confidence :
- List , , , and show how Apriori prunes candidates when forming .
- Generate all strong association rules from and that satisfy .
Pass 1 — Frequent -itemsets (): Counting single items across the transactions (threshold ):
- , , , .
All four meet , so .
Pass 2 — Candidate -itemsets () and frequent -itemsets (): Joining yields pairs:
- () frequent
- () frequent
- () frequent
- () frequent
- () infrequent
- () infrequent
Thus .
Pass 3 — Candidate generation and Apriori pruning for : Joining sorted pairs in with matching first items produces three raw -itemsets:
- : its -subsets are all in , so it survives into . Scanning the database gives (), so it is infrequent.
- : contains infrequent subset pruned before scanning.
- : contains infrequent subset pruned before scanning.
Hence and itemset mining terminates.
Generating rules from and ():
- From (, support ):
- : (Strong)
- : (Strong)
- From (, support ):
- : (Strong)
- : (Strong)
- ; ; and are pruned by the Apriori property before scanning, and has count , leaving .
- Strong rules from and : (), (), (), ().
Fitting Linear Regression and Running One Iteration of k-Means
- Fit a simple linear regression line to the points using ordinary least squares.
- Perform one assignment and update iteration of -means clustering on the four points starting from initial centroids and .
Part 1 — Computing OLS Linear Regression weights : First find the sample means:
Compute and :
Thus:
The fitted line is .
Part 2 — -Means Assignment Step (squared Euclidean distance):
- : ,
- : ,
- : ,
- : ,
Clusters are and .
Part 2 — -Means Centroid Update Step:
- Fitted regression equation: .
- After one -means iteration: with centroid , and with centroid .
Exercises
Practice Exercises — Basic Data Mining Algorithms
Explain the 1R (One-Rule) algorithm and apply it to select the better single attribute (Outlook vs. Windy) on the -instance table below, stating the resulting rule set and its training error rate:
| ID | Outlook | Windy | Play |
|---|---|---|---|
| Sunny | False | No | |
| Sunny | True | No | |
| Overcast | False | Yes | |
| Rainy | False | Yes | |
| Rainy | True | No | |
| Overcast | True | Yes |
Evaluating attribute Outlook:
Outlook = Sunny:No,YesruleSunny -> No( errors).Outlook = Overcast:Yes,NoruleOvercast -> Yes( errors).Outlook = Rainy:Yes,Notie; pickYes(orNo) error.
Total errors for Outlook out of (error rate ).
Evaluating attribute Windy:
Windy = False:Yes,NoruleFalse -> Yes( error).Windy = True:Yes,NoruleTrue -> No( error).
Total errors for Windy out of (error rate ).
Selecting the 1R attribute: Because Outlook achieves fewer errors (), 1R outputs the rule set based on Outlook.
1R picks Outlook with training error () (vs. for Windy), producing: Sunny -> No, Overcast -> Yes, Rainy -> Yes (or No).
How does PRISM differ from ID3 in constructing rules? Trace the first rule generated by PRISM for target class Play = Yes on the -instance table in Exercise 1 (Outlook, Windy Play).
Comparing PRISM and ID3: ID3 builds a single decision tree top-down using Information Gain across all classes simultaneously, whereas PRISM uses separate-and-conquer to build pure IF-THEN rules one class at a time by greedily picking the single attribute-value test maximizing .
Tracing the first PRISM rule for Play = Yes on the -row table ( Yes, No): Evaluating every candidate condition for (p = Play=Yes covered, t = total covered):
Outlook = Sunny:Outlook = Overcast:Outlook = Rainy:Windy = False:Windy = True:
Outlook = Overcast achieves the maximum (pure!) immediately, so PRISM outputs: IF Outlook = Overcast THEN Play = Yes, removes rows and , and continues on the remaining Yes instance (row : Outlook = Rainy AND Windy = False -> Yes).
PRISM learns class-specific rules via separate-and-conquer maximizing , unlike ID3's divide-and-conquer Information Gain tree. On the -row table, Outlook = Overcast gives , immediately producing IF Outlook = Overcast THEN Play = Yes (followed next by IF Outlook = Rainy AND Windy = False THEN Play = Yes).
- Given a logistic regression model with , compute for .
- Given a Perceptron with current weights , bias , and learning rate , compute the updated after observing a single training instance with true label .
Part 1 — Logistic Regression probability:
Part 2 — Perceptron prediction and weight update: First compute the raw activation:
Since , update using and :
- .
- Misclassified (); updated weights and .
Suppose four training points in have already been normalized:
Classify the query point using -Nearest Neighbor (-NN) with Euclidean distance, and explain why feature normalization is crucial before computing distances in -NN when attributes have different units.
Computing Euclidean distances from :
- (
Red) - (
Blue) - (
Blue) - (
Red)
Taking -NN majority vote and explaining normalization: The closest neighbors are (Blue), (Blue), and (Red). With votes for Blue vs. vote for Red, -NN classifies as Blue.
Importance of normalization: If one attribute is measured in thousands (e.g., annual income in NPR) and another in (e.g., GPA), raw squared differences in income completely overwhelm GPA, effectively ignoring the smaller-scale feature. Normalizing all features to comparable scales ensures balanced distance contributions.
The nearest neighbors are , , and , giving Blue vs. Red, so is classified as Blue. Normalization prevents large-scale attributes from dominating Euclidean distance calculations.
Explain the Apriori principle (downward closure of support) and describe the join and prune steps used to generate candidate -itemsets from frequent -itemsets . Why does the prune step save expensive database scans?
The Apriori Principle: Every non-empty subset of a frequent itemset must also be frequent ( whenever ). Conversely, if any subset of a candidate itemset is infrequent, the candidate itself cannot possibly reach minsup.
Join and Prune Steps:
- Join step: Sort items lexicographically within each -itemset in ; join any two itemsets whose first items match (with ) to form candidate -itemset .
- Prune step: Enumerate all subsets of size for each candidate ; if any -subset is absent from , delete from immediately in memory before scanning the transaction database.
Why Pruning Saves Database Scans: Disk/memory scans to count support over millions of transactions dominate Apriori's runtime. Eliminating guaranteed-infrequent supersets in memory shrinks dramatically before touching the transaction table.
The Apriori principle states that all subsets of a frequent itemset must be frequent. Candidate generation joins pairs in sharing their first items and prunes any candidate containing an infrequent -subset, eliminating impossible candidates in memory before expensive database scans.