0%

百面机器学习 (二)

1. 决策树之间的区别

ID3 C4.5 CART
依据 信息增益 信息增益率 Gini 系数
任务 分类 分类 分类和回归
树类型 多叉树 多叉树 二叉树

2. 如何对决策树进行剪枝

决策树剪枝包含 2 种:

  • 预剪枝: 在生成决策树的过程中提前停止树的增长,核心思想是在树进行扩展之前,计算当前划分能够带来模型泛化能力的提升,如果不能则停止生长。

    • 当树达到一定深度时候,停止生长。
    • 当前节点的样本数量小于某个阈值的时候,停止生长。
    • 计算每次分裂对于测试集的准确度的提升,当小于某个阈值时,停止生长。
  • 后剪枝:在已经生成的过拟合决策树上进行剪枝。核心思想在树完全生长后,从底层向上层计算是否剪枝。剪枝过程将子树删除,叶子节点进行代替。后剪枝可用测试集的准确率判断。

    • 常见后剪枝方法:降低剪枝 (REP), 悲观剪枝(PEP), 代价复杂度剪枝(CCP),最小误差剪枝(MEP)。
优点 缺点
预剪枝 简单高效,适合大规模问题 阈值选择,可能存在欠拟合风险,测试集可能在之后划分显著提高,但是提前终止了生长
后剪枝 相比于预剪枝,可得到泛化强的决策树 时间开销大

3. 如何定义主成分?从该定义出发,如何设计目标函数达到降维提取主成分的目的?针对该目标函数,如何对 PCA 问题求解?

给定数据向量 ${v_1, …, v_n}$, 以二维坐标为例如下两个图的变化过程。

  • 主要目标:降维后图 b 中的黄轴就是主成分的方向。其特点是黄轴上数据更为分散,即方差更大。由此可以看出 PCA 的主要目标,寻找到最大化投影方差。

  • 主要目标(数学表达):对所有样本去中心化 ${x1, …, x_n} = {v_1-\mu, …, v_n-\mu}$,其中 $\mu = \frac{1}{n}\sum{i=1}^nv_i$, 某个向量在某个单位向量上的投影公式 $x_i^Tw = |x_i|\cdot|w|\cdot\cos(\theta) = |x_i|\cos(\theta)$, 需要让该方差最大。

  • 通过求解和线性代数可发现,数据集投影后的方差就是 协方差矩阵 特征值 投影的方向 就是 特征值对应的 特征向量

  • PCA 求解方法:

      1. 对样本进行中心化处理
      1. 求样本协方差矩阵
      1. 对协方差矩阵进行特征值分解,并从大到小排序
      1. 取特征值前 d 的大的特征向量 $w_1, …, w_d$。 通过映射还原 n 维度到 d 维度
  • PCA 降维后的信息占比为: $\eta = \sqrt{\frac{\sum{i=1}^d{\lambda_i^2}}{\sum{i=1}^n{\lambda_i^2}}}$

4. 线性判别模型(LDA, linear discriminant analysis)

  • 相比于 PCA, LDA 可以作为一种基于标签的有监督的降维方法(如下图具有不同标签,PCA 将映射到 y 轴,相反 LDA 将映射到 x 轴,后者更好)。

  • 核心思想:最大化类间间距、最小化类内间距。(同样它对数据的分布做了一些很强的假设。认为每个类数据都是高斯分布,且各个类的协方差相等)。

  • 公式推理:以两个类为例子 $C_1, C_2$。

    • 最大化类内间距:需要找到一个投影平面 $w$, 最大化投影后两个类中心之间的距离。

      当 $w$ 与 $(\mu_1 - \mu_2)$ 方向一致的时候,该距离最大。此时可能出现如下图问题,就是投影后两个类出现了重叠。

    • 最小化类间间距:缩小类间距离,如下图所示,能够改善上图中的问题。

      目标函数: $D_1, D_2$ 表示投影后的类间距离

      对目标函数求导并令倒数为 0 得到。

5. 简述 K 均值算法的具体步骤

K 均值聚类的核心目标是将给定的数据集分类为 K 个族,并给出每个数据对应的簇中心点。其步骤如下:

    1. 数据预处理,如归一化、离群点处理等。
    1. 随机选取 K 个簇中心,记为 $u_1^{(0)}, …, u_k^{(0)}$。
    1. 定义代价函数: $J(c, u) = \minu\min_c\sum{i=1}^M||xi - u{c_i}||^2$
    1. 令 $t = 0, 1, …$ 为迭代部署,重复下面过程直到 $J$ 收敛。

