張子明，徐常青

（蘇州科技大學 數理學院，江蘇 蘇州215009）

大數據是當前研究的熱門學科之一，它涉及信息科學、統(tǒng)計學、計算數學、計算機科學和數值分析等，屬交叉性應用領域[1]。盡管到目前為止大數據還沒有一個統(tǒng)一的數學化定義，但通常人們把大數據理解為比傳統(tǒng)數據更復雜、維數更高且具有量（Volume）大（可達10 個Tb 以上）、更新快（velocity）、類型多（variety）三個特征（稱為3V）[2]。數據分析中著名的維數魔咒（The curse of dimensions）問題[3]描述當樣本點對應的特征向量（feature vector） 維數達一定程度后，相應變量或不變量的計算量（如樣本點集合對應的主成分的計算）將呈指數增長。這類問題在計算機網絡、張量分解（如張量CP 分解[4]）和模式識別等學科和理論中普遍存在，因此，降維問題是大數據和傳統(tǒng)數據分析面臨的一個關鍵問題[5]。

高維數據集對應一個高維樣本集，而數據分析的最終目的是對樣本分類并建立樣本分類預測模型。高維數據不僅難以被人們直觀理解，也難以被現有的機器學習和數據挖掘算法有效處理，因而很難建立樣本分類預測模型，比如LDA 算法在高維數據中往往性能不佳[6]。另一方面，低維統(tǒng)計度量在許多統(tǒng)計問題中有著重要的作用，如數據的統(tǒng)計分析和數據特征可視化等[7]。尋找一個從高維空間到低維空間的一個具有某種理想屬性的映射以實現數據降維是挖掘高維數據中有效信息的必要步驟[8]。

