符号定义
· $x, y, z$：数据对象、向量、点
· $x_u$：对象 $x$ 的第 $u$ 个属性值
· $m$：对象/记录总数
· $n$：属性/维度总数
· $S$：名义属性的取值个数
· $U$：训练记录集合
· $U_s$：分裂后的第 $s$ 个子集
· $|U|$：集合 $U$ 的记录数
· $c_k$：第 $k$ 个类别
· $p(c_k)$：属于类别 $c_k$ 的比例
· $\log_2$：以 2 为底的对数
- 二值相似度
定义：对二值向量 $x, y$，记
$$ f_{11} = \#\{u : x_u=1, y_u=1\} $$
$$ f_{10} = \#\{u : x_u=1, y_u=0\} $$
$$ f_{01} = \#\{u : x_u=0, y_u=1\} $$
$$ f_{00} = \#\{u : x_u=0, y_u=0\} $$
总属性数为
$$ f_{11}+f_{10}+f_{01}+f_{00} $$
$$ \mathrm{SMC} = \frac{f_{11}+f_{00}}{f_{11}+f_{10}+f_{01}+f_{00}} $$
$$ \mathrm{Jaccard} = \frac{f_{11}}{f_{11}+f_{10}+f_{01}} $$
- 余弦相似度
$$ \cos(x,y) = \frac{x \cdot y}{\|x\|\,\|y\|} $$
$$ x\cdot y = \sum_{u=1}^n x_u y_u $$
$$ \|x\| = \sqrt{\sum_{u=1}^n x_u^2} $$
- 距离度量
Euclidean distance：
$$ d(x,y) = \sqrt{\sum_{u=1}^n (x_u - y_u)^2} $$
Minkowski distance（$h \ge 1$）：
$$ d(x,y) = \left( \sum_{u=1}^n |x_u - y_u|^h \right)^{1/h} $$
特例：$h=1$（曼哈顿距离），$h=2$（欧氏距离）。
Supremum distance（$h = \infty$）：
$$ d_\infty(x,y) = \max_u |x_u - y_u| $$
加权距离：
$$ d(x,y) = \left( \sum_{u=1}^n w_u |x_u - y_u|^h \right)^{1/h} $$
- 归一化向量下的距离与余弦关系
若 $\|x\| = \|y\| = 1$，则
$$ d(x,y)^2 = 2\bigl(1 - \cos(x,y)\bigr) $$
- 文档权重（tf-idf）
$$ t'_{ij} = t_{ij} \log_2\left(\frac{m}{\mathrm{df}_i}\right) $$
其中 $t_{ij}$ 为词 $i$ 在文档 $j$ 中的频数，$m$ 为文档总数，$\mathrm{df}_i$ 为包含词 $i$ 的文档数。
- 基本统计量
均值：
$$ \bar{x} = \frac{1}{m}\sum_{i=1}^m x_i $$
样本方差：
$$ \sigma_x^2 = \frac{1}{m-1}\sum_{i=1}^m (x_i - \bar{x})^2 $$
标准差：
$$ \sigma_x = \sqrt{\sigma_x^2} $$
范围：
$$ \mathrm{range}(x) = \max_i x_i - \min_i x_i $$
相对频率：
$$ \mathrm{rel\_freq}(a_s) = \frac{\#\{i : x_i = a_s\}}{m} $$
众数：出现次数最多的值。
中位数：排序后中间值（奇数个）或中间两值的平均（偶数个）。
- 协方差与相关系数
协方差（样本）：
$$ \mathrm{cov}(x_u, x_v) = \frac{1}{m-1}\sum_{i=1}^m (x_{iu} - \bar{x}_u)(x_{iv} - \bar{x}_v) $$
相关系数：
$$ r_{uv} = \frac{\mathrm{cov}(x_u, x_v)}{\sigma_u \sigma_v},\quad -1 \le r_{uv} \le 1 $$
协方差矩阵（二属性）：
$$ \begin{bmatrix} \sigma_x^2 & \mathrm{cov}(x,y) \\ \mathrm{cov}(x,y) & \sigma_y^2 \end{bmatrix} $$
- 混淆矩阵与准确率
二分类混淆矩阵：
$$ \begin{array}{c|cc} & \text{Pred }1 & \text{Pred }0 \\ \hline \text{Actual }1 & a_{11} & a_{10} \\ \text{Actual }0 & a_{01} & a_{00} \end{array} $$
$$ \mathrm{Accuracy} = \frac{a_{11}+a_{00}}{a_{11}+a_{10}+a_{01}+a_{00}},\quad \mathrm{Error\ Rate} = 1 - \mathrm{Accuracy} $$
- 决策树：不纯度度量
熵（Entropy）：
$$ I(U) = -\sum_{k} p(c_k) \log_2 p(c_k) $$
二分类：
$$ I = -p \log_2 p - (1-p)\log_2(1-p) $$
基尼指数（Gini Index）：
$$ G(U) = 1 - \sum_k p(c_k)^2 $$
二分类：
$$ G = 1 - p^2 - (1-p)^2 $$
分类误差（Classification Error）：
$$ E(U) = 1 - \max_k p(c_k) $$
分裂后的加权不纯度（以熵为例）：
$$ I(P) = \sum_{s=1}^S \frac{|U_s|}{|U|} \, I(U_s) $$
信息增益：
$$ \mathrm{gain}(P) = I(U) - I(P) $$
基尼改善：
$$ \Delta G = G(U) - \sum \frac{|U_s|}{|U|} G(U_s) $$
误差改善：
$$ \Delta E = E(U) - \sum \frac{|U_s|}{|U|} E(U_s) $$
增益率：
$$ \mathrm{Gain\ Ratio} = \frac{\mathrm{gain}(P)}{\mathrm{Split\ Info}},\quad \mathrm{Split\ Info} = -\sum_{s=1}^S \frac{|U_s|}{|U|} \log_2 \frac{|U_s|}{|U|} $$
- 连续属性分裂
候选阈值：
$$ T_r = \frac{x_{(r)} + x_{(r+1)}}{2} $$
其中 $x_{(r)}$ 为排序后的属性值。选择最大化信息增益的阈值。
- 分类器评估与剪枝
重代入估计（Resubstitution Estimate）：
$$ \mathrm{error\_rate} = \frac{\text{training errors}}{N} $$
其中 $\text{training errors}$ 为各叶节点中非多数类记录数之和。
带惩罚的估计误差：
$$ \mathrm{error\_rate} = \frac{\text{training errors} + c \times (\text{leaf nodes})}{N} $$
$c$ 为每个叶节点的惩罚项。
- 朴素贝叶斯
贝叶斯定理：
$$ P(Y|X) = \frac{P(X|Y)P(Y)}{P(X)} $$
朴素假设（属性条件独立）：
$$ P(X|Y=c) = \prod_{u=1}^n P(X_u|Y=c) $$
分类决策：选择最大化
$$ P(Y=c)\prod_{u} P(X_u|Y=c) $$
的类别 $c$。
离散属性：
$$ P(X_u = a|Y=c) = \frac{\#\{i: X_{iu}=a \text{ and } Y_i=c\}}{\#\{i: Y_i=c\}} $$
连续属性（高斯分布）：
$$ P(X_u = x_u|Y=c) \approx \frac{\epsilon}{\sqrt{2\pi}\,\sigma_{u,c}} \exp\left(-\frac{(x_u - \mu_{u,c})^2}{2\sigma_{u,c}^2}\right) $$
其中 $\mu_{u,c}, \sigma_{u,c}^2$ 为类别 $c$ 下属性 $u$ 的样本均值和样本方差，$\epsilon$ 为小常数（通常忽略）。
- k-近邻（k-NN）
- 计算测试点与所有训练点的距离（通常欧氏距离）。
- 按距离升序排序，取前 k 个最近邻。
- 采用多数投票决定预测类别。
- 名义属性的二值划分数量
对于有 $S$ 个取值的名义属性，可能的二值划分数量为：
$$ 2^{S-1} - 1 $$