PadhaikoAll subjects

Algorithms: The Basic Methods

Data Mining (ENCT 435)

Open in the Padhaiko app

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

1R (One-Rule) AlgorithmText
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)

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 .

Definition

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

  1. 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:
  1. Missing Values: Ignored cleanly—simply omit the missing attribute from the product for that instance during both counting and prediction.
  2. Numeric Attributes (Gaussian Naive Bayes): Model each numeric attribute within class as a normal distribution with class-conditional mean and standard deviation :
  1. 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 .

Definition

Entropy and Information Gain (ID3)

Let dataset have classes with proportions ():

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 :

PRISM Covering AlgorithmText
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
AspectID3 (Divide-and-Conquer)PRISM (Separate-and-Conquer)
Output StructureDecision tree covering all classes simultaneouslyIndependent IF-THEN rules learned per target class
Splitting CriterionMaximize Information Gain across all classesMaximize target-class precision (tie-break on )
Granularity of ChoiceTests an entire attribute (all branches at once)Tests a single attribute-value pair at a time
Replicated SubtreesSuffers from replicated subtrees on disjunctive conceptsAvoids 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.

Definition

Itemsets, Support, and Confidence

Let be all items and be transactions.

The Apriori Principle and Algorithm

Naively counting all itemsets is computationally infeasible. Apriori (Agrawal & Srikant, ) exploits the anti-monotonicity (downward closure) property of support:

Theorem

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

  1. 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 .
  2. 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:

Perceptron Learning RuleText
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

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.

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

k-Means Clustering AlgorithmText
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

Worked Examples

Example 1

ID3 Information Gain vs. Laplace-Smoothed Naive Bayes (8 marks)

Consider an -instance dataset predicting Buys_Computer (Yes: , No: ) from two binary attributes Student (Yes, No) and Credit (Fair, Excellent):

IDStudentCreditBuys
YesFairYes
YesFairYes
YesFairYes
YesExcellentNo
NoFairYes
NoExcellentYes
NoExcellentNo
NoExcellentNo
  1. Using ID3, compute and and state which attribute becomes the root node.
  2. 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.

Answer:
  1. , Credit is selected as the root.
  2. Laplace Naive Bayes gives and predicted class is No.
Example 2

Finding Frequent Itemsets and Rules with Apriori (7 marks)

Apply the Apriori algorithm to the following transactions using minimum support () and minimum confidence :

  1. List , , , and show how Apriori prunes candidates when forming .
  2. 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)
Answer:
  1. ; ; and are pruned by the Apriori property before scanning, and has count , leaving .
  2. Strong rules from and : (), (), (), ().
Example 3

Fitting Linear Regression and Running One Iteration of k-Means (6 marks)

  1. Fit a simple linear regression line to the points using ordinary least squares.
  2. 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:

Answer:
  1. Fitted regression equation: .
  2. After one -means iteration: with centroid , and with centroid .

Exercises

Practice Exercises — Basic Data Mining Algorithms

Question 1

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:

IDOutlookWindyPlay
SunnyFalseNo
SunnyTrueNo
OvercastFalseYes
RainyFalseYes
RainyTrueNo
OvercastTrueYes

Evaluating attribute Outlook:

  • Outlook = Sunny: No, Yes rule Sunny -> No ( errors).
  • Outlook = Overcast: Yes, No rule Overcast -> Yes ( errors).
  • Outlook = Rainy: Yes, No tie; pick Yes (or No) error.

Total errors for Outlook out of (error rate ).

Evaluating attribute Windy:

  • Windy = False: Yes, No rule False -> Yes ( error).
  • Windy = True: Yes, No rule True -> 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.

Answer:

1R picks Outlook with training error () (vs. for Windy), producing: Sunny -> No, Overcast -> Yes, Rainy -> Yes (or No).

Question 2

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

Answer:

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

Question 3
  1. Given a logistic regression model with , compute for .
  2. 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 :

Answer:
  1. .
  2. Misclassified (); updated weights and .
Question 4

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.

Answer:

The nearest neighbors are , , and , giving Blue vs. Red, so is classified as Blue. Normalization prevents large-scale attributes from dominating Euclidean distance calculations.

Question 5

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.

Answer:

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.

← Output: Knowledge RepresentationCredibility: Evaluating What’s Been Learned →