到达数据中时空异常聚簇发现

在时空数据中有一类表示用户在某一时间到达某一地点的数据——到达数据,到达数据可以是社交网站的签到数据、轨迹数据中的停留点及公共交通中乘客抵达的位置数据,这些数据的聚簇可以反映用户的聚集行为.基于到达数据,提出一类新的时空数据查询——时空异常聚簇发现.将到达数据进行周期性划分,通过时空聚类算法对一个时间段的数据进行聚类,比较不同时间段内聚簇的差异度,发现具有最大簇异常度的前k个簇.通过该查询发现的时空异常聚簇可以应用于城市安全管理、基于位置的服务和交通调度等方面.定义了异常簇查询模型,提出了针对任意形状聚簇的簇差异度度量,将异常簇查询转化为二分图最大匹配问题,对二分图构建与匹配进行了优化并提出了高效的查询算法.利用真实数据集进行了充分实验,验证了查询结果的实际意义,评估了所提出的各查询算法在不同参数设置下的查询效率.     

海量中文短信文本最佳聚类数研究

针对海量中文短信文本的聚类簇数的确定问题，提出一种基于聚类过程的短信文本最佳聚类数确定方法。通过扫描一遍数据即可获得多个统计信息，利用增量逐层划分得到最优划分所对应的簇类数，求出最优解。实验结果表明，与其他方法相比，该方法的分类效率较高。     

采用元组聚类的增量式数据分区方法

数据分区是提升数据库可扩展能力的有效方法。在事务查询密集的系统中,合理的分区策略可减少分布式事务查询数量,并提高事务查询响应速度。提出了一种基于元组聚类的增量式分区方法,通过将元组聚簇和采用分区感知的数据筛选策略来降低算法的复杂度。首先依据时间窗口模型聚类元组,并构建簇节点图,然后利用分区感知策略对图进行删减,最后采用图划分算法对图进行子图划分来得到分区。与现有方法相比,该方法减少了分区响应时间,保证了较少的分布式事务数量,并提高了分区事务查询速度。     

基于实体对象树FOOT模型和四层体系结构的GIS方法研究

提出了面向地理空间实体对象树模型(FOOT)，首先重点讨论了空间分区、空间聚簇、空间索引，然后分析了四层结构设计中的数据库服务层、应用接口层、应用层相关技术。基于所提出的空间数据组织方法和系统结构，介绍了具有海量空间数据管理的系统功能模块，并提供了详细的对象逻辑关系说明。同时在对FOOT模型和系统实现的关键技术进行设计的基础上，给出了一个基于Linux操作系统和Oracle数据库的分布式海量空间数据处理平台实例。采用30GB的空间数据测试结果表明，系统实现了面向实体的空间数据组织、统一的海量空间数据管理以及分布式空间数据计算等主要目标。该系统用于对全国1：400万土地利用图、1：400万市县行政图数据上载的试验表明，不仅显示速度较快，且图形裁剪、空间叠加、缓冲分析等效率较高，验证了FOOT模型的正确性、有效性、合理性。     

基于MongoDB的轨迹大数据时空索引构建方法

近年来,随着计算机技术与无线传感器网络的发展,轨迹大数据越来越得到人们的关注.针对海量轨迹数据在存储与查询中出现的效率问题,文章基于文档型非关系型数据库MongoDB提出了一套基于四叉树的道路网时空索引,实现海量轨迹数据的高效查询.通过对太原市1915辆出租车的50万条轨迹数据进行时空查询,在不同数据量与不同并发数下测试道路网时空索引与MongoDB复合时空索引的效率表现.实验结果显示道路网时空索引在数据量大于10万时有较好表现,并能够适应不同并发数下的时空查询,验证了道路网时空索引构建方法的可行性和高效性.     

基于时空约束密度聚类的停留点识别方法

轨迹停留点的识别是轨迹分析、出行活动语义挖掘的关键。针对基于密度聚类的停留点识别方法对时空信息的表达缺陷,提出新的时空约束停留点识别方法,在密度聚类中引入轨迹的间接时空特征表示,将具有时空相似性的轨迹点进行聚合;采用与聚类过程相统一的时空特征约束对轨迹簇进行细粒度识别。算法在进行约束的时候再次利用到聚类时候所用的输入数据特征,特征的充分利用提高了识别的准确率。实验结果验证了本文方法的有效性。     

大规模数据集下基于DBSCAN算法的增量并行化快速聚类

