本系列另一篇文章《决策树》

https://blog.csdn.net/juwikuang/article/details/89333344
本文源代码：

https://github.com/juwikuang/machine_learning_step_by_step
最近我发现我之前写的一篇文章《一个公式告诉你为什么程序员要转算法工程师》

http://blog.csdn.net/juwikuang/article/details/73057194

有很多人访问。我想，很多程序员和我当初一样，想从程序员转算法工程师。
说说我当初为什么会想到升级成算法工程师。记得三年前，我还在印孚瑟斯（Infosys），我们的CFO非常自豪的宣布公司已经成功的让专科生的比例提高了，让本科生的比例降低了。我作为一个本科程序员，听了十分难受。当然，公司这样做是为了利润，也合理合法。换了我是CFO，我也会这样做，不过，我应该不会像他一样大声说。有些事，可以做，不能说。
后来，机缘巧合，我学习了机器学习，走上了算法工程师这条路。当时我学机器学习，是从吴恩达（Andrew Ng）的Coursera课程开始的。很多人和我一样，也是开了这门课，开始机器学习的。这门课挺好，可惜开发语言用了Octave，以至于我每次写作业，都很痛苦，因为我还要学Octave语言，而且这东西学了也没啥用。另外，这门课是英语的，只有少数人能看懂。
本文的目的，就是从最基本，最简单的机器学习算法讲起，手把手的教你实现这个算法。一边编程，一边就明白这个算法的原理了。我本人也是程序员转的算法工程师，我们的强项就是编程，弱项就是数学。我针对这个特点，专门做了以下教程。
言归正传。首先我们看看线性回归在整个机器学习里的位置。
从机器学习到线性回归

今天，我们只关注机器学习到线性回归这条线上的概念。别的以后再说。为了让大家听懂，我这次也不查维基百科了，直接按照自己的理解用大白话说，可能不是很严谨。
机器学习就是机器可以自己学习，而机器学习的方法就是利用现有的数据和算法，解出算法的参数。从而得到可以用的模型。
监督学习就是利用已有的数据（我们叫X，或者特征），和数据的标注（我们叫Y），找到x和y之间的对应关系，或者说是函数f。
回归分析是一种因变量为连续值得监督学习。
线性回归是一种x和y之间的关系为线性关系的回归分析。y=a1x1+a2x2+by=a_1x_1+a_2x_2+by=a1​x1​+a2​x2​+b，这个叫线性关系。如果这里出现了x2x^2x2,$log(x)$, $sin(x)$之类的，那就不是线性关系了。
一元线性回归说的是，自变量x是一个纯量（scalar）。scalar类型的变量，是不可再分的。
我希望你能说明白这些概念的关系。不过，我自己也是花了很久才了解清楚的。如果你没听明白，也没关系。毕竟都是概念，没什么实际的例子，也很难理解。等你看完了本文，了解了一元线性回归。回过头来再看这些概念，就能更好的理解了。
问题
这里，我们的问题是，找出算法工程师和程序员之间的工资关系。这里直接给出北京，上海，杭州，深圳，广州的工资。

城市
x-程序员工资
y-算法工程师工资
北京
1.3854
2.1332
上海
1.2213
2.0162
杭州
1.1009
1.9138
深圳
1.0655
1.8621
广州
0.09503
1.8016
把他们用图打出来看看他们之间的关系。

由图可见，他们之间大致是一个线性关系，这时候，我们就可以试着用一元线性回归去拟合（fit）他们之间的关系。
数学模型
一元线性回归公式
以下是公式
$y=ax+b+\epsilon$
y 为应变量 dependent variable

x 为自变量 independent variable

a 为斜率 coeffient

b 为截距 intercept

ε （读作epsilon）为误差，正态分布

线性回归的目标是，找到一组a和b，使得ε最小
y^=ax+b\hat{y}=ax+by^​=ax+b
ε=y−y^ε=y-\hat{y}ε=y−y^​
y^\hat{y}y^​ 读作y hat，也有人读作y帽子。这里的帽子一般表示估计值，用来区别真实值y。
下图可以更好的帮助你理解。


