机器学习导论

本导图内容涵盖了机器学习的基本概念、机器学习中基础的分类和回归算法，聚类算法和推荐算法。每种算法均包含算法流程和公式推导介绍。

机器学习导论

• 基本概念
  • 机器学习
    • 通过计算手段，利用经验改善系统自身性能
  • 三要素
    • data
    • algorithm
      • 产生model
    • model
      • result from data
  • 相关学科
    • 模式识别
      • 机器学习是方法，模式识别是目的
    • 数据挖掘
      • 机器学习+数据库
  • 分类
    • 监督学习
      • 分类
      • 回归
    • 无监督学习
      • 聚类
  • 基本术语
    • 假设hypothesis
      • 学习到的模型，数据的潜在规律
    • 真相ground-truth
      • 真实的潜在规律
    • 数据集data set
      • 样本
      • 属性或特征
      • 属性值
      • 样本空间
        • 属性张成的空间
      • 特征向量
    • 学习learning\训练training
    • 测试testing
    • 泛化能力generalization
      • 模型适用于
  • 评估方法
    • 有专门的测试集
    • 仅有一个数据集
      • 留出法
        • 直接分成两个互斥的集合
        • 两个集合数据分布一致
        • 进行若干次随机划分
        • 大小比例一般是2:1到4:1
      • 交叉验证法
        • 把数据集划分为k个
        • 取k-1个求并集作为训练集
        • 进行k次训练和测试，取均值
      • 自助法
        • 数据集较小，有m个样本
        • 有放回取球，形成m个样本的训练集
        • 没取到的球作为测试集
  • 数据清洗
    • 数据质量问题
      • 完整性
      • 唯一性
      • 权威性
      • 合法性
      • 一致性
    • 让数据更适合挖掘
      • 降维
      • 高维映射
      • 去除冗余
