机器学习算法优缺点笔记

Handsome_zhou

集成算法

Bagging
1.Bagging通过降低基分类器的方差，改善了泛化误差
2.性能依赖于基分类器的稳定性；如果基分类器不稳定，bagging有助于降低训练数据的随机波动导致的误差；如果稳定，则集成分类器的误差主要由基分类器的偏倚引起
3.由于每个样本选中的概率相同，因此bagging并不侧重于训练数据集中的任何特定的实例。

Boosting
其主要思想是将弱分类器组装成一个强分类器。在PAC(probably approximately correct,概率近似正确)学习框架下，则一定可以将弱分类器组装成一个强分类器。

关于Boosting的两个核心问题：
      1）在每一轮如何改变数据的权值和概率分布？
      通过提高那些在前一轮被弱分类器分错样例 的权值，减小前一轮分对样例的权值，来使得分类器对误分的数据有较好的效果。
      2）通过什么方式来组合弱分类器？
      通过加法模型将弱分类器进行线性组合，比如：
      AdaBoost(Adaptive boosting)算法：刚开始训练时对每一个训练例赋相等的权重，然后用该算法对训练集训练t轮，每次训练后，对训练失败的训练例赋以较大的权重，也就是让学习算法在每次学错以后更加注意学错的成本，从而得到多个预测函数。通过拟合残差的方式减少残差，将每一步生成的模型叠加得到最终的模型。
      GBDT(Gradient Boost Decision Tree),每一次的计算是为了减少上一次的残差，GBDT在残差减少(负梯度)的方向上建立一个新的模型。

常用的集成算法是随机森林
在随机森林中，集成中的每棵树都是由从训练集中抽取的样本构建的。另外，与使用所有特征不同，这里随机选择特征子集，从而进一步达到对树的随机化目的。
因此，随机森林产生的偏差略有增加，但是由于对相关性较小的树计算平均值，估计方差减小了，导致模型的整体效果更好。

聚类分析
K-means算法的优点如下：
   (1)它是解决聚类问题的一种简单、快速的经典算法
   (2)它的复杂度是O(nkt)。其中，n是所有对象的数目，k是簇的数目，t是迭代的次数。当结果簇是密集的并且簇与簇之间区别明显时，它的效果较好。
   (3)对于处理大数据集，该算法保持了可伸缩性和高效性。
K-means算法的缺点如下：
   (1)在簇的均值被定义的情况下才能使用，对某些应用可能并不适用。
   (2)在k-means算法中k是事先给定的，这个k值的选定是难以估计的，往往事先并不知道给定的数据集应该分成多少个类别才最合适。
   (3)在k-means算法中，首先需要根据初始簇中心来确定初始划分，然后对初始划分进行优化。这个初始簇中心的选择对聚类结果有较大的影响，如果初始值选择得不好，就可能无法得到有效得聚类结果。也就是说，该算法对初始值敏感。
   (4)该算法需要不断地进行样本分类调整，不断地计算调整后的新的簇中心，因此当数据量很大时，该算法的时间开销较大。
   (5)若簇中含有异常点，将导致均值偏离严重，即该算法对噪声和孤立点数据敏感。



分类


