机器学习浅析（下）
上篇文章讲了监督学习的五类分类算法，接下来要讲的是回归算法。那回归和分类有什么区别呢？区别就在于输出变量的类型。定量输出称为回归，或者说是连续变量预测；定性输出称为分类，或者说是离散变量预测。举个例子：预测明天的气温是多少度，这是一个回归任务；预测明天是阴、晴还是雨，就是一个分类任务。
回归方程.jpg
这就是所谓的回归方程，其中的B就是所谓的回归系数，求这些回归系数的过程就是回归。一旦有了这些回归系数，再给定输入，做预测就非常容易了。具体的作法使用回归系数乘以输入值，再将结果全部加在一起，就得到了预测值。
接下来讲最简单的回归方法：最小二乘法。最小二乘法（又称最小平方法）是一种数学优化技术。它通过最小化误差的平方和寻找数据的最佳函数匹配。利用最小二乘法可以简便地求得未知的数据，并使得这些求得的数据与实际数据之间误差的平方和为最小。
基本回归方式
我们举个例子来看一下，如下图所示：
推导公式.jpg
最小二乘法这样纯粹的线性回归往往会出现欠拟合现象，所以我们期望在估计中引入一些偏差，从而降低预测的均方误差。下面讲的是局部加权线性回归，它的思想在于，我们给所有的样本点赋予一定权重，并且认为离待预测点更近的样本点所拥有的权重应该更高。
局部加权线性回归
局部加权线性回归是机器学习里的一种经典的方法，弥补了普通线性回归模型欠拟合或者过拟合的问题。机器学习里分为无监督学习和有监督学习，线性回归里是属于有监督的学习。普通的线性回归属于参数学习算法(parametric learning algorithm)；而局部加权线性回归属于非参数学习算法(non-parametric learning algorithm)。所谓参数学习算法它有固定的明确的参数，参数 一旦确定，就不会改变了，我们不需要在保留训练集中的训练样本。而非参数学习算法，每进行一次预测，就需要重新学习一组 ， 是变化的，所以需要一直保留训练样本。也就是说，当训练集的容量较大时，非参数学习算法需要占用更多的存储空间。
上面的话好像不够直观，下面我们来直观地看一下局部加权线性回归到底是怎么样的。
局部加权线性回归就是在给待测点附近的每个点赋予一定的权重，也就是加一个核函数矩阵W，最后需要最小化的目标函数如下：
目标函数
这就是刚刚的加权最小二乘法，再来看看系数的估计项：
系数函数
矩阵
好吧，这就是加权最小二乘法，当然，如果这就是局部加权线性回归的全部，也不用发明它了，我们接着看。这里出现了一个问题，权重是如何确定的，也就是这个所谓的核函数矩阵的形式，百度了一下，通常使用的都是高斯核,形式如下：
高斯核
代表的是第i个样本点，x是我们预测点，对于金融数据来说，完全可以用时间t来衡量，也就是说时间越近的样本数据越重要，这样的预测对想研究的对象而言更准确。
介绍到这里似乎没有体现出机器学习的意思，仔细观察就会发现Ｋ是一个很重要的东西，不信，我们举个例子来看看：
为了简单起见，我们就用一元的线性回归来看看，方便数据可视化。这里我们取一些非线性拟合的数据，因为局部加权线性回归的优势就在于处理非线性关系的异方差问题。
看一下我们需要拟合的样本数据(点击查看原文代码)：
图一
很明显，这是一个非线性关系的样本数据，我们先用普通最小二乘回归来处理这个问题：
y=1.34568655273+0.979532165941x
图二
可以看到，要用直线来拟合非线性关系略有牵强，金融数据里很多时间序列的关系都是非线性的，回归的结果往往不好．
下面我们用刚才介绍的局部加权线性回归来拟合一下这个模型，简单回顾一下过程：
1.用高斯核函数计算出第ｉ个样本处，其它所有样本点的权重Ｗ
2.用权重ｗ对第ｉ个样本作加权线性回归，得到回归方程，即拟合的直线方程
3.用刚才得到的经验回归直线计算出xi处的估计值y^i
4.重复一至三步，得到每个样本点的估计值
这里作加权线性回归时，我使用的是把加权最小二乘转换为普通最小二乘的方法，也就是本帖第二部分内容，网上的做法大多是直接用上面的公式算出β的估计值。
刚才说到，ｋ是一个很关键的参数，我们从高斯函数的形式可以看出，ｋ取非常大的时候，每个样本点的权重都趋近于１，我们可以先取ｋ很大，检验一下是否正确
拟合曲线
表格
可以看到用普通最小二乘估计出来的值和我们用局部加权估计出来的值非常的一致，说明逻辑是对的。 下面调整一下ｋ的值，来看看各种ｋ值下的拟合状况：
图二
图三
图四
可以看到，当ｋ越小时，拟合的效果越好，但是我们拟合的目的在于预测，需要避免过拟合的问题，这时候需要做Bias/Variance Trade-off：
一般的Validation就是把数据分为随机的两部分一部分做训练，一部分作验证。还有leave-one-out validation,k-fold Cross Validation等方法。
训练的目的是为了让训练误差尽量减小，同时也要注意模型的自由度（参数个数）,避免测试误差很大。
训练误差一般用MSE来衡量：
均方误差
比如在我们这个简单的例子里，如果要对之后的数据进行预测，就需要通过Validation选择参数ｋ的大小，再对离需要预测的点最近的点做加权线性回归去估计那个点的值。
岭回归与Lasso回归
岭回归与Lasso回归的出现是为了解决线性回归出现的过拟合以及在通过正规方程方法求解θ的过程中出现的x转置乘以x不可逆这两类问题的，这两种回归均通过在损失函数中引入正则化项来达到目的，具体三者的损失函数对比见下图：
回归函数的损失函数
其中λ称为正则化参数，如果λ选取过大，会把所有参数θ均最小化，造成欠拟合，如果λ选取过小，会导致对过拟合问题解决不当，因此λ的选取是一个技术活。
岭回归与Lasso回归最大的区别在于岭回归引入的是L2范数惩罚项，Lasso回归引入的是L1范数惩罚项，Lasso回归能够使得损失函数中的许多θ均变成0，这点要优于岭回归，因为岭回归是要所有的θ均存在的，这样计算量Lasso回归将远远小于岭回归。
图六
图八
可以看到，Lasso回归最终会趋于一条直线，原因就在于好多θ值已经均为0，而岭回归却有一定平滑度，因为所有的θ值均存在。
树回归
上一节介绍了多种线性回归算法，但是对于某些复杂的数据集，并不能建立全局的回归方程，所以我们希望结合树的思想，先将数据集进行分类，将数据集切分成很多份易建模回归的数据，然后再用前面的回归方法来求得回归方程。
前面我们讲过ID3决策树算法，在那里我们一次分类就要消耗一个特征，在后面的分类过程中，这个被消耗掉的分类就不再起作用，这样的分类有时候太过迅速，浪费了一些信息，而且ID3决策树也只能处理离散型的数据，如果要处理连续性数据需要先经过一步预处理，但是这种处理会破坏连续性数据原本的内在性质。
为了解决前面提到的问题，我们介绍CART树（分类回归树）构建算法，它利用二元切分法处理连续型变量，即每次把数据切为两份，分别进入左子树和右子树。基于CART可以构建回归树，也可以构建模型树。
回归树概要，加载数据集，随后选定最好的划分特征和划分特征值，将原数据集划分成左子树和右子树，随后不断迭代划分，直到满足停止条件。当回归树构建完成后，我们用每个叶子节点数据的均值来代表这个叶子节点下的所有数据。
构建回归树的过程与ID3算法构建树的过程非常相似，接下来需要确定的是两点，一个是在构建回归树的过程中怎样选定最好的划分特征和划分特征值，第二个是应该用什么作为提前停止条件。
在ID3算法中，我们每次选择让整个数据集香农熵减小最多（信息增益最大）的特征对数据集进行划分，而在回归树算法中因为要处理的是连续性的数值变量，直接采用总方差来度量分类的有效程度，遍历所有特征及其所有可能的取值，每次选择让整个数据集总方差减小最多的特征及划分特征值对数据进行划分。
回归树算法中需要提前设定两个参数以控制算法的停止时机，一个是容许的误差下降值，一个是切分的最少样本数。也就是如果这次最佳划分使总方差的下降值小于预定阈值，或划分后的两个子集存在某个子集大小小于预定阈值，则停止继续划分。
使用CART构建树时还会涉及到树剪枝的问题，一棵树如果节点过多，表示该模型可能对数据进行了过拟合，我们可以通过交叉验证来判断是否发生了过拟合，通过降低决策树复杂度来避免过拟合的过程称为剪枝，提前终止条件实际上就是预剪枝，另一种形式的剪枝需要使用训练集和测试集，称作后剪枝。
如果使用预剪枝，我们需要不断的修改停止条件，而后剪枝则不需要用户指定参数，但相对的，后剪枝不如预剪枝有效。
后剪枝需要在树构建完成后使用测试集，自上而下找到叶节点，然后尝试合并相邻的叶节点，如果合并叶节点后能够降低在测试集上的误差，那我们就合并掉两个叶节点。
接下来要讲的是模型树，模型树与回归树的区别在于，每个叶子节点下不再是常数，而是用线性函数来对数据做拟合，整棵模型树成为了一个分段线性函数。
模型树
比如上图这样的数据就相当适合采用模型树来建模，整个数据集会被分为两个叶子节点，每个叶子节点下是一个线性函数。
其划分的基本思想仍然是找让整个数据集总误差最小的划分方式，回归树中的方法不能再用，但是我们在上一节讲过了相当多的线性模型，也讲过了它们对应的计算误差的方式（平方误差），我们只要在每次尝试划分后对每个叶子节点下用线性模型去拟合该节点下的数据，然后分别计算误差值，选取使总误差最小的划分方式即可。
树回归在预测复杂数据集时会比简单的线性模型更有效。
无监督学习
无监督学习是机器学习的一种方法，没有给定事先标记过的训练示例，自动对输入的数据进行分类或分群。通俗一点来说就是，我在给定数据的过程中，不给定任何标签，让你自己想办法对这些数据进行归类贴标签。接下来讲一种无监督学习算法——K-均值聚类算法。
K-均值聚类算法
我根据机器学习实战，总结了一下它的原理：选择k个初始点作为质心，然后为每个样本点找距其最近的质心，并将其分配给该质心所对应的簇，然后将每个簇的质心更新为该簇所有点的平均值，既然质心位置改变了，那对样本点的划分自然也要随之改变，如此不断迭代，直到对所有样本点的分类都不再改变，也即算法收敛。
其他工具
利用PCA与SVD来简化数据
主成分分析（Principal Component Analysis，PCA ）
将数据从原来的坐标系转移到新的坐标系，新坐标系的选择由数据本身决定，新坐标系的第一个坐标轴是原始数据中方差最大的方向，新坐标系的第二个坐标轴和第一个坐标轴正交、并且具有最大方差。该过程一直重复，次数为原始数据中维度。大部分方差都包含在前面几个新坐标轴中，因此可以忽略剩下的坐标轴，即对数据进行了降维处理。
因子分析（Factor Analysis）：
假设观察数据的生成中有一些观察不到的隐变量，即观察数据是由这些隐变量和某些噪声的线性组合，那么隐变量的数据可能比观察数据的数目少，找到隐变量就可以实现数据的降维。
独立成分分析（Independent Component Analysis，ICA）：
ICA假设数据是从N个数据源生成的，这一点和因子分析有些类似。假设数据为多个数据源的混合观察结果，这些数据源之间在统计上是相互独立的，而在PCA中只假设数据是不相关的。同因子分析一样，如果数据源的数目少于观察数据的数目，则可以实现降维过程。
在上述3种降维技术中，PCA的应用目前最为广泛。
线性映射（或线性变换），简单的来说就是将高维空间数据投影到低维空间上，那么在数据分析上，我们是将数据的主成分（包含信息量大的维度）保留下来，忽略掉对数据描述不重要的成分。即将主成分维度组成的向量空间作为低维空间，将高维数据投影到这个空间上就完成了降维的工作。
在 PCA中,数据从原来的坐标系转换到了新的坐标系,新坐标系的选择是由数据本身决定的。第一个新坐标轴选择的是原始数据中方差最大的方向,第二个新坐标轴的选择和第一个坐标轴正交且具有最大方差的方向。该过程一直重复,重复次数为原始数据中特征的数目。我们会发现,大部分方差都包含在最前面的几个新坐标轴中。因此,我们可以忽略余下的坐标轴,即对数据进行了降维处理。
PCA工作原理：
①找出第一个主成分的方向，也就是数据 方差最大 的方向。
②找出第二个主成分的方向，也就是数据 方差次大 的方向，并且该方向与第一个主成分方向正交(果是二维空间就叫垂直)。
③通过这种方式计算出所有的主成分方向。
④通过数据集的协方差矩阵及其特征值分析，我们就可以得到这些主成分的值。
⑤一旦得到了协方差矩阵的特征值和特征向量，我们就可以保留最大的 N 个特征。这些特征向量也给出了 N 个最重要特征的真实结构，我们就可以通过将数据乘上这 N 个特征向量 从而将它转换到新的空间上。
特征转化
奇异值分解 SVD(singular value decomposition)
SVD奇异值分解的定义：
假设M是一个m×n的矩阵，如果存在一个分解：
1.jpg
2.jpg
3.jpg
如何选择数值r?
确定要保留的奇异值数目有很多启发式的策略,其中一个典型的做法就是保留矩阵中90%的能量信息.为了计算能量信息,将所有的奇异值求其平方和,从大到小叠加奇异值,直到奇异值之和达到总值的90%为止;另一种方法是,当矩阵有上万个奇异值时, 直接保留前2000或3000个.,但是后一种方法不能保证前3000个奇异值能够包含钱90%的能量信息,但是操作简单。
