数据挖掘-CHAPTER2-数据预处理

1、1第第2章章: 数据预处理数据预处理n为什么预处理数据为什么预处理数据?n数据清理数据清理 n数据集成数据集成n数据归约数据归约n离散化和概念分层产生离散化和概念分层产生n小结小结2为什么数据预处理为什么数据预处理?n现实世界中的数据是脏的现实世界中的数据是脏的n不完全不完全: 缺少属性值缺少属性值, 缺少某些有趣的属性缺少某些有趣的属性, 或仅包含聚集数据或仅包含聚集数据n例例, occupation=“”n噪音噪音: 包含错误或孤立点包含错误或孤立点n例例, Salary=“-10”n不一致不一致: 编码或名字存在差异编码或名字存在差异n例例, Age=“42” Birthday=“03/

2、07/2010”n例例, 以前的等级以前的等级 “1,2,3”, 现在的等级现在的等级 “A, B, C”n例例, 重复记录间的差异重复记录间的差异3数据为什么脏数据为什么脏?n不完全数据源于不完全数据源于n数据收集时未包含数据收集时未包含n数据收集和数据分析时的不同考虑数据收集和数据分析时的不同考虑.n人人/硬件硬件/软件问题软件问题n噪音数据源于噪音数据源于n收集收集n录入录入n传输传输n不一致数据源于不一致数据源于n不同的数据源不同的数据源n违反函数依赖违反函数依赖4为什么数据预处理是重要的为什么数据预处理是重要的?n没有高质量的数据没有高质量的数据, 就没有高质量的数据挖掘结果就没有高

3、质量的数据挖掘结果!n高质量的决策必然依赖高质量的数据高质量的决策必然依赖高质量的数据n例如例如, 重复或遗漏的数据可能导致不正确或误重复或遗漏的数据可能导致不正确或误导的统计导的统计.n数据仓库需要高质量数据的一致集成数据仓库需要高质量数据的一致集成5数据质量：一个多维视角数据质量：一个多维视角n一种广泛接受的多角度一种广泛接受的多角度:n正确性正确性(Accuracy)n完全性完全性(Completeness)n一致性一致性(Consistency)n合时合时(Timeliness)：timely update? n可信性可信性(Believability)n可解释性可解释性(Interp

4、retability)n可存取性可存取性(Accessibility)6数据预处理的主要任务数据预处理的主要任务n数据清理数据清理n填充缺失值填充缺失值, 识别识别/去除离群点去除离群点, 光滑噪音光滑噪音, 并纠正数据中的不并纠正数据中的不一致一致n数据集成数据集成n多个数据库多个数据库, 数据立方体数据立方体, 或文件的集成或文件的集成n数据变换数据变换n规范化和聚集规范化和聚集n数据归约数据归约n得到数据的归约表示得到数据的归约表示, 它小得多它小得多, 但产生相同或类似的分析结但产生相同或类似的分析结果：维度规约、数值规约、数据压缩果：维度规约、数值规约、数据压缩n数据离散化和概念分层

5、数据离散化和概念分层7数据预处理的形式数据预处理的形式 8第第2章章: 数据预处理数据预处理n为什么预处理数据为什么预处理数据?n数据清理数据清理 n数据集成数据集成n数据归约数据归约n离散化和概念分层产生离散化和概念分层产生n小结小结9数据清理数据清理 Data Cleaningn现实世界的数据是现实世界的数据是脏脏的：很多潜在的不正确的数据，比如，的：很多潜在的不正确的数据，比如，仪器故障，人为或计算机错误，许多传输错误仪器故障，人为或计算机错误，许多传输错误nincomplete:缺少属性值缺少属性值, 缺少某些有趣的属性缺少某些有趣的属性, 或仅包含聚集数据或仅包含聚集数据ne.g.,

6、 职业职业=“ ” (missing data)nnoisy:包含错误或孤立点包含错误或孤立点ne.g., Salary=“10” (an error)ninconsistent:编码或名字存在差异编码或名字存在差异, e.g.,nAge=“42”, Birthday=“03/07/2010”n以前的等级以前的等级 “1, 2, 3”, 现在等级现在等级 “A, B, C”n重复记录间的差异重复记录间的差异n有意的有意的(e.g.,变相丢失的数据变相丢失的数据)nJan. 1 as everyones birthday?10如何处理缺失数据如何处理缺失数据?n忽略元组忽略元组: 缺少类别标签时

