大數(shù)據(jù)計算理論基礎(chǔ)201405陳國良

大數(shù)據(jù)計算理論基礎(chǔ)

ComputingTheory

FoundationsofBigData2014年5月陳國良，陸克中，毛睿深圳大學計算機與軟件學院2摘要：

大數(shù)據(jù)是當前IT信息技術(shù)研究和應(yīng)用的熱點。但是，目前的研究多集中于系統(tǒng)和應(yīng)用層面，理論基礎(chǔ)方面的探討相對較少。本文從計算機科學講起，以計算復(fù)雜性理論為基礎(chǔ)，著重研究大數(shù)據(jù)的計算復(fù)雜性（ComputationalComplexity）和大數(shù)據(jù)本身的復(fù)雜性（DataComplexity）：前者包括大數(shù)據(jù)統(tǒng)一化抽象表示；大數(shù)據(jù)劃分技術(shù)；大數(shù)據(jù)NC類計算理論；大數(shù)據(jù)計算模式等。后者包括大數(shù)據(jù)復(fù)雜性表示；大數(shù)據(jù)復(fù)雜性度量；大數(shù)據(jù)復(fù)雜性模型等。最后，根據(jù)大數(shù)據(jù)的4V特性，提出大數(shù)據(jù)處理應(yīng)對策略和變革思維方法研究大數(shù)據(jù)。3目錄計算機科學與計算問題分類計算機科學的經(jīng)典定義計算機科學定義的數(shù)學解釋計算機科學的歷史演變計算問題分類計算理論可計算性與計算復(fù)雜性圖靈計算模型串行復(fù)雜計算類：P，NP，NPC，NPH并行復(fù)雜計算類：NC，PC歸約大數(shù)據(jù)可計算性可(能)解與不可(用)解問題大數(shù)據(jù)可(能)解與不可(用)解問題數(shù)據(jù)庫查詢類的可(能)解與不可(用)解問題度量空間：大數(shù)據(jù)統(tǒng)一化抽象表示大數(shù)據(jù)統(tǒng)一化抽象表示的基本思路距離和度量的概念數(shù)據(jù)的度量空間表示度量空間舉例支撐點空間：度量空間的坐標化度量空間的坐標化支撐點空間的定義舉例完全支撐點空間數(shù)據(jù)的劃分技術(shù)超平面劃分有利點劃分包絡(luò)球劃分大數(shù)據(jù)NC計算理論NCi類的電路定義NCi類的層次大數(shù)據(jù)NC-類計算大數(shù)據(jù)計算模式基于MR的流計算流計算實例研究：Storm流計算增量計算大數(shù)據(jù)的復(fù)雜性大數(shù)據(jù)復(fù)雜性表示大數(shù)據(jù)復(fù)雜性度量大計算復(fù)雜性模型結(jié)論大數(shù)據(jù)處理應(yīng)對策略變革思維研究大數(shù)據(jù)1、計算機科學與計算問題分類

