时空对象的聚类方法与应用初探

杨振凯，李 响，陈 达

（1. 信息工程大学 地理空间信息学院，河南 郑州 450001；2. 31682部队，甘肃 兰州 730020）

0 引 言

空间分析是传统地理信息系统(Geographic Information System，GIS)的核心和灵魂。近年来，由于受到不断增长的大量空间数据的驱动，从数据出发的空间数据挖掘技术、基于人工智能的空间分析技术以及时空大数据分析技术受到重视并得到了深入发展[1-2]。文献[3-4]提出了全空间信息系统和多粒度时空对象的概念，将系统中的分析功能由传统的空间分析扩展到了时空大数据分析；文献[5]提出了多粒度时空对象的数据描述框架，认为全空间信息系统拥有更宽泛、更细化、更动态、更多关联的复杂时空数据。这些都为在同一系统中实现复杂的时空分析奠定了基础。

聚类分析是时空数据挖掘领域极为重要的分析方法之一，经历了传统聚类分析（仅考虑属性的相似性）、空间聚类分析（考虑实体在位置上的接近或相邻关系）及时空聚类分析（考虑时间上的临近性以及属性的多维特征）等发展阶段。随着数据信息种类和数量的增加以及面向对象时空数据模型的发展，基于时空对象的分析将成为时空数据的主要分析方式之一。文献[6]认为地理时空对象中封装了对象的时态性、空间特性、属性特性、相关的行为操作以及与其他对象的关系；文献[5]提出多粒度时空对象具有时空参照、空间位置、空间形态、组成结构、关联关系、认知能力、行为能力和属性特征8个描述方面，并需要动态描述，是对现实世界多粒度时空实体较为完整的描述方式。由此可见，聚类计算应考虑如何对时空对象的多方面特征及其变化进行描述和度量，才能实现复杂而完善的聚类分析。

就目前而言，时间维、空间维和属性维是时空数据的“三维特征”，也是时空对象最为重要的描述方面。本文从时空对象的角度，顾及时空对象的空间位置、属性特征及其变化特点，研究基于时空对象的聚类分析方法流程和应用特点。这里所说的时空对象，是指客观世界存在的、具有生命周期的实体的抽象，其变化特征主要通过时间序列来体现。

1 空间聚类分析研究现状

目前空间聚类分析方法的研究相对成熟，具有比较广泛的应用。空间聚类分析主要解决两类问题：①空间点实体聚类分析；②空间扩展形态实体的聚类分析[7]。前者将空间实体简化为实体点，是聚类分析中最为常见的情况；而对于实体形状和维度不能忽略的情况，则采用第2种方法进行分析，如面状建筑物的聚类方法研究等。

1.1 相似度度量方法

为了度量对象之间的接近或相似程度，需要定义一定的相似性度量标准。在某些情况下，特征空间中的“距离”具有更形象的意义，因此，距离作为相异度的度量标准也被广泛使用。

1）空间距离度量。点实体之间的距离计算是空间各种实体距离计算的基础，需要满足非负性、对称性和三角不等式条件。对于Rm中的两个点Pi(xi1,xi2,…，xim)和Pj(xj1,xj2,…，xjm)，距离按式（1）定义：

式中，根据n的不同取值可分别计算曼哈顿距离、欧氏距离、最大范数距离等。

2）专题属性相似性度量。对于单维数值型的属性，可以直接使用空间距离的计算方法；对于两个包含多维专题属性的空间实体，常用的距离度量包括切氏距离、马氏距离、Caberra距离和平均距离等。衡量两个属性向量的相近程度经常使用相似性测度的方法，包括角度相似系数、相关系数、指数相似系数等；而对于某些特殊的属性（如取值为布尔型），可采取匹配测度的方法。

1.2 空间聚类的主要方法

空间聚类可以分为两种形式：一种是依据实体间的空间距离进行聚类，另一种则同时考虑实体间空间位置临近与专题属性相似。从方法上划分，这些空间聚类算法可分为基于划分、基于层次、基于密度、基于图论、基于模型、基于格网以及混合的算法。空间聚类方法的扩展研究方向主要包括多尺度、多形态、顾及障碍、局部密度适应性、评价方法等方面[8-9]。

2 时空聚类分析方法

时空聚类分析是时空数据挖掘研究内容的重要组成部分，旨在从时空数据集中发现具有相似特征的实体或现象集合，在地震监测分析、居民行为模式识别、交通通行状况评估等方面具有重要应用价值[10]。文献[11]从时空聚类研究内容的角度，将目前的时空聚类研究内容归为五类：时空事件、地理参考变量、地理参考时间序列、移动物体和轨迹，并将时空聚类的框架用图1的情况展示。其中时空事件、地理参考时间序列和轨迹具有明显的时间变化特点，是目前时空聚类应用较多的领域。

