COMP5318 Week 02 数据预处理与 kNN 讲课总结

COMP5318 Week 02 讲课总结：Data Pre-processing and kNN

课程：COMP5318 / COMP4318 — Machine Learning and Data Mining，Semester 2 2026 讲师：Imdad Ullah；Slides 原作者：Irena Koprinska 参考章节：Tan ch.2；kNN 部分 Witten ch.4 pp.91–96 / 135–141 / 115–119，Tan ch.4 pp.208–212 来源：comp5318-week2-DataPreprocessing-kNN.pdf（61 页）+ Week 02 讲课字幕

老师开场点明本讲的两条主线：（1）为了让数据能喂给 ML 算法要做哪些预处理；（2）ML 的目标（objective）如何反过来决定你该怎么处理数据、选哪些特征。 第二条是本讲的隐藏主题——同样的数据，目标不同，预处理方式就完全不同。

---

一、数据的基本概念

1.1 术语对照

通俗说法	机器学习术语
一行 / 一条记录	Example（也叫 instance、record、observation、object）
一列	Attribute（也叫 feature、variable）
整个表	Data = a collection of examples
最后一列	Class（label / target）

老师强调的一点：class 列不是原始观测的一部分，是被引入的。谁引入？Domain expert。比如医生根据患者的各项指标判断属于哪种疾病，这个判断才成为 label。 因此：unsupervised learning 里这一列不存在；supervised learning 里它是训练数据的一部分。

1.2 属性类型

类型	定义	例子
Nominal（categorical）	取值属于预先指定的有限集合	outlook = {sunny, overcast, rainy}；temp = {hot, mild, cool}；windy = {true, false}
Numeric（continuous）	取值是数字	iris 数据集的 sepal length = 5.1、petal width = 0.2

本课两个贯穿全程的经典数据集：weather 数据集（nominal，outlook/temp/humidity/windy → play）和 iris 数据集（numeric，4 个花瓣萼片尺寸 → 3 种鸢尾）。

1.3 数据的多种形态（slide 5）

形态	例子
Data matrix	报税数据表（Refund / Marital Status / Taxable Income / Cheat）
Transaction data	购物篮：TID 1 → {Bread, Coke, Milk}
Graph	分子结构
Spatio-temporal	平均月度温度
Sequential	基因序列 GGTTCCGCCTTCAGCC...

老师在课上做了个测试：把标题遮住，人类看到"1 月冷、9 月凉"就知道这是温度；看到"面包、可乐、牛奶"就知道是超市。但机器不会。

1.4 语义从哪来（关键概念）

ML 算法天生不知道：Married 是一种婚姻状态、Bread 是一种杂货、A/C/G/T 是 DNA 碱基。

语义的四个来源：data schema、metadata、preprocessing / feature engineering、model design。

老师对 metadata 的解释：定义表的时候你就定义了每一列——marital status 是字符串、只接受字符；income 只接受数字加 K。每个属性都有它的 domain（取值域），DNA 就是取值域为 {A, C, G, T} 的有序序列。

1.5 转成机器可读格式（slides 6–7）

报税数据：

原始属性	转换
Refund	Yes → 1，No → 0
Marital status	Single → [1,0,0]，Married → [0,1,0]，Divorced → [0,0,1]
Taxable income	125K → 125000

交易数据（词表 = 5 种商品）：TID 1 = {Bread, Coke, Milk} → [1, 1, 1, 0, 0]

基因序列：A → [1,0,0,0]，C → [0,1,0,0]，G → [0,0,1,0]，T → [0,0,0,1]

⚠️ 老师在课上专门强调的考点：训练数据做了什么转换，测试数据必须做完全相同的转换。如果你用转换后的向量训练了一个基于距离的算法，测试时却直接喂 (No, Married, 100K)，结果会完全错。

1.6 完整 Pipeline（slide 8）

---

二、Data Cleaning

2.1 为什么需要：数据不完美

Noise 的三个来源：人工录入错误、测量仪器的局限、数据收集流程的缺陷。

老师补充的后果：噪声数据会带来大量额外计算、昂贵的执行开销，以及错误的预测。

2.2 噪声类型 1：Distortion of values（值失真）

例子：电话线路差时人声失真。

状态	能提取的特征
干净信号	frequency、pitch、amplitude、speech patterns 都能提取
加噪后	失真越高，信号形状可能完全丢失 → 语音识别系统会因背景噪声改变了音频特征而识别错单词

