认识数据（Getting to Know Your Data）

在进行数据挖掘之前，首先要理解数据是什么样的。本章介绍数据对象与属性类型、基本统计描述、数据可视化，以及数据相似性与相异性度量——这些是数据预处理的起点。

一、数据对象与属性类型

1.1 数据对象（Data Objects）

数据集由数据对象组成。一个数据对象代表一个实体。

场景 数据对象示例
销售数据库 顾客、商品、销售记录
医疗数据库 患者、治疗方案
大学数据库 学生、教授、课程

数据对象也被称为样本（samples）、示例（examples）、实例（instances）、数据点（data points）或元组（tuples）。

数据库的行对应数据对象，列对应属性。

1.2 数据集的类型

类型 子类型 示例
记录型（Record） 关系记录、数据矩阵、文档数据（词频向量）、事务数据 购物篮事务 TID={面包, 可乐, 牛奶}
图与网络（Graph/Network） 万维网、社交/信息网络、分子结构 网页链接关系
有序型（Ordered） 视频数据（图像序列）、时序数据、序列数据（交易序列）、基因序列 股票价格时间序列
空间/图像/多媒体 地图、图像、视频 卫星图像

1.3 结构化数据的重要特征

  1. 维度（Dimensionality）：属性数量。高维带来维度灾难——数据越来越稀疏，距离和密度概念失效
  2. 稀疏性（Sparsity）：很多属性值为 0 或空（只存储非零值有意义）
  3. 分辨率（Resolution）：数据的模式依赖于尺度——不同粒度上呈现的模式可能不同
  4. 分布（Distribution）：数据的集中趋势和分散程度

1.4 属性类型

属性（又称维度、特征、变量）是数据对象的一个数据字段，代表对象的某种特征或特性。

分类总览

1
2
3
4
5
6
7
8
9
属性
├── 分类属性（Qualitative）
│   ├── 标称（Nominal）——如：头发颜色、婚姻状况、邮编
│   ├── 二元（Binary）——标称的特殊情况，只有两个状态
│   └── 序数（Ordinal）——如：尺寸{小,中,大}、军衔、成绩等级
│
└── 数值属性（Quantitative）
    ├── 区间标度（Interval）——如：摄氏温度、日历日期（无真正零点）
    └── 比率标度（Ratio）——如：开尔文温度、长度、货币量（有真正零点）

标称属性（Nominal）

  • 值就是”名称”，代表类别、状态
  • 没有顺序关系，不能做算术运算
  • 示例：头发颜色 = {auburn, black, blond, brown, grey, red, white}
  • 只能进行 = 或 ≠ 的比较

二元属性（Binary）

  • 只有两个状态（0 和 1）
  • 对称二元属性：两个结果同等重要（如性别——男/女）
  • 非对称二元属性：结果重要性不同（如医学检测——阳性 vs 阴性）
    • 约定：将最重要的结果编码为 1（如 HIV 阳性 = 1）

序数属性（Ordinal）

  • 值之间有有意义的顺序，但相邻值之间的差异大小未知
  • 示例：Size = {small, medium, large}、成绩等级、军衔
  • 可以比较 < 和 >，但不能量化差值——“large 比 medium 大多少”这个问题本身没有意义

区间标度属性（Interval）

  • 在等大小单位的尺度上测量
  • 值有顺序，可以做加减
  • 没有真正的零点（零值不意味着”没有”）
  • 示例：摄氏/华氏温度（0°C 不是”没有温度”）、日历日期
  • 不能说”20°C 是 10°C 的两倍热”（因为零点是人定的）

比率标度属性（Ratio）

  • 具有固有的零点
  • 可以说一个值是另一个值的多少倍
  • 示例：开尔文温度（0K 是真正的”无热运动”）、长度、计数、货币量
  • 可以说”10K 是 5K 的两倍”

1.5 离散 vs. 连续属性

离散属性 连续属性
值的集合 有限或可数无限 实数
示例 邮编、职业、文档中的单词 温度、身高、体重
表示 常为整型变量 常为浮点型变量
备注 二元属性是离散属性的特例 实践中只能测量和表示为有限位小数

二、基本统计描述

动机：更好地理解数据的集中趋势、变异和散布情况。

2.1 集中趋势度量

（1）均值（Mean）

$$\bar{x} = \frac{1}{n}\sum_{i=1}^{n} x_i \qquad \mu = \frac{\sum_{i=1}^{N} x_i}{N}$$

  • n 为样本量，N 为总体量
  • 加权算术均值：$\bar{x} = \frac{\sum w_i x_i}{\sum w_i}$
  • 截尾均值（Trimmed mean）：去掉极端值后的均值

（2）中位数（Median）

  • 奇数个值：中间的那个值
  • 偶数个值：中间两个值的平均
  • 对分组数据的估计（插值法）：$median = L_1 + \left(\frac{n/2 - \sum freq_l}{freq_median}\right) \times width$

中位数不受极端值影响——当数据有严重偏斜或离群点时，中位数比均值更可靠

（3）众数（Mode）

  • 出现频率最高的值
  • 可以有单峰（unimodal）、双峰（bimodal）、三峰（trimodal）

（4）对称与偏斜

  • 对称分布：均值 ≈ 中位数 ≈ 众数
  • 正偏斜（右偏）：众数 < 中位数 < 均值（右边尾巴更长）
  • 负偏斜（左偏）：均值 < 中位数 < 众数（左边尾巴更长）

