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

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

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

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