第9章
数据挖掘

🔎 传统分析的天花板

查询、报表、OLAP 都只能回答已知的问题：你得先想到“啤酒和尿布可能相关”，才谈得上去查。人工归纳面对海量、高维、含噪声的数据更是力不从心。

⛏️ 挖掘的承诺

让算法自动搜索模式：银行从历史交易里学出“高风险贷款”的长相，零售从购物记录里发现商品关联，电信从通话行为里认出异常账户——规律事先未知，挖出来才知道。

🗄️ 按数据类型

关系数据库、数据仓库、事务数据、文本、Web、流数据挖掘系统——数据类型决定方法适配。

🎯 按挖掘任务

特征描述、关联、分类、预测、聚类、异常、演化——上一页的七类各成系统。

🏭 按应用领域

金融、电信、生物信息、电子商务、工业互联网等专用系统：通用算法＋领域规则。

🛠️ 按技术路线

基于数据库、基于统计学、基于机器学习、基于可视化——同一任务可以多路实现（第 38 页前端工具层呼应）。

🧺 现实数据的四种毛病

• 缺失值：录入遗漏、设备故障、数据合并丢项
• 噪声：测量误差、异常记录
• 不一致：同属性在多系统的命名、编码、单位各异（第 8 章的集成问题）
• 尺度差异：不同属性量纲悬殊，距离计算被大量纲主导

⚠️ 不处理直接挖的后果

模型会把错误当模式学走：把传感器故障读成“需求激增”、把单位混乱学成“区域差异”——结果既不准、也解释不通。预处理的目标：在保留主要信息的前提下，提高数据质量与算法效率。

🕳️ 缺失值五法

忽略记录、全局常量填充、均值/中位数填充、回归预测、基于相似样本估计——从粗暴到精细各有适用。

🔊 噪声三治

分箱平滑（用箱均值/中位数替换）、回归拟合、聚类检测（离群者多半是噪声或异常）。

🧩 集成三难

模式匹配、实体识别、冗余消除：A 库的 cust_id 与 B 库的 customer_no 是否同一客户，要靠名称、取值与语义共同判定。

📏 最小-最大规范化

v′ = (v − min) / (max − min)

线性映射到 [0,1]。适合最值已知且稳定的场景；缺点：对离群值敏感，新数据超界要重算。

📐 z-score 标准化

v′ = (v − 均值 Ā) / 标准差 σ

变换为均值 0、标准差 1。适合最值未知或要压低离群影响时，基于距离或梯度的算法常用。

🧮 聚合

日销量汇总为月销量、年销量：降低粒度，让趋势浮出水面（第 8 章上卷的思想重演）。

🪜 泛化

用概念分层换值：街道地址→城市→省份（第 8 章地点分层在此复用）。

📉 对数变换

v′＝log(v)：收入、价格等右偏分布被拉回近似对称，模型更好学。

🎚️ 离散化

连续值切成区间或类别：年龄→青年/中年/老年——决策树处理连续属性的候选分割点与此相关（第 19 页）。

✂️ 特征选择

删掉与任务无关或冗余的属性：方法有前向选择、后向消去、相关性过滤法。维度降下来，噪声与过拟合风险一起降。

🧭 主成分分析 PCA

正交变换把 n 维特征映成 k 维互不相关的主成分（k≪n)：步骤是 z-score 标准化→协方差矩阵→特征值排序→取累计贡献率 ≥85% 的前 k 个成分。适合高维且特征间线性相关的场景。

🎲 全等概率最乱

各类别等概率时熵最大：H_max＝log₂m——完全猜不准。

🎯 某一类必现

某类概率为 1 时熵为 0——完全确定，没有信息可挖。

⚖️ 二分类标尺

H＝−p·log₂p −(1−p)·log₂（1−p)，p＝0.5 时最高 1 bit——抛硬币是最不确定的二分类。

🔍 条件熵 H(Y|A)

已知特征 A 后，类别 Y 还剩多少不确定性：按 A 的每个取值把 D 切成子集 Dⱼ，各子集算熵再按子集大小加权平均。特征越会“分堆”，条件熵越低。

📉 信息增益 Gain(D, A)

Gain = H(Y) − H(Y|A)