图1 时空聚类研究内容Fig.1 Context for ST clustering

2.1 基于时空事件的聚类方法

时空事件是指在某个时间点、某个空间位置上发生的事件，典型的时空事件包括地震、传染病例、战争等[12]。这里区分时空事件和时空对象，认为时空事件是对时空对象某一时间段（通常是某一时刻）特殊的状态变化和行为的描述。在基于时空事件的聚类方法中，人们并不关注参与事件的时空对象本身（如究竟是哪个人感染了疾病），或是无法描述参与事件的时空对象（如是哪些地球板块之间运动形成了地震），而是对事件的位置和时间感兴趣，希望通过聚类方法发现这些事件的某种关联性。现有的时空事件聚类分析方法大致可以分为3种类型：①时空扫描统计；②时空密度聚类；③时空混合距离[13-15]。

2.2 基于时空观测变量的聚类方法

时空观测变量又称为专题属性时间序列，主要是针对空间位置固定、专题属性随时间变化的时空数据，将观测属性视为附加了空间位置和时间标签的时空实体，进一步针对时空实体进行聚类[16]。属性分布往往和空间和时间都有一定的关联，需要考虑时空耦合性，因此该方法也称为基于时空耦合的聚类方法。与时空事件类似，基于时空观测变量的聚类方法也是将时空数据抽象为时空坐标系中的一个点进行聚类计算，其方法同样分为时空扫描统计、时空密度以及时空混合距离3种。

2.3 基于轨迹的聚类方法

轨迹聚类是时空聚类计算中极为重要的一部分，通过对各种时空轨迹数据进行聚类分析，可以提取时空轨迹数据中的相似性并识别异常特征，有助于发现有意义的模式。时空轨迹是描述移动对象运动时间和位置的数据，其意义是连续的，但通常用一组时空点序列以离散的方式表示。文献[17]将时空轨迹聚类方法归纳为6类：时间全区间相似的聚类方法、全区间变换对应相似的聚类方法、多子区间对应相似的聚类方法、单子区间对应相似的聚类方法、单点对应相似的聚类方法和无时间区间对应相似的聚类方法。轨迹数据获取最为便捷，数据种类多种多样，基于轨迹数据的聚类分析应用范围涵盖了人类行为、交通物流、应急疏散管理、动物习性和市场营销等诸多方面。

3 时空对象的聚类分析方法流程

基于时空对象的聚类与传统的聚类分析方法的不同表现在：前者是针对某个时间段或在生命周期内，研究时空对象的空间位置、多维属性等特征的相似性，对时空对象进行聚类计算。若只针对单一时间点进行聚类处理或时空对象没有发生任何变化，则与空间聚类方法没有本质区别。时空对象的聚类分析方法流程如图2所示。

图2 时空对象的聚类分析方法流程Fig.2 Clustering process of ST objects

3.1 时空对象时间序列的相似性描述

在时空对象的生命周期内，空间位置和多维属性往往随着时间而变化，表现为对应于时间节点的空间位置序列（轨迹）和属性序列，统称为时间序列。对于某个研究的时间段，时空对象可能始终存在，也可能由于生命周期不同而分布于不同的时间区间，但都要考虑如下问题：

1）轨迹的相似性描述方法。轨迹表达的意义连续，采样点的坐标有二维三维之分；轨迹相似性度量方法较多，目前主要采用的方法为时间全区间相似计算方法。除了轨迹间欧式距离度量方法之外，还可以采用MBR距离、DTW距离、编辑距离等。

2）多维属性的相似性描述方法。属性信息的多样性决定了属性序列的种类相对复杂。从实际意义方面，属性变量可分为离散型和连续型变量；从取值类型方面，属性变量可能是数值型、布尔型甚至是文本型；从维度来看，时空对象的属性分为一元序列和多元序列。属性时间序列相似性表达需要依据传统序列挖掘中的序列相似性查找与匹配算法，确定通用的相似性计算模型。

总体来看，时间序列的相似性度量还需要考虑研究对象的时间区间长度是否一致、采样点间隔是否均匀、是否含有噪声数据，甚至原始数据不是序列表达形式等问题，必要时需要对序列数据进行重采样处理。

3.2 基于时空对象的聚类计算

基于时空对象的聚类计算主要是根据研究的时间段，建立对象间的相似度（或距离）计算模型和判别方法，选择某种聚类方法，将所有对象划分为不同的簇（或孤立对象），其内容如图3所示。

图3 基于时空对象的聚类计算Fig.3 Clustering calculation of ST objects