41、計算機科學與計算問題分類計算機科學的歷史演變計算機科學的形式化研究起源于數(shù)學的基礎(chǔ)研究：Cantor的集合論與Russell悖論：數(shù)學家們在集合論中發(fā)現(xiàn)了邏輯矛盾LetR={x|x?x}thenR∈R?R?RHilbert綱領(lǐng)：即在通用的形式邏輯系統(tǒng)中可以機械地判定任何給定命題的真?zhèn)危ㄍ陚湫裕?，證明每一形式系統(tǒng)的相容性，從而導出全部數(shù)學的相容性。G?del提出了形式系統(tǒng)的不完備性，它不能窮舉全部數(shù)學命題，任何足夠強的相容形式系統(tǒng)中均存在著該系統(tǒng)中所不能判定真?zhèn)蔚拿}。Hilbert綱領(lǐng)的失敗啟發(fā)人們不要花費大量精力去證明那些不能判定的問題，而應(yīng)集中精力研究“可計算求解性”問題。在此思想指引下，A.M.Turing從計算一個數(shù)的一般過程入手，將可計算性概念與機械程序的執(zhí)行過程統(tǒng)一起來，此即有名的圖靈計算模型。51、計算機科學與計算問題分類計算問題分類6計算問題不可判定問題可判定問題難解(不可能)解問題易解(可解，多項式時間)問題不可近似問題可近似問題大數(shù)據(jù)可解(BD-Tractable)問題大數(shù)據(jù)不可解(BD-Intractable)問題大數(shù)據(jù)不可近似問題大數(shù)據(jù)可近似問題2、計算理論（Theoryofcomputation）可計算性與計算復(fù)雜性可計算性：對于一個問題，如果存在一個機械過程，對給定的輸入，能夠在有限步內(nèi)給出結(jié)果，則稱此問題是可計算的。所謂機械的過程，系指在描述計算的某種設(shè)備上，實施該計算過程，而給出計算結(jié)果?？捎嬎阈蕴卣鳎捍_定性：對相同的初始輸入產(chǎn)生相同的輸出。有限性：在有限設(shè)備上能在有限時間內(nèi)求解。構(gòu)造性：每一計算過程的執(zhí)行都是“機械的”或“構(gòu)造性的”。數(shù)學描述性：計算的過程可以用嚴格的數(shù)學進行描述。停機問題：對于任意的圖靈機和輸入，是否存在一個算法，用于判定圖靈機在接收初始輸入后可到達停機狀態(tài)。若能找到此算法，停機問題可解，否則不可解。計算復(fù)雜性：用數(shù)學方法研究各類問題計算的復(fù)雜性質(zhì)。也可理解為利用計算機求解問題的難易程度。算法復(fù)雜性：算法復(fù)雜性是對算法效率的度量，系指運行算法所耗費的時間和空間（存儲量）。72、計算理論（Theoryofcomputation）圖靈計算模型將可計算性概念與機械程序的執(zhí)行過程統(tǒng)一起來，確認任一機械執(zhí)行過程均可在一臺機器（即圖靈機）上實現(xiàn)。圖靈機：圖靈機就是對一條兩端可無限延長的紙帶上的0和1執(zhí)行操作，一步一步地改變紙帶上的0或1值，經(jīng)此有限步驟最終得到一個滿足預(yù)先要求的符號串變換。圖靈機的作用：圖靈的研究成果認為“可計算性＝圖靈可計算性”，即任何在圖靈機上可求解的問題都是可計算的！82、計算理論（Theoryofcomputation）串行計算類：P，NP，NPC，NPHP類問題：在確定圖靈機上多項式（Polynomial）時間內(nèi)可求解的一類問題。NP類問題：在非確定圖靈機上多項式時間內(nèi)可求解的一類問題（所有NP問題均必須在有限步內(nèi)是可判定的）。NPC問題：對于L∈NP的問題，且NP類中的每一個L’均可在多項式時間內(nèi)歸約（轉(zhuǎn)換）到L，L’≤PL，則稱L為NPC（NP完全）的（第一個被證明是NPC問題的是布爾滿足性問題：BooleanSatisfiabilityProblem，SAT）。NPH（難）問題：一個問題H稱為NP難的，當且僅當存在著一個NPC問題L，L可在多項式時間內(nèi)圖靈歸約（Turing-Reduction）到H。簡記之為：L(NPC)

≤T

H(NPH)

（例如判定停機問題是NPH問題）。9NPHNPCNPP

NPPNPC當P≠NP時，NPH問題不能在多項式時間內(nèi)求解。當P≠NP時，NPC問題不能在多項式時間內(nèi)求解。注：①所有NPC問題均能在多項式時間內(nèi)歸約到NPH而求解之。

②NPC中的每個元素均必須是NP中的元素。

③NPH問題中不一定必須是NP中的元素。2、計算理論（Theoryofcomputation）并行計算類：NC，PCNC-類問題：在PRAM模型上，使用多項式數(shù)目（Polynomialsize）的處理器，運行在對數(shù)多項式時間（Polylogtime）內(nèi)的一類問題。（此類問題包括整數(shù)加法、乘法、除法，矩陣乘，行列式，找最大匹配（RNC問題）等）。NC-算法：在PRAM模型上，一個求解問題的算法使用了多項式數(shù)目的處理器，花費了對數(shù)多項式時間，則稱此算法為NC-算法。NC-歸約形式定義：對于問題L1和L2，如果存在一個NC-算法，可將L1的求解轉(zhuǎn)換成L2的求解，則稱L1可NC-歸約到L2，簡記為L1

≤NCL2。P完全（PC）問題：對于L∈P，且P中的任意L’均可NC-歸約到L，則稱L是P完全的。10PNCPC

當P≠NC時，PC問題不能在多項式時間內(nèi)求解。2、計算理論（Theoryofcomputation）

