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

第2章数据数据类型数据质量数据预处理相似性和相异性度量2.1数据类型

2.1.1属性与度量

2.1.2数据集的类型

3数据数据集是数据对象的集合数据对象用一组刻画对象基本特性（如物体质量或事件发生时间）的属性描述数据对象的其他名称记录、点、向量、模式、事件、案例、样本、观测或实体属性（attribute

）是对象的性质或特性，他因对象而异，或随时间而变化属性的其他名称变量、特性、字段、特征或维AttributesObjects属性如何测量和描述，既取决于事物本身的客观性质，也和所掌握的技术手段相关。涉及到测量精度：海岸线长度。虹膜颜色（分几类颜色描述、RBG均值描述、RBG直方图描述）04二月2023数据挖掘导论4测量标度是将数值或符号与对象的属性相关联的规则。属性的性质不必与用来度量它的值的性质相同。属性的类型序性质、可加性序性质04二月2023数据挖掘导论5属性的类型属性的类型，即测量标度类型，取决于下列4种数值性质：属性值（数值）的性质1、Distinctness（相异性）: = 2、Order（序）: <> 3、Addition（加法）: +- Multiplication（乘法）: */属性的类型不同，允许的操作不同04二月2023数据挖掘导论6属性的类型Therearedifferenttypesofattributes标称（Nominal）Examples:邮编、雇员ID序数（Ordinal）Examples:成绩、街道号码区间（Interval）Examples:日期、温度比率（Ratio）Examples:绝对温度、长度、年龄、计数04二月2023数据挖掘导论7表2-2不同的属性类型属性类型描

述例

子操

作标称属性的值仅仅只是不同的名字，即标称值只提供足够的信息以区分对象（=，）邮政编码、雇员ID号、眼球颜色、性别众数、熵、列联相关、2检验序数属性的值提供足够的信息确定对象的序（<，>）矿石硬度、{好，较好，最好}、成绩、街道号码中值、百分位、秩相关、游程检验、符号检验对于区间属性，值之间的差是有意义的，即存在测量单位（，）日历日期、摄氏或华氏温度均值、标准差、皮尔逊相关、t和F检验对于比率变量，差和比率都是有意义的（*，/）绝对温度、货币量、计数、年龄、质量、长度、电流几何平均、调和平均、百分比变差分类的(定性的)数值的(定量的)标称序数区间比率04二月2023数据挖掘导论8表2-3定义属性层次的变换属性类型变

换注

释任何一对一变换，例如值的一个排列如果所有雇员的ID号都重新赋值，不会导致任何不同值的保序变换，即新值=f(旧值),其中f是单调函数包括概念好、较好、最好的属性可以完全等价地用值{1,2,3}或用{0.5,1,10}表示新值

=a×旧值+b,其中a、b是常数华氏和摄氏温度标度零度的位置和1度的大小（单位）不同新值=a×旧值长度可以用米或英尺度量分类的(定性的)数值的(定量的)标称序数区间比率04二月2023数据挖掘导论9用值的个数描述属性：离散vs.连续属性离散属性(DiscreteAttribute)有限或无限可数(countableinfinite)个值例:邮政编码,计数,文档集的词常表示为整数变量.注意:二元属性(binaryattributes)是离散属性的特例连续属性(ContinuousAttribute)属性值为实数例:温度,高度,重量.实践中,实数只能用有限位数字的数度量和表示.连续属性一般用浮点变量表示.04二月2023数据挖掘导论10数据集的一般特性维度(Dimensionality)数据集的维度是数据集中的对象具有的属性数目维灾难（CurseofDimensionality）维归约（dimensionalityreduction）稀疏性(Sparsity)如具有非对称特征的数据集，一个对象的大部分属性上的值都为0只存储和处理非零值分辨率(Resolution)

数据的模式依赖于分辨率——度量尺度(scale)在数米的分辨率下，地球表面看上去很不平坦，但在数十公里的分辨率下却相对平坦小时标度下的气压变化反映风暴或其他天气系统的移动；在月标度下，这些现象就检测不到04二月2023数据挖掘导论11数据集类型（三大类）记录数据数据矩阵（DataMatrix）文本数据（DocumentData）：每篇文档可以表示成一个文档-词矩阵

