多标签学习问题广泛存在于文本分类、图像标注、信息检索、基因功能分析、医学诊断、定向营销以及电子商务中的个性化推荐等很多现实的应用中,近年来得到了大量的关注和研究。多标签学习假设一个样本可被同时标注多个标签,且不同标签之间是相互依赖的,其与传统有监督学习的主要区别在于输出空间上。多标签分类问题的主要研究集中在多标签分类方法、标签结构学习、大规模标签问题、弱标签问题以及与其他学习问题的结合等方面。论文重点探讨多标签分类问题和分类方法的形式化描述、挖掘标签关联和处理大规模标签问题的多标签分类方法。(1)针对多标签分类问题和分类方法缺少形式化描述的问题,论文第三章重点为多标签分类问题的标签空间建立图结构,并对典型的多标签分类方法进行图结构描述。论文首先基于有限布尔代数和图论在标签空间上分别建立有限偏序集的哈斯图以及超立方体,以更好地反映多标签分类问题的结构化输出的特点。并证明标签空间的哈斯图和超立方体是同构的,具有一些好的性质。然后,在标签空间的超立方体结构上,对典型的多标签分类方法进行图结构描述,从而在统一的图结构中直观地表示多标签分类方法的特点及联系。(2)在多标签分类方法的图结构描述框架下,论文提出处理多标签隐含关联和大规模标签问题的若干学习算法。①针对挖掘数据隐含关联和数据降维在多标签学习中的重要性,论文第四章探讨两个基于典型相关分析(CCA)的多标签分类算法。第一个算法ML-CCA利用CCA来挖掘样本集与标签集之间的相关性并提取样本特征;第二个算法CCA_LSDR针对大规模标签问题,通过修改CCA的优化问题,要求标签向量的映射是正交的并且使得标签解码是低损的,从而获得结合样本信息的标签降维,并在预测阶段通过正交映射解码还原预测的标签集。在6个大规模标签数据集上的数值实验表明:ML-CCA和CCA_LSDR通过挖掘样本集与标签集的相关性能够保证学习性能;且与ML-CCA相比,CCA_LSDR通过标签降维能够实现更快的预测;另外,CCA_LSDR与其他标签空间降维方法相比,具有更快的训练速度。②针对挖掘标签关联的低维嵌入方法缺少综合考虑样本特征信息和分类误差的问题,论文第五章提出基于有监督低维嵌入的联合学习框架ML-SLDE/DML-SLDE,将挖掘隐含数据关联与最小化经验风险整合到一个联合框架中,平衡数据关联学习与分类误差在分类模型中的重要性。有监督低维嵌入建立在潜在语义分析的思想之上,能够结合样本特征信息和标签信息挖掘数据的隐含语义与关联,并提取有价值的低维特征建立多标签分类模型。而分类函数的系数由所得到的低维映射直接确定。为了验证ML-SLDE/DML-SLDE的性能,对10个典型多标签数据集进行对比实验,探讨算法在分类精度、训练复杂度以及对关键参数的敏感性等方面的表现。实验结果表明,ML-SLDE/DML-SLDE能够较好处理各种不同类型的多标签数据集,相对于其他五种算法,它在多个评价指标上都取得最好或第二好的结果;同时,ML-SLDE/DML-SLDE在大部分数据集上的训练时间具有明显的优势。另外,通过敏感性分析发现,ML-SLDE/DML-SLDE对于低维子空间的维度是鲁棒的。③针对现实应用数据的增量获取方式,论文第六章讨论第五章联合框架ML-SLDE/DML-SLDE的增量学习方案,在尽量利用历史计算信息的前提下,减少增量建模的时间花费。首先直接在原算法上进行简单的增量变形,提出ML-SLDE_I和DML-SLDE_I,并在7个不同规模的数据集上验证了ML-SLDE_I在很好地保持分类性能的同时,训练速度能够比不使用增量学习时快几倍,且随着旧样本地不断积累,使用ML-SLDE_I进行样本增量学习的优势会更突出。另外,针对简单增量变形存在的问题,提出基于增量SVD的样本增量学习方案ML-SLDE_SVDI。该方案建立在对联合框架的原形式ML-SLDE提出基于SVD分解的求解算法的基础上,避免了样本增量学习过程中需要在原形式和对偶形式间转换的问题。通过时间复杂度分析,预计该方案在高维低秩情况下能够更好地发挥增量学习的优势。实验结果表明,通过SVD分解对联合框架ML-SLDE进行求解和增量学习能够很好地保持学习精度,并且能比非SVD分解的算法具有更快的训练速度。