Chap3_数据预处理

数据预处理

什么是数据预处理

数据分析算法的设计与选择需要考虑被处理数据的特征
数据质量过低或数据的形态不符合算法需求时，需要进行数据预处理工作
数据预处理是指对数据进行正式处理（计算）之前，根据后续数据计算的需求对原始数据集进行审计、清洗、变换、集成、脱敏、规约和标注等一系列处理活动，提升数据质量，并使数据形态更加符合某一算法要求，进而达到提升数据计算的效果和降低其复杂度的目的。

数据质量

数据鉴别技术

数据鉴别的目的

消息本身的鉴别： 验证消息的完整性，判断内容是否被篡改、重放或延迟等
主体的鉴别：验证发送者是真实的，而不是冒充的

数据鉴别的常用方法

消息鉴别码
Hash函数
数字签名

消息鉴别码 (Message Authentication Code，MAC)是一个固定长的鉴别码，其计算方式如下：MAC=C（K，M）
M 为输入消息（变长）；
K 为双方共享的密钥；
C为MAC函数；
C（K,M）为MAC函数的返回值（固定长度）
注意：消息鉴别码的生成与数据加密是两个不同的概念

消息鉴别码的生成与数据加密是两个不同的概念。在实际工作中，需要选择二者的执行顺序。从理论上看，可以选择3种方式：
MAC码直接附加在消息之后；
MAC直接附加在消息之后，并对整体进行加密；
先对消息加密，再对密文生成鉴别码。

消息鉴别码的实现方法有很多种，例如：
基于对称分组密码的MAC（CBC，Cipher Block Chaining-MAC）（Next slide）
基于CFB（Cipher Feed Back）的MAC码等

Hash函数
基于MAC的消息鉴别方法
需要加密处理，计算速度较慢，时间消耗长，硬件开销大
基于Hash函数的消息鉴别
不需要加密处理，计算速度更快
Hash函数是指具备如下特征的函数
输入为任意长度的消息M；
输出为一个固定长度的散列值，称为消息摘要Message Digest）；
消息中的任何一位或多位的变化都将导致该散列值的变化
一个好的Hash函数应具备如下个特征：
容易计算，即给定 M ，很容易计算 h ；
单向性，即如果已知h，根据 H(M) = h 计算 M 很难 ；
抗碰撞性，即给定 M1，要找到另一个消息 M2 并满足 H(M1) = H(M2) 很难
Hash函数在streaming算法中应用广泛

数字签名

签名与加密、鉴别的区别
签名的基本要求
签名者事后无法否认自己的签名、接收者能验证签名，而任何其他人都不能伪造签名；
在有争议时，可由第三方进行验证；对签名的作者、日期和时间、签名时刻消息的内容提供验证。
数字签名：用私钥加密，公钥可以解密

数据审计:

发现“问题”数据
数据审计是指按照数据质量的一般规律与评价方法，对数据内容及其元数据进行审计，发现其中存在的“问题”，例如：
缺失值（缺少数据）：如学生数据缺少某条记录
噪声值（异常数据）：如出生年份的值为120
不一致值（相互矛盾的数据）：此问题一般在集成多个原始数据时出现。如同一学生的出生年月不一致。
不完整值（被篡改或无法溯源的数据）：当数据本身带有校验信息（如hash值）则可判断校验其完整.

数据清洗

是指在数据审计的基础上，将“脏数据”（数据审计中发现的问题数据）清洗成“干净数据”的过程

缺失数据处理

①忽略元组：当缺少类标号时通常这样做。除非元组有多个属性缺少值，否则该方法不是很有效。
②人工填写缺失值：一般情况下，该方法很费时。
③使用一个全局常量填充缺失值：将缺失值用同一个常数（如Unknown或﹣∞）替换。如果缺失值都用Unknown替换，则挖掘程序可能误认为它们形成了一个有趣的概念，因为它们都具有相同的值“Unknown”。因此此方法虽然简单但不可靠。
④使用属性的均值填充缺失值：例如，假定顾客的平均收入为56000美元，则使用该值替换income中的缺失值。
⑤使用与给定元组属同一类的所有样本的属性均值，例如，将顾客按credit_risk分类，则用具有相同信用度给定元组的顾客的平均收入替换income中的缺失值。
⑥使用最可能的值填充缺失值：可以用回归、使用贝叶斯形式化的基于推理的工具或决策树归纳确定。例如，利用数据集中其他顾客的属性，可以构造一棵决策树来预测income的缺失值。

