袁 源, 郭進(jìn)利

(上海理工大學(xué) 管理學(xué)院,上海 200093)

0 引言

網(wǎng)絡(luò)無處不在，作為個體，我們是各種社會關(guān)系的單位；作為生物系統(tǒng)，我們又是生物網(wǎng)絡(luò)微妙反應(yīng)的結(jié)果。復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)能夠描述多種具有復(fù)雜性和高智能的系統(tǒng)。例如，細(xì)胞可以被描述為由生物反應(yīng)連接起來的復(fù)雜的生命體網(wǎng)絡(luò)[1]；因特網(wǎng)是由各種物理或無線鏈路連接的路由器和計算機組成的復(fù)雜網(wǎng)絡(luò)[2]；思想和觀點在社會網(wǎng)絡(luò)中傳播，社會網(wǎng)絡(luò)的節(jié)點是人，邊緣代表各種社會關(guān)系[3]。人們對這些復(fù)雜系統(tǒng)探索的興趣驅(qū)動了復(fù)雜網(wǎng)絡(luò)的發(fā)展。隨著海量數(shù)據(jù)的出現(xiàn)和計算機計算能力的顯著提高，復(fù)雜系統(tǒng)中的復(fù)雜網(wǎng)絡(luò)理論被廣泛地應(yīng)用于其他學(xué)科[4～7]，許多非結(jié)構(gòu)化的數(shù)據(jù)可以通過合適的網(wǎng)絡(luò)構(gòu)建技術(shù)向網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)轉(zhuǎn)換。復(fù)雜網(wǎng)絡(luò)不僅可以描述節(jié)點特征以及節(jié)點之間的相互關(guān)系，而且揭示了這種局部和全局結(jié)構(gòu)如何影響網(wǎng)絡(luò)的整體功能。因此，以網(wǎng)絡(luò)表示的數(shù)據(jù)比以向量形式表示的數(shù)據(jù)能編碼更多的信息，復(fù)雜網(wǎng)絡(luò)理論在處理機器學(xué)習(xí)或者數(shù)據(jù)挖掘更具優(yōu)勢，可以在監(jiān)督學(xué)習(xí)中利用已知節(jié)點的和未知節(jié)點的網(wǎng)絡(luò)關(guān)系預(yù)測測試節(jié)點的分類標(biāo)簽。

