大數據研究的若干科學問題及初步研究結果課件

1、 大數據研究的若干科學問題 及初步研究結果 (西安交通大學)第1頁，共49頁。內容提要關于大數據的認識大數據分析與處理中的科學問題若干進展第2頁，共49頁。關于大數據的認識（數據）(文本、圖像、地理數據、基因與蛋白質數據、視頻、程序、有限規(guī)則集等) 數據: 信息的載體;計算機處理的基本對象。 數據的多樣性和高復雜性第3頁，共49頁。關于大數據的認識 (什么是大數據?)大數據是指無法在容許的時間內用常規(guī)的軟件工具對其內容進行抓取、管理和處理的數據集合，大數據規(guī)模的標準是持續(xù)變化的，當前泛指單一數據集的大小在十幾TB和PB之間。（維基百科）ZB（1021）,EB（1018）,PB（1015）,TB

2、（1012）,GB（109）,MB（106）第4頁，共49頁。關于大數據的認識（主要來源）科學研究環(huán)保監(jiān)視遠程醫(yī)療互聯網、物聯網、社會網安全監(jiān)控大型企業(yè)信息存儲第5頁，共49頁。大數據：不能集中存儲、難以在可接受時間內分析處理、而數據整體呈現高價值的海量復雜數據集。 體量大不能用現有的物理設備集中存儲，開放，高速可擴展。復雜性高多源、異構、相關、非結構化、不一定可靠、不一致性。價值豐富個體或部分數據呈現低價值，而數據整體呈現高價值。關于大數據認識（什么是大數據？）第6頁，共49頁。關于大數據的認識（時代背景）被多數發(fā)達國家列為未來國家戰(zhàn)略優(yōu)先發(fā)展領域2011年，奧巴馬在“美國創(chuàng)新戰(zhàn)略”中發(fā)布了

3、大數據研究和發(fā)展倡議歐盟將信息技術作為歐洲2020戰(zhàn)略的優(yōu)先發(fā)展領域之一，而大數據研究為其中非常重要的一個方向法國、德國、英國、日本、韓國和俄羅斯等重要國家都將信息產業(yè)列為國家未來戰(zhàn)略優(yōu)先發(fā)展領域之一引起國際社會廣泛關注麥肯錫2011年5月發(fā)布下一個前沿：創(chuàng)新、競爭和生產力報告，認為大數據將引發(fā)新一輪的生產力增長與創(chuàng)新世界經濟論壇2012年發(fā)布Big Data，Big Impact報告，闡述大數據為世界帶來的新機遇聯合國在2012年5月公布了大數據促發(fā)展：挑戰(zhàn)與機遇白皮書IDC 在2012年6月發(fā)布中國互聯網市場洞見：互聯網大數據技術創(chuàng)新研究報告，指出大數據將引領中國互聯網行業(yè)新一輪技術浪潮第

4、7頁，共49頁。大數據價值：數據整體蘊含事件的相關性、發(fā)展的規(guī)律性與趨勢，揭示這樣的相關性、規(guī)律性與趨勢為科學探索、解決廣泛的社會發(fā)展與國家安全問題提供了依據與可能（特別是高的社會價值和解決社會學問題的方法論）。 科學研究高能物理天文生命科學機械設計經濟與社會推動物聯網、云計算產業(yè)升級大數據商業(yè)模式 (vs工業(yè)化模式)企業(yè)核心競爭力 (數據規(guī)模、 活性與解釋力)影響社會文化與組織遠程醫(yī)療.國家治理數據資產 (國家競爭力)數據主權 (同邊、海、空防)國防安全監(jiān)控網絡監(jiān)控.關于大數據的認識（價值與意義）第8頁，共49頁。大數據關注程度：30%企業(yè)已開始大數據工作，34%的企業(yè)已計劃兩年內開始。其中

