2020-12-22_v-optimal

大数据处理

数据采集

数据采集(DAQ)， 又称数据获取，是指从传感器和其它待测设备等模拟和数字被测单元中自动采集信息的过程。数据分类新一代数据体系中，将传统数据体系中没有考虑过的新数据源进行归纳与分类，可将其分为线上行为数据与内容数据两大类。

线上行为数据：页面数据、交互数据、表单数据、会话数据等。
内容数据：应用日志、电子文档、机器数据、语音数据、社交媒体数据等。
大数据的主要来源：1）商业数据 2）互联网数据 3）传感器数据

传统的数据采集来源单一，且存储、管理和分析数据量也相对较小，大多采用关系型数据库和并行数据仓库即可处理。对依靠并行计算提升数据处理速度方面而言，传统的并行数据库技术追求高度一致性和容错性，根据CAP理论，难以保证其可用性和扩展性。

而大数据的数据采集，来源广泛，信息量巨大，需要采用分布式数据库对数据进行处理。数据类型也相当丰富，既包括结构化数据，也包括半结构化和非结构化数据。

数据清洗

数据清洗方法

1、缺失值处理

在数据清洗中对缺失值的处理有删除、均值填补、热卡填补、回归填补、多重填补、K-最近邻法、有序最近邻法、贝叶斯等，以下介绍三种使用频率较高的缺失值补全方法：

删除：缺失部分在整体数据样本中占比较低时，直接删除即可；

均值填补：依据数据值属性相关度，对影响最大的那一组数据拆分成几个部分，计算出每部分的均值，加入到缺失数据中即可；

热卡填补法：若缺失值包含变量，那么在数据库中寻找与它相似度最高的一组数据进行填补；

2、异常值处理
在数据清洗中对异常值的处理有3∂原则、箱型图分析、模型检测、距离、密度、聚类、统计分析等，以下照例介绍三种使用频率较高的异常值处理方法：

统计分析：拿到数据之后，对其进行简单的描述性统计。通过选取最大最小阈值来判断是否符合常识；

模型检测：根据正常状态，建立数据模型。将数据表现与模型不拟合的数据定义为异常值；

3∂原则：如果数据服从正态分布，在3∂原则下，异常值为一组测定值中与平均值的偏差超过3倍标准差的值。如果数据服从正态分布，距离平均值3∂之外的值出现的概率为P(|x-u| > 3∂) <= 0.003，属于极个别的小概率事件。如果数据不服从正态分布，也可以用远离平均值的多少倍标准差来描述；

3、噪音处理

在数据清洗中，对噪音处理的方法为分箱法和回归法；以下对去处理方法做简要介绍：

分箱法：通过考察对比数据周边值来光滑有序数据值，这些数值被分布到一些箱中，再由分箱考察对比周边近邻值。以箱为单位对素质进行平均值替换或者中位数替换，箱中最大值最小值被视为边界，箱中的每个值被最近的边界值替换。

回归法：线性回归将拟合两个属性的最佳直线，使得一个属性能够预测另一个。多线性回归是线性回归的扩展，涉及将多个属性数据拟合到一个多维面；
数据清洗基本流程

1、数据预处理

将数据导入到处理工具当中，通过工具自动“查看”采集到的元数据信息，然后人工查看数据，归纳总结工具处理可能存在的遗漏或偏差，为下一步数据处理做准备；

2、数据分析处理

缺失值清洗：通过去重除噪、缺失值处理、通过其他渠道重新获取丢失的重要数据进行数据填充及补全；

（2）格式内容清洗：对格式的清洗，小到日期/数值/半全角显示，大到数值内容中是否存在不该有的字符或是与内容不符的字符，都必须通过数据清洗处理掉；

（3）逻辑错误清洗:重复性数据、与常识不符的异常数据、属性依赖冲突的数据以及非需求数据进行清除；

3、校验

最后对数据清洗的结论进行效验，如格式效验和数据关联性效验；
数据清洗的应用场景

随着企业从传统的人力巡检到半自动的数据化转型，越来越多的商业领域将涉及数据清洗的业务。例如制造业、农业在将设备接入物联网云平台之后，每天都会产生大量数据，通过数据清洗提高生产效率，降低运维成本。

3.3 数据变换

