4、几种主要分割算法的缺点，我们研究出了一种新的方法。滑动窗口算法的主要问题是他不能查看历史数据，对它的离线部分缺乏总体观。自底向上和自上而下方法能得出较好的结果，但是是离线的，而且需要最整个数据集进行扫描。这是不切实际。因为在数据挖掘背景下，数据可以达到TB级别或者以持续不断的数据流形式输入。因此我们提出一种新的方法，它同时保留了滑动窗口的在线特性以及自底向上算法的优越性。我们给这种算法取名叫滑动窗口自底向上算法。II4.1滑动窗口自底向上分割算法滑动窗口自底向上算法保留一个小的缓冲区，缓冲区的大小需要一开始设定以便有足够的数据来创建大概56个分段。自底向上应用于缓冲区的数据，
5、最左端的分段被报告出来。己经被报告过的数据将从缓冲区删除，然后读入更多的数据点。数据点读入的数量取决于输入数据的结构。这个过程由基于滑动窗口算法的Best_Line函数实现。然后在缓冲区中，对这些数据点再使用自底向上算法。只要有数据到达，就会不断重复上述步骤。这个算法的灵感源于此：Best_line函数找到符合一个使用滑动窗口的分段并把它放入缓冲区。当数据通过缓冲区时，再对它们使用自底向上算法来改善这个分割。因为这种报告算法是对整个数据半全局的。当数据从缓冲区离开的时候，分割点通常和自底向上算法的批处理版本是一样的。算法的伪代码如下表AlgorithmSeg_TS=SWAB
6、(max_error,seg_num)/seg_numisinteger,about5or6.readindatapointstofillw/wisthebuffer/Enoughtoapproximateseg_numofsegments.lower_bound-(sizeof同/2;upper_bound=2*(sizeofw);whiledataatinputT=Bottom_Up(w,max_error)/CalltheclassicBottom-Upalgorithm.Seg_TS=
7、CONCAT(SEG_TS,T(l);/Slidingwindowtotheright.w二TAKEOUTS广);/DeleteswpointsinT(1)fromw.ifdataatinput/AddpointsfromBEST_LINE()tow.w-CONCAT(w,BESTLINE(maxerror);12/Checkupperandlowerbound,adjustifnecessary.else/Flushapproximatedsegmentsfrombuffer.Seg_TS=CO
8、NCAT(SEG_TS,(T-T(l)end;end;FunctionS二BESTLINE(maxerror)/returnsSpoints.whileerrormax_error/nextpotentialsegment.readinoneadditionaldatapoint,d,intoSS=CONCAT(S,由;error=approx_segment(S);endwhile;returnS;使用缓冲区允许我们得到一个半全局的数据观。然而，利用窗口大小的高低界限也是非常重要的。一个任意增长的缓冲区会使这种算法回到单纯的自底
11、行线性扩展，而且只需要一定的空间来产生出高质量的数据近似。14参考文献1Agrawal,R.,Faloutsos,C.,&Swami,A.(1993).Efficientsimilaritysearchinsequencedatabases.Proceedingsofthe4theConferenceonFoundationsofDataOrganizationandAlgorithms._2Agrawal,R.,Lin,K.I.,Sawhney,H.S.,&Shim,K.(1995).Fastsimilaritysearc
12、hinthepresenceofnoise,scaling,andtranslationintimes-seriesdatabases.Proceedingsof21thInternationalConferenceonVeryLargeDataBases,pp490-50.3Agrawal,R.,Psaila,G.,Wimmers,E.L.,&Zait,M.(1995).Queryingshapesofhistories.Proceedingsofthe21stInternationalConferenceon
13、VeryLargeDatabases.4Chan,K.&Fu,W.(1999).Efficienttimeseriesmatchingbywavelets.Proceedingsofthe15theIEEEInternationalConferenceonDataEngineering.5Das,G.,Lin,K.Mannila,H.,Renganathan,G.,&Smyth,P.(1998).Rulediscoveryfromtimeseries.Proceedingsothe3rdIn
14、ternationalConferenceofKnowledgeDiscoveryandDataMining,pp1622.6Douglas,D.H.&Peucker,T.K.(1973).AlgorithmsfortheReductionoftheNumberofPointsRequiredtoRepresentaDigitizedLineorIts15Caricature.CanadianCartographer,Vol.10,No.2,December.Pp.112-122._7Duda,R.0
15、.andHart,P.E.1973.PatternClassificationandSceneAnalysis.Wiley,NewYork.8Ge,X.&SmythP.(2001).SegmentalSemi-MarkovModelsforEndpointDetectioninPlasmaEtching.ToappearinIEEETransactionsonSemiconductorEngineering._9Heckbert,P.S.&Garland,M.(1997).Surveyofpolygona
16、lsurfacesimplificationalgorithms,MultiresolutionSurfaceModelingCourse.Proceedingsofthe24thInternationalConferenceonComputerGraphicsandInteractiveTechniques.Hunter,J.&McIntosh,N.(1999).Knowledge-basedeventdetectionincomplextimeseriesdata.ArtificialIntelligenceinMedi
17、cine,pp.271-280.Springer.Ishijima,M.,etal.(1983).Scan-AlongPolygonalApproximationforDataCompressionofElectrocardiograms.IEEETransactionsonBiomedicalEngineering.BME-30(11):723-729.Koski,A.,Juhola,M.&Meriste,M.(1995).SyntacticRecognitionofECGSignalsByAttributedF
18、initeAutomata.PatternRecognition,28(12),pp.1927-1940.16Keogh,E,.Chakrabarti,K,.Pazzani,M.&Mehrotra(2000).Dimensionalityreductionforfastsimilaritysearchinlargetimeseriesdatabases.JournalofKnowledgeandInformationSystems.Keogh,E.&Pazzani,M.(1999).Relevancefeedbac
19、kretrievaloftimeseriesdata.Proceedingsofthe22thAnnualInternationalACM-SIGIRConferenceonResearchandDevelopmentinInformationRetrieval.15Keogh,E.,&Pazzani,M.(1998).Anenhancedrepresentationoftimeserieswhichallowsfastandaccurateclassification,clusteringandrelevan
20、cefeedback.Proceedingsofthe4thInternationalConferenceofKnowledgeDiscoveryandDataMining,pp239一241,AAAIPress.16Keogh,E.,&Smyth,P.(1997).Aprobabilisticapproachtofastpatternmatchingintimeseriesdatabases.Proceedingsofthe3rdInternationalConferenceofKnowledgeDisco
21、veryandDataMining,pp24-20._17Lavrenko,V.,Schmill,M.,Lawrie,D.,Ogilvie,P.,Jensen,D.,&Allan,J.(2000).MiningofConcurentTextandTimeSeries.Proceedingsofthe6thInternationalConferenceonKnowledgeDiscoveryandDataMining,pp.37-44.17Li,C,.Yu,P.&CastelliV.(1998).
22、MALM:Aframeworkforminingsequencedatabaseatmultipleabstractionlevels.Proceedingsofthe9thInternationalConferenceonInformationandKnowledgeManagement.pp267-272.McKee,J.J.,Evans,N.E.,&Owens,F.J.(1994).EfficientimplementationoftheFan/SAPA-2algorithmusingfixedpoi
23、ntarithmetic.Automedica.Vol.16,pp109-117.Osaki,R.,Shimada,M.,&Uehara,K.(1999).ExtractionofPrimitiveMotionforHumanMotionRecognition.The2ndInternationalConferenceonDiscoveryScience,pp.351-352.Park,S.,Kim,S.W.,&Chu,W.W.(2001).Segment-BasedApproachforSubsequen
24、ceSearchesinSequenceDatabases,ToappearinProceedingsofthe16thACMSymposiumonAppliedComputing.Park,S.&Lee,D.,&Chu,W.W.(1999).FastRetrievalofSimilarSubsequencesinLongSequenceDatabases”,Proceedingsofthe3rdIEEEKnowledgeandDataEngineeringExchangeWorkshop.Pavlid
25、is,T.(1976).Waveformsegmentationthroughfunctionalapproximation.IEEETransactionsonComputers.Perng,C.,Wang,H.,Zhang,S.,&Parker,S.(2000).Landmarks:18anewmodelforsimilarity-basedpatternqueryingintimeseriesdatabases.Proceedingsof16lhInternationalConferenceonData
26、Engineering.Qu,Y.,Wang,C.&Wang,S.(1998).Supportingfastsearchintimeseriesformovementpatternsinmultiplesscales.Proceedingsofthe7thInternationalConferenceonInformationandKnowledgeManagement.Ramer,U.(1972).Aniterativeprocedureforthepolygonalapproximationofplanar
27、curves.ComputerGraphicsandImageProcessing.1:pp.244-256.Shatkay,H.(1995).ApproximateQueriesandRepresentationsforLargeDataSequences.TechnicalReportcs-9503,DepartmentofComputerScience,BrownUniversity.Shatkay,IL,&Zdonik,S.(1996).Approximatequeriesandrepresentationsf
28、orlargedatasequences.Proceedingsofthe12thIEEEInternationalConferenceonDataEngineering,pp546-553.Sugiura,N.&Ogden,R.T.(1994).TestingChangepointswithLinearTrendCommunicationsinStatisticsB:SimulationandComputation.23:287-322.30Vullings,H.J.L.M.,Verhaegen,M.H.
31、UsingTime-Warping.Proceedingsofthe2ndInternationalSymposiumonIntelligentDataAnalysis.31Wang,C.&Wang,S.(2000).SupportingcontentbasedsearchesontimeSeriesviaapproximation.Proceedingsofthe12thInternationalConferenceonScientificandStatisticalDatabaseManagement.20再本文中
32、，我们评价文献中三种主要的分割方法，并且对来自金融医疗科学的数据集一个考察评估。这些实验的主要结果表明，只有在线算法得到了很差的近似数据，而批处理算法得到了高质量的结果和一一这些结果促使我们介绍一种新的在线算法，它能够又在线，又产出高质量的数据近似.本文接下来的主体结构如下：在第二节中，我们将对文献中已有的算法进行总体评价，解释它们的主要方法以及各种各样数据挖掘者的改变和扩展。在第三节中，我们将详细地考究、比较这些算法。我们会证明最受数据挖掘者欢迎的方法实际上产生相当糟糕的数据近似。这些糟糕的结果将激励我们寻求一种新的算法，而我们将在第四节中介绍和评估这种算法。第五节将做一个总结
35、之下，线性回归则产生了不连贯的图像。线性插补的美观的结果、较低的计算复杂度使它成为了计算机图形应用的选择。然而，按照欧几里得距离理论，线性插补得到的近似线段的质量通常比回归方法得到的要差。所有的分割算法都需要一些方法来为评估它应用于一个潜在分段的质量。通常采用的测量依据是平方和，或者残留的错误。这通最适线段和实际数据点的垂直差异，计算它们并且总和。另外一种常用的拟合优度的测量依据是最适线段和垂直方向上最远数据点的距离。以前，我们正如以前，我们一直保持我们的算法的描述，一般足以涵盖任何错误措施。特别地，伪代码函数calculate_error(T)可以被当做使用了任何的平方和，
37、:anchor+i)max_errori=i+1;end;Seg_TS=concat(Seg_TS,create_segment(Tanchor:anchor+(i-1);anchor=anchor+i;end;滑动窗口算法的优势在于它的简单，直观性，还有特别是因为它是一种在线算法。也有以此算法为基础的很多不同的变换和优化。Koskietal提出可以通过把变量i的增量由1变为“长度k的跳跃”来加速这种算法12o取决于使用的误差测量，可能还有其他的优化手段。Bulllingsetal提出因为残留的误差即使加入更多的数据点也不会增长，所以我们不必测出从2
39、指定的阈值，如果不是,算法将递归地进行分割子序列直到所有的分段的拟合误差都小于阈值。算法的伪代码如下表所示：AlgorithmSeg_TS=Top_Down(T,max_error)best_so_far=inf:fori=2tolength(T)-2/Findbestplacetodivide.improvement_in_approximation二improvement_splitting_here(T,i);ifimprovement_in_approximationmax_errorSegTS二TopDown(T1:b
40、reakpoint);end;/Recursivelysplittherightsegmentifnecessary.ifcalculate_error(Tbreakpoint+1:length(T))max_errorSegTS=TopDown(Tbreakpoint+1:length(T);end;在数十年前，自上而下算法的变种(包括二维情况)就被独立地应用于各个领域。在制图学，出名的有Douglas-Peucker算法，在图像处理方面，出名的有Ramers算法。大多数的机械学习与数据挖掘领域的研究者。在机器学习和数据挖掘领域，大多数的研究