（计算机软件与理论专业论文）基于粗糙集理论的时间序列数据分析.pdf

摘要 在时间序列信息系统获取方法方面，以往的文献涉及很少，本文 研究了其获取方法，它是转换为非时序信息系统的基础。时序信息系 统可以从原始离散数据中获得，也可以从实时时序信息系统转换得 到。 对转换后非时间序列信息表的属性约简，是进行数据挖掘的基 础。基于差别矩阵的约简策略在众多约简策略中是最常用的，但是该 算法策略存在计算复杂度大，计算效率低的问题。针对这些问题，本 文提出一种改进算法，使该策略的计算复杂度和空间复杂度小于基于 差别矩阵的约简策略，并且能达到相同的约简效果。 本文还研究了一种基于条件熵的属性约简策略，该策略考虑时序 决策表转换得到的非时序决策表中属性隐含的时间特性，提出关于时 间重要性的假设，并将其运用到属性约简策略。 最后，对规则获取策略进行了研究。规则获取的一般方法在直接 获得最小规则集的存在不足，本文提出一个改进的规则获取算法，可 以直接获取最小规则集。 本文使用笔者编写的模拟程序对u a 数据库集中与时序有关的 一个数据库进行实验仿真，对其进行了属性约简及规则获取，有效地 验证上述算法。 关键词：时间序列，粗糙集，数据挖掘，属性约简，规则获取 a b s t r a c t t h i st h e s i sd i s c u s s e st h em e m o do fo b t a i n i n gt i m es e r i e sm f o m a t i o n s y s t e m ，w h i c hi st i l eb a s eo fc o n v e r t i n gi n t on o n t i m es e r i e sm f o m a t i o n s y s t e m h o w e v e r ，f e wl i t e r a t u r e si n v 0 1 v et h em e t h o do fo b t a i n i n gt i m e s e d e si n f o m a t i o ns y s t e mf o 肌e r ly w ec a nw i nt i m es e r i e si n f o h l l a t i o n s y s t e m 丘o mb o t l l o r i g i l l d 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 s i n f o m a t i o ns y s t e m t h e a s p e c to f n o n t i m es e r i e si i l f o m a t i o ns y s t e mr e d u c i n ga t t r i b u t e s i sak e yp m c e s sb e f o r ed a t am i n i n g t h es 打a t e g yo fr e d u c i n g 砌b u t e b a s e do nd i s c e m a b l em a t r i xi s u s u a l l yu s e d 砌o n gm a n ym e t h o d s h o w e v e r i th a ss o m ei n s u m c i e n c i e s i n c l u d i n gh i g hc o m p u t i n g c o m p l e x i 妙a n dl o wc o m p u t i l l ge 瓶c i e n c ya i ma t t 1 a td i 币c u l t y ，m e t h e s i sp r o v i d e sa ni l p r o v e dm e t h o du n d e rm ei l l u m i n a t i o no fs o m e e x 锄p l e s ，w h i c ht i m ec o m p l e ) 【i 够a 1 1 ds p a c ec o m p l e x i t yi s l e s sm a nm a t b a s e do nd i s c e m a b l em a t r i xa n dh a st h es 锄ee f 王色c t t h i sd i s s e r t a t i o na l s or e s e a r c h e so nas 心a t e g yo fr e d u c 证ga t t r i b u t e b a s e du p o nc o n d i t i o n a li l l f o m a t i o ne n t m p y ，w h i c ht a k e sac o m l o t a t i v e c h a r a c t e r i s t i co ft i m ei na 州b u t eo fn o n t i m ed e c i s i o nt 山l ec o n v e r 七e d f 而mt i m ed e c i s i o nt a b l e t h i sd i s s e n a t i o np u t su pw i n lat e n t a t i v ea b o u t t i m es i g n f i c a l l c e ，w h i c hi su s e di n t om ea b o v es t r a t e 黟 f i n a l l y ， w eh a v eas t u d yo nm ea c q u i s i t i o no fm l e s b e f o r e p r o v i d i l l ga ni m p m v e ds t r a t e g yo n1 1 l 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 n o fe x a m p l e s ，w ea n a l y z ead r a w b a c ko ft m d i t i o n a lo n eo ng a i n i n g m i n i m a lm l e ss e td i r e c t l y t h ei m p r o v e ds t r a t e g yc a no b t a i nm i n i m a l m l e ss e td i r e c t l y u s i n gad a t a b a s er e l a t e dw i t ht i m es e r i e si nt h eu c id a t a b a s es e t s a n das i m u l a t e dp r o g m mc o m p i l e db ya u t h o r ，w ev a l i d a t et h ee f r e c to f t l l e a b o v es t m t e g i e s t h ep r o g r a n lc a nr e d u c ea t t r i b u t e sa n do b t a i nm l e sf o m “m es e r i e sd a t a k e yw 0 r d st i m es e r i e s ，r o u 曲s e t ，d a t am i n i n g ，a t t r i b u t e sr e d u c t ， r u l e sa c q u i s i t i o n 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得中南大学或其他单位的学位或证书而使用过的材料。与我共 同工作的同志对本研究所作的贡献均已在在论文中作了明确的说明。 作者签名：虚墼日期：丛年月三日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位 论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论 文；学校可根据国家或湖南省有关部门规定送交学位论文。 作者签名：趣导师签名：玉塑哩珥日期：丛年上月旦日 硕士学位论文 第一章绪论 1 1 研究背景 第一章绪论 随着计算机的普及，大容量存储技术的发展已经条形码等数据获取技术的广 泛应用，人们在日常事务处理和科学研究中积累了大量的各种类型的数据。在人 们所保存的数据中，有许多是“时间序列”( t i m es e r i e s ) 数据。所谓时间序列 是指按时间顺序排列的观测值的集合。按照研究的现象或问题的不同，可以得 到各种时间序列。例如股票分析员观察某个股票价格指数的波动，气象学家研究 某地区的气温与降雨量的变化，水文专家研究某流域水位与降雨量的变化关系 等，都会观测到按某种度量单位测量的一系列数据，其自然顺序就是按出现的时 间先后排列而得到的时间序列。自然界以及社会生活中的各种事物都是在运动、 变化和发展着的。事物之间也是相互影响、相互作用的，一个事物的运动、变化 和发展要受到其它事物的影响和制约，同时，它的发展变化也影响和制约着其它 事物。通过对记录各个事物运动、变化、发展的时间序列数据的分析研究，可以 揭示事物发展变化的内部规律，以及不同事物之间的相互作用关系，这对于人们 正确认识事物并以此为据做出科学的决策具有重要的现实意义。 这些数据不仅是对历史事件的记录，其背后还蕴含着许多重要的信息，这些 信息在决策生成过程中具有重要的参考价值。因此如何充分、有效地利用这些历 史数据就成为目前人们关注的重要问题。数据挖掘是近几年发展起来的一个新兴 的研究领域，它利用统计、机器学习、神经网络、数据库、网络通信等各学科领 域的先进技术对大量历史数据进行分析处理，从中提取出隐含的、事先未知的、 和有价值的知识，为人们的决策提供更高层次的技术支持。 人们采用数据挖掘技术对这些时间序列数据进行分析目的就是为了能获得 隐含的规则来提供决策。然而，这些数据本身有可能是不精确的、不完整的，这 就需要一种对于处理这种特点的数据比较有效的工具。粗糙集理论是一种处理模 糊性和不确定性的新型数学工具，能有效地处理不精确、不一致、不完整的信息， 并从中发现隐含的知识，揭示潜在的规律。粗糙集是数据挖掘的方法之一。粗糙 集由z p 盯w 肠七于1 9 8 2 年提出，是继概率论、模糊集理论、证据理论之后的又 一个处理不确定性的数学工具。该理论不需要任何附加的信息或先验知识，就能 有效地分析和处理不精确、不完整和不一致的数据，并从中发现隐含的知识，揭 示潜在的规律。粗糙集理论已经在很多领域如数据挖掘、机器学习、模式识别、 决策分析等取得了成功的应用。 硕士学位论文第一章绪论 将基于粗糙集理论的数据挖掘的思想和方法引入时间序列分析，从时间序列 中探索性地获取各种有价值的模式或规则是目前数据挖掘研究领域的一个新热 点。同时，对于分析时序数据是一个非常有效的工具。一方面，粗糙集理论可以 在不影响数据所表达的信息下使原来的数据大为减少( 数据浓缩) ；另一方面， 粗糙集理论可以产生决策规则，从而可以挖掘数据中的有效模式。 1 2 研究内容 本文的研究内容是如何使用粗糙集工具对时间序列数据进行数据挖掘，提取 有用的规则供人们决策。它的处理过程是对时间序列数据进行转换，将其变为非 时间序列数据，形式为非时序信息表或决策表，再采用基于粗糙集的方法对该表 进行属性约简，然后对约简后的属性集提取规则集。 首先，时间序列信息系统获取问题是转换为非时序信息系统的基础。通常的 时间序列数据，是人们在生产生活中通过采样得到，因为采用事先设定的抽样频 率，因此它们本身能够真实的反映出原始时间序列曲线，然而对于生成时序信息 表或决策表，在绝大多数情况下这些时序数据都存在冗余，因此如何从大量的原 始数据中提取满足条件的数据构成时序信息表或决策表是我们所要研究的内容 之一。至于将时序信息表转换为非时序信息表的问题，已有学者提出了较好的转 换算法，因此不在本文的研究范围内。 其次，对转换后的非时间序列信息表进行属性约简问题，它是进行数据挖掘 的关键步骤，本文重点研究属性约简问题。属性约简方法目前有很多，有基于属 性重要性的约简、基于差别矩阵的约简、基于遗传算法的约简、动态约简等。其 中基于差别矩阵的约简策略在众多的约简策略中是最常用的，该策略是在代数定 义下的，但是该算法策略存在计算复杂度大，计算效率低的问题。在本文中，针 对这些问题，在引例的启发下，提出一种改进算法，巧妙地把属性值个数应用到 属性约简上，使该策略的计算复杂度和空间复杂度小于基于差别矩阵的约简策 略，并且能达到基于差别矩阵的约简效果。基于属性重要性的约简包括代数定义 下的和信息定义下的，代数定义下的基于属性重要性的约简已经有众多学者进行 了研究，相比之下，信息定义下的基于属性重要性的约简研究较新。由于时序决 策表转换得到的非时序决策表属性仍然隐含着时间特性，为此，需要一种考虑时 间特性的属性约简策略。本文提出关于时间重要性的假设，并将其运用到基于条 件熵的属性约简策略，并在最后使用仿真算例验证该算法。 再次，数据挖掘的最后一个步骤是提取规则。本文首先分析了传统的规则获 取策略在获得最小规则集方面的不足，在所有可能的规则集中祛除冗余规则被认 为是很困难的。因此，在引例的启发下，提出一种可以直接获取最小规则集改进 硕士学位论文 第一章绪论 的规则获取策略，该策略存在两层规则获取机制，在得到所有单属性规则集的基 础上再进一步获取多属性规则集，最后用算例说明该改进策略的规则获取机制。 最后，本文采用自己编写的模拟程序对吲数据库集中与时序相关的数据 库进行仿真实验，对其进行时序转换、属性约简并获取规则。 1 3 研究意义 随着当今数据采集和存储技术的不断发展，数据库中存储的数据量急剧增 加，数据库的规模也因此变得越来越庞大。人们发现自己已不再是缺少信息，而 是被信息海洋所淹没。如何分析数据并从中挖掘出有用的知识是一项既费时又难 于进行的工作。通常，对于特定领域的数据挖掘需要有一定的背景领域知识，并 在此基础上采用某种有效工具从数据集中获取更多的隐含的、先前未知的并具有 潜在价值的知识。这种挖掘在工业过程控制、医疗诊断、股票分析、水文气象等 领域尤显重要，因为这些领域的数据有一个共同的特点，即它们都记录了某个领 域的时问序列信息，且信息量特别巨大，如果没有合适的挖掘手段则势必给以后 的决策和新数据的预测带来困难。信息系统中时间序列数据的出现使得有必要针 对这一特殊数据类型的挖掘给出相应的策略，以便发现在某段时间内连续记录的 某属性序列值的变化规律，以及它的变化给其它属性值所带来的影响。近些年来， 随着粗糙集理论的研究深入，它已被广泛地应用于数据库中的知识发现、智能控 制、机器学习、决策分析、专家系统以及模式识别等众多领域。 理论意义：通过对时间序列数据的研究，运用粗糙集工具对其进行属性约简， 从中获得人们感兴趣的规则集。文中的时序数据获取方法、基于差别矩阵的属性 约简的改进策略、一种考虑时间特性的基于条件熵的属性约简策略和改进的规则 获取算法和是对时间序列数据分析研究的一个补充。 现实意义：将上述方法运用到时间序列数据的实际工程领域，包括股票、电 力、水文、医疗等，为这些工程领域的信息处理提供一个有效的方法，以便人们 获取规则、发现知识，提高和改进工作效率。 1 4 论文的结构安排 本文的后续章节结构安排如下： 第二章介绍了时间序列数据、粗糙集、数据挖掘各自的概念及研究现状， 为后续章节的研究进行一些必要的铺垫。 第三章研究了时间序列信息系统的获取方法，可以从原始离散数据及实时 时间序列信息系统中获得；同时介绍了时间序列信息系统转换为信息系统的方 硕士学位论文第一章绪论 法。 第四章对属性约简策略进行了改进研究。首先分析了基于差别矩阵的属性 约简方法在运行效率方面的不足，并提出了对此方法的改进策略，使该策略的时 间复杂度和空间复杂度小于基于差别矩阵的约简策略，但同样能达到约简效果。 然后研究了考虑时间特性的基于条件熵的属性约简策略，针对转换后的非时序决 策表中的属性仍然隐含着时间特性，提出时间重要性的假设，并将其应用到属性 约简策略。 第五章对规则获取策略进行了改进研究。分析了传统的规则获取算法在生 成最小规则集方面的不足，在引例的启发下，提出一种直接获得最小规则集的改 进的规则获取策略，并使用u c ，数据库集中与时序相关的数据库进行仿真实验 予以验证。 第六章对本文所做的工作进行总结，同时对下一步的研究工作进行一些展 望。 硕士学位论文第二章时间序列、粗糙集及数据挖掘概述 第二章时间序列、粗糙集及数据挖掘概述 2 1 时间序列概述 2 1 1 时间序列概念 自然界以及社会生活的各种事物都在运动、变化和发展，将它们按时间顺序 记录下来，可以得到各种各样的时间序列。对时间序列进行分析，可以揭示事物 运动、变化和发展的内在规律，对于人们正确认识事物并据此做出科学的决策具 有重要的现实意义。 从经济到工程技术，从天文到地理和气象，几乎在各种领域都可以遇到时间 序列，在科技高速发展的今天，越来越多的时间序列信息被存储在计算机上，如 证券公司的计算机积累了大量的股票信息，商场的j p o s 系统收集了大量的销售 信息，工厂的监控系统保存了大量的工业参数的历史数据，这些数据中包含了很 多有用的信息，对时序数据进行分析具有很重要的价值。例如，对股票信息进行 分析，可以用来预测股票的走势；对商品销售信息进行分析，预测商品销售的趋 势，可以用来决策商品的进货、价格等，从而获得最大利润：对工业参数的历史 数据进行分析，发现参数问变化的内在联系，可以更好地对工业对象进行控制。 在4 “，口，等人的文章【“】中，时间序列被定义为“a nd r 如rs “旭口，“e ”。 它是指一类有序的，复杂的对象的集合，时间序列数据主要是通过一系列的方法， 从大量的时序数据中发现特定的规律和有价值的知识。如“相似性搜索”，“模式 发现”，“趋势预测”等。 时间序列首先要解决的问题是时序数据的形式化表示，目前的方法有：事件 表示和状态表示，前者的信息由某个时间点或时间区间所发生的事件来体现，后 者的信息主要由状态的变化来记录，如图2 1 所示。本文是基于事件表示。 图2 一l事件状态表示示意图 - 5 - 硕士学位论文 第二章时间序列、粗糙集及数据挖掘概述 2 1 2 时间序列的研究现状 目前对时间序列的研究工作主要集中在时间序列的数据压缩、趋势分析、相 似性搜索、周期分析、序列模式发现这几个方面。其中对时序数据的趋势分析和 相似性挖掘已有很多不同的方法，但大多基于数学计算，有彳日w d ，等人提出的 基于频谱分析和r 索引树的数学分析方法，上f 等人提出的基于相关统计分析的 数据计算方法，和q “加砌 j 0 ，f 哪d m 等提出的局部线性回归方法 5 】，以及各 类针对具体应用的特殊处理方法，但多集中于单维时间序列。下面介绍这几个方 面的研究所涉及的一些问题或采用的方法。 ( 1 ) 时间序列的数据压缩 将时问序列数据转化为趋势标志数据，数据量将大大的减少。其方法具体描 述如下【6 j 首先计算一个时间序列的两组不同时间长度的移动平均( 聊d v f n g 硎f 懈p ) ，一组长期的，一组短期的；其次根据具体的需要定义若干趋势标志 值( 如1 表示上升，0 表示保持，1 表示下降等) ；最后通过比较这两个移动平 均序列和原序列得出需要的趋势序列，数据量得到了压缩，而且该趋势序列继承 了原时间序列的移动特征。 ( 2 ) 时间序列趋势分析 采用移动平均对时间序列进行趋势分析是一个常用的方法，移动平均可以降 低数据集中的变化总量【】。因此用移动平均代替原时间序列可以减少不希望出 现的波动。移动平均会丢失原序列中的头或尾数据，由此有时会生成在原数据中 不会出现的循环或其他变化趋势；并且它可能受到一些极端数据的影响，可通过 适当权重的加权移动平均方法来降低其负面影响。另外采用适当阶数加权移动平 均可以消除数据中的循环、季节性和非规则的模式，只保留趋势变化【8 1 。 其他计算趋势的方法包括：徒手法【8 】( 加e 一 dm e 廊d 回，它是基于用户的判 断画根近似曲线或直线去拟合一组数据，这种方法的代价太大，而且只有当数 据规模较大时，挖掘结果才可靠。另一种方法是最小二乘法，将其中最好的拟合 曲线作为最小二乘曲线，即使曲线具有平方和误差。 ( 3 1 相似性搜索 在金融市场的分析( 股票数据分析) 、医疗诊断分析( 心电图分析) 、科学与 工程数据库分析( 能量消耗分析) 等方面，时间序列的相似性搜索有很大的应用 价值。对时间序列的相似性搜索分为：在一序列中寻找与样本序列( 根据领 域知识预先定义好) 相似的予序列；在同一序列中寻找相互间相似的子序列； 在若干序列间寻找相似序列。对应的三种方法简单介绍如下。 首先根据领域知识选择股票中频繁出现或有意义的样本子序列；其次用 硕士学位论文 第二章时间序列、粗糙集及数据挖掘概述 斜率序列( 采用拟合) 来表示样本子序列：对一个时间序列进行与样本子序列的 匹配，得到一个标注样本子序列的序列；最后对得到的标注序列进行模式的关联 性挖掘，得到样本子序列间的关联规则 9 1 。这一方法的不足是需要很强的领域知 识来预先定义样本序列，而样本子序列的定义对挖掘结果也产生决定性的影响。 首先将一个时间序列分为h 段子序列，每段包含f 条线段( 即什1 个数据 点) ；其次对每个子序列内部进行线段拟合；对拟合后具有相同数目数据点的子 序列按一定的度量公式计算其偏离值f ，当f 小于预定值时，则这两个子序列相 似。 在上述数据压缩方法中得到若干时间序列所对应的各自的趋势序列后， 对趋势序列进行编码( 每个趋势标志值用若干二进制位编码表示) ，然后通过位操 作( 移位、补零等) 进行趋势序列间的相似匹配搜索。在这里若寻找到两个时间序 列相似，且其一领先，则我们可预测落后时间序列的下一个趋势值【6 j i ”。 ( 4 ) 周期分析 周期分析是指对周期性模式的挖掘，即在时间序列数据库中找出重复出现的 模式。周期模式可以应用于许多重要的领域，如季节、潮汐、行星轨迹、每日能 量消耗、每天交通模式等。在同一序列中寻找相似子序列完毕后，可以判断这些 相似子序列的出现是否存在周期性l l 。 除了子序列的周期性，还有异类关联规则的周期性，这在得出序列间关联规 则然后判断规则产生的周期性。 ( 5 1 序列模式发现 序列模式是指挖掘相对于时间或其他模式来说出现频率较高的模式。例如， 一个月前烫发的人很有可能在一个星期内染发。在针对目标市场、客户吸引、气 象预报等分析中序列模式挖掘非常有前途。序列模式的挖掘大多采用了却r f o 一 算法及其变种来寻找频繁模式。在文献 1 1 中王振宇等提出了在关系型数据库中 基于时间窗口的序列模式挖掘方法，以时间窗口形为尺度将整个多属性时间序 列分成相邻前后重叠的子序列，然后寻找在所有子序列中频繁出现的模式( 数据 项之间存在一定的顺序) ，即序列模式。这种方法的不足之处在于：在时间窗口 长度的选择上需要很强的领域知识；且查找频繁序列的工作量很大。 2 2 粗糙集理论概述 2 2 1 粗糙集理论的产生和发展 长期以来，许多的科学家就致力于研究含糊概念。1 9 6 5 年，三爿历出矗提 硕士学位论文第二章时间序列、粗糙集及数据挖掘概述 出了模糊集概念，以说明现实中的含糊现象。许多的科学家试图通过这个理论解 释含糊概念。但是，模糊集无法对含糊的多少进行计算，模糊集中的隶属函数是 无法用数学公式计算的。j p a w 肠女教授提出了粗糙集，把那些无法确认的个体都 归属于边界线区域。由于它有确切的数学公式进行描述，所以含糊度是可以计算 的。下面是粗糙集理论的产生和发展过程中具有重要历史意义的事件： 1 9 8 2 年，p 口w 肠女教授提出了粗糙集理论，为人们研究模糊和不确定性知识 提供了一种新的数学工具。 1 9 9 1 年，m w 肠t 教授出版了第一本关于粗糙集的专著。 1 9 9 2 年，在波兰船e 幻口召开了第一届国际粗糙集学术讨论会，主要讨论了 集合近似定义的基本思想及其应用。 国内有关粗糙集的研究起步较晚，但近几年发展速度很快，取得了一定的研 究成果。 2 0 0 1 年，在重庆召开了第一届中国月d 础集与软计算学术研讨会。 2 0 0 3 年，成立了中国人工智能学会粗糙集与软计算专业委员会，月。础集 的研究队伍也更加壮大，研究成果在深度和广度上有了更大的发展。 当前许多重要的国际学术会议都把粗糙集理论的研究列入主要内容之一。 2 2 2 粗糙集理论的基本概念 粗糙集理论是一种新的处理模糊和不确定性知识的数学工具。其主要思想就 是在保持分类和决策能力不变的前提下，通过知识约简，导出问题的决策或分类 规则。目前，粗糙集理论己被成功地应用于机器学习、决策分析、过程控制、模 式识别与数据挖掘等领域。下面介绍粗糙集的相关理论，这些作为后续工作的理 论基础i ”o ”。 定义2 1信息表知识表达系统的基本成分是研究对象的集合，关于这些对 象的知识是通过指定对象的属性( 特征) 和它们的属性值( 特征值) 来描述的。 一般地，一个信息表知识表达系统s 可以表示为s = ，其中，u 是对 象的集合，也称为论域，爿= c u d 是属性集合，子集c 和d 分别称为条件属性 集和结果属性集，矿= ij 一是属性值的集合，巧表示属性，彳的属性值范围， r e 即属性，的值域， 【，x 4 jp ，是一个信息函数，它指定u 中每一个对象x 的属 性值。 定义2 2 对于每个属性子集曰彳，一个不可分辨二元关系( 不分明关系) i n d ( b ) 定义为i n d ( b ) = ( x ，y ) ( x y ) 廿? 、b b ( b ( x ) = b ( y ) ) j ，显然i n d ( b ) 是一 个等价关系，且肋何一n ，d ( 6 ) ) 。在不引起歧义的情况下，通常将z d 何) 硕士学位论文第二章时间序列、粗糙集及数据挖掘概述 简写为b 。 定义2 _ 3 给定知识表达系统s = ，对于每个子集x u 和不分明 关系b ，的上近似集和下近似集分别可由b 的基本集定义如下： 口矽= u ，k i ry f 硼上d 征p ny f 。矽，b ( 矽= u 厂一i r e 硼肋f 圳n x 矿，v 。其中， 叻w d 何j _ 硼u nv x v y v 6 p 俐= 6 以砂是不可分明关系b 对u 的划分，也 是论域u 的b 基本集的集合。 定义2 4集合b p p = 口p 9 b p 9 称为的b 边界；j d d 岛矽= b 矽称为x 的b 正域：e g b 矽= 己八口p 9 称为的b 负域。丑p p 是根据知识b ( 属性子集功， 【，中所有一定能归入集合j 的元素构成的集合，即所有包含于x 的基本集一的 并。b 。p p 是根据知识b ，u 中所有一定能和可能能归入集合x 的元素构成的集合， 即所有与z 的交不为空的集的基本集e 的并。删口p p 是根据知识曰，u 中既不能 肯定归入集合z 有不能肯定归入集合x 的元素构成的集合。正域p a 是根 据知识b ，u 中所有一定能归入集合x 的元素构成的集合。负域e g b 是根据 知识曰，( ，中所有不能确定一定归入集合的元素的集合。b 口p 是某种意义上 的论域的不确定域。如图2 2 所示i 】6 】。 图2 2 粗糙集概念示意图 定义2 5 设u 为一个论域，p 和q 为定义在u 上的两个等价关系簇，q 的 j d 正域记为p o 昂r f 2 j ，定义为p f 9 = 【j 只( x ) 。 * e 孑坦 定义2 6 设u 为一个论域，p 和q 为定义在u 上的两个等价关系簇，若 p o 娜f f 2 j = p o 跏1 删n q j ，则称r 为p 中相对于q 可省略的( 不必要的) ，简称p 中 q 可省略的；否则，称，为j d 中相对于q 不可省略的( 必要的) 。 定义2 7 设u 为一个论域，p 和p 为定义在u 上的两个等价关系簇，若p 中的每一r 都是p 中q 不可省略的，则称p 为( 相对于) q 独立的。 定义2 8 设u 为一个论域，p 和p 为定义在u 上的两个等价关系簇，若p 的q 独立子集s c j d 有p 呱n = p o 跏f 9 ，则称s 为p 的q 约简。 硕士学位论文 第二章时间序列、粗糙集及数据挖掘概述 定义2 9 个决策表是一个信息表知识表达系统s = ，彳= c u d 是属性集合，子集c 和d 分别称为条件属性和决策属性集，d 西。 定义2 1 0 差别矩阵是由波兰华沙大学数学家s 勋w m n 提出，其定义为：令 s = 似是一个信息系统，u 为论域且l ，- b ，x 孙x 4 是条件属性集合，d 是决策属性，日俐是记录x 在属性日上的值，差别矩阵可表示为： f n a ：n 扛a n ( x 1d 缸a 幸d ( x ( c o ) 2 od = d 矧产，2 ，n 、- 1 口扫口= 日和d b j d 从上式可以看出，当决策属性不同且条件属性也不完全相同时，元素值为互 不相同的属性组合；当决策属性相同时，元素值为o ；当决策属性不同而条件属 性完全相同时，元素值为一1 ，该情况表明数据有误或提供条件属性不足。 定义2 1 1 设集合簇f = 隅，场列是论域u 上定义的知识，e ，_ l j ，b 是一个属性子集，定义曰对f 近似分类的质量y 日 为，b = 1 b 一( 置) i i u i 。 扫i y 日倒是应用知识b 对对象进行分类时，能够确定决策的对象在论域中所占的比 例。 定义2 1 2 对于f 是属性集d 导出的分类，属性子集b 在属性集b 中的重 要性( f b ，如果属性集b 是默认的，如b 为条件属性全集，则可简称为属性 子集的重要性) 定义为y b 口一y b 值r 刃。这表示当从属性集曰中去掉属性子集f 对f 近似分类的质量的影响。属性的重要性还可以有其他度量方法，如属性子 集f 的重要性也可以定义为户o 口- 移p 蚴伊，其中p o 嗨矽= u p 吣。( ) 。 2 2 3 粗糙集理论的研究现状 目前，粗糙集理论已经成为人工智能研究领域中的一个学术热点。国际上成 立了粗糙集学术研究会。也出现了一些应用粗糙集的系统和商业化的软件。如 r e g i n o 大学利用粗糙集理论开发的知识发现系统碰) d r ，已经成功地应用于医 疗诊断和电信业等领域。美国肠船口s 大学开发的三e r 研z p 口r ”以g o 埘b m p ，盯 6 口s e d 册r d 职 & 叫系统，应用于医疗诊断、社区规划和全球气象研究等方向。 粗糙集理论在很多方面取得了比较大的成功。粗糙集理论从诞生到现在只有二十 年左右的时间，但是已经应用于机器学习、模式识别、知识发现、决策分析和过 硕士学位论文 第二章时间序列、粗糙集及数据挖掘概述 程控制等方面的领域。 目前对粗糙集的研究主要在以下两个方面。 ( 1 ) 粗糙集理论的理论方面的研究 粗糙集的数学性质方面的研究【”】：主要是粗糙集的代数结构和拓扑结构等 方面的研究。 粗糙逻辑与推理【”】；近似真的概念很早就引起哲学家和逻辑学家的注意， 而近年来主要是被从事人工智能的研究者所关注。粗糙逻辑有五个逻辑植，即真、 假、粗糙真、粗糙假和粗糙不相容。 粗糙集的扩展模型方面的研究1 7 】：主要有变精度粗糙集模型、概率粗糙集 模型、模糊粗糙集模型和基于随机集的粗糙集模型。 高效率的约简算法的研究1 8 喇】：找出信息系统所有的约简或最优约简是一 个 垆问题，于是目前主要集中在约简的启发式算法、并行算法、导出规则的增 量式算法等方面。 粗糙集理论和其他方法的结合：粗糙集与模糊集理论的结合【2 5 】；还有与神 经网络的结合 。 ( 2 ) 粗糙集理论的应用方面的研究 数据挖掘【2 7 】：粗糙集理论是一种比较有效的数据挖掘方法，现己成为数据 挖掘的一种重要方法。 模式识别【2 8 】：粗糙集理论可用在模式识别的特征选取中，以选择那些确实 能表征该模式的特征项。 医疗诊断口9 】：粗糙集方法根据以往的病例归纳出是否得病的决策规则，并 用这些决策规则来诊断新的病例。 决策分析1 7 】：利用信息系统( 决策表) ，粗糙集理论可以获得决策规则。 图象处理p u j 。 在今后几年内，粗糙集知识发现将有以下几个可能的研究方向【”j 。 基于粗糙集理论的粗糙逻辑以及不精确推理的研究。该项研究不仅对于知识 的挖掘和表示，而且对于人工智能中的不确定性推理将发挥重要作用。 快速、高效的约简算法。约简算法是粗糙集知识发现的基础，目前还没有一 种十分有效的约简算法。 粗糙集耽6 知识发现问题。随着知胞m 甜的迅速扩展，耽6 页面的增加，利 用粗糙集进行耽6 知识发现将是今后最重要的课题之一。 与模糊集方法等其他方法的结合问题。目前有很多知识发现方法，粗糙集如 何与其他方法结合，可能是提高知识发现效率的一种途径。 硕士学位论文 第二章时间序列、粗糙集及数据挖掘概述 2 3 数据挖掘概述 2 3 1 数据挖掘概念 ( 1 ) 技术角度的定义 数据挖掘( d 口细 卉h 啦g ) 就是从大量的、不完全的、有噪声的、模糊的、 随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有 用的信息和知识的过程。 与数据挖掘相近的同义词有数据融合、数据分析和决策支持等。这个定义包 括好几层含义：数据源必须是真实的、大量的、含噪声的；发现的是用户感兴趣 的知识：发现的知识可接受、可理解、可运用；并不要求发现放之四海皆准的知 识，仅支持特定的发现问题。 ( 2 ) 商业角度的定义 数据挖掘是一种新的商业信息处理技术，其主要特点是对商业数据库中的大 量业务数据进行抽取、转换、分析和其他模型化处理，从中提取辅助商业决策的 关键性数据。 数据挖掘可以描述为：按企业既定业务目标，对大量的企业数据进行探索和 分析，揭示隐藏的、未知的或验证已知的规律性，并进一步将其模型化的先进有 效的方法。 总之，数据挖掘涉及多学科技术的集成，包括数据库或数据仓库技术、统计 学、机器学习、模式识别、数据可视化、信息检索、图象与信号处理和空间数据 分析例。 2 3 2 数据挖掘的研究现状 目前，数据挖掘技术发展得十分迅速，国内的科研机构也十分重视这一方面 的研究，但与国外相比，国内对数据挖掘的研究稍晚，没有形成整体力量。1 9 9 3 年 国家自然科学基金首次支持对该领域的研究项目。紧接着，许多科研单位和高等 院校竞相开展知识发现的基础理论及其应用研究，这些单位包括清华大学、中科 院计算技术研究所、空军第三研究所、海军装备论证中心等。其中，北京系统工 程研究所对模糊方法在知识发现中的应用进行了较深入的研究，北京大学也在开 展对数据立方体代数的研究，华中科技大学、复旦大学、浙江大学、中国科技大 学、中科院数学研究所、吉林大学等单位开展了对关联规则开采算法的优化和改 造；南京大学、四川联合大学和上海交通大学等单位探讨、研究了非结构化数据 的知识发现以及耽6 数据挖掘。到目前为止，已有更多的大学投入至数据挖掘 硕士学位论文第二章时间序列、粗糙集及数据挖掘概述 的研究中来。 数据挖掘作为一门具有广泛应用价值的新兴学科，在许多领域都有很好的应 用前景。针对每个特定领域的应用，就应该将数据分析技术与特定的领域知识结 合起来，才能提供最为有效的数据挖掘方案。 ( 1 ) 生物医学 在过去的十年里，生物医学研究有了迅猛的发展，从新药物的开发和癌症治 疗的突破，到人类基因的识别与研究。基因研究的一个重要关注点是删序列 的研究，因为这种序列构成了所有活的生物体基因代码的基础。 目前生物医学的大量研究都集中在驯w 数据的分析上，从繁杂冗长的基因 序列中找出导致各种疾病的特定基因序列模式是一个很具挑战性的问题。而在数 据挖掘中已经存在的许多有意义的序列模式分析和相似性检索技术，因此数据挖 掘己成为删爿分析的强有力工具【s j o ( 2 ) 金融行业 金融事务需要搜集和处理大量数据，对这些数据进行分析，发现其数据模式 及特征，然后可能发现某个客户、消费群体或组织的金融和商业兴趣，并可观察 金融市场的变化趋势。 在银行和金融机构产生的金融数据通常比较完整、可靠和高质量，这大大的 方便了系统化的数据分析和数据挖掘，所以数据挖掘在金融行业的应用已比较普 遍。主要包括：贷款偿还预测和客户信用政策分析，对目标市场客户的分类和聚 类，对金融犯罪的侦破等【8 】o f 3 ) 零售行业 零售业是数据挖掘的主要应用领域，这是因为零售业积累了大量的销售数 据，顾客购买历史记录，货物进出，消费与服务记录，尤其如今电子商务和条形 码的运用等。它的应用主要包括以下方面：促销活动的有效性分析，顾客的购买 模式分析，商品间的关联度分析，顾客的忠诚度分析等弘】。 零售业数据挖掘有助于识别顾客购买行为，发现顾客购买模式和趋势，改进 服务质量，取得更好的顾客保持力和满意程度，提高货品销量比例，实现更好的 货品运输与分销策略，减少商业成本等。 ( 4 ) 电信行业 电信业已经迅速地从单纯的提供市话和长话服务转变为提供综合电信服务， 如语音、传真、寻呼、移动电话、图象、电子邮件、计算机和耽6 数据传输以 及其他数据通信服务。电信、计算机网络、因特网和各种其他方式的通信融合是 目前的大势所趋，而且随着许多国家对电信业的开发以及新兴计算与通信技术的 发展，电信市场正在迅速扩展并越发竞争激烈。 硕士学位论文第二章时间序列、粗糙集及数据挖掘概述 数据挖掘在电信业的应用主要包括：对电信数据本身的多维分析有助于识别 和比较数据通信情况、系统负载、资源利用等，盗用模式的发现，电信服务业中 客户的使用模式分析。 2 4 本章小结 本章全面地介绍了时间序列、粗糙集理论以及数据挖掘的相关概念及国内外 研究现状。时间序列数据是现实中广泛存在，并与人们的生活密切相关的。广大 学者一直在从事时间序列数据各方面的研究工作，并取得很多进展。1 9 8 2 年 m 肠提出粗糙集理论，经过二十多年研究发展，对于不精确和不确定方面的 问题处理已趋于成熟，并且越来越广泛地应用于现实生活。数据挖掘是从大量的 不完全的实际数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用 的信息和知识的过程。它在实际中的应用已日趋广泛，并且目前已有比较成型的 系统。数据分析是数据挖掘的近义词。本文研究的目的主要是用粗糙集工具对时 序数据进行数据挖掘，形成规则，预测趋势。 硕士学位论文第三章时序信息系统获取方法研究 3 1 引言 第三章时序信息系统获取方法研究 随着信息技术的不断发展，信息量变的越来越庞大，人们发现自己已不再 是缺少信息，而是被信息海洋所淹没。面对工业过程控制、医疗诊断、股票分析、 水文气象等很多领域内的数据，有一个共同的特点，即记录了某个领域的时间序 列信息。如何从海量时序数据中获取更多隐含的、先前未知的并具有潜在价值的 知识，即发现知识、提取规则是近期数据处理领域一个新兴的课题。为此，国内 外学者做了大量的研究工作。 波兰数学家zp w 肠t 于8 0 年代初提出的粗糙集理论提供了一套严格的数学 方法，对于具有噪声、不完全或者不精确的数据在无需任何附加信息的条件下对 其进行约简以及发现数据之间的依赖关系，是一种新型的处理不完整性和不确定 性问题的数学工具。时序数据由于采样、处理的过程中难免会存在噪声、不完整 或不精确数据。概率论、模糊集理论和粗糙集理论相对而言，概率论中常需要前 提假设，模糊集理论中则需要隶属函数假设，而粗糙集理论可以直接处理。因此 可以认为，基于粗糙集的时序数据挖掘策略与其他方法相比具有其独特的优势。 目前，基于粗糙集理论时序数据的研究取得了一定的成果。文献【3 2 提出了 实时时序逻辑的框架使用事件变量来表示时态序列，文献 3 3 】使用动态编程的方 法来检测时序模式，但没有就时序的处理与算法的实现做深入的探讨；文献 3 4 提出了时序信息系统( f e m p o r 日，f 确m 口f f o nj 把现z 舔) 与实时时序信息系统 ( 旭日f f 拥e 胞m p o 朋，f ”加r m d 打d 月s w 招m ，r m s ) 的概念，给出了时间序列转化为 信息系统的两种方法，使得粗糙集处理时间序列成为可能，但没有阐述时序信息 系统的获取问题。本文在上述文献的基础上，提出原始离散数据表、属性值变化 率等概念，阐述珊的获取途径，除了可以从原始离散数据表中采取选择提取的 方法得到，还可以从r 丌四转换获得，并提出一种根据客户需求利用属性值变化 率获得t 搭的方法。 3 2 相关基本概念 定义3 1时序信息系统t i s 是一个三元组s = u ，彳u d ，f ) ， ，其中：u 是一个非空有限的对象集合，爿是描述事件状态的条件属性集合，d 是决策属 性，是时序属性，d 诺4 ，fg 爿， 是关于f 的线序关系， 硕士学位论文 第三章时序信息系统获取方法研究 = ( x ，y ) ：x ，y | n z y ) ，是自然数集合。时序信息系统对应的二维表是 时序信息表。 时序信息系统很好的体现了时序特性，通过决策表清楚地看到时序与各非时 序属性之间的关系。对于粗糙集理论来说，它处理的对象是不随时间变化的信息 系统，因此对于7 嚣来说，要运用粗糙集理论来进行分析，首先必须考虑将7 b 向四的转换问题。转换的目的就是消去时序属性f ，然后运用粗糙集理论进行属 性约简并提取规则。 定义3 2 实时时序信息系统r t t i s 是一个三元组s 。= u ，爿u 翻，f ，6 ，_ ， 其中：u ，一，d ，f ，- 与定义3 1 的表示相同，占是时间属性，占