文档介绍：(numericaldata)例:{,,}模式间可以计算距离度量基于度量的模式分类方法标称数据(nominaldata)例:{红色,有光泽,甜,小}模式间没有距离的概念非度量方法决策树什么是决策树?决策树是一种类似流程图的树形结构,每个内部节点表示一个测试(查询),该节点的每个分支表示该测试的一个结果,每个叶节点表示一个类别决策树的构成根节点(root)分支(branch)叶节点(leaf)决策树决策树决策树分类过程从根节点开始,首先对某一属性的取值提问Color?与根节点相连的不同分支,对应这个属性的不同取值green;yellow;red;根据不同的回答,转向相应的分支green在新到达的节点处做同样的分支判断Size?–,直到到达某个叶节点,输出该叶节点的类别标记Watermelon决策树决策树的判决面决策树决策树的优势语义可表示性从根节点到叶节点表示为合取式(颜色=黄)AND(形状=细长)香蕉利用合取式和析取式获得某个类别的明确描述苹果=(绿色AND中等大小)OR(红色AND中等大小)分类速度快只需一系列简单查询即可对模式的类别做出判断可以很自然的嵌入专家的先验知识决策树学****算法决策树研究历史第一个决策树算法称为CLS(ConceptLearningSystem) [,,’sbook“ExperimentsinInduction”publishedbyAcademicPressin1966]真正引发决策树研究热潮的算法是ID3 [’spaperinabook“ExpertSystemsintheMicroElectronicAge”,publishedbyEdinburghUniversityPressin1979] [’sbook“:ProgramsforMachineLearning”anKaufmannin1993]决策树学****算法决策树研究历史通用的决策树算法CART(ClassificationandRegressionTree) [,,,’sbook“ClassificationandRegressionTrees”publishedbyWadsworthin1984]基于决策树的集成学****算法:随机森林(RandomForests) [’sMLJ’01paper“RandomForests”]构造决策树基本过程从上到下,分而治之(divide-and-conquer),递归生长最初,所有的样本都在根节点所有属性都是标称型的(如果是连续数值型的,则需要预先离散化)所有样本根据每次选择出的属性递归的逐渐划分开来选择出来的属性称为一个划分(split)或测试(test)或查询 (query)查询的选择基于启发式或者统计特征