（图片来自互联网）
黑色的点为观测样本，即$y=ax+b+\epsilon$。
x红色的线为回归线，即y^=ax+b\hat{y}=ax+by^​=ax+b。
x蓝色的线段为误差，即ε=y−y^ε=y-\hat{y}ε=y−y^​
方差 - 损失函数 Cost Function
在机器学习中，很多时候，我们需要找到一个损失函数。有了损失函数，我们就可以经过不断地迭代，找到损失函数的全局或者局部最小值（或者最大值）。损失函数使得我们的问题转化成数学问题，从而可以用计算机求解。在线性回归中，我们用方差作为损失函数。我们的目标是使得方差最小。
下面的表格解释了什么是方差。

其中SSE(Sum of Square Error)是总的方差，MSE（Mean Square Error）是方差的平均值。
而这里的损失函数，用的是0.5 * MSE。即：
J(a,b)=12n∑i=0n(yi−y^i)2J(a,b)=\frac{1}{2n}\sum_{i=0}^{n}(y_i−\hat{y}_i )^2J(a,b)=2n1​∑i=0n​(yi​−y^​i​)2
记住，这里的损失函数是针对参数a和b的函数，y和y^\hat{y}y^​ 其实都是已知的。
优化方法 Optimization Function
有了损失函数，我们还需要一个方法，使得我们可以找到这个损失函数的最小值。机器学习把他叫做优化方法。这里的优化方法，就是算损失的方向。或者说，当我的参数变化的时候，我的损失是变大了还是变小了。如果a变大了，损失变小了。那么，说明a增大这个方向是正确的，我们可以朝着这个方向继续小幅度的前进。反之，就应该考虑往相反的方向试试看。因为每个参数（a和b）都是一维的，所以，所谓的方向，无非就是正负符号。
这里，我们需要用偏微分的方法，得到损失函数的变化量。即：
∂J∂a=∂12n∑i=0n(yi−y^i)2∂a\frac{\partial J}{\partial a} = \frac{\partial \frac{1}{2n}\sum_{i=0}^{n}(y_i−\hat{y}_i )^2}{\partial a}∂a∂J​=∂a∂2n1​∑i=0n​(yi​−y^​i​)2​
=1n∑i=0n(yi−axi−b)∂(yi−axi−b)∂a= \frac{1}{n}\sum_{i=0}^{n}(y_i-ax_i-b) \frac{\partial (y_i-ax_i-b)}{\partial a}=n1​∑i=0n​(yi​−axi​−b)∂a∂(yi​−axi​−b)​
=1n∑i=0n(yi−axi−b)(−xi)= \frac{1}{n}\sum_{i=0}^{n}(y_i-ax_i-b) (-x_i)=n1​∑i=0n​(yi​−axi​−b)(−xi​)
=1n∑i=0nx(y^i−yi)= \frac{1}{n}\sum_{i=0}^{n}x(\hat{y}_i-y_i)=n1​∑i=0n​x(y^​i​−yi​)
∂J∂b=∂12n∑i=0n(yi−y^i)2∂a\frac{\partial J}{\partial b} =  \frac{\partial \frac{1}{2n}\sum_{i=0}^{n}(y_i−\hat{y}_i )^2}{\partial a}∂b∂J​=∂a∂2n1​∑i=0n​(yi​−y^​i​)2​
=1n∑i=0n(yi−axi−b)∂(yi−axi−b)∂b= \frac{1}{n}\sum_{i=0}^{n}(y_i-ax_i-b) \frac{\partial (y_i-ax_i-b)}{\partial b}=n1​∑i=0n​(yi​−axi​−b)∂b∂(yi​−axi​−b)​
=1n∑i=0n(yi−axi−b)(−1)= \frac{1}{n}\sum_{i=0}^{n}(y_i-ax_i-b) (-1)=n1​∑i=0n​(yi​−axi​−b)(−1)
=1n∑i=0n(y^i−yi)= \frac{1}{n}\sum_{i=0}^{n}(\hat{y}_i-y_i)=n1​∑i=0n​(y^​i​−yi​)
如果你已经忘了微积分，你暂时可以不必纠结上面的公式，只要知道公式给出了损失函数的变化就可以了。伟大的python还提供了sympy，你可以用sympy做微积分。这部分我也放在附件代码里了，有兴趣的可以看一下。
之前说到，整过迭代过程是小幅度进行的。这里，就需要一个超参数来控制这个过程。这个超参数就是$\alpha$，通常是0.01.
这时，我们就可以去更新a和b的值：
a=a−α∂J∂aa = a - \alpha \frac{\partial J}{\partial a}a=a−α∂a∂J​
b=b−α∂J∂bb = b - \alpha \frac{\partial J}{\partial b}b=b−α∂b∂J​
到这里，在你继续往下读之前，你先自己考虑一下，为什么这里是负号？
你考虑好了么，如果你考虑好了，我就公布答案了。
本身∂J∂a\frac{\partial J}{\partial a}∂a∂J​ 和 ∂J∂b\frac{\partial J}{\partial b}∂b∂J​ 是损失函数的变化量。如果损失函数随着a变大了，即 ∂J∂a\frac{\partial J}{\partial a}∂a∂J​ 为正。说明a的增大会导致损失函数的增大。那么是不是说，a的减小会使得损失函数减小呢？而我们的目标是使得J最小，所以，这个时候，我们的a要减小一点点。


