基于動(dòng)態(tài)賦權(quán)近鄰傳播的數(shù)據(jù)增量采樣方法*

陳曉琪,謝振平,劉 淵,詹千熠

1(江南大學(xué) 人工智能與計(jì)算機(jī)學(xué)院,江蘇 無錫 214122)

2(江蘇省媒體設(shè)計(jì)與軟件技術(shù)重點(diǎn)實(shí)驗(yàn)室(江南大學(xué)),江蘇 無錫 214122)

現(xiàn)代信息技術(shù)的不斷發(fā)展和進(jìn)步,使各個(gè)領(lǐng)域累計(jì)了大量的數(shù)據(jù),廣泛涉及圖像、文本、音頻以及其他各類非結(jié)構(gòu)化數(shù)據(jù)等.面對(duì)海量規(guī)模增長(zhǎng)的數(shù)據(jù)內(nèi)容,如何更有效地平衡信息獲取的效率和有效性,正成為大數(shù)據(jù)處理的新重要問題.數(shù)據(jù)采樣(data sampling)技術(shù)是一種能夠在一定程度上解決上述問題的手段之一,該技術(shù)考慮從數(shù)據(jù)集中選取有代表性的樣本作為整個(gè)數(shù)據(jù)集合的代表,在減小數(shù)據(jù)規(guī)模的同時(shí),最大可能地保留數(shù)據(jù)集的有用信息,從而精簡(jiǎn)地表達(dá)數(shù)據(jù)集合包涵的重點(diǎn)知識(shí).

當(dāng)前,與數(shù)據(jù)集代表點(diǎn)采樣相關(guān)的研究更多的是圍繞圖像數(shù)據(jù).文獻(xiàn)[1]提出了多字典不變稀疏編碼方法,在不依賴人工標(biāo)記、種子圖像或其他先驗(yàn)知識(shí)的情況下,采集互聯(lián)網(wǎng)上的代表性商標(biāo)圖像,為商標(biāo)識(shí)別、商標(biāo)侵權(quán)檢測(cè)、品牌保護(hù)等領(lǐng)域自動(dòng)提供原型、代表性圖像或弱標(biāo)簽訓(xùn)練圖像.文獻(xiàn)[2]使用圖像位置信息和圖像相關(guān)標(biāo)記,基于上下文和內(nèi)容挖掘與位置和標(biāo)記視覺相關(guān)聯(lián)的圖像,結(jié)合k-means 聚類方法從視覺相關(guān)圖像中選擇代表性圖像,為世界著名標(biāo)志性建筑提供瀏覽摘要.文獻(xiàn)[3]基于情感特征生成圖像摘要,通過概率情感模型提取輸入圖像情感特征,在情感空間中對(duì)圖像做聚類處理,結(jié)合覆蓋性、情感一致性和顯著性對(duì)簇排序并選擇代表性圖像.文獻(xiàn)[4]提出一種區(qū)別于大多數(shù)利用視覺特征系統(tǒng)的基于語義知識(shí)的圖像集合摘要方法,其通過圖像間的語義相似度構(gòu)建語義相關(guān)性網(wǎng)絡(luò),依據(jù)網(wǎng)絡(luò)中心性選擇代表性圖像.文獻(xiàn)[5]將圖像自動(dòng)摘要問題看作稀疏表示的字典學(xué)習(xí)問題,將圖像摘要任務(wù)看作是字典學(xué)習(xí)任務(wù),去實(shí)現(xiàn)大規(guī)模圖像數(shù)據(jù)集的代表性圖像選擇.

現(xiàn)有的代表點(diǎn)采樣方法大多基于聚類[6-9]方法,通?？沙橄鬄? 個(gè)步驟:(1) 用一組特征向量來表示數(shù)據(jù)集中的樣本點(diǎn),數(shù)值類型數(shù)據(jù)應(yīng)用簡(jiǎn)單處理可轉(zhuǎn)化為特征向量,圖像數(shù)據(jù)則根據(jù)自身特點(diǎn)結(jié)合特征提取方法表示為一組高維特征向量;(2) 在特征向量空間中,采用聚類方法將樣本點(diǎn)劃分為若干簇;(3) 利用樣本點(diǎn)代表性排序方法,從簇中選擇具有代表性的樣本.代表點(diǎn)采樣方法可以從數(shù)據(jù)表示、聚類方法和代表點(diǎn)選擇方法這3 個(gè)方面進(jìn)行研究.針對(duì)樣本點(diǎn)聚類和代表點(diǎn)排序,常用的方法是使用AP(affinity propagation)算法[6,7,10,11]進(jìn)行代表點(diǎn)的選擇.與傳統(tǒng)聚類算法相比,AP 算法不需要預(yù)先設(shè)定聚類個(gè)數(shù),對(duì)初始值不敏感,并且其生成的聚類中心是數(shù)據(jù)集中真實(shí)存在的樣本點(diǎn),不僅具有很好的代表性,且可以直接將聚類中心當(dāng)作簇代表點(diǎn).盡管AP 算法在處理許多問題上具有優(yōu)勢(shì),但它一個(gè)較大的不足是算法復(fù)雜度較高,在Frey 等人所做的代表性灰度圖像選擇實(shí)驗(yàn)中[12],運(yùn)行1 次AP 算法所消耗的時(shí)間與運(yùn)行100 次k-center 算法所消耗的時(shí)間基本相同.與K-means 算法相比,AP 算法的時(shí)間復(fù)雜度正比于數(shù)據(jù)規(guī)模的平方,而k-means 算法的時(shí)間消耗則是線性增長(zhǎng).當(dāng)數(shù)據(jù)規(guī)模較大時(shí),AP 算法的計(jì)算時(shí)間將很長(zhǎng),且對(duì)存儲(chǔ)空間要求也呈平方規(guī)模增長(zhǎng),這極大地限制了AP 算法應(yīng)用于大規(guī)模數(shù)據(jù)處理的實(shí)用性.

針對(duì)大規(guī)模數(shù)據(jù)的代表點(diǎn)采樣問題,本文提出了一種基于動(dòng)態(tài)賦權(quán)近鄰傳播的數(shù)據(jù)增量采樣算法ISAP (incremental data sampling using affinity propagation with dynamic weighting).主要包含兩個(gè)策略.

(1) 近鄰傳播偏向參數(shù)的動(dòng)態(tài)賦權(quán).在AP 算法的迭代過程中,利用樣本點(diǎn)單次迭代聚類結(jié)果計(jì)算樣本點(diǎn)自身輪廓系數(shù),對(duì)AP 算法的重要參數(shù)——偏向參數(shù)做動(dòng)態(tài)調(diào)整,使最終采樣結(jié)果能夠包含更多的潛在性樣本;

(2) 引入分層增量處理,將數(shù)據(jù)集劃均勻劃分為規(guī)模適中的子集,在各子集上分別執(zhí)行全局偏向參數(shù)動(dòng)態(tài)賦權(quán)的AP 算法,獲得局部最優(yōu)代表點(diǎn)集合;然后在局部最優(yōu)代表點(diǎn)集合上執(zhí)行局部偏向參數(shù)動(dòng)態(tài)賦權(quán)的AP 算法,推選出整個(gè)數(shù)據(jù)集的最終代表點(diǎn).

相比于現(xiàn)有的主要增量采樣算法[13,14],它們的主要目的在于實(shí)現(xiàn)數(shù)據(jù)密度上的均勻采樣.而ISAP 算法目的在于實(shí)現(xiàn)數(shù)據(jù)空間上基于聚類劃分的代表性樣本獲取.

