1 of 65

Bayesian Classification�

Dr. Debasis Samanta

Associate Professor

Department of Computer Science & Engineering

2 of 65

Today’s session includes…

  • Introduction to Classification

​

  • Classification Techniques
    • Supervised and unsupervised classifications

​

  • Formal statement of supervised classification technique

​

  • Naïve Bayesian Classifier
    • Principle of Bayesian classifier
    • Techniques
    • Addressing some issues with Naïve Bayesian Classifier

​

2

@DSamanta, IIT Kharagpur

3 of 65

3

@DSamanta, IIT Kharagpur

A Simple Quiz: Identify the objects

4 of 65

DebasisSamanta@IIT Kharagpur

4

Objects are characterized with features

5 of 65

DebasisSamanta@IIT Kharagpur

5

How we learn?

  • Each object is characterized with a set of feature values.

​

  • We learn an object by this feature set
    • We can differentiate one object from other
    • We can identify an object
    • We can group them
    • etc.

6 of 65

Learning Techniques

6

@DSamanta, IIT Kharagpur

7 of 65

DebasisSamanta@IIT Kharagpur

7

Types of learning

  • There are several learning techniques.

​

  • A taxonomy of well known learning techniques are shown in the following.

​

​

​

​

​

​

​

​

8 of 65

DebasisSamanta@IIT Kharagpur

8

Introduction to Machine Learning

Supervised learning

​

​

    • In this learning, every input pattern that is used to train a machine is associated with an output pattern.

​

      • This is called training set of data. Thus, in this form of learning, the input-output relationship of the training scenarios are available.

​

    • Here, the output of a machine is compared with the corresponding target value and the error is determined.

​

      • It is then feed back to the machine for updating the same. This results in an improvement.

​

    • This type of training is called learning with the help of teacher.

9 of 65

DebasisSamanta@IIT Kharagpur

9

Unsupervised learning

​

    • If the target output is not available, then the error in prediction can not be determined and in such a situation, the system learns of its own by discovering and adapting to structural features in the input patterns.

​

​

    • This type of training is called learning without a teacher.

10 of 65

DebasisSamanta@IIT Kharagpur

10

Reinforced learning

​

  • In this techniques, although a teacher is available, it does not tell the expected answer, but only tells if the computed output is correct or incorrect.
    • A reward is given for a correct answer computed and a penalty for a wrong answer.
    • This information helps the machine in its learning process.

​

​

11 of 65

DebasisSamanta@IIT Kharagpur

11

Gradient descent learning

 

12 of 65

DebasisSamanta@IIT Kharagpur

12

Stochastic learning

Stochastic learning

​

    • In this method, learning parameters are adjusted in a probabilistic fashion.
      • Simulated annealing is an example of such learning (proposed by Boltzmann and Cauch)

13 of 65

DebasisSamanta@IIT Kharagpur

13

Hebbian learning

 

14 of 65

DebasisSamanta@IIT Kharagpur

14

Competitive learning

Competitive learning:

​

    • In this learning method, those parameters which responds strongly to input have their values updated.

​

    • When an input pattern is presented, all parameters compete and the winning parameter undergoes weight adjustment.

​

    • This is why it is called a Winner-takes-all strategy.

​

15 of 65

Machine Learning Techniques

  • Supervised Learning 🡪 Classification
    • The set of possible classes is known in advance.

​

  • Unsupervised Learning 🡪 Clustering
    • Set of possible classes is not known. After classification we can try to assign a name to that class.
      • Unsupervised classification is called clustering.

​

DebasisSamanta@IIT Kharagpur

15

16 of 65

Introduction to Classification

  •  

16

@DSamanta, IIT Kharagpur

17 of 65

Examples of Classification in Data Analytics

  • Life Science: Predicting tumor cells as benign or malignant

​

  • Security: Classifying credit card transactions as legitimate or fraudulent

​

  • Prediction: Weather, voting, political dynamics, etc.

