machine learning笔记：机器学习的几个常见算法及其优缺点

接触机器学习也有一段较长的时间了，不敢说自己全部掌握甚至精通，但是期间也了解或者尝试了许多机器学习的算法。这次就结合参考资料和我自己的感受小结一下几种机器学习的常见算法及其优点和缺点。

---

决策树算法

学过数据结构中的树应该对这个算法不会感到困惑，下面就简单介绍一下其优缺点。

1. 优点

   • 易于理解和解释，可以可视化分析，容易提取出规则。
   • 可以同时处理标称型和数值型数据。
   • 测试数据集时，运行速度比较快。
   • 决策树可以很好的扩展到大型数据库中，同时它的大小独立于数据库大小。

2. 缺点

   • 对缺失数据处理比较困难。
   • 容易出现过拟合问题，容易受到例外的干扰，对测试集非常不友好。
   • 忽略数据集中属性的相互关联。
   • ID3算法计算信息增益时结果偏向数值比较多的特征。

3. 改进措施

   • 对决策树进行剪枝。可以采用交叉验证法和加入正则化的方法。较为理想的决策树是叶子节点数少且深度较小。
   • 使用基于决策树的combination算法，如bagging算法，randomforest算法，可以解决过拟合的问题。

4. 常见算法

   1. C4.5算法

      ID3算法是以信息论为基础，以信息熵和信息增益度为衡量标准，从而实现对数据的归纳分类。ID3算法计算每个属性的信息增益，并选取具有最高增益的属性作为给定的测试属性。C4.5算法核心思想是ID3算法，是ID3算法的改进，改进方面有：
      • 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足。
      • 在树构造过程中进行剪枝。
      • 能处理非离散的数据。
      • 能处理不完整的数据。

        优点

      • 产生的分类规则易于理解，准确率较高。

        缺点

      • 在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。
      • C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。

   2. CART分类与回归树

      这是一种决策树分类方法，采用基于最小距离的基尼指数估计函数，用来决定由该子数据集生成的决策树的拓展形。如果目标变量是标称的，称为分类树；如果目标变量是连续的，称为回归树。分类树是使用树结构算法将数据分成离散类的方法。

      优点

      • 非常灵活，可以允许有部分错分成本，还可指定先验概率分布，可使用自动的成本复杂性剪枝来得到归纳性更强的树。
      • 在面对诸如存在缺失值、变量数多等问题时CART显得非常稳健。

      下面对决策树的各种算法做一个小结：
      

      算法	支持模型	树结构	特征选择
      ID3	分类	多叉树	信息增益
      C4.5	分类	多叉树	信息增益比
      CART	分类、回归	二叉树	基尼系数、均方差

      补充：
      信息熵：表示随机变量的不确定性，熵越大，不确定性越大。这与物理中的熵性质类似。
      信息增益：即不确定性减小的幅度。信息增益=信息熵（前）-信息熵（后）。在构造决策树的时候往往选择信息增益大的特征优先作为节点分类标准。
      信息增益比：由于仅根据信息增益构建决策树，那么三叉树以及多叉树比二叉树的效果一般来说分类效果要好，然而这很有可能会导致过拟合的问题。因此定义信息增益比=惩罚参数*信息增益。当特征个数较多时，惩罚参数较小；当特征个数较少时，惩罚参数较大，从而使信息增益比较大，进而克服信息增益偏向于选取取值较多的特征的问题。总的来说，信息增益比相对于信息增益更客观。
      基尼系数：表示集合的不确定性，基尼系数越大，则表示不平等程度越高。

---

分类算法

1. KNN算法

   1. 优点

      • KNN是一种在线技术，新数据可以直接加入数据集而不必进行重新训练。
      • KNN理论简单，容易实现。实际上，KNN没有训练过程，或者说，它的训练过程就是导入数据集。

   2. 缺点

      • KNN对于样本容量大的数据集计算量比较大，极易引发维度灾难。
      • 样本不平衡时，预测偏差比较大。如：某一类的样本比较少，而其它类样本比较多。
      • KNN每一次分类都会重新进行一次全局运算，耗时久。这在实践中会非常有体会，可以参考kaggle笔记：手写数字识别——使用KNN和CNN尝试MNIST数据集。
      • 在CV领域，KNN已经被完全弃用。这是因为它不适合用来表示图像之间的视觉感知差异，如下图所示，这是CS231n中提到的一个例子，后三张图片经过不同的变换，结果与第一张原图的L2距离居然是一样的，而显然对我们而言这三张图是有很大区别的，在实际应用中往往应该区分开。

   3. 应用领域

      • 文本分类。
      • 模式识别。
      • 聚类分析。
      • 多分类领域。