2.3 噪声类型 2：Addition of spurious examples（虚假样本）

• 有些远离其他样本，即 outliers
• 有些混在正常数据里

关键区别：Outlier 通常容易检测，因为它们是孤立的；而混在真实数据里的噪声点很难识别，因为它们看起来就像属于某个 cluster。

老师在课上带着学生分析了一张散点图，加噪前后的差异：

加噪导致的问题	说明
边界变模糊	加噪前能清楚画出决策边界，加噪后 boundary 变得 vague
误分类	基于模糊边界做分类，会产生 misclassification
凭空多出 cluster	噪声再多一点，原本 2 个 cluster 会被看成 3 个
训练结果整体不可靠	因为边界本身就没定义好

老师追问"多几个 cluster 有什么坏处"，答案是：每个 cluster 都有自己的特征，cluster 一多、样本一多、特征一多，训练的计算量就会急剧上升。

2.4 噪声类型 3：Inconsistent and duplicate data

例子：负的体重和身高、不存在的邮编、同一个人有两条记录。

这类噪声比前两类更容易检测和纠正。

2.5 降噪手段

手段	说明
前置处理	在 DM 之前用信号 / 图像处理和 outlier detection 技术
换算法	用对噪声更鲁棒的 ML 算法，在有噪声时也能给出可接受的结果

⚠️ 老师延伸出的重要问题：什么叫"可接受"？ - 电话通话质量掉 5%？你大概能接受，因为还听得清对方。 - 癌症检测错 5%？完全不可接受。

结论："acceptable result" 的标准由 domain expert 定义，不是算法工程师说了算。

另一个课后问答的观点也值得记：学生指出噪声不总是坏事——如果实际数据本来就有噪声，只在纯净数据上训练反而会导致模型在真实场景失效。老师承认这一点，并说清洗噪声没有通用方法，是 domain specific 的。

2.6 缺失值处理（slide 14）

为什么会缺失：传感器中途停止工作（比如太热）、人工录入出错等。

方法	适用条件
1) 直接忽略含缺失值的样本	缺失比例小时可行
2) 用剩余值估计	见下

估计的具体做法：

属性类型	做法
Nominal	① 用属性 A 的最常见值填充；② 在同一 class 的样本中找最常见值（仅 supervised learning）→ 可能更准确
Numeric	用最近邻（最相似样本）的平均值填充

老师补充的时间序列场景：观测通常是连续的（比如传感器按时间从左到右采集温度）。这时可以取一段窗口内的平均值填充。但窗口大小要谨慎：

温度用 24 小时平均会把午夜的 5°C 和白天的 15°C 抹平，所以应该用较小的窗口。窗口选多大，同样是 domain knowledge 问题。

---

三、Data Pre-processing

六大手段：data aggregation、dimensionality reduction、feature extraction、feature subset selection、converting attributes from one type to another、normalization。

3.1 Data Aggregation（数据聚合）

定义：把两个或多个属性合并成一个。

目的	说明
Data reduction	更少内存和计算时间；从而有余力使用计算上更昂贵的 ML 算法
Change of scale	提供高层视角，如城市 → 州 → 国家
More stable data	聚合数据的方差比未聚合数据小。例：每日食物摄入聚合成每周，能更可靠地理解饮食结构（碳水 / 脂肪 / 蛋白质）

缺点：可能丢失有意思的细节（potential loss of interesting details）。

关键练习：目标决定是否聚合（slide 17）

同样是"每日饮食摄入"数据，两个不同目标：

ML 目标	是否需要聚合？	理由
预测一个人是否有长期肥胖风险	需要	长期趋势，不关心每小时吃了什么，聚合成周 / 月的卡路里摄入即可
预测一个人明天是否会血糖飙升	不需要	身体的短期变化取决于早上具体吃了什么、热量如何，必须保留细粒度数据

这道题完美体现了本讲的隐藏主线：objective 决定预处理方式。

3.2 Feature Extraction（特征提取）

定义：从原始数据中创造特征——非常重要，且需要 domain expertise。

例 1：图像分类（室内 / 室外）

• 原始数据：每个像素的颜色值
• 提取的特征：colour histogram、dominant colour、edge histogram 等

例 2：映射到新空间再提取特征

新空间可能揭示重要特性。

