多类分类问题是机器学习的一个重要研究领域,然而对其直接求解在很多情况下并不能达到很好的性能。因此,将多类问题分解成若干两类问题求解是一种简单通用的策略。纠错输出码(Error Correcting Output Codes,ECOC)是一个将多类问题分解为若干两类问题的通用框架。ECOC通常分为两个步骤:编码和解码。本文立足于编码,考虑到传统的编码方法独立于数据的缺点,提出了基于最大间隔树的纠错输出码。在此基础上,进一步考虑到编码矩阵中两类问题的可分性对整体分类性能的影响,提出了基于子类的最大间隔树纠错输出码。将其进一步推广,从ECOC整体出发,提出了基于子类的细粒度纠错输出码框架。该框架独立于编码和解码,在传统ECOC的基础上增加了子类划分和分类器选择,使得ECOC可以更好地解决复杂、线性不可分的问题。本文的工作主要体现在以下方面:(1)提出了基于最大间隔树的纠错输出码。该方法使用数据驱动的方式,通过大间隔来度量类间的可分性,指导编码矩阵地构造。因此,编码矩阵往往具有更好的表达能力,从而使ECOC获得更好的分类性能。(2)提出了基于子类的最大间隔树纠错输出码。在最大间隔树纠错输出码的基础上,进一步考虑到编码矩阵中两类问题的可分性会直接影响ECOC的分类性能。该方法通过聚类算法将原本复杂的类别划分为细粒度子类,以期使得在数据驱动下的细粒度子类更加容易构建出简单、线性可分的两类问题。(3)提出了基于子类的细粒度纠错输出码框架。在基于子类的最大间隔树纠错输出码基础上,从ECOC整体出发,增加了独立于编码和解码的子类划分和分类器选择步骤。在编码前,通过聚类算法将原本复杂的类别划分为细粒度子类,以期更好地解决复杂、线性不可分的问题。在解码前,自动选出最具代表性的分类器,不但可以降低模型的复杂程度,还能有效地提升分类性能。