Data Mining 课程复习笔记

笔记目录

认识数据
数据预处理
朴素贝叶斯分类器
决策树分类
基于规则的分类
回归算法
支持向量机 SVM
模型的评价

这里只记载一些重要的知识点 or 需要死记硬背的定义（sad）

这篇笔记中夹杂了许多个人学习时的吐槽，希望可以缓解诸位的背书负担 🎩

附录：

错题大赏会
考试回忆录

认识数据

这一节非常无趣且都是死记硬背的知识点，主要由以下几部分组成：

基本概念 | 数据统计的方法 | 相似性度量｜数据可视化｜复习小巧思

part one

数据的基本概念

一句话总结：数据（总体） > 数据对象（比如一张统计表） > 数据元素（表中的列） > 数据项（每列的具体值）

数据属性

阅读参考书目，感觉这里的数据属性指的是机器学习中数据的特征（比如Titanic数据集中的Age、Sex等）

比较搞人的是这里对数据属性也进行了分类，分为四种

标称属性：感觉这里指的是对数据的命名，比如 fanqi 养的六只猫需要六个不同的名字来区分
二元属性：只有两种取值的标称属性
序数属性：比如大中小，但是不知道大究竟是多少（定性分析）
数值属性：分成区间标度（我身高 180cm 比他高 2 cm）和比率标度（我跑步10km/h 比他快一倍）

‼️ 定性属性：标称 & 序数定量属性：区间 & 比率

part two - 数据统计的基本方法

标准差 $\sigma = \sqrt{\frac{1}{n} \sum_{i=1}^n (x_i - \overline{x})^2}$

差异系数 $CV = \frac{\sigma}{mean(x)}$

四分位极差 (range)

$IQR = Q_3 - Q_1$

$\max = Q_3 + 1.5 IQR$ 而 $\min = Q_1 - 1.5 IQR$

‼️ 这里的 max 和 min 不是数据集中的最大最小值，而是用来判断离群点的阈值

离群点检测除了上述计算方法外还有 LOF 方法，越大（ >1 之后）越离群

偏度系数 $SK = \frac{(mean - median)}{\sigma}$

峰度系数 $K = \frac{1}{n} \sum_{i=1}^n \left( \frac{x_i - mean}{\sigma} \right)^4$ （正太分布的峰度系数为3）

part three - 数据相似性度量

标称属性的近邻性度量：

$$ d(i,j) = \frac{p - m}{p} $$

其中 p 为属性总数，m 为两个对象在属性上取值相同的个数

二元属性的计算则可以画表来表示，令q r s t 分别表示如下四种情况的个数：

	Object j = 1	Object j = 0
Object i = 1	q	r
Object i = 0	s	t

常用的距离计算方式： $d(i,j) = \frac{r + s}{q + r + s + t}$

而倘若我们只关心两个对象同时为1的情况，则变为 $d(i,j) = \frac{r + s}{q + r + s}$ （理解起来也比较简单，比如疾病检测我们只关心阳性 😼）

补充：Jaccard系数： $sim(i,j) = \frac{q}{q + r + s}$

序数属性的近邻性计算（说成人话就是数据的各种距离度量）

(1) 闵可夫斯基距离

$$ d(i,j) = \left( \sum_{k=1}^{n} |x_{ik} - x_{jk}|^p \right)^{\frac{1}{p}} $$

根据 p 的不同取值，可以得到不同的距离计算方式

当 $p = 1$ 时，为曼哈顿距离
当 $p = 2$ 时，为欧氏距离
当 $p \to \infty$ 时，为切比雪夫距离

对于距离度量，他们都满足三种性质：非负性、对称性、三角不等式

(2) 余弦相似性

$$ sim(i,j) = \frac{\sum_{k=1}^{n} x_{ik} \cdot x_{jk}}{\sqrt{\sum_{k=1}^{n} x_{ik}^2} \cdot \sqrt{\sum_{k=1}^{n} x_{jk}^2}} = \frac{x_i \cdot x_j}{||x_i|| \cdot ||x_j||} $$

part four - 数据可视化

书本中介绍了三个可视化方法，分别是箱线图可视化、直方图可视化、散点图可视化

小结

💡 这一部分需要记住：数据的四种类型、四分位极差和那个神奇的 min、max 计算方式，还有一些新引入的概念如偏度、峰度系数

数据预处理

这一节主要包含以下四个部分：