線性子空間學習（Linear Subspace Learning，簡稱LSL）方法嘗試尋找這樣一類線性映射，它將高維數據集合中的樣本點投影至一個低維線性空間，以實現數據的降維[9]。該映射是通過對一個目標函數的最優(yōu)化來學習產生。線性子空間學習基本方法包括主成分分析法(Principal Component Analysis，簡稱PCA）、線性判別分析法（Linear Discriminant Analysis，簡稱LDA ）、典型相關分析法（Canonical Correlation Analysis，簡稱CCA）和偏 最 小 二 乘 法（Partial Least Square Method，簡 稱PLS）等[10]。LDA 在 自 然 語 言 處 理（Natural Language Process，簡稱NLP）和人臉識別等模式識別中有廣泛應用。LDA 在類別信息（或部分）已知的前提下通過一個線性投影以實現數據降維。因此，LDA 也是一種經典的有監(jiān)督或部分監(jiān)督條件下的降維方法[11]。CCA 通過兩組變量中部分變元的線性組合以生成低維綜合指標向量組，來代替原始樣本點集合，以考察兩組樣本集合之間的相關性[12]。CCA 在研究宏觀經濟走勢與股票市場走勢之間的關系、病人醫(yī)療費用與醫(yī)療保險支付的關系等眾多問題中有廣泛應用[13]。

給定數據集M={x1，x2，…，xN}，其中每個數據點xm∈RI為一個向量，S 為V=RI的一個線性子空間，且滿足0

記E=[β1，β2，…，βP]∈RI×P，則rank（E）=p，令U=E（ETE）－1ET，則U∈RI×I為一個對稱冪等矩陣，故為一個投影矩陣，且?x∈RI，Ux=E（ETE）－1ETx=Ey∈S，其中y=（ETE）－1ETx∈RP。

從以上分析可以看出，在給定目標投影子空間（或它的一組基）的前提下，理論上可計算出相應的線性投影映射，從而實現數據降維。因此，尋找投影線性子空間S 成為線性子空間方法的核心。

在大數據背景下，數據集M 所含數據點的個數及其所在的空間維數I 通常會是幾千萬甚至是幾十億，這時線性子空間學習需要很大的計算量。筆者將利用矩陣分解和矩陣分析方法對線性子空間方法中的LDA和CCA 方法進行改進，以提高計算效率。

1 線性判別法的改進

LDA 為樣本分類線性學習方法。給定訓練樣本集M={x1，x2，…，xN}?RI，其中每個樣本點xm∈RI是一個向量。記樣本矩陣為X=[x1，x2，…，xN]∈RI×N。LDA 方法尋求一個線性投影映射σ，使同類樣本在σ 下的投影盡可能近，異類樣本投影點盡可能遠。注意LDA 中的每個訓練樣本點都有類別標記。

記r 為類別數，C1，C2，…，Cr為類別標記。定義類指示矩陣P=（Pij）∈RN×r為（0，1）-矩陣且Pij=1 當且僅當xi∈Cj；類標記矩陣D=diag（n1，n2，…，nr），其中ni為類Ci所含樣本點個數。樣本集的類內散度矩陣和類間散度矩陣分別定義為

其中μi是樣本集Ci的樣本均值?？梢宰C明：

引理1

（1）類指示矩陣P的列向量構成正交向量組，且有PTP=D。

（2）令W=IN-PD-1PT，則W為投影矩陣，且Sw=XWXT。

（3）令R=Ir-（1/r）eeT（e為r 維全1 向量），B=PD-1/2RD-1/2PT，則R和B為投影矩陣，且Sb=XBXT。

證明（1）設pi與pj分別是矩陣P的第i 列與第j 列，由矩陣P的定義易知piTpj=0，piTpi=ni，故PTP=D。

（2）由于XP＝[μ1，μ2，…，μr]D=μD，所以μ=XPD-1，故有

其中W=IN-PD-1PT。不難證明W為對稱冪等矩陣，故W是投影矩陣。

（3）通過直接計算可以驗證R是對稱冪等矩陣，故R為正交投影矩陣。同時注意到故由（2）式可得

注意到B為對稱矩陣，且

故B為對稱投影陣。

LDA 的思路是求一個投影矩陣U∈RI×（r－1），使投影后的樣本點集合的各類中心到全局中心的距離之和最大，同時各類樣本點到其類中心距離之和盡可能小，這里的距離可以是任意類型的距離，一般默認這里的距離為歐式距離。這等價于優(yōu)化問題

利用Lagrange 乘子法不難發(fā)現，（3）式等價于廣義特征值問題

結合引理1，注意到P 為0-1 矩陣，D 為對角陣，因此，廣義特征問題（4）的計算量會大幅減少。

2 典型相關分析法的改進

2.1 迭代方法推導典型相關分析

CCA 是分別對兩組數據進行線性投影，通過綜合變量之間的相關性來反應兩組指標之間的相關性。它在研究國民經濟與多維有監(jiān)督學習中有廣泛應用[14]。

設有兩組數據集X∈RI×N，Y∈RJ×N，N 是每組的樣本個數，I 與J 是每組數據維數。記X，Y 對應的樣本協方差矩陣（又稱樣本散度矩陣）分別為Σxx，Σyy，即

若記H=IN-JN（JN＝eeT），則有

同理

定義兩變量p，q 的Pearson 相關系數為

下面是傳統(tǒng)的CCA 方法中逐次計算投影向量對的方法和步驟：

（1）第一對投影向量：設ux1∈RI和uy1∈RJ分別是兩組數據的第一對投影向量。目標函數為

優(yōu)化問題（9）等價于

寫成拉格朗日乘子法形式為

其中λ 和μ 是拉格朗日乘子。于是有

由式（13），得到

由式（14），得到

將式（16）代入到式（13），式（15）代入到式（12），得到

變成了求矩陣特征值與特征向量問題。（假設Σxx與Σyy均可逆）。

（2）第P 對投影向量：與求第一對投影向量類似，只是目標函數多了如下幾個限制條件[15]，即為減少數據冗余度，希望投影后的每組數據特征不相關且與兩組間不配對特征無關。

其中q=1，2，…，p-1。這樣可找到p=min{I，J}對投影向量{u?xp，u?yp}（詳細推導過程見文獻[15]），組成投影矩陣為其中

總結上述得到如下算法：

輸入： 訓練集X={x1，x2，…，xN}，Y＝{y1，y2，…，yN}；xm∈RI，ym∈RI；

過程：

1：根據式（5）、（6）、（7）分別計算Σxx、Σyy、Σxy；

2：通過逐個解式（16）和（17）這樣廣義特征值問題得到p 對{uxp，uyp}，其中p=min{I，J}，p 對{uxp，uyp}這樣投影向量組成投影矩陣

2.2 典型相關分析的矩陣推導形式

傳統(tǒng)的CCA 方法需要多次迭代以逐次計算投影向量對并最終生成投影矩陣，這種方法顯然非常繁瑣，在大數據情形下沒有可行性。下面用用更簡潔的矩陣形式計算投影矩陣，避免了繁瑣的迭代過程。

其中Λλ=diag（λ1，λ2，…，λI）。則

定理1設Σ＝cov（x，y）為協方差矩陣，其中x，y∈RI。Σxx、Σyy、Σxy、Σyx為2.1 中定義的樣本協方差矩陣，令則存在正交矩陣W∈RI×I，使

證明

注意到

所以W 是正交矩陣。證畢。

由定理1，可得到如下算法：

輸入： X={x1，x2，…，xN}，Y＝{y1，y2，…，yN}；xm∈RI，ym∈RI；

過程：

1：根據式（5）、（6）、（7）分別計算Σxx、Σyy、Σxy；

3 結語

文中對線性判別法（LDA）與典型相關分析法（CCA）通過矩陣分解的形式進行了改進。在LDA 中，類內散度矩陣Sw=XWXT，類間散度矩陣Sb=XBXT，較（2）式形式更簡潔且計算量更小。接下來問題是如果對（3）式可以進一步化簡，那么LDA 效率將會進一步提高。對于CCA，如果兩組數據集維度相等（如果兩組數據集維度不相等，可以嘗試對其進行降維處理使其相等），那么目標投影矩陣可以直接利用矩陣乘法求出，更易于編程且大幅節(jié)省計算時間。

事實上，LDA 與CCA 可以推廣到張量，比如利用張量CP 分解等張量知識進行處理，有關內容讀者可參閱文獻[15]。