（图片来自互联网）
算法步骤
a和b的起始值设置为零
通过模型y^=ax+b\hat{y}=ax+by^​=ax+b，我们可以算出y^\hat{y}y^​
有了y^\hat{y}y^​，就可以用优化方法算去更新参数
重复2和3，直到找到J的最小值
流程图如下：
Created with Raphaël 2.2.0开始a=0, b=0计算模型y_hat=ax+b计算a和b的微分更新a和b找到损失函数的最小值结束yesno
下图解释了模型，损失函数和优化方法之间的关系。

Python 实现
理论部分先告一段落，我们现在开始写代码，实现一元线性回归。
首先是模型，这个很简单：
def model(a, b, x):
    return a*x + b

接着，是损失函数：
def cost_function(a, b, x, y):
    n = 5
    return 0.5/n * (np.square(y-a*x-b)).sum()

最后，是优化函数：
def optimize(a,b,x,y):
    n = 5
    alpha = 1e-1
    y_hat = model(a,b,x)
    da = (1.0/n) * ((y_hat-y)*x).sum()
    db = (1.0/n) * ((y_hat-y).sum())
    a = a - alpha*da
    b = b - alpha*db
    return a, b

以上三个函数中a和b是标量（scalar value），x和y是向量（vector）

至此，一元线性回归的主要部分就完成了。一共才14行代码，是不是很简单。
训练模型
有了模型，损失函数，优化函数，我们就可以训练模型了。具体过程请见附件代码。
这里给出分别训练1次，再训练5次，再训练10次，再训练100，再训练10000次的模型。





从上面几幅图，我们可以看到，随着训练次数的增加，回归线越来越接近样本了。我们自己写的线性回归比较简单，我只能目测，凭直觉感觉损失函数已经达到了最小值，我们就停在10000次吧。
看得再多，不如自己动手。阅读下一章节之前，请自己实现一元线性回归。
这里有现成的代码，供你参考。
http://download.csdn.net/download/juwikuang/10050886
模型评价
在机器学习中，模型的好坏是有标准的。在回归模型中，我们用R2R^2R2 来评价模型。公式：
R2=SSR/SSTR^2=SSR/SSTR2=SSR/SST

