英语原文共 9 页，剩余内容已隐藏，支付完成后下载完整资料

用自适应k-均值聚类进行风暴空间模式识别

摘要——我们早期的工作通过极大量的降雨数据获得了规律性的风暴模式，本文对早期工作进行了延伸。在早期的工作中，我们描述了基于MapReduce的算法识别出的三类风暴：局部，小时性和整体风暴。在一般情况下，局部风暴在一个特定地点具有时间特征，小时性风暴在一个特定时间具有空间特征，而整体风暴同时具有空间和时间特征。我们的目标是，在时空数据（整体风暴是地理重叠，连续每小时的风暴的集）中挖掘到规律性模式和预测轨迹。在本文中，基于风暴的形状和大小，我们采用k-均值聚类来发掘不同类型小时性风暴。由于降雨数据通常大于单个计算机的内存容量，我们通过分布式数据处理框架Apache Spark实现该算法，并在计算机集群上运行实验。

关键词——Apache Spark、分布式计算、空间数据挖掘

1. 简介

很多数据分析和数据挖掘应用涉及时空数据。这样的例子包括移动物体，轨迹（车辆、动物的运动数据，携带手机/ GPS的人），以及像风暴和飓风这样的运动区域。本文基于随时间推移变化的形状和运动，重点研究如风暴和飓风这样的移动区域的聚类。例如，由于沿着风暴轨迹移动，风暴形状会随时间而变化。另一个典型的例子是森林火灾的发展趋势。

我们有50年来的降雨原始数据，这些数据覆盖德克萨斯州的大部分，以及包括科罗拉多、新墨西哥、路易斯安那和墨西哥等一些周边地区在内的一部分数据。在早期的工作中，我们开发了分布式MapReduce算法来分析数据，并定义了三个风暴概念：局部，小时性和整体风暴。

局部风暴描述风暴的位置特征，它显示了特定地点风暴的持续时间。它被定义为在一个特定空间内的一组连续的时间点和相关的降雨数据。两个不同的局部风暴在分离时间点无降水。这种定义风暴的传统方式，已被水文学者纳入研究范畴[ 4 ] [ 5 ] [ 6 ] [ 7 ]。

在水文领域，降雨/风暴分析主要是基于方法收集和存储的降雨数据，相对于专注新的计算技术，这些更多地是基于位置的。

另一方面，小时性风暴指的是基于时间的风暴特征，与局部风暴的概念形成鲜明对比。进行风暴分析时，每小时（时间点）都被认为是独立的。在给定内段内的小时性风暴，被定义为一组相邻地点及在特定的时间内记录的相应降雨值的集。

注意，小时性风暴可看作随时间推移收集的空间数据，而局部风暴可看作现场收集的时间数据。如果单独使用这两个风暴概念，并不能充分获取某区域内风暴的发展趋势。因此，只有结合这两个概念，才能定义整体风暴的概念。

整体风暴，描绘了风暴随时间推移的整体时空特征。提取的概念风暴信息不仅允许基于位置的分析，而且还包括对风暴的特定分析（在位置和时间上）。多个连续的小时性风暴有空间重叠相结合，以创建风暴为中心的整个风暴的特点。总的风暴中移动区域随着时间推移。对于这种时空数据，空间部分不断移动且形状随时间变化。

这项工作的目的是，以小时风暴为例，集群空间数据。它可以帮助我们进一步分析时空数据，这些时空数据被定义为有空间重叠的小时性风暴的时间序列。我们可以使用这些集群的每小时风暴的空间集群，以找到模式在未来的整体风暴。

此外，我们试图分析50年来的大规模风暴数据，因此我们在分布式框架Apache Spark进行了算法实现。

本文重点研究时空空间部分的时间数据的聚类。我们采用了k均值算法，并执行了聚类任务。本文的其余部分如下。第二部分讨论了不同的方法来进行风暴跟踪、时空聚类以及风暴概念与相关分析。第三节介绍了采用k均值算法进行小时性风暴的聚类。实验和结果在第四节。在第五节我们总结了工作并讨论了未来工作。

1. 相关工作

为了有效地分析风暴，包括风暴轨道的特点，需要考虑不同轨迹分析的概念。根据用户的域，我们把相关工作分为三部分。第一部分在GIS或气候学方面对风暴进行了跟踪研究，其次用挖掘算法处理了大规模时空数据集，并在第三节寄托之前的工作介绍了风暴概念。

A．风暴路径分析

Chang et al在水文观点中提出过风暴轨迹的基本概念。他们讨论了风暴路径的定义、分类和区别。空间维度在分析风暴路径中起着非常重要的作用，因此风暴分析研究通常在不同地点分别进行。一年的时间也显著；季节、年际、年代际风暴都不同。影响风暴轨道的五要素包括：斜压过程，线性不稳定，下游发展，正调制和非绝热加热。因此，文中对建模风暴轨道的两种方法进行了介绍：1）通过使用所有的五个物理过程和；2）通过使用最低限度（一些进程）。但是，风暴采矿不建议也不适用于本文。此外，没有提到过分布式计算技术。

