Data Mining

EL
Week 3:Bayes Classification

PT
Pabitra Mitra

N
Computer Science and Engineering, IIT Kharagpur

1
 Data Mining

EL
Bayes Classification

PT
Pabitra Mitra

N
Computer Science and Engineering, IIT Kharagpur

2
 A Simple Species Classification Problem
• Measure the length of a fish, and decide its class
– Hilsa or Tuna

EL
PT
N
 Collect Statistics …

EL
PT
N
Population for Class Hilsa

Population for Class Tuna

Count/probability Distribution of “Fish Length”
Class Conditional Distributions
HILSA P ( L = 1.75 ft | HILSA )
P ( L = 4.25 ft | TUNA )

EL
1ft length in feet

PT
Count/probability

N
TUNA
Histograms

4ft length in feet

 Decision Rule
• If length L ≤ B
– HILSA
• ELSE

EL
– TUNA

PT
• What should be the value of B (“boundary”
length) ?
N
– Based on population statistics
 Error of Decision Rule
P( L | TUNA)
P( L | HILSA)

EL
L

PT
B

N
Errors: Type 1 + Type 2,
Type 1: Actually Tuna, Classified as Hilsa (area under pink curve to the left of a B)
Type 2: Actually Hilsa, Classified as Tuna (area under blue curve to the right of a B)
 Optimal Decision Rule
P( L | TUNA)
P( L | HILSA)

EL
L

PT
B*

N
B*: Optimal Value of B, (Optimal Decision Boundary)
Minimum Possible Error If Type 1 and Type 2 errors have different costs :
P ( B* | HILSA ) = P ( B* | TUNA ) optimal boundary shifts
 Species Identification Problem
• Measure lengths of a (sizeable) population of Hilsa and
Tuna fishes
• Estimate Class Conditional Distributions for Hilsa and Tuna

EL
classes respectively

PT
• Find Optimal Decision Boundary B* from the distributions
• Apply Decision Rule to classify a newly caught (and

N
measured) fish as either Hilsa or Tuna
– (with minimum error probability)
 Location/Time of Experiment
• Calcutta in Monsoon
– More Hilsa few Tuna

EL
• California in Winter

PT
– More Tuna less Hilsa

N
• Even a 2ft fish is likely to be Hilsa in Calcutta
• a 1.5ft fish may be Tuna in California
 Apriori Probability
• Without measuring length what can we guess about the class of a
fish
– Depends on location/time of experiment
• Calcutta : Hilsa, California: Tuna

EL
• Apriori probability: P(HILSA), P(TUNA)
– Property of the frequency of classes during experiment

PT
• Not a property of length of the fish
– Calcutta: P(Hilsa) = 0.90, P(Tuna) = 0.10

N
– California: P(Tuna) = 0.95, P(Hilsa) = 0.05
– London: P(Tuna) = 0.50, P(Hilsa) = 0.50
• Also a determining factor in class decision along with class
conditional probability
 Classification Decision
• We consider the product of Apriori and Class conditional
probability factors
• Posteriori probability (Bayes rule)
– P(HILSA | L = 2ft) = P(HILSA) x P(L=2ft | HILSA) / P(L=2ft)

EL
– Posteriori ≈ Apriori x Class conditional
– denominator is constant for all classes

PT
• Apriori: Without any measurement - based on just location/time – what can we guess about
class membership (estimated frm size of class populations)

N
• Class conditional: Given the fish belongs to a particular class what is the probability that its
length is L=2ft (estimated from population)
• Posteriori: Given the measurement that the length of the fish is L=2ft what is the probability
that the fish belongs to a particular class (obtained using Bayes rule from above two
probabilities).
– Useful in decision making using evidences/measurements.
Bayes Classification Rule (Bayes Classifier)
Posteriori Distributions
P( TUNA | L)
P( HILSA | L)

EL
L

PT
B*

N
B*: Optimal Value of B, (Bayes Decision Boundary)
P ( HILSA| L= B* ) = P ( TUNA | L = B*)

Minimum error probability: Bayes error

 MAP Representation of Bayes Classifier
Posteriori Distributions
P( TUNA | L)
P( HILSA | L)

EL
L

PT
Hilsa has higher posteriori probability than Tuna for this length