事务数据（TransactionData）基于图形(Graph)的数据WorldWideWeb分子结构（MolecularStructures）有序(Ordered)数据空间数据（SpatialData）时间数据（TemporalData）序列数据（SequentialData）04二月2023数据挖掘导论12数据集类型1：记录数据:数据矩阵数据矩阵:如果一个数据集中的所有数据对象都具有相同的数值属性集,则数据对象可以看做是多维空间中的点,其中每个位代表描述对象的一个不同属性。这样的数据集可以用一个mXn的矩阵表示pregplaspresskininsumasspediageclass61487235033.60.62750positive1856629026.60.35131negative8183640023.30.67232positive04二月2023数据挖掘导论13数据集类型1：记录数据:事务数据典型的记录数据：事务数据或购物篮数据04二月2023数据挖掘导论14数据集类型2：基于图形的数据1带有对象之间联系的数据Examples:HTMLLinks04二月2023数据挖掘导论15数据集类型2：基于图形的数据2具有图形对象的数据对象具有结构，即对象包含具有联系的子对象例:苯分子的球—棍图，包含碳原子（黑色）和氢原子（灰色）04二月2023数据挖掘导论16数据集类型3：有序数据:时序数据有序数据有多种,常常涉及时间或空间序时序数据（sequentialdata）也称时间数据（temporaldata）时间次序重要,但具体时间不重要例：事务序列04二月2023数据挖掘导论17数据集类型3：有序数据:序列数据序列数据（sequencedata）个体项的序列例：基因组序列数据DNA都由4种核苷酸A,T,G和C构造没有时间标记，但与时序数据类似重要的是在序列中的位置04二月2023数据挖掘导论18数据集类型3：有序数据:时间序列数据

时间序列数据（timeseriesdata）特殊的时序数据，其中每个记录都是一个时间序列(timeseries)，即一段时间的测量序列时间自相关（temporalautocorrelation），即如果两个测量的时间很接近，这些测量的值通常非常相似04二月2023数据挖掘导论19数据集类型3：有序数据:空间数据空间数据具有空间属性，如位置或区域例:不同的地理位置收集的气象数据（降水量、气温、气压）空间自相关性（spatialautocorrelation）:物理上靠近的对象趋向于在其他方面也相似右图每月是空间数据,显示多月是时间-空间数据(Spatial-TemporalData)2.2数据质量2.2数据质量

2.2.1测量和数据收集问题 1.测量误差和数据收集错误 2.噪声和伪像 3.精度、偏倚、准确率 4.离群点 5.遗漏值 6.不一致的值 7.重复的值2.2.2数据质量:应用问题04二月2023数据挖掘导论22测量误差和数据收集错误测量误差和数据收集错误测量误差（measurementerror）测量过程导致的任何问题，表现为记录值与实际值不同数据收集错误（datacollectionerror）遗漏数据对象或属性值，或不正确地包含数据对象等错误测量误差和数据收集错误都可能是系统的或随机的04二月2023数据挖掘导论23测量误差和数据收集错误数据中可能存在的问题噪声（测量误差的随机部分）离群点（可能同时涉及测量误差和数据收集错误）遗漏值（可能同时涉及测量误差和数据收集错误）不一致的值（可能同时涉及测量误差和数据收集错误）重复的值（可能同时涉及测量误差和数据收集错误）04二月2023数据挖掘导论24

噪声和伪像噪声是测量误差的随机部分可能扭曲值或附加的谬误对象Examples:distortionofaperson’svoicewhentalkingonapoorphoneand“snow”ontelevisionscreenTwoSineWavesTwoSineWaves+Noise04二月2023数据挖掘导论25精度、偏倚、准确率精度：precision偏倚：bias准确率：accuracy04二月2023数据挖掘导论26

离群点离群点(Outliers)dataobjectswithcharacteristicsthatareconsiderablydifferentthanmostoftheotherdataobjectsinthedataset04二月2023数据挖掘导论27

遗漏值原因Informationisnotcollected

(e.g.,peopledeclinetogivetheirageandweight)Attributesmaynotbeapplicabletoallcases

(e.g.,annualincomeisnotapplicabletochildren)处理EliminateDataObjectsorAttribute删除数据对象或属性EstimateMissingValues估计遗漏值IgnoretheMissingValueDuringAnalysis分析时忽略遗漏值04二月2023数据挖掘导论28

