一种基于关键点的时间序列聚类算法

第３９卷第３期２０１２年３月

计算机科学

Ｃｏｍｐｕｔｅｒ

Ｓｃｉｅｎｃｅ

Ｖ０１．３９Ｎｏ．３

Ｍａｒ

２０１２

一种基于关键点的时间序列聚类算法

’

谢福鼎１李迎２孙岩２张永２大连１１６０２９）１

（辽宁师范大学城市与环境学院（辽宁师范大学计算机与信息技术学院大连１１６０８１）２

摘要基于关键点技术，提出了一种新的时间序列聚类方法。算法首先寻找时间序列的关键点，将关键点序列进行等维处理后，通过计算关键点序列的相似性构造复杂网络，最后通过复杂网络的社团划分，实现时间序列的聚类。实验结果表明，在时间序列聚类过程中，本方法不仅可以有效降低时间序列的维数，加快聚类的速度，而且可以得到理想的聚类结果。关键词

时间序列，降维，关键点，复杂网络，聚类

文献标识码Ａ

ＣｌｕｓｔｅｒＡｌｇｏｒｉｔｈｍｆｏｒＴｉｍｅＳｅｒｉｅｓＢａｓｅｄ

ＸＩＥＦｕ－ｄｉｎ９１

ＬＩＹｉｎｇ产ＳＵＮＹａｎ２

中图法分类号ＴＰ３１１

ｏｎ

ＫｅｙＰｏｉｎｔｓ

ＺＨＡＮＧ

Ｙｏｎ酽

（ＳＣｈｏｏＩｏｆＵｒｂａｎａｎｄ

ＥｎｖｉｒｏｎｍｅｎｔａｌＳｃｉｅｎｃｅ，ＬｉａｏｎｉｎｇＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｄａｌｉａｎ１１６０２９，Ｃｈｉｎａ）１

（ＤｅｐａｒｔｍｅｎｔｏｆＣｏｍｐｕｔｅｒａｎｄＳｃｉｅｎｃｅＴｅｃｈｎｏｌｏｇｙ，ＬｉａｏｎｉｎｇＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｄａｌｉａｎ１１６０８１，Ｃｈｉｎａ）２

ＡｂｓｔｒａｃｔＢａｓｅｄ

ｏｎ

ｋｅｙｐｏｉｎｔｔｅｃｈｎｏｌｏｇｙ，ａｎｅｗｍｅｔｈｏｄｆｏｒｔｉｍｅｓｅｒｉｅｓｃｌｕｓｔｅｒｗａｓｐｒｏｐｏｓｅｄ．Ｔｈｅｋｅｙｐｏｉｎｔｓｆｏｒｅａｃｈ

ｔｉｍｅｓｅｒｉｅｓｗｅｒｅｆｉｒｓｔｆｏｕｎｄ，ａｎｄｔｈｅｎｔｈｅｃｏｍｐｌｅｘｎｅｔｗｏｒｋｗａｓｃｏｎｓｔｒｕｃｔｅｄｂｙｃａｌｃｕｌａｔｉｎｇｔｈｅｓｉｍｉｌａｒｉｔｙｂｅｔｗｅｅｎｋｅｙ

ｐｏｉｎｔｓｅｒｉｅｓａｆｔｅｒｔｈｅｙｗｅｒｅ

ｅｑｕｉｄｉｍｅｎｓｉｏｎａｌ．Ａｔｌａｓｔ，ｔｈｅｃｌｕｓｔｅｒｉｎｇｔｉｍｅｓｅｒｉｅｓｗｅｒｅｉｍｐｌｅｍｅｎｔｅｄ

ｂｙｐａｒｔｉｔｉｏｎｉｎｇｔｈｅ

ｃｏｍｐｌｅｘｎｅｔｗｏｒｋｉｎｔｏｃｏｍｍｕｎｉｔｉｅｓ．Ｔｈｅｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｅｄｉｍｅｎｓｉｏｎｓｏｆｔｉｍｅｓｅｒｉｅｓａｎｄｔｈｅｃｏｎｓｕｍｐ—

ｔｉｏｎｏｆｃｏｍｐｕｔｉｎｇ

ｔｉｍｅ

ｃａｎ

