数据挖掘第二章 数据预处理

数据挖掘 数据处理 预处理 规范化

---

数据挖掘技术与原理主目录：
目录

第二章目录：

---

2 数据处理基础

2.1 数据及数据类型

数据：

广义的数据是数据对象及其属性的集合，其表现形式可以使数字、符号、文字、图像或是计算机代码等等。

属性：

（特征、维、字段）指一个对象的某个方面性质或特征。一个对象通过若干属性来刻画。可以用一个多维向量来进行表示

数据集

数据对象的集合（同分布、同特征）（训练集和测试集是概率同分布的）

属性类型：定性的（优良中差；男女；红黄蓝）、定量的（60,80,95）

数据集的特性：

维度（Dimensionality）：数据集中的对象具有的属性个数总和。维归约（把没有用的维，又叫特征选择）。

稀疏性（Sparsity）：指在某些数据集中，有意义的数据非常少，对象在大部分属性上的取值为0；非零项不到1%。文本数据集的维度都很高，且具有高度的稀疏性。

分辨率（Resolution）：不同分辨率下数据的性质不同。

数据集的类型

• 记录数据
  
  • 事务数据或购物篮数据
  • 数据矩阵
• 基于图形的数据
  
  • 万维网
  • 化合物结构
• 有序数据
  
  • 时序数据
  • 序列数据
  • 空间数据
  • 流数据

记录数据

事务数据是一种特殊类型的记录数据，其中每一个记录涉及一个项的集合。比如顾客一次购买的商品的集合，每一个商品就是一个项。

文本数据

每一个词都是一个分量（属性），每个分量的值是对应词在文档中出现的次数。

2.2 数据统计特征

数据统计又叫汇总统计，用单个数或数的小集合（比如身高体重）来捕获大的数据集的各种属性特征。通常需要数据的中心趋势和离散程度特征。
中心趋势度量包括均值、中位数、众数和中列数（数据集里最大值和最小值的算术平均）。
离散程度度量包括四分位数极差（四分之三分位数和四分之一分位数的差）和方差。

2.2.1 中心性度量

均值（mean）：算术平均、加权平均、截断均值
截断均值指指定一个百分数p，丢弃高端和低端（p//2)%的数据，然后用常规方法计算平均值得到的结果。

中位数是p=100%的截断均值，而标准均值是p=0%的截断均值。

2.2.2 离散程度度量

极差 = $max(X) - min(X)$
方差（$s^2$）
方差对离群值特别敏感，可以选择其他更加稳健的度量，如四分位数极差、绝对平均偏差等。

2.3 数据预处理

高质量的数据是进行有效挖掘的前提，高质量的决定必须建立在高质量的数据上。

数据预处理的主要任务：

数据清理：

填写空缺数据，平滑噪声数据，识别、删除孤立点，解决不一致性

数据集成：

集成多个数据库，数据立方体或文件

数据变换：

规范化和特征构造

数据归约：

得到数据集的压缩表示及特征选择

数据离散化：

通过概念分层和数据离散化来归约数据

2.3.1 数据清理

现实世界中的数据是“脏”的：

• 不完整的：感兴趣的属性可能缺少属性值
• 含噪声的：包含错误的或是“孤立点“
• 不一致的：命名或者编码上存在差异

数据清理就是要解决以上三个问题

数据清理——缺失值
引起缺失值的原因：

• 设备原因
• 与其他已有数据不一样而被删除
• 因为误解而没有被输入的数据
• 在输入数据时，有些数据认为得不到重视而没有被输入
• 对数据的改变没有进行日志记载

缺失值的处理方法：

• 忽略元组（忽略这一个样本）
• 忽略属性列（忽略这一个属性，当这一属性大部分样本都缺失时）
• 人工填写缺失值：费时费力
• 自动填充缺失值：
  策略一：使用一个全局常量来填充缺失值（比如该样本均值或众数）
  策略二：使用与给定记录属同一类的样本的平均值或众数来填充缺失值
  策略三：用可能的值来代替缺失值，可以使用回归或其他基于推理的工具或决策树归纳确定。

