（计算机应用技术专业论文）一种时序分类技术及其应用研究.pdf

中国科学技术大学碗l 学位论文一种时序分类技术鼓j ( 应用研究 摘要 时间序列是一类广泛存在于商业应用和科学研究中的复杂数据，如每i i 二；| 股票 价格、电信用户的每f = i 通话分钟数、太平洋每天海表面的温度值等。其复杂性表 现在：一般维数比较高，往往含有噪声：在幅度方面存在拉伸、平移，在时问轴 上存在拉伸等。 由于上述复杂性，传统的分类算法较难成功地用于时间序列数据。然而，现 实生活中很多决策依赖于时间序列的分类分析，例如通过分类一个病人的e c g 和e e g 的波形来判断该病人的心血管和中枢神经系统的运行情况或者分类语音 波形鉴别不同的讲话者。因此，研究用于时间序列数据的分类算法是非常重要的 和有挑战性的。 基于以上考虑，本文提出一种将时序相似性度量与k 近邻分类方法相结合的 时序分类方法。最后将该方法成功地应用于电信行业中的客户流失分析。本文的 主要工作和特色如下： 1 在分析了传统分类方法和时序相似性度量的基础上，筛选出种时序相似性 度量和k 一近邻分类方法相结合进行时序分类分析。详细设计了算法流程并分 析了算法的时间复杂度和空间复杂度。 2 针对国内现有的电信行业客户流失分析方法存在的问题，提出将上述时序分 类方法应用于客户流失分析。与应用c 4 5 算法的流失分析结果迸行比较， 发现本文提出的方法有较好的表现。 关键词：时序分类，数据挖掘，时序相似性度量，k 一近邻分类，流失 中国科学技术大学硕士学位论文 一种时序分类技术及其应用f 究 a b s t r a c t t i m es e r i e sd a t ao c c u r sf r e q u e n t l yi nb u s i n e s sa p p l i c a t i o n sa n di ns c i e n c e , f o r e x a m p l e ，i n c l u d i n gd a i l ys t o c kp r i c e s ，d a i l ym i n u t e so ft e l e p h o n ec a l l ，a n dd a i l y s e a s u r f a c et e m p e r a t u r er e a d i n g si nt h ep a c i f i c b e s i d e st h eh i g hd i m e n s i o n a l i t yo f t i m es e r i e sd a t a ，o n ec a ne n c o u n t e rv a r i o u sd i s t o r t i o n si n c l u d i n gn o i s e ，o f f s e t t r a n s l a t i o n ，a m p l i t u d es c a l i n gi nt i m es e r i e s d u et ot h ec o m p l e x i t yo ft i m es e r i e sd a t a ，a t t e m p t st ou t i l i z et r a d i t i o n a l a l g o r i t h m so fc l a s s i f i c a t i o no nt h ed a t ah a v en o tm e tw i t hg r e a ts u c c e s s h o w e v e r , m a n yd e c i s i o n - p r e d i c t i o n sl i eo nc l a s s i f i c a t i o nm e t h o dt oa n a l y z et i m es e r i e s ，f o r e x a m p l e ，u s i n ge c ga n de e gw a v e f o r m st o c h a r a c t e r i z et h ef u n c t i o n i n go fa p a t i e n t sc a r d i o v a s c u l a ra n dc e n t r a ln e r v o u ss y s t e m so ru s i n gs p e e c hw a v e f o r r n sa s a m e a n so fi d e n t i f y i n gd i f f e r e n ts p e a k e r s s oi ti ss i g n i f i c a n ta n dc h a l l e n g i n gt os t u d y t h ec l a s s i f i c a t i o nm e t h o d so f t i m es e r i e s o na c c o u n to fa b o v ef a c t o r s ，w ep r o p o s e dat i m es e r i e sc l a s s i f i c a t i o nm e t h o d t h i sm e t h o di n t e g r a t e s s i m i l a r i t ym e a s u r e sm e t h o do ft i m es e r i e sw i t hkn e a r e s t n e i g h b o rc l a s s i f i c a t i o nm e t h o d f i n a l l y , w ea p p l yt h et i m es e r i e sc l a s s i f i c a t i o nm e t h o d t oa s s e sc h u mr i s ko fc u s t o m e r si nt e l e c o m m u n i c a t i o n t h e m a i nw o r ka n d c h a r a c t e r i s t i co f t h et h e s i sa r e ： 1 w ef i r s t l ya n a l y z ec u r r e n ts i m i l a r i t ym e a s u r e sm e t h o d so ft i m es e r i e sa n d t r a d i t i o n a lc l a s s i f i c a t i o nm e t h o d s o nb a s i so ft h ea n a l y s i s ，w es e l e c t e da s i m i l a r i t ym e a s u r e sm e t h o do ft i m es e r i e sa n dkn e a r e s tn e i g h b o ri n t oo u r c l a s s i f i c a t i o nm e t h o do ft i m es e r i e s a n dw ed e s i g nf r a m eo ft h ea l g o r i t h ma n d a n a l y z et h er u n n i n gt i m ea n ds p a c eo fi t 2 i na l l u s i o nt ot h ep r o b l e m so fc u r r e n ta p p r o a c h e st oa s s e sc h u r nr i s ki n t e l e c o m m u n i c a t i o n ，w ea p p l ya b o v ec l a s s i f i c a t i o nm e t h o do ft i m es e r i e st oa s s e s c h u r nr i s k i nc o m p a r i s o nw i t ht h ee x p e r i m e n t a lr e s u l t sp r o d u c e db yc 4 5 ，w ec a n d r a wt h ec o n c l u s i o nt h a to u ra l g o r i t h mo u t p e r f o r m st h ec 4 5 中唇科学技术大学硕士学位论文 一种时序分类技术j ；5 乏其应用研究 k e yw o r d s ：t i m es e r i e sc l a s s i f i c a t i o n ，d a t am i n i n g ，s i m i l a r i t ym e a s u r e sm e t h o do f t i m es e r i e s ，k - n e a r e s tn e i 【g h b o rc l a s s i f i c a t i o n ，c h u r n 中国科学技术大学硕士学位论文 第一章绪论 1 1 数据挖掘概述 第一章绪论 1 1 1 数据挖掘的背景 目前数据库系统所能做到的只是对数据库中已有的数据进行存取，人们通过 这些数据所获得的信息量仅仅是整个数据库所包含的信息量的一部分，然而隐藏 在这些数据之后的更重要的信息是关于这些数据之间的关联性、归类性以及对数 据整体特征的描述和对其发展趋势的预测。这些信息在决策生成的过程中具有重 要的参考价值。但是超大数据量与无结构化，使得传统的手工和统计方法或者不 经济，或者在某些情况下几乎就不可能从中获得有意义的模式。因此，迫切需要 有新的更为有效的技术和工具对各种数据信息资源进行开采以发挥其应用潜能。 数据库中的知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，k d d ) 正是在这样的应 用需求背景下产生并迅速发展起来的，己经成为当前一个重要的研究领域。 定义1 1 数据库中的知识发现( k d d ) 是从大量的实际应用数据中，提取隐含 的、新颖的、潜在有用的信息和知识的非平凡过程u 1 。 数据挖掘( d a t am i n i n g ) 是知识发现( k d d ) 过程中的一个核心步骤，采用特定 的算法，在可接受的计算成本下，从数据集中搜索人们感兴趣的模式或模型。知 识、规则或高层次信息等都可以从包括关系数据库、数掘仓库、交易数据库、空 间数据库、时态数据库、时间序列数据库、文本数据库、多媒体数据库、w o r l dw i d e w e b 数据等各种数据源巾挖掘，其中后面几种都属于复杂类型的数据挖掘的对象 j 。数据挖掘能从各种角度对它们进行分析和应用，从而为人们从事科研和经济 实践提供了丰富的知识库。 k d d 是一个多阶段的处理过程，数据挖掘，t - 不是知识发现的全部。知识发 现还包括其它步骤，如数据选择和预处理、对挖掘结果进行恰当的评价和解释等 p j ，这些步骤对有效的知识发现过程来况也是必不可少的。一个完整的知识发现 过程共分为九个处理阶段，包括数据准备、数据选择、数据预处理、数据缩减、 中国科学技术大学硕士学位论文第一章绪论 k d d 目标确定、挖掘算法确定、数据挖掘、模式解释及知识评价。一个掠影如 图1 1 所示。 图1 1 知识发现过程 ( 1 ) 数据准备：了解k d d 相关领域的有关情况，熟悉有关的背景知识，并弄清 楚用户的要求。 ( 2 ) 数据选择：根据用户的要求从数据库中提取与k d d 相关的数据，k d d 将主 要从这些数据中进行知识提取，此过程中会利用一些数据库操作进行处理。 ( 3 ) 数据预处理：主要是对数据选择产生的数据进行加工，检查数据的完整性及 数据的一致性，对其中的噪音数据进行处理，对丢失的数据可以利用统计方 法进行填补。 ( 4 ) 数据缩减：对经过预处理的数据，根据知识发现的任务对数据进行再处理， 主要通过投影或数据库中的其它操作减少数据量。 ( 5 ) 确定k d d 的目标：根据用户的要求，确定k d d 是发现何种类型的知识，因 为对k d d 的不同要求会在具体的知识发现过程中采用不同的知识发现算 法。 ( 6 ) 确定知识发现算法：根据所确定的任务，选择合适的知识发现算法，这包括 选取合适的模型和参数，并使得知识发现算法与整个k d d 的评判标准相一 致。 ( 7 ) 数据挖掘：运用选定的知识发现算法，从数据库中提取出用户所需要的知识， 以一种特定的方式或一螳常用的表示方式表示知u ，如产小式规则等。 ( 8 ) 模式解释：对发现的模式进行解释。通常为了取得业为有效的知以，川。能会 返回前面处理步骤中的某些步骤以反复提取，从而得到更有效的知识。 酗f_iili_r：_=芏 ：l了。一 一露 中国科学技术大学硕士学位论文 第一章缔论 ( 9 ) 知识评价：将发现的知识以用户能理解的方式呈现给用户，也包含对知识的 一致性的检查，以确信本次发现的知识不与以前发现的知识相抵触。 在上述的每个处理阶段k d d 系统会提供处理工具完成相应的工作。在 对挖掘的知识进行评测后，根据结果可以决定是否重新进行某些处理过程， 在处理的任意阶段都可以返回以前的阶段进行再处理。 1 1 2 数据挖掘系统的分类 数据挖掘是- - 1 9 交叉学科，受多个学科的影响，包括数据库系统、统计学、 机器学习、可视化和信息科学等。此外依赖于所用的数据挖掘方法，以及可以使 用的其他学科技术，如神经网络、模糊逻辑、粗集理论、知识表示、归纳逻辑程 序设计或高性能计算等。 从不同的角度出发，对数据挖掘系统有几种分类，主要是根据挖掘的数据库 的种类、根据得到的知识分类和所使用的技术分英p j 。 ( 1 ) 根据数据库分类数据挖掘所基于的数据库类型有：关系型、事务型、面 向对象型、空间型、时序型、多媒体型、文本挖掘和基于网络信息的挖掘等。 ( 2 ) 根据得到的知识分类包括关联规则、特征规则、分类规则等的挖掘和 聚类、演变( e v o l u t i o n ) 分析、偏差( d e v i a t i o n ) 分析、孤立点分析和相似性分析 等，此外根据所挖掘的知识的抽象层次进行划分，可以包括原始层知识( 在原始 数据层) 、多层次知识和高层次知识的数据挖掘。 ( 3 ) 根据所采用的技术分类常用的数据挖掘技术有 人工神经网络：它从结构上模仿生物神经网络，是一种通过训练来学习的非 线性预测模型。可以完成分类、聚类和特征挖掘等任务。 判定树：用树型结构来表示决策集合。这些决策集合通过对数据集的分类产 生规则，典型的判定树方法有分类回归树( c a r t ) ，c 4 5 等，其典型应用为分类规 则的挖掘。 遗传算法：是一种新的优化技术基于生物进化概念设计了一系列的过程柬 达到优化的目的。这些过程有基因组合、交叉、变异和自然选择等。遗传算法易 于并行计算，并且已经应用于分类和其他优化问题。 粗集理论：它是一种研究不确定性问题的数学 二具，作为集合沦的扩展，主 中国科学技术大学硕士学位论文 第一章绪论 要用于研究不完全和不完整信息描述的数据挖掘技术。可以用于分类，进行特征 归约和最小属性子集归约。 模糊逻辑：通过隶属度函数定义分类系统的“模糊”阈值或边界，从而可以 产生人们易于理解的分类规则。 最近邻技术：通过k 个与之桐近的历史记录的组合来辨别新的记录，也称为k 一 最近邻技术。主要应用于分类、聚类和偏差分析等。 可视化：采用直观的图形方式将信息模式、数据的关联或趋势呈现给决策者， 决策者可以通过可视化技术交互式地分析数据关系。 目前，世界上比较有影响的典型数据挖掘系统有： ( 1 ) i n t e l l i g e n tm i n e r i b m 公司的数据挖掘产品，提供了很多数据挖掘算法，包括关联、分类、回 归、预测模型、偏离检测、序列模式和聚类。同时提供一个应用工具集，包括神 经网络算法、统计方法、数据准备模型和数据可视化工具。i n t e l l i g e n tm i n e r 的特 色有：一是数据挖掘算法的可伸缩性：二是它与i b md b 2 关系数据库紧密地结 合在一起。 ( 2 ) e n t e r p r i s em i n e r s a s 公司开发的产品( h t t p ：w w w s a s c o m ) ，提供多种数据挖掘算法，包括回 归、分类和统计软件分析包。特色是具有多种统计分析工具，这得益于s a s 公 司在统计分析市场多年的经验和历史。 ( 3 ) m i n e s e t 由s g i 公司( s i l i c o ng r a p h i c si n c ) 丌发的( h t t p ：w w w s g i c o m ) 。它也提供 了多种数据挖掘算法，包括关联和分类以及高级统计和可视化工具。特色是具有 强大的图形工具( 利用s g i 计算机强大的图形能力) ，包括规则可视化工具、树 可视化工具、地图可视化工具和多维数据分散可视化工具，用于实现数据和数据 挖掘结果的可视化。 ( 4 ) c l e m e n t i n e 由i s l 公司( i n t e g r a ls o l u t i o n sl t d ) 丌发的( h t t p ：w w w i s t c o u k ) 。它为终端 用户和开发者都提供了一个集成的数据挖掘，l ：发环境。系统集成了多剥数据挖掘 算法，如规则归纳、神经网络、分类和可视化工具。特色是具有面向对象的扩展 中国科学技术大学硕士学位论文 第一章绪论 的话模块接口，该接口使用户算法和工具可以加到c l e m e n t i n e 的可视化编程环 境中。i s l 已被s p s s 公司收购。 ( 5 ) d b m i n e r 由d b m i n e r t e c h n o l o g y 公司开发的( h t t p ：d b c s s f u c a ) ，提供多种挖掘算法， 包括发现驱动的o l a p 分析、关联、分类和聚类。特色是基于立方体的联机分 析挖掘，包括多利t 有效的频繁模式挖掘功能和集成的可视化分类方法【5 j 。 1 2 时间序列分析 时间序列是一串随时问变化的数据组成的序列，反映了属性值在时间顺序上 的特征。现实世界中大量数据的采集与时间相关，数据具有时间上的关联性。 时间序列，简称为时序，其取值一般在等时间间隔上度量j ，分析这些序列 的方法称作时间序列分析，简称时序分析。时间序列x 是一个观察数据序列， x = x ，0 t v ，v 是属性a 的一些取值。若属性a 有v 个取值，则对属性a 的测试可以看成对v 1 个可能的条件测试。 ( 2 ) 信息增益方法偏向于选择取值较多的属性，采用考虑每个属性取值概率 的增益比率方法或其他的诸如：g i n i 索引方法、x 2 条件统汁表方法和g 统计方法进行改进。 ( 3 ) 提出处理遗失数据的方法，利用属性a 中最常见的值来替代一个遗失或 未知属性a 的值。其他方法还包括：利用属性a 中出现次数最多的数值， 或利用属性a 与其他属性之间的关系。 ( 4 ) 可以生成分类规则。引入剪枝技术，简单化生成的树。 i d 3 算法及其后继版本c 4 5 算法局限于在计算机内存中处理整个数据集， s l i q 方法和s p r i n t 方法是比较有代表的解决有关判定树可扩展性问题的方法。 判定树归纳方法可以与数据仓库技术结合到一起进行数据挖掘工作。以及在分稚 式数据库中采用分级判定树进行知识发现。 1 判定树最适合实例具有“属性一值”叫的分类分析问题，最简单的判定树 只允许属性取少数的离散值，在后续的扩展算法中，允许属性的值域为实数，如 c 4 5 算法。 2 1 2 贝叶斯分类和贝叶斯网络 贝叶斯分类器是基于贝叶斯定理而构造出来的统计分类器，能够预测类别所 属的概率。设x 为一个类别未知的数据样本，h 为某个假设，若数据样本x 属 于一个特定的类别c ，那么分类问题就是决定p ( h i x ) ，即在获得数据样本x 时， h 假设成立的概率。p ( h i x ) 是事后概率，或为建立在x 之i z 的h 概率。类似的， p ( x i h ) 是建立在h 基础之上的x 成立概率。p ( x ) 、p ( h ) 和p ( x i h ) 的概率值可以 从数据集合中得到，贝叶斯定理则描述了如何根据p ( x ) ，p ( h ) 和p ( x i h ) i 算获得 的p ( h i x ) ，有关的具体公式定义描述如下： p ( h i x ) = p ( x l h ) p ( h ) p ( x 1 中国科学技术大学硕十学位论文第二章时序分类臼勺相关研究1 。作 最简单的贝叶斯分类器是基本贝叶斯分类器( n a i v eb a y e s i a nc l a s s i f i e r s ) ，它 假设一个指定类另i j 中各属性的取值是相互独立的。 从理论上讲与其他分类器相比，贝叶斯分类器具有最小的错误率，但实际上由 于其所依据的类别独立性假设和缺乏某些数据的准确概率分布，从而使得贝叶斯 分类器预测准确翠受到影响。 基本贝叶斯分类器是基于各类别相互独立这一假设来进行分类计算的，这一 假设简化了分类计算复杂性但实际上变量拣的相互依赖情况是较为常见的贝叶 斯信念网络就是用于描述这种相互关联的概率分布该网络能够描述各属性子集 之间有条件的相互独立它提供了一个图形模型来描述其中的因果关系，而学习也 正是基于这一模型进行的这一图形模型就称为贝叶斯信念网络一个信念网络包 含两部分内容：第一部分就是有向无环图，第二个部分就是包含所有变量的条件 概率表 在一个贝叶斯信念网络的学习或训练过程中，其网络结构必须首先事先确定 或从数据库中推出网络所涉及变量必须是可观察或隐含在训练数据集合中若隐 含在数据中，就称为数据遗失或不完全若网络结构确定且所涉及变量均为可观察 的，那么就可以进行网络学习了，这其中包括：计算c p t 表的入口，与基本贝叶斯分 类方法中的概率计算过程类似。 2 1 3 神经网络 所谓神经网络就是一组相互连接的输入输出单元，这些单元之间的每个连接 都关联一个权重。在网络学习阶段网络通过调整权重来实现输入样本与其相应 ( 正确) 类别的对应。由于网络学习主要是针对其中的连接权重进行的，因此神 经网络的学习有时也称为连接学习。 鉴于神经网络学习时问较长，因此它仅适用于时间容许的应用场合。此外它 们还需要些关键参数，如网络结构等；这些参数通常需要经验方能有效确定。 由于神经网络的输出结果较难理解，因而受到用户的冷落，也使得神经网络较难 成为理想的数据挖掘方法。 神经网络的优点就是对噪声数据有较好适应能力，并且列未知数据也具有较 好的预测分类能力。目前人们也提出了一些从神经网络中抽取出( 知识) 规则的 中国科学技术犬学硕= 卜学位论文第二章时序分类的相关_ | i j f 究t 作 算法。这些因素又将有助于数据挖掘中的神经网络应用。 八十年代初，人们提出了神经网络后传算法，该算法通过不断处理一个训练样 本集，并将网络处理结果与每个样本已知类别相比较所获误差，来帮助完成学习任 务。对于每个训练样本，不断修改权重以使网络输出与实际类别之间的均方差最小 权重的修改是以后传方式进行的，即从输出层开始，通过之后的隐含层，直到最后 面的隐含层。 多层前馈网络是利用该算法的一种典型神经网络。一个多层前馈神经网络利 用后传算法完成相应的学习任务如图所示就是一个神经网络示意描述其中的。 其中的输入对应每个训练样本的各属性取值；输入同时赋给第一层( 称为输入层) 单元，这些单元的输出结合相应的权重，同时反馈给第二层( 称为隐藏层) 单元： 隐藏层的带权输出又作为输入再反馈给另一隐含层等等，最后的隐含层结点带权 输出给输出层单元，该层单元最终给出相应样本的预测输出， w 1 ”j 图2 。l 一个多层前馈神经网络的示意描述 如上图2 1 所示，它包含两层处理单元( 除输入层外) ，该网络是前馈的，即每一 个反馈只能发送到秘面的输出层或隐含层它又是全连接的，即每一个层中单元均 与前面一层的各单元相连接 神经网络的一个主要缺点就是网络所隐含知识的( 清晰) 表示。以网络及其 各单元间连接的权值和偏差所构成的( 学习所获) 知识难以被人理解。如何从神 经网络中抽取相应的知识并以( 易于理解的) 符号形式加以描述己成为神经网络 研究中的一个重点。相关的方法包括：神经网络规则的抽取和网络敏感性分析。 目前已提出了许多从神经网络中抽取规则知识的方法。这些方法基本都是通过对 网络结构、输入值的离散化和神经网络训练过程等加以约束限制来实现的。完全 连接的网络难以清楚描述出来。但通常( 从神经网络中) 抽取规则的第一步就是 中国科学技术人学硕1 ：学位硷义 笫_ - 二章时序分类的相关研究丁作 网络消减。这一过程包括：除去网络中不会导致网络预测准确率下降的带权连接。 2 。2 基于实例的学习方法 2 2 1 k _ 近邻算法 k 最近邻分类器是基于类比学习的分类方法。训练样本是出n 个数值属性所 描述。每个样本代表n 维空间中的一个点，这样所有的样本就被存放在n 维空间 中。当给定一个未知( 类别) 数据对象，一个k 一最近邻分类器就搜索n 维空问， 并从中找出k 个与未知数据对象最为接近的训练样本，这k 个训练样本就是未知 数据对象的“k 个最近邻”。所谓最近就是指n 维空间中两点之间的欧氏距离最 小，r l 维空问中两点x = x l ，x 2 ，x n 和y = y l ，y 2 ，y n 之间的欧氏距离就是： d ( x ，) =撂，2 这样未知类别的数据对象就被归属于这k 个最近邻中出现次数最多的类别。 而当k = l 时，未知类别的数据对象就被归属于最接近它的一个训练样本所具有的 类别。 最近邻分类器是基于实例学习或懒惰学习( 1 a z yl e a r n i n g ) 方法，因为它实际 并没有( 根据所给训练样本) 构造一个分类器，而是将所有训练样本首先存储起 来，当要进行分类时，就临时进行计算处理。与积极学习方法，如判定树归纳方 法和神经网络方法相比，后者在进行分类前就已构造好一个分类模型；但前者， 消极学习方法，在当训练样本数目迅速增加时，就会导致最近邻的计算量迅速增 加。因此懒惰学习方法需要有效的索引方法支持。就学习而言，懒惰学习方法比 积极学习方法要快，但懒惰学习方法在进行分类时。需要进行大量的计算，因此 这时它要比积极学习方法慢许多。此外与判定树归纳方法和神经网络方法不同的 是，最近邻分类器认为每个属性的作用都是相同的( 赋予相同权值) 这样在属 性集包含有v t ：多不相关属性时，就会误导分类学习过程 距离加权最近邻算法是对k 一近邻算法的一个明显的改进。根据近邻相对查询 点x 。的距离将较大的权值赋给较近的近邻。例如，可以根据每个近邻与x q 的距离 平方的倒数加权近邻的“选举权”。按距离加权的k 一近邻算法是一种非常有效的 中国科学技术大学颁七学位论文第二章时序分类的相关训究丁作 归纳推理方法。它对训练数据中的噪声有很好的健壮性，而且当给定足够大的训 练集合时也非常有效。通过取k 个近邻的加权平均，可以消除孤立的噪声样例的 影响。 应用k 一近邻算法的一个实践问题是，实例间的距离是根据实例的所有属性计 算的。这与那些只选择全部实例属性的一个子集的方法不同，例如判定树学习系 统。为了理解这种策略的影响，考虑把k 近邻算法应用到这样一个问题：每个实 例由2 0 个属性描述，但在这些属性中仅由2 个与它的分类有关。结果，依赖这2 0 个属性的相似性度量会误导k 近邻算法的分类。近邻间的距离会被大量的不相关 属性所支配。这种由于存在很多不相关属性所导致的难题，有时被称为维度灾难。 解决维度灾难的一个方法是：当计算两个实例间的距离时，对每个属性加权。 这相当于按比例缩放欧氏空间中的坐标轴，缩短对应于不太相关的属性的坐标 轴，拉长对应于更相关的属性的坐标轴。每个坐标轴应伸展的数量可以通过交叉 验证的方法自动决定。具体做法如下，首先，假定使用因子z | 1 中展( 乘) 第i 个根 坐标轴，选择z i 的各个值z 1 z n 以使学习算法的真实分类错误率最小化。其次。 这个真实错误率可以使用交叉验证来估计。所以，一种算法使随机选取现有数据 的一个子集作为训练样例，然后决定2 1 - z 。的值。使剩余样例的分类错误率最小 化。通过多次重复这个处理过程，可以使加权因子的估计更加准确。这种伸展坐 标轴以优化k 一近邻算法的过程，提供了一种抑制无关属性影响的机制。 另一个方法是：从实例空问中完全消除最不相关的属性。这等效于设置某个 缩放因子z i 为0 。这种方法可以被看作以某个常量因子伸展坐标轴。另外一种可选 的做法时使用一个在实例空间上变化的值伸展雀标轴。这样增加了算法重新定义 距离度量的自由度，然而夜增加了过度拟合的风险。所以，局部伸展坐标轴的方 法是不太常见的。 应用k - 近邻算法的另外一个实践问题是如何建立高效的索引。因为这个算法 推迟所有的处理，直到接收到一个新的查询，所以处理每个新查询可能需要大量 的计算。目前已经丌发了很多方法用来对存储的训练样例进行索引，以便在增加 一定存储开销情况下更高效地确定最近邻。 中国科学技术大学硕士学位论文 第二章时序分类的相关研究t 作 2 2 2 基于案例的推理 与k 一近邻方法不同的是，基于案例的推理( c b r ) 方法具有如下特征： ( 1 ) 实例或案例可以用丰富的符号描述表示，例如c a d e t 系统州中使用的 功能图，c a d e t 系统是一种采用基于案例的推理来辅助简单机械设备的 总体设计的系统。相应地，相似性搜索时，可能需要不同于欧氏距离的 相似性度量，而是采用诸如两个功能图的最大可共享子图的大小。 ( 2 ) 检索到的多个案例可以合并形成新问题的解决方案。这与k 近邻方法相 。似一多个相似的案例用来构成对新查询的回答。然而，合并多个检索到 的案例的过程与k 近邻方法有很大的不同，它依赖于知识推理而不是统 计方法。 ( 3 ) 案例检索、基于知识的推理和问题求解问时紧密耦合在一起的。例如 c a d e t 系统在尝试找到匹配的案例过程中，它使用有关物理感应的一般 知识重写了功能图。人们已经_ 丌发出很多其它的系统，这些系统更加完 整地把基于案例的推理集成到基于搜索的问题求解系统中。 在基于案例的推理方法中，实例( 案例) 可以是丰富的关系的描述。在解决 当前查询时，案例检索和合并过程可能依赖于知识推理和搜索密集的问题求解方 法。 目前关于基于案例的推理研究的一个课题是，改进索引案例的方法。其中心 问题是句法相似度量( 例如，功能图之间的子图同构) 仅能近似地指出特定案例 与特定问题的相关度。当c b r 系统试图复用检索到的案例时，它可能遇到句法 相似度量中没有捕捉到的难点。当这种情况发生时，c b r 系统可回溯搜索另外 的案例以适应现有的案例，或者求助于其它的问题求解方法。重要的是，当检测 到这样的难点时，它们也提供了用来改进相似性度量( 或等价的，案例库索引结 构) 的训练数据。确切地讲如果根据相似性度量检索到了一个案例，但在进一 步的分析中发现这个案例与当前的设计是无关的。那么这个相似性度量会被改 进，以便对于以后的类似查询拒绝这个案例。 7 中国科学技术大学硕：l 学位论艾第一：章时序分类的相关耐究t 作 2 3 相似性度量 由于时态语义的特殊性，时序模式并不是一个形如y = f m 的函数表达式 当判断两个模式是相似时，常常允许某种程度的变形例如，图l 中的几组模式是 相似的，但它们都在局部上存在着某种程度的变形【19 1 。 类。 域* 卡批c 拍w 学 7 氇穆 o 仃撕t r l t t t f l a l t 傀, 拽摊i l l 咎i h ，d “m 水连蝰性枷斌埘“州i l b ) 八八八、 卜、m 八、八八 八、八 图2 2 时序模式的几种变形 研究者们已经提出了很多相似性度量方法。我们将其简要地归纳为下丽几 2 3 1 基于距离的度量 两个时间序列之间的“相似”通过距离函数来衡量，相似性和距离成反比关 系，距离越近，说明愈相似。从不同的角度又可以分为： ( 1 ) 欧几里德( e u c l i d e a n ) 距离 设有时间序列x = x o ，x i , - - - , x 。+ i 和y = y 0 ，y i _ ，y n + l ，将每个序列看成是n 维空恻 中的一个点，这里n 为序列的长度，x 和y 之间的距离定义为： 一| b ( x ，y ) = ( ( 气一卫y ) t - “；b q = l ，为m a h a t a n 距离，q = 2 ，为欧氏距离。 当两个序列之间的距离小于一个给定阂值，即d ( x ，y ) e ，我们认为x 和y 是相似的，否则称它们是不相似的。文献 2 0 】中采用欧氏距离作为相似性度 量。 这种方法的优点是容易计算，可以支持索引、聚类等问题的解决。缺点是不 支持平移，如股票x 在$ t o o 波动，而股票yn $ 3 0 波动；股票x 在$ 9 5 币n $ 1 0 5 中国科学技术人学碗 学位论史第二章时序分类的相关研究t 作 之间波动，而股票之间波动，而股票y 在$ 2 0 和$ 4 0 之间波动。 我们也可以先对序列进行标准化，即采用序列的均值( m e a n ) 和方差 ( v a r i a n c e ) 进行规范化，然后采用欧几里德距离度量。设“( x ) 和p ( x ) 为序列x 的均值和方差，标准化定义为： x 。= ( x ，一u ( x ) ) ，p ( x ) 序列进行标准化之后，相似性依然太严格，不允许噪声和短期波动：不允许 时间轴上的相位平移；不允许时间轴上的伸缩。 ( 2 ) 动态时间弯曲距离 动态时间弯曲( d y n a m i c t i m e w a r p i n g ) 广泛用于语音识别领域，允许信号沿 着时间轴对模式进行伸缩变换，以使查询模式q 与参考模式r 相匹配。它的基 本思想是：考虑时间序列x = x o ，x i , - - x n _ l 和y = y o ，y i ，- 一，y 。1 i ，允许通过重复元素扩 展每个序列，欧氏距离在扩展序列x ，年ny 之问计算。 设d ( i j ) 表示子序列x o , x l ，x ，和y o ，y l , - - - , y j 之间的动态弯曲距离，用公式 表示： d ( i , j ) 2 x i y j + m i n d ( i - l j ) ，d ( i l j 一1 ) ，d ( i , j - 1 ) 对弯曲路径作如下限制：( 1 ) 单调性：路径应该不能向下或向左：( 2 ) 连续 性：在序列中没有间断的点：( 3 ) 边界条件：弯曲路径要在矩阵的单元丌始和结 束。 用动态规划的解决方法，实现时问复杂度是0 ( n + m ) 。这罩n 是序列的长度， 需要计算每个( i ，j ) 组合。如果弯曲窗口满足- i i - jj w ，则复杂度为o ( n w ) 。文献 2 1 采用这种方法作为相似性度量。 动态时间弯曲距离的优点是：支持时间轴的伸缩；缺点是计算的代价高。 ( 3 ) 编辑距离 编辑距离( e d i t i n gd i s t a n c e ) 是度量一个模式近似出现的标准。两个序列a 和b 间的编辑距离定义为将a 转换为b 所需要的最小编辑步数，即将a 转换为 b 的最小代价。有如下三种形式的编辑步法：删除、插入和改变。编辑距离公式 如下： d ( o j ) = 00 j i q 中国科学技术大学硕士学位论文 第二二章时序分类的相关研究t 作 中国科学技术大学顾卜学位论文 筇二章时序分类的相关研究 作 界标距离的优点是度量方法直观，支持平移、幅度伸缩、时间弯曲等。 2 3 2 基于特定逻辑表示的度量 ( 1 ) 基于小波变换 文献 2 4 】基于小波变换提出了两类相似评价标准。一种是全局上的，根据全 局伸缩的性质，用小波变换导出h u r s t 指数来分类时间序列的统计特征来计算相 似性：另一种是面向时间序列局部细节的度量，采用小波变换的模极大尺度位 置分枝表示。 小波变换方法的优点是达到了信号压缩的目的，计算速度快，可以支持非欧 氏距离的度量。但是小波变换要求信号的长度n = 2 1 ，i 是某个整数。不支持加权的 距离度量。 ( 2 ) 基于线性分段 蔡智等，在文献 1 9 中提出一种以线段序列的斜率反正切值序列来表示时 序的方法。这种方法认为当某两段时序数据具有相同趋势时，它们属于同一模式。 衡量两个数据段的趋势是否相同，用斜率的反正切值是一个很好的选择，因为趋 势相似的两个线段其斜率反正切值必然相近，而且，数值上的偏移和漂移将不会 造成大的影响，因为我们关心的是其趋势及序列的形状特征。这样子序列和序列 模式的特征可用一系列线段序列的斜率反正切值序列来表示。 这种方法有着较强的优势：对于噪声和不确定性数据有较好的抗干扰性；时 间和空间上的花费较小：需要调整的参数较少等特点。 ( 3 ) 其它 k e o g h 等提出基于概率论方法的快速相似模式匹配模型【2 5 1 ，和基于相似性的 概率方法，采用时删序列q 和r 之问的概率距离进行度量，能有效地结合先验知识， 处理噪声和匹配过程中的不确定性。 文献 2 6 提出一个检索和表示时间序列部分信息( p a t i a i n f o r m a t i o n ) 的模 型和基于部分信息评价相似度量的方法。 2 中国科学技术大学硕士学位论文筘二章时序分类的相关研究t 作 2 4 本章小结及本文思路 在本章第一节中，我们回顾了数据分类的基本技术，如判定树归纳、贝叶斯 分类和贝叶斯网络、神经网络。这些方法有一个共同的特点：在分类新实例之前， 都会建立一个描述重要数据类的模型。因此，从这种观点出发，我们可以称这些 方法为基于模型的分类方法( m o d e l b a s e dc l a s s i f i c a t i o nm e t h o d ) 。它们主要集中用 于单一或彼此间独立的属性值来学习构造一个分类模型。而时间序列的属性值是 和时间紧密相关的，一般是连续的、高维的数据。 传统分类方法如何从这些具有连续、高维的属性值的实例中学习构造分类模 型呢? 文献 2 7 提出一种解决方案：从时间序列数据中抽耿决定时恻序列的行为 发展趋势的静态属性，组成静态数据库。然后将泛化性能较强的分类技术应用于 静态数据库中挖掘分类规则，对行为发展趋势做出预测。但是这种方法的前提是 必须抽取能反应时间序列行为发展趋势的静态属性，且对分类方法的泛化性能有 较高的要求。由于这两方面的困难，因此传统的分类方法应用于时间序列的分类 分析问题时并没有取得较大的成功。 除了上述基于模型的分类方法外，本章还介绍了基于实例的学习方法，如k 近邻算法、基于案例的推理。与基于模型的分类方法不同的是，这种方法在学习 阶段只是简单地把训练样例存储起来，从这些实例中泛化的工作推迟到必须分类 新的实例时。每当学习器遇到一个新的查询实例时，它分析这个新实例与以前存 储的实例之间的关系，并据此把一个目标函数值赋给新实例。如k 近邻算法中， 当遇到新的查询实例时，计算查询实例与训练实例之间的欧氏距离，然后确定距 离查询实例的k 个近邻，在基本的k - 近邻算法中，将近邻中最普遍的类标号作为 查询实例的类标号。 因此我们可以考虑将时序的相似性度量引入到k - 近邻算法中，作为k - 近邻算 法的距离定义标准。只要选择合适的、高效的相似性度量，找出查询实例的k 个近邻，最后的分类问题就可以转化成一般的分类问题，时序分类的复杂性可以 得到最大程度的简化。 一旦我们确定了将时序的相似性度量引入到k - 近邻算法中用于时序分类这 一思路后，问题就转变成了如何选择或设计适合的相似性度量。 本章第四节回顾了基于不同标准的相似性度量，主要包括基于距离f 内度量和 中国科学技术大学删士学位论文 笫二章时序分类的相关研究t 作 基于特定逻辑表示的度量。在基于距离的度量方法中，欧氏距离对于相似模式的 形变比较敏感，动态弯曲距离的计算代价又较高。 而基于特定逻辑表示的相似性度量，是建立在对时间序列进行有效描述的基 础上，这样可以提高相似性搜索的效率，如蔡智等在文献【1 9 】中提出的一种分段 线性化及拟合变换的方法就是一种高效、简单、能排除相似模式形变的影响的方 法。 因此，本文选择这种分段线性及拟合变换的方法对时间序列进行有效的描 述，再以序列间同类子模式的数量作为衡量查询实例的近邻的标准。在下一章， 我们将详细描述结合这种相似性度量方法的k 近邻分类算法。 中国科学技术大学硕十学位论文第三章苯于时序相似牲度量的k 近邻分类算法 第三章基于时序相似性度量的k - 近邻分 类算法 本章将详细描述基于时序相似性度量的k 一近邻分类算法的流程、各个功能模 块的定义和分析算法的时间复杂度和空间复杂度。 为了方便后续的描述，以下将基于时序相似性度量的k 一近邻分类算法简称为 k - 近邻时序分类方法( 简写为k n n - t s c ) 。下面的叙述都以k n n t s c 算法代称基 于时序相似性度量的k 一近邻分类算法。 3 1 算法流程 k n n t s c 算法的核心结构是表3 ，l 中描述的逼近离散值函数f 的k 近邻算 法【17 】的结构。 逼近离散值函数f ：r “- - v 的k 一近邻算法 训练算法： 对于每个训练实例 ，把这个实例加入到列表t r a i n e x a m p l e s 分类算法： 给定一个要分类的脊询实例。q 在t r a i n _ e x a m p l e s 中选出最靠近x q 的k 个实例，并用x 1 ，x k 表示 返同 k 胀q ) 。舯。6 ( v ，f ( x i ) ) j