一. 生成式（generative）学习算法

如果算法直接学习\\(p(y|x)\\)，或者尝试学习从输入空间\\(X\\)到类别\\(\\{0,1\\}\\)的映射关系的算法，称为判别式（discriminative）学习算法；比线性回归（lineaar regression）的模型：
\\[f(y|x;\\theta) = h_{\\theta}(x) + \\theta_{0} + \\theta_{1}x_1 + \\theta_{2}x_2 + … + \\theta_{n}x_n\\]

再比如逻辑回归（logistic regression）:
\\[f(y|x;\\theta) = h_{\\theta}(x) = g(\\theta^{T}x) = \\frac{1}{1+e^{-\\theta^{T}x}} \\]
这里的\\(g\\)是sigmoid函数

而另外一种算法是建立\\(p(x|y)\\)（和\\(p(y)\\)）的模型，这类算法称为生成式（generative）学习算法，我们今天要讨论的朴素贝叶斯算法即是其中一个。对\\(p(y)\\)（先验 prior）和\\(p(x|y)\\)，使用贝叶斯规则来推导给定\\(x\\)的\\(y\\)的后验（posterior）分布：

\\[p(y|x) = \\frac{p(x|y)p(y)}{p(x)}\\]

其中分母可由全概率公式计算：

\\[p(x) = p(x|y=1)p(y=1) + p(x|y=0)p(y=0)\\]

实际上，我们在计算\\(p(y|x)\\)做预测时，可以不用计算分母\\(p(x)\\)，因为：
\\[arg \\ \\max \\limits_{y} \\ p(y|x) = arg \\ \\max \\limits_{y} \\ \\frac{p(x|y)p(y)}{p(x)} = arg \\ \\max \\limits_{y} \\ p(x|y)p(y)\\]

二. 朴素贝叶斯（Naive Bayes）

2.1 朴素贝叶斯算法

假设我们想利用机器学习来构建一个言论过滤器，希望对网站的留言评论自动区分是侮辱性言论，还是非侮辱性言论。现在已知一个训练数据集（一些已经标记为侮辱或者非侮辱的言论集合）如下：

\"\"\"函数说明:创建实验样本Parameters:无Returns:postingList - 实验样本切分的词条classVec - 类别标签向量\"\"\"def loadDataSet():postingList = [[\'my\', \'dog\', \'has\', \'flea\', \'problems\', \'help\', \'please\'],          # 切分的词条[\'maybe\', \'not\', \'take\', \'him\', \'to\', \'dog\', \'park\', \'stupid\'],[\'my\', \'dalmation\', \'is\', \'so\', \'cute\', \'I\', \'love\', \'him\'],[\'stop\', \'posting\', \'stupid\', \'worthless\', \'garbage\'],[\'mr\', \'licks\', \'ate\', \'my\', \'steak\', \'how\', \'to\', \'stop\', \'him\'],[\'quit\', \'buying\', \'worthless\', \'dog\', \'food\', \'stupid\']]classVec = [0, 1, 0, 1, 0, 1]           # 对应postingList中每个样本的类别标签向量，1代表侮辱性言论， 0代表非侮辱性言论return postingList, classVec

[/code]

令 \\(y\\) 表示该言论是否是侮辱性言论：
\\[y =\\begin{cases}1 & \\mbox{侮辱性言论} \\\\0 & \\mbox{非侮辱性言论}\\end{cases}\\]
接下来，我们将样本数据，即postingList，转化成特征向量，用 \\(x\\) 表示，其中包含单词特征：
\\[x_j =\\begin{cases}1 & \\mbox{第 $j$ 个单词出现} \\\\0 & \\mbox{未出现}\\end{cases}\\]
编码到向量中的单词的集合称为词汇表，例如“ my”，“stupid”等等，向量\\(x\\)的长度等于词汇表的长度。

