（计算机软件与理论专业论文）基于粗糙集理论的连续值属性离散化方法研究(1).pdf

摘要现实中采集到用于分类学习的信息集合通常是基于连续特征空间的，但是，对于绝大多数机器学习算法来说，连续的特征值数据并不是一个合适的输入，必须将其离散化，采用高效的离散化算法，将会极大的提高机器学习算法的效率和精度，降低问题的求解复杂性并提高算法的可移植性，此外，将保持原始数据分类信息的离散化数据应用于机器学习算法所获取的知识具有更精简和更易理解的形式，因此连续属性值的离散化方法作为机器学习算法的预处理过程受到人们越来越多的关注。近年来，作为一种新兴的归纳学习方法，粗糙集理论以其“不需对数据的任何先验假设”、“可提供非完备，非协调等不确定性知识获取方法”、“所获知识具有较好的直观可理解性”等显著优势获得人们的广泛关注。基于r o u g h 集的离散化方法可以更加深刻的描述数据的依赖特征，获得较高的精度。本文通过对大量现有连续值属性离散化方法进行分析总结，依据发现的问题对基于粗糙集理论的离散化算法进行优化。主要研究内容及成果有：1 提出新的评价标准，对现有的多种离散化方法进一步分类细化，并在分类框架的基础上对典型方法进行评述。总体来说，连续值属性离散化算法现有分类标准：动态和静态( d y n a m i cv s s t a t i c ) ，受监督和非监督( s u p e r v i s e dv s u n s u p e r v i s e d ) ，全局和局部( g l o b a lv s l o c a l ) ，自项向下和自底向上( t o p d o w nv s b o s o m u p ) ，直接划分和逐步划分( d i r e c tv s i n c r e m e n t a l ) 。本文依据“离散化过程是否考虑属性依赖性”可将离散化方法进一步分为属性独立的和属性依赖的方法( a t t r i b u t e i n d e p e n d e n tv s a t t r i b u t e d e p e n d e n t ) ，通过建立离散化方法的分类框架可知具有s u p e r v i s e d ，g l o b a l ，i n c r e m e n t a l ，a t t r i b u t e d e p e n d e n t 等特征的离散化算法可以具有相对良好的划分精度。而基于粗糙集理论的方法通常具有以上特点。2 重点分析基于粗糙集理论的离散化方法，并依据发现的问题对原始的m d 一算法进行优化。基于粗糙集理论，利用连续属性值之间的序关系降低算法的时间和空间复杂度，设计具有线性存储结构的m d 离散化方法，并进行相关的算法复杂度分析和优化理论证明；依据分割点之间的关联对于离散化结果精度的影响，给出属性值域上分割点之间的相关性度量并设计相应的优化算法，进一步提高基于粗糙集理论的离散化算法的精度。3 进行对比实验分析，完成优化算法相关的实验验证。实现设计的优化算法，并将几种具有代表性的离散化算法以及优化后的算法应用于大规模遥感地理信息数据集，对算法效率及离散化结果进行综合分析评价。关键词：离散化方法；粗糙集理论；线性存储；分割点相关性；m d 一离散化算法中图分类号：r e s e a r c ho nd i s c r e t i z a t i o no fc o n t i n u o u sb a s e do nr o u g hs e tt h e o r yy u ex i a o d o n g ( d a t am i n i n ga n dk n o w l e d g ed i r e c t e db yp r o f e s s o rl id e y ua b s t r a c tf e a t u r e sd i s c o v e r y )d a t ac o m i n gf r o mt h er e a ll i f ea sc l a s s i f i c a t i o ni n f o r m a t i o ni su s u a l l vc o n t i n u o u sf o r m a t ，b u tc o n t i n u o u sf e a t u r ei sn o tp r o p e ri n p u t sf o rm o s ti n d u c t i v em a c h i n el e a r n i n ga l g o r i t h m s d i s c r e t ev a l u e sa r ei n t e r v a l si nac o n t i n u o u ss p e c t r u mo fv a l u e s t r a n s f o r m i n gc o n t i n u o u sf e a t u r ei n t od i s c r e t eo n e sc a nr e d u c et h et e s t e dd a t a ss c a l eg r e a t l ya n dt h ed i s c r e t ev a l u e sa r em o r ec o n c i s et or e p r e s e n ta n ds p e c i f y , e a s i e rt ou s ea n dc o m p r e h e n da n dc l o s e rt oak n o w l e d g e - l e v e lr e p r e s e n t a t i o nt h a nc o n t i n u o u sv a l u e s d i s c r e t i z a t i o nc a ni m p r o v em a n ym a c h i n el e a r n i n gm e t h o d s e f f i c i e n c ya n da c c u r a c y , s op e o p l ea r ep a y i n gm o r ea n dm o r ea t t e n t i o no ni t f o rt h ea d v a n t a g e so f “n on e e do fa s s u m p t i o no fd a t af o rm a c h i n el e a m i n g ”，“g e t t i n gk n o w l e d g ef r o mi n c o m p l e t eo ri n c o n s i s t e n td a t a ”a n dc t h ef o r mo f t h ek n o w l e d g em o r ec o n c i s et or e p r e s e n ta n dc o m p r e h e n d ”r o u g hs e tt h e o r yh a v eb e e nc o n s i d e r e da sa na d v a n c e di n d u c t i o nl e a r n i n gm e t h o d t h ed i s c r e t i z a t i o nm e t h o d sb a s e do nr o u g hs e tc a nd e s c r i b et h ed e p e n d e n c va m o n gt h ea t t r i b u t e sp r e c i s e l yt op r o d u c et h eb e t t e rd i s c r e t i z e dd a t a m o s te x i s t i n gd i s c r e t i z a t i o nm e t h o d sh a v eb e e nr e v i e w e da n da n a l y z e di nt h i sp 印e r f u r t h e r m o r e ，n e wo p t i m i z e dd i s c r e t i z a t i o nm e t h o d sb a s e do nr o u g hs e tf o rs u p e r v i s e dl e a r n i n ga r ed i s c o v e r e di nt h ee x i s t i n gm e t h o d s s e v e r a la s p e c t sa sf o l l o w sa l s op r o p o s e dt or e s o l v et h ep r o b l e m st h em a i nr e s e a r c hw o r kc o n s i s t so f1 p r o p o s ean e wa x eb yw h i c hd i s c r e t i z a t i o nm e t h o d sc a nb ec l a s s i f i e df u r t h e ra n di n t r o d u c em o s te x i s t i n gm e t h o d su n d e rt h ec l a s s i f i c a t i o nf r a m e i ng e n e r a l ，d i s c r e t i z a t i o nm e t h o d so fc o n t i n u o u sa t t r i b u t e sc a nb ec l a s s i f i e do ns e v e r a la x e s ：d y n a m i cv s s t a t i c ，u n s u p e r v i s e dv s s u p e r v i s e d ，l o c a lv s g l o b a l ，d i r e c tv s i n c r e m e n t a l ，t o p d o w nv s b o t t o m u p t h en e wa x e “a t t r i b u t e i n d e p e n d e n tv s a t t r i b u t e d e p e n d e n t i sp r o p o s e di nt h i sp a p e rf u r t h e r m o r e ，w ec a ns e et h em e t h o d so fs u p e r v i s e d ，g l o b a l ，i n c r e m e n t a l ，a t t r i b u t e d e p e n d e n tf e a t u r e sl e a dt ot h ea d v a n c e dd i s c r e t i z a t i o nr e s u l tt h r o u g ha n a l y z i n ge x i s t i n ga l g o r i t h m su n d e rt h ec l a s s i f i c a t i o nf l a m ea n dt h em e t h o d sb a s e do nr o u g hs e to f t e nh a v et h ec h a r a c t e r i s t i c sm e n t i o n e da b o v e 2 a n a l y z et h ed i s c r e t i z a t i o nm e t h o d sb a s e do nr o u g hs e ta n di m p r o v et h em d - a l g o r i t h ma c c o r d i n gt ot h ep r o b l e m sd i s c o v e r e di nt h ea n a l y s i s m a k i n gu s eo ft h eo r d e r i n go ft h ec u t sa n da t t r i b u t ev a l u e so nc o n t i n u o u sf e a t u r e s ，an e wm e t h o db a s e do nr o u g hs e tt h e o r yi sd e s i g n e df o rr e d u c i n gt h ec o m p l e x i t yo ft h ee x i s t i n gm d a l g o r i t h m t h en e wm e t h o dd o e s n tc o m p r e s st h ed a t as t r u c t u r ei n t ol i n e a rs p a c eo n l y , b u ta l s oc o m p u t e st h ec u t s i m p o r t a n c eb ys p e c i f i cf o r m u l a s oi tc a ni m p r o v et h ee f f i c i e n c yo ft h eo r i g i n a lm d a l g o r i t h mal o t c o n s i d e r i n gt h ei m p a c t so fr e l a t i o n s h i pa m o n gc u t st od i s c r e t i z a t i o na c c u r a c y , d e s i g nt h ed i s c r e t i z a t i o nm e t h o d st h a te m p l o y st h ec u td e p e n d e n c yc o m p u t a t i o np r o p o s e d t h em e t h o d sc a i li m p r o v et h ea c c u r a c yo fo r i g i n a lm d a l g o r i t h m 3 c o m p l e t et h ee m u l a t i o n a le x p e r i m e n ta n dv e r i f yt h ea d v a n t a g e so ft h ei m p r o v e da l g o r i t h m s i m p l e m e n tt h ea l g o r i t h m sd e s i g n e da n ds e v e r a lc l a s s i c a ld i s c r e t i z a t i o nm e t h o d st ot h eh u g es c a l eg e o g r a p h yi n f o r m a t i o ns e t s c o m p a r ea n da n a l y z et h ed i s c r e t i z a t i o nr e s u l t st op r o v et h ea d v a n t a g e so ft h ep r o p o s e dm e t h o d s k e y w o r d s ：d i s c r e t i z a t i o n ；r o u g hs e t ；l i n e a rm e m o r ys p a c e ；d e p e n d e n c yo fc u t s ；m d a l g o r i t h m第一章引言1 1 选题背景及意义作为知识发现过程中最重要的环节，数据挖掘技术( d a t am i n i n g ) l i 的作用就是从海量数据中抽取用户感兴趣的知识。而由现实世界中采集到的数据却往往不适合直接应用数据挖掘过程中的学习算法，首先，现实采集的数据集合中通常含有噪声数据，并且可能存在不完备和不协调信息，其次，直接采集的数据集合规模很大，而且通常具有连续的特征空间，这样，低品质的数据集如果被直接运用于数据挖掘过程，根本无法获取用户期望的知识精度和算法效率。因此，我们需要解决两个问题，“在对大规模数据集应用挖掘算法之前，进行怎样的数据预处理可以改进数据集的质量，并最终改进从中提取的知识精度? ”以及“进行怎样的数据预处理可以提高挖掘过程中应用机器学习算法的效率并降低挖掘过程的复杂度? ”。数据预处理过程应具有以下几种关键功效：数据净化( d a t ac l e a n i n g ) ，用于消除原始数据的噪声及更正数据集合中存在的不协调性；数据整合( d a t ai n t e g r a t i o n ) ，用于将各种不同来源的初始数据整合在统一的数据存储形式之下；数据转换( d a t ay r a n s f o r m a t i o n ) ，用于将数据的表现形式转换为规范的，适用于挖掘算法的形式；数据约简( d a t ar e d u c t i o n ) ，通过聚合数据，删除冗余数据及属性，以便在压缩初始数据规模的同时进一步改进数据的质量。以上各种预处理技术并不是严格划分的，在对初始数据进行预处理的过程中，一个处理步骤可能同时达到多种改进数据质量的效果，如高效的离散化算法在对初始数据进行数据约简的同时，通常可以达到数据净化以及数据转换的效果。数据属性的离散化技术是数据预处理过程的重要组成部分，有效的离散化方法可以在减小数据规模的同时，在一定程度上净化用于分类学习的数据以及规范数据的表达形式，从而进一步提高机器学习算法的效率，降低挖掘过程的复杂度，并可改进算法的可移植性，研究表明，在离散化的数据集上运用机器学习算法获取的知识往往具有更高的精度，且得到的规则也具有更简洁的形式，更易于理解和使用。数据属性的离散化技术依据数掘属性值域类型主要分为符号值属性离散化( 属性值域是符号的有限集合) 和连续值属性离散化( 属性值域是连续的实数值区间) 。由于现实采集的数据集合大多具有连续的特征空间，但对于数据挖掘过程中采用的绝大多数机器学习算法来说，要求有限离散的数值空f 自j 作为输入数据，因此，连续值属性离散化方法对于实现高效的数据挖掘具有极其重要的作用。下面，将简要介绍连续值属性离散化方法的基本思想【2j ，设一个具有连续值属基于粗糙集理论的连续值属件离散化方法研究性的决策信息系统s = ( u ，爿，u d ) ，这里u 为有限非空的样本集合，称为论域或对象空问，a t 是样本空间的非空属性集合，d 为决策属性集合，对于每个连续值属性a a t ，其值域旷是样本空间u 在属性a 上的取值范围，由实数域上的一段左闭右开的区间【v 。，比) 来表示。对样本空间的连续值属性离散化的结果就是要在每个连续值属性a 的值域屹中寻找一个恰当的划分p ，且在划分只下的系统与初始系统具有相同的决策能力，只将属性值域划分为若干互不相交的子区间，对每个子区间以符号赋值，即得到一组屹上的离散化取值。因为任何划分只是由一组值域屹内的分割点序列( v v ： 1 ) 个部分，并对当前的划分状态进行评价，这种方法称为d i r e c t ( 直接划分的方法) ，这类算法需要用户或相关的计算方法来定义划分参数k 。而另外的方法则由最简单的划分状态开始不断细分或合并属性上的间隔，即不断加入或去除分割点，这种算法称为i n c r e m e n t a l方法( 逐步划分算法) ，这类算法没有局限于将属性值域划分为固定数目的部分，而是逐步地划分，加以评价，此类算法要求定义相应的评价标准以选择分割或合并，并且设定离散化过程的停止条件。因为直接方法中的划分参数k 的选取是非常困难的，所以，大多数离散化算法采用逐步划分的方法。在考虑了以上五种分类标准，并对近年来的一些离散化算法的思想加以分析，本章中引入了个新的分类标准来对现有的离散化方法进行进一步的分类探讨，从而更加深入地分析高性能离散化方法发展的方向。第一章引高在目前的大多数离散化方法中，出于计算复杂度方面的考虑，离散化算法在对某一属性进行离散化的同时，并不考虑样本的其它属性对其离散化过程的影响，也就是说，各个连续的条件属性值域上的离散化过程是相互独立的。我们称这种方法是a t t r i b u t e i n d e p e n d e n t ( 属性独立的) 离散化算法。而另外有些算法则在离散化过程中综合考虑各属性划分之间的关联影响，从全部的属性分割点中选取分割( 如m d 一算法) ，这种方法，我们称之为a t t r i b u t e d e p e n d e n t ( 属性相关的) 离散化算法。综上所述，我们可以按照如下六条标准对现有的离散化方法进行分析归类，即d y n a m i cv s s t a t i c ，s u p e r v i s e dv s u n s u p e r v i s e d ，g l o b a lv s l o c a l ，s p l i t t i n g ( t o p d o w n )v s m e r g i n g ( b o t t o m u p l 以及d i r e c tv s i n c r e m e n t a l 和a t t r i b u t e i n d e p e n d e n tv s a t t r i b u t e - - d e p e n d e n t ，从而得到如图1 1 所示的离散化方法分类框架图。如图1 1 所示，基于前一部分提出的各类准则，本章进一步丰富了文献 6 】提出的分类框架。在对现有离散化方法( 主要是静态的方法) 进行层次化分类的过程中，首先我们考虑是否使用了样例的类别信息( s u p e r v i s e dv s u n s u p e r v i s e d ) ，然后根据离散化的直观过程( 细分或是合并) 可以做出进一步分类( t o p d o w nv s b o t t o m u p ) ，最后，根据各个算法采用的具体的离散化标准，我们对每类方法进行分组，现有的具体离散化标准有e n t r o p y ( 基于熵理论的方法) ，b i n n i n g ( 直接分块的方法) ，d e p e n d e n c y ( 属性划分与类别相关性) ，a c c u r a c y ( 基于应用精度的方法) ，r o u g hs e t ( 基于粗糙集理论的方法) 以及c l u s t e r i n g ( 基于聚类思想的离散化方法) 等。本章的下一部分将简要介绍框架中的离散化方法，并从以下几方面对与本课题研究相关的离散化方法进行详细说明：方法采用的具体评价划分的标准以及离散化算法停止的条件；按照本章提出的分类准则对现有方法进行分类总结；依据每个方法采用的具体思想以及文献 6 】中已有的部分实验数据，迸一步分析方法可能存在的问题及其适用的具体条件。甚十射i 糙集理论的连续填瑚性离散化方睦研究暑宴摹l篓墨霎gi 暑* 呻譬一“岛il 鼻星量聋器吾吾南挣抖锵斟和符舟磐斟姆詈；勇6 一耋蠹ll】_i王04，。_|。，|田。竹co目up_【iop_d0毒_e n n l 昌yn】amon口nhf凸njp口isn【tlo；口epn邑n口乓一n l 】n e n l圈_一强舜犍去串措匡糟圉pinnsoi_vim&一_ 。c 邑h ，faet_ooco=n第一章0 l 高1 2 2u n s u p e r v i s e d 方法初期的连续值属性的离散化方法并不考虑样本的类别信息，而是根据用户定义的参数直接对属性值域进行划分。非监督的方法主要有等宽划分( e q u a l w i d t h ) 和等频划分( e q u a l - - f r e q u e n c y ) ，均为自顶向下，细分属性的方法( t o p - d o w n ) 。等距划分和等频划分的方法均需要用户设定相关的参数k 以决定对某一属性值域进行分割。等距划分下，方法将单个属性值域平均划分为等长的k 段；等频划分下，对象集在属性上被等规模地划分为k 个部分，其中每个间隔内含有相同数目的样本。此后，根据一些存在的问题，人们又对这两种方法做出了相应的改进，设定了一些评价标准和划分参数以调整分割。u n s u p e r v i s e d 方法的优点在于算法实现简单，但是，其缺点也非常明显。首先，该算法仅适用于不同类别的样本在各属性上分布非常均匀的情况，这样，算法爿可能正确划分不同类的样本，但实际情况下，数据集的类别信息分布往往是不规则的；其次，即使在样本分布很规律的条件下，如何确定每个属性的参数k 也将是一件非常困难的事情，k 的取值将直接影响到算法效率。因此u n s u p e r v i s e d 方法并没有考虑利用训练样本的类别信息，是最简单的离散化方法，难以取得令人满意的效果，后来发展的离散化方法大都注重属性划分与类别信息的关系。1 2 3s u p e r v i s e d 方法在利用类别信息的受监督离散化算法中，根据直观的离散化过程，可以分为b o t t o m ，u p ( 自底向上合并) 与t o p d o w n ( 自顶向下细分) 两类算法，首先介绍自顶向下细分的受监督的离散化方法。1 2 3 1b i n n i n g ( 直接分割的方法)1 r 算法【7 1 ( h o l t e ，1 9 9 3 ) 根据划分边界上的样本类别信息进一步调整非监督的等分方法得到的划分。m a x i m u mm a r g i n a le n t r o p y ( d o u g h t y19 9 5 ) 方法( m d l 方法) | 5 】利用计算分割点边界熵值的度量标准来调整等频划分后的分割点。方法中采用的熵的定义具有与文献 8 】中定义的熵相似的形式，给定一个样本集合s ，一个连续值属性a ，一个该属性值域上的分割7 在s 上导致的划分对于类别信息所产生的熵值如下定义：心= 捌肼 ) + 斜肼幔)基十粗糙集理论的连续值属性离散化方法研究属性值域a 上所有分割中使以上定义的熵值最小的分割i 。被选择用于二分当前样本空问s ，方法重复以上步骤，不断二分样本集合，直至满足f a y y a d 和i r a n i 定义的条件如下 8 】：g a i n r ：s 、 0 ) 对于任意分割点集p ，我们有类似的定义：i n d ( p ) = ( x ，y ) u x u l v p 。p ，( 口，( x ) 一p 。) ( a j ( y ) 一p 。) o ) 易证i n d ( p ) = n 。，i n d ( p 。) 。用u i n d ( p ) 表示u 在i n d ( p ) 下的商集，也表示i n d ( p ) 决定的u 的划分。对于x u ，我们用i n d x ( p ) 表示i n d ( p ) 在x 上的限制。在不致产生误解的情况下，仍用i n d ( p ) 来表示i n d ，( j p ) 。容易证明下面的定理。定理3 1 设分割点子集q p ，x i i n d ( q ) = x 。，x ，x 。) ，对v 儿p q ，有x i n d ( q u ( p 。) ) = u 二( ，i n d ( p 。) ) 。定义3 2 设s = ( u ，a u d ) ) 是一个决策表，x u ，对v a a 上的任意分割点p 。p ，定义c 。( p 。) = ( x ，x ，) 爿l d ( x ) d ( x ，) ，( z ，x ，) 9 1 n d ( p 。) l 。由定义3 2 可知，c 。( p 。) 表示对象集z 中可被p 。区分的决策值不同的样本对数目。设x 1 n d ( p 。) = ( x 1 ，2 ，一= l 1l ， 2 = 2 f ，h ? = x 1x 爿a 矗( x ) = d 。) 1 ，月；= i 缸j x 彳：ac l ( x ) = d ， f ，这里i = 1 ，2 ，卅，m 表示决策类个数。则兰塑堡塞堡堡堕堡堡垒璺堡塑塑些塑鲨塑壅一c 。( p 。) = ” n ；= ”：一”? ”7 ，j = i容易证明下面的定理。定理3 2 设q p 为分割点子集，一为对象子集，x i n d ( q ) = - ，x z ，x 。) ，p 。p q ，瞄( 儿) 表示j 中可被p 口区分且不能被分割点集台q 所区分的决策值不同的样本对的数目，n c 多( p 。) = ：c 一( ) 。算法3 1 线性存储m d 一算法输入：一个信息系统s = ( u ，p ) ，其中u 为全体样本构成的论域，p 为在样本空间中全部连续属性n e a 的值域圪上形成的所有分割点集合a输出：一个次优划分月p 。数据结构：l ：u i n d ( r ) ，其中三是一个样本序列，并且l 可以根据等价关系i n d ( r 1 被划分为若干互不相交的段，l = 瓯，工：工) 。初始化：r ：庐，l = u ) ；r e p e a tf o r ( e v e r y p 。p ) b e g i nf o r ( e v e r y ，l ) b e g i ni f ( 1 厶l 1 ) b e g i nc o m p u t e l i n d ( p 。) ；c o m p u t e c ( p a ) ；e 1 s ec ( p 。) = 0 ：e n d i fe n d f o rc i ( ) = c ( ) ；e n d f o r选择分割点p 。：c ；( ) = m a x c ： ( p 。) ；p = p p 。，) ；r = r u p 。) ；l = u i n d ( r ) ：u n t i l ( 碟( p 。) = 0 ) o r ( p = )对决策表s ：( u ，爿u d ) ) ，设1 u 户 ， p l = k ，1 4 i k 。在算法3 1 中，由于数据结构三为线性的，因此算法空问复杂度为0 ( + 1 ) 月) 。计算c ( 儿) ，首先需要根据分割点p o 将厶划分为两个不相交的子序列，然后根据公式得到c 。( 风) 值，其计算第二章m d 算法存心- 的问题分析及改进复杂度为o ( 1 ，) ，这里( ，= l l 川。由于，= ”，所以计算c ；( 以) = c ( 风) 的时间复杂度为o ( n ) 。算法最外层循环的每一次执行中，选择分割点p 。需要计算当前分割点集合p 中每一个分割点的c ：( 儿) 值，在最坏的情况下r = p ，最外层循环将执行，次。这样，整个算法的时间复杂度为d ( ! 上型；兰n ) ：o ( k ，2 。) 。根据连续属性上分割点的定义，我们可知k 。( 1 ) ，所咀算法的时间复杂度也可近似描述为o ( k2 n 3 、。以上是关于线性存储m d 一算法的理论依据和算法设计，改进后的算法较原始m d 一算法，在时间、空间复杂度方面均进行了优化，可极大地提高算法的效率。在本文第四章的数据实验中，我们会进一步改进线性存储的m d 一方法【35 1 ，使其可以在一定程度上处理噪声数据，并在大规模数据集应用中为算法增加预处理过程，进一步提高算法效率。3 2 2 一个加权的m d 算法由上述m d 一算法的问题2 可知，造成算法精确度不高的主要原因在于选取一个分割点的时候，只注意到了分割与决策属性之间的关系，而忽略了该分割与其它候选分割之间的关系。一个分割所能区分的样本对，如果存在许多其它的候选分割也能够对该样本对进行区分，那么，该分割对于该样本对的区分能力相对地也就不那么重要了，也就是说，在m d 一算法下，虽然我们选择了区分能力最强的分割，但该分割的区分作用可能被其它的候选分割组合来代替，而该分割却无法代替其它分割的区分作用，这样，该分割就不像m d 算法分析得那样重要。可以这样认为，在每一个步骤中，不仅要寻找区分能力最强的分割，而且要寻找最不可替代的分割。典型的情况如例32 所示，决策不同的样本对( 1 ，2 ) ，( 5 ，4 ) ，( 5 , 6 )只能分别由变量p ? ，p ：，p ；中的划分柬区分，这样，p ? ，p ；，p ；一定存在于最优划分之中，并且我们可以看到，由p ? ，p ：，p ：组成的划分可以区分空间中所有的决策不同的样本对，而在m d 一算法分析下，它们的区分能力都不如拼，但p ? 却不是必须的，即p ? 的区分能力可以被分割p ? ，p ：，p ；组合代替，因此，p ? 的区分能力就不像看起来那么重要。基于以上的分析，我们定义了一个分割的区分能力的计算方法。基于符l 挝集理论的琏续佰属f ，_ l 离散化方法研究设有样本对伍，y ) ，且m ) ，) ，若存在，个分割 p 。，p ， 可以对其进行区分，定义其中任何一个分割对区分0 ，y ) 的重要性为s g ( p ，) = ，( i = 1 2 ，d 。这样，在选取分割对样本空间进行划分时，每个候选分割关于区分能力的重要性定义如下。月?1定义3 3 设p ? 为样本空间中任一属性a 上的任一分割，称s 姆( ) = 厶了_ 为、1，2 1的重要性，其中n ? 为每个分割可以区分的不同决策类的样本对数目，为对于第，个待区分的样本对，所能区分该样本对的分割总数。这样，我们可以设计一个加权的m d 离散化算法。算法3 2 加权值的m d 算法输入：样本空间u输出：一个次优划分r ，初始化为数据结构：一个区分矩阵4 +第一步：根据输入样本空间构建区分矩阵爿+ ；第二步：在区分矩阵爿+ 中寻找所有含有1 个数为l 的行，在d 删除这些行中1 所对应的列，以及改列中所有1 所对应的行，( 即寻找最优划分的核心分割，这些分割是不可替代的1 ，将这些划分并入胄，转至第五步；第三步：在a + 中计算每个分割p 的重要性s 9 0 ) ；计算m a x j 辔0 ) ，最大值对应的分割p 。，) j d a r ：第四步：在爿+ 中删除删应的列，以及列中所有1 所对应的行；第五步：如果a 不为空则转至第三步，否则算法结束通过算法可知，因为m d 一算法每选择一个分割都要遍历当前步骤的决策表a + ，所以，该算法与m d 算法相比，h , i - f i j 复杂度和空问复杂度都没有本质变化，分别为o ( k n 2l r l ) 和o ( k n 2 ) ，但是，划分结果的优化程度却得到了提高，下面，我们将加权的m d 一算法应用于例3 2 。系统中不存在不可代替的分割点，所以，转至下一步骤，计算得月?1蜊m = 萎。寺= h 眠第三币m d 算法存班的问题分析驶改进s i g ( 瑚= ：+s i g ( 硝) 2 +j 喀( p 。h j _ i 1 + ：s t g ( p ! ) = 三+s i g ( p 护1 3 乓s i g ( 鼢= 挂! 一_ 三一_44三+ 三+441 1+ 441 11+ + 4531l牟牟=3311上牟=33可得p 。= p ? ，在区分矩阵中删除p ? 对应的列，以及其中1 所对应的行，得到新的区分矩阵。继续计算可得m a x s i g ) ) = s i g ( p ：) = 1 1 1 ，在矩阵中继续删除，这时区分矩阵为空，算法终止。这样，我们得到了一个次优划分p ? 八p ：，由例3 ，1可知，这个次优划分就是样本空间的最优划分。同样，我们将加权m d 一算法应用于例3 2 ，也可得到优于原始m d 一算法的离散化结果。3 2 3 一个基于相似性的m d 算法由以上分析，我们知道，在候选划分集合中选取划分，不仅要注意该划分的区分能力，而且要注意各个候选划分之间的相关性，即要选出最不可替代的划分。算法3 2 使用了加权值的方法来计算划分的重要性，下面我 f i n 用模式识别理论中相似性测度方法中的匹配测度来计算一个划分的重要性。如何衡量一个划分的不可替代性呢? 如果一个划分的区分能力与其它划分的区分能力很相近，那么它通常很可能可以被其它划分组合代替，反之，则该划分不易被替代。在区分矩阵a 中，每个候选划分p 对于待划分的样本空间的划分信息为一个n维向量x = ( x ) = ，若第f 个样本对可以被p 区分，则x ，= 1 ，否则x ，= o ，这里n 表示a 中决策类不同的所有样本对总数。设x ，y 分别为两个不同候选划分所对应的n维向量，令d = x ，y ，b = 儿( 1 一x i ) ，c = x ，( 1 一y ，) ，e = ( 1 一x ，) ( 1 一h ) 。显然，a 为两向量x 与y 的( 1 1 ) 匹配的特征数目，b 为两向量x 与y 的( 0 1 ) 匹配的特征数目，c 为两向量x 与y 的( 1 0 ) 匹配的特征数目，p 为两向量x 与y 的( o o ) 匹配的特征数目。这样，我们可以利用t a n i m o t o 相似测度3 6 1 柬定义两划分对应的向量x ，y 的区分能力的相似度。脚筋bk卸叫腻乏= 三，一；。一。孔爿；!川基于耗1 糙集理论的琏续值属性离散化方法研究定义3 4 设z ，y 分别为划分点p ，q 对应的划分信息向量，定义p ，g 的相似度为她护百忌2。：一，这里x 1 ，。表示x ，y 的转置。x x4 - y y z y可以看出，s ；q ) 的分子部分只考虑( 1 - 1 ) 匹配，即两划分重复的区分能力，而分母为两个划分的区分能力之和。即两划分可区分的全部对象对的数目。所以，相似度s 慨9 ) 就是p ，q 之间重复的区分能力在两者共有的区分能力中所占的比重。定义3 5 设苴，y ，y 。分别为p ，q ，吼对应的划分信息向量，定义p 与划分z s ( p ；q ，)族 g i ，q ) 的相似度为s ( p ；q ”，g 女) = _ _ 。尼事实上，我们定义一个划分与一族划分的相似度为该划分与该族划分中每一个划分的相似度的加权和。定义3 6 设”。为划分p 可区分的样本对数，即p 对应区分向量中含1 的个数，定义划分p 相对于划分族 q ，q 。) 的重要性为s g ( p ；q ，q 。) = _ 二-5 u ，；q l ，g j利用上述的划分相似性概念，我们可以设计一个基于相似性的m d 算法。算法3 3 基于相似性的m d 算法输入：样本空间c ，输出：一个次优划分r ，初始化为数据结构：一个区分矩阵彳第一步：根据输入样本空间构建区分矩阵a ；第二步：在区分矩阵a + 中寻找划分的核心分割并入尺，在a 中删除其对应的列及已区分的样本对，然后转至第五步：第三步：在a + 中计算每个5 y ：9 4 p 的相似度j 佃；g ，q 。) ，进而求得其重要性j 喀p ；q ，q ) ；计算m a x s 喀0 ；g ，q 女) ) ，得到最大值对应的分割p 。加入r ；第四步：在a + 中删除删应的列以及列中所有】所对应的行；第五步：如果a 不为空则转至第三步，否则算法结束。与算法3 2 相比，本算法的时间复杂度和空间复杂度也没有本质变化，分别为0 ( k n2 lr1 ) 和0 ( 砌2o 将算法33 分别应用于例3 1 ，例3 2 ，可以得到优于原始m d 。算法结果的次优划分。第四章仿真实验分析第四章仿真实验及结果分析数据离散化的根本目的是在尽量不损失原始数据中分类信息的前提下，在属性的连续值域上寻求最优划分，并依据获取的分割点集转换数据集的连续属性值域为离散型值域，然后对离散化取值的数据集进行处理，去除冗余数据( 即对于分类学习完全相同的信息) ，实现数据压缩。因此，依据实验数据，主要从以下几个指标评价离散化方法的性能。1 离散化方法的数据压缩能力：即离散化后的数据集规模与原始数据集规模之比。2 离散化方法的精度：即离散化数据较之原始数据的分类信息损失程度，这一指标通过离散化后数据集中所含不协调信息的比例来体现。3 离散化方法的稳定性：即算法在不同类型的数据类别分布情况下的离散化结果是否稳定，以及对于相似的类别分布数据集，算法所获划分是否也相似。4 离散化算法的效率：由于按照分割点对数据集合离散化取值的时间损耗只与选取的划分点规模以及原始数据集规模有关，因此各种方法在这一步骤中的效率对比意义不大，算法的效率主要体现在分割点的选取步骤中。4 1 实验设计41 1 实验数据课题采用中国科学院地理科学与资源研究所提供的遥感影像作为实验数据。遥感影像由美国陆地卫星5 号( l a n d s a t5t m ) 于1 9 9 9 年8 月2 8 日在我国黄河三角洲地区摄取，影像区域位于山东省东营市和滨州市的交界地带，影像尺寸为5 1 5 5 1 5 像素，空间分辨率3 0 m ，左上角经纬度坐标分别为1 1 8 。0 3 40 7 ”e ，3 7 。2 2 2 4 0 0 ”n ：右下角经纬度分别为1 1 8 。1 0 5 28 3 ”e ，3 7 。1 3 5 813 ”n 。图像信息中每一个单位象素具有七个不同的波段信息值( 每个波段的值是光谱辐射量化值，也叫d n 值) 。由象素点波段值的信息，利用相应的机器学习算法( 课题中采用极大似然分类方法) ，可以对信息点的地表类型进行预测。由以上描述的遥感影像信息可以对应生成具有七个条件属性( 对应七个波段信息) 和一个决策属性( 对应地表类型) 的数据集合。实验采用的遥感影像如图4 1 所示。基于辑1 糙集理论的连续值属件离散化方_ ) 圭 j j f 宄图4 1 黄河三角洲地区遥感影像表4 1 和表4 2 分别表示遥感影像生成数据集的条件属性和决策属性信息。表4 1 条件属性值域类型及取值范围属性名称数值类型值域范同波段1 ( b a n d l )非负整数 9 6 ，1 6 9 波段2 ( b a n d 2 )非负整数 3 4 ，7 5 波段3 ( b a n d 3 )非负整数【3 3 ，1 0 5 】波段4 ( b a n d 4 )非负整数 2 2 ，1 3 8 】波段5 ( b a n d 5 )非负整数【1 0 ，1 7 4 波段6 ( b a n d 6 )非负整数 1 2 7 ，1 4 9 波段7 ( b a n d 7 )非负整数【4 ，1 2 4 】表4 2 决策属性类别及其真实含义类别值地表类型1w a t e r2a g r i c u l m r e13a g r i c u l t u r e24u r b a n5b o t t o m i a n d6b a r eg r o u n d第旧章仿真实验分析遥感影像生成样本空间为一个决