2. 支持向量机（SVM）

   支持向量机是一种基于分类边界的方法。其基本原理是（以二维数据为例）：如果训练数据分布在二维平面上的点，它们按照其分类聚集在不同的区域。基于分类边界的分类算法的目标是：通过训练，找到这些分类之间的边界（直线的称为线性划分，曲线的称为非线性划分）。对于多维数据（如N维），可以将它们视为N维空间中的点，而分类边界就是N维空间中的面，称为超面（超面比N维空间少一维）。线性分类器使用超平面类型的边界，非线性分类器使用超曲面。
   支持向量机的原理是将低维空间的点映射到高维空间，使它们成为线性可分，再使用线性划分的原理来判断分类边界。在高维空间中是一种线性划分，而在原有的数据空间中，是一种非线性划分。
   在我的博文machine-learning笔记：一个支持向量机的问题中，我提及了SVM的简介与一个问题，感兴趣的话可以了解一下。

   1. 优点

      • 解决小样本下机器学习问题，相对于其他训练分类算法不需要过多样本。
      • 解决非线性问题。擅长应付线性不可分，主要用松弛变量（惩罚变量）和核函数来实现。
      • 无局部极小值问题。（相对于神经网络等算法）
      • 引入了核函数，可以很好的处理高维数据集。
      • 泛化能力比较强。结构风险最小，指分类器对问题真实模型的逼近与真实解之间的累计误差。

   2. 缺点

      • 对于核函数的高维映射解释力不强，尤其是径向基函数。
      • 对缺失数据敏感。

   3. 应用领域：

      • 文本分类。
      • 图像识别。
      • 主要二分类领域。

3. 朴素贝叶斯算法

   朴素贝叶斯，即naive bayes。说白了就是要“sometimes naive”。

   1. 优点

      • 对大数量训练和查询时具有较高的速度。即使使用超大规模的训练集，针对每个项目通常也只会有相对较少的特征数，并且对项目的训练和分类也仅仅是特征概率的数学运算而已。
      • 支持增量式运算。即可以实时的对新增的样本进行训练。
      • 朴素贝叶斯对结果解释容易理解。

   2. 缺点

      • 由于使用了样本属性独立性的假设，所以如果样本属性有关联时其效果不好。

   3. 应用领域

      • 文本分类。
      • 欺诈检测。

4. Logistic回归算法

   1. 优点

      • 计算代价不高，易于理解和实现。

   2. 缺点

      • 容易产生欠拟合。
      • 分类精度不高。

   3. 应用领域

      • 用于二分类领域，可以得出概率值，适用于根据分类概率排名的领域，如搜索排名等。
      • Logistic回归的扩展softmax可以应用于多分类领域，如手写字识别等。

---

聚类算法

1. K-means算法

   K-means算法，即K均值算法，是一个简单的聚类算法，把n个对象根据它们的属性分为k个分割，k小于n。算法的核心就是要优化失真函数J，使其收敛到局部最小值但不是全局最小值。它比较适合凸数据集，即任意两个数据点之间的连线都在数据集内部。

   1. 算法流程

      1. 随机选择k个随机的点（称为聚类中心）。
      2. 对数据集中的每个数据点，按照距离k个中心的距离，将其与最近的中心点关联起来，与同一中心点关联的点聚成一类。
      3. 计算每一组的均值，将该组所关联的中心点移到平均值的位置。
      4. 重复第2、3两步，直到中心点不再变化。

   2. 优点

      • 算法速度很快。

   3. 缺点

      • 分组的数目k是一个输入超参数，不合适的k可能返回较差的结果。

2. EM最大期望算法

   EM算法是基于模型的聚类方法，是在概率模型中寻找参数最大似然估计的算法，其中概率模型依赖于无法观测的隐藏变量。E步估计隐含变量，M步估计其他参数，交替将极值推向最大。
   EM算法比K-means算法计算复杂，收敛也较慢，不适于大规模数据集和高维数据，但比K-means算法计算结果稳定、准确。EM经常用在机器学习和计算机视觉的数据集聚（Data Clustering）领域。

---

集成算法（AdaBoost）

俗话说的好“三个臭皮匠，顶个诸葛亮”，集成算法就是将多个弱分类器集成在一起，构建一个强分类器。事实上，它可能不属于算法，而更像一种优化手段。

1. 优点

   • 很好的利用了弱分类器进行级联。
   • 可以将不同的分类算法作为弱分类器。
   • AdaBoost具有很高的精度。
   • 相对于bagging算法和randomforest算法，AdaBoost充分考虑的每个分类器的权重。

2. 缺点

   • AdaBoost迭代次数也就是弱分类器数目不太好设定，可以使用交叉验证来进行确定。
   • 数据不平衡导致分类精度下降。
   • 训练比较耗时，每次重新选择当前分类器最好切分点。

3. 应用领域

   • 模式识别。
   • 计算机视觉领域。
   • 二分类和多分类场景。

---

神经网络算法

1. 优点

   • 分类准确度高，学习能力极强。
   • 对噪声数据鲁棒性和容错性较强。
   • 有联想能力，能逼近任意非线性关系。

2. 缺点

   • 神经网络参数较多，权值和阈值。我在训练一个只有四层的CNN时，C盘就被占用了几个G，详细情况可见kaggle笔记：手写数字识别——使用KNN和CNN尝试MNIST数据集。
   • 黑盒过程，不能观察中间的结果，甚至无法完全理解其是怎么达到效果的。
   • 学习过程比较长，有可能陷入局部极小值。

3. 应用领域

   • 计算机视觉。
   • 自然语言处理。
   • 语音识别等。