​

  • Entertainment: Categorizing news stories as finance, weather, entertainment, sports, etc.

​

  • Social media: Identifying the current trend and future growth

​

17

@DSamanta, IIT Kharagpur

18 of 65

Classification: Definition

  • Classification is a form of data analysis to extract models describing important data classes.

​

  • Essentially, it involves dividing up objects so that each is assigned to one of a number of mutually exhaustive and exclusive categories known as classes.

​

    • The term “mutually exhaustive and exclusive” simply means that each object must be assigned to precisely one class

​

      • That is, never to more than one and never to no class at all.

18

@DSamanta, IIT Kharagpur

19 of 65

Classification Techniques

  • Classification consists of assigning a class label to a set of unclassified cases.

​

  • Supervised Classification
    • The set of possible classes is known in advance.

​

  • Unsupervised Classification
    • Set of possible classes is not known. After classification we can try to assign a name to that class.
      • Unsupervised classification is called clustering.

​

19

@DSamanta, IIT Kharagpur

20 of 65

Supervised Classification

20

@DSamanta, IIT Kharagpur

21 of 65

Supervised Classification Technique

  • Given a collection of records (training set )

​

    • Each record contains a set of attributes, one of the attributes is the class.

​

  • Find a model for class attribute as a function of the values of other attributes.

​

  • Goal: Previously unseen records should be assigned a class as accurately as possible.

​

      • Satisfy the property of “mutually exclusive and exhaustive”

​

21

@DSamanta, IIT Kharagpur

22 of 65

Illustrating Classification Tasks

22

@DSamanta, IIT Kharagpur

23 of 65

Classification Problem

  • More precisely, a classification problem can be stated as below:

​

​

​

​

​

​

​

23

@DSamanta, IIT Kharagpur

 

Definition: Classification Problem

24 of 65

Classification Techniques

  •  

24

@DSamanta, IIT Kharagpur

25 of 65

Classification Techniques

  •  

25

@DSamanta, IIT Kharagpur

26 of 65

Bayesian Classifier

26

@DSamanta, IIT Kharagpur

27 of 65

Bayesian Classifier

  • Principle
    • If it walks like a duck, quacks like a duck, then it is probably a duck

27

@DSamanta, IIT Kharagpur

28 of 65

Bayesian Classifier

  • A statistical classifier

​

    • Performs probabilistic prediction, i.e., predicts class membership probabilities

​

  • Foundation

​

    • Based on Bayes’ Theorem.

​

  • Assumptions
    1. The classes are mutually exclusive and exhaustive.
    2. The attributes are independent given the class.

​

​

  • Called “Naïve” classifier because of these assumptions
    • Empirically proven to be useful.
    • Scales very well.

​

​

28

@DSamanta, IIT Kharagpur

29 of 65

Example: Bayesian Classification

  • Example: Air Traffic Data

​

    • Let us consider a set observation recorded in a database

​

      • Regarding the arrival of airplanes in the routes from any airport to New Delhi under certain conditions.

29

@DSamanta, IIT Kharagpur

30 of 65

Air-Traffic Data

30

@DSamanta, IIT Kharagpur

Days

Season

Fog

Rain

Class

Weekday

Spring

None

None

On Time

Weekday

Winter

None

Slight

On Time

Weekday

Winter

None

None

On Time

Holiday

Winter

High

Slight

Late

Saturday

Summer

Normal

None

On Time

Weekday

Autumn

Normal

None

Very Late

Holiday

Summer

High

Slight

On Time

Sunday

Summer

Normal

None

On Time

Weekday

Winter

High

Heavy

Very Late

Weekday

Summer

None

Slight

On Time

Cond. to next slide…

31 of 65

Air-Traffic Data

31

@DSamanta, IIT Kharagpur

Days

Season

Fog

Rain

Class

Saturday

Spring

High

Heavy

Cancelled

Weekday

Summer

High

Slight

On Time

Weekday

Winter

Normal

None

Late

Weekday

