数据挖掘 课件 第二章 数据挖掘中的预处理

数据挖掘中的预处理Contents数据挖掘过程概述01数据准备02数据预处理03数据挖掘的对象（1）关系型数据库、事务型数据库、面向对象的数据库；（2）数据仓库/多维数据库；（3）空间数据（如地图信息）（4）工程数据（如建筑、集成电路的信息）（5）文本和多媒体数据（如文本、图象、音频、视频数据）（6）时间相关的数据（如历史数据或股票交换数据）（7）万维网（如半结构化的HTML，结构化的XML以及其他网络信息）数据挖掘的步骤（1）数据清理（消除噪音或不一致数据，补缺）；（2）数据集成（多种数据源可以组合在一起）；（3）数据选择（从数据库中提取相关的数据）；（4）数据变换（变换成适合挖掘的形式）；（5）数据挖掘（使用智能方法提取数据模式）；（6）模式评估（识别提供知识的真正有趣模式）；（7）知识表示（可视化和知识表示技术）。Contents数据挖掘过程概述01数据准备02数据预处理03数据准备现实世界的数据是不完整的（有些感兴趣的属性缺少属性值，或仅包含聚集数据），含噪音的（包含错误，或存在偏离期望的异常值），不一致的（例如，用于商品分类的部门编码存在差异）。需要数据清理、数据集成、数据选择、数据变换等技术对数据进行处理。

数据准备——维归约/特征提取决策树归约（1）决策树归约构造一个类似于流程图的结构：其每个非叶子结点表示一个属性上的测试，每个分枝对应于测试的一个输出；每个叶子结点表示一个决策类。（2）在每个结点，算法选择“当前对分类最有帮助”的属性，出现在树中的属性形成归约后的属性子集。数据准备——维归约/特征提取粗糙集归约（1）粗糙集理论在数学意义上描述了知识的不确定性，它的特点是把用于分类的知识嵌入集合内，使分类与知识联系在一起。（2）知识的粒度、不可分辨关系、上近似、下近似、边界等概念见下图。数据准备——维归约/特征提取粗糙集归约（3）令Q代表属性的集合。q∈Q是一个属性，如果IND(Q−q)=IND(Q)，则q在S中不是独立的；否则称q在S中是独立的。（4）若集合满足IND(R)=IND(Q)且R中的每一个属性都是独立的，则R被称为Q的一个“约简”，记作R=RED(Q)。（5）约简可以通过删除冗余的（不独立的）属性而获得，约简包含的属性即为“对分类有帮助”的属性。数据准备——数据变换归一化与模糊化有限区间的归一化：无限区间的归一化：模糊隶属度：数据准备——数据变换核函数（1）核函数的基本思想是将在低维特征向量线性不可分的数据映射到线性可分的高维特征空间中去。（2）映射可以是显式的，也可以是隐式的。显式映射即找到一个映射关系f，使高维空间的特征向量f(x)可以被直接计算出来。（3）隐式映射，即引入一个核函数进行整体处理，就避免了对的直接求f(x)的计算困难。核函数即某高维特征空间中向量的内积，是核矩阵中的一个元素。（4）并不是所有的实值函数f(x)都可以作为空间映射的核函数，只有f(x)是某一特征空间的内积时，即符合Mercer条件，它才能成为核函数。数据准备——数据变换核函数多项式函数：

高斯（RBF）函数：

多层感知机函数：低维空间向量映射到高维空间向量举例：

数据准备——数据压缩离散化离散化的用途：（1）适应某些仅接受离散值的算法；（2）减小数据的尺度。离散化的方法包括几下几种。（1）等距分割；（2）聚类分割；（3）直方图分割；（4）基于熵的分割；（5）基于自然属性的分割。数据准备——数据压缩回归回归和对数线性模型可以用来近似给定的数据。在线性回归中，用一条直线来模拟数据的生成规则。多元回归是线性回归的扩展，涉及多个预测变量。在多项式回归中，通过对变量进行变换，可以将非线性模型转换成线性的，然后用最小平方和法求解。数据准备——数据压缩回归利用线性回归可以为连续取值的函数建模。广义线性模型则可以用于对离散取值变量进行回归建模。在广义线性模型中，因变量Y的变化速率是Y均值的一个函数；这一点与线性回归不同。常见的广义线性模型有：对数回归和泊松回归。对数回归模型是利用一些事件发生的概率作为自变量所建立的线性回归模型。泊松回归模型主要是描述数据出现次数的模型，因为它们常常表现为泊松分布。数据准备——数据压缩主成分分析（PCA）PCA算法搜索c个最能代表数据的k-维正交向量；这里c