將機器學(xué)習(xí)和復(fù)雜網(wǎng)絡(luò)兩大工具應(yīng)用于研究復(fù)雜系統(tǒng)，不僅具有理論基礎(chǔ)，還具有廣闊的應(yīng)用前景。比如，利用機器學(xué)習(xí)技術(shù)通過網(wǎng)絡(luò)視角將不同的區(qū)域空間結(jié)構(gòu)概念化，了解大型區(qū)域空間中尺度結(jié)構(gòu)。Zhang和Fang[8]收集手機信號數(shù)據(jù)，構(gòu)建了一個以60個子城市為節(jié)點的更細(xì)粒度的交通網(wǎng)絡(luò)，采用一種新的基于機器學(xué)習(xí)的加權(quán)隨機塊體模型及視覺分析方法，檢測到兩個以深圳和廣州為中心的核心-外圍結(jié)構(gòu)，為大型區(qū)域協(xié)調(diào)政策及空間規(guī)劃策略的制定提供建議；在氣象領(lǐng)域，通過整合網(wǎng)絡(luò)科學(xué)和機器學(xué)習(xí)用來分析全球氣候系統(tǒng)這樣復(fù)雜的數(shù)據(jù)。Santos和Vega-Oliveros[9]利用地表氣溫時間序列構(gòu)建時間氣候網(wǎng)絡(luò)，并計算網(wǎng)絡(luò)指標(biāo)來表征EI Nio-Southern Oscillation(ENSO)的暖、冷期，利用機器學(xué)習(xí)創(chuàng)建模型來劃分ENSO的不同類別；在物理學(xué)科，使用機器學(xué)習(xí)來預(yù)測和識別物理系統(tǒng)(如多體量子系統(tǒng))中的關(guān)鍵動態(tài)相變，Ni和Tang[10]使用復(fù)雜網(wǎng)絡(luò)上的流行病傳播動力學(xué)作為范例設(shè)置，結(jié)合了監(jiān)督和非監(jiān)督學(xué)習(xí)，得到一個通用的全面的機器學(xué)習(xí)框架，用于檢測相變和準(zhǔn)確地識別臨界過渡點，具有很強的魯棒性，計算效率高，并普遍適用于任意大小和拓?fù)涞膹?fù)雜網(wǎng)絡(luò)。在生物領(lǐng)域，可以用基于監(jiān)督學(xué)習(xí)的方法來預(yù)測蛋白質(zhì)相互作用網(wǎng)絡(luò)中的蛋白質(zhì)復(fù)合物。Zhou和Gui[11]認(rèn)為現(xiàn)有的復(fù)合物檢測方法大多是基于圖論的，不能充分利用已知復(fù)雜的信息，提出了一種監(jiān)督學(xué)習(xí)的方法來檢測蛋白復(fù)合物。Razaghi[12]利用支持向量機，根據(jù)從轉(zhuǎn)錄組數(shù)據(jù)的圖形中獲得的距離曲線來重建基因調(diào)控網(wǎng)絡(luò)。Liu和Yang[13]從人類蛋白質(zhì)相互作用網(wǎng)絡(luò)中獲取節(jié)點嵌入，通過節(jié)點嵌入之間的相似性對蛋白質(zhì)相互作用進(jìn)行加權(quán)，使用監(jiān)督學(xué)習(xí)的方法檢測蛋白復(fù)合物，提供了一種從人類和酵母蛋白相互作用網(wǎng)絡(luò)中識別蛋白復(fù)合物的新方法。

綜上所述，本文對基于復(fù)雜網(wǎng)絡(luò)的監(jiān)督學(xué)習(xí)方法進(jìn)行綜述。第一部分系統(tǒng)梳理了使用監(jiān)督學(xué)習(xí)方法所需要的復(fù)雜網(wǎng)絡(luò)構(gòu)建技術(shù)。第二部分理清了基于復(fù)雜網(wǎng)絡(luò)監(jiān)督學(xué)習(xí)常用算法的原理、適用范圍和研究現(xiàn)狀。并在此基礎(chǔ)上，第三部分提出了基于復(fù)雜網(wǎng)絡(luò)監(jiān)督學(xué)習(xí)方法的未來發(fā)展方向。第四部分明晰了目前基于復(fù)雜網(wǎng)絡(luò)監(jiān)督學(xué)習(xí)方法的局限性，為用復(fù)雜網(wǎng)絡(luò)理論研究監(jiān)督學(xué)習(xí)方法提供了借鑒。

1 理論基礎(chǔ)

在處理機器學(xué)習(xí)問題時，利用網(wǎng)絡(luò)的形式不僅能更直觀地展示數(shù)據(jù)樣本點的特征，并且相比于非結(jié)構(gòu)化數(shù)據(jù)，網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)能夠保留更多的信息，如樣本之間的關(guān)系和全局拓?fù)浣Y(jié)構(gòu)。因此用機器學(xué)習(xí)方法處理非結(jié)構(gòu)化數(shù)據(jù)時，就需要一座將非結(jié)構(gòu)化數(shù)據(jù)轉(zhuǎn)化為結(jié)構(gòu)化數(shù)據(jù)的橋梁，將非網(wǎng)絡(luò)化數(shù)據(jù)的關(guān)鍵信息提取出來，也就是這部分要被討論的復(fù)雜網(wǎng)絡(luò)的構(gòu)建方法。

1.1 復(fù)雜網(wǎng)絡(luò)的構(gòu)建

1.1.1 相似性函數(shù)和相異性函數(shù)

復(fù)雜網(wǎng)絡(luò)G=(V,E)由節(jié)點和連邊構(gòu)成，數(shù)據(jù)樣本中的每個數(shù)據(jù)項對應(yīng)網(wǎng)絡(luò)中的節(jié)點，網(wǎng)絡(luò)中的連邊反映了節(jié)點之間的關(guān)系，在機器學(xué)習(xí)中利用相似度(或相異度)確定是否存在連邊。

