（计算机应用技术专业论文）基于粗糙集的时间序列数据挖掘.pdf

招j 要 摘要 近年来，几乎在各种领域都需要处理时间序列数据，对时间序列数据的研 究也涉及很广。时间序列数据中包含着很多有用的信息，蕴含着许多潜在的事 物发展的规律。粗糙集理论是波兰数学家z p a w l a k 于1 9 8 2 年提出的一种处理含 糊性和不确定性问题的数学工具，已成为计算机科学与技术领域中颇具挑战力 的方向之一。约简是粗糙集理论的重要内容，通过删除知识库中多余的属性值， 来保留知识库中的重要知识，以提高知识的质量，方便用户决策。本文主要研 究时间序列数据的属性约简，以及关联规则的挖掘。具体工作如下： ( 1 ) 时序信息系统从原始离散数据和实时时序信息系统中获取方法的研究 和分析，并且形成非时序信息表。 ( 2 ) 对属性约简方法的研究，主要分为传统属性约简和非时间序列信息表的 属性约简研究。本文提出了基于信息增益和时间属性优先的属性频率约简策略。 ( 3 ) 对规则获取策略进行了研究。通过分析规则获取的一般方法在直接获得 最小规则集时存在的不足，本文提出一个改进的规则获取算法，可以直接获取 最小规则集。 ( 4 ) 编写模拟程序对时间序列数据进行了属性约简及规则获取，说明了所提 出的改进方法的可行性和有效性。 关键词：时间序列：粗糙集；数据挖掘；属性约简；规则获取 a b s t r a c t a b s t r a c t i nr e c e n ty e a r s ，t e m p o r a ld a t ae m e r g e di nv a r i e df i e l d s ，a n dm a n ys t u d i e so fi t h a db e e nh e l d t e m p o r a ld a t a i n c l u d e si n t e r e s t i n gi n f o r m a t i o na n dc o n t a i n ss o m e r u l e so ft h i n g s r o u g hs e tt h e o r y , w h i c hw a sp r o p o s e db yp o l i s hm a t h e m a t i c i a n p a w l a k zi n1 9 8 2 ，i sam a t h e m a t i c a lt o o lt oa n a l y z eu n c e r t a i na n dv a g u ed a t aa n dh a s b e e no n eo ft h e c h a l l e n g i n gf i e l d so fc o m p u t e rs c i e n c ea n dt e c h n o l o g y d a t a r e d u c t i o ni st h ek e y p a r to ft h er o u g hs e tt h e o r y r e d u c t i o no fk n o w l e d g ec o n s i s t si n r e m o v i n gs u p e r f l u o u sa t t r i b u t e s ( v a l u e s ) i nt h ek n o w l e d g eb a s e ，i ns u c haw a yt h a t t h ee l e m e n t a r yk n o w l e d g ei sp r e s e r v e d ，s oi tc a ni n c r e a s et h ek n o w l e d g e q u a l i t ya n d h e l pp e o p l em a k ed e c i s i o n t h i sd i s s e r t a t i o nf o c u s e so nt h er e s e a r c ho fa t t r i b u t e s r e d u c t i o n so f t e m p o r a ld a t aa n dt h ed a t am i n i n go fa s s o c i a t i o nr u l e s ，t h ec o n t r i b u t i o n s a r ea sf o l l o w s ： 1 t h er e s e a r c ha n da n a l y s i so fg e t t i n gt i m es e r i e si n f o r m a t i o ns y s t e mm e t h o d s f r o mb o t ho r i g i nd i s c r e t ed a t aa n dr e a l t i m et i m es e r i e si n f o r m a t i o ns y s t e ma n d n o n - t i m i n gi n f o r m a t i o nt a b l e 2 t h er e s e a r c ho fa t t r i b u t er e d u c t i o na p p r o a c h e sm a i n l yc o n t a i n st h er e d u c t i o n o ft r a d i t i o n a li n f o r m a t i o nt a b l ea n dn o n t i m e s e r i e st a b l e t h i sd i s s e r t a t i o np u t su p i n f o r m a t i o ng a i na n dt i m ep r i o r i t ya t t r i b u t e st h ep r o p e r t i e so f t h e 仔e q u e n c yr e d u c t i o n s t r a t e g y 3 w eh a v ear e s e a r c ho nt h ea c q u i s i t i o no fr u l e sb e f o r ep r o v i d i n ga ni m p r o v e d s t r a t e g yo nr u l ea c q u i s i t i o nu n d e rt h ei l l u m i n a t i o no fe x a m p l e s ，w ea n a l y z ea d r a w b a c ko ft r a d i t i o n a lo n eo ng a i n i n gm i n i m a lr u l e ss e t d i r e c t l y t h ei m p r o v e d s g a t e g yc a no b t a i nm i n i m a lr u l e ss e td i r e c t l y 4 t h es i m u l a t i o np r o g r a mc a nr e d u c et h ea t t r i b u t e so ft e m p o r a ld a t aa n df i n a l l y o b t a i nm jn i m a 】r u l e s k e yw o r d s ：t i m es e r i e s ；r o u g hs e t ；d a t am i n i n g ；a t t r i b u t er e d u c t ；r u l e s a c q u i s i t i o n l i 学位论文独创性卢明 学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得南昌大学或其他教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文作者签名( 手写) ：o 善丁 签字日期：a 培年位月多易日 学位论文版权使用授权书 本学位论文作者完全了解一南昌太学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权南昌太堂可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编本学位论文。同时授权中国科学技术信息研究 所将本学位论文收录到中国学位论文全文数据库，并通过网络向 社会公众提供信息服务。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：x 孥1导师签名：卯和b 裳 签字日期：沙 年亿月以日签字日期：觇年l2 月6 日 第1 章绪论 第1 章绪论 1 1 研究背景 面对信息社会中数据和数据库的爆炸式增长，人们在日常事务处理和科学 研究中积累了大量的各种类型的数据。在人们所保存的数据中，有许多是“时 问序列”( t i m es e r i e s ) 1 1 l 数据。时间序列类型数据【厶3 】就是按照时间先后顺序排列 各个观测记录的数据集。时间序列在社会生活中各个领域中都大量广泛存在， 如金融证券市场中每天的股票价格变化；商业零售行业中，某项商品每天的销 售额；气象预报研究中，某一地区的每天气温与气压的读数；以及在生物医学 中，某一症状病人在每个时刻的心跳变化等等。不仅如此，时间序列也是反映 事物运动，然而我们应该注意到时i 日j 序列不仅是对历史事件的记录，而且是展 现事物变化的显方式。随着时间推移和时间序列数据的大规模增长，如何对这 些海量的时间序列进行分析处理，挖掘其背后蕴涵的价值信息，对于我们揭示 事物发展变化的内部规律，以及不同的事物之间的相互作用关系，为人们正确 认识事物和科学决策提供依据等等具有重要的实际意义。因此有关时间序列分 析的研究一直以来就受到了许多研究人员的广泛重视，成为一个具有重要理论 和实用价值的热点研究课题。 人们采用数据挖掘技术对这些时间序列数据进行分析目的就是为了能获得 隐含的规则来提供决策。然而，这些数据本身有可能是不精确的、不完整的， 这就需要一种对于处理这种特点的数据比较有效的工具。粗糙集理论是一种处 理模糊性和不确定性的新型数学工具，能有效地处理不精确、不一致、不完整 的信息，并从中发现隐含的知识，揭示潜在的规律。粗糙集是数据挖掘的方法 之一。粗糙集【5 】由z p a w l a k 于1 9 8 2 年提出，是继概率论、模糊集理论、证据理 论之后的又一个处理不确定性的数学工具。该理论不需要任何附加的信息或先 验知识，就能有效地分析和处理不精确、不完整和不一致的数据，并从中发现 隐含的知识，揭示潜在的规律。粗糙集理论己经在很多领域如数据挖掘、机器 学习、模式识别、决策分析等取得了成功的应用。 随着当今数据采集和存储技术的不断发展，数据库中存储的数据量急剧增 加，数据库的规模也因此变得越来越庞大。人们发现缺少的不在是信息，而是 第l 章绪论 从信息海洋中提取有利的信息。如何分析数掘并从中挖掘出有川的知识是一项 既费时又难于进行的工作。通常，对于特定领域的数据挖掘需要有一定的背景 领域知识，并在此基础上采用某种有效工具从数据集中获取更多的隐含的、先 前未知的并具有潜在价值的知识。这种挖掘在j 工业过程控制、医疗诊断、股票 分析、水文气象等领域尤显重要，因为这些领域的数据有一个共同的特点，即 它们都记录了某个领域的时间序列信息，且信息量特别巨大，如果没有合适的 挖掘手段1 6 。9 】则势必给以后的决策和新数据的预测带来困难。信息系统中时间序 列数据的出现使得有必要针对这一特殊数据类型的挖掘给出相应的策略，以便 发现在某段时间内连续记录的某属性序列值的变化规律，以及它的变化给其它 属性值所带来的影响。本文旨在基于粗糙集理论与方法来研究时间序列数据， 以便挖掘时间序列数据中有用的信息和提取有用的规则帮助人们进行科学的决 策。 1 2 研究内容 本文的研究内容是如何使用粗糙集工具对时间序列数据进行数据挖掘，提 取有用的规则供人们决策。本文的主要研究内容如下： ( 1 ) 分析研究如何从原始的时间数据中获取时间序列数据并将所得数据转 变变为非时间序列数据； ( 2 ) 分析研究构建含有时间信息的传统决策表； ( 3 ) 基于粗糙集的方法研究含有时间信息的传统决策表的属性约简方法， 对所形成的决策表进行属性约简，得到属性约简集； ( 4 ) 研究规则获取策略，实现对约简后的决策表提取最小规则集； ( 5 ) 编写演示程序实现对时序相关的数据进行时序转换、属性约简并获取 规则，以便验证所提出的约简策略和所改进的规则提取算法的有效性。 1 3 数据挖掘研究概述 1 3 1 引言 数据挖掘1 ( d a t am i n i n g ) 捌a 大量的、不完全的、有噪声的、模糊的、随 机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息 和知识的过程。这一过程是从数据当中发现趋势或模式，目标是通过对大量数 2 第1 章绪论 据的分类从而发现新的信息。由于数据挖掘足一一门受到来自各种不同领域的研 究者关注的交叉性学科，因此导致了很多不同的术语名称。如k d d 、数据分析、 数据融合( d a t af u s i o n ) 以及决策支持等，最常用的术语是“知识发现”和“数据 挖掘”。相对来讲，数据挖掘手要流行于统计界( 最早出现于统计文献中) 、数据 分析、数据库和管理信息系统界；而知识发现则主要流行于人工智能和机器学 习界。 数据挖掘【9 】是2 0 世纪9 0 年代中期兴起的一项新技术，它是知识发现过程中 的关键步骤。所谓数据挖掘，就是从数据库中抽取隐含的、以前未知的、具有 潜在应用价值的信息的过程n 引。近些年来，它引起了信息产业界和理论界的极 大关注，并吸引了一大批研究者和开发者。关联规则挖掘作为数据挖掘的一种 重要模式，已成为数据挖掘领域的一个非常莺要的研究课题。所谓关联规则挖 掘是：从海量数据库提取给定数据项集的有趣模式。它在管理、生产控制、市 场分析、工程设计、科学探索等领域都有着重要的应用。目前又逐渐向生物医 学、金融设计、电信等领域渗透。 现在的社会已经进入了网络信息时代，计算机和网络信息技术的高速发展 和广泛应用使得各个领域的数据和信息急剧增加。随着信息量的不断增长，对 信息分析工具的要求也越来越高，人们希望能从海量数据中挖掘出潜在的、有 利用价值的信息，获取其潜在的依赖模型。这给人类的智能信息处理能力提出 了前所未有的挑战。由此产生了人工智能研究的一个崭新的领域数据挖掘 和数据库知识发现。1 9 8 9 年8 月，在第1 1 届国际人工智能联合会议的专题研讨 会上，首次提出基于数据库的知识发t 见( k d d 出，k n o w l e d g ed i s c o v e r y i nd a t a b a s e ) 技术。该技术涉及机器学习、模式识别、统计学、智能数据库、知识获取、专 家系统、数据可视化和高性能计算等领域，技术难度大，一时难以应付信息爆 炸的实际需要。到了1 9 9 5 年，在美国计算机年会( a c m ) 上，提出了数据挖掘 ( d m ，d a t am i n i n g ) 的概念，即通过从数据库中抽取隐含的、未知的、具有潜在使 用价值信息的过程。在1 9 9 6 年w j f r a w l e y ，g p i a t e t s k y - s h a p i r o 等人提出了比较 公认的数据挖掘定义：数据挖掘就是从大型数据库的数据中提取人们感兴趣的 知识。这些知识是隐含的、事先未知的潜在有用信息，提取的知识表示为概念 ( c o n c e p t s ) 、规则( r u l e s ) 、规律( r e g u l a r i t i e s ) 、模式( p a t t e r n s ) 等形式。这 种定义把数据挖掘的对象定义为数据库。而更广义的说法是：数据挖掘意味着 在一些事实或观察数据的集合中寻找模式的决策支持过程。数据挖掘的对象不 第1 章绪论 仪是数捌库，也可以是文件系统，或其它任何组织在一起的数捌集合，例如万 维网的信息资源、数据仓库等。 数据挖掘是一个多处理阶段，数据挖掘过程主要有三个过程组成旷1 ：数据 预处理、数据挖掘、结果解释和评价，整个过程是一个不断循环和反复的过程。 数据预处理主要目的是根据用户要求从数据库中提取与数据挖掘有关的数据， 并保证数据的完整性和一致性。 数据挖掘主要包括：确定数据挖掘的目的，运用正确高效的算法从数据库 中提取用户所需要的知识。结果的解释和评价则指：对所挖掘的知识进行解释， 以一种用户能够理解的方式呈现给用户。这期间可能还要对知识的一致性进行 检查以消除相互矛盾的知识。在数据挖掘和知识发现的诸多方法中，粗糙集理 论与方法对于处理复杂系统不失为一种较为有效的方法。因为它与概率方法、 模糊集方法和证据理论方法等其他处理不确定性问题理论的最显著的区别和最 大的优势是它无需提供问题所需处理数据集合之外的任何先验信息。粗糙集理 论的主要特点在于它恰好反映了人们用粗糙集方法处理不分明问题的常规性， 即以不完全信息或知识去处理一些不分明现象的能力，或依据观察、度量到的 某些不精确的结果而进行分类数据的能力。当然，由于这个理论未包含处理不 精确或不确定原始数据的机制，因此单纯地使用这个理论不一定能有效地描述 不精确或不确定的实际问题，所以需要和其他处理不确定性问题的理论进行互 补。 1 3 2 数据挖掘的研究现状 目前，数据挖掘技术发展得十分迅速，国内的科研机构也十分重视这一方 面的研究，但与国外相比，国内对数据挖掘的研究稍晚，没有形成整体力量。 数据挖掘作为一门具有广泛应用价值的新兴学科，在许多领域都有很好的应用 前景。针对每个特定领域的应用，就应该将数据分析技术与特定的领域知识结 合起来，才能提供最为有效的数据挖掘方案。 “从数据库中发现知识”即k d d f 2 2 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 s ) - - 词 首次出现在1 9 8 9 年8 月举行的第1 1 届国际联合人工智能学术会议上。迄今为止， 由美国人工智能主办的k d d 国际研讨会己经召开了8 次，规模由原来的专题讨 论会发展到国际学术大会，人数由二三十人到七八百人，研究重点也逐渐从发 现方法转向系统应用，并且注重多种发现策略和技术的集成，以及多种学科之 4 第l 章绪论 间的相互渗透。其他内容的专题会议也把数据挖掘和知识发现列为议题之一， 成为当前计算机科学界的一大热点。此外，数据库、人工智能、信息处理、知 识工程等领域的国际学术刊物纷纷卅辟了k d d 专题或专刊。i e e e 的k n o w l e d g e a n dd a t ae n g i n e e r i n g 会刊首先在1 9 9 3 年心版了k d d 技术专刊，所发表的5 篇 论文代表了当时k d d 研究的最新成果和动态，较全面地论述了k d d 系统方法 论、发现结果的评价、k d d 系统设计的逻辑方法，集中讨论了鉴于数据库的动 态性冗余、高噪声和不确定性、专家系统、人工神经网络、数理统计分析系统 的联系和区别以及相应的基本对策。不仅如此，在i n t e r n e t 上还有不少k d d 电 子出版物，其中以半月刊k n o w l e d g ed i s c o v e r yn u g g e t ：最为权威，另一份在线 周刊为d s * ( d s 代表决策支持) ，1 9 9 7 年1 0 月7 日开始出版。在网上，还有一 个自由论坛d me m a i lc l u b ，入们通过电子邮件相互讨论“数据挖掘和知识发现” 即d m k d ( d a t am i n i n ga n dk n o w l e d g ed i s c o v e r y ) 的热点问题。而领导整个潮流的 d m k d 开发和研究中心是设在美国e m d e n 的i b m 公司开发部。随着d m k d 研究逐步走向深入，人们越来越清楚地认识到，d m k d 的研究主要有3 个技术 支柱，即数据库、人工智能和数理统计。 与国外相比，国内对d m k d 的研究稍晚，没有形成整体力量。1 9 9 3 年国家自 然科学基金首次支持对该领域的研究项目。目前，国内的许多科研单位和高等 院校竞相开展知识发现的基础理论及其应用研究，这些单位包括清华大学、中 科院计算技术研究所、人民大学的数据挖掘中心、空军第三研究所、海军装备 论证中心等。其中，北京系统工程研究所对模糊方法在知识发现中的应用进行 了较深入的研究，北京大学也在开展对数据立方体代数的研究，华中理工大学、 复旦大学、浙江大学、中国科技大学、中科院数学研究所、吉林大学等单位开 展了对关联规则开采算法的优化和改造；可南京大学、四川大学和上海交通大 学等单位探讨、研究了非结构化数据的知识发现以及w e b 数据挖掘。中国人民 大学统计学院成立的数据挖掘中心旨在与海内外机构广泛合作，致力于企业数 据挖掘的应用、研究及培训，承接技术解决方案、数据挖掘和知识管理的现代 信息管理咨询项目。由他们从2 0 0 1 年开始举办的“成功企业数据挖掘即数量化 管理论坛到今年已是第三届了，论坛取得了丰硕成果。 此外，数据挖掘也已经渗透到国内的一些行业。在金融行业中，金融事务 需要搜集和处理大量数据，对这些数据进行分析，发现其数据模式及特征，然 后可能发现某个客户、消费群体或组织的金融和商业兴趣，并可观察金融市场 第1 章绪论 的变化趋势。零售业是数据挖掘的主要应用领域，这是因为零售业积累了大量 的销售数据，顾客购买历史记录，货物进出，消费与服务记录，尤其如今电子 商务和条形码的运用等。电信、计算机网络、因特网和各种其他方式的通信融 合是目商仃的大势所趋，而且随着许多国家对电信业的丌发以及新兴计算与通信 技术的发展，电信市场正在迅速扩展并越发竞争激烈。电信业己经迅速地从单 纯的提供市话和长话服务转变为提供综合电信服务，如语音、传真、寻呼、移 动电话、图象、电子邮件、计算机以及其他数据通信服务。 1 4 时序数据挖掘 1 4 1 时序数据挖掘的研究现状 数据挖掘【1 2 j 4 】作为- r - j 具有广泛应用价值的新兴学科，在许多领域都有很 好的应用前景。针对每个特定领域的应用，就应该将数据分析技术与特定的领 域知识结合起来，才能提供最为有效的数据挖掘方案。 在数据挖掘与知识发现中，实际的数据收集许多都与时间有关，例如数据 仓库的数据都有时间同志，研究销售、股票、气象、洪水和地震等数据变化和 知识发现的问题都与时间有关，因此必须研究带时间约束的数据挖掘问题。我 们把具有时间属性约束的数据称为时态数据；将包含时态数据的数据库称为具 有时态约束的数据库；将在时态数据中进行知识发现的过程称为时态数据挖掘。 这里的时间有多种概念解释：有效时间，交易时间，事件时间等等。时态数据 中包含的时间属性可以是以上一种时间，也可以是以上几种时间的组合。时间 属性能利用1 n f 范式并入数据元组中。时刻、时间间隔、时刻点的集合都能用 来作为一个时间戳去表示事件的时间参数。 近年来，时态数据挖掘研究主要有几个重要方面，包括趋势分析、相似搜 索、与时间有关数据的序列模式挖掘和周期模式挖掘等方面。 1 、趋势分析 目前一般有三种主要的变化用于特化时态数据【b 】。 长期或趋势变化：它用于反映一般的变化方向，其时序图是在较长时间间 隔上的数据变化。这种变化反映为一种趋势线或趋势曲线。循环变动或循环变 化：主要是指循环性，即趋势线或曲线在长期时间内呈摆动迹象。它可以是也 可以不是周期性的。即在等时问间隔之问，循环不需要沿着同样的模式演进【6 。8 1 。 6 第1 章绪论 季节性变动：它反映的是每年都重复出现的事件，如春节前过年物资的销 售会突然增加很多。换句话说，季节性变动是指同一或近似同一的模式，在连 续几年的有关月份期间重复出现。 非规则性或随机变化：它反映的是随机或者偶然事件引起的零星时序变化。 如火灾、瘟疫或劳工纠纷等。 2 、相似搜索 数据库查询要求找出与查询要求精确匹配的数据，而相似搜索是发现那些 与查询序列轻微不同的数据序列。给定一个时态数据序列，相似搜索问题就是 发现所有与要查询的序列相似的时态数据序列。在具有时态约束的数据库中进 行相似搜索，通常使用欧氏空间距离作为相似性计算的依据。两种常用的数据 独立转换有：离散傅立叶转换( d f t ) 和离散小波转换( d w t ) 。 3 、序列模式挖掘 序列模式挖掘是指挖掘相对时间或其他模式出现频率高的模式。由于许多 商业交易、天气数据和生产过程都是时间序列数据，在针对目标市场、客户吸 引、气象预报等的数据分析中，序列模式挖掘是很有用途的。 4 、周期挖掘 周期分析是指对周期模式的挖掘，即在时态数据中找出重复出现的模式。 周期模式挖掘可视为一组分片序列为持续时间的序列模式挖掘。 周期模式挖掘的问题可以分为三类： 挖掘全周期模式。这里每一时间点都影响着时态数据上的循环行为。如 一年中的每一天都对一年中的季节循环起着作用。 挖掘部分周期模式。它描叙在部分时间点上的时态周期。部分周期是一 种比全周期较为松散的形式，在现实世界也更为常见一些。 挖掘循环或周期关联规则。这种规则是周期出现的事件的关联规则。全 周期分析的技术己在信号分析和统计中得到研究。但全周期模式挖掘的 大部分方法不适用于部分周期模式挖掘，或者是代价太大，原因是部分 周期模式在同一周期内混杂有周期事件和非周期事件。 另外，国内外很多专家在时间序列模式发现，多时间粒度的知识发现，时 态约束的关联、周期等方面作了大量研究将时态数据挖掘的研究工作引入更深 更广的领域，取得了大量的研究成果。 7 第1 章绪论 1 4 2 粗糙集在时序数据上应用的研究现状 用粗糙集理论来分析时态数据，目前取得了一些成果。在利用料i 糙集处理 时态数据时，以往的研究主要关注被挖掘的时态数据的时间序歹| j ( t i m es e r i e s ) 特 征，即对象之间保持着严格的时间顺序。时间序列信息分两类，一是不带有实 时约束的时问序列；另一种是带有实时约束的时间序列。不带实时约束的序列 可以看成是按时i 、日j 排列的时间串，事件之间的时间间隔( 采样速率) 是常数：而对 带有实时约束的时间序列，必须考虑事件之间的时间问隔，这些时间间隔可能 是很不一样的。对时间序列的很多研究，一般的目的是根据傅里叶序列或概率 分布建立信号模型。另一个重要方面是时序推理，使用时序逻辑建立实时序列 模型。这些研究的着重点在于数据间的顺序和时间间隔，认为时态数据集与一 般数据集之间的最大区别在于时问维，因此关键是把时态数据集转换为粗糙集 能够处理的数扼集。为此，在信息系统i s ( i n f o r m a t i o ns y s t e m ) 的基础上，引入了 时序信息系统t i s ( t e m p o r a li n f o r m a t i o ns y s t e m ) 和实时时序信息系统r t t i s ( r e a l t i m et e m p o r a li n f o r m a t i o ns y s t e m ) ，目的是将对象的顺序( 或次序) 信息形式化。 虽然粗糙集理论在时态数据集上的应用有了以上的研究和成果，但已有的研究 都是着眼于时态数据在时间上的顺序性，即通过转换，消去时态数据的时间属 性，再用已有的粗糙集理论对数据集进行处理，本质上没有充分利用时态数据 在时间上的其它特点和性质。因此，有必要对其进行更深层次的研究，以便改 进挖掘的效率和质量。 1 5 论文结构安排 本文的后续章节结构安排如下： 第二章介绍了粗糙集的相关概念和理论，为后续章节的研究进行一些必 要的铺垫。 第三章分析研究时间序列信息系统的获取方法，即t i s ( 时序信息系统) 转换为i s ，r t t i s ( 实时时序信息系统) 转换为t i s 。 第四章对属性约简策略进行了改进研究。提出了基于信息增益的和属性 频率优先的属性约简，并给出实例进行说明。 第五章对决策规则进行了研究，给出了规则的提取方法，并给出实例进 行说明。 第1 章绪论 第六章对本文所做的工作进行总结，并对下一步的工作进行展望。 最后是致谢、参考文献、附录和攻读学位期问的研究成果。 9 第2 章粗糙集理论 第2 章粗糙集理论 2 1 知识表达 知以表达是智能信息系统的关键。所谓知识获取，就是要从原始数据信息 中分析发现有用的规律信息，即将知识从原来的表达形式( 原始数据表达形式) 转换为一种新的目标表达( 人类或者计算机便于处理的形式) 。基于粗糙集的理 论的知识发现，主要是借助于信息表这样一种有效的数据表来实现知识表达。 2 1 1 知识的分类概念 通常，我们对现实问题进行处理的时候，会将我们讨论的个体( 或称元素、 对象、样本) 局限在某一个特定的区域范围，这个区域内的所有个体就组成问 题的论域u 。以分类为基础，将分类理解为等价关系，而这些等价关系对论域u 进行划分。论域中由等价关系划分出的任意子集x ，都可以称之为u 中的概念。 这里，我们认为空集也是一个特殊的概念。论域u 中任意概念族称为关于u 的抽象知识，简称为知识，它代表了对u 全体的分类。这样知识就可以定义为： 给定一组数据( 集合) u 上的等价关系集合r ，在等价关系集合r 下对数据集 合u 的划分，称为知识，记为u r 。u 上的一簇划分( 对u 的分类) 称为关于 u 的知识库。关于u 的一个知识库也可以理解为一个关系系统：k = u ，p ，其中 p 为论域u 上的一簇等价关系，根据这些等价关系就可以对u 进行不同划分( 知 识) ，每种划分将把u 分为不同的子集( 概念) 。设r 是u 上的一个等价关系。 u r 表示u 上导出的所有等价类。 x 】r 表示包含元素x 的r 的等价类。如果q 互p 且q ，则nq ( q 的所有等价关系的交) 也是一个等价关系，记作i n d ( q ) 【7 】o 2 1 2 信息表知识表达系统 知识表示就是要研究用机器表示知识的可行的、有效的、通用的原则和方 法。本节我们介绍基于信息表的知识表达形式，它是粗糙集理论中对知识进行 表达和处理的基本工具。 在人工智能研究中，一个实例经常使用属性一值对的集合来表示，实例集就 是这样的实例集合，记为u 。u 可被划分为有限个类x 1 ，x 2 ，x n ，使得x c u ， x i ，x i n x j = ( i j ) ，( i , j = l ，2 ，n 且n x i 三叻。 l o 第2 章粗糙集理论 信息表知识表达系统的基本成分是研究对象的集合，关于这些对象的知识 是通过指定对象的属性( 特征) 和它们的属性值( 特征值) 柬描述的。一般地， 一个信息表知识表达系统i s ( i n f o r m a t i o ns y s t e m ) 可以表示为 s = ( u ，r ，v , o 式中 u ：对象集( 案例，状态，疾病，观测，) ； r ：cu d 子集c 和d 分别称为条件属性集和结果属性集； v ：属性值集合； f 信息函数，它指定u 中每一个对象x 属性值。 为了直观方便，u 也可以写成一个表，纵轴表示实例标记，横轴表示实例属 性，实例标记和属性的交会点就是这个实例在这个属性的值。这个表称为信息 表，是表达描述知识的数据表格。对于每个属性子集b cr ，我们定义一个不可 分辨二元关系( 不分明关系) i n d ( b ) ， 即i n d ( b ) = ( 工，y ) i ( x ，y ) u 2 ，v b b ，6 ( x ) = 6 ( y ) ) 。 每个子集b c _ r 也可称为一个属性，当b 是单元素集时，称b 为原始的， 否则称b 为复合的。属性b 可以认为是用等价关系( 在该属性上的取值相等) 表示的知识的一个名称，称为标识属性。一个表可以看作是定义的一个等价关 系簇，即知识库。 实际上，信息表这种数据表格知识表达系统是对客观对象的描述和罗列，表 达的是属于说明性的指示。当信息表包含的数据足以反映论域的时候，通过属性 所对应的等价关系就可以体现论域中的过程知识，即概念之间的逻辑关系或规则 知识。事实上，从信息表所表述的说明性知识中发现过程性知识( 规则知识) 就 是知识发现的研究内容。下面我们来看两个信息表知识表达系统的例子。 表2 1 信息表 思想( r 。)纪律( r ：)社会实践( 地) x l一般良好很少 x 2一般良好很少 x 3 一般 一般很少 x 4一般良好很少 x 5 先进一般经常 x 6一般一般经常 x ， 先进良好经常 x 8 先进 良好 很少 x 9 一般一般很少 第2 章粗糙集理论 例2 1 表2 1 给出了一个关了：学生信息的信息表。根据这个信息表，我们可 以得出有关的概念描述，如将学生按照思想、纪律和社会时间可以分别进行如 下分类，得到有关学生的概念知识： u r i = x l ，x 2 ，x 3 ，x 4 ，x 6 ，x 9 ， x 5 ，x 7 ，x s ； u r 2 = x 3 ，x 5 ，x 6 ，x 9 ) ， x l ，x 2 ，) q ，x 7 ，x s ； u r 3 = x l ，x 2 ，x 3 ，x 4 ，x 8 ，x 9 ， ) ( 5 ，x 6 ，x 7 ) 。 这罩，信息表中所包含的属性集只有对学生进行描述的属性。 2 1 3 决策表 决策表是一类特殊而重要的知识表达系统，也是一种特殊的信息表，它表 示当满足某些条件时，决策( 行为、操作、控制) 应当如何进行，决策表的定 义如下： 定义2 1 一个决策表是一个信息表知识表达系统s = ( u ，r ，v ，f ) ，r = cud 是属 性集合，子集c 和d 分别称为条件属性集和决策属性集，d 条件属性c 和 结果属性d 的等价关系r n d ( c ) 和i n d ( d ) 的等价类分别称为条件类和决策类。 一个决策表中的结果属性有时是唯一的，称为单一决策；有时是不唯一的， 称为多决策。对于具有多个结果属性的决策表，可以通过采用适当的方法将其 变换成为单一决策的决策表。本文所谈论的决策表都为单一决策。 2 2 粗糙集基本理论 粗糙集理论的研究已经历了1 0 多年的时间，无论是在系统理论、计算模型 的建立和应用系统的研制开发上，都已取得了很多成果，也建立了套较为完 善的粗糙集理论体系。下面我们对粗糙集理论进行简要介绍。 现实世界中的信息，通常可以用一个信息表来表示。信息表中的每一行称 为一个实例( 实体、对象) ，实例的性质是通过一些变量的赋值体现出来的。如 上一节所述，样例的属性集可以分为条件属性和结果属性( 决策，也称决策属 性) 。后面要介绍的不分明关系是粗糙集理论的一个关键概念，它通常是和一个 属性集合联系在一起的。 例如，在表2 2 中，属性思想，纪律和社会实践为条件属性；综合考评为决 策属性。 1 2 第2 章粗糙集理论 表2 2 决策表 编号条件属性决策 思想纪律社会实践综合考评 x 。一般 良好 很少 优 x 2一般一般很少差 x ，一般良好很少差 x 先进一般经常优 x s一般一般经常中 x ； 先进良好经常优 x 7 先进良好很少优 x 。 一般一般很少中 x 。 先进良好经常优 2 2 1 粗糙集的基本概念 定义2 2 ( 不i 叮分辨关系) 设信息系统s = ( u ，a ) ，集合c ，d a ，且cr 、d = ，且cud = a ，其中c 称为条件属性集，d 称为决策属性集，则d s = ( u ， a ，c ，d ) 为一个决策表。其中u 为论域，a 是一非空有限对象集，即 u _ x i ，x 2 ，) ( 。) ，a = a l ，a 2 ，a m ) 是非空有限的属性集合。b 彳定义b 在u 上的 不可分辨关系i b 为：，口= ( 石，y ) u x uv a b ，口( j ) = n ( y ) 。 定义2 3 ( 上、下近似)设s 为信息系统，x 为u 的非空子集，b c _ a 且b 。集合x 的b 下近似定义为：曰一( x ) = x u l x l 矗 ，其中m 。为基于不分明 关系i b 中包含对象x 的等价类；而集合x 的上近似定义为： b 一( x ) = i x u i 【工】占n 妒) 。 、 下近似n x ) 又称x 的b 正域，记为p o s b ( x ) ，表示肯定属于x 的对象所组 成的最大集合。上近似b 一时) 那些可能属于x 的对象组成的最大集合。 定义2 4 ( 约简) 设s = ( u ，a ) 为信息系统，曰s 彳且a b ，( 1 ) 如果i b = i b 。 ， 则称属性a 在b 中是冗余的，否则a 在b 中是必要的；( 2 ) 如果b 的所有属性是 必要的，则集合b 是独立的；( 3 ) 设b b ，如果b 7 是独立的，且i b = i b ，则b 是b 的一个约简。 定义2 5 ( 差别矩阵) 在s 中，u _ x l ，x 2 ，x n ) 为对象的结合，s 的差别矩 阵m ( s ) 为f 门矩阵，即m o = a ( x i ) a ( x j ) ( d d ，d ( x i ) d ( x i ) ) 其中i , j = l ，2 ，i l 。 根据定义可知m ( s ) 是一个对称矩阵。 。 定义2 6 ( 核) 属性集a 的核就是a 的所有约简的交集，记作：c o r e ( a ) = 1 - 1 r e d ( a ) 。 1 3 第2 章粗糙集理论 2 3 基于粗糙集的知识获取 2 3 1 决策规则 在基于粗糙集理论的知识获取研究中，主要是通过归纳学习和观察发现式 学习来得到知识的。归纳学习是通过对大量的实例进行推理归纳和对共性的分 析，抽象出一般的概念和规则，使这些新概念和新规则能蕴涵所有实例。一般 来说，决策表包含了某一领域中的大量数据记录，是领域的实例数据库。它记 录了大量实例的属性值和决策情况，是领域知识的载体。知识获取的目的就是 要通过分析这个实例库来得到该领域中有用的、规律性知识。我们通常采用决 策规则的形式记录下来，并可以在将来的决策过程中利用这些知识来对未知的 观察实例进行决策判定。下面我们给出决策规则的形式化描述。 定义2 7 定义公式如下【7 】 ( 1 ) ( a ，v ) ( 或写为a v ，a r ，v v a ，表示属性a 的取值为v ) 是原子公式；原 子公式是公式； ( 2 ) 如果a 和b 是公式，那么1a ，a 八b ，a v b ，a b 都是公式； ( 3 ) 只有按定义( 1 ) ( 2 ) 所组成的式子是公式。 定义2 8 公式a b 的逻辑含义称为决策规则，a 称为规则前件，b 称为 规则后件，它们表达一种因果关系。其中，公式a 中包含的原子公式中只有决 策表中的条件属性，b 中所包含的原子公式中只有决策表中的决策属性。 2 4 本章小结 1 9 8 2 年z p a w l a k 提出粗糙集理论，经过二十多年研究发展，粗糙集理论己 趋于成熟，并且越来越广泛地应用于现实生活。本章介绍粗糙集理论的基本概 念，包括知识表达，粗糙集理论中的最基本的概念如上、下近似，约简和决策 规则等内容。 1 4 第3 章时序信息系统获取方法的研究 第3 章时序信息系统获取方法的研究 3 1 引言 随着信息技术的不断发展，信息量变的越来越庞大，人们发现自己已不再 是缺少信息，而足被信息海洋所淹没。面对工业过程控制、医疗诊断、股票分 析、水文气象等很多领域内的数据，有一个共同的特点，即记录了某个领域的 时间序列信息。如何从海量时序数据中获取更多隐含的、先f ；i 未知的并具有潜 在价值的知识，即发现知识、提取规则是近期数据处理领域一个新兴的课题。 为此，国内外学者做了大量的研究工作。拳且糙集理论【1 3 。4 】提供了一套严格的数 学方法，对于具有噪声、不完全或者不精确的数据在无需任何附加信息的条件 下对其进行约简以及发现数据之间的依赖关系，是一种新型的处理不完整性和 不确定性问题的数学工具。时序数据由于采样、处理的过程中难免会存在噪声、 不完整或不精确数据。就概率沦、模糊集理论和粗糙集理论相对比较而言，概 率论中常需要前提假设，模糊集理论中则需要隶属函数假设，而粗糙集理论可 以直接处理。因此可以认为，基于粗糙集的时序数据挖掘策略与其他方法相比 具有其独特的优势。目前，基于粗糙集理论时序数据的研究取得了一定的成果 0 3 - 1 5 ：时序逻辑的框架使用事件变量来表示时态序列：用动态编程的方法来检测 时序模式；时序信息系统( t e m p o r a li n f o r m a t i o ns y s t e mt i s ) 与实时时序信息系统 ( r e a l t i m et e m p o r a li n f o r m a t i o ns y s t e m ，r t t i s ) 的概念的提出；时间序列转化为信 息系统的方法等。使得粗糙集处理时间序列成为可能，本文提出提出时间距离 的概念，阐述除了可以从原始离散数据表中采取选择提取的方法得到时序信息 表还可以从r t t i s 转换获得时序信息表并提出一种根据客户需求利用属性值变 化率得到t i s 的方法。 3 2 相关的基本概念 定义3 1 时序信息系统t i s 是一个三元组s t = u ，a u d ，t ) ，一 ，其中 u 是一个非空有限的对象集合，a 是描述事件状态的条件属性集合，d 是决策属 性，t 是时序属性，d 菇a ，t 舞a ，_ 是关于t 的线序关系， = ( x ，y ) - x ，y n n x y ) ， n