web数据挖掘-6数据挖掘的预处理技术

Chapter6:DataPreprocessingReview什么是数据挖掘数据挖掘的主要方法基于集合论的数据挖掘方法：关联分析基于信息论的数据挖掘方法：决策树Moretocome..数据挖掘的步骤三部曲数据准备数据选择：目标数据数据预处理：

消除噪声，不一致，冗余等

数据变换：连续数据离散化，数据转化

数据归约：特征选择和抽取数据挖掘结果的解释评估数据的预处理为什么要进行预处理数据清理：60%的工作量数据集成数据变换数据归约数据离散化为什么要预处理数据现实世界的数据是“肮脏的”–数据多了什么问题都会出现不完整的：有些感兴趣的属性缺少属性值e.g.,occupation=“”含噪声的：包含错误的，或者孤立点e.g.,Salary=“-10”不一致的：在编码或者命名上存在差异e.g.,Age=“42”Birthday=“03/07/1997”e.g.,Wasrating“1,2,3”,nowrating“A,B,C”e.g.,discrepancybetweenduplicaterecordsWhyIsDataPreprocessingImportant?6Noqualitydata,noqualityminingresults!Qualitydecisionsmustbebasedonqualitydatae.g.,duplicateormissingdatamaycauseincorrectorevenmisleadingstatistics.DatawarehouseneedsconsistentintegrationofqualitydataDataextraction,cleaning,andtransformationcomprisesthemajorityoftheworkofbuildingadatawarehouse重要性Importance“Datacleaningisoneofthethreebiggestproblemsindatawarehousing”—RalphKimball“Datacleaningisthenumberoneproblemindatawarehousing”—DCIsurvey数据质量的多维度量一个广为认可的多维度量观点精确度完整度一致性可信度附加价值可访问性根数据本身的含义相关的Intrinsic,contextual,representational,andaccessibility数据预处理的主要任务数据清理填写空缺的值，平化噪声数据，识别、删除孤立点，消除不一致性数据集成集成多个数据库、数据立方体或文件数据变换规范化和聚集数据归约得到数据集的压缩表示，它小得多，但可以得到相同或近似的结果数据离散化数据归约的一部分，通过概念分层和数据的离散化来规约数据，对数字型数据特别重要FormsofDataPreprocessing

10数据的预处理为什么要进行预处理数据清理：60%的工作量数据集成数据变换数据归约数据离散化空缺值数据并不总是完整的E.g.数据库表中，很多条记录的对应字段没有相应值，比如销售表中的顾客收入引起空缺值的原因设备异常与其他已有的数据不一致而被删除因为误解而没有被输入的数据对数据的改变没有进行日志记载如何处理空缺值忽略元组：当类标号缺少时通常会这么做人工填写空缺值：工作量大，可行性低使用一个全局变量填充空缺值：如unknown,N/Aminingroutinesmaymistakenlythinkthefilledvalueformaninterestingconcept使用属性的平均值填充空缺值使用与给定元组属同一类的所有样本的平均值使用最可能的值填充空缺值：使用像Bayesian公式或判定树这样的基于推断的方法smarterstrategy,whichusesthemostinformationcontainedinthepresentdataHowtoHandleMissingData?AgeIncomeReligionGender2324,200MuslimM39?ChristianF4545,390?F??Fillmissingvaluesusingaggregatefunctions(e.g.,average)orprobabilisticestimatesonglobalvaluedistributionE.g.,puttheaverageincomehere,orputthemostprobableincomebasedonthefactthatthepersonis39yearsoldE.g.,putthemostfrequentreligionhere噪声数据噪声：一个测量变量中的随机错误或偏差引起不正确属性值的原因数据收集工具的问题数据输入错误数据传输错误技术限制命名规则的不一致其他需要数据清理的数据问题重复纪录不完整的数据不一致的数据如何处理噪声数据分箱（Binning）首先排序，并将他们分到等深的箱中然后可以按箱的平均值平滑，按箱中值平滑，按箱的边界平滑等聚类检测并且去除孤立点计算机和人工检查结合计算机检测可疑数据，然后对他们进行人工判断回归通过让数据适应回归函数来平滑数据SimpleDiscretizationMethods:Binning17Equal-width(distance)partitioning：DividestherangeintoNintervalsofequalsize:uniformgridifAandBarethelowestandhighestvaluesoftheattribute,thewidthofintervalswillbe:W=(B–A)/N.Themoststraightforward,butoutliersmaydominatepresentationSkeweddataisnothandledwellEqual-depth(frequency)partitioningDividestherangeintoNintervals,eachcontainingapproximatelysamenumberofsamplesGooddatascalingManagingcategoricalattributescanbetrickySimpleDiscretizationMethods:BinningExample:customerages0-1010-2020-3030-4040-5050-6060-7070-80Equi-widthbinning:number

