《统计学习方法》读书笔记5:决策树

  1. 决策树像是if-then的规则集合。
  2. 决策树很可能发生过拟合现象,这时需要自下而上的剪枝。决策树的生成只考虑局部最优,而剪枝考虑全局最优。
  3. 特征选择时需要选取具有分类能力的特征,如果利用一个特征进行分类与随机分类的结果没有区别,则称这个特征没有分类能力。通常特征选择的标准是信息增益或信息增益比。
  4. 信息增益
    1. 熵(entropy)表示的是一个随机变量不确定的程度。设$X$是一个取有限值的离散随机变量,它的熵定义为
      $$ H(X)=-\sum_{i=1}^Np_i \log p_i $$
      如果与 $X$ 取值无关,只与其分布有关,还可以记作 $H(p)$。对数以2为底时,熵的单位为比特(bit);以 $e$ 为底时,单位为奈特(nat)。
    2. 条件熵 $H(Y|X)$ 表示已知 $X$ 的条件下,随机变量 $Y$ 的不确定程度
      $$
      H(Y|X)=\sum_{i=1}^Np_iH(Y|X=x_i)
      $$
    3. 信息增益:指给定特征 $A$ 的情况下,训练数据集 $D$ 的不确定性的减少量
      $$
      g(D, A) = H(D) - H(D|A)
      $$
      在信息论中称为互信息。$H(D)$ 是由训练集的经验概率得到的,所以称为经验熵
    4. 在实际选取过程中,根据信息增益大小选择特征
    5. 为了解决偏向于选择取值较多的特征的问题,可以用信息增益比:
      $$
      g_R(D,A) = \frac{g(D,A)}{H_A(D)}
      $$
      其中,$ H_A(D) = -\sum_{i=1}^n\frac{|D_i|}{|D|}\log_2\frac{|D_i|}{|D|} $
  5. 决策树的生成
    1. ID3算法:每次挑选信息增益最大的特征分裂数据集,直到信息增益小于某一阈值。
    2. C4.5算法:改进了ID3算法,使用信息增益比
  6. 决策树的剪枝
    1. 决策树的剪枝通过极小化决策树的损失函数完成。
    2. 决策树的损失函数定义为
      $$
      C_\alpha(T)=\sum_{i=1}^{|T|}N_tH_t(T)+\alpha|T|
      $$
      其中,经验熵为
      $$
      H_t(T)=-\sum_k\frac{H_{tk}}{N_t}\log\frac{N_{tk}}{N_t}
      $$
      通常,记
      $$
      C(T)=\sum_{t=1}^{|T|}N_tH_t(T)=-\sum_{t=1}^{|T|}\sum_{k=1}^KN_{tk}\log\frac{N_{tk}}{N_t}
      $$
      这时有
      $$
      C_\alpha(T)=C(T)+\alpha|T|
      $$
    3. 设一组节点回缩到其父节点之前与之后的整体树分别为$T_B$与$T_A$,其对应的损失函数分别为$C_\alpha(T_B)$与$C_\alpha(T_A)$,如果
      $$
      C_\alpha(T_A)\leq C_\alpha(T_B)
      $$
      则进行剪枝,即将父节点变为新的叶节点。重复这一过程,直至不能进行为止。
  7. CART算法
    1. CART(classification and regression tree)
    2. 回归树:X和Y分别为输入变量与输出变量,且Y为连续变量
    3. 分类树
      1. 基尼系数
      2. 根据基尼系数生成回归树