相似性函數(shù)的定義如下：

設(shè)X是一個非空集合，并定義了一個等價關(guān)系。假設(shè)s是一個相似性函數(shù)

s:X×X→IS?R

(1)

假設(shè)s是有上界的，意味著supRIS是存在的。

相異性函數(shù)的定義如下：

設(shè)X是一個非空集合，并定義了一個等價關(guān)系。假設(shè)d是一個相異性函數(shù)

d:X×X→Id?R

(2)

假設(shè)d是有下界的，意味著infRId是存在的。

定義smax≡supRIS和dmin≡infRId，且smax≥0，dmin≥0，相似性函數(shù)和相異性函數(shù)有4個主要性質(zhì)。

1.1.2 相似性和相異性度量

數(shù)據(jù)集Ω={x1,…,xN},N>1是一個非空集合，每個數(shù)據(jù)項存在一個特征向量xi=(xi1,…,xip)，P>0,數(shù)據(jù)項分為類別特征、順序特征和數(shù)值特征三大類，類別特征和順序特征統(tǒng)稱為定性特征，數(shù)值特征又稱為定量數(shù)據(jù)，可以進(jìn)行數(shù)值運算。本文給出了幾個常用的定量數(shù)據(jù)相似性和距離測量公式[14]。

1.1.3 網(wǎng)絡(luò)構(gòu)建技術(shù)

如果只是把相似性和相異性度量的結(jié)果作為節(jié)點之間連邊的權(quán)重，那么相似性很小的節(jié)點之間會存在連邊。大量帶噪音的連邊甚至被扭曲的點之間也會存在連邊，就會引發(fā)網(wǎng)絡(luò)存在連接過密的問題，甚至變成全連接網(wǎng)絡(luò)。全連接網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)特征難以被識別，稀疏性更有利于網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。因此，選擇合適的網(wǎng)絡(luò)構(gòu)建技術(shù)最大程度地過濾噪音、反映樣本信息，是取得較好學(xué)習(xí)效果的前提。本節(jié)討論兩種典型的網(wǎng)絡(luò)構(gòu)建算法[15]：

(1)k-近鄰網(wǎng)絡(luò)(參數(shù)n∈V)。如果節(jié)點i在節(jié)j點的n個最近鄰之內(nèi)，或者節(jié)j點在節(jié)i點的n個最近鄰之內(nèi)，則節(jié)點i和j通過一條邊連接，顯然這種關(guān)系是對稱的。這種構(gòu)建方法的優(yōu)點在于更容易選擇節(jié)點；每個節(jié)點都有k條邊連接，不會出現(xiàn)孤立的節(jié)點。缺點是相對于ε-半徑網(wǎng)絡(luò)技術(shù)，缺乏幾何直觀。

(2)ε-半徑網(wǎng)絡(luò)(參數(shù)ε∈R)。如果‖xi-xj‖2<ε，則節(jié)點i和節(jié)點j相連，‖xi-xj‖2是指歐氏距離。ε-半徑網(wǎng)絡(luò)是由幾何驅(qū)動，關(guān)系自然對稱，但往往導(dǎo)致圖中有幾個連接組件，難以選擇。

1.2 監(jiān)督學(xué)習(xí)的理論基礎(chǔ)

