数据挖掘导论第2章(v4)课件

1、第2章 数据数据类型数据质量数据预处理相似性和相异性度量2.1 数据类型2.1.1 属性与度量2.1.2 数据集的类型3数据数据集是数据对象的集合数据对象用一组刻画对象基本特性（如物体质量或事件发生时间）的属性描述 数据对象的其他名称记录、点、向量、模式、事件、案例、样本、观测或实体 属性（ attribute ）是对象的性质或特性，他因对象而异，或随时间而变化属性的其他名称变量、特性、字段、特征或维 AttributesObjects属性如何测量和描述，既取决于事物本身的客观性质，也和所掌握的技术手段相关。涉及到 测量精度：海岸线长度。虹膜颜色（分几类颜色描述、RBG均值描述、RBG直方图描

2、述）25 九月 2022数据挖掘导论4测量标度是将数值或符号与对象的属性相关联的规则。属性的性质不必与用来度量它的值的性质相同。属性的类型序性质、可加性序性质25 九月 2022数据挖掘导论5属性的类型属性的类型，即测量标度类型，取决于下列4种数值性质：属性值（数值）的性质1、Distinctness（相异性）: = 2、Order（序）: 3、Addition（加法）: + - Multiplication （乘法） : * /属性的类型不同，允许的操作不同25 九月 2022数据挖掘导论6属性的类型There are different types of attributes标称（Nomi

3、nal）Examples: 邮编、雇员ID序数（ Ordinal ）Examples: 成绩、街道号码区间（Interval）Examples: 日期、温度比率（Ratio）Examples: 绝对温度、长度、年龄、计数25 九月 2022数据挖掘导论7表2-2 不同的属性类型属性类型描 述例 子操 作标称属性的值仅仅只是不同的名字，即标称值只提供足够的信息以区分对象（=，）邮政编码、雇员ID号、眼球颜色、性别众数、熵、列联相关、2检验序数属性的值提供足够的信息确定对象的序（）矿石硬度、好，较好，最好、成绩、街道号码中值、百分位、秩相关、游程检验、符号检验对于区间属性，值之间的差是有意义的，即

4、存在测量单位（，）日历日期、摄氏或华氏温度均值、标准差、皮尔逊相关、t和F检验对于比率变量，差和比率都是有意义的（*，/）绝对温度、货币量、计数、年龄、质量、长度、电流几何平均、调和平均、百分比变差分类的(定性的)数值的(定量的)标称序数区间比率25 九月 2022数据挖掘导论8表2-3 定义属性层次的变换属性类型变 换注 释任何一对一变换，例如值的一个排列如果所有雇员的ID号都重新赋值，不会导致任何不同值的保序变换，即 新值= f(旧值),其中f是单调函数包括概念好、较好、最好的属性可以完全等价地用值1, 2, 3或用0.5, 1, 10表示新值 = a旧值+ b,其中a、b是常数华氏和摄氏

5、温度标度零度的位置和1度的大小（单位）不同新值= a 旧值长度可以用米或英尺度量分类的(定性的)数值的(定量的)标称序数区间比率25 九月 2022数据挖掘导论9用值的个数描述属性：离散vs.连续属性离散属性(Discrete Attribute)有限或无限可数 (countable infinite )个值例: 邮政编码, 计数, 文档集的词常表示为整数变量. 注意: 二元属性(binary attributes)是离散属性的特例连续属性(Continuous Attribute)属性值为实数例: 温度, 高度, 重量. 实践中, 实数只能用有限位数字的数度量和表示.连续属性一般用浮点变量表

6、示. 25 九月 2022数据挖掘导论10数据集的一般特性维度(Dimensionality)数据集的维度是数据集中的对象具有的属性数目 维灾难（Curse of Dimensionality）维归约（dimensionality reduction） 稀疏性(Sparsity)如具有非对称特征的数据集，一个对象的大部分属性上的值都为0 只存储和处理非零值分辨率(Resolution) 数据的模式依赖于分辨率度量尺度(scale)在数米的分辨率下，地球表面看上去很不平坦，但在数十公里的分辨率下却相对平坦 小时标度下的气压变化反映风暴或其他天气系统的移动；在月标度下，这些现象就检测不到 25 九

7、月 2022数据挖掘导论11数据集类型（三大类）记录数据数据矩阵（Data Matrix）文本数据（Document Data ）：每篇文档可以表示成一个文档-词矩阵 事务数据（Transaction Data）基于图形(Graph)的数据World Wide Web分子结构（Molecular Structures）有序(Ordered)数据空间数据（Spatial Data）时间数据（Temporal Data）序列数据（Sequential Data ）25 九月 2022数据挖掘导论12数据集类型1：记录数据: 数据矩阵数据矩阵:如果一个数据集中的所有数据对象都具有相同的数值属性集,则

