摘  要: 网络技术的飞速发展使得SVG成为矢量图形发布的新标准,SVG文档中隐藏着大量有趣的空间信息。本文综合利用空间信息和非空间信息，采用多维多层交叉关联规则挖掘技术，从SVG文档中挖掘隐藏的空间关联规则。
   关键词: SVG文档；矢量图形；空间数据挖掘；空间关联规则挖掘

Abstract: With the population and application of the computer network, SVG has been the new publishing standard for vector graphic. There are large interest spatial information hidden in SVG document. In this paper, We apply cross multilevel association rule discovery technique  to  find spatial association rules from a combination of spatial and non-spatial  information of SVG document.
Keywords: SVG document; Vector graphic; Spatial data mining; Spatial association rule data mining
1   引  言
1.1    SVG文档
   Internet的迅速发展，图形图像信息也需要通过网络实现共享。目前浏览器显示的大都是栅格形式的图像，栅格文件具有很多限制性，这些问题矢量图形可以很好的解决。W3C推出的SVG（Scalable Vector Graphics，可伸缩矢量图形），是一种基于XML的图形标准，因它具有纯文本、开放、动态、可缩放和平台无关等特性，成为进行空间矢量数据发布的生力军。
   SVG基于XML来描述2维矢量图形，对于基本图形元素和非几何特征都可以很好的表达。每一个SVG文档含有一个根元素需表达的整个内容处于根元素之间，空间对象以图层组织。图层Layer可采用表示，属于同一图层的几何元素可以是任何基本几何元素及其组合，包含于同一组之间。点集、线集、面集、复杂几何体类等也可采用表示， 元素的ID用于标识不同类型。基本的图形元素：点Point、线LineString、面Polygon，可采用、或等表达。
   几何图形的非几何特征表达在SVG中一般采用两种方式：内嵌法和外联法。内嵌法一般是作为元素（如circle、path等元素）的属性进行表达[1]。外联法是指非几何特征数据存储在服务器的数据库中，并且通过ID与SVG文档中的相关地物进行连接。
   SVG文档的结构可以认为是树状结构，图1是简单的SVG文档，文档包含了两个图层，分别是行政区域图层和水库分布图层。
1.2   空间拓扑关系
   几何对象间的空间关系通常为三类：空间拓扑

    关系、度量空间关系和顺序空间关系。空间拓扑关系对于空间数据挖掘非常重要。通过空间关系进行归纳和分类，得出了5种基本空间拓扑关系[2]：相离关系（Disjoint）、相接关系（Touch）、相交关系（Cross）、包含于关系（Within）、部分覆盖关系（Overlap）。这些空间拓扑关系之间具有层次性，图2是空间拓扑关系层次图。图中非相离关系是相离关系的补集。相邻关系是相离关系的子集，如果两个空间对象相离，并且两者距离小于给定值，那么它们间的拓扑关系是相邻。因为在实际应用中，只有两个相离几何对象间距离在一定范围内，才具有实际讨论意义。

小支持度阈值和最小置信度阈值的规则成为强规则。
   一直以来关联规则挖掘都是数据挖掘研究热点，它与空间领域结合产生了空间关联规则挖掘。目前空间关联规则挖掘研究主要是针对栅格图像[3,4,5]，在矢量数据上进行挖掘也有一定的研究 [6]。但基于结构化的SVG文档进行空间关联规则挖掘还很少研究，本文探讨如何基于SVG文档进行空间关联规则挖掘。
