韩家炜数据挖掘概念与技术第3章ppt课件.pptx

《韩家炜数据挖掘概念与技术第3章ppt课件.pptx》由会员分享，可在线阅读，更多相关《韩家炜数据挖掘概念与技术第3章ppt课件.pptx（119页珍藏版）》请在三一办公上搜索。

1、第3章 数据预处理,2014-11,目录,3.1 数据预处理：概览3.2 数据清洗3.3 数据聚合3.4 数据删减3.5 数据转换和数据离散化3.6 总结,数据预处理,真实世界中的数据库对噪声、缺失、以及不一致的数据是高度敏感的，因为这些数据常常容量很大，并且很可能是多来源的异质数据。数据的低质量会导致低质量的数据挖掘结果。“如何处理数据，以有助于提到数据的质量和数据挖掘的效果呢？数据被如何处理能够提高挖掘过程的高效性和简易型呢？”这里有几种数据预处理的技术，包括：数据清洗，数据聚合，数据删减，数据转换。这些技术能提升挖掘算法的精确性和效率。它们并非相对独立，是共同工作的。比如，数据清洗也包含

2、数据转化以去除错误数据。,3.1 数据预处理：概览,3.1.1 数据质量：为什么做数据预处理？如果数据满足了人们的预期用途的需求，则数据质量好。数据质量包含很多因素，如：精确性、完整性、一致性、时效性、可信性以及可解释性。数据的不精确、不完整以及不一致是大型真实世界数据库以及数据仓库的常见特点。,数据的不精确性,不精确数据有很多可能的原因：数据收集工具可能错误，数据记录中很多人为的或计算机导致的的错误。用户也可能在值当他们不愿意暴露个人资料的时候在一些强制必须填写的栏目故意提交了错误的资料（如生日直接用默认值1月1日）。这是一些伪装缺失的数据。数据在传输时也可能出错。一些技术上的限制，例如并行

3、同步数据的传输和计算时缓冲区间的有限性。不正确的数据也可能因为命名习惯或者数据编码的不一致性，或者输入域的格式不一致。重复的元组也需要进行数据清洗。,数据的不完整性,导致数据的不完整性的原因也有很多：感兴趣的属性并不能总是可获得，比如销售交易数据中的客户资料信息。另外，很可能因为在当时的条目中，该属性被认为是不重要的。相关联的数据没有被记录可能因为误解或者设备故障的原因。,不一致的数据,和其他数据记录不一致的数据应该被被删掉。另外，数据历史和修改可能被忽视。缺失的数据，特别是缺失了某些属性值的元组，值可能需要被推断。数据质量依赖于人们对数据的预期使用。两个不同的用户可能对一个给定的数据库的质量

4、有不同的评估。比如，一个市场分析员获得了一个由顾客地址列表的数据库。一些地址是过期或错误的，总体上有80%是精确的。市场分析员认为这是一个针对目标市场的很大的客户数据库，对数据的精确性很满意。但是，销售经理可能认为数据是不精确的。,数据的时效性,时效性也可能影响数据质量：比如你在浏览AllElectronics公式的每月销售奖金的数据分布。一些销售代表在月末的时候没有及时的提交他们的销售记录。在月末之后可能有一些数据的更正和调整。从每个月的时间周期来看，数据库中存放的数据是不完整的。因为月末的数据没有被及时的更新导致了数据质量的负面性影响。,数据的可信性和可解释性,另外的两个影响数据质量的因素

5、是可信性和可解释性。可信性反映用户有多相信这些数据，可解释性反应数据有多容易被理解。例如一个数据库在某一时刻有一些错误，然后都被更正了。过去的错误导致了销售部门用户的大量问题，因此他们不再相信这些数据。这些数据可能使用了很多会计代码，销售部门不懂如何解释。即使这些数据是精确完整一致和有时效性的，但是仍然被销售部门用户认为是低质量的。,3.1.2 数据预处理的主要任务,数据预处理的主要步骤是：数据清洗数据聚合数据删减数据转换,数据清洗,数据清洗的工作是清洗数据，通过填写缺失的数据，平滑噪音数据，识别需要去除的离群点，以及解决不一致性。如果用户相信数据是脏数据，便不可能信任数据挖掘的结果。另外，脏

6、数据可能导致挖掘过程中的混乱，导致不可靠的输出结果。即使绝大多数的挖掘方法都有处理数据不完整和噪声的步骤，但仍然不够健壮。通常，这些算法集中避免建模的函数对数据的过度拟合。因此，有用的预处理的步骤是把你的数据通过一些数据清洗的例程工作来完成。,数据聚合,如果你的分析中数据是多来源的，则需要进行数据聚合工作，即聚合多种数据库，数据立方，以及文件。一个给定概念的属性在不同数据库中可能有不同的命名，导致了不一致性和冗余。例如，顾客的主键属性在一个数据库中是custom_id, 在另外的数据库却是cust_id。命名的不一致性也可能发生在属性值的上面。例如，一个数据库中人名的第一个名字是”Bill”，

