时序数据维归约方法的研究

兰州大学硕士学位论文时序数据维归约方法的研究姓名杨仕博申请学位级别硕士专业计算机软件与理论指导教师马志新20080501兰州大学硕士研究生毕业论文摘要时间序列是一类重要的数据类型，广泛存在于金融、事务处理和科学研究等领域中。时间序列挖掘通过对过去历史行为的客观记录分析，提取人们事先不知道的，但又是潜在有用的与时间属性相关的信息和知识，从而揭示其内在的数据生成机制，进而发现和预测未来行为模式。本文系统地介绍了时间序列挖掘技术，包括时间序列的数据清理、分割、表示和相似性度量等技术。论文研究了时间序列的分段表示方法，主要的研究工作及成果如下1由于原始时间序列具有高维性、类型复杂和富含噪声的特点，直接在时间序列上执行数据挖掘任务，往往导致算法效率低下和挖掘结果不可靠。时间序列的维归约是一种对时间序列进行特征抽象和概括的表示方法，是对时间序列在更高层次上的重新描述。论文在分析了经典的自顶向下、自底向上和滑动窗口算法的基础上，针对滑动窗口算法出现的“过拟合”的分段，通过检测前后两个分段趋势的相近程度，对趋势相近的分段进行合并，从而有效地避免了尖峰形态数据的影响；针对“欠拟合“的分段，采用了一种新的度量方法，对“欠拟合”的分段进行适当分割，从而得到更好的表示效果。实验表明以上两种改进策略效果明显。2目前大量的信息系统都是实时地产生数据，这样的数据类型称作“数据流”，具有如下两个特点系统源源不断地产生大量的细节数据；需要实时地对新产生的数据进行分析。针对数据流上的应用，本文提出了一种适合在线分割的时间序列表示算法一RSW算法，该算法基于滑动窗口算法框架，应用了文中提出的两种改进策略，实验结果表明RSW是一种适合在线分割的时间序列表示算法，具有线性复杂度和拟合误差小的特点。关键词时间序列，数据挖掘，维归约兰州人学硕F研究生毕业论文ABSTRACTTIMESERIESISANIMPORTANTDATATYPE，WHICHISWIDELYUSEDINTHEAREASOFFINANCE，BUSINESSANDSCIENTIFICRESEARCHBYTHEANALYSISOFHISTORICALBEHAVIORSOBJECTIVERECORDSTIMESERIESMININGEXTRACTSTHEPOTENTIALLYUSEFULANDTIMERELATEDINFORMATIONANDKNOWLEDGE，WHICHISNOTKNOWNINADVANCEITREVEALSINTERNALDATAGENERATIONMECHANISMSTOFINDANDPREDICTTHEFUTUREBEHAVIORPATTERNSTHISPAPERSYSTEMATICALLYDISCUSSESTIMESERIESMININGTECHNOLOGY,INCLUDINGDATACLEANUP。SEGMENTATION。REPRESENTATIONANDSIMILARITYMEASUREITRESEARCHESTHEPIECEWISEPRESENTATIONOFTIMESERIESTHEMAINRESEARCHWORKANDCONTRIBUTIONSAREASFOILOWS1ASTHEORIGINALTIMESERIESWITHCHARACTERISTICSOFHIGHDIMENSIONAL，COMPLEXANDRICHNOISE，DATAMININGONTIMESERIESORENDIRECTLYLEADSTOALGORITHMINEFFICIENCYANDMININGRESULTSUNRELIABILITYDIMENSIONAL时REDUCTIONOFTIMESERIESISAMETHODOFTIMESERIESABSTRACTION，ANDAHIGHERLEVELREDESCRIPTIONABOUTTHEMWITHANALYSISOFTHECLASSICTOPDOWN，BOTTOMUPANDSLIDINGWINDOWALGORITHM，THEPAPERSOLVESTHE“OVERFITTING”INSLIDINGWINDOWALGORITHMSBYTESTINGTHESIMILARITYOFNEIGHBORINGSEGMENTS，ANDMERGINGSIMILARONESTHISMETHODAVOIDSIMPACTOFPEAKDATAEFFECTIVELYASTO”UNDERFITTING”PROBLEM，ANEWMEASUREMENTISUSEDTODIVIDE“UNDEMTTING”SEGMENTSFORBETTERPRESENTATIONTHEEXPERIMENTALRESULTSSHOWTHATTWOSTRATEGIESPROPOSEDINTHEPAPERISEFFECTIVE2ATPRESENT，ALOTOFINFORMATIONSYSTEMSPRODUCEONLINEDATA，ANDTHISTYPEOFDATAISCALLED”DATASTREAM”，WHICHHASTHEFOLLOWINGTWOCHARACTERISTICSSYSTEMGENERATESALOTOFDETAILDATACONTINUOUSLY；NEWGENERATEDDATANEEDONLINEANALYSISFORDATASTREAMAPPLICATIONS，THISPAPERDEVELOPSANEWONLINEALGORITHMRSWFORPRESENTATIONOFTIMESERIES。WHICHISBASEDONTHESLIDINGWINDOWALGORITHMFRAMEWORKANDAPPLIESTWOSTRATEGIESPROPOSEDINTHEPAPERTHEEXPERIMENTALRESULTSSHOWTHATRSWISAMORESUITABLEALGORITHM兰州人学硕F研究生毕业论文FORTIMESERIESONLINEDIVISION，ANDHASLINEARCOMPLEXITYANDSMALLFITTINGERRORSKEYWORDSTIMESERIES，DATAMINING，DIMENSIONALITYREDUCTION原创性声明本人郑重声明本人所呈交的学位论文，是在导师的指导下独立进行研究所取得的成果。学位论文中凡引用他人已经发表或未发表的成果、数据、观点等，均已明确注明出处。除文中已经注明引用的内容外，不包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研究成果做出重要贡献的个人和集体，均己在文中以明确方式标明。本声明的法律责任由本人承担。论文作者签名J碑日关于学位论文使用授权的声明本人在导师指导下所完成的论文及相关的职务作品，知识产权归属兰州大学。本人完全了解兰州大学有关保存、使用学位论文的规定，同意学校保存或向国家有关部门或机构送交论文的纸质版和电子版，允许论文被查阅和借阅；本人授权兰州大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用任何复制手段保存和汇编本学位论文。本人离校后发表、使用学位论文或与该论文直接相关的学术论文或成果时，第一署名单位仍然为兰州大学。保密论文在解密后应遵守此规定。论文作者签名硒师签名ET期丝岁珍兰州大学硕L研究生毕业论文第一章绪论11研究背景和意义从20世纪80年代开始，数据库技术广泛应用于科研、生产以及流通领域的事务处理，因此积累了庞大的数据，特别是数据仓库以及WEB等新型的数据源日益普及，人们面对浩瀚的数据海洋，如何有效利用这些数据资源，找出数据背后隐藏的信息和知识面对这一挑战，数据挖掘技术应运而生。数据挖掘技术作为一种新兴的智能决策支持技术，受到了广泛的关注。数据挖掘技术是数据库技术的发展和延伸。自20世纪60年代起，由于计算机技术在事务处理领域的应用，产生了人量的数据，由此引起了数据库技术的发展，从原始的文件处理演化到复杂的、功能强大的数据库系统。自70年代以来，数据库系统的研究和开发转向层次数据库、网状数据库和关系数据库等。自80年代以来，数据库的特点是广泛接受关系技术，研究和开发新的、功能强大的数据库系统，产生了扩充关系模型、面向对象模型、对象关系模型和演绎模型等先进的数据模型，出现了时间的、空问的、分布的、多媒体的、主动的和科学计算的数据库、知识库在内的多种面向应用的数据库系统。90年代以来，由于万维网的蓬勃发展，出现了基于WEB的数据库系统、多维数据库、数据仓库和联机分析处理OLAP等新的数据处理技术。数据库技术和人工智能中的机器学习的蓬勃发展，为快速、高效和自动处理海量数据提供了可能。1989年8月在美国底特律召开的第11届国际人工智能联合会议的专题讨论会上首次提出KDDKNOWLEDGEDISCOVERYINDATABASE。随后在1991年、1993年和1994年都举行了KDD专题讨论会，汇集了来自各个领域的研究人员和应用开发者，集中讨论数据统计、海量数据分析算法、知识表示、知识运用等问题。数据挖掘DATAMINING是指从大量的、真实的、含噪音的数据中提取有用的、隐藏的、用户感兴趣的信息和知识的过程【LJ。因此，数据挖掘也被称为知识挖掘、知识提取、知识发现等。自上世纪90年代以来，数据挖掘技术广泛应用于生物、医学、天气预报、销售分析等领域，用来发现对象的演化规律和变化兰州大学硕士研究生毕业论文趋势。其挖掘步骤如下1明确挖掘任务数据挖掘人员与领域专家合作，对问题进行深入的分析，清晰地定义出挖掘任务。认清数据挖掘的目的是数据挖掘前提，挖掘的最后结果是不可预测的，但要探索的问题应是可预见的。2数据的准备和选择了解相关的源数据结构并加以分析，确定数据选择的原则。并根据用户的要求从数据库中提取与挖掘任务相关的数据。3数据预处理存在不完整的、含噪声的和不一致的数据是人型的、现实世界数据库或数据仓库的共同特点II】。检查数据的完整性及数据的一致性，对其中的噪声数据进行处理，对缺失的数据利用统计方法进行填补。数据预处理技术可以改进数据的质量，从而有助于提高其后的数据挖掘的精度和性能。常用的技术有数据清理消除噪声数据、空缺值和不一致数据、数据集成和变换、数据归约、数据压缩和数值数据的概念分层。在数据挖掘之前运用合理的预处理技术，可以大大提高数据挖掘模式的质量，降低实际挖掘所需要的时间。4数据挖掘运用选定的算法，从数据中提取出用户所需要的知识。数据挖掘是KDD最关键的步骤，也是技术难点所在。采用的技术包括决策树、分类、聚类、粗糙集、关联规则、神经网络和遗传算法等。数据挖掘根据KDD的目标，选取相应算法，分析数据，得到相应的知识模式类型。5评价和解释模式是由数据挖掘得到的模型，可能没有实际意义或使用价值，或不能准确反映数据的真实含义，甚至在某些情况下是与事实相反的，因此对于数据挖掘的结果需要进行评估，以确定哪些是有效的、有用的模式。一般使用兴趣度度量来识别真正有趣的模式。将挖掘出来的模式解释成应用知识并集成到业务信息系统，根据知识本身描述的关系或结果给决策者提供技术支持。2兰州大学硕士研究生毕业论文卜一数据准备和选择十数据预处理叫数据挖掘斗结果表示及解释I知识图11数据挖掘的阶梯处理过程模型数据挖掘的基本功能和可以发现的模式类型如下1概念类描述CLASSCONCEPTDESCRIPTION数据可以与类或概念相关联。用汇总的、简洁的、精确的方式描述每个类和概念称为概念类描述。主要的方法有1数据特征化，是目标类数据的一般性特征或特性的汇总；2数据区分，将目标类对象的一般特性与其他类的一般特性相比较。2关联规则ASSOCIATIONANALYSIS数据关联是数据库中存在的一类重要的可被发现的知识。若两个或多个变量的取值之间存在某种规律性，就称为关联。关联可分为简单关联、时序关联、因果关联。关联规则挖掘是无指导学习系统中挖掘本地模式的最普通模式，利用该过程可以获取数据集中事先并不了解或不确定的有价值信息。3分类CLASSIFICATION分类是在一部分数据训练集上找出描述并区分数据类或概念的规律和模型，以便能够使用模型预测类标记未知的对象类。在分类的基础上可以进一步推演以实现推测数据对象的类标记和部分数据值。分类常用的方法决策树方法、粗集方法、贝叶斯方法、人工神经网络方法和遗传算法等。兰州大学硕土研究生毕业论文4聚类CLUSTERING把数据划分到不同的组中，组之间的差别尽可能大，组内的差别尽可能小。与分类不同的是，分类中知道训练集的分类属性值，而进行聚类时，需要在训练集中找到这个分类属性值，聚类可以直接满足用户的要求，同时也是概念描述和异常值分析的基础。聚类技术主要包括传统的模式识别方法和数学分类学。5孤立点分析OUTLIERANALYSIS在系统巾存在一些数据，它们不符合数据的一般模型，与其他数据对象不同或不一致，这样的数据对象被称为孤立点。孤立点在一些应用巾非常重要，隐藏着重要的信息，如欺诈行为检测。因此，孤立点分析和检测是一种非常有价值的数据挖掘任务，主要的孤立点分析方法有基于统计的孤立点检测、基于距离的孤立点检测、基于偏离的孤立点检测。6演变分析EVOLUTIONANALYSIS演变分析是通过数据分析描述行为随时间变化的规律和特征，并对其建模。主要的演变分析方法包括时间序列数据分析、序列或周期模式匹配和基于相似性的数据分析。7序列模式挖掘SEQUENCEPATTERNMINING序列模式挖掘是从序列中发现蕴含的序列模式。时间序列模式挖掘与关联规则挖掘有许多相似之处，前者一般是发现与时间属性相关的高频率子模式，后者一般是在忽略时间属性的情况下，发现项目之间的关联性。图12给出了数据挖掘系统结构图。其中，数据挖掘引擎是数据挖掘系统的核心部分，由一组实现具体挖掘功能的算法组成。知识库主要是是存放领域知识，用于指导搜索或评估模式的兴趣度。另外，知识库还包括兴趣度阈值和元数据描述来自多个异种数据源的数据。模式评估部分主要是使用兴趣度度量方法，识别表示知识的真正有价值的模式。数据库和数据仓库主要根据用户的数据挖掘主题目标和具体的挖掘任务提供数据资源。随着信息化水平的提高，证券、金融、保险和医疗等行业逐渐成数据密集型行业，如何发现其中的隐含信息以避免金融犯罪、违规操作等行为越来越受到关注。但是这些数据与时间紧密相连，利用传统的挖掘方法已经不能达到预期目标。因此，时间序列数据挖掘TIMESERIESDATAMINING，TSDM技术应运而生，成4兰州人学硕士研究生毕业论文为数据挖掘的一个重要研究方向。图12典型的数据挖掘系统结构LIJ时间序列挖掘通过对过去历史行为的客观记录分析，揭示其内在的规律如波动的周期、振幅、趋势的种类等，进而完成预测未来行为等决策性工作。期望通过对时间序列的分析，从大量的数据中发现和揭示某一现象的发展变化规律或从动态的角度刻画某一现象与其他现象之间的内在数量关系，以掌握和控制未来的行为。时间序列的研究必须依据合适的理论和技术进行，时间序列的多样性表明其研究必须结合序列特点找到合适的建模方法。12主要工作及创新本文系统地介绍了时间序列挖掘技术，包括时间序列的数据清理、数据分割、表示和相似性度量等技术。论文主要研究了时间序列的分段表示方法。本文的主要的研究工作内容及成果如下兰州人学硕士研究生毕业论文时间序列是随时间变化的属性值的序列，是信息系统中普遍存在的一类重要数据对象，如股票行情数据。由于原始时间序列具有高维性、类型复杂和富含噪声的特点，直接在时间序列上执行数据挖掘任务，往往导致算法效率低下和挖掘结果不可靠。本文在分析了经典自顶向下、自底向上和滑动窗口算法的基础上，针对滑动窗LJ算法出现的“过拟合”的分段，通过检测前后两个分段趋势的相近程度，对趋势相近的分段进行合并，从而有效地避免了尖峰形态数据的影响；针对“欠拟合”的分段，采用了一种新的度量方法，对“欠拟合”的分段进行适当分割，从而得到更好的表示效果。实验结果表明以上两种改进策略效果明显。针对数据流上的应用，本文提出了一种适合在线分割的时间序列表示算法叫SWREFINEDS1IDINGWINDOW算法，该算法基于滑动窗口算法框架，应用了文中提出的两种改进策略，实验结果表明RSW是一种适合在线分割的时间序列表示算法，具有线性复杂度和拟合误差小的特点。13本文组织结构本文共分五章，下面简要介绍一下各章的内容第一章阐述了课题的研究背景和意义，以及本文的主要工作和组织结构；第二章时间序列挖掘问题综述。系统地介绍了时间序列挖掘相关技术，包括时间序列的数据清洗、分割、表示、相似性性度量和预测。第三章对时间序列的表示分段表示算法进了详细描述，并介绍了相关研究的工作进展。分析了线性分段表示算法的优缺点，针对算法出现的“过拟合“和“欠拟合“的问题，提出了两种改进策略，并给出了算法的伪代码和实验效果。第四章针对时问序列在线分割的现实需求，应用第三章中提到的两种改进策略，提出了一种基于S1IDINGWINDOW算法的时间序列在线分割表示算法二一RSW算法，并通过实验对算法性能进行了验证。第五章对全文进行总结和展望。全面总结研究工作的内容，并提出下一步的研究方向。6兰州大学硕研究生毕业论文第二章时间序列挖掘问题综述21研究背景随着计算机技术的广泛应用和存储介质的大量供应，在日常的事务处理和科学研究中，人们积累了大量的各种类型的数据，它们被描述为“数据丰富，信息贫乏”。面对快速增长的海量级的数据，人们迫切需要强有力的数据分析工具，来分析和理解数据，进而辅助决策和规划。数据挖掘白上世纪90年代以来，被广泛应用于生物、医学、天气预报、销售分析等领域，用来发现对象的演化规律和变化趋势。数据挖掘可以发现的模式类型有概念，类描述、关联分析、分类和预测、聚类、孤立点分析和演变分析等。时间序列是随时间变化的属性值的序列，是信息系统中普遍存在的一类重要数据对象，如股票行情数据。通过提取隐含在时间序列中的模式来应用于时间序列的预测与聚类，以反映属性值在时间和空间上的特征。一方面，由于时间序列的数据类型复杂多变、有噪声、高维性等特点，使得时间序列的挖掘成为极具挑战一个领域；另一方面，时间序列广泛存在于日常事务处理的方方面面，因此时间序列挖掘成为近年来成为数据挖掘学者关注的热点，其研究的方向有时间序列模式的表示、时间序列的相似性度量、时间序列的查询等。22时间序列挖掘技术概述时间序列的数据挖掘技术自20世纪90年代以来有了快速发展，由最初的相似性分析到目前的包含人工智能的多学科交叉研究。时间序列挖掘就是从大量的时间序列数据中提取人们事先不知道、但又是潜在有用的与时间属性相关的信息和知识，并用于短期、中期或长期预测，指导人们的社会、生活、经济和军事等领域。时间序列TIMESERIESORTIMESEQUENCE是指随时间变化的属性值序列或事件序列。由于前后时刻的数值或数据点的相关性往往呈现出某种趋势或周期性7兰州人学硕士研究生毕业论文变化，因而时间序列里蕴藏着着其它信息形式所不B皂T替的知识。时间序列是一种非常重要的数据类型，在商业应用和科学研究中广泛存在着大量的时间序列，通过分析和处理这类数据，对自然和社会科学领域的预测、决策和发展具有重大意义。时间序列数据挖掘技术通过提取时间序列巾的隐含模式，将其应用于时间序列的预测与聚类中，以反映属性值在时间和空间上的特征。由于时间序列的数据类型复杂多变、有噪声、高维性等特点，时间序列的挖掘成为极具挑战性的一个领域。此外，它广泛存在于日常事务处理的方方面面，因此成为近年来数据挖掘学者关注的热点。其研究方向包括L、时间序列的归约通过对数据集归约，得到原数据集的近似表示。保持了原数据的特征信息，而数据量小得多。时间序列的归约是对时间序列进行抽象和概括的特征表示方法，在更高层次上对时间序列进行重新描述。常用的方法有奇异值分解SVD，SINGULARVALUEDECOMPOSITION、离散傅立叶变换DFT，DISCRETEFOURIERTRANSFORM、离散小波变换DWT，DISCRETEWAVELETTRANSFORM、符号映射和分段线性表示PLR，PIECEWISELINEARREPRESENTATION。维归约的任务是在保留主要特征模式的情况下，忽略部分数据，用尽可能小的空间完成原时间序列的近似表示。2、时间序列的划分对给定的包含N个时间点的时间序列Q构建模型，将其分为K个部分KMAX_ERROR计算ANCHORIL】，DATAANCHORI1的线性回归表示序列，并存入BEST；KK1新的分段保存第K段的结束时刻，开始值和结束值SEGJSKIL，BEST1，BESTEND；ANCHORI开始新的窗口END；END；处理最后一段KKL；保存最后一段的结束时刻，开始值和结束值SEG_TSK1ENGTHDATA，BEST1，BESTEND；图31SLIDINGWINDOW算法伪代码兰州人学硕士研究生毕业论文342TOPDOWN算法自顶向下法TOPDOWN首先扫描整个时间序列，找到最佳分割点将序列分为2个子序列，分别计算两个子序列的拟合误差。如果某个子序列拟合误差大于阈值，则继续对该子序列用相同的方法再进行细分，直到所有子序列的拟合误差都小于阈值。TOPDOWN算法输入时间序列DAM，最大累积误差阈值MAXERROR输出分段表示序列SEG_TSBESTSOFARINF；力，I_2TOLENGTHT一2计算使用第I个点分割的参考值，记为VALUEIEND；【E，BP】_MAXVALUE；计算DATA1BP的拟合误差E；矿EMAX_ERRORSEGJSLTOP_DOWNT1BP】；END；计算DATABPLLENGTHDAM的拟合误差E；17REMAX_ERRORSEG_TSRTOP_DOWNTBPLLENGTHT；END；合并SEGJSL和SEG_TS_R，并保存到SEGTS；图32TOP_DOWN算法伪代码343BOTTOMUP算法自底向上法BOTTOMUP首先把整个时问序列以每2个点为一段进行分段，计算相邻两段合并后的拟合误差，每次将误差最小的两段合并，直至任意相邻两段合并后的误差小于阈值。当第F段和第FL段合并后，算法只需要重新计算合兰州大学硕LJ研究生毕业论文并段与第FL段和第I2段的合并拟合误差。BOTTOM_UP算法伪代码输入时间序列DATA，最大累积误差阈值MAX,ERROR输出分段表示序列SEG_TS户，IL2LENGTHDATAL第I段和第IL段合并，合并的结果记为SEGTS；END；力，ILLENGTHSEGTS1计算第I段和第I1段合并的代价COSTI；END；【E，I】MINCOST】；WHILEE。令晒IFFLENGTHTM以】LENGTHTPG】IFFLENGTHTM刀】LENGTHSTARTNENDX1NEWBESTSEGMENTK1COEF1【STARTKENDK】SEGMENTK1COEF2；【VALUE，POS】MAXABSNEW_BESTBEST；ELSENEWBESTSEGMENTKCOEF1事【STARTNP门以一L】SEGMENTKCOEF2；【VALUE，POS】2MAXABSNEW_BESTBEST；END；UEVALUEBESTPOSFUEQ在I时刻处分割第K段分段为两段从SEGMENT中添加新分割的两段KK1END；图39DIVIDE_SEGMENTATION算法伪代码兰州人学硕L研究生毕业论文一F“一N莎彦”V。气矿O50100150200250300图3一10分割位置庐029，026从图310看出DIVIDE_SEGMENTATION可以有效的找到“欠拟合“的分段，并且当阈值Q给定的比较合适，算法可以找到恰当的分割位置，如果按照图310中给出的分割位置将原序列分为两段，虽然这样的分割虽然捕捉到了序列数值大的变化，但这样这种改进是通过增加序列分段的方式实现的，且新增加的分段表示效率很低，显然这样的分割是低效的。我们改进的方法是当分段的累积误差E超过指定阈值后，计算SE，若SE大于Q，则分割位置作为下一个滑动窗口的起始位置，当E029，Q26时，改进效果如图311。剥秽J图311当庐O29，Q26的分割效果虚线为滑动窗口重定位的位置实验表明DIVIDE_SEGMENTATION在解决SLIDINGWINDOW算法“欠拟合缺陷1864200000186420000O兰州大学硕士研究生毕业论文的同时，更好地表现了时间序列的局部细节。论文将在第四章继续讨论这一改进思路。兰州大学硕士研究生毕业论文第四章时间序列的在线归约41引言传统的数据库存储的是静态的数据，没有时间属性。但是越来越多的应用需要系统支持数据流上的处理。数据流是一个实时的、时间上连续的项目的序列。根据到达的先后顺序标记时间属性，序列的到达的顺序是不可控制的，并且存储全部序列也是不可行的P21。数据流应用的产生和发展是以下两个因素的结果【2J1产生大量细节数据的应用层出不穷。早期出现于传统的银行和股票交易正领域，现在则也出现在地质测量、气象、天文观测等方面。尤其是互联网网络流量监控，点击流和无线通信网通话事件记录的出现，产生了大量的数据流类型的数据。2需要以实时的方式对更新流进行复杂分析。对以上领域的数据进行复杂分析如趋势分析，预测以前往往是在数据仓库中脱机进行的，然而一些新的特殊的应用需要实时分析处理，如检测互联网上的极端事件、欺诈、入侵、异常，复杂人群监控，趋势监控TRACKTREND，探查性分析EXPLORATORYANALYSES，和谐度分析HARMONICANALYSIS等，都需要进行联机的分析。时间序列是按时间顺序排列的一组属性值的序列，广泛存在于商业、经济、工程和科学研究领域，例如证券价格、销售数据、图像处理、文本挖掘等领域。由于随着时间的推移会不断地产生大量的时间序列数据，一方面因为时间序列包含大量的噪声，需要使用更高级的数据表示形式，是数据挖掘在更高的层次上运行另一方面，需要实时处理不断产生的新数据，以便实时发现和预测时态模式的变化。42相关研究工作时间序列的归约是通过保留时问序列的主要特征信息，忽略其中的一些细节，使用更高级的数据表示彤式，以支持快速高效的数据挖掘算法。32兰州人学硕士研究生毕业论文滑动窗口算法最大的缺陷在于没有考虑到时间序列在整体上的特征，自底向上和自底向下的方法就很好得利用了这一结果，但是自底向上和自底向下的方法是不能用于联机处理的。SWABL5】SLIDINGWINDOWANDBOTTOMUP算法结合了滑动窗E1算法和自底向上算法的优点，保持了滑动窗U支持联机处理的特性，同时又保持了自底向上算法的优势。从文献F5L中的实验可以发现SWAB算法具有和BOTTOMUP算法相似的表示效果。SWAB算法的缺点是继承了BOTTOMUP算法较高的时间复杂度。文献【331提出了一种评估时间序列分割结果已经分割算法性能的评价指标，并开发出一种新的在线分割时间序列的递推算法OLS。OLS算法能够有效地在线检测出感兴趣的关键变化点，且不依赖关于时间序列的先验经验。43基于SLIDINGWINDOW的时间序列在线分割改进算法RSW拐点刻画的正确与否是时间序列趋势表示好坏的一个重要方面。拐点是时间序列火部分信息的承载点，也是不同趋势的邻接点。因此，对趋势表示而言，准确刻画时间序列数据的拐点就称为PLR模型准确程度的重要标志【3LJ。本文提出一种新的基于滑动窗口的算法一RSWREFINEDSLIDINGWINDOW算法，实验结果表明RSW是一种适合在线分割的时间序列表示算法，具有线性复杂度和拟合误差小的特点。RSW算法步骤输入时间序列DATA，最大累积误差阈值MAXERROR，R，Q输出分段表示序列SEG_TS1初始化ANCHOR0，SEGJSO，EO；2建立大小为W的环形缓冲区BUFFER3WHILE数据流未关闭4WHILEER12合并第KL段和第K段，更新SEG_TSK1，并删除SEGTSK；13ANCHORLAST_ANCHOR；14ENDIF,15计算第K段的SE，SE取得最小值位置记为POS；16FSEQ17将第K段从POS处分割为第K段和第K1段，并更新SEGJSK和SEGTSK1；，18ANCHORPOS；滑动窗VI重定位19ENDIF,20ENDF,图41RSW算法步骤RSW算法采用了环形数据缓冲区BUFFER，用来存放需要归约的数据，一般应该至少可以存放钆5个分段的时序数据。当从数据流中读入的数据累积误差E超过阈值时，对序列进行分割。然后分别计算UE和SE，动态调整第K1分段和第K分段的分割位置。44仿真实验实验数据取自上证A股综合指数2000年1月4日至2006年12月29日的收盘点位的时间序列数据来源清华金融数据；网址HTTPTHFDSEMTSINGHUAEDUON，共计1688个数据，数据按照式38进行规范化处理，规范化后的数据曲线如图所示。兰州大学硕L二研究生毕业论文10806040201080604020图42200014_20061229期间的上证指数收盘点位序列020040060080010001200140016001800图43当E0435时SLIDINGWINDOW算法的分割结果35兰州人学硕士研究生毕业论文图44当E0435，R015，Q28时RSW算法的分割结果如图44所示，RSW与SLIDINGWINDOW算法相比，更准确地抽取了原时间序列的特征信息。具体来讲，对于图44中区域A中的时间序列，SLIDINGWINDOW算法和RSW算法都没有反映足够的细节。SLIDINGWINDOW算法将A区域中的时间序列分割为两段，且两段拟合效果都很差，RSW算法将其合并为一段，虽然没有能够反映时间序列变化的细节，但是反映了区域A中时间序列的总体上升趋势。对于B区域中的时间序列，RSW把握住了明显的状态变化，较好的抽取了时间序列的特征信息，并且分割位置没有滞后。总体而言，RSW算法非常适合时间序列的在线分割和表示，可以抽取时间序列的人部分特征信息，且分割位置恰到好处，在数据归约和信息抽取之间取得了较好的平衡。同时，RSW算法具有线性复杂度的优点，适合海量数据处理。兰州大学硕上研究生毕业论文51总结第五章总结与展望本文主要研究了时序数据的维归约技术。论文首先系统地介绍了时间序列挖掘技术，包括时间序列的数据清理、数据分割、表示和相似性度量等技术。论文在分析了经典自顶向下、自底向上和滑动窗口算法的基础上，针对滑动窗口算法出现的“过拟合“的分段，通过检测前后两个分段趋势的相近程度，对趋势相近的分段进行合并，从而有效地避免了尖峰形态数据的影响针对“欠拟合“的分段，采用了一种新的度量方法，对“欠拟合”的分段进行适当分割，从而得到更好的表示效果。实验表明这两种改进策略显著的减小了算法的拟合误差总和，在视觉上更能反映时间序列的趋势信息。以上两种策略在提高算法分割的同时，人为得增加了算法的参数，而这些参数的确定在不同领域应用领域有不同的取值，这是改进策略的缺点所在。针对TOPDOWN和BOTTOMUP算法拟合误差小，但却不适合联机环境，而SLIDINGWINDOW算法适合联机应用，但拟合效果不理想的现状，文中提出的一种新的时序数据维归约算法RSW。RSW基于滑动窗口算法框架，应用了文中提出的两种改进策略，实验结果表明RSW是一种适合在线分割的时间序列表示算法，具有线性复杂度和拟合误差小的优点。52下一步研究工作的展望本阶段我们主要的研究重点是时间序列的维归约算法，其中以线性分段算法为主。下一阶段的主要目标是在进一步完善我们所做的基础理论研究工作的基础上，进行与时序数据维归约问题相关的应用研究。文中通过分析滑动窗口算法在时序数据维归约问题上的不足，提出了对时序数据历史分段进行分割和合并的度量方法，从而可以动态地调整分割点的位置，使得基于滑动窗口的维归约算法更为准确地抽取了时间序列的特征信息，从而为后续的数据挖掘算法提供了保证。文中阐述的动态调整分割点的思想，可以有效37兰州人学硕士研究生毕业论文地解决滑动窗口算法分割点位置不精确的弊端，并且这种改进保持了滑动窗口算法线性复杂度和适合在线归约的优点。我们将继续沿着这一思路，寻找抽取特征更准确的时序数据维归约算法。文中提出的对时序数据历史分段进行分割和合并的度量方法，使用了额外的参数R和Q，这使得归约任务需要人工干预，以确定合适的参数。我们将在以后的工作中研究参数R和Q的物理意义，进一步研究在噪声环境下更加符合视觉要求的时间序列维归约算法。38兰州大学硕士研究生毕业论文参考文献1HANJ，KAMBERMDATAMININGCONCEPTSANDTECHNIQUES，MORGANKAUFMANNPUBLISHERS，20012HENZINGERM，RAGHAVANP，RAJAGOPALANSCOMPUTINGONDATASTREAMSTECHNICALNOTE1998一011PALOALTO，CADIGITALSYSTEMSRESEARCHCENTER，19983DASG，LINKI，MANNILAH，ETA1RULEDISCOVERYFROMTIMESERIESINPROCEEDINGSOFTHEFOURTHINTERNATIONALCONFERENCEONKNOWLEDGEDISCOVERYANDDATAMININGKDD98，1622，NEWYORK，USAAAAIPRESS，19984SRIKANTR，AGRAWALRMININGSEQUENTIALPATTERNSGENERALIZATIONSANDPERFORMANCEIMPROVEMENTSINPROCEEDINGSOFTHE5THINTERNATIONALCONFERENCEONEXTENDINGDATABASETECHNOLOGY，3一17，AVIGNON，FRANCESPRINGERYERLAG，19965KEOGHEJ，CHUS，HARTD，ETA1ANONLINEALGORITHMFORSEGMENTINGTIMESERIESICDM，289296，20016AGRAWALR，FALOUTSOSC，SWAMIANEFFICIENTSIMILARITYSEARCHINSEQUENCEDATABASESPROCEEDINGSOFTHE4THINTERNATIONALCONFERENCEOFFOUNDATIONSOFDATAORGANIZATIONANDALGORITHMS，69一一84，CHICAGO，111INOISSPRINGERVERLAG，19937SHATKAY，HAGITTHEFOURIERTRANSFORMAPRIMERTECHNICALREPORTCS953719958肖辉时间序列的相似性查询与异常检测博士学位论文上海复旦大学，20059CHANK，CHEEAWEFFICIENTTIMESERIESMATCHINGBYWAVELETSINPROCEEDINGSOFTHE15THINTERNATIONALCONFERENCEONDATAENGINEERING，126133，SYDNEY，AUSTRALIA199910POPIVANOVI，RENEEJMILLERSIMILARITYSEARCHOVERTIMESERIESDATA39兰州人学硕士研究生毕业论文USINGWAVELETSINPROCEEDINGSOFTHE18THINTERNATIONALCONFERENCEONDATAENGINEERING，212221，SANJOSE，CA，USA200211AGRAWALR，LINKI，SAWHNEYHS，ETA1FASTSIMILARITYSEARCHINTHEPRESENCEOFNOISE，SCALING，ANDTRANSLATIONINTIMESERIESDATABASESTWENTYFIRSTINTERNATIONALCONFERENCEONVERYLARGEDATABASES，490一一501，ZURICH，SWITZERLANDMORGANKAUFMANN，199512LHJ，GMH，VERBRUGGENHBECGSEGMENTATIONUSINGTIMEWARPINGIDA97PROCEEDINGSOFTHESECONDINTERNATIONALSYMPOSIUMONADVANCESININTELLIGENTDATAANALYSIS，REASONINGABOUTDATA，275一一285，LONDON，UKSPRINGERVERLAG，199713JUANGLA，RABINERBHFUNDAMENTALSOFSPEECHRECOGNITION，PRENTICEHALLPRESS，199314MYERS，CSALRRACOMPARATIVESTUDYOFSEVERALDYNAMICTIMEWARPINGALGORITHMSFORCONNECTEDWORDRECOGNITIONTHEBELLSYSTEMTECH，1991，6071389140815YIBK，JAGADISHHV，FALOUTSOSCEFFICIENTRETRIEVALOFSIMILARTIMESEQUENCESUNDERTIMEWARPING201208，199816KEOGHE，RATANAMAHATANACAEXACTINDEXINGOFDYNAMICTIMEWARPINGKNOWLEDGEANDINFORMATIONSYSTEMS，2005，73358“38617XIONGY，YEUNGDTIMESERIESCLUSTERINGWITHARMAMIXTURESPATTERNRECOGNITION，2004，3781675“168918KALPAKISK，GADAD，PUTTAGUNTAVDISTANCEMEASURESFOREFFECTIVECLUSTERINGOFARIMATIMESERIESINTHEPROCEEDINGSOFTHE2001IEEEINTERNATIONALCONFERENCEONDATAMININGICDM01，273280，SANJOSE，CA200119KORNF，JAGADISHHV，FALOUTSOSCEFFICIENTLYSUPPORTINGADHOCQUERIESINLARGEDATASETSOFTIMESEQUENCESINPROCACMSIGMODINTERNATIONALCONFERENCEONMANAGEMENTOFDATA，289一一300，TUCSON199720PRATTKB，FINKESEARCHFORPATTERNSINCOMPRESSEDTIMESERIES兰州大学硕士研究生毕业论文INTERNATIONALJOURNALOFIMAGEANDGRAPHICS，2002，2189一10621KEOGHEJ，CHAKRABARTIK，PAZZANIMJ，ETA1DIMENSIONALITYREDUCTIONFORFASTSIMILARITYSEARCHINLARGETIMESERIESDATAB