6. K 均值算法的优缺点?如何对其调优?

  • 优点:对于大数据集,K 均值算法是可伸缩和高效的,它的计算复杂度是 O(NKt)线性的,$N, K, t$ 分别表示样本数目,聚类簇数和迭代的轮数。

  • 缺点:受初值和离群点的影响,每次结果不稳定,且结果通常是局部最优解不是全局最优解。

  • 调优方法:

      1. 数据归一化和离群点处理: 其距离计算公式基于欧式距离度量,均值和方差大的维度对数据聚类结果会产生决定性影响。未做归一化和统一单位的数据会无法直接参与运算和比较。离群点或噪声数据会导致中心偏移。
      1. 合理 K 值:基于经验和多次试验结果。尝试不同的 K 值,然后寻找折弯处。
      1. 采用核方法。

7. K 均值算法的缺点,有哪些改进模型?

  • 主要缺点:

      1. 需要人工预先确定初始 K 值,该值和真实的数据分布未必吻合。
      1. K 均值只能收敛到局部最优,效果受到初值影响很大。
      1. 容易受到噪声点的影响
      1. 样本只能被划分到单一的类中
  • 改进模型:

      1. K-means++:在初始类中心选取的时候,聚类中心会相互离的很远,不再是随机选择。
      1. ISODATA: K 值的选取。核心思想:当某个类别的样本数过少时,把该类去掉;当某个类的样本数过多、分数程度大的时候,将该类分为两个子类别。此时对应了三个参数,预期的聚类中心数目,每个类要求的最少样本数目(用于去掉某个类别),最大方差(用于控制某个类别中样本的分散程度),两个聚类中心之间允许的最小距离(当两个类靠很近时,进行合并操作)

8. 高斯混合模型的核心思想?它是如何迭代计算的?

  • 高斯混合模型是 生成式模型。核心思想假设数据可以看做从多个高斯分布中生成出来。在该假设下,每个单独的分模型都是标准高斯模型,其均值 和 方差 $\mu_i, \theta_i$ 都是待估计参数。每个分模型还有一个参数 $\pi_i$, 理解为权重和生成数据的概率。

  • 高斯混合模型的求解为 EM 算法

    • E-step: 根据当前参数,计算某个点由某个分模型生成的概率
    • M-step: 根据 E 步估计的概率,通过求导令偏导数为 0,改进每个分模型的均值、方差和权重参数。

以聚类问题为例,假设没有外部标签,如何评估两个聚类算法的优劣?

  • 以中心定义的数据簇:聚类后的集合到其中心(该类的评价值)的距离越小越好

  • 以密度定义的数据粗:这类数据城乡与周围数据簇明显不同的密度。该情况通常用于没有噪声点和离群点。

  • 以连通定义的数据簇: 这里数据集合中数据点和数据点之间有连接关系,整个数据簇表现为图结构。该定义对不规则形状和缠绕的数据簇有效。

  • 以概念定义的数据簇:该类数据集合中所有数据点具有某种性质。

  • 聚类算法的评估:

    • CH 指标 (Calinski-Harabasz):

    • 轮廓系数 (Silhouette Coefficient):
      每个样本都对应轮廓系数,其由两部分组成:$a$: 样本与同一簇中其他样本的平均距离。 $b$: 样本距离最近簇类中所有样本点的平均距离。
      轮廓系数:

常见的概率图模型中,那些是生成式模型?那些是判别式模型?

  • 判别式模型与生成式模型的区别:假设课管泽的变量集合为 $X$, 需要预测的变量集合为 $Y$, 其他变量集合为 $Z$。 生成式模型对联合概率 $P(X, Y, Z)$ 进行建模。在给定观测集合 $X$ 的条件下,通过计算边缘分布来得到对变量集合 $Y$ 的推断。即

    判别式模型则是直接对条件概率分布 $P(Y, Z|X)$ 进行建模,消去无关变量 $Z$ 就可以得到对变量集合 $Y$ 的预测。

  • 生成式模型:朴素贝叶斯,贝叶斯网络,pLSA, LDA, HMM

  • 判别式模型:最大熵模型, CRF

  • HMM —> MEMM(最大熵马尔科夫模型)(解决 HMM 输出独立性假设的问题,但是只是解决了观测值独立的问题,状态之间的假设可能会产生标注偏置问题) —> CRF(解决了标注偏置问题,去除了 HMM 中两个不合理的假设)

坚持原创技术分享,您的支持将鼓励我继续创作!