数据挖掘在基于GIS自动导航系统中的应用

２００７年９月　第２８卷　第９期　韶关学院学报・自然科学　ｏｕｍａｌ　ｏｆ　Ｓｈａｏ￣ｕａｎ　Ｕｎｉｖｅｒｓｉｔｙ・Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｓｅｐ．２００７　Ｖｏ１．２８　Ｎｏ．９　数据挖掘在基于ＧＩＳ自动导航系统中的应用　黄学宏，彭昕昀　（韶关学院信息工程学院，广东韶关５１２００５）　摘要：车辆自动导航系统是智能运输系统的一个重要组成部分．提出了一种数据挖掘的复合聚类分析算法，结合　ＧＩＳ系统在自动导航系统中线路设计方面的应用进行分析．实验证明这种复合聚类算法比传统的算法更加有效．　关键词：数据挖掘；地理信息系中图分类号：ＴＰ３１１，１３　（ＧＩＳ）；复合聚类分析算法；自动导航系统　文章编号：１００７—５３４８（２ｏｏ７）ｏ９—００１７—０３　文献标识码：Ａ　数据挖掘（Ｄａｔａ　Ｍｉｎｉｎｇ，ＤＭ）是一个从大量的数据中抽取出潜在的、有价值的知识（模型或规则）的过　程…．有许多种ＤＭ方法，聚类分析方法是其中的一种．这种方法把每个分类对象称为样品，并根据对象的　性质和分类的目的选定若干指标（变量），对每一个样品测出所有的指标值，将得到的结果列一个数据矩阵，　这个资料矩阵是聚类分析的出发点　』．　Ｋ均值聚类算法是最常用的划分方法之一，首先从ｎ个数据对象任意选择ｋ个对象作为初始聚类中　心，其他对象则根据它们与这些聚类中心的相似度（距离），分别分配给与其最相似的（聚类中心所代表的）　聚类；然后计算每个所获新聚类的聚类中心（该聚类中心中所有对象的均值），不断重复这一过程直到标准　测度函数开始收敛为止．这种算法使各聚类本身尽可能紧凑，而各聚类之间尽可能分开．只是它不适合用　于发现非凸性状的聚类，或具有各种不同大小的聚类，对异常数据也很敏感．但是基于密度的聚类方法却能　够帮助发现具有任意形状的聚类，并且仍然需要用户设置可帮助发现有效聚类的参数　Ｊ．　本文提出了一种复合聚类算法，将　均值算法的思想与基于密度的方法相融合，把定义在欧氏空间的　Ｋ均值聚类分析算法，推广到非欧氏空间，因而扩大了应用范围，同时能够获得更精确的聚类效果．将这种　算法用于地理信息系统（ｃＩＳ），利用ＧＩＳ提供的车辆数据进行车辆全球定位线路的自动设计．分析结果表　明，该方法在ＧＩＳ数据挖掘中有良好的效果，因而具有实际的意义．　１　ＣＩＳ的系统组成和功能　ＧＩＳ即地理信息系统，是在计算机硬、软件系统支持下，对现实世　空间分析　界（资源与环境）各类空间数据及描述这些空间数据特性的属性进行　采集、储存、管理、运算、分析、显示和描述的技术系统．地理信息系　坐标数据、属性数据以及以此为基础而演义出来的知识．　图１表示了ＧＩＳ的组成，它由５个主要的元素——硬件、软件、数　据、人员和模型构成．　硬件，主要是指ＧＩＳ所依托的计算机系统，它包含从中央计算机　计　统中的“地理”并非指地理学，而是广义地指地理坐标参照系统中的　机　系　统　算　数　据　库　系　统　地图可视化　图１　ＧＩＳ的组成　服务器到ＰＣ机，从单机到网络环境；ＧＩＳ软件提供所需的存储、分析　和显示地理信息的功能；数据，ＧＩＳ系统中最重要的是数据，ＧＩＳ系统　收稿日期：２０Ｏ７—０６—１２　作者简介：黄学宏（１９４８一），男，广东梅县人，韶关学院信息工程学院副教授。主要从事数据挖掘技术的研究　维普资讯 http://www.cqvip.com

