# 机器学习大作业
**Repository Path**: lyk_dugu/machine-learning-homework
## Basic Information
- **Project Name**: 机器学习大作业
- **Description**: 题目来源：https://kelvins.esa.int/collision-avoidance-challenge/data/
建立回归模型预测碰撞几率risk
- **Primary Language**: Python
- **License**: MulanPSL-2.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No
## Statistics
- **Stars**: 5
- **Forks**: 1
- **Created**: 2021-05-04
- **Last Updated**: 2024-12-19
## Categories & Tags
**Categories**: Uncategorized
**Tags**: None
## README
# 机器学习大作业
## 背景介绍
众所周知，随着空间碎片数量的增加，空间占用区域的不断增长，空间人造物体（如卫星等）之间碰撞的风险正在增加。更糟糕的是，轨道上的物体之间的一些碰撞可能会引发连锁反应，可能会彻底污染轨道，使其无法进入，这种情况被称为凯斯勒现象(Kessler syndrome)[1](#refer-anchor-1)。除非开发出适当的技术来处理这个问题，否则这将严重危及在地球科学应用中日益重要的卫星基础设施。事实上，除了作为空间科学、导航和电信的基础，卫星如今在气候科学、地球观测、灾害探测以及海洋、冰、地下水和陆地监测等广泛的地球科学相关应用中也起到核心作用。与此同时，航天机构、私人运营商和研究人员社区一直在研究解决这一问题的方法。当前的避碰策略是从一系列关联数据消息(CDMs)与潜在碰撞事件中评估其碰撞风险。[2](#refer-anchor-2)
在这项工作中，我们针对预测轨道碰撞几率问题，建立了诸如随机森林、XGBoost、深度森林等多种模型进行探讨。本次实验采用的数据来源是https://kelvins.esa.int/collision-avoidance-challenge/data/ 。实证表明，XGBoost方法针对此问题适用性最好，同时，我们仍在不断尝试进行下一步改进...
## 研究现状
自大约15年以来，ESA的空间碎片办公室提供服务来支持操作性避碰活动。目前，这项支持涵盖了ESA的Cryosat-2，Sentinel-1A / B，Sentinel-2A / B，Sentinel-3A任务以及低地球轨道的Swarm-A / B / C星座和高偏心轨道的Cluster-II星座接近GEO地区。这项支持服务向所有感兴趣的第三方开放，并且今天已经向第三方客户提供了6年的支持。鉴于过去十年中发生的严重碎片事件，例如2007年摧毁的Fengyun-1C，2009年发生了Iridium-33 / Cosmos-2251碰撞以及2012年的Briz-M爆炸，造成了数量非常庞大的碎片群，对于所有执行飞行任务的操作员来说，都需要将避免碰撞作为日常操作的一部分，并且从减少空间碎片的角度来看，这也应被视为一种良好做法。 在ERS-2和Envisat航天器上开始了ESA的作战联合分析和避免碰撞活动，如今，他们专注于ESA的Earth Explorer任务，哥白尼的LEO哨兵航天器以及第三方客户，其中包括五个卫星星座RapidEye，由Planet运营。
## 模型介绍
### 随机森林模型
随机森林（Random Forest）是一种基于分类树（classification tree）的算法（Breiman，2001）[3](#refer-anchor-3)。2001年Breiman和Cutler借鉴贝尔实验室的Ho所提出的随机决策森林（random decision forests）（Ho，1995，1998）[4,5](#refer-anchor-4,#refer-anchor-5)的方法，把分类树组合成随机森林，即在变量（列）的使用和数据（行）的使用上进行随机化，生成很多分类树，再汇总分类树的结果。随机森林在运算量没有显著提高的前提下提高了预测精度。同时，该方法对多元共线性不敏感，结果对缺失数据和非平衡的数据比较稳健，可以很好地预测多达几千个解释变量的作用，被誉为当前最好的算法之一（Iverson et al.，2008）[6](#refer-anchor-6)。在机器学习的诸多算法中，随机森林因高效而准确而备受关注，在各行各业得到越来越多的应用（e.g Cutler et al.，2007[7](#refer-anchor-7)；Genueret al.，2010）。
该模型是建立在决策树模型和Bagging算法的基础上发展而来的。它具有两重随机性：
- 数据的随机选取。首先，从原始的数据集中釆取有放回的抽样，构造子数据集，子数据集的数据量是和原始数据集相同的。不同子数据集的元素可以重复，同一个子数据集中的元素也可以重复。第二，利用子数据集来构建子决策树，将这个数据放到每个子决策树中，每个子决策树输出一个结果。最后，如果有了新的数据需要通过随机森林得到分类结果，就可以通过对子决策树的判断结果的投票，得到随机森林的输出结果。
- 待选特征的随机选取。与数据集的随机选取类似，随机森林中的子树的每一个分裂过程并未用到所有的待选特征，而是从所有的待选特征中随机选取一定的特征，之后再在随杋选取的特征中选取最优的特征。这样能够使得随机森林中的决策树都能够彼此不同，提升系统的多样性，从而提升分类性能。
随机森林的生成过程分以下4步：
1. Bagging过程：假设训练集中有N个样本，利用bootstrap方法有放回地随机抽取n个样本，作为一棵决策树的训练样本
2. 分裂属性选择过程：假设特征向量是m维，选取m1维作为子集指定给每个节点，从m1中选择分类效果最佳的一维特征作为接点的分类属性，且保证在随机森林的生长过程中m1保持不变
3. 决策树的生长过程：当每个节点的分类纯度达到期望比例或者生长层数达到给定值时，则停止决策树的生长，保证每个决策树都保证最大限度的生长，且没有剪枝情况。
4. 生成随机森林过程：重复step1-Step3，生长出多颗决策树，从而生成森林,通过对子决策树的判断结果的投票，得到随机森林的输出结果。
在建模过程中，该模型具有两个非常重要的自定义参数：分类树的数量（k）和分割节点的随机变量的数量（m）。通常可以对这些参数进行优化，以使数据处理过程中错误岀现的次数最小。随机森林模型可以通过有放回抽样以及不同树演化过程中随机改变预测变量组合来增加分类树的多样性。正如以上流程环节所示，每一个分类树可以通过原始数据集中的一个自助法取样子集进行生长，并且利用随机选择的m个预测变量中的最佳预测变量进行节点分割。这种分类方法与标准的分类树方法（如：分类回归树）有一点不同，即并没有以整个预测变量中最好的分割变量进行节点分割。
同时，在在生成每棵树的过程中，用bootstrap方法获得的训练集相比原始数据而言，只有63%的数据被重复抽取，而有37%的数据从未出现，这部分数据就叫做袋外数据(out of bag，OOB)。可以用OOB来检验每棵树分类效果的好坏，最终得到的误差值就为袋外误差(out of bag error)。OOB估计是RF算法的一个无偏估计，可以替代数据集交叉验证法，以避免过高的时间空间复杂度，故一般用于分类器泛化能力的衡量，这正是随机森林的一个重要优点。
### XGBoost模型
极端梯度提升树（eXtreme Gradient Boosting，xgboost），是2015年由陈天奇博士提出的一种规模较大的算法[8](#refer-anchor-8)，它在Gradient Boosting框架下既实现了提升决策树（GBDT），又实现了一些广义的线性机器学习算法。 XGBoost支持多种基分类器，当使用树作为基分类器时，它在GBDT的基础上做了一些改进，对每棵树进行了预剪枝；与传统GBDT只用损失函数的一阶导数信息进行优化相比， XGBoost对损失函数进行了二阶泰勒展开，同时用到了一、二阶导数信息，相当于使用牛顿法优化损失函数；XGBooSt在损失函数里引入了正则项，提升了单棵树的泛化能力； XGBooSt能够自动利用CPU的多线程进行并行，提高了运行速率，同时在算法上加以改进提高了精度，相同条件下， XGBoost算法的运行处理速度相对其它一些算法要快很多。目前， XGBooSt已经被越来越多的参赛者运用于各种AI竞赛项目中，受到了越来越多的欢迎和喜爱。
构建XGBoost模型时，需要根据目标函数最小化的原则寻找最优参数，以建立最优模型。XGBoost模型的目标函数可分为误差函数项L和模型复杂度函数项$\Omega$。目标函数可写为:
$$obj=\sum_{i=1}^{N} L\left(y_{i}, \widehat{y}_{l}\right)+\sum_{m=1}^{M} \Omega\left(f_{m}\right) $$
$$\Omega\left(f_{m}\right)=\gamma J+\frac{1}{2} \lambda\|\omega\|^{2} $$
$\Omega$为正则惩罚项函数，$\widehat{y}_{l}$为模型的预测值。我们依然设进行M次迭代，也就是产生M棵树。$f_m$第$m$棵树模型，就是第m个基学习器。在$\Omega(f_m)$表达式中，$J$表示每棵树的叶子结点数，$\omega$表示该决策树叶子结点的权重和，$y$和$\lambda$表示惩罚系数。XGBoost算法的具体流程为：
1. 初始化基学习器为$f_0(x)$。
2. 对$m=1，…，M$，计算损失函数的一阶导数和二阶导数：
$$g_{i}=\frac{\partial L\left(y_{i}, f_{m-1}\left(x_{i}\right)\right)}{\partial f_{m-1}\left(x_{i}\right)} $$
$$h_{i}=\frac{\partial^{2} L\left(y_{i}, f_{m-1}\left(x_{i}\right)\right)}{\partial f_{m-1}\left(x_{i}\right)} $$
这时我们得到决策树的目标函数为：
$$obj^{(m)}=\sum_{i=1}^{N}\left[g_{i} f_{m}\left(x_{i}\right)+\frac{1}{2} h_{i} f_{m}^{2}\left(x_{i}\right)\right]+\Omega\left(f_{m}\right)$$
3. 样本遍历转为叶结点遍历，损失函数为：
$$obj^{(m)}=\sum_{\mathrm{j}=1}^{J}\left[\left(\sum_{i \in I_{j}} g_{i}\right) w_{j}+\frac{1}{2}\left(\sum_{i \in I_{j}} h_{i}+\lambda\right) w_{j}^{2}\right]+\gamma J$$
其中，$I_j$表示第j个叶结点的样本集合。
4. 拟合数据生成基学习器$h_m$；最佳拟合值就是使目标损失函数最小。拟合的过程就是决策树结点分裂的过程，也就是选择属性进行划分。分类问题可利用基尼指数来进行属性选择，回归树可用平方误差选择划分的属性。于是我们就可以得到各叶结点最优的权重值以及目标函数值为：
$$w_{j}^{*}=-\frac{G_{i}}{H_{i}+\lambda} $$
$$obj=-\frac{1}{2} \sum_{j=1}^{J} \frac{G_{i}}{H_{i}+\lambda}+\gamma J$$
其中，$G_{i}=\sum_{i \in I_{j}} g_{i}, H_{i}=\sum_{i \in I_{j}} h_{i}$
5. 更新预测模型:$$f_m(x)=f_{m-1}(x)+h_m(x)$$
直到达到我们设定的收敛条件，或者迭代次数达到M次，停止算法，得到最终的预测模型。
XGBoost有很多优点：
- 使用二阶泰勒展开式对目标函数做近似展开，使得求最优解时候变得简单。
- 可以处理稀疏、缺失数据。
- 生成决策树时候使用结构分数进行生长。
- 分裂结点使用候选集合，使得算法的运行速度快。
- 定义了树的复杂度，并应用到目标函数中，可以把握模型的复杂度。
- 在目标函数中加入正则项，同时借鉴了随机森林算法，采用特征列采样的方法，避免过拟合现象的出现。
### 深度森林模型
多粒度级联森林（multi- Grained Cascade forest, GCForest）是2017年南京大学的周志华教授和冯霁博士提出的一种基于随机森林的集成方法[9](#refer-anchor-9)，也是种深度学习模型，周志华教授也将其称作深度森林（Deep Forest）。随机森林是深度森林算法的组成单元，可以说深度森林算法有着随机森林髙效准确和可拓展的优点，在网络结构上又和深度神经网络很相似，具有深度模型逐层加工，特征转换，和结构复杂的特征。更重要的是，同样作为深度模型，深度森林和深度神经网络相比超参数的数量较少，而且对超参数的依赖性也更低，因此深度森林的训练更为便捷，理论分析也更为清晰。该算法不仅可以增强输入特征的差异性，还可以提高输入特征的分类能力。
受到深度神经网络的启发，深度森林采用级联结构，每个级联由多个级别组成，每个级别对应于一个扫描粒度，即不同的滑动窗口长度对应不同的扫描粒度。其中每级级联接收由其前一级联处理的特征信息，并将其处理结果输出到下一级联。和多粒度扫描一样，级联结构中也包括不同类型的森林以鼓励多样性。值得注意的是，为了避免模型过拟合，每个森林得到的类向量前，需要用K折交叉验证进行处理。在扩展新级别后，需要在验证集上估计整个级联的性能，若该级联没有使模型具有显着的性能增益，训练过程随即终止。由此可以看出，与模型的复杂性固定的大多数深度神经网络相反，级联的数量是在模型训练中自动确定的。对模型复杂度的自适应调节使得深度森林可以应用在不同规模训练数据集上，完美地避免了深度神经网络在少量数据集上不能得到很好应用的困境。
其算法流程如下所示:
___
**深度森林算法**
输入：数据集D
输出：深度森林模型
1. 初始化$D_0=D$；
2. 用$D_i(i=0,1,2,3，…)$训练得到2个随机森林与2个完全随机森林，将它们组合在一起形成深度森林的第i层；
3. 对第i层的每个森林输出一个二维类向量$X$，将其叠加求均值，记为$\bar{X}$，令第i层的输出类别为$argmax \bar{X}$；
4. 在当前模型上用验证集进行预测，得到准确率$\theta_i$，当$\theta_i-\theta_{i-1}<0，(i>1)$时，输岀深度森林模型并终止；
5. 对第i层的每个森林输出二维类向量$X$，并与$D_0$中的特征进行拼接，得到新的$D_{i+1}$；跳转至步骤2。
___
由深度森林结构图和算法可知,深度森林每层使用了不同种类的森林,提高了模型的容错率。在深度森林中，下一层输入是上一层特征的强化,并且每层都与原始特征进行拼接,因此避免了信息丢失。从深度森林的整体模型训练过程，体现出了端到端的结构，且没有BP神经网络微调阶段，利用自适应机制的思想适宜地调节模型复杂度，十分适用于不同规模数据集的任务。
## 数据清洗
通过对于数据集的观察和统计可以发现，其数量非常庞大且有很多标签对应的数据出现大量缺失，其中c_rcs_estimate缺失五万多条数据，占比32.49%，所以在训练中抛弃该标签对应数据，其余最多缺失九千多条，使用取众数的方法进行补齐。另外，我们还进行了如下操作：
- 对于所有数值类数据采用zscore方法进行标准化。这里，随机森林实际不需要标准化操作，但是为统一起见，将数据进行标准化后再分别作为各个模型的输入。
- 对于标签类数据进行one-hot编码处理。
- 对于event_id我们认为对预测其结果无益处，直接抛弃处理。
- 用留出法对数据集按4:1比例随机划分训练集和测试集，经过50次测试取平均。
## 训练结果
对于训练结果我们使用50次随机留空法取平均MSE进行评估。我们所有模型的结果如下：
| **模型** | **随机森林100棵树** | **随机森林200棵树** | **XGBoost100个预测器** | **XGBoost800个预测器** | **深度森林** | **BP神经网络** |
| :------: | :-----------------: | :-----------------: | :--------------------: | :--------------------: | :----------: | :------------: |
| **MSE** | **0.0121** | **0.0119** | **0.0109** | **0.0071** | **0.0848** | **17.8397** |
> 注：xgboost运行结果受计算机环境与性能影响，在我们组员的电脑上的最好结果为0.0109与0.0071。
对于深度森林，其可调参数太少，而且其对参数不敏感，结果相对较差，我们不再对其进行探究。同时对于BP神经网络，其MSE太差，我们也不再对其进行优化。
### 随机森林
我们分别使用100棵以及200棵的随机森林模型，耗时相对较短，经过50次随机留出法取样得到，两者的MSE均约在0.012左右，标准差为0.0013，总体效果较好。
### XGBoost
我们使用了100个和800个预测器的XGBoost模型，对于100个预测器50次随机留出法取样的MSE稳定为0.01096，标准差为0.00068，耗时非常短，而对于800个预测器的结果大概稳定在MSE=0.007左右，效果极好，但耗时较长于100个预测器的模型，其收益不大，故放弃。其中100个预测器的XGBoost模型最后的训练曲线如下所示。
通过导出下图中的标签权重，可以发现对于模型预测结果影响最大的标签为max_risk_sacaling和max_risk_estimate，而其他标签总体影响都过小，说明我们的模型虽然总体效果较好，但对于标签的利用率不大，此处还有待改进。
## 优化展望
在我们所有的模型中只对于每个数据进行单独训练，没有考虑其同一event_id内的关联，也就是时间序列关系，其原因是因为我们所使用的xgboost封装度过高难以改进，基于这一想法，我们组提出了一个通过添加标签来优化训练模型的想法，我们创建last_risk标签，也就是同一event_id内上一时刻的risk，尝试以此迭代优化模型，其思想近似于循环神经网络。其结果相对于原xgboost结果较差，其mse稳定在0.07左右，结合下图其权重图，我们认为其关于last_risk可能出现了过拟合的情况，我们希望在接下来的优化中能够解决这一问题。
## 任务分工
- lyk：进行数据清洗，建立多种模型进行预测并撰写论文。
- cxy：进行论文撰写，并对模型进行优化。
## 参考文献
- [1]Kessler D J, Cour‐Palais B G. Collision frequency of artificial satellites: The creation of a debris belt[J]. Journal of Geophysical Research: Space Physics, 1978, 83(A6): 2637-2646.
- [2]Krag H, Flohrer T, Merz K, et al. ESA’s modernised collision avoidance service[C]//14th International Conference on Space Operations. 2016: 2449.
- [3]Breiman L. Random forests[J]. Machine learning, 2001, 45(1): 5-32.
- [4]Ho T K. The random subspace method for constructing decision forests[J]. IEEE transactions on pattern analysis and machine intelligence, 1998, 20(8): 832-844.
- [5]Ho T K. A data complexity analysis of comparative advantages of decision forest constructors[J]. Pattern Analysis & Applications, 2002, 5(2): 102-112.
- [6]Iverson L R, Prasad A M, Matthews S N, et al. Estimating potential habitat for 134 eastern US tree species under six climate scenarios[J]. Forest ecology and management, 2008, 254(3): 390-406.
- [7]Cutler D R, Edwards Jr T C, Beard K H, et al. Random forests for classification in ecology[J]. Ecology, 2007, 88(11): 2783-2792.
- [8]Chen T, Guestrin C. Xgboost: A scalable tree boosting system[C]//Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining. 2016: 785-794.
- [9]Zhou Z H, Feng J. Deep forest[J]. arXiv preprint arXiv:1702.08835, 2017.