注意，这里的词汇表不是将英语词典中单词全部列出来，通常是将训练数据集中的所有单词，即使仅出现过一次，放到词汇表中。这样做可以减少模型的词汇数量，从而减少计算量，节省空间；还有个好处是能够将英语词典中不会出现的词，但会出现在留言评论中的词，比如“\\(2233\\)”放到词汇表中；同时还需要剔除一些高频词，比如 “\\(the\\)” “\\(of\\)” “\\(and\\)”，这些词在很多的文本中都会出现，对区分是否是侮辱性言论没有任何帮助。

特征向量\\(x\\)与词汇表如下图所示，言论中包含“\\(a\\)”，“buy”，不包含“aardvard”，“aardwolf”，“zygmurgy”：

创建词汇表代码如下：

\"\"\"函数说明:将切分的实验样本词条整理成不重复的词条列表，也就是词汇表Parameters:dataSet - 样本数据集 postingListReturns:vocabSet - 返回不重复的词条列表，也就是词汇表\"\"\"def createVocabList(dataSet):vocabSet = set([])for document in dataSet:vocabSet = vocabSet | set(document)return list(vocabSet)

[/code]

将样本数据转换成特征向量\\(x\\)代码如下：

\"\"\"函数说明:根据vocabList词汇表，将inputSet向量化，向量的每个元素为1或0Parameters:vocabList - 词汇表inputSet - 某条言论文档Returns:returnVec - 言论文档向量\"\"\"def setOfWords2Vec(vocabList, inputSet):returnVec = [0] * len(vocabList)            # 创建一个其中所含元素都为0的向量for word in inputSet:                       # 遍历每个词条if word in vocabList:                   # 如果词条存在于词汇表中，则置1returnVec[vocabList.index(word)] = 1else:print(\"the word: %s is not in my vocabulary !\" % word)return returnVec

[/code]