不一致的值数据可能包含不一致的值例如,地址字段，其中列出了邮政编码和城市，但是特定的邮政编码区域并不包含在该城市纠正不一致需要附加或冗余信息时间序列数据中的不一致可能是使用不同的测量手段例:海洋表面温度（SST）1958～1982年用船或浮标收集SST1983年之后使用卫星收集SST两组数据,每组内的年相互之间趋向于正相关，但与另一组的年负相关04二月2023数据挖掘导论29

重复数据Datasetmayincludedataobjectsthatareduplicates,oralmostduplicatesofoneanotherMajorissuewhenmergingdatafromheterogeneoussourcesExamples:同一个人具有多个email地址SamepersonwithmultipleemailaddressesDatacleaning重复数据需要进行数据清洗Processofdealingwithduplicatedataissues04二月2023数据挖掘导论30数据质量:应用问题时效性有些数据收集后就开始老化例如,顾客的购买行为或Web浏览模式的快照只代表有限时间内的真实情况如果数据已经过时，则基于它的模型和模式也已经过时。相关性可用的数据必须包含应用所需要的信息例如,构造一个模型，预测驾驶事故发生率如果忽略了关于驾驶员的年龄和性别信息，那么除非这些信息可以间接地通过其他属性得到，否则模型的精度可能是有限的2.3数据预处理04二月2023数据挖掘导论32数据预处理数据预处理方法聚集(Aggregation)抽样(Sampling)维归约(DimensionalityReduction)特征子集选择(Featuresubsetselection)特征创建(Featurecreation)离散化与二元化(DiscretizationandBinarization)属性变换(AttributeTransformation)04二月2023数据挖掘导论33聚集Aggregation（聚集）:Combiningtwoormoreattributes(orobjects)intoasingleattribute(orobject)将两个或多个对象合并成单个对象PurposeDatareduction（数据归约）ReducethenumberofattributesorobjectsChangeofscale（标度转换）Citiesaggregatedintoregions,states,countries,etcMore“stable”data（更稳定的数据）Aggregateddatatendstohavelessvariability缺点：丢失有趣的细节04二月2023数据挖掘导论34聚集:例子VariationofPrecipitationinAustralia（澳大利亚降水量）平均月降水量标准差直方图平均年降水量标准差直方图04二月2023数据挖掘导论35抽样抽样是一种选择数据对象子集进行分析的常用方法

