第9章 数据挖掘

学习目标

1. 说明数据挖掘与知识发现的关系，以及数据挖掘相对于传统数据分析的特点。
2. 识别描述型任务和预测型任务，列举分类、预测、聚类、关联分析和异常点分析的典型应用。
3. 计算信息熵、条件熵、信息增益、信息增益比和基尼指数，并解释它们在决策树特征选择中的作用。
4. 比较 ID3、C4.5 和 CART 决策树算法在分裂准则、属性处理、剪枝和任务类型上的差异。
5. 计算支持度、置信度和提升度，并说明 Apriori 发现频繁项集的基本思想。
6. 比较 k-means、层次聚类和 DBSCAN 的适用条件、优缺点和主要参数。

引言

随着数据库、数据仓库和各类信息系统的广泛应用，组织积累的数据规模持续增长。仅依靠查询、报表和联机分析，往往只能回答已知的问题；面对海量数据中隐含的规律和趋势，还需要更系统的自动分析方法。数据挖掘研究如何从大规模、不完全、含噪声的数据中发现隐含的、事先未知的、具有潜在价值的信息和知识，它强调在大规模、高维、含噪声的数据中自动搜索模式，是知识发现流程中的核心环节。

本章以数据挖掘的基本概念为起点，依次讨论数据预处理、信息熵与特征选择、决策树分类、关联规则挖掘、聚类分析和异常点分析，最后介绍数据挖掘的应用与社会影响。内容侧重基础模型、算法思想和适用条件，覆盖分类、预测、聚类、关联分析等描述型与预测型任务的典型方法，有助于读者建立从原始数据到决策知识的完整分析视角，为后续学习更深入的机器学习方法奠定基础。

9.1 数据挖掘概论

9.1.1 数据挖掘与知识发现

数据挖掘是从大量数据中发现隐含规律和知识的过程。通常所说的知识发现（Knowledge Discovery from Data, KDD）包含数据选择、预处理、变换、数据挖掘以及结果解释与评价等阶段；数据挖掘处于其中的核心环节。数据挖掘所发现的知识应当具有隐含性、事先未知性、潜在有用性和可理解性，这与数据库查询、报表统计或人工经验归纳存在区别。

传统数据分析往往依据明确的假设和统计模型，数据挖掘则强调在大规模、高维、含噪声的数据中自动搜索模式。例如，银行可以从历史交易数据中学习“高风险贷款申请”的特征，零售企业可以从购物记录中发现商品之间的关联，电信运营商可以从通话行为中识别异常账户。这些任务通常难以仅通过人工观察完成，需要借助算法从数据中建立模型。

9.1.2 数据挖掘的发展背景

数据挖掘的发展建立在数据库技术、统计学、机器学习和可视化技术的基础上。数据库系统解决了数据的集中存储、共享和事务处理，数据仓库进一步提供了面向分析主题的历史数据集合。随着计算能力提高和数据规模扩大，统计建模和机器学习方法能够应用于更大规模的现实数据，数据挖掘逐渐成为从数据资源中获取决策知识的重要途径。 数据挖掘的典型工作流程可用图9-1 表示。

图9-1 知识发现与数据挖掘的基本过程

9.1.3 数据挖掘系统的分类

数据挖掘系统可以按照数据类型、知识类型、应用领域和技术路线进行分类。按照数据类型，可分为关系数据库、数据仓库、事务数据、文本、Web 和流数据等挖掘系统；按照挖掘任务，可分为特征描述、关联规则、分类、预测、聚类、异常点分析和演化分析等系统；按照应用领域，可分为金融、电信、生物信息、电子商务和工业互联网等专用系统；按照技术路线，还可区分基于数据库、基于统计学、基于机器学习和基于可视化的实现方式。

表9-1 数据挖掘任务类型

9.2 数据预处理

9.2.1 数据预处理的必要性

现实数据通常存在缺失值、噪声、不一致表示和尺度差异。缺失值可能来自录入遗漏、设备故障或数据合并，噪声可能来自测量误差或异常记录，不一致则表现为不同系统对同一属性的命名、编码或度量单位不同。若不经处理直接挖掘，模型可能学习到错误模式，结果也难以解释。数据预处理的目标是在保留主要信息的前提下，提高数据质量和算法效率。

9.2.2 数据清洗与集成

数据清洗处理缺失值、噪声和不一致。缺失值可以采用忽略记录、全局常量填充、属性均值或中位数填充、回归预测以及基于相似样本的估计等方法。噪声数据可以通过分箱平滑、回归拟合或聚类检测进行处理。数据集成将来自多个数据源的数据合并到统一视图，其核心问题包括模式匹配、实体识别和冗余消除。例如，数据库 A 中的 cust_id 与数据库 B 中的 customer_no 可能指向同一客户，需要通过属性名称、取值和语义共同判断。

