張燕

摘要：數(shù)據(jù)挖掘算法現(xiàn)面臨挑戰(zhàn)，這個挑戰(zhàn)就是要處理日益增長的復(fù)雜對象。對于圖數(shù)據(jù)，隨機(jī)游走核是有力的容錯圖匹配方法。由于隨機(jī)游走核的局部定義，它的適用性取決于潛在圖表示的特性。另外通過定義圖實(shí)例的核函數(shù)，數(shù)據(jù)挖掘算法的整個工具變得可用。迄今為止，已經(jīng)提出了基于圖的游走、子樹和循環(huán)的圖核。一般問題在于，這些核要么運(yùn)算量大要么受限于他們的表達(dá)性。我們試著通過定義基于路徑有表達(dá)性的圖核克服這個問題。由于計算圖的所有路徑和最長路徑是NP-難，我們建議基于最短路徑圖核。這些核在多項式時間內(nèi)就可以計算，保持表現(xiàn)力并且仍然是正定的。

關(guān)鍵詞：NP-難；圖核；核方法；隨機(jī)游走核；最短路徑核；正定

中圖分類號：TP391.4 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2013）07-1622-04

1 概述

核方法是統(tǒng)計學(xué)習(xí)理論[18]的流行方法，它在數(shù)據(jù)挖掘上有多種應(yīng)用。核可以完成比如分類這樣的任務(wù)，這些任務(wù)以非線性假設(shè)和很種不同數(shù)據(jù)類型的支撐向量機(jī)、回歸[5]、聚類[1]和主成分分析[19]來完成。

核方法的早期研究幾乎都只處理基于向量描述的輸入數(shù)據(jù)。Haussler[10]第一個定義了在結(jié)構(gòu)對象上用原則性方法設(shè)計核，也就是所謂的R-卷積核。卷積核的基本想法是定義復(fù)合對象子結(jié)構(gòu)正定核并使用在卷積下正定函數(shù)是關(guān)閉的屬性來組合這些核，成為一個復(fù)合對象自身的核函數(shù)。因此，卷積核推斷出復(fù)雜對象相似性來源于他們部件的相似性。將一個串拆分成兩個子串，例如，可以認(rèn)為是一個串的分解。對于串匹配，很多核函數(shù)提出來，大部分核函數(shù)屬于卷積核類。基本理念是將串映射到用串索引坐標(biāo)的特征空間。

近年來，結(jié)構(gòu)對象、圖[14]中節(jié)點(diǎn)和圖的核都已經(jīng)定義了，結(jié)構(gòu)對象比如字符串、樹、傳感器、動力系統(tǒng)。一般說來，圖核是基于經(jīng)由核的圖子結(jié)構(gòu)的比較。為了這個目的已經(jīng)考慮游走[13]、子樹[17]和循環(huán)模式[11]。然而，這些子結(jié)構(gòu)的核要么運(yùn)算量大，有時甚至是NP-難，要么局限于它們的表現(xiàn)力。

現(xiàn)存核方法的不足是因為圖核設(shè)計時的競爭需求：第一，核應(yīng)該是圖相似性的優(yōu)良準(zhǔn)則；第二，它的運(yùn)算應(yīng)可能在多項式時間內(nèi)；第三，核必須是正定的；第四，理想情況下它不僅僅只對圖的一小部分子集適用，對所有圖都應(yīng)適用。現(xiàn)存圖核對這四個目的至少有一個達(dá)不到。這篇文章我們介紹了一類圖核，它是基于圖最短路徑來評價相似性，它在多項式時間內(nèi)也可以計算出，是正定的并且適用于廣泛的圖。

2 現(xiàn)有圖核

在我們回顧現(xiàn)存圖核之前，為了方便論證，我們先規(guī)定圖論中的基本定義。

2.1 初級圖論

圖[G]由節(jié)點(diǎn)（或定點(diǎn)）集[V]和邊[E]組成。在本文中，[n]表示圖的節(jié)點(diǎn)數(shù)，[m]表示圖的邊數(shù)。

