我肝了三天，就是为了让你搞懂什么是树好久没更新文章了，因为偷偷去考了个在职研究生，虽说能读研这事吧，前途渺茫，但也是让我再次短暂经历了一次大学的考研生活，也让我下定决心把基础的知识继续拾起来。本节我们就将来侃一侃我考研准备期间偷出的时间呕心沥血写的树。树是数据结构中的重中之重，尤其以各类二叉树为学习的难点和典型。之前上学的时候学过树相关的知识,但是一直以来,对树的掌握都是模棱两可的状态。工作之余，现在希望通过一遍重新学习，一边重新写一个关于树的较系统的文章，从而更深入的掌握树。希望能过通过这一系列的学习做到心中有“树”。树的定义树，顾名思义，长得像一棵树，不过通常我们画成一棵倒过来的树，根在上，叶在下。我们日常所见的树也是一样的，从主树干出发，会衍生出很多枝干，而每个枝干又会衍生出枝丫，就这样组成了我们在地面上可以看到的树的结构，但对于每一个小枝丫来讲，归根结底，还是来自于主树干的层层衍生形成的 树形结构相比数组、链表、堆栈这些线性数据结构来说(线性结构中节点是首位相接一对一关系)，稍微复杂一点点，但树形结构可以用于解决很多实际问题，因为现实世界事物之间的关系往往不是线性关联的，而「树」恰好适合描述这种非线性关系。在树结构中节点之间不再是简单的一对一关系，而是较为复杂的一对多的关系，一个节点可以与多个节点发生关联，树是一种层次化的数据组织形式，树在现实中是可以找到例子的:用于保存和处理树状的数据，例如家谱，组织机构图进行查找，以及一些大规模的数据索引方面 今天就带大家一起学习下，数据结构中的各种「树」，这也是面试中经常考察的内容，手撕二叉树等更是常规套路，对候选人也很有区分度。 我们将一对多关系集合中的数据按照上图的形式存储,整个存储形状从逻辑结构上来看,类似于生活中倒挂的树,所以这种结构也被称为树形结构树的相关术语节点节点: 使用树结构存储的每一个数据元素都被称为“结点”,数据元素 A 就是一个结点父结点（双亲结点）：对于结点 A、B、C、D 来说，A 是 B、C、D 结点的父结点（也称为“双亲结点”）子节点(孩子节点): B、C、D 都是 A 结点的子结点（也称“孩子结点”)兄弟节点: 对于 B、C、D 来说，它们都有相同的父结点A，所以它们互为兄弟结点根结点：每一个非空树都有且只有一个被称为根的结点。结点A就是整棵树的根结点。(如果一个结点没有父结点，那么这个结点就是整棵树的根结点)叶子结点：如果结点没有任何子结点，那么此结点称为叶子结点。结点 K、L、F、G、M、I、J 都是这棵树的叶子结点。子树和空树空树 如果集合本身为空，那么构成的树就被称为空树。空树中没有结点子树 在上图中，整棵树的根结点为结点 A，而如果单看结点 B、E、F、K、L 组成的部分来说，也是棵树，而且节点 B 为这棵树的根结点。所以称 B、E、F、K、L 这几个结点组成的树为整棵树的子树；同样，结点 E、K、L 构成的也是一棵子树，只不过根结点为 E。 单个结点也是一棵树，只不过根结点就是它本身。比如:结点 K、L、F 等都是树，且都是整棵树的子树。下图是B,E,F,K,L组成的一颗子树: 节点的度和层次度对于一个结点，拥有的子树数（结点有多少分支）称为结点的度（Degree)。 上图中, 根结点A下分出了 3 个子树，所以，结点 A 的度为3。 一棵树的度是树内各结点的度的最大值。层次 从一棵树的树根开始，树根所在层为第一层，根的孩子结点所在的层为第二层，依次类推。对于上图来说，A 结点在第一层，B、C、D 为第二层，E、F、G、H、I、J 在第三层，K、L、M 在第四层。 一棵树的深度（高度）是树中结点所在的最大的层次。上图树的深度为4有序树和无序树如果树中结点的子树从左到右看，谁在左边，谁在右边，是有规定的，这棵树称为有序树；反之称为无序树。 在有序树中，一个结点最左边的子树称为"第一个孩子"，最右边的称为"最后一个孩子"。分类树的主要分类如下示: 下面我们主要讲解下重中之重的二叉树。二叉树什么是二叉树呢? 简单来说就是:本身是有序树；树中包含的各个节点的度不能超过 2，即只能是 0、1 或者2;下图就是一个二叉树示例: 下图是一个非二叉树示例:
节点1有三个子节点(即节点度超过2)经过前人的总结, 二叉树有这么几个性质:二叉树中，第i层最多有2^{i-1}个结点。如果二叉树的深度为 K，那么此二叉树最多2^{K}-1 个结点。二叉树中，终端结点数（叶子结点数）为 n0，度为 2 的结点数为 n2，则 n0=n2+1。上面的三个性质,其实也是很好验证的,看完后续的满二叉树和完全二叉树,我们会有更深的了解。二叉树还可以继续分类，衍生出下面几类常见的树:满二叉树如果二叉树中除了叶子结点，每个结点的度都为 2，则此二叉树称为满二叉树。下图就是一个满二叉树实例: 结合上图,我们可以理解一下满二叉树的几个性质:满二叉树中第 i 层的节点数为2^{i-1}个。深度为 k 的满二叉树必有2^{k}-1个节点 ，叶子数为2^{k-1}。满二叉树中不存在度为 1 的节点，每一个分支点中都两棵深度相同的子树，且叶子节点都在最底层。具有 n 个节点的满二叉树的深度为 log_2({n+1})。完全二叉树如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。下面我们还是结合图实例来感受一波:
上面的非完全二叉树不满足:最后一层的结点依次从左到右分布(可以跟完全二叉树实例对比下)我们也可以发现: 满二叉树是特殊的完全二叉树,因为它符合完全二叉树的所有特征。但完全二叉树不一定是满二叉树。完全二叉树性质对于任意一个完全二叉树来说，如果将含有的结点按照层次从左到右依次标号(如上图的完全二叉树示例,我们标号为1，2，3，4，5，6)，对于任意一个结点i:当 i>1 时，父亲结点为结点 [i/2] 。（i=1 时，表示的是根结点，无父亲结点）如果 2i>n（总结点的个数） ，则结点 i 肯定没有左孩子（为叶子结点）；否则其左孩子是结点 2i 。如果 2i+1>n ，则结点 i 肯定没有右孩子；否则右孩子是结点 2i+1 。其它二叉树平衡二叉树、二叉搜索树、红黑树、哈夫曼树等我们会在后续文章中单独重点讲解。存储二叉树树的存储结构主要分为两种: 顺序存储以及链式存储,下面我们分别介绍下。顺序存储二叉树的顺序存储，指的是使用顺序表（数组）存储二叉树。需要注意的是，顺序存储只适用于完全二叉树。换句话说，只有完全二叉树才可以使用顺序表存储。因此，如果我们想顺序存储普通二叉树，需要提前将普通二叉树转化为完全二叉树。那么如何将普通二叉树装换为完全二叉树呢?普通二叉树转完全二叉树的方法很简单:只需给二叉树额外添加一些节点，将其"拼凑"成完全二叉树即可.如下图示例所示: 我们给空节点添加元素0,将一棵普通二叉树给转换成了一棵完全二叉树。 那么又将如何用数组来表示呢? 下面我们直接给出直观的图解: 链表存储二叉树的顺序存储，通过学习你会发现，其实二叉树并不适合用数组存储,主要有:并不是每个二叉树都是完全二叉树普通二叉树使用顺序表存储或多或多会存在空间浪费的现象(因为需要存储额外的元素)。那链式存储该怎么存储呢? 若将其采用链式存储，则只需从树的根节点开始，将各个节点及其左右孩子使用链表存储即可。采用链式存储二叉树时,其表示法如下图所示:
可以从上图看出,节点主要由三部分组成:指向左节点孩子的指针lchild节点数据data指向右节点孩子的指针rchild在golang中我们也可以用代码的形式表示为:type Node struct{
Data interface{}
Lchild *BiTree
Rchild *BiTree
}
遍历为什么研究二叉树的遍历？因为计算机只会处理线性序列，而我们研究遍历，就是把树中的结点变成某种意义的线性序列，这给程序的实现带来了好处。遍历主要有以下几种方式，包括：前序遍历中序遍历后序遍历广度优先遍历(层次遍历)区别: 我们知道，一个二叉树有根节点，左节点，右节点。我们遍历的顺序肯定先是左节点，再右节点。前序、中序、后序的区别就是根节点的位置。如果根节点在左节点前面，那么就是前序遍历 (根，左，右) 。如果根节点在两者之间，那么就是中序遍历 (左，根，右) 。如果根节点在右节点后面，那么就是后序遍历了 (左，右，根) 。对于广度优先，我们把树分层，根节点为第一层，根节点的子节点为第二层，第二层的子节点为第三层，依次递推。遍历的时候就对每一层进行依次访问。下面,我们通过手撸一个个动图来动态的演示一下具体遍历的操作 (-^^-制作动图不易,喜欢的朋友请点个赞来波关注-^^-)前序遍历具体操作: 若树为空，则空操作返回。否则，先访问根节点，然后前序遍历左子树，再前序遍历右子树。 如上图所示: 我们采用前序遍历,我们得到的遍历序列为: 1,2,4,5,3,6,7中序遍历具体操作: 若树为空，则空操作返回。否则，从根节点开始（注意并不是先访问根节点），中序遍历根节点的左子树，然后是访问根节点，最后中序遍历根节点的右子树。 如上图所示: 我们采用中序遍历,我们得到的遍历序列为: 4，2，5，1，6，3，7后序遍历具体操作: 若树为空，则空操作返回。否则，从左到右先叶子后节点的方式遍历访问左右子树，最后访问根节点。 如上图所示: 我们采用后序遍历,我们得到的遍历序列为: 4，5，2，6，7，3，1层次遍历具体操作: 若树为空，则空操作返回。否则，从树的第一层，也就是根节点开始访问，从上到下逐层遍历，在同一层中，按从左到右的顺序结点逐个访问。 如上图所示: 我们采用层次遍历,我们得到的遍历序列为: 1，2，3，4，5，6，7实现https://github.com/yiye93/algo ^^代码不易，希望大家给个星鼓励下^^树结构定义:package tree
import "fmt"
type Node struct {
Data
interface{} //节点数据
LChild *Node
//左子树
RChild *Node
//右子树
}
func NewNode(data interface{}) *Node {
return &Node{Data: data}
}
func (this *Node) String() string {
return fmt.Sprintf("value:%+v, left child:%+v,right child:%+v", this.Data, this.LChild, this.RChild)
}
前序遍历我们使用简单直观的递归实现和相对复杂的栈两种实现方式展示一下如何前序遍历。中序遍历和后序遍历相同。递归方式实现package tree
import "fmt"
//前序遍历
func PreOrder(tree *Node) {
if tree == nil {
return
}
//打印根节点值
fmt.Printf("data:%v\n", tree.Data)
//遍历左子树
PreOrder(tree.LChild)
//遍历右子树
PreOrder(tree.RChild)
}
使用栈实现 参阅网上的一个流程图 并结合之前讲解的栈以及栈实现代码，完成二叉树的前序遍历。package tree
import (
"fmt"
"github.com/yiye93/algo/stack"
)
// 前序遍历
// 栈实现
func PreOrderV1(tree *Node) {
if tree == nil {
return
}
var elems = make([]interface{}, 0)
var s = stack.NewStackOnLinklist()
// 步骤1: 直到当前结点为空 & 栈空时，循环结束
for tree != nil
!s.IsEmpty() {
// 步骤2: 判断当前结点是否为空
if tree != nil {
// 步骤3: 保存当前节点值,并将该节点入栈
elems = append(elems, tree.Data)
s.Push(tree)
// 步骤4: 置当前结点的左孩子为当前节点
tree = tree.LChild
// 返回步骤1
} else {
// 步骤5：出栈栈顶结点
tree = s.Pop().(*Node)
// 步骤6：置当前结点的右孩子为当前节点
tree = tree.RChild
// 返回步骤1
}
}
for _, elem := range elems {
fmt.Printf("data:%v\n", elem)
}
return
}
中序遍历递归实现package tree
import "fmt"
//中序遍历
func MidOrder(tree *Node) {
if tree == nil {
return
}
//遍历左子树
MidOrder(tree.LChild)
//打印根节点值
fmt.Printf("data:%v\n", tree.Data)
//遍历右子树
MidOrder(tree.RChild)
}
使用栈实现 参考网上流程图
实现代码如下示:package tree
import (
"fmt"
"github.com/yiye93/algo/stack"
)
// 中序遍历
// 栈实现
func MidOrderV1(tree *Node) {
if tree == nil {
return
}
var elems = make([]interface{}, 0)
var s = stack.NewStackOnLinklist()
// 步骤1: 直到当前结点为空 & 栈空时，循环结束
for tree != nil
!s.IsEmpty() {
// 步骤2: 判断当前结点是否为空
if tree != nil {
// 步骤3: 将该节点入栈
s.Push(tree)
// 步骤4: 置当前结点的左孩子为当前节点
tree = tree.LChild
// 返回步骤1
} else {
// 步骤5：出栈栈顶结点
tree = s.Pop().(*Node)
// 步骤6：保存节点
elems = append(elems, tree.Data)
// 步骤7：置当前结点的右孩子为当前节点
tree = tree.RChild
// 返回步骤1
}
}
for _, elem := range elems {
fmt.Printf("data:%v\n", elem)
}
return
}
后序遍历递归实现package tree
import "fmt"
//后序遍历
func PostOrder(tree *Node) {
if tree == nil {
return
}
//遍历左子树
PostOrder(tree.LChild)
//遍历右子树
PostOrder(tree.RChild)
//打印根节点值
fmt.Printf("data:%v\n", tree.Data)
}
使用栈实现 参考网上流程图
代码实现如下示:package tree
import (
"fmt"
"github.com/yiye93/algo/stack"
)
func PostOrderV1(tree *Node) {
if tree == nil {
return
}
// 构建普通栈
var s = stack.NewStackOnLinklist()
// 构建中间输出栈
var out = stack.NewStackOnLinklist()
// 步骤1: 直到当前结点为空 & 栈空时，循环结束
for tree != nil
!s.IsEmpty() {
// 步骤2: 判断当前结点是否为空
if tree != nil {
// 步骤3: 将该节点入普通栈和中间输出栈
s.Push(tree)
out.Push(tree)
// 步骤4: 置当前结点的右孩子为当前节点
tree = tree.RChild
// 返回步骤1
} else {
// 步骤5：出栈栈顶结点
tree = s.Pop().(*Node)
// 步骤6：置当前结点的左孩子为当前节点
tree = tree.LChild
// 返回步骤1
}
}
for !out.IsEmpty() {
fmt.Printf("data:%v\n", out.Pop().(*Node).Data)
}
}
层次遍历使用队列实现,参考示意图如下示: 代码实现如下示:// 层次遍历
// 从上到下、从左到右
// 队列实现
func LevelTravel(tree *Node) {
if tree == nil {
return
}
elems := make([]interface{}, 0)
// 此处搞了个容量限制...
q := queue.NewQueueOnLinklist(10000)
// 头元素入队
q.EnQueue(tree)
// 队列非空
for !q.IsEmpty() {
n := q.DeQueue().(*Node)
elems = append(elems, n.Data)
// 左子树非空,左子树乖乖入队
if n.LChild != nil {
q.EnQueue(n.LChild)
}
// 右子树非空,右子树乖乖入队
if n.RChild != nil {
q.EnQueue(n.RChild)
}
}
for _, elem := range elems {
fmt.Printf("data:%v\n", elem)
}
}
一个测试调用demopackage tree
import "testing"
func TestBinaryTree(t *testing.T) {
// **测试二叉树结构如下**
//
1
//
2
3
//
4
5
6
7
//
8
//
9
// **前序遍历结果**
// 1 -> 2 -> 4 -> 8 -> 9 -> 5 -> 3 -> 6 -> 7
// **中序遍历结果**
// 8 -> 9 -> 4 -> 2 -> 5 -> 1 -> 6 -> 3 -> 7
// **后序遍历结果**
// 9 -> 8 -> 4 -> 5 -> 2 -> 6 -> 7 -> 3 -> 1
// **层次遍历结果**
// 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
var root = NewNode(1)
root.LChild = NewNode(2)
root.RChild = NewNode(3)
root.LChild.LChild = NewNode(4)
root.LChild.RChild = NewNode(5)
root.RChild.LChild = NewNode(6)
root.RChild.RChild = NewNode(7)
root.LChild.LChild.LChild = NewNode(8)
root.LChild.LChild.LChild.RChild = NewNode(9)
// PreOrder(root)
// PreOrderV1(root)
// MidOrder(root)
// MidOrderV1(root)
// PostOrder(root)
//PostOrderV1(root)
LevelTravel(root)
}
总结树相对来说是比较复杂难掌握的，本文尽量通过一些直观图文去讲清树是什么，以及重点讲解了二叉树。如果有帮助到您，希望给个赞和来波关注鼓励下。另外有任何问题也欢迎给我留言。在这里，也欢迎大家关注我的公众号以及github.link公众号: 程序员的进击之路github: https://github.com/yiye93/algo参阅图解数据结构（6）——树及树的遍历数据结构中的树存储结构树的几种遍历方式}

