一種線性辨別分析的可擴展的近似算法.pdf

1、Fisher線性辨別分析（FisherLinearDiscriminantAnalysis，LDA）是一種經(jīng)典的用于處理分類問題的有監(jiān)督的降維方法。傳統(tǒng)的LDA算法主要面臨的問題是“奇異性問題”，即當(dāng)訓(xùn)練數(shù)據(jù)的散布矩陣（ScatterMatrix）奇異時，傳統(tǒng)算法不再成立。近年來，研究者們提出了許多LDA的改進算法，用于處理“奇異性問題”，其中包括一些兩階段的近似算法，包括PCA+LDA算法和LDA\QR算法。這些算法首先通過一些其他降

2、維方法將原始數(shù)據(jù)集降到一個中間維度，使得降維后的協(xié)防差矩陣不再奇異，再在降維后的數(shù)據(jù)上使用傳統(tǒng)的LDA算法進一步降低原數(shù)據(jù)的維度。同時，傳統(tǒng)的LDA算法由于有較高的時間復(fù)雜度，可擴展性不高，因而無法應(yīng)用在大規(guī)模數(shù)據(jù)上。這些兩階段的算法，由于是傳統(tǒng)LDA算法的一個近似，相比傳統(tǒng)的LDA算法有較高的可擴展性。然而，目前對于這類兩階段LDA算法的有效性缺乏理論上的研究。
　　本文首先對一類兩階段的LDA算法的近似誤差進行了理論分析，提出

3、了兩階段算法近似誤差的一個理論界。根據(jù)該理論結(jié)果，本文提出了一種新的兩階段的LDA算法。實驗證明，該算法相較于PCA+LDA算法和LDA\QR算法，有更高的精確度。另一方面，由于本算法的主要部分是一個奇異值分解，應(yīng)用近年提出的一種基于隨機投影的奇異值分解算法，本算法也擁有較高的可擴展性，可用于大規(guī)模的數(shù)據(jù)上。
　　MapReduce是一個流行的分布式計算軟件構(gòu)架，它可以支持大規(guī)模數(shù)據(jù)的分布式處理。本文描述了本算法在MapReduc