魏彩鋒，孫永聰，曾憲華

（1. 重慶郵電大學 計算機科學與技術學院，重慶 400065; 2. 重慶郵電大學 計算智能重慶市重點實驗室，重慶400065）

目前，多媒體技術飛速發(fā)展，圖像數(shù)量呈指數(shù)級增長，圖像分類技術也得到了飛速發(fā)展。圖像分類方法主要包括分類器的設計和特征提取兩個部分，目前對圖像分類的研究主要集中在分類器性能的改進和改善特征提取方法兩方面。稀疏編碼(字典學習)[1-10]是圖像分類的有效技術之一，用于圖像分類的字典學習算法也可以分為2類：1)學習字典把原始圖像映射到有利于圖像分類的空間上，用傳統(tǒng)的分類器去分類；2)用稀疏系數(shù)所表示出來的樣本屬性進行分類。

在用于圖像分類的字典學習算法中，字典和編碼系數(shù)的設計從中起著關鍵作用[3]。基于稀疏表示的分類算法[4]，將整個訓練樣本作為字典，利用測試樣本在字典上的重構誤差分類。在字典中的每個原子都是一個樣本，由于樣本數(shù)量的限制，字典原子中有相同或相似的，還有一些則不包含在內造成分類錯誤。而Aharon M等提出的KSVD算法[5]學習的字典具有自適應性，能夠更好對信號進行稀疏表示。雖然，使用重構誤差作為損失函數(shù)，可以用于圖像分類，但是還有許多因素沒有考慮到。Yang等[6]提出Fisher字典學習在自適應字典基礎上，考慮到相同的樣本之間的類內散度較小，類間散度大，在目標函數(shù)上加入了識別系數(shù)項，提高分類能力。Jiang等[7]提出的LC-KVD算法，在KSVD算法[5]基礎上加入了標簽約束項。在文獻[8]中，由于分別學習特征影射矩陣和字典，會影響特征影射矩陣的判別信息，提出了同時學習投影矩陣和字典，為了能夠提取更多的判別信息，加入圖正則項。構建近鄰圖，近鄰且同類相似度為1，近鄰但不同類相似度為-1，其他為0。在文獻[9]中圖正則化中的相似度矩陣定義為兩近鄰樣本的相似度為兩樣本之間的歐氏距離，不近鄰樣本之間的相似度為0。使用不同的相似矩陣，分類效果也不同。另一方面，由于字典學習[3-9]大多是使用編碼系數(shù)的0或1范數(shù)作正則項，在訓練和測試階段效率較低，運行時間長。2014年在NIPS上Gu等[10]提出了字典對學習，聯(lián)合學習一個綜合字典和分析字典，用分析字典去分析編碼，由于綜合字典的重構效果比較好，使用綜合字典去重構圖像。它不僅減少了在訓練和測試階段的時間復雜度，也提高了模型的分類能力。但是，字典對學習模型沒有考慮圖像的幾何近鄰拓撲關系。為了提高模型的分類能力，基于同類樣本的系數(shù)之間的距離小，不同類系數(shù)之間的距離大的思想，提出了基于圖正則化字典對學習(GDPL)算法。

在最近的綜合研究[11]中，用十倍交叉驗證的方法評估輕度認知功能障礙(MCI)到阿爾茲海默癥(AD)的預測，只有4種方法的實驗結果比隨機分類的結果好，因此，提出新的方法提高MCIAD的預測是十分必要的。在圖像分類中，并不是所有的特征都與識別分類有關，其中有一些是無關特征，將這些特征用于分類會出現(xiàn)過擬合現(xiàn)象。由于稀疏表示中表示系數(shù)具有稀疏性，將本文提出的圖正則化字典對學習算法用于輕度認知功能障礙預測。

1 相關工作

1.1 字典學習

設 X =[X1···Xk···XK]∈ Rp×n是一個 K 類 p 維的訓練樣本，第 k 類樣本 Xk=[x1···xi···xnk]，Xk∈ Rp×nk,k=1,2,···,K 是第 k類訓練 nk樣本，n=n1+n2+···+nk+···+nK。字典學習模型的分類任務是通過利用訓練數(shù)據(jù)的類標簽信息學習一個有效的數(shù)據(jù)表示模型去進行分類。在使用字典學習算法的圖像分類研究中，如何設計對特征提取有效的字典和編碼系數(shù)是決定算法性能的關鍵因素[1]。對于字典學習算法設計考慮的有三方面：1)稀疏表示殘差(重構誤差)小，使樣本在稀疏表示時盡可能的接近原始樣本；2)對表示系數(shù)約束，使表示系數(shù)稀疏；3)考慮能夠更好提取更多的判別信息的判別項。用于圖像分類的判別字典學習模型[6-7,12-13]可通常以表示為：

式中： λ 、η 是常量(平衡因子)；Y 是樣本 X 的標簽向量；D 是學習的綜合字典；A 是 X 在綜合字典 D上的編碼系數(shù)矩陣。在訓練模型時，數(shù)據(jù)保真項||X-DA|是為了保證字典 D 的表示能力，使訓練數(shù)據(jù)的重構誤差最小，重構出來的圖像盡可能的接近原始樣本。正則項用于約束編碼系數(shù)的稀疏性，其通常應用范數(shù)表示為：

式中： || ·||p是編碼系數(shù) A 正則項的常用形式(p ＜2)，使編碼系數(shù) A 在重建誤差滿足要求的情況下盡可能地稀疏。 f (D,A,Y) 是字典學習用于分類的判別函數(shù)項，保證 D 和 A 的判別能力。

1.2 字典對學習

在1.1中描述的判別式字典學習模型是學習一個共享字典，對系數(shù)的約束都是使用 l0或者是l1范數(shù)對編碼系數(shù)進行系數(shù)正則化約束，使訓練模型在訓練階段和測試階段效率降低。Gu等[10]為了提高模型在訓練階段和測試階段的效率和整體的識別能力，提出了聯(lián)合學習一個綜合字典和分析字典的字典對學習(DPL)，不使用 l0或者是l1范數(shù)對編碼系數(shù)進行稀疏正則化，而是找到一個分析字典 P，使訓練樣本X 在分析字典 P上線性投影得出編碼系數(shù) A，即 A = PX 保持稀疏性，重建誤差與判別約束保證下使訓練樣本 X 的稀疏表示變的更加有效且解決了out-of-sample問題。字典對模型描述表示如下：

式中： f (D,P,X,Y) 表示判別函數(shù)。D 和 P 是一個字典對：分析字典 P 用于編碼 X，綜合字典 D 用于重構 X。學習一個結構綜合字典D=[D1···Dk···DK] 和 結構分析字典 P =[P1···Pk···PK]，其中 { Dk,Pk} 是第 k 類的子字典對。對于分析字典P 使其滿足第 i (i ≠k)類樣本在第 k 類的子字典Pk上的投影系數(shù)為空，即 PkXi≈ 0,?k≠ i，也就是編碼系數(shù)矩陣 PX 接近塊正交。對于合成字典D，使其子字典 Dk與投影編碼矩陣 PkXk能夠很好的重構樣本 Xk，要求字典對有最小的重構誤差：

因此，DPL模型的目標函數(shù)可以寫為：

式中： Xk是 Xk在整個訓練集中的補集；λ 是一個標準常量； di是合成字典的第 i 個原子。

2 圖正則化字典對學習

字典對學習只考慮圖像的重構誤差和不同類的分析字典和樣本的投影系數(shù)盡可能的小，沒有考慮原始樣本的近鄰幾何結構，引入圖正則化，使低維表示能夠保留原始樣本的近鄰結構。

2.1 圖正則化字典對學習

在流形學習中，假設兩個高維空間的相鄰的兩點，在其對應的低維空間仍保持其在高維空間的幾何近鄰拓撲關系。為了使樣本之間可區(qū)分，并同時保持原始圖像的幾何近鄰結構，且使同類樣本在分析字典 P 上的投影系數(shù)之間距離小，不同類之間的距離大。對編碼系數(shù)的圖正則項約束表示為：

式中：n 是所有樣本總數(shù)；u 和 v 是第 u (v) 訓練樣本； P xu和 P xv是訓練樣本 xu和 xv在分析字典 P的投影，即分析編碼系數(shù)。