其中
SSR=∑i=0n(y^i−yˉ)SSR=\sum_{i=0}^{n}(\hat{y}_i-\bar{y})SSR=∑i=0n​(y^​i​−yˉ​)
SST=∑i=0n(yi−yˉ)SST=\sum_{i=0}^{n}(y_i-\bar{y})SST=∑i=0n​(yi​−yˉ​)
yˉ\bar{y}yˉ​ 读作y bar，是y的平均值。

可以证明$SST=SSR+SSE$，证明过程又会涉及到期望等概念，我们这里不展开了。
好了，现在你应该回到代码中去计算R2R^2R2 了。
用scikit-learn训练和评价模型
平时在工作中，我们不可能自己去写回归模型，最常用的第三方工具是scikit-learn。

其官网是：

http://scikit-learn.org/
以下是ipython代码。
import numpy as np
from sklearn.linear_model import LinearRegression
import matplotlib.pyplot as plt
%matplotlib inline

x = [13854,12213,11009,10655,9503] #程序员工资，顺序为北京，上海，杭州，深圳，广州
x = np.reshape(x,newshape=(5,1)) / 10000.0
y =  [21332, 20162, 19138, 18621, 18016] #算法工程师，顺序和上面一致
y = np.reshape(y,newshape=(5,1)) / 10000.0
# 调用模型
lr = LinearRegression()
# 训练模型
lr.fit(x,y)
# 计算R平方
print lr.score(x,y)
# 计算y_hat
y_hat = lr.predict(x)
# 打印出图
plt.scatter(x,y)
plt.plot(x, y_hat)
plt.show()


恭喜你，看完了本文，也学会了一元线性回归。如果对你有帮助，请给我一个赞。你的支持和鼓励是我继续写下去的动力。
如果有疑问，请下面留言。
python机器学习手写算法系列
完整源代码：
https://github.com/juwikuang/machine_learning_step_by_step
欢迎阅读本系列其他文章：
《python机器学习手写算法系列——线性回归》
《python机器学习手写算法系列——逻辑回归》
《python机器学习手写算法系列——决策树》
《python机器学习手写算法系列——kmeans聚类》

Python机器学习教程

第一章：对于机器学习，我们选择了Python

第二章：了解SciPy、Pandas

持续更新 ... ...

 



 

前面几篇博文已经整理了Python做数据分析和建模以及机器学习基础知识。

这篇博文主要分享Python做数据分析和建模的实践案例应用。

分为两部分：

1、Python机器学习实践案例的算法总结。

     见博文下方的算法总结表格。

2、案例和代码实现。

     每个案例单独用一篇博文来讲解逻辑和Python代码实现。点击对应的链接到相应的博文中去阅读。

    （1）朴素贝叶斯、费舍尔分类器模型（文档分类）

            ---引申 用gesim-word2vec实现词矢量化

    （2）优化算法模型：

            [1] 旅行行程优化问题

            [2] 住宿房间分配问题

    （3）决策树分类建模

    （4）分级聚类、K均值聚类

              [1] 使用LSA潜在语义分析，聚类评论主题

    （5）KNN算法

            [1]数值预测、区间概率预测、概率密度图

            [2]协同过滤推荐简单实现

         ---引申  [3] 协同过滤推荐-pyspark实现

        ---引申  [4]spark的安装和Jupyter使用

    （6）寻找独立特征-非负矩阵因式分解

    （7）支持向量机

    （8）神经网络

    （9）特征工程

          [1]受限波兹曼机RBM在机器学习中的使用

          [2]在机器学习pipeline中同时使用PCA和LDA

          [3]线性判别式LDA的两种实现方式

          [4]主成分分析PCA的两种实现方式

          [5]用PCA、LDA、LR做人脸识别

 

机器学习实践案例算法总结
		
算法
			
算法描述/原理概述
			
适用的数据集类型
			
Python代码实现的主要步骤
			
优缺点说明
		
贝叶斯分类器
			
根据贝叶斯公式：P(cat|item) = P(item|cat)*P(cat)/P(item),

			其中，P(item|cat) = P(feature|cat)*P(feature|cat)*P(feature|cat)*…
			