屬性圖是節(jié)點(diǎn)和/或邊帶有標(biāo)簽的圖；標(biāo)簽指的是屬性。在例子中，屬性由形如（屬性-名稱，值）的對構(gòu)成。[G]的鄰接矩陣[A]定義如下：

這里[vi]和[vj]是[G]的節(jié)點(diǎn)。圖上長度為[k-1]的步子[w]是節(jié)點(diǎn)[v1，v2，...，vk]的一個序列，[vi-1，vi∈E ]，[ 1

如果[vi≠vi i≠j?i，j∈1，...，k]，[w]就是一個路徑?；蛘?，游走經(jīng)常就看作是路徑，路徑于是命為簡單的、唯一的或無環(huán)的路徑，這有可能會引起困惑。為了澄清余下本文的不同，我們定義路徑是沒有節(jié)點(diǎn)重復(fù)的游走。環(huán)就是[v1=vk]的游走，簡單環(huán)除了[v1]不含有任何重復(fù)節(jié)點(diǎn)。

漢密爾頓路徑是通過圖中每個節(jié)點(diǎn)一次，且恰好一次的路徑。歐拉路徑是通過圖中每條邊，且恰好一次的路徑。

2.2 隨機(jī)游走核

隨機(jī)游走核建立于計算兩個輸入圖匹配游走數(shù)基礎(chǔ)的想法上。[G?rter]及其他人[9]定義了一個講究的方法通過兩個輸入圖[G1=V1，E1]和[G2=V2，E2]的直積圖[G×]來決定所有的匹配游走對：

盡管有清晰的定義，這些隨機(jī)游走核仍具有難點(diǎn)。直積圖可能包含[V1×V2]個節(jié)點(diǎn)。即使它的鄰接矩陣是稀疏的，但它可能通過矩陣的力量變?yōu)闈M的。處理這樣大的滿陣會引起龐大的運(yùn)算時間和內(nèi)存需求。

除了運(yùn)算量問題，輸入圖中小的相同子結(jié)構(gòu)可能會引起高相似度。由于游走允許節(jié)點(diǎn)的重復(fù)，這些圖核會引起“動搖”問題，也就是通過重復(fù)訪問節(jié)點(diǎn)的相同環(huán)，游走可以人工產(chǎn)生高相似值。因此動搖限制了隨機(jī)游走圖核的表達(dá)性。

分析現(xiàn)在的隨機(jī)游走核，很明顯測量部分相似性方法會引起大的積圖。圍繞[G?rter]等人的原始隨機(jī)游走核，已經(jīng)丟失了尋找部分相似性的能力，減少了圖核的表達(dá)性。兩個方法都有動搖問題。

2.3 標(biāo)簽富集及核的重定義

進(jìn)行的步驟改進(jìn)了基于游走圖核的表達(dá)性和有效性。另外，每個圖增加的標(biāo)簽可以減少兩圖匹配節(jié)點(diǎn)數(shù)。這個測量減少了計算它們核值得工作，這是因為要考慮的游走對數(shù)減少了。

基于游走圖核為了避免動搖進(jìn)行了重定義，這樣游走不包含兩節(jié)點(diǎn)構(gòu)成的子環(huán)。然而當(dāng)節(jié)點(diǎn)富集在試驗評價上對分類精度有了積極影響時，同時也阻止兩節(jié)點(diǎn)環(huán)有更大的改進(jìn)。

3 最短路徑圖核

確定所有路徑是NP-難問題，同時找到路徑的特殊子集也不必要。確定圖的最長路徑又是NP-難，這是因為它考慮決定圖是否包含哈密爾頓路徑。然而計算圖的最短路徑在多項式時間內(nèi)可以解決。迪杰斯特拉[4]（從源節(jié)點(diǎn)出發(fā)的最短路徑）和弗洛伊德-沃爾什[6]（所有節(jié)點(diǎn)對）這些杰出算法考慮分別在[Om+n*log n] [7]和[On3]時間內(nèi)確定最短距離。

