分类树中C&RT算法与判别分析的比较及其医学应用

来源:岁月联盟 作者:张超 时间:2010-07-12

【摘要】    目的:探讨分类树中C&RT算法和判别分析在数据分析应用中的区别。方法:首先介绍模型的基本原理,据此对方法间的优缺点进行比较,然后采用实例进行分析介绍,并报告模型的树型图,10折交叉验证的预测准确率。结果:C&RT 算法是非参数、非线性的,对变量不同属性的适应是非常灵活地;C&RT在构造树模型时是单变量拆分和递归的,故能够明显细分危险因素。结论:C&RT 算法和判别分析模型各有优势,根据数据特点及专业背景合理分析与解释,将能保证分析的正确性和完善性。

【关键词】  C&RT 算法 线性判别分析 交叉验证 错分率

  在分类方法中传统的判别分析是最常用的,其核心思想是,先根据某些类别归属已知的对象建立判别函数,再将要进行分类的相应指标值带入此判别函数,根据所得函数值判断该对象所应归入的类别。对于常用的线性判别分析,如Bayes判别、典则判别、逐步判别分析要求原始变量在各组内具有近似正态分布,同时具有相同的协方差矩阵等条件,而实际中很多数据不能满足其算法条件,使其统计结果误差偏大。再者对于二次判别函数和非参数判别分析,由于其复杂,较少有教科书涉及,使其在应用中受到限制。而分类树C&RT算法作为数据挖掘中重要的分析方法,由于其算法是非参数,非线性的,加之其判别准则以图形化结果呈现,结果易于表述与解释,该法可以作为传统判别分析的补充,因而受到统计分析人员的青睐。本研究将两者作以初步比较与探讨,以便为数据分析提供理论依据。
 
  1  原理与方法
   
  C&RT算法简介[1~3]:分类与回归树CART(Classification and Regression Trees)由最早由Breiman等人于1984提出,Ripley在1996年进行了修改。变量分为预测变量(predict variable)和应变量(dependent variable),该模型使用二叉树将预测空间递归地划分为若干子集,而树中的叶节点对应着划分的不同区域,划分是由与每个内部节点相关的分支规则(Splitting Rules)来确定的,通过从树根到叶节点移动,一个预测样本被赋予一个惟一的叶节点,应变量在该节点上的条件分布也即被确定。C&RT算法包含3部分内容:分枝变量及拆分点的选择、树的修剪和模型树的评估。

  1.1  分枝变量及拆分点的选择
   
  分类树理想的结果是使得树中每一个叶节点要么是纯节点(节点内部样本的应变量属于同一个类),要么很小(节点内部所含样本个数小于事先给定的n值)。在从众多的预测变量中选择这个最佳分组变量时,C&RT算法采用基尼系数来进行评判。基尼系数越小,表明该节点越纯,则该预测变量就是当前属性的最优分割点。对基尼系数的介绍可有关。在对样本集进行分割时,分割规则采用二叉表示形式,算法从根结点开始分割,递归地对每个结点重复进行。

  1.2  树的修剪(Pruning)
   
  由于数据中有噪声和孤立点,许多分枝反映的是训练数据中的异常。C&RT采取的是后剪枝(postpruning)方法,剪去不可靠的分枝,以提高树正确的分类能力。C&RT采用CART系统的成本-复杂度最小(Minimal cost-complexity pruning)原则进行删减。

  1.3  评估树模型  
   
  C&RT法采用测试样本评估(Test Sample Estimates)、交叉验证评估(Cross-validation Estimates)或V-折交叉验证(V-fold cross-validation),使得最终的模型树分类误判率低且树模型简单。对于最终模型树大小的选择要结合资料的专业背景及统计结果来选择。

  2  C&RT与判别分析比较[4~6]

  2.1  C&RT方法是非参数非线性的
   
  线性判别分析要求原始变量在各组内具有近似正态分布,同时具有相同的协方差矩阵等条件,而现实中很多数据不能满足其算法条件,使其统计结果误差偏大。再者对于二次判别函数和非参数判别分析计算复杂, 即使SAS、SPSS等大型统计软件对判别分析呈二次判别方程时,也没有直接输出方程的结果。故由于其操作和结果的解释较为复杂,使其推广应用受到一定的限制,所以分类树方法可以进行弥补。

  2.2  应变量属性的灵活性 
  
  C&RT分类树法中应变量即可以是连续性数值变量(continuous predictors),也可为分类变量(categorical)。如果应变量为连续性变量,C&RT树为回归树,如果应变量为分类变量时,C&RT为分类树。而判别分析要求应变量为分类属性。

  2.3  预测变量属性的灵活性 
   
  分类树中的预测变量可以是连续性数值变量,也可为分类变量(categorical)。线性判别分析要求预测变量为计量(interval scale)。当在应用判别分析时预测变量为分类属性时,常将其设置为哑变量的形式参与计算,其实质在降低其正态性的要求。而分类树方法无此要求,故在预测变量的要求上是宽松的。
   
  分类树以树形图或一组if-then语句形式描述,判别分析用一组线性方程组表述,两者相比,C&RT结果易于表达和解释。

  2.4  C&RT算法在构造树模型时是单变量拆分、递归的
   
  判别分析的目的是建立判别方程,以便用来判断某一条新观测所属的类别。不同方法有其核心思想,对于典则判别分析目的是寻找一组数值型变量的线性组合,使其能够很好地反映各类别之间的差别;而逐步判别目的在于筛选出某些能最好地反映类别间差别的变量。所以当预测变量与应变量之间有较强的相关关系或者预测变量在应变量各属性上有统计学差异时,所构造的判别方程模型较好,然而对应变量与预测变量不呈上述关系时,判别方程显得无能为力;而C&RT算法是单变量、递归式拆分,即先在一个变量(A)上将全部观察单位进行回归,而后在去除第一步分层的观察单位后在第二个变量(B)上再进行回归,从而构成模型树,这正是C&RT算法的优势。在回归的运用上,分类树的危险因素是呈树枝状分布的,而判别分析是同时考虑所有观察单位和所有变量,同时进行回归,两者相比,分类树的分层结果使得观察单位的特征更加明显。总之,分类树与判别分析的本质区别在于它是递归的、分层的。

  3  分析实例
   
  通过下面的实例数据来说明C&RT方法的应用,数据来源于我校附属,采用SPSS公司AnswerTree3.0进行分析 [7]。该实例的目的为研究腮腺良恶性肿瘤在临床体症及CT影像上的差别,所有病例经过病确诊,其中腮腺良、恶性肿瘤分别为65、33例。收集临床上认为重要的特征指标,依次有性别、年龄、位置(浅叶、深叶、同时受累)、肿瘤的最大径(cm)、平扫密度、颈部淋巴结肿大与否、边界状态(清、不清)、CT增强幅度。将良、恶性肿瘤属性作为应变量,其余属性作为预测变量,其中年龄、肿瘤的最大径、增强幅度为连续性计量数据,其余为分类计数数据。由于本例样本量较小,采用10折交叉验证对模型进行评估其误差率。此处简要报告C&RT方法的主要分析结果,表1为C&RT模型的预测分类与实际分类结果,图1为树形图。该决策树图为采用C&RT方法进行的分类结果,由模型树图可得出以下结论:恶性肿瘤大多伴有淋巴结肿大、肿瘤直径大、边界不清、CT增强幅度大再检测的特征。

  表1  C&RT模型的预测分类与实际分类结果(略)

  经10折交叉验证,估计误差(Risk Estimate)及其标准误(SE of Risk Estimate)分别为0.918、0.029,模型的正确率近91%。
   
  将该资料采用Bayes线性判别分析,得判别函数为:
   
  Z1=-37.009+27.635X1+8.501X2+1.842X3+0.226X4
   
  Z2=-38.286+20.648X1+12.823X2+2.632X3+0.339X4
   
  公式中Z1、Z2分别代表良、恶性;X1为是否伴有淋巴结肿大, X2边界是否清晰, X3肿瘤最大径, X4为CT的增强幅度。采用交叉验证模型的准确率为89.2%。由于本资料数据量小,变量间的关系简单,两种模型的分析结果基本一致。相比于判别分析,C&RT方法的树型分类结果直观且宜于解释,由于分类树算法仅就节点处自身的数据进行分析,故在进行"危险因素"分析时,分类树结果更能强调危险因素,故从根节点到叶节点可明显区分恶性肿瘤与良性肿瘤的特征,即恶性肿瘤大多伴有淋巴结肿大、肿瘤直径大、边界不清,CT增强幅度大一些时可清晰确诊。该模型对实际的临床诊断有一定的指导意义。

  图1  腮腺良恶性肿瘤临床体症的C&RT模型树(略)

  4  讨论
   
  目前数据挖掘中有关分类树的算法非常多,SPSS13.0及AnswerTree软件主要提供有C&RT、CHAID 和QUEST 3种算法[8,9]。CHAID 算法以Pearson 卡方或似然比卡方检验为基础, 使用P 值对众多自变量进行比较并筛选出最佳分类变量和最佳分类结果,该算法更适于处理分类属性的变量,对于连续性变量需将其转化为分类变量再进行分析,因此会损失部分信息。QUEST 算法在思路上类似于CHIAD 算法,对连续或有序变量采用方差分析进行检验,而后又采用方差齐性检验进一步发掘变异程度上的差异, 弥补了CHAID方法的不足。C &RT 算法采用杂质缩减最大化为其基本思路,当应变量为分类属性时模型树为分类树,当应变量为连续性属性时,模型树为回归树。3种算法的应变量都可以为nominal、ordinal、continuous 3种类型,不同之处是QUEST、C &RT树模型为二叉树。
   
  对于常用线性判别分析要求原始变量在各组内具有近似正态分布,同时具有相同的协方差矩阵等条件,当自变量与应变量间呈线性关系时,采用线性判别分析会更为准确与合理。而分类树算法是非参数、非线性的,如果自变量与应变量间呈非线性关系,或自变量间有交互作用,采用二次判别函数和非参数判别分析,复杂,结果难以解释,而分类树方法可以弥补判别分析这一缺陷。判别分析构造模型时是针对所有数据的,而分类树算法仅就节点处自身的数据进行分析,故在进行危险因素分析时,分类树结果更能强调危险因素。判别分析与分类树分析各自有其优势,实际分析时结合数据自身特点与专业背景,选择恰当的方法,合理地解释结果。

【】
    1 毛国君,段立娟,王实,等.数据挖掘原理与算法. 清华大学出版社,2005,75~56.

  2 章兢, 张小刚. 数据挖掘算法及其工程应用.机械出版社,2006,40~60.

  3 Breiman L,Friedman JH,etal.Classification and regression tresss. Bel-mont, California:Wadsworth, 1984.

  4 http://www.statsoft.com/textbook/stcart.html#formulas.

  5 A classification of delivery patient groups using CART (Classification and Regression Trees) for an improvement of critical path. Stud Health Technol Inform, 2006,122:913.

  6 Application of data mining techniques to healthcare data. Infect Control Hosp Epidemiol, 2004, 25(8):690~695.

  7 SPSS Inc. AnswerTree 3. 0 User's Guide. Chicago, Illinois, SPSS Inc, 2001,7.

  8 张超,陈平雁,张小远. CHAID方法及其在高校教师职业倦怠感影响因素分析中的应用. 第一军医大学学报,2003,23(12):1352~1354.
  9 张超,陈平雁. 决策统计软件AnswerTree简介.卫生统计,2003,20(3):188.