时空轨迹数据挖掘是发现移动对象行为模式的重要方式。针对海量轨迹数据处理的需求,提出一种增量并行化快速聚类算法。算法基于数据点的数量采用二分法对空间网格分区,结合贪心算法弹性重组分区,合理进行数据划分;进行本地局部聚类,获得合并簇候选集;采用R*-tree索引候选簇进行合并判断并处理;建立合并簇的无向无环图模型,并进行数据的全局重标签。实验结果表明:算法的弹性分区处理能有效地减少噪点数据,提高局部聚类的质量,采用R*-tree索引结构的合并策略有效提高了聚类的时间效率,聚类效果好,能实现大规模数据的在线处理。     

关系数据库中海量要素存储的分区优化研究

目前,关系数据库中的分区技术应用相当广泛,但是用分区策略管理海量要素图层数据的存储与索引没有比较系统的技术方法。采用不同管理方式、不同分区粒度、不同索引方式及其组合的分区技术来系统地管理海量空间图层数据,进一步研究了不同的分区粒度及索引方式对查询效率的影响,并通过实验验证了关系数据库中的分区技术对海量要素图层数据的存储与管理具有优化作用。结果表明,在不使用分区键作为查询条件时,分区粒度越大查询效率越高;使用分区键作为查询条件时,本地分区索引查询效率更高等。利用合理的分区方案使得海量要素图层数据存储和管理得以优化,对矢量大数据的存储和管理研究具有重要意义,为更好地应用分区技术来解决实际遇到的存储与检索效率问题提供决策支持。     

时空数据挖掘研究进展

近年来,随着全球定位系统、传感器网络和移动设备等的普遍使用,非时空数据和时空数据急剧增加,加之时空数据处理更为复杂,使数据处理任务日趋繁重的形势更加严峻.因此,寻找有效的时空数据挖掘方法具有十分重要的意义.针对这一背景,主要围绕时空模式发现、时空聚类、时空异常检测、时空预测、时空分类、时空数据挖掘与推理的结合等方面,对时空数据挖掘研究的现状进行了详细介绍,对其当前所面临的一些主要问题及可能的解决方案进行了探讨.     

面向海量数据流的基于密度的簇结构挖掘算法

提出一种基于密度的簇结构挖掘算法(mining density-based clustering structure over data streams,简称MCluStream),以解决数据流密度聚类中输入参数选择困难和重叠簇识别等问题.首先,设计了一种树拓扑CR-Tree索引结构,将直接核心可达的一对数据点映射成树结构中的父子关系,蕴含了数据点依赖关系的CR-Tree涵盖了一系列subEps参数下的基于密度的簇结构;其次,MCluStream算法采用滑动窗口的方式更新CR-Tree,在线维护当前窗口上的簇结构,实现了对海量数据流的快速演化聚类分析;再次,设计了一种快速从CR-Tree提取簇结构的方法,根据可视化的簇结构,选择合理的聚类结果;最后,在真实和合成海量数据上的实验验证了MCluStream算法具有有效的挖掘效果、较高的聚类效率和较小的空间开销.MCluStream可适用于海量数据流应用中自适应的密度聚类演化 分析.     

时空聚类分析的普适性方法

时空聚类分析是时空数据挖掘领域近年来研究的热点问题,对于揭示时空要素的发展变化趋势、规律以及本质特征具有重要意义.目前,时空聚类分析的研究仍还初步,缺乏具有普适性的时空聚类分析方法.为此,本文首先建立了一套时空聚类分析的普适性理论方法框架.进而,借助时空统计学、智能计算等工具,提出了一种时空一体化的时空聚类方法.该方法很好地顾及了时空数据的时空耦合、时空相关与时空异质特征,避免了过多人为主观因素的干扰,时空聚类结果具有较好的可靠性.通过采用中国陆地区域42年(1951～1992)年平均气温时空数据进行分析,验证了本文提出的理论与方法的可行性与有效性.     

基于实时数据和历史查询分布的时空索引新方法

在大数据时代,数据具有体量大、时空复杂性明显、对实时性要求较高等特点,而传统基于树形结构对大规模时空数据进行索引的方法存在存储空间浪费和查询效率较低的问题。为了解决该问题,提出了一种基于数据和历史查询记录分布建立时空索引的新方法HDL-index。该算法一方面根据数据在空间上的分布,通过空间划分的思想建立索引网格;另一方面考虑到查询在时间上的延续性,对查询记录对象进行密度聚类后抽象出查询代表模型,然后根据模型的坐标位置和其查询粒度对整体查询区域进行分割。两部分所得到的索引网格都采用Geohash编码,最终合并得到最优的索引编码。HDL-index在考虑数据分布的同时充分考虑用户查询行为,使得频繁查询区域上的索引更加细化。在真实航空数据集上与同类方法进行比较测试的结果表明,其创建索引的效率提高了50%;同时在数据均匀分布的情况下对热点区域的查询效率可提高75%以上。     