為檢驗(yàn)ISAP 算法的性能及其在圖像數(shù)據(jù)應(yīng)用問題的價(jià)值,我們分別在人工合成數(shù)據(jù)集、UCI 標(biāo)準(zhǔn)數(shù)據(jù)集和圖像數(shù)據(jù)集上進(jìn)行了代表性樣本采樣任務(wù),對(duì)比一些經(jīng)典的和較新的方法,結(jié)果表明:我們的方法與現(xiàn)有相關(guān)方法在采樣劃分質(zhì)量上處于同一水平,而計(jì)算效率則獲得了大幅提升.進(jìn)一步將新方法應(yīng)用于深度學(xué)習(xí)的數(shù)據(jù)增強(qiáng)任務(wù)中,相應(yīng)的實(shí)驗(yàn)結(jié)果表明:在原始數(shù)據(jù)增強(qiáng)基礎(chǔ)上,結(jié)合進(jìn)高效增量采樣處理后,訓(xùn)練數(shù)據(jù)多樣性增加,在不改變總訓(xùn)練數(shù)據(jù)集規(guī)模的情況下,新方法介入所獲得的模型質(zhì)量可實(shí)現(xiàn)顯著的提升.

本文的主要貢獻(xiàn):

(1) 提出了一種基于動(dòng)態(tài)賦權(quán)近鄰傳播的數(shù)據(jù)增量采樣算法,引入分層增量處理和樣本點(diǎn)動(dòng)態(tài)賦權(quán)策略,良好地實(shí)現(xiàn)了數(shù)據(jù)采樣質(zhì)量和效率的平衡;

(2) 在人工合成數(shù)據(jù)集、UCI 標(biāo)準(zhǔn)數(shù)據(jù)集和圖像數(shù)據(jù)集上進(jìn)行代表性樣本采樣任務(wù),本文方法在提高采樣效率的同時(shí),保證了代表性樣本的顯著性和覆蓋性;

(3) 將本文方法應(yīng)用于深度學(xué)習(xí)的數(shù)據(jù)增強(qiáng)任務(wù)中,實(shí)驗(yàn)結(jié)果表明:在保持訓(xùn)練數(shù)據(jù)集規(guī)模不變的情況下,本文方法介入所獲得的模型質(zhì)量有顯著提升.

本文第1 節(jié)將介紹方法框架.第2 節(jié)、第3 節(jié)介紹標(biāo)準(zhǔn)AP 算法及基于動(dòng)態(tài)賦權(quán)近鄰傳播的數(shù)據(jù)增量采樣算法ISAP.第4 節(jié)對(duì)算法進(jìn)行相關(guān)分析.第5 節(jié)通過實(shí)驗(yàn)評(píng)估算法的效果.第6 節(jié)對(duì)本文進(jìn)行總結(jié),對(duì)未來工作進(jìn)行展望.

1 基于動(dòng)態(tài)賦權(quán)近鄰傳播的數(shù)據(jù)增量采樣方法ISAP 框架

本文提出的基于動(dòng)態(tài)賦權(quán)近鄰傳播的數(shù)據(jù)增量采樣算法框架如圖1 所示,主要包含以下內(nèi)容.

(1) 動(dòng)態(tài)賦權(quán)的AP 算法.本文提出一種用于代表點(diǎn)采樣的動(dòng)態(tài)賦權(quán)AP 算法,在AP 算法的迭代過程中,利用樣本點(diǎn)單次迭代聚類結(jié)果計(jì)算樣本點(diǎn)自身輪廓系數(shù)(silhouette coefficient),對(duì)樣本點(diǎn)的偏向參數(shù)做動(dòng)態(tài)調(diào)整,不斷賦予新的權(quán)值直至方法收斂,使最終采樣結(jié)果能夠包含更多的潛在性樣本;

(2) 分層增量采樣.基于上述偏向參數(shù)動(dòng)態(tài)賦權(quán)算法,結(jié)合整體樣本點(diǎn)的全局初始偏向參數(shù)和局部代表點(diǎn)之間的相對(duì)于整體數(shù)據(jù)集的局部初始偏向參數(shù),提出了分層增量的代表點(diǎn)采樣算法ISAP.算法架構(gòu)如圖1 所示:首先,將樣本集合劃分為規(guī)模上大小均勻的子集,在每個(gè)子集上執(zhí)行全局偏向參數(shù)動(dòng)態(tài)賦權(quán)的AP 算法,得到每個(gè)子集產(chǎn)生的局部代表點(diǎn),所有子集產(chǎn)生的局部代表點(diǎn)組成局部代表點(diǎn)集,本文將該過程稱為增量局部推選層;然后,在局部代表點(diǎn)集上利用動(dòng)態(tài)賦權(quán)AP 算法對(duì)局部代表點(diǎn)進(jìn)行合并,產(chǎn)生數(shù)據(jù)集整體代表點(diǎn),本文將該過程稱為合并推選層;最后,將數(shù)據(jù)集中的非代表點(diǎn)劃分給與其相似度最大的代表點(diǎn),完成全局簇劃分.

Fig.1 Flow chart of proposed incremental data sampling method圖1 本文數(shù)據(jù)增量采樣算法流程圖

2 AP 算法中偏向參數(shù)的動(dòng)態(tài)賦權(quán)

AP 算法[12]是一種exemplar-based 聚類方法,它將所有數(shù)據(jù)樣本看作是網(wǎng)絡(luò)中的節(jié)點(diǎn),通過節(jié)點(diǎn)間的雙向消息傳遞,收斂得到最優(yōu)的簇代表點(diǎn)集合.AP 算法與其他聚類方法的最大不同點(diǎn)是:其生成的聚類中心是數(shù)據(jù)集中真實(shí)存在的樣本,具有很好的代表性,可以直接作為簇的代表點(diǎn).

在基于聚類方法的代表點(diǎn)采樣問題中,聚類質(zhì)量與代表點(diǎn)采樣質(zhì)量緊密相關(guān),聚類質(zhì)量的提升,在一定程度上能夠解決采樣結(jié)果的代表性問題.AP 算法改善聚類質(zhì)量的一個(gè)方向是偏向參數(shù),偏向參數(shù)直接影響最終聚類數(shù)目,決定聚類質(zhì)量的好壞.偏向參數(shù)一般根據(jù)經(jīng)驗(yàn)設(shè)置為統(tǒng)一常數(shù)[12,15,16],在AP 算法的迭代過程中恒定不變,即所有樣本點(diǎn)成為簇代表點(diǎn)的可能性從始至終是一樣的.但是在實(shí)際情況中,樣本點(diǎn)之間的差異使得它們成為簇代表點(diǎn)的可能性不盡相同;此外,在迭代過程中因?yàn)樾畔⒔粨Q的影響,樣本點(diǎn)成為簇代表點(diǎn)的概率是會(huì)變動(dòng)的.因此,給所有樣本點(diǎn)設(shè)置同樣且恒定的偏向參數(shù)的做法并不恰當(dāng),容易導(dǎo)致不好的聚類結(jié)果.為便于后續(xù)討論,表1 中匯總給出了本小節(jié)與新方法有關(guān)的符號(hào)信息.

Table 1 Summary of relevant symbols on chapter 2表1 第2 節(jié)新方法相關(guān)符號(hào)匯總

2.1 初始偏向參數(shù)定義

