基于改進螢火蟲群優(yōu)化的多示例學習算法

陳濤，董紫君

（1.深圳職業(yè)技術學院教育技術與信息中心，深圳 518055；2.深圳職業(yè)技術學院建筑與環(huán)境工程學院，深圳 518055）

0 引言

多示例學習是一種新的機器學習框架。它被Dietterichet 等人[1]在對麝香分子活性研究中提出。在多示例學習中，它的訓練集由一些具有標簽的包組成，包有標簽信息；每個包中含有若干個示例，示例是沒有標簽信息的。假若一個包中有一個示例為正，那么該包能被標記為正包；當包中所有的示例都為負時，這個包才被標記為負包。通過對訓練集的學習，構造出學習系統(tǒng)，使用這個系統(tǒng)對測試集數(shù)據(jù)的包標簽進行預測[2]。

在多示例學習算法研究中，代表性算法有多樣性密度（DD）算法[3]、ED-DD 算法[4]等。DD 算法是 Maron等人提出，通過在特征空間中尋找一個目標概念點，這個概念點與所有正包中至少有一個示例距離最近、同時遠離所有負包中的示例。找到目標點后，把測試集包與該點之間距離是否大于一閾值來判定包的標簽。為了獲取到目標函數(shù)的最大值，DD 算法將所有正包中的每個示例作為一次搜索的初始點，使用梯度上升法，在示例空間中進行搜索，一次搜索找到一個極值點。最后通過比較這些極值點，得到全局最大值。缺點是需要多次搜索示例特征空間，計算耗時較長[5]。EM-DD算法是結合期望最大值算法和多樣性密度函數(shù)，在每個包中，使用估計對包的標簽起決定作用的示例代表包，將多示例轉換為單示例，來降低尋優(yōu)復雜度。

人工螢火蟲群優(yōu)化算法是一種融合人工智能技術與仿生物學的群智能算法。群智能優(yōu)化算法是模擬自然界中生物的群體行為，并用數(shù)學定義的方法。Krishnanand 和Ghose 根據(jù)螢火蟲的發(fā)出螢光素特性和相互吸引的行為，提出人工螢火蟲群算法[6]。它把空間上的各點看作為一個螢火蟲，利用螢光素強度較高的螢火蟲吸引螢光素強度較弱的螢火蟲的特點，在螢光素較弱的螢火蟲向螢光素較強的螢火蟲移動的迭代過程中，找到最優(yōu)位置點，完成尋優(yōu)過程。該算法獲得全局最優(yōu)解的概率較高,能較好地克服局部最優(yōu)解問題，是一種有效的優(yōu)化算法，在許多領域得到較好應用，已成為眾多學者研究的熱點[7]。

1 基于改進螢火蟲群優(yōu)化的多示例學習算法

1.1 構造出多示例學習的目標優(yōu)化函數(shù)

多樣性密度算法（DD）是O. Maron 和 T. Lozanoperez 等人提出，是多示例學習的一個目標優(yōu)化函數(shù)。它通過在示例特征空間中找到一個概念點，使得每個正包中至少有一個示例離該點最近，而負包中的示例均遠離該點。找到該點，把這個點作為參照點，來判斷新包的標簽。設目標概念點t 代表DD 函數(shù)值最大的點，通過最大化目標函數(shù)Pr(x=t|B1+,B+2,…,B+l+,,…,)確定點t。假設各包之間相互獨立，根據(jù)貝葉斯判定理論，點t 能被下式確定：

上式中，B+i代表第i 個正包，B+ij代表第i 個正包第j 個示例；B-i代表第i 個負包，B-ij代表第i 個負包第 j個示例，L 是訓練集。在求解時，公式（1）中乘積項能被轉換成：

概率Pr(t|Bij)被看作示例為目標概念點概率，由概念點t 與示例Bij之間的距離得出：

為了避免掉入局部最優(yōu)值，保證找到全局最大值，所有正包中的每個正示例作為一個初始值點，執(zhí)行一次尋優(yōu)過程，最后比較局部極值點，得到函數(shù)最大值。由于DD 算法需要多次使用梯度上升法搜索特征空間，所以求解最大值過程是非常耗時的，不利于在圖像檢索的應用，需要采用優(yōu)化算法來求解最大值。

1.2 使用改進的人工螢火蟲群算法尋找函數(shù)最優(yōu)值

人工螢火蟲群算法[7]來源于對自然界中螢火蟲發(fā)光求偶、覓食等行為研究，是一種群智能算法。它利用螢火蟲發(fā)出螢光素來誘導、吸引伴侶或獵物，發(fā)出的螢光素越明亮、越熾熱，代表越有吸引力，螢光素值低的螢火蟲向螢光素值高的螢火蟲移動。螢光素值對應適應函數(shù)的值。螢火蟲在動態(tài)決策鄰域內尋找螢光素值高的螢火蟲。人工螢火蟲群算法被描述以下4 個公式描述：

