《数据挖掘》课件 第2章 数据预处理与相似性.pdf

数据挖掘高级大数据人才培养丛书之一，大数据挖掘技术与应用第二章数据预处理与相似性数据是数据挖掘的目标对象和原 始资源，对数据挖掘最终结果起 着决定性的作用。现实世界中的 数据是多种多样的，具有不同的 特征，这就要求数据的存储采用 合适的数据类型，并且数据挖掘 算法的适用性会受到具体的数据 类型限制。另外，原始数据通常存在着噪声、不一致、部分数据缺失等问题，为了达到较好的挖掘结果，有必 要对这些数据进行预处理加工从 而提高数据的质量Hu Oflu d之 弋 1;IX 1 1 1 1 o 1 1 1*nu 1*1*1*1*1*1*1 1*nu Hu 1 nuX nu 1A nu 1 u flu nu 1A nu nu 1，nuA 1-，1 lx 1 1 nu nu nu-IX 1.nu 1高级大数据人才培养丛书之一，大数据挖掘技术与应用第二章数据预处理与相似性.2.1数据类型预处理2.3数据的相似性习题，2.1数据类型第二章数据预处理与相似性2.1.1属性与度量属性是数据对象的性质或特性，属性又可称为特征。每一个数据对象用一组属性描述，数据集是用结构化数据表表示，其中列是存放在表中的对象的属性，行代表一个对象实 例，表中单元格是实例对应属性的属性值。样本示例特征（属性）编号花萼长花萼宽花瓣长花瓣宽3.5J工3.01.4 1-5.93.05.12.1数据类型第二章数据预处理与相似性2.1.1属性与度量属性的测量值与属性的值的意义并不是完全对等的,比如数学上24.4是12.2的两倍，但 作为摄氏温度值24.4并不代表比12.2温暖两倍。天气属性值中晴天和多云也可 以用不同的数字来表示，它们没有前后次序关系，也不能进行加减运算，只能测试相等 或不等才有意义。在数据挖掘中知道属性的类型可以避免使用错误的统计操作。属性类别描述例 F分类的（定性的）标称类型的名称或编号（=#）工号，鱼的种类草鱼，鱼连鱼，黑鱼序数值有大小或前后关系（,）气温炎热，温暖，冷,成绩 优，良，中，差二元只有两个类别或状态（=，羊）抽烟0，1，其中1表示是，。表 示非数值的（定量的）区间有序，可加减不可乘除（-,+）摄氏温度，日期比率有自然零值，可以进行任何数学 运算（*,/）年龄，长度，重量，2.1数据类型第二章数据预处理与相似性2.1.2数据集的类型数据集的类型是从集合整体上分析数据的类型。从数据对象之间的结构关系角度 进行划分，比较常见的有记录数据、有序数据、图形数据。记录数据记录数据是最常见的数据集类型，数据集是一个二维表格，其中表中 行代表记录，列代表属性。例如一张普通的Excel表格文件或一张关 系数据库中的表。有序数据有序数据对象之间存在时间或空间上的顺序关系。例如股票价格波动 信息，医疗仪器监视病人的心跳、血压、呼吸数值，用户上网购物会 产生鼠标点击网页等操作指令序列，这些信息可以用来挖掘用户的上 网习惯。图形数据图形数据对象之间存在显式或隐式的联系，相互之间有一定的复杂依 赖关系，构成图形或网状结构，如互联网中的超链接。高级大数据人才培养丛书之一，大数据挖掘技术与应用第二章数据预处理与相似性2.1 数据类型2.2 数据预处理2.3 数据的相似性 习题，2.2数据预处理第二章数据预处理与相似性数据挖掘工作始终是以数据为中心开 展的，分类、聚类、回归、关联分析 以及可视化等工作的顺利进行完全是 建立在良好的输入数据基础之上。软 件开发行业有旬格言：Garbage-In-Garbage-Out/Z z这句话同样适用 于数据科学。事实上，我们采集到的原始数据通常 来自多个异种数据源，数据在准确性、完整性和一致性等方面存着多种多样 的问题，这些数据并不适合直接进行 挖掘。在进行挖掘算法执行之前，它 们需要进行一些诸如：移植、清洗、切片、转换等预处理工作。2.2数据预处理第二章数据预处理与相似性2.2.1数据清理由于人工输入错误或仪器设备测量精度以及数据收集过程机制缺陷等方面原因都 会造成采集的数据存在质量问题，主要包括：测量误差、数据收集错误、噪声、离群点（outlier）、缺失值、不一致值、重复数据等问题。数据清理阶段的主要 任务就是通过填写缺失值，光滑噪声数据、删除离群点和解决属性的不一致性等 手段来清理数据。缺失值处理噪声数据 1.忽略元组 2.数据补齐 1.分箱 2.孤立点分析，2.2数据预处理第二章数据预处理与相似性2.2.2数据集成数据集成就是将若干个分散的数据源中的数据，逻辑地或物理地集成到一个统一 的数据集合中。这些数据源包括关系数据库、数据仓库和一般文件。数据集成的 核心任务是要将互相关联的分布式异构数据源集成到一起，使用户能够以透明的 方式访问这些数据源。SQL，2.2数据预处理第二章数据预处理与相似性2.2.3数据规范化在对数据分析前，通常需要先将数据规范化(Normalization),也称为标 准化。不同性质属性数据直接相加不能正确反映出不同作用的正确结果。数据规 范化主要包括数据同趋化处理和无量纲化处理两个方面，可以使属性值按比例落 入到一个特定区间，如-LU或0,口。数据规范化一方面可以简化计算，提升模型的收敛速度；另一方面，在涉及 一些距离计算的算法时防止较大初始值域的属性与具有较小初始值域的属性相比 权重过大，可以有效提高结果精度。2.2数据预处理第二章数据预处理与相似性2.2.3数据规范化1.最小一最大规范化也称离差标准化，是对原始数据的线性变换，假定min,max分别为属性A的最小 值和最大值。转换函数如下：,x-min/.、x=-(new _ max-new _ min)+new _ minmax-min将痔专换到区间new_min,new_max中，结果为国这种方法有一个 缺陷就是当有新的数据加入时，可能导致max,min值的变化，需要重新定义。如果要做。-1规范化，上述式子可以简化为：,x-minjc max-min，2.2数据预处理第二章数据预处理与相似性2.2.3数据规范化2.z-score规范化也叫标准差标准化，经过处理的数据符合标准正态分布，即均值为0,标准差为L 属性A的值基A的均值a和标准内规范化，转化函数为：x-A jc-当属性A的实际最大值和最小值未知，或有超出取值范围的孤立点时,该方法适用。2.2数据预处理第二章数据预处理与相似性2.2.3数据规范化3.按小数定标规范化通过移动数据的小数点位置来进行标准化。小数点的移动位数取决于属性A的最 大绝对值。计算方法：，工X-7107其中/是使的最小整数。z-84x231,取/,=3，-84规范化后值为-0.084,23/规范化后为0.231。，2.2数据预处理第二章数据预处理与相似性2.2.4数据约简数据约简(data reduction)技术是指 在尽可能保持原始数据集完整性的前堤下，最大限度地精简数据量。数据约简技术可以用来得到数据集的归 约表示，它虽然小，但仍大致保持原数据 的完整性。在归约后的数据集上挖掘将更 有效，并产生相同(或几乎相同)的分析结果。下面介绍几种常用数据约简策略。，2.2数据预处理第二章数据预处理与相似性2.2.4数据约简1.属性子集选择嵌入式方法过滤方法包装器方法将属性选择任务 插入到数据挖掘 过程当中，挖掘 算法本身包含了 属性选择任务。属性选择过程独 立于挖掘算法。这种方法速度快,但是选出的属性 子集的分类性能 弱于包装器方法。属性选择与分类 算法绑定，在筛 选属性的过程中 直接用所选的特 征子集来训练分 类器，并根据在 测试集上的性能 表现来评价属性 子集的优劣。第二章数据预处理与相似性2.2.4数据约简2.主成分分析主成分分析(Principal Component Analysis,PCA)是一种广泛用于不同领域的无监督线 性数据转换技术。PCA的目标是在高维数据中找到最大方差的方向，并将数据映射到一个维度 小得多的新子空间上。借助于正交变换，将其分量相关的原随机向量转化成其分量不相关的新 随机向量。在代数上表现为将原随机向量的协方差阵变换成对角形阵，在几何上表现为将原坐 标系变换成新的正交坐标系，使之指向样本点散布最开的几个正交方向。，2.2数据预处理第二章数据预处理与相似性2.2.5数据离散化有些数据挖掘算法，要求数据属性是标称类别，当数据中包含数值属性时，为了使用这些算 法需要将数值属性转换成标称属性。通过采取各种方法将数值属性的值域划分成一些小的区 间，并将这连续的小区间与离散的值关联起来，每个区间看作一个类别。例如，某个问题中 的年龄属性一种可能的划分成类别操作是：0.11一儿童，口2.17青少年，口8.44一 青年，45.69一中年，69.8一老年。这种将连续变量划分成不同类别的过程通常称为离 散化(Discretization)。，2.2数据预处理第二章数据预处理与相似性2.2.5数据离散化连续属性离散化的问题本质是：决定选择多少个分割点和确定分割点位置。任务可分为两个步骤 完成。首先将连续属性排序，并通过指定n-l个分割点把它们分成n个区间。然后，将一个区间中 的所有值映射到相同的分类值。将排好序的数据从最小值到最大值 均匀划分成偌份，每份的间距是相 等的。假设A和B分别是属性值的最 小值和最大值，那么划分间距为 w=B-A/n这种方法的缺点是对异常点比较敏 感，倾向于不均匀地把实例分布到 各个箱中。将数据总记录数均匀分为灌份，每 份包含的数据个数相同。如果,那么每一份中将包含大约10%的数 据对象。等频法可能将具有不相同类标号的 相同属性值分入不同的箱中以满足 箱中数据固定个数的条件。等竟分箱法等频分箱法，2.2数据预处理第二章数据预处理与相似性2.2.5数据离散化ChiMerge是一种监督的、基于x?检验的数据离散化方法。其基本思想：对于精确的离 散化，相对类频率在一个区间内应当完全一致。因此，如果两个相邻的区间具有非常 类似的类分布，则这两个区间可以合并；否则，它们应当保持分开。而低庐值表明它 们具有相似的类分布。ChiMerge算法离散化数据操作流程包含三个基本步骤：(1)将所有样本数据按给定数值属性A的值升序排序。(2)把数值属性A的每个不同值看作一个区间。(3)对每对相邻的区间进行x2检验。将最小x2值的相邻区间合并成一个区间。重复 执行x2检验并且自底向上全并区间直到2检验达到设定的阈值。高级大数据人才培养丛书之一，大数据挖掘技术与应用第二章数据预处理与相似性2.1 数据类型_2.2 数据预处理2.3 数据的相似性习题 2.3数据的相似性第二章数据预处理与相似性数据挖掘任务需要计算数据对象之间的相似性或相异性，如聚类、最近邻分类、异常检 测等。相似度指两个对象相似程度的数据度量。相异度指两个对象差异程度的数值度量，距离可以作为相异度的同义词，两个数据所在的空间距离越大表示数据越相异 相似 性和相异性计算方法是一致的，通常是用两个对象之间的一个或多个属性距离来表示。数据对象之间的邻近度计算与数据对象属性类型密切相关。掌握简单属性之间的邻近度 是计算复杂对象之间邻近度的基础。本节分别以标称和数值类型属性介绍邻近性度量方 法。，2.3数据的相似性第二章数据预处理与相似性2.3.1 数值属性的相似性度量在一个空间下进行聚类或某些分类任务时，需要在该空间中找到一个距离测度，即给出该空间下任意两点之间的距离。距离测度是一个函数4%必，以空间中的两 个点作为参数，函数值是一个实数值，该函数必须满足下列准则：1.Dist（XM“（距离非负）2.当且仅当寸，Dist（4B=O3.Distp力Dist（/M（距离具有对称性）函数距离 准则4.Dist（%BwDist（%0+Dist（乙力（三角不等式），2.3数据的相似性第二章数据预处理与相似性2.3.1数值属性的相似性度量从直观上看，属于同一类的对象 在空间中应该互相靠近，而不同 类的对象之间的距离要大得多，因此可用距离来衡量对象之间的 相似程度。距离越小，对象间的 相似性就越大。常用的距离形式有：曼哈顿距离、欧几里得距离、切比雪夫距离、闵可夫斯基距离、杰卡德距离等。，2.3数据的相似性第二章数据预处理与相似性2.3.1数值属性的相似性度量1.曼哈顿距离(Manhattan Distance)两个点之间行进时必须要沿着网格 线前进，就如同沿着城市（如曼哈 顿）的街道行进一样。对于一个具 有正南正北、正东正西方向规则布 局的城市街道，从一点到达另一点 阻距离正是在南北方向上旅行阻距 离加上在东西方向上旅行的距离，是将多个维度上的距离进行求和的 结果。其距离公式：Dist(%,X2,/，%，为，笫)=一%i=l，2.3数据的相似性第二章数据预处理与相似性2.3.1数值属性的相似性度量2.欧几里得距离(Euclidean Distance)欧几里得距离也称欧氏距离，是最为熟 知的距离测度，也就是我们常说的距 离。在6维欧氏空间中，每个点是一个 力维实数向量，该空间中的传统距离测度 为为范式，定义如下：I mDist(XpX2?.9xm,ypy2,.,ym)-、，汇(七yz-)2V z=lEuclidean Distancey/(xi-x2y+(yi-?/2)2，2.3数据的相似性第二章数据预处理与相似性2.3.1数值属性的相似性度量3.切比雪夫距离：12,吧羽毛-WJ4.闵可夫斯基距离：(d s/pDist(|%i，X2,%，%)=Z3=1)5.杰卡德距昂：dsim（A,B）=d?d d 9，2.3数据的相似性第二章数据预处理与相似性2.3.2 标称属性的相似性度量 标称属性相似度计算就可通过编码方式转化为多个二元属性的相似度计算。一般地，二元属性相似度可以通过对属性匹配值求和来计算。即首先分别求解对 应单个属性间的相似度，然后对所有相似度数值进行直接累加：_ _ aSim(又,歹)二(%J)其中，d代表对象的属性总数。更为直接的理解，相似度可用取值相同 的同位属性数/属性总位数标识对于包含多个二元属性的数据对象相似 度计算。设有X=1,0,0,L0,0,L0,LI,Y=0,0,0,1,0,LLLL1,两个对象共有7 个属性取值相同，3个取值不同，那么相似度可以标识为3/10=0.3。2.3数据的相似性第二章数据预处理与相似性2.3.3 组合异种属性的相似性度量1.距离度量的标准化和相关性影响 因素值域不同量纲不同,测量单位不同，大小变化范围不 同属性相关性属性之间可能存在相关性、数据分布呈非均匀分布解决这些问题的方法是使用欧几里得距离的扩展马氏距离：歹）=（W F）工1（又一斤）T第二章数据预处理与相似性2.3.3组合异种属性的相似性度量1.组合异种属性的相似度现实当中从数据库取出的数据类型可能是标称、数值、二元、序数等数据类型的组合。这种组合 属性对象相似度最简单的方法是分别计算每个属性之间的相似度，然后取它们的平均值。对于取值非对称属性，分别计算相似度累加取均值方法失效。例如，两个对象的二元非对称属 性都取o值，并不能表示它们的相似性，可以在计算相似度时忽略，当二元非对称属性值为1时 才加入相似度计算。将第k个属性标准化到区间0国，计算相似度Sk(X,Y)创建一个指示变量bk,用来标示两个对象在第k个属性上是否同 时取值为0,如果同时为0,5k=0,否则bk=l。Sim(X,Y)=，2.3数据的相似性第二章数据预处理与相似性2.3.4文本相似性度量1.组合异种属性的相似度文档是由大量词语构成的，如果把特定词语出现的频率看作一个单独属性，那么文档可以由数千 个词频属性构成的向量表示。文档相似度需要关注两个文档同时出现的词语，以及这些词语出现 的次数，忽略零匹配的数值数据度量。余弦相似度，又称为余弦相似性，适合用来计算文档间的相似度。其原理是把两个文本文档以词 频向量表示，通过计算两个向量的夹角余弦值来评估他们的相似度。d二”cos(x,y)=XY不，2.3数据的相似性第二章数据预处理与相似性2.3.4文本相似性度量假设有两个文档,新闻满口新闻b,将它们的内容经过分词、词频统计处理后得到如下两个向量：文档a(L12LLL0Q0)文档b：(LLL0,L3,L6,l)。使用余弦相似度来计算两个文档的相似度过 程如下：新闻环口新闻。对应的向量分别是M国o)和)(%,为，Koo)(1)计算向量a优勺点积：/=lxl+lxl+2xl+lx0+lxl+lx3+0 xl+0 x6+0 xl=8(2)计算向量8、为勺欧几里得范数，即|同|、b:|Z?|二 V12+12+12+02+12+32+12+62+12=7.074=Vl2+12+22+12+12+12+02+02+02=3(3)计算相似度:cos（,。）=,0.377MxM2.3数据的相似性第二章数据预处理与相似性2.3.4文本相似性度量词频一逆文档频率(Term Frequency-Inverse Document Frequency,TF-IDF)是一种用于资讯检索与资讯探勘的常用加权技术。基于统计学方法来评估词语对文 档的重要性。字词的重要性随着它在文档中出现的次数成正比增加，但同时会随着 它在语料库中出现的频率成反比下降。TF卬文本X中词语.出现的次数 文本X中所有词语出现的次数 语料库的文档总数一 g包含该词的文档数+1TF-IDF=词频(TF)x逆文档频率(IDF)，2.3数据的相似性第二章数据预处理与相似性2.3.4文本相似性度量TF-IDF算法用来对文本进行特征提取，选出可以表征文章特性的关键词。假设文章灿。罕关键词的词频组成的向量表示，两篇文章“用勺相似度 可表亦为：).My)cos(x,y)=，2.3数据的相似性第二章数据预处理与相似性2.3.4文本相似性度量编辑距离编辑操作类型包括字符的替换、插入和删除，三种类型可以根据实际应用问题指定 相同或不同的操作代价。一般来说，编辑距离越小，两个串的相似度越大。Edit(z,y)=Edit(z-1,7-1)min(7(z-l,j)+wdel,Edit(i,j-l)+wins,Edit(z-l,j-l)+wrep)巧=匕M 刀习题:1.在数据挖掘之前为什么要对原始数据进行预处理？2.简述数据清理的基本内容。3.简述数据预处理的方法和内容。4.简述数据空缺值的处理方法。5.数据约简的方法有哪些？6.什么是数据规范化？规范化的常用方法有哪些？写出对应的变换 公式。7.计算数据对象X=(3,5,2,7)和Y=(6,8,2,3)之间的欧几里得距离、曼哈顿距离以及闵可夫斯基距离，其中闵可夫斯基距离中p值取为3。8.分析编辑距离与最长公共子序列这两个算法的异同。感谢聆听