投影寻踪方法及其应用.ppt

投影寻踪方法及其应用 金 菊 良 合肥工业大学土木建筑工程学院水利系 (邮编 230009，电话JINJL66126.com) 报告内容 1 投影寻踪方法的基本原理与建模步骤 4 总结与讨论 3 基于加速遗传算法的投影寻踪等级评价模型 2 基于加速遗传算法的投影寻踪聚类模型 1 投影寻踪方法的基本原理与建模型步骤 1.1 投影寻踪方法的基本原理 投影寻踪(projection pursuit，PP)方法属于直接由 样样本数据驱动驱动 的探索性数据分析方法。它把高维数 据x(i,j)通过某种组合投影到低维子空间上z(i)， 对于投影到的构形，采用投影指标函数Q(z(i)来描 述投影暴露原系统统某种分类排序结构的可能性大小 ，寻找出使投影指标函数达到最优（即能反映高维 数据结构或特征）的投影值z(i)，然后根据该投影值 来分析高维数据的分类结构特征（如投影寻踪聚类 评价模型），或根据该投影值与研究系统的实际输 出值之间的散点图构造适当的数学模型以模拟系统 输出（如投影寻踪等级评价模型）。 1 投影寻踪方法的基本原理与建模步骤 1.2 投影寻踪方法的建模步骤 步骤1：高维样本数据的预处理 ，确定系统输入。 步骤2：构造投影指标函数。 步骤3：优化投影指标函数。 步骤4：建立系统模型。 2 基于加速遗传算法的投影寻踪聚类模型AGA-PPCE 2.1 基于加速遗传算法的投影寻踪聚类模型的建立 步骤1：评价指标值的归一化处理。设样本集为 x*(i,j)| i =1n, j=1p。其中x*(i,j)为第i个样本第j个 指标值。为消除各指标值的量纲和统一各指标值的 变化范围，可采用下式进行极值归一化处理： 式中，xmin(j)、xmax(j)分别为样本集中第j个指标值的 最小值和最大值。 2 基于加速遗传算法的投影寻踪聚类模型AGA-PPCE 2.1 基于加速遗传算法的投影寻踪聚类模型的建立 步骤2：构造投影指标函数。PP方法就是把p维数据x(i,j)| j=1p综合成以a=(a(1),a(2), ,a(p)为投影方向的一维投影值 z(i) 然后根据z(i)| i=1n 的一维散布图进行分类。式(2.2)中a为单位长度 向量。在综合投影值时，要求投影值z(i)的散布特征应为：局部投影 点尽可能密集，最好凝聚成若干个点团；而在整体上投影点团之间 尽可能散开。据此投影指标函数可构造为 Q(a)= Sz Dz (2.3) 式中，Sz为投影值z(i)的标准差，Dz为投影值z(i)的局部密度，即 2 基于加速遗传算法的投影寻踪聚类模型AGA-PPCE 2.1 基于加速遗传算法的投影寻踪聚类模型的建立 步骤3：优化投影指标函数。当各指标值的样本集给定时，投 影指标函数Q(a)只随投影方向a的变化而变化。可通过求解投 影指标函数最大化问题来估计最大可能暴露高维数据某类特 征结构的最佳投影方向 ： max Q(a)= Sz Dz (2.4) 这是一个以a(j)|j=1p为优化变量的复杂非线性优化问题，用 模拟生物优胜劣汰规则与群体内部染色体信息交换机制的加速 遗传算法（AGA）来求解上述问题较为简便和有效。 加速遗传算法（AGA） 步骤1：模型参数的编码。设码长为e，第j个参数的 变化区间为aj，bj，j=1p。把这些区间等分成2e-1个 子区间： cj=aj+Ijdj (2) 式中子区间长度dj=(bj-aj)/(2e-1)是常数；搜索步数Ij 为小于2e的十进制整数，是变数；j=1p(下同)。把Ij转 化成e位二进制数ia(j, k)，k=1e(下同)，即式(3) ： 步骤2：初始父代群体的随机生成。 生成n组各p个均匀随机数(简称随机数)u(j,i) ，i=1n，经下式转换成十进制整数。 Ij(i)=INTu(j,i)2e (4) 式中INT为取整函数。由式(3)得对应二进制 数ia(j,k,i)，它们与n组模型参数cj(i)对应，并 把它们作为初始父代个体群。 编码与解码的逻辑过程：cj(i) Ij(i) ia(j, k,i) 步骤3：父代个体适应能力评价。 把第i组参数代入式(1)得目标函数值fi，fi越 小表示模型与观测值拟合得越好，适应能力 越强，设第i个个体的适应能力与fi成反比。 构造选择概率序列pi，把0，1区间 分成n个子区间：(0，p1)，(p1，p2)，pn- 1，pn，它们与n个个体一一对应，fi越小的 个体对应的子区间长度越大。 步骤4：父代个体的概率选择。 生成n个随机数 ui |i=1n，若 uipi-1，pi， 则选取第i个父代个体，其二进制数记为 ia1(j,k,i)。同理可得另外的n个父代个体 ia2(j,k,i)。选择是遗传算法的关键，它体现 了优胜劣汰的思想。 步骤5：父代个体的杂交。 由步4得到的父代个体配对成n对双亲。生 成两随机数u1和u2，再转成十进制整数： IU1=INT(1+u1e)，IU2=INT(1+u2e)，设 IU1IU2（否则互换其值）。杂交是指第i对双 亲ia1(j,k,i)和ia2(j,k,i)随机变换一段二进制数，从 而生成第i对子代个体： 0 1 1 0 10 0 1 0 1 (5) 1 0 1 0 01 1 1 0 0 (6) (杂交前) (杂交后) 步骤6：子代个体的变异。 生成随机数u1，u2，u3和u4。当u10.5时 子代个体取式(5)，否则取式(6)，记其二进制数 为ia(j, k,i) 。把u2、u3转换为十进制整数： IU1=INT(1+eu2)，IU2=INT(1+eu3) 设子代变异的概率(称为变异率)为pm。变异是 当u4pm时对子代个体的IU1位和IU2位的值进行 翻转操作： 0 1 1 0 10 0 1 1 1 (变异前) (变异后) 步骤7：进化迭代。 第i个子代个体经式(3)、式(2)转化成第i组 模型参数。这n个子代个体作为新的父代，算 法转入步3，进入下一轮进化过程，重新评价、 选择、杂交、变异，如此反复进化，使个体的 适应能力不断提高，直到最优个体的优化准则 值小于某一指定值或最优个体的优化准则值不 再改善，则终止进化迭代，算法结束。 (a)初始分布 (b)第20次进化迭代后的分布 (c)第60次进化迭代后的分布 步骤8：加速循环。 用第一次、第二次进化迭代所产生的优 秀个体的变量变化区间作为变量新的初始变 化区间，算法进入步骤1，重新运行SGA算法 ，如此加速循环，优秀个体的变化区间将逐 步调整和收缩，与最优点的距离将越来越近 ，直到最优个体的优化准则函数值小于某一 设定值或算法运行达到预定加速(循环)次数， 结束整个算法的运行。此时，就把当前群体 中最佳个体或优秀个体的平均值指定为AGA 的结果。 AGA的主要特点 利用标准遗传算法演化过程中的优秀个体子 群体来逐步调整、压缩算法的搜索空间。 控制参数设置：二进制编码长度e、杂交概率 和变异率分别固定设置为10、1.0和1.0；群体 规模n与优秀个体数目s关系：s/nn/(e2e)， (n,s)的常用配置有(300,10)、(400,20)和 (500,30)；每次加速循环中AGA只进行两次 SGA的进化迭代。 p个变量、加速循环q次，优秀个体包围最优 点的概率为(1-0.52s)pq 步骤4：建立聚类模型。把由步骤3求得的 最佳投影方向a*代入式(2.2)后，得各样本点 的投影值z*(i)。投影值z*(i) 与z*(j)越接近， 表示样本i与样本j越倾向于分为同一类。按 z*(i)值从大到小排序，据此可把各指标的样 本集进行分类。 2 基于加速遗传算法的投影寻踪聚类模型AGA-PPCE 2.2 基于加速遗传算法的投影寻踪聚类模型在气候区划中的应用 气候区划就是把研究区域划分成若干个分区，在同一分区内具有相似 的气候条件，以便调整种植结构，因地制宜地发展农业生产。 表2.1 气候样本集及其投影值 气候因子j j=1 j=2 j=3 j=4 j=5 j=6 j=7 j=8 j=9 j=10 样样本 年平均 极端最高 极端最低 10年 年降水 年日照 年均相对对 无霜 海拔 凌冻冻天 投影值值 气温/C 气温/C 气温/C 积积温/C 量/mm 数/h 湿度/% 期/d 高度/m 数/d z*(i) 1毕节毕节 12.9 33.6 10.1 3672.0 904.3 1236.0 82 250 1510.6 15.2 1.295 2大方 11.8 31.5 8.8 3332.8 1176.9 1265.9 84 256 1700.0 33.2 1.283 3黔西 14.1 35.4 8.6 4047.4 964.1 1263.6 81 274 1272.1 14.6 1.722 4金沙 15.1 36.0 6.2 4703.3 1049.7 1091.6 81 304 920.0 7.5 2.191 5织织金 14.2 33.1 9.5 4264.2 1432.6 1165.6 82 280 1319.0 11.8 1.728 6纳纳雍 13.7 33.5 8.4 4005.6 1234.3 1447.7 81 268 1457.1 14.2 1.625 7威宁 10.4 31.1 14.5 2572.8 943.5 1960.3 80 190 2234.5 63.9 0.271 8赫章 13.4 35.7 11.6 3948.9 892.8 1400.8 79 244 1534.9 12.4 1.282 图2.1 气候样本投影值z*(i)的散布图 由表2.1和图2.1可知：该样本集按投影值z*(i)从大到小排序的样本序 号依次为样本点4、5、3、6、1、2、8和7。其中，样本4可单独分为A类， 样本5、3、6、1、2和8可分为B类，样本7可单独分为C类，该分类结果与 文献“刘崇欣. 黔西北林木气候区划的聚类分析. 农业系统科学与综合研究 ,1997,13(3) ”的模糊聚类结果和根据表2.1各样本的对比分析结果都是一致 的。 B类可进一步细分为由样本5、3和6组成的B-1类和由样本1、2和8组 成的B-2类。 根据文献所示各样本的地理位置可知，以上分类具有明确的地理意 义：A类、B类和C类分别位于研究区域的东部、中部和西部，B-1类和B-2 类分别位于研究区域的中南部和中北部。 3 基于加速遗传算法的投影寻踪等级评价模型AGA-PPGE 3.1 AGA-PPGE的建立 步骤1：评价指标值的标准化处理。设样本 集为x*(i,j)| i =1n, j=1p。其中x*(i,j)为第i 个样本第j个指标值。为消除各指标值的量 纲和统一各指标值的变化范围，可采用下式 进行标准化处理： 式中，Ex(j)、Sx(j)分别为原第j个评价指标 x*(j,i)|i=1n的均值和标准差。 3 基于加速遗传算法的投影寻踪等级评价模型AGA-PPGE 3.1 AGA-PPGE的建立 步骤2：构造投影指标函数。PP方法就是把p维数据x(i,j)| j=1p综合 成以a=(a(1),a(2), ,a(p)为投影方向的一维投影值z(i) 式中，a为单位长度向量。在综合投影值时，要求投影值z(i)应尽可能多地 提取x(j,i)中的变异信息，即z(i)的标准差Sz达到尽可能大，同时要求z(i) 与已知标准等级值y(i)的相关系数的绝对值|Rzy|达到尽可能大。为此，投影 指标函数可构造为 Q(a)= Sz |Rzy| 式中，Sz和Rzy分别为 3 基于加速遗传算法的投影寻踪等级评价模型AGA-PPGE 3.1 AGA-PPGE的建立 步骤3：优化投影指标函数。当给定标准等级 及其评价指标的样本数据y(i)|i=1n和 x*(j,i)|j=1p,i=1n时，投影指标函数Q(a)只随投 影方向a的变化而变化。不同的投影方向反映不同 的数据结构特征，最佳投影方向就是最大可能暴露 高维数据某类特征结构的投影方向。可通过求解投 影指标函数最大化问题来估计最佳投影方向 ： max Q(a)= Sz |Rzy| 这是一个以a(j)|j=1p为优化变量的复杂的非 线性优化问题，用AGA可方便地求解上述优化问 题。 3 基于加速遗传算法的投影寻踪等级评价模型AGA-PPGE 3.1 AGA-PPGE的建立 步骤4：建立投影寻踪等级评价模型。把由步骤3求得的最佳投影 方向的估计值a*代入投影值公式后，得第i个样本投影值的计算值 z*(i)，根据z*(i)y(i)的散点图建立相应的等级评价模型。z*(i)与 y(i)之间一般呈单调非降关系，当z*(i)值超过某门限值时就判定为 最高等级(N级)，当指标值低于另门限值时就判定为最低等级(1 级)，当z*(i)值介于这两门限值之间时则为中等等级，可用逻辑斯 谛曲线来描述： 式中y*(i)为第i个样本等级的计算值；模型参数c(1)、c(2) 分别为 积分常数和增长率，可通过求解如下优化问题来确定： 3 基于加速遗传算法的投影寻踪等级评价模型AGA-PPGE 3.2 AGA-PPGE在洪水灾情等级评价中的应用 表3.1 河南省洪水灾情等级标准 灾情等级指标 一般灾 较大灾 大灾 特大灾 成灾面积(hm2) 283.3 直接经济损失(亿元) 85.0 根据表3.1，可用如下方法随机产生各灾情指标值及其对应的标准灾情等级样本系 列：四个灾情等级值一般灾、较大灾、大灾、特大灾分别对应标准灾情等级值1 、2、3、4。 确定一般灾的左端点值和特大灾的右端点值，这里分别取为一般灾的右端点值 的0.5倍和特大灾的左端点值的3倍，这样，所有灾级都有一个范围。 利用均匀随机数在每个灾级范围内产生5个值，考虑到直接经济损失一般与成 灾面积具有正相关性，同一样本点的直接经济损失的随机数应与成灾面积的随机数 相同。 在灾情等级标准表中取边界值各一次，灾情等级值取与该边界值有关的两个灾 级值的算术平均值。这样得到的样本点如表3.2序号123所示。 表3.2 洪水灾情等级的标准值和PPGE模型的计算值的对比结果 序号 灾情指标 投 影 洪水灾情等级 序号 灾情指标 投 影 洪水灾情等 级 i x*(1,i) x*(2,i) 值z*(i) 标准值 计算值 i x*(1,i) x*(2,i) 值z*(i) 标准值 计算 值 1 38.70 7.900 -1.178 1.0 1.369 17 157.30 38.600 - 0.469 3.0 2.486 2 38.50 7.800 -1.180 1.0 1.366 18 283.30 85.000 0.422 3.5 3.498 3 32.10 6.500 -1.215 1.0 1.315 19 556.90 167.100 2.171 4.0 3.967 4 24.20 4.900 -1.257 1.0 1.256 20 649.50 194.900 2.763 4.0 3.987 5 36.40 7.400 -1.191 1.0 1.350 21 602.30 180.700 2.461 4.0 3.979 6 46.70 9.500 -1.135 1.5 1.432 22 446.50 134.000 1.466 4.0 3.897 7 97.60 21.700 -0.840 2.0 1.895 23 694.90 208.500 3.053 4.0 3.992 8 60.40 12.800 -1.056 2.0 1.552 1950 72.92 9.900 -1.042 2.0 1.574 9 112.60 25.200 -0.755 2.0 2.033 1954 148.13 20.656 -0.679 2.0 2.156 10 56.20 11.800 -1.080 2.0 1.515 1956 203.92 27.521 -0.421 3.0 2.559 11 80.60 17.600 -0.939 2.0 1.736 1957 179.10 24.858 -0.532 3.0 2.389 12 136.70 31.000 -0.615 2.5 2.258 1963 375.46 94.927 0.83