最優路徑森林算法原理及其相關反饋應用

李宏林 朱建彬 徐夢迪

(1.泉州醫學高等?？茖W校,福建 泉州 362000;2.浙江大學,浙江 杭州 310012)

0 引言

手機應用端的普及與人工智能技術的廣泛應用推動了網絡大數據時代的迅猛發展；在電商、物流、教育等領域，機器分類技術被廣泛部署于信息檢索與模式識別等研究方向，相關反饋技術則進一步改善了人機交流模式和理解機制，兩者的融合應用有助于進一步提升信息分類、檢索準確率與用戶滿意度：通過機器分類提供首次檢索結果，運用人機交互反饋進一步縮小高層語義概念與低層機器特征之間的理解偏差。

相對于傳統分類算法，最優路徑森林(OPF,Optimum-path forest)算法可同時在分類精度與速度上達到較高性能[1-3]，被廣泛部署于機器分類與相關反饋等工業及科研領域[4-6]。沈龍鳳等[4]描述了OPF算法原理并羅列其在國際領域的多項應用，但僅限于算法流程[3]及相關應用文獻的摘要翻譯。本文以圖文方式剖析OPF算法細節，展示其在服裝檢索與人臉生成領域的相關反饋實例應用，為國內同行復現該算法并部署在不同應用領域提供有益借鑒。

1 相關研究

基于機器學習的分類技術被廣泛應用于數據挖掘、計算機視覺、語音識別、自然語言處理等多個領域，代表性技術主要有線性與邏輯回歸、決策樹、貝葉斯、神經網絡、遺傳算子、支持向量機[7]以及深度學習算法等。人機交互技術通過改善人與計算機的交流溝通模式進而提升人機協同工作效率，在優化用戶體驗、離線數據采集與實時信息反饋等方面有廣泛應用，主要有基于硬件的設備優化(如虛擬現實與增強現實)與基于軟件的操作界面與算法優化(如可視化應用)兩大研究方向，基于主動學習的相關反饋技術被證明可以有效提高圖像檢索效果[8]。

OPF算法是由Papa等人提出并經過多次更新優化[1-3]的一種基于完全圖的半監督分類算法，孫挺和耿國華提出的GL-OPF算法[9]進一步提升了基于內容的圖像檢索系統性能，國外多個科研與工業領域將OPF算法部署于智能分類等應用[4]，李宏林等[5]采用基于OPF算法的相關反饋方法優化服裝檢索結果，許彩娥等[6]運用OPF算法改善人臉檢索結果并優化以最優人臉特征點為條件參數的生成式競爭網絡。相較于其他機器分類與交互反饋算法而言，OPF算法具有精度高、實時響應快、初始標記訓練樣本需求不大及可迭代自優化等優點。

2 算法原理與流程剖析

OPF是由一群最優路徑樹OPT(Optimum-path tree)組成，每棵OPT代表一個分類器，樹上每個節點均歸類于根節點所屬類別；相鄰節點之間的連接弧權值由兩者的距離值表征，權值越大，兩個節點的相似度越低；每條路徑首尾節點的相似度由其所包含的各連接弧中的最大權重值而非總和值表征，即通過相鄰節點的相似度傳遞而非累加獲得；每個待分類樣本有且僅與OPF中的某棵OPT的根節點基于最小代價值直接或間接連接，并被歸類到該根節點所屬類別；OPF算法包含了訓練構建與分類反饋兩個階段，并可迭代自優化。

2.1 訓練構建

首先將候選數據庫視為訓練數據集并轉化為某種形式的特征向量集，基于某種距離度量指標建立相應的特征空間；用戶對空間內的初始給定樣本進行類別標記，最終該特征空間包含以下三類樣本：經用戶評估的歸屬于某個類別的根節點、非根節點以及后續基于距離自動歸類的非根節點。OPF算法包含一個初始化階段與三個主循環階段[3]。

2.1.1 OPF構建步驟

(1)基于用戶評估的節點構建完全圖并建立該圖的最小生成樹MST(Minimum Spanning Tree)，如圖1(A)至(B)所示。

(2)當該MST的某連接弧兩端節點分屬不同類別，則斷開該連接弧，并將這兩端節點分別定義為分屬不同類別的兩棵OPT的根節點，如圖1(C)所示。由于某個根節點在斷開連接弧之前可能與多個屬于其他類別的根節點相連，因此特征空間中可能存在不同OPT對應同一類別的現象。