在大多數(shù)圖正則項，都是對數(shù)據(jù)集構建近鄰圖[9]，用圖的邊的權值表示數(shù)據(jù)之間的關聯(lián)度。但是本文利用樣本總數(shù)去平衡類內和類間的距離，已經(jīng)證明能夠提高在字典上的編碼系數(shù)的判別能力[12]，因此，本文中相似度矩陣 S 是依據(jù)xu和 xv的標簽保證相應系數(shù)之間的相似性[12]。用訓練集構建近鄰圖，用標簽信息判讀樣本是否近鄰。如果 xu和 xv標簽相同，則為近鄰，相似度為Suv=1/nl(xu)； 如果 xu和 xv標簽不同，則不近鄰，相似度為 Suv=-1/(n-nl(xu))。 相似度矩陣 S 的第 u 行v列的元素為：

式 中 ： l (xu) 和 l ( xv) 表 示 的 是 樣 本 xu和 xv的 類 標簽； nl(xu)是訓練樣本中標簽為 l ( xu) 的樣本總數(shù)。矩陣 L =C∑-S ， 其中 C =diag{c1,c2,···,cn} 是對角矩陣，且 cv=v=1Suv。

在DPL算法的基礎上，構建近鄰圖保持原始圖像間的近鄰關系，由此提出了圖正則化字典對學習(GDPL)算法。GDPL算法的目標函數(shù)可寫為：

式中： λ 和 β 是平衡因子，在公式(9)中的第1項是重構誤差項，重構誤差項盡可能的小，使重構出來的圖像與原圖像盡可能的接近。 Xˉk是 Xk在整個訓練樣本上的補集，第2項是第 K 類以外的訓練樣本，在第 K 類的分析字典上的編碼系數(shù)盡可能小，使編碼系數(shù)盡可能的稀疏。第3項是圖正則項，使圖像在字典上的編碼系數(shù)仍舊保持原始圖像的近鄰關系。

引入變量編碼系數(shù) A， 使 A =PX ，目標函數(shù)可以寫為下面式子：

式 中 ： t r(·) 表 示 矩 陣 的 跡 。 矩 陣 L =C-S,C=diag{c1,c2,···,cn}該對角矩陣的對角元素是 S 的行(列)的元素之和。

2.2 圖正則化字典對學習

在流形學習中，假設兩個高維空間的相鄰的兩隨機初始化分析字典 P 和綜合字典 D，之后，迭代更新編碼系數(shù) A 和 { P ,D}。

1) 固定綜合字典 Dk和分析字典 Pk，更新編碼系數(shù) Ak， 由于含有 Ak的式子前面有相同的系數(shù) α，在計算的過程中可以消去，所以可以利用式(10)解出 Ak：

2) 固定編碼系數(shù) Ak， 更新綜合字典 Dk和分析字典 Pk。

對 Pk封閉求解，即

對 Pk求導，得

式中： γ =10e-4，I 是單位矩陣，在公式加入(一個極小的常數(shù))是為了保證逆運算有解。

在公式(13)中用交替方向乘子算法(AMMD)[8]對 D 優(yōu)化求解。具體的求解過程如下所示：

對 Dk求導：

對 Sk求導：

2.3 圖正則化字典對學習訓練算法

由于算法中的圖正則項，需要先用訓練樣本構建近鄰圖，計算出相似矩陣 S 和拉普拉斯矩陣L。利用目標函數(shù)優(yōu)化過程進行迭代更新，學習字典對 { P ,D}。圖正則化字典對學習算法的訓練過程在算法1中詳細描述。

算法1 GDPL訓練算法

輸入訓練樣本 X =[X1X2···XK]，訓練樣本標簽信息 Y =[Y1Y2···Yk]， 參數(shù) α ,τ,λ,β，子字典原子數(shù) m。最大迭代次數(shù)max。

1) 利用樣本標簽信息構建近鄰圖。根據(jù)樣本標簽信息判斷樣本是否為近鄰點。若 xu和 xv標簽相同，則為近鄰點，相似度 Suv=1/nl(xu)； 若 xu和xv標簽不相同，則不是近鄰點，相似度 Suv=-1/(n∑-nl(xu))。對 角 矩 陣 C =diag{c1,c2,···,cn}， 其 中 cv=v=1Suv，拉普拉斯矩陣 L =C-S。

2) 初始化：隨機生成綜合字典 D0和分析字典 P0， 迭代次數(shù) t = 0。