《统计学习方法》学习笔记4:朴素贝叶斯法

  1. 朴素贝叶斯方法是基于贝叶斯定律的方法。它做出了条件独立这个强条件假设,在损失一定分类准确性的情况下使算法可行。
  2. 推导过程使用贝叶斯定理,最终的结果为
    $$
    y = \arg\max_{c_k}P(Y=c_k)\prod\nolimits_jP(X^{(j)}=x^{(j)}|Y=c_k)
    $$
  3. 朴素贝叶斯实际上是另后验概率最大化。这等价于期望风险最小化。
  4. 计算朴素贝叶斯参数的方法是极大似然估计。
  5. 考虑出现概率0的情况,这会影响极大似然估计的结果。解决这一问题的方法是采用贝叶斯估计。条件概率的贝叶斯估计是
    $$
    P_\lambda (X^{(j)} = a_{jl} | Y = c_k) = \frac{\sum_{i=1}^N I(x_i^{(j)} = a_{jl}, y_i = c_k) + \lambda}{\sum_{i=1}^N I(y_i = c_k) + S_j\lambda}
    $$
    式中 $ \lambda \geqslant 0 $。当 $ \lambda = 0 $ 时就是极大似然估计。常取 $ \lambda = 1 $,这时称为拉普拉斯平滑(Laplace smoothing)。
  6. 先验概率的贝叶斯估计是
    $$
    P_\lambda (Y = c_k) = \frac{\sum_{i=1}^NI(y_i = c_k) + \lambda}{N+K\lambda}
    $$

《统计学习方法》学习笔记3:k近邻法

  1. k近邻法(k-nearest neighbor, k-NN)是一种基本分类与回归方法。这里只讨论分类问题的kNN。
  2. k近邻法的算法
    1. 输入
      训练集 $$ T = \lbrace(x_1, y_1), (x_2, y_2), \cdots , (x_N, y_N)\rbrace $$
      其中,$ x_i \in \mathcal{X} \subseteq \mathbf{R}^n $为实例的特征向量,$ y_i \in \mathcal{Y} = {c_1, c_2, \cdots ,c_K} $ 为实例的类别,$ i=1,2, \cdots , N $;实例特征向量 $ x $;
    2. 输出实例$ x $所属的类 $ y $。
    3. 过程
      1. 根据给定的距离度量,找出与$x$最邻近的$k$个点,这个邻域记作$N_k(x)$
      2. 在$N_k(x)$中根据分类决策规则(如多数表决)决定$x$的类别$y$:
        $$ \arg\max_{c_j}\sum_{x_i \in N_k(x)}I(y_i=c_j), i=1,2,\cdots,N;\ j=1,2,\cdots,K $$
        其中,$I$为指示函数,即当$y_i=c_i$时$I$为1,否则$I$为0
  3. $k=1$是一种特殊情况,称为最邻近算法。
  4. k近邻法的模型三要素是距离度量$k$值分类决策规则
    1. 基本概念
      1. 单元(cell):距离该点比其他点更近的所有点组成的一个区域。每个训练实例拥有一个单元。
      2. 类标记(class label):每个单元的类别。最邻近法将实例$x_i$的类$y_i$作为其单元中所有点的类标记。
    2. 距离度量
      1. $L_p$距离定义为
        $$ L_p(x_i, x_j) = \left(\sum_{l=1}^n|x_i^{(l)}| - x_j^{(l)}|^p\right)^\frac{1}{p} $$
      2. 当$L_p$距离中$p$取2时,称为欧氏距离(Euclidean distance)
      3. 当$L_p$距离中$p$取1时,称为曼哈顿距离(Manhattan distance)
      4. 当$L_p$距离中$p$取$\infty$时,它是各个坐标距离的最大值,即
        $$ L_\infty(x_i, y_i) = \max_l|x_i^{(l)}-x_j^{(l)}| $$
      5. 此外还有Minkowski距离
      6. 距离度量不同,最邻近点不同
    3. $k$值越小意味着模型越复杂,更容易过拟合。通常$k$取一个较小的值。通常采用交叉验证法确定$k$值。
    4. 分类决策规则:$k$近邻法的分类决策往往是多数表决。分类函数为
      $$ f: \mathbf{R}^n \rightarrow \lbrace c_1, c_2, \cdots , c_K \rbrace $$
      误分类的概率是
      $$ P(Y \neq f(X)) = 1 - P(Y=f(X)) $$
      对给定的实例$x \in \mathcal{X}$,其最邻近的$k$个训练实例点构成集合$N_k(x)$。如果涵盖$N_k(x)$的区域类别是$c_j$,那么误分类率是
      $$ \frac{1}{k}\sum_{x_i \in N_k(x)}I(y_i \neq c_j) = 1-\frac{1}{k}\sum_{x_i \in N_k(x)}I(y_i=c_j) $$
      要使误分类最小即经验风险最小,就要使$ \sum_{x_i \in N_k(k)}I(y_i = c_j) $最大,所以多数表决规则等价于经验风险最小化。
  5. 计算kNN的算法是kd树。kd树是一种对$k$维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。注意这里的$k$与$k$近邻的$k$并不是一个含义。它等于特征向量的维数。