Summer

High

None

On Time

Weekday

Winter

Normal

Heavy

Very Late

Saturday

Autumn

High

Slight

On Time

Weekday

Autumn

None

Heavy

On Time

Holiday

Spring

Normal

Slight

On Time

Weekday

Spring

Normal

None

On Time

Weekday

Spring

Normal

Heavy

On Time

Cond. from previous slide…

32 of 65

Air-Traffic Data

  • In this database, there are four attributes

A = [ Day, Season, Fog, Rain]

with 20 tuples.

  • The categories of classes are:

C= [On Time, Late, Very Late, Cancelled]

​

  • Given this is the knowledge of data and classes, we are to find most likely classification for any other unseen instance, for example:

​

​

​

  • Classification technique eventually to map this tuple into an accurate class.

​

​

​

32

@DSamanta, IIT Kharagpur

Week Day

Winter

High

None

???

33 of 65

Bayesian Classifier

  • In many applications, the relationship between the attributes set and the class variable is non-deterministic.

​

    • In other words, a test cannot be classified to a class label with certainty.

​

    • In such a situation, the classification can be achieved probabilistically.

​

  • The Bayesian classifier is an approach for modelling probabilistic relationships between the attribute set and the class variable.

​

  • More precisely, Bayesian classifier use Bayes’ Theorem of Probability for classification.

​

  • Before going to discuss the Bayesian classifier, we should have a quick look at the Theory of Probability and then Bayes’ Theorem.

33

@DSamanta, IIT Kharagpur

34 of 65

Bayes’ Theorem of Probability

34

@DSamanta, IIT Kharagpur

35 of 65

Simple Probability

35

@DSamanta, IIT Kharagpur

 

Definition 8.2: Simple Probability

36 of 65

Simple Probability

  • Suppose, A and B are any two events and P(A), P(B) denote the probabilities that the events A and B will occur, respectively.

​

  • Mutually Exclusive Events:
    • Two events are mutually exclusive, if the occurrence of one precludes the occurrence of the other.

Example: Tossing a coin (two events)

Tossing a ludo cube (Six events)

​

  • Can you give an example, so that two events are not mutually exclusive?

Hint: Tossing two identical coins, Weather (sunny, foggy, warm)

​

36

@DSamanta, IIT Kharagpur

37 of 65

Simple Probability

  • Independent events: Two events are independent if occurrences of one does not alter the occurrence of other.

​

Example: Tossing both coin and ludo cube together.

(How many events are here?)

​

  • Can you give an example, where an event is dependent on one or more other events(s)?

Hint: Receiving a message (A) through a communication channel (B)

over a computer (C), rain and dating.

37

@DSamanta, IIT Kharagpur

38 of 65

Joint Probability

38

@DSamanta, IIT Kharagpur

 

Definition 8.3: Joint Probability

39 of 65

Conditional Probability

39

@DSamanta, IIT Kharagpur

 

Definition 8.2: Conditional Probability

40 of 65

Conditional Probability

40

@DSamanta, IIT Kharagpur

 

Corollary 8.1: Conditional Probability

41 of 65

Conditional Probability

  •  

41

@DSamanta, IIT Kharagpur

42 of 65

Conditional Probability

  •  

42

@DSamanta, IIT Kharagpur

43 of 65

43

@DSamanta, IIT Kharagpur

Total Probability

CS 40003: Data Analytics

43

 

Definition 8.3: Total Probability

44 of 65

  •  

44

@DSamanta, IIT Kharagpur

Total Probability: An Example

45 of 65

  •  

45

@DSamanta, IIT Kharagpur

Reverse Probability

46 of 65

Bayes’ Theorem

46

@DSamanta, IIT Kharagpur

 

Theorem: Bayes’ Theorem

47 of 65

Prior and Posterior Probabilities

  •  

47

@DSamanta, IIT Kharagpur

X

Y

​

A

​

A

​

B

​

A

​

B

​

A

​

B

​

B