经验公式：$mean - mode \approx 3 \times (mean - median)$

2.2 数据分散度度量

（1）四分位数与箱线图

概念 说明
Q₁（第一四分位数） 第 25 百分位数
Q₃（第三四分位数） 第 75 百分位数
IQR（四分位距） IQR = Q₃ − Q₁
五数概括 min, Q₁, median, Q₃, max
离群点标准 通常，值 < Q₁−1.5×IQR 或 > Q₃+1.5×IQR

箱线图（Boxplot）：

  • 箱体的两端是 Q₁ 和 Q₃（箱高 = IQR）
  • 箱内的一条线标记中位数
  • 须（whiskers）：从箱体延伸到最小值和最大值（不含离群点）
  • 离群点：超出阈值线的点，单独绘制

（2）方差与标准差

方差（样本 s²，总体 σ²）：

$$s^2 = \frac{1}{n-1}\sum_{i=1}^{n}(x_i - \bar{x})^2 = \frac{1}{n-1}\left[\sum x_i^2 - \frac{1}{n}(\sum x_i)^2\right]$$

$$\sigma^2 = \frac{1}{N}\sum_{i=1}^{N}(x_i - \mu)^2 = \frac{1}{N}\sum x_i^2 - \mu^2$$

标准差 s（或 σ）：方差的平方根，与原数据单位一致，更直观。

第二个形式是代数等价的计算形式，只需一次扫描即可计算（不需先求均值）。

2.3 正态分布的性质

  • 从 μ−σ 到 μ+σ：包含约 68% 的测量值
  • 从 μ−2σ 到 μ+2σ：包含约 95% 的测量值
  • 从 μ−3σ 到 μ+3σ：包含约 99.7% 的测量值

2.4 基本统计描述的图形展示

图形 说明
箱线图 五数概括的可视化
直方图（Histogram） x 轴是值，y 轴是频率。注意：用面积（而非高度）表示值——当区间宽度不均时这是关键区别
分位数图（Quantile plot） 每个值 xᵢ 与 fᵢ 配对，表示约 100 fᵢ% 的数据 ≤ xᵢ
Q-Q 图（Quantile-Quantile plot） 将一个单变量分布的分位数与另一个分布的对应分位数画在一起，用于比较两个分布（如分支 1 和分支 2 的商品单价）
散点图（Scatter plot） 每对值作为平面上的坐标点绘制，用于观察二元数据的聚类、离群点和相关性

直方图 vs. 箱线图：两个不同的分布可能有相同的五数概括（min, Q₁, median, Q₃, max），即相同的箱线图，但直方图能揭示它们的数据分布差异。

三、数据可视化

为什么做可视化？

  • 通过将数据映射到图形元素来洞察信息空间
  • 提供大数据集的定性概览
  • 搜索模式、趋势、结构、不规则性和数据间的关系
  • 帮助发现有趣区域和适合作进一步定量分析的参数
  • 为计算机表示提供视觉验证

3.1 可视化方法分类

类别 方法 说明
像素导向 像素窗口、圆环分段 m 维数据创建 m 个窗口，每条记录的 m 个维度值映射到 m 个像素，颜色反映值大小
几何投影 散点图矩阵、Landscapes、平行坐标、投影追踪 数据的几何变换与投影的可视化
图标导向 Chernoff 脸、Stick Figures 将数据值可视化为图标的特征
层次化 Dimensional Stacking、Worlds-within-Worlds、Tree-Map、Cone Trees、InfoCube 使用层次划分将数据划分为子空间进行可视化
复杂数据 标签云、社交网络图 可视化非数值数据（文本、关系）

3.2 各方法简述

散点图矩阵：k 维数据的散点图矩阵（共 k²/2−k 个散点图），用于观察属性两两之间的关系。

平行坐标（Parallel Coordinates）：n 根等距平行轴，每根轴对应一个属性（缩放到 [min, max] 范围），每条数据对应一根穿越所有轴的折线。

Chernoff 脸（Chernoff Faces）：用脸部特征表示变量——如眉毛倾斜 = x、眼睛大小 = y、鼻子长度 = z……利用人类对面部差异的敏感性。

Stick Figures（棍形图）：用 5 片棍形（1 个身体 + 4 个肢体），两个属性映射到坐标轴，其余映射到肢体角度/长度。

Dimensional Stacking：将 n 维属性空间在 2D 子空间中分区并”堆叠”。适用于低基数序数属性，但难以显示超过 9 个维度。

Worlds-within-Worlds（世界中世界）：最重要的参数放在最内层世界，其他参数固定为常量，绘制其他维度的世界。

Tree-Map：用层次划分屏幕区域来显示层次数据——x 和 y 维度根据属性值交替划分。

InfoCube：3D 技术，层次信息显示为嵌套的半透明立方体——最外层对应顶层数据，子节点对应内部更小的立方体。

四、数据相似性与相异性度量

4.1 基本概念

  • 相似性（Similarity）：数值度量，表示两个数据对象有多相似。值越高越相似，通常在 [0, 1] 范围内
  • 相异性（Dissimilarity）：数值度量，表示两个数据对象有多不同。值越低越相似，最小值通常为 0
  • 邻近性（Proximity）：相似性或相异性的统称

4.2 数据矩阵与相异性矩阵

数据矩阵 相异性矩阵
结构 n 个数据点 × p 个维度 n × n 三角矩阵
模式 双模式 单模式
存储 原始数据值 对象两两之间的距离

