應(yīng)用于非精確圖匹配的改進DF 模型

李智杰，伊志林，李昌華，張 頡

西安建筑科技大學(xué) 信息與控制工程學(xué)院，西安 710055

圖（graph）在眾多的科學(xué)領(lǐng)域及工程領(lǐng)域（如計算機、醫(yī)學(xué)、生物、化學(xué)、建筑等）具有廣泛的應(yīng)用。作為數(shù)據(jù)的一種表示形式，能夠描述現(xiàn)實世界中復(fù)雜的結(jié)構(gòu)數(shù)據(jù)，如化合物集合、蛋白質(zhì)結(jié)構(gòu)、社交網(wǎng)絡(luò)等，圖強大而復(fù)雜的信息表達能力吸引了諸多學(xué)者的深入探索。

圖匹配主要分為精確圖匹配與非精確圖匹配，其算法層出不窮。圖匹配問題已被證明是一個非確定性多項式（nondeterministic polynomially，NP）問題，相對比之下非精確圖匹配允許算法在一定范圍內(nèi)的容錯匹配機制得到了學(xué)者的廣泛關(guān)注，如圖嵌入方法、基于約束松弛的方法、圖核等諸多的非精確圖匹配的方法被研究學(xué)者應(yīng)用到圖上，不同程度上為非精確圖匹配算法在領(lǐng)域內(nèi)發(fā)展作出重要貢獻。目前傳統(tǒng)算法在準確率以及有效性等方面難以滿足越來越多領(lǐng)域的應(yīng)用需求。

深度森林（deep forest，DF）是當前深度學(xué)習(xí)下的新框架，能夠?qū)Σ煌I(lǐng)域中存在的問題提供高效而便捷的解決方案。深度森林相對于現(xiàn)有的神經(jīng)網(wǎng)絡(luò)具有對超參敏感性小，在數(shù)據(jù)集的規(guī)模上適應(yīng)范圍大，同等條件下模型收斂速度快且高效等優(yōu)點。利用DeepForest 實現(xiàn)非精確圖匹配算法旨在提高目標的分類識別率與精度，從而解決應(yīng)用研究的需求不足問題。在深度學(xué)習(xí)研究領(lǐng)域中，文獻[6]首次提出了DeepForest 學(xué)習(xí)模型，模型包含多粒度掃描和級聯(lián)森林兩部分，分別承擔(dān)不同的責(zé)任角色。其中多粒度掃描的功能與文獻[14]提出的基于移動塊搜索的特征選擇隨機森林方法的思想不謀而合，在一定程度上提升了樣本的多樣性以及完整性，但是從圖結(jié)構(gòu)信息的整體關(guān)聯(lián)性與對局部信息增強的角度上分析，不能較好地表達圖結(jié)構(gòu)信息。對于與非精確圖匹配算法的結(jié)合，文獻[15]針對級聯(lián)森林深處的決策樹的精確概率模型，以實際研究的需求為目標進行了相應(yīng)的改良或變化，利用Dirichlet 模型的區(qū)間值概率替代精確的概率類分布，提出了非精確圖匹配的分類模型。文獻[16-18]針對決策樹葉節(jié)點的不同影響因素致使模型精度下降的問題，提出了采用權(quán)重方式的不同解決方案。雖然實際問題描述不同，但是問題的目標均為提高模型分類的準確性，采取權(quán)值規(guī)則方式增強模型的分類效果，提高訓(xùn)練效率與準確性。

上述方法雖然在不同角度對模型進行了局部改良或優(yōu)化，但在非精確圖匹配應(yīng)用上，由于圖結(jié)構(gòu)信息語義復(fù)雜的特點以及模型結(jié)構(gòu)自身等因素導(dǎo)致識別率上的差異。為充分利用深度學(xué)習(xí)高效、快速的優(yōu)勢，本文在DeepForest 模型的基礎(chǔ)上改良多粒度掃描算法，同時結(jié)合定義的權(quán)值策略規(guī)則，提出一種改進DF模型（improved DeepForest，IDF），并將其應(yīng)用于非精確圖匹配，達到提升圖匹配識別率與精度的目的。文獻[6]中的DeepForest在文中稱為原生深度森林（DF）。

