非线性多维数据可视化分类预测方法

1、II9IJ-Jn 上Lr M1.引言非线性多维数据可视化分类预测方法本课题得到国家自然科学基金项目资助(项目编号：40571119);国家社会科学基金资助项目(07BZZ015 )； 国家科技支撑项目资助课题(2006BAB15B03, 2006BAB15B06 )；中国地质大学(北京)人才基金资助项目李志建，郑新奇，赵璐，杨鑫中国地质大学(北京)土地科学技术学院，北京(100083)E-mail: zxqsd摘要：地理信息分类的传统线性算法具有正向直接判定的快速优势，但局限于对已知数据进行线性的判别划分，而非线性未知信息的分类预测同样是GIS技术的重要内容。人工神经网络算法为一些非线性知识的

2、发现提供了可能。本文在通用的GIS格式数据基础上，采用L-M算法进行分类，通过分类结果来预测未知信息。开发出可视化的GIS数据神经网络分类预测软件模块。并以美国各镇人口为样例数据进行测试，分类预测结果显示该算法具有可行性及系统具有实用性。关键词：空间数据挖掘；L-M算法；可视化；分类预测-1 -II9IJ-Jn 上Lr M-# -II9IJ-Jn 上Lr M分类技术是数据挖掘中的重要运用，而当前采用的主要分类算法1,2，(51900912300)的资助。都是基于各种距离或者角度的线性算法。无法处理空间数据挖掘过程中类似于人口增长与资源消耗的的非线性要求数据对象符合一定的统计学规近朱者赤”的假设

3、条件的基础。而在这种情况下，以上算法就失去关系。其次，传统分类算法可以被认为是统计分类手段。 律或数据模型。如线性的距离分类算法就是基于数据满足 空间数据挖掘对象往往是没有已知的数据模型和统计规律。了前提条件。再次，传统分类算法是在统计结果的基础之上对已知的属性进行判别分类。对潜在的未知的信息， 此类算法就无能为力了。 神经网络4算法为这个问题的解决提供了可能， 该方法很少需要关于实际数据的统计分布规律的假设；很少需要对模型的数学分析，但可以从大量样本数据中生成用于实现复杂非线性映射的模型5;可以通过已知的属性信息映射成未知信息的分类结果，从而达到预测的目的。 多层前向神经网络具有理论上可逼近

4、任意非线性连续映射的能力 6, BP神经网络算法是最早提出的该类型算法。实际运用中发现采 用梯度下降法的 BP算法存在收敛速度很慢，往往收敛于局部极小点其数值稳定性差，学习率、动量项系数和初始权值等参数难以调整的缺点。交互式可视化分类在一些遥感软件中运用的很普遍7。鉴于空间矢量数据的特殊性质，它的分类一般是通过统计方式对在属性数据层上进行分类。因此，本文借鉴遥感软件中的交互分类方法，对空间矢量数据实现可视化的交互分类过程，设计了L-M算法。其线性分类预测结果达到了传统分类算法的精度。非线性的预测结果也满足实际要求。2. 分类器设计进行多维空间数据分类算法有很多种，我们经过比较分析，选择了 L-

5、M (Levenberg-Marquardt )算法，即列文伯格-马夸尔特法。该算法是最小二乘拟合中的一种 算法，属于非线性最优化算法，是BP算法改进的一种途径，具有逼近最小误差的速度快、精度高等特点。实际上L-M算法是梯度下降法与高斯-牛顿法的结合。就训练次数与精确度而言，它明显优于共轭梯度法及变学习率的BP算法,适用于分类预测。2.1 L-M算法数学基础L-M算法主要解决的是如下形式的非线性最小二乘问题(1)f(x)二 + £r；(x)其中x = (xX2xn)为一个n维向量，r为由Rn到R的映射函数，口可以认为是最小二乘 的残差。这里设n奇。上式可以进一步简化，令r为残差向量，

6、r = (ri, r2rm)，得1 2f(x) = 2l|r|1此时的f可以用r的jacobian式子J表示了,J =,1弓<m, 1 W <n。先考虑线性情况?xi下，此时J为常数，r可以理解理解为一个超平面，从而 f (x) = 1 | Jx + r(0) |2。同时可以 得到？f(x) = JT(Jx+r) , ?2f(x) = JTJ。要求(1)式的最小值，只要满足 ？f(x)=o即 可。解得Xmin =-(JTJ)-1JTr。再考虑非线性的情况可得：10m?f(x) = ”rj(x)?rj(x)=JT(x)rj(x)(3)j=1m?2f (x) = JT(x)J(x) +