4.3 各类属性的邻近性度量

（1）标称属性

简单匹配：$d(i,j) = \frac{p - m}{p}$，其中 m 为匹配的属性数，p 为总属性数。

也可为每个标称状态创建新的二元属性，然后使用二元属性的度量方法。

（2）二元属性

列联表：

对象 j: 1 对象 j: 0 sum
对象 i: 1 q r q+r
对象 i: 0 s t s+t
sum q+s r+t p
  • 对称二元变量的距离：$d(i,j) = \frac{r + s}{q + r + s + t}$
  • 非对称二元变量的距离：$d(i,j) = \frac{r + s}{q + r + s}$（忽略 t，即两个都为 0 没有意义）
  • Jaccard 系数（非对称二元变量的相似度）：$sim(i,j) = \frac{q}{q + r + s}$

计算示例：

Name Gender Fever Cough Test-1 Test-2 Test-3 Test-4
Jack M Y P N N N N
Mary F Y P N P N N
Jim M Y P N N N N
  • Gender 是对称属性，其余是非对称二元（Y/P=1, N=0）
  • d(Jack, Mary) = (0+1)/(2+0+1) = 0.33
  • d(Jack, Jim) = (1+1)/(1+1+1) = 0.67
  • d(Jim, Mary) = (1+2)/(1+1+2) = 0.75

（3）数值属性

数据的标准化：

Z-score 标准化：$z = \frac{x - \mu}{\sigma}$

或使用均值绝对偏差（Mean Absolute Deviation，更鲁棒）：

$$s_f = \frac{1}{n}(|x_{1f} - m_f| + |x_{2f} - m_f| + … + |x_{nf} - m_f|), \quad m_f = \frac{1}{n}(x_{1f} + x_{2f} + … + x_{nf})$$

$$z_{if} = \frac{x_{if} - m_f}{s_f}$$

闵可夫斯基距离（Minkowski Distance）：

$$d(i,j) = \sqrt[h]{|x_{i1} - x_{j1}|^h + |x_{i2} - x_{j2}|^h + … + |x_{ip} - x_{jp}|^h}$$

其中 h 为阶数。该距离满足度量三性质：正定性、对称性、三角不等式。

h 值 名称 含义
h = 1 曼哈顿距离（L₁ 范数） “城市街区”距离
h = 2 欧几里得距离（L₂ 范数） 直线距离（最常用）
h → ∞ 上确界距离（L_max / L_∞） 各分量差的最大值

计算示例：x₁=(1,2), x₂=(3,5), x₃=(2,0), x₄=(4,5)

  • L₁（曼哈顿）: d(x₁,x₂) = |3-1|+|5-2| = 5
  • L₂（欧几里得）: d(x₁,x₂) = √((3-1)²+(5-2)²) = 3.61
  • L_∞（上确界）: d(x₁,x₂) = max(|3-1|, |5-2|) = 3

（4）序数属性

  1. 将每个属性的值用其秩（rank）替换：$r_{if} \in {1,…,M_f}$
  2. 映射到 [0, 1]：$z_{if} = \frac{r_{if} - 1}{M_f - 1}$
  3. 将 $z_{if}$ 当作区间标度属性做距离计算

（5）混合类型属性

数据库中可能同时包含所有属性类型。使用加权公式组合：

$$d(i,j) = \frac{\sum_{f=1}^{p} \delta_{ij}^{(f)} d_{ij}^{(f)}}{\sum_{f=1}^{p} \delta_{ij}^{(f)}}$$

  • 若 $x_{if}$ 或 $x_{jf}$ 缺失，或 $x_{if}=x_{jf}=0$ 且 f 是非对称二元 → $\delta_{ij}^{(f)} = 0$
  • 否则 $\delta_{ij}^{(f)} = 1$
  • 标称/二元：$d_{ij}^{(f)} = 0$ if $x_{if}=x_{jf}$，否则 1
  • 数值：归一化距离
  • 序数：先求秩再标准化，当区间标度处理

4.4 余弦相似度（Cosine Similarity）

文档可表示为数千个属性——每个属性记录特定单词或短语的频率（词频向量）。适用于信息检索、生物分类、基因特征映射等。

$$\cos(d_1, d_2) = \frac{d_1 \cdot d_2}{||d_1|| \cdot ||d_2||}$$

其中 $\cdot$ 表示向量点积，$||d||$ 表示向量长度。

余弦相似度关注的是方向而非大小——两个文档中的词频按相同比例增加时，余弦相似度不变。

计算示例：

  • d₁ = (5, 0, 3, 0, 2, 0, 0, 2, 0, 0)，||d₁|| = 6.48
  • d₂ = (3, 0, 2, 0, 1, 1, 0, 1, 0, 1)，||d₂|| = 4.12
  • d₁·d₂ = 5×3 + 3×2 + 2×1 + 2×1 = 25
  • cos(d₁, d₂) = 25 / (6.48 × 4.12) = 0.94 → 高度相似

五、本章总结

主题 核心内容
数据对象与属性 数据对象 = 实体；属性六种类型（标称/二元/序数/区间/比率）、离散 vs. 连续；数据集三大类（记录型/图与网络/有序型）
统计描述 集中趋势：均值/中位数/众数/中列数；分散度：方差/标准差/IQR/五数概括；箱线图/直方图/分位数图/Q-Q 图/散点图
数据可视化 像素导向/几何投影/图标导向/层次化可视化；平行坐标/Chernoff脸/Tree-Map/Dimensional Stacking 等
相似性与相异性 各属性类型的度量方法；闵可夫斯基距离（曼哈顿/欧几里得/上确界）；Jaccard 系数；余弦相似度；混合类型加权公式

