預(yù)測算法調(diào)研報告

一、研究現(xiàn)狀預(yù)測算法研究現(xiàn)狀在過去的幾十年中，預(yù)測逐步成為各國的研究熱點，許多模型和理論被應(yīng)用于國防、科技預(yù)測的研究中，歸納下來，重要有下列三種類型:(l)基于線性理論模型:重要有卡爾曼濾波模型、指數(shù)平滑模型、自適應(yīng)權(quán)重模型(2)基于非線性理論模型:重要有小波理論模型、突變理論模型、混沌理論模型等(3)基于知識發(fā)現(xiàn)的智能預(yù)測模型:重要有神經(jīng)網(wǎng)絡(luò)模型、非參數(shù)回歸模型等。卡爾曼濾波預(yù)測模型是通過觀察方程和狀態(tài)方程構(gòu)成的線性隨機系統(tǒng)來描述濾波器，并結(jié)合遞推算法對該狀態(tài)變量進行預(yù)計，從而得到交通流的預(yù)測值?；诳柭鼮V波遞推算法的預(yù)測模型的理論簡樸、容易被理解，該辦法在預(yù)測時只能通過本路段的歷史數(shù)據(jù)進行模型訓(xùn)練，沒有考慮其它影響，因此隨著預(yù)測時間間隔的減少，該模型的性能會明顯變差。指數(shù)平滑預(yù)測模型是運用最新觀察的狀況對預(yù)測成果進行糾正，將上一次的預(yù)測誤差綜合到下一次的預(yù)測中，重復(fù)迭代后，形成一種前面全部觀察值的線性組合，然后得到最后的預(yù)測成果。該模型對存儲的規(guī)定較低，不需要訓(xùn)練，計算較簡樸，在早期的預(yù)測中應(yīng)用較多。自適應(yīng)預(yù)測模型通過實時監(jiān)測指標，如突發(fā)事故、天氣變化、平均時間等因素來動態(tài)的調(diào)節(jié)各個預(yù)測因子在模型中的權(quán)重，從而解決了線性模型不能夠較好隨機性和非線性的缺點。但該模型缺少科學(xué)的選擇機制。小波理論預(yù)測模型通過小波分析理論將數(shù)據(jù)分解為分辨率不同的信號，對分解后的信號分別采用預(yù)測算法進行預(yù)測，最后將分解信號的預(yù)測成果合成就得到了最后的預(yù)測成果。小波理論預(yù)測模型的抗干擾能力較強，但該模型的計算量大，運算效率較低，且對于每一種預(yù)測段均需要建立對應(yīng)的模型，因此當對海量數(shù)據(jù)進行預(yù)測時，需要建立的模型會非常多，訓(xùn)練模型的時間花銷也會很大。神經(jīng)網(wǎng)絡(luò)預(yù)測模型需要通過大量的數(shù)據(jù)去對神經(jīng)網(wǎng)絡(luò)模型進行訓(xùn)練，生成的模型是輸出數(shù)據(jù)與輸入數(shù)據(jù)之間的映射關(guān)系，輸入數(shù)據(jù)通過該映射關(guān)系就能得到與之對應(yīng)的預(yù)測成果。該模型預(yù)測精度高，但前期需要大量的歷史數(shù)據(jù)進行模型訓(xùn)練。非參數(shù)回歸預(yù)測模型是從歷史數(shù)據(jù)中通過近鄰匹配找到與現(xiàn)在狀態(tài)最相似的近鄰數(shù)據(jù)集合，通過這些近鄰數(shù)據(jù)去預(yù)測道路下一時刻的交通流。該模型不需要任何的先驗知識，也不需要建立復(fù)雜的數(shù)學(xué)模型，能夠適應(yīng)多變的狀況，預(yù)測精度高，但是需要大量的歷史數(shù)據(jù)。預(yù)測精度與計算效率是矛盾的。預(yù)測精度高的模型普通都較為復(fù)雜或者需要解決大量的歷史數(shù)據(jù)，從而造成計算效率較低，而計算效率高的模型其預(yù)測精度普通會較低。為了能夠在確保預(yù)測精度的同時，提高算法的計算效率，使預(yù)測算法能夠更加好的應(yīng)用于實際預(yù)測中，我們講通過實驗神經(jīng)網(wǎng)絡(luò)、非回歸參數(shù)模型選用精確率最高的算法并采用分布式計算環(huán)境來解決計算計算效率的問題。計算平臺Hadoop,Spark等技術(shù)的快速發(fā)展為海量數(shù)據(jù)的存儲與解決提供了技術(shù)支持Hadoop框架能夠?qū)Υ笠?guī)模數(shù)據(jù)進行分布式計算和存儲，顧客能夠根據(jù)數(shù)據(jù)規(guī)模方便的擴展集群規(guī)模，擴展計算能力。但是Hadoop在實際應(yīng)用過程中仍存在諸多局限性:第一、一種MapReduce任務(wù)只有Map和Reduce兩個階段，復(fù)雜的計算需要大量的Job共同完畢，Job之間的依賴關(guān)系需要由開發(fā)者自己管理，這增加了開發(fā)者的研發(fā)難度。第二、Hadoop在進行MapReduce計算的過程中，會將map的計算成果寫入到本地磁盤或Hadoop分布式文獻系統(tǒng)(HadoopDistributedFileSystem,HDFS)上，然后再通過shuffle過程將計算成果發(fā)送到reduce上進行解決，重復(fù)的磁盤讀寫使Hadoop不能夠滿足低延遲的交互式數(shù)據(jù)挖掘任務(wù)的規(guī)定。第三、時間延遲高，ReduceTask需要等待全部MapTask都完畢后才能夠開始。相比Hadoop,Spark是一種分布式內(nèi)存型計算框架，它在HadoopMapReduce優(yōu)點的基礎(chǔ)上，提出了RDD數(shù)據(jù)模型，提供了多個算子，并且能夠?qū)⒂嬎愕闹虚g成果寄存到內(nèi)存中，這使得迭代計算的效率更高，更適合于實時計算、交互式計算等場景，因此擬采用spark平臺進行分布式計算。Spark項目是使用函數(shù)式語言Scala開發(fā)的，運用Scala開發(fā)的Spark應(yīng)用程序能夠像操作本地數(shù)據(jù)集同樣操作分布在Spark集群中的分布式數(shù)據(jù)集。Spark基于RDD的一棧式解決方案，將批解決、交互式查詢、Streaming流計算、GraphProcessing等模型統(tǒng)一到一種平臺下，這些模型通過一致的API接口和相似的布署方案，使得各個框架能夠在內(nèi)存中無縫的集成，協(xié)作完畢系統(tǒng)任務(wù)。MLlib是Spark對慣用的機器學(xué)習(xí)算法的實現(xiàn)庫。機器學(xué)習(xí)是一種多學(xué)科交叉的領(lǐng)域，涉及信息學(xué)、概率論、計算機、統(tǒng)計學(xué)等眾多知識，這對機器學(xué)習(xí)開發(fā)者提出了很高的規(guī)定。MLlib為顧客提供了便捷的API接口，減少了應(yīng)用程序開發(fā)者進行機器學(xué)習(xí)開發(fā)的難度。MLlib對二元分類、回歸、聚類、協(xié)同過濾等常見機器學(xué)習(xí)算法提供了較好的支持，并提供了有關(guān)的測試和數(shù)據(jù)的生成器。Deeplearning4j（簡稱DL4J）是Java和Scala環(huán)境下的開源、分布式深度學(xué)習(xí)項目，DL4J集成了HadoopandSpark，設(shè)計用于運行在分布式GPU和CPU上的商業(yè)環(huán)境。通過深度學(xué)習(xí)算法，能夠?qū)崿F(xiàn)無監(jiān)督學(xué)習(xí)，讓數(shù)據(jù)專家免于特性提取過程中的大量枯燥工作，從而把更多精力放在更故意思的任務(wù)之上。更廣泛說來，我們認為這些算法能夠協(xié)助建設(shè)更為安全、智能、透明和高效的社會環(huán)境。在定型深度學(xué)習(xí)網(wǎng)絡(luò)的過程中，有許多可供調(diào)節(jié)的參數(shù)。我們已盡量對這些參數(shù)進行解釋，從而使Deeplearning4j能夠成為在Hadoop和其它文獻系統(tǒng)環(huán)境內(nèi)Java、Scala編程人員的DIY工具。二、擬采用算法模型（成熟方案）1、隨機森林隨機森林是一種集成學(xué)習(xí)辦法，以決策樹為基本學(xué)習(xí)單元，包含多個由Bagging集成學(xué)習(xí)理論和隨機子空間辦法訓(xùn)練得到的決策樹，輸入待分類的樣本，由各個決策樹產(chǎn)生各分類成果，最后的分類成果由各個決策樹的成果進行投票決定。隨機森林是多個決策樹的集成學(xué)習(xí)辦法，不僅能夠克服決策樹的某些局限性，并且含有良好的可擴展性和并行性，能夠有效解決大數(shù)據(jù)的快速解決問題，針對大數(shù)據(jù)環(huán)境下的預(yù)測有較好的應(yīng)用前景。隨機森林算法不僅能夠?qū)崿F(xiàn)數(shù)據(jù)解決的并行化，還能夠?qū)崿F(xiàn)訓(xùn)練單元的并行化。如圖所示，將隨機森林算法的在Spark平臺并行實施的環(huán)節(jié)以下:Step1：在每個節(jié)點上對原始數(shù)據(jù)集進行并行采樣:重復(fù)運用Bootstrap采樣的辦法對原始訓(xùn)練集D進行采樣，獲得k個子訓(xùn)練集。與此同時，沒有被抽到的數(shù)據(jù)就構(gòu)成了袋外(Out-Of-Bag,OOB)數(shù)據(jù)集。最后，我們能夠獲得k個OOB數(shù)據(jù)集。這些袋外數(shù)據(jù)能夠用于檢測隨機森林模型的預(yù)測性能。Step2:在每個節(jié)點上進行決策樹建模:用上述k個子訓(xùn)練集構(gòu)建k個決策樹模型。值得注意的是，在建樹的過程中并不是使用全部的特性，每棵樹隨機的從全部的特性中選出m個進行建模。Step3:獲得隨機森林模型:收集k個決策樹模型構(gòu)建隨機森林模型。Step4:對預(yù)測樣本進行投票，以票數(shù)最多的為最后類別，?；趕park的并行隨機森林流程圖2、softmax回歸softmax回歸算法重要用于解決多元分類問題，它能輸出分類成果并給出對應(yīng)概率值。它的重要思想是，對于由m個已標記的樣本構(gòu)成的訓(xùn)練集其中x為樣本特性，y為每個樣本對應(yīng)的類標，并且類標用假設(shè)函數(shù)對測試樣本x’估算其屬于類別j的概率值，取概率最大的類別為測試樣本的預(yù)測類別。普通把假設(shè)函數(shù)記作，以下式所示。式一中的參數(shù)是一種矩陣，矩陣的每一行能夠看作是一種類別所對應(yīng)的分類器的參數(shù)，總共有k個類別，因而參數(shù)有k行，如式二所示。式一 · 式二由式一可知，只要擬定參數(shù)就能夠得到預(yù)測模型，從而對測試樣本進行類別預(yù)測，同時也需要對參數(shù)進行評定，方便擬定預(yù)測模型與否精確，因此要對假設(shè)函數(shù)進行評定，普通把評定假設(shè)函數(shù)好壞的函數(shù)稱之為損失函數(shù)或者錯誤函數(shù)，記作：其中，是一種批示性函數(shù)，當大括號中的值為真時，該函數(shù)的成果就為1，當大括號中的值為假時，其成果就為0}例如1{5=5}=1,1{2=3}=0規(guī)定得參數(shù)就是規(guī)定解使得獲得最小值，求解的辦法有諸多個，涉及梯度下降法、牛頓法和最小二乘法等。基于spark的并行softmax流程圖softmax回歸算法的訓(xùn)練階段在Spark平臺下的并行化設(shè)計以下:step1：首先從分布式文獻系統(tǒng)HDFS上讀取訓(xùn)練數(shù)據(jù)集生成內(nèi)部數(shù)據(jù)構(gòu)造是信息模型的RDD，并且生成RDD時指定RDD的分區(qū)數(shù)目，這個分區(qū)數(shù)目就是并行任務(wù)的數(shù)目;step2：通過map操作對數(shù)據(jù)進行格式上的轉(zhuǎn)化，使RDD的每個分區(qū)中的數(shù)據(jù)都是自定義的構(gòu)造;step3：對RDD調(diào)用cache函數(shù)，進行持久化操作，同時初始化權(quán)重矩陣;step4：運用廣播變量將權(quán)重矩陣分發(fā)到各個計算節(jié)點;step5：在各個計算節(jié)點上，根據(jù)權(quán)重矩陣計算每一條數(shù)據(jù)對應(yīng)的各個類別的梯度;step6：在各個計算節(jié)點上，計算各個類別的梯度和，生成全局梯度，返回給主節(jié)點;step7：在主節(jié)點上根據(jù)全局梯度更新權(quán)重矩陣;step8：重復(fù)環(huán)節(jié)3-6，直至達成設(shè)定的迭代次數(shù);step9：迭代完畢，輸出模型參數(shù)(權(quán)重矩陣)。Spark平臺下softmax回歸算法預(yù)測階段并行化流程以下所示：step1：在主節(jié)點上將訓(xùn)練階段所得到的模型參數(shù)廣播到各個計算節(jié)點;step2：從HDFS上讀取待分類數(shù)據(jù)集生成內(nèi)部數(shù)據(jù)構(gòu)造是客戶信息模型的RDD，并根據(jù)數(shù)據(jù)集大小指定RDD的分區(qū)數(shù)目;step3：通過map操作對數(shù)據(jù)進行解析，生成內(nèi)部是自定義數(shù)據(jù)構(gòu)造的RDD，由于不需要進行迭代，因而此時不需要調(diào)用cache持久化數(shù)據(jù)集;step4：在各個從節(jié)點上根據(jù)模型參數(shù)對每一條數(shù)據(jù)計算其屬于各個類別的概率，取概率最大的類別為數(shù)據(jù)項的預(yù)測類別;step5：輸出分類成果。3、KNNK近來鄰分類算法是最慣用的分類算法，K近鄰是指歷史數(shù)據(jù)集合中與樣本數(shù)據(jù)最相似的K個鄰居樣本。KNN分類算法的基本原理是對于給定的樣本，如果該樣本在歷史數(shù)據(jù)集合中的K個最相似的樣本大多數(shù)屬于某一種類別，則認為該樣本也屬于這個類別。KNN算法既可用于樣本分類還可用于樣本回歸，樣本回歸是指將樣本的K個最相似樣本的屬性平均值賦值給該樣本，這樣就得到該樣本的屬性值。將傳統(tǒng)的單機數(shù)據(jù)挖掘算法重新進行并行化實現(xiàn)，并在分布式集群中運行，能夠按需獲取分布式集群中的硬件資源和計算能力。KNN算法模型簡樸且預(yù)測精度高，但由于在樣本相似度計算過程中，每一種待分類的樣本都需要計算它到全部歷史樣本間的距離，以擬定待分類樣本的K個近來鄰點。隨著數(shù)據(jù)量的增大，會造成相似度計算量過大，從而造成計算效率較低的問題，這樣嚴重限制了KNN算法在數(shù)據(jù)挖掘工作中的應(yīng)用。而在Spark平臺上將KNN算法進行并行化實現(xiàn)，能夠有效的解決KNN算法近鄰查找過程中搜索歷史數(shù)據(jù)庫效率過低的問題，提高算法的計算效率，有效的改善KNN預(yù)測算法的實用性。并行化的KNN算法重要有兩個數(shù)據(jù)分發(fā)回收過程:一是將歷史數(shù)據(jù)集中的全部數(shù)據(jù)對象進行切分，并分發(fā)到Spark集群中的計算節(jié)點上，然后在各個計算節(jié)點上分別計算與測試數(shù)據(jù)集中每個數(shù)據(jù)對象的相似度。該過程首先需要將歷史數(shù)據(jù)集與測試數(shù)據(jù)集寄存到分布式文獻系統(tǒng)中，然后對數(shù)據(jù)集進行數(shù)據(jù)預(yù)解決工作，目的是為了選用出與后續(xù)工作有關(guān)的數(shù)據(jù)字段，最后將數(shù)據(jù)分發(fā)到集群的各個計算節(jié)點中進行樣本相似度的計算。二是將各個節(jié)點計算所得的相似度成果進行匯總并排序，然后擬定測試數(shù)據(jù)集中每個數(shù)據(jù)對象在歷史數(shù)據(jù)集中的K個近來鄰點，基于這K個近來鄰點的特性值求得每個測試數(shù)據(jù)對象的預(yù)測值。并行化KNN算法環(huán)節(jié)以下:Step1:將輸入數(shù)據(jù)存儲到HDFS文獻系統(tǒng)中;Step2:將HDFS文獻系統(tǒng)中的數(shù)據(jù)讀取到Spark集群中，并對數(shù)據(jù)進行字段剔除的預(yù)解決操作;Step3:將輸入數(shù)據(jù)分片成多份，并分發(fā)到Spark集群中的各個計算節(jié)點中Step4:根據(jù)具體應(yīng)用的場景及規(guī)定，生成數(shù)據(jù)的特性向量;Step_5:在各個節(jié)點中，并行計算歷史數(shù)據(jù)與測試數(shù)據(jù)特性向量間的相似度;Step6:將各節(jié)點特性向量相似度的計算成果匯總并排序，取出與測試數(shù)據(jù)特性向量最靠近的K個近鄰歷史數(shù)據(jù);Step7:將K個近鄰歷史數(shù)據(jù)的平均值或基于權(quán)重的計算值作為測試數(shù)據(jù)的預(yù)測值?；趕park的并行KNN算法流程圖二、擬采用算法模型（其它方案）1、ARIMA（自回歸積分移動平均模型）由于項目需要預(yù)測的信號出現(xiàn)時間含有周期性，采用出名的時間預(yù)測算法自回歸積分移動平均模型。所謂ARIMA模型，是指將非平穩(wěn)時間序列轉(zhuǎn)化為平穩(wěn)時間序列，然后將因變量僅對它的滯后值以及隨機誤差項的現(xiàn)值和滯后值進行回歸所建立的模型?；舅枷胧牵簩㈩A(yù)測對象隨時間推移而形成的數(shù)據(jù)序列視為一種隨機序列，用一定的數(shù)學(xué)模型來近似描述這個序列。這個模型一旦被識別后就能夠從時間序列的過去值及現(xiàn)在值來預(yù)測將來值。環(huán)節(jié)一：獲取被觀察系統(tǒng)時間序列數(shù)據(jù)；環(huán)節(jié)二：對數(shù)據(jù)繪圖，觀察與否為平穩(wěn)時間序列。若為非平穩(wěn)時間序列要先進行d階差分運算后化為平穩(wěn)時間序列，此處的d即為ARIMA(p,d,q)模型中的d；若為平穩(wěn)序列，則用ARMA