7、 在另一个中是”William”, 第三个中是”B”.,同时，你怀疑一些属性值是由其他属性值计算的（比如年收入）。有大量的冗余数据会让知识发现过程速度降低以及产生混乱。因此，除了数据清洗，必须采取步骤来避免在数据聚合中出现冗余。通常，数据清洗和数据聚合在为数据仓库准备数据时被整合成一个预处理步骤。在数据清洗之外，在鉴别和去除因聚合导致的冗余数据的步骤。,数据删减,“我被选做分析的数据集非常大，这确信无疑的会减慢挖掘过程。是否有一个方法能够在不影响数据挖掘的效果的情况下减小数据集呢？”这就是数据删减。数据删减能得到一个数据集的删减集，比原来的数据小很多，但是能产生相同的（或几乎相同的）分析结果。

8、数据删减包括维度删减和数据块删减。,维度删减：维度删减是一种获得原有数据的删减或者压缩集的数据编码方案。比如，数据压缩技术（小波分析、主成分分析）属性子集选择（去除不相关属性），以及属性构造（如从原有数据集中建立小的更有用的属性）数据块删减：数据被可选的更小的数据替换，使用参数模型（如回归和对数-线性模型）或者非参数模型（直方图，聚类，抽样和数据聚集）。,数据转换,在神经网络、最近邻分类以及聚类分析中，你可能使用一个基于距离的挖掘算法。如果将数据标准化，按比例缩小到一个更小的范围，如0.0，1.0中，可能会得到更好的效果。你的顾客数据中可能包含年龄属性和年薪属性。年薪属性会使用一个比年龄大得多

9、的值范围。因此，如果属性是左非规范的，距离测量会在年薪上产生更大的距离权重。,离散化和概念层次生成也很有效。用于将原始数据值替换成范围区间或者高层概念层级。例如，原始的年龄值被高层级的概念：年轻人，成年人和老年人替换。 离散化和概念层次生成是数据挖掘的强大工具，因为他们允许数据挖掘在更多抽象级别上进行。标准化、离散化和概念层次生成是数据转换的几种形式。,多种预处理的形式,预处理的作用,总之，真实世界中的数据更可能是脏的、不完整和不一致的。数据预处理技术可以提升数据质量，因而提升接下来的挖掘过程的精确性和有效性。数据预处理是知识发现过程的一个重要步骤，因为好的质量抉择基于好的质量的数据。发现数据

10、的异常，在早期进行修正，减少被分析的数据会给决策制定带来巨大的回报。,3.2 数据清洗,3.2.1 缺失值假设你需要分析AllElectronics的销售和顾客数据。你注意到许多元组在一些属性例如顾客收入上没有记录值。如何能填写这些属性的缺失值呢？有如下方法：1. 忽略元组。常常在类别标签（假定是分类任务）缺失时这样做。这种方法不是非常有效，除非元组包含若干缺失值的属性。当每个属性上缺失的值占的比例变化很大时，这种方法特别糟糕。通过忽略这些元组，也不会使用这些元组剩下的属性值。本来这些数据可以很有用的。,2 手工填写缺失值。通常，这种方法耗时，并且对一个有很多缺失值的大型数据集来说并非可行。3

11、 使用一个全局常数来填写缺失值。可以将所有缺失的属性值用同一个常数，例如标签“Unknown”或者”-”来表示。如果缺失值被“Unknown”替换，挖掘算法可能错误的认为形成了一个有趣的概念，因为他们都有一个共同的值”Unknown”.因此，即使这种方法很简单，却也并非不会出错。4 使用一个属性的中心性测量来填写缺失值。对于标准（对称的）数据分布，可以使用平均值，对偏斜数据分布可以使用中值。,5. 使用给定元组的类别相同的所有样本的均值或者中值。例如，如果根据顾客的信用风险来分类顾客，可以计算和该顾客的信用风险类别相同的所有顾客的收入均值，来填写给定元组的缺失的收入属性。如果对于给定类别数据分

12、布是偏斜的，则使用中值。6. 使用缺失值的最可能的值来填写。值可以由回归、使用Bayes公式的基于推理的工具，或者决策树推理。如，使用你的数据集中的其他顾客的属性，可以建立一个预测顾客缺失的收入值的决策树。方法3-6 改变了数据，即填写的值可能是不正确的。其中，方法6是一种流行的策略。,需要重点指出的是，在某些情形，一个缺失的值并非意味着数据的错误！例如，当申请信用卡时，申请者被要求提供驾驶证号码。没有驾驶证的自然就会在这一项不填写。表格应当允许回答者做详细说明，例如“不适合”。软件例程可能被使用来发现其他的空值（例如，“不知道？”或者“空”）。理想情况是，每一个属性有一个或者多个针对空值情形