機器學(xué)習(xí)按照訓(xùn)練方法的不同可以分為監(jiān)督學(xué)習(xí)、無監(jiān)督學(xué)習(xí)和強化學(xué)習(xí)。監(jiān)督學(xué)習(xí)就是給出一部分已標(biāo)記的樣本讓機器學(xué)習(xí)，得出訓(xùn)練模型，在未標(biāo)記的數(shù)據(jù)集上使用我們得出的訓(xùn)練模型對結(jié)果進(jìn)行預(yù)測。在監(jiān)督學(xué)習(xí)中進(jìn)行系統(tǒng)的輸入和輸出，并希望預(yù)測未知的輸出與已知的輸入相對應(yīng)。監(jiān)督學(xué)習(xí)方法包括分類問題和回歸問題，輸出變量是連續(xù)具體的數(shù)值，且輸出變量會隨著輸入變量變化而變化，預(yù)測問題是回歸問題；當(dāng)樣本標(biāo)簽是非連續(xù)的、有限個離散值時，預(yù)測問題是分類問題。常見的分類算法有：決策樹，支持向量機、樸素貝葉斯和k近鄰算法；回歸問題常用的回歸模型包括線性回歸、logistic回歸和多項式回歸。

與監(jiān)督學(xué)習(xí)不同的是，無監(jiān)督學(xué)習(xí)沒有已標(biāo)記的數(shù)據(jù)集，需要由機器從未標(biāo)記的數(shù)據(jù)集中發(fā)現(xiàn)一些結(jié)構(gòu)問題。我們見到的半監(jiān)督學(xué)習(xí)屬于監(jiān)督學(xué)習(xí)和無監(jiān)督學(xué)習(xí)的折中，研究已標(biāo)記的和未標(biāo)記的混合數(shù)據(jù)算法，降低監(jiān)督學(xué)習(xí)中需要標(biāo)記大量數(shù)據(jù)的成本。相比于監(jiān)督學(xué)習(xí)和半監(jiān)督學(xué)習(xí)，強化學(xué)習(xí)不需要大量的數(shù)據(jù)，需要多次嘗試來獲得某項技能，大多應(yīng)用在游戲場景[16,17]。由于本文討論的是監(jiān)督學(xué)習(xí)，對無監(jiān)督學(xué)習(xí)和強化學(xué)習(xí)不再贅述。

2 監(jiān)督學(xué)習(xí)的主要算法

我們將數(shù)據(jù)集及其標(biāo)簽分為訓(xùn)練數(shù)據(jù)和測試數(shù)據(jù)，對訓(xùn)練數(shù)據(jù)進(jìn)行訓(xùn)練得到分類器，利用測試數(shù)據(jù)判斷其分類精度。監(jiān)督學(xué)習(xí)分類器的算法分為兩類：一是分類問題。該類問題的算法有貝葉斯算法、人工神經(jīng)網(wǎng)絡(luò)算法、統(tǒng)計學(xué)習(xí)理論、決策樹、隨機森林和k-近鄰算法等。二是回歸問題。該類的算法有線性回歸、logistic回歸和多項式回歸，分別用直線、logistic曲線和n次多項式曲線來擬合自變量和因變量的關(guān)系。本文主要介紹分類問題的前四種算法，第二類問題可以參見Taneja[18]和Torre[19]等的研究。

2.1 貝葉斯算法

監(jiān)督學(xué)習(xí)算法中樸素貝葉斯分類器基于貝葉斯定理，假設(shè)條件是樣本的各特征之間是相互獨立的。這樣的條件在現(xiàn)實中往往很難滿足，而樣本的各個特征如果存在很強的相關(guān)性，會導(dǎo)致樸素貝葉斯分類器的分類效果較差，限制了樸素貝葉斯分類器的推廣。為了改進(jìn)這種假設(shè)，學(xué)者們進(jìn)行了大量研究，Zhang和 Huan[20]認(rèn)為現(xiàn)有加權(quán)貝葉斯模型很少同時關(guān)注屬性值的水平粒度和類標(biāo)簽的垂直粒度，提出一種新的細(xì)粒度屬性加權(quán)范式，即類特有屬性值加權(quán)(CAVWNB)；Chen和Webb[21]提出了一種有效的選擇性樸素貝葉斯算法，該算法僅采用部分屬性來構(gòu)造選擇性樸素貝葉斯模型，模型的構(gòu)建方式使得每個模型都是另一個模型的簡單擴展。另外，當(dāng)數(shù)據(jù)特征過多時，往往會出現(xiàn)類別分布不均勻問題，如在金融欺詐檢測、網(wǎng)絡(luò)入侵檢測等領(lǐng)域?？偠灾?，利用貝葉斯分類器在對具有復(fù)雜結(jié)構(gòu)的數(shù)據(jù)進(jìn)行分類時有很好的效果，但同時也還有很大的提升空間。