3.1 弗洛伊德-轉(zhuǎn)換

我們最短路徑核必要的第一步就是講原始圖轉(zhuǎn)換為最短路徑圖。最短路徑圖[S]包含輸入圖[I]的相同節(jié)點(diǎn)集。和輸入圖不同，通過[I]中游走連接的[S]中所有節(jié)點(diǎn)間存在邊。[S]中[vi]和[vj]間每條邊通過這兩個節(jié)點(diǎn)的最短距離來標(biāo)簽。

任何解決所有最短路徑對問題的算法可以用來確定[S]中所有最短距離的邊標(biāo)簽。我們建議用弗洛伊德的算法。這個算法運(yùn)行時間為[On3]，它也適用于有負(fù)邊權(quán)值的圖，但是多數(shù)不包含負(fù)的權(quán)值環(huán)。此外，執(zhí)行起來也很簡單。下面將提到經(jīng)弗洛伊德算法將圖[I]轉(zhuǎn)換到[S]的過程，稱為弗洛伊德轉(zhuǎn)換。

3.2 最短路徑核

繼我們輸入圖的弗洛伊德轉(zhuǎn)換，我們現(xiàn)在可以定義一個最短路徑核。

定義1（最短路徑圖核）[G1]和[G2]是兩個圖，經(jīng)弗洛伊德轉(zhuǎn)換為[S1]和[S1]。接著定義最短路徑圖核[S1=V1，E1]和[S2=V2，E2]為

下面我們證明最短路徑核的有效性。

引理1最短路徑圖核是正定的。

弗洛伊德-沃爾什（n節(jié)點(diǎn)的圖G和鄰接矩陣A）

證明：最短路徑核是運(yùn)行在弗洛伊德轉(zhuǎn)換圖的簡單游走核， 弗洛伊德轉(zhuǎn)換圖只考慮了長度為1的游走。首先，我們選擇一個節(jié)點(diǎn)的正定核和邊的正定核。接著我們定義長度為1的游走對[k1walk]，順著游走碰到的節(jié)點(diǎn)和邊的核結(jié)果。作為一個節(jié)點(diǎn)和邊核的張量結(jié)果，[k1walk]是正定的。接著我們0-擴(kuò)展[k1walk]到游走的整個節(jié)點(diǎn)對，將長度[≠]1的所有游走核值設(shè)為0。這個0-擴(kuò)展維持正定性。最短路徑核的正定性直接就像卷積核[10]一樣，從它的定義證明正定的。

運(yùn)行時間復(fù)雜度 最短路徑核避免了動搖，但是如何與已知的隨機(jī)游走核（測量部分相似性）進(jìn)行運(yùn)行時間復(fù)雜度的比較仍舊是個有趣的問題。

不失其廣義，我們假設(shè)要處理兩個各有[n]個節(jié)點(diǎn)和[m]條邊的圖。為了計算游走核，我們首先要確定直積圖，直積圖的節(jié)點(diǎn)數(shù)明顯上限到[n2]。我們接著要轉(zhuǎn)化這個直積圖的鄰接矩陣；[x?x]矩陣的逆的標(biāo)準(zhǔn)算法要求[Ox3]時間。我們的例子中[x≤n2]，隨機(jī)游走圖核整個的運(yùn)行時間復(fù)雜度為[On6]。

使用弗洛伊德沃爾什算法時最短路徑核要求進(jìn)行在[On3]內(nèi)能完成的弗洛伊德轉(zhuǎn)換。如果原始圖是連通的，轉(zhuǎn)換圖的邊數(shù)是[n2]。雙方轉(zhuǎn)換圖所有邊的成對比較是確定核值所必需的。我們要考慮[n2*n2]邊對，結(jié)果就是整個運(yùn)行時間是[On4]。