113、大數(shù)據(jù)可計算性可（能）解（Tractable）與不可（用）解（Intractable）可（能）解（Tractable:meaning“easilymanaged”）問題：經(jīng)典定義是在多項式時間內(nèi)可以解決的問題。不可（用）解（Intractable）問題：系指理論上能夠解（在無限長時間內(nèi)），但實際上求解時間太長而無法用的問題。因此缺乏多項式時間解的問題被視為不可（用）解的問題。完全問題不可解性：在P≠NP時，NPC問題是不可（用）解的問題；在P≠NC時，PC問題是不可（用）解的問題。大數(shù)據(jù)可（能）解與不可（用）解問題在大數(shù)據(jù)時有些問題是可（能）解的，例如布爾選擇查詢（在數(shù)據(jù)集D中，是否存在某一列的元組值為指定值，在B+樹[1]索引上可在O(log(|D|))時間內(nèi)解決）；但很多問題是不可（能）解的，例如圖的寬度優(yōu)先搜索[2]（是P完全的）。在大數(shù)據(jù)時，傳統(tǒng)的可（能）解問題，可能成為不可（用）解問題：例如采用速度可達6Gbps的快速硬盤，線性掃描1EB（E=1018字節(jié)）的數(shù)據(jù)，這本是線性復(fù)雜度的可（能）解問題，但實際需要長達5.28年時間，這就變成了不可（用）解問題了。12注1：B+樹是B樹的變形，關(guān)鍵字與數(shù)據(jù)值（鍵/值）成對存儲在樹的同一節(jié)點中，其中所有數(shù)據(jù)值存在樹的葉節(jié)點中，只將關(guān)鍵字與子女節(jié)點的指針存在樹的內(nèi)節(jié)點中。注2：寬度優(yōu)先搜索（BFS：Breadth-First-Search）從根節(jié)點開始，沿著樹的寬度遍歷其所有子節(jié)點，這些子節(jié)點被加入一個先進先出FIFO的隊列中。然后從FIFO隊列中取出先進入的子節(jié)點，重復(fù)上述寬度遍歷過程，直到所有節(jié)點均被訪問過。BFS問題是個P完全問題。

3、大數(shù)據(jù)可計算性13PTIME(ΠTQ)BD-IntractableBD-Tractable(ΠTQ0)P(ΠTQ)NCPCΠTQ0大數(shù)據(jù)統(tǒng)一化抽象表示的基本思路類型和距離函數(shù)：這是數(shù)據(jù)表示的兩個基本參數(shù)，其中類型可以是一維數(shù)據(jù)、多維數(shù)據(jù)、字符串、圖片等；對于復(fù)雜數(shù)據(jù)，除了精確匹配以外，更多要以距離衡量彼此的相似性。多維數(shù)據(jù)作為統(tǒng)一化抽象表示的局限性：使用多維數(shù)據(jù)作為統(tǒng)一表示時，數(shù)據(jù)本身必須能表示成特征向量（FeatureVector），且數(shù)據(jù)間的相似性用特征向量的歐式距離等衡量。但對有些數(shù)據(jù)和應(yīng)用無法滿足上述條件，例如文本字符串往往使用編輯距離，蛋白質(zhì)序列只能使用比對（Alignment）距離，圖片等只能使用Hausdorff距離等等。統(tǒng)一化抽象表示：針對上述情況，可將Variety數(shù)據(jù)抽象成統(tǒng)一的數(shù)據(jù)類型，將Variety距離抽象成統(tǒng)一的距離函數(shù)，此即下述的度量空間表示。4、度量空間：大數(shù)據(jù)統(tǒng)一化抽象表示14

4、度量空間：大數(shù)據(jù)統(tǒng)一化抽象表示15度量空間拓撲與拓撲空間：如果非空集合X的子集族τ，它滿足以下條件：?和X在τ中；τ的任意子族之元素的“并”（∪）在τ中；τ的任意子族之元素的“交”（∩）在τ中。則稱τ為X上的一個拓撲（Topology），偶對（X,τ）稱為X上的一個拓撲空間（TopologySpace）。度量與度量空間：設(shè)X為非空集合，d:X×X

→R，(x,y)→d(x,y)為映射，如果?x,y,z∈X滿足：

d(x,y)=d(y,x)（對稱性）；

d(x,y)≥0和d(x,y)=0iffx=y（半正定性）；