9.2.3 数据变换

数据变换改变数据的表示形式，使不同属性在数值范围、分布形态和粒度层次上更适合后续算法。

1. 规范化

规范化将数据按比例缩放到特定范围，避免取值范围较大的属性在距离计算中主导结果。常用方法包括最小-最大规范化、z-score 标准化。

(1) 最小-最大规范化（Min-Max Normalization）

将原始值线性映射到指定区间 $[new\_min, new\_max]$（通常为 $[0,1]$）：

适用性：适用于数据的最大值和最小值已知且稳定的场景。缺点是对离群值敏感——若新数据超出原始范围，需要重新计算。

(2) z-score 标准化（零均值规范化）

将数据变换为均值为 0、标准差为 1 的标准正态分布：

适用性：当数据的最小值和最大值未知，或需要降低离群值影响时较为适用，常用于基于距离或梯度的算法。

2. 常用数据变换

• 聚合将日销量汇总为月销量或年销量，从而降低数据粒度。
• 泛化利用概念分层将具体值替换为高层概念，例如将街道地址转换为城市或省份。
• 对数变换 $v'=\log(v)$ 适用于收入、商品价格等右偏分布数据，可使分布更接近对称。
• 离散化将连续属性转换为区间或类别，例如把年龄划分为“青年”“中年”“老年”。

3. 数据归约

数据归约目的是缩小数据集规模或降低数据维度，同时尽可能保持原始数据的分析价值。

• 特征选择（Feature Selection）：删除与挖掘任务无关或冗余的属性。常用方法包括前向选择、后向消去以及基于相关性分析的过滤法。
• 主成分分析（PCA, Principal Component Analysis）：通过正交变换将原始的 $n$ 维特征映射为不相关的 $k$ 维主成分（$k \ll n$），保留方差贡献率最大的前 $k$ 个主成分。其核心步骤包括：
  1. 对数据进行 z-score 标准化
  2. 对中心化后的数据矩阵 $X$ 计算协方差矩阵 $\Sigma = \frac{1}{n-1}X^TX$
  3. 求解协方差矩阵的特征值 $\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n$ 及对应的特征向量
  4. 选取前 $k$ 个特征向量构成投影矩阵，累计贡献率 $\frac{\sum_{i=1}^k \lambda_i}{\sum_{i=1}^n \lambda_i} \geq 85\%$

适用性：PCA 适用于特征维度较高且特征间存在线性相关性的场景。

9.3 信息熵与特征选择

9.3.1 信息熵

1948年，克劳德·香农（Claude Shannon）提出了**信息熵（Entropy）**的概念，为度量信息的不确定性奠定了数学基础。

对于一个离散随机变量 $Y$，它有 $m$ 个可能的取值 $\{y_1, y_2, \ldots, y_m\}$，每个取值对应的概率为 $p_i = P(Y = y_i)$，则 $Y$ 的信息熵定义为：

其中约定 $0 \log_2 0 = 0$。熵的单位为比特（bit）。

信息熵具有以下基本性质：

• 当所有类别等概率出现时（$p_i = 1/m$），熵取最大值 $H_{max} = \log_2 m$，此时不确定性最大。
• 当某一类概率为 1 时，熵为 0，表示完全确定。
• 对于二分类问题（$m=2$），熵简化为 $H = -p \log_2 p - (1-p) \log_2 (1-p)$，当 $p=0.5$ 时取最大值 1 bit。

9.3.2 条件熵与信息增益

在分类问题中，特征选择需要衡量引入某个特征后类别不确定性的减少程度。

条件熵（Conditional Entropy）

已知特征 $A$ 的条件下，数据集 $D$ 关于类别 $Y$ 的不确定性定义为：

信息增益（Information Gain）

信息增益定义为原始熵与条件熵之差，表示得知特征 $A$ 的信息而使得类别 $Y$ 的不确定性减少的程度：

ID3 决策树算法优先选择信息增益最大的特征作为分裂特征，因为信息增益越大，按该特征划分后类别不确定性下降越明显。

计算示例：设数据集 $D$ 包含 14 个样本，属性 T1、T2、T3 和类别 S 如表9-2 所示。试计算类别 S 的熵、S 关于 T1 的条件熵，以及 T1 带来的信息增益。

表9-2 信息增益计算示例数据

(1) 类别 S 的熵

14 个样本中，类1 有 9 个，类2 有 5 个，则：

(2) 类别 S 关于 T1 的条件熵

