第06章数据(A)资料课件

数据仓库与数据挖掘数据仓库与数据挖掘第第0606章章 数据数据第第6 6章章 数据数据n n数据类型数据类型数据类型数据类型n n数据质量数据质量数据质量数据质量n n数据预处理数据预处理数据预处理数据预处理n n相似性和相异性的度量相似性和相异性的度量相似性和相异性的度量相似性和相异性的度量2何为数据？何为数据？数据对象及其属性的集合数据对象及其属性的集合属性是一个对象的性属性是一个对象的性质质或特征或特征n例子：一个人的眼睛的颜色、例子：一个人的眼睛的颜色、温度、等。温度、等。n属性也被称为变量、字段、属性也被称为变量、字段、特性或特征特性或特征属性的集合描述一个对象属性的集合描述一个对象n对象也被称为记录、点、对象也被称为记录、点、事事件件、样本、实体或实例、样本、实体或实例AttributesObjects3属性值属性值属性值是分配给属性的属性值是分配给属性的数字数字或或符号符号属性和属性值之间的区别属性和属性值之间的区别n相同的属性可以映射到不同的相同的属性可以映射到不同的值域值域n例如：高度可以用英尺或米来测量例如：高度可以用英尺或米来测量n不同的属性可以映射到相同的值不同的属性可以映射到相同的值域域n例：身份证和年龄的属性值是整数例：身份证和年龄的属性值是整数n身份证没有限制，但年龄有一个最大值和最小值身份证没有限制，但年龄有一个最大值和最小值4长度的度量长度的度量 不同不同的方式衡量的属性是有可能不匹配的属性的方式衡量的属性是有可能不匹配的属性5属性的类型属性的类型 有不同类型的属性有不同类型的属性nNominal（标称）（标称）n例子：身份号码，眼睛颜色，邮政编码例子：身份号码，眼睛颜色，邮政编码nOrdinal（序数）（序数）n例子：排名（例如，口味薯片上的范围从例子：排名（例如，口味薯片上的范围从1-10），等级，在），等级，在高，高，中等身高，短中等身高，短nInterval（区间）（区间）n例如：日历日期，摄氏度或华氏度的温度例如：日历日期，摄氏度或华氏度的温度nRatio（比例（比例)n例子：在开尔文温度、长度、时间、计数例子：在开尔文温度、长度、时间、计数 6属性值的性质属性值的性质属性的类型取决于下列它操作属性的类型取决于下列它操作(拥有拥有)的性质的性质:n相异性相异性:=n序序:n加法加法:+-n乘法乘法:*/n标称属性标称属性:相异性相异性n序数属性序数属性:相异性相异性&序序n区间属性区间属性:相异性相异性,序序&加法加法n比率属性比率属性:所有所有 4 种性质种性质7属性值的性质属性值的性质8属性值的性质属性值的性质9离散和连续属性离散和连续属性离散属性离散属性n具有有限或无限可数个值具有有限或无限可数个值n例如：邮政编码例如：邮政编码,计数计数,文档集合中的单词集合文档集合中的单词集合 n常用整数变量表示常用整数变量表示.n注意：二元属性是离散属性的一种特殊情况注意：二元属性是离散属性的一种特殊情况连续属性连续属性n属性值取实数属性值取实数n例如：温度例如：温度,高度高度,重量重量.n实践中实践中,实数值只能用有限的精度测量和表示实数值只能用有限的精度测量和表示.n连续属性用浮点变量表示连续属性用浮点变量表示.10数据集的类型数据集的类型记录数据记录数据n数据矩阵数据矩阵n文档数据文档数据n事务数据事务数据基于图形的数据基于图形的数据nWorld Wide Webn分子结构分子结构有序的数据有序的数据n空间数据空间数据n时间数据时间数据n时序数据时序数据n基因序列数据基因序列数据11结构数据的重要特征结构数据的重要特征n维度维度n 维灾难维灾难n稀疏性稀疏性n 仅存在计数仅存在计数n分辨率分辨率n 模式依赖范围和规模模式依赖范围和规模 12记录数据记录数据数据是记录的集合数据是记录的集合,每个记录包含固定的数据字段每个记录包含固定的数据字段(属性属性)集集 13数据矩阵数据矩阵 如果所有数据对象都有相同的数值属性值如果所有数据对象都有相同的数值属性值,则数据对象可以看则数据对象可以看作是多维空间中的点作是多维空间中的点,其中每个维代表一个不同的属性其中每个维代表一个不同的属性这些数据可以用一个这些数据可以用一个 mn 的矩阵表示的矩阵表示,其中其中 m 行行,一个对一个对象一行象一行;n 列列,一个属性一列一个属性一列14文档数据文档数据每个文档用一个每个文档用一个“词词”向量表示向量表示,n每个词是向量的一个分量每个词是向量的一个分量(属性属性),n每个分量的值是对应词在文档中出现的次数每个分量的值是对应词在文档中出现的次数.15事务数据事务数据一种特殊类型的记录数据一种特殊类型的记录数据,其中其中 n每个记录每个记录(事务事务)包含一个项的集合包含一个项的集合.n例如例如,在一家杂货店在一家杂货店.顾客在一次购物中购买商品的集合构成一个事务顾客在一次购物中购买商品的集合构成一个事务,购买的商品就是项购买的商品就是项.16图数据图数据 例如例如:基因图和基因图和HTML链接链接 17化学数据化学数据 苯分子苯分子:C6H618有序数据有序数据 事务序列事务序列An element of the sequenceItems/Events19有序数据有序数据 基因组序列数据基因组序列数据20有序数据有序数据有序数据有序数据时空数据时空数据Average Monthly Temperature of land and ocean21数据质量数据质量 存在哪些数据质量问题存在哪些数据质量问题?如何检测数据问题如何检测数据问题?针对这些数据我们能做什么针对这些数据我们能做什么?数据质量问题的例子数据质量问题的例子 n噪声和孤立点噪声和孤立点 n缺失值缺失值 n重复数据重复数据 22噪声噪声噪声是指对原始值的修改噪声是指对原始值的修改n例如例如:在一部糟糕的电话机上通话的失真在一部糟糕的电话机上通话的失真;电视屏幕上的电视屏幕上的“雪花雪花”两个正弦波两个正弦波两个正弦波两个正弦波+噪声噪声23孤立点孤立点孤立点的特点是与数据集中的其它大部分数据对象差异非常大孤立点的特点是与数据集中的其它大部分数据对象差异非常大24缺失值缺失值缺失值的原因缺失值的原因n信息未收集信息未收集(例例,顾客拒绝提供自己的年龄和体重顾客拒绝提供自己的年龄和体重)n属性没有应用到所有案例中属性没有应用到所有案例中(例例,年收入属性不适用于儿童年收入属性不适用于儿童)处理缺失值处理缺失值n消除数据对象消除数据对象n估计缺失值估计缺失值n分析时忽略掉缺失值分析时忽略掉缺失值n用可能值替换用可能值替换(根据概率确定权重根据概率确定权重)25重复数据重复数据数据集可能包含重复或几乎重复的对象数据集可能包含重复或几乎重复的对象n从异构数据源中合并数据时的主要问题从异构数据源中合并数据时的主要问题例如例如:n同一人拥有多个同一人拥有多个email信箱信箱数据清洗数据清洗n处理有重复数据的问题处理有重复数据的问题26精度、偏倚和准确率精度、偏倚和准确率n精度精度：（同一个量的）重复测量值之间的接近程度：（同一个量的）重复测量值之间的接近程度n偏倚：测量值与被测量之间的系统的变差偏倚：测量值与被测量之间的系统的变差n准确率：被测量的测量值与实际值之间的接近度准确率：被测量的测量值与实际值之间的接近度27数据预处理数据预处理聚集聚集抽样抽样维规约维规约特征子集选择特征子集选择特征创建特征创建离散化和二元化离散化和二元化属性变换属性变换28聚集聚集将两个或更多的属性将两个或更多的属性(或对象或对象)合并为一个属性合并为一个属性(或对象或对象)目的目的:n数据规约数据规约n 减少属性或对象的数量减少属性或对象的数量n改变辖域改变辖域n 城市聚集到地区城市聚集到地区,州州,国家等国家等n更更“稳定稳定”的数据的数据n 聚集数据有较小的变异性聚集数据有较小的变异性缺点缺点:n可能丢失有趣的细节可能丢失有趣的细节n 如最高销售额如最高销售额29聚集聚集澳大利亚的降水变化澳大利亚的降水变化月均降水的标准差月均降水的标准差年均降水的标准差年均降水的标准差30抽样抽样 抽样是选择数据的主要技术抽样是选择数据的主要技术n常用于数据的事先调查和最终的数据分析常用于数据的事先调查和最终的数据分析n获得感兴趣的整个数据集的成本太高、太费时间获得感兴趣的整个数据集的成本太高、太费时间n处理整个数据集的成本太高、太费时间处理整个数据集的成本太高、太费时间有效抽样的主要原理如下有效抽样的主要原理如下:n如果样本有代表性如果样本有代表性,使用样本与使用整个数据集的效果几乎一样使用样本与使用整个数据集的效果几乎一样n一个样本是有代表性的一个样本是有代表性的,如果它近似地具有与原数据集相同的如果它近似地具有与原数据集相同的(感兴趣感兴趣的的)性质性质31抽样的方法抽样的方法简单随机抽样简单随机抽样n选取任何特定项的概率相等选取任何特定项的概率相等无放回抽样无放回抽样n随着每个项被抽中，随着每个项被抽中，它被从构成总体的所有对象集中删除它被从构成总体的所有对象集中删除有放回抽样有放回抽样n对象被选中时不从总体中删除对象被选中时不从总体中删除 n在有放回抽样中，相同的对象可能被多次抽出在有放回抽样中，相同的对象可能被多次抽出分层抽样分层抽样n将数据划分为几个部分；将数据划分为几个部分；然后从每个部分中随机抽取样本然后从每个部分中随机抽取样本32样本容量样本容量 8000 points 2000 Points 500 Points33样本大小样本大小需要多大的样本数才能从需要多大的样本数才能从10组中的每一组得到至少一个代表对组中的每一组得到至少一个代表对象象.34维灾难维灾难n n随着维度的增加随着维度的增加随着维度的增加随着维度的增加,数据在数据在数据在数据在所占据的空间中越来越稀所占据的空间中越来越稀所占据的空间中越来越稀所占据的空间中越来越稀疏疏疏疏n n对于聚类和孤立点检测对于聚类和孤立点检测对于聚类和孤立点检测对于聚类和孤立点检测,点的密度和距离的定义点的密度和距离的定义点的密度和距离的定义点的密度和距离的定义(对聚类至关重要对聚类至关重要对聚类至关重要对聚类至关重要)变得不变得不变得不变得不太有意义了太有意义了太有意义了太有意义了随机生成随机生成 500 个点个点在任意点对中计算它们最在任意点对中计算它们最大大和最小的距离的差异和最小的距离的差异35维规约维规约目的目的:n避免维灾难避免维灾难n降低数据挖掘算法的时间和内存消耗降低数据挖掘算法的时间和内存消耗n使数据更容易可视化使数据更容易可视化n能删除不相关的特征并降低噪声能删除不相关的特征并降低噪声技术技术n主成分分析主成分分析n奇异值分解奇异值分解n其它：监督和非线性技术其它：监督和非线性技术36维规约维规约:PCA:PCAn主成分分析主成分分析(PCA)目标是找目标是找到一个投影来捕获数据中最到一个投影来捕获数据中最大的变化量大的变化量n找出协方差矩阵的特征向量找出协方差矩阵的特征向量n特征向量定义新的空间特征向量定义新的空间n线性线性x2x1e37维规约维规约:ISOMAP:ISOMAPn构建一个相邻图构建一个相邻图n计算图中的每一点对的最短计算图中的每一点对的最短路径距离路径距离 测地距离测地距离n非线性非线性By:Tenenbaum,de Silva,Langford(2000)38特征子集选择特征子集选择降低维度的另一种方法降低维度的另一种方法冗余特征冗余特征 n重复了包含在一个或多个其它属性中的许多或所有信息重复了包含在一个或多个其它属性中的许多或所有信息n例如：例如：一种产品的购买价格和所支付的销售税额包含许多相同的信息一种产品的购买价格和所支付的销售税额包含许多相同的信息不相关特征不相关特征n包含对于手头的数据挖掘任务几乎完全没用的信息包含对于手头的数据挖掘任务几乎完全没用的信息n例如：例如：学生的学生的 ID 号码对于预测学生的总平均成绩号码对于预测学生的总平均成绩(GPA)是不相关的是不相关的39特征子集选择特征子集选择技术技术:n蛮力方法蛮力方法:n将所有可能的特征子集作为数据挖掘算法的输入将所有可能的特征子集作为数据挖掘算法的输入n嵌入方法嵌入方法:n 特征子集作为数据挖掘算法的一部分自然地出现特征子集作为数据挖掘算法的一部分自然地出现n过滤方法过滤方法:n 在数据挖掘算法运行前进行特征选择在数据挖掘算法运行前进行特征选择n包装方法包装方法:n 将数据挖掘算法作为黑盒找出最佳属性子集将数据挖掘算法作为黑盒找出最佳属性子集40特征子集选择体系架构特征子集选择体系架构属性搜索策略属性子集评估停止标准选择的属性验证过程不满足满足41特征创建特征创建创建新的属性集能比原有属性更有效地捕获数据创建新的属性集能比原有属性更有效地捕获数据集中的重要信息集中的重要信息三种通用方法三种通用方法:n特征提取特征提取n 特定领域需要特定的提取方法特定领域需要特定的提取方法,如图像处理如图像处理n映射数据到新的空间映射数据到新的空间n特征构造特征构造n 合并特征合并特征 42映射数据到新的空间映射数据到新的空间两个正弦波两个正弦波+噪声频率l傅立叶变换l小波变换 43使用类标号离散化使用类标号离散化基于熵的方法基于熵的方法 x 和 y 都分为3个区间 x 和 y 都分为5个区间44不使用类标号的离散化不使用类标号的离散化数据等宽离散化等频率离散化K均值离散化45属性变换属性变换通过一个函数映射某个给定的属性值的集合到一个新的替代通过一个函数映射某个给定的属性值的集合到一个新的替代值的集合值的集合,使得每一个旧值可以用一个新的值来识别使得每一个旧值可以用一个新的值来识别n简单函数简单函数:xk,log(x),ex,|x|n标准化和规范化标准化和规范化 n如：年龄与收入如：年龄与收入46相似度和相异度相似度和相异度相似度相似度n是两个对象相似程度的数值度量是两个对象相似程度的数值度量.n两个对象越相似两个对象越相似,它们的相似度越高它们的相似度越高.n在在 0,1 区间取值区间取值相异度相异度n是两个对象差异程度的数值度量是两个对象差异程度的数值度量n两个对象越相似两个对象越相似,它们的相异度越低它们的相异度越低n最小相异度为最小相异度为 0n上限不同上限不同近似是指相似或相异近似是指相似或相异47简单属性之间的相似度简单属性之间的相似度简单属性之间的相似度简单属性之间的相似度/相异度相异度相异度相异度p 和和 q 两个数据对象的属性值两个数据对象的属性值.属性类型相异度相似度标称序数区间和比率48欧几里德距离欧几里德距离欧几里德距离欧几里德距离n n n 是维数是维数,pk 和和 qk 分别是数据对象分别是数据对象 p 和和 q 的第的第k个属性个属性(分量分量).标准化是必须的，如果度量尺度不同的话标准化是必须的，如果度量尺度不同的话.49欧几里德距离欧几里德距离距离矩阵50明可夫斯基距离明可夫斯基距离明可夫斯基距离是欧氏距离的泛化明可夫斯基距离是欧氏距离的泛化 n r 是参数是参数,n 是维数是维数,pk 和和 qk 分别是数据对象分别是数据对象 p 和和 q 的第的第k个属性个属性(分量分量).51明可夫斯基距离明可夫斯基距离:范例范例r=1.城市块城市块(曼哈顿曼哈顿,出租车出租车,L1 范数范数)距离距离.n一个常见的例子是汉明距离一个常见的例子是汉明距离,它是两个二元向量之间不同的二进位个数它是两个二元向量之间不同的二进位个数r=2.欧氏距离欧氏距离r .“上确界上确界”(Lmax 范数范数,L 范数范数)距离距离.n这是向量这是向量(属性属性)的任何分量之间的最大距离的任何分量之间的最大距离不要将参数不要将参数 r 与维数与维数(属性数属性数)n 混淆混淆,所有这些距离都是对维数所有这些距离都是对维数 n 定义的定义的.52明可夫斯基距离明可夫斯基距离距离矩阵53马氏距离马氏距离马氏距离马氏距离图中红点,欧氏距离为 14.7,马氏距离为 6.是输入数据 X 的协方差矩阵54马氏距离马氏距离协方差矩阵协方差矩阵:BACA:(0.5,0.5)B:(0,1)C:(1.5,1.5)Mahal(A,B)=5Mahal(A,C)=4 55距离的一些普通性质距离的一些普通性质距离距离,如欧氏距离如欧氏距离,有一些众所周知的属性有一些众所周知的属性.n非负性非负性：d(p,q)0 for all p and q and d(p,q)=0 only if p=q.n对称性对称性：d(p,q)=d(q,p)for all p and q.n三角不等式三角不等式：d(p,r)d(p,q)+d(q,r)for all points p,q,and r.其中其中 d(p,q)是数据点是数据点 p 和和 q 的距离的距离(相异度相异度).满足这些性质的距离称为满足这些性质的距离称为度量度量56距离的一些普通性质距离的一些普通性质相似度相似度,也有一些众所周知的性质也有一些众所周知的性质.ns(p,q)=1(or maximum similarity)only if p=q.ns(p,q)=s(q,p)for all p and q.(对称性对称性)其中其中 s(p,q)是数据点是数据点 p 和和 q 的相似度的相似度.57二元向量的相似度二元向量的相似度p 和和 q 是两个对象是两个对象,仅有二元属性。用下面的量计算相似度仅有二元属性。用下面的量计算相似度nM00=p 取取 0 且且 q 取取 0 的属性个数的属性个数n M01=p 取取 0 且且 q 取取 1 的属性个数的属性个数nM10=p 取取 1 且且 q 取取 0 的属性个数的属性个数nM11=p 取取 1 且且 q 取取 1 的属性个数的属性个数简单匹配系数简单匹配系数SMC和和 Jaccard 系数系数 SMC=值匹配数值匹配数/属性数属性数 =(M11+M00)/(M01+M10+M11+M00)J=匹配数匹配数/不涉及不涉及 0-0 匹配的属性个数匹配的属性个数 =(M11)/(M01+M10+M11)58SMC SMC 对比对比 Jaccard:Jaccard:范例范例p=1 0 0 0 0 0 0 0 0 0 q=0 0 0 0 0 0 1 0 0 1 M01=2 (the number of attributes where p was 0 and q was 1)M10=1 (the number of attributes where p was 1 and q was 0)M00=7 (the number of attributes where p was 0 and q was 0)M11=0 (the number of attributes where p was 1 and q was 1)SMC=(M11+M00)/(M01+M10+M11+M00)=(0+7)/(2+1+0+7)=0.7 J=(M11)/(M01+M10+M11)=0/(2+1+0)=0 59余弦相似度余弦相似度 如果如果 d1 和和 d2 是两个文档向量是两个文档向量,则则 cos(d1,d2)=(d1 d2)/|d1|d2|,其中其中 表示向量点积表示向量点积,|d|是向量是向量 d 的长度的长度.例子例子:d1=3 2 0 5 0 0 0 2 0 0 d2=1 0 0 0 0 0 0 1 0 2 d1 d2=3*1+2*0+0*0+5*0+0*0+0*0+0*0+2*1+0*0+0*2=5|d1|=(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|d2|=(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.315060广义广义 Jaccard Jaccard 系数系数(Tanimoto (Tanimoto 系数系数)广义广义Jaccard系数用于连续或计数属性系数用于连续或计数属性n二元情况下归约至二元情况下归约至 Jaccard 系数系数61相关性相关性相关性是对象属性间线性联系的度量相关性是对象属性间线性联系的度量为了计算相关性为了计算相关性,标准化数据对象标准化数据对象 p 和和 q,然后取它们的点积然后取它们的点积62相关性可视化相关性可视化相关性可视化相关性可视化散点图显示散点图显示了相关度从了相关度从 1 to 1.63组合相似度的通用方法组合相似度的通用方法有时属性有许多不同的类型有时属性有许多不同的类型,但一个整体相似度是必需的但一个整体相似度是必需的.64使用权重组合相似度使用权重组合相似度不需要同等对待所有属性不需要同等对待所有属性.n权重权重 wk 值在值在 0 到到 1 之间之间,总和为总和为 1.65密度密度基于密度聚类需要一个密度概念基于密度聚类需要一个密度概念例如例如:n欧几里德密度欧几里德密度n 欧几里德密度欧几里德密度=每个单元卷上的点数每个单元卷上的点数n概率密度概率密度 n基于图的密度基于图的密度66欧几里德密度欧几里德密度 Cell-based Cell-based最简单的方法是将区域划分成一些相同的矩形单元最简单的方法是将区域划分成一些相同的矩形单元,根据单元所根据单元所包含的点数确定密度包含的点数确定密度单元密度每个单元的点数67欧几里德密度欧几里德密度 Center-based Center-based欧几里德密度是特定半径内的点数欧几里德密度是特定半径内的点数基于中心的密度6869总结总结n数据预处理对数据仓库和数据挖掘来说都是大问题。数据预处理对数据仓库和数据挖掘来说都是大问题。n描述性数据汇总是预处理对数据质量的要求。描述性数据汇总是预处理对数据质量的要求。n数据预处理包括：数据清洗、数据集成、数据规约、特征数据预处理包括：数据清洗、数据集成、数据规约、特征提取、离散化处理提取、离散化处理n尽管预处理已经有许多方法，但预处理的研究仍然非常活尽管预处理已经有许多方法，但预处理的研究仍然非常活跃跃作业与思考作业与思考1、70谢谢 谢谢 ！人有了知识，就会具备各种分析能力，明辨是非的能力。所以我们要勤恳读书，广泛阅读，古人说“书中自有黄金屋。”通过阅读科技书籍，我们能丰富知识，培养逻辑思维能力；通过阅读文学作品，我们能提高文学鉴赏水平，培养文学情趣；通过阅读报刊，我们能增长见识，扩大自己的知识面。有许多书籍还能培养我们的道德情操，给我们巨大的精神力量，鼓舞我们前进。