​

B

​

A

48 of 65

Naïve Bayesian Classifier

  •  

48

@DSamanta, IIT Kharagpur

INPUT (X)

CLASS(Y)

… … …

​

… … …

…

​

​

… … …

…

49 of 65

Naïve Bayesian Classifier

  •  

49

@DSamanta, IIT Kharagpur

50 of 65

Naïve Bayesian Classifier

  •  

50

@DSamanta, IIT Kharagpur

51 of 65

Naïve Bayesian Classifier

  • Example: With reference to the Air Traffic Dataset mentioned earlier, let us tabulate all the posterior and prior probabilities as shown below.

​

51

@DSamanta, IIT Kharagpur

​

Class

Attribute

On Time

Late

Very Late

Cancelled

Day

Weekday

9/14 = 0.64

½ = 0.5

3/3 = 1

0/1 = 0

Saturday

2/14 = 0.14

½ = 0.5

0/3 = 0

1/1 = 1

Sunday

1/14 = 0.07

0/2 = 0

0/3 = 0

0/1 = 0

Holiday

2/14 = 0.14

0/2 = 0

0/3 = 0

0/1 = 0

Season

Spring

4/14 = 0.29

0/2 = 0

0/3 = 0

0/1 = 0

Summer

6/14 = 0.43

0/2 = 0

0/3 = 0

0/1 = 0

Autumn

2/14 = 0.14

0/2 = 0

1/3= 0.33

0/1 = 0

Winter

2/14 = 0.14

2/2 = 1

2/3 = 0.67

0/1 = 0

52 of 65

Naïve Bayesian Classifier

52

@DSamanta, IIT Kharagpur

​

Class

Attribute

On Time

Late

Very Late

Cancelled

Fog

None

5/14 = 0.36

0/2 = 0

0/3 = 0

0/1 = 0

High

4/14 = 0.29

1/2 = 0.5

1/3 = 0.33

1/1 = 1

Normal

5/14 = 0.36

1/2 = 0.5

2/3 = 0.67

0/1 = 0

Rain

None

5/14 = 0.36

1/2 = 0.5

1/3 = 0.33

0/1 = 0

Slight

8/14 = 0.57

0/2 = 0

0/3 = 0

0/1 = 0

Heavy

1/14 = 0.07

1/2 = 0.5

2/3 = 0.67

1/1 = 1

Prior Probability

14/20 = 0.70

2/20 = 0.10

3/20 = 0.15

1/20 = 0.05

53 of 65

Naïve Bayesian Classifier

Instance:

​

​

​

Case1: Class = On Time : 0.70 × 0.64 × 0.14 × 0.29 × 0.07 = 0.0013

​

Case2: Class = Late : 0.10 × 0.50 × 1.0 × 0.50 × 0.50 = 0.0125

​

Case3: Class = Very Late : 0.15 × 1.0 × 0.67 × 0.33 × 0.67 = 0.0222

​

Case4: Class = Cancelled : 0.05 × 0.0 × 0.0 × 1.0 × 1.0 = 0.0000

​

Case3 is the strongest; Hence correct classification is Very Late

53

@DSamanta, IIT Kharagpur

Week Day

Winter

High

Heavy

???

54 of 65

Naïve Bayesian Classifier

  •  

54

@DSamanta, IIT Kharagpur

 

Algorithm: Naïve Bayesian Classification

55 of 65

Naïve Bayesian Classifier

Pros and Cons

  • The Naïve Bayes’ approach is a very popular one, which often works well.

​

  • However, it has a number of potential problems

​

    • It relies on all attributes being categorical.

​

    • If the data is less, then it estimates poorly.

55

@DSamanta, IIT Kharagpur

56 of 65

Naïve Bayesian Classifier

  •  

56

@DSamanta, IIT Kharagpur

57 of 65

Naïve Bayesian Classifier

  •  

57

@DSamanta, IIT Kharagpur

58 of 65

Naïve Bayesian Classifier