数据清理——噪声数据的平滑方法
噪声是测量变量的随机错误或偏差。草绳是测量误差的随机部分，包含错误或孤立点值。

来源：

• 数据收集的设备故障
• 数据录入过程中人的疏忽
• 数据传输过程中的错误

平滑方法：
分箱：通过考察“邻居”来平滑有序数据的值。（平均值平滑、边界平滑）
参考图像处理中的均值去噪、边缘去噪以及高斯去噪
聚类：聚类将类似的值组织成群或“簇”。
回归：让数据适合一个函数来平滑数据。

2.3.2 数据集成

将两个或多个数据源中的数据，存放在一个一致的数据存储设备中。
数据一致性和冗余是两个重要的问题。

不同表中可能使用不同的名称来指示同一个属性；又比如说，一个数据库中储存了出生年月和年龄两个属性，这两个属性就是冗余的，因为年龄可以由出生年月导出。

2.3.3 数据变换

平滑、聚集（汇总，数据立方体的构建）、数据概念化、规范化（消除纲量的影响：最小-最大规范化、Z-score规范化、小数定标规范化）、属性构造（通过现有属性构造新的属性）

规范化：

最小-最大规范化（将最小到最大整个空间映射到0-1）

$$v' = \frac{v - min_\alpha}{max_\alpha - min_\alpha}$$

Z-score规范化（将分布规范为正态分布）

$$v' = \frac{v-mean_\alpha}{\sqrt{var_\alpha}}$$

小数定标规范化

$$v' = \frac{v}{10^j}，其中，j是使max(|v'|)<1的最小整数$$

离散化和概念分层：

离散化

通过将属性域化为区间，减少给定连续属性值的个数。区间标号可以代替实际的数据值。比如，18-30岁都可以分为“青年”区间。
离散化也是一个构造新特征的过程。

等宽离散化、基于聚类的离散化、基于熵的离散化

概念分层

通过使用高层的概念来替代底层的属性值，和离散化有一定相似性。

2.3.4 数据归约

数据挖掘的训练集的获取本身就是一个采样的过程。

维归约：

维度归约是指通过使用数据编码或变换，得到原始数据的归约或“压缩”表示。
如果维度较低，许多数据挖掘算法效果会更好。可以产生更容易理解的模型。可以降低数据挖掘算法的时间和空间复杂度。

抽样：

选择数据对象子集进行分析的常用方法。
抽样需要具有代表性，即使用样本与使用整个数据集的效果几乎一样。

例如：简单随机抽样（有/无放回）、分层抽样（聚类分成几个簇，每个簇进行简单随机抽样）

特征选择：

从一组已知特征集合中选择最具有代表性的特征子集，使其保留原有数据的大部分信息，即所选特征子集可以像原来的特征子集一样用来正确区分数据集的每个数据对象。
步骤：搜索特征子集，进行评估，如果不满足停止标准，则重新搜索。

属性子集选择
找出最小属性集，使得数据类的概率分布尽可能地接近使用所有属性的原分布。

启发式（探索式）搜索方法：

• 逐步向前选择
• 逐步向后删除
• 向前选择和向后删除相结合
• 判定归纳树（决策树：二叉树）

逐步向前选择

由空属性集开始，选择原属性集中最好的属性，并将其添加入该集合，重复该步骤直到无法选择出最优属性或满足一定阈值约束为止。

逐步向后删除

由整个属性集开始，每一步都删除掉尚在属性集中的最坏属性。直到无法选择出最差属性为止或满足一定阈值约束为止。

特征选择的分类：

• 有监督的特征选择
• 无监督的特征选择
• 半监督的特征选择

有监督的特征选择方法
特征评估方法

• 距离向量
  类间距离（欧氏距离、马氏距离）
  概率距离度量
  相关度
• 不一致度
  一个模式下两个样本除了标签之外其他特征都相同，说明这个模式不一致。因为两个具有完全相同属性的样本却被分到了不同的类中。

样本聚类法：

