机器学习方法汇总
机器学习方法汇总一
1.决策树算法
决策树是一种树形分类结构，一棵决策树由内部结点和叶子结点构成，内部结点代表一个属性(或者一组属性)，该结点的孩子代表这个属性的不同取值;叶子结点表示一个类标。决策树保证每一个实例都能被一条从根结点到叶子结点的路径覆盖，叶子结点就是这条实例对应的类别，遍历这条路径的过程就是对这条实例分类的过程。关于决策树的详细介绍，可以参考这篇文章。
损失函数
假设决策树T的叶结点个数为|T|，t是树T的某个叶结点，该结点有\(N_t\)个样本点，其中k类的样本点有\(N_{tk}\)个，k=1,2,…,K(K为类别个数)，\(H_t(T)\)为叶结点t上的经验熵(即从训练数据算出的熵)，决策树模型对训练数据的预测误差\(C(T)\)定义为
\(C(T)=\sum_{t=1}^{|T|}N_tH_t(T)=-\sum_{t=1}^{|T|}\sum_{k=1}^{K}N_{tk}log\frac{N_{tk}}{N_t}\)
损失函数\(C_\alpha(T)\):
\(C_\alpha(T)=C(T)+\alpha|T|\)
参数\(\alpha>=0\)控制预测误差与模型复杂度的影响。
优化目标
在决策树的构造阶段，其优化目标是寻找最优的分裂属性，具体实现是最大化属性选择指标，包括信息增益、信息增益比率、基尼指数等，构造阶段用贪心策略得到局部最优的模型。
在剪枝阶段，其优化目标是最小化损失函数\(C_\alpha(T)\)，即
\(min_TC_a(T)\)
剪枝阶段是一个全局优化的过程，如果把@$\alpha$@设置得较大，则倾向于选择简单的树(此时预测误差较大，而泛化能力较好)，而如果$\alpha$设置得较小，则倾向于选择更复杂的模型(此时预测误差较小，而泛化能力偏差);设置为0，那就只考虑预测误差，即对训练数据的拟合程度最高，但对未见过的数据，分类能力并不高。一个适当的@$\alpha$@在预测误差与模型复杂度(泛化能力)之间平衡。
2.线性回归
线性回归使用线性模型拟合因变量与目标变量的关系，是最简单的预测模型。
假设函数
其中\(x_0=1\)
损失函数
\(C(\theta)=\frac{1}{2m}\sum_{i=1}^{m}(h_\theta(x^{(i)})-y^{(i)})^2\)
优化目标
选择合适的参数组\(\theta\)，使得损失函数最小化：
\(min_\theta(C(\theta))\)
优化实现
使用梯度下降法，不断地进行迭代，每一步的方向是负梯度方向：
\(\theta_j=\theta_j-\alpha\frac{\partial }{\partial \theta_j}Cost(\theta)=\theta_j-\alpha\frac{1}{m}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)}\)
3.逻辑回归
逻辑回归于线性回归有着惊人的相似，却又有着本质的不同，线性回归的假设函数度量了一个线性模型对因变量和目标变量的拟合，即给定一个输入，通过一个线性变换得到一个输出，而逻辑回归的假设函数计算的是对于给定输入，其输出y=1的概率，但逻辑回归与线性回归在计算形式上很相似，常常让误解为他们仅仅是假设函数的不同。
假设函数
其中\(x_0=1\) 、\(g(z)=\frac{1}{1+\exp^{-z}}\)
损失函数
这里的损失函数不再是线性回归时的求误差平方和，因为误差平方和不是参数$\theta$的凸函数，不容易求解全局最优解，因此该用极大释然估计作为损失函数，能满足凸函数的要求。
\(C(\theta)=-\frac{1}{m}[\sum_{i=1}^my^{(i)}log(h_\theta(x^{(i)}))+(1-y^{(i)})log(1-h_\theta(x^{(i)}))]\)
优化目标
\(min_\theta(C(\theta))\)
优化实现
使用梯度下降法，不断地进行迭代，每一步的方向是负梯度方向：
\(\theta_j=\theta_j-\alpha\frac{\partial }{\partial \theta_j}Cost(\theta)=\theta_j-\alpha\frac{1}{m}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)}\)
注意到，在优化实现上，逻辑回归与线性回归的形式一样的，只是具体的假设函数不同。实际上，这只是一个巧合，巧合之处在于，对各自的损失函数求偏导数后，其梯度值恰好是假设函数与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)})\)
\(h_W(x)=a^{(L)}\)
其中\(L\)表示神经网络的层数，\(g(z)=\frac{1}{1+\exp^{-z}}\)，\(W^{(i-1)}\)表示第i-1层与第i层单元的权值矩阵，并且把偏置\(\theta^{(i)}\)放在了权值矩阵\(W^{(i-1)}\)中
损失函数
神经网络的损失函数跟逻辑回归非常类似，但是神经网络的输出单元可能有多个，需要在每个输出单元上做一个累加：
\(Cost(W)=-\frac{1}{m}[\sum_{i=1}^m\sum_{k=1}^Ky_k^{(i)}log(h_\theta(x^{(i)}))_k+(1-y^{(i)}_k)log(1-h_\theta(x^{(i)}))_k]\)
其中K表示输出层神经单元的个数，m表示训练数据实例个数。
优化目标
各个算法的优化目标基本上都是寻求适当的参数，使得损失函数最小。
\(min_W(C(\theta))\)
优化实现
BP神经网络，利用反向传播，逐层采样梯度下降。
4.k近邻
损失函数
knn损失函数为0-1损失函数，假设给定一个实例x，其K个最近邻训练实例点构成的集合是\(N_k(x)\)：
\(cost(f)=\frac {1}{k}\sum_{x_i\in N_k(x)}I(y_i\ne c_j)=1-\frac {1}{k}\sum_{x_i\in N_k}(x)I(y_i=c_j)\)
优化目标
机器学习方法汇总二
学习方式
根据数据类型的不同，对一个问题的建模有不同的方式。在机器学习或者人工智能领域，人们首先会考虑算法的学习方式。在机器学习领域，有几种主要的学习方式。将算法按照学习方式分类是一个不错的想法，这样可以让人们在建模和算法选择的时候考虑能根据输入数据来选择最合适的算法来获得最好的结果。
监督式学习：
在监督式学习下，输入数据被称为“训练数据”，每组训练数据有一个明确的标识或结果，如对防垃圾邮件系统中“垃圾邮件”“非垃圾邮件”，对手写数字识别中的“1“，”2“，”3“，”4“等。在建立预测模型的时候，监督式学习建立一个学习过程，将预测结果与“训练数据”的实际结果进行比较，不断的调整预测模型，直到模型的预测结果达到一个预期的准确率。监督式学习的常见应用场景如分类问题和回归问题。常见算法有逻辑回归(Logistic Regression)和反向传递神经网络(Back Propagation Neural Network)
非监督式学习：
在非监督式学习中，数据并不被特别标识，学习模型是为了推断出数据的一些内在结构。常见的应用场景包括关联规则的学习以及聚类等。常见算法包括Apriori算法以及k-Means算法。
半监督式学习：
在此学习方式下，输入数据部分被标识，部分没有被标识，这种学习模型可以用来进行预测，但是模型首先需要学习数据的内在结构以便合理的组织数据来进行预测。应用场景包括分类和回归，算法包括一些对常用监督式学习算法的延伸，这些算法首先试图对未标识数据进行建模，在此基础上再对标识的数据进行预测。如图论推理算法(Graph Inference)或者拉普拉斯支持向量机(Laplacian SVM.)等。
强化学习：
在这种学习模式下，输入数据作为对模型的反馈，不像监督模型那样，输入数据仅仅是作为一个检查模型对错的方式，在强化学习下，输入数据直接反馈到模型，模型必须对此立刻作出调整。常见的应用场景包括动态系统以及机器人控制等。常见算法包括Q-Learning以及时间差学习(Temporal difference learning)
在企业数据应用的场景下， 人们最常用的可能就是监督式学习和非监督式学习的模型。 在图像识别等领域，由于存在大量的非标识的数据和少量的可标识数据， 目前半监督式学习是一个很热的话题。 而强化学习更多的应用在机器人控制及其他需要进行系统控制的领域。
算法类似性
根据算法的功能和形式的类似性，我们可以把算法分类，比如说基于树的算法，基于神经网络的算法等等。当然，机器学习的范围非常庞大，有些算法很难明确归类到某一类。而对于有些分类来说，同一分类的算法可以针对不同类型的问题。这里，我们尽量把常用的算法按照最容易理解的方式进行分类。
回归算法：
回归算法是试图采用对误差的衡量来探索变量之间的关系的一类算法。回归算法是统计机器学习的利器。在机器学习领域，人们说起回归，有时候是指一类问题，有时候是指一类算法，这一点常常会使初学者有所困惑。常见的回归算法包括：最小二乘法(Ordinary Least Square)，逻辑回归(Logistic Regression)，逐步式回归(Stepwise Regression)，多元自适应回归样条(Multivariate Adaptive Regression Splines)以及本地散点平滑估计(Locally Estimated Scatterplot Smoothing)
基于实例的算法
基于实例的算法常常用来对决策问题建立模型，这样的模型常常先选取一批样本数据，然后根据某些近似性把新数据与样本数据进行比较。通过这种方式来寻找最佳的匹配。因此，基于实例的算法常常也被称为“赢家通吃”学习或者“基于记忆的学习”。常见的算法包括 k-Nearest Neighbor(KNN), 学习矢量量化(Learning Vector Quantization， LVQ)，以及自组织映射算法(Self-Organizing Map ， SOM)
正则化方法
正则化方法是其他算法(通常是回归算法)的延伸，根据算法的复杂度对算法进行调整。正则化方法通常对简单模型予以奖励而对复杂算法予以惩罚。常见的算法包括：Ridge Regression， Least Absolute Shrinkage and Selection Operator(LASSO)，以及弹性网络(Elastic Net)。
决策树学习
决策树算法根据数据的属性采用树状结构建立决策模型， 决策树模型常常用来解决分类和回归问题。常见的算法包括：分类及回归树(Classification And Regression Tree， CART)， ID3 (Iterative Dichotomiser 3)， C4.5， Chi-squared Automatic Interaction Detection(CHAID), Decision Stump, 随机森林(Random Forest)， 多元自适应回归样条(MARS)以及梯度推进机(Gradient Boosting Machine， GBM)
贝叶斯方法
贝叶斯方法算法是基于贝叶斯定理的一类算法，主要用来解决分类和回归问题。常见算法包括：朴素贝叶斯算法，平均单依赖估计(Averaged One-Dependence Estimators， AODE)，以及Bayesian Belief Network(BBN)。
基于核的算法
基于核的算法中最著名的莫过于支持向量机(SVM)了。 基于核的算法把输入数据映射到一个高阶的向量空间， 在这些高阶向量空间里， 有些分类或者回归问题能够更容易的解决。 常见的基于核的算法包括：支持向量机(Support Vector Machine， SVM)， 径向基函数(Radial Basis Function ，RBF)， 以及线性判别分析(Linear Discriminate Analysis ，LDA)等
聚类算法
聚类，就像回归一样，有时候人们描述的是一类问题，有时候描述的是一类算法。聚类算法通常按照中心点或者分层的方式对输入数据进行归并。所以的聚类算法都试图找到数据的内在结构，以便按照最大的共同点将数据进行归类。常见的聚类算法包括 k-Means算法以及期望最大化算法(Expectation Maximization， EM)。
关联规则学习
关联规则学习通过寻找最能够解释数据变量之间关系的规则，来找出大量多元数据集中有用的关联规则。常见算法包括 Apriori算法和Eclat算法等。
人工神经网络
人工神经网络算法模拟生物神经网络，是一类模式匹配算法。通常用于解决分类和回归问题。人工神经网络是机器学习的一个庞大的分支，有几百种不同的算法。(其中深度学习就是其中的一类算法，我们会单独讨论)，重要的人工神经网络算法包括：感知器神经网络(Perceptron Neural Network), 反向传递(Back Propagation)， Hopfield网络，自组织映射(Self-Organizing Map, SOM)。学习矢量量化(Learning Vector Quantization， LVQ)
深度学习
深度学习算法是对人工神经网络的发展。 在近期赢得了很多关注， 特别是百度也开始发力深度学习后， 更是在国内引起了很多关注。 在计算能力变得日益廉价的今天，深度学习试图建立大得多也复杂得多的神经网络。很多深度学习的算法是半监督式学习算法，用来处理存在少量未标识数据的大数据集。常见的深度学习算法包括：受限波尔兹曼机(Restricted Boltzmann Machine， RBN)， Deep Belief Networks(DBN)，卷积网络(Convolutional Network), 堆栈式自动编码器(Stacked Auto-encoders)。
降低维度算法
像聚类算法一样，降低维度算法试图分析数据的内在结构，不过降低维度算法是以非监督学习的方式试图利用较少的信息来归纳或者解释数据。这类算法可以用于高维数据的可视化或者用来简化数据以便监督式学习使用。常见的算法包括：主成份分析(Principle Component Analysis， PCA)，偏最小二乘回归(Partial Least Square Regression，PLS)， Sammon映射，多维尺度(Multi-Dimensional Scaling, MDS), 投影追踪(Projection Pursuit)等。
集成算法：
集成算法用一些相对较弱的学习模型独立地就同样的样本进行训练，然后把结果整合起来进行整体预测。集成算法的主要难点在于究竟集成哪些独立的较弱的学习模型以及如何把学习结果整合起来。这是一类非常强大的算法，同时也非常流行。常见的算法包括：Boosting， Bootstrapped Aggregation(Bagging)， AdaBoost，堆叠泛化(Stacked Generalization， Blending)，梯度推进机(Gradient Boosting Machine, GBM)，随机森林(Random Forest)。