最优路径森林算法原理及其相关反馈应用

李宏林 朱建彬 徐梦迪

(1.泉州医学高等专科学校,福建 泉州 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包含的训练样本仅被手动或自动标记为与检索样本相关或非相关两类。基于用户对检索内容的每次评估结果，系统将反馈给用户一组再检索结果与一组再评估对象，两组对象的选择应符合以下要求：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算法部署在服装搭配等对主观评价需求较高的研究领域，以进一步提升用户满意度。