认识数据是数据预处理的第一步。以上步骤帮助我们理解数据的基本结构和特征，为后续的清洗、集成、归约和变换奠定基础。

数据预处理（Data Preprocessing）

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

一、数据质量（Data Quality）

数据质量的六个维度：

  1. 准确性（Accuracy）：数据是否正确
  2. 完整性（Completeness）：数据是否有缺失
  3. 一致性（Consistency）：同一数据在不同地方是否一致。例如用户的余额在不同的缓存中不会即时更新（因为代价太大），因此从不同库调取同一时刻的用户余额可能得到不同的值
  4. 时效性（Timeliness）：数据是否得到及时更新
  5. 可信度（Believability）：数据在多大程度上可以被信任
  6. 可解释性（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）

缺失数据的可能原因：

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

处理方法：

  1. 忽略该元组（Ignore the tuple）：通常用在分类任务中类别标签缺失时。但当各属性缺失比例差异较大时效果不佳
  2. 人工填充：繁琐且在大数据量下不可行
  3. 自动填充：
    • 全局常量：如填入 "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 数据清洗的流程

  1. 数据差异检测（Data discrepancy detection）

    • 使用元数据（域、范围、依赖关系、分布）
    • 检查字段重载（field overloading）
    • 检查唯一性规则、连续性规则、空值规则
    • 使用商业工具

  2. 数据擦洗（Data scrubbing）：用简单领域知识（如邮政编码、拼写检查）检测并修正错误

  3. 数据审计（Data auditing）：通过分析数据发现规则和关系以检测违规（如用相关性和聚类找离群点）

  4. 数据迁移与整合：使用 ETL（Extraction/Transformation/Loading）工具通过图形界面指定转换规则，将清洗后的数据加载到目标系统

  5. 迭代与交互：以上过程的整合是迭代和交互式的（如 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 个正交向量）：

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

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），以不同粒度查看数据
  • 递归地将低级概念（如年龄的具体数值）替换为高级概念（如青年、成年、老年）

标称数据的概念分层

四种生成方式：

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

自动生成示例：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）、概念分层生成

分类：基本概念（Classification: Basic Concepts）

一、分类概述

1.1 监督学习 vs. 无监督学习

监督学习（分类） 无监督学习（聚类）
训练数据 带有类别标签 无类别标签
目标 基于训练集对新数据分类 发现数据中自然存在的类或簇

1.2 分类 vs. 数值预测

  • 分类（Classification）：预测离散/标称的类别标签。基于训练集构建模型，用于对新数据分类
  • 数值预测（Numeric Prediction）：建模连续值函数，预测未知或缺失的数值

典型应用：

  • 信用/贷款审批
  • 医疗诊断（肿瘤是恶性还是良性）
  • 欺诈检测（交易是否欺诈）
  • 网页归类

1.3 分类的两步过程

第一步：模型构建（Model Construction）

  • 每条元组/样本假定属于一个预定义的类（由类别标签属性决定）
  • 用于模型构建的元组集合称为训练集（training set）
  • 模型表示为：分类规则、决策树、或数学公式

第二步：模型使用（Model Usage）

  • 用**测试集（test set）**估计模型准确率 —— 将测试样本的真实标签与模型分类结果比较
  • 准确率 = 被正确分类的测试样本百分比
  • 测试集必须独立于训练集（否则导致过拟合）
  • 如果准确率可接受，用模型对新数据分类

注意：如果测试集用于选择模型，则它被称为验证集（validation set）

模型构建示例：

NAME RANK YEARS TENURED
Mike Assistant Prof 3 no
Mary Assistant Prof 7 yes
Bill Professor 2 yes
Jim Associate Prof 7 yes
Dave Assistant Prof 6 no
Anne Associate Prof 3 no

→ 分类器（模型）：IF rank = 'professor' OR years > 6 THEN tenured = 'yes'

二、决策树归纳（Decision Tree Induction）

2.1 决策树示例

以 Quinlan’s ID3 的经典数据集为例（预测 buys_computer）：

1
2
3
4
5
6
7
8
9
          age?
    ┌──────┼──────┐
   <=30  31..40  >40
    │       │      │
 student?  yes  credit_rating?
 ┌──┴──┐       ┌────┴────┐
no    yes   excellent   fair
 │     │       │        │
 no   yes     no       yes

2.2 决策树基本算法（贪心算法）

  • 以自顶向下的递归分治方式构建
  • 初始时所有训练样本都在根节点
  • 属性是分类的（连续值属性需先离散化）
  • 基于选定的属性递归划分样本
  • 测试属性基于启发式或统计度量（如信息增益）选择

停止划分的条件：

  1. 给定节点的所有样本属于同一类
  2. 没有剩余属性可用来进一步划分 → 多数投票决定叶节点类别
  3. 没有剩余样本

2.3 属性选择度量

（1）信息增益（Information Gain, ID3/C4.5）

核心思想：选择具有最高信息增益的属性。

熵（Entropy）：度量数据的不确定性。

$$Info(D) = -\sum_{i=1}^{m} p_i \log_2(p_i)$$

其中 $p_i$ 是 D 中属于类 $C_i$ 的元组的概率，用 $|C_{i,D}|/|D|$ 估计。

