（管理科学与工程专业论文）基于粗糙集和决策树理论的时态增量算法.pdf

浙江工业大学硕士学位论文 基于粗糙集与决策树理论的时态增量算法 基于粗糙集与决策树理论的时态增量算法 摘要 时态数据挖掘是数据挖掘中一个重要的研究课题，有其自身的特 点，它需要在数据挖掘过程中考虑数据集中各数据之间存在的时间关 系。决策树和粗糙集是数据分类的两个最重要的方法，决策树在知识 表示上有层次、自然和推理易理解的特点，而粗糙集理论在处理数据 模糊和不确定性方面有着优势，对于增量时态数据，我们将借鉴决策 树算法思想对转换后的时态序列数据处理，在构造决策树过程中，利 用粗糙集理论来优化决策树的构造和规则的提取，从而提出一种新的 增量式分类挖掘算法。 本文首先给出了与时态数据有关的数学概念以及相关性质，介 一一_ ：一 一 绍了时态数据转化方法并给出了其改进的算法。然后介绍决策树分 类算法和粗糙集基础理论，接着分析了决策树分类算法固有的缺点 以及应用于时态数据分类挖掘中的缺点，提出了基于粗糙集与决策 树理论的时态增量算法，最后给出算法的应用实例，对股票的数据进 行分析，给出实验结果。 本文的主要贡献是提出了改进的时序转化方法，在构建决策树的 过程中，优化了信息熵的计算，提出了时间特性属性组合的思路和用 粗集理论的相关概念对生成的决策树进行剪枝处理思路，在增量数据 处理问题上，针对本文的时态数据处理方法，提出对应的增量数据处 l 浙江工业大学硕士学位论文 基于粗糙集与决策树理论的时态增量算法 理方法。本文所做的贡献对于时态数据分类挖掘具有一定的意义。 关键词：时态数据，分类挖掘，时态数据转化，决策树算法思想， 粗糙集理论，增量式挖掘 i l 浙江工业大学硕士学位论文 基于粗糙集与决策树理论的时态增量算法 i n c r e m e n t a la l g o r i t h m sf o rt e m p o r a l d a t am i n i n gb a s e do n r o u g hs e tt h e o r ya n dd e c i s i o nt r e e a b s t r a c t t e m p o r a ld a t am i n i n gi s a l li m p o r t a n ta r e ao nd a t am i n i n ga n di th a si t so w n c h a r a c t e r i s t i c w h e na n a l y z i n gt e m p o r a ld a t a , y o uh a v et ot a k et i m ea t t r i b u t ei nt o c o n s i d e r a t i o n t h ed e c i s i o nt r e ea l g o r i t h ma n dr o u g hs e tt h e o r yb o t ha l ei m p o r t a n t m e t h o do fc l a s s i f yi nd a t am i n i n g a st h ed e c i s i o nt r e ea l g o r i t h mh a sa d v a n t a g ei n m a k i n gt h er u l e se x t r a c t e dc l e a ra n dn a t u r a lo ne x p r e s s i o n ，k n o w l e d g ea c q u i r e di s e a s yt ou n d e r s t a n da n ds p e c u l a t e ，w h i l et h er o u g hs e tt h er o u g hs e tt h e o r yh a s a d v a n t a g ei np r o c e s s i n gd a t at h a ti sf u z z ya n du n c e r t a i n , c o n s i d e r i n gt h es i t u a t i o ni n t h er e a lw o r l dt h a tt h ed a t aa r ei n c r e a s i n ge v e r y d a y , w et a k ea d v a n t a g eo ft h ec l a s s i c c l a s s i f ya l g o r i t h md e c i s i o nt r e ea l g o r i t h m sm a i np r o c e s sp r o c e d u r et o d e a l 、析t l l 。q 劢n p o r a ld a t aw h i c hi st r a n s f e r r e d i nt h ep r o c e s s i n go fc r e a t i n gad e c i s i o n - t r e e ，w e m a k eg o o du s eo fr o u g hs e tt h e o r yt oo p t i m i z et h ep r o c e s so fb u i l d i n gt h ed e c i s i o n t r e ea n dd r a w i n gu s e f u lr u l e s ，t h e np e r s e n ta ni n c r e a m e n t a lc l a s s i f yd a t am i n i n g a l g o r i t h m = 一一二 t h i sp a p e rf i r s t l y i n t r o d u c e st h em a t h e m a t i c sc o n c e p tr e l a t e dt ot e m p o r a ld a t a t h e ni n t r o d u c e st h em e t h o da b o u tt r a n s f e r r i n gt e m p o r a ld a t ai n t ot h ed a t aw i t h o u tt i m e a t t r i b u t e ，p r o p o s i n gan e wm e t h o dt op r o c e s st h i sp r o c e d u r e t h e ni ti n t r o d u c e st h e b a s i ct h e o r ya b o u td e c i s i o n t r e ec l a s s i f i c a t i o na l g o r i t h ma n dr o u g hs e tt h e o r y , a n a l y z i n gt h es h o r t c o m i n go nd e c i s i o nt r e ea l g o r i t h m ，e s p e c i a l l yo nd a t am i n i n gf o r t e m p o r a ld a t ac l a s s i f i c a t i o na r e a a tl a s t ，t h i sa r t i c l ep r o p o s e si n c r e m e n t a la l g o r i t h m s f o rt e m p o r a ld a t am “n gb a s e do nr o u g hs e tt h e o r ya n dd e c i s i o nt r e e ，t h e ni t g i v e sa ne x a m p l e o ns t o c km a r k e td a t am i n i n g ，a p p l y i n gt h i sa l g o r i t h m n em a i nw o r ko ft h i sp a p e rp r o p o s e sa ni m p r o v e dt h em e t h o do ft r a n s f e r r i n g t e m p o r a ld a t ai n t ot h ed a t aw i t h o u tt i m ea t t r i b u t e i nt h ep r o c e s s i n go fb u i l d i n ga t r e e ，a ni m p r o v e dt h em e t h o do fc a l c u l a t i n gi n f o r m a t i o ne n t r o p y ，a n ds u g g e s t e d c o m b i n i n gs o m et i m ea t t r i b u t e sa so n ec o m b i n a t i v et e s ta t t r i b u t ew h e nn e c e s s a r y ，a n d u s er o u g hs e tt h e o r yt oc u to f fs o m eu s e l e s sr u l e s ，w h e np r o c e s s i n gi n c r e a s i n g l t l 浙江工业大学硕士学位论文基于粗糙集与决策树理论的时态增量算法 d a t a ，w et a k ec o n s i d e r a t i o no ft h i sa r t i c l e sp r o c e s s i n gi nt e m p o r a ld a t a ，b r i n gf o r w a r d c o r r e s p o n d i n gi n c r e m e n td a t ah a n d l i n gm e t h o d t os o m ee x t e n t , t h i sp a p e ri sm a k i n ga t t r i b u t i o nt oc a l s s i f yd a t am i n i n ga r e a k e y w o r d s ：t e m p o r a ld a t am i n i n g ；c l a s s i f yd a t am i n i n g ； t r a n s f e r r i n gt e m p o r a ld a t a ；d e c i s i o nt r e ea l g o r i t h m ； r o u g h s e tt h e o r y ；i n c r e m e n t a ld a t am i n i n g i v 浙江工业大学 学位论文原创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行 研究工作所取得的研究成果。除文中已经加以标注引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的研究成果，也不含为获得浙江 工业大学或其它教育机构的学位证书而使用过的材料。对本文的研究作出 重要贡献的个人和集体，均已在文中以明确方式标明。本人承担本声明的 法律责任。 作者签名：二豸携拉 日期豳牌肛月3 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权浙江工业大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密戳 ( 请在以上相应方框内打“ ) 作者签名：易铋放 刷程轹盖确 蚣 ，栩 日期：沙年，召月；7 日 日期：乃膨年钐月乡j 日 浙江工业大学硕士学位论文基于粗糙集与决策树理论的时态增量算法 1 绪论 1 1 课题研究的背景及意义 信息技术的发展极大的提高了人们产生、搜集和存储数据的能力。从企业、 科研机构到政府部门，从金融行业、零售行业到机械制造行业，从通讯、医疗到 保险，社会各个部门、经济系统和专业领域每时每刻都在生产和累积大量数据。 人们所保存的数据中，有许多是时间序列数据和时态数据。时间序列数据是数据 序列的一个现实反应，也就是指观察、测量或记录下来的一串按时间先后顺序排 列的而又相互关联的数据序列。时态数据是对时间序列的升华，是在观察到的时 间序列数据上进一步加工变形的含时间属性的数据。 目前，越来越多的系统应用要求可以管理那些被处理事件的历史性信息和系 统中元事件的时态信息，如：金融、医疗、保险、气象等与历史密切关联的应用 系统不仅需要处理当前的数据，同时也需要处理和查询过去曾经发生的数据( 即 历史数据) 。按照研究的现象或问题的不同，可以得到各种时态数据。例如股票分 析员观察某个股票价格指数的波动! 气象学家研究某地区的气温与降雨量的变化， 水文专家研究某流域水位与降雨量的变化关系等，都会观测到按某种度量单位测 量的一系列数据，其自然顺序就是按出现的时间先后排列而得到的时态序列。自 然界以及社会生活中的各种事物都是在运动、变化和发展着的。事物之间也是相 互影响、相互作用的，一个事物的运动、变化和发要受到其它事物的影响和制约， 同时，它的发展变化也影响和制约着其它事物。通过对记录各个事物运动、变化、 发展的时态数据的分析研究，可以揭示事物发展变化的内部规律，以及不同事物 之间的相互作用关系，这对于人们正确认识事物并以此为据做出科学的决策具有 重要的现实意义。随着时态数据越来越普及，可以预见，时态数据挖掘( t e m p o r a l d a t am i n i n g ) 将会是今后数据挖掘发展的一个非常自然而又十分重要的方向。 人们采用数据挖掘技术对这些时态数据进行分析目的就是为了能获得隐含的 规则来提供决策。分类在数据挖掘中是一项非常重要的任务，有很多用途，比如说 预测，即从历史的样本数据推算出未来数据的趋向。然而，时态数据固有的带有时 间维度的特点，使得传统的数据挖掘分类算法不能直接处理，将时态数据进行转换， 降维处理，转化为非时态序列数据是分类挖掘算法进行分析的前提和基础。 分类挖掘算法的决策树算法中一种广为人知的经典算法就是i d 3 算法陋1 ，是 1 9 8 6 年由q u i n l a n 提出的一种基于信息墒的决策树算法，具有对知识表示有层次、 自然推理易理解的特点，有着广泛的应用，鉴于其存在固有的缺点和很少将其应 用到时态数据挖掘中。 浙江工业大学硕上学位论文基于粗糙集与决策树理论的时态增量算法 粗糙集理论b 钔是一种处理模糊性和不确定性的新型数学工具，能有效地处理 不精确、不一致、不完整的信息，并从中发现隐含的知识，揭示潜在的规律。粗糙 集是分类数据挖掘的方法之一。粗糙集由z p a w l a k 于1 9 8 2 年提出 3 ，是继概率 论、模糊集理论、证据理论之后的又一个处理不确定性的数学工具。该理论不需要 任何附加的信息或先验知识，就能有效地分析和处理不精确、不完整和不一致的数 据，并从中发现隐含的知识，揭示潜在的规律。粗糙集理论己经在很多领域如数据 挖掘、机器学习、模式识别、决策分析等取得了成功的应用，在时态数据挖掘领域 也有所应用。 本文先利用粗糙集合理论( r o u g h s e tt h o r y ) 在处理数据模糊和不确定性方面的 优势，结合决策树对知识表示有层次、自然推理易理解的特点，对时态数据进行 分类挖掘，提取决策规则，发现不同时态序列之间的相互作用关系。 1 2 时态挖掘与时态数据分类挖掘研究现状 1 2 1 时态挖掘研究现状 目前对时态数据的研究工作主要集中在时态数据序列的数据压缩、趋势分析、 相似性搜索、时态关联挖掘、周期模式挖掘、预测挖掘、序列模式发现这几个方 面。 时态数据的挖掘有几个重要的方向，包括时态关联挖掘、序列模式挖掘、周期 模式挖掘和预测挖掘。 ( 1 ) 时态数据序列数据压缩 将时间序列数据转化为趋势标志数据，数据量将大大的减少。其方法具体描 述如下旧旧：首先计算一个时间序列的两组不同时间长度的移动平均 ( m o v i n g a v e r a g e ) ，一组长期的，一组短期的；其次根据具体的需要定义若干趋势 标志值；最后通过比较这两个移动平均序列和原序列得出需要的趋势序列，数据 量得到了压缩，而且该趋势序列继承了原时间序列的移动特征。 ( 2 ) 时态数据序列趋势分析 采用移动平均对时态数据序列进行趋势分析是一个常用的方法，移动平均可 以降低数据集中的变化总量。因此用移动平均代替原时态数据序列可以减少不希 望出现的波动。移动平均会丢失原序列中的头或尾数据，由此有时会生成在原数 据中不会出现的循环或其他变化趋势：并且它可能受到一些极端数据的影响，可通 过适当权重的加权移动平均方法来降低其负面影响。另外采用适当阶数加权移动 平均可以消除数据中的循环、季节性和非规则的模式，只保留趋势变化盯1 。其他 2 浙江工业大学硕士学位论文基于粗糙集与决策树理论的时态增量算法 计算趋势的方法包括：徒手法口1 ，它是基于用户的判断画一根近似曲线或直线去拟 合一组数据，这种方法的代价太大，这一方法的代价很大，且只对大规模数据挖 掘才可靠，有效性和质量就完全依赖个人的判断。另一种方法是最 b - - 乘法陋3 ：将 以最佳的拟合曲线c 作为最 b - - 乘曲线，即曲线具有最小的p ，d i ，其中偏差是 指点 x i ，y 。) 的值y 。为对应曲线c 的值之间的差值。 ( 3 ) 时态数据序列相似性搜索 相似搜索是发现那些与查询序列轻微不同的数据序列阳1 。给定一个时态数据 序列，相似搜索问题就是发现所有与要查询的序列相似的时态数据序列。在金融 市场的分析( 股票数据分析) 、医疗诊断分析( 心电图分析) 、科学与工程数据库分 析( 能量消耗分析) 等方面，时间序列的相似性搜索有很大的应用价值。 对时间序列的相似性搜索分为：在一序列中寻找与样本序列( 根据领域知 识预先定义好) 相似的子序列：在同一序列中寻找相互间相似的子序列：在 若干序列间寻找相似序列。在具有时态约束的数据库中进行相似搜索，通常使用 欧氏空间距离作为相似性计算的依据。两种常用的数据独立转换有：离散傅立叶 转换( d f t ) n 们和离散小波转换( d w t ) n 。 一 ( 4 ) 时态关联挖掘 时态关联定义的是事件间的继发关系。当某一事件或多个事件紧接着另事件 发生时，它们之间不一定是因果关系，但可以认为它们之间具有一定的关联性， 例如股票的涨跌模式。关联分析的基本思想是计算某种度量，这种度量包括信息 增益、g 硒索弓l - , - 趸嗍定性和相关系数等。 对于关联的研究已有很多，如单维的关联、多维的关联、单层次的关联、多层 次的关联、量化的关联、基于距离的关联等等。当前的时态关联研究大多将已有 的关联分析运用到时态数据中，主要考虑该关联成立的时间范围，提出了一些时 间区间合并、延展技术，提出了一些时态关联挖掘的算法，大都是基于a p f i o f i 算法n 2 1 的变形。 ( 5 ) 周期模式型挖掘 周期性分析是指对周期模式的挖掘，即在时态数据中找出重复出现的模式。 周期模式挖掘可视为一组分片序列为持续时间的序列模式挖掘盯3 。周期模式挖掘 的问题可以分为三类：全周期模式、部分周期模式、挖掘循环或周期关联规则。 周期挖掘可以应用于许多重要的领域，如季节、潮汐、行星轨迹、每日能量消耗、 每天交通模式等。 ( 6 ) 时态序列模式发现 序列模式n 羽挖掘是指挖掘相对时间或其他模式出现频率高的模式。由于许多 商业交易、天气数据和生产过程都是时间序列数据，在针对市场吸引客户、气象预 浙江工业大学硕士学位论文基于粗糙集与决策树理论的时态增量算法 报等的数据分析中，序列模式挖掘是很有用途的。例如，一个月前烫发的人很有 可能在一个星期内染发。在文 1 3 中王振宇等提出了在关系型数据库中基于时间 窗口的序列模式挖掘方法，存在一些参数，其取值如何将严重影响挖掘结果。第 一个参数是时间序列的持续时间乃第二个参数是时间重叠窗口( e v e n tf o l d i n g w i n d o w ) w ；第三个参数是被发现的模式中时间之间的间隔i n t 。 综上可知，现在的大部分研究主要集中在对单一时态序列的研究，而对于时 态序列和序列间的关系的研究比较少见。 本文基于时态数据序列转换的思想，提出一种时间粒度上的时序转换的方法， 再用传统的数据挖掘算法挖掘时态数据序列间的关系。 1 2 2 时态数据分类挖掘研究现状 时态数据分类挖掘研究并不多，目前取得了一些成果。比较集中的有流分类 方面的研究，d o m i n g g o s 和h u l t e n 1 4 的v f d t 研究了如何在数据流上构造决策树 的问题，他们的算法能够以一定的概率保证所构造决策树的精度，g a m a 等 1 5 设 计实现了v f d t c ，对v f d t 从两个方向进行了扩展；在处理联系属性的能力和在叶 节点上使用分类能力更强的贝叶斯分类技术。国内学者朱秋香等在文 1 6 中厂+ 对 流分类算法进行综述，介绍了流分类问题涉及到的一些概念性问题和目前流分类 的最新成果。 还有用粗糙集理论来分析时态数据，文 1 7 使用粗糙集利用动态约简对市场。 数据进行了分析，取得了成功。文 1 8 提出了实时时态逻辑的框架，使用事件变 量来表示时态序列。文 1 9 使用动态编程方法来检测时间序列的模式。文 2 0 2 1 对加拿大的股票数据进行了分析，提出了将时间序列到传统信息系统的转换的思 想。文 2 2 提出了时序信息系统和实施时序信息系统的概念，并将文 2 0 2 1 中 的时间序列转换为信息系统思想进行了形式化。文 2 3 将文 2 2 提出的思想进行 了形式化表示。文 2 2 提出了时序信息知识表达系统，为时态序列之间的关系研 究奠定了很好的基础。因其提出了时态数据序列转换的思想，将时态数据的时间 特性消除，转换为很多传统数据挖掘算法可以处理的信息知识表达系统。 1 3 本文研究的内容 本文的研究内容是结合粗糙集和决策树理论对带有时间维的数据进行增量 式挖掘，提取有用的规则供人们决策。它的处理过程是先对时间序列数据进行转 4 浙江工业大学硕士学位论文基于粗糙集与决策树理论的时态增量算法 换成为一系列静态模式( 每种模式代表一种行为趋势) ，然后将相同模式的时间序 列进行定性化和离散化处理，从而去掉其时间依赖性，将其变为非时间序列数据， 形式为非时序信息表或决策表，然后，结合决策树对知识表示有层次、自然推理 易理解的特点和粗糙集理论适合处理模糊数据的优点建立决策树，用粗集理论去 优化决策树算法，导出决策规则。最后，有新的时间序列数据增加时，根据新增 数据与已有决策树规则集的关系，在原有的规则集的基础上进行增量式更新。 给出下面的示意图便于理解文章研究内容( 如：图1 1 ) ： 增量规则提取算法 厂、 改进决策树算法 粗糙集属性约简算法 ：一一。，一，一一、一一一， 时态数据 i 厂 改进时序转换方法 a n d 时序数据编码 滑动窗口技术 l d 平滑特 征序列 l 一 子序列模式数据 信息表 图1 1 文章研究内容结构图 5 浙江工业大学硕士学位论文基于粗糙集与决策树理论的时态增量算法 1 4 全文安排 第二章给出了与时态数据有关的数学概念以及相关性质，介绍了时态数据转 化方法并给出了其改进的算法。 第三章介绍决策树分类算法和粗糙集基础理论， 第四章分析了决策树分类算法固有的缺点以及应用与时态数据分类挖掘中的 缺点，把握决策树分类算法和粗糙集分类算法互通的地方，运用用粗集理论的一 些概念和参数改进决策树算法，提出了基于粗糙集与决策树理论的时态增量算法， 使得其在时态数据分类挖掘中能更好的应用。 第五章给出算法的应用实例，对股票的数据进行分析。 第六章对本文所做工作的总结，和对尚未解决的问题和将来可能的研究方向 提出了展望。 最后是参考文献、攻读硕士期间公开发表的论文及致谢。 6 浙江工业大学硕士学位论文基于粗糙集t j 决策树理论的时态增量算法 2 时态数据与时态数据转换 本章先介绍时态数据的一些概念和性质，再介绍时态知识表达系统( t i s ) 以 及如何将t i s 的转换为工s ，分析转换方法的不足，提出改进的时序转换方法，给 出算法的核心代码，举例说明改进时序转换方法的应用。 2 1 时态数据 2 1 1 时态型、时间粒度概念嘲 客观世界中的数据是不断扩充和持续变化的，人们对规律的认识和评价也在 不断发展。带有时间维度的数据形成时态数据，如股市交易、超市销售、w e b 点 击流等。在时态数据挖掘中，其中一个重要的问题就是时间的描述和划分，常用 的时间粒度是秒、分、时、天、月和年等，在一些实际应用中，还需要研究变长 度时间的数据，如在股票分析中对几天或几周同时考虑，如文 2 5 - 2 6 中提出的 时态型描述多时间粒度，因为时间长度对挖掘出的决策规则的有效性、周期长度 以及序列模式等时态数据挖掘有重要的意义，因此有必要给出严格的数学表示。 现实世界的时间( 刻) 是无限的，可以看成是两段无限的实数轴，轴上的每 一点代表所处的某一时刻，从某一时刻到某一时刻看成是一段时间。我们把现实 一二世界的所处的时刻称为绝对时刻，所有的绝对时刻构成一个实数集合一r1 ( 时间数 轴) ，每一个绝对时刻对应一个实数，那么绝对时间是从一个绝对时刻开始一直连 续到一个绝对时刻结束，绝对时间是一个实数区间。我们选实数轴0 对应公元0 年1 月1 日0 点，以后每一点用秒、分、小时、日、月和年作为计量单位记录对 应实数的每一时刻，如一个绝对时刻为2 0 0 4 年7 月3 1 日2 点3 分5 0 秒，一个 绝对时间为2 0 0 4 年1 月1 日到2 0 0 4 年7 月1 日等。下面我们给出时态型( t e m p o r a l t y p e ) 概念的严格定义。 定义2 1 1 嘲设是绝对时刻到绝对时间的一个映射：r 。2 兄，设对于任 意绝对时刻t r ，我们有( 1 ) ( 非空性) t 2 ( t ) 。( 2 ) ( 单调性) 若t ， f ：， ( t 1 ) n 2 ( t 2 ) = 囝，对任意的t ( t 1 ) 和芒g ( t 2 ) ，有芒 芒7 ，记 ( f 1 ) ( f 2 ) 。( 3 ) ( 同一性) 任意f ( f ) ，有( f ) = ( f ) ，( 4 ) ( 有界性) 对任意r ( f ) ， i ，1 佃，则称为一个时态型，( f ) 称为时态型的时态因子( t e m p o r a lf a c t o r ) 。 7 浙江工业大学硕上学位论文基于粗糙集与决策树理论的时态增量算法 类似的时态型定义可参见文 2 6 。时态型是对时间数轴r 的一个划分，每个 时态因子是一个区间( 一般为半开半闭或开或闭) ，可以用秒、分、小时、日、周、 月和年来划分时间数轴r ，因此他们又都是时态型。一个时态因子是一个绝对时 间。若( t x v t 月) 为单点集，则称为原子时态型，若( f ) ( v f 尺) 为非单点集，则 称为非原子时态型，在日常生活中常用的时态型均是非原子时态型。 定义2 1 2 嘲设a ，y 是2 个时态型，如果l e n g t h ( ，( 幻) l e n g t h ( ( 幻) ( v t r ) ，称时态型y 小于时态型。若时态型v 小于时态型，如果对l ，的任何 时态因子y ( f ) ，存在唯- - p ( t ) 使得v ( t ) c ( f ) ，称v 是的一个基时态型。 显然秒是分、小时、日、周、月、季度和年的基时态型，小时是日、周、月、 季度和年的基时态型，日是周、月、季度和年的基时态型，月是季度和年的基时 态型，季度是年的基时态型，但是周不是月、季度和年的基时态型。 定义2 1 3 叼1 ( 1 ) 如果一个非原子时态型具有等长的绝对时间长度，称 为一个时间粒度。每个时态因子( f ) 称为时间因子，每个时间因子具有相同的时 间长度，记为l e n g t h ( ) 。( 2 ) 设y 是一个时间粒度，是一个时态型，是的 一个基时态型，称y 是的一个基时间粒度。 时态粒度是一个时间区间的划分，每个一个时间区间都可以被等长度的时间 因子度量。在我们日常生活中，我们常用的时间粒度是秒、分、小时、日和周， 而月、季度和年仅是时态型，因它们不具有等长的绝对时间长度。显然秒是分、 小时、日、周、月、季度和年的基时间粒度，小时是日、周、月、季度和年的基 时间粒度，日是周、月、季度和年的基时间粒度，但周不是月、季度和年的基时 间粒度。 定义2 1 4 啊1 ( 1 ) 如果一个非原子时态型具有有限个不等长的绝对时间长 度，称为一个粗时间粒度( 2 ) 设y 是一个粗时间粒度，是一个时态型，矿 是的一个基本时态型，称y 是的一个基粗时间粒度 月、季度、年是粗时间粒度我们经常用基时间粒度来度量其它时间粒度或粗 时间粒度，比如在股票统计中常用秒和日作为基时间粒度来描述股票变换的趋势， 如1 小时有3 6 0 0 秒，一周有7 天，一月有2 8 天、2 9 天、3 0 天和3 1 天4 个绝对 时间长度，一年有3 6 5 天或3 6 6 天，有时我们也用基粗时间粒度来度量其它时间 粒度或粗时间粒度，如1 个季节为4 个月，1 年为1 2 个月。 8 浙江工业大学硕上学位论文基于粗糙集与决策树理论的时态增量算法 2 2 时态知识表达系统和时序转换方法 2 2 1 时态知识表达系统和时序方法 时态数据，重点是其时间序列特征，即对象之间保持着严格的时间顺序。针 对时态数据的序列性，文 2 2 提出了时序信息知识表达系统( t i s ) s = ( 以厅u 4t ) ， ) 。 时序信息系统t i s 定义为： s = ( 彰月u zt ) ， ) 式中卜一对象集( 案例，状态，疾病，观测，) ； r 属性( 特征，变量，特点，条件，) a l 决策属性，靡a ； 卜序列属性，t g a ； 序列属性t 上的一个次序关系，且- 4 = ( 乃力：与y e a n d x 纠 实时时序信息系统r t t i s 定义为： a 。= ( y , 厅u z 巧万 ， ) 式中卜一对象集( 案例，状态，疾病，观测，) ； l 卜属性( 特征，变量，特点，条件，) 卜决策属性，以刀； 卜序列属性，芒萑彳； 序列属性t 上的一个次序关系，且 = ( 五力 # 7 酬a n d j 纠 万时间属性，6 芒a ，万( 商表示自对象而u 发生以来到彪u 发生的时 间，这里芒( 勒 芒( 动，并且不存在y e u ，满足( p 西) ( k 动 时序信息系统很好的体现了时序特性，通过决策表清楚地看到时序与各非时 序属性之间的关系。很多领域的数据都是连续的时态序列数据，如股市交易、超 市销售、w e b 点击流等。例如，属性集 t ，r 1 ，r 2 r n ，d ) 描述有限实体集s 纽口客户、 股票集) 的各种属性，t 是时序属性，可以是上节定义的时间粒度( 日，月，周等) ， r l ，r 2 r n ，d ) 为非时序属性，描述某时间粒度下实体的呈现的状态属性。对于 某支股票日交易数据，经适当的处理变换后，用时态序列信息系统 s = t ，r 1 ，r 2 r n ，d ) 表示，时序属性t ，选取日为时间粒度，有决策属性d = 涨跌 情况) ，条件属性集r = 开盘价，收盘价，交易量) 。要想研究条件属性的时态数据 序列对于决策属性时态数据序列之间的关系，先得将时序信息系统转换为传统的 信息系统。 我们先来看个例子( 描述了文 2 2 的转换方法) 例2 1 假设一个锅炉加热系统的数据表如表2 1 所示。我们可以看到，时间 9 浙江工业大学硕上学位论文基于粗糙集与决策树理论的时态增量算法 属性的属性值是一组序列，这个序列可以作为表中每个对象的标示而唯一确定。 该序列是不带实时约束的时间序列，可以看成是按时间排列的事件串，事件之间 的时间间隔( 采样速率) 是常数1 5 分钟( 时间粒度) 。所以表2 1 可以用时序信 息知识表达系统s = ( 所月u 4t ， ) 来表示，见表2 2 表2 1 原始数据表 我们看到表2 2 现在是一个时间序列决策表了，其中，c = 温度，气压) ，d = 阀 门状态) ，v 温度= v 气压= 低，偏低，正常，偏高，高) ，v d = 闭，开 接下来，所要 做的就是把时间序列数据集转换为传统数据挖掘算法能处理的数据集。也就是采 取一定的挖掘策略啪1 将t i s 转换为i s ，转换后的结果我们可以看表2 3 ： l o 浙江工业大学硕士学位论文 基于粗糙集与决策树理论的时态增量算法 表2 3 时序转化后的传统决策表 该数据集的对象之间已经没有严格的时间顺序了，它已经是一个普通的i s ， 将时序信息知识表达系统s 。= ( u ，a u d ，t ， ) 进行转换，去掉其时间属性， 变为知识表达系统s = ( u ，r ，v ，f ) 。 一 此方法为了能够从决策表中挖掘出与时间相关的有用信息，必须将t i s 转换 成i s 。转换后的i s 虽然从表面上看去掉了时间属性，实质上是通过增加决策表 属性个数将时间属性融入到决策表当中i 文一 2 3 和 2 8 多采用此转换思想：客户 确定回溯时间片数；建立木i c l 个新属性，分别对应l ，2 ，个时间片的 历史数据；将当前时间片的数据与历史数据相结合，组成新对象数据；决策属性 选用当前时间片的属性。 一一一一 这样将t i s 经过转换后称为普通的i s ，保留了历史数据对当前决策的影响因 素，还可以用传统的分类算法来处理和挖掘有用的决策规则。 2 3 改进时序转换方法 上节中提到的时序转换的方法，随着的增加，属性个数以2 的指数次增加， 当选用的过大，或者决策表条件属性个数本身比较多的情况下，使得转换后的 信息表变得很复杂。时态序列数据最大的特性是其时间特性，按照时间的先后顺 序，可以划分对应的子序列，现实中人们主要需要关心的是序列的空间形状和它 的变化趋势，而且往往关注序列变换趋势比较关键的部分，例如，如果一个股票 数据分析员想要以周( 每周5 个交易日) 为单位分析股票价格，并且只对价格涨 跌幅度在6 以上的数据感兴趣。 浙江工业大学硕士学位论文基于粗糙集与决策树理论的时态增量算法 针对上面的讨论，我们提出一种改进的时序转换的方法，设给定时态序列数 据s = ( x ，y 。) ( x 。，y 。) ) ，x i 为某一时间粒度下的时间值，y ，是x ，对应于的时 间序列的数值。 本文采用( w ，占) 方式进行时序转换，设：定滑动窗口长度( 粗时间粒度) w 1 ，即为回溯时间片数，约束占，可以根据用户关注的情况来设置对应的 约束( 也可以不设置) ，比如，分析股票价格，只对较之昨天的价格，涨跌幅度在 6 以上的数据感兴趣可以定义，如下约束：s ：i ( x ；一x ) x l 6 ，即在进行 序转换的同时，去除不满足约束条件的数据。 本文引进的约束是文献 4 1 中描述的数据挖掘中的简洁约束，所谓简洁约束 是能用数据库理论中的选择运算符号来解决的。 构建数据集s = ( p 。，q 。) ( p k ，q k ) ，其中p 。= x 矽，q l 为在给定时间窗口长 度为w ，满足约束条件的子序列进行体现变化趋势的编码，作为当前时间片p ，的历 史数据。转换后的数据集已经去除了时间属性，p i p 。可以用序号l k 代替。此 转换方法的难点在于时间片的历史数据获取和时间窗口w 内的编码处理，现在详细 介绍下处理的过程。 一一 1 把长度为w 滑动窗口放置在每一个序列的起始位置，此时滑动窗口对应 序列上的长度为w 的一段子序列，对这段子序列进行变换编码，这样每 一个长度为w 的子序列对应一f 维特征空间上的一个点。 2 滑动窗口后移，再以序列的第二个点为起始单位，形成另一个长度为w 的子序列，如果满足约束条件则对这段序列进行变换编码。否则，将时 间窗口下移，依次类推，最多一共可以得到l e n ( s ) 一w + 1 个编码。 其中第1 步中，子序列进行变换编码是最为关键的，直观观察时间序列曲线 图，会发现序列变化中有相对重要影响的点通常是局部极大值和极小值点，这些 点能够反映时间序列整体的变化趋势和主要特征模式，则称这些点为关键点。关键 点是时间序列趋势上升或下降的变化的分界点，比如，当观察一支股票的走势图 时，如果只有几秒钟的时间，人们经常首先记在脑海里的是一些转折点的位置， 将这些点连在一起，即可以大致恢复原始图形，因为这些转折点位置是最重要的， 我们用某种带有特殊含义的数字来表示变化趋势，即将时序数据离散化，这样就 就达到了降维的效果，也使得时态数据的状态能在数据库中存储，转换后的数据 可以为传统的数据挖掘算法处理，对于时态数据分类挖掘来说，我们可以把历史 时态数据状态作为一条件属性，其不同的状态编码作为属性值，挖掘其与某时间 粒度下当前时间点的决策属性的规则，挖掘出的规则( 需将编码还原) 可以达到 1 2 浙江工业大学硕士学位论文基于粗糙集与决策树理论的时态增量算法 分类预测的目的，即根据历史时态数据的状态预测当前某时间粒度下的时态数据 状态。 下面我们详细介绍如何用编码的方式表示时序序列的变换趋势。 选取长度为w 的一段子序歹u s i = ( x 。，y ，) ( x 。，y 。) ，有w 个时间点数据，( w 一1 ) 条线段，其中，x ，是时间标记，x ， x2 o ，设置为“上升趋势，编码为1 如果y i y i - l = o ，设置为“基本 不变”，编码为5 ；如果y i y i 1 4 时，随着编码的复杂程度增加，不能很好的表示时态序列的特征，可以 通过选用同一时间粒度下，不同时间间隔的的编码，比如：w = 6 时，先选用6 天为一 粒度进行编码先以时间间隔为1 进行编码提取属性a 1 ，再以时间间隔为2 或者3 进行 编码提取属性a 2 ，a 1 ，a 2 作为属性组合体描述同一粒度下时态数据状态。在分类 挖掘时，做组合属性处理，举个例子：选取w = 5 进行编码，为更好的描述窗口内子 序列数据的状态，我们选用时间间隔为1 和2 进行编码，如图2 2 为窗口内某一子序 列的编码 图2 2w = 5 时编码 下面我们讨论需要平滑处理的情况，如果出现下面( 图2 3 ) 情况的编码： 图2 3 ：需平滑处理的编码情况 这两子序列的编码一样，但是对于图2 3 ( 1 ) 号序列的下降的趋势很不明显， 几乎可以忽略不计，考虑到这样的情况，我们有必要对编码前的序列做平滑处理。 参考文献 2 5 中的方法进行平滑特征序列，文 3 0 中方法描述如下：给定特征序 列f ；= ( x j l ，y n ) ，( x 加，y 加) ，最小时间间隔ot i m e 和最小数值变化率 0v a l u e ，若它们满足条件： x 驴一x 妒 臼砌” 可了古黠 秒。妇 则从特征序列中去除这两个数值点，给出的例子( 如图2 4 ) 通过平滑处理把图2 4 中的( a ) 变成( b ) ： 1 4 浙江工业大学硕士学位论文 基于粗糙集与决策树理论的时态增量算法 图2 4 ：平滑子序列 下面我们对图2 3 e e 的情况进行处理：假设图2 3 6 e 的( 1 ) 号序列满足 而一x 2 揣 l ( w 一1 对t 取余数必须为0 ) ，调用其重载函数c o d i n g ( s ，w ，v a l u e ，t ) 。 s t e p 3 ：滑动窗口后移，再以序列的第下一个点为起始单位，形成另1 个长度 为w 的子序列，对这段序列用步骤1 的方法进行编码 s t e p 4 ：依次类推，需要对l e n