基于動態賦權近鄰傳播的數據增量采樣方法*

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

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

2(江蘇省媒體設計與軟件技術重點實驗室(江南大學),江蘇 無錫 214122)

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

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

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

針對大規模數據的代表點采樣問題,本文提出了一種基于動態賦權近鄰傳播的數據增量采樣算法ISAP (incremental data sampling using affinity propagation with dynamic weighting).主要包含兩個策略.

(1) 近鄰傳播偏向參數的動態賦權.在AP 算法的迭代過程中,利用樣本點單次迭代聚類結果計算樣本點自身輪廓系數,對AP 算法的重要參數——偏向參數做動態調整,使最終采樣結果能夠包含更多的潛在性樣本;

(2) 引入分層增量處理,將數據集劃均勻劃分為規模適中的子集,在各子集上分別執行全局偏向參數動態賦權的AP 算法,獲得局部最優代表點集合;然后在局部最優代表點集合上執行局部偏向參數動態賦權的AP 算法,推選出整個數據集的最終代表點.

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

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

本文的主要貢獻:

(1) 提出了一種基于動態賦權近鄰傳播的數據增量采樣算法,引入分層增量處理和樣本點動態賦權策略,良好地實現了數據采樣質量和效率的平衡;

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

(3) 將本文方法應用于深度學習的數據增強任務中,實驗結果表明:在保持訓練數據集規模不變的情況下,本文方法介入所獲得的模型質量有顯著提升.

本文第1 節將介紹方法框架.第2 節、第3 節介紹標準AP 算法及基于動態賦權近鄰傳播的數據增量采樣算法ISAP.第4 節對算法進行相關分析.第5 節通過實驗評估算法的效果.第6 節對本文進行總結,對未來工作進行展望.

1 基于動態賦權近鄰傳播的數據增量采樣方法ISAP 框架

本文提出的基于動態賦權近鄰傳播的數據增量采樣算法框架如圖1 所示,主要包含以下內容.

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

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

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

2 AP 算法中偏向參數的動態賦權

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

在基于聚類方法的代表點采樣問題中,聚類質量與代表點采樣質量緊密相關,聚類質量的提升,在一定程度上能夠解決采樣結果的代表性問題.AP 算法改善聚類質量的一個方向是偏向參數,偏向參數直接影響最終聚類數目,決定聚類質量的好壞.偏向參數一般根據經驗設置為統一常數[12,15,16],在AP 算法的迭代過程中恒定不變,即所有樣本點成為簇代表點的可能性從始至終是一樣的.但是在實際情況中,樣本點之間的差異使得它們成為簇代表點的可能性不盡相同;此外,在迭代過程中因為信息交換的影響,樣本點成為簇代表點的概率是會變動的.因此,給所有樣本點設置同樣且恒定的偏向參數的做法并不恰當,容易導致不好的聚類結果.為便于后續討論,表1 中匯總給出了本小節與新方法有關的符號信息.

Table 1 Summary of relevant symbols on chapter 2表1 第2 節新方法相關符號匯總

2.1 初始偏向參數定義

在實際問題中,根據局部密度、語義性等信息可以知道,樣本點成為簇代表點的可能性是有區別的,所以將偏向參數P={pk}1×N設置為統一常數的做法并不恰當.

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

其中,

?I(·)為指示函數;

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

參數θ定義為相似度截斷值,其大小的設置與數據集所有樣本點間的相似度緊密程度相關,其在某種程度上也反映了原始距離度量s(·,·)的上限合理尺度.

2.2 偏向參數動態賦權

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

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

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

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

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

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

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

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

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

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

在AP 算法迭代產生聚類中心的情況下,引入對樣本點的輪廓系數評價.參考Silhouette指標的結果可以得知樣本點是否被正確地劃分,以及被選作聚類中心的樣本點是否是正確的聚類中心,從而調整每個樣本的偏向參數{pk},動態改變樣本點成為聚類中心的可能性.顯然,聚類中心樣本與非聚類中心樣本在調整上存在差異,因此給出兩條偏向參數更新規則.