2.2 人工神經(jīng)網(wǎng)絡(luò)算法

人工神經(jīng)網(wǎng)絡(luò)是一種以神經(jīng)元為基本計算單元的計算模型，神經(jīng)元之間的信息交換是通過突觸完成的。目前尖峰神經(jīng)網(wǎng)絡(luò)的監(jiān)督學(xué)習(xí)是一個重要的研究領(lǐng)域。學(xué)者們對尖峰神經(jīng)網(wǎng)絡(luò)的監(jiān)督學(xué)習(xí)進(jìn)行了大量的研究，并取得了一定的成果。尖峰神經(jīng)網(wǎng)絡(luò)被證明是處理時空信息的合適工具。然而，由于尖峰神經(jīng)網(wǎng)絡(luò)具有復(fù)雜的不連續(xù)和隱式非線性機制，因此高效的尖峰神經(jīng)網(wǎng)絡(luò)監(jiān)督學(xué)習(xí)算法的制定十分困難，已成為該領(lǐng)域研究的一個重要問題。Lin[22]提出了一種新的多層尖峰神經(jīng)網(wǎng)絡(luò)有監(jiān)督的多尖峰學(xué)習(xí)算法，該算法首先通過定義內(nèi)積算子來對脈沖序列進(jìn)行數(shù)學(xué)描述和操縱，從而解決了學(xué)習(xí)過程中多個輸出脈沖之間的誤差函數(shù)構(gòu)造和反向傳播問題，實現(xiàn)了尖峰序列復(fù)雜的時空模式學(xué)習(xí)。Patino和Alberto[23]證明了在神經(jīng)形態(tài)硬件上實現(xiàn)MNIST和基于事件的NMNIST數(shù)字識別數(shù)據(jù)集的最新模型是可能的，通過這種方法對尖峰神經(jīng)元網(wǎng)絡(luò)有效編碼時空信息的能力有了新的認(rèn)識。但是現(xiàn)有的研究對神經(jīng)元網(wǎng)絡(luò)產(chǎn)生時空活動序列的機制仍不清楚。模型有的需要人工在隨機網(wǎng)絡(luò)中嵌入前饋網(wǎng)絡(luò)，有的需要監(jiān)督學(xué)習(xí)來訓(xùn)練網(wǎng)絡(luò)的連通性以生成序列，并沒有獲得生物學(xué)支持。

2.3 統(tǒng)計學(xué)習(xí)理論

統(tǒng)計學(xué)習(xí)理論和其他理論差別在于使用了統(tǒng)計方法，關(guān)于這類理論使用最廣泛的算法是近似實現(xiàn)結(jié)構(gòu)化風(fēng)險最小化的支持向量機(SVM)。目前支持向量機已經(jīng)成功地應(yīng)用到不同領(lǐng)域的分類和回歸問題。如果未標(biāo)記樣本的數(shù)量遠(yuǎn)遠(yuǎn)大于標(biāo)記樣本的數(shù)量，SVM分類器的分類性能可能會較差。在帶標(biāo)記樣本較少或未帶標(biāo)記樣本過多的情況下，SVM分類器使用受到限制。為了擴展支持向量機的適用性，Li提出了一種引入邊緣分布的魯棒轉(zhuǎn)換支持向量機(RTSVM)，將一階統(tǒng)計量(margin mean)和二階統(tǒng)計量(margin variance)正則化為TSVM，以獲得較強的泛化性能[24]。相比于人工神經(jīng)網(wǎng)絡(luò)，支持向量機的核函數(shù)不容易確定，且靈活性和擴展性也更差[25]。

2.4 決策樹

