数据预处理（Data Preprocessing）

数据预处理是数据挖掘中的关键步骤，现实世界的数据往往是”脏”的——不完整、有噪声、不一致。本章涵盖数据预处理的四大核心任务：数据清洗、数据集成、数据归约、数据变换与离散化。

一、数据质量（Data Quality）

数据质量的六个维度：

准确性（Accuracy）：数据是否正确
完整性（Completeness）：数据是否有缺失
一致性（Consistency）：同一数据在不同地方是否一致。例如用户的余额在不同的缓存中不会即时更新（因为代价太大），因此从不同库调取同一时刻的用户余额可能得到不同的值
时效性（Timeliness）：数据是否得到及时更新
可信度（Believability）：数据在多大程度上可以被信任
可解释性（Interpretability）：数据是否容易被理解。例如字段含义是否清晰、编码体系是否有文档说明

二、数据预处理的主要任务

任务	说明
数据清洗（Data Cleaning）	填充缺失值、平滑噪声、识别/移除离群点、解决不一致
数据集成（Data Integration）	整合多个数据库、数据立方体或文件
数据归约（Data Reduction）	降维（Dimensionality reduction）、数量归约（Numerosity reduction）、数据压缩
数据变换与离散化	归一化、概念分层生成

三、数据清洗（Data Cleaning）

3.1 现实数据的常见问题

不完整（Incomplete）：缺少属性值或仅包含聚合数据，如 Occupation=""
有噪声（Noisy）：包含错误或离群点，如 Salary="-10"
不一致（Inconsistent）：编码或名称存在差异，如 Age="42" 但 Birthday="03/07/2010"（年龄与生日不吻合）；评分从 "1,2,3" 变成 "A,B,C"；重复记录之间的差异
故意伪装的缺失数据（Intentional/Disguised missing data）：例如所有人的生日都被设为 1 月 1 日

3.2 处理缺失数据（Missing Data）

缺失数据的可能原因：

设备故障
与其他记录不一致而被删除
因误解而未录入
录入时被认为不重要
未记录数据的历史变更

处理方法：

忽略该元组（Ignore the tuple）：通常用在分类任务中类别标签缺失时。但当各属性缺失比例差异较大时效果不佳
人工填充：繁琐且在大数据量下不可行
自动填充：
- 全局常量：如填入 "unknown"（可能被当作新类别）
- 属性均值：用该属性的均值填充
- 同类均值：用属于同一类别的样本在该属性上的均值填充（更智能）
- 最可能值：用贝叶斯公式或决策树等推理方法预测最可能的值

3.3 处理噪声数据（Noisy Data）

噪声：测量变量中的随机误差或方差。

噪声来源：数据采集仪器故障、数据录入问题、数据传输问题、技术限制、命名规则不一致。

处理方法：

（1）分箱（Binning）

先排序，再将数据划分到等频的箱中
然后用箱均值、箱中位数或箱边界进行平滑

例子：价格数据 4, 8, 9, 15, 21, 21, 24, 25, 26, 28, 29, 34

划分为等频箱：

Bin 1: 4, 8, 9, 15
Bin 2: 21, 21, 24, 25
Bin 3: 26, 28, 29, 34

平滑方式	Bin 1	Bin 2	Bin 3
箱均值平滑	9, 9, 9, 9	23, 23, 23, 23	29, 29, 29, 29
箱边界平滑	4, 4, 4, 15	21, 21, 25, 25	26, 26, 26, 34

箱边界平滑：每个值用最近的箱边界值替换

（2）回归（Regression）

将数据拟合到回归函数上来进行平滑

（3）聚类（Clustering）

检测并移除离群点（outliers）

（4）计算机与人工结合检查

计算机先检测可疑值，再由人工核查

3.4 数据清洗的流程

数据差异检测（Data discrepancy detection）
- 使用元数据（域、范围、依赖关系、分布）
- 检查字段重载（field overloading）
- 检查唯一性规则、连续性规则、空值规则
- 使用商业工具
数据擦洗（Data scrubbing）：用简单领域知识（如邮政编码、拼写检查）检测并修正错误
数据审计（Data auditing）：通过分析数据发现规则和关系以检测违规（如用相关性和聚类找离群点）
数据迁移与整合：使用 ETL（Extraction/Transformation/Loading）工具通过图形界面指定转换规则，将清洗后的数据加载到目标系统
迭代与交互：以上过程的整合是迭代和交互式的（如 Potter’s Wheel 系统）