• 分类
  • 监督学习
    • 准备训练数据
    • 抽取训练数据特征，形成特征向量
    • 将特征向量和标记送入学习算法，得到预测模型
    • 对测试数据采用同样的特征抽取，得到特征向量
    • 用预测模型预测测试数据特征向量
  • 分类
    • 概念
      • 用已标注数据生成分类器
      • 用分类器判断未标注数据类别
    • 包括
      • 二分类
      • 多分类
      • 多标签分类
  • NN
    • NEAREST-NEIGHBOR
    • 1NN
      • 计算x与所有训练数据间的相似度
      • x与相似度最高的对象属于同一类别
    • KNN
      • 不必训练
      • 多个类别也挺简单
      • 类别之间相互影响
      • 数据集无穷大，KNN效果最佳
  • 决策树
    • 递归生成返回情况
      • 当前结点所有样本同类，无需划分
      • 所有属性都用过了或者当前结点的样本属性都一样
        • 当前结点作为叶结点，类别为样本最多的那个类
      • 当前结点莫得样本
        • 当前结点作为叶结点，类别为父结点样本最多的那个类
    • 如何选择划分属性
      • ID3
        • 信息增益高的属性更靠近根结点的树优先
        • 较短的树优先
        • bug：会选id（倾向于取值多的属性）
      • C4.5
        • 先找出信息增益高于平均水平的属性
        • 再从中选择信息增益率高的
        • 可能过度惩罚
      • CART
        • 选择使得划分后基尼值最小的属性
    • 选择依据
      • 熵
        • • Ent(D)：样本集合D的熵
          • p(k)：第k类样本所占的比例
      • 信息增益
        • • Gain(D,a)：样本集合D按照a属性进行划分的信息增益
          • Ent(D)：样本集合D的熵
          • 绝对值表示求样本集合的样本数
          • 我理解是父结点的熵减去所有子结点的加权平均熵
      • 信息增益率
        • • IV(a)：惩罚参数，属性取值越多，惩罚越猛
      • 基尼值
        • • Gini(D)：数据集D的基尼值
          • ：数据集中样本属于k类的概率
          • 整体表示从数据集D中随机抽取两个样本，它俩类别标记不一致的概率
      • 基尼指数
        • • Gini_index(D,a)：属性a的基尼指数
          • 就是按照属性a划分得到的子结点的基尼值的加权平均
    • 剪枝处理
      • 目的
        • 避免过拟合
      • 方式
        • 预剪枝
          • 划分前估计这个划分是否有利于泛化，若不能，直接标为叶结点
            • 欠拟合风险
        • 后剪枝
          • 决策树生成结束后，自底向上考察，将子树替换为叶子是否有利于泛化
            • 时间开销大
  • 朴素贝叶斯
    • 公式
      • • P(c)：先验概率，样本空间中各类样本所占比例
        • P(x|c)：样本x相对于类标记c的类条件概率，注意“未观测到”和“概率为零”
        • P(x)：用于归一化的证据因子
    • 属性条件独立性假设
    • 表达式
    • 模型训练
      • 离散属性
      • 连续属性
        • 假设正态
    • 修正
      • 拉普拉斯修正（解决零概率问题）
        • N表示训练集可能的类别数 Ni表示第i个属性可能的取值数
      • log space（解决浮点溢出问题）
        • 对概率取log值并进行累加的效果，比概率值的累乘要好
  • 支持向量机
    • 线性分类函数
      • f(x)=wTx+b
        • x：数据特征们，是个列向量
        • y：类别
        • w：法向量，决定超平面方向
        • b：位移项，决定超平面与原点距离
    • “间隔最大”推导过程
    • 问题转化
      • 寻找合适的w和b，使得M最大
      • 得到优化问题
    • 凸二次优化问题
      • 现成的优化计算包
      • 使用拉格朗日对偶性求解对偶问题
    • 拉格朗日乘子法处理过程
    • 分类过程
      • 对于新点x的预测，只需要计算它与训练数据点的内积即可
    • 核函数
      • 解决训练样本线性不可分的问题
      • 将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分
      • 如果原始空间是有限维，那么一定存在一个高维特征空间使样本可分
      • 常用核函数
        • 线性核
        • 多项式核
        • 高斯核
  • 集成学习
    • 集成方式
      • 同质集成
        • 个体学习器类型相同
      • 异质集成
        • 个体学习器算法不同
    • 分类
      • 个体学习器强依赖，串行生成
        • boosting
      • 个体学习器无强依赖，可同时生成
        • bagging
        • 随机森林
    • boosting
      • 工作机制
        • 先从初始训练集训练出一个基学习器
        • 再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续受到更多关注，然后基于调整后的样本分布来训练下一个基学习器
        • 如此重复进行，直至基学习器数目达到事前指定的值T，最终将这T个基学习器进行加权结合
      • 算法描述
      • 代表算法
        • adaboost
      • 两种方法
        • 重赋权法：在训练过程的每一轮中，根据样本分布为每个训练样本重新赋予一个权重
        • 重采样法：对无法接受带权样本的基学习算法，在每一轮学习中，根据样本分布对训练集重新进行采样，再用重采样的样本集对基学习器进行训练
    • bagging
      • 给定一个训练数据集，对训练样本进行采样，产生出若干不同的子集，再从每个数据子集中训练出一个基学习器
      • 基于自助采样法
      • 整合学习器
        • 分类：简单投票
        • 回归：简单平均
      • 算法描述
    • 随机森林
      • 在以决策树为基学习器构建Bagging集成的基础上，进一步在决策树的训练过程中引入了随机属性
      • 对基决策树的每个结点，先从该结点的属性集合中随机选择一个包含k个属性的子集，然后再从这个子集中选择一个最优属性用于划分
        • k控制了随机性的引入程度
        • 若k=d，基决策树的构建与传统决策树相同
        • 若k=1，随机选择一个属性用于划分
        • 推荐值：k=log2d
      • 每棵树的生成过程
        • 对于每棵树而言，随机且有放回地从训练集中抽取m个训练样本，作为该树的训练集；
        • 如果每个样本的特征维度为d，指定一个常数k<<d，随机地从d个特征中选取k个特征子集，每次树进行分裂时，从这k个特征中选择最优的；
        • 每棵树都尽最大程度的生长，并且没有剪枝过程。
      • 分类效果
        • 随机森林中任意两棵树的相关性
          • 相关性越大，错误率越大
        • 随机森林中每棵树的分类能力
          • 每棵树的分类能力越强，整个森林的错误率越低
        • 减小特征选择个数k，树的相关性和分类能力也会相应的降低；增大k，两者也会随之增大
  • 表现测量
    • 分类任务
      • 错误率
        • 分错样本占样本总数的比例
      • 精度
        • 分对样本占样本总数的比率
      • 分类结果混淆矩阵
      • 查全率recall
      • 查准率precision
      • FI度量
        • • ß=1，F1
          • ß>1，偏重Recall
          • ß<1，偏重Precision
      • P-R曲线
        • 根据学习器的预测结果按正例可能性大小对样例进行排序，并逐个把样本作为正例进行预测，则可以得到查准率-查全率曲线
        • 平衡点是曲线上“查准率=查全率”时的取值，可用来用于度量P-R曲线有交叉的分类器性能高低
      • ROC
        • 根据学习器的预测结果对样例排序，并逐个作为正例进行预测，以“假正例率”为横轴，“真正例率”为纵轴可得到ROC曲线，全称“受试者工作特征”
        • 给定m+个正例和m-个负例，根据学习器预测结果对样例进行排序，当前标记点坐标为(x,y) ,当前若为真正例，则对应标记点的坐标为(x,1/(y+ m+) );当前若为假正例，则对应标记点的坐标为(1/(x+ m- ),y) ,然后用线段连接相邻点.
      • AUC
        • 若某个学习器的ROC曲线被另一个学习器的曲线“包住”，则后者性能优于前者；否则如果曲线交叉，可以根据ROC曲线下面积大小进行比较，即AUC值.
        • 假设ROC曲线由{(x1,y1),(x2,y2),…,(xm,ym)}的点按序连接而形成(x1=0,xm=1) ，则：AUC可估算为：
