基于MPAA的迭代聚类算法：用于时间序列数据流的高效聚类方案

### 基于MPAA的迭代聚类算法：用于时间序列数据流的高效聚类方案 #### 1. 引言 在当今的数据处理领域，时间序列数据的聚类问题变得愈发复杂。以往的聚类算法大多适用于相对静态的数据模型，然而，许多新兴的应用场景，如股票报价、电子商务数据、系统日志以及网络流量管理等，都需要对快速变化的流式时间序列进行在线分析。 为了解决这一问题，我们提出了一种新的流式时间序列数据集聚类方法。该方法受到了Jessica Lin和Eamonn Keogh在时间序列迭代增量聚类方面工作的启发，采用了多分辨率分段聚合近似（MPAA）技术来加速聚类过程。MPAA不仅具备小波变换降维的强大剪枝能力，还能处理任意长度的查询，计算速度更快，并且支持更通用的距离度量。 我们的工作主要解决了在流式环境中应用相关思想进行时间序列聚类时面临的四个重大挑战，具体贡献如下： - **流式环境中的时间序列聚类**：流式时间序列在许多应用中十分常见，但由于数据的动态特性，传统的聚类方法不再适用。目前，针对流式时间序列聚类的研究还不够深入。 - **基于MPAA的迭代时间序列聚类**：引入了一种新颖的多分辨率PAA（MPAA）变换，以实现迭代聚类算法。 - **多级迭代聚类的停止准则**：利用Hoeffding界解决了在迭代聚类算法中确定每个节点所需级数的难题。 - **结合最近邻的时间序列聚类**：提出的在线聚类算法利用了邻域特征，显著减少了聚类构建时间并提高了聚类质量。 #### 2. 流式迭代聚类方法 ##### 2.1 MPAA - 基于降维 MPAA基于Eamonn Keogh和Yi与Faloutsos在时间序列降维表示方面的工作。其基本思想是将长度为n的时间序列 $X_i$ 表示为N维空间中的向量 $X_i = [x_{i1}, ..., x_{iN}]$，其中第i个元素的计算公式为： \[x_i = \frac{\sum_{j=(i - 1)\frac{n}{N}+1}^{i\frac{n}{N}}X_j}{\frac{n}{N}}\] MPAA方法将长度为n的时间序列 $X_i$ 划分为一系列不同分辨率N的低维信号，其中 $N \in \{1, ..., n\}$。具体操作如下： 1. 在第一级，将数据划分为N个“帧”，帧的大小不必连续且相等。 2. 计算每个帧内数据的平均值，这些平均值构成的数据向量即为降维后的表示。 3. 递归地对包含平均值的低分辨率数组应用上述两两平均过程，得到时间序列的多分辨率表示。 下面通过一个简单的例子来说明MPAA的分解过程： | 分辨率 | MPAA值 | | ---- | ---- | | 8 | 3,5,2,6,4,8,7,1 | | 4 | 4,4,6,4 | | 2 | 4,5 | | 1 | 4.5 | MPAA近似方案具有一些理想的特性，允许对解决方案进行增量计算，这对于在大型数据集和流式环境中高效运行算法至关重要。 ##### 2.2 增强的迭代聚类方法 我们的迭代聚类方法与相关工作类似，利用了MPAA的多分辨率特性。在迭代模型中，一个关键问题是确定最小观测次数，即设计一个目标函数来评估聚类结果的质量，以避免重新计算所有距离。 为了解决这个问题，我们使用了Hoeffding界。在对范围为R的实值随机变量r进行n次独立观测后，Hoeffding界确保在置信度为 $1 - \delta$ 的情况下，r的真实均值至少为 $r - \epsilon$，其中r是样本的观测均值，$\epsilon$ 的计算公式为： \[\epsilon = \sqrt{\frac{R^2 \ln(\frac{1}{\delta})}{2n}}\] 以下是增强的迭代聚类算法SI - kMeans的步骤： 1. 确定k的值。 2. 对原始数据进行MPAA分解。 3. 初始化k个聚类中心（必要时随机初始化）。 4. 计算Hoeffding界（$\epsilon$）。 5. 在MPAA表示的数据的第i级上运行k - Means算法。 6. 将第i级的最终中心作为第i + 1级的初始中心。 7. 计算第i级初始中心与第i + 1级初始中心之间的距离 $D_{center}$。 8. 分别计算第j次迭代聚类和第j + 1次迭代聚类的簇内平方误差之和的最大值，即 $E_{max}(i)$ 和 $E_{max}(i + 1)$。 9. 如果 $E_{max}(i + 1) - E_{max}(i) > \epsilon$，则退出。 10. 如果 $D_{center} > \epsilon$，则返回步骤3。 ##### 2.3 提出的流式聚类算法 流式时间序列聚类算法面临的一个关键挑战是输入序列的高插入率。为了解决这个问题，我们考虑了流式时间序列之间的强时间依赖性，引入了最近邻分析。 首先，我们定义了以下几个概念： - **相似度度量**：使用时间序列之间的相关性作为相似度度量。对于滑动窗口长度为w的两个时间序列 $T_i$ 和 $T_j$