四、数据集成（Data Integration）

将多个数据源的数据组合成一个一致的存储。

4.1 主要挑战

模式整合（Schema integration）：如 A.cust-id 和 B.cust-# 实际是同一个东西
实体识别问题（Entity identification）：从多个数据源中识别真实世界实体，如 Bill Clinton = William Clinton
数据值冲突：同一实体在不同数据源有不同的属性值（不同表示、不同尺度，如公制和英制）

4.2 处理冗余数据

冗余在整合多个数据库时经常发生：

对象识别问题：同一属性在不同数据库有不同名称
可推导数据：一个属性可能是另一个表中的派生属性（如年收入可由月收入推导）
可通过相关性分析和协方差分析检测冗余属性

我的思考：为什么建数据库时要建多张表而不是一张大表？因为数据来自不同的 pipeline，聚合的开销很大；更新数据时整张大表更新效率低；而且通常我们只需要一小部分数据，大表难以查找。

（1）卡方检验（χ², Chi-Square）——标称数据相关性

用于检验两个分类变量是否相关。

$$χ² = \sum \frac{(Observed - Expected)^2}{Expected}$$

χ² 值越大，变量越可能相关
与期望值差异最大的单元格对 χ² 贡献最大
相关性不代表因果性：城市中的医院数量和汽车盗窃数量相关，因为它们都与第三个变量（人口）相关

计算示例：

	Play chess	Not play chess	Sum (row)
Like science fiction	250 (90)	200 (360)	450
Not like science fiction	50 (210)	1000 (840)	1050
Sum (col.)	300	1200	1500

括号内为期望值，计算公式：$E_{ij} = \frac{count(A=a_i) \times count(B=b_j)}{N}$

$$χ² = \frac{(250-90)^2}{90} + \frac{(50-210)^2}{210} + \frac{(200-360)^2}{360} + \frac{(1000-840)^2}{840} = 507.93$$

显著性水平 α=0.05，自由度=(2-1)×(2-1)=1，查表得临界值=3.841
507.93 > 3.841，拒绝零假设，二者显著相关

（2）Pearson 相关系数——数值数据相关性

$$r_{A,B} = \frac{\sum_{i=1}^{n}(a_i - \bar{A})(b_i - \bar{B})}{(n-1)\sigma_A\sigma_B} = \frac{\sum(a_i b_i) - n\bar{A}\bar{B}}{(n-1)\sigma_A\sigma_B}$$

$r_{A,B} > 0$：正相关（A 增大时 B 也增大），值越大越强
$r_{A,B} = 0$：不相关（独立）
$r_{A,B} < 0$：负相关

相关系数本质上是标准化后的协方差，可以看作两个标准化向量的点积：
$$a’_k = \frac{a_k - \text{mean}(A)}{\text{std}(A)},\quad b’_k = \frac{b_k - \text{mean}(B)}{\text{std}(B)}$$
$$\text{corr}(A,B) = A’ \cdot B’ = \frac{\sum a’_k b’_k}{n-1}$$
这也意味着相关系数只度量线性关系——如果两个变量之间存在非线性关系（如二次关系 $y=x^2$），相关系数可能接近 0。

（3）协方差（Covariance）——数值数据

$$Cov(A,B) = \frac{\sum_{i=1}^{n}(a_i - \bar{A})(b_i - \bar{B})}{n} = \frac{\sum a_i b_i}{n} - \bar{A}\bar{B}$$

正协方差：A 和 B 都倾向于大于其期望值（同涨同跌）
负协方差：A 大于期望值时，B 倾向于小于期望值
协方差为 0 ≠ 独立：协方差只度量线性关系，协方差为 0 不代表独立。只有在额外假设下（如数据服从多元正态分布）协方差为 0 才意味着独立

