Data Mining · Week 12

Bayesian & Rule-Based Classification

Bayes' theorem, the naïve Bayesian classifier (categorical and Gaussian), rule-based classifiers with coverage and accuracy, extracting rules from a decision tree, and Weka's training/testing.

ITE34324 videos · 46 min📄 week 12.pdf

▶Lecture videos

Click any timestamp — here or inside the notes — to jump the video to that moment. Your position is remembered.

Support Lecture – Bayesian & Rule-Based Classification

Support lecture for this week's topics.

00:02Naive Bayes: derived from Bayes' theorem 00:55Bayes' equation: posterior, likelihood, prior 02:38Example: P(meningitis | stiff neck)04:36Multiple attributes: the conditional independence assumption 07:17Comparing classes: drop the common denominator 09:06Worked example: Refund, Marital status, Income → Evade 10:49Zero counts and the Laplace correction 15:11Computing the class probabilities and deciding 18:02Second example: buys_computer 19:49Rule-based classification: rules from a decision tree 21:40Using a rule base for prediction

Weka 2.1 – Be a classifier!

Building a tree by hand with Weka's UserClassifier.

00:15Introduction: build a classifier by hand (User Classifier)02:04The segment dataset (image analysis)03:01Setting the test set; the scatter plot 04:46Selecting regions with rectangles to make nodes 08:18Accepting the tree 10:01Evaluating on the test set

Weka 2.2 – Training and testing

Why you must evaluate on independent test data.

00:16Introduction: why training and test sets must differ 02:02Segment-challenge: J48 with a separate test set 02:54Evaluating on the training set (over-optimistic)03:46Percentage split; independent sampling

Weka 2.3 – Repeated training and testing

Repeating holdout with different random splits and averaging.

00:16Introduction: the random seed 01:08Changing the seed changes the result 02:05Repeating with different seeds (94%, 95%…)04:41Mean and standard deviation of accuracy 05:39Result: about 95% ± 2%

1Bayesian classifiers — overview

Bayesian classifiers are statistical classifiers. They predict class membership probabilities, i.e. the probability that a tuple belongs to a class.
They're based on Bayes' theorem.
The simple naïve Bayesian classifier performs comparably to decision trees and some neural networks, with high accuracy and speed on large databases.

Why "naïve"?

It assumes that the effect of an attribute value on a class is independent of the other attributes' values. This is called class-conditional independence. The assumption simplifies computation, which is why it's called "naïve".

Bayesian belief networks are graphical models that, unlike naïve Bayes, can represent dependencies among subsets of attributes. They can also be used for classification.

2Bayes' theorem

Named after Thomas Bayes, an 18th-century English nonconformist clergyman who worked on probability and decision theory.

Symbol	Name	Example meaning (customer aged 35, income $40,000)
X	Evidence: the data tuple	The customer's age and income
H	Hypothesis: X belongs to class C	"Will buy a computer"
P(H\|X)	Posterior (a posteriori) probability of H given X	Probability this customer buys a computer
P(H)	Prior probability of H	Probability any customer buys a computer
P(X\|H)	Posterior of X given H (likelihood)	Probability a buyer is 35 and earns $40,000
P(X)	Prior probability of X	Probability a customer is 35 and earns $40,000

P(H | X) = P(X | H) · P(H) / P(X)

Meningitis

Meningitis (M) causes a stiff neck (S) 50% of the time: P(S|M) = 0.5
P(M) = 1/50,000
P(S) = 1/20

If a patient has a stiff neck, what is the probability of meningitis?

P(M|S) = P(S|M)·P(M) / P(S) = 0.5 × (1/50,000) / (1/20) = 0.0002

So even with a stiff neck, meningitis is very unlikely, because its prior is tiny.

🧪 Try it — Bayes' theorem calculator

P(X|H) P(H) P(X)

3The naïve Bayesian classifier

Setup:

Training set D. Each tuple is X = (x₁, …, xₙ) over attributes A₁ … Aₙ.
There are m classes C₁ … Cₘ.

Decision rule

Predict the class Cᵢ with the highest posterior probability, the maximum posterior hypothesis:

P(Cᵢ|X) > P(Cⱼ|X) for all j ≠ i

By Bayes: P(Cᵢ|X) = P(X|Cᵢ)P(Cᵢ) / P(X).

P(X) is the same for every class, so maximise only P(X|Cᵢ)·P(Cᵢ).
If class priors are unknown, assume all classes are equally likely and maximise P(X|Cᵢ). Otherwise estimate P(Cᵢ) = |Cᵢ,D| / |D|.
Computing P(X|Cᵢ) directly is too expensive with many attributes. Class-conditional independence gives:

Estimating P(xₖ|Cᵢ)

Categorical attribute

P(xₖ|Cᵢ) = (number of class-Cᵢ tuples with value xₖ) / |Cᵢ,D|

Continuous attribute

Assume a Gaussian (normal) distribution with mean μ and standard deviation σ for that class:

g(x, μ, σ) = 1/(√(2π)·σ) · e^{−(x−μ)² / (2σ²)}

P(xₖ|Cᵢ) = g(xₖ, μ_Cᵢ, σ_Cᵢ)

Gaussian example

Buyers' ages are 38 ± 12 (μ = 38, σ = 12). For X with age = 35:

P(age = 35 | yes) = 1/(√(2π)·12) · e^{−(35−38)²/(2·12²)} = 0.0332 × e^−0.03125 ≈ 0.0322

