基于相邻关系的gml空间离群数据挖掘算法分析

《基于相邻关系的gml空间离群数据挖掘算法分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第1章绪论（2）无需购置专用的客户端软件就能在浏览器进行显示当客户端接受到GML文档时，它就被换成一系列的绘图对象并在浏览器中渲染成为一幅地图。SVG可用作绘图对象语言。这样，只要浏览器支持矢量图形，地图就不需要任何软件就能显示出来。目前由Adobe公司多开发的免费软件插件SVGView2.0/3.0可很好的支持SVG。这样，显示SVG文件就无需专门其他的软件。（3）定制地图样式GML仅包含地图的“内容”(如地物的位置、几何形状、类型和属性等)，但它并不提供地图如何显示的信息。这时，样式表就可用于将地理数据按照用户的意愿进行显示。

2、例如：一个用户选择细黑虚线表示道路，十字符号表示教堂；而另一个用户也许选择粗实红线表示道路、叉号表示教堂。对于这两个用户来说使用的是同一套GML数据，只是各自选用了不同的样式表来渲染地图而已。（4）可编辑的地图当基于GML的地图被下载并且显示在浏览器中后，对其进行注释就很容易。一旦GML被转换成SVG，用户就可以用客户端的图形编辑工具在地图上增加文本，加亮地物，或者绘制任何形状的图形。当然对注释过的地图也可以保存为本地文件或进行打印。（5）更高级的链接能力使用GML的另一个好处是用户可以嵌入与地物有关的链接。这些链接可以使简单的U

3、RL地址，也可以是更复杂的链接。这是意味着用户可以将任何网址与地物进行链接。当用户点击一个地物时，就可以转移到所相联的网址。GML的这种特性被用来发出一个基于特征的查询或者将用户引入一个新的网页（如点击地图中的剧院就可将用户带入该剧院的主页）。（6）更强的查询能力用户在浏览地图时经常想做的就是当取图上的一个地物就可以获取该地物的更多信息。随着Internet的应用，空间信息将会大量地以GML格式存在，GML数据越来越多，面向GML的数据挖掘具有重要的理论意义和广泛的应用价值，并受到研究人员的重视。然而，目前面向GML的数据挖掘研究

4、处于起步阶段，研究成果较少。本文将在国家自然科学基金项目（40771163，40871176）的资助下进行GML的离群数据挖掘研究，主要研究面向GML的结构离群挖掘算法和基于空间相邻关系的GML离群数据挖掘算法。1.2研究现状近年来国内外研究者提出了大量的离群数据检测算法，大致归纳以下几类：基于统计的方法、基于距离的方法、基于偏移的方法、基于聚类的方法、基于密度的方法。下面将对这些经典的离群点检测算法做个介绍。（1）基于统计的离群点检测算法2第1章绪论基于统计方法是最早的离群点检测方法。对给定的数据集合假设一个分布或概率模型，然后

5、根据模型采用不一致性检验来确立离群点。基于统计的离群点挖掘方法易于理解，实现起来也比较方便，但主要的缺点是绝大多数检测算法仅对数据分布满足某种概率分布的数值型单维数据集比较有效。然而许多数据挖掘问题要求在多维空间中发现离群点。同时，统计学的方法要求关于数据集合参数的知识，但是，这些参数有可能是未知的。当没有特定的检验时，该类方法不能确保所有的离群点被发现。（2）基于距离的离群点检测算法[4]基于距离方法最早是由Knorr和Ng在1998年提出的。他们用DB(p，d)来表示数据集中的离群点，采用不同的参数p与d，DB(p，d)可以表

6、示所有的离群点。[5]与此定义相应的算法有三种，它们是基于索引(index-based)的算法，嵌套循环[6，7][8](nested-loop)算法，基于单元或划分(cell–based)的算法等。它们的具体算法不在赘述。基于索引的方法依赖多维索引结构(R–trees，X–trees，KD-tress等)的性能。但是随着维数的增加，所有的索引结构的性能迅速下降，使得算法性能不佳。NL算法可以避免构建索引结构，减少了算法的I/O次数。以上两方法的算法时间复2杂度为O(kn)，当遇到大量数据集时它们还有待改进。基于单元的方法是把数据

7、集划分为单元，逐个单元的检测，而非逐个对象的检测。它的时间复杂度为O(ck+n)，其中ck取决于单元的个数n和维数k。Knorr和Ng通过试验证明，当k<=4时，此算法优于NL算法。相对于基于索引的算法和嵌套循环的算法，基于基于单元的算法无论是在数据量还是在维数增加时，性能都是最好的。此方法需要将数据空间分隔成彼此独立的单元结构，经过多次选择来判断离群数据。对于参数的每个变化都需要调整单元结构，因此会影响了算法的结果。[9]后来，Rastogi和Ramaswamy提出了一个新的基于距离的离群点定义，即基于距离的第k最近邻(k-th

8、NearestNeighbor)离群点挖掘方法。给定δ维空间中包含N个点的数据集D、参数n和k(自然数)，Dk(p)表示点p和它的第k最近邻的距离。如果满足Dk(q)>Dk(p)的点q不超过n-1个，即

9、{q∈D

10、Dk(q)>Dk(p)}

11、≤n-1