基于改进萤火虫群优化的多示例学习算法

2019-05-17陈涛董紫君

现代计算机 2019年10期

陈涛，董紫君

（1.深圳职业技术学院教育技术与信息中心，深圳 518055；2.深圳职业技术学院建筑与环境工程学院，深圳 518055）

0 引言

多示例学习是一种新的机器学习框架。它被Dietterichet 等人[1]在对麝香分子活性研究中提出。在多示例学习中，它的训练集由一些具有标签的包组成，包有标签信息；每个包中含有若干个示例，示例是没有标签信息的。假若一个包中有一个示例为正，那么该包能被标记为正包；当包中所有的示例都为负时，这个包才被标记为负包。通过对训练集的学习，构造出学习系统，使用这个系统对测试集数据的包标签进行预测[2]。

在多示例学习算法研究中，代表性算法有多样性密度（DD）算法[3]、ED-DD 算法[4]等。DD 算法是 Maron等人提出，通过在特征空间中寻找一个目标概念点，这个概念点与所有正包中至少有一个示例距离最近、同时远离所有负包中的示例。找到目标点后，把测试集包与该点之间距离是否大于一阈值来判定包的标签。为了获取到目标函数的最大值，DD 算法将所有正包中的每个示例作为一次搜索的初始点，使用梯度上升法，在示例空间中进行搜索，一次搜索找到一个极值点。最后通过比较这些极值点，得到全局最大值。缺点是需要多次搜索示例特征空间，计算耗时较长[5]。EM-DD算法是结合期望最大值算法和多样性密度函数，在每个包中，使用估计对包的标签起决定作用的示例代表包，将多示例转换为单示例，来降低寻优复杂度。

人工萤火虫群优化算法是一种融合人工智能技术与仿生物学的群智能算法。群智能优化算法是模拟自然界中生物的群体行为，并用数学定义的方法。Krishnanand 和Ghose 根据萤火虫的发出萤光素特性和相互吸引的行为，提出人工萤火虫群算法[6]。它把空间上的各点看作为一个萤火虫，利用萤光素强度较高的萤火虫吸引萤光素强度较弱的萤火虫的特点，在萤光素较弱的萤火虫向萤光素较强的萤火虫移动的迭代过程中，找到最优位置点，完成寻优过程。该算法获得全局最优解的概率较高,能较好地克服局部最优解问题，是一种有效的优化算法，在许多领域得到较好应用，已成为众多学者研究的热点[7]。

1 基于改进萤火虫群优化的多示例学习算法

1.1 构造出多示例学习的目标优化函数

多样性密度算法（DD）是O. Maron 和 T. Lozanoperez 等人提出，是多示例学习的一个目标优化函数。它通过在示例特征空间中找到一个概念点，使得每个正包中至少有一个示例离该点最近，而负包中的示例均远离该点。找到该点，把这个点作为参照点，来判断新包的标签。设目标概念点t 代表DD 函数值最大的点，通过最大化目标函数Pr(x=t|B1+,B+2,…,B+l+,,…,)确定点t。假设各包之间相互独立，根据贝叶斯判定理论，点t 能被下式确定：

上式中，B+i代表第i 个正包，B+ij代表第i 个正包第j 个示例；B-i代表第i 个负包，B-ij代表第i 个负包第 j个示例，L 是训练集。在求解时，公式（1）中乘积项能被转换成：

概率Pr(t|Bij)被看作示例为目标概念点概率，由概念点t 与示例Bij之间的距离得出：

为了避免掉入局部最优值，保证找到全局最大值，所有正包中的每个正示例作为一个初始值点，执行一次寻优过程，最后比较局部极值点，得到函数最大值。由于DD 算法需要多次使用梯度上升法搜索特征空间，所以求解最大值过程是非常耗时的，不利于在图像检索的应用，需要采用优化算法来求解最大值。

1.2 使用改进的人工萤火虫群算法寻找函数最优值

人工萤火虫群算法[7]来源于对自然界中萤火虫发光求偶、觅食等行为研究，是一种群智能算法。它利用萤火虫发出萤光素来诱导、吸引伴侣或猎物，发出的萤光素越明亮、越炽热，代表越有吸引力，萤光素值低的萤火虫向萤光素值高的萤火虫移动。萤光素值对应适应函数的值。萤火虫在动态决策邻域内寻找萤光素值高的萤火虫。人工萤火虫群算法被描述以下4 个公式描述：

