首页 > 代码库 > 朴素贝叶斯
朴素贝叶斯
朴素贝叶斯（Normal Bayes）适用于离散型特征的分类问题。
相比于KNN的纯暴力，决策树的降维以求减少比较次数的优化，NB的优势在于，训练完成之后，分类测试的效率非常高。
设样本数为n，分类数据为m
KNN没有训练过程，需要分类的时候，即时确定分类。总复杂度O（mn^2)
决策树虽然有训练过程，但是是将样本和待分类数据一同拉入树中分类，复杂度估测O（（n+m）^2*log(n+m))
NB则是先训练样本，复杂度O（n^2)，分类时，对于每个数据，for同时比较所有分类的各个维度，计算p(w|ci)，复杂度O（d)，总复杂度O（n^2+d)
所以在样本庞大时，NB很有优势，毕竟你总不能每次分类时还处理一下庞大的文本样本吧，提前训练一下，做个预处理，减少分类时的压力。
值得一提的是，NB假设各个特征是相对独立的，而且不能有什么上下文关联（和马科夫链完全不是一个概念）。
所以不要拿NB做文本识别什么的，因为NB会认为“我爱你”、“你爱我”这两个数据是相同的，实际上是不同的。
NB最常见的是用于文本内容的分类（不涉及上下文），此时维度d由总词典单词数确定，这是特例。
对于普通的离散型数据特征，分类比较的维度就是特征维度了，也没必要造词典了。
比如收集你喜欢的妹子和不喜欢的妹子的各个特征来训练，然后对于一个新交往的妹子，你就可以预测会不会喜欢她了。
————————————————————————————————————————————————————————————
NB的思路其实不是很复杂（以文本类NB说明，以下的代码确定一个0/1分类)
NB的分类公式P（ci|W）=P（W|ci）*P（ci）/P（W），ci指的是分类。
首先无视掉最后除的P(W)，因为P(W)由样本决定，对于所有分类数据P（W）都是一样的。
那么只要看P（W|ci）*P（ci）就行了。
P（ci）=样本中属于这个分类数/总样本数，这个也很好算。
P（W|ci）是重点，NB有个奇怪的假设就是所有特征是独立的，所以P（W|ci）=P（w1，w2，....wn|ci）=P（w1|ci）*P（w2|ci）...P（wn|ci）
P（w1|ci）=所有属于ci的样本在第1维度的累计值/在所有维度的累计值，这里处理条件概率的方式比较特别，其实就是分类累加，然后除一下就有概率了。
目测n=20时，精度就爆了，所以对X=P（W|ci）*P（ci）处理一下，取对数log再比较，变成logX=P（w1|ci）+P（w2|ci）+....P（wn|ci）+P（ci）
①读入数据，使用map造词典vocabList， 同时map存下每条样本的各个单词出现次数
②计算训练矩阵trainVec[n][m]
对于词典中的每个词i
如果j词条中存在这个词，则trainVec[j][i]=1 or cnt （这里有两个模型，词集模型的每个词只能出现一起所以为1,词袋模型中每个词可以出现多次，所以①中的次数就有用了）
不存在则trainVec[j][i]=0
③为两个分类累加各个维度的值，形成两个向量p0，p1，并统计该分类的总值p0Sum，p1Sum
该步需要做一下处理，就是如果某个维度的累加值最后是0，那么算P（w1|ci）*P（w2|ci）...P（wn|ci），最后就会变成0了，然后就是log（0），完蛋啦。
所以p0、p1的各个维度初始值设为1，那么p0Sum=p1Sum=维度大小，这样既保证每个分类算出的概率和为1，又能避免出现0问题。
④p0/p0Sum得到最后用于分类的p0Vec向量，p1同样处理。
⑤分类，计算P0，P1。方法是扫一遍词典，如果当前词在这个词汇中存在，则P0+=出现次数*p0Vec[i], P1+=出现次数*p1Vec[i]
由于p0Vec，p1Vec记录的是样本生成的多个维度的权，所以P0、P1因为各个维度的权不同，导致大小不同，谁大谁的分类就越有可能。
#include "cstdio"#include "vector"#include "string"#include "iostream"#include "map"#include "math.h"using namespace std;#define maxn 10005int n,tmp,p0Sum,p1Sum,cnt;string line,word;vector<string> wordVec[maxn];vector<int> classVec,trainVec[maxn],v0,v1;map<string,int> vocabList,wordHash[maxn];vector<double> p0Vec,p1Vec;void initProcess(){ cin>>n;getchar(); for(int i=0; i<n; i++) { getline(cin,line); word.clear(); tmp=0; for(int j=0; j<line.size(); j++) { if(line[j]==‘ ‘) { wordHash[i][word]++; vocabList[word]++; word.clear(); tmp=j+1; } else word.push_back(line[j]); } if(tmp!=line.size()) { vocabList[word]++; wordHash[i][word]++; } } for(int i=0;i<n;i++) {cin>>tmp;classVec.push_back(tmp);if(tmp) cnt++;} for(map<string,int>::iterator i=vocabList.begin(); i!=vocabList.end(); i++) for(int j=0; j<n; j++) if(wordHash[j].count(i->first)) trainVec[j].push_back(wordHash[j][i->first]); //model:bag?set else trainVec[j].push_back(0); v0=vector<int>(vocabList.size(),1),p0Vec.resize(vocabList.size()); v1=vector<int>(vocabList.size(),1),p1Vec.resize(vocabList.size()); p0Sum=p1Sum=vocabList.size(); //fixed for(int i=0; i<n; i++) { if(classVec[i]==0) { for(int j=0; j<trainVec[i].size(); j++) { v0[j]+=trainVec[i][j]; if(trainVec[i][j]==1) p0Sum++; } } else { for(int j=0; j<trainVec[i].size(); j++) { v1[j]+=trainVec[i][j]; if(trainVec[i][j]==1) p1Sum++; } } } for(int i=0; i<p0Vec.size(); i++) {p0Vec[i]=log((double)v0[i]/p0Sum);p1Vec[i]=log((double)v1[i]/p1Sum);}}int classify(vector<string> sample){ map<string,int> tt; for(int i=0;i<sample.size();i++) tt[sample[i]]++; double p0=0.0,p1=0.0; int pos=0; for(map<string,int>::iterator i=vocabList.begin();i!=vocabList.end();i++) { if(tt.count(i->first)) { p0+=p0Vec[pos]; p1+=p1Vec[pos]; } pos++; } p1+=log((double)cnt/n); p0+=log(1-(double)cnt/n); if(p0>p1) return 0; else return 1;}int main(){ freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); initProcess();getchar(); while(getline(cin,line)) { tmp=0; word.clear(); vector<string> sample; for(int j=0; j<line.size(); j++) { if(line[j]==‘ ‘) { sample.push_back(word); word.clear(); tmp=j+1; } else word.push_back(line[j]); } if(tmp!=line.size()) sample.push_back(word); cout<<"sample: "; for(int i=0; i<sample.size(); i++) cout<<sample[i]<<" "; cout<<endl; int x=classify(sample); cout<<"class: "<<x<<endl; }}
朴素贝叶斯