数据清洗 | 数据集成 | 数据规约 | 数据转换

进行数据预处理，主要目的是提升数据的质量，书中给了数据质量的衡量标准：准确性、完整性、一致性、合时性、可信性、可理解性等

数据清洗

缺失值处理方法：忽略元组、手动填写缺失值、自动填写（各种方法都可以）

噪声数据：离群点分析（这里就涉及到上一节里算出来的 max 和 min 了）、回归方法

数据不一致：开动我们的小脑瓜

数据集成

应该是为了缓解数据冗余，数据集成做的事情是将多个数据源进行合并

相关性分析

离散变量：chi-square 统计量：

$$\chi^2 = \sum_{i=1}^{r} \sum_{j=1}^{c} \frac{(o_{ij} - e_{ij})^2}{e_{ij}}$$

Tip : 上述表达式中，o 为观测值，e 为期望值 expected 的计算可以采用变量独立性假设来计算联合概率分布 $e^{ij} = \frac{(row_i) \times (column_j)}{total}$

连续变量：皮尔逊相关系数

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

根据 r 的取值划分成三级：$|r| < 0.4$ 为低度线性相关，$0.4 \leq |r| \leq 0.7$ 为显著性相关，$|r| > 0.7$ 为高度线性相关

补充：相关系数矩阵的计算

$$ R = \begin{bmatrix} 1 & r_{1,2} & \cdots & r_{1,n} \\ r_{2,1} & 1 & \cdots & r_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ r_{n,1} & r_{n,2} & \cdots & 1 \end{bmatrix} $$

其中

$$r_{i,j} = \frac{\sum_{k=1}^{n} (x_{k,i} - \overline{x_i})(x_{k,j} - \overline{x_j})}{n \cdot \sigma_i \sigma_j}$$

协方差分析

$$cov(A,B) = \frac{\sum_{i=1}^{n} (a_i - \overline{A})(b_i - \overline{B})}{n}$$

Tip : 协方差为 0 不一定代表两个变量是独立的（除非加上如服从正态分布等假设条件）

数据规约（人话版：如何节省存储空间）

思路一：数据降维（主成分分析PCA大法）

思路二：降数据（抽样法）

抽样法：简单随机抽样（SRS，又分成有放回与无放回）、分层抽样等

思路三：数据压缩

数据转换

数据转换就两种类型，一类规范化，另一类就是离散化

规范化

最小-最大规范化 $$v' = \frac{v - min_A}{max_A - min_A} (new\_{max_A} - new_{min_A}) + new_{min_A}$$
Z-Score 规范化 $$v' = \frac{v - \overline{A}}{\sigma_A}$$
小数定标规范化 $$v' = \frac{v}{10^j}$$ 其中 j 是使用该方法后，$|v'| < 1$ 的最小整数

离散化

💡 题目中经常把等宽、等频叫做 “分箱”

等宽法：将数据划分成宽度相等的区间（工资划分为低（0-3）、中（3-6）、高（6-9））
等频法：将数据划分成频率相等的区间（每个区间包含相同的数据点）
聚类：k-means等

‼️ 上面提到的三种方法都是非监督方法

朴素贝叶斯分类器

这部分内容构成方式为: 基本概念 | 例题｜总结

‼️ 贝叶斯分类器的目标是利用似然概率和先验概率 预测后验概率

基本概念

这一部分的核心就两点，第一点是贝叶斯定理

$$ P(A|B) = \frac{P(B|A) P(A)}{P(B)} $$

我们的目标是在给定数据分布 D 的条件下，找出最有可能的假设 h，即

$$ h_{MAP} = \arg\max_{h \in H} \frac{P(D|h) P(h)}{P(D)} = \arg\max_{h \in H} P(D|h) P(h) $$

第二个比较重要的就是 独立性假设

$$ h_{MAP} = \max_{h \in H} \Pi_{i=1}^{n} P(d_i | h) P(h) $$

例题

这篇文章举的例子就是一个不错的例题 😼

带你理解朴素贝叶斯分类算法 - 忆臻的文章 - 知乎

除此之外，参考书籍上还由电脑购买、垃圾邮件判断的例题

总结

贝叶斯分类器的特点：（这里是直接照搬的书籍）

属性可以离散也可以连续
数学基础坚实，分类效率稳定
对缺失和噪声数据不太敏感
属性如果不相关，分类效果很好

决策树分类

