机器学习的经典代表算法总结（一）

1980年机器学习作为一支独立的力量登上了历史舞台。在这之后的10年里出现了一些重要的方法和理论，典型的代表是：分类与回归树(CART，1984)、反向传播算法(1986)、卷积神经网络(1989)。

从1990到2012年，机器学习逐渐走向成熟和应用，在这20多年里机器学习的理论和方法得到了完善和充实，可谓是百花齐放的年代。代表性的重要成果有：支持向量机(SVM，1995)、AdaBoost算法(1997)、循环神经网络和LSTM(1997)、流形学习(2000)、随机森林(2001)。

下面我们对部分机器学习代表算法进行介绍。

⚫线性回归

在机器学习中，我们有一组输入变量(x)用于确定输出变量(y)。输入变量和输出变量之间存在某种关系，机器学习的目标是量化这种关系。

在线性回归中，输入变量(x)和输出变量(y)之间的关系表示为y=ax+b的方程。因此，线性回归的目标是找出系数a和b的值。这里，a是直线的斜率，b是直线的截距。上图显示了数据集的x和y值，线性回归的目标是拟合最接近大部分点的线。

⚫分类与回归树(CART)

CART是决策树的一个实现方式，由ID3，C4.5演化而来，是许多基于树的bagging、boosting模型的基础。CART可用于分类与回归。

CART是在给定输入随机变量x条件下输出随机变量y的条件概率分布，与ID3和C4.5的决策树不同的是，ID3和C4.5生成的决策树可以是多叉的，每个节点下的叉数由该节点特征的取值种类而定，比如特征年龄分为(青年，中年，老年)，那么该节点下可分为3叉。而CART的假设决策树为二叉树，内部结点特征取值为“是”和“否”。左分支取值为“是”，右分支取值为“否”。这样的决策树等价于递归地二分每一个特征，将输入空间划分为有限个单元，并在这些单元上预测概率分布，也就是在输入给定的条件下输出条件概率分布。

⚫随机森林(Random Forest)

随机森林指的是利用多棵决策树对样本进行训练并预测的一种分类器。它包含多个决策树的分类器，并且其输出的类别是由个别树输出的类别的众数而定。随机森林是一种灵活且易于使用的机器学习算法，即便没有超参数调优，也可以在大多数情况下得到很好的结果。随机森林也是最常用的算法之一，因为它很简易，既可用于分类也能用于回归。

其基本的构建算法过程如下：

1)用N来表示训练用例(样本)的个数，M表示特征数目。

2)输入特征数目m，用于确定决策树上一个节点的决策结果;其中m应远小于M。

3)从N个训练用例(样本)中以有放回抽样的方式取样N次，形成一个训练集(即bootstrap取样)，并用未抽到的用例(样本)作预测，评估其误差。

4)对于每一个节点，随机选择m个特征，决策树上每个节点的决定都是基于这些特征确定的。根据这m个特征，计算其最佳的分裂方式。

5)每棵树都会完整成长而不会剪枝，这有可能在建完一棵正常树状分类器后被采用。

⚫逻辑回归

逻辑回归最适合二进制分类(y=0或1的数据集，其中1表示默认类)例如：在预测事件是否发生时，发生的事件被分类为1(在预测人会生病或不生病，生病的实例记为1)。它是以其中使用的变换函数命名的，称为逻辑函数h(x)=1/(1+e-x)，它是一个S形曲线。

在逻辑回归中，输出是以缺省类别的概率形式出现的。因为这是一个概率，所以输出在0-1的范围内。输出(y值)通过对数转换x值，使用对数函数h(x)=1/(1+e-x)来生成，然后应用一个阈值来强制这个概率进入二元分类。

朴素贝叶斯(Naive Bayesian)

朴素贝叶斯法是基于贝叶斯定理与特征条件独立假设的分类方法。朴素贝叶斯分类器基于一个简单的假定：给定目标值时属性之间相互条件独立。

通过以上定理和“朴素”的假定，我们知道：

P(Category|Document)=P(Document|Category)*P(Category)/P(Document)

朴素贝叶斯的基本方法：在统计数据的基础上，依据条件概率公式，计算当前特征的样本属于某个分类的概率，选择最大的概率分类。

对于给出的待分类项，求解在此项出现的条件下各个类别出现的概率。哪个概率最大，就认为此待分类项属于哪个类别。其计算流程表述如下：

1)x={a1,a2,...,am}为待分类项，每个ai为x的一个特征属性

2)有类别集合C={y1,y2,...,yn}

3)计算P(y1|x),P(y2|x),...,P(yn|x)

4)如果P(yk|x)=max{P(y1|x)

⚫k最近邻(kNN)

kNN(k-Nearest Neighbor)的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。kNN方法在做类别决策时，只与极少量的相邻样本有关。由于kNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，kNN方法较其他方法更为适合。