d(x,z)≤d(x,y)+d(y,z)（三角不等式）。則稱d為X上的一個度量（距離），偶對（X,d）為度量空間，d(x,y)稱為是x與y間的距離。注：度量空間是一類特殊的拓撲空間；而n維歐氏空間是一類特殊的度量空間。4、度量空間：大數(shù)據(jù)統(tǒng)一化抽象表示16度量空間舉例字符串：數(shù)據(jù)類型可用文本類型（如ASCII碼等）數(shù)組表示；其距離函數(shù)可用編輯距離（EditDistance）表示：即將兩個字符串相互轉(zhuǎn)換所需的編輯動作（插入、刪除、替換等）的總開銷。蛋白質(zhì)序列：數(shù)據(jù)類型可用字節(jié)（蛋白質(zhì)的序列由20種氨基酸表示，每一種氨基酸用一個字節(jié)表示）數(shù)組表示；其距離函數(shù)可用全局比對（GlobalAlignment）表示：即加權(quán)的編輯距離?；蛐蛄校簲?shù)據(jù)類型可用字節(jié)（基因序列由4種堿基表示，每一種堿基用一個字節(jié)表示）數(shù)組表示；其距離函數(shù)可用海明距離（HammingDistance：對應(yīng)位不相同的數(shù)目）表示。圖片：數(shù)據(jù)類型可用長度為66的實數(shù)數(shù)組表示，用以表征圖片的結(jié)構(gòu)、紋理、顏色等特征；其距離函數(shù)可用“結(jié)構(gòu)距離（歐幾里得）+紋理距離（歐幾里得）+顏色距離（曼哈頓：Σ|xi-yi|）”三種距離的代數(shù)和表示。4、度量空間：大數(shù)據(jù)統(tǒng)一化抽象表示17度量空間的坐標化度量空間的問題：度量空間是個數(shù)據(jù)集合，集合中的諸元素沒有坐標，這樣就無法對集合中的諸元素按遠近施行劃分（Partitioning）操作。約定：令（M,d）是一個度量空間，S={xi|xi∈M,i=1,2,…,n}是M中的一個數(shù)據(jù)集，S?M；在S中選擇k個支撐點（Pivots），P={pj|j

=1,2,…,k}，

P?S。度量空間數(shù)據(jù)集S到k維實數(shù)空間的映射：

M→

Rk:IP,d(x)=(d(x,p1),d(x,p2),…,d(x,pk)),x∈S

其中d(x,pi)是x到pi的距離。這樣，度量空間M中數(shù)據(jù)集S的元素xi都賦予了坐標。支撐點空間的定義支撐點空間定義：IP,d(S)

={xP|xP=IP,d(x)=(d(x,p1),d(x,p2),…,d(x,pk)),x∈S}解釋：支撐點空間就是度量空間中元素集合S在多維實數(shù)空間中的映象，其每個元素的各個坐標是相應(yīng)的度量空間中數(shù)據(jù)到各個支撐點的距離。5、支撐點空間：度量空間的坐標化18

5、支撐點空間：度量空間的坐標化19編號原坐標(x,y)映射后坐標(d(A,p1),d(A,p2))1(0,0)(0,1.414)2(0,1)(1,1)3(1,1)(1.414,0)4(1,0)(1,1)5(0.5,0.5)(0.707,0.707)支撐點A支撐點B支撐點C初始值012101210123ABCd(x,A)d(x,B)d(x,C)x完全支撐點空間把所有的點都選為支撐點：P=S，M→Rn

IS,d(S)={xS|xS

=IS,d(x)=(d(x,x1),d(x,x2),…,d(x,xk)),x∈S}5、支撐點空間：度量空間的坐標化20x1x2……xnx1d(x1,x1)d(x1,x2)……d(x1,xn)x2d(x2,x1)d(x2,x2)……d(x2,xn)………………………………………………xnd(xn,x1)d(xn,x2)……d(xn,xn)6、數(shù)據(jù)劃分技術(shù)在度量空間中，我們可按數(shù)據(jù)到支撐點的遠近距離進行如下3種劃分超平面（Hyper-plane）劃分選擇中心點C1和C2；劃一超平面L（將C1和C2的連線垂直平分）；數(shù)據(jù)按距離C1和C2的遠近劃分之。21C1C2LLeftofLRightofLC1,C2

6、數(shù)據(jù)劃分技術(shù)有利點（VantagePoint）劃分選擇有利點VP1，以VP1為圓心、R1為半徑畫圓；數(shù)據(jù)按位于圓內(nèi)、外劃分之；再從圓內(nèi)、外分別選擇有利點VP21、VP22，分別以R21和R22為圓心畫圓。22d(VP1,x)≤R1d(VP1,x)>R1VP1,R1

