第四章-数据预处理

《第四章-数据预处理》由会员分享，可在线阅读，更多相关《第四章-数据预处理（117页珍藏版）》请在装配图网上搜索。

1、 数据仓库与数据挖掘数据仓库与数据挖掘2 目前，数据挖掘的研究工作大都集中在算法的探讨而忽视对数据处理的研究。事实上，数据预处理对数据挖掘十分重要，一些成熟的算法都对其处理的数据集合有一定的要求：比如数据的完整性好，冗余性小，属性的相关性小等。高质量的决策来自高质量的数据，因此数据预处理是整个数据挖掘与知识发现过程中的一个重要步骤。数据挖掘数据挖掘:数据库中的知识挖掘数据库中的知识挖掘(KDD)(KDD)数据挖掘数据挖掘知识挖知识挖掘的核心掘的核心数据清洗数据清洗数据集成数据集成数据库数据库数据仓库数据仓库任务相关数据任务相关数据选择选择数据挖掘数据挖掘模式评估模式评估5u数据预处理是数据挖掘

2、的重要一环，而且必不可少。要使挖掘算法挖掘出有效的知识，必须为其提供干净，准确，简洁的数据。u然而，当今现实世界中的数据库极易受到噪声数据、空缺数据和不一致性数据的侵扰，多数为“脏”数据。1）杂乱性：）杂乱性：如命名规则的不同如命名规则的不同 如性别：A数据库 male=1,female=2 B数据库 male=男，female=女 C数据库 male=M ,female=F2）重复性：）重复性：同一客观事物在数据库中存在两个以上相同的物同一客观事物在数据库中存在两个以上相同的物理描述。理描述。假设某周刊有100000个订户，邮件列表中0.1%的记录是重复的，主要是因为同一个客户的名字可能有不

3、同的写法，如：Jon Doe和John Doe。因此，每周需要印刷和邮寄100份额外的刊物，假设每份刊物每周的邮寄和印刷费用是两美元，公司每年将至少浪费1万美元以上。3）不完整性：）不完整性：由于实际系统设计时存在的缺陷以及使用过程由于实际系统设计时存在的缺陷以及使用过程中的一些人为因素，数据记录可能会出现数据值的丢失或不中的一些人为因素，数据记录可能会出现数据值的丢失或不确定。确定。原因可能有：（1）有些属性的内容有时没有 （家庭收入，参与销售事务数据中的顾客信息）（2）有些数据当时被认为是不必要的 （3）由于误解或检测设备失灵导致相关数据没有记录下来 （4）与其它记录内容不一致而被删除 （

4、5）忽略了历史数据或对数据的修改4）噪声数据：）噪声数据：数据中存在着错误或异常（偏离期望值）数据中存在着错误或异常（偏离期望值）v如：血压和身高为如：血压和身高为0就是明显的错误就是明显的错误v噪声数据的产生原因：噪声数据的产生原因：数据采集设备有问题；数据采集设备有问题；在数据录入过程发生人为或计算机错误；在数据录入过程发生人为或计算机错误；数据传输过程中出现错误；数据传输过程中出现错误；由于命名规则或数据代码不同而引起的不一致。由于命名规则或数据代码不同而引起的不一致。q 数据清理（清洗）数据清理（清洗）-去掉数据中的噪声，纠正不一致q 数据集成数据集成-将多个数据源合并成一致的数据存储

5、，构成一个完整的数据集，如数据仓库。q 数据变换（转换）数据变换（转换）-将一种格式的数据转换为另一格式的数据(如规范化)q 数据归约（消减）数据归约（消减）-通过聚集、删除冗余属性或聚类等方法来压缩数据。11注意：注意：上述的各种数据预处理方法，并不是相互独立上述的各种数据预处理方法，并不是相互独立的，而是相互关联的，如消除数据冗余既可以看成的，而是相互关联的，如消除数据冗余既可以看成是一种形式的数据清洗，也可以看成是一种数据归是一种形式的数据清洗，也可以看成是一种数据归约（消减）。约（消减）。4.1 数据清洗数据清洗4.2 数据集成和变换数据集成和变换4.3 数据归约数据归约4.4 数据离

6、散化和概念分层数据离散化和概念分层*14u 掌握数据清洗的处理方法（空缺、噪声、不一致）；u 掌握各种数据归约的方法；u 理解数据离散化的方法。4.1 数据清洗数据清洗 现实世界的数据一般是脏的、不完整的和不一致的。而数据清洗试图填充空缺的值、识别孤立点、消除噪声，并纠正数据中的不一致性。因此，从如下几个方面介绍：（1 1）空缺值；）空缺值；（2 2）噪声数据；）噪声数据；（3 3）不一致数据。）不一致数据。1.1.空缺值的处理？空缺值的处理？17空缺值空缺值u数据并不总是完整的数据库表中，很多条记录的对应字段可能没有相应值，比如销售表中的顾客收入u引起空缺值的原因设备异常与其他已有数据不一致

