数据挖掘数据清洗.doc

数据预处理1 数据清理数据清洗是清除错误和不一致数据的过程，当然，数据清洗不是简单的用更新数据记录，在数据挖掘过程中，数据清洗是第一步骤，即对数据进行预处理的过程。数据清洗的任务是过滤或者修改那些不符合要求的数据。不符合要求的数据主要有不完整的数据、错误的数据和重复的数据3大类。各种不同的挖掘系统都是针对特定的应用领域进行数据清洗的。包括：1) 检测并消除数据异常2) 检测并消除近似重复记录3) 数据的集成4) 特定领域的数据清洗项目中的数据来源于数据仓库，其中数据是不完整的、有噪声和不一致的。数据清理过程试图填充缺失的值，光滑噪声并识别离群点，并纠正数据中的不一致。数据清洗的目的是为挖掘提供准确而有效的数据，提高挖掘效率。下面介绍数据清理的过程，该过程依照云平台的处理流程。2 缺失值处理对于数据集中的数据，存在有这样两种情况：1) 数据中有大量缺失值的属性，我们通常采取的措施是直接删除，但是在有些系统进行ETL处理时，不能直接处理大量的缺失值。2) 对于比较重要的属性，也会存在少量缺失值，需要将数据补充完整后进行一系列的数据挖掘。针对这两种不完整的数据特征，在数据清洗时采取了以下两种方式对数据填补：1) 将缺失的属性值用同一个常数替换，如“Unknown”。这种方式用于处理上述的第一种数据特征的数据，先用一个替换值将空值进行约束替换。处理后的数据对后期挖掘工作没有价值会选择删除。2) 利用该属性的最可能的值填充缺失值。对于第二种数据特征的数据，事先对每个属性进行值统计，统计其值的分布状态和频率，对该属性的所有遗漏的值均利用出现频率最高的那个值来填补。对缺失数据进行填补后，填入的值可能不正确，数据可能会存在偏置，并不是十分可靠的。然而，该方法使用了该属性已有数据的大部分信息来预测缺失值。在估计缺失值时，通过考虑该属性的值的整体分布与频率，保持该属性的整体分布状态。3 数据选择在对数据进行第一步缺失值清理后，会考虑删除掉冗余属性、或者与挖掘关系不大的属性，这称为人工选择。属性的人工选择和数据消减是不同的，即使两者的目的都是缩小所挖掘数据的规模，但却不会影响（或基本不影响）最终的挖掘结果。都属于属性的降维，但是现有的数据消减包括：数据聚合、消减维度、数据压缩和数据块消减。而人工属性选择是物理降维方式，通过对业务的理解和相关人员的沟通，对数据集中的数据进行初步的筛选。4 数据变换数据变换是数据清理过程的第二步，是对数据的一个标准化的处理。大部分数据需要进行数据变换。数据变换是不同来源所得到的数据可能导致不一致，所以需要进行数据变换，构成一个适合数据挖掘决的描述形式。在项目中我们进行数据转换包含的处理内容有：(1) 属性的数据类型转换。当属性之间的取值范围可能相差很大时，要进行数据的映射处理，映射关系可以去平方根、标准方差以及区域对应。当属性的取值类型较小时，分析数据的频率分布，然后进行数值转换，将其中字符型的属性转换为枚举型。(2) 属性构造。根据已有的属性集构造新的属性，以帮助数据挖掘过程。很多情况下需要从原始数据中生成一些新的变量作为预测变量。(3) 数据离散化。将连续取值的属性离散化成若干区间，来帮助消减一个连续属性的取值个数。例如年龄字段取值大于0，为了分析的方便，根据经验，可以将用户的年龄段分成几个不同的区间：015、1624、2535、3655、大于55，分别用1，2，3，4，5来表示。(4) 数据标准化：不同来源所得到的相同字段定义可能不一样。如性别有男、女来表示，需要将定义标准化，把它们的定义和取值区间统一起来。如性别定义1（男）、2（女）、3（缺失）。数据标准化过程还用来消除变量之间不同数量级造成的数值之间的悬殊差异，消除个别数值较高的属性对聚类结果的影响。5 数据的集成数据集成是把不同来源、格式、特点性质的数据在逻辑上或物理上有机地集中，从而为数据挖掘提供完整的数据源。数据集成处理需要考虑以下几个问题：（1）来自多个数据源的数据表通过相同的主键进行自然连接，各个表中的主键要相互匹配，否则不能连接。（2）冗余问题，这是数据集成中经常发生的一个问题，所以在连接之前对各个表中字段进行人工选择，并采用自然连接的方式，防止冗余字段产生。（3）数据值的冲突检测，来自不同数据源的属性值或许不同，所以要检查数据表中连接字段的类型和是否有相同的记录等问题。6 数据消减对大规模的数据进行复杂的数据分析与数据挖掘通常需要耗费大量时间，所以在数据挖掘前要进行数据的约减，减小数据规模，而且还需要交互式的数据挖掘，根据数据挖掘前后对比对数据进行信息反馈。数据消减技术正是用于从原有庞大数据集中获得一个精简的数据集合，并使这一精简数据集保持原有数据集的完整性，这样在精简数据集上进行数据挖掘显然效率更高，并且挖掘出来的结果与使用原有数据集所获得结果基本相同。数据消减的目的就是缩小所挖掘数据的规模，但却不会影响（或基本不影响）最终的挖掘结果。现有的数据消减包括：（1）数据聚合；（2）消减维度，通过相关分析消除多余属性；（3）数据压缩；（4）数据块消减，利用聚类或参数模型替代原有数据。7 数据清洗评估 数据清洗的评估实质上是对清洗后的数据的质量进行评估， 而数据质量的评估过程是一种通过测量和改善数据综合特征来优化数据价值的过程。数据质量评价指标和方法研究的难点在于数据质量的含义、 内容、 分类、分级、 质量的评价指标等。数据质量评估至少应该包含以下两方面的基本评估指标：1) 数据对用户必须是可信的。可信性包括精确性、 完整性、 一致性、 有效性、 唯一性等指标。(1) 精确性: 描述数据是否与其对应的客观实体的特征相一致。(2) 完整性: 描述数据是否存在缺失记录或缺失字段。(3) 一致性: 描述同一实体的同一属性的值在不同的系统是否一致。(4) 有效性: 描述数据是否满足用户定义的条件或在一定的域值范围内。(5) 唯一性: 描述数据是否存在重复记录。2) 数据对用户必须是可用的。包括时间性、 稳定性等指标。(1) 时间性: 描述数据是当前数据还是历史数据。(2) 稳定性: 描述数据是否是稳定的， 是否在其有效期内。高质量的决策必然依赖于高质量的数据，因此，数据变换操作，如规范化和集成，是导向挖掘过程成功的预处理过程，是十分必要和重要的。1：C4.5 C4.5就是一个决策树算法，它是决策树(决策树也就是做决策的节点间的组织方式像一棵树，其实是一个倒树)核心算法ID3的改进算法，所以基本上了解了一半决策树构造方法就能构造它。决策树构造方法其实就是每次选择一个好的特征以及分裂点作为当前节点的分类条件。C4.5比ID3改进的地方时： ID3选择属性用的是子树的信息增益(这里可以用很多方法来定义信息，ID3使用的是熵(entropy)(熵是一种不纯度度量准则),也就是熵的变化值.而C4.5用的是信息增益率。也就是多了个率嘛。一般来说率就是用来取平衡用的，就像方差起的作用差不多，比如有两个跑步的人，一个起点是10m/s的人、其1s后为20m/s；另一个人起速是1m/s、其1s后为2m/s。如果紧紧算差值那么两个差距就很大了，如果使用速度增加率(加速度)来衡量，2个人就是一样了。在这里，其克服了用信息增益选择属性时偏向选择取值多的属性的不足。在树构造过程中进行剪枝，我在构造决策树的时候好讨厌那些挂着几个元素的节点。对于这种节点，干脆不考虑最好，不然很容易导致overfitting。对非离散数据都能处理，这个其实就是一个个式，看对于连续型的值在哪里分裂好。也就是把连续性的数据转化为离散的值进行处理。能够对不完整数据进行处理，这个重要也重要，其实也没那么重要，缺失数据采用一些方法补上去就是了。 2：CART CART也是一种决策树算法！相对于上着有条件实现一个节点下面有多个子树的多元分类，CART只是分类两个子树，这样实现起来稍稍简便些。所以说CART算法生成的决策树是结构简洁的二叉树。 3：KNN(K Nearest Neighbours) 这个很简单，就是看你周围的K个人(样本)那个类别的人占的多，那个多那我也是那个多的。实现起来就是对每个训练样本都计算与其相似度，选择相似度Top-K个训练样本出来，看这K个样本中那个类别的多些，谁多跟谁。 4：Naïve Bayes(朴素贝叶斯NB) NB认为各个特征是独立的，谁也不关谁的事。所以一个样本(特征值的集合，比如”数据结构”出现2词，“文件”出现1词)，可以通过对其所有出现特征在给定类别的概率相乘。比如“数据结构”出现在类1的概率为0.5，“文件”出现在类1的概率为0.3，则可认为其属于类1的概率为0.5*0.5*0.3。 5：Support Vector Machine(支持向量机SVM) SVM就是想找一个分类得最”好”的分类线/分类面(最近的一些两类样本到这个”线”的距离最远)。这个没具体实现过，上次听课，那位老师自称自己实现了SVM，敬佩其钻研精神。常用的工具包是LibSVM,SVMLight,MySVM. 6：EM(期望最大化) 这个我认为就是假设数据时由几个高斯分布组成的，所以最后就是要求几个高斯分布的参数。通过先假设几个值，然后通过反复迭代，以期望得到最好的拟合。 7：Apriori 这个是做关联规则用的。不知道为什么，一提高关联规则我就想到购物篮数据。这个没实现过，不过也还要理解，它就是通过支持度和置信度两个量来工作，不过对于Apriori，它通过频繁项集的一些规律(频繁项集的子集必定是频繁项集等等啦)来减少计算复杂度。 8：FP-Tree(Mining frequent patterns without candidate generation) 这个也不太清楚。FP-growth算法(Frequent Pattern-growth)使用了一种紧缩的数据结构来存储查找频繁项集所需要的全部信息。采用算法：将提供频繁项集的数据库压缩到一棵FP-tree来保留项集关联信息，然后将压缩后的数据库分成一组条件数据库（一种特殊类型的投影数据库），每个条件数据库关联一个频繁项集。 9：PageRank 大名鼎鼎的PageRank大家应该都知道(Google靠此专利发家，其实也不能说发家啦!)。对于这个算法我的理解就是：如果我指向你(网页间的连接)则表示我承认你，则在计算你的重要性的时候可以加上我的一部分重要性(到底多少，要看我自己有多少和我共承认多少个人)。通过反复这样来，可以求的一个稳定的衡量各个人(网页)重要性的值。不过这里必须要做些限制(一个人的开始默认重要性都是1)，不然那些值会越来越大越来越大。 10：HITS HITS也是一个连接分析算法，它是由IBM首先提出的。在HITS，每个节点(网页)都有一个重要度和权威度(Hubs and authorities,我也忘了具体的翻译是什么了)。通过反复通过权威度来求重要度，通过重要度来求权威度得到最后的权威度和重要度。 11：K-Means K-Means是一种最经典也是使用最广泛的聚类方法，时至今日任然有很多基于其的改进模型提出。K-Means的思想很简单，对于一个聚类任务(你需要指明聚成几个类，当然按照自然想法来说不应该需要指明类数，这个问题也是当前聚类任务的一个值得研究的课题)，首先随机选择K个簇中心，然后反复计算下面的过程直到所有簇中心不改变(簇集合不改变)为止：步骤1：对于每个对象，计算其与每个簇中心的相似度，把其归入与其最相似的那个簇中。 步骤2：更新簇中心，新的簇中心通过计算所有属于该簇的对象的平均值得到。 k-means 算法的工作过程说明如下：首先从n个数据对象任意选择k 个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数. k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。 12：BIRCH BIRCH也是一种聚类算法，其全称是Balanced Iterative Reducing and Clustering using Hierarchies。BIRCH也是只是看了理论没具体实现过。是一个综合的层次聚类特征(Clustering Feature, CF)和聚类特征树(CF Tree)两个概念，用于概括聚类描述。聚类特征树概括了聚类的有用信息，并且占用空间较元数据集合小得多，可以存放在内存中，从而可以提高算法在大型数据集合上的聚类速度及可伸缩性。 BIRCH算法包括以下两个阶段： 1）扫描数据库，建立动态的一棵存放在内存的CF Tree。如果内存不够，则增大阈值，在原树基础上构造一棵较小的树。 2）对叶节点进一步利用一个全局性的聚类算法，改进聚类质量。 由于CF Tree的叶节点代表的聚类可能不是自然的聚类结果，原因是给定的阈值限制了簇的大小，并且数据的输入顺序也会影响到聚类结果。因此需要对叶节点进一步利用一个全局性的聚类算法，改进聚类质量。 13：AdaBoost AdaBoost做分类的一般知道，它是一种boosting方法。这个不能说是一种算法，应该是一种方法，因为它可以建立在任何一种分类算法上，可以是决策树，NB，SVM等。 Adaboost是一种迭代算法，其核心思想是针对同一个训练集训练不同的分类器(弱分类器)，然后把这些弱分类器集合起来，构成一个更强的最终分类器(强分类器)。其算法本身是通过改变数据分布来实现的，它根据每次训练集之中每个样本的分类是否正确，以及上次的总体分类的准确率，来确定每个样本的权值。将修改过权值的新数据集送给下层分类器进行训练，最后将每次训练得到的分类器最后融合起来，作为最后的决策分类器。使用adaboost分类器可以排除一些不必要的训练数据，并将关键放在关键的训练数据上面。 14：GSP GSP，全称为Generalized Sequential Pattern(广义序贯模式)，是一种序列挖掘算法。对于序列挖掘没有仔细看过，应该是基于关联规则的吧！网上是这样说的： GSP类似于Apriori算法，采用冗余候选模式的剪除策略和特殊的数据结构-哈希树来实现候选模式的快速访存。 GSP算法描述: 1）扫描序列数据库，得到长度为1的序列模式L1，作为初始的种子集。 2）根据长度为i 的种子集Li ，通过连接操作和修剪操作生成长度为i+1的候选序列模式Ci+1；然后扫描序列数据库，计算每个候选序列模式的支持度，产生长度为i+1的序列模式Li+1，并将Li+1作为新的种子集。 3）重复第二步，直到没有新的序列模式或新的候选序列模式产生为止。 产生候选序列模式主要分两步： 连接阶段：如果去掉序列模式s1的第一个项目与去掉序列模式s2的最后一个项目所得到的序列相同，则可以将s1与s2进行连接，即将s2的最后一个项目添加到s1中。 修切阶段：若某候选序列模式的某个子序列不是序列模式，则此候选序列模式不可能是序列模式，将它从候选序列模式中删除。 候选序列模式的支持度计算：对于给定的候选序列模式集合C，扫描序列数据库，对于其中的每一条序列s,找出集合C中被s所包含的所有候选序列模式，并增加其支持度计数。 15：PrefixSpan 又是一个类似Apriori的序列挖掘。 其中经典十大算法为：C4.5，K-Means，SVM，Apriori，EM，PageRank，AdaBoost，KNN，NB和CART。7