第 2 期简彩仁, 等 : 基于函数型主成分和星座图的时间序列聚类法 189 这些方法均采取特征提取再进行时间序列聚类, 所提取的特征维数较高. 本研究借鉴众多学者对时间序列聚类的研究成果, 先构造融合函数型主成分得分和星座图表示法的特征提取技术, 即先采用函数型主成分分析 (functional

Size: px

Start display at page:

Download "第 2 期简彩仁, 等 : 基于函数型主成分和星座图的时间序列聚类法 189 这些方法均采取特征提取再进行时间序列聚类, 所提取的特征维数较高. 本研究借鉴众多学者对时间序列聚类的研究成果, 先构造融合函数型主成分得分和星座图表示法的特征提取技术, 即先采用函数型主成分分析 (functional"

庵均张
7 years ago
Views:

1 第 42 卷第 2 期 2014 年 4 月福州大学学报 ( 自然科学版 ) JournalofFuzhouUniversity(NaturalScienceEdition) Vol.42No.2 Apr.2014 DOI: /isn 文章编号 : (2014) 基于函数型主成分和星座图的时间序列聚类法简彩仁, 陈晓云, 吕书龙 ( 福州大学数学与计算机科学学院, 福建福州 ) 摘要 : 通过构造融合函数型主成分和星座图的时间序列特征提取方法, 结合模糊聚类思想得到时间序列聚类的一种算法. 实验一在第一次特征提取后, 用了五种不同的方法进行对比实验, 表明该方法在时间序列聚类上效果良好 ; 实验二将该方法应用在股票时间序列上, 可以很好地区分不同行业的股票 ; 实验三用该方法指导短期投资, 可以有较好的收益率. 关键词 : 时间序列聚类 ; 函数型主成分分析 ; 星座图 ; 模糊聚类算法中图分类号 :O212;TP311;TP371 文献标识码 :A FPCAandconstelationgraph-basedtimeseriesclusteringalgorithm JIANCai-ren,CHENXiao-yun,LYUShu-long (ColegeofMathematicsandComputerScience,FuzhouUniversity,Fuzhou,Fujian350116,China) Abstract:Thispaperproposesanewclusteringalgorithm fortimeseries,whichcombinesthefuzy clusteringalgorithm andafeatureextractionmethodbasedontheintegrationoffunctionalprincipal componentsanalysisandtheconstelationgraph.inthefirstexperiment,afterthefirstfeatureextrac tion,weusefivediferentmethodstoshowthatourmethodisefectiveforthetimeseriesclustering;in thesecondexperiment,theproposedmethodisappliedinthestocktimeseries,itcanbeverygoodat discriminatingtheindustry sstockfromdiferentareas;inthelastexperiment,theproposedmethodis usedtoguideshort-terminvestmentstohaveabeteryieldrate. Keywords:timeseriesclustering;functionprincipalcomponentsanalysis(FPCA);constelation graph;fuzyclusteringalgorithm 0 引言时间序列是一种特殊的数据组织形式, 时间序列挖掘是指对信息的时间特性等进行研究, 挖掘事物中蕴含的与事件相关的重要信息, 广泛应用于知识获取金融证券等领域. 时间序列聚类作为时间序列挖掘的热点研究问题之一, 备受关注. 目前研究时间序列数据聚类的方法主要有三种 [1] : 基于原始数据的方法基于特征提取的方法基于模型的方法. 基于特征提取的方法是指, 将时间序列数据通过映射或变换法提取特征, 可以实现降维, 再结合各种聚类算法完成聚类. [2-3] 近年来, 国内外学者在应用特征提取方法研究时间序列聚类方面做了大量的工作. 郭崇慧等提 [4] 出用基于独立成分分析技术提取特征, 并用多路归一化割谱聚类方法改进 k-means 法聚类. 李迎应 [5] 用基于 DTW 的符号化时间序列聚类算法, 对降维后得到的不等长符号时间序列进行聚类. 孙旭提出基 [6] 于全局特征提取的方法等也采用这种思想.R s nen 等提出基于统计特征的时间序列聚类方法.Wang [7] 等提出基于正交特征提取的时间序列聚类方法. 此外, 小波方法 [8] PCA [9] [10] 改进 SOM 法等提取特征法也得到广泛应用, 再用欧氏距离度量, 最后用改进的 k-means 法或层次法完成聚类. 收稿日期 : 通讯作者 : 陈晓云 (1970-), 教授, 研究方向 : 数据挖掘模式识别等, c_xiaoyun@21cn.com 基金项目 : 福州大学科技发展基金资助项目 (2011-XY-19,2013-XY-20)

2 第 2 期简彩仁, 等 : 基于函数型主成分和星座图的时间序列聚类法 189 这些方法均采取特征提取再进行时间序列聚类, 所提取的特征维数较高. 本研究借鉴众多学者对时间序列聚类的研究成果, 先构造融合函数型主成分得分和星座图表示法的特征提取技术, 即先采用函数型主成分分析 (functionalprincipalcomponentanalysis,fpca) 得到得分矩阵做为第一次的特征, 接着用加权方法得到星座图从而提取低维可视化特征, 再结合模糊聚类算法实现基于特征提取的时间序列聚类方法, 最后从三个不同角度对该方法进行数据验证和实证分析. 1 基于函数型主成分的特征提取 [11] 函数型数据是以函数为表现形式的数据, 其特点是具有函数性, 时间序列明显具备这种函数性. 对观测数据样本 x(t)=(x 1 (t),x 2 (t),,x N (t)),t=1,,n, 函数型数据的主成分线性组合可表示为 : f i = ξ(t)x i (t)dt= ξ,x i (i=1,,n) (1) 其中 : 下标 i 表示第 i 个序列 ;ξ(t) 为权函数, 即函数型主成分的特征函数. 函数型数据的第一主成分权函数 ξ 1 (t) 的求解过程类似多元主成分, 即有约束条件的优化问题 [11] : { maxn -1 N [ ξ 1(t)x i (t)d] t 2 i= 1 1 s.t. [ ξ 1(t )] 2 dt= 2 ξ 1 = 类似地求解第 k 个主成分权函数 ξ k (t). 求解函数型主成分权函数可以通过基函数展开法求出 [11]. 对样本数据 x i (t) 和权函数 ξ(s) 用基函数 = ( 1, 2,, K ) 展开, 可以得到特征方程 (s) T N -1 C T CWb=ρ (s) T b. 式中 :C 为 N K 的系数矩阵 ;b 为权函数展开系数 ;K 维对称矩阵 W =,w k 1,k 2 = k1 k2 ;ρ 为特征值. 由于上式对所有 s 都成立, 所以更进一步有 N -1 C T CWb=ρb, 设 u= W 1/2 b, 所以问题转化为特征值问题 N -1 W 1/2 C T CW 1/2 u=ρu 计算出 u 后, 根据 b=w -1/2 u 计算出 b, 将 b 带入 ξ(s)= (s) T b, 得到主成分的权函数 ξ(s). 在求得权函数 ξ(s) 后, 利用式 (1) 即可求得每条曲线在权函数 ξ(s) 上的得分, 将其作为特征是可行的. 更多方法及其 R 函数可参考文献 [11-12]. 2 聚类方法 2.1 模糊聚类算法 [13] 模糊聚类算法多种多样, 本研究选用的聚类算法模型可以表述如下 : minc = k v=1 n n u r ivu r jvd(i,j) i=1 2 n u r jv u iv 0 (i=1,,n;v=1,,k) s.t. { u iv =1 (i=1,,n ) k v=1 式中 :d(i,j) 是不相似度. 用欧氏距离表示不相似度, 并取模糊系数 r=2. 该模型对异常值更不敏感, 且更容易识别非球状聚类. 2.2 高维数据聚类 [14] C.Bouveyron 提出的高维数据聚类 (HDDC) 技术是用混合高斯分布拟合密度函数来构造似然函数, 并用 EM 算法进行参数估计, 最后用极大后验概率准则确定所属的类. (2) (4) (5)

3 190 福州大学学报 ( 自然科学版 ) 第 42 卷 2.3 星座图法聚类 [15] 星座图法聚类是一种直观聚类法 : 设有 n 个 m 维的样本点 x ij (i=1,2,,n;,2,,m), 作变换 ψ ij = x ij-x j,min π (6) x j,max -x j,min 式中 :x j,max 和 x j,min 分别为特征 j 的最大值和最小值, 并确定各指标的权重 W j (,2,,m),W j 0, m W j =1, 构建坐标公式 : U i = k W i cosψ ij, V i = k W i sinψ ij (7) 当 k=m 时, 点 (U i,v i ) 为第 i 个样本最终位置, 性质相似的点聚成星座, 即可用样本间距离聚类. 2.4 聚类效果评价标准 [1] 定义假设 G 为 k 个正确分类簇组成的集合,C 为 k 个基于聚类算法形成的聚类簇组成的集合, 那么定义下式为已知分类的聚类精度指标 : Sim(G,C)= 1 k k max sim(g i,c j ) (8) i=1 1 j k 式中 :sim(g i,c j )= 2 G i C j G i + C j, 其中,. 为集合的个数, 显然 0 Sim 1,Sim 越大越好. 运行时间是衡量算法性能的重要指标, 在 R 软件中, 以 CPU 流逝时间作为时间度量指标. 3 基于 FPCA 和星座图的时间序列聚类方法样本数据经过函数型主成分分析后得到每个样本的得分向量, 维数较高或者成分损失过多, 而通过星座图变换后, 不仅信息充分考虑, 而且维数低且可视化. 为避免星座图的主观性, 用模糊聚类完成聚类, 见表 1. 表 1 基于 FPCA 和星座图的时间序列聚类方法 Tab.1 FPCA& constelationgraph-basedtimeseriesclusteringalgorithm 输入 : 时间序列样本 {x 1 (t),x 2 (t),,x N (t)},t=1,,n 和聚类簇数 k 输出 :k 个聚类簇 step1: 对时间序列样本进行函数型主成分分析, 得到 n m 得分矩阵 SCORES 及其贡献率 ; v=(v 1,,v m ), 且满足 m v i =1; i=1 step2: 将得分矩阵 SCORES 利用式 (6) 进行变换, 将变换后的数据记为 Scores; step3: 根据式 (7) 以 v=(v 1,,v m ) 为权重向量对 Scores 进行坐标变换, 得每个样本的最终位置 (U i,v i ); step4: 用模糊聚类法对所有样本点的最终位置坐标聚类. 注 :step1 中的函数型主成分得分直接用 R 软件 fda 包的函数实现, 不考虑处理细节. 在计算最终位置坐标时, 还可以得到另外一个综合指标 [15] : Ψ i = m x ij -x j,min R j W j (i=1,,n) (9) 考虑将综合指标应用到聚类过程中是很有意义的, 作为一种改进, 可以将其与坐标混合作为最后的特征, 然后再进行聚类. 4 实验分析为验证算法的效果, 总共设计了三个实验. 硬件环境 : 处理器 :Pentium(R)Dual-CoreCPUE5300@

4 第 2 期简彩仁, 等 : 基于函数型主成分和星座图的时间序列聚类法 GHz; 内存 :2.00GB; 软件环境 :Windows7 操作系统 ;R 软件, 版本 , 通过 R 编程完成. 4.1 实验一数据集对比实验用人工时间序列数据集以五种方法进行对比实验. 表 2 数据集合数据来源于 UCR 时间序列数据库, 选取 UCR 数据库中 Tab.2 Dataset 的三个公开数据集 CBF ECG SyntheticControl(SC) 进数据集名称类数长度个数行实验 ( 注 : 已剔除序列异常点 ), 预处理后见表 2. CBF 采用函数型主成分分析方法得到得分特征维数依然 ECG 是高维的, 用不同的方法进行二次降维得到二次特征, SC 最后用聚类方法对所提取的特征进行聚类, 采用五种组合方法进行计算 : 注 : 数据来源于 UCR 时间序列数据库 htp://www. cs.ucr.edu/~eamonn/time_series_data 方法 1: 函数型主成分得分特征 + 星座图 + 模糊聚类算法, 记为 FSF; 方法 2: 函数型主成分得分特征 + 高维混合模型, 记为 FHDDC( 注 : 假设聚类样本满足高斯分布 ); 方法 3: 函数型主成分得分特征 + 模糊聚类算法, 记为 FF; 方法 4: 函数型主成分得分特征 + 主成分 + 模糊聚类算法, 记为 FPF; 方法 5: 函数型主成分得分特征 + 改进星座图 + 模糊聚类算法, 记为 FMSF. 因为样本的类别属性已知, 所以用相似度指标衡量, 通过分析相似度可以比较各方法的优劣. 在相似度量 (Sim) 和运行时间两方面进行对比, 各运行 50 次取平均值, 相似度结果列于表 3, 运行时间列于表 4. 表 3 相似度量 (Sim) Tab.3 Clustersimilaritymeasure 数据集名称 Sim FSF Sim FHDDC Sim FF Sim FPF Sim FMSF CBF ECG SC 表 4 运行时间 Tab.4 Runningtime (unit:s) 数据集名称 t FSF t FHDDC t FF t FPF FMSF CBF ECG SC 从相似度 (Sim) 上分析,FSF 除了在 SC 数据集上精度不高, 在其余数据集上都能得到较好的结果 ; FHDDC 在所有数据集上得到的相似度都一般 ;FF 在 ECG 数据集上的相似度为 , 精度最高, 但在另外两个数据集上的精度不理想 ;FPF 能在 ECG SC 两个数据集上得到理想的相似度结果, 但在 CBF 上效果一般 ;FMSF 与 FSF 结果类似, 但是比 FSF 在精度上略有改进. 从运行时间上看,FF 的运行时间远比其他方法来得多,FHDDC 在类别数较多时能很好的节约时间, 而 FSF 在运行时间上优于 FPF,FMSF 比 FSF 在时间上也略有改进. 总之,FSF 能较好地在运行时间和相似度上取到平衡, 而且结果也比较合理, 而 FMSF 对 FSF 的改进, 不管在运行时间, 还是相似度 (Sim) 方面都有所改进. 4.2 实验二股票收盘价时间序列聚类选取若干上证 A 股收盘价时间序列数据进行实证分析, 以图形直观给出聚类结果. 数据为上证 9 只股票的收盘价, 在至连续交易, 共 174 个交易日,9 只股票来自 3 个不同的行业, 见表 5.

5 ２福州大学学报自然科学版第４２卷表５股票数据集Ｔａｂ５Ｄａａｓｓｆｓｋｓ股票代码股票名称所属行业股票代码股票名称所属行业浦发银行银行业７开滦股份煤炭采选业５华夏银行银行业南京银行银行业明星电力电力供水供气业昊华能源煤炭采选业７５８红阳能源电力供水供气业平煤股份煤炭采选业５文山电力电力供水供气业注数据来源于兴业证券优理宝财富平台ｈｐｗｗｗｘｙｑｍｎｘｙｑｎｄｘｈｍｌ图中图ａｂ和是３类原始收盘价时间序列图图２中图２ａ２ｂ和２是聚类结果时间序列图从聚类结果分析相同行业的股票能较好地聚集在一起更重要的是聚类结果的图形很好的将形态相似的股票聚集走势相似和波动程度相近的股票时间序列能直观聚集图原始股票时间序列图ＦｇＴｍｓｓｆｓｕｓｋｓ４３实验三图２目标股票时间序列图Ｆｇ２Ｔｍｓｓｆｄｓｎａｎｓｋｓ投资模拟实验一和实验二都是在样本类别属性已知的情况下完成实验的为了弥补样本类别属性未知的不足以代价函数确定类别个数ｈｐｘｂｂｆｕｄｕｎ

6 第 2 期简彩仁, 等 : 基于函数型主成分和星座图的时间序列聚类法 193 以在上海证券交易所交易的有色金属冶炼及压延加工业的 16 只股票的收盘价为研究对象, 时间为 ( 含 ) 以前的 161 个交易日. 经过特征提取后得到的结果列于表 6. 表 6 样本特征与标号说明 Tab.6 Charactersofsampleandsymbolsdescription 序号及股票名称 U V Z 序号及股票名称 U V Z 1 包钢稀土豫光金铅南山铝业厦门钨业鑫科材料东阳光铝广晟有色金瑞矿业江西铜业宁波富邦吉恩镍业新疆众和宝钛股份株治集团贵研铂业博威合金注 :U,V 为星座图的平面坐标,Z 为综合得分由公式 (9) 给出如图 3 所示, 以公式 (4) 为代价, 确定类别数为 3 是合适的. 三维可视是 FMSF 的优点, 其聚类的结果如图 4 所示, 其中 :1,4,10,16 为一类 ;2,5,6,7,8,9,14 为一类 ;3,11,12,13,15 为一类. 图 3 最佳类别数图 Fig.3 Bestgroupnumber 图 4 聚类结果图 Fig.4 Clusteringresult 为进一步说明 FSMF 的实用性, 进行模拟投资, 龙头股选取厦门钨业, 希望找到与龙头股走势类似的股票以便作出投资决策. 用 FMSF 将上述样本点聚成 3 类, 得到和厦门钨业聚在一类的股票有包钢稀土广晟有色博威合金. 这些股票的短期投资收益率 ( 以为基期 ), 如表 7 所示. 表 7 短期投资收益率 Tab.7 Short-term investmentrate (%) 股票名称包钢稀土广晟有色厦门钨业博威合金平均收益率注 : 数据来源于兴业证券优理宝财富平台 htp:// 实验结果表明, 就前三个交易日而言投资模拟的效果较好, 短期投资的四只股票的收益率除了博威

7 194 福州大学学报 ( 自然科学版 ) 第 42 卷合金在为负收益率以外, 都可以取得正的收益率. 从投资收益率看出, 在短期内不同的交易日的投资收益率是不一样的, 而且变化是没有规律的, 所以无法取得最好的收益, 但可以取得正收益. 而后两个交易日, 包钢稀土都是负的收益率, 而且平均收益率越来越小, 所以对于非超短期交易, 要慎重考虑该方法. 5 结语提出融合函数型主成分和星座图的特征提取方法, 并应用模糊聚类算法对时间序列进行聚类, 实验一表明该方法能较好地在运行时间和聚类相似度上取得平衡, 并得到合理的结果 ; 实验二的结果表明, 该方法能将波动相似和走势相近的股票时间序列较好地聚类 ; 实验三用代价函数解决了类别数量的不足, 是对实验二结果的进一步分析, 从相同的行业筛选出与行业龙头股走势类似的股票用于超短期投资, 且能取得较可观的短期效益. 总之, 基于函数型主成分和星座图的时间序列聚类方法的应用效果达到研究预期, 且具备较强的实用性, 拥有可扩展性. 在探讨基于特征提取研究时间序列聚类方法中, 本研究所提方法存在一些不足 : 降维效果视函数型主成分个数而定, 尚无法确定最合适的个数 ; 函数型主成分分析中的参数优化降维特征保持以及如何将所提取的特征与各种聚类方法的有效融合. 这些不足将成为进一步研究的课题. 参考文献 : [1]LiaoTW.Clusteringoftimeseriesdata-asurvey[J].PaternRecognition,2005,38: [2] 郭崇慧, 贾宏峰, 张娜. 基于 ICA 的时间序列聚类方法及其在股票数据分析中的应用 [J]. 运筹与管理,2008,17(5): [3] 郭崇慧, 苏木亚. 基于独立成分分析的时间序列谱聚类方法 [J]. 系统工程理论与实践,2011,31(10): [4] 李迎. 一种基于 DTW 的符号化时间序列聚类算法 [J]. 微型机与应用,2011,30(18):7-9. [5] 孙旭. 时间序列全局特征聚类分析方法及其应用 [J]. 统计教育,2009,114(3): [6]R s nent,kolehmainenm.featurebasedclusteringforelectricityusetimeseriesdata[j].adaptiveandnaturalcomputing Algorithms,2009,5495: [7]WangXZ,LopesL.Orthogonalfeaturelearningfortimeseriesclustering[J].LectureNotesinComputerScience,2011, 6676: [8]VlachosM,LinJ,KeoghE,etal.Awaveletbasedanytimealgorithmfork-meansclusteringoftimeseries[C]//Proceedings ofthethirdsiam InternationalConferenceonDataMining,2003:1-3. [9]ShawCT,KingGP.Usingclusteranalysistoclasifytimeseries[J].PhysicaD:NonlinearPhenomena,1992,58: [10]OwsleyLM D,AtlasLE,BernardGD.Self-organizingfeaturemapsandhiddenMarkovmodelsformachine-toolmonito ring[j].ieeetranssignalproces,1997,45(11): [11]RamsayJO,SilvermanBW.Functionaldataanalysis[M].2nded. 影印版, 北京 : 科学出版社,2006. [12]RamsayJO,HookerG,GravesS.FunctionaldataanalysiswithRandMATLAB[M].NewYork:SpringerScience+Busi nesmedia,2009. [13]KaufmanL,RouseeuwPJ.Findinggroupsindata:anintroductiontoclusteranalysis[M].NewYork:Wiley,1990. [14]BouveyronC,GirardS,SchmidC.High-dimensionaldataclustering[J].ComputStatDataAnal,2007,52(1): [15] 洪文学, 李昕, 徐永红, 等. 基于多元统计图表示原理的信息融合和模式识别技术 [M]. 北京 : 国防工业出版社, ( 责任编辑 : 杨青 )

自然科学版预处理视盘粗定位视盘垂直坐标的粗定位视盘水平坐标的粗定位

自然科学版预处理视盘粗定位视盘垂直坐标的粗定位视盘水平坐标的粗定位自然科学版文章编号视网膜图像中视盘的快速自动定位方法赵晓芳林土胜李碧摘要基于眼底视网膜血管的分布结构及视盘本身的特点提出一种快速自动定位视盘的方法首先根据视网膜血管的网络分布结构大致定位视盘的垂直坐标然后根据视盘的亮度信息及视盘与血管的关系来定位视盘的水平坐标最后把视盘限定在以粗定位的视盘为中心的一个小窗口内用变换精确定位视盘中心该方法不需要事先分割视网膜血管也不需要对算法进行训练