【作者】 张丽新；

【导师】 王家廞；

【作者基本信息】 清华大学 ， 计算机科学与技术， 2004， 博士

【摘要】 图像处理、信息检索以及生物信息学等大规模机器学习问题的不断涌现,对已有的特征选择算法和机器学习算法提出了严峻的挑战,迫切需要适应大规模数据集的准确性和运行效率等综合性能较好的特征选择算法以及机器学习算法。本文在高维数据的特征选择以及基于特征选择的集成学习上开展了研究。主要工作包括以下方面:一、设计了两种串联型组合式特征选择算法。针对Relief评估不能去除冗余特征的缺点,设计了两种串联型组合式特征选择算法:一种为Filter-Filter模式,另一种为Filter-Wrapper模式。在人工数据集上的实验表明,Filter-Filter模式的组合式算法可以有效的克服Relief不能去除冗余特征的缺点,去掉全部或者近似全部的冗余特征,且运行效率高于Filter-Wrapper模式的组合算法;在人工数据集和实际数据集上的实验表明,Filter-Wrapper模式的组合式算法取得了明显高于Filter-Filter模式的测试准确率。二、基于Relief和遗传算法各自的优缺点,提出了Relief和遗传算法耦合的组合式特征选择算法。算法采用 Relief 指导遗传算法种群初始化,目的是提高遗传算法搜索近似最优解的速度,以便在较短时间内寻找到近似最优解。在17个维数较高的数据集上的实验结果表明,从分类准确率,特征子集大小以及运行时间等多角度考察,该算法具有良好的综合性能。三、从个体分类器准确率和个体分类器间差异度两方面出发,提出了一种适于高维数据的基于两步式特征选择的集成学习算法ReFeatEn。实验表明,在特征维数较高,特征间关系较复杂的数据集上,ReFeatEn算法的测试准确率始终优于或相当于Bagging、Boosting和基于随机特征选择的集成学习算法RandFeatEn,并且ReFeatEn的运行速度远高于Bagging和Boosting算法,而且适于并行运行,是一种适用于高维数据的基于特征选择的集成学习算法。四、提出了将特征选择嵌入到Boosting算法中的思路,并设计了总体算法框架,据此分别针对朴素贝叶斯分类器和最近邻中心分类器设计了相应的集成学习算法,解决了Boosting算法对噪声特征较敏感的缺陷,得到的测试准确率显著高于对应的Boosting算法,是一种鲁棒性很强且具有推广性的集成学习算法。更多还原

【Abstract】 The emergence of high-dimensional machine learning fields such as image processing, information retrieval and bioinformatics pose severe challenges to the existing feature selection and machine learning algorithms. This dissertation mainly studies on feature selection and ensemble learning based on feature selection for high-dimensional datasets. Contributions in this dissertation mainly include:(1). Two two-phase combined feature selection algorithms are designed based on Relief evaluation algorithm. One is with filter-filter model, and the other is with filter-wrapper model. For the filter-filter model, in the first phase, Relief algorithm is used to filter the irrelevant features; in the second phase, correlation analysis is utilized to remove the redundant features. For the filter-wrapper model, the first phase is the same with filter-filter model, while in the second phase, backward sequential search algorithm is used to remove the redundant features with the performance of the induction algorithm to be used after feature selection used as evaluation for the feature subsets. Experiments on artificial and real datasets illuminate that the filter-wrapper combined model outperforms filter-filter model with respect to accuracy while is much slower than filter-filter model, and experiments on artificial datasets illuminate that filter-filter combined model can remove all or equal all redundant features.(2). Based on the merits and demerits of Relief and genetic algorithm in wrapper model, a coupling model of Relief and genetic algorithm is proposed, which uses the feature evaluation of Relief to instruct the initialization of genetic population, the coupling model aims to improve the efficiency of genetic algorithm which use the performance of the classifier as evaluation of feature subsets. Experiments on 17 relatively high-dimensional datasets show that, the algorithm has good comprehensive performance with respects to accuracy, size of feature subsets, and efficiency.(3). Considered about the accuracy of individual classifier and diversity among individual classifiers, this dissertation proposes an ensemble learning algorithm <WP=6>based on two-phase feature selection for high-dimensional datasets. Experiments validate that on high-dimensional datasets, accuracy of ReFeatEn is always higher or equally good as Bagging, Boosting and the random subspace ensemble algorithm RandFeatEn. The efficiency of ReFeatEn is much greater than Bagging and Boosting, and also can be run in parallel, so ReFeatEn is very fit for high-dimensional problems.(4). Propose the hypothesis of embedding feature selection into Boosting algorithm, and design a general algorithm structure. Accordingly corresponding ensemble learning algorithms for na?ve Bayesian classifier and nearest mean classifier are designed. Experiment results and analysis show that this novel coupling algorithm solve the problem that Boosting is sensitive to noise features and samples, and gain accuracy which is remarkably higher than the Boosting algorithm, and is robust and easy to be extended for other classifiers.更多还原