（计算机应用技术专业论文）数据预处理中数据缺失填补算法的研究与应用.pdf

ad i s s e r t a t i o ns u b m i t t e dt og u a n g d o n gu n i v e r s i t yo f t e c h n o l o g y f o rt h ed e g r e eo fm a s t e ro fe n g i n e e r i n gs c i e n c e s t u d ya n da p p l i c a t i o no fm i s s i n gd a t ai m p u t a t i o ni n d a t ap r e p r o c e s s m a s t e rc a n d i d a t e ：w a n gf e n g m e i s u p e r v i s o r ：p r o f f ux i u f e n m a y2 0 10 f a c u l t yo fc om p u t e r g u a n g d o n gu n i v e r s i t yo ft e c h n o l o g y g u a n g z h o u ，g u a n g d o n g ，p r c h i n a ，5 10 0 9 0 8叭26眦5m 4叭7 川1洲y 摘要 摘要 随着技术的发展与科学的进步，数据量的飞速增长已成为一个不容忽视的问题， 面临堆积如山的数据，想要获取有用的信息与知识并非易事。因此数据挖掘技术伴 随着人们的需求与科技的进步获得快速发展。然而在实际应用时，缺失数据的出现 对所有数据分析技术包括数据挖掘都是一个普遍存在却富于挑战性的问题。 缺失数据的产生原因多种多样，有主观上人为的也有客观上的难以获取。它们 广泛存在于现实的数据集中，对数据分析产生严重影响：首先，系统丢失了大量的 有用信息，明显削弱了信息与统计的能力：其次，增强了系统的不确定性，使得正 常的数据分析方法不适用或难于应用；最后，包含缺值的数据还会使挖掘过程陷人 混乱，导致不可靠的输出。因此如何正确处理这些缺失数据成为数据预处理过程中 核心问题之一。 缺失填补技术无论是在技术还是理论上都得到了空前的重视，国际上已有大量 专家及研究机构对些问题进行深入研究。本文首先论述了缺失数据填补的意义及研 究现状，通过分析近年来出现的缺失填补策略，将其分成基于分类、聚类、关联的三 种填补思想，在此基础上提出一种新的缺失填补算法。通过对当前几个开源挖掘工 具预处理模块的研究，设计了一个处理缺失数据集的预处理模型，并通过研究基于 分类思想及关联思想的填补策略，对设计应用于模型中新的缺失填补法，规则近邻 法进行详细设计实现，通过实验对其填补的有效性，准确率进行验证。 实验用5 折交叉验证法证明算法的有效性；并通过与k n n 填补算法进行对比证 明该算法在填补准确率上的优越性；通过增加缺失比例及改变提取规则的最小支持 度与置信度确定影响该算法填补准确率的因素；面对连续数据集中的缺失值，通过 分析对比选择基于m d l p 的方法进行离散化，并通过扩大离散化的粒度对填补的准确 率结果进行分析，指出要使填补获得好效果并非离散粒度越大越好；填补算法应用 于离散化后的数据集进行与离散数据集相似的实验，证明此算法对连续数据集缺失 值填补的有效性。最后对全文进行总结及下一步工作需要改进的地方。 关键词：缺失数据；缺失填补；关联规则；预处理；离散化 广东工业大学硕士学位论文 a bs t r a c t t h er a p i dg r o w t hi nt h ea m o u mo fd a t ah a sb e c o m eap r o b l e mt h a tc a nn o tb e i g n o r e da l o n gw i t ht h ed e v e l o p m e n to ft e c h n o l o g ya n ds c i e n c e i t sn o te a s yf o ry o ut o g e tu s e f u li n f o r m a t i o na n dk n o w l e d g ew h e nf a c i n gw i t hm o u n t a i n so fd a t a t h e r e f o r e ， d a t am i n i n gt e c h n o l o g yw i t hp e o p l e sn e e d sa n da d v a n c e m e n to ft e c h n o l o g yi sa taf a s t p a c e h o w e v e r , i np r a c t i c a l ，t h ee m e r g e n c eo fm i s s i n gd a t ai sap e r v a s i v eb u tc h a l l e n g i n g p r o b l e mf o ra l ld a t aa n a l y s i st e c h n i q u e si n c l u d i n gd a t am i n i n g t h e r ea r ev a r i e t i e so fr e a s o n sf o rh o wt h em i s s i n gd a t ap r o d u c e d ，i tm a yb e s o m e b o d yd o e si ti n t e n t i o n a l l yo rn e g l i g e n t l y , o ri ti sd i f f i c u l tt oo b t a i no b j e c t i v e l yt h e i r p e r v a s i v ee x i s t e n c ei nm o s tr e a lw o r l dd a t as e t ss e r i o u s l ya f f e c t st h ep r o c e s so fd a t a a n a l y s i s ：f i r s t l y , t h es y s t e ml o s t al o to fu s e f u li n f o r m a t i o n ；i tc l e a r l yw e a k e n e dt h e a b i l i t yo fi n f o r m a t i o na n ds t a t i s t i c s s e c o n d l y , i ti n c r e a s e st h eu n c e r t a i n t yo f t h es y s t e m , m a k e st h es y s t e mm o r ed i f f i c u l tt og r a s pi m p l i c a t i o no ft h ed e t e r m i n i s t i cc o m p o n e n t ，i t a l s om a k e sc o m m o nd a t aa n a l y s i sm e t h o d si n a p p r o p r i a t eo rd i f f i c u l tt oa p p l y l a s t ，t h e d a t aw i t hm i s s i n gv a l u e sc a ni n t r o d u c ec h a o si n t om i n i n gp r o c e s s ，r e s u l t i n gi nu n r e l i a b l e o u t p u t s oh o wt oh a n d l et h e s em i s s i n gd a t ab e c o m e so n eo ft h e c o r ei s s u e sa sd a t a p r e p r o c e s s m gp r o c e s s m i s s i n gd a t ai m p u t a t i o nt e c h n ol o g y h a s a l r e a d y a t t r a c t e dm u c ha t t e n t i o ni n t e c h n o l o g ya n dt h e o r i e s t h e r ea r eal a r g en u m b e ro fi n t e r n a t i o n a le x p e r t sa n dr e s e a r c h i n s t i t u t i o n sh a v ed o n ei n d e p t hs t u d yo nt h i sp r o b l e m t h et h e s i sf i r s t l yd i s c u s s e st h e s i g n i f i c a n c eo fm i s s i n gd a t aa n dt h ec u r r e n ts i t u a t i o no ni m p u t a t i o nm i s s i n gd a t a ，i tt h e n c l a s s i f i e si m p u t a t i o ns t r a t e g i e sa p p e a r e dr e c e n ty e a r sa sb a s e do nc l a s s i f i c a t i o na n do n c l u s t e ra n do na s s o c i a t i o n b a s e do nt h i ss u m m a r i z ei tp u tf o r w a r dan e wm i s s i n gd a t a i m p u t a t i o na l g o r i t h m a f t e rs t u d y i n gs e v e r a lo p e n i n gd a t am i n i n gt o o l s ，i td e s i g n sa p r e p r o c e s sm o d e lf o ri n c o m p l e t ed a t as e t s t h ep r e p r o c e s s m o d e lu s e st h en e w i m p u t a t i o na l g o r i t h mw h i c hi sb a s e do nt h ei d e ao fc l a s s i f i c a t i o na n da s s o c i a t i o n t h e n e wa l g o r i t h mn a m e sa s s o c i a t i o n - n e i g h b o ra l g o r i t h m ，t h et h e s i sg i v e sad e t a i ld e s i g na n d r e a l i z a t i o nt oi t ，i na d d i t i o n ，d e s i g n se x p e r i m e n t st op r o v ei t sv a l i d i t ya n da c c u r a c y u a b s t r a c t t h e e x p e r i m e n t s u s e5 - f o l d s - c r o s sv a l i d a t em e t h o dt o p r o v ev a l i d i t y o f a s s o c i a t i o n - n e a r e s t - n e i g h b o ra l g o r i t h m , a n dc o m p a r ew i t hk n ni m p u t a t i o na l g o r i t h mt o p r o v et h en e wa l g o r i t h m sa c c u r a c y t h ee x p e r i m e n t sa l s oa s c e r t a i nt h ef a c t o rt h a ta f f e c t s t h ei m p u t a t i o n sa c c u r a c yb yi n c r e a s i n gt h ep e r c e n t a g eo fm i s s i n gd a t aa n dc h a n g i n gt h e m i n i m u ms u p p o r ta n dc o n f i d e n c eo fo b t a i n i n gr u l e st o w h e nf a c i n gc o n t i n u o u sd a t as e t w h i c hc o n t a i n sm i s sv a l u e s ，i ts e l e c t sm d l pb a s e dd i s c r e t em e t h o da f t e rc o m p a r i n gw i t h o t h e rm e t h o d st od i s c r e t et h ed a t a a f t e rl i g h t l ye x p a n d i n gt h es i z eo fd i s c r e t i z a t i o n ，i t c o m p a r e dt h er e s u l t so fa c c u r a c ya n dp o i n t e d t h a ti t sn o tag o o di d e at oe x p a n ds p l i ta r e a t oo b t a i n h i g h e ri m p u t a t i o na c c u r a c y a f t e rd o n es i m i l a re x p e r i m e n t s o nd i s c r e t e c o n t i n u ed a t as e t s ，t h er e s u l t si n d i c a t et h a tt h ea s s o c i a t i o n n e a r e s t n e i g h b o ri m p u t a t i o n a l g o r i t h mi se f f e c t i v ei ni m p u t a t i o nc o n t i n u ed a t as e t sw i t hm i s s i n gd a t a a tt h ee n d ，t h e t h e s i ss u m m a r i z e st h er e s e a r c ha n dp o i n t so u tt h ed i r e c t i o noff u t u r er e s e a r c h k e yw o r d s ： m i s s i n gd a t a ；m i s s i n gd a t ai m p u t a t i o n ；a s s o c i a t i o nr u l e s ；p r e p r o c e s s ； d i s c r e t i z a t i o n ： 1 i i 目录 目录 摘要i a b s t r a c t i 目录v c o n t e n t s v i i 第一章绪论1 1 1 研究背景和意义1 1 2 数据缺失填补国内外研究状况2 1 3 论文结构及主要研究内容4 1 3 1 论文结构安排4 1 3 2 论文主要研究内容5 第二章相关理论6 2 1 数据预处理6 2 2 连续数据离散化8 2 3 数据缺失问题1l 2 4 小结19 第三章数据预处理模型设计2 0 3 1 模型设计目标分析2 0 3 2 模型框架2 0 3 3 详细设计2 2 3 3 1 显示器模块2 2 3 3 2 离散器模块2 4 3 3 3 删补器模块2 4 3 4 小结2 7 第四章缺失值填补算法2 8 v 广东工业大学硕士学位论文 4 1 基于分类思想的填补2 8 4 2 基于聚类的填补3 2 4 3 基于关联规则的填补3 2 4 4 小结3 3 第五章规则近邻填补算法3 4 5 1 关联规则填补过程3 4 5 2 最近邻填补3 5 5 3 规则近邻算法策略3 7 5 4 实验对比及分析4 l 5 4 1 离散数据集4 2 5 4 2 连续属性集4 7 5 4 3 时间复杂度5 3 5 5 小结5 3 总结与展望5 4 参考文献5 6 攻读学位期间参加的研究项目和发表的学术论文6 0 独创性声明6 l 致访i 6 2 v l a b s t r a c t i i c o n t e n t s v c o n t e n t s v h c h a p t e r 1i n t r o d u c t i o n 1 1 1t h er e s e a r c hb a c k g r o u n da n dm e a n i n g 1 1 2t h es t a t eo f t h ea r tf o rm i s s i n gd a t ai m p u t a t i o n 2 1 3t h es t r u c t u r ea n dm a i nw o r ko f t h et h e s i s 4 1 ：；1t h es t r u c t u r e 4 一一“ 1 ：；：! m a i nw o r k 5 c h a p t e r 2c o r r e l a t i v et h e o r y 6 一一 2 1d a t ap r e p r o c e s s 6 2 2t h ed i s c r e t i z a t i o no fc o n t i n u o u sd a t a 8 一j 2 3t h ep r o b l e mo f m i s s i n gd a t a 11 2 4s u m m a r y 19 c h a p t e r3t h ed e s i g no fp r e p r o c e s sm o d e l 2 0 3 1m o d e la n a l y s i s 2 0 ：；2t h ef r a m eo f m o d e l ：! ( ) 3 3d e s i g ni nd e t a i l 2 2 3 3 1t h ed i s p l a ym o d u l e 2 2 ：i ：；2t h ed i s c r e t i z a t i o nm o d u l e 2 4 3 3 3d e l e t e - i m p u t a t i o nm o d u l e 2 4 ：；4s u m m a r y 2 7 c h a p t e r 4t h es t r a t a g yo fi m p u t a t i o n 2 8 4 1t h ei m p u t a t i o nb a s e do nc l a s s f i c a t i o n 2 8 v 广东工业大学硕士学位论文 4 2t h ei m p u t a t i o nb a s e do nc l u s t e r 3 2 4 3t h ei m p u t a t i o nb a s e do na s s o c i a t i o nr u l e s 3 2 4 4s u m m a r y 3 3 c h a p t e r5a s s o c i a t i o n - n e i g h b o r l m p u t a t i o na l g o r i t h m 3 4 5 1i m p u t a t i o np r o c e s so fa s s o c i a t i o nr u l e s 3 4 5 2n e a r e s tn e i g h b o ri m p u t a t i o n 3 5 5 3a s s o c i a t i o n - n e i g h b o ra l g o r i t h m 3 7 5 4e x p e r i m e n t sa n da n a l y s i s 4 1 5 4 1o nn o m i n a ld a t as e t s 4 2 5 4 2o nc o n t i n o u a ld a t as e t s 4 7 5 4 3t i m ec o m p l e x i t y 5 3 5 5s u m m a r y 5 3 c o n c l u s i o n _ s e x p e c t a t i o n 5 4 r e f e r e n c e s 5 6 t h ep a p e r sp u b l i s h e dd u r i n gt h em a s t e rd e g r e e 6 0 o r i g i n a ls t a t e m e n t 6 1 a c k n o w l e d g e m e n t s 6 2 v 1 1 1 第一章绪论 1 1 研究背景和意义 第一章绪论 数据缺失在实际中是经常发生的，甚至是不可避免的。造成数据缺失可能是信 息暂时无法获取或者在操作过程中被遗漏等。数据缺失对数据挖掘的过程和结果都 有十分严重的影响。数据缺失可能直接影响到挖掘模式发现的准确性和运行性能， 甚至导致错误的挖掘模型。处理有缺失数据的数据集是极端困难的，因为，现有的 模式发现算法通常假设输入的数据是无缺失的。于是，这些可用的模式发现算法和 实际数据之间存在一条不可逾越的鸿沟。 随着人们获取信息的手段不断增多，人们手中有用的无用的数据也越积越多，一 我们几乎被数据的大山所湮没。数据挖掘技术或者k d d ( k n o w l e d g ed i s c o v e r yf r o m d a t a b a s e s ) 的出现使人眼前一亮，它能帮我们理解堆积如山的数据并从中提取有用的 信息，并且随着k d d 技术的不断发展，它的作用范围也越来越广1 1 1 。但在实际操作 过程中，数据集中缺失数据( m i s s i n gd a t a ) 的出现成为众多数据分析技术中常见却又 极具挑战的问题。由于所有数据分析技术从严格意义上来讲都是从数据集中获取知 识的，因此其所获取到的知识的质量在很大程度上取决于其所作用的数据集的质量， 数据质量被证明成为数据分析与知识发现过程的关键部分【2 l 。如果数据质量太低， 也很可能使得一个数据分析系统成为一个垃圾进来最后垃圾出去的系统。因此数据 质量保证已成为数据分析领域众所关注的问题，高质量的数据是获取高质量信息的 前提。 噪声数据( n o i s yd a t a ) 、不一致数据( i n c o n s i s t e n td a t a ) 、缺失数据是获取高质量 数据的三大障碍【3 1 ，限于内容本文只取缺失数据作为研究对象。 数据缺失是数据预处理过程中经常碰到的问题，数据缺失涉及的范围很广，也 很难给出一个明确的界定，它包括实验中的缺失数据，也包括调查中的缺失数据或 者没有搜集到的数据，或者搜集后遗失的数据，还包括汇总时填报错误等原因所造 成的数据缺失。也就是说数据缺失广泛存在于现实世界的众多数据集中，它们可能 隐含了某些重要的信息。缺失数据的存在造成了以下影响：系统丢失了大量的有用 广东工业大学硕士学位论文 信息；系统中所表现出的不确定性更加显著，系统中蕴涵的确定性成分更难把握， 使得正常的数据分析方法不适用或难于应用；包含缺值的数据会使挖掘过程陷人混 乱，导致不可靠的输出。 研究源自需求。数据挖掘的大多数方法都只能应用于完整的数据集上( 比如在 研究于s t a t l o g 项目的2 3 种分类算法将近一半要求完整数据集【4 】) ，很明显，数据缺 失给大多数数据分析技术带来了挑战。尽管国际和国内学者已经提出了很多处理缺 失值的方法，并且已经研发出了处理缺失值的应用软件，如s a s ，s p l u s 等这些已 得到广泛应用的统计软件，但是存在的方法一直不能满足用户日益增长的需求，而 且已有的方法还存在着很多不完善的地方。 如直接删除( l i s t w i s e ) 含有缺失值的属性或事例法，多个实验研究 s l d 已表明如 果不是在完全随机缺失的机制下，它会导致预测准确性缺失并导致预测结果偏差。 因此在非完全随机缺失的情况下，应该对缺失值进行填补，而文献 7 】则通过多个实 验对比证明用均值填补却是一种很不可靠的填补技术。随着网络的普及和发展，数 据缺失的问题将会更加加深处理数据的难度，而如何正确处理缺失数据，已成为数 据预处理过程的主要问题之一。 1 2 数据缺失填补国内外研究状况 随着实际应用需求的不断增长，数据挖掘在理论与应用上获得了极大的发展， 数据预处理作为其重要且必不可少的组成部分，技术也随之迅速发展起来。数据清 理技术作为数据预处理的研究热点，主要集中在填补缺失数据、消除噪声数据或不 一致数据等问题的研究上，其中填补缺失数据逐步成为核心问题。 填充缺失数据的方法无论是在技术上还是理论上都得到了空i j f 的重视t s l ，国际 上已有专门机构研究此问题，如美国宾州大学和佛蒙特大学都成立有专门的研究小 组，很多国外文献资料表明一些缺失数据填补方法已在工业、经济、医学等领域得 到研究与应用，如文献 9 ，1 1 1 2 】。遗憾的是，对缺失数据问题的研究在数据挖掘与 机器学习领域中并未受到应有的重视，因此能够见刊的文章并不多。但统计学领域 对缺失数据填补方法却有着广泛的研究，从最初简单的单一填补法如均值填充法、 回归法、热卡( h o t d e c ) 填补等，到改进的多重填补方法如最大期望法( e x p e c t a t i o n m a x i m i z a t i o n ) 、p m m 法( p r e d i c t i v em e a nm a t c h i n g ，随机回归填补法) 、趋势得分法 ( p r o p e n s i t ys c o r e ，p s ) 、马尔科夫链蒙特卡罗法( m a r k o vc h a i nm o n t ec a r l o ，m c m c ) 2 第一章绪论 等等对缺失数据的处理起到了很重要的作用，尽管多重填补更加复杂，但为了能更 好地还原缺失数据，研究者更趋向于多重填补方法及其优化，这些方法都以很强的 数学理论为基础，也因此为数据缺失问题的发展找到很好的理论依据。 l i t t l e 和r u b i n 6 j 根据缺失数据的类型及特点为缺失数据定义了三种缺失机制： m c a r ( c o m p l e t e l ya tr a n d o m ) 、m a r ( m i s s i n ga tr a n d o m ) 、n i ( n o n - l g n o r a b l e ) , 对缺 失数据处理方法研究在统计学领域已基本形成自己的理论体系。各科学领域的研究 范围并没有严格的界线，它们都是相互渗透相互交叉的，这就使得数据挖掘与机器 机器学习在数据缺失问题上向统计学领域很好地借鉴成为可能。 目前国内对数据缺失问题的研究无论是在统计学领域还是在数据挖掘领域都还 处在一个开始阶段，尽管在一些学术期刊及学术会议上也可能见到一些有关理论及 部分实现的论文如 1 3 1 5 】，但直接针对数据缺失填补的研究成果却很少见到。 总体而言，目前存在的影响最大的两个处理缺失值问题的研究方向分别是统计 学方面和数据挖掘方面，对于处理缺失值问题，他们都建立了自己的理论体系，也 成功地应用到了实际中。但是，他们的研究方法大都针对自己领域的实际情况而被 提出，在自己领域内非常有效，若要把自己的方法应用到对方领域，就显得有点不 足。 填补缺失值的目标就是要求在各种评价指标上超过没有填充时的效果，或者能 比存在的方法效果明显。国内外大量的专家和研究机构已经对数据缺失的问题进行 了非常深入的研究，也取得了很多研究成果并总结出了丰富的研究经验：文献 1 5 】 在软件工程效率预测数据集上进行实验，通过将k n n 填补法与类均值填补法在不 同缺失机制下对比，并发现m a r 是最安全的默认缺失机制；文献 7 】通过大量实验 证明了数据的基础质量对填补错误率有很大影响，并且数据基础质量对缺失值填补 起着重要作用；文献 1 6 】还指出，缺失率达到4 0 以上对具体的分析就无太大意义 的观点已被广泛接受；文献 1 7 】、 1 9 的研究还表明，可根据有计划的缺失来增强研 究设计。对于先前的传统填补方法已很明显不能满足现在数据挖掘对数据质量的要 求，自从多重填补的思想提出后，国内外大量专家及研究机构对其青睐有加，文献 【1 7 】还主张抛弃传统的填补法而采用多重填补束处理缺失数据。这些经验与成果为 本文的研究工作提供了坚实的理论基础。 从上面的论述我们知道，在对缺失数据填补问题上的研究，统计学领域远比数 据挖掘及机器学习领域要早且深入，所幸的是各学科领域是交叉相互没有界定的， 3 广东- r & 大学硕士学位论文 因此在k d d 领域研究缺失数据填补问题就有理可依。国外对填补缺失值问题的研 究已较为广泛，无论在应用领域还是方法比较上的研究都有着不断更新；而国内对 此问题的研究很有限，主要成果一般为对国外相关研究资料的翻译或介绍，文献综 述等，近年来也出现一些方法上的比较研究”，及特定应用上的新方法“”川。 本文将针对缺失数据的预测性填补进行研究，对有关缺失填补算法进行分类详 细介绍，提出一种普适的填补算法，以填补准确率( 即还原数据本来面貌的程度) 进 行评价，并应用于所设计的预处理模型。通过实验证明，为缺失数据问题的研究提 供一种较优的填补策略。 1 3 论文结构及主要研究内容 1 3 1 论文结构安排 本文共分五个章节，各章节内容安排如下： 第一章绪论部分，介绍数据缺失填补研究的背景意义及国内外的研究现状； 第二章为本文相关理论支撑，介绍了数据预处理过程及其在数据挖掘过程中所 处的地位，连续数据离散化的必要性及方法，缺失技术的基本问题如缺失原因，当 前所提出的缺失机制，及缺失填补的衡量标准，及缺失填补技术； 第三章分析并描述了一个处理不完备数据集的预处理模型的设计思路，并设计 最后应用的填补算法过程； 第四章总结并分析近年来各领域内专家学者所提出的缺失填补算法，为本文算 法作铺挚； 第五章对第三章预处理模型的规则近邻填补算法进行详细设计及实验分，通过 与k n n 填补算法进行实验对比分析证明其有效性及进步性； 总结与展望详细总结了本文所做工作，并指出本文工作的不足之处，对下一步 工作进行展望。 为让本文将要研究的缺失填补问题在数据挖掘中的地位更加清晰，图卜1 将数 据挖掘过程预处理部分进行详细分层。 4 第一章绪论 1 3 2 论文主要研究内容 图1 - 1 数据挖掘过程 f i g 1 - 1d a t am i n i n gp r o g r e s s 上述表明，本文将研究的主要内容有： ( 1 ) 通过分析，设计一个专为处理不完备数据集的预处理过程模型。 ( 2 ) 通过对近几年缺失填补算法的仔细研究，对所设计的预处理过程中用到的 填补算法进行详细设计实现，进行实验分析算法优劣。 本文的主要创新点有： ( 1 ) 通过研究几个开源的数据挖掘工具发现，预处理过程对缺失值的处理均用 传统的填补，而前面研究表明这些传统的方法对数据挖掘过程会产生众多影响。本 文针对含缺失的数据集设计了一个预处理模型，出于对数据质量的要求，该模型除 保留传统填补方法外，还加入两种较复杂的填补算法，以供用户选择。 ( 2 ) 一般缺失值填补包括单一填补和多重填补，为向填补的准确率靠近，本文 将在原有的基于关联规则的填补算法的基础上进行优化，加入k n n 算法的思想， 对规则按缺失属性分类，得到与缺失事例相似的k 条优化规则进行填补。 广东工业大学硕士学位论文 2 1 数据预处理 第二章相关理论 在了解数据预处理过程之前，我们需要先了解其所属主题数据挖掘的一般过程 及主要技术。 1 数据挖掘简介 数据挖掘( d a t am i n i n g ) 是介于统计学、数据库技术、人工智能、机器学习、模 式识别、数据可视化以及高性能并行计算等的新兴交叉学科。它的一般含义就是从 大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中 的、人们事先不知道的、但又是潜在有用的信息和知识的过程。即通过预测未来趋 势及行为，以做出前摄的、基于知识的决策。目前它的主要研究内容包括基础理论、 发现算法、数据仓库、可视化技术、定性定量互换模型、知识表示方法、发现知识 的维护和再利用、半结构化和非结构化数据中的知识发现以及网上数据挖掘等1 3 】具 有极为广泛的应用前景。 数据挖掘整合了人工智能、统计及数据库等多种学科的理论、方法和技术，这 些学科中的多数技术和方法都可以直接应用在数据挖掘的过程中。如统计学中，除 了实验设计和数据挖掘的关系不大，几乎所有的其他方法，如概率分布、估计、不 确定性、假设检验、回归分析、主成分分析、马尔可夫链、基于案例的推理、时间 序列分析等都可用于数据挖掘，这些支撑技术如：决策树( d e c i s i o nt r e e ) 方法、人工 神经网络( a r t i f i c i a ln e u r a ln e t w o r k ) 方法、遗传算法( g e n e t i ca l g o r i t h m ) 、模拟退火算 法( s i m u l a t e da n n e a l i n g ) 、基于案例的推理( c a s e b a s e dr e a s o n i n g ) 、粗集理论法( r o u g h s e t ) 、模糊集合方法( f u z z ys e t ) 、云理论、可视化方法( v i s u a l i z e ) 等等。 一般而言，数据挖掘的流程主要由以下几个步骤组成【3 】：( 1 ) 数据准备选择出 适用于数据挖掘的数据；( 2 ) 数据预处理数据清理，数据合成，数据归约，数据转 换；( 3 ) 数据挖掘基本步骤，使用智能方法提取数据模式；( 4 ) 模式评估根据某种 兴趣度度量，识别表示知识的真正有趣的模式；( 5 ) 知识表示使用可视化和知识表 示技术，向用户提供挖掘的知识。 2 数据预处理重要性 6 第二章相关理论 从前面我们知道，数据预处理是数据挖掘的一个重要过程，它要为数据挖掘过 程提供数据质量保障。 数据挖掘所依赖的数据来源多种多样，可以是常用的关系数据库，事务数据库， 文本数据库，多媒体数据库等，而其真实的数据更是错综复杂，其中，不可避免的 存在噪音数据、冗余数据、缺失数据、不确定数据( u n c e r t a i nd a t a ) 和不一致数据等 诸多情况。这诸多情况堆积成的不确定、不一致和不完整的数据信息更是成为发现 知识的严重障碍。因此，人们不得不将大量的时间和精力花在数据预处理上。在保 证不减少数据所含信息的前提下，合理有效的数据预处理可以压缩数据量，改善数 据质量，提高数据挖掘算法的性能，减少学习时间。 由于高质量的决策必然依赖于高质量的数据，因此数据预处理是知识发现过程 的重要步骤。如果不进行数据的预处理工作或者预处理工作做的不好，那么在挖掘 阶段就势必会花费大量的、超过必要的时间去寻找知识，并且这样所得到的知识还 不能确定其可信度和可理解度。数据预处理技术对改进数据质量，提高其后的挖掘 过程的精度和性能有着不容忽视的作用。 已有的大量事实表明，数据预处理在实际的数据挖掘项目中是花费时间最长也 是最为烦琐的步骤，这个步骤通常要花费大量的人力、物力。例如：在机器学习和 数据挖掘应用方面，大约2 0 的精力花在数据理解方面，约1 0 的精力用在数据挖 掘和知识的分析方面，剩下的6 0 多的时