PCA数学原理解析

PCA数学原理解析数据仓库与数据挖掘WhatisPCA?• PCA（PrincipalComponentAnalysis）是一种常用的数据分析方法。• PCA通过线性变换将原始数据变换为一组各维度线性无关的表示，可用于提取数据的主要特征分量，常用于高维数据的降维。数据的向量表示• 一般情况下，在数据挖掘和机器学习中，数据被表示为向量。– 例如，某个淘宝店2012年全年的流量及交易情况可以看成一组记录的集合，其中每一天的数据是一条记录，列向量格式如下：– (浏览量,访客数,下单数,成交数,成交金额)T– (500,240,25,13,2312.15)T降维问题：目的和原则• 机器学习算法的复杂度通常与数据的维数有着密切关系，甚至与维数呈指数级关联。• 机器学习在实际中处理成千上万甚至几十万维的情况也并不罕见，在这种情况下，机器学习的资源消耗是不可接受的，因此我们必须对数据进行降维。• 降维当然意味着信息的丢失，不过鉴于实际数据本身常常存在的相关性，我们可以想办法在降维的同时将信息的损失尽量降低。降维与相关性举例（1）• 某学籍数据有两列M和F，其中，– M列的取值是：学生为男性取值1，为女性取值0；– F列的取值是：学生为女性取值1，男性取值0。• 此时，如果我们统计全部学籍数据，会发现对于任何一条记录来说，当M为1时F必定为0，反之当M为0时F必定为1。• 在这种情况下，我们将M或F去掉实际上没有任何信息的损失，因为只要保留一列就可以完全还原另一列。降维与相关性举例（2）• 例如上面淘宝店铺的数据，从经验可知：– “浏览量”和“访客数”往往具有较强的相关关系，– “下单数”和“成交数”也具有较强的相关关系。– 这里我们非正式的使用“相关关系”这个词，可以直观理解为“当某一天这个店铺的浏览量较高（或较低）时，我们应该很大程度上认为这天的访客数也较高（或较低）”。• 表明：如果删除浏览量或访客数其中一个指标，数据集并不会丢失太多信息。因此，将相关的指标删除一个，以降低机器学习算法的复杂度。降维方法：从直观描述到数学支撑• 上面给出的是降维的朴素思想描述，可以有助于直观理解降维的动机和可行性，但并不具有操作指导意义。– 例如，到底删除哪一列损失的信息才最小？亦或根本不是单纯删除几列，而是通过某些变换将原始数据变为更少的列但又使得丢失的信息最小？到底如何度量丢失信息的多少？如何根据原始数据决定具体的降维操作步骤？• 要回答上面的问题，就要对降维问题进行数学化和形式化的讨论。PCA是一种具有严格数学基础并且已被广泛采用的降维方法。降维的数学支撑（1）向量的表示及基变换向量的表示及基变换：内积和投影• 两个维数相同的向量的内积被定义为：• 内积运算将两个向量映射为一个实数。• 设A和B是两个n维向量，n维向量可以等价表示为n维空间中的一条从原点发射的有向线段：基的数学含义• 一个二维向量可以对应二维笛卡尔直角坐标系中从原点出发的一个有向线段。• 向量(x,y)实际上表示线性组合：– (1,0)和(0,1)叫做二维空间中的一组基。• 要准确描述向量，首先要确定一组基，然后给出在基所在的各个直线上的投影值。• 例如，(1,1)和(-1,1)也可以成为一组基，标准化后变成• (3,2)在新基上的坐标，基变换的矩阵表示• （3，2）的基变换：• 例如(1,1)，(2,2)，(3,3)的基变换：• 一般的，如果有M个N维向量，想将其变换为由R个N维向量表示的新空间中，那么首先将R个基按行组成矩阵A，然后将向量按列组成矩阵B，那么两矩阵的乘积AB就是变换结果，其中AB的第m列为A中第m列变换后的结果。协方差矩阵及优化目标• 如果我们有一组N维向量，现在要将其降到K维（K小于N），那么我们应该如何选择K个基才能最大程度保留原有的信息？• 假设数据由五条记录组成，将它们表示成矩阵形式：其中每一列为一条数据记录，而一行为一个字段。为了后续处理方便，首先将每个字段内所有值都减去字段均值，其结果是将每个字段都变为均值为0• 如果我们必须使用一维来表示这些数据，• 又希望尽量保留原始的信息，你要如何选择？• 通过基变换的讨论我们知道，这个问题实际上是要在二维平面中选择一个方向，将所有数据都投影到这个方向所在直线上，用投影值表示原始记录。这是一个实际的二维降到一维的问题。• 如果向x轴投影，则最左边的两个点会重叠在一起，中间的两个点也会重叠在一起，于是本身四个各不相同的二维点投影后只剩下两个不同的值了，这是一种严重的信息丢失，同理，如果向y轴投影最上面的两个点和分布在x轴上的两个点也会重叠。单独选x和y轴都不是最好的投影选择。方差• 目标：投影后投影值尽可能分散，而这种分散程度，可以用数学上的方差来表述。• 此处，一个字段的方差可以看做是每个元素与字段均值的差的平方和的均值，即：• 由于上面已将每个字段的均值都化为0了，因此方差可以直接用每个元素的平方和除以元素个数表示：• 于是上面的问题被形式化表述为：寻找一个一维基，使得所有数据变换为这个基上的坐标表示后，方差值最大。协方差• 目的：从直观上说，让两个字段尽可能表示更多的原始信息，不希望它们之间存在（线性）相关性的，因为相关性意味着两个字段不是完全独立，必然存在重复表示的信息。• 数学上可以用两个字段的协方差表示其相关性，由于已经让每个字段均值为0，则：– 可以看到，在字段均值为0的情况下，两个字段的协方差简洁的表示为其内积除以元素数m。• 当协方差为0时，表示两个字段完全独立。为了让协方差为0，我们选择第二个基时只能在与第一个基正交的方向上选择。因此最终选择的两个方向一定是正交的。• 至此，我们得到了降维问题的优化目标：将一组N维向量降为K维（K大于0，小于N），其目标是选择K个单位（模为1）正交基，使得原始数据变换到这组基上后，各字段两两间协方差为0，而字段的方差则尽可能大（在正交的约束下，取最大的K个方差）。协方差矩阵• 目的：降维的指标与字段内方差及字段间协方差有密切关系。因此，可将两者统一表示。• 用X乘以X的转置，并乘上系数1/m：– 矩阵对角线上的两个元素分别是两个字段的方差，而其它元素是a和b的协方差。– 两者被统一到了一个矩阵的。协方差矩阵推广协方差矩阵对角化• 目标：将协方差矩阵对角化，即除对角线外的其它元素化为0，并且在对角线上将元素按大小从上到下排列• 原矩阵与基变换后矩阵协方差矩阵的关系：• 设原始数据矩阵X对应的协方差矩阵为C，而P是一组基按行组成的矩阵，设Y=PX，则Y为X对P做基变换后的数据。设Y的协方差矩阵为D，我们推导一下D与C的关系：• P能让原始协方差矩阵对角化的P。换句话说，优化目标变成了寻找一个矩阵P，满足是一个对角矩阵，并且对角元素按从大到小依次排列，那么P的前K行就是要寻找的基，用P的前K行组成的矩阵乘以X就使得X从N维降到了K维并满足上述优化条件。PCA算法