数据预处理概述课件

2022/12/94.数据预处理2022/12/912022/12/74.数据预处理2022/12/71为什么要进行数据挖掘?现实世界的数据是脏的不完整:缺乏属性值，缺乏有意义的属性，或者只包含了汇总数据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.,discrepancybetweenduplicaterecords2022/12/92为什么要进行数据挖掘?现实世界的数据是脏的2022/12/7为什么数据预处理重要?Noqualitydata,noqualityminingresults!Qualitydecisionsmustbebasedonqualitydatae.g.,duplicateormissingdatamaycauseincorrectorevenmisleadingstatistics.DatawarehouseneedsconsistentintegrationofqualitydataDataextraction,cleaning,andtransformationcomprisesthemajorityoftheworkofbuildingadatawarehouse2022/12/93为什么数据预处理重要?Noqualitydata,no2022/12/94数据预处理的主要内容：2022/12/74数据预处理的主要内容：2022/12/9数据预处理的主要内容一、原始数据的表述二、数据清理三、数据变换四、元组的归约五、属性的归约2022/12/952022/12/7数据预处理的主要内容一、原始数据的表述20数据样本是数据挖掘过程的基本组成部分。一、原始数据的表述2022/12/96每个样本都用几个特征来描述，每个特征有不同类型的值。数据样本是数据挖掘过程的基本组成部分。一、原始数据的表述202022/12/92022/12/9常见的数据类型有：数值型和分类型。数值型包括实型变量和整型变量注：具有数值型值的特征有两个重要的属性：其值有顺序关系和距离关系。72022/12/72022/12/7常见的数据类型有：数值型2022/12/92022/12/9一个有两个值的分类型变量:分类型变量的两个值可以平等或不平等。原则上可以转化成一个二进制的数值型变量，这种数值型变量有两个值：0或1；而有N值的分类型变量原则上可以转化成一个二进制的数值型变量，这种数值型变量有N个值。82022/12/72022/12/7一个有两个值的分类型变量2022/12/92022/12/9例如：如果变量“眼睛颜色”有4个值：黑色、蓝色、绿色、褐色。

特征值编码黑色1000

蓝色0100

绿色0010

褐色000192022/12/72022/12/7例如：如果变量“眼睛颜色2022/12/92022/12/9变量的分类：连续型变量和离散型变量。连续型变量也认为是定量型或是量度型，是指在一定区间内可以任意取值的变量。离散型变量也叫定性型变量，是指全部可能取到的不相同的值是有限个的变量。注：一种特殊类型的离散型变量是周期变量，例如：星期、月和年中的日期。102022/12/72022/12/7变量的分类：连续型变量和2022/12/92022/12/9与时间有关的数据分类：静态数据——数据不随时间变化而变化动态数据（时间数据）——随时间变化而变化的属性。注：大多数数据挖掘方法更适用于静态数据，在对动态数据进行挖掘时要有特殊的考虑和预处理。112022/12/72022/12/7与时间有关的数据分类：12022/12/9二、数据清理——缺失值的填补2022/12/9对数据挖掘的实际应用而言，即使数据量很大，具有完整数据的案例也非常少，这样就面临数据的缺失问题。应用数据挖掘方法之前如何处理这样现象，最简单的办法是减少数据集，去掉所有有缺失值的样本。如果我们不想扔掉这些有缺失值的样本，就必须找到它们的缺失值，用什么方法来实现呢？填补缺失值。122022/12/7二、数据清理——缺失值的填补2022/122022/12/91、单一填补法（1）均值填补法。均值填补法是根据与含缺失值的目标属性相关性高的其它属性的信息将样品分为若干组，然后分别计算各组目标属性的均值，将各组均值作为组内所有缺失项的填补值。均值填补的优点是操作简便，并且可以有效地降低其点估计的偏差。但它的缺点也比较突出：首先，由于同组中的缺失值由同一个值填补，填补结果歪曲了目标属性的分布；其次，也导致在均值和总量估计中对方差的低估。2022/12/9132022/12/71、单一填补法2022/12/713例：2022/12/914例：2022/12/714均值填补：2022/12/915均值填补：2022/12/7152022/12/9（2）随机填补法。随机填补法是采用某种概率抽样的方式，从有完整信息的元组中抽取缺失数据的填补值的方法。它虽然能够避免均值填补中填补值过于凝集以及容易扭曲目标属性分布的弱点，使得填补值的分布与真值分布更为接近。但它却增大了估计量的方差，并且稳定性不够。2022/12/9162022/12/7（2）随机填补法。2022/12/7162022/12/9（3）热卡填补法。热卡填补法（hotdeckimputation）是规定一个或多个排序属性，按其观察值大小对全部观察单位排序，如果选择的是两个以上的属性，排序按属性的入选顺序依次进行。排序属性值完全相同的观察单位称为匹配，缺失值就用与之匹配的观察单位的属性值来填补。如果有多例相匹配，可取第一例或随机取其一。如果没有相匹配的，可以每次减少一个排序属性，再找相匹配的元组。如果直到最后一个排序属性，还没有找到相匹配的，则需要重新规定排序属性。2022/12/917项目性别年龄学生身分收入办卡1男>45否高会2女31~45否高会3女20~30是低会4男<20是低不会5女20~30是中不会6女20~30否中会7女31~45否高会8男31~45是中不会9男31~45否中会10女<20是低会2022/12/7（3）热卡填补法。2022/12/717项2022/12/9（4）回归填补法。回归填补法是指在现有观察值基础上，以含有缺失值的目标属性为因变量，以与目标属性相关性高的其它属性为自变量，建立最小二乘回归模型或判别模型，以估计缺失值。注意：以上几种方法都存在扭曲样本分布的问题，如均值填补会降低属性之间的相关关系，回归填补则会人为地加大变量之间的相关关系等。2022/12/9182022/12/7（4）回归填补法。2022/12/718例：2022/12/919例：2022/12/7192022/12/92022/12/9（二）异常值（孤立点）探测在大型数据集中，通常存在着不遵循数据模型的普遍行为的样本，这些样本和其他残余部分数据有很大不同或不一致，叫做异常点。异常点可能是由测量误差造成的，也可能是数据故有的可变性结果。例如：在检测银行交易中的信用卡欺诈行为时，异常点是可能揭示欺诈行为的典型例子。202022/12/72022/12/7（二）异常值（孤立点）探2022/12/92022/12/9异常值的探测方法第一，一维样本异常点的检测方法例如：如果所给的数据集用20个不同的值描述年龄特征：3,56,23,39,156,52,41,22,9,28,139,31,55,20,-67,37,11,55,45,37均值=39.9;标准差=45.65阈值=均值±2×标准差那么，所有在[-54.1,131.2]区间以外的数据都是潜在的异常点。根据实际可以把区间缩减到[0,131.2]，由这个标准发现3个异常点：156,139,-67。212022/12/72022/12/7异常值的探测方法第一，一2022/12/92022/12/9第二，基于距离的异常点检测（二维以上数据）例如：数据集为：S={S1,S2,S3,S4,S5,S6,S7}＝{(2,4),(3,2),(1,1),(4,3),(1,6),(5,3),(4,2)}