(3)計算特征空間中其余未經用戶評估的節點至每個根節點的所有可能直接或間接路徑的距離，將每個未評估節點基于最小距離路徑連接到相應根節點完成對應OPT的構建，所有OPT構成了OPF，如圖1(F)、(H)、(I)與(K)所示。

圖1 OPF構建及算法流程圖

2.1.2 OPF算法流程

(1)初始化階段：①定義特征空間的所有S個根節點為S及其代價值均為0，定義特征空間的所有M個非根節點為Rj(j=1,2,...,S)∈R及其代價值均為正無窮；②以最小堆數據結構建立一個空的優先級隊列P。

(2)第一階段主循環：①將所有Rj送入隊列P，如圖1(D)所示；②從P出隊當前代價值最小的Rj，計算所有Ti到該Rj的直接連接路徑的代價值，替換原有的正無窮初始值；③基于代價值以最小堆數據結構將所有Ti依次送入P，如圖1(E)所示。此階段結束后,P內包含S-1個Rj與M個Ti。

(3)第二階段主循環：①再次出隊當前代價值最小的Rj，計算每個Ti到該Rj的直接連接路徑代價值，若新代價值低于原代價值，則更新代價值并將Ti基于最小堆數據結構重新入隊；②循環執行該步驟S-2次，最終所有Ti都有且僅與一個Rj以最小代價值直接連接。此階段結束后P內僅剩M個Ti，如圖1(G)所示。

(4)第三階段主循環：①出隊當前代價值最小的Ti(根據多連接弧路徑取最大值原理，該Ti必然位于所有可能連接路徑中的最小路徑上)，計算隊列中其余Tk(k≠i)∈T通過該出隊節點連接到其所在路徑的Rj的代價值，若該代價值低于原代價值，則更新代價值并將相應Tk基于最小堆數據結構重新入隊；②循環執行上一步驟M-1次直至隊列為空，最終所有Ti都有且僅與一個Rj以最小代價值直接或間接連接。最終結果如圖1(K)所示。

2.2 分類反饋

分類精度高與對初始標記訓練樣本數量需求不大兩項優點使得OPF在機器分類領域具有實際推廣價值，實時響應快與可迭代自優化特點則令其可部署于相關反饋領域。

2.2.1 機器分類

與最近鄰分類算法原理不同，對于待分類節點而言，OPF算法是基于其至各棵OPT根節點距離的最小值或類別平均值而非其所在區域鄰近節點所屬類別比例實現分類，待分類節點被分類后可進一步擴充優化OPF，具體步驟如下：

(1)計算待分類節點到特征空間中OPF的每棵OPT的根節點的所有可能直接或間接連接距離。

(2)記錄該節點到每棵OPT根節點的最小距離值，按實際情況基于以下兩種方案分類：A.將其沿最小距離路徑連接到相應根節點，進而歸類至該根節點所屬類別；此方案適用于OPT數量較少的情況。B.對其連接至每項類別的同一類別的所有根節點的最小距離值取平均，將其分配到平均值最小的類別上，并沿最小距離路徑連接到該類別的對應根節點上；此方案適用于OPT數量較多的情況。

2.2.2 相關反饋

在相關反饋應用中，OPF包含的訓練樣本僅被手動或自動標記為與檢索樣本相關或非相關兩類?；谟脩魧z索內容的每次評估結果，系統將反饋給用戶一組再檢索結果與一組再評估對象，兩組對象的選擇應符合以下要求：A.再檢索結果應盡可能逼近用戶理想需求，因此必然從相關類中選擇；B.再評估對象應與用戶理想需求有一定差距但不能偏離過大，若從非相關類中選擇，則可能由于樣本差異顯著而難以獲得正例樣本，因此本文的再評估對象將選擇相關類中與相關類根節點差異最大的樣本；C.由于特征空間中存在非相關類根節點，僅基于與相關類根節點的距離來評判樣本是否具有強相關性是不足的(因為可能存在與相關類及非相關類根節點都很近的相關類節點)。