得知 A 后消除的不确定性。增益越大，按 A 划分后类别越“纯”。ID3 就选增益最大的特征当分裂点——下一页把这个过程完整算一遍。

🪜 算法五步

1. 算数据集整体熵 H(Y)
2. 对每个候选特征算信息增益
3. 选增益最大者 A* 作当前节点分裂特征
4. 按 A* 每个取值分子集，逐子集递归
5. 子集同类或无特征可分时，生成叶节点

由 Quinlan 于 20 世纪 80 年代提出，是决策树的开山之作。

🧱 三条局限

• 只能处理离散属性（连续值无从下手）
• 偏爱多取值特征（第 15 页的毛病）
• 不支持剪枝，容易过拟合（第 23 页）

三条局限，正是两位后继者 C4.5 与 CART 的改进清单。

⚖️ 准则换增益比

用 GainRatio 替代 Gain，抑制对多取值特征的偏好（第 15 页）。实战：先筛增益高于平均者，再取增益比最高。

✂️ 连续属性二分

取值排序后考察 n−1 个相邻中点作候选分割点，选增益最大的 t*，把连续属性二值化为 ≤t* 与 >t*——下一页实算。

🕳️ 缺失值加权

含缺失的样本按权重参与：未缺失样本以权重计增益，缺失样本按比例分配到各子节点——不因一行缺值就整行丢弃。

🌿 基尼值 Gini(D)

Gini = 1 − Σ pᵢ²

随机抽两个样本、类别不一致的概率。同例：Gini(D)＝1−(9/14)²−(5/14)² ≈ 0.459。越小越纯——与熵是同一件事的另一种刻度。

🔪 分裂方式

只长二叉树：遍历每个特征的每个取值（或二分点），把 D 切成 D₁/D₂ 两堆，选加权基尼指数最小的切法。回归任务时改用平方误差/绝对误差，同一副骨架做预测——分类回归一树两吃，故名 Classification And Regression Tree(1984)。

✂️ 预剪枝

边长边评：划分前先看验证集准确率是否提升，不升就停、节点转叶。常用停止条件：样本数低于阈值、增益低于 ε、深度达上限。省时，但可能早停错过后面才显效的划分。

🪚 后剪枝

先长满、再自底向上评估：把某子树换成叶后验证准确率不降（或可接受）就剪。CART 的代价复杂度剪枝用 Cα(T)＝C(T)＋α·|T| 在误差与树大小间定价。

📊 支持度 Support

P(A∪B)

A 与 B 同时出现的频率——规则有多普遍。太低的规则哪怕再准，也只是巧合。

🎯 置信度 Confidence

P(B|A) = supp(A∪B)/supp(A)

出现 A 时同时出现 B 的条件概率——规则有多可靠。

🚀 提升度 Lift

P(A∪B) / (P(A)·P(B))

与“碰巧共现”相比的放大倍数：>1 正相关、＝1 独立、<1 负相关——它裁决规则是否真有信息量。

1️⃣ 找频繁项集

逐层搜索：由频繁 k-项集 L_k 连接生成候选 C_{k+1}，扫库计数、删低于最小支持计数者，得 L_{k+1}。大部分计算量在这一步。

2️⃣ 生成强规则

对每个频繁项集枚举非空真子集作前件，只需验置信度（支持度已由频繁性保证）——下一组两页是完整案例。

🧲 定义与判据

无监督学习：样本没有预先标注的类别，按相似性划成若干簇。好聚类的标准只有一句：簇内相似度高、簇间差异大。

🎯 用在哪

市场（客户）细分、图像分割、文档组织、异常检测的预备动作。物流里：网点按货量与结构分群、客户按行为分层、运单按轨迹归类。

🧭 余弦相似度

cos(x,y) = (x·y) / (‖x‖·‖y‖)

只看方向不看长度，值域 [−1,1]。教材例：文档词频 x＝(2,1,0,1)、y＝(1,1,1,0)：内积 3、模 √6 与 √3,cos ＝ 3/√18 ≈ 0.707——方向相当接近。文本与 TF-IDF 向量的标配（第 14 章的嵌入相似度就是它）。

🃏 杰卡德系数

J(A,B) = |A∩B| / |A∪B|