k。这样，原来的数据投影到一个较小的空间，导致数据压缩。步骤如下：（1）对输入数据归一化，使得每个属性都落入相同的区间。（2）PCA计算c个规范正交向量，作为归一化输入数据的基。这些是单位向量，每一个都垂直于另一个：称为主成分。输入数据是主要成分的线性组合。（3）对主成分按“意义”或强度降序排列，选择部分主成分充当数据的一组新坐标轴。

数据准备——数据压缩离散小波变换（DWT）离散小波变换是一种线性信号处理技术。该技术方法可以将一个数据向量转换为另一个数据向量（为小波相关系数）；且两个向量具有相同长度。可以舍弃转换后的数据向量中的一些小波相关系数。保留所有大于用户指定阈值的小波系数，而将其它小波系数置为0，以帮助提高数据处理的运算效率。这一技术方法可以在保留数据主要特征情况下除去数据中的噪声，因此该方法可以有效地进行数据清洗。给定一组小波相关系数，利用离散小波变换的逆运算还可以近似恢复原来的数据。Contents数据挖掘过程概述01数据准备02数据预处理03数据预处理什么是数据预处理？数据挖掘的前提：真实世界中的数据来源复杂、体积巨大，往往难以避免地存在缺失、噪声、不一致等问题。为了提高数据挖掘的质量，产生了数据预处理技术。数据和特征决定了机器学习的上限，而所选模型和算法只是去逼近这个上限。数据预处理为什么做数据预处理？通过特征提取，我们能得到未经处理的特征，这时的特征可能有以下问题：不属于同一量纲：即特征的规格不一样，不能够放在一起比较。信息冗余：对于某些定量特征，其包含的有效信息为区间划分，例如学习成绩，假若只关心“及格”或不“及格”，那么需要将定量的考分，转换成“1”和“0”表示及格和未及格定性特征不能直接使用：某些机器学习算法和模型只能接受定量特征的输入，那么需要将定性特征转换为定量特征。存在缺失值：缺失值需要补充。信息利用率低：不同的机器学习算法和模型对数据中信息的利用是不同的。当数据的维数过高时还会存在所谓的“维数灾难（Curseofdimensionality）”问题，过高的维度不仅增加了计算量，反而可能会降低算法的效果。数据预处理常见数据预处理方法数据清洗处理数据的某些纪录值缺失，平滑数据中的噪声、发现异常值，改正不一致等。数据融合将不同来源的、异质的数据融合到一起。良好的数据融合可以减少数据中的冗余和不一致性，进而提升后续步骤的精度和速度。数据转换通过平滑聚集，数据概化，规范化等方式将数据转换成适用于数据挖掘的形式。数据降维将高维度数据化为低维度数据，仍保持原数据的大部分信息，使数据挖掘结果与降维前结果相同或几乎相同。数据预处理——数据清洗缺失值处理缺失值在实际数据中是不可避免的问题，对于不同的数据场景应该采取不同的策略，首先应该判断缺失值的分布情况：如果缺失值极少且这个维度信息不重要，一般删除它们对于整体数据情况影响不大；如果缺失值较多或这个维度的信息还很重要的时候，直接删除会对后面的算法跑的结果造成不好的影响。数据预处理——数据清洗缺失值处理我们常用的方法有以下几种：直接删除——适合缺失值数量较小，并且是随机出现的，删除它们对整体数据影响不大的情况；使用一个全局常量填充——譬如将缺失值用“Unknown”等填充，但是效果不一定好，因为算法可能会把它识别为一个新的类别，一般很少用；使用均值或中位数代替：

优点：不会减少样本信息，处理简单。缺点：当缺失数据不是随机数据时会产生偏差，对于正常分布的数据