• 回归
  • 线性回归
    • 最小二乘法（最小化均方误差）
      • 均方误差最小化
      • 求解
        • • E是凸函数，求两个偏导
  • 多元线性回归
    • 数据集
    • 目标
    • w和b的向量形式
      • 数据集可表示为
    • 最小二乘法
    • 问题：特征比样本多
      • XTX是奇异矩阵无法求逆
      • 办法
        • 减少特征数量
          • 手动筛选
          • 模型选择
        • 正则化
          • 保留所有特征，缩小参数量级
    • 正则化项
      • 也叫惩罚项、约束项
      • 作用
        • 使参数变化范围足够小，让模型由多解变为倾向于一个解
        • 参数的值越小，通常对应于越光滑的函数，也就是越简单的函数，不容易过拟合
      • 一般形式
        • • 第一部分：通过训练，使假设更好地拟合训练数据
          • 第二部分：保持参数值较小
          • 正则化参数
            • 控制在两个不同目标中的平衡关系
      • 范数
        • L0范数
          • 向量中非0的元素的个数
          • 用L0范数作参数矩阵w的正则化
          • 目标：w的大部分元素都是0，即w是稀疏的
          • NP-hard
        • L1范数
          • L1范数是L0范数的最优凸近似，且更易求解
          • 稀疏规则算子(Lasso regularization)
          • 向量中各个元素绝对值之和
        • L2范数
          • 模，向量各元素的平方和然后求平方根
          • L2范数的规则项||W||2最小，可以使得W的每个元素都很小，不等于0但都接近于0
          • 不但可以防止过拟合，还可以让优化求解变得稳定和快速
  • 其他回归模型
    • 岭回归
    • LASSO回归
    • ElasticNet回归
  • 二分类任务
    • 输出标记与预测值
    • 寻找单调可微函数将分类标记与线性回归模型输出联系起来
    • 最理想的函数——单位阶跃函数
      • 预测值大于零就判为正例，小于零就判为反例，预测值为临界值零则可任意判别
      • 不连续
    • 替代函数——logistic函数，sigmoid函数
      • 单调可微、任意阶可导
    • LR求解
      • 将y视为类后验概率估计
      • 通过极大似然法估计参数
        • 对数似然
        • 令每个样本属于其真实标记的概率越大越好
    • MLE
      • 参数估计
        • 目标：找出一组参数，使得模型产生出观测数据的概率最大
        • 用似然函数取到最大值时的参数值作为估计值
        • 多数情况下我们是根据已知条件来推算结果，而最大似然估计是已经知道了结果，然后寻求使该结果出现的可能性最大的条件，以此作为估计值。
      • 求解步骤
        • 写出似然函数；
        • 对似然函数取对数，并整理；
        • 求导数，令导数为0，得到似然方程；
        • 解似然方程，得到的参数即为所求。
      • 求解过程
    • 梯度下降
      • 常用的一阶优化方法
      • 求解无约束优化问题
    • 随机梯度上升或下降
    • 牛顿法