8、数据对象可以看做是多维空间中的点,其中每个位代表描述对象的一个不同属性。这样的数据集可以用一个mXn的矩阵表示pregplaspresskininsumasspediageclass61487235033.60.62750positive1856629026.60.35131negative8183640023.30.67232positive25 九月 2022数据挖掘导论13数据集类型1：记录数据: 事务数据典型的记录数据：事务数据或购物篮数据25 九月 2022数据挖掘导论14数据集类型2：基于图形的数据1带有对象之间联系的数据 Examples: HTML Links 25 九月 20

9、22数据挖掘导论15数据集类型2：基于图形的数据2具有图形对象的数据 对象具有结构，即对象包含具有联系的子对象 例: 苯分子的球棍图，包含碳原子（黑色）和氢原子（灰色） 25 九月 2022数据挖掘导论16数据集类型3：有序数据: 时序数据有序数据有多种, 常常涉及时间或空间序时序数据（sequential data）也称时间数据（temporal data） 时间次序重要, 但具体时间不重要例：事务序列25 九月 2022数据挖掘导论17数据集类型3：有序数据: 序列数据序列数据（sequence data）个体项的序列 例：基因组序列数据DNA都由4种核苷酸 A, T, G和C构造没有时间

10、标记，但与时序数据类似重要的是在序列中的位置25 九月 2022数据挖掘导论18数据集类型3：有序数据: 时间序列数据 时间序列数据（time series data）特殊的时序数据，其中每个记录都是一个时间序列(time series)，即一段时间的测量序列 时间自相关（temporal autocorrelation），即如果两个测量的时间很接近，这些测量的值通常非常相似 25 九月 2022数据挖掘导论19数据集类型3：有序数据:空间数据空间数据 具有空间属性，如位置或区域例: 不同的地理位置收集的气象数据（降水量、气温、气压）空间自相关性（spatial autocorrelation

11、）: 物理上靠近的对象趋向于在其他方面也相似 右图每月是空间数据,显示多月是时间-空间数据(Spatial-Temporal Data)2.2 数据质量2.2 数据质量2.2.1 测量和数据收集问题1.测量误差和数据收集错误2.噪声和伪像3.精度、偏倚、准确率4.离群点5.遗漏值6.不一致的值7.重复的值2.2.2 数据质量: 应用问题25 九月 2022数据挖掘导论22测量误差和数据收集错误测量误差和数据收集错误 测量误差（measurement error）测量过程导致的任何问题 ，表现为记录值与实际值不同数据收集错误（data collection error）遗漏数据对象或属性值，或不

12、正确地包含数据对象等错误 测量误差和数据收集错误都可能是系统的或随机的 25 九月 2022数据挖掘导论23测量误差和数据收集错误数据中可能存在的问题噪声（测量误差的随机部分）离群点（可能同时涉及测量误差和数据收集错误 ）遗漏值（可能同时涉及测量误差和数据收集错误 ）不一致的值（可能同时涉及测量误差和数据收集错误 ）重复的值（可能同时涉及测量误差和数据收集错误 ）25 九月 2022数据挖掘导论24 噪声和伪像噪声是测量误差的随机部分可能扭曲值或附加的谬误对象 Examples: distortion of a persons voice when talking on a poor phon

13、e and “snow” on television screenTwo Sine WavesTwo Sine Waves + Noise25 九月 2022数据挖掘导论25精度、偏倚、准确率精度：precision偏倚：bias准确率 ：accuracy25 九月 2022数据挖掘导论26 离群点离群点(Outliers)data objects with characteristics that are considerably different than most of the other data objects in the data set25 九月 2022数据挖掘导论27 遗

14、漏值原因Information is not collected (e.g., people decline to give their age and weight)Attributes may not be applicable to all cases (e.g., annual income is not applicable to children)处理Eliminate Data Objects or Attribute删除数据对象或属性Estimate Missing Values 估计遗漏值Ignore the Missing Value During Analysis分析时忽

15、略遗漏值25 九月 2022数据挖掘导论28 不一致的值数据可能包含不一致的值例如, 地址字段，其中列出了邮政编码和城市，但是特定的邮政编码区域并不包含在该城市 纠正不一致需要附加或冗余信息 时间序列数据中的不一致可能是使用不同的测量手段例: 海洋表面温度（SST） 19581982年用船或浮标 收集SST1983年之后使用卫星收集SST两组数据, 每组内的年相互之间趋向于正相关，但与另一组的年负相关 25 九月 2022数据挖掘导论29 重复数据Data set may include data objects that are duplicates, or almost duplicate

