数学技术之算法概论篇（5）

④机器学习与数据挖掘中的十大经典算法

数年前，有人动议在机器学习与数据挖掘领域中找出十大算法，即建立该领域算法的一个top10。后在该领域选出部分专家学者，经他们提名、汇总和筛选，在分类，聚类，图挖掘，关联分析等领域共选出18个算法。对这18个算法在更广泛的领域内，一人一票，最终得出了其中的10个作为最后的算法。应该说，受时间、经验、领域和参选人数等诸多限制，入选的十大算法，不一定个个都是最优秀的；受条件所限没有入选的有些算法，也不能说是不好的。下面列出这十大算法，供参考。
一、分类决策树算法C4.5
C4.5，是机器学习算法中的一个分类决策树算法，它是决策树(决策树，就是做决策的节点间的组织方式像一棵倒栽树)核心算法ID3的改进算法，所以基本上了解了一半决策树构造方法就能构造它。决策树构造方法其实就是每次选择一个好的特征以及分裂点作为当前节点的分类条件。
C4.5相比于ID3改进的地方有：
1、用信息增益率选择属性。
ID3选择属性用的是子树的信息增益，这里可以用很多方法来定义信息，ID3使用的是熵，一种不纯度度量准则，也就是熵的变化值，而C4.5用的是信息增益率。区别就在于一个是信息增益，一个是信息增益率。
2、 在树构造过程中进行剪枝，在构造决策树的时候，那些挂着几个元素的节点，不考虑最好，不然容易导致过拟。
3、能对非离散数据和不完整数据进行处理。
二、 K平均算法
K平均算法（k-means algorithm）是一个聚类算法，把n个分类对象根据它们的属性分为k类（k
近似的k平均算法已经被设计用于原始数据子集的计算。
从算法的表现上来说，它并不保证一定得到全局最优解，最终解的质量很大程度上取决于初始化的分组。由于该算法的速度很快，因此常用的一种方法是多次运行k平均算法，选择最优解。
算法缺点是，分组的数目k是一个输入参数，不合适的k可能返回较差的结果。另外，算法还假设均方误差是计算群组分散度的最佳参数。
三、支持向量机算法
支持向量机(Support Vector Machine)算法，简记为SVM，是一种監督式學習的方法，广泛用于统计分类以及回归分析中。
支持向量机属于一般化线性分类器。这类分类器的特点是他们能够同时最小化经验误差与最大化几何边缘区，因此支持向量机也被称为最大边缘区分类器。
Vapnik等人在多年研究统计学习理论基础上对线性分类器提出了另一种设计最佳准则。其原理也从线性可分说起，然后扩展到线性不可分的情况，甚至扩展到使用非线性函数中去。支持向量机是一种有很深理论背景的一种新方法。
SVM的主要思想可以概括为两点：(1)它是针对线性可分情况进行分析，对于线性不可分的情况，通过使用非线性映射算法将低维输入空间线性不可分的样本转化为高维特征空间使其线性可分，从而使得高维特征空间采用线性算法对样本的非线性特征进行线性分析成为可能；(2)它基于结构风险最小化理论之上，在特征空间中建构最优分割超平面，使得学习器得到全局最优化，并且在整个样本空间的期望风险以某个概率满足一定上界。
四、The Apriori algorithm
Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法，核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。
Apriori演算法所使用的前置统计量包括：
？最大规则物件数：规则中物件组所包含的最大物件数量；
？最小支援：规则中物件或是物件组必顸符合的最低案例数；
？最小信心水准：计算规则所必须符合的最低信心水准门槛。
该算法的基本思想是：首先找出所有的频集，这些频集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。然后使用第1步找到的频集产生期望的规则，产生只包含集合的项的所有规则，其中每一条规则的右部只有一项，这里采用的是中规则的定义。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。为了生成所有频集，使用了递推方法。
可能产生大量的候选集，以及可能需要重复扫描数据库，是Apriori算法的两大缺点。
五、最大期望(EM) 算法
在统计计算中，最大期望（EM，Expectation–Maximization）算法是在概率模型中寻找参数最大似然估计的算法，其中概率模型依赖于无法观测的隐藏变量。最大期望经常用在机器学习和计算机视觉的数据集聚领域。最大期望算法经过两个步骤交替进行计算，第一步是计算期望（E），也就是将隐藏变量象能够观测到的一样包含在内从而计算最大似然的期望值；第二步是最大化（M），也就是最大化在E步上找到的最大似然的期望值从而计算参数的最大似然估计。M步上找到的参数然后用于另外一个E步计算，这个过程不断交替进行。
六、Page Rank 算法
Page Rank是Google算法的重要内容。2001年9月被授予美国专利，专利人是Google创始人之一拉里？佩奇(Larry Page)。因此，Page Rank里的page不是网页，而是佩奇，即这个方法是以佩奇来命名的。Page Rank根据网站的外部链接和内部链接的数量和质量，衡量网站的价值。Page Rank背后的概念是每个到页面的链接都是对该页面的一次投票，被链接的越多，就意味着被其他网站投票越多。这就是所谓的“链接流行度”——衡量多少人愿意将他们的网站和你的网站挂钩。Page Rank这个概念引自学术中一篇论文的被引述的频度——即被别人引述的次数越多，一般判断这篇论文的权威性就越高。
七、Ada Boost 迭代算法
Ada boost是一种迭代算法，其核心思想是针对同一个训练集训练不同的分类器(弱分类器)，然后把这些弱分类器集合起来，构成一个更强的最终分类器(强分类器)。其算法本身是通过改变数据分布来实现的，它根据每次训练集之中每个样本的分类是否正确，以及上次的总体分类的准确率，来确定每个样本的权值。将修改过权值的新数据集送给下层分类器进行训练，最后将每次训练得到的分类器最后融合起来，作为最后的决策分类器。使用Ada boost分类器可以排除一些不必要的训练数据特徵，并将关键放在关键的训练数据上面。
目前，对Ada boost算法的研究以及应用大多集中于分类问题，同时近年也出现了一些在回归问题上的应用。就其应用Ada boost系列主要解决两类问题：多类单标签问题、多类多标签问题、大类单标签问题，回归问题。它用全部的训练样本进行学习。
该算法其实是一个简单的弱分类算法提升过程，这个过程通过不断的训练，可以提高对数据的分类能力。整个过程如下所示：
1. 先通过对N个训练样本的学习得到第一个弱分类器；
2. 将分错的样本和其他的新数据一起构成一个新的N个的训练样本，通过对这个样本的学习得到第二个弱分类器；
3. 将和都分错了的样本加上其他的新样本构成另一个新的N个的训练样本，通过对这个样本的学习得到第三个弱分类器；
4. 最终经过提升的强分类器，即某个数据被分为哪一类要通过多数表决。
对于Ada boosting算法，存在两个问题：
1. 如何调整训练集，使得在训练集上训练的弱分类器得以进行；
2. 如何将训练得到的各个弱分类器联合起来形成强分类器。
针对以上两个问题，Ada boost算法进行了调整：
1. 使用加权后选取的训练数据代替随机选取的训练样本，这样将训练的焦点集中在比较难分的训练数据样本上；
2. 将弱分类器联合起来，使用加权的投票机制代替平均投票机制。让分类效果好的弱分类器具有较大的权重，而分类效果差的分类器具有较小的权重。
Ada boost算法是Freund和Schapire根据在线分配算法提出的，他们详细分析了Ada boost算法错误率的上界，以及为了使强分类器达到错误率，算法所需要的最多迭代次数等相关问题。与Boosting算法不同的是，Ada boost算法不需要预先知道弱学习算法学习正确率的下限即弱分类器的误差，并且最后得到的强分类器的分类精度依赖于所有弱分类器的分类精度，这样可以深入挖掘弱分类器算法的能力。
Ada boost算法中不同的训练集是通过调整每个样本对应的权重来实现的。开始时，每个样本对应的权重是相同的，即其中n为样本个数，在此样本分布下训练出一弱分类器。对于分类错误的样本，加大其对应的权重；而对于分类正确的样本，降低其权重，这样分错的样本就被突出出来，从而得到一个新的样本分布。在新的样本分布下，再次对弱分类器进行训练，得到弱分类器。依次类推，经过T次循环，得到T个弱分类器，把这T个弱分类器按一定的权重叠加起来，得到最终想要的强分类器。
Ada boost算法的具体步骤如下：
1.给定训练样本集，其中分别对应于正例样本和负例样本；为训练的最大循环次数；
2.初始化样本权重，即为训练样本的初始概率分布；
3.第一次迭代：
(1) 训练样本的概率分布下，训练弱分类器；
(2) 计算弱分类器的错误率；
(3) 选取；
(4) 更新样本权重；
(5) 最终得到的强分类器。
八、kNN: k-nearest neighbor classification 最近邻分类算法
K最近邻(k-Nearest Neighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。
KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值，如权值与距离成正比。
该算法在分类时主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。因此可以采用权值的方法（和该样本距离小的邻居权值大）来改进。该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。
九、Naive Bayes？ 朴素贝叶斯算法
在众多的分类模型中，应用最为广泛的两种分类模型是决策树模型和朴素贝叶斯模型(Naive Bayesian Model，NBC)。朴素贝叶斯模型发源于古典数学理论，有着坚实的数学基础以及稳定的分类效率。同时，NBC模型所需估计的参数较少，对缺失数据不太敏感，算法也比较简单。理论上，NBC模型与其他分类方法相比具有最小的误差率，但实际上并非总是如此，这是因为NBC模型假设属性之间相互独立，这个假设在实际应用中往往是不成立的，这给NBC模型的正确分类带来了一定影响。在属性个数比较多或者属性之间相关性较大时，NBC模型的分类效率比不上决策树模型。而在属性相关性较小时，NBC模型的性能最为良好。
十、CART: 分类与回归树算法
分类与回归树算法（CART，Classification and Regression Trees）是分类数据挖掘算法的一种，有两个关键的思想：第一个是关于递归地划分自变量空间的想法；第二个想法是用验证数据进行剪枝。
让我们用变量y表示因变量（分类变量），用x ₁，x ₂，x ₃，...，x _p表示自变量。通过递归的方式把关于变量x的p维空间划分为不重叠的矩形。这个划分是以递归方式完成的。首先，一个自变量被选择，比如x _i和x _i的一个值s _i，比方说选择s _i把p维空间为两部分：一部分是p维的超矩形，其中包含的点都满足x _i≤s _i，另一个p维超矩形包含所有的点满足x _i>s _i。接着，这两部分中的一个部分通过选择一个变量和该变量的划分值以相似的方式被划分。这导致了三个矩形区域（从这里往后我们把超矩形都说成矩形）。随着这个过程的持续，我们得到的矩形越来越小。这个想法是把整个x空间划分为矩形，其中的每个小矩形都尽可能是同构的或“纯”的。“纯”的意思是（矩形）所包含的点都属于同一类。我们认为包含的点都只属于一个类（当然，这不总是可能的，因为经常存在一些属于不同类的点，但这些点的自变量有完全相同的值）。
分类与回归树CART描述给定预测向量值X后，变量Y条件分布的一个灵活的方法。该模型使用了二叉树将预测空间递归划分为若干子集，Y在这些子集的分布是连续均匀的。树中的叶节点对应着划分的不同区域，划分是由与每个内部节点相关的分支规则确定的。通过从树根到叶节点移动，一个预测样本被赋予一个惟一的叶节点，Y在该节点上的条件分布也被确定。CART模型最旱由Breman等人提出并己在统计学领域普遍应用。
剪枝是决策树停止分支的方法之一，分为预先剪枝和后剪枝两种。
预先剪枝是在树的生长过程中设定一个指标，当达到该指标时就停止生长，这样做容易产生“视界局限”，就是一旦停止分支，使得节点N成为叶节点，就断绝了其后继节点进行“好”的分支操作的任何可能性。不严格的说这些已停止的分支会误导学习算法，导致产生的树不纯度降差最大的地方过分靠近根节点。
后剪枝中树首先要充分生长，直到叶节点都有最小的不纯度值为止，因而可以克服“视界局限”。然后对所有相邻的成对叶节点考虑是否消去它们，如果消去能引起令人满意的不纯度增长，那么执行消去，并令它们的公共父节点成为新的叶节点。这种“合并”叶节点的做法和节点分支的过程恰好相反，经过剪枝后叶节点常常会分布在很宽的层次上，树也变得非平衡。后剪枝技术的优点是克服了“视界局限”效应，而且无需保留部分样本用于交叉验证，所以可以充分利用全部训练集的信息。但后剪枝的计算量比预剪枝方法大得多，特别是在大样本集中，不过对于小样本的情况，后剪枝方法还是优于预剪枝方法的。