按 T1 的取值将 $D$ 划分为三个子集：

表9-3 T1取值子集的熵计算

(3) T1 带来的信息增益

计算结果表明，已知 T1 的取值后，类别 S 的不确定性约减少 0.246 bit。其中 T1=B 的子集全部属于类1，纯度最高，对信息增益的贡献最大。若再分别计算 T2、T3 的信息增益，则可选取增益最大的属性作为决策树的分裂属性。

9.3.3 信息增益比

信息增益倾向于选择取值较多的特征。以“身份证号”为例，若该属性每个取值只对应一个样本，按它划分后每个子集的类别纯度都很高，信息增益接近最大，但这样的划分并不具有对新样本的泛化能力。

为了校正这一偏向，**信息增益比（Information Gain Ratio）**引入了一个惩罚项——分裂信息值（Split Information），对信息增益进行规范化：

分裂信息值 $SplitInfo_A(D)$ 本身就是特征 $A$ 取值分布的熵。当特征 $A$ 的取值越多且分布越均匀时，$SplitInfo_A(D)$ 越大，从而抑制了信息增益对多取值特征的偏好。这正是 C4.5 算法改进 ID3 算法的核心所在。

计算示例：仍以表9-2 的数据为例，计算属性 T1 的信息增益比。

由 9.3.2 节已知 $Gain(D, T1) \approx 0.246$ bit。T1 取值 A、B、C 的样本数分别为 5、4、5，则分裂信息值为：

信息增益比为：

与信息增益相比，信息增益比除以了反映取值个数与分布均匀程度的分裂信息值，因此对取值较多的属性施加了惩罚。

信息增益比虽然纠正了对多取值特征的偏好，但可能反过来偏向于取值较少的特征。在实际应用中（如 C4.5 算法），通常先从候选特征中选出信息增益高于平均水平的特征，再从中选取信息增益比最高者。

9.4 决策树分类算法

9.4.1 决策树基本概念

**决策树（Decision Tree）**是一种类似于流程图的树形结构，它模拟了人类决策的过程。树的每个内部节点代表对某个属性的测试，每个分支代表测试的结果，而叶节点则承载着最终的类别标签。从根节点到叶节点的每一条路径都代表了一条分类规则，具有极高的可解释性。

9.4.2 主要决策树算法

决策树学习通常采用自顶向下的递归划分策略，先选择一个区分能力最强的属性作为根节点，再对划分后的样本子集递归生成子树。不同算法的主要差异体现在分裂准则、属性处理和剪枝方式。

1. ID3 算法

ID3 由 J. Ross Quinlan 于 20 世纪 80 年代提出，采用信息增益作为分裂准则。

算法步骤：

1. 计算数据集 $D$ 的信息熵 $H(Y)$
2. 对每个候选特征 $A$，计算信息增益 $Gain(D, A) = H(Y) - H(Y|A)$
3. 选择信息增益最大的特征 $A^* = \arg\max_A Gain(D, A)$ 作为当前节点的分裂特征
4. 按 $A^*$ 的每个取值将 $D$ 划分为子集，对每个子集递归执行上述过程
5. 当子集中所有样本属于同一类别，或无剩余特征可分裂时，生成叶节点

局限性：只能处理离散属性；倾向于选择取值多的特征；不支持剪枝，容易过拟合。

2. C4.5 算法

作为 ID3 的改进版本，它做出了以下关键改进：

• 分裂准则：采用信息增益比 $GainRatio(D, A)$ 替代信息增益，抑制对多取值特征的偏好。
• 连续属性处理：对连续属性 $A$ 的 $n$ 个不同取值排序为 $\{a_1, a_2, \ldots, a_n\}$，考察 $n-1$ 个候选二分点 $t_i = \frac{a_i + a_{i+1}}{2}$，选择使信息增益最大化的分割点 $t^*$，将连续属性二值化为 $A \leq t^*$ 和 $A > t^*$。
• 缺失值处理：通过加权的方式处理含缺失值的样本，未缺失样本以权重参与信息增益的计算，缺失值样本按比例分配到各子节点。

计算示例（连续属性处理）：表9-2 中的 T2 为连续属性，以下演示 C4.5 如何确定 T2 的最优分割点。

(1) 排序并统计各取值的类别分布

T2 共有 9 个不同取值，按升序排列后，各取值对应的类别数量如下：

表9-4 T2取值的类别分布

(2) 生成候选分割点

相邻两个取值的中点共有 $9-1=8$ 个候选分割点：67.5、72.5、76.5、79、82.5、87.5、92.5、95.5。每个候选点 $t$ 将 $D$ 划分为 $T2 \leq t$ 和 $T2 > t$ 两个子集。