・ｌ８・　韶关学院学报・自然　必须建立在准确使用地理数据基础上，数据来源包括从商业组织购买，以及从其他数据的转换．数据分为空　间数据、属性数据，并与关系数据库相互连接；ＧＩＳ人员，ＧＩＳ应用的关键是掌握实施ＧＩＳ来解决现实问题的　人员的素质，ＧＩＳ的用户包括设计、维护系统的技术专家，以及使用该系统完成工作任务的人员；模型，ＧＩＳ的　专业模型和专家的经验，是ＧＩＳ应用系统成败的至关重要的因素　】．　ＧＩＳ系统的主要功能包括：（１）数据输入、存储、编辑；（２）操作运算；（３）数据查询、检索；（４）应用分析；　（５）数据显示、结果输出；（６）数据更新．　利用ＧＩＳ应能回答和解决以下５类问题：（１）定位（￣＿ａｔｉｏｎ）：对象在何处？（２）条件（Ｃｏｎｄｉｔｉｏｎ）：即满足　一定条件的实体在哪里？（３）趋势（Ｔｒｅｎｄｓ）：从何时起发生了哪些变化？（４）模式（Ｐａｔｔｅｒｎｓ）：即在某个地方　的空间实体的分布模式．模式分析揭示了地理实体之间的空间关系；（５）模型（Ｍｏｄｅｌｉｎｇ）：即某个地方如果具　备某种条件会发生什么，通过基于模型的分析实现．　２复合聚类分析算法　设Ｚ＝　，ｚ　，…，　｝ｃ　Ｒ　为一有限数据集合，／７，是数据集中元素的个数，将该数据集中的数据分为ｋ　类（１＜ｋ＜，１），则ｚ将被划分为　个／７，×ｋ的分类区域Ｕ＝｛ｕ　｝∈　“，ｋ的确定是根据不同对象的需要．　对于每一个小区域　，，按照密度计算法选取凝聚点：　Ｖ　Ｃｌ，　（Ｃ　＜Ｃ２）为球半径，通常Ｃ２＝２Ｃ，，　Ｓ（ｉ，　）＝Ｉ　Ｚ（　）一Ｚ（ｊ）Ｉ，　（１）　式中Ｉｓ（ｉ，．『）为两样本点Ｚ（　），Ｚ（ｊ）之间的距离．　（１）如果．ｓ（　，－『）≤Ｃ　（样本点落入Ｃ，球域），则计算落入Ｃ　球域的样本点，再选择密度最大的样本点　作为第一凝聚点Ｐ，．　（２）对于密度次大的样本点，如果Ｓ（Ｐ，，　）≤Ｃ　（样本点落入Ｃ　球域），则忽略此样本点，如果Ｉｓ（Ｐ　，　）　≥ｃ　（样本点不落入ｃ：球域），则选择此样本点作为第二凝聚点Ｐ　．　这样，按照样品密度由大到小一直选下去，每次和已选的任一凝聚点的距离不小于ｃ　的样品作为新的　凝聚点．　对于以上所求得的凝聚点再求平均密度中心利用重心连接算法公式：　，　・　＾　・　＾　、　（　，　）＝（…ｉ１∑　１∑　），ｉ：１　一ｉ　　（２）　其中　，　是样本点互的横坐标和纵坐标．　车辆自动导航系统是智能运输系统的重要组成部分，自动导航系统的应用将大幅度提高道路的通行能　力，缳解交通拥挤和阻塞．ＧＩＳ在车辆自动导航系统中发挥着重要的作用，ＧＩＳ条件下的电子地图数据库为车　辆自动导航系统提供了存放和管理自动导航信息的一个可视化载体．ＧＩＳ在车辆自动导航系统中的应用研　究将会成为智能运输系统的一个重要的发展方向．车辆自动导航系统中的一个重要部分就是车辆的行驶路　线的设计，下面两幅图是在二维平面上ＧＩＳ中车辆行驶路线设计的结果，图２是采用复合聚类分析方法在　Ｍａｔｌａｂ中实现的结果，图３是采用传统的基于密度的方法所得的聚类结果．比较这两幅图可以看出，复合聚　类分析方法比传统的基于密度的方法设计的行车路线要清晰明朗．　３　ＤＭ和ＧＩＳ在车辆自动导航系统中的应用　针对交通信息、交通系统的不确定性，在传统的基于数据库、知识库和模型库的决策支持系统基础上，　采用数据仓库、联机分析、数据挖掘以及专家系统的有关理论与技术，构建出新一代的智能决策支持系统模　维普资讯 http://www.cqvip.com ９　宏，等：数据挖掘在基于ＧＩＳ自动导航系统中的应用　・ｌ９・　型；应用数据挖掘方法（统计模式识别、神经网络方法、遗传规划和多源复杂信息知识挖掘技术等），研究建　立适合交通信息挖掘的具体模型；在信息分析技术方面，突破传统的基于经典数学的统计分析方法的局限　性，全面引入神经计算、模糊计算、进化计算等智能计算技术，为交通信息的综合管理、智能分析和实时决策　支持提供可行的方案．　经度，。　经度，。　图２　复合聚类方法的聚类结果　圈３　密度聚类方法的聚类结果　本文的实例数据来自于ＧＰＳ，通过ＳＱＬＳＥＲＶＥＲ建立专门的数据库，对数据进行存储、组织和管理．利用　ＳＱＬ　ＳＥＲＶＥＲ建立数据库时，设定相应的规则，保证数据的有效性、安全性和完整性．　该数据库仅含１张表，表中的每条记录有５个字段，分别为Ｎｕｍｂｅｒ（编号）、ｉａ（车辆名称）、ｔａｔ（纬度坐　标）、Ｉ＿ｏｎｇ（￣度坐标）、Ｄａｔｅ（日期）、Ｔｉｍｅ（时间），这样每条记录都完整地记录着某辆车在某一个时刻的确切　位置．所用的地理信息系统的软件为ＭａｐＩｎｆｏ，在ＭａｐＩｎｆｏ中调用ｓＱＬＳＥＲＶＥＲ中的数据，并且利用ＭａｐＩｎｆｏ中　提供的工具去除不必要的数据，对空间数据进行处理后，可以将数据库中包含的所有的车辆的位置，描到电　子地图的相应地点．由于数据量非常庞大，所以需要采用ＤＭ的方法从数据库中提取有价值的信息．下面以　自动导航系统中车辆行驶路线的设计为例来说明ＤＭ如何应用在ＧＩＳ中，主要步骤如下：　（１）获取数据．从卫星上得到所有加入到自动导航系统中的车辆的分布数据．　（２）选取样本数据．例如，选择任意的两个城市，并导出该区域所包含的数据．　（３）聚类分析．用前面所介绍的复合聚类算法进行聚类分析，提取能确定最优路线的数据，最终将所得　数据所确定的路线，在地图中以描点的方式显示出来．　因为从ＧＰＳ得来的自动导航系统的车辆分布数据是随机的，所以通过测试数据量、样本排序将数据进行　预处理，再进行区域分割，经多次试验证明ｋ的选取与ｎ有关，至少保证每个　内样本点数大于ｌＯ．如果样　本点太少，聚类效果不明显；反之，如果样本点数太多的话，设计的路线将会失真．我们取的两个城市之间的　样本点为ｌ　９０８，取ｋ＝１２０，试验证明，此时的聚类效果最好．　４结论　本文提出了复合聚类的方法，这种方法在初始的时候设定多个聚类中心，这样的初始中心在数据的空　间分布上是很广泛的，具有多样性的特点．这种特点使得最初的聚类基本上能保证每个小区域　有一个密　度中心，再根据适当的准则在小区域　找出几个子中心，删除冗余数据；然后计算这个区域　ｆ的平均密度中　心，来修正原来的密度中心．事实证明，这种方法在基于ＧＩＳ的自动导航系统中非常有效．　（下转第６８页）　维普资讯 http://www.cqvip.com