d(VP22,x)≤R22d(VP22,x)>R22VP22,R22

……VP21,R21

R22

R1

VP1R21VP21VP22qr6、數(shù)據(jù)劃分技術(shù)包絡(luò)球（BoundingSphere）劃分選擇中心點C1，以其為圓心、R(C1)為半徑畫一圓，包含了所有數(shù)據(jù)；在上述圓內(nèi)另選中心點C2、C3，再以其為圓心，以R(C2)和R(C3)為半徑畫圓，將數(shù)據(jù)劃分成兩部分；此兩圓均在以C1為圓心的圓內(nèi)，且所有點均在兩圓內(nèi)；因為以C2、C3為圓心的圓是從以C1為圓心的圓衍生出來的，劃分可能重疊是其明顯缺點。23C1C2C3C1,R(C1)C2,R(C2)

C3,R(C3)

7、大數(shù)據(jù)NC計算理論NCi類（Nick’sClass）的電路定義：NCi類均衡電路定義：NCi可定義為可計算的一組函數(shù)，可由一簇均衡電路輸出的一組布爾函數(shù)值表示，其中電路有多項式數(shù)目個門（至多兩輸入），深度為O(login)，i≥1。（電路越深，表示電路的級數(shù)越多）RNC（RandomizedNC）類概率電路定義：它是由一簇概率電路可計算的一組函數(shù)，此電路中除了通常的門以外，還有一個具有隨機概率“正確”與“錯誤”的輸出門，電路計算正確的概率至少是1/2。NC類的層次NCi類層次可定義如下：NC1

?

NC2

?

…?

NCi，NC類一般定義：NC=∪k≥1NCk247、大數(shù)據(jù)NC計算理論大數(shù)據(jù)NC-類計算NC類與PRAM模型關(guān)系：定義EREWk、CREWk和CRCWk分別由使用多項式數(shù)目的處理器、運行時間為O(logkn)對數(shù)多項式的并行計算模型PRAM-EREW、PRAM-CREW和PRAM-CRCW可計算的一類函數(shù)，它們之間關(guān)系如下：NCk?EREWk?CREWk?CRCWk?NCk+1大數(shù)據(jù)NC-類計算：采用上述方法，首先將大數(shù)據(jù)集D劃分成多項式數(shù)目個子集Di(i=1,2,···,PolynomialSize)；然后對Di在對數(shù)多項式時間（Polytime）內(nèi)施行并行處理。如果上述步驟證明是可行的，則稱此類數(shù)據(jù)計算為NC-類計算。注1：NC類在不同的并行計算模型上是保持不變的。注2：變量x的多項式通式為：

f(x)=a1x1+a2x2+…+aixi+…+anxn

對數(shù)logx的多項式通式為：

