張喜蓮，劉新偉，樊明宇

(溫州大學(xué)數(shù)理與電子信息工程學(xué)院，浙江溫州 325035)

隨著信息技術(shù)的快速發(fā)展，許多行業(yè)都會涉及到帶有大量特征的高維數(shù)據(jù)，這些高維數(shù)據(jù)經(jīng)常包含冗余特征和噪聲特征等，傳統(tǒng)的機器學(xué)習(xí)方法難以直接對此類數(shù)據(jù)進(jìn)行分析，于是降維就成了機器學(xué)習(xí)與模式識別領(lǐng)域中的一個關(guān)鍵問題．所謂降維，就是指采用某種映射方法，將原高維空間中的數(shù)據(jù)點映射到低維度的空間中，從而挖掘出隱藏在高維觀測數(shù)據(jù)中有意義的低維結(jié)構(gòu)，來研究數(shù)據(jù)屬性．在很多模式識別應(yīng)用中，降維是數(shù)據(jù)預(yù)處理的重要組成部分．

在過去的數(shù)十年里，研究學(xué)者提出了許多經(jīng)典而有效的降維方法，如PCA[1]、LPP[2]、SLPP[3]、CLPP[3]、NPE[4]、GNMF[5]、DUDR[6]等．根據(jù)數(shù)據(jù)的有無標(biāo)簽信息，降維方法可分為有監(jiān)督降維和無監(jiān)督降維．有監(jiān)督降維需要數(shù)據(jù)都有類別標(biāo)簽信息，而標(biāo)記大量的無標(biāo)簽數(shù)據(jù)需要花費大量的人力和物力；無監(jiān)督降維僅利用了無標(biāo)簽數(shù)據(jù)的信息，無法利用少量有標(biāo)簽數(shù)據(jù)的信息．在機器學(xué)習(xí)中，往往會遇到大量無標(biāo)簽的數(shù)據(jù)和少量有標(biāo)簽的數(shù)據(jù)，單純的無監(jiān)督降維和有監(jiān)督降維都不能達(dá)到令人滿意的效果．同時利用這些有標(biāo)簽的數(shù)據(jù)和無標(biāo)簽的數(shù)據(jù)可以提高降維的效果，因此，半監(jiān)督降維就成為了近幾年的研究熱點．

本文提出一種結(jié)構(gòu)正則化半監(jiān)督降維算法，主要貢獻(xiàn)是：

1）能夠?qū)W到兩種形式的數(shù)據(jù)結(jié)構(gòu)特征，軟數(shù)據(jù)結(jié)構(gòu)和硬數(shù)據(jù)結(jié)構(gòu)．成對數(shù)據(jù)點之間以實數(shù)型定義的相似性表達(dá)了軟數(shù)據(jù)結(jié)構(gòu)；通過數(shù)據(jù)分割可以學(xué)到數(shù)據(jù)的分類信息，稱為硬數(shù)據(jù)結(jié)構(gòu)．

2）數(shù)據(jù)結(jié)構(gòu)化和降維的結(jié)果交替優(yōu)化，更好的數(shù)據(jù)結(jié)構(gòu)能夠保證得到更優(yōu)的降維結(jié)果，同時，更好的降維結(jié)果能夠幫助得到更好的數(shù)據(jù)結(jié)構(gòu)．因此，在本文的框架中，數(shù)據(jù)的結(jié)構(gòu)化學(xué)習(xí)和降維的每個子任務(wù)可以相互促進(jìn)提升．

3）在降維的回歸框架中，軟數(shù)據(jù)結(jié)構(gòu)和硬數(shù)據(jù)結(jié)構(gòu)被公式化為正則化項，在保證收斂的情況下，這個算法能夠有效地優(yōu)化計算與實現(xiàn)．

1 提出的框架

1.1數(shù)據(jù)結(jié)構(gòu)化學(xué)習(xí)

假設(shè)在數(shù)據(jù)子空間的一個聯(lián)合體中，每個數(shù)據(jù)點能夠被其它數(shù)據(jù)點線性表出，公式化如下：

這里μ是正則化項，其目的是使原始數(shù)據(jù)的先驗條件為均勻分布．顯而易見，樣本較近的數(shù)據(jù)點對應(yīng)該有較大的相似性，相似矩陣S的估計能夠被當(dāng)成一種局部的結(jié)構(gòu)化特點．自表述模型（1）是保持全局和稀疏重構(gòu)數(shù)據(jù)結(jié)構(gòu)化的，而自適應(yīng)的鄰接模型（2）是以數(shù)據(jù)的局部相似性為基礎(chǔ)且針對數(shù)據(jù)局部結(jié)構(gòu)化的，一旦找到Z（或者相似矩陣S），通過引入關(guān)聯(lián)矩陣或者，然后應(yīng)用譜聚類，就能夠?qū)崿F(xiàn)數(shù)據(jù)分割．假設(shè)聚類結(jié)果已經(jīng)給定｛t1,t2,… ,tN｝，ti∈ ｛ 1, 2, … ,C ｝是xi的類別標(biāo)簽，C是類數(shù)，在本文中，使用非負(fù)實值描述點對之間相似性的關(guān)聯(lián)矩陣W，作為軟數(shù)據(jù)結(jié)構(gòu)化；而提供數(shù)據(jù)點類特征的數(shù)據(jù)分割結(jié)果，作為一種硬數(shù)據(jù)結(jié)構(gòu)化[7]．

