数据挖掘-数据预处理

发表于 | 分类于 | 阅读次数:
字数统计: 3,613 | 阅读时长 ≈ 14

数据预处理的主要步骤包括数据清理、数据集成、数据归约和数据变换。
数据清理可以用来清除数据中的噪声，纠正不一致。数据集成将数据由多个数据源合并成一个一致的数据存储，如数据仓库。数据归约可以通过如聚集、删除冗余特征或聚类来降低数据的规模。数据变换（如规范化）可以用来把数据压缩到较小的区间，如0.0到1.0，从而提高涉及距离度量的算法的准确率和效率。

数据清理

现实世界的数据一般是不完整的、有噪声的和不一致的。数据清理试图填充缺失值、光滑噪声并识别离群点、纠正数据中的不一致。

缺失值

常用的缺失值填补方法：

  1. 忽略元组：当元组有多个属性缺少值时。
  2. 人工填写缺失值。
  3. 使用一个全局常量填充：如unknown，简单但并不十分可靠。
  4. 使用属性的中心度量填充：对于对称的数据分布用均值，倾斜的用中位数。
  5. 使用与给定元组属同一类的所有样本的属性均值或中位数。
  6. 使用最可能的值填充：可以使用回归，决策树，贝叶斯等方法预测；最流行的策略。

噪声数据

可以使用分箱技术光滑数据，去除噪声。
例如数据4,8,15,21,21,24,25,28,34。
划分为等频的箱：

1
2
3
箱1： 4，8，15
箱2： 21，21，24
箱3： 25，28，34

用箱均值光滑：

1
2
3
箱1： 9，9，9
箱2： 22，22，22
箱3： 29，29，29

用箱边界光滑（每一个值被替换为最近的边界值）：

1
2
3
箱1： 4，4，15
箱2： 21，21，24
箱3： 25，25，34

除此之外，还有回归和离群点分析等方法。

数据集成

实体识别问题

由于数据语义的多样性，如何匹配多个数据源的模式，实质上是实体识别问题，如识别一个数据库中的customer_id和另一个数据库中的cust_number指的是同一个属性。

冗余和相关分析

冗余是数据集成的另一个重要问题，如一个属性能被另一个或几个属性导出。有些冗余可以被相关分析检测到。

一、 标称数据的$\chi ^2$（卡方）检验

标称数据，如名称，状态等，两个属性A和B之间的相关联系可以通过$\chi ^2$检验发现。
$$ \chi ^2 = \sum_{i=1}^{c} \sum_{j=1}^{r} \frac{(o_{ij}-e_{ij})^2}{e_{ij}} $$
其中，$o_{ij}$是联合事件$(A_i, B_j)$的观测频度，而$e_{ij}$是$(A_i, B_j)$的期望频度。
$$ e_{ij} = \frac{count(A = a_i) \times count(B = b_j)}{n} $$
其中，$n$是数据元组的个数，$count(A = a_i)$是A上具有值$a_i$的元组个数，而$count(B = b_j)$是B上具有值$b_j$的元组个数。
举一个简单的例子，如下表所示，

A1 A2 sum
B1 q r q+r
B2 s t s+t
sum q+s r+t q+r+s+t

根据上面公式，则有
$$ o_{A1B1} = q $$
$$ e_{A1B1} = \frac{(q+s) \times (q+r)}{q+r+s+t} $$
其余类似，由此便可以计算出$\chi ^2$。
$\chi ^2$检验假设A和B是独立的，检验基于显著水平，具有自由度$(r-1) \times (c-1)$，对于此自由度，在某个置信水平下，如果可以拒绝该假设，说明A和B相关。

二、 数值数据的相关系数

数值数据可以通过计算属性A和B的相关系数来估计相关度。
$$ r_{A,B} = \frac{\sum_{i=1}{n} (a_i - \bar A )(b_i - \bar B)}{n \sigma _{A} \sigma _{B}} $$
其中，$\sigma _{A}$ 和$\sigma {B}$分别是A和B的标准差，$n$是元组的个数。
取值范围$-1 \leq r{A,B} \geq 1$，如果$r_{A,B}$大于0，则表示正相关，值越大相关性越强；等于0则代表独立；小于0表示负相关。

三、 数值数据的协方差

协方差用来评估两个属性如何一起变化。
$$ Cov(A,B) = E((A-\bar A)(B-\bar B)) = \frac{\sum_{i=1}^{n}(a_i - \bar A)(b_i - \bar B)}{n} $$
可以证明，
$$ Cov(A,B) = E(A \cdot B) - \bar A \bar B$$
此公式通常用来计算协方差，较为方便。
当A和B独立时，则有$E(A \cdot B) = E(A) \cdot E(B)$，从而$Cov(A,B) = 0$， 反之不成立。
那么$E(A \cdot B)$怎么算呢？举个例子。

A B
0 q r
1 s t

则有
$$ E(A \cdot B) = \frac{q \times r + s \times t}{2} $$
协方差与相关系数的关系如下，
$$ r_{A,B} = \frac{Cov(A,B)}{\sigma _{A} \sigma _{B}} $$

数据规约

数据规约包括维规约、数量规约和数据压缩。

维规约（Dimensionality reduction）

减少所考虑的属性的个数，包括特征提取（Feature extraction)：无监督方法主成分分析（PCA）、有监督方法线性判别分析（LDA）；属性子集选择（Feature selection）等。

特征选择：

从所有的$p$个特征中选取大小为$d$的最佳子集。
$$ A \in [0,1]^{p \times d} $$
其中A的每一列只有一个1。

特征提取：

通过所有 p 特征的线性或非线性组合提取 d 个新特征。
$$ A\in R^{p \times d} : x \in R^p \rightarrow z = A^T x \in R^d $$

PCA

对于主成分分析（principal components analysis），基本思想是将数据投影到一个小得多的空间上,投影后投影值尽可能分散，即方差尽可能大（我们认为方差大意味着蕴含了原数据更多的信息）。PCA计算k个标准正交向量，作为输入数据的基，这些向量称为主成分。把数据变换到一个新的坐标系统中，使得任何数据投影的第一大方差在第一个坐标(称为第一主成分)上，第二大方差在第二个坐标(第二主成分)上，依次类推。

下面看如何选择这k个标准正交基。将一组N维向量降为K维（K大于0，小于N），其目标是选择K个标准正交基，使得原始数据变换到这组基上后，各特征两两间协方差（为了让两个特征尽可能表示更多的原始信息，我们不希望它们之间存在相关性的，而协方差正可以两个特征间的相关性）为0（正交基保证了为0），而特征的方差则尽可能大（在正交的约束下，取最大的K个方差）。

举个例子：
为了方便表示，我们首先将每个特征的所有值都减去该特征的均值，其结果是将每个特征都变为均值为0。
我们的目标是投影后投影值尽可能分散，而这种分散程度，可以用数学上的方差来表述
$$Var(a)=\frac{1}{m}\sum_{i=1}^m{(a_i-\mu)^2}$$
由于上面我们已经将每个特征的均值都化为0了，因此方差可以表示为
$$ Var(a)=\frac{1}{m}\sum_{i=1}^m{a_i^2} $$
找到一个方向使得投影后方差最大，这样就完成了第一个方向的选择，继而我们选择第二个投影方向。
我们希望两个方向之间不存在相关性的，可以用两个特征的协方差表示其相关性，由于已经让每个特征均值为0，则
$$ Cov(a,b)=\frac{1}{m}\sum_{i=1}^m{a_ib_i} $$
可以看到，在特征均值为0的情况下，两个字段的协方差可以表示为其内积除以元素数m。
我们在这里认为协方差为0时蕴含独立性。为了让协方差为0，我们选择第二个基时只能在与第一个基正交的方向上选择。因此最终选择的两个方向一定是正交的。
我们发现特征内方差及特征间协方差均可以表示为内积的形式，而内积又与矩阵相乘密切相关。
假设我们只有a和b两个字段，那么我们将它们按行组成矩阵X：
$$
X=\begin{pmatrix}
a_1 & a_2 & \cdots & a_m \\
b_1 & b_2 & \cdots & b_m
\end{pmatrix}
$$
用X乘以X的转置，并乘上系数1/m，得到：
$$
\frac{1}{m}XX^\mathsf{T}=\begin{pmatrix}
\frac{1}{m}\sum_{i=1}^m{a_i^2} & \frac{1}{m}\sum_{i=1}^m{a_ib_i} \\
\frac{1}{m}\sum_{i=1}^m{a_ib_i} & \frac{1}{m}\sum_{i=1}^m{b_i^2}
\end{pmatrix}
$$
这个矩阵对角线上的两个元素分别是两个字段的方差，而其它元素是a和b的协方差。
推广一下，设我们有m个n维数据记录，将其按列排成n乘m的矩阵X，设$C=\frac{1}{m}XX^\mathsf{T}$，则C是一个对称矩阵，其对角线分别个各个字段的方差，而第i行j列和j行i列元素相同，表示i和j两个字段的协方差。C被称为协方差矩阵。
我们的目标即使得各个特征内的方差最大，而特征之间的协方差为0，即如何将协方差矩阵转换为一个对角矩阵，除对角线外的其它元素化为0，并且在对角线上将元素按大小从上到下排列。

我们进一步看下原矩阵与基变换后矩阵协方差矩阵的关系：
设原始数据矩阵X对应的协方差矩阵为C，而P是一组基按行组成的矩阵，设Y=PX，则Y为X对P做基变换后的数据。设Y的协方差矩阵为D，我们推导一下D与C的关系：
$$
\begin{array}{l l l}
D & = & \frac{1}{m}YY^\mathsf{T} \\
& = & \frac{1}{m}(PX)(PX)^\mathsf{T} \\
& = & \frac{1}{m}PXX^\mathsf{T}P^\mathsf{T} \\
& = & P(\frac{1}{m}XX^\mathsf{T})P^\mathsf{T} \\
& = & PCP^\mathsf{T}
\end{array}
$$
优化目标变成了寻找一个矩阵P，满足PCPT是一个对角矩阵，并且对角元素按从大到小依次排列，那么P的前K行就是要寻找的基，用P的前K行组成的矩阵乘以X就使得X从N维降到了K维并满足上述优化条件。
由上文知道，协方差矩阵C是一个是对称矩阵，在线性代数上，实对称矩阵有一系列非常好的性质：

1）实对称矩阵不同特征值对应的特征向量必然正交。

2）设特征向量$\lambda$重数为r，则必然存在r个线性无关的特征向量对应于$\lambda$，因此可以将这r个特征向量单位正交化。
由上面两条可知，一个n行n列的实对称矩阵一定可以找到n个单位正交特征向量，设这n个特征向量为$e_1,e_2,\cdots,e_n$,我们将其按列组成矩阵：
$$
E=\begin{pmatrix}
e_1 & e_2 & \cdots & e_n
\end{pmatrix}
$$
则对协方差矩阵C有如下结论：
$$
E^\mathsf{T}CE=\Lambda=\begin{pmatrix}
\lambda_1 & & & \\
& \lambda_2 & & \\
& & \ddots & \\
& & & \lambda_n
\end{pmatrix}
$$
其中$\Lambda$为对角矩阵，其对角元素为各特征向量对应的特征值（可能有重复）。
到这里，我们发现我们已经找到了需要的矩阵P：
$$ P=E^\mathsf{T} $$
P是协方差矩阵的特征向量单位化后按行排列出的矩阵，其中每一行都是C的一个特征向量。如果设P按照Λ中特征值的从大到小，将特征向量从上到下排列，则用P的前K行组成的矩阵乘以原始数据矩阵X，就得到了我们需要的降维后的数据矩阵Y。

属性子集选择

属性子集选择即通过删除不相关或冗余的属性来减少数据量，与PCA的区别是它是在原来就有的属性上选择一个好的属性集合。

数量规约（Numerosity reduction ）

用替代的、较小的数据表示形式替换原数据。有参数方法，包括使用模型如回归等估计数据，使得只需要存储模型参数，而不是实际数据；非参数方法包括直方图、聚类、抽样等。
可以使用直方图（histogram）来近似数据的分布，使用等宽（每个桶宽度一致）或者等频（每个桶大致包含相同个数的邻近样本）划分。
抽样可以是无放回的简单随机抽样（SRSWOR），也可以是有放回的简单随机抽样（SRSWR），二者区别是后者同一个样本有可能被抽取多次。

数据压缩（Data compression）

包括无损的和有损的，维规约和数量规约也可以看作某种形式的数据压缩。
一个原则：花费在数据规约上的计算时间不应超过或抵消在规约后的数据上挖掘所节省的时间。

数据变换

对于数据变换，我们介绍规范化和离散化。

规范化

一般而言，用较小单位表示的属性将导致该属性具有较大值域，因此趋向于使这样的属性具有较大影响或权重，尤其对于神经网络或基于距离的算法或聚类。规范化试图赋予所有属性相等的权重，使之落入较小的共同区间，如[-1,1]或[0,1]。

  1. 最小-最大规范化
    将A的值$v_i$映射到区间$[newMin_A, newMax_A] $
    $$ \hat v_i = \frac{v_i - min_A}{max_A - min_A} (newMax_A - newMin_A) + newMin_A $$

  2. z-score规范化
    $$ \hat v_i = \frac{v_i-\bar A}{\sigma _A} $$
    当属性A的最小最大值未知或者离群点左右了最小-最大规范化时，该方法是有用的。
    其中，方差$\sigma _A$可以替换为A的均值绝对偏差$s_A$
    $$ s_A = \frac{1}{n} (|v_1-\bar A| + \cdots + |v_n- \bar A|) $$
    对于离群点，$s_A$比方差更加鲁棒，因为计算$s_A$时不对到均值的偏差即$|x_i - \bar x|$取平方，因此离群点的影响会降低。

  3. 小数定标规范化
    小数定标规范化就是通过移动值的小数点的位置进行规范化，如986变换为0.986。

离散化

离散化通过把值映射到区间或较高层的概念来变换数值数据。离散化技术包括分箱、直方图分析、聚类、决策树等。如将年龄的原始值用高层的概念（如青年、中年和老年）取代。