收 稿 日 期 ：0 1 6 - 0 汪 卫 ,教授。
一条序列， 这种序列就叫作多变量时间序列。多变量 时间序列广泛存在于金融、 传感器网络、 医疗等各种领 域。 本文旨在对这种有上千甚至上万个变量的大规模 多变量时间序列进行聚类分析。 对大规模传感器网络 多变量时间序列以天为周期进行聚类， 我们可以得到 一年中哪些天的传感器状态是相似的， 这对传感器网 络的监测和维护有着重要的意义。 对股票行情数据以 交易日为周期进行聚类， 我们可以得到一年中哪些交 易日的行情是相似的， 这可以作为投资者投资和决策 的参考依据。在已有的研究工作中， 其研究的多变量 时间序列的变量数目均很少， 在这些已有研究所使用
第 34卷第5 期 2017年 5 月
计算机应用与软件
Computer Applications and Software
Vol.34 No.5 May 2017
LS-Cluster:大 规 模 多 变 量 时 间 序 列 聚 类 方 法
郑 诚 王 鹏 汪 卫
( 复 旦 大 学 计 算 机 科 学 技 术 学 院 上 海 201203) ( 复 旦 大 学 上 海 市 数 据 科 学 重 点 实 验 室 上 海 201203)
(School of Computer Science ,Fudan University ^Shanghai 201203, China) {Shanghai Key Laboratory of Data Science ,Fudan University ^Shanghai 201203 , China)
摘 要 现有的关于多变量时间序列聚类的研究中所研究的变量规模均较少， 而现实生活又经常会出现大规 模多变量时间序列， 因此提出了 •算法， 旨在对有上万变量的大规模多变量时间序列进行聚类。首先， 将
LS-Clutei
每个时刻的多变量时间序列转化成矩形网格， 然后使用二维离散佘弦变换对其进行特征提取。接着提出了 法在人工合成数据和真实数据上都有较好的效果和可扩展性。 关键词 中图分类号 大规模多变量时间序列离散佘弦变换
4 - 0 1 。国家自然科学基金项目（ U1509213) 。郑 诚 ， 硕士生,主研领域： 时间序列， 数 据 挖 掘 。王 鹏 ， 副教授。
206
计算机应用与软件
2017 年
的数据集中， 变 量 数 目 最 多 的 是 E E G 数据集[1]， 有 64 个变量。而在现实生活中又经常会出现有上千甚至上 万变量的大规模多变量时间序列的数据， 并且变量之 间有一定的相关性。例如在大规模传感器网络、 股票 行情和大型服务器机房监控等数据中， 变量数就有可 能会达到上千甚至上万。因此有必要研究在大规模多 变 量 时 间 序 列 下 的 聚 类 方 法 。本 文 中 ， 我们提出了 L S - C lu ste i • 聚类方法， 和之前的研究工作不同， 我们主 要聚焦于处理变量数目非常多的大规模多变量时间序 列， 例如数千甚至上万个变量的多变量时间序列， 并且 方法考虑了变量之间的相关性。 首先， 将多变量时间序列中每个时刻的每个变量 的值放入矩形网格中， 使得每个时刻的数据都形成一 个矩形网格， 然后我们使用二维离散余弦变换来对矩 形网格提取特征， 得到一个特征矩阵。从一个时刻到 另一时刻的特征矩阵的变换可以看成是高维空间中的 一个向量， 我们把这种向量称为线段， 所有的线段的序 列我们称之为线段序列。从 而 ， 多变量时间序列可以 用高维空间的线段序列来表示。为了进行聚类分析， 我们提出了 L S 相似度来计算线段序列之间的相似程 度， 最后我们采用层次聚类来发现其中的模式并找出 其中的离群点。 实验环节中 ， 我们采取人工合成数据和金融数据 来验证我们的方法。在人工合成数据上的实验结果显 示我们的方法比其他的方法有更好的聚类效果和可扩 展性 。进 一 步 的 ， 我 们 在 2 0 0 8 年 上 海证券交易所的 1 1 0 支股票行情数据上进行了实验。我们发现聚类 结果和上证指数有着较高的一致性 ， 并发现了 一些离 群点， 说明了我们的方法得到了较好的聚类效果。
In the existing studies on multivariate time series clustering, the size of the variables studied is small ,and in real life , large scale multivariate time series often appear. Therefore , LZ-Cluster algorithm is pro clustering large scale multivariate time series with tens of thousandsof variables. Firstly, the each time is transformed into a rectangle grid, and then two-dimensional discrete cosine transform is used to extract features. LZ similarity is proposed to calculate the degree of similarity between feature sries. Finally , hierarchical clustering method is used to discover the patterns. The expermental results show that the proposed method has good performance and extensibility in both synthetic data and real data. K e y w o rd s Large scale Multivarate time seres Discrete cosine transform LS similarty Clusterng
LS相
似度用于计算特征序列之间的相似程度。最后， 采用层次聚类方法发现其中所蕴含的模式。实验结果显示， 该方
TP3
文献标识码
A
LS相 似 度 聚 类 DOI:10.3969/j.issn.1000-386x.2017.05.036
LS-CLUSTER： LARGE SCALE MULTIVARIATE TIME SERIES CLUSTEห้องสมุดไป่ตู้ING METHOD Zheng Cheng Wang Peng Wang Wei
A b s tra c t
〇 引 言 在现实生活中， 经常会出现同一时刻产生多个数 据值的情况， 这些数据值共同描述了当前的状态。例 如在有上千个传感器结点的大规模传感器网络中， 同 一时刻会有上千个数据产生， 这些数据共同描述了当 前传感器网络的状态。又如在金融领域中， 沪深股市 共有2 000多支股票， 在交易时间段内每一时刻就会 产生2 000多个价格， 这2 000多个价格共同描述了当 前股市的状态。 这些状态按照时间顺序排列就构成了