协方差受尺度影响较大，两个变量 scale 差异过大时可能失真，因此更常用相关系数（归一化后的协方差）。另外注意此处分母用 n 计算的是总体协方差，而 Pearson 相关系数用 n−1（样本标准差），二者定义略有不同但关系等价。

计算示例：两只股票一周价格，A: (2, 3, 5, 4, 6)，B: (5, 8, 10, 11, 14)

E(A) = 4，E(B) = 9.6
Cov(A,B) = (2×5+3×8+5×10+4×11+6×14)/5 − 4×9.6 = 4
Cov > 0，因此两只股票同涨同跌（受同一行业趋势影响）

五、数据归约（Data Reduction）

目标：获得一个体积小得多但能产生相同（或几乎相同）分析结果的归约数据集。数据仓库可能存储 TB 级数据，直接在完整数据上运行复杂分析太耗时。

5.1 维度归约（Dimensionality Reduction）

维度灾难（Curse of Dimensionality）

维度增加时，数据变得越来越稀疏
对聚类和离群点分析至关重要的密度和距离概念变得不再有意义
可能的子空间组合呈指数增长

维度归约的好处：

避免维度灾难
消除不相关特征、减少噪声
减少数据挖掘所需的时间和空间
便于可视化

（1）小波变换（Wavelet Transform）

将信号分解到不同频率子带，适用于 n 维信号。

变换后保留对象在不同分辨率下的相对距离
使自然聚类更容易被区分
用于图像压缩
离散小波变换（DWT）：线性信号处理，多分辨率分析
压缩近似：只保留最强的小波系数的一小部分
类似离散傅立叶变换（DFT），但有更好的有损压缩，且在空间上局部化

Haar 小波分解方法：

长度 L 必须是 2 的整数次幂（必要时用 0 填充）
每轮变换有 2 个函数：平滑（smoothing）和差分（difference）
对数据对应用，得到两组长度为 L/2 的数据
递归应用直到达到期望长度

示例：S = [2, 2, 0, 2, 3, 5, 4, 4] 可变换为 [23/4, -11/4, 1/2, 0, 0, -1, -1, 0]
压缩：很多小的细节系数可被 0 替代，只保留显著的系数

小波变换的优势：

使用帽形滤波器，强调点聚集区域，抑制边界弱信息
有效移除离群点
对噪声不敏感，对输入顺序不敏感
多分辨率：在不同尺度下检测任意形状的聚类
高效：复杂度 O(N)
局限：仅适用于低维数据（小波变换基于信号处理范式，在高维空间中难以定义合适的基函数）

（2）主成分分析（PCA）

找到一个投影，捕捉数据中最大的变异量。将原始数据投影到一个小得多的空间，实现降维。

核心思想：

找到协方差矩阵的特征向量（eigenvectors），它们定义了新的空间
第一主成分 z₁ 是 X 空间中到直线的最小距离拟合
第二主成分 z₂ 是在与 z₁ 垂直的平面中到直线的最小距离拟合
主成分是正交的，按包含的信息量（方差）降序排列

PCA 步骤（给定 N 个 n 维数据向量，找到 k ≤ n 个正交向量）：

归一化输入数据：使每个属性在相同范围内
计算 k 个标准正交向量（主成分）
每个输入数据是 k 个主成分向量的线性组合
主成分按”重要性”或强度降序排列
可消除弱成分（低方差成分）来减小数据尺寸——使用最强的主成分可以重构出原始数据的良好近似

PCA 仅适用于数值数据

PCA 的代数推导（点击展开）

目标：找到方向（单位向量）$u$，使得数据在该方向上投影的方差最大。

投影方差为：

$$\text{Var}(u^T X) = u^T \Sigma u$$

其中 $\Sigma$ 为协方差矩阵。这是一个约束优化问题：最大化 $u^T \Sigma u$，约束 $u^T u = 1$。

拉格朗日乘子法：

$$L(u, \lambda) = u^T \Sigma u - \lambda(u^T u - 1)$$

对 $u$ 求导并令其为 0：

$$\frac{\partial L}{\partial u} = 2\Sigma u - 2\lambda u = 0 \quad\Rightarrow\quad \Sigma u = \lambda u$$