3)Fori=1:K

While 未收斂(具體的在收斂性分析中)執(zhí)行下面步驟：

1) 固定字典 Dk和 Pk， 由目標函數(shù)中含有Ak的式子求解得出式(10)，根據(jù)式(10)，更新編碼系數(shù) Ak；

2) 固定編碼系數(shù) Ak， 由式(11)中 Dk使用ADMM算法得出式(14)更新字典 Dk；在ADMM算法中 Dk、 Sk、 Tk根據(jù)式(14)、(15)、(13)中最后一個式子更新直到達到ADMM算法的收斂條件停止。

3) 固定編碼系數(shù) Ak， 由式(11)中 Pk解出式(12)，根據(jù)式(12)更新字典 Pk；

End While

End For

輸出綜合字典 D，分析字典 P。

2.4 分類方法

在圖像分類中，并不是所有的特征都與識別分類有關，其中有一些是無關特征，將這些特征用于分類會出現(xiàn)過擬合現(xiàn)象。另一方面，稀疏表示是在超完備字典中用盡可能少的原子去表示原來的圖像信號，其中的表示系數(shù)具有稀疏性。用表示系數(shù)作為特征去分類，可以減少無關特征的影響，提高模型的判別能力。用ADNI1數(shù)據(jù)集進行驗證，具體的實驗結果在第4部分中，使用編碼系數(shù)用分類器分類效果比直接使用分類器[14]的效果好。

在分類模型中，輸入訓練樣本 X 使用算法1訓練出來的綜合字典 D 和分析字典 P，由 A，計算出訓練集在分析字典上的投影系數(shù)即稀疏表示中的編碼系數(shù) Atrain=PX ， 由測試樣本 Xtest和分析字典 P，可以計算出測試集的編碼系數(shù) Atest=PXtest。將編碼系數(shù)作為特征，用分類器對測試樣本進行分類。

3 算法分析

本節(jié)主要對提出的圖正則化字典對算法(GDPL)進行時間復雜度分析和收斂性分析，該算法通過聯(lián)合學習一個綜合字典和分析字典，將樣本在分析字典上的投影作為表示系數(shù)，減小了算法的時間復雜度。

3.1 時間復雜度分析

在GDPL算法中主要是計算訓練階段的時間復雜度。在訓練階段 Ak和 { Pk,Dk} 交替更新，每次更新過程相同，在此以一次更新為例。固定{Pk,Dk} 由 式(10)更新 Ak， Ak更新的時間復雜度是一個逆矩陣和一個矩陣相乘的時間復雜度即m×m 的矩陣， {Dk+τI} 的 時間復雜度為 O (m3)，在 m ×nk的矩陣 { τ PkXk+Xk} 中 ， PkXk的時間復雜度為 O (mpnk)，Xk的時間復雜度也是 O (mpnk)，所以矩陣 { τ PkXk+Xk} 的 時間復雜度為 O (mpnk)。矩陣 (Dk+τI)-1和 ( τ PkXk+Xk) 相乘的時間復雜度為 O (m2nk)， 整個更新 Ak的時間復雜度為O(m3+mpnk+m2nk)。 固定 Ak， 更新 { Pk,Dk}。 Pk由式(12)進行更新，在式(14)中 p ×p 的矩陣(τXk+λ3+γI+βXLXT)的 時 間 復 雜 度 為O(p2nk+p2(n-nk)+pn2+p2n)，但是在迭代過程中該矩陣值不變，在初始化階段提前計算出來，在迭代過程中不需要重復計算，因此不影響更新 Pk的時間復雜度。只需計算(τXk+λ3+γI+βXLXT)逆矩陣的時間復雜度為 O (p3)。 Ak的時間復雜度為 O (mnp)，兩矩陣相乘的時間復雜度為O(mp2)， 更新 Pk的時間復雜度為 O (mnkp+p3+mp2)。使用ADMM更新 Dk，將ADMM算法中迭代更新次數(shù)記為H，ADDM算法中，主要計算在式(13)中 D 更新過程的時間復雜度。 Dk根據(jù)式(14)更新的，式(14)中 Xk、 Ak、 ( Ak+ρI) 的逆矩陣、 Xk(Akk+ρI)-1的時間復雜度分別為O(pnkm)、 O (m2nk)、 O (m3)、 O (pm2)， 更新 Dk整個過程的時間復雜度為 O (H(pmnk+m2nk+m3+pm2))。

