一个高效的多变量时间序列聚类算法

2010，46（1）。。。。K-MEANS[1]DBSCAN[2]BIRCH[3]CURE[4]STNG[5]。xit[i=12…nt=12…m]n=1Uni－variateTimeSeriesn≥2MultivariateTimeSeriesMTS。MTS、、、、、6、、、。。。、、KMTSPCA-CLUSTERMTSMTSKKMTS。1。Everitt[6]1974。1221ZHOUDa-zhuo12JIANGWen-bo2LIMin-qiang11.3000722.0500611.SchoolofManagementTianjinUniversityTianjin300072China2.ComputerCenterHebeiUni[e-mail]ringisanimportantissueindataminingresearch.MostoftheexistingalgorithmsadoptK-meansmethodtoclusterlowdimensiondatawhicharenotsuitabletoaddresstheproblemofclusteringhighdimensionalMultivariateTimeSeriesMTSdata.ThispaperproposesanefficientclusteringalgorithmforMultivariateTimeSeries—PCA-CLUSTER.ThealgorithmappliesprincipalcomponentanalysistoreducethedimensionofMTSandsubsequentlychoosestheprincipalcomponentseriesofMTStoclusterbyaK-nearestneighboralgorithm.TheoreticanalysisandexperimentalresultsshowthatPCA-CLUSTERiseffectiveandefficient.Keywordsmultivariatetimeseriesclusteringanalysisprincipalcomponentanalysis。kMTS。PCA-CLUSTERMTSMTSK。MTS。DOI10.3778/j.issn.1002-8331.2010.01.0421002－8331201001-0137-03ATP311.13theKeyTechnologiesR&DProgramofHebeiProvinceChinaunderGrantNo.05213574。1971-1965-、。2008-07-242008-10-15ComputerEngineeringandApplications137ComputerEngineeringandApplications2010，46（1）K-means。。K-means123K456。K-meansDing[7]K-meansK-means-CPkk。kkNNkMNkk。2MTS、。[8]。1X1X2θZ1=cosθX1+sinθX2Z2=-sinθX1+cosθX21Z1Z2X1X21nZ1Z2。3FrobeniusAB2MTSMA×nMB×nSVDVA=[a1a2…an]VB=[b1b2…bn]ABFrobeniusExtendedFrobeniusNormEros[9]DErosABw=2-2ni=1Σwi|aibi|姨=2-2ni=1Σwi|nj=1Σaij×bij|姨2aibinaibiaibiwni=1Σwi=1。ErosDEros。DmaxABw=ni=1Σnj=1Σwiaij-bij2姨=2-2ni=1Σwinj=1Σaij×bij姨3DminABw=ni=1Σnj=1Σwi|aij|-|bij|2姨=2-2ni=1Σwinj=1Σ|aij×bij|姨44PCA-CLUSTERMTSMTSPCA-CLUSTERMTS。4.1MTSMTS。。MTS_PCAMTS1MTS2MTS3MTSb452~4MTS6MTS。4.2K-means-CPMTSk1kc1c2…cK2aad13d24d1d2d1d2aa52~4MTS6k。θX2X1Z1Z211382010，46（1）5MTShttp//finance.sina.com.cn60000060039330093299、、、、6。PentiumIV1.4GHzWindowsXPMatlab7.1。5．1200z=2k=10PCA-CLUSTERK-meanCPU2。2PCA-CLUSTERK-mean。k。5．2PCA-CLUSTERMTS。1MTSk=10、sn=200CPU3。2MTSFrobeniusk=10、z=2CPU4。6、。PCA-CLUSTERMTS。MTSMTS2MTSPCA-CLUSTER。[1]HanJia-wei.MichelinedataminingConceptsandtechniques[M].SanFransiscoCAMorganKaufinannPublishers2000.[2]EsterMKriegelHPSanderJetal.Adensitybasedalgorithmofdiscoveringclustersinlargespatialdatabaseswithnoise[C]//SinoudisEHanJWFayyadUM.Proceedingsofthe2ndInter－nationalConferenceonKnowledgeDiscoveryandDataMiningPortland.[S.l.]AAAIPress1996226-231.[3]ZhangTRamakrishnanRLivnyM.BIRCHAnefficientdataclus－teringmethodforverylargedatabases[C]//JagadishHVMumickIS.Procofthe1996ACMSIGMODIntConfonManagementofData.MontrealACMPress1996103-114.[4]GuhaSRostogiRShimK.CUREAnefficientclusteringalgorithmforlargedatabases[C]//HaasLMTiwaryA.ProceedingsoftheACMSIGMODInternationalConferenceonManagementofData.SeattleACMPress199873-84.[5]WangWYangJMuntzR.STINGAstatisticalinformationgridapproachtospatialdatamining[C]//ProcIntConfonVeryLargeDatabasesVLDB’971997186-195.[6]JainAKDubesRC.Algorithmsforclusteringdata[M]//Prentice-HallAdvancedReferenceSeries1988.[7]DingCHeX.K-nearest-neighborindataclusteringIncorporatinglocalinformationintoglobaloptimization[C/OL]//ProcoftheACMSymponAppliedComputing.NicosiaACMPress2004584-589.http//[8]JolliffeIT.Principalcomponentanalysis[M].BerlinSpringer2002.[9]YangKShahabiC.Anefficientknearestneighborsearchformul－tivariatetimeseries[J/OL].InformationandComputation200720565-98.http//


 /s123456z20100/s1510501001502002503003PCA-CLUSTER4PCA-CLUSTERASTARM。[1].[J].2006337199-203.[2].[J].2007266119-128.[3].[J].2006610-11.[4].[J].2004411148-155.[5].[J].2005281128-135.[6]FangGangWeiZu-kuanYinQian.Extractionofspatialassoci-ationrulesbasedonbinaryminingalgorithminmobilecompu-ting[C]//IEEEInformationConferenceonInformationandAutoma－tion.[S.l.]IEEEPress20081571-1575.[7].[J].20084435168-170.[8].[J].20081052-54.[9].[J].200931195-99.111139