可以使用均值代替，如果数据是倾斜的，使用中位数可能更好。数据预处理——数据清洗缺失值处理插补法

1）随机插补法——从总体中随机抽取某个样本代替缺失样本

2）多重插补法——通过变量之间的关系对缺失数据进行预测，例如利用蒙特卡洛方法

生成多个完整的数据集，在对这些数据集进行分析，最后对分析结果进行汇总处理

3）热平台插补——指在非缺失数据集中找到一个与缺失值所在样本相似的样本（匹配

样本）利用其中的观测值对缺失值进行插补。

4）拉格朗日差值法和牛顿插值法建模法——可以用回归、使用贝叶斯形式化方法的基于推理的工具或决策树归纳确定。例如，利用数据集中其他数据的属性，可以构造一棵判定树，来预测缺失值的值。

以上方法各有优缺点，具体情况要根据实际数据分分布情况、倾斜程度、缺失值所占比例等等来选择方法。一般而言，建模法是比较常用的方法，它根据已有的值来预测缺失值，准确率更高。数据预处理——数据清洗异常值处理异常值我们通常也称为“离群点”（outlier），即在样本空间中，与其他样本点的一般行为或特征不一致的点。一般可能有如下产生原因：计算的误差或者操作的错误所致，比如：某人的年龄

-999

岁，这就是明显由误操作所导致的离群点；数据本身的可变性或弹性所致，比如：一个公司中

CEO

的工资肯定是明显高于其他普通员工的工资，于是

CEO

变成为了由于数据本身可变性所导致的离群点。注意：离群点不一定是无用数据，它也许正是用户感兴趣的，比如在欺诈检测领域，那些与正常数据行为不一致的离群点，往往预示着欺诈行为，因此成为执法者所关注的。数据预处理——数据清洗异常值处理常见异常值检测方法：基于统计分布的离群点检测

这类检测方法假设样本空间中所有数据符合某个分布或者数据模型，然后根据模型采用不和谐校验（discordancytest）识别离群点。例如：1）3∂原则如果数据服从正态分布，在3∂原则下，异常值为一组测定值中与平均值的偏差超过3倍标准差的值。如果数据服从正态分布，距离平均值3∂之外的值出现的概率为P(|x-u|>3∂)<=0.003，属于极个别的小概率事件。如果数据不服从正态分布，也可以用远离平均值的多少倍标准差来描述。2）箱型图分析

箱型图提供了识别异常值的一个标准：如果一个值小于QL-1.5IQR或大于QU-1.5IQR的值，则被称为异常值。QL为下四分位数，表示全部观察值中有四分之一的数据取值比它小；QU为上四分位数，表示全部观察值中有四分之一的数据取值比它大；IQR为四分位数间距，是上四分位数QU与下四分位数QL的差值，包含了全部观察值的一半。箱型图判断异常值的方法以四分位数和四分位距为基础，四分位数具有鲁棒性：25%的数据可以变得任意远并且不会干扰四分位数，所以异常值不能对这个标准施加影响。因此箱型图识别异常值比较客观，在识别异常值时有一定的优越性。数据预处理——数据清洗异常值处理常见异常值检测方法：基于距离的离群点检测通常可以在对象之间定义邻近性度量，异常对象是那些远离其他对象的对象。如果样本空间D中至少有N个样本点与对象O的距离大于dmin,那么称对象O是以{至少N个样本点}和dmin为参数的基于距离的离群点。优点：简单；缺点：基于邻近度量的方法需要O(m^2)时间，大数据集不适用；该方法对参数的选择也是敏感的,不同的距离度量其结果也不一样；不能处理具有不同密度区域的数据集，因为它使用全局阈值，不能考虑这

种密度的变化。数据预处理——数据清洗异常值处理常见异常值检测方法：基于密度的局部离群点检测当一个点的局部密度显著低于它的大部分近邻时才将其分类为离群点。适合非均匀分布的数据。不同于基于距离的方法，基于密度的离群点检测不将离群点看做一种二元性质，即不简单用YesorNo来断定一个点是否是离群点，而是用一个权值来评估它的离群度。它是局部的，意思是该程度依赖于对象相对于其领域的孤立情况。这种方法可以同时检测出全局离群点和局部离群点。优点：给出了对象是离群点的定量度量，并且即使数据具有不同的区域也能够很好的处理；缺点：基于距离的方法一样，具有O(m^2)的时间时间复杂度，对于低维数据使用特定的数据结构可