3.2 收斂性分析

在目標函數(shù)式(1)中對于 { ( D,P),(A)} 的迭代更新是一個雙凸問題。在優(yōu)化求解的過程中，固定A對 D 和 P 求解是一個凸問題；固定 D和 P對 A求解也是一個凸問題，因此目標函數(shù)是一個雙凸問題。根據(jù)文獻[10]的補充材料，收斂時目標函數(shù)的能量值達到一個局部最小值。為了避免在更新過程中達到收斂條件，不同類之間單個樣本的能量不在同一個數(shù)量級上，所以，本文的收斂條件是單個樣本的能量到達某一局部最小。目標函數(shù)中各項的曲線如圖1所示。圖1只是以GDPL算法過程中使用其中一類迭代過程中的目標函數(shù)值畫出曲線為例。算法1中while后面的收斂條件為前后兩次迭代的整個目標函數(shù)值之差小于0，單個樣本的重構誤差的絕對值小于1，保證目標函數(shù)值在每次迭代過程中逐漸減小，最大迭代次數(shù)為50。

圖1 目標函數(shù)值隨迭代次數(shù)變化Fig.1 The value of the objective function varies with the number of iterations

圖1 中單個樣本的整個目標函數(shù)值在開始到40次的變化趨勢是平行趨于0，之后變成一個比較大的負值，由于相似度矩陣不是半正定矩陣，由此使圖正則項的值變成負值，并引起其他項的變化。并且由于圖像的損失函數(shù)一般都不會小于0，所以，從圖1可以看出算法在2～40次之間是局部收斂的。所以，有的實驗在第2次迭代就達到最優(yōu)值。

4 實驗結果與分析

為了驗證圖正則化字典對學習算法在圖像分類中的性能，本文在ADNI1數(shù)據(jù)集上進行驗證。ADNI由國際老年研究所、生物醫(yī)學成像和生物工程研究所、美國食品和藥物管理局、民營醫(yī)藥企業(yè)和非營利組織在2003年啟動，資金為60萬美元。ADNI的主要目標是測試是否能通過組合MRI、PET、其他生物標志物，以及臨床和神經(jīng)心理學評估來測定MCI和早期AD的進展。

在ADNI1[14]中，根據(jù)MCI患者在36個月之后的狀態(tài)，將36個月之后仍表現(xiàn)出MCI的狀態(tài)，則記為SMCI；36個月后表現(xiàn)為AD的病況，記為PMCI；沒有36個月之后的信息的患者，記為uMCI。實驗中只利用表1中顯示的有標簽的164個PMCI患者信息和100個SMCI患者信息，對MCI進展進行識別，提前預測AD。

表1 PMCI和SMCI相關信息Table1 PMCI and SMCI related information

所有實驗是使用中全局生物標志[14]和表1中顯示的 Age、MMSE、CDR-SB、RAVLT、FAQ、ADAS-cog信息的結合生物標志作為特征表示樣本，使用算法1中學習的字典對 { D ,P}，計算出樣本的編碼系數(shù)作為特征。在實驗中選擇較常用的分類器 SVM[11,14-17]、LDA[17]、KNN 作為比較方法。為了避免實驗結果的隨機性，運行100次10倍交叉驗證取最終的平均準確率(ACC)和平均ROC曲線下面的面積(AUC)，對于分類器的性能進行評價。

為了驗證提出的基于圖正則化的字典對學習方法的實驗效果比其他的實驗效果好，直接使用結合生物標志用SVM、LDA、KNN分類器分類，使用DPL方法訓練出來的字典對上的稀疏系數(shù)作為特征用分類器(SVM、LDA、KNN)做出的實驗效果，和使用GDPL方法訓練出來的字典對上的稀疏系數(shù)作為特征用SVM、LDA、KNN分類的實驗結果。最終的實驗結果是取100次10倍交叉驗證結果的平均值，對于具體實驗數(shù)據(jù)的精確度取小數(shù)點后3位。