基于以上分析，在2.1.2節的定義基礎上，進一步定義相關類根節點為Um(m=1,2,...,L)以及非相關類根節點為Vn(n=1,2,...,S-L)，其中Um∈R且≠Vn，反之亦然；定義相關類非根節點為Tp(p=1,2,...，Q,Q

(1)基于用戶對給定對象或首次檢索內容的評估結果按照2.1.1節所述建立OPF。

(2)運用公式(1)計算每個Tp的非相關值。

(3)將指定個數的具有最大和最小非相關值的Tp反饋給用戶，分別作為再評估對象與再檢索結果。

(4)用戶若對再檢索結果不滿意，則繼續對再評估對象進行標記，系統基于標記內容重新構建OPF，重復步驟(2)至(4)，直至用戶滿意。

(1)

2.3 迭代自優化

OPF可通過分類或交互反饋實現迭代自優化。局部自優化是指將待分類樣本依次納入訓練樣本集，使其被分類后成為相應OPT的一部分進而迭代更新分類器；全局自優化是指在訓練樣本總數不變的情況下，基于每次交互反饋信息的評估結果重構OPF；兩種優化方式的下一次分類或評估的結果均受上一次結果的影響，因此屬于迭代自優化。與需要大量標記訓練集的監督分類算法不同，OPF算法僅需少量用戶標注的訓練樣本即可初始化分類器組，進而基于最小路徑將其他未標記訓練樣本自動連接到對應分類器上實現該分類器組的構造。實驗表明，OPF算法可以通過交互反饋實現迭代自優化，并在有限次數內趨于穩定[5-6]。需要注意的是，后續納入的訓練樣本僅能優化分類器性能而不能改變分類器數量，分類器數量僅受初始標記樣本數量的影響。

3 交互反饋應用

本節通過分析OPF算法在服裝檢索與人臉生成兩個實例上的應用，進一步展示其運行機制與實際效果。

3.1 服裝檢索應用

李宏林等[5]利用基于OPF的相關反饋去迭代優化服裝檢索結果，如圖2所示(該圖展示僅包含兩類且只有兩棵最優路徑樹的特殊情況)，具體步驟如下：

圖2 基于OPF的服裝檢索交互反饋

(1)將待檢索服裝圖像與候選數據庫圖像轉化為基于Saliency map &Sift方法抽取的特征向量，找出特征空間中與待檢索圖像在歐式距離上最接近的五張圖像作為首次檢索結果。

(2)用戶對首次檢索結果進行評估，根據評估結果建立OPF。

(3)系統基于OPF算法按照公式(1)將非相關值最低和最高的相似圖像各5張，分別作為再檢索結果與再評估對象反饋給用戶。

(4)若用戶對再檢索結果滿意則終止交互反饋，否則重復步驟(2)至(4)，直至用戶滿意。

實驗結果表明，OPF算法能在5次迭代內顯著提升用戶對檢索結果的滿意度[5]。

3.2 人像生成應用

許彩娥等[6]采用基于OPF的相關反饋、最優相關點的位移優化、以位移優化點特征向量為條件參數的生成競爭網絡(Generative adversarial network，GAN)及以生成圖像相似度為權值的插值合成四個流程實現相似人像檢索合成，如圖3所示，具體步驟如下：

圖3 基于OPF的條件GAN人像生成交互反饋

(1)在特征空間中基于歐式距離搜索與輸入人像最相似的10張人像。

(2)用戶對檢索結果進行相似與否的二類標注，基于標注結果建立OPF。

(3)根據公式(1)計算并定位非相關值最低的最優特征向量，對其以基于方向、步長及范圍控制的位移方式在特征空間中移動并獲得若干個人像特征向量。

(4)以這些特征向量作為生成競爭網絡的條件參數生成若干張候選圖像，若用戶對候選圖像總體滿意，則可選擇若干張最滿意的放入待插值圖像集合中，否則返回步驟(2)再次評估重置OPF。

(5)用戶對待插值圖像進行相似度標注，根據標注相似度高低賦予待插值圖像不同的權重值，基于權重將待插值圖像在像素級別上進一步合成最終人像，若用戶對最終結果不滿意，仍可回到步驟(2)重復上述操作。

實驗結果表明，基于OPF算法的相關反饋能主動干預并優化基于GAN自動生成的人臉圖像，但紋理細節方面還有待進一步優化[6]。

4 結論

分類精度高、實時響應速度快、初始標記訓練樣本需求數量少及可迭代自優化等優點促使OPF算法能夠在機器分類與人機交互反饋等科研與工業領域得到進一步推廣。本文基于圖文描述直觀剖析OPF算法原理與實現流程，有助于科研工作者更好地復現該算法并部署在相應領域。通過近年來OPF算法在服裝檢索與人臉生成的兩個實例應用，進一步論證了其在人機交互反饋方面的可行性與實用性。未來可把OPF算法部署在服裝搭配等對主觀評價需求較高的研究領域，以進一步提升用戶滿意度。