基于数据的决策方法综述

基于数据的决策方法综述第35卷第6期自动化学报Vol.35,No.62009年6月ACTAAUTOMATICASINICAJune,2009基于数据的决策方法综述王红卫1祁超1魏永长1李彬1朱松1摘要现代的决策问题与传统环境相比具有两个特点,首先是系统自动化水平的提高带来的大量原始数据,另外则是由于现实决策问题的复杂性和不确定性导致的机理模型无法准确建立.面对这样的特点,传统的基于机理模型的决策方法无法得到有效应用,于是,大量的研究工作围绕基于数据的决策方法展开.本文根据决策问题的性质从三个方面综述了当前被普遍关注和应用的基于数据的决策方法:分类方法、决策分析方法和优化方法,针对各种具体方法,总结了该方法的特征、发展过程以及前景.关键词基于数据,决策,分类,决策分析,优化中图分类号TP273ReviewonData-basedDecisionMakingMethodologiesWANGHong-Wei1QIChao1WEIYong-Chang1LIBin1ZHUSong1AbstractTherearetwodistinguishingcharacteristicsformoderndecisionmakingproblemsincomparisonwiththetraditionalsituation:oneistheavailabilityoflargeamountoforiginaldataemergingwiththedevelopmentofsystemautomationtechnology;theotheristhecomplexityanduncertaintyunderlyingthereal-lifedecisionproblems,whichmakeitinfeasibletoestablishprecisemodels.Traditionalmodel-baseddecisionmakingmethodologiesareine±cientunderthiscircumstance.Therefore,anumberofresearchworkshavebeenconductedondata-baseddecisionmakingmethodologies.Thispaperreviewstheprevalentdata-baseddecisionmakingmethodologiesfromthreeaspectsbasedonthecharacteristicsoftheconsidereddecisionproblems:classi¯cationmethodology,decisionanalysismethodology,andoptimizationmethodology.Thecharacteristics,developmenthistory,andperspectivearesummarizedforeachspeci¯cmethodology.KeywordsData-based,decisionmaking,classi¯cation,decisionanalysis,optimization1978年度诺贝尔奖金获得者Simon教授指出管理就是决策,我国著名经济学家于光远先生认为管决策就是做决定.虽然决策问题和方法自古有之,然而,直到20世纪人类自然科学取得了辉煌成就,决策理论和方法才开始形成了一门真正意义上的学科.可以说,近现代的决策理论和方法是随着科学技术的进步和社会生产规模的不断扩大而逐渐发展起来的.1903年到1930年间,美国人Taylor、Gilbrech夫妇和Gantt等首先提出了科学管理,迈出了决策过程和方法的程序化与规范化的重要一步.在随后的一段时间里,人们不断追求决策的数学化和模型化,在20世纪60年代形成了一股热潮.到了70年代,人们逐渐发现,并非所有的决策问题都可以用准确的数学模型表达和求解,连Acko®这样的对运筹学做出了重大贡献的大师也在1973年的美国运筹学与系统工程学全国会议上指出收了这一点.随着计算机管理信息系统的飞速发展和广泛应用,社会经济和企业生产经营的规模和自动化水平不断提高,随之而来的是系统运作产生的大量原始数据,这些数据都是系统活动的真实记录,虽然计算机硬件技术的发展使这类数据可以被大量收集和存储,但在相应的决策过程中却往往缺乏对数据的有效统计、分析及评估,无法将这些数据转换成决策部门和企业有用的信息,为决策提供参考和支持.另一方面,由于大量的现实决策问题复杂且存在不确定性,往往无法利用传统方法建立准确的机理模型,而只能根据已知数据进行分析并决策.因此,数据的分析和利用在决策理论和方法的研究中引起了学术界的广泛关注.为了与传统的基于机理模型的决策方法相区别,我们将基于离线、在线数据的决策方法统称为基于数据的决策方法.本文综述了当前被普遍关注和应用的基于数据的决策方法,这些方法主要解决了三个方面的决策问题:1)分类问题:故障诊断、模式识别都是典型的分类问题.针对这类问题,传统的方法是通过实验设计所得到的先验信息和样本数据进行分类.但如今,分类方法需要能够有效地处理实时的涌现性的数据,决策者无法控制这些数据的产生.本文讨论的基于数据的分类方法包括决策树、支持向量机、小波分析、聚类分析和神经网络.2)决策分析问题:决策分析是人们为了达到某个目标,从一些可能的方案(途径)中进行选择的分析过程,基于数据的决策分析方法需要根据已知数据对影响决策的因素作逻辑判断与权衡,并考虑风险或不确定性.本文讨论的基于数据的决策分析方法包括统计学方法、基于推理的决策分析方法(包括证据推理和模糊推理)、数据包络分析方法、时间序列方法和基于神经网络的方法.3)优化问题:确定性的优化问题不在本文讨论的范围内.对于不确定性的优化问题,传统的随机规划方法是在假设随机变量概率分布已知的情况下,对问题进行建模和求解.但现实问题并非如此理想.一种现实情况是,不确定性无法用概率分布表示,另一种情况是由于问题的复杂性和不确定性导致机理模型无法准确建立,因此需要基于数据的优化方法对这类问题进行分析.本文讨论的基于数据的优化方法包括鲁棒优化、模糊规划、神经元动态规划和基于神经网络的优化方法.1基于数据的分类方法现实生活中存在大量的分类问题,如机械故障诊断、医学诊断、语音识别、人脸识别、信用评估、文本分类、网络入侵检测、图像识别等.从算法的角度上去看,如何处理大量的非线性数据,如何提高分类算法的泛化能力,及如何对各类不同数据设计有效分类方法等问题亟待解决.从应用角度来看,目前,我们面临的观测数据与传统意义上的数据集合并不一样.过去,数据一般是通过精心设计的试验,再仔细筛选,这些数据往往在统计上满足一定的条件,而现在,我们获得的数据是涌现性的,如网络数据、生物数据和经济金融数据,人们不能有效地控制这些数据的产生.于是,如何有效利用数据成为研究的关键所在.用于分类的方法既有传统方法,包括通过先验信息和样本数据来获得对未知样本进行估计的贝叶斯方法,也包括决策树、支持向量机、小波分析、聚类分析、神经网络、粗糙分类、模糊分类等现代方法,这些方法在数据挖掘、模式识别等领域得到了广泛的应用.1.1决策树决策树最初的研究是在决策理论与统计领域,然而人们却发现了它在数据挖掘、机器学习等学科非常有用.决策树不仅能对数据进行分类,同时也指出了分类的依据.由于样本数据的复杂性,构造决策树是这一方法的核心问题,也是NP难问题.早期的决策树构建算法有ID3算法[1],但该算法不能处理连续属性,且没有解决过学习问题.随后针对测试属性以及阈值等问题,出现了C4.5[2]、EC4.5[3]等算法.这些算法的一个共同缺点是不能处理大规模的数据.文献[4¡6]针对这一问题提出了各自的方法.IBM研究人员也提出了一种快速、可伸缩、适合处理较大规模数据的决策树分类算法[7].人们通常希望决策树能像神经网络一样具备强大的学习功能,随着新的样本数据的加入,决策树也应当相应地更新,为此,提出了增量决策树的概念以及相应的算法[8¡9].此外,不同的算法产生的决策树其性能指标也必将是不同的.训练误差是最直接的性能指标,树的简单性、鲁棒性、可解释性也是很重要的性能指标.最佳性能指标是引起广大学者争议的问题,但是对各种性能指标的综合却缺乏应有的关注.从应用领域来看,决策树主要集中于遥感[10]、模式识别[11¡13]、医疗诊断[14¡15]等应用领域.目前,决策树的主要研究方向有以下几点:1)决策树与神经网络技术、模糊集合以及进化算法的结合;2)寻找新的构造决策树的方法以及更好的简化决策树的方法;3)研究产生决策树的训练和检验数据的大小特性与决策树之间的关系;4)决策树的相关复杂性度量,以及处理时间复杂性和分类准确性的矛盾的问题;5)决策树的软件技术实现.1.2支持向量机支持向量机(Supportvectormachine,SVM)是一种基于统计学习理论的预测分类方法.Vap-nik早在60年代就开始了统计学习理论的研究[16].1971年提出了SVM的一个重要理论基础VC维理论[17].以此为基础,后续的研究工作中又进一步提出了结构风险最小原理、最优边界分类器[18],讨论了非线性最优边界的分类问题[19],完整地提出了SVM的分类[20],详细介绍了基于SVM的回归算法和信号处理方法[21].支持向量机通过结构风险最小原理解决了过学习问题.对于线性不可分的样本,通过引入核技术,将实际问题通过非线性变换转换到高维特征空间,并在高维特征空间中构造线性判别函数来实现输入空间中的非线性判别函数,同时巧妙地解决了维数问题.由于SVM坚实的理论基础,良好的泛化性能,并可以有效解决非线性和维数灾难等难题,使得SVM在字符识别[22]、时间序列分析[23¡27]、图像处理和计算机视觉[28¡32]、控制系统[33¡35]以及其他方面[36¡39]得到了广泛的应用.从未来的研究发展来看,支持向量机仍然面临以下几个问题:1)参数和阈值的选择与计算;2)现有的核函数一般是针对具体的分类问题,需要构造更加有效、更加适应样本的核函数;3)求解支持向量机所提出的二次规划问题,对于大数据量的模式分类或回归逼近问题缺乏快速有效的算法.1.3小波分析小波变换是时间(空间)频率的局部化分析,它通过伸缩平移运算对信号(函数)逐步进行多尺度细化,最终达到高频处时间细分,低频处频率细分,能自动适应时频信号分析的要求,从而可聚焦到信号的任意细节,解决了傅里叶变换的困难问题,成为继傅里叶变换以来在科学方法上的重大突破,被称为\数学显微镜.小波分析是建立在小波变换基础上的分析学,特别适用于非稳定信号的问题.1984年法国地球物理学家Morlet在分析地震数据时提出小波变换.随后.他与Grossmann共同进行研究,发展了连续小波变换的几何体系,由此能将任意一个信号分解成对空间和尺度的贡献.到1988年,Daubecies将小波分析的理论发展与实际应用推向了一个高潮.目前,小波变换作为一种数学理论和方法在科学技术界引起了越来越多的关注和重视.基于小波变换的小波分析技术是泛函分析、调和分析、数值分析等半个多世纪以来发展最完美的结晶.在工程应用领域,特别是在信号处理、图像处理、模式识别、语音识别、量子物理、地震勘测、流体力学、电磁场、CT成像、机器视觉、机械故障诊断与监控、分形、数值计算等领域,被认为是近年来在工具及方法上的重大突破.另外,小波分析还被成功应用于金融领域[40]、水文水资源学科、大量数据的滤波处理和综合分析[41]以及离散小波变换(主要是Haar离散小波变换)在管理决策支持方面的应用[42].1.4聚类分析聚类分析是研究分类问题的一种统计分析方法.在聚类分析中一般事先并不知道或无需明确应该分成几类,完全根据数据来确定,适用于对事物类别的面貌尚不清楚,甚至在事前连总共有几类都不能确定的情况下进行分类的情况.聚类分析实质上是寻找一种能客观反映元素之间亲疏关系的统