欧氏距离d=[(X1-X2)2+(Y1-Y2)2]1/2

取阈值距离为d=3222022/12/72022/12/7第二，基于距离的异常点检异常点2022/12/923异常点2022/12/723根据所用程序的结果和所给的阈值，可选择S3和S5作为异常点。2022/12/924根据所用程序的结果和所给的阈值，可选择S3和S5作为异常点。2022/12/9第三：基于分类预测模型的异常值探测异常值的探测也可以认为是一类特殊的分类问题。因为对于一般的分类问题，考虑的是如何将各种类别有效地分开，而在异常值探测中，分类的目标是准确地描述总体的正常行为特征，在此之外大范围的其它对象被视为异常值。其基本思想是：对总体的特征建立分类模型，形成正常行为的特征库；然后针对新的数据判断其是否属于正常行为，从而认定其是否与总体偏离，发生偏离的即是异常值。根据所建立的分类器的不同，异常值的探测方法有以下几种：决策树分类；贝叶斯分类；神经网络分类；聚类。2022/12/9252022/12/7第三：基于分类预测模型的异常值探测20222022/12/9异常值探测的应用信用卡、保险行业以及电信用户欺诈行为的探测。异常值探测对于欺诈行为的发现，主要是基于这样的思想：任何人在使用信用卡、投保和电信消费的正常行为都是有一定的规律的，并且可以通过这些行为产生的信息总结出这些规律；由于欺诈行为和正常的行为存在严重的差异，检查出这些差异就可以探测出是否存在欺诈发生。因此可以认为，欺诈行为的发现过程就是一种异常数据的挖掘过程。2022/12/9262022/12/7异常值探测的应用信用卡、保险行业以及电信用2022/12/9具体的实现途径是：利用聚类、神经网络和决策树等分类方法，通过分析用户的购买、投保或消费习惯，细分客户，以此分辨出偏离模式的信用卡欺诈行为；然后，推导出合法交易的定义，建立模型；利用模型来分析一个新的交易是合法还是非法。也可以通过六西格玛探测、聚类等方法，寻找出与正常投保行为有极大差别的不正常行为，即有可能的欺诈行为。除了利用上述技术对异常数据进行识别外，还可以通过关联规则的Apriori算法寻找异常数据间的隐含模型，从而达到反欺诈的目的。2022/12/9272022/12/7具体的实现途径是：利用聚类、神经网络和决策2022/12/9例如：对电信用户的欺诈行为探测的具体做法是：首先，将目标属性定为无意欠费客户和恶意欠费两类；其次，选择属性作为输入属性，通常包括服务合同属性（如服务类型、服务时间、交费类型等）、客户的基本状态（如性别、年龄、收入、婚姻状况、受教育年限/学历、职业、居住地区等）以及经常或定期改变的数据（如每月消费金额、交费纪录等）；然后，将分类方法用于预先选定的包含客户欠费状态的训练集中，从而挖掘归纳出规则集；最后，利用所获取的规则，对电信企业新用户的缴费情况进行预测分类，从而达到预防欺诈的目的。2022/12/9282022/12/7例如：对电信用户的欺诈行为探测的具体做法是2022/12/9三、数据变换数据变换是将数据转换成适合于挖掘的形式。数据变换可能涉及到如下内容：数据规范化数据平滑数据概化2022/12/9292022/12/7三、数据变换数据变换是将数据转换成适合于挖为什么要进行标准化？一些数据挖掘方法，需要对数据进行标准化以获得最佳的效果。例如，对于分类算法，如涉及神经网络的算法或诸如最临近分类和聚类的距离度量分类算法，都需要将训练样本属性度量输入值规范化，这样有助于加快学习阶段的速度。对于基于距离的方法，规范化可以帮助防止具有较大初始值域的属性与具有较小初始值域的属性相比，权重过大。2022/12/930（一）规范化（标准化）为什么要进行标准化？一些数据挖掘方法，需要对数据进行标准化以小数缩放移动小数点，但是要仍然保持原始数据的特征。小数点的移动位数依赖于X的最大绝对值。典型的缩放是保持数值在-1和1范围内，可以用格式描述：1、小数缩放规范化是指通过将属性数据按比例缩放，使之落入一个小的特定区间，如0.0到1.0，对属性规范化。2022/12/931小数缩放移动小数点，但是要仍然保持原始数据的特征。小数点的移2、最小-最大规范化2022/12/932最小-最大规范化是对原始数据进行线性变换。最小-最大规范化的格式：