以

达到O(mlogm)；参数选择困难。仍然需要选择这些离群度的上下界。数据预处理——数据清洗异常值处理处理方法：删除异常值——明显看出是异常且数量较少可以直接删除不处理——如果算法对异常值不敏感则可以不处理，但如果算法对异常值敏感，则最好不要用，如基于距离计算的一些算法，包括kmeans，knn之类的。平均值替代——损失信息小，简单高效。视为缺失值——可以按照处理缺失值的方法来处理数据预处理——数据清洗数据去重数据重复在实际生活中很常见，在一些数据挖掘模型中，这些冗余的数据加大了数据分析的难度和处理速度，因此需要对数据去重。常见方法：遍历数据搜索，复杂度高，仅适用于数据规模较小的情形。哈希表示，生成数据指纹，简单高效，适用于大规模数据，代表算法：1）Bitmap：位图法2）SimHash：相似哈希3）布隆过滤器数据预处理——数据清洗数据去噪噪声，是被测量变量的随机误差或方差。我们在上文中提到过异常点（离群点），那么离群点和噪音是不是一回事呢？观测量(Measurement)=真实数据(TrueData)+噪声(Noise)离群点(Outlier)属于观测量，既有可能是真实数据产生的，也有可能是噪声带来的，但是总的来说是和大部分观测量之间有明显不同的观测值。噪声包括错误值或偏离期望的孤立点值，但也不能说噪声点包含离群点，虽然大部分数据挖掘方法都将离群点视为噪声或异常而丢弃。然而，在一些应用（例如：欺诈检测），会针对离群点做离群点分析或异常挖掘。而且有些点在局部是属于离群点，但从全局看是正常的。数据预处理——数据清洗数据去噪常见数据去噪方法分箱法分箱方法通过考察数据的“近邻”（即周围的值）来光滑有序数据值。这些有序的值被分布到一些“桶”或箱中。由于分箱方法考察近邻的值，因此它进行局部光滑。1）用箱均值光滑：箱中每一个值被箱中的平均值替换。2）用箱中位数平滑：箱中的每一个值被箱中的中位数替换。3）用箱边界平滑：箱中的最大和最小值同样被视为边界。箱中的每一个值被最近的边界值替换。一般而言，宽度越大，光滑效果越明显。箱也可以是等宽的，其中每个箱值的区间范围是个常量。分箱也可以作为一种离散化技术使用。回归法可以用一个函数拟合数据来光滑数据。线性回归涉及找出拟合两个属性（或变量）的“最佳”直线，使得一个属性能够预测另一个。多线性回归是线性回归的扩展，它涉及多于两个属性，并且数据拟合到一个多维面。使用回归，找出适合数据的数学方程式，能够帮助消除噪声。数据预处理——数据融合数据融合就是将不同来源的、异质的数据融合到一起。良好的数据融合可以减少数据中的冗余(redundacies)和不一致性(inconsistence)，进而提升后续步骤的精度和速度。数据融合包括如下几个步骤：实体识别问题（EntityIdentificationProblem）实体识别中最主要的问题匹配不同的数据源中指向现实世界相同实体的纪录。比如分析有不同销售员纪录的17年和18年两年的销售数据，由于不同的销售员有不同的纪录习惯，顾客的名字纪录方式并不一样，一个销售员喜欢纪录全名（例如WardellStephenCurryII），另外一个销售员喜欢将中间名省略（WardellSCurryII），虽然WardellStephenCurryII和WardellSCurryII是现实世界中是同一名顾客，但计算机会识别为两位不同的顾客，解决这个问题就需要EntityIdentification。一个常用的EntityIndentificationProblem的解决算法是LSH算法。冗余和相关性分析当能够从样本的一个或多个属性推导出另外的属性的时候，那么数据中就存在冗余。检测冗余的一种方法是相关性分析——给定要进行检测的两个属性，相关性分析可以给出一个属性隐含(imply)另外一个属性的程度。对于标称型（Nominal）数据，可以使用χ2检验，而对于数值数据，可以根据方差和相关系数来分析。当相关系数是正的时候表示属性A和属性B正相关，当相关系数是负的时候属性A和属性B负相关，注意，相关关系并不等同于因果关系。数据预处理——数据转换在对数据进行统计分析时，要求数据必须满足一定的条件，数据转换就是将数据从一种表示形式变为另一种表现形式的过程。常见的数据转换方法大致可分为如下几类：离散化二值化归一化标准化正则化特征编码数据预处理——数据转换离散化有些数据挖掘算法，特别是某些分类算法，要求数据是分类属性形式。例如，发现关联模式的算法要求数据是二元属性形式。这样，常常需要将连续属性变换成分类属性（离散化，discretization），并且连续和离散属性可能都需要变换成一个或多个二元属性。此外，如果一个分类属性具有大量不同值（类别），或者某些值出现不频繁，则对于某些数据挖掘任务，通过合并某些值减少类别的数目可能是有益的。相比于连续属性值，离散属性值有一下优点：①通过离散化数据将被简化并且减少；②离散特征更容易被理解，使用和解释；③离散化使学习更加准确，快速；④使用离散特征获得的结果(如decisiontrees,inductionrules)更加紧凑，简短，准确，结果更容易进行检查，比较，使用和重复使用；⑤很多分类学习算法只能处理离散数据。常见离散化方法：1）无监督：分箱法（等宽/等频）、直观划分等2）有监督：1R方法、基于卡方的离散方法、基于熵的离散方法等数据预处理——数据转换二值化特征二值化是把数值特征转化成布尔值的过程，其核心在于设定一个阈值，大于阈值的赋值为1，小于等于阈值的赋值为0。这个方法对符合多变量伯努利分布的输入数据进行预测概率参数很有效。数据预处理——数据转换归一化归一化是一种简化计算的方式，即将有量纲的表达式，经过变换，化为无量纲的表达式，成为标量。它可将数据缩放至给定的最小值与最大值之间，通常是０与１之间。归一化常见两种方式：最小最大值归一化，将数据归一化到[0,1]区间绝对值最大归一化，将数据归一化到[-1,1]区间数据预处理——数据转换标准化不同的特征有不同的取值范围，如线性模型，特征的取值范围会对最终的结果产生较大的影响，取值范围不一致会导致模型会更偏向取值范围较大的特征。标准化通常是为了消除不同属性或样本间的不齐性，使同一样本内的不同属性间或同一属性在不同样本内的方差减小。另外数据的标准化也会加快数据的收敛速度。例如：Z-score标准化：数据预处理——数据转换正则化通常是为给数据加入某种限制，使其满足某一特性，常见的：L1正则化（稀疏性）：L2正则化（平滑性）：数据预处理——数据转换特征编码我们经常会遇到一些类别特征，这些特征不是离散型的数值，而是这样的：[“男性”,“女性”],[“来自欧洲”,“来自美国”,“来自亚洲”],[“使用Firefox浏览器”,“使用Chrome浏览器”,“使用Safari浏览器”,“使用IE浏览器”]等等。这种类型的特征可以被编码为整型（int），如[“男性”,“来自美国”,“使用IE浏览器”]可以表示成[0,1,3]，[“女性”,“来自亚洲”,“使用Chrome浏览器”]可以表示成[1,2,1]。这些整数式的表示不能直接作为机器学习模型的参数，因为我们需要的是连续型的输入，而且我们通常是有序的翻译这些特征，而不是所有的特征都是有序化的（譬如浏览器就是按人工排的序列）。将这些类别特征转化成机器学习模型的参数，可以使用的方法是：使用one-of-K或者one-hot编码（独热编码OneHotEncoding）。它可以把每一个有m种类别的特征转化成m中二值特征。注意：除了上述所提及的6种数据转换方法，我们可以根据模型需求和数据特性，自定义转换方法。数据预处理——数据降维维数灾难指在涉及到向量的计算的问题中，随着维数的增加，计算量呈指数倍增长的一种现象。维度灾难最直接的后果就是过拟合现象，而发生该现象最根本的原因是：维度增加时，有限的样本空间