原始信号是 2 个正弦波 + 噪声，直接看什么特征都提不出来。做 Fourier transform 后得到 power spectrum，出现对应两个正弦波周期的 2 个尖峰。

提取出的特征可以是：dominant frequency 1、dominant frequency 2、每个频率的 strength。

老师补充：强度很小的那些就可以当作噪声，强度大的才是真正的特征。

3.3 Feature Subset Selection（特征子集选择）

定义：移除不相关（irrelevant）和冗余（redundant）的特征，选出一个必要且充分的小特征集。

类型	例子（贷款申请）
Irrelevant	income ✓、repayment history ✓、favourite colour ✗
Redundant	annual income in dollars / annual income in thousands / monthly income —— 三者说的是一回事

为什么重要：

• 好的特征选择通常能提升准确率
• 用更少特征还意味着：更快构建分类器（降低计算成本）、分类规则更紧凑更易解释

老师的说法很直白：如果 10 个特征和 5 个特征的准确率没差别，为什么不用 5 个？

四种方法（slide 20，必考）

方法	做法	特点
Brute force	试所有可能的特征组合，选最好的	不实用。老师算过：30 个特征就是 亿种组合
Embedded	某些 ML 算法自动选特征	典型代表：decision tree（靠 < / > 阈值自然筛选特征）
Filter	在 ML 算法运行之前选好特征，与 ML 算法无关	基于统计量：information gain、mutual information、odds ratio；correlation-based feature selection
Wrapper	针对特定 ML 算法选最优子集，把算法当黑盒来评估不同子集	两种搜索策略：Forward selection（从无特征开始逐个加）、Backward elimination（从全部特征开始逐个删）

老师留作考题的问题（说"考试可能出类似的"）： 哪种方法最快？哪种最耗资源？（资源主要指 CPU 和内存，也可以算上能耗） 提示：brute force 显然最慢最耗资源；filter 最快（与算法解耦、只算统计量）；wrapper 要反复训练模型，代价高；embedded 介于中间（选特征"顺带"完成）。

3.4 Feature Weighting（特征加权）

定位：可以代替 feature reduction，也可以与之配合使用。

思路：重要的特征给高权重，不重要的给低权重。

方式	说明
Manually	基于 domain knowledge
Automatically	某些算法自动完成（如 boosting），或作为可选项（如 k-nearest neighbour）

在 kNN 中的体现：

普通 kNN 距离：

加权后：

核心思想：权重高的特征在构建模型时扮演更重要的角色。 例（贷款申请人）：， —— 银行认为负债比收入更能说明问题。 若想让两个特征同等重要，把 即可。

权重怎么定（slide 33）

没有单一的通用规则。

方法	说明
Domain knowledge	专家给更重要的变量更高权重
Statistical relationship with the target	例如与目标相关性更强的特征给更大权重
Optimisation using validation data	试不同权重组合，选验证集表现最好的
Learn automatically	某些 metric-learning 算法直接从训练数据学权重

示例：Debt = 0.50, Repayment history = 0.30, Income = 0.15, Age = 0.05 → （和为 1）

课堂讨论：权重一定要归一化到和为 1 吗？ 医生可能说某症状贡献 30%、另一个 50%、再一个 80%，加起来远超 100%。老师的结论是： 主要是语义和可解释性的理由——"加起来 100%"比"80% + 50%"好理解得多。 计算上影响很小，因为距离公式里只是做乘法。

3.5 类型转换：Discretization 与 Binarization

为什么需要：某些 ML 算法只接受数值 / 名义 / 二值属性，例如 linear 和 logistic regression 通常要求数值输入。

转换	定义	例子
Discretization	numeric → nominal	0–25 → Young，26–60 → Adult，61+ → Senior
Binarization	numeric / nominal → binary	Income > 100,000 → 1，Income ≤ 100,000 → 0

Binarization

没有最好的方法——最好的是对给定 ML 算法效果最好的那个，但不可能穷举评估所有可能。

简单技术：

One-hot encoding：每个类别一个位置，只有一个位置是 1，其余全 0。有 20 个类别就用 20 位的向量。

课堂上有学生问：为什么把数值先转成类别，最后又转回数字？ 老师的回答是计算与内存：如果收入取值是 100,001、100,002……你要为每一个值建立表示；但如果用区间，一整段范围只需要一个值（0 或 1 或 2）。既省内存又省计算。 用 3 个 bit 就能表示 5 个以上的类别，这就是紧凑表示的价值。

