基于语义聚类的查询分解算法在空间数据集成系统中的应用

饶祎　卢桂强　霍睿　王丰

摘要：通过对空间数据集成系统中数据查询基本流程的分析，指出了系统中数据源的异构性给查询带来的问题，并阐述了传统基于语法层面的查询分解方法的不足。提出了一种基于语义聚类的查询分解算法，在语义层面上将用户的查询请求分解为子查询并提交给相应的数据源，从而提高了系统对数据查询请求的响应率和结果的精确性。

关键词：空间数据集成；查询分解；语义距离；聚类算法；K-means

中图分类号：TP311.11 文献标识码：A 文章编号：1009-3044（2014）21-4963-04

对于大型的空间信息系统而言，其建设往往不是一蹴而就的，一般都需要很长的时间、地域跨度，这就导致了不同时间、地点建设的部分产生了一定程度的异构性，形成了众多的“信息孤岛”。而空间数据集成的主要目的就是屏蔽底层数据源的异构性，使用户能够透明地访问这些数据源[1，2]，即在存储、表示、管理、通信等方式均不相同的异种数据源上，通过资源服务的方式为用户提供逻辑上统一的数据视图和信息访问接口。简而言之，空间数据集成系统就是架设在用户与众多数据源之间纽带，而评判一个空间数据集成系统是否优秀的一个重要方面，就是看这个它能否为用户提供精确、快速的数据查询服务，这往往是用户最关心的事情。

空间数据集成系统中通常集成了多种分布的异构数据源，它们之间没有统一的模式结构，对于相同概念的表述往往不尽相同，这给数据查询带来了很大的困难。用户提交的数据查询请求，通常包含多个概念且没有统一的规范，如果不经预处理，直接下发给数据源进行检索，会极大地增加通信开销，并且还会令各数据源进行大量不相关的查询操作，严重影响系统的性能。因此，为空间数据集成系统设计一种准确高效的查询分解算法是必要的，其目的是使得分解后生成的子查询能够更加贴合不同数据源的要求，降低开销，提高系统对用户查询响应效率及精确性。

1 关键技术概述

1.1查询分解

空间数据集成系统的查询分解流程如图1所示，用户通过统一的服务接口描述自己所需的数据并提交查询，系统解析查询，将查询分解为多个子查询提交给相应的数据源，之后将这些数据源返回的结果以统一视图反馈给用户。

如何对顶层用户的查询请求进行有效的分解，并使得分解后的子查询比原来的查询请求更容易得到满意的匹配服务，这是能否为用户提供精确空间数据服务的关键。传统的信息查询技术主要是基于语法层次的，它能够在为用户提供一定程度的数据资源发现功能，但无法对用户查询进行语义层次的理解，导致了查询系统经常“误解”用户的初衷，用户提交的查询请求通常会得到大量与需要无关的搜索结果。而对于每一个独立的空间数据源实体来说，它所涉及到的空间数据概念往往较为集中，如果查询请求分解后的子查询中包含的概念范围是发散的，则分解后仍然无法得到满意的匹配结果。

为解决以上问题，该文采用基于语义聚类的查询分解方法对用户的查询请求进行预处理，在语义层面上将其分解为概念范围相对集中的子查询，以提高子查询的匹配成功率。

1.2语义距离

为了将人们在Web上使用的文本信息转化为计算机系统能够理解的描述，万维网之父英国人TimBerners Lee提出了语义Web这一概念[3]，目的是通过将Web内容的语法结构和语义以知识表示形式呈现出来，以实现与其它信息源共享知识，使得人与人、人与机器以及机器与机器之间能够准确地互相理解。

基于语义Web思想，可以通过构建空间数据集成系统统一的知识体系，对系统中不同的数据源上的信息进行语义标记，将模糊、有异义的关键词抽象、提炼为精确、无异义的概念。判断用户需求与数据源的相关程度，其实就是看查询请求表述的概念与数据源表述的概念之间语义距离的大小。

语义距离是指在不同概念间存在的继承关系或二元关系链中最短的关系链长度的一种度量，通过对概念之间相似程度的计算，可以量化概念之间的语义距离。

概念间的语义相似度计算公式[4]为：

1.3聚类分析

聚类分析是知识发现（Knowledge Discovery in Database， KDD）中的一项重要研究内容，旨在将数据集合划分为若干类的过程，使得类内差异小，类间差异大[5]。在这个过程中没有任何关于数据集分类的先验知识，没有任何指导，仅仅依靠事务之间的相似性作为类属划分的准则。聚类准则是度量分类对象之间的接近与相似程度从而判断样本是否归为一类的分类数据指标，通常的聚类准则可分为三个：基于距离的、基于密度的以及基于联接的。聚类的方法主要可以分为基于划分的方法、基于分层的方法、基于密度的方法和基于网格的方法[6]。