在實(shí)際問題中,根據(jù)局部密度、語義性等信息可以知道,樣本點(diǎn)成為簇代表點(diǎn)的可能性是有區(qū)別的,所以將偏向參數(shù)P={pk}1×N設(shè)置為統(tǒng)一常數(shù)的做法并不恰當(dāng).

為了充分考慮數(shù)據(jù)本身所蘊(yùn)含的信息,減少信息迭代中不必要的計(jì)算,文獻(xiàn)[17,18]依據(jù)數(shù)據(jù)集中樣本點(diǎn)的分布情況,為每個(gè)樣本賦予不同的初始偏向參數(shù).本文方法僅考慮樣本點(diǎn)在局部范圍內(nèi)與其他樣本之間的平均相似度,不考慮比例系數(shù)的影響,采用如下初始偏向參數(shù)計(jì)算公式:

其中,

?I(·)為指示函數(shù);

? 參數(shù)cutoff表示不等式s(i,k)≥θ的結(jié)果:如果s(i,k)≥θ成立,則I(cutoff)=1;否則為0.

參數(shù)θ定義為相似度截?cái)嘀?其大小的設(shè)置與數(shù)據(jù)集所有樣本點(diǎn)間的相似度緊密程度相關(guān),其在某種程度上也反映了原始距離度量s(·,·)的上限合理尺度.

2.2 偏向參數(shù)動(dòng)態(tài)賦權(quán)

標(biāo)準(zhǔn)AP 算法的輸入是相似度矩陣S={s(i,j)}N×N以及包含在S中的偏向參數(shù)P={pk}1×N(s(k,k)←pk),pk表示樣本點(diǎn)k被選為聚類中心的可能性.對(duì)于N 個(gè)樣本點(diǎn)的聚類問題,AP 算法旨在找到一組聚類中心,將每一個(gè)非中心點(diǎn)分配給唯一的聚類中心,以便最大化非中心點(diǎn)和其聚類中心之間的相似性以及各聚類中心的偏向參數(shù)的總和.一種典型的AP 算法二元變量因子圖[12]如圖2(1)所示.

Fig.2 Factor graph of the AP method圖2 AP 算法二元變量因子圖及其改進(jìn)后的因子圖

在圖2(1)中,{cij}N×N中的cij屬于{0,1},cij=1 表示點(diǎn)j是點(diǎn)i的聚類中心.標(biāo)準(zhǔn)AP 算法需要滿足兩個(gè)聚類約束條件:一個(gè)是聚類中心的唯一性,即一個(gè)點(diǎn)只能屬于一個(gè)類(圖2(1)中約束I);另一個(gè)是聚類中心的存在性,即當(dāng)一個(gè)點(diǎn)是另一個(gè)點(diǎn)的聚類中心時(shí),該點(diǎn)必然是自己的聚類中心(圖2(1)中約束E).基于這兩個(gè)約束,AP 算法通過在因子圖上的信息傳遞更新使得全局函數(shù)S(C)最大,其具體定義見公式(2).

針對(duì)這一NP 難問題,依據(jù)max-sum 算法[12,19]可推導(dǎo)出AP 算法的迭代更新公式.在AP 算法中,有兩種重要的消息在樣本點(diǎn)間傳遞,分別是吸引度(responsibility)和歸屬度(availability),在算法中表現(xiàn)為吸引度矩陣R= {r(i,j)}N×N和歸屬度矩陣A={a(i,j)}N×N,其更新公式如下:

吸引度r(i,j)表示樣本點(diǎn)j作為樣本點(diǎn)i的聚類中心的合適程度,歸屬度a(i,j)表示樣本點(diǎn)i選擇樣本點(diǎn)j作為聚類中心的合適程度.對(duì)于任意的樣本點(diǎn)k,如果其對(duì)于自身的歸屬度a(k,k)和吸引度r(k,k)之和大于0,則樣本點(diǎn)k是一個(gè)聚類中心.

從標(biāo)準(zhǔn)AP 算法的迭代過程和聚類中心選取方法可以看出,偏向參數(shù)P={pk}1×N(s(k,k)←pk)的大小直接影響最終聚類數(shù)目.在大多數(shù)基于AP 過程的算法中,各樣本的pk被設(shè)為同一常數(shù)并且在迭代過程中保持不變.一旦pk被確定,聚類結(jié)果也就被確定下來,過程中沒有其他的方法來對(duì)結(jié)果進(jìn)行修正.為了降低初始pk對(duì)聚類結(jié)果的影響,可以引入額外的信息在聚類過程中動(dòng)態(tài)改變偏向參數(shù).本文考慮引入節(jié)點(diǎn)的輪廓系數(shù)對(duì)每一次迭代產(chǎn)生的中間結(jié)果進(jìn)行評(píng)價(jià),從而依據(jù)評(píng)價(jià)結(jié)果動(dòng)態(tài)改變每個(gè)點(diǎn)的pk.即:當(dāng)AP 算法產(chǎn)生至少一個(gè)聚類中心時(shí),認(rèn)為點(diǎn)與點(diǎn)之間產(chǎn)生了相互作用.依照這一思想,AP 算法的因子圖模型結(jié)構(gòu)將相應(yīng)地發(fā)生變化,在原本的聚類約束條件下,將新增有關(guān)于聚類中心的約束,改變后的因子圖模型及其信息傳遞如圖2(2)所示.新的因子圖新增了聚類約束條件F,該約束表示當(dāng)產(chǎn)生至少一個(gè)聚類中心時(shí),各節(jié)點(diǎn)之間存在相互作用,新增約束公式及改變后的全局函數(shù)S(C)如下:

依據(jù)max-sum 算法,可以從新的全局函數(shù)及信息傳遞過程中[17,20]推導(dǎo)出如下公式:

與公式(2)比較可以發(fā)現(xiàn),新增信息量γik和φik不影響原本吸引度和歸屬度的更新過程.因此,引入額外信息改變pk不會(huì)改變AP 算法的核心公式.

輪廓系數(shù)是確定聚類質(zhì)量的一種常用指標(biāo),通常用來評(píng)價(jià)整體聚類質(zhì)量的好壞,但也可以用來評(píng)估某一個(gè)樣本點(diǎn)簇歸屬的合適程度.假設(shè)數(shù)據(jù)集被劃分為x個(gè)子集{C1,C2,…,Cx},a(i)是子集Ck中的樣本點(diǎn)i到同簇其他樣本點(diǎn)間的平均相似度,b(i,Cj)(i≠j)是樣本點(diǎn)i到子集Cj中所有樣本點(diǎn)的平均相似度.b(i,:)=min{b(i,Cj)}.一個(gè)樣本點(diǎn)的簇歸屬合適程度計(jì)算方法如下:

Silhouette(i)的取值范圍為[-1,1]:越接近1,則樣本點(diǎn)i的簇歸屬越合理;接近-1,說明樣本點(diǎn)i應(yīng)屬于其他簇;為0,則說明樣本點(diǎn)i在兩個(gè)簇的邊界上.

在AP 算法迭代產(chǎn)生聚類中心的情況下,引入對(duì)樣本點(diǎn)的輪廓系數(shù)評(píng)價(jià).參考Silhouette指標(biāo)的結(jié)果可以得知樣本點(diǎn)是否被正確地劃分,以及被選作聚類中心的樣本點(diǎn)是否是正確的聚類中心,從而調(diào)整每個(gè)樣本的偏向參數(shù){pk},動(dòng)態(tài)改變樣本點(diǎn)成為聚類中心的可能性.顯然,聚類中心樣本與非聚類中心樣本在調(diào)整上存在差異,因此給出兩條偏向參數(shù)更新規(guī)則.

