第2章 数据预处理

Chapter2:DataPreprocessingWhypreprocessthedata?(数据预处理的必要性）Descriptivedatasummarization（描述性数据汇总）Datacleaning（数据清洗）Dataintegrationandtransformation（数据集成和转换）Datareduction（数据规约）Discretizationandconcepthierarchygeneration（数值离散化和概念分层）Summary（小结）第二章数据预处理

2.1预处理的必要性

目前，数据挖掘的研究工作大都集中在算法的探讨而忽视对数据处理的研究。事实上，数据预处理对数据挖掘十分重要，一些成熟的算法对其处理的数据集合都有一定的要求：比如数据的完整性好，冗余性小，属性的相关性小等。数据预处理是数据挖掘的重要一环，而且必不可少。要使挖掘算法挖掘出有效的知识，必须为其提供干净，准确，简洁的数据。然而，实际应用系统中收集的数据通常是“脏”数据

1、杂乱性

如性别：

A数据库male=1,female=2B数据库

male=‘男’，female=‘女’

C数据库

male=‘M’,female=‘F’2、重复性

同一客观事物在数据库中存在两个以上相同的物理描述假设某周刊有100000个订户，邮件列表中0.1%的记录是重复的，主要是一个名字有不同的写法

JonDoe和JohnDoe

因此，每周需要印刷和邮寄100份额外的刊物，假设每周的邮寄和印刷费用是两圆，公司每年将浪费10000元以上3、不完整性

由于实际系统设计时存在的缺陷以及使用过程中的一些人为因素，数据记录可能会出现数据值的丢失或不确定，原因可能有：（1）有些属性的内容有时没有（家庭收入，参与销售事物数据中的顾客信息）（2）有些数据当时被认为是不必要的（3）由于误解或检测设备失灵导致相关数据没有记录下来（4）与其它记录内容不一致而被删除（5）忽略了历史数据或对数据的修改4、噪声数据

数据中存在着错误或异常（偏离期望值），血压和身高为0就是明显的错误，当数据缺失且用默认值来填充缺失项时，很容易发生这类错误。（1）数据采集设备有问题（2）数据录入过程中发生了人为或计算机错误（3）传输过程中发生错误4.2数据预处理的功能

数据清理（清洗）

------可以去掉数据中的噪声，纠正不一致

数据集成

-----将多个数据源合并成一致的数据存储，构成一个完整的数据集，如数据仓库或数据立方体

数据变换（转换）---将一种格式的数据转换为另一格式的数据(如规范化)

数据归约（消减）----可以通过聚集、删除冗余特性或聚类等方法来压缩数据

这里需要指出的是：上述的各种数据预处理方法，并不是相互独立的，而是相互关联的，如消除数据冗余既可以看成是一种形式的数据清洗，也可以看成是一种数据消减。Chapter2:DataPreprocessing2.1Whypreprocessthedata?2.2Descriptivedatasummarization2.3Datacleaning2.4Dataintegrationandtransformation2.5Datareduction2.6DiscretizationandconcepthierarchygenerationSummaryMiningDataDescriptive

CharacteristicsMotivationTobetterunderstandthedata:centraltendency,variationandspreadDatadispersioncharacteristics

median,max,min,quantiles,outliers,variance,etc.NumericaldimensionscorrespondtosortedintervalsDatadispersion:analyzedwithmultiplegranularitiesofprecisionBoxplotorquantileanalysisonsortedintervalsDispersionanalysisoncomputedmeasuresFoldingmeasuresintonumericaldimensionsBoxplotorquantileanalysisonthetransformedcubeMeasuringtheCentralTendency

（度量数据的中心趋势）Mean(algebraicmeasure)(samplevs.population):Weightedarithmeticmean:Trimmedmean:choppingextremevaluesMedian:Aholisticmeasure(中值，整体度量）Middlevalueifoddnumberofvalues,oraverageofthemiddletwovaluesotherwiseEstimatedbyinterpolation(forgroupeddata):Mode（众数）ValuethatoccursmostfrequentlyinthedataUnimodal,bimodal,trimodalEmpiricalformula:P2

Symmetricvs.SkewedData

对称的和倾斜的数据Median,meanandmodeofsymmetric,positivelyandnegativelyskeweddataMeasuringtheDispersionofData

度量数据的离散程度Quartiles,outliersandboxplots（四分位数、离散点和盒图）Quartiles:Q1(25thpercentile),Q3(75thpercentile)Inter-quartilerange:IQR=Q3–

Q1Fivenumbersummary:min,Q1,M,

Q3,maxBoxplot:endsoftheboxarethequartiles,medianismarked,whiskers,andplotoutlierindividuallyOutlier:usually,avaluehigher/lowerthan1.5xIQRVarianceandstandarddeviation(sample:

s,population:σ)（方差和标准差）Variance:(algebraic,scalablecomputation)Standarddeviations(orσ)isthesquarerootofvariances2(or

σ2)PropertiesofNormalDistributionCurve

正态分布特性Thenormal(distribution)curveFromμ–σtoμ+σ:containsabout68%ofthemeasurements(μ:mean,σ:standarddeviation)

Fromμ–2σtoμ+2σ:containsabout95%ofitFromμ–3σtoμ+3σ:containsabout99.7%ofit

BoxplotAnalysisFive-numbersummaryofadistribution:Minimum,Q1,M,Q3,MaximumBoxplotDataisrepresentedwithaboxTheendsoftheboxareatthefirstandthirdquartiles,i.e.,theheightoftheboxisIRQThemedianismarkedbyalinewithintheboxWhiskers:twolinesoutsidetheboxextendtoMinimumandMaximumVisualizationofDataDispersion:BoxplotAnalysisHistogramAnalysisGraphdisplaysofbasicstatisticalclassdescriptionsFrequencyhistogramsAunivariategraphicalmethodConsistsofasetofrectanglesthatreflectthecountsorfrequenciesoftheclassespresentinthegivendataP36QuantilePlot（分位数图）Displaysallofthedata(allowingtheusertoassessboththeoverallbehaviorandunusualoccurrences)Plotsquantile

informationForadataxi

datasortedinincreasingorder,fi

indicatesthatapproximately100fi%ofthedataarebeloworequaltothevaluexiP37Quantile-Quantile(Q-Q)PlotGraphsthequantilesofoneunivariatedistributionagainstthecorrespondingquantilesofanotherAllowstheusertoviewwhetherthereisashiftingoingfromonedistributiontoanotherP38Scatterplot（散点图）Providesafirstlookatbivariatedatatoseeclustersofpoints,outliers,etcEachpairofvaluesistreatedasapairofcoordinatesandplottedaspointsintheplaneLoessCurve（Loess曲线）AddsasmoothcurvetoascatterplotinordertoprovidebetterperceptionofthepatternofdependenceLoesscurveisfittedbysettingtwoparameters:asmoothingparameter,andthedegreeofthepolynomialsthatarefittedbytheregressionPositivelyandNegativelyCorrelatedData

正相关和负相关NotCorrelatedDataGraphicDisplaysofBasicStatisticalDescriptionsHistogram:(shownbefore)Boxplot:(coveredbefore)Quantileplot:eachvaluexi

ispairedwithfi

indicatingthatapproximately100fi

%ofdataare

xi

Quantile-quantile(q-q)plot:graphsthequantilesofoneunivariantdistributionagainstthecorrespondingquantilesofanotherScatterplot:eachpairofvaluesisapairofcoordinatesandplottedaspointsintheplaneLoess(localregression)curve:addasmoothcurvetoascatterplottoprovidebetterperceptionofthepatternofdependence2.3数据清理（清洗）数据清理完成:

填充空缺的值识别孤立点消除噪声纠正数据中的不一致

数据清理可以分为有监督和无监督两类

有监督过程是在领域专家指导下，分析收集的数据，去除明显错误的噪声数据和重复记录，填补缺省数据；

无监督过程是用样本数据训练算法，使其获得一定的经验，并在以后的处理过程中自动采用这些经验完成数据清洗工作。一、遗漏数据的处理

(1)忽略该元组若一条记录中有属性值被遗漏了，则将该记录排除在数据挖掘之外；尤其当类标号缺少时通常这样做（假定挖掘任务涉及分类或描述)。当每个属性缺少值的百分比变化很大时，它的性能非常差。

(2)人工填写空缺值当数据集很大、缺少很多值时，该方法可能行不通。(3)使用一个全局常量填充空缺值(4)使用属性的平均值填充空缺值将空缺的属性值用同一个常数(如“Unknown”或)替换。如果空缺值都用“Unknown”替换，当空缺值较多时。挖掘程序可能误以为它们形成了一个有趣的概念，因为它们都具有相同的值——“Unknown”。因此，尽管该方法简单，我们并不推荐它。例如，假定AllElectronics顾客的平均收入为$28000，则使用该值替换income中的空缺值(5)利用同类别均值填补遗漏数据例如，如果将顾客按creditrisk分类，则用具有相同信用度的顾客的平均收入替换income中的缺值(6)使用最可能的值填充空缺值可以利用回归、贝叶斯计算公式或判定树归纳确定，推断出该条记录特定属性最大可能的取值。例如，利用数据集中其他顾客的属性，可以构造一棵判定树，来预测income的空缺值。二、噪声数据噪声(noise)是一个测量变量中的随机错误或偏差。给定一个数值属性，例如price，我们怎样才能平滑数据，去掉噪声?

(1)分箱(binning)

分箱方法通过考察“邻居”(即周围的值)来平滑存储数据的值。存储的值被分布到一些“桶”或箱中。由于分箱方法参考相邻的值，因此它进行局部平滑。下图展示示了一些分箱技术。

在该例中，price数据首先被划分并存人等深的箱中(深度3)。对于按箱平均值平滑，箱中每一个值被箱中的平均值替换。例如，箱1中的值4，8和15的平均值是9；这样，该箱中的每一个值被替换为9。类似地，可以使用按箱中值平滑。此时，箱中的每一个值被箱中的中值替换。对于按箱边界平滑，箱中的最大和最小值被视为箱边界。箱中的每一个值被最近的边界值替换。

(2)聚类(clustering)

通过聚类分析可以检测孤立点，聚类将类似的值组织成群或“聚类”。直观地看，落在聚类集合之外的值被视为孤立点(3)计算机和人工检查结合

可以通过计算机和人工检查结合的办法来识别孤立点。

(4)回归(regression)

可以利用拟合函数(如回归函数)来平滑数据。

如线性回归涉及找出适合两个变量的“最佳”直线，使得一个变量能够预测另一个。多线性回归是线性回归的扩展，它涉及多于两个变量，数据要适合一个多维面。使用回归，找出适合数据的数学方程式，能够帮助消除噪声。Regressionxyy=x+1X1Y1Y1’

许多数据平滑的方法也是涉及离散化的数据归约方法。例如，上面介绍的分箱技术减少了每个属性的不同值的数量。概念分层是一种数据离散化形式，也可以用于数据平滑。例如，price的概念分层可以把price的值映射到inexpensive，moderately_priced和expensive，从而减少了挖掘过程所处理的值的数量。

2.4

数据集成和变换一、数据集成

它需要统一原始数据中的所有矛盾之处，如字段的:

同名异义、异名同义、单位不统一字长不一致，从而把原始数据在最低层上加以转换，提炼和集成。

1、模式集成数据分析者或计算机如何才能确信一个数据库中的customer_id和另一个数据库中的cust_number指的是同一实体？通常，数据库和数据仓库有元数据——关于数据的数据。这种元数据可以帮助避免模式集成中的错误。2、冗余问题一个属性是冗余的，如果它能由另一个表“导出”，如年薪属性；命名的不一致也可能导致数据集中的冗余有些冗余可以被相关分析检测到。例如，给定两个属性，根据可用的数据，这种分析可以度量一个属性能在多大程度上蕴含另一个。属性A和B之间的相关性可用下式度量：其中，n是元组个数，分别是A和B的平均值，分别是A和B的标准差。

如果(2.1)式的值大于0，则A和B是正相关的，意味A的值随B的值增加而增加。该值越大，一个属性蕴涵另一个的可能性越大。因此，一个很大的值表明A(或B)可以作为冗余而被去掉。如果结果等于0，则A和B是独立的，它们之间不相关。如果结果值小于0，则A和B是负相关的，一个值随另一个减少而增加。

(2．1)式可以用来检测上面的的customer_id和cust_number的相关性。3、数据值冲突的检测与处理

表示不同导致数据冲突语义不同导致数据冲突

对于现实世界的同一实体，来自不同数据源的属性值可能不同。这可能是因为表示、比例或编码不同。例如，重量属性可能在一个系统中以公制单位存放，而在另一个系统中以英制单位存放。不同旅馆的价格不仅可能涉及不同的货币，而且可能涉及不同的服务(如免费早餐)和税。数据这种语义上的异种性，是数据集成的巨大挑战。仔细将多个数据源中的数据集成起来，能够减少或避免结果数据集中数据的冗余和不一致性。这有助于提高其后挖掘的精度和速度。另外，在数据集成中还应考虑数据类型的选择问题，如在值域范围内应尽量用tinyint代替int,可大大减少字节数，对于大规模数据集来说将会大大减少系统开销。二、数据变换-----数据变换将数据转换成适合于挖掘的形式。主要是找到数据的特征表示，对数据进行规格化处理。用维变换或转换方式减少有效变量的数目或找到数据的不变式

（1）平滑(smoothing)

去掉数据中的噪声。这种技术包括分箱（Bin)、聚类和回归。