Discretization 的两大类

类型	是否用 class 信息
Unsupervised	不使用 class information
Supervised	使用 class information

两个必须做的决定：分几个区间（intervals）？ 切分点放在哪？

Unsupervised 的三种方法（假设用户指定 4 个区间）：

方法	做法
Equal width	4 个等宽区间，如 [0,5), [5,10), [10,15), [15,20)
Equal frequency	4 个区间，每个里面点数相同
Clustering（如 k-means）	由聚类方法决定 4 个区间

为什么这三种都是 unsupervised？ 因为没有任何一种方法在问："哪种区间边界最能预测目标类别？" 它们只是按宽度、按频数或按距离来切，从头到尾没用过 label。

老师在课上指出：k-means 的结果边界最清晰。

3.6 Normalization 与 Standardization

定义：把属性变换到新的取值范围，例如 。

为什么：避免大数值属性压倒小数值属性。

动机例子（slide 26）：

用 Manhattan 距离：

收入的差异完全主导，年龄根本没有贡献——等于说我们彻底忽略了年龄。

解法：先归一化 / 标准化，再算距离。

对使用距离或量级的算法尤其重要：k-NN、k-means、多数核的 SVM、PCA、神经网络。

两个公式（slide 27）

Normalization（也叫 min-max scaling）：

Standardization：

其中 是原值， 是新值， 是该属性的均值， 是该属性的标准差。逐属性（per attribute）进行。

老师对 standardization 的直觉解释：看一个值离均值有多远，再除以标准差。除以标准差是为了削弱异常值的影响——能看出哪个值在影响整体结果。 两者选哪个？都是可用的技术，都能降低某个属性的支配作用，按需选择。

归一化实例（slide 28）

假设 age: ；income: 。归一化后：

收入和年龄现在按比例贡献（各 0.2）。

⚠️ Slide 上专门标红的考点： min/max 或 mean/std 必须从 training data 计算，然后用同一组值去变换 test data。 这和 1.5 节"训练和测试必须用相同变换"是同一个原则。

---

四、Similarity Measures（相似度度量）

许多 ML 算法需要度量两个样本的相似性。两大类：Distance 和 Correlation。

4.1 数值属性的距离

设 的属性值分别为 和 。课上用的例子：

度量	公式	本例结果
Euclidean（L2 norm） ⭐最常用
Manhattan（L1 norm）

Minkowski distance —— Euclidean 与 Manhattan 的推广：

为正整数： → Manhattan； → Euclidean。

Weighted Euclidean（每个属性按重要性加权，需要 domain knowledge）：

4.2 二值向量的相似度

贯穿本节的例子：

Hamming distance

Hamming distance = 二值向量上的 Manhattan distance，即数不同的比特有几个。

本例：位置 1、7、10 不同 →

四个相似度系数

符号	含义	本例值
	匹配的 0-0 位数	7
	A 为 0、B 为 1 的位数	2
	A 为 1、B 为 0 的位数	1
	匹配的 1-1 位数	0

Simple Matching Coefficient (SMC)

本例： ——"如果匹配的 0 被认为有意义，两向量 70% 相似"。

⚠️ SMC 的致命问题（购物篮场景，必考）

设定：、 是两位顾客的超市账单，每个商品对应一个属性，值为 1 表示买了，0 表示没买。

问题：

SMC 会认为所有顾客的交易都相似！

原因链条：

1. 一次交易中没买的商品数量远远多于买了的
2. ⇒ 非常大（没买的商品）
3. ⇒ 很小（买了的商品）
4. ⇒ ， 的影响被完全淹没

更一般地：两个向量含有大量 0，即非常稀疏（sparse）⇒ SMC 不适合稀疏数据。

本例中 SMC 说两位顾客 70% 相似，但他们其实没有买过任何相同的商品——这个结论是错的。

Jaccard coefficient（解法）

只数匹配的 1-1，忽略匹配的 0-0。

本例： ——A 和 B 不相似，这才是正确答案。

什么时候用哪个？

场景	选择	理由
购物篮 / 稀疏数据	Jaccard	无意义且会淹没信号
医学检测结果	SMC	老师课上的例子：阳性和阴性的一致都重要——两人同为阴性也是有意义的相似