16、s of one anotherMajor issue when merging data from heterogeneous sourcesExamples:同一个人具有多个email地址Same person with multiple email addressesData cleaning重复数据需要进行数据清洗Process of dealing with duplicate data issues25 九月 2022数据挖掘导论30数据质量: 应用问题时效性 有些数据收集后就开始老化例如, 顾客的购买行为或Web浏览模式的快照只代表有限时间内的真实情况 如果数据已经过时，则基于它

17、的模型和模式也已经过时。相关性 可用的数据必须包含应用所需要的信息例如, 构造一个模型，预测驾驶事故发生率如果忽略了关于驾驶员的年龄和性别信息，那么除非这些信息可以间接地通过其他属性得到，否则模型的精度可能是有限的 2.3 数据预处理25 九月 2022数据挖掘导论32数据预处理数据预处理方法聚集(Aggregation)抽样(Sampling)维归约(Dimensionality Reduction)特征子集选择(Feature subset selection)特征创建(Feature creation)离散化与二元化(Discretization and Binarization)属性变

18、换(Attribute Transformation)25 九月 2022数据挖掘导论33聚集Aggregation（聚集）: Combining two or more attributes (or objects) into a single attribute (or object)将两个或多个对象合并成单个对象PurposeData reduction（数据归约） Reduce the number of attributes or objectsChange of scale（标度转换） Cities aggregated into regions, states, countrie

19、s, etcMore “stable” data（更稳定的数据） Aggregated data tends to have less variability 缺点：丢失有趣的细节25 九月 2022数据挖掘导论34聚集: 例子Variation of Precipitation in Australia（澳大利亚降水量）平均月降水量标准差直方图平均年降水量标准差直方图25 九月 2022数据挖掘导论35抽样抽样是一种选择数据对象子集进行分析的常用方法 统计学抽样vs数据挖掘抽样统计学抽样的原因是因为得到感兴趣的整个数据集的代价太高数据挖掘使用抽样是因为处理所有数据的代价太高有效抽样的原则:代

20、表性保留原数据集的性质抽样方法简单抽样(Simple Random Sampling)There is an equal probability of selecting any particular item简单无放回抽样(Sampling without replacement)As each item is selected, it is removed from the population简单有放回抽样(Sampling with replacement)Objects are not removed from the population as they are selected

21、for the sample. In sampling with replacement, the same object can be picked up more than once分层抽样(Stratified sampling)Split the data into several partitions; then draw random samples from each partition每组抽相同个数vs按比例自适应(adaptive)或渐进抽样(progressive sampling)原因：有时难以预先确定样本集大小方法：从一个小样本开始，然后增加样本容量直至得到足够容量的样

22、本 25 九月 2022数据挖掘导论37样本大小: 例子从8000个点分别抽2000和500个点2000个点的样本保留了数据集的大部分结构 500个点的样本丢失了许多结构8000 points 2000 Points500 Points25 九月 2022数据挖掘导论38维归约数据集包含大量特征例：文档数据集，数以万计的词对应数以万计的属性维灾难(curse of dimensionality)随着数据维度的增加，许多数据分析变得非常困难。特殊地，随着维度增加，数据在它所占据的空间中越来越稀疏 对于分类，这可能意味没有足够的数据对象来创建模型 对于聚类，点之间的密度和距离的定义（对聚类是至关重

23、要的）变得不太有意义 结果: 对于高维数据, 许多分类和聚类算法（以及其他数据分析算法）都有麻烦分类准确率降低，聚类质量下降 技术PCA：Principle Component Analysis 主成分分析SVD：Singular Value Decomposition 奇异值分解25 九月 2022数据挖掘导论39维归约: PCAGoal is to find a projection that captures the largest amount of variation in dataFind the eigenvectors of the covariance matrixThe e

24、igenvectors define the new spacex2x1e25 九月 2022数据挖掘导论40特征子集选择特征子集选择是降低维度的另一种方法。当存在冗余特征（Redundant features）、不相关特征（Irrelevant features）时，使用特征的一个子集，能在降低维度的同时避免丢失信息。特征子集选择的技术:Brute-force approach暴力穷举:Embedded approaches嵌入方法:Feature selection occurs naturally as part of the data mining algorithmFilter ap

25、proaches过滤方法:Features are selected before data mining algorithm is runWrapper approaches包装方法:Use the data mining algorithm as a black box to find best subset of attributes25 九月 2022数据挖掘导论41特征创建Create new attributes that can capture the important information in a data set much more efficiently than t