規(guī)則1.對(duì)于非聚類中心樣本:Silhouette指標(biāo)大于0,說明該樣本被劃分到正確的簇,其成為聚類中心的可能性應(yīng)該降低,pk應(yīng)適當(dāng)減小;Silhouette指標(biāo)小于0,則該點(diǎn)沒有被劃分到正確的簇,其應(yīng)該被劃分到其他簇或成為一個(gè)新的聚類中心,pk應(yīng)維持不變或適當(dāng)增加.

規(guī)則2.對(duì)于聚類中心樣本:Silhouette指標(biāo)大于0,說明該樣本是正確的聚類中心,pk應(yīng)維持不變或適當(dāng)增加;Silhouette指標(biāo)小于0,說明該點(diǎn)不是正確的聚類中心,pk應(yīng)適當(dāng)減小.

基于上述兩條規(guī)則,為了將Silhouette轉(zhuǎn)化為合適的Δp,定義如下轉(zhuǎn)換函數(shù):

O={ok}1×N存放聚類中心標(biāo)志,如果ok=1,表明樣本點(diǎn)i是聚類中心;否則,ok=-1.參數(shù)δ調(diào)整Δp的變動(dòng)幅度.引入基于Silhouette計(jì)算的Δp,當(dāng)算法產(chǎn)生至少一個(gè)聚類中心后,偏向參數(shù)動(dòng)態(tài)賦權(quán)的AP 算法更新公式如下:

偏向參數(shù)動(dòng)態(tài)調(diào)整的AP 算法在復(fù)雜度上與標(biāo)準(zhǔn)AP 算法沒有差別,但是因?yàn)榭紤]到了樣本點(diǎn)之間的相互作用關(guān)系,使得偏向參數(shù)能夠即時(shí)反映樣本點(diǎn)當(dāng)前迭代時(shí)刻的狀態(tài).對(duì)于基于聚類劃分的采樣問題來說,期望得到的代表點(diǎn)能夠更大程度地覆蓋原始數(shù)據(jù)的空間區(qū)域,包含更多數(shù)據(jù)密度較小區(qū)域的特異性樣本,而引入偏向參數(shù)的動(dòng)態(tài)調(diào)整能夠在一定程度上消除原始數(shù)據(jù)密度分布給初始偏向參數(shù)帶來的影響,從而能夠找到更多低數(shù)據(jù)密度空間區(qū)域中的代表性樣本.引入輪廓系數(shù)動(dòng)態(tài)改變偏向參數(shù)后,算法過程如下.

算法1.adjustPreferenceAP(S,P,λ,δ,maxiter,conviter).

輸入:數(shù)據(jù)集相似度矩陣S={sij}N×N,偏向參數(shù)P={p11,...,pNN},阻尼系數(shù)λ,變動(dòng)幅度δ,最大迭代次數(shù)maxiter,最大收斂狀態(tài)比較次數(shù)conviter;

輸出:聚類中心classcenter.

3 分層增量采樣

AP 算法中,聚類中心為真實(shí)樣本點(diǎn)這一特性,使得其非常適用于代表點(diǎn)的采樣.但是標(biāo)準(zhǔn)AP 算法的復(fù)雜度較高,不適用于大規(guī)模數(shù)據(jù)的代表點(diǎn)采樣.本文結(jié)合分層及增量處理的采樣策略,基于上述偏向參數(shù)的動(dòng)態(tài)賦權(quán)AP 算法,實(shí)現(xiàn)對(duì)數(shù)據(jù)集的高效采樣,以期實(shí)現(xiàn)處理效率和采樣質(zhì)量的更好兼顧.

本文提出的分層增量采樣方法框架如圖1 所示,是一層增量局部推選加一層合并推選的“1+1”模式的采樣.算法的輸入為已劃分好的子集序列,為了保證算法的計(jì)算效率,各子集的規(guī)模要相同或相近,可以采用順序劃分或隨機(jī)采樣劃分的方法.

將數(shù)據(jù)集劃分為規(guī)模適中的子集{D1,D2,…,Dn},分層增量采樣的第1 層(增量局部推選)依次處理樣本子集Di,選出基于全局偏向參數(shù)信息和局部相似度信息的子集代表點(diǎn)Ri={ri1,ri2,…,rix},構(gòu)成子集代表點(diǎn)集R.第2 層 (合并推選)完全基于R的全局信息,即數(shù)據(jù)集的局部信息,從R中挑選出數(shù)據(jù)集的整體代表點(diǎn).

在增量局部推選層中,為了將更多的潛在代表點(diǎn)挑選出來,需要考慮數(shù)據(jù)集的全局相似度信息.因此,將樣本點(diǎn)基于整個(gè)數(shù)據(jù)集中的全局初始偏向參考度作為AP 算法的輸入.依據(jù)公式(1)計(jì)算數(shù)據(jù)集的全局偏向參數(shù)PG={pgkk},每個(gè)子集的全局偏向參數(shù)集合為PGi.

合并推選層采樣是對(duì)增量局部推選層采樣結(jié)果的合并推選.在第1 層中已經(jīng)基于全局偏向參數(shù)獲得了所有潛在的整體代表點(diǎn)組成局部代表點(diǎn)集,在第2 層采樣中,只需基于局部代表點(diǎn)集的全部相似度信息,即整體數(shù)據(jù)集的局部節(jié)點(diǎn)之間的相似度信息進(jìn)行潛在代表點(diǎn)的采樣選擇,其中,仍采用公式(1)初始化其中局部代表點(diǎn)集相對(duì)于整體數(shù)據(jù)集的局部偏向參數(shù)PN={pnkk}.

結(jié)合截?cái)嘀祬?shù)θ的引入,本文方法可考慮對(duì)原始的所有數(shù)據(jù)點(diǎn)間的相似度矩陣進(jìn)行約簡(jiǎn),將小于相似度截?cái)嘀档倪呥M(jìn)行刪除,進(jìn)而達(dá)到約簡(jiǎn)相似度矩陣的目的,加速AP 算法的計(jì)算效率.綜前所述,可歸納給出如下的綜合算法過程.

算法2.ISAP({D1,D2,…,Dn},θ,λ,δ,maxiter,conviter).

輸入:子集序列D1,D2,…,Dn,相似度截?cái)嘀郸?阻尼系數(shù)λ,變動(dòng)幅度δ,最大迭代次數(shù)maxiter,最大收斂狀態(tài)比較次數(shù)conviter;

輸出:代表點(diǎn)集R′,全局劃分Cluster.

選出數(shù)據(jù)集的整體代表點(diǎn)后,如果需要實(shí)現(xiàn)單簇多代表點(diǎn)的選擇,則可依據(jù)最大相似度將非代表點(diǎn)分配給一個(gè)代表點(diǎn),完成基于最大相似度分配的全局簇劃分.然后依據(jù)最終的簇劃分,在每個(gè)簇中選取一組點(diǎn)放入代表點(diǎn)集.

4 算法分析