老师的总结：这个选择本质上取决于你的 ML objective——"两个都是 0" 这件事对你的问题有没有意义。

4.3 Cosine Similarity

其中 是向量点积， 是向量 A 的长度（模）。

适用：稀疏数据（二值和非二值都行），广泛用于文本文档分类。

几何解释：度量 与 之间的夹角。

取值	夹角	含义
1	0°	方向相同，非常相似
0	90°	垂直，在非负的文档场景下无重叠
(0, 1)	—	部分相似

计算实例（slide 39）

📌 Slide 上的一处笔误：把 写成了 2.245，正确值是 2.449。最终答案 0.3150 是按正确值算的（用 2.245 会得到 0.344）。做题时按 来。

文档分类的陷阱

假设词表 = [risk, rate, patient, bank]，要判断一篇新文档是医学还是金融文档：

词	判别力
patient	强 → 大概率是医学文档
bank	强 → 大概率是金融文档
risk、rate	弱 —— 两类文档里都会出现

问题：如果词表里只有 risk 和 rate，误分类的风险很高，只能得到"部分相似"这种模棱两可的结果。

改进：TF-IDF（term frequency–inverse document frequency）

给非常常见的词更低的权重，给有区分度的词更高的权重。

4.4 Correlation（相关性）

度量数值属性之间的线性关系。用 Pearson 相关系数：

其中

取值范围 ：

值	含义	例子
+1	完全正相关	学习时长 1 2 3 4 5 → 考试分数 50 60 70 80 90
−1	完全负相关	温度 10 20 30 40 50 → 供暖用量 100 80 60 40 20
0	无（线性）相关	—

三道课堂练习（slides 41–42，必做）

题	数据	答案
Ex1	，	，完全负线性相关（）
Ex2	，	，完全正线性相关（）
Ex3	，	，无线性相关。⚠️ 但存在非线性关系 ！

Ex3 是最重要的一题：相关系数为 0 ≠ 两个变量无关，只说明没有线性关系。

4.5 名义属性的距离

问题：数值属性可以直接相减（），但 high / low、yes / no、red / blue 相减没有意义。

做法：取决于任务和数据类型，需要 domain expertise 来引入属性语义。

Simple mismatch rule：

例子（slide 44）：两个属性 temperature（low / high）和 windy（yes / no）

⚠️ 序数属性的陷阱（老师课上专门讲的）

考虑 cold / mild / hot。用简单的 0/1 规则，cold 和 mild 的距离与 cold 和 hot 的距离都是 1。但这不对：

• cold → mild 只差 1 步
• cold → hot 差 2 步

解法：引入有序编码，例如 cold = 0, mild = 1, hot = 2，然后再算 Euclidean 距离。

有学生提出"不转成数字，直接做字符串匹配不行吗？"老师的回答： 可以，但会引入额外计算——比较字符串再判断 0/1，比直接用数字慢。

---

五、Nearest Neighbour 算法

5.1 分类任务的标准设置

给定：一组带类标签的样本。以 weather 数据集为例：14 个样本、4 个属性（outlook、temperature、humidity、windy）、class = play。

任务：构建一个模型（classifier），预测新的（未见过的）样本的类别。

例：预测 outlook=sunny, temp=hot, humidity=low, windy=true 的 class（yes / no）。

术语：

概念	定义
Training set	用来构建模型的样本
Test data	没有用于构建分类器的数据，也是带标签的
Accuracy	正确分类的测试样本比例

老师补充的实操细节：通常把数据集按 70/30 或 80/20 划分成 training / test。在 test 上跑完之后，因为原本就有标签，可以对比出准确率。 - 100% → 可以部署 - 只有 50% → 需要调整：是不是特征选得不好？数据是不是需要清洗？

医院的例子：200 万患者数据，70% 训练、30% 测试，准确率达标后部署；新患者来了就能预测可能的疾病。医生仍然需要——系统只是给出提示，剩下的诊断由医生完成。

5.2 算法本身

1. 记住所有训练样本
2. 对新的未标注样本：用距离度量找到最近的训练样本，用它的类标签作为预测结果

课上的可视化例子：两个数值特征 、，判断一个未知点是 swan 还是 chicken。

5.3 计算实例（slides 50–51，54，必考题型）

数据集：4 个样本，3 个数值特征 ，class 取 yes / no。