选择的依据是同类样本相同特征的取值相同或相近

主成分分析（PCA）：

找出主成分，这些属性是原属性的线性的线性组合。捕获数据的最大变差。

2.3 相似性度量

简单数据对象之间的相似度和相异度

相似度越高，两对象约相似，相异度则相反。

属性类比	相异度	相似度
标称的	d=0 if x == y else d=0	s=1 if x == y else s=0
序数的	$d = \frac{|x-y|}{n-1} 其中n是值的个数$	s = 1-d
区间的或比率的	$d = | x - y|$	$s = -d$, $s = \frac{1}{1+d}$, $s = d^{-d}$, $s = 1 - \frac{d-min_d}{max_d-min_d}$

连续属性之间的相关度：
线性相关系数：
对于两个连续特征(x,y)，其相关度的计算公式：

$$r = \frac{\sum_{i}{(x_i-\bar x_i)(y_i-\bar y_i)}}{\sqrt{\sum_{i}{(x_i-\bar x_i)^2}}\sqrt{\sum_{i}{(y_i-\bar y_i)^2}}}$$

余弦相似度：
如果（文档）d1和d2是两个（文档）向量，即
余弦相似度等于$cos(d1,d2)=\frac{d1\cdot d2}{|d1||d2|}$

离散属性的不确定性

特征X的信息熵计算：

$$H(X)= -\sum_{i}{P(x_i)log_2(P(x_i))}$$

已知变量y后x的条件信息熵计算：

$$H(X|Y)= -\sum_{j}{P(y_j)}\sum_{i}{P(x_i|y_j)log_2(P(x_i|y_j))}$$

信息增益：

$$IG(X|Y) = H(X) - H(X|Y)$$

数据对象之间的相异度

距离：

• 欧几里得距离：
  $$d(x,y) = \sqrt{\sum_{k=1}^{n}{(x_k-y_k)^2}}$$
  其中，n的维度（总特征数），$x_k$和$x_k$分别表示X和Y的第k分量。
• Minkowski距离：
  $$d(x,y) = (\sum_{k=1}^{n}{|x_k-y_k|^p})^{\frac{1}{p}}$$
  当p为2的时候是欧几里得距离，当p为1的时候是曼哈顿距离。

距离的性质：

• 非负性
• 对称性 （有的距离不满足）
• 三角不等式（有的距离不满足）

马氏距离：

$$d(\vec x,\vec y) = \sqrt{(\vec x,\vec y)^TS^{-1}(\vec x,\vec y)}$$
其中，S是$\vec x$和$\vec y$的两个向量协方差矩阵。

二值属性（如何度量二元数据的相似性？）

简单匹配系数（SMC）：

$$SMC = \frac{M_{11}+M_{00}}{M_{01}+M_{10}+M_{11}+M_{00}}$$
其中，$M_{01}$表示第一个向量中取0，第二个向量中取1的位置个数。
可以用来验证模型好坏（准确率）
但是适用于测试样本的结果比较平均的结果，即如果$M_{00}$远远大于其他三个，那么适用SMC计算出来就会发生偏差。

Jaccard系数：

$$J = \frac{M_{11}}{M_{01}+M_{10}+M_{11}}$$
其中的数值含义和SMC中的一样。
Jaccard去除了$M_{00}$，矫正了由于样本不平均情况而出现的偏差。

符号属性的距离定义：
简单匹配：$d(x,y) = \frac{M-S}{M}$
其中，M表示属性个数（维数），S表示匹配的属性个数。

如果是混合类型的变量，即向量中的元素混杂有数值属性、顺序属性或符号属性，这个时候（1）可以将变量按类型分组，然后单独进行聚类分析（2）将不同类型的变量组合到一个差异度矩阵中，吧所有变量转换到统一的区间[0,1]中。

对于第二种情况，表示为：

$$d(p,q) = \frac{\sum_{f=1}^{m}{\delta_{pq}(f)d_{pq}(f)}}{\sum_{f=1}^{m}{d_{pq}(f)}}$$