《第2章数据.ppt》由会员分享，可在线阅读，更多相关《第2章数据.ppt（77页珍藏版）》请在三一文库上搜索。
1、数据挖掘: 数据,第2章 数据,什么是数据?,数据集可以看作数据对象的集合。数据对象用一组刻画对象基本特性的属性描述 数据对象 记录、点、向量、模式、事件、案例、样本、观测、实体. 属性 变量、特性、字段、特征、维,Attributes,Objects,属性与属性值,属性的性质不必与度量它的属性值的性质相同，反之亦然 相同的属性可能有不同的属性值 例子: 高度可以用米或英尺来表示 不同的属性可能映射到相同的值的集合 例子: 雇员ID and 年龄 都用整型表示 然而，谈论平均年龄是有意义的，平均ID是无意义的 ID和年龄最大值不同,例 线段长度,知道属性的类型是重要的 它告诉我们测量值的哪些性
2、质与属性的基本性质一致，从而使我们可以避免一些愚蠢的行为。如：计算雇员的平均ID,属性的不同类型,四种属性类型 分类的（定性的） 标称 举例: 雇员id、眼球颜色、性别 序数 举例：矿石硬度、好，较好，最好 数值的（定量的） 区间 举例：日历日期、摄氏、华氏温度 比率 举例：绝对温度、货币量、计数、年龄、质量、长度、电流,离散和连续属性,离散属性 具有有限或无限可数个值 例子: ID号、计数、字母数 经常用整数表示. 一种特殊的离散属性：二元属性 连续属性 是取实数值的属性 例子: 温度、高度、重量. 连续属性用浮点变量表示. 实际上、实数值只能用有限的精度测量和表示.,2.1 数据集的类型,
3、记录数据 数据矩阵（Data Matrix） 文档词矩阵（Document term Data） 事物数据（Transaction Data） 图 带有对象之间联系的数据 具有图形对象的数据 有序数据 空间数据（Spatial Data） 时间数据（Temporal Data） 时间序列数据（Time Series Data） 序列数据（Sequence Data）,数据集的一般特性,维度(dimensionality) 数据集中的对象具有的属性个数 维灾难 维归约 稀疏性(sparsity) 具有非对称特征的数据集，一个对象大部分属性值为0，非零项一般不到1% 分辨率(resolution)
4、 不同的分辨率下数据的性质不同,记录数据,记录（数据对象）的汇集，每个记录包含固定的数据字段（属性）集,数据矩阵,如果一个数据集族中的所有数据对象都具有相同的数值属性集，则数据对象可以看作多维空间的点（向量），其中每一维代表描述对象的一个不同属性。 数据对象集可用mn的矩阵表示 它是记录数据的变体，它由数值属性组成，可以使用矩阵操作对数据进行变换和操作,稀疏数据矩阵,特殊的数据矩阵, 只有非零值是重要的, 例子：文档-词矩阵,事务数据,每个记录（事务）涉及一个项的集合. 例子：一个杂货店。顾客一次购买的商品的集合就构成一个事务，而购买的商品是项.这种类型的数据称作购物篮数据,基于图形的数据,带
5、有对象之间联系的数据,具有图形对象的数据,苯分子: C6H6,有序数据,时序数据 例子：时序事务数据,有序数据,时间序列数据,有序数据,序列数据 例子：基因组序列数据,有序数据,空间数据 例子：温度数据,数据质量,现实世界的数据是“肮脏的”数据多了，什么问题都会出现 不完整的：有些感兴趣的属性缺少属性值，或仅包含聚集数据 含噪声的：包含错误或者“孤立点” 不一致的：在编码或者命名上存在差异 没有高质量的数据，就没有高质量的挖掘结果 高质量的决策必须依赖高质量的数据 数据仓库需要对高质量的数据进行一致地集成,2.2数据质量,数据质量问题的例子: 噪声（Noise） 离群点（outliers ）
6、遗漏值（missing values ） 重复数据（ duplicate data ）,噪声,噪声是测量误差的随机部分 Examples: distortion of a persons voice when talking on a poor phone and “snow” on television screen,Two Sine Waves,Two Sine Waves + Noise,离群点,噪声和离群点的区别 离群点可以是合法的数据对象或值，不像噪声，离群点本身可以是令人感兴趣的 例子：欺诈和网络攻击检测中，目标就是从大量正常对象或事件中发现不 正常的对象和事件,遗漏值,原因 信息
7、未收集 (例如：有的人拒绝提供年龄和体重) 属性并不能用于所有对象 (例如：填写学历后，填写专业，研究方向) 处理遗漏值 删除数据对象或属性 估计遗漏值 在分析时忽略遗漏值,如何处理遗漏（缺失）值,忽略元组：当类标号缺少时通常这么做（假定挖掘任务涉及分类或描述），当每个属性缺少值的百分比变化很大时，它的效果非常差。 人工填写空缺值：工作量大，可行性低 使用一个全局变量填充空缺值：比如使用unknown或- 使用属性的平均值填充空缺值 使用与给定元组属同一类的所有样本的平均值,重复数据,数据集可能包含重复或几乎重复的数据对象 例子:许多人收到重复的邮件,2.3数据预处理,聚集 抽样 维归约 特征
8、子集选择 特征创建 离散化和二元化 变量变换,聚集,将两个或多个对象合并成单个对象 目的 数据归约 使数据集规模减少，从而耗时较多的数据挖掘算法更可行 尺度变换 建立高层数据视图。城市聚集成地区、省、国家 数据性质更加稳定 平均值、总数等聚集量具有更小的变异性,聚集,动机 1.数据归约导致的较小数据集需要较少的内存和处理时间，因此可以使用花费更大的数据挖掘算法。 2.通过高层而不是低层数据视图，聚集起到了辖域或标度转换的作用。 3.对象或属性群的性质通常比单个对象或属性的性质更加稳定,聚集,Standard Deviation of Average Monthly Precipitation,
9、Standard Deviation of Average Yearly Precipitation,例2.7 澳大利亚降水量 该例基于从1982年到1993年的降水量。左图显示澳大利亚3030个0.5度乘0.5度（经纬度）的网格单元上的平均月降水量的标准差。右图为相同位置的平均年降水量的标准差。,抽样,抽样是一种选择数据对象子集进行分析的常用方法 抽样长期用于数据的事先调查和最终的数据分析. 在统计学和数据挖掘中，抽样的动机并不相同. 统计学使用抽样是因为获得感兴趣的整个数据集的费用太高、太费时间 数据挖掘使用抽样是因为处理所有的数据的费用太高、太费时间,抽样 ,有效抽样（样本有代表性）:
10、使用抽样样本与使用整个数据集的效果几乎一样 如果它近似地具有与原数据集相同（感兴趣）的性质。 例子：如果感兴趣的数据对象是均值，而抽样样本具有近似于原数据集的均值，则样本是有代表性的,抽样方法,简单随机抽样 无放回抽样 有放回抽样 当样本与数据集相比相对较小时，两种方法产生的样本差别不大，有放回抽样较为简单 分层抽样 每种类型的对象数量差别很大时，简单随机抽样不能充分地代表不太频繁出现的对象类型。 先分组，然后对每组抽样。可以使每组抽样个数相同或从每组中抽取的对象数量正比于该组的大小,抽样SRS,SRSWOR (简单随机抽 样，不回放),SRSWR (简单随机抽 样，回放),分层抽样,原始数据
11、,聚类/分层选样,抽样与信息损失,8000 points 2000 Points 500 Points,较大的样本容量增大了样本具有代表性的概率， 但也抵消了抽样带来的许多好处。反过来，使 用较小容量的样本，可能丢失模式，或检测到错误的模式。,抽样尺寸,抽样尺寸选为多少？才能保证从每组中找出一个代表点.,维归约,目的: 减少数据挖掘算法运行的时间和空间 数据更容易可视化 删除不相关特征、降低噪音,维归约,通过删除不相干的属性或维减少数据量 属性子集选择 找出最小属性集，使得数据类的概率分布尽可能的接近使用所有属性的原分布 减少出现在发现模式上的属性的数目，使得模式更易于理解 技术 主成分分析（
12、Principle Component Analysis）,特征创建,由原来的属性创建新的属性集，更有效地捕获数据集中的重要信息 三个一般的方法: 特征提取 映射数据到新的空间 特征构造,特征提取,映射数据到新的空间,Two Sine Waves,Two Sine Waves + Noise,Frequency,傅立叶变换：把时间序列转化为频率信息 小波变换,特征构造,有时，原始数据集的特征具有必要的信息，但其形式不适合数据挖掘算法。在这种情况下，一个或多个由原特征构造的新特征可能比原特征更有用 例子：每个人工制品由体积、质量和其它信息构成。假定这些人工制品使用少量材料（木材、陶土、青铜、黄金
13、）制造，并且我们希望根据制造材料对它们分类。 密度=质量/体积将很直接地产生准确的分类。 尽管有一些努力，试图通过考察已有特征的简单的数学组合来自动的进行特征构造，但是最常见的方法还是使用专家的意见构造特征,离散化和二元化,分类属性二元化 如果有m个分类值，则将每个原始值唯一地赋予区间0,m-1中的一个整数。 如果属性是有序的，则赋值必须保持序关系 然后，将这m个整数的每一个都变换成一个二进制数。需要使用 个二进位表示这些整数 例：一个具有5个值awful,poor,ok,good,great的分类变量需要三个二元变量表示。,上面的变换可能导致复杂化，如无意中建立了转化后的属性之间的联系。 关
14、联分析可能认为x2和x3是相关的，因为good值使用这两个属性值表示 对于关联分析，需要为每个分类值引入一个二元属性,连续属性离散化,连续属性变为分类属性 将连续属性值排序后，通过指定n-1个分割点把他们分成n个区间 将一个区间中的所有值映射到相同的分类 例：对x=2.1，2.4，3，3.5，4， 3.2离散化为三个分类值 2.1，2.4，3，3.2，3.8，4 设定区间(-,2.7,(2.7,3.5,(3.5, + ) 离散化为0，0，1，1，2，2,非监督离散化,数据,等宽离散化,等频率离散化,k均值离散化,等宽 这种方法将属性的值域划分成具有相同宽度的区间 这种方法可能受离群点的影响而性
15、能不佳 等频率 这种方法将相同数量的对象放进每个区域 K均值聚类,监督离散化,带有类标号的数据离散化 基于熵的离散化 熵的计算公式 Mi是第i个区间中值的个数 Mij是第i个区间中类j的值的个数 将初始值切分成两部分，使得两个结果区间产生最小熵。然后，取一个最大熵的区间，重复分割过程，直到区间的个数达到用户指定的个数,变量变换,是指用于变量的所有值的变换 简单函数: xk, log(x), ex, |x|,1/x,sinx 规范化和标准化 规范化和标准化 比较两个人的不同：因为年龄之差一般远小于收入之差，因此如果不对数据标准化，将导致收入之差将主导人的不同 标准差方法： 均值和标准差受离群点影
16、响大， 可用中位点和绝对标准差代替,2.4 相似性和相异性的度量,相似度 两个对象之间的相似度是这两个对象相似程度的数值度量. 两个对象越相似，它们的相似度就越高 相似度是非负的，并常常在0和1之间取值 相异度 两个对象之间的相异度是这两个对象差异程度的数值度量 对象越相似，他们的相异度就越低 距离常作相异度的同义词 取值(0,1)或(0, ),变量变换用于相似度与相异度,例：如果对象之间的相似度在1（一点也不相似）和10（完全相似）之间变化，则我们可以使用如下变换将它变换到0, 1区间：s = (s - 1)/9，其中s和s分别是相似度的原值和新值。 在更一般的情况下，相似度到0, 1区间的
17、变换由如下表达式给出：s = (s - min_s) / (max_s - min_s)，其中max_s和min_s分别是相似度的最大值和最小值。类似地，具有有限值域的相异度也能用d = (d - min_d) / (max_d - min_d) 映射到0, 1区间。,相似度与相异度互换 对于变换s = 1/（d + 1），相异度0, 1, 10, 100分别 变换到1, 0.5, 0.09, 0.01； 对于s = 它们分别被变换到1.00, 0.37, 0.00, 0.00； 对于s =1- 它们分别被变换到1.00, 0.99, 0.00, 0.00。,简单属性之间的相似度和相异度,p
18、and q are the attribute values for two data objects.,数据对象之间的相异度,Euclidean Distance,明可夫斯基距离（Minkowski Distance）,Minkowski Distance r = 1. 城市块 (曼哈顿, 出租车, L1 范数) 距离. r = 2. 欧氏距离（ L2 范数） r . 上确界 (Lmax或L 范数) 距离.,Minkowski Distance,Distance Matrix,距离的性质,距离具有一些众所周知的性质. 非负性 d(x，y) 0，仅当x = y时d(x, y) = 0 对称性
19、d(x，y) = d(y，x) 三角不等式 d(x，z) d(x，y) + d(y，z) 满足以上三个性质的测度称为度量（metric）(距离),例2.14 非度量的相异度：集合差 这个例子是基于集合论中定义的两个集合差的概念，设有两个集合A和B，A - B是不在B中的A中元素的集合。 例如，如果A = 1, 2, 3, 4，而B = 2, 3, 4，则A - B = 1，而B - A = ，即空集。我们可以将两个集合A和B之间的距离定义为d(A, B) = size(A - B)，其中size是一个函数，它返回集合元素的个数。该距离测度是大于或等于零的整数值，但不对称性，同时还不满足三角不等
20、式。然而，如果将相异度修改为d(A, B) = size(A - B) + size(B - A)，则这些性质都可以成立,二元数据的相似性度量,两个仅包含二元属性的对象之间的相似性度量也称相似系数 两个对象的比较导致四个量 f00 = x取0并且y取0的属性个数 f01 = x取0并且y取1的属性个数 f10 = x取1并且y取0的属性个数 f11 = x取1并且y取1的属性个数 简单匹配系数 SMC = 值匹配的属性个数 / 属性个数 = (f11 +f00) / (f01 + f10 + f11 + f00) Jaccard(雅卡尔 ) 系数 （非对称二元属性） J = 匹配的个数 / 不
21、涉及0-0匹配的属性个数= (f11) / (f01 + f10 +f11),SMC vs Jaccard: 例子,x = 1 0 0 0 0 0 0 0 0 0 y = 0 0 0 0 0 0 1 0 0 1 f00 = 7 f01 = 2 f10 = 1 f11 = 0 SMC = (f11 + f00)/(f01 + f10 + f11 + f00) = (0+7) / (2+1+0+7) = 0.7 J = (f11) / (f01 + f10 + f11) = 0 / (2 + 1 + 0) = 0,余弦相似度,文档用向量表示，向量的每个属性代表一个特定的词（术语）在文档中出现的频率
22、。当然，实际情况要复杂得多，因为需要忽略常用词，并使用各种技术处理同一个词的不同形式、不同的文档长度以及不同的词频。 尽管文档具有数以百千计或数以万计的属性（词），但是每个文档都是稀疏的，因此，文档的相似性度量不仅应当像Jaccard度量一样需要忽略0-0匹配，而且还必须能够处理非二元向量。,余弦相似度,If d1 and d2 are two document vectors, then cos( x, y ) = (x y) / |x| |y| , Example: x = 3 2 0 5 0 0 0 2 0 0 y = 1 0 0 0 0 0 0 1 0 2 x y= 3*1 + 2*0
23、 + 0*0 + 5*0 + 0*0 + 0*0 + 0*0 + 2*1 + 0*0 + 0*2 = 5 |x| = (3*3+2*2+0*0+5*5+0*0+0*0+0*0+2*2+0*0+0*0)0.5 = (42) 0.5 = 6.481 |y| = (1*1+0*0+0*0+0*0+0*0+0*0+0*0+1*1+0*0+2*2) 0.5 = (6) 0.5 = 2.245 cos( d1, d2 ) = 0.3150,广义Jaccard系数 (Tanimoto谷本贵义-系数),相关性,两个具有二元变量或连续变量的数据对象之间的相关性是对象属性之间线性联系的度量。,相关性,皮尔逊相关系
24、数：两个具有二元变量或连续变量的数据对象之间的相关性是对象属性之间线性联系的度量。,相关性,例2.19 完全相关 相关度总是在-1到1之间取值。相关度为1（-1）意味x和y具有完全正（负）线性关系，即x = ay + b，其中a和b是常数。计算下面两个x和y的相关度。 x = (-3, 6, 0, 3, -6) y = (1, -2, 0, -1, 2) x = (3, 6, 0, 3, 6) y = (1, 2, 0, 1, 2),相关性可视化,两个数据对象x和y之间的相关性。X和y具有30个属性这些属性的值随机地产生。每个小圆圈代表30个属性中的一个.,马氏距离（Mahalanobis D
25、istance）,For red points, the Euclidean distance is 14.7, Mahalanobis distance is 6.,当属性值域不同，且某些属性之间还相关时，数据分布近似于高斯分布时，可以用马氏距离,Mahalanobis Distance,Covariance Matrix:,B,A,C,A: (0.5, 0.5) B: (0, 1) C: (1.5, 1.5) Mahal(A,B) = 5 Mahal(A,C) = 4,组合异种属性的相似度,当属性具有不同类型时，可以使用如下算法.,算法2.1 异种对象的相似度 1：对于第k个属性，计算相似度sk(x, y)，在区间0, 1中。 2：对于第k个属性，定义一个指示变量 ，如下： = 0，如果第k个属性是非对称属性，并且两个对象在该属性上的值都是0，或者如果一个对象的第k个属性具有遗漏值 = 1，否则 3：使用如下公式计算两个对象之间的总相似度： similarity (x, y) =,使用权值,当某些属性对邻近度的定义比其他属性更重要时，可以通过对每个属性的贡献加权来修改邻近度公式.,