电子技术与软件工程
Electronic Technology&Software Engineering
数据库技术
Database Technology SVG中数据挖掘与应用
陈少英
(厦门海洋职业技术学院福建省厦门市361012)
摘要：本文针对基于SVG的图形系统的特点，在SVG图形库非常庞大的情况下，采用K-means和Canopy算法进行聚类数据挖掘，提高服务器端对数据的特征提取挖掘、检索解析速度.
关键词：SVG；数据挖掘；K-means算法；Canopy聚类算法
SVG是由W3C组织发布的一种基于XML的二维矢量图形和矢量点阵混合图形的可扩展标记语言。其具有下载浏览速度快、动
svg交互图文入门
态、开放、便捷的图形定位与检索、良好的可交互性等优点，使其能更适用于不同系统间的图形系统交换。
在SVG的图形系统数据服务端，图元动态数据的描述信息准确与否，会影响服务端的解析效率。在SVG图形库庞大的情况下，
提高服务器端对动态数据的特征提取及数据挖掘、对动态数据描述
信息的解析就尤为重要。
1数据解析
SVG图形系统使用请求路由器MapDispatichServlet来解析输入请求，并将请求分发到相对应的对象进行处理。MapDispatichServlet分别实现doGet()方法和doPost()方法。doGet 方法解析用户的请求，从输入中得到要取得地图的名称，从缓冲器中取得地图的SVG文件，输出XML格式的SVG文件。同样地，doPost方法解析用户的请求，按照地图名称取得SVG地图，并根据请求格式的不同区分为SOAP请求和普通的表单POST请求，最后组成XML文件输出。
SXW格式解析器负责处理由SuperMap Deskpro地图编辑软件产生的空间SXW文件的解析，未来要考虑处理Maplnfb.ArcMap 等生成的工作空间文件。它提供外部所需的图层元素值，其中包括一个外部接口类(主类/驱动类)：MapConfig；两个内部调用类：LayerBuffer,Parser；一个数据LayerBean，如图1所示。外部程序只能调用MapConfig类，提供了两个入口，getValue方法它返回的图层元素值为一个数据L
aerBean，外部程序需要实例化该数据LayerBeano doParser提供SXW文档解析，外部程序首先应当调用该方法，驱动子系统解析SXW文件，并返回true。
其中，图形配置模块MapConfig中的getValue用于获取Layer 数据Bean,doParser用于设置文件路径，检查文件是否存在，并调用缓存处理模块LayerBufTer驱动XML文件的解析。缓存处理模块LayerBuffer中的getLayerValue用于对解析出来的数据Bean存储到HashMapo XML文件解析模块Parser中的getDocument用于生成XML文档解析器，生成Document对象，elementParse用于解析XML文档元素生成Bean,dec2Hex用于将十进制转换成十六进制。
public XMLDataSourceParser(InputStream xmlURLInputStream,X MLParseTemplate parseTemp)
{
sax R eader=new SAXReader();
this.parseTemp=parseTemp;
MapConfig
LayerBean LayerBean
■fileCheck CheckFile
^cache LayerBuffer
*MapConfig()
*getValue()
•doParse"
LayerBuffer
^HnapValues HashMap
紋a yerBuffe")
•getLayerVlaue()
LayerBean
wFontName
wFon(Height
^FontWidth
wFil For e Color
wFilBackColor
pKineColor
dkineWidth
wVisibteScaleMin
|爲Vi a bleScaleM ax
图1:SXW类图框架
public boolean doParse()
{
boolean parsedOK=false;
try{
xmlDoc=sax R eader.r ead(x m IURLInputStream);
XMLWriter writer=new XMLWriter(System.out);
writer.w rite(xmlDoc);
Element RootElement();
parseTemp.parse(rootEle);
parsedOK=true;
}
catch(DocumentException doce)
{
doce.printStackTrace();
}
图形数据解析完毕，接着需要装载SVG地图。通过loadSVGMap函数先读出地图的基本信息跟SVG内容，并按照每条基本信息构造SVG的名称，并将其作为索引写入svgMap哈希表内，也将相对应内容写入svgMap的内容中。接着doParser调用缓存处理模块驱动XML文件的解析，数据缓存器自行维护一块缓存数据，采用名称一内容方式存储数据。数据缓存器在服务器启动时自动建立唯一实例，并从Oracle数据库中的缓存数据存储表中读入所有数据。调用方传入数据名称，缓存器负责从缓存区中读取相对应的数据，并以byte数组方式返回请求的内容。如果请求的数据不在缓存区中，调用方可以从数据库中读取相应内容，并将读出
•2018年度福建省中青年教师教育科研项目成果(编号：JZ180509)。
131
数据库技术Database Technology
电子技术与软件工程
Electronic Technology&Software Engineering outside TI boundary,not a
member of this duster
图2:canopy算法概念图
图3:canopy算法流程图
的内容写入到缓存器中，以便下次调用的时候可以提高性能。数据缓存器不负责读取请求的解析，不负责访问数据库，仅仅用于查、匹配、读取、写入数据。
调用Parser.elementParse解析XML文档元素生成Bean。使用compose函数进行组装，从结果集中取出所有的SXW文件名、province>city、Datalink值，建立mapConfig，使用doParser()方法传入SXW文件名，设置Layerinfo，按照对应的Datalink取得Wing Layerlnfo表中Layerinfo的其他值，设置对应的Layerinfo类中的各个值，按照查询出的列数和行数进行双循环，查询出Wing_ Blockinfo中对应的各个块的内容，构造Blockinfo，并将其传入svgFactory,svgFactory返回SVG内容，完成组装。
2K-means算法数据挖掘
在SXW文件解析过程中，要对所有的SVG图形图像元素及属性进行特征提取和数据挖掘，以提高整个系统查询的效率和准确度。可以采用K-means算法来进行基于划分的聚类方法的数据挖掘。
其算法过程如下：
(1)从N个SXW解析文件随机选取K个SXW解析文作为质心。
(2)对剩余的每个文件测量其到每个质心的距离，并把它归到最近的质心的类。
(3)重新计算已经得到的各个类的质心。
(4)循环重复2〜3步直至新的质心与原来质心相等或小于指定阈值，算法结束。
具体实现如下：
(1)输入k,data[n]；选择k个初始中心点，例如c[0]=data[0],•••c[k-1]=data[k-1]；
(2)对于data[O]-*-.data[n]，分别与c[0]…c[k-l]比较，假定与c[i]差值最少，就标记为i；
(3)对于所有标记为i点，重新计算c[i]=；
(4)重复2、3步，直到所有c[i]值的变化小于给定阈值。
当目标函数达到最优或者达到最大的迭代次数就终止算法。针对不一样的距离度量，目标函数是会有差别的。当采用欧几里得方法计算距离度量时，目标函数-般通常采用最小化对象到其簇质心的距离的平方和，如下：
/=1xg C,
当采用余弦相似度时，目标函数一般为最大化对象到其簇质心的余弦相似度和，如下:
max工工cos恥(q,x)
K-menas®法试图到使平均误差准则函数最小的簇。若潜在的簇是凸形状的，那么簇间的区别就会比较明显，而且若簇大小相近时，那么使用K-menas算法的聚类结果比较理想。K-menas算法的优点在于算法时间复杂度0(tKmn)和样本数量线性是相关的，因此，当在处理大数据集时，该算法高效、伸缩性较好。但其不足在于该算法要事先确定簇数K，同时对初始聚类中心、“噪声”、孤立点敏感，因此，该方法不适合非凸面形状的簇或大小差别很大的簇。
3使用Canopy聚类算法改进数据挖掘
当数据的条目很多、数据向量其维度很大、包含多个属性，或者在进行数据挖掘时无法事先就判定应该聚成多少类，无法进行K 值的设定时，就要采取另外的途径，改进聚类算法，釆用Canopy 算法。
3.1Canopy算法的主要思想
Canopy算法把数据挖掘分为两个阶段，具体来说，阶段一，使用一个简单粗糙的距离计算方法来产生具
有一定数量的可重叠的子集，设定一个距离阈值，当计算的距离小于这个阈值的时候，就把数据向量归到此子集，也就是canopyo每个数据向量有可能存在于多个canopy里面，每个数据向量至少要包含于一个canopy中。同一个canopy中的样本数据向量彼此间还是存在相似性，有可能被分为同一个类。由于距离计算方式是粗糙的，因此不能够保证性能(计算精确度)。但是通过允许存在可叠加的canopy和设定一个较大的距离阈值，在某些情况下可以保证该算法的性能。
3.2创建Canopy算法
创建一个普通的canopy算法的概念图与简单步骤，如图2所示。
(1)从SVG元素工厂生成相应数据库表的SVG元素，获取对应的SVG元素数组。原始数据集合列表按照一定的规则进行排
132
电子技术与软件工程
Electronic Technology&Software Engineering
数据库技术Database Technology
序，初始距离阈值为Tl、T2，且Tl>T2o TK T2的设定可以根据用户的需要，或者使用交叉验证获得。
(2)在数据集合列表中随机挑选一个数据向量A，运用粗糙距离计算方式计算A与列表中其他数据向量之间的距离do
(3)根据第2步中的距离d，把d小于T1的样本数据向量划到一个canopy子集中，同时把d小于T2的样本数据向量从候选中心向量名单，也就是数据集合列表中移除。
(4)重复第2、3步，直到数据集合列表为空，算法结束。
创建canopy算法的流程图如图3所示。
阶段二，可以在阶段一的基础上应用传统聚类数据挖掘算法，比如贪婪凝聚聚类算法、K均值聚类算法，
当然，这些算法使用的距离计算方式是精准的距离计算方式。但是因为只计算了同一个canopy中的数据向量之间的距离，而没有计算不在同一个canopy 的数据向量之间的距离，所以假定它们之间的距离为无穷大。例如，若所有的数据都简单归入同一个canopy，那么阶段二的聚类挖掘就会退化成传统的具有高计算量的聚类算法了。但是，如果canopy 不是那么大，且它们之间的重叠不是很多，那么代价很大的距离计算就会减少，同时用于分类的大量计算也可以省去。进一步来说，如果把Canopy算法加入到传统的聚类挖掘算法中，那么算法既可以保证性能，即精确度，又可以增加计算效率，即减少计算时间。
Canopy算法的优势在于先进行数据预处理，在数据预处理中，使用粗糙距离计算方法将数据分到几个可重叠的子集中，再而只需计算在同一个重叠子集中的数据向量，以此来减少数据计算量。
3.3Canopy算法实施
使用Canopy算法对SVG向量数据进行聚类分析，涉及到以下几个过程：
(1)将SXW序列文件进行向量化转换。使用sequence2TFVectors方法将信息转换为<；词ID，词频〉的向量形式，每一个词ID就代表了一个变量的坐标，而这个词ID对应的词频即为该变量值，每一个词组成的位置信息则转换为了一个稀疏变量，SXW序列文件便转换为了稀疏矩阵。
WhitespaceAnalyzer.class,tokenizedPath,conf)；
Dictionary ateTermFrequencyVectors(tokenizedPath, new Path(outputDir),
Dictionary V ectorizer.DOCUMENT_VECTOR_OUTPUT_ FOLDER,conf,
minSupport,maxNGramSize,minLLRValue,-l.Of,false,
reduceTasks,chunkSize,sequentialAccessOutput,true);
}
Input用于输入的序列文件路径，analyzerClass是使用的Lucene解析器，Output指具体的输出目录。
(2)运行canopy算法初始化聚类重心。使用canopy算法API 对向量化后的文件初始化聚类中心。这里CanopyDriver方法需要设置的三个重要参数为距离选择，以及阈值Tl,T2的取值。这里选择的是适合文本分析的余弦距离公式，比如T1为0.6,T2为0.4。
CanopyDriver.run(conf,vectorsFolder,canopyCentroids,
new CosineDistanceMeasure(),0.6,0.4,false,0.0,false);
(3)运行kmeans算法对SVG信息进行聚类。在运行完了canopy方法后，便要进行kmeans算法，利用canopy生成的结果作为初始聚类中心，由于此时聚类中心数已经确定，则不需要设置k 值，最终的聚类数会根据收敛阈值变化而变化。
KMeansDriver.run(conf,vectorsFolder,new Path(canopyCentroids, Constants.CLUSTERS O FINAL),clusterOutput,0.3,100,true, 0.0,false);
}
其中涉及到重要的参数设置，收敛阈值为0.3，迭代次数为100o
(4)调用ClusterDumper类将最终的聚类结果转换为可以读懂的信息，由于聚类结果是序列文件，而且是以词ID的形式出现的，因此需要将在文本向量化过程中生成的dictionary文件关联至该方法。
ClusterDumper clusterDumper=new ClusterDumper();
String[]args={"-input",
Constants.KME AN S_OUTPUTD I R+'V'+Constants. CLUSTERS+”/”+Const
ants.CLUSTERS_3_FINAL,"—output",dumppath,
”-d”，Constants.KMEANS_OUTPUTDIR+'7M+Constants. DICTIONARY,n-p",
Constants.KMEANS_OUTPUTDIR+”/”+Constants. CLUSTERS+”/”+Constants.CLU
STEREDPOINTS/'-dt",Constants.SEQUENCEFILE,H-n", Constants.DUMPNUM};
int result=clusterDumper.run(args);
(5)利用dump接口对聚类结果进行解析。执行完第3个过程后，生成了一个序列文件保存结果，这个序列文件的key为进行比较的两组向量的ID信息，value为这两组向量的距离。我们只需要通过SequenceFile.Reader将距离信息读出，然后进行排序，即能得到最终结果。
4结论
基于SVG的图形系统结合了基于图像内容和基于图像特征的挖掘检索与应用，在SVG图形库非常庞大的情况下，从SVG图形基本信息的XML文件中采用K-means和Canopy算法进行聚类数据挖掘，包括文本向量处理部分的参数设置、Canopy与K-means 算法的收敛阈值参数设置，以及向量相似度算法的距离度量选择，为提高检索、解析速度提供了一种方法。
参考文献
[1]陈少英.LBS中基于SVG的地图组织与应用[J].现代计算机：
专业版,2018,632(32):75-79.
[2]陈少英.基于SVG的地图服务系统的实现[J].现代经济信息，
2010,000(001):151.
[3]宁可.海量数据挖掘中的分类方法研究[D].杭州电子科技大
学，2018.
⑷杨健兵.Canopy和K-means聚类算法在公交IC卡数据分析中
的应用研究[J].无线互联科技，2019,016(011):125-128. [5]瞿卓.基于Hadoop2.0的数据挖掘算法并行化研究[D].广东
工业大学,2015.
作者简介
陈少英(1979-)，女，福建省厦门市人。硕士研究生，讲师。研究方向为计算机图形图像处理。
133