统计学抽样vs数据挖掘抽样统计学抽样的原因是因为得到感兴趣的整个数据集的代价太高数据挖掘使用抽样是因为处理所有数据的代价太高有效抽样的原则:代表性保留原数据集的性质抽样方法简单抽样(SimpleRandomSampling)Thereisanequalprobabilityofselectinganyparticularitem简单无放回抽样(Samplingwithoutreplacement)Aseachitemisselected,itisremovedfromthepopulation简单有放回抽样(Samplingwithreplacement)Objectsarenotremovedfromthepopulationastheyareselectedforthesample.Insamplingwithreplacement,thesameobjectcanbepickedupmorethanonce分层抽样(Stratifiedsampling)Splitthedataintoseveralpartitions;thendrawrandomsamplesfromeachpartition每组抽相同个数vs按比例自适应(adaptive)或渐进抽样(progressivesampling)原因：有时难以预先确定样本集大小方法：从一个小样本开始，然后增加样本容量直至得到足够容量的样本04二月2023数据挖掘导论37样本大小:例子从8000个点分别抽2000和500个点2000个点的样本保留了数据集的大部分结构500个点的样本丢失了许多结构8000points 2000Points 500Points04二月2023数据挖掘导论38维归约数据集包含大量特征例：文档数据集，数以万计的词对应数以万计的属性维灾难(curseofdimensionality)随着数据维度的增加，许多数据分析变得非常困难。特殊地，随着维度增加，数据在它所占据的空间中越来越稀疏对于分类，这可能意味没有足够的数据对象来创建模型对于聚类，点之间的密度和距离的定义（对聚类是至关重要的）变得不太有意义结果:对于高维数据,许多分类和聚类算法（以及其他数据分析算法）都有麻烦——分类准确率降低，聚类质量下降技术PCA：PrincipleComponentAnalysis主成分分析SVD：SingularValueDecomposition奇异值分解04二月2023数据挖掘导论39维归约:PCAGoalistofindaprojectionthatcapturesthelargestamountofvariationindataFindtheeigenvectorsofthecovariancematrixTheeigenvectorsdefinethenewspacex2x1e04二月2023数据挖掘导论40特征子集选择特征子集选择是降低维度的另一种方法。当存在冗余特征（Redundantfeatures）、不相关特征（Irrelevantfeatures）时，使用特征的一个子集，能在降低维度的同时避免丢失信息。特征子集选择的技术:Brute-forceapproach暴力穷举:Embeddedapproaches嵌入方法:FeatureselectionoccursnaturallyaspartofthedataminingalgorithmFilterapproaches过滤方法:FeaturesareselectedbeforedataminingalgorithmisrunWrapperapproaches包装方法:Usethedataminingalgorithmasablackboxtofindbestsubsetofattributes04二月2023数据挖掘导论41特征创建Createnewattributesthatcancapturetheimportantinformationinadatasetmuchmoreefficientlythantheoriginalattributes三种一般方法:特征提取FeatureExtractiondomain-specific高度针对具体领域（如：人脸检测、指纹识别）映射数据到新的空间MappingDatatoNewSpace特征构造FeatureConstructioncombiningfeatures从多个原特征构造新的特征04二月2023数据挖掘导论42特征创建：映射数据到新空间傅里叶变换(Fouriertransform)小波变换(Wavelettransform)例:傅里叶变换左:两个sin波;中:两个sin波之和+噪声;检测不到模式右:傅里叶变换到频谱;两个尖峰对应于两个无噪声的时间序列TwoSineWavesTwoSineWaves+NoiseFrequency04二月2023数据挖掘导论43特征创建：特征构造原始数据集的特征具有必要的信息，但其形式不适合数据挖掘算法由原特征构造的新特征可能比原特征更有用例:文物数据库每件文物的特征包括:体积和质量，以及其他信息文物材质(类):木材、陶土、青铜、黄金原特征不适合分类构造新特征:密度=质量/体积常依据专家意见04二月2023数据挖掘导论44离散化和二元化为什么要离散化/二元化减少属性值个数，便于挖掘，结果知识表达更简洁、更易于理解、更易使用离散化产生概念分层结构，可以在不同抽象层进行挖掘有些算法需要离散属性有些算法需要二元属性1、离散属性二元化2、连续属性离散化3、具有过多值的离散属性非监督vs监督离散化差别：是否使用类信息04二月2023数据挖掘导论45变量变换变量/属性变换（variable/attributetransformation）Afunctionthatmapstheentiresetofvaluesofagivenattributetoanewsetofreplacementvaluessuchthateacholdvaluecanbeidentifiedwithoneofthenewvalues简单变换Simplefunctions:xk,log(x),ex,|x|,1/x注意:可能改变数据的特性例:变换1/x压缩了大于1的值，但是放大了0和1之间的值04二月2023数据挖掘导论46变量变换:标准化/规范化标准化（standardization）规范化（normalization）在数据挖掘中不区分在统计学有不同涵义目标:使整个值的集合具有特定的性质例:设是属性值的均值,sx是它们的标准差,变换

创建一个新的变量，它具有均值0和标准差1

可以用中位数取代均值可以绝对标准差（absolutestandarddeviation）取代标准差2.4相似性和相异性的度量2.4相似性和相异性的度量2.4.1基础 1.相似性和相异性的定义 2.相似性和相异性的变换2.4.2简单属性间的相似/相异度2.4.3数据对象间的相异度2.4.4数据对象间的相似度2.4.5邻近性度量的例子04二月2023数据挖掘导论49相似性和相异性相似性(Similarity)Numericalmeasureofhowaliketwodataobjectsare.Ishigherwhenobjectsaremorealike.Oftenfallsintherange[0,1]相异性(Dissimilarity)NumericalmeasureofhowdifferentaretwodataobjectsLowerwhenobjectsaremorealikeMinimumdissimilarityisoften0Upperlimitvaries邻近性(Proximity)referstoasimilarityordissimilarity04二月2023数据挖掘导论50pandqaretheattributevaluesfortwodataobjects简单属性的相似/相异度04二月2023数据挖掘导论51数据对象的相异度:欧几里得距离欧氏距离n是维数，而xk和yk分别是x和y的第k个属性（分量）04二月2023数据挖掘导论52闵可夫斯基距离Minkowski距离是欧氏距离的推广Whererisaparameterr=1.城市街区距离（又称为曼哈顿距离）Cityblock(Manhattan,taxicab,L1norm)distance.AcommonexampleofthisistheHammingdistance,whichisjustthenumberofbitsthataredifferentbetweentwobinaryvectorsr=2.欧几里得距离Euclideandistancer

