若把高维空间的样本点(可以想象是一个3维的)映射到一个超平面,怎样的超平面可以认为是“好的”,可以想到这个超平面大概有这样的性质:
- 最近重构行:样本点到超平面的距离都足够近;(样本点变化尽可能小,丢失的信息尽可能少)
- 最大可分性:样本点在这个超平面上的投影尽可能分开.(样本点在低维空间区分度尽可能高)
神奇的是,从两个角度出发,可以分别得到主成分分析PCA算法的两种等价推导。
根据最近重构性推导:
假设样本进行了中心化,即:
.
假设投影变换后新的坐标系为W={},其中是标准正交基向量,.
若丢弃坐标系中部分坐标,即将维度降低到d'<d,得到={},则样本点在低维坐标系中的投影为,其中.若基于来重构,则会得到:
(上式只是原样本点的的近似,因为丢弃了部分坐标).
对于整个样本集,原样本点和基于投影重构的样本点间的距离为:
.
根据最近重构性,上式应被最小化,得到主成分分析的优化目标:
.
根据最大可分性推导:
投影后,样本点的方差之和为(样本X已中心化:,所以投影后的Z也是中心化的):
.
根据最大可分性,投影后的样本点应尽量分开,所以方差应尽量大,于是从最大可分性角度得到主成分分析的优化目标:
.
显然,跟从最近重构性角度得到的优化目标是等价的。
利用拉格朗日乘子法,可得:.
发现须是的特征向量。于是,对进行特征值分解,将求得的特征值排序:,取前d'个特征值对应的特征向量构成={}(个人觉得,这里还需保证相互正交,才能满足约束,因为如果有相同的特征值,那么其对应的特征向量不一定正交。顺便补充一个定理:对称矩阵不同特征值对应的特征向量相互正交),这就是主成分分析的解。
算法描述如下:
其他补充:
有三种方法确定降维后的维度d':
- 人为指定;
- 在d'值不同的低维空间对k近邻分类器(或其他开销较小的学习器)进行交叉验证来选取较好的d'值;
- 设置一个重构阈值,如t = 95%,然后选取使 成立的最小d'值.
PCA算法除了保存投影矩阵,还需保存样本的均值向量,这是为了对新样本同样进行中心化。PCA降维看似舍弃了一部分信息,但这么做是必要的:1、这样做使样本的采样密度增大;2、当数据受到噪声影响时,最小特征值对应的特征向量往往与噪声有关。
参考资料:
周志华《机器学习》
参考博文:
相关博文: