【机器学习】机器学习阶段二 传统机器学习概览 - hippowc/hippowc.github.io GitHub Wiki

机器学习概览

机器学习是对能通过经验自动改进的计算机算法的研究

传统机器学习算法

knn

• 概述
  • 输入为实例的特征向量，对应于特征空间的点；输出为实例的类别
  • 分类时，对新的实例，根据其 k 个最近邻的训练实例的类别，通过多数表决等方式进行预测。
  • k近邻算法不具有显式的学习过程，即，没有模型训练的步骤
• 工作原理
  • 假设有一个带有标签的样本数据集（训练样本集），其中包含每条数据与所属分类的对应关系。
  • 输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较。
    • 计算新数据与样本数据集中每条数据的距离。
    • 对求得的所有距离进行排序（从小到大，越小表示越相似）
    • 取前 k （k 一般小于等于 20 ）个样本数据对应的分类标签
  • 求 k 个数据中出现次数最多的分类标签作为新数据的分类。
• 关键算法
  • 求距离算法
    • 欧氏距离
    • Minkowski 距离
    • 曼哈顿距离
  • 分类决策算法
    • 少数服从多数 来选取票数最多的标签
• 特点
  • 优点：精度高、对异常值不敏感、无数据输入假定
  • 缺点：计算复杂度高、空间复杂度高
  • 适用数据类型：数值型和标称型

决策树

• 概述
  • 决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。可以认为是 if-then 规则的集合
  • 决策树由结点（node）和有向边（directed edge）组成。结点有两种类型: 内部结点（internal node）和叶结点（leaf node）。内部结点表示一个特征或属性(features)，叶结点表示一个类(labels)
  • 决策树学习通常包括 3 个步骤: 特征选择、决策树的生成和决策树的修剪。
• 工作原理 构造决策树

def createBranch():
    检测数据集中的所有数据的分类标签是否相同:
        If so return 类标签
        Else:
            寻找划分数据集的最好特征（划分之后信息熵最小，也就是信息增益最大的特征）
            划分数据集
            创建分支节点
                for 每个划分的子集
                    调用函数 createBranch （创建分支的函数）并增加返回结果到分支节点中
            return 分支节点

• 关键算法
  • 树构造算法
    • ID3
    • CART
  • 选择最好划分特征算法
    • 计算香农熵
• 特点
  • 优点：计算复杂度不高，输出结果易于理解，数据有缺失也能跑，可以处理不相关特征。
  • 缺点：容易过拟合。
  • 适用数据类型: 数值型和标称型。

朴素贝叶斯

• 概述
  • 贝叶斯分类是一类分类算法的总称，这类算法均以贝叶斯定理为基础
  • 先验概率：根据客观事实和统计频率得出的概率。后验概率：在事情发生后，在事情发生这个事实下，判断导致这个事情发生的不同原因的概率。后验概率是根据先验概率推断而来的。
  • 朴素的意思是：每个特征之间是相互独立的
• 工作原理
  • 朴素贝叶斯的原理归根结底就是使用先验概率去计算后验概率。
  • 假设有一数据集X，包含X1到Xn条数据，每条数据包含m个特征(m维)
  • 数据集输出Y一共有k个类别，表示为1到k。
  • 我们根据频率统计得出输出Y的概率P(y=1)、P(y=2)...P(y=k)
  • 要求Xm的分类，那么求出所有 p(y=k|Xm)的概率(譬如p(y=1|Xm))，然后最大概率的y取值就是其分类
  • 根据条件概率公式，可转换为求p(Xm|y=1)的概率，然后可以根据频率统计得出最终的概率
• 关键算法
  • 通过统计计算先验概率
  • 根据贝叶斯原理计算后验概率
• 特点
  • 优点: 在数据较少的情况下仍然有效，可以处理多类别问题。
  • 缺点: 对于输入数据的准备方式较为敏感。
  • 适用数据类型: 标称型数据。

Logistic回归

• 概述
  • 使用回归思想，根据现有数据对分类边界线(Decision Boundary)建立回归公式，以此进行分类。
• 工作原理

每个回归系数初始化为 1
重复 R 次:
    计算整个数据集的梯度
    使用 步长 x 梯度 更新回归系数的向量
返回回归系数

• 关键算法
  • Sigmoid函数
  • 最优化理论
    • 梯度上升、梯度下降、随机梯度下降
    • 这些算法都有一个共通的缺点就是他们都是不断去逼近真实值，永远只是一个真实值的近似值而已。
• 特点
  • 优点: 计算代价不高，易于理解和实现。
  • 缺点: 容易欠拟合，分类精度可能不高。
  • 适用数据类型: 数值型和标称型数据。

回归

• 概述
  • 回归是对连续型的数据做出处理，回归的目的是预测数值型数据的目标值。
  • 回归问题一般是求一个给定回归方程的系数的问题
  • 说到回归，一般都是指 线性回归(linear regression)。线性回归意味着可以将输入项分别乘以一些常量，再将结果加起来得到输出。
  • 线性回归假设特征和结果满足线性关系。其实线性关系的表达能力非常强大，每个特征对结果的影响强弱可以由前面的参数体现，而且每个特征变量可以首先映射到一个函数，然后再参与线性计算。这样就可以表达特征与结果之间的非线性关系。
• 线性回归
  • 求方程系数常用方法
    • 找出使误差最小的w，误差一般采用平方误差（即最小二乘法）
  • 特点
    • 优点: 结果易于理解，计算上不复杂
    • 缺点: 对非线性的数据拟合不好
    • 适用于数据类型: 数值型和标称型数据
• 局部加权线性回归
  • 在损失函数上加权 Σ(y - yp)^2 --> Σw(y - yp)^2

树回归

• 概述
  • 实际生活中很多问题都是非线性的，不可能使用全局线性模型来拟合任何数据。
  • 一种可行的方法是将数据集切分成很多份易建模的数据，然后利用我们的线性回归技术来建模。如果首次切分后仍然难以拟合线性模型就继续切分。在这种切分方式下，树回归和回归法就相当有用。
• 工作原理
  • 为成功构建以分段常数为叶节点的树，需要度量出数据的一致性
  • 计算连续型数值的混乱度是非常简单的。首先计算所有数据的均值，然后计算每条数据的值到均值的差值。

对每个特征:
    对每个特征值: 
        将数据集切分成两份（小于该特征值的数据样本放在左子树，否则放在右子树）
        计算切分的误差
        如果当前误差小于当前最小误差，那么将当前切分设定为最佳切分并更新最小误差
返回最佳切分的特征和阈值

SVM支持向量机

• 概述
  • 是一种监督学习算法。
  • 支持向量(Support Vector)就是离分隔超平面最近的那些点。
  • 机(Machine)就是表示一种算法，而不是表示机器。
• 概念
  • 数据可以通过画一条直线就可以将它们完全分开，这组数据叫线性可分(linearly separable)数据，而这条分隔直线称为分隔超平面(separating hyperplane)
  • 如果数据集上升到1024维，那么需要1023维来分隔数据集，也就说需要N-1维的对象来分隔，这个对象叫做超平面(hyperlane)，也就是分类的决策边界。
• 工作原理
  • SVM几何含义比较直观，但其算法实现较复杂，牵扯大量数学公式的推导。
• 关键算法
  • 寻找最大间隔
    • 拉格朗日乘子法
    • SMO序列最小优化
• 特点
  • 优点: 泛化（由具体的、个别的扩大为一般的，就是说: 模型训练完后的新样本）错误率低，计算开销不大，结果易理解。
  • 缺点: 对参数调节和核函数的选择敏感，原始分类器不加修改仅适合于处理二分类问题。
  • 使用数据类型: 数值型和标称型数据。

集成方法

• 概述
  • 对其他算法进行组合的一种形式。
  • 当做重要决定时，会考虑吸取多个专家而不只是一个人的意见。
  • 集成方法：
    • 投票选举(bagging: 自举汇聚法 bootstrap aggregating): 是基于数据随机重抽样分类器构造的方法
      • 随机森林(random forest)
    • 再学习(boosting): 是基于所有分类器的加权求和的方法
      • AdaBoost
• bagging工作原理
  • 从原始样本集中抽取训练集.每轮从原始样本集中使用Bootstraping的方法抽取n个训练样本（在训练集中，有些样本可能被多次抽取到，而有些样本可能一次都没有被抽中）.共进行k轮抽取，得到k个训练集.（k个训练集相互独立）
  • 每次使用一个训练集得到一个模型，k个训练集共得到k个模型.（注：根据具体问题采用不同的分类或回归方法，如决策树、神经网络等）
  • 对分类问题：将上步得到的k个模型采用投票的方式得到分类结果；对回归问题，计算上述模型的均值作为最后的结果
• Boosting工作原理
  • 在每一轮如何改变训练数据的权值或概率分布
    • 通过提高那些在前一轮被弱分类器分错样例的权值，减小前一轮分对样本的权值，而误分的样本在后续受到更多的关注.
  • 通过什么方式来组合弱分类器
    • 通过加法模型将弱分类器进行线性组合，比如AdaBoost通过加权多数表决的方式，即增大错误率小的分类器的权值，同时减小错误率较大的分类器的权值.
• 两者区别
  • 样本选择
    • Bagging：训练集是在原始集中有放回选取的，从原始集中选出的各轮训练集之间是独立的
    • Boosting：每一轮的训练集不变，只是训练集中每个样例在分类器中的权重发生变化.而权值是根据上一轮的分类结果进行调整.
  • 样例权重
    • Bagging：使用均匀取样，每个样例的权重相等
    • Boosting：根据错误率不断调整样例的权值，错误率越大则权重越大.
  • 预测函数
    • Bagging：所有预测函数的权重相等
    • Boosting：每个弱分类器都有相应的权重，对于分类误差小的分类器会有更大的权重.

k-means 聚类

• 聚类
  • 一个庞杂数据集中具有相似特征的数据自动归类到一起，称为一个簇，簇内的对象越相似，聚类的效果越好。它是一种无监督的学习(Unsupervised Learning)方法
  • 至于“相似”这一概念，是利用距离这个评价标准来衡量的，我们通过计算对象与对象之间的距离远近来判断它们是否属于同一类别，即是否是同一个簇。
  • 至于距离如何计算，科学家们提出了许多种距离的计算方法，其中欧式距离是最为简单和常用的，除此之外还有曼哈顿距离和余弦相似性距离等。
• k-means
  • 概述
    • K-Means 是发现给定数据集的 K 个簇的聚类算法
  • 优点
    • 属于无监督学习，无须准备训练集
    • 原理简单，实现起来较为容易
    • 结果可解释性较好
  • 缺点
    • 需手动设置k值。 在算法开始预测之前，我们需要手动设置k值，即估计数据大概的类别个数，不合理的k值会使结果缺乏解释性
    • 可能收敛到局部最小值, 在大规模数据集上收敛较慢
    • 对于异常点、离群点敏感

机器学习周边技巧

归一化

归一化就是要把你需要处理的数据经过处理后（通过某种算法）限制在你需要的一定范围内，通常我们会归一化特征值，消除特征之间量级不同导致的影响

常用方法：

• 线性函数转换 y=(x-MinValue)/(MaxValue-MinValue)
• 对数函数转换 y=log10(x)
• 反余切函数转换 y=arctan(x)*2/PI

回归

假设现在有一些数据点，我们用一条直线对这些点进行拟合（这条直线称为最佳拟合直线），这个拟合的过程就叫做回归。进而可以得到对这些点的拟合直线方程

• 二值型输出分类函数
  • 能接受所有的输入然后预测出类别，譬如接受特征，输出0或1
  • 常用函数：
    • 单位阶跃函数：该函数在跳跃点上从 0 瞬间跳跃到 1，这个瞬间跳跃过程有时很难处理。
    • Sigmoid 函数：更平滑的跃阶函数
• 使用Sigmoid函数
  • 1/(1+e^-z)，可以
  • 为了实现 Logistic 回归分类器，我们可以在每个特征上都乘以一个回归系数，然后把所有结果值相加，将这个总和代入 Sigmoid 函数中，进而得到一个范围在 0~1 之间的数值。任何大于 0.5 的数据被分入 1 类，小于 0.5 即被归入 0 类。
  • Sigmoid 函数的输入记为 z, z = w0x0 + w1x1 + ... + wnxn，其中的向量 x 是分类器的输入数据，向量 w 也就是我们要找到的最佳参数（系数），从而使得分类器尽可能地精确。
  • 为了寻找该最佳参数，需要用到最优化理论的一些知识，譬如：梯度上升法

最优化理论

• 梯度上升法
  • 思路：要找到某函数的最大值，最好的方法是沿着该函数的梯度方向探寻。
• 梯度上升法 与 梯度下降法
  • 这个两个方法在此情况下本质上是相同的。关键在于代价函数（cost function）或者叫目标函数（objective function）。
  • 如果目标函数是损失函数，那就是最小化损失函数来求函数的最小值，就用梯度下降。
  • 如果目标函数是似然函数（Likelihood function），就是要最大化似然函数来求函数的最大值，那就用梯度上升。
• 局部最优现象
  • 算法求得的可能是局部最大值，而不是全局最大值

核函数

利用核函数将数据映射到高维空间，经过空间转换后: 低维需要解决的非线性问题，就变成了高维需要解决的线性问题。核函数并不仅仅应用于支持向量机，很多其他的机器学习算法也都用到核函数。最流行的核函数: 径向基函数(radial basis function)