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

1、第三章 数据预处理3.1 数据预处理3.2 数据清理3.3 数据集成3.4 数据规约3.5 数据变换与数据离散化3.6小结3.3.1 为什么要对数据预处理 低质量的数据将导致低质量的挖掘结果 准确性 完整性 一致性 时效性 可信性 可解释性高质量数据3.1.2 数据处理的主要任务 数据清理 数据集成 数据归约 数据变换现实世界的的数据一般是不完整的，有噪声的和不一致性的。数据清现实世界的的数据一般是不完整的，有噪声的和不一致性的。数据清理试图填充缺失值，光滑噪声、理试图填充缺失值，光滑噪声、识别识别离离群群点、纠正数据中的不一致。点、纠正数据中的不一致。3.2.1 缺失值1）忽略元组：缺少类标

2、号时通常这么做。但是忽略的元组其他属性也不能用，即便是有用的。2）人工填写：该方法很费事费时，数据集很大、缺失值很多时可能行不通。3）使用一个全局常量填充缺失值：将缺失值的属性用同一个常量替换。（方法简单但不可靠）4）使用属性的中心度量（均值、中位数）填写缺失值：对于正常的（对称的）数据分布，可以使用均值；对于倾斜数据（非对称）应该使用中位数。5）使用与给定元组同一类的所有样本的属性均值或中位数： 利用另外一个属性分类数据，计算缺失值的属性值该是多少（均值或中位数）。6）使用最可能的值填充：利用回归、贝叶斯形式化方法的基于推理的工具或决策树归纳确定。3.2.2 噪声数据 噪声：被测量的变量的随

3、机误差或方差。1）分箱：排序后的数据按等频（每个箱几个值）分箱， 然后： 用箱均值光滑：箱中每个值都被替换为箱中的均值。 用箱中位数光滑：箱中的每一个只都被替换为该箱的中位数。 用箱边界光滑：给定箱中的最大和最小值同样被视为箱边界， 箱中每个值都被替换为最接近的边界值。2）回归：可以用一个函数拟合数据来光滑数据。3）离群点分析：通过如聚类来检测利群点。3.2.3 数据清理作为一个过程数据清理的第一步是偏差检测。导致偏差的因素很多，认为输入错误、有意错误、数据退化（过时数据）、编码不一致、设备错误、系统错误。如何进行偏差检测？ 使用任何关于数据性质的知识： 元数据（主要是描述数据属性（prope

4、rty）的信息）、数据的基本统计描述（均值、中位数、众数、方差、标准差等）、唯一性规则、连续性规则、空值规则。 数据挖掘经常需要数据集成合并来自多个数据存储的数据。3.3.1 实体识别问题 模式集成和对象匹配可能需要技巧，例如如何让计算机识别customer_id和另外一个数据库的cust_number是同一属性？ 利用元数据，每个属性的元数据包括名字、含义、数据类型和属性的值的允许范围，以及处理空值的规则。这些元数据可以用来帮助避免模式集成的错误，还有助于变化数据3.3.2 冗余和相关分析 一个属性如果能由另一个或另一组属性“导出”，则这个属性可能是冗余的；属性或维命名的不一致也可能导致结果

5、数据集的冗余。1.标称数据的卡方相关检验2.数值数据的相关系数3.数值数据的协方差1.标称数据的卡方相关检验 假设A有c个不同的值，a1, a2,.ac. B有r个不同的值，b1,b2,br. 则包含属性A和属性B的元组可以使用一个列联表来表示，其中A属性的c个不同值构成表的列，B属性的r个不同值构成表的行。令(Ai, Bj)表示属性A取ai而属性B取bj的联合事件，即（A=ai, B=bj).在表中每一个可能的(Ai, Bj)联合事件都有一个单元。卡方值的公式是：其中，oij表示观察到的（Ai, Bj)联合事件的频率（实际次数）。而eij表示(Ai,Bj)事件的期望频率，计算公式是：其中，n