现在我们来构建\\(p(x|y)\\)。上面代码示例中词汇表中单词较少，但如果词汇表中包含50000个单词，那么\\(x \\in \\{0, 1\\rbrace^{50000}\\)（\\(x\\)是50000维0和1组成的向量），如果我们直接用多项式来构造\\(x\\)的\\(2^{50000}\\)个可能的结果，那么多项式的参数向量有\\(2^{50000} - 1\\)维，显然参数太多了。

因此算法做了一个强假设，即假设给定\\(y\\)的情况下\\(x_j\\)条件独立，这个假设就称为朴素贝叶斯假设，算法称为朴素贝叶斯分类。例如，如果\\(y=1\\)表示侮辱性言论，“\\(stupid\\)”是第\\(2087\\)个单词，“$worthless $”是第\\(39831\\)个单词，那么我们假设如果已知\\(y=1\\)，那么\\(x_{2087}\\)的值（“\\(stupid\\)”是否出现在言论中） 对\\(x_{39831}\\)的值（“$worthless \\(”是否出现在言论中）没有任何影响。正式一点来描述，上述可以写成\\)p(x_{2087}|y) = p(x_{2087}|y,x_{39831})\\(。需要注意的是，这里并不是说\\)x_{2087}\\(和\\)x_{39831}\\(相互独立，相互独立表示为\\)p(x_{2087}) = p(x_{2087}|x_{39831})\\(，而是仅假设\\)x_{2087}\\(和\\)x_{39831}\\(在给定\\)y$的情况下条件独立。根据上述假设，有如下等式成立：
\\[\\begin{eqnarray}p(x_1,...,x_{50000}|y) \\\\ &=& p(x_1|y)p(x_2|y,x_1)p(x_3|y,x_1,x_2)...p(x_{50000}|y,x1,...,x_{49999}) \\\\&=& p(x_1|y)p(x_2|y)p(x_3|y)...p(x_{50000}|y) \\\\&=& \\prod_{j=1}^{n} p(x_j|y)\\end{eqnarray}\\]
第一个等式是概率的基本性质，第二个等式用了朴素贝叶斯假设。

我们的模型中的参数为\\(\\phi_{j|y=1} = p(x_j = 1|y = 1)\\)，\\(\\phi_{j|y=0} = p(x_j = 1|y = 0)\\)和\\(\\phi_{y} = p(y = 1)\\)，其中\\(j\\)为词汇表中第\\(j\\)个单词。给定一个训练数据集$\\lbrace (x^{(i)}, y^{(i)}); i=1,...,m\\rbrace $，我们可以写出似然函数：

\\[L(\\phi_y, \\phi_{j|y=0}, \\phi_{j|y=1}) = \\prod_{i=1}^{m} p(x^{ ( i )}, y^{ ( i )})\\]

最大化关于参数\\(\\phi_y\\), \\(\\phi_{j|y=0}\\), \\(\\phi_{j|y=1}\\)的上述似然函数，得到第\\(j\\)个单词相关参数的极大似然估计：

\\[\\phi_{j|y=1} = \\frac{\\sum_{i=1}^{m} 1 \\{ x_j^{(i)} = 1 \\land y^{(i)} = 1 \\rbrace }{\\sum_{i=1}^{m} 1 \\{ y^{(i)} = 1 \\rbrace } \\]
$\\phi_{j|y=1} \\(即是对\\)p(x_j|y=1)$的估计；

\\[\\phi_{j|y=0} = \\frac{\\sum_{i=1}^{m} 1 \\{ x_j^{(i)} = 1 \\land y^{(i)} = 0 \\rbrace }{\\sum_{i=1}^{m} 1 \\{ y^{(i)} = 0 \\rbrace }\\]
$\\phi_{j|y=0} \\(即是对\\)p(x_j|y=0)$的估计；

\\[\\phi_{y=1} = \\frac{\\sum_{i=1}^{m} 1 \\{ y^{(i)} = 1 \\rbrace }{m}\\]
\\(\\phi_{y=1}\\)即是对\\(p(y=1)\\)的估计；同理
\\[\\phi_{y=0} = \\frac{\\sum_{i=1}^{m} 1 \\{ y^{(i)} = 0 \\rbrace }{m}\\]
\\(\\phi_{y=0}\\)即是对\\(p(y=0)\\)的估计；参数表达式中的 $ \\land \\(表示“与”。上面的参数不难理解，\\)\\phi_{j|y=1}\\(就是侮辱性言论（\\)y=1\\(）中单词\\)j$出现的百分比。训练阶段代码如下：

\"\"\"函数说明:朴素贝叶斯分类器训练函数Parameters:trainMatrix - 训练文档矩阵，即setOfWords2Vec返回的returnVec构成的矩阵trainCategory - 训练类别标签向量，即loadDataSet返回的classVecReturns:p0Vect - 非侮辱类的条件概率数组p1Vect - 侮辱类的条件概率数组pAbusive - 文档属于侮辱类的概率\"\"\"def trainNB0(trainMatrix, trainCategory):numTrainDocs = len(trainMatrix)         #计算训练的文档数目numWords = len(trainMatrix[0])          #计算每篇文档的词条数pAbusive = sum(trainCategory)/float(numTrainDocs)  #文档属于侮辱类的概率p0Num = np.zeros(numWords)              #创建numpy.zeros数组,词条出现数初始化为0p1Num = np.zeros(numWords)p0Denom = 0.0                           #分母初始化为0p1Denom = 0.0for i in range(numTrainDocs):if trainCategory[i] == 1:           #向量相加，统计属于侮辱类的条件概率所需的数据，即P(w0|1),P(w1|1),P(w2|1)···p1Num += trainMatrix[i]p1Denom += sum(trainMatrix[i])else:                               #向量相加，统计属于非侮辱类的条件概率所需的数据，即P(w0|0),P(w1|0),P(w2|0)···p0Num += trainMatrix[i]p0Denom += sum(trainMatrix[i])p1Vect = p1Num/p1Denomp0Vect = p0Num/p0Denomreturn p0Vect, p1Vect, pAbusive         #返回属于侮辱类的条件概率数组，属于非侮辱类的条件概率数组，文档属于侮辱类的概率

[/code]

已知参数估计之后，对一个特征向量\\(x\\)的新样本计算是侮辱性言论的概率如下：
\\[\\begin{eqnarray}p(y=1|x) &=& \\frac{p(x|y)p(y=1)} {p(x)} \\\\&=& \\frac{(\\prod_{j=1}^{n} p(x_j | y=1))p(y=1)} {(\\prod_{j=1}^{n} p(x_j | y= 1))p(y=1) + (\\prod_{j=1}^{n} p(x_j | y= 0))p(y=0)}\\end{eqnarray} \\]
同样，计算非侮辱性言论的概率如下：
\\[\\begin{eqnarray}p(y=0|x) &=& \\frac{p(x|y)p(y=0)} {p(x)} \\\\&=& \\frac{(\\prod_{j=1}^{n} p(x_j | y=0))p(y=0)} {(\\prod_{j=1}^{n} p(x_j | y= 1))p(y=1) + (\\prod_{j=1}^{n} p(x_j | y= 0))p(y=0)}\\end{eqnarray}\\]
如果计算得出$p(y=1|x) > p(y=0|x) $，则认为言论是侮辱性言论，反之是非侮辱性言论，预测代码如下：

\"\"\"函数说明:朴素贝叶斯分类器分类函数Parameters:vec2Classify - 待分类的词条数组p0Vec - 侮辱类的条件概率数组p1Vec -非侮辱类的条件概率数组pClass1 - 文档属于侮辱类的概率Returns:0 - 属于非侮辱类1 - 属于侮辱类\"\"\"def classifyNB0(vec2Classify, p0Vec, p1Vec, pClass1):p1 = reduce(lambda x,y : x * y, vec2Classify * p1Vec) * pClass1             # 对应元素相乘p0 = reduce(lambda x,y : x * y, vec2Classify * p0Vec) * (1 - pClass1)print(\'p0:\', p0)print(\'p1\', p1)if p1 > p0:return p1else:return p0

[/code]

2.2 下溢出与拉普拉斯平滑

2.1节中我们使用朴素贝叶斯算法构造了言论分类器，下面我们对算法进行测试：

\"\"\"函数说明:测试朴素贝叶斯分类器Parameters:无Returns:无\"\"\"def testingNB0():listOPosts, classVec = loadDataSet()  # 创建实验样本myVocabList = createVocabList(listOPosts)  # 创建词汇表# 打印中间结果print(\'myVocabList:\\n\', myVocabList)trainMat = []for postinDoc in listOPosts:trainMat.append(setOfWords2Vec(myVocabList, postinDoc))  # 将实验样本向量化p0V, p1V, pAb = trainNB0(np.array(trainMat), np.array(classVec))  # 训练朴素贝叶斯分类器# 打印中间结果print(\'p0V:\\n\', p0V)print(\'p1V:\\n\', p1V)print(\'classVec:\\n\', classVec)print(\'pAb:\\n\', pAb)testEntry = [\'love\', \'my\', \'dalmation\']  # 测试样本1thisDoc = np.array(setOfWords2Vec(myVocabList, testEntry))  # 测试样本向量化if classifyNB0(thisDoc, p0V, p1V, pAb):print(testEntry, \'属于侮辱类\')  # 执行分类并打印分类结果else:print(testEntry, \'属于非侮辱类\')  # 执行分类并打印分类结果testEntry = [\'stupid\', \'garbage\']  # 测试样本2thisDoc = np.array(setOfWords2Vec(myVocabList, testEntry))  # 测试样本向量化if classifyNB0(thisDoc, p0V, p1V, pAb):print(testEntry, \'属于侮辱类\')  # 执行分类并打印分类结果else:print(testEntry, \'属于非侮辱类\')  # 执行分类并打印分类结果if __name__ == \"__main__\":testingNB0()

[/code]

运行结果截图如下：

小伙伴们，发现问题了吗？显然这个结果是不对的。算法存在两个问题：

• 某些单词0概率，导致整体乘积为0，例如“\\(stupid\\)”；
• 下溢出（underflow）：

对于第一个问题，我们通过打印中间结果可以看出：

又或者对一个训练数据集中未出现的词，概率也是0，显然，这样是不合理的，因为训练集有限，不能因为训练集中没有出现，就认为这个词永远不会出现。记得吴恩达老师在机器学习课上讲了个段子，斯坦福大学的校篮球队接连输了5场比赛，问下一场比赛赢的概率?？连输5场，下一场肯定输吗？合理的预测是有赢的概率，只是比较小，设置赢的概率为1/7吧?。这种做法就叫做拉普拉斯平滑(Laplace Smoothing)。具体做法是修改极大似然估计的参数：

\\[\\phi_{j|y=1} = \\frac{\\sum_{i=1}^{m} 1 \\{ x_j^{(i)} = 1 \\land y^{(i)} = 1 \\rbrace + 1}{\\sum_{i=1}^{m} 1 \\{ y^{(i)} = 1 \\rbrace + k} \\]
$\\phi_{j|y=1} \\(即是对\\)p(x_j|y=1)$的估计；

\\[\\phi_{j|y=0} = \\frac{\\sum_{i=1}^{m} 1 \\{ x_j^{(i)} = 1 \\land y^{(i)} = 0 \\rbrace + 1 }{\\sum_{i=1}^{m} 1 \\{ y^{(i)} = 0 \\rbrace + k}\\]
$\\phi_{j|y=0} \\(即是对\\)p(x_j|y=0)$的估计。

其中\\(k\\)代表\\(y\\)的可能取值数量，我们的例子中\\(y\\)的取值只有\\(0\\)和\\(1\\)两种，因此\\(k=2\\)。
那么为什么分子加\\(1\\)，分母加\\(k\\)呢？因为要保证\\(\\phi_j\\)相加仍然是\\(1\\)。下面我们检验一下，假设随机变量\\(z\\)的取值有\\(k\\)个
\\[\\phi_{j} = \\frac{\\sum_{i=1}^{m} 1 \\{z_i = j\\rbrace}{m} \\]
其中\\(\\sum_{j=0}^{k} \\phi_j = 1\\)，则应用拉普拉斯平滑之后

\\[\\phi_{j}^{\'} = \\frac{\\sum_{i=1}^{m} 1 \\{z_i = j\\rbrace + 1}{m+ k} \\]
不难推出\\(\\sum_{j=0}^{k} \\phi_{j}^{\'} = 1\\)

除此之外，另外一个遇到的问题就是下溢出，这是由于太多很小的数相乘造成的。学过数学的人都知道，两个小数相乘，越乘越小，这样就造成了下溢出。在程序中，在相应小数位置进行四舍五入，计算结果可能就变成0了。为了解决这个问题，对乘积结果取自然对数。通过求对数可以避免下溢出或者浮点数舍入导致的错误。同时，采用自然对数进行处理不会有任何损失。下图给出函数f(x)和ln(f(x))的曲线：

检查这两条曲线，就会发现它们在相同区域内同时增加或者减少，并且在相同点上取到极值。它们的取值虽然不同，但不影响最终结果。因此我们可以对上篇文章的trainNB0(trainMatrix, trainCategory)函数进行更改，修改如下：

\"\"\"函数说明:朴素贝叶斯分类器训练函数Parameters:trainMatrix - 训练文档矩阵，即setOfWords2Vec返回的returnVec构成的矩阵trainCategory - 训练类别标签向量，即loadDataSet返回的classVecReturns:p0Vect - 非侮辱类的条件概率数组p1Vect - 侮辱类的条件概率数组pAbusive - 文档属于侮辱类的概率\"\"\"def trainNB(trainMatrix, trainCategory):numTrainDocs = len(trainMatrix)         # 计算训练的文档数目numWords = len(trainMatrix[0])          # 计算每篇文档的词条数pAbusive = sum(trainCategory) / float(numTrainDocs)  # 文档属于侮辱类的概率p0Num = np.ones(numWords)p1Num = np.ones(numWords)               # 创建numpy.ones数组,词条出现数初始化为1，拉普拉斯平滑p0Denom = 2.0p1Denom = 2.0                           # 分母初始化为2,拉普拉斯平滑for i in range(numTrainDocs):if trainCategory[i] == 1:           # 向量相加，统计属于侮辱类的条件概率所需的数据，，即P(w0|1),P(w1|1),P(w2|1)···p1Num += trainMatrix[i]p1Denom += sum(trainMatrix[i])else:                               # 向量相加，统计属于非侮辱类的条件概率所需的数据，即P(w0|0),P(w1|0),P(w2|0)···p0Num += trainMatrix[i]p0Denom += sum(trainMatrix[i])p1Vect = np.log(p1Num / p1Denom)        # 取对数，防止下溢出p0Vect = np.log(p0Num / p0Denom)return p0Vect, p1Vect, pAbusive         # 返回属于侮辱类的条件概率数组，属于非侮辱类的条件概率数组，文档属于侮辱类的概率\"\"\"函数说明:朴素贝叶斯分类器分类函数Parameters:vec2Classify - 待分类的词条数组p0Vec - 非侮辱类的条件概率数组p1Vec -侮辱类的条件概率数组pClass1 - 文档属于侮辱类的概率Returns:0 - 属于非侮辱类1 - 属于侮辱类\"\"\"def classifyNB(vec2Classify, p0Vec, p1Vec, pClass1):p1 = sum(vec2Classify * p1Vec) + np.log(pClass1)  # 对应元素相乘。logA * B = logA + logB，所以这里加上log(pClass1)p0 = sum(vec2Classify * p0Vec) + np.log(1.0 - pClass1)if p1 > p0:return 1else:return 0\"\"\"函数说明:测试朴素贝叶斯分类器Parameters:无Returns:无\"\"\"def testingNB():listOPosts, classVec = loadDataSet()  # 创建实验样本myVocabList = createVocabList(listOPosts)  # 创建词汇表# 打印中间结果print(\'myVocabList:\\n\', myVocabList)trainMat = []for postinDoc in listOPosts:trainMat.append(setOfWords2Vec(myVocabList, postinDoc))  # 将实验样本向量化p0V, p1V, pAb = trainNB(np.array(trainMat), np.array(classVec))  # 训练朴素贝叶斯分类器# 打印中间结果print(\'p0V:\\n\', p0V)print(\'p1V:\\n\', p1V)print(\'classVec:\\n\', classVec)print(\'pAb:\\n\', pAb)testEntry = [\'love\', \'my\', \'dalmation\']  # 测试样本1thisDoc = np.array(setOfWords2Vec(myVocabList, testEntry))  # 测试样本向量化if classifyNB(thisDoc, p0V, p1V, pAb):print(testEntry, \'属于侮辱类\')  # 执行分类并打印分类结果else:print(testEntry, \'属于非侮辱类\')  # 执行分类并打印分类结果testEntry = [\'stupid\', \'garbage\']  # 测试样本2thisDoc = np.array(setOfWords2Vec(myVocabList, testEntry))  # 测试样本向量化if classifyNB(thisDoc, p0V, p1V, pAb):print(testEntry, \'属于侮辱类\')  # 执行分类并打印分类结果else:print(testEntry, \'属于非侮辱类\')  # 执行分类并打印分类结果if __name__ == \"__main__\":testingNB()

[/code]

运行结果如下：

Reference

1. Naive_Bayes_classifier wiki
2. Gaussian Discriminant Analysis an example of Generative Learning Algorithms
3. cs229 lecture notes Part IV Generative Learning algorithms
4. Machine Learning in Action
5. [Jack Cui 机器学习实战教程（四）：朴素贝叶斯基础篇之言论过滤器](

转载于:https://www.cnblogs.com/withwhom/p/11624073.html