频繁项集

• 频繁项集：频繁出现项集合（无序）
• 频繁项序列：频繁出现项序列（有序）

• 相关关联规则算法：数据量大时，无法直接发现频繁项集
• 频繁项集评估标准

评估标准

• 支持度：数据关联出现概率，关联数据在数据集中出现次数占 总数据集比重

  $$Support(X, Y) = P(XY) = \frac {num(XY)} {num(All)}$$
  • 支持度高数据不一定构成频繁项集，但支持度数据肯定不能 不构成频繁项集

• 置信度：数据出现条件概率，某个数据出现、另一数据出现概率

  $$Confidence(X \Leftarrow Y) = P(X|Y) = \frac {P(XY)} {P(Y)}$$

• 提升度：数据之间关联关系，某数据出现、另一数据出现概率同 其总体出现概率之比

  $$\begin{align*} Lift(X \Leftarrow Y) & = \frac {P(X|Y)} {P(X)} \\ & = \frac {Confidence(X \Leftarrow)}{P(X)} \\ & = \frac {P(XY)} {P(X)P(Y)} \end{align*}$$
  • 提升度大于1则为有效的强关联规则，否则为无效的强关联 规则
  • 若X、Y不相关，则提升度为1

• 选择频繁数据集，一般需要自定义评估标准：自定义支持度、 自定义支持度和置信度组合

Apriori

Apriori算法

• 以支持度作为评估标准，找出数据集中最大的频繁$k$项集
  • 找到符合支持度标准的频繁$k$项集
  • 迭代直到无法找到项数更大的频繁项集

算法

• 输入：数据集合D、支持度阈值$\alpha$
• 输出：最大的频繁K项集

• 置$k=1$，扫描整个数据集，以所有出现过数据作为候选1项集
• 挖掘候选$k$项集
  • 扫描数据、计算候选$k$项集支持度
  • 去除支持度低于阈值$\alpha$的项集得到频繁$k$项集
    • 若频繁$k$项集只包含1项，直接返回
    • 若频繁$k$项集为空，返回频繁$k-1$项集
  • 基于频繁$k$项集连接、生成候选$k+1$项集
  • 置$k=k+1$

• 需要频繁扫描数据、效率低
• 频繁项集的子项集肯定也是频繁项集

FPTree/FPGrowth

FPTree：对Apriori算法改进，不在需要多次扫描数据

• FPTree引入部分数据结构以临时存储数据

  

  • 项头表：按频繁1项集出现频数降序排列的表
  • FP Tree：包含原始数据、频数的多叉树
  • 节点链表：链接项头表中频繁1项集、FPTree中相应节点 的链表

• 特点：效率高

  • 只需要扫描两次数据
  • 使用多叉树存储临时数据，利用高频频繁项集

算法

• 建立项头表

  • 扫描数据，得到所有1项集频数、剔除支持度低于阈值者， 并按支持度（频数）降序排列
  • 第二次扫描数据，剔除每条数据中非频繁1项集、 在每条数据内部按支持度降序排列

  

• 建立FPTree：逐条读取处理后排序后数据，依次插入树中

  • 每条数据中排序靠前者为祖先节点
  • 若有直系公共祖先则公共祖先节点计数+1
  • 新节点通过链表和项头表链接

  

• 挖掘FPTree：对项表头中每项，找到其条件模式基

  • 将子树中每个节点计数置为叶子节点计数和，则子树中节点 取值即为其与当前项组合出现频数/支持度
  • 删除（当前子树内）支持度/频数低于支持度阈值$\alpha$ 节点
  • 剩余节点项、当前项组合即为相应频繁$k$项集

  

  • 条件模式基：节点作为叶子节点所对应的FP子树

Prefix-Projected Pattern Growth

PrefixSpan：前缀投影模式挖掘

• 以支持度为标准，挖掘数据集中频繁序列
  • 每条数据为若干项集组成的序列，序列内项集间有序
  • 为方便，每条数据序列中项集中的项已排序

• 可以将每条数据序列整体视为串
• 频繁序列：频繁出现子序列

算法

• 输入：序列数据集$S$、支持度$\alpha$
• 所有满足阈值要求的频繁序列

• 找出所有长度1前缀（即所有项）、对应投影

  • 计数、剔除持度小于阈值$\alpha$者，得到频繁1项序列
  • 置$k=1$

• 对每个长度为$k$前缀递归挖掘

  • 若前缀对应投影为空，返回
  • 若前缀对应投影中所有项支持度均小于阈值$\alpha$，返回
  • 同满足阈值要求阈值$\alpha$要求项合并，得到新前缀
  • 置$k=k+1$

• prefix：前缀，正在处理的子序列
• projected：投影，各数据序列中位于前缀之后子串 ?串

聚类算法

聚类：按照某特定标准（如距离准则）把数据集分割成不同类、簇， 簇内数据相似性尽可能大、不同簇间数据对象差异性仅可能大

• 属于无监督学习，目标是把相似的样本聚集在一起

  • 通常只需要给定相似度的计算即可
  • 无需使用训练数据学习

• 聚类算法分类

  • 基于划分
  • Hierarchical Methods：基于层次
  • 基于密度
  • 基于网络
  • 基于模型
  • 模糊聚类
  • 基于约束
  • 基于粒度
  • 谱聚类
  • 核聚类
  • 量子聚类

衡量聚类算法优劣

• 算法的处理能力

  • 处理大数据的能力
  • 处理噪声数据能力
  • 处理任意形状数据的能力，如：有间隙的嵌套数据

• 算法是否需要预测条件

  • 聚类数目
  • 相关领域知识

• 输入数据关联性

  • 结果是否和数据输入顺序相关
  • 对数据维度敏感性（是否能处理高维数据）
  • 对数据类型要求

Hierarchical Methods

层次聚类

• 自底向上合并的层次聚类

  • 最底层开始，通过合并最相似类簇形成上层类簇
  • 全部数据点合并到同一类簇、或达到终止条件时结束

• 自顶向下分裂的层次聚类

  • 从包含全部数据点的类簇开始，递归分裂出最相异的下层 类簇
  • 每个类簇仅包含单个数据点时结束

• 优点

  • 可解释性好：如需要创建分类方法时
  • 研究表明能产生高质量聚类，可以应用在较大K的K-means 后的合并阶段
  • 可以解决非球形类簇

• 缺点

  • 时间复杂度高$O(N^2 log N)$（$N$为数据点数目）
  • 贪心算法无法取得最优解

• 距离选择参见ml_tech/#todo

AGENS

AGENS：自下向上层次聚类

• 组连接：组与组之间距离
  • single linkage
  • average linkage
  • complete linkage
• 算法复杂度：$n^2logn$

流程

• 每个数据点视为一类，计算两两直接最小距离
• 合并距离最小两个两类别为新类
• 重新计算新类、所有类之间距离
• 重复以上，直至所有类合并为一类

Divisive Analysis

DIANA：自定向下层次聚类

算法流程

• 所有数据归为一组$C_1=(p_1, p_2, dots, p_n)$
• 计算所有点之间的距离矩阵，选择到其他点平均距离最大的点， 记为$q$，取该点作为新组起始点
• $\forall p, p \notin C_1$，计算 $d_arg(p, C_1) - d_arg(p, C_2)$， 若小于零则属于$C_1$，否则属于$C_2$

Balanced Itertive Reducing and Clustering Using Hierarchies

BIRCH：利用层次方法的平衡迭代规约和聚类，利用层次方法聚类 、规约数据

• 特点
  • 利用CF树结构快速聚类
  • 只需要单遍扫描数据
  • 适合在数据类型为数值型、数据量大时使用

常见算法、改进

• A Hierarchical Clustering Algorithm Using Dynamic Modeling：使用KNN算法计算作为linkage、构建图
  • 较BIRCH好，但算法复杂度依然为$O(n^2)$
  • 可以处理比较复杂形状

Partition-Based Methods

基于划分的方法

• 基本流程

  • 确定需要聚类的数目，挑选相应数量点作为初始中心点
  • 再根据预定的启发式算法队数据点做迭代
  • 直到达到类簇内点足够近、类簇间点足够远

• 优点

  • 对大型数据集同样简单高效、时空复杂度低

• 缺点

  • 数据集越大，结果容易越容易陷入局部最优
  • 需要预先设置k值，对初始k中心点选取敏感
  • 对噪声、离群点敏感
  • 只适合数值性
  • 不适合非凸形状

• 影响结果因素

  • 原始问题是否可分
  • 分类数目K
  • 初始点选择

K-means

• 数据：$\Omega={X_1, X_2, \dots, X_N}$，分k个组

  $$C_1, C_2, \dots, C_k \\ C_1 \cup C_2 \cup \dots \cup C_k = \Omega \\$$

  每个样本点包含p个特征：$X_i = (x_1, x_2, \dots, x_p)$

• 目标：极小化每个样本点到聚类中心距离之和

  $$\arg_{C_1, C_2, \dots, C_K} \min \sum_{i=1}^K \sum_{x_j in \C_i} d(x_j, C_i)$$
  • 若定义距离为平方欧式距离，则根据组间+组内=全， 极小化目标就是中心点距离极大化

• 优化问题是NP-hard问题，需要采用近似方法

K值选择

• 经验选择
• 特殊方法：Elbow Method，肘部法则，画出距离和K的点图， 选择剧烈变化的点的K值

Lloyd’s Algorithm

• 随机选择K对象，每个对象初始地代表类簇中心
• 对剩余对象，计算与各簇中心距离，归于距离最近地类簇
• 重新计算各类簇平均值作为新簇中心
• 不断重复直至准则函数收敛

• 算法时间效率：$\in O(K * N^{\pi})$

常见算法、改进

• K-means++、Intelligent K-means、Genetic K-means：改进 K-means对初值敏感
• K-medoids、K-medians：改进K-means对噪声、离群点敏感
• K-modes：适用于分类型数据
• Kernel-Kmeans：可以解决非凸问题

Density-Based Methods

基于密度的方法

• 优点
  • 对噪声不敏感
  • 能发现任意形状聚类
• 缺点
  • 聚类结果和参数关系很大

相关概念

• 核心点：半径eps的邻域内点数量不少于阈值MinPts的点

• 直接可达：核心点半径eps的领域内被称为直接可达

  • 没有任何点是由非核心点直接可达的

• 可达：若存在$p_1, \cdots, p_n$点列中相邻点直接可达， 则$p_1, p_n$可达

  • 非对称关系，因为核心点没有直接可达点

• 连接性：若存在点$o$可达$p,q$，则$p,q$称为[密度]连接

  • 对称关系
  • 聚类内点都是相连接的
  • 若p由q可达，则p在q所属聚类中

• 局外点：不由任何点可达的点

DBSCAN

• Density-Based Spatial Clustering of Applications with Noise

算法流程

• 从任意对象点p开始
• 寻找合并核心点p对象直接密度可达对象
  • 若p是核心点，则找到聚类
  • 若p是边界，则寻找下个对象点
• 重复直到所有点被处理

说明

