function [predict, accuracy] = NaiveBayes(Train, Test)
%Input: Training set and testing set, each row represents a instance, last column is label, begins from zero
%Output:predict label by NaiveBayes as well as its accuracy
Train_sample = Train(:,1:end-1);
Train_label = Train(:,end);
Test_sample = Test(:,1:end-1);
Test_label = Test(:,end);
Class_num = length(unique(Train_label));
Feature_num = size(Train_sample,2);
Para_mean =   cell(1,Class_num);%Mean for each feature and class
Para_dev = cell(1,Class_num);%Dev for each feature and class
Sample_byclass = cell(1,Class_num);%Reorder the data set by class
Prior_prob = zeros(1,Class_num);%Prior probability of each class
for i=1:1:length(Train_sample) 
    Sample_byclass{1,Train_label(i,1)+1} = [Sample_byclass{1,Train_label(i,1)+1}; Train_sample(i,:)];
    Prior_prob(1,Train_label(i,1)+1) = Prior_prob(1,Train_label(i,1)+1) + 1;
end
Prior_prob = Prior_prob/size(Train_sample,1);
for i=1:1:Class_num
     miu = mean(Sample_byclass{1,i});
     delta = std(Sample_byclass{1,i});   
     Para_mean{1,i} = miu;
     Para_dev{1,i} = delta;
end
predict = [];
for i=1:1:length(Test_sample)
     prob = log(Prior_prob);
     for j=1:1:Class_num
         for k=1:1:Feature_num
             if Para_dev{1,j}(1,k) == 0
                 Para_dev{1,j}(1,k) = 0.1667;
             end
             prob(1,j) = prob(1,j)   - (Test_sample(i,k)-Para_mean{1,j}(1,k))^2/(2*Para_dev{1,j}(1,k)^2)   - log(Para_dev{1,j}(1,k));
         end
     end
     [value index] = max(prob);
     predict = [predict ; index-1];
end
accuracy = length(find(predict - Test_label ==0))/length(Test_label);