13、的规则。这些规则可以详细指明空值是否被允许或者种类值如何被处理和转换。属性域可以被留作空白，如果在随后的商业过程中能够被提供。因此，即使在数据被获取之后，我们能够尽力去清洗，好的数据库和数据表过程设计能在第一时间最小化缺失值和错误的数目。,3.2.2 噪声数据,“什么是噪声？”噪声是度量变量的随机错误或者偏差。第2章中介绍的基本统计描述技术（箱子图、散点图）、数据可视化的技术科用来识别离群点，这些可能代表噪声。给定一个数值属性，例如价格，如何来平滑数据以去除噪声呢？有如下技术：1、装箱装箱方法通过参考数据值的“邻居”（即该值周围的数据）来平滑排好序的数据。,排好序的数据被分布到一系列的“桶”,

14、或箱子中。因为装箱方法参考值的邻居，所以使用的是局部平滑。有若干种装箱技术：1）等频装箱。例如，价格属性先被排序，然后被分割到箱子的大小为3的等频箱子中。2）箱子均值平滑。箱子中的每个值被箱子的均值替代。3）箱子中值平滑。每个箱子值被箱子中值取代。4）箱子边界平滑。箱子值被最靠近的边界值（最大值或最小值）取代。箱子的宽度也大，平滑效果也越显著。另外，等宽度的箱子，即每个箱子间隔是个相同的常数也常被使用。箱子技术也是一种数据离散化的技术。,2、回归：数据平滑也可以使用回归的方法，即将数据值通过一个函数来表达。线性回归是寻找两个属性（或变量）的最好的直线来通过一个属性预测另外一个。多元线性回归是线

15、性回归的扩展。超过两个的属性被包含在其中，数据被拟合成一个高维超平面。3、离群点分析：通过聚类的方法可以检测离群点。例如，相似的值被分组，或“簇”。值落在簇之外的被认为是离群点。,4、其他方法：很多数据平滑技术也适用于数据离散化和数据削减。例如，装箱技术削减了每个属性的不同值的个数。在基于逻辑的数据挖掘方法例如决策树中，因为需要不断重复的在排序数据上做值的比较，因此这相当于是数据削减。概念分层是数据离散化的一种，可以用来做数据平滑。一个概念分层例如价格，可以映射真实的价格值到便宜、中等、昂贵上。这样削减了挖掘过程需要处理的数据值的个数。一些分类方法有内置的数据平滑机制。,3.2.3 数据清洗作

16、为一个过程,“数据清洗是一个巨大的工作。数据清洗作为一个过程怎么样呢？在处理这个任务是人如何精确的进行呢？有任何可用的工具吗？”数据清洗作为一个过程的第一步是不一致性检测。不一致性可能由多种原因导致：设计很差的数据表人为的输入错误故意的错误（不希望泄露个人信息的回答者），以及数据延迟（如过期的地址）还可能因为不一致的数据表达和编码的不一致使用其他的来源例如测量设备的错误导致的记录数据和系统错误错误也可能发生在被用于和预期不同的目的时还有一些不一致性是因为数据聚合导致的（一个给定的属性在不同数据库中使用不同的名称）,“那么，如何进行不一致检测呢？”使用任何你事先已经知道的关于数据的相应属性的知识

17、，这种知识被称为“元数据”。例如，数据的类型和每个属性的域是什么？每个属性的可接受的值是什么？基本的统计数据描述（Section 2.2）对于获取数据趋势和鉴别异常很有用。例如，寻找均值，中值和众数。数据是对称还是偏斜的？值的取值范围是？所有的值都落在期望的区间吗？每个属性的标准差是多少？值在距离均值两倍标准差的范围外的属性值可能是潜在离群值。属性之间有已知的依赖关系吗？在这个步骤，你可能需要写下你自己的脚本或者使用后面将要讨论的一些工具。通过这样的方式，你可以找到噪声，离群点，需要察觉的异常值。,作为一个数据分析师，你需要寻找不一致的编码以及任何不一致的数据表达（比如，2010/12/25

18、和 25/12/2010 )。字段过载是另一个错误源，常常是设计者将新属性的定义挤进一个已经定义好的属性未使用的位（bit)。（例如，一个属性的值范围是32位二进制中的31位，剩1个位未使用）。数据还需要使用唯一性规则，连续性规则和空值规则来检查。唯一值规则是给定属性的每一个值必须和该属性的其他所有值不同。连续性规则是在属性的最小值和最大值之间不能有缺失值（例如，检查号码）。空值规则指明了空白、提问标记、特殊字符或其他的字符串可能指代空值条件（如一个给定属性的值不可获得），以及这样的值如何被处理。,空值规则应当指明如何记录空值条件，例如，存储数值属性的0值，字符属性的空白，或者其他可能使用的习

