L1-PCA算法的若干研究

作     者：葛琪文 

作者单位：浙江大学 

学位级别：硕士

导师姓名：张振跃

授予年度：2012年

学科分类：07[理学] 070102[理学-计算数学] 0701[理学-数学] 

主      题：PCA L1-PCA 贪婪算法 异常点 

摘      要：在机器学习,数据挖掘等领域,往往需要处理大规模的数据,同时数据实际上通常都处于低维空间中,因而为了更好,更快速地对数据进行处理,我们需要对数据进行降维。PCA算法简单,容易求解,且能取得最优解,是一种应用十分广泛的线性降维方法,但是他对于异常点却十分敏感,这使得它在存在很多异常点的情况下,求得的解往往偏离我们想要的结果。而由于1-范数的鲁棒性,L1-PCA相对PCA,不易受异常点的影响。尽管Ll-PCA（?）（?）比较PCA更优,但是却也更难求解。关于Ll-PCA问题的求解,存在很多算法,但是大多计算比较复杂,求解速度很慢。 本文主要研究了一个近似求解Ll-PCA问题的快速的贪婪算法。首先从统计的角度来推导L1-PCA问题,并说明L1-PCA优于PCA的原因。接着介绍了几个Ll-PCA的求解算法,主要对逐步降维算法和贪婪算法的思想进行了细致地分析。根据其中贪婪算法的一些缺陷,提出了该贪婪算法的两个修正算法,以及投影优化算法。最后通过实验分析了各个算法的优劣。