使用属性 A 划分后的信息量（属性 A 将 D 划分为 v 个分区）：

$$Info_A(D) = \sum_{j=1}^{v} \frac{|D_j|}{|D|} \times Info(D_j)$$

信息增益：

$$Gain(A) = Info(D) - Info_A(D)$$

信息增益 = 划分前的信息量 − 划分后还需要的信息量，即”知道了 A 之后，不确定度减少了多少”

完整计算示例：以下数据集有 14 条记录（9 yes, 5 no）

age income student credit_rating buys_computer
<=30 high no fair no
<=30 high no excellent no
31..40 high no fair yes
>40 medium no fair yes
>40 low yes fair yes
>40 low yes excellent no
31..40 low yes excellent yes
<=30 medium no fair no
<=30 low yes fair yes
>40 medium yes fair yes
<=30 medium yes excellent yes
31..40 medium no excellent yes
31..40 high yes fair yes
>40 medium no excellent no

  1. 计算根节点信息量：$Info(D) = I(9,5) = -\frac{9}{14}\log_2\frac{9}{14} - \frac{5}{14}\log_2\frac{5}{14} = 0.940$

  2. 计算 age 的信息增益：

    • age <= 30 (5条: 2 yes, 3 no): $I(2,3) = 0.971$
    • age 31..40 (4条: 4 yes, 0 no): $I(4,0) = 0$
    • age > 40 (5条: 3 yes, 2 no): $I(3,2) = 0.971$
    • $Info_{age}(D) = \frac{5}{14} \times 0.971 + \frac{4}{14} \times 0 + \frac{5}{14} \times 0.971 = 0.694$
    • Gain(age) = 0.940 − 0.694 = 0.246

  3. 同理计算其他属性：

    • Gain(income) = 0.029
    • Gain(student) = 0.151
    • Gain(credit_rating) = 0.048

→ age 信息增益最高，选为根节点分裂属性

（2）连续值属性的信息增益

对连续值属性 A：

  1. 将 A 的值按升序排列
  2. 每一对相邻值的中点 $(a_i + a_{i+1})/2$ 作为一个可能的分裂点
  3. 选择使期望信息需求最小的点作为 split-point
  4. 分裂为 $D_1$ (A ≤ split-point) 和 $D_2$ (A > split-point)

（3）增益率（Gain Ratio, C4.5）

动机：信息增益偏向于取值多的属性。

$$SplitInfo_A(D) = -\sum_{j=1}^{v} \frac{|D_j|}{|D|} \times \log_2\left(\frac{|D_j|}{|D|}\right)$$

$$GainRatio(A) = \frac{Gain(A)}{SplitInfo(A)}$$

SplitInfo 相当于假定 A 按当前的划分方式被分成几类，这种分类方式本身能有多少”信息增益”。如果某个属性取值极多，SplitInfo 就会很大，从而惩罚这种偏好。

示例：gain_ratio(income) = 0.029 / 1.557 = 0.019

Gain Ratio 的陷阱与对策：

  • 靠近叶子节点时，若某 $D_j$ 相对 D 非常小，SplitInfo 会变得非常小 → GainRatio 异常大
  • 例：-999/1000·log(999/1000) - 1/1000·log(1/1000) = 0.0034（极小）
  • 对策：增加约束——选取的属性信息增益必须至少与所有考察属性的平均增益一样大

（4）基尼指数（Gini Index, CART）

$$gini(D) = 1 - \sum_{j=1}^{n} p_j^2$$

其中 $p_j$ 是类 j 在 D 中的相对频率。

若 D 基于属性 A 分裂为 $D_1$ 和 $D_2$：

$$gini_A(D) = \frac{|D_1|}{|D|}gini(D_1) + \frac{|D_2|}{|D|}gini(D_2)$$

杂质减少量：$\Delta_{gini}(A) = gini(D) - gini_A(D)$

选择使 $gini_A(D)$ 最小（即杂质减少最大）的属性分裂节点。

示例：D 有 9 yes, 5 no。若 income 分区 D₁={low, medium}(10条), D₂={high}(4条)，计算得 Gini 最小，选此分裂。

（5）三种度量比较

度量 特点
信息增益 偏向多值属性
增益率 倾向不平衡分裂（一个分区远小于其他分区）
基尼指数 偏向多值属性；类别数大时有困难；倾向产生等大小且纯度高的分区

其他度量：

  • CHAID：基于 χ² 独立性检验
  • C-SEP：在某些情况下优于信息增益和 Gini
  • G-statistic：近似 χ² 分布
  • MDL（最小描述长度）：最好的树需要最少的位数来编码树本身 + 编码异常
  • 多变量分裂（CART）：基于属性的线性组合

结论：大多数度量给出好结果，没有一种显著优于其他。

2.4 过拟合与剪枝

过拟合（Overfitting）：生成的树对训练数据拟合过度

  • 分支太多，部分可能反映噪声或离群点导致的异常
  • 对未见样本准确率差

两种对策：

方法 做法 难点
预剪枝（Prepruning） 提前终止树构建——如果分裂导致优度度量低于阈值，就不分裂 阈值的选取
后剪枝（Postpruning） 先构建”完全生长”的树，再移除分支，得到一系列逐步剪枝的树 需要用不同于训练数据的数据集决定”最佳剪枝树”