19、惯（如，像“不知道”或者“？”的输入应当被转换成空白）。有一系列不同的商业工具可以用来做不一致性检测。数据洗擦工具使用简单的领域知识（如邮政地址和拼音检查的知识）来检测和修正数据中的错误。这些工具在清洗多种来源的数据时依赖于语法解析和模糊匹配技术。数据审核工具通过分析数据发现规则和关系来寻找不一致性，以及检查违反了条件的数据。它们是数据挖掘工具的变体。它们可能使用统计分析来发现关联，或者聚类发现离群点。也可能利用2.2节介绍的基本统计数据描述方法。,一些数据不一致性可以通过使用外部参考来人工改正。例如，数据输入的错误可以通过纸上跟踪的方式来改正。绝大部分的输错，都需要进行数据转换。即一旦我们发

20、现了不一致性，常常需要定义和应用转换来修正。商业工具在数据转换步骤可以起到作用。数据迁移工具允许做简单的转换例如将字符串“gender”变为”sex”. ETL(抽取/转换/加载工具）允许用户规定使用图形用户接口（GUI) 来转换。这些工具常常只支持有限的转换集，因此，我们还常常选择编写定制的脚本来做数据清洗的工作。,不一致性的两个步骤即不一致性检测和数据转换是迭代的过程。这个过程是修剪错误，很耗时。,3.3 数据聚合,数据挖掘经常需要数据聚合合并多个数据库中的数据。细致的聚合能帮助减少和避免结果数据集中的冗余和不一致性。并在随后的数据挖掘过程中提高准确率和速度。,3.3.1 实体识别问题,数

21、据聚合是将多种数据来源结合到一个数据库中，如数据仓库。这些来源包含多种数据库，数据立方以及文件。模式聚合和对象匹配可能比较复杂。如何将真实世界中的实体等价地匹配到多个数据源中？这就是实体识别问题。,例如，数据分析师或者计算机如何确信一个数据库中的customer_id和另一个库中的cust_number指的是同一个属性？包含名称，含义，数据类型，属性的取值范围，以及控制规则的元数据在3.2节被探讨过。这种元数据能帮助避免模式聚合中的错误。元素据还可以用来帮助数据转换（例如，数据编码pay_type在一个数据库中可能是”H”、“S”,在一个中可能是”1”和“2”).因此，这个步骤和数据清洗也互相

22、关联。,将一个数据库中的属性匹配到另一个数据库时，需要特别注意数据的结构。必须保证源系统中的任何属性的功能性依赖关系以及参考限制与目标系统匹配。例如，在一个系统中，discount可能被按次序被应用，在另一个系统中则按每一个单个的项目内部的次序被应用。如果在聚合之前没有发现这个，目标系统中的商品则会有错误的discount信息。,3.3.2 冗余和关联性分析,冗余是数据聚合的另外一个重要的问题。一个属性（例如年收入）是冗余的，如果它能从其他的属性或属性集合推导得到。属性的不一致或者维度命名也会导致相应数据集中的冗余。这种冗余可以使用关联性分析来检测。给出两个属性，这种分析能基于可获得的数据测量

23、一个属性在多强的程度上暗含了另一个。对于名词数据，可以使用卡方检验。对数值型数据，使用关联系数和协方差。,名词数据的卡方关联检验,对名词数据，两个属性A和B之间的关联关系可以使用卡方检验来发现。假设A有c个不同的值，a1, a2,.ac. B有r个不同的值，b1,b2,br.则包含属性A和属性B的元组可以使用一个列联表来表示，其中A属性的c个不同值构成表的列，B属性的r个不同值构成表的行。令(Ai, Bj)表示属性A取ai而属性B取bj的联合事件，即（A=ai, B=bj).,在表中每一个可能的(Ai, Bj)联合事件都有一个单元。卡方值的公式是：其中，oij表示观察到的（Ai, Bj)联合事

24、件的频率（实际次数）。而eij表示(Ai,Bj)事件的期望频率，计算公式是：其中，n是数据元组的个数。,公式3.1计算全部r*c个单元的值。那些实际的次数和期望值相差最大的是对卡方值贡献最大的。卡方统计检验假定属性A和属性B是互相独立的，即这两个属性之间没有关联。基于显著性水平，自由度是(r-1)*(c-1)。如果假设被拒绝，则A和B统计相关。,卡方检验举例例3.1,假设调查了1500个人，按性别分成男和女。每个人投票是否喜欢阅读小说。这样，就有了两个属性：gender和preferred_reading.观察到的每个可能的联合事件的次数在表3.1中。圆括号中的表示事件的期望次数，按照公式3.

25、2计算出来的。,可以注意到，每一行中，期望次数的总和必须和这一行的观察次数的总和相等；每一列中，期望次数的和等于这一列的观察次数的和。利用公式3.1，计算卡方值为：对于2*2的表，自由度为(2-1)*(2-1)=1. 在自由度为1时，卡方值为10.828则可以在0.001的显著性水平上拒绝值原假设。因为计算出的值大于这个值，所以能以更小的显著性水平拒绝原假设，即性别和是否喜欢读小说之间存在强相关关系。,数值型数据的相关系数,相关系数rAB的值在-1到+1之间。如果rAB 0，则称A和B正相关。表示A的值随着B的值的增大而增大。值越大，相关性越强。因此，一个很大的值意味着A（或B)需要被作为冗余

