数据仓库与数据挖掘技术第6章 数据预处理技术主讲人：孙水华 副教授信息科学与工程学院数据仓库与数据挖掘技术数据预处理技术目 录n数据预处理概述 n数据清理 n数据集成n数据变换 n数据归约 n小 结数据仓库与数据挖掘技术数据预处理技术 数据预处理(data preprocessing)是指在对数据进行数据挖掘主要的处理以前，先对原始数据进行必要的清洗、集成、转换、离散和归约等等一系列的处理工作，以达到挖掘算法进行知识获取研究所要求的最低规范和标准。 现实世界的数据库往往易受噪声、丢失数据和不一致数据的侵扰，因为数据库太大(常常多达数千兆字节，甚至更多)，并且多半来自多个异构数据源。低质量的数据将导致低质量的挖掘结果。这就需要进行数据预处理，从而提高数据质量，进而提高挖掘结果的质量。 现在人们已经积累了大量的数据预处理技术。如何恰当选择和应用这些技术得到更有效的数据，是一个值得探讨的问题。数据仓库与数据挖掘技术数据预处理技术 数据仓库和数据挖掘的应用产生了大量的数据，这些数据不一定是规范化的，它以不同的形式存储在不同的地方。根据“垃圾进，垃圾出”原理，这些低质量的数据进入系统将会导致昂贵的操作费用和系统漫长的响应时间，并且对从数据集中抽取的模式的正确性和导出规则的准确性产生巨大的影响，更严重的是会使得决策支持系统产生错误的分析结果，误导决策。6.1 数据预处理概述数据预处理概述6.1.1 数据预处理的必要性数据预处理的必要性数据仓库与数据挖掘技术数据预处理技术 现实世界采集到的大量的各种各样的数据是不符合挖掘算法进行知识获取研究所要求的规范和标准的。主要具有以下特征： （1）不完整性。指的是数据记录中可能会出现有些数据属性的值丢失或不确定的情况，还有可能缺失必需的数据。这是由于系统设计时存在的缺陷或者使用过程中一些人为因素所造成的，如有些数据缺失只是因为输入时认为是不重要的；相关数据没有记录可能是由于理解错误，或者因为设备故障；与其他记录不一致的数据可能已经删除；历史记录或修改的数据可能被忽略等等。数据仓库与数据挖掘技术数据预处理技术 （2）含噪声。指的是数据具有不正确的属性值，包含错误或存在偏离期望的离群值。产生的原因很多。比如收集数据的设备可能出故障；人或计算机的错误可能在数据输入时出现；数据传输中也可能出现错误。不正确的数据也可能是由命名约定或所用的数据代码不一致，或输入字段(如时间)的格式不一致而导致的。实际使用的系统中，还可能存在大量的模糊信息，有些数据其至还具有一定的随机性。 （3）杂乱性(不一致性)。原始数据是从各个实际应用系统中获取的，由于各应用系统的数据缺乏统一标准的定义，数据结构也有较大的差异，因此各系统间的数据存在较大的不一致性，往往不能直接拿来使用。同时来自不同的应用系统中的数据由于合并而普遍存在数据的重复和信息的冗余现象。数据仓库与数据挖掘技术数据预处理技术 常见的数据预处理方法有：数据清洗、数据集成、数据变换和数据归约。图6.1给出了数据预处理的典型形式。6.1.2 数据预处理的基本方法数据预处理的基本方法数据清理数据集成数据变换数据归纳-2,32,100,59,48-0.02,0.32,1.00,0.59,0.48属性属性图6.1 数据预处理的典型形式数据仓库与数据挖掘技术数据预处理技术 数据清理(data cleaning)处理例程通常包括：填补遗漏的数据值、平滑有噪声数据、识别或除去异常值，以及解决不一致问题。 数据集成(data integration)就是将来至多个数据源的数据合并到一起，形成一致的数据存储，如将不同数据库中的数据集成入一个数据仓库中存储。之后，有时还需要进行数据清理以便消除可能存在的数据冗余。 数据变换(data transformation)主要是将数据转换成适合于挖掘的形式，如将属性数据按比例缩放，使之落入一个比较小的特定区间。这一点对那些基于距离的挖掘算法尤为重要。包括平滑处理、聚集处理、数据泛化处理、规格化、属性构造。 数据归约(data reduction)在不影响挖掘结果的前提下，通过数值聚集、删除冗余特性的办法压缩数据，提高挖掘模式的质量，降低时间复杂度。数据仓库与数据挖掘技术数据预处理技术 目前，数据仓库和数据挖掘在理论和应用上都获得了极大的发展，数据预处理作为其重要的、必不可少的组成部分，技术也随之快速发展。现阶段数据预处理技术中研究最多的是数据清洗和数据归约技术。6.1.3 数据预处理的研究现状数据预处理的研究现状数据仓库与数据挖掘技术数据预处理技术 数据清洗研究内容主要涉及以下几方面： （1）对数据集进行检测。现阶段主要有以下方法：可以采用统计学的方法来对数据进行统计分析，计算属性值的各种数值，如考虑属性值之间差别大小，方差等。还有可以对与其他数据格式不一致的数据进行格式转换，使之格式符合数据挖掘的需要。 （2）对数据集中重复的对象进行消除，也就是对重复记录的清理。对重复数据的处理在数据仓库环境下特别重要，因为在具有多个数据源的时候可能会产生大量的重复记录。 （3）对缺失数据的补齐，研究者大多采用可靠的算法将与缺失的值最相似的值替换缺失值的方法，包括贝叶斯网络、神经网络、k-最临近分类、粗糙集理论等，这些方法大都需要判断缺失记录与完整记录之间的记录相似度，这是其核心问题。数据仓库与数据挖掘技术数据预处理技术 数据归约技术及其主要内容为： （1）降维处理。主要采用删除冗余属性的方法，若用手工方法去除冗余属性就需要用到专家知识。通常使用属性子集选择方法，包括逐步向前选择法、逐步向后删除法、判定树归纳法等。 （2）从数据集中选择较小的数据表示形式来减少数据量，需要用到数值归约技术，主要采用直方图、聚类等技术。 （3）对信息系统中与决策属性没有关联或者关联度不大的属性进行约简。通过属性约简算法之后可以得到关键属性，减少冗余属性，从而减少得到决策结果所需要的时间。 （4）离散化技术减少给定连续属性值的个数。这种方法可以通过简化运算量，但大多是递归的，需要花费大量的时间在每一步的数据排序上。数据仓库与数据挖掘技术数据预处理技术 数据清洗可以分为有监督和无监督两类。有监督过程是在领域专家的指导下，分析收集的数据，去除明显错误的噪声数据和重复记录，填补缺值数据；无监督过程是用样本数据训练算法，使其获得一定的经验，并在以后的处理过程中自动采用这些经验完成数据清洗工作。6.2 数据清理数据清理数据仓库与数据挖掘技术数据预处理技术6.2.1 填充缺失值填充缺失值 很多的数据都有缺失值。比如，银行房屋贷款信用风险评估中的客户数据，其中的一些属性可能没有记录值，如客户的家庭月总收入。填充丢失的值，可以用下面的方法。 （1）忽略元组。当缺少类标号时通常这样做(假定挖掘任务涉及分类)。除非元组有多个属性缺少值，否则该方法不是很有效。当每个属性缺少值的百分比变化很大时，它的性能特别差。 （2）人工填写缺失值。此方法很费时，特别是当数据集很大、缺少很多值时，该方法可能不具有实际的可操作性。数据仓库与数据挖掘技术数据预处理技术 （3）使用一个全局常量填充缺失值。将缺失的属性值用同一个常数(如“Unknown”或-)替换。但这种方法因为大量的采用同一个属性值可能会误导挖掘程序得出有偏差甚至错误的结论，因此要小心使用。 （4）用属性的均值填充缺失值。例如，已知重庆市某银行的贷款客户的平均家庭月总收入为9000元，则使用该值替换客户收入中的缺失值。 （5）用同类样本的属性均值填充缺失值。例如，将银行客户按信用度分类，就可以用具有信用度相同的贷款客户的家庭月总收入替换家庭月总收入中的缺失值。 （6）使用最可能的值填充缺失值。可以用回归、使用贝叶斯形式化的基于推理的工具或决策树归纳确定。例如，利用数据集中其他客户顾客的属性，可以构造一棵决策树来预测家庭月总收入的缺失值。数据仓库与数据挖掘技术数据预处理技术 （7）用最邻近方法填充缺失值。 方法36使数据偏置，填入的值可能不正确。然而，方法6是流行的策略，与其他方法相比，它使用已有数据的大部分信息来预测缺失值。在估计家庭月总收入的缺失值时，通过考虑其他属性的值，有更大的机会保持家庭月总收入和其他属性之间的联系。数据仓库与数据挖掘技术数据预处理技术6.2.2 光滑噪声数据光滑噪声数据 噪声(noise)是被测量的变量的随机误差或方差。给定一个数值属性，如price，我们怎样才能“光滑”数据，去掉噪声?我们看看下面的数据光滑技术。 （1）分箱(binning)。分箱方法通过考察数据的“近邻”(即周围的值)来光滑有序数据的值。有序值分布到一些“桶”或箱中。由于分箱方法考察近邻的值，因此进行局部光滑。一般来说，宽度越大光滑效果越大。箱也可以是等宽的，每个箱值的区间范闱是个常量。 （2）回归。可以用一个函数(如回归函数)拟合数据来光滑数据。线性回归涉及找出拟合两个属性(或变量)的“最佳”线，使得一个属性可以用来预测另一个。多元线性回归是线性回归的扩展，其中涉及的属性多于两个，并且数据拟合到一个多维曲面。数据仓库与数据挖掘技术数据预处理技术 （3）聚类。可以通过聚类检测离群点，将类似的值组织成群或“簇”。直观地，落在簇集合之外的值视为离群点。 （4）人工检测。人工检测是由专业人员识别孤立点。通过人与计算机的结合，相比单纯手动检查整个数据库可以提高效率。数据仓库与数据挖掘技术数据预处理技术 把数据清理作为一个过程，该过程包括下列两个步骤： 第一步是偏差检测第一步是偏差检测(discrepancy detection)。发现噪声、离群点和需要考察的不寻常的值时，可以使用已有的关于数据性质的知识。这种知识或“关于数据的数据”称作元数据。考察每个属性的定义域和数据类型、每个属性可接受的值、值的长度范围；考察是否所有的值都落在期望的值域内、属性之间是否存在已知的依赖；把握数据趋势和识别异常，比如远离给定属性均值超过两个标准差的值可能标记为潜在的离群点。另一种错误是源编码使用的不一致问题和数据表示的不一致问题(如日期“20090925”和“25092009”)。而字段过载(field overloading)是另一类错误源。考察数据还要遵循唯一性规则、连续性规则和空值规则。可以使用其他外部材料人工地加以更正某些数据不一致。如数据输入时的错误可以使用纸上的记录加以更正。但大部分错误需要数据变换。6.2.3 数据清理过程数据清理过程数据仓库与数据挖掘技术数据预处理技术第二步是纠正偏差。第二步是纠正偏差。也就是说，一旦发现偏差，通常我们需要定义并使用(一系列)变换来纠正它们。商业工具可以支持数据变换步骤。但这些工具只支持有限的变换，因此，我们常常可能选择为数据清理过程的这一步编写定制的程序。偏差检测和纠正偏差这两步过程迭代执行。随着我们对数据的了解增加，重要的是要不断更新元数据以反映这种知识。这有助于加快对相同数据存储的未来版本的数据清理速度。数据仓库与数据挖掘技术数据预处理技术6.3 数据集成数据集成 数据集成主要是将多文件或多数据库运行环境中的异构数据进行合并处理，解决语义的模型性问题。该部分主要涉及数据的选择、数据的冲突问题以及不一致数据的处理问题。 在数据集成时，首先需要考虑的是模式集成和对象匹配问题。来自多个信息源的现实世界的等价实体的匹配涉及实体识别问题。例如，判断一个数据库中的customer_id与另一个数据库中的cust_number是否是相同的属性。每个属性的元数据可以用来帮助避免模式集成的错误，元数据还可以用来帮助变换数据。数据仓库与数据挖掘技术数据预处理技术 冗余是在数据集成时另一个需要考虑的重要问题。一个属性可能是冗余的，如果它能由另一个或另一组属性“导出”。属性或维命名的不一致也可能导致结果数据集中的冗余。 有些冗余可以被相关分析检测到。给定两个属性，这种分析可以根据可用的数据度量（两个属性之间的相关系数）估计一个属性能在多大程度上蕴涵另一个属性。对于数值属性a和b，之间的相关系数rAB为 数据仓库与数据挖掘技术数据预处理技术 其中，n是数据集的样本个数，ai和bi分别是元组i中a和b的值，和分别是a和b的均值，A和B分别是a和b的标准差，即数据仓库与数据挖掘技术数据预处理技术 -1rab+l。如果rab大于0，则a和b是正相关的，该值越大，相关性越强(即每个属性蕴涵另一个的可能性越大)。因此，一个较高的rab值表明a(或b)可以作为冗余而被去掉。如果结果值等于0，则a和b是独立的， 不存在相关。如果结果值小于0，则a和b是负相关的，一个值随另一个的减少而增加。这意味每一个属性都阻止另一个属性的出现。数据仓库与数据挖掘技术数据预处理技术 数据集成的第三个重要问题是数据值冲突的检测与处理。例如，对于现实世界的同一实体，来自不同数据源的属性值可能不同。这可能是因为表示、比例或编码不同。例如，重量属性可能在一个系统中以公制单位存放，而在另一个系统中以英制单位存放。对于连锁旅馆，不同城市的房价不仅可能涉及不同的货币，而且可能涉及不同的服务(如免费早餐)和税。数据仓库与数据挖掘技术数据预处理技术 数据变换把数据转换成适应于挖掘的形式。通过对某些属性按比例进行缩放，使属性取值落在较小的区间，例如数值型属性可以规范化到0，1区间，这种变换对聚类、神经网络等算法都是必要的。连续属性离散化也是决策树等分类分析常用的预处理。 属性规范化会减少挖掘过程所用的时间，而且规范化可以有效地避免较大取值的属性对数据挖掘的过度影响。 数据变换主要涉及如下方法：光滑、聚集 、数据泛化、规范化 。6.4 数据变换数据变换数据仓库与数据挖掘技术数据预处理技术（1）光滑 光滑：光滑：去掉数据中的噪声。这种技术包括分箱、回归和聚类等。回归和聚类技术在后面介始，这里简要介绍一下分箱技术。分箱是通过分析邻近的值平滑存储数据的值，可处理连续型和分类型变量，以得到更少的变量取值种类以便于分析。数据被分布到箱中，分箱的方法是进行局部的平滑，也可以作为一种离散化技术使用。在图6.2中，学生的数学成绩（已排序）被划分存入到等深的深度为3的箱中，然后采用下面的方法之一平滑。 1）按箱平均值平滑分箱：箱中每一个值都按箱中的平均值替换，例如箱1中的值61、65、69的平均值是65，该箱中的每一个值被箱中的平均值65替换。 2）按箱中值平滑：箱中的每一个值，按箱中的中值替换。 3）按箱边界平滑：箱中的最大和最小值被视为箱边界。箱中的每一个值被最近的边界替换。 数据仓库与数据挖掘技术数据预处理技术数据仓库与数据挖掘技术数据预处理技术（2）聚集 聚集：聚集： 对数据进行汇总或聚集。例如，可以聚集日销售数据，计算月和年销售量。通常，这一步用来为多粒度数据分析构造数据立方体。聚集产生较小的数据集，使得分析的数据更稳定，但也应注意可能会丢失有趣的细节。 数据仓库与数据挖掘技术数据预处理技术（3）数据泛化 数据泛化：数据泛化：使用概念分层，用高层概念替换低层或“原始”数据。例如，分类的属性，如街道，可以泛化为较高层的概念，如城市或国家。类似地，数值属性如年龄，可以映射到较高层概念如青年、中年和老年。数据仓库与数据挖掘技术数据预处理技术（4）规范化 规范化：规范化：如果描述样本或记录的变量单位不统一，数值差别比较大，就需要把数据归一化、指数化或标准化，把不同的属性进行比例缩放，使它们的值落在大致相同的范围内，如-1.O1.0或O.O1.0。 有许多数据规范化的方法，常用的有三种：最小-最大规范化、z-score规范化和按小数定标规范化。 数据仓库与数据挖掘技术数据预处理技术1）最小-最大规范化。假定mA和MA分别为属性A的最小值和最大值。最小-最大规范化通过计算将A的值v映射到区间new_mA,new_MA中的v。最小-最大规范化对原始数据进行线性变换，保持原始数据值之间的联系。如果今后的输入落在A的原始数据值域之外，该方法将面临“越界”错误。数据仓库与数据挖掘技术数据预处理技术2）z-score规范化(零均值规范化)。把属性A的值v基于A的均值和标准差规范化为v，通过下列公式计算：其中，和A分别为属性A的均值和标准差。当属性A的实际最大和最小值未知，或离群点左右了最大-最小规范化时，该方法是有用的。假定属性平均家庭月总收入的均值和标准差分别为9000元和2400元，值12600元使用z-score规范化转换为：数据仓库与数据挖掘技术数据预处理技术3）小数定标规范化。通过移动属性A的小数点位置进行规范化。小数点的移动位数依赖于A的最大绝对值。A的值v规范化为v，由下式计算： 其中，j是使得Max(|v|)1的最小整数。例如，假定A的取值是-975923。A的最大绝对值为975。使用小数定标规范化，用1 000(即j=3)除每个值，这样，-975规范化为-0.975，而923被规范化为0.923。规范化将原来的数据改变，特别是上面的后两种方法。有必要保留规范化参数(如均值和标准差，如果使用z-score规范化)，以便将来的数据可以用一致的方式规范化。数据仓库与数据挖掘技术数据预处理技术（5）属性构造 属性构造属性构造(或特征构造或特征构造)：属性构造是由给定的属性构造和添加新的属性，帮助提高准确率和对高维数据结构的理解。可以构造新的属性并添加到属性集中，以帮助挖掘过程。数据仓库与数据挖掘技术数据预处理技术 有些数据属性对发现任务是没有影响的，这些属性的加入会大大影响挖掘效率，甚至还可能导致挖掘结果的偏差。数据简化是在对发现任务和数据本身内容理解的基础上，寻找依赖于发现目标的表达数据的有用特征，以缩减数据模型，从而在尽可能保持数据原貌的前提下最大限度地精简数据量。 下面介绍几种常见的数据归约技术。6.5 数据归约数据归约数据仓库与数据挖掘技术数据预处理技术6.5.1 数据立方体聚集数据立方体聚集 数据立方体存储多维聚集信息。每个单元存放一个聚集值，对应于多维空间的一个数据点，每个属性可能存在概念分层，允许在多个抽象层进行数据分析。数据立方体提供对预计算的汇总数据进行快速访问，因此，适合联机数据分析处理和数据挖掘。例如收集的数据是某公司过去几年间每个季度的销售数据，而感兴趣的数据是年销售数据，可以通过对数据聚集汇总得到年总销售额。数据立方体聚集为在线分析处理的上钻、下钻等操作提供了可以快速访问的汇总数据。数据仓库与数据挖掘技术数据预处理技术 数据立方体聚集的基础是概念分层，用于处理数据立方体中的数据。在概念分层的最低抽象层创建的立方体称为基本方体(base cuboid)。基本方体应当对应于感兴趣的个体实体。即最低层应当是对应于分析可用的或有用的数据。最高层抽象的立方体称为顶点方体(apex cuboid)。对不同抽象层创建的数据立方体称为方体(cuboid)，因此数据立方体可以看作方体的格(lattice of cuboids)。每个较高层抽象将进一步减少结果数据的规模。当回答数据挖掘查询时，应当使用与给定任务相关的最小可用方体。数据仓库与数据挖掘技术数据预处理技术6.5.2 属性子集选择属性子集选择 用于分析的数据集可能包含数以百计的属性，其中大部分属性与挖掘任务不相关或冗余。 属性子集选择的基本启发式方法包括以下几种： （1）逐步向前选择。该过程由空属性集作为归约集开始，确定原属性集中最好的属性，并将它添加到归约集中。在其后的每一次迭代步，将剩下的原属性集中最好的属性添加到该集合中。 （2）逐步向后删除。该过程由整个属性集开始。在每一步，删除尚在属性集中最差的属性。 （3）向前选择和向后删除的结合。可以将逐步向前选择和向后删除方法结合在一起，每一步选择一个最好的属性，并在剩余属性中删除一个最差的属性。数据仓库与数据挖掘技术数据预处理技术 （4）决策树归纳。决策树算法最初是用于分类的。决策树归纳构造一个类似于流程图的结构，其中每个内部(非树叶)节点表示一个属性的测试，每个分枝对应于测试的一个输出；每个外部(树叶)节点表示一个类预测。在每个节点，算法选择“最好”的属性，将数据划分成类。当决策树归纳用于属性子集选择时，由给定的数据构造决策树。不出现在树中的所有属性假定是不相关的。出现在树中的属性形成归约后的属性子集。方法的结束标准可以不同。该过程可以使用一个度量阈值来决定何时停止属性选择过程。数据仓库与数据挖掘技术数据预处理技术6.5.3 维度归约维度归约 维度归约使用数据编码或变换，以便得到原数据的归约或“压缩”表示。两种流行、有效的有损的维归约方法是：小波变换和主成分分析。数据仓库与数据挖掘技术数据预处理技术1. 小波变换 小波变换可以用于多维数据，如数据立方体。可以按以下方法做：首先将变换用于第一个维，然后第二个，如此下去。计算复杂性关于立方体中单元的个数是线性的。对于稀疏或倾斜数据和具有有序属性的数据，小波变换给出很好的结果。小波变换有许多实际应用，包括指纹图像压缩、计算机视觉、时间序列数据分析和数据清理。 数据仓库与数据挖掘技术数据预处理技术2主成分分析 主成分分析(Principal Components Analysis，PCA)搜索k个最能代表数据的n维正交向量，其中kn。这样，原来的数据投影到一个小得多的空间，导致维度归约。PCA通过创建一个替换的、更小的变量集“组合”属性的基本要素。原数据可以投影到该较小的集合中。PCA常常揭示先前未曾察觉的联系，并因此允许解释不寻常的结果。基本过程如下： （1）对输入数据规范化，使得每个属性都落入相同的区间。此步有助于确保具有较大定义域的属性不会支配具有较小定义域的属性。数据仓库与数据挖掘技术数据预处理技术 （2）PCA计算k个标准正交向量，作为规范化输入数据的基。这些是单位向量，每一个方向都垂直于另一个。这些向量称为主成分。输入数据是主成分的线性组合。 （3）对主成分按“重要性”或强度降序排列。主成分基本上充当数据的新坐标轴，提供关于方差的重要信息。也就是说，对坐标轴进行排序，使得第一个坐标轴显示数据的最大方差，第二个显示次大方差，如此下去。 （4）主成分根据“重要性”降序排列，则可通过去掉较弱的成分(即方差较小)来归约数据的规模。使用最强的主成分，应当能够重构原数据的很好的近似。PCA计算开销低，可以用于有序和无序的属性，并且可以处理稀疏和倾斜数据。多于2维的多维数据可以通过将问题归约为2维问题来处理。主成分可以用作多元回归和聚类分析的输入。与小波变换相比，PCA能够更好地处理稀疏数据，而小波变换更适合高维数据。数据仓库与数据挖掘技术数据预处理技术6.5.4 数值归约数值归约 数值归约技术指的是选择替代的、“较小的”数据表示形式来减少数据量。几种常用数值归约技术如下：数据仓库与数据挖掘技术数据预处理技术1回归和对数线性模型 回归和对数线性模型可以用来近似给定的数据。在(简单)线性回归中，对数据建模，使之拟合到一条直线。例如，可以用以下公式，将随机变量y(称作响应变量)建模为另一随机变量x(称为预测变量)的线性函数。 y=wx+b 其中，假定y的方差是常量。在数据挖掘中，x和y是数值数据库属性。系数w和b(称作回归系数)分别为直线的斜率和Y轴截距。系数可以用最小二乘方法求解，它最小化分离数据的实际直线与直线估计之间的误差。多元线性回归是(简单)线性回归的扩充，允许响应变量y建模为两个或多个预测变量的线性函数 。 数据仓库与数据挖掘技术数据预处理技术2直方图 直方图使用分箱来近似数据分布。属性A的直方图将A的数据分布划分为不相交的子集或桶。如果每个桶只代表单个属性值频率对，则称为单桶。通常，桶表示给定属性的一个连续区间。 确定桶和属性值的划分规则，包括如下： （1）等宽。在等宽直方图中，每个桶的宽度区间是一致的。 （2）等频(或等深)。在等频直方图中，创建桶，使得每个桶的频率粗略地为常数(即每个桶大致包含相同个数的邻近数据样本)。数据仓库与数据挖掘技术数据预处理技术 （3）V最优。给定桶的个数，对于所有可能的直方图，则V最优直方图是具有最小方差的直方图。直方图的方差是每个桶代表的原来值的加权和，其中权等于桶中值的个数。 （4）MaxDiff：在MaxDiff直方图中，考虑每对相邻值之间的差。桶的边界是具有-1个最大差的对，其中是用户指定的桶数。V最优和MaxDiff直方图看来是最准确和最实用的。对于近似稀疏和稠密数据、高倾斜和均匀的数据，直方图是高度有效的。多维直方图可以表现属性间的依赖，这种直方图能够有效地近似多达5个属性的数据。但有效性尚需进一步研究。对于存放具有高频率的离群点，单桶是有用的。数据仓库与数据挖掘技术数据预处理技术3聚类 聚类技术将数据元组视为对象。它将对象划分为群或簇，使一个簇中的对象相互“相似”，而与其他簇中的对象“相异”。通常，相似性基于距离函数，用对象在空间中的“接近”程度定义。簇的“质量”可以用直径表示，直径是簇中任意两个对象的最大距离。质心距离是簇质量的另一种度量，定义为由簇质心(表示“平均对象”，或簇空间中的平均点)到每个簇对象的平均距离。数据仓库与数据挖掘技术数据预处理技术4抽样 抽样可以作为一种数据归约技术使用，因为它允许用数据的小得多的随机样本(子集)表示大型数据集。最常用的抽样方法有4种：(假定大型数据集D包含N个元组) （1）s个样本无放回简单随机抽样(SRSWOR)。 （2）s个样本有放回简单随机抽样(SRSWR)。 （3）聚类抽样：如果D中的元组分组放入M个互不相交的“簇”，则可以得到s个簇的简单随机抽样(SRS)，其中sM。例如，数据库中元组通常一次检索一页，这样每页就可以视为一个簇。也可以利用其他携带更丰富语义信息的聚类标准。数据仓库与数据挖掘技术数据预处理技术 （4）分层抽样：如果D划分成互不相交的部分，称作层，则通过对每一层的SRS就可以得到D的分层样本。特别是当数据倾斜时，这可以帮助确保样本的代表性。 采用抽样进行数据归约的优点是，得到样本的花费正比于样本集的大小s，而不是数据集的大小N。因此，抽样的复杂度子线性(sublinear)于数据的大小。其他数据归约技术至少需要完全扫描D。对于固定的样本大小，抽样的复杂度仅随数据的维数n线性地增加；而其他技术，如使用直方图，复杂度随n指数增长。 用于数据归约时，抽样最常用来估计聚集查询的回答。在指定的误差范围内，可以确定(使用中心极限定理)估计一个给定的函数所需的样本大小。样本的大小s相对于N可能非常小。对于归约数据集的逐步求精，只需要简单地增加样本大小即可。数据仓库与数据挖掘技术数据预处理技术6.5.5 数据离散化与概念分层数据离散化与概念分层 通过将属性值域划分为区间，数据离散化技术可以用来减少给定连续属性值的个数。区间的标记可以替代实际的数据值。用少数区间标记替换连续属性的数值，从而减少和简化了原来的数据。这导致挖掘结果的简洁、易于使用的、知识层面的表示。 对于给定的数值属性，概念分层定义了该属性的一个离散化。通过收集较高层的概念(如青年、中年或老年)并用它们替换较低层的概念(如年龄的数值)，概念分层可以用来归约数据。通过这种数据泛化，尽管细节丢失了，但是泛化后的数据更有意义、更容易解释。 这有助于通常需要的多种挖掘任务的数据挖掘结果的一致表示。此外，与对大型未泛化的数据集挖掘相比，对归约的数据进行挖掘所需的I/O操作更少，并且更有效。正因为如此，离散化技术和概念分层作为预处理步骤，在数据挖掘之前而不是在挖掘过程进行。数据仓库与数据挖掘技术数据预处理技术1数值数据的离散化和概念分层产生 数值属性的概念分层可以根据数据离散化自动构造。通常，每种方法都假定待离散化的值已经按递增序排序。 （1）分箱分箱是一种基于箱的指定个数自项向下的分裂技术。通过使用等宽或等频分箱，然后用箱均值或中位数替换箱中的每个值，可以将属性值离散化，就像分别用箱的均值或箱的中位数光滑一样。这些技术可以递归地作用于结果划分，产生概念分层。分箱并不使用类信息，因此是一种非监督的离散化技术。它对用户指定的箱个数很敏感，也容易受离群点的影响。数据仓库与数据挖掘技术数据预处理技术 （2）直方图分析 像分箱一样，直方图分析也是一种非监督离散化技术，因为它也不使用类信息。使用等频直方图，理想地分割值使得每个划分包括相同个数的数据元组。直方图分析算法可以递归地用于每个划分，自动地产生多级概念分层，直到达到预先设定的概念层数过程终止。也可以对每一层使用最小区间长度来控制递归过程。最小区间长度设定每层每个划分的最小宽度，或每层每个划分中值的最少数目。直方图也可以根据数据分布的聚类分析进行划分。 数据仓库与数据挖掘技术数据预处理技术 （3）基于熵的离散化 熵(entropy)是最常用的离散化度量之一。基于熵的离散化是一种监督的、自顶向下的分裂技术。它在计算和确定分裂点(划分属性区间的数据值)时利用类分布信息。对离散数值属性A，选择A的具有最小熵的值作为分裂点，并递归地划分结果区间，得到分层离散化。这种离散化形成A的概念分层。数据仓库与数据挖掘技术数据预处理技术 （4）基于x2分析的区间合并 采用自底向上的策略，递归地找出最佳邻近区间，然后合并它们，形成较大的区间。这种方法是监督的，它使用类信息。其基本思想是，对于精确的离散化，相对类频率在一个区间内应当相当一致。因此，如果两个邻近的区间具有非常类似的类分布，则这两个区间可以合并。否则，它们应当保持分开。 初始，将数值属性A的每个不同值看作一个区间。对每对相邻区间进行x2检验。具有最小x2值的相邻区间合并在一起，因为低x2值表明它们具有相似的类分布。该合并过程递归地进行，直到满足预先定义的终止标准。数据仓库与数据挖掘技术数据预处理技术 （5）聚类分析 聚类分析是一种流行的数据离散化方法。将属性A的值划分成簇或组，聚类考虑A的分布以及数据点的邻近性，可以产生高质量的离散化结果。遵循自顶向下的划分策略或自底向上的合并策略，聚类可以用来产生A的概念分层，其中每个簇形成概念分层的一个节点。在前者，每一个初始簇或划分可以进一步分解成若干子簇，形成较低的概念层。在后者，通过反复地对邻近簇进行分组，形成较高的概念层。数据仓库与数据挖掘技术数据预处理技术 （6）根据直观划分离散化 3-4-5规则可以用来将数值数据分割成相对一致、看上去自然的区间。一般该规则根据最高有效位的取值范围，递归逐层地将给定的数据区域划分为3、4或5个相对等宽的区间。数据仓库与数据挖掘技术数据预处理技术2分类数据的概念分层产生 （1）由用户或专家在模式级显式地说明属性的偏序 通常，分类属性或维的概念分层涉及一组属性。用户或专家在模式级通过说明属性的偏序或全序，可以很容易地定义概念分层。 （2）通过显式数据分组说明分层结构的一部分 这基本上是人工地定义概念分层结构的一部分。在大型数据库中，通过显式的值枚举定义整个概念分层是不现实的。然而，对于一小部分中间层数据，我们可以很容易地显式说明分组。数据仓库与数据挖掘技术数据预处理技术 （3）说明属性集但不说明它们的偏序 用户可以说明一个属性集形成概念分层，但并不显式说明它们的偏序。然后，系统可以尝试自动地产生属性的序，构造有意义的概念分层。可以根据给定属性集中每个属性不同值的个数自动地产生概念分层。具有最多不同值的属性放在分层结构的最低层。一个属性的不同值个数越少，它在所产生的概念分层结构中所处的层次越高。在许多情况下，这种启发式规则都很顶用。在考察了所产生的分层之后，如果必要，局部层次交换或调整可以由用户或专家来做。数据仓库与数据挖掘技术数据预处理技术 （4）只说明部分属性集 在定义分层时，有时用户可能不小心，或者对于分层结构中应当包含什么只有很模糊的想法。结果，用户可能在分层结构说明中只包含了相关属性的一小部分。为了处理这种部分说明的分层结构，重要的是在数据库模式中嵌入数据语义，使得语义密切相关的属性能够捆在一起。用这种办法，一个属性的说明可能触发整个语义密切相关的属性组“拖进”，形成一个完整的分层结构。然而必要时，用户应当可以选择忽略这一特性。数据仓库与数据挖掘技术数据预处理技术6.6 小结小结 本章主要介绍了数据预处理的相关概念和主要技术。 现实世界的数据往往存在噪声、丢失数据和不一致数据等问题。为了提高挖掘结果的质量就需要进行数据预处理工作。数据预处理(data preprocessing)是指在对数据进行数据挖掘主要的处理以前，先对原始数据进行必要的清洗、集成、转换、离散和归约等等一系列的处理工作，以达到挖掘算法进行知识获取研究所要求的最低规范和标准。 人们已经积累了大量的数据预处理技术。如何恰当选择和应用这些技术得到更有效的数据，是一个值得探讨的问题。数据仓库与数据挖掘技术数据预处理技术 下课了。休息一会儿。休息一会儿。数据仓库与数据挖掘技术数据预处理技术