N
Instead of finding decision boundary B*, state classification rule as:
Classify an object in to the class for which it has the highest posteriori prob.
(MAP: Maximum Aposteriori Probability)
 MAP Multiclass Classifier
Posteriori Distributions
P( TUNA | L) P( SHARK | L)
P( HILSA | L)

EL
L

PT
Hilsa has highest posteriori probability among all classes for this length

N
Classify an object in to the class for which it has the highest posteriori prob.
(MAP: Maximum Aposteriori Probability)
 Multivariate Bayes Classifier
Decision Boundary
Weight

TUNA

EL
HILSA

PT
N
Length
•Feature or Attribute Space

•Class Seperability
 Decision Boundary: Normal Distribution
• Two spherical classes having different means, but same variance (diagonal covariance matrix with same variances)

Weight

EL
TUNA

PT
HILSA

N Length
Decision Boundary: Perpendicular bisector of the mean vectors
 Distances
• Two vectors: Euclidean, Minkowski etc
• A vector and a distribution: Mahalanobis, Bhattacharya

Which distribution is closer to x?

EL
PT
x
σ2 σ1 µ

N
( x − µ )2
dM = , d M = ( X − µ )Σ −1 ( X − µ )T
σ
• Between two distributions: Kullback-Liebler Divergence
 Decision Boundary: Normal Distribution
• Two spherical classes having different means and variances (diagonal covariance matrix with different variances)

Weight

EL
TUNA

PT
HILSA

N Length

Boundary: Locus of equi-Mahalanobis distance points from the class distributions.

(still a straight line)
 Decision Boundary: Normal Distribution
• Two elliptical classes having different means and variances (general covariance matrix with different variances)

Weight

EL
TUNA

PT
HILSA

N
Class Boundary: Parabolic Length
 Multivariate Bayesian Classifiers
• Approach:
– compute the posterior probability P(C | A1, A2, …, An) for all
values of C using the Bayes theorem
P ( A A  A | C ) P (C )
P (C | A A  A ) =

EL
1 2 n

P( A A  A )
1 2 n

1 2 n

– Choose value of C that maximizes

PT
P(C | A1, A2, …, An)

N
– Equivalent to choosing value of C that maximizes
P(A1, A2, …, An|C) P(C)
• How to estimate P(A1, A2, …, An | C )?
 Example of Bayes Classifier
Name Give Birth Can Fly Live in Water Have Legs Class
human
python
yes
no
no
no
no
no
yes
no
mammals
non-mammals
A: attributes
salmon no no yes no non-mammals
whale
frog
yes
no
no
no
yes
sometimes
no
yes
mammals
non-mammals
M: mammals
komodo no no no yes non-mammals
bat yes yes no yes mammals N: non-mammals

EL
pigeon no yes no yes non-mammals
cat yes no no yes mammals
leopard shark yes no yes no non-mammals
turtle no no sometimes yes non-mammals

PT
penguin no no sometimes yes non-mammals
porcupine yes no no yes mammals
eel no no yes no non-mammals
salamander no no sometimes yes non-mammals

N
gila monster no no no yes non-mammals
platypus no no no yes mammals

P(A|M)P(M) > P(A|N)P(N)

owl no yes no yes non-mammals
dolphin yes no yes no mammals
eagle no yes no yes non-mammals

=> Mammals
Give Birth Can Fly Live in Water Have Legs Class
yes no yes no ?
 Estimating Multivariate Class Distributions
• Sample size requirement
– In a small sample: difficult to find a Hilsa fish whose length is
1.5ft and weight is 2 kilos, as compared to that of just finding a
fish whose length is 1.5ft

EL
– P(L=1.5, W=2 | Hilsa), P(L=1.5 | Hilsa)
– Curse of dimensionality

PT
• Independence Assumption
– Assume length and weight are independent

N
– P(L=1.5, W=2 | Hilsa) = P(L=1.5 | Hilsa) x P(W=2| Hilsa)
– Joint distribution = product of marginal distributions
– Marginals are easier to estimate from a small sample
 Naïve Bayes Classifier
• Assume independence among attributes Ai when class is
given:
– P(A1, A2, …, An |C) = P(A1| Cj) P(A2| Cj)… P(An| Cj)

EL
PT
– Can estimate P(Ai| Cj) for all Ai and Cj.