假設(shè)數(shù)據(jù)集被劃分為K個(gè)規(guī)模為M的子集(K<

在各子集上執(zhí)行AP 算法的空間復(fù)雜度為O(M2),每一次增量推選過程中消耗的存儲(chǔ)空間不變,因此增量執(zhí)行K次規(guī)模為M的AP 算法的空間消耗為s1=O(M2).依照上述設(shè)定,在局部代表點(diǎn)數(shù)為ρ·K·M的情況下,在局部代表點(diǎn)集上執(zhí)行AP 算法的空間消耗為s2=O(ρ2K2M2),因此分層采樣方法的空間復(fù)雜度為O(ρ2K2M2).而標(biāo)準(zhǔn)AP算法的空間復(fù)雜度為O(K2M2).ρ是一個(gè)大于0 且遠(yuǎn)小于1 的數(shù),因此分層增量采樣方法在空間上的消耗同樣優(yōu)于標(biāo)準(zhǔn)AP 算法.分層增量采樣方法在時(shí)間效率和存儲(chǔ)空間方面均可以得到提升.

相比于標(biāo)準(zhǔn)的AP 算法,ISAP 中引入了大規(guī)模數(shù)據(jù)的分層處理策略,在第1 層處理中對(duì)原始數(shù)據(jù)進(jìn)行一次局部約簡(jiǎn)處理后,僅選取部分代表性數(shù)據(jù)參與第2 層的再處理,從理論上看,可能會(huì)造成代表性數(shù)據(jù)對(duì)原始數(shù)據(jù)信息攜帶不足的問題,進(jìn)而導(dǎo)致最終采樣得到的代表性樣本在全局上的偏離問題.雖然如此,結(jié)合我們以前的相關(guān)研究[21,22]發(fā)現(xiàn):在增量學(xué)習(xí)過程中,如果階段性選擇的代表點(diǎn)集能夠構(gòu)成對(duì)目標(biāo)問題解的一個(gè)整體有效的表達(dá),那么在增量過程中逐步篩選掉非代表性樣本,僅基于保留下來的數(shù)據(jù)參與后續(xù)處理的做法,理論上在一定條件下可以達(dá)到與全局方法的一致.

具體到ISAP 算法,考慮在第1 層處理后保留的局部代表性樣本集是在整體上對(duì)原始數(shù)據(jù)空間區(qū)域進(jìn)行代表性表達(dá),而非數(shù)據(jù)密度上的約簡(jiǎn)采樣.這樣,AP 算法自身的特性就顯得非常有優(yōu)勢(shì),不僅可以有效地約簡(jiǎn)冗余數(shù)據(jù),減少計(jì)算量,而且能夠一定程度上解決原始數(shù)據(jù)空間中局部數(shù)據(jù)密度可能存在較大程度不平衡的問題,以使得最終得到的采樣結(jié)果更優(yōu).

5 實(shí)驗(yàn)分析

本文提出的代表點(diǎn)采樣方法基于AP 聚類,為檢驗(yàn)算法有效性,同樣與基于AP 的其他聚類方法進(jìn)行比較,幾種比較方法如下.

(1) 標(biāo)準(zhǔn)AP 算法的代表點(diǎn)采樣:使用文獻(xiàn)[12]提出的標(biāo)準(zhǔn)AP 算法來做代表點(diǎn)選取;

(2) 分層近鄰傳播算法HAP 的代表點(diǎn)采樣:使用文獻(xiàn)[23]提出的一種基于底層推舉和上層推舉的層次AP算法來做代表點(diǎn)選取.該方法同樣采用分層的策略,底層基于標(biāo)準(zhǔn)AP 算法,上層基于自適應(yīng)AP 算法;

(3) 近鄰賦值的增量式AP 聚類算法IAPNA 的代表點(diǎn)采樣:使用文獻(xiàn)[16]提出的一種增量式AP 算法來做代表點(diǎn)選取.該方法通過近鄰賦值構(gòu)建新增數(shù)據(jù)與已有數(shù)據(jù)之間的消息傳遞關(guān)系,增量式地?cái)U(kuò)充吸引度和歸屬度矩陣,直至方法收斂得到結(jié)果.

相關(guān)算法實(shí)驗(yàn)中,首先需要計(jì)算樣本點(diǎn)i和j之間的相似度s(i,j),s(i,j)的值越大,表示兩個(gè)樣本越相近.實(shí)驗(yàn)中,對(duì)兩個(gè)樣本點(diǎn)間的相似度s(i,j)采用歸一化計(jì)算定義:

D={d(i,j)}是樣本點(diǎn)之間的歐式距離矩陣,max 和min 操作分別表示取矩陣元素中的最大值和最小值.上式計(jì)算后,兩個(gè)樣本點(diǎn)完全相同時(shí)的相似度為1,完全不同時(shí)的相似度為0.

實(shí)驗(yàn)中,參考各自算法特點(diǎn)和相關(guān)文獻(xiàn),AP 算法的偏向參數(shù)取相似度矩陣中位值;對(duì)于IAPNA 方法參數(shù)pc,根據(jù)算法輸出簇?cái)?shù)和采樣質(zhì)量選取對(duì)比選取;對(duì)于ISAP 算法中的截?cái)鄥?shù)θ和變動(dòng)幅度參數(shù)δ,一方面也可類似地根據(jù)算法輸出簇?cái)?shù)和采樣質(zhì)量選取對(duì)比選取,其中的采樣質(zhì)量可以是使用有監(jiān)督的交叉驗(yàn)證選取;或者使用無監(jiān)督的質(zhì)量指標(biāo)(如代表點(diǎn)間平均歐式距離)作為參照.

此外,截?cái)鄥?shù)θ一定程度上反映了數(shù)據(jù)點(diǎn)間距離度量合理性的界限范圍,而變動(dòng)幅度參數(shù)δ是從微觀上對(duì)偏向參數(shù)進(jìn)行調(diào)整,解釋樣本點(diǎn)對(duì)于輪廓系數(shù)的學(xué)習(xí)能力.由此,取θ選擇范圍可取[10-2,max(D)],δ選擇范圍可設(shè)定為[10-3,10-1],其中,max(D)同公式(9)中的含義.

5.1 評(píng)價(jià)指標(biāo)

實(shí)驗(yàn)從聚類質(zhì)量、采樣質(zhì)量和方法效率這3 個(gè)方面對(duì)代表點(diǎn)采樣方法進(jìn)行評(píng)價(jià).標(biāo)準(zhǔn)化互信息(normalized mutual information,簡(jiǎn)稱NMI)是廣泛用于聚類質(zhì)量評(píng)估的聚類評(píng)價(jià)指標(biāo),用于度量方法結(jié)果與標(biāo)準(zhǔn)結(jié)果之間的相似度,其定義如下:

其中,N是數(shù)據(jù)樣本總數(shù);CX和CY分別是數(shù)據(jù)集的真實(shí)劃分和算法聚類結(jié)果包含的簇?cái)?shù);Cij表示同時(shí)屬于真實(shí)劃分簇?cái)?shù)i和聚類結(jié)果簇?cái)?shù)j的樣本數(shù)量.NMI的取值范圍為[0,1],其值越大,表示聚類結(jié)果與真實(shí)結(jié)果越匹配.

針對(duì)采樣質(zhì)量,本文引入代表點(diǎn)間平均歐式距離(average euclidean distance of representative points,簡(jiǎn)稱AEDRP)和距離方差(variance of representative points,簡(jiǎn)稱VRP)以及新設(shè)計(jì)綜合覆蓋率(comprehensive coverage rate,簡(jiǎn)稱CCR)來評(píng)價(jià)選取代表點(diǎn)的顯著性和覆蓋性.代表點(diǎn)間平均歐式距離越大,距離方差越小,說明選取的代表點(diǎn)的顯著性越好.綜合覆蓋率考慮反映在合理代表點(diǎn)個(gè)數(shù)下,代表點(diǎn)集對(duì)原始數(shù)據(jù)集的覆蓋程度.值越大,說明選取的代表點(diǎn)的覆蓋性越好.其定義如下:

