数据仓储与数据挖掘讲义 第4章：数据预处理

4为什么要预处理数据？4描述性数据汇总43数据清理4数据集成和变换4数据归约4.离散化和概念分层生成,第四章数据预处理,4为什么要预处理数据？,现实世界的数据是“肮脏的”不完整的：有些感兴趣的属性缺少属性值，或仅包含聚集数据(如空值）e.g.,occupation=“”含噪声的：包含错误或者“孤立点”e.g.,Salary=“-10”不一致的：在编码或者命名上存在差异e.g.,Age=“42”Birthday=“03/07/1997”e.g.,Wasrating“1,2,3”,nowrating“A,B,C”e.g.,discrepancybetweenduplicaterecords没有高质量的数据，就没有高质量的挖掘结果高质量的决策必须依赖高质量的数据数据仓库需要对高质量的数据进行一致地集成,一、数据质量的多维度量,一个广为认可的多维度量观点：精确度完整度（如排除空值）一致性合乎时机可信度,二、数据预处理的主要任务,数据清理填写空缺的值，平滑噪声数据，识别、删除孤立点，解决不一致性数据集成集成多个数据库、数据立方体或文件数据变换规范化和聚集.如年薪与年龄,销售汇总信息数据归约得到数据集的压缩表示，它小得多，但可以得到相同或相近的结果.例如数据聚集、维归约、数据压缩、概化数据离散化数据归约的一部分，通过概念分层和数据的离散化来规约数据，对数字型数据特别重要,三、数据预处理的形式,4.2描述性数据汇总,对于数据预处理，获得数据的总体印象非常重要描述性数据汇总技术用来识别数据的典型特征，突显那些数据应当视为燥声和孤立点。用户经常关心的数据的典型特征包括数据的中心趋势和离散特征中心趋势的度量包括：mean,median,mode和midrange数据离散度量包括：quartiles,outliers,variance和其他度量在大型数据库中挖掘用户感兴趣的描述统计计量涉及到如何利用关系数据库现有的函数来计算上述两类用户感兴趣的度量值关系数据库中，系统提供了以下聚集函数：count(),sum(),avg(),max(),min(),4.2.1度量中心趋势,算术平均值(mean)：,相当于SQL中的AVG函数,加权算术平均值：,截断均值：去掉头尾后，再平均,中位数(median)：如果值的个数n是奇数，则中位数是有序集合的中间值，否则它是中间两个数的平均值。用插值法(interpolation)来近似计算：,众数(mode)：出现频率最高的数据如果A1=71、A2=83、A3=71、A4=49、A5=92、A6=88，则公式“=MODE(A1:A6)”返回71。，,度量的分类,一个数据立方体的度量是一个数值函数，该函数可以对数据立方体的每一个点求值。度量可以根据其所用的聚集函数分为三类：,代数的(algebraic)：函数可以通过应用一个代数函数于一个或者多个分布度量计算的度量。比如：avg()，standard_deviation()例如:avg(A)=sum(A)/count(A)可以通过保留sum(A)、count(A)进而计算avg。,分布的(distributive)：将函数用于n个聚集值得到的结果和将函数用于所有数据得到的结果一样。比如：count()，sum()，min()，max()等例如:sum(A)=sum(A1)+sum(A2)+sum(An),整体的(holistic)：描述函数的子聚集所需的存储没有一个常数界。例如：median()(中位数)MEDIAN(11，12，13，14，15)返回13;MEDIAN(1，2，3，4，5，6)返回3.5，,均值、众数、中位数的关系：,对称vs.倾斜数据,Median（中位数）,mean（均值）andmode（众数）ofsymmetric,positivelyandnegativelyskeweddata,4.2.2度量数据的离散度,最常用度量：四分位数区间、标准差一、四分位数、孤立点和盒图百分位数(percentile)：第k个百分位数是具有如下性质的值x：数据项的k%在x上或低于x,四分位数：min,Q1,M,Q3,max,其中Q1(25%），Q3(75th)中间四分位数区间(IQR)：IQR=Q3Q1,对倾斜分布的描述，除了IQR还常需两个四分位数Q1和Q3，以及中位数M。一个识别孤立点的常用规则是：挑出落在至少高于第三个四分位数或低于第一个四分位数1.5IQR处的值,盒图四分位数的直观表示,在盒图中：端点在四分位数上，使得盒图的长度是IQR中位数M用盒内的线标记胡须延伸到最大最小观测值该盒图为在给定时间段在AllElectronics的4个分店销售的商品单价的盒图分店1中位数$80Q1:$60Q3:$100,使用盒图的数据离散的可视化描述,二、方差和标准差方差s2：n个观测之x1,x2.xn的方差是,标准差s是方差s2的平方根s是关于平均值的离散的度量，因此仅当选平均值做中心度量时使用所有观测值相同则s0，否则s0方差和标准差都是代数度量,4.2.2基本统计类描述的图形显示一、直方图,常用的显示数据汇总和分布的方法：直方图、分位数图、q-q图、散布图和局部回归曲线直方图一种单变量图形方法由一组矩形组成，这些矩形反映类在给定数据中出现的技术或频率,余略,43数据清理43空缺值,数据并不总是完整的例如：数据库表中，很多条记录的对应字段没有相应值，比如销售表中的顾客收入引起空缺值的原因设备异常与其他已有数据不一致而被删除因为误解而没有被输入的数据在输入时，有些数据因为得不到重视而没有被输入对数据的改变没有进行日志记载（不能恢复）空缺值要经过推断而补上,如何处理空缺值,忽略元组：假定挖掘任务设计为分类或描述时，缺少类标号的元组通常被忽略。元组中属性缺少值比较多时，挖掘算法的效果非常差。如天气好坏年龄人工填写空缺值：工作量大，可行性低使用一个全局变量填充空缺值：比如使用unknown或-使用属性的平均值填充空缺值使用与给定元组属同一类的所有样本的平均值使用最可能的值填充空缺值：使用像Bayesian公式或判定树这样的基于推断的方法,43噪声数据,噪声：一个测量变量中的随机错误或偏差引起不正确属性值的原因数据收集工具的问题数据输入错误数据传输错误技术限制命名规则的不一致其它需要数据清理的数据问题重复记录不完整的数据不一致的数据,如何处理噪声数据,分箱(binning):首先排序数据，并将他们分到等深（宽）的箱中然后可以按箱的平均值平滑、按箱中值平滑、按箱的边界平滑等等（）,数据平滑的分箱方法,price的排序后数据（单位：美元）：4，8，15，21，21，24，25，28，34划分为（等深的）箱：箱1：4，8，15箱2：21，21，24箱3：25，28，34用箱平均值平滑：箱1：9，9，9箱2：22，22，22箱3：29，29，29用箱边界平滑：箱1：4，4，15箱2：21，21，24箱3：25，25，34,如何处理噪声数据,聚类：将联系松散的当作孤立点监测并且去除孤立点。聚类集合之外的点即为孤立点计算机和人工检查结合计算机检测可疑数据，然后对它们进行人工判断回归通过让数据适应回归函数来平滑数据（线性回归多线性回归）,聚类,回归,x,y,y=x+1,X1,Y1,Y1,44数据集成和变换,44数据集成数据集成：将多个数据源中的数据整合到一个一致的存储中模式集成：整合不同数据源中的元数据问题1：实体识别问题：匹配来自不同数据源的现实世界的实体，比如：A.cust-id=B.customer_no？问题2：冗余问题：同一属性在不同的数据库中会有不同的字段名；一个属性可以由另外的属性导出，如如工资、基本工资、加班工资,（A-A平）（B-B平）RA,B=（n-1)AB,如果RA,B0，则A和B是正相关的；该值越大，则A涵盖B的可能性越大。,相关分析：讨论两个属性的相关性。,A平=A/nA=SQRT(A-A平)2/(n-1),其中A平、B平分别是A、B的平均值；A、B分别是A、B的标准差。,1216.7,203.3,问题3：检测并解决数据值的冲突对现实世界中的同一实体，来自不同数据源的属性值可能是不同的（如价格的单位：元、千元）可能的原因：不同的数据表示，不同的度量等等仔细将多个数据源中的数据集成起来，能够减少或避免结果数据中的冗余与不一致性，从而可以提高挖掘的速度和质量。,44数据变换,平滑：去除数据中的噪声。如分箱、聚类、回归。聚集：对数据进行聚集和汇总，数据立方体的构建数据概化：沿概念分层向上汇总规范化：将数据按比例缩放，使之落入一个小的特定区间最小最大规范化z-score规范化小数定标规范化属性构造通过现有属性构造新的属性，并添加到属性集中。,数据变换规范化,最小最大规范化:对原始数据进行线性变换，使得数据落在new_maxA,new_minA区间内。maxA,minA:属性A的最大最小值，new_maxA,new_minA:属性A的变换后区间的最大最小值例4.1（p46,一般映射到0，1区间）,z-score规范化：属性A的值基于A的平均值和标准差进行规范化。例4.2：假定属性income的平均值和标准差分别为:54,000和16,00073,600值被转换为(73600-54000)/16000=1.225（p76,例2.2，标准差p75）注意适用范围,小数定标规范化：通过移动小数点位置进行规范化。例4-3：（小数定标规范化，p46）例如：-986，-45，7，86，103，917小数定标规范化（j=3)：-0.986，-0.045，0.007，0.086，0.103，0.917,其中，j是使Max(|)1的最小整数,45数据归约,数据归约数据仓库中往往存有海量数据，在其上进行复杂的数据分析与挖掘需要很长的时间。数据归约可以用来得到数据集的归约表示，它小得多，但可以产生相同的（或几乎相同的）分析结果数据归约策略数据立方体聚集维归约数据压缩数值归约离散化和概念分层产生用于数据归约的时间不应当超过或“抵消”在归约后的数据上挖掘节省的时间。,4.5.1数据立方体聚集,最底层的方体对应于基本方体基本方体对应于感兴趣的实体（基本事实表）在数据立方体中存在着不同级别的汇总（图4）数据立方体可以看成方体的格每个较高层次的抽象将进一步减少结果数据数据立方体提供了对预计算的汇总数据的快速访问使用与给定任务相关的最小方体（基本方体，注意数据立方体的晶格结构）在可能的情况下，对于汇总数据的查询应当使用数据立方体,4.5.维归约,通过删除不相干的属性(或维)减少数据量属性子集选择找出最小属性集，使得数据类的概率分布尽可能的接近使用所有属性的原分布减少出现在发现模式上的属性的数目，使得模式更易于理解启发式的（探索性的贪心算法）方法逐步向前选择：从空集开始，逐步添加逐步向后删除：从整个属性集开始，逐步删除向前选择和向后删除相结合判定归纳树：如ID3和C4.5算法,探索性选择方法,d个属性有2d个可能的子集逐步向前选择由空属性集开始，选择原属性集中最好的属性，并将其添加入该集合，重复该步骤。初始属性集：A1,A2,A3,A4,A5,A6初始规约集：A1A1，A4A1，A4，A6规约后的属性集,探索性选择方法,逐步向后删除由整个属性集开始，每一步都删除掉尚在属性集中的最坏属性。初始属性集：A1,A2,A3,A4,A5,A6A1,A3,A4,A5,A6A1,A4,A5,A6A1，A4，A6规约后的属性集向前选择和向后删除相结合每一步选择一个最好属性，并删除一个最坏属性可以使用一个临界值来判定上述三种方法的结束条件,判定归纳树,Initialattributeset:A1,A2,A3,A4,A5,A6,Reducedattributeset:A1,A4,A6,（例图4）,45维度归约,有损压缩VS.无损压缩字符串压缩有广泛的理论基础和精妙的算法通常是无损压缩在解压缩前对字符串的操作非常有限音频/视频压缩通常是有损压缩，压缩精度可以递进选择有时可以在不解压整体数据的情况下，重构某个片断两种有损数据压缩的方法：小波变换和主要成分分析,45数值归约,通过选择替代的、较小的数据表示形式来减少数据量。有参方法、无参方法、回归模型有参方法：使用一个参数模型估计数据，最后只要存储参数即可。线性回归方法：Y=+X多元回归：线性回归的扩充、无参方法直方图聚类选样,直方图,一种流行的数据归约技术将某属性的数据划分为不相交的子集，或桶，桶中放置该值的出现频率,直方图,桶和属性值的划分规则等宽：每个桶的宽度区间是一个常数（如图4）等深：使得每个桶的频率粗略地为常数（即每个桶大致包含相同个数的临近数据样本）V-最优：V-最优直方图是具有最小方差的直方图,桶中数据两两间方差的和最小。（？）MaxDiff：考虑每对相邻值之间的差。桶的边界是具有个最大差的对，这里由用户指定。例如：（1，2，4，7，7，7，7，8，。），=5（1，2，4），（7，7，7，7，8，。）,、聚类,将数据集划分为聚类，然后通过聚类来表示数据集：高内聚、低偶合聚类质量描述：直径一个聚类中任意两个对象的最大距离。质心距离聚类质心到每个聚类对象的平均距离。如果数据可以组成各种不同的聚类，则该技术非常有效，反之如果数据界线模糊，则方法无效聚类示例：数据可以分层聚类，并被存储在多层索引树（B+树）中,986,3396,5411,8392,9544,9999,图2给定数据集的B+树的根,聚类的定义和算法都有很多选择，将在第八章介绍,0-9999之间共10000个元组，分成六个桶，每个桶的数据相同，约为10000/6个数据项。,选样,允许用数据的较小随机样本（子集）表示大的数据集对数据集D的样本选择：简单随机选择n个样本，不回放：由D的N个元组中抽取n个样本简单随机选择n个样本，回放：过程同上，只是元组被抽取后，将被回放，可能再次被抽取,Sampling,SRSWOR(simplerandomsamplewithoutreplacement),SRSWR,选样,聚类选样：D中元组被分入M个互不相交的聚类中，可在其中的m个聚类上进行简单随机选择（mM）P86分层选样：D被划分为互不相交的“层”，则可通过对每一层的简单随机选样得到D的分层选样,4.6离散化和概念分层生成,三种类型的属性值：名称型e.g.无序集合中的值序数e.g.有序集合中的值连续值e.g.实数离散化将连续属性的范围划分为区间有效的规约数据基于判定树的分类挖掘离散化的数值用于进一步分析,离散化和概念分层,离散化通过将属性域划分为区间，减少给定连续属性值的个数。区间的标号可以代替实际的数据值。概念分层通过使用高层的概念（比如：青年、中年、老年）来替代底层的属性值（比如：实际的年龄数据值）来规约数据,4.6.1数据数值的离散化和概念分层生成,1、分箱（binning）分箱技术递归的用于结果划分，可以产生概念分层。、直方图分析（histogram）直方图分析方法递归的应用于每一部分，可以自动产生多级概念分层。、聚类分析将数据划分成簇，每个簇形成同一个概念层上的一个节点，每个簇可再分成多个子簇，形成子节点。、基于熵的离散化：将在讨