这一章介绍了四类决策树算法，决策树可以看作是基于规则的分类器

Hunt 算法

这种算法不需要考虑划分节点的信息属性，只需要递归的添加划分节点，直到所有叶节点都是单一类别为止

这牵扯到两个问题

怎样为不同类型的属性指定测试条件
怎样选择最佳划分

下面三种算法就是为了解决第二个问题二提出的

ID3 算法

ID3 算法使用信息增益作为划分属性的选择标准

$$\begin{aligned} Entropy(D) &= - \sum_{i=1}^{m} p_i \log_2(p_i) \\ Entropy_A(D) &= \sum_{j=1}^{v} \frac{|D_j|}{|D|} \times Entropy(D_j) \\ Gain(A) &= Entropy(D) - Entropy_A(D) \end{aligned}$$

C4.5 算法

C4.5 算法使用信息增益率作为划分属性的选择标准

$$\begin{aligned} SplitInfo_A(D) &= - \sum_{j=1}^{v} \frac{|D_j|}{|D|} \log_2 \left( \frac{|D_j|}{|D|} \right) \\ GainRatio(A) &= \frac{Gain(A)}{SplitInfo_A(D)} \end{aligned}$$

CART 算法

CART 算法使用基尼指数作为划分属性的选择标准

$$\begin{aligned} Gini(D) &= 1 - \sum_{i=1}^{m} p_i^2 \\ Gini_A(D) &= \sum_{j=1}^{v} \frac{|D_j|}{|D|} \times Gini(D_j) \\ \Delta Gini(A) &= Gini(D) - Gini_A(D) \end{aligned}$$

决策树算法防止过拟合可以通过预剪枝和后剪枝两种方式实现

基于规则的分类

$$ (Condition) \to (Class) $$

在介绍如何制定划分规则之前，先对规则的评估方法进行介绍

规则的评估

覆盖率
准确率

根据这两种规则的指标，我们可以制定出规则的优先级

选择规则排序时，第一种方案是按照规则的质量进行排序，第二种方案是按照规则所属的类别进行排序

构造规则集的一个最基础的方法是顺序覆盖 + 删除实例

为什么删除实例：避免规则重复为什么删除正实例：防止高估后面规则的准确率，确保下一个规则不同为什么删除负实例：防止过拟合错误数据集，防止低估下一个规则的准确率

很奇怪的一点，书本上举的例子，对于企鹅这反例的删除位置很古怪，目前还没看明白

Learn One Rule 算法

该算法主要由以下步骤组成

规则增长：方案一是从一般到特殊，方案二是从特殊到一般

规则评估：准确率、似然比、Laplace、FOIL

似然比：

$$R = 2 \sum_{i = 1}^{k} f_i \log \left( \frac{f_i}{e_i} \right)$$

FOIL：

$$FOIL = f \left( \log_2 \left( \frac{f}{f + n} \right) - \log_2 \left( \frac{F}{F + N} \right) \right)$$

Laplace：

$$Laplace = \frac{f + 1}{n + k}$$

停止条件

规则剪枝

💡 这里简单介绍一下 lazy learning 与 eager learning 两种分类方法

回归算法

本章内容主要包含以下几部分：

线性回归 | 最小二乘法 | 梯度下降算法 | 逻辑回归 | 决策树回归

回归问题是什么，简单来说就是对两个变量之间的关系进行建模

线性回归

在该问题背景下，我们假设两个变量之间满足最简单的关系——线性关系

$$ y = ax + b $$

那么分析的目标就是找出“最优”的 a 和 b 值

最小二乘法

嘿！现在的问题就变成了如何定义这个优了，当然可以使用点到直线的距离衡量，但是更常用的方法是最小二乘法

$$ E(a,b) = \sum_{i=1}^{n} (y_i - (a x_i + b))^2 $$

如果我们令$\overline{x} = \frac{1}{n} \sum_{i=1}^n x_i$ 和 $\overline{y} = \frac{1}{n} \sum_{i=1}^n y_i$，那么最优的 a 和 b 可以通过以下公式计算得到：

$$ a = \frac{\sum_{i=1}^{n} (x_i - \overline{x})(y_i - \overline{y})}{\sum_{i=1}^{n} (x_i - \overline{x})^2} = \frac{\sum_{i=1}^{n} x_i y_i - n \overline{x} \overline{y}}{\sum_{i=1}^{n} x_i^2 -n \overline{x}^2} $$

