推荐星级：
- 1
- 2
- 3
- 4
- 5
一种时间序列数据的动态密度聚类算法
资料介绍
传统的聚类算法多是针对某个时间片上的静态数据集合进行的聚类分析,但事实上大部分数据存在时间序列上的连续动态演变过程.本文对时间序列数据及其类结构的演变过程进行了分析,发现在一定条件下相邻时间片间的数据集间存在较强的关联性,并且类簇结构间则存在一定的继承性.故本文得出新的思想,在前一时间片聚类结果的基础上,通过对部分变化数据的计算和类簇结构的局部调整就有望获得对后一时间片上数据进行完全聚类相同的效果,且运算量会显著下降.基于此思想提出了一种时间序列数据的动态密度聚类算法(DDCA/TSD).仿真实验中使用6种数据集对所提出算法进行了实验验证.结果显示DDCA/TSD在保证聚类准确性的基础上相对传统聚类算法有明显的时间效率提升,并能更有效地发现数据点的属性变化及类簇结构的演变过程.
部分文件列表
| 文件名 | 大小 |
| 一种时间序列数据的动态密度聚类算法.pdf | 645K |
部分页面预览
（完整内容请下载后查看）控 制 理 论 与 应 用
Control Theory & Applications
第 36 卷第 8 期
2019 年 8 月
Vol. 36 No. 8
Aug. 2019
一种时间序列数据的动态密度聚类算法
陈 皓†, 冀敏杰, 郭紫园, 夏 雨
(西安邮电大学 计算机学院, 陕西 西安 710121)
摘要： 传统的聚类算法多是针对某个时间片上的静态数据集合进行的聚类分析, 但事实上大部分数据存在时间
序列上的连续动态演变过程. 本文对时间序列数据及其类结构的演变过程进行了分析, 发现在一定条件下相邻时
间片间的数据集间存在较强的关联性, 并且类簇结构间则存在一定的继承性. 故本文得出新的思想, 在前一时间片
聚类结果的基础上, 通过对部分变化数据的计算和类簇结构的局部调整就有望获得对后一时间片上数据进行完全
聚类相同的效果, 且运算量会显著下降. 基于此思想提出了一种时间序列数据的动态密度聚类算法(DDCA/TSD).
仿真实验中使用6种数据集对所提出算法进行了实验验证. 结果显示DDCA/TSD在保证聚类准确性的基础上相对
传统聚类算法有明显的时间效率提升, 并能更有效地发现数据点的属性变化及类簇结构的演变过程.
关键词： 时间序列数据; 数据关联性; 动态密度聚类; 类继承性
引用格式： 陈皓, 冀敏杰, 郭紫园, 等. 一种时间序列数据的动态密度聚类算法. 控制理论与应用, 2019, 36(8)：
1304 - 1314
DOI： 10.7641/CTA.2019.80976
A dynamic density clustering algorithm for time series data
CHEN Hao†, JI Minꢀjie, GUO Ziꢀyuan, XIA Yu
(School of Computing Science, Xi’an University of Posts and Telecommunications, Xi’an Shaanxi 710121, China)
Abstract: The traditional clustering algorithms are an analysis method for static data sets on a certain time slice, but
most of the data sets have a continuous dynamic evolution process on the time series. A high data correlation and cluster
structure succession between adjacent time slice are found by the analysis of the successional process on time series data
and its class structure. Consequently, based on the clustering results of the previous time slice, it is able to obtain the same
effect as the result of completely clustering data on the latter time slice through calculating part changed data and adjusting
partial cluster structure, meanwhile the whole computation will significantly decrease. Based on this idea, a dynamic
density clustering algorithm for time series data (DDCA/TSD) is proposed. In simulations, six kinds of data sets are used
to verify the proposed algorithm. The results show that DDCA/TSD has obvious time efficiency improvement compared
with the traditional clustering algorithm on the basis of the cluster accuracy. Moreover, it is effective to find the change of
data points’ attribute and the evolution of cluster structure.
Key words: time series data; data correlation; dynamic density clustering; cluster succession
Citation: CHEN Hao, JI Minjie, GUO Ziyuan, et al. A dynamic density clustering algorithm for time series data.
Control Theory & Applications, 2019, 36(8)： 1304 - 1314
1 引言
数据的特征向量, 再利用静态聚类方法进行处理[3].
此类方法缺乏对每个时间片状态以及其数据的分析,
无法挖掘出时间片之间数据的具体演变过程, 只是对
整个时间序列采取整体或者抽象的处理方法. 另一些
方法是对于每个时间片进行一次静态聚类[4]. 这种方
法可以挖掘出时间片之间数据的演变过程, 但是无法
有效利用相邻时间片间的数据进行分析, 且每次静态
时间序列数据是指按时间先后顺序排列的数据序
列, 它潜在的表达了数据内部状态随时间变化的规律.
时间序列数据分析广泛应用于生物、医疗、教育和经
济等各个领域[1], 其中聚类作为主要研究方法越来越
受到学者的重视[2]. 目前, 一些时间序列聚类算法是
将时间序列模拟为n维空间的某个点或提取时间序列
收稿日期： 2018-12-14; 录用日期： 2019-04-17.
†通信作者. Eꢀmail： ; Tel.： +86 13720400364.
本文责任编委： 孙长银.
国家自然科学基金项目(61876138, 61203311, 61105064), 陕西省教育厅自然科学专项(17JK0701), 陕西省网络数据分析与智能处理重点实验室开
放课题基金项目(XUPT-KLND(201804)), 西安邮电大学创新基金项目(103-602080016)资助.
Supported by the National Natural Science Foundation of China (61876138, 61203311, 61105064), the Scientific Research Program Funded by
Shaanxi Provincial Education Department of China (17JK0701), the Science Foundation of the Shaanxi Key Laboratory of Network Data Analysis
and Intelligent Processing (XUPT-KLND(201804)) and the Innovation Funds of Xi’an University of Posts and Telecommunications (103-602080016).
第 8 期
陈皓等： 一种时间序列数据的动态密度聚类算法
1305
聚类操作对象都是全数据集. 当数据量比较大时, 计
算量会随之增大, 时间消耗也会随之增加[5].
的算法, 它是模糊C均值(fuzzy C-means, FCM)的时
间序列推广. Izakian和Pedrycz[18]提出了对时间序列
数据进行模糊聚类的欧氏距离的增广式, 但是复杂度
比较高. 谢福鼎等[3]通过等长处理时间序列后, 基于
欧氏距离及模糊C均值聚类算法实现时间序列聚类,
计算复杂度低, 容易实现. 但存在要求时间序列长度
针对以上问题, 本文基于密度聚类过程, 提出一种
利用时间片之间的关联性, 通过局部的计算和类簇结
构调整达到全局聚类效果的动态聚类方法. 该方法充
分利用了类结构在时间序列上的继承性, 不仅能够达
到传统聚类模式的运算效果, 而且能够揭示类簇结构
的变化和每个数据点的属性在时间序列上的变化过
程, 同时显著降低整体计算量.
一致且对时间轴变化敏感等问题. 孙雅与李志华[19]
基
于动态弯曲距离提出了一种时间序列层次聚类的算
法, 但该算法相似性度量计算复杂度较高, 影响了算
法效率. 刘琴等人[20]结合滑动窗口及k-means聚类算
法提出了一种基于滑动窗口不等长时间序列的短时
间序列距离的聚类算法, 能够解决不等长时间序列聚
类的问题, 但最佳聚类个数难以确定. Shukri S等
人[21]基于一个受自然启发的元启发式算法, 能够自动
检测集群数量, 但是对高维数据聚类效果不好.
2 相关工作
根据数据和聚类的动态性, 聚类分析基本可分为
4种类型[6]：
其一是数据是静态的, 集群过程也是静态的. 典型
的如MacQueen[7]提出的k-means算法, 聚类速度快,
可以用于各种数据类型, 但初始点的选取对聚类效果
有直接影响. 针对此问题Rodriguez A等人[8]提出的类
中心都处在局部密度比较大的位置, 且距离具有比它
更大的局部密度的对象相对较远. 基于层次聚类的代
表BIRCH[9] 算法聚类效率高, 可识别噪声点, 但是不
能发现任意形状的类. Ester等人[10]针对任意形状的
类, 采用密度概念提出了基于密度的噪声应用空间聚
类(densityꢀbased spatial clustering of applications with
noise, DBSCAN)算法, 该算法能够发现任意形状并且
能够识别噪声点, 有对输入参数敏感的缺点. 秦佳睿
等人[11]则采用自动适应的半径来解决输入参数敏感
问题.
本文所讨论问题属于第4类问题. 上述研究基本是
将时间序列模拟为n维空间的某个点或者提取时间序
列数据的特征向量, 其本质依然是利用静态聚类方法
处理时间序列数据, 并没有挖掘出每个数据的变化过
程, 同时缺乏连续时间片间数据关联性的分析.
3 时间序列数据及聚类过程分析
3.1 时间序列上数据的关联性和类结构的继承性
不失一般性, 一个时间片上的静态聚类过程可描
述如下： 数据集 ξ 由 n 个点组成, ξ ={X1, X2, · · · ,
Xn}, 且每个点可用一个 d 维向量表示Xi ={Xi1,
Xi2, · · · , Xid}. 给定数据集 ξ, 算法通过找到一组簇
类集合C ={C1, C2, · · · , Ck}使得簇间结构尽可能不
同, 而簇内结构尽可能相似. 其中每个簇的质心点由
CEj表示, j = 1, 2, · · · , k. 与之不同的是, 时间序列
数据的聚类是一个连续且动态的过程, 其中两个相邻
时刻的数据及簇类变化可表示为： ti 时刻集合ξi中
ni个元素构成了ki个类. 而在ti+1时刻, 集合ξi+1中元
素数量变为ni+1且构成ki+1个类. 在两个相邻时刻间,
元素将具有消失、新增、位移或不变4种状态, 从而影
响ti+1时刻的数据集ξi+1及簇类Ci+1. 以下是上述几
种元素状态的定义：
其二是数据被视为静态数据, 但是集群的数量在
每次新的计算时可动态变化. 如张阳等人[12]通过删除
由信息动态变化而产生的冗余信息, 来减少动态聚类
过程中的干扰, 但是对时间序列中集群数量变化的情
况却不适用.
其三数据被视为动态的、随时间变化的, 但集群的
数量是固定的. Agrawal等人[13]首次提出使用离散傅
里叶变换将时间序列的时间域转换为频率域的特征
表示方法. Benítez I等人[14]基于k-means算法采用
hausdorff相似度的相似距离, 对时间序列的住宅用电
量进行动态聚类分析. 王玲等人[15]通过选择一些蕴含
重要信息的特征点, 降低时间序列维度, 但需保证原
有时间序列趋势不变.
定义 1 元素消失. 元素Xj在ti时刻有Xji ∈ξi,
而ti+1时刻有Xji+1 ∈/ ξi+1
.
定义 2 元素新增. 元素Xj在ti时刻有Xji ∈/ ξi,
其四数据是动态的且集群的数量在每次迭代中都
是动态变化的. Luczak等人[16]考虑动态时间弯曲及
扩展动态时间方法对不等长时间序列进行聚类的优
势, 提出了一种新的距离度量标准, 能够较好的通过
不同时间序列的距离度量实现时间序列的聚类. 文献
[17]利 用Haar小 波 变 换 表 示 时 间 序 列 数 据, 采 用
k-means算法和欧氏距离对新特征空间中的数据进行
聚类. 文献[11] 描述了一种称为泛函模糊C均值或
实用模糊 C 均值 (functional fuzzy C-means, FFCM)
在ti+1时刻有Xji+1 ∈ξi+1
.
定义 3 元素位移. 元素Xj在ti时刻有Xji ∈ξi,
在ti+1时刻元素Xji+1 ∈ξi+1, Xji =Xji+1
.
定义 4 元素不变. 元素Xj在ti时刻有Xji ∈ξi,
在ti+1时刻元素Xji+1 ∈ξi+1, Xji =Xji+1
.
元素的变化首先会导致类结构的变化, 从而进一
步影响两个相邻时间片上类结构的变化. 假设ti+1时
刻相对ti时刻有w1个元素不变且其概率为p1, w2个元
全部评论(0)