1.2 線性判別分析

線性判別分析（LDA）目標(biāo)是尋求一種方向：在同類中，數(shù)據(jù)點之間離得較近，在不同類中數(shù)據(jù)點之間離得較遠(yuǎn)．對于已經(jīng)給定的類別標(biāo)簽數(shù)據(jù)集 X = ｛ x1,x2,… ,xn｝，LDA的主函數(shù)如下：

Tr(·)指矩陣跡算子， A ∈ Rm×d是映射矩陣，和S=b分別是類內(nèi)離散度矩陣和類間離散度矩陣，nc是樣本在第c類中的樣本數(shù)量，是第c類中的第i個樣本，是第c類中樣本的均值，是所有樣本的均值．定義為全散度矩陣，因此有 St=Sw+Sb．LDA的主函數(shù)等價于：

A由廣義特征值問題 Sbα =λStα的最大特征值所對應(yīng)的前m個特征向量組成，其中λ是特征值，α是所對應(yīng)的特征向量[8]，由于它的簡單有效性，LDA被廣泛應(yīng)用在機器學(xué)習(xí)中．

1.3 半監(jiān)督降維

這里我們公式化半監(jiān)督降維[9]．對于樣本數(shù)據(jù)集它的前l(fā)個樣本是有標(biāo)簽的，記為第l+1個樣本到n個樣本是無標(biāo)簽的，記為標(biāo)簽矩陣記為這里．通過數(shù)據(jù)結(jié)構(gòu)化學(xué)習(xí)能夠獲得數(shù)據(jù)的軟標(biāo)簽矩陣，然后通過半監(jiān)督學(xué)習(xí)得到硬標(biāo)簽矩陣——硬數(shù)據(jù)結(jié)構(gòu)化．

此外，我們希望降維后的結(jié)論能夠影響結(jié)構(gòu)化學(xué)習(xí)過程．在降維后，當(dāng)Axi和Axj比較接近時，數(shù)據(jù)xi和xj的相似度是比較大的；yi和yj比較接近時，標(biāo)簽yi和yj的相似度也是比較大的．在半監(jiān)督降維中，目的是使投影數(shù)據(jù)矩陣AX和相似度矩陣W盡可能地相似：

把（4）和（6）結(jié)合起來，公式化結(jié)構(gòu)正則化半監(jiān)督降維（Sr-SSDR）的優(yōu)化框架如下：

由（7）式可以看到，當(dāng)Y,A定時，本文的算法學(xué)習(xí)了映射后數(shù)據(jù)特征的數(shù)據(jù)結(jié)構(gòu)（前三項），當(dāng)Z定時，對于降維問題，硬數(shù)據(jù)結(jié)構(gòu)化被轉(zhuǎn)化為正則化項．本文的方法在很大程度上減輕了噪聲對數(shù)據(jù)的影響[10]．

1.4 優(yōu)化算法的步驟

這一部分，我們提出一種有效的優(yōu)化模型．優(yōu)化算法具體步驟：1）當(dāng)Y和A定時，優(yōu)化Z和E直到收斂；2）當(dāng)Z和E定時，優(yōu)化Y和A．當(dāng)標(biāo)簽矩陣Y和映射矩陣A（初始化為I）給定時，通過優(yōu)化下列結(jié)構(gòu)化問題求解出矩陣Z和E：

對于問題（8），用ADMM（Alternating Direction Method of Multipliers）算法，通過引入增廣矩陣 Q = Z - d iag(Z)，問題（8）就等價于：

進(jìn)一步，可得到上述優(yōu)化問題的增廣的拉格朗日函數(shù)如下：

其中Y1,Y2是拉格朗日乘子矩陣，μ＞0是一個自適應(yīng)參數(shù)．對于（10）中Z的子問題，通過ADMM算法，得到Z的閉式解：

Z的閉式解可以簡化為：

為了優(yōu)化（10）中的Q，對（10）關(guān)于Q求導(dǎo)，令導(dǎo)函數(shù)為0，得出的Q值就是最優(yōu)解．

當(dāng)其它的變量都固定時，求解噪聲E：