随着GIS在90年代后期得到普及，气候成为了一个GIS成功应用的领域。举例来说，可使用GIS软件ArcView分析风暴路径。风暴的运动被定义为一个序列的风暴中心，一个中心，承载了最强烈的暴雨重力。为了对风暴路径进行建模和分析，提出过两种方法：回波质心和互相关。实验表明，在风暴轨道的大小和形状不改变的情况下，前者优于后者。但方法的缺点如下，步骤中涉及人工干预，难以自动化。处理按顺序完成。最后，有许多先进复杂的工具和命令，提供了更大的灵活性，但不容易与ArcView兼容。

风暴识别算法被提出以用于识别风暴以及其轨道。与以前的方法相比，该算法具有高度适用性和强大性。应用卫星图像格式包括新一代天气雷达，CASA，GOES和SEVIRI。另一个关键的优点是，该算法通过测试所有-但最小数量的阈值确定一个最佳阈值。两个启发式建模风暴轨道：风暴质心和重叠像素。他们的算法使用了两种混合方法，并能够通过一个单一运行完成执行。分布式计算框架（例如MapReduce，Spark等）也没有被用到。

Marzban and Stumpf用神经网络（NN）来预测龙卷风。模型中一共有23个变量。除了闪电预测和云分类，所开发的NN提供了一个更可靠灵活的预测系统来统计概念，以提高性能，这是CSI的得分评估。

在[ 13 ]中所描述的一种方法，旨在在实时探测风暴和其他天气条件之间缩小技术细节和领域专家之间的差距。提出了一个更高效的领域特定的数据挖掘，因为大多数以前的方法不适合实时处理数据。传统的数据挖掘还没有适合处理连续大数据集的。建议的天气预报算法如下。首先，对整个图像进行粗略扫描处理。分组风暴集群在不同地区的基础上进行评估，哪些地区应分析第一/下一步，然后执行。精细扫描，是一种曾被使用的变异DBSCAN算法。除了昂贵计算的痛苦，该算法能处理数据的空间维度。增加时间维度的算法更多的被忽视了。

B．时空数据挖掘

几十年来，数据挖掘被广泛应用于各种应用领域。然而，直到本世纪初它才进入世界GIS。近期传播技术的进步导致了大量的地理空间和/或时间数据生成，面临的两种典型挑战是：1）现有的数据挖掘方法不能处理大规模基于位置的数据集；2）时空数据通常介绍更复杂的（例如，数据类型和结构表征）。提出的方法必须有效地解决这些挑战。

时空数据挖掘被姚建议分为五类：分割（分类、聚类、关联规则），异常检测，模式分析，总结和分类。关联规则和聚类应用于采用采矿方法的许多领域[ 15 ]。由于我们的研究更多与时空聚类相关，我们对一些时空聚类技术进行了讨论。

时空聚类将相关的划分到一组，基于一定的统计（S），来实现组内距离最小化，和组间距离最大化。轨迹模式分析，聚类方法，特别是k-均值，经常被用来作为主要的采矿步骤或预处理步骤。三技术因素在评估时空聚类方法包括：1）可扩展性的细节（例如，并行数据结构，I/O使用和优化）；2）时间维度支持；3）测量方法。

基于地理时态数据库，我们提出了几种方法挖掘轨迹和序列模式。曹等利用插值区域执行轨迹模式的挖掘任务（相对于朴素的标准规则网格）。在一种新的数据结构，即子串的树结构，提出了对大数据量的处理。设计算法时考虑了时间维。该算法考虑每个单点的轨迹聚类时的轨迹。类似的，严等还提出了一个新的数据结构，来提供更好的处理能力。该算法考虑到时间维度，提升了模式（形成，耗散和延续），并用几何对象代替点集，作为一种开采模式，以提供更强大的特定领域的计算。进行了一些实验来进行科学数据集的解释和验证。举例来说，模拟硅片（在材料科学）随着时间的推移演变。这种方法的缺点之一是，只在有限的模式下可提取。不像[ 17 ]和[ 18 ]，stolorz等人利用并行技术在超级计算机（例如，英特尔Paragon）来处理大量的数据。气旋轨迹和块特征识别系统的开发。识别过程是并行和分布式节点之间的负载均衡（有些节点可以接收更多的帧提供更有效的识别）。堆焊和聚类方法更好更快（通过降维）。由于该系统基于放大结构，提高系统的性能会产生很大的成本。在[ 21 ]所做的工作是不同于以前的三篇[ 17 ] [ 18 ] ]在所得的输出方面。黄等提出了一种挖掘事件序列模式（而非轨迹）的方法。论文中未提及可扩展性。

K-Harmonic和BIRCH是两个著名的k-均值聚类变量。这两种方法的主要贡献是消除了原始方法的限制，其中包括选择正确的k值和灵敏度的顺序输入。然而，他们都没有提到时间维度是如何处理的。在可扩展性方面，[ 20 ]没有提出加快大数据量的过程，而[ 19 ]介绍了通过I/O优化处理大规模数据处理等新树数据结构计算任何技术（CF树）、智能I/O和内存管理，通过增量单优化扫描过程中，过滤和提炼步骤。然而，一些问题仍然存在，如广泛的迭代内存重新分配，需要更好的启发式指标的性能评价和权衡。