決策樹是二叉樹或者非二叉樹的樹形結(jié)構(gòu)，由根節(jié)點、內(nèi)部節(jié)點和葉節(jié)點三種元素組成。決策樹根據(jù)層層推進(jìn)的方式獲得決策結(jié)果，在這個過程中特征值的選擇尤為重要，特征值的選擇直接影響分類器的分類效果，通常樣本的屬性有很多種，不同屬性對分類結(jié)果的影響大小不同，需要篩選出與樣本相關(guān)度高的屬性特征。決策樹有三種常用算法[26]，ID算法最早引入了信息論方法中熵的概念，把每個分裂屬性當(dāng)作根節(jié)點來對度量信息增量，選擇信息量最高的屬性。但I(xiàn)D算法沒有考慮到缺失值的情況和連續(xù)特征情況，在ID算法的基礎(chǔ)上，C4.5算法是對ID算法的優(yōu)化，對連續(xù)特征離散化，在某些特征缺失的情況下劃分屬性。ID算法和C4.5算法都存在過度擬合問題，CART算法采用減枝方法避免過度擬合，采用構(gòu)建二叉樹方法取代非二叉樹方法提高搜索效率。相比于其他算法決策樹算法具有簡單的結(jié)構(gòu)層次更容易理解和操作，且直觀性較強能夠進(jìn)行可視化分析，能夠處理不相關(guān)的特征，但容易忽略屬性之間的相互關(guān)聯(lián)性。

3 基于復(fù)雜網(wǎng)絡(luò)監(jiān)督學(xué)習(xí)方法的發(fā)展方向

在基于復(fù)雜網(wǎng)絡(luò)監(jiān)督學(xué)習(xí)方法中，讓計算機對訓(xùn)練的數(shù)據(jù)和標(biāo)簽進(jìn)行建模，來預(yù)測輸入新數(shù)據(jù)的標(biāo)簽。監(jiān)督學(xué)習(xí)方法利用訓(xùn)練數(shù)據(jù)及標(biāo)簽，往往能取得很好的預(yù)測結(jié)果。這種對標(biāo)簽分類方法實踐中被廣泛應(yīng)用，比如章成志[27]把學(xué)術(shù)論文全文作為研究對象，對論文中的研究方法進(jìn)行分類，為科研工作者推薦合適的研究方法。

另一種基于復(fù)雜網(wǎng)絡(luò)監(jiān)督學(xué)習(xí)方法的分類方式是關(guān)系分類，關(guān)系分類認(rèn)為數(shù)據(jù)之間是非獨立的，數(shù)據(jù)的標(biāo)簽不僅依賴于本身的屬性還依賴于鄰域數(shù)據(jù)的標(biāo)簽。鏈接預(yù)測就是預(yù)測網(wǎng)絡(luò)中沒有連邊的兩個節(jié)點在未來某個時間是否會產(chǎn)生連接。鏈接預(yù)測的研究分為基于網(wǎng)絡(luò)拓?fù)涞暮突趯W(xué)習(xí)的兩種方法。近些年來隨著人工智能的快速發(fā)展，后者成為了機器學(xué)習(xí)領(lǐng)域的新興研究方向。這種基于機器學(xué)習(xí)的鏈路預(yù)測可以應(yīng)用于解決多個領(lǐng)域問題。比如在社交平臺預(yù)測社交網(wǎng)絡(luò)中可能的好友、在科研合作網(wǎng)絡(luò)中對專家合作的預(yù)測[28]；在生物領(lǐng)域預(yù)測蛋白質(zhì)之間是否會發(fā)生相互作用，預(yù)防和研究人類疾病[29]；在電子商務(wù)網(wǎng)站學(xué)習(xí)消費者過去的購買特征預(yù)測未來消費行為，推薦可能購買的商品[30]。