2.5 决策树增强

  1. 连续值属性：动态定义新的离散值属性，将连续属性值划分为离散区间
  2. 缺失值处理：
    • 赋予该属性最常见的值
    • 为每个可能值赋予一个概率
  3. 属性构造：基于已有属性创建新属性（减少碎片化、重复和复制）

2.6 大规模数据库中的分类

决策树为什么流行？

  • 学习速度相对较快
  • 可转换为简单易懂的分类规则
  • 可用 SQL 查询访问数据库
  • 分类准确率与其他方法相当

RainForest（VLDB’98）：

  • 将可扩展性方面与决定树质量的判定标准分离
  • 构建 AVC-list（Attribute, Value, Class_label）
    • AVC-set（属性 X 的）：训练数据集在属性 X 和类别标签上的投影，聚合各类别的计数
    • AVC-group（节点 n 的）：节点 n 处所有预测属性的 AVC-set 的集合

BOAT：使用 bootstrapping 创建多个小样本子集，每个生成一棵树，然后整合为一棵新树 T’（只需两次数据库扫描，增量算法）。

三、贝叶斯分类方法（Bayes Classification Methods）

3.1 为什么用贝叶斯分类？

  • 概率预测：预测类成员概率
  • 理论基础：基于贝叶斯定理
  • 性能：简单的朴素贝叶斯分类器与决策树和神经网络性能相当
  • 增量学习：每个训练样本可增量地更新假设概率——先验知识可与观察数据结合
  • 标准：即使贝叶斯方法计算困难，也可作为最优决策的标准，用于衡量其他方法

3.2 贝叶斯定理

全概率公式：$P(B) = \sum_{i=1}^{M} P(B|A_i)P(A_i)$

贝叶斯定理：

$$P(H|X) = \frac{P(X|H)P(H)}{P(X)}$$

  • $P(H|X)$：后验概率（posterior）——给定数据 X，假设 H 成立的概率
  • $P(H)$：先验概率（prior）——H 成立的初始概率
  • $P(X|H)$：似然（likelihood）——在假设 H 成立下观察到 X 的概率
  • $P(X)$：证据（evidence）——观察到 X 的概率

直观理解：后验 = 似然 × 先验 / 证据

最优贝叶斯决策规则：

对于观测 X：

  • 若 $P(c_1|x) > P(c_2|x)$ → 真实类别为 $c_1$
  • 若 $P(c_1|x) < P(c_2|x)$ → 真实类别为 $c_2$

3.3 朴素贝叶斯分类器（Naïve Bayes Classifier）

核心简化假设：属性之间条件独立（给定类别时，属性间无依赖关系）：

$$P(X|C_i) = \prod_{k=1}^{n} P(x_k|C_i) = P(x_1|C_i) \times P(x_2|C_i) \times … \times P(x_n|C_i)$$

分类目标：最大化 $P(C_i|X)$。由于 P(X) 对所有类相同，只需最大化 $P(X|C_i)P(C_i)$。

概率估计：

  • 分类属性：$P(x_k|C_i) = \frac{C_i\text{ 类中 } A_k = x_k \text{ 的元组数}}{|C_{i,D}|}$
  • 连续属性：通常基于高斯分布：$g(x, \mu, \sigma) = \frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{(x-\mu)^2}{2\sigma^2}}$，其中 $\mu, \sigma$ 为 $C_i$ 类中该属性的均值和标准差

计算示例：

数据：X = (age <= 30, income = medium, student = yes, credit_rating = fair)

概率 buys_computer = yes buys_computer = no
P(Cᵢ) 9/14 = 0.643 5/14 = 0.357
P(age<=30|Cᵢ) 2/9 = 0.222 3/5 = 0.6
P(income=medium|Cᵢ) 4/9 = 0.444 2/5 = 0.4
P(student=yes|Cᵢ) 6/9 = 0.667 1/5 = 0.2
P(credit=fair|Cᵢ) 6/9 = 0.667 2/5 = 0.4
P(X|Cᵢ) 0.222×0.444×0.667×0.667 = 0.044 0.6×0.4×0.2×0.4 = 0.019
P(X|Cᵢ)×P(Cᵢ) 0.044 × 0.643 = 0.028 0.019 × 0.357 = 0.007

→ 0.028 > 0.007，X 属于 buys_computer = yes

3.4 零概率问题与拉普拉斯校正

问题：如果某个条件概率为 0，整个 $P(X|C_i)$ 就会变为 0。

拉普拉斯校正（Laplacian Correction）：每个计数 +1

例：1000 条记录中 income=low (0), medium (990), high (10)
校正后：Prob(low) = 1/1003, Prob(medium) = 991/1003, Prob(high) = 11/1003
校正后的概率接近未校正值

3.5 朴素贝叶斯评价

优点：易于实现，大多数情况下结果良好
缺点：类条件独立假设在实践中通常不成立，导致精度损失（如医院数据中：年龄、家族史、症状之间存在依赖关系）
解决依赖关系的方法：贝叶斯信念网络（Bayesian Belief Networks，第 9 章）

四、基于规则的分类（Rule-Based Classification）

4.1 IF-THEN 规则

形式：IF age = youth AND student = yes THEN buys_computer = yes

  • 规则前件（antecedent/precondition） vs 规则后件（consequent）
  • 规则的评估：
    • $coverage(R) = n_{covers} / |D|$ （覆盖率）
    • $accuracy(R) = n_{correct} / n_{covers}$ （准确率）