7、而被删除因为误解而没有被输入的数据在输入时，有些数据因为得不到重视而没有被输入对数据的改变没有进行日志记载u空缺值要经过推断而补上。如何处理空缺值如何处理空缺值1）忽略该元组：）忽略该元组：v 若一条记录中有属性值被遗漏了，则将该记录排除在数据挖掘之外；v 尤其当类标号缺少时通常这样做（假定挖掘任务涉及分类或描述)；v 但是，当某类属性的空缺值所占百分比很大时，直接忽略元组会使挖掘性能变得非常差。如何处理空缺值如何处理空缺值2）人工填写空缺值：）人工填写空缺值：v工作量大，可行性低3）使用属性的平均值填充空缺值：）使用属性的平均值填充空缺值：v如所有顾客的平均收入为$1000，则使用该值替换i

8、ncome中的空缺值。如何处理空缺值如何处理空缺值4）使用一个全局变量填充空缺值：）使用一个全局变量填充空缺值：v如：将空缺的属性值用同一个常数(如“Unknown”)替换。v如果空缺值都用“Unknown”替换，当空缺值较多时，挖掘程序可能误以为它们形成了一个有趣的概念，因为它们都具有相同的值“Unknown”。v因此，尽管该方法简单，我们并不推荐它。如何处理空缺值如何处理空缺值5）使用与给定元组属同一类的所有样本的平均值：）使用与给定元组属同一类的所有样本的平均值：l 适用于分类数据挖掘；l 如将顾客按信用度分类，则用具有相同信用度的顾客的平均收入替换income中的空缺值。6）使用最可能

9、的值填充空缺值（最常用）：）使用最可能的值填充空缺值（最常用）：l 可以利用回归、贝叶斯计算公式或判定树归纳确定，推断出该条记录特定属性最大可能的取值；l 如，利用数据集中其他顾客的属性，构造一棵判定树，预测income的空缺值。2.2.噪声数据的处理？噪声数据的处理？噪声数据噪声数据u噪声噪声(noise)：是一个测量变量中的随机错误或偏是一个测量变量中的随机错误或偏差差u引起噪声数据的原因引起噪声数据的原因数据收集工具的问题数据输入错误数据传输错误技术限制命名规则的不一致如何处理噪声数据如何处理噪声数据 1）分箱）分箱(binning):u分箱方法通过考察分箱方法通过考察“邻居邻居”(即周

10、围的值即周围的值)来平滑存储数来平滑存储数据的值。据的值。u存储的值被分布到一些存储的值被分布到一些“桶桶”或箱中。由于分箱方法或箱中。由于分箱方法参考相邻的值，因此它进行局部平滑。参考相邻的值，因此它进行局部平滑。如何处理噪声数据如何处理噪声数据 分箱的步骤：分箱的步骤：v首先排序数据，并将它们分到等深（等宽）的箱中；首先排序数据，并将它们分到等深（等宽）的箱中；v然后可以按箱的然后可以按箱的平均值平均值、按箱、按箱中值中值或者按箱的或者按箱的边界边界等等进行平滑。进行平滑。按箱的按箱的平均值平均值平滑：箱中每一个值被箱中的平均值替换平滑：箱中每一个值被箱中的平均值替换按箱的按箱的中值中值平

11、滑：箱中的每一个值被箱中的中值替换平滑：箱中的每一个值被箱中的中值替换按箱的按箱的边界边界平滑：箱中的最大和最小值被视为箱边界，箱中平滑：箱中的最大和最小值被视为箱边界，箱中的每一个值被最近的边界值替换。的每一个值被最近的边界值替换。如何处理噪声数据如何处理噪声数据 等深分箱等深分箱(binning):按记录数进行分箱，每箱具有相同的记录数，每箱按记录数进行分箱，每箱具有相同的记录数，每箱的记录数称为箱的权重，也称箱子的深度。的记录数称为箱的权重，也称箱子的深度。示例：示例：已知一组价格数据：已知一组价格数据：15,21,24,21,25,4,8,34,28现用等深（深度为现用等深（深度为3）

12、分箱方法对其进行平滑，以对数据中的噪声进行）分箱方法对其进行平滑，以对数据中的噪声进行处理。处理。思考：思考：根据根据bin中值进行中值进行平滑的结果？平滑的结果？结果：结果：Bin1：8、8、8；Bin2：21、21、21；Bin3：28、28、28 在该例中，在该例中，price数据首先被划分并存人等深的箱中数据首先被划分并存人等深的箱中(深度深度3)。v 对于按对于按箱平均值箱平均值平滑，箱中每一个值被箱中的平均值替换。平滑，箱中每一个值被箱中的平均值替换。例如，箱例如，箱1中的值中的值4，8和和15的平均值是的平均值是9；这样，该箱中的每；这样，该箱中的每一个值被替换为一个值被替换为9