N
– New point is classified to Cj if P(Cj) Π P(Ai| Cj) is maximal.
 Example of Naïve Bayes Classifier
Name Give Birth Can Fly Live in Water Have Legs Class
human
python
yes
no
no
no
no
no
yes
no
mammals
non-mammals
A: attributes
salmon no no yes no non-mammals
whale
frog
yes
no
no
no
yes
sometimes
no
yes
mammals
non-mammals
M: mammals
komodo no no no yes non-mammals
6 6 2 2
bat yes yes no yes mammals P ( A N:
| Mnon-mammals
) = × × × = 0.06

EL
pigeon no yes no yes non-mammals
cat yes no no yes mammals
7 7 7 7
leopard shark yes no yes no non-mammals 1 10 3 4
turtle no no sometimes yes non-mammals P( A | N ) = × × × = 0.0042

PT
penguin no no sometimes yes non-mammals 13 13 13 13
porcupine yes no no yes mammals
7
P ( A | M ) P ( M ) = 0.06 × = 0.021
eel no no yes no non-mammals
salamander no no sometimes yes non-mammals
20

N
gila monster no no no yes non-mammals
platypus no no no yes mammals
13
owl
dolphin
no
yes
yes
no
no
yes
yes
no
non-mammals
mammals
P ( A | N ) P ( N ) = 0.004 × = 0.0027
eagle no yes no yes non-mammals 20
P(A|M)P(M) > P(A|N)P(N)
Give Birth Can Fly Live in Water Have Legs Class
yes no yes no ? => Mammals
 Naïve Bayes Classifier: Smoothing
• If one of the conditional probability is zero, then the entire
expression becomes zero
• Probability estimation:

EL
N ic
Original : P ( Ai | C ) =

PT
Nc
c: number of classes
N +1
Laplace : P ( Ai | C ) = ic

N
Nc + c p: prior probability
N ic + mp
m - estimate : P ( Ai | C ) = m: parameter
Nc + m
 Conditional Independence
• Event A and B are conditionally independent given C
in case

EL
Pr(AB|C)=Pr(A|C)Pr(B|C)

PT
• A set of events {Ai} is conditionally independent given

N
C in case Pr( i Ai | C ) = ∏ i Pr( Ai | C )
 CI: Conditional Independence
• Variables are rarely independent but we can still leverage local structural
properties like CI.
• X ⊥ Y | Z if once Z is observed, knowing the value of Y does not change our
belief about X

EL
• The following should hold for all x,y,z

PT
• P(X=x | Z=z, Y=y) = P(X=x | Z=z)
• P(Y=y | Z=z, X=x) = P(Y=y | Z=z)

N
• P(X=x, Y=y | Z=z) = P(X=x| Z=z) P(Y=y| Z=z)
 Example
Let the two events be the probabilities of persons A and B getting home in
time for dinner, and the third event is the fact that a snow storm hit the city.

EL
While both A and B have a lower probability of getting home in time for dinner,
the lower probabilities will still be independent of each other. That is, the

PT
knowledge that A is late does not tell you whether B will be late. (They may be
living in different neighborhoods, traveling different distances, and using
different modes of transportation.) However, if you have information that they

N
live in the same neighborhood, use the same transportation, and work at the
same place, then the two events are NOT conditionally independent.
 Exercise: Conditional independence
smart ¬smart
p(smart ∧
study ∧ prep) study ¬study study ¬study

EL
prepared .432 .16 .084 .008

¬prepared

PT
.048 .16 .036 .072

• Queries:

N
– Is smart conditionally independent of prepared, given study?
– Is study conditionally independent of prepared, given smart?

30
 Ancestor
Representing Conditional Independence with DAG

• We now make this independence Parent

assumption more precise for directed
Y1 Y2
acyclic graphs (DAGs)

EL
• Each random variable X, is independent X

PT
of its non-descendents, given its
parents Pa(X)

N
• Formally, I (X, NonDesc(X) | Pa(X))

Non-descendent

Descendent
 Summary
Advantages:
• Robust to isolated noise points
• Handle missing values by ignoring the instance during probability estimate
calculations

EL
• Robust to irrelevant attributes

PT
Drawback:

N
• Independence assumption may not hold for some attributes
– Length and weight of a fish are not independent
– Conditional Independence
 EL
End of Bayes Classifier

PT
N