求解結(jié)構(gòu)正則化半監(jiān)督降維．

在自表述矩陣Z和噪聲矩陣E達(dá)到收斂的情況下，優(yōu)化類別標(biāo)簽Y和投影矩陣A．當(dāng)Z和E,A定時，優(yōu)化Y，目標(biāo)函數(shù)如下：

其中L是拉普拉斯矩陣，L=D+W， D = d iag()（i=1,…,n）是度矩陣且是一個對角線上元素為的對角矩陣．為計算方便，令則優(yōu)化（13）就相當(dāng)于優(yōu)化下式：

由于在 Y =［Yl, Yu］中，Yl是已知標(biāo)簽，所以求解Y實際只需求解未知標(biāo)簽Yu即可．為了求解這一問題，對（14）式關(guān)于Yu進(jìn)行求導(dǎo)，令導(dǎo)函數(shù)為0得的閉式解為：

給出標(biāo)簽Y，問題（7）化簡為下列問題：

基于標(biāo)簽Y，可估計出類內(nèi)散度矩陣Sw和類間散度矩陣Sb．由于A存在于分子、分母和條件項中，很難直接去求解（16），這里采用譜回歸把復(fù)雜問題（16）轉(zhuǎn)化為一種等價的回歸形式，使A更容易求解出來．令是中心化的數(shù)據(jù)矩陣，類間散度矩陣

定理1表明我們并不用解決（17）中的特征值問題，而是通過以下兩步求解LDA問題：

2 討 論

本文方法（SSrDR）使用了交替優(yōu)化的算法——同時優(yōu)化Z和E直到收斂，接著優(yōu)化Y和A，交替優(yōu)化，直到Z,E,Y,A都達(dá)到收斂．這里優(yōu)化Z和E是一個內(nèi)循環(huán)，優(yōu)化Y和A是外循環(huán)．采用本文方法求解投影矩陣A時，把復(fù)雜的特征值求解問題轉(zhuǎn)化為一種等價的回歸問題，其收斂速度更快，更容易求解，大大縮短了計算時間．

3 實 驗

用兩個圖像數(shù)據(jù)集（COIL20，Mpeg）做實驗來測試本文所給方法．我們用分類精確度作為性能度量，把最近鄰分類器應(yīng)用在無標(biāo)簽樣本的嵌入中去計算分類精確度，所有的實驗都獨立實驗 50次以上．實驗采用最近鄰分類器的分類精確度作為評價指標(biāo)，使用交叉驗證法估計最終的實驗結(jié)果，見圖1、圖2、圖3、圖4．

由實驗結(jié)果可以看出，在每一種降維算法下，隨著維度的增加，分類精確度都是逐漸上升的，在分類精確度達(dá)到穩(wěn)定時，本文的算法在兩種數(shù)據(jù)集上的分類精確度都是最高的．

4 結(jié)論與前景展望

本文提出了一種結(jié)構(gòu)正則化半監(jiān)督降維算法——同時降維和學(xué)習(xí)數(shù)據(jù)的結(jié)構(gòu)特征．在本文的半監(jiān)督降維方法中，通過交替優(yōu)化和半監(jiān)督分類，可以學(xué)到兩種數(shù)據(jù)結(jié)構(gòu)——軟數(shù)據(jù)結(jié)構(gòu)和硬數(shù)據(jù)結(jié)構(gòu)，把兩種數(shù)據(jù)結(jié)構(gòu)當(dāng)成正則化項，這種算法是一種高效的算法．大量的實驗驗證了本文算法的有效性．

圖1 COIL20數(shù)據(jù)集（有標(biāo)簽的數(shù)據(jù)占20%）在各種降維算法中分類精確度的比較Fig 1 The Comparison of Classification Accuracy of COIL20 Data Set (Labeled Data Account for 20%) in Various Dimensionality Reduction Algorithms

圖2 COIL20數(shù)據(jù)集（有標(biāo)簽的數(shù)據(jù)占25%）在各種降維算法中分類精確度的比較Fig 2 The Comparison of Classification Accuracy of COIL20 Data Set (Labeled Data Account for 25%) in Various Dimensionality Reduction Algorithms

圖3 Mpeg數(shù)據(jù)集（有標(biāo)簽數(shù)據(jù)占35%）在各種降維算法中分類精確度的比較Fig 3 The Comparison of Classification Accuracy of Mpeg Data Set (Labeled Data Account for 35%) in Various Dimensionality Reduction Algorithms

圖4 Mpeg數(shù)據(jù)集（有標(biāo)簽數(shù)據(jù)占40%）在各種降維算法中分類精確度的比較Fig 4 The Comparison of Classification Cccuracy of Mpeg Data Set (Labeled Data Account for 40%) in Various Dimensionality Reduction Algorithms