数据转换就是将数据进行转换或归并，从而构成一个适合数据处理的描述形式。数据转换包含以下处理内容。
1）平滑处理
帮助除去数据中的噪声，主要技术方法有 Bin 方法、聚类方法和回归方法。
2）合计处理
对数据进行总结或合计操作。例如，每天的数据经过合计操作可以获得每月或每年的总额。这一操作常用于构造数据立方或对数据进行多粒度的分析。
3）数据泛化处理
用更抽象（更高层次）的概念来取代低层次或数据层的数据对象。

例如，街道属性可以泛化到更高层次的概念，如城市、国家，数值型的属性，如年龄属性，可以映射到更高层次的概念，如年轻、中年和老年。
4）规格化处理
将有关属性数据按比例投射到特定的小范围之中。例如，将工资收入属性值映射到 0 到 1 范围内。
5）属性构造处理
根据已有属性集构造新的属性，以帮助数据处理过程。

下面将着重介绍规格化处理和属性构造处理。

规格化处理就是将一个属性取值范围投射到一个特定范围之内，以消除数值型属性因大小不一而造成挖掘结果的偏差，常常用于神经网络、基于距离计算的最近邻分类和聚类挖掘的数据预处理。

对于神经网络，采用规格化后的数据不仅有助于确保学习结果的正确性，而且也会帮助提高学习的效率。对于基于距离计算的挖掘，规格化方法可以帮助消除因属性取值范围不同而影响挖掘结果的公正性。

下面介绍常用的3种规格化方法。

1. 最大最小规格化方法
   该方法对被初始数据进行一种线性转换。

例如，假设属性的最大值和最小值分别是 98 000 元和 12 000 元，利用最大最小规格化方法将“顾客收入”属性的值映射到 0~1 的范围内，则“顾客收入”属性的值为 73 600 元时，对应的转换结果如下。

(73 600-12 000)/(98 000-12 000)(1.0-0.0) + 0 = 0.716
计算公式的含义为“（待转换属性值-属性最小值）/（属性最大值-属性最小值）（映射区间最大值-映射区间最小值）+映射区间最小值”。
2. 零均值规格化方法
该方法是指根据一个属性的均值和方差来对该属性的值进行规格化。

假定属性“顾客收入”的均值和方差分别为 54 000 元和 16 000 元，则“顾客收入”属性的值为 73 600 元时，对应的转换结果如下。

(73 600-54 000)/16000 = 1.225
计算公式的含义为“（待转换属性值-属性平均值）/属性方差”。
3. 十基数变换规格化方法
该方法通过移动属性值的小数位置来达到规格化的目的。所移动的小数位数取决于属性绝对值的最大值。假设属性的取值范围是 -986~917，则该属性绝对值的最大值为 986。属性的值为 435 时，对应的转换结果如下。

435/10^3 = 0.435
计算公式的含义为“待转换属性值/10”，其中，j 为能够使该属性绝对值的最大值（986）小于 1 的最小值。

属性构造方法可以利用已有属性集构造出新的属性，并将其加入到现有属性集合中以挖掘更深层次的模式知识，提高挖掘结果准确性。

例如，根据宽、高属性，可以构造一个新属性（面积）。构造合适的属性能够减少学习构造决策树时出现的碎块情况。此外，属性结合可以帮助发现所遗漏的属性间的相互联系，而这在数据挖掘过程中是十分重要的。

数据集成

数据处理常常涉及数据集成操作，即将来自多个数据源的数据，如数据库、数据立方、普通文件等，结合在一起并形成一个统一数据集合，以便为数据处理工作的顺利完成提供完整的数据基础。

在数据集成过程中，需要考虑解决以下几个问题。

1. 模式集成问题

模式集成问题就是如何使来自多个数据源的现实世界的实体相互匹配，这其中就涉及实体识别问题。

例如，如何确定一个数据库中的“custom_id”与另一个数据库中的“custome_number”是否表示同一实体。

数据库与数据仓库通常包含元数据，这些元数据可以帮助避免在模式集成时发生错误。

2. 冗余问题

冗余问题是数据集成中经常发生的另一个问题。若一个属性可以从其他属性中推演出来，那这个属性就是冗余属性。

例如，一个顾客数据表中的平均月收入属性就是冗余属性，显然它可以根据月收入属性计算出来。此外，属性命名的不一致也会导致集成后的数据集出现数据冗余问题。

