# PagedeGeek/naive-bayes forked from sausheong/naive-bayes

### Subversion checkout URL

You can clone with HTTPS or Subversion.

Fetching contributors…

Cannot retrieve contributors at this time

275 lines (218 sloc) 20.134 kb
 I first learnt about probability when I was in secondary school. As with all the other topics in Maths, it was just another bunch of formulas to memorize and regurgitate to apply to exam questions. Although I was curious if there was any use for it beyond calculating the odds for gambling, I didn't manage to find out any. As with many things in my life, things pop up at unexpected places and I stumbled on it again when as I started on machine learning and naive Bayesian classifiers. A classifier is exactly that -- it's something that classifies other things. A classifier is a function that takes in a set of data and tells us which category or classification the data belongs to. A naive Bayesian classifier is a type of learning classifier, meaning that you can continually train it with more data and it will be be better at its job. The reason why it's called Bayesian is because it uses Bayes' Law, a mathematical theorem that talks about conditional probabilities of events, to determine how to classify the data. The classifier is called 'naive' because it assumes each event (in this case the data) to be totally unrelated to each other. That's a very simplistic view but in practice it has been proven to be a surprisingly accurate. Also, because it's relatively simple to implement, it's quite popular. Amongst its more well-known usage include email spam filters. So what's Bayes' Law and how can it be used to categorize data? As mentioned, Bayes' Law describes conditional probabilities. An example of conditional probability is the probability of an event A happening given that another event B has happened. This is usually written as Pr(A | B), which is read as the probability of A, given B. To classify a document, we ask -- given a particular text document, what's the probability that it belongs to this category? When we find the probabilities of the given document in all categories, the classifier picks the category with the highest probability and announce it as the winner, that is, the document most probably belongs to that category. The question then follows, how to we get the probability of a document belonging to a category? This is where we turn to Bayes' Law which states that: Given our usage, what we want is: What we need is Pr(document|category) and Pr(category). You should keep in mind that we're comparing relative probabilities here so we can drop Pr(document) because it is the same for every category. What is Pr(document|category) and how do we find it? It is the probability that this document exists, given a particular category. As a document is made of a bunch of words, what we need to do is to calculate the probability of the words in the document within the category. Here is where the 'naive' part comes in. We know that the words in a document are not random and the probability of a word like 'Ruby' would be more likely to be found in an article on the Ruby programming language than say, an article on the dental practices in Uganda. However for the purpose of simplicity, the naive Bayesian classifier treats each word as independent of each other. Remember your probability lessons -- if the probability of each word is independent of each other, the probability of a whole bunch of words together is the product of the probability of each word in the bunch. A quick aside to illustrate this. Take a pair of dice and roll them one after another. The probability of the the first die to fall on any one of its 6 sides is 1 out of 6, that is 1/6. The probability of the second die to fall on any one of its 6 sides is also 1/6. So what is the probability that both dice lands on 6? Out of the 6 x 6 = 36 possible ways that a pair of dice can land there is only 1 way that both dice lands on 6, so the probability is 1/36, which is 1/6 x 1/6. This is true only if the dice rolls are independent of each other. In the same way we are 'naively' assuming that the words in the document are occurring independently of each other, as if it is written by the theoretical monkey with a typewriter. In other words, the probability that a document exists, given a category, is the product of the probability of each word in that document. Now that we've established this, how do we get the probability of a single word? Basically it's the count of the number of times the word appeared in the category after the classifier has been trained compared to the total word counts in that category. Another quick illustration. Say we train the classifier with 2 categories (spam and not-spam), there are 100 word counts in the spam category. There are only be 14 unique words in this category but some of these words have been trained more than once. Out of these 100 word counts, 5 of them are for the word 'money'. The probability for the word 'money' would be the number of times it is mentioned in the spam category (5) divided by the number of word counts in this category (100). Now that we know Pr(document|category) let's look at Pr(category). This is simply the probability of any document being in this category (instead of being in another category). This is the number of documents used to train this category over the total number of documents that used to train all categories. So that's the basic idea behind naive Bayesian classifiers. With that I'm going to show you how to write a simple classifier in Ruby. There is already a rather popular Ruby implementation by Lucas Carlsson called the Classifier gem (http://classifier.rubyforge.org) which you can use readily but let's write our own classifier instead. We'll be creating class named NativeBayes, in a file called native_bayes.rb. This classifier will be used to classify text into different categories. Let's recap how this classifier will be used:
1. First, tell the classifier how many categories there will be
2. Next, train the classifier with a number of documents, while indicating which category those document belongs to
3. Finally, pass the classifier a document and it should tell us which category it thinks the document should be in
Now let's run through the public methods of the NativeBayes class, which should map to the 3 actions above:
1. Provide the categories you want to classify the data into
2. Train the classifier by feeding it data
3. Doing the real work, that is to classify given data