主成分分析算法的FPGA实现

作者：侯咏佳，方东博，袁生光，沈海斌 日期：2008-11-03/span> 浏览：4446 查看PDF文档

主成分分析算法的FPGA实现

侯咏佳，方东博，袁生光，沈海斌
(浙江大学 超大规模集成电路设计研究所，浙江 杭州 310027)

摘要：主成分分析（PAC）是一种典型的数据降维方法，它通过对数据矩阵的特征分析，将高维数据降为低维数据，而且转换后数据包含的信息损失很小。提出了一种主成分分析算法的FPGA实现方案，通过Givens算法和CORDIC算法的矢量旋转，用简单的移位和加法操作来实现协方差矩阵的特征分析，只需计算上三角元素，因此计算复杂度小、迭代收敛速度快；系统对结构相同但不同时处理数据的模块进行复用，节省了资源；在计算协方差矩阵和线性空间投影时对数据并行处理，所以系统时钟频率不受数据维数变化的影响。实验数据表明，该系统能实现对不同维数数据的主成分分析，时钟频率稳定，占用资源少。
关键词：数据降维；主成分分析；矩阵的特征分析；FPGA
中图分类号：O242.2文献标识码：A文章编号：1001-4551(2008)09-0037-04

Implementation in FPGAs of principal component analysis
HOU Yong-jia, FANG Dong-bo, YUAN Sheng-guang, SHEN Hai-bin
（Institute of VLSI Design, Zhejiang University, Hangzhou 310027, China）
Abstract: Principal component analysis(PCA), which is a typical method of data dimensionality reduction, transforms high dimensional data to low dimensional data by eigenanalysis of the data matrix and loses little of information within the transformed data. A new architecture of FPGAs to realize PCA was demonstrated, which solved eigenanalysis of matrix by simple shift and addition operations with vector rotation of Givens and CORDIC algorithm, computing upper triangular elements only. Therefore, the computational complexity was low and the iterative convergence speed was fast. Moreover, the design reused some similar modules processing data asynchronously to save FPGA resources, and processed data in parallel during computing covariance matrix and linear space mapping, thus the clock frequency was not affected when the dimension of the original data was changed. The experiment results indicate that the system can implement PCA of different dimensional data with a stable clock frequency and a small amount of resources.
Key words: data dimensionality reduction; principal component analysis(PCA); eigenanalysis of matrix; field programmable gates array(FPGA)
参考文献(Reference):
［1］NGUYEN D, DAS A, MEMIK G, et al. A Reconfigurable Architecture for Network Intrusion Detection Using Principal Component Analysis［C］//Proceedings of the 2006 ACM/SIGDA 14th international symposium on Field programmable gate arrays. Monterey:CA,2006:235-235.
［2］NARA Y, YANG Jian-ming, SUEMATSU Y. Face Recognition Using Improved Principal Component Analysis［C］//Proceedings of 2003 International Symposium on Micromechatronics and Human Science. Nagoya:［s. n.］,2003:77-82.
［3］Agilent Technologies. Principal Components Analysis［EB/OL］.［2005-01-01］.http://www.chem.agilent.com/cag/bsp/sig/downloads/pdf/pca.pdf.
［4］SMITH L I. A tutorial on Principal Components Analysis［EB/OL］.［2002-2-26］.http://csnet.otago.ac.nz/cosc453/student_tutorials/principal_components.pdf.
［5］朱建平.应用多元统计分析［M］.北京:科学出版社,2006.
［6］山世光.人脸识别技术综述［EB/OL］.［2004-01-01］.http://www.jdl.ac.cn/user/sgshan/courses/slides/HCI-sgshan-Part-09-AFR-survey.ppt.
［7］HOTELLING H. Analysis of a complex of statistical variables into principal components［J］. Journal of Educational Psychology,1993(24):417-441,498-520.
［8］张贤达.矩阵分析与应用［M］.北京:清华大学出版社,2004.
［9］WILKINSON J H. The algebraic eigenvalue problem［M］. Britain: Oxford Science Publications，1999.
［10］ANDRAKA R. A Survey of CORDIC Algorithms for FPGA based Computers［C］//Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field Programmable Gate Arrays. Monterey: CA,1998:191-200.
［11］LIU Yang, BOUGANIS C, CHEUNG P Y K, et al. Hardware Efficient Architectures for Eigenvalue Computation［C］//Proceedings of the conference on Design, automation and test in Europe. Munich: European Design and Automation Association,2006:953-958.
［12］Xilinx. Virtex-II Pro and Virtex-II Pro X Complete Data Sheet［EB/OL］.［2007-11-5］.http://china.xilinx.com/support/documentation/data_sheets/ds083.pdf.