（计算机应用技术专业论文）知识挖掘在时序信号分析系统中的应用.pdf

摘要 摘要 现今社会信息技术1 5 l 速发展，人们在日常工作中会彩! 累犬量的多种类型的时序数 据。所谓时序数据是指按时l h jj i l j 孑摊列的观测值的集合。对于这些大量的时序数据进行 分析处理，挖掘其背后蕴涵的价值信息，具有重要的实际意义。粗糙集理论是波兰数学 家p a w l a k z 于1 9 8 2 年提出的一种分析模糊和不确定知识的强有力的数学工具。它能够 有效地处理不完整、不确定知识的表达和推理。这个特点使得粗糙集理论非常适合应用 于时序数据的分析处理。 首先，本文研究了时间序列信息系统的获取方法，它是转换为非时序信息系统的前 提，同时也是属性约简和规则提取的基础。时序信息系统可以从原始离散数据中获得， 也可以从实时时序信息系统转换得到，然后将时序信息系统转化成可以使用粗糙集进行 属性约简的信息系统。其次，对转化后的决策表进行属性约简，同时也是数据挖掘的基 础。本文详细介绍了几种约简算法的处理过程并且举算例进行验证分析，得出基于集合 近似质量的属性约简算法较其他几种算法简单明了，约简效果令人满意。另一方面，由 于基于差别矩阵的约简策略使用范围广，但算法计算复杂度大且效率低，所以针对这些 问题，本文对一种基于差别矩阵的算法进行改进，以属性频率作为选择属性的启发信息， 用过滤差别矩阵替代差别矩阵得到属性频率，避免了低效率大复杂度的计算，同时也可 以得到很好的约简效果。最后，本文研究了规则获取的方法。由于数据库中的时序信号 数据在实际情况中大部分是动态变化的，因此一般的基于静态数据库的规则获取方法显 然存在不足。本文给出了一种基于粗糙集和决策树的增量式规则获取方法，并与基于静 态的知识系统的规则获取方法和现有的动态规则获取算法进行分析比较，实验结果表明 该方法表现令人满意。 关键字：粗糙集；属性约简；时序系统；规则提取 人造交通人学r 导颂十学何论文 ! = = ! ! ! = = = ! ! ! = = ! = = ! = ! = ! = e = ! = ! ! ! ! ! = = = ! ! ! = ! = = = ! = - l ! ! ! ! = = ! ! = = = = ! = = ! ! = = = ! = ! ! = ! ! = ! = ! ! = = ! = = ! = ! ! ! ! e = ! a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g yi nt o d a y ss o c i e t y , p e o p l ew i l l a c c u m u l a t eal a r g en u m b e ro fm u l t i p l et y p e so ft i m e - s e r i e sd a t ai nt h e i rd a i l yw o r k t h e s o c a l l e dt i m e - s e r i e sd a t ai sa r r a n g e di nc h r o n o l o g i c a lo r d e r , ac o l l e c t i o no fo b s e r v a t i o n s i t h a si m p o r t a n tp r a c t i c a ls i g n i f i c a n c et o a n a l y z ea n dp r o c e s s w i t ht h el a r g en u m b e ro f t i m e s e r i e sd a t aa n dm i n ew i t ht h ev a l u eo ft h eu n d e r l y i n gi m p l i c a t i o no fi n f o r m a t i o n r o u g h s e tt h e o r yi sap o w e r f u lm a t h e m a t i c a lt o o lb r o u 【g h tb yp a w l a k zi n1 9 8 2 ，am a t h e m a t i c i a ni n p o l i s h ，w h i c hc o u l da n a l y z ev a g u ea n du n c e r t a i nk n o w l e d g e i tc a l le f f e c t i v e l yd e a lw i t h i n c o m p l e t ea n du n c e r t a i nk n o w l e d g er e p r e s e n t a t i o na n dr e a s o n i n g t h i sf e a t u r em a k e st h e r o u g hs e tt h e o r yi sv e r ys u i t a b l ef o rt i m e s e r i e sd a t aa n a l y s i sa n dp r o c e s s i n g f i r s to fa l l ，t h i sp a p e rs t u d i e st h ea c q u i s i t i o na p p r o a c ha b o u tt h ei n f o r m a t i o ns y s t e mo f t i m es e r i e s ，w h i c hi st h ep r e m i s eo fc o n v e r t i n gt on o n s e q u e n t i a li n f o r m a t i o ns y s t e m ，b u ta l s o t h ef o u n d a t i o no ft h ea t t r i b u t er e d u c t i o na n dr u l ee x t r a c t i o n t i m i n gi n f o r m a t i o ns y s t e m sc a l l b eo b t a i n e df r o mt h eo r i g i n a ld i s c r e t ed a t aa l s oc a nb ec o n v e r t e df r o mr e a l t i m et i m i n g i n f o r m a t i o ns y s t e m ，a n dt h e nc o n v e r t e dt i m i n gi n f o r m a t i o ns y s t e mi n t oi n f o r m a t i o ns y s t e m w h i c hc o u l du s et h er o u g hs e t st oa t t r i b u t er e d u c t i o n w h a t sm o r e ，w ed e a lt h ea t t r i b u t e r e d u c t i o na b o u tt h ed e c i s i o n m a k i n gt a b l ef r o mt h et r a n s f o r m a t i o n i ti sa l s ot h ef o u n d a t i o no f t h ed a t am i n i n g t h i sp a p e rm i n u t e l yd e s c r i b e ss e v e r a lp r o c e s s i n g so ft h er e d u c t i o n a l g o r i t h m s ，a n dg i v e se x a m p l e st ov e r i f y , a n dt h e nw eg e tag o o da l g o r i t h mb a s e do ns e t a p p r o x i m a t i o nq u a l i t y c o m p a r e dw i t ho t h e ra l g o r i t h m s ，i ti sm o r ec o n c i s ea n dt h ee f f e c to f r e d u c t i o ni ss a t i s f a c t o r y o nt h eo t h e rh a n d ，t h o u g hr e d u c t i o ns t r a t e g yb a s e do nd i s c e r n i b i l i t y m a t r i xi sw i d e l yu s e db u tt h ec o m p u t a t i o nc o m p l e x i t yi sv e r yl a r g ea n di n e f f i c i e n c y s oi n a l l u s i o nt ot h e s ep r o b l e m s ，t h i sp a p e rh a si m p r o v e d 柚a l g o r i t h mb a s e do nt h ed i s c e r n i b i l i t y m a t r i x ，u s i n ga t t r i b u t ef r e q u e n c ya sh e u r i s t i ci n f o r m a t i o no fc h o i c e a t t r i b u t ea n du s i n g f i l t e r i n gd i s c e r n i b i l i t ym a t r i xi n s t e a do fd i s c e r n i b i l i t ym a t r i xt og e tt h ea t t r i b u t ef r e q u e n c y , s o i tc a na v o i dt h ei n e f f i c i e n c ya n dl a r g ec o m p u t a t i o nc o m p l e x i t ya l s oc a ng e tt h es a t i s f a c t o r y r e s u l to fr e d u c t i o n f i n a l l y , t h i sp a p e rs t u d i e st h em e t h o d so fr u l ei n d u c t i o n b e c a u s em o s to f t h et i m i n gs i g n a ld a t ai nt h ed a t a b a s ei sd y n a m i ci na c t u a ls i t u a t i o n ，s ot h eg e n e r a lr u l eb a s e d o ns t a t i cd a t a b a s ea c c e s sm e t h o di sc l e a r l yd e f i c i e n t t h i sp a p e rp r e s e n ta ni n c r e m e n t a lr u l e i n d u c t i o nm e t h o db a s e do nd e c i s i o nt r e ea n dr o u g hs e t s a n dc o m p a r ew i t ht h er u l ei n d u c t i o n m e t h o dw h i c hi sb a s e do ns t a t i ck n o w l e d g es y s t e m t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h e p e r f o r m a n c eo ft h ei n c r e m e n t a lr u l ei n d u c t i o nm e t h o di ss a t i s f a c t o r y k e y w o r d s ：r o u g hs e t s ；a t t r i b u t er e d u c t i o n ；t i m i n gs y s t e m ；r u l ei n d u c t i o n 大连交通大学学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢及参考 文献的地方外，论文中不包含他人或集体已经发表或撰写过的研究成 果，也不包含为获得太羹塞通太堂或其他教育机构的学位或证书而 使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示谢意。 本人完全意识到本声明的法律效力，申请学位论文与资料若有不 实之处，由本人承担一切相关责任。 学位论文作者签名：刘延可鞭 日期： 2 。口? 年，z 月f 日 大连交通大学学位论文版权使用授权书 本学位论文作者完全了解态羹塞通太堂有关保护知识产权及保 留、使用学位论文的规定，即：研究生在校攻读学位期间论文工作的 知识产权单位属太董壅适盍堂，本人保证毕业离校后，发表或使用 论文工作成果时署名单位仍然为太整交通太堂。学校有权保留并向 国家有关部门或机构送交论文的复印件及其电子文档，允许论文被查 阅和借阅。 本人授权塞董塞适太堂可以将学位论文的全部或部分内容编入 中国科学技术信息研究所中国学位论文全文数据库等相关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 ( 保密的学位论文在解密后应遵守此规定) 学位论文作者签名：支t 、】廷卵岬 日期：z d 驴9 年t2 月日 学位论文作者毕业后去向： 工作单位： 通讯地址： 电子信箱： 导师签名：蜴亲辽蜴粢辽 吼力。7 年t 2 - 月日 电话： 邮编： 第一尊绪论 第一章绪论 1 1 研究背景 觇今社会信息技术飞速发展，人们在日常事务处理和科学研究中积累了大量的各种 类型的数据。在人们所存储的海量数据中，有许多是“时间序列”( t i m es e r i e s ) 数据。所 谓时问序列数据是指按时问顺序排列的观测值数据的集合。按照研究对象的不同，可以 得到各种类型的时间序列数据。例如地质学家测绘某个地区地质的细微变化，气象学家 研究天气变化与云层的关系，水利研究人员研究某流域水位与降雨量的变化关系等，都 会观测到按某种度量单位测量的一系列数据，其自然顺序就是按出现的时间先后排列而 得到的时间序列数据。自然界以及社会生活中的各种事物都是在运动、变化和发展着的。 事物之问也是相互影响、相互作用的，一个事物的运动、变化和发展要受到其它事物的 影响和制约，同时，它的发展变化也影响和制约着其它事物。 我们注意到时间序列数据不仅仅是对历史事件的记录，展现事物变化的显示方式。 伴随着时间推移和时间序列数据的大规模增长，如何对这些海量的时间序列进行分析处 理，挖掘其背后蕴涵的价值信息，对于我们揭示事物发展变化的内部规律，以及不同的 事物之间的相互作用关系，为人们正确认识事物和科学决策提供依据等等具有重要的实 际意义。因此有关时间序列分析研究一直以来就受到了许多研究人员的广泛重视，成为 一个具有重要理论和实用价值的热点研究课题。 金融市场、信息网络以及电子商务等领域超容量数据的获得，是时间序列分析研究 的一个重要动力，在全球化竞争日益激烈的环境中，这些数据的可利用价格越来越大。 对这些数据进行综合分析的迫切性促进了我国时间序列分析应用研究的发展。 近年来我国学者对于时间序列的研究取得了极其丰硕的成果，主要体现在基础理论 研究的不断加强f 某些领域已经达到了国际前沿水平，而不再只是纯粹的吸收引进国外 的先进成果) ；应用领域的不断拓展，在应用中求创新求发展，在部分应用领域中我们 已经跟上了国际步伐。虽然我们在时问序列研究领域取得了长足的进步，但是基础领域 的研究状况仍不为乐观，主要体现在整体研究水平不高，国际领先成果往往集中于个别 院校甚至个别人，这与国际研究趋势不符。应用领域也存在分析工具的滞后性，一些最 新成果还没有得到及时的应用，而且很多分析工具都是针对某具体领域的，并不适合 于多领域的时间序列数据分析。 当今数据采集和存储技术的迅速发展，数据库中存储的数据量急剧增加，数据库的 规模也因此变得越来越庞大。人们发现我们己不再是缺少信息，而是被信息海洋所淹没。 人造交通人学i 宁硕十学何沦文 如何分析数据并从中挖掘出有用的知识是一项既费时又难于进行的工作。通常，对于特 定领域的数据挖掘需要有定的背景领域知识，并在此基础上采用某种有效工具从数据 集中获取更多的隐含的、先前未知的并具有潜在价值的知识。这种挖掘在工业过程控制、 医疗诊断、股票分析、水文气象等领域尤显重要，因为这些领域的数据有一个共同的特 点，即它们都记录了某个领域的时间序列信息，且信息量特别巨大，如果没有合适的挖 掘手段则势必给以后的决策和新数据的预测带来困难。信息系统中时间序列数据的出现 使得有必要针对这一特殊数据类型的挖掘给出相应的策略，以便发现在某段时间内连续 记录的某属性序列值的变化规律，以及它的变化给其它属性值所带来的影响。 粗糙集理论的研究在近几年不断深入，因为其可以处理不精确、不确定与不完全数 据并从数据中挖掘出需要的知识，而且很多时序数据属于这种不精确不确定的类型，因 此可以运用粗糙集工具对时间序列进行属性约简，从中获得人们感兴趣的规则集。它已 被广泛地应用于数据库中的知识发现、智能控制、机器学习、决策分析、专家系统以及 模式识别等众多领域。 1 2 研究内容 本论文的研究内容是使用数据挖掘手段对大量的时序数据进行知识挖掘，论文里采 用的是粗糙集工具，从中获得有价值的规则或隐含的信息来供人们进行下一步决策。它 的处理过程是对时序数据进行预处理，去掉时间属性，将其变为非时序数据，形式为非 时序信息表或者是决策表，再采用基于粗糙集的方法对该决策表进行属性约简，去除冗 余数据，然后对约简后的决策表进行规则提取，得到我们想要的隐含信息。 论文核心工作的第一个部分就是时序信息表的获取问题，它是转换为非时序信息表 的基础。通常的时序数据，是人们在日常生产生活中通过采样得到。采样之前已经将抽 样频率设置好了，所以它们本身能够真实的反映出原始时序信号曲线。但是对于通过数 据预处理得到的时序信息表或决策表，在绝大多数情况下都存在冗余信息，因此如何从 大量的原始数据中提取满足要求的时序数据来构成时序信息表或决策表是我们所要研 究的一个问题。至于将时序信息表转换为非时序信息表的问题，己有学者提出了较好的 转换算法，所以本论文对于该方面不做详细讨论，只是简要描述该转换方法处理过程。 论文核心工作的第二个部分就是对转换后的非时间序列信息表进行属性约简问题， 它是进行数据挖掘的关键步骤，本文重点研究属性约简问题。属性约简方法目前有很多， 有基于属性重要性的约简、基于差别矩阵的约简、基于遗传算法的约简、动态约简等。 本文详细介绍了几种有代表性的属性约简算法并且列举出例子来说明约简过程，论文详 细介绍了一种基于集合近似质量的约简算法，并且分析了该方法的时间复杂度。另一方 2 第一蕈绪论 面，冈为甚于差别矩阵的约简策略在众多的约简策略中是最常用的，但是该算法策略存 舀计算：复杂度大，计算效率低的问题，特别是当数据量很人的时候这种不足就越发妙j 显。 故针对这些鬯问题，本文对一种基于差别矩阵的算法进行改进，以属性频率作为选择属性 的启发信息，用过滤差别矩阵替代差别矩阼得到属性频率，避免了低效率大复杂度的计 算的同时也能得到很好的约简效果。 核心问题的最后一个也是数据挖掘的最后一个步骤，它便是规则获取，获得我们想 要的隐含在大量数据当中的潜在价值信息。在实际应用中，数据库中的时序信号数据基 本上是动态变化的，因此一般基于静态数据库的规则获取方法和传统动态方法在规则获 取方面显然存在不足，因为每次新增数据之后都要重新进行学习过程，那样会耗费大量 时间和空间资源。所以研究规则获取的增量式算法是知识发现领域所需解决的一个很实 用的问题。文章给出了一种将粗糙集和决策树结合起来的增量式规则获取算法，然后将 其与基于静态的知识系统的规则获取算法和传统动态算法进行了分析比较，实验结果表 明该算法具有的更好的表现，识别率更高，获得的规则更精简。 1 3 研究意义 现今社会信息技术飞速发展，数据库中存储的数据量急剧增加，数据库的规模也因 此变得越来越庞大。人们发现自己已不再是缺少信息，而是被信息海洋所淹没。如何分 析数据并从中挖掘出有用的知识是一项既费时又难于进行的工作。通常，对于特定领域 的数据挖掘需要有一定的背景领域知识，并在此基础上采用某种有效工具从数据集中获 取更多的隐含的、先前未知的并具有潜在价值的知识。这种挖掘在工业过程控制、医疗 诊断、股票分析、水文气象等领域尤显重要，因为这些领域的数据有一个共同的特点， 即它们都记录了某个领域的时序数据信息，且信息量特别巨大，如果没有合适的挖掘手 段则势必给以后的决策和新数据的预测带来困难。 信息系统中时间序列数据的出现使得有必要针对这一特殊类型数据的挖掘给出相 应的策略，以便发现在某段时间内某属性序列值的变化规律，以及它的变化给其它属性 值所带来的影响。近年来，随着粗糙集理论研究的深入，它已被广泛地应用于数据库中 的知识发现、智能控制、机器学习、决策分析、专家系统以及模式识别等众多领域。 理论意义：通过对时序数据的知识挖掘，运用粗糙集工具对预处理后的决策表进行 属性约简，去除冗余信息，然后从中获得人们感兴趣的规则。文中的时序数据获取方法、 对基于差别矩阵的属性约简方法的改进和将粗糙集和决策树结合起来的增量式规则获 取方法是对知识挖掘在时序信号数据分析研究的个拓展。 现实意义：将上述方法运用到时序数据的实际工程领域，包括金融领域、电力行业、 3 人连交，嗵人。学。i ：1j 位论文 水利工程、医学器械等，为这些工程领域的信息处理提供一个有效的方法，以便人们获 取规则、发现知识，提高和改进工竹效率，以便对社会提供更好的服务。 1 4 论文结构分配 本论文结构分配如下所示： 第一章，介绍本文的研究背景、研究内容、研究意义以及章节安排。 第二章，介绍了时间序列数据、粗糙集、数据挖掘各自的概念、研究现状及相应功 能和技术，为后续章节的开展进行一些必要的铺垫。 第三章，探讨了时序数据信息系统的获取方法，可以从原始离散数据得到，也可以 从实时时序信号信息系统中获得；同时介绍了时序信号信息系统转换为信息系统的方 法。 第四章，研究了属性约简的方法。详细介绍了几种有代表性的属性约简方法，并且 举例说明约简过程，然后分析各自的特点，对一种基于集合近似质量的约简方法进行详 细的时问复杂度分析，相比之下比之前几种方法约简过程简单明了。之后针对基于差别 矩阵的约简方法使用范围广，但是计算复杂度高并且效率低的不足，对一种基于差别矩 阵的约简进行改进，以属性频率作为选择属性的启发信息，用过滤差别矩阵替代差别矩 阵得到属性频率，避免了低效率大复杂度的计算，同时也可以得到很好的约简效果。 第五章，对规则获取策略进行了探讨。因为传统的规则获取方法在处理动态数据方 面存在不足，所以我们需要一种在处理动态数据方面较优的获取策略。以粗糙集理论为 基础，根据新增数据集与已有规则集的关系，提出了一种将粗糙集理论和决策树结合起 来的增量式规则获取算法，通过与基于静态的知识系统的规则获取算法和传统动态规则 获取算法进行了对比分析，表明该算法表现效果更好。 第六章总结与展望。对本文所做工作进行总结，然后在此基础上对下一步的研究 工作做出工作展望。 4 第章时间哆列、羊! l 集硎论羊l l 藿7 j 据挖捌溉述 第二章时间序列、粗集理论和数据挖掘概述 2 1 时间序列概述 2 1 1 时间序列概念 在a g r a w a l 等人的文章【1 。3 l 中，时问序列被定义为“a no r d e rs e to fr e a lv a l u e ”。它是指 一类有序的，复杂的对象的集合，时间序列数据主要是通过系列的方法，从大量的时 序数据中发现特定的规律和有价值的知识。如“相似性搜索”，“模式发现”，“趋势预测 等。所以从一般意义上来说，时间序列泛指那些随时间或空间有序变化的数据集合，这 些数据记录集合往往采用等时间或空间问隔进行度量。如何充分有效地管理和利用这些 海量数据序列，更有效地发现和理解这些数据序列背后隐含的规律和知识，已经受到越 来越多数据挖掘研究者广泛关注。时问序列数据挖掘由此应运而生，并成为数据挖掘领 域中一个重要研究方向。 关注时间序列并不是新鲜的事，早在上个世纪4 0 年代就从数理统计的角度给出了 基本的理论，到了7 0 年代，就开始广泛应用了，成为统计学中很重要的一个分支，主 要集中于时间序列数据的建模、滤波和预测等方面。 传统的数理统计中的时间序列分析方法往往是先提出假设再进行验证，其目的是实 现对系统整体行为的把握和预测。但在实际生活和工作中逐渐提出了一些新需求：在实 际的时间序列分析过程中需要对时间序列局部特征进行分析；发现不同数据源在相同时 间区间内或者相同数据源在不同时间区间中的相似性和差异性，从中提取关联规则，发 现知识；在线监控不断变化的时间序列是否在某一时刻发生异常；为用户提供个性化的， 更容易理解的关于时间序列形态的形象化描述信息。传统的时间序列分析技术对数据库 应用领域( 如数据仓库以及知识发现等) 提出的新需求开始显得力不从心。因此从二十世 纪九十年代早期开始，时间序列数据挖掘作为一个新的研究方向出现，并成为数据挖掘 领域的一个重要分支。时间序列挖掘是针对时间序列的模式发现过程，旨在研究隐含在 时间序列中更深层次的知识，包括时间序列数据的拟合和变换、时间序列的相似性查询、 时序模式挖掘、聚类、分类、可视化、时间序列的异常检测等研究内容。 时间序列数据挖掘的许多技术来源于传统时间序列分析的理论与技术。两者的研究 对象与目的也基本相似：即发现时间序列数据中蕴含的规律。所不同的是时间序列数据 挖掘更加关注海量时间序列的处理技术且更加强调时间序列的形态特征，通常用形态特 征来刻画时间序列中蕴含的规律，而传统时间序列分析技术通常用解析函数或者统计量 刻画时间序列中蕴含的规律。 5 人近交通人f ：誓硕卜“寺沦艾 2 1 2 时间序列的研究现状 随着数掘挖掘研究领域的拓展，针对时间序列数据的挖掘研究r 益受坌0 人们的关 注，自从2 0 世纪9 0 年代以来发展迅速，其研究内容涵盖了时f i j 序列的柏似模式匹配、 分类和聚类、异常检测、序列模式挖掘、周期模式挖掘等等。下面介绍这几个方面的研 究所涉及的一些问题或采用的方法。 ( 1 ) 时问序列的相似模式匹配 时间序列相似模式匹配是时间序列数据挖掘的一个重要内容，至今还没有得到很好 地解决。因为时间序列来源于实际生活中的各个应用领域，采样方法和测量标准都不一 致，具有短期波动频繁、大量噪声干扰以及非稳态的特点，使得相似模式匹配变得非常 困难。相似性度量是时间序列的相似模式匹配的基础，时间序列的索引技术则可以提高 相似性查询的效率。 ( 2 ) 分类和聚类 分类问题是给定一个序列集合，每个序列隶属于一个事先定义好的类别，作为训练 集，通过一定的分类学习算法，自动学习每个类的特征描述，用来对新的未知类别的序 列进行归类。时间序列分类算法在许多文献中被提出【l ，但这些算法主要是在已有的 分类算法引入一个新的相似性度量方法，文献【7 】认为这些方法在一些有名的时间序列数 据库中，与e u c l i d e a n 距离相比，在实验中的性能很差。这种令人失望的效果可能是因 为时间序列数据库中存在的噪声和模糊特点造成的，为了解决这个问题，文献1 6 j 将模糊 规则引入到时间序列分类中。聚类问题是自动发现具有相似特征的时间序列，时间序列 的聚类发现往往以相似模式匹配算法为基础，总的可以分为两大类：全序列模式聚类和 子序列聚类。全序列聚类是在一个时间序列数据集中，将相似的时间序列组聚到一起。 子序列聚类是对一个时间序列来说，用一个移动窗，在滑动过程中，将行为相似的时间 序列段聚在一起。 ( 3 ) 异常检测 时间序列异常检测是时间序列数据挖掘的新兴研究领域。在通常的数据挖掘过程中 一般将异常数据忽略或者删除，但是在某些情况下，异常数据含有丰富的有价值的信息， 如电力系统运行中的异常或银行信用卡欺骗行为的监测等。目前，时间序列的异常还没 有一个公认的定义，许多研究者都提出了不同的异常定义。异常挖掘可以被视为两个子 问题：即什么样的数据是异常的，以及如何挖掘出这样的异常点。与之有关的文献有： 离群值挖掘【8 1 ，非正常事件挖掘【9 】，异常行为挖掘【1 0 l ，和惊奇模式挖掘1 1 1 啦】等。 ( 4 ) 序列模式挖掘 序列模式挖掘是挖掘与时间或其它时间序列有关的频繁发生的模式。可以分为关联 6 第：章时间守州、期l 集理论平l i 数据挖掘概述 规则挖掘和序贯模式挖掘算法。其中关联规则挖掘是由r a g r a w a l 等人【1 3 j 首先提出，挖 掘的是给定数据集中，数据项2 _ f h j 存在的有价值的联系1 1 4 l 。描述的是交易内部的项集之 间的关联，例如，一个顾客在购买电脑的同时也会购买软件，市场购物分析是它的一个 典型应用。序贯模式挖掘最早也是由r a g r a w a l 首先提出的【1 5 l ，描述的是交易之间的关 联，例如，1 0 购买计算机的客户在随后的交易中会升级内存。关联规则中采用的a p r i o r i 特性广泛应用于时间序列序列模式的挖掘中。另一种常用的方法是基于数据库投影的模 式成长技术，不需要生成候选模式。 ( 5 ) 周期模式挖掘 周期模式挖掘是一个前沿研究方向，用于揭示时间序列数据中存在的演化规律，对 于发现时序数据中的潜在知识具有重要意义。时间序列周期模式挖掘是对时间序列模式 挖掘的进一步发展和延伸，模式挖掘的一些方法和概念在周期模式挖掘中仍然存在广泛 应用，目前，时间序列周期模式挖掘的研究集中于给出不同类型的周期模式的定义及其 挖掘算法，如关联规则周期1 1 6 1 、部分周期模式1 1 7 。1 剐、异步周期模式挖掘【1 9 - 2 0 】、令人惊异 的周期模式1 2 1 】等，不同的部分周期模式的提出及其相应的挖掘算法是现在的研究重点。 2 2 粗糙集理论概述 2 2 1 粗糙集理论的产生和发展 经典逻辑中只有真、假二值，但实际上有大量含糊现象存在于真和假二值之间，因 此，长期以来许多逻辑学家和哲学家就致力于研究含糊概念。早在1 9 0 4 年，谓词逻辑 的创始人f r e g e g 就提出了含糊一词，并把它归结到边界线区域，也就是说在整体论域 上存在一些个体既不能在某个子集上被分类，也不能在该子集的补集上被分类。1 9 6 5 年，z a d e h l a 创立了模糊集合论，不少理论计算机科学家和逻辑学家，都试图通过这 一理论解决f r e g e g 的含糊概念，但模糊集是不可计算的，没有给出数学公式描述这一 模糊概念，故无法计算出它在边界线上的具体的含糊元素数目。1 9 8 2 年，p a w l a k z 针 对f r e g e g 的边界线思想提出了粗糙集，他把那些无法确认的个体都归属于边界线区域， 而这种边界线被定义为上近似集与下近似集之间的差集，由于上近似集和下近似集都可 以通过等价关系给出确定的数学公式描述，所以含糊元素数目可以被计算出来，即在真、 假二值之间的含糊程度可以计算，从而实现了f r e g e g 的边界线思想。粗集理论主要兴 趣在于它恰好反映了人们用粗集方法处理不分明问题的常规性，即以不完全信息或知识 去处理一些不分明现象的能力。 粗糙集理论是波兰数学家p a w l a k z 于1 9 8 2 年提出的1 2 2 1 。这一理论为处理具有模糊、 不精确或不完全信息的分类问题提供了一种新的工具。起初，由于这个理论建立在商集 7 人j 士奎：遵j j 。f 学硎十。何论文 基础之上，较为复杂的数学使得这个理论未能引起人工智能研究者的注意，研究地域也 仅局限于波兰等东欧一些国家。当时许多波兰学者对粗糙集理论及乓应用进行了i 坚持不 懈的研究，其f ，对粗糙集理论的数学性质与逻辑系统进行了广泛的分析。当时大多数研 究成果发表， “b u l l e t i no ft h ep o l i s ha c a d e m i co fs c i e n c e s ”上，同时，他们也丌发了一 些应用系统，但都处于萌芽阶段1 2 3 j 。直到1 9 9 0 年前后，由于该理论在数据的决策与分 析、模式识别、机器学习与知识发现等方面的成功应用 2 4 - 2 6 1 ，才逐渐引起世界数学界和 计算机界的广泛关注。1 9 9 1 年p a w l a k z 的专著粗糙集一关于数据推理的理论的问 世阳，标志着粗糙集理论及其应用的研究进入了活跃时期。 p a w l a k z 所建立的粗糙集理论有3 个部分：首先，使用上、下近似表示知识的不确 定性即粗糙，把某一论域中无法确认的个体归属于边界区域，而这种边界区域正是上近 似集和下近似集之差。其次，对数据库的知识约简。最后，基于不确定性的推理。p a w l a k z 建立粗糙的原始本意是为了不确定性推理，但是，近几年的研究表明，粗糙集中的不 确定性推理可能是这个理论中最不重要的部分，而最重要的是约简，其次是粗糙。粗糙 的重要性不是为了推理，而是为了表示不同简洁程度知识的粒度【撂2 9 】，粗糙集可以作为 表示知识粒度的一个显现的测量。粗糙集理论最为重要的意义是，将机器学习问题定义 在等价关系对空间的划分上，即商集理论上，并由此系统地提出约简的概念。 2 2 2 粗糙集理论的基本概念 粗糙集理论是一种新的处理模糊和不确定性知识的数学工具。其主要思想就是在保 持分类和决策能力不变的前提下，通过知识约简，导出问题的决策或分类规则。目前， 粗糙集理论己被成功地应用于机器学习、决策分析、过程控制、模式识别与数据挖掘等 领域。下面介绍粗糙集的相关理论，这些作为后续工作的理论基础1 3 0 - 3 3 1 。 定义2 1 信息系统被定义为如下的四元组：st 缈，a ，v ，厂) 。其中s 为知识表达系统； u 一 ，x ：，工。) 为对象的非空有限集合，也称论域；a = 和。，口：，a 。) 为属性的非空 有限集合；y 为属性值域，v = i j 圪；厂：ux a 呻矿为一信息函数，表示对每一个ae a ， 口，t x e u ，厂伍，a ) s 圪。当信息系统中属性a cud ，其中c 为条件属性集，d 为决策 属性集时，信息系统也称为决策系统。决策系统是最为常见的信息系统。 定义2 2 若p w ，且p 乒矿，则p 中的全部等价关系的交集称为p 上的不可分辨 关系，记为i n d ( p ) ：i n d ( p ) = o ，y ) ux u ，v a e p ，厂o ，a ) ；f ( y ，口) 。不可分辨关系 也称为等价关系。它把u 划分为有限个集合，称为等价类。在每一个等价集合中，对象 间是不可分辨的。 8 第二章时问宁列、糨集理论和数据挖掘概述 定义2 3 令x u ，r 是【，上的一个等价关系。当x 为尺的某些等价类的并时，称 是可定义的，称x 是尺可定义的，否则称石是r 不可定义的。尺可定义集称为尺精确 集，r 不可定义集称为r 粗糙集。粗糙集可以用两个精确集来描述，即粗糙集的上近似 和下近似。我们可以这样定义它们，把包含在x 中的最大可定义集称为x 的尺下近似， 记为r ( x ) 一缸e uib 】骨x ) 。包含x 的最小可定义集称为x 的尺上近似，记为 尺伍) = 缸【厂i f j c l rn x 乒囝】- 。从另一个角度来讲，也可以将集合的下近似和上近似也 可以用等式星( x ) 一咿缈r ) i y x 和n ( x ) t g r ) ly n x ，妒】来表示。 定义2 4 集合p o s 置( x ) 一星( x ) 称为x 的r 正域，n e g r 仁) ；u - n ( x ) 称为x 的r 负域。x 的尺边界域可以定义为剧( x ) tr ( x ) 一星( x ) 。星( x ) 表示在知识尺下u 中所 有一定能归入x 的元素的集合，r ( x ) 表示在知识尺下u 中可能归入x 的元素的集合。 b n 。( x ) 表示在知识尺下u 中既不能肯定归入x 也不能肯定归入一x 的元素的集合。 定义幸宰设u 为一个论域，p 和q 为定义在u 上的两个等价关系簇，q 的p 正域记为 p o s e ( q ) ，定义为p o s e ( q ) u 只何) 。如图2 1 所示。 、 f j ， l lji_ _ 一， l 、 i r ， i i | j ， il l 、l 1 i 【k_ j ， 1 ii ， l 一 图2 1 租糙集概念示意图 f i g 2 1r o u g hs e tc o n c e p ts k e t c h 定义2 5 设u 为一个论域，p 和q 为定义在u 上的两个等价关系簇，若 p o s p ( q ) = p o s ( p 、( ，) ) ( q ) ，则称，为p 中相对于q 可省略的( 不必要的) ，简称p 中q 可省 略的；否则，称r 为p 中相对于q 不可省略的( 必要的) 。 定义2 6 设u 为一个论域，p 和q 为定义在【厂上的两个等价关系簇，若p 中的每一 ，都是p 中q 不可省略的，则称p 为( 相对于) q 独立的。 定义2 7 设【厂为一个论域，p 和q 为定义在u 上的两个等价关系簇，若p 的q 独立 9 火连交通大学i ：学硕+ 学位论艾 子集sc p 有p o s s ( q ) tp o s p ( q ) ，则称s 为p 的q 约简。 定义2 8 一个决策表是一个信息表知识表达系统s = ，a = cud 是属 性集合，子集c 和d 分别称为条件属性和决策属性集，d 面。 定义2 9 差别矩阵是由波兰华沙大学数学家s k o w r o n 提出，其定义为：令s ：渺，彳) 是一个信息系统，【厂为论域r u 一怯，x ：，) ，a 是条件属性集合，d 是决策属性，a ( x ) 是记录x 在属性a 上的值，差别矩阵可表示为： ( 巳) = a e a ：口 ) ，t a ( x ，) d “) 一d 吒) 0 d 瓴) ad ) f ，；1 ，2 ，刀 一1 口“) = 口瓴)d “) d ( x ) 从上式可以看出，当决策属性不同且条件属性也不完全相同时，元素值为互不相同 的属性组合；当决策属性相同时，元素值为o ；当决策属性不同而条件属性完全相同时， 元素值为1 ，该情况表明数据有误或者提供条件属性不足。 定义2 1 0 对于一给定的决策系统s = 缈，cu d ，v ，d ，条件属性集合c 的约简是c 的一个非空子集p 。它满足：( 1 ) v a p ，a 都是d 不可省略的；( 2 ) p o s p ( d ) = p o s c ( d ) 则称p 是c 的一个约简，c 中所有约简的集合记作艇d ( c ) 。c 中所有不可省略属性的 集合称为c 的核，记为c d 髓( c ) ，则c d r e ( c ) = m 瞪d ( c ) 。 2 2 3 粗糙集理论的研究现状 目前，国内外对粗糙集理论的研究和应用发展都比较快，尤其是1 9 9 2 年s l o w i n s k i r 主编的关于粗糙集应用及其相关方法比较研究瞰j 的论文集的出版，推动了国际上对粗糙 集理论和应用的深入研究。1 9 9 2 年在波兰k i e k r z 召开了第一届国际粗糙集讨论会，这 次会议着重讨论了集合近似定义的基本思想及其应用，其中粗糙集环境下机器学习的基 础研究是这次会议的四个专题之一。但是，参加这次会议的研究者较少，范围也不太广 泛。1 9 9 3 年在加拿大b a n f f 召开了第二届国际粗糙集与知识发现( r s d 9 3 ) 研讨会。这次 会议极大地推动了国际上对粗糙集理论与应用的研究，其主题是粗糙集、模糊集与知识 发现。1 9 9 4 年在美国的s a n s o s e 召开了第三届国际粗糙集与软计算研讨会，这次会议广 泛探讨了粗糙集与模糊逻辑、神经网络、进化论等融合问题。 粗糙集理论及应用的几位主要倡导者，在1 9 9 5 年第1 1 期a c m 通讯上撰文，概括 性地介绍了目前人工智能应用新技术之一的粗糙集理论的基本概念，及其在知识获取和 机器学习、决策分析、知识发现等领域的具体研究项目和进展。尤其是1 9 9 5 年召开的 第4 届模糊理论与技术国际研讨会，在这次会议上，针对粗糙集与模糊集合的基本观点 1 0 第。二章时间序硎、粗集理论和数据挖掘概述 与相互关系展开了激烈的讨论，较大地促进了粗糙集的研究。1 9 9 6 年在日本东京召开了 第5 届国际粗糙集研讨会，这是第一次在亚洲地区召开的范围广泛的粗糙集研讨会。1 9 9 9 年1 1 月在日本、2 0 0 0 年1 0 月在加拿大又分别召开了第1 届和第2 届“粗糙集和计算的 当前趋势 学术会议，来自波兰、美国、加拿大、日本、挪威、俄罗斯、乌克兰和印度 等国家的研究人员参加了会议，会议阐述了当前粗糙集、模糊集的研究现状和发展趋势， 指出将着重在软计算、数据库、和近似推理等理论和应用方面发展。目前，许多关于 人工智能、模糊理论、信息管理与知识发现等国际学术会议上经常可以看到涉及粗糙集 的论文。 在国内，对粗糙集理论的研究和应用还处在起步阶段。1 9 9 6 年，王珏、苗夺谦等在 模式识别与人工智能发表了关于粗糙集理论与应用的综述，介