大數(shù)據(jù)研究的若干科學(xué)問題

及初步研究結(jié)果徐宗本

(西安交通大學(xué))Email:zbxu@Homepage:內(nèi)容提要關(guān)于大數(shù)據(jù)的認(rèn)識大數(shù)據(jù)分析與處理中的科學(xué)問題若干進(jìn)展關(guān)于大數(shù)據(jù)的認(rèn)識（數(shù)據(jù)）(文本、圖像、地理數(shù)據(jù)、基因與蛋白質(zhì)數(shù)據(jù)、視頻、程序、有限規(guī)則集等)

數(shù)據(jù):

信息的載體;計算機(jī)處理的基本對象。

數(shù)據(jù)的多樣性和高復(fù)雜性關(guān)于大數(shù)據(jù)的認(rèn)識

(什么是大數(shù)據(jù)?)大數(shù)據(jù)是指無法在容許的時間內(nèi)用常規(guī)的軟件工具對其內(nèi)容進(jìn)行抓取、管理和處理的數(shù)據(jù)集合，大數(shù)據(jù)規(guī)模的標(biāo)準(zhǔn)是持續(xù)變化的，當(dāng)前泛指單一數(shù)據(jù)集的大小在十幾TB和PB之間。（維基百科）ZB（1021）,EB（1018）,PB（1015）,TB（1012）,GB（109）,MB（106）關(guān)于大數(shù)據(jù)的認(rèn)識（主要來源）科學(xué)研究環(huán)保監(jiān)視遠(yuǎn)程醫(yī)療互聯(lián)網(wǎng)、物聯(lián)網(wǎng)、社會網(wǎng)安全監(jiān)控大型企業(yè)信息存儲大數(shù)據(jù)：不能集中存儲、難以在可接受時間內(nèi)分析處理、而數(shù)據(jù)整體呈現(xiàn)高價值的海量復(fù)雜數(shù)據(jù)集。體量大不能用現(xiàn)有的物理設(shè)備集中存儲，開放，高速可擴(kuò)展。復(fù)雜性高多源、異構(gòu)、相關(guān)、非結(jié)構(gòu)化、不一定可靠、不一致性。價值豐富個體或部分?jǐn)?shù)據(jù)呈現(xiàn)低價值，而數(shù)據(jù)整體呈現(xiàn)高價值。關(guān)于大數(shù)據(jù)認(rèn)識（什么是大數(shù)據(jù)？）關(guān)于大數(shù)據(jù)的認(rèn)識（時代背景）被多數(shù)發(fā)達(dá)國家列為未來國家戰(zhàn)略優(yōu)先發(fā)展領(lǐng)域2011年，奧巴馬在“美國創(chuàng)新戰(zhàn)略”中發(fā)布了《大數(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)力》報告，認(rèn)為大數(shù)據(jù)將引發(fā)新一輪的生產(chǎn)力增長與創(chuàng)新世界經(jīng)濟(jì)論壇2012年發(fā)布《BigData，BigImpact》報告，闡述大數(shù)據(jù)為世界帶來的新機(jī)遇聯(lián)合國在2012年5月公布了《大數(shù)據(jù)促發(fā)展：挑戰(zhàn)與機(jī)遇》白皮書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ù)浪潮大數(shù)據(jù)價值：數(shù)據(jù)整體蘊(yùn)含事件的相關(guān)性、發(fā)展的規(guī)律性與趨勢，揭示這樣的相關(guān)性、規(guī)律性與趨勢為科學(xué)探索、解決廣泛的社會發(fā)展與國家安全問題提供了依據(jù)與可能（特別是高的社會價值和解決社會學(xué)問題的方法論）。科學(xué)研究高能物理天文生命科學(xué)機(jī)械設(shè)計………經(jīng)濟(jì)與社會推動物聯(lián)網(wǎng)、云計算產(chǎn)業(yè)升級大數(shù)據(jù)商業(yè)模式(vs工業(yè)化模式)企業(yè)核心競爭力(數(shù)據(jù)規(guī)模、活性與解釋力)影響社會文化與組織遠(yuǎn)程醫(yī)療……..國家治理數(shù)據(jù)資產(chǎn)(國家競爭力)數(shù)據(jù)主權(quán)(同邊、海、空防)國防安全監(jiān)控網(wǎng)絡(luò)監(jiān)控…….關(guān)于大數(shù)據(jù)的認(rèn)識（價值與意義）大數(shù)據(jù)關(guān)注程度：30%企業(yè)已開始大數(shù)據(jù)工作，34%的企業(yè)已計劃兩年內(nèi)開始。其中50%數(shù)企業(yè)并不知道如何從數(shù)據(jù)中獲取價值。