基于機器學(xué)習(xí)的鏈接預(yù)測方法首先需要從網(wǎng)絡(luò)中得到各個節(jié)點的特征向量，然后將節(jié)點的特征向量作為機器學(xué)習(xí)算法特征值的輸入。Jalili[31]考慮一個由Twitter(微博服務(wù))和Foursquare(基于位置的社交網(wǎng)絡(luò))組成的多路網(wǎng)絡(luò)，分別用樸素貝葉斯分類器、支持向量機分類器和近鄰分類器來分類，開發(fā)了一種基于元路徑的算法來預(yù)測鏈接。Yuan和He[32]提出了一種新的基于圖核的鏈路預(yù)測方法，通過簽名社交網(wǎng)絡(luò)的結(jié)構(gòu)信息比較用戶相似度，最后利用用戶相似度信息訓(xùn)練SVM分類器來預(yù)測鏈接。Wang和Lv[33]提出了一種有效預(yù)測藥物-蛋白相互作用(DPIs)的方法，基于藥物-蛋白相互作用(DPI)局部結(jié)構(gòu)相似性(DLS)的鏈接預(yù)測方法來預(yù)測藥物-蛋白相互作用，將鏈路預(yù)測和二值網(wǎng)絡(luò)結(jié)構(gòu)相結(jié)合。

以上對于監(jiān)督學(xué)習(xí)的鏈路預(yù)測都是基于靜態(tài)網(wǎng)絡(luò)，近些年來動態(tài)網(wǎng)絡(luò)中的鏈路預(yù)測在實際應(yīng)用中的重要價值日益凸顯，因而受到學(xué)者越來越多的關(guān)注。Chen[34]提出了一種新的鏈路預(yù)測方法，該方法首先表示了動態(tài)網(wǎng)絡(luò)中結(jié)構(gòu)性質(zhì)的變化，然后，為每個屬性訓(xùn)練一個分類器。最后利用所有分類器的集成結(jié)果進(jìn)行鏈路預(yù)測。實驗表明網(wǎng)絡(luò)的演化信息有利于鏈路預(yù)測性能的提高。Ma[35]提出了一種新的圖正則非負(fù)矩陣分解算法(GrNMF)，用于不破壞動態(tài)網(wǎng)絡(luò)的時間鏈路預(yù)測問題。為了獲得每個網(wǎng)絡(luò)從1到的特征，GrNMF通過將剩余網(wǎng)絡(luò)設(shè)置為正則化，對與網(wǎng)絡(luò)相關(guān)的矩陣進(jìn)行分解，為表征時間鏈路的拓?fù)湫畔⑻峁┝烁玫姆椒āang[36]將動態(tài)網(wǎng)絡(luò)轉(zhuǎn)換為靜態(tài)圖像序列，并將時間鏈路預(yù)測作為條件圖像生成問題，提出了一種新的深度生成框架，它利用深度學(xué)習(xí)技術(shù)同時對動態(tài)網(wǎng)絡(luò)中的時空特征建模。由于現(xiàn)實網(wǎng)絡(luò)中節(jié)點通常含有多類異構(gòu)信息，在鏈接預(yù)測中加入更多異質(zhì)性信息，將是一個重要的發(fā)展方向。

4 基于復(fù)雜網(wǎng)絡(luò)監(jiān)督學(xué)習(xí)方法的局限性

4.1 訓(xùn)練數(shù)據(jù)的選擇

使用監(jiān)督學(xué)習(xí)方法對標(biāo)記數(shù)據(jù)進(jìn)行訓(xùn)練得到訓(xùn)練網(wǎng)絡(luò)，再利用這個訓(xùn)練網(wǎng)絡(luò)對標(biāo)簽未知的測試樣本進(jìn)行預(yù)測。因此訓(xùn)練數(shù)據(jù)是否適當(dāng)，就直接影響到輸出結(jié)果的準(zhǔn)確性。通常使用的誤差估計方法是K倍交叉檢驗。當(dāng)我們在對不同的模型進(jìn)行選擇時，往往選擇誤差結(jié)果最小的模型，但事實上K倍交叉檢驗的結(jié)果也是有一定偏差的。因為交叉檢驗所使用的訓(xùn)練樣本是有重疊的，表明模型并不是相互獨立的，相關(guān)變量總體方差隨著協(xié)方差的增大而增大。誤差估計的結(jié)果偏差越大，則越有可能出現(xiàn)不匹配識別。Rodriguez-Vidal和Gonzalo[37]在社交網(wǎng)絡(luò)中對影響者使用的領(lǐng)域特定詞匯進(jìn)行語言建模，研究發(fā)現(xiàn)訓(xùn)練數(shù)據(jù)集的可用性是在任務(wù)中獲得競爭結(jié)果的關(guān)鍵。