26、删除。如果rAB =0,则A和B相互独立，它们之间没有任何关系。如果值0,则A和B负相关，表示一个属性的值随着另一个值的降低而增大。散点图可以用来可视化属性之间的关联关系。,注意：关联并不表示因果。即如果A和B相关，但并不意味着A导致B或者B导致A。例如，在分析一个人口统计数据库时，我们发现表示医院数目的属性和盗车数目相关。但这并不表示一个属性导致了另外一个。两个属性实际上都是因为人口数这第三个属性导致的。,数值型数据的协方差,在概率理论和统计学中，相关性和协方差是评价两个属性是否一起发生变化的两种相似的测量。考虑两个数值型属性A和B, n个观察(a1,b1),(an,bn). 属性A和属性B

27、的均值，即期望值为：和,则属性A和B的协方差为：如果利用公式3.3来计算相关系数rA,B,则：其中分母是属性A和B的标准差。可以看到，,协方差举例例3.2,考虑下表，这是一个观察到的5次AllElectronics和Hightech公式的股票价格。如果股票是被同一个公司的趋势影响，那么它们的价格是否一起涨落呢？,计算均值：则协方差为：协方差值为正，因此，我们可以说两个公司的股票是一起涨的。,方差是协方差的特例，是两个属性相等，即属性自身的协方差。,3.3.3 元组复制,除了检测属性间的冗余，元组级别的冗余也需要被检测。不规范表的使用（一般是为了避免连接提高性能）是另一种数据冗余的来源。在不同的

28、复制之间常常产生不一致性。因为不精确的数据输入或者更新了一部分而非全部的数据。例如，一个购买订单数据库包含购买者的姓名和地址属性，而非这个信息的主键信息。不一致性就可能产生，比如在购买订单数据库中同样的购买者姓名却是不同的地址。,3.3.4 数据值和检测与解析的冲突,数据聚合还包含数据值冲突的检测和解析。例如，对于同一个真实世界实体，不同来源的属性值可能不同。可能是因为表达、刻度或者编码的不同。比如，体重属性在一个系统中可能以公制单位存放而在另一个中以英帝单位存放。学校之间交换信息的时候，每个学校有自己的课程设置和等级模式。一个大学可能采用一个季度系统，一个数据库系统中3门课程，等级从A+到F

29、。另一个可能采用学期值，数据库中提供2门课程，等级从1到10. 很难制定两所大学精确的课程等级转换规则，交换信息很困难。,属性的抽象级别也可能不同。在一个抽象级别更低的系统中，同一个属性的级别比另一个系统中同样的值更低。比如，total_sales在一个数据库中指AllElectronics的一个部门的总体销售，而同样名称的属性在另一个数据库中指的是一个给定地区的总体销售。,3.4 数据删减,3.4.1 数据删减策略概览数据删减策略包含减少维度，减少数据块以及数据压缩。维度删减是减少考虑的随机变量或属性的个数。维度删减方法包括小波转换，主成分分析，即将原有数据转换或者投影到一个更小的空间。属性

30、子集选择是检测和删除不相关的、弱相关的、冗余的属性和维度的减少维度的方法。,删减数据块是将原有数据以可选的、更小的表格替换。分参数和非参数两种技术。参数的方法是，使用一个模型来评估数据，常常只有数据参数被存储，而非实际的数据。回归和对数线性模型是两个参数技术的例子。非参数技术存放以直方图、聚类、抽样以及数据立方的形式表示的删减数据。,数据压缩中，应用转换来得到一个原有数据的删减或压缩的表达。如果原有数据能从压缩数据中被重构而没有任何信息损失，则数据删减是无损的。如果只能重构原有数据的近似集，则数据删减是有损的。有一些字符串压缩的无丢失的算法，这些通常只允许有限制的数据处理。减少维度和减少数据块

31、也能被看成是数据压缩的形式。还有许多其他数据删减的方法。花在数据删减上的时间复杂度不应当超过或等于挖掘一个删减的数据集节省的时间。,3.4.2 小波转换,离散小波转换（DWT)是一个线性信号处理技术。对一个数据向量X, 使用小波系数，转换成一个不同的数值向量X。这两个向量的长度相同。当应用这种数据删减的技术时，将每个元组看成一个n维的数据向量，X=(x1, x2, , xn)， 表示数据库的n个属性的n个测量。“如果小波转换的数据和原有数据的长度相同，这种数据删减技术如何有效呢？”,有效性在于小波转换的数据能够被截短。数据的被压缩的近似集被保留，只存放了小波系数最强的一小部分数据。例如，所有比

