date: 2015-01-10 19:55
layout: 'post'
title: 'Blogging Like a Hacker'
tags:
- "hello"
- 'world'
status: 'public'原理
给定n维特征的样本x，线性模型的形式为：f(x) = wx + b
其中w为每个特征对应的权重生成的权重向量。
线性模型的优点是：
很多功能强大的非线性模型可以在线性模型的基础上通过引入层级结构或者非线性映射得到。
考察点：把LR从头到脚都给讲一遍。建模，现场数学推导，每种解法的原理，正则化，LR和maxent模型啥关系，LR为啥比线性回归好。有不少会背答案的人，问逻辑细节就糊涂了。原理都会? 那就问工程，并行化怎么做，有几种并行化方式，读过哪些开源的实现。还会，那就准备收了吧，顺便逼问LR模型发展历史。
sigmoid函数作为逻辑函数），将连续值映射到0 和1逻辑回归作为一个回归函数，如何用于分类问题。 逻辑回归中，对于每个 x，其条件概率 y 的确是一个连续的变量。而逻辑回归中可以设定一个阈值，y 值大于这个阈值的是一类，y 值小于这个阈值的是另外一类。至于阈值的选择，通常是根据实际情况来确定，一般情况下选取 0.5 作为阈值来划分。
因为目标是要让预测为正的的概率最大，且预测为负的概率也最大，即每一个样本预测都要得到最大的概率，将所有的样本预测后的概率进行相乘都最大，这就能到似然函数了。
要求 w 使得 lnL(w) 最大，用梯度下降或者牛顿法求解都行。
梯度下降法，随机梯度下降法，牛顿法，LBFGS，BFGS,OWLQN
极大似然函数无法直接求解，一般是通过对该函数进行梯度下降来不断逼近其最优解。这里需要注意的点是要对梯度下降有一定的了解，就梯度下降本身来看的话就有随机梯度下降，批梯度下降，small batch 梯度下降三种方式，面试官可能会问这三种方式的优劣以及如何选择最合适的梯度下降方式。
线性回归用来做预测, LR用来做分类。
线性回归的拟合函数本质上是对 输出变量 y 的拟合， 而==逻辑回归的拟合函数是对 label 为1的样本的概率的拟合。==
![[公式]](https://cdn.jsdelivr.net/gh/AIGoBig/PicRepo@master/2024/03/equation-20210827140521662_20240315115739mq2p1d.jpg)
线性回归用最小二乘法来计算参数,LR用最大似然估计来计算参数。
🚩 ==线性回归更容易受到异常值的影响,而LR对异常值有较好的稳定性。==
方式1： 修改逻辑回归的损失函数，使用softmax函数构造模型解决多分类问题
softmax分类模型会有相同于类别数的输出，输出的值为对于样本属于各个类别的概率，最后对于样本进行预测的类型为概率值最高的那个类别。
方式2： 根据每个类别都建立一个二分类器，本类别的样本标签定义为0，其它分类样本标签定义为1
则有多少个类别就构造多少个逻辑回归分类器。
若所有类别之间有明显的互斥则使用softmax分类器，若所有类别不互斥有交叉的情况则构造相应类别个数的逻辑回归分类器。
LR是线性的，不能得到非线性关系，实际问题并不完全能用线性关系就能拟合。
将特征离散成高维的01特征可以解决分类模型的非线性问题
引入非线性。 逻辑回归属于广义线性模型，表达能力受限；单变量离散化为N个后，每个变量有单独的权重，相当于为模型引入了非线性，能够提升模型表达能力，加大拟合； 离散特征的增加和减少都很容易，易于模型的快速迭代；
运算速度快。 稀疏向量内积乘法运算速度快，计算结果方便存储，容易扩展
增加鲁棒性。 离散化后的特征对异常数据有很强的鲁棒性：
比如一个特征是年龄>30是1，否则0。如果特征没有离散化，一个异常数据“年龄300岁”会给模型造成很大的干扰；
由M+N个变量变为M*N个变量，进一步引入非线性，提升表达能力。
比如如果对用户年龄离散化，20-30作为一个区间，不会因为一个用户年龄长了一岁就变成一个完全不同的人。当然处于区间相邻处的样本会刚好相反，所以怎么划分区间是门学问。
逻辑回归和线性回归首先都是广义的线性回归，但是：
经典线性模型的优化目标函数是最小二乘，而逻辑回归则是似然函数，
另外线性回归在整个实数域范围内进行预测，敏感度一致，而分类范围，需要在[0,1]。逻辑回归就是一种减小预测范围，将预测值限定为[0,1]间的一种回归模型，因而对于这类问题来说，逻辑回归的鲁棒性比线性回归的要好
逻辑回归跟最大熵模型没有本质区别。逻辑回归是最大熵对应类别为二类时的特殊情况，也就是当逻辑回归类别扩展到多类别时，就是最大熵模型。
优点：
缺点：
原理： SVM，全称是support vector machine，中文名叫支持向量机。SVM是一个面向数据的分类算法，它的目标是为确定一个分类超平面，从而将不同的数据分隔开。
最大间隔超平面。
支持向量
SVM的核函数
核函数的本质可以概括为如下三点：
实际应用中，常常遇到线性不可分的情况。针对这种情况，常用做法是把样例特征映射到高维空间中，转化为线性可分问题。
将样例特征映射到高维空间，可能会遇到维度过高的问题。
针对可能的维数灾难，可以利用核函数。核函数也是将特征从低维到高维的转换，但避免了直接进行高维空间中的复杂计算，可以在低维上进行计算，却能在实质上将分类效果表现在高维上。
当然，SVM也能处理线性可分问题，这时使用的就是线性核了。
常用的核函数包括如下几个
松弛变量的理解
算法步骤：
在k-means或kNN，为什么用欧氏距离来计算最近邻之间的距离而不用曼哈顿距离？
曼哈顿距离只计算水平或垂直距离，有维度的限制。
另一方面，欧氏距离可用于任何空间的距离计算问题。
因为，数据点可以存在于任何空间，欧氏距离是更可行的选择。例如：想象一下国际象棋棋盘，象或车所做的移动是由曼哈顿距离计算的，因为它们是在各自的水平和垂直方向做的运动。
决策树的生成过程就是使用满足划分准则的特征不断的将数据集划分为纯度更高，不确定性更小的子集 的过程。对于当前数据集D的每一次的划分，都希望根据某特征划分之后的各个子集的纯度更高，不确定性更小。
在熵的理解那部分提到了，熵可以表示样本集合的不确定性，熵越大，样本的不确定性就越大。因此可以使用划分前后集合熵的差值来衡量使用当前特征对于样本集合D划分效果的好坏。
做法：计算使用所有特征划分数据集D，得到多个特征划分数据集D的信息增益，从这些信息增益中选 择最大的，因而当前结点的划分特征便是使信息增益最大的划分所使用的特征。
熵的理解：为了精确地定义信息增益，我们先定义信息论中广泛使用的一个度量标准称为熵（entropy）
它刻画了任意样例集的纯度（purity）。
给定包含关于某个目标概念的正反样例的样例集S，那么S相对这个布尔型分类的熵为：
其中，p+为正样本概率，p-为负样本概率。
本质： 是在信息增益的基础之上乘上一个惩罚参数。
公式：信息增益比 = 惩罚参数 * 信息增益
特征个数较多时，惩罚参数较小；特征个数较少时，惩罚参数较大。
缺点：信息增益比偏向取值较少的特征
原因： 当特征取值较少时HA(D)的值较小，因此其倒数较大，因而信息增益比较大。因而偏向取值较少 的特征。
信息增益比的使用：基于以上缺点，并不是直接选择信息增益率最大的特征，而是
定义：基尼指数（基尼不纯度）：表示在样本集合中一个随机选中的样本被分错的概率。
公式：基尼指数（基尼不纯度）= 样本被选中的概率 * 样本被分错的概率
注意： Gini指数越小表示集合中被选中的样本被分错的概率越小，也就是说集合的纯度越高，反之，集合越不纯。
- 🚩 pk表示选中的样本属于k类别的概率，则这个样本被分错的概率是(1-pk)
- 样本集合中有K个类别，一个随机选中的样本可以属于这k个类别中的任意一个，因而对类别就加和
- 当为二分类是，Gini(P) = 2p(1-p)
Boosting方法的例子
- AdaBoost(自适应增强)
- 基本思想
- 前一个分类器分错/分对的样本的权值会得到加强/降低，加权后的全体样本再次被用来训练下一个基本分类器。
- GBDT(梯度提升决策树)
基本思想
- GBDT的每一次计算都为了减少上一次的残差，进而在负梯度的方向上建立一个新的模型
- 根据当前模型损失函数的负梯度信息来训练新加入的弱分类器，然后把训练好的弱分类器以累加的形式结合到现有模型里
XGBoost
目标函数
- 目标函数分为两个部分：误差函数(logistic损失函数、平方损失函数)和正则化项（定义模型的复杂度）
- 将目标函数化简之后，目标函数只依赖于一阶导数g和二阶导数h
- 将目标函数和正则化项结合化简，对w进行求导，求出最优w，代入目标函数中
bagging方法的例子
- 随机森林 https://zhuanlan.zhihu.com/p/91395504
- 首先gbdt 是通过采用加法模型（即基函数的线性组合），以及不断减小训练过程产生的残差来达到将数据分类或者回归的算法。
- gbdt通过多轮迭代, 每轮迭代产生一个弱分类器，每个分类器在上一轮分类器的梯度（如果损失函数是平方损失函数，则梯度就是残差值）基础上进行训练。
- 🚩 对弱分类器的要求一般是足够简单，并且是低方差和高偏差的。因为训练的过程是通过降低偏差来不断提高最终分类器的精度（此处是可以证明的）。
- 弱分类器一般会选择为==CART TREE==（也就是分类回归树）。
- 由于上述高偏差和简单的要求，每个分类回归树的深度不会很深。最终的总分类器是将每轮训练得到的弱分类器加权求和得到的（也就是加法模型）。
处理缺失值
RF：
对应类别的中位数代替
快速简单但是效果差：
引入权重，先做相似度预测，相似度高的权重大
费时费力但效果好：
🚩GBDT
特征重要性判断
RF
GBDT:
计算 所有回归决策树中通过特征i分裂后平方损失或基尼指数的减少值的和 / 回归树数量 得到特征重 要性。
异同点
相同点：
不同点：
先说说LR和GBDT的区别：
当在高维稀疏特征的场景下，LR的效果一般会比GBDT好。
原因如下：
先看一个例子： 假设一个二分类问题，label为0和1，特征有100维，如果有1w个样本，但其中只要10个正样本1，而这些样本的特征 f1的值全为1，而其余9990条样本的f1特征都为0(在高维稀疏的情况下这种情况很常见)。
我们都知道在这种情况下，树模型很容易优化出一个使用fyu’yuya’s’d’f’j’ka特征作为重要分裂节点的树，因为这个结点直接能够将训练数据划分的很好，但是当测试的时候，却会发现效果很差，因为这个特征f1只是刚好偶然间跟y拟合到了这个规律，这也是我们常说的过拟合。
那么这种情况下，如果采用LR的话，应该也会出现类似过拟合的情况呀：y = W1 x f1 + Wi x fi+….，其中 W1特别大以拟合这10个样本。为什么此时树模型就过拟合的更严重呢？
仔细想想发现，因为现在的模型普遍都会带着正则项，而 LR 等线性模型的正则项是对权重的惩罚，也就是 W1一旦过大，惩罚就会很大，进一步压缩 W1的值，使他不至于过大。但是，树模型则不一样，树模型的惩罚项通常为叶子节点数和深度等，而我们都知道，对于上面这种 case，树只需要一个节点就可以完美分割9990和10个样本，一个结点，最终产生的惩罚项极其之小。
这也就是为什么在高维稀疏特征的时候，线性模型会比非线性模型好的原因了：带正则化的线性模型比较不容易对稀疏特征过拟合。
基本原理：
首先需要说一说GBDT，它是一种基于boosting增强策略的加法模型，训练的时候采用前向分布算法进行贪婪的学习，每次迭代都学习一棵CART树来拟合之前 t-1 棵树的预测结果与训练样本真实值的残差（使用损失函数的负梯度来近似模拟残差）。
XGBoost对GBDT进行了一系列优化，如果不考虑工程实现、解决问题上的一些差异，xgboost与gbdt比较大的不同就是目标函数的定义： 比如损失函数进行了二阶泰勒展开、目标函数加入正则项、支持并行和默认缺失值处理（稀疏感知法）等，在可扩展性和训练速度上有了巨大的提升，但其核心思想没有大的变化
1. 相比GBDT，XGBoost添加了正则项，对每颗树的复杂度进行了惩罚，包括叶子节点个数和叶节点权重：
- 对目标函数进行了二阶泰勒展开，得到节点分裂增益公式：
主要过程是：一层一层的完成建树过程， xgboost训练的时候，是通过加法的方式进行训练，也就是每一次通过聚焦残差训练一棵树出来， 最后的预测结果是所有树的加和表示。
对所有特征都按照特征的数值进行预排序， 然后遍历所有特征上的所有分裂点位，计算按照这些候选分裂点位分裂后 的全部样本的目标函数增益，找到最大的那个增益对应的特征和候选分裂点位，从而进行分裂。
xgboost优化
xgboost缺点
虽然利用预排序和近似算法可以降低寻找最佳分裂点的计算量，但在节点分裂过程中仍需要遍历数据集；
预排序过程的空间复杂度过高，不仅需要存储特征值，还需要存储特征对应样本的梯度统计值的索引，相当于消耗了两倍的内存。
XGBoost类似于GBDT的优化版，不论是精度还是效率上都有了提升。都是聚焦残差，不过与GBDT相比，具体的优点有：
基分类器：XGBoost的基分类器不仅支持CART决策树，还支持线性分类器，此时XGBoost相当于带L1和L2正则化项的Logistic回归（分类问题）或者线性回归（回归问题）。而GBDT仅支持CART树作为基学习器。
🚩 节点分裂的方式不同，GBDT是用的基尼系数，XGBoost是经过优化推导后的。
损失函数：XGBoost对损失函数做了二阶泰勒展开，用二阶梯度可以更好地拟合损失下降的曲线。并且XGBoost还支持自定义损失函数（可以是最小平方差、logistic loss function、hinge loss function或者人为定义的loss function），只要损失函数一阶、二阶可导便可进行boosting，其进一步增大了模型的泛化能力； GBDT旨在通过不断加入新的树最快速度降低残差，只用了一阶导数信息
正则项：XGBoost的损失函数（目标函数）加了正则项，对叶子节点个数和叶子结点的权重分别进行L1、L2正则化， 相当于预剪枝，使得学习出来的模型更加不容易过拟合。
列抽样：XGBoost支持列采样，与随机森林类似，不仅可以减少计算，还可以用于防止过拟合，而GBDT使用全部特征。
缺失值处理：对树中的每个非叶子结点，XGBoost可以自动学习出它的默认分裂方向。如果某个样本该特征值缺失，会将其划入默认分支。
并行化：注意不是tree维度的并行，而是特征维度的并行。XGBoost预先将每个特征按特征值排好序，存储为块结构，（按特征值由小到大排序，不仅要存储样本的特征值，还需要保存样本的索引，索引指向内存中的具体数据，即样本的一阶、二阶梯度信息），分裂结点时，根据索引可以得到相应的梯度信息（一阶、二阶），可以采用多线程并行查找每个特征的最佳分割点，极大提升训练速度。
收缩率：XGBoost加入了收缩率系数，在每次迭代完决策树fi后将叶子节点的权重乘上该系数，来削弱每棵树的影响，让后面的树有更大的学习空间。实际应用中，一般把eta设置为较小的数，把迭代次数设置为较大值。
XGBoost在设计时，为了防止过拟合做了很多优化，具体如下：
XGBoost模型的一个优点就是允许特征存在缺失值。对缺失值的处理方式如下：（稀疏感知算法）
XGBoost目标函数最终推导形式如下：
利用一元二次函数求最值的知识，当目标函数达到最小值Obj星时，每个叶子结点的权重为wj*。
具体公式如下：
Gj代表在叶子节点j上，所有样本的一阶导数值之和；Hj代表在叶子节点j上，所有样本的二阶导数值之和。最终的obj叫做结构分数，结构分数越小，代表生成的树的结构就越好（让残差尽可能的小）。
对于不平衡的数据集，例如用户的购买行为，肯定是极其不平衡的，这对XGBoost的训练有很大的影响，XGBoost有两种自带的方法来解决：
XGBoost在训练前预先将特征按照特征值进行了排序，并存储为block结构，以后在结点分裂时可以重复使用该结构。
选择最佳分裂点的方法有两种：全局扫描法和加权分位数算法。
全局扫描法：可以采用特征并行的方法利用多个线程分别计算每个特征的最佳分割点（对每个特征的每个可能的分割点都计算其分裂增益），根据每次分裂后产生的增益，最终选择增益最大的那个特征的特征值作为最佳分裂点。
加权分位数算法：如果在计算每个特征的最佳分割点时，对每个样本都进行遍历，计算复杂度会很大，这种全局扫描的方法并不适用大数据和样本特征的取值较多的场景。XGBoost还提供了一种加权分位数算法（直方图近似算法），对特征排序后仅选择常数个候选分裂位置作为候选分裂点，选择最佳分裂点时，仅仅需要在候选分裂点中进行选择，极大提升了结点分裂时的计算效率。
（相当于对分裂点进行了分桶，尽量让左右子树的loss分布均匀（利用二阶导数值hi根据每一个样本对拟合残差的贡献程度进行加权），这样先选出了候选分割点，我们只需要保存每个桶中样本的一阶导数值的和、二阶导数值的和，然后对于每个候选分割点，计算分裂增益时，只需要将分割点左边的桶的值进行求和与右边的桶的值求和进行比较即可。因为桶的个数肯定小于样本的数量，所以得以加速）
目标函数的scalability：支持自定义loss function，只需要其一阶、二阶可导。有这个特性是因为泰勒二阶展开，得到通用的目标函数形式。
学习方法的scalability：Block结构支持并行化，支持 Out-of-core计算。
gain: 计算使用 特征i分裂节点的分裂增益之和/所有特征分裂节点的分裂增益之和 ，得到重要性。
注意：覆盖范围这里指的是一个特征用作分割点后，其影响的样本数量，即有多少样本经过该特征分割到两个子节点。
对存在缺失值的特征，一般的解决方法是：
一些模型如SVM和KNN，其模型原理中涉及到了对样本距离的度量，如果缺失值处理不当，最终会导致模型预测效果很差。
而树模型对缺失值的敏感度低，大部分时候可以在数据缺失时时使用。原因就是，一棵树中每个结点在分裂时，寻找的是某个特征的最佳分裂点（特征值），完全可以不考虑存在特征值缺失的样本，也就是说，如果某些样本缺失的特征值缺失，对寻找最佳分割点的影响不是很大。
XGBoost对缺失数据有特定的处理方法：训练时，根据叶子结点分裂增益公式，将该特征值missing的样本分别分配到左叶子结点和右叶子结点，两种情形都计算一遍后，选择放到分裂后增益最大的那个方向（左分支或是右分支），作为预测时特征值缺失样本的默认分支方向（右子节点）。
因此，对于有缺失值的数据在经过缺失处理后：
首先需要初始化一些基本变量，例如：
learning_rate：学习率（收缩系数）
n_estimators：树的个数 一般会设置early_stopping_rounds=200,如果新增加200棵树都不降低损失，那么就停止建树， verbose=50，每50次输出一次结果。
max_depth：构建树的深度，越大越容易过拟合；
min_child_weight：孩子节点中最小的样本权重和。当引入一次分裂后，重新计算新生成的左、右两个叶子结点的样本权重和。如果任一个叶子结点的样本权重低于某一个阈值，会放弃此次分裂。这涉及到一个超参数:最小样本权重和，是指如果一个叶子节点包含的样本数量太少也会放弃分裂，防止树分的太细。
gamma：损失下降多少才进行分裂（控制叶子节点的个数，分裂后节点就增加了），也称作最小划分损失min_split_loss，只有当划分后的损失函数损失下降值大于此阈值，当前叶子节点才继续划分。
subsample：对训练样本的随机采样比例
colsample_bytree：对特征的采样比例
scale_pos_weight：正样本在数据集中占得权重（可以解决正负样本比例不均衡的问题）
alpha ：L1正则化系数，try 1e-5, 1e-2, 0.1, 1, 100
lambda ：L2正则化系数
(1) 确定learning rate和estimator的数量
learning rate可以先用0.1，用cv来寻找最优的estimators
(2) max_depth和 min_child_weight
我们调整这两个参数是因为，这两个参数对输出结果的影响很大。我们首先将这两个参数设置为较大的数，然后通过迭代的方式不断修正，缩小范围。
max_depth，每棵子树的最大深度，check from range(3,10,2)。
min_child_weight，子节点的权重阈值，check from range(1,6,2)。
如果一个结点分裂后，它的所有子节点的权重之和都大于该阈值，该叶子节点才可以划分。
(3) gamma
也称作最小划分损失min_split_loss，check from 0.1 to 0.5，指的是，对于一个叶子节点，当对它采取划分之后，损失函数的降低值的阈值。
(4) subsample, colsample_bytree
subsample是对训练的采样比例
colsample_bytree是对特征的采样比例
both check from 0.6 to 0.9
(5) 正则化参数
alpha 是L1正则化系数，try 1e-5, 1e-2, 0.1, 1, 100
lambda 是L2正则化系数
(6) 降低学习率
降低学习率的同时增加树的数量，通常最后设置学习率为0.01~0.1
当出现过拟合时，有两类参数可以缓解：
第一类参数：用于直接控制模型的复杂度。包括max_depth,min_child_weight,gamma 等参数（即控制树的深度和叶子节点的个数）；
第二类参数：用于增加随机性，从而使得模型在训练时对于噪音不敏感。包括subsample,colsample_bytree（即对样本集采样、对特征采样）；
还有就是直接减小learning rate，但需要同时增加estimator 参数。（即减小收缩系数，让叶子节点的权重更小，让后面的树有更大的学习空间）。
（1）树生长策略：XGB采用level-wise的分裂策略，LGB采用leaf-wise的分裂策略。XGB对每一层所有节点做无差别分裂，（该策略遍历一次数据可以同时分裂同一层的叶子，容易进行多线程优化，也好控制模型的复杂度，不容易过拟合）但是可能有些节点增益非常小，对结果影响不大，带来不必要的开销（一层一层的走，不管它效果好不好）。Leaf-wise是在所有叶子节点中选取分裂收益最大的节点进行的，（该策略可以降低更多的误差，得到更好的精度），但是很容易出现过拟合问题，所以需要对最大深度做限制 。
（2）分割点查找算法：XGB使用特征预排序算法，LGB使用基于直方图的切分点算法，其优势如下：
（XGB寻找最优分裂点的复杂度=特征数量 X 分裂节点数量 X 样本的数量，LGB分别从这三个方面进行了优化）
但实际上xgboost的近似直方图算法（加权分位数算法）也类似于lightgbm这里的直方图算法，为什么xgboost的近似算法比lightgbm还是慢很多呢？
xgboost在每一层都动态构建直方图， 因为xgboost的直方图算法不是针对某个特定的feature，而是所有feature共享一个直方图(每个样本的权重是二阶导)，所以每一层都要重新构建直方图，而lightgbm中对每个特征都有一个直方图，所以构建一次直方图就够了。（XGB在每一层的分裂过程中，都需要对所有的特征重新选择候选分割点（即重新构建直方图），因为XGB在选取候选分割点的时候，考虑的是想让loss在左右子树上分布均匀，（二阶导数代表样本对降低loss的贡献程度，所以可以根据二阶导数值累加来选取候选分割点），每次分裂之后，节点中的样本数量发生变化，每个节点的二阶导数和也是变化的，所以需要重新构建直方图。）
（3）支持离散变量：XGB无法直接输入类别型变量，因此需要事先对类别型变量进行编码（例如独热编码），而LightGBM可以直接处理类别型变量（采用many-vs-many的切分方式，将类别特征分为两个子集，实现类别特征的最优切分。基本思想为每次分组时，都会根据训练目标对类别特征进行分类：在枚举分割点之前，先把直方图按照每个类别对应的label均值进行排序，然后按照排序的结果依次枚举最优分割点）。
（4）缓存命中率：XGB使用Block结构的一个缺点是取梯度的时候，是通过索引来获取的，而这些梯度的获取顺序是按照特征的大小顺序的，（并且不同特征的访问顺序也不同），这将导致非连续的内存访问，可能使得CPU cache缓存命中率低，从而影响算法效率。而LGB是基于直方图分裂特征的，梯度信息都存储在一个个bin（桶：离散值索引？）中，所以访问梯度是连续的，缓存命中率高。
（5）LightGBM 与 XGboost 的并行策略不同：
learning_rate：学习率，预先设定一个较高的值，如0.1
boosting_type: 默认选择gbdt
n_estimators/num_boost_round：迭代次数（残差树的个数）
max_depth：树的深度
num_leaves：叶子个数，一般小于2**max_depth
min_data_in_leaf：节点中样本点最小个数
max_bin：最大分桶的个数（离散化时取值的最大值）
feature_fraction: 特征的采样率
bagging_fraction: 样本的采样率
bagging_freq: k，意味每k次迭代（每生成k棵树）执行bagging
lambda_l1: L1正则化参数
lambda_l2: L2正则化参数
min_split_gain: 分裂最小增益阈值，分裂增益小于阈值则终止分裂
针对leaf-wise树的参数优化
针对更快的训练速度
获得更好的准确率
缓解过拟合
第一步：学习率和迭代次数我们先把学习率先定一个较高的值，这里取 learning_rate = 0.1，其次确定估计器boosting/boost/boosting_type的类型，不过默认都会选gbdt。
'boosting_type'/'boosting': 'gbdt'
'objective': 'binary'
'metric': 'auc'
# 以下是选择的初始值
'max_depth': 5 # 由于数据集不是很大，所以选择了一个适中的值，其实4-10都无所谓。
'num_leaves': 30 # 由于lightGBM是leaves_wise生长，官方说法是要小于2^max_depth
'subsample'/'bagging_fraction':0.8 # 数据采样
'colsample_bytree'/'feature_fraction': 0.8 # 特征采样迭代的次数，也可以说是残差树的数目，参数名为n_estimators/num_iterations/num_round/num_boost_round。我们可以先将该参数设成一个较大的数，然后在cv结果中查看最优的迭代次数lgb.cv(params, data_train, num_boost_round=1000, nfold=5, stratified=False, shuffle=True, metrics='auc',early_stopping_rounds=50,seed=0)。
我们根据以上结果，就可以取n_estimators=188。
第二步：确定max_depth和num_leaves这是提高精确度的最重要的参数。这里我们引入sklearn里的GridSearchCV()函数进行搜索。
from sklearn.grid_search import GridSearchCV
params_test1={'max_depth': range(3,8,1), 'num_leaves':range(5, 100, 5)}
gsearch1 = GridSearchCV(estimator = lgb.LGBMClassifier(boosting_type='gbdt',objective='binary',metrics='auc',learning_rate=0.1, n_estimators=188, max_depth=6, bagging_fraction = 0.8,feature_fraction = 0.8),
param_grid = params_test1, scoring='roc_auc',cv=5,n_jobs=-1)
gsearch1.fit(X_train,y_train)
gsearch1.grid_scores_, gsearch1.best_params_, gsearch1.best_score_根据结果，我们取max_depth=4, num_leaves=10
第三步：确定min_data_in_leaf和max_bin
params_test2={'max_bin': range(5,256,10), 'min_data_in_leaf':range(1,102,10)}
gsearch2 = GridSearchCV(estimator = lgb.LGBMClassifier(boosting_type='gbdt',objective='binary',metrics='auc',learning_rate=0.1, n_estimators=188, max_depth=4, num_leaves=10,bagging_fraction = 0.8,feature_fraction = 0.8),
param_grid = params_test2, scoring='roc_auc',cv=5,n_jobs=-1)
gsearch2.fit(X_train,y_train)
gsearch2.grid_scores_, gsearch2.best_params_, gsearch2.best_score_这个结果就不显示了，根据结果，我们取min_data_in_leaf=51，max_bin in=15。
第四步：确定feature_fraction、bagging_fraction、bagging_freq
第五步：确定lambda_l1和lambda_l2
第六步：确定 min_split_gain
第七步：降低学习率，增加迭代次数，验证模型
model=lgb.LGBMClassifier(boosting_type='gbdt',objective='binary',metrics='auc',learning_rate=0.01, n_estimators=1000, max_depth=4, num_leaves=10,max_bin=15,min_data_in_leaf=51,bagging_fraction=0.6,bagging_freq= 0, feature_fraction= 0.8,
lambda_l1=1e-05,lambda_l2=1e-05,min_split_gain=0)
model.fit(X_train,y_train)
y_pre=model.predict(X_test)
print("acc:",metrics.accuracy_score(y_test,y_pre))
print("auc:",metrics.roc_auc_score(y_test,y_pre))这样会发现， 调完参之后， 比使用默认参数的acc，auc都会有所提高。还有一种是LightGBM的cv函数调参， 这个比较省事，写好代码自动寻优，但是需要调参经验，如何设置一个好的参数范围， 这个不写了，篇幅太长，具体的看最后面那个链接吧。
sklearn里的GridSearchCV()函数
与GBDT不同之处？
lightgbm和xgboost有什么区别？他们的loss一样么？ 算法层面有什么区别？
(1) XGBoost重要参数
xgboost主要分为三类参数:
1.通用参数 general parameter
booster: 每次迭代的模型选择，gbtree或者gbliner
silent: 控制打印信息，(过时，被verbosity代替)
nthread：并行的线程数，默认使用最大的核数
2.Booster参数：Parameters for Tree Booster
eta: shinkage防止过拟合，默认0.3
gamma:公式中叶子节点个数的参数，也就是分类后损失函数的增益，增益大于这个阈值，才会对节点进行分裂。
max_depth:默认为0，树的最大深度，用来避免过拟合。
min_child_weight: 最小的叶子节点样本权重和，如果节点分裂造成一个叶子节点的样本权重和小于该值，则放弃分裂。
max_delta_step: 该参数仙子每棵树权重改变的最大步长。一般用不到，但是在数据样本极度不平衡时，可能对逻辑回归有帮助。
subsample：训练样本随机采样的比例。
colsample_bytree, colsample_bylevel, colsample_bynode: 列采样的参数设置。bytree表示在构建每棵树的时候使用。bylevel表示构建每层节点的时候使用，bynode在每次分裂的时候使用。
lambda: L2正则化项。默认为1.
alpha：L1的正则化项.
scale_pos_weight: 控制正负样本的平衡，用于不平衡数据。
3.学习任务参数：控制训练目标的表现
objective:定义损失函数。常用值有binary:logistic; multi:softmax; multi:softprob
eval_metic: 验证集的评估指标。rmse, mae, logloss, error, merror, mlogloss, auc
seed:随机数的种子，设置它可以复现随机数的结果，也可以用于调整参数。
(2) XGBoost调参技巧
a.当出现过拟合时，有两类参数可以缓解：
也可以直接检查步长eta，此时需要增加num_round参数.
b.当遇到数据不平衡时(如广告点击率预测任务)，有两种方式提高模型的预测性能：
可以通过scale_pos_weight参数来平衡正负样本的权重; 使用AUC来评估。
不能重新平衡正负样本**；设置max_delta_step为一个有限的值(如1)，从而有助于收敛
LightGBM （Light Gradient Boosting Machine）是一个实现GBDT算法的框架，支持高效率的并行训练。
LigthGBM也是一种boosting算法，它由微软开源，是XGB的一种轻量级实现，用于分类或者回归问题。在准确率与XGB相近的情况下，大大减少运行时长和内存占用。
LightGBM提出的主要原因就是为了解决GBDT在海量数据遇到的问题，让GBDT可以更好更快地用于工业实践。
- 单边梯度抽样算法 - 过滤掉梯度小的样本，减少了大量的计算；
- 直方图算法 - 将遍历样本转变为遍历直方图，极大的降低了时间复杂度；
- 互斥特征捆绑算法（EFB）
- 带深度限制的 Leaf-wise 算法 - 减少了很多不必要的计算量
直方图算法的基本思想是先把连续的浮点特征值离散化成k个整数（其实又是分桶的思想，而这些桶称为bin，比如[0,0.1)→0, [0.1,0.3)→1），同时构造一个宽度为k的直方图。
在遍历数据的时候，根据离散化后的值作为索引在直方图中累积统计量，当遍历一次数据后，直方图累积了需要的统计量，然后根据直方图的离散值，遍历寻找最优的分割点。
使用直方图算法有很多优点。首先，最明显就是内存消耗的降低，直方图算法不仅不需要额外存储预排序的结果，而且可以只保存特征离散化后的值，而这个值一般用8位整型存储就足够了，内存消耗可以降低为原来的1/8。然后在计算上的代价也大幅降低，预排序算法每遍历一个特征值就需要计算一次分裂的增益，而直方图算法只需要计算k次（k可以认为是常数），时间复杂度从O(#data#feature)优化到O(k#features)。
在XGBoost中，树是按层生长的，称为Level-wise tree growth，同一层的所有节点都做分裂，最后剪枝，如下图所示：
Level-wise过一次数据可以同时分裂同一层的叶子，容易进行多线程优化，也好控制模型复杂度，不容易过拟合。但实际上Level-wise是一种低效的算法，因为它不加区分的对待同一层的叶子，带来了很多没必要的开销，因为实际上很多叶子的分裂增益较低，没必要进行搜索和分裂。
在Histogram算法之上，LightGBM进行进一步的优化。首先它抛弃了大多数GBDT工具使用的按层生长 (level-wise) 的决策树生长策略，而使用了带有深度限制的按叶子生长 (leaf-wise)算法。
Leaf-wise则是一种更为高效的策略，每次从当前所有叶子中，找到分裂增益最大的一个叶子，然后分裂，如此循环。因此同Level-wise相比，在分裂次数相同的情况下，Leaf-wise可以降低更多的误差，得到更好的精度。Leaf-wise的缺点是可能会长出比较深的决策树，产生过拟合。因此LightGBM在Leaf-wise之上增加了一个最大深度的限制，在保证高效率的同时防止过拟合。
LightGBM另一个优化是Histogram（直方图）做差加速。一个容易观察到的现象：一个叶子的直方图可以由它的父亲节点的直方图与它兄弟的直方图做差得到。通常构造直方图，需要遍历该叶子上的所有数据，但直方图做差仅需遍历直方图的k个桶。
利用这个方法，LightGBM可以在构造一个叶子的直方图后，可以用非常微小的代价得到它兄弟叶子的直方图，在速度上可以提升一倍。
实际上大多数机器学习工具都无法直接支持类别特征，一般需要把类别特征，转化到多维的0/1特征，降低了空间和时间的效率。而类别特征的使用是在实践中很常用的。基于这个考虑，LightGBM优化了对类别特征的支持，可以直接输入类别特征，不需要额外的0/1展开。并在决策树算法上增加了类别特征的决策规则。在Expo数据集上的实验，相比0/1展开的方法，训练速度可以加速8倍，并且精度一致。据我们所知，LightGBM是第一个直接支持类别特征的GBDT工具。
极简示例:
import numpy as np
import catboost as cb
# 读数据
train_data = np.random.randint(0, 100, size=(100, 10))
train_label = np.random.randint(0, 2, size=(100))
test_data = np.random.randint(0,100, size=(50,10))
print(train_data,train_label,test_data)
# 建立模型
model = cb.CatBoostClassifier(iterations=2, depth=2, learning_rate=0.5, loss_function='Logloss',
logging_level='Verbose')
# 模型拟合
model.fit(train_data, train_label, cat_features=[0,2,5])
# 预测
preds_class = model.predict(test_data)
preds_probs = model.predict_proba(test_data)
print('class = ',preds_class)
print('proba = ',preds_probs)设空间中两个点为(x1,y1),(x2,y2):
欧式距离:
曼哈顿距离（城区距离）:
d(i,j)=|X1-X2|+|Y1-Y2|
余弦距离:
欧式距离与余弦距离的对比?
1.欧式距离的数值受到维度的影响，余弦相似度不受维度影响, 在高维的情况下也依然保持低维完全相同时相似度为1等性质。
2.欧式距离体现的是距离上的绝对差异，余弦距离体现的是方向上的相对差异。
切比雪夫距离（横向纵向最大距离）:
dis=max(abs(x1-x2),abs(y1-y2))
特征组合的思想很简单，通过将单独的特征进行组合（相乘或求笛卡尔积）而形成的合成特征。比如属性A有三个特征，属性B有两个特征，笛卡尔积后就有六个组合特征，然后用one hot 或其他embedding方式给新的特征编码。
因为它假定所有的特征在数据集中的作用是同样重要和独立的。正如我们所知，这个假设在现实世界中是很不真实的，因此，说朴素贝叶斯真的很“朴素”。
启发式搜索算法蕴含着许多人生哲学，它虽不是数学方法，其思想更类似于人类解决问题的思想和一些人生中总结的道理，值得好好体会。最后用网上一段描述各种搜索算法的例子来作为总结：
为了找出地球上最高的山，一群有志气的兔子们开始想办法。 （1）兔子朝着比现在高的地方跳去。他们找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是爬山法，它不能保证局部最优值就是全局最优值。 （2）兔子喝醉了。他随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，他渐渐清醒了并朝他踏过的最高方向跳去。这就是模拟退火。 （3）兔子们知道一个兔的力量是渺小的。他们互相转告着，哪里的山已经找过，并且找过的每一座山他们都留下一只兔子做记号。他们制定了下一步去哪里寻找的策略。这就是禁忌搜索。 （4）兔子们吃了失忆药片，并被发射到太空，然后随机落到了地球上的某些地方。他们不知道自己的使命是什么。但是，如果你过几年就杀死一部分海拔低的兔子，多产的兔子们自己就会找到珠穆朗玛峰。这就是遗传算法。
利用模型的 feature_importances_方法。
阈值的选择会进行遍历并选择最佳的阈值
from numpy import sort
from sklearn.feature_selection import SelectFromModel # Fit model using each importance as a threshold
thresholds = sort(model_XGB.feature_importances_)
for thresh in thresholds:
# select features using threshold
selection = SelectFromModel(model_XGB, threshold=thresh, prefit=True)
select_X_train = selection.transform(X_train)
# train model
selection_model = XGBClassifier()
selection_model.fit(select_X_train, y_train)
# eval model
select_X_test = selection.transform(X_test)
y_pred = selection_model.predict(select_X_test)
predictions = [round(value) for value in y_pred]
accuracy = accuracy_score(y_test, predictions)
print("Thresh=%.3f, n=%d, Accuracy: %.2f%%" % (thresh, select_X_train.shape[1],
accuracy*100.0))判别方法：由数据直接学习决策函数 Y = f（X），或者由条件分布概率 P（Y|X）作为预测模型，即判别模型。
生成方法：由数据学习联合概率密度分布函数 P（X,Y）,然后求出条件概率分布P(Y|X)作为预测的模型，即生成模型。
由生成模型可以得到判别模型，但由判别模型得不到生成模型。
常见的判别模型有：K近邻、SVM、决策树、感知机、线性判别分析（LDA）、线性回归、传统的神经网络、逻辑斯蒂回归、boosting、条件随机场
常见的生成模型有：朴素贝叶斯、隐马尔可夫模型、高斯混合模型、文档主题生成模型（LDA）、限制玻尔兹曼机