7、 ”rj(x)?2rj(x)(4)j=1(4) 式的右边第二项为 2次高价导数数，且残差本身就很小，所以一般忽略不计。于是得 到近似线性的Hessian矩阵(4)。需要注意的是这里是假设了残差很小，对于残差很大的情 况不能忽略高阶项。L-M算法是个迭代的过程， 设W (K)表示第K次得迭代的网络权重向量， 相当于(1)式的x向量，维数为 M。把？f(W(k + 1)按Taylor级数展开可得11:?f (W(k + 1) =?f (W(k) + (W(k +1)- W(k)T? 2 f (W(k) + °W(k + 1)- W(k) (5) 令(5)式左边等于0求最小二乘解，可得牛顿

8、迭代策略：W(k+1) =W(k)- (?2f (W(k)-1?f (W(k)(6)如果再考虑进最速下降法便得到L-M的迭代策略：W(k + 1)=W(k)- (H + AI)-1?f(W(k)(7)其中H为Hessian矩阵。可以发现，当 入很小时，就接近于牛顿法，而入 很大时就是最速下降法，因此L-M算法实际上是上面两种迭代算法的组合。2.2分类器设计系统中设计的分类网络包括输入层、隐藏层和输出层。 考虑到训练速度，只设计了一个隐藏层。输入层的神经元数目是根据训练字段数动态确定的。隐藏层的神经元数目由用户动态确定，一般不要超过 7,否则将会影响训练速度。输出层神经元个数等于分类结果数目。

9、如图1所示。-3 -Bi zJ Tr Mr M图1分类网络示意图各权重被初始化为 0-1之间的实数。前向计算提供了sigmoid、tanh、和tan sig三种激活函数，可以根据实际需要选取。根据BP神经网络的导数处理方法，程序中对导数的处理如下：cq表示q神经网络J =入 01- Oq） Op（8）按（3） （4）两式计算一二阶导数，按（7）式修改权重迭代计算。其中 层的输出值，Op表示q层的上一神经网络层的输出值。3. 系统可视化设计采用的是VC+6.0和mapobject2.4开发环境。系统可视化主要体现在训练样本数据的选 取可视化和数据预测分类结果的显示上。数据处理流程如图2。预测预测

10、姑柴分析分类器分类图2 分类流程图输入数据可以为 SDE空间数据库和SHP文件格式数据。核心训练分类包括样本选择、网络训练、目标分类三个模块。预测结果分析采用专题图的方式，划分结果以不同地类符号及颜色库加以区分。用户可以通过符号或颜色判定数据类别，达到预测结果的目的。可视化界面由核心训练分类的三个模块组成，界面如图3、图5所示。分类列表飙色样榊丽II52.鵬賞玉用朮景中心点坐柿嚅定图3训练样本选取界面图4样本选择当用户打开了一个分类目标图层时，就可以通过训练样本选取界面（图3）选择要训练的字段，如上图选取的是单价字段。由于训练数据必须是实数型，加载训练字段时会对名义 型字段过滤。当然还可以添加

11、中心点坐标作为训练数据。系统支持用户在地图界面上框选样本数据。如图4为样本选择结果示例。网络训练是在后台完成，用户只需要在可视化界面下设置相应的参数（图5）。步长就是（7）式中的入值，训练过程中，系统会动态调整该值。当系统误差小于系统精度或训练次数达到最大训练次数时停止训练。训练算法采用L-M算法。激活函数为正向计算每层的-5 -Bi zJ Tr M-# -Bi zJ Tr M输出值的函数。见图5。图5网络训练参数设置图分类颜色设呈类别数开始颜色结東颜色确定I匚取消z"* J图6图层分类界面-# -Bi zJ Tr M-# -Bi zJ Tr M网络训练完以后，分类器即构造完毕。 系

12、统通过该分类器对目标图层分类。分类界面中类别数是样本选取的时候确定的，这里只可以设置分类后的颜色显示。如图6。4. 试验与分析试验数据来源于 ESRI公司随软件提供的数据，包括1990年、1999年两期城市、州的矢量数据。数据格式为.shp.试验过程中，首先选取城市数据进行计算。为了对比算法的线性分类情况，考虑1990年和1999年人口的关系分布而进行分类。选择样本数据时将两年的比值情况按高低情况分为了 4类。最大训练次数为 1000次。分类结果如图 7和图9。图元级的对比结果如图11。由图11可以看出各类别的图元数目在起始类时有较大差异，这是由于该类的训练样本数据 选的不足，且不同类别之间的

13、样本差异较小造成的。其他类有50%以上的图元在两种算法下划分一致，且重叠样本图元数目比例都很大，基本和图元数小的对应类的图元数相等。从图7和图9上也可以发现L-M学习到了这种线性关系。表明L-M算法同样适用于线性分类图7基于ArcGIS分类结果图8添加中心坐标多字段训练预测结果图9 未采用中心坐标的L-M分类结果图10未加中心坐标多字段预测结果35000000300000002500000020000000图11线性分类对比一二人口预测图15000000100000005000000人口下界POP1999人口上界图12aKsakrt naarncHM analsluuL htuaolip S&

14、amp;IS&HM OCIXxM W&N eessennn amphaIKU iruosHM sasnatuglnseQdarpoctssw.oatpkku hru§.tnomr&vnoasLUaKsalDaNdms eeohha_J人口预测图表情况。其次对州数据进行计算。图8、图10和图12是通过1990年人口、白人人数、亚裔人数预测1999年各州的人口的专题图和预测曲线图。图8是添加了中心点坐标的分类结果。对比图10可以发现，图8的分类结果更趋向于地理位置的相邻相似。人口分布由于存在中 心扩散的情况，所以和地理位置必然存在潜在关系。而其实某些情况下是不适合

15、添加坐标训练的。笔者对上述的两期人口比值添加中心坐标训练后，发现结果完全由空间位置主导，反映的比值信息很少。因此可以得到以下结论，不适合将和空间位置不相关的预测要素添加中 心点坐标作为训练字段。当然这可以通过试验的方式来验证。图12是图10的预测结果和实际1999年人口的曲线分布。前面谈到预测结果只能以一个范围的形式给出， 蓝色曲线是预测结果的人口下界，黄色曲线是预测人口的上界，品红色曲线是1999年人口的实际情况。其中超过黄色上界的有California,Texas两个州，低于蓝色下界的有 South Dakata,Wisconsin,Utah 等6个州。而差值绝对值最大的为12961。相对

16、于最小州人口数482025，误差也只为2.6%。其他州的人口分布都集中于预测范围之内(品红曲 线在红线和蓝线之间)。这里采用了三个属性来对未知信息预测，从这三个训练属性的分布 曲线中可以发现1990年总总人口和白人人数分布相似，而亚裔人数曲线没有太大起伏，鉴 于篇幅原因，略去该图。这说明三者存在某种潜在的非线性映射关系，L-M神经网络算法能够捕捉并学习到这种关系，预测结果的精度也基本满足实际情况，具有实用性。5. 结论与探讨本研究对空间数据预测分类中神经网络算法的应用和优化进行了初步探讨。所实现的基于L-M算法的GIS数据神经网络分类预测系统不仅能够发现并学习多维样本间的线性关系， 而且可以建

17、立其非线性映射模型，发现潜在的非线性映射关系。线性分类预测结果达到了传统分类算法的精度，非线性的预测结果也满足实际要求。本研究案例中非线性预测结果的范围还比较粗，在提供更多更准确的训练样本数据可以得到更为精确的预测分类结果。算法本身是一个迭代的过程，对一些样本很大、训练字段太多的数据，训练可能无法执行，系统网络训练效率还需进一步提高。进一步研究将对算法进行优化以提高训练效率，从而满足对多维、多尺度、海量数据分类的需求。参考文献1 郭云开，张起森.基于广义夹角的遥感图象计算机分类方法J.中国公路学报，2002,15(2):28-30,35.2 金连文，梁宇杰.一种新的距离分类方法及其应用J.计算

18、机工程,1999,25(8):30-31,57.3 胡立辉，罗国松.改进的基于矢量空间的群体聚类算法J.系统工程与电子技术，2007,29(3):472-474.4 McClellan G E, DeWitt R N, Hemmer T H, et al. Multispectral Image-processing with a Three-layer Back-propagatio n Network. Intern ati onal Joint Conference on Neural Networks, Washi ngton D C,1989.5 赵波,边馥苓.基于神经网络的GIS空

19、间数学模型研究J.计算机工程与运用，2006,(13):197-208.6 赵弘,周瑞祥.基于Levenberg-Marquardt算法的神经网络监督控制J.西安交通大学学 报,2002,5(5):523-527.7 贾泽露,刘耀林，张彤.可视化交互空问数据挖掘原型系统设计与实现J.武汉大学学报(信息科学版),2006,31(10):916-919.8 K. Leve nberg A method for the soluti on of certa in problems in least squaresJ, Quart. Appl.Math., 1944, (2): 164- 168.9

20、D. Marquardt An algorithm for least-squares estimati on of non li near parametersJ,SIAM J.Appl. Math., 1963,(11): 431 441.10 More J J. The Levenberg-Marquardt Algorithm: Implementation and TheoryJ. Numerical An alysis, ed. G. A.Wats on Lecture Notes in Mathematics 630, Spri ngerVerlag, 1977, 105 116

21、.11 王建梅，覃文忠.基于L-M算法的BP神经网络分类器J.武汉大学学报(信息科学版),2005,30(10):928-931.-7 -II9IJ-Jn 上Lr MNonlinear and Multi-dimensional Visualization of DataClass- predicting MethodLi Zhijia n, Zheng Xin qi, Zhao Lu, Yang XinSchool of Land scie nee and Tech no logy, China Uni versity of Geoscie nces (100083)AbstractTraditi on al li near classificati on algorithms of GIS have the adva ntage of determ ining in positive direct ion quickly, but have the limitatio n in determ ining the give n data lin early. However, the class-predict ing for the unknown non-l in ear in formati on is the importa nt part of GIS