Chapter 4 - Rules can be simplified (similar to pruning of the

Classification – Alternative Techniques tree)

Rule-Based Classifier Direct Methods of Rule Generation

- Classify records by using a collection of “if…then…” - Extract rules directly from data
rules - Sequential Covering (e.g. try to cover class +)
- Rule: ( Condition ) → y
- Condition is a conjunction of attributes called
LHS, antecedent or condition
- y is the class label called RHS or consequent
- Examples of classification rules for an animal
dataset:
- ( Blood Type=Warm ) ∧ ( Lay Eggs=Yes ) → Birds
-
( Taxable Income< 50 K ) ∧ ( Refund =Yes ) → Evade=No
Advantages of Rule-Based Classifiers
Using a Rule-Based Classifier
- As expressive as decision trees
A rule R covers an instance x if the attributes of the
- Easy to interpret
instance satisfy the condition of the rule. Such a rule
- Easy to generate
can be used for classification
- Can classify new instances rapidity
- Performance comparable to decision trees

Nearest Neighbor Classifier

- Basic Idea:
If it walks like a duck, quacks like a duck, then it’s
probably a duck

Ordered Rule Set vs Voting

- Rules are rank ordered according to their priority
- an ordered rule set is known as a decision list
- when a test record is presented to the classifier
- it is assigned to the class label of the highest
ranked rule it has triggered
- if none of the rules fired, it is assigned to the
default class Requires three things:
- Alternative: (weighted) voting by all matching rules - The set of stored records
- Distance Metric to compute the distance between
Rules from Decision Trees records
- The value of k, the number of nearest neighbors to
retrieve

To classify an unknown record:

- Compute the distance to other training records
- Identify k-nearest neighbors
- Use class labels of nearest neighbors to determine
the class label of an unknown record (e.g., by taking
majority vote)

- Rules are created by reading the decisions in tree

branches from the root to a final node
- Rule set contains as much information as the tree
 Bayes’ Rule
- The product rule gives us two ways to factor a joint
distribution

- Therefore,

- Can get diagnostic probability 𝑃 (cavity |

- Why is this useful?
- K-nearest neighbors of a record x are data points

toothache) from causal probability 𝑃(toothache

with the k smallest distances to x
- k is a hyperparameter
- odd numbers are preferable for k | cavity)
- We can update our beliefs based on evidence.
Distance Computation for Nearest-Neighbor - Important tool for probabilistic inference
Classification
- Compute distance between two points: Example:
- Typically uses Euclidean distance A doctor knows that meningitis causes a stiff neck 50%
of the time
d ( p , q )= √∑ ( p −q )
i
i i
2
P ( s|m )=0.5
Note: This means that the data needs to be The probability of any patient having meningitis is
scaled! 1
P ( m )= =0.00002
- Determine the class from nearest neighbor list. 5 0,000
a. Take the majority vote of class labels among the The probability of any patient having stiff neck is
k-nearest neighbors. 1
b. Weigh the vote according to distance (e.g., weight P ( s )= =0 . 0 5
20
factor w=1/d 2 )
has meningitis? 𝑃
If a patient has stiff neck, what’s the probability he/she

Choosing k P ( s|m ) P ( m ) 0.00002

- If k is too small, sensitive to noise points P ( m|s )= =.5× =0.0002
- If k is too large, neighborhood may include points P (s ) 0.05
from other classes Increases the probability by x10!

Advantage
- Can create arbitrary non-linear decision boundaries

Disadvantages
- It does not build models explicitly (unlike eager
learners such as decision trees).
- Needs to store all the training data.
- Classifying unknown records are relatively
expensive (find the k-nearest neighbors). Space
partitioning data structures like k-d trees can help.

Naïve Bayes Classifier