1）时空对象相似度计算模型。时空对象的属性变化特征与空间变化特征应作为时空聚类中重要的影响因素之一。除此之外，对象本身可能存在不随时间改变的本质属性，或是某些属性达到阈值或级别特征，可作为相似度计算的先决条件。如在轨迹聚类计算中，两条轨迹的长度差异过大，可认为不属于同一级别而直接排除对象相似性。对于时空对象存在多个属性时间序列的情况，还需要研究多时间序列对于聚类处理的综合影响，如某些属性的变化相似性对于聚类的重要性远大于其他因素，应赋予较高的权重比。

2）时空对象的聚类方法设计。在建立时空对象之间相似度或者距离的计算模型之后，需要采用某种搜索策略对所有对象访问，有时还需要进行多次遍历，从而使得某种迭代过程收敛或满足阈值条件。聚类过程中，需要考察算法的通用性，即是否对于时空对象的绝大多数特征都可以计算；需要考虑聚类算法对于数据参与运算顺序的敏感性，即在多次重复实验中以不同的顺序进行计算是否能保持聚类结果的稳定性；需要考虑对噪声和孤立点数据的处理能力，尽可能自主识别和筛选孤立点数据。考虑现实世界中时空对象的复杂性，一种聚类算法可能是不足的，必要时应采用多种算法相结合的计算模型。

3.3 时空对象聚类的评价方法

有效性评价一直是聚类分析中的难题。现阶段对于空间聚类，尤其是时空聚类有效性评价研究较少，以至于评价方法远远落后于聚类算法本身的发展。时空对象聚类的有效性评价主要解决两方面的问题：①针对某个应用背景，选择哪种时空对象聚类处理方法是最合适的；②针对某种时空对象聚类算法，选择怎样的参数配置是合适的。聚类结果的定量评价将为用户选择方法和调整参数提供重要的依据。

衡量时空对象聚类方法的标准体现在两方面：一是准确性，主要通过各类有效性评价指标，通过对聚类结果生成簇的分离程度和紧密程度进行计算得出；二是算法效率，主要通过理论上的算法复杂度和实际执行情况进行判断。已有的空间聚类评价方法可以为时空对象聚类评价方法提供借鉴和参考，如相对评价法中的DUNN指数、DB指数、SD指数等。

4 时空对象的聚类分析应用特点

4.1 聚类分析特点

1）聚类分析考虑时空对象的“三维特征”，分析内容更为全面。与此相比，现有的时空聚类方法在分析的内容方面存在一定不足。如轨迹聚类只关注于移动物体随着时间的空间位置移动，缺乏对于多维属性信息的描述；而基于观测变量的聚类则主要针对于空间位置固定而属性信息变化的问题进行研究。事实上，这些都可以看作时空聚类分析中的特殊情况；对于地理空间中既具有属性变化特征又具有位置变化特征的实体来说，上述聚类方法还不能适用。

2）基于对象进行聚类分析，更符合人们对于世界的认知规律。在多粒度时空对象的描述模型中，多维属性特征和空间位置都是其中的一部分且需要动态描述；由于目前基于地图模型的传统GIS数据描述能力有限，导致许多观测数据无法形成对象化的描述与分析。如在基于观测变量的时空聚类中，往往是以某个时刻某个观测地点的属性作为实体点进行聚类运算，属性维扩展性差，缺少对于时间段内对象的变化特征描述，割裂了对象的完整性。

4.2 应用场景设计

1）传统地理分析应用，以台风运动为例。西北太平洋地区，尤其是东北亚地区，台风灾害多发，这些地区的台风运动特点对社会经济发展带来深刻的影响。台风具有明显的生命周期特征，在其生命周期内轨迹和属性都有一定的变化。台风的变化属性主要包括移动速度、中心风速、气压等，其等级可作为聚类分析的先决条件。通过对轨迹和属性综合信息的相似性比较和对象聚类，可以对台风活动进行更准确的认识和分类，甚至辅助预测台风的运动特征。

2）其他领域分析应用，以体育运动为例。随着人们对于运动和健康的关注持续增加，各种运动记录方法、仪器和数据也不断产生。Sport GIS是GIS应用从宏观空间扩展至微观空间的发展方向之一，用于体育训练和运动员状态分析。如根据记录的足球或篮球运动员在球场上的活动轨迹，以及移动速度、心率等状态信息的变化，通过聚类分析研究某个运动员频繁出现的运动状态，或根据不同运动员的数据研究相似的活动特征，这些都将为分析运动员的身体状况、合理制定训练比赛计划提供依据。

5 结束语

本文针对时空数据的时间维、空间维和属性维特征，总结并分析了空间聚类和时空聚类的研究现状，提出了基于时空对象的聚类方法的主要流程和应用特点。以多粒度时空对象对现实世界进行抽象和建模是全空间信息系统的基本特征，对象化的管理和分析代表了新一代空间信息系统的应用需求方向。多粒度时空对象包含了丰富的特征描述信息，如何对形态、组成结构等方面加入聚类的相似性计算方法将是今后时空对象聚类的拓展研究方向。