基于Spark平台的SVD算法设计实现和应用

摘要

奇异值分解（Singular Value Decomposition）是线性代数中一种重要的矩阵分解算法。在信号处理、机器学习等领域都有广泛的应用，可用于对数据进行降维，主成分分析，噪声过滤，信息的分解和重构等方面。而在当前信息爆炸时代，大数据背景下，传统的SVD算法实现难以应对海量数据处理。结合大数据处理平台、高效的分布式算法设计和应用，已经成为一个富有意义和挑战的研究方向。
　　Spark是由加州大学伯克利分校AMP实验开发的基于内存的分布式计算框架。相对于MapReduce等分布式计算框架，它的优势在于能够很好地适应迭代计算，能高效地处理复杂的海量数据计算问题，良好地适应分布式迭代算法开发。
　　为了解决海量数据处理的问题，本文针对大规模稀疏矩阵设计了并行的SVD算法并在Spark平台上进行了实现。在大规模稀疏数据下的算法实现需要面对两个问题，一是计算过程中要保证数据的稀疏度，二是能够高效地实现并行化。针对这两个问题，本文给出了基于Lanczos分解算法、二分法和反幂法等算法设计了SVD并行算法。Lanczos算法是一种将实对称矩阵变换成对称三对角矩阵的算法，是求解大规模对称矩阵特征问题最有效方法之一，而二分法和反幂法分别用于高效地求解三对角矩阵特征值和特征向量。对基于Spark平台的SVD算法在效率、准确性、加速比方面展开了实验，结果表明，算法在对大规模数据处理时有较高的实现效率。
　　本文还给出了SVD算法在信息检索领域，查询推荐方面的应用研究。利用SVD算法，通过对搜索引擎中查询点击的标题文本分析，构建潜在语义分析模型并计算标题文本间相似度，进而得到查询间的相似度，可进一步应用于查询推荐或建议等。研究结果表明，算法在查询推荐方面也有较好的应用效果。

目录

封面

声明

中文摘要

英文摘要

目录

1 绪论

1.1 研究背景及意义

1.2 国内外研究发展现状

1.3 研究目的及创新点

1.4 主要内容及章节安排

2 针对大规模稀疏矩阵的SVD算法设计

2.1 奇异值分解算法简介

2.2 Lanczos算法介绍及优化

2.3 基于二分法求解三对角矩阵特征值

2.4 基于反幂法求解三对角矩阵特征向量

2.5 基于Lanczos等算法的SVD算法设计

2.6 本章小结

3 SVD算法在spark平台上的实现

3.1 spark大规模数据计算平台简介

3.2 基于spark平台的svd算法实现

3.3 算法实现结果分析

3.4 本章小结

4 基于点击标题文本分析和SVD算法的相似查询应用

4.1 潜在语义分析和相似查询算法

4.2 标题文本预处理

4.3 构造“query- 特征词”权重矩阵

4.4 基于SVD算法降维后的query相似度计算

4.5 应用结果分析

4.6 本章小结

5 总结与展望

5.1 工作总结

5.2 工作展望

致谢

参考文献