#				class
1	1	3	1	yes
2	3	5	2	yes
3	3	2	2	no
4	5	2	3	no

新样本：

Euclidean 距离计算：

算法	用到的邻居	预测
1-NN	最近的是 （）	yes
3-NN	(yes)、(yes)、(no) → 多数为 yes	yes

5.4 从 1-NN 到 k-NN

• 用最近的 1 个样本 → 1-Nearest Neighbor
• 用最近的 k 个样本 → k-Nearest Neighbor，用 majority voting（多数投票） 决定

为什么 k 常取奇数（3, 5, 7）？ 在二分类中减少投票平局（voting ties）。 若取偶数，可能出现 3 票 chicken vs 3 票 swan，无法判定。

k 的取值：

规则	内容
经验法则
商业软件	通常用 k = 10
效果	邻居越多，对噪声样本越鲁棒

k-NN 也能做回归：

预测值 = k 个最近邻的 class 值（数值）的平均。

5.5 ⚠️ 关键局限：baby swan 问题（slide 52）

如果一只幼年天鹅和一只成年鸡有完全相同的特征呢？

模型会把它判成 chicken。原因：

A classifier can only distinguish classes using the information contained in its features. （分类器只能用特征里包含的信息来区分类别。）

解法：增加更多、更有区分度的特征——比如加上羽毛颜色、喙的形状等，让幼年天鹅和成年鸡不再落在同一位置。

5.6 Weighted Nearest Neighbour（距离加权）

核心思想：更近的邻居应该算得更重。

Distance-weighted nearest-neighbour 算法：

1. 找到 k 个最近邻
2. 按它们到新样本的距离给投票加权
   • 越近 → 权重越大
   • 越远 → 权重越小
3. 例如权重取

注意区分 5.6 的距离加权（对邻居加权）和 3.4 的特征加权（对特征加权），两者都可以在 kNN 里用。

5.7 决策边界：Voronoi Diagram（slide 56）

• NN 分类器产生的决策边界形状是任意的（arbitrary shape）
• 1-NN 对噪声敏感
• 1-NN 的边界由 Voronoi 图中分隔两类点的边构成

Voronoi region：

1-NN 的几何表示。每个训练样本都有一个对应的 Voronoi 区域，这个区域包含所有"以该样本为最近邻"的数据点。

即：每个训练点都有自己的"领地"。

老师专门澄清的两点： 1. 1-NN 对噪声敏感的具体表现：如果有一只噪声鸡落在天鹅群里，它会自己形成一个小岛（tiny island）——下次任何落在这个小岛里的点都会被判成 chicken。 2. ⚠️ Voronoi 图只是理解用的几何表示，训练时并不需要真的去计算它。 实际跑 kNN 就是算距离而已。Python 库能画出来，但那是可视化，不是算法步骤。

5.8 k-NN 讨论总结（slide 57，必考）

特性	说明
✅ 常常非常准确	自 1950 年代起就在统计学中使用
❌ 大数据集上慢	见下节复杂度
⚠️ 基于距离 → 必须归一化	呼应 3.6 节
—	产生任意形状的决策边界，由 Voronoi 边的一个子集定义
❌ 对高维数据无效	"nearness"（接近）的概念在高维空间失效。解法：dimensionality reduction 和 feature selection
⚠️ 对 k 的取值敏感	：非常灵活，但对噪声敏感 或 ：通常更稳定 k 很大：可能过度平滑，忽略局部模式

总结句：k-NN 简单灵活，但它的成功高度依赖于好的特征、恰当的缩放、合理的 k 值，以及一个"距离仍然有意义"的数据集。

5.9 计算复杂度（slides 58–60）

关键特性：

不构建模型（No model is built），只是存储训练样本。

这就是所谓的 lazy learner —— 训练阶段几乎零成本，所有代价都在预测时。

分类（预测一个新样本）的复杂度：

把每个未见样本与每一个训练样本比较。若有 个训练样本、维度为 ：

具体例子：

内存需求：同样是 —— 需要存储大约 个特征值。

规模化的问题：

1000 万客户 × 每人 100 个特征 —— 每分类一个新客户就要和 1000 万条记录比对，代价极高。

结论：因时间和内存需求，对大数据不实用。

优化方案：

用更高效的数据结构：KD-trees 和 Ball trees（Witten pp.136–141）。 核心思想：组织训练数据，使得搜索空间的大部分可以被直接跳过。