其中,NR是算法劃分的類數(shù)即代表點(diǎn)數(shù)目,NNR是非代表點(diǎn)數(shù),R和NR分別為代表點(diǎn)集和非代表點(diǎn)集;dist(i,j)是代表點(diǎn)i和非代表點(diǎn)j間的歐式距離,dist(:,j)min是非代表點(diǎn)j與所有代表點(diǎn)之間的最小距離;dmean是整個(gè)數(shù)據(jù)集中數(shù)據(jù)點(diǎn)間的平均歐式距離;I(·)為指示函數(shù).CCR值綜合考慮代表點(diǎn)占原始數(shù)據(jù)大小的比例以及代表點(diǎn)對(duì)數(shù)據(jù)集在一定范圍內(nèi)的覆蓋程度,通常情況下,選取更多數(shù)量的代表點(diǎn)能夠明顯提升代表點(diǎn)對(duì)數(shù)據(jù)集的覆蓋程度.因此,在不考慮選取代表點(diǎn)數(shù)量的情況下去比較代表點(diǎn)對(duì)數(shù)據(jù)集的覆蓋程度是不合理的,所以在評(píng)價(jià)時(shí)引入與代表點(diǎn)數(shù)目相關(guān)的系數(shù),可以更為合理地評(píng)價(jià)代表點(diǎn)對(duì)數(shù)據(jù)集的覆蓋程度.當(dāng)然,在采樣問題中,覆蓋度是更被看重的問題,因此在CCR評(píng)價(jià)指標(biāo)中,代表點(diǎn)數(shù)目的影響權(quán)重較小,代表點(diǎn)對(duì)數(shù)據(jù)集覆蓋程度的影響權(quán)重較大.

5.2 數(shù)值數(shù)據(jù)實(shí)驗(yàn)分析

在3 組UCI 標(biāo)準(zhǔn)數(shù)據(jù)集和4 組人工合成數(shù)據(jù)集上進(jìn)行代表性樣本采樣實(shí)驗(yàn),數(shù)據(jù)集詳情見表2.

Table 2 Descriptions of numerical experimental data sets表2 數(shù)值型實(shí)驗(yàn)數(shù)據(jù)集描述

真實(shí)數(shù)據(jù)集iris,wine,yeast 來源于UCI,人工合成數(shù)據(jù)集Set 1~Set 4 是隨機(jī)生成的二維數(shù)據(jù)集,均符合正態(tài)分布,其樣本分布情況如圖3 所示.對(duì)每個(gè)數(shù)據(jù)集,依據(jù)公式(9)計(jì)算任意數(shù)據(jù)集內(nèi)樣本點(diǎn)間的相似度.4 種算法的AP 阻尼系數(shù)λ設(shè)為0.9,HAP 算法和ISAP 算法的分區(qū)子集大小設(shè)為數(shù)據(jù)規(guī)模的0.2[23],如果子集規(guī)模超過500,則設(shè)為500.采樣選取每個(gè)最終簇的一組數(shù)據(jù)(算法輸出的代表點(diǎn))作為代表點(diǎn).

在實(shí)驗(yàn)過程中,調(diào)整IAPNA 算法參數(shù)pc、ISAP 算法截?cái)鄥?shù)θ和變動(dòng)幅度參數(shù)δ進(jìn)行多次實(shí)驗(yàn).參數(shù)pc在真實(shí)數(shù)據(jù)集上的數(shù)值來源于文獻(xiàn)[16],參數(shù)θ,δ以及人工數(shù)據(jù)集上的pc綜合算法輸出的簇?cái)?shù)和采樣質(zhì)量選取.最終實(shí)驗(yàn)參數(shù)設(shè)置見表3.

Fig.3 Four synthetic data sets圖3 人工合成數(shù)據(jù)集情況

Table 3 Parameter setting for numerical experimental data sets表3 數(shù)值型數(shù)據(jù)實(shí)驗(yàn)算法參數(shù)設(shè)置情況

相應(yīng)的實(shí)驗(yàn)結(jié)果見表4、表5.從表中結(jié)果可以看到:AP 算法在小規(guī)模數(shù)據(jù)上耗時(shí)最短,但隨著數(shù)據(jù)規(guī)模增加其效率大幅下降,并且在所有數(shù)據(jù)集上的聚類質(zhì)量和采樣質(zhì)量都不太理想;IAPNA 算法是增量式輸入數(shù)據(jù)的全局AP 算法,其聚類質(zhì)量和采樣質(zhì)量最優(yōu);但隨著數(shù)據(jù)規(guī)模擴(kuò)大,其時(shí)間消耗劇增,不適用于大規(guī)模數(shù)據(jù)的代表點(diǎn)采樣;HAP 算法與ISAP 算法都是分層采樣代表點(diǎn)的方法,兩種方法的聚類質(zhì)量和采樣質(zhì)量均優(yōu)于AP 算法,接近IAPNA 算法,但兩種算法耗費(fèi)的時(shí)間遠(yuǎn)低于IAPNA 算法.但是HAP 算法在合并推選層上采用的是自適應(yīng)AP 聚類算法,需要執(zhí)行多次標(biāo)準(zhǔn)AP 算法得到最優(yōu)的結(jié)果;隨著數(shù)據(jù)規(guī)模的擴(kuò)大,參與合并推選層采樣的數(shù)據(jù)量也隨之增大.因此,HAP 算法的時(shí)間消耗增加幅度比ISAP 算法要大.ISAP 算法在聚類質(zhì)量和采樣質(zhì)量與IAPNA,HAP 算法處于相同水平,但計(jì)算消耗的時(shí)間顯著較短.

上述實(shí)驗(yàn)結(jié)果也從實(shí)際應(yīng)用角度表明:引入改進(jìn)AP 算法過程和分層處理的ISAP 算法不僅獲得了比標(biāo)準(zhǔn)AP 算法更好的采樣效果,且可以具有更好的計(jì)算效率.這也在一定程度上佐證了前文第4 節(jié)中關(guān)于ISAP 算法性能的理論分析結(jié)果.

4 種算法在yeast 數(shù)據(jù)集上的效果都不理想.wine,yeast 和Set 3 數(shù)據(jù)集內(nèi)各簇的規(guī)模不盡相同,但是wine 和Set 3 各簇之間規(guī)模相似,而yeast 的簇規(guī)模差別較大,是典型的不平衡數(shù)據(jù).從實(shí)驗(yàn)結(jié)果看,幾種對(duì)比算法在不平衡數(shù)據(jù)集的效果均相對(duì)較差.

