李元超， 陳 峰

(上海交通大學 工業(yè)工程與管理系， 上海 200240)

準確的兒童孤獨癥的影響因素分析對孤獨癥的早期發(fā)現與診療具有重要的作用.兒童孤獨癥(ASD)是廣泛性發(fā)育障礙的一種亞型，以男性多見，男女比例約為6∶1，起病于嬰幼兒期，主要表現為不同程度的言語發(fā)育障礙、人際交往障礙、興趣狹窄和行為方式刻板[1].孤獨癥的病因目前尚不明確，認為可能與遺傳因素和后天因素都相關.又因為孤獨癥對患兒和患兒家庭的危害較大，所以孤獨癥的早期診斷顯得特別重要.清晰準確地了解孤獨癥的影響因素可以有效地輔助孤獨癥的診斷，在孤獨癥的實際診療過程中發(fā)揮重要的作用，而臨床數據中存在著大量的數據缺失現象.一般而言，認為10%～20%的數據缺失量即會對統(tǒng)計結果造成影響，使之偏離實際情況.針對數據缺失現象，統(tǒng)計學家提出了很多填補缺失值的算法，如多重填補(MI)，隨機森林(RF)，最大期望(EM)等.

矩陣填充(MC)方法是目前解決數據缺失的有效方法，由壓縮感知發(fā)展而來.所謂壓縮感知，指的是利用信號的稀疏特性，在遠遠小于奈奎斯特(Nyquist)采樣率的條件下，用隨機采樣獲取信號的離散樣本，然后通過非線性算法完美重建信號.之后，Candès等[2]將壓縮感知的原理拓展到二維層面，使得原本的向量重建變?yōu)閷仃囍腥笔г氐奶钛a，并且稱其為矩陣填充.矩陣填充在處理大規(guī)模數據的表現方面尤其突出，時間復雜性低且精度高.特別是在處理非結構化數據方面，如圖形重建、數字識別和圖形壓縮等，矩陣填充方法表現出了極大的優(yōu)勢，而且在缺失類型為非隨機缺失時，矩陣填充也表現良好.

近年來矩陣填充的新方法不斷被提出，原有方法的改進報道也很常見.常用的低秩矩陣填充方法有SVT (Singular Value Thresholding)算法、APGL (Accelerated Proximal Gradient Linesearch-like)算法、IALM(Inexact Augmented Lagrange Multiplier)算法等. 許多新的正則化方式被應用到矩陣填充的凸優(yōu)化建模中，包括交替最小化、交替最小二乘法和截斷核范數等.Xu等[3]將交替方向算法應用到非負矩陣填充中，Recht 等[4]提出了利用平行隨機梯度下降法求解大規(guī)模矩陣填充的方法.

矩陣填充的應用方向廣泛，主要有協(xié)同濾波、系統(tǒng)識別、傳感器網絡和圖像處理等方面.經典的Netflix問題就是一個協(xié)同濾波矩陣填充問題.根據Netflix問題，發(fā)展出了各種推薦系統(tǒng)的用戶喜好預測問題.曾廣翔[5]進行了面向推薦系統(tǒng)的矩陣填充算法研究.Yeganli等[6]將SVT算法應用于圖形重建的過程中，有效地恢復了損壞圖形中的紋理部分.Li等[7]利用低秩矩陣填充進行了圖形的修復，提出了一種魯棒性較好的算法.Ji等[8]研究了魯棒視頻去噪，提出基于矩陣填充的視頻塊的去噪算法，結果顯著優(yōu)于其他去噪算法.在醫(yī)學上，矩陣填充方法被廣泛應用于醫(yī)學影像處理方面，主要用于提取磁共振的影像的特征，去除影像中的噪聲以及修復影像[9].

在待填充矩陣稀疏度低的情況下，低秩矩陣的填充效率低.這里稀疏度指矩陣中零元素占總元素的比例.而在日常應用中，待填充矩陣的稀疏性往往不夠強烈，此時低秩矩陣填充的算法就變得十分遲鈍，表現難以令人滿意.針對這種情況，統(tǒng)計學家提出了高秩矩陣填充的概念.高秩矩陣填充采用子空間聚類相關的思路.認為數據來自k個不同的未知線性空間，任務是將數據分別歸類到自己所屬的子空間中.近年來，許多高維數據背景下的子空間聚類算法被提出.Elhamifar[10]將矩陣的自我表示模型用于高秩矩陣填充.Fan等[11]將交替方向乘子(ADMM)應用于一般的矩陣填充，并且解決了若干典型圖像修復問題和子空間聚類問題，得到了令人滿意的效果.