6、是数据元组的个数。卡方统计检验假定属性A和属性B是互相独立的，即这两个属性之间没有关联。基于显著性水平，自由度是(r-1)*(c-1)。如果假设被拒绝，则A和B统计相关。3.13.2假设调查了1500个人，按性别分成男和女。每个人投票是否喜欢阅读小说。这样，就有了两个属性：gender和preferred_reading.观察到的每个可能的联合事件的次数在表3.1中。圆括号中的表示事件的期望次数，按照公式3.2计算出来的。可以注意到，每一行中，期望次数的总和必须和这一行的观察次数的总和相等；每一列中，期望次数的和等于这一列的观察次数的和。利用公式3.1，计算卡方值为：对于2*2的表，自由度为(

7、2-1)*(2-1)=1. 在自由度为1时，卡方值为10.828则可以在0.001的显著性水平上拒绝值原假设。因为计算出的值大于这个值，所以能以更小的显著性水平拒绝原假设，即性别和是否喜欢读小说之间存在强相关关系。2 数值数据的相关系数3.3相关系数rAB的值在-1到+1之间。如果rAB 0，则称A和B正相关正相关。表示A的值随着B的值的增大而增大。值越大，相关性越强。因此，一个很大的值意味着A（或B)需要被作为冗余删除。如果rAB =0,则A和B相互独立相互独立，它们之间没有任何关系。如果值0,则A和B负相关负相关，表示一个属性的值随着另一个值的降低而增大。散点图可以用来可视化属性之间的关联

8、关系。注意：关联并不表示因果。即如果A和B相关，但并不意味着A导致B或者B导致A。例如，在分析一个人口统计数据库时，我们发现表示医院数目的属性和盗车数目相关。但这并不表示一个属性导致了另外一个。两个属性实际上都是因为人口数这第三个属性导致的。3. 数值数据的协方差在概率理论和统计学中，相关性相关性和协方差协方差是评价两个属性是否一起发生变化的两种相似的测量。考虑两个数值型属性A和B, n个观察(a1,b1),(an,bn). 属性A和属性B的均值，即期望值为：和则属性A和B的协方差协方差为：如果利用公式3.3来计算相关系数相关系数rA,B,则：其中分母是属性A和B的标准差。可以看到，考虑下表，

9、这是一个观察到的5次AllElectronics和Hightech公式的股票价格。如果股票是被同一个公司的趋势影响，那么它们的价格是否一起涨落呢？计算均值：则协方差为：协方差值为正，因此，我们可以说两个公司的股票是一起涨的。3.3.3 元祖重复除了检测属性间的冗余，元组级别的冗余元组级别的冗余也需要被检测。不规范表的使用（一般是为了避免连接提高性能）是另一种数据冗余的来源。在不同的复制之间常常产生不一致性。因为不精确的数据输入或者更新了一部分而非全部的数据。例如，一个购买订单数据库包含购买者的姓名和地址属性，而非这个信息的主键信息。不一致性就可能产生，比如在购买订单数据库中同样的购买者姓名却是

10、不同的地址。3.3.4 数据值冲突的检测与处理数据集成数据集成还包含数据值冲突的检测和解析。例如，对于同一个真实世界实体，不同来源的属性值可能不同。可能是因为表达、刻度或者编码的不同。比如，体重属性在一个系统中可能以公制单位存放而在另一个中以英制单位存放。学校之间交换信息的时候，每个学校有自己的课程设置和等级模式。一个大学可能采用一个季度系统，一个数据库系统中3门课程，等级从A+到F。另一个可能采用学期值，数据库中提供2门课程，等级从1到10. 很难制定两所大学精确的课程等级转换规则，交换信息很困难。3.4.1 数据规约策略的概述3.4.2 小波变换3.4.3 主成分分析3.4.4 属性子集选

11、择3.4.5 回归和对数线性模型：参数化数据规约3.4.6 直方图3.4.7 聚类3.4.8 抽样3.4.9 数据立方体聚集3.4.1 数据规约策略的概述 数据规约策略包括维归约，数量规约，数据压缩 1）维归约：减少所考虑的随机变量或属性的个数。方法有 小波变换和主成分分析，它们把原数据变换或投影到较小的空间。属性子集选择是一种维归约方法，其中不相关、弱相关或冗余的属性或维被检测和删除。 2）数量归约：用替代的、较小的数据表示形式替换原数据。 3）数据压缩：使用变换，以便得到原数据的归约或“压缩”表示。如果原数据能够从压缩后的数据重构，而不损失信息，该数据归约为 无损的，近似重构原数据称为有损

12、的。（1）离散小波变换（DWT）：一种线性信号处理技术，用于数据向量X时，将它变成不同的数值小波系数向量X。（2）主成分分析：（PCA）又称K-L方法，搜索k个最能代表数据的n维正交向量，其中k=n。（3）属性子集选择：通过删除不相关或冗余的属性（维）减少数据量。目标是找出最小属性集，使得数据类的概率分布尽可能地接近使用所有属性得到的原分布。另外，在缩小后的属性集上挖掘能够减少出现在发现模式上的属性数目，使得模式更易于理解。（4）回归和对数线性模型：参数化数据归约 回归和对数线性模型可以用来近似给定的数据。 对数线性模型：近似离散的多维概率分布。给定n维元组的集合，我们把每个元组看做n维空间的