在使用字典對算法訓練字典的過程中，算法中參數(shù)設置是選擇一個參數(shù)變化，固定其他參數(shù)，進行遍歷。選取3次十倍交叉驗證平均準確率最好。經(jīng)過遍歷參數(shù)，算法中的參數(shù)設置如表2、3所示。

表2 使用DPL稀疏系數(shù)作為特征的參數(shù)設置Table2 Parameter setting using DPL algorithm

表3 使用GDPL稀疏系數(shù)作為特征的參數(shù)設置Table3 Parameter setting of the GDPL algorithm

1) 為了驗證在基于圖正則化的字典對(GDPL)算法學習的字典對上的系數(shù)作為特征效果比直接用結合生物標志作為特征的實驗效果好。本文使用準確率(ACC)和ROC曲線下的面積(AUC)作為評價標準。

從圖2可以看出直接用結合生物標志作為特征的準確率與使用字典對學習方法的準確率相差較大，使用SVM和GDPL+SVM的實驗結果相差了2個百分點，K近鄰(KNN)和GDPL+KNN相差了6個百分點。用GDPL方法的準確率比DPL方法的準確率高。從圖2整體上看使用GDPL方法的實驗效果比DPL方法和直接使用綜合特征的效果好。圖3從算法AUC性能評價，從中可以看出使用GDPL的稀疏系數(shù)作為特征的實驗中，除了SVM外，其他的方法都比使用DPL的效果好，其中KNN的AUC最高到達92.1%。從圖2、3中整體的結果可以看出GDPL方法的實驗結果比DPL的實驗結果好。

圖2 不同方法上的準確率 (ACC)Fig.2 The accuracy of different methods

圖3 不同方法上的ROC曲線下的面積(AUC)Fig.3 Area under ROC curve in different methods

2) 將結合生物標志直接作為特征用SVM、LDA、KNN分類，使用DPL方法的稀疏系數(shù)作為特征的分類方法記為DPL+SVM、DPL+LDA、DPL+KNN，和使用GDPL方法的稀疏系數(shù)作為特征的分類方法記為GDPL+SVM、GDPL+LDA、GDPL+KNN，所用實驗結果都是記錄使用100次十倍交叉驗證的結果(平均值)畫出的盒形圖。使用準確率(ACC)、ROC曲線下面的面積(AUC)對于分類器的性能進行評估，具體實驗結果在圖4、5中顯示。

從圖4中整體上可以看出使用GDPL算法的稀疏系數(shù)作為特征的平均準確率比DPL算法的稍微好一點，比直接使用結合生物標志作為特征的平均準確率高，GDPL+KNN算法的平均準確率最高達到了83.7%。圖5顯示ROC曲線下的面積(AUC)最好的是GDPL+KNN算法，AUC達到92.1%。在圖4、5，100次實驗結果中GDPL+KNN算法結果相對集中穩(wěn)定。整體上看使用GDPL方法訓練出來的字典對上的稀疏系數(shù)作為特征的實驗結果比直接使用結合生物標志特征的結果好，GDPL+KNN實驗結果最好，并且結果比較集中穩(wěn)定，每次實驗的結果的變化不大。

圖4 使用100次十倍交叉驗證的ACC畫出的箱型圖Fig.4 Box plot for the ACC of 100 times 10-fold cross-validation

圖5 使用100次10倍交叉驗證的AUC畫出的箱型圖Fig.5 Box plot for the AUC of 100 times 10-fold cross-validation

5 結束語

本文實驗結果表明在字典對學習算法中加入圖正則項，可以提高字典對模型的識別能力，能夠更好地對圖像進行分類。另一方面，使用在字典對上的稀疏系數(shù)作為特征對輕度認知功能障礙預測可以取得更好的效果，并且在GDPL算法上的稀疏系數(shù)作為特征的實驗結果比DPL上的實驗結果好。隨著科技的發(fā)展，圖像資源越來越豐富，用戶想在大量的圖像中找到需要的圖像信息比較困難。在現(xiàn)實生活中帶標簽的數(shù)據(jù)相對于不帶標簽的數(shù)據(jù)少很多，獲得帶標簽的圖像比較困難。并且訓練樣本較少不能獲得足夠的特征去學習字典，下一步可以將無標簽的樣本用于實驗中，學習一個更完備的字典，提高模型的識別能力?？梢赃M行半監(jiān)督字典對學習，提高模型的判別能力。