数据挖掘概念与技术第二章数据预处理的课件

1、数据挖掘: 概念与技术 第二章 数据预处理 2022/8/141数据挖掘：概念与技术第二章： 数据预处理为什么需要数据预处理?描述性数据汇总数据清理 数据集成和变换数据归约数据离散化和概念分层产生总结2022/8/142数据挖掘：概念与技术为什么需要预处理数据？现实世界的数据容易“变脏”不完整: 缺省属性值,缺少感兴趣的属性, 或者仅仅包含聚集数据。e.g., occupation=“ ”噪声: 包含错误数据或者离群数据e.g., Salary=“-10”不一致: 编码或名称有差异的数据e.g., Age=“42” Birthday=“03/07/1997”e.g., Was rating “

2、1,2,3”, now rating “A, B, C”2022/8/143数据挖掘：概念与技术为什么数据会变脏?不完整的数据可能来自收集数据时该数据值(属性)没有用在收集数据和分析数据时的存在不同考虑人员/硬件/软件故障的噪声数据（不正确的数值）可能来自仪器设备产生错误数据数据输入时人为错误或计算机错误数据传输错误不一致数据可能来自不同的数据源违反函数依赖 (e.g., 修改一些关联数据（FK）)重复元组也需要数据清理2022/8/144数据挖掘：概念与技术为什么数据预处理很重要?低质量的数据导致低质量的挖掘结果高质量的决策必须依赖于高质量的数据e.g., 重复数据和缺失数据可能引起不正确，

3、甚至令人误解的统计结果。数据仓库需要集成高质量的一致性数据数据抽取、清理和转换是构建数据仓库的主要工作。2022/8/145数据挖掘：概念与技术数据质量的度量被广泛接受的数据质量观点：精确性完全性一致性合时性可信性增值性可解释性可访问性广泛分类:内在的,上下文关系的,代表性的,可访问性的2022/8/146数据挖掘：概念与技术数据预处理的主要任务数据清理填充缺失值,光滑噪声数据, 识别和删除离群值,解决不一致性数据集成集成多个数据库、数据立方体或平面文件数据转换规范化和聚集数据归约获得大量数据的简化表示，但能够产生同样的结果数据离散化数据归约的一种，对于数值数据自动产生概念分层非常重要。202

4、2/8/147数据挖掘：概念与技术Chapter 2: Data PreprocessingWhy preprocess the data?描述性数据汇总Data cleaning Data integration and transformationData reductionDiscretization and concept hierarchy generationSummary2022/8/148数据挖掘：概念与技术挖掘数据的描述性特征（1）动机更好地理解数据分布：中心趋势，变化和传播趋势数据的中心趋势度量均值(mean)、中位数(median)、众数(mode)、中列数(midran

5、ge)等。数据的离中趋势度量四分位数(quartiles)、四分位数极差(interquartile range, IQR)、极差(range)、方差(variance)等。2022/8/149数据挖掘：概念与技术挖掘数据的描述性特征（2）数据度量类型分布式度量将数据集划分为较小的子集，计算每个子集的度量，然后合并计算结果而得到原数据集的度量值。如sum(), count(), min(), max()等。代数度量采用多个分布式度量函数来导出计算数据集的度量值。如average()=sum()/count() 。整体度量必须对整个数据集计算的度量，计算开销较大，可以寻找近似计算的方法。2022