这意味着 $u$ 是协方差矩阵 $\Sigma$ 的特征向量，$\lambda$ 是特征值。此时投影方差 $u^T \Sigma u = \lambda$，因此应选择特征值最大的特征向量作为第一主成分。

推广到 k 个主成分：对 $\Sigma$ 做特征值分解，取前 k 大特征值对应的特征向量，即为前 k 个主成分。数据向这些特征向量张成的子空间投影，即完成降维。

重构与误差：原始数据 $\hat{x} \approx \sum_{j=1}^{k} (x^T u_j) u_j$（用前 k 个主成分重构）。重构误差 = 被丢弃的特征值之和 $\sum_{j=k+1}^{n} \lambda_j$。PCA 在所有线性降维方法中最小化该重构误差。

PCA 的最优性质：在所有可能的降维线性变换中，PCA 最小化重构误差。

应用：图像压缩 —— 原始图像用 d=1,2,4,8,… 个主成分即可重构出越来越清晰的图像。

（3）特征子集选择（Attribute Subset Selection）

冗余属性：与其他属性包含重复信息（如商品购买价格和销售税额）
不相关属性：对当前挖掘任务不包含有用信息（如学号对预测 GPA 通常不相关）

有 d 个属性时，有 $2^d$ 种可能的属性组合，无法穷举，需要用启发式搜索：

方法	说明
逐步向前选择	先选最优单属性，再在条件下选次优，依次递进
逐步向后消除	反复消除最差的属性
组合选择与消除	前两者的结合
最优分支定界	使用属性消除和回溯

（4）特征创建（Attribute Creation / Feature Generation）

创建能更有效捕捉重要信息的新属性：

特征提取：领域特定的，或将数据映射到新空间（如傅立叶变换、小波变换）
特征构造：组合特征
数据离散化

降维算法分类

分类方式	算法
无监督	LSI（截断SVD）、PCA、ICA、CCA
有监督	LDA
半监督	SDA
线性	LSI、PCA、LDA、CCA
非线性	核方法、流形学习

5.2 数量归约（Numerosity Reduction）

用更小的数据表示形式减少数据量。

（1）参数化方法

线性回归：$Y = wX + b$，用最小二乘法拟合直线。回归分析是一组技术的统称，用于对数值数据建模和分析，包含因变量（响应变量）和自变量（解释变量），用途包括预测（含时间序列预测）、统计推断、假设检验和因果关系建模
多元回归：$Y = b_0 + b_1X_1 + b_2X_2$（多个预测变量；许多非线性函数也可转换为此形式）
对数线性模型：近似离散多维概率分布 —— 基于较小的维度组合子集，估计多维空间中每个点（元组）的概率；可用于降维和数据平滑

（2）非参数化方法

直方图（Histogram）：

将数据划分为桶（bucket），存储每个桶的平均值或总和
等宽划分（equal-width）：每个桶范围相同
等频划分（equal-frequency/equal-depth）：每个桶样本数近似相同

聚类（Clustering）：

基于相似性将数据集划分为聚类，只存储聚类表示（如质心和直径）
数据聚在一起时非常有效，数据”散开”时效果差
可以有多层次聚类，存储在多维索引树结构中

抽样（Sampling）：

用一个小样本 s 代表整个数据集 N
允许挖掘算法以亚线性的复杂度运行
关键原则：选择数据的一个代表性子集

抽样类型	说明
简单随机抽样	每个项目被选中的概率相等
不放回抽样	对象被选中后从总体中移除
放回抽样	选中的对象不从总体中移除
分层抽样	将数据集分区，从每个分区按比例抽样（适用于偏斜数据）

注意：抽样可能不会减少数据库 I/O（每次读一页）。

5.3 数据立方体聚合（Data Cube Aggregation）（课堂上从略）

数据立方体的最低层（基本方体）：对单个实体的聚合数据
多级聚合进一步减小数据量
使用足以解决任务的最小表示
关于聚合信息的查询应尽可能使用数据立方体回答

5.4 数据压缩（Data Compression）

类型	特点
字符串压缩	通常无损，但无解压时操作有限
音频/视频压缩	通常有损，渐进式细化；有时可不解压整个文件就重构小信号片段
时间序列	通常不长且随时间缓慢变化

