文科小白也能看懂的机器学习基础（三）

前面说的算法都是分类，现在说回归相关的算法。分类算法是训练一个能够判别样本类型的模型，回归算法是预测样本在坐标系中的位置。

（六）线性回归

最小二乘法是最简单的回归算法，假定二维平面存在一些样本点，最小二乘法希望能够画出一条直线，根据直线的方程（回归方程）能够以较小的误差预测样本点所在的位置。

为了使该回归方程的预测误差最小，最小二乘法计算每个训练样本点到回归直线的距离，将其平方求和后，得到最小二乘法的损失函数。最小二乘法希望最小化损失函数取值，使得所有训练样本点到回归直线距离的平方和最小，预测误差最小。

线性回归样例

模型训练中经常出现的两类典型问题:一类是模型无法得到较低的训练误差， 我们将这一现象称作欠拟合(underfitting);另一类是模型的训练误差远小于它在测试数据集上 的误差，我们称该现象为过拟合(overfitting)。

线性回归的一个问题是有可能出现欠拟合现象，因为它求的是最小均方误差的无偏估计，所以如果模型欠拟合就无法取得最好的预测效果。所以有些方法允许在估计中引入一些偏差，从而降低预测的均方误差。

其中一个方法是局部加权线性回归，对于最小二乘法而言，不论需要预测哪个点，所有训练样本的权重均相同。对于局部加权线性回归，离预测点更近的训练样本点所拥有的权重应当更高。

（七）树回归

实际生活很多问题都是非线性的，不可能使用全局线性模型来拟合任何数据。树回归，将数据集切分成很多份易建模的数据，然后用线性回归建模

前面我们讲过ID3决策树算法，是每次选取当前最佳特征来分割数据，并且按照特征的所有可能取值来切分，我们一次分类就要消耗一个特征，在后面的分类过程中，这个被消耗掉的分类就不再起作用，这样的切分太过迅速，浪费了一些信息。而且ID3决策树也只能处理离散型的数据，它不能直接处理连续性特征，只有事先将连续性特征转换为离散型，才能在ID3算法中使用，但转换会破坏连续型变量的内质。

为了解决前面提到的问题，我们介绍CART树（分类回归树）构建算法，它利用二元切分法处理连续型变量，如果特征值大于给定值就走左子树，否则走右子树，即每次把数据切为两份，分别进入左子树和右子树。

回归树概要，加载数据集，随后选定最好的划分特征和划分特征值，将原数据集划分成左子树和右子树，随后不断迭代划分，直到满足停止条件。当回归树构建完成后，我们用每个叶子节点数据的均值来代表这个叶子节点下的所有数据。

构建回归树的过程与ID3算法构建树的过程非常相似，接下来需要确定的是两点，一个是在构建回归树的过程中怎样选定最好的划分特征和划分特征值，第二个是应该用什么作为提前停止条件。

在ID3算法中，我们每次选择让整个数据集香农熵减小最多（信息增益最大）的特征对数据集进行划分，而在回归树算法中因为要处理的是连续性的数值变量，直接采用总方差来度量分类的有效程度，遍历所有特征及其所有可能的取值，每次选择让整个数据集总方差减小最多的特征及划分特征值对数据进行划分。

回归树算法中需要提前设定两个参数以控制算法的停止时机，一个是容许的误差下降值，一个是切分的最少样本数。也就是如果这次最佳划分使总方差的下降值小于预定阈值，或划分后的两个子集存在某个子集大小小于预定阈值，则停止继续划分。

使用CART构建树时还会涉及到树剪枝的问题，一棵树如果节点过多，表示该模型可能对数据进行了过拟合，我们可以通过交叉验证来判断是否发生了过拟合，通过降低决策树复杂度来避免过拟合的过程称为剪枝，提前终止条件实际上就是预剪枝，另一种形式的剪枝需要使用训练集和测试集，称作后剪枝。

如果使用预剪枝，我们需要不断的修改停止条件，而后剪枝则不需要用户指定参数，但相对的，后剪枝不如预剪枝有效。

后剪枝需要在树构建完成后使用测试集，自上而下找到叶节点，然后尝试合并相邻的叶节点，如果合并叶节点后能够降低在测试集上的误差，那我们就合并掉两个叶节点。

接下来要讲的是模型树，模型树与回归树的区别在于，每个叶子节点下不再是常数，而是用线性函数来对数据做拟合，整棵模型树成为了一个分段线性函数。

优点：可以对复杂和非线性数据建模，缺点：结果不容易理解。

现在开始说明无监督的学习方法。

（八）k-均值聚类

k-均值是发现给定数据集的k个簇的算法，簇个数k是用户给定的，每个簇通过其质心，即簇中所有点的中心来描述。

k-均值聚类聚类的流程：首先，选择k个初始点作为质心，然后为每个样本点找距其最近的质心，并将其分配给该质心所对应的簇，然后将每个簇的质心更新为该簇所有点的平均值，既然质心位置改变了，那对样本点的划分自然也要随之改变，如此不断迭代，直到对所有样本点的分类都不再改变，也即算法收敛。

为了克服K-均值聚类算法可能会收敛到局部最小值的问题，即容易受到初始簇质心的影响。为了更好聚类，有人提出了二分K-均值算法，该算法首先将所有点作为一个簇，使用k-均值算法（k=2）对其划分。下次迭代时，选择有最大误差的簇进行划分，该过程重复到k个簇创建成功为止。

优点：容易实现。缺点：可能收敛到局部最小值，在大规模数据集上收敛较慢。