规则冲突消解：当多条规则被触发时：

  1. 规模排序（Size ordering）：最”严格”的规则（最多属性测试）优先
  2. 类别排序（Class-based ordering）：按各类别的普遍性或误分类代价降序
  3. 规则排序（Rule-based ordering / decision list）：规则按某种质量度量或专家知识排优先级

4.2 从决策树提取规则

  • 一棵大树的每个从根到叶的路径 → 一条规则（路径上的属性-值对形成合取，叶子形成类别预测）
  • 提取出的规则互斥且穷举

示例（从 buys_computer 决策树提取）：

1
2
3
4
5
IF age = young AND student = no THEN buys_computer = no
IF age = young AND student = yes THEN buys_computer = yes
IF age = mid-age THEN buys_computer = yes
IF age = old AND credit_rating = excellent THEN buys_computer = no
IF age = old AND credit_rating = fair THEN buys_computer = yes

规则比大树更容易理解

4.3 顺序覆盖方法（Sequential Covering）

直接从训练数据中提取规则（典型算法：FOIL, AQ, CN2, RIPPER）。

步骤：

  1. 每次学习一条规则
  2. 每学完一条规则，移除被该规则覆盖的元组
  3. 在剩余元组上重复，直到终止条件（如不再有训练样本，或规则质量低于阈值）

与决策树归纳的区别：规则是逐一学习的，而非同时学习一组规则

4.4 学习单条规则（Learn-One-Rule）

  • 从最通用的规则开始（条件为空）
  • 贪心深度优先策略添加新属性
  • 选择最能提升规则的谓词

FOIL_Gain（用于 FOIL & RIPPER）：

$$FOIL_Gain = pos’ \times \left(\log_2\frac{pos’}{pos’ + neg’} - \log_2\frac{pos}{pos + neg}\right)$$

  • 倾向准确率高且覆盖更多正例的规则
  • pos/neg 是扩展前规则覆盖的正/负元组数，pos’/neg’ 是扩展后的

规则剪枝：$FOIL_Prune(R) = \frac{pos - neg}{pos + neg}$（在独立测试集上评估，若剪枝后更高则剪枝）

五、模型评估与选择（Model Evaluation and Selection）

5.1 混淆矩阵（Confusion Matrix）

真实类 \ 预测类 C₁ ¬C₁
C₁ TP (True Positives) FN (False Negatives)
¬C₁ FP (False Positives) TN (True Negatives)

示例：

真实 \ 预测 buy_computer = yes buy_computer = no Total
buy = yes 6954 46 7000
buy = no 412 2588 3000
Total 7366 2634 10000

5.2 评估指标

指标 公式 含义
准确率（Accuracy） (TP+TN)/All 被正确分类的样本百分比
错误率（Error Rate） (FP+FN)/All = 1-Accuracy 被错误分类的百分比
灵敏度/召回率（Sensitivity/Recall） TP/P 真实正例中被正确识别的比例
特异度（Specificity） TN/N 真实负例中被正确识别的比例
精确率（Precision） TP/(TP+FP) 被分类为正例的样本中真正例的比例
F₁ 分数 $2 \times \frac{Precision \times Recall}{Precision + Recall}$ 精确率和召回率的调和平均
F_β 分数 加权组合 β 倍权重给 recall

精确率衡量”精确性”（exactness）——预测的”正”中有多少是真的正；
召回率衡量”完备性”（completeness）——真正的”正”中有多少被找到了

类不平衡问题示例（cancer 分类）：

真实 \ 预测 cancer = yes cancer = no Total Recognition(%)
cancer = yes 90 210 300 30.00 (sensitivity)
cancer = no 140 9560 9700 98.56 (specificity)
Total 230 9770 10000 96.40 (accuracy)
  • Precision = 90/230 = 39.13%
  • Recall = 90/300 = 30.00%

准确率 96.4% 看起来很高，但 recall 仅 30%——大部分癌症患者被漏诊了！这就是为什么类不平衡时只看准确率会误导。

5.3 评估方法

Holdout 方法

  • 数据随机分为独立的训练集（如 2/3）和测试集（如 1/3）
  • Random subsampling：重复 k 次 holdout，取平均准确率

交叉验证（Cross-Validation）

  • k 折交叉验证（k = 10 最常用）：
    1. 将数据随机分为 k 个互斥的、大小近似相等的子集
    2. 第 i 次迭代：$D_i$ 做测试集，其余做训练集
  • 留一法（Leave-one-out）：k = 元组数（适用于小数据集）
  • 分层交叉验证（Stratified cross-validation）：每折中类分布与初始数据大致相同

Bootstrap

  • 适用于小数据集
  • 有放回地从 d 条元组中抽样 d 次 → 训练集
  • 未被抽中的元组 → 测试集（约 36.8%，因为 $(1-1/d)^d \approx e^{-1} = 0.368$）
  • .632 bootstrap是最常用的方法
  • 重复 k 次，取整体准确率

5.4 模型比较：置信区间与 t 检验

问题：两个分类器 M₁ 和 M₂，哪一个更好？差异是否仅由偶然导致？

步骤：

  1. 进行 10 折交叉验证，得到平均错误率
  2. 假设样本服从自由度为 k-1 的 t 分布
  3. 使用 t 检验（Student’s t-test）
  4. 零假设：M₁ 和 M₂ 相同
  5. 若可拒绝零假设，则二者差异统计显著

配对 t 检验（只有一个测试集可用时）：

  • 每轮交叉验证使用相同的划分计算 err(M₁) 和 err(M₂)
  • 计算 t 统计量，自由度 k-1