對(duì)于代表點(diǎn)綜合覆蓋率性能指標(biāo),其與代表點(diǎn)對(duì)數(shù)據(jù)集的覆蓋度和簇?cái)?shù)(代表點(diǎn)數(shù))有關(guān),一般簇?cái)?shù)越大,選取的代表點(diǎn)越多,其代表點(diǎn)對(duì)數(shù)據(jù)集的覆蓋度越大.從UCI 標(biāo)準(zhǔn)數(shù)據(jù)集上的結(jié)果來看:相比于標(biāo)準(zhǔn)AP 算法,ISAP算法能在產(chǎn)生更少代表點(diǎn)的同時(shí)獲得較大的代表點(diǎn)覆蓋度,因此其綜合覆蓋度較高.此外,從人工合成數(shù)據(jù)集上的結(jié)果來看:ISAP 算法在與HAP,IAPNA 算法產(chǎn)生相同簇?cái)?shù)的情況下,ISAP 算法產(chǎn)生的代表點(diǎn)間的平均距離較大,方差較小,說明代表點(diǎn)間的相似性低,挑選結(jié)果平滑,顯著性較好.

Table 4 Performance results obtained by several compared sampling methods on three UCI datasets表4 不同方法在3 個(gè)UCI 數(shù)據(jù)集上的性能對(duì)比結(jié)果

Table 5 Performance results obtained by several compared sampling methods on four synthetic datasets表5 不同方法在4 個(gè)人工數(shù)據(jù)集上的性能對(duì)比結(jié)果

5.3 代表性圖像選擇

在本實(shí)驗(yàn)中,實(shí)驗(yàn)圖像集來自搜索得到的車標(biāo)圖像以及ILSVRC2014 圖像集.車標(biāo)圖像集Carlogo 共有270張圖像,包含18 個(gè)類別的車標(biāo),每類包含15 幅圖像.分別取ILSVARC2014 驗(yàn)證集的前50 類、前100 類和前150類構(gòu)成圖像數(shù)據(jù)集ILSVARC50,ILSVARC100,ILSVARC150,分別包含2 500、5 000 和7 500 張圖像.

實(shí)驗(yàn)過程中,調(diào)整IAPNA 算法參數(shù)pc、ISAP 算法截?cái)鄥?shù)θ和變動(dòng)幅度參數(shù)δ多次執(zhí)行算法,綜合算法輸出的簇?cái)?shù)和采樣質(zhì)量選取,最終實(shí)驗(yàn)參數(shù)設(shè)置見表6.代表性圖像選擇實(shí)驗(yàn)僅評(píng)估算法的采樣質(zhì)量.其中,Carlogo圖像集采用SIFT 特征匹配度作為圖像間相似度,SIFT 相似度經(jīng)過公式(9)轉(zhuǎn)換后得出Carlogo 數(shù)據(jù)集上的AEDRP指標(biāo).ILSVARC 圖像數(shù)據(jù)集則使用卷積神經(jīng)網(wǎng)絡(luò)(convolutional neural networks,簡(jiǎn)稱CNN)提取圖像的特征向量,依據(jù)公式(9)計(jì)算圖像間的特征相似度.

Table 6 Parameter setting in representational image selection experiment表6 代表性圖像選擇實(shí)驗(yàn)參數(shù)設(shè)置情況

實(shí)驗(yàn)結(jié)果見表7.從表中結(jié)果可以看到:綜合考慮代表性圖像的平均距離、距離方差、綜合覆蓋度以及時(shí)間效率,ISAP 算法具有較為明顯的優(yōu)勢(shì).標(biāo)準(zhǔn)AP 算法在各方面都不占優(yōu)勢(shì);IAPNA 方法在數(shù)據(jù)集規(guī)模較大時(shí)時(shí)間耗費(fèi)過大;而HAP 算法得到的代表圖像之間的平均距離較大,但是代表圖像間距離的方差明顯超過另外3 種方法,其代表圖像間的距離分布不平滑.

Table 7 Performance results obtained by serval compared methods on representational image selection problem表7 對(duì)比方法在代表性圖像選擇實(shí)驗(yàn)上的性能結(jié)果

ISAP 算法從數(shù)據(jù)集CarLogo 中選擇的代表性圖像如圖4 所示.

Fig.4 Representational images selected by ISAP on CarLogo data set圖4 ISAP 在CarLogo 數(shù)據(jù)集上挑選的代表性圖像

可以看到:通過本文方法得到的代表性圖像很好地覆蓋了數(shù)據(jù)集,能夠作為數(shù)據(jù)集的代表.

5.4 數(shù)據(jù)增強(qiáng)應(yīng)用

深度學(xué)習(xí)是數(shù)據(jù)驅(qū)動(dòng)的方法,用規(guī)模更大、質(zhì)量更好的數(shù)據(jù)集去訓(xùn)練神經(jīng)網(wǎng)絡(luò)一般都能夠得到泛化性能更好的模型.但在實(shí)際情況中,數(shù)據(jù)的采集面臨多重困難,人工采集的樣本在多樣性和規(guī)模上均不能滿足實(shí)際訓(xùn)練的需求.數(shù)據(jù)增強(qiáng)即數(shù)據(jù)擴(kuò)增,是一種有效擴(kuò)充數(shù)據(jù)規(guī)模,解決訓(xùn)練樣本不足問題的方法[24-26].數(shù)據(jù)增強(qiáng)能夠擴(kuò)充數(shù)據(jù)規(guī)模,增加數(shù)據(jù)噪聲,使用增強(qiáng)后的數(shù)據(jù)集訓(xùn)練神經(jīng)網(wǎng)絡(luò)能夠提高模型的泛化能力和魯棒性.在圖像識(shí)別領(lǐng)域,數(shù)據(jù)增強(qiáng)可以很好地提升訓(xùn)練模型的識(shí)別率.但簡(jiǎn)單的數(shù)據(jù)增強(qiáng)策略容易產(chǎn)生許多極其相似的圖像序列.

考慮檢驗(yàn)ISAP 算法在數(shù)據(jù)增強(qiáng)任務(wù)上的價(jià)值,實(shí)驗(yàn)數(shù)據(jù)來源于加州理工大學(xué)開源數(shù)據(jù)集leaves,包含3 種類型的葉片,共186 張圖像.利用仿射變換、高斯噪聲、區(qū)域衰減、高斯模糊等數(shù)據(jù)增強(qiáng)手段,將leaves 數(shù)據(jù)集的規(guī)模擴(kuò)充10 倍至1 860 張圖像,命名為leavesDa10.在leavesDa10 的基礎(chǔ)上,再次利用上述數(shù)據(jù)增強(qiáng)手段將數(shù)據(jù)集規(guī)模擴(kuò)充5 倍至9 300 張圖像,命名為leavesDa50.

在leavesDa50 上執(zhí)行參數(shù)不同的ISAP 算法,采樣選取每個(gè)最終簇的10 幅圖像(ISAP 算法輸出的代表點(diǎn)及每個(gè)簇中離代表點(diǎn)最近的另外9 幅圖像,規(guī)模不足10 的簇則選取其全部圖像)作為代表圖像,并考慮形成約 1 860 張?jiān)鰪?qiáng)樣本圖像為目標(biāo),最終生成增強(qiáng)數(shù)據(jù)集leavesDaIsap0~leavesDaIsap4.leaves 葉片類型與部分增強(qiáng)圖像如圖5 所示.

Fig.5 leaves blade type and partial enhanced images圖5 leaves 葉片類型與部分增強(qiáng)圖像

在各數(shù)據(jù)集上,從每類葉片中取3/4 的圖像用于卷積神經(jīng)網(wǎng)絡(luò)CNN 訓(xùn)練,其余1/4 的圖像用于模型測(cè)試,使用參數(shù)不同的ISAP 算法產(chǎn)生的約簡(jiǎn)數(shù)據(jù)集訓(xùn)練得到的模型平均識(shí)別率(10 次實(shí)驗(yàn)結(jié)果的平均)如表8 所示.其中,采樣指標(biāo)AEDRP 值依據(jù)算法直接輸出的代表點(diǎn)進(jìn)行計(jì)算.

