That naive Bayes thing

The total probability formula is the basic rule that associates edge probability with conditional probability. It represents the total probability of an outcome, which can be realized by several different events.

The total probability formula transforms the problem of solving the probability of a complex event into a sum problem of the probability of simple events occurring under different circumstances. Formula for P = ∑ (B) (I = 1 n P (A I) P (B | A I) “role =” presentation “style =” position: relative;” > P = ∑ ni = 1 (B) P (Ai) P (B | Ai) P (B) = ∑ I = 1 n P (A I) P (B | A I).

Assume A sample space S, which is the sum of two events A and C, and event B has intersection with both of them, as shown in the figure below:

The probability of event B can be expressed as P (B) = P (B ⋂ A) + P (B ⋂ C)” role=”presentation” style=”position: relative;” > P (B) = P (B ⋂ A) + P (B ⋂ C) P (B) = P (B ⋂ A) + P (B ⋂ C)

Can be inferred through the conditional probability, P (B ⋂ A) = P (B | A) P (A) “role =” presentation “style =” position: relative;” ⋂ A > P (B) = P (B | A) P (A) P (B ⋂ A) = P (B | A) P (A), So P (B) = P (B | A) P (A) + P (B | C) P (C) “role =” presentation “style =” position: relative;” >P(B)=P(B|A)P(A)+P(B|C)P(C) P ( B ) = P ( B | A ) P ( A ) + P ( B | C ) P ( C )

So this is the total probability formula, which says that the probability of event B is equal to the sum of the probabilities of event A and of event C times the conditional probabilities of event B for each of them.

Similarly, to apply this formula, suppose that there are two factories that produce and supply light bulbs. The bulb from Factory X will work more than 5,000 hours 99% of the time, and the bulb from factory Y will work more than 5,000 hours 95% of the time. Factory X has 60% market share, and factory Y has 40%. What is the probability that the bulbs purchased will work more than 5,000 hours?

Using the total probability formula, it can be concluded that:

• P r ( B x ) = 6 10 ” role=”presentation” style=”position: relative;” >Pr(Bx)=610 Pr(Bx)=610: the probability of purchasing the light bulb made by factory X.

• P r ( B y ) = 4 10 ” role=”presentation” style=”position: relative;” >Pr(By)=410 Pr(By)=410: the probability of purchasing the bulb made By factory Y.

• P r ( A | B x ) = 99 100 ” role=”presentation” style=”position: relative;” > Pr (A | Bx) = 99100 r P (A | B) x = 99, 100: factory manufacturing x light bulb work more than 5000 hours of probability.

• P r ( A | B y ) = 95 100 ” role=”presentation” style=”position: relative;” > Pr (A | By) = 95100 r P (A | B y) = 95, 100: factory manufactures light bulb y probability of more than 5000 hours of work time.

Thus, the probability of purchasing a light bulb that works more than 5,000 hours is 97.4 percent.

Let’s say that X = f 1, f 2… F n” role=”presentation” style=”position: relative;” >X=f1,f2… fn X=f1,f2… fn, where each f is a characteristic attribute of X, C m “role=”presentation” style=”position: relative;” >C1,C2… Cm C1,C2… Cm.

You then need to calculate P (C | X 1), P (C | X) 2,…, P (m | C X) “role =” presentation “style =” position: relative;” > P (C1 | X), P (C2) | X,…, P (Cm | X) P (C | X 1), P (C | X) 2,…, P (m | X C), we can according to a training sample set (known classification to be classified collection). Then the conditional probability of each characteristic attribute in each category is obtained statistically:

P (f | 1 C, 1), P (f 2 | C 1),…, P n | 1 C (f),…, P (f | 1 C 2), P (f | 2 C 2),…, P n | 2 C (f), …, P (f | 1 C m), P (f | C m) 2,…, P n | C m (f) “role =” presentation “style =” position: relative;” | C1 > P (f1), P (f2 | C1),…, P (fn | C1),…, P | C2 (f1), P (f2 | C2),…, P (fn | C2),…, P | Cm (f1), P (f2 | Cm),…, P (fn | Cm) P (f | 1 C 1), P | C f (double),…, P n | 1 C (f),…, P (f | 1 C 2), P (f | C 2) 2,…, P n | 2 C (f),… P (f | 1 C m), P (f | C m 2),…, P n | C m (f)

If P (C k | X) = M A X (P (C | X 1), P (C | X) 2,…, P (M | C X)) “role =” presentation “style =” position: relative;” > P (Ck) | X = MAX (P (C1 | X), P (C2) | X,…, P (Cm) | X) P (C k | X) = M A X (P (C | X 1), P (C | X) 2,…, P (M | C X)), Then X ∈ C k “role=”presentation” style=”position: relative;” >X∈Ck X∈Ck (Bayesian classification is basically the one with the highest probability).

Naive bayes will assume that each characteristic is independent, according to the bayes’ theorem can be driven: P (C I | X) = P (X | C I) P (C I) P (X) “role =” presentation “style =” position: relative;” > P (Ci X |) = P (X | Ci) P (Ci) P (X) P (C I | X) = P (X | C I) P (C I) P (X), as the denominator for all categories for constant, so you just need to maximising molecules, and because of all the features are independent of each other, So the result is:

According to the above formula derivation, the process of naive Bayes can be shown as the figure below:

Let’s walk through the process in the figure above with an example.

There is a site that wants a program to automatically identify an account’s authenticity (sorting accounts into real and fake accounts, which are trumpets with fake information or malicious registrations).

• First, characteristic attributes and categories need to be determined, and then training samples need to be obtained. Assume that an account has three characteristics: number of logs/number of registered days (F1), number of friends/number of registered days (F2), and whether it uses a real profile picture (True: 1, False: 0).

• Using 10,000 accounts that had been manually examined as a training sample, P (C 0) = 8900 ÷ 10000 = 0.89, P (C 1) = 1100 ÷ 10000 = 0.11″ role=”presentation” style=”position: relative;” >P(C0)=8900÷10000=0.89,P(C1)=1100÷10000= 0.11p (C0)=8900÷10000=0.89,P(C1)=1100÷10000=0.11, C0 represents the category probability of the real account (89%), and C1 represents the category probability of the fake account (11%).

• Then the conditional probability of each feature under each category needs to be calculated and substituted into the naive Bayes classifier, Available P (F | 1 C) P (2 F | C) P (3 F | C) P (C) “role =” presentation “style =” position: relative;” | C) > P (F1, F2 P | C) P (F3 | C) P (C) P (F | 1 C) P (2 F | C) P (3 F | C) P (C), but there is one problem is that the F1 and F2 are continuous variables, not appropriate according to the probability of a specific value calculation. The solution is to convert continuous values into discrete values, and then calculate the probability of the interval, for example, decompose F1 into three intervals [0,0.05], [0.05,0.2], [0.2,+∞], and then calculate the probability of each interval.