冗余数据处理

冗余数据处理：过滤方法

1）重复过滤：在识别数据中的重复数据的基础上，从每个重复数据项中选择一项记录为代表保留。
两个关键活动：
识别重复数据
判断方法：根据来源数据的具体结构本身来确定。
如，关系表中，考虑属性值的相似性来确定；图论中，根据计算记录之间的距离的方法确定。
注意：判断重复记录，并不要求记录的属性值是完全相同的。
过滤重复数据， 两种方法
直接过滤：直接过滤，选择代表性的数据留下。
间接过滤：对重复数据进行一定校验、整合、合并操作之后，形成一条新纪录. (因为重复记录并一定是指相同的记录)
2）条件过滤：指根据某种条件进行过滤，如过滤掉年龄小于15岁的学生记录。
严格来讲，重复过滤也是条件过滤的一种特殊表现形式。

噪声数据处理

噪声：指测量变量中的随机错误或偏差
噪声数据的存在形式
错误数据
虚假数据
异常数据 （系统出问题导致的异常数据）
指对数据分析结果有重要影响的离群数据或孤立数据
噪声数据的处理方法
分箱（Binning）：把数据集放入多个箱内，用箱子的均值替换该箱内部的每个数据成员，从而达到降噪目的。
聚类（Clustering）：通过聚类检测离群点，将类似的值组织成群或簇。直观地，落在簇集合之外的值视为离群点。
回归（Regression）：用一个函数（如回归函数）拟合数据来光滑数据。


聚类定义：对给定的数据进行层次的分解：
分类：
凝聚的（agglomerative）方法（自底向上）
思想：一开始将每个对象作为单独的一组，然后根据同类相近，异类相异的原则，合并对象，直到所有的组合并成一个，或达到一个终止条件为止。
分裂的方法（divisive）（自顶向下）思想：一开始将所有的对象置于一类，在迭代的每一步中，一个类不断地分为更小的类，直到每个对象在单独的一个类中，或达到一个终止条件。
特点：
类的个数不需事先定好
需确定距离矩阵
运算量要大，适用于处理小样本数据

划分方法（Partitioning method）

较流行的方法有:
动态聚类法（也称逐步聚类法），如k－均值算法、k－中心点算法
思想：
随机选择k个对象，每个对象初始地代表一个类的平均值或中心，对剩余每个对象，根据其到类中心的距离，被划分到最近的类；然后重新计算每个类的平均值。不断重复这个过程，直到所有的样本都不能再分配为止。
缺陷：
不同的初始值，结果可能不同
有些k均值算法的结果与数据输入顺序有关，如在线k均值算法
用爬山式技术（hill-climbing）来寻找最优解，容易陷入局部极小值

噪声数据处理：回归方法

用一个函数（如回归函数）拟合数据来光滑数据

通过回归分析方法对数据进行平滑处理,识别并去除噪声

关于错误数据和虚假数据
错误数据和虚假数据也会影响数据分析与洞见的信度
错误数据和虚假数据的识别与处理更加复杂，需要与领域知识与经验相结合。
需要数据科学家的实战经验。

数据集成

对不同的数据源进行集成处理，并在集成后的数据集上进 行数据处理。

数据集成的基本类型：

内容集成
当目标数据集的结构与来源数据集的结构相同时，则进行合并处理。
结构集成
与内容集合不同，结构集成目标数据集的结果与来源数据集不同。需要对结构进行“自然连接”
数据分析任务多半涉及数据集成。
数据集成是指将多个数据源中的数据合并并存放到一个一致的数据存储（如数据仓库）中。
这些数据源可能包括多个数据库、数据立方体或一般文件。
（数据源是多样的，复杂的）

数据集成的3个基本问题