ｂｅｅｆｆｅｃｔｉｖｅｌｙｒｅｄｕｃｅｄｂｙｔｈｅｐｒｏｐｏｓａｌ．Ｆｕｒｔｈｅｒｍｏｒｅ，ｔｈｅ

ｄｅｓｉｒｅｄｃｌｕｓｔｅｒｒｅｓｕｌｔｉｓｏｂｔａｉｎｅｄ

ｗｈｅｎａｐｐｌｙｉｎｇｔｈｉｓｍｅｔｈｏｄｔｏｃｌｕｓｔｅｒｓｏｍｅｐｒａｃｔｉｃａｌｄａｔａ．Ｋｅｙｗｏｒｄｓ

Ｔｉｍｅ

ｓｅｒｉｅｓ，Ｒｅｄｕｃｔｉｏｎ

ｄｉｍｅｎｓｉｏｎ，Ｋｅｙｐｏｉｎｔ，Ｃｏｍｐｌｅｘ

ｎｅｔｗｏｒｋ，Ｃｌｕｓｔｅｒ

１

引言

时间序列是一类重要的数据对象，在经济、气象等许多领

题，如关键点提取之后，时间序列由原来的等长序列变为了不等长序列，在度量时间序列相似性时则受到了约束，因为此时无法利用计算等长序列相似性与聚类的方法。

本文提出了一种新的基于关键点技术的时间序列聚类方法，它对降维后得到的不等维关键点序列进行局部等维处理，能够实现非等长关键点序列的相似性度量与聚类。算法首先将时间序列利用关键点提取方法进行降维，利用本文方法将不等维的关键点序列进行局部等维，再用欧氏距离进行相似性度量。其次，利用所得到的相似度矩阵构造复杂网络；最后利用网络的划分结果，实现时间序列的聚类。本文通过两组实验，证明此方法在序列降维、相似性度量和聚类准确性上都有比较好的效果。此方法的另外一个优点是：在关键点序列局部等维之后，序列的相似性度量和聚类不再受距离公式和聚类方法的约束，拓展了基于关键点技术的时间序列聚类方法。比较试验结果说明，本文方法在计算准确率和空间存储上也有较大的改善。

域都大量存在。对这些数据进行分析，可以揭示事物变化和发展的规律，为科学决策提供依据。如何分析和处理这些海量的时间序列数据，并从中发现一些事先未知的、有价值的信息，正受到越来越多研究者的关注和重视。由于这些海量数据序列具有短期波动频繁、大量噪声干扰以及非稳态等特点，因此直接在原始时间序列上进行相似性查询［１’２］、分类和聚类［３｜、模式挖掘［４’５３等工作，不但会造成存储和计算效率低下，而且会影响算法的准确性和可靠性，从而难以获得满意的结果。近年来，时间序列的数据挖掘、知识发现、预测、相似性搜索等问题已经成为一个研究热点，主要研究工作包括降维、特征提取、相似性度量、相似性搜索等。

关键点选择算法ＫＰＳｅｇｍｅｎｔａｔｉｏｎ（ｋｅｙｐｏｉｎｔｓｓｅｇｍｅｎｔａ—ｔｉｏｎ）［６］是一种有效的时间序列降维方法。该方法将时间序列中重要的信息点全部提取出来，有效地去除了时间序列中的噪声与重要性小的数据点。这样不仅加快了对时间序列处理的速度，节省了处理时间与存储空间，而且处理问题的准确率还有所提高。但时间序列降维之后，也带来了另外一些问

到稿日期：２０１１—０４—１１返修日期：２０１１—０６—３０

２相关知识

２．１关键点提取

作为时间序列趋势变化的分界点，关键点对数据序列的

本文受国家自然科学基金（１０７７１０９２），辽宁省博士启动基金（２００８１０７９）资助。

谢福鼎（１９６５一），男，博士，教授，ＣＣＦ会员，主要研究方向为人工智能、数据挖掘；李迎（１９８６一），女，硕士，主要研究方向为人工智能、数据挖掘；孙岩（１９７４一），女，博士，副教授，主要研究方向为数据挖掘；张永（１９７５一），男，博士，副教授，主要研究方向为智能计算、可信计算。

万方数据

１５７

第1页下一页