（应用数学专业论文）信息粒度与决策树.pdf

摘要 摘要 信息粒度是对信息颗粒大小的描述，不同种类、不同层次的粒度产生的效果不 同。信息熵是信息粒不确定程度的度量，信息熵越大，信息粒的不确定程度也越大。 本文对粗信息粒与细信息粒的信息熵做了比较研究，并研究了粗信息粒和细信息粒 对决策树产生的影响，得出以下结论：粗信息粒的信息熵不小于细信息粒的信息熵， 细信息粒下选取扩展属性产生的决策树优于粗信息粒下选取扩展属性生成的决策 树。 关键词信息粒度粗信息粒细信息粒信息熵决策树 a b s t r a c t a b s t r a c t i n f o r m a t i o ng r a n u l a r i t yi sad e s c r i p t i o no ft h es i z eo ft h ei n f o r m a t i o ng r a n u l a r , d i f f e r e n tg r a n u l a r i t yh a sd i f f e r e n te f f e c ti ni n f o r m a t i o nd e a l i n g i n f o r m a t i o ne n t r o p yi sa m e a s u r eo ft h eu n c e r t a i n t yd e g r e ei nt h ei n f o r m a t i o ng r a n u l a r i t y , t h eb i g g e rt h e i n f o r m a t i o ne n t r o p yi s ，t h eb i g g e rt h eu n c e r t a i n t yd e g r e ei nt h ei n f o r m a t i o ng r a n u l a r i t yi s t h ei n f o r m a t i o n e n t r o p y b e t w e e nc o a r s e g r a n u l a r i t y a n df i n e g r a n u l a r i t y i s c o m p a r a t i v e l ys t u d i e d ，t h ei n f l u e n c eo nd e c i s i o nt r e ec a u s e db yc o a r s eg r a n u l a r i t ya n d f i n eg r a n u l a r i t yi si n v e s t i g a t e d ，a n dt h ec o n c l u s i o ni sp r o v i d e dt h a tt h ei n f o r m a t i o n e n t r o p yu n d e rc o a r s eg r a n u l a r i t yi sn o tl e s st h a nt h eo n eu n d e rf i n eg r a n u l a r i t y i ti s s h o w nt h a tt h ed e c i s i o nt r e eg e n e r a t e db ys e l e c t i n gt h ee x p a n d e da t t r i b u t eu n d e rf i n e g r a n u l a r i t yi sb e t t e rt h a nt h eo n e u n d e rc o a r s eg r a n u l a r i t y k e y w o r d s i n f o r m a t i o ng r a n u l a r i t yc o a r s eg r a n u l a r i t yf i n eg r a n u l a r i t y i n f o r m a t i o ne n t r o p yd e c i s i o nt r e e i i 河北大学 学位论文独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写的研究成果，也不包含为获得河北大学或其他教 育机构的学位或证书所使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了致谢。 作者签名： 日期：俎年月一同 学位论文使用授权声明 本人完全了解河北大学有关保留、使用学位论文的规定，即：学校有权保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存 论文。 本学位论文属于 1 、保密口，在年月日解密后适用本授权声明。 2 、不保密曰。 ( 请在以上相应方格内打“ ) 保护知识产权声明 本人为申请河北大学学位所提交的题目为嘱焦狂及多) 泛笨勿彳 ) 的学位论文，是我个人在导师( 壬眨暇) 指导并与导师合作下取得的研究成果， 研究工作及取得的研究成果是在河北大学所提供的研究经费及导师的研究经费 资助下完成的。本人完全了解并严格遵守中华人民共和国为保护知识产权所制定 的各项法律、行政法规以及河北大学的相关规定。 本人声明如下：本论文的成果归河北大学所有，未经征得指导教师和河北大 学的书面同意和授权，本人保证不以任何形式公开和传播科研成果和科研工作内 容。如果违反本声明，本人愿意承担相应法律责任。 声明人：日期：垫2 年么二月l 日 作者签名：左耋查 别磁辄号纽一 日期：丑年l 月l 日 日期：盟年上月l 日 第1 章绪论 第1 章绪论 1 1 课题研究的目的与意义 人类在认识问题时，可以先从较抽象的( 整体的或宏观的) 粒度开始，一步一步地深 入到较具体的( 局部的或微观的) 粒度的细节。如对人体的认识过程，先从整体出发，认 识人的外部特征，再从各个部位如头、身和四肌等，进而逐步深入，直至破译人体全部 的d n a 密码。在实际的认识过程中，人们往往不能或不必一次性地考虑所有问题的细 节，可以先将问题分解或简化，忽略其中的一些细节，应根据研究问题的需要选择适当 的粒度。如在判断一个人的外部特征时，就不用知道这个人的全部d n a 的密码；在判断 一个人的脸部特征时，就不用考虑到四肌和身体等的特征。有时要经过从抽象( 整体或 宏观) 到具体( 局部或微观) 、从具体( 局部或微观) 到抽象( 整体或宏观) 不断变化的粒度世 界，才能对一个问题有较清楚的认识。 信息粒度【卜4 j 的概念最早由模糊集的创始人l a z a d e h 于2 0 世纪7 0 年代提出。z a d e h 认为现实世界中由于信息度量和信息采集所限而造成的信息不连续性很难用经典的数 学方法来处理，因而z a d e h 将这些不连续的信息看作一个个信息颗粒，即把粒内的数据 点作为一个整体来对待而不是像经典数学那样无限精度的细分下去。 我国科学家张钹和张铃提出了商空间理论【5 6 j ，并指出：人类智能的一个公认的特 点，就是人们能从极不相同的粒度上观察和分析同一问题。 商空间下，粒度可以看作一个论域的类、簇或子集，论域中属于同一粒度的对象具 有不可分辩性、等价性或相似性。这样在此粒度下，将论域划分为若干个子集的过程就 是对论域的粒度化，并根据论域划分所得到的每个子集为基本单位进行推理。如在表1 中，属性o u t l o o k 可以看作一个等价关系，它形成论域u 的一个划分o u t l o o k = s u n n y ， o v e r c a s t ，r a i n ，这个划分就是u 的一个信息粒( 粒) ，而其中的一个元素( 子集) 为 一个基本粒，如s u n n y 就是一个基本粒，在信息处理过程中，不同的粒给我们提供的信 息量是不同的，产生的效果也不尽相同。信息熵1 7 j 是信息系统不确定程度的度量，熵越 大，系统的不确定性也越大，确定它需要的信息量也越大。在一个信息系统中，每一个 河北人学理学硕十学传论文 信息粒都有一个信息熵，不同的信息粒往往有不同的信息熵。 决策树o 】是一种典型的归纳学习方法，i d 3 算法【9 】是q u i i n l a n 提出的决策树生成算 法，它以信息熵为度量标准，递归地选取扩展属性，生成一棵树。 本文对粗信息粒与细信息粒的信息熵做了比较，并研究了粗信息粒与细信息粒对决 策树产生的影响，从粒度计算的角度为i d 3 算法的合理性提供了一个理论基础。得出了 以下结论：粗信息粒的信息熵不小于细信息粒的信息熵，细信息粒下选取扩展属性产生 的决策树优于粗信息粒下选取扩展属性生成的决策树。 1 2 本课题的国内外发展现状 粒度原本是一个物理学的概念，是指对微粒大小的平均度量。在这里被借用 作为对数据信息和知识粗细的平均度量，用于从宏观或微观层面上分析和处理信 息。在人类的认识活动中，粒度的思想无处不在，人们观察、度量、定义和推理 的实体都是粒度。 早在1 9 7 9 年z a d e h 就提出并讨论了模糊信息粒度【1 l l 】，以元素属于给定概念 ( 信息粒) 的隶属程度作为粒度，推动了模糊逻辑理论及其应用的发展。并于1 9 9 6 年提出了词计算理论【1 2 - 1 4 1 ，认为人类认知的三个主要概念是粒化( 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 9 8 2 年p a w l a k 提出了粗糙集理论【1 5 , 1 6 ，认为“人的知识就是一种分类的能力”，这 个观点可能不是很完备，但却非常精炼。他用论域中的子集来表示概念，给定了论域上 的一簇子集，就相当于给定了一组知识。这样在论域中给定了一个等价关系，就给定了 一个知识基，然后再讨论一个一般的概念如何用这个知识基来表示。 1 9 8 5 年，h o b b s 提出一种粒度理论【1 7 】，并首次提出了粒度( g r a n u l a r i t y ) l 拘概念，他 用谓词或函数项定义了粒度和划分粒度，但没有给出粒度的计算准则，他将一个表示待 求解的整体问题的逻辑公式用粒度理论分成若干小问题或子公式，然后分别对这些子公 式求解并最后合并成整体公式的解。 1 9 9 0 年，我国学者张钹和张铃在其专著【l8 】中进行了关于粒度问题的讨论，并为这 种“粒度世界模型 建立了一整套理论和相应的算法，将其应用于启发式搜索、路径规 划等方面，取得了较大的成功。他们认为“人类智能的一个公认的特点，就是人们能从 第1 章绪论 极不相同的粒度上观察和分析同一问题。人们不仅能在不同粒度( g r a n u l a r i t y ) 的世界上进 行问题的求够很快地从一个粒度世界跳到另一个粒度世界，往返自如，毫无困难。这种 处理不同粒度世界的能力，正是人类问题求解的强有力的表现。”【18 这段话把粒度计算 的特征刻画得淋漓尽致，这也是他们建立商空间理论的出发点。然而，粒度计算 ( g r a n u l a r c o m p u t i n g ，o r c ) 作为一个专业术语是在1 9 9 7 年由l i n 和z a d e h 首先提出【1 4 , 1 9 1 。 粒度计算( 又称粒计算) 象一把大伞，覆盖了所有有关粒度的理论、方法论、技术和工具 的研究，是用来处理不完全、不可靠、不精确、不一致和不确定的知识，也即利用对不 完全、不可靠、不精确、不一致和不确定知识的可容度来实现问题的可处理性和鲁棒性。 它是人工智能研究的最重要基础，主要包括模糊集理论、粗糙集理论和商空间理论等。 z a d e h 和p a w l a k 的工作激起了学术界对粒度计算的研究兴趣，近年来，关于粒度计算的 文章和专著也越来越多，粒度计算的应用领域越来越广，已成为计算智能领域研究的重 要热点，对它的研究将对复杂的智能系统的设计和实现产生深远的影响。 1 3 本课题研究的主要内容 在许多实际问题中，为了有效的处理信息，做出更加准确的预测，需要考虑信息的 粒度( 划分) ，可以从不同层次的粒度处理信息，不同的种类、不同层次的粒度所产生 产生的效果也不相同。如决策树中，一个属性形成样例集的一种粒度( 一个划分) ，不 同的属性往往形成不同种类的粒度( 划分) ，每次扩展属性的分支，使用不同的属性作 为分类属性将生成不同的决策树。例如，表1 中训练集共含有1 4 个训练样例，其中 o m l o o k ，t e m p e r a t u r e ，h u m i d i t y 和w i n d 是样例的4 个属性，每个属性都对应训练集的 一个划分，以o u t l o o k 为例， o u t l o o k = s u n n y w r a i n w o v e r c a s t ) 而 s u n n y = d 1 ，d 2 ，d 8 ，d 9 ，d 11 ) ； r a i n = d 4 ，d 5 ，d 6 ，d 1 0 ，d 1 4 1 ； o v e r c a s t = d 3 ，d 7 ，d 1 2 ，d 1 3 ) 。 在决策树生成过程中，先选择属性o u t l o o k 还是属性t e m p e r a t u r e 将生成不同的决策树。 河北大学理学硕十学位论文 表1 相对于目标概念p i a y t e n n i s 的训练样例 d a y o u t l o o k t e m p e r a t u r e h u m i d i t yw i n d yp l a y t e n n i s d 1 s u n n y h o t h i g l l w e a kn o d 2 s u n n y h o t h i 曲s t r o n g n o d 3o ve ：l c a s th o t h i 曲 w j a ky e s d 4r a i nm i l d h i g h w e a ky e s d 5r a i nc o o ln o r m a l w e a ky e s d 6 r a i nc 0 0 1n o r m a l s t r o n g n o d 7o v e r c a s tc o o ln o r m a l s t r o n g y e s d 8 s u n n y m i l d h i 曲 w e a kn o d 9 s u n n y c o o ln o r m a lw e a k y e s d 1 0r a i n m i l dn o r m a l w e a k y e s d 1 1 s u n n y m i l dn o r m a l s t r o n g y e s d 1 2o v e r c a s tm i i d h i 曲s t r o n g y e s d 1 3o v c l c a s th o tn o r m a lw e a k y e s d 1 4r a i n m i l d h i g hs t r o n g n o 为了描述一信息系统的不同种类、不同层次的粒度所产生的不同效果，本文对粗信 息粒与细信息粒的信息熵做了比较，并研究了粗信息粒与细信息粒对决策树产生的影 响，得出了以下结论：粗信息粒的信息熵不小于细信息粒的信息熵，细信息粒下选取扩 展属性产生的决策树优于粗信息粒下选取扩展属性生成的决策树。 第2 章介绍了一些基本概念，介绍了粒度、粒度计算的基础理论、信息熵的概念及 i d 3 算法的主要思想； 第3 章研究信息粒、信息熵与决策树的关系并给出了如下的结论：粗信息粒的信息 熵不小于细信息粒的信息熵，细信息粒下选取扩展属性产生的决策树优于粗信息粒下选 取扩展属性生成的决策树。 第4 章是结论与展望及下一步的工作设想。 第2 章基础知识 第2 章基础知识 这一章，介绍一些基本概念和基本理论，主要包括粒度、粒度计算的基础理论、 信息熵的概念及i d 3 算法的主要思想。 2 1 一些基本概念 定义2 1 1 ( 信息粒) 【6 1 设给定论域u 和u 上的一个关系r ：u p ( u ) ，u = u 彳， 则称彳，为u 的一个基本粒， 彳，) 。为u 的一个信息粒，其中p ( u ) 为u 的幂集，7 r 为 一个实数集；r 可代表等价关系、不可区分关系、相似关系、功能相似关系、相等关 系、约束、复合关系、模糊关系、属性、投影、结构关系和一般的函数等。 从集合论观点来看，一个信息粒相当于一个覆盖，划分是它的一个特例；从代数 学的观点来看，一个信息粒相当于一个二元关系，等价关系是其特例。 本文考虑的信息粒都是其基本粒没有公共元素的，在集合论中它对应划分，在代 数学中它对应等价关系；另外，本文还规定，论域是有限的。 定义2 1 2 ( 信息粒的粗细) 设r 是论域u 上关系的全体，且蜀，r ：r ，若对 v x ，y u ，x r l yjx r 2 y ，则称r 1 比r 2 细，或r 2 比r 1 粗，简记为r l 比r 2 或r 2 r 1 一个关系代表一个分类，因此，也可表示粒的粗细。同一论域的粒之间存在不能 比较粗细的情形。 例如，设论域u = x 1 , x 2 ，x 3 ；x 4 ，x 5 ，x 6 ) ，r 1 ，r 2 ，r 3 是u 上的三个关系，且 r 1 = x 1 ，x 2 ，x 3 ) ， x 4 , x 5 ，x 6 ) ) ，r 2 = x 1 , x 2 ) ， x 3 ) x 4 , x 5 ，x 6 ) ) ， r 3 = “x l ，x 2 ) ， x 3 , x 4 ) ， x 5 , x 6 ) ) ，则r 2 r 1 ，即r 2 比r 1 细，但r 3 与r 1 不能比较 粗细。 定义2 1 3 信息熵是信息的一种不确定性程度的度量，假定一个系统s 具有概率 分布p2 p ) ( o 只1 ) ，f _ 1 ，2 ，一，则系统s 的信息熵( s h a n n o ne n t r o p y ) 定义为 e 0 ，c o ，d 0 令 第3 章粒j 交计算与决策树 u ( c ，力= x l 0 9 2 ( x + c ) + y l 0 9 2 c v + 印一( x + y ) l 0 9 2 ( x + y + c + 印 我们求( 3 5 ) 的最值 由甜d ) = 面1 【鬲x xc 一= 一 y d xc 而当一y = 一d 时 仁一去n 2c 南一 l 、( x + c 1 2 x + y x + y + c + d x + y ( 工+ y + c + d ) 2 ) = 0 可得 卜击赢 。 所以，当兰：三时，( 3 7 ) 式达到最大值， 1 ，a 将三：三代入( 3 5 ) 式，整理可得 1 ，a “m a x ( c ，d ) = x l 0 9 2x + y l 0 9 2y 一( x + y ) l 0 9 2 ( x + y ) 同理，姒删) = 去( 南一 可得三 y 而当三 y c d = 昙时 x + y z + y + c + d 1 = 0 ， ，! ：一三一r 兰 一 兰羔 、：一l “矗一丽丽一瓦万丽户一而 所以，当兰：三时，( 3 4 ) 式达到最大值， 1 ，a y ( x + c ) 2 ( 工+ y ) 0 将兰：一c 代入( 3 5 ) 式，整理可得 1 ，a z m a x ( c ，d ) = x l 0 9 2x + y l 0 9 2y 一( x + y ) l 0 9 2 ( x + y ) 所以 当三：三时 y d m a x ( c ，d ) = x l 0 9 2x + y l 0 9 2y 一( x + y ) l 0 9 2 ( x + y ) 从而( 3 4 ) 式成立， 1 7 - ( 3 5 ) ( 3 6 ) ( 3 7 ) ( 3 8 ) ( 3 9 ) 河北人学理学硕十学位论文 令x = p l ，y = q l , c = p 2 , d = q 2 ，代入( 3 4 ) 可得 p 1l 0 9 2p l + q ll 0 9 2q l 一( p l + q 1 ) l 0 9 2 ( p 1 + q 1 ) p 1l 0 9 2 ( p l + p 2 ) + q ll 0 9 2 ( g l + q 2 ) 一( p l + q 1 ) l 0 9 2 ( p l + q l + p 2 + q 2 ) ( 3 1 0 ) 同理，令x = p 2 ，y = q 2 c = p 1 ，d = q i ，代入( 3 4 ) 可得 p 2l 0 9 2p 2 + q 1l 0 9 2q 2 一( p 2 + q 2 ) l 0 9 2 ( p 2 + q