• F 1 = 0.1, F 2 = 0.2, F 3 = 0″ role=”presentation” style=”position: relative; >F1=0.1,F2=0.2,F3=0 F1=0.1,F2=0.2,F3=0, guess whether the account is a real one or a fake one. In this case, F1 is 0.1 and falls within the second interval, so the probability of the occurrence of the second interval is used in calculation. According to the training samples, the results can be obtained as follows:

• Then the trained classifier can be used to get the real account probability and false account probability of the account, and then take the maximum probability as its category:

The end result is that the account is a real one.

With enough theory in mind, we are going to implement a Gaussian Naive Bayes in Python to solve the diabetes problem of the Pima people. The sample data (available from this hyperlink) is a CSV file with each value as a number. The document describes real-time measurements from the patient’s age, number of pregnancies and blood test results. Each record has a category value (a Boolean value, expressed as 0 or 1) that indicates whether the patient has had diabetes in the last five years. This is a data set that has been studied extensively in the machine learning literature, and a good prediction accuracy would be between 70% and 76%. The meaning of each column of sample data is as follows:

Column 1: Number of pregnancies Column 2: Plasma glucose concentration in the oral glucose tolerance test (2h) Column 3: cardiac diastolic pressure (mm Hg) Column 4: Triceps skin fold thickness (mm) Column 5: Serum insulin within 2h (MU U/ mL) Column 6: Body mass index ((weight in kg/(height in m)^2)) Column 7: Family effect column 8: Age column 9: Category Boolean value, 0 is 5 years without diabetes, 1 to 5 years had diabetes -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 6148,72,35,0,33.6, 0.627, 1,85,66,29,0,26.6 50, 1, 0.351, 31, 0 1,89,66,23,94,28.1,64,0,0,23.3 8183, 0.672, 32, 1, 0.167, 21 0137,40,35,168,43.1, 0, 2.288, 33, 1...Copy the code

