《大數據環境下增量式疊代計算框架的研究與最佳化》是依託東北大學，由張一川擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：大數據環境下增量式疊代計算框架的研究與最佳化
- 項目類別：青年科學基金項目
- 項目負責人：張一川
- 依託單位：東北大學
中文摘要,結題摘要,
中文摘要
不動點疊代廣泛存在於數據挖掘和機器學習算法中，這些算法已套用到諸如社會網路分析、高性能計算、推薦系統、搜尋引擎、模式識別等諸多領域中。在大數據時變性環境下，由於數據的快速變化，每當數據發生改變整個疊代算法也需要重新運行，這將會導致大量的運算資源浪費和性能損失。本課題擬利用新增或刪減數據和原始疊代結果數據關係研究增量式疊代計算方法，提出包括正增量與負增量計算過程的增量式疊代計算模型。避免全集數據的反覆重新計算，大幅度的提高大數據環境下疊代計算的效率。在此基礎上考慮增量式疊代計算框架最佳化方法的研究，根據增量式疊代計算方法的特點，從疊代計算本身的初始點設定及負載均衡角度研究如何對其進行最佳化，從而進一步提高疊代計算性能。最後，在增量式疊代計算模型與最佳化方法的基礎上，基於HaLoop疊代計算框架進行擴展構建一個增量式的疊代計算框架，並以真實的電子商務需求測試該框架的實際套用情況，以驗證本課題的研究。
結題摘要
在大數據的背景下, 隨著數據挖掘、機器學習等相關領域的發展, 越來越多的疊代計算套用諸多領域中。然而在大數據背景下, 疊代算法也出現諸多不適用性。低價值密度導致多次疊代計算的輸入數據既重疊又會有所差異，疊代結果無法復用；時變性在數據產生變化後原始數據的疊代結果將不再適用, 整個疊代算法也需要在數據全集上重新運行, 這將浪費大量的時間和資源；同時，大數據疊代分析算法期望作用在全集數據而非局部數據之上，當局部數據進行匯總後，需要在全集數據上進行重新疊代計算，嚴重影響了疊代計算的效率。 針對大數據環境下的疊代計算框架及最佳化方法的研究，本課題將基於現有疊代計算的研究成果，以基於Spark計算模型框架為基礎，展開了研究工作。具體研究包括：提出一個可復用的且適用於大部分算法的疊代計算模型，在不損失疊代精度的前提下利用原始的疊代結果和數據的變化量獲得新的疊代結果，採用理論證明以及實驗分析的方法, 證明了可復用疊代計算模型的正確性和性能優勢；其次，疊代算法的特性由其疊代變數所表征，疊代變數的選擇對於疊代算法的收斂速度起到至關緊要的作用。結合可復用疊代計算模型,提出一種疊代變數初始點選擇算法, 以最佳化疊代計算的效率；再次，異構的分散式計算環境中, 由於節點計算能力的差異, 並行性難以保證, 節點間同步時會相互等待,浪費計算資源, 嚴重影響計算性能。從負載均衡的角度出發, 提出了基於任務分發和調整的負載均衡算法, 提高節點並行性, 進而提高疊代計算的性能；最後，提出了基於Spark框架的歸併疊代計算模型以及歸併疊代損失彌補模型和函式，歸併疊代計算模型在不損失疊代結果精度的情況下利用現有的疊代數據分布情況對疊代數據進行區內疊代，併合並區內疊代結果以得到最終疊代結果。