我们在这项工作的贡献体现在两个层面：运用分布式计算技术、Apache Spark更好地协助可扩展性问题，而不是考虑一个单一事件，是一个包括更现实的模式识别形状和尺寸的频繁小时性暴风雨团。

C．风暴概念概要

在我们以前的工作中，我们概念化并提取不同方面的风暴。风暴识别系统包含了两种方法：基于CUAHSI 和基于MapReduce。雨落的数据集（多传感器降水估计、MPE）用取自nws-wgrfc（国家气象服务-西湾河预报中心）的数据，代表在一个小时的文本文件格式基于HRAP（水文雨量分析项目）标准网格坐标系统。每个文件具有四个属性，即观察时间，行数，站点ID和降水值，并按订单编号依次从西到东、从南到北依次排列。观测的覆盖范围主要包括德克萨斯和一些周边地区，共有165750个观测点。

我们把原降雨数据组成的三个不同概念风暴暴雨给出如下：

1）局部风暴：一个特定地点的风暴或局部风暴，被定义为在一定的位置的一个时间序列的降雨数据值。在一个给定的位置上，局部风暴是由一些无雨（零）降水值组成，称为跨事件时间（H），通常被设置为6小时。连续的局部风暴是那些开始（结束）时间和结束（开始）定义，本地风暴的时间是至少相隔H小时。否则，他们被视为相同的局部风暴。启动时间和结束时间必须是非零和中间值，但不能超过H小时。风暴深度和风暴持续时间被分别定义为降水值的总和与风暴的持续时间。两者的比值（风暴深度和风暴持续时间）被称为风暴强度。

2）小时性风暴：一个具体时间的风暴或小时风暴被定义为一组连续的网站和他们在某个特定的时间相应的雨量值，正交局部暴雨。任何两个有效的小时性风暴在给定的时间内不能重叠，也不是相邻点。也就是说，两组相邻点被认为是两个不同的小时风暴，如果：（1）没有从每个风暴的非零站点成员是相邻点和；2）的每一个成员在每小时风暴集有至少一个相邻点。整个网站的降水值的总和和最大值被分别称为风暴站总量和风暴中心。小时性 风暴覆盖的地点被称为风暴覆盖。风暴点总数和风暴覆盖率之间的比值称为风暴平均值。风暴的边界被定义为一个MBR（最小外接矩形）的风暴的实际形状。

3）整体风暴：整体风暴被定义为一个时间序列的重叠的小时性风暴。这种类型的风暴同时考虑位置和时间，并分析一个风暴行为。如果两个小时性风暴满足两个约束：分组窗口和空间窗口，那他们将被视为同一个风暴。分组窗口定义了最大的时间间隔，在这两个连续的每小时风暴相结合，而空间窗口定义了最小数量的共同站共享的两个小时风暴。这种定义的整体风暴，在一段时间内，假定移动到同一方向的小时性风暴是相同的风暴。风暴的整体深度定义为整个暴雨降水总量（总）时间。风暴总强度（每小时）和风暴的整体平均（每个网站）可以分别由风暴的整体深度除以风暴持续时间和风暴覆盖得出。

在下一节中，我们将在小时性风暴（空间风暴）的形状和大小的基础上，来描述一种适应k-均值聚类的集群。

III. 方法论

在本节中，我们定义了一些必要的组件，以适应数据集的空间方面，并解释了我们所提出的方法适应k-均值聚类分析。

A.太空风暴的转化

小时性的太空风暴，定义为空间内的站点集合。这些风暴呈区域性分布，例如，一些风暴可能是在南部的得克萨斯州，而另一些在北得克萨斯州。另外，在某个时间点，北德克萨斯州的风暴可能和南德克萨斯州的风暴相似。为了比较两个不同的区域的风暴，我们对它们做个简单的转化，将它们的最小边界长方形（MBR）的左坐标设为（0，0），然后将其他点相应转化。以上可以通过减少最小边界长方形的左下坐标来实现。将风暴移动到坐标系统的相同空间位置，从而更加容易去发现它们之间的相似性。在下一部分，我们将

描述杰卡德相似性来发掘两个小时性风暴的相似性。

B. 相似性度量

我们使用一套相似性度量，来发掘两个风暴之间的相似性，因为以下原因：我们的概念风暴定义为集（在一个标准的网格，HRAP），集的相似性可以捕捉风暴形状和大小的本质，这是我们的空间数据的重要特征。我们的方法采用了Jaccard相似性。Jaccard相似性将两个风暴A和B之间可以转化定义为：

相似性（A，B）= |Acap;B|（1）|Acup;B|

其中分子为两个风暴A和B之间的常见站点数，分母是他们都有独特的站点总数。如果两场风暴之间的Jaccard相似性接近1，则认为它们相似。这意味着，Jaccard相似度值越高，两个风暴越相似。此外，风暴A是类似于其他风暴B，如果两者之间的相似性大于theta;（theta;可用来缩小搜索空间，通常

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[139993]，资料为PDF文档或Word文档，PDF文档可免费转换为Word