分类和预测

分类和预测分类VS.预测分类：预测分类标号（或离散值）根据训练数据集和类标号属性，构建模型来分类现有数据，并用来分类新数据预测：建立连续函数值模型，比如预测空缺值典型应用信誉证实目标市场医疗诊断性能预测数据分类——一个两步过程(1)第一步，建立一个模型，描述预定数据类集和概念集假定每个元组属于一个预定义的类，由一个类标号属性确定基本概念训练数据集：由为建立模型而被分析的数据元组形成训练样本：训练数据集中的单个样本（元组）学习模型可以用分类规则、判定树或数学公式的形式提供数据分类——一个两步过程(2)第二步，使用模型，对将来的或未知的对象进行分类首先评估模型的预测准确率对每个测试样本，将已知的类标号和该样本的学习模型类预测比较模型在给定测试集上的准确率是正确被模型分类的测试样本的百分比测试集要独立于训练样本集，否则会出现“过分适应数据”的情况第一步——建立模型训练数据集NAMERANKYEARSTENUREDMikeAssistantProf3noMaryAssistantProf7yesBillProfessor2yesJimAssociateProf7yesDaveAssistantProf6noAnneAssociateProf3no分类算法IFrank=‘professor’ORyears6THENtenured=‘yes’分类规则第二步——用模型进行分类分类规则测试集NAMERANKYEARSTENUREDTomAssistantProf2noMerlisaAssociateProf7noGeorgeProfessor5yesJosephAssistantProf7yes未知数据(Jeff,Professor,4)Tenured?有指导的学习VS.无指导的学习有指导的学习（用于分类）模型的学习在被告知每个训练样本属于哪个类的“指导”下进行新数据使用训练数据集中得到的规则进行分类无指导的学习（用于聚类）每个训练样本的类编号是未知的，要学习的类集合或数量也可能是事先未知的通过一系列的度量、观察来建立数据中的类编号或进行聚类准备分类和预测的数据通过对数据进行预处理，可以提高分类和预测过程的准确性、有效性和可伸缩性数据清理消除或减少噪声，处理空缺值，从而减少学习时的混乱相关性分析数据中的有些属性可能与当前任务不相关；也有些属性可能是冗余的；删除这些属性可以加快学习步骤，使学习结果更精确数据变换可以将数据概化到较高层概念，或将数据进行规范化比较分类方法使用下列标准比较分类和预测方法预测的准确率：模型正确预测新数据的类编号的能力速度：产生和使用模型的计算花销健壮性：给定噪声数据或有空缺值的数据，模型正确预测的能力可伸缩性：对大量数据，有效的构建模型的能力可解释性：学习模型提供的理解和洞察的层次用判定树归纳分类什么是判定树？类似于流程图的树结构每个内部节点表示在一个属性上的测试每个分枝代表一个测试输出每个树叶节点代表类或类分布判定树的生成由两个阶段组成判定树构建开始时，所有的训练样本都在根节点递归的通过选定的属性，来划分样本（必须是离散值）树剪枝许多分枝反映的是训练数据中的噪声和孤立点，树剪枝试图检测和剪去这种分枝判定树的使用：对未知样本进行分类通过将样本的属性值与判定树相比较ageincomestudentcredit_ratingbuys_computer=30highnofairno=30highnoexcellentno31…40highnofairyes40mediumnofairyes40lowyesfairyes40lowyesexcellentno31…40lowyesexcellentyes=30mediumnofairno=30lowyesfairyes40mediumyesfairyes=30mediumyesexcellentyes31…40mediumnoexcellentyes31…40highyesfairyes40mediumnoexcellentno概念“buys_computer”的判定树age?overcaststudent?creditrating?noyesfairexcellent=3040nonoyesyesyes30..40判定归纳树算法判定归纳树算法（一个贪心算法）自顶向下的分治方式构造判定树树以代表训练样本的单个根节点开始使用分类属性（如果是量化属性，则需先进行离散化）递归的通过选择相应的测试属性，来划分样本，一旦一个属性出现在一个节点上，就不在该节点的任何后代上出现测试属性是根据某种启发信息或者是统计信息来进行选择（如：信息增益）在树的每个节点上使用信息增益度量选择测试属性；选择具有最高信息增益（或最大熵压缩）的属性作为当前节点的测试属性。（即根据当前节点对应的训练样本，计算各属性的信息增益，然后选用具有最高信息增益的属性来做样本划分）判定树归纳策略(1)1.树以代表训练样本的单个节点开始2.如果样本都在同一个类，则该节点成为树叶，并用该类标记3.否则，算法使用基于熵的度量——信息增益作为指导信息，选择能够最好的将样本分类的属性；该属性成为节点的“测试”或“判定”属性。（使用分类属性）4.对测试属性每个已知的值，创建一个分支，并以此划分样本判定树归纳策略(2)5.算法使用同样的过程，递归的形成每个划分上的样本判定树。一旦一个属性出现在一个节点上，就不在该节点的任何子节点上出现6.递归划分步骤停止的条件给定节点的所有样本属于同一类没有剩余属性可以用来进一步划分样本——使用多数表决没有剩余的样本ageincomestudentcredit_ratingbuys_computer=30highnofairno=30highnoexcellentno31…40highnofairyes40mediumnofairyes40lowyesfairyes40lowyesexcellentno31…40lowyesexcellentyes=30mediumnofairno=30lowyesfairyes40mediumyesfairyes=30mediumyesexcellentyes31…40mediumnoexcellentyes31…40highyesfairyes40mediumnoexcellentno判定归纳树算法示例(1)对于上述数据，可以略过步骤1，2步骤3，计算基于熵的度量——信息增益，作为样本划分的根据Gain(age)=0.246Gain(income)=0.029Gain(student)=0.151Gain(credit_rating)=0.048然后，对测试属性每个已知的值，创建一个分支，并以此划分样本，得到第一次划分判定归纳树算法示例(2)判定归纳树算法示例(3)age?overcaststudent?creditrating?noyesfairexcellent=3040nonoyesyesyes30..40防止分类中的过分适应产生的判定树会出现过分适应数据的问题由于数据中的噪声和孤立点，许多分枝反应的是训练数据中的异常对新样本的判定很不精确防止过分适应的两种方法先剪枝：通过提前停止树的构造——如果在一个节点划分样本将导致低于预定义临界值的分裂（e.g.使用信息增益度量）选择一个合适的临界值往往很困难后剪枝：由“完全生长”的树剪去分枝——对于树中的每个非树叶节点，计算该节点上的子树被剪枝可能出现的期望错误率使用一个独立的测试集来评估每颗树的准确率，就能得到具有最小期望错误率的判定树由判定树提取分类规则可以提取判定树表示的知识，并以IF-THEN形式的分类规则表示对从根到树叶的每条路径创建一个规则沿着给定路径上的每个属性-值对形成规则前件（IF部分）的一个合取项叶节点包含类预测，形成规则后件（THEN部分）IF-THEN规则易于理解，尤其树很大时示例：IFage=“=30”ANDstudent=“no”THENbuys_computer=“no”IFage=“=30”ANDstudent=“yes”THENbuys_computer=“yes”IFage=“31…40”THENbuys_computer=“yes”IFage=“40”ANDcredit_rating=“excellent”THENbuys_computer=“yes”IFage=“40”ANDcredit_rating=“fair”THENbuys_computer=“no”基本判定树归纳的加强修改算法，允许属性具有整个离散区间或连续值动态的定义新的离散值属性，将连续值属性划分到多个离散的间隔中处理空缺的属性值属性A的空缺值或未知值可以用A的最常见值替换使用A的最可能值替换，或使用A和其他属性的已知联系属性构造通过由给定的属性创建新的属性，改进给定属性的受限表示可以防止或减轻碎片、重复或复制问题大型数据库的分类挖掘——可伸缩性分类挖掘是一个在统计学和机器学习的领域也被广为研究的问题，并提出了很多算法，但是这些算法都是内存驻留的可伸缩性问题：要求以合理的速度对数以百万计的样本和数以百计的属性的进行分类挖掘由大型数据库构造判定树首先将样本划分为子集，每个子集可以放在内存中然后由每个自己构造一颗判定树输出的分类法将每个子集的分类法组合在一起（其他方法包括SLIQ,SPRINT,RainForest等等）集成数据仓库技术和判定树归纳将判定树归纳与多维数据立方体和面向属性的归纳(AOI)相集成，可以进行交互的多层挖掘数据立方体与判定树归纳存放在概念分层中的知识可以用在不同的抽象层归纳判定树对导出的判定树，可以进一步在属性上进行上卷或下钻，以概化或特化树节点；使用户将注意力集中于感兴趣的树区域AOI与判定树归纳利用属性上的概念分层，以高层概念替换低层概念概化训练数据应当概化到由领域专家或用户设定的某个中间值，防止概化过低或者是过分概化对判定树中，由于递归划分，使得某些数据子集太小而失去统计意义的情况，可以通过引入相应的临界值，控制子集的划分贝叶斯分类贝叶斯分类利用统计学中的贝叶斯定理，来预测类成员的概率，即给定一个样本，计算该样本属于一个特定的类的概率。朴素贝叶斯分类：假设每个属性之间都是相互独立的，并且每个属性对非类问题产生的影响都是一样的。)()()|()|(DPhPhDPDhP后向传播分类后向传播是一种神经网络学习算法；神经网络是一组连接的输入/输出单元，每个连接都与一个权相连。在学习阶段，通过调整神经网络的权，使得能够预测输入样本的正确标号来学习。优点预测精度总的来说较高健壮性好，训练样本中包含错误时也可正常工作输出可能是离散值、连续值或者是离散或量化属性的向量值对目标进行分类较快缺点训练（学习）时间长蕴涵在学习的权中的符号含义很难理解很难根专业领域知识相整合其他分类方法k-最临近分类给定一个未知样本，k-最临近分类法搜索模式空间，找出最接近未知样本的k个训练样本；然后使用k个最临近者中最公共的类来预测当前样本的类标号基于案例的推理样本或案例使用复杂的符号表示，对于新案例，先检测是否存在同样的训练案例；如果找不到，则搜索类似的训练案例遗传算法结合生物进化思想的算法粗糙集方法模糊集方法允许在分类规则中定义“模糊的”临界值或边界什么是预测？预测是构造和使用模型评估无样本类，或评估给定样本可能具有的属性或值空间。预测和分类的异同相同点两者都需要构建模型都用模型来估计未知值预测当中主要的估计方法是回归分析线性回归和多元回归非线性回归不同点分类法主要是用来预测类标号（分类属性值）预测法主要是用来估计连续值（量化属性值）线性回归、多元回归和非线性回归线性