1.决策树算法

决策树是一种树形分类结构，一棵决策树由内部结点和叶子结点构成，内部结点代表一个属性（或者一组属性），该结点的孩子代表这个属性的不同取值；叶 子结点表示一个类标。决策树保证每一个实例都能被一条从根结点到叶子结点的路径覆盖，叶子结点就是这条实例对应的类别，遍历这条路径的过程就是对这条实例 分类的过程。 

损失函数

假设决策树T的叶结点个数为|T|，t是树T的某个叶结点，该结点有Nt个样本点，其中k类的样本点有Ntk个，k=1,2,…,K（K为类别个数），Ht(T)为叶结点t上的经验熵（即从训练数据算出的熵），决策树模型对训练数据的预测误差C(T)定义为

C(T)=∑|T|t=1NtHt(T)=−∑|T|t=1∑Kk=1NtklogNtkNt

损失函数Cα(T):

Cα(T)=C(T)+α|T|

参数α>=0控制预测误差与模型复杂度的影响。

优化目标

在决策树的构造阶段，其优化目标是寻找最优的分裂属性，具体实现是最大化属性选择指标，包括信息增益、信息增益比率、基尼指数等，构造阶段用贪心策略得到局部最优的模型。

在剪枝阶段，其优化目标是最小化损失函数Cα(T)，即

minTCa(T)

剪枝阶段是一个全局优化的过程，如果把@$\alpha$@设置得较大，则倾向于选择简单的 树（此时预测误差较大，而泛化能力较好），而如果$\alpha$设置得较小，则倾向于选择更复杂的模型（此时预测误差较小，而泛化能力偏差）；设置为 0，那就只考虑预测误差，即对训练数据的拟合程度最高，但对未见过的数据，分类能力并不高。一个适当的@$\alpha$@在预测误差与模型复杂度（泛化 能力）之间平衡。

2.线性回归

线性回归使用线性模型拟合因变量与目标变量的关系，是最简单的预测模型。

假设函数

其中x0=1

损失函数

C(θ)=12m∑mi=1(hθ(x(i))−y(i))2

优化目标

选择合适的参数组θ，使得损失函数最小化：

minθ(C(θ))

优化实现

使用梯度下降法，不断地进行迭代，每一步的方向是负梯度方向：

θj=θj−α∂∂θjCost(θ)=θj−α1m∑mi=1(hθ(x(i))−y(i))x(i)j

3.逻辑回归

逻辑回归于线性回归有着惊人的相似，却又有着本质的不同，线性回归的假设函数度量了一个线性模型对因变量和目标变量的拟合，即给定一个输入，通过一 个线性变换得到一个输出，而逻辑回归的假设函数计算的是对于给定输入，其输出y=1的概率，但逻辑回归与线性回归在计算形式上很相似，常常让误解为他们仅 仅是假设函数的不同。

假设函数

其中x0=1 、g(z)=11+exp−z

损失函数

这里的损失函数不再是线性回归时的求误差平方和，因为误差平方和不是参数$\theta$的凸函数，不容易求解全局最优解，因此该用极大释然估计作为损失函数，能满足凸函数的要求。

C(θ)=−1m[∑mi=1y(i)log(hθ(x(i)))+(1−y(i))log(1−hθ(x(i)))]

优化目标

minθ(C(θ))

优化实现

使用梯度下降法，不断地进行迭代，每一步的方向是负梯度方向：

θj=θj−α∂∂θjCost(θ)=θj−α1m∑mi=1(hθ(x(i))−y(i))x(i)j

注意到，在优化实现上，逻辑回归与线性回归的形式一样的，只是具体的假设函数不同。实际上，这只是一个巧合，巧合之处在于，对各自的损失函数求偏导数后，其梯度值恰好是假设函数与y的表达式，但线性回归与逻辑回归的本质是不同的。

3.BP神经网络

这篇文章已经介绍了BP神经网络，这里只是从模型、策略、算法这三个层面来总结一下BP，模型就是指假设函数，策略则指优化目标，算法即指优化实现。

假设函数

神经网络的假设函数不是一个简单的公式，它是多个逻辑回归函数逐层迭代的结果，形式上可以写成如下：

a(1)=x

a(2)=g(W(1)a(1))

a(i)=g(W(i−1)a(i−1))

….

a(L)=g(W(L−1)a(L−1))

hW(x)=a(L)

其中L表示神经网络的层数，g(z)=11+exp−z，W(i−1)表示第i-1层与第i层单元的权值矩阵，并且把偏置θ(i)放在了权值矩阵W(i−1)中

损失函数

神经网络的损失函数跟逻辑回归非常类似，但是神经网络的输出单元可能有多个，需要在每个输出单元上做一个累加：

Cost(W)=−1m[∑mi=1∑Kk=1y(i)klog(hθ(x(i)))k+(1−y(i)k)log(1−hθ(x(i)))k]

其中K表示输出层神经单元的个数，m表示训练数据实例个数。

优化目标

各个算法的优化目标基本上都是寻求适当的参数，使得损失函数最小。

minW(C(θ))

优化实现

BP神经网络，利用反向传播，逐层采样梯度下降。

4.k近邻

损失函数

knn损失函数为0-1损失函数，假设给定一个实例x，其K个最近邻训练实例点构成的集合是Nk(x)：

cost(f)=1k∑xi∈Nk(x)I(yi≠cj)=1−1k∑xi∈Nk(x)I(yi=cj)

优化目标