基于ICA的时间序列聚类方法及其在股票数据分析中的应用
第17卷 第5期
2008年10月
运 筹 与 管 理OPERATI O NS RESE ARCH AND MANAGE ME NT SC I E NCE Vol . 17, No . 5Oct . 2008
基于I C A 的时间序列聚类方法及其在
股票数据分析中的应用
郭崇慧, 贾宏峰12
(1. 大连理工大学系统工程研究所, 辽宁大连, 辽宁大连116024)
摘 要:, 通常由于时间序列数据的特殊结构, 导致一。本文提出了一种基于独立成分分析与改进k 2均值算法相结合的, , 然后利用改进k 2均值聚类算, 从而得到了一种新的基于特征的时间序列聚类方法。为了验证该方法的有效性和可行性, 将其应用于实际的股票时间序列数据聚类分析中, 取得了较好的数值结果。
关键词:多元统计分析; 时间序列聚类分析; 独立成分分析; 股票数据
中图分类号:N945. 11 文章标识码:A 文章编号:100723221(2008) 0520120205
T i m e Ser i es C luster i n g Ba sed on I CA for Stock Da t a Ana lysis
G UO Chong 2hui , J I A Hong 2feng , Z HANG Na
(1. Institute of Syste m s Engineering, D a lian U niversity of Technology, D alian 116024, China; 2. D epart m ent of A pplied M athe m atics, D alian U niversity of Technology, D alian 116024, Ch ina )
Abstract:Ti m e series clustering is an i m portant task in ti m e series data m ining . Compared t o traditi onal cluste 2ring p r oble m s, ti m e series clustering poses additi onal difficulties . The unique structure of ti m e seriesmakesmany traditi onal clustering methods unable t o app ly directly . This paper p resents a novel feature 2based app r oach t o ti m e series clustering, which first converts the ra w ti m e series data int o feature vect ors of l ower di m ensi on by u 2sing I CA alg orith m , and then app lies a modified k 2means algorithm t o the extracted feature vect ors . Finally, t o validate effectiveness and feasibility of the p resented method, we use it t o analyze the real world st ock ti m e series data and achieve reas onable results .
Key words:multivariate analysis, ti m e series clustering analysis, independent component analysis, st ock data 1220 引言
时间序列是一种重要的高维数据类型, 它是由客观对象的某个物理量在不同时间点的采样值按照时间先后次序排列而组成的序列。在科学、工程和商业领域具有广泛应用。如:股票市场每天的股票收盘价格数据、每季度乘坐某次航班的旅客数、电话公司每小时的话务量等都是时间序列数据。分析时间序列的目的就是利用客观对象本身的动态时间序列去分析、研究和预测客观对象未来的变化规律。近年来, 对于时间序列数据的分析与挖掘激发了越来越多的研究人员的研究热情
收稿日期:08202218
基金项目:国家自然科学基金资助项目(10571018; 70431001)
作者简介:郭崇慧(19732) , 男, 博士, 副教授, 博士生导师, 主要研究方向:系统优化方法, 数据挖掘与机器学习。贾宏峰(19822) , 男, 硕士研究生, 研究方向:独立成分分析。[1~3]。时间序列聚类分析可以有效提
第5期 郭崇慧, 等:基于I CA 的时间序列聚类方法及其在股票数据分析中的应用
供数据中的重要信息, 是时间序列数据挖掘中的重要任务之一
在类间相似性最小[5, 6][4]121。聚类是无指导学习的一种方法, 其目的是通过辨识数据间的结构特征, 使得数据在类内相似性最大、。文[1]把对静态数据的聚类方法分为五种, 即划分聚类、层次聚类、基于密度的聚
[4]类、基于网格的聚类和基于模型的聚类。由于时间序列数据与静态数据有着极大的不同, 故对其进行聚类分析有着很大的复杂性。近年来, 涌现出许多时间序列聚类方法, 这些时间序列数据聚类方法大体上
可以分为三种, 即基于原始数据的聚类、基于特征的聚类和基于模型的聚类。其中后两种方法的核心思想是把时间序列数据转化为静态的特征数据或者是模型参数, 聚类任务。, , 已经提出了多种基于特征的时间序列数据聚类方法, 知重要点[10][][8]、互相关函数[9]、感、时域-频域表示
[13][11]、小波变换[12]独立成分分析(I ndependent 是信号处理领域在20世纪90年代发展起来的一种新的统计方法, eigend 将I CA 的研究推广到金融领域后, I CA 用在金融数据方
[14]。文[15]将I CA 应用于分析同一连锁店中若干商店的现金流转, 找到了
[16]影响商店现金流量的一些公共基本因素, 并尝试结合自组织映射模型来发现序列之间的相似性。文
归模型的效果要好。将I CA 与自回归模型相结合用于金融时间序列预测, 数值结果表明, 利用I CA 预测时间序列比直接利用自回
I CA 可以看成是主成分分析和因子分析的拓展。但是I CA 是一项更强有力的技术, 当经典方法完全失效时, 它仍然可能找出支撑观测数据的内在因子或源[13]。针对股票收益时间序列数据的聚类分析问题, 本文提出了一种基于I CA 与改进k 2均值算法相结合的时间序列聚类算法, 其基本思想是首先利用I CA 对时间序列数据进行特征提取, 然后利用一般的划分聚类算法完成对时间序列特征数据的聚类分析。在聚类分析中, k 2均值算法是一种常用的基于划分的聚类算法, 其优点是简单、快速、有效, 但缺点也十分明显, 即k 个初始聚类中心的选取对聚类结果具有较大的影响, 从不同的初始聚类中心出发, 将得到不同的聚类结果, 且准确率也高低不一, 因此如何选择初始聚类中心就成为影响最终聚类结果的重要因素。为了完成对特征数据的聚类, 本文提出了一种改进的k 2均值算法, 通过合理选取初始聚类中心, 达到了更好的聚类效果。因此对于原始时间序列数据, 可以利用I CA 方法首先提取静态特征数据, 然后利用本文所提出的改进k 2均值算法对所提取的静态特征数据进行聚类, 从而完成了对原始时间序列数据的聚类, 由此便得到了一种新的基于I CA 的时间序列聚类方法。
1 基于I CA 的时间序列聚类分析方法
1. 1 I CA 简介
I CA 源于盲源分离(盲源分离指的是在源信号和传输通道参数未知的情况下, 仅由观测到的信号恢复出源信号的各个独立成分的过程) 中经典的鸡尾酒会问题, 即在多个人的说话声相互混叠的情况下, 将各
T 个人的语音单独分离出来。I CA 假设存在n 个相互统计独立的源信号s (t ) =[s 1(t ) , s 2(t ) , …, s n (t ) ],
T 观测信号x (t ) =[x 1(t ) , x 2(t ) , …, x n (t ) ]是源信号各分量的线性混合, 即
x (t ) =A s (t ) (1)
其中A ∈R
T n ×n 是未知非奇异混合矩阵。I CA 的实质是在无先验知识的前提下寻求分离矩阵T T n ×n W =(w 1, …, w n ) ∈R , 进而得到
y (t ) =W x (t ) (2)
T 其中y (t ) =[y 1(t ) , y 2(t ) , …, y n (t ) ], 且使得y (t ) 中的各分量尽可能相互统计独立, 从而获得独立成分
的估计, 即y (t ) =^s (t ) , 因此它可以分析隐藏在现象背后的深层次原因。
由于独立成分正是隐藏在现象背后深层次的公共因素, 故可以认为其权重(即混合矩阵) 代表了时间序列的特征, 利用对权重的聚类来代替对原始时间序列数据的聚类, 可以大大减少计算量。本文采用独立
122运 筹 与 管 理 2008年第17卷
[13]成分分析中经典的FastI CA 算法来得到混合矩阵
n , 其步骤如下步骤1 中心化和白化观测数据x (t ) , 得到z (t ) 。步骤2 给定w i ∈R , i =1, …, n 的初值, 使其范数为1, 如步骤4正交化矩阵W 。
(w i z ) }w i , 其中g 是根据数据的高斯性选定的步骤3 对每个i =1, …, n, 令w i ←E{zg (w i z ) }-E{g ′T T
非线性函数。
步骤4 对称正交化矩阵W
W ←(WW ) T -2W
步骤5 如果不收敛, 返回步骤3。
1. 2 改进的k -均值聚类算法
将一群物理的或抽象的对象, , 其中相似的对象构成一组, 这一过程称为聚类过程。一个聚类, , 不同聚类中对象通常是不相似的。, 使得数据在类内相似性最大、k 2均值算法是聚类分析算法中比较流行的一种算法, 但此算法的一个重要缺陷是算法对初始聚类中心过于敏感。本文提出了一种改进的k 2均值算法对利用I CA 得到的混合矩阵W 进行聚类, 该算法首先利用层次算法得到一组初始聚类中心, 这样就优化了初始聚类中心的选择。算法具体步骤如下:
输入 聚类的数目k 和包含n 个对象的数据矩阵W ;
输出 k 个集合并且使集合内平方误差最小。
步骤1 初始化:R 0={wi , i =1, …, n};P 0=P (W ) ; T =0, 其中P (W ) 代表从W 推导出的n ×n 邻接矩阵。步骤2 重复执行下列步骤:t =t +1; 合并R t -1中距离最近的两个类集得到R t ; 从P t -1利用完全连通算法中的矩阵更新算法得到邻接矩阵P t 。
步骤3 直到形成聚类R n -k , 即所有的向量合并到k 个聚类中。
步骤4 计算以上所得k 个聚类的中心, 作为改进k -均值算法的初始聚类中心。
步骤5 利用步骤4所得的k 个初始聚类中心, 利用经典的k -均值算法对混合矩阵W 进行聚类。综上所述, 利用独立成分分析中的FastI CA 算法与上述改进的k -均值聚类算法相结合即得到了基于独立成分分析的时间序列聚类分析方法。
2 基于I CA 的时间序列聚类方法在股票数据分析中的应用
当今中国经济活动中, 股票已经成为百姓投资的热点。但股市中机遇与风险并存, 因此有必要对中国股票市场的波动特征进行分析。但传统的股票分析方法有很多缺点, I CA 作为揭示隐藏在数据背后的深层次原因的有效手段, 能正确分析出影响股票走势和股票受益的各个因素, 非常适合于这方面的分析有效性和可行性, 下面将其应用于实际的股票时间序列数据聚类分析中。
2. 1 股票收益时间序列的分布[17]。股票收益数据是典型的时间序列数据, 为了验证本文所提出的基于独立成分分析的时间序列聚类方法的
本文从s ohu 网财经板块[18]逐一提取股票截至2007年10月1日的前200个共有交易日的K 线数据,
[19]然后按收盘价得到时间序列数据库供分析所用。假设p (t ) 是股票t 个交易日的收盘价, 取不同的时间间隔, 可以分别得到日线收盘价序列和周线收盘价序列。用d (t ) 表示收益序列, 则d (t ) 可如下定义
d (t ) ln p (t ) -ln p (t -1) ,
0, t >1t =1(3)
2假设d (t ) 服从密度函数为N (0, δ) 的高斯分布, 则其特征函数为
于低风险出现的概率, 因此可假定δ为一个随机变量, 服从参数为λ的指数分布。于是得到混合特征函数
2
第5期 郭崇慧, 等:基于I CA 的时间序列聚类方法及其在股票数据分析中的应用
它是Lap lace 分布的特征函数, 对应的密度函数为
λexp (-λ|t |) f (t ) =0. 5
同时, 由文[19](5) 可知大多数股价收益服从这种超高斯分布, 即不满足高斯分布。这就证明了I CA 用于股票走势分析的可能性。
2. 2 数值实验及实证分析
本文进行数值实验所选取40支股票均取自s ohu [18]1. 中国石化; 2. 三峡水利; 3. 马钢股份; 4上海能源; 5. 四川长虹; 6. 上海汽车; 7. ; 8. 9. 中青旅; 10. 邯郸钢铁;
11. 东风汽车; 12华夏银行; 13民生银行; 14. . . 中原高速; 17. 上海电力; 18. 济南钢铁; 19. 中海发展; 20. 三一重工; 21. 22. ; 23哈飞股份; 24. 夏新电子; 25. 新疆天业;
26. 国能集团; 27. 29. ; 30. 波导股份; 31. 重庆啤酒; 32. 四维控股; 33. 中国船舶; 34. . ; 36. 建发股份; 37. 华升股份; 38. 沈阳新开; 39. 武汉控股; 40. 江苏吴中。
首先, 用40×200的矩阵表示这40支股票的历史数据, 将其输入到FastI CA 的程序中去, 经过中心化, 白化, PCA 降维(精度为0. 77) 和I CA 分析, 得到了40×5的混合矩阵; 其次利用改进的k 2均值算法对得到的混合矩阵进行聚类, 得到的聚类结果为将原股票时间序列聚成了8类, 其结果如下(为了简便, 只写本文提供的股票代号) :
第一类:1, 3, 12, 13, 15, 18, 22;
第二类:14, 40;
第三类:4, 5, 16, 21, 27, 29, 39;
第四类:9, 17, 19, 31, 33, 36;
第五类:2, 11, 23, 24, 25, 26, 30, 32, 37;
第六类:6, 7, 10, 28;
第七类:8, 34, 35, 38;
第八类:20
。
图1 同类中的股票走势 图2 不同类中的股票走势
由图1和图2容易看出, 相同类中的股票具有相似的走势, 而不同类中的股票则差别很大。下面将属于不同类别的有代表性的8支股票(如图2所示) 进行独立成分分析, 以进一步揭示隐藏在数据背后深层次的原因。利用的8矩阵表示这8支股票的历史数据, 将其输入到FastI CA 的程序中去, 经过中心化, 白化和I CA 分析, 得到了的混合矩阵(即独立成分) , 如图3所示。
124运 筹 与 管 理 2008年第17卷 确定性时序模型中假设时间序列的变化
形式是由长期趋势、季节变动、循环变动和不
[20]规则变动四部分叠加或耦合而成。利用确
定性时序模型对图3中的独立成分进行分析
与解释, 可以得到如下的几个主要因素:第1
个独立成分和第4个独立成分反映了原股票
序列的循环运动, 第2个独立成分和第3个独
立成分反映了原股票序列的长期趋势, 第5个
独立成分和第8个独立成分反映了原股票序
列的季节变动, 第6个独立成分和第7个独立
成分反映了原股票序列的不规则变动。影响
股市的因素是错综复杂的, 列因素综合作用的结果, 先验知识的差异, 。
3 结束语图3 独立成分
本文提出了基于独立成分分析的时间序
列聚类分析方法, 它有效地利用了独立成分分析与聚类分析的优点, 使得时间序列的聚类变得简单易行, 提高了数据分析与信息处理的效率。在此基础了, 把该方法用于股票收益时间序列数据分析中, 通过“FastI CA 2改进k 2均值算法2FastI CA ”的方法对股票收益时间序列数据首先利用独立成分分析进行特征提取, 然后对特征数据进行聚类分析, 最后利用聚类分析结果进一步完成独立成分分析, 得到了较好的效果。由于一般的时间序列数据都具有高维特性和高噪声特性, 因此有必要更加深入地研究各种基于特征的时间序列数据聚类方法。
参考文献:
[1]Han J, Ka mberM. Data m ining:concep ts and techniques, second editi on[M].San Francisco:Morgan Kauf mann, 2006.
[2]Dunha m M H. 数据挖掘教程[M].郭崇慧等译. 北京:清华大学出版社, 2005.
[3]Keogh E, Kasetty S . On the need for ti m e series data m ining bench marks:a survey and e mp irical de monstrati on [J ].Data
M ining and Knowledge D iscovery, 2003, 7(4) :3492371.
[4]L iao T W. Clustering of ti m e series data:a survey[J ].Pattern Recogniti on, 2005, 38:185721874.
[5]王实, 高文. 数据挖掘中的聚类方法[J ].计算机科学, 2000, 27(4) :42245.
[6]Theodoridis S, Koutr ou mbas K . Pattern recogniti on[M].Third Editi on . Ne w York:Acade m ic Press, 2006.
[7]W il pon J G, Rabiner L R. Modified k 2means clustering algorith m for use in is olated word recogniti on[J ].I EEE Transacti ons
on Acoustics, Speech and Signal Pr ocessing, 1985, 33(3) :5872594.
[8]Sha w C T, King G P . U sing cluster analysis t o classify ti m e series[J ].Physica D, 1992, 58:2882298.
[9]Goutte C, Toft P, Rostrup E . On clustering F MR I ti m e series[J ].Neur oi m age, 1999, 9(3) :2982310.
[10]Fu T 2C, Chung F 2L, Ng V, Luk R. Pattern discovery fr om st ock ti m e series using self 2organizing map s[A].I n:K DD 2001
Workshop on Temporal Data M ining[C ], San Francisco, 2001, 27237.
[11]Owsley L M D, A tlas L E, Bernard G D. Self 2organizing feature map s and hidden M arkov models f or machine 2t ool monit oring
[J ].I EEE Transacti ons on Signal Pr ocessing, 1997, 45(11) :278722798.
[12]V lachosM , L in J, Keogh E, Gunopul os D. A wavelet 2based anyti m e algorith m for k 2means clustering of ti m e series[A].I n:
Pr oceedings of the Third SI A M I nternati onal Conference on Data M ining[C ].San Francisco, 2003.
[13]Hyvarinen A, Karhunen J, O ja E . I ndependent Component Analysis[M].Ne w York:John W iley, 2001.
[14]Back A D, W eigend A S . A first app licati on of independent component analysis t o extracting structure fr om st ock returns[J ].
I nternati onal Journal on Neural Syste m s, 1998, 8:4732484.
[15]Kiviluot o K, O ja E . I ndependent co mponent analysis f or parallel financial ti m e series [A].I n:Kearns M, S olla S, Cohn D
(Eds ) . . Pr oceedings of the Fifth I nternati onal Conference on Neural I nf or mati on Pr ocessing[C].M I T Press, 1998, 2:8952898.
[16]Malar oiu S, Kiviluot o K, O ja E . Ti m e series p redicti on with independent component analysis[A].I n:Tonkes E, Tan C,
Sugden S, Ku mar K (Eds . ) . Pr oceedings of the I nternati onal conference on advanced invest m ent technol ogy [C ].Gold Coast, Australia, 2000.
[17]陈玉山, 席斌. 独立成份分析方法在股票分析中的应用[J ].计算机工程与设计, 2007, 28(6) :147321476.
[18]搜狐财经[E B /OL].htt p://business. s ohu . com /st ock . sht m l
[19]Tsay R S . Analysis of financial ti m e series, second editi on[M].W iley 2I nterscience, 2005.
[20]马超群, 兰秋军, 陈为民. 金融数据挖掘[M].北京:科学出版社, 2007.