13、。v 对于按对于按箱边界箱边界平滑，箱中的平滑，箱中的最大和最小值被视为箱边界最大和最小值被视为箱边界。箱。箱中的每一个值被最近的边界值替换。中的每一个值被最近的边界值替换。v 类似地，可以使用按类似地，可以使用按箱中值箱中值平滑。此时，箱中的每一个值被平滑。此时，箱中的每一个值被箱中的中值替换。箱中的中值替换。如何处理噪声数据如何处理噪声数据 等宽分箱等宽分箱(binning):在整个属性值的区间上平均分布，即每个箱的区间在整个属性值的区间上平均分布，即每个箱的区间范围设定为一个常量，称为箱子的宽度。范围设定为一个常量，称为箱子的宽度。示例：示例：已知一组价格数据：已知一组价格数据：15,2

14、1,24,21,25,4,8,34,28现用等宽（宽度为现用等宽（宽度为10）分箱方法对其进行平滑，以对数据中的噪声进）分箱方法对其进行平滑，以对数据中的噪声进行处理。行处理。结果：结果：先排序：先排序：4，8，15，21，21，24，25，28，341）划分为等宽度箱子）划分为等宽度箱子Bin1：4、8；Bin2：15、21、21、24、25；Bin3：28、342）根据均值进行平滑）根据均值进行平滑Bin1：6、6；Bin2：21、21、21、21、21；Bin3：31、313）根据中值进行平滑）根据中值进行平滑Bin1：6、6；Bin2：21、21、21、21、21；Bin3：31、31