A general method of spatio-temporal clustering analysis

Spatio-temporal clustering has been a hot topic in the feld of spatio-temporal data mining and knowledge discovery.It can be employed to uncover and interpret developmental trends of geographic phenomenon in the real world.However,existing spatio-temporal clustering methods seldom consider both spatiotemporal autocorrelations and heterogeneities among spatio-temporal entities,and the coupling in space and time has not been well highlighted.In this paper,a unifed framework for the clustering analysis of spatio-temporal data is proposed,and a novel spatio-temporal clustering algorithm is developed by means of a spatio-temporal statistics methodology and intelligence computation technology.Our method is applied successfully to fnding spatio-temporal cluster in China’s annual temperature database for the period 1951 1992.     

时空推理中自动生成复合表的通用算法

时空推理是面向时间/空间问题的研究领域,在人工智能(如语义Web、机器人导航、自然语言处理、物理过程的定性模拟和常识推理等)和其他领域有着广泛的应用前景.复合推理在时空推理中具有重要作用,是约束满足问题等其他定性推理的基础.复合推理是由R(a,b)和R(b,c)决定R(a,c)的一种演绎推理.一般将关系复合结果放在复合表中备查.但目前复合表的建立需要逐个模型进行手工推导,少数模型给出了独立的复合表生成算法,没有适合多种时空关系模型、能自动生成复合表的通用算法.为此,提出了一种能自动生成复合表的通用算法.首先,给出了基于空间划分的通用时空表示模型.在此基础上,提出了基于场景检测的通用复合表生成算法.通过理论分析和对RCC、宽边界、区间代数等20余种典型时空模型的测试,证明了本算法对于所有以精确区域(或区间)为基础的确定、不确定时空模型均能正确快速地生成复合表.     

基于Hilbert-R树分级索引的时空查询算法

针对树形空间索引中多路查询及未考虑时间维索引的问题,提出一种结合时间和聚类结果的Hilbert-R树索引构建策略。首先,按照数据采集的周期划分时空数据集,并在此基础上建立时间索引,通过Hilbert曲线对空间数据进行分割编码,将空间坐标映射到一维区间;其次,依据数据要素在空间中的分布,采用动态确定K值的聚类算法,结合聚类结果构建高效的Hilbert-R树空间索引;最后,基于Redis几种常见的键值数据结构,对时空数据的时间属性和聚类结果构建分级索引。在时空范围及目标矢量对象查询的实验中,与缓存敏感R+树（CCR+）相比,所提算法可有效减少时间开销,查询时间平均缩短约25%,对不同密集型数据具有良好的适应性,可更好地支持Redis应用于海量时空数据查询。     

基于时空模式的轨迹数据聚类算法

针对轨迹聚类算法在相似性度量中多以空间特征为度量标准,缺少对时间特征的度量,提出了一种基于时空模式的轨迹数据聚类算法。该算法以划分再聚类框架为基础,首先利用曲线边缘检测方法提取轨迹特征点;然后根据轨迹特征点对轨迹进行子轨迹段划分;最后根据子轨迹段间时空相似性,采用基于密度的聚类算法进行聚类。实验结果表明,使用所提算法提取的轨迹特征点在保证特征点具有较好简约性的前提下较为准确地描述了轨迹结构,同时基于时空特征的相似性度量因同时兼顾了轨迹的空间与时间特征,得到了更好的聚类结果。     

基于时空切片的球拍类体育视频比赛镜头抽取

提出了一种基于短时切片的球拍类体育视频比赛镜头提取方法。该方法对视频时空切片分帧,通过对切片帧聚类、合并、边界检测和映射获取比赛镜头。实验表明该方法具有很好的鲁棒性和准确度。     

面向海量交通数据的HBase时空索引

针对HBase无法直接建立时空索引所带来的交通数据查询性能问题,基于HBase行键设计了面向海量交通数据的HBase时空索引。首先利用Geohash降维方法将二维空间位置数据转化为一维编码,再与时间维度进行组合;然后根据组合顺序的不同,提出了四种结构模型,分别讨论了模型的具体构成以及交通数据查询中的适应面;最后提出了相应的时空索引管理算法及基于Hbase时空索引的交通数据查询方法。通过实验验证了提出的HBase时空索引结构能有效提升海量交通数据的区域查询性能,并比较了四种时空索引结构在不同数据规模、不同查询半径以及不同时间范围的查询性能,量化验证了不同索引结构在交通数据查询中的适应场景。