The first thing to do is read this CSV file and parse it into a data structure that we can use directly. Due to the sample data file without any empty lines and mark symbol, is each row corresponds to a row, simply put each line can be encapsulated into a list (return results as a list, it is every element contains a row of the list), pay attention to the data in the file are for the digital, need to do first type conversion.

import csv
def load_csv_file(filename):
    with open(filename) as f:
        lines = csv.reader(f)
        data_set = list(lines)
    for i in range(len(data_set)):
        data_set[i] = [float(x) for x in data_set[i]]
    return data_setCopy the code

After obtaining the sample data, the model needs to be divided into training data sets (which naive Bayes needs to use for prediction) and test data sets in order to evaluate the accuracy of the model. The data is randomly selected in the process of segmentation, but we will choose a ratio to control the size of the training data set and test data set, generally 67% : 33%, which is a relatively common ratio.

import random
def split_data_set(data_set, split_ratio):
    train_size = int(len(data_set) * split_ratio)
    train_set = []
    data_set_copy = list(data_set)
    while len(train_set) < train_size:
        index = random.randrange(len(data_set_copy))
        train_set.append(data_set_copy.pop(index))
    return [train_set, data_set_copy]Copy the code

After sample data is segmented, more detailed processing is required for the training data set. Gaussian Naive Bayes assumes that every feature follows normal distribution, so abstracts need to be extracted from the training data set, which contains mean and standard deviation. The number of abstracts is determined by the combination number of categories and feature attributes. If you have three categories and seven characteristic attributes, then you need to calculate the mean and standard deviation for each characteristic attribute and category, which is 21 summaries.

Before calculating the summary of the training data set, our first task is to separate the characteristics and categories of the training data set, that is, to construct a hash table with the key as the category and the value as the row of the data in that class.

def separate_by_class(data_set, class_index):
    result = {}
    for i in range(len(data_set)):
        vector = data_set[i]
        class_val = vector[class_index]
        if (class_val not in result):
            result[class_val] = []
        result[class_val].append(vector)
    return resultCopy the code

Since you already know that there is only one category and that it is at the end of each row, you simply pass -1 to the class_index argument. Then a summary of the training data set is calculated (the mean and standard deviation of each characteristic attribute in each category). The mean is used as the median of the normal distribution, while the standard deviation describes how discrete the data is, and is used as the expected distribution of each characteristic attribute in the normal distribution when calculating the probability.

The standard deviation is the square root of the variance, which can be obtained by first finding the variance (the average of the square sum of the difference between each eigenvalue and the mean).

import math
def mean(numbers):
    return sum(numbers) / float(len(numbers))
def stdev(numbers):
    avg = mean(numbers)
    variance = sum([pow(x - avg, 2) for x in numbers]) / float(len(numbers))
    return math.sqrt(variance)Copy the code

With these auxiliary functions, it is easy to calculate the summary by constructing the hash table with key as the category from the training data set, and then calculating the mean and standard deviation according to the category and each feature.

def summarize(data_set): Use the zip function to encapsulate the NTH attribute in each element into a tuple. Summariecheck is to package each column into a tuple summaries = [(mean(feature), Stdev (feature)) for feature in zip(*data_set)] del summaries[-1] # summarize_by_class(data_set): class_map = separate_by_class(data_set, -1) summaries = {} for class_val, data in class_map.items(): summaries[class_val] = summarize(data) return summariesCopy the code

The data processing stage has been completed, and the following task is to make predictions based on the training data set. This stage needs to calculate the class probability and the conditional probability of each feature and category, and then select the category with the highest probability as the classification result. The key is to calculate the conditional probability, using the density function of the normal distribution, which depends on the parameters (characteristic, mean, standard deviation) that we have already prepared.

def calculate_probability(x, mean, stdev): exponent = math.exp(-(math.pow(x - mean, 2) / (2 * math.pow(stdev, 2)))) return (1 / (math.sqrt(2 * math.pi) * stdev)) * exponent def calculate_conditional_probabilities(summaries, input_vector): probabilities = {} for class_val, class_summaries in summaries.items(): probabilities[class_val] = 1 for i in range(len(class_summaries)): Typecheck link Mean, stdev = class_summariecheck [I] # input_vector is a row of data in test_set, X is a characteristic attribute in this line x = input_vector[I] # multiply the probabilities probabilities[class_val] *= calculate_probability(x, mean, stdev) return probabilitiesCopy the code