1 IDF 模型

IDF 模型整體框架主要分為復(fù)合多粒度掃描與加權(quán)級聯(lián)森林兩個模塊。復(fù)合多粒度模塊在多粒度模塊的基礎(chǔ)上結(jié)合隨機采樣的方式對模塊的采樣進行改進優(yōu)化；加權(quán)級聯(lián)森林則定義了集中決策時的權(quán)值規(guī)則，決策過程中不斷降低影響因子小的決策枝對結(jié)果的貢獻值。

1.1 復(fù)合多粒度掃描

復(fù)合多粒度掃描主要是對高維數(shù)據(jù)進行特征提取。針對圖數(shù)據(jù)結(jié)構(gòu)的復(fù)雜性與節(jié)點間的信息交互傳遞的特性，單一滑動窗口獲取的樣本在樣本整體的擬合優(yōu)勢上存在欠缺。按照隨機的原則，即保證總體中每一個對象都有已知的、非零的概率被選入作為研究的對象，保證樣本的代表性，結(jié)合隨機窗口采樣可以彌補樣本特征集的擬合優(yōu)度與多樣性。

設(shè)長度為的一維特征向量，使用長度為的窗口進行滑動掃描且每次滑動步距為1 個單位，產(chǎn)生(-+1)個具有維特征向量的數(shù)據(jù)子集F。每次窗口滑動同時隨機捕獲相同維度的特征向量數(shù)據(jù)子集F，進而將兩者合并構(gòu)成(-+1)個具有2維特征向量的數(shù)據(jù)子集G，如式（1）所示。

同理，對于一個×的二維數(shù)據(jù)采取相同的方式獲取樣本的特征向量數(shù)據(jù)子集，將兩者復(fù)合構(gòu)成新的維度特征向量的數(shù)據(jù)子集，并作為級聯(lián)森林的輸入。整個復(fù)合多粒度掃描算法和結(jié)構(gòu)如算法1 和圖1 所示。

復(fù)合多粒度掃描算法

圖1 復(fù)合多粒度掃描Fig.1 Compound multi-grained scanning

算法1 的時間復(fù)雜度雖然仍維持為()，但由于隨機窗口采樣的隨機選擇性，在移動掃描的同時對樣本的局部或整體給予關(guān)注。對于作為級聯(lián)模塊的輸入數(shù)據(jù)，相較單一滑動窗口的數(shù)據(jù)采樣，并非所有特征的特征屬性都對其分類研究有真同等重要的地位，復(fù)合采樣構(gòu)成的特征數(shù)據(jù)子集體現(xiàn)了樣本的擬合優(yōu)度，彌補了在特征分類上的不足。

1.2 加權(quán)級聯(lián)森林

加權(quán)級聯(lián)森林作為整個模型的另一核心模塊，以復(fù)合多粒度掃描模塊處理的數(shù)據(jù)特征子集為輸入，以模型最終的分類結(jié)果為輸出，對模塊底層內(nèi)的決策樹采取權(quán)值策略規(guī)則，降低決策樹因等權(quán)決策機制對結(jié)果產(chǎn)生的決策差異，提高模型的分類準確率。在本模塊內(nèi)單層森林的具體結(jié)構(gòu)如圖2 所示。

式中，為數(shù)據(jù)集的標簽分類數(shù)，p表示數(shù)據(jù)被第棵樹分為第類的概率。

圖2 單層級聯(lián)森林概率分布Fig.2 Probability distribution of single-level cascade forest

定義函數(shù)max()用于計算概率矩陣中列向量的最大概率分量值，即

根據(jù)圖2定義決策樹的迭代權(quán)值規(guī)則，在式（3）中：

（1）當max()所對應(yīng)分量值的列下標與數(shù)據(jù)集的真實映射分類標志相同時，?。?/p>

（2）其余情況則?。?/p>

其中，p為概率分布中列下標與數(shù)據(jù)集的真實映射分類相同的概率分量；表示當前層當前森林的第棵樹。即：

由式（6）得到單層森林的權(quán)重概率和為：