(3) 逐一计算各候选点的信息增益

以 $t=82.5$ 为例：$T2 \leq 82.5$ 的子集有 9 个样本（类1 为 7 个，类2 为 2 个），$T2 > 82.5$ 的子集有 5 个样本（类1 为 2 个，类2 为 3 个），则：

对其余候选点采用相同方法计算，结果如表9-5 所示。

表9-5 T2各候选分割点的信息增益

(4) 确定最优分割点并计算信息增益比

$t^*=82.5$ 时信息增益最大，因此 T2 被二值化为 $T2 \leq 82.5$ 和 $T2 > 82.5$ 两个分支，其信息增益为 0.102 bit。该划分的分裂信息值为：

该值小于 T1 的信息增益比 0.156。因此，仅就这两个属性而言，C4.5 将优先选择 T1 作为根节点的分裂属性。

3. CART 算法

由 Breiman 等人在 1984 年提出。CART 构建的是二叉树，使用**基尼指数（Gini Index）**作为特征选择标准。

对于数据集 $D$，假设有 $m$ 个类别，第 $i$ 个类别的样本占比为 $p_i$，则其基尼值定义为：

基尼值反映了从数据集中随机抽取两个样本，其类别标记不一致的概率。$Gini(D)$ 越小，数据集 $D$ 的纯度越高。

对于特征 $A$ 的某个取值 $a$，将 $D$ 划分为 $D_1 = \{x \in D | A(x) = a\}$ 和 $D_2 = D \setminus D_1$ 两部分，则在该划分下的基尼指数为：

CART 算法遍历所有特征的所有可能取值（或二分点），选择使基尼指数最小的特征及其取值作为最优分裂点：

对于回归树，CART 使用平方误差或绝对误差度量节点不纯度，选择使划分后误差下降最大的特征和切分点。

计算示例：仍以表9-2 的数据为例，用 CART 算法选择根节点的分裂属性。

(1) 计算数据集的基尼值

14 个样本中类1 有 9 个，类2 有 5 个，则：

(2) 枚举候选二分划分

CART 只生成二叉树，因此每个划分都将 $D$ 分为两个子集：

• 离散属性 T1 有 A、B、C 三个取值，对应 3 种二分方式：$\{A\}$ 与 $\{B,C\}$，$\{B\}$ 与 $\{A,C\}$，$\{C\}$ 与 $\{A,B\}$。
• 离散属性 T3 有 0、1 两个取值，对应 1 种二分方式。
• 连续属性 T2 与 C4.5 相同，取相邻取值的中点作为候选分割点，共 8 个，划分为 $T2 \leq t$ 和 $T2 > t$。

(3) 计算各划分的基尼指数

以 $T1 = B$ 为例：$D_1$（T1 为 B）有 4 个样本，全部为类1；$D_2$（T1 为 A 或 C）有 10 个样本，类1 和类2 各 5 个，则：

其余划分的计算方法相同，结果如表9-6 所示。

表9-6 各候选划分的基尼指数

(4) 选择最优分裂点

基尼指数最小的划分为 $T1 = B$，其值约为 0.357，基尼值下降量为 $0.459 - 0.357 \approx 0.102$。因此 CART 以"T1 是否等于 B"作为根节点的测试条件：满足条件的 4 个样本全部属于类1，直接生成叶节点；不满足条件的 10 个样本（类1 和类2 各 5 个）仍不纯，对其重复上述过程继续递归划分，直到满足停止条件。

表9-7 ID3、C4.5与CART算法对比

9.4.3 树剪枝技术

如果决策树生长得过于茂盛，它会过度拟合训练数据中的噪声和细节，导致在面对新数据时预测表现糟糕，这被称为过拟合（Over-fitting）。

剪枝（Pruning） 技术通过剪掉那些统计意义不显著的分支，将模型简化，从而提高泛化能力。

(1) 预剪枝（Pre-pruning）：在树生长过程中，对每个节点在划分前进行评估。若当前划分不能带来验证集上准确率的提升，则停止划分，将该节点标记为叶节点。常用的停止条件包括：

• 节点包含的样本数小于阈值
• 所有特征的信息增益（或基尼指数下降）小于阈值 $\epsilon$
• 树的深度达到预设的最大值

(2) 后剪枝（Post-pruning）：先让树完全生长，再自底向上评估每个内部节点。若将某子树替换为叶节点后，模型在验证集上的准确率不降低（或下降可接受），则进行剪枝。CART 算法的**代价复杂度剪枝（Cost-Complexity Pruning）**定义如下：