• 聚类
  • 目标
    • 将数据集中的样本划分为若干个通常不相交的子集
  • 形式化描述
  • 性能度量
    • 有效性指标
      • 簇内相似度高且簇间相似度低
    • 外部指标
      • 与参考模型比较
      • jacard系数
      • FM指数
      • Rank指数
      • 上述结果值均在[0,1]区间，值越大越好
    • 内部指标
      • 不利用任何参考模型
      • 簇C内样本件平均距离
      • 簇C内样本件最远距离
      • 簇Ci与Cj最近样本间距离
      • 簇Ci与Cj中心点间距离
      • DB指数
        • • 越小越好
      • Dunn指数
        • • 越大越好
  • 原型聚类
    • 概念
      • 假设聚类结构能通过一组原型刻画
      • “原型”指样本空间中具有代表性的点
      • 算法先对原型进行初始化，然后对原型进行迭代更新求解
    • k均值聚类
      • 给定样本集D={x1,x2,…,xm}，k-means算法针对聚类所得簇划分C={C1,C2,…,Ck}最小化平方误差
      • 最小化E是一个NP难问题
      • 贪心策略，通过迭代优化来近似求解
      • 算法描述
      • seed choice
        • 随机的种子选取会导致聚类结果间存在差异
        • 某些种子会导致收敛速度很慢，或者是收敛至次优(sub-optimal)的结果
        • 采用启发式的方法选择较好的种子 (e.g., doc least similar to any existing mean)
        • 尝试多种不同的初始种子选择
        • 先采用一种方法进行聚类，基于其结果再对K-means进行初始化
    • 高斯混合聚类
      • 高斯分布
      • 高斯混合分布
        • 该分布共由k个混合成分组成，每个混合成分对应一个高斯分布
        • μi与∑i是第i个高斯混合成分的参数，αi>0为相应的“混合系数”，且
      • EM算法求解
      • EM算法为什么work
      • 高斯混合聚类算法
  • 密度聚类
    • 特点
      • 假设聚类结构能通过样本分布的紧密程度确定
      • 从样本密度的角度来考察样本之间的可连接性，并基于可连接样本不断扩展聚类簇以获得最终的聚类结果
    • 代表算法：DBSCAN
      • 基于一组“邻域”参数(ε,MinPts)刻画样本分布的紧密程度
      • 基本概念
        • 对簇的定义：
          • 由密度可达关系导出的最大的密度相连样本集合
        • 对簇的形式化描述
          • 给定邻域参数(ε,MinPts)，簇是满足以下性质的非空样本子集：
          • 连接性：xi ∈C，xj ∈C=>xi与xj密度相连
          • 最大性：xi ∈C，xj由xi密度可达=> xj ∈C
          • 实际上，若x为核心对象，由x密度可达的所有样本组成的集合记为={^′∈ | ^′ 由密度可达}，则为满足连接性与最大性的簇。
      • 算法
  • 层次聚类
    • 试图在不同层次对数据集进行划分，从而形成树形的聚类结构
      • 自底向上(更容易)，自顶向下
    • AGNES：自底向上聚合策略的层次聚类算法
      • 先将数据集中的每个样本看作一个初始聚类簇，然后在算法运行的每一步中找出距离最近的两个聚类簇进行合并，该过程不断重复，直到达到预设的聚类簇个数
      • 给定聚类簇Ci与Cj，计算簇间的距离
        • 最小距离
        • 最大距离
        • 平均距离
      • 算法
• 推荐
  • 基于内容
    • 基本思想
      • 如果用户x对某物品评分很高，那就为其推荐相似的物品
    • 物品属性
      • 物品特征集合
    • 用户属性
      • 描述形式
        • 已评价物品属性集合的平均
        • 用户自己对各物品评价与平均分的差距
      • 如何推荐
        • 计算用户属性和物品属性的余弦相似度
  • 协同过滤
    • 基于用户的协同过滤
      • 方法
        • 找到和目标用户兴趣相似的用户集合
        • 找到大家喜欢的，目标用户没听说过的东西推荐给目标用户
      • 关键问题
        • 找相似用户
      • 用户相似度计算
        • Jaccard相似度
          • 交集/并集
          • 忽略了评分信息
        • 余弦相似度
          • 将缺失数据视为负反馈
        • Pearson相关系数
    • 基于物品的协同过滤
      • 假设
        • 喜欢A的用户大多喜欢B，可推断AB相似
      • 主要思想
        • 不用物品本身属性计算相似度，根据用户行为计算物品相似度
      • 方法
        • 利用用户行为计算物品之间的相似度
        • 根据物品的相似度和用户的历史行为给用户生成推荐列表
  • 基于矩阵分解/隐语义模型