一一《2013年大數(shù)據(jù)普及程度及背后的炒作》（Gartner）關(guān)于大數(shù)據(jù)的認(rèn)識（值得熱嗎？）為什么要關(guān)注呢，能做什么？

高附加值在哪里？數(shù)據(jù)的價值得到廣泛認(rèn)可數(shù)據(jù)挖掘成為普世的高新技術(shù)值得熱，但不可以一哄而起!物理、材料、電子等大數(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è)模式、公共政策）計算機(jī)科學(xué)各行各業(yè)數(shù)據(jù)管理數(shù)據(jù)質(zhì)量數(shù)據(jù)標(biāo)準(zhǔn)數(shù)據(jù)共享數(shù)據(jù)隱私存儲查詢存儲模式查詢算法實時處理軟硬件數(shù)據(jù)挖掘數(shù)據(jù)表示數(shù)據(jù)建模高效計算統(tǒng)計推斷數(shù)據(jù)工程超高維問題重采樣問題計算理論問題分布實時計算問題非結(jié)構(gòu)化問題可視分析問題大數(shù)據(jù)分析與處理中的科學(xué)問題大數(shù)據(jù)高維問題：“決策要素（P）伴隨大數(shù)據(jù)(n)呈現(xiàn)更高量級”所引起的解的不確定性與經(jīng)典統(tǒng)計推斷失效問題。

經(jīng)典統(tǒng)計學(xué)：n>>p;高維問題：p>>n;大數(shù)據(jù)高維問題：p=O(exp(n)),n->∞.

解漸近正態(tài)

大數(shù)據(jù)研究中的科學(xué)問題（超高維問題）線性模型:數(shù)據(jù)：矩陣形式：基本科學(xué)問題

如何補(bǔ)足信息使問題可解?非iid數(shù)據(jù)統(tǒng)計學(xué)；低維幾何的高維泛化(積分幾何)；超高維數(shù)據(jù)的低維特征(多維特征提取等)；熱點研究：稀疏建模（壓縮感知、低秩矩陣分解、基于稀疏性的特征提取、數(shù)據(jù)降維、壓縮學(xué)習(xí)等）大數(shù)據(jù)研究中的科學(xué)問題（超高維問題）大數(shù)據(jù)的重采樣：如何進(jìn)行合適的subsampling，將大數(shù)據(jù)隨機(jī)劃分成若干小數(shù)據(jù)集，而根據(jù)小數(shù)據(jù)集所獲得的統(tǒng)計推斷，進(jìn)行聚合處理后能反應(yīng)原大數(shù)據(jù)集的規(guī)律與形態(tài)(分布式算法)。熱點問題：TheBigDataBootstrap.Kleineret.al.2012ICML

大數(shù)據(jù)研究中的科學(xué)問題（重采樣問題）X1X2X3……Xn隨機(jī)機(jī)制D1DkDm….….聚合機(jī)制基本科學(xué)問題

如何重采樣以反映整體數(shù)據(jù)特征?

