一种线性辨别分析的可扩展的近似算法

摘要

Fisher线性辨别分析（FisherLinearDiscriminantAnalysis，LDA）是一种经典的用于处理分类问题的有监督的降维方法。传统的LDA算法主要面临的问题是“奇异性问题”，即当训练数据的散布矩阵（ScatterMatrix）奇异时，传统算法不再成立。近年来，研究者们提出了许多LDA的改进算法，用于处理“奇异性问题”，其中包括一些两阶段的近似算法，包括PCA+LDA算法和LDA\QR算法。这些算法首先通过一些其他降维方法将原始数据集降到一个中间维度，使得降维后的协防差矩阵不再奇异，再在降维后的数据上使用传统的LDA算法进一步降低原数据的维度。同时，传统的LDA算法由于有较高的时间复杂度，可扩展性不高，因而无法应用在大规模数据上。这些两阶段的算法，由于是传统LDA算法的一个近似，相比传统的LDA算法有较高的可扩展性。然而，目前对于这类两阶段LDA算法的有效性缺乏理论上的研究。
　　本文首先对一类两阶段的LDA算法的近似误差进行了理论分析，提出了两阶段算法近似误差的一个理论界。根据该理论结果，本文提出了一种新的两阶段的LDA算法。实验证明，该算法相较于PCA+LDA算法和LDA\QR算法，有更高的精确度。另一方面，由于本算法的主要部分是一个奇异值分解，应用近年提出的一种基于随机投影的奇异值分解算法，本算法也拥有较高的可扩展性，可用于大规模的数据上。
　　MapReduce是一个流行的分布式计算软件构架，它可以支持大规模数据的分布式处理。本文描述了本算法在MapReduce上的一种高效实现。这进一步验证了本算法的可扩展性。

目录

声明

摘要

图目录

表目录

第一章 绪论

1．1 LDA概述

1．2 相关算法

1．3 分布式环境下的计算

1．4 本文的主要工作

1．5 本文的结构

1．6 本章小结

第二章 两阶段LDA算法及分析

2．1 两阶段算法的理论分析

2．2 SVD-QR-LDA算法

2．3 截断SVD算法

2．4 对KDA的推广

2．5 本章小结

第三章 SVD-QR-LDA算法的MapReduce实现

3．1 MapReduce环境介绍

3．2 算法回顾

3．3 MapReduce上的矩阵乘法

3．4 其他MapReduee实现技巧

3．5 SVD-QR-LDA算法的MapReduce实现详解

3．6 PCA+LDA算法的MapReduce实现

3．7 本章小结

第四章 实验设计与结果

4．1 数据集介绍

4．2 实验设置

4．3 单机实验

4．4 Hadoop上的实验结果

4．5 本章小结

第五章 结论与展望

5．1 本文的主要工作和结论

5．2 下一步工作与未来展望

5．3 本章小结

参考文献

发表文章目录

致谢