三、基于概率论的分类方法：朴素贝叶斯1.概述

　　前两章的KNN分类算法和决策树分类算法最终都是预测出实例的确定的分类结果，但是，有时候分类器会产生错误结果；本章要学的朴素贝叶斯分类算法则是给出一个最优的猜测结果，同时给出猜测的概率估计值。利用已知值估计未知概率

• 优点：在数据较少的情况下仍然有效，可以处理多类别问题。
• 缺点：对于输入数据的准备方式较为敏感。
• 适用数据类型：标称型数据
  

2.算法介绍

• 训练算法：计算不同的独立特征的条件概率。
• 测试算法：计算错误率。
• 使用算法：一个常见的朴素贝叶斯应用是文档分类。可以在任意的分类场景中使_用朴素贝叶斯命类器，不一定非要是文本。输入数据分别属于哪个分类，最后应用对计算出的分类执行后续处理。
  

2.1 条件概率

[color=rgba(0, 0, 0, 0.75)]P(c|x)=P(c,x)P(x)=P(x|c)P(c)P(x)(1)(1)P(c|x)=P(c,x)P(x)=P(x|c)P(c)P(x)

2.2 如何使用条件概率进行分类

　　假设这里要被分类的类别有两类，类c1和类c2，那么我们需要计算概率p(c1|x,y)和p(c2|x,y)的大小并进行比较：

如果：p(c1|x,y)>p(c2|x,y),则(x,y)属于类c1

     p(c1|x,y)<p(c2|x,y),则(x,y)属于类c2

• 1
  

　　我们知道<span class="MathJax" id="MathJax-Element-6-Frame" tabindex="0" data-mathml="p(x,y|c)" role="presentation" style="overflow-wrap: normal; box-sizing: border-box; outline: 0px; display: inline; line-height: normal; text-align: left; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-; min-height: 0px; border: 0px; word-break: break-all; position: relative;">p(x,y|c)p(x,y|c)的条件概率所表示的含义为：已知类别c条件下，取到点(x，y)的概率；那么<span class="MathJax" id="MathJax-Element-7-Frame" tabindex="0" data-mathml="p(c|x,y)" role="presentation" style="overflow-wrap: normal; box-sizing: border-box; outline: 0px; display: inline; line-height: normal; text-align: left; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-; min-height: 0px; border: 0px; word-break: break-all; position: relative;">p(c|x,y)p(c|x,y)所要表达的含义呢？显然，我们同样可以按照条件概率的方法来对概率含义进行描述，即在给定点(x,y)的条件下，求该点属于类c的概率值。那么这样的概率该如何计算呢？显然，我们可以利用贝叶斯准则来进行变换计算：

[color=rgba(0, 0, 0, 0.75)]p(ci|x,y)=p(x,y|ci)p(ci)p(x,y)(2)(2)p(ci|x,y)=p(x,y|ci)p(ci)p(x,y)

[color=rgba(0, 0, 0, 0.75)]上述公式写为：

[color=rgba(0, 0, 0, 0.75)]p(ci|w⃗ )=p(w⃗ |ci)p(ci)p(w⃗ )(3)(3)p(ci|w→)=p(w→|ci)p(ci)p(w→)

3.伪代码

朴素贝叶斯完成文档分类依次执行以下操作：
计算每个类别文档的数目
计算每个类别占总文档数目的比例

• 对每一篇文档：
  　　- 对每一个类别：
  　　　　- 如果词条出现在文档中->增加该词条的计数值#统计每个类别中出现的词条的次数
  　　　　- 增加所有词条的计数值#统计每个类别的文档中出现的词条总数
  　　- 对每个类别：
  　　　　- 将各个词条出现的次数除以类别中出现的总词条数目得到条件概率
• 返回每个类别各个词条的条件概率和每个类别所占的比例
  

4.实例1、文档分类

• 针对算法的部分改进
  

1)计算概率时，需要计算多个概率的乘积以获得文档属于某个类别的概率，即计算p(w0|ci)p(w1|ci)…p(wN|ci)，然后当其中任意一项的值为0，那么最后的乘积也为0.为降低这种影响，采用拉普拉斯平滑，在分子上添加a(一般为1)，分母上添加ka(k表示类别总数)，即在这里将所有词的出现数初始化为1，并将分母初始化为2*1=2