（2）聚集对数据进行汇总和聚集例如，可以聚集日销售数据，计算月和年销售额。这一步用来为多粒度数据分析构造数据立方体。

(3)数据概化使用概念分层，用高层次概念替换低层次“原始”数据。例如，分类的属性，如street，可以概化为较高层的概念，如city或country。类似地，数值属性，如age映射到较高层概念，如young，middle-age和senior。

(4)规范化(规格化）

将属性数据按比例缩放，使之落入一个小的特定区间，如-1．0到1．0或0.0到1.0。如学生成绩GINT（G/10）规格化的目的是将一个属性取值范围影射到一个特定范围之内，以消除数值性属性因大小不一而造成挖掘结果的偏差在正式进行数据挖掘之前，尤其是使用基于对象距离的挖掘算法时，必须进行数据的规格化。如对于一个顾客信息数据库中年龄属性或工资属性，由于工资属性的取值比年龄属性的取值要大得多，若不进行规格化处理，基于工资属性的距离计算值将远远超过基于年龄属性的计算值，这就意味着工资属性的作用在整个数据对象的距离计算中被错误放大了①最小-最大规范化对原始数据进行线性变换。假定minA，和maxA分别为属性A的最小和最大值。最小—最大规范化通过计算

将属性A的一个值v影射到v’[new_minA,new-maxA](3.2)EX1

假定属性income的最小与最大值分别为$12000和$98000。我们想映射income到区间[0，1]。根据最小-最大规范化，income值$73000将变换为②Z-score规范化（或零-均值规范化）该方法是根据属性A的平均值和标准差规范化。A的值v被规范化为v’，由下式计算：(3.3)EX2假定属性income的平均值和标准差分别为$54000和$16000。使用z-score规范化，值$73600被转化为③小数定标规范化(十基数变换）通过移动属性A的小数点位置进行规范化。小数点的移动位数依赖于A的最大绝对值。

A的值v被规范化为，由下式计算其中，j是使max(|v’|<1)成立最小整数。

EX3假定A的值由-986到917。

A的最大绝对值为986。为使用小数定标规范化，我们用1000（即j=3）除每一值。这样，-986被规范化为-0.986。注意，规范化将原来的数据改变很多，特别是上述的后两种方法。有必要保留规范化参数（如平均值和标准差，如果使用z-score规范化），以便将来的数据可以用一致的方式规范化。

（5）属性构造(或特征构造)

可以利用已知的属性构造新的属性并添加到属性集中，以帮助挖掘过程。（由长，宽求面积）2.5数据规约（消减）

数据立方合计维数削减数据压缩数据块消减离散化与概念层次生成

1、数据立方体合计主要用于构造数据立方---建立数据仓库如对某公司三年销售合计处理，可用一个三维数据立方体（时间，商品，部门）表示，它从三个角度描述相应时空的销售额。每个属性都可对应一个概念层次树，以帮助进行多抽象层次的数据分析。2、维归约

----主要用于检测并删除不相关、弱相关或冗余的属性维。用于数据分析的数据可能包含数以百计的属性，其中大部分属性与挖掘任务不相关，是冗余的。例如，如果分析任务是按顾客听到广告后，是否愿意在A11E1ectronics买流行的新款CD将顾客分类，与属性age，music_tasfe不同，诸如顾客的电话号码等属性多半是不相关的。

属性子集选择的目标是找出最小属性子集，使得数据类的概率分布尽可能地接近原分布。

“如何找出原属性的一个‘好的’子集?”d个属性有2d个可能的子集。穷举搜索找出属性的最佳子集可能是不现实的，特别是当d和数据类的数目增加时。

因此，对于属性子集选择，通常使用压缩搜索空间的启发式算法。它们的策略是做局部最优选择，期望由此导致全局最优解。

(1)逐步向前选择(逐步添加方法）：该过程由空属性集开始，选择原属性集中最好的属性，并将它添加到该集合中。在其后的每一次迭代，将原属性集剩下的属性中的最好的属性添加到该集合中。如遗传算法遗传算法是一种基于生物进化论和分子遗传学的全局随机搜索算法。

(2)逐步向后删除(逐步消减方法）：该过程由整个属性集开始。在每一步，删除掉在属性集中的最坏属性。直到无法选择出最坏属性或满足一定的阈值为止。

如粗集理论不需要先验知识；

算法简单，易于操作，可有效地去除冗余属性，对于每个属性值域出现的冗余现象，也可用粗集理论删除，从而使条件属性的个数和取值得到化减。其基本思路是：利用定义的数据集合U上的等价关系对U进行划分，对于数据表来说，这种等价关系可以是某个属性，或者是几个属性的集合。因此，按照不同属性的组合就把数据表划分成不同的基本类，在这些基本类的基础上进一步求得最小约简集。(3)向前选择和向后删除的结合：向前选择和向后删除方法可以结合在一起，每一步选择一个最好的属性，并在剩余属性中删除一个最坏的属性。

(4)判定树归纳

判定树算法，如ID3和C4．5最初是用于分类的,也可用于构造属性子集利用决策树的归纳方法对初始数据进行分类归纳学习，获得一个初始决策树，所有没出现在这个树上的属性均认为是无关属性，删除无关属性之后，就可获得一个较优的属性子集。3、数据压缩数据压缩使用数据编码或数据转换机制压缩数据集。若根据压缩后的数据集可以恢复原来的数据集-----无损（loseless)若根据压缩后的数据集不能恢复原来的数据集-----有损(lossy)常用的有小波变换和主要素分析

离散小波变换是一种线形信号处理技术，可将一个向量D转换为D’（为小波相关系数）为提高数据运算处理的效率，可以保留用户指定阈值的小波系数，而将其他小波系数置0。小波变换可以保留数据的主要特征情况下除去数据中的噪声。应用小波变换进行数据转换时，通常采用通用层次算法：(1)L为所输入数据向量的长度，它必须是2的幂(2)每次转换使用两个函数，第一个负责初步平滑，第二个完成带权差值计算以获得数据的主要特征。(3)将数据向量一分为二，应用(2)中的两个函数分别处理低频、高频数据(4)对所输入的向量循环使用(3)中的处理步骤，直到所有划分的子数据向量的长度均为2为止(5)取出(3),(4)步骤处理结果便获得被转换数据向量的小波相关系数。4、数据块消减------利用更简单的数据表达形式

参数与非参数两种方法参数方法是通过模型计算获得原来的数据，只要存储模型的参数即可非参数方法是指存储利用直方图、聚类或采样而获得的消减后的数据直方图（等宽，等高）采样（随机，聚类，分类）5离散化和概念分层生成

离散化技术通过将属性域划分为区间来减少给定连续属性值的个数。区间的标号可以替代实际的数据值。概念层次树可以通过利用较高层次概念替换较低层次概念而减少原来的数据。

对于用户或领域专家，人工地定义概念分层可能是一项令人乏味、耗时的任务。幸而，许多分层蕴涵在数据库模式中，并且可以在模式定义级定义。概念分层常常自动地产生，或根据数据分布的统计分析动态地加以提炼。

数值数据的离散化和概念分层生成数值属性的概念分层可以根据数据分布分析自动地构造。分箱

通过将数据分布到箱中，并用箱中的平均值或中值替换箱中的每个值，可以将属性值离散化。就像用箱的平均值平滑或用箱的中值平滑一样。这些技术可以递归地作用于结果划分，产生概念分层。

直方图分析直方图也可以用于离散化.下面给出了一个直方图，显示某给定数据集price属性的数据分布。例如，频率最高的价格大约在$300—$325。可以使用划分规则定义值的范围。例如，在等宽直方图中，将值划分成相等的部分或区间(如($0…S100)，($100…$200)，…，($900…S1000)。在等深直方图中，值被划分使得每一部分包括相同个数的样本。聚类算法可以用来将数据划分成簇或群。每一个簇形成概念分层的一个节点，而所有的节点在同一概念层。每一个簇可以进一步分成若干子簇，形成较低的概念层。簇也可以聚集在一起，以形成分层结构中较高的概念层。

基于熵的离散化

熵(entropy)，可以用来递归地划分数值属性A的值，产生分层的离散化,形成属性的数值概念分层。给定一个数据元组的集合S，基于熵对A离散化的方法如下：1)A的每个值可以认为是一个潜在的区间边界或阈值T。例如，A的值v可以将样本划分成分别满足条件A<T和A>T的两个子集,这样就创建了一个二元离散化。2)给定S，所选择的阈值是这样的值，它使其后划分得到的信息增益最大。信息增益(informationgain)是

其中，S1，S2分别对应于S中满足条件A<T和A>T的样本。对它的熵函数Ent根据集合中样本的类分布来计算。例如，给定m个类，它的熵是3)确定阈值的过程递归地用于所得到的每一个划分，直到满足某个终止条件，如

基于熵的离散化可以压缩数据量。与迄今为止提到的其他方法不同，基于熵的离散化使用类信息，有助于提高分类的准确性。这里介绍的信息增益和熵也用于判定树归纳。

分类数据的概念分层生成分类数据(categoricaldata)是离散数据。一个分类属性具有有限个(但可能很多)不同值，值之间无序。如地理位置、工作分类和商品类型。

由用户或专家在模式级显式地说明属性的部分序：通常，分类属性或维的概念分层涉及一组属性。用户或专家在模式级通过说明属性的部分序或全序，可以很容易地定义概念分层。例如，关系数据库或数据仓库的维location可能包含如下一组属性：street，city，province_or_state，和country。可以在模式级说明一个全序，如