.上确界距离“supremum”(Lmaxnorm,L

norm)distance.Thisisthemaximumdifferencebetweenanycomponentofthevectors04二月2023数据挖掘导论53距离的性质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.Adistancethatsatisfiesthesepropertiesisametric04二月2023数据挖掘导论54非度量的相异度有些相异度都不满足一个或多个度量性质例1.集合差每个对象是一个集合相异度用集合差的元素个数定义d(A,B)=size(AB)一般地，可能ABBA，size(AB)size(BA)定义d(A,B)=size(AB)+size(BA)例2.时间详见P432.4相似性和相异性的度量2.4.1基础 1.相似性和相异性的定义 2.相似性和相异性的变换2.4.2简单属性间的相似/相异度2.4.3数据对象间的相异度2.4.4数据对象间的相似度2.4.5邻近性度量的例子04二月2023数据挖掘导论56数据对象之间的相似度设s(x,y)是数据点x和y之间的相似度（通常,0s(x,y)1）s(x,y)=1,iffx=y（0s(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邻近性度量的例子04二月2023数据挖掘导论58简单匹配系数/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）04二月2023数据挖掘导论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=2x取0并且y取1的属性个数f10=1x取1并且y取0的属性个数f00=7x取0并且y取0的属性个数f11=0x取1并且y取1的属性个数04二月2023数据挖掘导论60余弦相似度设x和y是两个向量，则“”表示向量点积||x||是向量x的长度几何解释其中，x’=x/||x||，y’=y/||y||是长度为1的向量04二月2023数据挖掘导论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+20+00+50+00+00+00+21+00+02=5cos(x,y)=5/(5.482.45)=0.3104二月2023数据挖掘导论62广义Jaccard系数广义Jaccard系数Tanimoto系数设x和y是两个向量，则04二月2023数据挖掘导论63相关性对象之间的相关性是对象属性之间线性联系的度量设x和y是两个向量标准差协方差皮尔森相关（Pearson’scorrelation）系数1corr(x,y)1.corr(x,y)=0,不相关.corr(x,y)=1(1),正(负)相关04二月2023数据挖掘导论64相关性:可视化Scatterplotsshowingthesimilarityfrom–1to1.04二月2023数据挖掘导论65邻近度计算问题1距离度量的标准化和相关性属性具有不同的值域问题:距离可能被具有较大值域的属性左右处理:变换到相同值域某些属性之间相关:使用Mahalanobis距离(马氏距离)

mahalanobis(x,y)=(xy)1(xy)T

其中,1是数据协方差矩阵的逆协方差矩阵是这样的矩阵，它的第ij个元素是第i个和第j个属性的协方差马氏距离它是一种有效的计算两个未知样本集的相似度的方法。与欧氏距离不同的是它考虑到各种特性之间的联系，即独立于测量尺度。04二月2023数据挖掘导论66邻近度计算问题1:例例:1000个点，其x属性和y属性的相关度为0.6.在椭圆长轴两端的两个大点之间的欧几里得距离为14.7，但Mahalanobis距离仅为604二月2023数据挖掘导论67邻近度计算问题2组合异种属性的相似度Sometimesattributesareofmanydifferenttypes,butanoverallsimilarityisneeded算法2.1异种对象的相似度1：对于第k个属性，计算相似度sk(x,y)，在区间[0,1]中。2：对于第k个属性，定义一个指示变量k，如下：k=0，如果第k个属性是非对称属性,并且两个对象在该属性上的值都是0，或者如果一个对象的第k个属性具有遗漏值k

=1，否则3：使用如下公式计算两个对象之间的总相似度：附录04二月2023数据挖掘导论69离散化和二元化为什么要离散化/二元化减少属性值个数，便于挖掘，结果知识表达更简洁、更易于理解、更易使用离散化产生概念分层结构，可以在不同抽象层进行挖掘有些算法需要离散属性有些算法需要二元属性非监督vs监督离散化差别：是否使用类信息04二月2023数据挖掘导论70离散属性二元化1方法1如果