2)解决下溢出问题
　　正如上面所述，由于有太多很小的数相乘。计算概率时，由于大部分因子都非常小，最后相乘的结果四舍五入为0,造成下溢出或者得不到准确的结果，所以，我们可以对成绩取自然对数，即求解对数似然概率。这样，可以避免下溢出或者浮点数舍入导致的错误。同时采用自然对数处理不会有任何损失。

3)上面也提到了关于如何选取文档特征的方法，上面用到的是词集模型，即对于一篇文档，将文档中是否出现某一词条作为特征，即特征只能为0不出现或者1出现；然后，一篇文档中词条的出现次数也可能具有重要的信息，于是我们可以采用词袋模型，在词袋向量中每个词可以出现多次，这样，在将文档转为向量时，每当遇到一个单词时，它会增加词向量中的对应值

2、过滤垃圾邮件

• 切分数据
  　　这样就得到了一系列词组成的词表，但是里面的空字符串还是需要去掉，此时我们可以通过字符的长度，去掉长度等于0的字符。并且，由于我们是统计某一词是否出现，不考虑其大小写，所有还可以将所有词转为小写字符，即lower(),相应的，转为大写字符为upper()
  　　此外，需要注意的是，由于是URL，因而可能会出现en和py这样的单词。当对URL进行切分时，会得到很多的词，因此在实现时也会过滤掉长度小于3的词。当然，也可以根据自己的实际需要来增加相应的文本解析函数。

• 交叉验证
  　　代码中，采用随机选择的方法从数据集中选择训练集，剩余的作为测试集。这种方法的好处是，可以进行多次随机选择，得到不同的训练集和测试集，从而得到多次不同的错误率，我们可以通过多次的迭代，求取平均错误率，这样就能得到更准确的错误率。这种方法称为留存交叉验证

  
  

3、朴素贝叶斯从个人广告中获取区域倾向

　　在本例中，我们通过从不同的城市的RSS源中获得的同类型广告信息，比较两个城市人们在广告用词上是否不同。如果不同，那么各自的常用词是哪些？而从人们的用词当中，我们能否对不同城市的人所关心的内容有所了解？如果能得到这些信息，分析过后，相信对于广告商而言具有不小的帮助。
　　需要说明的是，这里用到了将出现次数最多的30个单词删除的方法，结果发现去掉了这些最常出现的高频词后，错误率大幅度上升，这表明了文本中的小部分高频单词占据了文本中绝大部分的用词。产生这种情况的原因是因为语言中大部分是冗余和结果辅助性内容。所以，我们不仅可以尝试移除高频词的方法，还可以进一步从某个预定词表(停用词表)中移除结构上的辅助词，通过移除辅助性词，分类错误率会所有下降

此外，为了得到错误率的精确估计，应进行多次上述实验，从而得到错误率平均值。

• 1
  

5.存在的问题及解决方法

　　朴素贝叶斯在数据较少的情况下仍然适用，虽然例子中为两类类别的分析，但是朴素贝叶斯可以处理多分类的情况；朴素贝叶斯的一个不足的地方是，对输入的数据有一定的要求，需要花费一定的时间进行数据的处理和解析。朴素贝叶斯中用来计算的数据为标称型数据，我们需要将字符串特征转化为相应的离散值，用于后续的统计和计算。

===============================================================

四、Logistic回归1.概述

ogistic回归是一种简单的分类算法，利用logistic回归进行分类的主要思想是：根据现有数据对分类边界线建立回归公式，以此进行分类。
而“回归”也就意味着最佳拟合。要进行最佳拟合，则需要寻找到最佳的拟合参数，一些最优化方法就可以用于最佳回归系数的确定。

我们知道，logistic回归主要是进行二分类预测，也即是对于0~1之间的概率值，当概率大于0.5预测为1，小于0.5预测为0.显然，我们不能不提到一个函数，即<span class="MathJax" id="MathJax-Element-10-Frame" tabindex="0" data-mathml="sigmoid=11+e−z" role="presentation" style="overflow-wrap: normal; box-sizing: border-box; outline: 0px; display: inline; line-height: normal; text-align: left; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-; min-height: 0px; border: 0px; word-break: break-all; position: relative;">sigmoid=11+e−zsigmoid=11+e−z，该函数的曲线类似于一个s型，在x=0处，函数值为0.5.

• 优点：计算代价不高，易于理解和实现。
• 缺点：容易欠拟合，分类精度可能不高。 .
• 适用数据类型：数值型和标称型数据。
  

2.算法介绍