32、一些用户指定阀值更大的小波系数被保留。其他的系数被设置为0.得到的数据表达因此非常稀疏，操作就可以利用数据的稀疏性，在小波空间计算将非常快。这个技术还能被用于去除噪声，而不需要消除数据的主要特征，像数据清洗一样有效。给定一系列系数，原有数据的近似能应用逆DWT被重构。,DWT和离散傅里叶转换（DFT)关联性很强。DFT是一种包含正弦余弦的信号处理技术。一般情况下，DWT能得到更好的无损压缩。即如果在给定数据向量上应用DWT和DFT，DWT能得到原有数据更好的近似集。因此，得到一个相同的近似集，DWT需要更少的空间。只有一种DFT，但DWT有不同的系列。流行的小波转换包含Harr-2, Daub

33、echies-4, 以及Daubechies-6. 应用一个离散小波转换的一般步骤是使用一个层次化的金字塔算法，每次迭代将数据减半，这是非常快的计算速度。,DWT的步骤：1、输入数据向量的长度L必须是2的整数次幂。这个条件可以在必要时以0填充数据向量来满足。2、每个转换包含应用两个函数。第一个应用一些数据平滑，例如求和或者加权平均。第二个使用一个加权差，为了表达数据的具体特征。3、这两个函数被应用到向量X的每一个对（x2i , x2i+1). 这会得到两个长度为L/2的数据集。一般情况下，它们一个表达的是平滑的或者低频的输入数据的版本，另一个是高频的内容。4、这两个函数被递归的应用到前一个循环

34、得到的数据集上，直到数据集的长度变成2.5、从前一次迭代的数据集中选择值，将其指明为转换数据的小波系数。,一个矩阵被应用在输入数据上，以便于得到小波系数。矩阵依赖于给定的DWT。矩阵必须是正交的，即列是单位向量，相互正交的，因此矩阵的逆是它的转置。通过将矩阵分解为几个稀疏矩阵，得到的快速DWT算法具有O(n)的时间复杂度。小波转换能被应用于高维数据如数据立方上。方法是首先应用转换到第一个维度上，然后第二个，以此类推。计算复杂度视立方的单元数目而定。小波转换对于稀疏或偏斜的数据有很好的效果，以及次序属性的数据上。小波变换的有损压缩据说比JPEG好。它有很多实际的应用，包括指纹图像、计算机视觉的压

35、缩，时间序列数据分析以及数据清洗。,3.4.3 主成分分析,假定要删减的数据包含n个属性或维度。主成分分析（PCA) 寻找K个n维正交向量，这些向量能最好的表达数据，kn. 原有的数据因此被投影到一个更小的空间，得到删减的维度。不同于属性子集选择，PCA通过创建一个可选的更好的变量集，得到重要属性的联合。PCA常常揭示之前没有察觉的关系，因此得到通常没有的解释。,a product of a few sparse matrices,PCA的基本步骤：1、将输入数据标准化，每个属性落在相同的值区间。确保属性在更大范围的不会占有更大权重。2、计算K个正交向量，提供标准输入数据的基础。这是一些单位向

36、量。每个点在方向上与其他的垂直。这些向量被称为主要成分。输入数据是主成分的线性组合。3、主成分按重要性或者长度递减的次序存放。主成分作为数据的新的坐标轴的集合，提供重要的方差信息。即，排序的坐标轴中，第一个轴表示数据的最大方差，第二个表示次高的方差，以此类推。例如图3.5表示了两个主成分Y1和Y2。,4、因为主成分按重要性的降序排列，数据尺寸可以通过去除次要成分来减少，即具有更小方差信息的。使用最强的主成分，得到原有数据的很好的近似集的重构是可能的。PCA能被应用于次序或者非次序属性。能处理稀疏和偏斜的数据。高维数据能被减少为2个。相比于小波转换，PCA能更好的处理稀疏数据，而小波转换更适合处

37、理高维数据。,3.4.4 属性子集选择,用来做分析的数据集可能包含成百个属性，许多属性和挖掘任务并不相关或者是冗余的。例如，挖掘任务是对顾客进行分类，判断他们是否会购买一个流行的新CD，像顾客的电话号码很可能是不相关的，不像年龄和音乐类型这类属性是相关的。领域专家挑选一些有用的属性是可能的，但这是一个困难和耗时的工作，特别是在数据的行为并不已知的时候。去掉了相关的属性，或者保留了不相关的属性都是有害的。导致挖掘算法的困惑以及低质量的模式发现。并且，增加的不相关和冗余属性也会让挖掘过程变慢。,属性子集选择通过减少不相关和冗余的属性来减少数据集的大小。属性子集选择的目标是寻找一个相应的数据类别分布