5、50%數企業(yè)并不知道如何從數據中獲取價值。 一一2013年大數據普及程度及背后的炒作（Gartner）關于大數據的認識（值得熱嗎？）為什么要關注呢，能做什么？ 高附加值在哪里？數據的價值得到廣泛認可數據挖掘成為普世的高新技術值得熱，但不可以一哄而起!第9頁，共49頁。物理、材料、電子等大數據研究催生大數據產業(yè) (從數據到價值的產業(yè)鏈）數據獲取與管理數據查存與處理數據分析與理解數據工程與應用數學與統計學大數據研究:高度的多學科綜合研究大數據產業(yè)管理（產業(yè)鏈管理、商業(yè)模式、公共政策）計算機科學各行各業(yè)數據管理數據質量數據標準數據共享數據隱私存儲查詢存儲模式查詢算法實時處理軟硬件數據挖掘數據表示數據

6、建模高效計算統計推斷數據工程第10頁，共49頁。超高維問題重采樣問題計算理論問題分布實時計算問題非結構化問題可視分析問題大數據分析與處理中的科學問題第11頁，共49頁。大數據高維問題：“決策要素（P）伴隨大數據(n)呈現更高量級”所引起的解的不確定性與經典統計推斷失效問題。 經典統計學：np; 高維問題：pn; 大數據高維問題：p=O(exp(n), n -. 解 漸近正態(tài) 大數據研究中的科學問題（超高維問題）線性模型:數據：矩陣形式：第12頁，共49頁。 基本科學問題 如何補足信息使問題可解?非iid 數據統計學；低維幾何的高維泛化(積分幾何)； 超高維數據的低維特征(多維特征提取等)；熱點

7、研究：稀疏建模（壓縮感知、低秩矩陣分解、基于稀疏性的特征提取、數據降維、壓縮學習等）大數據研究中的科學問題（超高維問題）第13頁，共49頁。大數據的重采樣：如何進行合適的subsampling，將大數據隨機劃分成若干小數據集，而根據小數據集所獲得的統計推斷，進行聚合處理后能反應原大數據集的規(guī)律與形態(tài) (分布式算法)。熱點問題：The Big Data Bootstrap. Kleiner et.al. 2012 ICML 大數據研究中的科學問題（重采樣問題）X1X2X3Xn隨機機制D1DkDm.聚合機制第14頁，共49頁。基本科學問題 如何重采樣以反映整體數據特征? 分布式算法可行性嗎? 基于

8、試驗設計的重采樣； 更加有效的聚合原理; Subsampling的原則（相似性，傳 遞性,) 大數據研究中的科學問題（重采樣問題）未知總體實驗設計大數據就是“總體”如何實驗設計體現總體數據相似性D1D2D3傳遞性第15頁，共49頁。大數據研究中的科學問題（計算理論問題）計算理論：大數據背景下有關一個計算問題是否可解與能解的理論。傳統上，一個可解性問題是指能在有限步內在圖靈機上求解的問題；一個問題能解是指在可接受的存儲空間與時間代價下，該問題可以求解。M.R. Garey, D.S. Johnson, Computers and Intractability: A guide to the th

9、eory of NP-completeness.經典的計算復雜性理論（可解性理論）：計算時間（時間復雜性），占用內存空間（空間復雜性）第16頁，共49頁。大數據研究中的科學問題（計算理論問題） 基本科學問題 大數據問題的可解性理論；時間復雜性理論（難和易如何定義？）對具體類大數據的復雜性理論: 流數據（容易=處理速度快于數據更新速度）分布式數據（容易=交互速度快于數據處理速度）D1D2D3交互數據處理第17頁，共49頁。分布式實時計算:是大數據處理的計算模式，它包含多處理器自主計算、相互通信，為完成統一任務而并行工作的實時計算過程。主要挑戰(zhàn)來自數據的分布性與計算的實時性要求。大數據研究中的科學

10、問題（分布實時計算）HDFSHBaseMapReduceHadoop第18頁，共49頁。 基本科學問題 與分布式實時計算相適應的存儲 與查詢 (理論、技術)；問題的可分解性與解的可組裝性?大數據環(huán)境下的機器學習與數據挖掘;眾包(crowdsourcing)方法論 . 函數：新增加數據D2數據D1D1 + D2Zongben Xu et.al. Efficiency speed-up for evolutionary computation Fundamentals and Fast-Gas. AMC 2003編碼大數據研究中的科學問題（分布實時計算）第19頁，共49頁。大數據研究中的科學問題（

11、非結構化問題）非結構化問題：不能用有限規(guī)則完全表征與刻畫，并不能在可接受時間內形式化處理的大數據。主要的挑戰(zhàn)來自數據的異構性、信息的不相容性與認知的不一致性。 (結構化大數據85%:文本、圖像、時空數據、基因與蛋白質、視頻）第20頁，共49頁。 基本科學問題 異構數據的統一表示與分析方法 (向量 矩陣 張量)非結構化數據處理的統一框架（特別是機器學習算法）； 多源異構數據的信息融合；基于認知的非結構化信息處理； 非結構化數據文本圖像視頻統一機器學習框架決策：大數據研究中的科學問題(非結構化問題)第21頁，共49頁。大數據研究中的科學問題（可視分析問題）可視分析：運用與人類視認知相一致的圖形或者

12、圖像方式生動展示高維數據的內在結構與規(guī)律性。提供了人機協同處理數據、人人廣泛參與收集理解的平臺（或許是解決大數據問題的另外一條道路）。數據空間特征提取映照關系可展示的幾何空間FacebookWordleWhisper第22頁，共49頁。 基本科學問題 高維數據的本質特征提?。恍蜗蟮慕Y構化表征（可表達幾何空間的構造）；從數據特征空間到可表達幾何空間的映照設計；基于不變量（幾何，代數）的高維數據展示方式；非結構化數據的隱結構識別與展示； 大數據研究中的科學問題（可視分析問題）Microsoft T-drive Yuan et al., 2010平行坐標系第23頁，共49頁。超高維問題：大數據聚類重

13、采樣問題：分布式算法的可行性實時計算問題：網絡流計算非結構化問題：基于視覺原理的數據挖掘解決科學問題的若干進展第24頁，共49頁。大數據聚類:對特征數p遠大于樣本數n的大數據進行聚類。新問題：有大量冗余特征，聚類時必須同時剔除冗余特征(識別有效特征）；特征數隨樣本數變化（p=p(n)）。本質上要求同時解決聚類、特征選擇、不同時刻聚類相容性問題(特別是穩(wěn)定聚類問題)。超高維問題：大數據聚類K均值聚類：導致：最優(yōu)分類與特征的維數p變化無關對有效特征有嚴格的判定準則期望：第25頁，共49頁。超高維問題：大數據聚類K均值：模型：基本思路:重寫目標函數為特征的“分離可加”形式，以此抽象新的最優(yōu)劃分定義，

14、使得最優(yōu)劃分與p無關，從而產生大數據的穩(wěn)定聚類。( Chang ,Lin & Xu, Sparse K-Means via l/l0 Penalty for High-dimensional Data Clustering, 2014.) 最優(yōu)劃分:噪音特征:一個特征j為噪音特征如果對于任意給定的劃分C都有否則為相關特征。第26頁，共49頁。（I） (II)理論：如果數據X由高斯混合模型產生，其中有p*個相關特征，p-p*個噪音特征，則結論：高斯混合數據具有穩(wěn)定聚類；對于這樣的大數據而言，其最優(yōu)劃分與p無關（n足夠大）：Xp1Xp2Xp3XptC*1C*2C*3C*t超高維問題：大數據聚類第2

15、7頁，共49頁。實現算法：超高維問題：大數據聚類第28頁，共49頁。實驗:從高斯混合分布產生60個樣本，其中有50個特征為相關特征，其它為噪音特征，總特征數分別取p=200,500,1000.比較三種不同算法的特征選擇結果與聚類結果如下：超高維問題：大數據聚類第29頁，共49頁。基于Hadoop的分布式算法:Hadoop是主流的分布式處理系統框架。Map-Reduce是基于Hadoop的一種分布式數據處理編程模式，其工作原理為“分而治之”?；谶@種分而治之的策略設計的算法可統稱之為分布式算法。HDFSHBaseMapReduceHadoop重采樣問題：分布式回歸的可行性第30頁，共49頁。St

16、ep 1:重采樣數據使得整體數據隨機均勻的分布在m臺local machines上.X1X2X3Xn均勻分布D1DkDm.聚合機制Global MachineGlobal MachineLocal Machines重采樣問題：分布式回歸的可行性分布式回歸算法：第31頁，共49頁。Step 2: 分布地在每臺local machine運行一個回歸算法（例如正則化回歸算法），得到m個回歸估計。X1X2X3Xn均勻分布D1DkDm.聚合機制Global MachineGlobal MachineLocal Machines重采樣問題：分布式回歸的可行性第32頁，共49頁。Step 3: 將local

17、 machine所獲得的m個回歸估計聚合形成一個整體估計（運用某種聚合算法，例如簡單平均）。X1X2X3Xn均勻分布D1DkDm.聚合機制Global MachineGlobal MachineLocal Machines重采樣問題：分布式回歸的可行性第33頁，共49頁。 初步試驗 線性回歸模型：參數設置： 噪聲：樣本個數：100萬參數空間維數：100數據總量：6G使用local machines: 試驗結果重采樣問題：分布式回歸的可行性第34頁，共49頁?？尚行岳碚?如果數據中所蘊含的回歸關系f*具有一定的光滑性，LocalMachine上使用同一類核回歸方法，Global Machine使

18、用簡單平均聚合，則從泛化性的意義上分布式回歸算法是可行的（當數據量足夠大且mC0N時，分布式算法所產生的估計收斂于f*)。 (Chang & Xu, Feasibility of Distributed Regression for Big Data, 2014)重采樣問題：分布式回歸的可行性第35頁，共49頁。通信網絡異常檢測: 網絡數據是一類典型的非結構化大數據。通過檢測源節(jié)點到目的地節(jié)點連接的通信流，從而識別網絡流量異常。 實時計算問題：網絡流計算交通異常檢測第36頁，共49頁。網絡拓撲圖稀疏異常矩陣：A低秩交通矩陣：X稀疏-低秩建模：LLA-LADM算法：序列收斂到目標函數的穩(wěn)定點實時

19、計算問題：網絡流計算第37頁，共49頁。Abilene IP網絡11個城市，41個鏈接，121條OD通信流每5分鐘記錄一次網絡流量動態(tài)監(jiān)控網絡流量的變化，實時識別流量異常Data: /observatory/achive/data-collections.html紐約與華盛頓之間的流量監(jiān)控實時計算問題：網絡流計算第38頁，共49頁。非結構化問題：基于視覺原理的數據挖掘分類 為什么我一眼就看出來了呢？ 核心思想：將數據建模問題看成是一個認知問題，然后通過模擬視覺認知原理來解決。聚類 回歸 第39頁，共49頁?；诔叨瓤臻g的數據建模（尺度空間） 問題：如何從數學上刻畫視網膜上的圖像清晰程度與觀察距

20、離或者晶狀體曲率之間的關系？ 令 為自然界中某個物體的光強分布, 該物體在視網膜上所形成的光強分布 可以通過如下偏微分方程描述： 為尺度, 表示物體與視網膜之間的距離或者晶狀體的曲率。注：該模型僅為理想視網膜模型，即假設視網膜的成像是各向同性和空間不變的。其中,線性擴散模型：第40頁，共49頁?；驹恚?將數據點視為單位光強的光點，將數據集視為一幅圖像；通過模擬人眼的視覺原理，發(fā)展基于尺度空間的聚類原理與算法（IEEE Trans. PAMI, 2000). 數據圖像:尺度空間圖像:= 0.2= 1.2= 5.0數據集的多尺度演化：基于尺度空間的數據建模（聚類）第41頁，共49頁。什么是類：一個光斑可解釋為一類。光斑是由收斂于同一極大值點的所有數據點所組成，而極大值點即為該類的類中心。光 斑類中心:梯度流:300類 (3 類 (1 類 (= 0.2 )= 1 )= 5 )基于尺度空間的數據建模（聚類）第42頁，共49頁。三個基本問題: 如何離散化尺度? 什么是類? 類是單調演化的嗎? 步驟 1：確定一序列尺度 ，其中 。當 時, 每個數據點都是一類，而該數據點即為所在類的類中心。令 。步驟 2：在尺度 下，從前一尺度 的聚類中心點出發(fā)，找到新的聚類中心，并對