从广义上讲,机器学习(Machine Learning)是以使其包括任何计算机程序通过经验来提高其任务处理性能的行为。如果机器能够真正完全地根据经验来自动提高,其影响将是空前的。为此,自从第一台电子计算机ENIAC问世以来,大批学者与专家就在为使其能够自我学习而不懈努力。到目前为止,针对特定学习任务的算法已产生[58][59],关于学习的理论认识已开始形成[60][61],其中,从特殊的训练样例中归纳出一般函数是机器学习的中心问题,而决策树学习则是应用最广的归纳推理算法之一[1][10]。决策树方法在实际中有着广泛的应用,如根据疾病分类患者[58];根据起因分类设备故障;根据拖欠支付的可能性分类贷款申请。这类问题的核心任务都是把样例分入各个可能的对应的类别中,因此称为分类问题(Classification problem)[1]。经典的分类问题是在假设为各种分类错误所要付出的代价相同的情况下,要求达到高的分类正确率。然而这种假设在实际应用中很难满足,如根据疾病分类患者问题中,将病人判断为健康者与将健康者判断为病人,这两种错误的诊断所要付出的代价一定是不相同的。针对此类问题,专家们提出了代价敏感的学习方法(Cost-sensitive Learning,CSL)。由于其在现实中广泛的应用,近年来一直是机器学习领域中的一个研究热点[20][51]。本文首先介绍了机器学习的主要研究领域,并分析了目前国内外关于代价敏感学习的理论与方法,指出现有的代价敏感学习方法的优点与不足。针对存在的问题与不足,提出了一些新方法,并通过实验证明本文所提出的方法的可行性与有效性。本文的主要内容如下(其中部分工作于参考文献[56][57][62]中发表):(1)简述决策树(Decision Tree)方法以及代价敏感学习(CSL)现有的方法,分析其优缺点。同时也介绍了与代价敏感学习密切相关的代价约束(Budget Learning)及主动学习(Active Learning)的概念和基本方法。(2)提出代价约束下的代价敏感学习的新方法。本论文改变了前人将代价敏感学习中各种代价(如获得每个实例的属性值的代价和发生错误判断时所要付出的代价)用同一代价尺度来衡量的习惯做法[20][47],取而代之用不同的代价尺度来衡量不同的代价。另外,在前人的部分