• 训练算法：大部分时间将用于训练，训练的目的是为了找到最佳的分类回归系数。
• 测试算法：一旦训练步驟完成，分类将会很快。
• 使用算法：首先，我们需要输入一些数据，并将其转换成对应的结构化数值；
  接着，基于训练好的回归系数就可以对这些数值进行简单的回归计算，判定它们属于哪个类别，在这之后，我们就可以夺输出的类别上做一些其他分析工作。
  

2.1 确定最佳回归系数

sigmoid函数的输入记为z，即

[color=rgba(0, 0, 0, 0.75)]z=w0x0+w1x1+w2x2+...+wnxn(1)(1)z=w0x0+w1x1+w2x2+...+wnxn

[color=rgba(0, 0, 0, 0.75)]记为：

[color=rgba(0, 0, 0, 0.75)]z=wTxz=wTx

[color=rgba(0, 0, 0, 0.75)]最优化方法有基于梯度的梯度下降法[color=rgba(0, 0, 0, 0.75)]、梯度上升法[color=rgba(0, 0, 0, 0.75)]，改进的随机梯度上升法[color=rgba(0, 0, 0, 0.75)]等等。基于梯度的优化方法在求解问题时，本身对要求解的问题有要求：即问题本身必须是可导的。其次，基于梯度的方法会使得待优化问题陷入局部最优。此时，一些启发式优化方法可以很好的解决这样的问题，但是启发式算法的求解速度较慢，占用内存较大。
[color=rgba(0, 0, 0, 0.75)](1)梯度上升[color=rgba(0, 0, 0, 0.75)]它的基本思想是：要找到某函数的最大值，最好的方法就是沿着该函数的梯度方向搜寻。如果函数为f，梯度记为D，a为步长，那么梯度上升法的迭代公式为：

[color=rgba(0, 0, 0, 0.75)]w：w+αΔwf(w)(3)(3)w：w+αΔwf(w)

[color=rgba(0, 0, 0, 0.75)](2)随机梯度上升法[color=rgba(0, 0, 0, 0.75)]我们知道梯度上升法每次更新回归系数都需要遍历整个数据集，当样本数量较小时，该方法尚可，但是当样本数据集非常大且特征非常多时，那么随机梯度下降法的计算复杂度就会特别高。一种改进的方法是一次仅用一个样本点来更新回归系数[color=rgba(0, 0, 0, 0.75)]。由于可以在新样本到来时对分类器进行增量式更新，因此随机梯度上升法是一个在线学习算法。
2.2 处理数据中的缺失值

我们可能会遇到数据缺失的情况，但有时候数据相当昂贵，扔掉和重新获取均不可取，这显然是会带来更多的成本负担，所以我们可以选取一些有效的方法来解决该类问题。比如：

　　1 使用可用特征的均值填补缺失值

　　2 使用特殊值来填补缺失的特征，如-1

　　3 忽略有缺失值的样本

　　4 使用相似样本的平均值填补缺失值

　　5 使用另外的机器学习算法预测缺失值

3.伪代码

使用梯度上升法寻找最佳参数
假设有100个样本点，每个样本有两个特征：x1和x2.此外为方便考虑，我们额外添加一个x0=1，将线性函数z=wTx+b转为z=wTx(此时向量w和x的维度均价

1).那么梯度上升法的伪代码如下：

• 初始化每个回归系数为1
• 重复R次：
  　　- 计算整个数据集梯度
  　　- 使用alpha*gradient更新回归系数的向量
• 返回回归系数
  

2)随机梯度上升法可以写成如下伪代码：

• 所有回归系数初始化为1
• 对数据集每个样本
  　　- 计算该样本的梯度
  　　- 使用alpha*gradient更新回顾系数值
• 返回回归系数值
  

4.实例1、从疝气病症预测病马死亡率

• 处理数据缺失：
  这里我们根据logstic回归的函数特征，选择实数0来替换所有缺失值，而这恰好能适用logistic回归。因此，它在参数更新时不会影响参数的值。即如果某特征对应值为0 ，那么由公式w：w+alpha*gradient，可知w不会发生改变。

  　　此外，由于sigmoid(0)=0.5,表面该特征对结果的预测不具有任何倾向性，因此不会对误差造成影响。

  　　当然，如果是发生有样本的类标签缺失的情况，此时我们最好的办法是将该样本舍弃，这是因为标签与特征不同，我们很难确定采用某个合适的值替换掉。