（计算机应用技术专业论文）基于粒度计算的分类方法研究.pdf

基于粒度计算的分类方法研究 摘要 知识发现( k d d ，k n o w l e d g ed i s c o v e r y i nd a t a b a s e ) 是从数据中获取知识的一种智 能信息处理技术。分类是数据挖掘的重要组成部分，它根据类标号已知的数据建立模型， 进而使用该模型来预测类标号未知的数据所属的类。 粒度计算的思想产生于2 0 世纪7 0 年代，它的基本思想是模仿人类思考阿题的方式： 即人们能从极不相同的粒度上观察和分析同一问题，而且能够很快地从一个粒度世界跳 到另一个粒度世界，往返自如，毫无困难。近年来，人们开始将粒度计算应用到数据挖 掘领域中，并初步取得了一些成果，成为当前数据挖掘领域一个新的研究方向。 本文的主要工作是将粒度计算引入数据分类中，做了一些相关的研究，主要的研究 内容包括： 1 、本文较全面和深入地探讨了数据分类问题，讨论了分类的内涵( 分类器构造) 、 外延( 特征选择和规则提取) 和本质，并针对数据分类问题的难点，研究了分类器构造 的粒度变换与计算问题。 2 、本文探讨了分类算法的粒度原理，利用粒度计算理论，独立于具体算法，展开 对基于粒度计算理论的数据分类建模的研究，以探讨信息系统中知识形成的一般性规律 和内在机制 3 、研究了不完备信息系统的分类问题。根据人的认知规律，即人类可以利用有限 的知识，在较浅层次上获取比较满意的结果，避免了知识深层次上的不完备性的特点。 利用商空间粒度计算理论和r o u g hs e t 相结合的办法，对缺省属性样本进行投影和粗粒 度处理，使得投影后的系统成为决策一致性系统。这样尽可能利用现有已知样本，采用 多层次的处理方法解决了不完备信息系统的分类问题，克服了现有大多数算法只能应用 于完备信息系统的分类问题，扩大了分类器的应用范围。 本文的创新点主要表现在： 1 、定义了集合的粒度表示，导出一个基于粒度计算理论的数据分类建模。 2 、将粒度计算模型和r o u g hs e t 相结合应用于解决不完备信息系统的分类问题。 关键词：知识发现，粒度计算，分类，信息系统 r e s e a r c ho nm e t h o d so fc l a s s i f i c a t i o nb a s e do n g r a n u l a r c o m p u t i n g a u t h o r ：s h e nq i n ga d v i s o r ：h a nx i e a b s t r a c t k d d , k n o w l e d g ed i s c o v e r y i n d a t a b a s e , i san o v e lt e c h n o l o g yo fi n t e l l i g e n t i n f o r m a t i o np r o c e s s i n gf o rk n o w l e d g ed i s c o v e r yi nl a r g ed a t a b a s e c l a s s i f i c a t i o ni sav e r y i m p o r t a n tt a s ki nd a t am i n i n g i tb u i l d sam o d e la c c o r d i n gt ot h ed a t aw h o s ec l a s sl a b e l sa r e k n o w n , a n dt h e nu s e st h i sm o d e lt op r e d i c tt h ec l a s s e so ft h ed a t aw h o s oc l a s sl a b e l sa r c u n k n o w l l t h ei d e ao fg r a n u l a rc o m p u t i n gw a se m e r g e di n1 9 7 0 s i t sm a i ni d e ai st oa n a l o g yt h e m a n n e ro fp e o p l e st h i n k i n g t h a ti sp e o p l ec a no b s e r v ea n da n a l y s i sp r o b l e mf r o mq u i e t d i f f e r e n tg r a n u l a r i t y , a n d 锄e a s i l yt r a n s f e rf x o mo n eg r a n u l a r i t yw o r l dt oa n o t h e r i nr e c e n t y e a r s ，p e o p l eh a v eb e g u nt oa p p l yg r a n u l a rc o m p u t i n gt od a t am i n i n g , a n da c h i e v e ds e i n e g o o dr e s u l t s i th a sb e c o m ean 鲫a n dp r o s p e c t i v er e s e a r c ht o p i ci nd a t am i n i n g 。 i nt h i st h e s i s , w ea p p l yg r a n u l a rc o m p u t i n gt oc l a s s i f i c a t i o na n d 由s o m e ：p r i m i t i v e r e s e a r c h o u rw o r km a i n l yi n c l u d e s ： 1 i nt h i st h e s i s , t h ea u t h o rc a r r i e so u tad e e pa n dc o m p r e h e n s i v ea n a l y s i st o w a r d s c l a s s i f i c a t i o np r o b l e m ：d i s c u s s i n gi t si n t e n s i o n ( c l a s s i f i e rc o n s t r u c t i o n ) ，e x t e n s i o n ( f e a t u r e s e l e c t i o n , r u l ee x t r a c t i o n ) a n dn a t n r e a n dt h et h e s i sa l s oc o n c e n t r a t e so np r e s e n th o t r e s e a r c hi s s u e so fc l a s s i f i c a t i o n , t h e ns t u d yt h eg r a n u l a rc o m p u t i n gi nc l a s s i f i e rc o n s t r u c t i o n 2 w ed i s c u s st h eg r a n u l a rp r i n c i p l eo fc l a s s i f i c a t i o n f i r s t , i n d e p e n d e n to fi d i o g r a p h i c a l g o r i t h m s ，d a t ac l a s s i f i c a t i o nm o d e l i n gb a s e do ng r a n u l a rc o m p u t i n gi ss t u d i e dw i t hg r a n u l a r c o m p u t a t i o na f t e rs y s t e m a t i c a l l yr e v i e w i n gr e l a t e dw o r k ；a n dr u n - o f - m i l ll a w sa r ed r o w n o u t 3 t h ec l a s s i f i c a t i o no fi n c o m p l e t ei n f o r m a t i o ns y s t e m si ss t u d i e d a c c o r d i n gt ot h e h u m a nc o g n i t i v er u l e s p e o p l ec a nu t i l i z el i m i t e dk n o w l e d g et oo b t a i nr a t h e rs a t i s f a c t o r y r e s u l t sa tav e r ys i m p l ek n o w l e d g el e v e li no r d e rt oa v o i dt h ei n c o m p l e t ei n f o r m a t i o na ta d e e pk n o w l e d g el e v e l b a s e du p o nt h i sr o l e ，a l la l g o r i t h mi sd e v e l o p e dw h i c hc o m b i n e st h e u s e so ft h eg r a n u l a r i t ym o d e li nt h eq u o t i e n ts p a c et h e o r ya n dt h er o u g hs e tt h e o r y a f t e r p r o j c o t i n ga t t r i b u t e s ，t h es a m p l e sa r ep r o c e s s e dw i t hr o u g hg r a n u l a rt op r o v i d ead e c i s i o n c o n s i s t e n c es y s t e m s t h i sa l g o r i t h me n a b l e sc l a s s i f i c a t i o no fa l li n c o m p l e t ei n f o r m a t i o n s y s t e mb yu t i l i z i n g t h ee x i s t i n gs a m p l e sa t h i e r a r c h yl e v e l s i t t h e r e f o r er e d u c e st h e l i m i t a t i o n so fm o s tc u r r e n ta l g o r i t h m st h a tc a no n l yb ea p p l i e di nt h ec l a s s i f i c a t i o no f c o m p l e t ei n f o r m a t i o ns y s t e m s a sc o n s e q u e n c e ，t h ep r o p o s e da l g o r i t h ms h o u l de x p a n dt h e a p p l i c a t i o ns c o p eo fs u c hc l a s s i f i e r sw h i c ha r eu s e dt oc l a s s i f i e rt h ec o m p l e t ei n f o r m a t i o n s y s t e m m a i nc o n c l u s i o n sa n ds i g n i f i c a n c e so ft h i st h e s i sa l ea sf o l l o w i n g ： 1 ad a t as e ti se x p r e s s e di ng r a n u l a rf o r m sa n dt h e nd a t ac l a s s i f i c a t i o nm o d e l i n gi s e d u c e db a s e do i lg r a n u l a rc o m p u t i n g 2 t h ec l a s s i f i c a t i o no fi n c o m p l e t ei n f o r m a t i o ns y s t e m si ss o l v e db yc o m b i n i n gt h e g r a n u l a r i t ym o d e la n dt h er o u g hs e tt h e o r y k e y w o r d s ：k d d ，c l a s s i f i c a t i o n ，g r a n u l a rc o m p u t i n g ，i n f o r m a t i o ns y s t e m 原创性声明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 论文作者签名：壹蝠日期：旦2 ：丝 关于学位论文使用权的说明 本人完全了解中北大学有关保管、使用学位论文的规定，其中包 括：学校有权保管、并向有关部门送交学位论文的原件与复印件； 学校可以采用影印、缩印或其它复制手段复制并保存学位论文； 学校可允许学位论文被查阅或借阅；学校可以学术交流为目的，复 制赠送和交换学位论文；学校可以公布学位论文的全部或部分内容 ( 保密学位论文在解密后遵守此规定) 。 签名： 立通 日期：丑：! 。旦 导师签名：二；釜二￥ 中北大学学位论文 1 绪论 随着数据库技术的成熟和应用的普及，人类积累的数据量以指数级速度迅速增长； 并且随着社会各领域中信息的数字化建设，日益增长的科学计算和大规模的工业生产过 程产生了海量数据。数据量的这种爆炸式的增长速度已经远远超过了人们解释、分析和 消化数据的能力。于是，相对于“数据过剩”和“信息爆炸”，奈斯伯特( j o h nn a i s b e t t ) 惊呼“w ea r ed r o w n i n gi ni n f o r m a t i o n , b u ts a a r v m gf o rk n o w l e d g e 1 b ( 人类正被数据淹没， 却饥渴于知识) 面临浩渺无边的数据，人们呼唤从数据的汪洋去租取精、去伪存真的技术。面数据 库知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e s ，k d d ) 【2 l 及其核心技术数据挖掘 ( d a t am i n i n g ，d m ) 【3 j 便应运而生了。普遍认为k d d ：数据预处理+ 数据挖掘+ 解释评估。 而目前数据预处理技术和解释评估的方法都已经研究比较成熟，所以目前k d d 的研究 热点和关键问题都集中在数据挖掘上。 1 1k d p 的产生与发展 不缺信息缺知识。随着数据库技术的成熟和信息应用的普及，人们积累的信息量正 在指数地增长。全世界每天存入数据库的数据量超过万兆字符。虽然人们拥有太多的数 据，但总嫌知识不够。面对这种新的挑战，数据库知识发现( 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 , k d d ) 及其核心技术数据挖掘( d a t am i n i n g , d m ) 技术应运而生，并显示出强 大的生命力。 数据挖掘技术是一个年轻且充满希望的研究领域，商业利益的强大驱动力将会不停 地促进它的发展，每年都有新的数据挖掘方法和模型闯世，人们对它的研究正日益广泛 和深入。 1 9 8 9 年8 月，在美国底特律召开的第1 1 届国际人工智能联合会议的专题讨论会上 首次出现k d d 这个术语。随后在1 9 9 1 、1 9 9 3 和1 9 9 4 年都举行了k d d 专题讨论会， 汇集来自各个领域的研究人员和应用开发者，集中讨论数据统计、海量数据分析算法、 1 中北大学学位论文 知识表示、知识运用等问题。髓着参与人员的不断增多，国际k d d 组委会于1 9 9 5 年把 专题讨论会更名为国际学术大会，并在加拿大蒙特利尔市召开了第一届知识发现和数据 挖掘国际学术会议( k d d - 9 5 ) ，以后每年召开一次，规模由原来的专题讨论会发展为国际 学术大会，参加人数也是逐年增多，2 0 0 6 年第1 2 届国际k d d 会议( k d d - 2 0 0 6 ) 于2 0 0 6 年8 月在美国费城召开。亚太地区也于1 9 9 7 年在新加坡组织召开了第一次规模较大的 k d d 学术研讨会( p a k d d - 9 7 ) ，此后p a k d d 每年召开一次，2 0 0 6 年第l o 届亚太知识 发现与数据挖掘会议( p a k d d 2 0 0 6 ) 于4 月9 1 2 日在新加坡召开。目前，在d c a i 、a a a i 、 v i d b 、a c m - s i g m o d 等代表人工智能与数据库技术研究最高水平的国际学术会议上， 对k d d 的研究都占有较大的比例，k d d 已经成为当今计算机科学与技术研究、应用的 热点领域之一。 i 2k d d 的处理过程模型 目前人们对整个k d d 处理过程并没有给出非常清楚的划分，而建立合适的处理过程 模型能将各个处理阶段有机地结合在一起，以便于人们开发及使用k d d 应用系统。比 较有代表性的模型有三种； 第一种是u s a m am f a y y a d 等人给出的多处理阶段模型。 第二种是g e o r g eh j o h n 给出的多处理阶段模型【4 】。 第三种是b m c h m a n & a n a n d 提出的以用户为中心的处理模型。 图1 1 是u s a m af a y y a d 等人给出的处理模型。该处理模型把k d d 过程分为九个处 理阶段：任务理解、数据选择、数据预处理、数据规约、k d d 目标确定、挖掘算法确 定、数据挖掘、模式解释闸：价及知识表示脸并。 i 任务理解：了解k d d 相关领域的有关情况，包括实际应用中的预备知识和目标， 熟悉有关的背景知识，并弄清楚用户的要求。 2 数据选择：根据用户要求从任务相关数据库中提取与k d d 要求相关的数据，k d d 主要从这些数据中进行知识提取。在此过程中，会使用一些数据库操作对数据进行处理， 建立一个目标数据集。 2 中北大学学位论文 图1 1k d d 的处理过程模型 3 数据预处理：主要是对数据选择阶段产生的数据进行再加工，检查数据的完整性 和一致性，利用统计方法等对丢失的数据进行填补，去除噪音数据和空白数据域，考虑 时间顺序和数据变化等。 4 数据转换：对经过预处理的数据，根据知识发现的任务对数据进行再处理，主要 通过投影或数据库中的其他操作减少数据量或找到数据的不变模式。 5 确定k d d 目标：根据用户要求，确定k d d 发现的知识类型，因为对k d d 的不 同要求，会在具体的知识发现过程中采用不同的知识发现算法。 6 确定知识发现算法：根据确定k d d 目标阶段所确定的任务，选择合适的数据挖 掘算法，包括选取合适的模型和参数，并使得挖掘算法与整个k d d 的评判标准相一致。 7 数据挖掘：运用选定的挖掘算法，搜索或产生一个特定的感兴趣的模式或数据集， 从数据中提取出用户所需要的知识，这些知识可以用某种特定的方式表示或使用一些常 用的表示方式，如产生规则等。 8 模式解释、评价：对发现的模式进行解释，去掉多余的不切题意的模式，转换成 某个有用的模式，以便于用户理解。在此过程中，为了取得更为有效的知识，可能会返 回前面处理中的某些步骤，以便反复提取，从而提取出更有效的知识。 9 知识表示、合并：将发现的知识以用户可理解的方式呈现给用户或合并到系统中， 也包含对知识的一致性检查。 3 中北大学学位论文 在上述的每个处理阶段，k d d 系统提供处理工具完成相应的工作。在对挖掘的知 识进行评测后，根据结果可以决定是否重新进行某些处理过程，在处理的任意阶段都可 以返回到前面的某个阶段进行再处理。 1 3 知识发现与数据挖掘 知识发现的过程是一个反复迭代的过程，在任何一步，如果没得到满意的结果，都 可以返回前一步，直到有满意的结果为止。在上述的几个步骤中，数据挖掘是知识发现 过程的核心内容。实际上，在k d d 系统的实际开发当中，往往不是严格按照图1 1 所 示的步骤去设计。而是根据问题的具体情况来对上述步骤进行取舍或和合并，更多时 候是把k d d 的处理过程分为三个过程阁。第一是数据准备，主要目标是对原始数据的 格式等进行转化，变成挖掘算法可处理的格式：一旦数据被格式化，就可以对其应用多 种算法从数据中抽取模式、规则，或一般性规律，这一过程就是知识发现的核心步骤 数据挖掘；第三是结果后处理，其目标是对数据挖掘过程产生的结果进行进一步的 转化，形成多种可理解的形式。 严格说，数据挖掘( d m ) 是知识发现( k d d ) 的一个步骤，它是由具有多项式时 间( 可接受的计算时间) 的算法组成旧。但是，目前很多算法在功能上已经远远超过了 数据挖掘当初所界定的范围，因此数据挖掘往往被当作知识发现的同义词。也就是说， 只有“知识发现”才能较好地概括当今在“从数据中抽取知识”的这一研究领域里所涵 盖的理论、技术和方法。 1 4 知识发现方法的研究现状及面临的挑战 1 4 1 知识发现方法的研究概述 知识发现是一种多领域交叉性学科，它综合了统计学、a j 、数据库技术、机器学习、 可视化技术和信息论等学科和技术。其研究方法可从相应的这些领域中探讨。 ( 1 ) 统计分析方法 统计分析方法是知识发现最早使用、也是经典和最成熟的方法，它是数据库技术和 统计学相结合的结果。典型的例子是a p r i o p r i 算法，它主要运用于发现关联规则，并且 4 中北大学学位论文 在很多领域中得到了成功的应用。其原理是，通过对数据表的各属性进行统计，找出它 们之间的关系( 函数关系，或者相关关系) ，然后采用回归分析、相关分析、主成分分 析等方法。 实际上，知识发现的大多方法都是基于统计学的基本原理，它是知识发现研究的重 要理论基础。 ( 2 ) 决策树方法 决策树算法最早由q u i n l a n 于1 9 7 9 年提出的，这就是著名的m 3 ( 7 l 算法。随后，他 又提出i d 3 的改进算法c 4 5 算法旧。这两个算法奠定了数据分类算法的基础。其后 提出的许多分类算法都是在这两个算法的基础上进行改进，或者说是这两种算法的变 种。但是这两种算法及其一些变种版本，还存在一些不足之处：( a ) 伸缩性不强。对于 相对较小的数据集，它们是很有效的，而对于现实世界中大型数据库，其有效性却大为 降低。这是因为当训练集很大时，它无法同时全部驻留内存，使得算法在学习时，不断 进行主存和外存的换进换出；( b ) 可调性差，对噪音敏感。算法在树的每个节点上的信 息增益( i n f o r m a t i o ng a i n ) 作为节点分裂的优良性度量，选择具有最高信息增益的属性作 为当前节点的测试属性。这样，一边构造一边评价和分裂，一旦做出“决定”就没有“悔 改”的可能。所以构造出来的决策树在内容和结构上很难得到有效的修改和调整；( c ) 仅以信息增益度量作为启发信息，缺乏全局搜索策略，结果很难得到最优的决策树。 目前，研究的重点主要是针对上述问题展开的，旨在提高决策树的精度，减少决策 树的规模、提高其处理大数据集的能力、设计增量式算法以及多变量决策树等。 ( 3 ) 神经网络 神经网络( n n ，n e u t r a ln e t w o r k s ) 模型的构造涉及两方面问题，一是网络拓扑结构的 辨识；二是网络权值的学习【9 l 。一个网络要选择什么样的拓扑结构，一般是没有统一的 标准，只能视具体问题而定。神经网络可以实现从p 维空间到q 维空间的非线性映射， 具有很好的函数逼近能力，而且所有决策树都有等价的人工神经网络表示。所以用已训 练过的神经网络做分类器，有其独特的优势，在很多方面都得到很好的应用。与基于决 策树的方法相比，基于神经网络的方法具有更小的分类出错率；不同的是，抽取的时间 消耗比基于决策树的方法长。 ( 4 )( 朴素) 贝叶斯分类法 5 中北大学学位论文 严格说，贝叶斯分类法是统计学分类方法。它是一种对无条件数据限制其输入的技 术。朴素贝叶斯分类是基于这样的假设：一个属性值对给定类的影响独立于其它属性的 值，并把实验中观测到的频率作为条件概率。这种分类法可以与决策树和神经网络分类 法相媲美，用于大型数据库，贝叶斯分类也已表现出高准确率与高速度。但上述假设要 求过强，在现实中一般难以满足。 ( 5 ) 模糊集和粗糙集方法 分类方法大多都是基于一种测度进行。例如，如果某样本的测度大于或等于某一个 阈值，则该样本属于某一类，面如果小于该阈值则该样本属于另一类。那么，如果大于 或等于3 5 岁的为中年人，小于3 5 岁的为青年人，则出现这种情况：3 4 岁和3 5 岁的人 分别属于青年和中年两个不同时代的人。这显然难以接受为解决这种“截断”的分类方 法，人们引入模糊集的方法。其基本思想是，首先将数值属性值映射成模糊值；该模糊 值匹配多个模糊规则；然后对被匹配规则的后件转换后采用加权平均值作为返回值。该 方法已在工业当中得到了很大的应用。不过该方法一般是和别的方法结合使用。 模糊集可以表示模糊的概念，但是模糊集本身是不可计算的。1 9 8 2 年，波兰数学家 p a w l a k 提出了粗糙集皿s ，r o u g hs c t ) 的概念【1 0 l 。他把模糊元素归属于边界区域，使得模 糊元素变为可数。这样，任一个模糊概念都可以用数学公式进行描述，可进行理论分析 和论证。对处理不精确、含糊的数据，这种方法具有独特的优势；弗且r s 方法在处理 模糊概念时不需要数据以外的其它信息( 如隶属度等) ，有效发现数据中蕴涵的有用模 式，易于并行化等【1 1 1 自从s k o w r o n 提出分辨矩阵1 1 习以来，r s 理论以其这种优势引来 了许多学者的广泛关注。特别近年来，在知识发现领域中r s 逐步成为研究的重要理论 工具。 旧可视化技术 可视化技术为用户和k d d 系统的相互交流提供一种接口。它是把数据、信息或知 i 9 , - 转化为理解的表示形式，如直观图。该技术可以有效地把人的智能和洞察力跟k d d 系统有效地结合起来，提高知识发现的速度和知识的质量。 实际上，很多方法都是与其它方法结合使用的，这要根据实际应用需要而定。 6 中北大学学位论文 1 4 2 面临的一些挑战 k d d 算法的效率问题 当今，由于信息技术应用的普及，许多商务活动以及科研工作都被“数字化”了， 工作的每一个状态及其结果都以数字的形式保存下来，这样海量数据的出现就在所难 免。对海量数据的智能分析和处理将是今后信息社会的一个基本任务。实践表明，决策 树方法以及粗糙集方法等对于小数据集是很有效的，但对于海量数据处理，决策树方法 以及粗糙集方法等一些贪心算法就显得力不从心了。一方面，这些方法容易产生局部解； 另一方面，其计算时间往往是不能接受的( 一般是非多项式时间) ，效率很低。实际上， k d d 算法的效率是伴随着k d d 的诞生而一直受到关注的。一种k d d 产品能否得到推 广应用，除了其准确率以外算法的效率同样起着非常重要的决定作用。为此，人们对 k d d 算法的研究一直是坚持不懈的努力，试图找到一种高效的k d d 算法。虽然在这些 方面取得了一定的成果，但是要在一个数量级上降低算法的复杂度，却是一件非常困难 的事情。所以，当样本数量增加时，算法的运行时间就会急剧增加，使得发现任务无法 在可忍受的时间内完成。可以说，不管是过去、现在还是将来，算法效率都是研究者必 须面对的一个极具挑战性的问题。 “发现用户感兴趣的知识” k d d 算法容易从数据库中产生大量的知识，这些知识都能揭示数据所蕴涵的一些 新颖的“规律性的东西”但是不同的用户，其所感兴趣的知识一般是不同的。对既定 的用户而害，其中大多数模式对用户是没价值的。这种“发现用户感兴趣的知识”的研 究难度在于，如何构造用户对知识感兴趣程度的度量函数( 知识评价) 兴趣度函数， 因为这不但与用户的领域知识有关，而且与他的兴趣和爱好等因素都有关，具有很大的 主观成分，需要加入用户的领域知识和个人喜好；另外，用户的这些主观因素的表示以 及如何把它们更为有效地融入知识发现过程中，指导算法进行定向发掘，找出用户感兴 趣的知识，去掉多余的信息，这是至关重要的一环。对此，目前未有很好的解决办法， 有待于进一步的研究。 k d d 算法的局部收敛性和局部知识的产生问题 在k d d 研究当中，很多算法是由机器学习( m l ) 算法( 包括决策树等) 改进而来的。 7 中北大学学位论文 这些算法对小数据集显示出较强的性能，但对于大数据集基于m l 的贪心的k d d 算法 易于得到局部最优解i 埘，而且效率很低。即使采用或结合一些智能的计算方法，如神经 网络和进化计算等，虽然对测试集获得较高的分类准确率( 甚至达到1 0 0 ) ，但是这并 不代表它们在实际应用中仍然具有较高的准确率。因为这些算法本身就存在着局部收敛 的问题，当把它们用于更大的“测试集” 垂际系统的未知数据时，知识的局部特性 就会表现出来了准确率急剧下降。所以，许多算法在走出实验室以后就失去了其应 用的价值。但是，局部收敛性在很多算法研究中都是尚未得到有效解决问题，如何攻破 这一难题是避免k d d 算法产生局部知识的一个关键因素。 知识发现的基础理论 在知识发现研究中，许多理论和方法的证明一般是求助于统计学，它没有形成自己 较为完善的代数和几何理论体系。这导致在算法设计过程中缺少必要的理论指导，而只 能凭借经验，这非常不利于k d d 研究的进一步发展。当前，r s 理论已经成为k d d 研 究和开发的一个有力工具。在这方面，张文修教授等对粗糙集的扩展模型以及公理化方 法进行了系统的理论研究i 埔均。王国胤教授等讨论了r o u g h 集理论的代数观和信息双两 种形式的关系，并得出了一些经典理论观点存在缺陷的根本原因：在信息论和r s 理论 的结合方面做了深入的研究【1 6 - t 9 。但是，这些工作主要限于粗糙集方面，而且作为处理 模糊和不确定性信息的数学工具，它对于不确定性的度量和粗糙性的量化研究却缺少必 要的理论，这对知识的定量分析非常不利。 ： 其它 除上述几个方面以外，其它挑战性的问题还包括，开发k d d 查询语言及查询优化 技术、基于非完备系统( 包括多表、高维) 的知识发现、增量挖掘算法的研究、基于流 量的知识发现以及基于复杂类型数据( 包括非结构化数据、视音频数据等) 的知识发现 和有效的知识发现过程和结果可视化技术等。 总之，在众多科研人员的努力下，经过十多年的发展，知识发现在各方面虽然取得 了较大的成绩，但在许多方面尚存在待解决和完善的地方。这需要我们进一步加大研究 力度，提高和完善信息社会意义下的智能信息处理技术。 8 中北大学学位论文 1 5 分类问题的内涵与本质 1 5 1 分类问题的一般概念 分类是数据挖掘领域中最为重要的一类问题。许多挖掘问题本质上都可以等价地转 化为分类问题。分类可以描述如下： 类别已知的样本构成数据集，数据集一般被划分为训练集( t r a i n i n gs e 0 和测试集 ( t e s ts e t ) 每个样本有多个属性( a t t r i b u t e ) 或称特征t f e a t u r e ) ，属性既可以是连续属性， 也可以是离散属性其中有一个属性被称为类别属性( c l a s sl a b e l ) ，用来标明该样本所 属的类另| i 。 所谓分类就是：通过对训练集的学习，用样本的其它属性建立一个划分类别属性的 模型( 这被称为分类器训练) 。然后用测试集来评价模型的准确率( 这被称为分类器测 试) ，被评价为准确的模型便可以对新数据进行分类。这实际上是将训练数据间的共性 与个性具体化、形式化，并给出一个确定的、可操作的描述。这个训练和测试的过程被 称为分类器构造。在分类器构造中，测试只是一个评估的过程，而训练是最为重要的。 下面来看一个分类的具体例子。图1 2 给出了一个数据集的例子，图中每个样本是 一个车辆保险申请单，它给出投保人的年龄、投保的车型这两个属性的取值，然后会有 若干相关保险专家，根据每个投保人的这些特征，来指定这份保单是属于高风险类还是 低风险类。现在我们有了已经给好风险类型的训练集和测试集，我们关心的是，到底有 哪些属性，它们是怎样决定了一个申请是高风险的，还是低风险，怎样利用训练集来构 造出这个分类的模型，一旦此模型建立就可以划分一个新申请的风险类别。 分类被广泛应用于金融信用评级、目标市场分析、仓储地点选择、药物疗效分析和 医疗诊断等诸多领域。在数据挖掘出现之前，分类就已经是系统辨识、模式识别、归纳 学习中的重要的研究领域。 9 中北大学学位论文 1 5 2 分类问题的数学机理 年龄车型风险 2 3 轿车高 1 7 跑车高 4 3跑车高 6 8 轿车低 3 2 货车 低 2 0 轿车高 图1 2 数据集的一个例子 从更深入的观点来看，分类器构造的方法都是通过对训练集中样本数据的学习，尽 可能从中得到事先未知的、隐藏于数据中的重要信息分类器判别函数。然后选定一 种带有参数的模型函数，通过学习确定模型函数的参数，用它来直接或间接地拟合或逼 近分类判别函数，这一过程就是分类器的训练( t r a i n i n g ) 。下面我们给出一个分类器构造 的数学定义。 所谓分类，从数学上讲，就是在分类判别函数f 事先未知的情况下，利用含有n 个 样本s i ，m 个属性( 或称为特征) q 的训练集s i ( c 1 ，c , z ，c - m ；d ) ，( i = 1 ，神。构造一个特 征域空间( c l ，到类别域衲空间的跌射或称模型【刎函数g 来拟合或逼近类判别函 数f 。 实际上可以用数学中泛函的观点来统一的看待分类问题，设x 是一个无限维赋范函 数空间，分类判剐函数f e x ，有限维真子空间gcx ，分类器的调练就是在子空问g 中找到g e g ，使得： ， l ，一g i 一赌占0 这里是函数空间x 的范数。有了这个观点，相关的泛函分析的知识就可以应用 到分类问题的研究中。 在分类的相关研究中，一个重要的方向就是不断提出各种分类器构造的方法模型。 1 0 d“ o 1 2 3 4 5 中北大学学位论文 目前为止，国内外已有很多分类器构造的方法模型。实际上，一种分类器构造的方法模 型就对应着一个有限维真子空间g ，由相关的泛函分析知识我们知道： 定理1 1 如果我们适当地选择模型，使得f g ，那么g 一f ，这时，l ，一g 9 - 0 。 定理1 1 说明模型构造方法的重要性，一种好的模型可以在理论上保证分类判别函 数f 可以被毫无误差的拟合。正因为如此，国内外的学者才会不断提出新的模型，以便 能够得到更好的分类器构造方法，实际上这些研究就是不断给出新的真子空间g 和它们 的生成方法。 另外，由于赋范函数空问是无限维的，而真子空问g 是有限维的，因此，根据泛函 分析的知识可以知道， 定理1 2 不可能存在一个g ，使得：v f 墨f e g 。 定理1 2 说明不可能有一个一劳永逸的模型，在各种类型的数据集上的分类结果均 好于其他的模型。这也就说明了为什么很多学者的实验显示，几乎所有的分类器构造算 法，在精度上都只是适用于某些类别的数据，而在另一些类型的数据上效果不佳。 1 5 3 模型函数的特性 对于含有n 个样本s t ，r a 个属性q 的训练集c l , c 2 , ，；d ) ，0 = 1 ，力，分类判别 函数是形如： d - - - f ( s 0 , s t ( c l ，c 2 ，；甄( i = 1 ，神 的缺射，其中s i 为一个样本，q 为该样本第j 个属性的数学值，d 为其类别标记。 相应于图1 2 中数据集，一个可能的分类准则为： i f ( 年龄 2 5 ) v ( 车型= 跑车) t h e n 风险= 高 e l s e 风险= 低 与它等价的分类判别函数实际上是一个简单的二维分段常数函数： 瓶c 2 ) i 品也淼 这里，c l 为年龄大小，c 2 为车型，货车为1 ，轿车为2 ，跑车为3 。f ( s i ) = 1 为高风险， f ( s 0 = o 为低风险。 1 1 中北大学学位论文 分类判别函数有一个最基本的要求：它必须具有光滑性，至少应该是分段光滑的。 光滑性意味着：若两个样本只有微小差异，它们在类别上就没有本质区别。它比连续性 的要求要高。只有分类判别函数满足光滑性的要求，才能使得一个样本的类别可以由另 一些差别不大的样本来刻画。因此，光滑性等价于要求分类判别函数不是。局部”的， 而是具有某种整体性。 定义1 1 一个映射，若它每个点的取值只有该点自己决定，而与其它点无关，则称 该映射是完全局部的 若一个分类判别函数是完全局部的，那么每个样本点的类别只能由它自己决定，因 此这样的函数是没有办法拟合或逼近的。实际上，讨论这样的分类判别函数是没有意义 的，因为从某种程度上说，它是任意给定的。 在理想的情况下，所有样本数据的类别完全由分类判别函数决定。分类就是在分类 判别函数未知的情况下，利用模型函数对分段光滑的分类判别函数的拟合或逼近。 1 6 分类问题的外延 当训练集中的样本包含很多特征时，光研究分类器构造本身还不足以解决问题，还 要涉及到分类问题的另一个重要研究领域：特征选择。特别是当面对复杂的基因数据库 中的知识发现和文本挖掘时【2 1 捌，特征选择显得更为重要 当特征域空阎( c t 庇，c 皿) 的维数很高，即样本含有大量的特征时，将会导致： 1 、过多的特征使得训练集的数据量过大，分类器构造算法的训练时间过长，“减慢 挖掘过程”圆； 2 、过多的特征使得训练集的维数过高，经训练得到的分类器是数值不稳定的，因 此分类器的分类准确率会显著降低； 3 、训练集特征过多，训练后的分类器得出的i f - t h e n 规则的前件过于冗长。不容易 理解。 因此必须去掉冗余( r e d u n d a n t ) 和无关的( i r r e l e v a n t ) 特征，只保留那些和类别相关 ( r e l e v a n t ) 的特征。所谓冗余特征是指：几个特征高度线性相关，甚至就是一个特征多次 重复地出现，这些特征实际上取其一即可，其他的特征就是冗余的特征；所谓无关特征 就是指：该特征和类别( c l a s sl a b e l ) 是随机关系，即和类别是无关的。举例来说，图1 2 1 2 中北大学学位论文 所示的例子中，f i d 就是一个无关特征，若再有一个取值和年龄完全相同的属性a g e ，那 么年龄和a g e 取其一即可，另一个为冗余特征。 冗余和无关特征会极大地影响分类器构造的效率和精度，必须删除。采用某种方法 找到这些冗余和无关特征的过程被称为特征选择( f e a t u r es e l e c t i o n ) 、特征子集选择 ( f e a t u r es u b s e ts e l e c t i o n ) 、特征空间的维数约简( d i r n e n s i o n a t i t yr e d u c t i o n ) 或属性约简 ( a t t r i b u t er e d u c t i o n ) 、属性子集选择( a t t r i b u t es u b s e ts e l e c t i o n ) 。 和分类器构造相关的另一个研究领域是：规则提取。它的研究是；怎样从已构造好 的分类器中，精确地抽取显式i f - t h e n 规则，以便辅助人工决策。规则提取方法和分 类器构造模型直接相关，有一种模型就有一种规则提取方法。由于这个领域的研究已经 比较完备，因此就不作为本文的研究内容。 1 7 课题意义及研究内容 通过本章对知识发现方法面临的一些挑战，分类问题的内涵、外延等的分析可以看 到，目前对数据分类问题的研究主要集中在：分类模型和分类算法的可伸缩性；分类模 型的粒度变换与粒度计算等。在这些方向上都有很多比较困难的问题需要解决。 人类的认知过程是一种智能行为，面对复杂的现实世界，尽管自身的能力和知识有 限，但却能自如地解决那些看起来难以胜任的问题，并做出正确的决策和反应。其秘密 在予人们通常不是采用系统的、精确的方法去追求惩题的最优解，而是通过逐步尝试的 办法，达到有限的合理的目标，即取得所谓满意的解。人类采用这样的方法，避免了高 复杂度计算的困难，使得原来看起来无法解决的难题迎刃而解。这种启发式问题求解的 思想，非常适合指导人们对复杂的海量数据挖掘，达到智能信息处理。然而如何“再现 智能”却有相当大的难度，国内外许多学者都在作这方面的努力，并取得了一定的成果， 如商空间理论、分形理论以及各种粒度计算、层次处理、分解计算等等，但研究远没有 结束，亟需在更深层次上进行理论研究，以期待智能化信息处理时代的到来。本文所研 究的数据挖掘的各种方法，大都遵循了人的认知习惯，根据问题的具体情况，在不同粒 度下和不同层次下处理数据，使得算法更加适合有效的数据挖掘。 本文将粒度计算的思想引入分类算法，在基于粒度计算的分类研究方面做了一些相 关的工作，希望能从一个新的角度来分析和研究分类