机器学习10大经典算法详解

　　＂数据+算法=模型＂。 面对具体的问题，选择切合问题的模型进行求解十分重要。有经验的数据科学家根据日常算法的积累，往往能在最短时间内选择更适合该问题的算法，因此构建的模型往往更准确高效。
　　本文归纳了机器学习的10大算法，并分别整理了各算法的优缺点及主要特征，供大家学习参考。读完本文，你将掌握以下机器学习10大算法的基本概念及主要适用情况，是机器学习过程不可错过的基础概念篇。
　　本文涵盖的机器学习领域10大算法包括：
　　·决策树算法
　　·朴素贝叶斯算法
　　·K最近邻算法
　　·AdaBoost算法
　　·PageRank算法
　　·EM算法(期望最大化算法)
　　·Apriori算法
　　·SVM算法
　　·K均值聚类算法
　　·线性回归算法   Linear Regression
　　下面我们将具体展开介绍。
　　1.决策树算法
　　决策树，是一个类似于流程图的树形结构，树内部的每一个节点代表的是对一个特征的测试，树的分支代表该特征的每一个测试结果，而树的每一个叶子节点代表一个类别。树的最高层就是根节点。
　　决策树的生成过程主要分为以下3个部分：
　　1. 特征选择 : 特征选择是指从训练数据中众多的特征中选择一个特征作为当前节点的分裂标准，如何选择特征有着很多不同量化评估标准标准，从而衍生出不同的决策树算法。
　　2.决策树生成:  根据选择的特征评估标准，从上至下递归地生成子节点，直到数据集不可分则停止决策树停止生长。 树结构来说，递归结构是最容易理解的方式
　　3.剪枝:  决策树容易过拟合，一般来需要剪枝，缩小树结构规模、缓解过拟合。剪枝技术有预剪枝和后剪枝两种。
　　树模型和线性模型之间的区别
　　树形模型是一个一个特征进行处理，线性模型是所有特征给予权重相加得到一个新的值。决策树与逻辑回归的分类区别也在于此，逻辑回归是将所有特征变换为概率后，通过大于某一概率闻值的划分为一类，小于某一概率闻值的为另一类，而决策树是对每一个特征做一个划分。另外逻辑回归只能找到线性分割(输入特征x与logit之间是线性的，除非对x进行多维映射)，而决策树可以找到非线性分割。
　　而树形模型更加接近人的思维方式，可以产生可视化的分类规则，产生的模型具有可解释性(可以抽取规则)。树模型拟合出来的函数其实是分区间的阶梯函数。
　　算法优点：
　　· 学习以及预测的速度都非常快；
　　· 并且树模型适用于各种各样的问题，不需要对数据进行任何特殊的处理。
　　算法缺点：
　　· 对连续性的字段比较难预测。
　　· 容易出现过拟合。
　　· 对于各类别样本数量不一致的数据，在决策树当中，信息增益的结果偏向于那些具有更多数值的特征。
　　决策树的典型算法包括ID3，C4.5，CART等，下面重点介绍一下C4.5和CART。
　　C4.5
　　国际权威的学术组织，数据挖掘国际会议ICDM （the IEEE International Conference on Data Mining）在2006年12月评选出了数据挖掘领域的十大经典算法中，C4.5算法排名第一。C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法。
　　C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进：
　　1)用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；
　　2)在树构造过程中进行剪枝；
　　3)能够完成对连续属性的离散化处理；
　　4)能够对不完整数据进行处理。
　　C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。
　　CART
　　CART（ClassificaTIon andRegression Tree）分类回归树是一种决策树构建算法。不同于ID3与C4．5，CART为一种二分决策树，是满二叉树。CART算法由Breiman等人在 1984 年提出，它采用与传统统计学完全不同的方式构建预测准则，它是以二叉树的形式给出，易于理解、使用和解释。
　　CART是在给定输入随机变量X条件下输出随机变量Y的条件概率分布的学习方法。CART假设决策树是二叉树，内部结点特征的取值为＂是＂和＂否＂，左分支是取值为＂是＂的分支，右分支是取值为＂否＂的分支。这样的决策树等价于递归地二分每个特征，将输入空间即特征空间划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布。
　　CART算法既可以处理离散型问题，也可以处理连续型问题。这种算法在处理连续型问题时，主要通过使用二元切分来处理连续型变量，即特征值大于某个给定的值就走左子树，或者就走右子树。
　　CART优点：
　　· 可以生成可以理解的规则；
　　· 计算量相对来说不是很大；
　　· 可以处理连续和种类字段；
　　· 决策树可以清晰的显示哪些字段比较重要。
　　CART缺点：
　　· 对连续性的字段比较难预测；
　　· 对有时间顺序的数据，需要很多预处理的工作；
　　· 当类别太多时，错误可能就会增加的比较快；
　　· 一般的算法分类的时候，只是根据一个字段来分类。
　　2.朴素贝叶斯算法
　　贝叶斯分类是一类分类算法的总称，这类算法均以贝叶斯定理为基础，故统称为贝叶斯分类。而朴素贝叶斯（Naive Bayes）分类是贝叶斯分类中最简单，也是常见的一种分类方法。
　　朴素贝叶斯算法的核心思想是通过考虑特征概率来预测分类，即对于给出的待分类样本，求解在此样本出现的条件下各个类别出现的概率，哪个最大，就认为此待分类样本属于哪个类别。
　　在机器学习中如KNN、逻辑回归、决策树等模型都是判别方法，也就是直接学习出特征输出Y 和特征X 之间的关系（决策函数Y = f ( X ) 或者条件分布P(Y∣X)）。但朴素贝叶斯是生成方法，它直接找出特征输出Y和特征X的联合分布P ( X , Y )，进而通过P ( Y ∣ X ) = P ( X , Y ) |P ( X ) 计算得出结果判定。
　　基于贝叶斯定理的贝叶斯模型是一类简单常用的分类算法。在「假设待分类项的各个属性相互独立」的情况下，构造出来的分类算法就称为朴素的，即朴素贝叶斯算法。
　　所谓「朴素」，是假定所有输入事件之间是相互独立。进行这个假设是因为独立事件间的概率计算更简单。
　　算法优点：
　　朴素贝叶斯算法假设了数据集属性之间是相互独立的，因此算法的逻辑性十分简单，并且算法较为稳定，当数据呈现不同的特点时，朴素贝叶斯的分类性能不会有太大的差异。换句话说就是朴素贝叶斯算法的健壮性比较好，对于不同类型的数据集不会呈现出太大的差异性。当数据集属性之间的关系相对比较独立时，朴素贝叶斯分类算法会有较好的效果。
　　算法缺点：
　　属性独立性的条件同时也是朴素贝叶斯分类器的不足之处。数据集属性的独立性在很多情况下是很难满足的，因为数据集的属性之间往往都存在着相互关联，如果在分类过程中出现这种问题，会导致分类的效果大大降低。
　　3.K最近邻算法
　　邻近算法，或者说K最邻近（KNN，K-NearestNeighbor）分类算法是数据挖掘分类技术中最简单的方法之一。所谓K最近邻，就是K个最近的邻居的意思，说的是每个样本都可以用它最接近的K个邻近值来代表。近邻算法就是将数据集合中每一个记录进行分类的方法。
　　KNN算法是一种基于实例的学习，或者是局部近似和将所有计算推迟到分类之后的惰性学习。用最近的邻居（k）来预测未知数据点。 k 值是预测精度的一个关键因素 ，无论是分类还是回归，衡量邻居的权重都非常有用，较近邻居的权重比较远邻居的权重大。
　　距离或紧密度的概念可能会在高维环境（大量输入变量）下崩溃，这会对算法造成负面影响。这类事件被称为维度诅咒。它也暗示了你应该只使用那些与预测输出变量最相关的输入变量。
　　算法优点：
　　KNN方法思路简单，易于理解，易于实现，无需估计参数。
　　算法缺点：
　　· 该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数
　　· 该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。
　　· 惰性学习
　　KNN算法是懒散学习方法（lazy learning,基本上不学习），一些积极学习的算法要快很多。
　　4.AdaBoost算法
　　Boosting是一种从一些弱分类器中创建一个强分类器的集成技术。 它先由训练数据构建一个模型，然后创建第二个模型来尝试纠正第一个模型的错误。 不断添加模型，直到训练集完美预测或已经添加到数量上限。
　　AdaBoost是为二分类开发的第一个真正成功的Boosting算法，同时也是理解Boosting的最佳起点。
　　AdaBoost算法是Adaptive Boost的简称，Adaboost是一种迭代算法，其核心思想是针对同一个训练集训练不同的分类器(弱分类器)，然后把这些弱分类器集合起来，构成一个更强的最终分类器（强分类器）。
　　AdaBoost算法流程：
　　1. 先通过对N个训练样本的学习得到第一个弱分类器；
　　2. 将分错的样本和其他的新数据一起构成一个新的N个的训练样本，通过对这个样本的学习得到第二个弱分类器 ；
　　3. 将1和2都分错了的样本加上其他的新样本构成另一个新的N个的训练样本，通过对这个样本的学习得到第三个弱分类器；
　　4. 最终经过提升的强分类器。即某个数据被分为哪一类要由各分类器权值决定。
　　以做错题为例做一个形象的比喻：
　　做正确的题，下次少做点，反正都会了；
　　做错的题，下次多做点，集中在错题上；
　　随着学习的深入，做错的题会越来越少。
　　算法优点：
　　· 很好的利用了弱分类器进行级联；
　　· 可以将不同的分类算法作为弱分类器；
　　· AdaBoost具有很高的精度；
　　· 相对于bagging算法和Random Forest算法，AdaBoost充分考虑的每个分类器的权重；
　　算法缺点：
　　· AdaBoost迭代次数也就是弱分类器数目不太好设定，可以使用交叉验证来进行确定；
　　· 数据不平衡导致分类精度下降；
　　· 训练比较耗时，每次重新选择当前分类器最好切分点。
　　5.PageRank算法
　　PageRank，网页排名，又称佩奇排名。谷歌的两位创始人，佩奇 (Larry Page) 和布林 (Sergey Brin) 开始了对网页排序问题的研究。他们的借鉴了学术界评判学术论文重要性的通用方法， 那就是看论文的引用次数。由此想到网页的重要性也可以根据这种方法来评价。
　　于是PageRank的核心思想就诞生了，非常简单：
　　如果一个网页被很多其他网页链接到的话说明这个网页比较重要，也就是PageRank值会相对较高；
　　如果一个PageRank值很高的网页链接到一个其他的网页，那么被链接到的网页的PageRank值会相应地因此而提高。
　　算法优点：
　　是一个与查询无关的静态算法，全部网页的PageRank值通过离线计算获得；有效降低在线查询时的计算量，极大降低了查询响应时间。
　　算法缺点：
　　· 人们的查询具有主题特征，PageRank忽略了主题相关性，导致结果的相关性和主题性减少；
　　· 旧的页面等级会比新页面高。由于即使是非常好的新页面也不会有非常多上游链接，除非它是某个网站的子网站。
　　6.EM算法(期望最大化算法)
　　EM算法全称Expectation Maximization算法，即期望最大化算法，由Arthur P. Dempster，Nan Laird和Donald Rubin 1977年正式提出，是一种在已知部分相关变量的情况下，估计未知变量的迭代算法。EM算法是最常见的隐变量估计方法，在机器学习中有极为广泛的用途，例如常被用来学习高斯混合模型（Gaussian mixture model，简称GMM）的参数；隐式马尔科夫算法（HMM）、LDA主题模型的变分推断等等。
　　EM算法包含两个步骤，E步和M步。E步也就是我们求期望的步骤，M步将E步所求的期望最大化，重复E步和M步直到收敛，也就是我们估计的模型参数不再发生变化或者变化幅度很小，这就是EM算法的基本概括。
　　以分菜为例做一个形象的比喻。
　　比如说食堂的大师傅炒了一份菜，要等分成两份给两个人吃，显然没有必要拿来天平一点一点的精确的去称分量，最简单的办法是先随意的把菜分到两个碗中，然后观察是否一样多，把比较多的那一份取出一点放到另一个碗中，这个过程一直法代地执行下去，直到大家看不出两个碗所究纳的菜有什么分量上的不同为止。EM算法就是这样，假设我们估计知道A和B两个参数，在开始状态下二者都是未知的，并且知道了A的信息就可以得到B的信息，反过来知道了B也就得到了A。可以考虑首先赋予A某种初值，以此得到B的估计值，然后从B的当前值出发，重新估计A的取值，这个过程一直持续到收敛为止。
　　算法优点：
　　· 聚类；
　　· 算法计算结果稳定、准确；
　　· EM算法自收敛，既不需要事先设定类别，也不需要数据间的两两比较合并等操作。
　　算法缺点：
　　· 对初始化数据敏感；
　　· EM算法计算复杂，收敛较慢，不适于大规模数据集和高维数据；
　　· 当所要优化的函数不是凸函数时，EM算法容易给出局部最优解，而不是全局最优解。
　　7.Apriori算法
　　Apriori 算法是一种最有影响力的挖掘布尔关联规则的频繁项集的算法，它是由Rakesh Agrawal 和RamakrishnanSkrikant 提出的，例如著名的购物篮问题中顾客在买完尿布之后通常会买啤酒。作为第一个关联规则挖掘算法，它开创性的使用了基于支持度的剪枝技术。
　　它使用一种称作逐层搜索的迭代方法，k- 项集用于探索（k+1）- 项集。首先，找出频繁 1- 项集的集合。该集合记作L1。L1 用于找频繁2- 项集的集合 L2，而L2 用于找L2，如此下去，直到不能找到 k- 项集。每找一个 Lk 需要一次数据库扫描。为提高频繁项集逐层产生的效率，一种称作Apriori 性质的重要性质，用于压缩搜索空间。其运行定理在于一是频繁项集的所有非空子集都必须也是频繁的，二是非频繁项集的所有父集都是非频繁的。
　　Apriori算法过程分为两个步骤：
　　第一步通过迭代，检索出事务数据库中的所有频繁项集，即支持度不低于用户设定的阈值的项集；
　　第二步利用频繁项集构造出满足用户最小信任度的规则。
　　算法优点：
　　· 适合稀疏数据集；
　　· 算法原理简单，易实现；
　　· 适合事务数据库的关联规则挖掘。
　　算法缺点：
　　· 可能产生庞大的候选集；
　　· 算法需多次遍历数据集，算法效率低，耗时。
　　8.SVM算法
　　支持向量机，英文全称＂Support Vector Machines＂（简称 SVM），它是机器学习中最常用的一种＂分类算法＂，可广泛地应用于统计分类以及回归分析。它是将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面，分隔超平面使两个平行超平面的距离最大化。假定平行超平面间的距离或差距越大，分类器的总误差越小。
　　对于支持向量机而言有三个重要构件，分别是：最大间隔、高维映射、核函数。
　　上述三者是 SVM 支持向量机的核心，用一句话来总结这三个部件的作用，那就是＂最大间隔是标尺，高维映射是关键，最终结论看核函数＂。
　　算法优点：
　　· 使用核函数可以向高维空间进行映射；
　　· 使用核函数可以解决非线性的分类；
　　· 分类思想很简单，就是将样本与决策面的间隔最大化。
　　· 分类效果较好
　　算法缺点：
　　· SVM算法对大规模训练样本难以实施；
　　· 用SVM解决多分类问题存在困难；
　　· 对缺失数据敏感，对参数和核函数的选择敏感。
　　9.K均值聚类算法
　　k均值聚类算法（k-means clustering algorithm）是一种迭代求解的聚类分析算法，其步骤是，预将数据分为K组，则随机选取K个对象作为初始的聚类中心，然后计算每个对象与各个种子聚类中心之间的距离，把每个对象分配给距离它最近的聚类中心。聚类中心以及分配给它们的对象就代表一个聚类。每分配一个样本，聚类的聚类中心会根据聚类中现有的对象被重新计算。这个过程将不断重复直到满足某个终止条件。终止条件可以是没有（或最小数目）对象被重新分配给不同的聚类，没有（或最小数目）聚类中心再发生变化，误差平方和局部最小。
　　算法优点：
　　· 是解决聚类问题的一种经典算法，简单、快速；
　　· 对处理大数据集，该算法保持可伸缩性和高效性；
　　· 当簇接近高斯分布时，它的效果较好。
　　算法缺点：
　　· 在 K-means 算法中 K 是事先给定的，K 值的选定难以估计；
　　· 在 K-means 算法中，首先需要根据初始聚类中心来确定一个初始划分，然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响，一旦初始值选择的不好，可能无法得到有效的聚类结果(可能会陷入死循环)；
　　· 该算法需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心，因此当数据量非常大时，算法的时间开销是非常大的；
　　· 若簇中含有异常点，将导致均值偏离严重(即:对噪声和孤立点数据敏感)
　　10.   线性回归算法   Linear Regression
　　回归分析（Regression Analysis）是统计学的数据分析方法，目的在于了解两个或多个变量间是否相关、相关方向与强度，并建立数学模型以便观察特定变量来预测其它变量的变化情况。
　　线性回归算法（Linear Regression）的建模过程就是使用数据点来寻找最佳拟合线。公式，y = mx + c，其中 y 是因变量，x 是自变量，利用给定的数据集求 m 和 c 的值。
　　线性回归又分为两种类型，即 简单线性回归（simple linear regression)，只有 1 个自变量；多变量回归（multiple regression)，至少两组以上自变量。
　　算法优点：
　　· 思想简单，实现容易。建模迅速，对于小数据量、简单的关系很有效；
　　· 是许多强大的非线性模型的基础；
　　· 线性回归模型十分容易理解，结果具有很好的可解释性，有利于决策分析；
　　· 蕴含机器学习中的很多重要思想；
　　· 能解决回归问题。
　　算法缺点：
　　· 对于非线性数据或者数据特征间具有相关性多项式回归难以建模；
　　· 难以很好地表达高度复杂的数据。
　　经典的机器学习算法还有很多，欢迎大家补充交流。