{"id":648,"date":"2019-01-08T11:13:13","date_gmt":"2019-01-08T11:13:13","guid":{"rendered":"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=648"},"modified":"2019-01-08T11:56:48","modified_gmt":"2019-01-08T11:56:48","slug":"naive-bayes-classification","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/chapter\/naive-bayes-classification\/","title":{"rendered":"Na\u00efve Bayes Classification"},"content":{"raw":"
\r\n\r\n \r\n\r\nLearning Objectives:<\/strong>\r\n\r\n \r\n\r\nThe learning objectives of this module are as follows:\r\n\r\n \r\n\r\n\u2022 To understand Probabilistic Classification\r\n\r\n \r\n\r\n\u2022 To explain Na\u00efve Bayes Classifier\r\n\r\n \r\n\r\n\u2022 To understand some applications of Na\u00efve Bayes Classifier\r\n\r\n \r\n\r\n \r\n\r\n30.1 Classification problem<\/strong>\r\n\r\n \r\n

Let us again look at the classification problem, a supervised learning problem. The training data consists of examples of the form (d,h(d)) where d is the data object to classify (inputs) and h(d) is the correct class information for d. The goal of classification is to find the class h(dnew<\/sub>) of dnew<\/sub>, an hitherto unseen data object (Figure 30.1).<\/p>\r\n\"\"\r\n

Figure 30.1 Supervised Learning<\/strong><\/p>\r\n\r\n<\/div>\r\n\u00a0<\/strong>\r\n\r\n30.1.1 Methods to Create Classifiers<\/strong>\r\n

\r\n\r\n \r\n\r\nThere are three methods to establish a classifier as given below:\r\n\r\n \r\n\r\na)\u00a0Model a classification rule directly - <\/strong>Examples: k-NN, decision trees, perceptron, SVM\r\n\r\n \r\n\r\nb)\u00a0Model the probability of class memberships given input data - <\/strong>Example: perceptron with the cross-entropy cost\r\n\r\n \r\n

c)\u00a0Make a probabilistic model of data within each class - <\/strong>Examples: naive Bayes<\/strong>, model based classifiers Of these methods a) and b) are examples of discriminative classification and c<\/em>) is an example of generative classification. Moreover b<\/em>) and c<\/em>) are both examples of probabilistic classification.<\/p>\r\n \r\n\r\n30.2 <\/strong>Probabilistic Classification<\/strong>\r\n\r\n \r\n

Generally, in classification the goal is to predict the value of a class c given the value of a input feature vector x. From a probabilistic perspective, the goal is to find the conditional distribution p(c|x).There are two types of probabilistic models of classification, the discriminative model and the generative model.<\/p>\r\n \r\n\r\n30.2.1 Discriminative model<\/strong>\r\n\r\n \r\n

The most common approach to probabilistic classification is to represent the conditional distribution using a parametric model, and then to determine the parameters using a training set consisting of pairs <xn, cn> of input vectors along with their corresponding target output vectors. In other words discriminative classifiers model the posterior p(c|x) directly which can then be used to make predictions of c for new values of x (Figure 30.2). Here for example the classes can be C1=benign mole or C2 = cancer which can be modelled given the respective data points. This is known as a discriminative approach, since the conditional distribution discriminates directly between the different values of c.<\/p>\r\n \r\n\r\n\"\"\r\n\r\n \r\n

Figure 30.2 Discriminative Model<\/strong><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\n30.2.2 Generative model<\/strong>\r\n\r\n \r\n

The generative model is a model for randomly generating observable data values, typically given some hidden parameters. It specifies a joint probability distribution over observation and label sequences. Generative models are used for modelling data directly that is modelling observations drawn from a probability density function). This approach to probabilistic classification finds the joint distribution p(x, c), expressed for instance as a parametric model, and then subsequently use this joint distribution to evaluate the conditional p(c|x) in order to make predictions of c for new values of x by application of Bayes theorem. This is known as a generative approach since by sampling from the joint distribution it is possible to generate synthetic examples of the feature vector x (Figure 30.3). Here for the vector of random variables we learn the probability for each class c given the input. In practice, the generalization performance of generative models is often found to be poorer than that of discriminative models due to differences between the model and the true distribution of the data.<\/p>\r\n\"\"\r\n

