数据挖掘中的数据预处理

0.0 关于 《DATA MINING—Concepts and Techniques》

《DATA MINING—Concepts and Techniques》是经典的数据挖掘入门书籍，内容囊括数据挖掘的基本概念、数据的预处理、数据的存储、数据中模式的挖掘、分类、聚类、异常检测等方面，作者是著名的韩家炜教授。数据的预处理在真实世界数据中是非常关键的一步，它既是不同数据挖掘应用的共同起点，又很大程度上影响了数据挖掘应用的效果。我将翻译、整理这本书中关于数据预处理的部分，如果有纰漏欢迎指正。

0.1 数据预处理综述

  • 由于真实世界中的数据来源复杂、体积巨大，往往难以避免地存在缺失、噪声、不一致（inconsistencies）等问题。
  • 当数据的维数过高时还会存在所谓的“维数诅咒（Curse of dimensionality）”问题，过高的维度不仅增加了计算量，反而可能会降低算法的效果。
  • 有些算法对数据存在特殊的要求，比如KNN、Neural Networks、Clustering等基于距离（distance based）的算法在数据进行normalize之后效果会提升。

解决上述问题需要在将数据送入算法之前进行预处理，具体包括Data Cleaning,Data Intergation，Data reduction,Data Transformation and Data Discretization等步骤。下面将对各个部分详细展开。

1. 数据清洗（Data Cleaning）

数据清洗的主要作用是处理数据的某些纪录值缺失，平滑数据中的噪声、发现异常值，改正不一致。

值缺失

针对数据中某些记录的值缺失问题（比如用户销售数据中，有些顾客的收入信息缺失，有些顾客的年龄信息缺失），可以采用如下的方式：

  • 忽略存在缺失值的记录。在分类问题中，如果样本（本文中，’一个样本’和’一条记录’是同义词）的label缺失了，那么这个样本一定是要丢弃的。其他情况下，除非一条记录缺失了多个值，否则这种简单粗暴的方法往往效果不好，尤其当不同的属性值缺失状况相差很大时，效果会更差。
  • 手动填写缺失的值。根据经验手工补上缺失的值，但是这种活儿谁愿意干呢？
  • 用全局的常量来替代缺失值。再拿用户销售数据做例子，对于年龄缺失的纪录年龄全用unknow来代替，但是对于数据挖掘算法来说，young和unknow并没有什么本质的不同，都只是属性值的一种而已，所以所有年龄缺失的纪录在算法看来都是同一种年龄—-“unknow”,这反而可能会降低算法的效果。
  • 使用中值和均值来替代缺失值。某种属性的中值和均值代表了此属性的平均趋势，用它们来代替缺失值不失为一种可行的方案。但是，当属性是“红、绿、蓝”这种离散值时显然不存在中值、均值的概念。
  • 使用class-specific的中值和均值来代替缺失值。在有监督问题中，一个基本假设是label相同的样本属性也相似，那么，某个样本的缺失值，用其所在类别内的所有样本的在此属性的均值或中值来代替理应效果更好。
  • 使用最可能的值来填充缺失值。用此样本的其他属性来推断缺失属性的最可能值，实际上这就变成了一个回归或分类问题（属性值连续时是回归问题，离散时是分类问题）。实际中常用贝叶斯推理或决策树来解决上述问题。

上述的第3-第6种方法都会引入偏差，因为补充的缺失值跟真实值很可能不同。第六种方法在现实中非常流行，因为它在推断缺失值时使用的信息最多，那么结果理应更准确。不过需要注意的是，有时缺失值也会提供有用的信息，比如在信用卡申请用户数据中，没有驾照号码很可能是因为没有汽车，而是否有汽车是评价信用等级很有用的信息。

噪声（noise）