适应于所有能转换成一组特征列表的数据集。
			
1、定义特征提取函数getfeature

			2、利用样本对分类器进行训练，得到记录了特征和某个特定分类相关联的数字概率P(feature|(cat)

			3、分类预测(朴素贝叶斯分类器)
			
优点：

			1、训练和分类计算的速度快

			2、支持增量式的训练

			3、特征的概率值被保存，所以分类学习的解释相对简单

			缺点：

			1、无法处理特征组合会产生分类结果影响的情况
		
决策树分类器
			
从根部开始构造决策树，在每一步中都会选择一个属性，利用该属性以最佳的可能方式对数据进行拆分。

			对于构造完成的决策树，从树的根部节点开始，对每一个节点的判断条件进行检查，走相应的yes or no 分支直至叶节点，即代表新数据的预测分类
			
适应于数值型或者名词性的有分类结果的数据集
			
1、创建决策树。

			熵、基尼不纯度衡量集合的混乱、不纯程度。信息增益来衡量一次拆分的好坏。

			2、决策树剪枝

			3、决策树显示--树状图/文本打印

			4、决策树分类
			
优点：

			1、易于对模型的解释和理解。重要的判断因素都在靠近根部的位置。

			2、能处理变量之间的相互影响。

			缺点：

			1、不擅长对数值结果的预测。

			2、不支持增量式的训练。
		
神经网络
			
　
			
　
			
　
			
　
		
支持向量机SVM
			
　
			
　
			
　
			
　
		
K最近邻算法KNN
			
对一个待预测的新数据项，将其与已经知道结果值的数据项进行比较，从中找出最为接近的若干项，并根据距离远近求其加权平均值以得到最终的预测结果。
			
可以做数值预测的数据集
			
1、对变量进行缩放处理和交叉验证

			2、给出一个距离度量算法/相似度度量算法

			3、加权KNN算法预测
			
优点：

			1、简单易懂 2、合理的数据缩放量不但可以改善预测效果，还能知道预测过程中各个变量的重要程度。3、新的数据可以随时被添加进来，是一种online的技术。

			缺点：

			1、计算低效。每一个待预测项必须和所有其他数据进行比较。2、寻找合理的缩放因子的过程很乏味、计算和评估的计算工作量很大。
		
分级聚类
			
它是构造一颗由所有数据项构成的树的过程。

			工作方式：寻找两个距离最接近的数据项，将它们合二为一，新聚类的"位置"等于原两个数据项位置的均值。重复此过程，直到每个数据项都被包含在了一个大的聚类中为止。
			
任何一个具有一个或多个数值属性的数据集
			
1、给出一个相关系数度量方法

			2、分级聚类

			3、绘制分级聚类树状图
			
优点：

			1、层级结构可以显示为树状图的形状，易于解读

			2、面对一个全新的数据集，并不清楚想要多少群组时可通过分级聚类观察出哪些群组最接近
		
K-Means聚类
			
它是将数据拆分到不同群组的方法。

			工作方式：随机产生K个中心点的位置，将每个数据项都分配到距离最近的中心点。将中心位置移到分配给原中心点的所有项的平均位置处。重复上述聚类步骤。直到中心位置不再变化或达到某阈值。
			
任何一个具有一个或多个数值属性的数据集
			
1、给出想要的群组数量

			2、给出一个相关系数度量方法

			3、K-means聚类

			4、打印分类群组结果
			
优点：

			1、聚类得到的群组易于打印和识别
		
模拟退火算法
			
以一个随机推测的题解开始，以此为基准随机选择一个方向，找到另一个近似解，判断其成本值。如果新题解的成本值小，则替换原题解。如果成本值更大，则用概率觉得是否取代原题解。迭代至温度几乎为0时，返回题解。
			
给定定义域和成本函数的优化问题
			
1、确定变量定义域domain

			2、定义成本函数costf
			
　
		
遗传算法
			
以一组种群题解开始，筛选出其中成本值最低的精英题解，利用变异、交叉的修改方法将精英题解扩充到原种群大小，称新得到的这个种群为下一代。迭代至一定代数或成本值达到某阈值或种群不再改变，返回成本值最低的作为最优解。
			
给定定义域和成本函数的优化问题
			
1、确定变量定义域domain

			2、定义成本函数costf
			
　
		
非负矩阵因式分解NMF
			
　
			
　
			
　
			
　
		

分享一个朋友的人工智能教程。零基础！通俗易懂！风趣幽默！还带黄段子！大家可以看看是否对自己有帮助：点击打开

    



全栈工程师开发手册 （作者：栾鹏）

python教程全解

安装
pip install lightgbm

gitup网址：https://github.com/Microsoft/LightGBM
中文教程
http://lightgbm.apachecn.org/cn/latest/index.html
lightGBM简介
xgboost的出现，让数据民工们告别了传统的机器学习算法们：RF、GBM、SVM、LASSO………。现在微软推出了一个新的boosting框架，想要挑战xgboost的江湖地位。
顾名思义，lightGBM包含两个关键点：light即轻量级，GBM 梯度提升机。
LightGBM 是一个梯度 boosting 框架，使用基于学习算法的决策树。它可以说是分布式的，高效的，有以下优势：


更快的训练效率


低内存使用


更高的准确率


支持并行化学习


可处理大规模数据


xgboost缺点
其缺点，或者说不足之处：
每轮迭代时，都需要遍历整个训练数据多次。如果把整个训练数据装进内存则会限制训练数据的大小；如果不装进内存，反复地读写训练数据又会消耗非常大的时间。
预排序方法（pre-sorted）：首先，空间消耗大。这样的算法需要保存数据的特征值，还保存了特征排序的结果（例如排序后的索引，为了后续快速的计算分割点），这里需要消耗训练数据两倍的内存。其次时间上也有较大的开销，在遍历每一个分割点的时候，都需要进行分裂增益的计算，消耗的代价大。
对cache优化不友好。在预排序后，特征对梯度的访问是一种随机访问，并且不同的特征访问的顺序不一样，无法对cache进行优化。同时，在每一层长树的时候，需要随机访问一个行索引到叶子索引的数组，并且不同特征访问的顺序也不一样，也会造成较大的cache miss。
lightGBM特点
以上与其说是xgboost的不足，倒不如说是lightGBM作者们构建新算法时着重瞄准的点。解决了什么问题，那么原来模型没解决就成了原模型的缺点。
概括来说，lightGBM主要有以下特点：


基于Histogram的决策树算法


带深度限制的Leaf-wise的叶子生长策略


直方图做差加速


直接支持类别特征(Categorical Feature)


Cache命中率优化


基于直方图的稀疏特征优化


多线程优化


前2个特点使我们尤为关注的。
Histogram算法
直方图算法的基本思想：先把连续的浮点特征值离散化成k个整数，同时构造一个宽度为k的直方图。遍历数据时，根据离散化后的值作为索引在直方图中累积统计量，当遍历一次数据后，直方图累积了需要的统计量，然后根据直方图的离散值，遍历寻找最优的分割点。
带深度限制的Leaf-wise的叶子生长策略
Level-wise过一次数据可以同时分裂同一层的叶子，容易进行多线程优化，也好控制模型复杂度，不容易过拟合。但实际上Level-wise是一种低效算法，因为它不加区分的对待同一层的叶子，带来了很多没必要的开销，因为实际上很多叶子的分裂增益较低，没必要进行搜索和分裂。
Leaf-wise则是一种更为高效的策略：每次从当前所有叶子中，找到分裂增益最大的一个叶子，然后分裂，如此循环。因此同Level-wise相比，在分裂次数相同的情况下，Leaf-wise可以降低更多的误差，得到更好的精度。
Leaf-wise的缺点：可能会长出比较深的决策树，产生过拟合。因此LightGBM在Leaf-wise之上增加了一个最大深度限制，在保证高效率的同时防止过拟合。
xgboost和lightgbm
决策树算法
XGBoost使用的是pre-sorted算法，能够更精确的找到数据分隔点；

首先，对所有特征按数值进行预排序。
其次，在每次的样本分割时，用O(# data)的代价找到每个特征的最优分割点。
最后，找到最后的特征以及分割点，将数据分裂成左右两个子节点。

优缺点：
这种pre-sorting算法能够准确找到分裂点，但是在空间和时间上有很大的开销。

i. 由于需要对特征进行预排序并且需要保存排序后的索引值（为了后续快速的计算分裂点），因此内存需要训练数据的两倍。
ii. 在遍历每一个分割点的时候，都需要进行分裂增益的计算，消耗的代价大。

LightGBM使用的是histogram算法，占用的内存更低，数据分隔的复杂度更低。
其思想是将连续的浮点特征离散成k个离散值，并构造宽度为k的Histogram。然后遍历训练数据，统计每个离散值在直方图中的累计统计量。在进行特征选择时，只需要根据直方图的离散值，遍历寻找最优的分割点。
Histogram 算法的优缺点：

Histogram算法并不是完美的。由于特征被离散化后，找到的并不是很精确的分割点，所以会对结果产生影响。但在实际的数据集上表明，离散化的分裂点对最终的精度影响并不大，甚至会好一些。原因在于decision tree本身就是一个弱学习器，采用Histogram算法会起到正则化的效果，有效地防止模型的过拟合。
时间上的开销由原来的O(#data * #features)降到O(k * #features)。由于离散化，#bin远小于#data，因此时间上有很大的提升。
Histogram算法还可以进一步加速。一个叶子节点的Histogram可以直接由父节点的Histogram和兄弟节点的Histogram做差得到。一般情况下，构造Histogram需要遍历该叶子上的所有数据，通过该方法，只需要遍历Histogram的k个捅。速度提升了一倍。

决策树生长策略
XGBoost采用的是按层生长level（depth）-wise生长策略，如Figure 1所示，能够同时分裂同一层的叶子，从而进行多线程优化，不容易过拟合；但不加区分的对待同一层的叶子，带来了很多没必要的开销。因为实际上很多叶子的分裂增益较低，没必要进行搜索和分裂。

LightGBM采用leaf-wise生长策略，如Figure 2所示，每次从当前所有叶子中找到分裂增益最大（一般也是数据量最大）的一个叶子，然后分裂，如此循环。因此同Level-wise相比，在分裂次数相同的情况下，Leaf-wise可以降低更多的误差，得到更好的精度。Leaf-wise的缺点是可能会长出比较深的决策树，产生过拟合。因此LightGBM在Leaf-wise之上增加了一个最大深度的限制，在保证高效率的同时防止过拟合。

网络通信优化
XGBoost由于采用pre-sorted算法，通信代价非常大，所以在并行的时候也是采用histogram算法；LightGBM采用的histogram算法通信代价小，通过使用集合通信算法，能够实现并行计算的线性加速。
LightGBM支持类别特征
实际上大多数机器学习工具都无法直接支持类别特征，一般需要把类别特征，转化one-hotting特征，降低了空间和时间的效率。而类别特征的使用是在实践中很常用的。基于这个考虑，LightGBM优化了对类别特征的支持，可以直接输入类别特征，不需要额外的0/1展开。并在决策树算法上增加了类别特征的决策规则。
lightGBM调参
所有的参数含义，参考：http://lightgbm.apachecn.org/cn/latest/Parameters.html
调参过程：
（1）num_leaves
LightGBM使用的是leaf-wise的算法，因此在调节树的复杂程度时，使用的是num_leaves而不是max_depth。
大致换算关系：num_leaves = 2^(max_depth)
（2）样本分布非平衡数据集：可以param[‘is_unbalance’]=’true’
（3）Bagging参数：bagging_fraction+bagging_freq（必须同时设置）、feature_fraction
（4）min_data_in_leaf、min_sum_hessian_in_leaf
sklearn接口形式的LightGBM示例
这里主要以sklearn的使用形式来使用lightgbm算法，包含建模，训练，预测，网格参数优化。
import lightgbm as lgb
import pandas as pd
from sklearn.metrics import mean_squared_error
from sklearn.model_selection import GridSearchCV
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.datasets import  make_classification
# 加载数据
print('Load data...')

iris = load_iris()
data=iris.data
target = iris.target
X_train,X_test,y_train,y_test =train_test_split(data,target,test_size=0.2)

# df_train = pd.read_csv('../regression/regression.train', header=None, sep='\t')
# df_test = pd.read_csv('../regression/regression.test', header=None, sep='\t')
# y_train = df_train[0].values
# y_test = df_test[0].values
# X_train = df_train.drop(0, axis=1).values
# X_test = df_test.drop(0, axis=1).values

print('Start training...')
# 创建模型，训练模型
gbm = lgb.LGBMRegressor(objective='regression',num_leaves=31,learning_rate=0.05,n_estimators=20)
gbm.fit(X_train, y_train,eval_set=[(X_test, y_test)],eval_metric='l1',early_stopping_rounds=5)

print('Start predicting...')
# 测试机预测
y_pred = gbm.predict(X_test, num_iteration=gbm.best_iteration_)
# 模型评估
print('The rmse of prediction is:', mean_squared_error(y_test, y_pred) ** 0.5)

# feature importances
print('Feature importances:', list(gbm.feature_importances_))

# 网格搜索，参数优化
estimator = lgb.LGBMRegressor(num_leaves=31)

param_grid = {
    'learning_rate': [0.01, 0.1, 1],
    'n_estimators': [20, 40]
}

gbm = GridSearchCV(estimator, param_grid)

gbm.fit(X_train, y_train)

print('Best parameters found by grid search are:', gbm.best_params_)


原生形式使用lightgbm
# coding: utf-8
# pylint: disable = invalid-name, C0111
import json
import lightgbm as lgb
import pandas as pd
from sklearn.metrics import mean_squared_error
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.datasets import  make_classification

iris = load_iris()
data=iris.data
target = iris.target
X_train,X_test,y_train,y_test =train_test_split(data,target,test_size=0.2)


# 加载你的数据
# print('Load data...')
# df_train = pd.read_csv('../regression/regression.train', header=None, sep='\t')
# df_test = pd.read_csv('../regression/regression.test', header=None, sep='\t')
#
# y_train = df_train[0].values
# y_test = df_test[0].values
# X_train = df_train.drop(0, axis=1).values
# X_test = df_test.drop(0, axis=1).values

# 创建成lgb特征的数据集格式
lgb_train = lgb.Dataset(X_train, y_train)
lgb_eval = lgb.Dataset(X_test, y_test, reference=lgb_train)

# 将参数写成字典下形式
params = {
    'task': 'train',
    'boosting_type': 'gbdt',  # 设置提升类型
    'objective': 'regression', # 目标函数
    'metric': {'l2', 'auc'},  # 评估函数
    'num_leaves': 31,   # 叶子节点数
    'learning_rate': 0.05,  # 学习速率
    'feature_fraction': 0.9, # 建树的特征选择比例
    'bagging_fraction': 0.8, # 建树的样本采样比例
    'bagging_freq': 5,  # k 意味着每 k 次迭代执行bagging
    'verbose': 1 # <0 显示致命的, =0 显示错误 (警告), >0 显示信息
}

print('Start training...')
# 训练 cv and train
gbm = lgb.train(params,lgb_train,num_boost_round=20,valid_sets=lgb_eval,early_stopping_rounds=5)

print('Save model...')
# 保存模型到文件
gbm.save_model('model.txt')

print('Start predicting...')
# 预测数据集
y_pred = gbm.predict(X_test, num_iteration=gbm.best_iteration)
# 评估模型
print('The rmse of prediction is:', mean_squared_error(y_test, y_pred) ** 0.5)