分布式算法可行性嗎?基于試驗設(shè)計的重采樣；更加有效的聚合原理;Subsampling的原則（相似性，傳遞性,……)大數(shù)據(jù)研究中的科學(xué)問題（重采樣問題）未知總體實驗設(shè)計大數(shù)據(jù)就是“總體”如何實驗設(shè)計體現(xiàn)總體數(shù)據(jù)相似性D1D2D3傳遞性大數(shù)據(jù)研究中的科學(xué)問題（計算理論問題）計算理論：大數(shù)據(jù)背景下有關(guān)一個計算問題是否可解與能解的理論。傳統(tǒng)上，一個可解性問題是指能在有限步內(nèi)在圖靈機(jī)上求解的問題；一個問題能解是指在可接受的存儲空間與時間代價下，該問題可以求解。M.R.Garey,D.S.Johnson,ComputersandIntractability:AguidetothetheoryofNP-completeness.經(jīng)典的計算復(fù)雜性理論（可解性理論）：計算時間（時間復(fù)雜性），占用內(nèi)存空間（空間復(fù)雜性）大數(shù)據(jù)研究中的科學(xué)問題（計算理論問題）基本科學(xué)問題

大數(shù)據(jù)問題的可解性理論；時間復(fù)雜性理論（難和易如何定義？）對具體類大數(shù)據(jù)的復(fù)雜性理論:…

流數(shù)據(jù)（容易=處理速度快于數(shù)據(jù)更新速度）分布式數(shù)據(jù)（容易=交互速度快于數(shù)據(jù)處理速度）D1D2D3交互數(shù)據(jù)處理分布式實時計算:是大數(shù)據(jù)處理的計算模式，它包含多處理器自主計算、相互通信，為完成統(tǒng)一任務(wù)而并行工作的實時計算過程。主要挑戰(zhàn)來自數(shù)據(jù)的分布性與計算的實時性要求。大數(shù)據(jù)研究中的科學(xué)問題（分布實時計算）HDFSHBaseMapReduceHadoop基本科學(xué)問題

與分布式實時計算相適應(yīng)的存儲與查詢(理論、技術(shù))；問題的可分解性與解的可組裝性?大數(shù)據(jù)環(huán)境下的機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘;眾包(crowdsourcing)方法論

……….

函數(shù)：新增加數(shù)據(jù)D2數(shù)據(jù)D1D1+D2ZongbenXuet.al.Efficiencyspeed-upforevolutionarycomputationFundamentalsandFast-Gas.AMC2003編碼大數(shù)據(jù)研究中的科學(xué)問題（分布實時計算）大數(shù)據(jù)研究中的科學(xué)問題（非結(jié)構(gòu)化問題）非結(jié)構(gòu)化問題：不能用有限規(guī)則完全表征與刻畫，并不能在可接受時間內(nèi)形式化處理的大數(shù)據(jù)。主要的挑戰(zhàn)來自數(shù)據(jù)的異構(gòu)性、信息的不相容性與認(rèn)知的不一致性。

