基于超圖的多模態特征選擇算法及其應用*

彭 瑤，祖 辰，張道強

南京航空航天大學 計算機科學與技術學院，南京 211106

1 引言

阿爾茨海默癥（Alzheimer's disease，AD），又稱老年癡呆癥，是一種進行性發展的中樞神經系統變性病，多起病于老年期，病程發展緩慢并且不可逆。臨床上表現為日常生活能力進行性減退，并有各種神經精神癥狀和行為障礙[1]。老年癡呆癥是影響老年人健康的頑癥，現在能做到的就是早期發現，早期治療，以延緩癡呆病程的發展[2]。

現有的研究表明，阿爾茨海默癥與大腦的結構萎縮、新陳代謝改變、病理性淀粉樣蛋白沉積有關[3]。到目前為止，已經有多個生物標記被證明對AD的診斷敏感，如：能夠測定腦萎縮的結構磁共振成像（MRI）[4-5]、能夠量化代謝減退的功能成像（FDGPET）等[6-7]。這些通過不同成像技術得到的生物標記可以看作是不同模態的數據。

近年來，利用多模態數據進行學習已經成為機器學習領域的熱門問題之一。多模態數據是指對同一事物從不同角度描述所得到的數據。不同的圖像模態之間能夠提供必要的互補信息，整合多模態的數據能夠發現單模態中無法發現的信息。在醫學診斷中，利用多模態的數據來診斷腦部疾病，能夠提高診斷的敏感性和特異性。多個實驗結果也說明了多模態分析方法能挖掘不同模態間的相關信息、互補診斷信息，能獲得比單模態分析方法更好的性能[8-11]。

由于醫學影像中，數據樣本少，特征維數大，在實際應用中這是典型的小樣本問題[12]。研究人員已經提出多種針對多模態醫學影像數據的特征選擇算法。如Jie等人[13]提出了流形正則化的多模態特征選擇算法，通過多任務學習和流形正則化項來保留模態之間的關聯信息以及每個模態的數據分布信息，從而選擇出更具有判別性的特征。Zu等人[14]提出了標簽對齊的多模態特征選擇算法，通過在多任務學習的目標函數中加入標簽對齊正則化項來使具有相同標簽不同模態的樣本在投影后的標號空間中距離更接近。現有的多模態特征選擇算法都只考慮了樣本之間的成對關系，而忽略了樣本之間的高階關系，充分利用樣本之間的這種先驗分布知識，有利于選擇出更具有判別性的特征。

本文提出了基于超圖的多模態特征選擇算法，具體而言，將每組模態當作一組任務，利用l2,1范數進行特征選擇，保證不同模態相同腦區的特征被選中。通過構建超圖來刻畫樣本之間的高階關系，從而充分利用每組模態數據內部的分布先驗。最后，利用多核支持向量機對選擇出來的特征進行融合分類。在ADNI數據集上對本文方法進行了驗證，分類實驗結果表明了提出方法的有效性。

2 方法

基于超圖的多模態特征選擇算法是在多任務特征選擇的基礎上，通過嵌入超圖知識來保留樣本之間的高階信息，最后通過多核支持向量機對選擇出來的特征進行融合分類。

2.1 多任務特征選擇

多任務學習[15-16]是對多個相關任務同時進行學習，并且通過學習多個任務之間的相關信息來提高學習效率。多任務學習被廣泛應用到許多領域，包括醫療診斷、生物醫學信息、文本分類等。本文將醫學影像中每個模態的特征選擇看作是一個任務，進行多個模態的聯合特征選擇。

給定第m個模態的訓練集，其中表示第i個樣本對應的特征列向量，d表示特征的維度，N表示樣本的數目。令Y=[y1,y2,…,yi,…,yN]T∈RN表示N個樣本對應的標簽向量，其中yi的值為1或-1。多任務特征選擇（multitask feature selection，MTFS）模型[17]的目標公式如下：

其中，wm表示第m個模態的回歸系數向量，所有模態的系數向量都來自一個系數矩陣W=[w1,w2,…,wm,…,wM]∈Rd×M，M表示模態數目。在式（1）中，||W||2,1表示矩陣W的l2,1范數，，其中wi表示矩陣W的第i行。λ是正則化系數，控制著式（1）中兩項的相對權重。