适用性：预剪枝计算开销小，但存在"欠拟合"风险；后剪枝保留了更多分支信息，泛化能力通常优于预剪枝，但计算代价较高。实际应用中后剪枝更为常用。

9.5 关联规则挖掘

9.5.1 关联规则问题

关联规则挖掘用于发现事务数据中项集之间的频繁联系。零售业中常被引用的“啤酒与尿布”案例说明，某些看似不相关的商品可能具有稳定的共同购买模式。设 $I=\{i_1,i_2,\ldots,i_m\}$ 为所有项的集合，事务数据库 $D$ 中的每条事务 $T$ 是 $I$ 的一个子集。关联规则通常记为 $A \Rightarrow B$，其中 $A$、$B$ 为不相交的项集。

9.5.2 支持度、置信度与提升度

为筛选具有统计意义和业务价值的规则，需要同时考察支持度、置信度和提升度。

• 支持度衡量规则在事务数据库中的普遍程度，即项集 $A \cup B$ 出现的频率。
  $$support(A \Rightarrow B) = P(A \cup B) \tag{9-12}$$
• 置信度衡量规则的可靠性，即在出现 $A$ 的条件下同时出现 $B$ 的条件概率。
  $$confidence(A \Rightarrow B) = P(B|A) = \frac{support(A \cup B)}{support(A)} \tag{9-13}$$
• 提升度比较规则的置信度与 $B$ 的总体出现频率。提升度大于 1 表示正相关，等于 1 表示相互独立，小于 1 表示负相关。
  $$Lift(A, B) = \frac{P(A \cup B)}{P(A)P(B)} \tag{9-14}$$

计算示例：设某商店的购物篮事务数据库如表9-8 所示。数据库共有 4 条事务，TID 为事务编号，右列为该事务中顾客购买的商品（以 A～F 表示 6 种商品）。设最小支持度为 50%，最小置信度为 50%，下面计算规则的支持度、置信度和提升度，并判断其是否为强规则。

表9-8 购物篮事务示例

(1) 统计项集的支持度

表9-9 项集的支持度统计

(2) 计算规则的支持度、置信度和提升度

以规则 $A \Rightarrow C$ 为例：

对规则 $C \Rightarrow A$ 和 $A \Rightarrow B$ 采用同样的方法计算，结果如下：

表9-10 候选规则的评价结果

(3) 结果解释

• $A \Rightarrow C$ 和 $C \Rightarrow A$ 的支持度均为 50%，置信度分别为 66.7% 和 100%，都满足最小支持度和最小置信度，是强关联规则。其中 $C \Rightarrow A$ 的置信度为 100%，表示购买 C 的顾客全部也购买了 A。
• 两条规则的支持度和提升度相同，但置信度不同：支持度与提升度只取决于 $A \cup C$ 的整体共现情况，而置信度的分母随前件不同而变化。
• $A \Rightarrow C$ 的提升度约为 1.33，大于 1，说明 A 与 C 正相关：购买 A 的顾客购买 C 的概率（66.7%）高于全体顾客购买 C 的概率（50%）。
• $A \Rightarrow B$ 的支持度和置信度均不满足阈值，且提升度约为 0.67，小于 1，说明 A 与 B 呈负相关，不应作为推荐依据。

9.5.3 频繁项集挖掘算法

关联规则挖掘的关键步骤是发现支持度不低于最小支持度阈值的频繁项集。项集的候选组合空间随项数呈指数增长，直接枚举通常不可行。

Apriori 算法利用先验性质缩小搜索空间：频繁项集的任何非空子集也一定是频繁项集，因此若某项集不频繁，其所有超集都可以被剪枝。算法采用逐层搜索，先生成候选 $(k+1)$-项集，再通过数据库扫描计算支持度。该方法仍需多次扫描数据库，且候选集规模可能较大。

FP-growth 算法通过构建频繁模式树（FP-tree）压缩事务数据库。树中节点记录项的出现频数，共享前缀的事务被合并到同一路径。挖掘时从条件模式基出发，递归构造条件 FP-tree，在无需生成全部候选项集的情况下发现频繁模式，通常比 Apriori 具有更高的效率。

9.5.4 计算案例（Apriori）

大型数据库中的关联规则挖掘分为两个步骤：

1. 找出所有频繁项集：即支持计数不低于最小支持计数的项集。大部分计算集中在这一步。
2. 由频繁项集产生强关联规则：即同时满足最小支持度和最小置信度的规则。

设事务数据库如表9-11 所示，共 9 条事务，最小支持计数为 2（对应最小支持度 $2/9 \approx 22\%$），进行关联规则的挖掘。

表9-11 事务数据库

1. 用 Apriori算法找出所有频繁项集