第一种是划分法（partitioning methods）。给定一个有N个元组或者记录的数据集，分裂法将构造K个分组，每个分组将代表一个聚类，K

第二种为层次法（hierarchical methods）。对给定的数据集进行层次似的分解，直到某种条件满足为止。具体有可分为“自底向上”和“自顶向下”两种方案。例如在“自底向下”方案中，初始时每一个数据记录都组成一个单独的组，在接下来的迭代中，它把那些相互邻近的组合并成一个组，直到所有的记录组成一个分组或者某个条件满足为止。代表算法有：BIRCH算法、CURE算法、CHAMELEON算法等。

第三种是基于密度的方法（density-based methods）。它不是基于各种各样的距离的，而是基于密度的，只要一个区域中的点的密度大于某个阀值，就把它加到与之相近的聚类中去。代表算法有：DBSCAN算法、OPTICS算法、DENCLUE算法等。

第四种为基于网格的方法（grid-based methods）。先将数据对象空间划分成为有限个单元（cell）的网格结构，所有的处理都是以单个的单元为对象的。代表算法有：STING算法、CLIQUE算法、WAVE-CLUSTER算法。

2 基于语义距离的K-means聚类查询分解算法

通过对主要的聚类算法进行比较，由于K-means聚类法具有运算量小、能用于处理庞大样本数据的明显优势，该文采用K-means聚类法作为数据查询请求分解的基础。

2.1算法基本思想

K-means算法[7-8]的核心思想是：给定簇的个数K，将n个对象分到K个簇中去，使得类内对象之间的相似性最大，而类之间的相似性最小。其使用随机方式选择K个元素作为初始的聚类中心，按照算法的迭代执行，整个算法的结束条件是簇的中心（或凝聚点）不再改变。K-means的计算复杂性是O（nKt），其中，n为元素数量，K为簇的数量，t为迭代次数。

2.1.1聚类准则函数

2.1.2聚类中心的选择方法

算法的每次迭代需要确定新的聚类中心，由于查询请求的聚类结果是概念的集合，选择聚类中心也就是选择最能够代表这个类中的语义含义的子概念。本算法中采用了基于最小距离和的中心选择方法，即如果某一子概念到类内其它概念的距离和最小，就将其设定为新的聚类中心：

2.1.3算法工作原理

算法首先随机从请求概念集中选取K个点作为初始聚类中心，然后计算各子概念到聚类中心的距离，将其归到离它最近的那个聚类中心所在的类。计算新形成的类的聚类中心，如果相邻两次迭代的聚类中心没有任何变化，说明分解调整结束，聚类准则函数GC已经收敛。

2.2 算法描述

3 性能分析与结论

在实验环境中，我们对基于语义聚类的查询分解算法进行了仿真测试，对含有不同空间属性概念个数的查询访问进行了模拟，以此来分析算法在数据查询请求复杂度不同的情况下的表现。图2显示了算法在各种请求复杂度情况下的响应率，可见使用传统查询算法的情况下系统响应率随着数据查询请求复杂度的提高急剧下降，而采用了语义聚类查询分解算法的曲线则较为平缓。

实验结果证明基于语义聚类的查询分解算法可以有效地提高系统对用户数据查询请求的响应率，从而提高了空间数据集成系统的总体性能。

参考文献：

[1] Maurizio L. Data Integration： a Theoretical Perspective[J].The ACM SIGACT-SIGMOD -SIGART Symposium on Principles of Database Systems， 2002.

[2] 李晓军，丘健妮，彭龙军，等.多源空间数据集成技术状况与应用前景研究[J].计算机与现代化，2006（5）.

[3] Bermers-Lee T，Hendler J，Lassila O. The semantic web[J].Scientific American，2001，284（5）：34-43.

[4] 王家琴，李仁发，李仲生.一种基于本体的概念语义相似度方法的研究[EB/OL].http：//www.paper.edu.cn.

[5] Han J W，Kambr M.Data mining concepts and techniques[M]. Beijing： Higher Education Press，2001：145-176.

[6] 张敏.基于划分的模糊聚类算法[J].软件学报，2004（6）.

[7] Olivia P. 数据挖掘实践[M].北京：机械工业出版社，2003.

[8] 周爱武，于亚飞. K-means聚类算法的研究[J].计算机技术与发展，2011，21（2）.