上述公式，公式（2）是萤光素的t 次迭代更新，ρ 是衰减因子，γ 是强化系数，J(xi(t))是位置xi的适应度值。公式（3）是萤火虫 i 移动到 j 的概率，j ∈Ni(t) ，Ni(t) 是萤火虫 i 的邻域：li(t)

在基本GSO 算法的位置x 迭代计算中，会出现在具有亮萤光素的萤火虫位置处停滞现象，它将延迟算法的收敛，增加耗时。为了避免这个现象，本文提出在具有亮萤光素的萤火虫附近扰动的改进算法：

RGSO 算法描述如下：

（1）初始化萤火虫数 n 和位置，置常量 ρ, γ, β,nt,s,l0,rs的数值；

（2）由公式（2），更新每个萤火虫的萤光素值；

（3）由公式（3），计算每个萤火虫移动概率，得出移动概率最大值的萤火虫j；

（4）由公式（4），更新每个萤火虫的位置；

（5）由公式（5），更新每个萤火虫的决策邻域；

（6）由公式（6），在萤火虫局部极值位置处扰动；

（7）如果满足收敛条件，则退出迭代，否则跳至步骤（2）处，循环执行；

（8）输出具有最亮萤光素的萤火虫位置，也就是求解的目标概念点。

1.3 应用到图像检索

首先将每幅图像分割成若干个区域，每个区域析取出一个9 维的区域特征[8]，将图像和区域分别看作为多示例学习中的包和示例，这样，将图像检索问题转换到多示例学习框架下处理。

RGSOMIL 算法流程图，见图1 所示。

RGSOMIL 算法描述如下：

输入：一组检索图像L={(I1,y1),...,(I|L|,y|L|)}，|L|是检索图像数。

输出：从图像库中，返回相似度概率排前k 幅图像。

图1 RGSOMIL算法流程图

（1）用户提交一组检索图像（含正类图像和负类图像，正类与负类图像数相同）。

（2）将每幅图像分割成若干个区域，每个区域析取出一个9 维的区域特征。将图像和区域分别看作为多示例学习中的包和示例，构造多示例学习优化函数。

（3）使用改进的萤火虫群优化算法RGSO，求解得特征向量空间中的最优解，即目标概念点。

（4）计算图像库中图像与目标概念点之间的距离，作为该图像与检索图像的相似度成绩。排名前k 幅图像被作为检索结果返回给用户。

2 实验结果与分析

实验中使用的图像数据库为Corel 2000 图像库，它来自 http://www.cs.olemiss.edu/～ychen/ddsvm.html。它从Corel 图像库中抽取2000 幅图像，分属20 个类别，每类100 幅图像，有非洲土著居民、历史建筑、大象、海滩、公共汽车、花、滑雪、战舰等20 类。实验时，选择其中一类图像作为正类，其他类别图像作为负类，正负类的选择图像数相同，为各3 幅。根据Krishnanand 和 Ghose 的分析[6]和实验数据集，RGSO 算法中的参数设置为：ρ=0.4,γ=0.6, β=0.08,nt=5,s=0.1,l0=5,rs=3。适应函数J( )是多示例学习中的DD 函数。初始化前，先对示例特征归一化预处理。所有示例向量被初始化作为n 个萤火虫位置。

图2 是本文方法在检索“滑雪”类别图像的一次检索结果，返回相似度概率排前20 幅的图像，检索精确率达90%，方法取得较好的检索结果。

图2 一个检索“滑雪”类别图像结果

为了估算RGSOMIL 方法的检索效率，做了一组检索耗时实验。检索耗时是指从用户提交检索图像开始，到返回排前k 幅的图像之间时间。实验平台为Intel Core i5-4570 CPU 3.2GHz，3.2GHz 和内存 8GB。将RGSOMIL 与DD 方法进行比较，计算耗时见表1。

表1 计算耗时（秒）

从表1 看出，本文提出的GSOMIL 方法计算耗时为3.3 秒，相较DD 方法大大减少，仅为DD 方法的1/3左右。因为：DD 方法需要一一将所有正包的正示例作为初始点，通过梯度上升法，来寻找函数极值点，最后选取具有最大值的极值点作为目标概念点，这个计算过程耗时较长。而RGSOMIL 通过改进的人工萤火虫群优化算法，能快速收敛，找到DD 函数最大值，减少耗时。