基于数据集相似性的分类算法自动选择研究

Different classification algorithm has a different class of data sets on which it performs well, which implies choosing a proper classification algorithm for a given data set is important. However, it is very difficult to select a suitable classification algorithm manually. Therefore, it is of vital importance for choosing a classification algorithm automatically according to the data set characteristics. The key scientific problem of automatic selection of classification algorithms (or algorithm selection for short) is how to characterize the data set features. Most of the existing methods describe the features using statistical and information-theoretic measures. This description would lose some useful information for the classification algorithms, thereby affecting the accuracy of algorithm selection. In addition, there is no theoretical study on the impact of features on classification performance for all existing work, resulting in a lack of theoretical guidance. To sum up, the existing methods have two drawbacks: one is the insufficient feature information; the other is the lack of theoretical analysis. To remedy the above limitations, this project will research on four points. The first point is to extract features for the purpose of preserving as much as information of the problems. Then, we develop an efficient algorithm to compute the similarity between data sets based on the data set features. Next, we establish the relationship between data sets and classification algorithms based on the similarity between the data sets. Finally, we theoretically analyze the impact of features on classification performance. This project is expected to make great progress in feature extraction and theoretical analysis. The research achievements will be applied to algorithm selection. It will open a new way for the practical applications of algorithm selection systems.

不同的分类算法擅长的数据集类型不同，需要针对给定的数据集选择合适的分类算法。人工选择合适的分类算法具有很大的困难。因此，根据数据集的特点自动选择分类算法具有重要的意义。分类算法自动选择（简称算法选择）的关键科学问题是如何描述数据集的特征。已有方法大多采用统计或信息论的特征描述，会丢失一些对分类有用的信息，从而影响算法选择的准确度。此外，已有的工作均无进行特征对分类算法性能影响的理论研究，从而缺乏理论指导。针对目前研究中特征包含的信息不足，以及缺乏理论分析的缺陷，本项目拟研究四个内容：(1)提取特征以尽可能地保留数据集的信息；(2)基于数据集特征，设计出度量数据集相似性的高效算法；(3)基于数据集相似性，建立数据集与分类算法的联系；(4)理论分析特征对分类算法性能的影响。本项目拟希望在特征提取和理论分析方面取得突破性进展，将所取得的成果应用于算法选择，最终为算法选择系统的实际应用开辟新途径。

不同的分类算法擅长的数据集类型不同，需要针对给定的数据集选择合适的分类算法。然而，分类算法的自动选取（简称算法选择）具有极大的挑战性。算法选择的关键问题是提取数据集的特征。已有的特征提取方法无法较好地保留数据集的几何信息，以及缺乏理论分析。针对以上问题，本项目研究根据数据集的几何信息以及分类问题的决策边界来提取数据集的特征。我们通过数据集内积构成的Gram矩阵来保留数据集的几何结构，以及利用数据集的类别信息来描述分类问题的决策边界。数据集相似性的计算是一个NP-hard问题，我们通过问题的特殊结构，提出了高效的算法求解近似解，并理论分析了近似解与精确解的联系。进一步，我们在理论上研究数据集特征的相似程度对支持向量机分类器的影响，结果表明，分类器的性能与数据集的几何信息以及类标相关。与已有的特征相比，我们提出的特征有更好的分类性能。本项目的研究成果将帮助设计性能更好的算法选择系统。