源码：https://github.com/kanyuanzhi/HW_Prediction
这次比赛还是有挺大遗憾的，由于算法中随机部分的影响，导致在大数据量情况下最终结果不稳定，最后一版提交分数远不如最高分，而赛制又是取最后一次的分数，最终未能进入复赛。
本总结技术指导性很低，一是因为比赛的确挺玄学，大部分高分也是通过调参调出来的； 二是自己也并未用到高级的东西，都是常用模型与常见算法，对其理解也仅是些皮毛，其他部分则都是垃圾逻辑代码的堆砌。主要是自己的一些小思考以及后期学习的方向。
忍不住还要吐槽一下，一模一样的代码跑了三个分数出来，而且还是一次比一次低。在最后仅有两次提交机会的时候，决定提交之前最高分数的版本， 提交完毕系统跑分结果出来的一瞬间有点吃惊，因为在练习阶段此代码的的评分从未波动过，但这分数是肯定不会进复赛（前36）的。 跟队友商量后，前64对我们没有任何意义，于是对算法运行时间稍作限制（其他均未有变动）再提交一次，结果彻底崩溃，又降了接近10分…… 就此用完十次机会，将近一个月的辛苦就这样有点莫名其妙的白费了（白费一词可能需要再斟酌一下，毕竟还是有所收获的，而且之前最高分也不一定就能进复赛，而我现在已经不想再看）。
在练习赛阶段的最高名次曾到达赛区（上合）第5。
赛题介绍
本次比赛主要分为两部分，预测+放置，根据历史数据预测下一时间段的虚拟机请求数以及在预测的结果上将虚拟机放置在物理服务器中使得物理服务器的利用率最大。 其他信息可参考官网（http://codecraft.devcloud.huaweicloud.com/home/detail），在此不再赘述。
预测
首先要说明的是这个比赛不允许使用任何第三方库，所以一些开源的机器学习、深度学习的框架是没法使用的，甚至连numpy都不能使用，当然矩阵运算也不是很复杂，但是自己写的速度上肯定比不上numpy。
预测部分是一个典型的时间序列建模预测问题，有很多经典的模型可以使用，比如线性回归、指数平滑、GARCH、ARIMA、回归树，随机森林甚至是GBDT等等， 深度学习中的循环神经网络（LSTM）也是解决序列建模的利器，但手撸LSTM困难还是比较大的，个人也是水平有限。
尝试模型
我们在练习阶段尝试了如下几种方法：线性自适应、BP网络、线性回归、一阶指数平滑和二阶指数平滑，这些都非常简单而且易于实现。对于预测问题，也并不是模型越复杂就越好。 现在回顾整个比赛，觉得最欠缺的还是原始数据处理部分。如果数据处理的好，简单的模型也会取得很好的预测效果，
线性回归、线性自适应相当于在解一个Y=WX+b方程，通过近期数据的线性组合来预测出下一期数据。 这个效果并不是很好，首先是训练集的划分很难平衡X的维度与整体数据量的关系（或者说是方程数与待求变量数的关系），很容易造成解不唯一但都符合训练集的误差要求。
在学习过程中了解过正则化，通过对线性回归加一个正则项，将解集限定在一定范围内来避免过拟合的问题，如岭回归与lasso回归，此处并未深入学习。
BP网络通过加了一层神经元使得其可以逼近任意非线性函数，这也跳出了线性模型的线性限制，但同样存在数据集的划分问题，每次训练后权值都不一样，但对训练集都可以完美拟合。 此外BP网络的训练收敛速度也是一个问题所在。
对于指数平滑，则是一个相当具有普适性的预测方法了。一阶指数平滑主要针对无规律的序列，二阶指数平滑针对有趋势的序列，三阶指数平滑则针对季节性明显的序列。 结合本次比赛，通过对训练集的数据绘图，肉眼并未观察到任何规律所在，甚至怀疑题目是否可以建模预测。实际代码中使用了一阶与二阶指数平滑，一阶对单个时间段内的请求数建模， 二阶对单个时间段内的累积请求数建模。调参上则是手动不断尝试，曾使用过自动调参，通过遍历参数值计算训练集的拟合程度来决定参数，但最终效果不太理想。 最后最高分版本使用的是一阶指数平滑，参数已经调到1.1，正常范围是0~1，这说明预测数据对最后一天的依赖更大。还有一种说法是参数大于1之后应该用更高阶的指数平滑来分析， 但同样二阶的效果并不好，可能是跟参数没有调好有关系，总之这里的调参非常玄学。
其他模型
以下提到的其他模型仅有考虑但并未代码实现。
ARIMA通过差分运算，将非平稳序列转变为平稳序列而后进行分析，对于练习赛数据， 不管是一阶差分还是二阶差分均不能将原序列转化为平稳序列，因此未使用ARIMA。GARCH则是针对波动率聚集现象进行建模，简单表述为 “大波接大波，小波接小波”，通过观察原序列也并未发现有此规律。以上仅凭肉眼排除使用ARIMA与GARCH，可能有欠考虑， 如果进复赛是会尝试这两个模型，尤其是GARCH。由于代码中并未使用到此两种模型，故也未做更深入的学习。
回归树是决策树的一种，用以解决回归问题，通过CART算法构建，核心通过使平方误差最小化来寻找最优切分特征与最优切分点， 其训练集划分也与线性回归模型有些类似，若干维度的X预测下一期值。但回归树建完后规模通常过大，造成过拟合，这可以通过剪枝来进一步优化， 但回归树是否真的适合时间序列分析也是值得商榷的，比赛后期考虑回归树可能有点病急乱投医的意思了。此处也准备在之后做更系统的学习。
至于随机森林与GBDT，则完全是一种理想中的方法。一来自己本身机器学习的基础并不扎实，难以不依赖第三方库来实现它们；二来即使可以实现， 其训练效率上肯定也是一个很大的问题。而LSTM则更是一种难以徒手实现的方法了，争取在之后的学习中熟悉了解并实现它们。
还有一个模型直觉上应该也适合这种时间序列建模，尤其是预测值与最相邻阶段的值相关性极大的序列——隐马尔可夫模型（HMM）。 这是在正式赛前两天在上随机过程课时想到的一个方法，在马尔可夫链中，每个状态仅依赖于之前的n个状态，求解关键是建立状态转移矩阵， 矩阵中的每个元素为相应的状态转移概率。而对于隐马尔科夫模型，除了可观察到的状态外（请求量），还存在一个隐藏状态集合（当前请求量的变化趋势）， 如果这两个状态是概率相关的，则可用HMM来分析。李航的《统计学习方法》中有关于HMM的讲解，以及关于其学习方法的EM算法，之后会做更深入的了解。
小结
总体上比赛的预测部分还是需要有一定机器学习基础的，如果之前就有写过一些经典的训练方法，此时完全可以拿出来使用。 对于我们这些现学现写的，还是只能尝试一些简单的模型。
预测开头有提到原始数据预处理的问题，这点应该是最需要好好反思的。训练数据中由于节假日的存在，造成某一天的请求量异常， 还有其他非节假日的噪点存在，怎么处理这些噪点？在代码中我们仅仅用周围的平均值来取代原始节假日的请求数，而对整体则通过高斯去噪进行特别粗糙的平滑处理， 高斯去噪的参数也是不断手动尝试，对于分数提升起到了一定的效果。这方面可在之后多补从补充DM相关的知识。
放置
放置阶段可以看做是一个多重二维背包问题，一个背包的容量有两个维度CPU（核数）与MEM（内存），在两个维度均不能超分的前提下，使的其中一个维度的利用率最大。 这是一个纯算法问题，既可以用经典的动态规划求解，也可以用一些启发式算法。
动态规划
首先要推荐的是一篇文章https://www.kancloud.cn/kancloud/pack/70125（背包问题九讲）。
具体实现还是比较简单的，下面是核心代码：
for k in range(1, len(matrix)): # c第k件物品
for i in range(len(matrix[0])): # i维度1剩余大小（CPU）
for j in range(len(matrix[0][0])): # j维度2剩余大小（MEM）
if i < w1[k] or j < w2[k]:
matrix[k][i][j] = matrix[k - 1][i][j]
else:
matrix[k][i][j] = max(matrix[k - 1][i][j], matrix[k - 1][i - w1[k]][j - w2[k]] + v[k])
状态转移方程的解释可参考推荐文章，在此也不再赘述。
下面要考虑的是如何加快动态规划算法的求解速度：
- 对于多重背包问题中物品数量的分解，可将复杂度由O(VΣn[i])降到O(VΣlog n[i])，核心是用二进制表示来降低划分数量， 具体划分同样可参考推荐文章；
- 由于题目不仅要知道价值最大值，还要知道具体的放置过程，因此不能将数组降维来降低空间复杂度。对于追踪放置过程有两种方式： 一个是在状态转移的同时用另一个矩阵来记录转移点；二是在状态矩阵建立完毕后再次遍历以找出状态转移点。前者以空间换取时间， 可以取得更快的求解速度；
- 整体上对比赛中的放置部分采取动态规划算法也只是针对每个物理服务器而言找到一个最优解，因此它也是一种贪心算法，并不能保证全局最优。 而考虑全局采取动态规划难度还是比较大的，比赛中其他高分队伍可能会解决此问题，那在放置阶段会得到接近满分的结果。再说到此处优化速度， 可以在对某个物理服务器找到一个最优解时并不立即寻找下个物理服务器的最优解，而是遍历剩余未放置虚拟机数量，观察是否满足当前物理服务器的最优放置方法， 若满足，则直接复制当前物理服务器，若不满足，再去使用动态规划寻找下个最优解。实验中此方法可大大加快算法的求解速度。
退火算法
退火算法是一种启发式算法，即设定初始温度、结束温度和降温速度三个参数，通过调整这三个参数可以确保算法在规定时间内收敛到一个比较好的解（同样并不能保证最优解）， 但有一定概率跳出局部极值点。
联系到本次比赛，将退火算法与首适应算法结合，每次循环随机交换两个虚拟机的位置，通过暴力循环不断降低评价函数，最终也可得到一个次优解。
以下为评价函数：
physical_server_numbers = len(physical_server_cluster_resource_left) - 1
target_resource = {"CPU": physical_server_CPU, "MEM": physical_server_MEM}[resource]
target_resource_index = {"CPU": 0, "MEM": 1}[resource]
last_rate = physical_server_cluster_resource_left[physical_server_numbers][target_resource_index] / float(
target_resource)
mark = physical_server_numbers + last_rate
小结
最终版本的代码里使用的是退火算法，测试里也注意到单独使用首适应在虚拟机乱序下的放置结果与退货+首适应求得的结果几乎一致，这可能是因为训练集的规模比较小。 而过早使用退火算法取得较好结果，也降低了我们尝试全局动态规划找到最优解的动力，最终比赛的分数变化较大很大程度上应该是因为不完美的放置算法导致的。
最后
不管怎样，得到这样的结果还是本身代码有问题，赛制对于所有人都是公平的。调整心态，学到东西最重要。^_^