基于改進螢火蟲群優化的多示例學習算法

陳濤，董紫君

（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 函數最大值，減少耗時。

3 結語

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