模糊减法聚类在时间序列分段线性表示上的应用

孙达辰 张秀萍 孙常丽

（1.牡丹江医学院图书馆 黑龙江省牡丹江市 157011 2.牡丹江医学院药学院 黑龙江省牡丹江市 157011）

时间序列是一种常见且具有时间先后顺序的数据，它具有时间属性和其他变量属性。这类数据广泛存在于各个领域，如医疗心电图、气象温度气候变化、客户行为和订单消费、金融股票等，近年来，相关学者对时间序列数据的挖 掘利用进行了大量研究，在数据挖掘领域，时间序列则是数据挖掘的一个热门研究领域。时间序列具有数据量大，维数高和更新速度快等特点，导致一般的分段线性方法难以刻画原始时间序列的全局趋势特征。当前，时间序列的表示方法，主要有以下四种：基于频域的表示方法、基于奇异值分解的方法、基于符号近似聚合的表示方法和分段线性表示方法。时间序列分段线性表示方法是从原始数据中提取重要的特征点，用这些特征点连接起来的直线表示原来的时间序列，能够保留原时间序列的有效特征，并减少数据量。目前，时间序列分段表示中的两个经典算法有自顶向下的TD 方法寻找关键点和自底向上的BU 方法寻找关键点的方法，但这两种表示方法的时间复杂度较高。近年来，出现很基于重要点的分段线性算法，就是通过考察一个点的特征值中部域区间内与区间端点的比值如果超过已经设置的阈值，则认为是趋势点，或者是根据序列的中极值点和变化幅度比较大的点来得到关键点的分段线性表示方法，还有基于时态边缘算子的时间序列分段表示方法，就是根据时间序列中的特征，先计算出时间序列听时态边缘算子，进而得到时间序列的边缘点。以上的方法，直接以一维的时间序列做为研究对象，却没有充分考虑其在时间序列上的相关性。有相关文献提出将时间序列数据编码为不同类型的图像：格拉姆角场（Gramian Angular Field, GAF）和马尔可夫域（Markov Transition Fields, MTF）,实现使用图像领域的识别网络分类时间序列数据，这种方法需要计算量较大。基于以上的研究现状，本文提出了基于模糊减法聚类的时间序列分段线性表示方法。模糊减法聚类是用来估计数据库在多层矢量自回归空间中聚类个数和聚类中心位置的快速多状态数据融合算法，模糊减法聚类将每个数据点作为一个可能的聚类中心，通过设置模糊减法聚类函数，对数据信息流进行多层聚焦。

1 基于模糊减法聚类的时间序列分段线性表示方法的构建

1.1 利用模糊关系进行聚类

模糊聚类算法是无监督的聚类算法，其聚类结果是每个数据样本点对聚类中心的隶属度。模糊聚类算法由于可以利用数学方法来量化样本间的模糊关系，能提高样本分布特征描述的准确性。模糊聚类算法直接由计算样本的隶属度来进行聚类，隶属度原则：设论域 中的M 个模糊子集w1,w2,...wM，且对于每一个wi 都有隶属度函数μwi(X0)=max[μw1(X0)，μw2(X0)，...，μwM(X0)]

在实际的应用中，被识别的对象往往不是论域中的一个确定的元素，而是中的一个字集。这时，所讨论的对象不是一个元素对集合的隶属程度，而是两模糊子集间的贴近程度。

设WA，WB 是上的两个模糊子集，则期间的贴近度定义为

分别为A 和B 的内积和外积。

1.2 模糊减法聚类

普通的模糊聚类是一种局部搜索算法，如果初始值选择不当，它就会收敛到局部极小点上，所以本文选用模糊减法聚类。

模糊减法聚类将每个数据作为可能的聚类中心，并根据各个数据点周围的数据点密度来计算这个点作为聚类中心的可能性。被选为聚类中心的数据点周围具有最高的数据点密度，同时，这个数据点附近的数据点被排除作为聚类中心的可能性；在选出每一个聚类中心后，从剩余的可能作为聚类中心的数据点中，继续采用类似的方法选择下一个聚类中心。这个过程一直持续到所有剩余的数据点做为聚类中心的可能性低于某一阈值。具体算法如下：

步骤1：将样本点集合X=｛x1,x2,x3,...,xn｝中每个数据作为可能的聚类中中心z1,z2,z3,...,zn。

步骤2：根据各个数据点周围的数据点密度进行计算，最高密度数据中心的点{xk1,xk2,xk3,...,xkm}，确定为新的聚类中心{zk1,zk2,zk3,...,zkm}。这些新的聚类中心附近的数据点被排除作为聚类中心的可能性。

步骤3：从剩余的可能作为聚类中心的数据点中，重复步骤1 和步骤2，直到所有剩余的数据点做为聚类中心的可能性低于阈值d。

1.3 基于模糊减法聚类的时间序列分段线性表示方法的构建

本文在文献的启发下，为达保留原时间序列的有效特征，并减少数据量目的，对时间序列进行分段线性表示方法，本文采用模糊减法聚类从原始数据中提取重要的特征点，用这些特征点连接起来的直线表示原来的时间序列。