M-estimate of Conditional Probability

​

  • The M-estimation is to deal with the potential problem of Naïve Bayesian Classifier when training data size is too poor.

​

    • If the posterior probability for one of the attribute is zero, then the overall class-conditional probability for the class vanishes.

​

    • In other words, if training data do not cover many of the attribute values, then we may not be able to classify some of the test records.

​

  • This problem can be addressed by using the M-estimate approach.

58

@DSamanta, IIT Kharagpur

59 of 65

M-estimate Approach

  •  

59

@DSamanta, IIT Kharagpur

60 of 65

Case Study-1

Example

60

@DSamanta, IIT Kharagpur

Class:

C1:buys_computer = ‘yes’

C2:buys_computer = ‘no’

​

Data instance

X = (age <=30,

Income = medium,

Student = yes

Credit_rating = fair)

61 of 65

Solution to Case Study-1

61

@DSamanta, IIT Kharagpur

  • P(Ci): P(buys_computer = “yes”) = 9/14 = 0.643

P(buys_computer = “no”) = 5/14= 0.357

​

  • Compute P(X|Ci) for each class

P(age = “<=30” | buys_computer = “yes”) = 2/9 = 0.222

P(age = “<= 30” | buys_computer = “no”) = 3/5 = 0.6

P(income = “medium” | buys_computer = “yes”) = 4/9 = 0.444

P(income = “medium” | buys_computer = “no”) = 2/5 = 0.4

P(student = “yes” | buys_computer = “yes) = 6/9 = 0.667

P(student = “yes” | buys_computer = “no”) = 1/5 = 0.2

P(credit_rating = “fair” | buys_computer = “yes”) = 6/9 = 0.667

P(credit_rating = “fair” | buys_computer = “no”) = 2/5 = 0.4

​

  • X = (age <= 30 , income = medium, student = yes, credit_rating = fair)

​

P(X|Ci) : P(X|buys_computer = “yes”) = 0.222 × 0.444 × 0.667 × 0.667 = 0.044

P(X|buys_computer = “no”) = 0.6 × 0.4 × 0.2 × 0.4 = 0.019

​

P(X|Ci)*P(Ci) : P(X|buys_computer = “yes”) * P(buys_computer = “yes”) = 0.028

P(X|buys_computer = “no”) * P(buys_computer = “no”) = 0.007

​

Therefore, X belongs to class (“buys_computer = yes”)

62 of 65

Case Study-2

Example

62

@DSamanta, IIT Kharagpur

​

WEATHER

TEMPERATURE

HUMIDITY

WINDY

PLAY GOLF

1

Rainy

Hot

High

False

No

2

Rainy

Hot

High

True

No

3

Overcast

Hot

High

False

Yes

4

Sunny

Mild

High

False

Yes

5

Sunny

Cool

Normal

False

Yes

6

Sunny

Cool

Normal

True

No

7

Overcast

Cool

Normal

True

Yes

8

Rainy

Mild

High

False

No

9

Rainy

Cool

Normal

False

Yes

10

Sunny

Mild

Normal

False

Yes

11

Rainy

Mild

Normal

True

Yes

12

Overcast

Mild

High

True

Yes

13

Overcast

Hot

Normal

False

Yes

14

Sunny

Mild

High

True

No

63 of 65

Case Study-2

63

@DSamanta, IIT Kharagpur

WEATHER

TEMPERATURE

HUMIDITY

WINDY

Rainy

Hot

High

False

64 of 65

Reference

64

@DSamanta, IIT Kharagpur

  • The detail material related to this lecture can be found in

​

Data Mining: Concepts and Techniques, (3rd Edn.), Jiawei Han, Micheline Kamber, Morgan Kaufmann, 2015.

​

Introduction to Data Mining, Pang-Ning Tan, Michael Steinbach, and Vipin Kumar, Addison-Wesley, 2014

65 of 65

Any question?

​

​

65

@DSamanta, IIT Kharagpur