Figure 30.3 Generative Model<\/strong><\/p>\r\n \r\n\r\n30.3 Na\u00efve Bayes<\/strong>\r\n\r\n \r\n

Na\u00efve Bayes is a type of generative model. Here we try to determine the conditional probability P(C|X) that is the probability of a class given a set or bag of features. This probability can be determined by finding the likelihood of the input features given the class and the prior probability of the class. Here the difficulty lies in learning the joint probability of the features given the class.<\/p>\r\n\"\"\r\n

An important assumption that Na\u00efve Bayes method makes is that all input<\/strong> attributes are conditionally independent. <\/strong>In other words assume that the\u00a0joint probability can be found by finding the individual probability of each feature given the class (Figure 30.4).<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\r\n

Figure 30.4 Na\u00efve Bayes Assumption<\/strong><\/p>\r\n \r\n

This is an important special, simplification of a Bayes optimal classifier, where the hypothesis is the classification and all attributes are conditionally independent given the class (Figure 30.5)<\/p>\r\n\"\"\r\n

Figure 30.5 Independence of Attributes<\/strong><\/p>\r\n \r\n

The setting for the Na\u00efve Bayes classifier is where a set of training examples is provided, and a new instance is presented, described by the tuple of attribute values (a<\/em><\/strong>l<\/em><\/strong>, a<\/em><\/strong>2<\/em><\/strong> ...a<\/em><\/strong>n<\/em><\/strong>).<\/em><\/strong> The job of the learner is to predict the target value (classification), for this new instance.<\/p>\r\n \r\n

Na\u00efve Bayes is one of the most practical Bayes learning methods. The naive Bayes classifier applies to learning tasks where each instance x<\/em> is described by a conjunction of attribute values and where the target function f (x) can take on any value from some finite set V. Na\u00efve Bayes method is generally used when there is a moderate or large training set available and when attributes that describe instances are conditionally independent given the classification. Some successful applications of Na\u00efve Bayes method are medical diagnosis and classifying text documents.<\/p>\r\n \r\n\r\n30.3 Na\u00efve Bayes Classifier: Assumptions<\/strong>\r\n\r\n \r\n

As already discussed for the Na\u00efve Bayes classifier we need to determine two probabilities that is prior probability of the class and the likelihood of the data with respect to the class.<\/em><\/p>\r\n\r\n<\/div>\r\n \r\n\r\nThe prior probability of the class <\/span>P<\/em>(c<\/em><\/strong>j<\/em><\/strong>) c<\/strong>an be estimated from the frequency of classes in the training examples.<\/span>\r\n

\r\n\r\n \r\n

However the likelihood or the joint probability of the features of the input data given the class P<\/em>(x<\/em><\/strong>1<\/em><\/strong>,x<\/em><\/strong>2<\/em><\/strong>,\u2026,x<\/em><\/strong>n<\/em><\/strong>|c<\/em><\/strong>j<\/em><\/strong>)<\/strong> is of the order of O(|X|<\/em>n<\/em>\u2022|C|<\/em>) and can only be estimated if a very, very large number of training examples was available. This is where the naivety of Na\u00efve Bayes method comes into the picture that is the conditional independence assumption <\/strong>where we assume that the probability of observing the conjunction of attributes is equal to the product of the individual probabilities.<\/p>\r\n \r\n

Let us first formulate Bayesian Learning. Let each instance x<\/em> of a training set D<\/em> be a conjunction of n<\/em> attribute values <a<\/em>1<\/em>,a<\/em>2<\/em>,..,a<\/em>n<\/em>><\/em> and let f(x),<\/em> the target function, be such that f(x)<\/em> \u00ce<\/em> V<\/em>, a finite set. According to the Bayesian approach using Maximum A Posteriori (MAP) we can specify this as follows:<\/p>\r\n\"\"\r\n