2  空间关联规则挖掘
2.1   据预处理
   SVG是结构化文档，元素中存在层次性。空间对象间的拓扑关系具有层次性。非空间属性也可以定义其概念层次结构，因而适合在SVG文档上进行多维多层关联规则挖掘。但是SVG文档并不是为了空间挖掘而建立的，不能直接用于多维多层关联规则挖掘，需要将其转换成适合挖掘的形式。数据预处理中的基本思路是从SVG文档中选取挖掘任务所需几何对象，根据其空间、非空间信息，构造事务数据库。
   拓扑关系是挖掘所需主要空间信息，但SVG文档中通常没有显示地记录几何对象间的拓扑关系，需要调用相应的空间分析算子进行空间分析，构造空间拓扑关系表[7]，如表1所示。构造规则：Itdbmax＝{(01,02,T)|01,02∈SDoc,01distance=dist02∧dist≦max∧01T02}。SDoc是SVG文档，max、distance均为数值数据，T为拓扑关系。

   许多挖掘任务，不仅仅在空间信息上挖掘，还需要与非空间信息相结合。根据不同挖掘任务，从SVG文档中提取空间对象的非空间特征，在空间拓扑关系表中提取对象间的拓扑关系，构造关系表，如表2所示。

   进行多维多层数据挖掘前，数据还需要先转换成单维单层结构。根据SVG文档结构、拓扑层次结构、非空间特征概念层次结构对关系表中所有项编码。每个项所对应编码第1位用于区分项的类型。取值1表示是空间对象，2表示是拓扑关系，3表示是非空间属性。编码其他位取值由其所对应层次结构决定。空间对象的编码可借助DOM（Document Object Model）操作，采用深度遍历来实现。算法如下：
输入：SVG文档，路径P为空字符串
输出：空间对象编码
步骤：
1.调用GetSVGDocument（）函数，得到SVG DOM文档对象。
2.调用GetElementByid()函数，得到结点L。判断结点L：
(1)如果 L是叶节点，访问标志改为True，输出，返回父节点。
(2)如果结点L是非叶节点：
A．如果L的访问标志为False，输出，记录访问标志改为Ture，字符1作为尾字符加入路径P，访问L的第一个子结点；
B．如果L的访问标志为True，L有未访问子结点，路径P的最后字符值加1，访问L的下一个子结点；
C．如果L的访问标志为True，L所有子结点已被访问，去掉P的最后一个字符，更改后的P的最后一个字符值加1，返回父结点。
3．依次循环，直到SVG文档所有对象被访问。
拓扑关系和非空间属性编码相对简单，根据预先定义的层次结构就可以得到相应编码（如图3、4所示）。图3是拓扑关系编码图，拓扑关系所对应的编码是从根结点到本结点路径上所有编码的组合，例如相接关系的编码为”211”，相邻关系编码为”22”。图4是非空间属性人口、收入概念层次结构编码图。表3是表2运用上述编码规则后形成的编码表。

2.2   空间关联规则生成
算法如下所示：
输入：编码表Ctab、最大层次数Max_l、各层最小支持度Minsup[Max_l]、最小置信度Mincon[Max_l]。
输出：强关联规则。
步骤：
1.扫描编码表Ctab，计算1层频繁1项目集到Max_l层频繁1项目集。
2.循环调用如下过程产生L层频繁2项目集到L层频繁k项目集：
(1)由频繁L层（k-1）项目集产生L层候选k项目集。
(2)循环计算L层候选k项目集中各项目的支持度，得到L层频繁k项目集。
3.根据最小置信度，得到对应的强关联规则，检查冗余，剔除冗余规则。
算法具体分析如下：
   步骤1：频繁1项集生成中不同层赋予不同的最小支持度，较低层使用递减的最小支持度，避免丢掉出现在较低抽象层中有意义的关联规则。
步骤2： L层k项目候选集Ck生成,需要L层（k-1）项目集进行自身连接生成L层K项目候选集，还要使用1层1项目集、2层1项目集…、L-1层1项目集与L层（k-1）项目集连接生成L层K项目候选集。
步骤3：各层规定不同的最小置信度，由各层得到的频繁项生成强关联规则。由于项之间的“祖先”关系，如果规则的祖先，它的支持度和置信度都接近于“期望”值，那这个规则是冗余的。应该剔除[8]。
3  应用分析
3.1  区域环境分析
   当前社会经济、人口迅速发展，生态环境越来越受到关注。图5是某区域的SVG矢量图，图中包括行政区域、长年河、水库、林地、草地等图层。通过挖掘空间关联规则，可帮助分析此区域的环境特征。例如：分析此区域城市与水域、植被等分布的关系，可运用上述空间挖掘思路进行空间挖掘。由于此挖掘任务未涉及非空间属性，只需选取此区域中几何对象城市、水域、森林、草地以及其拓扑