Apriori 采用逐层搜索：先由频繁 $k$-项集 $L_k$ 生成候选 $(k+1)$-项集 $C_{k+1}$，再扫描数据库统计支持计数，删除低于最小支持计数的候选，得到 $L_{k+1}$。其依据是 Apriori 性质：频繁项集的所有非空子集必定也是频繁的；反之，只要有一个子集不频繁，该项集就一定不频繁，可直接剪枝而无需扫描数据库。

(1) 第 1 次扫描：生成 $C_1$ 并得到 $L_1$

将每个单项都作为候选 1-项集，扫描数据库统计支持计数：

表9-12 候选1-项集的支持计数

5 个单项的支持计数均不小于 2，因此 $L_1=\{\{I_1\},\{I_2\},\{I_3\},\{I_4\},\{I_5\}\}$。

(2) 第 2 次扫描：生成 $C_2$ 并得到 $L_2$

将 $L_1$ 与自身连接，得到 $\binom{5}{2}=10$ 个候选 2-项集。由于 $L_1$ 中所有 1-项集都是频繁的，它们的子集检查全部通过，无需剪枝。再次扫描数据库统计支持计数：

表9-13 候选2-项集的支持计数

删除不满足最小支持计数的 $\{I_1,I_4\}$、$\{I_3,I_4\}$、$\{I_3,I_5\}$、$\{I_4,I_5\}$，得到：

(3) 第 3 次扫描：生成 $C_3$ 并得到 $L_3$

连接：若 $L_2$ 中两个项集的前 $k-2=1$ 个项相同，则将它们连接为一个候选 3-项集，得到 6 个候选：

$\{I_1,I_2,I_3\}$、$\{I_1,I_2,I_5\}$、$\{I_1,I_3,I_5\}$、$\{I_2,I_3,I_4\}$、$\{I_2,I_3,I_5\}$、$\{I_2,I_4,I_5\}$

剪枝：利用 Apriori 性质检查每个候选的所有 2-项子集是否都在 $L_2$ 中：

表9-14 候选3-项集的剪枝检查

剪枝后 $C_3=\{\{I_1,I_2,I_3\},\{I_1,I_2,I_5\}\}$，候选数由 6 个减为 2 个，被剪掉的 4 个项集无需再扫描数据库。扫描统计支持计数：

表9-15 候选3-项集的支持计数

因此 $L_3=\{\{I_1,I_2,I_3\},\{I_1,I_2,I_5\}\}$。

(4) 生成 $C_4$，算法终止

将 $L_3$ 中两个项集连接，得到候选 4-项集 $\{I_1,I_2,I_3,I_5\}$。其 3-项子集 $\{I_2,I_3,I_5\}$ 不在 $L_3$ 中（它在上一步已被剪枝），因此该候选被剪枝，$C_4=\varnothing$，算法终止。

所有频繁项集为 $L_1 \cup L_2 \cup L_3$，其中最大的频繁项集为 $\{I_1,I_2,I_3\}$ 和 $\{I_1,I_2,I_5\}$。

2. 由频繁项集产生强关联规则

强关联规则同时满足最小支持度和最小置信度。由频繁项集产生的规则必然满足最小支持度，因此只需检验置信度：

产生规则的过程如下：

1. 对每个频繁项集 $l$，产生 $l$ 的所有非空真子集 $s$；
2. 对每个非空子集 $s$，若 $\dfrac{support\_count(l)}{support\_count(s)} \geq min\_conf$，则输出规则 $s \Rightarrow (l-s)$。

设最小置信度 $min\_conf=70\%$。

例 1：频繁项集 $l=\{I_1,I_2,I_5\}$（$support\_count(l)=2$）

$l$ 的非空真子集为 $\{I_1,I_2\}$、$\{I_1,I_5\}$、$\{I_2,I_5\}$、$\{I_1\}$、$\{I_2\}$、$\{I_5\}$，据此得到 6 条候选规则：

表9-16 频繁项集{I1,I2,I5}的候选规则

其中分母分别为 $support\_count(\{I_1,I_2\})=4$、$support\_count(\{I_1,I_5\})=2$、$support\_count(\{I_2,I_5\})=2$、$support\_count(\{I_1\})=6$、$support\_count(\{I_2\})=7$、$support\_count(\{I_5\})=2$。因此得到 3 条强关联规则：

例 2：频繁项集 $l=\{I_1,I_2,I_3\}$（$support\_count(l)=2$）

表9-17 频繁项集{I1,I2,I3}的候选规则

该频繁项集没有产生任何强关联规则。可见频繁项集只保证规则满足最小支持度，是否成为强规则还取决于置信度。对其余频繁项集（如 2-项集），按同样的方法逐一检验即可。