ofvalues0-2222-3144-4832-3838-4448-5555-6262-80Equi-depthbinning:数据平滑的分箱方法Price的排序后数据：4,8,15,21,21,24,25,28,34划分为（等深的）箱箱14815箱2212124箱3252834平滑方法用箱的平均值平滑箱1999箱2222222箱3292929用箱边界平滑箱14415箱2212124箱3252534划分为（等深的）箱箱14815箱2212124箱3252834聚类消除噪声分析查找孤立点回归消除噪音通过构造函数来符合数据变化的趋势，这样可以用一个变量预测另一个变量线性回归非线性回归xyy=x+1X1Y1Y1’数据的预处理为什么要进行预处理数据清理：60%的工作量数据集成数据变换数据归约数据离散化数据集成数据集成功能：将来自不同数据源的数据整合成一致的数据存储。元数据、相关分析、数据冲突检测和语义异种性的解析都有助于数据集成。问题和解决办法：问题1：模式集成来自多个信息源的现实世界的实体如何“匹配”？--实体识别问题E.g.,数据分析者或计算机如何才能确信一个数据库中的customer_id和另一个数据库中的cust_number指的是同一个实体？E.g.familynamevs.surname解决方法：利用数据库的元数据--一种关于数据的数据。这种元数据可以帮助避免模式集成中的错误。问题2：冗余一个属性若能由另一个表导出，它便是冗余的。例如年薪。属性或维命名的不一致也可能导致数据集中的冗余。解决方法：可利用相关分析的方法检测冗余。除了检测属性间的冗余外，“重复”也当在元组级进行检测。所谓重复是指对于同一数据，存在两个或多个相同的元组。CorrelationAnalysis(NumericalData)Correlationcoefficient(alsocalledPearson’sproductmomentcoefficient)wherenisthenumberoftuples,andaretherespectivemeansofAandB,σAandσBaretherespectivestandarddeviationofAandB,andΣ(AB)isthesumoftheABcross-product.IfrA,B>0,AandBarepositivelycorrelated(A’svaluesincreaseasB’s).Thehigher,thestrongercorrelation.rA,B=0:rA,B<0:negativelycorrelated27举例cor=0AandBarenotcorrelatede.g.A:rainB:goodTVprogramnote:notcorrelatedisnotequaltoindependentcor>0AandBarepositivelycorrelatede.g.A:rainB:cloudycor<0AandBarenegativelycorrelatede.g.A:rainB:sunshinePositivelyandNegativelyCorrelatedData2902February202330NotCorrelatedData问题3：数据值冲突的检测和处理对于现实世界的同一实体，来自不同数据源的属性值可能不同。这可能是因为表示、比例或编码的不同。例如重量属性可能在一个系统中以公制单位存放，而在另一个系统中以英制单位存放。数据这种语义上的异种性，是数据集成的巨大挑战。数据的预处理为什么要进行预处理数据清理：60%的工作量数据集成数据变换数据归约数据离散化数据变换数据变换将数据转换成适合挖掘的形式。平滑：去掉数据中的噪声。这种技术包括分箱、聚类和回归。聚集：对数据进行汇总和聚集。例如可以聚集日销售数据，计算年销售额。通常这一步用来为多粒度数据分析构造数据立方体。数据变换数据概化：使用概念分层，用高层次的概念替换低层次的“原始”数据。如分类的属性street可以概化为较高层的概念，如city或country。规范化：将属性数据按比例缩放，使之落入一个小的特定区间，如-1.0到1.0或0.0到1.0最小----最大规范化：对原始数据进行线形变换。假定属性A的最小和最大值分别为minA和maxA,计算Ex.Letincomerange$12,000to$98,000normalizedto[0.0,1.0].Then$73,000ismappedto数据变换

