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

投影寻踪方法及其应用金菊良合肥工业大学土木建筑工程学院水利系(邮编230009，电话0551-2903357，JINJL66),报告内容,1投影寻踪方法的基本原理与建模步骤,4总结与讨论,3基于加速遗传算法的投影寻踪等级评价模型,2基于加速遗传算法的投影寻踪聚类模型,1投影寻踪方法的基本原理与建模型步骤,1.1投影寻踪方法的基本原理投影寻踪(projectionpursuit，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)=SzDz(2.3)式中，Sz为投影值z(i)的标准差，Dz为投影值z(i)的局部密度，即,2基于加速遗传算法的投影寻踪聚类模型AGA-PPCE,2.1基于加速遗传算法的投影寻踪聚类模型的建立步骤3：优化投影指标函数。当各指标值的样本集给定时，投影指标函数Q(a)只随投影方向a的变化而变化。可通过求解投影指标函数最大化问题来估计最大可能暴露高维数据某类特征结构的最佳投影方向：maxQ(a)=SzDz(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对子代个体：0110100101(5)1010011100(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位的值进行翻转操作：0110100111(变异前)(变异后),步骤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气候样本集及其投影值气候因子jj=1j=2j=3j=4j=5j=6j=7j=8j=9j=10样本年平均极端最高极端最低10年年降水年日照年均相对无霜海拔凌冻天投影值气温/C气温/C气温/C积温/C量/mm数/h湿度/%期/d高度/m数/dz*(i)1毕节12.933.610.13672.0904.31236.0822501510.615.21.2952大方11.831.58.83332.81176.91265.9842561700.033.21.2833黔西14.135.48.64047.4964.11263.6812741272.114.61.7224金沙15.136.06.24703.31049.71091.681304920.07.52.1915织金14.233.19.54264.21432.61165.6822801319.011.81.7286纳雍13.733.58.44005.61234.31447.7812681457.114.21.6257威宁10.431.114.52572.8943.51960.3801902234.563.90.2718赫章13.435.711.63948.9892.81400.8792441534.912.41.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.1AGA-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.1AGA-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.1AGA-PPGE的建立步骤3：优化投影指标函数。当给定标准等级及其评价指标的样本数据y(i)|i=1n和x*(j,i)|j=1p,i=1n时，投影指标函数Q(a)只随投影方向a的变化而变化。不同的投影方向反映不同的数据结构特征，最佳投影方向就是最大可能暴露高维数据某类特征结构的投影方向。可通过求解投影指标函数最大化问题来估计最佳投影方向：maxQ(a)=Sz|Rzy|这是一个以a(j)|j=1p为优化变量的复杂的非线性优化问题，用AGA可方便地求解上述优化问题。,3基于加速遗传算法的投影寻踪等级评价模型AGA-PPGE,3.1AGA-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.2AGA-PPGE在洪水灾情等级评价中的应用表3.1河南省洪水灾情等级标准灾情等级指标一般灾较大灾大灾特大灾成灾面积(hm2)283.3直接经济损失(亿元)85.0根据表3.1，可用如下方法随机产生各灾情指标值及其对应的标准灾情等级样本系列：四个灾情等级值一般灾、较大灾、大灾、特大灾分别对应标准灾情等级值1、2、3、4。确定一般灾的左端点值和特大灾的右端点值，这里分别取为一般灾的右端点值的0.5倍和特大灾的左端点值的3倍，这样，所有灾级都有一个范围。利用均匀随机数在每个灾级范围内产生5个值，考虑到直接经济损失一般与成灾面积具有正相关性，同一样本点的直接经济损失的随机数应与成灾面积的随机数相同。在灾情等级标准表中取边界值各一次，灾情等级值取与该边界值有关的两个灾级值的算术平均值。这样得到的样本点如表3.2序号123所示。,表3.2洪水灾情等级的标准值和PPGE模型的计算值的对比结果序号灾情指标投影洪水灾情等级序号灾情指标投影洪水灾情等级ix*(1,i)x*(2,i)值z*(i)标准值计算值ix*(1,i)x*(2,i)值z*(i)标准值计算值138.707.900-1.1781.01.36917157.3038.600-0.4693.02.486238.507.800-1.1801.01.36618283.3085.0000.4223.53.498332.106.500-1.2151.01.31519556.90167.1002.1714.03.967424.204.900-1.2571.01.25620649.50194.9002.7634.03.987536.407.400-1.1911.01.35021602.30180.7002.4614.03.979646.709.500-1.1351.51.43222446.50134.0001.4664.03.897797.6021.700-0.8402.01.89523694.90208.5003.0534.03.992860.4012.800-1.0562.01.552195072.929.900-1.0422.01.5749112.6025.200-0.7552.02.0331954148.1320.656-0.6792.02.1561056.2011.800-1.0802.01.5151956203.9227.521-0.4213.02.5591180.6017.600-0.9392.01.7361957179.1024.858-0.5323.02.38912136.7031.000-0.6152.52.2581963375.4694.9270.8344.03.72613259.1076.1000.2513.03.3631964301.2447.8360.1123.03.23314200.1054.400-0.1663.02.9151975141.97116.4390.2573.03.36815280.1083.8000.3993.03.4811982279.84121.1270.7724.03.69916236.1067.6000.0883.03.2091984172.0651.619-0.2893.02.750,图3.1河南省洪水灾情投影值z*(i)与标准灾情等级y(i)的散点图图3.1表明，可用逻辑斯谛曲线来描述z*(i)与y(i)间的关系，其中参数N=4，c(1)、c(2)通过用AGA优化估计，这样得到的河南省洪水灾情等级的PPGE模型为,用PPGE模型和河南省1950至1990年41a中实际发生的9次大的洪灾损失资料进行灾情等级评估，结果参见表3.2序号1950至1984这9次洪水，它们的灾情等级标准值取神经网络模型的评估结果，可见两模型的评定结果相一致，PPGE模型的灾级分别率更高。如1950年的洪灾，成灾面积和直接经济损失的灾情指标值都在一般灾级与较大灾级的边界处附近，因此PPGE模型评估该年的灾级为1.574是合理的。,4总结与讨论,（1）应用投影寻踪方法过程中富有创新之处是如何构造反映研究问题要求的投影指标函数。（2）用遗传算法等适应性强的优化方法优化投影指标函数和系统模型的参数。（3）通过应用投影寻踪方法解决各种实际系统问题，不断提高对这些问题的认识。,谢谢大家！,