當結(jié)果不滿足模型設(shè)定的閾值時，由式(6)計算出本層森林決策樹的權(quán)重值，對比上一層的權(quán)重值，降低訓(xùn)練過程中精度不準確的決策樹對決策結(jié)果的權(quán)重比例，取min(,)作為當前森林中決策樹的權(quán)重賦值函數(shù)，繼續(xù)深入擴展直至滿足模型設(shè)定的閾值時停止，輸出最終的分類結(jié)果。

加權(quán)級聯(lián)森林算法

圖2 以及算法2 結(jié)合圖匹配算法以提升準確率為目標，雖然算法的時間復(fù)雜度維持為(×)，但采用權(quán)值策略規(guī)則對級聯(lián)森林底層的決策樹賦權(quán)優(yōu)化，加速了模型在迭代過程中的收斂速度。通過加權(quán)方式降低了森林中各子樹在迭代過程中被逐級放大的決策差異與模型結(jié)構(gòu)的深度，提升了模型在圖匹配算法應(yīng)用上的性能。

IDF 算法

算法3 描述了IDF 算法在非精確圖匹配上的訓(xùn)練與預(yù)測過程，其中步驟5 調(diào)用算法1 對實驗數(shù)據(jù)進行復(fù)合多粒度掃描，而步驟7 調(diào)用算法2 對模型進行訓(xùn)練。算法3 雖然在時間復(fù)雜度上沒有發(fā)生變化，但是算法整體上既兼顧圖結(jié)構(gòu)信息特點，又在圖匹配算法上的分類準確率及擴展級上體現(xiàn)其優(yōu)勢。

2 實驗與分析

在實驗部分中，為方便比較模型的實驗效果，采取控制單一變量原則構(gòu)建了實驗所涉及到的對比模型：復(fù)合多粒度深度森林（compound multi-grained deep forest，CMDF）模型和加權(quán)級聯(lián)深度森林（weighted cascade deep forest，WCDF）模型。其模型的具體結(jié)構(gòu)關(guān)系如圖3 所示。

為驗證模型在非精確圖匹配上的實際效果，對多個不同的標準數(shù)據(jù)集進行了訓(xùn)練和測試。對比實驗中所使用的具體模型結(jié)構(gòu)詳見圖3，針對不同模型分別做了三組對比實驗，測試時選取每個數(shù)據(jù)集中的80%數(shù)據(jù)用于訓(xùn)練，20%的數(shù)據(jù)則用于測試。

實驗中的評價指標主要為實驗數(shù)據(jù)的分類準確率，其中在IDF 算法的對比中增加了擴展級數(shù)的評價指標，繪制實驗圖表以及采用平均值的方式對不同算法的實驗結(jié)果列表對比。

圖3 模型結(jié)構(gòu)關(guān)系Fig.3 Relationship of model structure

2.1 實驗數(shù)據(jù)集

實驗中采用的標準數(shù)據(jù)集信息如表1 所示。

表1 數(shù)據(jù)集信息Table 1 Information of dataset

2.2 實驗結(jié)果與分析

為驗證復(fù)合多粒度掃描算法，與文獻[6]中的DF模型進行對比實驗。實驗參數(shù)采用文獻[6]中的參數(shù)列表，模型評價以準確率為指標，圖的橫軸表示實驗次數(shù)，縱軸表示實驗的準確率，實驗結(jié)果如圖4 所示。

實驗結(jié)果表明，復(fù)合多粒度深度森林的平均準確率為MUTAG-92.2%、PTC-72.1%、COX2-91.8%，略高于DF 的MUTAG-91.7%、PTC-71.3%、COX2-90.7%。究其原因，對于圖結(jié)構(gòu)數(shù)據(jù)，采用隨機窗口融合移動掃描窗口的取樣方式，在一定程度上既關(guān)注了圖結(jié)構(gòu)的整體信息，也對局部信息給予加強，增加了樣本的擬合優(yōu)度與多樣性，提升了模型的分類性能。

為驗證加權(quán)級聯(lián)森林算法，與文獻[6]中的DF 模型進行對比。圖的橫軸表示實驗次數(shù)，縱軸表示實驗的準確率，實驗結(jié)果如圖5 所示。