15、4）根据边界进行平滑：）根据边界进行平滑：Bin1：4、8；Bin2：15、25、25、25、25；Bin3：28、34练习：练习：已知客户收入属性已知客户收入属性income排序后的值（人民币元）：排序后的值（人民币元）：800，1000，1200，1500，1500，1800，2000，2300，2500，2800，3000，3500，4000，4500，4800，5000要求：分别用等深分箱方法要求：分别用等深分箱方法(箱深为箱深为4）、等宽分箱方法）、等宽分箱方法（宽度为（宽度为1000）对其进行平滑，以对数据中的噪声进行）对其进行平滑，以对数据中的噪声进行处理。处理。（1）等深分箱结

16、果：）等深分箱结果：（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）（1）等深分箱结果：）等深分箱结果：（2）按箱的中

17、值平滑，结果为：）按箱的中值平滑，结果为：箱箱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）（2）等宽分箱结果：）等宽分箱结果：（1）首先，划分为等宽的箱：）首先，划分为等宽

18、的箱：箱箱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）（2）等宽分箱结果：）等宽分箱结果：（1）按箱的中值平滑，结果为：）按箱的中值平滑，结果为：箱箱1（1350，135

19、0，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）如何处理噪声数据如何处理噪声数据 u2）聚类（）聚类（Clustering）：）：相似或相邻近的数据聚合在一起形成各个聚类集合，而那些位于聚类集合之外

20、的数据对象，被视为孤立点。特点：直接形成簇并对簇进行描述，不需要任何先验知识。通过聚类分通过聚类分析查找孤立析查找孤立点，消除噪点，消除噪声声如何处理噪声数据如何处理噪声数据 u3）计算机和人工检查结合）计算机和人工检查结合计算机检测可疑数据，然后对它们进行人工判断u4）回归）回归发现两个相关的变量之间的变化模式，利用回归分析方法所获得的拟合函数，帮助平滑数据及除去噪声。xyy=x+1X1Y1Y1 许多数据平滑的方法也是涉及离散化的数据归约方法许多数据平滑的方法也是涉及离散化的数据归约方法。例如，上面介绍的分箱技术减少了每个属性的不同值。例如，上面介绍的分箱技术减少了每个属性的不同值的数量。的

21、数量。另外，概念分层是一种数据离散化形式，也可以用于另外，概念分层是一种数据离散化形式，也可以用于数据平滑。例如，数据平滑。例如，price的概念分层可以把的概念分层可以把price的值映射的值映射到到inexpensive，moderately_priced和和expensive，从而减，从而减少了挖掘过程所处理的值的数量。少了挖掘过程所处理的值的数量。注意：注意：3.3.不一致数据的处理？不一致数据的处理？40不一致数据不一致数据处理不一致数据的方式：l人工更正l利用知识工程工具：如，如果知道属性间的函数依赖关系，可以据此查找违反函数依赖的值。l 数据字典：在将不同操作性数据库中的数据进行

22、集成时，也会带来数据的不一致。如：一个给定的属性在不同的数据库中可能具有不同的名字，如姓名在一个数据库中为Bill，在另一个数据库中可能为B。对此，可根据数据字典中提供的信息，消除不一致。4.2 数据集成和变换数据集成和变换q 数据挖掘所需要的海量数据集往往涉及多个数据源，因此，在信息处理之前需要合并这些数据源存储的数据。q 如果原始数据的形式不适合信息处理算法的需要，就要进行数据变换。1）数据集成）数据集成：将来自多个数据源的数据合并到一起：2）数据变换）数据变换：对数据进行规范化操作，将其转换成适合于数据挖掘的形式。1.1.数据集成？数据集成？43数据集成数据集成q 数据集成 将多个数据源

23、中的数据整合到一个一致的存储中。这些源可以是关系型数据库、数据立方体或一般文件。q 它需要统一原始数据中的所有矛盾之处，如字段的:同名异义；异名同义；单位不统一；字长不一致等。44数据集成数据集成集成过程中需要注意的问题v模式集成问题；模式集成问题；v冗余问题；冗余问题；v数据值冲突检测与消除数据值冲突检测与消除。45（1 1）模式集成问题）模式集成问题模式集成：v 整合不同数据源中的元数据；v 进行实体识别：匹配来自不同数据源的现实世界的实体如：如何确信一个数据库中的customer_id和另一个数据库中的cust_number是同一实体。通常，数据库的数据字典数据字典和数据仓库的元数据元数

24、据，可帮助避免模式集成中的错误。46（2 2）数据冗余问题）数据冗余问题数据冗余问题：v同一属性值不同的数据库中会有不同的字段名；v一个属性可以由另外一个表导出，如：一个顾客数据表中的平均月收入属性，可以根据月收入属性计算出来。47（2 2）数据冗余问题）数据冗余问题数据冗余问题：有些冗余可以被相关分析检测到：BABAnBBAAr)1()(,如果变量如果变量A、B间具有较高的相关系数，表明间具有较高的相关系数，表明A或或B可以可以作为冗余而去掉。作为冗余而去掉。除了检查属性是否冗余外，还要检查记录行的冗余。48(3)(3)数据值冲突问题数据值冲突问题数据值冲突对现实世界的同一实体，来自不同数据

25、源的属性值可能不同。产生的原因：表示、比例或编码不同。如：重量属性在一个系统中可能以公制单位存放，而在另一系统中可能以英制单位存放；同一商品的价格属性值不同地域采用不同价格单位；不同学校的成绩单可能以百分制、五分制及其他等级制来存放等等。2.2.数据变换？数据变换？50数据变换数据变换数据变换：将数据转换成适合数据挖掘的形式。涉及内容：（1）平滑）平滑：去掉数据中的噪声，将连续的数据离散化：分箱 聚类 回归。（2）聚集）聚集：对数据进行汇总和聚集 Avg(),count(),sum(),min(),max(),如，每天销售额（数据）可以进行聚集操作以获得每月或每年的总额。可用来构造数据立方体。

26、51数据变换数据变换数据变换：将数据转换成适合数据挖掘的形式。涉及内容：（3）数据概化）数据概化：使用概念分层，用更抽象（更高层次）的概念来取代低层次或数据层的数据对象 如，街道属性，可以泛化到更高层次的概念，如城市、国家；同样，对于数值型的属性，如年龄属性，可以映射到更高层次的概念，如年轻、中年和老年。52数据变换数据变换数据变换：将数据转换成适合数据挖掘的形式。涉及内容：（4）规范化）规范化：将数据按比例进行缩放，使之落入一个特定的区域，以消除数值型属性因大小不一而造成的挖掘结果的偏差。如将工资收入属性值映射到-1.0,1.0的范围内。常用的方法：最小最小-最大规范化；最大规范化；零零-均

27、值规范化（均值规范化（z-score规范化）；规范化）；小数定标规范化小数定标规范化。规格化的目的：规格化的目的：是将一个属性取值范围影射到一个特定范围之内，以是将一个属性取值范围影射到一个特定范围之内，以消除数值性属性因大小不一而造成挖掘结果的偏差。消除数值性属性因大小不一而造成挖掘结果的偏差。数据变换数据变换规范化规范化 在正式进行数据挖掘之前，尤其是使用基在正式进行数据挖掘之前，尤其是使用基于对象距离于对象距离的挖掘算法时，必须进行数据的规格化。的挖掘算法时，必须进行数据的规格化。如对于一个顾客信息数据库中如对于一个顾客信息数据库中年龄年龄属性或属性或工资工资属性，属性，由于工资属性的取

28、值比年龄属性的取值要大得多，若不进由于工资属性的取值比年龄属性的取值要大得多，若不进行规格化处理，基于工资属性的距离计算值将远远超过基行规格化处理，基于工资属性的距离计算值将远远超过基于年龄属性的计算值，这就意味着工资属性的作用在整个于年龄属性的计算值，这就意味着工资属性的作用在整个数据对象的距离计算中被错误放大了。数据对象的距离计算中被错误放大了。数据变换数据变换规范化规范化55数据变换数据变换规范化规范化数据规范化：将数据按比例缩放至一个小的特定区间：1）最小最小最大规范化最大规范化：假定minA和maxA分别为属性A的最小和最大值，则通过下面公式将A的值映射到区间new_min,new_

29、max中的v：AAAAAAminnewminnewmaxnewminmaxminvv_)_(例：例：假定属性income的最小与最大值分别为$12000和$98000，可根据最小最大规范化方法将其范围映射到0,1：如：属性值$73600将变换为：(73600-12000)/(98000-12000)*(1-0)+0=0.71656数据变换数据变换规范化规范化2）z-scorez-score规范化规范化（零均值规范化）：将属性A的值根据其平均值和标准差进行规范化；常用于属性最大值与最小值未知，或使用最小最大规范化方法会出现异常数据的情况。AAdevstandardmeanvv 其中，meanA、

30、standard-devA分别为属性A取值的均值和标准差。例：例：假定属性income的平均值与标准差分别为$54000和$16000，使用z-score规范化，则属性值$73600将变换为：(73600-54000）/16000=1.22557数据变换数据变换规范化规范化3）小数定标规范化小数定标规范化：通过移动属性A的小数点位置进行规范化，小数点的移动依赖于A的最大绝对值：例：例：假定A的取值范围-986,917，则A的最大绝对值为986，为使用小数定标规范化，用1000（即j=3）除每个值，这样-986被规范化为-0.986。jvv10其中，其中，j是使是使 Max(|v|)1的最小整数

31、的最小整数q规范化将原来的数据改变很多，特别是上述的后两规范化将原来的数据改变很多，特别是上述的后两种方法。种方法。q有必要保留规范化参数（如平均值和标准差，如果有必要保留规范化参数（如平均值和标准差，如果使用使用z-score规范化），以便将来的数据可以用一致规范化），以便将来的数据可以用一致的方式规范化。的方式规范化。注意：注意：59数据变换数据变换数据变换：将数据转换成适合数据挖掘的形式。涉及内容：（5）属性构造）属性构造：利用已有属性集构造出新的属性，并加入到现有属性集中以帮助挖掘更深层次的模式知识，提高挖掘结果的准确性；如，根据宽、高属性，可以构造一个新属性：面积。4.3 4.3 数

32、据归约数据归约u对大规模数据库内容进行复杂的数据分析常需要消耗大量的时间，使得这样的分析变得不现实和不可行；u数据归约（data reduction）：数据消减或约简，是在不影响最终挖掘结果的前提下，缩小所挖掘数据的规模。u数据归约技术可以用来得到数据集的归约表示，它小得多，但仍接近保持原数据的完整性。u对归约后的数据集进行挖掘可提高挖掘的效率，并产生相同（或几乎相同）的结果。4.3 4.3 数据归约数据归约数据归约的标准：数据归约的标准：u用于数据归约的时间不应当超过或“抵消”在归约后的数据集上挖掘节省的时间。u归约得到的数据比原数据小得多，但可以产生相同或几乎相同的分析结果。4.3 4.3

33、 数据归约数据归约数据归约的策略如下：u数据立方体聚集；u维归约；u数据压缩；u数值归约；u离散化和概念分层生成。1.1.数据立方体聚集？数据立方体聚集？64数据立方体聚集数据立方体聚集2.2.维归约？维归约？66维归约维归约u维归约：主要用于检测并删除不相关、弱相关或冗余的属主要用于检测并删除不相关、弱相关或冗余的属性维性维用于数据分析的数据可能包含数以百计的属性，其中大部分可能与挖掘任务不相关，是冗余的。如，分析顾客是否会在商场购买mp3播放器，诸如顾客的电话号码等属性多半是不相关的。维归约通过删除不相关的属性（或维），而有效减少数据库的规模。u最常用的方法：属性子集选择。67维归约维归约

34、属性子集选择属性子集选择q 目标：找出最小属性集，确保新数据集的概率分布尽可能接近原数据集的概率分布。q 如何找出原属性的一个好的子集 d个属性有2d个可能的子集。穷举搜索找出属性的最佳子集可能是不现实的，特别是当d的数目很大时。68维归约维归约属性子集选择属性子集选择q 启发式算法：对于属性子集选择，通常使用压缩搜索空间的启发式算法。它们的策略是做局部最优选择，期望由此导致全局最优解。69维归约维归约属性子集选择属性子集选择常用的启发式方法：1 1）逐步向前选择）逐步向前选择：u该过程由空属性集开始，选择原属性集中最好的属性，并将它添加到该集合中。u在其后的每一次迭代，将原属性集剩下的属性中

35、的最好的属性添加到该集合中。u 如：遗传算法是遗传算法是一种基于生物进化论和分子遗传学的全局随机搜索算法。70维归约维归约属性子集选择属性子集选择常用的启发式方法：2）逐步向后删除：）逐步向后删除：由整个属性集开始，每一步都删除尚在属性集中的最坏属性。直到无法选择出最坏属性或满足一定的阈值为止。如：粗糙集理论粗糙集理论，利用定义的数据集合U上的等价关系对U进行划分，对于数据表来说，这种等价关系可以是某个属性，或者是几个属性的集合。因此，按照不同属性的组合就把数据表划分成不同的基本类，在这些基本类的基础上进一步求得最小约简集。71维归约维归约属性子集选择属性子集选择常用的启发式方法：3 3）向前

36、选择和向后删除的结合：）向前选择和向后删除的结合：将向前选择和向后删除方法结合在一起；每一步选择一个最好的属性，并在剩余属性中删除一个最坏的属性。72维归约维归约属性子集选择属性子集选择常用的启发式方法：4 4）判定树归纳：）判定树归纳：u 在判定树的每个节点，算法选择“最好”的属性，将数据划分成类。u当判定树归纳用于属性子集选择时，不出现在树中的所有属性假定是不相关的；u出现在判定树中的属性形成归约后的属性子集。3.3.数据压缩？数据压缩？75数据压缩数据压缩 数据压缩就是利用数据编码或数据转换将原来的数据集合压缩为一个较小规模的数据集合。压缩算法分为两类：v 无损压缩（loseless）：

37、可以不丢失任何信息地还原压缩数据；如：字符串压缩v 有损压缩（lossy）：只能重新构造原数据的近似表示；如：音频/视频压缩。7677数据压缩数据压缩两类：1）无损压缩：指使用压缩后的数据进行重构(或者叫做还原，解压缩)，重构后的数据与原来的数据完全相同。u即：数据经过压缩后，信息不受损失，还能完全恢复到压缩前的原样。u压缩软件：Zip或RAR。78数据压缩数据压缩两类：2）有损压缩：又称破坏型压缩，即将次要的信息数据压缩掉，牺牲一些质量来减少数据量，使压缩比提高。u常用于压缩声音、图像以及视频。音频能够在没有察觉的质量下降情况下实现 10:1 的压缩比，视频能够在稍微观察质量下降的情况下实现

38、如 300:1 这样非常大的压缩比。常见算法：JPEG、MPEG、MP3等。算法机理：小波变换小波变换或主成份分析主成份分析4.4.数值归约？数值归约？80数值归约数值归约数值归约：通过选择替代的、较小的数据表示形式来减少通过选择替代的、较小的数据表示形式来减少数据量数据量。（1）有参方法）有参方法：通常使用一个参数模型来评估数据，该方法只需要存储参数，而不是实际数据，能大大减少数据量，但只对数值型数据有效。如：线性回归方法（最小二乘法）：Y=+X81数值归约数值归约数值归约：通过选择替代的、较小的数据表示形式来减少通过选择替代的、较小的数据表示形式来减少数据量数据量。（2）无参方法）无参方法

39、：常见的有：v 直方图；直方图；v 聚类；聚类；v 取样取样。821 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,30,30,30。试用直方图表示，以压缩数据。831 1）直方图）直方

40、图频率频率-值对应关系图值对应关系图842 2）聚类）聚类聚类：将原数据集划分成多个群或聚类。u原则原则：同类中的数据彼此相似；不同类中的数据彼此不相似。u相似相似：通常用空间距离度量u 聚类的有效性有效性依赖于实际数据的内在规律。853 3）取样）取样取样（抽样）：允许用数据的较小随机样本（子集）表示大的数据集。取样方法：u 不放回简单随机取样（Simple Random Sampling Without Replacement,SRSWOR）u放回简单随机取样（Simple Random Sampling With Replacement,SRSWR）u 聚类取样：先聚类，后取样u 分层取

41、样：先分层，后取样。取样取样SRSSRSSRSWOR(简单随机选简单随机选样，不回放样，不回放)SRSWR(简单随机选简单随机选样，回放样，回放)原始数据原始数据87取样取样聚类采样：聚类采样：首先将大数据集D划分为M个互不相交的聚类，然后再从M个类中的数据对象分别进行随机抽取，可最终获得聚类采样的数据子集。聚类采样方法示意图聚类采样方法示意图88聚类取样聚类取样89取样取样分层取样：分层取样：首先将大数据集D划分为互不相交的层，然后对每一层简单随机选样得到D的分层选样。如，根据顾客的年龄组进行分层，然后再在每个年龄组中进行随机选样，从而确保了最终获得分层采样数据子集中的年龄分布具有代表性。9

42、0分层取样分层取样分层采样方法示意图分层采样方法示意图4.4 4.4 数据离散化和概念分层数据离散化和概念分层*三种类型的属性值：l标称型（名称型、名义型）：数值来自于无序集合，如性别、地名、人名等。l序数型：数值来自于有序集合，如奖学金的等级；职称分布等。l连续型：实数值，如温度、体重等。离散化技术：l通过将属性（连续取值）阈值范围分为若干区间，来帮助消减一个连续（取值）属性的取值个数。l 如，将气温划分为：冷、正常、热。4.4 4.4 数据离散化和概念分层数据离散化和概念分层*概念分层：l概念分层定义了一组由低层概念到高层概念集的映射。允许在各种抽象级别上处理数据，从而在多个抽象层上发现知

43、识。l用较高层概念替换低层次（如年龄的数值）的概念，以此来减少取值个数。l 虽然一些细节数据在泛化过程中消失了，但这样所获得的泛化数据或许更易于理解、更有意义。l另外，在消减后的数据集上进行信息处理显然效率更高。l 概念分层结构可以用树来表示，树的每个节点代表一个概念。93概念分层概念分层离散化方法离散化方法常用的离散化方法：1）分箱：）分箱：属性的值可以通过将其分配到各分箱中而将其离散化。v 利用每个分箱的均值或中数替换每个分箱中的值（利用均值或中数进行平滑）。v 循环应用这些操作处理每次操作结果，就可以获得一个概念层次树。离散化方法离散化方法常用的离散化方法：2）直方图：）直方图：l等宽直

44、方图中，将数据划分成相等的部分或区间，如(0,100$)、(100$,200$、(200$,300$.l等深直方图：值被划分使得每一部分包括相同个数的样本。离散化方法离散化方法常用的离散化方法：3）聚类分析聚类分析：v 聚类算法可以将数据集划分为若干类或组。v 每个类构成了概念分层树的一个节点；v 每个类还可以进一步分解为若干子类，从而构造更低水平的层次。v 当然类也可以合并起来构成更高层次的概念水平。4）基于熵的离散化基于熵的离散化：熵是一种信息度量的方法5）通过自然划分分段通过自然划分分段基于熵的离散化基于熵的离散化思想：思想：u 考虑类别信息，递归计算信息熵，产生分层的离散化。I(S)=

45、初始不确初始不确定性：定性：基于熵的离散化基于熵的离散化思想：思想：u 考虑类别信息，递归计算信息熵，产生分层的离散化。给定一个数据元组的集合给定一个数据元组的集合S，基于熵对，基于熵对S离散化的方法如下：离散化的方法如下：1）属性A中的每个取值可被认为是一个潜在的区间边界或阈值T。例如，A的取值v可以将样本S划分为分别满足Av和Av两个子集，这样就创建了一个二元离散化。2）对于数据集S，根据所划分子集而获得的最大熵增益来选择阈值，划分后数据集S提供的信息如下：E(A)=学习属性学习属性A之之后的不确定性：后的不确定性：基于熵的离散化基于熵的离散化 其中S1和S2分别对应于S中满足条件：AT与

46、AT，的样本。对给定的集合，熵函数Ent根据集合中样本的类分布来计算。例如，给定m个不同类别，S1的熵就是：其中pi为类i在S1中出现的概率，等于S1中类i的样本除以S1中样本的总行数。同理，计算Ent(S2)。3）确定阈值的过程递归的用于所得到的每个划分，直到满足某个终止条件，如：Ent(S)-I(S,T)信息增益不能低于信息增益不能低于：基于熵的离散化基于熵的离散化 与迄今为止提到的其他方法不同，基于熵的离散化使用了类别信息。这使得它更有可能将区间边界定义在准确位置，有助于提高分类的准确性。此处用到的信息增益和信息熵也用于决策树归纳。自然划分分段自然划分分段思想：思想：u 将数值区域划分为

47、相对一致的、易于阅读的、看上去更直观或自然的区间。聚类分析产生的概念分层可能会将一个工资区间划分为：51263.98,60872.34而通常数据分析人员希望看到划分的形式为50000，60000u自然划分的3-4-5规则规则常可以将数值数据划分为相对一致和“自然”的区间。一般的，根据最重要的数字上的值区域，递归的和逐层的将给定的数据区域划分为3、4或5个等宽区间。自然划分的自然划分的3-4-5规则规则 规则的划分步骤：规则的划分步骤：如果一个区间最高有效位最高有效位上跨越3，6，7或9个不同的值，就将该区间划分为3个等宽子区间；(72,3,2)如果一个区间最高有效位最高有效位上跨越2，4，或8

48、个不同的值，就将该区间划分为4个等宽子区间；如果一个区间最高有效位最高有效位上跨越1，5，或10个不同的值，就将该区间划分为5个等宽子区间；将该规则递归的应用于每个子区间，产生给定数值属性的概念分层；自然划分的自然划分的3-4-5规则规则 规则的划分步骤：规则的划分步骤：对于数据集中出现的最大值和最小值的极端分布，为了避免上述方法出现的结果扭曲，可以在顶层分段时，选用一个大部分的概率空间。e.g.5%-95%例如，在资产数据集中，少数人的资产可能比其他人高几个数量级。如果按照最高资产值进行分段，可能导致高度倾斜的分层。此时，可以在顶层分段时，选用一个大部分的概率空间。e.g.5%-95%。越出

49、顶层分段的特别高和特别低的部分采用类似的规则划分方法形成单独的区间。示例：示例：3-4-5规则规则 假定AllElectronics所有分部1999年的利润覆盖了一个很宽的区间，从-351.00$到4700$。要求利用3-4-5规则自动构造利润属性的一个概念层次树。示例：示例：3-4-5规则规则思路：思路：设在上述范围取值为5%至95%的区间为：-159$至1838$。应用3-4-5规则的具体步骤如下：1）根据以上信息，在利润数据集中最小和最大值分别为：MIN=-351$,MAX=4700$。而根据以上分析，对于分段的顶层或第一层，要考虑的最低（5%）和最高（95%）的值是：LOW=-159$

50、,HIGH=1838$。2）依据LOW和HIGH及其取值范围，确定最高有效位为1000$，LOW按1000$美元向下取整，得到LOW=-1000$；HIGH按1000$向上取整，得到：HIGH=2000$。示例：示例：3-4-5规则规则3）由于该区间在最高有效位上跨越了3个值，即(2000-(-1000)/1000=3，根据3-4-5规则，该区间被划分成3个等宽区间：(-1000$,0,(0,1000$,(1000$,2000$。这代表分层结构的最顶层。示例：示例：3-4-5规则规则4）现在，考察原数据集中MIN和MAX值与最高层区间的联系。由于MIN值落在区间(-1000$,0，因此调整左边

51、界，对MIN取整后的-400$，所以第一个区间调整为(-400$,0。而由于MAX值不在最后一个区间(1000$,2000$中，因此需新建一个区间（最右边区间）。对MAX取整后得5000$，因此新区间为(2000$,5000。因此最终，概念树分层结构的最顶层包含4个区间：(-400$,0,(0,1000$,(1000$,2000$,(2000$,5000$。示例：示例：3-4-5规则规则5）对上述每个区间递归应用3-4-5规则，形成分层结构的下一个较低层：第一个区间(-400$,0：划分为4个子区间(-400$,-300$,(-300$,-200$,(-200$,-100$,(-100$,0$

52、.第二个区间(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规则可继续在较低的层次上迭代。3-4-5规则规则例子例子(-$4000-$5,000)(-$400-0)(-

53、$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第二步第二步第四步第四步

54、第一步第一步 -$351-$159profit$1,838$4,700 Min Low(i.e,5%-tile)High(i.e,95%-0 tile)Maxcount(-$1,000 -$2,000)(-$1,000-0)(0-$1,000)第三步第三步($1,000-$2,000)分类数据的概念分层生成分类数据的概念分层生成分类（名义）数据（分类（名义）数据（categorical data）：）：是一种离散数据；可取有限个值且这些值之间无大小和顺序。如：国家、工作、商品类别等。分类数据的概念分层生成分类数据的概念分层生成有一些典型的方法可用于生成分类数据的概念分层：有一些典型的方法可用于

55、生成分类数据的概念分层：1）由用户或专家在模式级显式的说明属性的部分序）由用户或专家在模式级显式的说明属性的部分序：通过在（数据库）模式定义时指定各属性的有序关系，可帮助轻松构造相应的概念分层。如：关系数据库或数据仓库的维location可能包含如下一组属性：street,city,province,country。可在数据库模式级定义一个全序，如：streetcityprovincecountry，来定义分层结构。分类数据的概念分层生成分类数据的概念分层生成有一些典型的方法可用于生成分类数据的概念分层：有一些典型的方法可用于生成分类数据的概念分层：2）对数据进行分组（聚合）产生分层）对数据进

56、行分组（聚合）产生分层：属于人工定义概念分层结构的一部分。如：在模式级说明了省（province）和国家（country）形成一个分层后，可能想人工地添加某些中间层。如显式的定义：安徽、江苏、山东 华东地区，广东、福建 华南地区，等中间层次。分类数据的概念分层生成分类数据的概念分层生成有一些典型的方法可用于生成分类数据的概念分层：有一些典型的方法可用于生成分类数据的概念分层：3 3）定义一组属性集，但不说明它们的偏序）定义一组属性集，但不说明它们的偏序：用户可以说明一个属性集，形成概念分层，但并不显式说明它们的属性，由系统自动产生属性顺序以构造一个有意义的概念层次树。但如果没有数据语义的知识，

57、想要获得任意一组属性的顺序关系是很困难的。方法：方法：较高层概念通常包含若干从属的较低层概念。且与较低层概念相比，通常包含较少数目的不同值。因此，可根据给定属性集中每个属性不同值的个数，自动产生概念分层。属性集的规格属性集的规格 根据在给定属性集中，每个属性所包含的不同值的个数，可以自动的生成概念分成；不同值个数最多的属性将被放在概念分层的最底层。countryprovincecitystreet5个不同值个不同值65 个不同值个不同值3567 个不同值个不同值674,339 个不同值个不同值本章小结本章小结数据预处理：建立数据仓库和进行数据挖掘的一个重要问题u数据清理：填充空缺值、平滑数据、

58、找出孤立点、纠正不一致u数据集成：将来自不同数据源的数据整合为一致的数据存储。u数据变换：将数据变换成易于数据挖掘的形式。u数据归约：数据约简，缩小所挖掘数据的规模。u数值数据的概念分层：使用高层的概念来替代底层的属性值。习题习题数据元组中age的值如下（按递增序）：13，15，16，1，19，20，20，21，22，22，25，25，25，30，33，33，35，35，36，40，45，46，52，70。问题：u使用等深分箱（箱深为3）的平均值平滑方法对上述数据进行平滑。u使用最小-最大规范化方法，将age的属性值35转换到0,1.0区间。u使用z-score规范化方法转换age的属性值35，其中age的标准差为12.94年。u使用小数定标规范化转换age属性值35.u画出属性age宽度为10的等宽直方图。117为什么要进行数据清理，有哪些方法。为什么要进行数据清理，有哪些方法。在进行数据集成时，需要注意什么。在进行数据集成时，需要注意什么。数据变换的目的？方法？数据变换的目的？方法？数据归约的方法？数据归约的方法？为什么进行连续属性离散化？为什么进行连续属性离散化？复习与思考问题复习与思考问题