$$ b = \overline{y} - a \overline{x} $$

梯度下降算法

之前求解最优 a 和 b 的方法是通过解析解的方式求解的，除此之外，还可以使用数值解法——梯度下降法

一些注意事项

学习率 $\eta$ 的选择不能太大也不能太小（老生常谈了）
收敛到的结果未必是全局最优值

逻辑回归

逻辑回归个人感觉放在这里怪里怪气，它算是一种分类算法吧（相信书本这么安排肯定有它的道理 🤨）

逻辑回归的核心思路是，将回归的输出结果转化为 0 - 1 的概率值

线性回归的原始输出为 $ax + b \in \mathbb{R}$，使用 sigmoid 可以将其转化为 0 - 1 之间的概率值

$$ P(y = 1 | x) = \frac{1}{1 + e^{-(a x + b)}} $$

BUT：sigmoid 带来了一个问题，如果仍使用之前的平方损失函数，那么这个结果是非凸的，从而无法使用梯度下降法进行优化

直觉上告诉我们，对于 $P(y|x)$ 正确分类时肯定越大越好

那么我们可以构造出

$$ P(y|x) = p_i^{y_i} (1 - p_i)^{1 - y_i} $$

其中 $p_i = P(y_i = 1 | x_i)$

为了方便计算，我们对其取对数

$$\log(P(y|x)) = y_i \log(p_i) + (1 - y_i) \log(1 - p_i)$$

那么简单推导可以得出

$$\begin{aligned} \log(P(y|x)) &= y_i (a x_i + b) - \log(1 + e^{a x_i + b}) \quad (算作\ \ln L)\\ \log \left( \frac{p_i}{1 - p_i} \right) &= a x_i + b \quad (算作\ logit) \end{aligned}$$

这个损失函数的最终形式和线性模型一样

ln L 损失函数使用的是经验风险最小化，不是结构风险最小化，泛化能力差，容易过拟合（摘抄自书后习题）

优势比 OR（Odds Ratio）

对于上述二分类的情况，优势比就等于 $e^a$

$$OR = \frac{(p_1)(1 - p_1)}{(p_0)(1 - p_0)}$$

其中 $p_1$ 和 $p_0$ 为在第 j 个特征分别取值为 $c_1$ 和 $c_0$ 时属于正类的概率

对 OR 取对数

$$\log(OR) = \log \left( \frac{p_1}{1 - p_1} \right) - \log \left( \frac{p_0}{1 - p_0} \right) = \beta_j (c_1 - c_0)$$

那么 OR 可以表示为

$$OR = e^{\beta_j (c_1 - c_0)}$$

如果我们令 $c_1 - c_0 = 1$，那么

$$ OR = e^{\beta_j} = \begin{cases} > 1 & \beta_j > 0 \\ = 1 & \beta_j = 0 \\ < 1 & \beta_j < 0 \end{cases} $$

三种情况分别对应危险因子、无作用、保护因子

参数估计

对于一个实际发生的样本 $i$，它的概率可以表示为

$$P(y_i | x_i) = p_i^{y_i} (1 - p_i)^{1 - y_i}$$

那么似然函数可以表示为

$$ L = \prod_{i=1}^{n} p_i^{y_i} (1 - p_i)^{1 - y_i} $$

对似然函数取对数，得到对数似然函数

$$\begin{aligned} \log L &= \sum_{i=1}^{n} \left( y_i \log(p_i) + (1 - y_i) \log(1 - p_i) \right) \\ &= \sum_{i=1}^{n} \left( y_i \log \frac{p_i}{1 - p_i} - \log(1 - p_i) \right) \\ &= \sum_{i=1}^{n} \left( y_i (a x_i + b) - \log(1 + e^{a x_i + b}) \right) \end{aligned}$$

当 $\log L$ 取到最大值时，逻辑回归的参数估计也就完成了

正则化

这一部分和正常的机器学习正则化方法类似，主要是为了防止过拟合

L1 正则化（Lasso 回归）：偏好稀疏编码
L2 正则化（Ridge 回归）：偏向于整体更小

决策树回归

决策树回归的思想比较简单，就是每次将数据所在的空间一分为二，下面的内容也集中在如何选择最优划分节点上了划分节点的选择很简单，遍历所有的可能划分点，选择使得划分后的均方误差（MSE）最小的点

很有意思的是，在完成上面一次划分后，可以使用残差

$$r_i = y_i - \hat{y_i}$$