・６８・　韶关学院学报・自然科学　参考文献：　［１］廖常初．ＰＩＥ基础及应用［Ｍ］．北京：机械工业出版社，２００３．　［２］殷洪义．可编程控制器选择设计与维护［Ｍ］．北京：机械工业出版社，２ＯＯ２：２４—４９．　［３］王永华．现代电气控制及ＰＩＥ应用技术［Ｍ］．北京：北京航空航天大学出２００３：８０—９６　Ｒｅａｌｉｚｅｓ　ｗｒａｐｐａｇｅ　ｅｘａｍｉｎａｔｉｏｎ、ｖｉｔｈ　ＰＬＣ　ｏｎ　ｔｈｅ　ＺＢ４５　ｐａｃｋａｇｉｎｇ　ｍａｃｈｉｎｅ　ＵＵ　Ｚｈｅｎ。ｗｅｎ　（ｓｈ删Ｃｉｇａｒｅｔｔｅ　Ｆａｃｔｏｒｙ，Ｃｈｉｎａ　Ｔｏｂａｃｃｏ　Ｇｕａｎｇｄｏｎｇ　Ｉｎｄｕｓｔｒｉａｌ　Ｃｏｒｐｏｒａｔｉｏｎ，Ｓｈａｏｇｕａｎ　５　１２０２６，Ｇｕａｎｇｄｏｎｇ，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｕｓｅｓ　ｔｈｅ　ＰＩＥ　ｐｒｏｇｒａｍｍｉｎｇ　ｃｏｎｔｒｏｌ　ｔｏ　ｒｅａｌｉｚｅ　ｏｎ　ｔｈｅ　ｐａｃｋａｇｉｎｇ　ｍａｃｈｉｎｅ　ｗｒａｐｓ　ｓｅｐａｒａｔｅｌｙ（ｐａｃｋｉｎｇ　ｔｏ　ｈａｖｅ　ｆｌａｗ　ｓｍｏｋｅ　ｐａｃｋａｇｅ）ｔｏ　ｅ】　ｎｅ．Ｔｈｅ　ＺＩＭ５　ｐａｃｋａｇｉｎｇ　ｍａｃｈｉｎｅ　ｗｈｅｎ　ｔｈｅ　ｐｒｏｄｕｃｔｉｏｎ　ｐｒｏｃｅｓｓ，ｗｒａｐｓ　ｅｐａｒｓａｔｅｌｙ　ｈｅ　ｔｅＤｓ．．８ｏｒ　ｅｘ—　ａｍｉｎｅｓ　ｈａｓ　ｗｒａｐｓ　ｅｐａｒｓａｔｅｌｙ　ｔｈｅ　ｓｍｏｋｅ　ｔｈｅ　ｏｕｔｐｕｔ　ｓｉｇｎａｌ，ｗｒａｐｓ　ｓｅｐａｒａｔｅｌｙ　ｈｅ’ｔｓｉｇｎａｌ　ａｎｄ　ｈｅ　ｔｐｏｓｉｔｉｏｎ　ｔｒａｎｓｍｉｔｅｒ　ｃｏｕｎｔｉｎｇ　ｓｉｎ￣ｉｇｎｐｕｔ　ｇｉｖｅｓ　ＰＬＣ，ｔｈｅ　ｓｉｎａｇｌ　ａｆｔｅｒ　ｔｈｅ　ＰＬＣ　ｐｒｏｃｅｓｓｉｇ，ｔｎｈｅ　ＰＬＣ　ｏｕｔｐｕｔ　ｒｅｊｅｃｔｉｏｎ　ｓｉｇｎａｌ　ｆｏｒ　ｔｈｅ　ｐａｃｋａｇｉｎｇ　ｍａｃｈｉｎｅ　ｒｅｊｅｃｔｉｏｎ　ｓｙｓｔｅｍ，ｗｉｌｌ　ｗｒａｐ　ｅｐａｒａｔｓｅｌｙ　ｈｔｅ　ｓｏｋｅ　ｕｓｉｍｇ　ｎｈｅ　ｔｐａｃｋａｇｉｇ　ｎｍａｃｈｉｎｅ　ｅｃｔｉｏｎ　ｓｓｔｙｅｍ　ｔｏ　ｒｅｊｅＣｔ，ｔｈｕｓ　ｒｅａｌｉｚｅｄ　ｈａｓ　ｗｒａｐｐｅｄ　ｅｐａｒｓａｔｅｌｙ　ｔｈｅ　ｇｏａｌ　ｗｈｉｃｈ　ｔｈｅ　ｓｏｋｅ　ｒｍｅｊｅｃｔｅｄ．　Ｋｅｙ　ｗｏｒｄｓ：ＰＬＣ　ｃｏｎｔｒｏｌ；ｗｒａｐｐａｇｅ　ｅｘａｍｉｎａｔｉｏｎ；ｒｅｊｅｃｔｉｏｎ　ｓｙｓｔｅｍ　（责任编辑：颜志森）　ｅ穹　ｅ　奢　、　ｅ　ｓ　ｓ　ｅ　螽　螽　螽　螽　螽　、　（上接第ｌ９页）　参考文献：　［１］Ｂｉｎｇ　Ｈｕ．Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ　ａｎｄ　Ｄａｔａ￣ｉｎｇ［Ｊ］．２１世纪青年科学论坛，２００１，１９（６）：７０—７４．　［２］朱明．数据挖掘［Ｍ］．合肥：中国科学技术大学出版社，２１３０２：２８．　［３］Ｗａｎｇ　Ｘ　Ｚ．Ｄａｔａ　Ｍｉｎｉｎｇ　ｎｄ　ａＫｎｏｗｌｅｄｇｅ　ｉｓＤｃｏｖｅｒｙ　ｆｏｒ　Ｐｒｏｃｅｓｓ　Ｍｏｎｉｔｏｒｉｎｇ　ａｎｄ　Ｃｏｎｔｒｏｌ［Ｍ］．Ｌｏｎｄｏｎ：Ｓｐｒｉｇ—Ｖｅｒｎｂｓ　ｌｉｍｉｔｅｄ，１９９９：１３４—　１３６．　［４］朱勇华，邰淑彩，孙韫玉．应用数理统计［Ｍ］．武汉：武汉水利电力大学出版社，１９９９：３６２—３７６．　［５］龚健雅．当代ＧＩＳ的若干理论与技术［Ｍ］．武汉：武汉测绘科技大学出版社，１９９９．　Ｄａｔａ瑚　ｉｎ　ａｕｔｏ　ｎａｖｉｇａｔｉｏｎ　ｓｙｓｔｅｍ　ｏｎ　ｂａｓｅ　ＧＩＳ　ＨＵＡＮＧ　Ｘｕｅ—ｈｏｎｇ，ＰＥＮＧ　Ｘｉｎ—ｙｔｍ　（Ｉｎｓｔｉｕｔｔｅ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｇ，Ｓｈａｏｇｕａｎｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈａｏｇｕａｎ　５１２００５，Ｇｕａｎｇｄｏｎｇ，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｔｈｅ　ｖｅｈｉｃｌｅ　ａｕｔｏ　ｎａｖｉｇａｔｉｏｎ　ｓｙｓｔｅｍ　ｉｓ　ｏｎｅ　ｏｆ　ｈｅ　ｔｉｍｐｏｒｔａｎｔ　ｐａｒｔｓ　ｆ　ｏｈｅ　ｉｔｎｔｅｌｌｉｇｅｎｔ　ｔｒａｎｓｐｏｒｔａｔｉｏｎ　ｓｓｔｙｅｍ．Ｔｈｅ　ｐａ—　ｐｅｒ　ｇｉｖｅｓ　ａ　ｍｕｌｉｔｐｌｅｘ　ｃｌｕｓｔｅｒｉｇ　ａｎｌｇｏｒｉｔｈｍ　ｏｆ　ｄａｔａ　ｄｉｇｇｉｎｇ，ａｎｄ　ａｎａｌｙｚｅ　ａ　ｎｅｗ　ａｐｐｌｉｃａｔｉｏｎ　ｉｎ　ｔｈｅ　ｄｅｓｉｇｎ　ｏｆ　ｈｅ　ｒｔｏｕｔｅ　ｗｉｔｈ　ｈｅ　ｇｅｏｇｒｔａｐｈｉｃａｌ　ｉｎｆｏｒｍａｔｉｏｎ　ｓｙｓｔｅｍ　Ｅｘｐｅｒｉｍｅｎｔ　ｈａｓ　ｐｒｏｖｅｄ　ｓｕｃｈ　ｃｏｍｐｏｕｎｄ　ｃｌｕｓｔｅｒ’Ｓ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｍｏｌｅ　ｅｆｆｅｃｔｉｖｅ　ｔｈａｎ　ｔｈｅ　ｔｒａｄｉｉｔｏｎａｌ￣，ｏｉｒｔｈｍ．　Ｋｅｙ　ｗｏｒｄｓ：ｄａｔａ￣ｍｎｇ；ｇｅｏｇｒａｐｈｉｃａｌ　ｉｎｆｏｒｍａｔｉｏｎ　ｓｙｓｔｅｍ（ＧＩＳ）；ｍｕｌｉｔｐｌｅｘ　ｃｌｕｓｔｅｒｉｎｇ　ａｌｇｏｒｉｈｔｍ；ａｕｔｏ　ｎａｖｉｇａｔｉｏｎ　ｓｙｓｔｅｍ　（责任编辑：胡伶俐）