38、概率尽可能接近使用所有属性的原始分布的最小属性集合。在删减的属性集上挖掘具有特别的好处：使挖掘出的模式更容易被理解。“如何寻找一个原有属性的好的子集合呢？”对于n个属性，有2n个子集合，对优化子集的穷举搜索是代价很大的，特别是在n和数据类别增加的时候。因此，剪枝式的启发式方法通常被用于属性子集选择。这些方法通常是贪心式的，策略是做一个局部最优的选择用以得到一个全局优化的解。,“最好的”（以及“最差的”）属性常常是使用统计显著性检验来决定，假定属性之间是互相独立的。许多其他的属性评估方法如决策树分类中的信息增益。基本的属性子集选择的启发式技术如下：1、逐步向前选择。该方法从一个属性的空集合开始作

39、为删减集合。然后确定一个原有属性的最好属性，加入到删减集合中。每一次迭代，都把剩余属性集中最好的属性加入到该集合。2、逐步向后删除。该方法从全体属性集开始，每一次从中去除剩余属性集合中最差的属性。3、结合向前选择和向后删除的方法。,属性子集选择的贪心式方法,4、决策树推导。决策树算法（如ID3，C4.5， 和CART)最初被用于分类。决策树推导是创建一个流程图结构，每一个内部节点（非叶子节点）表示一个属性的检验，每一个分支对应于一个检验的结果，每一个外部节点（叶子节点）表示一个类别预测。在一个节点，算法选择最好的属性去将数据分割成单个的类别。当决策树用于属性子集选择时，给定数据的树被创建。所有

40、没有出现在树中的属性被认为是不相关的。出现在树中的属性构成了删减属性子集。在某些情形下，可能需要基于一些属性创建一些新的属性。这类属性构造能帮助提高对高维数据的精确性和结构的理解。比如，基于属性height和width创建area属性。通过结合属性，属性构造能发现数据属性之间的缺失信息，有利于知识发现。,3.4.5 回归和对数线性模型：参数数据删减,线性回归中，数据被拟合成一条直线。例如，随机变量y(也称为响应变量），被建模成另一个随机变量x(称为预测变量）的线性函数，公式为： y=wx+b在数据挖掘环境中，x和y都是数值型的属性，系数w和b称为回归系数，定义了直线的斜率和y-截距。系数的求解

41、可以使用最小二乘法，最小化实际直线分割数据和估计值之间的错误。多元线性回归是线性回归的扩展，将相应变量y建模成2个或更多的预测变量的线性函数。,对数线性模型近似于离散高维概率分布。给定一系列包含n维属性的元组，将每一个元组当成n维空间中的一个点。对数线性模型基于一个更小的维度联合的子集，来估计每个点在高维空间的概率。这样就能从低维空间构建高维数据空间。因此，模型可以用于维度删减（因为低维点常常比原有数据点占有更少的空间）以及数据平滑（因为低维空间的聚合估计比高维空间的估计对抽样变化主观度更小）,回归和对数线性模型都能用在稀疏数据上，即使应用比较有限。两种方法都能处理偏斜数据，回归做的更好。对高

42、维数据，回归的计算复杂度很高，而对数线性模型对高于10维的数据有更好的可扩展性。一些软件包中有回归问题的解决方法。如SAS, SPSS, S-Plus.,3.4.6 直方图,直方图使用箱子来近似数据分布，是一种流行的数据删减的形式。直方图是将一个属性A划分成不相交的子集，称为桶或者箱子。如果每个桶只表示一个单个的属性值/频率对，则桶称为单例桶。如图3.7. 通常，桶表示给定属性的连续范围。“如何确定桶和属性值的划分呢？”有如下划分的技术：等宽度：每个桶的范围都是相同的。如图3.8.等频率：每个桶的频数相同（即装了个数几乎相同的数据样本）,单例桶举例,等宽度装箱,直方图对于稀疏和稠密数据都很高效

43、，对高度偏斜或者均匀分布的数据也是一样。单个属性的直方图可以被扩展到多个属性。多维直方图能捕获属性间的依赖关系，最多能对5维数据有效。进一步的研究高维数据的有效直方图是有必要的。,3.4.7 聚类,聚类技术将数据元组当成对象。将对象划分成分组，或簇，在同一个簇中对象是相似的，跟其他簇中的对象是不相似的。相似性一般是基于距离函数，以对象在空间上的距离有多接近来定义。聚类的质量可以用它的直径来表示，即簇中两个对象的最大距离。几何中心距离是聚类质量的一个可选的测量，定义为每个聚类对象到聚类中心的平均距离。图3.3展示了一个顾客数据的2-D散点图，点的位置是在一个城市中的顾客位置。可以看见3个数据簇。

44、,3.4.8 抽样,抽样也可以作为一种数据删减的技术，因为它允许从一个大数据集中抽取小得多的随机数据（子集）来表示。假定一个大数据集D包含N个元组，最常用的数据删减的抽样技术包括：1、无置换的简单随机抽样（SRSWOR)。方法是从N个元组中以概率1/N从D中抽样s个数据，每个元组被抽样的概率都相等。2、有置换的简单随机抽样（SRSWR)。类似于SPSWOR, 除了每次从D中抽样一个元组之后，记录它然后替换。即元组被抽样之后，再放回D中下次还可以被继续抽到。,3、聚类样本。如果D中的元组被分成M个互不相交的簇，然后就可以抽样得到s个简单随机抽样簇，sM. 例如，元组在一个数据库中通常被一次检索一