• DBSCAN用固定参数识别聚类，类簇稀疏程度不同时，相同判断 标准会破坏类自然结构

  • 较稀疏类簇会被划分为多个
  • 密度大距离近多个类被合并

• 参数影响

  • eps过大大多数点聚为同一簇中、过小则会导致簇分裂
  • MinPts值过大则同簇中点被标记为噪声点、过小则有大量 核心点

• 超参半径eps、最小点数量MinPts经验选取

  • 计算所有点k距离
  • 对各点k距离排序、绘制折线图
  • 观察折线图，以发现极具变化的位置对应k距离作为半径
  • k即作为最小点数量

  • k距离：距离点第k近点距离

常见算法、改进

• Ordering Points to Indentify Clustering Structure：优先 搜索高密度，然后根据高密度特点设置参数，改善DBSCAN

Grid-Based Methods

基于网络的方法

• 优点

  • 速度快，速度与数据对象个数无关，只依赖数据空间中每维 上单元数目
  • 可以和基于密度算法共同使用

• 缺点

  • 对参数敏感
  • 无法处理不规则分布的数据
  • 维数灾难
  • 聚类结果精确性低：算法效率提高的代价

流程

• 将数据空间划分为网格单元：不同算法主要区别
• 将数据对象集映射到网格单元中，计算各单元密度
• 根据预设的阈值判断每个网格单元是否为高密度单元
• 将相连的高度密度网格单元识别为类簇

常见算法、改进

• statistical information grid
• wave-cluster
• clustering-quest

Model-Based Methods

基于模型的方法：为每个类簇假定模型，寻找对给定模型的最佳拟合

• 优点
  • 对类划分以概率形式表示
  • 每类特征可以用概率表达
• 缺点
  • 执行效率不高，尤其是分布数量多、数据量少时

SOM

SOM：假设输入对象中存在一些拓扑结构、顺序，可以实现从输入 空间到输入平面的降维映射，且映射具有拓扑特征保持性质

• 网络结构

  • 输入层：高维输入向量
  • 输入层：2维网络上的有序节点

• 学习过程

  • 找到、更新与输入节点距离最短的输出层单元，即获胜单元
  • 更新邻近区域权值，保持输出节点具有输入向量拓扑特征

SOM算法流程

• 网络初始化：初始化输出层节点权重
• 随机选取输入样本作为输入向量，找到与输入向量距离最小的 权重向量
• 定义获胜单元，调整获胜单元邻近区域权重、向输入向量靠拢
• 收缩邻域半径、减小学习率、重复，直到小于允许值，输出聚类 结果

常见算法

• 概率生成模型：假设数据是根据潜在概率分布生成
  • Gaussian Mixture Model
• 基于神经网络模型的方法
  • Self Organized Maps

模糊聚类

模糊聚类：样本以一定概率属于某个类

• 优点
  • 对正态分布的数据聚类效果较好
  • 算法对孤立点敏感

Fuzzy C-means(FCM)

FCM：对K-means的推广软聚类

• 算法最终输出$C$个聚类中心向量、$C*N$模糊划分矩阵

  • 表示每个样本点对每个类的隶属度
  • 根据划分矩阵、按照最大隶属原则确定样本点归属
  • 聚类中心表示类平均特征，可以作为类代表

• 特点

  • 算法性能依赖初始聚类中心，需要依赖其他算法快速确定 初始聚类中心、或多次执行算法
  • 不能确保收敛于最优解

• soft cluster：点可以属于多个类

参数选择

• 聚类数目$C$：$C$远远小于聚类样本总数目，且大于1
• 柔性参数$m$
  • $m$过大：聚类效果差
  • $m$过小：算法接近HCM聚类算法

算法流程

• 标准化数据矩阵
• 建立模糊相似矩阵，初始化隶属矩阵

• 迭代，直到目标函数收敛到极小值

  $$w_k(x_i) = \frac 1 \sum_{i=1}^k (\frac {d(x_i, \mu_k)} {d(x_i, \mu_i} )^{1/(m-2)})$$

• 根据迭代结果，由最终隶属矩阵确定数据所属类，得到聚类结果

常见算法、改进

• HCM算法

基于约束的算法

基于约束的算法：考虑聚类问题中的约束条件，利用约束知识进行 推理

• 约束

  • 对聚类参数的约束
  • 对数据点的约束

• 典型算法

  • Clustering with Obstructed Distance：用两点之间障碍 距离取代一般的欧式距离计算最小距离

量子聚类

量子聚类：用量子理论解决聚类过程中初值依赖、确定类别数目的 问题

• 典型算法
  • 基于相关点的Pott自旋、统计机理提供的量子聚类模型： 将聚类问题视为物理系统

核聚类

核聚类：增加对样本特征的优化过程，利用Mercer核把输入空间映射 至高维特征空间，在特征空间中进行聚类

• 特点

  • 方法普适
  • 性能上优于经典聚类算算法
  • 可以通过非线性映射较好分辨、提取、放大有用特征
  • 收敛速度快

• 典型算法

  • SVDD算法
  • SVC算法

谱聚类

谱聚类：建立在图论中谱图理论基础上，本质是将聚类问题转换为 图的最优划分问题

基本流程

• 根据样本数据集定义描述成对数据点的相似度亲和矩阵
• 计算矩阵特征值、特征向量
• 选择合适的特征向量聚类不同点

自编码机/稀疏编码/堆栈自编码器

• 起源：编码理论可以应用于视觉皮层感受野，大脑主要视觉皮层 使用稀疏原理创建可以用于重建输入图像的最小基函数子集

• 优点

  • 简单技术：重建输入
  • 可堆栈多层
  • 直觉型，基于神经科学研究

• 缺点

  • 贪婪训练每层
  • 没有全局优化
  • 表现较监督学习差
  • 多层容易失效
  • 输入的重建可能不是学习通用表征的理想metric

总述

expectation maximization algorithm：含有隐变量的概率模型 参数的极大似然估计法、极大后验概率估计法

• 模型含有latent variable（潜在变量）、hidden variable （隐变量）似然函数将没有解析解

• 所以EM算法需要迭代求解，每次迭代由两步组成

  • E步：求期望expectation
  • M步：求极大maximization

• 模型变量都是observable variable、给定数据情况下，可以 直接使用极大似然估计、贝叶斯估计

EM算法

对含有隐变量的概率模型，目标是极大化观测数据（不完全数据） $Y$关于参数$\theta$的对数似然函数，即极大化

$$\begin{align*} L(\theta) & = log P(Y|\theta) \\ & = log \sum_Z P(Y, Z|\theta) \\ & = log \left(\sum_Z P(Y|Z,\theta) P(Z|\theta) \right) \end{align*}$$

• $Y$：观测变量数据
• $Z$：隐随机变量数据（未知）
• $Y,Z$合在一起称为完全数据
• $P(Y,Z|\theta)$：联合分布
• $P(Z|Y,\theta)$：条件分布

• 但是极大化目标函数中包括未观测数据$Z$、求和（积分）的 对数，直接求极大化非常困难
• EM算法通过迭代逐步近似极大化$L(\theta)$

推导

• 假设第i次迭代后$\theta$的估计值是$\theta^{(i)}$，希望 新估计值$\theta$能使$L(\theta)$增加，并逐步增加到极大值 ，考虑两者之差

  $$L(\theta) - L(\theta^{(i)}) = log (\sum_Z P(Y|Z,\theta) P(Z|\theta)) - log P(Y|\theta^{(i)})$$

• 利用Jensen不等式有

  $$\begin{align*} L(\theta) - L(|\theta^{(i)}) & = log(\sum_Z P(Y|Z, \theta^{(i)}) \frac {P(Y|Z,\theta) P(Z|\theta)} {P(Y|Z,\theta^{(i)})}) - log P(Y|\theta^{(i)}) \\ & \geq \sum_Z P(Z|Y,\theta^{(i)}) log \frac {P(Y|Z,\theta) P(Z|\theta)} {P(Z|Y,\theta^{(i)})} - log P(Y|\theta^{(i)}) \\ & = \sum_z P(Z|Y,\theta^{(i)}) log \frac {P(Y|Z,\theta) P(Z|\theta)} {P(Z|Y,\theta^{(i)}) P(Y|\theta^{(i)})} \end{align*}$$

• 令

  $$B(\theta, \theta^{(i)}) = L(\theta^{(i)}) + \sum_Z P(Z|Y,\theta^{(i)}) log \frac {P(Y|Z,\theta) P(Z|\theta)} {P(Z|Y,\theta^{(i)}) P(Y|\theta^{(i)})}$$

  则$B(\theta, \theta^{(i)})$是$L(\theta)$的一个下界，即

  $$\begin{align*} L(\theta) & \geq B(\theta, \theta^{(i)}) \\ \end{align*}$$

  并根据$B(\theta, \theta^{(i)})$定义有

  $$\begin{align*} L(\theta^{(i)}) = B(\theta^{(i)}, \theta^{(i)}) \end{align*}$$

• 则任意$\theta$满足 $B(\theta,\theta^{(i)}) > B(\theta^{(i)},\theta^{(i)})$ ，将满足$L(\theta) > L(\theta^{(i)})$，应选择 $\theta^{(i+1)}$使得$B(\theta,\theta^{(i)})$达到极大

  $$\begin{align*} \theta^{(i+1)} & = \arg\max_{\theta} B(\theta,\theta^{(i)}) \\ & = \arg\max_{\theta} L(\theta^{(i)}) + \sum_Z P(Z|Y,\theta^{(i)}) log \frac {P(Y|Z,\theta) P(Z|\theta)} {P(Z|Y,\theta^{(i)}) P(Y|\theta^{(i)})} \\ & = \arg\max_{\theta} (\sum_Z P(Z|Y,\theta^{(i)}) log(P(Y|Z,\theta)P(Z|\theta))) \\ & = \arg\max_{\theta} (\sum_Z P(Z|Y,\theta^{(i)}) log P(Y,Z|\theta)) \\ & = \arg\max_{\theta} Q(\theta, \theta^{(i)}) \end{align*}$$

  • 和$\theta$无关的常数项全部舍去

• $Q(\theta, \theta^{(i)})$：Q函数，完全数据的对数似然函数 $logP(Y,Z|\theta)$，关于在给定观测$Y$和当前参数 $\theta^{(i)}$下，对未观测数据Z的条件概率分布 $P(Z|Y,\theta^{(i)})$ $$Q(\theta, \theta^{(i)}) = E_z [logP(Y,Z|\theta)|Y,\theta^{(i)}]$$

算法

1. 选择参数初值$\theta^{0}$，开始迭代

2. E步：记$\theta^{(i)}$为第$i$迭代时，参数$\theta$的估计值 ，在第$i+1$步迭代的E步时，计算Q函数 $Q(\theta, \theta^{(i)})$

3. M步：求使得Q函数极大化$\theta$作为第$i+1$次估计值 $\theta^{(i+1)}$

   $$\theta^{(i+1)} = \arg\max_{\theta} Q(\theta, \theta^{(i)})$$