利用相关分析可以帮助发现一些数据冗余情况。

例如，给定两个属性 A 和 B,则根据这两个属性的数值可分析出这两个属性间的相互关系。

如果两个属性之间的关联值 r>0,则说明两个属性之间是正关联，也就是说，若 A 增加，B 也增加。r 值越大，说明属性 A、E 的正关联关系越紧密。

如果关联值产 0,则说明属性 A、B 相互独立，两者之间没有关系。如果 r<0,则说明属性 A、B之间是负关联，也就是说，若 A 增加，B 就减少。r 的绝对值越大，说明属性 A、B 的负关联关系越紧密。

3. 数据值冲突检测与消除问题

在现实世界实体中，来自不同数据源的属性值或许不同。产生这种问题的原因可能是表示、比例尺度，或编码的差异等。

例如，重量属性在一个系统中采用公制，而在另一个系统中却采用英制；价格属性在不同地点采用不同的货币单位。这些语义的差异为数据集成带来许多问题。

数据消减

们都知道对大规模数据进行复杂的数据分析通常需要耗费大量的时间，这时就需要我们的数据消减技术了。

数据消减技术的主要目的就是从原有巨大数据集中获得一个精简的数据集，并使这一精简数据集保持原有数据集的完整性。这样在精简数据集上进行数据挖掘就会提高效率，并且能够保证挖掘出来的结果与使用原有数据集所获得的结果基本相同。

数据消减的主要策略有以下几种。
名称 说明
数据立方合计 这类合计操作主要用于构造数据立方（数据仓库操作）。
维数消减 主要用于检测和消除无关、弱相关，或冗余的属性或维（数据仓库中属性）。
数据压缩 利用编码技术压缩数据集的大小。
数据块消减 利用更简单的数据表达形式，如参数模型、非参数模型（聚类、采样、直方图等），来取代原有的数据。
离散化与概念层次生成 所谓离散化就是利用取值范围或更高层次概念来替换初始数据。利用概念层次可以帮助挖掘不同抽象层次的模式知识。
数据立方合计
图 1 展示了在 3 个维度上对某公司原始销售数据进行合计所获得的数据立方。它从时间（年代）、公司分支，以及商品类型 3 个角度（维）描述了相应（时空）的销售额（对应一个小立方块）。
数据立方合计描述
图 1 数据立方合计描述

每个属性都可对应一个概念层次树，以帮助进行多抽象层次的数据分析。例如，一个分支属性的（概念）层次树，可以提升到更高一层的区域概念，这样就可以将多个同一区域的分支合并到一起。

在最低层次所建立的数据立方称为基立方，而最高抽象层次对应的数据立方称为顶立方。

顶立方代表整个公司三年中，所有分支、所有类型商品的销售总额。显然每一层次的数据立方都是对低一层数据的进一步抽象，因此它也是一种有效的数据消减。
维数消减
数据集可能包含成百上千的属性，而这些属性中的许多属性是与挖掘任务无关的或冗余的。

例如，挖掘顾客是否会在商场购买电视机的分类规则时，顾客的电话号码很可能与挖掘任务无关。但如果利用人类专家来帮助挑选有用的属性，则困难又费时费力，特别是当数据内涵并不十分清楚的时候。无论是漏掉相关属性，还是选择了无关属性参加数据挖掘工作，都将严重影响数据挖掘最终结果的正确性和有效性。此外，多余或无关的属性也将影响数据挖掘的挖掘效率。

维数消减就是通过消除多余和无关的属性而有效消减数据集的规模的。

这里通常采用属性子集选择方法。属性子集选择方法的目标就是寻找出最小的属性子集并确保新数据子集的概率分布尽可能接近原来数据集的概率分布。利用筛选后的属性集进行数据挖掘，由于使用了较少的属性，从而使得用户更加容易理解挖掘结果。

如果数据有 d 个属性，那么就会有 2^d 个不同子集。从初始属性集中发现较好的属性子集的过程就是一个最优穷尽搜索的过程，显然，随着属性个数的不断增加，搜索的难度也会大大增加。所以，一般需要利用启发知识来帮助有效缩小搜索空间。这类启发式搜索方法通常都是基于可能获得全局最优的局部最优来指导并帮助获得相应的属性子集的。

一般利用统计重要性的测试来帮助选择“最优”或“最差”属性。这里假设各属性之间都是相互独立的。构造属性子集的基本启发式搜索方法有以下几种。