規則1.對于非聚類中心樣本:Silhouette指標大于0,說明該樣本被劃分到正確的簇,其成為聚類中心的可能性應該降低,pk應適當減小;Silhouette指標小于0,則該點沒有被劃分到正確的簇,其應該被劃分到其他簇或成為一個新的聚類中心,pk應維持不變或適當增加.

規則2.對于聚類中心樣本:Silhouette指標大于0,說明該樣本是正確的聚類中心,pk應維持不變或適當增加;Silhouette指標小于0,說明該點不是正確的聚類中心,pk應適當減小.

基于上述兩條規則,為了將Silhouette轉化為合適的Δp,定義如下轉換函數:

O={ok}1×N存放聚類中心標志,如果ok=1,表明樣本點i是聚類中心;否則,ok=-1.參數δ調整Δp的變動幅度.引入基于Silhouette計算的Δp,當算法產生至少一個聚類中心后,偏向參數動態賦權的AP 算法更新公式如下:

偏向參數動態調整的AP 算法在復雜度上與標準AP 算法沒有差別,但是因為考慮到了樣本點之間的相互作用關系,使得偏向參數能夠即時反映樣本點當前迭代時刻的狀態.對于基于聚類劃分的采樣問題來說,期望得到的代表點能夠更大程度地覆蓋原始數據的空間區域,包含更多數據密度較小區域的特異性樣本,而引入偏向參數的動態調整能夠在一定程度上消除原始數據密度分布給初始偏向參數帶來的影響,從而能夠找到更多低數據密度空間區域中的代表性樣本.引入輪廓系數動態改變偏向參數后,算法過程如下.

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

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

輸出:聚類中心classcenter.

3 分層增量采樣

AP 算法中,聚類中心為真實樣本點這一特性,使得其非常適用于代表點的采樣.但是標準AP 算法的復雜度較高,不適用于大規模數據的代表點采樣.本文結合分層及增量處理的采樣策略,基于上述偏向參數的動態賦權AP 算法,實現對數據集的高效采樣,以期實現處理效率和采樣質量的更好兼顧.

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

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

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

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

結合截斷值參數θ的引入,本文方法可考慮對原始的所有數據點間的相似度矩陣進行約簡,將小于相似度截斷值的邊進行刪除,進而達到約簡相似度矩陣的目的,加速AP 算法的計算效率.綜前所述,可歸納給出如下的綜合算法過程.

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

輸入:子集序列D1,D2,…,Dn,相似度截斷值θ,阻尼系數λ,變動幅度δ,最大迭代次數maxiter,最大收斂狀態比較次數conviter;

輸出:代表點集R′,全局劃分Cluster.

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

4 算法分析