Here we try to find a value v<\/em><\/strong>j<\/em><\/strong> that maximizes the probability given the attribute values. Applying Bayes Theorem this is finding the v<\/em><\/strong>j<\/em><\/strong> that maximizes the product of the likelihood P(a<\/em><\/strong>1<\/em><\/strong>,a<\/em><\/strong>2<\/em><\/strong>,..,a<\/em><\/strong>n<\/em><\/strong>|v<\/em><\/strong>j<\/em><\/strong>)<\/em><\/strong> and the prior probability P(v<\/em><\/strong>j<\/em><\/strong>).<\/em><\/strong><\/p>\r\n \r\n

Now according to Na\u00efve Bayesian Approach, w<\/strong>e assume that the attribute values are conditionally independent so that P(a<\/em><\/strong>1<\/em><\/strong>,a<\/em><\/strong>2<\/em><\/strong>,..,a<\/em><\/strong>n<\/em><\/strong>|v<\/em><\/strong>j<\/em><\/strong>) =<\/em><\/strong>\u00d5<\/em><\/strong>i<\/em><\/strong> P(a<\/em><\/strong>1<\/em><\/strong>|v<\/em><\/strong>j<\/em><\/strong>)<\/em><\/strong>. This means that too large a data set is not required.<\/p>\r\n \r\n\r\nTherefore\u00a0 Na\u00efve Bayes Classifier:<\/em>\u00a0v<\/em><\/strong>NB<\/em><\/strong> = argmax<\/em><\/strong>vj<\/em><\/strong>\u00ce V<\/em><\/strong> P(v<\/em><\/strong>j<\/em><\/strong>) <\/em><\/strong>\u00d5i<\/em><\/strong> P(a<\/em><\/strong>i<\/em><\/strong>|v<\/em><\/strong>j<\/em><\/strong>)\u00a0<\/em><\/strong>Na\u00efve assumption of attribute independence for a set of k features is as given below:\r\n\r\n \r\n\r\nP(x1,\u2026,xk|C) = P(x1|C)\u00b7\u2026\u00b7P(xk|C)\r\n\r\n \r\n

Now if the If i-th attribute is categorical then P(xi|C) is estimated as the relative freq of samples having value xi. However if the i-th attribute is continuous then P(xi|C) is estimated through a Gaussian density function. It is computationally easy in both cases.<\/p>\r\n \r\n

30.5 Na\u00efve Bayes Algorithm<\/strong><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\nNa\u00efve Bayes Algorithm (considering discrete input attributes) has two phases\r\n\r\n \r\n\r\n1.\u00a0 <\/strong>Learning Phase<\/strong>: Given a training set S<\/strong>,\r\n\r\n\"\"\r\n\r\n \r\n\r\n2. Test Phase<\/strong>: Given an unknown instance Xj, Nj X L Look up tables to assign the label c*<\/em> to X\u2019<\/strong> if X\u2019 = (a1\u2019, a2\u2019, \u2026\u2026an\u2019) Classification is easy, just multiply probabilities\r\n\r\n\"\"\r\n\r\nNaive Bayes Classifier<\/strong>\r\n\r\n \r\n\r\nIn general we assume that target function is f: X<\/em> \u00e8<\/em> V<\/em>, where each instance x<\/em> is described by attributes a<\/em>1<\/em>, a<\/em>2<\/em> .. a<\/em>n<\/em>\r\n\r\n\"\"\r\n\r\n<\/div>\r\n
\r\n\r\n\"\"\"\"\r\n\r\n30.6 Characteristics of Na\u00efve Bayes<\/strong>\r\n\r\n \r\n

Therefore Na\u00efve Bayes classifier only requires the estimation of the prior probabilities P(C<\/em>K<\/em><\/sub>)<\/em> (where k is the given number of classes), and p<\/em> (where p is the number of attributes) conditional probabilities for each class. We will be able to answer full set of queries across classes and features. Empirical evidence shows that Na\u00efve Bayes\u00a0classifiers work remarkable well. It has been that the use of a more complex full Bayes (belief) network provides only limited improvements in classification performance.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\n30.7 Example 1 \u2013 Playing Tennis<\/strong>\r\n\r\n \r\n\r\nGiven a training set (Figure 30.6), we can compute probabilities from the data.\r\n\r\n \r\n

