type
status
date
slug
summary
tags
category
icon
password
Property
集成学习概述
集成学习的思想：对于训练集数据，通过训练若干个个体学习器，通过一定的结合策略，就可以最终形成一个强学习器，以达到博采众长的目的。
集成学习有两个主要的问题：第一是如何得到若干个个体学习器，第二是如何选择一种结合策略，将这些个体学习器集合成一个强学习器。
集成学习之个体学习器
如何得到若干个个体学习器，这里有两种选择：
- 第一种就是所有的个体学习器都是一个种类的，或者说是同质的，比如都是决策树个体学习器，或者都是神经网络个体学习器。
- 第二种是所有的个体学习器不全是一个种类的，或者说是异质的。比如一个分类问题，对训练集采用支持向量机个体学习器，逻辑回归个体学习器和朴素贝叶斯个体学习器来学习，再通过某种结合策略来确定最终的分类强学习器。
目前来说，同质个体学习器的应用是最广泛的，一般常说的集成学习的方法都是指的同质个体学习器。而同质个体学习器使用最多的模型是CART决策树和神经网络。同质个体学习器按照个体学习器之间是否存在依赖关系可以分为两类：
- 第一个是个体学习器之间存在强依赖关系，一系列个体学习器基本都需要串行生成，代表算法是boosting系列算法
type
status
date
slug
summary
tags
category
icon
password
Property
原理
GBDT概述
GBDT也是集成学习Boosting家族的成员，但是却和传统的Adaboost有很大的不同。Adaboost利用前一轮迭代弱学习器的误差率来更新训练集的权重，这样一轮轮的迭代下去。GBDT也是迭代，使用了前向分布算法，但弱学习器限定了只能使用CART回归树模型，同时迭代思路和Adaboost也有所不同。无论是GBDT分类树还是GBDT回归树，底层使用的都是CART回归树，并没有使用CART分类树。
在GBDT的迭代中，假设前一轮迭代得到的强学习器是，损失函数是，本轮迭代的目标是找到一个CART回归树模型的弱学习器，让本轮的损失函数最小。也就是说，本轮迭代找到决策树，要让样本的损失尽量变得更小。
GBDT的思想可以用一个通俗的例子解释：假如有个人30岁，首先用20岁去拟合，发现损失有10岁，这时用6岁去拟合剩下的损失，发现差距还有4岁，第三轮用3岁拟合剩下的差距，差距就只有一岁了。如果迭代轮数还没有完，可以继续迭代下面，每一轮迭代，拟合的岁数误差都会减小。
从例子看这个思想还是蛮简单的，但是有个问题是这个损失的拟合不好度量，损失函数各种各样，怎么找到一种通用的拟合方法呢？
GBDT的负梯度拟合
针对这个问题，大牛Freidman提出了用损失函数的负梯度来拟合本轮损失的近似值，进而拟合一个CART回归树。第轮的第个样本的损失函数的负梯度表示为
代码
type
status
date
slug
summary
tags
category
icon
password
Property
原理
从GBDT到XGBoost
作为GBDT的高效实现，XGBoost是一个上限特别高的算法，因此在算法竞赛中比较受欢迎。简单来说，对比原算法GBDT，XGBoost主要从下面三个方面做了优化：
- 一是算法本身的优化：在算法的弱学习器模型选择上，对比GBDT只支持决策树，还可以直接很多其他的弱学习器。在算法的损失函数上，除了本身的损失，还加上了正则化部分。在算法的优化方式上，GBDT的损失函数只对误差部分做负梯度（一阶泰勒）展开，而XGBoost损失函数对误差部分做二阶泰勒展开，更加准确。算法本身的优化是重点也是难点
- 二是算法运行效率的优化：对每个弱学习器，比如决策树建立的过程做并行选择，找到合适的子树分裂特征和特征值。在并行选择之前，先对所有的特征的值进行排序分组，方便前面说的并行选择。对分组的特征，选择合适的分组大小，使用CPU缓存进行读取加速。将各个分组保存到多个硬盘以提高IO速度
- 三是算法健壮性的优化：对于缺失值的特征，通过枚举所有缺失值在当前节点是进入左子树还是右子树来决定缺失值的处理方式。算法本身加入了L1和L2正则化项，可以防止过拟合，泛化能力更强
XGBoost损失函数
在看XGBoost本身的优化内容前，先回顾下GBDT的回归算法迭代的流程，对于GBDT的第颗决策树，主要是走下面4步：
代码
type
status
date
slug
summary
tags
category
icon
password
Property
LightGBM
microsoft • Updated Dec 27, 2023
LightGBM （Light Gradient Boosting Machine）是一个实现GBDT算法的框架，支持高效率的并行训练。
LightGBM在Higgs数据集上LightGBM比XGBoost快将近10倍，内存占用率大约为XGBoost的1/6，并且准确率也有提升。GBDT在每一次迭代的时候，都需要遍历整个训练数据多次。如果把整个训练数据装进内存则会限制训练数据的大小；如果不装进内存，反复地读写训练数据又会消耗非常大的时间。尤其面对工业级海量的数据，普通的GBDT算法是不能满足其需求的。
LightGBM提出的主要原因就是为了解决GBDT在海量数据遇到的问题，让GBDT可以更好更快地用于工业实践。
LightGBM在哪些地方进行了优化 (区别XGBoost)？
- 基于Histogram的决策树算法
- 带深度限制的Leaf-wise的叶子生长策略
- 直方图做差加速直接
type
status
date
slug
summary
tags
category
icon
password
Property
原理
bagging的原理
从上图可以看出，Bagging的弱学习器之间的确没有boosting那样的联系。它的特点在“随机采样”。那么什么是随机采样？
随机采样(bootsrap)就是从训练集里面采集固定个数的样本，但是每采集一个样本后，都将样本放回。也就是说，之前采集到的样本在放回后有可能继续被采集到。对于Bagging算法，一般会随机采集和训练集样本数一样个数的样本。这样得到的采样集和训练集样本的个数相同，但是样本内容不同。如果我们对有 个样本训练集做次的随机采样，则由于随机性， 个采样集各不相同。
注：这和GBDT的子采样是不同的。GBDT的子采样是无放回采样，而Bagging的子采样是放回采样。bootstap的目的是减少样本的方差（当然也有可能增加偏倚），重采后的分布比样本表现出的分布对于真实分布而言更稳定， 从而得到防止过拟合的目的。子采样的分布改变了原样本数据集的分布，准确说是更好的模拟了样本数据分布背后的真实分布。
代码
type
status
date
slug
summary
tags
category
icon
password
Property
层次聚类hierarchical clustering (hierarchical cluster analysis or HCA )
层次聚类可以划分为两类：
- agglomerative Hierarchical clustering(AHC)自底向上，这里主要写的是这种方法
- divisive Hierarchical clustering 自顶向下，一开始所有数据为一类，每次把一个类分开，因为把类分开算法较为复杂，所以这种方法关注度不高，
step1：先让各个样本各自成一类，
step2：距离最近的两类合并成一个新类
step3：反复执行step2
step4：根据需要，或根据距离临界值（阈值）确定分类数和分类结果
type
status
date
slug
summary
tags
category
icon
password
Property
高斯混合模型（Gaussian Mixed Model，GMM）也是一种常见的聚类算法，与K均值算法类似，同样使用了EM算法进行迭代计算。高斯混合模型假设每个簇的数据都是符合高斯分布（正态分布）的，当前数据呈现的分布就是各个簇的高斯分布叠加在一起的结果。
第一张图是一个数据分布的样例，如果只用一个高斯分布来拟合图中的数据，图中所示的椭圆即为高斯分布的二倍标准差所对应的椭圆。直观来说，图中的数据明显分为两簇，因此只用一个高斯分布来拟和是不太合理的，需要推广到用多个高斯分布的叠加来对数据进行拟合。第二张图是用两个高斯分布的叠加来拟合得到的结果。这就引出了高斯混合模型，即用多个高斯分布函数的线形组合来对数据分布进行拟合。理论上，高斯混合模型可以拟合出任意类型的分布。
高斯混合模型的核心思想是，假设数据可以看作从多个高斯分布中生成出来 的。在该假设下，每个单独的分模型都是标准高斯模型，其均值 和方差 是待估计的参数。此外，每个分模型都还有一个参数 ，可以理解为权重或生成数据的概率。高斯混合模型的公式为：
通常并不能直接得到高斯混合模型的参数，而是观察到了一系列数据点，给出一个类别的数量K后，希望求得最佳的K个高斯分模型。因此，高斯混合模型的计算，便成了最佳的均值，方差、权重的寻找，这类问题通常通过 最大似然估计来求解。遗憾的是，此问题中直接使用最大似然估计，得到的是一 个复杂的非凸函数，目标函数是和的对数，难以展开和对其求偏导。
type
status
date
slug
summary
tags
category
icon
password
Property
原理
BIRCH概述
BIRCH的全称是利用层次方法的平衡迭代规约和聚类（Balanced Iterative Reducing and Clustering Using Hierarchies）。BIRCH只需要单遍扫描数据集就能进行聚类，那它是怎么做到的呢？
BIRCH算法利用了一个树结构来帮助我们快速的聚类，这个数结构类似于平衡B+树，一般将它称之为聚类特征树(Clustering Feature Tree，CF Tree)。这颗树的每一个节点是由若干个聚类特征(Clustering Feature，CF)组成。从下图可以看看聚类特征树是什么样子的：每个节点包括叶子节点都有若干个CF，而内部节点的CF有指向孩子节点的指针，所有的叶子节点用一个双向链表链接起来。
聚类特征CF与聚类特征树CF Tree
在聚类特征树中，一个聚类特征CF是这样定义的：每一个CF是一个三元组，可以用（N，LS，SS）表示。其中N代表了这个CF中拥有的样本点的数量；LS代表了这个CF中拥有的样本点各特征维度的和向量，SS代表了这个CF中拥有的样本点各特征维度的平方和。
如下图，在CF Tree中的某一个节点的某一个CF中，有下面5个样本。则它对应的N=5， LS=, SS =
