图挖掘与深度学习算法
近年来由于大数据的兴起，和一些优化算法上的突破，深度学习迅速崛起，影响了很多机器学习的领域，比如图像识别，语音识别，自然语言处理（NLP）等等。受自然语言处理中的词嵌入（Word embedding）模型的启发，一类被称为网络嵌入（Network embedding）的社交网路模型越来越受到学术和工业界的重视。
图挖掘算法
Page ranking, label propagation, connected component, triangle count
Page ranking
PageRank算法是一种链接分析算法，由Google提出并用于标识网页重要性。PageRank算法基于两个假设：
1）入链数量假设：如果一个网页的入链数量越多，则其重要程度越高。
2）入链质量假设：高质量的网页为其链接的页面带去更多权重。
以上两个假设分别对应小白规则一和规则二。基于这两条假设，PageRank算法为每个页面设置初始权重值，根据网页间的链接关系，在多轮迭代中更新每个网页的权重，直至各页面的权重值稳定。不考虑作弊的情况，我们通常将最终权重值越高的节点视为越可靠网页。
Label propagation
标签传播算法（label propagation）的核心思想非常简单：相似的数据应该具有相同的label。LP算法包括两大步骤：1）构造相似矩阵；2）勇敢的传播吧。
Label Propagation算法是一种基于标签传播的局部社区划分算法。对于网络中的每一个节点，在初始阶段，Label Propagation算法对每一个节点一个唯一的标签，在每一个迭代的过程中，每一个节点根据与其相连的节点所属的标签改变自己的标签，更改的原则是选择与其相连的节点中所属标签最多的社区标签为自己的社区标签，这便是标签传播的含义。随着社区标签的不断传播，最终紧密连接的节点将有共同的标签。
Label Propagation算法最大的优点是其算法过程比较简单，想比较于优化模块度的过程，算法速度非常快。Label Propagation算法利用网络的结构指导标签的传播过程，在这个过程中无需优化任何函数。在算法开始前我们不必要知道社区的个数，随着算法的迭代，在最终的过程中，算法将自己决定社区的个数。
连通分支
连通分支（Connected Component）是指：在一个图中，某个子图的任意两点有边连接，并且该子图去剩下的任何点都没有边相连。
Triangle count 三角形计数
Triangle Count在社交网络分析中是非常有用的。这个三角形是一个三结点的小图，其中结点两两相连。假如，在Facebook上，你认识两个校友，而这两个校友彼此有相互认识，那么你们三个就组成了一个三角形。像这样的，社交网络拥有越多的三角形，其联系也就业紧密。
Triangle Count的算法思想如下：
• 计算每个结点的邻结点，
• 统计对每条边计算交集，并找出交集中id大于前两个结点id的结点，
• 对每个结点统计Triangle总数，注意只统计符合计算方向的Triangle Count。
深度学习Deep Learning
简单来说，深度学习模型是大而深的人工神经网络。 神经网络（“NN”）可以很好地呈现在有向无环图中：输入层接收信号向量; 一个或多个隐藏层处理前一层的输出。
因为现在有了大量数据和巨大计算能力， 深度学习模型越来越受到人们的关注。大而深的神经网络在每层中有更多的层+更多的节点，这导致要调整的指数级更多的参数。 没有足够的数据，我们无法有效地学习参数。 如果没有强大的计算机，学习将会过于缓慢和不足。
下面是几种主要的深度学习模型
1.Convolutional Neural Network 卷积神经网络
卷积神经网络是“CNN”的缩写，是一种前馈人工神经网络，其神经元之间的连接模式受到视觉皮层系统组织的启发。初级视觉皮层（V1）从视网膜的原始视觉输入中进行边缘检测。次级视觉皮层（V2），也称为前皮质，接收来自V1的边缘特征，并提取简单的视觉特性，例如方向，空间频率和颜色。 可视区域V4处理更复杂的对象属性。所有处理过的视觉特征都流入最终逻辑单元，即颞下回（IT），用于对象识别。
卷积是一个数学术语，这里指的是两个矩阵之间的操作。 卷积层具有固定的小矩阵，也称为内核或滤波器。
卷积和合并（或上图中的“子采样”）层的作用类似于V1，V2和V4视觉皮层单元，响应特征提取。 对象识别推理发生在后来的全连接层中，这些层采用了提取的特征。
递归神经网络 Recurrent Neural Network
序列模型通常被设计为将输入序列转换为输出序列。 递归神经网络，简称“RNN”，适用于此目的，并在手写识别，语音识别和机器翻译等问题上有了巨大的改进。
自动编码 Autoencode
自动编码器用于无监督学习, 它旨在学习用低维数据表示高维数据集。
自动编码器模型试图学习近似函数f（x）≈x 重现输入数据。但是，它受到中间瓶颈层的限制，节点数量非常少。 由于容量有限，模型被迫形成非常有效的数据编码，这实际上是我们学到的低维代码。
强化（深度）学习Reinforcement (Deep) Learning
RL是机器学习的子领域，它允许机器和软件代理自动确定给定上下文中的最佳行为，目标是最大化由给定度量测量的长期性能。深度增强学习Deep Reinforcement Learning是将深度学习与增强学习结合起来从而实现从Perception感知到Action动作的端对端学习的一种全新的算法。简单的说，就是和人类一样，输入感知信息比如视觉，然后通过深度神经网络，直接输出动作，中间没有hand-crafted工作。深度增强学习具备使机器人实现完全自主的学习一种甚至多种技能的潜力。
上面这张图（来自David Silver）可以很清楚的看到整个交互过程。事实上，这就是人与环境交互的一种模型化表示。在每个时间点time-step Agent都会从可以选择的动作集合A中选择一个执行.这个动作集合可以是连续的比如机器人的控制也可以是离散的比如游戏中的几个按键。动作集合的数量将直接影响整个任务的求解难度，因此DeepMind才从玩最简单的游戏做起。
那么知道了整个过程，任务的目标就出来了，那就是要能获取尽可能多的reward。没有目标，控制也就无从谈起，因此，获取reward就是一个量化的标准，reward越多，就表示执行得越好。每个时间片，Agent都是根据当前的观察来确定下一步的动作。每次的观察就作为Agent的所处的状态state，因此，状态State和动作Action存在映射关系，也就是一个state可以对应一个action，或者对应不同动作的概率（常常用概率来表示，概率最高的就是最值得执行的动作）。那么state到action的过程就称之为一个策略Policy。
生成性对抗网络Generative Adversarial Network
生成对抗网络（GAN）是由两个网络组成的深度神经网络体系结构，将一个网络与另一个网络相互对立（因此称为“对抗性”）。
GAN的潜力巨大，因为他们可以学习模仿任何数据分布。 也就是说，GAN可以被教导在任何领域创造类似于我们自己的世界：图像，音乐，演讲，散文。 从某种意义上说，他们是机器人艺术家，他们的作品令人印象深刻 - 甚至令人痛苦。要理解GAN，你应该知道生成算法是如何工作的，为此，将它们与判别算法进行对比是有益的。 判别算法试图对输入数据进行分类; 也就是说，给定数据实例的功能，它们会预测数据所属的标签或类别。
例如，给定电子邮件中的所有单词，判别算法可以预测该邮件是垃圾邮件还是非垃圾邮件。 垃圾邮件是标签之一，从电子邮件收集的单词包是构成输入数据的功能。 当以数学方式表达此问题时，标签称为y，并且要素称为x。 公式p（y | x）用于表示“y给定x的概率”，在这种情况下，它将转换为“基于邮件的内容，这份电子邮件是垃圾邮件的概率”。
因此，判别算法将特征映射到标签。 他们只关心这种相关性。 考虑生成算法的一种方法是他们做相反的事情。 他们尝试预测给定某个标签的特征，而不是预测给定某些特征的标签。
生成算法试图回答的问题是：假设这封电子邮件是垃圾邮件，这些功能的可能性有多大？ 虽然判别模型关心y和x之间的关系，但是生成模型关心“你如何得到x。”它们允许你捕获p（x | y），x给出y的概率，或给出类的特征的概率。 （也就是说，生成算法也可以用作分类器。恰好它们可以做的不仅仅是对输入数据进行分类。）
另一种思考方式是将判别与生成区分开来，如下所示：
判别模型学习了类之间的界限
生成模型模拟各个类的分布
一个神经网络，称为生成器，生成新的数据实例，而另一个神经网络，鉴别器，评估它们的真实性; 即，鉴别器决定它所评论的每个数据实例是否属于实际训练数据集。
以下是GAN采取的步骤：
生成器接收随机数并返回图像。
将生成的图像与从实际数据集中获取的图像流一起馈送到鉴别器中。
鉴别器接收真实和假图像并返回概率，0到1之间的数字，1表示真实性的预测，0表示假。
所以你有一个双反馈循环：
鉴别器处于反馈循环中，具有图像的基本事实，我们知道这一点。
发生器与鉴别器一起处于反馈回路中。
你可以将GAN看作是猫与老鼠游戏中伪造者和警察的组合，其中伪造者正在学习传递虚假笔记，并且警察正在学习如何检测它们。两者都是动态的;也就是警察也在训练中（也许中央银行正在标记掉掉的账单），并且每一方都在不断升级中学习对方的方法。
鉴别器网络是标准卷积网络，可以对馈送给它的图像进行分类，二项分类器将图像标记为真实或伪造。在某种意义上，生成器是反卷积网络：当标准卷积分类器采用图像并对其进行下采样以产生概率时，生成器采用随机噪声矢量并将其上采样到图像。第一个通过下采样技术（如maxpooling）丢弃数据，第二个生成新数据。
两个网都试图在零和游戏中优化不同的和相反的目标函数或损失函数。这实际上是一个演员评论模型。当鉴别器改变其行为时，发生器也是如此，反之亦然。他们的损失相互冲突。
Deep learning 用途
1. 分类 classification
所有分类任务都取决于标记的数据集; 也就是说，人类必须将他们的知识传递给数据集，以便神经元学习标签和数据之间的相关性。 这被称为监督学习。
检测面部，识别图像中的人物，识别面部表情（生气，快乐）
识别图像中的物体（停车标志，行人，车道标记......）
识别视频中的手势
检测语音，识别发言者，将语音转录为文本，识别语音中的情感
将文本分类为垃圾邮件（在电子邮件中）或欺诈性（在保险索赔中）; 识别文本中的情绪（客户反馈）
人类可以生成的任何标签，您关心的任何结果以及与数据相关的任何结果都可用于训练神经网络。
2. 聚类 Clustering
聚类或分组是对相似性的检测。 深度学习不需要标签来检测相似性。 没有标签的学习被称为无监督学习。 未标记的数据是世界上大多数数据。 机器学习的一个定律是：算法可以训练的数据越多，它就越准确。 因此，无监督学习有可能产生高度准确的模型。
搜索：比较文档，图像或声音以表示类似的项目。
异常检测：检测相似性的另一面是检测异常或异常行为。 在许多情况下，异常行为与您想要检测和预防的事物高度相关，例如欺诈。
3. 预测分析：回归 Predictive Analytics: Regressions
通过分类，深度学习能够在例如图像中的像素和人的名称之间建立相关性。 你可以称之为静态预测。 出于同样的原因，暴露于足够的正确数据，深度学习能够建立当前事件和未来事件之间的相关性。 它可以在过去和未来之间进行回归。 从某种意义上说，未来的事件就像标签一样。 深度学习并不一定关心时间，或者事情尚未发生。 给定时间序列，深度学习可以读取一串数字并预测下一个最可能发生的数字。
硬件故障（数据中心，制造，运输）
健康故障（中风，基于重要统计数据的心脏病发作和来自可穿戴设备的数据）
客户流失（根据Web活动和元数据预测客户离开的可能性）
员工流动（同上，但员工）
我们越能预测，我们就越能预防。 通过神经网络，我们正在走向一个意外减少的世界。 不是零意外，只是略微减少。 我们也正在走向一个智能代理的世界，它将神经网络与强化学习等其他算法相结合，以实现目标。
工具
Tensorflow
TensorFlow可能是最着名的深度学习框架; 它由Google开发和维护。 它是用C ++ / Python编写的，提供Python，Java，Go和JavaScript API。目前，TensorFlow聚集了最大的深度学习社区，因此有很多视频，在线课程，教程等等。 它支持在多个GPU上运行模型，甚至可以在计算集群中的多台机器上分割单个计算图。
PyTorch
PyTorch是由Facebook的人工智能研究小组发布的，基于Torch（之前的Facebook Lua框架）。 它是动态图的主要代表。PyTorch是pythonic，非常适合开发人员。 PyTorch中的内存使用对任何神经网络都非常有效。 它也被称为比TensorFlow快一点。
Gradient Boosting Decision Tree（GBDT） 梯度下降树
决策树是一种基本的分类与回归方法。决策树模型具有分类速度快，模型容易可视化的解释，但是同时是也有容易发生过拟合，虽然有剪枝，但也是差强人意。
提升方法（boosting）在分类问题中，它通过改变训练样本的权重（增加分错样本的权重，减小分队样本的的权重），学习多个分类器，并将这些分类器线性组合，提高分类器性能。boosting数学表示为：
其中w是权重，ϕ是弱分类器的集合，可以看出最终就是基函数的线性组合。于是决策树与boosting结合产生许多算法，主要有提升树、GBDT等。
1.1 Gradient boosting
Gradient Boosting是一种Boosting的方法，它主要的思想是，每一次建立模型是在之前建立模型损失函数的梯度下降方向。损失函数是评价模型性能（一般为拟合程度+正则项），认为损失函数越小，性能越好。而让损失函数持续下降，就能使得模型不断改性提升性能，其最好的方法就是使损失函数沿着梯度方向下降（讲道理梯度方向上下降最快）。Gradient Boost是一个框架，里面可以套入很多不同的算法
1.2 提升树-boosting tree
以决策树为基函数的提升方法称为提升树，其决策树可以是分类树OR回归树。提升树模型可以表
示为决策树的加法模型。
2. Gradient boosting decision tree (GBDT) 梯度下降树
梯度提升决策树GBDT(Gradient Boosting Decision Tree)最早由Friedman文章“Greedy Function Approximation: A Gradient Boosting Machine”提出这个概念。GBDT中的树用的是CART回归树（不是分类树），GBDT用来做 回归预测，调整后也可以用于分类。由于GBDT中的CART树，在模型训练的时候，需要逐个训练样本进行计算，模型的训练时间相当之长。因此，这个也决定了GBDT不适合实时的线上训练，更加适用于离散的场景。
GBDT的思想使其具有天然优势可以发现多种有区分性的特征以及特征组合。Facebook(Practical Lessons From Predicting Clicks on Ads at Facebook)使用其来自动发现有效的特征、特征组合，来作为LR模型中的特征，以提高 CTR预估（Click-Through Rate Prediction）的准确性。GBDT在万能的淘宝搜索及预测业务上也发挥了重要作用。
GBDT 虽然是个强力的模型，但却有着一个致命的缺陷，不能用类似 mini batch 的方式来训练，需要对数据进行无数次的遍历。如果想要速度，就需要把数据都预加载在内存中，但这样数据就会受限于内存的大小；如果想要训练更多的数据，就要使用外存版本的决策树算法。虽然外存算法也有较多优化，SSD 也在普及，但在频繁的 IO 下，速度还是比较慢的。
工作过程实例
以年龄预测为例，A,B,C,D四个人，他们的年龄分别是14,16,24,26。其中A、B分别是高一和高三学生；C,D分别是应届毕业生和工作两年的员工。如果是用一棵传统的回归决策树来训练，会得到如下图1所示结果
现在我们使用GBDT来做这件事，由于数据太少，我们限定叶子节点做多有两个，即每棵树都只有一个分枝，并且限定只学两棵树。我们会得到如下图2所示结果：
在第一棵树分枝和图1一样，由于A,B年龄较为相近，C,D年龄较为相近，他们被分为两拨，每拨用平均年龄作为预测值。此时计算残差（残差的意思就是： A的预测值 + A的残差 = A的实际值），所以A的残差就是16-15=1（注意，A的预测值是指前面所有树累加的和，这里前面只有一棵树所以直接是15，如果还有树则需要都累加起来作为A的预测值）。进而得到A,B,C,D的残差分别为-1,1，-1,1。然后我们拿残差替代A,B,C,D的原值，到第二棵树去学习，如果我们的预测值和它们的残差相等，则只需把第二棵树的结论累加到第一棵树上就能得到真实年龄了。这里的数据显然是我可以做的，第二棵树只有两个值1和-1，直接分成两个节点。此时所有人的残差都是0，即每个人都得到了真实的预测值。
换句话说，现在A,B,C,D的预测值都和真实年龄一致了。：
A: 14岁高一学生，购物较少，经常问学长问题；预测年龄A = 15 – 1 = 14
B: 16岁高三学生；购物较少，经常被学弟问问题；预测年龄B = 15 + 1 = 16
C: 24岁应届毕业生；购物较多，经常问师兄问题；预测年龄C = 25 – 1 = 24
D: 26岁工作两年员工；购物较多，经常被师弟问问题；预测年龄D = 25 + 1 = 26
LightGBM
LightGBM采用Histogram算法，其思想是将连续的浮点特征离散成k个离散值，并构造宽度为k的Histogram。然后遍历训练数据，统计每个离散值在直方图中的累计统计量。在进行特征选择时，只需要根据直方图的离散值，遍历寻找最优的分割点。
LightGBM增加了针对于类别特征的决策规则，这在决策树上也很好实现。主要的思想是，在对类别特征计算分割增益的时候，不是按照数值特征那样由一个阈值进行切分，而是直接把其中一个类别当成一类，其他的类别当成另一类。这实际上与0/1展开的效果是一样的。
为了能让 GBDT 高效地用上更多的数据，我们把思路转向了分布式 GBDT， 然后就有了 LightGBM。设计的思路主要是两点，1. 单个机器在不牺牲速度的情况下，尽可能多地用上更多的数据；2.多机并行的时候，通信的代价尽可能地低，并且在计算上可以做到线性加速。
基于这两个需求，LightGBM 选择了基于 histogram 的决策树算法。相比于另一个主流的算法 pre-sorted（如 xgboost 中的 exact 算法），histogram 在内存消耗和计算代价上都有不少优势。
Pre-sorted 算法需要的内存约是训练数据的两倍(2 * #data * #features
* 4Bytes)，它需要用32位浮点来保存 feature value，并且对每一列特征，都需要一个额外的排好序的索引，这也需要32位的存储空间。对于 histogram 算法，则只需要(#data
* #features * 1Bytes)的内存消耗，仅为 pre-sorted算法的1/8。因为 histogram 算法仅需要存储 feature
bin value (离散化后的数值)，不需要原始的 feature value，也不用排序，而 bin
value 用 uint8_t (256bins) 的类型一般也就足够了。
在计算上的优势则主要体现在“数据分割”。决策树算法有两个主要操作组成，一个是“寻找分割点”，另一个是“数据分割”。从算法时间复杂度来看，Histogram 算法和 pre-sorted 算法在“寻找分割点”的代价是一样的，都是O(#feature*#data)。而在“数据分割”时，pre-sorted 算法需要O(#feature*#data)，而 histogram 算法是O(#data)。因为 pre-sorted 算法的每一列特征的顺序都不一样，分割的时候需要对每个特征单独进行一次分割。Histogram算法不需要排序，所有特征共享同一个索引表，分割的时候仅需对这个索引表操作一次就可以。（更新: 这一点不完全正确，pre-sorted 与 level-wise 结合的时候，其实可以共用一个索引表(row_idx_to_tree_node_idx)。然后在寻找分割点的时候，同时操作同一层的节点，省去分割的步骤。但这样做的问题是会有非常多随机访问，有很大的chche miss，速度依然很慢。）。
最后，在数据并行的时候，用 histgoram 可以大幅降低通信代价。用 pre-sorted 算法的话，通信代价是非常大的（几乎是没办法用的）。所以 xgoobst 在并行的时候也使用 histogram 进行通信。
当然， histogram 算法也有缺点，它不能找到很精确的分割点，训练误差没有 pre-sorted 好。但从实验结果来看， histogram 算法在测试集的误差和 pre-sorted 算法差异并不是很大，甚至有时候效果更好。实际上可能决策树对于分割点的精确程度并不太敏感，而且较“粗”的分割点也自带正则化的效果。
在 histogram 算法之上， LightGBM 进行进一步的优化。首先它抛弃了大多数 GBDT 工具使用的按层生长
(level-wise) 的决策树生长策略，而使用了带有深度限制的按叶子生长 (leaf-wise) 算法。 level-wise 过一次数据可以同时分裂同一层的叶子，容易进行多线程优化，不容易过拟合。但实际上level-wise是一种低效的算法，因为它不加区分的对待同一层的叶子，带来了很多没必要的开销。因为实际上很多叶子的分裂增益较低，没必要进行搜索和分裂。leaf-wise则是一种更为高效的策略，每次从当前所有叶子中，找到分裂增益最大(一般也是数据量最大)的一个叶子，然后分裂，如此循环。因此同 level-wise 相比，在分裂次数相同的情况下，leaf-wise 可以降低更多的误差，得到更好的精度。leaf-wise 的缺点是可能会长出比较深的决策树，产生过拟合。因此 LightGBM 在leaf-wise 之上增加了一个最大深度的限制，在保证高效率的同时防止过拟合。
另一个比较巧妙的优化是 histogram 做差加速。一个容易观察到的现象：一个叶子的直方图可以由它的父亲节点的直方图与它兄弟的直方图做差得到。通常构造直方图，需要遍历该叶子上的所有数据，但直方图做差仅需遍历直方图的 k 个桶。利用这个方法，LightGBM 可以在构造一个叶子的直方图后，可以用非常微小的代价得到它兄弟叶子的直方图，在速度上可以提升一倍。
随机森林算法
随机森林属于集成学习（Ensemble Learning）中的bagging算法。在集成学习中，主要分为bagging算法和boosting算法。我们先看看这两种方法的特点和区别。
bagging的算法过程如下：
• 从原始样本集中使用Bootstraping方法随机抽取n个训练样本，共进行k轮抽取，得到k个训练集。（k个训练集之间相互独立，元素可以有重复）
• 对于k个训练集，我们训练k个模型（这k个模型可以根据具体问题而定，比如决策树，knn等）
对于分类问题：由投票表决产生分类结果；对于回归问题：由k个模型预测结果的均值作为最后预测结果
boosting的算法过程如下：
• 对于训练集中的每个样本建立权值wi，表示对每个样本的关注度。当某个样本被误分类的概率很高时，需要加大对该样本的权值。
进行迭代的过程中，每一步迭代都是一个弱分类器。我们需要用某种策略将其组合，作为最终模型。（例如AdaBoost给每个弱分类器一个权值，将其线性组合最为最终分类器。误差越小的弱分类器，权值越大）
Bagging，Boosting的主要区别
• 样本选择上：Bagging采用的是Bootstrap随机有放回抽样；而Boosting每一轮的训练集是不变的，改变的只是每一个样本的权重。
• 样本权重：Bagging使用的是均匀取样，每个样本权重相等；Boosting根据错误率调整样本权重，错误率越大的样本权重越大。
• 预测函数：Bagging所有的预测函数的权重相等；Boosting中误差越小的预测函数其权重越大。
• 并行计算：Bagging各个预测函数可以并行生成；Boosting各个预测函数必须按顺序迭代生成。
下面是将决策树与这些算法框架进行结合所得到的新的算法：
1）Bagging + 决策树 = 随机森林
2）AdaBoost + 决策树 = 提升树
3）Gradient Boosting + 决策树 = GBDT
决策树
常用的决策树算法有ID3，C4.5，CART三种。3种算法的模型构建思想都十分类似，只是采用了不同的指标。决策树模型的构建过程大致如下：
ID3，C4.5决策树的生成
输入：训练集D，特征集A，阈值eps 输出：决策树T
• 若D中所有样本属于同一类Ck，则T为单节点树，将类Ck作为该结点的类标记，返回T
• 若A为空集，即没有特征作为划分依据，则T为单节点树，并将D中实例数最大的类Ck作为该结点的类标记，返回T
• 否则，计算A中各特征对D的信息增益(ID3)/信息增益比(C4.5)，选择信息增益最大的特征Ag
• 若Ag的信息增益（比）小于阈值eps，则置T为单节点树，并将D中实例数最大的类Ck作为该结点的类标记，返回T
• 否则，依照特征Ag将D划分为若干非空子集Di，将Di中实例数最大的类作为标记，构建子节点，由结点及其子节点构成树T，返回T
• 对第i个子节点，以Di为训练集，以A-{Ag}为特征集，递归地调用1~5，得到子树Ti，返回TiCART决策树的生成
•
这里只简单介绍下CART与ID3和C4.5的区别。
• CART树是二叉树，而ID3和C4.5可以是多叉树
• CART在生成子树时，是选择一个特征一个取值作为切分点，生成两个子树
• 选择特征和切分点的依据是基尼指数，选择基尼指数最小的特征及切分点生成子树
随机森林是一种重要的基于Bagging的集成学习方法，可以用来做分类、回归等问题。
随机森林有许多优点：
• 具有极高的准确率
• 随机性的引入，使得随机森林不容易过拟合
• 随机性的引入，使得随机森林有很好的抗噪声能力
• 能处理很高维度的数据，并且不用做特征选择
• 既能处理离散型数据，也能处理连续型数据，数据集无需规范化
• 训练速度快，可以得到变量重要性排序
• 容易实现并行化
•
随机森林的缺点：
• 当随机森林中的决策树个数很多时，训练时需要的空间和时间会较大
• 随机森林模型还有许多不好解释的地方，有点算个黑盒模型
与上面介绍的Bagging过程相似，随机森林的构建过程大致如下：
• 从原始训练集中使用Bootstraping方法随机有放回采样选出m个样本，共进行n_tree次采样，生成n_tree个训练集
• 对于n_tree个训练集，我们分别训练n_tree个决策树模型
• 对于单个决策树模型，假设训练样本特征的个数为n，那么每次分裂时根据信息增益/信息增益比/基尼指数选择最好的特征进行分裂
• 每棵树都一直这样分裂下去，直到该节点的所有训练样例都属于同一类。在决策树的分裂过程中不需要剪枝
• 将生成的多棵决策树组成随机森林。对于分类问题，按多棵树分类器投票决定最终分类结果；对于回归问题，由多棵树预测值的均值决定最终预测结果
AdaBoost
Adaboost 是 bosting 的方法之一。bosting就是把若干个分类效果并不好的分类器综合起来考虑，会得到一个效果比较好的分类器。
AdaBoost的一般流程如下所示：
（1）收集数据
（2）准备数据：依赖于所用的基分类器的类型，这里的是单层决策树，即树桩，该类型决策树可以处理任何类型的数据。
（3）分析数据
（4）训练算法：利用提供的数据集训练分类器
（5）测试算法：利用提供的测试数据集计算分类的错误率
（6）使用算法：算法的相关推广，满足实际的需要
接下来，具体阐述adaBoost分类算法1 训练算法：基于错误提升分类器的性能
上面所述的基分类器，或者说弱分类器，意味着分类器的性能不会太好，可能要比随机猜测要好一些，一般而言，在二类分类情况下，弱分类器的分类错误率达到甚至超过50%，显然也只是比随机猜测略好。但是，强分类器的分类错误率相对而言就要小很多，adaBoost算法就是易于这些弱分类器的组合最终来完成分类预测的。
adaBoost的运行过程：训练数据的每一个样本，并赋予其一个权重，这些权值构成权重向量D，维度等于数据集样本个数。开始时，这些权重都是相等的，首先在训练数据集上训练出一个弱分类器并计算该分类器的错误率，然后在同一数据集上再次训练弱分类器，但是在第二次训练时，将会根据分类器的错误率，对数据集中样本的各个权重进行调整，分类正确的样本的权重降低，而分类错的样本权重则上升，但这些权重的总和保持不变为1.
并且，最终的分类器会基于这些训练的弱分类器的分类错误率，分配不同的决定系数alpha，错误率低的分类器获得更高的决定系数，从而在对数据进行预测时起关键作用。alpha的计算根据错误率得来：
alpha=0.5*ln(1-ε/max(ε,1e-16))
其中，ε=为正确分类的样本数目/样本总数，max(ε,1e-16)是为了防止错误率为而造成分母为0的情况发生
计算出alpha之后，就可以对权重向量进行更新了，使得分类错误的样本获得更高的权重，而分类正确的样本获得更低的权重。D的计算公式如下：
如果某个样本被正确分类，那么权重更新为：
D(m+1,i)=D(m,i)*exp(-alpha)/sum(D)
如果某个样本被错误分类，那么权重更新为：
D(m+1,i)=D(m,i)*exp(alpha)/sum(D)
其中，m为迭代的次数，即训练的第m个分类器，i为权重向量的第i个分量，i<=数据集样本数量
当我们更新完各个样本的权重之后，就可以进行下一次的迭代训练。adaBoost算法会不断重复训练和调整权重，直至达到迭代次数，或者训练错误率为0。
基于单层决策树构建弱分类器
单层决策树是一种简单的决策树，也称为决策树桩。单层决策树可以看做是由一个根节点直接连接两个叶结点的简单决策树，比如x>v或x<v，就可以看做是一个简单决策树。