26、he original attributes三种一般方法 :特征提取Feature Extractiondomain-specific 高度针对具体领域（如：人脸检测、指纹识别）映射数据到新的空间Mapping Data to New Space特征构造Feature Construction combining features 从多个原特征构造新的特征25 九月 2022数据挖掘导论42特征创建：映射数据到新空间傅里叶变换(Fourier transform)小波变换(Wavelet transform)例: 傅里叶变换左: 两个sin波; 中: 两个sin波之和+噪声; 检测不到模式右:

27、 傅里叶变换到频谱; 两个尖峰对应于两个无噪声的时间序列 Two Sine WavesTwo Sine Waves + NoiseFrequency25 九月 2022数据挖掘导论43特征创建：特征构造原始数据集的特征具有必要的信息，但其形式不适合数据挖掘算法 由原特征构造的新特征可能比原特征更有用 例: 文物数据库每件文物的特征包括: 体积和质量，以及其他信息 文物材质(类): 木材、陶土、青铜、黄金 原特征不适合分类构造新特征: 密度=质量/体积常依据专家意见25 九月 2022数据挖掘导论44离散化和二元化 为什么要离散化/二元化减少属性值个数，便于挖掘，结果知识表达更简洁、更易于理解、

28、更易使用离散化产生概念分层结构，可以在不同抽象层进行挖掘有些算法需要离散属性有些算法需要二元属性1、离散属性二元化2、连续属性离散化 3、具有过多值的离散属性非监督vs监督离散化差别：是否使用类信息25 九月 2022数据挖掘导论45变量变换 变量/属性变换（variable/attribute transformation） A function that maps the entire set of values of a given attribute to a new set of replacement values such that each old value can be i

29、dentified with one of the new values简单变换Simple functions: xk, log(x), ex, |x|, 1/x注意:可能改变数据的特性 例: 变换1/x压缩了大于1的值，但是放大了0和1之间的值 25 九月 2022数据挖掘导论46变量变换: 标准化/规范化标准化（standardization）规范化（normalization）在数据挖掘中不区分 在统计学有不同涵义目标: 使整个值的集合具有特定的性质 例: 设 是属性值的均值, sx是它们的标准差, 变换创建一个新的变量，它具有均值0和标准差1 可以用中位数取代均值可以绝对标准差（ab

30、solute standard deviation）取代标准差 2.4 相似性和相异性的度量2.4 相似性和相异性的度量2.4.1 基础1.相似性和相异性的定义2.相似性和相异性的变换2.4.2 简单属性间的相似/相异度2.4.3 数据对象间的相异度2.4.4 数据对象间的相似度2.4.5 邻近性度量的例子25 九月 2022数据挖掘导论49相似性和相异性 相似性(Similarity)Numerical measure of how alike two data objects are.Is higher when objects are more alike.Often falls in

31、the range 0,1相异性(Dissimilarity)Numerical measure of how different are two data objectsLower when objects are more alikeMinimum dissimilarity is often 0Upper limit varies邻近性 (Proximity) refers to a similarity or dissimilarity25 九月 2022数据挖掘导论50p and q are the attribute values for two data objects简单属性的

32、相似/相异度25 九月 2022数据挖掘导论51数据对象的相异度:欧几里得距离欧氏距离n是维数，而xk和yk分别是x和y的第k个属性（分量） 25 九月 2022数据挖掘导论52闵可夫斯基距离 Minkowski距离是欧氏距离的推广Where r is a parameterr = 1.城市街区距离（又称为曼哈顿距离） City block (Manhattan, taxicab, L1 norm) distance. A common example of this is the Hamming distance, which is just the number of bits that

33、are different between two binary vectorsr = 2.欧几里得距离Euclidean distancer .上确界距离“supremum” (Lmax norm, L norm) distance. This is the maximum difference between any component of the vectors25 九月 2022数据挖掘导论53距离的性质Distances, such as the Euclidean distance, have some well known properties.非负性。Non-negativi

34、ty: d(x, y) 0 for all x and y, and d(x, y) = 0 only if x = y. 对称性。Symmetry: d(x, y) = d(y, x) for all x and y. 三角不等式。Triangle Inequality: d(x, z) d(x, y) + d(y, z) for all points x, y, and z. where d(x, y) is the distance (dissimilarity) between points (data objects), x and y.A distance that satisfi