在利用模糊减法聚类对时间序列分段的过程中，阈值d的值越大，保留的关键点就越少，相邻关键点之间的变化，反映的趋势就越是宏观趋势；阈值d 的值越小，保留的关键点就越多，相邻关键点之间的变化，反映的趋势就越是微观趋势。

2 实验与结果分析

2.1 实验数据及实验环境

本文中的数据集选择来自不同领域的时间序列数据集：随机数数据，UCR_TS 中的worm 数据和UCR_TS 中的yoga 数据。实验环境为Windows7 64 位操作系统，处理器Intel(R)Core(TM)i5-3470CPU@3.2GHz，内存（RAM）：4.00GB。MATLAB R2016a。

2.2 实验方法及结果

以长度相同的随机数数据，UCR_TS 中的worm 数据和UCR_TS 的yoga 数据为数据集，分别进行实验。

（1）在阈值d 为0.1 的条件下，对随机数数据，UCR_TS 中的worm 数据和UCR_TS 的yoga 数据分别运行模糊减法聚类程序，图1，图2 分别展示了随机数数据，UCR_TS中的yoga 数据的运行结果。

图1：数据集为随机数，d 为0.1

图2：数据集为yoga 数据，d 为0.1

图2 中的圆圈点，是运行程序后得到的聚类中心点，也就是本文采用模糊减法聚类从原始数据中提取重要的特征点。按顺序用直线连接各个特征点，可以得到对于原始数据的分段线性表示。在阈值d 为0.1 的条件下，对于本文中的、数据点为100 个的随即数数据，得到了包括端点在内的55 个关键点；相同条件下，数据点为100 个的UCR_TS 的yoga 数据，得到了包括端点在内的22 个关键点；相同条件下，数据点为100 个的UCR_TS 的worm 数据，得到了包括端点在内的20 个关键点。

（2）在阈值d 为0.2 的条件下，对随机数数据，UCR_TS 中的worm 数据和UCR_TS 的yoga 数据分别运行模糊减法聚类程序。

在阈值d 为0.2 的条件下，对于本文中的、数据点为100 个的随即数数据，得到了包括端点在内的24 个关键点；相同条件下，数据点为100 个的UCR_TS 的yoga 数据，得到了包括端点在内的10 个关键点；相同条件下，数据点为100 个的UCR_TS 的worm 数据，得到了包括端点在内的12个关键点。

（3）在阈值d 为0.3 的条件下，对随机数数据，UCR_TS 中的worm 数据和UCR_TS 的yoga 数据分别运行模糊减法聚类程序。

在阈值d 为0.3 的条件下，对于本文中的、数据点为100 个的随即数数据，得到了包括端点在内的15 个关键点；相同条件下，数据点为100 个的UCR_TS 的yoga 数据，得到了包括端点在内的9 个关键点；相同条件下，数据点为100 个的UCR_TS 的worm 数据，得到了包括端点在内的8个关键点。

（4）在阈值d 为0.1，0.2 和0.3 的条件下，以长度为10000 随机数据为数据集，运行本方法，进行关键点的提取，验证本方法对时长时间序列的运行效率。得到的程序运行时间分别为2.768863 秒，2.660376 秒和2.602249 秒。

（5）在相同压缩率下，与基于PAA 的时间序列分段线性表示进行对比。基于PAA 的时间序列分段线性表示方法是Keogh 和Yi 等人分别提出的时间序列表示方法，用相同长度的窗口分割时间序列，每个被分割的时间序列用平均值来表示。在相同压缩率下，对于本文所用到的数据集的拟合误差如表1。

表1：数据集的拟合误差

通过对比，可以发现，相同压缩率下，本文提出的方法，都好于PAA 方法。

2.3 结果分析

通过实验结果数据对比分析，可以得出下面的结论，阈值d 越小，对时间序列运行本方法后，得以的关键点就最多，对原时间序列的压缩比数值就越大，对序列本身的微观趋势变化信息反映的就越多；阈值d 越大，对时间序列运行本方法后，得以的关键点就最少，对原时间序列的压缩比数值就越小，对序列本身的宏观趋势变化信息反映的就越多；通过阈值d 的设定，可以反映不同程度的趋势变化信息，即，可以多尺度地对原时间序列进行分段表示。另外，对于长时间序列，本方法也具有较高的运行效率。

3 结束语

本文采用模糊减法聚类从原始数据中提取重要的特征点，利用得到的特征点对原时间序列进行分段线性表示，即，基于模糊减法聚类的时间序列分段线性表示方法，该方法通过对阈值设定，可以提取出不同数量的特征点，进行完成对原时间序列的不同尺度的划分，最后，达到不能尺度的分段线性表示。在以多个不同的时间序列数据为数据集的情况下，验证了本方法的有效性。另外，本文还对长时间序列数据，在不同阈值的情况下，进行试验，验证的本方法具有较高的运行效率。