老师给的直觉类比：

场景	做法
找最近的餐厅，没有索引	检查悉尼每一家餐厅的距离
有空间索引	先搜索你周边区域，直接忽略明显很远的区域

KD-tree 对特征向量做的就是同一件事。

---

六、考点重点

1. 术语：example / instance / record / observation / object 是行；attribute / feature / variable 是列。class 列由 domain expert 引入，不是原始观测。
2. ⭐ 训练与测试必须使用完全相同的变换——包括编码方式，以及 normalization 的 min/max 和 standardization 的 mean/std 都要从 training data 算出后套用到 test data。这是两个高频考点。
3. 噪声三类型：distortion of values、addition of spurious examples（outlier 易检测，混入的难检测）、inconsistent & duplicate data（最易检测纠正）。
4. 缺失值：小比例可直接删；nominal 用最常见值或同类中最常见值（supervised 更准）；numeric 用最近邻的平均。
5. Aggregation 的三个目的 + 一个缺点：data reduction、change of scale、more stable data；缺点是丢失细节。会判断给定目标是否需要聚合（长期肥胖 → 聚合；明日血糖 → 不聚合）。
6. ⭐ Feature selection 四方法：brute force（不实用，）、embedded（决策树）、filter（独立于算法，用 information gain / mutual information / odds ratio / correlation）、wrapper（针对特定算法，forward selection / backward elimination）。要会比较速度与资源消耗。
7. Irrelevant vs Redundant 特征：贷款例中 favourite colour 是 irrelevant；三种收入表示是 redundant。
8. Normalization vs Standardization 公式要能默写；知道为什么需要（避免大数值属性支配）以及哪些算法必须做（kNN、k-means、SVM、PCA、神经网络）。
9. Discretization 三种 unsupervised 方法：equal width、equal frequency、k-means。要能解释为什么它们都是 unsupervised（没有任何一个在问"哪个边界最能预测 class"）。
10. ⭐ 距离度量：Euclidean（L2）、Manhattan（L1）、Minkowski（ Manhattan， Euclidean）、Hamming（= 二值 Manhattan）。会手算 、 → 5 和 7。
11. ⭐ SMC vs Jaccard：会算 ；记住购物篮例子 SMC = 0.7（错）vs Jaccard = 0（对）；SMC 不适合稀疏数据；医学检测（阴阳都重要）该用 SMC。
12. Cosine similarity：公式、几何含义（1 = 同向、0 = 垂直）、适合稀疏 / 文本数据；TF-IDF 的作用是降低常见词权重、提高区分词权重。
13. ⭐ Correlation：取值 ；会做三道练习；最重要的是 Ex3—— 只说明没有线性关系， 仍然是强关系。
14. 名义属性距离：simple mismatch rule（相同 0、不同 1）；序数属性（cold/mild/hot）要用有序编码 0/1/2，否则丢失顺序信息。
15. ⭐ kNN 手算：会算 那道题，1-NN 和 3-NN 都答 yes。
16. k 的选择：取奇数避免平局；；商业软件常用 k=10； 灵活但敏感、 稳定、k 太大过度平滑。
17. kNN 的两种加权要分清：feature weighting（对特征加权）vs distance-weighted kNN（对邻居按 加权）。
18. kNN 也能做回归：取 k 个邻居 class 值的平均。
19. Voronoi diagram：1-NN 的决策边界；每个训练点有自己的区域；只是几何理解工具，实际不需要计算。
20. ⭐ 计算复杂度：不建模型（lazy learner）；分类复杂度 ，内存 ；会算 ；优化用 KD-trees / Ball trees。
21. baby swan 问题：分类器只能用特征里包含的信息——特征不足就无法区分，解法是加特征。

---

七、本讲的一条主线

把老师反复强调的那句话拎出来：

你的 ML objective 决定一切。

• 目标决定要不要聚合（长期肥胖 vs 明日血糖）
• 目标决定选哪些特征、给什么权重（银行看 debt 还是 income）
• 目标决定用 SMC 还是 Jaccard（"两个都是 0" 有没有意义）
• 目标决定什么叫"可接受的准确率"（通话质量 vs 癌症检测）

而这些判断大多不是算法能给你的，需要 domain knowledge。这也是 Week 1 那句"数据挖掘是交叉学科"的具体落地。