数据挖掘的方法有哪些?并简述,数据挖掘的四种基本方法
微信官方账号后台回复“书”了解更多主书和新书内容。作者：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挑出哔哩哔哩那些“厉害”的老奶奶！你认为去哔哩哔哩旅游可以学习编程吗？
