机器学习-(新)

机器学习Machinelearning2011年春季学期机器学习简介及决策树刘扬哈工大计算机学院自然计算研究室1相关信息教材Mitchell,机器学习（必需）ChrisBishop,PatternRecognitionandMachineLearning（电子版，必需）DavidMackay,InformationTheory,Inference,andLearningAlgorithms教师刘扬[e-mail]2什么是学习？定义1：由于经验或实践的结果而发生的持久或相对持久的适应性行为变化定义2：能够使动物的行为对特定的环境条件发生适应性变化的所有过程，或者说是动物借助于个体生活经历和经验使自身的行为发生适应性变化的过程百度百科3什么是机器学习？是寻找一种对自然/人工主题、现象或活动可预测且/或可执行的机器理解方法4什么是机器学习研究计算机怎样模拟或实现人类（动物）的学习行为，以获取新的知识或技能重新组织已有的知识结构使之不断改善自身的性能是人工智能的核心，是使计算机具有智能的根本途径其应用遍及人工智能的各个领域，它主要使用归纳、综合而不是演绎5机器学习的一个形象描述6机器学习研究一种算法提高它的性能（P）在某项任务中（T）利用一些经验（E）well-definedlearningtask:P,T,E7机器学习的应用8自然语言处理/语音识别现在语音识别器或翻译器几乎都是建立在某种具有学习能力的设备上----使用的越多，则它越聪明9对象识别10机器人控制汽车自动驾驶系统11机器人控制12文本挖掘13生物信息学14进化15机器学习的一般泛型监督学习无监督学习强化学习16机器学习——理论对于学习到的函数F(;θ)一致性（Consistency，值，模式、、）偏执与方差（Biasversusvariance）采样复杂性（Samplecomplexity）学习率（learningrate）收敛性（Convergence）误差界（Errorbound）稳定性（Stability）…17机器学习机器学习是研究开发一种具有如下能力的理论和计算机系统表示分类，聚类和识别不确定条件下推理预测对外界环境的反应…可以在显示的模型或数学框架下，根据数据和自身经验，复杂的真实世界信息可以：被形式（formally）刻画和分析加入人的先验具有在数据与领域间的泛化和适应能力自动或自主操作被人类解释和感知18机器学习的快速增长机器学习是最受青睐的方法语音识别，自然语言处理计算机视觉医学处理机器人控制机器学习分量在增加机器学习性能不断提高数据快速增长，网络发展一些软件太复杂人工撰写比较困难新的感知器件/IO设备环境与用户的个性化服务19推理（Inference）预测（Prediction）不确定性环境下的决策….→统计机器学习→函数近似：𝑭(|θ)20分类镰刀形细胞贫血症函数近似21函数近似设置示例集合X未知的目标函数f：𝑋→𝑌函数假设集合H={h|h:X→𝑌}给定目标函数f的训练样本{𝑥𝑖,𝑦𝑖}确定h∈𝐻，可以最好地近似f22税务欺诈检测问题采用什么样的函数f假设空间是什么的样的如何使用？23查询数据的判别举例从根节点开始24查询数据的判别举例25查询数据的判别举例26查询数据的判别举例27查询数据的判别举例28查询数据的判别举例29税务欺诈的一个假设（决策树）输入：属性向量X=[Refund,MarSt,TaxInc]输出：Y=是否欺诈H就是不同的决策过程（不同的决策树）每一个内结点：测试一个属性Xi每个分支：选择属性Xi的一个取值每个叶结点：预测Y30决策树的表示能力决策树可以表示输入属性的任何函数例如，对于布尔函数，真值表的一行→一条路径（根到叶）如果对训练数据中的每个样例都建立一条从根到叶的路径（除非f对于输入x是不确定的）就得到一个一致的决策树，但其可能没有泛化能力因此希望找一个更加紧凑（小规模）的决策树31决策树学习32一棵决策树（欺诈问题）33另一棵决策树同样一个训练数据集，可以有多棵树与其一致34Top-Down的决策树归纳算法（构造）Mainloop：1.A←下一个结点node的最好属性2.把A作为决策属性赋给结点node3.对A的每一个取值，创建一个新的儿子结点node4.把相应的训练样本分到叶结点5.如果训练样本被很好的分类，则停止，否则在新的叶结点上重复上述过程哪个属性更好？35树的归纳贪心策略基于一个可以最优化某项准则的属性来切分示例集和问题如何切分示例集和如何确定属性的测试条件？如何确定最好的切分？停止切分准则36树的归纳贪心策略基于一个可以最优化某项准则的属性来切分示例集和问题如何切分示例集和如何确定最好的切分？如何确定属性的测试条件？停止切分准则37如何确定特测条件？依赖于属性类型名词性\离散（Nominal）有序的（Ordinal）连续（Continuous）依赖于切分的分支个数两路切分（2-way）多路切分（Multi-way）38对名词属性的切分多路切分：一个离散属性值对应一路切分两路切分：离散属性值被切分成两个子集，需要寻找最优切分39对有序属性的切分多路切分：一个属性值对应一路切分两路切分：属性值被切分成两个子集，需要寻找最优切分这个如何？40对连续属性的切分不同的处理方案离散化构造有序的类属性静态——在起始位置一次离散化动态——范围可以通过等区间或等频率确定，或者是聚类二值决策：(AV)or(A=V)考虑所有可能的切分并选择最好的计算量可能非常大41对连续属性的切分42树的归纳贪心策略基于一个可以最优化某项准则的属性来切分示例集和问题如何切分示例集和如何确定最好的切分？如何确定属性的测试条件？停止切分准则43如何确定最好的切分Idea：一个好的属性切分是将示例集合分成若干子集，最理想情况是每个子集为“皆为正例”或“皆为反例”贪心搜索更倾向结点上的数据具有同质（homogeneous）类别分布需要对结点混杂度（impurity）进行测量44如何衡量属性的“好”与“坏”熵（Entropy）随机变量𝑋的熵𝐻(𝑋)𝐻(𝑋)是对从𝑋随机采样值在最短编码情况下的每个值平均（期望）长度（以2为底就是0、1编码）𝐻𝑋=−𝑃𝑥=𝑖𝑙𝑜𝑔2𝑃(𝑥=𝑖)𝑁𝑖=1Why？信息论：在最短编码情况下，对消息𝑋=𝑖分配−log2𝑃(𝑋=𝑖)位，所以其编码一个随机变量𝑋的期望位数是𝐻𝑋=−𝑃𝑥=𝑖𝑙𝑜𝑔2𝑃(𝑥=𝑖)𝑁𝑖=145如何衡量属性的“好”与“坏”条件熵𝑋在给定𝑌=𝑣特定条件熵𝐻(𝑋|𝑌=𝑣)𝐻𝑋|𝑦=𝑗=−𝑃𝑥=𝑖|𝑦=𝑗𝑙𝑜𝑔2𝑃(𝑥=𝑖|𝑦=𝑗)𝑁𝑖=1𝑋在给定𝑌条件熵𝐻(𝑋|𝑌)𝐻𝑋|𝑌=𝑃𝑦=𝑗𝐻(𝑋|𝑦=𝑗)𝑗∈𝑉𝑎𝑙(𝑦)𝑋和Y的互信息𝐼𝑋;𝑌=𝐻𝑋−𝐻𝑋𝑌=𝐻𝑌−𝐻𝑌𝑋=𝐻𝑋+𝐻𝑌−𝐻(𝑋,𝑌)46样本熵S是训练例子的样本集P+是S中的正例比例P-是S中反例的比例用熵来测量S的混杂度47计算熵的例子48信息增益信息增益父结点P被切分成k部分；ni是每一切分的样本数即目标类变量与属性A变量在S（样本集）上的互信息测量由于切分带来的熵减少量，选择具有最大减少量的切分（最大增益）在ID3和C4.5中采用缺点：倾向选择具有切分分数多的属性，因为每份可以很少的样本，但很纯49例子选择哪个属性作为根节点？50树归纳的停止准则当一个结点上所有样本属于同一个类别，停止扩展当一个结点上所有样本具有相似的属性值，停止扩展提早结束（以后会介绍）51基于决策树的分类优点构建过程计算资源开销小分类未知样本速度极快对于小规模的树比较容易解释在许多小的简单数据集合上性能与其它方法相近例子：C4.5深度优先构建方法采用了信息增益在每一个结点需要对示例依据连续属性排序数据需要全部装入内存不适合大规模数据52应该输出哪棵树ID3在决策树空间中执行启发式搜索当获得最小可接受的决策树时则停止Why?Occam’s剃刀：选择适合训练集合数据的最简单假设53决策树的实践问题欠拟合（underfitting）和过拟合（Overfitting）特征值丢失54总结：你应当知道的适定的函数近似问题示例空间，X标注的训练样本{xi,yi}假设空间，H={f:X→Y}学习是H空间上的搜索/优化问题各种各样目标函数最小化训练误差（0-1损失）在所有的满足最小误差的假设中，选择最小的（？）决策树学习贪心的Top-down决策树过拟合以及剪枝扩展55思考问题（1）ID3和C4.5在树空间上执行启发式算法。为什么不做穷尽搜索？56思考问题（2）考虑目标函数f:x1,x2→y，这里x1和x2是实数，如果在树中每个属性只被允许使用一次，那么决策树可以表达的决策平面是什么样子的？57思考问题（3）为什么用信息增益来选择属性？有没有其他方案58假设空间大小n布尔特征有多少个决策树布尔函数函数个数=具有2n行的真值表个数=2𝑛𝑛有6个布尔属性，则有18,446,744,073,709,551,616棵树59NotesonOverfittingOverfittingresultsindecisiontreesthataremorecomplexthannecessaryTrainingerrornolongerprovidesagoodestimateofhowwellthetreewillperformonpreviouslyunseenrecordsWhichTreeShouldWeOutput?Occam’srazor:preferthesimplesthypothesisthatfitsthedata60Occam’sRazorGiventwomodelsofsimilargeneralizationerrors,oneshouldpreferthesimplermodeloverthemorecomplexmodelForcomplexmodels,thereisagreaterchancethatitwasfittedaccidentallybyerrorsindataTherefore,oneshouldincludemodelcomplexitywhenevaluatingamodel61MinimumDescriptionLength(MDL)Cost(Model,Data)=Cost(Data|Model)+Cost(Model)Costisthenumberofbitsneededforencoding.Searchfortheleastcostlymodel.Cost(Data|Model)encodesthemisclassificationerrors.Cost(Model)usesnodeencoding(numberofchildren)plussplittingconditionencoding.62HowtoAddressOverfittingPre-Pruning(EarlyStoppingRule)Stopthealgorithmbeforeitbecomesafully-growntreeTypicalstoppingconditionsforanode:StopifallinstancesbelongtothesameclassStopifalltheattributeval