KNN算法的优点如下：
(1)简单，易于理解，易于实现，无须估计参数，无须训练。
(2)适合对稀有事件进行分类
(3)特别适用于多分类问题
KNN算法有如下缺点：
(1)对每一个待分类样本都要计算它到全体训练样本的距离，才能求得它的k个最近邻。对测试样本进行分类时计算量大，内存开销大。
(2)可解释性较差，无法给出像决策树那样的规则
(3)当样本不平衡(例如，一个类的样本容量很大，而其他类的样本容量很小）时，有可能导致以下情况：当输入一个新样本时，该样本的k个近邻中大容量类的样本占多数，影响分类结果。


朴素贝叶斯分类算法有以下优点：
(1)算法逻辑简单，易于实现。
(2)分类过程中时空开销小。
(3)朴素贝叶斯分类模型发源于古典数学理论，有着坚实的数学基础以及稳定的分类效率。
(4)该算法所需估计的参数很少，对缺失数据不太敏感。
朴素贝叶斯分类算法有如下缺点：
(1)在实际情况下，类别总体的概率分布和各类别样本的概率分布函数(或密度函数)常常是未知的。为了获得它们，要求样本量足够大。另外，该算法用于文本分类时，要求表达文本的主题词相互独立，这样的条件在实际文本中一般很难满足，因此该算法往往在文本分类效果上难以到达理论上的最大值。
(2)需要知道先验概率
(3)分类决策有一定的错误率
(4)理论上，朴素贝叶斯分类算法与其他分类器算法相比具有最小的误差率；但是实际上并非总是如此，这是因为朴素贝叶斯分类算法假设各特征属性相互独立，这个假设在实际应用中往往是不成立的，在属性个数比较多或者属性之间相关性比较大时，分类效果不好。


决策树分类
决策树算法有ID3，C4.5，CART, SLIQ，CHAID

CART算法的优点如下：
(1)CART算法采用了简化的二叉树模型，同时在选择属性时采用了近似的基尼系数来简化计算。
(2)二叉树最大的好处是还可以作为回归模型
CART算法的缺点如下：
(1)CART算法在进行特征属性选择的时候都是最优的一个特征属性来进行分类决策，但是大多数分类决策不是由一个特征决定的，而是由一组特征属性决定的。根据一组特征属性构造的决策树更加准确。
(2)样本发生很小的改变，就会导致二叉树结构的剧烈改变。这个问题可以通过集成学习中的随机森林等方法解决。

ID3算法的优点如下：
(1)理论清晰，方法简单，学习能力较强
(2)生成的规则易被人理解
(3)适用于处理大规模的学习问题
(4)构建决策树的速度较快，计算时间随数据的增加呈线性地增加
(5)ID3算法不存在无解的危险，并且全盘使用训练数据，而不是像候选剪除算法那样逐个考虑训练集，从而可以抵抗噪声
(6)全盘使用训练数据，可得到一颗较为优化的决策树
ID3算法的缺点如下：
(1)ID3算法倾向于选择拥有多个属性值的属性作为分裂属性，而这些属性不一定是最佳分裂属性
(2)只能处理离散属性，对于连续型的属性，在分类前需要对其进行离散化处理，才可使用此方法
(3)无法对决策树进行优化，生成的决策树往往过于拟合
(4)当类别太多时，错误可能就会增加得比较快
(5)ID3不能以增量方式接受训练集，每增加一次实例就要抛弃原有得决策树，重新构造新得决策树，开销很大


C4.5算法优点如下：
(1)产生的分类规则易于理解，准确率较高
(2)通过信息增益选择分类属性，弥补了ID3算法中通过信息增益倾向于选择拥有多个属性值的属性作为分类属性的不足
(3)能够处理离散型和连续型属性，即对连续型属性进行离散化处理
(4)构造决策树之后进行剪枝操作
(5)能够处理具有缺失属性值的训练集
C4.5算法缺点如下：
(1)在构造决策树的过程中，需要对训练集进行多次遍历和排序(特别是针对含有连续型属性值的训练集时，这一点尤为突出)，因而导致算法效率低
(2)C4.5算法只适用于能够驻留于内存的训练集；当训练集大得无法放在内存中时，程序无法进行
(3)C4.5算法在选择分裂属性时没有考虑到条件属性间的相关性，只计算数据集中每一个条件属性与决策属性之间的期望信息，有可能影响属性选择的正确性

以上三种算法的比较：
(1)ID3和C4.5算法在每个节点上可以产生多个分支，而CART算法在每个节点上只会产生两个分支
(2)C4.5算法通过引入信息增益率，弥补了ID3算法在特征取值比较多时由于过度拟合而使泛化能力变弱的缺陷
(3)ID3算法只能处理离散型属性，而C4.5算法和CART算法可以处理连续型属性
(4)ID3算法和C4.5算法只能用于分类任务，而CART算法可以用于分类和回归任务
(5)CART算法通过基尼系数进行划分，C4.5算法通过信息增益率进行划分，ID3算法通过信息增益率进行划分

tomok

谢谢分享