l2,1范數||W||2,1可以看作矩陣W的每一行的l2范數之和[17]。多任務特征選擇利用了任務之間的相關信息，不同任務的變量之間有相似的稀疏模式。l2,1范數將不同模態的同一特征的權重聯合起來，使得一部分共同特征能夠被聯合選擇出來。多任務特征選擇模型最后得到的權重矩陣W的多行元素都為0，這就是“組稀疏”性。多任務特征選擇模型中，當只有一個任務時，就退化成為Lasso（least absolute shrinkage and selection operator）模型[18]。

2.2 超圖學習

在機器學習問題中，常常假定研究的物體之間存在成對的關系，這種關系可以很自然地用圖來表示。在傳統圖中，頂點表示物體，如果兩個頂點之間有聯系，就用一條邊來連接。圖可以是有向或者無向的，這取決于物體之間的成對關系是對稱還是非對稱的。

但是，在許多實際問題中，物體之間存在更復雜的關系，無法用成對關系來表示。因此，研究者們提出使用超圖對三者及三者以上的關系進行刻畫。在超圖中，一條超邊可以連接兩個及以上的頂點（超邊實際上是頂點集的子集），傳統圖是超圖的一個特例。

使用超圖來對更復雜的關系（如高階關系）進行建模[19-21]。如圖1左側所示，藍色頂點分別被不同的超邊包含，每條超邊可以包含兩個以上的頂點。特別是當超邊中所包含的頂點數目為2時，該超邊退化為普通邊。目前，超圖學習已經被廣泛地應用于許多實際應用中[22-23]。

Fig.1 Hypergraph model圖1 超圖模型

令G(V,E,a)表示一個超圖，其中V表示頂點的集合，E表示超邊的集合，a表示各超邊權重的集合。這里，每一條超邊ei(i=1,2,…,Ne)都被賦予了一個權重a(ei)。對于超圖G，它的關聯矩陣H用于表示各頂點之間的關系，具體地，矩陣H的第i行、第j列的元素若是1，則表示超圖的第j條超邊包含第i個頂點，若是0，則表示不包含，如圖1右側所示。矩陣H定義如下：

在關聯矩陣的基礎上，各頂點的度和各超邊的度分別被定義如下：

另外，令Dv和De分別表示各對角線元素為頂點的度和超邊的度的對角矩陣，令A表示各超邊權重的對角矩陣，即Aii=a(ei)。研究人員提出了多種計算超圖拉普拉斯矩陣的方法，大致可以分為兩類：第一種方法是在原始的超圖上構建一個簡單圖，如星形擴展[24]；第二種方法是類比簡單圖拉普拉斯矩陣來定義超圖拉普拉斯矩陣[19]。上述兩種方法都很相似。本文采用文獻[19]提出的超圖拉普拉斯矩陣計算方法，即定義半正定矩陣Lh為超圖的拉普拉斯矩陣：

超圖的構建在超圖學習中是最關鍵的一步。根據文獻[19]提出的方法，采用KNN算法來構建超圖。具體來說，把每個頂點看作一個中心，計算出中心點與其他頂點的歐式距離，再把中心點與距它最近的k個頂點連接起來，構成了一條超邊。給定N個樣本，就能構建出N條超邊。本文將每條超邊的權重都賦值為1，即a(ei)=1。

2.3 基于超圖的多模態特征選擇

根據超圖拉普拉斯矩陣，超圖正則化項定義如下：

直觀上，式（6）表示想要保留在原始特征空間中的數據結構信息，這種高階結構信息通過超圖拉普拉斯矩陣Lh反映出來。對每一個模態的樣本都構建一個超圖，保留每一個模態的高階結構信息。在多任務特征選擇的目標公式中加入超圖正則化項，就構成了基于超圖的多模態特征選擇的目標公式：

在本文的模型中，不僅用多任務特征選擇保證了不同模態相同腦區的特征被選中，考慮了模態之間的關系，還利用了超圖拉普拉斯矩陣保留同一模態樣本之間的高階結構信息。現有的多模態特征選擇算法，都只考慮了樣本之間的成對關系，而忽略了樣本之間的高階關系。

2.4 優化算法

目前已有許多方法可以對目標式（7）進行求解，例如ADMM（alternating direction method of multipliers）和APG（accelerated proximal gradient）算法等。本文采用APG算法來求解問題[25-26]。將式（7）中的目標函數分為光滑項f(W)和非光滑項g(W)：

