一种基于DM的GIS 及其在航海中的应用

数据挖掘（Data Mining简称DM）是20世纪末刚刚兴起的数据智能分析技术，它可以从数据库或数据仓库，以及其他各种大量数据类型中，自动抽取或发现有用的模式知识。DM作为一个新兴的多学科交叉应用领域，正在许多行业的决策支持活动中扮演重要的角色。目前有许多种DM方法，聚类分析把每个分类对象称为样品，并根据对象的性质和分类的目的选定若干指标（变量），对每一个样品测出所有的指标值，将得到的结果列成一个数据矩阵，这个资料阵就是聚类分析的出发点。 k-means算法是划分方法的一种，首先从n个数据对象任意选择k个对象作为初始聚类中心，而对于所剩下的其它对象，则根据他们与这些聚类中心的相似度（距离），分别分配给与其最相似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中心（该聚类中心中所有对象的均值），不断重复这一过程直到标准测度函数开始收敛为止。这种算法使得各聚类本身尽可能紧凑，而各聚类之间尽可能的分开。但它不适合用于发现非凸性状的聚类，或具有各种不同大小的聚类，对异常数据也很敏感。然而，基于密度的聚类方法却能够帮助发现具有任意形状的聚类，但它仍然需要用户负责设置可帮助发现有效聚类的参数。 我们提出了一种复合聚类分析算法，将k-means算法的思想与基于密度的方法相融合，它把定义在欧氏空间的k-均值推广到非欧氏空间，扩大了应用范围，同时能够获得更精确的聚类效果。进一步研究将这种算法用于地理信息系统（GIS）的数据挖掘，利用GIS所提供的船舶数据，进行船舶航线的自动设计，分析结果表明，该方法在GIS数据挖掘中具有实用价值。 1 GIS概述 1.1 GIS定义 地理信息系统(Geographic Information System 简称GIS)是一项以计算机为基础的新兴技术，它可以对在地球上存在的东西和发生的事件进行成图和分析。它能把各种地理位置信息和有关的视图结合起来，利用计算机图形与数据库技术来采集、存储、编辑、显示、转换、分析和输出地理图形及其属性数据。即在计算机软硬件支持下，它可以对空间数据按地理坐标或空间位置进行各种处理、研究各种空间实体及相互关系，通过对多因素的综合分析，它可以迅速地获取满足应用需要的信息，并能以地图、图形或数据的形式表示处理的结果。这种能力使 GIS与其他信息系统相区别，从而使其应用遍及金融、电信、交通、国土资源、电力、水利、农林、环境保护、 地矿等国民经济各领域[4]。我们就是利用一种基于聚类分析的数据挖掘方法，从数据库大量的数据中，提取有效的数据，绘制最优船舶航线。 1.2 GIS系统的构成 GIS 由五个主要的元素所构成：硬件、软件、数据、人员和模型。 （1） 硬件是GIS所操作的计算机。今天，GIS软件可以在很多类型的硬件上运行。从中央计算机服务器到普通PC机，从单机到网络环境。 （2） GIS软件提供所需的存储、分析和显示地理信息的功能。其要素有： l 地理信息输入和处理的工具； l 数据库管理系统(DBMS) ； l 空间查询、分析、可视化表达工具； l 图形用户界面(GUI) 。 （3） 数据。一个GIS系统中最重要的部件就是数据了，GIS系统必须建立在准确使用地理数据基础上，数据来源包括从商业组织购买，以及从其他数据的转换。数据类型分为空间数据、属性数据，并与关系数据库互相连接。 （4）GIS人员。GIS应用的关键是掌握实施GIS来解决现实问题的人员的素质。GIS的用户范围包括从设计和维护系统的技术专家，到那些使用该系统并完成他们每天工作的人员。 （5）模型。GIS专业模型和经验，是GIS应用系统成败的至关重要的因素[5]。 1.3 GIS的功能 一个GIS系统的主要功能包括：①数据输入、存储、编辑；②操作运算；③数据查询、检索；④应用分析；⑤数据显示、结果输出；⑥数据更新。 利用GIS应能回答和解决以下五类问题： l 定位(Location)： 对象在何处? l 条件(Condition)，即满足一定条件的实体在哪里。 l 趋势(Trends)： 从何时起发生了哪些变化？ l 模式(Patterns)，即在某个地方的空间实体的分布模式。模式分析揭示了地理实体之间的空间关系。 l 模拟(Modeling)，即某个地方如果具备某种条件会发生什么。通过基于模型的分析实现。 2 复合聚类分析算法 设 为一有限数据集合，n是数据集中元素的个数，将该数据集中的数据分为k类（1 （C1 < C2） 为球半径， 通常（C2＝2C1）， 式中： S（i ，j）为两样本点Z（i），Z（j）之间的距离， If S（i，j）≤ C1 （样本点落入C1球域）， Then 计算落入C1球域的样本点， And then 选择密度最大的样本点作为第一凝聚点P1； 对于密度次大的样本点 If S(P1,j)≤C2（样本点落入C2球域） Then 忽略此样本点， If S(P1,j)≥C2（样本点不落入C2球域） Then 选择此样本点作为第二凝聚点P2； 这样，按照样品密度由大到小一直选下去，每次和已选的任一凝聚点的距离不小于C2的样品作为新的凝聚点。 对于以上所求得的凝聚点再求平均密度中心，公式如下： 其中xi，yi是样本点Zi的横坐标和纵坐标。 　　图２为复合聚类分析算法的计算机流程。 以下给出了两维平面上GIS中船舶航线设计的结果，与传统的基于密度的方法相比较。图2为本文所采用聚类分析方法在MATLAB上的聚类结果；图3为采用传统的基于密度的方法在MATLAB上的聚类结果。由图2图3的比较可以看出，本文所采用聚类分析方法的聚类效果要比传统的基于密度的方法的优越，航线设计明显。 3 DM在GIS中的应用 本文所用示例数据来自于GPS,通过ACCESS建立专门的数据库（如图4所示），对数据进行存储，组织和管理。利用ACCESS建立数据库时，设定相应的规则，保证数据的有效性。 该数据库仅包含一张表，表中的每条记录，包括五个字段，分别为Number， Id， Lat， Long， Date， Time，这样一条记录就完整的记录了某条船在某一时刻的确切位置。所用地理信息系统软件为ESRI的ArcView 3.2[6]，在ArcView 3.2中调用ACCESS中的数据，并利用ArcView 3.2提供的工具去除不必要的数据，对空间数据进行处理后，可以将数据库中包含的所有的船的位置，描到世界地图的相应地点。由于数据量庞大，故需要采用DM方法从数据库中提取有价值的信息。本文以船舶航线设计为例说明DM在GIS中的应用，图5为采用DM进行船舶航线设计的过程。 如图5 所示，先从卫星上得到全球船舶分布数据，然后选取样本数据，例如：选择从布宜诺斯艾利斯和好望角之间的海域（如图6所示），并导出该区域所包含的数据，再用本文所介绍的方法进行聚类分析，提取能确定最优航线的数据，最终将所得数据所确定的航线，在地图中以描点的方式显示出来（如图7所示）。 图6 布宜诺斯艾利斯与好望角之间的船舶分布 图7布宜诺斯艾利斯与好望角之间的航线设计 图8为本文所采用的聚类分析的GIS船舶航线的设计的流程图。 图8 基于复合聚类分析算法流程图 因为从GPS得来的全球船舶分布数据是杂乱无章的、随机的，所以通过测试数据量、样本排序将数据进行预处理，再进行区域分割，经多次试验证明k的选取与n有关，至少保证每个mij内样本点数大于10，因为样本点太少，聚类效果不明显；当然太多的话，设计的航线就会失真。本文从布宜诺斯艾利斯和好望角之间的海域取的样本点有1844个，取k＝100，试验证明，此时的聚类效果最好。 4 结论 本文中提出的聚类分析方法在初始化时设定多个聚类中心，这样的初始中心在数据空间分布范围广泛，具有多样性。使得最初的聚类基本上能保证每个小区域mij有一个密度中心，然后再根据适当的准则在小区域mij找出几个子中心，删除冗余数据，再计算这个区域mij的平均密度中心，来修正原来的密度中心。经试验可以看出，这种方法用于GIS中船舶航线的设计是非常有效的。进一步可将该方法与电子海图系统相结合，开发基于智能的船舶航线自动设计系统。 参考文献 ［1］朱明. 数据挖掘［M