圖5 中，在MUTAG、PTC、COX2 數(shù)據(jù)集的實驗結(jié)果顯示，加權(quán)級聯(lián)深度森林的準確率曲線位于DF之上，平均準確率分別為93.1%vs91.7%(MUTAG)、72.5%vs71.3%(PTC)、91.8%vs90.7%(COX2)。究其原因，圖的復(fù)雜結(jié)構(gòu)特征在經(jīng)過加權(quán)級聯(lián)森林的決策樹分類時，利用算法2 的權(quán)值策略規(guī)則在迭代過程中不斷降低分類效果差的決策樹對分類結(jié)果的貢獻，以此達到提高模型分類準確率的目的。

圖4 復(fù)合多粒度深度森林準確率Fig.4 Accuracy of compound multi-grained deep forest

圖5 加權(quán)級聯(lián)深度森林準確率Fig.5 Accuracy of weighted cascade deep forest

圖6 三個數(shù)據(jù)集上兩種算法的準確率Fig.6 Accuracy of two algorithms on three datasets

為驗證IDF 算法的整體分類效果，實驗分別采用在數(shù)據(jù)集上的準確率與級聯(lián)結(jié)構(gòu)所生成的擴展級數(shù)作為評價指標。擴展層級的對比實驗采用傳統(tǒng)深度學(xué)習(xí)的棧式自動編碼機（stacked autoencoder，SAE），圖的橫軸表示實驗次數(shù)，縱軸表示實驗的準確率，具體實驗數(shù)據(jù)如圖6 及表2 所示。

表2 深度模型層數(shù)Table 2 The number of layers in depth model

由圖4～圖6及文獻[12]得到的在不同模型下針對相同數(shù)據(jù)集測試的平均準確率對比結(jié)果如表3 所示。

表3 數(shù)據(jù)集的平均準確率Table 3 Average accuracy of dataset

結(jié)合圖6、表2、表3 可以得到在數(shù)據(jù)集MUTAG、PTC、COX2 上，IDF 模型取得的平均準確率分別為94.5%、73.7%、94.1%，相較于現(xiàn)有的DF 算法，部分優(yōu)化的CMDF、WCDF 算法，以及結(jié)合神經(jīng)網(wǎng)絡(luò)的BCNNS 算法，實驗結(jié)果有明顯的提升。相較于傳統(tǒng)的深度學(xué)習(xí)方法，深度森林減少了超參數(shù)的同時，對不同規(guī)模的數(shù)據(jù)適應(yīng)性強，能夠迅速收斂，提升算法的效率及準確性。對于改進的模型，IDF較DF算法在擴展層數(shù)的圖上略顯優(yōu)勢，降低了1至2個單位的擴展層數(shù)。

現(xiàn)有的DF算法相較于神經(jīng)網(wǎng)絡(luò)算法，避免了數(shù)據(jù)規(guī)模小的困窘，同樣的參數(shù)下模型迅速得到極佳的性能。IDF算法在原先深度學(xué)習(xí)的優(yōu)勢下，繼承了CMDF算法通過隨機窗口對圖結(jié)構(gòu)數(shù)據(jù)在局部與全局的關(guān)注，以及WCDF算法利用權(quán)值加速模型收斂減小決策誤差的優(yōu)勢，實現(xiàn)了IDF算法整體上的性能提升。

3 結(jié)束語

深度森林是一種基于樹的集成學(xué)習(xí)方法，它通過對樹構(gòu)成的森林進行集成并串聯(lián)以達到讓分類器進行表征學(xué)習(xí)的目的，能夠在同樣的超參條件下迅速達到極佳的性能。IDF 模型針對圖數(shù)據(jù)的結(jié)構(gòu)復(fù)雜、節(jié)點間信息交互的特點，通過復(fù)合多粒度掃描增強了樣本特征的擬合優(yōu)度與多樣性，結(jié)合加權(quán)級聯(lián)森林的權(quán)值策略規(guī)則對各子樹間的差異給予充分的重視，在一定程度上降低了模型的復(fù)雜度且提高了模型分類準確率。相對于DF，實驗表明IDF 模型在用于非精確圖匹配算法上取得了較好的分類效果。但在掃描選取特征的合理性校檢存在不足，在特征的重要程度上如何從重而輕選取，后期會針對相應(yīng)的問題進一步開展研究。