数据挖掘导论第章vppt课件.ppt

第2 数据类型数据质量数据预处理相似性和相异性度量 1 2 1数据类型 2 1 1属性与度量2 1 2数据集的类型 2 数据 数据集是数据对象的集合数据对象用一组刻画对象基本特性 如物体质量或事件发生时间 的属性描述数据对象的其他名称记录 点 向量 模式 事件 案例 样本 观测或实体属性 attribute 是对象的性质或特性 他因对象而异 或随时间而变化属性的其他名称变量 特性 字段 特征或维 属性如何测量和描述 既取决于事物本身的客观性质 也和所掌握的技术手段相关 涉及到测量精度 海岸线长度 虹膜颜色 分几类颜色描述 RBG均值描述 RBG直方图描述 3 测量标度是将数值或符号与对象的属性相关联的规则 属性的性质不必与用来度量它的值的性质相同 属性的类型 序性质 可加性 序性质 4 属性的类型 属性的类型 即测量标度类型 取决于下列4种数值性质 属性值 数值 的性质1 Distinctness 相异性 2 Order 序 3 Addition 加法 Multiplication 乘法 属性的类型不同 允许的操作不同 5 属性的类型 Therearedifferenttypesofattributes标称 Nominal Examples 邮编 雇员ID序数 Ordinal Examples 成绩 街道号码区间 Interval Examples 日期 温度比率 Ratio Examples 绝对温度 长度 年龄 计数 6 表2 2不同的属性类型 分类的 定性的 数值的 定量的 标称 序数 区间 比率 7 表2 3定义属性层次的变换 分类的 定性的 数值的 定量的 标称 序数 区间 比率 8 用值的个数描述属性 离散vs 连续属性 离散属性 DiscreteAttribute 有限或无限可数 countableinfinite 个值例 邮政编码 计数 文档集的词常表示为整数变量 注意 二元属性 binaryattributes 是离散属性的特例连续属性 ContinuousAttribute 属性值为实数例 温度 高度 重量 实践中 实数只能用有限位数字的数度量和表示 连续属性一般用浮点变量表示 9 数据集的一般特性 维度 Dimensionality 数据集的维度是数据集中的对象具有的属性数目维灾难 CurseofDimensionality 维归约 dimensionalityreduction 稀疏性 Sparsity 如具有非对称特征的数据集 一个对象的大部分属性上的值都为0只存储和处理非零值分辨率 Resolution 数据的模式依赖于分辨率 度量尺度 scale 在数米的分辨率下 地球表面看上去很不平坦 但在数十公里的分辨率下却相对平坦小时标度下的气压变化反映风暴或其他天气系统的移动 在月标度下 这些现象就检测不到 10 数据集类型 三大类 记录数据数据矩阵 DataMatrix 文本数据 DocumentData 每篇文档可以表示成一个文档 词矩阵事务数据 TransactionData 基于图形 Graph 的数据WorldWideWeb分子结构 MolecularStructures 有序 Ordered 数据空间数据 SpatialData 时间数据 TemporalData 序列数据 SequentialData 11 数据集类型1 记录数据 数据矩阵 数据矩阵 如果一个数据集中的所有数据对象都具有相同的数值属性集 则数据对象可以看做是多维空间中的点 其中每个位代表描述对象的一个不同属性 这样的数据集可以用一个mXn的矩阵表示 12 数据集类型1 记录数据 事务数据 典型的记录数据 事务数据或购物篮数据 13 数据集类型2 基于图形的数据1 带有对象之间联系的数据Examples HTMLLinks 14 数据集类型2 基于图形的数据2 具有图形对象的数据对象具有结构 即对象包含具有联系的子对象例 苯分子的球 棍图 包含碳原子 黑色 和氢原子 灰色 15 数据集类型3 有序数据 时序数据 有序数据有多种 常常涉及时间或空间序时序数据 sequentialdata 也称时间数据 temporaldata 时间次序重要 但具体时间不重要例 事务序列 16 数据集类型3 有序数据 序列数据 序列数据 sequencedata 个体项的序列例 基因组序列数据DNA都由4种核苷酸A T G和C构造没有时间标记 但与时序数据类似重要的是在序列中的位置 17 数据集类型3 有序数据 时间序列数据 时间序列数据 timeseriesdata 特殊的时序数据 其中每个记录都是一个时间序列 timeseries 即一段时间的测量序列时间自相关 temporalautocorrelation 即如果两个测量的时间很接近 这些测量的值通常非常相似 18 数据集类型3 有序数据 空间数据 空间数据具有空间属性 如位置或区域例 不同的地理位置收集的气象数据 降水量 气温 气压 空间自相关性 spatialautocorrelation 物理上靠近的对象趋向于在其他方面也相似右图每月是空间数据 显示多月是时间 空间数据 Spatial TemporalData 19 2 2数据质量 20 2 2数据质量 2 2 1测量和数据收集问题1 测量误差和数据收集错误2 噪声和伪像3 精度 偏倚 准确率4 离群点5 遗漏值6 不一致的值7 重复的值2 2 2数据质量 应用问题 21 测量误差和数据收集错误 测量误差和数据收集错误测量误差 measurementerror 测量过程导致的任何问题 表现为记录值与实际值不同数据收集错误 datacollectionerror 遗漏数据对象或属性值 或不正确地包含数据对象等错误测量误差和数据收集错误都可能是系统的或随机的 22 测量误差和数据收集错误 数据中可能存在的问题噪声 测量误差的随机部分 离群点 可能同时涉及测量误差和数据收集错误 遗漏值 可能同时涉及测量误差和数据收集错误 不一致的值 可能同时涉及测量误差和数据收集错误 重复的值 可能同时涉及测量误差和数据收集错误 23 噪声和伪像 噪声是测量误差的随机部分可能扭曲值或附加的谬误对象Examples distortionofaperson svoicewhentalkingonapoorphoneand snow ontelevisionscreen 24 精度 偏倚 准确率 精度 precision偏倚 bias准确率 accuracy 25 离群点 离群点 Outliers dataobjectswithcharacteristicsthatareconsiderablydifferentthanmostoftheotherdataobjectsinthedataset 26 遗漏值 原因Informationisnotcollected e g peopledeclinetogivetheirageandweight Attributesmaynotbeapplicabletoallcases e g annualincomeisnotapplicabletochildren 处理EliminateDataObjectsorAttribute删除数据对象或属性EstimateMissingValues估计遗漏值IgnoretheMissingValueDuringAnalysis分析时忽略遗漏值 27 不一致的值 数据可能包含不一致的值例如 地址字段 其中列出了邮政编码和城市 但是特定的邮政编码区域并不包含在该城市纠正不一致需要附加或冗余信息时间序列数据中的不一致可能是使用不同的测量手段例 海洋表面温度 SST 1958 1982年用船或浮标收集SST1983年之后使用卫星收集SST两组数据 每组内的年相互之间趋向于正相关 但与另一组的年负相关 28 重复数据 Datasetmayincludedataobjectsthatareduplicates oralmostduplicatesofoneanotherMajorissuewhenmergingdatafromheterogeneoussourcesExamples 同一个人具有多个email地址SamepersonwithmultipleemailaddressesDatacleaning重复数据需要进行数据清洗Processofdealingwithduplicatedataissues 29 数据质量 应用问题 时效性有些数据收集后就开始老化例如 顾客的购买行为或Web浏览模式的快照只代表有限时间内的真实情况如果数据已经过时 则基于它的模型和模式也已经过时 相关性可用的数据必须包含应用所需要的信息例如 构造一个模型 预测驾驶事故发生率如果忽略了关于驾驶员的年龄和性别信息 那么除非这些信息可以间接地通过其他属性得到 否则模型的精度可能是有限的 30 2 3数据预处理 31 数据预处理 数据预处理方法聚集 Aggregation 抽样 Sampling 维归约 DimensionalityReduction 特征子集选择 Featuresubsetselection 特征创建 Featurecreation 离散化与二元化 DiscretizationandBinarization 属性变换 AttributeTransformation 32 聚集 Aggregation 聚集 Combiningtwoormoreattributes orobjects intoasingleattribute orobject 将两个或多个对象合并成单个对象PurposeDatareduction 数据归约 ReducethenumberofattributesorobjectsChangeofscale 标度转换 Citiesaggregatedintoregions states countries etcMore stable data 更稳定的数据 Aggregateddatatendstohavelessvariability缺点 丢失有趣的细节 33 聚集 例子 VariationofPrecipitationinAustralia 澳大利亚降水量 34 抽样 抽样是一种选择数据对象子集进行分析的常用方法统计学抽样vs数据挖掘抽样统计学抽样的原因是因为得到感兴趣的整个数据集的代价太高数据挖掘使用抽样是因为处理所有数据的代价太高 有效抽样的原则 代表性保留原数据集的性质 35 抽样方法 简单抽样 SimpleRandomSampling Thereisanequalprobabilityofselectinganyparticularitem简单无放回抽样 Samplingwithoutreplacement Aseachitemisselected itisremovedfromthepopulation简单有放回抽样 Samplingwithreplacement Objectsarenotremovedfromthepopulationastheyareselectedforthesample Insamplingwithreplacement thesameobjectcanbepickedupmorethanonce分层抽样 Stratifiedsampling Splitthedataintoseveralpartitions thendrawrandomsamplesfromeachpartition每组抽相同个数vs按比例自适应 adaptive 或渐进抽样 progressivesampling 原因 有时难以预先确定样本集大小方法 从一个小样本开始 然后增加样本容量直至得到足够容量的样本 36 样本大小 例子 从8000个点分别抽2000和500个点2000个点的样本保留了数据集的大部分结构500个点的样本丢失了许多结构 8000points2000Points500Points 37 维归约 数据集包含大量特征例 文档数据集 数以万计的词对应数以万计的属性维灾难 curseofdimensionality 随着数据维度的增加 许多数据分析变得非常困难 特殊地 随着维度增加 数据在它所占据的空间中越来越稀疏对于分类 这可能意味没有足够的数据对象来创建模型对于聚类 点之间的密度和距离的定义 对聚类是至关重要的 变得不太有意义结果 对于高维数据 许多分类和聚类算法 以及其他数据分析算法 都有麻烦 分类准确率降低 聚类质量下降技术PCA PrincipleComponentAnalysis主成分分析SVD SingularValueDecomposition奇异值分解 38 维归约 PCA GoalistofindaprojectionthatcapturesthelargestamountofvariationindataFindtheeigenvectorsofthecovariancematrixTheeigenvectorsdefinethenewspace 39 特征子集选择 特征子集选择是降低维度的另一种方法 当存在冗余特征 Redundantfeatures 不相关特征 Irrelevantfeatures 时 使用特征的一个子集 能在降低维度的同时避免丢失信息 特征子集选择的技术 Brute forceapproach暴力穷举 Embeddedapproaches嵌入方法 FeatureselectionoccursnaturallyaspartofthedataminingalgorithmFilterapproaches过滤方法 FeaturesareselectedbeforedataminingalgorithmisrunWrapperapproaches包装方法 Usethedataminingalgorithmasablackboxtofindbestsubsetofattributes 40 特征创建 Createnewattributesthatcancapturetheimportantinformationinadatasetmuchmoreefficientlythantheoriginalattributes三种一般方法 特征提取FeatureExtractiondomain specific高度针对具体领域 如 人脸检测 指纹识别 映射数据到新的空间MappingDatatoNewSpace特征构造FeatureConstructioncombiningfeatures从多个原特征构造新的特征 41 特征创建 映射数据到新空间 傅里叶变换 Fouriertransform 小波变换 Wavelettransform 例 傅里叶变换左 两个sin波 中 两个sin波之和 噪声 检测不到模式右 傅里叶变换到频谱 两个尖峰对应于两个无噪声的时间序列 42 特征创建 特征构造 原始数据集的特征具有必要的信息 但其形式不适合数据挖掘算法由原特征构造的新特征可能比原特征更有用例 文物数据库每件文物的特征包括 体积和质量 以及其他信息文物材质 类 木材 陶土 青铜 黄金原特征不适合分类构造新特征 密度 质量 体积常依据专家意见 43 2020年2月8日星期六 数据挖掘导论 44 离散化和二元化 为什么要离散化 二元化减少属性值个数 便于挖掘 结果知识表达更简洁 更易于理解 更易使用离散化产生概念分层结构 可以在不同抽象层进行挖掘有些算法需要离散属性有些算法需要二元属性1 离散属性二元化2 连续属性离散化3 具有过多值的离散属性非监督vs监督离散化差别 是否使用类信息 44 变量变换 变量 属性变换 variable attributetransformation Afunctionthatmapstheentiresetofvaluesofagivenattributetoanewsetofreplacementvaluessuchthateacholdvaluecanbeidentifiedwithoneofthenewvalues简单变换Simplefunctions xk log x ex x 1 x注意 可能改变数据的特性例 变换1 x压缩了大于1的值 但是放大了0和1之间的值 45 变量变换 标准化 规范化 标准化 standardization 规范化 normalization 在数据挖掘中不区分在统计学有不同涵义目标 使整个值的集合具有特定的性质例 设是属性值的均值 sx是它们的标准差 变换创建一个新的变量 它具有均值0和标准差1可以用中位数取代均值可以绝对标准差 absolutestandarddeviation 取代标准差 46 2 4相似性和相异性的度量 47 2 4相似性和相异性的度量 2 4 1基础1 相似性和相异性的定义2 相似性和相异性的变换2 4 2简单属性间的相似 相异度2 4 3数据对象间的相异度2 4 4数据对象间的相似度2 4 5邻近性度量的例子 48 相似性和相异性 相似性 Similarity Numericalmeasureofhowaliketwodataobjectsare Ishigherwhenobjectsaremorealike Oftenfallsintherange 0 1 相异性 Dissimilarity NumericalmeasureofhowdifferentaretwodataobjectsLowerwhenobjectsaremorealikeMinimumdissimilarityisoften0Upperlimitvaries邻近性 Proximity referstoasimilarityordissimilarity 49 pandqaretheattributevaluesfortwodataobjects 简单属性的相似 相异度 50 数据对象的相异度 欧几里得距离 欧氏距离n是维数 而xk和yk分别是x和y的第k个属性 分量 51 闵可夫斯基距离 Minkowski距离是欧氏距离的推广Whererisaparameterr 1 城市街区距离 又称为曼哈顿距离 Cityblock Manhattan taxicab L1norm distance AcommonexampleofthisistheHammingdistance whichisjustthenumberofbitsthataredifferentbetweentwobinaryvectorsr 2 欧几里得距离Euclideandistancer 上确界距离 supremum Lmaxnorm L norm distance Thisisthemaximumdifferencebetweenanycomponentofthevectors 52 距离的性质 Distances suchastheEuclideandistance havesomewellknownproperties 非负性 Non negativity d x y 0forallxandy andd x y 0onlyifx y 对称性 Symmetry d x y d y x forallxandy 三角不等式 TriangleInequality d x z d x y d y z forallpointsx y andz whered x y isthedistance dissimilarity betweenpoints dataobjects xandy Adistancethatsatisfiesthesepropertiesisametric 53 非度量的相异度 有些相异度都不满足一个或多个度量性质例1 集合差每个对象是一个集合相异度用集合差的元素个数定义d A B size A B 一般地 可能A B B A size A B size B A 定义d A B size A B size B A 例2 时间 详见P43 54 2 4相似性和相异性的度量 2 4 1基础1 相似性和相异性的定义2 相似性和相异性的变换2 4 2简单属性间的相似 相异度2 4 3数据对象间的相异度2 4 4数据对象间的相似度2 4 5邻近性度量的例子 55 数据对象之间的相似度 设s x y 是数据点x和y之间的相似度 通常 0 s x y 1 s x y 1 iffx y 0 s x y 1 s x y s y x 三角不等式 或类似的性质 通常不成立 56 2 4相似性和相异性的度量 2 4 1基础1 相似性和相异性的定义2 相似性和相异性的变换2 4 2简单属性间的相似 相异度2 4 3数据对象间的相异度2 4 4数据对象间的相似度2 4 5邻近性度量的例子 57 简单匹配系数 Jaccard系数 设x和y是两个对象 都由n个二元属性组成f00 x取0并且y取0的属性个数f01 x取0并且y取1的属性个数f10 x取1并且y取0的属性个数f11 x取1并且y取1的属性个数简单匹配系数 SimpleMatchingCoefficient SMC Jaccard系数 JaccardCoefficient 58 简单匹配系数 Jaccard系数 例 例 两个对象x和yx 1 0 0 0 0 0 0 0 0 0 y 0 0 0 0 0 0 1 0 0 1 f01 2x取0并且y取1的属性个数f10 1x取1并且y取0的属性个数f00 7x取0并且y取0的属性个数f11 0 x取1并且y取1的属性个数 59 余弦相似度 设x和y是两个向量 则 表示向量点积 x 是向量x的长度几何解释其中 x x x y y y 是长度为1的向量 60 余弦相似度 例 例 两个数据向量对象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 0 0 5 0 0 0 0 0 0 0 2 1 0 0 0 2 5cos x y 5 5 48 2 45 0 31 61 广义Jaccard系数 广义Jaccard系数Tanimoto系数设x和y是两个向量 则 62 相关性 对象之间的相关性是对象属性之间线性联系的度量设x和y是两个向量标准差协方差皮尔森相关 Pearson scorrelation 系数 1 corr x y 1 corr x y 0 不相关 corr x y 1 1 正 负 相关 63 相关性 可视化 Scatterplotsshowingthesimilarityfrom 1to1 64 邻近度计算问题1 距离度量的标准化和相关性属性具有不同的值域问题 距离可能被具有较大值域的属性左右处理 变换到相同值域某些属性之间相关 使用Mahalanobis距离 马氏距离 mahalanobis x y x y 1 x y T其中 1是数据协方差矩阵的逆协方差矩阵 是这样的矩阵 它的第ij个元素是第i个和第j个属性的协方差马氏距离它是一种有效的计算两个未知样本集的相似度的方法 与欧氏距离不同的是它考虑到各种特性之间的联系 即独立于测量尺度 65 邻近度计算问题1 例 例 1000个点 其x属性和y属性的相关度为0 6 在椭圆长轴两端的两个大点之间的欧几里得距离为14 7 但Mahalanobis距离仅为6 66 邻近度计算问题2 组合异种属性的相似度Sometimesattributesareofmanydifferenttypes butanoverallsimilarityisneeded 67 附录 68 2020年2月8日星期六 数据挖掘导论 69 离散化和二元化 为什么要离散化 二元化减少属性值个数 便于挖掘 结果知识表达更简洁 更易于理解 更易使用离散化产生概念分层结构 可以在不同抽象层进行挖掘有些算法需要离散属性有些算法需要二元属性非监督vs监督离散化差别 是否使用类信息 69 2020年2月8日星期六 数据挖掘导论 70 离散属性二元化1 方法1如果属性具有m个值 则将每个原始值唯一地映射到区间 0 m 1 中的一个整数 保序 把m个整数都变换成一个二进制数需要n log2m 个二进位表示这些整数用n个二元属性表示这些二进制数例 5个值 awful poor OK good great 的分类变量需要三