机器学习经典算法(PPT45页)

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,11/7/2009,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,经典算法,机器学习十大经典算法,C4.5,分类与回归树,朴素贝叶斯,支持向量机（SVM),K近邻（KNN）,AdaBoost,K均值（K-means）,最大期望（EM）,Apriori算法,Pagerank,机器学习方法的分类,基于学习方式的分类,（1）,有监督学习：,输入数据中有导师信号，以概率函数、代数函数或人工神经网络为基函数模型，采用迭代计算方法，学习结果为函数。,（2）,无监督学习：,输入数据中无导师信号，采用聚类方法，学习结果为类别。典型的无导师学习有发现学习、聚类、竞争学习等。,（3）,强化学习（增强学习）：,以环境反馈（奖/惩信号）作为输入，以统计和动态规划技术为指导的一种学习方法。,有监督学习（用于分类）,标定的训练数据,训练过程：根据目标输出与实际输出的误差信号来调节参数,典型方法,全局：BN,NN,SVM,Decision Tree,局部：KNN、CBR(Case-base reasoning),S(x)=0,Class A,S(x)0,Class B,S(x)=0,Objects,X2,(area),(perimeter)X1,Object Feature Representation,无监督学习（用于聚类）,不存在标定的训练数据,学习机根据外部数据的统计规律（e.g.Cohension&divergence）来调节系统参数，以使输出能反映数据的某种特性。,典型方法,K-means、SOM.,示例：聚类,半监督学习,结合（少量的）标定训练数据和（大量的）未标定数据来进行学习,典型方法,Co-training、EM、Latent variables.,一、C4.5,C4.5由J.Ross Quinlan在ID3的基础上提出的。ID3算法用来构造决策树。决策树是一种类似流程图的树结构，其中每个内部节点（非树叶节点）表示在一个属性上的测试，每个分枝代表一个测试输出，而每个树叶节点存放一个类标号。一旦建立好了决策树，对于一个未给定类标号的元组，跟踪一条有根节点到叶节点的路径，该叶节点就存放着该元组的预测。,决策树的优势在于不需要任何领域知识或参数设置，产生的分类规则易于理解，准确率较高。适合于探测性的知识发现。,缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。,增益比率度量是用增益度量Gain(S，A)和分裂信息度量SplitInformation(S，A)来共同定义的,设,S,代表训练数据集，由,s,个样本组成。,A,是,S,的某个属性，有,m,个不同的取值，根据这些取值可以把,S,划分为,m,个子集，,S,i,表示第,i,个子集（,i,=1,2,m,），|,S,i,|表示子集,S,i,中的样本数量。,数据集如图1所示，它表示的是天气情况与去不去打高尔夫球之间的关系,二、,分类和回归树（Classification and Regression TreesCART，可简写为C&RT）,CART算法中的每一次分裂把数据分为两个子集，每个子集中的样本比被划分之前具有更好的一致性。它是一个递归的过程，也就是说，这些子集还会被继续划分，这个过程不断重复，直到满足终止准则，然后通过修剪和评估，得到一棵最优的决策树。,在ID3算法中，用“熵”来度量数据集随机性的程度。在CART中我们把这种随机性的程度称为“杂度”（impurity，也称为“不纯度”），并且用“吉尼”(gini)指标来衡量它。,决策树停止生长的条件,满足以下一个即停止生长。,（1）节点达到完全纯性；,（2）数树的深度达到用户指定的深度；,（3）节点中样本的个数少于用户指定的个数；,（4）异质性指标下降的最大幅度小于用户指定的幅度。,剪枝：完整的决策树对训练样本特征的描述可能“过于精确”（受噪声数据的影响），缺少了一般代表性而无法较好的用对新数据做分类预测，出现”过度拟合,”,。,移去对树的精度影响不大的划分。使用 成本复杂度方法，即同时度量错分风险和树的复杂程度，使二者越小越好。,剪枝方式：,A、预修剪（prepruning）：停止生长策略,B、后修剪（postpruning）：在允许决策树得到最充分生长的基础上，再根据一定的规则，自下而上逐层进行剪枝。,优点,（1）可自动忽略对目标变量没有贡献的属性变量，也为判断属性变量的重要性，减少变量数据提供参考；,（2）在面对诸如存在缺失值、变量数多等问题时C&RT 显得非常稳健（robust）；,（3）估计模型通常不用花费很长的训练时间；,（4）,推理过程完全依据属性变量的取值特点（与 C5.0不同，C&RT的输出字段既可以是数值型，也可以是分类型）,（5）比其他模型更易于理解从模型中得到的规则能得到非常直观的解释，决策推理过程可以表示成 IFTHEN的形式,（6）目标是定类变量为分类树，若目标变量是定距变量，则为回归树；,（7）通过检测输入字段，通过度量各个划分产生的异质性的减小程度，找到最佳的一个划分。,（8）非常灵活，可以允许有部分错分成本，还可指定先验概率分布，可使用自动的成本复杂性剪枝来得到归纳性更强的树,三、朴素贝叶斯,机器学习的任务：在给定训练数据D时，确定假设空间H中的最佳假设。,最佳假设：一种方法是把它定义为在给定数据D以及H中不同假设的先验概率的有关知识下的最可能假设。贝叶斯理论提供了一种计算假设概率的方法，基于假设的先验概率、给定假设下观察到不同数据的概率以及观察到的数据本身。,主要应用在电子邮件过滤和文本分类的研究,朴素贝叶斯算法原理：,四、KNN,K-,近邻分类算法（,K Nearest Neighbors,，简称,KNN,）通过计算每个训练数据到待分类元组的距离，取和待分类元组距离最近的,K,个训练数据，,K,个数据中哪个类别的训练数据占多数，则待分类元组就属于哪个类别。,K的值一般选取为,q(q为训练元组的数目，商业算法通常以10作为默认值),尽管近邻法有其优良品质，但是它的一个严重弱点与问题是需要存储全部训练样本，以及繁重的距离计算量。但以简单的方式降低样本数量，只能使其性能降低，这也是不希望的。,该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。,五、SVM,SVM的主要思想可以概括为两点：,(1)它是针对线性可分情况进行分析，对于线性不可分的情况，通过使用非线性映射算法将低维输入空间线性不可分的样本转化为高维特征空间使其线性可分，从而使得高维特征空间采用线性算法对样本的非线性特征进行线性分析成为可能；,(2)它基于结构风险最小化理论之上在特征空间中建构最优分割超平面，使得学习器得到全局最优化,并且在整个样本空间的期望风险以某个概率满足一定上界。,SVM,的应用主要于模式识别领域,:,手写数字识别,、,语音识别,、,人脸识别,、,文本分类,如何针对不同的问题选择不同的核函数仍然是一个悬而未决的问题。标准的,SVM,对噪声是不具有鲁棒性的,。,六、AdaBoost,Adaboost是一种迭代算法，其核心思想是针对同一个训练集训练不同的分类器（弱分类器），然后把这些弱分类器集合起来，构成一个更强的最终分类器（强分类器）。,Adaboost算法本身是通过改变数据分布来实现的，它根据每次训练集之中每个样本的分类是否正确，以及上次的总体分类的准确率，来确定每个样本的权值。将修改过权值的新数据集送给下层分类器进行训练，最后将每次得到的分类器最后融合起来，作为最后的决策分类器。,Adaboost有很多优点:,1)adaboost是一种有很高精度的分类器,2)可以使用各种方法构建子分类器，adaboost算法提供的是框架,3)当使用简单分类器时，计算出的结果是可以理解的。而且弱分类器构造极其简单,4)简单，不用做特征筛选,5)不用担心overfitting,adaboost算法的一些实际可以使用的场景：,1）用于二分类或多分类的应用场景,2）用于做分类任务的baseline,3）用于特征选择（feature selection),4）Boosting框架用于对badcase的修正,七、K-means,K-means算法是很典型的基于距离的聚类算法，采用距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。该算法认为簇是由距离靠近的对象组成的，因此把得到紧凑且独立的簇作为最终目标。,K-means步骤,1 设置初始类别中心和类别数;,2 根据类别中心对数据进行类别划分;,3 重新计算当前类别划分下每类的中心;,4 在得到类别中心下继续进行类别划分;,5 如果连续两次的类别划分结果不变则停止算法；否则循环步骤25;,k,-means,算法的性能分析,主要优点：,是解决聚类问题的一种经典算法，简单、快速。,对处理大数据集，该算法是相对可伸缩和高效率的。,当结果簇是密集的而簇间区别是明显的时，它的效果较好。,主要缺点,必须事先给出,k,（要生成的簇的数目），而且对初值敏感，对于不同的初始值，可能会导致不同结果。,不适合于发现非凸面形状的簇或者大小差别很大的簇。,对于“躁声”和孤立点数据是敏感的，因为簇的中心是通过计算数据的平均值得到的，这些数据的存在会使聚类的中心发生很大的偏移。,八、EM,九、Apriori算法,Apriori,算法是一种最有影响的挖掘,布尔,关联规则频繁项集的算法。,Apriori算法使用频繁项集的先验知识，使用一种称作逐层搜索的迭代方法，k项集用于探索(k+1)项集。首先，通过扫描事务（交易）记录，找出所有的频繁1项集，该集合记做L1，然后利用L1找频繁2项集的集合L2，L2找L3，如此下去，直到不能再找到任何频繁k项集。最后再在所有的频繁集中找出强规则，即产生用户感兴趣的关联规则。,步骤,1,：发现频繁项集,频繁项集发现过程：,（,1,）扫描,（,2,）计数,（,3,）比较,（,4,）产生频繁项集,（,5,）连接、剪枝，产生候选项集,重复步骤（,1,）,（,5,）直到不能发现更大频集,步骤,2,：产生关联规则,根据前面提到的置信度的定义，关联规则的产生如下：,（,1,）对于每个频繁项集,L,，产生,L,的所有非空子集；,（,2,）对于,L,的每个非空子集,S,，如果,则输出规则“,S L,S”,。,注：,L,S,表示在项集,L,中除去,S,子集的项集。,Apriori算法可以提高数据访问效率，提升发现频繁项集的速度,局限性：,可能产生大量的候选集,可能需要重复扫描数据库,十、Pagerank,基本思想：如果网页T存在一个指向网页A的连接，则表明T的所有者认为A比较重要，从而把T的一部分重要性得分赋予A。这个重要性得分值为：PR（T）/C(T)其中PR（T）为T的PageRank值，C(T)为T的出链数，则A的PageRank值为一系列类似于T的页面重要性得分值的累加。,优点：是一个与查询无关的静态算法，所有网页的PageRank值通过离线计算获得；有效减少在线查询时的计算量，极大降低了查询响应时间。,不足：人们的查询具有主题特征，PageRank忽略了主题相关性，导致结果的相关性和主题性降低；另外，PageRank有很严重的对新网页的歧视,本次课题结束，谢谢,演讲完毕，谢谢观看！,内容总结,经典算法。K均值（K-means）。（1）有监督学习：输入数据中有导师信号，以概率函数、代数函数或人工神经网络为基函数模型，采用迭代计算方法，学习结果为函数。典型的无导师学习有发现学习、聚类、竞争学习等。全局：BN,NN,SVM,Decision Tree。增益比