45、页，每一页可以被看做一个簇。然后使用SRSWOR到页面上，便可以得到删减数据的代表，即元组的聚类抽样。其他的一些包含丰富语义信息的聚类规则也可以使用。例如，在空间数据库中，基于不同地区在地理位置上的接近程度来图形化地定义簇。,4、分层抽样：如果D被分成互不相交的层，分层抽样可以通过对每个层进行简单随机抽样来生成。这能在数据偏斜的时候，选出具有代表性的样本。例如，从顾客数据中进行分层抽样。将每个顾客按年龄分组，然后对分组抽样。在这种方式下，有最小个数的顾客年龄层也被保证会被抽取。,使用抽样的方法进行数据删减的优点在于，得到一个样本的代价和样本的大小成比例，即s与N的比例。因此，抽样复杂度是亚线性

46、比于数据尺寸。其他的数据删减技术的复杂度至少是O(N)。给定一个固定的样本大小，抽样复杂度随着数据维度的个数增加而增加。如果用直方图技术，复杂度则是n的指数级别。抽样是最常用的用来估计一个集合查询的答案的方法。,3.4.9 数据立方聚合,假设你在为你的分析收集数据。这些数据包括AllElectronics公司每个季度的销售，从2008年至2010年。你感兴趣的是每年的销售额，而不是每个季度的总体销售额。因此，数据需要被聚合，得到每年的销售总额而非季度销售额。图3.10是聚合的情况。得到的数据集尺寸更小，对分析任务来说没有必要的信息损失。,举例,数据立方存储的是高维聚合信息。如图3.11是一个销

47、售数据的高维分析的数据立方，包含AllElectronics公司所有分部的每年的每种商品类型的销售额。每个单元是一个聚合的数据值，对应于高维空间中的数据点。每个属性有一个概念层级，允许对数据的多层抽象级别的分析。比如，对于子公司的层级允许将子公司基于位置分组为不同的地区。数据立方提供对预先计算，数据摘要的快速访问，因此有利用在线分析处理以及数据挖掘。,3.5 数据转换和离散化,3.5.1 数据转换策略概览数据转换把数据转换或合并成适合数据挖掘的形式。数据转换的策略包括：1、平滑。用于去除数据中的噪声。技术包括装箱，回归和聚类。2、属性构造（或特征构造）。从给定属性中构造或增加新属性以便于挖掘过

48、程。3、聚合。在数据上应用聚合或者概括操作。例如，聚合每日销售数据以计算每月和每年的总体数据。通常这个步骤用在构造用于多层抽象级别数据分析的数据立方。,4、规范化。属性被按比例缩放到一个更小的范围，如-1.0 到 1.0， 或 0.0到1.0之间。5、离散化。数值属性的原始值被区间标签或概念标签置换。标签能被递归的组织成高层概念。形成一个数值属性的概念层级。图3.12是一个价格属性的概念层级的例子。超过一个的概念层级可以被用来满足不同用户的需求。6、名词数据的概念层级生成。例如steet属性可以扩展成高层概念，如city和country. 许多名词属性的层次是隐藏在数据库模式中的，可以在模式定

49、义级别自动定义。,离散化,离散化技术可以基于离散化方法的不同来分类，例如是使用类别信息还是处理方向（自底向上和自顶向下）。如果离散化过程使用类别信息，称为有监督的离散化；否则是无监督的。如果过程先寻找一个活若干点来分割整个属性范围，然后对每个区间递归重复这个步骤，则称为自顶向下的离散化或分割。自底向上的离散化或合并先把所有的连续值作为潜在的分割点，通过合并相邻的值移除某些点来形成区间，然后再递归的应用这个过程到每一个区间。,数据离散化和概念层级生成也是数据删减的形式。原始数据被一个数目更小的区间或者概念标签置换。这简化了原有数据，使挖掘更高效。挖掘出的模式通常更易于被理解。概念层级在对多层抽象

50、级别挖掘上也十分有效。,3.5.2 数据标准化,使用的度量单位会影响数据分析。例如，将身高的度量单位从米变成英寸，或体重从公斤变为磅，会导致非常不同的结果。通常，用更小的单位表达的属性会有一个更大的属性取值范围，倾向于给这类属性更大的效应或“权重”。为了避免对度量单位的依赖，数据需要被标准化。这会将数据按比例缩放在一个更小或更常见的区间，如-1,1或0,1。,标准化数据会给所有属性相同权重。在分类算法包括神经网络或最近令分类以及聚类中，标准化特别有效。如果在神经网络反向传播算法中，对每个训练元组的每个属性的输入值进行标准化，则会加速学习的速度。对于基于距离的方法，标准化可以避免属性在初始时具有