大數(shù)據(jù)研究的若干科學(xué)問題及初步研究結(jié)果課件

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

16、ep 1:重采樣數(shù)據(jù)使得整體數(shù)據(jù)隨機均勻的分布在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頁。 初步試驗 線性回歸模型：參數(shù)設(shè)置： 噪聲：樣本個數(shù)：100萬參數(shù)空間維數(shù)：100數(shù)據(jù)總量：6G使用local machines: 試驗結(jié)果重采樣問題：分布式回歸的可行性第34頁，共49頁?？尚行岳碚?如果數(shù)據(jù)中所蘊含的回歸關(guān)系f*具有一定的光滑性，LocalMachine上使用同一類核回歸方法，Global Machine使

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

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

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