本文將ADMM算法應用于矩陣填充，在現有的高秩矩陣填充的成果基礎上，提出了一種考慮待填充矩陣中各因素的重要性的高秩矩陣填充(HRMC)算法.其創(chuàng)新性在于結合矩陣填充的特征，根據數據中各要素的重要性在問題建模時賦予不同的權重參數，提高了算法的效率，在解決高秩矩陣填充問題方法表現較為突出.在數值實驗部分采用了生成的測試數據與實際孤獨癥就診數據，算法精度均表現優(yōu)秀，填充結果合乎預期.

1 HRMC算法介紹

矩陣填充問題的一般描述如下：

(1)

式中：X為待恢復矩陣；M為X中已知元素的集合，且i,j∈Ω，Ω為矩陣中已知元素的下標集合.但是，該問題為NP-hard，且時間復雜性為指數[2]，故求解起來十分困難.此時，Candès等[2]指出可以通過求解原問題的近似問題來求解：

(2)

m≥Gn6/5rlgn

(3)

式中:r為矩陣的秩.但是，這種矩陣填充的方法僅僅適用于低秩矩陣的填充，而在日常的應用中，往往會遇到需要恢復高秩矩陣甚至滿秩矩陣的情況.通常而言，高秩矩陣填充往往與子空間聚類(SSC)有關，所謂子空間聚類，指有向量x1,x2,…,xn∈Rn，可以被聚類為最多k個子空間.SSC的一般描述如下：

(4)

式中：C為矩陣X的自我表示矩陣，將矩陣X表示成X本身的列的線性組合；E為誤差；l為范數，可根據實際問題取某一個特定的范數；λ為由原數據的噪聲情況確定，原數據噪聲特別大時，λ取比較小的值，反之則取較大的值.

本文結合矩陣填充的思路，利用ADMM算法來實現.ADMM算法通過求解一系列結構相似的子問題來優(yōu)化未知變量和參數[12].ADMM算法的一般描述如下：

(5)

先求得其增廣拉格朗日乘子函數：

Lμ(x,z,y)=f(x)+g(z)+yT(ax+bz-c)+

(6)

然后進行迭代更新，并且重復更新過程，直到整個算法收斂為止.

因為矩陣是不完整的，所以要解決的問題較SSC的研究問題增加了一個約束條件.在實際應用中很難知道待填充的矩陣的秩，故引入了參數αp和λ.其中：αp影響填充矩陣的秩，對較高秩的待填充矩陣，αp應該取比較小的值，反之則取一個較大的值.一般而言，待研究的結構化數據構成的目標矩陣中往往存在關鍵因素和非關鍵因素，為了提高算法的運行速度和效率，對關鍵因素與非關鍵因素分別賦權值.如此可以使算法將更多資源投入關鍵因素的缺失項填充過程中，提升效率.注意到約束X=XC+E中，對于不確定的X和C，它是非凸的，而對每一個確定的X和C來說，該約束都是凸的，如此則可用ADMM算法求解.

本文研究的高秩矩陣填充整個問題描述如下：

(7)

為了方便用ADMM求解，式(7)可以表示為

(8)

式中：Y和A均為輔助矩陣；Yp為原矩陣中對應權值αp的因素的集合.增廣拉格朗日乘子函數

Lμ=‖C‖l+∑αp‖Yp‖*+λ‖E‖l+

(9)

圖1 HRMC算法流程Fig.1 HRMC algorithm process

輸入：原始矩陣X，矩陣中已知值M，參數αp和λ.

當算法未收斂且k

(1) 更新A(k+1)，即

(10)

(2) 更新C(k+1)，即

(11)

(3) 更新X(k+1)，即

(12)

(4) 更新Y(k+1)，即

Y(k+1)=arg minα‖Y(k)‖*+

(13)

此時Y為Yp的集合.

(5) 更新E(k+1)，即

E(k+1)=arg minλ‖E(k)‖*+

(14)

(6) 更新乘子:

(15)

(7) 更新參數:

μ=min(ρμ,μmax)

(16)

ADMM的收斂性已被Stephen Boyd等人證明，且本文在實際求解中，算法均可正常收斂.

在上面的算法描述中，各個迭代步驟都有相似的表達形式.本文可以通過如下方法求A(k+1).即

(17)

同理，在步驟(2)中，C(k+1)的求法是：

(18)

式中：Φτ(*)是一個近鄰收縮閾值算子[13]，其具體定義為

Φτ(ω)=max{|ω|-τ,0}sgn(ω)

(19)

式中：sgn(*)為符號函數.

步驟(3)中，

(20)

步驟(4)中，

(21)

式中：Θ為奇異值閾值算子[14].

步驟(5)中，E(k+1)求法比較特殊，因為根據不同的應用背景，E的范數可以取不同類型，本文取 2.1 范數，具體的計算方法為