来继续进行划分，从而得到更好的拟合效果 (提升树)

决策树回归相当有趣，可以看课本上的具体例子辅助理解

支持向量机 SVM

SVM 问题的损失函数叫做 Hinge Loss $\to$ $\max(0, 1 - y_i(w^Tx_i + b))$

问题推导：SVM 的目标很简单，就是希望在两个类别之间找到一个最优的划分超平面，先假设数据是线性可分的，而且一个类别为 +1，另一个类别为 -1，那么划分超平面可以表示为

$$\begin{aligned} &w \cdot x + b \\ &w \cdot x + b <= -1 \quad for \quad y_i = -1 \\ &w \cdot x + b >= 1 \quad for \quad y_i = +1 \end{aligned}$$

结合之前学习过的凸优化知识，可以将 SVM 转化为如下所示的优化问题

$$\begin{aligned} &\min \quad \frac{1}{2} ||w||^2 \\ &s.t. \quad y_i (w \cdot x_i + b) >= 1, \quad i = 1, 2, \ldots, n \end{aligned}$$

求解该优化问题可以使用拉格朗日对偶方法，构造拉格朗日函数

$$L(w, b, \alpha) = \frac{1}{2} ||w||^2 - \sum_{i=1}^{n} \alpha_i [y_i (w \cdot x_i + b) - 1]$$

那么求解该优化问题就变成了求解下面的优化问题

$$\begin{aligned} &\min_{w,b} \max_{\alpha >= 0} \left( \frac{1}{2} ||w||^2 - \sum_{i=1}^{n} \alpha_i [y_i (w \cdot x_i + b) - 1] \right) \\ = & \max_{\alpha >= 0} \min_{w,b} \left( \frac{1}{2} ||w||^2 - \sum_{i=1}^{n} \alpha_i [y_i (w \cdot x_i + b) - 1] \right) \end{aligned}$$

上述交换成立的前提是满足 KKT 条件
$$\begin{aligned} &a_i \ge 0 \\ &y_i (w \cdot x_i + b) - 1 \ge 0 \\ &\alpha_i [y_i (w \cdot x_i + b) - 1] = 0, \quad i = 1, 2, \ldots, n \end{aligned}$$

通过对拉格朗日函数分别对 w 和 b 求偏导，并令其为 0，可以得到

$$\begin{aligned} &w = \sum_{i=1}^{n} \alpha_i y_i x_i \\ &\sum_{i=1}^{n} \alpha_i y_i = 0 \end{aligned}$$

最终模型可以表示为

$$f(x) = \text{sign} \left( \sum_{i=1}^{n} \alpha_i y_i x_i^T \cdot x + b \right)$$

KKT 条件保证了只有支持向量对应的 $\alpha_i$ 不为 0，因此最终模型只与支持向量有关

当然，SVM 还有软间隔和核函数的内容，不过这里就不展开介绍了 😶

需要知道 Kernel 可以处理非线性可分问题，将数据映射到高维空间

常见核函数

高斯 RBF 核函数 $$K(x_i, x_j) = \exp \left( - \frac{||x_i - x_j||^2}{2 \sigma^2} \right)$$
齐次多项式核函数 $$K(x_i, x_j) = (x_i \cdot x_j)^d$$
非齐次多项式核函数 $$K(x_i, x_j) = (x_i \cdot x_j + 1)^d$$
sigmoid 核函数 $$K(x_i, x_j) = \tanh(k x_i \cdot x_j + \theta)$$

模型的评价

本章一共由三个部分组成：分类模型评价指标 | 不平衡分类问题 | 过拟合 & 欠拟合

分类模型评价指标

这一节的核心内容应该就是 ROC 曲线，需要知道 FP FN TP TN 的计算、Precision 和 Recall 以及 F1-score 是什么

TP：将正类正确分类为正类的数量

TN：将负类正确分类为负类的数量

FP：将负类错误分类为正类的数量

FN：将正类错误分类为负类的数量

准确率 (Accuracy)：分类器正确分类的比例

$$Accuracy = \frac{TP + TN}{TP + TN + FP + FN}$$

精确度 (Precision)：正类预测中真正类所占的比例

$$Precision = \frac{TP}{TP + FP}$$

需要注意 Precision 和 Accuracy 二者的不同 ⚠️

召回率 (Recall)：正类被正确预测的比例

$$Recall = \frac{TP}{TP + FN}$$