f(x)=a1logx+a2log2x+…+ailogix+…+anlognx258、大數(shù)據(jù)計算模式基于MR的流計算MR是針對靜態(tài)批處理計算的，啟動MR時，計算數(shù)據(jù)均已到位（例如：保存在DFS中的數(shù)據(jù)）；而流數(shù)據(jù)是源源不斷流入系統(tǒng)的，顯然傳統(tǒng)的MR不行，改進的方法包括：Micro-BatchMR：首先把流式數(shù)據(jù)按到達時間的先后形成一些小的靜態(tài)數(shù)據(jù)；然后定期啟動MR施行微批處理計算。流水MR：通過作業(yè)內(nèi)或作業(yè)間數(shù)據(jù)傳輸?shù)牧魉€，實現(xiàn)OnlineHadoop，即實現(xiàn)了Map到Reduce之間數(shù)據(jù)的Pipeline，使得Map產(chǎn)生部分數(shù)據(jù)后就可送到Reduce端，以便Reduce可提前或定期計算。動態(tài)加入輸入：數(shù)據(jù)未完全到位時，提前向運行中的作業(yè)加入新的輸入數(shù)據(jù)，這樣將數(shù)據(jù)流切成較小的datasegment，可大大減少處理大作業(yè)的等待時間。268、大數(shù)據(jù)計算模式流計算（StreamComputing）定義：流處理是一種易于開發(fā)并行性的計算機編程范例，勿需顯式管理計算的任務(wù)調(diào)度、同步和通信等。組成：流處理系由一組流式的數(shù)據(jù)和在流數(shù)據(jù)單元上的一系列操作（稱之為KernelFunction）所組成。其中KernelFunction通常是流水線式的。優(yōu)點：因為Kernel和Stream抽象揭示了數(shù)據(jù)的相關(guān)性和使用數(shù)據(jù)的局部性，所以編譯工具很容易自動優(yōu)化。流處理在傳統(tǒng)的DSP或GPU中廣泛應(yīng)用。注釋：早在上世紀80年代開發(fā)的數(shù)據(jù)流語言SISAL(StreamandInteractioninSingleAssignmentLanguage)就是一種流處理語言。278、大數(shù)據(jù)計算模式實例研究：Storm流計算Storm系由函數(shù)式程序設(shè)計語言開發(fā)的。Storm系統(tǒng)架構(gòu)：系統(tǒng)采用主-從結(jié)構(gòu)，由三種節(jié)點組成：主節(jié)點（類似Hadoop的Jobtracker）統(tǒng)管全局，負責接收作業(yè)，分配任務(wù)；監(jiān)控節(jié)點（類似Hadoop的Tasktracker）負責接收任務(wù)，起/停工作進程；工作節(jié)點執(zhí)行進程，負責處理數(shù)據(jù)。Storm計算模型：該模型系由Spout（負責產(chǎn)生事件Event）和Bolt（負責接收并處理事件）組成。事件Event流會在Spout和Bolt之間動態(tài)流動，以計算出所需的結(jié)果。Storm主要優(yōu)點：Storm具有Scale-out能力，計算所需的各種狀態(tài)均是自滿足的，可以簡單地加入新的計算節(jié)點以滿足系統(tǒng)計算能力的提升；另外，Storm可以維持分布式計算涉及到的多進程間通信、同步和正確性依賴關(guān)系，確保信息會被完整處理。288、大數(shù)據(jù)計算模式增量計算（IncrementalComputing）定義：增量計算系指僅對變化的輸入數(shù)據(jù)施行重新計算，以節(jié)省全部數(shù)據(jù)計算時間。增量計算前提：增量計算需要預(yù)先定義好能被單獨處理的最小變化單元（SmallestUnitofChange）。如果一個變化在定義好的最小變化單元區(qū)間（Scope）內(nèi)，則可施行增量計算。增量計算的實現(xiàn)：構(gòu)造所有需要再計算的數(shù)據(jù)元素的相關(guān)圖（DependencyGraph）；需要修改的數(shù)據(jù)元素可由相關(guān)圖的傳遞閉包（TransitiveClosure）給出。也就是說，如果從一變化的元素到另一元素存在著一條路徑，則后者將要被修改。應(yīng)用實例：采用增量計算處理滲流（過濾）器（Percolator:IncrementalProcessingUsingDistributedTransactions），獲得比采用MR方法更好的性能，其延遲時間改善了好幾個數(shù)量級（OSDI,2010）。299、大數(shù)據(jù)的復(fù)雜性大數(shù)據(jù)復(fù)雜性表示探索大數(shù)據(jù)的本征特征（IntrinsicProperty）：尋找大數(shù)據(jù)間的本征結(jié)構(gòu)（IntrinsicStructure）；研究大數(shù)據(jù)間的跨時空連接模式（ConnectionPatterns）。量化大數(shù)據(jù)的特征表示：用抽樣、抽象和特征提取方法量化特征數(shù)據(jù)；將量化的特征數(shù)據(jù)表示成高維稀疏特征矩陣。大數(shù)據(jù)復(fù)雜性度量計算語義距離：通過上下文語義分析計算語義距離；使用測度函數(shù)（如歐式距離等）和基于機器學習模型度量語義距離。復(fù)雜性度量：選取度量參數(shù)，包括數(shù)據(jù)的多維度性（D）、多樣性（S）、不確定性（U）和間斷性（I）等；構(gòu)建復(fù)雜性函數(shù)f(D,S,U,I)=aD+bS+cU+dI。309、大數(shù)據(jù)復(fù)雜性大數(shù)據(jù)復(fù)雜性模型（BenjaminW.Wah）基于結(jié)構(gòu)的概率圖模型：概率圖模型（ProbabilisticGraphicalModel）是一類利用圖形模式（GraphicalModel）表達基于概率相關(guān)關(guān)系的模型。在此模型中表達變量（數(shù)據(jù)）之間的關(guān)系時，通常使用了貝葉斯網(wǎng)絡(luò)（BayesianNetwork）和馬爾科夫隨機場（MarkovRandomField），其主要區(qū)別