(22)

2 數值實驗

本文利用了人工生成的測試數據和來自上海市精神衛(wèi)生中心孤獨癥門診的患兒就診數據進行案例分析.在中國，孤獨癥患者的數據十分珍貴.因孤獨癥未得到社會和家庭的足夠重視，前來就診的患兒較少，而且患兒家長在錄入基本信息和填寫有關量表的時候，由于自身的文化程度或其他原因，往往會有漏填、錯填的現象出現，故原始數據中有不少缺失項需要處理.又因數據珍貴，若刪除缺失觀測，原來的患者分布統(tǒng)計會有較大偏差，而且孤獨癥各個量表的得分，患者的基本情況各項相關性較弱，故整個數據矩陣的秩較高.

數值實驗流程：首先采用生成的測試矩陣測試；然后利用實際的孤獨癥數據，抽取有代表性的無缺失樣本進行測試，并且與常用的參數化填補方式和低秩矩陣填充算法做對比；最后利用全部的實際數據進行矩陣填充實驗，觀察算法的效率和填充是否合理.

2.1 測試數據填充實驗

矩陣填充的誤差可以表示為

(23)

實驗結果如表2所示.表中：rMC為矩陣填充的秩；EMC為矩陣填充誤差.

表1 測試矩陣配置Tab.1 Parameters of test matrix

表2 測試矩陣填充情況Tab.2 Result of matrix completion

由表2可以看出，隨機生成的測試數據實驗結果較好，可以正常收斂，且矩陣填充誤差均在可接受范圍內.該算法在不同的缺失率下均可使填充后矩陣的秩與原矩陣相等.在隨機缺失的前提下，δ分別為 0.25 和 0.5 時基本可以正常填充，δ到達 0.75 時填充效果就有了明顯的下降.這與低秩矩陣填充的經驗不符.原因是低秩矩陣中有效的元素本身較少，大部分元素均與有效元素相關，即使是高度缺失的矩陣中仍然保留有足夠完整恢復原矩陣的信息；而高秩矩陣中本身的有效元素較多，高度缺失的情況下有效信息的損毀過于嚴重，以至于難以將原矩陣完整恢復.

2.2 實際孤獨癥數據子樣本填充

由表4可見，HRMC在3種算法中表現最為優(yōu)秀，MI緊隨其后，SVT最差，而且隨著缺失度增加，矩陣填充誤差隨之上升.其原因是MI的原理為貝葉斯預測，對矩陣的秩不敏感，而SVT對數據的低秩性和稀疏性要求較高.而MI在缺失模式為NMAR時，填充誤差急劇上升，HRMC則不會.這說明MI在處理MAR數據表現較為出色，但無法很好地處理NMAR數據，HRMC則對數據的缺失類型不敏感.若是能尋找一個原始數據的稀疏表示，則一般低秩矩陣填充算法也可應用.綜上所述，HRMC在處理實際孤獨癥數據時表現良好，可以應用到大規(guī)模的數據處理中.

表3 實際孤獨癥數據非隨機缺失填充結果Tab.3 Result of practical ASD data completion in NMAR

表4 HRMC與其他算法對比結果Tab.4 Comparison of HRMC and other algorithms

2.3 實證分析

經過必要的數據前處理，原始的孤獨癥患者數據(包括基本情況和各量表作答情況)被整理為一個499×143的矩陣，矩陣中共有 71 357 個數據，其中 15 497 個數據缺失，缺失度為 21.72%；共有 12 433 個值為0，稀疏度為 17.4%，為稠密矩陣.對該矩陣應用HRMC算法進行矩陣填充，結果很好，缺失值的填充結果均符合各項參數的取值范圍，而且速度極快，大約 1 000 步迭代后即會收斂.

3 結語

本文研究了高秩矩陣的矩陣填充問題，提出了一種基于ADMM算法的高秩矩陣填充算法(HRMC).該算法利用對偶最小化的方法，使得矩陣填充在矩陣本身的秩比較高(甚至滿秩)，矩陣中的無效元素比較少的時候仍然能以較高的概率恢復原矩陣.本文利用生成的測試數據和截取的實際孤獨癥數據進行測試，并且將HRMC與一般的參數化方法和低秩矩陣填充方法的表現做對比，結果是HRMC的精確度要顯著優(yōu)于其他算法.不足之處在于全部實際孤獨癥數據的填充由于原始數據的缺失，故無法精確衡量填充結果.另外，HRMC算法對數據歸一化要求高，若數據的各個參數取值波動巨大時，該算法收斂速度較慢.HRMC算法不僅在醫(yī)療數據的填補方面，在圖形修復、模式識別等領域應該也有不錯的表現和廣闊的應用前景.