分类在机器学习中的应用非常重要，因为计算机其实无法深层次地理解文字图片目标的意思，只能回答是或者不是。所以让计算机知道数据的含义是很重要的。今天我们一起来看看机器学习中常用的分类算法。

朴素贝叶斯

说到朴素贝叶斯，先说一下贝叶斯定理，首先要解释的就是条件概率，非常简单，表示事件B发生的情况下，事件A发生的概率

贝叶斯定理之所以有用，是因为我们在生活中经常遇到这种情况：我们可以很容易直接得出，则很难直接得出，但我们更关心，贝叶斯定理就为我们打通从获得的道路。

直接给出贝叶斯定理：

朴素贝叶斯的原理和流程

先通俗地解释一下原理，对于给出的待分类项，求解在此项出现的条件下各个类别出现的概率，哪个最大，就认为此待分类项属于哪个类别。

朴素贝叶斯的定义如下：

1.设x={a1,a2,a3,a4,a5,….,am}为一个代分类项，而每个a为x的一个属性

2.类别集合C={y1,y2,y3,y4,…,yn}

3.计算

4.如果那么x就属于

这些过程都非常简单，现在就需要计算第三步的各个条件概率，这其实也是一个训练过程

1.找到一个训练样本，也就是一个已知分类的待分类项集合

2.统计计算在各个类别下各个特征属性的条件概率估计

3.如果各个特征属性是条件独立的，根据贝叶斯定理

因为P(x)是常数，所以我们只需要计算

特征值是连续的情况的条件概率

整个朴素贝叶斯的分类过程中，计算是一个关键一步，当特征属性为离散值时，只要很方便的统计训练样本中各个划分在每个类别中出现的频率即可用来估计，下面重点讨论特征属性是连续值的情况。

当特征属性为连续值时，通常假定其值服从高斯分布（也称正态分布）。因此只要计算出训练样本中各个类别中此特征项划分的各均值和标准差，就可以得到相应的概率。

另一个需要讨论的问题就是当怎么办，当某个类别下某个特征项划分没有出现时，就是产生这种现象，这会令分类器质量大大降低。为了解决这个问题，我们引入Laplace校准，它的思想非常简单，就是对没类别（概率为0的类别）下所有划分的计数加1，这样如果训练样本集数量充分大时，并不会对结果产生影响，并且解决了上述频率为0的尴尬局面。

朴素贝叶斯的优缺点

朴素贝叶斯的优点：对小规模的数据表现很好，适合多分类任务，适合增量式训练。
朴素贝叶斯的缺点：对输入数据的表达形式很敏感。

决策树

决策树（decision tree）是一个树结构（可以是二叉树或非二叉树）。其每个非叶节点表示一个特征属性上的测试，每个分支代表这个特征属性在某个值域上的输出，而每个叶节点存放一个类别。使用决策树进行决策的过程就是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果。

决策数有两大优点：1）决策树模型可以读性好，具有描述性，有助于人工分析；2）效率高，决策树只需要一次构建，反复使用，每一次预测的最大计算次数不超过决策树的深度。

对于决策树算法我准备单独写一篇博客来说明一下。

Logistic Regression(LR)

Logistic Regression别看它名字里带了回归，但是它其实是一种分类的方法，用于两分类的问题。

基本原理

找一个合适的预测函数（Andrew Ng的公开课中称为hypothesis），一般表示为h函数，该函数就是我们需要找的分类函数，它用来预测输入数据的判断结果。这个过程是非常关键的，需要对数据有一定的了解或分析，知道或者猜测预测函数的“大概”形式，比如是线性函数还是非线性函数。
构造一个Cost函数（损失函数），该函数表示预测的输出（h）与训练数据类别（y）之间的偏差，可以是二者之间的差（h-y）或者是其他的形式。综合考虑所有训练数据的“损失”，将Cost求和或者求平均，记为J(θ)函数，表示所有训练数据预测值与实际类别的偏差。
显然，J(θ)函数的值越小表示预测函数越准确（即h函数越准确），所以这一步需要做的是找到J(θ)函数的最小值。找函数的最小值有不同的方法，Logistic Regression实现时有的是梯度下降法（Gradient Descent）。

过程详解

1.既然这种分类方法就叫Logistic Regression，那么Logistic肯定是一个重要的东西，没错有个函数就叫Logistic函数（也叫Sigmoid函数）

它的导数形式

2.Logistic回归方法是用最大似然估计来进行学习的，单个样本的后验概率是

那么整个样本的后验概率

再进行求对数

上面求得的就是cost function，要求它的最小值可以用梯度下降法，对l(θ)求微分，可得

Logistic Regression的优缺点

Logistic回归优点：1、实现简单；2、分类时计算量非常小，速度很快，存储资源低；
缺点：1、容易欠拟合，一般准确度不太高；2、只能处理两分类问题（在此基础上衍生出来的softmax可以用于多分类），且必须线性可分；

KNN算法

K Nearest Neighbor算法，又称K近邻算法。

1.计算训练样本和测试样本中每个样本点的距离（常见的距离度量有欧式距离，马氏距离等）；

2.对上面所有的距离值进行排序；

3.选前k个最小距离的样本；

4.根据这k个样本的标签进行投票，得到最后的分类类别；

如何选择一个最佳的K值，这取决于数据。一般情况下，在分类时较大的K值能够减小噪声的影响。但会使类别之间的界限变得模糊。一个较好的K值可通过各种启发式技术来获取，比如，交叉验证。另外噪声和非相关性特征向量的存在会使K近邻算法的准确性减小。

近邻算法具有较强的一致性结果。随着数据趋于无限，算法保证错误率不会超过贝叶斯算法错误率的两倍。对于一些好的K值，K近邻保证错误率不会超过贝叶斯理论误差率。

注：马氏距离一定要先给出样本集的统计性质，比如均值向量，协方差矩阵等。

KNN算法的优缺点

KNN算法的优点：1. 思想简单，理论成熟，既可以用来做分类也可以用来做回归；2. 可用于非线性分类；3. 训练时间复杂度为O(n)；4.准确度高，对数据没有假设，对outlier不敏感
缺点：1.计算量大；2. 样本不平衡问题（即有些类别的样本数量很多，而其它样本的数量很少）；3. 需要大量的内存；