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

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

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

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

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

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

1 IDF 模型

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

1.1 復合多粒度掃描

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

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

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

復合多粒度掃描算法

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

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

1.2 加權級聯森林

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

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

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

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

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

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

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

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

由式（6）得到單層森林的權重概率和為：

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

加權級聯森林算法

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

IDF 算法

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

2 實驗與分析

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

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

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

圖3 模型結構關系Fig.3 Relationship of model structure

2.1 實驗數據集

實驗中采用的標準數據集信息如表1 所示。

表1 數據集信息Table 1 Information of dataset

2.2 實驗結果與分析

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

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

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

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

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

圖5 加權級聯深度森林準確率Fig.5 Accuracy of weighted cascade deep forest

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

為驗證IDF 算法的整體分類效果，實驗分別采用在數據集上的準確率與級聯結構所生成的擴展級數作為評價指標。擴展層級的對比實驗采用傳統深度學習的棧式自動編碼機（stacked autoencoder，SAE），圖的橫軸表示實驗次數，縱軸表示實驗的準確率，具體實驗數據如圖6 及表2 所示。

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

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

表3 數據集的平均準確率Table 3 Average accuracy of dataset

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

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

3 結束語

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