先自報(bào)家門吧妙啃，我是來自成渝賽區(qū)的一支隊(duì)伍档泽，勉強(qiáng)進(jìn)了全國總決賽，見識了其他賽區(qū)的各路神仙揖赴，大開眼界馆匿，被按在地上摩擦，最后拿了20多名燥滑，還是自己太弱了渐北，慚愧慚愧。
因?yàn)榇a所屬權(quán)的問題铭拧，暫時(shí)無法公布源碼赃蛛，就簡單總結(jié)下這次比賽的收獲恃锉。
今年賽題實(shí)際上包含了兩個(gè)問題，第一部分是根據(jù)虛擬機(jī)申請歷史數(shù)據(jù)預(yù)測未來一定時(shí)間的數(shù)據(jù)（根據(jù)預(yù)測準(zhǔn)確度評分）呕臂，第二部分是將虛擬機(jī)預(yù)測的結(jié)果放置在特定的物理機(jī)中破托，使資源利用率最優(yōu)（利用率公式在初賽、復(fù)賽歧蒋、決賽略有不同）土砂。詳細(xì)賽題鏈接如下：賽題介紹。

復(fù)賽階段的評分公式：

復(fù)賽階段評分公式

前半部分是評估預(yù)測結(jié)果的準(zhǔn)確度谜洽，后半部分是計(jì)算多維度資源利用率萝映。

決賽階段評分公式：

決賽階段評分公式

前半部分相同，后半部分變成了利潤率（考慮了虛擬機(jī)和物理機(jī)的價(jià)格）阐虚。

特征選擇和預(yù)處理

特征選擇

第一個(gè)問題就是特征選擇序臂，從預(yù)測結(jié)果的要求來看，預(yù)測未來幾天（1到4周）不同虛擬機(jī)的申請數(shù)量敌呈，首先想到的是以天作為特征贸宏，方便將預(yù)測結(jié)果求和。接著考慮的問題是磕洪，不同虛擬機(jī)數(shù)據(jù)之間有沒有相關(guān)性吭练。先看看歷史數(shù)據(jù)：

以天為單位的不同虛擬機(jī)的線下數(shù)據(jù)

以周為單位的不同虛擬機(jī)的線下數(shù)據(jù)

預(yù)處理

首要的疑問是：到底需不需要預(yù)處理卑吭，其次是需要哪些預(yù)處理
在嘗試了很多種預(yù)測模型之后，我的體會是马绝，對于不同的預(yù)測模型需要不同的預(yù)處理或者不處理豆赏。
· 噪聲處理
通過觀察線下數(shù)據(jù)，確實(shí)存在著遠(yuǎn)遠(yuǎn)高于其他數(shù)據(jù)的點(diǎn)，那么考慮到先進(jìn)行數(shù)據(jù)清洗掷邦。
首先是如何篩選出噪聲點(diǎn)白胀，我采用的第一種方法是3σ原則，有如下結(jié)論：假設(shè)歷史數(shù)據(jù)是符合正太分布的耙饰，那么落在μ ± 3σ的概率為99.74%纹笼，那么落在這個(gè)范圍之外的點(diǎn)，可以看作是噪聲點(diǎn)苟跪。這本身就存在一個(gè)問題廷痘，實(shí)際數(shù)據(jù)未必符合正太分布，因?yàn)榇嬖谶f增的趨勢件已，因此笋额，這是一種近似處理。
嘗試的第二種方法是箱型圖篷扩，之前沒聽過這種算法兄猩，學(xué)習(xí)了其他隊(duì)伍的結(jié)果。大概的思路是先將數(shù)據(jù)排序鉴未，取出四分之一位置和四分之三位置的數(shù)據(jù)取差枢冤，再乘以一個(gè)系數(shù)（一般取3），在區(qū)間(Q3+3ΔQ, Q1-3ΔQ)之外的值被視為噪聲铜秆，可以參考：WIKI-箱型圖淹真。
還有其他的方法，比如聚類方法：K-Distance等连茧，大概了解核蘸，沒有深究。
· 更新異常值
首先直接刪除異常值是不客觀的啸驯，因?yàn)檫@是一個(gè)時(shí)間序列客扎，刪除異常值就等價(jià)于在這個(gè)時(shí)間點(diǎn)上的數(shù)據(jù)為零，這和實(shí)際情況不符罚斗。最直接的想法是取均值徙鱼，這是一種簡單粗暴的方法，我覺得這種處理太粗糙针姿，不能完全表達(dá)出數(shù)據(jù)的特點(diǎn)袱吆。
其次我一直用的方法是取前兩個(gè)數(shù)據(jù)的均值代替異常值，這也符合時(shí)間序列的特點(diǎn)搓幌，算是一種“加權(quán)平均法”的思想杆故。
還有其他的方法迅箩，比如用一次指數(shù)平滑或移動(dòng)平均法將數(shù)據(jù)從頭到尾平滑一遍溉愁，這樣處理后的數(shù)據(jù)”非常好看“，但是感覺涂抹太過嚴(yán)重，失去了太多的細(xì)節(jié)拐揭，但這也是一種思路撤蟆。
以上只是一些大概的思路，其中還有很多實(shí)現(xiàn)的細(xì)節(jié)堂污，我就不一一解釋了家肯。