F1-score：准确率和召回率的调和平均数

$$F1 = 2 \times \frac{Precision \times Recall}{Precision + Recall}$$

ROC 曲线

TPR（真正率）和 FPR（假正率）的计算

$$\begin{aligned} &TPR = \frac{TP}{TP + FN} \quad (Recall) \\ &FPR = \frac{FP}{FP + TN} \end{aligned}$$

三种常见情况

(FPR, TPR) = (0, 0)：将所有样本都预测为负类
(FPR, TPR) = (1, 1)：将所有样本都预测为正类
(FPR, TPR) = (0, 1)：完美分类器

不平衡分类问题

这一块的知识点还蛮重要的，至少在课本后面的题目中经常见到

核心目标是解决样本数据集不平衡导致分类器偏向于多数类的问题

第一种方法：重采样，包括过采样和欠采样

过采样：增加少数类样本数量（可能导致过拟合）
欠采样：减少多数类样本数量（可能训练不充分，但是可以通过多次采样缓解）

第二种方法：两阶段学习，分为特征学习与分类器学习

两阶段学习：PN-Rules
- 基于规则的分类
- 学习分成两个阶段，每个阶段学习一组规则
训练也包含两个阶段
- 阶段一：学习一组规则，尽可能覆盖正类（少数类）
- 阶段二：使用阶段一覆盖的正负样本以及少部分为覆盖的负样本，学习一组规则
分类使用两组规则
- 先使用阶段一的规则进行分类，若分类为负类则输出负类
- 否则使用阶段二的规则进行分类，若分类为正类则输出正类，否则输出负类

第三种方法：代价敏感学习

通过调整不同类型分类错误的代价，来缓解不平衡分类问题
代价矩阵

	Predicted Positive	Predicted Negative
Actual Positive	0	$C_{FN}$
Actual Negative	$C_{FP}$	0

F1-score 在不平衡分类问题中更有意义，它更强调精确率和召回率，但不考虑误分类代价

过拟合 & 欠拟合

过拟合的原因：噪声导致的过拟合、缺乏代表性样本导致的过拟合

减少泛化误差的方法：添加正则化项、Dropout、交叉验证

过拟合	欠拟合
低偏差	高偏差
高方差	低方差

关联规则挖掘

内容主要包含以下几部分：

基本概念 | Apriori算法 | FP-Growth算法

基本概念

在前面讲述过了规则的定义，那就可以开始学习关联规则挖掘了，如果我们提出假设 $A \to B$，那么我们需要评估这个假设的质量，常用的评估指标有以下三种： 支持度 (Support)

AB在一起出现的频率

$$Support(A \to B) = P(A \cup B) = \frac{count(A \cup B)}{N}$$

置信度 (Confidence)

B 在 A 发生的条件下发生的概率

$$Confidence(A \to B) = P(B|A) = \frac{count(A \cup B)}{count(A)}$$

提升度 (Lift)

衡量规则 $A \to B$ 对 B 发生的影响程度

$$Lift(A \to B) = \frac{P(B|A)}{P(B)} = \frac{Confidence(A \to B)}{P(B)}$$

❗️ 记住上面三种评估指标的计算公式

Apriori算法

⚠️ 候选项集生成的一个重要策略是，在删除最后一个项后，前面的项相同才能合并

‼️ 如果生成的一个项，他的所有子集有不是频繁的情况，需要剪枝删除

FP-Growth算法

集成学习

AdaBoost 算法

不断关注前一轮分类失败的样本，将多个弱学习器组合成一个强学习器

理论上可以训练出误差任意低的分类器，但是弱分类器要求正确率大于 50%

一般损失函数为指数函数

具体流程

初始化样本权重 $$ w_i = \frac{1}{N}, \quad i = 1, 2, \ldots, N $$
对 m = 1, 2, …, M 重复以下步骤
1. 使用加权样本训练弱分类器 $G_m(x)$
2. 计算分类误差率 $$ err_m = \frac{\sum_{i=1}^{N} w_i I(y_i \neq G_m(x_i))}{\sum_{i=1}^{N} w_i} $$
3. 计算分类器权重 $$ \alpha_m = \frac{1}{2} \log \left( \frac{1 - err_m}{err_m} \right) $$
4. 更新样本权重 $$ w_i \leftarrow w_i \times \exp(-\alpha_m y_i G_m(x_i)), \quad i = 1, 2, \ldots, N$$
5. 归一化样本权重 $$ w_i \leftarrow \frac{w_i}{\sum_{j=1}^{N} w_j}, \quad i = 1, 2, \ldots, N$$
最终分类器 $$ G(x) = \text{sign} \left( \sum_{m=1}^{M} \alpha_m G_m(x) \right) $$