假設數據集被劃分為K個規模為M的子集(K<

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

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

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

5 實驗分析

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

(1) 標準AP 算法的代表點采樣:使用文獻[12]提出的標準AP 算法來做代表點選取;

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

(3) 近鄰賦值的增量式AP 聚類算法IAPNA 的代表點采樣:使用文獻[16]提出的一種增量式AP 算法來做代表點選取.該方法通過近鄰賦值構建新增數據與已有數據之間的消息傳遞關系,增量式地擴充吸引度和歸屬度矩陣,直至方法收斂得到結果.

相關算法實驗中,首先需要計算樣本點i和j之間的相似度s(i,j),s(i,j)的值越大,表示兩個樣本越相近.實驗中,對兩個樣本點間的相似度s(i,j)采用歸一化計算定義:

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

實驗中,參考各自算法特點和相關文獻,AP 算法的偏向參數取相似度矩陣中位值;對于IAPNA 方法參數pc,根據算法輸出簇數和采樣質量選取對比選取;對于ISAP 算法中的截斷參數θ和變動幅度參數δ,一方面也可類似地根據算法輸出簇數和采樣質量選取對比選取,其中的采樣質量可以是使用有監督的交叉驗證選取;或者使用無監督的質量指標(如代表點間平均歐式距離)作為參照.

此外,截斷參數θ一定程度上反映了數據點間距離度量合理性的界限范圍,而變動幅度參數δ是從微觀上對偏向參數進行調整,解釋樣本點對于輪廓系數的學習能力.由此,取θ選擇范圍可取[10-2,max(D)],δ選擇范圍可設定為[10-3,10-1],其中,max(D)同公式(9)中的含義.

5.1 評價指標

實驗從聚類質量、采樣質量和方法效率這3 個方面對代表點采樣方法進行評價.標準化互信息(normalized mutual information,簡稱NMI)是廣泛用于聚類質量評估的聚類評價指標,用于度量方法結果與標準結果之間的相似度,其定義如下:

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

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

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

5.2 數值數據實驗分析

在3 組UCI 標準數據集和4 組人工合成數據集上進行代表性樣本采樣實驗,數據集詳情見表2.

Table 2 Descriptions of numerical experimental data sets表2 數值型實驗數據集描述

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

在實驗過程中,調整IAPNA 算法參數pc、ISAP 算法截斷參數θ和變動幅度參數δ進行多次實驗.參數pc在真實數據集上的數值來源于文獻[16],參數θ,δ以及人工數據集上的pc綜合算法輸出的簇數和采樣質量選取.最終實驗參數設置見表3.

Fig.3 Four synthetic data sets圖3 人工合成數據集情況

Table 3 Parameter setting for numerical experimental data sets表3 數值型數據實驗算法參數設置情況

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

上述實驗結果也從實際應用角度表明:引入改進AP 算法過程和分層處理的ISAP 算法不僅獲得了比標準AP 算法更好的采樣效果,且可以具有更好的計算效率.這也在一定程度上佐證了前文第4 節中關于ISAP 算法性能的理論分析結果.

4 種算法在yeast 數據集上的效果都不理想.wine,yeast 和Set 3 數據集內各簇的規模不盡相同,但是wine 和Set 3 各簇之間規模相似,而yeast 的簇規模差別較大,是典型的不平衡數據.從實驗結果看,幾種對比算法在不平衡數據集的效果均相對較差.

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

Table 4 Performance results obtained by several compared sampling methods on three UCI datasets表4 不同方法在3 個UCI 數據集上的性能對比結果

Table 5 Performance results obtained by several compared sampling methods on four synthetic datasets表5 不同方法在4 個人工數據集上的性能對比結果

5.3 代表性圖像選擇

在本實驗中,實驗圖像集來自搜索得到的車標圖像以及ILSVRC2014 圖像集.車標圖像集Carlogo 共有270張圖像,包含18 個類別的車標,每類包含15 幅圖像.分別取ILSVARC2014 驗證集的前50 類、前100 類和前150類構成圖像數據集ILSVARC50,ILSVARC100,ILSVARC150,分別包含2 500、5 000 和7 500 張圖像.

實驗過程中,調整IAPNA 算法參數pc、ISAP 算法截斷參數θ和變動幅度參數δ多次執行算法,綜合算法輸出的簇數和采樣質量選取,最終實驗參數設置見表6.代表性圖像選擇實驗僅評估算法的采樣質量.其中,Carlogo圖像集采用SIFT 特征匹配度作為圖像間相似度,SIFT 相似度經過公式(9)轉換后得出Carlogo 數據集上的AEDRP指標.ILSVARC 圖像數據集則使用卷積神經網絡(convolutional neural networks,簡稱CNN)提取圖像的特征向量,依據公式(9)計算圖像間的特征相似度.

Table 6 Parameter setting in representational image selection experiment表6 代表性圖像選擇實驗參數設置情況

實驗結果見表7.從表中結果可以看到:綜合考慮代表性圖像的平均距離、距離方差、綜合覆蓋度以及時間效率,ISAP 算法具有較為明顯的優勢.標準AP 算法在各方面都不占優勢;IAPNA 方法在數據集規模較大時時間耗費過大;而HAP 算法得到的代表圖像之間的平均距離較大,但是代表圖像間距離的方差明顯超過另外3 種方法,其代表圖像間的距離分布不平滑.

Table 7 Performance results obtained by serval compared methods on representational image selection problem表7 對比方法在代表性圖像選擇實驗上的性能結果

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

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

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

5.4 數據增強應用

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

考慮檢驗ISAP 算法在數據增強任務上的價值,實驗數據來源于加州理工大學開源數據集leaves,包含3 種類型的葉片,共186 張圖像.利用仿射變換、高斯噪聲、區域衰減、高斯模糊等數據增強手段,將leaves 數據集的規模擴充10 倍至1 860 張圖像,命名為leavesDa10.在leavesDa10 的基礎上,再次利用上述數據增強手段將數據集規模擴充5 倍至9 300 張圖像,命名為leavesDa50.

在leavesDa50 上執行參數不同的ISAP 算法,采樣選取每個最終簇的10 幅圖像(ISAP 算法輸出的代表點及每個簇中離代表點最近的另外9 幅圖像,規模不足10 的簇則選取其全部圖像)作為代表圖像,并考慮形成約 1 860 張增強樣本圖像為目標,最終生成增強數據集leavesDaIsap0~leavesDaIsap4.leaves 葉片類型與部分增強圖像如圖5 所示.

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

在各數據集上,從每類葉片中取3/4 的圖像用于卷積神經網絡CNN 訓練,其余1/4 的圖像用于模型測試,使用參數不同的ISAP 算法產生的約簡數據集訓練得到的模型平均識別率(10 次實驗結果的平均)如表8 所示.其中,采樣指標AEDRP 值依據算法直接輸出的代表點進行計算.

Table 8 Performance results obtained by different ISAP-augmented deep learning on leaves recognition task表8 不同參數ISAP 算法數據增強下leaves 葉片識別問題的深度學習性能結果比較

考慮以采樣比例和AEDRP 指標為依據,針對表8 中的實驗結果,將leavesDaIsap0 數據集上訓練的結果與其他方法進行比較.

考慮在leavesDa50 上執行HAP 算法,用上述選取代表性圖像方法構成增強數據集leavesDaHap;為了更好地與HAP 算法進行對比分析,調整ISAP 參數為θ=0.3,δ=0.05,可形成規模為4 584 的數據集leavesDaIsap5,相應的實驗結果見表9,其中的平均識別率為10 次實驗的平均結果.

Table 9 Performance results obtained by different augmented datasets on leaves recognition task表9 不同增強數據集下leaves 葉片識別問題的深度學習性能結果比較

從表9 中實驗結果可以看到:leavesDa10 與leavesDaIsap0 的規模相近,在經過ISAP 算法采樣約簡的數據集leavesDaIsap0 上訓練學得的模型識別率遠好于在使用簡單數據增強手段的leavesDa10 上訓練學得的模型識別率.leavesDa50 是基本數據增強擴充50 倍后的數據集,其規模大致是leavesDaIsap0 的5 倍.用leavesDaIsap0 訓練得到的模型的識別率與用leavesDa50 訓練得到的模型的識別率相差已不大.在經過HAP 算法采樣約簡的數據集leavesDaHap 上訓練得到的模型識別率接近在leavesDa50 上學得的模型,其數據規模只有leavesDa50 的1/2 左右.但是相比于ISAP 算法的采樣,HAP 算法的采樣并不占優勢.因為HAP 算法無法有效獲得可控數量的代表點集,ISAP 算法在調整參數的情況下可以控制輸出代表點的規模.而在最終樣本規模相近的情況下,ISAP算法數據增強策略相對于HAP 算法數據增強策略獲得的模型識別率也較為接近.而在實際使用時,由于ISAP算法計算效率顯著較高,顯然具有更高的實用價值.

綜上表明,數據增強手段結合進高效增量采樣處理后,在不改變總訓練數據集規模的情況下,ISAP 算法介入所獲得的模型質量可實現顯著的提升.且ISAP 算法能夠控制約簡后數據集的規模,有效地在減小數據規模的同時,保證數據集的多樣性;在保持數據集規模不變的情況下有效提升數據質量,增加樣本多樣性.此外,因為ISAP 高效的處理速度,可以快速地處理更大規模的數據增強數據集,更好地滿足現實應用需求.

6 結論與展望

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

在下一階段,我們將從以下幾個方面進行嘗試.

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

(2) 類似于標準的AP 算法,本文方法還不能很好地適應于類規模差別較大的數據集,在不平衡數據集上的采樣效果不太理想.對算法過程作何改進,能夠使其適用于不平衡數據集,是一個值得思考的問題;

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