Introduction: 知识提纲
- 数据预处理：数据清洗、数据变换
- 特征工程
- 监督学习：
- 分类算法：K-近邻算法，决策树，朴素贝叶斯，Logistic 回归，SVM，Softmax 回归
- 回归算法：线性回归，局部加权线性回归
- 无监督学习：
- K-means，层次聚类，DBSCAN
- 模型评估方法：准确率，召回率，P-R 曲线，ROC，AUC，MSE
§1 数据预处理
数据预处理：在数据挖掘中，海量的原始数据中存在着大量不完整（有缺失值）、不一致、有异常的数据，严重影响到数据挖掘建模的执行效率，甚至可能导致挖掘结果的偏差，所以进行数据清洗显得尤为重要，数据清洗完成后接着进行或者同时进行数据集成、转换、规约等一系列的处理。
数据预处理的主要内容包括数据清洗、数据集成、数据变换和数据规约。
1.1 数据清洗
删除原始数据集中的无关数据、重复数据，平滑噪声数据，筛选掉与挖掘主题无关的数据，处理缺失值、异常值等。
缺失值处理
删除记录：小部分有效，但会造成资源大量浪费
数据插补：常用五种方法
- 均值/中位数/众数填充：scikit-learn 中常用的方法；
- 使用固定值：将缺失的属性值用常量替换；
- 最近临插补：在记录中找到与缺失样本中最接近的样本的该属性值插补；
- 回归方法：根据已有数据和其他变量数据建立拟合模型来预测缺失的属性值；
- 插值法：利用已知点建立合适的插值函数f(x)，再求未知点的插值，如拉格朗日插值法、牛顿插值法等。
异常值处理
异常值是否剔除，需视情况而定，因为有些异常值可能蕴含着有用的信息。
判断异常值的方法：简单统计量分析、3∂原则、箱型图分析等。
异常值处理方法：删除、视为缺失值、平均值修正、不处理。
1.2 数据集成
数据集成就是将多个数据源合并并存放在一个一致的数据存储中的过程。
在数据集成时，来自多个数据源的现实世界实体的表达形式是不一样的，有可能不匹配，要考虑实体识别问题和属性冗余问题，从而将源数据在最底层上加以转换、提炼和集成。
实体识别
实体识别是指从不同数据源识别出现实世界的实体，它的任务是统一不同源数据的矛盾之处。比如：同名异义、异名同义、单位不统一等。
冗余属性识别
数据集成往往往往导致数据冗余，当然对于有些冗余属性可以用相关分析检测。给定两个数值型的属性A和B，根据其属性值，用相关系数度量一个属性在多大程度上蕴含另一个属性。
1.3 数据变换
数据变换主要是对数据进行规范化处理，将数据转换成“适当的”形式，也就是适用于算法的要求形式，以适用于挖掘任务及算法的需要。
简单函数变换：对原始数据进行某些数学函数变换，常用的变换包括平方、开方、取对数、差分运算等，常用来将不具有正态分布的数据变换成具有正态分布的数据。
规范化/归一化
数据规范化（归一化）处理是数据挖掘的一项基础工作。不同评价指标往往具有不同的量纲，数值间的差别可能很大，不进行处理可能会影响到数据分析的结果。为了消除指标之间的量纲和取值范围差异的影响，需要进行标准化处理，将数据按照比例进行缩放，使之落入一个特定的区域，便于进行综合分析。
① 最小-最大规范化
最小-最大规范化也称为离差标准化，是对原始数据进行线性变换，将数值映射到 $[0,1]$ 区间。转换公式如下：
$$
x^*=\frac{x-\min}{\max-\min}
$$
其中，$\max$ 为样本数据中的最大值，$\min$ 为样本数据中的最小值，$\max-\min$ 为极差。离差标准化保留了原始数据中存在的关系，是消除量纲和数据取值范围影响的最简单方法。
这种处理方法的缺点是：若数据集中某个数值很大，则规范化后各值会接近于 $0$，并且彼此之间的差异会变小。
② 零-均值规范化
零-均值规范化也称为标准差标准化。经过处理的数据均值为 $0$，标准差为 $1$。转换公式为：
$$
x^*=\frac{x-\bar{x}}{\delta}
$$
其中，$\bar{x}$ 为原始数据的均值，$\delta$ 为原始数据的标准差。这是当前使用较多的数据标准化方法。
③ 小数定标规范化
小数定标规范化通过移动属性值的小数位数，将属性值映射到 $[-1,1]$ 区间。移动的小数位数取决于属性值绝对值的最大值。转换公式为：
$$
x^*=\frac{x}{10^j}
$$
当然在sklearn库中有专门的API可以做数据的标准化。
类别特征编码
在机器学习中，特征经常不是连续的数值型而是标称型的，这些特征能够被有效地编码成整数。要把标称型特征（categorical features）转换为这样的整数编码（inter codes），我们可以使用OrdinalEncoder。这个估计器把每一个categorical feature变换成一个新的整数数字特征（0到n-categories-1）。但是，这样的整数特征表示并不能在scikit-learn的估计器中直接使用，因为这样的连续输入，估计器会认为类别之间是有序的，但实际上是无序的。
1 | enc = preprocessing.OrdinalEncoder() |
另外一种比较常用的是模型是使用one-hot编码。这种编码类型在OneHotEncoder中实现。默认情况下，每个特征使用几维的数值可以从数据集自动推断。
1 | enc = preprocessing.OneHotEncoder() |
1 | genders = ['female', 'male'] |
如果训练数据可能缺少分类特性，通常最好指定handle_unknown = ‘ignore’，而不是像上面手动设置类别。当指定handle_unknown = ‘ignore’，并且在转换过程中遇到未知类别时，不会产生错误，但是为该特性生成的一热编码列将全部为零（handle_unknown=’ignore’只支持一热编码）。
1 | enc = preprocessing.OneHotEncoder(handle_unknown='ignore') |
连续属性离散化
一些数据挖掘算法，特别是某些分类算法，要求数据是分类属性。这样，常常需要将连续属性变成分类属性，即连续属性离散化。
连续属性的离散化就是在数据的取值范围内设定若干个离散的划分点，将取值范围划分为一些离散化的区间，最后用不同的符号或整数值代表落在每个子区间中的数据值。所以，离散化涉及两个子任务：确定分类数以及如何将连续属性值映射到这些分类值。
常用的离散化方法：等宽法、等频法、基于聚类分析的方法。
生成多项式特征
在机器学习中，通过增加一些输入数据的非线性特征来增加模型的复杂度通常是有效的。一个简单的办法是使用多项式特征，这可以获得特征的更高维度和相互间关系的项。
数据规约
在大数据集上进行复杂的数据分析和数据挖掘需要很长的时间，数据规约产生更小但保持原数据完整性的新数据集。在规约后的数据集上进行分析和挖掘将更有效率。
种类：属性规约、数值规约。
§2 特征工程
2.1 特征工程概述
在机器学习中，特征 是用来描述数据的变量。比如在预测房价的任务中，特征可能包括房子的面积、房龄、地段等信息，而目标变量（Target） 就是房价本身。
特征的质量直接决定了模型的效果。如果你选择了不相关的特征，或者没有正确处理数据，那么你的模型可能无法准确预测。
特征工程的目标是通过合理的特征选择和转换，找到能够更好地描述数据的特征，使得模型更容易学习并做出准确的预测。
2.2 特征选择
定义：从给定的特征集合中选出相关特征子集的过程称为特征选择(feature selection)。
相关特征 & 无关特征：以对学习的关联程度划分
冗余特征：可以从其他特征推演出来的特征
采用特征选择的原因：
维数灾难问题。因为属性或者特征过多造成的问题，如果可以选择重要的特征，使得仅需要一部分特征就可以构建模型，可以大大减轻维数灾难问题，从这个意义上讲，特征选择和降维技术有相似的动机，事实上它们也是处理高维数据的两大主流技术。
去除无关特征可以降低学习任务的难度，也同样让模型变得简单，降低计算复杂度。
特征选择的两个部分：子集搜索、子集评价
常见的特征选择方法
- 过滤式（filter）：先对数据集进行特征选择，其过程与后续学习器无关，即设计一些统计量来过滤特征，并不考虑后续学习器问题。
- 包裹式（wrapper）：直接把最终将要使用的学习器的性能作为特征子集的评价原则。其目的就是为给定学习器选择最有利于其性能、量身定做的特征子集。
- 嵌入式（embedded）：将特征选择与学习器训练过程融为一体，两者在同一个优化过程中完成的。即学习器训练过程中自动进行了特征选择。
2.3 特征提取
定义：将原始数据转换为一组具有明显物理意义（比如 Gabor、几何特征、纹理特征）或者统计意义的特征。
一般常用的方法包括降维（PCA、ICA、LDA等）、图像方面的SIFT、Gabor、HOG等、文本方面的词袋模型、词嵌入模型等。
降维：PCA（主成分分析）
PCA 是降维最经典的方法，寻找一组相互正交的新坐标轴，使数据投影到前几个坐标轴后具有尽可能大的方差，从而用较少维度保留尽可能多的整体变化信息。
PCA 的思想是通过坐标轴转换，寻找数据分布的最优子空间。（如果三维数据点大致分布在一个二维平面附近，就可以把它们投影到该平面，用两个坐标近似表示。）
PCA 的解法一般分为以下几个步骤：
- 对样本数据进行中心化处理；
- 求样本协方差矩阵；
- 对协方差矩阵进行特征值分解，将特征值从大到小排列；
- 取特征值前 n 个最大的对应的特征向量
W1, W2, …, Wn，这样将原来 m 维的样本降低到 n 维。
特征向量可以理解为坐标转换中新坐标轴的方向，特征值表示在对应特征向量上的方差，特征值越大，方差越大，信息量也就越大。这也是为什么选择前 n 个最大的特征值对应的特征向量，因为这些特征包含更多重要的信息。
局限性：PCA 是一种线性降维方法，对某些复杂数据集效果不佳。
图像特征提取：SIFT、HOG
SIFT、HOG 等属于传统计算机视觉中的人工图像特征。
传统计算机视觉：
图像 → 人工设计 SIFT/HOG 等特征 → 分类器
深度学习：
图像 → CNN 自动学习多层表示 → 分类结果
文本特征提取：词袋模型、N-gram模型、词嵌入模型
词袋模型：将整段文本以词为单位切分开，然后每篇文章可以表示成一个长向量，向量的每一个维度代表一个单词，而该维度的权重反映了该单词在原来文章中的重要程度。通常采用 TF-IDF 计算权重。
N-gram模型：N-gram 将连续出现的 (n) 个词或字符视为一个整体特征。例如二元模型会使用“机器学习”“学习模型”等连续两个词组成的特征。
词嵌入模型：是一类将词向量化的模型的统称，核心思想是将每个词都映射成低维空间（通常 K=50~300 维）上的一个稠密向量（Dense Vector）。实际应用中，如果直接将该矩阵作为原文本的特征表示输入到模型中训练，通常很难得到满意的结果，一般还需要对该矩阵进行处理，提取和构造更高层的特征。
特征提取和特征选择的区别
特征选择：从原有特征中挑出一部分，特征本身没有改变。
特征提取：把原始特征转换成一组新的特征。
特征提取强调转换，特征选择强调选取子集。
2.4 特征构建
特征构建是指从原始数据中人工的构建新的特征。需要花时间去观察原始数据，思考问题的潜在形式和数据结构，对数据敏感性和机器学习实战经验能帮助特征构建。
| 原始特征 | 构建的新特征 |
|---|---|
| 身高、体重 | BMI |
| 出生日期 | 年龄 |
| 时间戳 | 小时、星期、是否周末 |
| 长度、宽度 | 面积 |
| 总消费、购买次数 | 平均每次消费金额 |
| 两个地点的经纬度 | 两地距离 |
特征构建需要很强的洞察力和分析能力，要求我们能够从原始数据中找出一些具有物理意义的特征。假设原始数据是表格数据，一般你可以使用混合属性或者组合属性来创建新的特征，或是分解或切分原有的特征来创建新的特征。
特征构建非常需要相关的领域知识或者丰富的实践经验才能很好构建出更好的有用的新特征。
§3 监督学习
3.1 监督学习概述
监督学习是指利用带有标签的数据训练模型，使模型学习从输入特征到目标输出之间的映射关系。训练完成后，模型可以根据新样本的特征，对其未知标签或数值结果进行预测。
监督学习的数据集通常由特征和标签组成。训练时，需要使用损失函数衡量预测结果与真实标签之间的差异，并不断调整模型参数，使损失尽可能减小。
在训练模型之前，通常会将已有数据划分为训练集、验证集和测试集：
- 训练集用于学习和更新模型参数；
- 验证集用于选择模型结构、调整超参数，并观察模型是否出现过拟合；
- 测试集用于在模型确定后，对其泛化能力进行最终评估。
模型在训练集上学习输入特征与标签之间的关系，并根据验证集的表现进行调整。模型和超参数确定后，再使用测试集进行一次相对独立的评价。如果模型在未参与训练的新数据上仍能取得较好的效果，就说明它具有一定的泛化能力，可以进一步用于实际预测。
监督学习主要包括两类任务：
- 分类：预测离散的类别标签，例如判断邮件是否为垃圾邮件；
- 回归：预测连续的数值结果，例如预测房屋价格。
3.2 回归算法
监督学习中的回归问题是指，利用带有特征和连续标签的训练数据，学习输入特征与目标值之间的映射关系，使模型能够对新样本的目标数值进行预测。
线性回归（Linear Regression）
线性回归就是假设样本的feature和label之间满足线性关系，线性回归模型训练过程就是找到能让损失函数值最小的，斜率w的值。
线性回归方程/线性回归的假设函数
在机器学习中，线性回归模型的方程式如下所示：
$$y^{\prime}=b+{w_1}{x_1}$$
其中，$y^{\prime}$ 是预测标签（输出），$b$ 是模型的偏差（代数方程式中的截距），$w_1$ 是特征的权重（代数方程式中的斜率），$x_1$ 是特征（输入）。
在训练期间，模型会计算出可生成最佳模型的权重和偏差。
更复杂的模型可能依赖于多项特征，每项特征都有一个单独的权重，方程线性叠加即可。
$$h_w(x)=w_0+{w_1}{x_1}+{w_2}{x_2}+⋅⋅⋅+{w_n}{x_n}$$
线性回归的假设函数也可以表示为两个向量的点积，一个是模型参数 $\omega$ 合并偏置和特征系数，另一个是特征 $x$ 向量，在第一个位置增加一个1和代表偏置的参数对应。
损失函数
损失用于衡量模型预测与实际标签之间的距离。训练模型的目标是尽可能降低损失，使其达到最低值。损失侧重于值之间的距离，而不是方向，因此，所有用于计算损失的方法都会移除符号。通常用绝对值或平方的方法去除符号。
在线性回归中有5种主要类型的损失：
| 损失类型 | 定义 | 公式 |
|---|---|---|
| $L_1$ 损失 | 预测值与真实值之间绝对误差的总和。 | $\displaystyle L_1=\sum_{i=1}^{N}\lvert y_i-\hat{y}_i\rvert$ |
| 平均绝对误差（MAE） | 一组 $N$ 个样本的平均 $L_1$ 损失。 | $\displaystyle \operatorname{MAE}=\frac{1}{N}\sum_{i=1}^{N}\lvert y_i-\hat{y}_i\rvert$ |
| $L_2$ 损失 | 预测值与真实值之间平方误差的总和。 | $\displaystyle L_2=\sum_{i=1}^{N}(y_i-\hat{y}_i)^2$ |
| 均方误差（MSE） | 一组 $N$ 个样本的平均 $L_2$ 损失。 | $\displaystyle \operatorname{MSE}=\frac{1}{N}\sum_{i=1}^{N}(y_i-\hat{y}_i)^2$ |
| 均方根误差（RMSE） | 均方误差（MSE）的平方根。 | $\displaystyle \operatorname{RMSE}=\sqrt{\frac{1}{N}\sum_{i=1}^{N}(y_i-\hat{y}_i)^2}$ |
选择损失函数的一个重要依据是离群值。
- MSE。模型更接近离群点，但距离大多数其他数据点更远。
- MAE。模型离离群点的距离更远，但离大多数其他数据点的距离更近。
梯度下降法
梯度下降法是一种数学技巧，可迭代地找到能使模型产生最低损失的权重和偏差。梯度下降法通过重复以下过程（迭代次数由用户定义）来找到最佳权重和偏差。
模型开始训练时，权重和偏差会随机化为接近于零的值，然后重复执行以下步骤：
- 使用当前权重和偏差计算损失。
- 确定可减少损失的权重和偏差移动方向。
- 将权重和偏差值沿可减少损失的方向移动少量距离。
- 返回到第 1 步，重复此过程，直到模型无法进一步减少损失为止。
线性回归模型的损失函数始终会生成凸面。根据这一属性，当线性回归模型收敛时，我们知道该模型已找到可产生最低损失的权重和偏差。
超参数
超参数是控制训练不同方面的变量，常见的超参数有学习率、批次大小、周期等。
学习率用于影响模型收敛的速度。学习率决定了在梯度下降过程的每一步中，对权重和偏差所做的更改幅度。
如果学习率过低，模型可能需要很长时间才能收敛。不过，如果学习速率过高，模型将永远无法收敛，而是在可最大限度减少损失的权重和偏差附近跳动。目标是选择一个既不太高也不太低的学习速率，以便模型快速收敛。
批次大小指的是模型在更新权重和偏差之前处理的示例数量。当批次过大时，很难计算每个样本的损失再更新权重和偏差。有2种方法解决这个问题：
- 随机梯度下降法（SGD）：在每次迭代中仅使用一个示例（批次大小为 1）。在迭代次数足够多的情况下，SGD 可以正常运行，但噪声非常大。“噪声”是指训练期间导致损失在迭代过程中增加而非减少的变化。“随机”一词表示每个批次中的一个示例是随机选择的。
- 小批次随机梯度下降法（小批次SGD）：小批次随机梯度下降法是全批次和 SGD 之间的折衷方案。对于N个数据点，批次大小可以是大于 1 且小于N的任意数字。模型会随机选择每个批次中包含的示例，对它们的梯度求平均值，然后在每次迭代中更新一次权重和偏差。
周期数是指模型已处理训练集中每个示例的次数。训练通常需要多个周期。也就是说，系统需要多次处理训练集中的每个示例。一般来说，训练周期数越多，模型效果越好，但训练时间也越长。
线性回归不是只能拟合直线。我们可以通过构造高次特征来解决。一般的做法是先从二次项开始，逐步增加，直到达到我们满意的效果。假如你在构造特征的二次项，需要注意的是，构造的特征不光可以是一个特征的平方，也可以是任意两个特征之间的乘积。
下面是用Python实现的简单的线性回归：
1 | # Feature 数据 |
3.3 分类算法
监督学习中的分类问题是指，给定一些数据，其中每个数据都有一个标签或类别，我们需要根据这些数据构建一个模型，使得该模型能够对新的数据进行分类。
从数据中学习一个分类模型或分类决策函数，称为分类器。分类器对新的输入进行预测，称为分类。可能的输出称为类别。
评价分类器性能的指标一般是分类准确率（accuracy），其定义是：对于给定的测试数据集，分类器正确分类的样本数与总样本数之比。
逻辑回归（Logistic Regression）
逻辑回归（Logistic Regression）是一种统计分析模型，常用于二分类问题，也可以通过一些扩展应用到多分类问题上。它通过拟合一个逻辑函数来预测一个事件发生的概率。
核心思想：通过拟合一个 S 型的逻辑函数（也称为 sigmoid 函数、假设函数），将输入变量映射到输出变量的概率。Sigmoid 函数的数学表达式如下所示：
$$
y = \frac{1}{1 + e^{-x}}
$$
该函数将线性函数的输出转换为一个概率值，范围在0到1之间。sigmoid函数是一个s形的曲线，它的取值在[0, 1]之间，在远离0的地方函数的值会很快接近0或者1。它的这个特性对于解决二分类问题十分重要。
逻辑回归的假设函数
逻辑回归的假设函数形式如下：
$
h_\theta(x)=g(\theta^T x),
\qquad
g(z)=\frac{1}{1+e^{-z}}
$
所以：
$
h_\theta(x)=\frac{1}{1+e^{-\theta^T x}}
$
其中，$x$ 是我们的输入，$\theta$ 为我们要求取的参数。
实际上，逻辑回归就是在线性回归的计算结果上，增加了一个Sigmoid激活函数。
$$
\begin{aligned}
\operatorname{LogisticRegression}(x_1,x_2,\ldots,x_n)
&=\operatorname{Sigmoid}\left(
w_1x_1+w_2x_2+\cdots+w_nx_n+b
\right)
\end{aligned}
$$
一个机器学习模型，实际上是把决策函数限定在某一组条件下，这组限定条件就决定了模型的假设空间。当然，我们还希望这组限定条件简单而合理。
逻辑回归模型所作的假设是：
$$
P(y=1\mid x;\theta)=g(\theta^T x)=\frac{1}{1+e^{-\theta^T x}}
$$
这个函数的含义是：在给定 $x$ 和 $\theta$ 的条件下，$y=1$ 的概率。
这里的 $g(z)$ 就是上面提到的 Sigmoid 函数，与之相对应的决策函数为：
$$
y^*=1,
\qquad
\text{if }P(y=1\mid x)>0.5
$$
选择 $0.5$ 作为阈值是一种常见做法。实际应用时，可以根据具体情况选择不同的阈值：
- 如果对正例的判别准确性要求较高，可以选择更大的阈值；
- 如果对正例的召回率要求较高，则可以选择更小的阈值。
决策边界：也称决策面，是用于在N维空间，将不同样本分开的平面或曲面。分为线性与非线性两种。在逻辑回归中表示为 $\theta^T x=0$。
决策边界是模型假设函数的属性，由模型参数决定；而模型参数通常是通过数据集学习得到的，因此数据集会间接影响决策边界。
代价函数：概况来讲，任何能够衡量模型预测出来的值与真实值之间的差异的函数都可以叫做代价函数。一个好的代价函数需要满足两个最基本的要求：能够评价模型的准确性，对参数可微。
在Logistic 回归中，最常用的代价函数是交叉熵。
Logistic 回归标签只有两种情况：
$$y\in{0,1} $$
单个样本的真实标签出现概率，可以统一写为：
$$ P(y\mid x)=p^y(1-p)^{1-y} $$
为了把乘法变成更方便计算的加法，对它取对数：
$$\log P(y\mid x) = y\log p+(1-y)\log(1-p)$$
训练通常写成最小化问题，所以加一个负号：
$$L=-\left[y\log p+(1-y)\log(1-p)\right] $$
这就是二元交叉熵，也就是 Logistic 回归常用的损失函数。
Softmax 回归
Softmax 回归实际上就是 Logistic 回归在多分类情况下的一般形式。
Softmax 回归通过 Softmax 函数计算一个样本在不同类别中的概率大小，并选出概率最大的那个作为预测结果。
假设函数：Softmax 函数把各类别的原始分数转换成概率：
$$ P(y=k\mid x;\theta) = \frac{e^{z_k}} {\sum_{j=1}^{K}e^{z_j}} $$
因为：
$$ z_k=\theta_k^Tx $$
所以也可以写成：
$$ P(y=k\mid x;\theta) = \frac{e^{\theta_k^Tx}} {\sum_{j=1}^{K}e^{\theta_j^Tx}} $$
其中，$x$ 是输入特征；$\theta_k$ 是第 $k$ 个类别对应的参数；$z_k$ 是模型对第 $k$ 个类别计算出的原始分数；$k$ 表示当前正在计算哪个类别；$K$ 表示类别总数。
损失函数：
$$L_i=-\log P(y=y_i\mid x_i;\theta)$$
代价函数：
$$J(\theta) = -\frac{1}{m} \sum_{i=1}^{m} \log P(y=y_i\mid x_i;\theta)$$
$$or J(\theta) = -\frac{1}{m} \sum_{i=1}^{m} \sum_{k=1}^{K} \mathbf{1}{y_i=k} \log P(y=k\mid x_i;\theta)$$
$\mathbf{1}{y_i=k} $ 称为指示函数。含义是：
$$ \mathbf{1}{y_i=k} = \begin{cases} 1,&y_i=k\ 0,&y_i\neq k \end{cases} $$
对于每个样本，只有其真实类别对应的指示函数等于 $1$，其他类别对应的指示函数都等于 $0$。因此，上面两种代价函数的写法是等价的。
Softmax 回归适用于互斥多分类。例如一张图片只能在猫、狗、鸟中选择一类；如果一个样本可以同时具有多个类别标签，就不是普通 Softmax 回归所处理的问题。
决策树（Decision Tree）
决策树是根据某种决策不断的对数据集进行分裂，使得到的子数据集上的标签越来越纯净，最终得到的模型就是一个树形结构，故其名曰决策树。
下面介绍三种经典决策树，唯一区别是节点划分的决策选择不同。
ID3决策树
决策选择：选择信息增益最大的特征进行数据集划分
信息熵用于衡量一个数据集合中类别的混乱程度：
$$H(D)=-\sum_{k=1}^{K}p_k\log_2p_k $$
其中：$D$ 当前数据集， $K$ 类别数量，$p_k$ 第 $k$ 类样本所占比例
假设使用特征 $a$ 划分数据，数据被分成若干子集。划分后的整体混乱程度是各子集熵的加权平均：
$$H(D\mid a) = \sum_{v} \frac{|D_v|}{|D|} H(D_v) $$
其中：$D_v$：特征 $a$ 取值为 $v$ 的样本子集；$|D_v|$：该子集的样本数；$|D|$ ：整个数据集的样本数。
信息增益表示划分前后，混乱程度减少了多少：
$$ \operatorname{Gain}(D,a) = H(D)-H(D\mid a) $$
信息增益越大，说明这个特征越能把不同类别分开。
ID3决策树的缺点：对可取值数目较多的特征有所偏好；只能用于处理离散分布的特征，不能处理连续值与缺失值；只能用于分类。
C4.5决策树
决策选择：选择信息增益率大的特征进行数据集划分，对取值过多的特征进行一定惩罚
$$\operatorname{GainRatio}(D,a) = \frac{\operatorname{Gain}(D,a)} {\operatorname{IV}(a)}$$
优点：改进ID3倾向于选择取值较多的特征的缺点；可处理连续值与缺失值
缺点：只能用于分类；计算有大量对数运算
CART
决策选择：使用基尼系数小的特征进行数据集划分
$$\operatorname{Gini}(D) = 1-\sum_{k=1}^{K}p_k^2$$
优点：减少大量对数运算；可同时用于分类与回归
缺点：倾向于多取值特征
总结
| 对比维度 | ID3 | C4.5 | CART |
|---|---|---|---|
| 划分标准 | 使用信息增益，容易偏向取值较多的特征 | 使用信息增益率，缓解信息增益偏好多值特征的问题，但可能偏向取值较少的特征 | 分类树使用基尼指数，回归树使用平方误差；无需计算对数，计算相对简单 |
| 适用任务 | 只能用于分类 | 只能用于分类 | 可以用于分类和回归 |
| 树的结构 | 通常生成多叉树 | 通常生成多叉树 | 只生成二叉树 |
| 连续特征 | 原始算法主要处理离散特征 | 可以处理连续特征 | 可以处理连续特征 |
| 缺失值处理 | 对缺失值较敏感，原始算法缺少完善的处理方法 | 可以处理缺失值 | 可以通过代理划分等方式处理缺失值 |
| 计算复杂度 | 计算相对简单 | 需要计算信息增益率，并对连续特征寻找划分点，计算成本较高 | 基尼指数计算简单，通常效率较高 |
| 特征能否重复使用 | 离散特征在一条路径中通常只使用一次 | 离散特征在一条路径中通常只使用一次；连续特征可在不同节点再次使用 | 同一特征可以在不同节点多次使用 |
| 剪枝策略 | 原始 ID3 没有完善的剪枝策略 | 通常采用悲观剪枝 | 通常采用代价复杂度剪枝 |
| 主要优点 | 原理简单，容易理解 | 改进了 ID3，支持连续特征、缺失值和剪枝 | 结构统一，效率较高，同时支持分类和回归 |
| 主要缺点 | 偏好多值特征、容易过拟合、适用范围有限 | 计算较复杂，信息增益率本身也存在偏好问题 | 二叉划分可能使树更深，单棵树仍容易过拟合且对数据变化敏感 |
支持向量机（Support Vector Machine, SVM）
SVM支持向量机，是指寻找到一个超平面使样本分成两类，并且间隔最大的算法。
适用范围：线性或非线性分类、回归，甚至是异常值检测任务。
超平面：在高维特征空间中分隔数据的决策边界。
线性 SVM 的分类超平面表示为：
$$ w^Tx+b=0 $$
其中：$x$：输入样本；$w$：决定超平面方向的参数向量；$b$：决定超平面位置的参数；$w^Tx$：各个特征与其参数相乘后求和。
支持向量：距离决策边界较近、对确定分隔超平面起关键作用的训练样本。在硬间隔 SVM 中，支持向量位于间隔边界上；在软间隔 SVM 中，位于间隔内部或被错误分类的部分样本也可能成为支持向量。
间隔：两个平行于决策边界且穿过支持向量的超平面之间的距离。这个距离的计算公式是 $ \frac{2}{|w|} $
硬间隔分类：严格让所有实例都不在最大间隔之间，并且位于正确的一边。
硬间隔分类只在数据是线性可分离时才有效；
硬间隔分类对异常值非常敏感。
硬间隔分类的目标函数为：
$$\min_{w,b}\frac12|w|^2$$
其约束为：
$$y_i(w^Tx_i+b)\geq1$$
该约束可理解为，位于超平面上方的样本点标签为1，位于下方的样本点标签为-1。
软间隔分类：尽可能保持最大间隔宽阔和限制间隔违例（即位于最大间隔内部，甚至在错误的一边的实例）之间找到良好的平衡。
在scikit-learn的SVM类中，可以通过超参数C值来控制这个平衡。C值越小，间隔越宽，间隔违例也越多；C值越大，间隔违例较少，但间隔也小。
软间隔分类的目标函数为：
$$\min_{w,b,\xi} \frac12|w|^2 + C\sum_{i=1}^{m}\xi_i$$
其中： $\frac12|w|^2$ ：希望间隔尽可能大； $\sum\xi_i$ ：希望违反间隔要求的程度尽可能小； $C$ ：控制这两个目标之间的权衡。
约束为：
$$ y_i(w^Tx_i+b)\geq1-\xi_i $$
$$ \xi_i\geq0 $$
其中 $\xi_i$ 是松弛变量，表示第 $i$ 个样本违反间隔要求的程度：
- $\xi_i=0$：样本位于间隔边界或间隔之外；
- $0<\xi_i\leq1$：样本位于间隔内部，但仍被正确分类；
- $\xi_i>1$：样本被错误分类。
关于公式具体推导参见：https://zhuanlan.zhihu.com/p/259850768
核技巧：将二维线性不可分样本点映射到高维空间中，让样本点在高维空间线性可分。用于解决样本点不再线性可分的情形，比如二维空间中环形分布的数据点。核方法使 SVM 能够形成非线性决策边界。
具体来说，核技巧是利用 $x\longrightarrow\phi(x)$ 将数据映射到新的空间，再利用核函数 $K(x_i,x_j) = \phi(x_i)^T\phi(x_j)$ 直接计算两个样本在新特征空间的内积。
常见的核函数有：线性核、多项式核、RBF高斯核。
K-近邻 （K Nearest Neighbors, KNN）
KNN算法是指当预测一个新的值x的时候，根据它距离最近的K个点是什么类别来判断x属于哪个类别。
K值选择：一般自己调整，过小容易过拟合，过大容易欠拟合。KNN 通常需要先进行标准化或归一化。
距离的度量：曼哈顿距离、欧式距离、无穷范式等。最常用的是欧氏距离。
优点：简单易上手。
缺点：对K值选择敏感；时间空间复杂度较大；对异常值、噪声和错误标签较敏感。
朴素贝叶斯（Naive Bayes）
贝叶斯定理：
条件概率形式：
$$
P(A\mid B)=\frac{P(B\mid A)P(A)}{P(B)}
$$
全概率形式：
$$
P(A_i\mid B)=\frac{P(B\mid A_i)P(A_i)}{\sum_{j=1}^{n}P(B\mid A_j)P(A_j)}
$$
贝叶斯定理可以用于监督学习。朴素贝叶斯就是假设样本各个特征之间相互条件独立（朴素的定义），用 $P(特征|类别)$ 、$P(类别)$ 、$P(特征)$ 三个概率值算出 $P(类别|特征)$ 的概率值，继而将测试样本分类的算法。
因为该概率值只需要用于比较，因此分母 $P(特征)$ 通常不计算。
由于朴素的前提，特征相关的概率可以由乘法原理简单算得。
注意事项：
- 特征太多时，多个小于1的概率值累乘可能导致下溢出，因此可以转化为对数加法运算，避免下溢出。
- 如果某一类别下特征m没有出现，此时P(特征m|类别)=0, 这会造成最终的概率值为0, 所以可使用拉普拉斯平滑，就是在分子分母分别加1，可避免0概率出现的情况。在样本量充足的情况下，平滑不会对结果产生影响。
优点：逻辑简单，基于统计而非权重迭代优化；时间与空间复杂度都较小。
缺点：只能处理分类任务，且样本少的情况下效果最好；特征之间相互独立的假设通常不成立。
§4 无监督学习
4.1 概述
在无监督学习中，数据集中只有输入特征（X），没有标签（Y）。算法自动发现数据中的模式对数据进行分析。
无监督学习的主要任务有聚类、降维、密度估计、表示学习等。其中，主要的任务是聚类，将数据集中的样本划分成若干个互不相交的子集（称为簇或类），使得同一个簇内的样本彼此相似，而不同簇中的样本彼此不相似。
4.2 聚类算法
K-Means
K-Means 是最著名、最常用的聚类算法之一，其思想直观，实现相对简单。
具体步骤：
- 确定簇的数量 K：首先，你需要决定想把数据分成几类。这个 K 值需要预先指定，这是 K-Means 的一个关键参数。
- 初始化代表（质心）：随机在数据空间中选取 K 个点，作为每个簇的初始”中心点”，我们称之为质心。
- 分配居民（样本）：计算数据集中每一个样本点到这 K 个质心的距离。遵循”近者归其类”的原则，将每个样本分配给距离它最近的那个质心所在的簇。这样，所有样本就被划分到了 K 个簇中。
- 改选新代表更新质心）：现在，每个簇里都有了一批样本。重新计算每个簇的质心，新的质心就是该簇内所有样本点的平均值（均值点）。
- 重复与收敛：重复步骤 3（分配）和步骤 4（更新），直到质心的位置不再发生显著变化（即算法收敛）。此时，每个样本的所属簇也不再变化。
选择K值的方法：一个常用的方法是 “肘部法则”。其思想是：随着簇数量 K 的增加，样本点到其所属簇质心的平均距离（称为畸变程度或 inertia）会下降。当 K 小于真实簇数时，增加 K 会大幅降低这个距离；当 K 达到真实簇数后，再增加 K，距离的下降幅度会骤减。这个拐点就像手肘的关节，对应的 K 值就是较好的选择。
层次聚类
层次聚类算法(Hierarchical Clustering)将数据集划分为一层一层的clusters，后面一层生成的clusters基于前面一层的结果。层次聚类算法一般分为两类：
- Divisive 层次聚类：又称自顶向下（top-down）的层次聚类，最开始所有的对象均属于一个cluster，每次按一定的准则将某个cluster 划分为多个cluster，如此往复，直至每个对象均是一个cluster。
- Agglomerative 层次聚类：又称自底向上（bottom-up）的层次聚类，每一个对象最开始都是一个cluster，每次按一定的准则将最相近的两个cluster合并生成一个新的cluster，如此往复，直至最终所有的对象都属于一个cluster。
DBSCAN
DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是一种基于密度的无监督聚类算法。它认为：同一簇中的样本通常分布得比较密集，而不同簇之间由密度较低的区域分隔。
DBSCAN 需要设置两个参数：
- $\varepsilon$：邻域半径，表示两个样本距离多近才算邻居；
MinPts：形成密集区域所需的最少样本数。
根据邻域内的样本数量，可以将样本分为：
- 核心点：$\varepsilon$ 邻域内的样本数不少于
MinPts； - 边界点：自身邻居不足，但位于某个核心点的邻域内；
- 噪声点：既不是核心点，也不属于任何核心点的邻域。
算法步骤
- 任意选择一个尚未访问的样本；
- 找出其 $\varepsilon$ 邻域内的所有样本；
- 如果邻域内样本数不少于
MinPts，则将其作为核心点，并建立一个新簇； - 继续检查该核心点邻域中的样本，将与它密度相连的核心点和边界点加入同一簇；
- 重复上述过程，直到该簇无法继续扩展；
- 选择下一个未访问样本，直到所有样本都被处理；
- 无法被加入任何簇的样本被标记为噪声点。
算法效果
DBSCAN 不需要提前指定聚类数量，能够发现圆形以外的任意形状簇，并且可以自动识别噪声点和异常点。
其主要缺点是对 $\varepsilon$ 和 MinPts 的选择较敏感。当不同簇的密度差异较大时，DBSCAN 可能难以同时识别所有簇；在高维数据中，距离度量的效果也可能下降。
§5 模型评估方法
建模的评估一般可以分为回归、分类和聚类的评估。
5.1 回归模型的评估
主要有以下方法：
| 指标 | 描述 | metrics方法 |
|---|---|---|
| Mean Absolute Error(MAE) | 平均绝对误差 | from sklearn.metrics import mean_absolute_error |
| Mean Square Error(MSE) | 均方误差 | from sklearn.metrics import mean_squared_error |
| R-Squared | R平方值 | from sklearn.metrics import r2_score |
平均绝对误差（Mean Absolute Error，MAE）指预测值与真实值之间平均相差多大：
$$\operatorname{MAE} = \frac{1}{N} \sum_{i=1}^{N}|y_i-\hat y_i|$$
平均绝对误差能更好地反映预测值误差的实际情况，对异常值相对不那么敏感。
均方误差（Mean Squared Error，MSE）指观测值与真值偏差的平方和与观测次数的比值：
$$\operatorname{MSE} = \frac{1}{N} \sum_{i=1}^{N}(y_i-\hat y_i)^2$$
这也是线性回归中最常用的损失函数，线性回归过程中尽量让该损失函数最小。那么模型之间的对比也可以用它来比较。 MSE可以评价数据的变化程度，MSE的值越小，说明预测模型描述实验数据具有更好的精确度。
**R-square(决定系数)**通过数据的变化来表征一个拟合的好坏。分母理解为原始数据的离散程度，分子为预测数据和原始数据的误差，二者相除可以消除原始数据离散程度的影响：
$$R^2 = 1- \frac{\sum_{i=1}^{N}(y_i-\hat y_i)^2} {\sum_{i=1}^{N}(y_i-\bar y)^2}$$
$R^2=1$ 表示完美预测，$R^2=0$ 表示模型大致相当于始终预测平均值，$R^2$ 也可能小于 $0$，说明模型甚至不如该基准。
5.2 分类模型的评估
混淆矩阵
混淆矩阵也称误差矩阵，是表示精度评价的一种标准格式，用n行n列的矩阵形式来表示。具体评价指标有总体精度、制图精度、用户精度等，这些精度指标从不同的侧面反映了图像分类的精度。
| 实际情况 | 预测为正 | 预测为负 |
|---|---|---|
| 实际为正 | TP | FN |
| 实际为负 | FP | TN |
准确率、精确率、召回率、F1
准确率（Accuracy）的定义是：对于给定的测试集，分类模型正确分类的样本数与总样本数之比；
$$\operatorname{Accuracy} = \frac{TP+TN}{TP+TN+FP+FN}$$
精确率（Precision）的定义是：对于给定测试集的某一个类别，分类模型预测正确的比例，或者说：分类模型预测的正样本中有多少是真正的正样本；
$$\operatorname{Precision} = \frac{TP}{TP+FP}$$
召回率（Recall）的定义为：对于给定测试集的某一个类别，样本中的正类有多少被分类模型预测正确；
$$\operatorname{Recall} = \frac{TP}{TP+FN}$$
在理想情况下，我们希望模型的精确率越高越好，同时召回率也越高越高，但是，现实情况往往事与愿违，在现实情况下，精确率和召回率像是坐在跷跷板上一样，往往出现一个值升高，另一个值降低，那么，有一个指标来综合考虑精确率和召回率，这个指标就是F1值。
$$F1 = \frac{2\cdot Precision\cdot Recall} {Precision+Recall}$$
P-R 曲线
P-R曲线是指用横轴表示召回率，纵轴表示精确率，将数据绘制成图表的形式所得到的曲线。
当提升精确率时，召回率会降低，相反如果要提供召回率，则精确率会相应降低。
理想的情况是精确率和召回率都相当高的点，但由于两者是成反比的关系，一个升高就会导致另一个降低。不过，PR曲线上存在精确率和召回率相同的点，这个点叫做平衡点(Break Even Point, BEP)。在这个点上，精确率和召回率之间达到了最好的平衡状态。
ROC 曲线和 AUC
ROC 曲线表示分类阈值不断变化时，TPR 和 FPR 如何变化。其中，纵轴TPR就是Recall，横轴FRP是负正类率（(False Positive Rate），FPR=1-TNR。
AUC就是ROC 曲线下的面积，通常情况下数值介于0.5-1之间，可以评价分类器的好坏，数值越大说明越好。
AUC评价：
AUC = 1 表示模型能够把所有正样本排在所有负样本之前，因此存在一个合适的阈值可以实现完美分类。绝大多数预测的场合，不存在完美分类器。
0.5 < AUC < 1，优于随机猜测。这个分类器（模型）妥善设定阈值的话，能有预测价值。
AUC = 0.5，跟随机猜测一样（例：丢铜板），模型没有预测价值。
AUC < 0.5，比随机猜测还差；但只要总是反预测而行，就优于随机猜测，因此不存在AUC < 0.5的情况。
Comments