#TODO

算一遍课本上的例题

错题大赏会

精选试卷四

1.精选试题四的第三题第二小问，答案给出的对于准确度和召回率的计算非常奇怪，没看明白什么意思

2.第四题

计算距离的时候，对于性别籍贯这种名目型属性（课本中叫做标称），如果值相同则距离为0，不同则距离为1
而在计算点到簇的距离时，对于标称数据，计算的是 1 - P，P 代表该值在簇中出现的频率
计算簇到簇的距离时，举个例子

C1 = {男： 25 ，⼥：5 ；⼴州： 20 ，深圳：6 ，韶关：4 ； 20 } C2 = {男： 3 ，⼥： 12 ；汕头： 12 ，深圳： 1 ，韶关： 2 ； 24 }
$$\begin{aligned} d =& \frac{(1 - \frac{25}{30} \times \frac{3}{15}) + (1 - \frac{5}{30} \times \frac{12}{15})}{2} \\ &+ \frac{(1 - \frac{20}{30} \times \frac{0}{15}) + (1 - \frac{0}{30} \times \frac{12}{15}) + (1 - \frac{6}{30} \times \frac{1}{15}) + (1 - \frac{4}{30} \times \frac{2}{15})}{4} \\ &+ |20 - 24| \end{aligned}$$

精选试卷五

第一题

关联规则挖掘并不是单纯找出所有满足最小支持度的项，还需要保留那些满足最小置信度的规则
K-means 算法是基于原型 or 质心的分类方法，且需要预先指定 K 值

第二题

计算贝叶斯分类器，实际上就是计算各个类别的后验概率，然后选择概率最大的类别作为预测结果
题目答案给错了，学生栏的数据统计反了

精选试卷六

单选第七题

数据预处理包括：数据清洗、数据集成、数据规约、数据变换（感觉这一题更应该选 A 变量代换）

单选第14题

对于一个包含 n 个项的频繁项集，可以产生 $2^n - 2$ 条关联规则

单选第17题答案错误

多选第一题

模式发现不属于预测建模任务，模式匹配更像是数据检索

判断第六题

特征提取高度依赖特定的领域

判断第十四题

贝叶斯算法的核心目标是计算后验概率，而且不是依赖全体数据，而是每个类别的条件概率

精选试卷七

单选第十题

极差在取平均的情况下应该是 36，不知道答案中的31从哪里算出来的

单选第八题

信息熵的计算方法是 $H = -\sum_{i=1}^n p_i \log_2(p_i)$
在等可能情况下简化成 $H = \log_2(n)$

精选试卷八

选择

第10题

当训练集规模较大时，SGD 比批处理梯度下降更优

第12题

逻辑回归对噪声也是敏感的

第十三题

若 SVM 的支撑向量过多，则说明训练的模型过拟合

多选

第四题

对于随机森里的决策树，特征数量 m 越大，单棵树的相关性越大，方差越小；越小则相关性越小但方差变大

第十五题

属性的别名又叫做维度、特征、字段

精选试卷九

如果对于贝叶斯分类任务中，误把某一个特征多算了一遍，意味着加强了这个特征对分类的影响

此外如果贝叶斯所有分类都重复一遍，结果可能会发生变化，因为分类的外部概率未知，平方可能会缩小概率差距从而影响分类结果

决策树的父节点的熵比子节点更大

对于 噪声的敏感度 排序：

AdaBoost > 逻辑回归 / 线性 SVM > 软间隔 SVM > 随机森林

KNN、线性回归需要对数据进行规范化处理，而贝叶斯分类器和决策树不需要（二者关注相对顺序）

对比 BootStrap 和 K折叠交叉验证

当数据量小的时候，BootStrap 更合适
BootStrap 对集成学习有很大帮助
交叉验证一般能提高模型的泛化能力
难以划分训练测试集的时候，BootStrap 更合适

虽然决策树也能处理回归问题，但是当需要得到函数表达式时，线性回归更合适

三种可以处理高维数据可视化的方法

平行坐标系
散点图矩阵
切尔诺夫脸