4.2 對比分析

獲得訓(xùn)練函數(shù)過程中對訓(xùn)練數(shù)據(jù)的過度擬合，正如在回歸分析中的過度擬合問題一樣。為了能完美擬合樣本集，引入過多的變量，雖然分類器在訓(xùn)練數(shù)據(jù)中表現(xiàn)良好，但在對未知數(shù)據(jù)進(jìn)行測驗以驗證其泛化能力的效果卻不佳，并且隨著數(shù)據(jù)量的增大，預(yù)測效果進(jìn)一步減弱。加入大量的變量，雖然可以在訓(xùn)練集中完美擬合，在實踐中可能就會表現(xiàn)極差。

4.3 性能和效率問題

在監(jiān)督學(xué)習(xí)中，性能解決的問題是如何開發(fā)機器學(xué)習(xí)算法來實現(xiàn)對訓(xùn)練集之外的樣本的最優(yōu)性能。監(jiān)督學(xué)習(xí)系統(tǒng)的性能特征是其泛化誤差，它測量的是訓(xùn)練模型的輸出函數(shù)和潛在目標(biāo)函數(shù)之間的距離。大多數(shù)現(xiàn)有的監(jiān)督學(xué)習(xí)訓(xùn)練方法都存在模式識別的固有問題：偏差和方差困境。例如：一個神經(jīng)網(wǎng)絡(luò)太大，它可能會過度擬合一個特定的訓(xùn)練集合從而不能保持良好的泛化誤差。然而，一個小的神經(jīng)網(wǎng)絡(luò)可能足以近似一個最優(yōu)解。此外，一個重要的算法問題是如何處理一個可能有許多局部極小值的復(fù)雜優(yōu)化問題。效率處理的是監(jiān)督學(xué)習(xí)在空間和訓(xùn)練時間上的復(fù)雜性。機器學(xué)習(xí)的大小可以通過空間復(fù)雜度來表征，空間復(fù)雜度與自由參數(shù)的數(shù)量有關(guān)(例如，神經(jīng)網(wǎng)絡(luò)的權(quán)值的數(shù)量)。學(xué)習(xí)時間可以用時間復(fù)雜度來表征，時間復(fù)雜度是一種相對于特征向量維數(shù)的尺度屬性。隨著數(shù)據(jù)項數(shù)量和維數(shù)的增多，計算時間也隨之增加，面臨性能和效率的取舍問題。對于大問題，訓(xùn)練數(shù)據(jù)就會變得很慢，這也制約了它的使用范圍。

5 結(jié)束語

機器學(xué)習(xí)是大勢所趨，也是目前社會關(guān)注的重要領(lǐng)域之一，本文在這個背景下，從復(fù)雜網(wǎng)絡(luò)的視角切入機器學(xué)習(xí)下的監(jiān)督學(xué)習(xí)這一主題。本文梳理了復(fù)雜網(wǎng)絡(luò)的構(gòu)建方法和監(jiān)督學(xué)習(xí)的概念，通過歸納總結(jié)現(xiàn)有基于復(fù)雜網(wǎng)絡(luò)監(jiān)督學(xué)習(xí)分類算法，闡明了算法原理及發(fā)展現(xiàn)狀，提出了基于復(fù)雜網(wǎng)絡(luò)監(jiān)督學(xué)習(xí)的鏈接預(yù)測是重要的發(fā)展方向，最后剖析了目前基于復(fù)雜網(wǎng)絡(luò)監(jiān)督學(xué)習(xí)算法的局限性，為下一步的研究工作提供參考?；趶?fù)雜網(wǎng)絡(luò)監(jiān)督學(xué)習(xí)算法的研究剛剛起步，有很多的問題需要深入系統(tǒng)的研究。