預(yù)測模型

線性回歸LR

線性回歸很簡單，很多人都很熟悉盟猖，是利用線性回歸方程對自變量和因變量之間關(guān)系進(jìn)行建模的一種回歸分析讨衣，常用的求取線性回歸方程的方法是最小二乘法，其中涉及到矩陣乘法式镐、轉(zhuǎn)置反镇、求逆等運(yùn)算，本來以為這部分會比較耗時(shí)娘汞，實(shí)際上計(jì)算量并不多歹茶。對于這種數(shù)據(jù)波動(dòng)很大的情況，預(yù)測效果很一般你弦。

線性回歸方程

平均法MA

平均法可以分為移動(dòng)平均衷蜓，加權(quán)平均等，移動(dòng)平均的思路是取一段區(qū)間計(jì)算其均值尘喝，作為區(qū)間外下一個(gè)數(shù)據(jù)的預(yù)測值磁浇，然后依次加入一個(gè)新值（真實(shí)數(shù)據(jù)），移除區(qū)間里的第一個(gè)舊值朽褪，重新計(jì)算下一個(gè)預(yù)測值（預(yù)測數(shù)據(jù)）置吓。

移動(dòng)平均法

加權(quán)平均法

指數(shù)平滑ES

賽前完全不了解指數(shù)平滑型凳，參考了很多資料崭捍，算是對指數(shù)平滑有了基本的認(rèn)識。
指數(shù)平滑可以分為一次指數(shù)平滑啰脚、二次指數(shù)平滑殷蛇、三次指數(shù)平滑（等價(jià)模型：Holt-Winter）
一次指數(shù)平滑類似與加權(quán)平均法，一般應(yīng)用于直線型的數(shù)據(jù)橄浓。
二次指數(shù)平滑是在一次指數(shù)平滑的基礎(chǔ)上粒梦，再進(jìn)行一次平滑。
三次指數(shù)平滑是再二次指數(shù)平滑的基礎(chǔ)上荸实，再進(jìn)行一次平滑匀们，適用于具有季節(jié)性趨勢的數(shù)據(jù)。
指數(shù)平滑的公式就省略了准给，有非常多的文章都有很詳細(xì)的說明泄朴。
從比賽來看，二次指數(shù)平滑和三次指數(shù)平滑比較適用于實(shí)際數(shù)據(jù)（季節(jié)性不明顯）露氮，其次祖灰，數(shù)據(jù)去噪對于指數(shù)平滑的影響很大，甚至可以增加去噪的力度畔规。
還有一點(diǎn)局扶，自動(dòng)尋參，在這方面我做了很多的嘗試叁扫。二次指數(shù)和三次指數(shù)都只有一個(gè)參數(shù)α三妈，而Holt-Winter有三個(gè)（后來覺得過于麻煩，被放棄）莫绣，那么對于不同的用例畴蒲，如何找到最優(yōu)的α？假如對于不同用例找到各自最好的參數(shù)对室，那么自動(dòng)尋參的意義就很大模燥，最核心的問題是如何評價(jià)一個(gè)參數(shù)的好壞狞玛？
我的思路是在0和1之間遍歷α，建立一個(gè)評價(jià)函數(shù)涧窒，選擇最優(yōu)的α。評價(jià)函數(shù)計(jì)算方法如下：

1锭亏、選定初值：α = 0.001纠吴，sum = 0；
2慧瘤、用7天的歷史數(shù)據(jù) (data[i]) 預(yù)測”未來7天“ (pred[i])戴已，計(jì)算預(yù)測值和真實(shí)數(shù)據(jù)差的平方：sum += (pred[i] - data[i+1])2，累加求和锅减；
3糖儡、是否到達(dá)最后一位歷史數(shù)據(jù)，否則轉(zhuǎn)4怔匣，是則轉(zhuǎn)5握联；
4、將歷史數(shù)據(jù)向后移動(dòng)一位每瞒，轉(zhuǎn)2金闽；
5、sum則為此α的評價(jià)度剿骨，α += 0.001代芜，轉(zhuǎn)2；
6浓利、選擇評價(jià)度最小的alpha作為最優(yōu)α挤庇。
補(bǔ)充：對于步驟2中的平方和是累加的，實(shí)際上就是每個(gè)評價(jià)度權(quán)值全為1贷掖，還有可以進(jìn)一步改進(jìn)的地方嫡秕，按照加權(quán)平均法的思想，認(rèn)為越靠近預(yù)測值的數(shù)據(jù)的評價(jià)度越重要苹威，可以使用遞減的加權(quán)函數(shù)給每個(gè)平方和加權(quán)淘菩。

其他

很可惜，有些模型沒有嘗試屠升，比如ARIMA潮改，而LSTM也沒有更多的耐心改進(jìn)，被輕易放棄腹暖。實(shí)際上對于短期預(yù)測和長期預(yù)測可以分開處理汇在，神經(jīng)網(wǎng)絡(luò)模型作長期預(yù)測也許更合適。
另外脏答，對于不同類型的虛擬機(jī)糕殉，可以使用不同的預(yù)測模型亩鬼，雖然調(diào)參的工作量會大很多，但預(yù)測準(zhǔn)確率必然更高阿蝶，這些都是后話了雳锋。