机器学习数据挖掘常用算法总结梳理完整版

所需积分/C币:37 2018-08-08 10:44:15 2MB PDF
376
收藏 收藏
举报

机器学习数据挖掘常用算法总结梳理完整版:是对于机器学习以及数据挖掘领域中使用到的算法、方法和模型等方面一个全面的总结和学习概括,欢迎同行互相交流学习,欢迎指点。
表1天气预报数据集例子 Outlook Temperature Humidity Windy Play? sunny false sunny hot true n overcast hot false yes rain high false yes raIn cool normal false raIn cool normal true no overcast cool normal true yes sunny false no sunny normal false yes raIn mild normal false yes sunny mild normal true ves overcast mild high true yes overcast hot normal false yes rain mild high true no 可以看出,一共14个样例,包括9个正例和5个负例。那么当前信息的熵计算如下 95 5 Entropy(s) 1og21o924≈0.940286 14 outlook sunny overcast rainy yes yes yes ves yes yes no Yes ves no no yes no 划分后,数据被分为三部分了,那么各个分支的信息熵计算如下 23 3 Entropy(sunny)=-=10525 6 logs =0.970951 Entropy( overcast)s、4 40824-0log20=0 3 Entropy(rainy)=--loga=_=%,s 0970951 那么划分后的信息熵为 5 Entropy(ST)=0.970951+:0+0.970951=0.693536 14 14 总结 ID3算法:以信息増益为准则选择信息増益最大的属性。 缺点: 1)信息增益对可取值数目较多的属性有所偏好,比如通过I号可将每个样本分 成一类,但是没有意义 2)ID3只能对离散属性的数据集构造决策树 C45决策树 C4.5基于⑩3改进而提出的。D3采用的信息增益度量存在一个缺点,它 般会优先选择有较多属性值的 Feature,因为属性值多的 Feature会有相对较大的 信息增益,信息增益反映的给定一个条件以后不确定性减少的程度,必然是分得 越细的数据集确定性更髙,也就是条件熵越小,信息增益越大.为了避免这个不足 C4.5中是用信息增益率( gainratio)来作为选择分支的准则。信息增益率通过引入 个被称作分裂信息( Splitinformation)的项来惩罚取值较多的 Feature除此之外 C4.5还弥补了ID3中不能处理特征属性值连续的问题。但是,刈连续属性值需 要扫描排序,会使C4.5性能下降 SplilInformalion(D,A)= g(D, A Gain ratio(d, a) splillnformaLion(D, A 但是当某个D2的大小跟D的大小接近的时候, Splitinformation(D,A)→0, Gain ratio(D,4)→∞,为了避免这样的属性可以采用启发式的思 路,只对那些信息增益比较高的属性才应用信息增益比率. C45是狂揉的,只要你给它输入属性和喻出属性,即使输出和输入之间没有 任何关系,决策树一样可以给岀很不错的决策正确率,尤其是集内测试正确率 C45还允许属性值缺失,它会将其当做一类处理。 C45能自动排除那些不相关的属性,但是在训练数据稀疏的情况下,决策树 一样会利用那些不相关的属性,得到一些结论。所以不能一咕脑儿把所有的属性 扔给决策树,还是需要对输入属性与输出属性之间有没有关联进行仔细的分析 决策树的结论属性不宜太多。超过20就是很不好了,因为决策树认为结论 属性完全是枚举类型的,结论属性之间的各个可能的取值没有仁何关系,如果问 题中结论属性有一·定的连续意义,比如预测一个韵律环境下音节应该的长度,那 么则决策树的效果就很有可能比其他的类似于拟合的算法差∫。决策树在分析各 个属性时,是完全独立的。比如如果其实数据中只需要一条规律:“属性A的值 比属性B的值大的时候,输出为1,否则为0”的话,决策树无法给出这样的规 律,因为它只会尝试属性A和某个常数的比较,属性B和某个常数的比较,而 不会比较属性A和属性B的差值。 C4.5还能处理连续属性值,具体步骤为: http://eijun00.github.1o/2014/09/decision-tree 把需要处理的样本(对应根节点)或样本子集(对应子树)按照连续变量的大小 从小到大进行排序假设该属性对应的不同的属性值一共有NN个,那么总共有 N-1N-1个可能的候选分割阈值点,每个候选的分割阈值点的值为上述排序后的 属性值中两两前后连续元素的中点,根据这个分割点把原来连续的属性分成bool 属性实际上可以不用检查所有N-1N-1个分割点,用信息增益比率选择最佳划 分 C4.5还能对缺失值进行处理,处理的方式通常有三种 1)赋上该属性最常见的值 2)根据节点的样例上该属性值出现的情况赋一个概率,比如该节点上有10 个样本,其中属性A的取值有6个为是,4个为否.那么对改节点上缺失的属性A, 以0.6的概率设为是,04的概率设为否 3)丢弃有缺失值的样本 结 4.5算法:以信息增益率为准则选择属性;在信息增益的基础上对属性冇 个惩罚,抑制可取值较多的属性,增强泛化性能。 其他优点: 1)在树的构造过程中可以进行剪枝,缓解过拟合 2)能够对连续属性进行离散化处理(二分法); 3)能够对缺失值进行处理: 缺点: 构造树的过程需要对数据集进行多次顺序扫描和排序,导致算法低效; 刚才我们提到信息增益对可取值数目较多的属性有所偏好 而信息増益率对可取值数目较少的属性有所偏好 解决方法: 先从候选属性中找岀信息增益高于平均水平的属性,再从中选择增益率最高的。 而不是大家常说的直接选择信息增益率最高的属性! CART分类回归树 CART( Classification and regression trio)分类回归树。D3中根据属性值分 割数据,之后该特征不会再起作用,这种快速切割的方式会影响算法的准确率。 CART是一棵二叉树,米用二元切分法,每次把数据切成两份,分别进入左子树、 右子树。而且每个非叶子节点都有两个孩子,所以CART的叶子节点比非叶子多 1。相比I3和C4.5,CART应用要多一些,既可以用于分类也可以用于回归 CART分类时,使用基尼指数(Gini)来选择最好的数据分割的特征,gini描述 的是纯度,与信息熵的含义相似。CART中每一次迭代都会降低GINI系数。回 归时使用均方差作为 loss function。基尼系数的计算与信息熵增益的方式非常类 似 Gm(D)=1-∑(2n) in(D|A)=∑ Gini( di) 总结: CART算法( Classification and Regression Tree):顾名思义,可以进行分类和 回归,可以处理离散属性,也可以处理连续的。分类树使用GINI指数来选择划 分属性:在所有候选属性中,选择划分后GINI指数最小的属性作为优先划分属 性。回归树就用最小平方差。 二者简单的总结 样本数据的差异 ·D3只能对分类变量进行处理,C4.5和CART可以处理连续和分类丙种自变量 ·D3对缺失值敏感,而c4.5和CART对缺失值可以进行多种方式的处理 ·只从样本量考虑,小样本建议考虑4.5、大样本建议考虑cart。c4.5处理过程中需对数据集进 行多次排序,处理成本耗时较高,而car本身是一种大样本的统计方法,小样本处理下泛化误 差较大 目标医变量的差异: ·1D3和C4.5只能做分类,CART(分类回归树)不仅可以做分类(0/1)还可以做回归(0-1) ·|D3和C45节点上可以产出多叉(低、中、高),而CART节点上永远是二叉(低、非低 样本特征上的差异: ·特征变量的使用中,多分的分类变量D3和C45层级之间只单次使用,CART可多次重复使用 决策树产生过程中的优化差异: C4.5是通过枝剪来修正树的准确性,而CART是直接利用全部数据发现所有树的结构进行对比 树的前枝问题 使川树模型很容易引起过拟合,这里就需要采取一定的措施防止过拟合。前 面的算法生成的决策树非常详细并且庞大,每个属性都被详细地加以考虑,决策 树的树叶节点所覆盖的训练样本都是“纯”的。因此用这个决策树来对训练样本进 行分类的话,你会发现对于训练样本而言,这个树表现完好,误差率极低且能够 正确得对训练样木集中的样木进行分类(泛化能力很低)。训练样木中的错误数 据也会被决策树学习,成为决策树的部分,但是对于测试数据的表现就没有想象 的那么好,或者极差,这就是所谓的过拟合( Overfitting问题。 在数据集中,过拟合的决策树的错误率比经过简化的决策树的错误率要高。 怎么剪枝 剪枝可以分为两种:预剪枝(Pre- Pruning)和后剪枝( Post-Pruning) PrePrune:预剪枝,及早的停止树增长,方法可以参考见上面树停止增长的方法。 PostPrune:后剪枝,在已生成过拟合决策树上进行剪枝,可以得到简化版的剪枝 决策树。 其实剪枝的准则是如何确定决策树的规模,可以参考的剪枝思路有以下几个: http://blog.csdn.net/u011067360/article/details/24871801 l:使用训练集合( Training Set)和验证集合( Validation Set),来评估剪枝方法在修 剪结点上的效用 2:使用所有的训练集合进行训练,但是用统计测试来估计修剪特定结点是否会 改善训练集合外的数据的评估性能,如使用 Chi-Square( Quinlan,1986)测试来 进一步扩展结点是否能改善整个分类数据的性能,还是仅仅改善了当前训练集合 数据上的性能。 3:使用明确的标准来衡量训练样例和决筼树的复杂度,岀编码长度最小时,停 止树增长,如 MDL( Minimum Description Length)准则。 基于概率的方法 分类原理是通过某对象的先验概率,利用概率计算公式计算出其后验概率 即该对象属于某一·类的概率,选择具有最大后验概率的类作为该对象所属的类, 在这方面最经典的方法航是贝叶斯方法。 朴素贝叶斯假设是约束性很强的假设,假设特征条件独立,虽然这一偎设条 件在现实中几乎是不成立的,但是事实证明 Baves效果很岀色,朴素贝叶斯算法 简单,快速,具有较小的出错率。在朴素贝叶斯的应用中,主要研究了电子邮件 过滤以及文木分类研究 根据贝叶斯定理,对一个分类问题,给定样本特征X,样本属于类别y的概率是 (12)p(a9)p(y) (1) 朴素贝叶斯的主要缺点有: 1)理论上,朴素贝叶斯模型与其他分类方法相比具有最小的误差率。但是实际 上并非总是如此,这是因为朴素贝叶斯模型假设属性之间相互独立,这个假设在 实际应用中往往是不成立的,在属性个数比较多或者属性之间相关性较大时,分 类效果不好。而在属性相关性较小时,朴素贝叶斯性能最为良好。对于这一点, 有半朴素贝叶斯之类的算法通过考虑部分关联性适度改进 2)需要知道先验概率,且先验概率很多时候取决于假设,假设的模型可以有很 多种,因此在某些时候会由于假设的先验模型的原因导致预测效果不佳。 3)由于我们是通过先验和数据来决定后验的概率从而决定分类,所以分类决策 存在一定的错误率。 4)对输入数据的表达形式很敏感。 贝叶斯优点: (1)朴素贝叶斯模型发源于古典数学理论,有着坚实的数学基础,以及稳定的分 类效率; (2)对小规模的数据表现很好,能个处理多分类仼务 (3)对缺失数据不太敏感,算法也比较简单,常用于文本分类 (4)对大数量训练和査询时具有较高的逑度。即使使用超大规模的训练集,针对 每个项目通常也只会有相对较少的特征数,并且对项目的训练和分类也仅仅是特 征概率的数学运算而已 (5)支持增量式运算。即可以实时的对新增的样本进行训练; (6)朴素贝叶斯对结果解释容易理解。 贝叶斯缺点: (1)需要计算先验概率; (2)分类决策存在错误率; (3)对输入数据的表达形式很敏感。 (4)由于使用了样本属性独立性的假设,所以如果样本属性们关联吋其效果不好 主要应用范围: 文木分类、欺诈检测中使用较多 基于核的方法 利用核两数将低维线性不可分问题转化为高维线性可分问题,从而找到可用 于分割空问的超平面完成分类,这方面最经典的方法就是SVM了。SVM在解决 小样本、非线性及高维模式识别问题中表现岀许多特有的优势,并能够推广应用 到函数拟合等其他机器学习问题中 Ⅹ C XX 分离超平面 H1 H2 2 Class 2 Wx+b=1 Class 1 wx+b=-1 wx+b=O net/zouxy09 在议两个超平面上的样本点也就是理论上离分隔超平面最近的点,是它们的存在决定了H1和H2的位置,支撑起了分界 线,它们就是所谓的支持向量,这就是支持向量机的由来 SwM中常用核函数有四种:多项式核数、高斯核函数RBF、线性核函数、 sigmod核函数。核函数的价值在于它虽然也是将特征进行从低维到高维的转换, 但核涵数绝就绝在它事先在低维上进行计算,而将实质上的分类效果表现在了高 维上,也就如上文所说的避免了直接在高维空间中的复杂计算。 在选用核函数的时候,如果我们对我们的数据有一定的先验知识,就利用先 验来选择符合数据分布的核数;如果不知道的话,通常使用交义验证的方法, 来试用不同的核函数,误差最下的即为效果最好的核函数,或者也可以将多个核 函数结合起来,形成混合核函数。选择核函数的方法: 如果特征的数量大到和样本数量差不多,则选用LR或者线性核的SVM 如果特征的数量小,样木的数量正常,则选用SⅴM+高斯核函数 如果特征的数量小,而样本的数量很大,则需要手工添加一些特征从而变成 第一种情况 ·线性核函数 (,a)=x·c 线性核,主要用于线性可分的情况,我们可以看到特征空间到输入空间的维度是一样的,其参数少速 度快,对于线性可分数据,其分类效果很理想,因此我们通常首先尝试用线性核函数来做分类,看看 效果如何,如果不行再换别的 多项式核函数 (z,)=(:)+1) 多项式核函数可以实现将低维的输入空间映射到高纬的特征空间,但是多项式核函数的参数多,当多 项式的阶数比较高的时候,核矩阵的元素值将趋于无穷大或者无穷小,计算复杂度会大到无法计算。 高斯(RBF)核函数 2 (,Z p( 高斯径向基函数是一种局部性強的核函数,其可以将一个样木映射到一个更高维的空间內,该核函数 是应用最广的一个,无论大样本还是小样本都有比较好的性能,而且其相对于多项式核函数参数要 少,因此大多数情况下在不知道用什么核函数的时候,优先使用高斯核函数。 sigmoid核函数 A(a,a ( 采用 sigmoid核函数,支持向量机实现的就是一种多层神经网络。 SVM优点: (1)可以解决高维问题,即大型特征空问 (2)能够处理非线性特征的相互作用; (3)解决小样本下机器学习问题。 4)无需依赖整个数据; (5)泛化能力比较强 (6)无局部极小值问题。(相对于神经网络等算法) SVM缺点 (1)当观测样本很多时,效率并不是很高(人样本反而不合适) (2)对非线性问题没有通用解决方案,有时候很难找到一个合适的核函数; (3)对缺失数据敏感 主要应用范围: 文本分类、图像识别、主要二分类领域 基于距离的方法 在这里比较常用的经典的方法是KNN。kNN算法的核心思想是如果一个样 本在特征空间中的k个最相邻的样本中的大多数属于某一个类别,则该样本也属 于这个类別,并具有这个类別上样本的特性。该方法在确定分类决策上只依据最 邻近的一个或老几个样本的类别来决定待分样本所属的类别。 这里的距离选择较为重要,一般使用以下两种距离 欧式距离:d(xy)=1∑(-),曼哈顿距离:a(x,y)=1∑x-1 k=1 算法的流程: 1)讣算测试数据与各个训练数据之间的距离 2)按照距离的递增关系进行排序; 3)选取距离最小的K个点; 4)确定前K个点所在类别的出现频率 5)返回前K个点中出现频率最高的类别作为测试数据的预测分类 KNN优点: (1)理论成熟,思想简单,既可以用来做分类也可以用来做回归; (2)可用于非线性分类 (3)训练时间复杂度为O(n) (4)对数据没有假设,准确度高,对 outlier不敏感; (5)KNN是一种在线技术,新数据可以直接加入数据集而不必进行重新训练 KNN缺点: (1)对于样木容量大的数据集计算量比较大。 (2)样本不平衡时,预测偏差比较大。如:某一类的样本比较少,而其它类样本 比较多。 (3)KNN每次分类都会重新进行一次全局运算 (4)k值大小的选择。 5)需要大量的内存 主要应用范围: 文本分类、模式识别、聚类分析,多分类领域 聚类算法 聚类算法是机器学习中的另一大类别,聚类的准则是类间距离最大,类内距 离最小,即把最相似的样木放在同一类中。 层次聚类 层次法( Hierarchical methods)先计算样本之间的距离。每次将距离最近的 点合并到同一个类。然后,再计算类与类之间的距离,将距离最近的类合并为 个大类。不停的合并,直到合成了一个类。 其中类与类的距离的计算方法有:最短距离法,最长距离法,中间距离法, 类平均法等。比如最短距离法,将类与类的距离定义为类与类之间样本的最短距

...展开详情
试读 19P 机器学习数据挖掘常用算法总结梳理完整版
立即下载
限时抽奖 低至0.43元/次
身份认证后 购VIP低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • GitHub

  • 签到王者

  • 技术圈认证(专家版)

  • 分享王者

关注 私信
上传资源赚钱or赚积分
最新推荐
机器学习数据挖掘常用算法总结梳理完整版 37积分/C币 立即下载
1/19
机器学习数据挖掘常用算法总结梳理完整版第1页
机器学习数据挖掘常用算法总结梳理完整版第2页
机器学习数据挖掘常用算法总结梳理完整版第3页
机器学习数据挖掘常用算法总结梳理完整版第4页

试读结束, 可继续读2页

37积分/C币 立即下载