The function calculate_conditional_probabilities() returns a hash table with the key of the category and the value of the probability. The hash table records the conditional probability of each feature category, and then only needs to select the category with the highest probability.

def predict(summaries, input_vector):
    probabilities = calculate_conditional_probabilities(summaries, input_vector)
    best_label, best_prob = None, -1
    for class_val, probability in probabilities.items():
        if best_label is None or probability > best_prob:
            best_label = class_val
            best_prob = probability
    return best_labelCopy the code

Finally, we define a function to predict the accuracy of the model for each data instance in the test data set. This function returns a list of predicted values for each data instance. Based on this return value, the accuracy of the prediction can be evaluated.

def get_predictions(summaries, test_set): predictions = [] for i in range(len(test_set)): result = predict(summaries, test_set[i]) predictions.append(result) return predictions def get_accuracy(predictions, Detecset): Correct = 0 for x in range(Len (test_set)): the predictions are correct if test_set[x][-1] == Predictions [x]: Correct += 1 return (correct/float(len(test_set)) * 100.0Copy the code

The complete code is as follows:

import csv, random, math """ A simple classifier base on the gaussian naive bayes and problem of the pima indians diabetes. (https://archive.ics.uci.edu/ml/datasets/Pima+Indians+Diabetes) """ def load_csv_file(filename): with open(filename) as f: lines = csv.reader(f) data_set = list(lines) for i in range(len(data_set)): data_set[i] = [float(x) for x in data_set[i]] return data_set def split_data_set(data_set, split_ratio): train_size = int(len(data_set) * split_ratio) train_set = [] data_set_copy = list(data_set) while len(train_set) < train_size: index = random.randrange(len(data_set_copy)) train_set.append(data_set_copy.pop(index)) return [train_set, data_set_copy] def separate_by_class(data_set, class_index): result = {} for i in range(len(data_set)): vector = data_set[i] class_val = vector[class_index] if (class_val not in result): result[class_val] = [] result[class_val].append(vector) return result def mean(numbers): return sum(numbers) / float(len(numbers)) def stdev(numbers): avg = mean(numbers) variance = sum([pow(x - avg, 2) for x in numbers]) / float(len(numbers)) return math.sqrt(variance) def summarize(data_set): summaries = [(mean(feature), stdev(feature)) for feature in zip(*data_set)] del summaries[-1] return summaries def summarize_by_class(data_set): class_map = separate_by_class(data_set, -1) summaries = {} for class_val, data in class_map.items(): summaries[class_val] = summarize(data) return summaries def calculate_probability(x, mean, stdev): exponent = math.exp(-(math.pow(x - mean, 2) / (2 * math.pow(stdev, 2)))) return (1 / (math.sqrt(2 * math.pi) * stdev)) * exponent def calculate_conditional_probabilities(summaries, input_vector): probabilities = {} for class_val, class_summaries in summaries.items(): probabilities[class_val] = 1 for i in range(len(class_summaries)): mean, stdev = class_summaries[i] x = input_vector[i] probabilities[class_val] *= calculate_probability(x, mean, stdev) return probabilities def predict(summaries, input_vector): probabilities = calculate_conditional_probabilities(summaries, input_vector) best_label, best_prob = None, -1 for class_val, probability in probabilities.items(): if best_label is None or probability > best_prob: best_label = class_val best_prob = probability return best_label def get_predictions(summaries, test_set): predictions = [] for i in range(len(test_set)): result = predict(summaries, test_set[i]) predictions.append(result) return predictions def get_accuracy(predictions, test_set): correct = 0 for x in range(len(test_set)): if test_set[x][-1] == predictions[x]: Return (correct/float(len(test_set))) * 100.0 def main(): Filename = 'pima-indians-diabetes.data.csv' split_ratio = 0.67 data_set = load_csv_file(filename) train_set, test_set = split_data_set(data_set, split_ratio) print('Split %s rows into train set = %s and test set = %s rows' %(len(data_set), len(train_set), len(test_set))) # prepare model summaries = summarize_by_class(train_set) # predict and test predictions = get_predictions(summaries, test_set) accuracy = get_accuracy(predictions, test_set) print('Accuracy: %s' % accuracy) main()Copy the code