(結(jié)構(gòu)化大數(shù)據(jù)<15%：表格、曲線、幾何圖形、程序、有限規(guī)則集)(非結(jié)構(gòu)化大數(shù)據(jù)>85%:文本、圖像、時空數(shù)據(jù)、基因與蛋白質(zhì)、視頻）基本科學(xué)問題

異構(gòu)數(shù)據(jù)的統(tǒng)一表示與分析方法(向量矩陣張量)非結(jié)構(gòu)化數(shù)據(jù)處理的統(tǒng)一框架（特別是機(jī)器學(xué)習(xí)算法）；多源異構(gòu)數(shù)據(jù)的信息融合；基于認(rèn)知的非結(jié)構(gòu)化信息處理；非結(jié)構(gòu)化數(shù)據(jù)文本圖像視頻統(tǒng)一機(jī)器學(xué)習(xí)框架決策：大數(shù)據(jù)研究中的科學(xué)問題(非結(jié)構(gòu)化問題)大數(shù)據(jù)研究中的科學(xué)問題（可視分析問題）可視分析：運用與人類視認(rèn)知相一致的圖形或者圖像方式生動展示高維數(shù)據(jù)的內(nèi)在結(jié)構(gòu)與規(guī)律性。提供了人機(jī)協(xié)同處理數(shù)據(jù)、人人廣泛參與收集理解的平臺（或許是解決大數(shù)據(jù)問題的另外一條道路）。數(shù)據(jù)空間特征提取映照關(guān)系可展示的幾何空間FacebookWordleWhisper基本科學(xué)問題高維數(shù)據(jù)的本質(zhì)特征提取；形象的結(jié)構(gòu)化表征（可表達(dá)幾何空間的構(gòu)造）；從數(shù)據(jù)特征空間到可表達(dá)幾何空間的映照設(shè)計；基于不變量（幾何，代數(shù)）的高維數(shù)據(jù)展示方式；非結(jié)構(gòu)化數(shù)據(jù)的隱結(jié)構(gòu)識別與展示；

大數(shù)據(jù)研究中的科學(xué)問題（可視分析問題）MicrosoftT-drive[Yuanetal.,2010]平行坐標(biāo)系超高維問題：大數(shù)據(jù)聚類重采樣問題：分布式算法的可行性實時計算問題：網(wǎng)絡(luò)流計算非結(jié)構(gòu)化問題：基于視覺原理的數(shù)據(jù)挖掘解決科學(xué)問題的若干進(jìn)展大數(shù)據(jù)聚類:對特征數(shù)p遠(yuǎn)大于樣本數(shù)n的大數(shù)據(jù)進(jìn)行聚類。新問題：有大量冗余特征，聚類時必須同時剔除冗余特征(識別有效特征）；特征數(shù)隨樣本數(shù)變化（p=p(n)）。本質(zhì)上要求同時解決聚類、特征選擇、不同時刻聚類相容性問題(特別是穩(wěn)定聚類問題)。超高維問題：大數(shù)據(jù)聚類K均值聚類：導(dǎo)致：最優(yōu)分類與特征的維數(shù)p變化無關(guān)對有效特征有嚴(yán)格的判定準(zhǔn)則期望：超高維問題：大數(shù)據(jù)聚類K均值：模型：基本思路:重寫目標(biāo)函數(shù)為特征的“分離可加”形式，以此抽象新的最優(yōu)劃分定義，使得最優(yōu)劃分與p無關(guān)，從而產(chǎn)生大數(shù)據(jù)的穩(wěn)定聚類。(Chang,Lin&Xu,SparseK-Meansvial∞/l0

PenaltyforHigh-dimensionalDataClustering,2014.)最優(yōu)劃分:噪音特征:一個特征j為噪音特征如果對于任意給定的劃分C都有否則為相關(guān)特征。（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足夠大）：Xp1Xp2Xp3Xpt……C*1C*2C*3C*t……超高維問題：大數(shù)據(jù)聚類實現(xiàn)算法：超高維問題：大數(shù)據(jù)聚類實驗:從高斯混合分布產(chǎn)生60個樣本，其中有50個特征為相關(guān)特征，其它為噪音特征，總特征數(shù)分別取p=200,500,1000.比較三種不同算法的特征選擇結(jié)果與聚類結(jié)果如下：超高維問題：大數(shù)據(jù)聚類基于Hadoop的分布式算法:Hadoop是主流的分布式處理系統(tǒng)框架。Map-Reduce是基于Hadoop的一種分布式數(shù)據(jù)處理編程模式，其工作原理為“分而治之”?；谶@種分而治之的策略設(shè)計的算法可統(tǒng)稱之為分布式算法。HDFSHBaseMapReduceHadoop重采樣問題：分布式回歸的可行性Step1:重采樣數(shù)據(jù)使得整體數(shù)據(jù)隨機(jī)均勻的分布在m臺localmachines上.X1X2X3……Xn均勻分布D1DkDm….….聚合機(jī)制GlobalMachineGlobalMachineLocalMachines重采樣問題：分布式回歸的可行性分布式回歸算法：Step2:分布地在每臺localmachine運行一個回歸算法（例如正則化回歸算法），得到m個回歸估計。X1X2X3……Xn均勻分布D1DkDm….….聚合機(jī)制GlobalMachineGlobalMachineLocalMachines重采樣問題：分布式回歸的可行性Step3:將localmachine所獲得的m個回歸估計聚合形成一個整體估計（運用某種聚合算法，例如簡單平均）。X1X2X3……Xn均勻分布D1DkDm….….聚合機(jī)制GlobalMachineGlobalMachineLocalMachines重采樣問題：分布式回歸的可行性初步試驗線性回歸模型：參數(shù)設(shè)置：

噪聲：樣本個數(shù)：100萬參數(shù)空間維數(shù)：100數(shù)據(jù)總量：6G使用localmachines:試驗結(jié)果重采樣問題：分布式回歸的可行性可行性理論:如果數(shù)據(jù)中所蘊(yùn)含的回歸關(guān)系f*具有一定的光滑性，LocalMachine上使用同一類核回歸方法，GlobalMachine使用簡單平均聚合，則從泛化性的意義上分布式回歸算法是可行的（當(dāng)數(shù)據(jù)量足夠大且m<C0N時，分布式算法所產(chǎn)生的估計收斂于f*)。

(Chang&Xu,FeasibilityofDistributedRegressionforBigData,2014)重采樣問題：分布式回歸的可行性通信網(wǎng)絡(luò)異常檢測:網(wǎng)絡(luò)數(shù)據(jù)是一類典型的非結(jié)構(gòu)化大數(shù)據(jù)。通過檢測源節(jié)點到目的地節(jié)點連接的通信流，從而識別網(wǎng)絡(luò)流量異常。

實時計算問題：網(wǎng)絡(luò)流計算交通異常檢測網(wǎng)絡(luò)拓?fù)鋱D稀疏異常矩陣：A低秩交通矩陣：X稀疏-低秩建模：LLA-LADM算法：序列收斂到目標(biāo)函數(shù)的穩(wěn)定點實時計算問題：網(wǎng)絡(luò)流計算AbileneIP網(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ò)流計算非結(jié)構(gòu)化問題：基于視覺原理的數(shù)據(jù)挖掘分類

