兒童孤獨(dú)癥的高秩矩陣填充模型與方法

李元超， 陳 峰

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

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

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

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

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

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

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

1 HRMC算法介紹

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

(1)

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

(2)

m≥Gn6/5rlgn

(3)

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

(4)

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

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

(5)

先求得其增廣拉格朗日乘子函數(shù)：

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

(6)

然后進(jìn)行迭代更新，并且重復(fù)更新過程，直到整個算法收斂為止.

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

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

(7)

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

(8)

式中：Y和A均為輔助矩陣；Yp為原矩陣中對應(yīng)權(quán)值αp的因素的集合.增廣拉格朗日乘子函數(shù)

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

(9)

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

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

當(dāng)算法未收斂且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)

此時(shí)Y為Yp的集合.

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

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

(14)

(6) 更新乘子:

(15)

(7) 更新參數(shù):

μ=min(ρμ,μmax)

(16)

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

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

(17)

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

(18)

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

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

(19)

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

步驟(3)中，

(20)

步驟(4)中，

(21)

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

步驟(5)中，E(k+1)求法比較特殊，因?yàn)楦鶕?jù)不同的應(yīng)用背景，E的范數(shù)可以取不同類型，本文取 2.1 范數(shù)，具體的計(jì)算方法為

(22)

2 數(shù)值實(shí)驗(yàn)

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

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

2.1 測試數(shù)據(jù)填充實(shí)驗(yàn)

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

(23)

實(shí)驗(yàn)結(jié)果如表2所示.表中：rMC為矩陣填充的秩；EMC為矩陣填充誤差.

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

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

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

2.2 實(shí)際孤獨(dú)癥數(shù)據(jù)子樣本填充

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

表3 實(shí)際孤獨(dú)癥數(shù)據(jù)非隨機(jī)缺失填充結(jié)果Tab.3 Result of practical ASD data completion in NMAR

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

2.3 實(shí)證分析

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

3 結(jié)語

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