上述公式，公式（2）是螢光素的t 次迭代更新，ρ 是衰減因子，γ 是強化系數(shù)，J(xi(t))是位置xi的適應度值。公式（3）是螢火蟲 i 移動到 j 的概率，j ∈Ni(t) ，Ni(t) 是 螢 火 蟲 i 的 鄰 域 ：li(t)

在基本GSO 算法的位置x 迭代計算中，會出現(xiàn)在具有亮螢光素的螢火蟲位置處停滯現(xiàn)象，它將延遲算法的收斂，增加耗時。為了避免這個現(xiàn)象，本文提出在具有亮螢光素的螢火蟲附近擾動的改進算法：

RGSO 算法描述如下：

（1）初始化螢火蟲數(shù) n 和位置，置常量 ρ, γ, β,nt,s,l0,rs的數(shù)值；

（2）由公式（2），更新每個螢火蟲的螢光素值；

（3）由公式（3），計算每個螢火蟲移動概率，得出移動概率最大值的螢火蟲j；

（4）由公式（4），更新每個螢火蟲的位置；

（5）由公式（5），更新每個螢火蟲的決策鄰域；

（6）由公式（6），在螢火蟲局部極值位置處擾動；

（7）如果滿足收斂條件，則退出迭代，否則跳至步驟（2）處，循環(huán)執(zhí)行；

（8）輸出具有最亮螢光素的螢火蟲位置，也就是求解的目標概念點。

1.3 應用到圖像檢索

首先將每幅圖像分割成若干個區(qū)域，每個區(qū)域析取出一個9 維的區(qū)域特征[8]，將圖像和區(qū)域分別看作為多示例學習中的包和示例，這樣，將圖像檢索問題轉換到多示例學習框架下處理。

RGSOMIL 算法流程圖，見圖1 所示。

RGSOMIL 算法描述如下：

輸入：一組檢索圖像L={(I1,y1),...,(I|L|,y|L|)}，|L|是檢索圖像數(shù)。

輸出：從圖像庫中，返回相似度概率排前k 幅圖像。

圖1 RGSOMIL算法流程圖

（1）用戶提交一組檢索圖像（含正類圖像和負類圖像，正類與負類圖像數(shù)相同）。

（2）將每幅圖像分割成若干個區(qū)域，每個區(qū)域析取出一個9 維的區(qū)域特征。將圖像和區(qū)域分別看作為多示例學習中的包和示例，構造多示例學習優(yōu)化函數(shù)。

（3）使用改進的螢火蟲群優(yōu)化算法RGSO，求解得特征向量空間中的最優(yōu)解，即目標概念點。

（4）計算圖像庫中圖像與目標概念點之間的距離，作為該圖像與檢索圖像的相似度成績。排名前k 幅圖像被作為檢索結果返回給用戶。

2 實驗結果與分析

實驗中使用的圖像數(shù)據(jù)庫為Corel 2000 圖像庫，它 來 自 http://www.cs.olemiss.edu/～ychen/ddsvm.html。它從Corel 圖像庫中抽取2000 幅圖像，分屬20 個類別，每類100 幅圖像，有非洲土著居民、歷史建筑、大象、海灘、公共汽車、花、滑雪、戰(zhàn)艦等20 類。實驗時，選擇其中一類圖像作為正類，其他類別圖像作為負類，正負類的選擇圖像數(shù)相同，為各3 幅。根據(jù)Krishnanand 和 Ghose 的分析[6]和實驗數(shù)據(jù)集，RGSO 算法中的參數(shù)設置為：ρ=0.4,γ=0.6, β=0.08,nt=5,s=0.1,l0=5,rs=3。適應函數(shù)J( )是多示例學習中的DD 函數(shù)。初始化前，先對示例特征歸一化預處理。所有示例向量被初始化作為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 方法需要一一將所有正包的正示例作為初始點，通過梯度上升法，來尋找函數(shù)極值點，最后選取具有最大值的極值點作為目標概念點，這個計算過程耗時較長。而RGSOMIL 通過改進的人工螢火蟲群優(yōu)化算法，能快速收斂，找到DD 函數(shù)最大值，減少耗時。

3 結語

本文提出了一個基于改進螢火蟲群優(yōu)化的多示例學習算法RGSOMIL，不依賴初始值點，尋找全局最大值精度高，能快速收斂。在Corel 圖像集上的實驗表明，提出的方法具有較好的檢索性能。此外，我們發(fā)現(xiàn)RGSOMIL 算法在處理高維示例特征時，尋優(yōu)值不夠理想，這將是下一步的研究方向。