将A的值映射到区间[new_minA,new_maxA]中的v’

z-score规范化：属性A的值基于A的平均值和标准差规范化，计算Ex.Letμ=54,000,σ=16,000.Then小数定标规范化：通过移动属性A的小数点位置进行规范化，计算数据变换属性构造：由给定的属性构造和添加新的属性，以帮助提高精度和对高维数据结构的理解。例如，我们可能根据属性height和width添加属性area。通过组合属性，属性构造可以发现关于数据属性间联系的丢失信息，这对知识发现是有用的。数据的预处理为什么要进行预处理数据清理：60%的工作量数据集成数据变换数据归约数据离散化数据归约数据仓库中往往存有海量数据，在其上进行数据分析与挖掘需要很长时间数据归约数据归约可以用来得到数据集的归约表示，它小得多，却可以产生相同的或几乎相同的分析结果数据归约策略数据立方体聚集：聚集操作用于数据立方体中的数据。维归约：通过删除不相关的属性（或）维减少数据量。通常使用属性子集选择方法。数据压缩数值归约离散化和概念分层产生用于数据归约的时间不应当超过或抵消归约后的数据上挖掘节省的时间数据立方体聚集最底层的方体对应于基本方体基本方体对应感兴趣的实体在数据立方体中存在着不同级别的汇总数据立方体可以看成方体的格每个较高层次的抽象将进一步减少结果数量数据立方体提供了对于计算的汇总数据的快速访问使用与给定任务相关的最小方体在可能的情况下，对于汇总数据的查询应当使用数据立方体维归约通过删除不相干的属性或维减少数据量属性子集选择目标：找出最小属性集，使得数据类的概率分布尽可能地接近使用所有属性的原分布。优点：减少了出现在发现模式上的属性的数目，使得模式更易于理解。维归约启发式的方法属性子集选择方法包括以下技术：逐步向前选择：由空属性集开始，每次都选择原属性集中最好的属性，将其添加到集合中。逐步向后删除：由整个属性集开始，在每一步，删除掉尚在属性集中的最坏属性。向前选择和向后删除的结合：每一步选择一个最好的属性，并在剩余属性中删除一个最坏的属性。判定树归纳：用判定树算法选择“最好”的属性，将数据划分成类。逐步向前选择Step-wiseforwardselectionselectthebestoftheoriginalattributesselectthebestoftheremainingoriginalattributes……initialattributeset:{A1,A2,A3,A4,A5,A6}initialreducedset:{}step1:{A1}step2:{A1,A4}step3:{A1,A4,A6}逐步向后删除Step-wisebackwardeliminationeliminatetheworstoftheoriginalattributeseliminatetheworstoftheremainingoriginalattributes……initialattributeset:{A1,A2,A3,A4,A5,A6}initialreducedset:{A1,A2,A3,A4,A5,A6}step1:{A1,A3,A4,A5,A6}step2:{A1,A4,A5,A6}step3:{A1,A4,A6}向前选择和向后删除的结合Combinedforwardselectionandbackwardeliminationselectthebestoftheoriginalattributesandeliminatetheworstoftheremainingoriginalattributes……initialattributeset:{A1,A2,A3,A4,A5,A6}initialreducedset:{A1,A2,A3,A4,A5,A6}step1:{A1,A3,A4,A5,A6}step2:{A1,A4,A5,A6}step3:{A1,A4,A6}46ExampleofDecisionTreeInductionInitialattributeset:{A1,A2,A3,A4,A5,A6}A4?A1?A6?Class1Class2Class1Class2>Reducedattributeset:{A1,A4,A6}数据压缩有损压缩vs.无损压缩字符串压缩有广泛的理论基础和精妙的算法通常是无损压缩在解压缩前对字符串的操作非常有限音频/视频压缩通常是有损压缩，压缩精度可以递进选择有时可以在不解压整体数据的情况下，重构某个片断两种有损数据压缩的方法：小波变换和主要成分分析DataCompression48OriginalDataCompressedDatalosslessOriginalDataApproximatedlossyPrincipalComponentAnalysis(PCA)49GivenNdatavectorsfromn-dimensions,findk≤northogonalvectors(principalcomponents)thatcanbebestusedtorepresentdataStepsNormalizeinputdata:EachattributefallswithinthesamerangeComputekorthonormal(unit)vectors,i.e.,principalcomponentsEachinputdata(vector)isalinearcombinationofthekprincipalcomponentvectorsTheprincipalcomponentsaresortedinorderofdecreasing“significance”orstrengthSincethecomponentsaresorted,thesizeofthedatacanbereducedbyeliminatingtheweakcomponents,i.e.,thosewithlowvariance.(i.e.,usingthestrongestprincipalcomponents,itispossibletoreconstructagoodapproximationoftheoriginaldataWorksfornumericdataonlyUsedwhenthenumberofdimensionsislargeX1X2Y1Y2PrincipalComponentAnalysisX1,X2:originalaxes(attributes)Y1,Y2:principalcomponentssignificantcomponent(highvariance)Orderprincipalcomponentsbysignificanceandeliminateweakerones数值归约通过选择替代的较小的数据表示形式来减少数据量有参方法：使用一个参数模型来估计数据，最后只要存储参数即可线性回归方法：无参方法：直方图聚类选样数据归约：直方图一种流行的数据归约技术将某属性的数据划分成不相交的子集，或桶，桶中放置该值得出现频率桶和属性值得划分规则等深：

equalbucketrange等宽：

orequal-depthV-最优withtheleasthistogramvariance(weightedsumoftheoriginalvaluesthateachbucketrepresents)MaxDiffsetbucketboundarybetweeneachpairforpairshavetheβ–1largestdifferencesβdeterminesthenumberofbuckets直方图数据归约：聚类将数据集划分为聚类，然后通过聚类来表示数据集如果数据可以组成各种不同的聚类，则该技术非常有效，反之如果数据界限模糊，则方法无效数据可以分层聚类，并被存储在多层索引书中聚类的定义和算法都有很多选择数据归约：选样允许用数据的较小的随机样本来表示大的数据集对数据集D的样本选择简单随机选取n各样本，不放回：由D的N个元组中抽取n个样本简单随机选择n各样本，放回，过程同上聚类选样：D中元组被分入M个互不相交的聚类中，可在其中的m个聚类上进行简单随机选择(m<M)分层选样：D被划分为互不相交的层，则可通过对每一层的简单随机选样得到D的分层选样选样SRSWOR(simplerandomsamplewithoutreplacement)SRSWRRawData选样–聚类/分层选样RawDataCluster/StratifiedSamplerandomsamplingwithoutreplacement--〉randomsamplingwithreplacement(bootstrapsampling)ClustersamplingStratifiedsampling数据的预处理为什么要进行预处理数据清理：60%的工作量数据集成数据变换数据归约数据离散化离散化三种类型的属性值名称型–无序集合中的值序数–有序集合中的值连续值离散化将连续属性的范围划分为区间有效的归约数据基于判定树的分类挖掘离散化的数值用于进一步分析离散化和概念分层离散化通过将属性域划分为区间，减少给定连续数值的个数。区间的标号可以代替实际的数据值。概念分层通过使用高层的概念（青年、中年、老年）来代替底层的属性值（实际的年龄）来归约数据数据数值的离散化和概念分层生成分箱（Binning）分箱技术递归的用于结果划分，可以产生概念分层Top-downsplit,unsupervised,直方图分析直方图分析方法递归用于每一部分，可以自动的产生多级概念分层Top-downsplit,unsupervised聚类分析将数据划分成簇，每个簇形成同一个概念层上的一个节点，每个簇可再分成多个簇，形成子节点Eithertop-downsplitorbottom-upmerge,unsupervised基于熵的离散化supervised,top-downsplit通过自然划分分段top-downsplit,unsupervisedEntropy-BasedDiscretizationGivenasetofsamplesS,ifSispartitionedintotwointervalsS1andS2usingboundaryT,theinformationgainI(S,T)afterpartitioningisTheboundarythatmaximizestheinformationgainoverallp