判断方法：

  • 选择显著性水平（如 sig = 0.05）
  • 查 t 分布表，找自由度 k-1 对应的 t 值（置信限 z = sig/2 = 0.025）
  • 若 t > z 或 t < -z → 拒绝零假设 → 显著差异
  • 否则 → 差异可能由偶然造成

5.5 ROC 曲线

  • ROC（Receiver Operating Characteristics）曲线：可视化比较分类模型
  • 起源于信号检测理论
  • 纵轴：真正率（True Positive Rate）
  • 横轴：假正率（False Positive Rate）
  • 对角线：随机猜测（AUC = 0.5）
  • AUC（Area Under Curve）：完美模型 AUC = 1.0，越接近 0.5 越不准确
  • 展示了 TPR 和 FPR 之间的权衡

5.6 影响模型选择的因素

  • 准确率：分类器准确率
  • 速度：模型构建时间 + 使用时间
  • 鲁棒性（Robustness）：处理噪声和缺失值
  • 可扩展性（Scalability）：在磁盘数据库上的效率
  • 可解释性（Interpretability）：模型提供的理解和洞察
  • 其他：规则优度（如决策树大小、规则紧凑性）

六、集成方法（Ensemble Methods）

核心思想：使用多个模型的组合来提高准确率。组合 k 个模型 M₁, M₂, …, Mₖ，创建改进的模型 M*。

6.1 Bagging (Bootstrap Aggregation)

类比：基于多个医生的多数投票做诊断。

训练：

  • 从 D（d 条元组）中有放回抽样得到 $D_i$（d 条）
  • 对每个 $D_i$ 学习分类器 $M_i$

分类：

  • 每个 $M_i$ 投票
  • M* 取票数最多的类（分类）；取平均值（数值预测）

特点：

  • 通常比单一分类器显著更好
  • 对噪声数据更鲁棒
  • 可证明提高预测准确率

6.2 Boosting

类比：咨询多位医生，根据各自过去的诊断准确率加权投票。

工作原理：

  1. 权重分配给每个训练元组
  2. 迭代学习 k 个分类器
  3. 学完 $M_i$ 后更新权重 → 让 $M_{i+1}$ 更关注之前被误分类的元组
  4. M* 组合所有分类器的投票，每个分类器的投票权重是其准确率的函数

Adaboost 算法细节

  • 初始：所有权重 = 1/d
  • 每轮 i：
    1. 从 D 中有放回抽样形成 $D_i$（基于权重）
    2. 从 $D_i$ 学习 $M_i$
    3. 用 $D_i$ 计算 $M_i$ 的错误率：$error(M_i) = \sum_j w_j \times err(X_j)$
    4. 若元组被误分类 → 权重增加；否则权重减少
  • 分类器 $M_i$ 的投票权重：$\log\frac{1-error(M_i)}{error(M_i)}$

Bagging vs. Boosting：

  • Boosting 通常有更高准确率
  • 但 Boosting 有过拟合的风险（过度关注被误分类的数据）

6.3 随机森林（Random Forest）

  • 每个分类器是决策树，在每个节点随机选择属性的子集来确定分裂
  • 分类时：每棵树投票，返回最流行的类

两种构建方法：

方法 做法
Forest-RI（Random Input） 每个节点随机选 F 个属性作为分裂候选（CART 方法）
Forest-RC（Random Combinations） 创建现有属性的线性组合作为新特征（减少树之间的相关性）

特点：

  • 准确率与 Adaboost 相当，但对错误和离群点更鲁棒
  • 对每个节点考虑的属性数不敏感
  • 比 bagging/boosting 更快

6.4 类不平衡数据集分类

问题：正例稀有但负例众多（如医疗诊断、欺诈检测等）。传统方法假设平衡分布且错误代价相等，不适用。

典型方法（二分类）：

方法 说明
过采样（Oversampling） 重新采样正例数据
欠采样（Under-sampling） 随机减少负例数据
阈值移动（Threshold-moving） 移动决策阈值 t，使稀有类更易被分类（减少代价高昂的假阴性）
集成方法 组合多个分类器

多分类问题的类不平衡仍然很难解决

七、本章总结

主题 核心内容
分类概述 监督学习 vs. 无监督学习、分类 vs. 数值预测、两步过程（模型构建 + 模型使用）
决策树 ID3（信息增益）→ C4.5（增益率）→ CART（基尼指数）；连续值属性处理；过拟合与剪枝（预剪枝/后剪枝）；可扩展算法（RainForest、BOAT）
贝叶斯分类 贝叶斯定理；朴素贝叶斯（条件独立假设）；拉普拉斯校正（零概率问题）；贝叶斯信念网络
基于规则的分类 IF-THEN 规则；顺序覆盖算法（FOIL、RIPPER）；FOIL_Gain 度量；冲突消解
模型评估与选择 混淆矩阵；TP/FP/TN/FN；Accuracy/Recall/Precision/F₁；Holdout/交叉验证/Bootstrap；t 检验（统计显著性）；ROC 曲线与 AUC
集成方法 Bagging（bootstrap + 投票）；Boosting/Adaboost（加权投票 + 误分类关注）；随机森林（随机特征选择）；类不平衡处理（过采样/欠采样/阈值移动）

没有哪一种分类方法在所有数据集上都优于其他——需要综合考量准确率、训练时间、鲁棒性、可伸缩性和可解释性。