用下面這個函數來近似f(W)+g(W)：

其中，‖?‖F是Frobenius范數；?f(W(k))是f(W)在第k次迭代點W(k)處的梯度；l是步長。APG算法的更新步驟是：

其中，l可以通過線性搜索得到；

APG算法的關鍵就是如何有效地計算更新步驟。研究表明這個問題可以分解成d個獨立的子問題，而這些子問題的解可以很容易得到[27]。

另外，根據文獻[26]提出的方法，可以通過Q(k)來計算定義如下：

2.5 多核支持向量機

多核支持向量機可以有效地對多模態的數據進行融合，并對阿爾茨海默癥進行分類[8]。給定訓練集，第m個模態的核函數為，對多模態核函數進行融合以后，可以得到k(xi,xj)=，由此可以得到多核支持向量機的對偶形式：

其中，N為訓練樣本總數。

給定一個新的測試樣本x0，決定樣本標簽的決策函數定義如下：

本文用LIBSVM工具包[28]來實現SVM（support vector machine）分類器，核函數采用線性核，βm通過網格搜索在訓練集上進行交叉驗證得到。

3 實驗及結果分析

3.1 實驗方法

本文在標準數據集ADNI的202個樣本上進行了實驗，其中包括51名阿爾茨海默癥患者，99名輕度認知功能障礙患者（mild cognitive impairment，MCI），其中輕度認知障礙包含43名MCI轉換病人（即在18個月內從MCI轉換為AD，MCI-C）和56名MCI不轉換病人（即在18個月內不從MCI轉換為AD，MCINC），52名正常人（normal control，NC）。采用了MRI和PET兩種醫學圖像數據，標注出每個樣本的MRI和PET圖像的93個感興趣的區域（腦區），并計算出樣本的每個感興趣區域的MRI圖像灰質組織體積，對PET圖像計算出相應感興趣區域的強度均值。這樣，就得到了MRI圖像的93個特征和PET圖像的93個特征。本文在數據集上進行了3組實驗，分別為AD vs.NC，MCI vs.NC，MCI-C vs.MCI-NC。

在本實驗中，采用了十折交叉驗證方法驗證各方法的效果。具體來說，將整個樣本集平均地劃分為10份。在每一次的交叉驗證實驗中，都取其中的9份作為訓練集，剩下的1份作為測試集。這樣獨立進行10次實驗，以消除隨機劃分數據集所引入的偏差。將10次分類的精度取平均得到最終的分類精度。目標公式中最優的參數值λ、κ、μ以及多核分類器中的βm，通過在訓練集上再進行一次十折交叉驗證來尋找。用LIBSVM[28]工具包，并選擇線性核函數來實現SVM分類器。最后，計算出分類的精度（ACC）、敏感性（SEN）和特異性（SPE）來評價各方法的性能。

還將本文提出的方法與現有的3種多模態分類方法進行了對比。第一種方法是不經過特征選擇，直接進行多模態融合分類（用Baseline來表示）[7]。第二種方法是將MRI的93維特征和PET的93維特征直接拼接起來，構成一個186維的特征向量，再用t-test方法在該特征向量上進行特征選擇，最后用SVM進行分類（t-test SVM）。第三種方法是將MRI和PET連接成186維的特征向量，再用Lasso進行特征選擇，最后用SVM在選擇出來的特征上進行分類（Lasso SVM）。

3.2 實驗結果

AD vs.NC以及MCI vs.NC的分類結果如表1所示。可以看到，本文方法分類性能最好。在AD vs.NC的實驗中，本文方法能達到95.85%的精度，而在其他3種方法中，精度最高的是Baseline達到的94.13%。此外，本文方法敏感性達到了97.84%，也就是能將更多的AD患者準確地識別出來。在MCI vs.NC的實驗中，本文方法能達到82.19%的精度，而在其他3種方法中，精度最高的是Lasso達到的76.89%。此外，本文方法敏感性也能達到94.34%。在該組實驗中，敏感性與特異性的差別較大，如表1所示，本文得到的敏感性較高，但是特異性較低。在醫學診斷中，誤將一個患者診斷為正常人和誤將一個正常人診斷為患者所付出的代價是不一樣的。能得到較高的敏感性也就是能盡可能少地將患者診斷為正常人，以免因為誤診而耽誤治療。