模式集成: 多个数据源中的实体如何匹配，即实体识别问题。如，数据分析者或计算机如何才能确信一个数据库中的customer_id和另一个数据库中的cust_number指的是相同的属性。
数据冗余：一个属性可能是冗余的，如果它能由另一个或另一组属性导出
冲突检测与消除: 如多个数据源中的单位不一致（如，美元与人民币）
数据冗余：若一个属性可以从其他属性中推演出来，那这个属性就是冗余属性。如顾客数据表中的“平均月收入”就是冗余属性，因为这个可以根据数据算出来。

属性A和属性B之间的相关度可根据以下计算公式分析获得：

其中，A ̅和B ̅分别代表属性A，B的平均值， 和 分别表示属性A，B的标准方差




若有 rA,B>0，则属性A，B之间是正关联，也就是说若A增加，B也增加； 值越大，说明属性A，B正关联关系越密；
若有 rA,B=0，就有属性A，B相互独立，两者之间没有关系。最后若有 <0,则属性A，B之间是负关联，也就是说若A增加，B就减少；
rA,B<0绝对值越大，说明属性A，B负关联关系越密。

数据脱敏

数据脱敏操作不能停留在简单的将敏感信息屏蔽掉或匿名处理。要满足以下三个原则：
单向性：从原始数据可以容易得到脱敏数据，但无法从脱敏数据推导出原始数据。
无残留: 保证用户无法通过其他途径还原敏感信息。
易于实现:数据脱敏涉及的数据量大,需要简单的计算方法。如不能采用加密算法来进行脱敏，则计算太复杂。
数据脱敏可以采用替换和过滤方法。
替换可以采用hash函数方法进行数据的单项映射

数据规约

在不影响数据的完整性和数据分析结果的正确性的前提下，通过减少数据规模的方法达到提升分析的效果和目的。

属性子集选择的方法
①逐步向前选择：该过程由空属性集作为归约集开始，确定原属性集中最好的属性，并将它添加到归约集中。在其后的每一次迭代步，将剩下的原属性集中最好的属性添加到该集合中。(Greedy 贪婪算法思路)
②逐步向后删除：该过程由整个属性集开始。在每一步，删除尚在属性集中最差的属性。
③向前选择和向后删除的结合。
④决策树归纳：决策树算法，如ID3、C4.5和CART最初是用于分类的。决策树归纳构造一个类似于流程图的结构，其中
每个内部（非树叶）节点表示一个属性的测试，
每个分枝对应于测试的一个输出；
每个外部（树叶）节点表示一个类预测。在每个节点，算法选择最好的属性，将数据划分成类

数据标注

按标注活动的自动化程度，数据标注可以分为手工标注（ImageNet）、自动化标注和 半自动化(服务器端算法+客户端人工， 如高德地图事故标注)标注。

从标注的实现层次看，数据标注可以分为：
语法标注：采用语法层次上的数据计算技术，对文字、图片、语音、视频等目标数据给出语法层次的标注信息。
如，标出图像数据的颜色、纹理等。
语义标注：从语义层次上标注。
如，视频的tag。
数据标注的例子
imageNet http://www.image-net.org/
ImageNet 是一个计算机视觉系统识别项目， 是目前世界上图像识别最大的数据库。是美国斯坦福的计算机科学家，模拟人类的识别系统建立的。
该图片数据库是通过 Amazon Mturk 的众包平台完成的
ImageNet Challenge on Kaggle!

正确认识数据预处理（1）

数据预处理工作往往有一定代价的
导致数据损失，甚至可能对数据产生曲解。
因此，应尽可能减少预处理对数据原始内容的改变。
要减少数据预处理工作，必须提升计算方法（平台）的鲁棒性！

正确认识数据预处理（2）

从本质上看，数据预处理的必要性的讨论可以归结为两个问题：
一是我们是否接受“数据的复杂性”；（接受复杂性，则意味着对计算平台对数据更有鲁棒性）
二是我们的计算能力是否足以解决数据中的复杂性问题 （计算能力强，则可以省略一些简单的预处理工作）（这就是为什么 大数据和云计算是一对的原因）

正确认识数据预处理（3）

随着大数据时代的到来，上层数据处理应用系统的主要需求发生了新的变化。例如，
简单查询操作的响应时间的高度重视
强调应用系统对不断变化的环境的自适应能力等。
同时，上述新趋势也对数据预处理活动提出了新的挑战。