QInzhengk/Math-Model-and-Machine-Learning (github.com)一、决策树(Desision Tree)1.一棵决策树的生成过程分为以下3个部分特征选择：指从训练数据中众多的特征中选择一个特征作为当前节点的分裂标准，如何选择特征有着很多不同量化评估标准，从而衍生出不同的决策树算法。决策树生成：根据选择的特征评估标准，从上至下递归地生成子节点，直到数据集不可分则停止决策树生长。剪枝：决策树容易过拟合，一般需要剪枝，缩小树结构规模，缓解过拟合。信息熵越低，纯度越高。信息熵的公式：p_{k} 表示的是：当前样本集合D中第k类样本所占的比例为 p_{k} 。信息增益公式：特征a对训练集D的信息增益Gain(D,a)决策树的生成ID3算法-最大信息增益
在根节点处计算信息熵，然后根据属性依次划分并计算其节点的信息熵，用根节点信息熵-属性节点的信息熵=信息增益，根据信息增益进行降序排列，排在前面的就是第一个划分属性，其后依次类推，这就得到了决策树的形状，也就是怎么“长”了。
不过，信息增益有一个问题：对可取值数目较多的属性有所偏好，例如：考虑将“编号”作为一个属性。为了解决这个问题，引出了另一个算法C4.5。2.C4.5-最大信息增益比为了解决信息增益的问题，引入一个信息增益率：其中：属性a的可能取值数目越多(即V越大)，则IV(a)的值通常就越大。信息增益比本质： 是在信息增益的基础之上乘上一个惩罚参数。特征个数较多时，惩罚参数较小；特征个数较少时，惩罚参数较大。缺点：信息增益率偏向取值较少的特征。因此C4.5并不是直接选择信息增益率最大的特征，而是现在候选特征中找出信息增益高于平均水平的特征，然后在这些特征中再选择信息增益率最高的特征。3.CART算法-最大基尼指数（Gini）另外一个表示纯度的方法，叫做基尼指数：表示在样本集合中一个随机选中的样本被分错的概率。举例，现在一个袋子里有3种颜色的球若干个，伸手进去掏出2个球，颜色不一样的概率。Gini(D)越小，数据集D的纯度越高。2.决策树如何剪枝剪掉一些枝叶，提升模型的泛化能力。决策树的剪枝基本策略有 预剪枝 (Pre-Pruning) 和 后剪枝 (Post-Pruning)。预剪枝：在每一次实际对结点进行进一步划分之前，先采用验证集的数据来验证如果划分是否能提高划分的准确性。如果不能，就把结点标记为叶结点并退出进一步划分；如果可以就继续递归生成节点。后剪枝：先从训练集生成一颗完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来泛化性能提升，则将该子树替换为叶结点。3.决策树怎么处理连续特征连续特征离散化（C4.5二分法）假设样本在集合D中有n个取值，从小到大排序确定一个阈值，把样本集合分成两部分，阈值选取规则：取排序后两个相邻值的均值（n个值就有n-1个阈值）分别比较这n-1个阈值的信息增益，选择信息增益最大的阈值来划分。4.决策树怎么处理缺失值如何在属性值缺失的情况下进行划分属性的选择？忽略特征缺失的样本来计算属性的信息增益或其他指标2. 给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？若样本x在划分属性a上的取值未知，则将x同时划入所有子结点，调整此刻样本的权重值，也就是让同一样本以不同概率划入到不同的子结点去。5.三种不同的决策树的差异ID3 只能处理离散型变量，而C4.5 和CART 都可以处理连续型变量；ID3 和C4.5 只能用于分类任务， 而CART (Classification and Regression Tree ，分类回归树）从名字就可以看出其不仅可以用于分类， 也可以应用于回归任务（回归树使用最小平方误差准则）；ID3 对样本特征缺失值比较敏感，而C4.5 和CART 可以对缺失值进行不同方式的处理；ID3 和C4. 5 可以在每个结点上产生出多叉分支，且每个特征在层级之间不会复用，而CART 每个结点只会产生两个分支，因此最后会形成一颗二叉树，且每个特征可以被重复使用；ID3 和C4.5 通过剪枝来权衡树的准确性与泛化能力，而CART 直接利用全部数据发现所有可能的树结构进行对比。6.树形结构为什么不需要归一化?因为数值缩放不影响分裂点位置，对树模型的结构不造成影响。按照特征值进行排序的，排序的顺序不变，那么所属的分支以及分裂点就不会有不同。而且，树模型是不能进行梯度下降的，因为构建树模型（回归树）寻找最优点时是通过寻找最优分裂点完成的，因此树模型是阶跃的，阶跃点是不可导的，并且求导没意义，也就不需要归一化。既然树形结构（如决策树、RF）不需要归一化，那为何非树形结构比如Adaboost、SVM、LR、Knn、KMeans之类则需要归一化。对于线性模型，特征值差别很大时，运用梯度下降的时候，损失等高线是椭圆形，需要进行多次迭代才能到达最优点。但是如果进行了归一化，那么等高线就是圆形的，促使SGD（随机梯度下降）往原点迭代，从而导致需要的迭代次数较少。7.回归决策树
回归树采用最小方差作为分裂规则
对于任意划分特征A，对应的任意划分点S两边划分得数据集D1和D2，求出使D1和D2各自集合的均方差最小，同时使D1和D2的均方差之和最小，所对应的特征和特征值划分点。8.决策树的目标函数（待续）二、随机森林(Random Forest)为了增加元模型之间的差异，随机森林不应对子树进行剪枝1.Bagging
给定一个大小为n的训练集D，从中均匀地、有放回地（自助抽样）选出m个大小为n'的子集Di，作为新的训练集，在这m个训练集上使用回归、分类算法，得到m个模型，在通过取平均值、取多数票等方法，得到结果。这就极大可能的避免了不好的样本数据，从而提高准确度。因为有些是不好的样本，相当于噪声，模型学入噪声后会使准确度不高。随机森林Random Forest(随机森林)是一种基于树模型的Bagging的优化版本，一棵树的生成肯定还是不如多棵树，因此就有了随机森林，解决决策树泛化能力弱的特点。而同一批数据，用同样的算法只能产生一棵树，这时Bagging策略可以帮助我们产生不同的数据集。每棵树的按照如下规则生成：如果训练集大小为N，对于每棵树而言，随机且有放回地从训练集中的抽取N个训练样本，作为该树的训练集；如果每个样本的特征维度为M，指定一个常数m<<M，随机地从M个特征中选取m个特征子集，每次树进行分裂时，从这m个特征中选择最优的；每棵树都尽最大程度的生长，并且没有剪枝过程。两个随机性的引入对随机森林的分类性能至关重要。由于它们的引入，使得随机森林不容易陷入过拟合，并且具有很好得抗噪能力（比如：对缺省值不敏感）。总的来说就是随机选择样本数，随机选取特征，随机选择分类器，建立多颗这样的决策树，然后通过这颗决策树来投票，决定数据属于哪一类(投票机制有一票否决制、少数服从多数、加权多数)2.随机森林为什么比bagging效率高？bagging无随机特征，使得训练决策树时效率更低。3.随机森林分类效果的影响因素森林中任意两棵树的相关性：相关性越大，错误率越大；森林中每棵树的分类能力：每棵树的分类能力越强，整个森林的错误率越低。减小特征选择个数m，树的相关性和分类能力也会相应的降低；增大m，两者也会随之增大。所以关键问题是如何选择最优的m（或者是范围），这也是随机森林唯一的一个参数。4.什么是OOB？随机森林中OOB是如何计算的，它有什么优缺点？构建随机森林的关键问题就是如何选择最优的m，要解决这个问题主要依据计算袋外错误率oob error（out-of-bag error）。bagging方法中Bootstrap每次约有1/3的样本不会出现在Bootstrap所采集的样本集合中，当然也就没有参加决策树的建立，把这1/3的数据称为袋外数据oob（out of bag）,它可以用于取代测试集误差估计方法。袋外数据(oob)误差的计算方法如下：对于已经生成的随机森林,用袋外数据测试其性能,假设袋外数据总数为O,用这O个袋外数据作为输入,带进之前已经生成的随机森林分类器,分类器会给出O个数据相应的分类因为这O条数据的类型是已知的,则用正确的分类与随机森林分类器的结果进行比较,统计随机森林分类器分类错误的数目,设为X,则袋外数据误差大小=X/O优缺点：这已经经过证明是无偏估计的,所以在随机森林算法中不需要再进行交叉验证或者单独的测试集来获取测试集误差的无偏估计。 5.随机森林有什么优缺点优点：它能够处理很高维度（feature很多）的数据，并且不用做特征选择(因为特征子集是随机选择的)。在训练完后，它能够给出哪些feature比较重要。训练速度快，容易做成并行化方法(训练时树与树之间是相互独立的)。在训练过程中，能够检测到feature间的互相影响。对于不平衡的数据集来说，它可以平衡误差。如果有很大一部分的特征遗失，仍可以维持准确度。缺点：随机森林已经被证明在某些噪音较大的分类或回归问题上会过拟合。对于有不同取值的属性的数据，取值划分较多的属性会对随机森林产生更大的影响，所以随机森林在这种数据上产出的属性权值是不可信的。6.随机森林如何处理缺失值？根据随机森林创建和训练的特点，随机森林对缺失值的处理还是比较特殊的。首先，给缺失值预设一些估计值，比如数值型特征，选择其余数据的中位数或众数作为当前的估计值然后，根据估计的数值，建立随机森林，把所有的数据放进随机森林里面跑一遍。记录每一组数据在决策树中一步一步分类的路径.判断哪组数据和缺失数据路径最相似，引入一个相似度矩阵，来记录数据之间的相似度，比如有N组数据，相似度矩阵大小就是N*N如果缺失值是类别变量，通过权重投票得到新估计值，如果是数值型变量，通过加权平均得到新的估计值，如此迭代，直到得到稳定的估计值。其实，该缺失值填补过程类似于推荐系统中采用协同过滤进行评分预测，先计算缺失特征与其他特征的相似度，再加权得到缺失值的估计，而随机森林中计算相似度的方法（数据在决策树中一步一步分类的路径）乃其独特之处。(相似度矩阵：两个样本落在树的同一个节点次数越多，这两样本相似度越高。)随机森林的过拟合问题可以采用交叉验证来调整树的数量。7.如何使用随机森林对特征重要性进行评估Gainoob对于随机森林的每一棵决策树，使用相应的oob计算它的袋外数据误差，记为 err_{oob1} 随机地对袋外数据所有样本特征X加入噪声干扰，再计算它的袋外数据误差 err_{oob2} 假设随即森林有n棵树，那么对于特征X的重要性为 err_{oob1}-err_{oob1}/N ，之所以可以用这个表达式来作为相应特征的重要性度量值是因为：若给某个特征随机加入噪声之后，袋外的准确度大幅降低，则说明这个特征对于样本的分类结果影响很大，也就是它的重要性程度比较高。Stacking：多次采样，训练多个分类器，将输出作为最后的输入特征。三、梯度提升决策树(GBDT)1.Boosting思想给定初始训练数据，由此训练出第一个基学习器；根据基学习器的表现对样本进行调整，在之前学习器做错的样本上投入更多关注；用调整后的样本，训练下一个基学习器；重复上述过程 T 次，将 T 个学习器加权结合。2.GBDT原理每一次计算都是为了减小上一次的残差，而为了消除残差，在残差减小的梯度方向上建立模型。3.GBDT使用的决策树都是CART回归树，为什么不用CART分类树呢？因为GBDT每次迭代要拟合的是梯度值，是连续值所以用回归树。4.为何gbdt可以用负梯度近似残差呢？回归任务下，GBDT 在每一轮的迭代时对每个样本都会有一个预测值，此时的损失函数为均方差损失函数，那此时的负梯度是这样计算的所以，当损失函数选用均方损失函数是时，每一次拟合的值就是（真实值 - 当前模型预测的值），即残差。此时的变量是 y_{i} ，即“当前预测模型的值”，也就是对它求负梯度。GBDT用于分类时，损失函数为log loss。5.梯度提升和梯度下降的区别和联系是什么？ 下表是梯度提升算法和梯度下降算法的对比情况。可以发现，两者都是在每一轮迭代中，利用损失函数相对于模型的负梯度方向的信息来对当前模型进行更新，只不过在梯度下降中，模型是以参数化形式表示，从而模型的更新等价于参数的更新。而在梯度提升中，模型并不需要进行参数化表示，而是直接定义在函数空间中，从而大大扩展了可以使用的模型种类。6.为什么GBDT需要归一化？因为GBDT的树是在上一棵树的基础上通过梯度下降求解最优解，归一化能收敛的更快。7.GBDT的优点和局限性有哪些？ 优点预测阶段的计算速度快，树与树之间可并行化计算。在分布稠密的数据集上，泛化能力和表达能力都很好。 采用决策树作为弱分类器使得GBDT模型具有较好的解释性和鲁棒性，能够自动发现特征间的高阶关系。局限性GBDT在高维稀疏的数据集上，表现不如支持向量机或者神经网络。GBDT在处理文本分类特征问题上，相对其他模型的优势不如它在处理数值特征时明显。 训练过程需要串行训练，只能在决策树内部采用一些局部并行的手段提高训练速度。8.RF(随机森林)与GBDT之间的区别与联系相同点：都是由多棵树组成，最终的结果都是由多棵树一起决定。RF和GBDT在使用CART树时，可以是分类树或者回归树。（？）不同点：组成随机森林的树可以并行生成，而GBDT是串行生成随机森林的结果是多数表决的，而GBDT则是多棵树累加之和随机森林对异常值不敏感，而GBDT对异常值比较敏感随机森林是减少模型的方差，而GBDT是减少模型的偏差随机森林不需要进行特征归一化，而GBDT则需要进行特征归一化GBDT调参learning_rate:每个弱学习器的权重缩减系数。9.GBDT是如何做分类和回归的回归：生成每一棵树的时候，第一棵树的叶子结点内所有样本的label的均值就是这颗树的预测值，后面根据残差在预测，最后根据将第一棵树的预测值+权重*（其他树的预测结果）分类（softmax）（待续）四、XGBoost不适合处理稀疏特征1.什么是XGBoostXGBoost高效地实现了GBDT算法并进行了算法和工程上的许多改进。说到XGBoost，不得不提GBDT(Gradient Boosting Decision Tree)。因为XGBoost本质上还是一个GBDT，但是力争把速度和效率发挥到极致，所以叫X (Extreme) GBoosted。包括前面说过，两者都是boosting方法XGBoost的核心算法思想不难，基本就是：不断地添加树，不断地进行特征分裂来生长一棵树，每次添加一个树，其实是学习一个新函数f(x)，去拟合上次预测的残差。当我们训练完成得到k棵树，我们要预测一个样本的分数，其实就是根据这个样本的特征，在每棵树中会落到对应的一个叶子节点，每个叶子节点就对应一个分数最后只需要将每棵树对应的分数加起来就是该样本的预测值。2.如何停止树的循环生成当引入的分裂带来的增益小于设定阀值的时候，可以忽略掉这个分裂，所以并不是每一次分裂loss function整体都会增加的，有点预剪枝的意思，阈值参数为（即正则项里叶子节点数T的系数）；当树达到最大深度时则停止建立决策树，设置一个超参数max_depth，避免树太深导致学习局部样本，从而过拟合；样本权重和小于设定阈值时则停止建树。即涉及到一个超参数-最小的样本权重和min_child_weight，和GBM的 min_child_leaf 参数类似，但不完全一样。大意就是一个叶子节点样本太少了，也终止同样是防止过拟合；3.XGBoost与GBDT有什么不同GBDT是机器学习算法，XGBoost是该算法的工程实现。在使用CART作为基分类器时，XGBoost显式地加入了正则项来控制模型的复杂度，有利于防止过拟合，从而提高模型的泛化能力。GBDT在模型训练时只使用了代价函数的一阶导数信息，XGBoost对代价函数进行二阶泰勒展开，可以同时使用一阶和二阶导数。传统的GBDT采用CART作为基分类器，XGBoost支持多种类型的基分类器，比如线性分类器。传统的GBDT在每轮迭代时使用全部的数据，XGBoost则采用了与随机森林相似的策略，支持对数据进行采样。传统的GBDT没有设计对缺失值进行处理，XGBoost能够自动学习出缺失值的处理策略。4.为什么XGBoost要用泰勒展开，优势在哪里？XGBoost使用了一阶和二阶偏导, 二阶导数有利于梯度下降的更快更准. 使用泰勒展开取得函数做自变量的二阶导数形式, 可以在不选定损失函数具体形式的情况下, 仅仅依靠输入数据的值就可以进行叶子分裂优化计算, 本质上也就把损失函数的选取和模型算法优化/参数选择分开了. 这种去耦合增加了XGBoost的适用性, 使得它按需选取损失函数, 可以用于分类, 也可以用于回归。5.XGB如何处理缺失值在特征k上寻找最佳 split point 时，不会对该列特征 missing 的样本进行遍历，而只对该列特征值为 non-missing 的样本上对应的特征值进行遍历，通过这个技巧来减少了为稀疏离散特征寻找 split point 的时间开销。在逻辑实现上，为了保证完备性，会将该特征值missing的样本分别分配到左叶子结点和右叶子结点，两种情形都计算一遍后，选择分裂后增益最大的那个方向（左分支或是右分支），作为预测时特征值缺失样本的默认分支方向。如果在训练中没有缺失值而在预测中出现缺失，那么会自动将缺失值的划分方向放到右子结点。6.XGB如何处理不平衡数据如果采用AUC来评估模型的性能，可以通过设置scale_pos_weight来平衡正负样本的权重。还可以通过上采样、下采样、SMOTE算法或者自定义代价函数的方式解决正负样本不平衡的问题。7.XGB如何评价特征的重要性weight：该特征在所有树中被用作分割样本的特征的总次数。gain ：该特征在其出现过的所有树中产生的平均增益。cover：该特征在其出现过的所有树中的平均覆盖范围。注意：覆盖范围这里指的是一个特征用作分割点后，其影响的样本数量，即有多少样本经过该特征分割到两个子节点。8.XGB和LGB的区别树生长策略：XGB采用level-wise的分裂策略，LGB采用leaf-wise的分裂策略。XGB对每一层所有节点做无差别分裂，但是可能有些节点增益非常小，对结果影响不大，带来不必要的开销。Leaf-wise是在所有叶子节点中选取分裂收益最大的节点进行的，但是很容易出现过拟合问题，所以需要对最大深度做限制 。2. 分割点查找算法：XGB使用特征预排序算法，LGB使用基于直方图的切分点算法，其优势如下：减少内存占用，比如离散为256个bin时，只需要用8位整形就可以保存一个样本被映射为哪个bin(这个bin可以说就是转换后的特征)，对比预排序的exact greedy算法来说（用int_32来存储索引+ 用float_32保存特征值），可以节省7/8的空间。计算效率提高。LGB还可以使用直方图做差加速，一个节点的直方图可以通过父节点的直方图减去兄弟节点的直方图得到，从而加速计算。但实际上xgboost的近似直方图算法也类似于lightgbm这里的直方图算法，为什么xgboost的近似算法比lightgbm还是慢很多呢？xgboost在每一层都动态构建直方图， 因为xgboost的直方图算法不是针对某个特定的feature，而是所有feature共享一个直方图(每个样本的权重是二阶导)，所以每一层都要重新构建直方图，而lightgbm中对每个特征都有一个直方图，所以构建一次直方图就够了。3. 支持离散变量：无法直接输入类别型变量，因此需要事先对类别型变量进行编码（例如独热编码），而LightGBM可以直接处理类别型变量。4. 缓存命中率：XGB使用Block结构的一个缺点是取梯度的时候，是通过索引来获取的，而这些梯度的获取顺序是按照特征的大小顺序的，这将导致非连续的内存访问，可能使得CPU cache缓存命中率低，从而影响算法效率。而LGB是基于直方图分裂特征的，梯度信息都存储在一个个bin中，所以访问梯度是连续的，缓存命中率高。5.LightGBM 与 XGboost 的并行策略不同：特征并行 ：LGB特征并行的前提是每个worker留有一份完整的数据集，但是每个worker仅在特征子集上进行最佳切分点的寻找；worker之间需要相互通信，通过比对损失来确定最佳切分点；然后将这个最佳切分点的位置进行全局广播，每个worker进行切分即可。XGB的特征并行与LGB的最大不同在于XGB每个worker节点中仅有部分的列数据，也就是垂直切分，每个worker寻找局部最佳切分点，worker之间相互通信，然后在具有最佳切分点的worker上进行节点分裂，再由这个节点广播一下被切分到左右节点的样本索引号，其他worker才能开始分裂。二者的区别就导致了LGB中worker间通信成本明显降低，只需通信一个特征分裂点即可，而XGB中要广播样本索引。数据并行 ：当数据量很大，特征相对较少时，可采用数据并行策略。LGB中先对数据水平切分，每个worker上的数据先建立起局部的直方图，然后合并成全局的直方图，采用直方图相减的方式，先计算样本量少的节点的样本索引，然后直接相减得到另一子节点的样本索引，这个直方图算法使得worker间的通信成本降低一倍，因为只用通信以此样本量少的节点。XGB中的数据并行也是水平切分，然后单个worker建立局部直方图，再合并为全局，不同在于根据全局直方图进行各个worker上的节点分裂时会单独计算子节点的样本索引，因此效率贼慢，每个worker间的通信量也就变得很大。投票并行（LGB）：当数据量和维度都很大时，选用投票并行，该方法是数据并行的一个改进。数据并行中的合并直方图的代价相对较大，尤其是当特征维度很大时。大致思想是：每个worker首先会找到本地的一些优秀的特征，然后进行全局投票，根据投票结果，选择top的特征进行直方图的合并，再寻求全局的最优分割点。五、LightGBM1.LightGBM是什么?https://github.com/Microsoft/LightGBMLightGBM （Light Gradient Boosting Machine)是一个实现GBDT算法的框架，支持高效率的并行训练。LightGBM提出的主要原因就是为了解决GBDT在海量数据遇到的问题，让GBDT可以更好更快地用于工业实践。2.LightGBM在哪些地方进行了优化 (区别XGBoost)？基于Histogram（直方图）的决策树算法带深度限制的Leaf-wise的叶子生长策略直方图做差加速直接支持类别特征(Categorical Feature)Cache命中率优化基于直方图的稀疏特征优化多线程优化。3.Histogram算法直方图算法的基本思想是先把连续的浮点特征值离散化成k个整数（其实又是分桶的思想，而这些桶称为bin，比如[0,0.1)→0, [0.1,0.3)→1），同时构造一个宽度为k的直方图。在遍历数据的时候，根据离散化后的值作为索引在直方图中累积统计量，当遍历一次数据后，直方图累积了需要的统计量，然后根据直方图的离散值，遍历寻找最优的分割点。使用直方图算法有很多优点。首先，最明显就是内存消耗的降低，直方图算法不仅不需要额外存储预排序的结果，而且可以只保存特征离散化后的值，而这个值一般用8位整型存储就足够了，内存消耗可以降低为原来的1/8。然后在计算上的代价也大幅降低，预排序算法每遍历一个特征值就需要计算一次分裂的增益，而直方图算法只需要计算k次（k可以认为是常数），时间复杂度从O(#data*#feature)优化到O(k*#features)。4.LightGBM优点LightGBM 是一个实现GBDT算法的框架，支持高效率的并行训练，并且具有以下优点：更快的训练速度更低的内存消耗更好的准确率分布式支持，可以快速处理海量数据六、CatBoost1.相比于XGBoost、LightGBM，CatBoost的创新点有哪些？自动将类别特征处理为数值型特征；CatBoost对类别特征进行组合，极大地丰富了特征的维度；采用预排序提升的方法对抗训练集中的噪声点，从而避免梯度估计的偏差，进而解决预测偏移的问题；采用了完全对称树作为基模型。如何从减小方差和偏差的角度解释Boosting 和Bagging 的原理？Boosting方法是通过逐步聚焦于基分类器分错的样本，减小集成分类器的偏差。Bagging方法则是采取分而治之的策略，通过对训练样本多次采样，并分别训练出多个不同模型，然后做综合，来减小集成分类器的方差。Adaboost(Boosting思想)和Adaboost相比，随机森林对异常值更鲁棒Adaboost初始时每个训练元祖被赋予相等的权重参考：}