数据挖掘的方法有哪些-并简述,数据挖掘的四种基本方法

  数据挖掘的方法有哪些?并简述,数据挖掘的四种基本方法

  微信官方账号后台回复“书”了解更多主书和新书内容。作者:luanhz

  来源:十进制记录

  指导阅读

  从事数据挖掘的人一定知道XGBoost算法,这个曾经在数据挖掘大赛中大放异彩的生成神器。是2016年暖月神提出的经典算法。本质上,XGBoost被看作是GBDT算法的优化实现,但除了继承了集成算法的概念外,具体的设计细节其实差别很大。最近深入学习,简单探索底层设计的数据结构,不禁感慨算法的精妙!做个总结,从中吸取教训!

  2016年,暖月受邀参加了关于XGBoost的分享会。

  XGBoost是机器学习中的一种集成算法,分为三个集成学派,属于Boosting学派。Boosting学派也是集成算法中最活跃、最强大的学派。除了XGBoost,Adaboost和GBDT都在前面,后面是LightGBM和CatBoost。当然,LightGBM、CatBoost和XGBoost一般被认为是GBDT的改进和优化实现。

  其实XGBoost算法的原理已经非常成熟和完备,网上有无数这方面的分享。因此,本文不想重复前面的工作,而是着眼于以下目的:一、从讲解公式的角度分享我个人对XGBoost算法原理的理解;第二,简单探讨一下XGBoost的数据结构设计。后者类似于之前推文《数据科学:Sklearn中的决策树,底层是如何设计和存储的?》的定位。

  01学习公式推导,理解原理

  为了理解XGBoost的算法原理,下面主要分享与该算法相关的五个主要公式的推导过程。所有公式主要来源于XGBoost官方文档(https://XGBoost . readthedocs . io/en/latest),也可以通过查阅相关论文找到。

  公式1——Boosting集成算法的加法模型:

  公式很简单,但是理解下面的公式很重要。作为Boosting算法,XGBoost的集成思想遵循的是典型的加法模型,即集成算法的输出等于基础学习者的输出之和(回归问题通过求和很好理解,在对问题进行分类时,实际上是拟合logloss,这类似于后面提到的logistic回归中的做法)。上式中,fk(x)代表单个基础学习者,K代表基础学习者的数量。以下图中有两个基础学习者的整合模型为例。‘儿子’的整合模型输出是两个基础学习者各自输出之和,即20.9=2.9;爷爷的综合模型输出是两个基础学习者的输出之和,即-1-0.9=-1.9。

  公式2——XGBoost中基学习器的目标函数

  机器学习有三个要素:模型、策略和算法。策略包括如何定义或评估模型,换句话说,它涉及定义损失函数。与GBDT的连续拟合残差不同,XGBoost增加了模型的结构损失,可以理解为模型学习的代价;残差对应的是经验损失,可以理解为模型学习能力的差距和不足。

  在上面的目标函数中(目标函数是比损失函数更高级的一项,一般包括两部分:目标函数=损失正则项,越小越好。除了目标函数和损失函数,还有一个相关的术语叫做成本函数。在某种意义上,成本函数可以近似理解为损失函数。),求和的第一部分定义了当前模型训练结果与真实值的差异,称为经验风险。具体的测量方法取决于相应损失函数的定义。典型的损失函数有:回归问题对应MSE损失,分类问题对应logloss损失损失;求和的第二部分反映了模型的结构风险,影响了模型的泛化能力。如果基础学习者选择决策树,那么这里的结构风险定义为:

  其中和都是正则项系数,t是决策树中的叶节点数。请注意,这是叶节点的数量,而不是决策树中的节点数量(当在CCP之后修剪CART决策树时,使用的常规术语是计算所有节点的数量)。另外,这是一般介绍XGBoost原理时的公式,在最早的《暖月》论文中也有写。在Python的xgboost工具包中,除了这两个参数对应的gamma和reg_lambda,还有reg_alpha参数,代表一阶正则项。这时,你可以写:

  公式3——XGBoost中的Taylor二阶展开近似值

  理解:这种泰勒二阶展开近似可谓是XGBoost的灵魂,也是与GBDT相比最能体现其羞涩的墨镜和力量。为了更好地解释上述近似,首先给出一般意义下的泰勒展开式:

  当然,上面的公式只是扩展到二阶近似,只要f(x)是无限可导的,就可以有更高阶的近似。在XGBoost中,泰勒二阶展开近似的应用实际上只针对模型的经验风险部分,即公式2中第一部分之和的各个子项。这里,再次给出一个表达式:

  上式中,下标I对应训练集中的第I个样本,集成算法中的T和t-1轮对应上角标记T和t-1。那么,F,X和x是谁?这里F是函数标记,对应损失函数中的L。理解X和 X很重要。

  模型训练时,训练数据集其实是确定的,在每个基础学习者中是一组固定的值,所以yi也不例外,在上面的公式中可以看作一个常数。在集成模型训练的t轮中,此时模型训练的目的是基于上一轮t-1轮(此时已经确定)的训练结果,寻找最佳的t轮结果,从而得到当前可能的最小损失。

  实际上,在集成学习中,第一个基本学习者已经能够拟合大部分结果。比如在通常的拟合年龄的例子中,假设要拟合的结果是100,那么很可能第一个基础学习者的拟合结果是90,而后面的N-1个学习者只是在不断地修正残差:10。这个例子的目的是想表达在上面的公式中,第t-1轮的拟合结果y_hat实际上对应的是f中的x(xx),而第t轮的拟合值可以看作是一个浮动变量x,此时,按照泰勒展开的风格,上面的目标函数可以具体展开如下:

  其中gi和hi分别是一阶导数和二阶导数,如下所示:

  此外,如果y是真实值,y_hat是拟合值,则最常用的MSE损失应用于回归问题,其损失函数和对应的一阶导数和二阶导数为:

  对于分类问题,以二元分类问题为例,XGBoost中默认的损失函数是logloss,对应的损失函数和对应的一阶、二阶导数是:

  公式4——决策树中的最优叶子权重求解

  XGBoost理论上可以支持任何基础学习者,但实际上决策树是最常用的。Python中的xgboost工具库也默认使用gbtree作为基础学习器。在决策树中,T轮训练得到的最优决策树实际上就是寻求最优叶权的过程,所以理解这个最优叶权就显得尤为重要。

  好在上面两个公式的解法都非常简单易懂,甚至是初中数学知识的范畴,比SVM的拉格朗日对偶问题要容易理解得多。先看下面的转换:

  第一步中的近似等号当然是从公式3中的泰勒二阶展开近似推导出来的,但此时省略了常数部分。需要注意的是,此时的解是基于样本大小的,即I为样本序号,n为样本总数。第二步等号转换,以叶节点为粒度,聚合落在同一叶节点的多个样本。此时落在同一个叶节点上的所有样本的预测结果就是它们的叶权j,每个叶节点内部的和对应于内部的sigma。

  利用叶节点的上述近似展开和收敛,可以导出下面的公式:

  其中Gj和Hj是f的和

  上面的客观公式可以看作是T个一元二次表达式的求和,其中每个一元二次表达式中的变量为 j,显然,用f (x)=ax 2bx c的形式求解最小值问题是初中的数学问题,然后很容易得到最优的j和此时对应的损失函数的最小值。结果是:

  这里一元二次函数一定有最小值,因为它的二次项的系数1/2(Hj )一定是正数!

  公式5——决策树的分裂增益

  公式4解决了叶节点的最优权重问题,所以它实际上绕过了一个前置问题:如何拆分决策树的内部节点?如何拆分内部节点可以进一步细分为两个子问题:

  选择哪个特征进行分割?

  用什么阈值划分左右子树?

  第一个问题很容易解决。最简单且仍在使用的方法是逐个遍历所有特征,比较哪个特征带来最大的增益。

  至于第二个问题,其实也是用遍历优化的方法来获得最优的分裂阈值。至于如何遍历优化,它可以进一步细分为两个问题:

  I)选择哪些候选分裂阈值?

  Ii)如何衡量哪个分裂阈值更好?

  选择哪些候选分裂阈值涉及许多技巧。XGBoost和LightGBM都采用直方图的方法来简化可能的最优分裂点候选。这里涉及的细节还很多,暂且不谈。对于如何度量更好的分裂阈值的问题,我们可以只使用前面公式4的结论——,最优权重下叶节点的最小损失表达式。在此基础上,测量最佳分割阈值的过程如下:

  如果节点没有分裂,即视为叶子节点,可以得到当前的最小损失值;

  对于选定的特征和阈值,将当前节点的所有样本分成左右两个子树,然后可以得到左右两个子树对应的最小损失值。

  那么,从直接作为叶节点的节点分裂成两个子叶节点,损耗会降低吗?所以只要减去拆分前后的损失就行了!那为什么减法后T部分变成了-?其实是因为这部分的正则项在分裂前对应一个叶节点,分裂后对应两个叶节点,所以两部分的相减T是-。

  以上是对XGBoost中几个关键公式的理解。相信了解了这五个公式,就基本可以了解XGBoost是如何设计和实现的了。当然,XGBoost的强大和巧妙设计并不局限于上述算法原理。其实还有很多实用的技巧和优化,也构成了XGBoost的scalable能力。详情请参考论文《XGBoost: A Scalable Tree Boosting System》。

  02检查源代码,了解底层数据结构。

  第一部分主要介绍XGBoost中的核心公式,简单分享一下XGBoost中底层数据结构的设计。之所以增加这部分工作,还是因为近期需要做一些预研工作。因此,本文重点研究XGBoost的底层是如何存储所有的基础学习者,也就是每个决策树的训练结果的。

  为了理解XGBoost如何在训练后存储每个决策树,我们看一下分类器的模型训练部分的源代码。简单看了一下,我们可以找到下面的代码:

  也就是说XGBClassifer模型的训练结果要保存在_Booster属性中。

  当然,在其原生训练方法中,上面提到的xgboost提供的sklearn类型接口实际上是调用xgboost.train函数来实现模型训练的。这时候无论是回归任务还是分类任务都调用这个函数,只是通过不同的目标函数来区分不同的任务类型。

  为了进一步了解this _Booster属性,我们实际上训练了一个XGBoost二进制分类模型,使用了下面的简单代码示例:

  From sklearn.datasets导入load _ iris from XG Boost导入XG BClassifierrx,y=load _ iris(return _ x _ y=true)# Native iris数据集分为三类,它分为两类:x=x[y2]y=y[y2]xgb=xgb classifier(use _ label _ encoder=false)xgb . fit(x,y,eval _ metric= logloss )。然后,通过dir属性检查this _Booster的结果:

  其实this _Booster属性是xgboost中定义的一个类,上面的结果也可以直接从xgboost中Booster类的定义中查看。在上面的dir结果中,有几个函数值得特别注意:

  Save_model:用于将xgboost模型训练结果保存为文件,xgboost非常友好。1.0.0版本以后直接支持json格式存储,比pickle格式方便很多,可读性也大大增强。

  Load_model:有save_model就一定有load_model,这是一个互逆操作,即load_model可以将save_model的json文件结果作为xgboost模型读取。

  Dump_model:其实Dump也有存储的意思。例如,json中定义的读写函数是load和dump。在xgboost中,dump_model和save_model的区别在于,dump_model的存储结果便于人类读取,但过程是单向的,即转储结果无法加载回来;

  Get_dump:类似于dump_model,只不过它不是存储为文件,而是只返回一个字符串;

  Trees_to_dataframe:意思很明确,就是把所有训练后的树信息转换成一个dataframe。

  这里,先看trees_to_dataframe的结果:

  似乎从栏目名称来看,除了最后两个字段Cover和Category,其他字段的含义都很清楚,就不做过多解释了。

  之后探究save_model和dump_model的结果。因为dump_model的结果易于阅读,所以首先检查这个结果:

  这里截取了dump_model之后txt文件中三棵决策树的信息,可以看出dump_model的结果只保留了每棵决策树的拆分信息。以booster[0]中的第一棵决策树为例,该决策树有三个节点,节点的缩进关系表示子节点的对应关系。内部节点标签标识所选择的分裂特征和相应的阈值,但是叶节点后面的值实际上不是它的权重。

  然后,探索save_model的json文件结果,先检查整个json的结构关系:

  其中,树部分是包含100个条目的列表,对应于100个基础学习者的信息。进一步考察发现,它类似于sklearn中定义的基于数组的树表示形式,这里的决策树每个节点的信息仍然是基于数组的,即每个属性的第I个值表示对应的第I个节点的对应属性。主要字段和含义如下:

  值得指出的是,通过比较left_children、right_children和parents的值,很容易推断出xgboost中的决策树节点数是层次遍历,与sklearn中使用的前序遍历不同。

  以上仅给出了xgboost中关于学习者基本信息的一些简单探索。有兴趣的可以进一步尝试,查看相应的源代码设计,希望对理解xgboost的原理有所帮助。

  睫毛的可爱新书已经在当当上架了。我写过一本书:《拿下Offer-数据分析师求职面试指南》。目前当当网正在举办活动。你可以以相当于原价50%的预购价购买。还是很划算的:建立了数据森林微信官方账号的交流群,很多小伙伴都加入了进来。谢谢你的支持。您可以在小组中交流有关数据分析和数据挖掘的信息。没有加入的可以扫描下面管理员的二维码。入群前一定要关注微信官方账号奥数。关注后请管理员帮你加入群。我们期待您的加入。二维码:猜你喜欢卧槽!原来爬哔哩哔哩弹幕这么简单牛逼!可爱的睫毛书在JD.COM名列销售榜首!知乎沙雕问题列表,人不偿命笑死用Python挑出哔哩哔哩那些“厉害”的老奶奶!你认为去哔哩哔哩旅游可以学习编程吗?

郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。

留言与评论(共有 条评论)
   
验证码: