Data Mining（二）：数据预处理

• 2021 年 1 月 5 日
• AI
• 数据挖掘应用

数据质量评估指标

• 准确性
• 完整性
• 一致性
• 时效性
• 可信性
• 可解释性

数据清理

数据清理（data cleaning）：通过填写缺失的值，光滑噪声数据，识别并删除离群点并解决不一致性来清理数据。数据清洗通常是一个两步迭代过程，包括偏差检测和数据变换。

缺失值

• 忽略元组
• 人工填写缺失值
• 使用一个全局变量填充缺失值
• 使用数据的中心度量填充缺失值：对于对称数据分布，选择均值；而倾斜数据分布使用中位数
• 使用与给定元组数同一类的所有样本的属性均值或中位数
• 使用最有可能的值填充：通过回归、决策树等

噪声数据

噪声（noise）是被测量的变量的随机误差或方差。

数据光滑技术：

• 分箱（binning）：分箱方法通过考察数据的邻近值来光滑有序数据值（局部光滑）。有序数据分享后，可分别根据箱均值、箱中位数、箱边界光滑
• 回归（regression）：用一个函数你和数据来光滑数据，包括线性回归和多元线性回归
• 离群点分析（outlier analysis）：可通过聚类的方法检测离群点

数据集成

数据集成（data integration）：集成多个数据库、数据立方体或文件以分析来自多个数据源的数据。

• 实体识别问题
• 属性冗余
• 元组重复
• 数据值冲突

实体识别问题

将来自现实世界的多个信息源的等价实体进行匹配，例如异名同义属性名的匹配。

• 属性的元数据包括名字、含义、数据类型和属性的允许取值范围，以及处理空白、零和Null值的空值规则

冗余和相关性分析

冗余：一个属性可有另一个或一组属性导出；或是属性和维命名的不一致也可能导致冗余。

部分冗余可由相关分析检测，即度量一个属性在多大程度上蕴涵另一个。

• 标称数据，使用卡方检验\chi ^2进行相关分析；

  • 

  • 将两个属性描述数据表为相依表，列为属性A的c个值，行为属性B的r个值，见上图；

  • \chi^{2}=\sum_{i=1}^{c} \sum_{j=1}^{r} \frac{\left(o_{i j}-e_{i j}\right)^{2}}{e_{i j}}，其中o_{i j}是联合事件(A_i,B_j)的观测频度（即实际计数），e_{i j}是(A_i,B_j)的期望频度，e_{i j}=\frac{\operatorname{count}\left(A=a_{i}\right) \times \operatorname{count}\left(B=b_{j}\right)}{n}，其中n是数据元组的个数，\operatorname{count}\left(A=a_{i}\right)是A中具有值a_i的元组个数，\operatorname{count}\left(B=b_{j}\right)是B中具有值b_j的元组个数；

  • 根据\chi ^2分布的百分点表，查找自由度(r-1)\times(c-1)下的显著水平，计算值大于该值，拒绝假设，两属性相关，反之独立。

    

  • \chi ^2统计检验假设A和B是独立的；

  • 对\chi ^2值贡献最大的单元是实际计数与期望技术很不相同的单元。

• 数值数据，使用相关系数和协方差进行相关分析。

  • 属性A和B的相关系数（Pearson积矩系数）：r_{A, B}=\frac{\sum_{i=1}^{n}\left(a_{i}-\bar{A}\right)\left(b_{i}-\bar{B}\right)}{n \sigma_{A} \sigma_{B}}=\frac{\sum_{i=1}^{n}\left(a_{i} b_{i}\right)-n \bar{A} \bar{B}}{n \sigma_{A} \sigma_{B}}，其中，n为元组个数，\bar A、\bar B分别为对应均值，\sigma_{A}、 \sigma_{B}分别为A/B的标准差。
    • r_{A,B}取值范围为[-1,1]，该值大于0时，表示正相关，值越大相关性越高；反之亦然。
    • 散点图可用来观测属性之间的相关性；
    • 相关性并不蕴涵因果关系。
  • 属性A和B的协方差：\operatorname{Cov}(A, B)=E((A-\bar{A})(B-\bar{B}))=\frac{\sum_{i=1}^{n}\left(a_{i}-\bar{A}\right)\left(b_{i}-\bar{B}\right)}{n}=E(A·B)-\bar A \bar B。
    • r_{A,B}=\frac{\operatorname{Cov}(A,B)}{\sigma_a \sigma_b}；
    • 如果A和B独立，E(A,B)=E(A)·E(B)，Cov(A,B)=0；然而，其逆不成立，即某些随机变量对的协方差可能为0，却是非独立的；
    • 方差是协方差的特殊情况，其中两个属性相同，即属性与其自身的协方差。

数据归约

数据归约（data reduction）：得到数据集的简化表示，它小得多，但能够产生同样的分析结果。

• 花费在数据归约上的时间不应超过或“抵消”在规约后的数据上挖掘所节省的时间。

维归约

维归约：减少所考虑的随机变量数量或属性的个数。

小波变换

离散小波变换（DWT）是一种线性信号处理技术，用于将数据向量X变换为不同的数值小波系数向量X^{‘}，两个向量具有相同的长度。

• 小波系数：一个信号无论进行连续小波变换（CWT）或是离散小波变换（DWT），变换完的结果就叫小波系数；小波系数是没有量纲单位的结果，需要经过重构这些系数得到实际有量纲的信号。
• 虽然小波变换后的数据与原数据长度相等，但小波变换后的数据可以截短，进存放一部分最强的小波系数，就能保留近似的压缩数据；
• DWT也可用于消除噪声，而不会光滑掉数据的主要特征；
• 给定一组小波系数，使用所用的DWT的逆，可以构造原数据的近似；
• 与离散傅里叶变换（DFT）相比，DWT是一种更好的有损压缩（相同数目系数时DWT更接近原数据；相同近似下DWT需要的空间更小）；小波空间相比DFT的局部性更好，有助于保留局部细节；只有一种DFT，担忧若干族DWT；
• DWT一般使用层次金字塔算法，在每次迭代时数据减半，计算速度很快。
  1. 输入数据向量的长度L必须为2的整数幂，必要时在数据后添加0；
  2. 每个变换应用两个函数，第一个求和或加权平均进行数据光滑；第二个进行加权差分，提取数据的细节特征；
  3. 两个函数分别作用于原数据的所有数据点对(x_{2i},x_{2i+1})，得到两个长度为L/2的数据集，分别代表输入数据的光滑后的版本或低频版本和它的高频内容；
  4. 递归上述过程，直到得到的结果数据集的长度为2；
  5. 由以上迭代得到的数据集中选择的值被指定为数据变换的小波系数。
• 对输入数据应用矩阵乘法，也可以得到小波系数；通过将矩阵分解成几个稀疏矩阵的乘积，对于长度为n的输入向量，“快速DWT”算法的复杂度为O(n)。

主成分分析

主成分分析PCA：将n维特征映射到k维上，这k维是全新的正交特征也被称为主成分，是在原有n维特征的基础上重新构造出来的k维特征。基本过程为：

• 对数据规范化，使得每个属性都落入相同的区间，避免较大定义域属性对其他属性的支配；

• PCA计算k个标准正交向量，作为规范化输入数据的基（输入数据是主成分的线性组合）；

  • 计算数据矩阵的协方差矩阵；
  • 计算协方差矩阵的特征值和特征向量；
    • 特征值分解协方差矩阵
    • 奇异值分解协方差矩阵
  • 选择特征值最大（即方差最大）的k个特征所对应的特征向量组成矩阵；
  • 将数据矩阵转换到新的空间当中，实现数据特征的降维。

• 与小波变换相比，PCA可以更好的处理稀疏数据，而小波变换更适合高维数据。

属性子集选择

属性子集选择（特征子集选择）：检测并删除不相关、弱相关或冗余的属性或维。

• 属性子集选择通常使用压缩搜索空间的启发式算法，例如典型的贪心算法：
  • 逐步向前选择：每一步在原属性集中确定最好的属性，将其加入归约集；
  • 逐步向后删除：每一步删除现有属性集中最差的属性；
  • 逐步向前选择和逐步向后删除的组合：每一步选择一个最好的属性，并删除剩余属性中最差的属性；
  • 决策树归纳：由给定的数据构造决策树，不出现在树中的所有属性被认为是“无意义”属性，出现在树中的属性形成规约后的属性子集。
• 属性构造：通过组合属性（如高度和宽度组合为面积属性），发现属性间联系的缺失信息。

数量归约

数量规约：用替代的、较小的数据表示形式替换原数据。

• 参数方法：使用模型估计数据，只需存放模型参数而不是实际数据；
• 非参数方法

参数方法

回归和对数-线性模型

• 线性回归：利用线性回归方程的最小二乘函数对一个或多个自变量和因变量之间关系进行建模的一种回归分析，包括简单线性回归和多元线性回归。
• 对数线性模型：在线性模型的基础上通过复合函数（sigmoid/softmax/entropy ）将其映射到概率区间，使用对数损失构建目标函数，包括逻辑回归、最大熵模型和条件随机场等。

非参数方法

直方图

• 等宽直方图：每个桶的区间范围一致；
• 等频直方图：每个桶大致包含相同个数的邻近数据样本。

聚类

聚类：将对象划分为群或簇，使得同一个簇内的对象相似，而与其他簇内的对象相异。

• 簇质量的度量：
  • 直径——卒中两个对象的最大距离；
  • 形心距离——簇中每个对象到簇形心的平均距离。

抽样

• 无放回简单随机抽样SRSWOR

• 有放回简单随机抽样SRSWR

• 簇抽样

• 分层抽样：数据分层（分类）后，在每层按比例采样

• 采用抽样进行数据规约的好处：花费时间正比于样本集的大小，而不是数据集的大小，因此抽样复杂度可能亚线性（sublinear）于数据的大小；

• 对于固定大小的样本，抽样复杂度随数据维数线性增加，而其他技术复杂度呈指数增加。

数据压缩

数据压缩：使用变换，得到原数据的规约或“压缩”表示。如果原数据可由压缩后的数据重构，而不损失任何信息，称为无损压缩，否则是有损的。

数据变换与数据离散化

数据变换（data transformation）：包括规范化、数据离散化和概念分层产生等。

数据规范化

规范化：把数据属性按比例缩放，使之落入一个特定的小区间。

• 最小-最大规范化：x^{‘}_{i}=\frac{x_i-min}{mxa-min}(max_{new}-min_{new})+min_{new}；
  • 最小-最大规范化保持原始数据之间的联系；
  • 规范化后区间范围[min_{new},max_{new}]。
• z分数规范化（零均值规范化）：x^{‘}_{i}=\frac{x_i-\bar x}{\sigma_x}；
  • 当数据的最大最小值未知，或离群值左右最小-最大化规范时，使用该方法；
  • 规范化后的区间范围[\frac{x_{min}-\bar{x}}{\sigma_x},\frac{x_{max}-\bar{x}}{\sigma_x}]。
  • 上式中的标准差\sigma_x可以用均值绝对偏差s_x替换，s_{x}=\frac{1}{n}\left(\left|x_{1}-\bar{x}\right|+\left|x_{2}-\bar{x}\right|+\cdots+\left|x_{n}-\bar{x}\right|\right)，这样x^{‘}_{i}=\frac{x_i-\bar x}{s_x}；
  • 对于离群点，均值绝对偏差s_x比标准差\sigma_x更加鲁棒。
• 小数定标规范化：通过移动数据的小数点未知进行规范化，x_{i}^{‘}=\frac{x_i}{10^j}，其中j是使得max(|x_i^{‘}|)<1成立得最小整数；
  • 规范化后的区间范围(-1,1)。

数据离散化

• 通过分箱离散化：等宽或等频分箱，用箱均值或中位数替换箱中的每个值，将属性离散化；
• 通过直方图分析离散化：等宽直方图或等频直方图；
• 通过聚类、决策树和相关分析离散化
  • 聚类——自顶向下的划分策略或自底向上的合并策略；非监督的；
  • 决策树——自顶向下的划分方法；有监督的；主要思想是，选择划分点使得一个给定的结果分区包含尽可能多的同类元组，其中，熵是最常用的划分点度量；
  • 相关性度量可用于离散化——例如ChiMerge是一种基于\chi^{2}的离散化方法。
    • ChiMerge是自底向上的策略；有监督的；
    • ChiMerge过程如下：初始时，将数据按序排好，将数值属性的每个值看作一个区间；对每个相邻区间进行\chi^{2}检验；将具有最小\chi^{2}值的相邻区间合并在一起；递归合并过程，直到满足预定义的终止条件。
• 标称数据的概念分层
  • 基于模式定义或每个属性的不同值个数产生；
  • 启发式规则：定义在较高概念层的属性（如country）与定义在较低概念层的属性（如street）相比，一般包含较少的不同值，因此，可以根据给定属性集中每个属性不同值的个数，自动地产生概念分层，但并不绝对。

TODO

• 小波变换
• 主成分分析（基于特征值 vs 基于SVD）//blog.csdn.net/program_developer/article/details/80632779
• 简单线性回归模型 //zhuanlan.zhihu.com/p/73494604
• 多元线性回归 //zhuanlan.zhihu.com/p/48541799 //zhuanlan.zhihu.com/p/124902625
• 对数线性模型 //zhuanlan.zhihu.com/p/112816694

参考

1. 《数据挖掘：概念与技术》第三章
2. 小波系数 //blog.csdn.net/hai_girl/article/details/85105540
3. 小波变换通俗解释 //blog.sina.com.cn/s/blog_13bb711fd0102w9x1.html
4. 白话解释“差分”、“一阶差分” //zhuanlan.zhihu.com/p/46699931