資源描述：
《一種線性辨別分析的可擴展的近似算法》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在學術論文-天天文庫。
1、浙江大學研究生學位論文獨創(chuàng)性聲明本人聲明所呈交的學位論文是本人在導師指導下進行的研究工作及取得的研究成果。除了文中特別加以標注和致謝的地方外，論文中不包含其他人已經(jīng)發(fā)表或撰寫過的研究成果，也不包含為獲得浙江大學或其他教育機構(gòu)的學位或證書而使用過的材料。與我一同工作的同志對本研究所做的任何貢獻均己在論文中作了明確的說明并表示謝意。學位論文作者簽名：簽字日期：2014年1月10日學位論文版權使用授權書本學位論文作者完全了解浙江大學有權保留并向國家有關部門或機構(gòu)送交本論文的復印件和磁盤，允許論文被查閱和借閱
2、。本人授權浙江大學可以將學位論文的全部或部分內(nèi)容編入有關數(shù)據(jù)庫進行檢索和傳播，可以采用影印、縮印或掃描等復制手段保存、匯編學位論文。(保密的學位論文在解密后適用本授權書)學位論文作者簽名：導師簽名：簽字日期：2014年1月10日簽字日期：2014年1月10日浙江大學碩士學位論文摘要摘要Fisher線性辨別分析(FisherLinearDiscriminantAnalysis，LDA)是一種經(jīng)典的用于處理分類問題的有監(jiān)督的降維方法。傳統(tǒng)的LDA算法主要面臨的問題是“奇異性問題”，即當訓練數(shù)據(jù)的散布矩陣(
3、ScatterMatrix)奇異時，傳統(tǒng)算法不再成立。近年來，研究者們提出了許多LDA的改進算法，用于處理“奇異性問題”，其中包括一些兩階段的近似算法，包括PCA+LDA算法和LDA＼QR算法。這些算法首先通過一些其他降維方法將原始數(shù)據(jù)集降到一個中間維度，使得降維后的協(xié)防差矩陣不再奇異，再在降維后的數(shù)據(jù)上使用傳統(tǒng)的LDA算法進一步降低原數(shù)據(jù)的維度。同時，傳統(tǒng)的LDA算法由于有較高的時間復雜度，可擴展性不高，因而無法應用在大規(guī)模數(shù)據(jù)上。這些兩階段的算法，由于是傳統(tǒng)LDA算法的一個近似，相比傳統(tǒng)的LDA算
4、法有較高的可擴展性。然而，目前對于這類兩階段LDA算法的有效性缺乏理論上的研究。本文首先對一類兩階段的LDA算法的近似誤差進行了理論分析，提出了兩階段算法近似誤差的一個理論界。根據(jù)該理論結(jié)果，本文提出了一種新的兩階段的LDA算法。實驗證明，該算法相較于PCA+LDA算法和LDA＼QR算法，有更高的精確度。另一方面，由于本算法的主要部分是一個奇異值分解，應用近年提出的一種基于隨機投影的奇異值分解算法，本算法也擁有較高的可擴展性，可用于大規(guī)模的數(shù)據(jù)上。MapReduce是一個流行的分布式計算軟件構(gòu)架，它可
5、以支持大規(guī)模數(shù)據(jù)的分布式處理。本文描述了本算法在MapReduce上的一種高效實現(xiàn)。這進一步驗證了本算法的可擴展性。關鍵詞：分類，降維，線性辨別分析，可擴展性，MapReduce浙江大學碩士學位論文ABSTRACTAbstractTheFisherLinearDiscriminantAnalysis(LDA)isaclassicalsuperviseddimensionreductionmethodforclassificationproblem．Amajorlimitationoftheconven
6、tionalLDAisaso-calledsin-gularityissue．Thatis，itfailswhenthescattermatrixoftheoriginaldatasetissingular．Recently，ManyLDAvariantswereproposedtosolvethisissue，includingsometwo-stagemethodssuchasPCA+LDAandLDA＼QR．Inthetwo-stagemethods，anintermediatestagefor
7、dimensionreduc-tionisdevelopedbeforetheactualLDAmethodworl【s．Ontheotherhand．theconventionalLDAalgorithmarecomputationallyexpensive，andnotscalable．Therefore，itCannotbeappliedtolargescaledatasets．Thesetwo-stagemethodsarescalablebecausetheyareanapproximate
8、alternativeoftheLDAmethod．However，thereisnotheoreticalanalysisonhowwelltlleyapproximatetheconventionalLDAproblem．Inthispaper,wefirstpresenttheoreticalanalysisontheapproximationerrorofatwo—stagealgorithm．Atheoreticalboundfortheapp