6、/8/1410数据挖掘：概念与技术度量数据的中心趋势（1）平均值mean (代数度量，分布式度量，SQL中AVG():加权算术平均:截断平均（Trimmed mean）: 去掉极值中值median: (整体度量值)奇数个值的中间值, 偶数个值的中间两个的平均值插值估计 (for 分组分区间数据):2022/8/1411数据挖掘：概念与技术度量数据的中心趋势（2）众数Mode集合中出现频率最高的值单峰的 Unimodal, 双峰的 bimodal, 三峰的trimodal经验公式：中列数数据集中最大和最小值的平均值2022/8/1412数据挖掘：概念与技术度量数据的离散程度（1） (数据已经递增

7、排序)极差，四分位数, 离群点 与 盒图极差（range）：最大值与最小值之差四分位数: Q1 (第25个百分位数), Q3 (第75个百分位数)中间四分位数极差: IQR = Q3 Q1 五数概括: min, Q1, Median, Q3, max盒图:盒的端点在四分位数上使得盒的长度是中间四分位数极差IQR中位数用盒内的线标记盒的另外两条线（胡须）延伸到最小和最大观测值离群点单独个别绘出离群点:高于Q3或低于Q1的1.5 x IQR2022/8/1413数据挖掘：概念与技术度量数据的离散程度（2）方差和标准差 方差: (代数度量, 可伸缩的计算)标准差 s (or ) 是方差的平方根 s2

8、 (or 2)2022/8/1414数据挖掘：概念与技术正态分布曲线的属性正态分布曲线从 到 +: 大约包含68%的观测值 (: mean, : standard deviation)从 2 到 +2:大约包含95%的观测值 从 3 到 +3:大约包含99.7%的观测值 2022/8/1415数据挖掘：概念与技术描述数据汇总的图形显示直方图：Histogram盒图: Boxplot分位数图：Quantile plot分为数分为数图：Quantile-quantile (q-q) plot散布图：Scatter plot局部回归曲线：Loess (local regression) curve2

9、022/8/1416数据挖掘：概念与技术直方图分析频率直方图 概括给定属性分布的图形方法根据某一数据属性将数据分布划分为不相交的子集或桶。每个桶的宽度一致桶的高度等于桶中的值的计数或相对频率2022/8/1417数据挖掘：概念与技术分位数图：Quantile Plot观察单变量数据分布的简单有效方法显示给定属性的所有数据 (允许用户评估总体情况和不寻常的出现情况)绘出分位数信息对于按递增排序的数据xi ，每个观测值xi 与一个百分数fi 配对，使得数据的fi %的数据小于或等于xi Q10.25分为数； Q20. 5分为数； Q30.75分为数；2022/8/1418数据挖掘：概念与技术分为数

10、分为数图：Quantile-Quantile (Q-Q) Plot对着另一个对应的分为数图，绘制一个单变量分布的分为数可以观察从一个分布到另一个分布是否有位移强有力的数据可视化工具2022/8/1419数据挖掘：概念与技术散布图：Scatter plot确定两个属性值之间是否有联系、模式或趋势的图形化方法每个值对视为一个代数坐标对，作为一个点画在平面上。观察双变量的方法，观察点的簇和离群点，考察相关联系的可能性。2022/8/1420数据挖掘：概念与技术正相关和负相关数据2022/8/1421数据挖掘：概念与技术 不相关数据2022/8/1422数据挖掘：概念与技术局部回归曲线：Loess C

11、urve增加一条光滑曲线到散布图，以便更好地理解依赖模式两个设置参数： 光滑参数，在0.251之间被拟合多项式的次数， =1，先行拟合； =2，二次拟合2022/8/1423数据挖掘：概念与技术Chapter 2: Data PreprocessingWhy preprocess the data?Descriptive data summarizationData cleaning Data integration and transformationData reductionDiscretization and concept hierarchy generationSummary202

12、2/8/1424数据挖掘：概念与技术数据清理重要性“数据清理是数据仓库中三个最大的问题之一”Ralph Kimball“数据清理是数据仓库中的第一个问题”DCI survey数据清理的任务填充缺失值识别离群点和平滑噪声数据纠正不一致的数据解决由于数据集成而引起的数据冗余问题2022/8/1425数据挖掘：概念与技术缺失数据数据并不是经常可用的E.g., 许多元组的一些属性上没有记录值，如销售数据中没有顾客的收入。缺失值的可能原因设备故障由于与其它记录数据的不一致而删除由于误解而没有记录相关数据某些数据可能由于当时认为不重要而没有录入记录历史或修改的数据被忽略。缺失数据需要被推断出来2022/8

13、/1426数据挖掘：概念与技术如何处理缺失值？忽略元组：缺失类标号时忽略该元组 (对于分类挖掘当每个属性缺少值的百分比变化很大时，性能特别差。人工填写缺失值：费时乏味，甚至不可行。自动填值方法：用全局常量填写： e.g., “unknown”, 可能被认为一个新类?! 用属性的平均值填写用与给定元组属同一类的所有样本的属性均值填写: smarter！使用最可能的值填写：基于推理的方法，如回归、贝叶斯、回归树方法2022/8/1427数据挖掘：概念与技术噪声数据噪声:被测量数据的随机误差或方差不正确的属性值可能由于：有故障的数据采集设备数据录入问题数据传输问题技术限制，如数据传输的同步缓冲区的大

14、小限制不一致的命名约定需要数据清理的其他数据问题重复数据不完备数据不一致数据2022/8/1428数据挖掘：概念与技术如何处理噪声数据?分箱（Binning）先排序，然后分箱（等频）箱均值光滑，箱中位数光滑，箱边界值光滑。回归（regression）通过回归函数拟合数据来光滑数据聚类（Clustering）检测并删除离群点计算机与人工检测相结合检测可疑值，并由人工确认，如离群点检测。2022/8/1429数据挖掘：概念与技术简单的离散化方法：分箱等宽分割(distance)将变化范围均分为N个间隔。若A和B分别为属性值的最小和最大值，则间隔宽度为： W = (B A)/N.最简单直接的方法，但

15、容易受离群点的影响。倾斜数据不能很好地处理等深分割 (frequency)将变化范围分为N个间隔，每个间隔内包含相同的样本数。具有很好的数据伸缩性。2022/8/1430数据挖掘：概念与技术分箱方法举例已经排序的价格数据：4, 8, 9, 15, 21, 21, 24, 25, 26, 28, 29, 34* 等频（等深）分箱: - Bin 1： 4, 8, 9, 15 - Bin 2：21, 21, 24, 25 - Bin 3：26, 28, 29, 34* 箱均值光滑 - Bin 1 ： 9, 9, 9, 9 - Bin 2 ： 23, 23, 23, 23 - Bin 3 ： 29,

16、29, 29, 29* 箱边界光滑: - Bin 1 ： 4, 4, 4, 15 - Bin 2 ： 21, 21, 25, 25 - Bin 3 ： 26, 26, 26, 342022/8/1431数据挖掘：概念与技术回归xyy = x + 1X1Y1Y12022/8/1432数据挖掘：概念与技术聚类分析2022/8/1433数据挖掘：概念与技术数据清理作为一个过程数据偏差检测使用元数据 (e.g., domain, range, dependency, distribution)检查字段过载，新属性挤占了未使用的部分。 检查唯一性规则、连续性规则和空值规则。使用商业工具进行偏差检测数据清

17、洗工具: 使用简单的域知识 检测和修改错误数据审计工具: 通过分析数据发现规则和联系以及检测违反这些条件的数据来发现偏差 (e.g., 相关或聚类来发现离群点)数据迁移与集成数据迁移工具: 允许说明变换ETL (Extraction/Transformation/Loading) 工具: 允许用户通过图形用户界面说明变换数据集成的两个过程迭代和交互 (e.g., Potters Wheels，数据清理工具，)2022/8/1434数据挖掘：概念与技术Chapter 2: Data PreprocessingWhy preprocess the data?Data cleaning Data i

18、ntegration and transformationData reductionDiscretization and concept hierarchy generationSummary2022/8/1435数据挖掘：概念与技术数据集成数据集成：合并来自多个数据存储的数据模式集成: e.g., A.cust-id B.cust-#从不同的源数据集成元数据实体识别问题： e.g., Bill Clinton = William Clinton检测并解决数据值冲突对于同一实体, 不同数据源中的属性值是不相同的可能原因：不同表示方法，不同尺度2022/8/1436数据挖掘：概念与技术处理数据

19、集成中的冗余多个数据集成时冗余数据可能发生于：对象识别: 同一属性或对象在不同数据库中可能有不同的名字。派生数据： e.g., annual revenue相关分析可能检测到属性冗余细致集成多源数据可以减少或避免冗余和不一致性，从而提高数据挖掘的速度和质量2022/8/1437数据挖掘：概念与技术相关分析 (数值数据)相关系数 (also called Pearsons product moment coefficient)where n is the number of tuples, and are the respective means of A and B, A and B are

20、the respective standard deviation of A and B, and (AB) is the sum of the AB cross-product.If rA,B 0, A and B 正相关 The higher, the stronger correlation.rA,B = 0: 独立; rA,B 0: 负相关2022/8/1438数据挖掘：概念与技术相关性分析 (分类数据)2 (卡方) 检验：相依表2 越大, 变量越可能相关对2贡献最大的单元是其实际计数值与期望计数值很不相同的单元。相关性并不意味因果关系医院数与盗车数是相关的，不意味一个因素导致另一个因

21、素。由于第三变量:人口2022/8/1439数据挖掘：概念与技术卡方计算例子2 (chi-square) calculation (numbers in parenthesis are expected counts calculated based on the data distribution in the two categories)It shows that like_science_fiction and play_chess are correlated in the groupPlay chessNot play chessSum (row)Like science fict

22、ion250(90)200(360)450Not like science fiction50(210)1000(840)1050Sum(col.)300120015002022/8/1440数据挖掘：概念与技术数据转换平滑: 去掉数据中的噪声聚集: 汇总，构造数据立方体数据泛化: 概念分层（向上提升）规范化: 将属性按比例缩放,变换到指定的范围最小最大规范化z-score 规范化（零均值规范化）小数定标规范化属性构造（特征构造）：从给定的属性集中构造新的属性2022/8/1441数据挖掘：概念与技术数据转化：规范化最小-最大规范化: to new_minA, new_maxAEx. 将收入范

23、围 $12,000到$98,000 规范到 0.0, 1.0. 则 $73,000 将映射为 Z-score 规范化 (: mean, : standard deviation):Ex. Let = 54,000, = 16,000. Then小数定标规范法j 是使得 Max(|) 1的最小整数2022/8/1442数据挖掘：概念与技术Chapter 2: Data PreprocessingWhy preprocess the data?Data cleaning Data integration and transformationData reductionDiscretization

24、and concept hierarchy generationSummary2022/8/1443数据挖掘：概念与技术数据归约策略为什么需要数据归约?Tb级的数据仓库在完整的数据集上进行复杂的数据分析或挖掘非常耗时数据归约 在更小的数据量上获得归约表示，但产生相同或近似的结果数据归约策略数据立方体聚集:属性子集选择 e.g., 去除不重要的属性数据压缩：使用编码机制减少数据集的规模数值归约 e.g., 将数据拟合成模型离散化和概念分层产生2022/8/1444数据挖掘：概念与技术数据立方体聚集基本立方体 (base cuboid)：最低抽象层创建的立方体对应于感兴趣的个体实体，E.g., 顾

25、客顶点立方体（apex cuboid）：最高层抽象的立方体。E.g.,所有商品类型，所有分店三年的总销售额。多层次聚集进一步减少数据量参考合适的层级用最小但足够的立方体实现给定任务2022/8/1445数据挖掘：概念与技术属性子集选择特征选择 (i.e., 属性子集选择):目标：找出最小属性集，使数据类的概率分布尽可能地接近使用所有属性得到的原分布减少了出现在发现模式的属性数目，使得模式更易于理解最好和最差属性使用统计显著性检验来确定。对于d个特征，存在2d 个可能的子集启发式方法 (由于与选择组合成指数关系):逐步向前选择逐步向后删除向前选择与向后删除结合决策树归纳2022/8/1446数据

26、挖掘：概念与技术启发式属性子集选择的例子2022/8/1447数据挖掘：概念与技术数据压缩字符串压缩有一些很好的理论和算法无损压缩但只允许有限的数据操作视频/音频压缩有损压缩有时小的片段可以在不整体重构的情况下重构2022/8/1448数据挖掘：概念与技术数据压缩原始数据压缩数据无损压缩近似的原始数据 有损压缩2022/8/1449数据挖掘：概念与技术维度压缩:小波变换 离散小波变换 (DWT):线性信号处理，多分辨率分析近似压缩数据：仅保存一小部分最强的小波系数与离散傅立叶变换近似 (DFT), 但有损压缩更好，小波空间局部性相当好，有助于保留局部细节。方法:长度L必须是2的整数次幂 (必要

27、时添0补充)每次变换涉及两个函数:平滑函数, 加权差分函数递归作用于上一步的结果数据集, 导致两个长度为 L/2的数据集 Haar2Daubechie42022/8/1450数据挖掘：概念与技术基于DWT的图像压缩Image Low Pass High Pass Low Pass High PassLow Pass High Pass2022/8/1451数据挖掘：概念与技术搜索k个最能代表数据的n维正交向量，将原来的数据投影到一个小得多的空间。通过创建一个替换的、更小的变量集组合属性的基本要素。 步骤输入数据规范化:每个属性都落入相同的区间计算k个正交向量输入数据是主成份的线性组合对主成份按

28、重要性或强度降序排列去掉较弱的成分（即方差较小）来归约数据的规模，使用最强的主成份应当能够非常近似的原始数据。仅能处理数值型数据当维数维度压缩: 主成份分析 (PCA)2022/8/1452数据挖掘：概念与技术X1X2Y1Y2主成分分析2022/8/1453数据挖掘：概念与技术数值归约通过选择替代的、较小的数据表现形式来减少数据量参数方法使用模型估计数据，只需存放模型参数，而不是实际数据。例子：回归模型，对数线性模型非参数方法不要假设模型直方图，聚类，抽样2022/8/1454数据挖掘：概念与技术数据归约 (1): 回归和对数线性模型线性回归: 对数据拟合成直线模型常用最小二乘方法求解斜率和截

29、距系数多元回归: 允许响应变量建模为多个预测变量的线性函数。对数线性模型: 近似离散的多维概率分布。2022/8/1455数据挖掘：概念与技术回归分析: Y = w X + b两个回归系数, w 和 b, 对 Y1, Y2, , X1, X2, .通过最小二乘计算多元回归: Y = b0 + b1 X1 + b2 X2.对数线性模型:概率: p(a, b, c, d) = ab acad bcd回归分析和对数线性模型2022/8/1456数据挖掘：概念与技术数据归约方法 (2): 直方图将数据划分为桶，并存储每桶的平均值划分规则:等宽: 每桶范围相同等频 (or 等深)：每桶个数相同V-最优具

30、有最小方差的直方图MaxDiff: 桶的边界是具有1 最大差（相邻值之间的差）的对， 为桶数2022/8/1457数据挖掘：概念与技术数据归约方法 (3): 聚类将数据划分为簇或群，使得簇中对象相似，而与其他簇中对象相异，仅存储簇的表示相似性基于距离函数，用对象在空中的接近程度。能够提供分层聚类，并存储在多维索引树中。第七章讲聚类。2022/8/1458数据挖掘：概念与技术数据归约方法 (4): 抽样抽样: 用小样本表示整个数据集 得到样本的开销正比于样本集的大小，而不是数据集的大小抽样的复杂性子线性与数据的大小无放回简单随机抽样有放回简单随机抽样聚类抽样分层抽样2022/8/1459数据挖掘

31、：概念与技术抽样: 有/无放回SRSWOR(simple random sample without replacement)SRSWRRaw Data2022/8/1460数据挖掘：概念与技术抽样: 聚簇或分层抽样Raw Data Cluster/Stratified Sample2022/8/1461数据挖掘：概念与技术Chapter 2: Data PreprocessingWhy preprocess the data?Data cleaning Data integration and transformationData reductionDiscretization and co

32、ncept hierarchy generationSummary2022/8/1462数据挖掘：概念与技术离散化三类属性:名义的 values from an unordered set, e.g., color, profession次序的 values from an ordered set, e.g., military or academic rank 连续的 real numbers, e.g., integer or real numbers离散化: 将连续属性范围分割为间隔一些分类算法仅接受分类属性减少数据为进一步分析作准备2022/8/1463数据挖掘：概念与技术离散化和概念

33、分层离散化 通过将属性范围分割为区间值减少数据值区间标记可以替代实际值监督和非监督的离散化分裂 (top-down) vs. 合并 (bottom-up)可以迭代离散化概念分层形式通过高层概念替换较低层概念来迭代减少哦数据2022/8/1464数据挖掘：概念与技术数值数据的离散化和概念分层产生典型方法:所有方法都可以递归使用。分箱 (covered above)Top-down split, unsupervised, 直方图分析 (covered above)Top-down split, unsupervised聚类分析 (covered above)Either top-down spl

34、it or bottom-up merge, unsupervised基于熵的离散化: supervised, top-down split基于 2 分析的区间合并: unsupervised, bottom-up merge根据直观划分离散化: top-down split, unsupervised2022/8/1465数据挖掘：概念与技术基于熵的离散化Given a set of samples S, if S is partitioned into two intervals S1 and S2 using boundary T, the information gain after

35、partitioning isEntropy is calculated based on class distribution of the samples in the set. Given m classes, the entropy of S1 iswhere pi is the probability of class i in S1The boundary that minimizes the entropy function over all possible boundaries is selected as a binary discretizationThe process

36、 is recursively applied to partitions obtained until some stopping criterion is metSuch a boundary may reduce data size and improve classification accuracy2022/8/1466数据挖掘：概念与技术基于 2 分析的区间合并Merging-based (bottom-up) vs. splitting-based methodsMerge: Find the best neighboring intervals and merge them t

37、o form larger intervals recursivelyChiMerge Kerber AAAI 1992, See also Liu et al. DMKD 2002Initially, each distinct value of a numerical attr. A is considered to be one interval2 tests are performed for every pair of adjacent intervalsAdjacent intervals with the least 2 values are merged together, s

38、ince low 2 values for a pair indicate similar class distributionsThis merge process proceeds recursively until a predefined stopping criterion is met (such as significance level, max-interval, max inconsistency, etc.) 2022/8/1467数据挖掘：概念与技术根据直观划分离散化A simply 3-4-5 rule can be used to segment numeric d

39、ata into relatively uniform, “natural” intervals.If an interval covers 3, 6, 7 or 9 distinct values at the most significant digit, partition the range into 3 equi-width intervalsIf it covers 2, 4, or 8 distinct values at the most significant digit, partition the range into 4 intervalsIf it covers 1,

40、 5, or 10 distinct values at the most significant digit, partition the range into 5 intervals2022/8/1468数据挖掘：概念与技术Example of 3-4-5 Rule(-$400 -$5,000)(-$400 - 0)(-$400 - -$300)(-$300 - -$200)(-$200 - -$100)(-$100 - 0)(0 - $1,000)(0 - $200)($200 - $400)($400 - $600)($600 - $800)($800 - $1,000)($2,000

41、 - $5, 000)($2,000 - $3,000)($3,000 - $4,000)($4,000 - $5,000)($1,000 - $2, 000)($1,000 - $1,200)($1,200 - $1,400)($1,400 - $1,600)($1,600 - $1,800)($1,800 - $2,000) msd=1,000Low=-$1,000High=$2,000Step 2:Step 4:Step 1: -$351-$159profit $1,838 $4,700 Min Low (i.e, 5%-tile) High(i.e, 95%-0 tile) Maxco

42、unt(-$1,000 - $2,000)(-$1,000 - 0)(0 -$ 1,000)Step 3:($1,000 - $2,000)2022/8/1469数据挖掘：概念与技术分类数据的概念分层产生Specification of a partial/total ordering of attributes explicitly at the schema level by users or expertsstreet city state countrySpecification of a hierarchy for a set of values by explicit data groupingUrbana, Champaign, Chicago Illinois