从而将X的值映射到[0，1]中。2、最小-最大规范化2022/12/732最小-最大规范化是2022/12/93、标准差规范化（Z-SCORE规范化）标准差规范化是将某个属性的值基于其平均值和标准差进行规范化。标准差规范化的格式是其中：是均值；是标准差。注意：该方法适用于当属性X的最大和最小值未知，或孤立点左右了最大-最小规范化的情况下。2022/12/9332022/12/73、标准差规范化（Z-SCORE规范化）标为什么要进行数据的平滑？一个数值型的特征可能包含许多不同的值。对许多数据挖掘技术来说，这些值之间小小的区别并不重要，但可能会降低挖掘方法的性能并影响最终的结果。因此，对变量的值进行平滑处理很重要。2022/12/934（二）数据平滑(离散化)为什么要进行数据的平滑？一个数值型的特征可能包含许多不同的值2022/12/92022/12/9数据平滑：是指去掉数据中的噪声。这种技术包括分箱技术、聚类和回归。35例如：进行圆整处理。如果给定特征的值的集合是平滑后的集合是2022/12/72022/12/7数据平滑：是指去掉数据中2022/12/91、分箱分箱方法是通过考察“邻居”来平滑存储数据的值。存储的值被分布到一些“桶”或“箱”中。由于分箱方法参考的是相邻的值，因此，它进行的是局部平滑。分箱方法有以下几种：按箱平均值平滑按箱中值平滑按箱边值平滑。2022/12/9362022/12/71、分箱分箱方法是通过考察“邻居”来平滑存2022/12/9例如：某产品的价格排序后的数据为：4、8、15、21、21、24、25、28、34。首先，将上述数据划分为等深的箱：

箱1：4、8、15

箱2：21、21、24

箱3：25、28、34（1）按箱中值平滑：箱1：8、8、8

箱2：21、21、21

箱3：28、28、282022/12/9372022/12/7例如：某产品的价格排序后的数据为：4、8、2022/12/9排序后的数据为：4、8、15、21、21、24、25、28、34。

箱1：4、8、15

箱2：21、21、24

箱3：25、28、34（2）按箱平均值平滑：箱1：9、9、9

箱2：22、22、22

箱3：29、29、292022/12/9382022/12/7排序后的数据为：4、8、15、21、21、排序后的数据为：4、8、15、21、21、24、25、28、34。

箱1：4、8、15

箱2：21、21、24

箱3：25、28、34（3）按箱边界值平滑：箱1：4、4、15

箱2：21、21、24

