清华大学系统工程11 (7)

系统工程导论,开课单位：清华大学自动化系 授课时间：2009年春季学期 主讲教师：胡坚明副教授,清华大学本科专业限选课程,第五章 主成分分析方法,§5.1 引言 §5.2 主成分分析基本原理 §5.3 主成分的计算方法及有关性质 §5.4 主成分的计算方法证明,例：一批龟壳化石的长、宽、高数据，请将全部乌龟分为三类,5.1 引言,若存在一个线性关系,或者,或者,或者,观察：长、宽、高之间近似存在线性关系,只需要根据两个变量分类！,5.1 引言,或者,或者,或者,若存在两个线性关系,只需要根据一个变量分类,5.1 引言,据长分类,据高分类,4,4,据宽分类,5,5,根据什么变量分类较好？,4,5,5.1 引言,任取,只要有关向量线性无关，就成立,若存在两个线性关系，例如,5.1 引言,一般性建模问题,使得,和,如果变量间近似线性相关，则存在低维向量,所以，一旦知道,，于是,的样本数据，可考虑低维问题,5.1 引言,主成分分析试图从样本点×定量变量的数据表中，找出最为关键的少数综合变量，能与原有系统数据保持很高的一致性。 实际采用降维方法（如20维降为2维），只选择起最主要作用的自变量和因变量来建模。 在数学上，可以看成将坐标做平移和旋转变换，使得新坐标的原点与样本数据群的重心重合，第一轴（称为第一主轴u1）与数据变异最大的方向对应；第二轴与数据变异次大的方向对应依此类推。经有效舍弃后，主轴u1 u2 up能十分有效地表示原数据的变异情况。,5.2 主成分分析基本原理,主成分分析几何意义： 平移旋转，使得样本点在第一主轴的方差最大,5.2 主成分分析基本原理,变量的样本均值,变量的样本方差,基本准则：分类变量的分散程度越大越有利,变量的分散程度可用其样本方差表示,5.2 主成分分析基本原理,确定分类变量的基本方式,5.2 主成分分析基本原理,辅助措施：对组合变量施加规范化约束,措施1：对原始变量的尺度规范化,措施2：对组合参数的尺度规范化,5.2 主成分分析基本原理,最终的优化模型,其中,该问题的最优解,就是这组样本数据的第一主成分,5.2 主成分分析基本原理,在当前情况下用第一主成分分类最有利！,因为由线性关系,仍可得到,5.2 主成分分析基本原理,任取,只要有关行向量线性无关，就成立,若仅存在一个线性关系，例如,5.2 主成分分析基本原理,类似于前面的讨论，可求解,措施3：,保证两个组合向量线性无关！,5.2 主成分分析基本原理,最终模型,最优解就是第一和第二主成分,5.2 主成分分析基本原理,给定一组样本数据：,一般情况,首先求出其规格化的数据：,5.2 主成分分析基本原理,确定m个主成分的优化模型为,5.2 主成分分析基本原理,符号约定：,5.2 主成分分析基本原理,5.2 主成分分析基本原理,因为,5.2 主成分分析基本原理,结论：,5.3 主成分的计算方法及有关性质,主成分的样本均值,主成分的样本方差,5.3 主成分的计算方法及有关性质,主成分的样本方差之和,5.3 主成分的计算方法及有关性质,样本相关矩阵,因为,所以,5.3 主成分的计算方法及有关性质,分类变量的个数选择准则,设定方差阈值,选择最小的m，满足,取前m个主成分为分类变量,5.3 主成分的计算方法及有关性质,乌龟数例的计算结果,取第一个主成分为分类变量,5.3 主成分的计算方法及有关性质,-2.4310 -2.4410 -2.0023 0.2349 0.1351 -0.6467 0.3475 0.5134 0.1407 2.1487 2.0953 1.9055,主成分,分类结果,1-3,4-9,10-12,5.3 主成分的计算方法及有关性质,5.4 主成分的计算方法证明,基本出发点：实对称矩阵的正交对角分解,5.4 主成分的计算方法证明,记,q(k)是 XXT 的第 k 大的 特征向量对应的特征根,5.4 主成分的计算方法证明,5.4 主成分的计算方法证明,令,注意,所以,5.4 主成分的计算方法证明,5.4 主成分的计算方法证明,记,5.4 主成分的计算方法证明,引理1,则成立,5.4 主成分的计算方法证明,证明,因为,所以,另外，显然成立,5.4 主成分的计算方法证明,因为,记,5.4 主成分的计算方法证明,的对角线元素大于或等于0,证明结束,引理2,则成立,5.4 主成分的计算方法证明,证明,如果m = n，,如果m n，但是,显然成立,下面将推出矛盾，从而证明引理成立。,5.4 主成分的计算方法证明,证明结束,5.4 主成分的计算方法证明,根据引理1,根据引理2,5.4 主成分的计算方法证明,令,5.4 主成分的计算方法证明,5.4 主成分的计算方法证明,因此,是最优解！,回忆,最终,是原问题的最优解！,5.4 主成分的计算方法证明,结论,是优化问题,的一个最优解,5.4 主成分的计算方法证明,例：一批龟壳 化石的长 宽高数据,5.5 主成分在数据压缩中的作用,如前所述，若存在一个线性关系,总之，可以用两个变量的样本数据近似恢复三个变量的样本数据。,或者,或者,或者,5.5 主成分在数据压缩中的作用,或者,或者,或者,若采用规格化的数据，前面三式可化为,可以用两个变量的规格化数据近似恢复三个变量的规格化数据。,5.5 主成分在数据压缩中的作用,更好的做法是极小化逼近误差,确定存储什么数据，其中采用规格化的样本数据是为了平衡不同变量的逼近误差。,有了规格化的样本数据，只要再记住原变 量的样本均值和方差，即可恢复原数据。,5.5 主成分在数据压缩中的作用,或者,或者,或者,同样，若存在两个线性关系,总之，可以用一个变量的样本数据近似恢复三个变量的样本数据。,5.5 主成分在数据压缩中的作用,同样，可以求解优化问题,来确定存储什么数据！,5.5 主成分在数据压缩中的作用,给定一组样本数据：,一般情况：,首先求出其规格化的数据：,5.5 主成分在数据压缩中的作用,然后求解优化问题,可将其写成,由于 L 和 y(t) 均为变量，为使解比较确定，应对它们加一定的限制。,5.5 主成分在数据压缩中的作用,对于数据压缩问题,若列向量 线性相关,5.5 主成分在数据压缩中的作用,对于数据压缩问题,第二、假定 L 满足下式也不影响优化效果,5.5 主成分在数据压缩中的作用,第一、假定 L 列满秩不影响优化效果,有如下两个性质：,因为当 L 列满秩时，存在可逆矩阵 G,使得,和满足,的 P,于是,5.5 主成分在数据压缩中的作用,数据压缩问题成为,下面说明，这组样本数据的前 m 个主成分就是该问题的一个最优解。,5.5 主成分在数据压缩中的作用,为简化符号，考虑下述优化问题,先求各 y(t) 的最优解,将 y(t) 的最优解代入目标函数，可得,5.5 主成分在数据压缩中的作用,因为,5.5 主成分在数据压缩中的作用,原问题等价于,5.5 主成分在数据压缩中的作用,由于,所以,5.5 主成分在数据压缩中的作用,最终可知，求数据压缩问题等价于求解,并且，最优的压缩变量是,它就是前 m 个主成分。,数据压缩问题的相对逼近误差,5.5 主成分在数据压缩中的作用,对于乌龟数例，若用第一个主成分压缩原数据，只需存储:,共15个数据，仅占原数据的15/36=42%,5.5 主成分在数据压缩中的作用,因为,令,相对逼近误差为,5.5 主成分在数据压缩中的作用,注意,能够利用主成分有效压缩数据，是因为数据本身具有可压缩性，这就是样本相关矩阵的特征根相差很大，其本质是变量间近似线性相关。,5.5 主成分在数据压缩中的作用,对某组10维规格化向量的数据压缩问题，用第一至第四个主成分进行压缩和用第一至第五个主成分进行压缩的误差相同；用第一、第三个主成分进行压缩和用第二、第四个主成分进行压缩的误差相同；用第一个主成分进行压缩相对误差是0.6。请求出每个主成分的样本方差。,例题,5.5 主成分在数据压缩中的作用,基于PCA的海量数据压缩实例,5.5 主成分在数据压缩中的作用, 交通数据预处理,压缩与恢复性能评价指标,主要研究结果,其他结果分析,软件展示, 交通数据预处理,交通流中的“尖峰” 这些非线性的尖峰严重影响了PCA对数据的压缩恢复效果。 利用均值滤波器提取“尖峰” 尖峰时刻的交通流量在压缩前单独存储。 用均值滤波器平滑后的流量值代替尖峰值。,5.5 主成分在数据压缩中的作用,压缩与恢复性能评价指标,5.5 主成分在数据压缩中的作用,主要研究结果,主成分分析 第一主成分贡献率达80.97%。 前25个主成分贡献率和达92.88%。,Fig. 压缩比和误差随主成分个数增加的变化趋势,结果 CR(压缩比)为6.2。 平均APRE为13。 平均相关系数为0.9524。,5.5 主成分在数据压缩中的作用,主要实验结果,对于具有不同特征的交通流均可以较好的恢复。 不同的早、晚高峰时间 同一时段不同的流量值 特殊的“尖峰”,Fig 原始数据与恢复数据,5.5 主成分在数据压缩中的作用,其他结果分析,恢复误差分布 具有正态分布的特征 绝大多数恢复数据点与原始数据点基本相同。,对异常数据具有鲁棒性 “尖峰”点 交通流异常（如在白天出现堵车现象时的交通流）,5.5 主成分在数据压缩中的作用,Table 各路口压缩和恢复性能参数,5.5 主成分在数据压缩中的作用,软件展示,5.5 主成分在数据压缩中的作用,龟壳化石数据,5.6 主成分在线性回归中的作用,规格化的重量和长宽高之间存在线性关系,参数估计：,5.6 主成分在线性回归中的作用,相对拟合误差：,另一组样本,5.6 主成分在线性回归中的作用,预报精度：,5.6 主成分在线性回归中的作用,利用全部样本回归,参数估计：,原因分析,求偏导并令偏导等于0，可求得,5.6 主成分在线性回归中的作用,假定最好的参数值是,参数估计误差为,，误差,5.6 主成分在线性回归中的作用,因为,由主成分分析知,5.6 主成分在线性回归中的作用,拟合误差12.2% 预报误差12.4%,一般情况,没有病态问题,5.6 主成分在线性回归中的作用,课后作业,见网络学堂。 提交时间，下周上课前。 网络学堂提交电子版。,