Training Phase: <\/strong>First we compute the probabilities of Playing tennis (positive) and not Playing Tennis (negative) as P(p) and P(n) respectively (Figure 30.7).<\/p>\r\n\"\"\r\n

Figure 30.7 Probability of Playing tennis and not Playing Tennis<\/strong><\/p>\r\n \r\n\r\nProbabilities of each of the attributes is then calculated as given below:\r\n\r\n \r\n

We need to estimate P(xi|C) where xi is each value for each attribute given C which is either positive (p) or negative (n) class for Play Tennis. For example consider the attribute Outlook has value sunny for 2 of the 9 positive samples (2\/9) and for 3 of the 5 negative samples (3\/5). We calculate such probabilities for every other attribute value for attribute Outlook and similarly for each value of each of the other attributes Temperature, Humidity and Windy (Figure 30.8)<\/p>\r\n\"\"\r\n

Figure 30.8 Conditional Probabilities of each Attribute<\/strong><\/p>\r\n\r\n<\/div>\r\n

\u00a0<\/strong>Test Phase<\/strong>: Given a new instance<\/span> x\u2019 <\/strong>of variable values, we need to calculate the probability of either Playing Tennis or not Playing Tennis. Now assume we are given the values of the four attributes as shown below:<\/span><\/p>\r\n \r\n

x\u2019=(Outlook=Sunny,<\/em> Temperature=Cool,<\/em> Humidity=High,<\/em> Wind=Strong<\/em>)<\/strong><\/p>\r\n\r\n

\r\n\r\n\"\"\r\n

Figure 30.9 Calculating whether Tennis will be played given the new instance<\/strong><\/p>\r\n \r\n

Here we consider the probability of Outlook being Sunny and look up the probability of Play Tennis and not Play tennis. Similarly we look up the probabilities for Temperature =Cool, Humidity = High and Wind = Strong. Now we can calculate the probability of Playing tennis and not Playing Tennis given the new instance x\u2019<\/strong> by finding the product of each of the probabilities obtained for the value of each variable. Now we find that P(Yes\/ x\u2019) = 0.0053 and P(No\/ x\u2019) = 0.0206. Since P(No\/ x\u2019) is greater we can conclude that the new instance x\u2019 <\/strong>will be labelled as No.<\/p>\r\n \r\n\r\n30.8 Example 2 \u2013 Text Classification<\/strong>\r\n\r\n \r\n

We learn from examples which articles are of interest. The attributes in this case are the words. Since we are talking about the Na\u00efve Bayes model, this just means that we have a random sequence model within each class. It has been found that NB classifiers are one of the most effective classifiers for this task.<\/p>\r\n \r\n\r\n30.8.1 Definition of Text Classification<\/strong>\r\n\r\n \r\n

First let us define the Text Classification problem. Here a document d is a data point in multi-dimensional space X, whose dimension is based on the number of unique words in the corpus. C is the set of categories we want the documents to be classified under. D is the training set of labelled documents <d,c>. The learning algorithm needs to find a mapping g that X \u00ae C (Figure 30.10).<\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\r\n

Figure 30.10 Definition of Text Classification <\/strong><\/p>\r\n \r\n

30.8.2 Uses of Text Classification<\/strong><\/p>\r\n \r\n\r\nText classification is the task of classifying text documents to multiple classes.\r\n\r\n \r\n\r\nThis has many applications as listed below:\r\n\r\n \r\n\r\n\u2013\u00a0 Is this mail spam?\r\n\r\n\u2013\u00a0 Is this article from comp.ai or misc.piano?\r\n\r\n\u2013\u00a0 Is this article likely to be relevant to user X?\r\n\r\n\u2013 Is this page likely to lead me to pages relevant to my topic? (as in topic-specific crawling), etc.\r\n\r\n \r\n\r\n \r\n\r\n30.8.3 Na\u00efve Bayes Classifier and Text Classification<\/strong>\r\n\r\n \r\n\r\n30.8.3.1 Document Representation<\/strong>\r\n\r\n \r\n