箱3：25、25、342022/12/939对于按箱边值平滑来说，箱中的最大和最小值被视为箱边界。箱中每一个值被最近的边界值替换。排序后的数据为：4、8、15、21、21、24、25、28、2、回归xyy=x+1X1Y1Y1’2022/12/9402、回归xyy=x+1X1Y1Y1’2022/12/3、通过自然划分分段3-4-5规则可以将数值数据划分成相对一致和“自然”区间。如果一个区间在最高有效位上包含3,6,7或9个不同的值，则将该区间划分为3个区间（对于3、6和9划分为3个等宽区间；对于7，按2-3-2分组，划分为3个区间）；如果最高有效位上包含2,4或8个不同的值，则将区间划分为4个等宽区间；如果最高有效位上包含1,5或10个不同的值，则将区间划分为5个等宽区间.2022/12/9413、通过自然划分分段3-4-5规则可以将数值数据划分成相对一EXAMPLE(-$400-$5,000)(-$400-0)(-$400--$300)(-$300--$200)(-$200--$100)(-$100-0)(0-$1,000)(0-$200)($200-$400)($400-$600)($600-$800)($800-$1,000)($2,000-$5,000)($2,000-$3,000)($3,000-$4,000)($4,000-$5,000)($1,000-$2,000)($1,000-$1,200)($1,200-$1,400)($1,400-$1,600)($1,600-$1,800)($1,800-$2,000)msd=1,000 Low=-$1,000 High=$2,000Step2:Step4:Step1:-$351 -$159 profit $1,838 $4,700 MinLow(i.e,5%-tile) High(i.e,95%-0tile)Maxcount(-$1,000-$2,000)(-$1,000-0)(0-$1,000)Step3:($1,000-$2,000)2022/12/942EXAMPLE(-$400-$5,000)(-$400-为什么要进行数据概化？数据库通常存放有大量的细节数据，但我们通常希望看到的是以简洁的、更一般的描述形式来观察数据的特点。例如：对于一个销售经理来说，面对顾客数据库，他可能不想考察每个顾客的事务，而更愿意概化到高层的数据，比如说，根据地区按顾客的分组汇总，来观察每组顾客的购买频率和顾客的收入，以此来分析区域差异。2022/12/943（三）数据概化为什么要进行数据概化？数据库通常存放有大量的细节数据，但我们2022/12/9数据概化：是一个过程，它将大的任务相关的数据集从较低的概念层抽象到较高的概念层。使用概念分层，用高层次概念替换低层次“原始”数据。例如，分类的属性，“street”，可以概化为较高层的概念，如“city”或“country”；再如，“年龄”可以概化为“青年”、“中年”和“老年”等。2022/12/9442022/12/7数据概化：是一个过程，它将大的任务相关的数2022/12/9四、元组的归约为什么要进行离散化？在机器学习和数据挖掘中，已经发展了处理离散型数据的很多算法，如决策树、关联规则及基于粗糙集理论的许多方法，而这些算法对于连续型数据却不适用；另外，有些算法即使能处理连续型数据，挖掘和学习也没有处理离散型数据有用和有效。离散化后可以达到归约元祖的目的。2022/12/9452022/12/7四、元组的归约为什么要进行离散化？2022连续属性的离散化就是将数值属性的值域划分为若干子区间，每个区间对应一个离散值。离散化方法依据不同的标准主要有以下几种划分：有监督和无监督、动态和静态、全局和局部、自顶向下和自底向上等。2022/12/946连续属性的离散化就是将数值属性的值域划分为若干子区间，每个区2022/12/9按照离散化过程中是否考虑类别信息，可以将离散化算法分为有监督算法和无监督算法。有监督算法是其输入样本集中除了待离散化的数值属性外，还有一个或多个离散型的类别属性。这种算法在离散化时，将类别信息作为参考。无监督离散化是在离散化过程中不考虑类别信息的方法，其输入样本集中仅含有待离散化的属性。早期的等宽、等频的离散化方法是无监督方法的典型代表。无监督的方法的缺陷在于它对分布不均匀的数据不适用，对异常点比较敏感。2022/12/9471、有监督离散化和无监督离散化2022/12/7按照离散化过程中是否考虑类别信息，可以将离2、动态和静态离散化动态离散化方法是在建立分类模型的同时对连续特征进行离散化，例如，C4.5算法。在静态离散化方法中，离散化是先于分类任务进行的。2022/12/9482、动态和静态离散化动态离散化方法是在建立分类模型的同时对连2022/12/9自顶向下的方法是离散化开始于空的分割点（分裂点）列表，通过“分裂”区间增加新的分割点到列表中的离散化过程。自底向上是开始于属性的全部连续值作为分割点的完全列表，以通过“合并”区间来移除它们中的一部分作为离散化的过程。2022/12/9493、自顶向下和自底向上2022/12/7自顶向下的方法是离散化开始于空的分割点（分4、局部和全局离散化局部离散化方法是仅对每一个属性的属性值进行划分，如等宽区间法、等频区间法和最大熵法等。全局离散化则是考虑全部条件属性的属性值进行划分的方法，如全局聚类分析方法。2022/12/9504、局部和全局离散化局部离散化方法是仅对每一个属性的属性值进2022/12/9（二）典型离散化的过程一个局部单个属性的离散化过程主要由以下四步组成（自底向上）：（1）对要离散化的属性的连续值排序。（2）根据一定的规则产生候选断点集，构造初始区间。（3）按照合并的规则，合并相邻的初始区间。（4）制定停止标准，使得合并一直进行到符合停止标准为止。2022/12/9512022/12/7（二）典型离散化的过程一个局部单个属性的离2022/12/9（三）离散化方法的评价（1）区间的总数。这是对模型简洁性的要求。理论上来说，离散得到的区间数越少越好，便于理解；但区间数的减少另一方面也会导致数据的可理解性变差。（2）由离散化引起的不一致性的数目。所谓不一致性是指当两个样本所有的条件属性取值相同而类别属性的取值不同时，就称这两个样本是不一致的。离散化后的不一致性数目至少应该比在离散化前原始数据的不一致性数目少，且不一致性数目越少越好。（3）预测精确度。根据训练样本集预测新样本类别的准确率即是预测精确度，预测精确度越高，当然就说明此离散化方法越好。2022/12/9522022/12/7（三）离散化方法的评价（1）区间的总数。22022/12/91、直方图方法直方图方法是将要离散化的变量值从小到大排序，然后对这些数值进行分组，最后，对这些进行赋值。依据分组的方式该方法又可以分为等宽和等频两种。等宽是指所分组是等距式分组。等频是指所有的分组的次数是相等的。2022/12/9（四）具体的离散化方法532022/12/71、直方图方法2022/12/7（四）具体2022/12/9采用Iris样本集进行统计模拟（数据来源：加州大学UCIMachineLearning的数据库中Iris样本集）。Iris样本集是对3种鸢尾花：刚毛鸢(yuan)尾花、变色鸢尾花、佛吉尼亚鸢尾花各抽取50个样本。属性是sepallengthincm萼片长度、sepalwidthincm萼片宽度、petallengthincm花瓣长度、petalwidthincm花瓣宽度。2022/12/9等宽直方图离散化的应用542022/12/7采用Iris样本集进行统计模拟（数据来源：我们现在以花萼长（

sepallengthincm）属性为例，来进行连续型值属性的离散化。具体步骤为如下：（1）对要离散化的属性的连续值排序。（2）根据一定的规则产生候选断点集，构造初始区间。2022/12/955我们现在以花萼长（sepallengthincm）2022/12/92022/12/9数值频数数值频数数值频数数值频数数值频数4.315105.786.477.114.435.195.876.557.234.515.245.936.627.314.645.31666.787.414.725.466.166.837.614.855.576.246.947.744.965.666.39717.91562022/12/72022/12/7数值频数数值频数数值频数2022/12/9（3）按照合并的规则，合并相邻的初始区间。根据斯特杰公式有：n=1+3.3lgN=1+3.3lg150≈8那么，组距为d=R/n=(7.9-4.3)/8=0.45现分组如右：2022/12/9分组频数4.3~4.75114.75~5.2305.2~5.65245.65~6.1246.1~6.55316.55~7177~7.4577.45~7.96572022/12/7（3）按照合并的规则，合并相邻的初始区间。2022/12/9（4）制定停止标准，使得合并一直进行到符合停止标准为止。（5）防止过度拟合。为防止过度拟合，应使得每个区间的频数大于等于总体单位数的平方根。sqrt(150)≈122022/12/9582022/12/7（4）制定停止标准，使得合并一直进行到符合2022/12/959分组频数4.3~4.75114.75~5.2305.2~5.65245.65~6.1246.1~6.55316.55~7177~7.4577.45~7.962022/12/759分组频数4.3~4.75114.75~2022/12/9进行重新分组：使得每个区间的频数大于122022/12/9分组频数赋值4.3~5.24115.2～6.14826.1~74837~7.9134602022/12/7进行重新分组：使得每个区间的频数大于1222022/12/92、聚类聚类算法可以用来将数据划分为群或簇。每一个簇形成概念分层的一个节点，而所有的节点在同一个概念层。每一个簇可以进一步分成若干子簇，形成较低的概念层簇也可以聚集在一起，以形成分层结构中较高的概念层。2022/12/9612022/12/72、聚类聚类算法可以用来将数据划分为群或簇具体方法是：首先，将元组划分为群或簇，使得在每一个簇中的对象“类似”，但与其他簇中的对象“不类似”。其次，为这些簇赋值，所有包含在同一个簇中的对象的值相同。注意：这种方法的有效性依赖于数据的性质，数据必须能够组织成不同的聚类；另外，它只适用于无监督的离散化。2022/12/962具体方法是：2022/12/7622022/12/9例如：见IRIS样本集，在不考虑类别信息的情况下，现用聚类方法离散化属性“sepallengthincm”。有：2022/12/9分组频数赋值4.3~5.44615.4~6.03726.0~6.53236.5~7.9354632022/12/7例如：见IRIS样本集，在不考虑类别信息的2022/12/93、基于熵的离散化方法信息熵的概念信息论中的熵：是信息的度量单位，是一种对属性“不确定性的度量”。属性的不确定性越大，把它搞清楚所需要的信息量也就越大，熵也就越大。Shannon公式：其中，I(A)度量事件A发生所提供的信息量，称之为事件A的自信息，P(A)为事件A发生的概率。2022/12/9642022/12/73、基于熵的离散化方法信息熵的概念2022如果一个属性有N个可能的取值，且它们出现的概率分别为，那么这个属性的信息熵为：一个系统越是有序，信息熵就越低。2022/12/965如果一个属性有N个可能的取值，且它们出现的概率分别为贪心算法所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。2022/12/966贪心算法所谓贪心算法是指，在对问题求解时，总是做出在当前看来例如：假设有四种硬币，它们的面值分别为二角五分、一角、五分和一分。现在要找给某顾客六角三分钱。这时，我们会不假思索地拿出2个二角五分的硬币，1个一角的硬币和3个一分的硬币交给顾客。这种找硬币方法与其他的找法相比，所拿出的硬币个数是最少的。这里，我们下意识地使用了这样的找硬币算法：首先选出一个面值不超过六角三分的最大硬币，即二角五分；然后从六角三分中减去二角五分，剩下三角八分；再选出一个面值不超过三角八分的最大硬币，即又一个二角五分，如此一直做下去。这个找硬币的方法实际上就是贪心算法。顾名思义，贪心算法总是作出在当前看来是最好的选择。也就是说贪心算法并不从整体最优上加以考虑，它所作出的选择只是在某种意义上的局部最优选择。2022/12/967例如：假设有四种硬币，它们的面值分别为二角五分、一角、五分和但是：如果硬币的面值改为一分、五分和一角一分3种，而要找给顾客的是一角五分钱。还用贪心算法，我们将找给顾客1个一角一分的硬币和4个一分的硬币。然而3个五分的硬币显然是最好的找法。显然贪心算法不是对所有问题都能得到整体最优解，但对范围相当广的许多问题它能产生整体最优解。如，图的单源最短路径问题。在一些情况下，即使贪心算法不能得到整体最优解，但其最终结果却是最优解的很好的近似解。2022/12/968但是：2022/12/768基于熵的离散化方法是通过贪心算法搜寻给定数据区间内的具有熵值最小的数据点作为断点。该方法将区间内的每一个数值作为候选断点，计算其熵值，然后从中选出具有最小熵值的数据点作为断点，将区间一分为二，然后再对得到的区间递归地应用以上方法进行离散化。停止准则是当得到的每个区间中的类标签都是一致时，即停止离散化过程；或者达到某个停止标准时，停止。2022/12/969基于熵的离散化方法基于熵的离散化方法是通过贪心算法搜寻给定数据区间内的具有熵值2022/12/9基于熵的离散化方法2022/12/9一个给定的样本分类所需要的信息某种划分的期望信息70项目性别年龄学生身分收入办卡1男>45否高会2女31~45否高会3女20~30是低会4男<20是低不会5女20~30是中不会6女20~30否中会7女31~45否高会8男31~45是中不会9男31~45否中会10女<20是低会2022/12/7基于熵的离散化方法2022/12/7一个给2022/12/9Sepallen:(cm)d1d2d3Sepallen:(cm)d1d2d34.31006.10424.43006.20224.51006.30364.64006.40254.72006.50144.85006.60204.94116.703558206.80125.18106.90135.231070105.31007.10015.45107.20035.52507.30015.60517.40015.72517.60015.81337.70045.90217.900160422022/12/9举例：IRIS样本集的具体步骤712022/12/7Sepallen:(cm)d1d2d3Se2022/12/9首先，从第一个分割点开始，将属性值分为两部分即[4.3,4.4)和[4.4,7.9]，则分割后新的类别熵为：

2022/12/9区间d1d2d3合计[4.3,4.4)1001[4.4,7.9]495050149722022/12/7首先，从第一个分割点开始，将属性值分为两部2022/12/9以此类推，如把属性值分为[4.3,5.6)和[5.6,7,9]两个区间时，产生的新的类别熵为：2022/12/9区间d1d2d3合计[4.3,5.6)4711159[5.6,7.9]3394991732022/12/7以此类推，如把属性值分为[4.3,5.6)2022/12/9对所有的分割点将属性值分为两个区间的新类别熵计算出来，有2022/12/9d1d2d3新的类别熵d1d2d3新的类别熵4.31000.4739260420.349374.43000.464086.10420.358754.51000.459666.20220.367514.64000.446796.30360.392024.72000.439546.40250.409654.85000.420436.50140.422754.94110.421886.60200.4204958200.398366.70350.436735.18100.362776.80120.439835.23100.349366.90130.443085.31000.3424770100.435835.45100.311227.10010.439545.52500.309387.20030.450345.60510.327887.30010.453855.72510.321787.40010.457305.81330.330407.60010.460715.90210.337427.70040.473927.9001742022/12/7对所有的分割点将属性值分为两个区间的新类别2022/12/9从上表中可以看到，将属性值分为[4.3,5.6)和[5.6,7,9]两个区间时，类别熵最小，因此首先把属性值分为两大部分。按照上述步骤，

分别再找出区间[4.3,5.6)和[5.6,7,9]的二分点，以此类推，逐渐将区间分割为更小的区间，直到满足某个终止条件为止。2022/12/9752022/12/7从上表中可以看到，将属性值分为[4.3,52022/12/92022/12/9d1d2d3新的类别熵d1d2d3新的类别熵4.31000.4739260420.349374.43000.464086.10420.358754.51000.459666.20220.367514.64000.446796.30360.392024.72000.439546.40250.409654.85000.420436.50140.422754.94110.421886.60200.4204958200.398366.70350.436735.18100.362776.80120.439835.23100.349366.90130.443085.31000.3424770100.435835.45100.311227.10010.439545.52500.309387.20030.450345.60510.327887.30010.453855.72510.321787.40010.457305.81330.330407.60010.460715.90210.337427.70040.473927.9001762022/12/72022/12/7d1d2d3新的类2022/12/92022/12/94、CHIMERGE算法772022/12/72022/12/74、CHIMERGE算法2022/12/92022/12/978Sepallen:(cm)d1d2d3Sepallen:(cm)d1d2d34.31006.10424.43006.20224.51006.30364.64006.40254.72006.50144.85006.60204.94116.703558206.80125.18106.90135.231070105.31007.10015.45107.20035.52507.30015.60517.40015.72517.60015.81337.70045.90217.900160422022/12/72022/12/778Sepallen:(2022/12/92022/12/9792022/12/72022/12/7792022/12/92022/12/9802022/12/72022/12/7802022/12/9应用采用Iris样本集进行统计模拟。现在以花萼长（

sepallengthincm）属性为例，来进行连续型值属性的离散化。2022/12/9812022/12/7应用采用Iris样本集进行统计模拟。现在以2022/12/9Sepallen:(cm)d1d2d3Sepallen:(cm)d1d2d34.31006.10424.43006.20224.51006.30364.64006.40254.72006.50144.85006.60204.94116.703558206.80125.18106.90135.231070105.31007.10015.45107.20035.52507.30015.60517.40015.72517.60015.81337.70045.90217.900160422022/12/9822022/12/7Sepallen:(cm)d1d2d3Se2022/12/9具体步骤：（1）观察各区间，先将类分布完全相同的区间进行合并。2022/12/9区间d1d2d3区间d1d2d3[4.3,4.9)1600[5.7,5.9)384[4.9,5.0)411[5.9,6.6)01822[5.0,5.3)1940[6.6,6.7)020[5.3,5.4)100[6.7,7.0)0510[5.4,5.6)760[7.0,7.1)010[5.6,5.7)051[7.1,7.9)0012832022/12/7具体步骤：（1）观察各区间，先将类分布完全2022/12/92022/12/9（2）考察[4.3,4.9)与[4.9,5)，看其是否能够合并？两区间的卡方统计量和为5.87，大于临界值，因此两区间不能合并。区间d1d2d3求和[4.3,4.9)160016[4.9,5)4116求和201122区间eijeijeij[4.3,4.9)14.5450.7270.727[4.9,5)5.4550.2730.273区间χ2[4.3,4.9)0.1450.7270.7271.6[4.9,5)0.3881.9391.9394.267表1：两区间的列联表表2：计算各项的eij表3：两区间的卡方统计量值842022/12/72022/12/7（2）考察[4.3,4.2022/12/92022/12/9（3）继续考察区间[4.9,5)与[5.0,5.3)，看其是否能够合并，直到所有的区间卡方统计量大于阀值为止。852022/12/72022/12/7（3）继续考察区间[4.2022/12/9五、属性的归约属性的归约包括两类方法：属性的提取和属性子集的选择。（一）属性的提取属性的提取是通过映射（或变换）的方法，将高维的属性空间压缩为低维的属性空间，即将原始属性变换为较少的新属性。此时，“较少的新属性”是原始属性的某种线性组合，也可以称为“二次属性”。2022/12/9862022/12/7五、属性的归约属性的归约包括两类方法：属性2022/12/9属性提取的最大的优点在于：这样的线性组合比属性选择中的最优子集有更好的判别能力。但相应的问题是，这样的线性组合的实际意义却不明显，有时难以解释。到目前为止，对属性提取的研究主要是从线性和非线性的数据变换角度进行的。用的比较多的线性数据变换方法是：主成分分析、因子分析、判别分析、聚类分析、多维标度、投影寻踪以及小波变换等。非线性的数据变换，主要是基于自组织映射的属性抽取方法、基于核的主成分分析和基于核的判别分析方法等。2022/12/9872022/12/7属性提取的最大的优点在于：这样的线性组合比2022/12/91、主成分分析（因子分析）主成分分析和因子分析都是多元统计分析中的一种常用方法，是数学上处理降维的一种方法。主成分分析的基本思想：设法将原始属性重新组合成一组新的互相无关的几个综合属性，同时根据需要从中选取少数几个综合属性来尽可能多地反映原来指标的信息。综合指标的选取使用的是方差最大法。2022/12/9882022/12/71、主成分分析（因子分析）主成分分析和因子2、因子分析因子分析的基本思想：通过变量（或样本）的相关系数矩阵内部结构的研究，找出能控制所有变量的少数几个因子去描述多个变量之间的相关关系；然后，根据相关性的大小把变量分组，使得同组内的变量之间相关性较高，但不同组之间相关性较低。2022/12/9892、因子分析因子分析的基本思想：2022/12/7892022/12/9主成分分析和因子分析的对比数据标准化建立指标之间的相关系数矩阵R求R的特征值和特征向量计算累计贡献率大于85%的前n个特征值的特征向量根据特征向量建立n个主成分（由变量的线性组合而成）2022/12/9根据n个特征向量建立因子载荷阵对因子载荷阵实行方差最大旋转按照变量在每个因子上载荷阵的高低，分类。主成分分析因子分析由因子的线性组合来解释变量902022/12/7主成分分析和因子分析的对比数据标准化建立指主成份分析和因子分析的优点因子（主成份）之间的线性相关关系不显著。主成份参与数据建模能够有效地解决变量多重共线性等分析应用带来的问题。因子能够反映原有变量的绝大部分信息。因子的方差贡献和方差贡献率是衡量因子重要性的关键指标。该值越高，说明相应因子的重要性越高。aij因子载荷反映了某i个变量在第j因子上的相对重要性。因子得分是因子分析的最终体现。在后续的分析中可以用因子变量代替原有变量进行建模，或者利用因子变量对样本分类、评价或排序等研究。2022/12/991主成份分析和因子分析的优点因子（主成份）之间的线性相关关系不3、聚类分析——K均值聚类分析K均值法是麦奎因（MacQueen，1967）提出的，这种算法的基本思想是将每一个样品分配给最近中心（均值）的类中.具体的算法至少包括以下三个步骤：

1．将所有的样品分成K个初始类；

2．通过欧氏距离将某个样品划入离中心最近的类中，并对获得样品与失去样品的类，重新计算中心坐标；

3．重复步骤2，直到所有的样品都不能再分配时为止。2022/12/9923、聚类分析——K均值聚类分析K均值法是麦奎因（MacQu2022/12/9（二）属性子集的选择属性子集的选择是通过删除不相关的属性来减少数据量。属性子集选择的目标是找出最小属性集，使得数据类的概率分布尽可能地接近使用所有属性的原分布。2022/12/9932022/12/7（二）属性子集的选择属性子集的选择是通过删2022/12/9属性子集的选择方法一般有两个组成部分：一是高效率的属性子集搜索策略，即在允许的时间内，用以找出最小的、最能描述类别的属性组合的搜索方法；二是确定评价函数，是衡量属性组合是否最优的标准。属性子集的选择一般分两步进行：首先，产生属性子集；然后，对子集进行评价，如果满足停止条件则停止，否则重复前述两步直到条件满足为止。2022/12/994通过该标准，要能够衡量哪组属性子集的分类效果最好，即使得数据类的概率分布尽可能地接近使用所有属性的原分布；或者能够衡量哪组属性子集的分类效果最好，即最能够代表全部的属性集合对样本的划分。2022/12/7属性子集的选择方法一般有两个组成部分：202022/12/91、搜索策略按照搜索属性形成属性子集的方式，搜索策略可以分为：穷举法、启发式和随机搜索。启发式搜索即贪心算法。基本的启发式属性选择算法主要有：逐步向前选择（SFS）、逐步向后选择（SBG）以及向前选择和向后删除相结合的方法等。2022/12/9952022/12/71、搜索策略按照搜索属性形成属性子集的方式2022/12/9（1）逐步向前选择逐步向前选择方法是一种自下而上的搜索方法，它是由空属性集开始，依次从未入选的属性中选择一个属性，使它与已入选的属性组合在一起时所得的评价函数达到最大值（或最小值，依评价函数选取的不同，取最大或最小值），直到评价函数的值不再增加（或减小）时为止，亦或者达到指定的属性数为止。2022/12/99696能够衡量哪组属性子集的分类效果最好，最能够代表全部的属性集合对样本的划分。2022/12/7（1）逐步向前选择2022/12/7969这种算法的不足是：在算法中虽然考虑了所选属性与已入选属性之间的相关性，但却未考虑未入选属性之间的统计相关性，并且一旦某个属性已入选，即使由于后加入的属性使它变为多余，也无法再剔除。2022/12/997这种算法的不足是：在算法中虽然考虑了所选属性与已入选属性之间2022/12/9（2）逐步向后删除逐步向后删除是一种自上而下搜索的方法，它由整个属性集开始，在每一步删除掉在属性集中最坏的属性，评判属性好坏的准则是，如果剔除该属性后，属性集的评价函数达到最大（或最小）值，那么这个属性是最坏的。2022/12/998982022/12/7（2）逐步向后删除2022/12/7989（3）逐步向前选择和逐步向后删除相结合向前选择和向后删除结合的方法则是将向前选择和向后删除方法结合在一起，每一步选择一个最好的属性，并在其剩余的属性中删除掉一个最坏的属性。这两种方法也存在着与逐步向前选择方法相同的缺点。2022/12/999（3）逐步向前选择和逐步向后删除相结合2022/12/7992022/12/9（4）广义逐步向前选择广义逐步向前选择方法是逐步向前选择方法的推广，针对逐步向前选择方法“未能考虑未入选属性之间的统计相关性”的缺点，该方法每次从未入选的属性中挑选的不止是一个属性而是多个属性。广义逐步向前选择方法的缺点是：计算量要比逐步向前选择方法大很多，并且也未解决“一旦某个属性已入选，即使由于后加入的属性使它变为多余，也无法再剔除”的问题。2022/12/91001002022/12/7（4）广义逐步向前选择2022/12/712022/12/92、属性子集选择中的评价函数在属性子集选择中，找出最具代表性的属性子集需要一个子集优劣的评价标准。通过该标准，使得数据类的概率分布尽可能地接近使用所有属性的原分布；如果没有类属性，则能够衡量哪组属性子集的分类效果最好，最能够代表全部的属性集合对样本的划分。这种评价标准以函数的形式表示出来就是评价函数。它在模式识别中，也被称为类别可分性判据。2022/12/91012022/12/72、属性子集选择中的评价函数在属性子集选择2022/12/9评价函数在属性子集的选择中是非常关键的，不同的评价函数可能会得出不同的结果。评价函数的建立形式是多种多样的：基于距离的评价函数、基于相关性的评价函数（无监督属性子集的选择方法）。基于一致性的评价函数、分类错误率以及基于信息熵的评价函数等(有监督属性子集选择方法)。2022/12/91022022/12/7评价函数在属性子集的选择中是非常关键的，不3、评价函数的要求2022/12/91033、评价函数的要求2022/12/71032022/12/94、模式识别中基于距离的评价函数2022/12/91042022/12/74、模式识别中基于距离的评价函数2022/2022/12/92022/12/91052022/12/72022/12/71052022/12/9属性子集选择方法的应用主要思路：通过因子分析和相关分析为逐步向前选择算法找到每一次选用子集的最优属性。选用2004年各地区城镇居民家庭人均全年消费性支出样本集对逐步向前的属性子集选择方法进行模拟。具体步骤如下：首先，对这个样本集作KMO(Kaiser-Meyer-Olkin)检验，KMO值为0.87，表明该数据集适合作因子分析。KMO值是用于比较变量间简单相关系数和偏相关系数的指标。KMO值在0.9以上表式非常适合作因子分析，在0.8～0.9之间表示适合，在0.7～0.8表示一般，在0.6～0.7之间表示不太适合，0.6以下表示极不适合。2022/12/91062022/12/7属性子集选择方法的应用主要思路：通过因子分2022/12/91072022/12/71072022/12/9108因子初始解第二列说明提取公因子后，变量可以被因子解释的信息有多少2022/12/7108因子初始解第二列说明提取公因子后，变2022/12/92022/12/9109对样本集进行因子分析，因子分析中前2个因子的贡献率分别是74.543%和11.144%，累计贡献率为85.687%。2022/12/72022/12/7109对样本集进行因子分2022/12/92022/12/91102022/12/72022/12/71102022/12/92022/12/91112022/12/72022/12/71112022/12/92022/12/91122022/12/72022/12/71122022/12/92022/12/91132022/12/72022/12/71132022/12/92022/12/91142022/12/72022/12/71142022/12/94.数据预处理2022/12/91152022/12/74.数据预处理2022/12/71为什么要进行数据挖掘?现实世界的数据是脏的不完整:缺乏属性值，缺乏有意义的属性，或者只包含了汇总数据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.,discrepancybetweenduplicaterecords2022/12/9116为什么要进行数据挖掘?现实世界的数据是脏的2022/12/7为什么数据预处理重要?Noqualitydata,noqualityminingresults!Qualitydecisionsmustbebasedonqualitydatae.g.,duplicateormissingdatamaycauseincorrectorevenmisleadingstatistics.DatawarehouseneedsconsistentintegrationofqualitydataDataextraction,cleaning,andtransformationcomprisesthemajorityoftheworkofbuildingadatawarehouse2022/12/9117为什么数据预处理重要?Noqualitydata,no2022/12/9118数据预处理的主要内容：2022/12/74数据预处理的主要内容：2022/12/9数据预处理的主要内容一、原始数据的表述二、数据清理三、数据变换四、元组的归约五、属性的归约2022/12/91192022/12/7数据预处理的主要内容一、原始数据的表述20数据样本是数据挖掘过程的基本组成部分。一、原始数据的表述2022/12/9120每个样本都用几个特征来描述，每个特征有不同类型的值。数据样本是数据挖掘过程的基本组成部分。一、原始数据的表述202022/12/92022/12/9常见的数据类型有：数值型和分类型。数值型包括实型变量和整型变量注：具有数值型值的特征有两个重要的属性：其值有顺序关系和距离关系。1212022/12/72022/12/7常见的数据类型有：数值型2022/12/92022/12/9一个有两个值的分类型变量:分类型变量的两个值可以平等或不平等。原则上可以转化成一个二进制的数值型变量，这种数值型变量有两个值：0或1；而有N值的分类型变量原则上可以转化成一个二进制的数值型变量，这种数值型变量有N个值。1222022/12/72022/12/7一个有两个值的分类型变量2022/12/92022/12/9例如：如果变量“眼睛颜色”有4个值：黑色、蓝色、绿色、褐色。

特征值编码黑色1000

蓝色0100

绿色0010

褐色00011232022/12/72022/12/7例如：如果变量“眼睛颜色2022/12/92022/12/9变量的分类：连续型变量和离散型变量。连续型变量也认为是定量型或是量度型，是指在一定区间内可以任意取值的变量。离散型变量也叫定性型变量，是指全部可能取到的不相同的值是有限个的变量。注：一种特殊类型的离散型变量是周期变量，例如：星期、月和年中的日期。1242022/12/72022/12/7变量的分类：连续型变量和2022/12/92022/12/9与时间有关的数据分类：静态数据——数据不随时间变化而变化动态数据（时间数据）——随时间变化而变化的属性。注：大多数数据挖掘方法更适用于静态数据，在对动态数据进行挖掘时要有特殊的考虑和预处理。1252022/12/72022/12/7与时间有关的数据分类：12022/12/9二、数据清理——缺失值的填补2022/12/9对数据挖掘的实际应用而言，即使数据量很大，具有完整数据的案例也非常少，这样就面临数据的缺失问题。应用数据挖掘方法之前如何处理这样现象，最简单的办法是减少数据集，去掉所有有缺失值的样本。如果我们不想扔掉这些有缺失值的样本，就必须找到它们的缺失值，用什么方法来实现呢？填补缺失值。1262022/12/7二、数据清理——缺失值的填补2022/122022/12/91、单一填补法（1）均值填补法。均值填补法是根据与含缺失值的目标属性相关性高的其它属性的信息将样品分为若干组，然后分别计算各组目标属性的均值，将各组均值作为组内所有缺失项的填补值。均值填补的优点是操作简便，并且可以有效地降低其点估计的偏差。但它的缺点也比较突出：首先，由于同组中的缺失值由同一个值填补，填补结果歪曲了目标属性的分布；其次，也导致在均值和总量估计中对方差的低估。2022/12/91272022/12/71、单一填补法2022/12/713例：2022/12/9128例：2022/12/714均值填补：2022/12/9129均值填补：2022/12/7152022/12/9（2）随机填补法。随机填补法是采用某种概率抽样的方式，从有完整信息的元组中抽取缺失数据的填补值的方法。它虽然能够避免均值填补中填补值过于凝集以及容易扭曲目标属性分布的弱点，使得填补值的分布与真值分布更为接近。但它却增大了估计量的方差，并且稳定性不够。2022/12/91302022/12/7（2）随机填补法。2022/12/7162022/12/9（3）热卡填补法。热卡填补法（hotdeckimputation）是规定一个或多个排序属性，按其观察值大小对全部观察单位排序，如果选择的是两个以上的属性，排序按属性的入选顺序依次进行。排序属性值完全相同的观察单位称为匹配，缺失值就用与之匹配的观察单位的属性值来填补。如果有多例相匹配，可取第一例或随机取其一。如果没有相匹配的，可以每次减少一个排序属性，再找相匹配的元组。如果直到最后一个排序属性，还没有找到相匹配的，则需要重新规定排序属性。2022/12/9131项目性别年龄学生身分收入办卡1男>45否高会2女31~45否高会3女20~30是低会4男<20是低不会5女20~30是中不会6女20~30否中会7女31~45否高会8男31~45是中不会9男31~45否中会10女<20是低会2022/12/7（3）热卡填补法。2022/12/717项2022/12/9（4）回归填补法。回归填补法是指在现有观察值基础上，以含有缺失值的目标属性为因变量，以与目标属性相关性高的其它属性为自变量，建立最小二乘回归模型或判别模型，以估计缺失值。注意：以上几种方法都存在扭曲样本分布的问题，如均值填补会降低属性之间的相关关系，回归填补则会人为地加大变量之间的相关关系等。2022/12/91322022/12/7（4）回归填补法。2022/12/718例：2022/12/9133例：2022/12/7192022/12/92022/12/9（二）异常值（孤立点）探测在大型数据集中，通常存在着不遵循数据模型的普遍行为的样本，这些样本和其他残余部分数据有很大不同或不一致，叫做异常点。异常点可能是由测量误差造成的，也可能是数据故有的可变性结果。例如：在检测银行交易中的信用卡欺诈行为时，异常点是可能揭示欺诈行为的典型例子。1342022/12/72022/12/7（二）异常值（孤立点）探2022/12/92022/12/9异常值的探测方法第一，一维样本异常点的检测方法例如：如果所给的数据集用20个不同的值描述年龄特征：3,56,23,39,156,52,41,22,9,28,139,31,55,20,-67,37,11,55,45,37均值=39.9;标