9.5.5 其他关联规则

前面讨论的关联规则都是布尔关联规则：只关心某个项在事务中出现还是未出现（取值为 1 或 0，Yes or No），不关心购买数量或价格；规则涉及的项也都处于同一抽象层次，例如“购买牛奶的顾客通常也会购买面包”。这类规则是离散的、二元的关系。

现实数据往往更加复杂：事务中除商品外还带有年龄、性别、收入等属性，属性可以是数值型，商品之间还存在“品牌—品类—大类”的层次关系。针对这些情形，关联规则可以扩展为多维关联规则、量化关联规则和多层次关联规则，它们的共同思路是先把数据转换为布尔形式，再沿用 Apriori 等算法求解。

1. 多维关联规则

Apriori 算法天生为“购物篮”设计，只有“物品”这一个维度。如果要同时考虑用户的性别、年龄、地区等多个维度，可采用单维化处理：把各维属性“压扁”，伪装成普通的项（item），再用 Apriori 算法挖掘。例如，规则 年龄_20-30 ∧ 性别_男 ⇒ 啤酒 同时涉及年龄、性别和商品三个维度。

设原始数据如表9-18 所示：

表9-18 带有用户属性的事务数据

第一步：量化数据离散化。 先把数值变成区间标签。

• 年龄：25、26 归入 [20-30岁]，45 归入 [40-50岁]。
• 收入：8000、9000 归入 [中低收入]，25000 归入 [高收入]。

第二步：属性标签化。 把“列名”和“值”拼接起来，变成项。例如，性别“男”变成项 性别_男，年龄区间 [20-30岁] 变成项 年龄_20-30。

第三步：合并入篮（扁平化）。 将每条事务的所有属性项与商品项合并到同一个“超级购物篮”中，如表9-19 所示。

表9-19 扁平化后的超级购物篮

进一步可将项集转换为布尔矩阵（One-Hot 编码），出现记为 1，未出现记为 0，如表9-20 所示。此后即可直接套用前述的 Apriori 算法。

表9-20 布尔矩阵（One-Hot编码）

2. 量化关联规则

量化关联规则处理的数据包含数值属性。它不再是简单的“买没买”，而是涉及“买了多少”“年龄多大”“收入多少”这类量化概念，通常需要把连续的数字划分为区间，再寻找规律。

难点在于区间如何划分：按 10 岁一段还是按 5 岁一段，会使挖掘出的规则完全不同。区间过窄，每个区间的支持度偏低，规则可能达不到最小支持度；区间过宽，规则的置信度又会被稀释。核心思路是先把“量化”问题变成“布尔”问题，再用 Apriori 或其他算法求解。常见的处理方式有三种：

(1) 静态离散化（Static Discretization）

在挖掘之前，预先把数值划分为区间（分箱），然后将区间作为布尔属性。例如，原数据为年龄 = 23、24、25、26、27……，处理后变为布尔属性“青年”（20-30 岁）和“中年”（30-50 岁）。常见的切分策略有：

• 等宽分箱：每个区间的宽度相同，例如每 10 岁一档。
• 等频分箱：每个区间包含的记录数大致相同。

(2) 基于聚类的处理（Clustering-based）

利用聚类算法（如 k-means）对量化属性进行处理：

1. 把所有人的“收入”“年龄”等属性投射到坐标系上；
2. 观察数据点在哪里最密集，让算法自动聚成若干簇；
3. 给每一簇起一个名字（如 A 类人群、B 类人群）；
4. 用簇的 ID 替换原来的数值，再运行 Apriori。

(3) 动态量化关联规则挖掘

这类算法（如 Srikant 和 Agrawal 提出的方法）不预先固定区间，而是在挖掘过程中动态合并相邻区间。算法先从细粒度区间开始（20-21 岁、21-22 岁……），如果发现“20-21 岁”和“21-22 岁”都与“购买啤酒”有关联，就自动把它们合并为“20-22 岁”，从而提高支持度。

3. 多层次关联规则

商品之间通常存在概念分层，例如“电子产品 → 笔记本电脑 → 联想笔记本 → 联想 X1 Carbon”。多层次关联规则在不同抽象层次上挖掘规则：高层规则概括性强，低层规则更具体。主要有三种挖掘策略。

(1) 自顶向下策略（Top-Down Strategy）

先在最高层的“大类”上找规则；若大类之间存在关联，再向下展开到下一层继续挖掘；若大类之间没有关联，则其下的小类直接放弃（剪枝）。

表9-21 自顶向下挖掘策略示例

