机器学习经典算法.pptx

机器学习十大经典算法C45分类与回归树朴素贝叶斯支持向量机（SVM)K近邻（KNN）AdaBoostK均值（Kmeans）最大期望（EM）Apriori算法Pagerank

机器学习方法的分类基于学习方式的分类（1）有监督学习：输入数据中有导师信号，以概率函数代数函数或人工神经网络为基函数模型，采用迭代计算方法，学习结果为函数。（2）无监督学习：输入数据中无导师信号，采用聚类方法，学习结果为类别。典型的无导师学习有发现学习聚类竞争学习等。（3）强化学习（增强学习）：以环境反馈（奖/惩信号）作为输入，以统计和动态规划技术为指导的一种学习方法。

有监督学习（用于分类）标定的训练数据训练过程：根据目标输出与实际输出的误差信号来调节参数典型方法全局：BN,NN,SVM,DecisionTree局部：KNNCBR(Casebasereasoning)S(x)=0ClassAS(x)0ClassBS(x)=0ObjectsX2(area)(perimeter)X1ObjectFeatureRepresentation

无监督学习（用于聚类）不存在标定的训练数据学习机根据外部数据的统计规律（egCohensiondivergence）来调节系统参数，以使输出能反映数据的某种特性。典型方法KmeansSOM…示例：聚类

半监督学习结合（少量的）标定训练数据和（大量的）未标定数据来进行学习典型方法CotrainingEMLatentvariables…

一C45C45由JRossQuinlan在ID3的基础上提出的。ID3算法用来构造决策树。决策树是一种类似流程图的树结构，其中每个内部节点（非树叶节点）表示在一个属性上的测试，每个分枝代表一个测试输出，而每个树叶节点存放一个类标号。一旦建立好了决策树，对于一个未给定类标号的元组，跟踪一条有根节点到叶节点的路径，该叶节点就存放着该元组的预测。决策树的优势在于不需要任何领域知识或参数设置，产生的分类规则易于理解，准确率较高。适合于探测性的知识发现。缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。

增益比率度量是用增益度量Gain(S，A)和分裂信息度量SplitInformation(S，A)来共同定义的设S代表训练数据集，由s个样本组成。A是S的某个属性，有m个不同的取值，根据这些取值可以把S划分为m个子集，Si表示第i个子集（i=1,2,…,m），|Si|表示子集Si中的样本数量。

数据集如图1所示，它表示的是天气情况与去不去打高尔夫球之间的关系

二分类和回归树（ClassificationandRegressionTrees——CART，可简写为CRT）CART算法中的每一次分裂把数据分为两个子集，每个子集中的样本比被划分之前具有更好的一致性。它是一个递归的过程，也就是说，这些子集还会被继续划分，这个过程不断重复，直到满足终止准则，然后通过修剪和评估，得到一棵最优的决策树。

在ID3算法中，用“熵”来度量数据集随机性的程度。在CART中我们把这种随机性的程度称为“杂度”（impurity，也称为“不纯度”），并且用“吉尼”(gini)指标来衡量它。

决策树停止生长的条件满足以下一个即停止生长。（1）节点达到完全纯性；（2）数树的深度达到用户指定的深度；（3）节点中样本的个数少于用户指定的个数；（4）异质性指标下降的最大幅度小于用户指定的幅度。

剪枝：完整的决策树对训练样本特征的描述可能“过于精确”（受噪声数据的影响），缺少了一般代表性而无法较好的用对新数据做分类预测，出现”过度拟合”。移去对树的精度影响不大的划分。使用成本复杂度方法，即同时度量错分风险和树的复杂程度，使二者越小越好。剪枝方式：A预修剪（prepruning）：停止生长策略B后修剪（postpruning）：在允许决策树得到最充分生长的基础上，再根据一定的规则，自下而上逐层进行剪枝。

优点（1）可自动忽略对目标变量没有贡献的属性变量，也为判断属性变量的重要性，减少变量数据提供参考；（2）在面对诸如存在缺失值变量数多等问题时CRT显得非常稳健（robust）；（3）估计模型通常不用花费很长的训练时间；（4）推理过程完全依据属性变量的取值特点（与C50不同，CRT的输出字段既可以是数值型，也可以是分类型）（5）比其他模型更易于理解——从模型中得到的规则能得到非常直观的解释，决策推理过程可以表示成IF…THEN的形式（6）目标是定类变量为分类树，若目标变量是定距变量，则为回归树；（7）通过检测输入字段，通过度量各个划分产生的异质性的减小程度，找到最佳的一个划