噪声是混在观测值的错误(error)或误差(variance)，具体去噪方式有以下几种：

  • Binning。Data Bininig，又称为Bucketing，从字面意思来展开，就是把样本点按照一定的准则分配到不同的bin(bucket)中去，然后对每个样本点根据其所在bin内样本点的分布来赋一个新值，同一个bin的样本点被赋予的新值是一致的。对于一维数据，bin可以按照区间大小划分，也可以按照data frequency来划分，而每个bin的值可以选择分布在其中样本的均值、中值或者边界值。另外，CNN中的max-pooling层，也属于data binning的范畴，典型的max-pooling层bin的尺寸为2*2，选择每个bin中的最大值作为bin四个值的新值。
  • 回归。如果变量之间存在依赖关系，即y=f(x)，那么我们可以设法求出依赖关系f，从而根据x来预测y，这也是回归问题的实质。实际中更常见的假设是P(y)=N(f(x))，N是正态分布。假设y是观测值且存在噪声，如果我们能求出x和y之间的依赖关系，从而根据x来更新y的值，就可以去除其中的随机噪声，这就是回归去噪的原理。
  • 异常值检测。数据中的噪声可能有两种，一种是随机误差，另外一种可能是错误，比如我们手上有一份顾客的身高数据，其中某一位顾客的身高纪录是20m，很明显，这是一个错误，如果这个一场的样本进入了我们训练数据可能会对结果产生很大影响，这也是去噪中使用异常值检测的意义所在。当然，异常值检测远不止去噪这么一个应用，网络入侵检测、视频中行人异常行为检测、欺诈检测等都是异常值检测的应用。异常值检测方法也分为有监督，无监督和半监督方法，这里不再详细展开。

    2. 数据融合

    所谓数据融合就是将不同来源的、异质的数据融合到一起。良好的数据融合可以减少数据中的冗余(redundacies)和不一致性(inconsistence)，进而提升后续步骤的精度和速度。数据融合包括如下几个步骤：

    实体识别问题（Entity Identification Problem）

    实体识别中最主要的问题匹配不同的数据源中指向现实世界相同实体的纪录。比如分析有不同销售员纪录的14年和15年两年的销售数据，由于不同的销售员有不同的纪录习惯，顾客的名字纪录方式并不一样，一个销售员喜欢纪录全名（例如 Wardell Stephen Curry II），另外一个销售员喜欢将中间名省略（Wardell S Curry II ），虽然Wardell Stephen Curry II和Wardell S Curry II是现实世界中是同一名顾客，但计算机会识别为两位不同的顾客，解决这个问题就需要Entity Identification。一个常用的Entity Indentification Problem的解决算法是LSH算法
    另外一个问题是Schema integration, Schenma在这里指使用DBMS支持的形式化语言对一个数据库的结构化描述，Schema是构建一个数据库的蓝图。Schema intergration则是指，将若干个Schema合成一个global Schema，这个global Schema可以表达所有子Schema的要求（也就是一个总的蓝图）。属性的metadata（比如名称、取值范围、空值处理方法）可以帮助减少Schema Intergration的错误。

    冗余和相关性分析

    当能够从样本的一个或多个属性推导出另外的属性的时候，那么数据中就存在冗余。检测冗余的一种方法是相关性分析—-给定要进行检测的两个属性，相关性分析可以给出一个属性隐含(imply)另外一个属性的程度。对于标称型（Nominal）数据，可以使用$\chi^2$检验，而对于数值数据，可以根据方差和相关系数来分析。
  • 标称数据的$\chi^2$相关性检验。
    假设有A和B两个属性，A有$a_1,a_2,…a_c$共c种不同的取值，B有$b_1,b_2,…b_r$共r种不同的取值。我们可以为属性A和B建立一个列联表(contingency table)C，所谓列联表，就是一个r*c的矩阵，位置（i,j）代表属性A的值$a_i$和属性B的值$b_i$在样本中同时出现(事件(A=$a_i$,B=$b_j$)发生)的频率$o_ij$。属性A和属性B的$\chi^2$值可以通过下面的式子计算：

    $\chi^2=\sum_{i=1}^{c}\sum_{j=1}^{r}\frac{(o_{ij}-e_{ij})^2}{e_{ij}}$ (1)

其中$o_ij$是联合事件(A=$a_i$,B=$b_j$)发生的频率，$e_ij$是期望频率，用如下的公式计算：

$e_{ij}=\frac{count(A=a_i)\times count(B=b_j)}{n}$ (2)

  • 数值数据的相关系数
    假设有n个样本，$S_1,S_2,…S_n$,样本$S_i$的A，B两种属性的值分别是$a_i,b_i$，那么属性A和B的相关系数定义是：

    $r_{A,B}=\frac{\sum_{i=1}^{n}(a_i-\overline{A})(b_i-\overline{B})}{n\delta_A\delta_B}=\frac{\sum_{i=n}^{n}(a_i b_i)-n\overline{A} \overline{B}}{n\delta_A\delta_B}$ （3）

当相关系数是正的时候表示属性A和属性B正相关，当相关系数是负的时候属性A和属性B负相关，注意，相关关系并不等同于因果关系。