Na\u00efve Bayes Classifier has been applied widely for text classification tasks. The question to be answered is how to represent text documents as feature vectors? The vector space representation is one where each document is represented by a n dimensional vector where n is the number of unique words (after removing all stop words) of all the documents in the document corpus (the collection unique words is called vocabulary).There are many vector space variants. The vector space model that is widely used is the one where each document is represented in each dimension by the frequency of occurrences of the words. One variant of the vector representation is the binary version each dimension is 1 if the word is present in the document, 0 otherwise. A problem with vector space representation is that the vectors are likely to be as large as the size of the vocabulary. Then \u201cfeature selection\u201d techniques are used to select only a subset of words as features. One simple feature selection method is to limit the vocabulary by having words with frequency of occurrence that are above a threshold. In another variation of the vector space model we have the unigram model where the document is represented as a vector of positions with values being the words.<\/p>\r\n \r\n

30.8.3.2 Na\u00efve Bayes Algorithm \u2013Testing Phase<\/strong><\/p>\r\n \r\n

During the testing phase, given a test document <\/span>X where n is<\/em> the number of word occurrences in <\/span>X, we need to r<\/em>eturn the category of the document. Here we find the category C using Maximum Likelihood that is the C that gives maximum probability with product of likelihood of n attributes given Ci and the prior probability of Ci. Here we assume that <\/span>a<\/em>j<\/em> is the word occurring at the the <\/span>j<\/em>th position in X. The probabilities of each of the attributes is assumed to be independent according to the Na\u00efve Bayes assumption.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\r\n\r\n \r\n\r\n30.8.3.3 Text Na\u00efve Bayes Algorithm \u2013 Training Phase<\/strong>\r\n\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\n30.9 Learning the Model<\/strong>\r\n\r\n\"\"\r\n

Figure 30.11 Na\u00efve Bayes Model<\/strong><\/p>\r\n \r\n

Let us assume that the Na\u00efve Bayes Model is represented as in Figure 30.11 where C is the class which is dependent on 6 attributes. The common practice used to find the maximum likelihood is to simply use the frequencies in the data. The two terms of Maximum Likelihood, prior probability and likelihood are\u00a0calculated as given below. We explain with document classification as example. The prior probability P(cj) of a class cj is calculated as the number of documents in the labelled corpus with category C=cj<\/sub> divided by the total number of documents. The likelihood of the each attribute or feature (word) xi given class cj<\/sub> is calculated as the number of documents of class cj having that attribute divided by the total number of documents of class cj. We find the posterior probability for each class in this way.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\r\n

Figure 30.12 Calculating Prior Probability and Likelihood<\/strong><\/p>\r\n \r\n

In order to reemphasize the na\u00efve Bayes assumption, we use the example of classification of Flu given the 5 symptoms runnynose, sinus, cough, fever, muscle-ache (Figure 30.13). We do not find the probability of all symptoms occurring together but assume that the symptoms are independent and hence calculate the likelihood of each symptom given the class independently.<\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\r\n

Now the issue is what if we have seen no training cases where patient had no flu and muscle aches? In other words certain cases are zero because these cases not available in training set. Zero probabilities cannot be conditioned away, no matter the other evidence therefore we need to do some method of smoothing. We will explain this in the next section.<\/p>\r\n \r\n\r\n30.9.1 Naive Bayes - to Classify Text: Basic method<\/strong>\r\n\r\n \r\n

Let us assume that the documents are represented by attributes that are text positions, where the values are words. This is as given below.<\/p>\r\n\"\"\r\n

However there are too many possibilities. Now let us assume that the classification is independent<\/em> of the positions of the words, now we need to use some parameters for each position and hence we come to what is called the \u201cBag of words\u201d model.<\/p>\r\n \r\n\r\n30.10 Example 3 \u2013Text Classification<\/strong>\r\n\r\n \r\n\r\nLet us take a toy example of text classification to explain Na\u00efve Bayes method. Let us assume we are given N=4 documents which are classified into two classes: \u201cChina\u201d, \u201cnot China\u201d. We are also know the vocabulary V = {Beijing, Chinese, Japan, Macao, Tokyo}. We need to classify the test document given.\r\n\r\n\"\"\r\n