维度归约和数量归约也可视为数据压缩的形式。

六、数据变换与离散化

6.1 数据变换（Data Transformation）

将给定属性的整个值集映射为一组新的替换值。方法包括：

平滑（Smoothing）：去除噪声
特征构造（Attribute/feature construction）：从已有属性构建新属性
聚合（Aggregation）：汇总，数据立方体构建
归一化（Normalization）：缩放到更小的指定范围
离散化（Discretization）：概念分层爬升

6.2 归一化（Normalization）

（1）最小-最大归一化（Min-Max Normalization）

$$v’ = \frac{v - min_A}{max_A - min_A} \times (new_max_A - new_min_A) + new_min_A$$

示例：收入范围 $12,000~$98,000 归一化到 [0, 1]，则 $73,000 映射为 $\frac{73000-12000}{98000-12000} = 0.716$

（2）Z-Score 归一化

$$v’ = \frac{v - \mu}{\sigma}$$

其中 μ 为均值，σ 为标准差。

示例：若 μ=54,000，σ=16,000，则 $73,600 的 z-score 为 $\frac{73600-54000}{16000} = 1.225$

（3）小数定标归一化（Decimal Scaling）

$$v’ = \frac{v}{10^j}$$

其中 j 是使 $Max(|v’|) < 1$ 的最小整数。

6.3 离散化（Discretization）

三种属性类型：

标称（Nominal）：无序集合中的值，如颜色、职业
序数（Ordinal）：有序集合中的值，如军衔、学术等级
数值（Numeric）：实数

离散化：将连续属性的范围划分为区间，用区间标签替换实际数据值。

可减少数据量
有监督 vs. 无监督
自顶向下分裂 vs. 自底向上合并
可递归执行
为后续分析（如分类）做准备

常用离散化方法

方法	类型	说明
分箱（Binning）	无监督，自顶向下	等宽或等频划分
直方图分析	无监督，自顶向下	基于直方图划分
聚类分析	无监督，自顶向下或自底向上	K-means 聚类通常效果更好
决策树分析	有监督，自顶向下	用熵确定分裂点（详见第7章）
相关性分析（Chi-merge）	有监督，自底向上	χ² 值低的相邻区间（类别分布相似）合并

分箱方法对比

等宽（Equal-width）：

$W = (B - A)/N$
最直接，但离群点可能主导分布
对偏斜数据处理不好

等深（Equal-depth / Equal-frequency）：

每个区间约含相同数量的样本
数据缩放性好
处理类别属性较棘手

6.4 概念分层（Concept Hierarchy Generation）

概念分层将概念（属性值）按层级组织，通常与数据仓库中的每个维度关联。

便于数据仓库中的钻取（drilling）和上卷（rolling），以不同粒度查看数据
递归地将低级概念（如年龄的具体数值）替换为高级概念（如青年、成年、老年）

标称数据的概念分层

四种生成方式：

模式级显式指定部分/全序：如 street < city < state < country
显式数据分组：如 {Urbana, Champaign, Chicago} < Illinois
指定部分属性集：如仅指定 street < city
自动生成：通过分析不同值的数量 —— 不同值最多的属性放在层级最低层

自动生成示例：country (15个不同值) → province/state (365个) → city (3567个) → street (674,339个)
例外：weekday, month, quarter, year 这种虽然 month 只有 12 个值但放在 year 下面

七、总结

环节	核心内容
数据质量	准确性、完整性、一致性、时效性、可信度、可解释性（六维度评估）
数据清洗	处理缺失值（忽略/填充/推理）、处理噪声（分箱/回归/聚类）、清洗流程（差异检测→数据擦洗→数据审计→ETL→迭代交互）
数据集成	将多个数据源合并为一致存储，解决实体识别、冗余（χ² 检验、相关系数、协方差）、数据值冲突
数据归约	维度归约（小波变换/PCA/特征选择）、数量归约（回归/直方图/聚类/抽样）、数据压缩
数据变换与离散化	归一化（Min-Max/Z-Score/小数定标）、离散化（分箱/聚类/决策树/Chi-merge）、概念分层生成