35、es these properties is a metric25 九月 2022数据挖掘导论54非度量的相异度有些相异度都不满足一个或多个度量性质 例1. 集合差每个对象是一个集合相异度用集合差的元素个数定义d(A, B) = size(AB)一般地，可能AB BA， size(AB) size(BA) 定义d(A, B) = size(A B) + size(B A) 例2. 时间 详见P432.4 相似性和相异性的度量2.4.1 基础1.相似性和相异性的定义2.相似性和相异性的变换2.4.2 简单属性间的相似/相异度2.4.3 数据对象间的相异度2.4.4 数据对象间的相似度2.4.5

36、邻近性度量的例子25 九月 2022数据挖掘导论56数据对象之间的相似度 设s(x, y)是数据点x和y之间的相似度（通常, 0 s(x, y) 1）s(x, y)=1, iff x=y （ 0 s(x, y) 1 ）s(x, y) = s(y, x)三角不等式（或类似的性质）通常不成立 2.4 相似性和相异性的度量2.4.1 基础1.相似性和相异性的定义2.相似性和相异性的变换2.4.2 简单属性间的相似/相异度2.4.3 数据对象间的相异度2.4.4 数据对象间的相似度2.4.5 邻近性度量的例子25 九月 2022数据挖掘导论58简单匹配系数/ Jaccard系数设x和y是两个对象，都由

37、n个二元属性组成f00 = x取0并且y取0的属性个数f01 = x取0并且y取1的属性个数f10 = x取1并且y取0的属性个数f11 = x取1并且y取1的属性个数简单匹配系数(Simple Matching Coefficient, SMC )Jaccard系数（Jaccard Coefficient） 25 九月 2022数据挖掘导论59简单匹配系数/ 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 = 2 x取0并且y取1的属性个数f10 = 1

38、x取1并且y取0的属性个数f00 = 7 x取0并且y取0的属性个数f11 = 0 x取1并且y取1的属性个数25 九月 2022数据挖掘导论60余弦相似度设x和y是两个向量，则“”表示向量点积 | x |是向量x的长度 几何解释其中，x = x / | x |，y = y / | y | 是长度为1的向量25 九月 2022数据挖掘导论61余弦相似度：例例: 两个数据向量对象x = (3, 2, 0, 5, 0, 0, 0, 2, 0, 0)y = (1, 0, 0, 0, 0, 0, 0, 1, 0, 2)xy = 31+2 0+0 0+5 0+0 0+0 0+0 0+2 1+0 0+0

39、2 = 5cos (x, y) = 5/(5.482.45)=0.31 25 九月 2022数据挖掘导论62广义Jaccard系数广义Jaccard系数Tanimoto系数设x和y是两个向量，则25 九月 2022数据挖掘导论63相关性 对象之间的相关性是对象属性之间线性联系的度量 设x和y是两个向量标准差协方差皮尔森相关（Pearsons correlation）系数 1 corr(x, y) 1. corr(x, y)=0, 不相关. corr(x, y)= 1 (1), 正(负)相关25 九月 2022数据挖掘导论64相关性: 可视化Scatter plots showing the s

40、imilarity from 1 to 1.25 九月 2022数据挖掘导论65邻近度计算问题 1距离度量的标准化和相关性 属性具有不同的值域问题: 距离可能被具有较大值域的属性左右处理: 变换到相同值域某些属性之间相关: 使用Mahalanobis距离(马氏距离) mahalanobis(x, y) = (x y)1(x y)T 其中, 1是数据协方差矩阵的逆协方差矩阵 是这样的矩阵，它的第ij个元素是第i个和第j个属性的协方差 马氏距离它是一种有效的计算两个未知样本集的相似度的方法。与欧氏距离不同的是它考虑到各种特性之间的联系，即独立于测量尺度。25 九月 2022数据挖掘导论66邻近度计

41、算问题 1:例例: 1000个点，其x属性和y属性的相关度为0.6. 在椭圆长轴两端的两个大点之间的欧几里得距离为14.7，但Mahalanobis距离仅为625 九月 2022数据挖掘导论67邻近度计算问题2组合异种属性的相似度 Sometimes attributes are of many different types, but an overall similarity is needed算法2.1 异种对象的相似度 1：对于第k个属性，计算相似度sk(x, y)，在区间0, 1中。2：对于第k个属性，定义一个指示变量k，如下： k= 0，如果第k个属性是非对称属性, 并且两个对象在该属性 上的值都是0，或者如果一个对象的第k个属性具有遗漏值 k = 1，否则3：使用如下公式计算两个对象之间的总相似度：附录25 九月 2022数据挖掘导论69离散化和二元化 为什么要离散化/二元化减少属性值个数，便于挖掘，结果知识表达更简洁、更易于理解、更易使用离散化产生概念分层结构，可以在不