4. 重复E步、M步直到待估参数收敛

• 算法初值可以任意选择，但EM算法对初值敏感

• E步：参数值估计缺失值分布，计算Q函数（似然函数）

• M步：Q函数取极大得新参数估计值

• 收敛条件一般是对较小正数$\epsilon$，满足 $|\theta^{(i+1)} - \theta^{(i)}| < \epsilon$或 $|Q(\theta^{(i+1)},\theta^{(i)}) - Q(\theta^{(i)},\theta^{(i)})| < \epsilon$

EM算法特点

EM算法优点

• EM算法可以用于估计含有隐变量的模型参数
• 非常简单，稳定上升的步骤能非常可靠的找到最优估计值
• 应用广泛，能应用在多个领域中
  • 生成模型的非监督学习

EM算法缺点

• EM算法计算复杂、受外较慢，不适合高维数据、大规模数据集
• 参数估计结果依赖初值，不够稳定，不能保证找到全局最优解

算法收敛性

定理1

• 设$P(Y|\theta)$为观测数据的似然函数，$\theta^{(i)}$为 EM算法得到的参数估计序列，$P(Y|\theta^{(i)}),i=1,2,…$ 为对应的似然函数序列，则$P(Y|\theta^{(i)})$是单调递增的 $$P(Y|\theta^{(i+1)}) \geq P(Y|\theta^{(i)})$$

• 由条件概率

  $$\begin{align*} P(Y|\theta) & = \frac {P(Y,Z|\theta)} {P(Z|Y,\theta)} \\ logP(Y|\theta) & = logP(Y,Z|\theta) - logP(Z|Y,\theta) \end{align*}$$

• 则对数似然函数有

  $$logP(Y|\theta) = Q(\theta, \theta^{(i)}) - H(\theta, \theta^{(i)})$$

  • $H(\theta, \theta^{(i)}) = \sum_Z log P(Z|Y,\theta) P(Z|Y,\theta)$
  • $Q(\theta, \theta^{(i)})$：前述Q函数
  • $logP(Y|\theta)$和$Z$无关，可以直接提出