為什么我一眼就看出來了呢？

核心思想：將數(shù)據(jù)建模問題看成是一個認(rèn)知問題，然后通過模擬視覺認(rèn)知原理來解決。聚類

回歸

基于尺度空間的數(shù)據(jù)建模（尺度空間）

問題：如何從數(shù)學(xué)上刻畫視網(wǎng)膜上的圖像清晰程度與觀察距離或者晶狀體曲率之間的關(guān)系？

令

為自然界中某個物體的光強(qiáng)分布,該物體在視網(wǎng)膜上所形成的光強(qiáng)分布

可以通過如下偏微分方程描述：

為尺度,表示物體與視網(wǎng)膜之間的距離或者晶狀體的曲率。

注：該模型僅為理想視網(wǎng)膜模型，即假設(shè)視網(wǎng)膜的成像是各向同性和空間不變的。其中,

線性擴(kuò)散模型：基本原理：

將數(shù)據(jù)點視為單位光強(qiáng)的光點，將數(shù)據(jù)集視為一幅圖像；通過模擬人眼的視覺原理，發(fā)展基于尺度空間的聚類原理與算法（IEEETrans.PAMI,2000).

數(shù)據(jù)圖像:尺度空間圖像:=0.2=1.2=5.0數(shù)據(jù)集的多尺度演化：基于尺度空間的數(shù)據(jù)建模（聚類）什么是類：一個光斑可解釋為一類。光斑是由收斂于同一極大值點的所有數(shù)據(jù)點所組成，而極大值點即為該類的類中心。光

斑類中心:梯度流:300類( 3類( 1類( =0.2)=1)=5)基于尺度空間的數(shù)據(jù)建模（聚類）三個基本問題:如何離散化尺度?什么是類?類是單調(diào)演化的嗎?

步驟1：確定一序列尺度

，其中

。當(dāng)

時,每個數(shù)據(jù)點都是一類，而該數(shù)據(jù)點即為所在類的類中心。令