集合的交并比，专治布尔/集合型数据：文本去重、推荐系统里比对两个用户的行为集合，都是它。

⚠️ 局限清单

• 要预先指定 k（取几簇没有天书）
• 对初始质心敏感（可用 k-means++ 改进初始化）
• 只擅长球形/近球形簇，复杂形状与大小悬殊的簇会翻车
• 对离群值与噪声敏感（均值被极端点拽着走）

🎲 教材例题盘面

10 个二维点 P1—P10（如 P1(3,8)、P5(3,4)、P6(5,1)、P10(7,3)…),k＝2，初始质心 m₁＝(1, 3.25)、m₂＝(9, 4.15)。第一轮只比距离平方：P1 到 m₁ 约 26.56、到 m₂ 约 50.82 → 归簇 1。三轮迭代后收敛——动画演示的是同族过程。

🎯 核心对象

ε-邻域内对象数 ≥ MinPts 的点：簇的种子。

🌗 边界对象

自身邻域不够密，但落在核心对象的邻域里：簇的边缘成员。

🔇 噪声

不在任何核心对象邻域内的点：直接标记为噪声/离群——聚类顺手把异常筛了。

🗑️ 传统眼光

在分布或局部密度上显著偏离大多数的样本，传统统计常将其当噪声剔除——第 9.2 节清洗的“噪声处理”说的就是这种处置。

💰 挖掘眼光

在欺诈检测、入侵监测、设备故障诊断、医疗异常识别里，异常点恰恰是正主：一万笔正常运单里，那笔路线、时效、重量全都不对劲的，可能就是虚假交易。

📈 基于统计分布

假设数据服从某概率模型，落在低概率区的判异常。一维正态用 3σ 法则：|x−μ|>3σ 即异常（正常覆盖 99.73%）；多维用马氏距离——计入维度相关性与尺度，超卡方阈值判异常。软肋：分布假设现实中常不成立，复杂分布建模乏力。

📍 基于距离

不设分布假设，只数邻居：DB(pct, d_min）定义——至少 pct 比例的对象离它超过 d_min，就是异常点；实操常用 kNN 法：算每点到第 k 近邻的距离，降序取前 n 名。直观简单，但朴素实现 O(n²)，且在密度不均的数据上会把稀疏区的正常点误报。

🏦 金融

分类＋异常检测评贷款信用风险，关联分析揪可疑交易——重点在风控与欺诈。

🧬 生物信息

对基因表达数据做聚类与模式发现——对象是序列、网络与高维表达数据。

🌐 互联网

链接分析、推荐系统、点击流分析全靠大规模挖掘——重点在链接结构、用户行为与实时反馈。

🧩 复杂类型数据

• 图挖掘：频繁子图、社区发现、链接预测——社交与生物网络
• 文本挖掘：分词、向量表示、主题建模、情感分析（NLP 搭桥）
• 流数据挖掘：增量更新、有限内存下的近似处理——第 5 章流数据的算法面

🔒 隐私与治理

能力越大、边界越要清楚：个人信息保护、算法公平、结果可解释三题并存。匿名化挡不住重识别；差分隐私以受控噪声换可量化的隐私保证。落地靠技术＋制度＋审计共同约束，在数据价值与个人权益间划明边界。

📌 本章带走的六件事

• 挖掘是 KDD 的核心环节：知识要隐含、未知、有用、可理解；任务分预测型与描��型
• 预处理四工序：清洗、集成、变换、归约；距离类算法前先规范化
• 熵度量不确定性：增益选分裂、增益比纠偏——ID3/C4.5/CART 三代各进一步
• 关联规则三指标：支持度看普遍、置信度看可靠、提升度看相关；强规则过双门槛
• Apriori 靠先验性质剪枝逐层挖频繁项集；FP-growth 用树压缩免候选
• 聚类三法各表形状，异常三路各表假设；能力之外还有隐私与公平的边界

✍️ 课后思考

• 习题 2：年龄 35 在 [20,80] 规范化到 [0,1] 是多少？（第 9 页已现算）
• 习题 5:100 笔事务中 A∧B 共 20、A 25、B 40——三指标各是多少？提升度说明什么？
• 习题 8：给一家快递企业写一个挖掘闭环：数据、模式、决策、验证各一格