• 分别取$\theta^{(i+1)}, \theta^{(i)}$带入，做差

  $$logP(Y|\theta^{(i+1)}) - logP(Y|\theta^{(i)}) = [Q(\theta^{(i+1)}, \theta^{(i)}) - Q(\theta^{(i)}, \theta^{(i)}] - [H(\theta^{(i+1)}, \theta^{(i)}) - H(\theta^{(i)}, \theta^{(i)})]$$

  • $\theta^{(i+1)}$使得$Q(\theta, \theta^{(i)})$取极大

  • 又有

    $$\begin{align*} & H(\theta^{(i+1)}, \theta^{(i)}) - H(\theta^{(i)}, \theta^{(i)}) \\ = & \sum_Z (log \frac {P(Z|Y,\theta^{(i+1)})} {P(Z|Y,\theta^{(I)})}) P(Z|Y,\theta^{(i)}) \\ \leq & log (\sum_Z \frac {P(Z|Y,\theta^{(i+1)})} {P(Z|Y,\theta^{(I)})} P(Z|Y,\theta^{(i)})) \\ = & log \sum_Z P(Z|Y,\theta^{(i+1)}) = 0 \end{align*}$$

定理2

• 设$L(\theta)=log P(Y|\theta)$为观测数据的对数似然函数， $\theta^{(i)},i=1,2,…$为EM算法得到的参数估计序列， $L(\theta^{(i)}),i=1,2,…$为对应的对数似然函数序列

  • 若$P(Y|\theta)$有上界，则$L(\theta^{(i)})$收敛到某 定值$L^{*}$
  • Q函数$Q(\theta, \theta^{‘})$与$L(\theta)$满足一定 条件的情况下，由EM算法得到的参数估计序列 $\theta^{(i)}$的收敛值$\theta^{*}$是$L(\theta)$的 稳定点

• 结论1由序列单调、有界显然

• Q函数$Q(\theta, \theta^{‘})$与$L(\theta)$的条件在大多数 情况下是满足的
• EM算法收敛性包含对数似然序列$L(\theta^{(i)})$、参数估计 序列$\theta^{(i)}$的收敛性，前者不蕴含后者
• 此定理只能保证参数估计序列收敛到对数似然序列的稳定点， 不能保证收敛到极大点，可选取多个不同初值迭代，从多个结果 中选择最好的

Gaussion Mixture Model

• 高斯混合模型是指具有如下概率分布模型 $$P(y|\theta) = \sum_{k=1}^K \alpha_k \phi(y|\theta_k)$$

  • $\alphak \geq 0, \sum{k=1}^K \alpha_k=1$：系数
  • $\phi(y|\theta_k)$：高斯分布密度函数
  • $\theta_k=(\mu_k, \sigma_k)$：第k个分模型参数

• 用EM算法估计高斯混合模型参数 $\theta=(\alpha_1,…,\alpha_2,\theta_1,…,\theta_K)$

推导

明确隐变量

明确隐变量，写出完全数据对数似然函数

• 反映观测数据$y_j$来自第k个分模型的数据是未知的

  $$\gamma_{j,k} = \left \{ \begin{array}{l} 1, & 第j个观测来自第k个分模型 \\ 0, & 否则 \end{array} \right.$$

  • $j=1,2,\cdots,N$：观测编号
  • $k=1,2,\cdots,K$：模型编号

• 则完全数据为

  $$(y_j,\gamma_{j,1},\cdots,\gamma_{j,K}), j=1,2,...,N$$

• 完全数据似然函数为

  $$\begin{align*} P(y,\gamma|\theta) & = \prod_{j=1}^N P(y_j,\gamma_{j,1},\cdots,\gamma_{j,N}|\theta) \\ & = \prod_{k=1}^{K} \prod_{j=1}^N [\alpha_k \phi(y_j|\theta_k)]^{\gamma _{j,k}} \\ & = \prod_{k=1}^{K} \alpha_k^{n_k} \prod_{j=1}^N [\phi(y_j|\theta_k)]^{\gamma _{j,k}} \\ \end{align*}$$

  • $nk = \sum{j=1}^{N} \gamma_{j,k}$
  • $\sum_{k=1}^K n_k = N$

• 完全数据的对数似然函数为

  $$logP(y, \gamma|\theta) = \sum_{k=1}^K \left \{ n_k log \alpha_k + \sum_{j=1}^N \gamma_{j,k} [log \frac 1 {\sqrt {2\pi}} - log \sigma_k - \frac 1 {2\sigma_k}(y_j - \mu_k)^2] \right \}$$

E步：确定Q函数

$$\begin{align*} Q(\theta, \theta^{(i)}) & = E_z[logP(y,\gamma|\theta)|Y,\theta^{(i)}] \\ & = E \sum_{k=1}^K \left \{ n_k log\alpha_k + \sum_{j=1}^N \gamma_{j,k} [log \frac 1 {\sqrt {2\pi}} - log \sigma_k - \frac 1 {2\sigma_k}(y_j - \mu_k)^2] \right \} \\ & = \sum_{k=1}^K \left \{ \sum_{k=1}^K (E\gamma_{j,k}) log\alpha_k + \sum_{j=1}^N (E\gamma_{j,k}) [log \frac 1 {\sqrt {2\pi}} - log \sigma_k - \frac 1 {2\sigma_k}(y_j - \mu_k)^2] \right \} \end{align*}$$

• $E\gamma{j,k} = E(\gamma{j,k}|y,\theta)$：记为 $\hat \gamma_{j,k}$

$$\begin{align*} \hat \gamma_{j,k} & = E(\gamma_{j,k}|y,\theta) = P(\gamma_{j,k}|y,\theta) \\ & = \frac {P(\gamma_{j,k}=1, y_j|\theta)} {\sum_{k=1}^K P(\gamma_{j,k}=1,y_j|\theta)} \\ & = \frac {P(y_j|\gamma_{j,k}=1,\theta) P(\gamma_{j,k}=1|\theta)} {\sum_{k=1}^K P(y_j|\gamma_{j,k}=1,\theta) P(\gamma_{j,k}|\theta)} \\ & = \frac {\alpha_k \phi(y_j|\theta _k)} {\sum_{k=1}^K \alpha_k \phi(y_j|\theta_k)} \end{align*}$$

带入可得

$$Q(\theta, \theta^{(i)}) = \sum_{k=1}^K \left\{ n_k log\alpha_k + \sum_{k=1}^N \hat \gamma_{j,k} [log \frac 1 {\sqrt{2\pi}} - log \sigma_k - \frac 1 {2\sigma^2}(y_j - \mu_k)^2] \right \}$$

M步

求新一轮模型参数 $\theta^{(i+1)}=(\hat \alpha_1,…,\hat \alpha_2,\hat \theta_1,…,\hat \theta_K)$

$$\begin{align*} \theta^{(i+1)} & = \arg\max_{\theta} Q(\theta,\theta^{(i)}) \\ \hat \mu_k & = \frac {\sum_{j=1}^N \hat \gamma_{j,k} y_j} {\sum_{j=1}^N \hat \gamma_{j,k}} \\ \hat \sigma_k^2 & = \frac {\sum_{j=1}^N \hat \gamma_{j,k} (y_j - \mu_p)^2} {\sum_{j=1}^N \hat \gamma_{j,k}} \\ \hat \alpha_k & = \frac {n_k} N = \frac {\sum_{j=1}^N \hat \gamma_{j,k}} N \end{align*}$$

• $\hat \theta_k = (\hat \mu_k, \hat \sigma_k^2)$：直接求 偏导置0即可得
• $\hat \alphak$：在$\sum{k=1}^K \alpha_k = 1$条件下求 偏导置0求得

算法

• 输入：观测数据$y_1, y_2,\cdots, y_N$，N个高斯混合模型
• 输出：高斯混合模型参数

1. 取参数初始值开始迭代

2. E步：依据当前模型参数，计算分模型k对观测数据$y_j$响应度

   $$\hat \gamma_{j,k} = \frac {\alpha \phi(y_k|\theta_k)} {\sum_{k=1}^N \alpha_k \phi(y_j|\theta)}$$

3. M步：计算新一轮迭代的模型参数 $\hat mu_k, \hat \sigma_k^2, \hat \alpha_k$

4. 重复2、3直到收敛

• GMM模型的参数估计的EM算法非常类似K-Means算法

  • E步类似于K-Means中计算各点和各聚类中心之间距离，不过 K-Means将点归类为离其最近类，而EM算法则是算期望
  • M步根据聚类结果更新聚类中心

GEM

Maximization-Maximization Algorithm

Free Energy函数

• 假设隐变量数据Z的概率分布为$\tilde P(Z)$，定义分布 $\tilde P$与参数$\theta$的函数$F(\tilde P, \theta)$如下 $$F(\tilde P, \theta) = E_{\tilde P} [log P(Y,Z|\theta)] + H(\tilde P)$$

• $H(\tilde P)=-E_{\tilde P} log \tilde P(Z)$：分布 $\tilde P(Z)$的熵
• 通常假设$P(Y,Z|\theta)$是$\theta$的连续函数，则函数 $F(\tilde P,\theta)$是$\tilde P, \theta$的连续函数

定理1

• 对于固定$\theta$，存在唯一分布$\tilde P\theta$，极大化 $F(\tilde P, \theta)$，这时$\tilde P\theta$由下式给出 $$\tilde P_\theta(Z) = P(Z|Y,\theta)$$ 并且$\tilde P_{\theta}$随$\theta$连续变化

• 对于固定的$\theta$，求使得$F(\tilde P, \theta)$的极大， 构造Lagrange函数

  $$L(\tilde P, \lambda, \mu) = F(\tilde P, \theta) + \lambda(1 - \sum_Z \tilde P(Z)) - \mu \tilde P(Z)$$

  因为$\tilde P(Z)$是概率密度，自然包含两个约束

  $$\left \{ \begin{array}{l} \sum_Z \tilde P(Z) = 1 \\ \tilde P(Z) \geq 0 \end{array} \right.$$

  即Lagrange方程中后两项

• 对$\tilde P(Z)$求偏导，得

  $$\frac {\partial L} {\partial \tilde P(Z)} = log P(Y,Z|\theta) - log \tilde P(Z) - \lambda - \mu$$

  令偏导为0，有

  $$\begin{align*} log P(Y,Z|\theta) - log \tilde P(Z) & = \lambda + \mu \\ \frac {P(Y,Z|\theta)} {\tilde P(Z)} & = e^{\lambda + \mu} \end{align*}$$

• 则使得$F(\tilde P, \theta)$极大的$\tilde P_\theta(Z)$ 应该和$P(Y,Z|\theta)$成比例，由概率密度自然约束有

  $$\tilde P_\theta(Z) = P(Y,Z|\theta)$$

  而由假设条件，$P(Y,Z|\theta)$是$\theta$的连续函数

• 这里概率密度函数$\tilde P(Z)$是作为自变量出现

• 理论上对$\tilde P(Z)$和一般的复合函数求导没有区别， 但$E_{\tilde P}, \sum_Z$使得整体看起来非常不和谐

  $$\begin{align*} E_{\tilde P} f(Z) & = \sum_Z f(Z) \tilde P(Z) \\ & = \int f(Z) d(\tilde P(Z)) \end{align*}$$

定理2

• 若$\tilde P_\theta(Z) = P(Z|Y, \theta)$，则 $$F(\tilde P, \theta) = log P(Y|\theta)$$

定理3

• 设$L(\theta)=log P(Y|\theta)$为观测数据的对数似然函数， $\theta^{(i)}, i=1,2,\cdots$为EM算法得到的参数估计序列， 函数$F(\tilde P,\theta)$如上定义

  • 若$F(\tilde P,\theta)$在$\tilde P^{}, \theta^{}$ 上有局部极大值，则$L(\theta)$在$\theta^{*}$也有局部 最大值
  • 若$F(\tilde P,\theta)$在$\tilde P^{}, \theta^{}$ 达到全局最大，则$L(\theta)$在$\theta^{*}$也达到全局 最大

• 由定理1、定理2有

  $$L(\theta) = logP(Y|\theta) = F(\tilde P_\theta, \theta)$$

  特别的，对于使$F(\tilde P,\theta)$极大$\theta^{8}$有

  $$L(\theta^{*}) = logP(Y|\theta^{*}) = F(\tilde P_\theta^{*}, \theta{*})$$

• 由$\tilde P_\theta$关于$\theta$连续，局部点域内不存在点 $\theta^{}$使得$L(\theta^{}) > L(\theta^{})$，否则 与$F(\tilde P, \theta^{})$矛盾

定理4

• EM算法的依次迭代可由F函数的极大-极大算法实现
• 设$\theta^{(i)}$为第i次迭代参数$\theta$的估计， $\tilde P^{(i)}$为第i次迭代参数$\tilde P$的估计，在第 i+1次迭代的两步为

  • 对固定的$\theta^{(i)}$，求$\tilde P^{(i)}$使得 $F(\tilde P, \theta^{(i)})$极大
  • 对固定的$\tilde P^{(i+1)}$，求$\theta^{(i+1)}$使 $F(\tilde P^{(t+1)}, \theta)$极大化

• 固定$\theta^{(i)}$

  $$\begin{align*} F(\tilde P^{(i+1)}, \theta^{(i)} & = E_{\tilde P^{(t+1)}} [log P(Y,Z|\theta)] + H(\tilde P^{(i+1)}) \\ & = \sum_Z log P(Y,Z|\theta) P(Z|Y,\theta^{(i)}) + H(\tilde P^{(i+1)}) \\ & = Q(\theta, \theta^{(i)}) + H(\tilde P^{(i+1)}) \end{align*}$$

• 则固定$\tilde P^{(i+1)}$求极大同EM算法M步

GEM算法

• 输入：观测数据，F函数
• 输出：模型参数

1. 初始化$\theta^{(0)}$，开始迭代

2. 第i+1次迭代：记$\theta^{(i)}$为参数$\theta$的估计值， $\tilde P^{(i)}$为函数$\tilde P$的估计，求 $\tilde P^{(t+1)}$使$\tilde P$极大化$F(\tilde P,\theta)$

3. 求$\theta^{(t+1)}$使$F(\tilde P^{(t+1)l}, \theta)$极大化

4. 重复2、3直到收敛

次优解代替最优解

• 输入：观测数据，Q函数
• 输出：模型参数

1. 初始化参数$\theta^{(0)}$，开始迭代

2. 第i+1次迭代，记$\theta^{(i)}$为参数$\theta$的估计值， 计算

   $$\begin{align*} Q(\theta, \theta^{(i)}) & = E_Z [ log P(Y,Z|\theta)|Y,\theta^{(i)}] \\ & = \sum_Z P(Z|Y, \theta^{(i)}) log P(Y,Z|\theta) \end{align*}$$

3. 求$\theta^{(i+1)}$使

   $$Q(\theta^{(i+1)}, \theta^{(i)}) > Q(\theta^{(i)}, \theta^{(i)})$$

4. 重复2、3直到收敛

• 有时候极大化$Q(\theta, \theta^{(i)})$非常困难，此算法 仅寻找使目标函数值上升方向

ADMM求次优解

• 输入：观测数据，Q函数
• 输出：函数模型

1. 初始化参数 $\theta^{(0)} = (\theta_1^{(0)},…,\theta_d^{(0)})$， 开始迭代

2. 第i次迭代，记 $\theta^{(i)} = (\theta_1^{(i)},…,\theta_d^{(i)})$， 为参数$\theta = (\theta_1,…,\theta_d)$的估计值，计算

   $$\begin{align*} Q(\theta, \theta^{(i)}) & = E_Z [ log P(Y,Z|\theta)|Y,\theta^{(i)}] \\ & = \sum_Z P(Z|Y, \theta^{(i)}) log P(Y,Z|\theta) \end{align*}$$

3. 进行d次条件极大化

   1. 在$\theta1^{(i)},…,\theta{j-1}^{(i)},\theta_{j+1}^{(i)},…,\theta_d^{(i)}$ 保持不变条件下 ，求使$Q(\theta, \theta^{(i)})$达到极大的 $\theta_j^{(i+1)}$

   2. j从1到d，进行d次条件极大化的，得到 $\theta^{(i+1)} = (\theta_1^{(i+1)},…,\theta_d^{(i+1)})$ 使得

      $$Q(\theta^{(i+1)}, \theta^{(i)}) > Q(\theta^{(i)}, \theta^{(i)})$$

4. 重复2、3直到收敛

K-NN

• 输入：p维实例特征向量

  • 将样本点视为p维特征空间的中点

• 输出：实例类别，可以取多类别

• 基本思想

  • 在已有数据中找到与$X_0$相似的若干个观测 $(X_1, X_2, …, X_k)$，称为$X_0$的近邻
  • 对近邻$(X_1, X_2, …, X_k)$的输出变量 $(y_1, y_2, …, y_k)$，计算诸如算术平均值 （加权平均值、中位数、众数），作为新观测$X_0$输出 变量取值$y_0$的预测值

• 特点

  • k近邻不具有显式学习过程、简单、直观
  • 不需要假设$y=f(X)$函数体形式，实际上是利用训练数据集 对特征空间进行划分

局部方法

k-NN是一种“局部”方法，仅适合特征空间维度较低的情况

• 给定k的情况下，在高维空间中，需要到更远的区域寻找近邻， 局部性逐渐丧失，近似误差变大

• 如：n个观测均匀分布在超立方体中，确定k后即确定$X_0$需要 寻找的近邻个数占总观测的比率r，即近邻覆盖的体积

  • 考虑$X_0$在原点，则近邻分布的小立方体边期望长度为

    $$Ed_p(r) = r^{1/p} \\ Ed_3(0.1) = 0.1^{1/3} = 0.46 \\ Ed_10(0.1)d = 0.1^{1/10} = 0.79 \\ Ed_10(0.01) = 0.1^{1/10} = 0.63 \\$$

  • 可以看出：减少近邻比例（数量）没有帮助，还会使得近似 误差变大，只能通过增大样本量解决

• 特征选择有必要

特征选择

• 变量本身考察

  • low variance filter：剔除标准差小于阈值数值型变量
  • missing values ratio：剔除缺失值大于阈值的变量
  • 剔除众数比率大于阈值的分类型变量

• 变量与输出变量相关性角度考察

  • high correlation filter

• 对预测误差影响角度考察

  • Wrapper方法：逐个选择使错误率、均方误差下降最快变量 ，可使用Forward Feature Elimination

k-NN模型

K-NN是使用模型：实际上对应于特征空间的划分

• 模型包括3个基本要素，据此划分特征空间，确定特征空间中 每个点所属类
  • k值选择
  • 距离度量：参见data_science/ref/functions
  • 分类决策规则

k值选择

k值选择对k-NN方法有重大影响

• 较小k值：相当于使用较小邻域中训练实例进行预测

  • 复杂模型，容易发生过拟合
  • approximation error较小：只有于输入实例近、相似的 训练实例才会对预测结果有影响
  • estimation error较大：预测结果对近邻实例点非常敏感

• 较大k值：相当于使用较大邻域中训练实例进行预测

  • 简单模型
  • 估计误差较小
  • 近似误差较大：同输如实例远、相似程度差的训练实例也会 对预测结果有影响

k=1

只使用一个近邻做预测

• 找到距离$X_0$最近的近邻$X_i$，用其取值作为预测值

• 模型简单、效果较理想

  • 尤其适合特征空间维度较低、类别边界不规则情况
  • 只根据单个近邻预测，预测结果受近邻差异影响极大，预测 波动（方差）大，稳健性低

• 预测错误的概率不高于普通贝叶斯方法的两倍

  $$\begin{align*} P_e & = (1-p(y=1|X=X_0))P(y=1|X=X_0) + (1-p(y=0|X=X_0))P(y=0|X=X_0) \\ & = 2P(y=1|X=X_0)(1-P(y=1|X=X_0)) \\ & \leq 2(1-P(y=1|X=X_0)) \\ \end{align*}$$

  • $P(y=1|X=X_0)$：普通贝叶斯方法做分类预测，预测结果 为1的概率
  • 1-NN方法犯错的概率就是$X_0$、$X_i$二者实际值不同的 概率？？？？

k=N

使用训练样本整体做预测

• 无论输入实例，预测结果完全相同

  • 对分类预测，预测结果为“众数”
  • 对回归预测，预测结果为“平均数”

• 模型过于简单、效果不好

  • 忽略训练实例中大量信息
  • “稳健性”极好：预测值基本不受近邻影响，无波动

决策规则

分类决策规则

Majority Voting Rule

多数表决规则：等价于经验风险最小化

• 分类损失函数为0-1损失函数，分类函数为 $f: \mathcal{R^n} \rightarrow {c_1, c_2, \cdots}$

• 误分类概率$P(Y \neq f(X)) = 1 - P(Y=f(X))$

• 给定实例$x \in \mathcal{X}$的误分率为

  $$\frac 1 k \sum_{x \in N_k(x)} I(y_i \neq c_j) = 1 - \frac 1 k \sum_{x \in N_k(x)} I(y_i = c_j)$$

  • $N_k(x)$：最近邻k个实例构成集合
  • $c_j$：涵盖$N_k(x)$区域的类别
  • $I$：指示函数

• 为使误分率（经验风险）最小，应选择众数

• 经验风险的构造中，前提是近邻被认为属于相同类别$c_j$，
• 当然这个假设是合理的，因为k-NN方法就是认为近邻类别相同， 并使用近邻信息预测
• $c_j$的选择、选择方法是模型选择的一部分，不同的$c_j$会 有不同的经验风险

数值决策规则

算法

• 实现k近邻法时，主要问题是对训练数据进行快速k近邻搜索， 尤在特征空间维数大、训练数据量大

• 考虑使用特殊的结构存储训练数据，减少计算距离次数，提高 k近邻搜索效率

linear scan

线性扫描：最简单的实现方法

• 需要计算输入实例与每个训练实例的距离，训练集较大时计算 非常耗时

kd树最近邻搜索

• 输入：已构造kd树
• 输出：x的最近邻

• 在kd树种找出包含目标点x的叶节点的

  • 从根节点出发，比较对应坐标，递归进行访问，直到叶节点 为止

  • 目标点在训练样本中不存在，必然能够访问到叶节点

• 以此叶节点为“当前最近点”

  • 目标点在此叶节点中点所在的区域内，且区域内只有该 叶节点中点

• 回溯，并在每个节点上检查

  • 如果当前节点保存实例点比当前最近点距离目标的更近， 更新该实例点为“当前最近点”

  • 检查该节点另一子区域是否可能具有更近距离的点

    • 即其是否同以目标点为圆心、当前最短距离为半径圆 相交
    • 只需要比较目标点和相应坐标轴距离和最短距离即可

  • 若二者相交，则将目标节点视为属于该子区域中点， 进行最近邻搜索，递归向下查找到相应叶节点，重新 开始回退

  • 若二者不相交，则继续回退

• 退回到根节点时，搜索结束，最后“当前最近点”即为最近邻点

• 这里涉及到回溯过程中，另一侧子域是否访问过问题，可以通过 标记、比较相应轴坐标等方式判断
• k>1的情况类似，不过检测时使用最远近邻，新近邻需要和所有 原近邻依次比较

加权k-NN

变量重要性

计算变量的加权距离，重要变量赋予较高权重

• 变量重要性：Backward Feature Elimination得到各变量 重要性排序

  $$FI_{(i)} = e_i + \frac {1} {p} \quad \\ w_{(i)} = \frac {FI_{(i)}} {\sum_{j=1}^p FI_{(j)}}$$

  • $e_i$：剔除变量i之后的均方误差（错误率）

• 加权距离：$dw(x,y)=\sqrt {\sum{i=1}^{p} w^{(i)}(x_i - y_i)^2}$

观测相似性

目标点的k个近邻对预测结果不应有“同等力度”的影响，与$X_0$越 相似的观测，预测时重要性（权重）越大

• 权重：用函数$K(d)$将距离d转换相似性，$K(d)$应该有特性

  • 非负：$K(d) \geqslant 0, d \in R^n$
  • 0处取极大：$max K(d) = K(0)$
  • 单调减函数，距离越远，相似性越小

  • 核函数符合上述特征
  • 且研究表明除均匀核外，其他核函数预测误差差异均不明显

步骤

• 依据函数距离函数$d(Z_{(i)}, Z_0)$找到$X_0$的k+1个近邻

  • 使用第k+1个近邻距离作为最大值，调整距离在0-1之间 $$D(Z_{(i)}, Z_0) = \frac {d(Z_{(i)}, Z_0)} {d(Z_{(k+1)}, Z_0)}, \quad i=1,2,...,k$$

• 依据函数$w_i=K(d)$确定k各近邻的权重

• 预测

  • 回归预测 $$\hat{y}_0 = \frac 1 k (\sum_{i=1}^k w_iy_i)$$
  • 分类预测：多数表决原则 $$\hat{y}_0 = max_r (\sum_{i=1}^k w_iI(y_i=r)) \\ P(\hat{y}_0=r|X_0)= \frac {\sum_{i=1}^k w_iI(y_i=r)} {\sum_{i=1}^k w_i}$$

Approximate Nearest Neighbor

相似最近邻

决策树概述

结构

• 决策树分析结论、展示方式类似一棵倒置的树

• 决策树由 node、directed edge 组成

  • internal node：内部节点，表示特征、属性
  • leaf node：叶子节点，表示一个类

• 对训练数据进行分类

  • 从根节点开始，对实例某特征进行测试，根据测试结果将实例分配到其子节点，对应该特征一个取值
  • 递归地对实例进行分配，直至到达叶子节点，将实例分到叶节点地类中

• 对新数据的预测

  • 从决策树的树根到树叶搜索，确定数所的叶子节点
  • 利用叶子节点中训练数据集预测
    • 分类型：众数
    • 数值型：均值

本质

决策树：本质上是从训练数据中归纳出一组分类规则

• 与训练数据不矛盾的分类规则（即能对训练数据正确分类）可能有多个、没有，需要找到矛盾较小、泛化能力较好的
• 决策树学习也是由训练数据集估计条件概率模型，需要寻找对训练数据有很好拟合、对未知数据有很好预测的模型

分类规则集合

• 决策树可以看作是 if-then 规则的集合：体现输入、输出变量逻辑关系

• 决策树根节点到叶节点每条路径构成一条规则
• 路径上内部节点的特征对应规则的条件，叶节点对应规则结论
• 决策树的路径或其对应的 if-then 规则集合 互斥且完备，即每个实例有且仅有一条路径覆盖

条件概率分布

• 决策树可以表示定义在特征空间、类空间上的条件概率分布

• 此条件概率分布定义在特征空间的一个划分（有限）上

  • 决策树中一条路径（叶节点）对应划分中一个单元
  • 每个单元定义的概率分布就构成一个条件概率分布

• 条件概率分布由 各单元的给定条件下，各类的条件概率分布组成

  • $P(Y|X)$：$X$ 为表示特征的随机变量（取值各个单元），$Y$ 表示类的随机变量
  • 各叶节点上的条件概率往往偏向于某类，决策树分类时将属于该节点实例分为该类

特点

• 优势

  • 能有效处理分类型输入变量
  • 能够实现非线性分割
  • 模型具有可读性，分类速度块

• 问题

  • 充分生长的决策有高方差，预测不稳定
  • 剪枝可以提高预测稳健性，但是预测精度可能会下降

决策树构建

• 从所有可能决策树中选取最优决策树是NP完全问题

  • 所以实际决策树算法通常采用 启发式 算法、贪心算法，近似求解最优化问题，得到 sub-optimal 决策树
  • 从包含所有数据的根节点开始，递归的选择 当前 最优特征、分割点对训练数据进行分割，使得各子数据集有当前最好分类
  • 此样本不断分组过程对应特征空间的划分、决策树的构建

• 原则：使节点/组内观测取值异质性下降最大，从而确定

  • 最佳划分特征
  • 特征的最佳分割点

异质性衡量：划分准则

• 信息增益
• 信息增益比：避免信息增益倾向于取值较多特征
  • 若样本类别严格服从分布，则信息增益和信息增益比选择应完全相同
  • 但由于偶然性、样本数量等原因，各特征取值的样本数量往往不完全符合分布
  • 由信息增益定义可看出，各特征取值样本数量较小时，数量变动影响更大，而特征取值较多更可能出现各取值对应样本数量较小
• GINI 指数

• 研究表明，不同决策树的划分准则对泛化性能影响有限，信息增益和 GINI 指数理念分析表明，其仅在 2% 情况下有所不同

特征变量处理

• 离散值处理

  • 全分类：各类别分别独立作为分支，构建节点
  • 切分二分：将类别分为的两组
  • 是否二分：某取值作为一个分支，其余作为另一分支

• 连续值处理

  • 二分法：选择阈值，按照阈值将连续值分为两部分
    • 精确阈值选取：检查所有可能阈值点，即所有不同取值点的中间点
    • 近似阈值选取
  • 近似分裂算法：选取一组阈值，将特征划分至不同桶内，类似分类值处理
    • 等频阈值：分位数
    • 等距阈值：linespace

缺失值处理

• 缺失值处理需要解决：异质性衡量指标计算、特征缺失样本划分问题

• 异质性衡量指标计算：使用特征未缺失样本权重对指标加权（以信息增益为例）

  $$\begin{align*} g(Y|X) &= \rho * g(\tilde Y | X) \\ & = \rho * (H(\tilde D) - \sum_v^V \tilde {r_v} H(\tilde {D^v})) \\ H(\tilde V) &= - \sum_k^K \tilde {p_k} log \tilde {p_k} \\ \rho &= \frac {\sum_{x \in \tilde D} w_x} {\sum_{x \in D} w_x}\\ \tilde {p_x} &= \frac {\sum_{x \in \tilde {D_k}} w_x} {\sum_{x \in \tilde D} w_x} \\ \tilde {r_v} &= \frac {\sum_{x \in \tilde {D^v}} w_x} {\sum_{x \in \tilde D} w_x} \end{align*}$$

  • $Y, X, w_x$：样本类别，特征，样本权重
  • $D, \tilde D, \tilde {D_k}, \tilde {D^v}$：样本全集，在特征 $X$ 上无缺失样本子集，属于 $k$ 类样本子集，在特征 $X$ 上取 $v$ 样本子集

• 特征缺失样本划分

  • 划分至所有节点，其权重设置为 $\tilde {r_v} * w_x$
    • $\tilde {r_v}$ 为节点 $v$ 的权重
    • 即将特征缺失样本节点权重比例划分至各节点

剪枝

树剪枝：在决策树的学习过程中，将已生成的树进行简化的过程

• 最小化 RSS、最大化置信目标下，会导致庞大的树

  • 对训练数据拟合好
  • 模型复杂度越高
  • 推广能力差
  • 比较难理解、解释

• 通过剪枝得到恰当的树，具备一定的预测精度、复杂程度恰当，代价（误差）和复杂度之间的权衡是必要的

• Pre-pruning 预剪枝：在决策树分裂过程中，不分裂不满足分裂条件的节点，限制决策树充分生长

  • 分裂条件
    • 最大深度
    • 叶节点数量
    • 样本量最小值
    • 异质性下降阈值
  • 预剪枝基于“贪心”的禁止划分，可能降低过拟合、减少时间开销，但也可能导致欠拟合

• Post-pruning 后剪枝：决策分裂完成后，根据一定规则剪去不具备普遍性的子树

  • 比预剪枝决策保留更多分支，欠拟合风险小、泛化性能好
  • 决策树生成局部模型，决策树剪枝学习整体模型

• 剪枝方法、程度对泛化性能影响显著，尤其是数据带有噪声

自底向上剪枝

• 自底向上剪去所有无法改善评价准则的非叶节点分支（转为叶节点）

  • 最简单后剪枝策略
  • 若已使用一定预剪策略，则该策略价值不大

• 特点

  • 须在生成完全决策树之后自底向上逐个考察非叶节点，时间开销大

Minimal Cost Complexity Pruning

$$\begin{align*} C_\alpha(T) & = C(T) + \alpha |T| \\ & = \sum_{t=1}^{|T|} N_t H_t(T) + \alpha |T| \\ & = -\sum_{t=1}^{|T|} \sum_{k=1}^K \frac {N_{t,k}} {N_t} log \frac {N_{t,k}} {N_t} + \alpha|T| \\ H_t(T) & = -\sum_k (\frac {N_{t,k}} {N_t} log \frac {N_{t,k}} {N_t}) \end{align*}$$

• $N_t$：树 $T$ 的第 $t$ 个叶子节点中样本点数量
• $N_{t,k}$：树 $T$ 的第 $t$ 个叶子节点第 $k$ 类样本点数量
• $H_t(T)$：树 $T$ 的第 $t$ 个叶子节点熵
• $C(T)$：模型对训练数据的预测误差
• $|T|$：用叶节点数量衡量的模型复杂度
• $\alpha \geq 0$：控制模型复杂度对模型总损失影响，每个叶节点带来的复杂度

• 极小化损失复杂度剪枝
  • 损失函数：正则化的极大似然函数
  • 此策略即在给定 $\alpha$ 的情况下，选择损失函数最小树

剪枝步骤

• 输入：生成算法产生的整个树 $T$，参数 $\alpha$
• 输出：修剪后的子数 $T_\alpha$

• 计算每个节点的经验熵
• 递归的从树的叶节点向上回缩
  • 若 $C\alpha(T{before}) \geq C\alpha(T{after})$，则剪枝
  • 不断回缩直到根节点，选取损失函数最小的子树 $T_\alpha$

• 算法只需要比较节点、节点子树之间损失函数之差即可，计算可以在局部进行
• 算法可以由动态规划算法实现

超参选择

• 对给定超参 $\alpha$，存在使损失函数 $C\alpha(T)$ 最小子树 $T\alpha$，且此最优子树唯一

  • $\alpha$ 偏大时，最优子树 $T_\alpha$ 偏小
  • $\alpha=0$ 时完整树最优，$\alpha \rightarrow \infty$ 时单节点树最优

• 对决策树种每个节点 $t$，通过以下策略生成 $g(t)$

  • $C_{\alpha}(T^t) = C(T^t) + \alpha|T^t|$：以 $t$ 为根节点的子树 $T^t$ 损失
  • $C_{\alpha}(t) = C(t) + \alpha$：对 $t$ 剪枝之后，仅包含单个节点 $t$ 的正则损失
  • 则 $\alpha=g(t) = \frac {C(t)-C(T^t)} {|T^t|-1}$ 时，单节点 $t$ 和子树 $T^t$ 损失相同

• 考虑以上 $g(t)$ 序列

  • $\alpha^t=g(t)$ 表示对 $T^{(0)}$ 中每个内部节点 $t$ 剪枝后，整体损失函数值减少程度
  • 可以证明，对以上 $\alpha > 0$ 序列排序，按 $0, \alpha^{(1)}, \cdots, \alpha^{(N)}$ 依次进行剪枝，对应最优子树序列 $T^{(0)}, T^{(1)},\cdots, T^{(N)}$ 嵌套
  • 通过交叉验证法在独立的验证数据集上对子树进行测试，选择最优决策树

完整剪枝+超参选择

• 输入：CART 算法生成决策树 $T^{(0)}$
• 输出：最优决策树 $T_\alpha$

• 自下而上地计算各内部节点 $t$ 对应 $C(T^t), |T^t|, g(t)$，对 $g(t)$ 升序排列得到 $\alpha^{(1)},\cdots,\alpha^{(N)}$

• 置：$k=1, \alpha=\alpha^{(k)}, T=T^{(0)}$

• 自上而下访问内部节点，若有 $g(t)=\alpha$，剪枝并计算新叶节点 $t$ 取值，得到对应最优树 $T^{(k)}$

  • 对于节点 $t$，其子树 $T^t$ 最大有效 $\alpha$ 也只是根节点对应 $g(t)$，更大没有价值
  • 自上而下剪枝避免无效剪枝

• 置：$k+=1, \alpha=\alpha^{(k)}, T=T^{(k)}$

• 若 $T$ 不是单节点树，则重复以上

• 采用交叉验证法在子树序列中选取最优子树 $T_\alpha$

• 也可从 $\alpha \leftarrow \infty$ 开始，逐渐减少，添枝 得到子树序列

决策树构建算法

• 以下是一些经典的决策树（算法），但实际实现中往往不会严格按其构建决策树

• 决策树算法常用递归描述、构建，完全决策树中止条件如下 （往往不会应用，而是以预剪枝条件作为中止条件）

  • 节点中样本属于同一类
  • 所有特征利用完毕
  • 无法找到满足划分阈值的特征、划分点

Iterative Dichotomiser 3

步骤

• 输入：训练数据集 $D$，特征集 $A$，阈值 $\epsilon$
• 输出：决策树 $T$

• 以下情况下 $T$ 为单节点树，以 $D$ 中实例数最大的类（众数） $C_k$ 作为该节点的类标记，返回 $T$

  • $D$ 中所有实例属于同一类 $C_k$
  • $A = \varnothing$

• 计算 $A$ 中各特征对 $D$ 的信息增益，选择信息增益最大的特征 $A_g$

  • 若 $A_g$ 的信息增益小于阈值 $\epsilon$，则置 $T$ 为单节点树，并将 $D$ 中实例数最大的类 $C_k$ 作为节点类标记，返回 $T$
  • 否则，对 $A_g$ 每个可能值 $a_m$，将 $D$ 分割为若干非空子集 $D_i$
    • 将 $D_i$ 中实例数最多的类作为标记，构建子节点
    • 对第 $i$ 个子节点，以 $D_i$ 为训练集，以 $A-{A_g}$ 为特征集，递归的构造子树 $T_i$ 并返回

特点

• 只允许分类型特征，且每个特征只会被用于划分一次

  • 每次所有取值都会被用于建立子节点
  • ID3 树是多叉树，各个节点的分叉个数取决于使用特征

• 只有树的生成，容易产生过拟合

• 以信息增益作为划分训练数据集的特征，倾向于选择取值较多的特征进行划分

  • 理论上若特征取值严格符合分布，取值数量多寡，对信息增益没有影响
  • 由于各种误差的存在，样本不可能严格符合总体分布，取值数量较多特征，各取值对应样本数量较少，误差会使得条件经验熵倾向于偏小 （假设误差随机，可以大概证明）

• 相当于用 极大似然法 进行概率模型的选择

C4.5

C4.5算法：ID3 算法继承者

• 与 ID3 差别

  • 用信息增益比代替信息增益用于选择特征，并且也被用于 前剪枝
    • 修正 ID3 倾向于使用取值较多的特征值分裂结点
  • 兼容数值型特征，使用二分法处理

• C4.5 算法还包含 C4.5Rules 将 C4.5 决策树转化为符号规则 - 各分支被重写为规则，并进行前件合并、删减

  • 最终规则集泛化性能可能优于原决策树

Classification and Regression Tree

CART 树：可用于分类和回归的二叉树

• 特点

  • 二叉树
  • 可以用于分类、回归
    • 分类：众数代表节点，GINI 指数选择特征
    • 回归：均值代表节点，MSE 选择特征
  • 能较好的处理缺失值

• CART 回归：平方误差最小化准则

  $$f(x) = \sum_{m=1} \hat c_m I(x \in R_m)$$

  • $R_m$：空间划分出的第 $m$ 单元
  • $\hat c_m=avg(y_i|x_i \in R_m)$：第 $m$ 个单元上所有实例输出变量均值，此时平方误差最小

• CART 分类：最小化基尼指数准则

  $$Gini(D, X=a) = \frac {|D_1|} {|D|} Gini(D_1) + \frac {|D_2|} {|D|} Gini(D_2)$$

  • $D_1 = {(x,y) \in D, X = a}$
  • $D_2 = D - D_1$
  • CART 树是二叉树，对分类变量只选择是否

CART回归步骤

• 输入：训练数据集 $D$
• 输出：回归树 $f(x)$

• 选择最优切变量 $j$、切分点 $s$，即求解

  $$\arg\min_{j,s} [\min_{c_1} \sum_{x_i \in R_1(j,s)} (y_i - c_1)^2 + \min_{c_2} \sum_{x_i \in R_2(j,s)} (y_i - c_2)^2 ]$$

  • $R_1(j,s) = {x|x^{(j)} \leq s}$
  • $R_2(j,s) = {x|x^{(j)} \geq s}$
  • $c_m = avg(y_i|x_i \in R_m)$：使得区域 $R_m$ 中平方误差最小，即其中样本点 $y_i$ 均值
  • 这里通过 遍历 得到

• 对两个子区域 $R_1(j,s), R_2(j,s)$ 继续重复以上步骤，直至满足停止条件

• 将输入空间划分为 $M$ 个区域 $R_1, R_2, \cdots, R_M$，生成决策 树

  $$f(x) = \sum_{m=1} \hat c_m I(x \in R_m)$$

CART 分类步骤

• 输入：训练数据集 $D$，停止计算条件
• 输出：CART 决策树

• 选择最优切变量 $j$、切分点 $s$

  $$Gini(D, X=a) = \frac {|D_1|} {|D|} Gini(D_1) + \frac {|D_2|} {|D|} Gini(D_2)$$
  • 对每个特征 $X$，对其所有取值 $a$ 计算条件基尼指数
  • 选择条件基尼指数最小的特征、对应的切分点，将训练数据依特征分配到两个子结点中

• 对生成两个子节点递归分裂，直至满足停止条件

• 生成 CART 决策树

Chi-squared Automatic Interaction Detector

CHAID 卡方自动交叉检验法：类似 ID3 算法，但利用卡方统计确定特征变量

• https://wenku.baidu.com/view/bdd3e60abed5b9f3f90f1cd6.html
• https://sefiks.com/2020/03/18/a-step-by-step-chaid-decision-tree-example/

特点

• 通过卡方统计量选择最显著特征变量作为划分特征

  • 分类目标变量：列联分析，卡方检验
  • 数值目标变量：回归分析，F检验

• 特征预处理

  • 分类型特征变量：根据卡方统计量显著性、组数量等考虑拆分、合并分组
  • 数值型特征变量：均分分组

• 是从相关性显著角度确定特征变量

  • 对决策树分支优化明显
  • 可用特征变量与目标相关性显著显著性作为停止分裂的标准

QUEST

Quick Unbiased Efficient Statical Tree：类似 CHAID 算法，但对选择特征、划分点依据不同，仅能处理分类目标变量

特点

• 类似 CHAID，选择最显著（p 值）的特征变量作为划分特征

  • 分类特征变量：连列分析，卡方检验
  • 数值特征变量：方差分析，F检验

• 划分点选择

  • 分类特征变量：映射为 one-hot 向量后，用判别分析求解划分向量，再映射回划分取值

• 目标变量多分类

  • 为每个类别计算特征均值，使用均值聚类将其简化为二分类
  • 只需要为节点内样本的、用待划分特征计算均值

• 运行速度快于 CART 树

• http://www.mclover.cn/blog/index.php/archives/60.html
• http://www3.stat.sinica.edu.tw/statistica/oldpdf/A7n41.pdf

Naive Bayes Classifier

朴素贝叶斯：在训练数据集上学习联合概率分布$P(X,Y)$，利用后验 分布作为结果

• 朴素：条件概率分布有条件独立性假设，即特征在类别确定 下条件独立

模型

• 输出Y的先验概率分布为

  $$P(Y = c_k), k = 1,2,\cdots,K$$

  • 先验概率是指输出变量，即待预测变量的先验概率分布， 反映其在无条件下的各取值可能性
  • 同理所有的条件概率中也是以输出变量取值作为条件

• 条件概率分布为

  $$P(X=x|Y=c_k) = P(X^{(1)}=x^{(1)},\cdots,X^{(D)}=x^{(D)}| Y=c_k)$$

  • $D$：用于分类特征数量

  其中有指数数量级的参数（每个参数的每个取值都需要参数）

• 因此对条件概率分布做条件独立性假设，即分类特征在类别 确定条件下是独立的

  $$\begin{align*} P(X=x|Y=c_k) & = P(X^{(1)}=x^{(1)},\cdots,X^{(D)}=x^{(D)} |Y=c_k) \\ & = \prod_{j=1}^D P(X^{(j)}=x^{(j)}|Y=c_k) \end{align*}$$
  • 条件独立性假设是比较强的假设，也是朴素的由来

  • 其使得朴素贝叶斯方法变得简单，但有时也会牺牲准确率

  • 以上即可得到联合概率分布$P(X,Y)$

  • 朴素贝叶斯学习到的联合概率分布$P(X,Y)$是数据生成的 机制，即其为生成模型

策略

策略：选择使得后验概率最大化的类$c_k$作为最终分类结果

$$P(Y=c_k|X=x) = \frac {P(Y=c_k, X=x)} {\sum_{i=1}^K P(Y=c_k, X=x)}$$

• $K$：输出类别数量

• 后验概率根计算根据贝叶斯定理计算

  $$\begin{align*} P(Y=c_k|X=x) & = \frac {P(X=x|Y=c_k)P(Y=c_k)} {\sum_{k=1}^K P(X=x|Y=c_k) P(Y=c_k)} \\ & = \frac {P(Y=c_k) \prod_{j=1}^D P(X^{(j)}|Y=c_k)} {\sum_{k=1}^K P(Y=c_k) \prod_{j=1}^D P(X^{(j)}|Y=c_k)} \end{align*}$$

• 考虑上式中分母对所有$c_k$取值均相等，则最终分类器为

  $$y = \arg\max_{c_k} P(Y=c_k) \prod_{j=1}^D P(X^{(j)} = x^{(j)}|Y=c_k)$$
  • 即分类时，对给定输入$x$，将其归类为后验概率最大的类

策略性质

后验概率最大化等价于0-1损失的经验风险最小化

• 经验风险为

  $$\begin{align*} R_{emp}(f) & = E[L(Y, f(X))] \\ & = E_x \sum_{k=1}^K L(y, c_k) P(c_k | X) \end{align*}$$

• 为使经验风险最小化，对训练集中每个$X=x$取极小化，对每个 个体$(x,y)$有

  $$\begin{align*} f(x) & = \arg\min_{c_k} \sum_{k=1}^K L(y, c_k) P(c_k|X=x) \\ & = \arg\min_{c_k} \sum_{k=1}^K P(y \neq c_k|X=x) \\ & = \arg\min_{c_k} (1-P(y=c_k|X=x)) \\ & = \arg\max_{c_k} P(y=c_k|X=x) \end{align*}$$

  即后验概率最大化

算法

极大似然估计

• 先验概率的极大似然估计为

  $$P(Y=c_k) = \frac {\sum_{i=1}^N I(y_i = c_k)} N, k=1,2,\cdots,K$$

• 条件概率的极大似然估计为

  $$P(X^{(j)}=a_{j,l}|Y=c_k) = \frac {\sum_{i=1}^N I(x_i^{(j)}=a_{j,l}, y_i=c_k)} {\sum_{i=1}^N I(y_i=c_k)} \\ j=1,2,\cdots,N;l=1,2,\cdots,S_j;k=1,2,\cdots,K$$

  • $a_{j,l}$；第j个特征的第l个可能取值
  • $S_j$：第j个特征的可能取值数量
  • $I$：特征函数，满足条件取1、否则取0

算法

• 输入：训练数据T
• 输出：朴素贝叶斯分类器

1. 依据以上公式计算先验概率、条件概率

2. 将先验概率、条件概率带入，得到朴素贝叶斯分类器

   $$y = \arg\max_{c_k} P(Y=c_k) \prod_{j=1}^D P(X^{(j)} = x^{(j)}|Y=c_k)$$

贝叶斯估计

• 条件概率贝叶斯估计

  $$P(X^{(j)}=a_{j,l}|Y=c_k) = \frac {\sum_{i=1}^N I(x_i^{(j)}=a_{j,l}, y_i=c_k) + \lambda} {\sum_{i=1}^N I(y_i=c_k) + S_j \lambda} \\ j=1,2,\cdots,N;l=1,2,\cdots,S_j;k=1,2,\cdots,K$$

  • $\lambda \geq 0$

  • $\lambda=0$时就是极大似然估计
  • 常取$\lambda=1$，此时称为Laplace Smoothing
  • 以上设计满足概率分布性质 $$\begin{align*} P_{\lambda}(X^{(j)}=a_{j,l}|Y=c_k) \geq 0 \\ \sum_{l=1}^{S_j} P_{\lambda}(X^{(j)}=a_{j,l}|Y=c_k) = 1 \end{align*}$$

• 先验概率贝叶斯估计

  $$P_{\lambda}(Y=c_k) = \frac {\sum_{i=1}^N I(y_i = c_i) + \lambda} {N + K\lambda}$$

• 极大似然估计可能出现所需估计概率值为0，影响后验概率计算 结果，贝叶斯估计能够避免这点

Semi-Naive Bayes Classifier

半朴素贝叶斯分类器：适当考虑部分特征之间的相互依赖信息

• Semi-Naive Bayes可以视为是利用规则对变量加权，以 此来体现相关变量的协同影响

  $$y = \arg\max_{c_k} P(Y=c_k) \prod_{j=1}^D \beta_j P(X^{(j)} = x^{(j)}|Y=c_k)$$
  • 特别的：权值为0/1即为变量筛选

One-Depentdent Estimator

独依赖估计：假设特征在类别之外最多依赖一个其他特征，这是半 朴素贝叶斯分类器中最常用的一种策略

$$P(X=x|Y=c_k) = \prod_{j=1}^D P(X^{(j)}=x^{(j)} | Y=c_k, pa_j)$$

• $pa_j$：特征$X^{(j)}$依赖的父特征

• 若父特征已知，同样可以使用条件概率计算 $P(X^{(j)}=x^{(j)} | Y=c_k, pa_j)$

  $$P(X^{(j)}=x^{(j)} | Y=c_k, pa_j) = \frac {P(X^{(j)}=x^{(j)}, Y=c_k, pa_j)} {P(Y=c_k, pa_j)}$$

• ODE形式半朴素贝叶斯分类器相应的策略为

  $$y = \arg\max_{c_k} P(Y=c_k) \prod_{j=1}^D P(X^{(j)} = x^{(j)}|Y=c_k, pa_j)$$

• 根据确定各特征父特征的不同做法，可以分为不同类型的独依赖 分类器

  • Super-Parent ODE：假设所有特征都依赖同一父特征
  • Averaged ODE：类似随机森林方法，尝试将每个属性作为 超父特征构建SPODE
  • Tree Augmented Naive Bayes：基于最大带权生成树发展

SPODE

SPODE：每个特征只与其他唯一一个特征有依赖关系

$$y = \arg\max_{c_k} P(Y=c_k, pa) \prod_{j=1}^D P(X^{(j)} = x^{(j)}|Y=c_k, pa)$$

• $pa$：所有特征共有的依赖父特征

AODE

AODE：以所有特征依次作为超父特征构建SPODE，以具有足够训练 数据支撑的SPODE集群起来作为最终结果

$$y = \arg\max_{c_k} (\sum_{i=1}^D P(Y=c_k, X^{(i)}) \prod_{j=1}^D P(X^{(j)} = x^{(j)}|Y=c_k, X^{(i)}))$$

• 这里只选取训练数据足够，即取特征$X^{(i)}$某个取值的样本 数量大于某阈值的SPODE加入结果

TAN

TAN步骤

• 计算任意特征之间的互信息

  $$g(X^{(i)}, X^{(j)}| Y) = \sum P(X^{(i)}, X^{(j)} | Y=c_k) log \frac {P(X^{(i)}, X^{(j)} | Y=c_k)} {P(X^{(i)} | Y=c_k) P(X^{(j)} | Y=c_k)}$$

• 以特征为节点构建完全图，节点边权重设为相应互信息

• 构建此完全图的最大带权生成树

  • 挑选根变量
  • 将边设置为有向

• 加入预测节点$Y$，增加从$Y$到每个属性的有向边

特点

• 条件互信息$g(X^{(i)}, X^{(j)}| Y)$刻画了特征在已知类别 情况下的相关性

• 通过最大生成树算法，TAN仅保留了强相关属性之间的依赖性

子集回归

• 特征子集选择独立于回归模型拟合，属于封装器特征选择

最优子集

• 特点
  • 可以得到稀疏的模型
  • 但搜索空间离散，可变性大，稳定性差

Forward Feature Elimination

前向变量选择

步骤

• 初始变量集合$S_0 = \varnothing$
• 选择具有某种最优特性的变量进入变量集合，得到$S_1$
• 第j步时，从剩余变量中选择最优变量进入集合，得到$S_{j+1}$
• 若满足终止条件，则结束，否则重复上步添加变量
  • j达到上限
  • 添加剩余变量均无法满足要求

Backward Feature Elimination

后向变量选择

步骤

• 初始变量集合$S_0$包含全部变量
• 从变量集合中剔除具有某种最差特性变量，得到$S_1$
• 第j步时，从剩余变量中剔除最差变量，得到$S_{j+1}$
• 若满足终止条件，则结束，否则重复上步添加变量
  • j达到上限
  • 剔除剩余变量均无法满足要求

范数正则化约束

• 回归过程中自动选择特征，属于集成特征选择

Ridge Regression

$$\min_{\beta \in R^n} \left\{ ||y - X\beta||_2^2 + \lambda ||\beta||_2^2 \right\}$$

• 在L2范数约束下最小化残差平方
• 作为连续收缩方法
  • 通过bias-variance trade-off，岭回归较普通最小二乘 预测表现更好
  • 倾向于保留所有特征，无法产生疏系数模型

LASSO

$$\min_{\beta \in R^n} \left\{ ||y - X\beta||_2^2 + \lambda||\beta||_1 \right\}$$

能够选择部分特征，产生疏系数模型

• p > n时，即使所有特征都有用，LASSO也只能从中挑选n个
• 如果存在相关性非常高的特征，LASSO倾向于只从该组中选择 一个特征，而且是随便挑选的
  • 极端条件下，两个完全相同的特征函数，严格凸的罚函数 （如Ridge）可以保证最优解在两个特征的系数相等，而 LASSO的最优解甚至不唯一

Elastic Net

Naive Elastic Net

$$\begin{align*} & \min_{\beta \in R^n} \left\{ ||y - X\beta||_2^2 + \lambda_1||\beta||_1 + \lambda_2||\beta||_2^2 \right\} \\ \Rightarrow & \min_{\beta^* \in R^p} \left\{ ||y - X^*\beta^*||_2^2 + \lambda^*||\beta^*||_1 \right\} \\ where: & y^* = \begin{pmatrix} y \\ \vec 0_p \end{pmatrix} \\ & X^* = \frac 1 {\sqrt {1+\lambda^2}} \begin{pmatrix} X \\ \sqrt {\lambda_2} I_p \end{pmatrix} \\ & \beta^* = \sqrt {1+\lambda_2} \beta \\ & \lambda^* = \frac {\lambda_1} {1+\lambda_2} \\ \end{align*}$$

• 弹性网在Lasso的基础上添加系数的二阶范数

  • 能同时做变量选择和连续收缩
  • 并且可以选择一组变量

• 传统的估计方法通过二阶段估计找到参数

  • 首先设置ridge系数$\lambda_2$求出待估参数$\beta$， 然后做lasso的收缩
  • 这种方法有两次收缩，会导致估计偏差过大，估计不准

• 弹性网可以变换为LASSO，因而lasso的求解方法都可以用于 elastic net

elastic_net

Least Angle Regression

• 线性回归即找的一组系数能够用自变量的线性组合表示 因变量

Forward Selection/Forward Stepwise Regression

• 从所有给定predictors中选择和y相关系数绝对值最大的变量 $x_{j1}$，做线性回归

  • 对于标准化后的变量，相关系数即为变量之间的内积
  • 变量之间相关性越大，变量的之间的夹角越小，单个变量 能解释得效果越好
  • 此时残差同解释变量正交

• 将上一步剩余的残差作为reponse，将剩余变量投影到残差上 重复选择步骤

  • k步之后即可选出一组变量，然后用于建立普通线性模型

• 前向选择算法非常贪心，可能会漏掉一些有效的解释变量，只是 因为同之前选出向量相关

Forward Stagewise

前向选择的catious版本

• 和前向选择一样选择和y夹角最小的变量，但是每次只更新较小 步长，每次更新完确认和y夹角最小的变量，使用新变量进行 更新

  • 同一个变量可能会被多次更新，即系数会逐渐增加
  • 每次更新一小步，避免了前向选择的可能会忽略关键变量

• 输入：实例的特征向量
• 输出：实例类别+1、-1

感知机模型

感知机：线性二分类模型（判别模型）

$$f(x) = sign(wx + b)$$

• $x \in \chi \subseteq R^n$：输入空间
• $y \in \gamma \subseteq R^n$：输出空间
• $w \in R^n, b \in R$：weight vector、bias
• 也常有$\hat w = (w^T, b^T)^T, \hat x = (x^T + 1)^T$， 则有$\hat w \hat x = wx + b$

• 感知机模型的假设空间是定义在特征空间的所有 linear classification model/linear classifier，即函数 集合${f|f(x)=wx+b}$

• 线性方程$wx+b=0$：对应特征空间$R^n$中一个hyperplane

  • $w$：超平面法向量
  • $b$：超平面截距

  • 超平面将特征空间划分为两个部分，其中分别被分为正、负 两类

  • 也被称为separating hyperplane

Linearly Separable Data Set

• 对数据集$T={(x_1,y_1),\cdots,(x_N,y_N)}$，若存在超平面 $S: wx + b=0$能够将正、负实例点，完全正确划分到超平面 两侧，即 $$\begin{align*} wx_i + b > 0, & \forall y_i > 0 \\ wx_i + b < 0, & \forall y_i < 0 \end{align*}$$ 则称数据集T为线性可分数据集

感知机学习策略

感知机学习策略：定义适当损失函数，并将经验风险极小化，确定 参数$w, b$

0-1损失

经验风险：误分率（误分点总数）

• 不是参数$w, b$的连续可导函数，不易优化

绝对值损失

经验风险：误分类点到超平面距离

• 对误分类数据$(x_i, y_i)$，有$-y_i(wx_i + b) > 0$

• 则误分类点$(x_i, y_i)$到超平面S距离

  $$\begin{align*} d_i & = \frac 1 {\|w\|} |wx_i + b| \\ & =-\frac 1 {\|w\|} y_i(wx_i + b) \end{align*}$$

• 则感知机损失函数可定义为 $L(w,b) = -\sum_{x_i \in M} y_i(wx_i + b)$

  • $M$：误分类点集合
  • 损失函数是$w, b$的连续可导函数：使用$y_i$替代绝对值

• 损失函数$L(w,b)$梯度有

  $$\begin{align*} \bigtriangledown_wL(w, b) & = -\sum_{x_i \in M} y_ix_i \\ \bigtriangledown_bL(w, b) & = -\sum_{x_i \in M} y_i \end{align*}$$

学习算法

Stochastic Gradient Descent

随机梯度下降法

• 输入：数据集$T$、学习率$\eta, 0 \leq \eta \leq 1$
• 输出：$w,b$、感知模型$f(x)=sgn(wx+b)$

1. 选取初值$w_0, b_0$

2. 随机选取一个误分类点$(x_i, y_i)$，即$y_i(wx_i+b) \leq 0$ ，对$w, b$进行更新

   $$\begin{align*} w^{(n+1)} & \leftarrow w^{(n)} + \eta y_ix_i \\ b^{(n+1)} & \leftarrow b^{(n)} + \eta y_i \end{align*}$$

   • $0 < \eta \leq 1$：learning rate，学习率，步长

3. 转2，直至训练集中无误分类点

• 不同初值、随机取点顺序可能得到不同的解
• 训练数据线性可分时，算法迭代是收敛的
• 训练数据不线性可分时，学习算法不收敛，迭代结果发生震荡
• 直观解释：当实例点被误分类，应该调整$w, b$值，使得分离 超平面向误分类点方向移动，减少误分类点与超平面距离， 直至被正确分类

学习算法对偶形式

todo

算法收敛性

为方便做如下记号

• $\hat w = (w^T, b^T)^T, \hat w \in R^{n+1}$
• $\hat x = (x^T, 1)^T, \hat x \in R^{n+1}$

此时，感知模型可以表示为

$$xw + b = \hat w \hat x = 0$$

• 数据集$T={(x_1, y_1), (x_2, y_2),…}$线性可分，其中： $x_i \in \mathcal{X = R^n}$， $y_i \in \mathcal{Y = {-1, +1}}$，则

• 存在满足条件$|\hat w{opt}|=1$超平面 $\hat w{opt} \hat x = 0$将训练数据完全正确分开，且 $\exists \gamma > 0, yi(\hat w{opt} x_i) \geq \gamma$

• 令$R = \arg\max_{1\leq i \leq N} |\hat x_i|$，则 随机梯度感知机误分类次数$k \leq (\frac R \gamma)^2$

超平面存在性

• 训练集线性可分，存在超平面将训练数据集完全正确分开，可以 取超平面为$\hat w_{opt} \hat x = 0$

• 令$|\hat w_{opt}| = 1$，有

  $$\forall i, y_i(\hat w_{opt} \hat x_i) > 0$$

  可取

  $$\gamma = \min_i \{ y_i (\hat w_{opt} \hat x) \}$$

  满足条件

感知机算法收敛性

• 给定学习率$\eta$，随机梯度下降法第k步更新为 $\hat wk = \hat w{k-1} + \eta y_i \hat x_i$

• 可以证明

  • $\hat wk \hat w{opt} \geq k\eta\gamma$

    $$\begin{align*} \hat w_k \hat w_{opt} & = \hat w_{k-1} \hat w_{opt} + \eta y_i \hat w_{opt} \hat x_i \\ & \geq \hat w_{k-1} \hat w_{opt} + \eta\gamma \\ & \geq k\eta\gamma \end{align*}$$

  • $|\hat w_k|^2 \leq k \eta^2 R^2$

    $$\begin{align*} \|\hat w_k\|^2 & = \|\hat w_{k-1} + \eta y_i x_i \|^2 \\ & = \|\hat w_{k-1}\|^2 + 2\eta y_i \hat w_{k-1} \hat x_i + \eta^2 \|\hat x_i\|^2 \\ & \leq \|w_{k-1}\|^2 + \eta^2 \|\hat x_i\|^2 \\ & \leq \|w_{k-1}\|^2 + \eta^2 R^2 \\ & \leq k\eta^2 R^2 \end{align*}$$

• 则有

  $$\begin{align*} k \eta \gamma & \leq \hat w_k \hat w_{opt} \leq \|\hat w\| \|\hat w_{opt}\| = \|\hat w\| \leq \sqrt k \eta R \\ k^2 \gamma^2 & \leq k R^2 \end{align*}$$

• 直观理解就是超平面最大移动次数不大于最大移动距离 除以最小移动步长

  • $\eta \gamma^2$：超平面法向量最小增加量（移动步长）
  • $\eta R^2$：超平面法向最大增加量（移动距离）
  • 但是超平面不可能将所有点都归为同一侧

• 误分类次数有上界，经过有限次搜索可以找到将训练数据完全 正确分开的分离超平面，即训练数据集线性可分时，算法的迭代 形式是收敛的