有利于游走核，如果兩個因素圖所有節(jié)點(diǎn)貼有同樣地標(biāo)簽，直積圖的節(jié)點(diǎn)數(shù)僅僅是[n2]可能會有爭論。這對基于整個相似性的隨機(jī)游走是成立的，但是基于部分相似性的隨機(jī)游走總會引起有[n2]節(jié)點(diǎn)的積圖。因此，只有測量整個相似性并創(chuàng)建[n43]節(jié)點(diǎn)積圖的隨機(jī)游走核有相同運(yùn)行時間復(fù)雜度。

4 實(shí)驗結(jié)果

4.1 隨機(jī)游走核

在本節(jié)，我們提供一個評估，它用傳統(tǒng)隨機(jī)游走核進(jìn)行評估圖相似性。

實(shí)驗數(shù)據(jù)庫由線圖組成，代表線圖有大寫字母。為了獲得字母噪音樣本集，我們重復(fù)應(yīng)用失真到干凈的字母原型。接著失真的線圖通過代表節(jié)點(diǎn)和邊的線終點(diǎn)轉(zhuǎn)變?yōu)閳D。節(jié)點(diǎn)用相應(yīng)終點(diǎn)的二維坐標(biāo)標(biāo)簽。按照這個程序，我們每150就構(gòu)造一個訓(xùn)練集和驗證集，還有一個750的測試集。數(shù)據(jù)庫由15類字母[（A，E，F(xiàn)，H，I，K，L，M，N，T，V，W，X，Y，Z）]組成。如圖1和2所示。

4.2 最短路徑核

為了評價我們最短路徑圖核的實(shí)際性能，我們選擇從蛋白質(zhì)中選擇分類任務(wù)。540個蛋白質(zhì)，每90個一類，應(yīng)該分為6個不同功能類，這些功能類在10倍的交叉檢驗，單獨(dú)地基于蛋白質(zhì)結(jié)構(gòu)信息。

我們隨機(jī)抽取90個蛋白質(zhì)，將這些蛋白質(zhì)結(jié)構(gòu)轉(zhuǎn)化為圖模型。每個節(jié)點(diǎn)都和它空間中三個最近鄰連通。簡單說，二級結(jié)構(gòu)元素間距離就用它們空間中心的距離計算。邊用它們在埃代表的距離進(jìn)行標(biāo)簽。節(jié)點(diǎn)用代表它們的類型、片層和氨基酸中的長度進(jìn)行標(biāo)簽。

我們在蛋白質(zhì)模型圖上運(yùn)行游走核和最短路徑核，因為計算游走核步子會到無窮大，這就導(dǎo)致內(nèi)存問題，我們粗略估計它步數(shù)達(dá)到k，設(shè)定長步到0的核值。我們在4到6的范圍內(nèi)運(yùn)行k的測試。

[核類型＼&精確度＼&標(biāo)準(zhǔn)偏差＼&最短路徑＼&93.33＼&3.22＼&長度4的游走＼&89.63＼&2.30＼&長度5的游走＼&88.89＼&1.99＼&長度6的游走＼&88.15＼&1.67＼&]

最短路徑核以至少93.33%的精確度勝過所有游走核，540個蛋白質(zhì)上最壞的最短路徑核精度等級明顯高于用長度為4的最好游走核。結(jié)果，考慮最短路徑而不是游走會明顯增加分類的精度。

5 結(jié)束語

我們定義了基于最短路徑的圖核，它在多項式內(nèi)可以計算，是正定的并且保有表達(dá)性，同時避免了“動搖”現(xiàn)象。在分類蛋白質(zhì)圖模型到功能類的實(shí)驗中，它們明顯勝過隨機(jī)游走核。在往后的學(xué)習(xí)中，我們要考慮到圖論和核方法之間的聯(lián)系。

參考文獻(xiàn)：

