面向复杂应用的新型空间查询与模式挖掘技术研究

摘要

随着地理信息系统、互联网、移动智能终端等技术的发展，空间数据得到了极大的丰富，具有海量性、动态性和异构性等特点，为空间数据库技术的发展提供了新的机遇。通过对这些多样的、丰富的数据进行查询与挖掘可以有效提升智能交通、智慧城市、基于位置的服务、地理信息服务等重要应用的水平。 空间数据所表现的新特点为空间的复杂应用提供了基础条件，同时对空间数据库的查询与挖掘提出了新的挑战，主要体现在:1）查询需求不局限于单个对象，而更关注于查询分组对象关系或区域特征;2）空间查询需综合考虑对象多种类别的信息，包括位置、文本描述、对象关系及人员活动等信息;3）空间查询及挖掘表现出了智能化趋势，从多类型、海量的空间数据中高效、智能地获取知识能够进一步推动基于位置的服务发展。上述新的挑战对空间查询与挖掘算法、索引技术、评价方法等关键技术均提出了新的要求。 本文针对当前空间数据库中相关应用需求进行了归纳和总结，对空间数据查询与挖掘的研究现状进行了分析和综述。针对空间的复杂应用，对多种新型的空间查询与挖掘技术进行了深入研究，包括基于线索的区域位置定位、空间主题相关的区域发现、区域对象流动模式挖掘及区域流动模式查询处理等问题。在查询算法、索引、挖掘方法及结果应用等方面提出了相应的方法，这些技术可以有效地提高空间数据库系统的数据管理能力和处理效率，从而支持复杂的新型空间查询应用。本文的主要工作包括以下几个方面: (1)在空间位置查询方面，提出一种新的空间数据查询—基于线索的区域位置定位查询。由于环境信息的多样性、用户对空间认知的模糊性决定了线索是多样的、模糊的，将多样模糊的线索与海量空间特征数据有效匹配实现位置查询是一个重要的研究问题。为了有效地实现基于线索的查询，本文设计了三类算法，包括分支限界算法，逐个特征对象连接算法和基于预计算的算法。其中基于预计算的算法采用实例化预连接结果，设计了网格结构进行索引，线索查询在预计算的结果上进行，较大程度地提高了查询效率。 (2)在面向区域的查询方面，提出了主题相关的区域查询，查询返回与给定主题最相关的空间区域，解决城市主题的划分、设施的优化选址等决策分析问题。为了有效地处理主题相关的区域查询设计了三类算法，一类为基本查询算法;为根据结果分布的特点，定义了候选扩展区域，设计了过滤-提炼两阶段的第二类算法;基于聚类扩展区域、细粒度划分，进行候选区域收缩等方式设计了第三类算法，进一步提高了查询效率。所提出的算法解决了给定查询窗口下对数据空间任意位置按主题相关程度进行排序的问题。 (3)在面向区域的模式挖掘方面，研究了空间区域中移动对象流动模式的挖掘方法，将区域的流动规律以时间序列形式进行定量表示，用于改进城市规划、智能交通系统等方面。为了构建高预测精度的模式，本文提出了一种基于层次聚类的流动模式构建模型，模型中通过数据的离散化、序列化、模式训练等步骤实现了模式的构建;提出了偏斜度层次聚类树及异常序列去除方法，可以有效地去除局部异常序列及自动选取聚簇，提高了模式的预测精度。 (4)在空间区域的模式查询处理方面，提出一种新的模式收敛封装概念，用于查询匹配大量的移动对象流中的模式，且模式可以具有不同长度与匹配阈值。为了索引不同长度和阈值的模式，本文将模式等分为相同长度不同阈值的子模式，实现了多树和单树两种索引结构用以索引子模式。在模式匹配中，单树具有更好的剪枝能力，多树需要较少的内存。 针对以上问题，本文利用真实数据集对所提出的问题及算法进行了充分的实验，在有效性与效率方面进行评估验证，验证了所提出问题的意义及所提出的算法的高效性。总之，本文所研究的基于线索的区域位置定位、主题相关区域查询、区域流动模式查询与挖掘等问题扩展了空间数据库研究，解决了多种复杂的新型空间应用需求问题。

目录

声明

摘要

第一章绪论

1．1空间数据库

1．1．1空间数据库的发展

1．1．2空间数据库系统结构

1．1．3空间数据的分类

1．1．4空间数据的模型表示

1．2空间数据关键处理技术

1．2．1空间索引结构

1．2．2空间数据查询技术

1．2．3空间数据挖掘技术

1．2．4空间数据查询与挖掘的发展趋势

1．3本文的研究内容及组织结构

1．3．1本文的研究内容

1．3．2本文的组织结构

第二章基于线索的空间区域定位查询

2．1问题提出

2．2问题定义

2．3查询处理算法

2．3．1分支限界算法

2．3．2逐点距离连接算法

2．3．3基于预计算的算法

2．3．4算法分析比较

2．4实验评估

2．4．1数据集与实验设置

2．4．2算法性能评价

2．5本章小结

第三章空间中主题相关的区域查询

3．1问题提出

3．2问题定义

3．3查询处理

3．3．1查询框架

3．3．2 Baseline算法

3．3．3过滤-提炼两阶段算法

3．3．4基于收缩处理的算法

3．4实验结果分析

3．4．1查询有效性测试

3．4．2算法查询效率测试

3．5本章小结

第四章空间区域中对象流动模式挖掘

4．1问题提出

4．2问题定义

4．3模式挖掘模型

4．4模式训练

4．4．1偏斜度层次聚类树

4．4．2模式集的生成算法

4．5实验评价

4．5．1区域模式展示

4．5．2预测精度评价

4．6本章小结

第五章空间区域中对象流动模式查询处理

5．1问题提出

5．2问题定义及查询处理策略

5．3不同阈值模式的封装与匹配

5．3．1基本匹配算法

5．3．2带有收敛封装的楔形结构

5．3．3索引不同阈值的模式

5．3．4匹配算法

5．4不同长度模式的索引与匹配

5．4．1基于多树索引的匹配

5．4．2基于单树索引的匹配

5．5讨论

5．5．1内存需求

5．5．2尾部处理与划分粒度选择

5．6实验分析

5．6．1实验设置

5．6．2阈值变化和模式长度相同情况测试

5．6．3模式长度变化和阈值变化情况测试

5．6．4内存消耗

5．7本章小结

第六章结论

6．1本文的主要贡献与结论

6．2进一步的工作

参考文献

致谢

攻博期间发表的文章

攻博期间参加和完成的科研项目

作者简介