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

西南交通大学硕士研究生学位论文第1 页 摘要 随着信息时代的来临，人类在各种领域中面临着越来越多的数据信息， 与此同时，这些数据的规模还在以惊人的速度不断增长。因此，为了提高工 作效率和生活质量，人们必须获取蕴藏在这些数据中的有价值信息。为了达 到这个目的，人们开始致力于从数据库中挖掘知识的研究。然而，众所周知， 数据库中往往存在冗余数据、缺失数据、不确定数据和不一致数据等诸多情 况，这些数据成了发现知识的一大障碍。因此，在从数据库中挖掘知识之前 必须对数据进行预处理。 本论文着重研究数据挖掘中的数据预处理技术，尤其是数据清洗技术， 并实现了数据挖掘试验平台( d a t am i n i n gl a b o r a t or y d m l a b ) 的数据预处理 模块的功能。 首先对数据预处理知识做了全面和详细的描述，介绍了数据预处理的研 究背景、定义和主要的预处理技术研究现状等。然后对现有的数据预处理技 术进行了深入的分析，涉及到数据清洗、数据选样、数据变换和数据归约等 技术。之后重点对缺失值填充技术及各种填充算法进行了深入地研究和探讨， 并提出了基于聚类技术的缺失值填充法。最后，在前面讨论的各种技术的基 础上，实现了数据挖掘试验平台的数据预处理模块功能，主要包括数据清洗、 数据选样、数据转换、数据归约等功能。 在对数据预处理技术进行的研究中，着重介绍了缺失值清洗的基本知识 和方法，并探讨了当前缺失值清洗技术，客观地评价了它们的优缺点。本文 对目前广泛应用的各种数据预处理技术进行了深入的研究，并在此基础上完 成了d m l a b 系统中数据预处理模块的设计和实现，既根据系统需要实现了 部分基础的预处理算法，又提出了如何应用聚类算法进行缺失值填充的新方 法，并给出了在数据集上的试验结果及结论。 本文的主要创新点在于提出的基于聚类技术的缺失值填充算法。 关键词：数据挖掘：数据预处理；数据清洗；缺失值：填充缺失值 西南交通大学硕士研究生学位论文第| l 页 a b s tr a c t w i t ht h ec o m i n go fi n f 0 瑚a t i o na g e ，h u m a na r cc o n f r o n t e dw i t hi n c r e a s i n g d a t a 强di n f 0 珊a t i o ni nd i f ：f e r e n tf i e l d s a tt h es a m et i m e ，t h e s ed a t aa r e d e v e l o p i n gi ns u r p r i s i n g i ys p e e d i no r d e rt oi m p r o v ew o r ke f f i c i e n c ya n dl i f e q u a l i t y ，p c o p l em u s to b t a i nt h ev a l u a b l ei n f o 肌a t i o nh i d d c ni nt h e s ed a t a s o ， r e s e a r c h e st h a tm i n i n gk n o w l e d g ef r o md a t a b a s e sa r es t a n e d h 0 w e v e r ，a sw c l l k n o w n ，t h e r ea r em a i l yi s s u e si nd a t a b a s e s ，s u c ha sr e d u n d a td a t a ，m i s s i n gd a t a ， u n c e n a i nd a t a ，i n c o n s j s t e n td a t a ，a n ds oo ，t h e ya r ct h eb a 喇e f st ok n o w l e d g c d j s c o v e r y t h e r e f o r e ， i ti s i m p o r t a n tt op r e p m c c s sd a t a b e f o r ek n o w l e d g e d i s c 0 v e f yf r o md a t a b a s e s a i l dt h i sp a p e rf b c u s c so nt h ed a t ap r e p r o c e s s i n gi nd a t am i i n g ，e s p c c i a l l y o nt h ed a t ac l e a n j n g ，a n dt h ed a t ap t c p r o c e s s i n gf u n c t i o sa r ei m p l e m e n t e da l s o i nd a t am i n i n gl a b o r a t o r yp l a t f 0 皿( d m l a b ) f i r s t ly ，t h ek n o w l e d g e0 fd a t ap r e p r o c c s s i n gi sd e s c r i b e dg e n e r a l l ya n d p a r t i c u l a r l y ，a n dt h er e s e a r c hb a c k 簪o l l n d ，c o n c e p ta n dt h cr e s c a r c hs t a t u so fm a i p r e p r o c e s s i n gt e c h n i q u e sa r ei n t r o d u c e d n l e n ，t h ee x i s t i n gd a t ap r e p r o c e s s i n g t e c h n i q u e sa r ea n a l y z e dd e e p l y w h i c hi n v o l v e dd a t ad e a n i n g ，d a t as a m p l i n 岛 d a t at r a n s f o m a t i o na n dd a t ar e d u c t i o n t h ep a p e rl a y sas t r o n ge m p h a s i so nt h e m i s s i n gd a t ai m p u t a t i o nt e c h n i q u e s ，a n dm a n yi m p u t a t j o na l g o r i t h m sa r es t u d i 蛐 a n dd i s c u s s e di nd e t a i l ，t h ei m p u t a t i o na i g o r i m mb a s e do nd u s t e r i l l gt e c l l l l i q u ei s p r o p o s e d f i n a l l y t h ed a t ap r c p f o c e s s i n g m o d u l ei nd a t am i n i n gl a b o n t o r y p l a t f o r mi s i m p l e m e n t e db a s e d0 nm a n yt e c h n i q u c sd i s c u s s e de a r l i e r ，a n dt h e m o d u l ec o n t a i n sd a t ac l e a n i n 函d a t as a m p l i n g ，d a t at r a n s f o n n a t i o na n dd a t a r e d u c t i o nf u n c t i o n sr e s p e c t i v e l y t h ep a p e ri n t r o d u c e sb a s i ck n o w l e d g ea n da l g o r i t h m so fd a t ap r e p r o c e s s i n g t e c h n 0 1 0 9 i e s ，e s p e c i a l l ym i s s i n gd a t ac l e a n i n g ， a n dd i s c u s s e st h em e r i ta d d f a w b a c k so f m i s s i n g d a t a c l e a i n gt e c h n i q u e so b j e c t i v e b m a n y d a t a p r e p t o c e s s i n gt e c h n i q u e st h a ta p p l i e dw i d e l ya tp r e s e n t a r cs t u d i e d ，a n dt h e d e s i g na n di m p l e m e n t a t i o no fd a t ap r e p r o c e s s i n gm o d u l ef u n c t i o n si nd m l a b s y s t e mw c r ca c h i e v c db a s c d0 nt h e s t u d i e s n o t0 n l yi m p l e m e n tt h eb a s i c p r e p r o c e s s i n ga l g o t h m sa c c o r d i n gt os y s t e md e m a n d ， b u tan e wm e t h o d 西南交通大学硕士研究生学位论文第1 | i 页 a p p l y i n gc l u s t e r i n ga l g o r i t h mf o ri m p u t a t i o ni sp r o p o s e d ，a tt h ec n dt h et e s tr e s u l t a n dc o n c l u s i o na r ep r o v j d e d t h e1 e a d i n gc r e a t i v ep o i n ti st h ei m p u t a t i o na l g o r “h mp m p o s e d0 fm i s s i n g d a t ab a s e do nt h ec l u s t e ft e c l l i l i q u e k e y w o r d s ： d a t a m j n i n g ； d a t a p r e p r o c e s s i n g ； d a t a c l e a n s i n g ；m i s s i n gd a t a ； i n l p u t a t i o n ； 西南交通大学硕士研究生学位论文第1 页 1 。1 研究背景 第1 章绪论 近年来，随着信息产业的快速发展，人们积累的数据越来越多。激增的 数据背后隐藏着许多重要的信息，如何对其进行更高层次的分析，以便更好 地利用这些数据，变得越来越重要。传统的数据管理方法可以高效地实现数 据的录入、查询、统计等功能，但无法发现数据中潜在的、有用的关系和规 则。为了挖掘数据背后隐藏的知识，解决“数据爆炸但知识贫乏”问题，人 们努力寻求各种新方法和技术，以便使数据能够转化成有用的信息和知识。 数据挖掘在这种背景下应运而生了。目前，它已成为计算机科学研究中一个 十分活跃的前沿领域，并在市场分析、金融投资、医疗卫生、环境保护、产 品制造和科学研究等许多领域获得了广泛的成功应用，取得了十分可观的社 会效益和经济效益。 数据挖掘领域的研究日趋成熟，其中许多研究把方法和模型建立在理想 的数据而不是现实的数据集上。但现实中的数据是错综复杂的，总体而言， 它们不可避免的存在冗余数据皿e d u d a n td a t a ) 、缺失数据( m i s s i n gd a t a ) 、不 确定数据( u n c e r t a i nd a t a ) 和不一致数据( h l c o n s i s t e n td a t a ) 等诸多情况m l ，这 样的数据简称为“脏数据”，它们成为数据挖掘的一大障碍。要在基于历史的、 现存的数据基础上去为将来的企业发展作决策或预测时，数据的质量问题就 变得很关键。根据“垃圾进，垃圾出”( g i g o ，g a r b a g ei l l ，g a r b a g eo u t ) 原理 【2 叭，错误的数据会导致昂贵的操作费用和漫长的响应时问，影响从数据集中 抽取的模式的正确性和导出规则的准确性，使得决策支持系统产生错误的分 析结果，将会误导决策，影响信息服务的质量。因此，在从数据库中挖掘知 识之前必须对其进行一系列的预处理工作。大量的事实证明，在数据挖掘系 统中，数据预处理所占的工作量达到了整个工作量的6 0 至8 0 1 3 】。 1 2 数据预处理简介 在数据挖掘中，数据预处理就是在对数据进行数据挖掘前，先对原始数 西南交通大学硕士研究生学位论文第2 页 据进行必要的清洗、集成、转换、离散和归约等等一系列的处理工作，使之 达到挖掘算法进行知识获取研究所要求的最低规范和标准1 1 9 2 3 1 。 通过数据预处理工作，可以使残缺的数据完整，将错误的数据纠正，将 多余的数据去除，将所需的数据挑选出来并且进行数据集成，将不适应的数 据格式转换为所要求的格式，还可以消除多余的数据属性，从而达到数据类 型相同化、数据格式一致化、数据信息精练化和数据存储集中化。总而言之， 经过预处理之后，我们不仅可以得到挖掘系统所要求的数据集，使数据挖掘 成为可能；而且，还可以尽量地减少挖掘系统所付出的代价和提高挖掘出的 知识的有效性与可理解性。 数据预处理的主要任务有： 数据清洗：如填补缺失数据、消除噪声数据等。数据清洗的原理1 2 7 - 2 9 1 ， 就是通过分析“脏数据”的产生原因和存在形式，利用现有的技术 手段和方法去清洗“脏数据”，将“脏数据”转化为满足数据质量或 应用要求的数据，从而提高数据集的数据质量。 数据集成：将所用的数据统一存储在数据库、数据仓库或文件中形 成一个完整的数据集，这一过程要消除冗余数据。 数据转换：主要是对数据进行规格化( n o 珊a l i z a t i o n ) 操作，如将数据 值限定在特定的范围之内【2 3 】。对于某些挖掘模式，需要数据满足一 定的格式，数据转换能把原始数据转换为挖掘模式要求的格式，以 满足挖掘的需求。 数据归约：把那些不能够刻画系统关键特征的属性剔除掉，从而得 到精练的并能充分描述被挖掘对象的属性集合。对于需要处理离散 型数据的挖掘系统，应该先将连续型的数据量化，使之能够被处理。 1 3 数据预处理技术研究现状 目前数据挖掘在理论和应用上都获得了极大的发展，数据预处理作为其 重要的、必不可少的组成部分，技术也随之快速发展。现阶段数据预处理技 术中研究最多的是数据清洗和数据归约技术，下面将国内外有关这两方面技 术的研究现状傲如下概述： 西南交通大学硕士研究生学位论文第3 页 1 3 1 数据清洗研究现状 国外对数据清洗技术的研究，最早出现在美国，是从对全美的社会保险 号错误的纠正开始的【4 】。美国信息业和商业的发展，刺激了这方面技术的研 究。研究内容主要涉及以下几方面： 1 对数据集进行异常检测。主要有下列方法【3 0 】：采用统计学的方法来检 测数值型属性，计算属性值的均值和标准差，考虑每个属性的置信区间来 识别异常属性和记录。 2 识别并消除数据集中的近似重复对象，也就是重复记录的清洗 1 2 7 ，2 9 ，3 1 1 。它在数据仓库环境下特别重要，因为在集成不同的数据时会产生大 量的重复记录。 3 对缺失数据的清洗【4 ，5 ，6 65 1 ，研究者大多采用最近似的值替换缺失值的 方法，包括贝叶斯网络、神经网络、七最临近分类、粗集理论等，这些方法 大都需要判断缺失记录与完整记录之间的记录相似度，这是其核心问题。 目前国内对数据清洗技术的研究，还处在一个开始阶段。尽管在一些学 术期刊及学术会议上也能见到一些有关这方面的理论性文章，但直接针对数 据清洗的论文并不多。银行、保险和证券等对客户数据的准确性要求很高的 行业，都在做自己的客户数据的清洗工作，针对自己的具体应用开发软件， 且很少有理论性的文章公布出来。 1 3 2 数据归约研究现状 在海量数据上进行复杂的数据分析和挖掘将需要很长时间，数据归约技 术f 1 9 7 0 】用来得到数据集的归约表示，在归约后的数据集上挖掘将更有效。其 研究内容主要涉及： 1 高维数据的降维处理【3 3 ，7 0 1 。主要采用删除冗余属性的方法，若用手工 方法去除冗余属性就需要用到专家知识。通常使用属性子集选择方法【1 9 】，包 括逐步向前选择法、逐步向后删除法、判定树归纳法等。 2 从数据集中选择较小的数据表示形式来减少数据量，需要用到数值归 约技术【1 9 ，2 3 ，8 3 1 ，主要采用的直方图、聚类等技术。 3 离散化技术【2 3 4 1 l 减少给定连续属性值的个数。这种方法大多是递归 的，大量的时间花在每一步的数据排序上。 西南交通大学硕士研究生学位论文第4 页 求取信息系统的最小归约和所有归约是一个n p 难题【8 7 l 。目前人们已经 做了许多工作，也提出了许多算法，现有的关予归约的文献大部分都是在基 于属性重要性和基于分辨矩阵两种算法的基础上提出的启发式属性归约方法 1 8 劬。 1 4 本文的工作和内容组织 数据预处理的研究领域很广，并且包含很多不同的处理策略和技术，本 文主要从数据清洗、数据选样、数据变换、数据归约等方面，结合已经实现 的数据挖掘试验平台( d m h b ) 来讨论数据预处理技术。 第一章介绍了数据预处理问题提出的背景，有关数据预处理的知识，以 及国内外数据预处理技术的研究现状，最后介绍本文的研究内容和各章节安 排。 第二章主要介绍了现有的数据预处理技术，包括数据清洗、数据选样、 数据变换、数据归约等技术，详细研究了各类技术所采用的具体方法。 第三章是本文工作的重点，首先对数据清洗中的缺失值填充技术进行分 析，找出各类算法的差异及不足。在此基础上提出了基于聚类技术的缺失值 清洗算法，并进行了试验验证。 第四章结合前面进行的研究工作，给出了参与设计的实验性数据挖掘工 具数据挖掘试验平台。主要介绍了该平台设计的应用背景，平台的数据 预处理框架结构、设计和操作流程。 第五章总结了本文所做的研究工作，并对迸一步工作的研究方向进行了 展望。 本论文的主要贡献： ( 1 ) 提出了基于聚类技术的缺失值清洗方法。 ( 2 ) 实现了数据挖掘试验平台的数据预处理功能。 西南交通大学硕士研究生学位论文第5 页 第2 章数据预处理算法 数据预处理技术包含很多方面的内容，本章主要讨论数据清洗、数据选 样、数据变换及数据归约技术。第l 节介绍了数据清洗技术，包括重复记录 清洗和噪声数据的处理，缺失值的清洗问题将单独在第3 章提出。第2 节介 绍数据选样技术，包括简单的随机选样和复杂的逐步向前选样算法。第3 节 介绍数据变换技术，第4 节介绍数据归约技术。包含了现有的数据归约大部 分算法。 2 1 数据清洗技术 如第一章所述，现实中的数据一般不能直接用于数据挖掘，需要预处理 为满足要求的数据才能用于挖掘。缺失值清洗技术将在第三章详细讲述，在 此仅研究重复记录清洗、噪声数据处理等技术。 2 1 1 重复记录清洗 在构造数据仓库的过程中，需要从各种数据源导入大量的数据。理想情 况下，对于现实世界中的一个实体，数据库或数据仓库中应该只有一条与之 对应的记录。但在对异种信息表示的多个数据源进行集成时，由于实际数据 中可能存在数据输入错误，格式、拼写上存在差异等各种问题，导致不能正 确识别出标识同一个实体的多条记录，使得逻辑上指向同一个现实世界的实 体，在数据仓库中可能会有多个不同的表示，即同一实体对象可能对应多条 记录。 重复记录会导致错误的挖掘模式，因此有必要去除数据集中的重复记录， 以提高其后挖掘的精度和速度。每种重复记录检测方法都需要确定是否有两 个及以上的实例表示的是同一实体。有效的检测方法是对每一个实例都与其 他实例进行对比，从而发现重复实例。然而，这种方法虽然效果最好，但其 计算复杂度为o 似2 1 ，h 为数据集中的记录数，使得这种方法效率不高，并且 费时费力，在现实中一般不采用。 费时费力，在现实中一般不采用。 西南交通大学硕士研究生学位论文第6 页 为了从数据集中检测并消除重复记录，首要的问题就是如何判断两条记 录是否是重复的。这就需要比较记录的各对应属性，计算其相似度，再根据 属性的权重，进行加权平均后得到记录的相似度，如果两记录相似度超过了 某一闽值，则认为两条记录是匹配的，否则，认为是指向不同实体的记录。 排序合并方法是检测数据库中完全重复记录的标准方法【8 2 ，8 “。它的基本 思想是，先对数据集排序，然后比较相邻记录是否相等。这一方法也为在整 个数据集上检测重复记录提供了思路，目前已有的检测重复记录的方法也大 多以此思想为基础【3 s 】。目前采用的比较普遍的算法是基本近邻排序算法 ( b a s i cs o n e dn c i 卧b m h o o dm e t h o d ，s n m ) 方法。该方法的思想【3 5 j 是：将数据 集中的记录按指定的关键字( k e y ) 排序，然后在排序后的数据集上移动一个固 定大小的窗口，只检测窗口内的记录，判定它们是否匹配，以此来减少记录 的比较次数。 当前窗口 了) 下一个窗口 图2 1 窗口的滑动示意图 基本的s n m 方法主要包括以下三步： 1 ) 生成关键词：通过抽取数据集中相关属性的值为每个实例生成一个 关键字。 2 1 数据排序：按上步生成的关键字为数据集中的数据排序。尽可能的 使潜在的可能的重复记录调整到一个邻近的区域内，从而对于特定 的记录可以将进行记录匹配的对象限制在一定的范围之内。 3 ) 合并：在已排序的数据集上依次移动一个固定大小的窗口，数据集 中每条记录仅与窗口内的记录进行比较。如果窗口的大小是包含m 个记录，则每条新进入窗口的记录都要与先前进入窗口的m 1 条记 录进行比较，来检测重复记录，然后最先进入窗口内的记录滑出窗 口，最后一条记录的下一条记录移入窗口，再把此脚条记录作为下 t m 上厂ii、l 西南交通大学硕士研究生学位论文第7 页 一轮比较对象，直到数据集的最后( 如图2 1 所示) 。 2 1 2 消除噪声数据 噪声数据的出现可能有多种原因 3 0 】，由于噪声数据的存在使得数据不在 规定的数据域内，从而会影响后面的挖掘效果和结果。常用的消除噪声数据 的方法是分箱方法【2 3 】。 分箱方法通过参考周围实例的值来平滑需要处理的数据值。需要处理的 数据被分布到一些箱中，不同的分箱技术对这些值进行不同的平滑。现有的 分箱方法有等深分箱法和等宽分箱法。等深的分箱法是把数据划分到相同深 度的不同箱内。具体方法如下： ( 1 ) 按箱平均值平滑 该方法把箱中的所有值平均，然后使用箱的平均值替代箱中所有数据。 ( 2 ) 按箱边界平滑 箱中的最大和最小值被视为箱边界，箱中的每一个值被最近的箱边界值 替换。 2 2 数据选样 数据选样【l9 ”】是从数据集中选取部分数据，用于数据分析。在统计学中， 数据选样经常用在数据准备阶段和最终的数据分析。在数据挖掘中因为处理 大型数据集常常需要过高的代价和过长的处理时间，因此也常采用数据选样 方法。在某种情况下，使用数据选样方法可以减小数据集规模，使得某些效 果更好但代价较高的算法可以应用到数据集上。 有效的数据选样原则【”】是：选样后的数据集与原数据集在挖掘的效果上 应当相同。这就要求选样的数据在原数据集中应该有代表性，即选样数据在 某些特征上应与原数据集更接近。 2 2 1 简单随机选样 简单随机选样方法【2 3 是最简单最容易实现的选样方法。对于数据集中的 任意数据都有相同的被抽取概率。它有两种方法： 西南交通大学硕士研究生学位论文第8 页 1 无放回选样( s a m p i i n gw i t h o u tr e p l a c c m e n t ) 当数据被抽取到时，将该数据从数据集中删除，然后再进行下次抽取。 2 有放回选样( s a m p l i gw i t hr e p l a c e m e n t ) 当数据被抽取到时，该数据并不从全部数据中删除。在这种方法下，同 一个数据有可能被再次抽取到。这种方法比前者更容易实现。 当数据集中包含不同类型的数据对象并且数据对象的数量也不是平均分 配的时候，简单随机选样方法对数据对象较少的数据类型的选样概率较低， 这样就不能正确表征数据集。比如，若要对较少的类建立分类模型，那么就 需要在样本集中包含适量的稀有类，但是简单随机采用方法往往效果不佳。 因此，需要一种新的选样方法，该方法能够对不同频率的数据对象正确选样。 2 2 2 分层选样 如果数据集被划分为互不相交的几个部分( 层) ，则通过对每一层的随机 选样就可以得到整个数据集的选样。特别是当数据集倾斜时，可以帮助确保 样本的代表性。分层选样( s t r a t i f i e ds 锄p l i n 曲技术【2 0 l 就是在互不相交的几部 分内进行选样，其选样技术可以用简单随机选样技术。 确定样本集的大小是比较困难的任务。如果样本集大的话，那么选用样 本的代表性就大，但是这会减少选样的优点；反之，若样本集较小，那么很 多数据模式就会丢失。但是选样的大小又关系到样本集的质量，从而影响到 后面的挖掘结果。 2 2 3 逐步向前选样 逐步向前选样方法从一个小样本集开始，然后从数据集中选择样本，逐 步增加样本集的大小，直到得到一个大小合适的样本集为止1 2 1 矧。逐步向前 选样算法需要用到选样计划表s 一 枷，弘m ，n t ，其中m 脚，( f tj ) ，每个m 指定了一个样本集的大小。 样本集大小与模型精确度之间的关系【2 1 】如图2 2 所示。横坐标表示的是 样本集的大小( 介于0 和n 之间) ，纵坐标是模型的精确度，是由样本集产 生的。该曲线最初倾斜度较大，在中间部分又稍微倾斜，最后成稳定状态。 当曲线在最后接近水平状态时，样本集的增大对模型的精确度几乎没有影响。 西南交通大学硕士研究生学位论文第9 页 当曲线刚刚进入水平状态时，样本集大小与精确度的交点称为会聚点，此时， 数据集大小为一曲。当样本集的大小小于，l i n 时，模型的精确度会降低，而 当样本集大于，l 响时，模型的精确度也不会高于在甩曲下的精确度。 栉1 ，1 2n i 肛m j n 厅j 万k 州 图2 2 样本集大小与模型精确度曲线 表2 1 给出了其具体算法。然而，如何判断算法是否达到会聚点，是较 困难的。 表2 1 逐步向前选样算法 计算样本集大小的计划表s 一 ，l 们，鸭，m ) n n 0 m 一由h 个实例得到的模型 w h i i e 未达到会聚点 重新计算s ； 疗一s 中大于阼的元素： m 一由n 个实例得到的模型； r e t u r n ? m 2 3 数据变换 数据变换是将数据转换成适合于各种挖掘模式的形式，需要根据其后所 使用的数据挖掘算法，决定选用何种数据变换方法。 西南交通大学硕士研究生学位论文第1 0 页 2 3 1 简单函数变换 这种形式的数据变换只需要对每个属性值应用简单的数学函数即可。若 工是某个属性值，则这类变换包括：x ，l o g 而e 。，；，1 而s i n z ，i x i 等。在统计学 中，数据变换特别是开方、求倒数等都经常用于把非高斯分布的数据转换为 高斯分布数据。在应用简单函数变换时应该谨慎，因为有时会改变数据的原 有特性【2 6 1 。比如，当使用1 茸进行数据变换时，可以使大于1 的数据减小， 但会增大值域在( o ，1 ) 之间的数据。若给定数据 1 ，2 ，3 ) ，使用1 x 进行变换 后，成为 1 ，吉，丢 ；但是给定数据 1 ，寺，言) ，则会变换为 1 ，2 ，3 ) 。 二j j 因此，对所有的数据而言，1 x 变换法逆置了数据集的顺序，这点需要特别 留意。 2 3 2 规范化 另一种常用的方法是数据的规范化。通过将属性数据按比例缩放，使之 落入一个小的特定区间，如【o ，1 】。对于分类算法，如涉及神经网络的算法或 诸如最临近分类和聚类的距离度量分类算法，规范化特别有用。对于基于距 离的方法，规范化可以帮助防止具有较大初始值域的属性与具有较小初始值 域的属性相比，权重过大。有许多数据规范化的方法，在此介绍三种：最小 最大规范化、z s c o r e 规范化和按小数定标规范化【2 3 川。 1 最小最大规范化 该方法对原始数据进行线性变换。假定埘现a 和拼盘瓠分别为属性爿的最 小和最大值，最小最大规范化通过计算 v i 三二里堡三一m e wm a x 一以p wm i n _ ) + n e wm i n ( 2 1 ) m a x 4 一n l i n 、 一 。 将爿的值映射到区间加e m 舅加a ，忍e w 卅甜a 】中的y 。最小- 最大规范化能 保持原始数据之间的关系。 2 z s c o r e 规范化 在该方法中属性的值基于爿的平均值和标准差规范化。a 的值y 被规 范化为v ，由下式计算： 西南交通大学硕士研究生学位论文第1 1 页 。兰墨 ( 2 2 ) 其中，互和a 。分别为属性4 的平均值和标准差，j 。卫， 们薯1 障( 其中，a 为属性值，n 为数据集包含的总记录数) 。当属 vn 一1 性4 的最大署墨最小值未知，或孤立点左右了最大最小值规范化时，该方法是 有用的。 3 小数定标规范化 或称为十进制缩放方法，该方法通过移动属性爿的小数点位置进行规范 化。小数点的移动位数依赖于4 的最大绝对值。4 的值被规范化为v ，由下 式计算： v 一击 ( 2 - 3 ) i o 其中，是使得肘缸( i v 1 ) 1 的最小整数。 2 4 数据归约 数据集一般都会含有大量的属性，并且实例也非常庞大。如果在海量数 据上进行复杂的数据分析和挖掘将需要很长时间，使得这种分析不现实或不 可行。数据归约技术【”8 3 8 4 l 可以得到数据集的归约表示，它小得多，但仍接 近于保持原数据的完整性。这样，在归约后的数据集上挖掘将更有效，并产 生相同( 或几乎相同) 的分析结果。 数据归约的技术较多，下面主要介绍了维归约、属性选择和离散化技术。 2 4 1 维归约 用于数据分析的数据可能包含数以百计的属性，其中大部分属性与挖掘 任务不相关，是冗余的。遗漏相关属性或留下不相关属性是有害的，会导致 所用的挖掘算法无所适从，这可能导致发现的模式质量较差。此外，不相关 或冗余的属性增加了数据量，可能会减慢挖掘进程。使用维归约有很多益处， 最重要的是如果数据集的维较低则可以使数据挖掘算法的效果更好。 维归约主要用到的方法是属性构造1 8 。属性构造通过合并已有的属性来 西南交通大学硕士研究生学位论文第1 2 页 构造和添加新的属性。最常用的属性构造方法是根据领域专家的意见来合并 已有的属性。 2 4 2 属性选择 属性选择方法可以减少数据集中的冗余属性和不相关属性i 洲。有研究表 明，冗余和不相关属性会降低分类的精度和聚类的质量【1 9 】。 有些冗余和不相关属性可以用领域知识直接去掉，然而要得到最佳的属 性子集，则需要用到系统方法。这种方法是把所有可能的属性子集全部用来 试验数据挖掘算法，然后得到最佳的属性子集。然而，若数据集有n 个属性， 那么其所有属性子集为2 n ，这种方法费时费力，在实际中用处不大。 表2 2 是抽象的属性选择算法，概括了不同类型的属性选择算法。 表2 2 抽象的属性选择算法 输入： s 具有万个属性的数据集样本，属性集为z ，因= n j 评价方法 g s 候选属性生成策略 输出： 勋m 砌 选出的属性子集 方法： 工= 属性集x 的起点： 勘缸f f d n = 根据评价方法，得出的工中的最佳属性； d o 三= 通过6 s 从x 中生成的候选属性； r = 从上中选出的经过j 评价后的最佳属性： i f p ( z j ( 勋，“咖n ) 0 p ( x 一 ，( 勋m 咖万) i 工l c i 勋乜f f 。啊i ) ) s 口知矗佩= 盘： u n t i ls t o p ，工) 上表中的工，r 都是属性子集中间变量：s l o p 0 是停止属性子集选择的策略。 从概念上讲，属性选择是对所有可能的属性子集进行选择。属性选择策 略有很多，但选择策略应该能满足以下两个条件：( 1 ) 计算代价小，( 2 ) 能找到 最佳或接近最佳的属性子集。当然，有时并不能完全满足这两个条件，需要 西南交通大学硕士研究生学位论文第1 3 页 权衡利弊。 选出属性子集后，评价方法要对其进行评价，以确定该属性子集对于某 个特定的数据挖掘任务是否是最佳的。由于属性子集的个数较多，对它们进 行一一测试是不切实际的，需要一个标准来决定什么情况下可以停止选择。 选择标准包含以下的一种或几种策略：跌代次数，经评价后是否是最优或是 否超过了某个阈值，属性子集是否达到了某种大小等等。 一旦选出了属性子集，应该确认一下该属性子集的性能。标准是应用到 该属性子集上的数据挖掘方法得出的结果应该与应用到整个属性集上的结果 相同或相对更好。也可以使用属性权值，重要的属性赋的权值较高，次要的 属性赋的权值较小，需要使用领域知识来分配属性权值。当然，对于小数据 集，也可以让使用者自己手动选择需要的属性。 2 。4 3 离散化 离散化技术可以用于数据转换【2 3 】。比如，对数据集使用分类算法时，需 要把数据变成离散的形式；而对于关联规则发现算法，则需要变为二元变量 的属性格式。因此，有时需要从连续型数据转换为离散型数据，而有时需要 把连续型和离散型的数据转换为二元变量形式。另外，如果离散数据的值较 大，或某些值出现的频率较少，则可以通过合并这些数值来达到对离散数据 归约的目的。 离散化经常用在需要分类或关联规则分析的情况下。把连续型数据转换 为离散型数据一般包含两个予任务：( 1 ) 判断需要多少离散型数据，( 2 ) 如何把 连续型数据映射到离散型数据中。在第一步中，先对连续型数据进行排序， 然后指定n 1 个点把数据分为忍个区间。在第二步中，把落在同一个区间内 的所有连续型数据都映射到相同的离散型数据上。因此，离散化问题就变成 了如何划分区间的问题。 分箱方法也可以用于离散化。等深的分箱方法是把相同数量的属性值放 入不同箱内，然后对每个箱里的数据进行处理。在此是把箱中的所有数据取 平均值，然后把每个值用平均值来替换，从而达到属性值离散化的目的。 西南交通大学硕士研究生学位论文第1 4 页 第3 章缺失值清洗算法研究 缺失值的清洗是数据清洗过程中最关键的问题之一，也是研究较多的领 域。本章简要介绍了缺失值清洗的基本知识、基本方法，然后分别对其所涉 及的关键算法进行了详细的研究。第2 节和第3 节分别分析和研究了现有的 不同类型的缺失值清洗算法。第4 节是本章的重点，介绍了如何确定相似度 的问题，主要包括属性相似问蹶和记录相似问题，提出并研究了如何应用聚 类技术进行缺失值清洗，并给出了数据集上的实验及结果分析。 3 1 缺失值清洗简介 缺失值在许多研究领域都很常见但又难以解决【6 】比如人工智能【5 】，机 器学习【4 】等研究领域。理想情况下，数据集中的每条记录都应该是完整的。 然而，存在不完整的、含噪声的数据是大型的、现实世界数据集的共同特点。 缺失数据的出现可能有多种原因，人工输入时认为不重要而漏掉，或者被调 查人不愿公布等。 在数据集中，若某记录的属性值被标记为空白、“u n l 【o w ”或“未知” 等，则认为该记录存在缺失值，是不完整的数据。 清洗缺失数据的问题是数据清洗及数据预处理领域研究的主要问题之 一。这些不完整、不准确的数据会影响从数据集中抽取的模式的正确性和导 出规则的准确性，建立错误的数据挖掘模型，使得应用于前端的决策支持系 统产生不准确的分析结果和决策，导致企业费用的增加和利润的减少，影响 信息服务的质量。如果对客户的信用等级有着错误的认识会导致投资风险， 对某个客户的价值没有充分的认识可能导致失去顾客，错误的记录可能会导 致营销资源的浪费，等等。 当前有很多方法用于缺失值清洗，可以粗略地分为两类【1 3 】： 1 忽略不完整数据的方法； 2 基于填充技术的方法。 第一类方法最简单，并且容易实现，常用的是删除属性或实例，这种方 法通过删除含有不完整数据的属性或实例来去除不完整数据。第二类方法是 西南交通大学硕士研究生学位论文第1 5 页 采用填充算法对不完整数据进行填充，大多是通过分析完整数据来对不完整 数据进行填充，是完整数据分析方法。 下面，具体介绍这两类算法。 3 2 忽略不完整数据的缺失值清洗算法 清洗缺失值有很多简单的方法，比如，删除属性或实例【”_ 18 1 。删除属性 是把含有不完整数据的属性全部删除，删除实例是把含有不完整数据的实例 删除。 删除属性或实例是常用的方法，很多统计工具都把该方法作为缺省方法。 虽然该方法具有效率高的特点，但是，它的缺点也比较明显。 1 最显然的是这种方法删除了相当多的信息。如果在一个小数据集中删 除一些含有不完整数据的属性或实例，那么会使该数据集更小，从而使得剩 余的数据在构建一些模型时变得毫无意义，建立的模型也不容易让人信赖。 2 同时，该方法会使数据集产生偏差。当经过该方法处理过的数据用于 数据挖掘的分类、聚类等时，分类或聚类模型将产生倾斜，从而使得挖掘结 果产生误导。这一点是需要特别强调的。 3 3 基于填充技术的缺失值清洗算法 如果使用忽略不完整数据的缺失值清洗方法，那么很有可能将潜在的有 价值的信息也一并删除，这比含有不完整数据的情况还要严重1 4 2 1 。比较好的 做法是把那些不完整的数据填充上，而不是删除掉。缺失值填充算法用于缺 失值的处理，即把缺失值用最接近它的值来替代，从而提高可用数据的数量。 填充方法可以保留潜在的有用数据，而不必删除不完整数据。填充算法比删 除属性或实例方法运用了更多的不完整数据，并且不易于产生偏差。 缺失值填充算法在当前是一个研究热点，所以这类算法比较多。具体可 以分为统计方法、分类方法、关联规则分类方法等。当然，还有其它一些填 充算法，在本节将具体介绍。 西南交通大学硕士研究生学位论文第1 6 页 3 3 1 采用统计方法清洗缺失值 这类方法主要通过对数据的分析，得出数据集的统计信息，然后利用这 些信息清洗缺失值。其中最简单也最常用的方法是平均值填充方法【7 ，8 1 。 均值填充法是最常用的缺失值填充法，它把完整数据的算术平均值作为 缺失数据的值。安德逊等1 9 】提出的原理是“在正态分布下，样本均值是估算 出的最佳的可能取值”。应用均值填充法将会影响缺失数据与其它数据之间的 相关性。而且，如果一个大数据集采用均值填充法，被填充的变量的频率分 布有可能会产生误导，因为过多的中值会产生更多的尖峰态分布【1 0 】。 3 3 2 采用分类方法清洗缺失值 数据分类是数据挖掘的一种非常重要的方法【矧。当人们面对海量的数据 时，首先要对这些数据进行分类，然后再对较小的数据集进行分析研究。这 符合人类遇到复杂问题时采取的“分而治之”的策略。 分类的概念是在已有数据的基础上构造出一个分类函数或模型，即通常 所说的分类器( c l a s s i 丘e r ) 。该函数或模型能够把数据库中的数据记录映射到 给定类别中的某一个类别。要构造分类器，需要有一个训练样本数据集作为 输入。训练集( t r a i n i n gs e t ) 由一组数据集记录构成，每个记录是一个由关键属 性值组成的特征向量，我们把用于分类的属性叫做标签( l a b c l ) ，标签属性也 就是训练集的类别标记。一个具体的样本的形式可以表示为( x b 毒：，赫；c ) ， 其中嗣表示属性值，c 表示类别。 数据分类技术，如贝叶斯网络、神经网络等已被用于清洗缺失值，还有 其他分类方法，如七最临近分类、粗集理论等也都用来清洗缺失值，以下将 会分别介绍。 3 3 2 1 基于神经网络的清洗方法 神经网络( a n n ) 最早是由心理学家和神经生物学家提出的，旨在寻求开 发和测试神经的计算模拟【1 ”。神经网络需要很长的训练时间，因而对于有足 够长训练时间的应用更合适。它需要大量的参数，这些主要靠经验确定，如 网络拓扑或“结构”。神经网络的优点包括其对噪声数据的高承受能力，以及 西南交通大学硕士研究生学位论文第1 7 页 它对未经训练的数据分类模式的能力。 在构建神经网络时有几点需要注意： 1 需确定输入层的节点数； 2 确定输出层的节点数： 3 必须选择网络拓扑( 比如，隐含层的层数或隐含层的节点数) 结构： 4 随机初始化权重； 5 训练样本必须是完整数据，如果存在缺失值则要去除该实例。 神经网络的特点如下【1 5 l ： 第一，神经网络很难解释，目前还没有能对神经网络作出显而易见解释 的方法学； 第二，神经网络可以处理属性冗余问题。在网络训练阶段权值自动学习， 冗余属性的权值较小； 第三，神经网络会学习过度，在训练神经网络是一定要恰当的使用一些 能严格衡量神经网络的方法，如测试集方法和交叉验证法等。这主要是由于 神经网络太灵活、可变参数太多。 第四，除非问题非常简单，训练一个神经网络可能需要相当可观的时间 才能完成。 第五，建立神经网络需要做的数据准备工作量很大。 3 3 2 2 贝叶斯网络清洗方法 贝叶斯网络(