Figure 30.14 Example for Text Classification<\/strong><\/p>\r\n \r\n\r\nThe prior probability of class China and not China is given below:\r\n\r\n\"\"\r\n

We need nonzero probabilities for all words, even for words that don't exist. So we just count every word one time more than it actually occurs ( a way of\u00a0smoothing). Since we are only concerned with relative probabilities, this inaccuracy should be of no concern. Therefore the way to calculate likelihood for the example is as follows (Figure 30.15):<\/span><\/p>\r\n\r\n<\/div>\r\n \r\n\r\n\"\"\r\n

\r\n

Figure 30.15 Calculating Likelihood<\/strong><\/p>\r\n \r\n

Now we need to carry out estimation to find the likelihood and use this to do the classification of the test document. We find the likelihood of each word (Chinese, Tokyo, Japan) in the test document for class Chinese and class not Chinese. Then we find the posterior probability of class Chinese and class not Chinese as given in Figure 30.16. We find that the probability for Class Chinese is higher and so that is the class of the test document.<\/p>\r\n\"\"\r\n

Figure 30.16 Estimation and Classification for the Example<\/strong><\/p>\r\n \r\n\r\n30.11 Na\u00efve Bayes Classifier - Comments<\/strong>\r\n\r\n \r\n

The foremost reason for the wide use of Na\u00efve Bayes classifier is that it is easy to implement. The major advantage of Na\u00efve Bayes classifier is that it has good learning speed as well as classification speed. It has modest space storage requirements. In addition incrementality is supported. Recommendations can re-done as more attribute values of the new item become known. Another advantage is that it seems to work very well in many scenarios. Na\u00efve Bayes Classifier has much wider range of applicability than previously thought, this despite using the independence assumption.<\/p>\r\n \r\n

However classification accuracy is different from probability estimate accuracy. We make the assumption of class conditional independence and therefore there is loss of accuracy because practically, dependencies exist among variables. As an example in hospitals: we can have patients who have profiles\u00a0based on variables such as age, family history etc , who are associated with symptoms: such as fever, cough etc., and can have diseases such as lung cancer, diabetes etc and some of these variables are not independent. Dependencies among these variables cannot be modeled by Na\u00efve Bayesian Classifier, We will tackle these dependencies later using Bayesian Belief Networks.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\n30.12 Issues Relevant to Na\u00efve Bayes<\/strong>\r\n\r\n \r\n\r\n1.\u00a0 Violation of Independence Assumption<\/strong>\r\n\r\n \r\n\r\nFor many real world tasks, events are correlated, but nevertheless, na\u00efve Bayes works surprisingly well anyway.\r\n\r\n\"\"\r\n\r\n \r\n\r\n2.\u00a0 Zero conditional probability Problem<\/strong>\r\n\r\n \r\n\r\nSuch problem exists when no example contains the attribute value\r\n\r\n\"\"\r\n

during test. One solution to the issue is to estimate conditional probabilities with virtual examples. We have estimated probabilities by the fraction of times the event is observed to n<\/em>c<\/em> occur over the total number of opportunities n. However<\/em> this provides poor estimates when n<\/em>c<\/em> is very small. What happens if none of the training instances with target value v<\/em>j<\/em> have attribute value a<\/em>i<\/em>? In other words n<\/em>c<\/em> is 0.<\/p>\r\n \r\n

When n<\/em>c<\/em> is very small we calculate likelihood as follows :<\/p>\r\n\"\"\r\n

Here n <\/em>is number of training examples for which v=v<\/em>j<\/em> , n<\/em>c<\/em> number of examples for which v=v<\/em>j<\/em> and a=a<\/em>i,<\/em> p<\/em> is prior<\/strong> estimate and m<\/em> is weight given to prior (i.e. number of ``virtual'' examples) .<\/p>\r\n\r\n<\/div>\r\n\"\"\r\n\r\nSummary<\/strong>\r\n