Table 8 Performance results obtained by different ISAP-augmented deep learning on leaves recognition task表8 不同參數(shù)ISAP 算法數(shù)據(jù)增強(qiáng)下leaves 葉片識(shí)別問題的深度學(xué)習(xí)性能結(jié)果比較

考慮以采樣比例和AEDRP 指標(biāo)為依據(jù),針對(duì)表8 中的實(shí)驗(yàn)結(jié)果,將leavesDaIsap0 數(shù)據(jù)集上訓(xùn)練的結(jié)果與其他方法進(jìn)行比較.

考慮在leavesDa50 上執(zhí)行HAP 算法,用上述選取代表性圖像方法構(gòu)成增強(qiáng)數(shù)據(jù)集leavesDaHap;為了更好地與HAP 算法進(jìn)行對(duì)比分析,調(diào)整ISAP 參數(shù)為θ=0.3,δ=0.05,可形成規(guī)模為4 584 的數(shù)據(jù)集leavesDaIsap5,相應(yīng)的實(shí)驗(yàn)結(jié)果見表9,其中的平均識(shí)別率為10 次實(shí)驗(yàn)的平均結(jié)果.

Table 9 Performance results obtained by different augmented datasets on leaves recognition task表9 不同增強(qiáng)數(shù)據(jù)集下leaves 葉片識(shí)別問題的深度學(xué)習(xí)性能結(jié)果比較

從表9 中實(shí)驗(yàn)結(jié)果可以看到:leavesDa10 與leavesDaIsap0 的規(guī)模相近,在經(jīng)過ISAP 算法采樣約簡(jiǎn)的數(shù)據(jù)集leavesDaIsap0 上訓(xùn)練學(xué)得的模型識(shí)別率遠(yuǎn)好于在使用簡(jiǎn)單數(shù)據(jù)增強(qiáng)手段的leavesDa10 上訓(xùn)練學(xué)得的模型識(shí)別率.leavesDa50 是基本數(shù)據(jù)增強(qiáng)擴(kuò)充50 倍后的數(shù)據(jù)集,其規(guī)模大致是leavesDaIsap0 的5 倍.用leavesDaIsap0 訓(xùn)練得到的模型的識(shí)別率與用leavesDa50 訓(xùn)練得到的模型的識(shí)別率相差已不大.在經(jīng)過HAP 算法采樣約簡(jiǎn)的數(shù)據(jù)集leavesDaHap 上訓(xùn)練得到的模型識(shí)別率接近在leavesDa50 上學(xué)得的模型,其數(shù)據(jù)規(guī)模只有l(wèi)eavesDa50 的1/2 左右.但是相比于ISAP 算法的采樣,HAP 算法的采樣并不占優(yōu)勢(shì).因?yàn)镠AP 算法無法有效獲得可控?cái)?shù)量的代表點(diǎn)集,ISAP 算法在調(diào)整參數(shù)的情況下可以控制輸出代表點(diǎn)的規(guī)模.而在最終樣本規(guī)模相近的情況下,ISAP算法數(shù)據(jù)增強(qiáng)策略相對(duì)于HAP 算法數(shù)據(jù)增強(qiáng)策略獲得的模型識(shí)別率也較為接近.而在實(shí)際使用時(shí),由于ISAP算法計(jì)算效率顯著較高,顯然具有更高的實(shí)用價(jià)值.

綜上表明,數(shù)據(jù)增強(qiáng)手段結(jié)合進(jìn)高效增量采樣處理后,在不改變總訓(xùn)練數(shù)據(jù)集規(guī)模的情況下,ISAP 算法介入所獲得的模型質(zhì)量可實(shí)現(xiàn)顯著的提升.且ISAP 算法能夠控制約簡(jiǎn)后數(shù)據(jù)集的規(guī)模,有效地在減小數(shù)據(jù)規(guī)模的同時(shí),保證數(shù)據(jù)集的多樣性;在保持?jǐn)?shù)據(jù)集規(guī)模不變的情況下有效提升數(shù)據(jù)質(zhì)量,增加樣本多樣性.此外,因?yàn)镮SAP 高效的處理速度,可以快速地處理更大規(guī)模的數(shù)據(jù)增強(qiáng)數(shù)據(jù)集,更好地滿足現(xiàn)實(shí)應(yīng)用需求.

6 結(jié)論與展望

本文針對(duì)數(shù)據(jù)集代表點(diǎn)采樣的一般性問題,提出了一種基于動(dòng)態(tài)賦權(quán)近鄰傳播的數(shù)據(jù)增量采樣算法ISAP.算法通過引入分層增量處理和樣本點(diǎn)動(dòng)態(tài)賦權(quán)策略,結(jié)合偏向參數(shù)動(dòng)態(tài)賦權(quán)的AP 算法,有效地實(shí)現(xiàn)了處理效率和采樣質(zhì)量的兼顧,更好地滿足大規(guī)模數(shù)據(jù)集上的高效代表點(diǎn)選擇.設(shè)計(jì)實(shí)驗(yàn)分別使用人工數(shù)據(jù)集、UCI 標(biāo)準(zhǔn)數(shù)據(jù)集和圖像數(shù)據(jù)集進(jìn)行性能分析,與其他方法相比,ISAP 算法在獲得了采樣劃分質(zhì)量與其他方法處于同一水平的同時(shí),計(jì)算效率獲得了大幅提升.進(jìn)一步將ISAP 算法應(yīng)用于深度學(xué)習(xí)的數(shù)據(jù)增量任務(wù)中,相應(yīng)實(shí)驗(yàn)結(jié)果表明:基本數(shù)據(jù)增強(qiáng)策略結(jié)合進(jìn)高效處理的ISAP 算法后,在不改變總訓(xùn)練數(shù)據(jù)集規(guī)模的情況下增加了樣本的多樣性,在保留樣本多樣性的同時(shí)約簡(jiǎn)了訓(xùn)練數(shù)據(jù)集的規(guī)模,新數(shù)據(jù)增強(qiáng)后所獲得的模型質(zhì)量可實(shí)現(xiàn)顯著的提升.

在下一階段,我們將從以下幾個(gè)方面進(jìn)行嘗試.

(1) 本文中使用的數(shù)據(jù)規(guī)模與實(shí)際情況可能會(huì)面臨的數(shù)據(jù)規(guī)模相比,規(guī)模還不夠大.當(dāng)數(shù)據(jù)規(guī)模擴(kuò)大到一層增量局部推選加一層合并推選的“1+1”模式的采樣無法處理時(shí),研究如何將該方法擴(kuò)充至n層增量局部推選加一層最終合并推選的“n+1”模式的采樣;

(2) 類似于標(biāo)準(zhǔn)的AP 算法,本文方法還不能很好地適應(yīng)于類規(guī)模差別較大的數(shù)據(jù)集,在不平衡數(shù)據(jù)集上的采樣效果不太理想.對(duì)算法過程作何改進(jìn),能夠使其適用于不平衡數(shù)據(jù)集,是一個(gè)值得思考的問題;

(3) 作為一種同步約簡(jiǎn)的增量式采樣算法,關(guān)于其中理論性能的分析研究還不夠深入,這也將在我們的后續(xù)研究中進(jìn)一步展開.