13、点，对于离散属性集，可使用对数线性模型，基于维组合的一个较小子集，估计多维空间中每个点的概率。（5）直方图 直方图使用分箱来近似数据分布，是一种流行的数据归约形式。（6）聚类 聚类技术把数据元组看做对象，将对象划分为群或簇，使得在一个簇中的对象相互“相似”，而与其他簇中的对象“相异”。通常，相似性基于距离函数。（7）抽样 抽样可以作为一种数据归约的技术使用，因为它允许用数据小得多的随机样本表示数据集。例如：簇抽样，分层抽样（8）数据立方体聚集 对数据仓库的多维数据结构建模3.5.1 数据变换策略概述： 1）光滑：去掉数据中的噪声。技术包括分箱、回归、聚类。 2）属性构造（特征构造）：由给定的属

14、性构造新的属性并添加到属性集中，以帮助数据挖掘。 3）聚集：对数据进行汇总或聚集。 4）规范化：把属性数据按比例缩放，使之落入一个特定的区间。 5）离散化：数值属性（eg。年龄）的原始值用区间标签（eg. 0-10,11-20）或概念标签（youth，adult，senior）替换。 6）由标称数据产生概念分层：将某个属性（eg. street）泛化到较高的概念层（city）。3.5.2 通过规范化变换数据1.最小-最大规范化：对原始数据进行线性变换。令minA和maxA表示属性A的最小值和最大值，最小最大值标准化将值vi映射为vi(范围是new_minA, new_maxA:最小最大值标准化

15、保留了原有数据值的关系。如果后来的输入的标准化的数据落在了原有数据区间的外面，将会发生过界的错误。假定收入属性的最小值和最大值分别是$12,000和$98,000. 将收入属性映射到范围0.0, 1.0上。则一个值为$73,600的收入标准化为：3.5.2 通过规范化变换数据2. Z-分数标准化假定income属性的均值和标准差是$54,000和$16,000。使用z-分数标准化，则$73,600被转换为：3.5.3 通过分箱离散化 分箱并不使用类信息，因此是一种非监督的离散化技术，对用户制定的箱个数很敏感，也容易受离群点的影响。3.5.4 通过直方图分析离散化 直方图分析也是一种非监督离散化

16、技术，因为它不使用类信息。3.5.5 通过聚类、决策树和相关分析离散化 聚类将数学的值划分成簇或；离散化的决策树方法是监督的，它们使用了类标号（分类）。3.5.6 标称数据的概念分层产生标称属性具有有穷多个不同值，值之间无序。如地理位置，商品类型。 四中标称数据概念分层产生的方法： 1）由用户或专家在模式级显示地说明属性的部分序。（标称属性或维的概念分层涉及一组属性，由用户或专家说明属性的偏序或全序，然后很容易定义概念分层。） 2）通过显式数据分组说明分层结构的一部分。对于小部分数据，显式说明分组。 3）说明属性集但不说明它们的偏序：用户可以说明一个属性集形成概念分层，但并不显式说明它们的偏序

17、，系统可以试图自动产生属性的序，构造有意义的概念分层。 4）只说明部分属性集 数据质量包括精确性、完整性、一致性、时效性、可信性和可解释性。质量的评估基于对数据的预期使用。 即使目前存在大量的数据预处理技术，这仍然是一个研究的活跃领域，因为大量的不一致和脏数据的存在以及问题的复杂度的原因。D. P. Ballou and G. K. Tayi. Enhancing data quality in data warehouse environments. Comm. of ACM, 42:73-78, 1999A. Bruce, D. Donoho, and H.-Y. Gao. Wavelet

18、 analysis. IEEE Spectrum, Oct 1996T. Dasu and T. Johnson. Exploratory Data Mining and Data Cleaning. John Wiley, 2003J. Devore and R. Peck. Statistics: The Exploration and Analysis of Data. Duxbury Press, 1997.H. Galhardas, D. Florescu, D. Shasha, E. Simon, and C.-A. Saita. Declarative data cleaning: Language, model, and algorithms. VLDB01M. Hua and J. Pei. Cleaning disguised missing data: A heuristic approach. KDD07H. V. Jagadish, et al., Special Issue on Data Reduction Techniques. Bulletin of the Technical Committee on Da