数据挖掘概念与技术第三章

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2015/9/22,#,数据挖掘概念与设计,第三章 数据预处理,3.1,数据预处理,3.2,数据清理,3.3,数据集成,3.4,数据规约,3.5,数据变换与数据离散化,3.6,小结,第三章 数据预处理,3.3.1,为什么要对数据预处理,低质量的数据将导致低质量的挖掘结果,准确性,完整性,一致性,时效性,可信性,可,解释性,3.1,数据预处理,高质量数据,3.1.2,数据处理的主要任务,数据清理,数据,集成,数据归约,数据变换,3.1,数据预处理,现实世界的的数据一般是不完整的，有噪声的和不一致性的。数据清理试图填充缺失值，光滑噪声、,识别,离,群,点、纠正数据中的不一致。,3.2.1,缺失值,1,）,忽略元组,：缺少类标号时通常这么做。但是忽略的元组其他属性也不能用，即便是有用的。,2,）,人工填写,：该方法很费事费时，数据集很大、缺失值很多时可能行不通。,3,）,使用一个全局常量填充缺失值,：将缺失值的属性用同一个常量替换。（方法简单但不可靠）,4,）,使用属性的中心度量（均值、中位数）填写缺失值,：对于正常的（对称的）数据分布，可以使用均值；对于倾斜数据（非对称）应该使用中位数。,5,）,使用与给定元组同一类的所有样本的属性均值或中位数,：利用另外一个属性分类数据，计算缺失值的属性值该是多少（均值或中位数）。,6,）,使用最可能的值填充,：,利用回归、贝叶斯,形式化,方法,的,基于推理的工具或决策树归纳确定,。,3.2,数据清理,3.2.2,噪声数据,噪声,：被测量的变量的随机误差或方差。,1,）,分箱,：,排序后的数据按等,频（每个箱几个值）分,箱，,然后,：,用,箱均值光滑：箱中每个值都被替换为箱中的均值。,用,箱中位数光滑：箱中的每一个只都被替换为该箱的中位数。,用,箱边界光滑：给定箱中的最大和最小值同样被视为箱边界,，,箱,中每个值都被替换为最接近的边界值。,2,）,回归,：可以用一个函数拟合数据来光滑数据。,3,）,离,群,点分析,：通过如聚类来检测利群点。,3.2,数据清理,3.2.3,数据清理作为一个过程,数据清理的第一步是偏差,检测。导致偏差的因素很多，认为输入错误、有意错误、数据退化（过时数据）、编码不一致、设备错误、系统错误,。,如何,进行偏差检测？,使用任何关于数据性质的知识：元数据,（,主要是描述数据,属性,（,property,）的,信息,）,、数据的基本统计描述（均值、中位数、众数、方差、标准差等）、唯一性规则、连续性规则、空值规则。,3.2,数据清理,数据,挖掘经常需要数据集成,合并来自多个数据存储的数据,。,3.3.1,实体识别问题,模式,集成和对象匹配可能需要技巧，例如如何让计算机识别,customer_id,和另外一个数据库的,cust_number,是同一属性？,利用元数据，每个属性的元数据包括名字、含义、数据类型和属性的值的允许范围，以及处理空值的规则。这些元数据可以用来帮助避免模式集成的错误，还有助于变化,数据,3.3,数据集成,3.3.2,冗余和相关分析,一,个,属性如果,能由另一个或另一组属性“导出”，则这个属性可能是冗余的；属性或维命名的不一致也可能导致结果数据集的冗余,。,1.,标称数据的卡方相关检验,2.,数值数据的相关系数,3.,数值数据的协方差,3.3,数据集成,1.,标称数据的卡方相关检验,假设,A,有,c,个不同的值，,a,1,a,2,.a,c,.,B,有,r,个不同的值，,b,1,b,2,b,r,.,则,包含属性,A,和属性,B,的元组可以使用一个列联表来表示，其中,A,属性的,c,个不同值构成表的列，,B,属性的,r,个不同值构成表的行。,令,(A,i,B,j,),表示属性,A,取,a,i,而属性,B,取,b,j,的联合事件，即（,A=a,i,B=b,j,).,3.3,数据集成,在表中每一个可能的,(A,i,B,j,),联合事件都有一个单元。,卡方值,的公式是：,其中，,o,ij,表示观察到的（,A,i,B,j,),联合事件的频率（实际次数）,。而,e,ij,表示,(A,i,B,j,),事件的期望频率,，计算公式是：,其中，,n,是数据元组的个数。,卡方统计检验,假定属性,A,和属性,B,是互相独立的,，即这两个属性之间没有关联。基于显著性水平，自由度是,(r-1)*(c-1),。,如果假设被拒绝，则,A,和,B,统计相关,。,3.1,3.2,假设调查了,1500,个人，按性别分成男和女。每个人投票是否喜欢阅读小说。这样，就有了两个属性：,gender,和,preferred_reading.,观察到的每个可能的联合事件的次数在表,3.1,中,。,圆括号中的表示事件的期望次数,，按照公式,3.2,计算出来的。,可以注意到，,每一行中，期望次数的总和必须和这一行的观察次数的总和相等；每一列中，期望次数的和等于这一列的观察次数的和。,利用公式,3.1,，计算卡方值为：,对于,2,*,2,的表，自由度为,(2-1)*(2-1)=1.,在自由度为,1,时，卡方值为,10.828,则可以在,0.001,的显著性水平上拒绝值原假设。因为计算出的值大于这个值，所以能以更小的显著性水平,拒绝原假设,，即,性别和是否喜欢读小说之间存在强相关关系,。,2,数值数据的相关系数,3.3,数据集成,对于数值型属性，可以通过计算,相关系数（皮尔逊相关系数）,来估计两个属性,A,和,B,之间的相关性：,其中，,n,是元组的个数，,a,i,和,b,i,是元组,i,的属性,A,和属性,B,的值，,和,表示属性,A,和属性,B,的,均值,，,A,和,B,是属性,A,和属性,B,的,标准差,。,3.3,相关系数,r,AB,的值在,-1,到,+1,之间。如果,r,AB,0,，则称,A,和,B,正相关,。表示,A,的值随着,B,的值的增大而增大。值越大，相关性越强。因此，,一个很大的值意味着,A,（或,B),需要被作为冗余删除,。,如果,r,AB,=0,则,A,和,B,相互独立,，它们之间没有任何关系。如果值,0,则,A,和,B,负相关,，表示一个属性的值随着另一个值的降低而增大。,散点图,可以用来可视化属性之间的关联关系。,注意：,关联并不表示因果,。即如果,A,和,B,相关，但并不意味着,A,导致,B,或者,B,导致,A,。,例如，在分析一个人口统计数据库时，我们发现表示医院数目的属性和盗车数目相关。但这并不表示一个属性导致了另外一个。两个属性实际上都是因为人口数这第三个属性导致的。,3.,数值数据的协方差,3.3,数据集成,在概率理论和统计学中，,相关性,和,协方差,是,评价两个属性是否一起发生变化,的两种相似的测量。,考虑两个,数值型属性,A,和,B,n,个观察,(a,1,b,1,),(a,n,b,n,).,属性,A,和属性,B,的均值，即期望值为：,和,则属性,A,和,B,的,协方差,为：,如果利用公式,3.3,来计算,相关系数,r,A,B,则：,其中分母是属性,A,和,B,的标准差。可以看到，,对于一起发生变化的属性,A,和,B,，如果,A,大于,时，,B,也可能大于,。因此，,A,和,B,之间的协方差为正,。如果一个属性的值在均值以下时另一个倾向于在均值以上，则,协方差为负,。,如果,A,和,B,相互独立（没有关联），则协方差为,0,.,但,反过来并不成立,。即一些随机变量对的协方差值为,0,，但并不独立。只有在一些额外的假设（如数据满足多元正态分布）时协方差为,0,表明独立性。,考虑下表，这是一个观察到的,5,次,AllElectronics,和,Hightech,公式的股票价格。如果股票是被同一个公司的趋势影响，那么它们的价格是否一起涨落呢？,计算均值：,则协方差为：,协方差值为正，因此，我们可以说两个公司的股票是一起涨的,。,3.3.3,元祖重复,3.3,数据集成,除了检测属性间的冗余，,元组级别的冗余,也需要被检测。,不规范表的使用,（一般是为了避免连接提高性能）是另一种数据冗余的来源。在,不同的复制,之间常常产生不一致性。因为,不精确的数据输入或者更新了一部分而非全部的数据,。,例如，一个购买订单数据库包含购买者的姓名和地址属性，而非这个信息的主键信息。不一致性就可能产生，比如在购买订单数据库中同样的购买者姓名却是不同的地址。,3.3.4,数据值冲突的检测与处理,3.3,数据集成,数据集成,还包含,数据值冲突的检测和解析,。例如，对于同一个真实世界实体，不同来源的属性值可能不同。可能是因为表达、刻度或者编码的不同。,比如，体重属性在一个系统中可能以公制单位存放而在另一个中以,英制,单位存放。,学校之间交换信息的时候，每个学校有自己的课程设置和等级模式。一个大学可能采用一个季度系统，一个数据库系统中,3,门课程，等级从,A+,到,F,。另一个可能采用学期值，数据库中提供,2,门课程，等级从,1,到,10.,很难制定两所大学精确的课程,等级转换规则，交换信息很困难。,3.4.1,数据规约策略的概述,3.4.2,小波变换,3.4.3,主成分分析,3.4.4,属性子集选择,3.4.5,回归和对数线性模型：参数化数据规约,3.4.6,直方图,3.4.7,聚类,3.4.8,抽样,3.4.9,数据立方体聚集,3.4,数据规约,3.4.1,数据规约策略的概述,数据规约策略包括维归约，数量规约，数据压缩,1,）维归约：减少所考虑的随机变量或属性的个数。方法有,小波变换和主成分分析,，它们把原数据变换或投影到较小的空间。属性子集选择是一种维归约方法，其中不相关、弱相关或冗余的属性或维被检测和删除。,2,）数量归约：用替代的、较小的数据表示形式替换原数据。,3,）数据压缩：使用变换，以便得到原数据的归约或“压缩”表示。如果原数据能够从压缩后的数据重构，而不损失信息，该数据归约为 无损的，近似重构原数据称为有损的。,3.4,数据规约,（,1,）,离散小波变换（,DWT,）：一种线性信号处理技术，用于数据向量,X,时，将它变成不同的数值小波系数向量,X,。,（,2,）,主成分分析：（,PCA,）又称,K-L,方法，搜索,k,个最能代表数据的,n,维正交向量，其中,k=n,。,（,3,）,属性子集选择：通过删除不相关或冗余的属性（维）减少数据量。目标是找出最小属性集,，,使得,数据,类的概率分布尽可能地接近使用所有属性得到的原分布。另外，在缩小后的属性集上挖掘能够减少出现在发现模式上的属性数目，使得模式更易于理解。,3.4,数据规约,（,4,）回归和对数线性模型：参数化数据归约,回归和对数线性模型可以用来近似给定的数据。对数线性模型：近似离散的多维概率分布。给定,n,维元组的集合，我们把每个元组看做,n,维空间的点，对于离散属性集,，可使用,对数线性模型，基于维组合的一个较小子集，,估计多维,空间中每个点的概率。,（,5,）直方图,直方图使用分箱来近似数据分布，是一种流行的数据归约形式。（,6,）聚类,聚类技术把数据元组看做对象，将对象划分为群或簇，使得在一个簇中的对象相互,“相似”,，而与其他簇中的对象“相异”。通常，相似性基于距离函数。,（,7,）,抽样,抽样可以作为一种数据归约的技术使用，因为它允许用数据小得多的随机样本表示数据集。,例如,：,簇,抽样，,分层抽样,（,8,）数据立方体聚集,对数据仓库的多维数据结构建模,3.5.1,数据,变换,策略概述：,1,）光滑：去掉数据中的噪声。技术包括分箱、回归、聚类。,2,）属性构造（特征构造）：由给定的属性构造新的属性并添加到属性集中，以帮助数据挖掘。,3,）聚集：对,数据进行汇总,或聚集。,4,）规范化：把属性数据按比例缩放，使之落入一个特定的区间。,5,）离散化：数值属性（,eg,。年龄）的原始值用区间标签（,eg.0-10,11-20,）或概念标签（,youth,，,adult,，,senior,）替换。,6,）由标称数据产生概念分层：将某个属性