Table 1 Results ofAD vs.NC and MCI vs.NC表1 AD vs.NC和MCI vs.NC實驗結果 %

MCI-C vs.MCI-NC的實驗結果如表2所示。可以看到，本文方法能在分類中達到74.70%的精度，而其他3種方法中，精度最高的是Lasso達到的69.10%。

Table 2 Results of MCI-C vs.MCI-NC表2 MCI-C vs.MCI-NC實驗結果 %

此外對3組實驗結果的精度、敏感性、特異性的標準差進行了計算，本文方法得到的實驗結果的標準差也比較小，說明了本文方法較其他方法更加穩定。

由于每次交叉驗證中所選擇的腦區不盡相同，統計出了最常被選中的10個腦區，如表3、圖2所示。其中所選中的腦區如海馬體是與長期記憶非常相關的大腦區域，與已知的AD/MCI相關文獻一致[29-30]，再例如杏仁核與三角部額下回也證明是與AD有關的腦區[31]。

Table 3 Top 10 ROIs selected by the proposed method for MCI表3 MCI分類中最常被選中的10個腦區

4 總結

本文提出了一種基于超圖的多模態特征選擇方法，將不同成像技術得到的醫學圖像數據作為不同的模態，進行多任務特征選擇，保證不同模態的同一腦區同時被選中，同時通過加入超圖正則化項來保留同一模態樣本之間的高階結構信息，這樣能選擇出更具有判別性的腦區。分類實驗結果也證明了本文方法的有效性。但是，本文實驗沒有考慮到超邊的權重信息，可能會丟失掉一些信息。在今后的工作中，嘗試對超邊的權重進行優化，盡可能地少丟失信息，以達到更好的實驗結果。

Fig.2 Top 10 ROIs selected by the proposed method for MCI圖2 MCI分類中最常被選中的10個腦區圖示

[1]Lin Shuwu.An introduction toAlzheimer’s disease[J].Journal of Shenyang Medical College,2013,15(1):1-4.

[2]Liu Liping.Progress in pathology of Alzheimer's disease[J].Chinese Journal of Clinical Rehabilitation,2003,7(5):785-786.

[3]Jack C R,Knopman D S,Jagust W J,et al.Hypothetical model of dynamic biomarkers of the Alzheimer's pathological cascade[J].The Lancet Neurology,2010,9(1):119-128.

[4]de Leon M J,Mosconi L,Li J,et al.Longitudinal CSF isoprostane and MRI atrophy in the progression toAD[J].Journal of Neurology,2007,254(12):1666-1675.

[5]Du Antao,Schuff N,Kramer J H,et al.Different regional patterns of cortical thinning inAlzheimer's disease and frontotemporal dementia[J].Brain,2007,130(4):1159-1166.

[6]de Santi S,de Leon M J,Rusinek H,et al.Hippocampal formation glucose metabolism and volume losses in MCI and AD[J].Neurobiology ofAging,2001,22(4):529-539.

[7]Morris J C,Storandt M,Miller J P,et al.Mild cognitive im-pairment represents early-stage Alzheimer disease[J].Archives of Neurology,2001,58(3):397-405.

[8]Zhang Daoqiang,Wang Yaping,Zhou Luping,et al.Multimodal classification of Alzheimer's disease and mild cognitive impairment[J].Neuroimage,2011,55(3):856-867.

[9]Westman E,Muehlboeck J S,Simmons A.Combining MRI and CSF measures for classification of Alzheimer's disease and prediction of mild cognitive impairment conversion[J].Neuroimage,2012,62(1):229-238.

[10]Landau S M,Harvey D,Madison C M,et al.Comparing predictors of conversion and decline in mild cognitive impairment[J].Neurology,2010,75(3):230-238.

[11]Gray K R,Aljabar P,Heckemann R A,et al.Random forestbased similarity measures for multi-modal classification of Alzheimer's disease[J].Neuroimage,2012,65:167-175.

[12]Zhou Zhihua.Machine learning[M].Beijing:Tsinghua University Press,2016:247-249.

[13]Jie Biao,Zhang Daoqiang,Cheng Bo,et al.Manifold regularized multitask feature learning for multimodality disease classification[J].Human Brain Mapping,2015,36(2):489-507.