[1] A. Ben-Hur，D. Horn，H. Siegelmann，V. Vapnik.A support vector method for hierarchical clustering[M]//T. K. Leen，T. G. Dietterich，V. Tresp.editors， Advances in Neural Information Processing Systems 13.MIT Press，2001：367-373..

[2] H. Berman，J. Westbrook，Z. Feng，G. Gilliland，T. Bhat，H. Weissig，I. Shindyalov，P. Bourne. The protein data bank[J].Nucleic Acids Research，2000（28）：235-242.

[3] K. M. Borgwardt，C. S. Ong，S. Schoenauer，S. Vishwanathan，A. Smola，H.-P.Kriegel. Protein function prediction via graph kernel. Bioinformatics，2005. in press.

[4] E. W. Dijkstra.A note on two problems in connection with graphs[J].Numerische Mathematics， 1959（1）：269-271.

[5] H. Drucker，C. J. C. Burges，L. Kaufman，A. Smola，V. Vapnik. Support vector regression machines[M]//M.C.Mozer，M.I.Jordan，T. Petsche，editors.Advances in Neural Information Processing Systems 9，Cambridge，MA，1997：155-161.

[6] R. Floyd.Algorithm 97， shortest path. Comm. ACM， 5：345， 1962.

（下轉(zhuǎn)第1629頁）

（上接第1625頁）

[7] M. L. Fredman，R. E. Tarjan.Fibonacci heaps and their uses in improved network optimization algorithms[J].JACM，1987，34（3）：596–615.

[8] T. G¨artner.Exponential and geometric kernels for graphs.In NIPS*02 workshop on unreal data， volume Principles of modeling nonvectorial data，2002.

[9] T. G¨artner， P. Flach， and S. Wrobel. On graph kernels： Hardness results and efficient alternatives[M]//B. Sch¨olkopf and M.Warmuth， editors， Sixteenth Annual Conference on Computational Learning Theory and Seventh Kernel Workshop， COLT.Springer，2003.

[10] D. Haussler.Convolutional kernels on discrete structures.Technical Report UCSC-CRL-99 - 10， Computer Science Department， UC Santa Cruz，1999.

[11] T. Horvath， T. G¨artner， and S. Wrobel. Cyclic pattern kernels for predictive graph mining. In Proceedings of the International Conference on Knowledge Discovery and Data Mining， 2004.

[12] D. Jungnickel. Graphen， Netzwerke und Algorithmen. BIWiss.- Verlag， Mannheim， Germany， 1994.

[13] H. Kashima， K. Tsuda， and A. Inokuchi. Marginalized kernels between labeled graphs[C].In Proceedings of the 20th International Conference on Machine Learning （ICML），Washington， DC， United States，2003.

[14] R. S. Kondor，J. Lafferty.Diffusion kernels on graphs and other discrete structures[C].In Proceedings of the ICML，2002.

[15] I. Schomburg，A. Chang，C. Ebeling，M. Gremse， C. Heldt， G. Huhn， and D. Schomburg. Brenda， the enzyme database： updates and major new developments. Nucleic Acids Res， 32 Database issue：D431–D433，Jan 2004.

[16] P. Maha，N. Ueda， T.Akutsu， J.-L. Perret， and J.-P. Vert. Extensions of marginalized graph kernels.In Proceedings of the Twenty-First International Conference on Machine Learning， 2004.

[17] J. Ramon and T. G¨artner. Expressivity versus efficiency of graph kernels. Technical report， First International Workshop on Mining Graphs， Trees and Sequences （held with ECML/PKDD03）， 2003.

[18] B. Sch¨olkopf and A. J. Smola.Learning with Kernels[M].MIT Press，2002.

[19] B. Sch¨olkopf， A. J. Smola， and K.-R. M¨uller. Kernel principal component analysis. In B. Sch¨olkopf， C. J. C. Burges， and A. J. Smola， editors， Advances in Kernel Methods-Support Vector Learning， MIT Press，Cambridge， MA，1999：327-352.