Algorithms for �Classification:

The Basic Methods

Outline

​

• Naïve Bayes

​

2

Classification

• Task: Given a set of pre-classified examples, build a model or classifier to classify new cases.
• Supervised learning: classes are known for the examples used to build the classifier.
• A classifier can be a set of rules, a decision tree, a neural network, etc.
• Typical applications: credit approval, direct marketing, fraud detection, medical diagnosis, …

3

Simplicity first

• Simple algorithms often work very well!
• There are many kinds of simple structure, eg:
• Majority class classifier
• One attribute does all the work
• All attributes contribute equally & independently
• A weighted linear combination might do
• Instance-based: use a few prototypes
• Use simple logical rules
• Success of method depends on the domain

4

Bayesian (Statistical) modeling

• “Opposite” of 1R: use all the attributes
• Two assumptions: Attributes are
• equally important
• statistically independent (given the class value)
• I.e., knowing the value of one attribute says nothing about the value of another�(if the class is known)
• Independence assumption is almost never correct!
• But … this scheme works well in practice

5

Probabilities for weather data

6

Probabilities for weather data

• A new day:

7

Bayes’s rule

• Probability of event H given evidence E :���
• A priori probability of H :
• Probability of event before evidence is seen
• A posteriori probability of H :
• Probability of event after evidence is seen

8

Thomas Bayes

Born: 1702 in London, England�Died: 1761 in Tunbridge Wells, Kent, England

​

from Bayes “Essay towards solving a problem in the doctrine of chances” (1763)

Naïve Bayes for classification

• Classification learning: what’s the probability of the class given an instance?
• Evidence E = instance
• Event H = class value for instance
• Naïve assumption: evidence splits into parts (i.e. attributes) that are independent

9

Weather data example

10

Evidence E

Probability of

class “yes”

The “zero-frequency problem”

• What if an attribute value doesn’t occur with every class value?�(e.g. “Humidity = high” for class “yes”)
• Probability will be zero!
• A posteriori probability will also be zero!�(No matter how likely the other values are!)

​

• Remedy: add 1 to the count for every attribute value-class combination (Laplace estimator)

​

• Result: probabilities will never be zero!�(also: stabilizes probability estimates)

​

11

*Modified probability estimates

• In some cases adding a constant different from 1 might be more appropriate
• Example: attribute outlook for class yes

​

​

​

​

• Weights don’t need to be equal �(but they must sum to 1)

12

Sunny

Overcast

Rainy

Missing values

• Training: instance is not included in frequency count for attribute value-class combination
• Classification: attribute will be omitted from calculation
• Example:

​

13

Numeric attributes

• Usual assumption: attributes have a normal or Gaussian probability distribution (given the class)
• The probability density function for the normal distribution is defined by two parameters:
• Sample mean μ

​

​

• Standard deviation σ

​

​

• Then the density function f(x) is

14

Karl Gauss, 1777-1855

great German mathematician

Statistics for�weather data

• Example density value:

15

Classifying a new day

• A new day:

​

​

​

​

​

​

• Missing values during training are not included in calculation of mean and standard deviation

16

*Probability densities

• Relationship between probability and density:

​

​

• But: this doesn’t change calculation of a posteriori probabilities because ε cancels out
• Exact relationship:

​

17

Naïve Bayes: discussion

• Naïve Bayes works surprisingly well (even if independence assumption is clearly violated)
• Why? Because classification doesn’t require accurate probability estimates as long as maximum probability is assigned to correct class
• However: adding too many redundant attributes will cause problems (e.g. identical attributes)
• Note also: many numeric attributes are not normally distributed (→ kernel density estimators)

18

Naïve Bayes Extensions

• Improvements:
• select best attributes (e.g. with greedy search)
• often works as well or better with just a fraction of all attributes

​

• Bayesian Networks

19

Summary

​

• Naïve Bayes – use all attributes and Bayes rules to estimate probability of the class given an instance.

​

• Simple methods frequently work well, but …
• Complex methods can be better (as we will see)

​

20