分类是机器学习领域重要的任务之一.不同的分类算法对不同类型的数据集存在偏好,故为新数据集选择合适的分类算法充满挑战.一种可行的方法是分类算法自动选择,即根据数据集之间的相似性,为新的数据集推荐最优的分类器.分类器自动选择中最关键的任务是提取数据集特征,因为其决定了数据集相似性的度量,而数据集往往有不同的样本数、维数、类别数以及属性类型.已有的数据集特征从某些角度刻画了数据集的相似性,如统计和几何,但它们与分类器的性能没有太大的联系,从而导致推荐性能欠佳.此外,这些特征也缺乏理论支持.综上所述,本学位论文拟从提取有效的数据集特征和理论分析两方面研究分类器自动选择问题.本学位论文共有四章.第一章介绍分类算法自动选择的研究背景和相关工作;第二章和第三章为本学位论文的主要贡献;第四章是本论文的总结与展望.第二章提出了欧几里得几何结构保持特征来解决已有特征刻画不准确的问题.该特征联合了数据集的内积矩阵以及类别标签,因而可以从几何上同时刻画数据点分布和决策边界.我们认为,分类任务的难度主要由数据集的几何分布以及决策边界形状所共同决定.数据集特征相似性的计算是一个图匹配问题,根据问题的特殊性,我们采用了一种新的方法来求解,比已有的图匹配算法更高效.此外,我们从理论上证明了该特征的相似性与分类器性能相似性的关系,从而保证了我们算法的合理性.直接将该特征推广到核空间中,我们还可以度量数据集的局部几何结构以及非线性结构.最后,我们采用了人工数据集和真实世界的数据集进行模拟实验,该特征的性能优于对比的特征.第三章提出了一种度量分类问题复杂度(简称分类复杂度)的数据集特征来解决已有特征刻画不准确和计算复杂度高的问题.分类复杂度是对分类任务难易程度的一种度量.我们认为,若测得的复杂度与分类器性能有联系,那么具有相同复杂度的分类问题就应该有相同的最优分类器.首先,我们提出了五个几何和统计指标来刻画分类复杂度,然后它们被联合起来作为数据集特征.我们从理论上证明了其中的两个指标和一些分类器的泛化误差上界有联系,从而从理论上保证了特征的准确性.计算复杂度低是这个特征的另一个优点,与已有特征相比,我们的特征可以大大的节省时间,从而在实际应用中可以提升效率.此外,我们还可以将此特征推广到任意的核空间中去刻画数据的非线性结构.最后,我们也采用了人工数据集和真实世界的数据集进行模拟实验,该特征的性能在各方面都优于对比的已有的特征.