4Worked example — will X buy a computer?

Same 14-tuple training set as Week 11 (9 yes, 5 no). Classify:

X = (age = youth, income = medium, student = yes, credit_rating = fair)

Priors

P(yes) = 9/14 = 0.643
P(no) = 5/14 = 0.357

Conditional probabilities

	P(·\|yes)	P(·\|no)
age = youth	2/9 = 0.222	3/5 = 0.600
income = medium	4/9 = 0.444	2/5 = 0.400
student = yes	6/9 = 0.667	1/5 = 0.200
credit_rating = fair	6/9 = 0.667	2/5 = 0.400

Multiply

P(X|yes) = 0.222 × 0.444 × 0.667 × 0.667 = 0.044
P(X|no) = 0.600 × 0.400 × 0.200 × 0.400 = 0.019

Times the priors

P(X|yes)·P(yes) = 0.044 × 0.643 = 0.028
P(X|no)·P(no) = 0.019 × 0.357 = 0.007

0.028 > 0.007, so the prediction is buys_computer = yes.

🧪 Try it — Naïve Bayes classifier (buys_computer data)

Use Laplacian correction (add 1 to each count, which avoids zero probabilities)

Exam focus

Naïve Bayes calculations are very common. Lay them out exactly like the table:

Priors
Each conditional as a fraction
The products P(X|C)
Multiply by the priors
Compare and state the class

5Rule-based classification

A rule-based classifier uses a set of IF-THEN rules:

R1: IF age = youth AND student = yes THEN buys_computer = yes
(age = youth) ∧ (student = yes) ⇒ (buys_computer = yes)

Part	Name
IF part (left-hand side)	Rule antecedent or precondition: one or more attribute tests ANDed together
THEN part (right-hand side)	Rule consequent: the class prediction

If all the tests in the antecedent hold for a tuple, the rule is satisfied and covers the tuple.

Coverage and accuracy

coverage(R) = n_covers / |D| accuracy(R) = n_correct / n_covers

n_covers = number of tuples the rule covers
n_correct = number of those it classifies correctly
|D| = total number of tuples

R1 on the 14-tuple data

R1 covers 2 tuples (RIDs 9 and 11, both youth students) and gets both right.

coverage = 2/14 = 14.28%
accuracy = 2/2 = 100%

🧪 Try it — Rule evaluator

Build a rule antecedent (leave "any" to skip an attribute) and choose the consequent.

THEN buys_computer =

6Extracting rules from a decision tree

Decision trees are accurate and easy to understand, but large trees get hard to interpret. IF-THEN rules can be easier for humans, especially when the tree is very big.

How to extract

Create one rule per path from the root to a leaf.
The splitting criteria along the path are ANDed to form the antecedent.
The leaf's class is the consequent.

From the buys_computer tree (age → student / yes / credit_rating):

Rule	IF	THEN
R1	age = youth AND student = no	buys_computer = no
R2	age = youth AND student = yes	buys_computer = yes
R3	age = middle_aged	buys_computer = yes
R4	age = senior AND credit_rating = excellent	buys_computer = no
R5	age = senior AND credit_rating = fair	buys_computer = yes

Careful: the PDF swaps R4 and R5

The lesson PDF says senior + excellent → yes and senior + fair → no. The data says otherwise. The senior + excellent tuples (RIDs 6 and 14) are both no, and the senior + fair tuples (4, 5, 10) are all yes. Use the table above. You can check it in the rule evaluator.

Properties of rules extracted from a tree:

Mutually exclusive: no two rules cover the same tuple.
Exhaustive: there's a rule for every combination of attribute values.

7Weka: training and testing

Video	Key takeaways
2.1 Be a classifier!	Use Weka's UserClassifier to build a tree by hand, drawing regions on a 2-D plot. Compare your accuracy with J48's
2.2 Training and testing	Never evaluate on the training data. Use a separate test set, or percentage split (holdout, e.g. 66% train / 34% test). Training-set accuracy is optimistic
2.3 Repeated training and testing	Different random splits give different accuracies. Repeat with different random seeds and average, reporting the mean and standard deviation. This leads to cross-validation

8Quick revision sheet

Concept	Remember it as
Bayesian classifier	Statistical; predicts class membership probabilities
Naïve	Class-conditional independence
Bayes' theorem	P(H\|X) = P(X\|H)P(H) / P(X); posterior vs prior
Meningitis	0.5 × (1/50000) / (1/20) = 0.0002
Decision	Maximise P(X\|Cᵢ)·P(Cᵢ) (P(X) is constant)
Categorical P(xₖ\|Cᵢ)	Count in class / class size
Continuous	Gaussian g(x, μ, σ)
Example result	yes: 0.044 × 0.643 = 0.028 vs no: 0.019 × 0.357 = 0.007 → yes
Rule	IF antecedent (ANDed tests) THEN consequent (class)
Coverage / accuracy	n_covers/\|D\| · n_correct/n_covers; R1 = 14.28%, 100%
Tree → rules	One rule per root-to-leaf path; mutually exclusive and exhaustive
Belief networks	Graphical; allow dependencies between attributes

?Self-check quiz

11 questions on this week. Answer them all, then press Check my answers. Your best and latest scores are saved and shown on the subject page.

← PreviousClassification & Decision Tree Induction Next →Cluster Analysis & k-means