1. 逐步添加方法
   该方法从一个空属性集（作为属性子集初始值）幵始，每次从原有属性集合中选择一个当前最优的属性添加到当前属性子集中。直到无法选择出最优属性或满足一定阈值约束为止。
2. 逐步消减方法
   该方法从一个全属性集（作为属性子集初始值）开始，每次从当前属性子集中选择一个当前最差的属性并将其从当前属性子集中消去。直到无法选择出最差属性或满足一定阈值约束为止。
3. 消减与添加结合方法
   该方法将逐步添加方法与逐步消减方法结合在一起，每次从当前属性子集中选择一个当前最差的属性并将其从当前属性子集中消去，以及从原有属性集合中选择一个当前最优的属性添加到当前属性子集中。直到无法选择出最优属性且无法选择出最差属性，或满足一定阈值约束为止。
4. 决策树归纳方法
   通常用于分类的决策树算法也可以用于构造属性子集。具体方法就是，利用决策树的归纳方法对初始数据进行分类归纳学习，获得一个初始决策树，没有出现在这个决策树上的属性均认为是无关属性，将这些属性从初始属性集合中删除掉，就可以获得一个较优的属性子集。
   数据压缩
   数据压缩就是利用数据编码或数据转换将原来的数据集合压缩为一个较小规模的数据集合。

若仅根据压缩后的数据集就可以恢复原来的数据集，那么就认为这一压缩是无损的，否则就称为有损的。在数据挖掘领域通常使用的两种数据压缩方法均是有损的，它们是离散小波转换（Discrete Wavelet Transforms）和主要素分析（Principal Components Analysis）。

1. 离散小波变换
   离散小波变换是一种线性信号处理技术，该方法可以将一个数据向量转换为另一个数据向量（为小波相关系数），且两个向量具有相同长度。可以舍弃后者中的一些小波相关系数。

例如，保留所有大于用户指定阈值的小波系数，而将其他小波系数置为 0，以帮助提高数据处理的运算效率。

这一方法可以在保留数据主要特征的情况下除去数据中的噪声，因此该方法可以有效地进行数据清洗。此外，在给定一组小波相关系数的情况下，利用离散小波变换的逆运算还可以近似恢复原来的数据。
2. 主要素分析
主要素分析是一种进行数据压缩常用的方法。

假设需要压缩的数据由 N 个数据行（向量）组成，共有 k 个维度（属性或特征）。该方法是从 k 个维度中寻找出 c 个共轭向量（c<<N)，从而实现对初始数据的有效数据压缩的。

主要素分析方法的主要处理步骤如下。

1）对输入数据进行规格化，以确保各属性的数据取值均落入相同的数值范围。

2）根据已规格化的数据计算 c 个共轭向量，这 c 个共轭向量就是主要素，而所输入的数据均可以表示为这 c 个共轭向量的线性组合。

3）对 c 个共轭向量按其重要性（计算所得变化量）进行递减排序。

4）根据所给定的用户阈值，消去重要性较低的共轭向量，以便最终获得消减后的数据集合，此外，利用最主要的主要素也可以更好地近似恢复原来的数据。

主要素分析方法的计算量不大且可以用于取值有序或无序的属性，同时也能处理稀疏或异常数据。该方法还可以将多于两维的数据通过处理降为两维数据。与离散小波变换方法相比，主要素分析方法能较好地处理稀疏数据，而离散小波变换则更适合对高维数据进行处理变换。
数据块消减
数据块消减方法主要包括参数与非参数两种基本方法。所谓参数方法就是利用一个模型来帮助获得原来的数据，因此只需要存储模型的参数即可（当然异常数据也需要存储）。

例如，线性回归模型就可以根据一组变量预测计算另一个变量。而非参数方法则是存储利用直方图、聚类或取样而获得的消减后数据集。下面介绍几种主要的数据块消减方法。

1. 回归与线性对数模型
   回归与线性对数模型可用于拟合所给定的数据集。线性回归方法是利用一条直线模型对数据进行拟合的，可以是基于一个自变量的，也可以是基于多个自变量的。

线性对数模型则是拟合多维离散概率分布的。如果给定 n 维（例如，用 n 个属性描述）元组的集合，则可以把每个元组看作 n 维空间的点。