(2) 层级独立的支持度策略（Variable Support Strategy）

Apriori 通常只设置一个支持度阈值（如 5%），但这对多层次数据并不合适：对高层的大类，5% 太容易达到，会挖出大量无意义的规则；对底层的具体商品，5% 又太难达到，许多有价值的规则被误删。因此可以为不同层级设置不同的最小支持度阈值：

表9-22 各层级的最小支持度设置

(3) 同级与跨级混合挖掘（Cross-level Mining）

有时需要发现跨越层次的规则，例如“联想笔记本电脑（具体层）⇒ 鼠标（抽象层）”。做法是对数据进行全层级展开：把一个商品同时翻译成它在各个层级上的所有身份，一并放入购物篮。

• 原始数据：{ 联想 X1 Carbon }
• 展开后：{ 联想 X1 Carbon, 联想笔记本, 笔记本电脑, 电子产品 }

展开后，算法会自动计算各种项的组合，这会产生冗余规则，例如“联想 X1 Carbon ⇒ 联想笔记本”。这类规则只是反映了概念分层本身，并没有提供新的知识。为此需要设定输出规则：若 A 是 B 的上级（或下级），则 A 与 B 之间的关联规则直接剔除，不予输出。

4. 三类扩展规则的比较

表9-23 三类扩展关联规则的比较

9.6 聚类分析

9.6.1 聚类的基本概念

聚类是一种无监督学习方法，在样本没有预先标注类别的情况下，根据对象之间的相似性将数据划分为若干簇。聚类结果应使同一簇内的对象相似度较高，不同簇之间的对象差异较大。市场细分、图像分割、文档组织和异常检测等任务经常使用聚类作为探索数据结构的方法。

9.6.2 相似性度量

聚类质量依赖相似性或距离的定义。数值型数据通常采用闵可夫斯基距离、余弦相似度和杰卡德系数等度量。

1. 闵可夫斯基距离

它是欧氏距离和曼哈顿距离的泛化表示，对于 $n$ 维数值型数据：

表9-24 闵可夫斯基距离的特例

2. 余弦相似度

对于文本文档等高维稀疏向量，关注方向而非绝对距离：

适用性：适合文本向量、TF-IDF 表示的文档相似度计算。值域为 $[-1, 1]$，1 表示方向完全一致，0 表示正交无关，-1 表示方向相反。

计算示例：设两个文档的词频向量为 $\mathbf{x} = (2, 1, 0, 1)$，$\mathbf{y} = (1, 1, 1, 0)$，则：

• 内积：$\mathbf{x}^T \mathbf{y} = 2\times1 + 1\times1 + 0\times1 + 1\times0 = 3$
• 向量模：$||\mathbf{x}|| = \sqrt{2^2+1^2+0^2+1^2} = \sqrt{6}$，$||\mathbf{y}|| = \sqrt{1^2+1^2+1^2+0^2} = \sqrt{3}$
• 余弦相似度：$\cos(\mathbf{x}, \mathbf{y}) = \dfrac{3}{\sqrt{6}\times\sqrt{3}} = \dfrac{3}{\sqrt{18}} \approx 0.707$

结果表明这两个文档的词频方向较为接近，相似度较高。

3. 杰卡德系数

用于度量两个集合之间的相似性，常用于布尔类型或集合型数据：

适用性：广泛应用于文本去重、推荐系统中的用户行为相似度计算。

4. 相异度（距离）计算

许多聚类算法以相异度矩阵为基础：$n$ 个对象构成 $n\times n$ 的对称矩阵，元素 $d(i,j)$ 表示对象 $i$ 与 $j$ 的差异，$d(i,i)=0$，且 $d(i,j)=d(j,i)$。若原始数据以数据矩阵（对象×属性）形式给出，需先转换为相异度矩阵。$d(i,j)$ 的具体算法取决于变量类型，常见类型包括区间标度变量、二元变量、类别型（标称）变量、序数型变量和混合类型变量。

(1) 区间标度变量

区间标度变量为连续数值，可直接采用前文的闵可夫斯基距离（欧氏距离、曼哈顿距离等）计算。为避免量纲和取值范围差异的影响，通常先进行最小-最大规范化或 z-score 标准化。

(2) 二元变量

二元变量只有 0、1 两种状态，例如 smoker 表示是否吸烟。一个对象可以包含多个二元变量。设对象 $i$ 与 $j$ 共有 $p$ 个二元变量，其取值匹配情况如下表所示：

表9-25 二元变量的取值匹配情况

其中 $q$ 为两对象取值均为 1 的变量数，$t$ 为均为 0 的变量数，$r$、$s$ 为两对象取值不同的变量数。