关于 One Hot 独热编码 🆚 LabelEncoder 标签编码

对数值不敏感的模型（如决策树、朴素贝叶斯等），可以使用标签编码
对数值敏感的模型（如线性回归、逻辑回归、KNN、SVM 等），应该使用独热编码

精选试卷十

SVM 对于类别不平衡的分类问题也能有不错的表现，而贝叶斯、神经网络、KNN 等模型则非常敏感

PCA 的投影方向是数据散度更大的方向，而 LDA 的投影方向才是类别区分度更大的方向（多了一个label的约束）

此外 PCA 并不强调属性值规范化（附加项），常规流程包含取均值、矩阵特征值分解、坐标变换

Kernel Trick 的核心思想是通过核函数计算高维空间中数据点的内积，从而避免显式地进行高维映射，降低计算复杂度

计算统计数据的标准差时，一般使用样本标准差公式（分母为 n - 1），而不是总体标准差公式（分母为 n），但是对数据进行 Z-score 规范化时，使用的标准差是总体标准差公式（分母为 n）

精选试卷十一

当进行 Lasso 回归时，如果一个特征被放大了 k > 1 倍，那么它对应的系数会缩小 k 倍，反而是的在进行正则化时，对损失函数的贡献变小，更容易保留该特征

数据质量的指标不包含精确性(Precision)

书本上给出的数据质量的指标是

准确性
完整性
一致性
合时性
可信性、可解释性

对于双峰数据类型，使用离散化方法来处理更合适，而 Min-Max 规范化和 Z-score 规范化更适合单峰数据类型

逻辑回归比决策树更不容易过拟合

对于样本不均衡的分类任务，使用 F1-score、G-mean、AUC 作为评价指标更合适，而 Accuracy 则不合适

精选试卷十二

对于逻辑回归而言，MSE 不是一个合适的损失函数

SVM 与逻辑回归的核心区别在于 LOSS 函数不同

考试回忆录

基本全是原题，十二套模拟卷基本完成了测试集的全覆盖

除了有简答题考了 hunt 决策树算法的基本原则和对标称数据的处理方法之外，其余题目基本都是已有的题目，绝大部分都没有修改数据

Data Mining 课程复习笔记#

认识数据#

part one#

part two - 数据统计的基本方法#

part three - 数据相似性度量#

part four - 数据可视化#

小结#

数据预处理#

数据清洗#

数据集成#

数据规约（人话版：如何节省存储空间）#

数据转换#

朴素贝叶斯分类器#

基本概念#

例题#

总结#

决策树分类#

Hunt 算法#

ID3 算法#

C4.5 算法#

CART 算法#

基于规则的分类#

Learn One Rule 算法#

回归算法#

线性回归#

最小二乘法#

梯度下降算法#

逻辑回归#

优势比 OR（Odds Ratio）#

参数估计#

正则化#

决策树回归#

支持向量机 SVM#

模型的评价#

分类模型评价指标#

ROC 曲线#

不平衡分类问题#

过拟合 & 欠拟合#

关联规则挖掘#

基本概念#

Apriori算法#

FP-Growth算法#

集成学习#

AdaBoost 算法#

错题大赏会#

精选试卷四#

精选试卷五#

精选试卷六#

精选试卷七#

精选试卷八#

精选试卷九#

精选试卷十#

精选试卷十一#

精选试卷十二#

考试回忆录#

Data Mining 课程复习笔记

认识数据

part one

part two - 数据统计的基本方法

part three - 数据相似性度量

part four - 数据可视化

小结

数据预处理

数据清洗

数据集成

数据规约（人话版：如何节省存储空间）

数据转换

朴素贝叶斯分类器

基本概念

例题

总结

决策树分类

Hunt 算法

ID3 算法

C4.5 算法

CART 算法

基于规则的分类

Learn One Rule 算法

回归算法

线性回归

最小二乘法

梯度下降算法

逻辑回归

优势比 OR（Odds Ratio）

参数估计

正则化

决策树回归

支持向量机 SVM

模型的评价

分类模型评价指标

ROC 曲线

不平衡分类问题

过拟合 & 欠拟合

关联规则挖掘

基本概念

Apriori算法

FP-Growth算法

集成学习

AdaBoost 算法

错题大赏会

精选试卷四

精选试卷五

精选试卷六

精选试卷七

精选试卷八

精选试卷九

精选试卷十

精选试卷十一

精选试卷十二

考试回忆录