关系。城市、水域、植被等图层处于SVG文档层次关系第二层，拓扑层次关系总共分为三层。这里列出由第二、三层挖掘后的部分频繁模式。第二层最小支持度56％，置信度第三层最小支持度40％：
is_a(A, town),is_a(B,river), not_disjoint(A,B),
is_a(C,forest), not_disjoint(A,C),is_a(D,grass)，ot_disjoint(A,D),close_to(A,E),cross(A,B),within(A,C),within (A,D)
根据置信度，可以得到强关联规则。如
is_a(A, town)is_a(B,river) cross(A,B)等。
   以上信息表明在此区域城市大都有分布有水源、各种植被。但是还不能提供进一步详细信息，如城市水源是否充足，植被覆盖是否茂盛等。因而在之前空间信息基础上，加入非空间属性：城市面积、人均水量、人均草地面积、人均森林面积等，并且建立非空间属性层次图进一步进行挖掘，得到一组强关联规则。如规则：is_a(A, town)is_a(C,grass) cross(A,C) ave_river(Low),表明大多数城市都覆盖有草地，人均草地占有量低。
3.2 区域环境分析
   目前各个地区都处于发展当中，影响区域发展的因素很多，这些因素与发展的相关性通常都是隐性的，需要通过相关数据进行分析。如图6是某区域的SVG矢量图，图中有城市边界、公路两个图层，以及土地利用等属性数据。

   在图6数据基础上分析城市的公路分布与土地各项利用变化之间的关系，进行空间挖掘。预处理中利用文中所述方法得到地区城市与道路拓扑关系编码表，此表中包含非空间属性，分别是公路分布密度、耕地、城乡工矿居民用地和未利用地的使用变化，其中公路分布密度利用地区城市与道路拓扑关系可求得。图7可视化的显示了各区域的公路分布和土地利用变化，各个区域根据公路分布密度的不同赋予了不同颜色，颜色的设置规则如图8，其中n表示公路密度。对于土地利用的变化采用柱状图表示，柱状图中长方形颜色不同表示的变化也不同，具体见图9。

   最后设置最小支持度、置信度进行空间关联规则的生成，得到一组强关联规则，这些规则所显示的信息可作为区域的发展策略的参考依据，帮助区域达到更好的和谐发展。

4  总   结

   本文探讨了如何在SVG文档上挖掘空间关联规则。为了得到有趣信息，综合利用空间信息和非空间信息，基于挖掘任务进行多维多层交叉挖掘，并且应用于实际分析，扩展了SVG的研究与应用。
   但是由于基于SVG文档的挖掘还处于起步阶段，所做工作存在很多不足，如关联规则挖掘中没有考虑增量挖掘的情况；对于各层最小支持度和置信度依赖于经验进行手工设置；冗余规则的检测原则过于简单，没有考虑实际应用情况。这些问题都有待于进一步解决。

参 考 文 献

[1] 徐云和等．基于SVG的空间数据的可视化[J] ．计算机应用研究，2005，2：46-48．
[2] 邬伦等．地理信息系统-原理、方法和应用[M] ．北京：科学出版社，2001：65-66．
[3] Thanapat Kangkachit, Kitsana Waiyamai. A business-oriented spatial association rule mining system prototype(Bosarm)[J]. Information and Computer Engineering Postgraduate Workshop , 2002.
[4] Donato Maleba, Francesca A.lisi. An ILP method for spatial association rule mining[J].Working notes of the First Workshop on Multi-Relational Data Mining, 2001:18-29
[5] W.Sabhananda, K.Waiyamai. Data Mining: A Novel Approach for Multi-level association Rules Mining in Large Databases[J]. The Fifth National Computer Science and Engineering Conference, 2001.
[6] 厍向阳，许五弟，薛惠锋．矢量空间数据库中关联规则的挖掘算法研究[J] ．计算机应用，2004，24(8):47-49
[7] Ester M., Kriegel H.-P., and Sander J.Spatial Data Mining: A Database Approach[A].in: Proc.5th Int. Symp.on Large Spatial Databases[C], Berlin Germany, 1997:47-66.
[8] Jiawei Han, Micheline Kamber. 数据挖掘－概念与技术[M]. 北京：高等教育出版社， 2005:236-237.