[14]Zu Chen,Jie Biao,Liu Mingxia,et al.Label-aligned multi-task feature learning for multimodal classification of Alzheimer's disease and mild cognitive impairment[J].Brain Imaging&Behavior,2016,10(4):1148-1159.

[15]Evgeniou T,Pontil M.Regularized multi-task learning[C]//Proceedings of the 10th International Conference on Knowledge Discovery and Data Mining,Seattle,Aug 22-25,2004.New York:ACM,2004:109-117.

[16]Kumar A,Daumé III H.Learning task grouping and overlap in multi-task learning[C]//Proceedings of the 29th International Conference on Machine Learning,Edinburgh,Jun 27-Jul 3,2012.New York:Omni Press,2012:1383-1390.

[17]Yuan Ming,Lin Yi.Model selection and estimation in regression with grouped variables[J].Journal of the Royal Statistical Society,2006,68(1):49-67.

[18]Tibshirani R.Regression shrinkage and selection via the lasso[J].Journal of the Royal Statistical Society:Series B Methodological,1996,58(1):267-288.

[19]Zhou Dengyong,Huang Jiayuan,Sch?lkopf B.Learning with hypergraphs:clustering,classification,and embedding[C]//Proceedings of the 20th Annual Conference on Neural Information Processing Systems,Vancouver,Dec 4-7,2006.Cambridge:MIT Press,2007:1601-1608.

[20]Bu Jiajun,Tan Shulong,Chen Chun,et al.Music recommendation by unified hypergraph:combining social media information and music content[C]//Proceedings of the 18th International Conference on Multimedia,Firenze,Oct 25-29,2010.New York:ACM,2010:391-400.

[21]Wang Fei,Zhang Changshui.Label propagation through linear neighborhoods[J].IEEE Transactions on Knowledge&Data Engineering,2007,20(1):55-67.

[22]Gao Yue,Wang Meng,Tao Dacheng,et al.3-D object retrieval and recognition with hypergraph analysis[J].IEEE Transactions on Image Processing,2012,21(9):4290-4303.

[23]Ji Rongrong,Gao Yue,Hong Richang,et al.Spectral-spatial constraint hyperspectral image classification[J].IEEE Transactions on Geoscience&Remote Sensing,2014,52(3):1811-1824.

[24]Zien J Y,Schlag M D F,Chan P K.Multilevel spectral hypergraph partitioning with arbitrary vertex sizes[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,1999,18(9):1389-1399.

[25]Nesterov Y.Introductory lectures on convex optimization:a basic course[M].Springer US,2013.

[26]Chen Xi,Pan Weike,Kwok J T,et al.Accelerated gradient method for multi-task sparse learning problem[C]//Proceedings of the 9th International Conference on Data Mining,Miami,Dec 6-9,2009.Washington:IEEE Computer Society,2009:746-751.

[27]Liu Jun,Ye Jieping.Efficient ? 1/?q norm regularization[J/OL].(2010-09-24).arXiv:1009.4766.

[28]Chang C C,Lin C J.LIBSVM:a library for support vector machines[J].ACM Transactions on Intelligent Systems and Technology,2011,2(3):27.

[29]Wolf H,Jelic V,Gertz H,et al.A critical discussion of the role of neuroimaging in mild cognitive impairment[J].Acta Neurologica Scandinavica Supplementum,2003,179:52-76.

[30]Poulin S P,Dautoff R,Morris J C,et al.Amygdala atrophy is prominent in early Alzheimer's disease and relates to symptom severity[J].Psychiatry Research:Neuroimaging,2011,194(1):7-13.

[31]Cheng Liuquan,Cai Youquan,Xie Hengge,et al.MRI volumetry of amygdala and hippocampal formation in the diagno-sis of Alzheimer disease[J].Chinese Journal of Radiology,1998,32(12):827-832.

附中文參考文獻:

[1]林樹無.簡述阿爾茨海默病[J].沈陽醫學院學報,2013,15(1):1-4.

[2]劉麗萍.阿爾茨海默癥病理學研究進展[J].中國臨床康復,2003,7(5):785-786.

[12]周志華.機器學習[M].北京:清華大學出版社,2016:247-249.

[31]程流泉,蔡幼銓,解恒革,等.Alzheimer病杏仁核海馬結構體積的MRI測量[J].中華放射學雜志,1998,32(12):