（计算机应用技术专业论文）基于粒计算的海量数据挖掘算法研究.pdf

重庆邮电大学硕士论文摘要 摘要 数据挖掘是从大量的数据中挖掘出有用的或者人们感兴趣的知识的一种方法。 然而随着互联网及数据库技术的不断发展，处理海量数据已经成为数据挖掘领域 所要解决的一个重要课题。粗糙集理论，是一种处理不完备和不确定知识的软计 算工具。它能有效地分析和处理不精确、不一致、不完整等各种信息，并从中发 现隐含的知识，揭示潜在的规律。近年来在数据挖掘等多个领域得到广泛应用。 粒计算是一种新的智能信息处理理论。现己成为国际上人工智能研究的主要方法 之一。对于粒计算的研究，很大程度上是因为它模拟了人脑认识和解决问题的过 程。采用粒计算思想的很多理论已经被广泛地应用于机器学习、数据挖掘等领域， 并被证明是有效的求解问题的方法。 s m l g r c 算法把传统的r o u g hs e t 算法引入到粒计算理论中，并使得算法所获 取的规则相对较短。但是该算法却无法处理海量数据集。为了解决这个问题，并 且通过对信息表分层粒化模型的分析，一种粒分布链表在本文中被提出。结合成 熟的数据库技术，为分层粒化模型中的粒子生成粒分布链表，解决了s m l g r c 算法 在处理海量数据时的内存限制问题。同时，样本覆盖因子的概念也在本文中被提 出，该因子用来控制算法生成规则，它可以有效的避免冲突规则的产生，并且只 有在产生冲突规则时起作用。改进的算法在不影响原算法有效性的基础上可以很 好的适用于海量数据集。一系列的实验测试证实了该方法的有效性。 关键词：粒计算，r o u g hs e t ，粒分布链表海量数据，可伸缩性 重庆邮电大学硕士论文 a b s t r a c t d a t am i n i n gi sap r o c e s st oe x t r a c ti n t e r e s t i n ga n du s e f u lk n o w l e d g ef r o md a t as e t s a n df o l l o w i n gt h ed e v e l o p m e n to fi n t e r n e ta n dd a t a b a s et e c h n o l o g y , p r o c e s s i n gh u g e d a t as e t sh a sb e e na ni m p o r t a n tt o p i ci nd a t am i n i n g r o u g hs e tt h e o r y , i sat o o lf o r d e a l i n gw i t l li n c o m p l e t ea n du n c e r t a i ni n f o r m a t i o n i ti se f f i c i e n tt oa n a l y z ep r o c e s sa n d a c q u i r ep o t e n t i a lk n o w l e d g ef r o mi m p r e c i s e ，i n c o n s i s t e n ta n di n c o m p l e t ed a t as e t s r o u g hs e tt h e o r yh a sb e e ns t u d i e da n da p p l i e di nd a t am i n i n ga n dm a n yo t h e rf i e l d s g r a n u l a rc o m p u t i n g ( g r c ) i sa ne m e r g i n gt h e o r yb a s e do nt h eu 辩o fg r a n u l e si n p r o b l e ms o l v i n ga n di n f o r m a t i o np r o c e s s i n g t h er e s e a r c ho ng r a n u l a rc o m p u t i n g , t oa g r e a te x t e n t , s i m u l a t e st h ep r o c e s si nw h i c hh u m a nb r a i nu n d e r s t a n d i n ga n ds o l v i n g p r o b l e m s m a n yt h e o r i e se m p l o y i n gt h ei d e ao fg r ch a v eb e e nw i d e l ya p p l i e di n m a c h i n el e a r n i n g , d a t am i n i n ga n do t h e rf i e l d s w h i c hh a v eb e e np r o v e d 私e f f i c i e n t w a y sf o rp r o b l e ms o l v i n g s m l g r c a l g o r i t h mi n t r o d u c e sg r ct oc l a s s i cr o u g hs e ta l g o r i t h m , a n dm a k e st h e l e n g t ho f t h er u l e sr e l a t i v e l ys h o r t ，b u ti tc a l ln o tp r o c e s sm a s sd a t a s c t s i no r d e rt os o l v e t h i sp r o b l e m ，b a s e do nt h ea n a l 蜘so ft h eh i e r a r c h i c a lg r a n u l a rm o d e lo fi n f o r m a t i o n t a b l e ，t h em e t h o do fg r a n u l a rd i s t r i b u t i o nl i s t ( g d l ) i si n t r o d u c e dt og e n e r a t eg r a n u l a r , a n dt h eg r a n u l a rc o m p u t i n ga l g o r i t h m ( s l m g r c ) i si m p r o v e d s a m p l ec o v e r e df a c t o r ( s c f 3i sa l s oi n t r o d u c e dt oc o n t r o lt h eg e n e r a t i o no f r u l e sw h e nt h ea l g o r i t h mg e n e r a t e s c o n f l i c t e dr u l e s t h ei m p r o v e da l g o r i t h mc a np r o c e s sm a s sd a t a s e t sd i r e c t l yw i t h o u t i n f l u e n c i n gt h ec o r r e c t i o nr a t eo ft h es u g 疋e x p e r i m e n t sd e m o n s t r a t e st h ev a l i d i t y o f o u rm e t h o d k e yw o r d s ：g r a n u l a rc o m p u t i n g ，r o u g hs e t ，g r a n u l a rd i s t r i b u t i o nl i s t ，n 均s sd a t a m i n i n g ，f l e x i b i f i t y 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及 取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论 文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重庆 邮虫太堂或其他教育机构的学位或证书而使用过的材料与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 贰 学位论文作者签名： 2 拐签字日期：刀 7 年莎月p 日 学位论文版权使用授权书 本学位论文作者完全了解重麽邮电太堂有关保留、使用学位论 文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权重废邮电太堂可以将学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等 复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：卫屿 签字日期：7 n 7 年6 月髟同 聊躲研 签字日期：砷年彳月g 日 重庆邮电大学硕士论文 第一章绪论 1 1 引言 第一章绪论 数据挖掘，又称数据库中的知识发现，是一个从大规模数据库中的数据中抽取 有效的、隐含的、以前未知的、有潜在使用价值的有用信息的非平凡过程，它是 当今众多学科领域特别是数据库领域最前沿的研究课题之一【l l 。数据挖掘是- - 1 1 交 叉学科，它把人们对数据的应用从低层次的简单查询，提升到从数据中挖掘知识， 提供决策支持，它汇聚了不同领域的研究者，尤其是数据库技术、人工智能技术、 数理统计、可视化技术、并行计算等方面的学者和工程技术人员，投身到数据挖 掘这一新兴的研究领域，形成新的技术热点。 海量数据只是个相对的概念。从以往研究人员的试验数据可知，这里的大量其 实只是很少的一部分数据量，从几十条几百条数据到几万条数据。对于如何界定 海量数据与传统数据挖掘定义中的大量数据，现在还没有一个明确的概念。 海量数据是一个形容词，它是用来形容巨大的、空前浩瀚的数据，我们这里所 指的海量数据已经达到了上百万条、上千万条甚至更多。广义上来说，海量数据 可指驻存在整个互联网上或分布于不同主机上的相关数据。狭义上来说，也可指 驻存在单机上的海量数据。传统的数据挖掘算法都是假设输入内存的数据只有相 对少的记录。但是由于内存容量的限制，当系统无法一次性把所有需分析的数据 调入内存时，就会严重降低算法的性能，甚至得不到预期的结果。因此，要使挖 掘算法在挖掘海量数据时更有效率，就必须使其具备良好的可伸缩性【2 j 。此外，对 于海量数据而言，算法的空间可伸缩性比时间效率更为重要p j 。 1 2 海量数据挖掘现状 近十几年，随着互联网及数据库技术的飞速发展，各个领域数据也日益增长， 如人类对太空的探索数据，银行每天的巨额交易数据。面对不断增加如潮水般的 数据，人们不再满足于数据库的简单查询功能，提出了深层次问题：能不能从数 据中提取有用的信息或者知识为决策服务，从而孕育了数据挖掘技术的诞生，然 而随着数据的不断增加，传统的数据挖掘技术已不能适应，因此，如何解决数据 挖掘过程中空间及时间的可伸缩性己经成为数据挖掘领域中亟待解决的难题。 数据挖掘作为一门处理数据的新兴技术，它许多的新特征。首先，它面对的是 重庆邮电大学硕士论文 第一章绪论 大量的数据；其次，数据可能是不完全的、有噪声的、随机的，并且有复杂的数 据结构，维数大。最后，数据挖掘是许多学科的交叉，运用了统计学，计算机， 数学等学科的技术。海量数据挖掘除了继承数据挖掘的上述特点外，它主要以解 决传统数据挖掘算法无法适应更大数据的局限性为目的。 1 2 1 海量数据挖掘技术 关于海量数据挖掘很早就有研究，人们首先考虑的是如何直接对整个海量数据 集进行处理。1 9 9 1 年c a r l e t t 提出了一种r a n d o ms a m p li n g 4 1 的方法来处理大数据 量问题，但是能处理的最大数据量也只有3 2 0 0 0 条。现有的海量数据挖掘技术除 了改进传统的算法，使其具有更好的伸缩性外，同时很多其他领域的方法也被引 进来处理海量数据，并取得了很好的效果。 1 数据集约简 很多传统的数据挖掘算法都会假设输入内存的数据只有相对少的记录，因此当 数据不断增多，无法一次性输入内存时就无法处理。我们可以通过数据集约简的方 法，减少输入内存的数据量，也可以说减少需要分析的数据量以此来解决内存 的限制问题，提高算法的可伸缩性。 现有的数据集约简技术主要有： 抽样：抽样是被公认的和广泛使用的统计技术，通过对数据集进行有效的 抽样的分析可以得出全局结论。因此，当我们面对海量数据时，有时对所 有的数据进行分析是不可能的也是没有必要的，只要在理论的指导下进行 合理的抽样同样可以取得很好的效果。但是这种方法会在一定程度上损失 算法的正确性。 数据集分割：数据集分割就是把整个数据集分割为若干个可调入内存的子 集，分别求出各子集的局部频繁模式，所有局部频繁模式的并集为全局频 繁模式的候选集，然后再扫描整个海量数据集，最终求出全局频繁模式集。 但是，当各个数据子集中挖掘出来的局部模式和规则合并在一起时的规模 超出内存的容量时，结果会使得算法彻底崩溃。 数据集削减：数据集削减就是把基于辅存和基于内存的挖掘结合起来，用 基于辅存的挖掘来缓和算法对内存的限制。 信息论方法：由信息熵的定义可知，利用某一属性列的值确定分类标准列 在值具有较高的可信度【5 1 。因此，在挖掘分类知识时，可以利用信息熵的 方法，从数据库中选择具有较大平均互信息量的属性列而把数据库中与 分类标准列无关的、或关系不大的那些属性列去除，就u r 以降低数据库的 重庆邮电大学硕士论文 第一章绪论 维数，从而加速知识发现的过程。 2 分布式数据挖掘( d d m ) 分布式数据挖掘就是将分布在各个节点机上的数据分别进行分析后整合最后 规则，这样就可以有效的解决数据挖掘算法在处理海量数据时内存限制问题。同 时，各个节点可以使用不同的挖掘算法并行的进行挖掘，挖掘的同时也不需要与 其他节点机相互通信，因此其所耗时间相对较小。现在已经有很多改进的算法用 以处理分布式的海量数据，如【4 扣1 1 j 。 分布式数据挖掘具有高并行性能、低通信负载和处理速度快等优点。分布式算 法具有高度的适应性、可伸缩性、低性能损耗和容易连接等特性，可以很好的处 理分布式数据源。一个典型的分布式数据挖掘模型如图1 1 ： 数据源数据源数据源 图1 1 分布式数据挖掘典型模型 此外，在很多情况下，分布式挖掘的思想也适用于把一个原始的存储海量数据 的数据库进行分割后放到不同的处理器上进行分析。这种情况与经典的分布式数 据挖掘的唯一区别就是首先要对数据库进行分割，因此分割算法的好坏直接影响 着整个数据挖掘算法的有效性。当分割数目比较大时，因为分割后的数据子集包 含的样本相对与海量数据集太小而不会产生理想的效果。此外，分割过程中所造 成的信息遗损在后继的分布式处理及整合局部模型中都无法弥补，因此分割算法 的设计在处理这种情况下的分布式海量数据挖掘上具有十分重要的意义。这种分 重庆邮电大学硕士论文 第一章绪论 布式挖掘方法一般分为以下三个步骤： 数据分割：通过特定的数据分割算法将父数据集分割成为许多个空间上独立的 子数据集。一般来说，分割后会丢失一部分信息，因此在分割的时候如何使重要 的信息保留下来成为数据分割算法主要考虑的问题。此外还要考虑子数据集间的 负载平衡。 规则生成：各子数据集生成规则的过程是相互独立的，相互间不需要任何通信。 因此具有高并行性能以及通信费用低等优点。 组合规则：将所有的子规则集组合形成父规则集。 3 增量式数据挖掘 数据挖掘的过程是一个反复交互的过程，用户的本次要求往往与前次的要求有 较大的重复性，这种重复性主要表现在数据集的增量性及算法参数的相似性两个 方面，因此我们如果可以充分利用前次的挖掘结果来提高本次挖掘的效率，而不 是简单的将算法重新作用于整个数据库，就可以提高算法处理海量数据的性能。 同时，通过把当前的挖掘结果与历史的挖掘结果相比较可以得出迄今为止仍然有 效和感兴趣的知识，这种积累的时序知识也可以为用户提供一个数据规则的动态 描述。 4 决策树方法 决策树方法是数据挖掘的一种分类分析方法，它以特有的优点得到了最广泛的 应用：决策树分类的速度快；决策树模型简单，便于理解，能方便地转换为s q l 语句来实现；此外，相对于其他方法而言，决策树分类可以得到较高的精确度。 为了解决在处理海量数据时，传统的分类方法性能下降或精度降低等问题，i b m 研究人员最初提出了一种快速的、可伸缩的、适合处理较大规模的决策树分类算 法s l i q t l 2 】，该算法利用属性表、类表和类直方图3 种数据结构来构造树，在决策 树的构造阶段采用了预排序技术，并与宽度优先增长策略相结合。此外，在修剪 阶段，采用了基于最小描述长度的肋l 方法，时间开销小。但是，s l i q 算法要求 类表驻留内存，限制了s l i q 算法处理数据的最大规模。随后，i b m 研究人员又提 出了决策树分类算法s p r i n t t ”】，该算法消除了所有的内存限制，易于并行化，性 能较好，使用属性表和直方图两种数据结构对s l i q 算法进行了改进。实验表明， 当s l i q 的类表可以存放在内存的情况下，s l i q 的执行速度比s p r i n t 快，而当训 练集数据超过了s l i q 能承受的最大规模后，s p r i n t 的执行速度明显要比s l i o 快。 此外，研究人员还提出了c l o u l d s h 1 ，s c a l p a r c i ”i 等改进算法，他们都试图在 生成树的过程中减少算法与驻留磁盘中数据的i o 操作。之后，j g e h r k e 又提出 了针对大多数决策树生成算法框架r a i n f o r e s t ”】，此框架适用于大多数决策树算 法，并在很多场合的速度都超过了s p r i n t 算法。 4 重庆邮电大学硕士论文第一章绪论 5 其它方法 目前，除了上述介绍的方法外还有一些其他比较新颖的方法在处理海量数据时 也可以取得比较好的结果。如优化给定的数据和数学模型之间的适应性，改进传 统的挖掘算法【1 7 】；我国的何清、任力安、史忠植等研究人员提出了一种基于j o r d a n 曲线定理的分类超曲面的分类方法，有效的解决在有限区域分布很复杂的非线性 的海量数据库【1 8 】；把模糊集方法与关联算法结合起来从大型数据库中得出的关联 规则集完成个性化服务【19 l ；利用进化计算的方法，加速挖掘进程并构建了基于知 识的进化系统框架【2 0 j ；把智能“代理”方法与控制策略联系起来，对海量数据进 行有效的聚类【2 l 】等等。 1 2 2 海量数据挖掘功能 海量数据挖掘继承了数据挖掘的很多特点，因此它的功能和数据挖掘的功能相 同。数据挖掘综合了各个学科技术，有很多的功能，当前的主要功能如下： 1 分类 按照分析对象的属性、特征，建立不同的组类来描述事物。例如：银行部门根 据以前的数据将客户分成了不同的类别，现在就可以根据这些来区分新申请贷款 的客户，以采取相应的贷款方案。 2 聚类 识别出分析对内在的规则，按照这些规则把对象分成若干类。例如：将申请人 分为高度风险申请者，中度风险申请者，低度风险申请者。 3 关联规则和序列模式的发现 关联是某种事物发生时其他事物会发生的这样一种联系。例如：每天购买啤酒 的人也有可能购买香烟，比重有多大，可以通过关联的支持度和可信度来描述。 与关联不同，序列是一种纵向的联系。例如：今天银行调整利率，明天股市的变 化。 4 预测 把握分析对象发展的规律，对未来的趋势做出预见。例如：对未来经济发展的 判断。 5 偏差的检测 对分析对象的少数的、极端的特例的描述，揭示内在的原因。例如：在银行的 1 0 0 万笔交易中有5 0 0 例的欺诈行为，银行为了稳健经营，就要发现这5 0 0 例的内 在因素，减小以后纤营的风险。 需要i e 意的是：数据挖掘的各项功能不是独立存在的，在数掘挖掘中互相联系 重庆邮电大学硕士论文 第一章绪论 发挥作用。 1 2 3 海量数据挖掘应用 海量数据挖掘所要处理的问题，就是在庞大的数据库中找出有价值的隐藏 事件，并且加以分析，获取有意义的信息，归纳出有用的结构，用以作为企业进 行决策的依据。随着互联网及数据库技术的不断升级，数据量的不断增多，其应 用也越来越广泛。常见的应用案例多发生在零售业、制造业、财务金融保险、通 讯及医疗服务等等。 1 零售商从顾客购买商品中及购买能力等发现一定的关系，提供相应的打折 购物券等，提高销售额。 2 保险公司通过数据挖掘建立预测模型，辨别出可能的欺诈行为，避免道德 风险，减少成本，提高利润 3 在制造业中，半导体的生产和测试中都产生大量的数据，就必须对这些数 据进行分析，找出存在的问题，提高质量 4 电子商务的作用越来越大，可以用数据挖掘对网站进行分析，识别用户的 行为模式，保留客户，提供个性化服务，优化网站设计 5 医院对以往病例的分析，建立合理的医疗专家系统，可以有效的解决医院 就医中的很多麻烦，节约时间 6 通过对卫星从太空获取的数据进行分析，可以帮助我们更好了了解太空， 了解未知世界。 此外，还有很多公司运用数据挖掘的成功案例，显示了数据挖掘的强大生命力： 美国a u t o t r a d e r c o m 是世界上对大的汽车销售站点，每天都会有大量的用户 对网站上的信息点击，寻求信息，其运用了s a s 软件进行数据挖掘，每天对数据 进行分析，找出用户的访问模式，对产品的喜欢程度进行判断，并设特定服务娶， 取得了成功。 r e u t e r e s 是世界著名的金融信息服务公司，其利用的数据大都是外部的数据， 这样数据的质量就是公司生存的关键所在，必须从数据中检测出错误的成分。 r e u t e r e s 用s p s s 的数据挖掘工具s p s s c l e m e n t i n e ，建立数据挖掘模型，极大地 提高了错误的检测，保证了信息的正确和权威性。 b a s se x p o r t 是世界最大的啤酒进出口商之一，在海外8 0 多个市场从事交易， 每个星期传送2 3 0 0 0 份定单，这就需要了解每个客户的习惯，如品牌的喜好等， b a s se x p o r t 用i b m 的i n e e l 】i g e n tm i n e r 很好的解决了上述问题。 6 重庆邮电大学硕士论文第一章绪论 1 3 论文背景及工作内容 传统的数据挖掘算法大都要求一次性将所要分析的数据存入内存，然而随着数 据量的不断增加，很多时候都无法一次将所有数据存入内存，因此，如何解决内 存限制的问题，使得挖掘算法可以处理海量数据是当前数据挖掘领域中的一项重 要课题。在粗糙集理论研究中，覃政仁等提出了一种类分布链表田】( c d l ) ，它有 效的利用了数据库技术，很好的解决了传统的粗糙集算法在处理海量数据时的限 制。此外，覃政仁等还提出了一种基于r o u g hs c t 的海量数据分割算法田】。该算法 利用r o u g hs e t 的特点提出最佳分割的定义将一个原始的海量数据集分割成许多 个独立的小数据集进行分布式的处理，实验证明该方法可以有效的分割并处理海、 量数据，正确性较高。 同时，在处理现实问题时，很难得到完全确定的数据，对不确定性数据的处理 s k o w r o n 教授等人提出的一种通过投影得到缺省决策规则的算法1 2 4 】，可以从不确 定性数据中提取规则，但该算法需要人为确定域值来控制规则的生成：王国胤教 授等人针对该问题给出了一种决策表信息系统的不确定性度量方法瞄】，并且基于 这种方法提出了一种不依赖领域先验知识的自主式知识学 - j 模型l 驯。 粒计算是一种基于粒子的问题求解和信息处理方法，其基本思想存在于许多领 域，如经典集合论及其扩展( f u z z y 集、r o u g h 集、v a g u e 集等) 、区间分析、证据 理论、神经网络、决策树、机器学习、数据挖掘、语义网络、聚类分析等。1 9 7 9 年f u z z y 集创始人l a z a d e h 教授在世界上首次提出了模糊信息粒化问题【2 ”。从 那以后，信息粒化开始得到人们越来越多的关注。在运用粒计算理论进行知识获 取的研究方面，已经有了一些研究成果。文献 2 s l o e 的s l m g r c 算法，通过对样 本空间进行不同层次的分解，再从每一层的粒子中获取规则，与许多经典决策树 算法相比，该算法不需要考虑属性选择问题，同时结合粗糙集中不确定性度量的 方法生成阈值并控制规则的生成，相应地提高算法的执行效率。但是s g 疋算 法要求一次性将所有的数据都存入内存，因此不能处理海量数据。 一种基于粒计算的可伸缩算法在本文中被提出，该算法通过利用粒计算中对样 本空问进行不同层次粒化的方法对海量数据进行分层、粒化，同时结合本文提出 的粒分布链表利用数据库技术实现该算法的可伸缩性。仿真实验表明，该算法生 成的规则集较小，规则短，对未知样本有较高的识别率，同时也可以处理海量数 据集。 本论文工作得到重庆市自然科学基金( n o 2 0 0 5 b b 2 0 6 3 ) 重庆市自然科学基 金重点项目( n o 2 0 0 5 b a 2 0 0 3 ) ；重庆市教委科学技术研究项目( n o k j 0 5 0 5 0 9 ) 的 资助，是这些项目整体研究工作中的一部分。 重庆邮电大学硕士论文 第一章绪论 1 4 论文组织与结构 本论文的组织结构如下： 第一章介绍了海量数据挖掘的现状，以及本文的研究背景和研究工作； 第二章中，为了便于后面的叙述，我们先对粗糙集、粒计算理论中的一些基本 概念进行了简单介绍； 第三章提出了一种可伸缩的粒计算知识获取模型及其实现，以及运用这个模型 从数据集中获取知识的方法。 第四章通过一系列的试验及对比来验证该算法的有效性，可伸缩性及速度。 第五章对本文进行了总结。 重庆邮电大学硕士论文第二章租糙集及粒计算理论基础 第二章粗糙集及粒计算理论基础 2 1 粗糙集理论基础 粗糙集理论是一种刻画不完整性和不确定性的数学工具，能有效地分析和处理 不精确、不一致、不完整等各种不完备信息，并从中发现隐含的知识，揭示潜在 的规律。粗糙集理论的研究已经经历了近2 0 年的时间，无论是在系统理论、计算 模型的建立和应用系统的研制开发上，都己取得了很多成果，也建立了一套较为 完善的粗糙集理论体系。 2 1 1 粗糙集理论概念 在粗糙集中，“知识”被认为是一种将现实或抽象的对象进行分类的能力。 定义2 i 给定我们感兴趣的对象论域u ，对于任何子集x u ，称之为u 中的概念或 范畴。为了规范起见，我们认为空集也是一个概念，并且u 中任何概念族称为关 于u 的抽象知识，简称知识。我们通常用等价关系代替分类。 定义2 2 设【，是一个论域，r 是【，上的一个等价关系。洲r 表示u 上由r 导出的所有 等价类。f x 】。表示包含元素工的r 的等价类，工u 。一个知识库就是一个关系系 统k = u ，p ，u 其中是论域，p 是u 上等价关系族。如果q e p j l q o ，则n q ( q 的所有等价关系的交) 也是一种等价关系，称为p 上不分明关系，且记为 i n d ( p ) 。 不分明关系的概念是r o u g h 集理论的基石，它揭示出论域知识的颗粒状结构。 定义2 3 令u ，当x 能够用属性子集r 确切地描述( 即属性子集r 所确定的u 上 的不分明关系的并) 时，称x 是可定义的，否则称x 是不可定义的。只可定义集 也称作精确集，r 不可定义集也称为非精确集或r 粗糙集( 在不发生混淆的情况 下也简称为粗糙集) 。 定义2 4 假设给定知识库k = ( u ，r ) ，对于每个子集u 和一个等价关系 r 1 n d ( k 1 ，我们可以根据月的基本集合的描述来划分集合x ，为了衡量基于尺 的基本集合的描述y ，精确地说明中对象的隶属度情况，我们使用f 近似集l j 9 重庆邮电大学硕士论文第二章租糙集及粒计算理论基础 上近似集这两个概念，它们分别定义如下： 下近似集： 足( x ) = u l ( 誓v t z n d ( r ) y , x ) ( 2 1 ) 上近似集： r 一( x ) = u i l ( ie u i i n d ( r ) y 。n 肖中) ( 2 2 ) 也可以表示为： 足( x ) = 冰工u 乩z ) ( 2 3 ) r 一( x ) = 洲工u “j l n x 巾) ( 2 4 ) 定义2 5 集合引( x ) = r 一( x ) 一r ；( x ) 称为x 的r 边界域，集合j p o 品( x ) = 足( x ) 称、 为x 的r 正域，集合鹏( x ) = 【，一足( x ) 称为x 的r 负域。 足( x 1 是根据知识r ，u 中所有一定能够归入x 的元素的集合，即所有包含 于j 的i 的并。r 一( x ) 是根据知识五，( ，中一定能和可能能够归入x 的元素的集 合，即所有与j 的交不为零的r 的并。b n r ( x ) 是根据知识r ，c ，中即不能肯定 归入集合x ，又不能肯定归入集合x 的元素构成的集合。p o 峨( x ) 是根据知识五， u 中所有一定能归入集合x 的元素构成的集合。n e g r ( x ) 是根据知识r ，u 中所 有不能确定一定归入集合x 的元素的集合。 2 1 2 不确定性度量 文献 2 5 提出了一种决策表信息系统的不确定性度量方法，基于这种方法， 我们可以在没有领域先验知识时，对不确定性信息进行处理。下面给出这种不确 定性度量方法的定义。 定义2 6 给定决策表s = ，r = c u d ，c 和d 分别为决策表的条件属性和 决策属性，【，l i n d ( c ) 和u 1 1 n d ( d ) 分别为论域u 在属性集c 和d 上形成的划分； 条件分类定义为：e u i i n d ( c ) ，i = l ，m ，m 为条件分类的个数；决策分类 定义为：x f u i i n d ( d ) ，= 1 ，n ，疗为决策分类的个数。 对于决策表s = ，r = c u d ，c 和d 分别为决策表的条件属性和 决策属性，分类耳u l i n d ( c ) ( i = i ，m ) 为条件分类，x ，u i i n d ( d ) ( j = 1 ，n ) 为决策分类，则对于任意条件分类e 对应有集合巧，满足： 巧= m a x 目n i x j u i i n d ( d ) ( 2 5 ) 因此对于各条件分类集合局，蜀，都分别存在对应的五，l ，乙。 定义2 7 l o 重庆邮电大学硕士论文 第二章租糙集及粒计算理论基础 给定决策表s = ，巨，互，已是所有的条件分类，那么决策表 整体确定性定义为： 吲 胪钉 决策表整体不确定性定义为： 蚓 儿。1 他引一钎 ( 2 6 ) ( z 7 ) 定义2 8 、 给定决策表s u ，置矿，厂 ，r = c u d ，c 和d 分别为决策表的条件属性和 决策属性，分类巨u l m d ( c ) ( i = l ，聊) 为条件分类，u i i n d ( d ) ( j = l ，h ) 为决策分类，任意条件分类层u l 优d ( c ) 对于决策属性分类的确 定性程度定义为： r ( 巨) = m a x l 历n l l e l i v l m d ( d ) ( 2 8 ) r ( 骂) ，j r ( 瓦) 是条件分类对决策分类的确定性程度，则决策表局部最小确 定性定义为： 巴= m i l l k 假) ，r ( e ) ( 2 9 ) 决策表局部最大不确定性定义为：= 1 一a 。 定理2 1 由决策表s 得到的规则集f ，在决策表能够充分反映领域样本数据的情况下， 对从决策表中获取的规则知识进行测试的最大可能正确率，7 等于决策表整体确定 性雎，即有： 吲 1 1 = 炉钎 q 1 0 其中m 为决策表条件分类数。 定理2 2 对决策表s u ，r ，矿， ，其中r = c u d ，我们取决策表局部最小确定性为 阈值来控制规则集f 的生成，用f 对样本数据集进行测试，理论上可以得到对样 本数据集测试的最大正确率。 定理2 2 的证明【2 6 】： 首先根据条件属性集c 计算决策表s 的条件分类：气l u i , n o ( c ) ， 重庆邮电大学硕士论文 第二章粗糙集及粒计算理论基础 k = l ，一，l u i 刀v d ( c ) i 。 对于任意& 。，c ) 对应存在c l = m 缸 & 。岛n 五i 置u i 优o ( d ) ，且对任意条 件分类臣i ，c ) ，存在一u i 刀v d ( d ) ，并满足： & ) n = i n 越 置。，c ) n x , l x , 【，l 7 v d ( d ) = c ) a 因此k 。c ，n _ l | 臣。，c ) i - l 墨，i i e ! 盯) l 是规则d 甜( & 。c ) ，c ) 寸d 酷( - ，d ) 的可 信度因子，其中，d 晒( & ) ，c ) 为用条件属性集c 来表示条件分类气。c ) 的公式， d 甜( 乃，d ) 为用决策属性集d 来表示决策分类以的公式。 由此可知： i z i q i | 气“) | = r ( 置。，q ) 。 叉因为： 以= m 血 k ( 气q ) ，r ( 墨。q ) ，k ( 州斜c ) ) ， 所以k ) i 1 e ( 一2 吒 因此，我们可以得到规则脑( 艮c ) ，c ) 斗d 部( _ ，d ) 0 c ) i 1 e , ) i ，其中， i 五耶) i i e , 托) i 是该规则的可信度因子。 如果用这条规则测试，c ) 中的数据，可得到正确结果的样本集合为 墨) = m a x 置。c ) n 五i 瓦u 1 月v d ( d ) ) 。 因此，测试整个决策表得到正确结果的样本集合为： i v l v ( c l 墨 h - i 柙：掣 v l x o ( c w 。 2 重庆邮电大学硕士论文第二章粗糙集及粒计算理论基础 2 1 3 类分布链表 文献 2 2 引入了一个链表结构来描述某个条件属性组合对论域的划分情况以 及该条件属性组合相对于决策属性的正域，该链表结构既为类分布链表。任意一 个条件属性子集p ( p c o 的类分布链表示为c d l ( p ) ，它用来表示p o s e ( d ) 和 u p 的信息。在类分布链表中，任意两个相邻的样本都由符号“& ”，“ ”或者 “撑”来连接。对于属性组合p 的类分布链表，其中的任意两个样本五和而使用何 种符号来连接要依据以下三种情况： 如果王( p ) x d p ) ，则x 和x ：使用“撑”来连接； 如果( p ) = 而( p ) 但是) 毛( d ) ，则五和而使用“ ”来连接； 如果而( p ) = 而( p ) 同时 ( d ) = 而( d ) ，则五和而使用“& ”来连接； 因此，在c d 正里，所有的条件分类被“撑”分隔开来，任意两个“萍”间的部 分就是一个条件分类。 表2 1 是一个决策表信息系统的例子。 表2 1 决策表 i n d e x s a l a r ya g e c l a s s 1h3 0b 2 l 2 3b 3h4 0 g 4 m 5 5b 5 h 5 5g 6 m4 5 g 7l6 0b 8v h3 5g 从该表上我们可以得到属性s a l a r y 的类分布链表： c d l ( s a l a r y ) = # 1 3 & 5 # 2 & 7 # 4 6 # 8 # 从c d 正( 扫口肠 ) 中我们可以发现样本1 ，3 和5 具有相同的s a l a r y 值，但样本 3 和5 的决策属性值与样本1 的决策属性值不相同，因此这个由1 ，3 和5 三个样 本组成的条件分类是有冲突的。而样本2 和7 具有相同的s a l a r y 值和相同的c l a s s 值，它们在s a l a r y 上是完全一致的。而另一方面，我们可以直接从表3 1 得到： u c l a s s = 1 ，2 ，4 ，7 ， 3 ，5 ，6 ，8 ，和 u s a l a r y - 1 ，3 ，5 ， 2 ，7 ， 4 ，6 ， 8 重庆邮电大学硕士论文第二章租糙集及粒计算理论基础 因此有尸。墨。圳( c 哪 ) = 2 ，7 u 8 ) 。所以，类分布链表c d l ( 阳肠，) ，) ) 能够 完全体现了u s a l a r y 和p 6 嘎。t a r y ( c 螂 ) 的信息。 c d l 可以反映某个条件属性组合对论域的分类情况，它又可分为两个部分： 不相容类分布链表( i c d l - - i n c o n s i s t e n tc l a s sd i s t r i b u t i o nl i s t ) 和相容类 分布链表( c c d l - - c o n s i s t e n tc l a s sd i s t r i b u t i o nl i s t ) 。c c d l 根据链表中 每个分类的样本数目又可分为单例相容类分布链表( s s c d l s i n 9 1 es a m p l e c o n s i s t e n td i s t r i b u t i o nl i s t ) 和多例相容分布链表( m s c d l - - m u l t i s a m p l e c o n s i s t e n td i s t r i b u t i o nl i s t ) 。s s c d l 是c d l 中只含有一个样本的分类的组合， m s c d l 由c d l 中含有多个样本但不含有“ ”的分类组成i c d l 是c d l 中含有 多个样本同时也含有“ ”的分类的组合。如葶誓1 中的类分布链表c d ( 阳肠，) ) 就可以分成三部分： i c d l ( s a l a r y ) = 撑l 3 5 埘 甜 s s c d l i s a l a r y ) = 群8 群 m s c d l ( s a l a r y ”= 拌2 & 7 群 2 2 粒计算理论基础 人脑对问题的认知可以用三个基本概念来描述，即粒化( g r a n u l a t i o n ) 、重组 ( o r g a n i z a t i o n ) 和因果推理( c a u s a t i o n ) 1 2 7 捌，“粒化是把整体分解为部分， 重组是把部分合并为整体，而因果推理指的是促使这种分解与合并的原因以及它 们会导致的结果”。对于粒计算的研究，很大程度上是因为它模拟了人脑认识和解 决问题的过程。粒计算的主要模型有包括：集合论和区间分析、模糊集、粗糙集、 商空间理论、概率论等等。对于这些模型已有了许多研究和应用，特别值得注意 的是，它们大多是独立发展起来的，彼此之间并没有多少相互影响，但它们最终 都统一于粒计算这个框架之下，这也从另一方面表明粒计算本身是一种基础的问 题求解方法。 2 2 1 粒计算的概念 粒计算中存在许多基本问题，如空间的粒化、粒的描述、粒子之间的关系和使 用粒的计算。空问的粒化是指将对象空间分解为许多子空间，或是基于有用的信 息和知识将空间中的个体聚集成不同的类，这些类我们称为粒，粒中的元素可以 对应概念的实例。因为概念生成的目的之一是对具有某些概念的粒的表示、特征 化、描述和解释，而知识发现和数据挖掘的一个重要方面就是n ：颗粒之| 日j 建立关 4 重庆邮电大学硕士论文第二章租糙集及粒计算理论基础 联和因果等联系，因此可以把粒计算机制与概念生成、知识发现和数据挖掘联系 起来。 虽然目前对什么是粒计算还没有明确的定义，也没有一个统一的模型来统一诸 多粒计算的具体模型。但是人们对粒计算基本问题都有一个大致的想法，即粒计 算可以从两大方面来进行研究：粒子的构造和使用粒子的计算。前者处理粒子的 形成、表示和解释，后者处理在问题求解中粒子的运用。同时粒计算的研究可以 从两个同等重要的层面展开：语义和算法。 通俗地讲，粒计算的语义研究侧重“为什么”这类问题，侧重于对粒的解释， 如为什么两个对象会在同一个粒之中? 不同粒子之间存在怎样的关系? 一般来 讲，每一个粒中的元素满足不可分辨关系、相似性、邻近性或者功能性，同时信 息粒化也基于这些关系。由于对论域不同的分类标准( 等价、相容、泛序、异同 等关系) 可能会形成不同的粒空间，并具有不同的粒子结构，所以有必要研究这 些关系的语义解释，如相似性( c l o s e n e s s ) 、关联性( a s s o c i a t i o n ) 、依赖性 ( d e p e n d e n c y ) 。粒子结构的不同对论域的任一子集的近似集和对这些基本粒的操 作会有所不同，并导致算法的时间、空间复杂度有很大差别，因此进行信息粒化 时要结合实际需要。 粒计算的算法研究关注“如何”这类问题，即如何进行粒化和如何进行基于粒 的计算。很有必要研究粒计算的方法学和工具( 如近似、推理等机制) 。对粒子的 分解与合并机制的研究，是构建任何粒度体系结构的本质要求。 2 2 2 粒的层次 直观地讲，粒的大小描述了其特异性，粒中元素越多，它就越抽象越通用； 反之则越抽象。 信息粒化的层次取决于所要求解的问题。信息粒可视为概念的构造块，用来 观察和描述问题并同外界交互，从而决定了粒度的层次。在此，我们把信息粒视 为一种执行有效计算的机制，在问题求解中选择最有用