7、常用缺少类别标签时常用(假定涉及分类假定涉及分类不是很有不是很有效，当每个属性的缺失百分比变化大时效，当每个属性的缺失百分比变化大时n手工填写缺失数据手工填写缺失数据: 乏味乏味+费时费时+不可行不可行 ?n自动填充自动填充n一个全局常量一个全局常量 : e.g., “unknown”, a new class?! n使用属性均值使用属性均值n与目标元组同一类的所有样本的属性均值与目标元组同一类的所有样本的属性均值: 更巧妙更巧妙n最可能的值最可能的值: 基于推理的方法，如基于推理的方法，如贝叶斯公式或决策树贝叶斯公式或决策树11噪音数据噪音数据Noisy DatanNoise: 被测量的变量

8、的随机误差或方差被测量的变量的随机误差或方差n不正确的属性值可能由于不正确的属性值可能由于n错误的数据收集工具错误的数据收集工具n数据录入问题数据录入问题 data entry problemsn数据传输问题数据传输问题data transmission problemsn技术限制技术限制 technology limitationn不一致的命名惯例不一致的命名惯例 inconsistency in naming convention n其他需要数据清理的问题其他需要数据清理的问题n重复记录重复记录 duplicate recordsn数据不完整数据不完整 incomplete datan不一

9、致的数据不一致的数据 inconsistent data12如何处理噪音数据如何处理噪音数据?n分箱分箱Binning method:n排序数据，分布到等频排序数据，分布到等频/等宽的箱等宽的箱/桶中桶中n箱均值光滑、箱中位数光滑、箱边界光滑箱均值光滑、箱中位数光滑、箱边界光滑, etc.n聚类聚类Clusteringn检测和去除检测和去除 离群点离群点/孤立点孤立点 outliersn计算机和人工检查相结合计算机和人工检查相结合n人工检查可疑值人工检查可疑值 (e.g., deal with possible outliers)n回归回归 Regressionn回归函数拟合数据回归函数拟合数

10、据13分箱：简单的离散化方法分箱：简单的离散化方法n等宽度等宽度Equal-width (distance) 剖分剖分:n分成大小相等的分成大小相等的n个区间个区间: 均匀网格均匀网格 uniform gridn若若A和和B是是 属性的最低和最高取值属性的最低和最高取值, 区间宽度为区间宽度为: W = (B A)/N.n孤立点可能占据重要影响孤立点可能占据重要影响 may dominate presentationn倾斜的数据处理不好倾斜的数据处理不好.n等频剖分等频剖分 (frequency) /等深等深equi-depth :n分成分成n个区间个区间, 每一个含近似相同数目的样本每一个含

11、近似相同数目的样本nGood data scalingn类别属性可能会非常棘手类别属性可能会非常棘手.14Binning Methods for Data Smoothing* Sorted data for price (in dollars): 4, 8, 9, 15, 21, 21, 24, 25, 26, 28, 29, 34* Partition into (equi-depth) bins: - Bin 1: 4, 8, 9, 15 - Bin 2: 21, 21, 24, 25 - Bin 3: 26, 28, 29, 34* Smoothing by bin means: -

12、Bin 1: 9, 9, 9, 9 - Bin 2: 23, 23, 23, 23 - Bin 3: 29, 29, 29, 29* Smoothing by bin boundaries: - Bin 1: 4, 4, 4, 15 - Bin 2: 21, 21, 25, 25 - Bin 3: 26, 26, 26, 3415聚类分析聚类分析16Regressionxyy = x + 1X1Y1Y117数据清理作为一个过程数据清理作为一个过程n数据偏差检测数据偏差检测 Data discrepancy detectionn使用元数据使用元数据(数据性质的知识数据性质的知识)(e.g.,领域

13、领域, 长度范围长度范围,从属从属, 分布分布)n检查字段过载检查字段过载 field overloading n检查唯一性规则检查唯一性规则, 连续性规则连续性规则,空值规则空值规则n使用商业工具使用商业工具n数据清洗数据清洗Data scrubbing: 使用简单的领域知识使用简单的领域知识(e.g., 邮编邮编, 拼写检拼写检查查) 检查并纠正错误检查并纠正错误n数据审计数据审计 Data auditing: 通过分析数据发现规则和联系发现违规通过分析数据发现规则和联系发现违规者者(孤立点孤立点)n数据迁移和集成数据迁移和集成n数据迁移工具数据迁移工具Data migration too

14、ls:允许指定转换允许指定转换n提取提取/变换变换/装入工具装入工具ETL (Extraction/Transformation/Loading) tools: 允许用户通过图形用户界面指定变换允许用户通过图形用户界面指定变换n整合两个过程整合两个过程n两个过程迭代和交互执行两个过程迭代和交互执行(e.g., Potters Wheels)18第第2章章: 数据预处理数据预处理n为什么预处理数据为什么预处理数据?n数据清理数据清理 n数据集成数据集成n数据归约数据归约n离散化和概念分层产生离散化和概念分层产生n小结小结19数据集成数据集成n数据集成数据集成 Data integration:

15、n合并多个数据源中的数据，存在一个一致的数据存储中合并多个数据源中的数据，存在一个一致的数据存储中n涉及涉及3个主要问题：模式集成、冗余数据、冲突数据值个主要问题：模式集成、冗余数据、冲突数据值n模式集成模式集成 Schema integration n例如例如., A.cust-id ？ B.cust-#n实体识别问题实体识别问题 Entity identification problem: n多个数据源的真实世界的实体的识别多个数据源的真实世界的实体的识别, e.g., Bill Clinton = William Clintonn集成不同来源的元数据集成不同来源的元数据n冲突数据值的检测

16、和解决冲突数据值的检测和解决n对真实世界的实体，其不同来源的属性值可能不同对真实世界的实体，其不同来源的属性值可能不同n原因原因:不同的表示不同的表示,不同尺度不同尺度,公制公制 vs. 英制英制20数据集成中冗余数据处理数据集成中冗余数据处理n冗余数据冗余数据Redundant data （集成多个数据库时出（集成多个数据库时出现）现）n目标识别：同一个属性在不同的数据库中有不同的名称目标识别：同一个属性在不同的数据库中有不同的名称n衍生数据：一个属性值可由其他表的属性推导出衍生数据：一个属性值可由其他表的属性推导出, e.g.,年收入年收入n相关分析相关分析 correlation ana

17、lysis /协方差分析协方差分析covariance analysisn可用于检测冗余数据可用于检测冗余数据n小心的集成多个来源的数据可以帮助降低和避免结果数据小心的集成多个来源的数据可以帮助降低和避免结果数据集中的冗余和不一致，提高数据挖掘的速度和质量集中的冗余和不一致，提高数据挖掘的速度和质量21相关分析相关分析 (数值数据数值数据)nCorrelation coefficient (also called Pearsons product moment coefficient)n相关系数（皮尔逊相关系数）相关系数（皮尔逊相关系数）n元组个数元组个数, 和和 属性属性A和和B上的平均值上

18、的平均值, A and B分别为各自标准差，分别为各自标准差， (aibi) is the AB叉积叉积 cross-product之和之和.nIf rA,B 0, A and B 正相关正相关 (As values increase as Bs). 值越大相关程度值越大相关程度越高越高.nrA,B = 0: 不相关不相关; rAB 0, 则则A 和和B 同时倾向于大于期望值同时倾向于大于期望值.n负covariance: If CovA,B 0.26相关分析相关分析 (名义数据名义数据Nominal Data)n2 (chi-square) test 开方检验开方检验nij是是(ai,bj)

19、的观测频度（实际计数）的观测频度（实际计数）neij是是(ai,bj)的期望频度的期望频度nN数据元组的个数数据元组的个数属属A性性a1a2i acb1Bb2j br(A=ai,B=bj)rjijijijciee1212)(NbBcountaAcountejiij)(*)(n2 值越大值越大,相关的可能越大相关的可能越大n对对 2 值贡献最大的项，其值贡献最大的项，其实际值与期望值相差最大的实际值与期望值相差最大的相相n相关不意味着因果关系相关不意味着因果关系27Chi-Square 卡方值计算卡方值计算: 例子例子n2 (chi-square) 计算计算(括号中的值为期望计值，由两个类别的分

20、布数据计括号中的值为期望计值，由两个类别的分布数据计算得到算得到)n结果表明结果表明like_fiction 和和play_chess 关联关联93.507840)8401000(360)360200(210)21050(90)90250(22222Play chessNot play chessSum (row)看小说看小说250(90)200(360)450不看小说不看小说50(210)1000(840)1050Sum(col.)30012001500901500300*450)(*)(11Ncountcounte下棋看小说28数据变换数据变换Data Transformationn光滑光

21、滑: 去掉噪音，技术：分箱、回归、聚类去掉噪音，技术：分箱、回归、聚类n聚集聚集Aggregation:汇总汇总, 数据立方体构造数据立方体构造n数据泛化数据泛化Generalization:概念分层概念分层n规范化规范化Normalization:按比例缩放到一个具体区间按比例缩放到一个具体区间n最小最小-最大规范化最大规范化nz-score 规范化规范化n小数定标规范化小数定标规范化n属性属性Attribute/特征特征feature 构造构造n从给定的属性构造新属性从给定的属性构造新属性n机器学习中称为：特征构造机器学习中称为：特征构造数据规约29规范化数据的方法规范化数据的方法n最小最

22、小-最大规范化最大规范化 min-max normalizationn新数据可能新数据可能“越界越界”nz-score normalizationnnormalization by decimal scalingn移动属性移动属性A的小数点位置的小数点位置(移动位数依赖于属性移动位数依赖于属性A的最大值的最大值)AAAAAAminnewminnewmaxnewminmaxminvv_)_(A标准差均值Avvjvv10J为使得 Max(| |)最后的集合: A1, A4, A6维度规约维度规约-决策树规约决策树规约3939维度规约维度规约-属性属性/特征产生特征产生nFeature Genera

23、tion 产生新的属性，其可以比产生新的属性，其可以比原始原始属性属性更有效地更有效地表示数据的重要信息。表示数据的重要信息。n三个一般方法三个一般方法:n属性提取属性提取 Attribute extractionn特定领域的特定领域的n映射数据到新空间映射数据到新空间nE.g., 傅立叶变换傅立叶变换, wavelet transformation, 流形方法流形方法( manifold approaches)n属性构造属性构造n组合特征组合特征n数据离散化数据离散化 Data discretization4040 x2x1e主成分分析主成分分析 (PCA)nprincipal compon

24、ent analysis，K-L变换变换n找到一个投影，其能表示数据的最大变化找到一个投影，其能表示数据的最大变化n原始数据投影到一个更小的空间中，导致维度减少原始数据投影到一个更小的空间中，导致维度减少. n发现的协方差矩阵的特征向量，用这些特征向量定义新发现的协方差矩阵的特征向量，用这些特征向量定义新的空间的空间4141n给定给定 p维维空间中的空间中的N个点个点, 找到找到 k p 个正交向量个正交向量 (principal components) 可以很好表示原始数据的可以很好表示原始数据的 n归范化输入数据归范化输入数据: 每个属性值位于相同的区间内每个属性值位于相同的区间内n计算计

25、算 k 个标准正交向量个标准正交向量, i.e., principal componentsn每个输入的点是这每个输入的点是这k 个主成分的线性组合个主成分的线性组合nThe principal components are sorted in order of decreasing “significance” or strengthnSince the components are sorted, the size of the data can be reduced by eliminating the weak components(i.e., using the strongest

26、principal components, it is possible to reconstruct a good approximation of the original data)nWorks for numeric data only主成分分析主成分分析 (Steps)42X1X2Y1Y2Principal Component Analysis43数值规约数值规约n选择替代的、选择替代的、“较小的较小的”数据表示形式数据表示形式n参数方法参数方法n假设数据适合某个模型，估计模型参数，仅存储的参假设数据适合某个模型，估计模型参数，仅存储的参数，并丢弃数据（孤立点除外）数，并丢弃数据（孤

27、立点除外）n对数线性模型对数线性模型:n基于一个较小的维组合的子集来估计基于一个较小的维组合的子集来估计 离散属性的离散属性的多维空间中每个点的概率多维空间中每个点的概率n非参数方法非参数方法n不假定模型不假定模型nhistograms, clustering, sampling 44回归和对数线性模型回归和对数线性模型n线性回归线性回归: 数据拟合到一条直线上数据拟合到一条直线上n通常使用最小二乘法拟合通常使用最小二乘法拟合n多元线性回归多元线性回归n允许响应变量允许响应变量Y表示为多个预测变量的函数表示为多个预测变量的函数n对数线性模型对数线性模型: n近似离散的多维概率分布近似离散的多维

28、概率分布4545回归分析回归分析n研究因变量因变量/响应变量响应变量Y(dependent variable/response variable) 对个或多个自变量自变量/解释变量解释变量(independent variable / explanatory variable)的相依关系的方法的统称n参数需要估计以最好的拟合给定参数需要估计以最好的拟合给定的数据的数据n绝大多数情况绝大多数情况“最好的拟合最好的拟合”是由是由最小二乘法最小二乘法(least squares method)实实现现, 其他的方法也有其他的方法也有n用于预测（包括时用于预测（包括时间序列数据的预间序列数据的预测），

29、推断，假设测），推断，假设检验和因果关系的检验和因果关系的建模建模yxy = x + 1X1Y1Y146线性回归线性回归-用于预测用于预测Y: -diameter at breast height(DBH) X: - Age0123456789101112Y?1.01.01.56.09.010.5 1116.5 9.58.012.5 12.5X3411121528455257758188939747线性回归线性回归(cont.)nGiven x, construct the linear regression model for y against x as:nLeast squares es

30、timation of y given variable x is:48多元线性回归多元线性回归n响应变量响应变量: w，自变量，自变量: A1,A2,Ak.n“5” 样本数目样本数目) 1 (21kAAAw49直方图直方图Histogramsn把数据划分成不相交的子把数据划分成不相交的子集或桶集或桶n一维时可用动态规划优化一维时可用动态规划优化构建构建n涉及量化问题涉及量化问题051015202530354010000200003000040000500006000070000800009000010000050聚类聚类Clusteringn将对象划分成集将对象划分成集/簇簇, 用簇的表示替

31、换实际数据用簇的表示替换实际数据n技术的有效性依赖于数据的质量技术的有效性依赖于数据的质量n使用层次聚类，并多维索引树结构存放使用层次聚类，并多维索引树结构存放n非常多的聚类算法和定义非常多的聚类算法和定义51抽样抽样Samplingn抽样抽样: 获得一个小的样本集获得一个小的样本集s来表示整个数据集来表示整个数据集 Nn允许一个挖掘算法运行复杂度子线性于样本大小允许一个挖掘算法运行复杂度子线性于样本大小n关键原则关键原则:选择一个有代表性的数据子集选择一个有代表性的数据子集n数据偏斜时简单随机抽样的性能很差数据偏斜时简单随机抽样的性能很差n发展适应抽样方法：分层抽样发展适应抽样方法：分层抽样

32、 nNote: Sampling may not reduce database I/Os (page at a time)52抽样类型抽样类型 Types of Samplingn简单随机抽样 Simple random samplingn相同的概率选择任何特定项目相同的概率选择任何特定项目n无放回抽样 Sampling without replacementnOnce an object is selected, it is removed from the populationn放回抽样Sampling with replacementn一个被抽中的目标不从总体中去除一个被抽中的目标不从

33、总体中去除n分层抽样 Stratified sampling: n把数据分成不相交部分把数据分成不相交部分(层层), 然后从每个层抽样然后从每个层抽样(按比例按比例/大大约相同比例的数据约相同比例的数据) n偏斜数据偏斜数据53Sampling: With or without ReplacementSRSWOR(simple random sample without replacement)SRSWRRaw Data54Sampling: Cluster or Stratified SamplingRaw Data Cluster/Stratified Sample55第第2章章: 数据预

34、处理数据预处理n为什么预处理数据为什么预处理数据?n数据清理数据清理 n数据集成数据集成n数据归约数据归约n离散化和概念分层产生离散化和概念分层产生n小结小结56离散化离散化 Discretization和概念分成和概念分成n三种类型属性三种类型属性:n名义名义 values from an unordered set， color, professionn顺序数顺序数 values from an ordered set , e.g., military or academic rank n连续连续 real numbersn离散化离散化 Discretization: 把连续属性的区域分成

35、区间把连续属性的区域分成区间n区间标号可以代替实际数据值区间标号可以代替实际数据值 n利用离散化减少数据量利用离散化减少数据量n有监督有监督 vs. 无监督：是否使用类的信息无监督：是否使用类的信息n某个属性上可以递归离散化某个属性上可以递归离散化n分裂分裂 Split (top-down) vs. 合并合并merge (bottom-up)n自顶向下：由一个自顶向下：由一个/几个点开始递归划分整个属性区间几个点开始递归划分整个属性区间n递归离散化属性，产生属性值分层递归离散化属性，产生属性值分层/多分辨率划分：多分辨率划分：概念分层概念分层57数值数据离散化数值数据离散化/概念分层概念分层n

36、分箱分箱 Binning(Top-down split, unsupervised)n直方图（直方图（Top-down split, unsupervised）n聚类聚类 (unsupervised, top-down split or bottom-up merge)n基于基于 2 分析的区间合并分析的区间合并(unsupervised, bottom-up merge)n基于熵基于熵 Entropy-based discretizationn根据自然划分根据自然划分58不用类别不用类别(Binning vs. Clustering) DataEqual interval width (bi

37、nning)Equal frequency (binning)K-means clustering leads to better results59基于熵基于熵Entropy的离散化的离散化60 Chi-merge离散化离散化nChi-merge: 2-based discretizationn有监督有监督: use class informationn自低向上自低向上: find the best neighboring intervals (具有相似的类具有相似的类别分布别分布, i.e., low 2 values) to mergen递归地合并递归地合并, until a prede

38、fined stopping condition61由自然划分离散化由自然划分离散化n3-4-5 规则规则n如果最高有效位包含如果最高有效位包含 3, 6, 7 or 9 个不同的值个不同的值, partition the range into 3 个等宽区间（个等宽区间（7：2-3-2分成分成3个区间）个区间）n2, 4, or 8 不同的值不同的值, 区域分成区域分成 4 个等宽区间个等宽区间n1, 5, or 10 不同的值不同的值, 区域分成区域分成5 个等宽区间个等宽区间n类似地，逐层使用此规则类似地，逐层使用此规则62分类数据的概念分层分类数据的概念分层 Categorical D

39、atan用户用户/专家在模式级显式地指定属性的偏序专家在模式级显式地指定属性的偏序nstreetcitystatecountryn通过显式数据分组说明分层通过显式数据分组说明分层n厄本，香槟，芝加哥厄本，香槟，芝加哥Illinoisn只说明属性集只说明属性集 n系统自动产生属性偏序，根据系统自动产生属性偏序，根据 每个属性下不同值的数据每个属性下不同值的数据n启发式规则：相比低层，高层概念的属性通常有较少取值启发式规则：相比低层，高层概念的属性通常有较少取值nE.g., street city state countryn只说明部分属性值只说明部分属性值63自动产生概念分层自动产生概念分层nS

40、ome concept hierarchies can be automatically generated based on the analysis of the number of distinct values per attribute in the given data set n含不同值最多的属性放在层次的最低层含不同值最多的属性放在层次的最低层nNote: Exceptionweekday, month, quarter, yearcountryprovince_or_ statecitystreet15 distinct values65 distinct values356

41、7 distinct values674,339 distinct values64SummarynData preparation is a big issue for both warehousing and miningnData preparation includesnData cleaning and data integrationnData reduction and feature selectionnDiscretizationnA lot a methods have been developed but still an active area of researchD

42、ata Reduction, Transformation, IntegrationnData QualitynMajor Tasks in Data PreprocessingnData Cleaning and Data IntegrationnData Cleaningni. Missing Data and Misguided Missing Datanii. Noisy Dataniii. Data Cleaning as a ProcessnData Integration MethodsnData ReductionnData Reduction StrategiesnDimen

43、sionality Reductionni. Principal Component analysisnii. Feature Subset Selectionniii. Feature CreationnNumerosity Reductionni. Parametric Data Reduction: Regression and Log-Linear Modelsnii. Mapping Data to a New Space: Wavelet Transformationniii. Data Cube aggregationniv. Data Compressionnv. Histogram analysisnvi. Clusteringnvii. Sampling: Sampling without Replacement, Stratified SamplingnData Transformation and Data DiscretizationnData Transformation: NormalizationnData Discretization Methodsni. Binningnii. Cluster Analysisniii. Discretization Using Class Labels: Entropy-Based Di