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

摘要 近年来，几乎在各种领域都需要处理时态数据，对时态的研究 也涉及很广。时态数据中包含着很多有用的信息，蕴含着许多潜在 的事物发展的规律。为了进行预测，必须挖掘时态数据中隐含的、 先前未知的、潜在有用的知识，以掌握事物发展的规律与趋势。很 多文献给出了时态型、时间粒度的概念、定义和性质，但如何将这 些性质运用在实际应用中，以便充分利用这些性质，提高数据挖掘 的深度和广度，这是一个需要解决的问题。本文提出的时态关系模 式在这方面作了初步研究，在时态数据理论上的定义、性质和实际 应用之间建立了一个转换的机制，并且运用了粗糙集理论对时态数 据挖掘进行了研究。 本文的第一章讨论了粗糙集理论和时态数据挖掘的研究现状， 并给出了本文的研究内容；第二章给出了与本文研究相关的粗糙集 概念和性质；第三章论述了时态数据与时态知识表达系统，第四章 研究了基于租糙集的时态数据挖掘的几个算法，第五章给出了一个 车流量统计分析上的应用。 本文获得的主要成果如下：针对粗糙集理论在知识获取上的特 点，提出了时态知识表达系统，并研究了时态知识表达系统的周期 性，多时间粒度性；给出了设定时态关系模式应遵循的规则；提出 了应用粗糙集在时态决策表上进行多时间粒度周期模式挖掘各个环 节的七个算法。 关键词：时态数据粗糙集时态关系模式多时间粒度 a b s tr a c t i i lr 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 d m a n y s t u d i e so fi th a db e e n h e l d t e m p o r a l d a t ai n c l u d e s i n t e r e s t i n g i n f o r m a t i o na n dc o n t a i n ss o m er u l e so ft h i n g s t oo b t a i nt h o s eu n k n o w n ， a v a i l a b l ea n du n d e r l y i n gk n o w l e d g ew h i c hi m p l i e di nt e m p o r a ld a t a ，w e h a v et o s t u d y i t st r a i t sa n d p r o p e r t i e s s o m ep a p e r s h a d p r o p o s e d c o n c e p t s ，d e f i n i t i o n a n dp r o p e r t i e ss u c ha s t e m p o r a lt y p e ，m u l t i - t i m e g r a n u l a r i t i e s ，e t c w i t ht h o s ed e f i n i t i o na n dp r o p e r t i e s ，w eh o p e t og e ta b e t t e rr e s u l to fd a t am i n i n g h o w e v e r , i ti sap r o b l e mh o wt oe x e r c i s e t h o s ed e f i n i t i o na n dp r o p e r t i e s i n p r a c t i c e 。s o 恤i sp a p e rp r o p o s e s t e m p o r a lr e l a t i o n a lp a t t e r nt or e a l i z es w i t c h i n gf r o mt h e o r yo ft e m p o r a l d a t at op r a c t i c a la p p l i c a t i o n r 1 1 l i sp a p e ra p p l i e st h e o r yo fr o u g hs e tt o s t u d yt e m p o r a l d a t a m i n i n g t h i sp 印e rd i s c u s s e st h et h e o r yo fr o u g hs e ta n da c t u a l i t yo fs t u d y w i t hr e s p e c tt ot e m p o r a ld a t am i n i n g ，a n di n t r o d u c e st h ec o n t e n t so f s t u d yo f t h i sp a p e ri nc h a p t e r1 i ti n t r o d u c e sc o n c e p t sa n dp r o p e r t i e so f r o u g hs e tt h a tr e l a t et ot h i sp a p e r sc o n t e n t so fs t u d yi nc h a p t e r2 t h e t h i r dc h a p t e rd i s c u s s e st e m p o r a ld a t aa n dt e m p o r a li n f o r m a t i o ns y s t e m w i t hm u l t i t i m eg r a n u l a r i t i e s t h ef o u r t hc h a p t e rr e s e a r c h e si n t os e v e r a l a l g o r i t h m sw i t hr e s p e c t t ot e m p o r a ld a t am i n i n gt h a tb a s e do nr o u g hs e t t h ef i f t hc h a p t e ra p p l i e so u rw o r kt oa n a l y z et h es t a t i s t i co fv e h i c u l a r c i r c u l a t i o n 1 5 i sp a p e rh a sd o n et h er e w a r d i n gt r yi nt h er e s e a r c ho ft e m p o r a l d a t am i n i n gb a s e do nr o u g hs e t t h em a i na c h i e v e m e n t sc o n t a i n ：1 p u t f o r w a r dt h et e m p o r a li n f o r m a t i o ns y s t e mw i t hm u l t i - t i m eg r a n u l a r i t i e s ， a n ds t u d yi t sp e r i o da n dp r o p e r t i e so fm u l t i t i m eg r a n u l a r i t i e s ；2 b r i n g f o r w a r dt h er u l e st h a tm u s tb ea p p l i e dw h e ns e tt e m p o r a l r e l a t i o n a l p a t t e r n ；3 d e v e l o ps e v e r a la l g o r i t h m st h a tw o r k i nw h o l ep r o c e d u r eo f t e m p o r a ld a t am i n i n g ，b y w h i c hw ec a na p p l yr o u g hs e tt oo b t a i np e r i o d p a t t e r no fm u l t i t i m eg r a n u l a r i t i e s o nt h et e m p o r a li n f o r m a t i o ns y s t e m w i t hm u l t i t i m eg r a n u l a r i t i e s k e yw o r d s ：t e m p o r a ld a t a ，r o u g hs e t ，t e m p o r a l r e l a t i o n a l p a t t e r n ，m u l t i - t i m eg r a n u l a r i t i e s 湘潭大学硕士学位论义 第一章绪论 本章介绍了粗糙集、时态数据挖掘有关的概念、技术乖研究现 状，论述了粗糙集理论的发展过程、研究背景和起源，总结了前人 在此领域所取得的成果，探讨了应用粗糙集理论进行时态数据挖掘 的研究和应用。最后介绍了本文研究的内容。 1 1 数据挖掘研究概述 1 1 1 引言 现在的社会已经进入了网络信息时代，计算机和网络信息技术 的高速发展和广泛应用使得各个领域的数据和信息急剧增加。随着 信息量的不断增长，对信息分析工具的要求也越来越高，人们希望 能从海量数据中挖掘出潜在的、有利用价值的信息，获取其潜在的 依赖模型。这给人类的智能信息处理能力提出了前所未有的挑战。 由此产生了人工智能研究的个崭新的领域数据挖掘和数据库 知识发现。 1 9 8 9 年8 月，在第1 1 届国际人工智能联合会议的专题研讨会上， 首次提出基于数据库的知识发现( k d d ，k n o w l e d g ed i s c o v e r yi n d 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 等人提出 了比较公认的数据挖掘定义u “：数据挖掘就是从大型数据库的数据 中提取人们感兴趣的知识。这些知识是隐含的、事先未知的潜在有用 信息，提取的知识表示为概念( 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 ) 等形式。这种定义把数据挖掘 的对象定义为数据库。而更广义的说法是h 。：数据挖掘意味着在一些 事实或观察数据的集合中寻找模式的决策支持过程。数据挖掘的对象 不仅是数据库，也可以是文件系统，或其它任何组织在一起的数据集 湘潭a 学硬士学位论文 合，侧如w w w 信息资源、数据仓库等。 数据挖掘是一个多处理阶段，数据挖掘过程主要有三个过程组 成：数据预处理、数据挖掘、结果解释和评价，整个过程是一个不 断循环和反复的过程。数据预处理主要目的是根据用户要求从数据 库中提取与数据挖掘有关的数据，并保证数据的完整性和一致性。 数据挖掘主要包括：确定数据挖掘的目的，运用正确高效的算法从 数据库中提取用户所需要的知识。结果的解释和评价则指：对所挖 掘的知识进行解释，以一种用户能够理解的方式呈现给用户。这期 间可能还要对知识的一致性进行检查以消除相互矛盾的知识。 在数据挖掘和知识发现的诸多方法中，粗糙集理论与方法对于 处理复杂系统不失为一种较为有效的方法。因为它与概率方法、模 糊集方法和证据理论方法等其他处理不确定性问题理论的最显著的 区别和最大的优势是它无需提供问题所需处理数据集合之外的任何 先验信息。粗糙集理论的主要特点在于它恰好反映了人们用粗糙集 方法处理不分明问题的常规性，即以不完全信息或知识去处理一些 不分明现象的能力，或依据观察、度量到的某些不精确的结果而进 行分类数据的能力。当然，由于这个理论未包含处理不精确或不确 定原始数据的机制，因此单纯地使用这个理论不一定能有效地描述 不精确或不确定的实际问题，所以需要和其他处理不确定性问题的 理论进行互补。 1 1 2 粗糙集理论研究现状 粗糙集( r s ，r o u g hs e t ) 理论是在集合论基础上发展起来的， 是一种刻划不完整性和不确定性的数学工具，能有效地分析和处理不 精确、不一致、不完整等各种不完备信息，并从中发现隐含的知识， 揭示潜在的规律n 3 。它是由波兰华沙理工大学z p a w l a k 教授等人在 1 9 8 2 年提出的随3 。由于最初关于粗糙集理论的研究主要集中在波兰， 因此当时并没有引起国际计算机界和数学界的重视，研究地域局限于 东欧一些国家。直到1 9 9 0 年前后，由于该理论在数据的决策与分析、 模式识别、机器学 - j 与知识发现等方面的成功应用，才逐渐引起了世 界各国学者的广泛关注。1 9 9 t 年p a w l a k 出版了专著n 1 ，系统全面地 阐述了粗糙集理论，奠定了严密的数学基础。该书与1 9 9 2 年出版的 粗糙集理论应用专集聃3 较好地总结了这一时期粗糙集理论与实践的 塑翌盔堂堡主兰垡笙塞! 研究成果，促进了它的进一步发展，现已成为学习和应用粗糙集理 论的重要文献。1 9 9 2 年在波兰k i e k r z 召开了第一届国际粗糙集讨论 会。1 9 9 3 年在加拿大b a n f f 召开了第二届国际粗糙集与知识发现研 讨会，这次会议极大地推动了国际上对粗糙集理论与应用的研究。 1 9 9 5 年a c mc o m m u n i c a t i o n 将粗糙集列为新浮现的计算机科学的研 究课题。至今，每年都召开以粗糙集为主题的国际会议，推动了粗 糙集理论的拓展和应用。1 9 9 9 年在日本召开了“第七届粗糙集、f u z z y 集、数据挖掘和粒度一软计算的国际学术研讨会”，阐述了当前粗糙 集、模糊集的研究现状和发展趋势，指出将着重在软计算、数据库、 a i 和近似推理等理论和应用方面发展。目前粗糙集理论已成为人工 智能领域中一个较新的学术热点，引起了越来越多的科研人员的关 注。 粗糙集理论具有以下特点： 1 粗糙集不需要先验知识。模糊集和概率统计方法是处理不确 定信息的常用方法，但这些方法需要一些数据的附加信息或先验知 识，如模糊隶属函数和概率分布等，这些信息有时并不容易得到。 粗糙集分析方法仅利用数据本身提供的信息，无须任何先验知识。 2 粗糙集是一个强大的数据分析工具。它能表达和处理不完备 信息；能在保留关键信息的前提下对数据进行化简并求得知识的最 小表达；能识别并评估数据之间的依赖关系，揭示出概念简单的模 式；能从经验数据中获取易于证实的规则知识，特别适于智能控制。 3 。粗糙集与模糊集分别刻划了不完备信息的两个方面1 ：粗糙 集以不可分辨关系为基础，侧重分类；模糊集基于元素对集合隶属 程度的不同，强调集合本身的含混性( v a g u e n e s s ) 。从粗糙集的观点 看，粗糙集合不能清晰定义的原因是缺乏足够的论域知识，但可以 用一对清晰集合逼近。有关粗糙集和模糊集内在联系的阐述及模糊 粗糙集( f u z z y r o u g hs e t ) 的概念，请参见文 1 0 1 2 。粗糙集和 证据理论也有一些相互交叠之处n ”，在实际应用中可以相互补充。 近年来，粗糙集理论开始逐渐应用到数据采掘的领域中，在对 大型数据库中不完整数据进行分析和学习方面取得了显著效果。如 使用粗糙集理论抽取聚类定义的符号规则“；空间数据处理“”1 等 等。很多学者针对p a w l a k 的粗糙集模型的不足也进行了各方面的扩 充，如z i a r k o 提出的变精度粗糙集模型“7 1 是对p a w l a k 粗糙集模型 的扩充，增强了对噪音数据的适用能力，适于处理实际应用中不精 塑翌奎兰堡主堂垡望苎 兰 确的数据。利用此模型，在建立专家诊断系统，规则推理，医疗数 据库上的知识发现等方面取得了很多研究成果“”1 。本文的数值实 验也是应用变精度粗糙集模型。 目前，粗糙集理论已成为信息科学最为活跃的研究领域之一， 它不仅为信息科学和认知科学提供了新的科学逻辑和研究方法，而 且为智能信息处理提供了有效的处理技术。 1 2 时态数据挖掘 在数据挖掘与知识发现中，实际的数据收集许多都与时间有关， 例如数据仓库的数据都有时间日志，研究销售、股票、气象、洪水 和地震等数据变化和知识发现的问题都与时间有关，因此必须研究 带时间约束的数据挖掘问题。我们把具有时间属性约束的数据称为 时态数据；将包含时态数据的数据库称为具有时态约束的数据库； 将在时态数据中进行知识发现的过程称为时态数据挖掘。这里的时 间有多种概念解释：有效时间，交易时间，事件时间等等。时态数 据中包含的时间属性可以是以上一种时间，也可以是以上几种时问 的组合。时间属性能利用1 n f 范式并入数据元组中。时刻、时间间 隔、时刻点的集合都能用来作为一个时间戳去表示事件的时间参数。 1 2 1 时态数据挖掘的研究现状 近年来，时态数据挖掘研究主要有几个重要方面，包括趋势分 析、相似搜索、与时间有关数据的序列模式挖掘和周期模式挖掘等 方面。本节首先对这几个方面进行介绍。 1 趋势分析 目前一般有四种主要的变化用于特化时态数据。 长期或趋势变化：它用于反映一般的变化方向，其时序图是在 较长时间间隔上的数据变化。这种变化反映为种趋势线或趋势曲 线。 循环变动或循环变化：主要是指循环性，即趋势线或曲线在长 期时间内呈摆动迹象。它可以是也可以不是周期性的。即在等时间 间隔之间，循环不需要沿着同样的模式演进。 季节性变动：它反映的是每年都重复出现的事件，如春节前过 年物资的销售会突然增加很多。换句话说，季节性变动是指同一或 湘潭大学硕士学位论文 n 近似同一的模式，在连续几年的有关月份期间重复出现。 非规则性或随机变化：它反映的是随机或者偶然事件引起的零 星时序变化。如火灾、瘟疫或劳工纠纷等。 t i ms h i m e a l l s d p h i lw i l l i a m s 对于计算机网络信息安全进行了 趋势分析【2 】i ，并将趋势进行了分类：内因和外因趋势、时态趋势、 空间趋势、关联趋势和混合趋势。并且对于不同的趋势分析类型介 绍了趋势分析的方法。 通常，对于趋势进行估计有三种曲线拟合方法： 加权移动平均方法【2 2 j ：采用合适的阶的移动平均，来消除循 环，季节性和非规则的模式，而只保留下趋势变化。 自由方法f 2 3 j ：它是基于用户的判断画一条近似曲线或直线去 拟合所给出的一组数据。这一方法的代价很大，且只对大规模数据 挖掘才可靠。有效性和质量就完全依赖个人的判断。 最r b - - - - 乘方法1 2 叼：将以最佳的拟合曲线c 作为最小二乘曲线， 即曲线具有最小的了7 d i ，其中偏差是指点 毛m 的值y i 为对应曲线 c 的值之间的差值。 2 相似搜索 数据库查询要求找出与查询要求精确匹配的数据，而相似搜索 是发现那些与查询序列轻微不同的数据序列瞄j 。给定一个时态数据 序列，相似搜索问题就是发现所有与要查询的序列相似的时态数据 序列。 在具有时态约束的数据库中进行相似搜索，通常使用欧氏空间 距离作为相似性计算的依据。两种常用的数据独立转换有：离散傅 立叶转换( d f t ) i 硐和离散小波转换( d w t ) 2 7 1 。 3 序列模式挖掘 序列模式f 2 8 1 挖掘是指挖掘相对时间或其他模式出现频率高的模 式。由于许多商业交易、天气数据和生产过程都是时间序列数据， 在针对目标市场、客户吸引、气象预报等的数据分析中，序列模式 挖掘是很有用途的。对序列模式挖掘，存在一些参数，其取值如何 将严重影响挖掘结果。第一个参数是时间序列的持续时间乃第二个 参数是时间重叠窗口( e v e n tf o l d i n gw i n d o w ) w ；第三个参数是被发 现的模式中时间之间的间隔m f 。 4 周期挖掘 塑要查兰堡主兰堡堡兰皇 周期分析是指对周期模式的挖掘，即在时态数据中找出重复出 现的模式。周期模式挖掘可视为组分片序列为持续时间的序列模 式挖掘2 9 1 。 周期模式挖掘的问题可以分为三类： 挖掘全周期模式。这里每一时间点都影响着时态数据上的循环 行为。如一年中的每一天都对一年中的季节循环起着作用。 挖掘部分周期模式。它描叙在部分时间点上的时态周期。部分 周期是一种比全周期较为松散的形式，在现实世界也更为常见一些。 挖掘循环或周期关联规则。这种规则是周期出现的事件的关联 规则。 全周期分析的技术已在信号分析和统计中得到研究。但全周期 模式挖掘的大部分方法不适用于部分周期模式挖掘，或者是代价太 大，原因是部分周期模式在同一周期内混杂有周期事件和非周期事 件。 另外，国内外很多专家在时间序列模式发现 4 3 埘】，多时间粒度 的知识发现【3 8 捌】，时态约束的关联、周期【4 0 枷】等方面作了大量研究， 将时态数据挖掘的研究工作引入更深更广的领域，取得了大量的研 究成果。 1 2 2 粗糙集在时态数据上应用的研究现状 用粗糙集理论来分析时态数据，目前取得了一些成果。文 3 1 提出了实时时态逻辑的框架，使用事件变量来表示时态序列。文 3 2 使用动态编程方法来检测时间序列的模式。文 3 3 使用粗糙集利用 动态约简对市场数据进行了分析，取得了成功。文 3 4 3 5 对加拿 大的股票数据进行了分析，提出了将时间序列到传统信息系统的转 换的思想。文 3 6 提出了时序信息系统和实施时序信息系统的概念， 并将文 3 4 3 5 中的时间序列转换为信息系统思想进行了形式化。 文 3 7 3 将文 3 6 提出的思想进行了形式化表示。 在利用粗糙集处理时态数据时，以往的研究主要关注被挖掘的 时态数据的时间序列( t i m es e r i e s ) 特征，即对象之间保持着严格的 时间顺序。时间序列信息分两类1 3 0 1 ，一是不带有实时约束的时间序 列；另一种是带有实时约束的时间序列。不带实时约束的序列可以 看成是按时间排列的时间串，事件之间的时间间隔( 采样速率) 是常 数；而对带有实时约束的时间序列，必须考虑事件之间的时间间隔， 塑翌查兰堡主堂垡丝茎! 这些时间间隔可能是很不一样的。 对时间序列的很多研究，一般的目的是根据傅里叶序列或概率 分布建立信号模型。另一个重要方面是时序推理，使用时序逻辑建 立实时序列模型。这些研究的着重点在于数据间的顺序和时间间隔， 认为时态数据集与一般数据集之间的最大区别在于时间维，因此关 键是把时态数据集转换为粗糙集能够处理的数据集。为此，在信息 系统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 l i n f o r m a t i o n s y s t e m ) 和实时时序信息系统 r t t i s ( r e a lt i m et e m p o r a li n f o r m a t i o ns y s t e 曲【3 6 】，目的是将对 象的顺序( 或次序) 信息形式化。 时序信息系统t i s 定义为： s t = ( u r u 匾t ，i ) 式中【卜一对象集( 案例，状态，疾病，观测，) ； 卜属性( 特征，变量，特点，条件，) ； 卜决策属性，d c - a ； r 序列属性，f 毛4 ； _ 序列属性，上的个次序关系，且= “) ，) ：五y n a n d z 叫) 实时时序信息系统r t t i s 定义为： a ，。= ( uru 西万) ， ) 式中【卜对象集( 案例，状态，疾病，观测，) 只属性( 特征，变量，特点，条件，) d 决策属性，d 岳爿 r 序列属性，f 丘4 序列属性t 上的一个次序关系，且 = y ) ：五y e n a n d x y 巧时间属性，占刮，占如) 表示自对象肋e u 发生以来到 砣u 发生的时间，这里 & j ) ，并且不存在y e u ，满足( 诊 x j ) ( k x 2 ) 如此，问题就变成了将t i s 转换为i s ，或将r t t i s 转换为t i s ， 再转换为i s 。经过转换后时态数据集中的数据对象之间没有了严格 的时间顺序性，适合用粗糙集理论进行处理。 虽然粗糙集理论在时态数据集上的应用有了以上的研究和成 果，但已有的研究都是着眼于时态数据在时间上的顺序性，通过转 塑翌查堂堡主堂堡堡兰 ! 换，消去时态数据的时问属性，再用已有的粗糙集理论对数据集进 行处理。本质上没有充分利用时态数据在时间上的其它特点和性质， 对其进行更深层次的挖掘，改进挖掘的效率和质量。 因此，我们希望能对时态数据建立一种比较规范系统的模型进 行研究，建立时态粗糙集模型，将时态数据的时间属性不仅仅看作 数据对象间的序列参数，而是对时间的性质进行研究，达到描述不 同时间粒度下的周期、趋势等知识的效果。 1 3 本文研究内容 本文主要研究的内容如下： 1 、时态数据的概念、定义和各种性质，在实际应用中如何体现， 以便加以利用。 2 、采用什么知识表达方式，以方便粗糙集理论进行时态数据挖 掘。 3 、研究了时态知识表达系统的周期性，多时间粒度性。 4 、研究了应用粗糙集在时态决策表上进行多时间粒度周期模式 挖掘各个环节的算法。 我们获得以下几个主要成果： l 、本文提出了“时态关系式”和“时态关系模式”，目的是在 实际应用中建立一个转换的机制，使一般的带时间属性的数据表能 够体现时态的性质，以利于时态挖掘。 2 、针对粗糙集理论在知识获取上的特点，提出了“时态知识表 达系统”，这样粗糙集能在这个知识表达系统上对时态数据进行挖 掘。 3 、给出了粗糙集在时态决策表上进行挖掘的各个环节的算法。 下面介绍本文以后各章节的安排： 第二章介绍粗糙集理论的基本概念、定义、性质和相关的定理。 第三章介绍了时态的基本概念、定义、性质；提出了时态关系 式，时态关系模式；并在此基础上提出了时态知识表达系统，并研 湘潭大学硕士学位论文9 究了它的周期性，多时间粒度性；给出了设定“时态关系模式”应 遵循的规则； 第四章给出了粗糙集在时态知识表达系统上时态数据挖掘的各 个环节的算法。 第五章应用三、四章提出的理论和算法，对车流量统计数据进 行了挖掘。并对结果作出了分析总结。 在总结和展望中，对本文所做的一些工作进行了总结和展望。 最后是参考文献、攻读硕士期间公开发表的论文及致谢。 斓潭大学硕上学位论文 第二章粗糙集理论 本章介绍了粗糙集理论的基本概念、性质和特点，也介绍了 p a w l a k 粗糙集模型的扩充一变精度粗糙集模型。在以后的章节中都 要用到这些知识。 2 1 知识表达 知识表达是智能信息系统的关键。所谓知识获取，就是要从大 量的原始数据信息中分析发现有用的规律信息，即将知识从一种原 来的表达形式( 原始数据表达形式) 转换为一种新的目标表达形式 ( 人类或者计算机便于处理的形式) 。基于粗糙集的理论的知识发 现，主要是借助于信息表这样一种有效的数据表知识表达方式。 2 1 1 知识的分类概念 通常，我们对现实问题进行处理的时候，会将我们讨论的现实 个体( 或称元素、对象、样本) 局限在某一个特定的区域范围之内。 这个区域内的所有个体就组成问题的论域u 。以分类为基础，可以将 分类理解为等价关系，而这些等价关系对论域u 进行划分。对于论 域中由等价关系划分出的任意子集x ，都可以称之为u 中的一个概 念。这里，我们认为空集中也是一个特殊的概念。论域u 中的任意 概念族称为关于u 的抽象知识，简称为知识，它代表了对u 中个体 的分类。这样知识就可以定义为：给定一组数据( 集合) u 和等价关 系集合r ，在等价关系集合r 下对数据集合u 的划分，称为知识，记 为u r 。u 上的一簇划分( 对u 的分类) 称为关于u 的知识库。关于 u 的一个知识库也可以理解为一个关系系统，其中u 为论域，r 是u 上的一簇等价关系，根据这些等价关系就可以对u 进行不同的划分 ( 知识) ，每种划分将把u 分为不同的子集( 概念) 。 设u 是一个论域，r 是u 上的个等价关系。u r 表示u 上由r 导出的所有等价类。 x ，表示包含元素x 的r 的等价类，x u 。一 个知识库就是个关系系统k = u ，p ，其中u 是论域，p 是u 上的一 湘潭大学硕士学位论文1 1 个等价关系簇。如果q c _ p 且q o ，则n q ( q 的所有等价关系的交) 也是一个等价关系，记作i n d ( q ) 。 2 1 2 信息表知识表达系统 知识表示就是要研究用机器表示知识的可行的、有效的、通用 的原则和方法。本节我们介绍基于信息表的知识表达形式，它是粗 糙集理论中对知识进行表达和处理的基本工具。 在人工智能研究中，一个实例经常使用属性一值对的集合来表 示，实例集就是这样的实例集合，记为u 。u 可被划分为有限个类x ， x 2 i 一，x 一，使得 x ；_ c u ，x ，o ，x j n x 产中( i j ) ，( i ，j = 1 ，2 ，n 且n x ，= u ) 。 信息表知识表达系统的基本成分是研究对象的集合，关于这些 对象的知识是通过指定对象的属性( 特征) 和它们的属性值( 特征 值) 来描述的。一般地，一个信息表知识表达系统i s ( i n f o r m a t i o n s y s t e m ) 可以表示为 s = t u r ，v ? f ) 式中 泸一对象集( 案例，状态，疾病，观测，) 肝一f u 刀子集c 和d 分别称为条件属性集和结果属性集 胪一uk 是属性值的集合，k 表示属性r e r 的属性值范围，即 属性r 的值域 产一，x 片一矿是一个信息函数，它指定中每一个对象j 的 属性值 为了直观方便，u 也可以写成一个表，纵轴表示实例标记，横轴 表示实例属性，实例标记和属性的交会点就是这个实例在这个属性 的值。这个表称为信息表，是表达描述知识的数据表格。 对于每个属性子集b c r ，我们定义一个不可分辨二元关系( 不 分明关系) i n d ( b ) ，即 i n d ( b ) = f ( x ，y ) f ( x ，y ) u 2 ，v b b ( b ( x ) = b ( y ) ) ) 。 每个子集b c r 也可称为一个属性，当b 是单元素集时，称b 为 原始的，否则称b 为复合的。属性b 可以认为是用等价关系( 在该 属性上的取值相等) 表示的知识的一个名称，称为标识属性。一个 表可以看作是定义的一个等价关系簇，即知识库。 实际上，信息表这种数据表格知识表达系统是对客观对象的描 湘潭大学硕士学位论文1 2 述和罗列，表达的是属于说明性的指示。当信息表包含的数据足以 反映论域的时候，通过属性所对应的等价关系就可以体现论域中的 过程知识，即概念之间的逻辑关系或规则知识。事实上，从信息表 所表述的说明性知识中发现过程性知识( 规则知识) 就是知识发表 的研究内容。下面我们来看两个信息表知识表达系统的例子。 表2 1 样本集颜色( r 。)形状( r 2 )大小( r 3 ) x lr e dr o u n ds a m l l x 2b l u e s q u a r el a r g e x 3r e d t r i a n g u l a r s a m l l x b l u e t r i a n g u l a rs a m l l x 5y e l l o wr o u n ds a m l l x 6y e l l o w s q u a r e s a m l l x 7r e d t r i a n g u l a rl a r g e x 8y e l l o w t r i a n g u l a rl a r g e 例2 1 表2 1 给出了一个关于玩具积木的信息表。 根据这个信息表，我们可以得出有关的概念描述，如将玩具积 木按照颜色、形状和大小可以分别进行如下分类，得到有关玩具积 木的概念知识： u r l = “x - ，x 3 ，x 7 ) ， x 2 ，x 4 ) ， x 5 ，x 6 ，x 8 ) ) ； u r 2 = “x l ，x 5 ) ， x 2 ，x 6 ) ， x 3 ，x ，x 7 ，x 8 ”； u 心= “x 1 ，x 3 ，x t ，x 5 ，x 6 ， x 2 ，x 7 ，x 8 。 这里，信息表中所包含的属性集只有对对象( 积木) 进行描述 的属性。 例2 2 如表2 2 所示的信息表，表示了流感病例的数据信息。 表2 ，2 个体编号头疼肌肉疼体温流感 e i是是正常否 e 2是是高是 e 3是是很高是 e 4否是正常否 e s否否局否 e b否是很高是 塑翌查兰堡主竺垡笙兰 ! ! 有的病例属于流感，有的不是。论域u = e 。，e ：，e 。，e 。，e ；，e 。) ，它 的属性集可以分为条件属性集c = 头疼，肌肉疼，体温) 和结果属性 集d = 流感 ，属性头疼的值域是( 是，否 ，肌肉疼的值域是( 是，否 ， 体温的值域是 正常，高，很高 ，信息函数将每个对象的属性取值 映射到具体的属性之上，如 f ( e 。，头疼) = “是”， f ( e 。，体温) = “高”， 从表2 2 可以看出，条件属性和结果属性之间还存在一定的关 系，如当肌肉疼的属性值为“否”的时候，流感的属性值肯定是“否”， 这可以形成诸如规则等形式的过程性知识。 2 1 3 决策表 决策表是一类特殊而重要的知识表达系统，也是一种特殊的信 息表，它表示当满足某些条件时，决策( 行为、操作、控制) 应当 如何进行，决策表的定义如下： 定义2 - 1 1 “铂一个决策表是一个信息表知识表达系统s = ( 口冠 kf ) ，r = c u d 是属性集合，子集c 和d 分别称为条件属性集和结 果属性集，d 条件属性c 和结果属性d 的等价关系i n d ( c ) 和t n d ( d ) 的等价类 分别称为条件类和决策类。 一个决策表中的结果属性有时是唯一的，称为单一决策；有时 是不唯一的，称为多决策。对于具有多个结果属性的决策表，文 4 7 有两种方法将其变换成为单一决策的决策表。本文所谈论的决策表 都为单一决策。 2 2 粗糙集理论 粗糙集理论的研究已经历了1 0 多年的时间，无论是在系统理论、 计算模型的建立和应用系统的研制开发上，都已取得了很多成果， 也建立了套较为完善的粗糙集理论体系。下面我们对粗糙集理论 进行介绍。 2 2 1 粗糙集的基本概念 现实世界中的信息，通常可以用一个信息表来表示。信息表中 的每一行称为一个实例( 实体、对象) ，实例的性质是通过一些变量 塑璺查兰堡主兰堡笙苎 ! 兰 的赋值体现出来的。如上一节所述，样例的属性集可以分为条件属 性和结果属性( 决策，也称决策属性) 。上一节介绍的不分明关系是 粗糙集理论的一个关键概念，它通常是和一个属性集合联系在一起 的。 表2 3 条件属性 个体编号决策 头疼肌肉疼体温 e i是是正常否 e 2是是高是 e a是是很高是 e 4否是正常否 e 5否否高否 e 6否是很高是 例如，在表2 3 中，考虑条件属性头疼和肌肉疼。对于e 。，e 。， e a 这三个实例，其条件属性头疼的值都是“是”，条件属性肌肉疼得 值也都是“是”，因此从条件属性头疼和肌肉疼的角度来看，这三个 实例是不可分辨的。同样e 。，e 。在这两个属性上也是不可分辨的。 由此构成的不分明集fe 。，e 。，e 。) ， e 。，e 。 和 e 。 被称为基本集。 任意有限多个基本集的并被称之为可定义集。 定义2 2 1 h 铂令x u ，当x 能用属性子集b 确切地描述( 即是 属性子集b 所确定的u 上的不分明集的并) 时，称x 是b 可定义的， 否则称x 是b 不可定义的。b 可定义集也称作b 精确集，b 不可定义 集也称为b 非精确集或b 粗糙集( 简称粗糙集) 例2 3 在表2 3 所示的决策表中，集合 e 。，e 。，e 。，e s 就是 条件属性集合b = 头疼，肌肉疼) 不可定义的，是b 粗糙集，因为根 据条件属性子集b ，样例e 。，和e 。，e 。是不可分辨的，e 。和e e 是不可 分辨的。我们不能根据条件属性子集b 来对所有实例是否属于集合 e 。，e e ，e 。) 作精确判定。但是，如果样例的属性取值是头疼= “否”，肌肉疼= “否”，则我们可以确定地说该样例属于集合 e z ， e 3 ，e ，e 5 ) 。 从例2 3 可以看出，对于一个样例子集，也称为一个概念，根 据一个条件属性子集所确定的不分明关系，我们有可能能够准确地 判定一些样例是否属于该概念，也有可能不能够判定某些样例是否 湘潭大学硕士学位论文1 5 属于该概念。为了描述这个问题，粗糙集理论采用了上近似集、下 近似集的概念。 定义2 2 2 “”对每个概念x ( 样例子集) 和不分明关系b ，包含 于x 中的最大可定义集和包含x 的最小可定义集，都是根据b 能够 确定的，前者称为x 的下近似集( 记为b 一( x ) ) ，后者称为x 的上近 似集( 记为b 一( x ) ) 下面是上近似集和下近似集的形式化定义。 定义2 2 3 h ”给定知识表达系统乒( 彰冠巧f ) ，对于每个 子集x c _ u 和不分明关系b ，x 的上近似集和下近似集分别可以由b 的基本集定义如下： b 一( 劢= u e i ( 丘纠i n d ( 助) 八只e 脚； b 一( = u 只f ( e e 叫i n d 国) 八只n 彤函 ， 其中，纠i n d ( 窃= x l ( 埏u a v x v y v 6 ( 6 ( 曲= 6 ( 力) ) ) 是不分明关系 b 对u 的划分，也是论域u 的b 的基本集的集合 定义2 2 4h 7 1 集合b n 。( 劢= b 一( 劢b 一( 劢称为x 的b 边界： p o s 。( = b - ( 称为x 的b 正域；n e g b ( 彩= 从b - ( 称为x 的b 负域 例2 4 在表2 3 所示的决策表中，对于属性子集b - 头疼，肌 肉疼 ，集合x = fe 。，e 。，e 。 是一个b 粗糙集，下面分别计算集合x 的上近似集、下近似集、正域、边界域。 首先计算论域u 的所有b 基本集， 纠i n d ( 曰= e 。，e ：，e 。) ， e 。e 。) ， e 。) ， 令b ，= e ，e 。，e 3 ) ，b 2 = f e 。，e 6 ，b 产 e s ，集合x 与基本集有如下关 系： x n b l = e 2 ，e 3 m ， x n b 2 = 中， x n b 。= b 。= e 。 中。 由此可以的集合x 的上近似集、下近似集、正域、边界域： b 一( = b lu b 2 = e l ，e 2 ，e a ，e b j ， b 一( = b 3 = e 5 j ， p o s 。( = b 一( = e s ， b n b ( 国= b i = e i ，e 2 ，e 3 。 2 2 2 属性的重要性 湘潭大学硕士学位论文1 6 定义2 2 5 “玎设集合簇f = x ，x ：，x 。) ( u = 0 x ；) 是论域u 上定 义的知识，b 是一个属性子集，定义b 对f 近似分类的质量f b ( f ) 为： r b ( f ) = 妻| b ( 鼢i l 叫 c - 1 b 对f 近似分类的精度描述的是当使用知识b ( 属性子集b ) 对 对象进行分类时，在所有可能的决策中确定决策所占的比例；b 对f 近似分类的质量是应用知识b 对对象进行分类时，能够确定的决策 的对象在论域中所占的比例。 利用粗糙集，根据知识b 对集合簇f 近似分类的质量r b ( f ) 这 概念，我们可以对属性的重要性进行度量，这个度量是根据论域中 的样例来得到的，不依赖于人的先验知识。 定义2 2 6h ”对于f 是属性集d 导出的分类，属性子集b 在属 性集b 中的重要性( b 。_ c b ，如果属性集b 是默认的，如b 为条件属 性全集，则可简称为属性子集b 的重要性) 定义为 r b ( f ) 一r 。a ，( f ) 这表示当我们从属性集b 中去掉属性子集b 。对f 近似分类的质 量影响。 2 2 3 属性约简 我们在2 1 3 节中讨论了决策表，决策表的条件属性集合p 形 成对论域u 的划分u p ；同时，决策属性集也对论域形成一个划分 o d 。这两个划分形成了条件属性和决策属性在对论域样本分类上的 知识。属性约简的目的就是要从条件属性集合中发现部分必要的条 件属性，使得根据这部分条件属性形成的相对于决策属性的分类和 所有条件属性形成的相对于决策属性的分类一致，即和所有条件属 性相对于决策属性有相同的分类能力。这就是相对约简的概念。 定义2 2 7h 7 1 设u 是一个论域，p 和q 是定义在u 上的两个等 价关系簇，q 的p 正域记为p o s ，( q ) ，定义为 p o s r ( q ) = u p x ) x e u ，q 定义2 2 8 “7 1 设u 是一个论域，p 和q 是定义在u 上的两个等 价关系簇，若p o s ，( q ) = p o s