对于离散属性集，可以使用线性对数模型，基于维组合的一个较小子集，来估计多维空间中每个点的概率。这使得高维数据空间可以由较低维空间构造。因此，线性对数模型也可以用于维归约和数据光滑。

回归与线性对数模型均可用于稀疏数据及异常数据的处理。但是回归模型对异常数据的处理结果要好许多。应用回归方法处理高维数据时计算复杂度较大，而线性对数模型则具有较好的可扩展性。
2. 直方图
直方图是利用 Bin 方法对数据分布情况进行近似的，它是一种常用的数据消减方法。属性 A 的直方图就是根据属性 A 的数据分布将其划分为若干不相交的子集（桶）的。这些子集沿水平轴显示，其高度（或面积）与该桶所代表的数值平均（出现）频率成正比。若每个桶仅代表一对属性值/频率，则这个桶就称为单桶。通常一个桶代表某个属性的一段连续值。

以下是一个商场所销售商品的价格清单（按递增顺序排列，括号中的数表示前面数字出现的次数）。

1（2）、5（5）、8（2）、10（4）、12、14（3）、15（5）、18（8）、20（7）、21（4）、25（5）、28、30（3）
上述数据所形成的属性值/频率对的直方图如图 2 所示。构造直方图所涉及的数据集划分方法有以下几种。
1）等宽方法
在一个等宽的直方图中，每个桶的宽度（范围）是相同的（如图 2 所示）。
2）等高方法
在一个等高的直方图中，每个桶中的数据个数是相同的。
3）V-Optimal 方法
若对指定桶个数的所有可能直方图进行考虑，该方法所获得的直方图是这些直方图中变化最小的，即具有最小方差的直方图。直方图方差是指每个桶所代表数值的加权之和，其权值为相应桶中数值的个数。
4）MaxDiff 方法
该方法以相邻数值（对）之差为基础，一个桶的边界则是由包含有 β-1 个最大差距的数值对所确定的，其中，β 为用户指定的阈值。
等宽的直方图
图 2 等宽的直方图

V-Optimal 方法和 MaxDiff 方法比其他方法更加准确和实用。直方图在拟合稀疏和异常数据时具有较高的效能，此外，直方图方法也可以用于处理多维（属性）数据，多维直方图能够描述出属性间的相互关系。
3. 聚类
聚类技术将数据行视为对象。聚类分析所获得的组或类具有以下性质。同一组或类中的对象彼此相似，而不同组或类中的对象彼此不相似。

相似性通常利用多维空间中的距离来表示。一个组或类的“质量”可以用其所含对象间的最大距离（称为半径）来衡量，也可以用中心距离，即组或类中各对象与中心点距离的平均值，来作为组或类的“质量”。

在数据消减中，数据的聚类表示可用于替换原来的数据。当然这一技术的有效性依赖于实际数据的内在规律。在处理带有较强噪声数据时采用数据聚类方法常常是非常有效的。
4. 采样
采样方法由于可以利用一小部分数据（子集）来代表一个大数据集，因此可以作为数据消减的技术方法之一。

假设一个大数据集为 D，其中包括 N 个数据行。几种主要的采样方法如下。

1）无替换简单随机采样方法（简称 SRSWOR 方法）

该方法从 N 个数据行中随机（每一数据行被选中的概率为 1/N）抽取出 n 个数据行，以构成由 n 个数据行组成的采样数据子集，如图 3 所示。

两种随机采样方法示意
图 3 两种随机采样方法示意

2）有替换简单随机采样方法（简称 SRSWR 方法）

该方法也是从 N 个数据行中每次随机抽取一个数据行，但该数据行被选中后仍将留在大数据集 D 中，最后获得的由 n 个数据行组成的采样数据子集中可能会出现相同的数据行，如图 3 所示。

3）聚类采样方法

该方法首先将大数据集 D 划分为 M 个不相交的类，然后再分别从这 M 个类的数据对象中进行随机抽取，这样就可以最终获得聚类采样数据子集。

4）分层采样方法

该方法首先将大数据集划分为若干不相交的层，然后再分别从这些层中随机抽取数据对象，从而获得具有代表性的采样数据子集。

例如，可以对一个顾客数据集按照年龄进行分层，然后再在每个年龄组中进行随机选择，从而确保最终获得的分层采样数据子集中的年龄分布具有代表性。