（计算机系统结构专业论文）基于粗糙集的时序数据分析方法研究.pdf

摘要 粗糙集理论是一种处理不精确、不确定和不完备信息的数学工 具，它能有效地从数据本身提供的信息中发现有效的、潜在的知识。 将粗糙集应用于数据挖掘领域，能提高对数据进行分析和学习的能 力。本文基于粗糙集理论，针对时间序列数据处理技术涉及的关键问 题进行了较为深入的研究和探索。 用粗糙集理论来进行时间序列数据分析，关键是将时态信息系统 转化为适用粗糙集方法处理的传统信息系统。本文探讨了基于粗糙集 方法的时间序列挖掘问题，主要包括时态信息系统转换成信息系统以 及实时时态信息系统转换成时态信息系统的各种方法。在时态信息系 统转换成信息系统转换过程中回溯时间片长度的确定是一个重要的 问题，本文在现有的方法基础上提出了一种基于时间粒度的时态信息 系统转化方法，有效地减少了转换后信息系统属性个数。 属性约简是粗糙集理论研究的一个重要内容。在实际运用中，时 序数据库往往是动态变化的，本文针对时间序列数据动态变化的特 性，对动态变化的决策表属性约简进行了深入研究，在改进的区分矩 阵的基础上，提出了一种增量启发式属性约简算法，能有效的处理不 一致数据集的动态更新。 论文最后选取u c i 数据集进行实验仿真，对动态数据库增量式约 简算法进行实验分析，有效地验证了上述算法的有效性。 关键词粗糙集，时间序列，增量更新，约简 a bs t r a c t r o u g hs e ti s an e wv a l i dm a t h e m a t i c a lt h e o r yd e v e l o p e di nr e c e n t y e a r s ，w h i c hh a st h ea b i l i t yt od e a lw i t hi m p r e c i s e ，u n c e r t a i n ，a n dv a g u e i n f o r m a t i o n i tc a na b t a i nv a l i da n dp o t e n t i a l l yu s e f u lk n o w l e d g ei nd a t a a p p l y i n gr o u g hs e tt h e o r yi nd a t am i n i n gf i e l dc a nl a r g e l yi m p r o v et h e a n a l y z i n ga n dl e a r n i n ga b i l i t yf o ri n c o m p l e t ed a t ao fl a r g ed a t a b a s e ， w h i c hh a se x t e n s i v ea p p l i e dp r o s p e c ta n dv a l u e b a s e do nr o u g hs e t t h e o r yt h ep r o b l e m so ft i m es e r i e sp r o c e s s i n gh a v eb e e nm a i n l ys t u d i e di n t h i st h e s i s r e s e a r c hh a sb e e nd o n et oa n a l y z et i m es e r i e su s i n gr o u g hs e t m e t h o d i tm a i n l yc o n t a i n st h em e t h o df o rt r a n s l a t i n gt i st oi sa n d t r a n s l a t i n gr t t i st ot i s s o m em e t h o d so fm i n i n gt i m es e r i e sw i t h r o u g hs e ta r ed i s c u s s e d i np r o c e s so ft r a n s l a t i n gt i st oi s ，t r a c e dt i m e s e g m e n t sp r o b l e mh a sa l r e a d yb e e na ni m p o r t a n tp r o b l e mo fd a t am i n i n g f r o mat i m es e r i e sw i t hr o u g hs e t f u r t h e rm o r eam e t h o df o r t r a n s f o r m i n gt i st oi sb a s e d o nt i m eg r a n u l a r i t yi sp r o p o s e d a t t r i b u t er e d u c t i o ni so n eo ft h ek e yp r o b l e m sf o rt h ek n o w l e d g e a c q u i s i t i o n i np r a c t i c a l i t yt i m es e r i e sd a t a b a s ea r ed y n a m i c ，s os t u d yo n i n c r e m e n t a la l g o r i t h m sf o ra t t r i b u t er e d u c t i o ni s t h r o u g h l yi m p o r t a n t i n c r e m e n t a la l g o r i t h m sf o ra t t r i b u t er e d u c t i o nb a s e do nd i s c e m a b i l i t y m a t r i xa r ep r o p o s e d ，b yw h i c ha t t r i b u t er e d u c t i o no fn e wd e c i s i o nt a b l e c a nb eo b t a i n e dq u i c k l yw h e nr e c o r d sa r ea d d e do rd e l e t e dt op r i m a r y d e c i s i o nt a b l e f i n a l l y , t h r o u g hs i m u l a t i o n ，w ev a l i d a t et h ee f f e c ta n da c c u r a c yo ft h e a l g o r i t h mo fi n c r e m e n t a lr e d u c tf o rd y n a m i cd a t a b a s e k e yw o r d s r o u g hs e t ，t i m es e r i e s ，i n c r e m e n t a lu p d a t i n g ，r e d u c t n 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：日期：三竺年二月日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签名： 导师签名：杰立g 卫亟日期：兰堕年月三角 硕士学位论文第一章绪论 第一章绪论 随着信息技术的飞速发展和互联网技术的普及，使得人们所面对的数据量急 速增长，大量的业务处理数据和市场变化数据被大规模的存放在数据库或数据仓 库中，日积月累，变拥有了海量的数据信息。这些积累下来的历史数据是一笔宝 贵的财富，其背后隐藏着很多有用的信息，这些信息在制定决策中具有非常重要 的参考价值，从这些海量数据中挖掘出有用的信息成为当务之急，在这种情况下， 各种数据分析和数据挖掘技术与方法应运而生。粗糙集理论作为智能信息处理的 有效工具之一，具有处理不精确、不确定和不完备数据，并从中获取知识的能力， 自上世纪8 0 年代提出以来得到不断完善与发展，取得了良好的研究和应用成果， 但是在现实问题中，数据规模和复杂程度的俱增给粗糙集方法与技术提出了新的 挑战。 1 1 课题研究背景与意义 随着计算机和互联网技术的发展，数据已超出它原始的范畴，包含各种类别 和形式的信息，需要利用相关的数据分析方法从中提取规则，发现知识。大量的 时间序列数据被存储在计算机上，使得我们拥有海量的时间序列数据。从经济到 工程技术，从气象、环保到天文地理，几乎在各个领域都会遇到时问序列数据。 如科学研究记录：包括天文观测，气象图像等。病历记录：包括病人的每次看病 的病情记录以及心电图等扫描仪器的数据记录等。金融和商业交易记录：如股 票市场每天的交易价格及交易量，超级市场每种商品的销售情况等。时间序列几 乎无处不在。随着科学技术的不断发展，计算机以及存储设备的存储容量日益增 大，时间序列数据库也越来越大，因此对于时间序列的数据挖掘的研究显得愈发 必要。 面对这些时间序列数据，人们想找到有效的方法或技术来揭示这些时间序列 数据集中所隐藏的知识或信息，人们不断地研究和探索新技术、新方法，把历史 时序数据转化为对人类有用的知识和信息。这就使得时间序列数据挖掘的研究得 到了空前的发展，并己发展成为数据挖掘的一个重要的研究方向。由于自然界里 的事物之间是相互联系和相互影响的，事物的运动、变化和发展有其内在的必然 性，因而已经发生的历史时间序列与将来发生的时间序列之间必然有其内在的联 硕士学位论文 第一章绪论 系。因此，我们通过分析和研究反映事物过去的运动、变化和发展的历史时间序 列数据，在很大程度上是可以发现事物变化发展的内在规律的，这就能为决策者 制定决策提供重要的参考信息或知识。 近些年来，随着粗糙集理论的研究深入，它已被广泛地应用于数据库中的知 识发现、智能控制、机器学习、决策分析、专家系统以及模式识别等众多领域。 信息系统中时间序列数据的出现使得有必要针对这一特殊数据类型的挖掘给出 相应的策略，以便发现在某段时间内连续记录的某属性序列值的变化规律，以及 它的变化给其它属性值所带来的影响。利用粗糙集对时间序列数据进行分析研究 已经取得了一定的成果，人们开始运用粗糙集工具对时间序列进行属性约简，从 中获得人们感兴趣的规则集。本文主要对信息系统获取方法、增量式属性约简算 法的进行了研究，是对利用粗糙集对时间序列数据进行分析研究的一个补充。将 文中方法运用到时间序列数据的实际工程领域，可为这些工程领域的智能信息信 息处理提供一个有效的方法，便于人们从中获取规则、发现知识，提高和改进工 作效率。 1 2 国内外研究现状 1 2 1 数据挖掘技术概述 面对信息社会中数据和数据库的爆炸式增长，人类分析数据和从中提取有用 信息的能力远远不能满足实际需要，所以迫切需要一种能够智能的自动地把数据 转换成有用信息和知识的技术和工具，知识发现也就孕育而生。一般说来，知识 发现的通用过程包括以下几个步骤： 数据清理：消除噪声或不一致数据； 数据集成：多种数据源可以组合在一起； 数据选择：从数据库中检索与分析任务相关的数据； 数据变换：将数据变换或统一成适合挖掘的形式，如通过汇总或聚集操作； 数据挖掘：使用智能方法提取数据模式： 模式评估：根据某种兴趣度度量，识别表示知识的真正有趣的模式： 知识表示：使用可视化和知识表示技术向用户提供挖掘出来的知识。 其中数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、 随机数据中发现隐含的知识和规律。它既是一种知识获取技术，又是一个数据处 理过程。它为大型数据库的自动分析与处理、从中提取有用的模式和关系提供了 有效的方法和手段，它从大量数据中提取有价值的知识和模式的过程乜1 ，它是 在信息技术飞速发展和信息量日渐增大的情况下产生的，是数据库中的知识发现 2 硕士学位论文第一章绪论 过程的关键步骤。 目前，对数据挖掘的研究主要集中在以下三个方面： ( 1 ) 数据挖掘的理论研究。其目标是建立完整的数据挖掘理论体系，建立通 用、有效的处理模型，用科学的方法论指导发现知识的过程，使之成为一种主流 技术。 ( 2 ) 数据挖掘技术和算法的研究。数据挖掘是从人工智能发展而来，因此人 工智能中的许多技术成果都可以移植到数据挖掘中来。传统的统计、聚类、决策 树、集合论，近年来十分活跃的关联规则、粗糙集理论、人工神经网络、遗传算 法和进化计算等在数据挖掘中都有应用。 ( 3 ) 应用研究。应用研究的一种划分是按照处理的数据类型分，产生了时间 序列数据挖掘、空间数据挖掘、文本数据挖掘等。应用研究的另一种划分是按照 应用领域，如股票价格分析与预测，金融风险分析，信用卡欺诈分析，气象预报， 生物工程等。随着的普及与发展，对数据的挖掘，如站点访问模式分析，成为当 今一个十分活跃的应用领域研究方向。 由于数据挖掘所使用的数据直接来自数据库，数据的组织形式、规模都具有 依赖数据库的特点，特别是当数据挖掘处理的数据量非常巨大时，数据的完整性、 一致性都难以保证。这时数据挖掘算法的效率、有效性和可扩充性都显得至关重 要。充分利用现代数据库技术优势也是提高数据挖掘算法效率的有效途径。 数据挖掘技术与传统数据库查询技术存在显著不同口1 。首先，传统的数据库 查询一般都具有严格的查询表达式，可以用s q l 语句描述。而数据挖掘则常常 表现出即时、随机的特点，查询要求不确定，无法用s q l 语言表达。其次，传 统的数据库查询一般生成严格的结果集，但数据挖掘过程往往基于统计规律，产 生的规则并不要求对所有的数据项总是成立的，而是达到事先约定的阈值就可以 了。此外，通常情况下，数据库查询只对数据库的原始字段进行，而数据挖掘可 能在数据库的不同层次上发掘知识规则。 1 2 2 粗糙集研究现状 粗糙集理论是波兰数学家z p a w l a k 于1 9 8 2 年提出的一种处理不精确、不确 定和不完备数据的数学工具h 引，粗糙集理论是一种新型的处理不完整性和不确 定性问题的数学工具，能根据人们对所获取数据的已有认识，有效地分析和处理 各种不完备信息，从中发现隐含的知识并揭示出其中的潜在规律。 粗糙集理论自其诞生以来引起了许多数学家、逻辑学家和计算机研究人员的 关注，他们在粗糙集的理论和应用方面做了大量的研究工作。1 9 9 1 年z p a w l a k 出版的专著睢1 系统全面地阐述粗糙集理论，此后召开的与粗糙集有关的国际会议 硕士学位论文 第一章绪论 进一步推动了粗糙集的发展，越来越多的科技人员开始了解并准备从事该领域的 研究。1 9 9 2 年在波兰k i e k r z 召开了第一届国际粗糙集理论研讨会，同年，粗糙 集理论应用专集的出版对这一段时期粗糙集理论和实践的成果做了较好的总结， 促进了粗糙集在各个领域的应用。1 9 9 6 年在闩本东京召开的第五届国际粗糙集 理论研讨会，推动了亚洲地区对粗糙集理论与应用的研究。近年来，粗糙集理论 及其应用得到了广泛的认可，已经成为学术界的一个研究热点，许多国际学术会 议和期刊都将它列为重要内容之一，而国内对于粗糙集的研究也正处在一个迅猛 发展的时期。 粗糙集理论有效地克服了传统的数据分析和信息处理方法的不足，成为信息 科学和认知科学领域新的研究和应用热点，在不确定问题和智能计算、数据分析 方面表现出较强的处理能力，得到了学术界的广泛关注口1 。它通过不可分辨关系 对论域进行划分，用上、下近似集合对给定概念进行逼近，从而得出粗糙的概念 表示形式，将不确定或不精确的知识用已知的知识来近似刻画。粗糙集理论不仅 为信息科学和认知科学提供了新的科学逻辑和研究方法，而且为智能信息处理和 数据挖掘提供了有效的技术，作为一种新型的处理模糊和不确定性问题的工具， 它能有效地解决下列问题：发现属性之间的依赖关系、计算属性重要度、冗余属 性和数据的约简、求属性及属性值的核、获取决策规则等。粗糙集理论无需任何 关于数据的先验信息和附加信息，对问题的不确定性描述和处理比较客观，能分 析挖掘隐藏在数据中的事实，与概率论、模糊集、证据理论等其它处理不确定性 问题的理论有较好的互补性。 粗糙集的研究对象是由一个多值属性集合描述的对象集合，对象、属性和描 述符是表达决策问的三个基本要素。 这种表达形式也可以看成一个二维表格，表格的行与对象相对应，列对应于 对象的属性；各行包含了表示相应对象信息的描述符，还有关于各个对象的类别 成员的信息。 粗糙集方法可以在缺少数据的先验知识( 统计中要求的先验概率和模糊集中 要求的隶属度) 的情况下，仅仅以观测数据的分类能力为基础，解决模糊或不确 定性数据的分析和处理，且算法简单易于操作。其特点可归纳为旧1 ： ( 1 ) 不需要先验知识 模糊集和概率统计方法是处理不确定信息的常用方法，但这些方法需要一些 数据的附加信息或先验信息，如模糊隶属函数和概率分布等，这些信息并不容易 得到。粗糙集分析方法仅利用数据本身提供的信息，无须任何先验知识。 ( 2 ) 一个强大的数据分析工具 它能表达和处理不完备信息；能在保留关键信息的前提下对数据进行化简并 4 硕十学位论文第一章绪论 求得知识的最小表达式；能识别并评估数据之问的依赖关系，揭示出概念简单的 模式；能从经验数据中获取易于证实的规则知识，特别适于智能控制。 ( 3 ) 与模糊集分别刻画了不完备信息的两个方面 r s 以不可分辨关系为基础，侧重分类，模糊集基于元素对集合隶属程度的 不同，强调集合本身的含混性( v a g u e n e s s ) 。从r s 的观点看，粗糙集合不能清晰 定义的原因是缺乏足够的论域知识，但可以用一对清晰集合逼近。 目前，粗糙集已成为人工智能和智能信息处理领域中一个较新的学术研究和 技术应用热点，在专家系统呻1 、知识发现n 、数据挖掘“、决策分析n “、医疗诊 断。引、粗糙控制n 引、模式识别与人工智能“m 1 等许多领域中得到了广泛的应用。 基于粗糙集理论的原型系统主要有波兰华沙大学和挪威科技大学联和开发的基 于粗糙集的决策分析系统r o s e t t a 及其增强版r s e s “”，加拿大r e g i n a 大学研制 开发的基于变精度粗糙集模型，主要用于市场分析的知识发现系统k d d - r 【l ，美 国k a n s a s 大学开发的用于环境保护、气候研究和医疗诊断的实例学习系统 l e r s 【l 鲫等。这些实用系统实现了粗糙集模型的基本功能，在不同的领域取得了较 好的应用效果，在满足实际问题需要的同时也对粗糙集理论基础理论有了进一步 的发展。 现有的粗糙集理论相关研究与应用主要是针对其存在的问题提出更有效的 算法和改进，将其应用于决策分类和知识获取，并没有太多结合数据本身的特性 进行的研究，而数据分析和挖掘问题的基本出发点是待处理的数据，现实世界中 数据集的规模和复杂程度越来越大，给粗糙集理论在实际问题中的应用推广提出 了挑战。粗糙集理论及方法虽然在理论和应用上日渐成熟，但仍不能适应实际问 题中迅速增长的数据量和数据集内部错综复杂的关系，学术界正在针对这一问题 进行探索和研究，寻找合理有效的解决方法。 1 2 3 时间序列研究现状 当前对于时间序列数据挖掘主要集中在趋势分析，相似性搜索等。其中趋势 分析是对测得的时间序列数据进行一系列处理，如去掉噪声、毛刺，忽略不规则 的波动，而把注意力集中在序列的长期运动方向上；相似搜索主要目的是找出与 给定查询序列最接近的数据序列进行匹配。其中主要分为，子序列匹配与整体序 列匹配。 1 趋势分析 时间序列的变化纷繁复杂，但总有一定的规律可循。对时间序列研究最多的 是它的趋势变化情况。对时间序列的趋势分析，是对测得的时问序列数据进行一 系列处理，如去掉噪声、毛刺，忽略不规则的波动，而把注意力集中在序列的长 硕士学位论文 第一章绪论 期运动方向上。因此趋势分析的主要工作之一是对时序数据曲线的平滑，常见的 趋势分析( 曲线平滑) 方法有四种，分别有： ( 1 ) 徒手法3 ( f r e e h a n dm e t h o d ) ：这一方法代价很大，在很大程度上依 靠用户的经验和直觉，并且只对大规模的数据挖掘可靠，一般很少使用。 ( 2 ) 简单移动平均值法乜”( s i m p l em o v i n ga v e r a g e ，s m a ) ：移动平均值的作 用是平滑短期波动和发现隐藏趋势。它的缺点在于没有区别前后各天数据对求平 均值时的作用，只是简单计算各天数据的算术平均值。 ( 3 ) 加权平均值法乜2 3 ( w e i g h t e dm o v i n ga v e r a g e ，w m a ) ：加权平均通常对中 间数据或者说当前数据赋予较大的权重，以便抵消平滑效果。移动平均会丢失序 列数据中的头尾数据，由此有时会生成在原始数据中不会出现的循环或者其他变 化趋势，并且它可能受一些极端数据的影响。 ( 4 ) 最j , _ - - 乘法瞳“：最小二乘法的优势在于，一旦求得了拟合函数，就可以 利用一些函数的性质，如连续、求导等方法来对时序数据进行分析。而它的难点 在于，当时序数据曲线非常不规则时，拟合函数很难构造，或者即使构造出来， 也非常复杂或者是病态的，不便于使用。并且误差的平方和往往也很大，超出期 望的范围。 2 相似性搜索 所谓的相似搜索，找出与给定查询序列最接近的数据序列。其中主要分为， 子序列匹配与整体序列匹配。子序列匹配是找出与给定序列相似的所有数据序 列，而整体序列匹配是找出彼此间相似的序列。在金融市场数据分析，科学与工 程数据库分析以及医疗诊断分析中时间序列相似性搜索有非常广泛的应用。其基 本方法有： ( 1 ) 数据变换 从时间域到频率域，这是由于许多信号分析技术需要数据来自频率域。常见 的独立与数据的变换是离散傅立叶变换乜3 1 ( d f t ) 和离散小波变换乜钔( d w t ) 。 ( 2 ) 相似搜索的索引方法 在时间序列表示的基础上，提取其主要特征，将时间序列映射到高维空间中 的点，通过建立索引可以提高查询效率。a g r a w a l 等口最早提出了时间序列的f 一 索引，s a l z b e r g 等乜钉对时序数据库的索引方法进行了比较和评价。目前，时间序 列索引主要有两种方法，一是直接利用高维数据索引方法，如r 树等；二是针对 时间序列的具体特点和要求，对高维数据索引方法加以改进，或设计专门的索引 方法。由于索引方法是目前整个信息技术领域研究的热点问题，近年来国内外研 究者提出了一系列索引方法啪2 l 巩。直接利用高维数据索引可以充分利用现有 技术，但由于时间序列的维数比较高，如何避免“维灾问题”是需要解决的主要 6 硕士学位论文第一章绪论 问题。针对时间序列的索引实际上都建立在高维数据索引方法的基础上，也面临 同样的问题。 ( 3 ) 时间序列相似性度量 相似性度量是衡量时间序列相似性的标准。相似性度量的选择决定了查询算 法的性能，影响到查询的完备性、对时间序列各种变形的支持等。当然，相似性 度量标准的选择也受时间序列表示方法的制约。 目前，时间序列相似性度量主要有：欧氏距离口、动态时间弯曲距离口1 1 和编 辑距离b 羽等，其中欧氏距离是m i n k o w s k i 距离的一种特例。m i n k o w s k i 距离计算简 单，复杂性为0 ( n ) ，支持各种索引方法，但对时间序列的各种变形都不支持；动 态时间弯曲距离是目前相似性度量中的研究热点，其主要优点是支持时间序列的 时间轴弯曲，但其计算比较复杂，时间复杂性为0 ( m n ) 。编辑距离支持时间轴的 伸缩，但其计算复杂性也比较高。 1 2 4 粗糙集与时间序列 目前，用基于粗糙集理论来进行时间序列数据分析已经取得了一定的成果。 研究热点主要集中在如何将粗糙集理论适用于时间序列数据挖掘和利用粗糙集 对现实中金融医疗等时间序列数据进行分析，获取一系列规则用于预测时间序列 未来的行为。 在理论方面，文献 3 3 提出了一种基于条件熵的属性约简及规则提取的方 法，该方法考虑时序决策表转换得到的非时序决策表中属性隐含的时间特性。该 方法在对时序数据进行属性约简时，采用粗糙熵与时问距离相结合的方法，使得 最终得到的约简在时序方面是较优的。 文献 3 4 提出了实时时态逻辑的框架，使用时间变量来表示时态序列。文献 3 5 使用动态变化得方法来检测时间序列的模式，但没有就时序的处理算法的实 现做深入探讨。 文献 3 6 构造了基于动态信息系统相适用的粗糙集模型，把传统的粗糙集理 论应用于动态信息系统。 文献 3 7 通过基于移动窗口技术对时间序列数据的挖掘做了预测分析，其主 要思想是通过在数据序列中移动窗口，只有落入窗口内的数据的时间依赖才被列 入考察范围。人们在对时间序列数据进行数据挖掘时，把过多精力侧重于对未来 数据走势的预测，时常忽视了对其中非时序依赖信息的考虑。然而，在时间序列 数据分析中可以挖掘的信息是多方面的，它们相互补充、相互促进，如果在上述 移动窗口的同时能够再考虑其它方面的依赖信息，则势必将更能揭示出其中隐含 的规律。 7 硕士学位论文 第一章绪论 文献 3 8 提出了时态信息系统和实时时态信息系统的概念，提出了一种时态 信息系统转化为信息系统的方法。文献 3 9 针对时态信息系统中含有缺失信息情 况，提出了“填充值”和“增加步幅”两种改进方法，使之适用于一般的时间序 列的挖掘。 文献 4 0 提出了基于r o u g h 集的时间序列数据挖掘策略，包括非时序信息以 及时态信息系统获取的各种策略，强调了时间序列数据中的多方面信息，包括原 始数据及其变化量、变化率所提供的信息。 文献 4 1 针对文献 3 8 1 中的方法，提出了一种“趋势增量”的方法，该方法 对信息表中的每个属性增加一个新的属性，一个用于标定属性的起点，另一个用 于描述原属性值的变化趋势。通过该方法转换后信息系统的对象的属性数有所减 少，降低了规则提出的复杂度，但该方法只考虑了与当前时间片最近的一个时间 片数据，由于没有考虑更多的历史数据，获取的规则比较简单，难以满足实际需 求，具有一定的局限性。另外，还提出了一种将实时时态信息系统转换为时态信 息系统过程中基于最小时问问隔的方法，与传统的基于最大公约数方法相比，利 用该方法转换后的时态信息系统中对象个数较少，在较少的对象的信息系统上使 用粗糙集方法进行数据挖掘无疑将能很大程度上降低计算复杂性。 文献e 4 2 在文献 4 1 的基础上，对于如何将时态信息系统转化为信息系统提 出了一种“相对趋势增量法”，使得生成规则更能表达属性值的变化趋势，并指 出在规则集较庞大的情况下，可采用规则约简的方法加以解决。 在实际应用中，对时问序列数据进行分析的过程主要包括三部分：预处理、 属性约简和规则获取。其中数据预处理主要是利用信号处理技术清洗数据，然后 将清洗后的时间序列按照自身的特征( 如斜率，拐点，极值) 对其进行分割，分 割后每个时间段内的变化趋势保持不变，这样就将时间序列转换成为一系列静态 模式( 每种模式代表一种行为趋势) ，从而去掉其时间依赖性。再将决定各种模 式的相关属性抽取出来组成一个适用于粗集理论的信息表，然后采用粗集理论对 信息表进行属性约简和规则获取，所得到的规则就可以用于预测时间序列在未来 的行为档一“。 1 3 论文的主要内容与结构 粗糙集理论及方法是应用于数据分析，处理不精确、不一致和不完备信息的 新工具，能在保持信息系统分类能力不变的前提下，通过知识约简有效地导出问 题的决策规则，不需要任何先验信息。论文将粗糙集理论与时间序列数据分析相 结合，针对时间序列数据的特点，在粗糙集理论基础上对信息系统获取方法，时 序数据库增量式属性约简等方面展开了研究。 8 硕+ 学位论文 第一章绪论 1 3 1 论文的主要研究内容 由于自然界里的事物之间是相互联系和相互影响的，事物的运动、变化和发 展有其内在的必然性，因而已经发生的历史时问序列与将来发生的时间序列之间 必然有其内在的联系。因此，我们通过分析和研究反映事物过去的运动、变化和 发展的历史时间序列数据，在很大程度上是可以发现事物变化发展的内在规律 的，这就能为决策者制定决策提供重要的参考信息或知识。本文首先介绍了粗糙 集的基本理论，包括粗糙集中的上近似和下近似，正区域、负区域和边界域，不 确定性的度量，粗糙集的族集描述以及属性约简。 为了使粗糙集理论更好的适用于时问序列数据分析，本文主要对信息系统获 取方法和增量式属性约简两个方面进行了深入研究： 1 信息系统获取方法 信息系统中时间序列数据的出现，使得有必要针对这一特殊的数据类型的分 析给出相应的方法，发现其数据体现的特殊规律，以及它们的变化给信息系统带 来的影响。时间序列数据中属性值是随时间变化的，为了能利用粗糙集理论对时 间序列数据进行分析，必须将时态信息系统( t i s ) 转化为适用与粗糙集方法处理 的传统信息系统( i s ) 。利用粗糙集理论来进行时间序列数据分析，关键是将时态 信息系统转化为适用粗糙集方法处理的传统信息系统。 本文研究了时态信息系统的获取方式，分析了时态信息系统( t i s ) 转换成信 息系统( i s ) 以及实时时态信息系统( r t t i s ) 到时态信息系统( t i s ) 的各种转换方 法。在时念信息系统( t i s ) 转换成信息系统( i s ) 过程中，转换过程中回溯时间片 长度的确定是一个重要的问题，本文在现有的方法基础上提出了一种基于时间粒 度的时态信息系统转化方法。本文认为在时间序列数据分析中越靠近当前时间的 数据越有参考价值，该方法在回溯时间片很大情况下，有效的减少了转换后信息 系统属性个数，而且可以根据实际需要灵活的选取回溯属性。 2 增量式属性约简研究 属性约简是粗糙集理论研究的一个重要内容，通过属性约简删除了决策信息 系统中的冗余信息。在大型知识库中，经常存在大量的冗余数据。冗余数据的存 在，不仅浪费储存空间，而且干扰了人们做出正确而简洁的决策。属性约简就是 在保持知识库的分类或决策能力不变的情况下，删去其中不相关或次要的知识， 对知识库进行浓缩，保留其重要知识。 实际应用中，时序数据库往往是动态变化的，对于动态变化的数据库有两种 处理方法，一种是每次数据更新时对新数据库重新进行数据挖掘，另一种是在原 有数据挖掘的结果上，充分利用原有结果对更新的数据库进行增量式数据挖掘。 对于大型数据库，一方面，数据挖掘算法的时空开销往往都很大；另一方面，数 9 硕士学位论文 第一章绪论 据挖掘过程本身又是一个反复的交互式过程，用户的本次挖掘与前次挖掘往往有 较大的重复性，充分利用上次挖掘结果，可以提高数据挖掘的效率，所以增量式 学习成为了人工智能领域一个重要的研究内容之一。 在动态数据库中对象会不断更新，动态数据库的约简会随着数据库的变化而 变化，利用新增加的对象与原有约简的关系进行修正，大大节省了计算量，提高 的增量式约简的效率。本文在改进的区分矩阵的基础上，着重讨论了增量式属性 约简算法，通过对基于属性出现频率约简算法研究，对属性出现频率计算方法进 行改进，提出了一种快速的增量启发式属性约简算法。提出了一种快速的增量式 属性约简算法，该算法可以同时处理动态变化决策表添加和删除数据的情况，并 且在实际运用中可以循环调用，具有较好的实用性。最后选取u c i 数据集进行实 验仿真，对动态数据库增量式约简算法进行实验分析，有效地验证了上述算法的 有效性。 1 3 2 论文结构 论文共分六章，结构如下： 第一章，绪论。简要介绍课题的研究背景和意义、数据挖掘技术、粗糙集理 论和时间序列数据分析的国内外研究现状，以及论文的主要研究内容和文章结 构。 第二章，粗糙集理论基础。本章介绍粗糙集理论的基础内容，包括等价关系、 上下近似与粗糙集合、知识的约简、知识的依赖性和属性重要，决策信息系统等 基本概念。 第三章，时态信息系统获取方法研究。本章介绍了实时时态信息系统，时态 信息系统和信息系统基本概念，着重论述了实时时态信息系统到时态信息系统以 及时态信息系统到信息系统之间的各种转换算法，针对回溯法的不足，提出了一 种基于时间粒度的时态信息系统到信息系统的转换算法，有效地减少了转换后信 息系统属性个数。 第四章，增量式属性约简研究。本章针对时间序列数据动态变化的特性，对 动态变化的决策表进行属性约简处理进行了深入研究，本文在改进的区分矩阵的 基础上，提出了一种增量启发式属性约简算法，该算法能处理不一致数据库的动 态更新，特别适用于数据库动态更新频率高，数据更新量较小的数据库动态更新。 最后通过试验证明了该算法的有效性。 第五章，总结与展望。对论文的研究工作进行总结，对未来的研究工作进行 展望，并提出进一步研究的方向。 1 0 硕士学位论文 第一章绪论 1 4 本章小结 现实应用中，数据量的不断增大给正在迅速发展中的粗糙集理论方法与技术 提出了挑战，本章介绍了课题的研究背景与意义，数据挖掘技术，粗糙集理论一 些基本特点，结合时间序列数据分析领域综述了国内外研究现状，最后概述了论 文的主要研究内容和总体结构组织。 硕十学位论文 第二章粗糙集理论基础 第二章粗糙集理论基础 粗糙集理论是一种处理模糊和不确定性问题的数据分析方法，粗糙集的方法 的最大优点在于它不需要关于数据预先的或附加的信息，而且容易领会和使用。 粗糙集数据分析方法从数据本身的特性出发，分析其中的分类关系和知识依赖 性，从原始数据集中获取规则并发现其隐含的知识。粗糙集的数据分析方法自问 世以来已经得到了广泛的应用，为机器学习、决策分析、模式识别、模糊控制等 领域提供了一种新的有效的数学分析方法。 2 1 粗糙集的基本概念 粗糙集是一种新的处理模糊和不确定性知识的数学工具。其主要思想是在保 持分类能力不变的前提下，通过知识约简，导出问题的决策或分类规则。粗糙集 理论是建立在分类机制基础上的，它将分类理解为在特定空间上的等价关系，而 等价关系构成了对该空间的划分。其主要思想是利用己知的知识库，将不精确或 不确定的知识用已知的知识库中的知识来( 近似) 刻画。该理论与其它处理不确 定和不精确问题理论的虽显著的区别是它无需提供问题所需处理的数据集合之 外的任何先验信息。并且与概率论、模糊数学、证据理论等其它处理不确定或不 精确问题的理论有很强的互补性。 定义2 1 设u 是非空论域；r 是一个不可分辨关系，即等价关系；a p r = ( u ， r ) 为一个近似空间；u r 表示r 中所有等价类的集合，又称u 的分类；【x 】尺表示 r 中包含x 的等价类。 定义2 2 设x 是u 的子集，且x - - - - u ，则下近似是x 包含的所有原子集合的 并，即x 包含的最大复合集合( 最大包含) 星( x ) = 缈( x ) ke ul 【x 】月x = u 【x 】凡。 ( 2 1 ) j r c - x 定义2 3 设x 是u 的子集，且xg u ，则上近似是与x 相交非空的所有原 子集合的并，即包含x 的最小复合集合( 最小包含) 页( x ) = 缈( x ) x ui 【x 】rn x m =u【x 】尼。 ( 2 2 ) i ，】足n x 中 硕士学位论文第二章粗糙集理论基础 显然：当a p r ( x ) x a p r ( x ) ；当a p r ( x ) = a p r ( x ) 时，x 是r 一可精确定义的。 集合x u 的下、上近似将论域u 划分为三个不相交的区域： 正区域：p o s ( x ) = a p r ( x ) ，正区域( 即下近似) 的元素一定属于x 。 负区域：n e g ( x ) = u 一面( x ) ，负区域的元素一定不属于x 。 边界域：b n d ( x ) = a p r ( x ) 一a p r ( x ) ，边界区域的元素不能在x 和它的补集 j 上精确分类，边界域是论域的不确定域。 r s 理论中集合的模糊性基于边界的概念，一个模糊的概念具有模糊的不可 被明确划分的边界，其模糊性是由不确定性来定义的，因此考虑不确定性十分必 要。 定义2 4 对于x u 的r 的精确度p r ( x ) 表示集合x 的知识完全程度或集 合x 的确定度： p r ( x ) ：广a p t ( x ) n ：a p r ( x ) ：f a p l r ( x ) ( 2 - 3 ) 风x 2 匾两面网2 雨两 p r ( x ) 越大，精确度越高，知识系统u r 对x 的可表示程度越高，粗糙度越 低。 ( 1 ) x 为空集，p 月( x ) = 1 ； ( 2 ) x 是复合集合，那么p r ( x ) = 1 ，说明可用知识系统u r 中的知识精确 表达x ； ( 3 ) x 不是复合集合，那么0 p 尺( x ) 1 ，不能用知识系统u r 中的知识精 确表达x ，知识系统u r 对x 的表示是粗糙的。 定义2 5 对于x u 的r 的粗糙度d 霄( x ) 反映了解集合x 的知识不完全程 度或集合x 的不确定度： 蹦耻h 小h 一矧= 鬻 4 ， ( 1 ) d 凡( x ) = 0 ，x 的边界域为空，x 是r 可精确定义的； ( 2 ) 0 d r ( x ) ， x 2 ，) 【4 ，x 7 ，x s ) ，u r 3 = x , ，x s ， x 6 ， x 2 ，x 7 ，x 8 ) ， x 3 ，x 4 ) ，贝i j x i r i m x i ， x 4 ，x s ，【x 2 v a 2 x l ，x 3 ，x d 。 ( 1 ) 若w = r i ，r 2 ) ，则【x l 】w = x l ，x d ，即x i 和x 5 对于关系r l 、r 2 来说都是不可分辨的，且i n d ( w ) = “x i ，x 5 ， x 2 ，x 8 ， x 3 ) ， x 4 ， x 6 ) ， x 7 ) 。 ( 2 ) 若w = r i ，r 2 ，r 3 ) ，则i n d ( w ) = “x i ，x d ， x 2 ，x d ， x 3 ， ) 【4 ， x d ， x 7 ) ) 。对于u 上的任意两个子集x l = x l ，x 4 ，x 7 ) ，x 2 = x 2 ，x 5 ，x s ，可 得到下、上近似为： 一a p r ( x i ) 5 x 4 ) u x 7 ) 2 x4 ，x 7 ) ， 一a p r ( x ) = x l ，x ， u x 。 ux ，) = x ，x 4 x ，x ，) ， a p r ( x ：) = x ： u x 。 = x ：，x 。 ， 1 4 硕士学位论文第二章粗糙集理论基础 一a p r ( x ：) = x l ，x ， u x ：) u x 。 = x 。，x ：，x 5 ，x 。) 。 在信息系统i s = 中，考察每一个属性a r ，若删除属性a 之后 仍然保持原有的由属性集r 确定的不可分辨关系，即i n d ( r ) ：i n d ( r 一 a ) ) ，则 称属性a 是冗余的，可以在信息系统中被约简，否则，属性a 是非冗余的。如果 信息系统中包含冗余的属性，就需要找出所有可能的最小属性子集，由它们确定 的不可分辨关系与由完整的属性集确定的不可分辨关系是等价的，我们称这样的 属性子集为原属性集的约简。 若对任意a r ，a 非冗余，则称属性集r 为独立的，如果r 是独立的，p r ， 则p 也是独立的。在用属性集r 表达论域知识时，r 独立意味着属性集里的每一 个属性都是必不可少的，它可以独立地表达一组知识分类。 定义2 7 在信息系统i s = 中，属性子集p c _ r ，当p 独立，且 i n d ( p ) ：i n d ( r ) ，则p 为属性集r 的约简，用r e d ( r ) 表示。 定义2 8 信息系统i s 中，属性集r 可能存在多个约简，