《统计学习方法》读书笔记2:感知机

  1. 感知机(perceptron)的输入空间是$ \mathcal{X}\subseteq\mathbf{R}^n $,输出空间是 $ \mathcal{Y} = \lbrace +1, -1 \rbrace $,输入空间到输出空间的函数是 $$ f(x) = \rm{sign}(w \cdot x + b) $$ 其中,sign是符号函数

$$ \rm{sign}(x) =
\begin{cases}
+1, & x \geqslant 0\newline
-1, & x < 0
\end{cases}
$$

  1. 如果存在一个超平面可以将数据的正类负类分开,那么数据被称为线性可分的。
  2. 感知机只能处理线性可分的数据。
  3. 感知机的损失函数,是所有错误分类的点到超平面的距离之和
    $$
    -\frac{1}{\Vert w \Vert}\sum_{x_i \in M}y_i(w \cdot x_i + b)
    $$
    因为 $ \frac{1}{\Vert w \Vert} $ 是常数,所以可以忽略掉它得到最终的损失函数
    $$
    L(w,b) = - \sum_{ x \in M }y_i(w \cdot x_i + b)
    $$
    使用此函数而不是误分类数作为代价函数的好处是,这个函数可导,便于计算。
  4. 感知机学习算法的原始形式
    1. 选取初值 $ w_0 $, $ b_0 $
    2. 在训练集中选取数据 $ ( x_i , y_i) $
    3. 如果 $ y_i(w \cdot x_i + b) \leqslant 0 $
      $ w \leftarrow w + \eta y_i x_i $
      $ b \leftarrow b + \eta y_i $
    4. 转至2,直至训练集中没有误分类点
  5. 可以证明,算法是收敛的,也就是经过有限次,一定能将线性可分的数据完全正确分类。但是解唯一。证明方法留待以后看。
  6. 感知机存在一个对偶解法,使用对偶解法的原因可以查看这个知乎帖子
  7. 感知机模型的对偶解法还需要仔细理解,以后补充。

《统计学习方法》读书笔记1:概论

  1. 统计学习的三要素是是模型策略、和算法。方法 = 模型 + 策略 + 方法。
    1. 模型就是所要学习的条件概率分布或决策函数。
    2. 按照什么样的准则学习或选择最优模型就是策略
      1. 首先要引入损失函数的概念,度量预测错误的程度。
      2. 风险函数或期望损失指的是损失函数的期望$$ R_{exp}(f) = E_p[L(Y, f(X)))] = \int_{\mathcal{X}\times\mathcal{Y}}L(y, f(x))P(x, y)dxdy $$ 学习的目标是让期望损失最小化。但是P(x,y)未知,所以无法得到这个期望。于是一个替代办法是使用经验风险或经验损失替代 $$ R_{emp}(f)=\frac{1}{N}\sum_{i=1}^NL(y_i, f(x_i)) $$ 根据大数定律,样本足够大时$ R_{emp}(f) $会趋于$ R_{exp}(f) $。但是样本不足时就会有偏差,需要矫正。
      3. 经验风险最小化指的就是上面所说的直接最小化 $ R_{emp}(f) $。结构风险最小化是为了防止样本不足产生的偏差。结构风险最小化等价于正则化,结构风险的定义是 $$ R_{srm}(f) = \frac{1}{N}\sum_{i=1}^NL(y_i, f(x_i))+\lambda J(f) $$
      4. 贝叶斯中的极大后验概率估计(maximum posterior probability estimation, MAP)是结构风险最小化的一个例子。
    3. 算法是指具体的计算方法。
  2. 模型评估需要引入训练误差和测试误差。训练误差能判定当前的方法是不是能学习这些数据,测试误差反应了预测未知数据的能力。如果学习方法训练误差很小而测试误差很大,这种现象就是过拟合。在模型选取中,应该用结构风险最小化的方式避免过拟合。

- 阅读剩余部分 -