袁 源, 郭進利

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

0 引言

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

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

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

1 理論基礎

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

1.1 復雜網(wǎng)絡的構建

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

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

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

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

s:X×X→IS?R

(1)

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

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

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

d:X×X→Id?R

(2)

假設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ù)，可以進行數(shù)值運算。本文給出了幾個常用的定量數(shù)據(jù)相似性和距離測量公式[14]。

1.1.3 網(wǎng)絡構建技術

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

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

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

1.2 監(jiān)督學習的理論基礎

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

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

2 監(jiān)督學習的主要算法

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

2.1 貝葉斯算法

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

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

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

2.3 統(tǒng)計學習理論

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

2.4 決策樹

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

3 基于復雜網(wǎng)絡監(jiān)督學習方法的發(fā)展方向

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

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

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

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

4 基于復雜網(wǎng)絡監(jiān)督學習方法的局限性

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

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

4.2 對比分析

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

4.3 性能和效率問題

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

5 結束語

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