第四章-数据预处理.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据仓库与数据挖掘,1,引 言,目前，数据挖掘的研究工作大都集中在算法的探讨而忽视对数据处理的研究。事实上，数据预处理对数据挖掘十分重要，一些成熟的算法都对其处理的数据集合有一定的要求：比如数据的完整性好，冗余性小，属性的相关性小等。,高质量的决策来自高质量的数据，因此数据预处理是整个数据挖掘与知识发现过程中的一个重要步骤。,2,数据挖掘:数据库中的知识挖掘(KDD),数据挖掘,知识挖掘的核心,数据清洗,数据集成,数据库,数据仓库,Knowledge,任务相关数据,选择,数据挖掘,模式评估,3,第,4,章数据预处理,4,数据预处理的重要性,数据预处理是数据挖掘的重要一环，而且必不可少。要使挖掘算法挖掘出有效的知识，必须为其提供干净，准确，简洁的数据。,然而，当今现实世界中的数据库极易受到噪声数据、空缺数据和不一致性数据的侵扰，多数为“脏”数据。,5,1,）杂乱性：,如命名规则的不同,如性别：,A,数据库,male=1,female=2,B,数据库,male=,男，,female=,女,C,数据库,male=M ,female=F,数据预处理的重要性,6,2,）重复性：,同一客观事物在数据库中存在两个以上相同的物理描述。,假设某周刊有,100000,个订户，邮件列表中,0.1%,的记录是重复的主要是因为同一个客户的名字可能有不同的写法，如：,Jon Doe,和,John Doe,。,因此，每周需要印刷和邮寄,100,份额外的刊物，假设每份刊物每周的邮寄和印刷费用是两美元，公司每年将至少浪费,1,万美元以上。,数据预处理的重要性,7,3,）不完整性：,由于实际系统设计时存在的缺陷以及使用过程中的一些人为因素，数据记录可能会出现数据值的丢失或不确定。,原因可能有：,（,1,）有些属性的内容有时没有,（家庭收入，参与销售事务数据中的顾客信息）,（,2,）有些数据当时被认为是不必要的,（,3,）由于误解或检测设备失灵导致相关数据没有记录下来,（,4,）与其它记录内容不一致而被删除,（,5忽略了历史数据或对数据的修改,数据预处理的重要性,8,4,）噪声数据：,数据中存在着错误或异常（偏离期望值）,如：血压和身高为,0,就是明显的错误,噪声数据的产生原因：,数据采集设备有问题；,在数据录入过程发生人为或计算机错误；,数据传输过程中出现错误；,由于命名规则或数据代码不同而引起的不一致。,数据预处理的重要性,9,数据清理（清洗）,-,去掉数据中的噪声，纠正不一致,数据集成,-,将多个数据源合并成一致的数据存储，构成一个完整的数据集，如数据仓库。,数据变换（转换）,-,将一种格式的数据转换为另一格式的数据,(,如规范化,),数据归约（消减）,-,通过聚集、删除冗余属性或聚类等方法来压缩数据。,数据预处理的常见方法,10,11,注意：,上述的各种数据预处理方法，并不是相互独立的，而是相互关联的，如消除数据冗余既可以看成是一种形式的数据清洗，也可以看成是一种数据归约（消减）。,12,4,.1,数据清洗,4,.,2,数据集成和变换,4,.,3,数据归约,4.4,数据离散化和概念分层,*,第,4,章,13,学习目的,掌握数据清洗的处理方法（空缺、噪声、不一致）；,掌握各种数据归约的方法；,理解数据离散化的方法。,14,4.1,数据清洗,现实世界的数据一般是脏的、不完整的和不一致的。而数据清洗试图填充空缺的值、识别孤立点、消除噪声，并纠正数据中的不一致性。因此，从如下几个方面介绍1,）空缺值；,（,2,）噪声数据；,（,3,）不一致数据。,15,1.,空缺值的处理？,16,空缺值,数据并不总是完整的,数据库表中，很多条记录的对应字段可能没有相应值，比如销售表中的顾客收入,引起空缺值的原因,设备异常,与其他已有数据不一致而被删除,因为误解而没有被输入的数据,在输入时，有些数据因为得不到重视而没有被输入,对数据的改变没有进行日志记载,空缺值要经过推断而补上。,17,如何处理空缺值,1,）忽略该元组：,若一条记录中有属性值被遗漏了，则将该记录排除在数据挖掘之外；,尤其当类标号缺少时通常这样做（假定挖掘任务涉及分类或描述,),；,但是，当某类属性的空缺值所占百分比很大时，直接忽略元组会使挖掘性能变得非常差。,18,如何处理空缺值,2,）人工填写空缺值：,工作量大，可行性低,3,）使用属性的平均值填充空缺值：,如所有顾客的平均收入为,$1000,，则使用该值替换,income,中的空缺值。,19,如何处理空缺值,4,）使用一个全局变量填充空缺值：,如：将空缺的属性值用同一个常数,(,如“,Unknown”),替换。,如果空缺值都用“,Unknown”,替换，当空缺值较多时，挖掘程序可能误以为它们形成了一个有趣的概念，因为它们都具有相同的值,“Unknown”,。,因此，尽管该方法简单，我们并不推荐它。,20,如何处理空缺值,5,）使用与给定元组属同一类的所有样本的平均值：,适用于分类数据挖掘；,如将顾客按信用度分类，则用具有相同信用度的顾客的平均收入替换,income,中的空缺值。,6,）使用最可能的值填充空缺值（最常用）：,可以利用回归、贝叶斯计算公式或判定树归纳确定，推断出该条记录特定属性最大可能的取值；,如，利用数据集中其他顾客的属性，构造一棵判定树，预测,income,的空缺值。,21,2.,噪声数据的处理？,22,噪声数据,噪声,(noise),：,是一个测量变量中的随机错误或偏差,引起噪声数据的原因,数据收集工具的问题,数据输入错误,数据传输错误,技术限制,命名规则的不一致,23,如何处理噪声数据,1,）分箱,(binning):,分箱方法通过考察“邻居”,(,即周围的值,),来平滑存储数据的值。,存储的值被分布到一些“桶”或箱中。由于分箱方法参考相邻的值，因此它进行局部平滑。,24,如何处理噪声数据,分箱的步骤：,首先排序数据，并将它们分到等深（等宽）的箱中；,然后可以按箱的,平均值,、按箱,中值,或者按箱的,边界,等进行平滑。,按箱的,平均值,平滑：箱中每一个值被箱中的平均值替换,按箱的,中值,平滑：箱中的每一个值被箱中的中值替换,按箱的,边界,平滑：箱中的最大和最小值被视为箱边界，箱中的每一个值被最近的边界值替换。,25,如何处理噪声数据,等深分箱,(binning):,按记录数进行分箱，每箱具有相同的记录数，每箱的记录数称为箱的权重，也称箱子的深度。,26,示例：,已知一组价格数据：,15,21,24,21,25,4,8,34,28,现用等深（深度为,3,）分箱方法对其进行平滑，以对数据中的噪声进行处理。,思考：,根据,bin,中值进行平滑的结果？,结果：,Bin1,：,8,、,8,、,8,；,Bin2,：,21,、,21,、,21,；,Bin3,：,28,、,28,、,28,27,在该例中，,price,数据首先被划分并存人等深的箱中,(,深度,3),。,对于按,箱平均值,平滑，箱中每一个值被箱中的平均值替换。例如，箱,1,中的值,4,，,8,和,15,的平均值是,9,；这样，该箱中的每一个值被替换为9,。,对于按,箱边界,平滑，箱中的,最大和最小值被视为箱边界,。箱中的每一个值被最近的边界值替换。,类似地，可以使用按,箱中值,平滑。此时，箱中的每一个值被箱中的中值替换。,28,如何处理噪声数据,等宽分箱,(binning):,在整个属性值的区间上平均分布，即每个箱的区间范围设定为一个常量，称为箱子的宽度。,29,示例：,已知一组价格数据：,15,21,24,21,25,4,8,34,28,现用等宽（宽度为,10,）分箱方法对其进行平滑，以对数据中的噪声进行处理。,结果：,先排序：,4,，,8,，,15,，,21,，,21,，,24,，,25,，,28,，,34,1,）划分为等宽度箱子,Bin1,：,4,、,8,；,Bin2,：,15,、,21,、,21,、,24,、,25,；,Bin3,：,28,、,34,2,）根据均值进行平滑,Bin1,：,6,、,6,；,Bin2,：,21,、,21,、,21,、,21,、,21,；,Bin3,：,31,、,31,3,）根据中值进行平滑,Bin1,：,6,、,6,；,Bin2,：,21,、,21,、,21,、,21,、,21,；,Bin3,：,31,、,31,4,）根据边界进行平滑：,Bin1,：,4,、,8,；,Bin2,：,15,、,25,、,25,、,25,、,25,；,Bin3,：,28,、,34,30,练习：,已知客户收入属性income,排序后的值（人民币元）：,800,，,1000,，,1200,，,1500,，,1500,，,1800,，,2000,，,2300,，,2500,，,2800,，,3000,，,3500,，,4000,，,4500,，,4800,，,5000,要求：分别用等深分箱方法,(,箱深为,4,）、等宽分箱方法（宽度为,1000,）对其进行平滑，以对数据中的噪声进行处理。,31,（,1,）等深分箱结果：,（,1,）首先，划分为等深的箱：,箱,1,（,800,，,1000,，,1200,，,1500,）；,箱,2,（,1500,，,1800,，,2000,，,2300,）；,箱,3,（,2500,，,2800,，,3000,，,3500,）；,箱,4,（,4000,，,4500,，,4800,，,5000,）,（,2,）按箱的平均值平滑，结果为：,箱,1,（,1125,，,1125,，,1125,，,1125,）；,箱,2,（,1900,，,1900,，,1900,，,1900,）；,箱,3,（,2950,，,2950,，,2950,，,2950,）；,箱,4,（,4575,，,4575,，,4575,，,4575,）,32,（,1,）等深分箱结果：,（,2,）按箱的中值平滑，结果为：,箱,1,（,1100,，,1100,，,1100,，,1100,）；,箱,2,（,1900,1900,，,1900,，,1900,）；,箱,3,（,2900,，,2900,，,2900,，,2900,）；,箱,4,（,4650,，,4650,，,4650,，,4650,）,（,2,）按箱的边界值平滑，结果为：,箱,1,（,800,，,800,，,1500,，,1500,）；,箱,2,（,1500,，,1500,，,2300,，,2300,）；,箱,3,（,2500,，,2500,，,3500,，,3500,）；,箱,4,（,4000,，,4000,，,5000,，,5000,）,33,（,2,）等宽分箱结果：,（,1,）首先，划分为等宽的箱：,箱,1,（,800,，,1000,，1200,，,1500,，,1500,，,1800,）；,箱,2,（,2000,，,2300,，,2500,，,2800,，,3000,）；,箱,3,（,3500,，,4000,，,4500,）；,箱,4,（,4800,，,5000,）,（,2,）按箱的平均值平滑，结果为：,箱,1,（,1300,，,1300,，,1300,，,1300,，,1300,，,1300,）；,箱,2,（,2520,，,2520,，,2520,，,2520,，,2520,）；,箱,3,（,4000,，,4000,，,4000,）；,箱,4,（,4900,，,4900,）,34,（,2,）等宽分箱结果：,（,1,）按箱的中值平滑，结果为：,箱,1,（,1350,，,1350,，,1350,，,1350,，,1350,，,1350,）；,箱,2,（,2500,，,2500,，,2500,，,2500,，,2500,）；,箱,3,（,4000,，,4000,，,4000,）；,箱,4,（,4900,，,4900,）,（,2,）按箱的边界值平滑，结果为：,箱,1,（,800,，,800,，,800,，,1800,，,1800,，,1800,）；,箱,2,（,2000,，,2000,，,3000,，,3000,，,3000,）；,箱,3,（,3500,，,3500,，,4000,）；,箱,4,（,4800,，,5000,）,35,如何处理噪声数据,2,）聚类（,Clustering,）：,相似或相邻近的数据聚合在一起形成各个聚类集合，而那些位于聚类集合之外的数据对象，被视为孤立点。,特点：直接形成簇并对簇进行描述，不需要任何先验知识。,通过聚类分析查找孤立点，消除噪声,36,如何处理噪声数据,3,）计算机和人工检查结合,计算机检测可疑数据，然后对它们进行人工判断,4,）回归,发现两个相关的变量之间的变化模式，利用回归分析方法所获得的拟合函数，帮助平滑数据及除去噪声。,x,y,y=x+1,X1,Y1,Y1,37,许多数据平滑的方法也是涉及离散化的数据归约方法。例如，上面介绍的分箱技术减少了每个属性的不同值的数量。,另外，概念分层是一种数据离散化形式，也可以用于数据平滑。例如，,price,的概念分层可以把,price,的值映射到,inexpensive,，,moderately_priced,和,expensive,，从而减少了挖掘过程所处理的值的数量。,注意：,38,3.,不一致数据的处理？,39,不一致数据,处理不一致数据的方式：,人工更正,利用知识工程工具：如，如果知道属性间的函数依赖关系，可以据此查找违反函数依赖的值。,数据字典：在将不同操作性数据库中的数据进行集成时，也会带来数据的不一致。如：一个给定的属性在不同的数据库中可能具有不同的名字，如姓名在一个数据库中为,Bill,，在另一个数据库中可能为,B,。对此，可根据数据字典中提供的信息，消除不一致。,40,4.2,数据集成和变换,数据挖掘所需要的海量数据集往往涉及多个数据源，因此，在信息处理之前需要合并这些数据源存储的数据。,如果原始数据的形式不适合信息处理算法的需要，就要进行数据变换。,1,）数据集成,：将来自多个数据源的数据合并到一起：,2,）数据变换,：对数据进行规范化操作，将其转换成适合于数据挖掘的形式。,41,1.,数据集成？,42,数据集成,数据集成,将多个数据源中的数据整合到一个一致的存储中。,这些源可以是关系型数据库、数据立方体或一般文件。,它需要统一原始数据中的所有矛盾之处，如字段的,:,同名异义；异名同义；,单位不统一；,字长不一致等。,43,数据集成,集成过程中需要注意的问题,模式集成问题；,冗余问题；,数据值冲突检测与消除,。,44,（,1,）模式集成问题,模式集成：,整合不同数据源中的元数据；,进行实体识别：匹配来自不同数据源的现实世界的实体,如：如何确信一个数据库中的,customer_id,和另一个数据库中的,cust_number,是同一实体。,通常，数据库的,数据字典,和数据仓库的,元数据,，可帮助避免模式集成中的错误。,45,（,2,）数据冗余问题,数据冗余问题：,同一属性值不同的数据库中会有不同的字段名；,一个属性可以由另外一个表导出，如：一个顾客数据表中的平均月收入属性，可以根据月收入属性计算出来。,46,（,2,）数据冗余问题,数据冗余问题：,有些冗余可以被相关分析检测到：,如果变量,A,、,B,间具有较高的相关系数，表明,A,或,B,可以作为冗余而去掉。,除了检查属性是否冗余外，还要检查记录行的冗余。,47,(3),数据值冲突问题,数据值冲突,对现实世界的同一实体，来自不同数据源的属性值可能不同。,产生的原因：表示、比例或编码不同。,如：重量属性在一个系统中可能以公制单位存放，而在另一系统中可能以英制单位存放；同一商品的价格属性值不同地域采用不同价格单位；不同学校的成绩单可能以百分制、五分制及其他等级制来存放等等。,48,2.,数据变换？,49,数据变换,数据变换：将数据转换成适合数据挖掘的形式。涉及内容：,（,1,）平滑,：去掉数据中的噪声，将连续的数据离散化：,分箱,聚类,回归。,（,2,）聚集,：对数据进行汇总和聚集,Avg(),count(),sum(),min(),max(),如，每天销售额（数据）可以进行聚集操作以获得每月或每年的总额。,可用来构造数据立方体。,50,数据变换,数据变换：将数据转换成适合数据挖掘的形式。涉及内容：,（,3,）数据概化,：使用概念分层，用更抽象（更高层次）的概念来取代低层次或数据层的数据对象,如，街道属性，可以泛化到更高层次的概念，如城市、国家；,同样，对于数值型的属性，如年龄属性，可以映射到更高层次的概念，如年轻、中年和老年。,51,数据变换,数据变换：将数据转换成适合数据挖掘的形式。涉及内容：,（,4,）规范化,：将数据按比例进行缩放，使之落入一个特定的区域，以消除数值型属性因大小不一而造成的挖掘结果的偏差。如将工资收入属性值映射到,-1.0,1.0,的范围内。,常用的方法：,最小,-,最大规范化；,零,-,均值规范化（,z-score,规范化）；,小数定标规范化,。,52,规格化的目的：,是将一个属性取值范围影射到一个特定范围之内，以消除数值性属性因大小不一而造成挖掘结果的偏差。,数据变换,规范化,53,在正式进行数据挖掘之前，尤其是使用基,于对象距离,的挖掘算法时，必须进行数据的规格化。,如对于一个顾客信息数据库中,年龄,属性或,工资,属性，由于工资属性的取值比年龄属性的取值要大得多，若不进行规格化处理，基于工资属性的距离计算值将远远超过基于年龄属性的计算值，这就意味着工资属性的作用在整个数据对象的距离计算中被错误放大了。,数据变换,规范化,54,数据变换,规范化,数据规范化：,将数据按比例缩放至一个小的特定区间,：,1,）,最小,最大规范化,：假定,min,A,和,max,A,分别为属性,A,的最小和最大值，则通过下面公式将,A,的值映射到区间,new_min,new_max,中的,v,：,例：,假定属性,income,的最小与最大值分别为,$12000,和,$98000,，可根据最小,最大规范化方法将其范围映射到,0,1,：,如：属性值,$73600,将变换为：,(73600-12000)/(98000-12000)*(1-0)+0=0.716,55,数据变换,规范化,2,）,z-score,规范化,（零均值规范化）：,将属性,A,的值根据其平均值和标准差进行规范化；,常用于属性最大值与最小值未知，或使用最小最大规范化方法会出现异常数据的情况。,其中，,mean,A,、,standard,-,dev,A,分别为属性,A,取值的均值和标准差。,例：,假定属性,income,的平均值与标准差分别为,$54000,和,$16000,，使用,z-score规范化，则属性值,$73600,将变换为：,(73600-54000,）,/16000=1.225,56,数据变换,规范化,3,）,小数定标规范化,：通过移动属性,A,的小数点位置进行规范化，小数点的移动依赖于,A,的最大绝对值：,例：,假定,A,的取值范围,-986,917,，则,A,的最大绝对值为,986,，为使用小数定标规范化，用,1000,（即,j=3,）除每个值，这样,-986,被规范化为,-0.986,。,其中，,j,是使,Max(|v|)1,的最小整数,57,规范化将原来的数据改变很多，特别是上述的后两种方法。,有必要保留规范化参数（如平均值和标准差，如果使用,z-score,规范化），以便将来的数据可以用一致的方式规范化。,注意：,58,数据变换,数据变换：将数据转换成适合数据挖掘的形式。涉及内容：,（,5,）属性构造,：,利用已有属性集构造出新的属性，并加入到现有属性集中以帮助挖掘更深层次的模式知识，提高挖掘结果的准确性；,如，根据宽、高属性，可以构造一个新属性：面积。,59,4.3,数据归约,对大规模数据库内容进行复杂的数据分析常需要消耗大量的时间，使得这样的分析变得不现实和不可行；,数据归约（,data reduction,）：数据消减或约简，是在不影响最终挖掘结果的前提下，缩小所挖掘数据的规模。,数据归约技术可以用来得到数据集的归约表示，它小得多，但仍接近保持原数据的完整性。,对归约后的数据集进行挖掘可提高挖掘的效率，并产生相同（或几乎相同）的结果。,60,4.3,数据归约,数据归约的标准：,用于数据归约的时间不应当超过或“抵消”在归约后的数据集上挖掘节省的时间。,归约得到的数据比原数据小得多，但可以产生相同或几乎相同的分析结果。,61,4.3,数据归约,数据归约的策略如下：,数据立方体聚集；,维归约；,数据压缩；,数值归约；,离散化和概念分层生成,。,62,1.,数据立方体聚集？,63,数据立方体聚集,64,2.,维归约？,65,维归约,维归约：,主要用于检测并删除不相关、弱相关或冗余的属性维,用于数据分析的数据可能包含数以百计的属性，其中大部分可能与挖掘任务不相关，是冗余的,。,如，分析顾客是否会在商场购买,mp3,播放器，诸如顾客的电话号码等属性多半是不相关的,。,维归约通过删除不相关的属性（或维），而有效减少数据库的规模。,最常用的方法：属性子集选择。,66,维归约,属性子集选择,目标：,找出最小属性集，确保新数据集的概率分布尽可能接近原数据集的概率分布。,如何找出原属性的一个好的子集,d,个属性有,2,d,个可能的子集。穷举搜索找出属性的最佳子集可能是不现实的，特别是当,d,的数目很大时。,67,维归约,属性子集选择,启发式算法：,对于属性子集选择，通常使用压缩搜索空间的启发式算法。,它们的策略是做局部最优选择，期望由此导致全局最优解。,68,维归约,属性子集选择,常用的启发式方法：,1,）逐步向前选择,：,该过程由空属性集开始，选择原属性集中最好的属性，并将它添加到该集合中。,在其后的每一次迭代，将原属性集剩下的属性中的最好的属性添加到该集合中。,如：,遗传算法是,一种基于生物进化论和分子遗传学的全局随机搜索算法。,69,维归约,属性子集选择,常用的启发式方法：,2,）逐步向后删除：,由整个属性集开始，每一步都删除尚在属性集中的最坏属性。,直到无法选择出最坏属性或满足一定的阈值为止。,如：,粗糙集理论,，,利用定义的数据集合,U,上的等价关系对,U,进行划分，对于数据表来说，这种等价关系可以是某个属性，或者是几个属性的集合。因此，按照不同属性的组合就把数据表划分成不同的基本类，在这些基本类的基础上进一步求得最小约简集。,70,维归约,属性子集选择,常用的启发式方法：,3,）向前选择和向后删除的结合：,将向前选择和向后删除方法结合在一起；,每一步选择一个最好的属性，并在剩余属性中删除一个最坏的属性。,71,维归约,属性子集选择,常用的启发式方法：,4,）判定树归纳：,在判定树的每个节点，算法选择“最好”的属性，将数据划分成类。,当判定树归纳用于属性子集选择时，不出现在树中的所有属性假定是不相关的；,出现在判定树中的属性形成归约后的属性子集,。,72,73,3.,数据压缩？,74,数据压缩,数据压缩就是利用数据编码或数据转换将原来的数据集合压缩为一个较小规模的数据集合。,压缩算法分为两类：,无损压缩（,loseless,）：可以不丢失任何信息地还原压缩数据；如：字符串压缩,有损压缩（,lossy,）：只能重新构造原数据的近似表示；如：音频,/,视频压缩,。,75,76,数据压缩,两类：,1,）无损压缩,：指使用压缩后的数据进行重构,(,或者叫做还原，解压缩,),，重构后的数据与原来的数据完全相同。,即：数据经过压缩后，信息不受损失，还能完全恢复到压缩前的原样。,压缩软件：,Zip,或,RAR,。,77,数据压缩,两类：,2,）有损压缩,：又称破坏型压缩，即将次要的信息数据压缩掉，牺牲一些质量来减少数据量，使压缩比提高。,常用于压缩声音、图像以及视频。音频能够在没有察觉的质量下降情况下实现,10:1,的压缩比，视频能够在稍微观察质量下降的情况下实现如,300:1,这样非常大的压缩比。,常见算法：,JPEG,、,MPEG,、,MP3,等。,算法机理：,小波变换,或,主成份分析,78,4.,数值归约？,79,数值归约,数值归约：,通过选择替代的、较小的数据表示形式来减少数据量,。,（,1,）有参方法,：,通常使用一个参数模型来评估数据，该方法只需要存储参数，而不是实际数据，能大大减少数据量，但只对数值型数据有效。,如：线性回归方法（最小二乘法）：,Y=,+,X,80,数值归约,数值归约：,通过选择替代的、较小的数据表示形式来减少数据量,。,（,2,）无参方法,：,常见的有：,直方图；,聚类；,取样,。,81,1,）直方图,直方图：,根据属性的数据分布将其分成若干不相交的区间，每个区间的高度与其出现的频率成正比,。,例：下面的数据是,AllElectronics,通常销售的商品的单价表（已排序）：,1,1,5,5,5,5,5,8,8,10,10,10,10,12,14,14,14,15,15,15,15,15,15,18,18,18,18,18,18,18,18,20,20,20,20,20,20,20,21,21,21,21,25,25,25,25,25,28,28,3030,30,。,试用直方图表示，以压缩数据。,82,1,）直方图,频率,-,值对应关系图,83,2,）聚类,聚类：,将原数据集划分成多个群或聚类,。,原则,：同类中的数据彼此相似；不同类中的数据彼此不相似。,相似,：通常用空间距离度量,聚类的,有效性,依赖于实际数据的内在规律。,84,3,）取样,取样（抽样）：,允许用数据的较小随机样本（子集）表示大的数据集。,取样方法：,不放回简单随机取样（,Simple Random Sampling Without Replacement,SRSWOR,）,放回简单随机取样（,Simple Random Sampling With Replacement,SRSWR,）,聚类取样：先聚类，后取样,分层取样：先分层，后取样。,85,取样,SRS,SRSWOR,(,简单随机选,样，不回放,),SRSWR,(,简单随机选,样，回放,),原始数据,86,取样,聚类采样：,首先将大数据集,D,划分为,M,个互不相交的聚类，然后再从,M,个类中的数据对象分别进行随机抽取，可最终获得聚类采样的数据子集。,聚类采样方法示意图,87,聚类取样,88,取样,分层取样：,首先将大数据集,D,划分为互不相交的层，然后对每一层简单随机选样得到,D,的分层选样。,如，根据顾客的年龄组进行分层，然后再在每个年龄组中进行随机选样，从而确保了最终获得分层采样数据子集中的年龄分布具有代表性。,89,分层取样,分层采样方法示意图,90,4.4,数据离散化和概念分层,*,三种类型的属性值：,标称型（名称型、名义型）：数值来自于无序集合，如性别、地名、人名等。,序数型：数值来自于有序集合，如奖学金的等级；职称分布等。,连续型：实数值，如温度、体重等。,离散化技术：,通过将属性（连续取值）阈值范围分为若干区间，来帮助消减一个连续（取值）属性的取值个数。,如，将气温划分为：冷、正常、热。,91,4.4,数据离散化和概念分层,*,概念分层：,概念分层定义了一组由低层概念到高层概念集的映射。允许在各种抽象级别上处理数据，从而在多个抽象层上发现知识。,用较高层概念替换低层次（如年龄的数值）的概念，以此来减少取值个数。,虽然一些细节数据在泛化过程中消失了，但这样所获得的泛化数据或许更易于理解、更有意义。,另外，在消减后的数据集上进行信息处理显然效率更高。,概念分层结构可以用树来表示，树的每个节点代表一个概念。,92,概念分层,93,离散化方法,常用的离散化方法：,1,）分箱：,属性的值可以通过将其分配到各分箱中而将其离散化。,利用每个分箱的均值或中数替换每个分箱中的值（利用均值或中数进行平滑）。,循环应用这些操作处理每次操作结果，就可以获得一个概念层次树。,94,离散化方法,常用的离散化方法：,2,）直方图：,等宽直方图中，将数据划分成相等的部分或区间，如,(0,100),、,(100$,200$,、,(200$,300$.,等深直方图：值被划分使得每一部分包括相同个数的样本。,95,离散化方法,常用的离散化方法：,3,）,聚类分析,：,聚类算法可以将数据集划分为若干类或组。,每个类构成了概念分层树的一个节点；,每个类还可以进一步分解为若干子类，从而构造更低水平的层次。,当然类也可以合并起来构成更高层次的概念水平。,4,）,基于熵的离散化,：熵是一种信息度量的方法,5,）,通过自然划分分段,96,基于熵的离散化,思想：,考虑类别信息，递归计算信息熵，产生分层的离散化。,I(S)=,初始不确定性：,97,基于熵的离散化,思想：,考虑类别信息，递归计算信息熵，产生分层的离散化。,给定一个数据元组的集合,S,，基于熵对,S,离散化的方法如下：,1,）属性,A,中的每个取值可被认为是一个潜在的区间边界或阈值,T,。例如，,A,的取值,v,可以将样本,S,划分为分别满足,Av,和,Av,两个子集，这样就创建了一个二元离散化。,2,）对于数据集,S,，根据所划分子集而获得的最大熵增益来选择阈值，划分后数据集,S,提供的信息如下：,E(A)=,学习属性,A,之后的不确定性：,98,基于熵的离散化,其中,S,1,和,S,2,分别对应于,S,中满足条件：,AT,与,AT,，的样本。对给定的集合，熵函数,Ent,根据集合中样本的类分布来计算。例如，给定,m,个不同类别，,S,1,的熵就是：,其中,p,i,为类,i,在,S,1,中出现的概率，等于,S,1,中类,i,的样本除以,S,1,中样本的总行数。同理，计算,Ent(S,2,),。,3,）确定阈值的过程递归的用于所得到的每个划分，直到满足某个终止条件，如：,Ent(S)-I(S,T),信息增益不能低于,：,99,基于熵的离散化,与迄今为止提到的其他方法不同，基于熵的离散化使用了类别信息。这使得它更有可能将区间边界定义在准确位置，有助于提高分类的准确性。,此处用到的信息增益和信息熵也用于决策树归纳。,100,自然划分分段,思想：,将数值区域划分为相对一致的、易于阅读的、看上去更直观或自然的区间。,聚类分析产生的概念分层可能会将一个工资区间划分为：,51263.98,60872.34,而通常数据分析人员希望看到划分的形式为,50000,，,60000,自然划分的,3-4-5,规则,常可以将数值数据划分为相对一致和“自然”的区间。一般的，根据最重要的数字上的值区域，递归的和逐层的将给定的数据区域划分为,3,、,4,或,5,个等宽区间。,101,自然划分的,3-4-5,规则,规则的划分步骤：,如果一个区间,最高有效位,上跨越,3,，,6,，,7,或,9,个不同的值，就将该区间划分为,3,个等宽子区间；,(7,2,3,2),如果一个区间,最高有效位,上跨越,2,，,4,，或,8,个不同的值，就将该区间划分为,4,个等宽子区间；,如果一个区间,最高有效位,上跨越,1,，,5,，或,10,个不同的值，就将该区间划分为,5,个等宽子区间；,将该规则递归的应用于每个子区间，产生给定数值属性的概念分层；,102,自然划分的,3-4-5,规则,规则的划分步骤：,对于数据集中出现的最大值和最小值的极端分布，为了避免上述方法出现的结果扭曲，可以在顶层分段时，选用一个大部分的概率空间。,e.g.5%-95%,例如，在资产数据集中，少数人的资产可能比其他人高几个数量级。如果按照最高资产值进行分段，可能导致高度倾斜的分层。此时，可以在顶层分段时，选用一个大部分的概率空间。,e.g.5%-95%,。,越出顶层分段的特别高和特别低的部分采用类似的规则划分方法形成单独的区间。,103,示例：,3-4-5,规则,假定,AllElectronics,所有分部,1999,年的利润覆盖了一个很宽的区间，从,-351.00$,到,4700$,。要求利用,3-4-5,规则自动构造利润属性的一个概念层次树。,104,示例：,3-4-5,规则,思路：,设在上述范围取值为,5%,至,95%,的区间为：,-159$,至,1838$,。应用,3-4-5,规则的具体步骤如下：,1,）根据以上信息，在利润数据集中最小和最大值分别为：,MIN=-351$,MAX=4700$,。而根据以上分析，对于分段的顶层或第一层，要考虑的最低（5%,）和最高（,95%,）的值是：,LOW=-159$,HIGH=1838$,。,2,）依据,LOW,和,HIGH,及其取值范围，确定最高有效位为,1000$,，,LOW,按,1000$,美元向下取整，得到,LOW=-1000$,；,HIGH,按,1000$,向上取整，得到：,HIGH=2000$,。,105,示例：,3-4-5,规则,3,）由于该区间在最高有效位上跨越了,3,个值，即,(2000-(-1000)/1000=3,，根据,3-4-5,规则，该区间被划分成,3,个等宽区间：,(-1000$,0,(0,1000$,(1000$,2000$,。这代表分层结构的最顶层。,106,示例3-4-5,规则,4,）现在，考察原数据集中,MIN,和,MAX,值与最高层区间的联系。由于,MIN,值落在区间,(-1000$,0,，因此调整左边界，对,MIN,取整后的,-400$,，所以第一个区间调整为,(-400$,0,。,而由于,MAX,值不在最后一个区间,(1000$,2000$,中，因此需新建一个区间（最右边区间）。,对,MAX,取整后得,5000$,，因此新区间为,(2000$,5000,。,因此最终，概念树分层结构的最顶层包含,4,个区间,：,(-400$,0,(0,1000$,(1000$,2000$,(2000$,5000$,。,107,示例：,3-4-5,规则,5,对上述每个区间递归应用,3-4-5,规则，形成分层结构的下一个较低层：,第一个区间,(-400$,0,：划分为,4,个子区间,(-400$,-300$,(-300$,-200$,(-200$,-100$,(-100$,0$.,第二个区间,(0$,1000$,：划分为,5,个子区间,(0$,200$,(200$,400$,400$,600$,(600$,800$,(800$,1000$.,第三个区间,(1000$,2000$,：划分为,5,个子区间,(1000$,1200$,(1200$,1400$,1400$,1600$,(1600$,1800$,(1800$,2000$.,第四个区间,(2000$,5000$,：划分为,3,个子区间,(2000$,3000$,(3000$,4000$,(4000$,5000$,。,类似的，如有必要，,3-4-5,规则可继续在较低的层次上迭代。,108,3-4-5,规则,例子,(-$4000-$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,000Low=-$1,000High=$2,000,第二步,第四步,第一步,-$351-$159profit$1,838$4,700,Min Low(i.e,5%-tile)High(i.e,95%-0 tile)Max,count,(-$1,000 -$2,000),(-$1,000-0),(0-$1,000)